聚类python代码_基于SNN密度的聚类及python代码实现
在某些情况下，依赖于相似度和密度的标准⽅法的聚类技术不能产⽣理想的聚类效果。
存在的问题
1.传统的相似度在⾼维数据上的问题
传统的欧⼏⾥得密度在⾼维空间变得没有意义。特别在⽂本处理之中，以分词作为特征，数据的维度将会⾮常得⾼，⽂本与⽂本之间的相似度低并不罕见。然⽽许多⽂档都有着不同类的最近邻，虽然近邻之间相似度虽然⾼，然⽽却不是同⼀类⽂档。由此可以看出，传统的相似度成为了不可靠的指导。
2.密度不同的问题
传统的基于密度的聚类问题，虽然能够有效的发现不同形状的簇，然⽽由于在计算密度的时候是通过计算之间的欧式距离确定密度的，若存在密度差别较⼤的簇将⽆法很好地识别。
如下图，显⽰了⼀对具有不同密度点的⼆维簇。右边的簇尽管不太稠密，但形成了同样合法的簇。
若使⽤传统的dbscan聚类算法(sklearn开源包)，将获得以下聚类效果，其中⿊⾊点表⽰噪声。python新手代码及作用
SNN相似度
为了解决上诉问题，提出了 共享最近邻 (Shared Nearest Neighbor, SNN)相似度。如字⾯意思，通过计算2个点之间共享的近邻个数，确定两点之间的相似度。
算法流程
出所有点的k-最近邻if 两个点x和y不是在对⽅的k-最近邻中 then similarity(x, y) = 0else similarity(x, y) = 共享的近邻个数
SNN相似度只依赖于两个对象共享的最近邻的个数，⽽不是这些近邻之间相距多远。这样⼀来相似度关于点的密度⾃动进⾏缩放
SNN密度
由于SNN相似性度量反映了数据空间中点的局部结构，因此它对密度的变化和空间的维度相对不太敏感，所以可以⽤来做新的密度度量。
定义如下
核⼼点： 在给定邻域(Eps)内的点数超过某个阈值(MinPts)
边界点： 不属于核⼼点，但在某个核⼼点的邻域内。
噪声点： 既⾮核⼼点，也⾮边界点的噪声。
可以理解为，SNN密度度量⼀个点被类似的点包围的程度。
基于SNN密度的聚类
将上⾯定义的SNN密度与dbScan算法结合起来，就可以得出⼀种新的聚类算法
算法流程
计算SNN相似度图以⽤户指定的参数Eps和MinPts，使⽤dbScan算法
以上⾯的数据集为例，使⽤该聚类算法得出以下结果。
具体python代码实现，使⽤了开源包sklearn的kd-tree以及dbScan算法。
import numpy as ighbors import NearestNeighborsfrom itertools import combinationsimport timedef
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_matrixif __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 =
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__sample_indices_] = True labels = db.labels_ n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0) unique_labels = set(labels) colors =
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col, markeredgecolor='k', markersize=6) plt.title('SNN') plt.show()

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。