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

引言

在机器学习领域，聚类是一种重要的无监督学习方法。与K-means等基于距离的聚类算法不同，DBSCAN（Density-Based Spatial Clustering of Applications with Noise）基于密度的概念进行聚类，能够自动识别任意形状的簇，并将噪声点标记为异常值。1996年由Ester等人提出以来，DBSCAN因其鲁棒性和灵活性，在地理信息系统、图像分割、异常检测等领域得到广泛应用。

算法原理

1. 核心概念

• ε-邻域：以某点为中心、半径为ε的圆形区域
• 核心点：ε-邻域内包含至少MinPts个点的点
• 边界点：在核心点的ε-邻域内，但自身不是核心点
• 噪声点：既不是核心点也不是边界点的点
• 直接密度可达：点q在核心点p的ε-邻域内
• 密度可达：存在点链p₁,…,pₙ，每对相邻点直接密度可达
• 密度相连：存在点o，使p和q都从o密度可达

2. 算法步骤

1. 遍历所有点，标记每个点为核心点、边界点或噪声点
2. 删除噪声点
3. 为每个核心点创建簇，将密度相连的核心点合并到同一簇
4. 将边界点分配到相邻核心点所在的簇

3. 与K-means的对比

Java实现

import java.util.*;

/**
 * DBSCAN密度聚类算法实现
 * 能够识别任意形状的簇并标记噪声点
 */
public class DBSCAN {

    /**
     * 数据点类
     */
    static class Point {
        double[] features;
        int clusterId;      // -1表示未分类，0表示噪声
        boolean visited;

        Point(double[] features) {
            this.features = features;
            this.clusterId = -1;
            this.visited = false;
        }

        /**
         * 计算与另一点的欧几里得距离
         */
        double distance(Point other) {
            double sum = 0;
            for (int i = 0; i < features.length; i++) {
                double diff = features[i] - other.features[i];
                sum += diff * diff;
            }
            return Math.sqrt(sum);
        }

        @Override
        public String toString() {
            return Arrays.toString(features) + " [cluster=" + clusterId + "]";
        }
    }

    private double eps;      // 邻域半径
    private int minPts;      // 成为核心点的最小邻居数
    private List<Point> points;

    public DBSCAN(double eps, int minPts) {
        this.eps = eps;
        this.minPts = minPts;
        this.points = new ArrayList<>();
    }

    public void addPoint(double[] features) {
        points.add(new Point(features));
    }

    /**
     * 获取某点的ε-邻域内所有点（包括自身）
     */
    List<Point> getNeighbors(Point center) {
        List<Point> neighbors = new ArrayList<>();
        for (Point p : points) {
            if (center.distance(p) <= eps) {
                neighbors.add(p);
            }
        }
        return neighbors;
    }

    /**
     * 执行DBSCAN聚类
     * @return 簇的数量（噪声点不计入）
     */
    public int cluster() {
        int clusterId = 0;

        for (Point p : points) {
            if (p.visited) continue;
            p.visited = true;

            List<Point> neighbors = getNeighbors(p);

            // 噪声点：邻居数不足MinPts
            if (neighbors.size() < minPts) {
                p.clusterId = 0; // 标记为噪声
            } else {
                // 发现新簇
                clusterId++;
                expandCluster(p, neighbors, clusterId);
            }
        }

        return clusterId;
    }

    /**
     * 扩展簇：将密度可达的点加入当前簇
     */
    void expandCluster(Point corePoint, List<Point> neighbors, int clusterId) {
        corePoint.clusterId = clusterId;

        // 使用队列进行BFS扩展
        Queue<Point> queue = new LinkedList<>(neighbors);

        while (!queue.isEmpty()) {
            Point current = queue.poll();

            if (!current.visited) {
                current.visited = true;
                List<Point> currentNeighbors = getNeighbors(current);

                // 如果当前点也是核心点，将其邻居加入队列
                if (currentNeighbors.size() >= minPts) {
                    for (Point n : currentNeighbors) {
                        if (n.clusterId == -1 || n.clusterId == 0) {
                            queue.offer(n);
                        }
                    }
                }
            }

            // 如果点尚未分配到任何簇，加入当前簇
            if (current.clusterId == -1 || current.clusterId == 0) {
                current.clusterId = clusterId;
            }
        }
    }

    /**
     * 获取聚类结果
     */
    public Map<Integer, List<Point>> getClusters() {
        Map<Integer, List<Point>> clusters = new HashMap<>();
        for (Point p : points) {
            clusters.computeIfAbsent(p.clusterId, k -> new ArrayList<>()).add(p);
        }
        return clusters;
    }

    /**
     * 获取噪声点列表
     */
    public List<Point> getNoisePoints() {
        List<Point> noise = new ArrayList<>();
        for (Point p : points) {
            if (p.clusterId == 0) noise.add(p);
        }
        return noise;
    }

    /**
     * 计算轮廓系数评估聚类质量
     */
    public double silhouetteScore() {
        double totalScore = 0;
        int validPoints = 0;

        for (Point p : points) {
            if (p.clusterId <= 0) continue; // 跳过噪声和未分类点

            double a = averageIntraDistance(p);
            double b = averageNearestInterDistance(p);

            if (a != -1 && b != -1) {
                totalScore += (b - a) / Math.max(a, b);
                validPoints++;
            }
        }

        return validPoints == 0 ? 0 : totalScore / validPoints;
    }

    /**
     * 计算点到同簇其他点的平均距离
     */
    double averageIntraDistance(Point p) {
        double sum = 0;
        int count = 0;
        for (Point other : points) {
            if (other != p && other.clusterId == p.clusterId) {
                sum += p.distance(other);
                count++;
            }
        }
        return count == 0 ? -1 : sum / count;
    }

    /**
     * 计算点到最近其他簇的平均距离
     */
    double averageNearestInterDistance(Point p) {
        double minAvg = Double.MAX_VALUE;
        for (int cid : getClusterIds()) {
            if (cid == p.clusterId || cid <= 0) continue;
            double sum = 0;
            int count = 0;
            for (Point other : points) {
                if (other.clusterId == cid) {
                    sum += p.distance(other);
                    count++;
                }
            }
            if (count > 0) {
                minAvg = Math.min(minAvg, sum / count);
            }
        }
        return minAvg == Double.MAX_VALUE ? -1 : minAvg;
    }

    Set<Integer> getClusterIds() {
        Set<Integer> ids = new HashSet<>();
        for (Point p : points) ids.add(p.clusterId);
        return ids;
    }

    public static void main(String[] args) {
        // 测试案例：生成两个同心圆簇加一些噪声
        DBSCAN dbscan = new DBSCAN(0.5, 4);

        // 簇1：中心(0,0)，半径1附近的点
        for (int i = 0; i < 50; i++) {
            double angle = 2 * Math.PI * i / 50;
            double r = 1.0 + (Math.random() - 0.5) * 0.2;
            dbscan.addPoint(new double[]{r * Math.cos(angle), r * Math.sin(angle)});
        }

        // 簇2：中心(3,3)，半径0.8附近的点
        for (int i = 0; i < 40; i++) {
            double angle = 2 * Math.PI * i / 40;
            double r = 0.8 + (Math.random() - 0.5) * 0.2;
            dbscan.addPoint(new double[]{3 + r * Math.cos(angle), 3 + r * Math.sin(angle)});
        }

        // 噪声点
        dbscan.addPoint(new double[]{5, 5});
        dbscan.addPoint(new double[]{-2, -2});
        dbscan.addPoint(new double[]{2, 5});

        int numClusters = dbscan.cluster();
        System.out.println("发现簇数量：" + numClusters);
        System.out.println("噪声点数量：" + dbscan.getNoisePoints().size());

        Map<Integer, List<Point>> clusters = dbscan.getClusters();
        for (Map.Entry<Integer, List<Point>> entry : clusters.entrySet()) {
            System.out.println("簇 " + entry.getKey() + "：" + entry.getValue().size() + " 个点");
        }

        double score = dbscan.silhouetteScore();
        System.out.println("轮廓系数：" + String.format("%.4f", score));
    }
}

复杂度分析

对于大规模数据集，建议使用空间索引结构（如KD-Tree）加速邻域查询。

参数选择策略

1. MinPts：通常取维度数+1，或2×维度数
2. ε：可通过K-距离图（k-distance graph）选择，取拐点处的距离值
3. 自适应DBSCAN：自动估计参数，如OPTICS算法

应用场景

1. 地理信息系统：基于位置的商铺聚类、热点区域发现
2. 图像分割：基于颜色或纹理的像素聚类
3. 异常检测：网络入侵检测、信用卡欺诈识别
4. 社交网络分析：社区发现与意见领袖识别

总结

DBSCAN通过密度概念实现聚类，克服了K-means对簇形状和噪声敏感的缺点。其核心优势在于无需预先指定簇数量，能自动发现任意形状的簇。理解密度可达和密度相连的概念，是掌握DBSCAN算法的关键。