本篇文章分享一些日常工作中最常用的聚类算法做介绍,全文较长,全文较长,欢迎点赞收藏。
来源:https://zhuanlan.zhihu.com/p/78382376,作者:Slumbers(美团)
对于有标签的数据,我们进行有监督学习,常见的分类任务就是监督学习;而对于无标签的数据,我们希望发现无标签的数据中的潜在信息,这就是无监督学习。
聚类,就是无监督学习的一种,它的概念是:将相似的对象归到同一个簇中,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起,不同数据尽量分离。
聚类算法有很多种分法,体系也很大,这里举例几种分法:
其实还有很多分类,但这里不再列举了,有兴趣的同学可以参考sklearn文档中关于聚类的划分:
https://scikit-learn.org/stable/modules/clustering.html#clustering
这个可以说是最基础的聚类算法了,它的输入需要簇的个数k,这个k是用户指定的,也就是说需要提前确定类别,其算法流程是:
随机确定$k$个初始点$u_1, u_2...u_k$作为聚类质心
重复以下过程直到收敛:
对于每一个样例,找到离它最近的质心作为label:
对于每一个类j, 更新其质心:
主要是速度快
k-means有一些改进算法,多是针对k-means会受异常点的影响这一点来改进的,比如K-Means++, K-Medians...
基于密度的算法,要求聚类空间的一定区域所包含的对象的数目不小于某一给定阈值,先了解一些基本概念:
(1)Eps邻域:给定对象半径Eps内的邻域称为该对象的Eps邻域;
(2)核心对象(core point):如果对象的Eps邻域至少包含最小数目MinPts的对象,则称该对象为核心对象;
(3)直接密度可达(directly density-reachable):若某点p在点的q的Eps领域内,且q是一个核心对象,则p-q直接密度可达
(4)密度可达(density-reachable):如果存在一个对象链 p1, …,pi,.., pn,如果对于任意pi, pi-1都是直接密度可达的,则称pi到pi-1密度可达,实际上是直接密度可达的传播链
(5)密度相连(density-connected):如果从某个核心对象p出发,点q和点k都是密度可达的,则称点q和k是密度相连的。
(6)边界点(edge point):边界点不是核心对象,但落在某个核心对象的邻域内;
(7)噪音点(outlier point):既不是核心点,也不是边界点的任何点;
看看上图,红色点是所谓的核心对象,以它为圆心,Eps为半径去画圆,在圆内样本点数目大于MinPts的就是核心对象;被包含在核心对象的范围内,但是自身不是核心对象的点是样本点;即不被包含在核心对象内,自身也不是核心对象的点为噪音点,将被抛弃。
DBSCAN的核心思想是从某个核心点出发,不断向密度可达的区域扩张,从而得到一个包含核心点和边界点的最大化区域,区域中任意两点密度相连。现在我们来看看DBSCAN的一个算法流程,会更容易理解:
输入:给定点在领域内成为核心对象的最小领域点数(MinPts), 领域半径: Eps
输出:簇集合
伪代码如下:
首先将数据集D中所有的对象标记为未处理状态:
对数据集D中的每个对象p:
if p已经归入了某个簇:
continue
else:
检查对象p的Eps领域 NEps(p)
if NEps(p)包含的对象数小于MinPts:
标记对象p为边界点或者噪声点;
else:
标记对象p为核心点,并建立新簇C,将p领域内的所有点加入C
for (NEPs(p)中所有尚未处理的对象q):
检查对象q的领域NEps(q), 若NEps(q)包含至少MInPts个对象,则将NEps(q)中未归入
任何一个簇的对象加入C
从上面的图形中可以看出来:kmeans和DBSCAN的对比可以看出DBSCAN对这种数据分布的拟合更好
这是一个对DBSCAN的改进算法,结合了密度聚类和层次聚类。它的优化点主要如下:
可达距离是对DBSCAN中核心距离的一个改进版,也是DBSCAN的改进算法OPTICS的主要核心思想,也就是通过改变距离的度量方式减少dbscan对阈值Eps的敏感性;该距离可以让稀疏的点离密度高的区域更远。了解可达距离之前,我们先看看核心距离:
核心距离
:对于给定的样本点,使得该点成为核心点的最小Eps为该点的核心距离。
假设样本点为p, 找到以p为圆心,刚好满足minPts的最外层的点q,则p和q的距离为核心距离;看下图,加入我们的MinPts设为3,那么找到以红色点P为圆心,MinPts正好为3的半径 即为核心距离
可达距离
:对于样本点p周围的点q1,q2...,1n,如果这些点到点p的距离大于p的核心距离,则可达距离为该点到p的实际距离;如小于,则可达距离为点x的核心距离。我们继续看上图,点1,2,3的可达距离均为核心距离,而在核心距离之外的点4,5, 它们到点P的距离仍然是欧式距离。
那么为什么要用可达距离替换欧氏距离呢?
看看下图中,蓝色核心点和绿色核心点原本的距离应该是两点的欧氏距离,但是因为蓝色核心点在绿色核心点的核心距离内,所以此时它们的可达距离为绿色核心点的半径>两点的欧氏距离,相当于把蓝色核心点和绿色核心点区分开了;
红色核心点到蓝色核心点的距离一样,它们的可达距离要大于蓝色核心点和红色核心点的实际距离,这样以蓝色核心点为代表的高密度区域与红色核心点、绿色核心点的低密度区域就被推开了;而绿色核心点和红色核心点的距离则依旧是它们的欧氏距离。
要理解HDBSCAN,首先要搞清楚层次聚类到底是什么。层次聚类有自上而下的方式和自下而上的方式。在这里我们只介绍自下而上的方式,也就是HDBSCAN算法中用到的方式。
其实就是一个不断归一化最后归成一类的过程。实际上层次不同的层次聚类算法考虑的主要是相似度的衡量方式和终止聚类的条件的不同。相似度的衡量方式决定了哪些样本将被聚到一起,而中止聚类的条件决定了选择哪一层级的类别作为最终的聚类输出。
而HDBSCAN是以可达距离作为领接边权重,对所有节点构建最小生成树,之后进行层次聚类。
我们将HDBSCAN的样本点进行层次聚类,构造成上面的生成树图之后,HDBSCAN会进行一个压缩树的过程。它的原理是,对于我们生成的最小生成树,从上往下遍历,在一个簇被划分为两个子簇的过程中,如果子簇的样本点数量小于设定的最小值(也就是前面可达距离的概念中设置的MinPts,那么这个小于MinPts的子簇将会不会被保留,子簇中的样本将作为-1类被删除。
在聚类的簇完成簇压缩的过程后,此时我们得到了一个更小的最小生成树,此时,我们需要开始决定保留那些簇作为我们的类。对于DBSCAN算法来说,实际上是在某个阈值下画了一条线,来决定选取哪些类作为聚类类别。
而HDBSCAN使用了一个簇稳定性的概念。
定义s为簇稳定性,其计算方式如下:
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。