一种改进的基于核密度估计的 DPC 算法 仇上正 张曦煌 江南大学物联网工程学院 摘 要： 快速搜索和找到密度峰 DPC (clustering by fast search and find of density peaks) 的聚类是一种新颖的算法, 它通过找到密度峰来有效地发现聚类的中心。DPC 算法的精度取决于对给定数据集的密度的精确估计以及对截止距离 dc (cutoff distance) 的选择。dc 主要是用于计算每个数据点的密度和识别集群中的边界点, 而 DPC 算法中 dc 的估计值却主要取决于主观经验值。提出一种基于核密度估计的 DPC 方法 (KDE-DPC) 来确定最合适的 dc 值。该方法通过引用一种新的 Solve-the-Equation 方法进行窗宽优化, 根据不同数据集的概率分布, 计算出最适合的 dc。标准聚类基准数据集的实验结果证实了所提出的方法优越于 DPC 算法以及经典的 K-means 算法、DBSCAN 算法和 AP 算法。关键词： 概率密度估计; 核密度估计; 类簇中心; 聚类; 作者简介：仇上正, 硕士生, 主研领域:计算机应用技术。作者简介：张曦煌, 教授。收稿日期：2016-12-22基金：江苏省产学研合作项目 (BY2015019-30) AN IMPROVED DPC ALGORITHM BASED ON KERNEL DENSITY ESTIMATIONQiu Shangzheng Zhang Xihuang School of Internet of Things Engineering, Jiangnan University; Abstract： Clustering by fast search and find of density peaks ( DPC) is a novel algorithm that efficiently discovers the centers of clusters by finding the density peaks. The accuracy of DPC depends on the accurate estimation of densities for a given dataset and also on the selection of the cutoff distance ( dc) . Mainly, dc is used to calculate the density of each data point and to identify the border points in the clusters. However, the estimation of dc largely depends on subjective experience. This paper presents a method based on kernel density estimation ( KDE-DPC) to determine the most suitable dc. This method performs window width optimization by referencing a new Solve-the-Equation method. According to the probability distributions of the different data sets, the optimal dc is obtained. The experimental results of standard clustering benchmark data sets confirm that the proposed method is superior to DPC algorithm, as well as classic Kmeans algorithm, DBSCAN algorithm and AP algorithm.Keyword： Probability density estimation; Kernel density estimation; Cluster center; Clustering; Received： 2016-12-220 引言聚类在知识发现和数据挖掘的领域中起着重要作用。聚类算法试图将大量数据分配成不同的不相交的类别, 其中更相似的数据点被分配到同一群集中, 而不相似的数据点被分组到不同的群集中1。聚类分析是一种无监督的机器学习方法, 在数据挖掘中, 有着很重要的应用, 在目前是重要的研究方向之一2。人们借助聚类分析, 不仅可以从大量数据中发现所需的知识与信息, 还可以降低工作量, 提升工作效率。目前, 世界上存在的聚类算法有层次聚类方法、分层聚类方法、基于密度的聚类方法和基于网格的聚类方法, 以及集成式聚类算法。在基于划分的算法中, K-means 算法是目前运用最广泛的算法之一3。然而, 严重依赖于初始聚类中心使得 K-means 算法的聚类结果难以满足目前人们的需求。首先 K-means 算法很难发现非凸形状的簇, 对噪声点和离群点敏感, 而且严重依赖初始设定的 K 值。目前, K-means 算法存在很大缺陷, 文献4-6提出了GKM (Global K-means) 算法等一系列改进的方法, 来优化 K-means 算法。2014 年 6 月, 由 Alex 和 Laio 在Science上发表了一种自动确定类簇数量和类簇中心的新型快速聚类算法, 简称 DPC7。DPC 算法存在两个优点:能快速发现任意形状数据集的密度峰值点 (即类簇中心) , 并且能够高效进行样本点分配, 还可以快速进行离群点剔除工作。因此, DPC 算法适用于大规模数据的聚类分析。然而, 该算法存在一个重大的问题, 在度量样本密度的时候, 该算法根据主观经验, 原文作者 Alex 选择 2%作为截断距离参数 dc 的值, 对聚类结果影响较大, 可能丢失聚类中心, 也可能无法识别所有核心点。为了弥补该算法的不足, 本文提出了一种改进的基于核密度估计的 DPC 算法 (KDE-DPC) 。为了减少因人为经验选取截断距离参数 dc 的因素对聚类结果造成的影响, 在计算核密度的时候, 我们通过引用一种新的 Solve-the-Equation 方法8来进行窗宽优化, 然后设计一套迭代算法得出最优窗宽, 利用最优窗宽从而产生较好的核密度估计结果。该方法避免了人工输入经验参数 dc 值的弊端, 根据不同数据集, 自动计算出最优窗宽, 提高了核密度计算的准确性, 同时还提高了样本分配边界点的结果。实验结果表明, 该算法能够提高聚类的准确性, 能准确识别所有聚类中心, 还能更好地分配边界点。1 相关研究1.1 DPC 算法快速搜索和发现样本密度峰值的聚类算法 (DPC) 能自动发现数据集样本的类簇中心, 实现任意形状数据集样本的高效聚类。其基本原理是:理想的类簇中心 (density peaks) 具备两个基本特征:1) 与邻居数据点相比, 类簇的中心点具有更大的密度;2) 与其他数据点相比, 类簇中心点之间的距离相对较大。对于一个数据集, DPC 算法引入了样本 i 的局部密度 i和样本 i 到局部密度比它大且距离它最近的样本 j 的距离 i, 来找到同时满足上述条件的类簇中心, DPC算法的有效性很大程度上取决于密度和 dc的准确估计。其定义如式 (1) 和式 (2) 所示:其中:d ij为样本 i, j 之间的欧氏距离, d c为截断距离, 当 x0 为一个平滑参数, 称作带宽 (bandwidth) 。Kh (x) = (1/h) K (x/h) 为缩放核函数。高斯核密度估计是一种常用的核密度估计方法:式 (5) 的性能在很大程度上取决于窗宽 h 的选择。均方积分误差被用来衡量估计 h 的最佳标准:高斯核密度估计具有一些限制, 例如, 敏感的参数 h (带宽) 难以选择、边界偏置, 以及欠平滑或过平滑等缺点。2 改进的 DPC 算法针对上述 DPC 算法的问题, 本文提出一种改进的基于核密度估计的密度峰快速聚类算法 (KDE-DPC) 。该算法包括各步骤:(1) 计算出核密度的最佳带宽 h;(2) 根据 h 计算每个点的密度 ;(3) 计算出每个点的距离 ;(4) 画出决策图;(5) 从决策图中选取聚类中心;(6) 将点分配给聚类中心;(7) 检查边界点, 形成聚类簇。2.1 最优带宽 h 的选择由文献8给出的核指数密度计算公式和核密度估计函数公式可以发现, d c相当于核密度估计函数公式中的窗宽 h, 我们想要得到最优的 dc, 可以转变为得到最优的窗宽 h。上面提到评价 h 优劣的标准为 MISE, 在弱假设下, 其中 AMISE 为渐进的 MISE, 而 AMISE 如下:为了使 MISE 最小, 则转化为求极小值问题, 如下:其中:通过式 (8) 得:对于高斯核函数, R (K) =1, m 2 (K) =1。对于 R (f) , 我们引入一种新的方法 Solve-the-Equation 方法对 R (f) 求解得:由于式 (10) 中, 在最优化 hopt的表达式中含有未知量 h, 因此, 我们设计一套迭代算法来计算最优的窗口值。令 hopt=F (h) , 则计算最优窗口宽度值如下:Step1 h1=F (h0) , h0=s, 对于 s 的初始值我们对在后面阐述。初始化参数 k, 其中 k 为一极小值。Step2 当h 1-h0k 时, 循环执行下面步骤: (1) 将 h1的值赋给 h0, 即执行h0=h1;(2) 对于新的 h0值, 利用表达式 h1=F (h0) 计算出新的 h1值;Step3 返回窗口宽度最优值 hopt=h1。对于 s 的确定, 我们采用如下标准:其中:n 为样本观察值的个数, 为样本观察值的标准差。2.2 算法性能分析本文改进的算法复杂度主要由下面几个方面决定:1) 计算样本之间的距离, 此过程的时间复杂度为 O (n) ;2) 计算 hopt, 时间复杂度为 O (n) ;3) 迭代求出最优 h, 时间复杂度为 O (n) 。因此经过对比分析, 相比于原算法, 改进后的算法复杂度一样。3 实验结果与分析3.1 人工数据集实验结果分析为了评估我们提出的 KDE-DPC 方法的效果, 我们将提出方法的实验结果与 DPC算法的结果作对比。所用的人工数据集如表 1 所示。DPC 算法是文献7作者提供的源代码。本文 KDE-DPC 算法采用 Matlab R2010a 实现。本实验的所有实验运行环境均为 Win 864 bit 操作系统, Matlab R2010a 软件, 12 GB 内存, Intel (R) Core (TM) 2 Quad CPU I5-5200U2.7 GHz。表 1 数据集的基本信息 下载原表 为了能更全面地展现本算法的效果, 我们采用对比实验来分析算法。图 3 展现的是提出的 KDE-DPC 算法与 DPC 算法分别在 D31 数据集和 R15 数据集上做纵向对比实验的结果。图 3 DPC 算法与 KDE-DPC 算法对 R15 数据集和 D31 数据集的聚类结果 下载原图图 3 DPC 算法与 KDE-DPC 算法对 R15 数据集和 D31 数据集的聚类结果 下载原图从图 3 中, 我们可以发现提出的 KDE-DPC 算法能够更好地处理噪声点, 准确分配样本点。表 2 展示了本文提出的 KDE-DPC 算法与 DPC 算法在识别聚类点和错误分类点方面的详细比较。从表中可以发现 KDE-DPC 算法无论数据集的性质如何, 都能准确识别聚类群的核心点。表 2 对