0 引言

聚类是数据挖掘中研究最活跃的领域之一，它依据相似性将相似的对象聚集在一起形成一个簇，不同簇中的对象具有高度不相似性。聚类是无监督学习，在分析数据的内部结构、属性之间的关系等方面有重要的作用，并已经广泛应用于模式识别、图像处理、市场分析等领域^[1-4]。目前，学者们对聚类技术进行了深入的研究，提出了大量算法，如K-means^[5]、经典的基于密度聚类(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法^[6]等，如何提高算法的效率和对高维空间聚类的准确性依然是值得研究的问题^[7-8]。

K-means是基于划分的聚类算法，适用于对含有球形簇的数据集进行聚类，由于算法中使用欧氏距离，故对高维数据集的聚类结果精度不高。

基于密度的聚类由于其能发现任意形状、大小的聚类而备受关注^[9]。DBSCAN是基于密度聚类的经典算法，它认为一个聚类由核心点和非核心点组成，密度可达的核心点集合构成聚类的骨架，由骨架中的核心点可达的非核心点组成聚类肌肉。但基于密度的聚类算法不适合于多密度数据集和含有桥接聚类的数据集，聚类精度与邻域半径、密度阈值两个参数高度相关，时间复杂度为O(n²)，由于DBSCAN使用欧几里得度量距离，致使在处理高维数据集时陷入维数灾难。

为提高聚类质量，Rodriguez等^[10]将基于中心划分和基于密度划分的方法相结合提出密度中心聚类(Clustering by Fast search and find of Density Peaks, CFDP)算法，该算法认为聚类中心具有较大局部密度且彼此相距较远，剩余点就近分配给比其密度高的点所在聚类。从骨架的角度分析，聚类中心及其周围拥有大于平均局部密度上界的核心点集合构成聚类的骨架，与已分类数据点距离小于截断距离(cutoff distance)的非核心点集合形成聚类肌肉。CFDP算法可自动识别出含噪声和任意形状、密度的簇；但是当一个簇中包含多个核心点时，算法会将一个完整的簇划分为多个簇，且该算法的整体时间复杂度较高。

针对DBSCAN和CFDP均不适用于多密度数据集且时间复杂度较高的问题，Chen等提出密度骨架聚类(CLUstering based on Backbone, CLUB)算法^[11]，依据互k近邻一致性，将互为k近邻的点划为同一簇^[12]，形成初始簇，并在每个初始簇中分别使用k近邻识别出密度骨架，未分配的低密度点寻找距离其最近的高密度点，形成聚类肌肉。该算法使用密度骨架获得簇结构，有效解决了桥接簇和同一个簇中出现多个聚类中心而导致错误划分的问题；使用空间索引查找k近邻点，将时间复杂度降低为O(n·log n)。但该算法在识别密度骨架的过程中，两次建立索引查找k近邻点，形成初始聚类之后，要计算每个簇中数据点的局部密度并进行排序，故实际的运行时间开销依旧很大。能否通过一次查找k近邻得到高密度骨架是值得研究的问题。

为提高聚类算法的效率和在高维数据集上的聚类准确性，本文提出一种快速识别高密度骨架的聚类(Efficient CLUstering based on density Backbone, ECLUB)算法。本文的主要工作如下：

1) 定义一种基于k近邻的对象局部密度计算方法，可用于高维空间数据密度的计算；

2) 提出一种识别密度骨架的简单方法，能快速识别出任意形状、任意密度的聚类骨架。

1 ECLUB算法 1.1 符号与定义

设数据集D={x₁, x₂, …, x_n}，其中x_i=(x_i1, x_i2, …, x_im)(i=1, 2, …, n)。

定义1  k近邻集。给定x∈D，距离点x最近的前k个点x构成的k近邻集，记作NN_k(x):

NN_k(x)={y∈D|d(x, y)≤k_dist(x)}

其中：d(x, y)表示点x和y的欧氏距离；k_dist(x)表示点x到其第k个最近邻点的欧氏距离。

定义2  互k近邻。给定x, y∈D，如果x∈NN_k(y)且y∈NN_k(x)，称x和y互为k近邻。

互为k近邻的两个点，极有可能在同一个簇^[11]。

定义3  共享k近邻集。给定x, y∈D，如果x和y互为k近邻，∃z∈D既属于NN_k(x)，又属于NN_k(y)，称z为x和y的共享k近邻点，这样的点构成集合称为x和y的共享k近邻集，记作SNN(x, y)：

SNN(x, y)=NN_k(x)∩NN_k(y)

若点x和y互为k近邻且同属一个簇，则x和y的共享k近邻点也极有可能同属这一类^[11]。

定义4  对象的局部密度。点x的局部密度定义为σ(x)：

$\sigma (\mathit{\boldsymbol{x}}) = \sum\limits_{\mathit{\boldsymbol{y}} \in N{N_k}(\mathit{\boldsymbol{x}})} {\exp ( - d{{(\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}})}^2}/\delta )} $

(1)

其中：$ \delta = \mathop {{\rm{max}}}\limits_{\mathit{\boldsymbol{x}} \in {\bf{D}}} \sum\limits_{\mathit{\boldsymbol{y}} \in N{N_k}(\mathit{\boldsymbol{x}})} {d(\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}})}, \delta $用于规范σ(x)，避免σ(x)过大或过小而影响聚类结果，σ(x)越大，说明点x的局部密度越高，越有可能成为高密度点。

定义5  簇密度。簇密度是指簇中所有对象的局部密度的平均值，簇C的簇密度记为den(C)：

$ den(\mathit{\boldsymbol{C}}) = \sum\limits_{\mathit{\boldsymbol{x}} \in \mathit{\boldsymbol{C}}} {\sigma ({\pmb{x}})} /|\mathit{\boldsymbol{C}}| $

(2)

其中：|C|表示簇C中数据点总个数。簇密度作为判断是否将数据对象划分为同一簇和是否能合并两个簇的依据。

定义6  点簇密度相似度。给定x, y∈D，x与簇C的点簇密度相似度记作S_DC(x, C)：

${S_{\mathit{\boldsymbol{DC}}}}(\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{C}}) = |1 - \sigma (\mathit{\boldsymbol{x}})/den(\mathit{\boldsymbol{C}})|$

(3)

点簇密度相似度表征点与簇在密度上的相似程度，越接近0，说明点x的局部密度与簇C中包含点的局部密度越接近。

定义7  簇密度相似度。给定两个簇C_p、C_q，C_p∩C_q=∅，簇密度相似度记作S_CC(C_p, C_q)

$ {S_{\mathit{\boldsymbol{CC}}}}({\mathit{\boldsymbol{C}}_p}, {\mathit{\boldsymbol{C}}_q}) = |1-\frac{{2den({\mathit{\boldsymbol{C}}_q})}}{{den({\mathit{\boldsymbol{C}}_p}) + den({\mathit{\boldsymbol{C}}_q})}}| $

(4)

式(4)是由$\frac{{|den({\mathit{\boldsymbol{C}}_p}) - den({\mathit{\boldsymbol{C}}_q})|}}{{den({\mathit{\boldsymbol{C}}_p}) + den({\mathit{\boldsymbol{C}}_q})}}$化简得到，簇密度相似度表征两个簇的簇密度接近程度，越接近0，表明两个簇越相似，越可能合并为同一簇。

在CLUB算法中，若点x_i和x_j互为k近邻，则x_i、x_j以及它们的SNN(x_i, x_j)极有可能在同一个簇。若增加CLUB算法在识别密度骨架时对密度的限制条件，则更有把握将满足以下条件的数据对象分为一类，ε值的取值范围为[0, 1)。

条件1  若x_i和x_j互为k近邻，x_i∈C_q, x_j未标记，且满足S_DC(x_j, C_q)≤ε，则将点x_i和x_j划为同一簇，即x_j∈C_q。

条件2  若x_i, x_j∈C_q, x_k∈SNN(x_i, x_j)，x_k未标记，且满足S_DC(x_k, C_q)≤ε，则将点x_k、x_i和x_j划分为同一簇，即x_k∈C_q。

条件3  若x_i和x_j互为k近邻，x_i∈C_p, x_j∈C_q，且满足S_CC(C_p, C_q)≤ε，则合并簇C_p和簇C_q。

1.2 ECLUB算法步骤

ECLUB算法基于以下思想：互为k近邻的高密度点及其SNN在满足密度相近的条件下可分为一类，形成高密度骨架，未分配的低密度点寻找距离其最近的高密度点形成聚类肌肉或标记为离群点。ECLUB算法描述如算法1所示。

算法1  ECLUB。

输入  数据集D、近邻点个数k；

输出  聚类结果C。

步骤1  计算对象的局部密度。根据式(1)计算每个数据对象的局部密度σ(x_i)，并降序排列得到序列x′₁, x′₂, …, x′_n。

步骤2  高密度骨架的识别。遍历前2/3的数据对象(前2/3的数据对象作为高密度点，所占比例在后文有详细说明)，对每个高密度点x′_i作如下操作。

a) 若x′_i未分配，创建新簇C_p，并将x′_i分配给C_p，根据式(2)计算簇C_p的簇密度den(C_p)，若x′_i已分配，则直接执行b)。

b) 将满足条件1、2和3的数据对象分为一类，更新簇密度。

步骤3  低密度点的分配。未标记的低密度点与其互为k近邻的点分为一类，若其不存在互为k近邻的点，则标记为离群点。

ECLUB算法定义了对象的局部密度，在识别密度骨架的过程中，同时考虑近邻关系以及点、簇的密度关系，通过一次查找k近邻点，一次遍历数据对象，得到高密度骨架，提高了算法效率。

2 实验结果与分析

本文所有实验环境均为Windows 7 64位操作系统，Matlab R2015a软件，CPU为AMD 3.4 GHz，内存为4 GB。

2.1 实验数据集

实验选用8个数据集，其中3个人工合成数据集来自同类研究的相关文献[10-11]，分别用于验证ECLUB算法在处理桥接簇、多密度簇和非球形簇的能力；5个真实数据集来源于UCI机器学习数据库^[13]和Olivetti Face数据库^[14]的100张头像，用于验证ECLUB算法对真实的高维数据处理的有效性。Olivetti Face数据集中包含10个人物，每个人物拥有不同表情、侧脸、是否佩戴眼镜等特征的10张头像图片。表 1详细描述了实验中使用到的数据集。

2.2 评价指标

实验的评价指标采用调整兰德系数(Adjusted Rand Index, ARI)和归一化互信息(Normalized Mutual Information, NMI)，这两个指标用于度量聚类结果的准确性，取值越接近1，表明聚类结果越准确。

2.3 算法有效性分析

图 1是ECLUB算法在不同数据集上的聚类结果，不同灰度点代表不同簇。图 1(a)是k∈[16, 18]时的聚类结果，表明ECLUB算法可以准确识别出aggregation数据集中桥接聚类的簇；图 1(b)是k∈[6, 9]时的聚类结果，表明ECLUB算法能够准确识别出compound数据集中相互嵌套的多密度簇；图 1(c)是k∈[45, 60]时的聚类结果，表明ECLUB算法能够有效识别T4数据集中带有干扰线的非球形聚类。上述三个二维数据集上的聚类结果验证了ECLUB算法的有效性。

图 2显示ECLUB算法对Olivetti Face数据集的聚类结果，同一簇用相同灰度值的图片表示，右下最后一个头像图片灰度值最低，用于表示不属于任何簇。ECLUB算法能准确识别出8个簇，分别为前两个和后六个人物，中间(第3、4个)人物误分为一类，ARI和NMI分别为0.8779和0.9622；文献[11]给出了CLUB算法对Olivetti Face数据集的聚类结果，CLUB算法能够识别出8个簇，其中：3个头像未分类，14个头像误分类，ARI和NMI分别为0.7758和0.8843。可以看出，ECLUB算法对于Olivetti Face数据集的聚类结果准确性要高于CLUB算法。

表 2采用ARI和NMI对4种算法在人工数据集和真实数据集的实验结果进行评价(T4数据集缺少真实类标号，不包含其评价)。ECLUB与CLUB算法相比，ECLUB算法的ARI值有6项为最高，NMI值有5项为最高；CLUB算法的ARI值有4项为最高，NMI值有5项为最高。ECLUB算法对Segmentation和compound数据集的聚类准确性低于CLUB算法，但偏差极小；对Glass和Olivetti Face数据集的聚类准确性比CLUB算法平均提高了25.02%。同样，ECLUB算法的ARI和NMI评价指标在绝大多数的数据集上均高于CFDP和DBSCAN算法。整体来看，上述结果验证了ECLUB算法在人工数据集和高维真实数据集聚类结果的有效性和准确性。

2.4 算法时间复杂度及运行效率分析

本文算法使用局部敏感哈希函数^[7]查找k近邻，时间复杂度为O(n log n)，其中n为数据集总个数。在ECLUB算法步骤步骤1中使用快速排序算法对点局部密度降序排列，时间复杂度为O(n log n)；识别密度骨架时仅考虑前2/3的数据量，时间复杂度为O(2kn/3)，其中，k为近邻个数，通常k≪n，故可记为O(n)；对低密度点进行分配时，时间复杂度为O(kn/3)，通常剩余点数远小于n/3，甚至接近于0，故可忽略不计。因此ECLUB算法的整体时间复杂度为O(n log n)。

CFDP算法和DBSCAN算法的时间复杂度为O(n²)，随着数据量的增加，算法运行时间呈指数型增长；ECLUB算法和CLUB算法的时间复杂度为O(n log n)，接下来主要对比ECLUB和CLUB算法在不同数据量上的运行时间。在人工合成数据集上分别执行ECLUB和CLUB算法，针对不同数据量，每种算法均独立运行10次，选取10次实验的平均值作为算法在该数据量上的运行时间。如图 3所示，随着数据量的增加，ECLUB算法较CLUB的高效性逐步凸显。当数据量为20 000时，CLUB算法的运行时间为777.060 s，ECLUB算法的运行时间为486.008 s。

虽然ECLUB算法与CLUB算法时间复杂度相同，但后者在识别密度骨架时，首先通过互k近邻和共享k近邻集识别初始簇，然后要对每个初始簇中的数据点重新查找k近邻，并计算局部密度。在实际运行情况下，ECLUB算法仅需一步识别密度骨架，故与CLUB算法相比，运行效率更高。

2.5 高密度点所占比例与相似度阈值的分析

图 4展示了经降序排列后的点局部密度的斜率变化情况，从a点之后，点局部密度值开始呈现快速降低，由高密度点逐步转化为低密度点。根据a点所处位置，判断出高密度点所占比例。在人工数据集和真实数据集上的实验显示，高密度点所占比例的选取具有鲁棒性，图 4中两种数据的高密度点所占比例可选范围分别为[40%, 80%]、[32%, 82%]。本文中统一将2/3作为高密度点所占比例。

相似度阈值ε的大小约束着局部密度差异对数据点划分和簇合并的影响程度。根据点簇密度相似度和簇密度相似度的定义，S_DC(x, C)≤ε, 即|1-σ(x)/den(C)|≤ε，可转化为den(C)·(1-ε)≤σ(x)≤den(C)·(1+ε)，故0≤ε < 1；同理，S_CC(C_p, C_q)≤ε，即|1-2den(C_q)/(den(C_p)+den(C_q))|≤ε，可转化为|den(C_p)-den(C_q)|/(den(C_p)+den(C_q))≤ε，故0≤ε < 1。ε值过大，容易将密度差异大的数据点分为一类; 相反，ε值过小，导致局部密度相近的点或簇不能准确地进行合并。从图 5可以看出，随着ε值的增大，ARI呈现先增大后减小的趋势。在人工数据集和真实数据集上的实验结果表明，ε值在[0.01, 0.8]的范围内，ARI均能取得较高值，当ε值为0.01时，ARI均为最高。本文实验中统一将ε取值为0.01。

3 结语

本文提出一种快速识别密度骨架的聚类算法ECLUB，该算法在识别密度骨架的过程中，同时考虑近邻关系以及点和簇的密度关系，避免了CLUB算法必须通过两步识别高密度骨架的缺陷。ECLUB算法可以有效发现任意形状、不同密度的簇，可适用于任意维度，在保证算法聚类结果准确性有所提高的同时，提高算法聚类速度。如何在密度骨架的基础上，进一步提高聚类准确性是下一步的研究工作。