用C++实现DBSCAN聚类算法

这几天由于工作需要,对DBSCAN聚类算法进行了C++的实现。时间复杂度O(n^2),主要花在算每个点领域内的点上。算法很简单,现共享大家参考,也希望有更多交流。
 数据点类型描述如下:


代码如下:

#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;
 }

DBSCAN算法类型描述:


代码如下:

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

(0)

相关推荐

  • C++实现迷宫算法实例解析

    本文以实例形式描述了C++实现迷宫算法.本例中的迷宫是一个矩形区域,它有一个入口和一个出口.在迷宫的内部包含不能穿越的墙或障碍.障碍物沿着行和列放置,它们与迷宫的矩形边界平行.迷宫的入口在左上角,出口在右下角 本实例迷宫算法的功能主要有: 1.自动生成10*10迷宫图 2.判断是否有迷宫出口,并且画出路线图 具体实现代码如下: # include <iostream> # include <list> # include <sys/timeb.h> # include

  • python实现的生成随机迷宫算法核心代码分享(含游戏完整代码)

    完整代码下载:http://xiazai.jb51.net/201407/tools/python-migong.rar 最近研究了下迷宫的生成算法,然后做了个简单的在线迷宫游戏.游戏地址和对应的开源项目地址可以通过上面的链接找到.开源项目中没有包含服务端的代码,因为服务端的代码实在太简单了.下面将简单的介绍下随机迷宫的生成算法.一旦理解后你会发现这个算法到底有多简单. 1.将迷宫地图分成多个房间,每个房间都有四面墙. 2.让"人"从地图任意一点A出发,开始在迷宫里游荡.从A房间的1/

  • 基于一致性hash算法 C++语言的实现详解

    一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择. 首先来谈一下一致性hash算法中用于存储结点的数据结构.通过了解一致性hash的原理,我们知道结点可以想象为是存储在一个环形的数据结构上(如下图),结点A.B.C.D按hash值在环形分布上是有序的,也就是说结点可以按hash值存储在一个有序的队列里.如下图所示,当一个hash值为-2^20的请求点P查找路由结点时,一致性hash算法会按hash值的顺时针方向路由到第一个结点

  • C++火车入轨算法的实现代码

    [问题描述] 某城市有一个火车站,铁轨铺设如图所示.有n节车厢从A方向驶入车站,按进站顺序编号为1~n.你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站.为了重组车厢,你可以借助中转站C.这是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出.对于每个车厢,一旦从A移入C,就不能再回到A了:一旦从C移入B,就不能回到C了.换句话说,在任意时刻,只有两种选择:A→C和C→B. 这个问题和之前数据结构实验的火车入轨类似,而且较之简化.自己尝试写了下,和书上

  • C++实现汉诺塔算法经典实例

    本文所述为汉诺塔算法的C++代码的经典实现方法. 汉诺塔问题描述:3个柱为a.b.c,圆盘最初在a柱,借助b柱移到c柱.需要你指定圆盘数. 具体实现代码如下: #include <iostream> using namespace std; int times = 0; //全局变量,搬动次数 //第n个圆盘从x柱搬到z柱 void move(int n, char x, char z) { cout << "第" << ++times <&l

  • C++基本算法思想之穷举法

    穷举算法(Exhaustive Attack method)是最简单的一种算法,其依赖于计算机的强大计算能力来穷尽每一种可能性,从而达到求解问题的目的.穷举算法效率不高,但是适应于一些没有规律可循的场合. 穷举算法基本思想穷举算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下: (1)对于一种可能的情况,计算其结果. (2)判断结果是否符合要求,如果不满足则执行第(1)步来搜索下一个可能的情况:如果符合要求,则表示寻找到一个正确答案. 在使用穷举法时,需要明确问题的答案的范围,这

  • C++中的几种排序算法

    SortAlgorithm.h 复制代码 代码如下: #include <vector>using namespace std; class SortAlgorithm{public:    SortAlgorithm(int = 10);    void displayVector();    void swap(int &, int &); void insertSort();                     //O(n^2)    void selectSort(

  • c++非变易算法-stl算法

    C++ STL标准模板库在数据结构和算法的实践领域发挥着重要作用,极大的提高了开发效率.STL的三大组成部分为容器.迭代器.算法,本文主要讲解STL算法中的非变易算法.本文从实践的角度简单介绍了一下相关函数的使用. C++ STL的非变易算法(Non-mutating algorithms)是一组不破坏函数数据的模板函数,用来对序列数据进行逐个处理.元素查找.子序列搜索.统计和匹配,基本上可用于各种容器.下面的叙述中迭代器区间默认为[first, last),迭代器具有"++"迭代和&

  • C++ 冒泡排序数据结构、算法及改进算法

    程序代码如下: 复制代码 代码如下: // BubbleSort.cpp : 定义控制台应用程序的入口点.//#include "stdafx.h"#include <cmath>#include <iostream>using namespace std;#define  MAXNUM 20template<typename T>void Swap(T& a, T& b){    int t = a;    a = b;    b

  • c++实现MD5算法实现代码

    测试结果和百度百科测试例子一致. 实现过程中需要注意事项:最后把四个变量A B C D 链接成结果时 ,注意变量高低位的先后顺序,具体参考 LinkResult()方法. md5.h #ifndef _MD5_H_ #define _MD5_H_ #include <iostream> #include <string> using namespace std; class MD5 { public: typedef unsigned char uchar8; //make sur

  • C++基本算法思想之递推算法思想

    递推算法是非常常用的算法思想,在数学计算等场合有着广泛的应用.递推算法适合有明显公式规律的场合. 递推算法基本思想递推算法是一种理性思维莫斯的代表,根据已有的数据和关系,逐步推到而得到结果.递推算法的执行过程如下: (1)根据已知结果和关系,求解中间结果. (2)判断是否达到要求,如果没有达到,则继续根据已知结果和关系求解中间结果.如果满足要求,则表示寻找到一个正确答案. 递推算法需要用户知道答案和问题之间的逻辑关系.在许多数学问题中,都有明确的计算公式可以遵循,因此可以采用递推算法来实现. 递

  • C++实现各种排序算法类汇总

    C++可实现各种排序算法类,比如直接插入排序.折半插入排序.Shell排序.归并排序.简单选择排序.基数排序.对data数组中的元素进行希尔排序.冒泡排序.递归实现.堆排序.用数组实现的基数排序等. 具体代码如下: #ifndef SORT_H #define SORT_H #include <iostream> #include <queue> using namespace std; // 1.直接插入排序 template<class ElemType> void

随机推荐