根据上面第二个数据集的簇的形状比较怪异，分簇结果应该是连起来的属于一个簇，但是k-means结果分出来很不如人意，所以这里介绍一种新的聚类方法，此方法不同于上一个基于划分的方法，基于划分主要发现圆形或者球形簇；为了发现任意形状的簇，用一个基于密度的聚类方法，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域，这一理念刚好也符合数据集的特征。
DBSCAN：一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。它将簇定义为密度相连的点的最大集合；为了理解基于密度聚类的思想，首先要掌握以下几个定义：
给定对象半径r内的邻域称为该对象的r邻域；
如果对象的r邻域至少包含最小数目MinPts的对象，则称该对象为核心对象；
给定一个对象集合D，如果p在q的r邻域内，并且q是一个核心对象，则我们说对象p从对象q出发是直接密度可达的；
如果存在一个对象链p1，p2，p3，...，pn，p1=q，pn=p，对于pi属于D，i属于1~n，p（i+1）是从pi关于r和MinPts直接密度可达的，则对象p是从对象q关于r和MinPts密度可达的；
如果存在对象o属于D，使对象p和q都是从o关于r和MinPts密度可达的，那么对于对象p到q是关于r和MinPts密度相连的；
密度可达是直接密度可达的传递闭包，这种关系非对称，只有核心对象之间相互密度可达；密度相连是一种对称的关系；
有了以上的概念接下来就是算法描述了：DBSCAN通过检查数据库中每点的r邻域来搜索簇。如果点p的r邻域包含的点多余MinPts个，则创建一个以p为核心对象的新簇。然后，DBSCAN迭代的聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以添加到任何簇时，该过程结束；
具体的伪代码描述如下（摘自维基百科）：
1 DBSCAN(D, eps, MinPts)
2 C = 0 //类别标示
3 for each unvisited point P in dataset D //遍历
4 mark P as visited //已经访问
5 NeighborPts = regionQuery(P, eps) //计算这个点的邻域
6 if sizeof(NeighborPts) [span style="color: rgba(0, 128, 128, 1)"> MinPts //不能作为核心点
7 mark P as NOISE //标记为噪音数据
8 else //作为核心点，根据该点创建一个类别
9 C = next cluster
10 expandCluster(P, NeighborPts, C, eps, MinPts) //根据该核心店扩展类别
11
12 expandCluster(P,//代码效果参考：http://www.zidongmutanji.com/zsjx/186137.html
NeighborPts, C, eps, MinPts)13 add P to cluster C //扩展类别，核心店先加入
14 for each point P' in NeighborPts //然后针对核心店邻域内的点，如果该点没有被访问，
15 if P' is not visited
16 mark P' as visited //进行访问
17 NeighborPts' = regionQuery(P', eps) //如果该点为核心点，则扩充该类别
18 if sizeof(NeighborPts') >= MinPts
19 NeighborPts = NeighborPts joined with NeighborPts'
20 if P' is not yet member of any cluster //如果邻域内点不是核心点，并且无类别，比如噪音数据，则加入此类别
21 add P' to cluster C
22
23 regionQuery(P, eps) //计算邻域
24 return all points within P's eps-neighborhood
这个算法的时间复杂度的限制主要在于邻域的计算，如果存在索引，则能够降低时间复杂度，如果不存在索引，则邻域计算需要遍历所有点，这样时间复杂度就比较高，相当于双层的n的循环，所以时间复杂度为O（n2）；
//代码效果参考：http://www.zidongmutanji.com/zsjx/517461.html
不过针对相同时间复杂度的时间，每个人的算法的运行时间也不尽相同，如果能够做很多的优化，一些常数时间的减少也能够减少时间，由于我这里仅仅是针对伪代码的实现，没有进行数据结构的优化，相对的数据结构也是利用了k-means用的数据结构进行了一些补充，比如添加一些基于密度需要的属性，比如是否被访问，是否为噪音，是否被添加至邻域中等等，跑起来针对数据集1的规模能够很快的得出结果，但是针对数据集2的数据量30W左右的点就存在很多问题，时间很慢，甚至不能容忍，release优化下好一些，debug下基本上无法等待出结果的，所以任何程序都要进行优化的，优化到你个人的最优；接下来是这个算法的具体实现：
?123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106COLORREF colorfultmp【】={RGB(192,192,192),RGB(255,255,0),RGB(227,207,87),RGB(255,153,18),RGB(235,142,85),RGB(255,227,132),RGB(255,97,0),RGB(176,224,230),RGB(65,105,230),RGB(0,255,255),RGB(56,94,15),RGB(8,46,84),RGB(128,42,42),RGB(34,139,34),RGB(160,32,240),RGB(255,0,0),RGB(176,48,96),RGB(176,23,31),RGB(0,0,0)}; void Cluster::dbscan(vector pts,double eps,int MinPts){ int categroy=0; int i,length=pts.size(); vector neightpts,tmpneightpts; //遍历所有的点 for (i=0;im_bVisited) { pts【i】->m_bVisited=TRUE; //计算邻域 neightpts=pts【i】->regionQuery(pts,pts【i】,eps); //include //噪音标记 if (neightpts.size()categroy=0;//NOISE pts【i】->m_isNoise=TRUE; pts【i】->m_colorPT=colorfultmp【pts【i】->categroy%18】; } else { //核心点，聚类 categroy++; pts【i】->categroy=categroy; pts【i】->m_colorPT=colorfultmp【pts【i】->categroy%18】; //邻域内的点标记已经被添加 for (int k=0;km_isInclude=TRUE; } //继续扩大此聚集类 int j=1; //因为邻域的规模组建增大，所以利用while while (jcategroy==0) { neightpts【j-1】->categroy=categroy; neightpts【j-1】->m_colorPT=colorfultmp【neightpts【j-1】->categroy%18】; } //标记访问 if (!neightpts【j-1】->m_bVisited) { neightpts【j-1】->m_bVisited=TRUE; //计算邻域 tmpneightpts=neightpts【j-1】->regionQuery(pts,neightpts【j-1】,eps); //合并核心点的邻域 if (tmpneightpts.size()>=MinPts) { //合并 int m,n; //已经添加则不进行添加 for (m=0;mcategroy==0) { neightpts.push_back(tmpneightpts【m】); } / //不重复添加 //感觉这里限制程序时间的瓶颈 if (!tmpneightpts【m】->m_isInclude) { neightpts.push_back(tmpneightpts【m】); tmpneightpts【m】->m_isInclude=TRUE; } / BOOL exist=FALSE; for (n=0;n
