#include <vector>

?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<unsigned long> 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<unsigned long>& 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<DIME_NUM;i++)
???? {
???????? this->dimension[i]=dimension[i];
???? }
?}

?//設置維度數據
?void DataPoint::SetDimension(double* dimension)
?{
???? for(int i=0; i<DIME_NUM;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<unsigned long>& DataPoint::GetArrivalPoints()
?{
???? return arrivalPoints;
?}

#include <iostream>
?#include <cmath>

?using namespace std;

?//聚類分析類型
?class ClusterAnalysis
?{
?private:
???? vector<DataPoint> 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 <fstream>
?#include <iosfwd>
?#include <math.h>

?/*
?函數：聚類初始化操作
?說明：將數據文件名，半徑，領域最小數據個數信息寫入聚類算法類，讀取文件，把數據信息讀入寫進算法類數據集合中
?參數：
?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<DIME_NUM; 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<dataNum;i++)
???? {
???????? SetArrivalPoints(dadaSets[i]);??????????? //計算數據點領域內對象
???? }
???? return true;??? //返回
?}

?/*
?函數：將已經過聚類算法處理的數據集合寫回文件
?說明：將已經過聚類結果寫回文件
?參數：
?char* fileName;??? //要寫入的文件名
?返回值： true??? */
?bool ClusterAnalysis::WriteToFile(char* fileName )
?{
???? ofstream of1(fileName);??????????????????????????????? //初始化文件輸出流
???? for(unsigned long i=0; i<dataNum;i++)??????????????? //對處理過的每個數據點寫入文件
???? {
???????? for(int d=0; d<DIME_NUM ; d++)??????????????????? //將維度信息寫入文件
???????????? of1<<dadaSets[i].GetDimension()[d]<<'/t';
???????? of1 << dadaSets[i].GetClusterId() <<endl;??????? //將所屬簇ID寫入文件
???? }
???? of1.close();??? //關閉輸出文件流
???? return true;??? //返回
?}

?/*
?函數：設置數據點的領域點列表
?說明：設置數據點的領域點列表
?參數：
?返回值： true;??? */
?void ClusterAnalysis::SetArrivalPoints(DataPoint& dp)
?{
???? for(unsigned long i=0; i<dataNum; 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<dataNum;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 <<"共聚類" <<clusterId<<"個"<< endl;??????? //算法完成后，輸出聚類個數
???? 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<unsigned long>& arrvalPoints = srcDp.GetArrivalPoints();??????? //獲取對象領域內點ID列表
???? for(unsigned long i=0; i<arrvalPoints.size(); i++)
???? {
???????? DataPoint& desDp = dadaSets[arrvalPoints[i]];??? //獲取領域內點數據點
???????? if(!desDp.isVisited())??????????????????????????? //若該對象沒有被訪問過執行
???????? {
???????????? //cout << "數據點/t"<< desDp.GetDpId()<<"聚類ID為/t" <<clusterId << endl;
???????????? 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<DIME_NUM;i++)??? //對數據每一維數據執行
???? {
???????? distance += pow(dp1.GetDimension()[i] - dp2.GetDimension()[i],2);??? //距離+每一維差的平方
???? }
???? return pow(distance,0.5);??????? //開方并返回距離
?}

#include "ClusterAnalysis.h"
?#include <cstdio>

?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;??????????? //返回
?}