聚类算法^[1,2]根据数据之间的相似性对数据进行分组, 主要目的是最大化属于同一簇的数据之间的相似性和属于不同簇的数据之间的不相似性. 在现实生活中, 聚类是数据挖掘^[3]、图像处理^[4,5]、社交网络^[6]、生物信息学^[7]等领域的一个活跃的研究课题, 还在医学等方面具有重要的作用^[8]. 针对不同的应用, 已经提出了各种聚类算法, 如基于层次、划分、模型、网格和密度的算法, 文献[9,10]对各种聚类算法进行了详细描述.

国内外也有很多基于图的聚类算法被提出. 例如文献[11,12]通过构造 k最近邻图, 也有算法^[13,14]利用最小生成树(MST)进行聚类. Zahn ^[13]提出的基于最小生成树的聚类算法将不一致边定义为那些权重明显大于子树中邻近边的平均权重的边.

针对不同的应用场景, 已经提出了广泛的聚类算法. 然而, 由于问题的多样性和数据分布的复杂性, 这些算法并不总是令人完全满意. 基于划分的聚类算法是最基本的聚类方法, 其中K-means算法^[15]是划分聚类算法中的经典代表. 该算法简单易用, 倾向于将数据聚类成球形, 但对于具有任意形状的簇来说显然不足够. 尽管如此, 识别具有任意形状的簇在聚类算法的应用中仍然是一项非常重要的任务. 最小生成树聚类算法不受簇边界的几何变化影响, 因此簇边界的形状对算法性能的影响很小, 这使我们能够克服经典聚类算法通常面临的问题. 基于密度的聚类算法一直是聚类算法研究的重点. DPC算法^[16]是一种非常有影响力的聚类算法, 尽管在各种数据上表现良好, 但它不能正确处理不同部分密度不同的数据集. 尽管许多聚类算法已经被提出许多年, 但对能够处理上述问题的新的聚类算法的需求仍在继续. 为了克服这些问题, 本文对DPC算法和MST算法进行了改进和扩展, 提出了能够在密度不均匀、形状复杂的数据集上表现优异的聚类算法DPMST.

对国内外研究现状进行分析, 发现大部分聚类算法在处理具有复杂流形分布的数据集方面存在问题, 而在实际应用中, 复杂流形分布是普遍存在的一种结构, 因此复杂流形数据集的聚类分析具有重要的实际意义. 最小生成树聚类算法可以识别复杂的流形簇, 但功能较弱; 密度峰值聚类 (DPC) 算法功能强大, 但对流形结构的适用性较低.

本文针对最小生成树聚类算法和 DPC 算法存在的问题进行研究, 将密度峰与最小生成树聚类算法相结合, 用标签传播提高聚类质量, 提出了基于局部密度峰和标签传播的最小生成树聚类算法(DPMST). 该算法主要在以下3个方面做了改进: 一是利用DPC 算法思想的优点来寻找局部密度峰. 局部密度峰是具有局部最大密度的点, 它保留了原始数据集的分布结构,有助于在局部密度峰上有效构建最小生成树, 减少噪声点的影响, 从而提高算法性能; 二是采用基于共享邻的距离权值, 利用局部密度峰之间的邻域信息, 以更合适的方式表示它们之间的距离, 更有效地识别无效边; 三是引入标签传播机制, 提高聚类结果的质量.

1 相关工作

我们提出的算法是在最小生成树聚类算法和DPC算法的基础上改进的, 先介绍两种算法, 再进行研究分析.

1.1 最小生成树聚类算法

基于最小生成树的聚类算法流程: 首先构造数据集的无圈加权图, 再创建最小生成树, 计算所有边的均值与方差, 不断去除不一致的边, 直到满足某些终止条件, 则算法结束, 得到一组连通子图即为聚类结果.

最近几年, 在基于MST的聚类算法中, Zhou等提出AMST算法^[17], 通过使用新的有效性指标来定义任意形状的簇. 在他们的工作中, 有效性指标被用来确定最佳的簇数量并评估最终的簇. 类似的, Halim等使用新的内部有效性指标^[18], 用于改进生成的簇. Saar等提出的算法^[19]的目标是克服去除不一致的边和处理异常值这两个问题, 他们的主要贡献是使用一种被称为临界距离的方法来定义最优簇. Zhong等^[20]结合了K-means算法和MST算法, 首先利用K-means算法将数据集划分为k个分区, 然后用最小生成树来构建簇.

理想状态是簇间分离良好, 不一致的边就是最长的边, 但是事实上噪声点的出现使得去掉最长边未必能得到正确的聚类结果. 因此, 在最小生成树聚类中如何有效构建最小生成树、有效识别无效边和降低噪声点的干扰是研究中面临的主要问题.

1.2 密度峰值聚类算法

密度峰值聚类(DPC)算法要画出关于局部密度和相对距离的决策图, 找出局部密度和相对距离都较大的数据点, 从而很容易得到簇中心.

DPC算法至提出后一直流行, 近年来, 许多学者都在努力改进DPC. Li等提出的KS-FDPC算法^[21]采用了分区合并策略, 通过将数据划分为多个子簇, 可以降低高密度点对后续分配点的影响范围. Zhao等提出DPC-FWSN算法^[22]将k最近邻与模糊邻域相结合, 得到一个最近邻模糊核函数以此重新定义局部密度. DPC-PPNNN算法^[23]通过引入自然最近邻域和概率传播的思想, 实现了非参数聚类过程.

DPC算法在许多数据集上表现出色, 具有显著的优点. 然而, 该算法也存在一些局限性. 首先, 其聚类过程相对简单, 主要是通过最近距离原则将每个点分配到相应的簇中心所在的簇, 这使得它在处理复杂数据结构时可能不适用. 其次, DPC算法仅适用于每个簇都有密度峰且各簇之间密度差异较小的简单数据集. 当数据集具有流形结构时, DPC算法的适用性会大大降低.

我们尝试利用DPC算法的优点和最小生成树聚类算法来设计一种新的聚类算法. 尽管DPC算法在全局聚类上可能不够可靠, 但它能够在局部数据子集中实现高纯度聚类. 因此, 本文将使用局部密度峰来改进最小生成树聚类算法.

1.3 分析

最小生成树聚类算法可以识别形状不规则的簇, 问题在于如何有效构建最小生成树、识别无效边和降低噪声点干扰.

密度峰值聚类算法原理简单, 功能强大, 但对复杂数据结构的适用性较低.

我们结合两种算法的优点, 针对上述问题, 做出以下改进.

一是利用 DPC 算法思想的优点来寻找局部密度峰. DPC 算法可以在局部数据子集中实现高纯度. 局部密度峰包含了一定的局部信息, 保留了原始数据集的分布结构. 我们提出用家族树来捕获数据中的潜在结构, 这有助于反映数据中最近邻之间的密度优势. 通过将数据集划分为多个家族树, 可以更好地获得复杂的数据结构. 每个家族树都包含一个局部密度峰, 在此基础上可以有效构造最小生成树, 从而减少噪声点干扰, 提高算法性能.

二是采用基于共享邻的距离权值. 基于共享邻的距离权值充分利用邻域信息, 能够缩小在密集区域的局部密度峰间的距离, 扩大由稀疏区域连接的局部密度峰间的距离, 从而更准确地表示局部密度峰间的距离. 当使用基于共享邻的距离构造最小生成树时, 以一种更合适的方式表示了局部密度峰之间的距离, 更有效地识别无效边.

三是标签传播. 标签传播通过转移矩阵将簇主干的强标签传播到其余点, 并根据得到的标签矩阵重新分配标签. 标签传播可以增强强标签, 削弱弱标签, 以细化错误的标签, 这种改进策略可以提高聚类结果的质量.

2 改进的算法

本节将详细介绍我们提出的算法, 即基于局部密度峰和标签传播的最小生成树聚类算法(DPMST).

我们将介绍一些重要的概念, 再基于这些概念描述基于局部密度峰和标签传播的最小生成树聚类算法(DPMST)的详细流程, 该算法包括3个阶段: 识别局部密度峰, 构造最小生成树, 以及标签传播.

2.1 识别局部密度峰

局部密度峰是在局部密度最大的数据点, 识别它要先计算局部密度, 再构造家族树(family tree), 数据集将被划分为多个家族树, 每个家族树都有一个根节点(root), 即局部密度峰.

局部密度的计算通过下面几个定义说明.

定义1 (k最近邻). k最近邻是距离数据点最近的k个邻居的集合. 给定数据点${x_i}$, ${x_i} \in X$, 本文使用$N{N_k}\left( {{x_i}} \right)$来表示数据点${x_i}$在数据集 X 中的 k 最近邻.

定义2 (相互最近邻MNN). 若数据点p属于数据点q的k最近邻并且数据点q属于数据点p的k最近邻, 那它们互为相互最近邻(mutual nearest neighbor):

$MNN\left(p\right)=\left\{q\text{|}p\in N{N}_{k}\left(q\right)且q\in N{N}_{k}\left(p\right)\right\}$

(1)

定义3 (局部密度函数). 给定数据点${x_i}$, ${x_i} \in X$, 局部密度的定义是相互最近邻的个数:

$\rho \left( {{x_i}} \right) = \left| {MNN\left( {{x_i}} \right)} \right|$

(2)

通过局部密度, 再构造家族树. 家族树的定义如下.

定义4 (家族树). 构造家族树的思想是在k个最近邻的意义上找到每个数据点的父节点$P\left( {{x_i}} \right)$, 并将没有父节点的数据点识别为树的根节点(root), 即为局部密度峰. 如果点p的k最近邻中存在密度较高的点, 则选择最近的点q作为p的父点(如果有多个这样的点q, 选择第一个满足条件的); 否则, p没有父点, p被定为局部密度峰. 局部密度峰, 也就是家族树的根节点(root)可以代表所在的家族树上的数据点, 因此又叫代表点.

$P\left({x}_{i}\right)= \left\{\begin{array}{l} {\underset{{x}_{j}\in {{higher}}\left({x}_{i}\right)}{{\mathrm{argmin}}}}dis{t}_{ij}, \quad {\mathrm{if}}\; {{higher}}\left({x}_{i}\right)\ne \varnothing \\ {\mathrm{none}}, \qquad\qquad\quad\; {\mathrm{otherwise}}\end{array} \right.$

(3)

$higher\left( {{x_i}} \right) = \left\{ {{x_j}{\text{|}}{x_j} \in N{N_k}\left( {{x_i}} \right), \rho \left( {{x_j}} \right) > \rho \left( {{x_i}} \right)} \right\}$

(4)

其中, dist是一个$n \times k$矩阵, $dis{t_{ij}}$是${x_i}$与其第j个近邻之间的欧氏距离.

数据集构造家族树的思想是在k个最近邻的意义上找到每个数据点的父节点, 并将没有父节点的数据点识别为树的根节点(root), 即局部密度峰. 数据集将被划分为多个家族树, 每个家族树都有一个局部密度峰, 在局部密度峰上构造最小生成树, 降低了噪声点的干扰, 提高了算法的性能.

2.2 构造最小生成树

局部密度峰在数据集上并非均匀分布, 这是由数据集的分布情况决定的. 因此, 使用欧氏距离来衡量局部密度峰之间的距离是不合适的. 我们采用基于共享邻的距离^[24,25]权值(SW)来度量局部密度峰间的距离. 首先需要介绍一些与局部密度峰相关的概念.

定义5 (局部密度峰的成员MLDP). 局部密度峰, 也就是家族树的根节点(root)可以代表所在的家族树上的数据点, MLDP是局部密度峰所在家族树上的数据点的集合. 对于局部密度峰p, 它的成员是被p代表的数据点:

$MLDP\left( p \right) = \left\{ {a \in X\;{{\mid{{root}}}}\left( a \right) = p} \right\}$

(5)

定义6 (局部密度峰的邻域NLDP). 对于一个局部密度峰h, 它的邻域是h所有成员的k 最近邻的并集:

$NLDP\left( h \right) = \bigcup\limits_{a \in MLDP\left( h \right)} {N{N_k}\left( a \right)}$

(6)

定义7 (局部密度峰之间的共享邻SLDP). 两个局部密度峰p和q的共享邻是它们邻域的交集:

${\textit{SLDP}}\left( {p, q} \right) = NLDP\left( p \right) \cap NLDP\left( q \right)$

(7)

基于共享邻的距离权值的定义如下.

定义8 (基于共享邻的距离权值SW). 对于局部密度峰p和q, 它们的基于共享邻的距离权值计算为:

$\begin{split} & {\textit{SW}}\left( {p, q} \right) =\\ & \left\{ {\begin{array}{*{20}{l}} {\dfrac{{d\left( {p, q} \right)}}{{\left| {{\textit{SLDP}}\left( {p, q} \right)} \right| \times \displaystyle\sum\limits_{o \in {\textit{SLDP}}\left( {p, q} \right)} {\rho \left( o \right)} }}},&{{\mathrm{if}}{\text{ }}\left| {{\textit{SLDP}}\left( {p, q} \right)} \right| \ne 0} \\ {\max d \times \left( {1 + d\left( {p, q} \right)} \right)},&{{\mathrm{otherwise}}} \end{array}} \right. \end{split}$

(8)

其中, d(p, q) 是局部密度峰 p和q之间的欧氏距离, maxd为所有局部密度峰之间欧氏距离的最大值.

基于共享邻的距离权值SW的定义可以看出, 在密集区域紧密相连的局部密度峰的SLDP集合中会有许多数据点, 局部密度之和也很大, 所以分母很大, 能够缩短由密集区域紧密相连的局部密度峰间的距离; 在稀疏区域, 分隔的局部密度峰的SLDP集合中会有很少的数据点, 局部密度之和也很小, 所以分母很小, 能够放大被稀疏区域分隔的局部密度峰间的距离.

利用局部密度峰之间的邻域信息, 能够以一种更合适的方式表示了局部密度峰间的距离. 从下面的例子中可以清楚地看出这一点.

从图1中可以看出, 点 P与点H的距离较近, 但并不在同一个簇中, 点 H与点O距离较远, 但在同一簇中. 在数据经过归一化处理之后, 计算欧氏距离和基于共享邻的距离权值SW.

从表1可以直观地看出, 点 P与点H的距离被放大了, 点H与点O的距离被缩小了. 在欧氏距离中, 点H与点O距离大约是点 P与点H距离的两倍, 而在SW距离中, 点H与点O距离大约是点 P与点H距离的二分之一. SW距离可以缩短由密集区域紧密相连的局部密度峰间的距离, 放大被稀疏区域分隔的局部密度峰间的距离, 以一种更合适的方式表示了局部密度峰间的距离, 用这个距离权值能更有效地构造最小生成树, 识别无效边.

通过Prim算法用SW距离权值来构造最小生成树. 然后, 反复删除权值最大边, 每删除一次, 簇的数目增加一个(若目标簇数c, 需要删除c–1条边), 得到给定数目的簇. 举例如图2, 假设目标簇数为3, 该最小生成树需要删除2条边, 按权值需要删除BC边和CF边, 删除后可以看出BE在同一簇, AC在同一簇, DF在同一簇, 这样就分成了3个簇.

数据点根据所在的簇分配相应的标签, 所有的数据点都有一个标签. 每个局部密度峰和其邻居被定义为一个簇的主干部分, 主干的标签是强标签, 确定之后保持不变, 某些位于边界和重叠区域的数据的标签是弱标签, 之后可能会再变动标签.

2.3 标签传播

这一步的目的是使用强标签的簇主干为某些弱标签的数据点重新分配标签. 标签传播这一步要先把局部密度峰的确定性标签分配给其邻居, 每个局部密度峰和其邻居被定义为一个簇的主干部分, 主干的标签是强标签, 确定之后保持不变, 然后簇主干部分的标签通过转移矩阵传播到其余点, 根据得到的标签矩阵为某些位于边界和重叠区域的数据重新分配标签. 标签传播增强强标签, 削弱弱标签, 以细化错误的标签, 提高聚类质量. 具体流程如下.

首先, 计算转移矩阵, 我们定义了一个加权图G=(V, E, W), 其中顶点V对应数据集X, 权值为:

${W_{i, j}} = {\mathrm{exp}}\left( {\frac{{d{{\left( {{x_i}, {x_j}} \right)}^2}}}{{{\sigma_{i, j} ^2}}}} \right)$

(9)

其中, ${\sigma _{i, j}}$表示${x_i}$和${x_j}$的k近邻之间的平均距离.

上述的权值是使用一个全连通的图来定义的. 一般来说, 全连通图并不继承数据点的自然结构, 使用全连通图也会增加计算的复杂度. 因此, 一个更好的方法是连接一个基于k最近邻的图, 其中每个节点只连接到它的邻居, 节省计算成本.

基于k最近邻的权值:

$W_{i, j}^{\left( {N{N_k}} \right)} = \left\{ {\begin{array}{*{20}{l}} {{W_{i, j}}},&{{\mathrm{if}}{\text{ }}{x_j} \in N{N_k}\left( {{x_i}} \right)} \\ 0,&{{\mathrm{otherwise}}} \end{array}} \right.$

(10)

然后通过对权值进行归一化, 也就是权值除以行和, 定义一个转移矩阵:

${P_{i,j}} = \frac{{W_{i, j}^{\left( {N{N_k}} \right)}}}{{\displaystyle\mathop \sum \nolimits_{h \in V} W_{i, h}^{\left( {N{N_k}} \right)}}}$

(11)

将数据分为有标记点和未标记点. 已标记的数据点指的是定义为簇主干的数据点, 也就是局部密度峰和其邻居, 其余的数据点被认为是未标记的. 请注意, 每个数据点都与一个标签相关联. 初始标签矩阵定义为:

${Y_0} = \left[ {{Y^{\left( l \right)}};{Y^{\left( u \right)}}} \right] \in {R^{n \times c}}$

(12)

其中, ${Y^{\left( l \right)}}$为标记数据点的标签矩阵, ${Y^{\left( u \right)}}$为未标记数据点的标签矩阵. 如果${x_i}$属于第a个簇, 则$Y_{i, a}^{\left( l \right)} = 1$, 否则将其设置为0. n是数据集 X的数据点数目, c是簇个数. 初始标签矩阵中有标记的数据点是局部密度峰与其邻居, 也就是簇的主干部分.

在每次迭代中, 未标记的点更新其标签如下:

${Y_{t + 1}} = {F_t}*{Y_t}$

(13)

${F}_{0}=P, \text{ }{F}_{t+1}=\left\{\begin{array}{ll}P,& {\mathrm{if}}\text{ }t=0\\ P\left({F}_{t}+{Y}_{t}{Y}_{t}^{{\mathrm{T}}}\right){P}^{{\mathrm{T}} },& {\mathrm{if}}\text{ }t > 0\end{array} \right.$

(14)

直到标签矩阵不再发生变化, 迭代停止. 在每次迭代中, 那些初始标记的数据点可能会被分配不同的标签. 因此, 它们的标签需要重置如下:

$Y_{t + 1}^{\left( l \right)} = Y_0^{\left( l \right)}$

(15)

通过上述过程, 簇主干部分的强标签通过转移矩阵传播到其余点, 我们根据最终得到的标签矩阵为某些弱标签的数据点重新分配新标签, 得到最终的聚类结果.

大多数标签分配是单步操作的, 因此如果某个数据点被错误地分配了标签, 由于缺乏细化策略, 这个错误会传播到其他节点. 为了解决这个问题, 我们提出通过迭代过程更新标签. 数据点的标签根据标签传播后的标签矩阵进行更新, 给某些位于边界和重叠区域的数据重新分配真标签. 这种策略将数据的局部结构与标签空间相关性相结合, 特别是对边界点以及流形区域, 可以提高聚类结果的质量.

以上就是基于局部密度峰和标签传播的最小生成树聚类算法的整个流程.

基于局部密度峰和标签传播的最小生成树聚类(DPMST)的具体步骤如算法 1 所示.

算法1. 基于局部密度峰和标签传播的最小生成树聚类

输入: 数据集$\scriptstyle X = \left. {\left\{ {{x_1}, {x_2}, \cdots , {x_n}} \right.} \right\}$, 最近邻数量k, 簇个数c.

输出: 聚类标签$\scriptstyle Y = \left. {\left\{ {{y_1}, {y_2}, \cdots , {y_n}} \right.} \right\}$.

for each $\scriptstyle {x_i} \in X$ do

　　Calculate MNN($\scriptstyle {x_i}$) (见定义2)

　　Calculate $\scriptstyle \rho \left( {{x_i}} \right)$ (见定义3)

end for

root←$\scriptstyle \varnothing$

for each $\scriptstyle {x_i} \in X$ do

　　Compute $\scriptstyle P\left( {{x_i}} \right)$ (见定义4)

　　If $\scriptstyle P\left( {{x_i}} \right)$=none then

　　　root←root$\scriptstyle \cup \left\{ {{x_i}} \right\}$

end for

root 即局部密度峰

for each 局部密度峰 p do

　　Compute MLDP(p) (见定义5)

　　Compute NLDP(p) (见定义6)

end for

for each pair of 局部密度峰 p and q do

　　Compute SLDP(p, q) (见定义7)

　　Compute SW(p, q) (见定义8)

end for

edge←构造最小生成树(局部密度峰, SW)

k=1

while k<c do

　　Cut the longest edge

　　k=k+1

end while

Assign labels according to the cluster in which they are located

Assign the label of cluster centers to their nearest neighbors to form cluster backbones

Compute transition matrix P (见式(11))

for 迭代次数t=1 to T do

　　Compute label matrix $\scriptstyle {Y_t}$ (见式(13)–式(15))

end for

Reassign new labels to certain data points according to the resulting label matrix

2.4 DPMST算法分析

DPMST算法第1步识别局部密度峰: 计算局部密度, 为数据集构造家族树, 在 k 个最近邻的意义上找到每个数据点的父节点, 并将没有父节点的数据点识别为树的根节点(root), 即局部密度峰. 局部密度峰包含了一定的局部信息, 保留了原始数据集的分布结构. 用家族树来捕获数据中的潜在结构, 可以反映数据中最近邻之间的密度优势. 数据集被划分为多个家族树, 有助于获得复杂的数据结构. 一个数据集将被划分为多个家族树, 每个家族树都有一个局部密度峰, 在局部密度峰上能有效构造最小生成树, 降低噪声点的干扰, 提高算法的性能.

DPMST 算法第 2 步构造最小生成树: 计算局部密度峰之间 SW 距离权值, 使用 SW 距离权值来构造最小生成树, 反复删除最长边, 直到找到给定数量的簇, 根据所在的簇分配标签. 使用基于共享邻的距离构造最小生成树, 能够更有效地识别无效边.

DPMST 算法第 3 步标签传播: 把局部密度峰的确定性标签分配给其邻居, 即簇的主干部分, 计算转移矩阵, 然后簇主干部分的强标签通过转移矩阵传播到其余点, 数据点的标签根据标签传播后的标签矩阵进行更新. 这种策略可以提高聚类结果的质量.

3 实验

在本节中, 我们将详细介绍并分析实验结果, 以证明基于局部密度峰和标签传播的最小生成树聚类算法 (DPMST)的有效性.

3.1 实验指标和设置

我们选择了7种经典的聚类算法与DPMST算法比较, 包括 DPC^[16]、MST^[26]、K-means^[15]、DBSCAN^[27]、AP^[28]、谱聚类(SC)^[29]和 BIRCH^[30]. 为了更客观地反映各种算法的实际结果, 我们进行参数调优, 从而确保比较的是它们的最佳性能.

为验证我们的DPMST算法在各种数据集上的有效性, 我们选取了3种评价指标, 评价指标均保留4位小数. 本文采用了调整兰德指数(ARI)、标准化互信息(NMI)和 Fowlkes-Mallows 指数(FMI)对聚类算法的有效性进行评估, 3种评价指标的满分为1, 指标值与聚类效果成正比.

3.2 实验结果

在本节中, 我们选取几个广泛应用于检验聚类算法性能的人工数据集进行分析. 这些数据集具有点、簇分布与数目上的差异, 能够对比各种聚类算法在不同场景的效果. 我们选择的人工和真实数据集的情况如表2所示．

真实和人工数据集源于UCI network data repository和GitHub中. 真实数据集大多来源于生物和医学领域.

8个人工数据集上的聚类评价指标得分在表3显示, 得分最高的评价指标用粗体标记, 可以看到, 在大多数情况下, 我们的算法DPMST获得的得分最高.

8个人工数据集都是便于可视化的 2维数据, 因此本文对8个人工数据集都以图表的形式展示了聚类结果, 绘制图所使用软件是PyCharm.

如图3所示, spiral 是一个具有 3 个簇且低密度的数据集, 数据点构成了彼此交叉缠绕的螺旋形曲线.可以看到我们的算法DPMST、MST、DBSCAN和谱聚类算法在此数据集上表现良好, 而 K-means 算法仅考虑数据点之间的距离特性, 无法处理环绕的流线形数据, 效果最差.

jain是一个具有 2 个簇的数据集, 图4中数据点形成上下两环形, 上面的簇密度低, 下面的簇密度高. 可以看到只有我们的算法DPMST能够正确识别所有簇, 密度聚类算法性能不佳的原因是两个簇的密度差异太大. 而K-means不适合用于具有流线形状的数据集.

在图5中, 我们可以看到2d-4c-no9数据集有4个簇, 其中一个簇有非常高的密度. 我们的算法DPMST和DPC算法较为成功地检测到了所有的簇, 聚类效果最佳. K-means和BIRCH效果稍微差一些.

我们的算法DPMST和其他算法在Aggregation上的表现如图6所示. 可以看出, 我们的算法可以正确地检测到该数据集, K-means不能这样做, 因对K-means来说Aggregation数据集有些复杂.

图7显示了Compound数据集上的结果. 我们的算法与MST算法各具优势, 可以正确地检测大部分簇, 还可以识别噪声点. DBSCAN擅长识别噪声, 但它也将许多数据点错误地归类为噪声. DPC和K-means不能识别有噪声的簇.

在图8中, 我们可以看到zelink1数据集有3个簇, 形状像同心圆, 最中间的圆心密度高, 其余两簇密度逐渐降低. 我们的算法DPMST成功地检测到了所有的簇, 聚类效果最佳.

在图9中, Half kernel是一个具有两个簇且高密度的数据集, 数据点形成两个弧形簇. 在使用8种聚类算法对它们进行聚类时, 我们的算法DPMST在 Half kernel数据集上具有最佳的聚类结果, 其次是 MST算法.

如图10所示, Moon数据集有4个簇, 数据点形成4个弧形簇. 我们的算法DPMST可以正确识别所有簇, 而其余密度聚类算法将个别点识别为了离群点, 因此没有获得较好表现.

从8个人工数据集的结果可以看出, 本文提出的算法具有非常好的性能, 能聚类任意形状的簇, 具有较好的鲁棒性, 通过调节参数可以对密度差异大的数据实现较好的聚类, 对流形数据也有非常好的效果．

为证明我们算法DPMST在实践中的有效性, 进一步选取8个真实数据集开展实验, 这些数据集的数量、属性以及簇数各不相同, 相较于前面的人工数据集更加复杂. 通过表4中的实验结果可以发现, 在密度不均匀、形状复杂的真实数据集上表现优异的聚类算法DPMST大部分情况下优于其他7种聚类算法. 因此, 我们认为 DPMST算法具有一定的有效性和实用性, 可以在实际应用(例如生物和医学领域)中发挥作用.

4 结论

本文提出了一种聚类算法DPMST. 算法过程有以下步骤: 首先, 计算局部密度, 为数据集构造家族树, 识别局部密度峰; 其次, 计算SW距离权值, 构造最小生成树, 反复删除最长边, 直到找到给定数量的簇, 根据所在的簇分配标签; 最后, 标签传播, 计算转移矩阵, 簇主干的标签通过转移矩阵传播到其余点, 数据点的标签根据标签传播后的标签矩阵进行更新.

本文提出的改进后的算法 DPMST, 利用 DPC 算法思想的优点来寻找局部密度峰, 在局部密度峰上能有效构造最小生成树, 降低噪声点的干扰. 该算法构造最小生成树时使用基于共享邻的距离, 其以一种更合适的方式表示了局部密度峰之间的距离, 更有效地识别无效边. 标签传播将数据的局部结构与标签空间相关性相结合, 可以提高聚类结果的质量.

人工和真实数据集的实验结果表明, DPMST算法在密度不均匀、形状复杂的数据集上能够达到较为理想的聚类效果, 通过调节参数可以达到不同的聚类效果, 算法性能良好, 总体聚类性能优于其他对比算法, 具有一定的实用价值. 但是, DPMST算法仍需要输入参数, 这意味着该算法不能排除人为因素的干扰, 这对该算法在实际问题中的应用带来了一定的挑战, 因此, 在后续工作中我们将考虑参数的自适应.