Page 8 - 《软件学报》2020年第11期

3324 Journal of Software 软件学报 Vol.31, No.11, November 2020

DPC
28
26
24
22
20
18
16
14
0 5 10 15
X
(a) 采用公式(2),d c=4%的聚类结果 (b) 采用公式(1),d c=4%的聚类结果 (c) 采用公式(2),d c=2%的聚类结果
Fig.2 Clustering results of DPC on the Flame with different local density and different cutoff distance d c
图 2 DPC 在 Flame 上采用不同局部密度和截断距离 d c 的聚类结果

从图 2 可以看出,局部密度的计算影响了 DPC 在数据集上的聚类效果.
许多学者针对局部密度的计算方式进行了 DPC 优化.在文献[20]中,Du 等人提出了基于 K 近邻的密度峰值
聚类(DPC-KNN)算法,将 K 近邻的概念引入到 DPC 中,考虑数据的局部分布,为计算局部密度提供了另一种选
择,从而统一局部密度的度量方式,减少截断距离 d c 对聚类结果的影响.在文献[21]中,Xie 等人提出了一种基于
模糊加权 K 近邻(FKNN-DPC)的密度峰值搜索和点分配算法,使用 K 近邻信息来定义点的局部密度并搜索和发
现聚类中心,从而统一局部密度的度量方式,并减少截断距离 d c 对聚类结果的影响.在文献[22]中,谢娟英等人提
出了 K 近邻优化的密度峰值快速搜索聚类算法,利用样本的 K 近邻信息重新定义局部密度属性和分配策略,有
效地改进了局部密度度量不理想的弊端.
受以上优化算法的启发,本文提出了基于不相似性度量优化的密度峰值聚类算法(DDPC).DDPC 算法首先
利用概率块代替原来的几何距离计算新的相似度矩阵,而后利用新的相似度矩阵获取数据样本的 K 近邻信息,
再根据样本的 K 近邻重新定义局部密度的度量方式.由于 DDPC 算法基于新的不相似性度量方式计算相似度
矩阵,充分考虑了数据分布的局部环境,所以可以反映更准确的数据结构,在高维数据集以及密度变化的数据集
上可以得到更优的聚类结果.同时,由于 DDPC 算法定义了新的局部密度,统一了局部密度在任意大小数据集上
的度量方式,避免了 DPC 算法中截断距离 d c 对聚类结果的影响.
2 基于不相似性度量优化的密度峰值聚类算法

2.1 基于块的不相似性度量
由上一节分析得出,DPC 算法由于直接采用几何距离度量数据样本之间的相似度从而计算局部密度以及
相对距离属性,忽略了数据分布的周围环境,所以在复杂数据集,特别是高维数据以及密度不均匀数据集上,DPC
算法聚类效果不尽如人意.自 1970 年代开始,心理学家就表示,两个实例的相似性不能简单地由几何模型表征,
相似性的度量受到测量的背景以及实例附近的点的影响 [23] .基于这个事实,可以定义更合适的相似性度量方式,
在这里称为基于块的不相似性度量 [24] .
基于块的不相似性度量的基本思想是,密集区域的两个实例的相似度小于同等间隔但位于低密度区域的
两个实例 [25] .基于几何模型的相似度计算仅依赖于几何位置推导距离;相反,基于块的不相似性的度量方式主要
取决于数据分布,即覆盖两个实例的最小区域的概率块 [26] .假设 D 表示概率密度函数 F 中的数据样本,H∈H(D)
表示一个层次划分,将空间划分成不重叠的非空域.
定义 1. R(x,y|H;D)表示关于 H 和 D 覆盖 x 和 y 的最小域,定义为
R (, |xy H ; )D = argmin ∑ ( I z ∈ ) r (6)
rH⊂ s.t. { , }x y ∈ r zD∈
其中,I(⋅)表示指数函数.
定义 2. x 和 y 关于 D 和 F 的基于块的不相似性定义为 R(x,y|H,D)的期望概率.