# How is finding the centroid different from finding the mean?

When performing hierarchical clustering, one can use many metrics to measure the distance between clusters. Two such metrics imply calculation of the centroids and means of data points in the clusters.

What is the difference between the mean and the centroid? Aren't these the same point in cluster?

As far as I know, the "mean" of a cluster and the centroid of a single cluster are the same thing, though the term "centroid" might be a little more precise than "mean" when dealing with multivariate data.

To find the centroid, one computes the (arithmetic) mean of the points' positions separately for each dimension. For example, if you had points at:

• (-1, 10, 3),
• (0, 5, 2), and
• (1, 20, 10),

then the centroid would be located at ((-1+0+1)/3, (10+5+20)/3, (3+2+10)/3), which simplifies (0, 11 2/3, 5). (NB: The centroid does not have to be--and rarely is---one of the original data points)

The centroid is also sometimes called the center of mass or barycenter, based on its physical interpretation (it's the center of mass of an object defined by the points). Like the mean, the centroid's location minimizes the sum-squared distance from the other points.

A related idea is the medoid, which is the data point that is "least dissimilar" from all of the other data points. Unlike the centroid, the medoid has to be one of the original points. You may also be interested in the geometric median which is analgous to the median, but for multivariate data. These are both different from the centroid.

However, as Gabe points out in his answer, there is a difference between the "centroid distance" and the "average distance" when you're comparing clusters. The centroid distance between cluster $A$ and $B$ is simply the distance between $\text{centroid}(A)$ and $\text{centroid}(B)$. The average distance is calculated by finding the average pairwise distance between the points in each cluster. In other words, for every point $a_i$ in cluster $A$, you calculate $\text{dist}(a_i, b_1)$, $\text{dist}(a_i, b_2)$ , ... $\text{dist}(a_i, b_n)$ and average them all together.

• Under what conditions the centroid and the medoid be identical? And also why the centroid is a good representative of a set of points? – raikumardipak Jan 21 '18 at 20:57
• @dkr, You might want to ask this as a new question to get more (and more in-depth) responses. That said, the difference boils down to two things: 1) the thing to be minimized (squared distance/L2 norm for the centroid, absolute distance/L1 norm for mediod) and 2) Whether the output can be any point (centroid) or must be in the data set (mediod). You can imagine cases where they'll be the same, but in general, they will not. The centroid is "good" for the same reasons the mean is (smallest sum-squared distance to the points) and also has similar drawbacks (e.g., not robust against outliers). – Matt Krause Jan 21 '18 at 23:00

The above answer may be incorrect see this video: https://www.youtube.com/watch?v=VMyXc3SiEqs It seems that average adds up all the combinations of distances between the elements of cluster 1 and cluster 2 - that is n^2 distances added together and then divides by n^2 to the average.

Centroid method first computes the average of each cluster within itself. Then it calculates one distance between those average points.

• Hi Gabe! I think you're talking about this part of the video? As far as I know, the centroid and mean of a single cluster are the same thing but, as you pointed out, the centroid distance and average distance between two clusters are different measures. I thought the OP was asking about the former, but I just edited in a bit about the latter too. Thanks for pointing that out (+1) and welcome to Cross Validated! – Matt Krause Oct 10 '15 at 0:14

centroid is average of data points in a cluster, centroid point need not present in the data set whereas medoid is the data point which is closer to centroid,medoid has to be present in the original data

Let $$x_1,\dots ,x_n\in \mathbb{R}^d$$ and $$\{C_1,C_2\}$$ a partition of $$\{1,\dots,n\}$$. Let $$d$$ be a metric in $$\mathbb{R}^d$$, positive homogeneous (for instance, the euclidean distance)

Define $$\alpha := d(\frac{1}{|C_1|}\sum_{i\in C_1}x_i,\frac{1}{|C_2|}\sum_{j\in C_2}x_j)$$ and $$\beta := \frac{1}{|C_1|}\frac{1}{|C_2|}\sum_{i\in C_1}\sum_{j\in C_2} d(x_i,x_j)$$

Claim: $$\alpha \leq \beta$$

Proof: The function $$\phi:= d(\cdot ,\frac{1}{|C_2|}\sum_{j\in C_2}x_j)$$ is convex (this follows by the triangle inequality of the metric + positive homogeneity). Therefore, by Jensen's Inequality

$$\alpha = \phi(\frac{1}{|C_1|}\sum_{i\in C_1}x_i) \leq \frac{1}{|C_1|}\sum_{i\in C_1}\phi(x_i)$$

For every fixed $$x_i$$ the function $$\psi_i := d(x_i , \cdot )$$ is also convex. Replacing above, we get $$\alpha \leq \frac{1}{|C_1|}\sum_{i\in C_1}\psi_i(\frac{1}{|C_2|}\sum_{j\in C_2}x_j)$$

Using one more time Jensen's Inequality we get

$$\alpha \leq \frac{1}{|C_1|}\sum_{i\in C_1}\frac{1}{|C_2|}\sum_{j\in C_2}\psi_i(x_j) = \beta$$