DBSCAN聚类

题意

给定若干二维或三维坐标点，以及 DBSCAN 算法的两个参数 （邻域半径）和 （最少样本数），要求输出聚类个数和噪声点个数。

核心定义：

  • 距离度量：欧几里得距离
  • 核心点： 邻域内的点数（含自身）
  • 聚类通过核心点的邻域可达性扩展
  • 噪声点：不属于任何聚类的点

思路

DBSCAN 本质上是一个图搜索问题。你先想清楚两件事就行了：谁是核心点？从核心点出发能"传染"到谁？

第一步：找邻居。 对每个点，暴力 枚举所有点对，算欧氏距离。距离 的就互为邻居。这一步可以预处理出每个点的邻居列表。

第二步：判定核心点。 一个点的邻居数加上自身 ，它就是核心点。

第三步：BFS 扩展聚类。 按序扫描所有点，遇到一个未被分配且是核心点的点，就从它开始 BFS。BFS 的规则是：

  • 把当前点的所有未分配邻居都拉进当前聚类
  • 但只有核心点邻居才继续入队扩展

为什么非核心点不继续扩展？因为 DBSCAN 的定义里，非核心点是"边界点"——它能被核心点拉进聚类，但它自己的邻域不够"密"，没有资格继续传播。

最后： 扫描结束后，所有仍然没被分配聚类的点就是噪声点。

复杂度

  • 时间：，其中 是点数， 是维度（2 或 3）。瓶颈在距离计算。
  • 空间：，存邻居列表。

代码

import math
from collections import deque

def solve():
    first_line = input().split()
    eps = float(first_line[0])
    min_samples = int(first_line[1])
    x = int(first_line[2])

    points = []
    for _ in range(x):
        coords = list(map(float, input().split()))
        points.append(coords)

    n = len(points)

    def dist(a, b):
        return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

    # 预处理每个点的邻居
    neighbors = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            d = dist(points[i], points[j])
            if d <= eps:
                neighbors[i].append(j)
                neighbors[j].append(i)

    # 判定核心点（邻居数 + 自身 >= min_samples）
    is_core = [len(neighbors[i]) + 1 >= min_samples for i in range(n)]

    # BFS 扩展聚类
    cluster_id = [-1] * n
    current_cluster = 0

    for i in range(n):
        if cluster_id[i] != -1 or not is_core[i]:
            continue
        queue = deque([i])
        cluster_id[i] = current_cluster
        while queue:
            p = queue.popleft()
            for nb in neighbors[p]:
                if cluster_id[nb] == -1:
                    cluster_id[nb] = current_cluster
                    if is_core[nb]:
                        queue.append(nb)
        current_cluster += 1

    noise_count = cluster_id.count(-1)
    print(current_cluster, noise_count)

solve()

#include <bits/stdc++.h>
using namespace std;

int main(){
    double eps;
    int minSamples, x;
    cin >> eps >> minSamples >> x;

    vector<vector<double>> pts(x);
    for(int i = 0; i < x; i++){
        string line;
        getline(cin >> ws, line);
        istringstream iss(line);
        double v;
        while(iss >> v) pts[i].push_back(v);
    }

    int dim = pts[0].size();

    vector<vector<int>> nb(x);
    for(int i = 0; i < x; i++){
        for(int j = i+1; j < x; j++){
            double d2 = 0;
            for(int k = 0; k < dim; k++){
                double diff = pts[i][k] - pts[j][k];
                d2 += diff * diff;
            }
            if(sqrt(d2) <= eps){
                nb[i].push_back(j);
                nb[j].push_back(i);
            }
        }
    }

    vector<bool> isCore(x, false);
    for(int i = 0; i < x; i++){
        if((int)nb[i].size() + 1 >= minSamples) isCore[i] = true;
    }

    vector<int> cid(x, -1);
    int cur = 0;
    for(int i = 0; i < x; i++){
        if(cid[i] != -1 || !isCore[i]) continue;
        queue<int> q;
        q.push(i);
        cid[i] = cur;
        while(!q.empty()){
            int p = q.front(); q.pop();
            for(int n : nb[p]){
                if(cid[n] == -1){
                    cid[n] = cur;
                    if(isCore[n]) q.push(n);
                }
            }
        }
        cur++;
    }

    int noise = count(cid.begin(), cid.end(), -1);
    cout << cur << " " << noise << endl;
}