這幾天由于工作需要，對DBSCAN聚類算法進行了C++的實現。時間復雜度O(n^2)，主要花在算每個點領域內的點上。算法很簡單，現共享大家參考，也希望有更多交流。
數據點類型描述如下：
復制代碼 代碼如下:
#include
using namespace std;
const int DIME_NUM=2;??????? //數據維度為2，全局常量
//數據點類型
class DataPoint
{
private:
unsigned long dpID;??????????????? //數據點ID
double dimension[DIME_NUM];??????? //維度數據
long clusterId;??????????????????? //所屬聚類ID
bool isKey;??????????????????????? //是否核心對象
bool visited;??????????????????? //是否已訪問
vector arrivalPoints;??? //領域數據點id列表
public:
DataPoint();??????????????????????????????????????????????????? //默認構造函數
DataPoint(unsigned long dpID,double* dimension , bool isKey);??? //構造函數
unsigned long GetDpId();??????????????? //GetDpId方法
void SetDpId(unsigned long dpID);??????? //SetDpId方法
double* GetDimension();??????????????????? //GetDimension方法
void SetDimension(double* dimension);??? //SetDimension方法
bool IsKey();??????????????????????????? //GetIsKey方法
void SetKey(bool isKey);??????????????? //SetKey方法
bool isVisited();??????????????????????? //GetIsVisited方法
void SetVisited(bool visited);??????????? //SetIsVisited方法
long GetClusterId();??????????????????? //GetClusterId方法
void SetClusterId(long classId);??????? //SetClusterId方法
vector& GetArrivalPoints();??? //GetArrivalPoints方法
};
這是實現：
復制代碼 代碼如下:
#include "DataPoint.h"
//默認構造函數
DataPoint::DataPoint()
{
}
//構造函數
DataPoint::DataPoint(unsigned long dpID,double* dimension , bool isKey):isKey(isKey),dpID(dpID)
{
//傳遞每維的維度數據
for(int i=0; i
{
this->dimension[i]=dimension[i];
}
}
//設置維度數據
void DataPoint::SetDimension(double* dimension)
{
for(int i=0; i
{
this->dimension[i]=dimension[i];
}
}
//獲取維度數據
double* DataPoint::GetDimension()
{
return this->dimension;
}
//獲取是否為核心對象
bool DataPoint::IsKey()
{
return this->isKey;
}
//設置核心對象標志
void DataPoint::SetKey(bool isKey)
{
this->isKey = isKey;
}
//獲取DpId方法
unsigned long DataPoint::GetDpId()
{
return this->dpID;
}
//設置DpId方法
void DataPoint::SetDpId(unsigned long dpID)
{
this->dpID = dpID;
}
//GetIsVisited方法
bool DataPoint::isVisited()
{
return this->visited;
}
//SetIsVisited方法
void DataPoint::SetVisited( bool visited )
{
this->visited = visited;
}
//GetClusterId方法
long DataPoint::GetClusterId()
{
return this->clusterId;
}
//GetClusterId方法
void DataPoint::SetClusterId( long clusterId )
{
this->clusterId = clusterId;
}
//GetArrivalPoints方法
vector& DataPoint::GetArrivalPoints()
{
return arrivalPoints;
}
DBSCAN算法類型描述：
復制代碼 代碼如下:
#include
#include
using namespace std;
//聚類分析類型
class ClusterAnalysis
{
private:
vector dadaSets;??????? //數據集合
unsigned int dimNum;??????????? //維度
double radius;??????????????????? //半徑
unsigned int dataNum;??????????? //數據數量
unsigned int minPTs;??????????? //鄰域最小數據個數
double GetDistance(DataPoint& dp1, DataPoint& dp2);??????????????????? //距離函數
void SetArrivalPoints(DataPoint& dp);??????????????????????????????? //設置數據點的領域點列表
void KeyPointCluster( unsigned long i, unsigned long clusterId );??? //對數據點領域內的點執行聚類操作
public:
ClusterAnalysis(){}??????????????????? //默認構造函數
bool Init(char* fileName, double radius, int minPTs);??? //初始化操作
bool DoDBSCANRecursive();??????????? //DBSCAN遞歸算法
bool WriteToFile(char* fileName);??? //將聚類結果寫入文件
};
聚類實現：
復制代碼 代碼如下:
#include "ClusterAnalysis.h"
#include
#include
#include
/*
函數：聚類初始化操作
說明：將數據文件名，半徑，領域最小數據個數信息寫入聚類算法類，讀取文件，把數據信息讀入寫進算法類數據集合中
參數：
char* fileName;??? //文件名
double radius;??? //半徑
int minPTs;??????? //領域最小數據個數
返回值： true;??? */
bool ClusterAnalysis::Init(char* fileName, double radius, int minPTs)
{
this->radius = radius;??????? //設置半徑
this->minPTs = minPTs;??????? //設置領域最小數據個數
this->dimNum = DIME_NUM;??? //設置數據維度
ifstream ifs(fileName);??????? //打開文件
if (! ifs.is_open())??????????????? //若文件已經被打開，報錯誤信息
{
cout << "Error opening file";??? //輸出錯誤信息
exit (-1);??????????????????????? //程序退出
}
unsigned long i=0;??????????? //數據個數統計
while (! ifs.eof() )??????????????? //從文件中讀取POI信息，將POI信息寫入POI列表中
{
DataPoint tempDP;??????????????? //臨時數據點對象
double tempDimData[DIME_NUM];??? //臨時數據點維度信息
for(int j=0; j
{
ifs>>tempDimData[j];
}
tempDP.SetDimension(tempDimData);??? //將維度信息存入數據點對象內
//char date[20]="";
//char time[20]="";
double type;??? //無用信息
//ifs >> date;
//ifs >> time;??? //無用信息讀入
tempDP.SetDpId(i);??????????????????? //將數據點對象ID設置為i
tempDP.SetVisited(false);??????????? //數據點對象isVisited設置為false
tempDP.SetClusterId(-1);??????????? //設置默認簇ID為-1
dadaSets.push_back(tempDP);??????????? //將對象壓入數據集合容器
i++;??????? //計數+1
}
ifs.close();??????? //關閉文件流
dataNum =i;??????????? //設置數據對象集合大小為i
for(unsigned long i=0; i
{
SetArrivalPoints(dadaSets[i]);??????????? //計算數據點領域內對象
}
return true;??? //返回
}
/*
函數：將已經過聚類算法處理的數據集合寫回文件
說明：將已經過聚類結果寫回文件
參數：
char* fileName;??? //要寫入的文件名
返回值： true??? */
bool ClusterAnalysis::WriteToFile(char* fileName )
{
ofstream of1(fileName);??????????????????????????????? //初始化文件輸出流
for(unsigned long i=0; i
{
for(int d=0; d
of1<
of1 << dadaSets[i].GetClusterId() <
}
of1.close();??? //關閉輸出文件流
return true;??? //返回
}
/*
函數：設置數據點的領域點列表
說明：設置數據點的領域點列表
參數：
返回值： true;??? */
void ClusterAnalysis::SetArrivalPoints(DataPoint& dp)
{
for(unsigned long i=0; i
{
double distance =GetDistance(dadaSets[i], dp);??? //獲取與特定點之間的距離
if(distance <= radius && i!=dp.GetDpId())??????? //若距離小于半徑，并且特定點的id與dp的id不同執行
dp.GetArrivalPoints().push_back(i);??????????? //將特定點id壓力dp的領域列表中
}
if(dp.GetArrivalPoints().size() >= minPTs)??????????? //若dp領域內數據點數據量> minPTs執行
{
dp.SetKey(true);??? //將dp核心對象標志位設為true
return;??????????????? //返回
}
dp.SetKey(false);??? //若非核心對象，則將dp核心對象標志位設為false
}
/*
函數：執行聚類操作
說明：執行聚類操作
參數：
返回值： true;??? */
bool ClusterAnalysis::DoDBSCANRecursive()
{
unsigned long clusterId=0;??????????????????????? //聚類id計數，初始化為0
for(unsigned long i=0; i
{
DataPoint& dp=dadaSets[i];??????????????????? //取到第i個數據點對象
if(!dp.isVisited() && dp.IsKey())??????????? //若對象沒被訪問過，并且是核心對象執行
{
dp.SetClusterId(clusterId);??????????????? //設置該對象所屬簇ID為clusterId
dp.SetVisited(true);??????????????????? //設置該對象已被訪問過
KeyPointCluster(i,clusterId);??????????? //對該對象領域內點進行聚類
clusterId++;??????????????????????????? //clusterId自增1
}
//cout << "孤立點\T" << i << endl;
}
cout <
return true;??? //返回
}
/*
函數：對數據點領域內的點執行聚類操作
說明：采用遞歸的方法，深度優先聚類數據
參數：
unsigned long dpID;??????????? //數據點id
unsigned long clusterId;??? //數據點所屬簇id
返回值： void;??? */
void ClusterAnalysis::KeyPointCluster(unsigned long dpID, unsigned long clusterId )
{
DataPoint& srcDp = dadaSets[dpID];??????? //獲取數據點對象
if(!srcDp.IsKey())??? return;
vector& arrvalPoints = srcDp.GetArrivalPoints();??????? //獲取對象領域內點ID列表
for(unsigned long i=0; i
{
DataPoint& desDp = dadaSets[arrvalPoints[i]];??? //獲取領域內點數據點
if(!desDp.isVisited())??????????????????????????? //若該對象沒有被訪問過執行
{
//cout << "數據點\t"<< desDp.GetDpId()<
desDp.SetClusterId(clusterId);??????? //設置該對象所屬簇的ID為clusterId，即將該對象吸入簇中
desDp.SetVisited(true);??????????????? //設置該對象已被訪問
if(desDp.IsKey())??????????????????? //若該對象是核心對象
{
KeyPointCluster(desDp.GetDpId(),clusterId);??? //遞歸地對該領域點數據的領域內的點執行聚類操作，采用深度優先方法
}
}
}
}
//兩數據點之間距離
/*
函數：獲取兩數據點之間距離
說明：獲取兩數據點之間的歐式距離
參數：
DataPoint& dp1;??????? //數據點1
DataPoint& dp2;??????? //數據點2
返回值： double;??? //兩點之間的距離??????? */
double ClusterAnalysis::GetDistance(DataPoint& dp1, DataPoint& dp2)
{
double distance =0;??????? //初始化距離為0
for(int i=0; i
{
distance += pow(dp1.GetDimension()[i] - dp2.GetDimension()[i],2);??? //距離+每一維差的平方
}
return pow(distance,0.5);??????? //開方并返回距離
}
算法調用就簡單了：
復制代碼 代碼如下:
#include "ClusterAnalysis.h"
#include
using namespace std;
int main()
{
ClusterAnalysis myClusterAnalysis;??????????????????????? //聚類算法對象聲明
myClusterAnalysis.Init("D:\\1108\\XY.txt",500,9);??????? //算法初始化操作，指定半徑為15，領域內最小數據點個數為3，(在程序中已指定數據維度為2)
myClusterAnalysis.DoDBSCANRecursive();??????????????????? //執行聚類算法
myClusterAnalysis.WriteToFile("D:\\1108\\XYResult.txt");//寫執行后的結果寫入文件
system("pause");??? //顯示結果
return 0;??????????? //返回
}
