聚类分析

聚类分析

聚类分析是非监督学习的很重要的领域。所谓非监督学习，就是数据是没有类别标记的，算法要从对原始数据的探索中提取出一定的规律。而聚类分析就是试图将数据集中的样本划分为若干个不相交的子集，每个子集称为一个“簇”。下面是sklearn中对各种聚类算法的比较。 ### 1.密度聚类（DBSCAN） 密度聚类的思想是不同于KMeans的，但是更符合我们人类的思维，基本的思想是通过是否紧密相连来判断样本点是否属于一个簇。代表性的算法就是DBSCAN (Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法),K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN既可以适用于凸样本集，也可以适用于非凸样本集。它基于一组邻域参数\((\epsilon,MinPts)\)来表征某处样本是否是紧密的。在介绍算法之前先介绍一些概念。 #### (4) 密度聚类原理 DBSCAN是一种基于密度的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。同一类别的样本，他们之间的紧密相连的，也就是说，在该类别任意样本周围不远处一定有同类别的样本存在。

通过将紧密相连的样本划为一类，这样就得到了一个聚类类别。通过将所有各组紧密相连的样本划为各个不同的类别，则我们就得到了最终的所有聚类类别结果。 #### (2)基本概念 * \(\epsilon\)-邻域： 即对于样本点\(x_i\),与它的距离在\(\epsilon\)之内的属于样本集\(D\)中的点的集合，即\(N_\epsilon(x_j)=\{x_i \in D\vert dist(x_i,x_j)\leq\epsilon\}\) * 核心对象： 若\(x_i\)的\(\epsilon\)-邻域至少包含\(MinPts\)个样本，即\(\vert N_\epsilon(x_j)\ge MinPts\vert\)，那么\(x_j\)是一个核心对象。也即是说在核心对象周围的点相对于邻域参数来说是致密的。 * 密度直达：如果\(x_i\)位于核心对象\(x_j\)的\(\epsilon\)-邻域中，则称\(x_i\)由\(x_j\)出发是密度直达的。 * 密度可达：如果存在一个样本序列\(p_1,p_2,...,p_n\),样本皆为核心对象，\(x_i\)由\(p_1\)密度直达，\(x_j\)由\(p_n\)密度直达，且\(p_(k+1)\)由\(p_k\)密度直达，则称\(x_i\)由\(x_j\)出发是密度可达的。也即是说密度可达满足传递性，但不满足对称性，这个可由密度直达的不对称性得出。 * 密度相连：对于\(x_i\)和\(x_j\)如果存在核心对象\(x_k\)，使\(x_i\)和\(x_j\)均由\(x_k\)密度可达，则称\(x_i\)和\(x_j\)密度相连。注意密度相连关系是满足对称性的。 上图为“密度直达”和“密度可达”概念示意描述。根据前文基本概念的描述知道：由于有标记的各点­M、P、O和R的Eps近邻均包含3个以上的点，因此它们都是核对象；M­是从P“密度直达”；而Q则是从­M“密度直达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”（对称）的。 #### (3)DBSCAN密度聚类思想 　　　　DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。

　　　　这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。

　　　　那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

　　　　基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。

　　　　第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象在周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。

　　　　第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。如果大家对于最近邻的思想，距离度量，KD树和球树不熟悉，建议参考之前写的另一篇文章K近邻法(KNN)原理小结。

　　　　第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于ϵ，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。 #### (4)DBSCAN聚类算法 算法表达一： 输入：样本集\(D=(x_1,x_2,...,x_m)\)，邻域参数\((\epsilon,MinPts)\)，样本距离度量方式。 输出:簇划分\(C\) 1. 初始化核心对象集合\(\Omega=\emptyset\)，初始化聚类簇数\(k=0\)，初始化未访问的样本集合\(\Gamma=D\)，簇划分\(C=\emptyset\) 2. 对于\(j=1,2,...,m\)，按下面的步骤找出所有的核心对象： a)通过距离度量方式，找到样本\(x_j\)的\(\epsilon\)-邻域子样本集\(N_\epsilon(x_j)\) b)如果子样本集的样本个数满足\(\vert N_\epsilon(x_j)\vert\ge MinPts\)，将样本\(x_j\)加入核心对象样本集合：\(\Omega=\Omega\cup \{x_j\}\) 3. 如果核心对象集合\(\Omega=\emptyset\)，则算法结束，否则转入步骤4 4. 在核心对象集合\(\Omega\)中，随机选择一个核心对象\(o\)，初始化当前簇核心对象列队\(\Omega_{cur}=\{o\}\)，初始化类别序号\(k=k+1\)，初始化当前簇样本集合\(C_k=\{o\}\)，更新未访问样本集合\(\Gamma=\Gamma-{o}\) 5. 如果当前簇核心对象列队\(\Omega_{cur}\ne\emptyset\),转入步骤6，否则当\(\Omega_{cur}=\emptyset\)，则当前聚类簇\(C_k\)生成完毕，更新簇划分\(C=\{C_1,C_2,...,C_k\}\)，更新核心对象集合\(\Omega=\Omega-C_k\)，转入步骤3 5. 在当前簇核心对象队列\(\Omega_{cur}\)中取出一个核心对象，通过邻域距离阈值\(\epsilon\)找出所有的\(\epsilon\)-邻域子样本集\(N_\epsilon(o^\prime)\)，令\(\Delta=N_\epsilon(o^\prime)\cap\Gamma\)，更新当前簇样本集合\(C_k=C_k\cup \Delta\)，更新未访问样本集合\(\Gamma=\Gamma-\Delta\)，更新\(\Omega_{cur}=\Omega_{cur}\cup(\Delta\cap\Omega)-o^\prime\)，转入步骤5

输出结果为：簇划分\(C=\{C_1,C_2,...,C_k\}\)

算法表达二： 输入： \(D\)：一个包含\(n\)个对象的数据集 \(\epsilon\)：半径参数 \(MinPts\)：邻域密度阈值 输出：基于密度的簇的集合 步骤： 1. 标记所有对象为unvisited 2. Do 3. 随机选择一个unvisited对象\(p\) 4. 标记\(p\)为visited 5. If \(p\)的\(\epsilon\)-邻域至少有\(MinPts\)个对象 6. 　　创建一个新簇\(C\)，并把\(p\)添加到\(C\) 7. 　　令\(N\)为\(p\)的\(\epsilon\)-邻域中的对象集合 8. 　　For \(N\) 中的每个点\(q\) 9. 　　　　If \(q\)是unvisited 10. 　　　　　　标记\(q\)为visited 11. 　　　　　　If \(q\)的\(\epsilon\)-邻域至少有\(MinPts\)个对象，把这些对象添加到\(N\) 12. 　　　　　　If \(q\)还不是任何簇的成员，把\(q\)添加到\(C\) 13.　　End for 14.　　输出\(C\) 15. Else标记\(p\)为噪声 16. Until没有标记为unvisited的对象

(5)DBSCAN小结

　　　　和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点，这点和BIRCH算法类似。

　　　　那么我们什么时候需要用DBSCAN来聚类呢？一般来说，如果数据集是稠密的，并且数据集不是凸的，那么用DBSCAN会比K-Means聚类效果好很多。如果数据集不是稠密的，则不推荐用DBSCAN来聚类。

　　　　下面对DBSCAN算法的优缺点做一个总结。

　　　　DBSCAN的主要优点有：

　　　　1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。

　　　　2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。

　　　　3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。

　　　　DBSCAN的主要缺点有：

　　　　1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。

　　　　2） 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。

　　　　3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。