A mean gives a set of numerical values one representative value: add the values and divide by their count. For a nonempty set S with n values, μ = (sum of the values in S) / n. It is useful when an algorithm needs a center, but it does not describe how far the values spread around that center. section 10.3.3
In a similarity search tree, a node needs a centroid for its bounding envelope. Treat each child centroid as a point; for each coordinate, take the mean of that coordinate across the children. A leaf’s children are its points, while an internal node’s children are other nodes. After computing the centroid, update the envelope’s radius to include its entries. section 10.3.3
Listing 10.10 The SsNode:: updateBoundingEnvelope method
function SsNode::updateBoundingEnvelope() #1
points ← this.getCentroids() #2
for i in {0..k-1} do #3
this.centroid[i] ← mean{point[i] for point in points} #4
this.radius ←
max{distance(this.centroid, entry)+entry.radius for entry in points} #5
The update operation shows the implementation directly: loop over coordinates, assign each coordinate its mean, then compute the radius. section 10.3.3
The mean also makes variance computable: variance is the mean of the squared differences between each value and the set’s mean. During a similarity search tree split, comparing variance along coordinate axes provides a simple choice of split direction. An axis need not match the true direction of maximum variance when the points are rotated. section 10.3.3
Recentering a cluster
In k-means, assign each point to its closest centroid, then replace each cluster’s centroid with its center of mass. Compute that center coordinate by coordinate: each new coordinate is the mean of the corresponding coordinates of points assigned to the cluster. Repeat assignment and recentering until assignments stop changing or the iteration limit is reached. section 12.2
Check for outliers before relying on a mean as a cluster center. K-means assigns outliers to their closest clusters, and those points can pull the mean—and therefore the centroid—away from a better position. For a scalar mean, one pass can accumulate the sum and count using constant extra space; computing each of k centroid coordinates across m entries requires work proportional to m × k. section 12.2.1 section 10.3.3
