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

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

从图 4 中可以看出,DDPC 可以很好地处理密度不均匀的数据集.在数据集 D 上,DDPC 算法可以很好地聚
类成 3 类.但是 DPC 不能很好地将数据集分成 3 类,因为 DPC 只是简单地用数据间的几何距离来度量相似度,
计算局部密度和相对距离属性,所以对于数据集分布不均匀的数据集,DPC 不能很好地识别所有的类.而 FKNN-
DPC 算法虽然考虑了样本的 K 近邻度量局部密度,但是 K 近邻的判断依旧是根据简单的几何距离度量的相似
性判断的近邻点,所以针对密度不均匀的分布数据集,FKNN-DPC 算法的聚类结果也不是很理想.同样,DPC-
KNN 算法也引入的 K 近邻信息是依据样本间的相似性判断的,但是相似性的判断只是依赖数据的几何距离,所
以聚类效果不尽如人意.
从图 5~图 7 中可以看出:虽然在分布相对均匀的数据集上,DDPC 以及 DPC 和 FKNN-DPC,DPC-KNN 算法
均可以通过选择合适的参数得到较为满意的聚类结果,但是 DPC 算法中局部距离的度量方式不统一,并且需要
选择合适的 d c .而 DDPC 算法以及 FKNN-DPC 和 DPC-KNN 统一了局部密度的度量方式,并且不再需要选择参
数 d c .虽然依旧有参数 k,但是 k 值的变化对聚类中心的选择影响不大,即对聚类结果的影响不是很大.
从图 8 中可以看出:DDPC 和 DPC 算法可以得到令人满意的聚类结果,但是 FKNN-DPC 和 DPC-KNN 算法
的聚类结果不是很理想.DPC 算法考虑聚类中心的特点,从全局角度出发选择聚类中心,所以可以准确处理类之
间有交叉的数据集.虽然 FKNN-DPC 和 DPC-KNN 引入数据样本的 K 近邻统一局部密度的度量方式,不再需要
参数 d c ,但是 FKNN-DPC 和 DPC-KNN 只是简单进行几何距离的度量选择 K 近邻,忽略了数据分布的周围的环
境,所以当数据集类之间有交叉,分布紧密的时候结果不理想.而本文 DDPC 算法虽然也是考虑样本的 K 近邻度
量局部密度,但是由于 K 近邻的度量不再简单根据几何距离度量,而是使用了基于块的不相似性度量,考虑了数
据分布的周围环境,所以 DDPC 可以和 DPC 一样,针对 FKNN-DPC 和 DPC-KNN 聚类结果不理想的类有交叉的
数据集上聚类的结果还是相对较满意.
各算法虽然在大部分分布规则、密度均匀的数据集上聚类效果都差强人意,但是 DPC 算法局部密度和相
对距离简单依赖几何距离度量的相似度,使得 DPC 算法在密度不均匀的数据集上聚类效果不尽如人意,同时在
高维数据集上的聚类结果也不是很理想,将在下节实验证明.另外,局部密度的度量方式不统一,d c 的选择对聚类
结果的影响,使得 DPC 算法在实际操作中需要一定的先验知识.而 FKNN-DPC 和 DPC-KNN 虽然统一了局部密
度的度量方式,同时去除了 d c 改变对聚类结果的影响,但是由于引入的 K 近邻信息也只是简单依靠几何距离度
量寻得,而忽略了数据分布的周围环境,所以当数据分布复杂,有交叉、密度不均匀时,FKNN-DPC 和 DPC-KNN
的聚类结果不是很理想.而本文提出的 DDPC 聚类算法在引入 K 近邻的基础上又考虑数据分布的周围环境度
量样本间的相似性,所以本文 DDPC 算法在处理密度不均匀以及类间有交叉点时效果较理想,同时统一了局部
密度的度量方式,克服了 d c 改变对聚类结果的影响,并且 DDPC 本身只有一个参数 k 需要选择,而由于 DDPC 依
旧采用 DPC 中选择聚类中心的特点选取密度峰值,所以聚类中心一定处于密度较大的区域,所以 k 的微小改变
对聚类的结果影响不大.
3.2.2 真实数据集实验结果分析
本节对 6 组人工数据集进行 DDPC 测试,实验数据特征见表 2.由于 DPC 算法中 d c 的改变对小样本数据集
上聚类的结果影响较大,同时,在数据维度较高的数据集上 DPC 的聚类结果不尽如人意,所以本节实验挑选了经
典的小样本数据集,并且包含较高的维度.
实验分别将本文 DDPC 算法和 DPC 算法以及 FKNN-DPC 算法和 DPC-KNN 算法在以上 6 个数据集上进
行了聚类,聚类结果见表 3,并且给出了对应的最佳参数.粗体即为各算法中最优结果,而 DDPC 同时在括号中给
出了 20 次测试均值.
从表 3 可以看出,本文 DDPC 算法整体的聚类效果较 DPC 以及 FKNN-DPC 和 DPC-KNN 更好.而 DPC 在
维度较高的数据集上聚类结果不是很满意,而且 d c 需要合适的选择.虽然 FKNN-DPC 和 DPC-KNN 算法避免了
传统 DPC 算法中参数 d c 的选择,结果较 DPC 相比差强人意,但是与 DDPC 算法相比,聚类结果不是很理想.本文
DDPC 算法由于考虑数据分布的周围环境,用基于块的不相似性度量代替了简单的几何距离度量相似度的方
式,所以本文 DDPC 算法在针对数据维度较高的数据集效果较好.另外,由于 DDPC 也选择考虑 K 近邻来度量局