基于成对约束的判别型半监督聚类分析

ＩＳＳＮ　１０００－９８２５，ＣＯＤＥＮ　ＲＵＸＵＥＷ　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８，ＰＰ．２７９１—２８０２　ＤｏＩ：１０．３７２４／Ｓ　Ｊ．１００１．２００８．０２７９１　Ｅ—ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｃｎ　ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃａ　Ｔｅｌ／Ｆａｘ：＋８６．１０．６２５６２５６３　＠２００８　ｂｙ　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ．Ａｌｌ　ｒｉｇｈｔｓ　ｒｅｓｅｒｖｅｄ．　木　基于成对约束的判别型半监督聚类分析　尹学松　，一，胡思良　，陈松灿　（南京航空航天大学信息科学与技术学院，江苏南京（浙江广播电视大学计算机科学与技术系，浙江杭州２１００１６）　３１００１２）　Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　Ｓｅｍｉ—Ｓｕｐｅｒｖｉｓｅｄ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｎａｌｙｓｉｓ　ｗｉｔｈ　Ｐａｉｒｗｉｓｅ　Ｃｏｎｓｔｒａｉｎｔｓ　ＹＩＮ　Ｘｕｅ　Ｓｏｎｇ‘　，ＨＵ　Ｅｎ．Ｌｉａｎｇ　，ＣＨＥＮ　Ｓｏｎｇ—Ｃａｎ　（Ｃｏｌｌｅｇｅ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＡｅｒｏｎａｕｔｉｃｓ＆Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ　２１００１６，Ｃｈｉｎａ）　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｊｉａｎｇ　Ｒａｄｉｏ＆ＴＶ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ　３１００１２，Ｃｈｉｎａ）　＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ａｕｔｈｏｒ：Ｅ—ｍａｉｌ：ｓ．ｃｈｅｎ＠ｎｕａａ．ｅｄｕ．ｃｎ　Ｙｉｎ　ＸＳ，Ｈｕ　ＥＬ，Ｃｈｅｎ　ＳＣ．Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｓｅｍｉ－ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　ｗｉｔｈ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ．　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２００８，１９（１１）：２７９１～２８０２．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｒｄｌＯ００－９８２５／１９／２７９１．ｈｔｍ　Ａｂｓｔｒａｃｔ：Ｍｏｓｔ　ｅｘｉｓｔｉｎｇ　ｓｅｍｉ－ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｗｉｔｈ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｎｅｉｔｈｅｒ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｖｉｏｌａｔｉｏｎ　ｏｆ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｅｆｆｅｃｔｉｖｅｌｙ，ｎｏｒ　ｈａｎｄｌｅ　ｔｈｅ　ｈｉｇｈ—ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ，ｃａｌｌｅｄ　ＤＳＣＡ，　ｗｈｉｃｈ　ｅｆｆｅｃｔｉｖｅｌｙ　ｕｔｉｌｉｚｅｓ　ｓｕｐｅｒｖｉｓｅｄ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｏ　ｉｎｔｅｇｒａｔｅ　ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　ｒｅｄｕｃｔｉｏｎ　ａｎｄ　ｃｌｕｓｔｅｒｉｎｇ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｊｅｃｔｓ　ｔｈｅ　ｄａｔａ　ｏｎｔｏ　ａ　ｌｏｗ－ｄｉｍｅｎｓｉｏｎａｌ　ｍａｎｉｆｏｌｄ，ｗｈｅｒｅ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｂａｓｅｄ　Ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ　ｕｓｅｄ　ｔｏ　ｃｌｕｓｔｅｒ　ｔｈｅ　ｄａｔａ．Ｍｅａｎｗｈｉｌｅ，ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｂａｓｅｄ　Ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｐｒｅｓｅｎｔｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｒｅｄｕｃｅｓ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｃｏｎｓｔｒａｉｎｔｓ　ｂａｓｅｄ　ｓｅｍｉ－ｓｕｐｅｒｖｉｓｅｄ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｒｅｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｖｉｏｌａｔｉｎｇ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｉｎ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｏｎ　ｒｅａｌ・－ｗｏｒｌｄ　ｄａｔａｓｅｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｅｆｆｅｃｔｉｖｅｌｙ　ｄｅａｌ　ｗｉｔｈ　ｈｉｇｈ－・ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ａｎｄ　ｐｒｏｖｉｄｅ　ａｎ　ａｐｐｅａｌｉｎｇ　ｃｌｕｓｔｅｒｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｓｔａｔｅ－ｏｆ－ｔｈｅ－ａｒｔ　ｓｅｍｉ－ｓｕｐｅｒｖｉｓｅｄ　ａｌｇｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ；ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ；ｃｌｏｓｕｒｅ　ｃｅｎｔｒｏｉｄ；ｐｒｏｊｅｃｔｉｏｎ　ｍａｔｒｉｘ；ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　摘要：　现有一些典型的半监督聚类方法一方面难以有效地解决成对约束的违反问题，另一方面未能同时处理高　维数据．通过提出一种基于成对约束的判别型半监督聚类分析方法来同时解决上述问题．该方法有效地利用了监督　信息集成数据降维和聚类，即在投影空间中使用基于成对约束的　均值算法对数据聚类，再利用聚类结果选择投影　空间．同时，该算法降低了基于约束的半监督聚类算法的计算复杂度，并解决了聚类过程中成对约束的违反问题．在　一组真实数据集上的实验结果表明，与现有相关半监督聚类算法相比，新方法不仅能够处理高维数据，还有效地提高　了聚类性能．　关键词：　半监督聚类；成对约束；闭包中心：投影矩阵：聚类分析　・Ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆＣｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏｓ．６０５０５００４，６０７７３０６１（国家自然科学基金）　Ｒｅｃｅｉｖｅｄ　２００８・０１－０８；Ａｃｃｅｐｔｅｄ　２００８—０８—２６　２７９２　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８　中图法分类号：ＴＰ１８１　文献标识码：Ａ　在机器学习和数据挖掘领域中，人们经常遇到大量的无类标号数据．对这些无标号数据进行标号时．不仅费　时、费力，有时甚至要付出相当大的代价，如会谈中说话人语音的分割与识别【”、ＧＰＳ数据中的道路检测［　］以及　电影片段中不同男演员或女演员的分组【３］等问题．因此，利用样本的先验知识来解决这一问题已成为机器学习　领域的研究热点［２－１０］．半监督聚类正是利用样本的先验信息或背景知识，通过充分利用无标号数据来完成对样　本数据的聚类．它也能自然地应用于无监督聚类算法，以达到提高无监督聚类性能的目的，故已开始成为机器学　习和数据挖掘中的重要研究内容之一．　现有的半监督聚类算法大致可分为３类．第１类是基于约束的半监督聚类算法（ｃｏｎｓｔｒａｉｎｔ．ｂａｓｅｄ　ｓｅｍｉ．　ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ，简称ＣＢＳＳＣ）拉Ｉ４　’　Ｊ．这类算法一般使用ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束来引导聚　类过程．ｍｕｓｔ．１ｉｎｋ约束规定：如果两个样本属于ｍｕｓｔ．１ｉｎｋ约束，那么这两个样本在聚类时必须被分配到同一个聚　类中．ｃａｎｎｏｔ．１ｉｎｋ约束则相应地规定：如果两个样本属于ｃａｎｎｏｔ—ｌｉｎｋ约束，那么这两个样本在聚类时必须被分配　到不同聚类之中．第２类是基于距离的半监督聚类算法（ｄｉｓｔａｎｃｅ．ｂａｓｅｄ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ．简称　ＤＢＳＳＣ）［　”】．这类算法利用成对约束来学习距离度量，从而改变各样本之间的距离，使其有利于聚类．第３类是　集成了约束与距离的半监督聚类算法（ｃｏｎｓｔｒａｉｎｔ　ａｎｄ　ｄｉｓｔａｎｃｅ　ｂａｓｅｄ　ｓｅｍｉ．ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ。简称　ＣＤＢＳＳＣ）［ｂ　．＿它实际上是上述两类方法的组合．　以上３类算法尽管利用成对约束来指导聚类，但在求解过程中常常遇到成对约束的违反问题，因而聚类结　果并不十分令人满意．如ＤＢＳＳＣ通过利用ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束来学习一个距离函数，从而改变各　样本之间的距离，达到提升聚类性能的效果．但这类算法不能保证在改变样本间的距离后，ｍｕｓｔ．１ｉｎｋ点对总能被　分组到同一聚类之中，而ｃａｎｎｏｔ—ｌｉｎｋ点对则常有部分被分配到同一聚类之中，致使约束被违反．ＣＢＳＳＣ是在　均　值算法的目标函数中通过添加惩罚项来试图解决成对约束的违反问题，但选择合适的惩罚因子是这类算法面　临的难题，因此，这类算法仍未能有效地解决约束违反问题．作为前两类方法组合的ＣＢＳＳＣ继承了它们的不足，　因而同样未能实现对约束违反问题的有效解决．此外，这３类算法只适用于较低维数的样本数据．在遇到较高维　数的数据时，这些算法会显得力不从心，因为在高维数据空间中，不同数据分布和不同距离函数的样本点对之间　的距离几乎是相同的　，　Ｊ．　针对高维数据聚类问题，Ｔａｎｇ［８］等人提出了一种基于特征投影的半监督聚类算法，部分地解决了该问题，但　其不足是仅采用了ｍｕｓｔ—ｌｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束得到投影矩阵，而没有采用大量无标号样本数据，因此限制　了聚类性能的提高．　针对这些问题，本文提出一种基于成对约束的判别型半监督聚类分析方法（ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｓｅｍｉ．ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　ｗｉｔｈ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔｓ。简称ＤＳＣＡ）．该方法首先利用ｍｕｓｔ—ｌｉｎｋ和ｃａｎｎｏｔ．１ｉｋ成对约束得到　ｎ投影矩阵，在投影空间中对数据聚类得到聚类标号；其次，利用线性判别分析（１ｉｎｅａｒ　ｄｉｓｃｒｉｍｉｎａｎｔ　ａｎａｌｙｓｉｓ，简称　ＬＤＡ）选择子空问：最后，使用基于成对约束的　均值算法对子空问中的数据聚类．该方法有效地利用了监督信　息集成数据降维和聚类，即在投影空间中使用基于成对约束的　均值算法对数据聚类，再利用聚类结果选择投　影空间．同时。新方法提出的基于成对约束的　均值算法降低了基于约束的半监督聚类算法的计算复杂度，并解　决了聚类过程中成对约束的违反问题．　事实上，对数据聚类来说，得到聚类标号后，ＬＤＡ选择的线性子空间是最好的子空问，因为在ＬＤＡ子空间里，　各聚类之间能够被有效地分开［”】．因此，本文提出的算法利用ＬＤＡ来选择子空间，在子空间里使用新的基于成　对约束的　均值算法对数据聚类．新算法的贡献表现为以下３个方面：　（１）新算法将动态聚类方法引入半监督聚类之中，即聚类和降维同时进行．现有的半监督聚类方法要么只　关注监督信息对聚类的帮助［４－７，９，１０　而忽略了对数据的降维，要么分离了聚类与降维　１．新算法利用聚　类结果进行子空间选择，然后在子空间中完成数据聚类，两者交替迭代进行，有效地提高了聚类性能．　（２）新算法解决了成对约束的违反问题．ＣＢＳＳＣ在　均值算法的目标函数中加入惩罚项来限制违反　尹学松等：基于成对约束的判别型半监督聚类分析　２７９３　ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ约束的样本对［６，７，９，１０］；ＤＢＳＳＣ用监督信息去学习度量，进行聚类［３，５，１１】．通常，这样　处理并不能有效地解决ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ约束的违反问题．新算法借助ｍｕｓｔ．１ｉｎｋ成对约束的等　价关系，简化ｍｕｓｔ．１ｉｋ成对约束，ｎ构成新的ｃａｎｎｏｔ．１ｉｎｋ约束，并将其应用到　均值聚类之中，基本上解　决了ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ约束的违反问题．　（３）基于成对约束的　均值算法改进了ＣＢＳＳＣ．ＣＢＳＳＣ在　均值聚类的目标函数中添加惩罚项，构成新的　目标函数来解决约束的违反问题，但选择合适的惩罚因子是该算法面临的难题．因此，该方法不仅难以　有效地解决成对约束的违反问题，还增加了算法的计算复杂度．基于成对约束的　均值算法只是将　ｃａｎｎｏｔ．１ｉｎｋ成对约束运用到　均值聚类中，在保持　均值聚类计算复杂度的情况下，提高了聚类性能。　本文提出的算法不仅集成了投影空间选择与数据聚类，还努力架起一座连接原空间中样本和子空间中样　本的桥梁．通过该桥梁，可以在全局最优的子空间中对数据聚类，避免了维数灾难的发生．　１基于成对约束的判别型半监督聚类分析算法　基于成对约束的判别型半监督聚类分析算法的框图如图１所示．对于给定的样本集合　［　１　２，．．．　］，其中　Ｘ　∈吼　，ｍｕｓｔ—ｌｉｎｋ成对约束集合为＾　｛　啦）｝，ｃａｎｎｏｔ－ｌｉｎｋ成对约束集合为ｃ。＿｛　ｆ）｝．基于成对约束的判别型　半监督聚类分析算法由３步组成．首先是算法初始化，利用给定的ｍｕｓｔ．１ｉｋ和ｃａｎｎｏｔｎ．１ｉｎｋ成对约束集合得到一　个投影矩阵，在投影空间中对数据聚类得到聚类标号；其次，使用ＬＤＡ选择子空间；最后，利用基于成对约束的　均值算法对数据聚类．　Ｆｉｇ．１　Ｆｒａｍｅｗｏｒｋ　ｏｆ　ｔｈｅ　ＤＳＣＡ　ｍｅｔｈｏｄ　图ｌ　ＤＳＣＡ算法的框图　１．１初始化　在高维空间中，不同数据分布和不同距离函数的样本点对之间的距离几乎是相同的，因此，如果对样本聚　类，就有必要将高维数据投影到低维空间．设投影矩阵为　数据投影到一个低维空间：　＝ｒ＝［Ｗｌ…．，　】，它包含，个ｍ维正交单位向量，将原始　Ｗ　∈吼　，ｌ＜ｍ　（１）　投影矩阵不仅要在投影空间中尽可能地保持原始数据的结构，还要使ｃａｎｎｏｔ．１ｉｎｋ集合中的点对之间距离　最大化、ｍｕｓｔ－ｌｉｎｋ集合中的点对之间距离最小化．因此，定义一个目标函数‘，（　，并相对　最大化其值来求取投　影矩阵　４］：　２７９４　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８　（　羽１　ｌ　Ｉ－．　南　象肼　一　ｌｌ。　【南　募　（薯一　一　）Ｌ羽１　丢　（　一　一　）　＝‘２）　∑　ＤＷ，　其中，ｌＣｌ和ｌＭ１分别表示ｃａｎｎｏｔ．１ｉｎｋ和ｍｕｓｔ－ｌｉｎｋ成对约束中的点对数．　Ｄ：南　。（　（　Ｌ南　象　（　（　ｆ１　ｉｆ　ｉ：，　。ｔｈ。　ｉ　。‘　通过最大化式（２）可以得到最优的投影矩阵　不难发现，由于目标和约束所具有的凸性，我们能够获得　的　解析解．因此，利用ＫＴ定理，定义如下Ｌａｇｒａｎｇｅ函数：　Ｌ（ｒＶ）＝　（　，　，．．．，ｗ３－∑　（　一１）　相对　求　（ｅ，９的偏导，得到：　＝２Ｄ　一２　＝０，Ｖｉ＝１，．．．，，　（３）　ａ　Ｄ　＝　，Ｖｉ：ｌ，．．．，，　（４）　显然，由方程式（４）可以解出最优的投影矩阵　严【　，．．．，　就是由矩阵Ｄ的ｆ个最大特征值所对应的特征　向量组成．进而可以利用式（１）将原始数据投影到低维空间并使用如下Ｋ均值算法（　ｍｅａｎｓ）实现对低维数据的　聚类：　ｍｈｎＪ　＝∑∑ＩｌＸｉ一“　（５）　得到聚类标号．　对高维原始数据的聚类，一般地，首先降低它们的维数以避免维数灾难的发生．利用ｍｕｓｔ－ｌｉｎｋ和ｃａｎｎｏｔ－ｌｉｎｋ　成对约束，由式（２）得到投影矩阵，在对数据投影时，尽可能地保持原始数据结构，并最大化ｃａｎｎｏｔ－ｌｉｎｋ点对问的　距离、最小化ｍｕｓｔ．１ｉｎｋ点对间的距离．因此，能够得到令人较为满意聚类结果，便于使用ＬＤＡ选择子空间．　１．２基于成对约束的胸值聚类　作为ＣＢＳＳＣ和ＤＢＳＳＣ组合的ＣＤＢＳＳＣ，在目标函数中添加惩罚项　，　，试图解决约束的违反问题．　互　吒　ｇ（ｄｅｔ（　））ｊ＋　磊　‘≠　】＋（ｘｉ　ｊｌ［‘　在ＣＤＢＳＳＣ中，违反ｍｕｓｔ．１ｉｎｋ约束的惩罚因子　和违反ｃａｎｎｏｔ－ｌｉｎｋ约束的惩罚因子嘞取值分别如下：　：＊一砘＋　一＿　－－‘７）　（８）　Ｉｘ：，一ｘ；Ｉ　ＩＸｉ－Ｘｊ　ＡＩ　ｉＣＤＢＳＳＣ　ｍｕｓｔ　ｌｉｋ　ｎ　指出：如果两个样本违反了　．　约束，则　的值是使用不同聚类中的度量得到的距离之和；如果两个样本违反了ｃａｎｎｏｔ．１ｉｎｋ约束，则研的值是该聚类里选择最远的两个样本之间的距离与这两个样本之　间的距离之差．显然，惩罚因子ｍｆ和　，并不能够有效地解决约束的违反问题．　针对该问题，并受文献【８】的启发，本节引入一种基于成对约束的Ｋ均值聚类算法（ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｔ　ｂａｓｅｄ　ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ，简称ＰＣＢＫＭ），该算法的目的就是寻找Ｋ个互不相交的样本分割，且不违反　尹学松等：基于成对约束的判别型半监督聚类分析　２７９５　ｃａｎｎｏｔ．１ｉｎｋ成对约束和ｍｕｓｔ．１ｉｎｋ成对约束．为了解决成对约束的违反问题，首先合并ｍｕｓｔ．１ｉｎｋ约束构建新的　ｃａｎｎｏｔ．１ｉｎｋ约束作为预处理，具体描述如下：　定义ｌ（同类闭包）．如果有３个样本ａｌ，ａ２和　３，（口１，ａ２）∈　（口２，ａ２）∈　则（口ｌ，口３）∈Ｍ并称ａｌ，ａ２和ａ３构成的集　合为同类闭包，简称闭包．　１　Ｐ　定义２（闭包中心）．如果｛　Ｉ，ａ２…．，　｝构成一个同类闭包，口＝亡∑ｑ，Ｐ　则称口为闭包中心．　ｉ＝１　定义３（异类闭包）．如果存在两个闭包　＝｛口１，ａ２…．，　｝和　＝｛６ｌ，ｂ２，．．．，　），以及（口ｆ，　）∈Ｃ，其中ａｉＡ，ｒ　∈　，则称　。　互为异类闭包．　为了简化约束，使用闭包中心之间的ｃａｎｎｏｔ．１ｉｎｋ约束代替样本之间的ｃａｎｎｏｔ—ｌｉｎｋ约束．如图２所示，实线表　示ｍｕｓｔ．１ｉｎｋ约束，虚线表示ｃａｎｎｏｔ．１ｉｎｋ约束，白点表示原始样本，黑点代表闭包中心．其中，｛口ｌ，ａ２，ａ３｝和　｛ｂｌ，ｂ２，ｂ３，ｂ４，ｂ５｝分别表示两个闭包，ａ，ｂ分别代表它们的闭包中心．样本之间的ｃａｎｎｏｔ－ｌｉｎｋ约束就可以简化为闭包　中心ａ，ｂ之间的ｃａｎｎｏｔ．１ｉｎｋ约束．特别地，如果一个样本不属于任何约束，则可以构造一个闭包，在该闭包里只有　这一个样本元素．　０－一一一一一一一●　ａ　ｂ　Ｆｉｇ．２　Ａｎ　ｉｌｌｕｓｔｒａｔｉｏｎ　ｏｆ　ｃｏｍｂｉｎｉｎｇ　ｍｕｓｔ・ｌｉｎｋ　ｃｏｎｓｔｒａｉｎｔｓ　ｔｏ　ｆｏｒｍ　ｎｅｗ　ｃａｎｎｏｔ－ｌｉｎｋ　ｃｏｎｓｔｒａｉｎｔｓ　图２合并ｍｕｓｔ．１ｉｋ约束构成新的ｃａｎｎｏｔｎ．１ｉｎｋ约束示意图　用闭包中心代替闭包，用两个闭包中心的ｃａｎｎｏｔ．１ｉｎｋ约束代替相应的异类闭包中样本间的ｃａｎｎｏｔ．１ｉｎｋ约　束，则合并ｍｕｓｔ—ｌｉｎｋ成对约束以后，原样本数据　可简化为　，＝［　，　，．．．，　，］（ｒｌｍｌ＜ｒ１），ｃａｎｎｏｔ－ｌｉｎｋ成对约束的集　合改变为　尸｛（　，ｘ　）｝．　命题１．若以闭包中心取代闭包，两个异类闭包的闭包中心分别代替相应的ｃａｎｎｏｔ．１ｉｎｋ约束的异类闭　包，ＰＣＢＫＭ对闭包中心聚类，则ＰＣＢＫＭ能够解决ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束的违反问题．　证明：分两种情况来证明，一是证明ＰＣＢＫＭ不违反ｍｕｓｔ．１ｉｎｋ成对约束，二是证明ＰＣＢＫＭ不违反　ｃａｎｎｏｔ．１ｉｎｋ成对约束．　（１）ＰＣＢＫＭ不违反ｍｕｓｔ．１ｉｎｋ成对约束　证明：设　尸　１　２，…，Ｘｐ｝为第ｉ个同类闭包，　是　ｆ的闭包中心，Ｃ＝｛ｃ１，Ｃ２…．，ｃ　是　个聚类集合，　｛“ｌ，　…．，　）是　个聚类分别对应的聚类中心集合．　Ｅ“　“ｆ∈　“ｆ∈ｕ，使得“ｆ＝ａｒｇｍｉｎ（］［　一＂　ＩＩ　），得至０　Ｅ　Ｃｉ．　因为闭包中心　代替了　ｆ，所以墨∈Ｇ　ｆｃＣｉ．　于是，　ｆ∈　ｊ　ｆ∈　，ｉ＝１，２，．．．　．证毕．　口　上述结果避免了同类闭包　中的元素聚类到其他聚类中，解决了　中ｍｕｓｔ．１ｉｎｋ成对约束的违反问题．类似　地，可以证明其他同类闭包不违反ｍｕｓｔ．１ｉｎｋ成对约束．　（２）ＰＣＢＫＭ不违反ｃａｎｎｏｔ．１ｉｎｋ成对约束　证明：设Ａ，－＝｛Ｘｌ，ｘ２，．．．　）为第ｆ个同类闭包，　是Ａｆ的闭包中心　『＝ｘ１　２，．．．　）为第Ｊ个同类闭包，　，是　ｆ　的闭包中心，且Ａ　和　，属于异类闭包．　由于ｃａｎｎｏｔ・ｌｉｎｋ成对约束要求　和＿『被聚类到不同的聚类中，故存在Ｕｉ，“ｆ，且ｔ，ｔｉ￣　“『∈Ｕ，“ｆ∈≠“，，使得　２７９６　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８　（Ｕｉ，Ｕｊ）＝鹕　因此，　∈　，　，∈ｃｊ．　“。．　Ｅ　Ｕ　、　ＩＩ２＋　一　”　”，　（９）因为　是Ａ，的闭包中心，　，是　，的闭包中心，　所以，可得Ａｆｃｃｉ￣ａｊｃＧ．　即Ｖ　ｆ∈　ｆ　ｆ∈Ｇ，卢１，２，．．．　；　∈　力∈　户１，２，．．．　．证毕．　口　由以上证明不难发现，互为异类闭包的两个闭包中的样本分别聚类到两个不同的聚类中，符合ｃａｎｎｏｔ．１ｉｎｋ　的要求，解决了ｃａｎｎｏｔ．１ｉｎｋ成对约束违反问题．　ＰＣＢＫＭ的伪代码见算法１．ＰＣＢＫＭ的计算复杂度是Ｏ（ｔｎ　，，　）（ｎｒｎｌ＜Ｖ１），其中，，是样本维数，ｎ　，是合并　ｍｕｓｔ．１ｉｎｋ成对约束后的样本数，　是原样本数，ｆ是迭代次数．不难发现，ＰＣＢＫＭ的计算复杂度小于或者等于　Ｋ－ｍｅａｎｓ的计算复杂度（Ｏ（ｔｎｌ２））．因此，ＰＣＢＫＭ是一种简单而有效的算法．　算法１．基于成对约束的　均值算法（ＰｃＢＫＭ）．　输入：样本数据　，、ｃａｎｎｏｔ．１ｉｎｋ约束集合　，和聚类数目　输出：　个不相交的样本分割．　Ｓｔｅｐ　１．初始化聚类中心．　Ｓｔｅｐ　２．重复执行下面的步骤，直到收敛为止．　ｆｏｒ　ｆ＝１　ｔｏ　ｌ＇ｌｍｌ　（ａ）对一个闭包不与任一个闭包构成异类闭包，找到一个聚类中心Ｕ　使该闭包中心　满足　＝ａｒｇｍｉｎ￣ｆ　一　８　；　（ｂ）对于互为异类闭包的两个闭包，　和ｘ　ｙ是它们的闭包中心，（　，　）∈　ｆ，找到两个聚类中心　“　和　，使ｍｉｎｆ　ＩＩｘ；－￣ｔｉ　（ｃ）对某个聚类ｃ　，更新其聚类中心Ｕｉ＝÷∑　ｉ‘．　ｉｊ＝ｌ　Ｓｔｅｐ　３．返回　个不相交的样本分割．　ＣＤＢＳＳＣ在Ｋ－ｍｅａｎｓ的目标函数中添加惩罚项，试图解决约束的违反问题．但选择合适的惩罚因子是该类　算法面临的难题．因此，这类算法不仅难以解决约束的违反问题，而且还增加了算法的计算复杂度（Ｏ（ｔｎｌ４））．本节　提出的ＰＣＢＫＭ，其思想是用ｍｕｓｔ—ｌｉｎｋ，ｃａｎｎｏｔ．１ｉｎｋ约束分别构成同类闭包和异类闭包，并应用于Ｋ－ｍｅａｎｓ中，在　保持其计算复杂度的情况下，解决成对约束的违反问题，有效地提高聚类性能，并通过合并ｍｕｓｔ．１ｉｎｋ约束，可以　简化原始样本，有助于算法实现大规模数据集的处理．　１．３基于成对约束的判别型半监督聚类算法　基于上面的描述，本文提出一种同时执行子空间选择和聚类的判别型半监督聚类分析算法，见算法２．其步　骤如下：　算法２．基于成对约束的判别型半监督聚类分析算法（ＤＳＣＡ）．　输入：样本数据　ｍｕｓｔ—ｌｉｋ和ｃａｎｎｏｔｎ　１ｉｋ成对约束、聚类数目　ｎ输出：　个样本分割．　Ｓｔｅｐ　１．根据第１．１节，得到Ｋ个样本分割，ｔ＝１．　Ｓｔｅｐ　２．执行以下步骤：　（ａ）利用　个样本分割，在原样本空间中计算ＬＤＡ，得到子空间；　（ｂ）使用ＰＣＢＫＭ对子空间中的样本聚类，得到　个样本分割；　（Ｃ）ｆ：ｆ＋ｌ，返回Ｓｔｅｐ　２，直到算法收敛为止．　尹学松等：基于成对约束的判别型半监督聚类分析　２７９７　Ｓｔｅｐ　３．返回Ｋ个样本分割．　类似于文献［１３，１５，１６］的结果，可以证明ＤＳＣＡ在有限步内收敛．在实验中观察到，不到１０次迭代即收敛．　从上述算法可以发现，ＤＳＣＡ的复杂度主要是在求解ＰＣＢＫＭ上．ＰＣＢＫＭ的计算复杂度是Ｏ（ｔｎ　，，　），因此，　ＤＳＣＡ的复杂度为Ｏ（ｐｔｎ　，／２），ｐ是ＤＳＣＡ迭代次数．　２实验及其分析　首先比较本文的算法ＰＣＢＫＭ与ＣＤＢＳＳＣ，以验证它们解决成对约束的违反问题．其次，将本文算法ＤＳＣＡ　与现有相关的半监督算法进行比较．　２．１　ＰＣＢＫＭ与ＣＤＢＳＳＣ的比较　２．１．１人工数据集上的实验　考虑两类人工数据集，如图３（ａ）所示，实线连接的两个样本属于同一聚类，是ｍｕｓｔ－ｌｉｎｋ约束；虚线连接的两个　样本属于不同聚类，是ｃａｎｎｏｔ．１ｉｎｋ约束．在实验中，违反ｍｕｓｔ．１ｉｋ约束用实线表示，ｎ违反ｃａｎｎｏｔ－ｌｉｎｋ约束用虚线　表示．如果解决了约束违反问题，则不用实线和虚线表示．　（ａ）Ｏｒｉｇｉｎａｌ　ｍｕｓｔ—ｌｉｎｋ　ａｎｄ　ｃａｎｎｏｔ－ｌｉｎｋ　ｃｏｎｓｔｒａｉｎｔｓ　（ａ）原ｍｕｓｔ—ｌｉｋ和ｃａｎｎｏｔ—ｎｌｉｎｋ约束　（ｂ）Ｃｌｕｓｔｅｒｅｄ　ｒｅｓｕｌｔｓ　ｏｆ　ＣＢＳＳＣ　（ｂ）ＣＢＳＳＣ聚类结果　（ｃ）Ｃｌｕｓｔｅｒｅｄ　ｒｅｓｕｌｔｓ　ｏｆ　ＣＤＢＳＳＣ　（ｄ）Ｃｌｕｓｔｅｒｅｄ　ｒｅｓｕｌｔｓ　ｏｆＰＣＢＫＭ　（ｃ）ＣＤＢＳＳＣ聚类结果　（ｄ）ＰＣＢＫＭ聚类结果　Ｆｉｇ．３　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｖｉｏｌａｔｉｏｎ　ｉｓｓｕｅ　ｏｆ　ｔｈｅ　ｃｏｎｓｔｒａｉｎｔｓ　ｓｏｌｖｅｄ　ｂｙ　ＰＣＢＫＭ　ａｎｄ　ＣＤＢＳＳＣ　图３　ＰＣＢＫＭ与ＣＤＢＳＳＣ解决约束违反问题的比较　从图３（ｂ）中不难发现，实线连接的ｍｕｓｔ．１ｉｎｋ点对已经被ＣＢＳＳＣ分组到不同的聚类中，虚线连接的　ｃａｎｎｏｔ－ｌｉｋ点对被聚类成相同的类．ｎ因此，该算法未能有效地解决约束的违反问题．同样的问题可以由图３（ｃ）中　２７９８　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８　发现，即ＣＤＢＳＳＣ仍未能有效地解决约束的违反问题．本文提出的ＰＣＢＫＭ解决了成对约束的违反问题，如　图３（ｄ）所示．　２．１．２真实数据集上的实验　通过两个ＵＣＩ数据集，分别测试ＣＤＢＳＳＣ和ＰＣＢＫＭ解决约束的违反问题．在表１中，对Ｉｏｎｏｓｐｈｅｒｅ数据集　而言，选择ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ的点对分别为７９对和６６对，ＣＤＢＳＳＣ聚类时，违反ｍｕｓｔ．１ｉｎｋ约束的点对数　为ｌ４对，违反ｃａｎｎｏｔ．１ｉｎｋ约束的点对数为３６对．本文提出的算法ＰＣＢＫＭ解决了成对约束的违反问题．　Ｔａｂｌｅ　１　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｎｕｍｂｅｒｓ　ｏｆ　ｃｏｎｓｔｒａｉｎｔｓ　ｖｉｏｌａｔｅｄ　ｂｙ　ＰＣＢＫＭ　ａｎｄ　ＣＤＢＳＳＣ　表１　ＰＣＢＫＭ和ＣＤＢＳＳＣ违反成对约束数的比较　Ｄａｔａｓｅｔ　ｍｕｓｔ．１ｉｎｋ　ｃａｎｎｏｔ—ｌｉｋｎ　ＣＤＢＳＳＣ　ＰＣＢＫＭ　ｍｕｓｔ－ｌｉｋｎ　ｃａｎｎｏｔ—ｌｉｋｎ　ｍｕｓｔ—ｌｉｎｋ　ｃａｎｎｏｔ．１ｉｋｎ　Ｉｏｎｏｓｐｈｅｒｅ　７９　６６　１４　３６　０　０　ＩｒｉＳ　ｌ６　１６　６　７　０　０　２．２　ＤＳＣＡ与其他相关半监督算法的比较　２．２．１　实验设置　首先，我们从ＵＣＩ数据集上选择了７个较低维数的数据集，它们分别是Ｂａｌａｎｃｅ，Ｉｏｎｏｓｐｈｅｒｅ，Ｉｒｉｓ，Ｌｅｔｔｅｒ，　Ｓｏｙｂｅａｎ，Ｖｅｈｉｃｌｅ和Ｗｉｎｅ．同时选择了５个较高维数的数据集，它们是ＹａｌｅＢ人脸数据集、ＯＲＬ人脸数据集和３　个文本数据集Ｎｅｗｓ．Ｄｉｆｆｅｒｅｎｔ，Ｎｅｗｓ．Ｓａｍｅ，Ｎｅｗｓ．Ｓｉｍｉｌａｒ．　然后，我们选择４种聚类算法作为对比，来验证ＤＳＣＡ的性能．这４种算法是：　（１）Ｋ－ｍｅａｎｓ．它是一种常用的、适合于较低维数的样本数据的聚类算法．　（２）相关成分分析算法（ＲｃＡ）［３】．该算法是最近被提出来的一种半监督度量学习算法，实验结果已经表明其　性能优于由Ｘｉｎｇ等人【　ｌ提出的基于约束的半监督度量学习算法．在使用ＲＣＡ对样本数据进行度量变　换后，使用Ｋ－ｍｅａｎｓ对变换后的数据聚类．　（３）局部线性嵌入（ＬＬＥ）【＂１．它是无监督降维方法．使用该方法对较高维数的样本数据降维，然后使用　Ｋ－ｍｅａｎｓ对数据聚类．　（４）特征投影的半监督聚类算＂￣（ＳＣＲＥＥＮ）ｔＳｋ该方法借助于ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ－ｌｉｎｋ成对约束得到投影矩　阵，在子空间中用基于约束的球形　均值算法对数据聚类．它既可用于对低维数据聚类，也可用于对高　维数据聚类．　本文采用规范化互信，ｇ（ＮＭＩ）作为聚类的评价方法【６１．如果Ｃ是样本聚类后的类标号，ｙ是样本原有类标号，　则ＮＭＩ表示为　ＮＭｔ（ｃ　＝　（１０　其中Ｉ（Ｃ；ＩＯ＝Ｈ（Ｙ）　ｙ１０是Ｃ和ｙ之间的互信息　ｙ）是ｙ的香农熵，　０是在给定ｃ的条件下，ｙ的条件　熵．ＮＭＩ值的范围在０，１之间，ＮＭＩ值越大，聚类的性能就越好．一般而言，ＮＭＩ评价方法要优于其他评价方法Ｌ８】．　最后，算法运行在Ｉｎｔｅｌ　Ｐｅｎｔｉｕｍ　３．００ＧＨｚ　ＣＵＰ，１Ｇ内存Ｗｉｎｄｏｗｓ环境下的机器上．５种算法分别在每个数据　集上重复实验１５次，在每次实验中选择１００对成对约束，并在整个数据集上来测试算法的性能，取１５次实验　ＮＭＩ值的均值作为最终的聚类结果．在对数据降维时，一般设置维数降到』，＿＿１维（其中　是聚类数）．　２．２．２实验结果　表２和表３是在１２个数据集上分别执行５种算法得到的ＮＭＩ值．表２中的数据是低维数据，在对低维数据　聚类时，ＤＳＣＡ的ＮＭＩ值在Ｉｒｉｓ，Ｌｅｔｔｅｒ，Ｓｏｙｂｅａｎ和Ｗｉｎｅ四个数据集上占优，ＳＣＲＥＥＮ的ＮＭＩ值在Ｂａｌａｎｃｅ数据　集上效果好，ＲＣＡ的ＮＭＩ值在Ｉｏｎｏｓｐｈｅｒｅ和Ｖｅｈｉｃｌｅ两个数据集上占优．总体而言，ＤＳＣＡ的性能在低维数据集　上优于其他３种算法．表３中的数据是高维数据．不难发现，在对高维数据聚类时，ＤＳＣＡ的ＮＭＩ值要高于其他３　种算法的ＮＭＩ值．其次，ＮＭＩ值较好的是ＳＣＲＥＥＮ，而ＲＣＡ对高维数据进行处理时ＮＭＩ值较差．所以，对高维数　尹学松等：基于成对约束的判别型半监督聚类分析　２７９９　据聚类，ＤＳＣＡ的性能要优于其他几种算法．ＤＳＣＡ利用了监督信息集成数据降维和聚类，且聚类时考虑了成对　约束的违反问题，因此，ＤＳＣＡ的性能要优于其他几种算法．　在ＤＳＣＡ初始化得到投影矩阵后，使用ＰＣＢＫＭ代替Ｋ－ｍｅａｎｓ，这样有利于ＬＤＡ选择子空间．　Ｔａｂｌｅ　２　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ＮＭＩ　ａｃｈｉｅｖｅｄ　ｂｙ　ＤＳＣＡ　ａｎｄ　ｔｈｒｅｅ　ｍｅｔｈｏｄｓ　ｏｎ　ｓｅｖｅｎ　ｌｏｗ－ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａｓｅｔｓ　表２　ＤＳＣＡ与３种算法在７个低维数据集上的ＮＭＩ值的比较　Ｔａｂｌｅ　３　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ＮＭＩ　ａｃｈｉｅｖｅｄ　ｂｙ　ＤＳＣＡ　ａｎｄ　ｔｒｈｅｅ　ｍｅｔｈｏｄｓ　ｏｎ　ｆｉｖｅ　ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａｓｅｔｓ　表３　ＤＳＣＡ与３种算法在５个高维数据集上的Ｎ／ＶＩＩ值的比较　２．３成对约束对ＤＳＣＡ性能的影响　Ｍｕｓｔ．Ｌｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束由用户提供，半监督聚类算法一般认为这两个约束是正确的．本文提出的　ＤＳＣＡ和其他半监督聚类算法借助于ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束来提高聚类性能．　由表２和表３不难发现，ＤＳＣＡ的性能优于其他几种算法．为了更好地理解成对约束对半监督聚类算法性能　的影响，实验过程中选择了不同数量的成对约束．从图４中可以观察到，尽管几种算法的性能都随着成对约束的　数量增多而逐渐提高，但不同数量的成对约束对几种算法性能的影响是不同的．在成对约束数量较少（如ｌｏ）　时，ＤＳＣＡ的ＮＭＩ值高于其他几种算法的ＮＭＩ值．在成对约束数量逐渐增多时，ＤＳＣＡ的ＮＭＩ值平稳上升，其性　能优于其他几种算法．　ＳＣＲＥＥＮ借助于ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束得到投影矩阵，在子空间中用基于约束的球形　均值算　法对数据聚类．因此，选择的ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｋｎ成对约束得到好的投影矩阵对该算法至关重要．本文提出的　ＤＳＣＡ是在初始化步骤里借助于这两种约束得到投影矩阵。进而在子空间中得到初始聚类．所以。当选择的　ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束得不到好的投影矩阵时，对ＤＳＣＡ的聚类会产生一定的影响，但由于ＤＳＣＡ利　用无标号样本来重新得到投影矩阵，所以在固定成对约束数量的情况下，选择相同的成对约束对ＤＳＣＡ性能的　影响比对ＳＣＲＥＥＮ性能影响要小．　要解决上述问题，一个自然的想法就是需要尽可能多地选择ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束，但提供更多　的成对约束需要付出很大的代价．因此，在有限的ｍｕｓｔ．１ｉｋｎ和ｃａｎｎｏｔ．１ｉｎｋ成对约束中，选择有利于聚类算法的成　对约束将是一个挑战．　３相关工作　ＣＢＳＳＣ首先是由Ｗａｇｓｔａｆｆ［　等人提出来的，他们将ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束运用到无监督聚类中．　由于该算法在聚类过程中严格限制成对约束的使用，因此，该算法的聚类性能受到了影响．Ｂｕａｌ［　等人提　出，ＣＢＳＳＣ是从带有类标号的样本中设法找到更好的初始聚类中心，并将这些带有类标号的样本用于聚类过程．　该方法使用的有监督信息是带有类标号的样本，而不是成对约束．相对于约束的半监督聚类算法，基于距离的半　监督聚类算法是通过有监督信息去学习一个距离函数，以此来提高聚类性能．Ｘｉｎｇ［５１等人利用成对约束和牛顿　２８００　鲫　如　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８　Ｏ　Ｏ　Ｏ　０　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　∞　如　娜　∞　迭代法来学习一个马氏距离并应用到聚类中．Ｂａｒ．Ｈｉｌｌｅｌ［　等人提出的方法仅仅利用ｍｕｓｔ．１ｉｎｋ成对约束得到块　（ｃｈｕｎｋ１ｅｔ）协方差矩阵，然后对块协方差矩阵进行白化变换来学习一个马氏距离．Ｙｅｕｎｇ［　等人提出的方法是　Ｂａｒ．Ｈｉｌｌｅｌ所提出方法的改进，用ｍｕｓｔ．１ｉｎｋ　ｃａｎｎｏｔ．１ｉｎｋ成对约束得到块协方差矩阵．Ｓｃｈｕｌｔｚ㈣等人提出的方法　是从相对约束关系中学习一个带有权值的欧氏距离．Ｂｕａｌ和Ｂｉｌｅｎｋｏ［　，　提出的方法是集成ｍｕｓｔ．１ｉｎｋ，ｃａｎｎｏｔ．１ｉｎｋ　成对约束和度量学习，应用到聚类中．　０．９５　０．９０　（）ｌ８５　至　Ｚ　ｚ　０．８０　０．７５　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　Ｏ　０．７０　１０　２０　３０　４０　５（）　６０　７０　８０　９０　ｌ００　Ｎｕｍｂｅｒ　ｏｆｃｏｎｓｔｒａｉｎｔｓ　∞　Ｎｕｍｂｅｒ　ｏｆｃｏｎｓｔｒａｉｎｔｓ　蛐　如　ｌ０　２０　３０　４０　５０　６０　７０　８０　９０　１Ｏ０　（ａ）Ｂａｌａｎｃｅ　ｄａｔａｓｅｔｓ　（ａ）Ｂａｌａｎｃｅ数据集　（）．９０　０．８５　０．８０　０．７５　（ｂ）Ｉｒｉｓ　ｄａｔａｓｅｔｓ　（ｂ）Ｉｒｉｓ数据集　＝　Ｚ　０．７０　０　６５　０　６０　０．５５　１０　２０　３０　４０　１０　２Ｏ　３Ｏ　４０　５０　６０　７０　８０　９０　ｌＯ０　Ｎｕｍｂｅｒ　ｏｆ　ｃｏｎｓｔｒａｉｎｔｓ　Ｎｕｍｂｅｒ　ｏｆｃｏｎｓｔｒａｉｎｔｓ　（ｃ）Ｓ０ｙｂｅａｎ　ｄａｔａｓｅｔｓ　（ｃ）Ｓｏｙｂｅａｎ数据集　（ｄ】Ｗｉｎｅ　ｄａｔａｓｅｔｓ　（ｄ）Ｗｉｎｅ数据集　Ｆｉｇ．４　Ｒｅｌａｔｉｖｅ　ｉｍｐａｃｔ　ｏｎ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｃｈｏｏｓｉｎｇ　ｔｈｅ　ｄｉｆｆｅｒｅｎｔ　ｎｕｍｂｅｒｓ　ｏｆ　ｐａｉｒｗｉｓ　ｃｏｎｓｔｒａｉｎｔｓ　图４选择不同数量的成对约束对算法性能的影响　上述算法只适用于低维空间．对高维数据聚类，一种方法是利用无监督降维方法对高维数据降维，然后使用　上述方法对数据聚类；另一种方法是寻找新的算法，借助于有监督信息，对高维数据降维并聚类．前一种聚类方　法已经得到验证，结果不能令人满意Ｉ　．因此，只能寻找新的半监督聚类方法来解决高维数据聚类问题．Ｗｅｉ［８】等　人提出基于特征投影的半监督聚类算法，该算法利用ｍｕｓｔ．１ｉｋ和ｃａｎｎｏｔｎ．１ｉｋ成对约束得到投影矩阵，ｎ在投影空　问中应用基于约束的球形　均值聚类方法对数据聚类．该算法可以解决高维数据聚类问题，但其缺点是只使用　ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束得到投影矩阵，既没有考虑到大量无标号样本数据，又忽略了降维和聚类的相　互促进，因此限制了聚类性能的提高．　最近，一些学者针对高维数据的无监督聚类提出了新的方法．Ｄｅ　ｌａ　Ｔｏｒｒｅ［１９１等人提出判别聚类分析算法．该　算法集成了降维和聚类，即首先对高维数据降维，然后在低维空间中对数据聚类．Ｃｈｒｉｓ　Ｄｉｎｇ［”】等人提出了一种　自适应无监督降维迭代算法．该算法使用Ｋ－ｍｅａｎｓ来产生数据的类标号，然后用线性判别分析方法对高维数据　尹学松等：基于成对约束的判别型半监督聚类分析　２８０１　降维．在降维空间中，再使用Ｋ－ｍｅａｎｓ方法对数据聚类．ｙｅ［　】提出了自适应距离学习聚类算法．该算法同样是集　成降维和聚类，但不同的是，算法是最优化同一个目标函数来得到聚类和降维．以上３种方法的目的是通过降维　来帮助聚类，再通过聚类来指导降维，但它们都没有解决好一个难题，即在高维空间中，算法是先执行降维还是　先执行聚类．本文提出的基于成对约束的判别型半监督聚类分析算法先借助于成对约束求解投影矩阵，然后在　子空间中聚类，再利用聚类结果指导降维．显然，新算法不仅在很大程度上解决了上述无监督聚类算法所面临的　问题，而且充分利用有监督信息，有效地提高了聚类性能．　借助于一部分有监督信息，半监督聚类在很大程度上提高了无监督聚类的性能．因此，一些研究人员着力去　研究监督信息在聚类分析中的作用，并将其运用到半监督分类和半监督回归等方面．目前，半监督学习已经受到　越来越多的研究者的重视．　４结束语　本文提出了一种基于成对约束的判别型半监督聚类分析方法．新方法首先利用ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成　对约束得到初始投影矩阵，在投影空间中对数据聚类；然后，利用ＬＤＡ选择子空间；最后，使用基于成对约束的　均值算法对子空间中的数据聚类．该方法有效地利用了监督信息集成数据降维和聚类，即在投影空间中使用基　于成对约束的　均值算法对数据聚类，再利用聚类结果选择投影空问．同时，新方法提出的基于成对约束的　均　值算法降低了基于约束的半监督聚类算法的计算复杂度，并解决了聚类过程中成对约束的违反问题．　在半监督聚类算法中，监督信息越多，越有助于算法性能的提高．但由于监督信息由用户提供，代价较大．因　此，在有限的ｍｕｓｔ．１ｉｎｋ和ｃａｎｎｏｔ．１ｉｎｋ成对约束中，选择有利于提高算法性能的成对约束将是一个让人感兴趣的　课题，也是我们下一阶段工作的方向．　致谢张道强教授和蔡维玲博士对本文的工作提出了有益的建议，我们在此表示感谢　Ｒｅｆｅｒｅｎｃｅｓ：　ｆ１］　Ｂａｒ－Ｈｉｌｌｅｌ　Ａ，Ｈｅｒｔｚ　Ｔ，Ｓｈａｎｔａｌ　Ｎ，Ｗｅｉｎｓｈａｌｌ　Ｄ．Ｌｅａｒｎｉｎｇ　ａ　ｍａｈａｌａｎｏｂｉｓ　ｍｅｔｒｉｃ　ｆｒｏｍ　ｅｑｕｉｖａｌｅｎｃｅ　ｃｏｎｓｔｒａｉｎｔｓ．Ｊｏｕｒｎａｌ　ｏｆＭａｃｈｉｎｅ　Ｌｅａｍｉｎｇ　Ｒｅｓｅａｒｃｈ，２００５，６（５）：９３７—９６５．　［２］　Ｗａｇｓｔａｆｆ　Ｋ，Ｃａｒｄｉｅ　Ｃ，Ｒｏｇｅｒｓ　Ｓ，Ｓｃｈｒｏｅｄｌ　Ｓ．Ｃｏｎｓｔｒａｉｎｅｄ　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｗｉｔｈ　ｂａｃｋｇｒｏｕｎｄ　ｋｎｏｗｌｅｄｇｅ．Ｉｎ：Ｂｒｏｄｌｅｙ　ＣＥ，　Ｄａｎｙｌｕｋ　ＡＰ，ｅｄｓ．Ｐｒｏｃ．ｏｆｔｈｅ　１８ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｗｉｌｌｉａｍｓｔｏｗｎ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，２００１．５７７—５８４．　［３］　Ｂａｒ—Ｈｉｌｌｅｌ　Ａ，Ｈｅｒｔｚ　Ｔ，Ｓｈｅｎｔａｌ　Ｎ，Ｗｅｉｎｓｈａｌｌ　Ｄ．Ｌｅａｒｎｉｎｇ　ｄｉｓｔａｎｃｅ　ｆｕｎｃｔｉｏｎｓ　ｕｓｉｎｇ　ｅｑｕｉｖａｌｅｎｃｅ　ｒｅｌａｔｉｏｎｓ．Ｉｎ：Ｆａｗｃｅｔｔ　Ｔ，Ｍｉｓｈｒａ　Ｎ，　ｅｄｓ．Ｐｒｏｃ．ｏｆｔｈｅ　２０ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，２００３．１　１－１８．　［４］　Ｂａｓｕ　Ｓ，Ｂａｎｅｏｅｅ　Ａ，Ｍｏｏｎｅｙ　ＲＪ．Ｓｅｍｉ—Ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ｂｙ　ｓｅｅｄｉｎｇ．Ｉｎ：Ｓａｍｍｕｔ　Ｃ，Ｈｏｆｆｍａｎｎ　ＡＧ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　９ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｓｙｄｎｅｙ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，２００２．１　９－２６．　【５］Ｘｉｎｇ　ＥＰ，Ｎｇ　ＡＹ，Ｊｏｒｄａｎ　ＭＩ，Ｒｕｓｓｅｌｌ　Ｓ．Ｄｉｓｔａｎｃｅ　ｍｅｔｒｉｃ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｃｌｕｓｔｅｒｉｎｇ　ｗｉｔｈ　ｓｉｄｅ—ｉｎｆｏｒｍａｔｉｏｎ．Ｉｎ：Ｂｅｃｈｅｒ　Ｓ．　Ｔｈｒｕｎ　Ｓ，Ｏｂｅｒｍａｙｅｒ　Ｋ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１６ｔｈ　Ａｎｎｕａｌ　Ｃｏｎ￣ｏｎ　Ｎｅｕｒａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　ＳｙｓｔｅｍＣａｍｂｒｉｄｇｅ：ＭＩＴ　Ｐｒｅｓｓ．　．２００３．５０５－５　ｌ２．　【６］Ｂａｓｕ　Ｓ，Ｂａｎｅｒｊｅｅ　Ａ，Ｍｏｏｎｅｙ　ＲＪ．Ａ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｂｏｕｌｉｃａｕｔ　ＪＦ，Ｅｓｐｏｓｉｔｏ　Ｆ，Ｇｉｎｎｏｔａｔｉ　Ｆ，Ｐｅｄｒｅｓｃｈｉ　Ｄ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１０ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００４．５９－６８．　［７］Ｂｉｌｅｎｋｏ　Ｍ，Ｂａｓｕ　Ｓ，Ｍｏｏｎｅｙ　ＲＪ．Ｉｎｔｅｇｒａｔｉｎｇ　ｃｏｎｓｔｒａｉｎｔｓ　ａｎｄ　ｍｅｔｒｉｃ　ｌｅａｒｎｉｎｇ　ｉｎ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｂｒｏｄｌｅｙ　ＣＥ．ｅｄ．Ｐｒｏｃ．　ｏｆｔｈｅ　２１　ｓｔ　Ｉｎｔ’１　ＣｏｎＥ　ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００４８１—８８．　．［８］Ｔａｎｇ　Ｗ，Ｘｉｏｎｇ　Ｈ，Ｚｈｏｎｇ　Ｓ，Ｗｕ　Ｊ．Ｅｎｈａｎｃｉｎｇ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ：ａ　ｆｅａｔｕｒｅ　ｐｒｏｊｅｃｔｉｏｎ　ｐｅｒｓｐｅｃｔｉｖｅ．Ｉｎ：Ｂｅｒｋｈｉｎ　Ｐ．Ｃａｒｕａｎａ　Ｒ，Ｗｕ　ＸＤ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　３ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ２００７．７０７－７１６．　，　［９］Ｂａｓｕ　Ｓ，Ｂａｎｅｒｊｅｅ　Ａ，Ｍｏｏｎｅｙ　ＲＪ．Ａｃｔｉｖｅ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｉｏｎ　ｆｏｒ　ｐａｉｒｗｉｓｅ　ｃｏｎｓｔｒａｉｎｅｄ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｊｏｎｋｅｒ　Ｗ，Ｐｅｔｋｏｖｉｃ　Ｍ，ｅｄｓ．Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＳＩＡＭ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｃａｍｂｒｉｄｇｅ：ＭＩＴ　Ｐｒｅｓｓ２００４．３３３—３４４．　，２８０２　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１９，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ　２００８　Ｂ，Ｄｏｍｅｎｉｃｏｎｉ　Ｃ．Ａｎ　ａｄａｐｔｉｖｅ　ｋｅｒｎｅｌ　ｍｅｔｈｏｄ　ｆｏｒ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｆｔｉｒｎｋｒａｎｚ　Ｊ，Ｓｃｈｅｆｆｅｒ　Ｔ，Ｓｐｉｌｉｏｐｏｕｌｏｕ　Ｍ，ｅｄｓ　［１０］　Ｙａｎ　Ｐｒｏｃ．ｏｆ　ｔｈｅ　１　７ｔｈ　Ｅｕｒｏｐｅａｎ　Ｃｏｎｆ．ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｂｅｒｌｉｎ：Ｓｉｇｍａ　Ｐｒｅｓｓ，２００６．１　８－２２．　Ｙｅｕｎｇ　ＤＹ，Ｃｈａｎｇ　Ｈ．Ｅｘｔｅｎｄｉｎｇ　ｔｈｅ　ｒｅｌｅｖａｎｔ　ｃｏｍｐｏｎｅｎｔ　ａｎａｌｙｓｉｓ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｅｔｒｉｃ　ｌｅａｒｎｉｎｇ　ｕｓｉｎｇ　ｂｏｔｈ　ｐｏｓｉｔｉｖｅ　ａｎｄ　ｎｅｇａｔｉｖｅ　ｅｑｕｉｖａｌｅｎｃｅ　ｃｏｎｓｔｒａｉｎｔｓ．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，２００６，３９（５）：１００７—１０１０．　　Ｋ，Ｇｏｌｄｓｔｅｉｎ　Ｊ，Ｒａｍａｋｒｉｓｈｎａｎ　Ｒ，Ｓｈａｆｔ　Ｕ．Ｗｈｅｎ　ｉｓ“Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒｓ　Ｍｅａｎｉｎｇｆｕｌ”？Ｉｎ：Ｂｅｅｒｉ　Ｃ，Ｂｕｎｅｍａｎ　Ｐ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　［１２］　Ｂｅｙｅｒｔｈｅ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｄａｔａｂａｓｅ　Ｔｈｅｏｒｙ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，１９９９．２１７－２３５．　［１　３］　Ｄｉｎｇ　ＣＨ，Ｌｉ　Ｔ．Ａｄａｐｔｉｖｅ　ｄｉｍｅｎｓｉｏｎ　ｒｅｄｕｃｔｉｏｎ　ｕｓｉｎｇ　ｄｉｓｅｒｉｍｉｎａｎｔ　ａｎａｌｙｓｉｓ　ａｎｄ　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｇｈａｈｒａｍａｎｉ　Ｚ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１９ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００７．５２１－５２８．　［１４］　Ｚｈａｎｇ　ＤＱ，Ｚｈｏｕ　ＺＨ，Ｃｈｅｎ　ＳＣ．Ｓｅｍｉ—Ｓｕｐｅｒｖｉｓｅｄ　ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　ｒｅｄｕｃｔｉｏｎ．Ｉｎ：Ｍａｎｄｏｉｕ　Ｉ，Ｚｅｌｉｋｏｖｓｋｙ　Ａ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　７ｔｈ　ＳＩＡＭ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．Ｃａｍｂｒｉｄｇｅ：ＭＩＴ　Ｐｒｅｓｓ，２００７．６２９－６３４．　　ＪＰ，Ｚｈａｏ　Ｚ，Ｌｉｕ　Ｈ．Ａｄａｐｔｉｖｅ　ｄｉｓｔａｎｃｅ　ｍｅｔｒｉｃ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｂｉｓｈｏｐ　ＣＭ，Ｆｒｅｙ　Ｂ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　［１　５］　ＹｅＳｏｃｉｅｔｙ　Ｃｏｎｆ．ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ　ａｎｄ　Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ．Ｍａｄｉｓｏｎ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ　Ｐｒｅｓｓ，２００７．１－７．　ＪＨ，Ｚｈａｏ　Ｚ，Ｙｅ　ＪＰ，Ｌｉｕ　Ｈ．Ｎｏｎｌｉｎｅａｒ　ａｄａｐｔｉｖｅ　ｄｉｓｔａｎｃｅ　ｍｅｔｒｉｃ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｂｅｒｋｈｉｎ　Ｐ，Ｃａｒｕａｎａ　Ｒ，Ｗｕ　ＸＤ，ｅｄｓ．　【１６］　Ｃｈｅｎ　Ｐｒｏｃ．ｏｆｔｈｅ　１３ｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ｎｄ　ａＤａｔａ　Ｍｉｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００７．１２３—１３２．　　ＬＫ，Ｒｏｗｅｉｓ　ＳＴ．Ｔｈｉｎｋ　ｇｌｏｂａｌｌｙ，ｆｉｔ　ｌｏｃａｌｌｙ：Ｕｎｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ　ｏｆ　ｌｏｗ　ｄｉｍｅｎｓｉｏｎａｌ　ｍａｎｉｆｏｌｄｓ．Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　［１７］　ＳａｕｌＬｅａｒｎｉｎｇ　Ｒｅｓｅａｒｃｈ，２００３，４（３）：１　１９－１５５．　ｔｚ　Ｍ，Ｊｏａｃｈｉｍｓ　Ｔ．Ｌｅａｒｎｉｎｇ　ａ　ｄｉｓｔｎｃｅ　ａｍｅｔｒｉｃ　ｆｒｏｍ　ｒｅｌａｔｉｖｅ　ｃｏｍｐａｒｉｓｏｎｓ．Ｉｎ：Ｔｈｒｕｎ　Ｓ，Ｓａｕｌ　ＬＫ，Ｓｃｈ６１ｋｏｐｆ　Ｂ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　［１８］　Ｓｃｈｕｌ１７ｔｈ　Ａｎｎｕａｌ　Ｃｏｎｆ．ｏｎ　Ｎｅｕｒａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　Ｓｙｓｔｅｍ．Ｃａｍｂｒｉｄｇｅ：ＭＩＴ　Ｐｒｅｓｓ，２００４．４１—４８．　ａ　ＴｏⅡｅ　Ｆ，Ｋａｎａｄｅ　Ｔ．Ｄｉｓｃｒｉｍｉｎａｔｉｖｅ　ｃｌｕｓｔｅｒ　ａｎａｌｙｓｉｓ．Ｉｎ：Ｗｉｌｌｉａｍ　ＷＣ，Ａｎｄｒｅｗ　Ｍ，ｅｄｓ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　１９ｔｈ　Ｉｎｔ’１　Ｃｏｎｆ．ｏｎ　［１９］　Ｄｅ　ｌＭａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００６．２４１—２４８．　尹学松（１９７５一），男，安徽长丰人，博士生，　主要研究领域为模式识别，神经计算．　胡恩￣（１９７５一），男，博士生，主要研究领域　为模式识别。神经计算．　＿　陈师别松，Ｃ神灿经Ｆ（计高１９算６级２，会机一员器），男学主，习博要，研士图究像，教领处授域理，博．为　士模生式识导