密度聚类（Density-based Clustering）假设聚类结构能够通过样本分布的紧密程度来确定。DBSCAN是常用的密度聚类算法，它通过一组邻域参数（??，MinPtsMinPts）来描述样本分布的紧密程度。给定数据集DD={x? 1，x? 2，x? 3，...，x? Nx→1，x→2，x→3，...，x→N}，数据集属性定义如下。

• ??-邻域：N?(x? i)N?(x→i)={x? j∈D|distance(x? i,x? j)x→j∈D|distance(x→i,x→j)≤?≤?}，N?(x? i)N?(x→i)包含了样本集DD中与x? ix→i距离不大于??的所有样本。

• 核心对象core object：若|N?(x? i)N?(x→i)|≥MinPts≥MinPts，则称x? ix→i是一个核心对象。即：若x? ix→i的??-邻域中至少包含MinPtsMinPts个样本，则称x? ix→i是一个核心对象。

• 密度直达directly density-reachable：若x? ix→i是一个核心对象，且x? j∈x→j∈N?(x? i)N?(x→i)，则称x? jx→j由x? ix→i密度直达，记作x? ix→i–>x? jx→j。

• 密度可达density-reachable：对于x? ix→i和x? jx→j，若存在样本序列(p? 0，p? 1，p? 2，...，p? m，p? m+1p→0，p→1，p→2，...，p→m，p→m+1），其中p? 0p→0=x? ix→i，p? m+1p→m+1=x? jx→j，p? s∈D,s=1,2,...,mp→s∈D,s=1,2,...,m。如果p? s+1p→s+1由p? s,s=1,2,...,mp→s,s=1,2,...,m密度直达，则称x? jx→j由x? ix→i密度可达，记作x? ix→i~>x? jx→j。

• 密度相连density-connected：对于x? ix→i和x? jx→j，若存在x? kx→k，使得x? ix→i和x? jx→j均由x? kx→k密度可达，则称x? jx→j由x? ix→i密度相连，记作x? ix→i~x? jx→j。

??DBSCAN算法的定义：给定邻域参数（??，MinPtsMinPts），一个簇C?DC?D是满足下列性质的非空样本子集：

• 接性connectivity：若x? i∈C,x? j∈Cx→i∈C,x→j∈C，则x? ix→i~x? jx→j
• 大性maximality：若x? i∈Cx→i∈C，且→xi→xi~>x? jx→j，则x? j∈Cx→j∈C 
  即一个簇是由密度可达关系导出的最大的密度相连样本集合。

??DBSCAN算法的思想：若x? x→为核心对象，则x? x→密度可达的所有样本组成的集合X={x? ?∈D|x? x→?∈D|x→~>x? ?x→?},可以证明XX就是满足连接性与最大性的簇。于是DBSCAN算法首选任选数据集中的一个核心对象作为种子seedseed，再由此出发确定相应的聚类簇。

下面给出DBSCAN算法：

• 输入

  • 数据集DD={x? 1，x? 2，x? 3，...，x? Nx→1，x→2，x→3，...，x→N}
  • 邻域参数（??，MinPtsMinPts）

• 输出：簇划分CC={C1,C2,...,CkC1,C2,...,Ck}

• 算法步骤如下： 
  
  • 初始化核心对象集合为空集：Ω=??
  • 寻找核心对象：遍历所有的样本点x? i,i=1,2,...,Nx→i,i=1,2,...,N，计算N?(x? i)N?(x→i)，如果|N?(x? i)N?(x→i)|≥MinPts≥MinPts，则Ω=Ω??{x? ix→i}
  • 迭代：以任一未访问过的核心对象为出发点，找出有其密度可达的样本生成的聚类簇，直到所有的核心对象都被访问为止

Python 实战

??DBSCANDBSCAN是sciki?kearnsciki?kearn提供的密度聚类算法模型，其原型为：

class sklearn.cluster.DBSCAN(eps=0.5,min_samples=5,metric=‘euclidean‘,algorithm=‘auto‘,leaf_size=30,p=None,random_state=None)

• 1

参数

• epseps：??参数，用于确定邻域大小。
• min_samplesmin_samples：MinPtsMinPts参数，用于判断核心对象。
• metricmetric：一个字符串或可调用对象，用于计算距离。如果是字符串，则必须是在metrics.pairwise.calculate_distance中指定。
• algorithmalgorithm：一个字符串，用于计算两点间距离并找出最近邻的点，可以为如下： 
  
  • ‘autoauto’：由算法自动取舍合适的算法。
  • ‘ball_treeball_tree’：用ball树来搜索。
  • ‘kd_treekd_tree’：用kd树搜索。
  • ‘brutebrute’：暴力搜索。
• leaf_sizeleaf_size：一个整数，用于指定当algorithm=ball_tree或kd_tree时，树的叶节点大小。该参数会影响构建树，搜索最近邻的速度，同时影响树的内存。
• random_staterandom_state：被废弃的接口，将在scikit-learn v 0.18中移除。

属性

• core_sample_indices_core_sample_indices_：核心样本在原始训练集中的位置。
• components_components_：核心样本的一份副本。
• labels_labels_：每个样本所属的簇标记。对于噪声样本，其簇标记为-1副本。

方法

• fit(X[,y,sample_weight])fit(X[,y,sample_weight])：训练模型。
• fit_predict(X[,y,sample_weight])fit_predict(X[,y,sample_weight])：训练模型并预测每个样本所属的簇标记。

#导包 from sklearn import cluster from sklearn.metrics import adjusted_rand_score import numpy as np import matplotlib.pyplot as plt from sklearn.datasets.samples_generator import make_blobs from sklearn import mixture from sklearn.svm.libsvm import predict

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

#产生数据 def create_data(centers,num=100,std=0.7): X,labels_true = make_blobs(n_samples=num,centers=centers, cluster_std=std) return X,labels_true

• 1
• 2
• 3
• 4

""" 数据作图 """ def plot_data(*data): X,labels_true=data labels=np.unique(labels_true) fig=plt.figure() ax=fig.add_subplot(1,1,1) colors=‘rgbycm‘ for i,label in enumerate(labels): position=labels_true==label ax.scatter(X[position,0],X[position,1],label="cluster %d"%label), color=colors[i%len(colors)] ax.legend(loc="best",framealpha=0.5) ax.set_xlabel("X[0]") ax.set_ylabel("Y[1]") ax.set_title("data") plt.show()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

#测试函数 def test_DBSCAN(*data): X,labels_true = data clst = cluster.DBSCAN(); predict_labels = clst.fit_predict(X) print("ARI:%s"%adjusted_rand_score(labels_true,predict_labels)) print("Core sample num:%d"%len(clst.core_sample_indices_))

• 1
• 2
• 3
• 4
• 5
• 6
• 7

#结果 ARI:0.330307120902 Core sample num:991

• 1
• 2
• 3

??其中ARIARI指标为0.330307120902，该值越大越好，DBSCAN根据密度，将原始数据集划分为991个簇。

下面考察??参数的影响：

def test_DBSCAN_epsilon(*data): X,labels_true = data epsilons = np.logspace(-1,1.5) ARIs=[] Core_nums = [] for epsilon in epsilons: clst = cluster.DBSCAN(eps=epsilon) predicted_labels = clst.fit_predict(X) ARIs.append(adjusted_rand_score(labels_true,predicted_labels)) Core_nums.append(len(clst.core_sample_indices_)) fig = plt.figure(figsize=(10,5)) ax = fig.add_subplot(1,2,1) ax.plot(epsilons,ARIs,marker = ‘+‘) ax.set_xscale(‘log‘) ax.set_xlabel(r"$\epsilon$") ax.set_ylim(0,1) ax.set_ylabel(‘ARI‘) ax = fig.add_subplot(1,2,2) ax.plot(epsilons,Core_nums,marker=‘o‘) ax.set_xscale(‘log‘) ax.set_xlabel(r"$\epsilon$") ax.set_ylabel(‘Core_num‘) fig.suptitle("DBSCAN") plt.show()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27

centers = [[1,1],[1,2],[2,2],[10,20]] X,labels_true = create_data(centers,1000,0.5) test_DBSCAN_epsilon(X,labels_true)

• 1
• 2
• 3

??参数的影响结果如上图所示：

??可以看到ARIARI指数随着??的增长，先上升后保持平稳，最后悬崖式下降。悬崖式下降是因为我们产生的训练样本的间距比较小，最远的两个样本之间的距离不超过30，当??过大时，所有的点都在一个邻域中。 
??样本核心数量随着??的增长而上升，这是因为随着??的增长，样本点的邻域在扩展，则样本点邻域中的样本会增多，这就产生了更多满足条件的核心样本点。但是样本集中的样本数量有限，因此核心样本点的数量增长到一定数目后会趋于稳定。

下面接着考察MinPtsMinPts参数的影响：

def test_DBSCAN_min_samples(*data): X,labels_true=data min_samples=range(1,100) ARIs=[] Core_nums=[] for num in min_samples: clst=cluster.DBSCAN(min_samples=num) predicted_labels=clst.fit_predict(X) ARIs.append(adjusted_rand_score(labels_true, predicted_labels)) Core_nums.append(len(clst.core_sample_indices_)) fig=plt.figure(figsize=(10,5)) ax=fig.add_subplot(1,2,1) ax.plot(min_samples,ARIs,marker=‘+‘) ax.set_xlabel("min_samples") ax.set_ylim(0,1) ax.set_ylabel(‘ARI‘) ax=fig.add_subplot(1,2,2) ax.plot(min_samples,Core_nums,marker=‘o‘) ax.set_xlabel("min_samples") ax.set_ylabel(‘Core_nums‘) fig.suptitle("DBSCAN") plt.show()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

centers = [[1,1],[1,2],[2,2],[10,20]] X,labels_true = create_data(centers,1000,0.5) test_DBSCAN_min_samples(X,labels_true)

• 1
• 2
• 3

MinPtsMinPts参数的影响结果如下:

??可以看出ARIARI指数随着MinPtsMinPts的增长，平稳地下降。而核心样本数量随着MinPtsMinPts的增长基本呈线性下降，这是因为随着MinPtsMinPts的增长，样本点的邻域中必须包含更多的样本才能使它成为一个核心点。因此产生的样本点数量越来越少。

有关ARIARI，请参考：