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

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

以相同的方式构建并遍历所有的树,得到 x 3 和 x 7 的块值总和,求平均即得到 x 3 和 x 7 的不相似性.
2.2 DDPC算法介绍
本文 DDPC 算法将继续采用 DPC 的中心思想,快速寻找局部密度以及相对距离属性均较大的点作为聚类
中心,但是相似度计算以及局部密度的度量方式我们将进行改进.首先,样本间相似性度量将使用基于块的不相
似性度量代替简单的几何距离度量,根据公式(9)得出新的相似度矩阵;然后根据新的相似度矩阵,找到样本的 K
个最接近的匹配近邻,并定义新的局部密度.
ρ = i exp( mx x− ∑ e ( , j )) (10)
i
∈
jKNN () i
其中,KNN(i)是点 i 的 k 个近邻点.同时,数据样本的相对距离属性也不再依赖几何距离度量的相似度,而是利用
公式(9)计算得到的相似度.
⎧ min (mx i j j ∃ ρ > i ρ j
( , )), if s.t. x
: j ρ ⎪
e
δ = ⎨ j ρ > i (11)
i
( ,
⎪ ⎩ max(mx x j )), otherwise
e
i
j
DDPC 算法具体步骤如算法 2.
算法 2. DDPC 聚类算法.
输入:数据集 X={x 1 ,x 2 ,…,x n },iTree 的数目 t,每棵 iTree 的大小ψ,近邻数 k.
输出:聚类结果 Y.
步骤:
Step 1. 将数据集 X 通过随机采样分为 t 个大小为ψ的集合,如果 n<ψ值,则采样的大小取 n.
Step 2. 对每个集合,根据算法 1 进行轴平行分割,构成 1 棵 iTree,t 棵 iTree 构成 1 个 iForest.
Step 3. 遍历 iForest,根据公式(9),基于块的不相似性度量方式计算样本相似度矩阵.
Step 4. 根据重新定义的局部密度的计算公式(10),计算每个样本的ρ i 值.
Step 5. 根据公式(11)计算每个样本的δ i 值.
Step 6. 根据由ρ i 和δ i 构成的决策图,自动选择聚类中心.
Step 7. 将数据集中的其余数据点归于密度等于或者高于“当前点”的最近点一类.
Step 8. 返回结果矩阵 Y.
DDPC 算法保留了 DPC 算法寻找聚类中心的主要步骤,快速寻找密度峰值作为聚类中心.但是本文 DDPC
算法局部密度以及相对距离属性的度量依赖于更符合人类心理的基于块的不相似性度量方式计算得到的样本
间相似度,代替了传统 DPC 算法中简单的距离度量得到的相似度,使 DDPC 在高维数据以及密度不均匀数据集
上更高效.另外,利用基于块的不相似性度量计算的数据样本间的相似性,定义了基于样本 K 近邻的新的局部密
度.与 DPC 算法相比,DDPC 算法避免了过度依赖截断距离 d c ,并且局部密度度量适合于任意大小的数据集.

3 实验与分析

3.1 实验设计
为了验证 DDPC 算法的聚类性能,实验采用人工数据集和真实数据集对本文算法进行测试.聚类精度(Acc)
被用来测量聚类结果的质量,Acc 的值越高,聚类性能越好.Acc 的计算公式如下.
Acc = ∑ N δ (,y map ( ))z n (12)
i= 1 i i
对于数据集 X={x 1 ,x 2 ,…,x n },y i ,z i 分别是固有类标签和聚类结果标签,map(⋅)通过 Hungarian 算法将每个类标签映
射到类别标签,并且该映射是最优的.除了 DPC 算法,我们将 DDPC 算法与 DPC 的优化算法 FKNN-DPC 以及
DPC-KNN 进行对比,对比算法的实验结果均采用 Acc 统一标准进行准确率度量.由于我们的算法没有考虑噪声
点处理,所以为了公平起见,我们选择无噪声数据集,见表 1 和表 2,对比算法也均不处理噪声点.另外,DPC 算法的
参数取值参考文献[10],为[0.2%,0.4%,0.6%,1%,2%,4%,6%];FKNN-DPC 算法以及 DPC-KNN 算法中的 k 值参考