DBSCAN聚类︱scikit-learn中一种基于密度的聚类方式

一、DBSCAN聚类概述

基于密度的方法的特点是不依赖于距离,而是依赖于密度,从而克服基于距离的算法只能发现“球形”聚簇的缺点。 DBSCAN的核心思想是从某个核心点出发,不断向密度可达的区域扩张,从而得到一个包含核心点和边界点的最大化区域,区域中任意两点密度相连。

1、伪代码

算法: DBSCAN 输入: E — 半径 MinPts — 给定点在 E 领域内成为核心对象的最小领域点数 D — 集合 输出:目标类簇集合 方法: repeat 1) 判断输入点是否为核心对象 2) 找出核心对象的 E 领域中的所有直接密度可达点 util 所有输入点都判断完毕 repeat 针对所有核心对象的 E 领域所有直接密度可达点找到最大密度相连对象集合, 中间涉及到一些密度可达对象的合并。 Util 所有核心对象的 E 领域都遍历完毕

密度:空间中任意一点的密度是以该点为圆心,以EPS为半径的圆区域内包含的点数目
边界点:空间中某一点的密度,如果小于某一点给定的阈值minpts,则称为边界点
噪声点:不属于核心点,也不属于边界点的点,也就是密度为1的点

2、优点:

  • 这类算法能克服基于距离的算法只能发现“类圆形”(凸)的聚类的缺点
  • 可发现任意形状的聚类,且对噪声数据不敏感。
  • 不需要指定类的数目cluster
  • 算法中只有两个参数,扫描半径 (eps)和最小包含点数(min_samples)

3、缺点:

  • 1、计算复杂度,不进行任何优化时,算法的时间复杂度是O(N^{2}),通常可利用R-tree,k-d tree, ball tree索引来加速计算,将算法的时间复杂度降为O(Nlog(N))。
  • 2、受eps影响较大。在类中的数据分布密度不均匀时,eps较小时,密度小的cluster会被划分成多个性质相似的cluster;eps较大时,会使得距离较近且密度较大的cluster被合并成一个cluster。在高维数据时,因为维数灾难问题,eps的选取比较困难。
  • 3、依赖距离公式的选取,由于维度灾害,距离的度量标准不重要
  • 4、不适合数据集集中密度差异很大的,因为eps和metric选取很困难

4、与其他聚类算法比较

来看两张图:

DBSCAN可以较快、较有效的聚类出来

eps的取值对聚类效果的影响很大。 .

二、sklearn中的DBSCAN聚类算法

1、主要函数介绍:

DBSCAN(eps=0.5, min_samples=5, metric='euclidean', algorithm='auto', leaf_size=30, p=None, n_jobs=1)

最重要的两个参数:

eps:两个样本之间的最大距离,即扫描半径 min_samples :作为核心点的话邻域(即以其为圆心,eps为半径的圆,含圆上的点)中的最小样本数(包括点本身)。 其他参数: metric :度量方式,默认为欧式距离,还有metric=’precomputed’(稀疏半径邻域图) algorithm:近邻算法求解方式,有四种:‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’ leaf_size:叶的大小,在使用BallTree or cKDTree近邻算法时候会需要这个参数 n_jobs :使用CPU格式,-1代表全开

其他主要属性:

core_sample_indices_:核心样本指数。(此参数在代码中有详细的解释) labels_:数据集中每个点的集合标签给,噪声点标签为-1。 components_ :核心样本的副本

运行式子:

model = sklearn.cluster.DBSCAN(eps_领域大小圆半径,min_samples_领域内,点的个数的阈值) model.fit(data) 训练模型 model.fit_predict(data) 模型的预测方法 .

2、DBSCAN自编代码

来源:【挖掘模型】:Python-DBSCAN算法

import numpy
import pandas
import matplotlib.pyplot as plt

#导入数据
data = pandas.read_csv("F:\\python 数据挖掘分析实战\\Data\\data (7).csv")

plt.scatter(
    data['x'], 
    data['y']
)

eps = 0.2;
MinPts = 5;

from sklearn.metrics.pairwise import euclidean_distances

ptses = []
dist = euclidean_distances(data)
for row in dist:
    #密度,空间中任意一点的密度是以该点为圆心、以 Eps 为半径的圆区域内包含的点数
    density = numpy.sum(row<eps)
    pts = 0;
    if density>MinPts:
        #核心点(Core Points)
        #空间中某一点的密度,如果大于某一给定阈值MinPts,则称该为核心点
        pts = 1
    elif density>1 :
        #边界点(Border Points)
        #空间中某一点的密度,如果小于某一给定阈值MinPts,则称该为边界点
        pts = 2
    else:
        #噪声点(Noise Points)
        #数据集中不属于核心点,也不属于边界点的点,也就是密度值为1的点
        pts = 0
    ptses.append(pts)

#把噪声点过滤掉,因为噪声点无法聚类,它们独自一类
corePoints = data[pandas.Series(ptses)!=0]

coreDist = euclidean_distances(corePoints)

#首先,把每个点的领域都作为一类
#邻域(Neighborhood)
#空间中任意一点的邻域是以该点为圆心、以 Eps 为半径的圆区域内包含的点集合
cluster = dict();
i = 0;
for row in coreDist: 
    cluster[i] = numpy.where(row<eps)[0]
    i = i + 1

#然后,将有交集的领域,都合并为新的领域
for i in range(len(cluster)):
    for j in range(len(cluster)):
        if len(set(cluster[j]) & set(cluster[i]))>0 and i!=j:
            cluster[i] = list(set(cluster[i]) | set(cluster[j]))
            cluster[j] = list();

#最后,找出独立(也就是没有交集)的领域,就是我们最后的聚类的结果了
result = dict();
j = 0
for i in range(len(cluster)):
  if len(cluster[i])>0:
    result[j] = cluster[i]
    j = j + 1

#找出每个点所在领域的序号,作为他们最后聚类的结果标记
for i in range(len(result)):
    for j in result[i]:
        data.at[j, 'type'] = i

plt.scatter(
    data['x'], 
    data['y'],
    c=data['type']
)

3、实战案例:

# DBSCAN clustering algorithm

print(__doc__)

import numpy as np

from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler

# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
                            random_state=0)

X = StandardScaler().fit_transform(X)


# Compute DBSCAN
db = DBSCAN(eps=0.1, min_samples=10).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_

# Number of clusters in labels, ignoring noise if present.
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)

print('Estimated number of clusters: %d' % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
      % metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
      % metrics.adjusted_mutual_info_score(labels_true, labels))
print("Silhouette Coefficient: %0.3f"
      % metrics.silhouette_score(X, labels))


# 
import matplotlib.pyplot as plt

# Black removed and is used for noise instead.
unique_labels = set(labels)
colors = [plt.cm.Spectral(each)
          for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:
        # Black used for noise.
        col = [0, 0, 0, 1]

    class_member_mask = (labels == k)

    xy = X[class_member_mask & core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=14)

    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=6)

plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

最后的结果:

.

延伸一:DPEAK算法——密度最大值算法

本节来源:机器学习笔记(九)聚类算法及实践(K-Means,DBSCAN,DPEAK,Spectral_Clustering)聚类 - 4 - 层次聚类、密度聚类(DBSCAN算法、密度最大值聚类) 密度最大值聚类是一种简洁优美的聚类算法, 可以识别各种形状的类簇, 并且参数很容易确定。用于找聚类中心和异常值的。 用DPEAK算法找到聚类中心之后,在用DBSCAN会更好

(1)我们首先给定一个半径范围r,然后对我们所有的样本,计算它的r邻域内的样本数目记作它的局部密度记作rho (2)第二步,计算每个样本到密度比它高的点的距离的最小值记作sigma,有了这两个参数就可以进行我们下一步的筛选工作了

具体分成以下四种情况: 1 rho很小,sigma很大。这个样本周围的样本量很小,但是到比它密度大的点的距离还挺远的,这说明啥,它是个远离正常样本的异常值啊,在偏僻的小角落里搞自己的小动作啊,果断踢了它呀。 2 rho很大,sigma也很大。这个样本周围样本量很大,并且要找到比它密度还大的点要好远好远,这说明这个点是被众星环绕的啊,它就是这个簇的王,我们往往把它确定为簇中心。 3 rho很小,sigma也很小。样本周围的样本量很小,但要找到样本密度比它大的点没多远就有,说明这个点是一个处在边缘上的点,往往是一个簇的边界。 4 rho很大,sigma很小。该样本周围的样本量很大,但是密度比它还大的居然也不远,这种情况只会发生在你处在了簇中心的旁边时,很可惜,也许你是这个簇的核心成员,但你做不了这个簇的王。

好的,基于每个样本的rho和sigma,我们大概就能确定它们各自的所扮演的角色了,我们把大反派异常值从样本中剔除,然后把我们找到的rho和sigma都很大的点作为簇中心,再利用K-Means或者DBSCAN算法进行聚类就能得到相对比较好的结果。

参考来源 聚类分析(五)基于密度的聚类算法 — DBSCAN 聚类算法第三篇-密度聚类算法DBSCAN 聚类算法初探(五)DBSCAN,作者: peghoty 聚类算法第一篇-概览 sklearn.cluster.DBSCAN 【挖掘模型】:Python-DBSCAN算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

R语言处理缺失数据的高级方法

主要用到VIM和mice包 [plain] view plain install.packages(c("VIM","mice")) 1.处理缺失值的步骤 ...

3217
来自专栏机器学习原理

我的机器学习概率论篇排列 组合古典概率联合概率条件概率全概率公式贝叶斯公式独立事件随机变量离散型随机变量连续型随机变量期望和方差三个基本定理参数估计

前言: 概率论的理解有些抽象,掌握概率论的方法,用实际样本去无限接近真实,熟练掌握并且使用一些最基本的概念是前提,比如,均值,方差 排列 组合 计算各种...

3516
来自专栏生信技能树

【直播】我的基因组80:为什么有些基因的内部测序深度差异如此大

这一讲里,我们依旧根据统计的基因测序的深度进行一下讨论,来看看为什么有些基因的内部测序深度差异如此大? 在前面我们的计算中,s列表示的是基因的每一个坐标的...

3387
来自专栏SIGAI学习与实践平台

基于内容的图像检索技术综述-传统经典方法

今天我们来介绍一下图片检索技术,图片检索就是拿一张待识别图片,去从海量的图片库中找到和待识别图片最相近的图片。这种操作在以前依靠图片名搜图的时代是难以想象的,直...

752
来自专栏张耀琦的专栏

【机器学习入门系列05】分类、概率生成模型

本文通过将神奇宝贝数值化的过程介绍了分类模型、先验概率以及高斯分布的应用;最大似然估计的方法;推导后验概率等

6410
来自专栏kevindroid

mahout学习之聚类(1)——向量的引入与距离测度

1534
来自专栏AI科技评论

干货 | 三维网格物体识别的一种巧妙方法

AI 科技评论按:本文由「图普科技」编译自 Medium - 3D body recognition using VGG16 like network

731
来自专栏SIGAI学习与实践平台

理解概率密度函数

概率密度函数是概率论中的核心概念之一,用于描述连续型随机变量所服从的概率分布。在机器学习中,我们经常对样本向量x的概率分布进行建模,往往是连续型随机变量。很多同...

684
来自专栏斑斓

掌握一点儿统计学

对于数据分析师而言,统计学必定是一门绕不开的学科。我今生做数据科学家已经无望了,但就工程角度来讲,致力于大数据行业,了解一些必备的统计学知识仍有必要。Data ...

3176
来自专栏书山有路勤为径

卷积滤波器与边缘检测

高低频率 高频图像是强度变化很大的图像。并且亮度级别从一个像素到下一个像素快速变化。低频图像可以是亮度相对均匀或变化非常慢的图像。这是一个例子中最容易看到的。

992

扫码关注云+社区