# 3N算法（Nature Nearest Neighbor）

``````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)

``````