查找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中的平方根。