vlambda博客
学习文章列表

聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分离。

K-means可以work的理论基础是假定了数据点符合同方差的高斯分布模型，通过最大似然估计得到的k-means的迭代方法，这个函数是个非凸函数，根据初始值不同只能得到局部最优解。 

一、K-means算法

K-均值算法是发现给定数据集的k个簇的算法，簇个数是用户给定的，每一个簇通过其质心（centroid）即簇中所有点的中心来描述。

 1、K-均值算法的流程：

（1）对于输入样本集 {x1,x2,...,xm}，随机确定k个质心 {μ1,μ2,...,μk}；

（2）计算每个样本xj到各个质心μi的欧式距离：dji=||xj-μi||2；

（3）根据距离最近的μ确定样本xj的簇标记：labelj=arg minidji；

（4）循环将数据集中的每个样本分配到各个簇中（染色），每个簇的样本数量为N1,N2,...,Nk；

（5）更新每个簇的质心的位置，为该簇所有样本的均值；

（6）重复上述步骤（染色分配-移动质心-重新染色-再次移动...），直到所有的质心均不再更新；或者达到设定的某个终止条件，如最大迭代次数、最小调整幅度阈值、最小平方误差MSE等。 

注：

K-means的变体为K-Mediods：

1. 计算新的簇中心的时候不再使用选择均值，而是选择中位数；

2. 抗噪能力得到增强

 

二、二分K-means算法

为了克服K-means算法容易收敛于局部极小值的问题，可以使用bisecting K-means算法弱化随机初始质心的影响。该算法首先将所有的样本作为一个簇，然后根据某种规则将该簇一分为二；之后选择其中一个簇继续划分，直到达到停止条件（聚簇数量、迭代次数、最小SSE等）。

1. 选择划分聚簇的规则一般有两种：

（1）选择样本量最大的簇进行划分；

（2）选择SSE值最大的簇进行划分。

2. K-means的损失函数

每个点到中心点的位置MSE

3.具体步骤：

 

分别计算四个簇的MSE，会发现有两个簇的MSE很小，一个簇的MSE很大。

选择合并簇中心比较近，MSE很小的簇。切分簇中心离其他簇中心比较远，MSE比较大的簇。

 

三、K-means++算法

K-means++算法可以解决K-means对初始质心比较敏感的问题，算法的区别主要在于选择的初始k个质心的之间的相互距离要尽可能的远。

K-means++算法的流程是：

（1）从数据集中随机选择一个样本作为第一个质心；

（2）对数据集中的每个样本，计算它到所有已有质心的距离的总和D(x)；

（3）采用线性概率选择出下一个聚类中心点，即D(x)较大的点成为新增质心的概率较大；

（4）重复步骤2直到找到k个聚类中心点

（5）使用得到的k个质心作为初始化质心运行K-means算法。

K-means++算法的缺点：

（1）有可能选中离群点作为质心；

（2）计算距离质心最远的点的开销比较大；

（3）由于质心的选择过程中的内在有序性（第k个质心的选择依赖前k-1个质心的值），在扩展方面存在着性能问题。

 

四、K-means||算法

解决K-means++算法缺点而产生的一种算法，主要思路是改变每次遍历时候的取样规则，并非按照K-means++算法每次遍历只获取一个样本，而是每次获取k个样本，重复该取样操作logm次，然后再将这些抽样出来的样本聚类出k个质心，作为K-means算法的初始质心。实践证明，一般只需要5次重复采样就可以得到比较好的初始质心。

五、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）循环迭代（2、3）步操作，直到质心稳定或者达到指定迭代次数，停止计算。

 

六、层次聚类

• 解决了k-means k值选择和初始中心点选择的问题。

• 分为分裂法和凝聚法。

 

1. 凝聚法：

将所有点看做一个独立的簇：

While 不满足条件：

计算两两簇之间的距离，找到最小离的簇C1 和C2（多种计算方式）

合并C1 C2

合并C1 C2的方式：

1. 两个簇间距离最小的样本距离

2. 两个簇间最远的两个点的距离

3. 两个簇之间两两求距离的平局值

4. 两个粗之间两两求距离的中位数

5. 求每个集合的中心点，用中心点的距离代表簇的距离

 

2. 分裂法：

将所有样本归为一个簇

While 不满足条件（k个数或距离阈值）∶

在同一个簇C中计算样本间距离，选最远的距离的两个样本 ab（终止条件检测）；

将样本a，b划入cl c2（终止条件检测）；

计算原簇c中样本离谁近，划入谁。

 

七、Canopy聚类

Canopy属于一种‘粗’聚类算法，即使用一种简单、快捷的距离计算方法将数据集分为若干可重叠的子集canopy，这种算法不需要指定k值、但精度较低，可以结合K-means算法一起使用：先由Canopy算法进行粗聚类得到k个质心，再使用K-means算法进行聚类。

Canopy算法步骤如下：

（1）将原始样本集随机排列成样本列表L=[x1,x2,...,xm]（排列好后不再更改），根据先验知识或交叉验证调参设定初始距离阈值T1、T2，且T1>T2 。

（2）从列表L中随机选取一个样本P作为第一个canopy的质心，并将P从列表中删除。

（3）从列表L中随机选取一个样本Q，计算Q到所有质心的距离，考察其中最小的距离D：

如果D≤T1，则给Q一个弱标记，表示Q属于该canopy，并将Q加入其中；

如果D≤T2，则给Q一个强标记，表示Q属于该canopy，且和质心非常接近，所以将该canopy的质心设为所有强标记样本的中心位置，并将Q从列表L中删除；

如果D>T1，则Q形成一个新的聚簇，并将Q从列表L中删除。

（4）重复第三步直到列表L中元素个数为零。

 

注意：

（1）‘粗’距离计算的选择对canopy的分布非常重要，如选择其中某个属性、其他外部属性、欧式距离等。

（2）当T2<D≤T1时，样本不会从列表中被删除，而是继续参与下一轮迭代，直到成为新的质心或者某个canopy的强标记成员。

（3）T1、T2的取值影响canopy的重叠率及粒度：当T1过大时，会使样本属于多个canopy，各个canopy间区别不明显；当T2过大时，会减少canopy个数，而当T2过小时，会增加canopy个数，同时增加计算时间。

（4）canopy之间可能存在重叠的情况，但是不会存在某个样本不属于任何canopy的情况。

（5）Canopy算法可以消除孤立点，即删除包含样本数目较少的canopy，往往这些canopy包含的是孤立点或噪音点。

 

八、密度聚类

基于密度的聚类算法假设聚类结构能够通过样本分布的紧密程度确定，以数据集在空间分布上的稠密程度为依据进行聚类，即只要一个区域中的样本密度大于某个阈值，就把它划入与之相近的簇中。

密度聚类的主要特点是：发现任意形状的簇，对噪声数据不敏感，一次扫描，需要密度参数作为停止条件，计算量大、复杂度高。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是基于一组邻域参数（ε，MinPts）来描述样本分布的紧密程度，相比于基于划分的聚类方法和层次聚类方法，DBSCAN算法将簇定义为密度相连的样本的最大集合，能够将密度足够高的区域划分为簇，不需要给定簇数量，并可在有噪声的空间数据集中发现任意形状的簇。

 

1、基本概念（参考西瓜书）：

给定的数据集D={x(1),x(2),...,x(m)}

（1）ε-邻域（Eps）：对x(j)∈D，其ε-邻域包含D中与x(j)的距离不大于ε的所有样本。

 

（2）MinPts：ε-邻域内样本个数最小值。

（3）核心对象：若x(j)的ε-邻域至少包含MinPts个样本，|Nε(x(j))|≥MinPts，则x(j)为一个核心对象。

（4）密度直达（directly density-reachable）：若x(j)位于x(i)的ε-邻域中，且x(i)是核心对象，则称x(j)由x(i)密度直达。密度直达关系通常不满足对称性，除非x(j)也是核心对象。

（5）密度可达（density-reachable）：对x(i)与x(j)，若存在样本序列p1,p2,...,pn，其中p1=x(i)，pn=x(j)，p1,p2,...,pn-1均为核心对象且pi+1从pi密度直达，则称x(j)由x(i)密度可达。密度可达关系满足直递性，但不满足对称性。

（6）密度相连（density-connected）：对x(i)与x(j)，若存在x(k)使得x(i)与x(j)均由x(k)密度可达，则称x(i)与x(j)密度相连。密度相连关系满足对称性。

 

（7）基于密度的簇：由密度可达关系导出的最大的密度相连样本集合C，簇C满足以下两个性质：

连接性（connectivity）：x(i)∈C，x(j)∈C → x(i)与x(j)密度相连；

最大性（maximality）：x(i)∈C，x(j)由x(i)密度可达 → x(j)∈C。

 

2、DBSCAN算法原理与流程

DBSCAN算法先任选数据集中的一个核心对象作为种子，创建一个簇并找出它所有的核心对象，寻找合并核心对象密度可达的对象，直到所有核心对象均被访问过为止。

DBSCAN的簇中可以少包含一个核心对象：如果只有一个核心对象，则其他非核心对象都落在核心对象的ε-邻域内；如果有多个核心对象，则任意一个核心对象的ε-邻域内至少有一个其他核心对象，否则这两个核心对象无法密度可达；包含过少对象的簇可以被认为是噪音。

 

3、DBSCAN算法的优缺点

优点：

不需要事先给定簇的数目k；

适于稠密的非凸数据集，可以发现任意形状的簇；

可以在聚类时发现噪音点、对数据集中的异常点不敏感；

对样本输入顺序不敏感。

缺点：

对于高维数据效果不好；

不适于数据集中样本密度差异很小的情况；

调参复杂，给定eps选择过大的MinPts会导致核心对象数量减少，使得一些包含对象较少的自然簇被丢弃；

选择过小的MinPts会导致大量对象被标记为核心对象，从而将噪声归入簇；

给定MinPts选择过小的eps会导致大量的对象被误标为噪声，一个自然簇被误拆为多个簇；

选择过大的eps则可能有很多噪声被归入簇，而本应分离的若干自然簇也被合并为一个簇；

 数据量很大时算法收敛的时间较长，可对搜索最近邻时建立的KD-tree或Ball-tree进行规模限制。

 

九、密度最大值聚类（MDCA）

MDCA（Maximum Density Clustering Algorithm）算法将基于密度的思想引入到划分聚类中，使用密度而不是初始质心作为考察簇归属情况的依据，能够自动确定簇数量并发现任意形状的簇。MDCA一般不保留噪声，因此也避免了由于阈值选择不当而造成大量对象丢弃情况。

MDCA算法的基本思路是寻找最高密度的对象和它所在的稠密区域，在原理上MDCA和密度的定义无关，采用任意一种密度定义公式均可，一般采用DBSCAN算法中的密度定义方式。

1、基本概念：

给定数据集D，density(p) 表示对象p的密度，

（1）最大密度点： 

（2）密度阈值density0：

当对象的密度值大于密度阈值时，认为该对象属于一个比较固定的簇。在第一次构建基本簇的时候，就将这些对象添加到对应的簇中，如果小于阈值的时候，暂时认为该对象为噪声。

（3）Spmax序列的对象密度曲线：

根据所有对象与pmax的欧式距离对数据集重新排序 

说明：

图像横轴为对象与pmax的欧式距离，纵轴为该对象所处位置的密度。

第一个波谷表明左侧的对象与pmax距离较近、处在同一个基本簇内，波谷的密度较低；

波谷右侧的密度又开始升高，说明对象属于其他的簇。

从数据集中移除已经划归为第一个基本簇的所有对象，从剩余对象中再次计算最大密度点并绘制对象密度曲线(b)。

（4）簇间距离阈值dist0：

对于两个基本簇Ci和Cj，采用二者最近两个成员之间的邻近度作为簇间距离

当两个基本簇的簇间距离小于给定阈值的时候，合并这两个基本簇。

（5）M值：基本簇中最多样本总数。

2、算法步骤

（1）将数据集划分为基本簇

对数据集选取最大密度点pmax，按照距离排序得到Spmax；

对序列前M个样本数据进行判断，如果对象密度大于等于density0，那么将当前对象添加到基本簇Ci中；

从数据集中删除Ci中包含的所有对象，处理余下的数据集，选择最大密度点pmax’，并构建基本簇Ci+1；

循环操作直到数据集剩余对象的密度均小于density0。

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

在所有簇中选择距离最近的两个簇进行合并；

合并要求是：簇间距小于等于dist0；

如果所有簇中没有簇间距小于dist0的时候，结束合并操作。

（3）处理剩余点

如果保留噪声：则扫描所有剩余对象，将其中与某些簇距离小于或等于dist0的对象归入相应的最近的簇；

与任何簇的距离都大于的dist0的对象视为噪声。

如果不保留噪声：则把每个剩余对象划给最近的簇。