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

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

datasets, ignoring the local information of the data, so the change of d c will affect the results of clustering, especially on small scale
datasets. Aiming at these shortcomings, this study proposes an optimized density peaks clustering algorithm based on dissimilarity
measure (DDPC). DDPC introduces a mass-based dissimilarity measure to calculate the similarity matrix, and calculates the k-nearest
neighbor information of the sample based on the new similarity matrix. Then local-density is redefined by the k-nearest neighbor
information. Experimental results show that the optimized density peaks clustering algorithm based on dissimilarity measure is superior to
the optimized FKNN-DPC and DPC-KNN clustering algorithms, and can be satisfied on datasets with uneven density and higher
dimensions. As a result, the local-density measurement method is unified at the same time, which avoids the influence of d c on the
clustering results in the traditional DPC algorithm.
Key words: density peaks clustering; local-density; decision graph; dissimilarity measure; uneven density

聚类分析是数据挖掘的有效技术之一,因为聚类分析不依赖于类的预先定义以及数据样本的标签,所以被
[1]
称为无监督学习 .目前,聚类分析在市场分析、模式识别、基因研究、图像处理等领域具有一定的应用价值 [2−4] .
聚类分析的主要目标是:根据某种相似性(不相似性)度量把数据对象分成多个类,尽可能使同一类簇内样
[5]
本的相似度较大,不同类簇之间样本的相似度较小 .然而,相似性的度量至今没有统一的定义,不同的数据类型
[6]
对应不同的相似性度量定义,得到不同的聚类结果 .类似地,不同的聚类目标对应不同的聚类算法,目前,聚类
[7]
算法主要被分为基于划分的聚类、基于密度的聚类、基于网格的聚类、基于层次以及基于模型的聚类 .这 5
[8]
大类算法各有利弊,不同的算法适用于不同类型的数据集.例如,经典的 K 均值 聚类算法在凸球形结构的数据
[9]
集上具有满意的聚类结果,但却对初始值的设置敏感;尽管 DBSCAN 在不规则簇簇上提供了良好的聚类结果,
并且不需要预先设定类簇数,但对于密度分布不均匀和高维较高的数据集,聚类结果不尽如人意.
2014 年,Rodriguez 等人 [10] 提出一种快速寻找聚类中心的密度峰值聚类算法(clustering by fast search and
find of density peaks,简称 DPC).DPC 算法利用数据的局部密度以及相对距离属性快速确定聚类中心,可以用于
任意形状数据的聚类分析,并有效进行样本点分配,得到比较满意的聚类结果 [11] .但是它存在以下不足.
(1) 局部密度和相对距离的计算基于数据之间的相似性,而相似性的度量却只是简单依赖于数据之间的
几何距离,所以在复杂数据上,DPC 无法得到满意的聚类结果,特别是当数据分布不均匀和数据维度
较高时 [12] .
(2) 局部密度的计算没有统一的度量,根据不同的数据集大小,需要选择不同的度量方式 [13] .
(3) 截断距离 d c 的度量只考虑数据的全局分布,在小数据集上,d c 的改变会影响聚类的结果 [14] .
针对以上不足,本文提出一种基于不相似性度量优化的密度峰值聚类算法(optimized density peaks
clustering algorithm based on dissimilarity measure,简称 DDPC).DDPC 算法的主要创新点包括:(1) 考虑数据分
布的周围环境,利用概率块代替几何距离度量数据之间的相似性,提高数据在较高维度以及分布不均匀数据集
上的聚类精度;(2) 利用样本的 K 近邻信息重新定义局部密度,统一不同大小数据集上局部密度的度量方式;
(3) 改进的局部密度度量,使 DDPC 算法的聚类结果不受截断距离 d c 变化的影响.
1 DPC 聚类算法

一种基于局部密度和相对距离的密度聚类算法 DPC 由 Rodrigue 等人在 Science 上提出.DPC 算法基于一
个重要假设:聚类中心的局部密度大于周围邻居的局部密度;聚类中心的距离密度比其高的点的距离相对较
远 [15] .DPC 算法分为两个步骤完成聚类:(1) 确定聚类中心;(2) 分配剩下的点 [16] .
DPC 算法首先根据聚类中心的特点为每一个数据点赋予局部密度ρ i 和相对距离δ i 属性.ρ i 的物理意义表示
与点 x i 的距离小于 d c 的点的个数,定义为

ρ i χ = (d − ∑ ij d c ), χ ( )x = ⎧ ⎨ 1, x < 0 (1)
j ⎩ 0, x≥ 0
其中,d ij 表示数据点 x i 和 x j 的距离.d c 是唯一的输入参数,表示截断距离,定义为两两数据点之间相似度按从小到
大排列后 2%位置处的值.另外,当数据集较小时,局部密度ρ i 以高斯核函数的形式被定义.