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

丁世飞 等:基于不相似性度量优化的密度峰值聚类算法 3323

⎛ d ⎞ 2
ρ = i exp − ∑ ⎜ ⎜ ij 2 ⎟ ⎟ (2)
j ⎝ d c ⎠
数据点 x i 的δ i 是点到所有比其局部密度大的点的距离的最小值,其公式为
δ = min j : j ρ i ρ > (d ij ) (3)
i
对于密度最大的点,我们可以得到:
δ i =max j (d ij ) (4)
DPC 算法选择ρ i 和δ i 均较大的数据点作为聚类中心.为了可以自动确定聚类中心,DPC 算法借助决策图选
择聚类中心.决策图的绘制以ρ i 为横坐标,δ i 作为纵坐标.在实际情况中,为了有助于更准确地确定聚类中心,算法
定义一个参数γ i .
γ i =ρ i ⋅δ i (5)
此时,DPC 算法将根据γ i 绘制决策图,选择γ i 大的点作为聚类中心.
DPC 算法确定好聚类中心后,需要将剩余的点分配到相应的类簇中.剩余的点分为一般的数据点以及噪声
点.DPC 算法首先将所有剩下的点归于局部密度等于或者高于其最近点一类,而后为每一个类簇定义一个边界
阈值,边界阈值即为划分为该类但是距离其他类簇的点的距离小于 d c 的点,然后将局部密度最大的点的值作为
阈值,小于该阈值的点将作为噪声点去除完成聚类.
DPC 算法简单有效,能够很好地处理噪声孤立点,而且可以得到任意形状的簇聚类,同时不需要提前指定数
据中类簇的数量,并且需要用户指定的参数比较少,因此近几年得到了很多学者的关注.在 DPC 的应用方面,
2015 年,Zhang 等人 [17] 利用密度峰值聚类算法提取多文档摘要,提出了一个同时测量代表性和多样性的统一句
子评分模型,优于现有的 MDS 方法;2016 年,Chen 等人 [18] 使用 DPC 算法来获得基于人脸图像的可能年龄估
计;2017 年,Shi 等人 [19] 将 DPC 算法应用于场景图像聚类,提出了一种新颖的基于聚类的图像分割方法,能够捕捉
图像的固有结构并检测非球形簇.
虽然 DPC 算法在大部分数据集上的聚类结果令人满意,但是 DPC 的缺点也非常明显.
• 首先,局部密度和相对距离的计算都依赖简单的距离度量,所以当数据分布不均匀和数据维度较高
时,DPC 无法得到满意的聚类结果.例如图 1 所示,在 3 类密度不均匀的数据集上,DPC 的聚类结果不尽
如人意,无法得到准确的 3 类.
• 其次,局部密度的计算没有统一的度量,根据不同的数据集大小,需要选择公式(1)或者公式(2)度量.同
时,局部密度的计算依赖于截断距离 d c 的选择,但是 d c 只考虑数据的全局分布,忽略了数据的局部信息,
所以 d c 的改变会影响聚类的结果,尤其是在小数据集上.例如图 2 所示,在小数据集 Flame 上,图 2(a)是
采用公式(2)计算局部密度,并且截断距离 d c 取 4%,可以很好地将数据集分成两类;而图 2(b)中,d c 取值
和图 2(a)一样,取 4%,但是局部密度的度量采用公式(1),则并不能得到满意的聚类结果;图 2(c)采用和图
2(a)相同的方法计算局部密度,但是截断距离取 2%,得到的聚类结果也不是很理想.
DPC
40
35
30
25
20
15
10
5
0
0 5 10 15 20 25
X
Fig.1 Clustering result of DPC on non-uniform density dataset
图 1 DPC 在密度不均匀数据集上的聚类结果