第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sep.2019 D0:10.11992/tis.201810002 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20190527.1407.010.html 公理化模糊共享近邻自适应谱聚类算法 储德润，周治平 (江南大学物联网技术应用教育部工程研究中心，江苏无锡214122) 摘要：针对传统的谱聚类算法通常利用高斯核函数作为相似性度量，且单纯以距离决定相似性不能充分表现 原始数据中固有的模糊性、不确定性和复杂性，导致聚类性能降低的问题。提出了一种公理化模糊共享近邻自 适应谱聚类算法，首先结合公理化模糊集理论提出了一种模糊相似性度量方法，利用识别特征来衡量更合适的 数据成对相似性，然后采用共享近邻的方法发现密集区域样本点分布的结构和密度信息，并且根据每个点所处 领域的稠密程度自动调节参数，从而生成更强大的亲和矩阵，进一步提高聚类准确率。实验表明，相较于距 离谱聚类、自适应谱聚类、模糊聚类方法和地标点谱聚类，所提算法有着更好的聚类性能。 关键词：机器学习；数据挖掘；聚类分析；模糊聚类；谱聚类；公理化模糊集理论；共享最近邻：尺度参数 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)05-0897-08 中文引用格式：储德润，周治平.公理化模糊共享近邻自适应谱聚类算法机.智能系统学报，2019,14(5)：897-904 英文引用格式：CHU Derun,ZHOU Zhiping.Shared nearest neighbor adaptive spectral clustering algorithm based on axiomatic fuzzy set theory(J.CAAI transactions on intelligent systems,2019,14(5):897904. Shared nearest neighbor adaptive spectral clustering algorithm based on axiomatic fuzzy set theory CHU Derun,ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122.China) Abstract:For the traditional spectral clustering algorithm,the Gaussian kernel function is usually used as the similarity measure.However,the similarity of distance cannot fully express the ambiguity,uncertainty,and complexity inherent in the original data,resulting in the reduction of clustering performance.To solve this problem,we propose an axiomatic fuzzy set shared nearest neighbor adaptive spectral clustering algorithm.First,the proposed algorithm uses a fuzzy sim- ilarity measurement method based on axiomatic fuzzy set theory to measure more suitable data pairwise similarity by identifying features.Then,the structure and density information of sample point distribution in a dense area is obtained using the method of sharing the nearest neighbor,and the parameter o is automatically adjusted according to the density degree of each point in the domain,thereby generating a more powerful affinity matrix to further increase the accuracy rate of clustering.Experimental results show that the proposed algorithm has better clustering performance than dis- tance spectral clustering,adaptive spectral clustering,fuzzy clustering,and landmark spectral clustering. Keywords:machine learning,data mining,clustering analysis,fuzzy clustering,spectral clustering;axiomatic fuzzy set theory;shared nearest neighbor;scale parameter 聚类技术作为机器学习领域中的一种无监督挥着重要的作用。在过去的几十年中，许多聚类 技术，在检测数据的内在结构和潜在知识方面发 方法得到了发展，如基于分区的方法(k-means)、 基于模型的方法、基于密度的方法、层次聚类方 收稿日期：2018-10-03.网络出版日期：201905-28 通信作者：储德润.E-mail:CDR0727@163.com 法、模糊聚类方法(fuzzy c-means)和基于图的方
DOI: 10.11992/tis.201810002 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20190527.1407.010.html 公理化模糊共享近邻自适应谱聚类算法 储德润，周治平 （江南大学 物联网技术应用教育部工程研究中心，江苏 无锡 214122） 摘 要：针对传统的谱聚类算法通常利用高斯核函数作为相似性度量，且单纯以距离决定相似性不能充分表现 原始数据中固有的模糊性、不确定性和复杂性，导致聚类性能降低的问题。提出了一种公理化模糊共享近邻自 适应谱聚类算法，首先结合公理化模糊集理论提出了一种模糊相似性度量方法，利用识别特征来衡量更合适的 数据成对相似性，然后采用共享近邻的方法发现密集区域样本点分布的结构和密度信息，并且根据每个点所处 领域的稠密程度自动调节参数 σ，从而生成更强大的亲和矩阵，进一步提高聚类准确率。实验表明，相较于距 离谱聚类、自适应谱聚类、模糊聚类方法和地标点谱聚类，所提算法有着更好的聚类性能。 关键词：机器学习；数据挖掘；聚类分析；模糊聚类；谱聚类；公理化模糊集理论；共享最近邻；尺度参数 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)05−0897−08 中文引用格式：储德润, 周治平. 公理化模糊共享近邻自适应谱聚类算法 [J]. 智能系统学报, 2019, 14(5): 897–904. 英文引用格式：CHU Derun, ZHOU Zhiping. Shared nearest neighbor adaptive spectral clustering algorithm based on axiomatic fuzzy set theory[J]. CAAI transactions on intelligent systems, 2019, 14(5): 897–904. Shared nearest neighbor adaptive spectral clustering algorithm based on axiomatic fuzzy set theory CHU Derun，ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China) Abstract: For the traditional spectral clustering algorithm, the Gaussian kernel function is usually used as the similarity measure. However, the similarity of distance cannot fully express the ambiguity, uncertainty, and complexity inherent in the original data, resulting in the reduction of clustering performance. To solve this problem, we propose an axiomatic fuzzy set shared nearest neighbor adaptive spectral clustering algorithm. First, the proposed algorithm uses a fuzzy similarity measurement method based on axiomatic fuzzy set theory to measure more suitable data pairwise similarity by identifying features. Then, the structure and density information of sample point distribution in a dense area is obtained using the method of sharing the nearest neighbor, and the parameter σ is automatically adjusted according to the density degree of each point in the domain, thereby generating a more powerful affinity matrix to further increase the accuracy rate of clustering. Experimental results show that the proposed algorithm has better clustering performance than distance spectral clustering, adaptive spectral clustering, fuzzy clustering, and landmark spectral clustering. Keywords: machine learning; data mining; clustering analysis; fuzzy clustering; spectral clustering; axiomatic fuzzy set theory; shared nearest neighbor; scale parameter 聚类技术作为机器学习领域中的一种无监督 技术，在检测数据的内在结构和潜在知识方面发 挥着重要的作用。在过去的几十年中，许多聚类 方法得到了发展，如基于分区的方法 (k-means)、 基于模型的方法、基于密度的方法、层次聚类方 法、模糊聚类方法 (fuzzy c-means) 和基于图的方 收稿日期：2018−10−03. 网络出版日期：2019−05−28. 通信作者：储德润. E-mail：CDR0727@163.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2019
·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 卷
第5期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·899· 强了在处理现实数据中对各种数据集的适应性， 度属于另一个样本的描述，用模糊集表示为距离 为处理离群点提供了有效方法。 度量。在最初的AFS聚类92训基础上，在AFS空 在文献[15]中，根据EI代数的定义，对于任 间上构建相似性度量。 意概念集合ASM,Ⅱm表示A中模糊概念的集 首先建立隶属度函数，需要定义以下有序关 合，为了更好地提取数据结构，清楚地说明可将 系：设X是一个样本集合，M是X上的一组模糊 AFS理论结合以下场景： 集合。对于任意A,SM,x∈X,可以写成： 设X={x,x,…,x6}是6个人的样本集合及其 A:≥(x)=yeXx≥my,for VmEA;}∈X (6) 特征（属性），由真实数字（年龄、身高、体重）、布 式中：m∈M;“x≥my”表示m代表x的模糊关系大 尔值（性别）、额定值（黑色素）和顺序关系（发黑、 于或等于m代表y的模糊关系；A,≥(x)是x中所 发白)描述；M={m1,m2,,m6}是样本X上的模糊 有模糊关系小于或等于Ⅱm的x样本中的元素 概念集。M中的每一个元素都被看作描述事物 的集合。A≥()是由A,模糊集的语义和观测数 的简单概念，它们相应的语言标签被定义为： 据集的概率分布决定的。 m(老年人)、m2(高的人)、m(重的人)人、m(头发黑色 对于模糊集合∈E,:X→[O,1]。根据文献 素更多的)、ms(男性)、m6(女性)。则A1={m1,m6}S [17刀，e(x)∈E}是AFS模糊逻辑系统(E,V,)的 M,·m=m6是一个新的复杂概念“老年女人”； 一组相关隶属度函数，则满足条件： A2={m1,m3}≤M,Πm=mm3表示“重的老年人”； 1)对于a,BEE,如果a≤B在系统(E,V,A) A=m}≤M,nm=m表示“高的人”。对于 内，并且对于任意x∈X,4(x)≤g()都成立； y=mm6+mm3+m2,它的概念为“老年女人”或者 2)对于xeX,n=meE,如果对于任意 “重的老年人”或者“高的人”，是一个复杂概念的 ie1,A:≥(x)=⑦，则4()=0： 集合。一个新的模糊集可以被写成： 3)对于xy∈X,A:M,n=Ⅱm∈E,如果 2g小县m+县m+思 (3) A≥(x)A:≥(x,则4，(x)≤4，：如果A≥(x)=X, 则4n(x)=1。 这些基于简单概念的EI代数运算生成的概 确定相关性隶属函数首先要确定X上的测 念被认为复杂的概念。 度。下面给出了实现该测度的具体内容。设y是 因此，概念的逻辑表达可以用m表示 关于X的一个模糊项。文献[17刀中A:的权重函 (A,SM,i∈D。若m是非空集，集合E定义为 数被定义为： 设P,:X→R*=[0,o),如果P,满足条件： A. (4) 1)Py(x)=0台x<mx,x∈X: 式中1为非空索引集。 2)P(x)≥Py)台xmy,x,y∈X。 则称P,为模糊项y的权重函数。 其中，每个模糊集可以被唯一地分解： 设(2，f,P)是一个概率测度空间，M是X上 =a叫 (5) 的一组模糊集合，P,是模糊项y∈M的权重函数， 式中A,是M的子集。 X≤2是概率空间(2，f,P)上的一个有限观测样本 集。如果对于任意的m∈M,x∈2；m≥(x)∈f,则 2所提算法 {(x)∈E}是(E,V,A)的一组相关隶属度函数， 2.1在模糊空间建立距离度量 条件是每个模糊集5=口m eE的隶属函数被 本文提出的亲和矩阵构造方法是建立在 定义为 AFS理论基础上的，该过程允许我们在发现的判 Py(u) 别模糊子空间中表示不同模糊项的样本。这些子 ()=supinf Hx∈X ∑Pv(0 (7) 空间由模糊隶属函数选择，消除了不明显或噪声 特征。因此，它们被认为能够改善内部相似和减 ()dp ue (x)=supinf- Hx∈2 (8) 少相互相似。此外，利用AFS中定义的模糊隶属 ∑P,0dP,, 度和逻辑运算，放宽了欧氏假设对数据距离推断 如果对于每个y∈M,P,()在2上是连续的 的影响。更具体地说，本文使用一个样本的隶属 且XW是从概率空间(2，f,P)中随机抽取的一组样
强了在处理现实数据中对各种数据集的适应性， 为处理离群点提供了有效方法。 A ⊆ M Π m∈A m 在文献 [15] 中，根据 EI 代数的定义，对于任 意概念集合 ， 表示 A 中模糊概念的集 合，为了更好地提取数据结构，清楚地说明可将 AFS 理论结合以下场景： X = {x1, x2,· · ·, x6} M = {m1,m2,· · ·,m6} X M m1 m2 m3 m4 m5 m6 A1 = {m1,m6} ⊆ Π m∈A1 m = m1m6 A2 = {m1,m3} ⊆ M Π m∈A2 m = m1m3 A3 = {m3} ⊆ M Π m∈A3 m = m3 γ = m1m6 +m1m3 +m2 设 是 6 个人的样本集合及其 特征 (属性)，由真实数字 (年龄、身高、体重)、布 尔值 (性别)、额定值 (黑色素) 和顺序关系 (发黑、 发白) 描述； 是样本 上的模糊 概念集。 中的每一个元素都被看作描述事物 的简单概念，它们相应的语言标签被定义为： (老年人)、 (高的人)、 (重的人)、 (头发黑色 素更多的)、 (男性)、 (女性)。则 M， 是一个新的复杂概念“老年女人”； ， 表示“重的老年人”； ， 表 示 “ 高的人 ” 。对于 ，它的概念为“老年女人”或者 “重的老年人”或者“高的人”，是一个复杂概念的 集合。一个新的模糊集可以被写成: ∑3 i=1 ( Π m∈Ai m ) = Π m∈A1 m+ Π m∈A2 m+ Π m∈A3 m (3) 这些基于简单概念的 EI 代数运算生成的概 念被认为复杂的概念。 ∑ i∈I ( Π m∈Ai m ) (Ai ⊆ M,i ∈ I) m E 因此，概念的逻辑表达可以用 表示 。若 是非空集，集合 定义为 E = ∑ i∈I ( Π m∈Ai m ) Ai ⊆ M,i ∈ I (4) 式中 I 为非空索引集。 其中，每个模糊集可以被唯一地分解： ξ = ∑ i∈I ( Π m∈Ai m ) (5) 式中 Ai 是 M 的子集。 2 所提算法 2.1 在模糊空间建立距离度量 本文提出的亲和矩阵构造方法是建立 在 AFS 理论基础上的，该过程允许我们在发现的判 别模糊子空间中表示不同模糊项的样本。这些子 空间由模糊隶属函数选择，消除了不明显或噪声 特征。因此，它们被认为能够改善内部相似和减 少相互相似。此外，利用 AFS 中定义的模糊隶属 度和逻辑运算，放宽了欧氏假设对数据距离推断 的影响。更具体地说，本文使用一个样本的隶属 度属于另一个样本的描述，用模糊集表示为距离 度量。在最初的 AFS 聚类[19-21] 基础上，在 AFS 空 间上构建相似性度量。 Ai ⊆ M x ∈ X 首先建立隶属度函数，需要定义以下有序关 系：设 X 是一个样本集合，M 是 X 上的一组模糊 集合。对于任意 ， ，可以写成： Ai ⩾ (x) = {y ∈ X |x⩾my, for ∀m ∈ Ai } ⊆ X (6) m ∈ M x ⩾m y m x m y Ai ⩾ (x) x Π m∈Ai m x Ai ⩾ (x) Ai 式中： ；“ ”表示 代表 的模糊关系大 于或等于 代表 的模糊关系； 是 中所 有模糊关系小于或等于 的 样本中的元素 的集合。 是由 模糊集的语义和观测数 据集的概率分布决定的。 ξ ∈ E µξ : X → [0,1] { µξ (x)|ξ ∈ E } (E,∨,∧) 对于模糊集合 ， 。根据文献 [17]， 是 AFS 模糊逻辑系统 的 一组相关隶属度函数，则满足条件： α, β ∈ E α ⩽ β (E,∨,∧) x ∈ X µα (x) ⩽ µβ (x) 1 ) 对 于 ，如果 在系统 内，并且对于任意 ， 都成立； x ∈ X η = ∑ i∈I ( Π m∈Ai m ) ∈ E i ∈ I Ai ⩾ (x) = ∅ µη (x) = 0 2) 对于 ， ，如果对于任意 ， ，则 ； x, y ∈ X Ai ⊆ M η = Π m∈Ai m ∈ E Ai ⩾ (x) ⊆ Ai ⩾ (x) µη (x) ⩽ µη (y) Ai ⩾ (x) = X µη (x) = 1 3 ) 对 于 ， ， ，如果 ，则 ；如果 ， 则 。 X γ X Ai 确定相关性隶属函数首先要确定 上的测 度。下面给出了实现该测度的具体内容。设 是 关于 的一个模糊项。文献 [17] 中 的权重函 数被定义为： ργ : X → R + 设 = [0,∞), 如果 ργ 满足条件： 1) ργ (x) = 0 ⇔ x(x) ργ (t)dPt ∑ Ω ργ (t)dPt , ∀x ∈ Ω (8) γ ∈ M ργ (x) Ω |X| (Ω, f,P) 如果对于每个 ， 在 上是连续的 且 是从概率空间 中随机抽取的一组样 第 5 期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·899·
·900· 智能系统学报 第14卷 本集，则式(7)所定义的隶属函数等于式(8)所定 义的隶属函数。 4(X)= {k∈x (14) 根据以上可知，在E中模糊概念的隶属函数 可以由P,(x)和A:≥(x)来确定，这既考虑了模糊 式中：4m(X)表示数据样本模糊项m:的X,的模 性又考虑了随机性。根据文献[17]，对于任意模 糊隶属度；m表示模糊项集合x中的每个模糊 糊概念专=∑Ⅱm∈E,对于任意x∈X,专的隶属 项；（巛）表示模糊项集合x的数据样本X的 函数被定义为 平均隶属度。 在AFS理论的基础上，为了更好地提取数据 Ha(x)=sup A:≥(x (9) 结构，在AFS空间中建立了距离测量，公式为 yeXx≥ay,YmeA u(x)=sup (10) (15) iel X 式中D,为式(13)所示基于公理化模糊集理论的 式中Pm是一个权重函数。 距离定义。 接着设样本集为X={m,,,xSR,X上的 2.2所提算法 一个特征集合F={f,f五，…，f,M={ml1≤i≤l,1≤ 在2.1小节中虽然利用AFS理论在谱聚类算法 j≤k}表示一组相对于特征的选择的k个模糊 中构建了新的距离度量，即A(x,x)=exp(-D/2r2) 概念的集合，m,m2,…,m是其中与特征f相对 但是高斯核函数中σ是一个人工指定的参数，为 应的一组简单模糊概念。在新的测度空间中，对 每个数据集指定一个合适的参数σ是一件很复 于每一个样本x,发现一个显著的模糊子集 杂的事，需要花费大量的时间和精力。本文将数 g=nm,以便g.有效地表示x,而不是整个模糊 据点的领域信息加入相似度的计算中，并结合共 集。这里，如果x属于m的隶属度大于某一阈 享近邻的思想，在AFS理论距离测量的基础上定 值，则模糊隶属函数用作特征的度量，m足够好 义了一个能够自适应得到尺度参数σ的高斯核 地将与其他值区分开。在这里定义： 函数一一基于AFS理论的共享近邻自适应高斯 B5={m∈Mlum(x)≥max{μm(c)}-e} (11) 核函数，其定义为 式中：s表示误差阈值20，在这里设s=0.3,通过 D i≠j 设定误差阈值避免了使用模糊隶属函数的不明显 A(xi,xi) exp ,(SNN(x,x)+1) 0,i=j 特征，使样本的表示方法能够更好地表达数据中 (16) 的底层语义结构，排除了噪声对数据样本特征的 式中σ：的取值由数据点：的K个最近邻确定， 干扰，若对误差阈值运用自适应策略，将明显增 通常为K=7。根据文献[22]可知，K的选择与 加算法的计算复杂度。考虑本文算法的总体性能 尺度参数无关，并且是嵌入空间数据维数的函 表现，实验中参考文献[20]中的经验数值进行设 数，通过K共享近邻的方法能够根据数据样本本 定。B表示关于数据样本x的全部的模糊项的 身之间的关系自适应的获得更加适合的尺度参 集合。然后将5描述为 数，避免了选取尺度参数给算法带来的不确定 .=tem (12) 性。其计算方法为 式中∧是AFS代数中的模糊隶属关系运算。通 0i= d(x,xm） (17) 过这样表示，所有理想的模糊项都结合在一起作 为样本表示。然后，通过AFS代数和AFS理论中 式中：σ：表示样本点x:和其K个最近邻距离的平 的模糊运算，结合模糊隶属度的关系，通过逻辑 均值；同理σ，表示样本点x和其K个最近邻距 运算的数据距离推理，将模糊集表示的另一个 离的平均值。SNN(x,x)表示样本点：和x在K 邻域内所共有的邻居个数。SNN(x,x)反映了x 描述样本的隶属度用作距离度量。根据AFS聚 类92训，对于两个数据样本X和X,它们之间的距 和x点的局部密度，可以用来提高数据点间的相 似性，有助于样本点正确的划分。 离定义为： 2.3所提算法流程 Dij=1-min Fx (X ),Fcs (Xj) (13) 算法公理化模糊共享近邻自适应谱聚类算
本集，则式 (7) 所定义的隶属函数等于式 (8) 所定 义的隶属函数。 ργ (x) Ai ⩾ (x) ξ = ∑ i∈I ( Π γ∈Ai m ) ∈ E x ∈ X ξ 根据以上可知，在 E 中模糊概念的隶属函数 可以由 和 来确定，这既考虑了模糊 性又考虑了随机性。根据文献 [17]，对于任意模 糊概念 ，对于任意 ， 的隶属 函数被定义为 µξ (x) = sup i∈I { |Ai ⩾ (x)| |X| } (9) µξ (x)= sup i∈I y ∈ X x⩾ρm y,∀m ∈ Ai |X| (10) 式中 ρm 是一个权重函数。 X = {x1, x2,· · ·, xn} ⊆ R X F = {f1, f2,· · ·, fl} M = {mi, j |1 ⩽ i ⩽ l, 1 ⩽ j ⩽ ki} fi ki mi,1,mi,2,· · ·,mi,ki fi x ζx = Π m∈M m ζx x xk mi, j mi, j xk 接着设样本集为 ， 上的 一个特征集合 ， 表示一组相对于特征 的选择的 个模糊 概念的集合， 是其中与特征 相对 应的一组简单模糊概念。在新的测度空间中，对 于每一个样本 ，发现一个显著的模糊子集 ，以便 有效地表示 ，而不是整个模糊 集。这里，如果 属于 的隶属度大于某一阈 值，则模糊隶属函数用作特征的度量， 足够好 地将 与其他值区分开。在这里定义： B ε x = {m ∈ M |µm (x) ⩾ max{µm (x)}−ε} (11) ε ε = 0.3 B ε x x ζx 式中： 表示误差阈值[20] ，在这里设 ，通过 设定误差阈值避免了使用模糊隶属函数的不明显 特征，使样本的表示方法能够更好地表达数据中 的底层语义结构，排除了噪声对数据样本特征的 干扰，若对误差阈值运用自适应策略，将明显增 加算法的计算复杂度。考虑本文算法的总体性能 表现，实验中参考文献 [20] 中的经验数值进行设 定。 表示关于数据样本 的全部的模糊项的 集合。然后将 描述为 ζx = ∧ m∈Bε x m (12) ∧ Xi Xj 式中 是 AFS 代数中的模糊隶属关系运算。通 过这样表示，所有理想的模糊项都结合在一起作 为样本表示。然后，通过 AFS 代数和 AFS 理论中 的模糊运算，结合模糊隶属度的关系，通过逻辑 运算的数据距离推理，将模糊集表示的另一个 描述样本的隶属度用作距离度量。根据 AFS 聚 类 [19-21] ，对于两个数据样本 和 ，它们之间的距 离定义为： Di j = 1−min{ µ¯ ζXi (Xi),µ¯ ζXj ( Xj ) } (13) µ¯ ζXi ( Xj ) = mk ∈ ζXi ∑N k=1 µmk ( Xj ) N (14) µmk ( Xj ) mk Xj mk ζXi µ¯ ζXi ( Xj ) ζXi Xj 式中： 表示数据样本模糊项 的 的模 糊隶属度； 表示模糊项集合 中的每个模糊 项； 表示模糊项集合 的数据样本 的 平均隶属度。 在 AFS 理论的基础上，为了更好地提取数据 结构，在 AFS 空间中建立了距离测量，公式为 A ( xi , xj ) = exp( − Di j 2 2σ2 ) (15) 式中 Di j 为式 (13) 所示基于公理化模糊集理论的 距离定义。 2.2 所提算法 A ( xi , xj ) = exp( −Di j 2 /2σ 2 ) σ σ σ 在 2.1 小节中虽然利用 AFS 理论在谱聚类算法 中构建了新的距离度量，即 , 但是高斯核函数中 是一个人工指定的参数，为 每个数据集指定一个合适的参数 是一件很复 杂的事，需要花费大量的时间和精力。本文将数 据点的领域信息加入相似度的计算中，并结合共 享近邻的思想，在 AFS 理论距离测量的基础上定 义了一个能够自适应得到尺度参数 的高斯核 函数——基于 AFS 理论的共享近邻自适应高斯 核函数，其定义为 A ( xi , xj ) = exp( − Di j 2 σiσj ( SNN( xi , xj ) +1 ) ) , i , j 0, i = j (16) σi xi K = 7 K K 式中 的取值由数据点 的 K 个最近邻确定， 通常为 [22]。根据文献 [22] 可知， 的选择与 尺度参数无关，并且是嵌入空间数据维数的函 数，通过 共享近邻的方法能够根据数据样本本 身之间的关系自适应的获得更加适合的尺度参 数，避免了选取尺度参数给算法带来的不确定 性。其计算方法为 σi = 1 K ∑K m=1 d (xi , xm) (17) σi xi K σj xj SNN( xi , xj ) xi xj K SNN( xi , xj ) xi xj 式中： 表示样本点 和其 个最近邻距离的平 均值；同理 表示样本点 和其 K 个最近邻距 离的平均值。 表示样本点 和 在 邻域内所共有的邻居个数。 反映了 和 点的局部密度，可以用来提高数据点间的相 似性，有助于样本点正确的划分。 2.3 所提算法流程 算法 公理化模糊共享近邻自适应谱聚类算 ·900· 智 能 系 统 学 报 第 14 卷
第5期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·901· 法(AFSSNNSC) 表1UCI实验数据集的特性 输入数据集X={x,,,x小，目标聚类数k Table 1 Characteristics of the UCI experimental datasets 输出聚类实际产生y类。 数据集 数据总量 维数 类数 1)首先为数据点的每个特征构造模糊关系 Heart 270 13 2 模糊项m Hepatitis 155 19 2 2)使用式(10)计算每个数据点的隶属度函数 Sonar 208 60 2 Wobc 699 9 2 umeM (x); Wdbc 569 30 2 3)通过式(11)找出模糊项的集合B; Iris 150 3 4)通过C.=Am构建每个样本的描述g: Wine 178 13 3 5)根据(.利用式(13)计算成对距离D: Protein 552 77 8 6)通过式(17计算σ：和σ： Libras 360 90 5 7)利用式(16)构建亲和矩阵A; LetterRec 20000 16 26 581012 54 > 8)根据Da=∑S计算对角矩阵D: Covtype 9)计算归一化拉普拉斯矩阵，拉普拉斯矩阵 基于聚类误差(CE)的实验结果如表2所示， L由L=D-S被归一化为 由表2可知所提的方法在大部分实验数据集上均 L=D-IPLD-IP =I-D-IPSD-IP 获得了优于对比算法的CE值；所提出的方法在 10)对L进行特征分解，得到前k个特征向 Heart、Hepatitis、Wdbc、Protein和Libras数据集上 量，并构建特征向量空间： 的CE分别为15.27%、27.14%、6.03%、51.12%、 11)利用经典的聚类算法如k-means对特征 52.31%,相比较AFS算法而言均改进了10%以 向量空间中的特征向量进行聚类。 上，在其他5个数据集上的CE相比较AFS也均 有所提高。证明了利用谱理论对相似矩阵进行划 3实验与结果分析 分比之前提出的传递闭包理论好得多，考虑到传 3.1实验环境及性能指标 递闭包方法的验证循环，所提出的方法也相对更 在UCI、USPS手写数字的相同数据集上，采 快、更容易实现。在Iris、Wine数据集中，所提算 用本文提出的方法和文献[10]的NJW谱聚类 法的CE分别为7.42%和2.89%，相对聚类错误率 (SC)、文献[21]的AFS聚类算法(AFS)、文献[22] 略高于ST$C算法。因为这两个数据集中只有 的self-tuning spectral clustering(STSC)算法、基于 150个样本和178个样本，但是差异实际上只有 K均值的近似谱聚类(KASP)2、基于Nystrom近 一两个样本，但相对于总体而言，所提算法CE普 似谱聚类(Nystrom)2和基于地标点谱聚类算法 遍低于其他算法在各数据集上的结果，仍具有较 LSC-R,LSC-K)2进行对比实验。本文算法实验 好的优越性；与基于距离度量的方法相比所提算 是在MATLAB2014b,计算机的硬件配置为Intel 法在给出的所有数据集中都显示出了优越性，在 Sonar数据集上更加改进5%以上，本文算法与基 i7-4770CPU3.40GHz、16 GB RAM的平台下进 于Nystrom近似谱聚类方法相比在所有数据集上 行。为了评估所提算法的聚类性能，本文使用聚 均有1%以上的优势。本文算法与基于地标点的 类误差(CE)2和归一化互信息(NM22种性能 谱聚类方法LSC-R和LSC-K相比也展现出较好 指标对本文算法与其他聚类方法的聚类结果进行 的聚类性能。这是因为通过模糊隶属函数代替距 了比较。其中CE被广泛用于评价聚类性能， 离度量数据之间的相似性，利用模糊语义结构解 CE越低聚类性能越好。NMI也是一种广泛使用 释数据之间的复杂的相互关系，增强了算法的鲁 的评估算法聚类性能的测量标准，NMI越大性能 棒性。对于Protein、Libras等多聚类数据集，AFS 越好。 的聚类错误率偏高，因为AFS聚类需要根据每个 3.2UCI数据集实验结果与分析 集群的边界选择最好的数据聚类分区。随着集群 为了验证所提出算法的有效性，本文将所提 规模数量的不断增加，将很难去清晰地找到边 的算法和其他方法应用于UCI数据库中的11个 界，这样聚类误差也会随之增高。总体而言，与对 基准数据集作为测试样本，表1为这11类数据集 比文献方法相比，所提算法的CE值在所有实验 的特征，分别是数据总量、维数以及类的个数。 数据集上均得到了改善，降低了算法的聚类错误率
法 (AFSSNNSC) 输入 数据集 X = {x1, x2,· · ·, xn} ，目标聚类数 k ； 输出 聚类实际产生 y 类。 fi mi, j 1) 首先为数据点的每个特征 构造模糊关系 模糊项 ； µm∈M (x) 2) 使用式 (10) 计算每个数据点的隶属度函数 ； B ε 3 x ) 通过式 (11) 找出模糊项的集合 ； ζx = ∧ m∈Bε x 4) 通过 m 构建每个样本的描述 ζx； 5) 根据 ζx 利用式 (13) 计算成对距离 Di j ； 6) 通过式 (17) 计算 σi 和 σj ； 7) 利用式 (16) 构建亲和矩阵 A ； Dii = ∑ 1⩽j⩽n 8) 根据 Si j 计算对角矩阵 D ； L L = D−S 9) 计算归一化拉普拉斯矩阵，拉普拉斯矩阵 由 被归一化为 L = D −1/2LD−1/2 = I− D −1/2SD−1/2 10) 对 L 进行特征分解，得到前 k 个特征向 量，并构建特征向量空间； 11) 利用经典的聚类算法如 k-means 对特征 向量空间中的特征向量进行聚类。 3 实验与结果分析 3.1 实验环境及性能指标 在 UCI、USPS 手写数字的相同数据集上，采 用本文提出的方法和文献 [10] 的 NJW 谱聚类 (SC)、文献 [21] 的 AFS 聚类算法 (AFS)、文献 [22] 的 self-tuning spectral clustering(STSC) 算法、基于 K 均值的近似谱聚类 (KASP)[23] 、基于 Nystrom 近 似谱聚类 (Nystrom)[24] 和基于地标点谱聚类算法 (LSC-R，LSC-K)[25] 进行对比实验。本文算法实验 是在 MATLAB 2014b，计算机的硬件配置为 Intel i7-4770 CPU 3.40 GHz、16 GB RAM 的平台下进 行。为了评估所提算法的聚类性能，本文使用聚 类误差 (CE)[26] 和归一化互信息 (NMI)[27] 2 种性能 指标对本文算法与其他聚类方法的聚类结果进行 了比较。其中 CE 被广泛用于评价聚类性能， CE 越低聚类性能越好。NMI 也是一种广泛使用 的评估算法聚类性能的测量标准，NMI 越大性能 越好。 3.2 UCI 数据集实验结果与分析 为了验证所提出算法的有效性，本文将所提 的算法和其他方法应用于 UCI 数据库中的 11 个 基准数据集作为测试样本，表 1 为这 11 类数据集 的特征，分别是数据总量、维数以及类的个数。 表 1 UCI 实验数据集的特性 Table 1 Characteristics of the UCI experimental datasets 数据集 数据总量 维数 类数 Heart 270 13 2 Hepatitis 155 19 2 Sonar 208 60 2 Wobc 699 9 2 Wdbc 569 30 2 Iris 150 4 3 Wine 178 13 3 Protein 552 77 8 Libras 360 90 15 LetterRec 20 000 16 26 Covtype 581 012 54 7 基于聚类误差 (CE) 的实验结果如表 2 所示， 由表 2 可知所提的方法在大部分实验数据集上均 获得了优于对比算法的 CE 值；所提出的方法在 Heart、Hepatitis、Wdbc、Protein 和 Libras 数据集上 的 CE 分别为 15.27%、27.14%、6.03%、51.12%、 52.31%，相比较 AFS 算法而言均改进了 10% 以 上，在其他 5 个数据集上的 CE 相比较 AFS 也均 有所提高。证明了利用谱理论对相似矩阵进行划 分比之前提出的传递闭包理论好得多，考虑到传 递闭包方法的验证循环，所提出的方法也相对更 快、更容易实现。在 Iris、Wine 数据集中，所提算 法的 CE 分别为 7.42% 和 2.89%，相对聚类错误率 略高于 STSC 算法。因为这两个数据集中只有 150 个样本和 178 个样本，但是差异实际上只有 一两个样本，但相对于总体而言，所提算法 CE 普 遍低于其他算法在各数据集上的结果，仍具有较 好的优越性；与基于距离度量的方法相比所提算 法在给出的所有数据集中都显示出了优越性，在 Sonar 数据集上更加改进 5% 以上，本文算法与基 于 Nystrom 近似谱聚类方法相比在所有数据集上 均有 1% 以上的优势。本文算法与基于地标点的 谱聚类方法 LSC-R 和 LSC-K 相比也展现出较好 的聚类性能。这是因为通过模糊隶属函数代替距 离度量数据之间的相似性，利用模糊语义结构解 释数据之间的复杂的相互关系，增强了算法的鲁 棒性。对于 Protein、Libras 等多聚类数据集，AFS 的聚类错误率偏高，因为 AFS 聚类需要根据每个 集群的边界选择最好的数据聚类分区。随着集群 规模数量的不断增加，将很难去清晰地找到边 界，这样聚类误差也会随之增高。总体而言，与对 比文献方法相比，所提算法的 CE 值在所有实验 数据集上均得到了改善，降低了算法的聚类错误率。 第 5 期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·901·
·902· 智能系统学报 第14卷 表2UCI数据集上的CE比较 Table 2 Comparison of CE on the UCI datasets % 数据集 KASP SC STSC AFS Nystrom LSC-R LSC-K 本文算法 Heart 19.47 19.63 21.14 29.62 21.64 17.18 16.25 15.27 Hepatitis 37.48 29.72 38.77 44.18 36.74 31.36 29.43 27.14 Sonar 40.25 42.38 42.85 37.24 40.57 39.26 38.27 35.61 Wobc 3.31 3.45 3.37 2.78 3.24 3.12 2.84 2.72 Wdbc 8.58 9.54 7.27 18.13 8.32 6.85 6.53 6.03 Iris 9.57 10.05 7.31 9.66 9.34 8.78 8.62 7.42 Wine 3.62 3.46 2.82 3.47 3.74 3.36 3.15 2.89 Protein 56.53 53.74 56.28 64.65 56.35 54.37 53.58 51.12 Libras 57.56 55.46 53.48 62.76 58.82 56.27 55.63 52.31 LetterRec 45.42 47.83 46.56 48.35 45.27 43.85 43.26 41.37 Covertype 53.81 54.76 54.36 52.25 53.68 52.85 52.24 51.15 在归一化互信息NM⑩中测量的聚类性能如 性更加复杂。所以在Covertype数据集下所有算 表3所示。所提出的算法的聚类结果NMI与其 法的NMI都普遍较低，但是所提算法获得了比其 他方法的NMI相比都得到了改善，尤其在 他算法更好的聚类效果。 Heart和Protein数据集上，所提算法相对于 从实验结果可以看出，STSC不是很稳定，它 KASP、SC、STSC、AFS和Nystrom对比算法而言 在Hepatitis和Sonar数据集上的NMI情况都非常 NM均提高了5%以上。只是在Wine数据集上， 差，由于在STSC和本文算法中都考虑到了数据 所提算法的NM为87.86%，与其他算法相当，但 之间的相互关系，利用到了数据邻居的近邻作 在整个对比表格中为最好的聚类性能。由于所 用，所以可以从中得出结论，与考虑到数据样本 选Covertype数据集是一个从地图变量预测森林 关系之间的传统距离度量作为相似性度量相比， 覆盖类型的数据集，它们都主要是在荒野地区发 采用具有数据样本模糊关系的模糊隶属度作为距 现的，所以覆盖类型在实际地理上是非常接近 离度量，在相似性度量上更具有鲁棒性。总体而 的，相对于其他数据集而言，这个数据集数据特 言，所提算法相较于对比算法都具有明显的改善。 表3UCI数据集上的NMⅡ比较 Table 3 Comparison of NMI on the UCI datasets % 数据集 KASP SC STSC AFS Nystrom LSC-R LSC-K 本文算法 Heart 32.61 28.51 25.83 17.62 30.37 35.45 37.11 38.18 Hepatitis 14.84 14.55 4.84 3.23 14.68 15.16 15.33 15.86 Sonar 14.53 7.56 1.67 17.22 12.15 16.48 17.23 19.09 Wobc 78.57 77.12 80.04 73.86 78.34 80.49 81.13 81.76 Wdbc 65.69 63.33 61.45 60.31 64.57 67.14 67.62 68.97 Iris 79.73 77.85 79.21 78.57 78.67 80.24 80.75 81.46 Wine 87.59 87.32 86.93 85.56 87.46 87.61 87.69 87.86 Protein 56.17 54.42 46.25 35.63 56.83 59.43 60.85 62.18 Libras 65.48 63.72 64.91 38.14 64.63 66.37 66.88 68.07 LetterRec 40.16 35.19 37.67 34.53 39.12 37.34 39.63 41.27 Covertype 7.44 6.87 7.19 6.54 7.42 8.31 9.02 9.83 3.3USPS数据集实验结果与分析 局通过扫描信封中的手写数字获得的数字数据。 选择两个典型谱聚类算法SC和STSC与所 原始扫描的数字是二进制的，大小和方向不同。 提方法在广泛使用的USPS数据库中的手写数字 本文使用的图像经过了大小归一化，得到了 数据集进行对比实验。该数据集包含美国邮政总 1616张256维的灰度图像。它包含7291个训练
表 2 UCI 数据集上的 CE 比较 Table 2 Comparison of CE on the UCI datasets % 数据集 KASP SC STSC AFS Nystrom LSC-R LSC-K 本文算法 Heart 19.47 19.63 21.14 29.62 21.64 17.18 16.25 15.27 Hepatitis 37.48 29.72 38.77 44.18 36.74 31.36 29.43 27.14 Sonar 40.25 42.38 42.85 37.24 40.57 39.26 38.27 35.61 Wobc 3.31 3.45 3.37 2.78 3.24 3.12 2.84 2.72 Wdbc 8.58 9.54 7.27 18.13 8.32 6.85 6.53 6.03 Iris 9.57 10.05 7.31 9.66 9.34 8.78 8.62 7.42 Wine 3.62 3.46 2.82 3.47 3.74 3.36 3.15 2.89 Protein 56.53 53.74 56.28 64.65 56.35 54.37 53.58 51.12 Libras 57.56 55.46 53.48 62.76 58.82 56.27 55.63 52.31 LetterRec 45.42 47.83 46.56 48.35 45.27 43.85 43.26 41.37 Covertype 53.81 54.76 54.36 52.25 53.68 52.85 52.24 51.15 在归一化互信息 (NMI) 中测量的聚类性能如 表 3 所示。所提出的算法的聚类结果 NMI 与其 他方法 的 N M I 相比都得到了改善，尤其 在 Heart 和 Protei n 数据集上，所提算法相对 于 KASP、SC、STSC、AFS 和 Nystrom 对比算法而言 NMI 均提高了 5% 以上。只是在 Wine 数据集上， 所提算法的 NMI 为 87.86%，与其他算法相当，但 在整个对比表格中为最好的聚类性能。由于所 选 Covertype 数据集是一个从地图变量预测森林 覆盖类型的数据集，它们都主要是在荒野地区发 现的，所以覆盖类型在实际地理上是非常接近 的，相对于其他数据集而言，这个数据集数据特 性更加复杂。所以在 Covertype 数据集下所有算 法的 NMI 都普遍较低，但是所提算法获得了比其 他算法更好的聚类效果。 从实验结果可以看出，STSC 不是很稳定，它 在 Hepatitis 和 Sonar 数据集上的 NMI 情况都非常 差，由于在 STSC 和本文算法中都考虑到了数据 之间的相互关系，利用到了数据邻居的近邻作 用，所以可以从中得出结论，与考虑到数据样本 关系之间的传统距离度量作为相似性度量相比， 采用具有数据样本模糊关系的模糊隶属度作为距 离度量，在相似性度量上更具有鲁棒性。总体而 言，所提算法相较于对比算法都具有明显的改善。 表 3 UCI 数据集上的 NMI 比较 Table 3 Comparison of NMI on the UCI datasets % 数据集 KASP SC STSC AFS Nystrom LSC-R LSC-K 本文算法 Heart 32.61 28.51 25.83 17.62 30.37 35.45 37.11 38.18 Hepatitis 14.84 14.55 4.84 3.23 14.68 15.16 15.33 15.86 Sonar 14.53 7.56 1.67 17.22 12.15 16.48 17.23 19.09 Wobc 78.57 77.12 80.04 73.86 78.34 80.49 81.13 81.76 Wdbc 65.69 63.33 61.45 60.31 64.57 67.14 67.62 68.97 Iris 79.73 77.85 79.21 78.57 78.67 80.24 80.75 81.46 Wine 87.59 87.32 86.93 85.56 87.46 87.61 87.69 87.86 Protein 56.17 54.42 46.25 35.63 56.83 59.43 60.85 62.18 Libras 65.48 63.72 64.91 38.14 64.63 66.37 66.88 68.07 LetterRec 40.16 35.19 37.67 34.53 39.12 37.34 39.63 41.27 Covertype 7.44 6.87 7.19 6.54 7.42 8.31 9.02 9.83 3.3 USPS 数据集实验结果与分析 选择两个典型谱聚类算法 SC 和 STSC 与所 提方法在广泛使用的 USPS 数据库中的手写数字 数据集进行对比实验。该数据集包含美国邮政总 局通过扫描信封中的手写数字获得的数字数据。 原始扫描的数字是二进制的，大小和方向不同。 本文使用的图像经过了大小归一化，得到了 1 616 张 256 维的灰度图像。它包含 7 291 个训练 ·902· 智 能 系 统 学 报 第 14 卷
第5期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·903· 实例和2007个测试实例（总共9298个）。为了展 100 ✉SC ▣STSC 示该方法的可伸缩性，考虑了不同数量的集群。 具体来说，数字子集{0,8}、{4,9}、{0,5,8}、{3,5,8}、 60 {1,2,3,4}、{0,2,4,6,7}和整个集合{0,1，…，9}用于测 %/IWN 试本文提出的算法。这些子集的详细信息如表4 所示。分别在每个子集上进行实验，并使用 20 CE和NMI来测量性能。 表4USPS实验数据集的特性 0,8 49 05 35,8 {0,24,6,7 {1,23,49 9 0,1 Table 4 Characteristics of the USPS experimental datasets 数据集 数据总数 类数 维数 图2USPS数据集上NMI的性能比较 Fig.2 Performance comparison of NMI on the USPS data- {0,8} 2261 256 sets {4,9} 1673 256 4 结束语 {0,5,8} 2977 3 256 {3,5,8} 2248 3 256 本文提出了一种新的无监督广义数据亲和图 {1,23.4} 3837 4 256 的构造方法，该方法具有更强的鲁棒性和更有意 {0,2,4,6,7} 4960 J 256 义的数据亲和图，以提高谱聚类精度。采用模糊 10 256 理论定义数据相似度，利用模糊隶属度函数导出 {0,1,…,9} 9298 亲和图。此外，亲和图不是盲目地相信所有可用 从图1可以看出，在CE方面，所提算法在所 变量，而是通过捕捉和通过对每个样本的模糊描 有的情况下都优于STSC和SC,尤其在{0,8}、 述，确定了特征子空间中组合分布的微妙两两相 {0,5,8}、{3,5,8}、{0,2,4,6,7}、{0,1,…,9}数据集上 似关系。同时采用共享近邻的方法发现密集区域 CE均改善了5%以上，甚至在{3,5,8}上CE相较 样本点分布的结构和密度信息，并且根据每个点 于其他对比算法，所提算法改进了10%以上。总 所处领域的稠密程度自动调节参数σ，从而生成 体而言与SC和STSC相比，可以从图1中看出所 更强大的亲和矩阵，进一步提高聚类准确率，证 提出的方法均得到明显的改善。 明了该方法对不同类型数据集的有效性。实验结 50r✉SC 果表明，该方法与其他先进的方法相比具有一定 STSC 40AFSSNNSC 的优越性。数据大小的多样性在一定程度上体现 了该方法对于大数据集的可扩展性。在未来将通 30 过系统地将所提出的算法与一些采样或量化策略 20 相结合来处理一般的可伸缩性问题。 10 参考文献： 2 0,24,6,7 .9 [1]XU Dongkuan,TIAN Yingjie.A comprehensive survey of 0,1 clustering algorithms[J].Annals of data science,2015, 2(2:165-193. 图1USPS数据集上CE的性能比较 [2]LIU Hanqiang,ZHAO Feng,JIAO Licheng.Fuzzy spec- Fig.1 Performance comparison of CE on the USPS data- tral clustering with robust spatial information for image sets segmentation[J].Applied soft computing,2012,12(11): 图2显示了基于NMI的USPS数据集的结 3636-3647. 果。从图2中可以看出，所提出的方法在所有情 [3]TUNG F,WONG A,CLAUSI D A.Enabling scalable 况下都比SC和STSC有优势。在{0,8}、 spectral clustering for image segmentation[J].Pattern re- {1,2,3,4}、{0,1,…,9}上相较于其他对比算法，所提 c0 gnition,2010,43(12:4069-4076. 算法的NM都提高了10%以上，特别是对于具有 [4]ZENG Shan,HUANG Rui,KANG Zhen,et al.Image seg- mentation using spectral clustering of Gaussian mixture 挑战性的情况{3,5,8}和多类情况{1,2,3,4}、 models[J].Neurocomputing,2014,144:346-356. {0,2,4,6,7}、{0,1,…,9},所提出的算法都具有一定 [5]JIANG J Q,DRESS A W M,YANG Genke.A spectral 的优越性。 clustering-based framework for detecting community struc-
实例和 2 007 个测试实例 (总共 9 298 个)。为了展 示该方法的可伸缩性，考虑了不同数量的集群。 具体来说，数字子集{0,8}、{4,9}、{0,5,8}、{3,5,8}、 {1,2,3,4}、{0,2,4,6,7}和整个集合{0,1,···,9}用于测 试本文提出的算法。这些子集的详细信息如表 4 所示。分别在每个子集上进行实验，并使 用 CE 和 NMI 来测量性能。 表 4 USPS 实验数据集的特性 Table 4 Characteristics of the USPS experimental datasets 数据集 数据总数 类数 维数 {0,8} 2 261 2 256 {4,9} 1 673 2 256 {0,5,8} 2 977 3 256 {3,5,8} 2 248 3 256 {1,2,3,4} 3 837 4 256 {0,2,4,6,7} 4 960 5 256 {0,1,···,9} 9 298 10 256 从图 1 可以看出，在 CE 方面，所提算法在所 有的情况下都优于 STSC 和 SC，尤其在{0,8}、 {0,5,8}、{3,5,8}、{0,2,4，6,7}、{0,1,···,9}数据集上 CE 均改善了 5% 以上，甚至在{3,5,8}上 CE 相较 于其他对比算法，所提算法改进了 10% 以上。总 体而言与 SC 和 STSC 相比，可以从图 1 中看出所 提出的方法均得到明显的改善。 CE/% 0 10 20 30 40 {0,8} {4,9} {0,5,8} {3,5,8} {1,2,3,4} {0,2,4,6,7} {0,1,···,9} 50 SC STSC AFSSNNSC 图 1 USPS 数据集上 CE 的性能比较 Fig. 1 Performance comparison of CE on the USPS datasets 图 2 显示了基于 NMI 的 USPS 数据集的结 果。从图 2 中可以看出，所提出的方法在所有情 况下都 比 S C 和 STS C 有优势。在 {0,8} 、 {1,2,3,4}、{0,1,···,9}上相较于其他对比算法，所提 算法的 NMI 都提高了 10% 以上，特别是对于具有 挑战性的情况 {3,5,8}和多类情况 {1,2,3,4}、 {0,2,4,6,7}、{0,1,···,9}，所提出的算法都具有一定 的优越性。 NMI/% 0 20 40 60 80 100 SC STSC AFSSNNSC {0,8} {4,9} {0,5,8} {3,5,8} {1,2,3,4} {0,2,4,6,7} {0,1,···,9} 图 2 USPS 数据集上 NMI 的性能比较 Fig. 2 Performance comparison of NMI on the USPS datasets 4 结束语 σ 本文提出了一种新的无监督广义数据亲和图 的构造方法，该方法具有更强的鲁棒性和更有意 义的数据亲和图，以提高谱聚类精度。采用模糊 理论定义数据相似度，利用模糊隶属度函数导出 亲和图。此外，亲和图不是盲目地相信所有可用 变量，而是通过捕捉和通过对每个样本的模糊描 述，确定了特征子空间中组合分布的微妙两两相 似关系。同时采用共享近邻的方法发现密集区域 样本点分布的结构和密度信息，并且根据每个点 所处领域的稠密程度自动调节参数 ，从而生成 更强大的亲和矩阵，进一步提高聚类准确率，证 明了该方法对不同类型数据集的有效性。实验结 果表明，该方法与其他先进的方法相比具有一定 的优越性。数据大小的多样性在一定程度上体现 了该方法对于大数据集的可扩展性。在未来将通 过系统地将所提出的算法与一些采样或量化策略 相结合来处理一般的可伸缩性问题。 参考文献： XU Dongkuan, TIAN Yingjie. A comprehensive survey of clustering algorithms[J]. Annals of data science, 2015, 2(2): 165–193. [1] LIU Hanqiang, ZHAO Feng, JIAO Licheng. Fuzzy spectral clustering with robust spatial information for image segmentation[J]. Applied soft computing, 2012, 12(11): 3636–3647. [2] TUNG F, WONG A, CLAUSI D A. Enabling scalable spectral clustering for image segmentation[J]. Pattern recognition, 2010, 43(12): 4069–4076. [3] ZENG Shan, HUANG Rui, KANG Zhen, et al. Image segmentation using spectral clustering of Gaussian mixture models[J]. Neurocomputing, 2014, 144: 346–356. [4] JIANG J Q, DRESS A W M, YANG Genke. A spectral clustering-based framework for detecting community struc- [5] 第 5 期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·903·
·904· 智能系统学报 第14卷 tures in complex networks[J].Applied mathematics letters, actions on knowledge and data engineering,2009,21(3) 2009,22(9):1479-1482. 443462 [6]FORESTIER G,WEMMERT C.Semi-supervised learn- [19]LIU Xiaodong,REN Yan.Novel artificial intelligent tech- ing using multiple clusterings with limited labeled data[J]. niques via AFS theory:feature selection,concept categor- Information sciences,2016,361-362:48-65. ization and characteristic description[J].Applied soft [7]赵晓晓，周治平.结合稀疏表示与约束传递的半监督谱 computing,2010,10(3)y:793-805. 聚类算法).智能系统学报，2018,135)：855-863. [20]LIU Xiaodong,WANG Xianchang,PEDRYCZ W.Fuzzy ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spec- clustering with semantic interpretation[J].Applied soft tral clustering algorithm combined with sparse representa- computing,.2015,26:21-30. tion and constraint propagation[J].CAAI transactions on [21]LIU Xiaodong,WANG Wei,CHAI T.The fuzzy cluster- intelligent systems,2018,13(5):855-863. ing analysis based on AFS theory[J].IEEE transactions on [8]林大华，杨利锋，邓振云，等.稀疏样本自表达子空间聚 systems,man,and cybernetics,part B,2005,35(5): 类算法).智能系统学报，2016,11（⑤）：696-702. 1013-1027. LIN Dahua,YANG Lifeng,DENG Zhenyun,et al.Sparse [22]ZELNIK-Manor L,PERONA P.Self-tuning spectral clus- sample self-representation for subspace clustering[J]. tering[Cl//Proceedings of the 17th International Confer- CAAI transactions on intelligent systems,2016,11(5): ence on Neural Information Processing Systems.Pas- 696-702. adena,USA,2004:1601-1608. [9]CHANG Yanshuo,NIE Feiping,LI Zhihui,et al.Refined [23]YAN Donghui,HUANG Ling,JORDAN M I.Fast ap- spectral clustering via embedded label propagation[]. proximate spectral clustering[C]//Proceedings of the 15th Neural computation,2017,29(12):3381-3396. ACM SIGKDD International Conference on Knowledge [10]NG A Y,JORDAN M I,WEISS Y.On spectral cluster- Discovery and Data Mining.Paris,France,2009: ing:analysis and an algorithm[C /Proceedings of the 14th 907-916. International Conference on Neural Information Pro- [24]LI Mu,KWOK J T,LU Baoliang.Making large-scale cessing Systems:Natural and Synthetic.Vancouver, nystrom approximation possible[C]//Proceedings of the Canada,2001:849-856. 27th International Conference on International Confer- [11]YE Xiucai,SAKURAI T.Robust similarity measure for ence on Machine Learning.Haifa,Israel,2010:631-638. spectral clustering based on shared neighbors[J].ETRI [25]CAI Deng,CHEN Xinlei.Large scale spectral clustering journal,2016,38(3):540-550. via landmark-based sparse representation[J].IEEE trans- [12]JIA Hongjie,DING Shifei,DU Mingjing.Self-tuning p- actions on cybernetics,2015,45(8):1669-1680. spectral clustering based on shared nearest neighbors[J. [26]SCHOLKOPF B,PLATT J,HOFMANN T.A local learn- Cognitive computation,2015,7(5):622-632. ing approach for clustering[C]//Proceedings of the 19th [13]王雅琳，陈斌，王晓丽，等.基于密度调整的改进自适应 International Conference on Neural Information Pro- 谱聚类算法[.控制与决策，2014,29(9片1683-1687. cessing Systems.Doha,Qatar,2007:1529-1536. WANG Yalin,CHEN Bin,WANG Xiaoli,et al.Im- [27]STREHL A,GHOSH J.Cluster ensembles:a knowledge proved adaptive spectral clustering algorithm based on reuse framework for combining partitionings[C]//Pro- density adjustment[J].Control and decision,2014,29(9): ceedings of the 18th National Conference on Artificial In- 1683-1687. telligence.Alberta,Canada,2003:583-617. [14]SHI Jianbo,MALIK J.Normalized cuts and image seg- mentation[J].IEEE transactions on pattern analysis and 作者简介： machine intelligence,2000,22(8):888-905. 储德润，男.1994年生，硕士研究 [15]LIU Xiaodong.The fuzzy theory based on AFS algebras 生，主要研究方向为数据挖掘。 and AFS structure[J].Journal of mathematical analysis and applications,1998,217(2):459-478. [16]LIU Xiaodong,PEDRYCZ W,ZHANG Qingling.Axio- matics fuzzy sets logic[Cl//Proceedings of the12th IEEE International Conference on Fuzzy Systems.St Louis, USA.2003:55-60. 周治平，男，1962年生，教授，博 [17]LIU Xiaodong,PEDRYCZ W.Axiomatic fuzzy set the- 士，主要研究方向为智能检测、网络安 ory and its applications[M].Berlin,Heidelberg:Springer, 全。发表学术论文20余篇。 2009. [18]LIU Xiaodong,PEDRYCZ W,CHAI Tianyou,et al.The development of fuzzy rough sets with the use of struc- tures and algebras of axiomatic fuzzy sets[J].IEEE trans-
tures in complex networks[J]. Applied mathematics letters, 2009, 22(9): 1479–1482. FORESTIER G, WEMMERT C. Semi-supervised learning using multiple clusterings with limited labeled data[J]. Information sciences, 2016, 361−362: 48–65. [6] 赵晓晓, 周治平. 结合稀疏表示与约束传递的半监督谱 聚类算法 [J]. 智能系统学报, 2018, 13(5): 855–863. ZHAO Xiaoxiao, ZHOU Zhiping. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J]. CAAI transactions on intelligent systems, 2018, 13(5): 855–863. [7] 林大华, 杨利锋, 邓振云, 等. 稀疏样本自表达子空间聚 类算法 [J]. 智能系统学报, 2016, 11(5): 696–702. LIN Dahua, YANG Lifeng, DENG Zhenyun, et al. Sparse sample self-representation for subspace clustering[J]. CAAI transactions on intelligent systems, 2016, 11(5): 696–702. [8] CHANG Yanshuo, NIE Feiping, LI Zhihui, et al. Refined spectral clustering via embedded label propagation[J]. Neural computation, 2017, 29(12): 3381–3396. [9] NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Vancouver, Canada, 2001: 849−856. [10] YE Xiucai, SAKURAI T. Robust similarity measure for spectral clustering based on shared neighbors[J]. ETRI journal, 2016, 38(3): 540–550. [11] JIA Hongjie, DING Shifei, DU Mingjing. Self-tuning p - spectral clustering based on shared nearest neighbors[J]. Cognitive computation, 2015, 7(5): 622–632. [12] 王雅琳, 陈斌, 王晓丽, 等. 基于密度调整的改进自适应 谱聚类算法 [J]. 控制与决策, 2014, 29(9): 1683–1687. WANG Yalin, CHEN Bin, WANG Xiaoli, et al. Improved adaptive spectral clustering algorithm based on density adjustment[J]. Control and decision, 2014, 29(9): 1683–1687. [13] SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE transactions on pattern analysis and machine intelligence, 2000, 22(8): 888–905. [14] LIU Xiaodong. The fuzzy theory based on AFS algebras and AFS structure[J]. Journal of mathematical analysis and applications, 1998, 217(2): 459–478. [15] LIU Xiaodong, PEDRYCZ W, ZHANG Qingling. Axiomatics fuzzy sets logic[C]//Proceedings of the12th IEEE International Conference on Fuzzy Systems. St Louis, USA, 2003: 55-60. [16] LIU Xiaodong, PEDRYCZ W. Axiomatic fuzzy set theory and its applications[M]. Berlin, Heidelberg: Springer, 2009. [17] LIU Xiaodong, PEDRYCZ W, CHAI Tianyou, et al. The development of fuzzy rough sets with the use of structures and algebras of axiomatic fuzzy sets[J]. IEEE trans- [18] actions on knowledge and data engineering, 2009, 21(3): 443–462. LIU Xiaodong, REN Yan. Novel artificial intelligent techniques via AFS theory: feature selection, concept categorization and characteristic description[J]. Applied soft computing, 2010, 10(3): 793–805. [19] LIU Xiaodong, WANG Xianchang, PEDRYCZ W. Fuzzy clustering with semantic interpretation[J]. Applied soft computing, 2015, 26: 21–30. [20] LIU Xiaodong, WANG Wei, CHAI T. The fuzzy clustering analysis based on AFS theory[J]. IEEE transactions on systems, man, and cybernetics, part B, 2005, 35(5): 1013–1027. [21] ZELNIK-Manor L, PERONA P. Self-tuning spectral clustering[C]//Proceedings of the 17th International Conference on Neural Information Processing Systems. Pasadena, USA, 2004: 1601−1608. [22] YAN Donghui, HUANG Ling, JORDAN M I. Fast approximate spectral clustering[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 907−916. [23] LI Mu, KWOK J T, LU Baoliang. Making large-scale nyström approximation possible[C]//Proceedings of the 27th International Conference on International Conference on Machine Learning. Haifa, Israel, 2010: 631−638. [24] CAI Deng, CHEN Xinlei. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE transactions on cybernetics, 2015, 45(8): 1669–1680. [25] SCHÖLKOPF B, PLATT J, HOFMANN T. A local learning approach for clustering[C]//Proceedings of the 19th International Conference on Neural Information Processing Systems. Doha, Qatar, 2007: 1529−1536. [26] STREHL A, GHOSH J. Cluster ensembles: a knowledge reuse framework for combining partitionings[C]//Proceedings of the 18th National Conference on Artificial Intelligence. Alberta, Canada, 2003: 583–617. [27] 作者简介： 储德润，男，1994 年生，硕士研究 生，主要研究方向为数据挖掘。 周治平，男，1962 年生，教授，博 士，主要研究方向为智能检测、网络安 全。发表学术论文 20 余篇。 ·904· 智 能 系 统 学 报 第 14 卷