11_聚类算法

1 聚类

1.1 什么是聚类

• 聚类就是对大量未知标注的数据集，按照数据内部存在的数据特征将数据集划分为多个不同的类别，使类别内的数据比较相似，类别之间的数据相似度比较小；属于无监督学习

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

• 和分类算法的区别：

  • 分类算法是有监督学习，基于有标注的历史数据进行算法模型构建
  • 聚类算法是无监督学习，数据集中的数据是没有标注的

1.2 相似度/距离公式

1.3 聚类的思想

• 给定一个有M个对象的数据集，构建一个具有k个簇的模型，其中k<=M。满足以下条件：

  • 每个簇至少包含一个对象
  • 每个对象属于且仅属于一个簇
  • 将满足上述条件的k个簇成为一个合理的聚类划分

• 基本思想：对于给定的类别数目k，首先给定初始划分，通过迭代改变样本和簇的隶属关系，使得每次处理后得到的划分方式比上一次的好(总的数据集之间的距离和变小了)

2 K-means算法

2.1 K-means算法步骤

• K-means算法，也称为K-平均或者K-均值，是一种使用广泛的最基础的聚类算法，一般作为掌握聚类算法的第一个算法

• 假设输入样本为T=X₁,X₂,…,X_m；则算法步骤为（使用欧几里得距离公式）：

  • 选择初始化的k个类别中心a₁,a₂,…a_k；
  • 对于每个样本X_i，将其标记位距离类别中心a_j最近的类别j
  • 更新每个类别的中心点a_j为隶属该类别的所有样本的均值
  • 重复上面两步操作，直到达到某个中止条件

• 中止条件：

  • 迭代次数、最小平方误差MSE、簇中心点变化率

2.2 K-means算法思考

• K-means算法在迭代的过程中使用所有点的均值作为新的质点(中心点)，如果簇中存在异常点，将导致均值偏差比较严重

  • 比如一个簇中有2、4、6、8、100五个数据，那么新的质点为24，显然这个质点离绝大多数点都比较远；在当前情况下，使用中位数6可能比使用均值的想法更好，使用中位数的聚类方式叫做K-Mediods聚类(K中值聚类)

• K-means算法是初值敏感的，选择不同的初始值可能导致不同的簇划分规则

  • 为了避免这种敏感性导致的最终结果异常性，可以采用初始化多套初始节点构造不同的分类规则，然后选择最优的构造规则

2.3 K-means算法优缺点

缺点：

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

优点：

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

3 解决K-Means算法对初始簇心比较敏感的问题

3.1 二分K-Means算法

解决K-Means算法对初始簇心比较敏感的问题，二分K-Means算法是一种弱化初始质心的一种算法，具体思路步骤如下：

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

从队列中选择划分聚簇的规则一般有两种方式；分别如下：

• 对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种)，选择SSE最大的聚簇进行划分操作(优选这种策略)
• 选择样本数据量最多的簇进行划分操作

3.2 K-Means++算法

解决K-Means算法对初始簇心比较敏感的问题，K-Means++算法和K-Means算法的区别主要在于初始的K个中心点的选择方面，K-Means算法使用随机给定的方式，K-Means++算法采用下列步骤给定K个初始质点：

• 从数据集中任选一个节点作为第一个聚类中心
• 对数据集中的每个点x，计算x到所有已有聚类中心点的距离和D(X)，基于D(X)采用线性概率选择出下一个聚类中心点(距离较远的一个点成为新增的一个聚类中心点)
• 重复步骤2直到找到k个聚类中心点

缺点：

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

3.3 K-Means||算法

解决K-Means++算法缺点而产生的一种算法；主要思路是改变每次遍历时候的取样规则，并非按照K-Means++算法每次遍历只获取一个样本，而是每次获取K个样本，重复该取样操作O(logn)次，然后再将这些抽样出来的样本聚类出K个点，最后使用这K个点作为K-Means算法的初始聚簇中心点。实践证明：一般5次重复采用就可以保证一个比较好的聚簇中心点。

3.4 Canopy算法

Canopy算法属于一种“粗”聚类算法，执行速度较快，但精度较低，算法执行
步骤如下：

• 给定样本列表L=x₁，x₂…，x_m以及先验值r1和r2(r1>r2)
• 从列表L中获取一个节点P，计算P到所有聚簇中心点的距离(如果不存在聚簇中心，那么此时点P形成一个新的聚簇)，并选择出最小距离D(P,a_j) 【表示p到簇中心点a_j的最小距离】
• 如果距离D小于r1，表示该节点属于该聚簇，添加到该聚簇列表中
• 如果距离D小于r2，表示该节点不仅仅属于该聚簇，还表示和当前聚簇中心点非常近，所以将该聚簇的中心点设置为该簇中所有样本的中心点，并将P从列表L中删除
• 如果距离D大于r1，那么节点P形成一个新的聚簇
• 直到列表L中的元素数据不再有变化或者元素数量为0的时候，结束循环操作

3.4.1 Canopy算法常用应用场景

由于K-Means算法存在初始聚簇中心点敏感的问题，常用使用Canopy+KMeans算法混合形式进行模型构建

• 先使用canopy算法进行“粗”聚类得到K个聚类中心点
• K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点，进行“细”聚类

优点：

• 执行速度快(先进行了一次聚簇中心点选择的预处理)
• 不需要给定K值，应用场景多
• 能够缓解K-Means算法对于初始聚类中心点敏感的问题

4 Mini Batch K-Means算法

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

算法步骤如下：

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

5 聚类算法的衡量指标

5.1 聚类算法的衡量指标—混淆矩阵、均一性、完整性、V-measure

需要引入y

5.2 聚类算法的衡量指标—调整兰德系数(ARI)

需要引入y

5.3 聚类算法的衡量指标—调整互信息(AMI)

需要引入y

5.4 聚类算法的衡量指标—轮廓系数(Silhouette) 重点

• 簇内不相似度：计算样本 i 到同簇其它样本的平均距离为a_i；a_i越小，表示样本 i 越应该被聚类到该簇，簇C中的所有样本的a_i的均值被称为簇C的簇不相似度。
• 簇间不相似度：计算样本 i 到其它簇C_j的所有样本的平均距离b_ij，b_i=min{b_i1,b_i2,…,b_ik}；b_i越大，表示样本 i 越不属于其它簇。
• 轮廓系数：S_i值越接近1表示样本 i 聚类越合理；越接近-1，表示样本 i 应该分类到另外的簇中；近似为0，表示样本 i 应该在边界上；所有样本的S_i的均值被成为聚类结果的轮廓系数

6 层次聚类方法

层次聚类方法对给定的数据集进行层次的分解，直到满足某种条件为止，传统的层次聚类算法主要分为两大类算法：

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

6.1 AGNES算法中簇间距离

• 最小距离(SL聚类)
  • 两个聚簇中最近的两个样本之间的距离(single/word-linkage聚类法)
  • 最终得到模型容易形成链式结构
• 最大距离(CL聚类)
  • 两个聚簇中最远的两个样本的距离(complete-linkage聚类法)
  • 如果存在异常值，那么构建可能不太稳定
• 平均距离(AL聚类)
  • 两个聚簇中样本间两两距离的平均值(average-linkage聚类法)
  • 两个聚簇中样本间两两距离的中值(median-linkage聚类法)

6.2 AGNES和DIANA算法优缺点

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

7 层次聚类优化算法

7.1 BIRCH算法(平衡迭代削减聚类法)（重点）

BIRCH算法(平衡迭代削减聚类法)：聚类特征使用3元组进行一个簇的相关信息，通过构建满足分枝因子和簇直径限制的聚类特征树来求聚类，聚类特征树其实是一个具有两个参数分枝因子和类直径的高度平衡树；分枝因子规定了树的每个节点的子女的最多个数，而类直径体现了对这一类点的距离范围；非叶子节点为它子女的最大特征值；聚类特征树的构建可以是动态过程的，可以随时根据数据对模型进行更新操作。

优缺点：

• 适合大规模数据集，线性效率；
• 只适合分布呈凸形或者球形的数据集、需要给定聚类个数和簇之间的相关参数；

类直径：主要用于判断样本是否属于当前簇
分支因子：当一个节点的子节点数目超过分支因子的时候，那么将这个节点划分成为两个子节点；当一个叶子节点中的样本数目超过分支因子的时候，将叶子节点分成两个叶子节点

7.2 CURE算法(使用代表点的聚类法)

CURE算法(使用代表点的聚类法)：该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是：取消了使用所有点或用中心点+距离来表示一个类，而是从每个类中抽取固定数量、分布较好的点作为此类的代表点，并将这些代表点乘以一个适当的收缩因子，使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景，而且收缩因子的使用可以减少噪音对聚类的影响

优缺点：

• 能够处理非球形分布的应用场景
• 采用随机抽样和分区的方式可以提高算法的执行效率

8 密度聚类方法

• 密度聚类方法的指导思想: 只要样本点的密度大于某个阈值，则将该样本添加到最近的簇中
• 这类算法可以克服基于距离的算法只能发现凸聚类的缺点，可以发现任意形状的聚类，而且对噪声数据不敏感。
• 计算复杂度高，计算量大
• 常用算法：
  • DBSCAN
  • 密度最大值算法

8.1 DBSCAN算法

• DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
• 一个比较有代表性的基于密度的聚类算法，相比于基于划分的聚类方法和层次聚类方法，DBSCAN算法将簇定义为密度相连的点的最大集合，能够将足够高密度的区域划分为簇，并且在具有噪声的空间数据集能够发现任意形状的簇。
• DBSCAN算法的核心思想是：用一个点的ε邻域内的邻居点数衡量该点所在空间的密度，该算法可以找出形状不规则的cluster，而且聚类的时候事先不需要给定cluster的数量

8.1.1 DBSCAN算法基本概念

8.1.2 DBSCAN算法流程

算法流程：

• 如果一个点x的ε邻域包含多余m个对象，则创建一个x作为核心对象的新簇；
• 寻找并合并核心对象直接密度可达的对象；
• 没有新点可以更新簇的时候，算法结束。

算法特征描述:

• 每个簇至少包含一个核心对象
• 非核心对象可以是簇的一部分，构成簇的边缘
• 包含过少对象的簇被认为是噪声

8.1.3 DBSCAN算法优缺点

优点：

• 不需要事先给定cluster的数目
• 可以发现任意形状的cluster
• 能够找出数据中的噪音，且对噪音不敏感
• 算法只需要两个输入参数
• 聚类结果几乎不依赖节点的遍历顺序

缺点：

• DBSCAN算法聚类效果依赖距离公式的选取，最常用的距离公式为欧几里得距离。但是对于高维数据，由于维数太多，距离的度量已变得不是那么重要
• DBSCAN算法不适合数据集中密度差异很小的情况

8.2 密度最大值聚类算法(MDCA)

• MDCA(Maximum Density Clustering Application)算法基于密度的思想引入划分聚类中，使用密度而不是初始点作为考察簇归属情况的依据，能够自动确定簇数量并发现任意形状的簇；另外MDCA一般不保留噪声，因此也避免了阈值选择不当情况下造成的对象丢弃情况。
• MDCA算法的基本思路是寻找最高密度的对象和它所在的稠密区域；MDCA算法在原理上来讲，和密度的定义没有关系，采用任意一种密度定义公式均可，一般情况下采用DBSCAN算法中的密度定义方式 。

8.2.1 MDCA基本概念

8.2.2 MDCA算法聚类过程步骤

• 将数据集划分为基本簇；

  • 对数据集X选取最大密度点P_max，形成以最大密度点为核心的新簇C_i，按照距离排序计算出序列S_pmax，对序列的前M个样本数据进行循环判断，如果节点的密度大于等于density₀，那么将当前节点添加C_i中；
  • 循环处理剩下的数据集X，选择最大密度点P_max，并构建基本簇C_i+1，直到X中剩余的样本数据的密度均小于density₀

• 使用凝聚层次聚类的思想，合并较近的基本簇，得到最终的簇划分；

  • 在所有簇中选择距离最近的两个簇进行合并，合并要求是：簇间距小于等于dist₀,如果所有簇中没有簇间距小于dist₀的时候，结束合并操作

• 处理剩余节点，归入最近的簇

  • 最常用、最简单的方式是：将剩余样本对象归入到最近的簇

9 谱聚类

• 谱聚类是基于谱图理论基础上的一种聚类方法，与传统的聚类方法相比：具有在任意形状的样本空间上聚类并且收敛于全局最优解的优点。
• 通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据进行聚类的目的；其本质是将聚类问题转换为图的最优划分问题，是一种点对聚类算法。
• 谱聚类算法将数据集中的每个对象看做图的顶点V，将顶点间的相似度量化为相应顶点连接边E的权值w，这样就构成了一个基于相似度的无向加权图G(V,E)，于是聚类问题就转换为图的划分问题。基于图的最优划分规则就是子图内的相似度最大，子图间的相似度最小。

9.1 谱聚类的构建过程

1. 构建表示对象相似度的矩阵W
2. 构建度矩阵D(对角矩阵)
3. 构建拉普拉斯矩阵L
4. 计算矩阵L的前k个特征值的特征向量(k个列向量)
5. 将k个列向量组成矩阵U
6. 对矩阵U中的n行数据利用K-means或其它经典聚类算法进行聚类得出最终结果

9.2 拉普拉斯矩阵变形

9.3 谱聚类应用场景及面临的问题

• 应用场景
  • 图形聚类、计算机视觉、非凸球形数据聚类等
• 面临的问题
  • 相似度矩阵的构建问题：业界一般使用高斯相似函数或者k近邻来作为相似度量，一般建议 使用k近邻的方式来计算相似度权值
  • 聚类数目的给定
  • 如何选择特征向量
  • 如何提高谱聚类的执行效率

10 综合案例：图片压缩

有时候在存储图片的时候，我们会在清晰度和图片大小两方面进行进行均衡，对于某些情况下，我们可能会将一个清晰的图片转换成为一个相对不太清晰的图片，因此存储的图片大小会降低很多，这里介绍一种基于聚类算法的减小图片大小的方式，使用K-Means算法对图片进行聚类矢量化图片，从而达到图片压缩的效果 。