1
$\begingroup$

I am new to clustering and am a bit confused on how the following code can compute centroid information without the original euclidean vectors.

import numpy as np
from scipy.cluster import hierarchy
import matplotlib.pyplot as plt

# Create an array of distances
x = np.array([100., 200., 300., 400., 500., 250.,
              450., 280., 450., 750.])
 
# compute linkage
temp = hierarchy.linkage(x, method="centroid")

This code runs without error and is using 'centroid' as the link method. I am confused as to how this is even possible. My guess is there might be a formula which maps distance pair values to the centroid distance value.

I tried looking at various sources, including scipy documentation, but they all mention taking on average of the original data. Is there some reference which discusses how one can compute centroid distances without the original euclidean data?

$\endgroup$
2
  • 1
    $\begingroup$ You might want to read docs.scipy.org/doc/scipy/reference/generated/… including Note 2 towards the end which says "it is the user’s responsibility to assure that these distances are in fact Euclidean, otherwise the produced result will be incorrect" I am not sure your example distances are consistent with that, but if they were then some geometric shortcuts might be possible including the Unweighted Pair-Groups Method Centroid algorithm. $\endgroup$
    – Henry
    Aug 20, 2022 at 20:47
  • $\begingroup$ How to compute distances between centroids from pairwise eucludean distance matrix: stats.stackexchange.com/q/148847/3277 $\endgroup$
    – ttnphns
    Aug 21, 2022 at 22:04

1 Answer 1

0
$\begingroup$

Thanks to @Henry for pointing me to the end of the documentation which points to this paper:

Modern hierarchical, agglomerative clustering algorithms

In the paper a general clustering algorithm is described in Fig 1. The author specifies that centroid, and many other clustering strategies, can be thought of as a distance update algorithm. Thus, the need for the original euclidean data is not needed to calculate the centroids. The author does not derive the formulas but this was enough to satisfy my curiosity.

$\endgroup$
1
  • $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes or disappears. $\endgroup$
    – Glorfindel
    Aug 21, 2022 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.