? 密度聚类，也被称为CFDP(Clustering by fast search and find of density peaksd)。
? 密度聚类的作用和Kmeans聚类差不多，可以将一堆数据分成若干类。“密度聚类”，顾名思义其实就是根据点的密度进行归类，比如说某一处点特别密集，那么这一块会偏向归为一类。这篇文章就具体整理一下密度聚类的原理与实现。
1.密度聚类实现过程??
假设在一个二维平面中有若干个点，我们想要对这些点进行聚类，那么密度聚类的过程如下：
? 对于每一个点，我们需要计算这个点的“局部密度”与“局部距离”这两个变量。
局部密度:
? 局部密度取决于dc值，dc值是在密度聚类前人为指定的一个超参数，它是一个范围距离，那么某一个点的局部密度就是这个点周围dc范围内（即以这一点为圆心，dc为半径的圆）邻居点的个数。
? 关于dc值的选取，一般是选取一个值——该值使得所有数据点的平均邻居个数为总数据点的1-2%。
局部距离：
? 局部距离理解起来比局部密度要抽象一些，不能靠它的名称来理解。假设现在我们已经得到了所有点的局部密度，对于每一个点的局部距离来说：
1.对于局部密度最大的点（就只有那一个点），它的局部距离是该点和其他所有点距离的最大值。即到距离它最远点的距离。
2.对于非局部密度最大的点（剩下的所有的点），它的局部距离是：在比它局部密度高的所有点中，至离它最近的点的距离。
总距离：
? 至此，每个点的总距离=局部密度+局部距离。如果最终要将数据分成3类，那么总距离最大的前三个点，就是三个中心点，其余的点离哪一个点近，就归为哪一类。（所以其实“总距离”也可以说成是“总权重”，总权重越大就越有资格成为一个聚类中心。）密度聚类的实现过程就整理完毕了。
2.密度聚类原理分析与理解
接下来讲一下密度聚类这样做的原理是什么，为什么这样做就可以较好的实现出聚类的效果。这部分需要一些理解。
（其实理解密度聚类的精髓就是理解“总距离”尤其是“局部距离”的计算逻辑。
一、对于局部密度最大的点，它必然是要成为一个中心的，因此我们直接赋予它最大的局部距离即可；这样会毫无疑问算出一个最大的总距离，毫无疑问出第一个中心。
二、而对于局部密度也很大但不是最大的点来说，一般有两种情况：
1.一种是它紧挨着局部密度最大点，此时我们肯定是希望这种点不要自成一个中心，而是附属于旁边那个局部密度最大点。为了实现这个要求，就让它后面的局部距离不要太大即可（这样总距离就不会太大），因此局部距离就选“在比它局部密度高的所有点中离它最近的点的距离”，这个距离必然是很小的。
2. 另一种情况就是它离局部密度最大点较远，此时它自己可能成为某一块的中心，此时易知它的局部距离按照给定的计算方法来说是很可观的（较大的），因此剩下的中心也基本上来自于这种点。
三、 对于局部密度比较少的点，这种点基本上最后的总距离不会很大，很难成为中心。但如果它离任何一个比它局部密度高的点都特别远，即局部距离很大，那么它也能算出很大的总距离，也会成为中心。
??可见，对于种种情况，密度聚类算法通过局部密度和局部距离的计算，都可以自适应实现挑选聚类中心点的功能。既避免了在一处很密集的地方有多个中心，又赋予了偏远处点中出现中心的可能。）
3.密度聚类代码实现
? 密度聚类的原理讲完了，下面是我自己用python代码实现的简单密度聚类，并且可视化其聚类效果。在代码中，我在一个二维坐标平面上随机成500个数，并对这500个数进行CFDP聚类。
from matplotlib import pyplot as plt
import random
class Dot():#定义一个点类
def __init__(self,x,y):
self.x = x
self.y = y
self.cut_off = 0 #邻居数，也就是局部密度
self.distance = 0#距离
self._class = None
def distance(x1,y1,x2,y2): #计算两点间距离的函数，直接用欧氏距离就好
return (x1-x2)**2+(y1-y2)**2
dot_list=[] #用于存放所有点的列表
for i in range(500): #随机生成500个点
x = random.randint(1,200)
y = random.randint(1,200)
dot_list.append(Dot(x,y))
#通过下面这一段来找到合适的dc值
# sum1 = 0
# for dot in dot_list:
# sum1+=dot.cut_off
# print(sum1/500/500)#让每个数据点的平均邻居个数为总数居点的1%-2%
#计算密度
dc = 120 #通过上面调试，dc值设定为120
for dot1 in dot_list:
for dot2 in dot_list:
if distance(dot1.x,dot2.x,dot1.y,dot2.y)==0:
pass
else:
if distance(dot1.x,dot2.x,dot1.y,dot2.y)-dc<0:#增加dot1的局部密度
dot1.cut_off+=1
#计算距离
for dot1 in dot_list:#对于每一个点
flag = 0#先假设是局部密度最大点
min_distance=[]
for dot2 in dot_list:
if dot1.cut_off<dot2.cut_off:
flag=1#不是局部密度最大点了
min_distance.append(distance(dot1.x,dot2.x,dot1.y,dot2.y))#先暂存这个距离
if flag==1:#不是局部密度最大点，
dot1.distance=min(min_distance)#找出最近的那个点
else:#仍然是局部密度最大点
for dot2 in dot_list:
if distance(dot1.x,dot2.x,dot1.y,dot2.y)>dot1.distance:
#更新dot1.distance到最大
dot1.distance=distance(dot1.x,dot2.x,dot1.y,dot2.y)
dot_list.sort(key=lambda x:x.cut_off+x.distance,reverse=True)#按照总距离进行排序
# for dot in dot_list:
# print(dot.cut_off)
class_num = 3 #假设我们要分成3类
dot_list[0]._class = 1#前三个分别就是三个中心
dot_list[1]._class = 2
dot_list[2]._class = 3
for dot in dot_list[3:]:#对于其他的点，离谁近就是哪一类
if distance(dot.x,dot.y,dot_list[0].x,dot_list[0].y) == min(distance(dot.x,dot.y,dot_list[0].x,dot_list[0].y),distance(dot.x,dot.y,dot_list[1].x,dot_list[1].y),distance(dot.x,dot.y,dot_list[2].x,dot_list[2].y)):
dot._class=1
elif distance(dot.x,dot.y,dot_list[1].x,dot_list[1].y) == min(distance(dot.x,dot.y,dot_list[0].x,dot_list[0].y),distance(dot.x,dot.y,dot_list[1].x,dot_list[1].y),distance(dot.x,dot.y,dot_list[2].x,dot_list[2].y)):
dot._class=2
else:
dot._class=3
for dot in dot_list:#一些上色和可视化操作
if dot._class==1:
plt.plot(dot.x,dot.y,'x',color = 'blue')
elif dot._class==2:
plt.plot(dot.x,dot.y,'d',color = 'green')
elif dot._class==3:
plt.plot(dot.x,dot.y,'^',color = 'black')
plt.show()上面的代码可以直接复制去运行，因为每次的随机生成的数据点，因此每次的结果也会稍有不同。
聚类效果:
? ?上面左图是密度聚类的实现结果。可见密度聚类算法大致成功地将数据集划分为了三部分。
? （值得一提的是，假如对于同样的500个数据点，我使用Kmeans聚类，分出的三种数据类会呈现“块状”（如右图）；而使用密度聚类，则会呈现左图所示的“层状”，或许从这里能体现出两种算法的不同之处和侧重点。）
小结：
? 这篇文章主要梳理了密度聚类CFDP的算法原理，以及对密度聚类进行了实现和效果展示。