聚类方法

聚类属于无监督学习，因为输入的数据是没有标签的，通过算法每个样本自动的划分到相应的簇中。

K-means

k均值是一种基于形心的技术。给定一个包含n 个数据对象的数据库，以及要生成的簇的数目k，一个划分类的算法将数据对象组织为k 个划分（k≤n），其中每个划分代表一个簇。通常会采用一个划分准则（经常称为相似度函数，similarity function），例如距离dist(i,j)，以便在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。

K-means把簇的形心定义为簇内点的均值，通过贪心的方法不断迭代形心的坐标，直到形心的坐标不再改变而结束迭代。

步骤

算法的步骤为：

• 首先在数据集D中选择k个对象，每个对象代表一个簇的初试均值即形心。
• 对剩下的对象，根据其与这个k个形心的欧式距离将其分配到距离最近的形心的簇。
• 完成了分配后重新计算每个簇的均值中心点并更新。
• 使用更新后的均值中心点，重新分配每一个对象。
• 不断迭代，直到本轮的中心点与上一轮的相同，即本轮形成的簇与上一轮相同。

伪代码

伪代码为：

K-means对离群点敏感，因为当一个离群点被分配到一个簇的时候，可能会严重扭曲簇的均值。

k中心点算法是基于对象的，通过挑选实际的对象来代表簇，其余的对象被分配与其最为相似的代表对象所在的簇。

参考

《数据挖掘概念与技术》第3版 第十章聚类分析：基本概念和方法