K-MEANS算法(K均值算法)

k-means算法

一．算法简介

k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。

二．划分聚类方法对数据集进行聚类时包括如下三个要点：

（1）选定某种距离作为数据样本间的相似性度量

k-means聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。

X??xm|m?1,2,...,total?假设给定的数据集 ，X中的样本用d个描述属性A1,A2…Ad来表示，并且d个描述属性都是连续型属性。数据样本xi=(xi1,xi2,…xid), xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分别是样本xi和xj对应d个描述属性A1,A2,…Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。

d欧式距离公式如下： ?xi,xj??

??xk?1dik?xjk?2（2）选择评价聚类性能的准则函数

k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…XK；

各个聚类子集中的样本数量分别为n1，n2,…,nk;各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。

则误差平方和准则函数公式为： E???p?mii?1p?Xik2（3）相似度的计算根据一个簇中对象的平均值来进行。 1) 将所有对象随机分配到k个非空的簇中。

2) 计算每个簇的平均值，并用该平均值代表相应的簇。 3) 根据每个对象与各个簇中心的距离，分配给最近的簇。

4) 然后转2），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。

三．算法描述

1. 为中心向量c1, c2, …, ck初始化k个种子 2. 分组:

a) 将样本分配给距离其最近的中心向量

b) 由这些样本构造不相交（ non-overlapping ）的聚类 3. 确定中心:

a) 用各个聚类的中心向量作为新的中心 4. 重复分组和确定中心的步骤，直至算法收敛

四．算法流程

输入：簇的数目k和包含n个对象的数据库。 输出：k个簇，使平方误差准则最小。 算法步骤：

1.为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。 2.将样本集中的样本按照最小距离原则分配到最邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。 4.重复步骤步直到聚类中心不再变化。

5.结束，得到K个聚类

五．算法举例

数据对象集合S见表1，作为一个聚类分析的二维样本，要求的簇的数量k=2。

O 1 2 3 4 5 X 0 0 5 5 Y 2 0 0 0 2 OM(1)选择 O 1 ? 0,2 ?， 2 ? 0,0 1 ? O 1 ? ? 0,2 ? ， 2?O2??0,0??为初始的簇中心，即 M(2)对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。 对 O 3 ：d ?M1,O3???0?1.5???2?0??2.5d?M2,O3???0?1.5???0?0??1.5CO显然 d 2 , 3 ? ? d ?M 1 ,O 3? ，故将 3 分配给 2O?M2222dM,O?0?5?0?0?5??????对于 O 4 ： d?M1,O4???0?5???2?0??2924c因为 d ? M 2, O 4 ? ? d ? M 1, O 4 ? ，所以将 O 24 分配给

对于 O 5 ：d ?M1,O5??2222?0?5???2?2??5d?M2,O5???0?5???0?2?? d?M? ，所以将 O因为 d 1 ,O 5? ? M 2 ,O 5 5 分配给C 1更新，得到新簇 C 1 ? ? O 1 ,O 5? 和 C 2??O2,O3,O4?计算平方误差准则，单个方差为

222??25 E1???0?0???2?2????0?5?2?2????????总体平均方差是： E?E1?E2?25?27.25?52.2522222?29E2?27.25（3）计算新的簇的中心。 M 1???0?5?2,?2?2?2???2.5,2?

M2???0?1.5?5?3,?0?0?0?3???2.17,0?重复（2）和（3），得到O1分配给C1；O2分配给C2，O3分配给C2 ，O4分配给

C1? ?O??C2，O5分配给C1。更新，得到新簇 1, O 5 ? C 2和 O 2 , O 3 ,O 4? 。 中心为 M 1 ? ?2 . 5 ,2 ? ， M 2 ? ? 2.17,0 ? 。 单个方差分别为

2222????12.5?E?0?2.5?2?2?2.5?5?2?2???????? 1????

E2?13.15

总体平均误差是： E?E?E?12.5?13.15?25.6512由上可以看出，第一次迭代后，总体平均误差值~，显着减小。由于在两次迭代中，簇中心不变，所以停止迭代过程，算法停止。

六．k-means算法的性能分析

k-means算法的优缺点 主要优点：

1. 是解决聚类问题的一种经典算法，简单、快速。

2. 对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是0 (n k

t ) , 其中, n 是所有对象的数目, k 是簇的数目, t 是迭代的次数。通常k <

3. 当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。 主要缺点

1. 在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适

用。

2. 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，

可能会导致不同结果。

3. 它对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生

极大的影响。

针对K-Means算法对于不同的初始值，可能会导致不同结果。解决方法： 1.多设置一些不同的初值，对比最后的运算结果）一直到结果趋于稳定结束，比较耗时和浪费资源

2.很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。

3. 所谓的gapstatistics（ Gap统计模型） ISODATA算法

ISODATA算法与K-均值算法的比较：

1. K-均值算法通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活； 2. 从算法角度看， ISODATA算法与K-均值算法相似，聚类中心都是通过样本均

值的迭代运算来决定的；

3. ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其

能利用中间结果所取得的经验更好地进行分类。主要是在选代过程中可将一类一分为二，亦可能二类合二为一，即“自组织”，这种算法具有启发式的特点。

ISODATA算法与K-means相比在下列几方面有改进：

1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制心距离小于

，以及类间中心距离参数

。若出现两类聚类中

的情况，可考虑将此两类合并。

分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数用以决定是否需要将某一类分裂成两类。

2.由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。

ISODATA算法基本步骤和思路

选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。 计算各类中诸样本的距离指标函数。

（3）~（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。

重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。 k-means算法初始中心的选取对算法的影响

，