K-Means如何运作？

Question

我对K-Means的工作方式感到迷茫和困惑.到目前为止我所知道的是

1. 情节n分,说7分
2. 随机选择k点,比如3点,它们将作为质心
3. 质心将是类的类型,所以我们有3个类
4. 选择一个点来分类它的类
5. 所选择的3中最接近的等级将对所选择的点进行分类

我已经实现了获取包含这些点的文本文件.选择文件后,将绘制点.现在我停在那里.

这是我想知道的:

1.我想知道在绘制点之后我应该做的下一件事,因为我不确定我上面说的算法.

2.我想知道迭代是如何工作的,迭代得到每个点的最终类.我很困惑,因为我不知道如果从类最近的点获得类,拾取点如何更改类

任何帮助将非常感激.

Answer 1

K-Means的输入是一组点(观察)和一个整数K.目标是将输入点划分为K个不同的集合(集群).

第一步是通过选择K个初始聚类质心位置来初始化算法.这通常通过从输入集中随机选择K点来完成.使用这些初始K质心,算法通过重复以下两个主要步骤来继续:

1)群集分配 - 这里,每个观察(例如,数据集中的每个点)被分配给群集质心,使得WCSS目标函数被最小化.这通常可以转换为将每个观察分配给最近的聚类质心(这对于许多距离度量而言恰好最小化WCSS),但是对于一些距离度量和空间,这不是必须的.
2)更新质心 - 在将所有输入观测值分配给聚类质心后,重新计算每个质心.对于每个聚类,通过对分配给它的观察值求平均来计算新的质心(例如,计算观察值的"平均值").

重复这些步骤直到算法"收敛".有几种方法可以检测收敛.最典型的方法是运行,直到没有观察结果改变集群成员资格.作为附加提示,如果您为每次迭代计算WCSS(如下所述),您应该看到它减少(例如,随着算法运行,误差应该变小).如果没有,你的实现可能有一个bug.

同样重要的是要理解K-Means因陷入局部最小值而臭名昭着.这意味着最终结果可能不是最好的结果.为了克服这个问题,K-Means通常使用不同的起点(初始质心)运行多次,并选择具有最低误差的运行.

群内平方和(WCSS)用于衡量误差(在维基百科上有解释:http://en.wikipedia.org/wiki/K-means_clustering).WCSS计算为

totalError = 0;
foreach(Point p in inputData)
{
    // compute p's error
    pError = someDistanceFunc(p, p_centroid)^2 
    totalError += pError;
}

基本上,对于每个点,您可以根据它与质心的接近程度来计算误差测量值.将所有这些错误相加以计算总错误.

互联网上有很多K-Means信息.如需更深入的描述,我推荐Andrew Ng的Coursera讲座:http://www.youtube.com/watch？v = Ao2vnhelKhI