算法简介
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种经典的基于密度的聚类算法。与K-means等基于距离的算法不同，DBSCAN能够发现任意形状的簇，并自动识别噪声点。算法的核心思想是：通过检查每个数据点邻域内的点密度，将高密度区域划分为簇，将低密度区域标记为噪声。
核心思想
DBSCAN算法依赖两个关键参数：
- ε（eps）：邻域半径，定义了一个点的邻域范围
- MinPts：最小点数，一个核心点邻域内至少包含的点数
根据这两个参数，点被分为三类：
- 核心点（Core Point）：邻域内包含至少MinPts个点的点
- 边界点（Border Point）：在核心点邻域内但自身邻域不满足MinPts条件的点
- 噪声点（Noise Point）：既不是核心点也不是边界点的点
算法从任意一个未访问的核心点开始，通过密度可达性不断扩展簇，直到所有点都被处理完毕。
Java实现
import java.util.*;
/**
* DBSCAN密度聚类算法实现
*
* @author AlgorithmDaily
*/
public class DBSCAN {
// 邻域半径
private double eps;
// 最小点数阈值
private int minPts;
// 数据点列表
private List<Point> points;
// 簇ID计数器，0表示噪声
private int clusterId;
/**
* 数据点内部类
*/
public static class Point {
double x, y;
int clusterId; // 所属簇ID，0为未分配，-1为噪声
boolean visited; // 是否已访问
public Point(double x, double y) {
this.x = x;
this.y = y;
this.clusterId = 0;
this.visited = false;
}
/**
* 计算与另一个点的欧几里得距离
*/
public double distanceTo(Point other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
@Override
public String toString() {
return String.format("(%.2f, %.2f)[cluster=%d]", x, y, clusterId);
}
}
public DBSCAN(double eps, int minPts) {
this.eps = eps;
this.minPts = minPts;
this.clusterId = 0;
}
/**
* 执行DBSCAN聚类
* @param points 待聚类的数据点列表
* @return 聚类结果，每个簇包含一组点
*/
public List<List<Point>> cluster(List<Point> points) {
this.points = points;
this.clusterId = 0;
// 重置所有点状态
for (Point p : points) {
p.visited = false;
p.clusterId = 0;
}
List<List<Point>> clusters = new ArrayList<>();
for (Point point : points) {
if (point.visited) continue;
point.visited = true;
// 获取该点的ε邻域内的所有点
List<Point> neighbors = getNeighbors(point);
// 邻域点数不足MinPts，标记为噪声
if (neighbors.size() < minPts) {
point.clusterId = -1;
} else {
// 发现新的簇
clusterId++;
List<Point> cluster = new ArrayList<>();
expandCluster(point, neighbors, cluster);
clusters.add(cluster);
}
}
return clusters;
}
/**
* 获取指定点的ε邻域内的所有点
*/
private List<Point> getNeighbors(Point center) {
List<Point> neighbors = new ArrayList<>();
for (Point p : points) {
if (center.distanceTo(p) <= eps) {
neighbors.add(p);
}
}
return neighbors;
}
/**
* 扩展簇：从核心点开始，密度可达的所有点加入同一簇
*/
private void expandCluster(Point corePoint, List<Point> neighbors, List<Point> cluster) {
// 核心点加入当前簇
corePoint.clusterId = clusterId;
cluster.add(corePoint);
// 使用队列进行广度优先扩展
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) {
queue.addAll(currentNeighbors);
}
}
// 如果点尚未分配簇（包括之前被标记为噪声的点），加入当前簇
if (current.clusterId <= 0) {
current.clusterId = clusterId;
cluster.add(current);
}
}
}
/**
* 获取所有噪声点
*/
public List<Point> getNoisePoints() {
List<Point> noise = new ArrayList<>();
for (Point p : points) {
if (p.clusterId == -1) {
noise.add(p);
}
}
return noise;
}
/**
* 主程序：演示DBSCAN聚类
*/
public static void main(String[] args) {
// 生成测试数据：两个密度不同的簇加一些噪声点
List<Point> data = new ArrayList<>();
Random random = new Random(42);
// 簇1：中心(2, 2)的密集簇
for (int i = 0; i < 50; i++) {
data.add(new Point(
2 + random.nextGaussian() * 0.3,
2 + random.nextGaussian() * 0.3
));
}
// 簇2：中心(6, 6)的密集簇
for (int i = 0; i < 40; i++) {
data.add(new Point(
6 + random.nextGaussian() * 0.4,
6 + random.nextGaussian() * 0.4
));
}
// 添加一些噪声点
for (int i = 0; i < 10; i++) {
data.add(new Point(
random.nextDouble() * 10,
random.nextDouble() * 10
));
}
// 执行DBSCAN聚类
DBSCAN dbscan = new DBSCAN(0.8, 5);
List<List<Point>> clusters = dbscan.cluster(data);
System.out.println("=== DBSCAN聚类结果 ===");
System.out.println("参数：eps=" + dbscan.eps + ", minPts=" + dbscan.minPts);
System.out.println("发现 " + clusters.size() + " 个簇");
for (int i = 0; i < clusters.size(); i++) {
System.out.println("簇 " + (i + 1) + ": " + clusters.get(i).size() + " 个点");
}
List<Point> noise = dbscan.getNoisePoints();
System.out.println("噪声点: " + noise.size() + " 个");
}
}
复杂度分析
- 时间复杂度：最坏情况下为 $O(n^2)$，其中 $n$ 是数据点数量。这是因为每个点都需要计算与其他所有点的距离。如果使用空间索引结构（如R树或k-d树），可以优化到 $O(n \log n)$。
- 空间复杂度：$O(n)$，需要存储所有点的邻域信息和访问状态。
算法特点与适用场景
优点：
– 无需预先指定簇的数量
– 能够发现任意形状的簇
– 对噪声点具有鲁棒性
缺点：
– 参数 eps 和 minPts 的选择对结果影响很大
– 对高维数据效果不佳（维度灾难）
– 密度不均匀的数据集效果较差
适用场景：图像分割、异常检测、地理空间数据分析、客户分群等。
