第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 标函数最终在特征分解问题的框架内求解，因此能第 １１ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．５ ２０１６ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０８０２２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８２４．０９２８．００４．ｈｔｍｌ 基于局部保留投影的多可选聚类发掘算法 程旸，王士同 （江南大学 数字媒体学院，江苏 无锡 ２１４１２２） 摘 要：绝大多数的聚类分析算法仅能得到单一的聚类结果，考虑到数据的复杂程度普遍较高，以及看待数据的视 角不同，所得到的聚类结果在保证其合理性的基础上应当是不唯一的，针对此问题，提出了一个新的算法 ＲＬＰＰ，用 于发掘多种可供选择的聚类结果。 ＲＬＰＰ 的目标函数兼顾了聚类质量和相异性两大要素，采用子空间流形学习技 术，通过新的子空间不断生成多种互不相同的聚类结果。 ＲＬＰＰ 同时适用于线性以及非线性的数据集。 实验表明， ＲＬＰＰ 成功地发掘了多种可供选择的聚类结果，其性能相当或优于现有的算法。 关键词：可供选择的聚类结果；无监督学习；流形学习；多聚类；特征分解 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０５⁃０６００⁃０８ 中文引用格式：程旸，王士同．基于局部保留投影的多可选聚类发掘算法［Ｊ］． 智能系统学报， ２０１６， １１（５）： ６００⁃６０７． 英文引用格式：ＣＨＥＮＧ Ｙａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ａ ｍｕｌｔｉｐｌｅ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃ⁃ ｔｉｏｎｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（５）： ６００⁃６０７． Ａ ｍｕｌｔｉｐｌｅ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ ＣＨＥＮＧ Ｙａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｍｏｓｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｔｙｐｉｃａｌｌｙ ｆｉｎｄ ｊｕｓｔ ｏｎｅ ｓｉｎｇｌｅ ｒｅｓｕｌｔ ｆｏｒ ｔｈｅ ｄａｔａ ｉｎｐｕｔｔｅｄ． Ｃｏｎｓｉｄｅｒｉｎｇ ｔｈａｔ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｄａｔａ ｉｓ ｇｅｎｅｒａｌｌｙ ｈｉｇｈ， ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｎｅｅｄ ｔｏ ａｌｌｏｗ ｔｈｅ ｄａｔａ ｔｏ ｂｅ ｖｉｅｗｅｄ ｆｒｏｍ ｄｉｆｆｅｒｅｎｔ ｐｅｒ⁃ ｓｐｅｃｔｉｖｅｓ （ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｅｎｓｕｒｉｎｇ ｒｅａｓｏｎａｂｌｅｎｅｓｓ）， ｍｅａｎｓ ｔｈａｔ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ａｒｅ ｏｆｔｅｎ ｎｏｔ ｕｎｉｑｕｅ． Ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ＲＬＰＰ ｆｏｒ ａｎ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ｇｅｎｅｒａｔｉｏｎ ｍｅｔｈｏｄ． Ｔｈｅ ｏｂｊｅｃｔｉｖｅ ｏｆ ＲＬＰＰ ｉｓ ｔｏ ｆｉｎｄ ａ ｂａｌａｎｃｅ ｂｅｔｗｅｅｎ ｃｌｕｓｔｅｒｉｎｇ ｑｕａｌｉｔｙ ａｎｄ ｄｉｓｓｉｍｉｌａｒｉｔｙ ｕｓｉｎｇ ａ ｓｕｂｓｐａｃｅ ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ ｔｅｃｈｎｉｑｕｅ ｉｎ ａ ｎｅｗ ｓｕｂｓｐａｃｅ ｓｏ ｔｈａｔ ａ ｖａｒｉｅｔｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ ｃａｎ ｂｅ ｇｅｎｅｒａｔｅｄ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｕｓｉｎｇ ｂｏｔｈ ｌｉｎｅａｒ ａｎｄ ｎｏｎｌｉｎｅａｒ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈａｔ ＲＬＰＰ ｓｕｃｃｅｓｓｆｕｌｌｙ ｐｒｏｖｉｄｅｓ ａ ｖａｒｉｅｔｙ ｏｆ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ｒｅｓｕｌｔｓ， ａｎｄ ｉｓ ａｂｌｅ ｔｏ ｏｕｔｐｅｒｆｏｒｍ ｏｒ ａｔ ｌｅａｓｔ ｍａｔｃｈ ａ ｒａｎｇｅ ｏｆ ｅｘｉｓｔｉｎｇ ｍｅｔｈｏｄｓ． Ｋｅｙｗｏｒｄｓ：ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ； ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ； ｍａｎｉｆｏｌｄ ｌｅａｒｎｉｎｇ； ｍｕｌｔｉｐｌｅ ｃｌｕｓｔｅｒｉｎｇｓ； ｅｉｇｅｎｄｅｃｏｍｐｏｓｉ⁃ ｔｉｏｎ 收稿日期：２０１５⁃０８⁃２６． 网络出版日期：２０１６⁃０８⁃２４． 基金项目：国家自然科学基金项目（６１２７２２１０）． 通信作者：程旸． Ｅ⁃ｍａｉｌ：ｓｚｈｃｈｅｎｇｙａｎｇ＠ １６３．ｃｏｍ． 大多数传统的聚类算法仅仅能得到单个结果， 但是当对复杂数据进行聚类分析时，很可能存在多 个具有合理性的聚类结果。 这一特点在高维数据上 表现得尤为明显，例如文本、图像、基因数据等，这些 数据具有多种特征，而不同的特征子空间往往会得 到完全不同的聚类结果，同时每一种结果都能体现 数据不同的结构信息。 本文根据文献［１］所述原理，提出了一种能够发 掘多个可供选择的聚类结果的算法 ＲＬＰＰ。 算法结 合了 希 尔 伯 特 施 密 特 独 立 性 度 量 准 则 （ ｈｉｌｂｅｒｔ⁃ ｓｃｈｍｉｄｔ ｉｎｄｅｐｅｎｄｅｎｃｅ ｃｒｉｔｅｒｉｏｎ，ＨＳＩＣ） ［２］ 以及局部保 持投影（ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ，ＬＰＰ） ［３］ ，改进 了 ＬＰＰ 算法学习子空间的过程。 由于 ＨＳＩＣ 可以高 效地评估不同随机变量之间的依赖性，而 ＬＰＰ 算法 具有流形学习能力，因此 ＲＬＰＰ 同时兼顾了聚类结 果的相异性和聚类质量这两大要素。 并且由于其目 标函数最终在特征分解问题的框架内求解，因此能