數據挖掘演算法：DBSCAN演算法的C++實現

(期末考試快到了，所以比較粗糙，請各位讀者理解。。)

一、    概念

DBSCAN是一種產生劃分聚類的基於密度的聚類演算法，簇的個數由演算法自動地確定。低密度區域中的點被視為雜訊而忽略，因此DBSCAN不產生完全聚類。

二、    偽代碼

1    將所有點標記為核心點、邊界點和雜訊點。

2    刪除雜訊點。

3    為距離在Eps之內的所有核心點之間賦予一條邊。

4    每組連通的核心點形成一個簇。

5    將每個邊界點指派到一個與之關聯的核心點的簇中。

三、    重要數據結構

1    定義鄰域半徑值、密度閾值、數據集點數

#define Eps 3 // Eps為鄰域半徑值

#define MinPts 3  // 鄰域密度閾值

#define N 20  // 數據集包含N個對象

2    定義數組保存所有點

double point[N][2];      // 保存所有的數據點

3    定義vector保存核心點、邊界點、雜訊點的位置

vector<int> kernel_point;   // 保存核心點在point[][]中的位置

vector<int> border_point;   // 保存邊界點在point[][]中的位置

vector<int> noise_point; // 保存雜訊點在point[][]中的位置

4    定義vector保存最終形成的簇

vector<vector<int> > cluster;   // 保存最終形成的簇，每個簇中包含點在point[][]中的位置

四、    源代碼

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>

using namespace std;

#define Eps 3 // Eps為鄰域半徑值
#define MinPts 3 // 鄰域密度閾值
#define N 20 // 數據集包含N個對象

double point[N][2]; // 保存所有的數據點
vector<int> kernel_point; // 保存核心點在point[][]中的位置
vector<int> border_point; // 保存邊界點在point[][]中的位置
vector<int> noise_point; // 保存雜訊點在point[][]中的位置
vector<vector<int> > mid; // 可能存在重疊的簇
vector<vector<int> > cluster; // 保存最終形成的簇，每個簇中包含點在point[][]中的位置

// 初始化N個坐標點
void init(int n) {
srand((unsigned)time(NULL));
for(int i=0; i<n; i++) {
for(int j=0; j<2; j++) {
point[i][j] = rand() % (N+1);
}
}
}

int main(int argc, char** argv) {

// 初始化數據集
int n = N;
init(n);

// 將所有點標記為核心點、邊界點或雜訊點
// 標記核心點
for(int i=0; i<N; i++) {
int num = 0; // 判斷是否超過MinPts，若一次迴圈後num>=MinPts，則加入核心點
for(int j=0; j<N; j++) {
if(pow(point[i][0]-point[j][0], 2)+pow(point[i][1]-point[j][1], 2)<=pow(Eps, 2)) { // 本身也算一個
num++;
}
}
if(num>=MinPts) {
kernel_point.push_back(i);
}
}

// 標記為邊界點或雜訊點
for(int i=0; i<N; i++) {
// 邊界點或雜訊點不能是核心點
int flag = 0; // 若flag=0，則該點不是核心點，若flag=1，則該點為核心點
for(int j=0; j<kernel_point.size(); j++) {
if(i == kernel_point[j]) {
flag = 1;
break;
}
}
if(flag == 0) {
// 判斷是邊界點還是雜訊點
int flag2 = 0; // 若flag=0，則該點為邊界點，若flag=1，則該點位雜訊點
for(int j=0; j<kernel_point.size(); j++) {
int s = kernel_point[j]; // 標記第j個核心點在point[][]中的位置，方便調用
if(pow(point[i][0]-point[s][0], 2)+pow(point[i][1]-point[s][1], 2)<pow(Eps, 2)) {
flag2 = 0;
border_point.push_back(i);
break;
}
else {
flag2 = 1;
continue;
}
}
if(flag2 == 1) {
// 加入雜訊點
noise_point.push_back(i);
continue;
}
}
else {
continue;
}
}

// 將距離在Eps之內的核心點放在一個vector中
for(int i=0; i<kernel_point.size(); i++) {
int x = kernel_point[i];
vector<int> record; // 對於每一個點建立一個record，放入mid當中
record.push_back(x);
for(int j=i+1; j<kernel_point.size(); j++) {
int y = kernel_point[j];
if(pow(point[x][0]-point[y][0], 2)-pow(point[x][1]-point[y][1], 2)<pow(Eps, 2)) {
record.push_back(y);
}
}
mid.push_back(record);
}

// 合併vector
for(int i=0; i<mid.size(); i++) { // 對於mid中的每一行
// 判斷該行是否已經添加進前面的某一行中
if(mid[i][0] == -1) {
continue;
}
// 如果沒有被判斷過
for(int j=0; j<mid[i].size(); j++) { // 判斷其中的每一個值
// 對每一個值判斷其他行中是否存在
for(int x=i+1; x<mid.size(); x++) { // 對於之後的每一行
if(mid[x][0] == -1) {
continue;
}
for(int y=0; y<mid[x].size(); y++) {
if(mid[i][j] == mid[x][y]) {
// 如果有一樣的元素，應該放入一個vector中，併在迴圈後加入precluster，同時置該vector內所有元素值為-1
for(int a=0; a<mid[x].size(); a++) {
mid[i].push_back(mid[x][a]);
mid[x][a] = -1;
}
break;
}
}
}
}

cluster.push_back(mid[i]);

}

// 刪除cluster中的重覆元素
for(int i=0; i<cluster.size(); i++) { // 對於每一行
for(int j=0; j<cluster[i].size(); j++) {
for(int n=j+1; n<cluster[i].size(); n++) {
if(cluster[i][j] == cluster[i][n]) {
cluster[i].erase(cluster[i].begin()+n);
n--;
}
}
}
}

// 至此，cluster中保存了各個簇，每個簇中有點對應在point[][]中的位置
// 將每個邊界點指派到一個與之相關聯的核心點的簇中
for(int i=0; i<border_point.size(); i++) { // 對於每一個邊界點
int x = border_point[i];
for(int j=0; j<cluster.size(); j++) { // 檢查每一個簇，判斷邊界點與哪個簇中的核心點關聯，將邊界點加入到第一個核心點出現的簇中
int flag = 0; // flag=0表示沒有匹配的項，flag=1表示已經匹配，退出迴圈
for(int k=0; k<cluster[j].size(); k++) {
int y = cluster[j][k];
if(pow(point[x][0]-point[y][0], 2)+pow(point[x][1]-point[y][1], 2)<pow(Eps, 2)) {
cluster[j].push_back(x);
flag = 1;
break;
}
}
if(flag == 1) {
break;
}
}
}


/*******************************************************************************************/
cout<<"All Points : "<<endl;
for(int i=0; i<N; i++) {
cout<<"第"<<i<<"個"<<"\t";
for(int j=0; j<2; j++) {
cout<<point[i][j]<<"\t";
}
cout<<endl;
}
cout<<endl;

cout<<"Kernel Points : "<<endl;
for(int i=0; i<kernel_point.size(); i++) {
cout<<kernel_point[i]<<"\t";
}
cout<<endl<<endl;

cout<<"Border Points : "<<endl;
for(int i=0; i<border_point.size(); i++) {
cout<<border_point[i]<<"\t";
}
cout<<endl<<endl;

cout<<"Noise Points : "<<endl;
for(int i=0; i<noise_point.size(); i++) {
cout<<noise_point[i]<<"\t";
}
cout<<endl<<endl;

cout<<"Cluster : "<<endl;
for(int i=0; i<cluster.size(); i++) {
cout<<"第"<<i<<"個"<<"\t";
for(int j=0; j<cluster[i].size(); j++) {
cout<<cluster[i][j]<<"\t";
}
cout<<endl;
}

return 0;
}

五、    運行結果

圖1 DBSCAN演算法的運行結果

圖2 利用Graph作圖展示DBSCAN演算法運行結果

（其中，粉色點為雜訊點，藍色與黃色為兩個簇）