DBSCAN聚类算法详解

生信修炼手册

发布于 2021-03-24 09:14:41

1.2K00

代码可运行

文章被收录于专栏：生信修炼手册生信修炼手册

运行总次数：0

代码可运行

DBSCAN全称如下

Density-Based Spatial Clustering of Applications with Noise

是一种基于密度的聚类算法，所谓密度，就是说样本的紧密程度对应其类别，属于同一个cluster的样本是紧密相连的。为了定量描述紧密相连，首先引入以下3个因素

1. distance funcition, 距离的度量方式，通过距离来定量描述样本点之间的关系，这里的距离可以是欧式距离之类的计算公式

2. Epsilon, 距离的阈值，用于定义一个邻域，通过统计邻域内的样本个数来定义样本类型

3. minPoints, 领域内的最小样本数，如果大于该阈值，则将样本称之为核心样本

在DSCAN算法中，将样本划分为以下3类，图示如下

1. core point, eps邻域内的样本数大于minPoints

2. border points, eps邻域内的样本数小于minPoints

3. noise points, 噪音点，不属于任何core points的邻域内

在eps邻域和minPoints的基础上，通过以下两个概念来描述样本的紧密相连

1. 密度直达

如下图所示

样本X在核心样本Y的邻域内，则称Y到X是密度直达的，注意这个关系是单向的，反向不一定成立

2. 密度可达

如下图所示

核心样本Y到核心样本P3是密度直达的，核心样本P3到核心样本P2是密度直达的，核心样本P2到样本X是密度直达的，像这种通过P3和P2的中转，在样本Y到样本X建立的关系叫做密度可达。

3. 密度相连

如下图所示

核心样本O到样本Y是密度可达的，同时核心样本O到样本X是密度可达的，这样的关系，我们可以说样本X和样本Y是密度相连的。

对于一系列密度可达的点而言，其邻域范围内的点都是密度相连的，下图所示是一个minPoints为5的领域，红色点为core ponit, 绿色箭头连接起来的则是密度可达的样本集合，在这些样本点的邻域内的点构成了一个密度相连的样本集合，这些样本就属于同一个cluster

DBSCAN的聚类过程就是根据核心点来推导出最大密度相连的样本集合，首先随机寻找一个核心样本点，按照minPoiints和eps来推导其密度相连的点，赋予一个cluser编号，然后再选择一个没有赋予类别的核心样本点，开始推导其密度相连的样本结合，一直迭代到所有的核心样本点都有对应的类别为止。

在scikit-learn中，使用DBSCAN聚类的代码如下

>>> from sklearn.cluster import DBSCAN
>>> from sklearn import metrics
>>> from sklearn.datasets import make_blobs
>>> from sklearn.preprocessing import StandardScaler
>>> 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)
>>> db = DBSCAN(eps=0.3, 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_

labels_属性记载了样本对应的cluster编号，其中编号为-1的为噪音点，上述聚类的结果可视化如下

>>> n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
>>> n_noise_ = list(labels).count(-1)
>>> import matplotlib.pyplot as plt
>>> 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)
...
[<matplotlib.lines.Line2D object at 0x11840CE8>]
[<matplotlib.lines.Line2D object at 0x11840EB0>]
[<matplotlib.lines.Line2D object at 0x11851088>]
[<matplotlib.lines.Line2D object at 0x11851238>]
[<matplotlib.lines.Line2D object at 0x118513E8>]
[<matplotlib.lines.Line2D object at 0x11851598>]
[<matplotlib.lines.Line2D object at 0x11851748>]
[<matplotlib.lines.Line2D object at 0x118518F8>]
>>> plt.title('Estimated number of clusters: %d' % n_clusters_)
Text(0.5, 1.0, 'Estimated number of clusters: 3')
>>> plt.show()