k均值算法的基本原理

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

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

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

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

半监督学习是近年来机器学习领域的一个研究热点，已经出现了很多半监督学习算法，在很多实际应用中，获取大量的无标号样本非常容易，而获取有标签的样本通常需要出较大的代价。因而，相对大量的无标签样本，有标签的样本通常会很少。传统的监督学习只能利用少量的有标签样本学习，而无监督学习只利用无标签样本学习。半监督学习的优越性则体现在能同时利用有标签样本和无标签样本学习。 针对这种情况，引入半监督学习的思想，对部分已知分类样本运用图论知识迭代确定K-means 算法的K值和初始聚类中心，然后在全体样本集上进行K-均值聚类算法。

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

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

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

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

一种改进的K-均值聚类算法

摘要：在K-均值聚类算法中，K值需事先确定且在整个聚类过程中不能改变其大小，而按照经验K值划分所得的最终聚类结果一般并非最佳结果。本文将最大最小距离算法与K-均值算法结合，通过最大最小距离算法估算出K值，再用K-均值算法改进聚类精度。

1. 概述

聚类(cluster)做为数据挖掘技术的主要研究领域之一，近年来被广泛应用于各行各业。聚类分析方法做为一种无监督的学习方法，采用“物以类聚”的思想，将数据对象按某些属性分组成为多个类或簇，并且使得同类或簇中数据对象相似度尽可能大，而不同类或簇之间的差异尽可能大。K- 均值聚类算法是聚类分析中一种基本的划分方法，因其思想可靠，算法简洁，而且能有效的应用于大数据集而被广泛使用。但是传统的K 均值聚类算法往往受初始中心点选取的影响并且常常终止于局部最优。因此初始中心点的选择在K-均值聚类算法中非常重要，通常希望找到散布较大的点作为初始中心点。但是在传统的K-均值聚类算法中初始中心点选择的随机性较强，导致聚类结果的随机性。而且在传统的K-均值聚类算法中K的值需要给定，如果K值给定的不合理也将影响聚类的效果。

针对以上缺点本文将最大最小距离聚类算法和传统的K-均值聚类算法结合。形成一种初始中心点的距离最大，中心点数自动调整的K-均值算法。以达到更高的聚类精度。

2．K-均值聚类算法基本思想

K 均值聚类算法是一种基于划分方法的经典聚类算法之一，该算法的核心思想如下：首先从所给n 个数据对象中随机选取k 个对象作为初始聚类中心点，然后对于所剩下的其它对象，则根据它们与所选k 个中心点的相似度(距离)分别分配给与其最相似的聚类，然后在重新计算所获聚类的聚类中心(该聚类中所有对象的均值)，不断重复这一过程直到标准测度函数开始收敛为止，其基本算法流程如下：

1) 从n个数据对象中任意选择k个对象作为初始聚类中心。

2) 根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离并根据最小距离对相应对象进行划分。

k均值算法的基本原理

k均值算法是一种常见的聚类算法，它可以将一组数据分为k个不同的簇或群体。在这种算法中，每个簇都由一个代表点或中心点来表示，该中心点是该簇中所有数据点的平均值。k均值算法的基本原理可以总结为以下几个步骤：

1. 初始化：首先需要确定要将数据分成多少个簇，即确定k的值。然后随机选择k个数据点作为初始的中心点。

2. 分配数据点到簇：对于每个数据点，根据其与每个中心点的距离，将其分配到距离最近的簇中。

3. 更新簇的中心点：对于每个簇，计算其中所有数据点的平均值，将该平均值作为新的中心点。

4. 重新分配数据点到簇：根据新的中心点，重新分配每个数据点到距离最近的簇中。

5. 重复步骤3和步骤4，直到簇的中心点不再变化或达到预定的迭代次数。

k均值算法的核心思想是通过不断更新簇的中心点，使得簇内的数据点趋于聚集，而簇间的数据点相对分散。通过迭代的过程，最终达到数据点在各个簇内部相似度高、簇之间相似度低的效果。

k均值算法的优缺点:

k均值算法是一种简单而有效的聚类算法，具有以下优点：

1. 算法简单易懂：k均值算法的计算过程相对简单，容易理解和实现。

2. 可扩展性强：k均值算法可以处理大规模数据集，其计算复杂度较低。

3. 结果可解释性强：通过k均值算法得到的聚类结果可以很直观地解释，每个簇都有自己的中心点。

然而，k均值算法也存在一些缺点：

1. 对初始值敏感：k均值算法的结果受初始中心点的选择影响较大，不同的初始中心点可能导致不同的聚类结果。

2. 只适用于凸型数据集：k均值算法假设每个簇都是凸型的，这意味着对于非凸型的数据集，可能会导致聚类结果不理想。

3. 需要提前确定k的值：k均值算法需要事先确定要将数据分为多少个簇，而实际应用中往往难以确定合适的k值。

为了克服k均值算法的一些缺点，研究人员还提出了一些改进的方法，例如k均值++算法、k均值++算法等。这些改进算法在初始中心点的选择上更加合理，可以得到更好的聚类结果。

1K-means算法原理

模型

1967年，JamesMacQueen提出“K-Means”（K均值），是基于距离的聚

类算法。两个对象距离越近，相似度越大，对指定的K个划分，迭代确定每个

簇的中心和比较靠近该中心的归属节点，达到平方误差最小的平衡状态。

算法

算法的描述如下：1、随机选取k个聚类质心点（clustercentroids）为u1,u2,…,uk∈Rn.

2、重复下面过程直到收敛{

对于每一个样例i，计算与质心的最小距离，判断其应该属于的类

对于每一个类j，重新计算该类的质心，向量的平均值

}

算法的目标函数如下：

J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。

固定每类的质心u(j)，调整样本的所属类别c(i)，让J函数减少。然后，固定c(i)，

调整每个类的质心u(j)，使J减少。当J递减到最小时，u和c也同时收敛。函

数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值。

K-means算法体现了EM迭代的思想，E步是估计隐含类别y的期望值，M步

调整其他参数使得在给定类别y的情况下，极大似然估计P(x,y)能够达到极大值。

然后在其他参数确定的情况下，重新估计y，周而复始，直至收敛。用K-means

解释就是开始不知道每个样本对应的隐含变量类别c(i)，E步随便定一个c(i)给

样本，然后是M步让P(x,c(i))最大（这里是让J最小），求出给定c的情况下，

J最小时的质心u(j)（其他参数），质心确定后，重新E步估计样本的更好c(i)

（归属到距离小的相似质心分类中，使J最小），c(i)得到重新调整。重复到c

没有调整。算法是硬指定隐含类别变量给一个样本，而不是对每个类别赋予不同

的概率。总体思想是一个迭代优化过程，有目标函数，也有参数变量，只是多了

个隐含变量类别c(i)，确定其他参数质心u(j)估计隐含变量，再确定隐含变量估

计其他参数，直至目标函数最优。

问题

算法的缺点是：类型数目k需要首先较为合理的确定下来，没有在迭代过程中优