DBSCAN聚类

[编程题]DBSCAN聚类

热度指数：434 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

任务: 用DBSCAN在二维或三维实数坐标上做聚类，输出“簇的数量”和“噪声点数量”。
定义: 距离为欧氏距离；某点的邻域半径为eps；若该点邻域内样本数（含自身）≥ min_samples，则为核心点；从未访问核心点出发，按邻域可达关系扩展一个簇；不被任何簇吸收的点视为噪声

输入描述:

第一行: eps min_samples x
接下来x行: 每行2个或3个实数（同一测试仅一种维度）

输出描述:

一行: 簇数 噪声点数

示例1

输入

输出

2 0

说明

前3个点彼此间距都≤1.5，形成一簇；后3个点同理形成另一簇；无噪声。

备注:

本题由牛友@Charles 整理上传

算法知识视频讲解

Python3

摆烂咸鱼大学生

感觉比现有两个题解简洁一点

from math import sqrt

eps, min_sample, x = map(eval, input().split())

nodes = []
for _ in range(x):
    nodes.append(tuple(map(eval, input().split())))

def dist(n1, n2):
    tmp = 0
    for x1, x2 in zip(n1, n2):
        tmp += (x1 - x2) ** 2
    return sqrt(tmp)

def func(node):
    if node in centers:
        return True
    tmp = []
    for n in nodes:
        if dist(node, n) <= eps:
            tmp.append(n)
    if len(tmp) < min_sample:
        return False
    centers.add(node)
    closed.update(tmp)
    for n in tmp:
        func(n)
    return True
    
centers = set()
closed = set()
clusters = 0
for node in nodes:
    if node in closed:
        continue
    elif func(node):
        clusters += 1

print(clusters, x - len(closed))

发表于 2025-10-28 22:46:57 回复(0)