k-means和二分k-means算法

以你之姓@ 2022-01-07 08:43 269阅读 0赞

聚类算法是机器学习中的一类无监督学习方法，用于将无标签的数据进行聚类划分。最简单的也最典型的一类算法就是KMeans算法。此处的K表示划分成K个聚类。利用各个点到质心之间的距离的平方和作为将节点划分到不同类的标准。当然也可以采用其他的距离计算方法，不一定是欧式距离方法。

一、KMeans

此方法一般是在数据分析前期使用，选取适当的K，将数据聚类后，研究不同聚类下数据的特点。

算法原理：

（1）随机选择K个中心点；

（2）在第j次迭代中，对于每个样本点，选取最近的中心点，归为该类；

（3）更新中心点为每类的均值；

（4）j < j-1，重复（2）（3）迭代更新，直到误差小到某个值或者达到一定的迭代步数，误差不变，也就是收敛为止；

空间复杂度为O（n），时间复杂度为O（l\*K\*N），其中N为样本个数，K为中心点个数，即聚类数，I为迭代次数

为什么迭代后误差逐渐减小：

SSE= ![804917-20160904175320383-954261983.png][]

对于![804917-20160904175917768-2122669790.png][] 而言，求导后，当![20190627073831571.png][] 时，SSE最小，对应第(3)步；

对于![804917-20160904175938035-561869282.png][] 而言，求导后，当![804917-20160904175945645-1649964697.png][]  时，SSE最小，对应第(2)步。

因此KMeans迭代能使误差逐渐减少直到不变

二、二分kmeans算法

上述kmeans算法还是存在一定的问题，即它对初始选取的k比较敏感，一旦k选取不合适就容易陷入局部最优解的怪圈中，而不是全局最优解，而接下来引入的二分kmeans算法就是用于解决此类问题的一个算法。一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和），对应clusterAssment矩阵的第一列之和。SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。  
那么如何对结果进行改进？你可以对生成的簇进行后处理，一种方法是将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-均值聚类算法，其中的K为2。

有两种可以量化的办法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。第一种思路通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程，直到找到合并最佳的两个簇为止。接下来将讨论利用上述簇划分技术得到更好的聚类结果的方法。

二分kmeans算法伪代码如下：

为克服K-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分K均值（bisectingK-means)的算法, 该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。

二分K-均值算法的伪代码形式如下：  
将所有点看成一个簇  
当簇数目小于k时  
对于每一个簇  
计算总误差  
在给定的簇上面进行K-均值聚类（k=2)  
计算将该簇一分为二之后的总误差  
选择使得误差最小的那个簇进行划分操作

另一种做法是选择SSE最大的簇进行划分，直到簇数目达到用户指定的数目为止。这个做法听起来并不难实现。下面就来看一下该算法的实际效果。

# 二分`k-means`算法 #

二分`k-means`算法是分层聚类（[Hierarchical clustering][]）的一种，分层聚类是聚类分析中常用的方法。  
分层聚类的策略一般有两种：

*  聚合。这是一种`自底向上`的方法，每一个观察者初始化本身为一类，然后两两结合
 *  分裂。这是一种`自顶向下`的方法，所有观察者初始化为一类，然后递归地分裂它们

二分`k-means`算法是分裂法的一种。

## 1 二分`k-means`的步骤 ##

二分`k-means`算法是`k-means`算法的改进算法，相比`k-means`算法，它有如下优点：

*  二分`k-means`算法可以加速`k-means`算法的执行速度，因为它的相似度计算少了
 *  能够克服`k-means`收敛于局部最小的缺点

二分`k-means`算法的一般流程如下所示：

*  （1）把所有数据初始化为一个簇，将这个簇分为两个簇。
 *  （2）选择满足条件的可以分解的簇。选择条件综合考虑簇的元素个数以及聚类代价（也就是误差平方和`SSE`），误差平方和的公式如下所示，其中w(i)

w(i)表示权重值，y∗

*  y∗表示该簇所有点的平均值。

![这里写图片描述][SouthEast]

*  （3）使用`k-means`算法将可分裂的簇分为两簇。
 *  （4）一直重复（2）（3）步，直到满足迭代结束条件。

以上过程隐含着一个原则是：因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点越接近于它们的质心，聚类效果就越好。  
所以我们就需要对误差平方和最大的簇进行再一次的划分，因为误差平方和越大，表示该簇聚类越不好，越有可能是多个簇被当成一个簇了，所以我们首先需要对这个簇进行划分。

[804917-20160904175320383-954261983.png]: /images/20211223/955d98f3ec6a4d14a60e34df4c30bb29.png
[804917-20160904175917768-2122669790.png]: https://images2015.cnblogs.com/blog/804917/201609/804917-20160904175917768-2122669790.png
[20190627073831571.png]: /images/20211223/b124b2e7166b47c0b29f53eb5dfec1a8.png
[804917-20160904175938035-561869282.png]: https://images2015.cnblogs.com/blog/804917/201609/804917-20160904175938035-561869282.png
[804917-20160904175945645-1649964697.png]: /images/20211223/9c1f725f67784c35b6e2da9c42f19843.png
[Hierarchical clustering]: https://en.wikipedia.org/wiki/Hierarchical_clustering
[SouthEast]: /images/20211223/2abe1f5c2bc8407b9df8183adfcb1d07.png