Li_阴宅

这个屌丝很懒，什么也没留下！

热门标签

多元统计分析——聚类分析——DBSCAN（基于密度的聚类）_密度聚类的聚类数量

作者：Li_阴宅 | 2024-07-11 17:14:23

踩

密度聚类的聚类数量

聚类方法	适用场景	代表算法	优点	缺陷	延伸
层次聚类	小样本数据	-	可以形成类相似度层次图谱，便于直观的确定类之间的划分。该方法可以得到较理想的分类	难以处理大量样本，计算复杂度高
基于划分的聚类	大样本数据	K-means算法	是解决聚类问题的一种经典算法，简单、快速，复杂度为O(N) 对处理大数据集，该算法保持可伸缩性和高效率当簇近似为高斯分布时，它的效果较好	在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用必须事先给出k(要生成的簇的数目)，而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸形状的簇或者大小差别很大的簇对躁声和孤立点数据敏感	可作为其他聚类方法的基础算法，如谱聚类 k值可以通过其他的算法来估计，如：BIC(Bayesian information criterion)、MDL(minimum description length)
两步法聚类	大样本数据	BIRCH算法	层次法和k-means法的结合，具有运算速度快、不需要大量递归运算、节省存储空间的优点	-
基于密度的聚类	大样本数据	DBSCAN算法	基于密度定义，相对抗噪音，能处理任意形状和大小的簇（弥补“基于划分的聚类”的不足，尤其是对圆环形等异形簇分布的数据集）。无需指定聚类数量，对数据的先验要求不高。	当簇的密度变化太大时，会有麻烦；对于高维问题，密度定义是个比较麻烦的问题
基于密度的聚类	大样本数据	密度最大值算法	-	-

一、密度聚类方法

密度聚类方法的指导思想是，只要样本点的密度大于某阈值，则将该样本添加到最近的簇中。

这类算法能克服基于距离的算法只能发现“类圆形”(凸)的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。

密度聚类方法常见为以下两种：

DBSCAN
密度最大值算法

二、DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类，对噪声鲁棒。

DBSCAN的基本概念可以用1个核心思想，2个算法参数，3种点的类别，4种点的关系来总结。

1、1个核心思想：基于密度。

直观效果上看，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。如下：

那么如何量化“密集”？我们通过以下两个参数来定义。

2、2个算法参数：邻域半径R和最少点数目minpoints。

这两个算法参数实际可以刻画什么叫密集——当邻域半径R内的点的个数大于最少点数目minpoints时，就是密集。

3、3种点的类别：核心点，边界点和噪声点。

核心点(core point) :在邻域半径R内样本点的数量大于等于minpoints数目的点，则该点为核心点。这些点都是在簇内的。
边界点(border point):在邻域半径R内样本点的数量小于MinPts（不是核心点），但是在某个核心点的领域内的点。
噪音点(noise point):任何不是核心点或边界点的点。

为了更加直观的理解：我们以下图中的A、B、C点为例进行说明，我们事先设定邻域半径R=1，minpoints=5：

首先我们需要知道的是：数据集中特定点的密度通过该点邻域半径R之内的点计数(包括本身)来估计，密度依赖于半径。如下图：A点的密度为7。

A点：邻域半径R=1内的样本点数量为6，大于minpoints，则该点为核心点。
B点：邻域半径R=1内的样本点数量为4，小于minpoints，但是其在A点（核心点）的邻域内，则该点为边界点。
C点：即不属于核心点（邻域半径R=1内的样本点数量为3，小于minpoints），也不属于边界点（不在核心点A的领域内）的点，则该点为噪声点。

4、4种点的关系：密度直达，密度可达，密度相连，非密度相连。

密度直达：如果P为核心点，Q在P的R邻域内，那么称P到Q密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果P到Q密度直达，那么Q到P不一定密度直达（Q不一定是核心点）。
密度可达：如果存在核心点 $P_{2}$ ， $P_{3}$ ，……， $P_{n}$ ，且 $P_{1}$ 到 $P_{2}$ 密度直达， $P_{2}$ 到 $P_{3}$ 密度直达，……， $P_{n-1}$ 到 $P_{n}$ 密度直达， $P_{n}$ 到Q密度直达，则 $P_{1}$ 到Q密度可达（基于R(半径)和m(minpoints)）。密度可达也不具有对称性（Q不一定是核心点）。
密度相连：如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连（基于R(半径)和m(minpoints)）。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。
非密度相连：如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

例：如图所示，R用一个相应的半径表示，设minpoints=3，请分析Q,M,P,S,O,T这几个样本点之间的关系。

解答：

根据以上概念知道，上图中Q,M,P,S,O,T的R邻域半径内含有的样本数（包含其自身）为：Q:1,M:5,P:4,S:2,O:4,T:3，由于有标记的各点M、P、O和T的R邻域半径均包含3个以上的点，因此它们都是核心点；
M是从P“密度直达”；而Q则是从M“密度直达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。
类似地，S和T从O是“密度可达”的；O、T和S均是“密度相连”的，“密度相连”的点属于同一个聚类簇。

三、DBSCAN算法步骤

1、寻找核心点形成临时聚类簇

扫描全部样本点，如果某个样本点R半径范围内点数目>=MinPoints，则将其纳入核心点列表，并将其密度直达的点形成对应的临时聚类簇。

2、合并临时聚类簇得到聚类簇

对于每一个临时聚类簇，检查其中的点是否为核心点，如果是，将该点对应的临时聚类簇和当前临时聚类簇合并，得到新的临时聚类簇。

重复此操作，直到当前临时聚类簇中的每一个点要么不在核心点列表，要么其密度直达的点都已经在该临时聚类簇，该临时聚类簇升级成为聚类簇。

继续对剩余的临时聚类簇进行相同的合并操作，直到全部临时聚类簇被处理。

四、DBSCAN特点

1、优点：

基于密度定义，相对抗噪音。
无需知道聚类簇的数量。
能处理任意形状和大小的簇。

2、缺点

当簇的密度变化太大时，聚类效果较差。
对于高维问题，密度定义（基于R半径和minpoints最少点数目）是个比较麻烦的问题，通常适合于对较低维度数据进行聚类分析。
当数据量增大时，要求较大的内存支持，I/O消耗也比较大。

3、不同数据下密度最大值聚类的效果

五、案例

1、生成样本集——圆环形


import numpy as np
import pandas as pd
from sklearn import datasets
 
X,_ = datasets.make_moons(500,noise = 0.1,random_state=1)
df = pd.DataFrame(X,columns = ['feature1','feature2'])
df

输出：

生成的样本点分布如下：

df.plot.scatter('feature1','feature2', s = 60,alpha = 0.6, title = 'dataset by make_moon')

输出：

2、dbscan聚类

调用dbscan接口进行聚类，两个参数：eps为邻域半径，min_samples为最少点数目；返回值：core_samples为样本点的下标，cluster_ids 为聚类结果便签。


from sklearn.cluster import dbscan
 
core_samples,cluster_ids = dbscan(X, eps = 0.2, min_samples=20) # eps为邻域半径，min_samples为最少点数目
cluster_ids  # 聚类结果标签，cluster_ids中-1表示对应的点为噪声点

输出：


array([ 0,  0,  1,  1,  0,  0,  0,  1, -1,  1,  0,  1,  1,  1,  0,  1,  0,
        0,  1,  1,  0,  0,  0,  0,  1,  0,  1,  0,  1,  1,  1,  0,  1,  0,
        0,  1, -1,  1,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  1,  1,
        1,  1,  0,  0,  1,  0,  0,  1,  0,  0,  1,  0,  0,  0,  0,  0,  0,
        0,  1,  0,  0,  1,  1,  1,  0,  0,  0, -1,  1,  0,  1,  1,  0,  1,
        1,  0,  0,  0,  0,  0,  0,  0,  1,  0,  1,  1,  1, -1,  1,  1,  0,
        0,  1,  0,  1,  0, -1,  1,  1,  0,  0,  0,  0,  0,  1,  0,  1,  1,
        0,  0,  1,  1,  0,  1,  0,  0,  0,  1,  1, -1,  1,  0,  1,  0,  0,
        0,  0,  0,  1,  1,  1,  1,  0,  1,  0,  1,  1,  1,  1,  1,  1,  0,
        1,  0,  0, -1,  1,  1,  0,  1,  0,  0,  0,  0, -1,  1,  1,  0,  0,
        1,  1,  0,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  1,  0, -1,  1,
        1,  1,  0,  1,  1,  0,  0,  1,  0,  1,  0,  1,  0,  0,  0,  0,  1,
        1,  0,  1,  1,  1,  0,  1,  1,  0, -1,  1,  1,  1,  1, -1,  1,  1,
        1,  0,  1,  0,  1,  0,  0,  0,  0,  0,  1,  0,  0,  0,  1,  1,  0,
        0,  1,  1, -1,  1,  1,  0,  0,  1,  0,  0,  0,  0,  0,  1,  1,  0,
        0,  0,  0,  0,  1,  0,  0,  1,  0,  1,  1,  0,  1,  1,  0,  0,  1,
       -1,  1,  0,  1,  1,  0,  1,  1,  1,  1,  0,  1, -1,  1,  1,  0,  0,
        1,  1,  0,  0,  1,  0,  0,  0,  1,  0,  0,  1,  1,  1,  0,  0,  1,
        0,  1,  0,  1,  1,  0,  0,  1,  1,  0,  1,  1,  1,  1,  1,  1,  0,
        1,  1,  0,  0,  0,  1,  1,  1,  0,  0,  0,  0,  1,  1,  1,  0,  1,
        0,  1,  0,  1,  1,  0,  1,  1,  0,  1,  0,  1,  1,  1,  0,  0,  0,
        1,  1,  1,  1,  1,  1,  1,  0,  0,  1,  0,  1,  1,  1,  1,  0,  0,
        0,  1,  0,  1,  0,  0,  1,  1,  1,  0,  0,  1,  0, -1,  1,  0,  0,
        0,  0,  0,  0,  0,  1,  1,  0,  0,  1,  1,  0,  1,  0,  1,  1,  1,
        0,  0,  0,  1,  1,  1,  0,  1,  0,  0,  0,  1,  1, -1,  0,  1,  1,
        0,  0,  1,  0,  1,  1,  1,  1,  0,  0,  1,  0,  0,  1,  1,  1,  0,
        1,  0,  1,  0,  0,  0,  1,  1,  0,  1,  0,  1,  0,  1,  0,  0,  1,
        0,  1,  0,  0,  1,  0,  1,  1,  0,  1,  1,  1,  1,  0,  0,  1,  0,
        0,  0,  0,  0, -1,  0,  1,  0,  0,  1,  1,  0,  1,  1,  0,  0,  1,
        1,  0,  0,  1,  0,  1,  1], dtype=int32)

注意：cluster_ids中-1表示对应的点为噪声点。

将聚类标签和原始样本拼在一起。


df['cluster_id'] = cluster_ids
df

输出：

聚类结果的可视化：


df.plot.scatter('feature1','feature2', s = 60,
                c = list(df['cluster_id']),cmap = 'rainbow',colorbar = False,
                alpha = 0.6,title = 'DBSCAN cluster result')

输出：

3、K-means聚类

我们可以运用K-means算法对本数据进行聚类，来比较两者的不同：


from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.metrics import silhouette_score  #总的聚类效果轮廓系数
from sklearn.metrics import silhouette_samples   #单个样本的轮廓系数
 
fig=plt.figure(figsize=(10,3.5)) #表示绘制图形的画板尺寸为6*4.5；
 
#WGSS
ax=fig.add_subplot(1,2,1)
wgss=[]   
for i in range(6):
    cluster = KMeans(n_clusters=i+1, random_state=0).fit(X)
    wgss.append(cluster.inertia_)  #inertia_：每个点到其簇的质心的距离之和。即WGSS
#绘制WGSS的碎石图
plt.plot([i+1 for i in range(6)],wgss,marker='o')
plt.title('WGSS')
 
#轮廓系数
ax=fig.add_subplot(1,2,2)
silhouette_scores=[]   
for i in range(1,6):
    cluster = KMeans(n_clusters=i+1, random_state=0).fit(X)
    # 访问labels_属性，获得聚类结果
    y_pred = cluster.labels_
    # 计算平均轮廓系数
    silhouette_avg = silhouette_score(X, y_pred)
    silhouette_scores.append(silhouette_avg)
#绘制silhouette_scores的碎石图
plt.plot([i+1 for i in range(1,6)],silhouette_scores,marker='d')
plt.title('silhouette_scores')

输出：

有WGSS和silhouette_scores，我们按照暂时按两类进行聚类，输出一下聚类效果：


cluster = KMeans(n_clusters=2, random_state=0).fit(X)
df['label']=cluster.labels_
df.plot.scatter('feature1','feature2', s = 60,
                c = list(df['label']),cmap = 'rainbow',colorbar = False,
                alpha = 0.6,title = 'KMeans cluster result')

输出：

从以上图我们可以看出，K-means对于圆环分布的数据的聚类效果不是很好。故对于圆环数据分布的样本集，我们首选DBSCAN算法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/810983