机器学习(四):聚类算法

持续更新中。。。


聚类简介

聚类就是对大量未知标注的数据集,按照数据 内部存在的数据特征 将数据集划分为 多个不同的类别,使 类别内的数据比较相似,类别之间的数据相似度比较小

聚类算法的重点是计算样本项之间的相似度,有时候也称为样本间的距离。

聚类属于无监督学习,和分类算法的区别:
(1)分类算法是有监督学习,基于有标注的历史数据进行算法模型构建
(2)聚类算法是无监督学习,数据集中的数据是没有标注的

聚类算法的衡量指标:

  • 混淆矩阵
  • 均一性
  • 完整性
  • V-measure
  • 调整兰德系数(ARI)
  • 调整互信息(AMI)
  • 轮廓系数(Silhouette)

kmeans

K-means算法,也称为K-平均或者K-均值,是一种使用广泛的最基础的聚类算法,一般作为接触聚类算法的第一个算法。

假设输入样本为 T=X1, X2, …, Xm; 则 算法步骤为(使用欧几里得距离公式):
(1)随机初始化 k 个类别中心 a1, a2,…ak;
(2)对于每个样本 Xi,将其标记为距离类别中心 aj 最近的类别 j
(3)更新每个类别的中心点 aj 为隶属该类别的所有样本的均值
(4)重复上面两步操作,直到达到某个中止条件

中止条件:迭代次数、最小平方误差MSE、簇中心点变化率

K-means算法在迭代的过程中使用所有点的均值作为新的质点(中心点),如果簇中存在异常点,将导致均值偏差比较严重。K-means算法是初值敏感的,选择不同的初始值可能导致不同的簇划分规则。

缺点:

  • K值是用户给定的,在进行数据处理前,K值是未知的,不同的K值得到的结果也不一样;
  • 对初始簇中心点是敏感的
  • 不适合发现非凸形状的簇或者大小差别较大的簇
  • 特殊值(离群值)对模型的影响比较大

优点:

  • 理解容易,聚类效果不错
  • 处理大数据集的时候,该算法可以保证较好的伸缩性和高效率
  • 当簇近似高斯分布的时候,效果非常不错

Mini Batch K-Means

当需要聚类的数据量非常大的时候,效率是最重要的诉求。

Mini Batch K-Means算法是K-Means算法的一种优化变种,采用小规模的数据子集(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)减少计算时间,同时试图优化目标函数;Mini Batch K-Means算法可以减少K-Means算法的收敛时间,而且产生的结果效果只是略差于标准K-Means算法。

算法步骤如下:

  • 首先 抽取部分数据集,使用K-Means算法构建出K个聚簇点的模型
  • 继续抽取训练数据集中的部分数据集样本数据,并将其添加到模型中,分配给距离最近的聚簇中心点
  • 更新聚簇的中心点值
  • 循环迭代第二步和第三步操作,直到中心点稳定或者达到迭代次数,停止计算操作

二分KMeans算法

解决K-Means算法对初始簇心比较敏感的问题,二分K-Means算法是一种弱化初始质心的一种算法。

具体思路步骤如下:

  • 将所有样本数据作为一个簇放到一个队列中
  • 从队列中选择一个簇进行K-means算法划分,划分为两个子簇,并将子簇添加到队列中
  • 循环迭代第二步操作,直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)
  • 队列中的簇就是最终的分类簇集合

从队列中 选择划分聚簇 的规则一般有两种方式;

  • 对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种),选择SSE最大的聚簇进行划分
    操作(优选这种策略)
  • 选择样本数据量最多的簇进行划分操作
由于计算量大,二分KMeans优化算法使用的比较少

Kmeans++

解决K-Means算法对初始簇心比较敏感的问题,使用非常广泛。

K-Means++算法和K-Means算法的区别主要在于K的选择上。K-Means算法使用随机给定的方式。K-means++的思想则是:初始的聚类中心之间的相互距离要尽可能的远

主要步骤如下:

  • 从输入的数据点集合中 随机选择一个点作为第一个聚类中心
  • 对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
  • 选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大
  • 重复2和3直到k个聚类中心被选出来
  • 利用这k个初始的聚类中心来运行标准的k-means算法

从上面的算法描述上可以看到,算法的关键是第3步,如何将D(x)反映到点被选择的概率上,一种算法如下(详见此地):

  • 先从我们的数据库随机挑个随机点当“种子点”
  • 对于每个点,我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里,然后把这些距离加起来得到Sum(D(x))。
  • 然后,再取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先取一个能落在Sum(D(x))中的随机值Random,然后用Random -= D(x),直到其<=0,此时的点就是下一个“种子点”。
  • 重复2和3直到k个聚类中心被选出来
  • 利用这k个初始的聚类中心来运行标准的k-means算法

可以看到算法的第三步选取新中心的方法,这样就能保证距离D(x)较大的点,会被选出来作为聚类中心了。至于为什么原因很简单,如下图 所示:

假设A、B、C、D的D(x)如上图所示,当算法取值Sum(D(x))*random时,该值会以较大的概率落入D(x)较大的区间内,所以对应的点会以较大的概率被选中作为新的聚类中心。

缺点:由于聚类中心点选择过程中的内在有序性,在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)


层次聚类 Hierarchical Clustering

k-means聚类算法的一个变体,主要是为了改进k-means算法随机选择初始质心的随机性造成聚类结果不确定性的问题。

层次聚类算法主要分为两大类算法:

  • 凝聚的层次聚类:AGNES 算法(AGglomerative NESting)==>采用 自底向上 的策略。最初将每个对象作为一个簇,然后这些簇根据某些准则被一步一步合并,两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定;聚类的合并过程反复进行直到所有的对象满足簇数目。
  • 分裂的层次聚类:DIANA 算法(DIvisive ANALysis)==>采用 自顶向下 的策略。首先将所有对象置于一个簇中,然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式距离),直到达到某个终结条件(簇数目或者簇距离达到阈值)。

优缺点

  • 简单,理解容易
  • 合并点/分裂点选择不太容易
  • 合并/分类的操作不能进行撤销
  • 大数据集不太适合
  • 执行效率较低O(t*n 2 ),t为迭代次数,n为样本点数

密度聚类

解决K-Means算法只能发现凸聚类的缺点。

密度聚类可以发现任意形状的聚类,而且对噪声数据不敏感。但是计算复杂度高,计算量大。常用算法为 DBSCAN 和 密度最大值算法。