论文部分内容阅读
摘 要：2014年6月发表在Science的密度峰值聚类算法（DPC）是基于密度的新型聚类算法，算法不需要迭代过程，具有更高效率。但是DPC算法计算密度时人为设定截断距离和人工选取簇类中心带有主观因素，因此本文提出一种基于K近邻的密度峰值聚类算法。首先根据k近邻思想计算截断距离和样本点的局部密度值，然后通过综合变量的排序选取簇类中心，最后将剩余的数据点划分到适当的簇类并进行噪声点检测。在人工测试数据集和UCI真实数据集的实验显示，基于K近邻的密度峰值聚类算法的聚类结果优于DPC算法以及经典算法K-means和DBSCAN。
关键词：密度峰值；K近邻；局部密度；截断距离；聚类
引言
聚类主要用作无监督学习方法，是数据挖掘的一项主要技术。聚类方法包括划分聚类、分层聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类或这些方法的组合。K-means是一种经典的划分聚类方法，K-means无法识别任意形状的簇。DBSCAN是一种基于密度的聚类方法，可以检测任意形状的聚类，但是阀值的选择依赖经验知识。
2014年Science发表了一种新的基于密度峰值聚类方法（DPC），簇类中心基于以下假设：簇类中心被邻近局部密度较低的数据点所包围，并且与任何具有较高局部密度的数据点相距较远。
DPC算法虽然简单高效，但是存在以下不足：截断距离的选取影响密度的计算和噪声点的检测，人为设定截断距离影响聚类结果；人工判断簇类中心带有主观因素，降低算法的鲁棒性。针对DPC算法的不足，本文提出基于K近邻的密度峰值聚类算法（KNN-DPC），首先根据k近邻思想计算截断距离和样本点的局部密度值，然后通过综合变量的排序选取簇类中心，最后将剩余的数据点划分到适当的簇类并进行噪声点检测。实验证明本文算法较之DPC算法、K-means算法和DBSCAN具有更优的聚类结果。
一、DPC算法
采用决策图的方法选择簇类中心，选择局部密度和距离均较大的样本点为簇类中心。
对于剩余数据样本点，DPC算法将其归并到密度比其大且距其最近的簇类。
虽然DPC算法能简单高效的处理聚类问题，但是DPC算法中局部密度值的计算和噪声点的判断依赖截断距离，人为设定的截断距离使得聚类结果差异很大，而且人工选取簇类中心会出错的可能性。
二、基于K近邻的密度峰值聚类算法
（一） K近邻思想
对于基于k近邻的局部密度计算，更容易区分核心区域中的点与其他领域的点，有助于聚类获得更准确的结果。因此本文将k近邻思想与DPC聚类算法相结合，计算DPC算法中的局部密度值ρi以及截断距离dc。
（二）簇类中心的选择
根据簇类中心的两个基本特点，考虑构建综合变量ri从而选取簇类中心。
γi值越大表示数据点越有可能成为数据中心点。因此只需对γ值进行降序排列，从前往后截取K个数据点作为簇类中心。
（三）算法描述
本文提出k近邻密度峰值聚类算法，有效改进了DPC算法的不足，以下是KNN-DPC算法的描述。
输入：数据集D，聚类数K ，近邻数k，敏感系数
输出：数据点的类标签C
1.计算数据集D的距离矩阵，根据距离远近筛选出每个数据点的k个最近邻并计算截断距离dc
2. 计算D中每个数据点的局部密度ρi和距离δi
3. 计算综合变量γi并进行降序排序，选择前K个数据点作为聚类中心
4.对K个类中心进行标签和对非聚类中心数据点归类
5.判断噪声点，为每个类计算平均局部密度上界，若该类的边界点密度低于平均局部密度上界，则判断为噪声点。
三、实验结果分析
为了验证本文算法的性能，分别使用人工数据集和UCI数据集进行实验。
（一）人工数据集
本文选取了Spiral、Compoud、D31和S1四类人工测试数据进行实验，每个数据集的前两个实验是DPC算法不同的p值取得的聚类结果，后一个实验是本文算法取得的聚类结果，黑色点表示噪声点。
从图1结果显示，本文算法能得出符合数据集分布和直观判断的聚类结果，能有效识别任意形状的数据集。对于Spiral、D31、S1三个数据集，DPC算法能取得准确的簇类中心，且p值越小，噪声污染越小，聚类效果越好。但是p值并非越小越好，p值越小则决策图中簇类中心点与其他中心点越难区分。而对于Compound数据集，DPC算法无法识别圆环中的簇类，而本文算法能准确识别圆环中的簇类。人工数据集的实验结果显示，本文算法有效避免DPC算法中截断距离难以选取和决策图中人工选取簇类中心出错的情况，具有更好的聚类效果。
（二）UCI数据集
为了验证本文算法在真实数据集上的聚类效果，将本文算法与DPC、K-means和DBSACN算法分别在UCI数据集的Iris、Wine、Pima和Sonar四个UCI数据集上进行测试，最后采用F-measure和Purity指标进行聚類评价。
如图2实验结果所示，本文算法较之DPC、K-means和DBSACN算法，在F-measure值和Purity值对比上，在四个数据集上的实验效果均优于比较算法。综上所述，本文算法在人工数据集上优于DPC算法，在真实数据集上的聚类效果均优于DPC、K-means和DBSACN，具有更高的聚类精度。
四、结束语
本文提出一种基于K近邻的密度峰值聚类算法，使用K近邻思想计算局部密度，克服了截断距离对密度计算的影响。其次截断距离通过k近邻值计算得出，避免了人为设定的缺陷，最后通过综合变量来选取簇类中心，避免了决策图人工选取簇类中心的主观性。人工数据集和UCI真实数据集的实验结果表明，KNN-DPC算法能准确识别簇类中心，能发现任意形状的簇类，具有更高的聚类精度。然而如何合理确定KNN-DPC算法中近邻样本数需要更进一步的研究。
参考文献：
[1]R.Xu，I.Wunsch D，Survey of clustering algorithms[J]，Neur. Netw.IEE Trans.2005，16（3）：645-678
[2]A.K.Jain.Data clustering：50 years beyond k-means[J]，Pattern Recognit.Lett.2010，31（8）：651-666
[3]A.Rodriguez，A.Laio.Clustering by fast search and find of densitypeaks[J]，Science.2014，344（6191）：1496
[4] Liu Yaohui，Ma Zhengming，Yu Fang.Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy.[J]， Knowledge-Based Systems.2017.133：208-220
[5] Vidar V.Vikjord，Robert Jenssen.Information theroretic clustering using a k-nearest neighbors approach[J]，Pattern Recognition.2014，47（9）：3070-3081
作者简介：
曾嘉豪（1992-），男，籍贯：广东， 学历：硕士研究生，研究方向：聚类分析。
关键词：密度峰值；K近邻；局部密度；截断距离；聚类
引言
聚类主要用作无监督学习方法，是数据挖掘的一项主要技术。聚类方法包括划分聚类、分层聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类或这些方法的组合。K-means是一种经典的划分聚类方法，K-means无法识别任意形状的簇。DBSCAN是一种基于密度的聚类方法，可以检测任意形状的聚类，但是阀值的选择依赖经验知识。
2014年Science发表了一种新的基于密度峰值聚类方法（DPC），簇类中心基于以下假设：簇类中心被邻近局部密度较低的数据点所包围，并且与任何具有较高局部密度的数据点相距较远。
DPC算法虽然简单高效，但是存在以下不足：截断距离的选取影响密度的计算和噪声点的检测，人为设定截断距离影响聚类结果；人工判断簇类中心带有主观因素，降低算法的鲁棒性。针对DPC算法的不足，本文提出基于K近邻的密度峰值聚类算法（KNN-DPC），首先根据k近邻思想计算截断距离和样本点的局部密度值，然后通过综合变量的排序选取簇类中心，最后将剩余的数据点划分到适当的簇类并进行噪声点检测。实验证明本文算法较之DPC算法、K-means算法和DBSCAN具有更优的聚类结果。
一、DPC算法
采用决策图的方法选择簇类中心，选择局部密度和距离均较大的样本点为簇类中心。
对于剩余数据样本点，DPC算法将其归并到密度比其大且距其最近的簇类。
虽然DPC算法能简单高效的处理聚类问题，但是DPC算法中局部密度值的计算和噪声点的判断依赖截断距离，人为设定的截断距离使得聚类结果差异很大，而且人工选取簇类中心会出错的可能性。
二、基于K近邻的密度峰值聚类算法
（一） K近邻思想
对于基于k近邻的局部密度计算，更容易区分核心区域中的点与其他领域的点，有助于聚类获得更准确的结果。因此本文将k近邻思想与DPC聚类算法相结合，计算DPC算法中的局部密度值ρi以及截断距离dc。
（二）簇类中心的选择
根据簇类中心的两个基本特点，考虑构建综合变量ri从而选取簇类中心。
γi值越大表示数据点越有可能成为数据中心点。因此只需对γ值进行降序排列，从前往后截取K个数据点作为簇类中心。
（三）算法描述
本文提出k近邻密度峰值聚类算法，有效改进了DPC算法的不足，以下是KNN-DPC算法的描述。
输入：数据集D，聚类数K ，近邻数k，敏感系数
输出：数据点的类标签C
1.计算数据集D的距离矩阵，根据距离远近筛选出每个数据点的k个最近邻并计算截断距离dc
2. 计算D中每个数据点的局部密度ρi和距离δi
3. 计算综合变量γi并进行降序排序，选择前K个数据点作为聚类中心
4.对K个类中心进行标签和对非聚类中心数据点归类
5.判断噪声点，为每个类计算平均局部密度上界，若该类的边界点密度低于平均局部密度上界，则判断为噪声点。
三、实验结果分析
为了验证本文算法的性能，分别使用人工数据集和UCI数据集进行实验。
（一）人工数据集
本文选取了Spiral、Compoud、D31和S1四类人工测试数据进行实验，每个数据集的前两个实验是DPC算法不同的p值取得的聚类结果，后一个实验是本文算法取得的聚类结果，黑色点表示噪声点。
从图1结果显示，本文算法能得出符合数据集分布和直观判断的聚类结果，能有效识别任意形状的数据集。对于Spiral、D31、S1三个数据集，DPC算法能取得准确的簇类中心，且p值越小，噪声污染越小，聚类效果越好。但是p值并非越小越好，p值越小则决策图中簇类中心点与其他中心点越难区分。而对于Compound数据集，DPC算法无法识别圆环中的簇类，而本文算法能准确识别圆环中的簇类。人工数据集的实验结果显示，本文算法有效避免DPC算法中截断距离难以选取和决策图中人工选取簇类中心出错的情况，具有更好的聚类效果。
（二）UCI数据集
为了验证本文算法在真实数据集上的聚类效果，将本文算法与DPC、K-means和DBSACN算法分别在UCI数据集的Iris、Wine、Pima和Sonar四个UCI数据集上进行测试，最后采用F-measure和Purity指标进行聚類评价。
如图2实验结果所示，本文算法较之DPC、K-means和DBSACN算法，在F-measure值和Purity值对比上，在四个数据集上的实验效果均优于比较算法。综上所述，本文算法在人工数据集上优于DPC算法，在真实数据集上的聚类效果均优于DPC、K-means和DBSACN，具有更高的聚类精度。
四、结束语
本文提出一种基于K近邻的密度峰值聚类算法，使用K近邻思想计算局部密度，克服了截断距离对密度计算的影响。其次截断距离通过k近邻值计算得出，避免了人为设定的缺陷，最后通过综合变量来选取簇类中心，避免了决策图人工选取簇类中心的主观性。人工数据集和UCI真实数据集的实验结果表明，KNN-DPC算法能准确识别簇类中心，能发现任意形状的簇类，具有更高的聚类精度。然而如何合理确定KNN-DPC算法中近邻样本数需要更进一步的研究。
参考文献：
[1]R.Xu，I.Wunsch D，Survey of clustering algorithms[J]，Neur. Netw.IEE Trans.2005，16（3）：645-678
[2]A.K.Jain.Data clustering：50 years beyond k-means[J]，Pattern Recognit.Lett.2010，31（8）：651-666
[3]A.Rodriguez，A.Laio.Clustering by fast search and find of densitypeaks[J]，Science.2014，344（6191）：1496
[4] Liu Yaohui，Ma Zhengming，Yu Fang.Adaptive density peak clustering based on K-nearest neighbors with aggregating strategy.[J]， Knowledge-Based Systems.2017.133：208-220
[5] Vidar V.Vikjord，Robert Jenssen.Information theroretic clustering using a k-nearest neighbors approach[J]，Pattern Recognition.2014，47（9）：3070-3081
作者简介：
曾嘉豪（1992-），男，籍贯：广东， 学历：硕士研究生，研究方向：聚类分析。