每日算法 — 使用java实现DBSCAN聚类：密度可达与噪声点识别算法

算法概述

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是由Martin Ester等人于1996年提出的基于密度的聚类算法。与K-means等划分式聚类算法不同，DBSCAN不需要预先指定聚类数量，能够发现任意形状的簇，并且具有识别噪声点的能力。

本文将深入讲解DBSCAN的核心概念（密度可达、核心点、边界点、噪声点），并给出完整的Java实现，包含空间索引优化与可视化辅助理解。

核心概念

密度定义

DBSCAN使用两个关键参数定义密度：

• ε（epsilon）：邻域半径。以某点为中心、ε为半径的圆（二维）或球（高维）内的区域称为该点的ε-邻域
• MinPts：成为核心点所需的最小邻域点数。通常取MinPts ≥ 维度数 + 1

点的分类

根据点在密度空间的分布，DBSCAN将点分为三类：

1. 核心点（Core Point）：ε-邻域内包含至少MinPts个点（包括自身）的点
2. 边界点（Border Point）：ε-邻域内点数少于MinPts，但落在某个核心点ε-邻域内的点
3. 噪声点（Noise Point）：既不是核心点也不是边界点的点

密度关系

• 直接密度可达：点p在核心点q的ε-邻域内，则p从q直接密度可达
• 密度可达：存在点链p₁,p₂,…,pₙ，其中p_{i+1}从p_i直接密度可达，则pₙ从p₁密度可达
• 密度相连：若存在点o使得p和q都从o密度可达，则p和q密度相连

簇的定义

一个簇是满足以下条件的最大点集合：
1. 簇内任意两点密度相连
2. 簇内至少包含一个核心点

完整Java实现

import java.util.*;

/**
 * DBSCAN密度聚类算法实现
 * 时间复杂度: O(n * 邻居查询时间)，使用KD树可优化到O(n log n)
 * 空间复杂度: O(n)
 */
public class DBSCAN {

    // 点类别常量
    public static final int UNCLASSIFIED = -2;   // 未分类
    public static final int NOISE = -1;          // 噪声点

    // 数据点集合
    private final double[][] points;
    private final int n;
    private final int dim;

    // 每个点的聚类标签
    private final int[] labels;

    // 邻域半径
    private final double eps;

    // 最小点数阈值
    private final int minPts;

    // 当前聚类编号
    private int clusterId;

    /**
     * 构造函数
     * @param points 输入数据点，每个点是一个double数组
     * @param eps ε邻域半径
     * @param minPts 核心点最小邻域点数
     */
    public DBSCAN(double[][] points, double eps, int minPts) {
        this.points = points;
        this.n = points.length;
        this.dim = points[0].length;
        this.eps = eps;
        this.minPts = minPts;
        this.labels = new int[n];
        Arrays.fill(labels, UNCLASSIFIED);
        this.clusterId = 0;
    }

    /**
     * 执行DBSCAN聚类
     * @return 每个点的聚类标签，NOISE表示噪声点
     */
    public int[] cluster() {
        for (int i = 0; i < n; i++) {
            // 如果点已经分类，跳过
            if (labels[i] != UNCLASSIFIED) {
                continue;
            }

            // 获取点i的ε-邻域
            List<Integer> neighbors = regionQuery(i);

            // 如果邻域点数不足MinPts，标记为噪声点
            if (neighbors.size() < minPts) {
                labels[i] = NOISE;
            } else {
                // 发现一个新的簇
                clusterId++;
                expandCluster(i, neighbors, clusterId);
            }
        }

        return labels.clone();
    }

    /**
     * 扩展簇：从核心点出发，将所有密度可达的点加入同一簇
     * @param corePoint 核心点索引
     * @param neighbors 核心点的ε-邻域
     * @param clusterId 当前簇编号
     */
    private void expandCluster(int corePoint, List<Integer> neighbors, int clusterId) {
        // 将核心点标记为当前簇
        labels[corePoint] = clusterId;

        // 使用队列进行BFS扩展
        ArrayDeque<Integer> queue = new ArrayDeque<>(neighbors);

        // 注意：neighbors列表本身也需要标记
        for (int nb : neighbors) {
            if (labels[nb] == UNCLASSIFIED || labels[nb] == NOISE) {
                labels[nb] = clusterId;
            }
        }

        while (!queue.isEmpty()) {
            int point = queue.poll();

            // 获取当前点的ε-邻域
            List<Integer> pointNeighbors = regionQuery(point);

            // 如果当前点也是核心点，继续扩展
            if (pointNeighbors.size() >= minPts) {
                for (int newPoint : pointNeighbors) {
                    if (labels[newPoint] == UNCLASSIFIED) {
                        // 未分类的点加入队列并标记
                        labels[newPoint] = clusterId;
                        queue.add(newPoint);
                    } else if (labels[newPoint] == NOISE) {
                        // 噪声点可能是边界点，重新标记但不扩展
                        labels[newPoint] = clusterId;
                    }
                }
            }
        }
    }

    /**
     * 区域查询：获取点idx的ε-邻域内所有点的索引
     * 基础实现为线性扫描，时间复杂度O(n)
     * 对于大规模数据，建议替换为KD-Tree或Ball-Tree查询
     */
    private List<Integer> regionQuery(int idx) {
        List<Integer> neighbors = new ArrayList<>();
        double[] p = points[idx];

        for (int i = 0; i < n; i++) {
            if (i == idx) {
                neighbors.add(i); // 自身也算在邻域内
                continue;
            }
            if (euclideanDistance(p, points[i]) <= eps) {
                neighbors.add(i);
            }
        }

        return neighbors;
    }

    /**
     * 计算两个点之间的欧几里得距离
     */
    private double euclideanDistance(double[] a, double[] b) {
        double sum = 0.0;
        for (int i = 0; i < dim; i++) {
            double diff = a[i] - b[i];
            sum += diff * diff;
        }
        return Math.sqrt(sum);
    }

    /**
     * 获取聚类统计信息
     */
    public ClusterStats getStats() {
        int noiseCount = 0;
        Set<Integer> clusterSet = new HashSet<>();
        Map<Integer, Integer> clusterCounts = new HashMap<>();

        for (int label : labels) {
            if (label == NOISE) {
                noiseCount++;
            } else if (label > 0) {
                clusterSet.add(label);
                clusterCounts.merge(label, 1, Integer::sum);
            }
        }

        return new ClusterStats(clusterSet.size(), noiseCount, clusterCounts);
    }

    /**
     * 聚类统计结果
     */
    public static class ClusterStats {
        public final int clusterCount;
        public final int noiseCount;
        public final Map<Integer, Integer> clusterSizeMap;

        public ClusterStats(int clusterCount, int noiseCount, Map<Integer, Integer> clusterSizeMap) {
            this.clusterCount = clusterCount;
            this.noiseCount = noiseCount;
            this.clusterSizeMap = clusterSizeMap;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("聚类数量: ").append(clusterCount).append("\n");
            sb.append("噪声点数量: ").append(noiseCount).append("\n");
            sb.append("各簇大小:\n");
            for (Map.Entry<Integer, Integer> entry : clusterSizeMap.entrySet()) {
                sb.append("  簇").append(entry.getKey()).append(": ").append(entry.getValue()).append(" 点\n");
            }
            return sb.toString();
        }
    }

    // ==================== 测试主程序 ====================

    public static void main(String[] args) {
        // 构造测试数据：三个明显的簇 + 一些噪声点
        List<double[]> dataList = new ArrayList<>();
        Random rand = new Random(42);

        // 簇1：中心(2,2)，50个点
        for (int i = 0; i < 50; i++) {
            dataList.add(new double[]{
                2.0 + rand.nextGaussian() * 0.3,
                2.0 + rand.nextGaussian() * 0.3
            });
        }

        // 簇2：中心(6,6)，40个点
        for (int i = 0; i < 40; i++) {
            dataList.add(new double[]{
                6.0 + rand.nextGaussian() * 0.3,
                6.0 + rand.nextGaussian() * 0.3
            });
        }

        // 簇3：中心(2,6)，30个点（形成月牙形）
        for (int i = 0; i < 30; i++) {
            double angle = Math.PI * i / 30;
            dataList.add(new double[]{
                2.0 + Math.cos(angle) * 1.0 + rand.nextGaussian() * 0.15,
                6.0 + Math.sin(angle) * 1.0 + rand.nextGaussian() * 0.15
            });
        }

        // 噪声点：20个随机散点
        for (int i = 0; i < 20; i++) {
            dataList.add(new double[]{
                rand.nextDouble() * 10,
                rand.nextDouble() * 10
            });
        }

        double[][] points = dataList.toArray(new double[0][]);

        // 执行DBSCAN聚类
        double eps = 0.8;
        int minPts = 5;

        DBSCAN dbscan = new DBSCAN(points, eps, minPts);
        int[] labels = dbscan.cluster();

        // 输出统计
        DBSCAN.ClusterStats stats = dbscan.getStats();
        System.out.println("=== DBSCAN聚类结果 ===");
        System.out.println("参数: eps=" + eps + ", minPts=" + minPts);
        System.out.println("总点数: " + points.length);
        System.out.println(stats);

        // 参数敏感性测试
        System.out.println("\n=== 参数敏感性测试 ===");
        testParameterSensitivity(points);
    }

    /**
     * 测试不同参数组合的效果
     */
    private static void testParameterSensitivity(double[][] points) {
        double[][] epsValues = {{0.5, 0.8, 1.2}, {3, 5, 8}};

        for (double eps : new double[]{0.5, 0.8, 1.2}) {
            for (int minPts : new int[]{3, 5, 8}) {
                DBSCAN dbscan = new DBSCAN(points, eps, minPts);
                dbscan.cluster();
                ClusterStats stats = dbscan.getStats();
                System.out.printf("eps=%.1f, minPts=%d -> 簇数=%d, 噪声=%d%n",
                    eps, minPts, stats.clusterCount, stats.noiseCount);
            }
        }
    }
}

ε与MinPts参数选择

DBSCAN的效果高度依赖参数选择。以下是常用的参数选择策略：

k-距离图法

1. 对每个点计算到其第k个最近邻的距离（k = MinPts – 1）
2. 将所有k-距离按降序排列绘制曲线
3. 曲线中第一个”拐点”对应的距离即为推荐的ε值

/**
 * 计算k-距离辅助参数选择
 */
public static double[] computeKDistances(double[][] points, int k) {
    int n = points.length;
    double[] kDistances = new double[n];

    for (int i = 0; i < n; i++) {
        // 计算点i到所有其他点的距离
        double[] distances = new double[n];
        for (int j = 0; j < n; j++) {
            distances[j] = euclideanDistance(points[i], points[j]);
        }
        Arrays.sort(distances);
        // distances[0]是自身距离0，取第k个
        kDistances[i] = distances[k];
    }

    Arrays.sort(kDistances);
    // 降序排列便于观察拐点
    for (int i = 0; i < n / 2; i++) {
        double tmp = kDistances[i];
        kDistances[i] = kDistances[n - 1 - i];
        kDistances[n - 1 - i] = tmp;
    }

    return kDistances;
}

MinPts经验公式

• 二维数据：MinPts = 4
• 高维数据：MinPts = 2 × 维度数

复杂度分析

与K-means的对比

应用场景

• 地理信息系统：根据位置密度发现城市热点区域
• 图像分割：基于像素颜色空间的密度聚类
• 异常检测：自动识别交易数据中的噪声/欺诈点
• 社交网络分析：发现紧密连接的社区结构
• 推荐系统：基于用户行为密度的兴趣群组发现

小结

DBSCAN通过密度的局部定义，实现了无需预设簇数量、支持任意形状簇、自动识别噪声的聚类能力。理解该算法的关键在于掌握核心点、密度可达和密度相连三个核心概念。在实际应用中，参数ε和MinPts的选择对结果影响巨大，建议结合k-距离图进行辅助决策。对于大规模数据集，使用KD-Tree或Ball-Tree替代线性邻域查询是实现高效DBSCAN的关键优化。