查找K均值聚類中的最小方差

Question

我有一組二維點，我想用K均值算法來劃分出正確數量的聚類。

我讀到，對於固定數量的聚類，我應該運行幾次並找到給出最小方差的結果。

例如，說我知道，集羣的「正確」的個數爲4。因此，在這個例子中的僞代碼：

List<kmeansResult> result; 

for(int i = 0 ; i < numIteration; ++i) 
{ 
    result.Add(kmeans.Compute(4)); 
} 

而且我會獲得4類10種不同的方式result，每個都有其各自的羣集差異。

我在這種情況下的問題是如何量化「最小」方差。由於方差在2維中，即var(X)和var(Y)，可能存在其中var(X)被簡化但不是var(Y)的情況。將2合併在一起會是一個很好的措施？

Answer 1

一個常見的做法是儘量減少sum { (C_i - x_i) \cdot (C_i - x_i) i=1,...,n}，其中：

• C_i - 中央的點集羣的我
• x_i - i點
• \cdot - 積
• n - 樣本數量

這個想法是儘量減少L2與簇的距離，導致每個簇緊密聚集在一起。

簡而言之，它基本上是將每個點與其質心的歐氏距離相加 - 但沒有采用euclidean distance metric中的平方根。