开放科学（资源服务）标志码（OSID）：

0 概述

聚类是将数据按照一定的相似性度量规则分为多个不同的类别，将差异小的样本尽可能聚为同一类，将差异大的样本聚为不同的类。聚类算法在处理数据之前无需指定数据集的标签信息，属于无监督的机器学习领域，被广泛应用在图像处理和模式识别等领域^[1]。根据算法特点大致分为基于划分的聚类算法（如K-means算法）、基于层次的聚类算法（如BIRCHIS算法）、基于密度的聚类算法（如DBSCAN算法）、基于网格的聚类算法（如STING算法等^[2]）。对于凸数据集，许多聚类算法都能获得较好的聚类效果，但是对于非凸数据集则难以识别复杂的数据集从而无法很好的聚类。由于谱聚类算法在非凸数据集上有较好的聚类效果，近年谱聚类算法的研究迅猛发展^[3-4]。谱聚类算法将数据集中的每个点视为图的顶点，并将任意两点之间的相似性视为连接两个顶点的边的权重。根据图划分方法，将图分为几个不连续的子图，子图中包含的点集则是聚类后生成的簇^[5]。

尽管谱聚类算法在实践中取得了良好的性能，但作为一种新的聚类方法仍处于发展阶段，有许多问题需要进一步研究。谱聚类算法的聚类性能主要由相似性矩阵的构造决定。在现有相似性矩阵的研究中，大多数研究都是基于欧几里得距离、余弦相似度或高斯核函数来评估数据点之间的相似度。文献[6]提出一种基于数据本身蕴含信息的集成度量学习方法的谱聚类算法。文献[7]通过将数据集样本表示为稀疏的线性组合，通过构造最优化问题的模型，使该方法能较好地反映数据空间的局部一致性，从而提升系统的鲁棒性。文献[8]提出一种自适应谱聚类技术，用于处理多尺度数据集，它没有选择全局参数$ \sigma $，而是根据每个点的邻域信息计算自适应参数。文献[9]通过局部密度获得数据中隐含的簇结构特征，结合自调整高斯核函数，提出一种基于共享邻域自适应相似度的谱聚类算法。文献[10]提出流形结构数据点之间的相似度计算方法，以提高算法的聚类性能。文献[11]致力于找到核参数$ \sigma $的最佳值以改进谱聚类算法，但最佳值是一个全局值，不适用具有密度的簇数据集。文献[12]提出一种翘曲模型，用于将数据映射到新的空间，以更准确进行相似性度量。文献[13]使用数据点之间的局部密度来缩放参数，具有放大集群内相似性的作用。文献[14]基于数据点之间的最大流量来测量相似度，以满足谱聚类算法中使用相似度度量的要求。文献[15]将相对密度敏感项引入相似性度量，在满足全局和局部一致性的同时，通过相对密度敏感项能有效规避噪声点对样本空间的干扰，尤其是对于“桥”噪声。文献[16]通过截断核范数的低秩张量分解方法。计算各视角的样本相似度矩阵和转移概率矩阵，从而解决谱聚类算法的多视角问题。

对于构造谱聚类算法中相似性矩阵，目前研究大多采用K最近邻（K-Nearest Neighbor，KNN）图构建相似图，并基于密度敏感项改进的欧几里得距离相似性度量来评价样本点之间的相似性。然而基于KNN图构建的相似图通常会引入冗余连接，并且易受噪声影响，噪声样本点使聚类质心不准确。这两个因素会降低谱聚类性能使其出现错误的聚类结果^[17]，需根据经验确定K最近邻的值，使最终聚类效果具有不确定性。基于欧几里得距离的相似性度量也存在着无法揭示某些复杂数据集的真实簇的问题，尤其是不能很好地分离数据集。因不同群集中某些数据点相距不远，噪声的存在也会使数据集无法很好地分离。由于许多实际数据集没有很好地分离，很难找到正确的聚类，因此提出一种对未分离的数据集具有鲁棒性的聚类算法是十分必要。

本文以相似性矩阵构造为切入点，提出一种基于共享邻的密度自适应邻域谱聚类算法（SC-DANSN），构建无需指定初始参数的相似图，并将共享最近邻作为样本点之间的相似性度量，以减少噪声信息在分离数据集上的影响，并解决谱聚类算法相似性度量无法准确反映数据空间结构的问题。

1 谱聚类

谱聚类是一种基于图论的聚类方法。通过对数据集相似矩阵进行谱分析得到较好的聚类结果。谱聚类的概念起源于谱划分，谱划分将数据聚类转换为无向图的多向划分问题^[18]。谱聚类算法将数据点定义为无向图$ G=(V, E) $的顶点，其中$ V $是顶点集，$ E $是顶点之间的边集。建立图上各顶点之间的相似度矩阵$ \boldsymbol{S} $，其元素$ {S}_{ij} $可被视为连接第$ i $个数据点和第$ j $个数据点的边上的权重。相似度矩阵的元素$ {S}_{ij} $由高斯核函数表示：

$ {S}_{ij}=\left\{\begin{array}{ll}\mathrm{e}\mathrm{x}\mathrm{p}(-{d}^{2}({p}_{i}, {p}_{j})/(2{\sigma }^{2}\left)\right), i\ne j& \\ 0, i=j& \end{array}\right. $

(1)

其中，$ {P}_{i} $和$ {P}_{j} $分别表示第$ i $个数据点和第$ j $个数据点，而$ {d}^{2}({P}_{i}, {P}_{j}) $表示$ {P}_{i} $和$ {P}_{j} $之间的欧几里得距离，$ \sigma $是确定数据点之间相似度的比例参数。NJW算法使用归一化相似度矩阵作为图拉普拉斯矩阵，并通过考虑对应于最大特征值的特征向量，基于归一化割准则优化分区问题，谱聚类算法描述如下：

算法1  谱聚类

输入  数据集D，聚类数目K

输出  K个簇的集合$ C=\{{C}_{1}, {C}_{2}, \cdots , {C}_{K}\} $

步骤1  通过KNN邻域或$ \varepsilon $邻域生成无向图，基于式（1）构建相似性矩阵$ \boldsymbol{S} $，生成对应的度矩阵$ \boldsymbol{B} $，其中$ {B}_{ij}=\sum\limits_{j=1}{S}_{ij}, i, j=\mathrm{1, 2}, \cdots , n $。

步骤2  生成对应规范化的拉普拉斯矩阵$ \boldsymbol{L} $。

步骤3  计算拉普拉斯矩阵$ \boldsymbol{L} $对应的特征向量，并选取前K个最大特征值对应的特征向量构建矩阵$ \boldsymbol{X} $。

步骤4  用K-means算法对$ \boldsymbol{Y} $进行聚类，输出K个簇的集合$ C=\{{C}_{1}, {C}_{2}, \cdots , {C}_{K}\} $。

2 基于共享邻的密度自适应邻域谱聚类 2.1 密度自适应邻域构建算法

谱聚类算法主要是构建相似性矩阵，在此之前，先构建能反映样本空间的无向图。主要方法是基于KNN图或ε邻域图，其缺点是对参数的选取敏感，不能较好地反映数据空间。

聚类是基于相似性度量形成点组，因此同组内的点之间相似度很高，而来自不同群体点的相似度很低。邻居包括本地相似的点，因此数据点及其邻居应位于同一簇中。

在2个数据集上使用KNN和$ \varepsilon $邻域算法构建的邻域如图 1所示。根据欧氏距离来衡量相似度，图 1（a）中有2个簇。当K≤3时，簇2中点i的KNN邻域包括来自同一簇的点，即点j，m和n；当K≥4时，簇1中点p包含在点i的邻域中。因此，KNN无法提取点i和o之间超过点m的间接连接，并导致混合邻域。图 1（b）中的数据集有3个簇，其中1个簇具有内部密度变化。对于固定半径ε，点s的邻域包括来自同一簇簇1的点，但是点r的邻域为空，即使它不是离群值也是如此。当ε值增大时，点r不再是异常值，但点s的邻域也增大，并引起了簇2和簇3的邻域混合^[19]。从图 1可以看出，聚类问题中参数对邻域方法的敏感性。

本文采用一种密度自适应的邻域构造（Neighborhood Construction，NC）算法克服KNN和ε邻域方法的局限性。算法的流程如图 2所示。

在构建密度自适应邻域算法之前，定义以下概念：

$ D $：代表一个数据集；

$ i $，$ j $，$ p $：代表数据点；

$ {d}_{ij} $：代表点$ i $和$ j $之间点欧氏距离；

$ C{C}_{i} $：代表点$ i $的核心近邻点；

$ B{C}_{i} $：代表点$ i $的密度连接近邻点；

$ P{C}_{i} $：代表点$ i $的扩展近邻点；

$ C{S}_{i} $：代表点$ i $的最终近邻点；

$ B(i, j, {d}_{ij}) $：以$ i $和$ j $为圆上两点，$ {d}_{ij} $为直径，作一个圆，圆内点的集合是$ B(i, j, {d}_{ij}) $；

直接连接：当且仅当$ B(i, j, {d}_{ij})\bigcap D=\mathrm{\varnothing } $时，称点$ i $和$ j $为直接连接，即$ i $和$ j $之间的集合$ B(i, j, {d}_{ij}) $内不存在任何点；

间接连接：如果$ B(i, j, {d}_{ij})\bigcap D\ne \mathrm{\varnothing } $时，称点$ i $和$ j $为间接连接，即$ i $和$ j $之间的集合$ B(i, j, {d}_{ij}) $内至少存在一个点；

$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{ij} $：代表点$ i $和$ j $之间的密度，该值定义为集合$ B(i, j, {d}_{ij})\bigcap D $内点的个数。

NC算法描述如下：

算法2  密度自适应邻域构建算法

输入  数据集D

输出  密度自适应最终邻居集合$ C{S}_{i} $

步骤1  列出D中除点$ i $以外的所有点，按其到点$ i $的距离由近到远排列，并形成有序集$ {T}_{i} $。

步骤2  初始化$ C{C}_{i}=\mathrm{\varnothing } $，$ j=0 $遍历有序集合$ {T}_{i} $，计算$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]} $，对于$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]}=0 $，更新$ C{C}_{i} $=$ C{C}_{i}\bigcup \left\{{T}_{i}\right[j\left]\right\} $，$ j=j+1 $，直到$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]}\ne 0 $，结束遍历，并设置indirect $ i $=$ j $。

步骤3  初始化$ B{C}_{i} $=$ C{C}_{i} $，$ j $=indirect $ i $遍历有序集合$ {T}_{i} $，计算$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]} $，对于$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]}-\mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}[j-1]}\ge $ $ 0 $，更新$ B{C}_{i} $=$ B{C}_{i}\bigcup \left\{{T}_{i}\right[j\left]\right\} $，$ j=j+1 $，直到$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]}-\mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}[j-1]} < 0 $，结束遍历，并设置break$ i $=$ j-1 $。

步骤4  初始化$ P{C}_{i} $=$ B{C}_{i} $，$ j $=break$ i $，遍历有序集合$ {T}_{i} $，计算$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]} $，对于$ \mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}\left[j\right]}-\mathrm{D}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}{\mathrm{y}}_{i，{T}_{i}[j-1]}\ge $$ 0 $，更新$ P{C}_{i}= $$ P{C}_{i}\bigcup \left\{{T}_{i}\right[j\left]\right\} $，$ j=j+1 $，直到$ B{C}_{i}\bigcup B{C}_{{T}_{i}\left[j\right]}=\mathrm{\varnothing } $，结束遍历，并设置$ C{S}_{i} $=$ P{C}_{i} $。

步骤5  初始化$ j $= 0，遍历有序集合$ {T}_{i} $，对于$ C{C}_{i}\bigcup C{S}_{C{S}_{i}\left[\mathrm{j}\right]}=\mathrm{\varnothing } $，从集合$ C{S}_{i} $中移除$ C{S}_{i}\left[j\right] $，更新$ j=j+1 $，直到集合$ C{S}_{i} $不再发生变化，算法结束，输出最终邻居集$ C{S}_{i} $。

NC算法最终输出的密度自适应邻居集可以构造密度自适应的无向图$ G=(V, E) $，本文把图$ G $记为DAN（Density Adaptive Neighborhood）。构造相似矩阵还需要对无向图DAN进行加权，权重样本点之间的相似性度量。

2.2 基于共享最近邻的相似性度量

在构建局部自适应邻域后可以生成无向图。为实现谱聚类算法应先对该无向图加权，权重即为数据点之间的相似度。目前谱聚类算法广泛使用基于欧氏距离的相似性度量，这种相似性度量有时难以反映数据点之间的真实相似程度^[18]。因此考虑一种基于共享最近邻的新相似性度量，并将其与局部自适应邻域构建相结合，从而形成一种改进的谱聚类算法。本文基于局部自适应邻域图中共享的最近邻来测量数据点之间的相似度。

设$ {N}_{i} $表示局部自适应邻域图中数据点$ {X}_{i} $的邻集。$ {X}_{i} $与$ {X}_{j} $之间共享邻居的集合为$ {N}_{i}\bigcap {N}_{j} $，通过集合$ {N}_{i}\bigcap {N}_{j} $来测量成对相似度$ {S}_{ij} $。通常$ {N}_{i} $不包括$ {X}_{i} $，因此$ {N}_{i}\bigcap {N}_{j} $不包括两个测量点$ {X}_{i} $和$ {X}_{j} $。$ {N}_{i}\bigcap {N}_{j} $是否包含$ {X}_{i} $和$ {X}_{j} $取决于$ {X}_{i} $和$ {X}_{j} $的关系，并影响相似性度量。在图 3（a）和图 3（b）中两种不同情况下显示点1和点2的邻居。在图 3（b）中，点1和点2是彼此的邻居，在图 3（a）中则不是。如果不考虑点1和点2的关系，在两种情况下点1和点2的共享邻居集相同。因在图 3（b）中点1和点2是彼此的邻居，图 3（b）中的点1和点2的相似度高于图 3（a）。

通过考虑两个测量点之间的关系来重新定义图中两个点的共享邻居集合。$ {N}_{i} $是$ {X}_{i} $的邻居集合，并且不包括$ {X}_{i} $。$ {N}_{i}\bigcap {N}_{j} $是点$ {X}_{i} $和$ {X}_{j} $之间共享邻居的集合，其重新定义为：

$ {N}_{i}\bigcap {N}_{j}=\left\{\begin{array}{ll}{N}_{i}\bigcap {N}_{j}\bigcup \left\{{x}_{ij}^{\mathrm{\text{'}}}\right\}, {X}_{i}\mathrm{和}{X}_{j}\mathrm{互}\mathrm{为}\mathrm{邻}\mathrm{居}& \\ {N}_{i}\bigcap {N}_{j}, \mathrm{其}\mathrm{他}& \end{array}\right. $

(2)

其中，$ {x}_{ij}^{\mathrm{\text{'}}} $是一个虚拟数据点，表示$ {X}_{i} $是$ {X}_{j} $的邻居，并同时表示$ {X}_{j} $是$ {X}_{i} $的邻居。如果不考虑其他共享邻居，则$ {X}_{i} $和$ {X}_{j} $具有一个共享邻居。

根据式（2）定义共享邻居的集合来测量成对相似性。许多基于共享邻居的聚类方法都将成对相似性视为共享邻居数量的函数。如果2个数据点具有更多共享的邻居，则它们具有较高的成对相似性。但仅考虑共享最近邻居的数量可能会导致测量结果错误。在2种不同情况下点1和点2的3个邻居如图 4所示。点1和点2在图 4（a）中具有2个共享邻居，而在图 4（b）中它们具有1个共享邻居。如果仅考虑共享邻居数量，图 4（a）中的点1和点2的成对相似度高于图 4（b）中的点。图 4（b）中点1和点2非常接近，它们的成对相似度应高于图 4（a）。因此仅考虑共享邻居的数量可能会忽略数据点的紧密度。

为测量成对相似度$ {S}_{ij} $，根据$ {N}_{i}\bigcap {N}_{j} $中共享邻居对数据点$ {X}_{i} $和$ {X}_{j} $的权重。令$ {W}_{ij} $表示$ {N}_{i}\bigcap {N}_{j} $中共享的邻居的权重。令$ {X}_{r} $为$ {N}_{i}\bigcap {N}_{j} $中共享的邻居之一。假设$ {X}_{r} $是$ {X}_{i} $的第$ {i}_{r}^{\mathrm{t}\mathrm{h}} $个邻居和$ {X}_{i} $的第$ {j}_{r}^{\mathrm{t}\mathrm{h}} $个邻居，则邻居$ {W}_{ij} $的权重表达式为：

$ {W}_{ij}=\sum\limits_{{X}_{r}\in {N}_{i}\bigcap {N}_{j}}(k-{i}_{r}^{\mathrm{t}\mathrm{h}}+1)(k-{j}_{r}^{\mathrm{t}\mathrm{h}}+1) $

(3)

为了进行统计分析，考虑在$ {S}_{ij} $∈[0, 1]范围内的成对相似性。计算成对相似度$ {S}_{ij} $为：

$ {S}_{ij}=\frac{{W}_{ij}}{\mathrm{m}\mathrm{a}\mathrm{x}\left\{{W}_{ij}\right\}} $

(4)

相似矩阵$ \boldsymbol{S} $为：

$ \boldsymbol{S}=({S}_{ij}{)}_{i, j=\mathrm{1, 2}, \cdots , n} $

(5)

通过对DAN进行加权构建一种基于共享邻的局部自适应邻域相似矩阵。

2.3 基于共享最近邻的密度自适应邻域谱聚类

为提高传统谱聚类算法对相似性矩阵构造参数的敏感性，以及相似性度量难以准确反映复杂数据和非凸数据的结构，增加聚类算法结果的稳定性。本文在原有谱聚类算法的基础上，结合一种密度自适应邻域构建方法，并通过共享最近邻进行样本点的相似性衡量，提出一种新的基于共享近邻的密度自适应邻域谱聚类算法SC-DANSN。利用密度自适应邻域构建方法构建无向图DAN；通过最终邻居集基于共享最近邻对DAN的边进行加权；生成相似矩阵，并计算相应的拉普拉斯矩阵和度矩阵，再进行特征向量的计算，最终通过K-means算法进行聚类得到最终的聚类结果。

算法3  基于共享最近邻的密度自适应邻域谱聚类算法

输入  数据集D聚类数目K

输出  K个簇的集合$ C=\{{C}_{1}, {C}_{2}, \cdots , {C}_{K}\} $

步骤1  通过NC算法构建密度自适应邻域，并生成无向图DAN，列出DAN中共享最近邻集合。

步骤2  如果DAN中的连通子图数大于K，则在最近的连通子图之间插入边。相应地更新已连通子图的数量和DAN图，直到连通子图数等于K。

步骤3  基于共享最近邻测量成对相似度$ {S}_{ij} $，对DAN进行加权，构建相似矩阵S。

步骤4  根据相似矩阵$ \boldsymbol{S} $，计算度矩阵$ \boldsymbol{B} $及其对应的规范化拉普拉斯矩阵$ \boldsymbol{L} $。

步骤5  计算拉普拉斯矩阵$ \boldsymbol{L} $对应的特征向量，并选取前K个最大特征值对应的特征向量构成矩阵$ \boldsymbol{X} $。

步骤6  通过K-means算法对$ \boldsymbol{X} $进行聚类，最终输出K个簇的集合$ C=\{{C}_{1}, {C}_{2}, \cdots , {C}_{K}\} $，算法结束。

SC-DANSN算法主要由3部分构成，第1部分为通过NC算法构造DAN图，具体分为5步，步骤1和步骤2的时间复杂度由密度计算确定，该步骤的程序执行次数与样本点个数n成10³增长，即时间复杂度为$ O\left({n}^{3}\right) $。步骤3和步骤4在整个过程中的时间复杂度为$ O\left({n}^{2}\right) $。步骤5在$ O\left({n}^{2}\right) $时间内检查点与其邻域的相互连通性，重复进行直到邻域不再变化。所以构造DAN图即NC算法的时间复杂度为$ O\left({n}^{3}\right) $。第2部分为测量成对相似的构造相似性矩阵S，该部分的时间复杂度为$ O\left({n}^{2}d\right) $，d表示数据集的维度即特征数目。第3部分为聚类部分，采用K-means算法，故该部分的时间复杂度为$ O\left(tkn\right) $，t表示迭代次数，k表示类别数目。结合上述3部分分析，由于构建DAN时的算法复杂度较高，本文所提算法SC-DANSN的时间复杂度为$ O\left({n}^{3}\right) $比传统谱聚类算法时间复杂度$ O\left({n}^{2}\right) $高，

3 实验与结果分析

实验环境为Intel^® Core^TMi7-6700HQ CPU@2.60 GHz，内存为8.0 GB；编程环境为PyCharm；在Windows10操作系统的计算机上进行测试。通过在人工数据集和UCI数据集上进行实验，评估和分析所提算法。

为了比较和分析聚类结果，在以下实验中采用评估2种聚类性能方法归一化互信息（NMI）^[18]和兰德指数（RI）^[20]。

归一化互信息（NMI）被广泛用于评估聚类算法性能。令$ C=\{{C}_{1}, {C}_{2}, \cdots , {C}_{K}\} $表示正确的聚类结果，$ C\text{'}=\{{C}_{1}^{\mathrm{\text{'}}}, {C}_{2}^{\mathrm{\text{'}}}, \cdots , {C}_{K}^{\mathrm{\text{'}}}\} $表示通过聚类算法获得的预测聚类结果。$ P\left({c}_{i}\right)=\left|{c}_{i}\right|/n $是数据点属于簇$ \left|{c}_{i}\right| $的概率，其中$ \left|{c}_{i}\right| $是簇$ {c}_{i} $的基数，n是数据点的总数。$ P({c}_{i}\bigcap {c}_{j}^{\mathrm{\text{'}}})=\left|{c}_{i}\bigcap {c}_{j}^{\mathrm{\text{'}}}\right|/n $是数据点属于群集$ {c}_{i} $和$ {c}_{j}^{\mathrm{\text{'}}} $交集的概率。NMI计算如下：

$ N(C, C\text{'})=\frac{2\varphi (C, C\text{'})}{\varphi \left(C\right)+\varphi \left(C\text{'}\right)} $

其中：$ \varphi \left(C\right)=-\sum\limits_{i=1}^{K}P\left({c}_{i}\right)\mathrm{l}\mathrm{g}P\left({c}_{i}\right) $；$ \varphi (C，C\text{'})=\sum\limits_{i=1}^{K}\sum\limits_{j=1}^{K}P({c}_{i}\bigcap {c}_{j}^{\mathrm{\text{'}}}) $ $ \mathrm{l}\mathrm{g}\frac{P({c}_{i}\bigcap {c}_{j}^{\mathrm{\text{'}}})}{P\left({c}_{i}\right)P\left({c}_{i}^{\mathrm{\text{'}}}\right)} $。

N值越大表示聚类结果越好，N最大为1，表示所有数据点均被正确分类。

兰德指数（RI）用于测量2个群集的相似性，考虑到同群集和不同群集中存在的数据点数量。RI将群集标签分配视为数据点之间的成对关系，表明每对数据点可以分配给相同的群集，还可以属于不同的群集。对于具有N个数据点的数据集，RI的计算如下：

$ \begin{array}{l}R(U, V)=\left(\begin{array}{c}{N}_{lk}\\ 2\end{array}\right)-\left[\sum\limits_{l}\left(\begin{array}{c}{N}_{l.}\\ 2\end{array}\right)\cdot \sum\limits_{k}\left(\begin{array}{c}{N}_{.k}\\ 2\end{array}\right)\right]/\left(\begin{array}{c}N\\ 2\end{array}\right)/\\ \left((1/2)\left[\sum\limits_{l}\left(\begin{array}{c}{N}_{l.}\\ 2\end{array}\right)+\sum\limits_{k}\left(\begin{array}{c}{N}_{.k}\\ 2\end{array}\right)\right]-\\ \left[\sum\limits_{l}\left(\begin{array}{c}{N}_{l.}\\ 2\end{array}\right)\cdot \sum\limits_{k}\left(\begin{array}{c}{N}_{.k}\\ 2\end{array}\right)\right]/\left(\begin{array}{c}N\\ 2\end{array}\right)\right)\end{array} $

其中，$ {N}_{lk} $表示在U中属于相同簇$ l $的数据点和V中属于相同簇$ k $数据点的数量，$ {N}_{l.} $表示分配给U中的相同簇$ l $并属于其中不同簇数据点的数量，$ {N}_{k.} $表示属于U中不同簇并分配给V中的相同簇$ k $数据点的数量。RI的值在0~1，其中RI值越高表示聚类效果越好。

3.1 人工合成数据集

在人工合成数据集中随机选取4个数据集，分别测试K-means、SC-KNN、SC-DANSN算法的聚类效果。采用的数据集属性如表 1所示。

聚类结果如图 5~图 8所示。在凸数据集Five_cluster，K-means、SC-KNN和SC-DANSN算法均能正确的聚类如图 7所示，而在其他3个非凸数据集，K-means算法效果最差（见图 5、图 6、图 8）。本次实验固定SC-KNN算法的核参数为5，K最近邻为20即构建相似图时选取20个最近的邻居作为构图参数。由于SC-KNN算法受限于相似矩阵构建时参数的影响，聚类效果不稳定，需要不断地尝试选择参数来实现正确的聚类。本次实验中SC-DANSN算法的共享最近邻数量也设为20。由于SC-DANSN算法采用一种密度自适应邻域方法来构造相似图，无需指定构建相似图的参数信息，只需指定共享最近邻的数量以测量成对相似性。由于SC-DANSN算法无参构造相似图的特性，无需像传统谱聚类算法要不断尝试构造相似图的参数，所以其聚类效果稳定并能正确聚类。对于加入噪声的数据集Cluto_t4，SC-KNN算法无论进行何种调参，噪声样本都无法很好地分离。而SC-DANSN算法通过引入共享最近邻能较好地分离噪声信息，在3种算法中抗噪声性能最优。

3.2 UCI真实数据集

为进一步验证SC-DANSN算法的有效性，随机选取UCI机器学习库的4个真实数据集。4个数据集的属性如表 2所示。

本次实验对每种数据集进行10次独立的实验，对于SC-KNN、SC-DANSN算法，取K值从5~50步长为5，K在SC-KNN算法中代表K最近邻数量，在SC-DANSN算法中代表共享最近邻的数量。经过10次独立的试验后，K-means、SC-KNN、SC-DANSN算法在UCI数据集的RI和NMI值的平均值如表 3所示。结果表明基于RI和NMI准则，在4种UCI数据集中，SC-DANSN算法的聚类效果最好，SC-KNN次之，两种算法聚类结果相似。由于K-means基于划分的聚类规则，对于非凸数据集分离效果不好，相比其他谱聚类算法，其聚类效果最差。

为验证SC-DANSN算法对参数选择的不敏感性，使用SC-DANSN和SC-KNN算法对4个UCI数据集的最近邻数K的变化进行聚类实验。SC-DANSN和SC-KNN算法在K值选取4个最佳结果时的敏感性如图 9~图 12所示，可以看出，SC-DANSN算法对参数K的敏感性更小。

4 结束语

本文提出一种基于共享最近邻的密度自适应邻域谱聚类算法SC-DANSN，以降低谱聚类算法对构造相似图的参数敏感性并充分分离数据集。该算法的相似性度量是基于无向DAN图中共享的最近邻居的接近度，与基于无向KNN图的传统谱聚类算法相比，其对共享最近邻居数K不敏感。实验结果表明，在人工合成数据集和UCI真实数据集上，SC-DANSN分离复杂结构和含噪声数据集的性能优于传统的谱聚类算法。下一步考虑使用分布式和并行算法构造相似性矩阵并计算特征向量，并将谱聚类算法应用于大数据集。