C++实现DBSCAN密度聚类算法

一、基本概念

可以用1，2，3，4来总结DBSCAN的基本概念。

1个核心思想：基于密度

直观效果上看，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当做一个一个的聚类簇。

2个算法参数：邻域半径R和最少点数目minpoints

这两个算法参数实际可以刻画什么叫密集——当邻域半径R内的点的个数大于最少点数目minpoints时，就是密集。

3种点的类别：核心点，边界点和噪声点

邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点。

4种关系：密度直达，密度可达，密度相连，非密度相连

如果P为核心点，Q在P的R邻域内，那么称P到Q密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果P到Q密度直达，那么Q到P不一定密度直达。

如果存在核心点P2，P3，……，Pn，且P1到P2密度直达，P2到P3密度直达，……，P(n-1)到Pn密度直达，Pn到Q密度直达，则P1到Q密度可达。密度可达也不具有对称性。

如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。

如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

二、算法描述

DBSCAN 算法对簇的定义很简单，由密度可达关系导出的最大密度相连的样本集合，即为最终聚类的一个簇。

DBSCAN 算法的簇里面可以有一个或者多个核心点。如果只有一个核心点，则簇里其他的非核心点样本都在这个核心点的 Eps 邻域里。如果有多个核心点，则簇里的任意一个核心点的 Eps 邻域中一定有一个其他的核心点，否则这两个核心点无法密度可达。这些核心点的 Eps 邻域里所有的样本的集合组成一个 DBSCAN 聚类簇。

DBSCAN算法的描述如下。

输入：数据集，邻域半径 Eps，邻域中数据对象数目阈值 MinPts;
输出：密度联通簇。
处理流程如下。

1）从数据集中任意选取一个数据对象点 p；

2）如果对于参数 Eps 和 MinPts，所选取的数据对象点 p 为核心点，则找出所有从 p 密度可达的数据对象点，形成一个簇；

3）如果选取的数据对象点 p 是边缘点，选取另一个数据对象点；

4）重复（2）、（3）步，直到所有点被处理。

DBSCAN 算法的计算复杂的度为 O(n²)，n 为数据对象的数目。这种算法对于输入参数 Eps 和 MinPts 是敏感的。

代码实现逻辑如下：

1）计算每个point的eps范围内的point数量pts；

2）对于所有pts >Minpts的point，记为Core point；

3）对于所有的corepoint，将其eps范围内的core point下标添加到vector集合（vector neighborCoreIdx）中；

4）遍历所有的corepoint，采用深度优先的方式遍历它的neighborCoreIdx集合，使得相互连接的core point具有相同的cluster编号；

5）对所有pts < Minpts且在Core point 范围内的点，记为Borderpoint；

若某个Borderpoint点在某个Core point的eps范围内，则让该Borderpoint点的cluster编号等于这个Core point的cluster编号；

6）剩余的point的为Noise point；

程序结束。

三、代码实现

看了几个其他博客的代码，但是感觉很乱，有的运行出错，或者是展示效果差。本人自己整理了一份可以使用和展示的代码，运行无误！加了很多帮助理解的注释，浅显易懂！

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//为了便于可视化展示算法效果，引入OpenCV库。
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/core/core.hpp"
#include "opencv2/imgproc/imgproc.hpp"
using namespace cv;


enum ESampleType
{
	NOISE = 1,
	BORDER = 2,
	CORE = 3,
};

struct point
{
public:
	float x;
	float y;
	int cluster = 0; //所属类别（一个标识代号，属于同一类的样本具有相同的cluster）

	//邻域半径R内样本点的数量大于等于minpoints的点叫做核心点。
	//不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点
	int pointType = NOISE;		 // 1:noise 	2:border 	3:core  （初始默认为噪声点）
	int pts = 0;				 //points in MinPts （指定领域内样本点的个数）
	vector neighborCoreIdx; //对所有的corepoint，将其eps范围内的core point下标添加到vector neighborCoreIdx中
	int visited = 0;			 //是否被遍历访问过

	point()
	{
	}
	point(float a, float b)
	{
		x = a;
		y = b;
		//cluster = c;
	}
};

float stringToFloat(string i)
{
	stringstream sf;
	float score = 0;
	sf << i;
	sf >> score;
	return score;
}

//读取文本文件，从中解析出数据。
vector openFile(const char *dataset)
{
	fstream file;
	file.open(dataset, ios::in);
	if (!file)
	{
		cout << "Open File Failed!" << endl;
		vector a;
		return a;
	}

	vector data;
	int i = 1;

	while (!file.eof())
	{
		string temp;
		file >> temp;
		int split = temp.find(',', 0);
		point p(stringToFloat(temp.substr(0, split)), stringToFloat(temp.substr(split + 1, temp.length() - 1)));
		data.push_back(p);
	}

	file.close();
	cout << "successful!" << endl;
	return data;
}

//计算平面内两点之间的距离
float squareDistance(point a, point b)
{
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}


void DBSCAN(vector &dataset, float Eps, int MinPts)
{
	int count = 0;
	int len = dataset.size();
	//calculate pts
	cout << "计算各点的邻域数量" << endl;

	for (int i = 0; i < len; i++)
	{
		//特别注意 !!! 这里如果j从i开始，表明某点的邻域范围内样本数量包含自己，若j从i+1开始则不包含自己。
		for (int j = i; j < len; j++)
		{
			if (squareDistance(dataset[i], dataset[j]) < Eps)
			{
				dataset[i].pts++;
				dataset[j].pts++;
			}
		}
	}

	//core point ，若某个点在其领域Eps范围内的点个数>=MinPts，称该点为core point核心点
	cout << "寻找核心点" << endl;
	//核心点集合索引（索引为样本点原本的索引，从0开始）
	vector corePtInxVec;
	for (int i = 0; i < len; i++)
	{
		if (dataset[i].pts >= MinPts)
		{
			dataset[i].pointType = CORE;
			dataset[i].cluster = (++count);
			corePtInxVec.push_back(i);
			printf("样本(%.1f, %.1f)的邻域点数量为:%d,被确立为核心点, cluster：%dn", dataset[i].x, dataset[i].y, dataset[i].pts, dataset[i].cluster);
		}
	}

	//合并core point
	cout << "合并核心点" << endl;
	for (int i = 0; i < corePtInxVec.size(); i++)
	{
		for (int j = i + 1; j < corePtInxVec.size(); j++)
		{
			//对所有的corepoint，将其eps范围内的core point下标添加到vector corepts中
			if (squareDistance(dataset[corePtInxVec[i]], dataset[corePtInxVec[j]]) < Eps)
			{
				dataset[corePtInxVec[i]].neighborCoreIdx.push_back(corePtInxVec[j]);
				dataset[corePtInxVec[j]].neighborCoreIdx.push_back(corePtInxVec[i]);

				printf("核心点%.1f, %.1f)与核心点%.1f, %.1f)处在半径范围内，相互连接，可以合并n",
					   dataset[corePtInxVec[i]].x, dataset[corePtInxVec[i]].y, dataset[corePtInxVec[j]].x, dataset[corePtInxVec[j]].y);
			}
		}
	}

	//对于所有的corepoint，采用深度优先的方式遍历每个core point的所有corepts，使得相互连接的core point具有相同的cluster编号
	for (int i = 0; i < corePtInxVec.size(); i++)
	{
		for (int j = 0; j < dataset[corePtInxVec[i]].neighborCoreIdx.size(); j++)
		{
			int idx = dataset[corePtInxVec[i]].neighborCoreIdx[j];
			dataset[idx].cluster = dataset[corePtInxVec[i]].cluster;
		}
	}

	//不属于核心点但在某个核心点的邻域内的点叫做边界点
	cout << "边界点，把边界点加入到靠近的核心点" << endl;
	//border point,joint border point to core point
	for (int i = 0; i < len; i++)
	{
		if (dataset[i].pointType == CORE) //忽略核心点
			continue;

		for (int j = 0; j < corePtInxVec.size(); j++)
		{
			int idx = corePtInxVec[j]; //核心点索引
			if (squareDistance(dataset[i], dataset[idx]) < Eps)
			{
				dataset[i].pointType = BORDER;
				dataset[i].cluster = dataset[idx].cluster;
				printf("样本(%.1f, %.1f)被确立为边界点, cluster：%dn", dataset[i].x, dataset[i].y, dataset[i].cluster);
				break;
			}
		}
	}

	cout << "输出结果：" << endl;
	for (int i = 0; i < len; i++)
	{
		if (dataset[i].pointType == CORE)
		{
			printf("CORE: x:%.2f, y:%.2f cluster:%dn", dataset[i].x, dataset[i].y, dataset[i].cluster);
		}
		else if (dataset[i].pointType == BORDER)
		{
			printf("BORDER: x:%.2f, y:%.2f cluster:%dn", dataset[i].x, dataset[i].y, dataset[i].cluster);
		}
		else
		{
			printf("NOISE: x:%.2f, y:%.2f cluster:%dn", dataset[i].x, dataset[i].y, dataset[i].cluster);
		}
	}

	// for(int i=0;i < corePoint.size(); i++)
	// {
	// 		clustering<> 8) & 0xFF, (icolor >> 16) & 0xFF);
}

int main(int argc, char **argv)
{
	//加载数据
	vector dataset = openFile("dataset.txt");
	float radius = 2.0; //邻域半径R
	int MinPts = 2;		//邻域半径R内样本点的数量大于等于minpoints的点叫做核心点
	//DBSCAN算法进行聚类
	DBSCAN(dataset, radius, MinPts);

	//设置了6种不同的颜色
	const int colorCnts = 6;
	cv::Scalar colors[] = {cv::Scalar(255, 100, 80), cv::Scalar(0, 255, 0), cv::Scalar(0, 0, 255),
						   cv::Scalar(0, 255, 255), cv::Scalar(255, 0, 255), cv::Scalar(255, 255, 0)};

	//画出原始数据分布图
	cv::Point offset(10, 10); //所有样本均加上这个偏移、防止离原点太近影响视觉显示效果
	cv::Mat originalMat = cv::Mat::zeros(cv::Size(300, 300), CV_8UC3);
	for (size_t i = 0; i < dataset.size(); i++)
	{
		cv::Point pt = offset + cv::Point(dataset[i].x * 10, dataset[i].y * 10);
		cv::circle(originalMat, pt, 2, cv::Scalar(0, 0, 255), 2);
	}
	cv::imshow("original data", originalMat);

	//画出结果示意图,不同的cluster样本点用不同的颜色表示。
	map clusterMap;
	map::iterator it;

	cv::Mat resultMat = cv::Mat::zeros(cv::Size(300, 300), CV_8UC3);
	cv::Scalar color;
	for (size_t i = 0; i < dataset.size(); i++)
	{
		it = clusterMap.find(dataset[i].cluster);
		if (it == clusterMap.end()) //首次出现，为该cluster随机分配一组颜色。
		{
			color = random_color();
			clusterMap.insert(std::make_pair(dataset[i].cluster, color));
		}
		else
			color = it->second;

		cv::Point pt = offset + cv::Point(dataset[i].x * 10, dataset[i].y * 10);
		cv::circle(resultMat, pt, 2, color, 2);
	}
	cv::imshow("cluster data", resultMat);

	cv::waitKey(0);
	getchar();
	return 0;
}

附程序所使用的dataset.txt文件：

0,0
3,8
2,2
1,1
5,3
4,8
6,3
5,4
6,4
7,5
12,4
12,5
12,6
13,4
17,8
18,9

四、代码运行效果

五、参考资料

鸣谢：

聚类算法-DBSCAN-C++实现_k76853的专栏-CSDN博客_c++ dbscan

DBSCAN详解_hansome_hong的博客-CSDN博客_dbscan

C++实现DBSCAN密度聚类算法

C/C++/C#相关栏目本月热门文章