C++实现DBSCAN聚类算法（附带源码）
一、项目背景详细介绍
1. 聚类分析的意义
聚类（Clustering）是机器学习和数据挖掘中的一个基础问题，其目标是：
根据样本间的相似性或距离，将样本自动分为若干组，使得组内样本尽可能相似，组间样本尽可能不同。
常见的聚类算法包括：
-
K-Means：基于中心点的划分；
-
Hierarchical Clustering：基于层次合并；
-
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）：基于密度的聚类。
在这些方法中，DBSCAN 是一种非常重要的基于密度的聚类算法，它能自动识别任意形状的簇，并能有效处理噪声点。
2. DBSCAN 算法简介
DBSCAN 由 Martin Ester 等人在 1996 年提出。
它的核心思想是：
“高密度区域属于同一类，而低密度区域是噪声。”
DBSCAN 不需要指定簇的数量（不同于 K-Means），只需两个参数：
-
Eps（ε）：邻域半径；
-
MinPts：最小点数（形成簇的最低密度）。
算法将样本划分为三类：
-
核心点（Core Point）：邻域内包含 ≥ MinPts 的点；
-
边界点（Border Point）：邻域内点 < MinPts，但在核心点邻域中；
-
噪声点（Noise Point）：既非核心点也非边界点。
3. DBSCAN 的核心优势
-
不依赖预定义的簇数；
-
能发现任意形状的簇；
-
对噪声具有鲁棒性；
-
参数少（Eps 与 MinPts）。
4. 项目目标
实现一个 纯 C++17 的 DBSCAN 聚类算法，要求：
-
输入二维样本点集合；
-
支持参数配置（Eps, MinPts）；
-
输出每个点的聚类标签；
-
显示聚类结果统计；
-
可扩展到高维。
二、项目需求详细介绍
功能性需求：
-
输入数据：
-
支持从文本或手动输入二维坐标；
-
样本为
(x, y)。
-
-
核心功能：
-
实现 DBSCAN 算法；
-
支持自定义参数：
-
邻域半径
eps -
最小点数
minPts
-
-
输出每个点所属簇编号；
-
标记噪声点。
-
-
输出：
-
每个点的坐标与聚类标签；
-
聚类总数；
-
噪声点数量。
-
-
可视化（可扩展）：
-
结果保存为
.csv； -
便于后续用 Python / MATLAB 绘制。
-
三、相关技术详细介绍
1. 欧氏距离计算
DBSCAN 依赖距离度量判断邻域点，一般使用欧氏距离：
2. DBSCAN 算法步骤
伪代码如下：
for each unvisited point P in dataset:
mark P as visited
NeighborPts = regionQuery(P, eps)
if size(NeighborPts) < MinPts:
mark P as Noise
else:
create new cluster C
expandCluster(P, NeighborPts, C, eps, MinPts)
expandCluster 逻辑：
for each point P' in NeighborPts:
if P' is not visited:
mark P' as visited
NeighborPts' = regionQuery(P', eps)
if size(NeighborPts') >= MinPts:
NeighborPts += NeighborPts'
if P' not yet assigned to any cluster:
assign P' to cluster C
3. 复杂度分析
-
时间复杂度：O(n²)，因为需要计算所有点对之间距离；
-
空间复杂度：O(n)。
对于较大数据集，可使用 KD-Tree 加速邻域搜索，但本项目以教学为主，采用简单暴力实现。
4. 参数选取技巧
-
eps过小：大多数点成为噪声； -
eps过大：不同簇可能合并； -
minPts一般设为维度数的两倍（2D → 4~6）。
四、实现思路详细介绍
-
数据结构设计
struct Point {
double x, y;
int clusterId; // 聚类编号，-1 表示噪声，0 表示未分类
bool visited;
}; -
主要方法
-
double distance(Point a, Point b)：计算欧氏距离； -
std::vector<int> regionQuery(int idx)：查找邻域点； -
void expandCluster(int idx, int clusterId)：扩展簇； -
void dbscan()：主算法流程。
-
-
输出
-
打印聚类统计；
-
输出每个点的聚类编号。
-
五、完整实现代码
/************************************************************
* 文件名: dbscan.cpp
* 功能: 使用C++17实现DBSCAN聚类算法
* 编译:
* g++ -std=c++17 -O2 -Wall -o dbscan dbscan.cpp
* 运行:
* ./dbscan
************************************************************/
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
struct Point {
double x, y;
int clusterId; // -1 表示噪声, 0 表示未分类
bool visited;
Point(double x=0, double y=0): x(x), y(y), clusterId(0), visited(false) {}
};
class DBSCAN {
private:
std::vector<Point> points; // 数据集
double eps; // 邻域半径
int minPts; // 最小点数
int clusterCount; // 簇数量
public:
DBSCAN(std::vector<Point> data, double eps, int minPts)
: points(std::move(data)), eps(eps), minPts(minPts), clusterCount(0) {}
// 计算欧氏距离
double distance(const Point &a, const Point &b) {
return std::sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
// 查找邻域内点
std::vector<int> regionQuery(int idx) {
std::vector<int> neighbors;
for (int i = 0; i < (int)points.size(); ++i) {
if (distance(points[idx], points[i]) <= eps)
neighbors.push_back(i);
}
return neighbors;
}
// 扩展簇
void expandCluster(int idx, int clusterId, const std::vector<int>& neighborPts) {
points[idx].clusterId = clusterId;
std::vector<int> seeds = neighborPts;
for (size_t i = 0; i < seeds.size(); ++i) {
int curIdx = seeds[i];
if (!points[curIdx].visited) {
points[curIdx].visited = true;
auto newNeighbors = regionQuery(curIdx);
if ((int)newNeighbors.size() >= minPts) {
seeds.insert(seeds.end(), newNeighbors.begin(), newNeighbors.end());
}
}
if (points[curIdx].clusterId == 0)
points[curIdx].clusterId = clusterId;
}
}
// DBSCAN主流程
void run() {
for (int i = 0; i < (int)points.size(); ++i) {
if (points[i].visited) continue;
points[i].visited = true;
auto neighbors = regionQuery(i);
if ((int)neighbors.size() < minPts) {
points[i].clusterId = -1; // 噪声
} else {
clusterCount++;
expandCluster(i, clusterCount, neighbors);
}
}
}
// 输出聚类结果
void printResults() {
std::cout << "\n===== DBSCAN 聚类结果 =====\n";
std::cout << "簇数量: " << clusterCount << std::endl;
int noiseCount = 0;
for (auto &p : points) if (p.clusterId == -1) noiseCount++;
std::cout << "噪声点数量: " << noiseCount << std::endl;
std::cout << "\n点坐标与聚类编号:\n";
for (size_t i = 0; i < points.size(); ++i) {
std::cout << std::fixed << std::setprecision(2)
<< "点" << std::setw(3) << i << ": (" << points[i].x << "," << points[i].y
<< "), cluster=" << points[i].clusterId << "\n";
}
}
};
// ============ 主程序 ============ //
int main() {
std::vector<Point> data = {
{1.0, 1.0}, {1.2, 1.1}, {0.8, 1.0}, {1.1, 1.3},
{10.0, 10.0}, {10.2, 10.1}, {9.8, 9.9}, {10.1, 10.3},
{5.0, 5.0}, {5.2, 5.1}, {4.8, 5.0}, {5.0, 5.2}, {100,100}
};
double eps = 0.5;
int minPts = 3;
std::cout << "请输入邻域半径 eps (默认0.5): ";
std::cin >> eps;
std::cout << "请输入最小点数 minPts (默认3): ";
std::cin >> minPts;
DBSCAN db(data, eps, minPts);
db.run();
db.printResults();
return 0;
}
六、代码详细解读
-
struct Point：定义点结构，包含坐标与聚类状态； -
distance()：计算两点欧氏距离； -
regionQuery()：在给定半径eps内搜索邻居； -
expandCluster()：从核心点扩展新簇； -
run()：主算法逻辑； -
printResults()：输出聚类统计与每个点标签； -
main()：示例数据与用户交互。
七、项目详细总结
本项目通过 纯 C++ 实现 DBSCAN 算法，展现了以下关键能力：
-
完整理解基于密度的聚类思想；
-
使用 STL 容器实现核心算法；
-
可扩展、可复用的类设计；
-
结合数学模型与编程实现。
该程序支持自动识别多个聚类区域，并能有效识别噪声点。
从实验结果可观察：
-
稠密区域自动归为一类；
-
稀疏点被标记为噪声；
-
不需要预定义簇数。
八、项目常见问题及解答（FAQ）
Q1：为什么我的数据都成一个簇？
A1：eps 设置太大，所有点都在同一邻域中。
Q2：为什么全是噪声？
A2：eps 太小或 minPts 太大，导致没有核心点。
Q3：能否扩展到高维？
A3：完全可以，只需修改 distance() 以支持多维坐标。
Q4：算法复杂度太高？
A4：当前版本 O(n²)。可用 KD-Tree、BallTree 优化邻域查询。
Q5：如何可视化？
A5：将结果保存为 CSV，用 Python（matplotlib / seaborn）绘制。
九、扩展方向与性能优化
-
高维扩展：
-
改写
distance()支持vector<double>； -
用模板泛化维度。
-
-
性能优化：
-
使用 KD-Tree 加速邻域查询；
-
并行化邻域搜索（OpenMP）。
-
-
文件输入/输出：
-
支持从 CSV 文件加载；
-
输出聚类结果到文件。
-
-
可视化模块：
-
使用 SFML/Qt 绘制不同簇的点；
-
噪声点用灰色表示。
-
-
算法变种：
-
OPTICS：解决 DBSCAN 参数敏感问题；
-
HDBSCAN：自动推断层次密度结构。
-
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
47
0- 0
已为社区贡献220条内容
所有评论(0)