基于Universum学习的核聚类方法
朱昌明 吴爱华 王健安
摘要：
为解决原始核聚类（Kernel Clustering， KC）中模式信息不足、聚类结果不佳的缺点，以KC为基础，利用Universum学习带来的优势，提出基于Universum学习的核聚类（Universum learningbased Kernel Clustering， UKC）方法.首先利用Universum学习生成相应的Universum模式，再利用KC算法把数据集分割成多个簇，最后利用每个簇中所包含的Universum模式和训练模式来更新该簇，从而使得这些簇更加合理.实验表明，该算法可以更好地改善聚类效果和分类器的分类性能、泛化能力和计算效率.虽然该方法的步骤比KC多，但是其较好的聚类性能可以帮助人们处理分类问题.
关键词：
Universum学习； 核聚类； 先验知识
0引言
Universum学习由WESTON等[1]提出，旨在把有关应用域的先验知识引入到学习过程中.这些知识是以附加的无标签的和有标签的训练模式的形式表示的.基于Universum的优点，CHERKASSKY等[2]提出基于Universum的支持向量机（Universum Support Vector Machine， USVM），LIU等[3]提出自学习的Universum下的支持向量机（SelfUniversum Support Vector Machine， SUSVM）.笔者把USVM与支持向量机（Support Vector Machine，SVM）进行比较，发现Universum模式的质量会影响分类器的性能.CHEN等[4]发现在目标类之间分布的Universum模式对生成分类界面更有用.由相关实验可知，Universum学习可使模型更符合模式分布、结构等，从而提高算法有效性.如今Universum学习已广泛运用于文本聚类[5]、身体姿势识别[6]、Boosting策略[7]、降维技术[8]和多视角学习[9]等方面.
大部分数据集拥有可以改进分类器性能的局部信息或结构[10]，而聚类是得到这些局部信息或结构的一个较好的方法.聚类旨在把一个由所有模式组成的全局空间分成多个子集，这些子集被称为簇、核或子类.它们有较高的簇内相似度和较低的簇间相似度.一般地，每个簇也可被看作一个局部空间.典型的聚类方法有k均值（kmeans）[11]、合成聚类（Agglomerative Hierarchical Clustering， AHC）[12]和核聚类（Kernel Clustering， KC）[13].通过聚类，可以更好地挖掘模式的局部结构信息.然而，k均值和AHC或生成的簇不一定合适，或计算复杂度高，或聚簇结果对初始设置敏感，所以相比而言，KC才是一个比较合适的聚类方法.
尽管如此，KC所使用的模式都是原始模式.如果可以得到除原始模式之外的新模式，则可以得到更多的模式信息，并进一步提升聚类效果，从而提高分类器性能.鉴于此，本文借助Universum学习的优点[59]，提出基于Universum学习的核聚类（Universum learningbased Kernel Clustering， UKC）方法.首先利用文献[9]中使用的方法，通过Universum学习生成更多有用的Universum模式，然后把这些Universum模式和原始模式都用到原始的KC中，从而提升聚类效果.
1UKC方法
1.1生成Universum模式
采用文献[9]中使用的方法来创建Universum模式.假设有两类模式集，分别从一个类中选取一个模式，然后计算这两个模式的均值，从而得到一个Universum模式.若两类分别有a，b个模式，则可以得到a×b个Universum模式.
1.2KC生成簇
利用文献[13]的方法生成簇.对一个两类问题，把其中一类作为目标类，另一类作为非目标类.计算目标类中尚未被簇所覆盖的模式的均值，并逐步扩大簇，直到遇到一个非目标类模式为止，则一个簇生成完毕.针对该目标类，重复上述步骤，直到目标类中的每个模式都至少被一个目标簇所覆盖.
1.3更新簇
原始KC算法生成的簇仅包含原始训练模式的信息，而Universum模式往往包含更多的模式信息.为此，本文提出的UKC方法中，使用Universum模式来更新生成的簇，从而使得簇中包含更多的模式信息，并进一步提升分类器性能.
假设有Universum模式集U={u1，u2，…，um}，相应的簇集为C={C1，C2，…，Cn}.对任一簇Cj，其内部所包含的Universum模式集为Uj={uj1，uj2，…，ujp}，训练模式集为Dj={dj1，dj2，…，djq}.
随后计算该簇中所有模式的均值，即μj=（dj1+dj2+…+djq+uj1+uj2+…+ujp）/（p+q）.再计算Uj和Dj中所有模式到μj的距离，并记最大值为σj.从而，该簇的中心被更新为μj，宽度被更新为σj.
通过如上步骤，可以在Universum模式的帮助下，更新已有的簇，从而使得这些簇更加符合模式的结构、分布和信息.
2实验
2.1实验设置
首先选择24个UCI Machine Learning Repository数据集和5个图像数据集作为实验数据（见表1），然后比较UKC或KC中生成的簇对分类器性能的影响.相关分类器为局部多核学习（Localized Multiple Kernel Learning， LMKL）[19]，三层结构的HoKashyap修正算法（Threefold Structured Modified HoKashyap Algorithm， TSMHKA）[20]，基于切割的规范化图像分割（Normalized Cutbased Graph Partitioning， NCGP）[21]，多分类器系统（Multiple Classifier System， MCS）[22]，径向基网络学习（Radial Basis Function Network Learning， RBFNL）[23]和多局部化的经验核学习（Multiple Localized Empirical Kernel Learning， MLEKL）[24].最后，为验证Universum学习对KC的有效性，USVM和SUSVM也被用于实验.进一步，为选择所有分类器的最佳参数，本文采用文献[25]中的调参方式.
2.2实验分析
表2给出了使用KC和UKC时，生成的簇对相关分类器的平均性能影响.USVM和SUSVM的实验结果也在表2中给出.这里，性能对比主要体现在分类正确率、泛化性能、计算复杂性和计算效率方面.分类正确率越高，分类器对实际分类问题的预测能力越好；泛化性能越高，分类器对未知模式的预测能力越好；计算复杂性越高，分类器的复杂度越高，对问题的适应能力越差；计算效率越高，分类器计算速度、算法执行等方面的性能越好.为方便性能对比，规定基于KC的LMKL的各个指标为1.泛化性能、计算复杂度和计算效率的计算方法都可以参考文献[25]中给出的方法.从表2可知：（1）UKC生成的簇可以带来更好的平均分类正确率、泛化性能和计算效率，计算复杂性更低；（2）就Universum学习而言，相比USVM和SUSVM，UKC可以给相关分类器带来更好的性能；（3）从计算复杂度和计算效率而言，UKC不仅可以降低分类器的复杂度，还能提高计算效率；（4）从泛化能力的角度看，UKC可以给分类器带来更好的性能，也能为基于局部结构的分类器设计提供一个更合适的指导方向.
3结束语
一个好的聚类方法在发现模式的局部结构和信
息方面有着重要的作用，且可以有效提高子类中所包含的模式信息的重要度.本文充分利用它们的优点并提出基于Universum学习的核聚类（UKC）方法.利用Universum学习生成相应的Universum模式，把这些模式用到原始的KC中，从而更新簇的信息.实验证实，具有UKC的分类器拥有更高的分类正确率和更低的泛化风险，同时在计算复杂性和计算效率上也具有优势.
参考文献：
[1]WESTON J， COLLOBERT R， SINZ F， et al. Inference with the Universum[C]//COHEN W， MCCALLUM A. Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh， Pennsylvania， USA： Carnegie Mellon University， 2006： 10091016.
[2]CHERKASSKY V， DAI Wuyang. Empirical study of the Universum SVM learning for highdimensional data[C]//ALIPPI C， POLYCARPOU M， PANAYIOTOU C， et al. Lecture Notes in Computer Science. Berlin： Springer， 2009： 932941.
[3]LIU D L， TIAN Y J， BIE R F， et al. SelfUniversum support vector machine[J]. Personal and Ubiquitous Computing， 2014， 18（8）： 18131819.
[4]CHEN S， ZHANG C S. Selecting informative Universum sample for semisupervised learning[C]//KITANO H. Proceedings of the 21st International Joint Conference on Artifical Intelligence. Pasadena， California， USA： Morgan Kaufmann， 2009， 38（4）： 10161021.
[5]ZHANG D， WANG J D， SI L. Document clustering with Universum[C]//MA W Y， NIE J Y. Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York， USA： ACM， 2011： 873882.
[6]PENG B， QIAN G， MA Y Q. Viewinvariant pose recognition using multilinear analysis and the Universum[C]//BEBIS G， BOYLE R， PARVIN B， et al. Lecture Notes in Computer Science. Berlin： Springer， 2008： 581591.
[7]SHEN C H， WANG P， SHEN F M， et al. Uboost： boosting with the Universum[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 825832.
[8]CHEN X H， CHEN S C， XUE H. Universum linear discriminant analysis[J]. Electronics Letters， 2012， 48（22）： 14071409.
[9]WANG Z， ZHU Y J， LIU W W， et al. Multiview learning with Universum[J]. KnowledgeBased Systems， 2014， 70（C）： 376391.
[10]任蕾， 施朝健， 冉鑫. 结合局部和全局显著性的海上小目标检测[J]. 上海海事大学学报， 2012， 33（2）： 15.
[11]DAY W H E， EDELSBRUNNER H. Efficient algorithms for agglomerative hierarchical clustering methods[J]. Journal of Classification， 1984， 1（1）： 724.
[12]HARTIGAN J A， WONG M A. Algorithm AS 136： a kmeans clustering algorithm[J]. Applied Statistics， 1978， 28（1）： 100108.
[13]GAO D Q， LI J. Kernel fisher discriminants and kernel nearest neighbor classifiers： a comparative study for largescale learning problems[C]//SHI B E. International Joint Conference on Neural Networks. Vancouver， Bc， Canada： IEEE， 2006： 13331338.
[14]NENE S A， NAYAR S K， MURASE H. Columbia object image library （COIL20）[R]. New York， USA： Columbia University， 1996.
[15]CUN L Y， BOSER B， DENKER J S， et al. Handwritten digit recognition with a backpropagation network[J]. Advances in Neural Information Processing Systems， 1990： 396404.
[16]BENNETT F， RICHARDSON T， HARTER A. Teleportingmaking applications mobile[C]//Mobile Computing Systems and Applications. Washington， DC， USA： IEEE Computer Society （IEEE）， 1994： 8284.
[17]KUMAR N， BERG A C， BELHUMEUR P N， et al. Attribute and simile classifiers for face verification[C]//International Conference on Computer Vision. Kyoto， Japan： IEEE， 2009， 30（2）： 365372.
[18]SMITH B A， YIN Q， FEINER S K， et al. Gaze locking： passive eye contact detection for humanobject interaction[C]//Proceedings of the 26th Annual ACM Symposium on User Interface Software and Technology. New York， USA： ACM， 2013： 271280.
[19]GONEN M， ALPAYDIN E. Localized multiple kernel learning[C]//COHEN W. Proceedings of the 25th International Conference on Machine Learning. Helsinki， Finland： University of Helsinki， 2008： 352359.
[20]WANG Z， ZHU C M， GAO D Q， et al. Threefold structured classifier design based on matrix pattern[J]. Pattern Recognition， 2013， 46（6）： 15321555.
[21]SEN D， GUPTA N， PAL S K. Incorporating local image structure in normalized cut based graph partitioning for grouping of pixels[J]. Information Sciences， 2013， 248： 214238.
[22]CHAN P P K， YEUNG D S， NG W W Y， et al. Dynamic fusion method using localized generalization error model[J]. Information Sciences， 2012， 217： 120.
[23]YEUNG D S， CHAN P P K， NG W W Y. Radial basis function network learning using localized generalization error bound[J]. Information Sciences， 2009， 179（19）： 31993127.
[24]WANG Z， XU J， GAO D Q， et al. Multiple empirical kernel learning based on local information[J]. Neural Computing and Applications， 2013， 23（7/8）： 21132120.
[25]ZHU C M， GAO D Q. Multiple matrix learning machine with five aspects of pattern information[J]. KnowledgeBased Systems， 2015， 83： 1331.
（编辑赵勉）
摘要：
为解决原始核聚类（Kernel Clustering， KC）中模式信息不足、聚类结果不佳的缺点，以KC为基础，利用Universum学习带来的优势，提出基于Universum学习的核聚类（Universum learningbased Kernel Clustering， UKC）方法.首先利用Universum学习生成相应的Universum模式，再利用KC算法把数据集分割成多个簇，最后利用每个簇中所包含的Universum模式和训练模式来更新该簇，从而使得这些簇更加合理.实验表明，该算法可以更好地改善聚类效果和分类器的分类性能、泛化能力和计算效率.虽然该方法的步骤比KC多，但是其较好的聚类性能可以帮助人们处理分类问题.
关键词：
Universum学习； 核聚类； 先验知识
0引言
Universum学习由WESTON等[1]提出，旨在把有关应用域的先验知识引入到学习过程中.这些知识是以附加的无标签的和有标签的训练模式的形式表示的.基于Universum的优点，CHERKASSKY等[2]提出基于Universum的支持向量机（Universum Support Vector Machine， USVM），LIU等[3]提出自学习的Universum下的支持向量机（SelfUniversum Support Vector Machine， SUSVM）.笔者把USVM与支持向量机（Support Vector Machine，SVM）进行比较，发现Universum模式的质量会影响分类器的性能.CHEN等[4]发现在目标类之间分布的Universum模式对生成分类界面更有用.由相关实验可知，Universum学习可使模型更符合模式分布、结构等，从而提高算法有效性.如今Universum学习已广泛运用于文本聚类[5]、身体姿势识别[6]、Boosting策略[7]、降维技术[8]和多视角学习[9]等方面.
大部分数据集拥有可以改进分类器性能的局部信息或结构[10]，而聚类是得到这些局部信息或结构的一个较好的方法.聚类旨在把一个由所有模式组成的全局空间分成多个子集，这些子集被称为簇、核或子类.它们有较高的簇内相似度和较低的簇间相似度.一般地，每个簇也可被看作一个局部空间.典型的聚类方法有k均值（kmeans）[11]、合成聚类（Agglomerative Hierarchical Clustering， AHC）[12]和核聚类（Kernel Clustering， KC）[13].通过聚类，可以更好地挖掘模式的局部结构信息.然而，k均值和AHC或生成的簇不一定合适，或计算复杂度高，或聚簇结果对初始设置敏感，所以相比而言，KC才是一个比较合适的聚类方法.
尽管如此，KC所使用的模式都是原始模式.如果可以得到除原始模式之外的新模式，则可以得到更多的模式信息，并进一步提升聚类效果，从而提高分类器性能.鉴于此，本文借助Universum学习的优点[59]，提出基于Universum学习的核聚类（Universum learningbased Kernel Clustering， UKC）方法.首先利用文献[9]中使用的方法，通过Universum学习生成更多有用的Universum模式，然后把这些Universum模式和原始模式都用到原始的KC中，从而提升聚类效果.
1UKC方法
1.1生成Universum模式
采用文献[9]中使用的方法来创建Universum模式.假设有两类模式集，分别从一个类中选取一个模式，然后计算这两个模式的均值，从而得到一个Universum模式.若两类分别有a，b个模式，则可以得到a×b个Universum模式.
1.2KC生成簇
利用文献[13]的方法生成簇.对一个两类问题，把其中一类作为目标类，另一类作为非目标类.计算目标类中尚未被簇所覆盖的模式的均值，并逐步扩大簇，直到遇到一个非目标类模式为止，则一个簇生成完毕.针对该目标类，重复上述步骤，直到目标类中的每个模式都至少被一个目标簇所覆盖.
1.3更新簇
原始KC算法生成的簇仅包含原始训练模式的信息，而Universum模式往往包含更多的模式信息.为此，本文提出的UKC方法中，使用Universum模式来更新生成的簇，从而使得簇中包含更多的模式信息，并进一步提升分类器性能.
假设有Universum模式集U={u1，u2，…，um}，相应的簇集为C={C1，C2，…，Cn}.对任一簇Cj，其内部所包含的Universum模式集为Uj={uj1，uj2，…，ujp}，训练模式集为Dj={dj1，dj2，…，djq}.
随后计算该簇中所有模式的均值，即μj=（dj1+dj2+…+djq+uj1+uj2+…+ujp）/（p+q）.再计算Uj和Dj中所有模式到μj的距离，并记最大值为σj.从而，该簇的中心被更新为μj，宽度被更新为σj.
通过如上步骤，可以在Universum模式的帮助下，更新已有的簇，从而使得这些簇更加符合模式的结构、分布和信息.
2实验
2.1实验设置
首先选择24个UCI Machine Learning Repository数据集和5个图像数据集作为实验数据（见表1），然后比较UKC或KC中生成的簇对分类器性能的影响.相关分类器为局部多核学习（Localized Multiple Kernel Learning， LMKL）[19]，三层结构的HoKashyap修正算法（Threefold Structured Modified HoKashyap Algorithm， TSMHKA）[20]，基于切割的规范化图像分割（Normalized Cutbased Graph Partitioning， NCGP）[21]，多分类器系统（Multiple Classifier System， MCS）[22]，径向基网络学习（Radial Basis Function Network Learning， RBFNL）[23]和多局部化的经验核学习（Multiple Localized Empirical Kernel Learning， MLEKL）[24].最后，为验证Universum学习对KC的有效性，USVM和SUSVM也被用于实验.进一步，为选择所有分类器的最佳参数，本文采用文献[25]中的调参方式.
2.2实验分析
表2给出了使用KC和UKC时，生成的簇对相关分类器的平均性能影响.USVM和SUSVM的实验结果也在表2中给出.这里，性能对比主要体现在分类正确率、泛化性能、计算复杂性和计算效率方面.分类正确率越高，分类器对实际分类问题的预测能力越好；泛化性能越高，分类器对未知模式的预测能力越好；计算复杂性越高，分类器的复杂度越高，对问题的适应能力越差；计算效率越高，分类器计算速度、算法执行等方面的性能越好.为方便性能对比，规定基于KC的LMKL的各个指标为1.泛化性能、计算复杂度和计算效率的计算方法都可以参考文献[25]中给出的方法.从表2可知：（1）UKC生成的簇可以带来更好的平均分类正确率、泛化性能和计算效率，计算复杂性更低；（2）就Universum学习而言，相比USVM和SUSVM，UKC可以给相关分类器带来更好的性能；（3）从计算复杂度和计算效率而言，UKC不仅可以降低分类器的复杂度，还能提高计算效率；（4）从泛化能力的角度看，UKC可以给分类器带来更好的性能，也能为基于局部结构的分类器设计提供一个更合适的指导方向.
3结束语
一个好的聚类方法在发现模式的局部结构和信
息方面有着重要的作用，且可以有效提高子类中所包含的模式信息的重要度.本文充分利用它们的优点并提出基于Universum学习的核聚类（UKC）方法.利用Universum学习生成相应的Universum模式，把这些模式用到原始的KC中，从而更新簇的信息.实验证实，具有UKC的分类器拥有更高的分类正确率和更低的泛化风险，同时在计算复杂性和计算效率上也具有优势.
参考文献：
[1]WESTON J， COLLOBERT R， SINZ F， et al. Inference with the Universum[C]//COHEN W， MCCALLUM A. Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh， Pennsylvania， USA： Carnegie Mellon University， 2006： 10091016.
[2]CHERKASSKY V， DAI Wuyang. Empirical study of the Universum SVM learning for highdimensional data[C]//ALIPPI C， POLYCARPOU M， PANAYIOTOU C， et al. Lecture Notes in Computer Science. Berlin： Springer， 2009： 932941.
[3]LIU D L， TIAN Y J， BIE R F， et al. SelfUniversum support vector machine[J]. Personal and Ubiquitous Computing， 2014， 18（8）： 18131819.
[4]CHEN S， ZHANG C S. Selecting informative Universum sample for semisupervised learning[C]//KITANO H. Proceedings of the 21st International Joint Conference on Artifical Intelligence. Pasadena， California， USA： Morgan Kaufmann， 2009， 38（4）： 10161021.
[5]ZHANG D， WANG J D， SI L. Document clustering with Universum[C]//MA W Y， NIE J Y. Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York， USA： ACM， 2011： 873882.
[6]PENG B， QIAN G， MA Y Q. Viewinvariant pose recognition using multilinear analysis and the Universum[C]//BEBIS G， BOYLE R， PARVIN B， et al. Lecture Notes in Computer Science. Berlin： Springer， 2008： 581591.
[7]SHEN C H， WANG P， SHEN F M， et al. Uboost： boosting with the Universum[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 825832.
[8]CHEN X H， CHEN S C， XUE H. Universum linear discriminant analysis[J]. Electronics Letters， 2012， 48（22）： 14071409.
[9]WANG Z， ZHU Y J， LIU W W， et al. Multiview learning with Universum[J]. KnowledgeBased Systems， 2014， 70（C）： 376391.
[10]任蕾， 施朝健， 冉鑫. 结合局部和全局显著性的海上小目标检测[J]. 上海海事大学学报， 2012， 33（2）： 15.
[11]DAY W H E， EDELSBRUNNER H. Efficient algorithms for agglomerative hierarchical clustering methods[J]. Journal of Classification， 1984， 1（1）： 724.
[12]HARTIGAN J A， WONG M A. Algorithm AS 136： a kmeans clustering algorithm[J]. Applied Statistics， 1978， 28（1）： 100108.
[13]GAO D Q， LI J. Kernel fisher discriminants and kernel nearest neighbor classifiers： a comparative study for largescale learning problems[C]//SHI B E. International Joint Conference on Neural Networks. Vancouver， Bc， Canada： IEEE， 2006： 13331338.
[14]NENE S A， NAYAR S K， MURASE H. Columbia object image library （COIL20）[R]. New York， USA： Columbia University， 1996.
[15]CUN L Y， BOSER B， DENKER J S， et al. Handwritten digit recognition with a backpropagation network[J]. Advances in Neural Information Processing Systems， 1990： 396404.
[16]BENNETT F， RICHARDSON T， HARTER A. Teleportingmaking applications mobile[C]//Mobile Computing Systems and Applications. Washington， DC， USA： IEEE Computer Society （IEEE）， 1994： 8284.
[17]KUMAR N， BERG A C， BELHUMEUR P N， et al. Attribute and simile classifiers for face verification[C]//International Conference on Computer Vision. Kyoto， Japan： IEEE， 2009， 30（2）： 365372.
[18]SMITH B A， YIN Q， FEINER S K， et al. Gaze locking： passive eye contact detection for humanobject interaction[C]//Proceedings of the 26th Annual ACM Symposium on User Interface Software and Technology. New York， USA： ACM， 2013： 271280.
[19]GONEN M， ALPAYDIN E. Localized multiple kernel learning[C]//COHEN W. Proceedings of the 25th International Conference on Machine Learning. Helsinki， Finland： University of Helsinki， 2008： 352359.
[20]WANG Z， ZHU C M， GAO D Q， et al. Threefold structured classifier design based on matrix pattern[J]. Pattern Recognition， 2013， 46（6）： 15321555.
[21]SEN D， GUPTA N， PAL S K. Incorporating local image structure in normalized cut based graph partitioning for grouping of pixels[J]. Information Sciences， 2013， 248： 214238.
[22]CHAN P P K， YEUNG D S， NG W W Y， et al. Dynamic fusion method using localized generalization error model[J]. Information Sciences， 2012， 217： 120.
[23]YEUNG D S， CHAN P P K， NG W W Y. Radial basis function network learning using localized generalization error bound[J]. Information Sciences， 2009， 179（19）： 31993127.
[24]WANG Z， XU J， GAO D Q， et al. Multiple empirical kernel learning based on local information[J]. Neural Computing and Applications， 2013， 23（7/8）： 21132120.
[25]ZHU C M， GAO D Q. Multiple matrix learning machine with five aspects of pattern information[J]. KnowledgeBased Systems， 2015， 83： 1331.
（编辑赵勉）
