k均值与k中心算法

定义

K-means Clustering Algorithm 中文名也许叫“K均值聚类算法”，是统计学和数据挖掘领域中常用的一种算法。k-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean^[1]。

聚类

数据聚类 (英语 : Cluster analysis) 是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离等。^[2] 聚类的目标是找出样本中的内在的群组关系。

K均值算法的主要思路(J. MacQueen, 1967)

l  选择聚类的个数k.

l  任意产生k个聚类，然后确定聚类中心，或者直接生成k个中心。

l  对每个点确定其聚类中心点。

l  再计算其聚类新中心.

l  重复以上步骤直到满足收敛要求。(通常就是确定的中心点不再改变).

K均值算法公式

特点

K-means 算法的特点——采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配 ^[3] 。

k-means 算法缺点^[3]

① 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献中，是根据方差分析理论，应用混合 F 统计量来确定最佳分类数，并应用了模糊划分熵来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵的 RPCL 算法，并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。

② 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献 中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。

③ 从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。

K中心点算法^[4]

为了减轻k均值算法对孤立点的敏感性，k中心点算法不采用簇中对象的平均值作为簇中心，而选用簇中离平均值最近的对象作为簇中心。

k中心算法的基本过程是:首先为每个簇随意选择一个代表对象，剩余的对象根据其与每个代表对象的距离分配给最近的代表对象所代表的簇；然后反复用非代表对象来代替代表对象，以优化聚类质量。聚类质量用一个代价函数来表示。当一个中心点被某个非中心点替代时，除了未被替换的中心点外，其余各点被重新分配。

K中心点算法思路：

（1）           随机选择k个代表对象作为初始的中心点

（2）           指派每个剩余对象给离它最近的中心点所代表的簇

（3）           随机地选择一个非中心点对象y

（4）           计算用y代替中心点x的总代价s

（5）           如果s为负，则用可用y代替x，形成新的中心点

（6）           重复(2)(3)(4)(5)，直到k个中心点不再发生变化.

K中心点算法可以看做是K均值算法的一种改进。