import numpy as np
def three_n(data_set):
m = data_set.shape[0] # m 样本个数(n维)
dist_mat = np.diag(np.ones(m) * np.inf) # 初始化 距离矩阵
for r in range(m):
for c in range(r + 1, m):
dist_mat[r, c] = np.linalg.norm(data_set[r] - data_set[c])
dist_mat = dist_mat + dist_mat.T # 距离矩阵 计算完成
adjacency = np.zeros((m, m)) # 初始化 有向图的邻接矩阵
nonzero_len_init = 0
r = 0
while 1:
row_min_index = np.argmin(dist_mat, axis=1) # 每一行的最小距离的索引，也就是每个数据的第k最近邻居
for i in range(m): # 行和为每一个顶点的出度，代表着距离每一个顶点最近的（1的个数）个
adjacency[i, row_min_index[i]] = 1 # 列和为每一个顶点的入度，代表着邻居的个数，也是该顶点出现在其他顶点的邻居中的次数，即“密度”
dist_mat[i, row_min_index[i]] = np.inf # 更新距离矩阵
density = np.sum(adjacency, axis=0, dtype=np.int32) # 计算每个顶点的“密度”
nonzero_len = len(np.nonzero(density)[0]) # 统计“密度”不为0的顶点个数
r += 1
if nonzero_len == m or nonzero_len == nonzero_len_init:
nn = {}
p = 0
for i in range(m):
nn[i + 1] = np.nonzero(adjacency.T)[1].tolist()[p:p + density[i]]
nn[i + 1] = [x + 1 for x in nn[i + 1]]
p = p + density[i]
return density.tolist(), nn, r
nonzero_len_init = nonzero_len
s = np.mat('1,2,3;2,3,5;4,6,7;1,2,1;4,4,3;2,6,9;1,2,5')
d = three_n(s)
print(d)
运行结果
函数返回结果：
第一个元素：每一个数据点的邻居数（被其他数据点的邻域覆盖的次数，即“密度”）
第二个元素：每一个数据点的邻域集（每一列）
第三个元素：supk
