第11卷第5期 智能系统学报 Vol.11 No.5 2016年10月 CAAI Transactions on Intelligent Systems 0ct.2016 D0I:10.11992/is.201508022 网络出版地址：htp:/ww.cnki.net/kcms/detail/23.1538.TP.20160824.0928.004.html 基于局部保留投影的多可选聚类发掘算法 程肠，王士同 (江南大学数字蝶体学院，江苏无锡214122) 摘要：绝大多数的聚类分析算法仅能得到单一的聚类结果，考虑到数据的复杂程度普遍较高，以及看待数据的视 角不同，所得到的聚类结果在保证其合理性的基础上应当是不唯一的，针对此问题，提出了一个新的算法RLPP,用 于发掘多种可供选择的聚类结果。RLPP的目标函数兼顾了聚类质量和相异性两大要素，采用子空间流形学习技 术，通过新的子空间不断生成多种互不相同的聚类结果。LPP同时适用于线性以及非线性的数据集。实验表明， RLPP成功地发掘了多种可供选择的聚类结果，其性能相当或优于现有的算法。 关键词：可供选择的聚类结果：无监督学习；流形学习：多聚类；特征分解 中图分类号：TP18文献标志码：A文章编号：1673-4785(2016)05-0600-08 中文引用格式：程肠，王士同.基于局部保留投影的多可选聚类发掘算法[J].智能系统学报，2016,11(5)：600-607. 英文引用格式：CHENG Yang,WANG Shitong.A multiple alternative clusterings mining algorithm using locality preserving projec tions[].CAAI transactions on intelligent systems,2016,11(5):600-607. A multiple alternative clusterings mining algorithm using locality preserving projections CHENG Yang,WANG Shitong (School of Digit Media,Jiangnan University,Wuxi 214122.China) Abstract:Most clustering algorithms typically find just one single result for the data inputted.Considering that the complexity of the data is generally high,combined with the need to allow the data to be viewed from different per- spectives (on the basis of ensuring reasonableness),means that clustering results are often not unique.We present a new algorithm RLPP for an alternative clustering generation method.The objective of RLPP is to find a balance between clustering quality and dissimilarity using a subspace manifold learning technique in a new subspace so that a variety of clustering results can be generated.Experimental results using both linear and nonlinear datasets show that RLPP successfully provides a variety of alternative clustering results,and is able to outperform or at least match a range of existing methods. Keywords:alternative clustering;unsupervised learning;manifold learning;multiple clusterings;eigendecomposi- tion 大多数传统的聚类算法仅仅能得到单个结果， 本文根据文献[1]所述原理，提出了一种能够发 但是当对复杂数据进行聚类分析时，很可能存在多掘多个可供选择的聚类结果的算法RLPP。算法结 个具有合理性的聚类结果。这一特点在高维数据上合了希尔伯特施密特独立性度量准则(hilbert- 表现得尤为明显，例如文本、图像、基因数据等，这些 schmidt independence criterion,HsIC)]以及局部保 数据具有多种特征，而不同的特征子空间往往会得 持投影(locality preserving projections,LPP)[),改进 到完全不同的聚类结果，同时每一种结果都能体现 了LPP算法学习子空间的过程。由于HSIC可以高 数据不同的结构信息。 效地评估不同随机变量之间的依赖性，而LPP算法 具有流形学习能力，因此RLPP同时兼顾了聚类结 收稿日期：2015-08-26.网络出版日期：2016-08-24 果的相异性和聚类质量这两大要素。并且由于其目 基金项目：国家自然科学基金项目(61272210). 通信作者：程肠.E-mail:szhchengyang(@163.com 标函数最终在特征分解问题的框架内求解，因此能
第 １１ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．５ ２０１６ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０８０２２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８２４．０９２８．００４．ｈｔｍｌ 基于局部保留投影的多可选聚类发掘算法 程旸，王士同 （江南大学 数字媒体学院，江苏 无锡 ２１４１２２） 摘 要：绝大多数的聚类分析算法仅能得到单一的聚类结果，考虑到数据的复杂程度普遍较高，以及看待数据的视 角不同，所得到的聚类结果在保证其合理性的基础上应当是不唯一的，针对此问题，提出了一个新的算法 ＲＬＰＰ，用 于发掘多种可供选择的聚类结果。 ＲＬＰＰ 的目标函数兼顾了聚类质量和相异性两大要素，采用子空间流形学习技 术，通过新的子空间不断生成多种互不相同的聚类结果。 ＲＬＰＰ 同时适用于线性以及非线性的数据集。 实验表明， ＲＬＰＰ 成功地发掘了多种可供选择的聚类结果，其性能相当或优于现有的算法。 关键词：可供选择的聚类结果；无监督学习；流形学习；多聚类；特征分解 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０５⁃０６００⁃０８ 中文引用格式：程旸，王士同．基于局部保留投影的多可选聚类发掘算法［Ｊ］． 智能系统学报， ２０１６， １１（５）： ６００⁃６０７． 英文引用格式：ＣＨＥＮＧ Ｙａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ａ ｍｕｌｔｉｐｌｅ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃ⁃ ｔｉｏｎｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（５）： ６００⁃６０７． Ａ ｍｕｌｔｉｐｌｅ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ ＣＨＥＮＧ Ｙａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｍｏｓｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｙｐｉｃａｌｌｙ ｆｉｎｄ ｊｕｓｔ ｏｎｅ ｓｉｎｇｌｅ ｒｅｓｕｌｔ ｆｏｒ ｔｈｅ ｄａｔａ ｉｎｐｕｔｔｅｄ． Ｃｏｎｓｉｄｅｒｉｎｇ ｔｈａｔ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｄａｔａ ｉｓ ｇｅｎｅｒａｌｌｙ ｈｉｇｈ， ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｎｅｅｄ ｔｏ ａｌｌｏｗ ｔｈｅ ｄａｔａ ｔｏ ｂｅ ｖｉｅｗｅｄ ｆｒｏｍ ｄｉｆｆｅｒｅｎｔ ｐｅｒ⁃ ｓｐｅｃｔｉｖｅｓ （ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｅｎｓｕｒｉｎｇ ｒｅａｓｏｎａｂｌｅｎｅｓｓ）， ｍｅａｎｓ ｔｈａｔ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ａｒｅ ｏｆｔｅｎ ｎｏｔ ｕｎｉｑｕｅ． Ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ＲＬＰＰ ｆｏｒ ａｎ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ｇｅｎｅｒａｔｉｏｎ ｍｅｔｈｏｄ． Ｔｈｅ ｏｂｊｅｃｔｉｖｅ ｏｆ ＲＬＰＰ ｉｓ ｔｏ ｆｉｎｄ ａ ｂａｌａｎｃｅ ｂｅｔｗｅｅｎ ｃｌｕｓｔｅｒｉｎｇ ｑｕａｌｉｔｙ ａｎｄ ｄｉｓｓｉｍｉｌａｒｉｔｙ ｕｓｉｎｇ ａ ｓｕｂｓｐａｃｅ ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ ｔｅｃｈｎｉｑｕｅ ｉｎ ａ ｎｅｗ ｓｕｂｓｐａｃｅ ｓｏ ｔｈａｔ ａ ｖａｒｉｅｔｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｃａｎ ｂｅ ｇｅｎｅｒａｔｅｄ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｕｓｉｎｇ ｂｏｔｈ ｌｉｎｅａｒ ａｎｄ ｎｏｎｌｉｎｅａｒ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈａｔ ＲＬＰＰ ｓｕｃｃｅｓｓｆｕｌｌｙ ｐｒｏｖｉｄｅｓ ａ ｖａｒｉｅｔｙ ｏｆ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ， ａｎｄ ｉｓ ａｂｌｅ ｔｏ ｏｕｔｐｅｒｆｏｒｍ ｏｒ ａｔ ｌｅａｓｔ ｍａｔｃｈ ａ ｒａｎｇｅ ｏｆ ｅｘｉｓｔｉｎｇ ｍｅｔｈｏｄｓ． Ｋｅｙｗｏｒｄｓ：ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ； ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ； ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ； ｍｕｌｔｉｐｌｅ ｃｌｕｓｔｅｒｉｎｇｓ； ｅｉｇｅｎｄｅｃｏｍｐｏｓｉ⁃ ｔｉｏｎ 收稿日期：２０１５⁃０８⁃２６． 网络出版日期：２０１６⁃０８⁃２４． 基金项目：国家自然科学基金项目（６１２７２２１０）． 通信作者：程旸． Ｅ⁃ｍａｉｌ：ｓｚｈｃｈｅｎｇｙａｎｇ＠ １６３．ｃｏｍ． 大多数传统的聚类算法仅仅能得到单个结果， 但是当对复杂数据进行聚类分析时，很可能存在多 个具有合理性的聚类结果。 这一特点在高维数据上 表现得尤为明显，例如文本、图像、基因数据等，这些 数据具有多种特征，而不同的特征子空间往往会得 到完全不同的聚类结果，同时每一种结果都能体现 数据不同的结构信息。 本文根据文献［１］所述原理，提出了一种能够发 掘多个可供选择的聚类结果的算法 ＲＬＰＰ。 算法结 合了 希 尔 伯 特 施 密 特 独 立 性 度 量 准 则 （ ｈｉｌｂｅｒｔ⁃ ｓｃｈｍｉｄｔ ｉｎｄｅｐｅｎｄｅｎｃｅ ｃｒｉｔｅｒｉｏｎ，ＨＳＩＣ） ［２］ 以及局部保 持投影（ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ，ＬＰＰ） ［３］ ，改进 了 ＬＰＰ 算法学习子空间的过程。 由于 ＨＳＩＣ 可以高 效地评估不同随机变量之间的依赖性，而 ＬＰＰ 算法 具有流形学习能力，因此 ＲＬＰＰ 同时兼顾了聚类结 果的相异性和聚类质量这两大要素。 并且由于其目 标函数最终在特征分解问题的框架内求解，因此能
第5期 程肠，等：基于局部保留投影的多可选聚类发掘算法 ·601· 够确保求出的新的子空间一定存在，并且解是全局 列空间中，可以用P×b计算，其中P被称为投影矩 最优的。 阵，P=A(ATA)AT。而(I-P)同样也是一个投 总的来说，本文所做的工作为：1)提出了一种新的 影矩阵，表示把投影到了AT的零空间中。文献[14] 算法RLPP,用于发掘多种可供选择的聚类结果：2) 中提出的2种算法把每个数据实例看作向量，利用 LPP根据同时满足质量和相异性要求的目标函数，生 了上述投影等式。文献[15]中的研究也与此相关， 成一个新的特征子空间，该特征子空间能够确保存在， 投影矩阵被应用于从所提供的聚类结果导出的距离 并且是全局最优的：3)通过实验，验证了RLPP的效 矩阵上。相比于文献[14]中的2种算法，这种方法 果，并与其他现有的算法进行了性能比较。 的优势在于能够解决数据维数比类别数小的情况。 1当前典型的可选聚类发掘方法 文献[16]提出的算法采用了不同的方法，通过对数 据的投影，使得在参考聚类结果中属于相同类别的 当前，有关发掘可选聚类结果的算法大体上可 数据点经过映射后在新的空间中拉开距离。这一方 以分为两类：一类直接利用原始数据空间寻找，另一 法与其他方法之间的不同之处在于它并不寻找一个 类则是基于投影（变形）子空间寻找。 全新的可选聚类，而是通过设定2个聚类结果之间 1.1基于全部原始数据空间 的相异度阈值，允许已知的聚类结果中的部分在可 这类研究利用的是整个原始特征空间，大多数 选聚类结果中保留下来。文献[17]和文献[18]中 研究的不同之处在于优化聚类质量和相异性的目标 所提出的算法基于谱聚类实现，前者表明可选聚类 函数不同。文献[4-9]中的研究可以归类为此类。 结果可以通过拉普拉斯矩阵不同的特征向量找到， 文献[4]提出了一种分层聚类(hierarchical cluste- 后者所提出的多重谱聚类(multiple spectral cluste- ring)算法COALA,该算法把从提供的聚类结果中生 ring,MSC)把子空间学习技术融入了谱聚类的过程 成的cannot--link约束项合并入它的每一个凝聚步骤 中，也就是说，MSC的目标函数是一个对偶函数 中，即尽可能多地满足这些cannot--ink约束项。在 (dual-function),通过最优化一项来修正另一项。另 文献[7]中，提出了CAMI算法，用于同时寻找两个 外，文献[I]提出了正则化PCA(regularized PCA, 可供选择的聚类结果。CAMI算法在混合模型下构 RPCA)和正则化的图方法(regularized graph-based 造聚类问题，优化了一个双重目标函数(dual-objec- method,RegGB)算法，其中RPCA与MSC一样，都 tive function),使得当两个混合模型之间的互信息 采用了HSIC,用于评估相关性，而RegGB算法则是 (反映了两种聚类结果之间的不同)最小时，对数似 基于图论构造。总的来说，RPCA和RegGB算法在 然（反映了聚类质量）最大。文献[6]提出的两种算 寻找可选聚类的能力上要优于之前所提到的算法， 法Dec-kmeans和Conv-EM也属于此类，这两种算法 但是RPCA算法只适用于线性结构的数据集，并且 分别改进了k-means和EM的目标函数，结合了一 其寻找可选聚类结果的能力有限，往往只能找到 个修正项，用于表示两种聚类结果之间的去相关信 个可选聚类，这些都极大地影响了它在使用上的灵 息。文献[8]中的工作采用了不同的方式，其原理 活性。因此，本文在文献[1]所提出的思路上，探索 来源于信息论，它的目标函数最大化全部数据实例 了一种新的算法，通过引入流形学习大大提高了其 和可选聚类结果类标之间的互信息(M),同时最小 发掘低维流形结构的能力和子空间学习能力，并通 化可选聚类和所提供的聚类结果之间的互信息。文 过核化扩大了其适用范围，使得其既适用于线性，同 献[8]中并没有基于传统的香农嫡，而是采用了 时又适用于非线性的数据集。 Renyi熵，以及相对应的二次互信息[2]，这种方法 在结合了非参数Parzen窗[]后使得MI基本近似。 2问题描述 这种双重优化聚类目标同样被用于文献[9]中，区 别在于文献「91使用的是迭代法，而不是文献「81中 假设数据集X={x1x2…xn},x:eR,即X是 所使用的分层技术。 dxn的矩阵，并提供一个使用任意聚类算法得到的 1.2基于投影子空间 参考聚类结果C)。则本文研究的目标为：发掘数 如果原数据空间的子空间与原数据空间是相互 据集X上的可供选择的聚类结果C2),并且C2)中 独立的（比如是正交的），那么根据该子空间得到的 的所有类别C2必须满足两个条件，U,C2=X和 聚类结果也与原聚类结果不同。文献[14-18]就是 C2nC2=0(i≠j)。除了与C)不同外，还要求 根据这样的理论基础提出了各自的算法。文献 C(2)的聚类质量较高。同理，若提供一组参考聚类 「14]由正交投影方法提出了两种寻找可供选择的 结果{C),C,…{,必须生成高质量的可供选择 聚类结果的算法。已知一个向量b,投影到矩阵的 的聚类结果C),且与之前所有的聚类结果{C)
够确保求出的新的子空间一定存在，并且解是全局 最优的。 总的来说，本文所做的工作为：１）提出了一种新的 算法 ＲＬＰＰ，用于发掘多种可供选择的聚类结果；２） ＲＬＰＰ 根据同时满足质量和相异性要求的目标函数，生 成一个新的特征子空间，该特征子空间能够确保存在， 并且是全局最优的；３）通过实验，验证了 ＲＬＰＰ 的效 果，并与其他现有的算法进行了性能比较。 １ 当前典型的可选聚类发掘方法 当前，有关发掘可选聚类结果的算法大体上可 以分为两类：一类直接利用原始数据空间寻找，另一 类则是基于投影（变形）子空间寻找。 １．１ 基于全部原始数据空间 这类研究利用的是整个原始特征空间，大多数 研究的不同之处在于优化聚类质量和相异性的目标 函数不同。 文献［４⁃９］ 中的研究可以归类为此类。 文献［４］ 提出了一种分层聚类（ ｈｉｅｒａｒｃｈｉｃａｌ ｃｌｕｓｔｅ⁃ ｒｉｎｇ）算法 ＣＯＡＬＡ，该算法把从提供的聚类结果中生 成的 ｃａｎｎｏｔ⁃ｌｉｎｋ 约束项合并入它的每一个凝聚步骤 中，即尽可能多地满足这些 ｃａｎｎｏｔ⁃ｌｉｎｋ 约束项。 在 文献［７］中，提出了 ＣＡＭＩ 算法，用于同时寻找两个 可供选择的聚类结果。 ＣＡＭＩ 算法在混合模型下构 造聚类问题，优化了一个双重目标函数（ ｄｕａｌ⁃ｏｂｊｅｃ⁃ ｔｉｖｅ ｆｕｎｃｔｉｏｎ），使得当两个混合模型之间的互信息 （反映了两种聚类结果之间的不同）最小时，对数似 然（反映了聚类质量）最大。 文献［６］提出的两种算 法 Ｄｅｃ⁃ｋｍｅａｎｓ 和 Ｃｏｎｖ⁃ＥＭ 也属于此类，这两种算法 分别改进了 ｋ⁃ｍｅａｎｓ 和 ＥＭ 的目标函数，结合了一 个修正项，用于表示两种聚类结果之间的去相关信 息。 文献［８］中的工作采用了不同的方式，其原理 来源于信息论，它的目标函数最大化全部数据实例 和可选聚类结果类标之间的互信息（ＭＩ），同时最小 化可选聚类和所提供的聚类结果之间的互信息。 文 献［８］中并没有基于传统的香农熵［１０］ ，而是采用了 Ｒｅｎｙｉ 熵，以及相对应的二次互信息［１１⁃１２］ ，这种方法 在结合了非参数 Ｐａｒｚｅｎ 窗［１３］ 后使得 ＭＩ 基本近似。 这种双重优化聚类目标同样被用于文献［９］ 中，区 别在于文献［９］使用的是迭代法，而不是文献［８］中 所使用的分层技术。 １．２ 基于投影子空间 如果原数据空间的子空间与原数据空间是相互 独立的（比如是正交的），那么根据该子空间得到的 聚类结果也与原聚类结果不同。 文献［１４⁃１８］就是 根据这样的理论基础提出了各自的算法。 文献 ［１４］由正交投影方法提出了两种寻找可供选择的 聚类结果的算法。 已知一个向量 ｂ，投影到矩阵的 列空间中，可以用 Ｐ×ｂ 计算，其中 Ｐ 被称为投影矩 阵，Ｐ ＝ Ａ（Ａ ＴＡ ） －１Ａ Ｔ 。 而（Ⅰ－Ｐ） 同样也是一个投 影矩阵，表示把投影到了Ａ Ｔ 的零空间中。 文献［１４］ 中提出的 ２ 种算法把每个数据实例看作向量，利用 了上述投影等式。 文献［１５］中的研究也与此相关， 投影矩阵被应用于从所提供的聚类结果导出的距离 矩阵上。 相比于文献［１４］中的 ２ 种算法，这种方法 的优势在于能够解决数据维数比类别数小的情况。 文献［１６］提出的算法采用了不同的方法，通过对数 据的投影，使得在参考聚类结果中属于相同类别的 数据点经过映射后在新的空间中拉开距离。 这一方 法与其他方法之间的不同之处在于它并不寻找一个 全新的可选聚类，而是通过设定 ２ 个聚类结果之间 的相异度阈值，允许已知的聚类结果中的部分在可 选聚类结果中保留下来。 文献［１７］和文献［１８］中 所提出的算法基于谱聚类实现，前者表明可选聚类 结果可以通过拉普拉斯矩阵不同的特征向量找到， 后者所提出的多重谱聚类（ ｍｕｌｔｉｐｌｅ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅ⁃ ｒｉｎｇ， ＭＳＣ）把子空间学习技术融入了谱聚类的过程 中，也就是说， ＭＳＣ 的目标函数是一个对偶函数 （ｄｕａｌ⁃ｆｕｎｃｔｉｏｎ），通过最优化一项来修正另一项。 另 外，文献［ １］ 提出了正则化 ＰＣＡ（ ｒｅｇｕｌａｒｉｚｅｄ ＰＣＡ， ＲＰＣＡ）和正则化的图方法（ ｒｅｇｕｌａｒｉｚｅｄ ｇｒａｐｈ⁃ｂａｓｅｄ ｍｅｔｈｏｄ， ＲｅｇＧＢ）算法，其中 ＲＰＣＡ 与 ＭＳＣ 一样，都 采用了 ＨＳＩＣ，用于评估相关性，而 ＲｅｇＧＢ 算法则是 基于图论构造。 总的来说，ＲＰＣＡ 和 ＲｅｇＧＢ 算法在 寻找可选聚类的能力上要优于之前所提到的算法， 但是 ＲＰＣＡ 算法只适用于线性结构的数据集，并且 其寻找可选聚类结果的能力有限，往往只能找到一 个可选聚类，这些都极大地影响了它在使用上的灵 活性。 因此，本文在文献［１］所提出的思路上，探索 了一种新的算法，通过引入流形学习大大提高了其 发掘低维流形结构的能力和子空间学习能力，并通 过核化扩大了其适用范围，使得其既适用于线性，同 时又适用于非线性的数据集。 ２ 问题描述 假设数据集 Ｘ ＝ ｛ ｘ１ ｘ２… ｘｎ ｝，ｘｉ∈Ｒ ｄ ，即 Ｘ 是 ｄ×ｎ的矩阵，并提供一个使用任意聚类算法得到的 参考聚类结果 Ｃ （１） 。 则本文研究的目标为：发掘数 据集 Ｘ 上的可供选择的聚类结果 Ｃ （２） ，并且 Ｃ （２） 中 的所有类别 Ｃ （２） ｉ 必须满足两个条件，ＵｉＣ （２） ｉ ＝ Ｘ 和 Ｃ （２） ｉ ∩Ｃ （２） ｊ ＝Ø（∀ｉ≠ｊ）。 除了与 Ｃ （１）不同外，还要求 Ｃ （２）的聚类质量较高。 同理，若提供一组参考聚类 结果｛Ｃ （１） ，Ｃ （２） ，…｝，必须生成高质量的可供选择 的聚类结果 Ｃ （ｋ） ，且与之前所有的聚类结果｛Ｃ （１） ， 第 ５ 期 程旸，等：基于局部保留投影的多可选聚类发掘算法 ·６０１·
·602· 智能系统学报 第11卷 C2),…}不同。 假设欧式空间R”中的数据矩阵通过非线性映 为了发掘另一个可供选择的聚类结果，使用子 射函数p映射到希尔伯特空间K,即p:R→K。使 空间流形学习方法，将原始数据空间X映射到一个 用(X)表示希尔伯特空间中的数据矩阵，即 新的子空间中。该空间保留了X的特征，并且完全 p(X)=[e(x,)p(x2)…p(xn)]。那么，在希尔伯 独立于其他的参考聚类结果。任何聚类算法都可以 特空间中的特征向量问题就可以表示为 使用这个新的子空间进行聚类分析。 [(X)Le(X)']v=A[e(X)De(X)]v (5) 考虑如下的核函数： 3局部保持投影 K(x:,x)=(p(x:)·p(x))=p(x)p(x) 局部保持投影(locality preserving projections, 式(5)中的特征向量是p(x,),p(x2),, LPP)[)是一种非监督降维方法，是流形学习算法 p(x)的线性组合，每一项的系数分别为a, Laplacian Eigenmap的线性逼近。给定R中的n个 i=1,2,…,m,即y= 数据点x1,x2,…,xn,LPP通过寻找转换矩阵A,将 ae(x)=g(X)a。其中， i=1 这n个数据点映射为R(ld)上的数据点y,y2, a=[a,a2…an]T。经过简单的代数变换，可以得 …Jyn,即 到如下特征向量问题：KLKa=AKDKa。. y:=Ax,i=1,2,…,n (1) 4希尔伯特-施密特独立性度量准则 式中所需的转换矩阵A可以通过最小化式(2)目标 函数得到： 已知一个参考聚类结果C”,使用RLPP算法学 A=argmin∑(y:-y,)2wg (2) 习相对于C)独立的子空间A,这样就确保了使用 A得到的聚类结果C)与C)不同。为了计算不同 式中：W是权值矩阵，可采用k最近邻算法得到邻 子空间之间的相异性，采用了HSIC(hilbert-schmidt 接图，再求出权值矩阵。 independence criterion)),更重要的是，LPP与HSIC 如果x:是x:的k近邻点，则W=exp- 1x-x2 结合后可以导出一个特征分解问题，这样就一定可 以计算出全局最佳解。 (t∈R):否则W,=0。显然，W是一个n×n的稀疏对 HSIC是一种基于核的独立性度量方法，采用 称矩阵。 Hilbert--Schmidt互协方差算子，通过对该算子范数 从目标函数式(2)可以看出，降维后的特征空间 的经验估计得到独立性判断准则。具体来说，已知 可以保持原始高维空间的局部结构。结合式(1)和 X和Y两个随机变量，HSIC(x,n的值越大说明X和 式(2)，做简单的代数变换： Y的关联性越强，值等于0时说明X和Y相互之间 Σ)， 完全独立。 数学上，令F表示再生核希尔伯特空间，P(x) Σ(4x-Ax护W,= 表示数据x从原空间映射到F中的映射函数，则核 函数可以写为K(x,x)=〈p(x),(x)）。同样的， ∑Ax,DaxA-∑Ax,W,xA= 定义山(y)为原空间中的数据y映射到再生希尔伯 (3) 特空间G的映射函数，核函数可以写为L(y,y)= AX(D-W)XA =ATXLXA 〈(y),(y)》。则互协方差算子C,:G→F可以 式中：X=[x1x2…xn],D是一个n的对角矩阵，对角 被定义为C,=E,[((x)-u)⑧((y)-μ，)]，⑧ 线元素D=∑W,L是拉普拉斯矩阵，L=D-W。 表示张量积。C,即为Hilbert-Schmidt算子，而HSIC 能够使得式(3)取最小值的变换矩阵A的求解 定义为C,的Hilbert--Schmidt算子范数，即 可以转换为如下的广义特征值问题： HSIC(eF.=IC,I,其中P表示X和Y的联合 XLXA =AXDXA (4) 分布。实际上，不需要知道联合分布P,已知n个 将式(4)求解出的特征值按从小到大排列，即 观测值Z={(x1y1),…,(xyn)},可以直接给出 入。<…<入-1，取前k个最小的特征值对应的特征向 HSIC的经验估计值为HSICr.=(n-l)-r(L,H)。 量a0,a1,…,ak-1组成A,即A=[aoa1…ak-1】,由于 其中K,L,∈R,且K,L,分别是核K和L关于Z观 a:是列向量，所以A是d×k的矩阵。 测值的Gam矩阵，即K,=k(x:,x),L,g=(y:,》)= 此外，LPP不仅适用于原始数据空间，还适用于 《心：y〉，其中y:是一个二元向量，表示对x,的类标 再生核希尔伯特空间(reproducing kernel hilbert space,RKHS),这样就可以引出核LPP算法。 签所做的编码（稍后将举例说明)。H=1-e,c,e
Ｃ （２） ，…｝不同。 为了发掘另一个可供选择的聚类结果，使用子 空间流形学习方法，将原始数据空间 Ｘ 映射到一个 新的子空间中。 该空间保留了 Ｘ 的特征，并且完全 独立于其他的参考聚类结果。 任何聚类算法都可以 使用这个新的子空间进行聚类分析。 ３ 局部保持投影 局部 保 持 投 影 （ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ， ＬＰＰ） ［３］是一种非监督降维方法，是流形学习算法 Ｌａｐｌａｃｉａｎ Ｅｉｇｅｎｍａｐ 的线性逼近。 给定 Ｒ ｄ 中的 ｎ 个 数据点 ｘ１ ，ｘ２ ，…，ｘｎ ，ＬＰＰ 通过寻找转换矩阵 Ａ，将 这 ｎ 个数据点映射为Ｒ ｌ （ｌ≪ｄ） 上的数据点 ｙ１ ，ｙ２ ， …，ｙｎ ，即： ｙｉ ＝ Ａ Ｔ ｘｉ，ｉ ＝ １，２，…，ｎ （１） 式中所需的转换矩阵 Ａ 可以通过最小化式（２）目标 函数得到： Ａ ＝ ａｒｇｍｉｎ∑ｉｊ （ｙｉ － ｙｊ） ２Ｗｉｊ （２） 式中：Ｗｉｊ是权值矩阵，可采用 ｋ 最近邻算法得到邻 接图，再求出权值矩阵。 如果 ｘｊ 是 ｘｉ 的 ｋ 近邻点，则 Ｗｉｊ ＝ｅｘｐ－ ‖ｘｉ －ｘｊ‖２ ｔ （ｔ∈Ｒ）；否则 Ｗｉｊ ＝ ０。 显然，Ｗ 是一个ｎ×ｎ的稀疏对 称矩阵。 从目标函数式（２）可以看出，降维后的特征空间 可以保持原始高维空间的局部结构。 结合式（１）和 式（２），做简单的代数变换： １ ２ ∑ｉｊ （ｙｉ － ｙｊ） ２ Ｗｉｊ ＝ １ ２ ∑ｉｊ （Ａ Ｔ ｘｉ － Ａ Ｔ ｘｊ） ２ Ｗｉｊ ＝ ∑ｉ Ａ Ｔ ｘｉ Ｄｉｉ ｘ Ｔ ｉ Ａ － ∑ｉｊ Ａ Ｔ ｘｉ Ｗｉｊ ｘ Ｔ ｊ Ａ ＝ Ａ ＴＸ(Ｄ － Ｗ) Ｘ ＴＡ ＝ Ａ ＴＸＬ Ｘ ＴＡ （３） 式中：Ｘ＝ ｘ１ ｘ２… ｘｎ [ ] ，Ｄ 是一个 ｎ×ｎ 的对角矩阵，对角 线元素 Ｄｉｉ ＝ ∑ ｊ Ｗｉｊ，Ｌ 是拉普拉斯矩阵，Ｌ ＝ Ｄ － Ｗ。 能够使得式（３）取最小值的变换矩阵 Ａ 的求解 可以转换为如下的广义特征值问题： ＸＬＸ ＴＡ ＝ λＸＤＸ ＴＡ （４） 将式（４）求解出的特征值按从小到大排列，即 λ０＜…＜λｌ－１ ，取前 ｋ 个最小的特征值对应的特征向 量 ａ０ ，ａ１ ，…，ａｋ－１组成 Ａ，即 Ａ ＝ ａ０ ａ１… ａｋ－１ [ ] ，由于 ａｉ 是列向量，所以 Ａ 是 ｄ×ｋ 的矩阵。 此外，ＬＰＰ 不仅适用于原始数据空间，还适用于 再生 核 希 尔 伯 特 空 间 （ ｒｅｐｒｏｄｕｃｉｎｇ ｋｅｒｎｅｌ ｈｉｌｂｅｒｔ ｓｐａｃｅ， ＲＫＨＳ），这样就可以引出核 ＬＰＰ 算法。 假设欧式空间 Ｒ ｎ 中的数据矩阵通过非线性映 射函数 φ 映射到希尔伯特空间 Ｋ，即 φ：Ｒ ｎ→Ｋ。 使 用 φ（ Ｘ） 表 示 希 尔 伯 特 空 间 中 的 数 据 矩 阵， 即 φ（Ｘ）＝ [φ（ｘ１ ）φ（ｘ２ ） …φ（ｘｎ ） ] 。 那么，在希尔伯 特空间中的特征向量问题就可以表示为 φ（Ｘ）Ｌφ（Ｘ） Ｔ [ ] ｖ ＝ λ φ（Ｘ）Ｄφ（Ｘ） Ｔ [ ] ｖ （５） 考虑如下的核函数： Ｋ ｘｉ，ｘｊ ( ) ＝ φ ｘｉ ( )·φ ｘｊ ( ( ) ) ＝ φ ｘｉ ( ) Ｔφ ｘｊ ( ) 式（ ５） 中的特征向量是 φ（ ｘ１ ），φ（ ｘ２ ），…， φ（ｘｎ ） 的 线 性 组 合， 每 一 项 的 系 数 分 别 为 ａｉ， ｉ ＝ １，２，…，ｍ，即 ｖ ＝ ∑ ｎ ｉ ＝ １ ａｉφ（ｘｉ） ＝ φ（Ｘ）ａ。 其中， ａ ＝ ［ａ１ ａ２ … ａｎ ］ Ｔ 。 经过简单的代数变换，可以得 到如下特征向量问题：ＫＬＫａ ＝λＫＤＫａ。 ４ 希尔伯特－施密特独立性度量准则 已知一个参考聚类结果 Ｃ （１） ，使用 ＲＬＰＰ 算法学 习相对于 Ｃ （１）独立的子空间 Ａ，这样就确保了使用 Ａ 得到的聚类结果 Ｃ （２）与 Ｃ （１）不同。 为了计算不同 子空间之间的相异性，采用了 ＨＳＩＣ（ ｈｉｌｂｅｒｔ⁃ｓｃｈｍｉｄｔ ｉｎｄｅｐｅｎｄｅｎｃｅ ｃｒｉｔｅｒｉｏｎ） ［１］ ，更重要的是，ＬＰＰ 与 ＨＳＩＣ 结合后可以导出一个特征分解问题，这样就一定可 以计算出全局最佳解。 ＨＳＩＣ 是一种基于核的独立性度量方法，采用 Ｈｉｌｂｅｒｔ⁃Ｓｃｈｍｉｄｔ 互协方差算子，通过对该算子范数 的经验估计得到独立性判断准则。 具体来说，已知 Ｘ 和 Ｙ 两个随机变量，ＨＳＩＣ（Ｘ，Ｙ） 的值越大说明 Ｘ 和 Ｙ 的关联性越强，值等于 ０ 时说明 Ｘ 和 Ｙ 相互之间 完全独立。 数学上，令 Ｆ 表示再生核希尔伯特空间，φ（ ｘ） 表示数据 ｘ 从原空间映射到 Ｆ 中的映射函数，则核 函数可以写为Ｋ（ｘ，ｘ Ｔ ）＝ 〈φ（ｘ），φ（ｘ Ｔ ）〉。 同样的， 定义 ψ（ｙ）为原空间中的数据 ｙ 映射到再生希尔伯 特空间 Ｇ 的映射函数，核函数可以写为 Ｌ（ ｙ，ｙ Ｔ ） ＝ 〈ψ（ｙ），ψ（ｙ Ｔ ）〉。 则互协方差算子 Ｃｘｙ：Ｇ→Ｆ 可以 被定义为 Ｃｘｙ ＝ Ｅｘｙ [（φ（ｘ）－μｘ）（ψ（ｙ）－μｙ） ] ， 表示张量积。 Ｃｘｙ即为 Ｈｉｌｂｅｒｔ⁃Ｓｃｈｍｉｄｔ 算子，而 ＨＳＩＣ 定 义 为 Ｃｘｙ 的 Ｈｉｌｂｅｒｔ⁃Ｓｃｈｍｉｄｔ 算 子 范 数， 即 ＨＳＩＣ（Ｐｘｙ ，Ｆ，Ｇ） ＝ ‖Ｃｘｙ‖２ ＨＳ ，其中 Ｐｘｙ表示 Ｘ 和 Ｙ 的联合 分布。 实际上，不需要知道联合分布 Ｐｘｙ，已知 ｎ 个 观测值 Ｚ ＝ （ｘ１ ，ｙ１ ），…，（ｘｎ ，ｙ { ｎ ）} ，可以直接给出 ＨＳＩＣ 的经验估计值为 ＨＳＩＣ（Ｚ，Ｆ，Ｇ） ＝ （ｎ－１） －２ ｔｒ（ＫＨＬｙＨ）。 其中 Ｋ，Ｌｙ∈Ｒ ｎ×ｎ ，且 Ｋ，Ｌｙ 分别是核 Ｋ 和 Ｌ 关于 Ｚ 观 测值的 Ｇｒａｍ 矩阵，即 Ｋｉｊ ＝ ｋ（ｘｉ，ｘｊ），Ｌｙ ｉｊ ＝ ｌ（ｙｉ，ｙｊ）＝ 〈ｙｉ，ｙｊ〉，其中 ｙｉ 是一个二元向量，表示对 ｘｉ 的类标 签所做的编码（稍后将举例说明）。 Ｈ ＝ Ｉ－ １ ｎ ｅｎ ｅ Ｔ ｎ ，ｅｎ ·６０２· 智 能 系 统 学 报 第 １１ 卷
第5期 程肠，等：基于局部保留投影的多可选聚类发掘算法 ·603· 表示元素值全为1的列向量。r(·)表示矩阵的 此，P(X)LP(X)T+p(X)HL,Hp(X)'是实对称矩 迹。 阵。作为一个特征分解问题，A的最优解由前k个 为了表示简单，使用HSICox,)代替HSIC(2.F,, 最小非零特征值对应的特征向量构成，即A= 表示随机变量X和(x)=A'x,也就是X和Y之间 [a,a2…&]。下一步，可以使用k-means算法 的依赖性。 对子空间A进行聚类，得到可供选择的聚类结 假设有8个数据{x1,x2,…,xg,{,其中x,和x2, 果C2)。 x3和x4,x3和x6,x,和xg分别为一类。则向量y1= 可以看到，(X)HL,He(X)I直接影响了LPP y2=(1000),y3=y4=(0100),y5=y6= 算法中(X)Lp(X)T项，也就是说，可以把两个聚 (0010)T,y,=yg=(0001)'。矩阵Y的每一行对 类结果之间的独立性看作添加的约束项。同时，通 应一个y。L,是一个8×8的矩阵，由：和y的点 过添加更多的HSIC项，将算法推广可以找到更多 积构成。K是一个8×8的矩阵，表示(x:)和(x) 可供选择的聚类结果。 之间的相似度。同时注意，根据定义，H是一个n×n 举例来说，在寻找第3个可供选择的聚类结果 (在本例中是8×8)的常数矩阵，每行每列的和都等 C3)时，只要提供之前找到的两个聚类结果C)和 于0。因此，在上述示例中，每一行（列）都包含7个 C2),并把式(6)中的HSIC(ax.c)一项替换为 (安)和1个 HSIC(ATx.c)+HSIC(ax.c2,即可。因此只要在式 (8)中使用A'XHL,HXA+A'XHL2HXA,即直接 5基于局部保留投影的多可选聚类发 使用AXH(L,:+L,2）HXA代替AXHL,HXA。 掘算法 也就是说，使用(L,+L,2)代替了L,其他矩阵保持 不变即可。 由于通过HSIC,)可以自然地评估结构很复 RLPP算法描述如下： 杂的样本X和Y之间的相关性，因此结合HSICo.” 1)输入数据集X;一个X上的参考聚类结果 对LPP的目标函数进行修改。要求是转换矩阵A C。 必须能够发掘嵌入在高维数据中的低维流形结构， 2)输出一个数据集X上可供选择的参考聚类 并且与已知的聚类结果C)完全独立。换句话说， 结果C2。 在所有与已经存在的聚类结果C)不同的子空间 3)算法流程： 中，要选出能够最好地保持高维数据流形结构的子 ①计算L,L,=(y:y〉，其中y:是一个二元向 空间。因此，改进LPP的目标函数如下： 量，表示C)中x,的类标签的编码。 A=argmin A'XLX'A HSIC(ATX.c(D)= ②计算H=1-e.c。 argmin A XLX'A tr(HKHL,) (6) 式中：A表示A的最佳解，且由迹的性质可知 ③计算权值矩阵W,如果x是x:的k近邻点， r(HKHL,)=r(KHL,H)。不同的核函数在计算变 那么W,=exp- x-12 (t∈R),否则W,=0。 量之间的独立性时结果不同，这里采用线性核函数， t 映射函数定义为：(x)=ATx,因此，K= ④计算矩阵D,Da=∑W,计算拉普拉斯矩阵 (p(X),P(X)〉=YAAX。即 L,L=D-W。 ATXLXA tr(HKHL,)= ⑤使用高斯核计算核矩阵K,K=9(x)'· AXLXA+AXHL HX'A= p()。 AT (XLX+XHL HX)A (7) ⑥分解核矩阵K,K=PP,根据P(X)=AP 将数据集合X映射到高维特征空间中后，就可 得到(X)。 以最终得到(X)=[p(x)(x2)…(xn)]。其 ⑦计算(X)LP(X)'+(X)HL,H(X)的特 中，核矩阵K的元素为K=p(x:)I·(x)。即： 征值和特征向量。 A.m=A((X)L(X)+(X)HL H (X))A ⑧按特征值从小到大的顺序对特征向量排序。 (8) ⑨选择前k个最小的特征值对应的特征向量， 因为H和L,都是对称矩阵，所以 即A=[a0a1…ak-1Jo (X)HL,H(X)'也是对称矩阵，同样，因为L是 ①c2)-k-means(A'e(X))。 对称矩阵，所以P(X)L(X)T也是对称矩阵。因 RLPP算法的时间复杂度完全由计算最近邻矩
表示元素值全为 １ 的列向量。 ｔｒ（·） 表示矩阵的 迹。 为了表示简单，使用 ＨＳＩＣ（Ｘ，Ｙ） 代替 ＨＳＩＣ（Ｚ，Ｆ，Ｇ） ， 表示随机变量 Ｘ 和 φ（ｘ）＝ Ａ Ｔ ｘ，也就是 Ｘ 和 Ｙ 之间 的依赖性。 假设有 ８ 个数据｛ｘ１ ，ｘ２ ，…，ｘ８ ，｝，其中 ｘ１ 和 ｘ２ ， ｘ３ 和 ｘ４ ，ｘ５ 和 ｘ６ ，ｘ７ 和 ｘ８ 分别为一类。 则向量 ｙ１ ＝ ｙ２ ＝ （１ ０ ０ ０） Ｔ ， ｙ３ ＝ ｙ４ ＝ （０ １ ０ ０） Ｔ ， ｙ５ ＝ ｙ６ ＝ （０ ０ １ ０） Ｔ ，ｙ７ ＝ ｙ８ ＝ （０ ０ ０ １） Ｔ 。 矩阵 Ｙ 的每一行对 应一个 ｙｉ。 Ｌｙ 是一个 ８×８ 的矩阵，由 ｙｉ 和 ｙｊ 的点 积构成。 Ｋ 是一个 ８×８ 的矩阵，表示 φ（ｘｉ）和φ（ｘｊ） 之间的相似度。 同时注意，根据定义，Ｈ 是一个 ｎ×ｎ （在本例中是 ８×８）的常数矩阵，每行每列的和都等 于 ０。 因此，在上述示例中，每一行（列）都包含 ７ 个 （－ １ ８ ）和 １ 个 ７ ８ 。 ５ 基于局部保留投影的多可选聚类发 掘算法 由于通过 ＨＳＩＣ（Ｘ，Ｙ） 可以自然地评估结构很复 杂的样本 Ｘ 和 Ｙ 之间的相关性，因此结合 ＨＳＩＣ（Ｘ，Ｙ） 对 ＬＰＰ 的目标函数进行修改。 要求是转换矩阵 Ａ 必须能够发掘嵌入在高维数据中的低维流形结构， 并且与已知的聚类结果 Ｃ （１） 完全独立。 换句话说， 在所有与已经存在的聚类结果 Ｃ （１） 不同的子空间 中，要选出能够最好地保持高维数据流形结构的子 空间。 因此，改进 ＬＰＰ 的目标函数如下： Ａｏｐｔ ＝ ａｒｇｍｉｎ Ａ ＴＸＬＸ ＴＡ ＋ ＨＳＩＣ（ＡＴＸ，Ｃ（１）） ＝ ａｒｇｍｉｎ Ａ ＴＸＬＸ ＴＡ ＋ ｔｒ ＨＫＨＬｙ ( ) （６） 式中：Ａｏｐｔ 表示 Ａ 的最佳解， 且由迹的性质可知 ｔｒ ＨＫＨＬｙ ( ) ＝ ｔｒ(ＫＨＬｙＨ) 。 不同的核函数在计算变 量之间的独立性时结果不同，这里采用线性核函数， 映射 函 数 定 义 为： φ（ｘ） ＝ Ａ Ｔ ｘ ， 因 此， Ｋ ＝ 〈φ（Ｘ），φ（Ｘ）〉 ＝ Ｘ ＴＡＡ ＴＸ 。 即 Ａ ＴＸＬＸ ＴＡ ＋ ｔｒ ＨＫＨＬｙ ( ) ＝ Ａ ＴＸＬＸ ＴＡ ＋ Ａ ＴＸＨＬｙＨＸ ＴＡ ＝ Ａ Ｔ ＸＬＸ Ｔ ＋ ＸＨＬｙＨＸ Ｔ ( ) Ａ （７） 将数据集合 Ｘ 映射到高维特征空间中后，就可 以最终得到 φ（Ｘ）＝ ［φ（ｘ１ ） φ（ｘ２ ） … φ（ｘｎ ）］。 其 中，核矩阵 Ｋ 的元素为 Ｋｉｊ ＝φ （ｘｉ） Ｔ·φ（ｘｊ）。 即： Ａｏｐｔ ＝ Ａ Ｔ （φ（Ｘ）Ｌφ （Ｘ） Ｔ ＋ φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ ）Ａ （８） 因 为 Ｈ 和 Ｌｙ 都 是 对 称 矩 阵， 所 以 φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ也是对称矩阵，同样，因为 Ｌ 是 对称矩阵，所以 φ(Ｘ) Ｌφ （Ｘ） Ｔ 也是对称矩阵。 因 此，φ（Ｘ）Ｌφ （Ｘ） Ｔ ＋φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ 是实对称矩 阵。 作为一个特征分解问题，Ａｏｐｔ的最优解由前 ｋ 个 最小 非 零 特 征 值 对 应 的 特 征 向 量 构 成， 即 Ａ ＝ ［α１ α２… αｋ ］。 下一步，可以使用 ｋ⁃ｍｅａｎｓ ［１９］ 算法 对子空间 Ａ 进行聚类， 得到可供选择的聚类结 果 Ｃ （２） 。 可以看到，φ（Ｘ）ＨＬｙＨφ （Ｘ） Ｔ 直接影响了 ＬＰＰ 算法中 φ（Ｘ）Ｌφ （Ｘ） Ｔ 项，也就是说，可以把两个聚 类结果之间的独立性看作添加的约束项。 同时，通 过添加更多的 ＨＳＩＣ 项，将算法推广可以找到更多 可供选择的聚类结果。 举例来说，在寻找第 ３ 个可供选择的聚类结果 Ｃ （３）时，只要提供之前找到的两个聚类结果 Ｃ （１） 和 Ｃ （２） ，并 把 式 （ ６ ） 中 的 ＨＳＩＣ（ＡＴＸ，Ｃ（１）） 一 项 替 换 为 ＨＳＩＣ（ＡＴＸ，Ｃ（１） ） ＋ ＨＳＩＣ（ＡＴＸ，Ｃ（２）） 即可。 因此只要在 式 （８）中使用 Ａ ＴＸＨＬｙ１ＨＸ ＴＡ＋Ａ ＴＸＨＬｙ２ＨＸ ＴＡ，即直接 使用 Ａ ＴＸＨ （ Ｌｙ１ ＋ Ｌｙ２ ） ＨＸ ＴＡ 代替 Ａ ＴＸＨＬｙＨＸ ＴＡ。 也就是说，使用（Ｌｙ１ ＋Ｌｙ２ ）代替了 Ｌｙ，其他矩阵保持 不变即可。 ＲＬＰＰ 算法描述如下： １）输入 数据集 Ｘ；一个 Ｘ 上的参考聚类结果 Ｃ （１） 。 ２）输出 一个数据集 Ｘ 上可供选择的参考聚类 结果 Ｃ （２） 。 ３）算法流程： ①计算 Ｌｙ，Ｌｙ ＝ 〈 ｙｉ，ｙｊ〉，其中 ｙｉ 是一个二元向 量，表示 Ｃ （１）中 ｘｉ 的类标签的编码。 ②计算 Ｈ＝ Ｉ－ １ ｎ ｅｎ ｅ Ｔ ｎ 。 ③计算权值矩阵 Ｗ，如果 ｘｊ 是 ｘｉ 的 ｋ 近邻点， 那么 Ｗｉｊ ＝ ｅｘｐ－ ‖ｘｉ －ｘｊ‖２ ｔ （ｔ∈Ｒ），否则 Ｗｉｊ ＝ ０。 ④计算矩阵 Ｄ， Ｄｉｉ ＝ ∑ ｊ Ｗｉｊ，计算拉普拉斯矩阵 Ｌ，Ｌ ＝ Ｄ － Ｗ 。 ⑤使用高斯核计算核矩阵 Ｋ，Ｋｉｊ ＝ φ （ｘｉ） Ｔ · φ（ｘｊ）。 ⑥分解核矩阵 Ｋ，Ｋ ＝ Ｐ ＴΛＰ，根据 φ（Ｘ） ＝ Λ １ ２ Ｐ 得到 φ（Ｘ）。 ⑦计算 φ（Ｘ）Ｌφ （Ｘ） Ｔ ＋φ（Ｘ）ＨＬｙＨφ（Ｘ） Ｔ 的特 征值和特征向量。 ⑧按特征值从小到大的顺序对特征向量排序。 ⑨选择前 ｋ 个最小的特征值对应的特征向量， 即 Ａ＝ ［ａ０ ａ１… ａｋ－１ ］。 ⑩Ｃ （２）＝ ｋ⁃ｍｅａｎｓ（Ａ Ｔφ（Ｘ））。 ＲＬＰＰ 算法的时间复杂度完全由计算最近邻矩 第 ５ 期 程旸，等：基于局部保留投影的多可选聚类发掘算法 ·６０３·
·604. 智能系统学报 第11卷 阵以及核矩阵决定，因为它们的时间复杂度均为 果，并与其他算法进行比较。第1组人工数据集 0(n2d),因此整体的时间复杂度也为0(n2d)。 Sym1分布在二维空间内，分为4部分，每部分由200 个数据点组成，共8O0个数据，点。使用数据集Syml 6 实验与分析 的目的是检验算法是否能够尽可能多的发现可供选 6.1聚类结果评估 择的聚类结果，且所有结果均满足与初始聚类结果 聚类结果根据聚类质量和相异性两方面进行评 正交的条件。第2组人工数据集Sym2的结构较为 估。聚类质量分为两种情况：如果已知正确的类标， 复杂，每部分的形状都是非凸的。使用数据集Sy2 则可选聚类结果和正确的类标之间通过F-measure 的目的是检验算法是否能够处理非线性的数据结 计算，计算公式为F=2P×R/(P+R),其中P和R分 构，并且发掘出嵌入在高维数据中的低维流形结构。 别表示准确率(precision)和召回率(recall);否则， 图1中的第1行表示的是RLPP使用数据集 使用Dunn Index计算，表示为Dl(g。数学上，Dunn Syml得到的运行结果。其中，第1列表示的是所提 min均{8(c,9)} 供的参考聚类结果C),第2列表示的是由RLPP ndex定义为Dlo-742,其中8：GxC一 得到的可供选择的聚类结果C2)。从图中可以直观 R。,表示类与类之间的距离，△：C→R。表示类内 地看出，RLPP成功地找到了与所提供的参考聚类 直径。对于评估聚类结果的相异性，使用了两种不 结果完全不相同，但是聚类质量很高的可选聚类结 同的方法。第1种是最为常用的标准化互信息 果。另外，如果我们把该结果C2)看作除C)外新 (normalized mutual information,NMl),第2种是杰 增的参考聚类结果，并且寻找第2个可选的参考聚 卡德指数(Jaccard index,.JI)。 类结果C),RLPP会得到第3列所显示的聚类结 对于NMI和JⅡ指标，值越小意味着不同聚类结 果。C3)在欧氏距离下与前两个聚类结果相比不是 果之间的相似度越高；对于F-measure和Dunn Index 特别得自然，但是C)仍然很有启发性，并且它完全 指标，值越大意味着更高的聚类质量。 独立于前2个参考聚类结果C)和C2)。同时注意 6.2人工数据集 到，RPCA算法无法寻找出合适的C)。在表1中， 使用两种流行的人工数据集评估LPP的效 提供了这些算法的表现。 14 2 10 2 6 1012 14 -4 2 0 246 101214-4-202 468101214 (a)Synl数据集可选聚类结果C (b)Syml数据集可选聚类结果C (c)Synl数据集可选聚类结果C ② 88 4-4-3 -2 4-4-3 -2-1 01234 (d)Syn2数据集可选聚类结果C (e)Syn2数据集可选聚类结果Ca (f)Syn2数据集可选聚类结果C 图1由数据集Synl(第1行)和Syn2(第2行)得到的可选聚类结果 Fig.1 Alternative clusterings uncovered from Synl(1"row)and Syn2(24 row)datasets
阵以及核矩阵决定，因为它们的时间复杂度均为 Ｏ（ｎ ２ ｄ），因此整体的时间复杂度也为 Ｏ（ｎ ２ ｄ）。 ６ 实验与分析 ６．１ 聚类结果评估 聚类结果根据聚类质量和相异性两方面进行评 估。 聚类质量分为两种情况：如果已知正确的类标， 则可选聚类结果和正确的类标之间通过 Ｆ⁃ｍｅａｓｕｒｅ 计算，计算公式为 Ｆ ＝ ２Ｐ×Ｒ ／ （Ｐ＋Ｒ），其中 Ｐ 和 Ｒ 分 别表示准确率（ ｐｒｅｃｉｓｉｏｎ） 和召回率（ ｒｅｃａｌｌ）；否则， 使用 Ｄｕｎｎ Ｉｎｄｅｘ 计算，表示为 ＤＩ（Ｃ） 。 数学上，Ｄｕｎｎ Ｉｎｄｅｘ 定义为 ＤＩ（Ｃ） ＝ ｍｉｎｉ≠ｊ｛δ（ｃｉ，ｃｊ）｝ ｘ１≤ｌ≤ｋ｛Δ（ｃｌ）｝ ，其中 δ：Ｃ×Ｃ→ Ｒ ＋ ０ ，表示类与类之间的距离，Δ：Ｃ→Ｒ ＋ ０ 表示类内 直径。 对于评估聚类结果的相异性，使用了两种不 同的方法。 第 １ 种是最为常用的标准化互信息 （ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ， ＮＭＩ），第 ２ 种是杰 卡德指数（Ｊａｃｃａｒｄ ｉｎｄｅｘ， ＪＩ）。 对于 ＮＭＩ 和 ＪＩ 指标，值越小意味着不同聚类结 果之间的相似度越高；对于 Ｆ⁃ｍｅａｓｕｒｅ 和 Ｄｕｎｎ Ｉｎｄｅｘ 指标，值越大意味着更高的聚类质量。 ６．２ 人工数据集 使用两种流行的人工数据集评估 ＲＬＰＰ 的效 果，并与其他算法进行比较。 第 １ 组人工数据集 Ｓｙｎ１ 分布在二维空间内，分为 ４ 部分，每部分由 ２００ 个数据点组成，共 ８００ 个数据点。 使用数据集 Ｓｙｎ１ 的目的是检验算法是否能够尽可能多的发现可供选 择的聚类结果，且所有结果均满足与初始聚类结果 正交的条件。 第 ２ 组人工数据集 Ｓｙｎ２ 的结构较为 复杂，每部分的形状都是非凸的。 使用数据集 Ｓｙｎ２ 的目的是检验算法是否能够处理非线性的数据结 构，并且发掘出嵌入在高维数据中的低维流形结构。 图 １ 中的第 １ 行表示的是 ＲＬＰＰ 使用数据集 Ｓｙｎ１ 得到的运行结果。 其中，第 １ 列表示的是所提 供的参考聚类结果 Ｃ （１） ，第 ２ 列表示的是由 ＲＬＰＰ 得到的可供选择的聚类结果 Ｃ （２） 。 从图中可以直观 地看出，ＲＬＰＰ 成功地找到了与所提供的参考聚类 结果完全不相同，但是聚类质量很高的可选聚类结 果。 另外，如果我们把该结果 Ｃ （２） 看作除 Ｃ （１） 外新 增的参考聚类结果，并且寻找第 ２ 个可选的参考聚 类结果 Ｃ （３） ，ＲＬＰＰ 会得到第 ３ 列所显示的聚类结 果。 Ｃ （３）在欧氏距离下与前两个聚类结果相比不是 特别得自然，但是 Ｃ （３）仍然很有启发性，并且它完全 独立于前 ２ 个参考聚类结果 Ｃ （１）和 Ｃ （２） 。 同时注意 到，ＲＰＣＡ 算法无法寻找出合适的 Ｃ （３） 。 在表 １ 中， 提供了这些算法的表现。 图 １ 由数据集 Ｓｙｎ１（第 １ 行）和 Ｓｙｎ２（第 ２ 行）得到的可选聚类结果 Ｆｉｇ．１ Ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕｎｃｏｖｅｒｅｄ ｆｒｏｍ Ｓｙｎ１（１ ｓｔ ｒｏｗ） ａｎｄ Ｓｙｎ２（２ ｎｄ ｒｏｗ） ｄａｔａｓｅｔｓ ·６０４· 智 能 系 统 学 报 第 １１ 卷