K-means

实验目的

在聚类的相关知识的基础上，本次实验将对论文《Clustering by fast search and find of density peaks》中的实验方法进行学习，重现论文的算法，并对该算法的性能进行分析。

实验原理

聚类作为机器学习常用的无监督学习方法，核心思想就是根据元素的相似性进行分类，诸如K-means，K-medoids等都是聚类的常见算法，但是K-means算法的核心依赖于欧氏距离，无法分辨出非球形的簇，而DBSCAN虽然可以解决非球形簇的问题，但是只适用于一组坐标定义的数据，且效率较低，因此在《Clustering by fast search and find of density peaks》一文中，作者提出了新的聚类算法（下称DPC），既能分辨出非球形的簇，也有着较高的效率（无需显式地最大化每个数据点的密度场。

DPC的基础是假定每个簇的中心v具有较高的局部密度，且被局部密度较低的邻域包围，且与其他局部密度较高的点之间距离较大，因此在算法中，需要计算的数据为：各个点之间的欧氏距离，局部密度以及大小关系，具体运行步骤如下：

  • 计算样本的距离矩阵 $D_{ij}=(X_i-X_j)^T(X_i-X_j)$
  • 计算每个样本点的局部密度，对样本i，局部密度的定义为$\rho =\sum_j\chi(d_{ij}-dc),\chi(a)=\begin{cases}0,a\ge0\\1,a<0\end{cases}$
  • 利用局部密度，计算样本点i与其他密度更高的点的距离的最小值$\delta _i=min_{j:\rho j>\rho i}d_ij$,其中，对于局部密度最大的点，记为与该点距离最远的点对应的距离$\delta_{i}=max_jd_{ij}$（该点必然是某一个簇的中心）
  • 找到所有簇的中心，对于局部密度高于某阈值的样本点，如果该点的一定邻域内不存在簇的中心，则可将该点作为新的簇
  • 对于其他的样本点，将样本归属到局部密度大于该点且距离该点最近的节点所属的簇，按局部密度的降序依次计算，每个样本点划分到所属的簇

评估指标：DBI

DBI越小，说明分类越合理。

实验步骤

数据预处理

从文件读取数据，并对数据进行归一化，本次实验的数据均为二维向量（便于可视化）

df = pd.read_csv('...txt',sep=' ',header=None)
data=np.array(df)
data=np.array((df-df.min())/(df.max()-df.min()))

算法核心部分

  • 计算距离矩阵和局部密度

    for i in range(self.size):
       for j in range(self.size):
           t=np.sum((self.data[i]-self.data[j])**2)
           self.dist[i,j]=t
           if t-self.dc<0:		self.rho[i]+=1

  • 计算delta数组，index是根据局部密度rho进行排序（从大到小）

    index=(-self.rho).argsort()
self.delta[index[0]]=self.dist[index[0]].max()
for i in range(1,self.size):
    self.delta[index[i]]=self.dist[index[i],index[0:i]].min()

  • 计算簇中心

    • 局部密度大于阈值且与局部密度大的节点距离均超过阈值时，标记为新的簇中心
    • 局部密度小于阈值且与局部密度大的节点距离均超过阈值时，标记为异常点，将簇的编号记作-1
    for i in range(0,self.size):
    if self.rho[i]>self.rho_val and self.delta[i]>self.delta_val:
        self.center.append(i)
        self.clus[i]=self.clu_num
        self.clu_num+=1
    elif self.rho[i]<self.rho_val and self.delta[i]>self.delta_val:
            self.clus[i]=-1

  • 按局部密度从大到小计算其他节点所属的簇，对于既不是簇中心，也不是异常点的数据来说，将该节点和距离该节点距离最近的且局部密度大于该节点的点视作同一簇的元素

    for i in range(1,self.size):
    if self.clus[index[i]]==0:
        t=np.argmin(self.dist[index[i],index[0:i]])
        self.clus[index[i]]=self.clus[index[t]]

作图及分析

为了评估算法的运行结果，除了计算DBI（调用sklearn.metrics来计算）外，还要绘制决策图和聚类结果图以便可视化算法结果

  • 决策图，分别以rho,delta为坐标轴，绘制所有样本的散点图，图中delta值明显高于正常值的数值的点即为簇的中心点集，是按照rho的降序依次得到的

    fig = plt.figure() 
ax1 = fig.add_subplot(111)
ax1.set_title('Decision Plot') 
plt.xlabel('delta') 
plt.ylabel('rho') 
ax1.scatter(d.rho, d.delta,s=10) 
plt.show()

  • 聚类

    #聚类结果散点图
fig = plt.figure() 
ax1 = fig.add_subplot(111)
ax1.set_title('Scatter Plot') 
colors = d.clus
plt.xlabel('X') 
plt.ylabel('Y') 
ax1.scatter(data[:,0], data[:,1],c=colors,s=20,marker='o',cmap='tab20b',alpha=0.6) 
ax1.scatter(data[d.center,0], data[d.center,1],marker='x',c='Black') 
plt.show()

实验结果及分析

对三个输入进行处理，分别选用不同的超参数(dc,rho,delta)：

文件名 dc rho delta
Aggregation.txt 0.009 30 0.015
D31.txt 0.001 30 0.005
R15.txt 0.002 20 0.003
  • delta值偏大时，偏差较小时，对预测结果影响不大（因为数据分布的结果较好，簇与簇数据点之间的距离远大于簇内点的距离，delta略微浮动对结果影响不大）
  • delta值严重偏离理论值时（大于理论值100倍时较为明显），算法过程中会将不属于同一个簇的划分到同一个簇中，导致聚类结果变差
  • delta值偏小时，会导致算法将属于同一个簇中的点划分为多个簇，导致簇的数量剧增，也就导致聚类结果变差