基于划分的方法

1、基于划分的方法是简单、常用的一种聚类方法；

2、通过将对象划分为互斥的簇进行聚类，每个对象属于且仅属于一个簇；

3、划分结果旨在使簇之间的相似性低，簇内部的相似度高；

4、基于划分的方法常用算法有k均值、k-medoids、k-prototype等；

K-均值算法

k-均值聚类是基于划分的聚类算法，计算样本点与类簇质心的距离，与类簇质心相近的样本点划分为同一类簇。k-均值通过样本间的距离来衡量它们之间的相似度，两个样本距离越远，则相似度越低，否则相似度越高

首先选取 k 个类簇（k需要用户进行指定）的质心，通常是随机选取。

对剩余的每个样本点，计算它们到各个质心的欧式距离，并将其归入到相互间距离最小的质心所在的簇。计算各个新簇的质心。

在所有样本点都划分完毕后，根据划分情况重新计算各个簇的质心所在位置，然后迭代计算各个样本点到各簇质心的距离，对所有样本点重新进行划分。

重复第（2）步和第（3）步, 直到迭代计算后，所有样本点的划分情况保持不变，此时说明k-均值算法已经得到了最优解，将运行结果返回

k-均值算法原理简单，容易实现，且运行效率比较高

k-均值算法聚类结果容易解释，适用于高维数据的聚类

k-均值算法采用贪心策略，导致容易局部收敛，在大规模数据集上求解较慢

k-均值算法对离群点和噪声点非常敏感，少量的离群点和噪声点可能对算法求平均值产生极大影响，从而影响聚类结果

k-均值算法中初始聚类中心的选取也对算法结果影响很大，不同的初始中心可能会导致不同的聚类结果。对此，研究人员提出k-均值++算法，其思想是使初始的聚类中心之间的相互距离尽可能远

k-均值算法簇的聚类中心选取受到噪声点的影响很大，因为噪声点与其他样本点的距离远，在计算距离时会严重影响簇的中心。

k-medoids 算法克服了k-均值算法的这一缺点， k -medoids算法不通过计算簇中所有样本的平均值得到簇的中心，而是通过选取原有样本中的样本点作为代表对象代表这个簇，计算剩下的样本点与代表对象的距离，将样本点划分到与其距离最近的代表对象所在的簇中；

距离计算过程与k均值算法的计算过程类似，只是将距离度量中的中心替换为代表对象，绝对误差标准如下；

k-prototype 算法的聚类过程与k-均值算法相同，只是在聚类过程中引入参数γ来控制数值属性和分类属性的权重。