·898· 智能系统学报 第14卷 法(spectral clustering)。由于谱聚类在处理非凸 的亲和矩阵。同时采用共享近邻的方法发现密集 形结构的数据集方面的高效性，谱聚类在图像分 区域样本点分布的结构和密度信息，并且根据每 割2、社区检测、人脸识别阿等方面得到了广泛 个点所处领域的稠密程度自适应调节参数σ，与 的研究和应用。 高斯核距离测度相比，本文的解决方案对参数具 然而，传统的谱聚类算法在使用高斯核函数 有较强的鲁棒性，增强了对各种数据集的适应 构造亲和矩阵时，需要先验信息来设置合适的参 性，减少了噪声数据带来的不良影响。 数以控制邻域的尺度：并且以距离来度量数据点 之间的相似性，没有考虑到整体数据点的变化情 1相关算法理论 况，对于高维数据来说，较难得到更高的聚类精 1.1谱聚类算法 度。近年来有很多学者对谱聚类算法进行了研 在谱聚类中，设x1,x2,…,xn∈R为n个具有d 究。赵晓晓等结合稀疏表示和约束传递，提出 个特征的样本，数据集可用一个加权无向图来描 一种结合稀疏表示和约束传递的半监督谱聚类算 述，该图由Ⅵ个顶点和E个边组成。对于 法，进一步提高了聚类准确率。林大华等]针对 v:eV,表示一个样本，e表示：和之间的 现有子空间聚类算法没有利用样本自表达和稀疏 权重。e通常是由x和x;之间的相似性来度量 相似度矩阵，提出了一种新的稀疏样本自表达子 的。通常引入高斯核函数来构造相似矩阵S,其 空间聚类方法，所获得的相似度矩阵具有良好的 定义为 子空间结构和鲁棒性。Chang等提出了一种通 - 过嵌入标签传播来改进谱聚类的方法，通过密集 Si= i卡j (1) 0,i=j 的未标记数据区域传播标签。以上方法虽然一定 作为一种简单而有效的聚类准则，归一化割 程度上提高了谱聚类算法的聚类性能，但是，在 Ncut)在文献[14]中提出，其定义为 大部分谱聚类算法中，高斯核函数中尺度参数σ 的选取往往都是通过人工选取，对聚类结果有一 Ncut(A.B)=y(D-W)y (2) yDy 定的影响。NJW算法O对预先给定几个尺度参 式中：D是对角矩阵；y是最优分割向量。谱聚类 数σ进行谱聚类，最后从这几个聚类结果中选择 的一般过程为： 具有最佳聚类结果的σ作为尺度参数，该方法消 1)构造图G的相似度矩阵S,对于给定的σ， 除了尺度参数σ选择的人为因素，但是也增加了 S是由式(1)构造的： 计算时间。Ye等在有向KNN图中考虑了一种 2)计算对角矩阵D,构造对角矩阵D, 基于共享最近邻的鲁棒相似性度量，大大提高了 Da=∑S; 谱聚类的聚类精度。Jia等提出了一种基于共 3)计算归一化拉普拉斯矩阵，拉普拉斯矩阵 享近邻的自校正p谱聚类算法，该算法利用共享 L为L=D-S,L被归一化为 最近邻来度量数据间的相似性，然后应用果蝇优 L=D-1/PLD-1p=1-D-1PSD-12: 化算法找到p-laplacian矩阵的最优参数p,从而更 4)对L进行特征分解，得到前k个特征向 好地进行数据分类。王雅琳等]提出一种基于 量，并构建特征向量空间； 密度调整的改进自适应谱聚类算法，通过样本点 5)利用经典的聚类算法如k-means对特征向 的近邻距离自适应得到尺度参数，使算法对尺度 量空间中的特征向量进行聚类。 参数相对不敏感。 1.2AFS理论 传统的谱聚类以及上述大部分改进的谱聚类 AFS理论是刘晓东s-1)在1998年提出的一 算法都是单一的针对距离度量或者尺度参数进行 种基于AFS代数和AFS结构的模糊理论， 调整，本文从一个新的角度出发，在公理化模糊 AFS理论放弃使用距离度量来计算数据之间的相 集(AFS)理论的基础上，结合局部密度估计和共 似性关系，而是将观测数据转化为模糊隶属函 享近邻的定义，提出一种基于AFS理论的共享近 数，并实现其逻辑运算。然后，可以从AFS空间 邻自适应谱聚类算法一一公理化模糊共享近邻自 而不是原始特征空间中提取信息。在AFS空间 适应谱聚类算法。利用AFS理论提出了一种模 中利用模糊关系来构建数据之间的相似性度量。 糊相似性度量方法，并将其作为谱聚类算法输入 采用模糊隶属度来表示数据之间的距离关系，增法 (spectral clustering)[1]。由于谱聚类在处理非凸 形结构的数据集方面的高效性，谱聚类在图像分 割 [2-4] 、社区检测[5] 、人脸识别[6] 等方面得到了广泛 的研究和应用。 σ σ σ σ 然而，传统的谱聚类算法在使用高斯核函数 构造亲和矩阵时，需要先验信息来设置合适的参 数以控制邻域的尺度；并且以距离来度量数据点 之间的相似性，没有考虑到整体数据点的变化情 况，对于高维数据来说，较难得到更高的聚类精 度。近年来有很多学者对谱聚类算法进行了研 究。赵晓晓等[7] 结合稀疏表示和约束传递，提出 一种结合稀疏表示和约束传递的半监督谱聚类算 法，进一步提高了聚类准确率。林大华等[8] 针对 现有子空间聚类算法没有利用样本自表达和稀疏 相似度矩阵，提出了一种新的稀疏样本自表达子 空间聚类方法，所获得的相似度矩阵具有良好的 子空间结构和鲁棒性。Chang 等 [9] 提出了一种通 过嵌入标签传播来改进谱聚类的方法，通过密集 的未标记数据区域传播标签。以上方法虽然一定 程度上提高了谱聚类算法的聚类性能，但是，在 大部分谱聚类算法中，高斯核函数中尺度参数 的选取往往都是通过人工选取，对聚类结果有一 定的影响。NJW 算法[10] 对预先给定几个尺度参 数 进行谱聚类，最后从这几个聚类结果中选择 具有最佳聚类结果的 作为尺度参数，该方法消 除了尺度参数 选择的人为因素，但是也增加了 计算时间。Ye 等 [11] 在有向 KNN 图中考虑了一种 基于共享最近邻的鲁棒相似性度量，大大提高了 谱聚类的聚类精度。Jia 等 [12] 提出了一种基于共 享近邻的自校正 p 谱聚类算法，该算法利用共享 最近邻来度量数据间的相似性，然后应用果蝇优 化算法找到 p-laplacian 矩阵的最优参数 p，从而更 好地进行数据分类。王雅琳等[13] 提出一种基于 密度调整的改进自适应谱聚类算法，通过样本点 的近邻距离自适应得到尺度参数，使算法对尺度 参数相对不敏感。 传统的谱聚类以及上述大部分改进的谱聚类 算法都是单一的针对距离度量或者尺度参数进行 调整，本文从一个新的角度出发，在公理化模糊 集 (AFS) 理论的基础上，结合局部密度估计和共 享近邻的定义，提出一种基于 AFS 理论的共享近 邻自适应谱聚类算法——公理化模糊共享近邻自 适应谱聚类算法。利用 AFS 理论提出了一种模 糊相似性度量方法，并将其作为谱聚类算法输入 σ 的亲和矩阵。同时采用共享近邻的方法发现密集 区域样本点分布的结构和密度信息，并且根据每 个点所处领域的稠密程度自适应调节参数 ，与 高斯核距离测度相比，本文的解决方案对参数具 有较强的鲁棒性，增强了对各种数据集的适应 性，减少了噪声数据带来的不良影响。 1 相关算法理论 1.1 谱聚类算法 x1, x2,··· , xn ∈ R d n d |V| |E| vi ∈ V vi xi ei j vi vj ei j xi xj S 在谱聚类中，设 为 个具有 个特征的样本，数据集可用一个加权无向图来描 述，该图由 个顶点和 个边组成。对于 ， 表示一个样本 ， 表示 和 之间的 权重。 通常是由 和 之间的相似性来度量 的。通常引入高斯核函数来构造相似矩阵 ，其 定义为 Si j =      e − ( ∥xi−x j∥ 2 ) 2σ2 , i , j 0, i = j (1) 作为一种简单而有效的聚类准则，归一化割 (Ncut) 在文献 [14] 中提出，其定义为 Ncut(A,B) = y T (D−W) y y T Dy (2) 式中： D 是对角矩阵； y 是最优分割向量。谱聚类 的一般过程为： G S σ S 1) 构造图 的相似度矩阵 ,对于给定的 ， 是由式 (1) 构造的； D D Dii = ∑ 1⩽j⩽n Si j 2 ) 计算对角矩阵 ，构造对角矩阵 ， ； L = D−S 3) 计算归一化拉普拉斯矩阵，拉普拉斯矩阵 L 为 ，L 被归一化为 L = D −1/2LD−1/2 = I− D −1/2SD−1/2 ; 4) 对 L 进行特征分解，得到前 k 个特征向 量，并构建特征向量空间； 5) 利用经典的聚类算法如 k-means 对特征向 量空间中的特征向量进行聚类。 1.2 AFS 理论 AFS 理论是刘晓东[15-18] 在 1998 年提出的一 种 基 于 A F S 代 数 和 A F S 结构的模糊理论， AFS 理论放弃使用距离度量来计算数据之间的相 似性关系，而是将观测数据转化为模糊隶属函 数，并实现其逻辑运算。然后，可以从 AFS 空间 而不是原始特征空间中提取信息。在 AFS 空间 中利用模糊关系来构建数据之间的相似性度量。 采用模糊隶属度来表示数据之间的距离关系，增 ·898· 智 能 系 统 学 报 第 14 卷