DBSCAN聚类算法原理及其实现
来源：open开发经验库
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是一种基于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇。我们总结一下DBSCAN聚类算法原理的基本要点： 
DBSCAN算法需要选择一种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难，所以对于二维空间中的点，可以使用欧几里德距离来进行度量。 
DBSCAN算法需要用户输入2个参数：一个参数是半径（Eps），表示以给定点P为中心的圆形邻域的范围；另一个参数是以点P为中心的邻域内最少点的数量（MinPts）。如果满足：以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts，则称点P为核心点。 
DBSCAN聚类使用到一个k-距离的概念，k-距离是指：给定数据集P={p(i); i=0,1,…n}，对于任意点P(i)，计算点P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有点之间的距离，距离按照从小到大的顺序排序，假设排序后的距离集合为D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，则d(k)就被称为k-距离。也就是说，k-距离是点p(i)到所有点（除了p(i)点）之间距离第k近的距离。对待聚类集合中每个点p(i)都计算k-距离，最后得到所有点的k-距离集合E={e(1), e(2), …, e(n)}。 
根据经验计算半径Eps：根据得到的所有点的k-距离集合E，对集合E进行升序排序后得到k-距离集合E’，需要拟合一条排序后的E’集合中k-距离的变化曲线图，然后绘出曲线，通过观察，将急剧发生变化的位置所对应的k-距离的值，确定为半径Eps的值。 
根据经验计算最少点的数量MinPts：确定MinPts的大小，实际上也是确定k-距离中k的值，DBSCAN算法取k=4，则MinPts=4。 
另外，如果觉得经验值聚类的结果不满意，可以适当调整Eps和MinPts的值，经过多次迭代计算对比，选择最合适的参数值。可以看出，如果MinPts不变，Eps取得值过大，会导致大多数点都聚到同一个簇中，Eps过小，会导致已一个簇的分裂；如果Eps不变，MinPts的值取得过大，会导致同一个簇中点被标记为噪声点，MinPts过小，会导致发现大量的核心点。 
我们需要知道的是，DBSCAN算法，需要输入2个参数，这两个参数的计算都来自经验知识。半径Eps的计算依赖于计算k-距离，DBSCAN取k=4，也就是设置MinPts=4，然后需要根据k-距离曲线，根据经验观察找到合适的半径Eps的值，下面的算法实现过程中，我们会详细说明。对于算法的实现，首先我们概要地描述一下实现的过程： 
解析样本数据文件 
计算每个点与其他所有点之间的欧几里德距离 
计算每个点的k-距离值，并对所有点的k-距离集合进行升序排序，输出的排序后的k-距离值 
将所有点的k-距离值，在Excel中用散点图显示k-距离变化趋势 
根据散点图确定半径Eps的值 
根据给定MinPts=4，以及半径Eps的值，计算所有核心点，并建立核心点与到核心点距离小于半径Eps的点的映射 
根据得到的核心点集合，以及半径Eps的值，计算能够连通的核心点，得到噪声点 
将能够连通的每一组核心点，以及到核心点距离小于半径Eps的点，都放到一起，形成一个簇 
选择不同的半径Eps，使用DBSCAN算法聚类得到的一组簇及其噪声点，使用散点图对比聚类效果 
然后，再详细描述聚类过程的具体实现。 
计算欧几里德距离 
我们使用的样本数据，来自一组经纬度坐标数据，数据文件格式类似如下所示： 
116.389463
39.87194
116.389463
116.312984
116.382798
116.496648
116.436246
116.622074
116.599267
116.441824
116.599267
116.402096
39.93428
116.327812
116.374739
116.287195
116.513574
116.474355
116.400651
... ... 我们需要做的首先就是，解析样本数据文件，将其转换成我们需要的表示形式，我们定义了Point2D类，代码如下所示： 
package org.shirdrn.
public class Point2D {
protected final D
protected final D
public Point2D(Double x, Double y) {
super();
this.x =
this.y =
@Override
public int hashCode() {
return 31 * x.hashCode() + 31 * y.hashCode();
@Override
public boolean equals(Object obj) {
Point2D other = (Point2D)
return this.x.doubleValue() == other.x.doubleValue() && this.y.doubleValue() == other.y.doubleValue();
public Double getX() {
public Double getY() {
@Override
public String toString() {
return "(" + x + ", " + y + ")";
} 我们可以将解析后的点的对象放到一个List&Point2D& allPoints集合里面，以便后续使用时迭代集合。在计算两点之间的欧几里德距离时，需要迭代前面生成的Point2D的集合，计算欧几里德距离，实现方法如下所示： 
public static double euclideanDistance(Point2D p1, Point2D p2) {
double sum = 0.0;
double diffX = p1.getX() - p2.getX();
double diffY = p1.getY() - p2.getY();
sum += diffX * diffX + diffY * diffY;
return Math.sqrt(sum);
} 如果需要，可以将计算的所有点之间的距离缓存，因为计算k-距离需要多次访问点的欧几里德距离，比如，可以使用Guava库中的Cache工具： 
Cache&Set&Point2D&, Double& distanceCache =
CacheBuilder.newBuilder().maximumSize(Integer.MAX_VALUE).build(); 上面代码中，设置缓存容纳足够多（Integer.MAX_VALUE）的对象，将计算出的全部的欧几里德距离放在内存中，便于后续迭代时重用。 
计算k-距离 
每个点都要计算k-距离，在计算一个点的k-距离的时候，首先要计算该点到其他所有点的欧几里德距离，按照距离升序排序后，选择第k小的距离作为k-距离的值，实现代码如下所示： 
Task task = q.poll(); // 从队列q中取出一个Task，就是计算一个点的k-距离的任务
KPoint2D p1 = (KPoint2D) task.p;
final TreeSet&Double& sortedDistances = Sets.newTreeSet(new Comparator&Double&() { // 创建一个降序排序TreeSet
@Override
public int compare(Double o1, Double o2) {
double diff = o1 - o2;
if(diff & 0) {
return -1;
if(diff & 0) {
return 1;
return 0;
for (int i = 0; i & allPoints.size(); i++) { // 计算点p1与allPoints集合中每个点的k-距离
if(task.pos != i) { // 点p1与它自己的欧几里德距离没必要计算
KPoint2D p2 = (KPoint2D) allPoints.get(i);
Set&Point2D& set = Sets.newHashSet((Point2D) p1, (Point2D) p2);
Double distance = distanceCache.getIfPresent(set); // 从缓存中取出欧几里德距离（可能不存在）
if(distance == null) {
distance = MetricUtils.euclideanDistance(p1, p2);
distanceCache.put(set, distance); // 不存在则加入缓存中
if(!sortedDistances.contains(distance)) {
sortedDistances.add(distance);
if(sortedDistances.size() & k) { // TreeSet中只最多保留k个欧几里德距离值
Iterator&Double& iter = sortedDistances.iterator();
iter.next();
// remove (k+1)th minimum distance
iter.remove(); // 将k+1个距离值中最大的删除，剩余k个是最小的
// collect k-distance
p1.kDistance = sortedDistances.iterator().next();
// 此时，TreeSet中最大的，就是第k最小的距离 上述代码中，KPoint2D类是Point2D的子类，不过比基类Point2D多了一个k-距离的属性，代码如下所示： 
private class KPoint2D extends Point2D {
private Double kDistance = 0.0;
public KPoint2D(Double x, Double y) {
super(x, y);
@Override
public int hashCode() {
return super.hashCode();
@Override
public boolean equals(Object obj) {
return super.equals(obj);
} 代码比较容易，可以查看相关注释信息。 
绘制k-距离曲线，寻找半径Eps 
x轴坐标点我们直接使用递增的自然数序列，每个点对应一个自然数，y轴就是所有点的k-距离的大小，我们在代码中可以进行处理，实现如下： 
for(int i=0; i&allPoints.size(); i++) {
KPoint2D kp = (KPoint2D) allPoints.get(i);
System.out.println(i + "\t" + kp.kDistance);
} 最终生成的数据，输出格式类似如下： 
6.257E-4
8.753E-4
8.709E-4
8.01E-4
9.06E-4
... ... 
我们把输出数据复制到Excel表格中，使用上述数据生成散点图，基于x坐标取了4个不同的范围，观察曲线的变化情况，0~0、、0~2500各个x坐标范围内的点，对应的散点图分别如下所示： 
通过上图可以看出： 
左上图（0~2600）：由于x=2500之后店的k-距离变化太快（可以忽略），导致前面点的k-距离的变化趋势无法观察出来。 
右上图（0~2000）：去掉尾部的一些点的k-距离，可以看出曲线的变化趋势。 
左下图（）：x坐标轴后半部分的距离的变化趋势。 
右下图（0~2500）：去掉尾部一些k-距离点，展示大部分k-距离点的变化趋势。 
综合上面4个图，可以选择得到半径Eps的范围大致在0.002~0.006之间，已知MinPts=4，具体我们可以选择下面3个k-距离的值作为半径Eps： 
0.403014 通过下一步进行聚类，看一下使用选择的Eps的这几个值进行聚类的效果对比。另外，对半径Eps=8也进行聚类，主要是为了看一下半径变化对聚类效果的影响。 
计算核心点 
聚类过程需要知道半径Eps，半径已知，首先需要计算有哪些核心点，给定点，如果以该点为中心半径为Eps的邻域内的其他点的数量大于等于MinPts，则该点就为核心点。计算核心点的实现代码如下所示： 
Point2D p1 = taskQueue.poll();
if(p1 != null) {
++processedP
Set&Point2D& set = Sets.newHashSet();
Iterator&Point2D& iter = epsEstimator.allPointIterator();
while(iter.hasNext()) {
Point2D p2 = iter.next();
if(!p2.equals(p1)) {
double distance = epsEstimator.getDistance(Sets.newHashSet(p1, p2));
// collect a point belonging to the point p1
if(distance &= eps) { // 收集每个点与其邻域内的点之间距离小于等于Eps的点
set.add(p2);
// decide whether p1 is core point
if(set.size() &= minPts) { // 计算收集到的邻域内的点的个数，小于等于MinPts，则加入到映射表Map&Point2D, Set&Point2D&& corePointScopeSet中
corePointScopeSet.put(p1, set);
LOG.debug("Decide core point: point" + p1 + ", set=" + set);
} else {
// here, perhaps a point was wrongly put into noise point set
// afterwards we should remedy noise point set
if(!noisePoints.contains(p1)) { // 这里，会把一些点错误地加入到噪声点集合noisePoints中，后面会进行修正
noisePoints.add(p1);
} 那些被错误放入噪声点集合的点，需要在计算核心点完成之后，遍历噪声点集合，与核心点集合（及其对应的映射点集合）进行比对，代码如下所示： 
// process noise points
Iterator&Point2D& iter = noisePoints.iterator();
while(iter.hasNext()) {
Point2D np = iter.next();
if(corePointScopeSet.containsKey(np)) {
iter.remove();
} else {
for(Set&Point2D& set : corePointScopeSet.values()) {
if(set.contains(np)) {
iter.remove();
} 这样，有些非噪声点就从噪声点集合中被排除了。 
连通核心点生成簇 
核心点能够连通（有些书籍中称为：“密度可达”），它们构成的以Eps长度为半径的圆形邻域相互连接或重叠，这些连通的核心点及其所处的邻域内的全部点构成一个簇。假设MinPts=4，则连通的核心点示例，如下图所示： 
计算连通的核心点的思路是，基于广度遍历与深度遍历集合的方式：从核心点集合S中取出一个点p，计算点p与S集合中每个点（除了p点）是否连通，可能会得到一个连通核心点的集合C1，然后从集合S中删除点p和C1集合中的点，得到核心点集合S1；再从S1中取出一个点p1，计算p1与核心点集合S1集中每个点（除了p1点）是否连通，可能得到一个连通核心点集合C2，再从集合S1中删除点p1和C2集合中所有点，得到核心点集合S2，……最后得到p、p1、p2、……，以及C1、C2、……就构成一个簇的核心点。最终将核心点集合S中的点都遍历完成，得到所有的簇。具体代码实现，如下所示： 
// join connected core points
("Joining connected points ...");
Set&Point2D& corePoints = Sets.newHashSet(corePointScopeSet.keySet());
while(true) {
Set&Point2D& set = Sets.newHashSet();
Iterator&Point2D& iter = corePoints.iterator();
if(iter.hasNext()) {
Point2D p = iter.next();
iter.remove();
Set&Point2D& connectedPoints = joinConnectedCorePoints(p, corePoints);
set.addAll(connectedPoints);
while(!connectedPoints.isEmpty()) {
connectedPoints = joinConnectedCorePoints(connectedPoints, corePoints);
set.addAll(connectedPoints);
clusteredPoints.put(p, set);
} else {
} 上面调用了重载的两个方法joinConnectedCorePoints，分别根据参数不同计算连通的核心点集合：计算核心点集合中一个点，与该核心点集合中其它的所有核心点是否连通，调用如下方法： 
private Set&Point2D& joinConnectedCorePoints(Point2D p1, Set&Point2D& leftCorePoints) {
Set&Point2D& set = Sets.newHashSet();
for(Point2D p2 : leftCorePoints) {
double distance = epsEstimator.getDistance(Sets.newHashSet(p1, p2));
if(distance &= eps) {
// join 2 core points to the same cluster
set.add(p2);
// remove connected points
leftCorePoints.removeAll(set); // 删除已经确定为与p1连通的核心点
} 还有一个方法是，上面第一个参数变为一个集合，它调用上面的方式处理每一个点，方法代码实现如下所示： 
private Set&Point2D& joinConnectedCorePoints(Set&Point2D& connectedPoints, Set&Point2D& leftCorePoints) {
Set&Point2D& set = Sets.newHashSet();
for(Point2D p1 : connectedPoints) {
set.addAll(joinConnectedCorePoints(p1, leftCorePoints));
} 最后，集合clusteredPoints存储的就是聚类后的核心点的信息，再根据核心点到其邻域内半径小于等于Eps的点的集合的映射，就能将所有的点生成聚类了。 
聚类效果比较 
选择不同的半径Eps进行聚类分析， 聚类的结果也不相同，有些情况下差异很大，有些情况差异较小。比如，在MinPts=4的情况下，如何绘制k-距离曲线，已经在前面详细说明了处理过程，我们根据k-距离趋势增长曲线，选择了一组半径Eps的值，执行DBSCAN聚类算法，下面我们比较在MinPts=4和MinPts=8的情况下，再分别选择不同的半径Eps，执行DBSCAN聚类算法生成簇，对分布情况进行对比。 
参数：MinPts=4 
选择半径Eps的值分别为如下3个观察值： 
0.403014 
最终得到的聚类效果图在下面可以看到，其中，左侧为没有噪声点的情况各个簇的分布情况，右侧是将噪声点全部加入到图上显示，图中图例中的9999表示噪声点，其他的都是聚类生成的簇，如下图所示： 
通过上图可以看出，半径Eps选择的较小时，会产生大量的噪声点，其实我们想一下，半径小了，自然落在某个点的邻域内的点减少的可能性就增加了，导致很多点可能就无法成为核心点，自然也就无法成为某个簇的点，而且很生成的簇包含的点的数量都比较少，某些本来很接近的点应该可以成为同一个簇，但是被分裂了。 
当半径比较大一些时，生成的一个簇包含了比较多的点，而且这个簇的形状中间可能出现一些“空洞”，因为点之间的距离大一些也能满足成为核心点的要求，所以这些点聚到一簇中可能确实比较合理。 
参数：MinPts=8 
选择半径Eps的值分别为如下3个观察值： 
0.911
0.196359 
使用我们实现的DBSCAN聚类算法进行分析处理，得到的聚类结果，如下图所示： 
总结 
因为DBSCAN聚类算法，是基于密度的聚类算法，所以对于密度分别不均，各个簇的密度变化较大时，可能会导致一些问题：比如半径Eps较大时，本来不属于同一个的簇的点被聚到一个簇中；比如半径Eps比较小时，会出现大量比较小的簇（即每个簇中含有的点不较少，但是这些点组成的小簇密度确实很大），同时出现了大量的点不满足成为核心点的要求，MinPts越大越容易出现这种情况。DBSCAN聚类算法的思想非常明确易懂，虽然需要用户输入2个参数，但是正是输入参数的灵活性，我们可以根据自己实际应用的需要，适当调整参数值，在特定应用场景下进行聚类分析，得到合适的簇划分。通过上面选择不同参数进行聚类的结果对比，如果希望局部比较密集的点都能够生成簇，那么在固定MinPts的值的条件下，半径Eps通过调整变小，可能达到这一需要，产生的簇的数量比较多，但是同时也产生了大量分散的噪声点，实际上应该可以进行二次聚类，将噪声点也通过合适的方式归到指定的簇中；如果希望生成全局比较大的簇，可以适当调整半径Eps变大，生成的簇的数量较少，噪声点的数量也相对较少。原文
免责声明：本站部分内容、图片、文字、视频等来自于互联网，仅供大家学习与交流。相关内容如涉嫌侵犯您的知识产权或其他合法权益，请向本站发送有效通知，我们会及时处理。反馈邮箱&&&&。
学生服务号
在线咨询，奖学金返现，名师点评，等你来互动这几天由于工作需要，对DBSCAN聚类算法进行了C++的实现。时间复杂度O(n^2)，主要花在算每个点领域内的点上。算法很简单，现共享大家参考，也希望有更多交流。
&数据点类型描述如下：
1 #include &vector&
3 using namespace
5 const int DIME_NUM=2;
//数据维度为2，全局常量
7 //数据点类型
8 class DataPoint
10 private:
unsigned long dpID;
//数据点ID
double dimension[DIME_NUM];
//维度数据
long clusterId;
//所属聚类ID
//是否核心对象
//是否已访问
vector&unsigned long& arrivalP
//领域数据点id列表
17 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方法
这是实现：
1 #include &DataPoint.h&
3 //默认构造函数
4 DataPoint::DataPoint()
8 //构造函数
9 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];
18 //设置维度数据
19 void DataPoint::SetDimension(double* dimension)
for(int i=0; i&DIME_NUM;i++)
this-&dimension[i]=dimension[i];
27 //获取维度数据
28 double* DataPoint::GetDimension()
return this-&
33 //获取是否为核心对象
34 bool DataPoint::IsKey()
return this-&isK
39 //设置核心对象标志
40 void DataPoint::SetKey(bool isKey)
this-&isKey = isK
45 //获取DpId方法
46 unsigned long DataPoint::GetDpId()
return this-&dpID;
51 //设置DpId方法
52 void DataPoint::SetDpId(unsigned long dpID)
this-&dpID = dpID;
57 //GetIsVisited方法
58 bool DataPoint::isVisited()
return this-&
64 //SetIsVisited方法
65 void DataPoint::SetVisited( bool visited )
this-&visited =
70 //GetClusterId方法
71 long DataPoint::GetClusterId()
return this-&clusterId;
76 //GetClusterId方法
77 void DataPoint::SetClusterId( long clusterId )
this-&clusterId = clusterId;
82 //GetArrivalPoints方法
83 vector&unsigned long&& DataPoint::GetArrivalPoints()
return arrivalP
DBSCAN算法类型描述：
1 #include &iostream&
2 #include &cmath&
5 using namespace
7 //聚类分析类型
8 class ClusterAnalysis
10 private:
vector&DataPoint& dadaS
//数据集合
unsigned int dimN
unsigned int dataN
//数据数量
unsigned int minPTs;
//邻域最小数据个数
double GetDistance(DataPoint& dp1, DataPoint& dp2);
//距离函数
void SetArrivalPoints(DataPoint& dp);
//设置数据点的领域点列表
void KeyPointCluster( unsigned long i, unsigned long clusterId );
//对数据点领域内的点执行聚类操作
20 public:
ClusterAnalysis(){}
//默认构造函数
bool Init(char* fileName, double radius, int minPTs);
//初始化操作
bool DoDBSCANRecursive();
//DBSCAN递归算法
bool WriteToFile(char* fileName);
//将聚类结果写入文件
&聚类实现：
1 #include &ClusterAnalysis.h&
2 #include &fstream&
3 #include &iosfwd&
4 #include &math.h&
7 函数：聚类初始化操作
8 说明：将数据文件名，半径，领域最小数据个数信息写入聚类算法类，读取文件，把数据信息读入写进算法类数据集合中
10 char* fileN
12 int minPTs;
//领域最小数据个数
13 返回值：
14 bool ClusterAnalysis::Init(char* fileName, double radius, int minPTs)
this-&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);
//将维度信息存入数据点对象内
37 //char date[20]=&&;
38 //char time[20]=&&;
//无用信息
41 //ifs &&
//无用信息读入
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&dataNi++)
SetArrivalPoints(dadaSets[i]);
//计算数据点领域内对象
return true;
59 函数：将已经过聚类算法处理的数据集合写回文件
60 说明：将已经过聚类结果写回文件
62 char* fileN
//要写入的文件名
63 返回值： true
64 bool ClusterAnalysis::WriteToFile(char* fileName )
ofstream of1(fileName);
//初始化文件输出流
for(unsigned long i=0; i&dataNi++)
//对处理过的每个数据点写入文件
for(int d=0; d&DIME_NUM ; d++)
//将维度信息写入文件
of1&&dadaSets[i].GetDimension()[d]&&'\t';
of1 && dadaSets[i].GetClusterId() &&
//将所属簇ID写入文件
of1.close();
//关闭输出文件流
return true;
78 函数：设置数据点的领域点列表
79 说明：设置数据点的领域点列表
81 返回值：
82 void ClusterAnalysis::SetArrivalPoints(DataPoint& dp)
for(unsigned long i=0; i&dataN 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
dp.SetKey(false);
//若非核心对象，则将dp核心对象标志位设为false
100 函数：执行聚类操作
101 说明：执行聚类操作
102 参数：
103 返回值：
104 bool ClusterAnalysis::DoDBSCANRecursive()
unsigned long clusterId=0;
//聚类id计数，初始化为0
for(unsigned long i=0; i&dataNi++)
//对每一个数据点执行
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 &&
cout &&&共聚类& &&clusterId&&&个&&&
//算法完成后，输出聚类个数
return true;
125 函数：对数据点领域内的点执行聚类操作
126 说明：采用递归的方法，深度优先聚类数据
127 参数：
128 unsigned long dpID;
//数据点id
129 unsigned long clusterId;
//数据点所属簇id
130 返回值：
131 void ClusterAnalysis::KeyPointCluster(unsigned long dpID, unsigned long clusterId )
DataPoint& srcDp = dadaSets[dpID];
//获取数据点对象
if(!srcDp.IsKey())
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 &&
desDp.SetClusterId(clusterId);
//设置该对象所属簇的ID为clusterId，即将该对象吸入簇中
desDp.SetVisited(true);
//设置该对象已被访问
if(desDp.IsKey())
//若该对象是核心对象
KeyPointCluster(desDp.GetDpId(),clusterId);
//递归地对该领域点数据的领域内的点执行聚类操作，采用深度优先方法
152 //两数据点之间距离
154 函数：获取两数据点之间距离
155 说明：获取两数据点之间的欧式距离
156 参数：
157 DataPoint& dp1;
158 DataPoint& dp2;
159 返回值：
//两点之间的距离
160 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);
//开方并返回距离
算法调用就简单了：
1 #include &ClusterAnalysis.h&
2 #include &cstdio&
4 using namespace
6 int main()
ClusterAnalysis myClusterA
//聚类算法对象声明
myClusterAnalysis.Init(&D:\\1108\\XY.txt&,500,9);
//算法初始化操作，指定半径为15，领域内最小数据点个数为3，（在程序中已指定数据维度为2）
myClusterAnalysis.DoDBSCANRecursive();
//执行聚类算法
myClusterAnalysis.WriteToFile(&D:\\1108\\XYResult.txt&);//写执行后的结果写入文件
system(&pause&);
//显示结果
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：16110次
排名：千里之外
转载：36篇
(2)(1)(11)(1)(12)(1)(8)