转载

机器学习经典算法详解及Python实现--聚类及K均值、二分K-均值聚类算法

摘要

聚类是一种无监督的学习（无监督学习不依赖预先定义的类或带类标记的训练实例），它将相似的对象归到同一个簇中，它是观察式学习，而非示例式的学习，有点像全自动分类。说白了，聚类（clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。机器学习中常见的聚类算法包括 k-Means算法、期望最大化算法（Expectation Maximization，EM，参考“ EM算法原理 ”）、谱聚类算法（参考机器学习算法复习-谱聚类）以及人工神经网络算法，本文阐述的是K-均值聚类算法，本文介绍K-均值（K-means）和二分K-均值聚类算法。

（一）何谓聚类

还是那句“物以类聚、人以群分”，如果预先知道人群的标签（如文艺、普通、2B），那么根据监督学习的分类算法可将一个人明确的划分到某一类；如果预先不知道人群的标签，那就只有根据人的特征（如爱好、学历、职业等）划堆了，这就是聚类算法。

聚类是一种无监督的学习（无监督学习不依赖预先定义的类或带类标记的训练实例），它将相似的对象归到同一个簇中，它是观察式学习，而非示例式的学习，有点像全自动分类。所谓簇就是该集合中的对象有很大的相似性，而不同集合间的对象有很大的相异性。簇识别（cluster identification）给出了聚类结果的含义，告诉我们这些簇到底都是些什么。通常情况下，簇质心可以代表整个簇的数据来做出决策。聚类方法几乎可以应用于所有对象，簇内的对象越相似，聚类的效果越好。

从机器学习的角度讲，簇相当于隐藏模式，聚类与分类的最大不同在于，分类学习的实例或数据对象有类别标记，而聚类则不一样，需要由聚类学习算法自动确定标记。因为其产生的结果与分类相同，而只是类别没有预先定义，所以聚类也被称为无监督分类（unsupervised classification )。

聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。

聚类分析试图将相似对象归入同一簇，将不相似对象归到不同簇，那么是否“相似”就要有所选择的相似度计算方法。现在，存在多种不同的相似度计算方法，到底使用哪种相似度计算方法取决于具体应用，选择合适的相似度计算方法才会提高聚类算法的性能。机器学习中常用的相似性度量方法参考博文“ 机器学习中的相似性度量 ”。

聚类算法通常按照中心点或者分层的方式对输入数据进行归并，所以的聚类算法都试图找到数据的内在结构，以便按照最大的共同点将数据进行归类，其目标是使同一类对象的相似度尽可能地大；不同类对象之间的相似度尽可能地小。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法，参考“各种聚类算法的比较”。聚类算法的基本过程包含特征选择、相似性度量、聚类准则、聚类算法和结果验证等，具体参考“聚类算法学习笔记（一）——基础”。

说白了，聚类（clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。简单理解，如果一个数据集合包含N个实例，根据某种准则可以将这N个实例划分为m个类别，每个类别中的实例都是相关的，而不同类别之间是区别的也就是不相关的，这就得到了一个聚类模型了。判别新样本点的所属类时，就通过计算该点与这m个类别的相似度，选择最相似的那个类作为该点的归类。

既然聚类可以看做是一种无监督分类，那么其应用场景就是广泛的，包括用户群划分、文本分类、图像识别等等。当几乎没有有关数据的先验信息(如统计模型)可用，而用户又要求尽可能地对数据的可能性少进行假设等限制条件下，聚类方法都适合用来查看数据点中的内在关系以对它们的结构进行评估、决策。

机器学习中常见的聚类算法包括 k-Means算法、期望最大化算法（Expectation Maximization，EM，参考“EM算法原理”）、谱聚类算法（参考机器学习算法复习-谱聚类）以及人工神经网络算法，本文介绍K-均值（K-means）聚类算法。

（二）K-均值（K-means）聚类算法

1. 认识K-均值聚类算法

K-均值算法是最简单的一种聚类算法，属于分割式聚类算法，目的是使各个簇（共k个）中的数据点与所在簇质心的误差平方和SSE(Sum of Squared Error）达到最小，这也是评价K-means算法最后聚类效果的评价标准。

k-means算法的基础是最小误差平方和准则。其代价函数是：

机器学习经典算法详解及Python实现--聚类及K均值、二分K-均值聚类算法

式中，μ _c(i) 表示第i个簇的质心，我们希望得到的聚类模型代价函数最小，直观的来说，各簇内的样本越相似，其与该簇质心的误差平方越小。计算所有簇的误差平方之和，即可验证分为k个簇时时的聚类是否是最优的。 SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标，聚类的目标是在保持族数目不变的情况下提高簇的质量。

k-均值（k-means）聚类算法之所以称之为k-均值是因为它可以发现k个不同的簇，且每个簇的中心采用簇中所含子数据集样本特征的均值计算而成。k-均值是发现给定数据集的k个簇的算法，簇个数k由用户给定，每一个簇通过其质心( centroid) -- 即簇中所有点的中心来描述。K-均值聚类算法需要数值型数据来进行相似性度量，也可以将标称型数据映射为二值型数据再用于度量相似性，其优点是容易实现，缺点是可能收敛到局部最小值，在大规模数据集上收敛较慢。

假设训练样本数据集X为(m, n）维矩阵，m表示样本数、n表示每个样本点的特征数，那么k-均值聚类算法的结果就是得到一个kxn维矩阵，k表示用户指定的簇个数，每一行都是一个长度为n的行向量--第i个元素就是该簇中所有样本第j（j=0,1,...,n-1）个特征的均值。下图是K-均值聚类算法聚类的过程：

机器学习经典算法详解及Python实现--聚类及K均值、二分K-均值聚类算法

2. 算法过程

K-均值算法的工作流程是这样的。首先，随机确定k个初始点作为质心；然后将数据集中的每个点分配到一个簇中--就是为每个点找距其最近的质心，并将其分配给该质心所对应的簇；该步完成之后更新每个簇的质心（该簇所有数据样本特征的平均值）；上述过程迭代多次直至所有数据点的簇归属不再改变或者达到了最大迭代次数Maxiteration。k-均值算法的性能会受到所选相似性度量方法的影响，常用的相似性度量方法就是计算欧氏距离。上述过程的伪代码表示如下：

***************************************************************

创建k个点作为起始质心

任意点的簇分配结果发生改变时（循环内设置、维护标志位changed，也可同时设定最大迭代次数max）

对数据集中的每个数据点

对每个质心

计算质心与数据点之间的距离

将数据点分配到距其最近的簇（若有点的簇发生改变则置标志位为changed = True）

更新簇中心：对每一个簇，计算簇中所有点的均值并将均值作为质心

***************************************************************

上述循环的终止条件是每个点的簇分配结果没有发生改变或者达到了最大循环次数。

初始化时k个质心的选择可以是随机的，但为了提高性能常用的方式是

（1）尽量选择距离比较远的点（方法：依次计算出与已确定的点（第一个点可以随机选择）的距离，并选择距离最大的点）。当k比较大时，这种方法计算量比较复杂，适合二分K-均值聚类算法的k值初始化。

（2）采取层次聚类的方式找出k个簇。 TBD

3. 特征值处理

K-均值聚类算法需要数值型数据来进行相似性度量，也可以将标称型数据映射为二值型数据再用于度量相似性。

另外，样本会有多个特征，每一个特征都有自己的定义域和取值范围，他们对 distance计算的影响也就不一样，如取值较大的影响力会盖过取值较小的参数。为了公平，样本特征取值必须做一些scale处理，最简单的方式就是所有特征的数值都采取归一化处置，把每一维的数据都转化到0,1区间内，从而减少迭代次数，提高算法的收敛速度。

4. k值的选取

前面提到，在k-均值聚类中簇的数目k是一个用户预先定义的参数，那么用户如何才能知道k的选择是否正确？如何才能知道生成的簇比较好呢？与K-近邻分类算法的k值确定方法一样,k-均值算法也可采用交叉验证法确定误差率最低的k值，参考“机器学习经典算法详解及Python实现--K近邻(KNN)算法”的2.3节-k值的确定。

当k的数目低于真实的簇的数目时，SSE（或者平均直径等其他分散度指标）会快速上升。所以可以采用多次聚类，然后比较的方式确定最佳k值。多次聚类，一般是采用 k=1, 2, 4, 8... 这种二分数列的方式，通过交叉验证找到一个k在 v/2, v 时获取较好聚类效果的v值，然后继续使用二分法，在 [v/2, v] 之间找到最佳的k值。

5. K-均值算法的Python实现

下载地址：TBD

K-均值算法收敛但聚类效果较差的原因是，K-均值算法收敛到了局部最小值，而非全局最小值（局部最小值指结果还可以但并非最好结果，全局最小值是可能的最好结果)。为克服k- 均值算法收敛于局部最小值的问题，有人提出了另一个称为二分k- 均值（bisecting K-means)的算法。

（三）二分K-均值（bisecting k-means)聚类算法

顾名思义，二分K-均值聚类算法就是每次对数据集（子数据集）采取k=2的k-均值聚类划分，子数据集的选取则有一定的准则。二分K-均值聚类算法首先将所有点作为一个簇，第一步是然后将该簇一分为二，之后的迭代是：在所有簇中根据SSE 选择一个簇继续进行二分K-均值划分，直到得到用户指定的簇数目为止。根据SSE选取继续划分簇的准则有如下两种:

(1)选择哪一个簇进行划分取决于对"其划分是否可以最大程度降低SSE的值。这需要将每个簇都进行二分划分，然后计算该簇二分后的簇SSE之和并计算其与二分前簇SSE之差（当然SSE必须下降），最后选取差值最大的那个簇进行二分。

该方案下的二分k-均值算法的伪代码形式如下：

***************************************************************

将所有数据点看成一个簇

当簇数目小于k时

对每一个簇

计算总误差

在给定的簇上面进行k-均值聚类（k=2）

计算将该簇一分为二后的总误差

选择使得误差最小的那个簇进行划分操作

***************************************************************

(2)另一种做法是所有簇中选择SSE最大的簇进行划分，直到簇数目达到用户指定的数目为止，算法过程与（1）相似，区别仅在于每次选取簇中SSE最大的簇。