第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
阵以及核矩阵决定，因为它们的时间复杂度均为 Ｏ（ｎ ２ ｄ），因此整体的时间复杂度也为 Ｏ（ｎ ２ ｄ）。 ６ 实验与分析 ６．１ 聚类结果评估 聚类结果根据聚类质量和相异性两方面进行评 估。 聚类质量分为两种情况：如果已知正确的类标， 则可选聚类结果和正确的类标之间通过 Ｆ⁃ｍｅａｓｕｒｅ 计算，计算公式为 Ｆ ＝ ２Ｐ×Ｒ ／ （Ｐ＋Ｒ），其中 Ｐ 和 Ｒ 分 别表示准确率（ ｐｒｅｃｉｓｉｏｎ） 和召回率（ ｒｅｃａｌｌ）；否则， 使用 Ｄｕｎｎ Ｉｎｄｅｘ 计算，表示为 ＤＩ（Ｃ） 。 数学上，Ｄｕｎｎ Ｉｎｄｅｘ 定义为 ＤＩ（Ｃ） ＝ ｍｉｎｉ≠ｊ｛δ（ｃｉ，ｃｊ）｝ ｘ１≤ｌ≤ｋ｛Δ（ｃｌ）｝ ，其中 δ：Ｃ×Ｃ→ Ｒ ＋ ０ ，表示类与类之间的距离，Δ：Ｃ→Ｒ ＋ ０ 表示类内 直径。 对于评估聚类结果的相异性，使用了两种不 同的方法。 第 １ 种是最为常用的标准化互信息 （ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ， ＮＭＩ），第 ２ 种是杰 卡德指数（Ｊａｃｃａｒｄ ｉｎｄｅｘ， ＪＩ）。 对于 ＮＭＩ 和 ＪＩ 指标，值越小意味着不同聚类结 果之间的相似度越高；对于 Ｆ⁃ｍｅａｓｕｒｅ 和 Ｄｕｎｎ Ｉｎｄｅｘ 指标，值越大意味着更高的聚类质量。 ６．２ 人工数据集 使用两种流行的人工数据集评估 ＲＬＰＰ 的效 果，并与其他算法进行比较。 第 １ 组人工数据集 Ｓｙｎ１ 分布在二维空间内，分为 ４ 部分，每部分由 ２００ 个数据点组成，共 ８００ 个数据点。 使用数据集 Ｓｙｎ１ 的目的是检验算法是否能够尽可能多的发现可供选 择的聚类结果，且所有结果均满足与初始聚类结果 正交的条件。 第 ２ 组人工数据集 Ｓｙｎ２ 的结构较为 复杂，每部分的形状都是非凸的。 使用数据集 Ｓｙｎ２ 的目的是检验算法是否能够处理非线性的数据结 构，并且发掘出嵌入在高维数据中的低维流形结构。 图 １ 中的第 １ 行表示的是 ＲＬＰＰ 使用数据集 Ｓｙｎ１ 得到的运行结果。 其中，第 １ 列表示的是所提 供的参考聚类结果 Ｃ （１） ，第 ２ 列表示的是由 ＲＬＰＰ 得到的可供选择的聚类结果 Ｃ （２） 。 从图中可以直观 地看出，ＲＬＰＰ 成功地找到了与所提供的参考聚类 结果完全不相同，但是聚类质量很高的可选聚类结 果。 另外，如果我们把该结果 Ｃ （２） 看作除 Ｃ （１） 外新 增的参考聚类结果，并且寻找第 ２ 个可选的参考聚 类结果 Ｃ （３） ，ＲＬＰＰ 会得到第 ３ 列所显示的聚类结 果。 Ｃ （３）在欧氏距离下与前两个聚类结果相比不是 特别得自然，但是 Ｃ （３）仍然很有启发性，并且它完全 独立于前 ２ 个参考聚类结果 Ｃ （１）和 Ｃ （２） 。 同时注意 到，ＲＰＣＡ 算法无法寻找出合适的 Ｃ （３） 。 在表 １ 中， 提供了这些算法的表现。 图 １ 由数据集 Ｓｙｎ１（第 １ 行）和 Ｓｙｎ２（第 ２ 行）得到的可选聚类结果 Ｆｉｇ．１ Ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕｎｃｏｖｅｒｅｄ ｆｒｏｍ Ｓｙｎ１（１ ｓｔ ｒｏｗ） ａｎｄ Ｓｙｎ２（２ ｎｄ ｒｏｗ） ｄａｔａｓｅｔｓ ·６０４· 智 能 系 统 学 报 第 １１ 卷
第5期 程肠，等：基于局部保留投影的多可选聚类发掘算法 ·605. 表1人工数据集Syml上3种算法的表现 Table 1 Clustering performance of all algorithms for synthetic dataset Synl 算法 NMI2 NMI NMI2 e J 几 F2 FB RPCA 0.00 0.33 1.00 RegGB 0.00 0.00 0.00 0.33 0.33 0.33 1.00 1.00 1.00 RLPP 0.00 0.00 0.00 0.33 0.33 0.33 1.00 1.00 1.00 表2人工数据集Sym2上3种算法的表现 Table 2 Clustering performance of all algorithms for synthetic dataset Syn2 算法 NMI2 NMI NMI2 JI2 几g J几 S RegGB 0.00 0.00 0.00 0.33 0.33 0.33 1.00 1.00 1.00 RLPP 0.00 0.00 0.00 0.33 0.33 0.33 1.00 1.00 1.00 6.3舍尔图数据集 虽然图2(f)的结果看似更佳，但是图2(d)保留了 选择文献[11]中所介绍的埃舍尔图(escher im- 原图中更多的信息，每只爬行动物的轮廓都能够得 age)作为另一个用于寻找多个可选聚类结果实验的 到保留，这是由于RLPP采用了流形子空间学习技 数据集。对于人眼来说，埃舍尔图有多种分割结果 (即聚类结果)。图2(a)显示的图片为原始图片， 术，能够最大程度地保留原始数据的结构。对每种 可以看到图中有多只爬行动物，并且聚类时明显可 算法重复运行了10次，表3给出了这些算法的平均 以有多种聚类结果。在分割过程中，图中的每个像 表现。 素点都表示一个反映了RGB信息的数据点。我们 使用k-means对图2(a)进行聚类。图2(b)为k- means得到的聚类结果，作为其他算法所需要的参 考聚类结果。图2(c)和图2(d)分别为RLPP得到 产 的可选聚类结果C(2)和C3),可以看出图2(c)中的 (b) (c) 爬行动物为水平姿势，图2(d)中的爬行动物为垂直 姿势。为了对比，提供了由RegGB算法得到的结果 (RPCA算法得到的C(2)与RegGB算法近似，C3)则 效果很差，因此不加入对比)。图2(e)和图2(f)为 2 RegGB得到的可选聚类结果C(2)和C3)。从肉眼观 (d) (e) (f 察的角度可以发现，图2(c)与图2(e)相比轮廓更 图2埃舍尔图数据集上的图像分割结果 加清晰，聚类的效果更好。图2(d)与图2()相比， Fig.2 Image segmentation results on Escher image data 表3埃舍尔图数据集上两种算法的表现 Table 3 Clustering performance of two algorithms on the Escher image data 算法 NMI2 NMI3 NMI JIp JI2 DI DIs DL RegGB 0.05 0.27 0.26 0.39 0.33 0.28 3.81 0.05 2.38 RLPP 0.03 0.06 0.01 0.19 0.39 0.34 3.81 0.02 1.60 6.4 CMUFace数据集 随机选取了3个人的全部图像进行试验。 使用UCI数据库中的CMUFace数据集检验算 图3显示的是聚类结果的平均值的图像。其中 法。CMUFace数据集包含20个人的图像，每个人 第1行是原始图像经由k-means算法得到的平均值 又分为不同的面部表情（正常、高兴、悲伤、生气）， 图像，第2行由LPP算法得到，第3行和第4行由 不同的头部朝向（向左、向右、向前、向上），不同眼 RPCA与RegGB算法得到。 部状况（睁开、墨镜）。每个人有32张图片，包含了 从图像上看，第1行聚类的依据是不同的人，其 上述特征的组合。由于图片中的人的身份是已知 余3行聚类的依据是人不同的头部朝向。很明显，3 的，因此身份信息可以作为参考聚类结果直接使用。 种算法都从数据集中得到了另一组完全不同，但是
表 １ 人工数据集 Ｓｙｎ１ 上 ３ 种算法的表现 Ｔａｂｌｅ １ Ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ａｌｌ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｙｎｔｈｅｔｉｃ ｄａｔａｓｅｔ Ｓｙｎ１ 算法 ＮＭＩ１２ ＮＭＩ１３ ＮＭＩ２３ ＪＩ１２ ＪＩ１３ ＪＩ２３ Ｆ１２ Ｆ１３ Ｆ２３ ＲＰＣＡ ０．００ ＼ ＼ ０．３３ ＼ ＼ １．００ ＼ ＼ ＲｅｇＧＢ ０．００ ０．００ ０．００ ０．３３ ０．３３ ０．３３ １．００ １．００ １．００ ＲＬＰＰ ０．００ ０．００ ０．００ ０．３３ ０．３３ ０．３３ １．００ １．００ １．００ 表 ２ 人工数据集 Ｓｙｎ２ 上 ３ 种算法的表现 Ｔａｂｌｅ ２ Ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ａｌｌ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｙｎｔｈｅｔｉｃ ｄａｔａｓｅｔ Ｓｙｎ２ 算法 ＮＭＩ１２ ＮＭＩ１３ ＮＭＩ２３ ＪＩ１２ ＪＩ１３ ＪＩ２３ Ｆ１２ Ｆ１３ Ｆ２３ ＲｅｇＧＢ ０．００ ０．００ ０．００ ０．３３ ０．３３ ０．３３ １．００ １．００ １．００ ＲＬＰＰ ０．００ ０．００ ０．００ ０．３３ ０．３３ ０．３３ １．００ １．００ １．００ ６．３ 舍尔图数据集 选择文献［１１］中所介绍的埃舍尔图（ ｅｓｃｈｅｒ ｉｍ⁃ ａｇｅ）作为另一个用于寻找多个可选聚类结果实验的 数据集。 对于人眼来说，埃舍尔图有多种分割结果 （即聚类结果）。 图 ２（ ａ） 显示的图片为原始图片， 可以看到图中有多只爬行动物，并且聚类时明显可 以有多种聚类结果。 在分割过程中，图中的每个像 素点都表示一个反映了 ＲＧＢ 信息的数据点。 我们 使用 ｋ⁃ｍｅａｎｓ 对图 ２（ ａ） 进行聚类。 图 ２（ ｂ） 为 ｋ⁃ ｍｅａｎｓ 得到的聚类结果，作为其他算法所需要的参 考聚类结果。 图 ２（ｃ）和图 ２（ｄ）分别为 ＲＬＰＰ 得到 的可选聚类结果 Ｃ （２）和 Ｃ （３） ，可以看出图 ２（ｃ）中的 爬行动物为水平姿势，图 ２（ｄ）中的爬行动物为垂直 姿势。 为了对比，提供了由 ＲｅｇＧＢ 算法得到的结果 （ＲＰＣＡ 算法得到的 Ｃ （２）与 ＲｅｇＧＢ 算法近似，Ｃ （３） 则 效果很差，因此不加入对比）。 图 ２（ｅ）和图 ２（ｆ）为 ＲｅｇＧＢ 得到的可选聚类结果 Ｃ （２）和 Ｃ （３） 。 从肉眼观 察的角度可以发现，图 ２（ｃ）与图 ２（ ｅ）相比轮廓更 加清晰，聚类的效果更好。 图 ２（ｄ）与图 ２（ｆ）相比， 虽然图 ２（ｆ）的结果看似更佳，但是图 ２（ ｄ）保留了 原图中更多的信息，每只爬行动物的轮廓都能够得 到保留，这是由于 ＲＬＰＰ 采用了流形子空间学习技 术，能够最大程度地保留原始数据的结构。 对每种 算法重复运行了 １０ 次，表 ３ 给出了这些算法的平均 表现。 图 ２ 埃舍尔图数据集上的图像分割结果 Ｆｉｇ．２ Ｉｍａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｒｅｓｕｌｔｓ ｏｎ Ｅｓｃｈｅｒ ｉｍａｇｅ ｄａｔａ 表 ３ 埃舍尔图数据集上两种算法的表现 Ｔａｂｌｅ ３ Ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｔｈｅ Ｅｓｃｈｅｒ ｉｍａｇｅ ｄａｔａ 算法 ＮＭＩ１２ ＮＭＩ１３ ＮＭＩ２３ ＪＩ１２ ＪＩ１３ ＪＩ２３ ＤＩ１２ ＤＩ１３ ＤＩ２３ ＲｅｇＧＢ ０．０５ ０．２７ ０．２６ ０．３９ ０．３３ ０．２８ ３．８１ ０．０５ ２．３８ ＲＬＰＰ ０．０３ ０．０６ ０．０１ ０．１９ ０．３９ ０．３４ ３．８１ ０．０２ １．６０ ６．４ ＣＭＵＦａｃｅ 数据集 使用 ＵＣＩ 数据库中的 ＣＭＵＦａｃｅ 数据集检验算 法。 ＣＭＵＦａｃｅ 数据集包含 ２０ 个人的图像，每个人 又分为不同的面部表情（正常、高兴、悲伤、生气）， 不同的头部朝向（向左、向右、向前、向上），不同眼 部状况（睁开、墨镜）。 每个人有 ３２ 张图片，包含了 上述特征的组合。 由于图片中的人的身份是已知 的，因此身份信息可以作为参考聚类结果直接使用。 随机选取了 ３ 个人的全部图像进行试验。 图 ３ 显示的是聚类结果的平均值的图像。 其中 第 １ 行是原始图像经由 ｋ⁃ｍｅａｎｓ 算法得到的平均值 图像，第 ２ 行由 ＲＬＰＰ 算法得到，第 ３ 行和第 ４ 行由 ＲＰＣＡ 与 ＲｅｇＧＢ 算法得到。 从图像上看，第 １ 行聚类的依据是不同的人，其 余 ３ 行聚类的依据是人不同的头部朝向。 很明显，３ 种算法都从数据集中得到了另一组完全不同，但是 第 ５ 期 程旸，等：基于局部保留投影的多可选聚类发掘算法 ·６０５·
·606 智能系统学报 第11卷 同等重要的聚类结果。从图中可以看出，RLPP和 7结束语 RPCA的聚类效果最好，RegGB稍差。表4是这3 种算法的对比。 本文提出了一种新的算法RLPP,采用子空间流 表4 CMUFace数据集上3种算法的表现 形学习技术，寻找可供选择的聚类结果。RLPP算 Table 4 Clustering performance of all algorithms for CM- 法的优势在于最终能够转化为特征分解问题，也就 UFace data 是说可以找到封闭解，并且子空间一定是全局最优 算法 NMI F 的，这也是本文区别于其他相关研究的重要特点之 RPCA 0.0124 0.2941 0.7139 一。在文章中对RLPP算法进行了论证和实验，并 对比了目前效果最好的著名算法。实验结果表明 RegGB 0.6690 0.4444 0.7512 RLPP算法的性能不输于甚至优于其他算法。对于 RLPP 0.0766 0.2151 0.7021 如何更好地选取最小特征值的个数k,以及如何降 低算法在处理维数较大数据时的时间复杂度，都是 继续研究的方向。 参考文献： [1]DANG Xuanhong,BAILEY J.Generating multiple alterna- tive clusterings via globally optimal subspaces[J].Data (a)k-means算法基于不同人的聚类结果 mining and knowledge discovery,2014,28(3):569-592. [2]GRETTON A,BOUSQUET O,SMOLA A,et al.Measuring statistical dependence with Hilbert-Schmidt norms M]// JAIN S.SIMON H U.TOMITA E.Algorithmic Learning Theory.Berlin Heidelberg:Springer,2005:63-77 (b)RLPP算法基于头部朝向的聚类结果 [3]HE Xiaofei,NIYOGI X.Locality preserving projections [C]//Advances in Neural Information Processing Systems. Vancouver,Canada,2003,16:153-160. [4]BAE E,BAILEY J.COALA:a novel approach for the ex- traction of an alternate clustering of high quality and high dissimilarity[C]//Proceedings of the 6th International Con- (C)RPCA算法基于头部朝向的聚类结果 ference on Data Mining.Hong Kong,China,2006:53-62. 5]GONDEK D.HOFMANN T.Non-redundant data clustering []Knowledge and information systems,2007,12(1):1- [6]JAIN P,MEKA R,DHILLON I S.Simultaneous unsuper- vised learning of disparate clusterings[.Statistical analy- (d)RegGB算法基于头部朝向的聚类结果 sis and data mining:the ASA data science journal,2008,1 图3 CMUFace数据集上的运行结果 (3):195-210. Fig.3 Results on CMUFace data [7]DANG Xuanhong,BAILEY J.Generation of alternative 6.5算法运行时间 clusterings using the CAMI approach[C]//Proceedings of the SIAM International Conference on Data Mining,SDM 实验均在MARTLAB8.1.0.604(R2013a)平台下 2010.Columbus,0hio.USA,2010.10:118-129. 完成，操作系统为4位Windows7,CPU为Intel(R) [8]DANG Xuanhong,BAILEY J.A hierarchical information Core(TM)i3-32403.40GHz,内存为4GB。 theoretic technique for the discovery of non linear alternative 对于人工数据集Synl和Svn2,RLPP算法发掘 clusterings[C]//Proceedings of the 16th ACM SIGKDD In- 出一个可供选择的聚类结果分别耗时3.4s和2.9s。 ternational Conference on Knowledge Discovery and Data 对于Esher图，由于聚类之前需要进行图像一维化 Mining.Washington,DC,USA,2010:573-582 处理，因此数据集的维数很大，共耗时136s。对于 [9]VINH N X,EPPS J.MinCEntropy:a novel information the- CMUFace数据集，RLPP算法找到一个可供选择的 oretic approach for the generation of alternative clusterings 聚类结果共耗时2.7s。以上运行时间均为运行10 [C]//Proceedings of the IEEE International Conference on Data Mining.Sydney,Australia,2010:521-530 次试验的平均时间。 [10]COVER T M,THOMAS J A.Elements of information theo- 上述运行时间表明本文算法在合适的数据集上 ry[M].Chichester:John Wiley Sons,2012. 是完全适用的，但是在数据集规模很大的情况下，仍 [11]KAPUR J N.Measures of information and their applica- 存有改进的空间。 tions[M].New York:Wiley-Interscience,1994
同等重要的聚类结果。 从图中可以看出，ＲＬＰＰ 和 ＲＰＣＡ 的聚类效果最好，ＲｅｇＧＢ 稍差。 表 ４ 是这 ３ 种算法的对比。 表 ４ ＣＭＵＦａｃｅ 数据集上 ３ 种算法的表现 Ｔａｂｌｅ ４ Ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ａｌｌ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ＣＭ⁃ ＵＦａｃｅ ｄａｔａ 算法 ＮＭＩ ＪＩ Ｆ ＲＰＣＡ ０．０１２ ４ ０．２９４ １ ０．７１３ ９ ＲｅｇＧＢ ０．６６９ ０ ０．４４４ ４ ０．７５１ ２ ＲＬＰＰ ０．０７６ ６ ０．２１５ １ ０．７０２ １ 图 ３ ＣＭＵＦａｃｅ 数据集上的运行结果 Ｆｉｇ．３ Ｒｅｓｕｌｔｓ ｏｎ ＣＭＵＦａｃｅ ｄａｔａ ６．５ 算法运行时间 实验均在 ＭＡＲＴＬＡＢ ８．１．０．６０４（Ｒ２０１３ａ）平台下 完成，操作系统为 ６４ 位 Ｗｉｎｄｏｗｓ７，ＣＰＵ 为 Ｉｎｔｅｌ（Ｒ） Ｃｏｒｅ（ＴＭ） ｉ３⁃３２４０ ３．４０Ｇ Ｈｚ，内存为 ４ ＧＢ。 对于人工数据集 Ｓｙｎ１ 和 Ｓｙｎ２，ＲＬＰＰ 算法发掘 出一个可供选择的聚类结果分别耗时 ３．４ ｓ 和２．９ ｓ。 对于 Ｅｓｈｅｒ 图，由于聚类之前需要进行图像一维化 处理，因此数据集的维数很大，共耗时 １３６ ｓ。 对于 ＣＭＵＦａｃｅ 数据集，ＲＬＰＰ 算法找到一个可供选择的 聚类结果共耗时 ２．７ ｓ。 以上运行时间均为运行 １０ 次试验的平均时间。 上述运行时间表明本文算法在合适的数据集上 是完全适用的，但是在数据集规模很大的情况下，仍 存有改进的空间。 ７ 结束语 本文提出了一种新的算法 ＲＬＰＰ，采用子空间流 形学习技术，寻找可供选择的聚类结果。 ＲＬＰＰ 算 法的优势在于最终能够转化为特征分解问题，也就 是说可以找到封闭解，并且子空间一定是全局最优 的，这也是本文区别于其他相关研究的重要特点之 一。 在文章中对 ＲＬＰＰ 算法进行了论证和实验，并 对比了目前效果最好的著名算法。 实验结果表明 ＲＬＰＰ 算法的性能不输于甚至优于其他算法。 对于 如何更好地选取最小特征值的个数 ｋ，以及如何降 低算法在处理维数较大数据时的时间复杂度，都是 继续研究的方向。 参考文献： ［１］ＤＡＮＧ Ｘｕａｎｈｏｎｇ， ＢＡＩＬＥＹ Ｊ． Ｇｅｎｅｒａｔｉｎｇ ｍｕｌｔｉｐｌｅ ａｌｔｅｒｎａ⁃ ｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｖｉａ ｇｌｏｂａｌｌｙ ｏｐｔｉｍａｌ ｓｕｂｓｐａｃｅｓ ［ Ｊ ］． Ｄａｔａ ｍｉｎｉｎｇ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｄｉｓｃｏｖｅｒｙ， ２０１４， ２８（３）： ５６９⁃５９２． ［２］ＧＲＥＴＴＯＮ Ａ， ＢＯＵＳＱＵＥＴ Ｏ， ＳＭＯＬＡ Ａ， ｅｔ ａｌ． Ｍｅａｓｕｒｉｎｇ ｓｔａｔｉｓｔｉｃａｌ ｄｅｐｅｎｄｅｎｃｅ ｗｉｔｈ Ｈｉｌｂｅｒｔ⁃Ｓｃｈｍｉｄｔ ｎｏｒｍｓ ［ Ｍ］ ／ ／ ＪＡＩＮ Ｓ， ＳＩＭＯＮ Ｈ Ｕ， ＴＯＭＩＴＡ Ｅ． Ａｌｇｏｒｉｔｈｍｉｃ Ｌｅａｒｎｉｎｇ Ｔｈｅｏｒｙ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００５： ６３⁃７７． ［ ３ ］ ＨＥ Ｘｉａｏｆｅｉ， ＮＩＹＯＧＩ Ｘ． Ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ ［Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， ２００３， １６： １５３⁃１６０． ［４］ＢＡＥ Ｅ， ＢＡＩＬＥＹ Ｊ． ＣＯＡＬＡ： ａ ｎｏｖｅｌ ａｐｐｒｏａｃｈ ｆｏｒ ｔｈｅ ｅｘ⁃ ｔｒａｃｔｉｏｎ ｏｆ ａｎ ａｌｔｅｒｎａｔｅ ｃｌｕｓｔｅｒｉｎｇ ｏｆ ｈｉｇｈ ｑｕａｌｉｔｙ ａｎｄ ｈｉｇｈ ｄｉｓｓｉｍｉｌａｒｉｔｙ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ． Ｈｏｎｇ Ｋｏｎｇ， Ｃｈｉｎａ， ２００６： ５３⁃６２． ［５］ＧＯＮＤＥＫ Ｄ， ＨＯＦＭＡＮＮ Ｔ． Ｎｏｎ⁃ｒｅｄｕｎｄａｎｔ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ， ２００７， １２（１）： １⁃ ２４． ［６］ ＪＡＩＮ Ｐ， ＭＥＫＡ Ｒ， ＤＨＩＬＬＯＮ Ｉ Ｓ． Ｓｉｍｕｌｔａｎｅｏｕｓ ｕｎｓｕｐｅｒ⁃ ｖｉｓｅｄ ｌｅａｒｎｉｎｇ ｏｆ ｄｉｓｐａｒａｔｅ ｃｌｕｓｔｅｒｉｎｇｓ［ Ｊ］． Ｓｔａｔｉｓｔｉｃａｌ ａｎａｌｙ⁃ ｓｉｓ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ： ｔｈｅ ＡＳＡ ｄａｔａ ｓｃｉｅｎｃｅ ｊｏｕｒｎａｌ， ２００８， １ （３）： １９５⁃２１０． ［ ７ ］ ＤＡＮＧ Ｘｕａｎｈｏｎｇ， ＢＡＩＬＥＹ Ｊ． Ｇｅｎｅｒａｔｉｏｎ ｏｆ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕｓｉｎｇ ｔｈｅ ＣＡＭＩ ａｐｐｒｏａｃｈ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＡＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ， ＳＤＭ ２０１０． Ｃｏｌｕｍｂｕｓ， Ｏｈｉｏ， ＵＳＡ， ２０１０， １０： １１８⁃１２９． ［８］ ＤＡＮＧ Ｘｕａｎｈｏｎｇ， ＢＡＩＬＥＹ Ｊ． Ａ ｈｉｅｒａｒｃｈｉｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｅｔｉｃ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ｔｈｅ ｄｉｓｃｏｖｅｒｙ ｏｆ ｎｏｎ ｌｉｎｅａｒ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １６ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｗａｓｈｉｎｇｔｏｎ， ＤＣ， ＵＳＡ， ２０１０： ５７３⁃５８２． ［９］ＶＩＮＨ Ｎ Ｘ， ＥＰＰＳ Ｊ． ＭｉｎＣＥｎｔｒｏｐｙ： ａ ｎｏｖｅｌ ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅ⁃ ｏｒｅｔｉｃ ａｐｐｒｏａｃｈ ｆｏｒ ｔｈｅ ｇｅｎｅｒａｔｉｏｎ ｏｆ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ． Ｓｙｄｎｅｙ， Ａｕｓｔｒａｌｉａ， ２０１０： ５２１⁃５３０． ［１０］ＣＯＶＥＲ Ｔ Ｍ， ＴＨＯＭＡＳ Ｊ Ａ． Ｅｌｅｍｅｎｔｓ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏ⁃ ｒｙ［Ｍ］． Ｃｈｉｃｈｅｓｔｅｒ： Ｊｏｈｎ Ｗｉｌｅｙ ＆ Ｓｏｎｓ， ２０１２． ［１１］ ＫＡＰＵＲ Ｊ Ｎ． Ｍｅａｓｕｒｅｓ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｔｈｅｉｒ ａｐｐｌｉｃａ⁃ ｔｉｏｎｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｗｉｌｅｙ⁃Ｉｎｔｅｒｓｃｉｅｎｃｅ， １９９４． ·６０６· 智 能 系 统 学 报 第 １１ 卷
第5期 程肠，等：基于局部保留投影的多可选聚类发掘算法 ·607· [12]PRINCIPE J C,XU D,FISHER J.Information theoretic [18]NIU Donglin,DY J G,JORDAN M I.Multiple non-redun- learning[M]//HAYKIN S.Unsupervised Adaptive Filte- dant spectral clustering views C]//Proceedings of the ring.New York:Wiley,2000,1:265-319. 27th International Conference on Machine Learning.Haifa, [13]PARZEN E.On estimation of a probability density function Israel.2010:831-838 and mode J].The annals of mathematical statistics, 作者简介： 1962,33(3):1065-1076. 程肠，男，1991年生，硕士研究生 [14]CUI Ying,FERN X Z,DY J G.Non-redundant multi-view 主要研究方向为人工智能与模式识别、 clustering via orthogonalization [C]//Proceedings of the 数据挖掘。 7th IEEE International Conference on Data Mining.Oma- ha,Nebraska,USA,2007:133-142. [15]DAVIDSON I,QI Zijie.Finding alternative clusterings u- sing constraints[C]//Proceedings of the 8th IEEE Interna- tional Conference on Data Mining.Pisa,Italy,2008:773- 778. 王士同，男，1964年生，教授，博士 [16]QI Zijie,DAVIDSON I.A principled and flexible frame- 生导师，中国离散数学学会常务理事， work for finding alternative clusterings [C]//Proceedings 中国机器学习学会常务理事。主要研 of the 15th ACM SIGKDD International Conference on 究方向为人工智能、模式识别和图像处 Knowledge Discovery and Data Mining.Paris,France, 理。发表学术论文近百篇，其中被SC、 2009:717-726. EI检索50余篇。 [17]DASGUPTA S,NG V.Mining clustering dimensions [C]//Proceedings of the 27th International Conference on Machine Learning.Haifa,Israel,2010:263-270. 第2届物联网，大数据和安全国际会议 2nd International Conference on Internet of Things, Big Data and Security 24-26 April,2017,Porto,Portugal Internet of Things(IoT)is a platform and a phenomenon that allows everything to process information,commu- nicate data,analyze context collaboratively and in the service or individuals,organizations and businesses.In the process of doing so,a large amount of data with different formats and content has to be processed efficiently,quick- ly and intelligently through advanced algorithms,techniques,models and tools.This new paradigm is enabled by the maturity of several different technologies,including the internet,wireless communication,cloud computing, sensors,big data analytics and machine learning algorithms. Big Data is another paradigm to describe processing of data to make it make sense'to people using loT.Big Data has five characteristics:volume,velocity,variety,veracity and value.There are reports that businesses and research communities equipped with Big Data skills can provide additional incentives,opportunities,funding and innovation to their long-term strategies.The new knowledge,tools,practices,and infrastructures produced will en- able breakthrough discoveries and innovation in physical science,engineering,mobile services,medicine,busi- ness,education,earth science,security and risk analysis.For organizations that adopt Big Data,the boundary be- tween the use of private clouds,public clouds,IoT is sometimes very thin to allow better access,performance and efficiency of analyzing the data and understanding the data analysis.A common approach is to develop Big Data in the loT to deliver "Everything as a Service".In the process of doing so,innovative services known as "Emerging Services and Analytics"can be the highlight and strategic solutions to organizations adopting IoT and Big Data. Website:http://www.iotbd.org/?y=2017
［１２］ＰＲＩＮＣＩＰＥ Ｊ Ｃ， ＸＵ Ｄ， ＦＩＳＨＥＲ Ｊ． Ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｅｔｉｃ ｌｅａｒｎｉｎｇ［ Ｍ］ ／ ／ ＨＡＹＫＩＮ Ｓ． Ｕｎｓｕｐｅｒｖｉｓｅｄ Ａｄａｐｔｉｖｅ Ｆｉｌｔｅ⁃ ｒｉｎｇ． Ｎｅｗ Ｙｏｒｋ： Ｗｉｌｅｙ， ２０００， １： ２６５⁃３１９． ［１３］ＰＡＲＺＥＮ Ｅ． Ｏｎ ｅｓｔｉｍａｔｉｏｎ ｏｆ ａ ｐｒｏｂａｂｉｌｉｔｙ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ｍｏｄｅ ［ Ｊ ］． Ｔｈｅ ａｎｎａｌｓ ｏｆ ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓｔｉｃｓ， １９６２， ３３（３）： １０６５⁃１０７６． ［１４］ＣＵＩ Ｙｉｎｇ， ＦＥＲＮ Ｘ Ｚ， ＤＹ Ｊ Ｇ． Ｎｏｎ⁃ｒｅｄｕｎｄａｎｔ ｍｕｌｔｉ⁃ｖｉｅｗ ｃｌｕｓｔｅｒｉｎｇ ｖｉａ ｏｒｔｈｏｇｏｎａｌｉｚａｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ． Ｏｍａ⁃ ｈａ， Ｎｅｂｒａｓｋａ， ＵＳＡ， ２００７： １３３⁃１４２． ［１５］ＤＡＶＩＤＳＯＮ Ｉ， ＱＩ Ｚｉｊｉｅ． Ｆｉｎｄｉｎｇ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕ⁃ ｓｉｎｇ ｃｏｎｓｔｒａｉｎｔｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ． Ｐｉｓａ， Ｉｔａｌｙ， ２００８： ７７３⁃ ７７８． ［１６］ＱＩ Ｚｉｊｉｅ， ＤＡＶＩＤＳＯＮ Ｉ． Ａ ｐｒｉｎｃｉｐｌｅｄ ａｎｄ ｆｌｅｘｉｂｌｅ ｆｒａｍｅ⁃ ｗｏｒｋ ｆｏｒ ｆｉｎｄｉｎｇ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １５ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｐａｒｉｓ， Ｆｒａｎｃｅ， ２００９： ７１７⁃７２６． ［ １７ ］ ＤＡＳＧＵＰＴＡ Ｓ， ＮＧ Ｖ． Ｍｉｎｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ｄｉｍｅｎｓｉｏｎｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｈａｉｆａ， Ｉｓｒａｅｌ， ２０１０： ２６３⁃２７０． ［１８］ＮＩＵ Ｄｏｎｇｌｉｎ， ＤＹ Ｊ Ｇ， ＪＯＲＤＡＮ Ｍ Ｉ． Ｍｕｌｔｉｐｌｅ ｎｏｎ⁃ｒｅｄｕｎ⁃ ｄａｎｔ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ ｖｉｅｗｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｈａｉｆａ， Ｉｓｒａｅｌ， ２０１０： ８３１⁃８３８． 作者简介： 程旸，男，１９９１ 年生，硕士研究生， 主要研究方向为人工智能与模式识别、 数据挖掘。 王士同，男，１９６４ 年生，教授，博士 生导师，中国离散数学学会常务理事， 中国机器学习学会常务理事。 主要研 究方向为人工智能、模式识别和图像处 理。 发表学术论文近百篇，其中被 ＳＣＩ、 ＥＩ 检索 ５０ 余篇。 第 ２ 届物联网，大数据和安全国际会议 ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ， Ｂｉｇ Ｄａｔａ ａｎｄ Ｓｅｃｕｒｉｔｙ ２４－２６ Ａｐｒｉｌ， ２０１７， Ｐｏｒｔｏ， Ｐｏｒｔｕｇａｌ Ｉｎｔｅｒｎｅｔ ｏｆ Ｔｈｉｎｇｓ （ＩｏＴ） ｉｓ ａ ｐｌａｔｆｏｒｍ ａｎｄ ａ ｐｈｅｎｏｍｅｎｏｎ ｔｈａｔ ａｌｌｏｗｓ ｅｖｅｒｙｔｈｉｎｇ ｔｏ ｐｒｏｃｅｓｓ ｉｎｆｏｒｍａｔｉｏｎ， ｃｏｍｍｕ⁃ ｎｉｃａｔｅ ｄａｔａ， ａｎａｌｙｚｅ ｃｏｎｔｅｘｔ ｃｏｌｌａｂｏｒａｔｉｖｅｌｙ ａｎｄ ｉｎ ｔｈｅ ｓｅｒｖｉｃｅ ｏｒ ｉｎｄｉｖｉｄｕａｌｓ， ｏｒｇａｎｉｚａｔｉｏｎｓ ａｎｄ ｂｕｓｉｎｅｓｓｅｓ． Ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｄｏｉｎｇ ｓｏ， ａ ｌａｒｇｅ ａｍｏｕｎｔ ｏｆ ｄａｔａ ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｆｏｒｍａｔｓ ａｎｄ ｃｏｎｔｅｎｔ ｈａｓ ｔｏ ｂｅ ｐｒｏｃｅｓｓｅｄ ｅｆｆｉｃｉｅｎｔｌｙ， ｑｕｉｃｋ⁃ ｌｙ ａｎｄ ｉｎｔｅｌｌｉｇｅｎｔｌｙ ｔｈｒｏｕｇｈ ａｄｖａｎｃｅｄ ａｌｇｏｒｉｔｈｍｓ， ｔｅｃｈｎｉｑｕｅｓ， ｍｏｄｅｌｓ ａｎｄ ｔｏｏｌｓ． Ｔｈｉｓ ｎｅｗ ｐａｒａｄｉｇｍ ｉｓ ｅｎａｂｌｅｄ ｂｙ ｔｈｅ ｍａｔｕｒｉｔｙ ｏｆ ｓｅｖｅｒａｌ ｄｉｆｆｅｒｅｎｔ ｔｅｃｈｎｏｌｏｇｉｅｓ， ｉｎｃｌｕｄｉｎｇ ｔｈｅ ｉｎｔｅｒｎｅｔ， ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎｉｃａｔｉｏｎ， ｃｌｏｕｄ ｃｏｍｐｕｔｉｎｇ， ｓｅｎｓｏｒｓ， ｂｉｇ ｄａｔａ ａｎａｌｙｔｉｃｓ ａｎｄ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ． Ｂｉｇ Ｄａｔａ ｉｓ ａｎｏｔｈｅｒ ｐａｒａｄｉｇｍ ｔｏ ｄｅｓｃｒｉｂｅ ｐｒｏｃｅｓｓｉｎｇ ｏｆ ｄａｔａ ｔｏ ｍａｋｅ ｉｔ ‘ｍａｋｅ ｓｅｎｓｅ’ ｔｏ ｐｅｏｐｌｅ ｕｓｉｎｇ ＩｏＴ． Ｂｉｇ Ｄａｔａ ｈａｓ ｆｉｖｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ： ｖｏｌｕｍｅ， ｖｅｌｏｃｉｔｙ， ｖａｒｉｅｔｙ， ｖｅｒａｃｉｔｙ ａｎｄ ｖａｌｕｅ． Ｔｈｅｒｅ ａｒｅ ｒｅｐｏｒｔｓ ｔｈａｔ ｂｕｓｉｎｅｓｓｅｓ ａｎｄ ｒｅｓｅａｒｃｈ ｃｏｍｍｕｎｉｔｉｅｓ ｅｑｕｉｐｐｅｄ ｗｉｔｈ Ｂｉｇ Ｄａｔａ ｓｋｉｌｌｓ ｃａｎ ｐｒｏｖｉｄｅ ａｄｄｉｔｉｏｎａｌ ｉｎｃｅｎｔｉｖｅｓ， ｏｐｐｏｒｔｕｎｉｔｉｅｓ， ｆｕｎｄｉｎｇ ａｎｄ ｉｎｎｏｖａｔｉｏｎ ｔｏ ｔｈｅｉｒ ｌｏｎｇ－ｔｅｒｍ ｓｔｒａｔｅｇｉｅｓ． Ｔｈｅ ｎｅｗ ｋｎｏｗｌｅｄｇｅ， ｔｏｏｌｓ， ｐｒａｃｔｉｃｅｓ， ａｎｄ ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ ｐｒｏｄｕｃｅｄ ｗｉｌｌ ｅｎ⁃ ａｂｌｅ ｂｒｅａｋｔｈｒｏｕｇｈ ｄｉｓｃｏｖｅｒｉｅｓ ａｎｄ ｉｎｎｏｖａｔｉｏｎ ｉｎ ｐｈｙｓｉｃａｌ ｓｃｉｅｎｃｅ， ｅｎｇｉｎｅｅｒｉｎｇ， ｍｏｂｉｌｅ ｓｅｒｖｉｃｅｓ， ｍｅｄｉｃｉｎｅ， ｂｕｓｉ⁃ ｎｅｓｓ， ｅｄｕｃａｔｉｏｎ， ｅａｒｔｈ ｓｃｉｅｎｃｅ， ｓｅｃｕｒｉｔｙ ａｎｄ ｒｉｓｋ ａｎａｌｙｓｉｓ． Ｆｏｒ ｏｒｇａｎｉｚａｔｉｏｎｓ ｔｈａｔ ａｄｏｐｔ Ｂｉｇ Ｄａｔａ， ｔｈｅ ｂｏｕｎｄａｒｙ ｂｅ⁃ ｔｗｅｅｎ ｔｈｅ ｕｓｅ ｏｆ ｐｒｉｖａｔｅ ｃｌｏｕｄｓ， ｐｕｂｌｉｃ ｃｌｏｕｄｓ， ＩｏＴ ｉｓ ｓｏｍｅｔｉｍｅｓ ｖｅｒｙ ｔｈｉｎ ｔｏ ａｌｌｏｗ ｂｅｔｔｅｒ ａｃｃｅｓｓ， ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ａｎａｌｙｚｉｎｇ ｔｈｅ ｄａｔａ ａｎｄ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｔｈｅ ｄａｔａ ａｎａｌｙｓｉｓ． Ａ ｃｏｍｍｏｎ ａｐｐｒｏａｃｈ ｉｓ ｔｏ ｄｅｖｅｌｏｐ Ｂｉｇ Ｄａｔａ ｉｎ ｔｈｅ ＩｏＴ ｔｏ ｄｅｌｉｖｅｒ “Ｅｖｅｒｙｔｈｉｎｇ ａｓ ａ Ｓｅｒｖｉｃｅ”． Ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｄｏｉｎｇ ｓｏ， ｉｎｎｏｖａｔｉｖｅ ｓｅｒｖｉｃｅｓ ｋｎｏｗｎ ａｓ “Ｅｍｅｒｇｉｎｇ Ｓｅｒｖｉｃｅｓ ａｎｄ Ａｎａｌｙｔｉｃｓ” ｃａｎ ｂｅ ｔｈｅ ｈｉｇｈｌｉｇｈｔ ａｎｄ ｓｔｒａｔｅｇｉｃ ｓｏｌｕｔｉｏｎｓ ｔｏ ｏｒｇａｎｉｚａｔｉｏｎｓ ａｄｏｐｔｉｎｇ ＩｏＴ ａｎｄ Ｂｉｇ Ｄａｔａ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ： ／ ／ ｗｗｗ．ｉｏｔｂｄ．ｏｒｇ ／ ？ ｙ ＝ ２０１７ 第 ５ 期 程旸，等：基于局部保留投影的多可选聚类发掘算法 ·６０７·