国产精品动漫视频网站,成人免费黄网站,黄片毛片视频

這幾天由于工作需要，對(duì)DBSCAN聚類(lèi)算法進(jìn)行了C++的實(shí)現(xiàn)。時(shí)間復(fù)雜度O(n^2)，主要花在算每個(gè)點(diǎn)領(lǐng)域內(nèi)的點(diǎn)上。算法很簡(jiǎn)單，現(xiàn)共享大家參考，也希望有更多交流。
數(shù)據(jù)點(diǎn)類(lèi)型描述如下：

復(fù)制代碼代碼如下:

#include <vector>

using namespace std;

const int DIME_NUM=2;        //數(shù)據(jù)維度為2，全局常量

//數(shù)據(jù)點(diǎn)類(lèi)型
class DataPoint
{
private:
     unsigned long dpID;                //數(shù)據(jù)點(diǎn)ID
     double dimension[DIME_NUM];        //維度數(shù)據(jù)
     long clusterId;                    //所屬聚類(lèi)ID
     bool isKey;                        //是否核心對(duì)象
     bool visited;                    //是否已訪問(wèn)
     vector<unsigned long> arrivalPoints;    //領(lǐng)域數(shù)據(jù)點(diǎn)id列表
public:
     DataPoint();                                                    //默認(rèn)構(gòu)造函數(shù)
     DataPoint(unsigned long dpID,double* dimension , bool isKey);    //構(gòu)造函數(shù)

     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方法
};

這是實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

#include "DataPoint.h"

//默認(rèn)構(gòu)造函數(shù)
DataPoint::DataPoint()
{
}

//構(gòu)造函數(shù)
DataPoint::DataPoint(unsigned long dpID,double* dimension , bool isKey):isKey(isKey),dpID(dpID)
{
     //傳遞每維的維度數(shù)據(jù)
     for(int i=0; i<DIME_NUM;i++)
     {
         this->dimension[i]=dimension[i];
     }
}

//設(shè)置維度數(shù)據(jù)
void DataPoint::SetDimension(double* dimension)
{
     for(int i=0; i<DIME_NUM;i++)
     {
         this->dimension[i]=dimension[i];
     }
}

//獲取維度數(shù)據(jù)
double* DataPoint::GetDimension()
{
     return this->dimension;
}

//獲取是否為核心對(duì)象
bool DataPoint::IsKey()
{
     return this->isKey;
}

//設(shè)置核心對(duì)象標(biāo)志
void DataPoint::SetKey(bool isKey)
{
     this->isKey = isKey;
}

//獲取DpId方法
unsigned long DataPoint::GetDpId()
{
     return this->dpID;
}

//設(shè)置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;
}

DBSCAN算法類(lèi)型描述：

復(fù)制代碼代碼如下:

#include <iostream>
#include <cmath>

using namespace std;

//聚類(lèi)分析類(lèi)型
class ClusterAnalysis
{
private:
     vector<DataPoint> dadaSets;        //數(shù)據(jù)集合
     unsigned int dimNum;            //維度
     double radius;                    //半徑
     unsigned int dataNum;            //數(shù)據(jù)數(shù)量
     unsigned int minPTs;            //鄰域最小數(shù)據(jù)個(gè)數(shù)

     double GetDistance(DataPoint& dp1, DataPoint& dp2);                    //距離函數(shù)
     void SetArrivalPoints(DataPoint& dp);                                //設(shè)置數(shù)據(jù)點(diǎn)的領(lǐng)域點(diǎn)列表
     void KeyPointCluster( unsigned long i, unsigned long clusterId );    //對(duì)數(shù)據(jù)點(diǎn)領(lǐng)域內(nèi)的點(diǎn)執(zhí)行聚類(lèi)操作
public:

     ClusterAnalysis(){}                    //默認(rèn)構(gòu)造函數(shù)
     bool Init(char* fileName, double radius, int minPTs);    //初始化操作
     bool DoDBSCANRecursive();            //DBSCAN遞歸算法
     bool WriteToFile(char* fileName);    //將聚類(lèi)結(jié)果寫(xiě)入文件
};

聚類(lèi)實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

#include "ClusterAnalysis.h"
#include <fstream>
#include <iosfwd>
#include <math.h>

/*
函數(shù)：聚類(lèi)初始化操作
說(shuō)明：將數(shù)據(jù)文件名，半徑，領(lǐng)域最小數(shù)據(jù)個(gè)數(shù)信息寫(xiě)入聚類(lèi)算法類(lèi)，讀取文件，把數(shù)據(jù)信息讀入寫(xiě)進(jìn)算法類(lèi)數(shù)據(jù)集合中
參數(shù)：
char* fileName;    //文件名
double radius;    //半徑
int minPTs;        //領(lǐng)域最小數(shù)據(jù)個(gè)數(shù)
返回值： true;    */
bool ClusterAnalysis::Init(char* fileName, double radius, int minPTs)
{
     this->radius = radius;        //設(shè)置半徑
     this->minPTs = minPTs;        //設(shè)置領(lǐng)域最小數(shù)據(jù)個(gè)數(shù)
     this->dimNum = DIME_NUM;    //設(shè)置數(shù)據(jù)維度
     ifstream ifs(fileName);        //打開(kāi)文件
     if (! ifs.is_open())                //若文件已經(jīng)被打開(kāi)，報(bào)錯(cuò)誤信息
     {
         cout << "Error opening file";    //輸出錯(cuò)誤信息
         exit (-1);                        //程序退出
     }

     unsigned long i=0;            //數(shù)據(jù)個(gè)數(shù)統(tǒng)計(jì)
     while (! ifs.eof() )                //從文件中讀取POI信息，將POI信息寫(xiě)入POI列表中
     {
         DataPoint tempDP;                //臨時(shí)數(shù)據(jù)點(diǎn)對(duì)象
         double tempDimData[DIME_NUM];    //臨時(shí)數(shù)據(jù)點(diǎn)維度信息
         for(int j=0; j<DIME_NUM; j++)    //讀文件，讀取每一維數(shù)據(jù)
         {
             ifs>>tempDimData[j];
         }
         tempDP.SetDimension(tempDimData);    //將維度信息存入數(shù)據(jù)點(diǎn)對(duì)象內(nèi)

//char date[20]="";
//char time[20]="";
         ////double type;    //無(wú)用信息
         //ifs >> date;
//ifs >> time;    //無(wú)用信息讀入

         tempDP.SetDpId(i);                    //將數(shù)據(jù)點(diǎn)對(duì)象ID設(shè)置為i
         tempDP.SetVisited(false);            //數(shù)據(jù)點(diǎn)對(duì)象isVisited設(shè)置為false
         tempDP.SetClusterId(-1);            //設(shè)置默認(rèn)簇ID為-1
         dadaSets.push_back(tempDP);            //將對(duì)象壓入數(shù)據(jù)集合容器
         i++;        //計(jì)數(shù)+1
     }
     ifs.close();        //關(guān)閉文件流
     dataNum =i;            //設(shè)置數(shù)據(jù)對(duì)象集合大小為i
     for(unsigned long i=0; i<dataNum;i++)
     {
         SetArrivalPoints(dadaSets[i]);            //計(jì)算數(shù)據(jù)點(diǎn)領(lǐng)域內(nèi)對(duì)象
     }
     return true;    //返回
}

/*
函數(shù)：將已經(jīng)過(guò)聚類(lèi)算法處理的數(shù)據(jù)集合寫(xiě)回文件
說(shuō)明：將已經(jīng)過(guò)聚類(lèi)結(jié)果寫(xiě)回文件
參數(shù)：
char* fileName;    //要寫(xiě)入的文件名
返回值： true    */
bool ClusterAnalysis::WriteToFile(char* fileName )
{
     ofstream of1(fileName);                                //初始化文件輸出流
     for(unsigned long i=0; i<dataNum;i++)                //對(duì)處理過(guò)的每個(gè)數(shù)據(jù)點(diǎn)寫(xiě)入文件
     {
         for(int d=0; d<DIME_NUM ; d++)                    //將維度信息寫(xiě)入文件
             of1<<dadaSets[i].GetDimension()[d]<<'\t';
         of1 << dadaSets[i].GetClusterId() <<endl;        //將所屬簇ID寫(xiě)入文件
     }
     of1.close();    //關(guān)閉輸出文件流
     return true;    //返回
}

/*
函數(shù)：設(shè)置數(shù)據(jù)點(diǎn)的領(lǐng)域點(diǎn)列表
說(shuō)明：設(shè)置數(shù)據(jù)點(diǎn)的領(lǐng)域點(diǎn)列表
參數(shù)：
返回值： true;    */
void ClusterAnalysis::SetArrivalPoints(DataPoint& dp)
{
     for(unsigned long i=0; i<dataNum; i++)                //對(duì)每個(gè)數(shù)據(jù)點(diǎn)執(zhí)行
     {
         double distance =GetDistance(dadaSets[i], dp);    //獲取與特定點(diǎn)之間的距離
         if(distance <= radius && i!=dp.GetDpId())        //若距離小于半徑，并且特定點(diǎn)的id與dp的id不同執(zhí)行
             dp.GetArrivalPoints().push_back(i);            //將特定點(diǎn)id壓力dp的領(lǐng)域列表中
     }
     if(dp.GetArrivalPoints().size() >= minPTs)            //若dp領(lǐng)域內(nèi)數(shù)據(jù)點(diǎn)數(shù)據(jù)量> minPTs執(zhí)行
     {
         dp.SetKey(true);    //將dp核心對(duì)象標(biāo)志位設(shè)為true
         return;                //返回
     }
     dp.SetKey(false);    //若非核心對(duì)象，則將dp核心對(duì)象標(biāo)志位設(shè)為false
}

/*
函數(shù)：執(zhí)行聚類(lèi)操作
說(shuō)明：執(zhí)行聚類(lèi)操作
參數(shù)：
返回值： true;    */
bool ClusterAnalysis::DoDBSCANRecursive()
{
     unsigned long clusterId=0;                        //聚類(lèi)id計(jì)數(shù)，初始化為0
     for(unsigned long i=0; i<dataNum;i++)            //對(duì)每一個(gè)數(shù)據(jù)點(diǎn)執(zhí)行
     {
         DataPoint& dp=dadaSets[i];                    //取到第i個(gè)數(shù)據(jù)點(diǎn)對(duì)象
         if(!dp.isVisited() && dp.IsKey())            //若對(duì)象沒(méi)被訪問(wèn)過(guò)，并且是核心對(duì)象執(zhí)行
         {
             dp.SetClusterId(clusterId);                //設(shè)置該對(duì)象所屬簇ID為clusterId
             dp.SetVisited(true);                    //設(shè)置該對(duì)象已被訪問(wèn)過(guò)
             KeyPointCluster(i,clusterId);            //對(duì)該對(duì)象領(lǐng)域內(nèi)點(diǎn)進(jìn)行聚類(lèi)
             clusterId++;                            //clusterId自增1
         }
         //cout << "孤立點(diǎn)\T" << i << endl;
     }

     cout <<"共聚類(lèi)" <<clusterId<<"個(gè)"<< endl;        //算法完成后，輸出聚類(lèi)個(gè)數(shù)
     return true;    //返回
}

/*
函數(shù)：對(duì)數(shù)據(jù)點(diǎn)領(lǐng)域內(nèi)的點(diǎn)執(zhí)行聚類(lèi)操作
說(shuō)明：采用遞歸的方法，深度優(yōu)先聚類(lèi)數(shù)據(jù)
參數(shù)：
unsigned long dpID;            //數(shù)據(jù)點(diǎn)id
unsigned long clusterId;    //數(shù)據(jù)點(diǎn)所屬簇id
返回值： void;    */
void ClusterAnalysis::KeyPointCluster(unsigned long dpID, unsigned long clusterId )
{
     DataPoint& srcDp = dadaSets[dpID];        //獲取數(shù)據(jù)點(diǎn)對(duì)象
     if(!srcDp.IsKey())    return;
     vector<unsigned long>& arrvalPoints = srcDp.GetArrivalPoints();        //獲取對(duì)象領(lǐng)域內(nèi)點(diǎn)ID列表
     for(unsigned long i=0; i<arrvalPoints.size(); i++)
     {
         DataPoint& desDp = dadaSets[arrvalPoints[i]];    //獲取領(lǐng)域內(nèi)點(diǎn)數(shù)據(jù)點(diǎn)
         if(!desDp.isVisited())                            //若該對(duì)象沒(méi)有被訪問(wèn)過(guò)執(zhí)行
         {
             //cout << "數(shù)據(jù)點(diǎn)\t"<< desDp.GetDpId()<<"聚類(lèi)ID為\t" <<clusterId << endl;
             desDp.SetClusterId(clusterId);        //設(shè)置該對(duì)象所屬簇的ID為clusterId，即將該對(duì)象吸入簇中
             desDp.SetVisited(true);                //設(shè)置該對(duì)象已被訪問(wèn)
             if(desDp.IsKey())                    //若該對(duì)象是核心對(duì)象
             {
                 KeyPointCluster(desDp.GetDpId(),clusterId);    //遞歸地對(duì)該領(lǐng)域點(diǎn)數(shù)據(jù)的領(lǐng)域內(nèi)的點(diǎn)執(zhí)行聚類(lèi)操作，采用深度優(yōu)先方法
             }
         }
     }
}

//兩數(shù)據(jù)點(diǎn)之間距離
/*
函數(shù)：獲取兩數(shù)據(jù)點(diǎn)之間距離
說(shuō)明：獲取兩數(shù)據(jù)點(diǎn)之間的歐式距離
參數(shù)：
DataPoint& dp1;        //數(shù)據(jù)點(diǎn)1
DataPoint& dp2;        //數(shù)據(jù)點(diǎn)2
返回值： double;    //兩點(diǎn)之間的距離        */
double ClusterAnalysis::GetDistance(DataPoint& dp1, DataPoint& dp2)
{
     double distance =0;        //初始化距離為0
     for(int i=0; i<DIME_NUM;i++)    //對(duì)數(shù)據(jù)每一維數(shù)據(jù)執(zhí)行
     {
         distance += pow(dp1.GetDimension()[i] - dp2.GetDimension()[i],2);    //距離+每一維差的平方
     }
     return pow(distance,0.5);        //開(kāi)方并返回距離
}

算法調(diào)用就簡(jiǎn)單了：

復(fù)制代碼代碼如下:

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

using namespace std;

int main()
{
     ClusterAnalysis myClusterAnalysis;                        //聚類(lèi)算法對(duì)象聲明
     myClusterAnalysis.Init("D:\\1108\\XY.txt",500,9);        //算法初始化操作，指定半徑為15，領(lǐng)域內(nèi)最小數(shù)據(jù)點(diǎn)個(gè)數(shù)為3，（在程序中已指定數(shù)據(jù)維度為2）
     myClusterAnalysis.DoDBSCANRecursive();                    //執(zhí)行聚類(lèi)算法
     myClusterAnalysis.WriteToFile("D:\\1108\\XYResult.txt");//寫(xiě)執(zhí)行后的結(jié)果寫(xiě)入文件

     system("pause");    //顯示結(jié)果
     return 0;            //返回
}