基于SNN密度的聚类及python代码实现

  在某些情况下,依赖于相似度和密度的标准方法的聚类技术不能产生理想的聚类效果。

存在的问题

1.传统的相似度在高维数据上的问题

  传统的欧几里得密度在高维空间变得没有意义。特别在文本处理之中,以分词作为特征,数据的维度将会非常得高,文本与文本之间的相似度低并不罕见。然而许多文档都有着不同类的最近邻,虽然近邻之间相似度虽然高,然而却不是同一类文档。由此可以看出,传统的相似度成为了不可靠的指导。

2.密度不同的问题

  传统的基于密度的聚类问题,虽然能够有效的发现不同形状的簇,然而由于在计算密度的时候是通过计算之间的欧式距离确定密度的,若存在密度差别较大的簇将无法很好地识别。
  如下图,显示了一对具有不同密度点的二维簇。右边的簇尽管不太稠密,但形成了同样合法的簇。
  不同密度的二维簇图
  若使用传统的dbscan聚类算法(sklearn开源包),将获得以下聚类效果,其中黑色点表示噪声。
  dbscan

SNN相似度

  为了解决上诉问题,提出了共享最近邻(Shared Nearest Neighbor, SNN)相似度。如字面意思,通过计算2个点之间共享的近邻个数,确定两点之间的相似度。
算法流程

1
2
3
4
5
找出所有点的k-最近邻
if 两个点x和y不是在对方的k-最近邻中 then
similarity(x, y) = 0
else
similarity(x, y) = 共享的近邻个数

  SNN相似度只依赖于两个对象共享的最近邻的个数,而不是这些近邻之间相距多远。这样一来相似度关于点的密度自动进行缩放

SNN密度

  由于SNN相似性度量反映了数据空间中点的局部结构,因此它对密度的变化和空间的维度相对不太敏感,所以可以用来做新的密度度量。
定义如下
核心点: 在给定邻域(Eps)内的点数超过某个阈值(MinPts)
边界点: 不属于核心点,但在某个核心点的邻域内。
噪声点: 既非核心点,也非边界点的噪声。
  可以理解为,SNN密度度量一个点被类似的点包围的程度。

  

基于SNN密度的聚类

  将上面定义的SNN密度与dbScan算法结合起来,就可以得出一种新的聚类算法
算法流程

1
2
计算SNN相似度图
以用户指定的参数Eps和MinPts,使用dbScan算法

  以上面的数据集为例,使用该聚类算法得出以下结果。
SNN

具体python代码实现,使用了开源包sklearn的kd-tree以及dbScan算法。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import numpy as np
from sklearn.neighbors import NearestNeighbors
from itertools import combinations
import time


def snn_sim_matrix(X, k=5):
"""
利用sklearn包中的KDTree,计算节点的共享最近邻相似度(SNN)矩阵
:param X: array-like, shape = [samples_size, features_size]
:param k: positive integer(default = 5), 计算snn相似度的阈值k
:return: snn距离矩阵
"""
try:
X = np.array(X)
except:
raise ValueError("输入的数据集必须为矩阵")
samples_size, features_size = X.shape # 数据集样本的个数和特征的维数
nbrs = NearestNeighbors(n_neighbors=k, algorithm='kd_tree').fit(X)
knn_matrix = nbrs.kneighbors(X, return_distance=False) # 记录每个样本的k个最近邻对应的索引
sim_matrix = 0.5 + np.zeros((samples_size, samples_size)) # snn相似度矩阵
for i in range(samples_size):
t = np.where(knn_matrix == i)[0]
c = list(combinations(t, 2))
for j in c:
if j[0] not in knn_matrix[j[1]]:
continue
sim_matrix[j[0]][j[1]] += 1
sim_matrix = 1 / sim_matrix # 将相似度矩阵转化为距离矩阵
sim_matrix = np.triu(sim_matrix)
sim_matrix += sim_matrix.T - np.diag(sim_matrix.diagonal())
return sim_matrix

if __name__ == '__main__':
from sklearn.cluster import DBSCAN
from sklearn.datasets.samples_generator import make_blobs
import matplotlib.pyplot as plt

# 构建数据集
centers = [37, 4]
centers_2 = [-37, 4]
X, labels_true = make_blobs(n_samples=100, centers=centers, cluster_std=20)
X_2, l_2 = make_blobs(n_samples=50, cluster_std=8, centers=centers_2)
X = np.concatenate((X, X_2))

# 基于snn相似度的聚类
t1 = time.time()
sim_matrix = snn_sim_matrix(X, k=8)
t2 = time.time()
print "the time of creating sim matrix is %.5fs" % (t2 - t1)
t1 = time.time()
db = DBSCAN(eps=0.5, min_samples=5, metric='precomputed').fit(sim_matrix)
t2 = time.time()
print "the time of clustering is %.5fs" % (t2 - t1)
# 构图
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
for k, col in zip(unique_labels, colors):
if k == -1:
# Black used for noise.
col = 'k'
class_member_mask = (labels == k)
xy = X[class_member_mask & core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=10)
xy = X[class_member_mask & ~core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=6)
plt.title('SNN')
plt.show()

Have a nice day!