有关k-均值聚类算法的理解

有关k-均值聚类算法的理解

有关k-均值聚类算法的理解

1.K-均值聚类算法的历史：

聚类分析作为一种非监督学习方法，是机器学习领域中的一个重要的研究方向，同时，聚类技术也是数据挖掘中进行数据处理的重要分析工具和方法。1967 年MacQueen 首次提出了K 均值聚类算法（K-means算法）。到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数

迄今为止，很多聚类任务都选择该经典算法，K-means算法虽然有能对大型数据集进行高效分类的优点，但K-means算法必须事先确定类的数目k，而实际应用过程中，k 值是很难确定的，并且初始聚类中心选择得不恰当会使算法迭代次数增加，并在获得一个局部最优值时终止，因此在实际应用中有一定的局限性。

半监督学习是近年来机器学习领域的一个研究热点，已经出现了很多半监督学习算法，在很多实际应用中，获取大量的无标号样本非常容易，而获取有标签的样本通常需要出较大的代价。因而，相对大量的无标签样本，有标签的样本通常会很少。传统的监督学习只能利用少量的有标签样本学习，而无监督学习只利用无标签样本学习。半监督学习的优越性则体现在能同时利用有标签样本和无标签样本学习。

有关k-均值聚类算法的理解

针对这种情况，引入半监督学习的思想，对部分已知分类样本运用图论知识迭代确定K-means 算法的K值和初始聚类中心，然后在全体样本集上进行K-均值聚类算法。

2. K-算法在遥感多光谱分类中的应用

基于K-均值聚类的多光谱分类算法

近年来对高光谱与多光谱进行分类去混的研究方法很多，K-均值聚类算法与光谱相似度计算算法都属于成熟的分类算法.这类算法的聚类原则是以数据的均值作为对象集的聚类中心。均值体现的是数据集的整体特征，而掩盖了数据本身的特性。无论是对高光谱还是对多光谱进行分类的方法很多，K-均值算法属于聚类方法中一种成熟的方法。

使用ENVI将多光谱图像合成一幅伪彩色图像见图1，图中可以看出它由标有数字1 的背景与标有数字2 和3的两种不同的气泡及标有数字4的两个气泡重叠处构成。

有关k-均值聚类算法的理解

图1 原始图像

用ENVI进行K-means分类，分类结果如图2，背景被分成标有数字1的红色与标有数字2的绿色两类；一种气泡被分为两类，一类归为标有数字2的绿色的背景类，一类为标有数字4的蓝色的气泡类；另外一种气泡被分为标有数字3的黄色与标有数字5的浅蓝色两类。通过ENVI用K-均值（K-means）进行分类，K-means算法对于两种气泡的分类效果都很好。

有关k-均值聚类算法的理解

图2 K-均值分类后的图像

3. K-算法的步骤：

11第一步：选K个初始聚类中心，Z11,Z2，其中括号内的序号为, Zk

寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。

第二步：逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个Z(

j1)。对所有的i≠j，j=1,2, ,K ，如果

111则 ，X SkZ1,Z2, Zkj其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为Zj。

第三步：计算各个聚类中心的新的向量值Z(

jk 1)，j=1,2, ,K,求

有关k-均值聚类算法的理解

各聚类域中所包含样本的均值向量：

Z(k 1)

j1 NjX S(jK) X

其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的

聚类中心，可使如下聚类准则函数J最小：

K2

J j 1X S(jK) X Z(jk 1)

在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。

第四步：若Z(

jk 1) Z(

jk 1) ，j=1,2, ,K，则返回第二步，将模式

样本逐个重新分类，重复迭代运算；若Z(

jk 1) Z(

jk 1) ，j=1,2, ,K，

则算法收敛，计算结束。

4.K-均值聚类算法的优缺点：

优点：算法的特点是：第一，能根据较少的已知聚类样本的类别对树进行剪枝确定部分样本的分类；第二，为克服少量样本聚类的不准确性，该算法本身具有优化迭代功能，在已经求得的聚类上再次进行迭代修正剪枝确定部分样本的聚类，优化了初始监督学习样本分类不合理的地方；第三，由于只是针对部分小样本可以降低总的聚类时间复杂度。

有关k-均值聚类算法的理解

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

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

③ 从 K-means 算法可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分

有关k-均值聚类算法的理解

析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。

5.K-均值算法的总结：

K-means是最常用的聚类算法之一，能有效地处理规模较大和高维的数据集合，能对大型数据集进行高效分类，把数据分成几组，按照定义的测量标准，同组内数据与其他组数据相比具有较强的相似性，这就叫聚簇。

K-means算法的效率比较高；缺点是只能处理数值型数据，不能处理分类数据，对例外数据非常敏感，不能处理非凸面形状的聚簇。

K-means算法接受输入量k：然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。