聚类是一种非监督学习方法,而K均值聚类(K-Means Clustering)是最基础和最常用的聚类算法。它的基本思想是:通过迭代方式寻找K的簇(Cluster)的一种划分方案,使得聚类结果对应的代价函数最小。特别的,代价函数可以定义为各个样本点到距离其所属簇中心点的误差的平方和:
其中
代表第
个样本,
是
所属的簇,
代表簇对应的中心点,
是样本总数。
K均值聚类的核心目标是将给定的数据集划分成
个簇,并给每个数据对应的簇中心点。算法的具体步骤描述如下:
为迭代步数,重复以下过程直到
收敛: 对于每一个样本
,将其分配至距离最近的簇
对于每一个类簇
,重新计算该类簇的中心
K均值算法在迭代时,假设当前
没有达到最小值,那么首先固定簇中心
,调整每个样例
所属的类别
来让受损失函数
减少,然后固定
,调整簇中心
使得
减少。这两个过程交替循环,
单调递减;当
递减到最小值时,
和
也同时收敛。
K均值算法有一些缺点,例如:
但K均值算法也有一些优点:
是数据对象的数目,
是聚类的簇数,
是迭代的轮数。
Gap Statistic定义为:
其中
是
的期望,一般通过蒙特·卡罗尔模拟产生。
K均值算法的主要缺点: (1)需要人工预先确定初始
值,且该值和真实的数据分布未必吻合。 (2)K均值只能收敛到局部最优,效果受初始值影响很大。 (3)易收到噪声点的影响。 (4)样本点只能被划分到单一的类中。
改进型基本也是朝着能减弱这些缺点的方向来做。
原始K均值算法最开始随机选取数据集中
个点作为聚类中心,而KMeans++算法按照如下的思想选取K和聚类中心:
假设已经选取了n个初始的聚类中心(
),则在选取第
个聚类中心时,距离当前
个聚类中心越远的点会有更高的概率被选为第
个聚类中心。在初次迭代选取第一个聚类中心是(
)仍然是随机选取的,这又符合我们的直觉,因为直观上讲聚类中心离得越远越好。其余过程和经典KMeans算法相同。
ISODATA全称迭代自组织数据分析法(Iterated Self Organization Data)。在KMeans算法中,聚类个数K往往实现由人为决定,计算过程中无法更改。而在海量高维数据的场景下,K的大小是难以估计的。ISODATA基于这个思想进行了改进:
ISODATA算法在K均值算法的基础之上增加了两个操作:
该算法需要四个参数: (1)预期的聚类中心数目
。在ISODATA算法运行过程中聚类中心数可以改变,
只是一个参考值,最终输出的聚类中心一般在
之间。 (2)每个类所需要的最少样本数目
,如果分裂后将导致某个子类别的样本数目小于该阈值,则不会进行分裂操作。 (3)最大方差sigma。用于控制某个类别中样本的分散程度。当样本的分散程度大于这个阈值并且满足条件(2),则进行分裂。 (4)两个聚类中心之间允许的最小距离
,如果两个类之间的距离小于这个阈值,则对这两个类进行合并操作。