题解 | DBSCAN聚类

import sys
import math

def cal_dis(point1,point2):
    dim = len(point1)
    sum_up = 0
    for i in range(dim):
        sum_up += (point1[i]-point2[i])**2
    return math.sqrt(sum_up)


def get_neighbors(samples,ind,eps):
    neighbors = []
    for i in range(len(samples)):
        dis = cal_dis(samples[i],samples[ind])
        if dis <= eps:
            neighbors.append(i)
    return neighbors


def DBSCAN(eps,min_samples,x,samples):
	#使用一个列表core_points，表示每个点是否为核心点，0为非核心点，1为核心点,初始化为0
    #使用一个列表label_ind，表示每个点的簇的下标，初始化为-2,表示未访问,-1为噪声,其他值表示簇的下标。
    core_points = [0 for i in range(x)]
    label_ind = [-2 for i in range(x)]
    cluster_id = 0

    for i in range(x):
       if label_ind[i] != -2:
	   #已经访问过此点，直接下一个
           continue
       neighbors = get_neighbors(samples,i,eps)
       if len(neighbors) < min_samples:
           label_ind[i] = -1
       else:
           points_set = list(neighbors) #表示需要扩展的点集
           points_set.remove(i) #删除点自身
           label_ind[i] = cluster_id #更新此点簇的序号
           core_points[i] = 1 #此点为核心点

           j = 0
           while j < len(points_set): #对于需要扩展的点
               point_ind = points_set[j]
               if label_ind[point_ind] == -1: #为噪声，不扩展
                   label_ind[point_ind] = cluster_id
               elif label_ind[point_ind] == -2:
                   #关键在于此处，不断更新需要扩展的点集
                   #如果当前点未被访问过，判断是否为核心点，如果是，则更新需要扩展的点的集合,并且只将未被访问过的点或者噪声点加入
                    label_ind[point_ind] = cluster_id
                    point_neighbor = get_neighbors(samples,point_ind,eps)
                    if len(point_neighbor) >= min_samples:
                        core_points[point_ind] = 1
                        for neighbor_ind in point_neighbor:
                            if label_ind[neighbor_ind] == -2 or label_ind[neighbor_ind] == -1:
                                if neighbor_ind not in points_set:
                                    points_set.append(neighbor_ind)
               j += 1
           cluster_id += 1
    noise_count = label_ind.count(-1)
    cluster_num = len(set(label_ind))-(1 if -1 in label_ind else 0)
    return cluster_num,noise_count


if __name__ == '__main__':
    lines = []
    while True:
        try:
            line = input().split()
            if line:
                lines.append(line)
            else:
                break
        except EOFError:
            break
    eps, min_samples, x = float(lines[0][0]), int(lines[0][1]), int(lines[0][2])
    samples = [ (float(lines[i][0]),float(lines[i][1])) for i in range(1,len(lines))]
    cluster_num, noise_count = DBSCAN(eps, min_samples, x, samples)
    print(cluster_num,noise_count)