Merging multiple average values without calculating total

user_2872388 0
Viewed 439

I currently have multiple [Average, Count] pairs from serialized data. User wants the ability to merge(group) some sets of values together and get the aggregated result.

I am like its easy, I will just do Sum(Average * Count) / Sum(Count)

But the problem is, some of the values are very large, its causing arithmetic overflow if I sum all of them.

Is there a way to merge the average part without calculating the total? Count part is pretty obvious.

math statistics
2 Answers

Assuming that Count and Average are indexed values, you can compute your aggregate average this way:

TotalCount = Sum(Count)
TotalAverage = Sum(Average * (Count/TotalCount))

If you want to calculate the values in a single iteration over your serialized data, you can sum successive weighted averages in a manner that looks like exponential averages.

TotalCount = 0
TotalAverage = 0
for each index in data-set of [Average, Count]
    TotalCount = TotalCount + Count[index]
    Weight = Count[index]/TotalCount
    TotalAverage =   TotalAverage * (1 - Weight)
                   + Average[index] * Weight

You can derive the right approach by considering the first two pairs.

If there was only the first pair:

TotalCount = Count[1]
TotalAverage = Average[1]

But, if there are two pairs:

TotalCount = Count[1] + Count[2]
TotalAverage =   Average[1] * (Count[1]/TotalCount) 
               + Average[2] * (Count[2]/TotalCount)

If we were iterating from the first pair into the second pair, then the two pair calculation could look like:

TotalCount = TotalCount + Count[2]
TotalAverage =   TotalAverage * (TotalCount - Count[2])/TotalCount
               + Average[2]   * (Count[2]/TotalCount)

If we let Weight represent Count[2]/TotalCount, the above simplifies to:

TotalCount = TotalCount + Count[2]
Weight = Count[2]/TotalCount
TotalAverage =   TotalAverage * (1 - Weight)
               + Average[2] * Weight

Since TotalCount and TotalAverage is correct at each step that takes on a new pair of the serialized data, the [2] can be replaced with an iteration index.

user_3150520

While answer by @jxh is good and solve your problem, his and your original approach does two passes over pairs data (first for total count, then for average), which could harm performance. You could do it in one pass, doing rolling average. It could be used even if pairs are coming from the stream, and you don't know how many of them are here

Some Python code:

data = [(3.1, 12), (5.2, 17), (9.7, 11)]

total_count = 0
total_avg   = 0.0
for avg, count in data:
    n0 = total_count
    total_count += count

    p = float(n0) / float(total_count)
    total_avg = p*total_avg + (1.0 - p)*avg

print(total_count)
print(total_avg)
user_40446960
Related