基于Universum學(xué)習(xí)的核聚類方法

朱昌明　吳愛華　王健安

摘要：

為解決原始核聚類（Kernel Clustering， KC）中模式信息不足、聚類結(jié)果不佳的缺點(diǎn)，以KC為基礎(chǔ)，利用Universum學(xué)習(xí)帶來的優(yōu)勢(shì)，提出基于Universum學(xué)習(xí)的核聚類（Universum learningbased Kernel Clustering， UKC）方法.首先利用Universum學(xué)習(xí)生成相應(yīng)的Universum模式，再利用KC算法把數(shù)據(jù)集分割成多個(gè)簇，最后利用每個(gè)簇中所包含的Universum模式和訓(xùn)練模式來更新該簇，從而使得這些簇更加合理.實(shí)驗(yàn)表明，該算法可以更好地改善聚類效果和分類器的分類性能、泛化能力和計(jì)算效率.雖然該方法的步驟比KC多，但是其較好的聚類性能可以幫助人們處理分類問題.

關(guān)鍵詞：

Universum學(xué)習(xí)； 核聚類； 先驗(yàn)知識(shí)

0引言

Universum學(xué)習(xí)由WESTON等[1]提出，旨在把有關(guān)應(yīng)用域的先驗(yàn)知識(shí)引入到學(xué)習(xí)過程中.這些知識(shí)是以附加的無標(biāo)簽的和有標(biāo)簽的訓(xùn)練模式的形式表示的.基于Universum的優(yōu)點(diǎn)，CHERKASSKY等[2]提出基于Universum的支持向量機(jī)（Universum Support Vector Machine， USVM），LIU等[3]提出自學(xué)習(xí)的Universum下的支持向量機(jī)（SelfUniversum Support Vector Machine， SUSVM）.筆者把USVM與支持向量機(jī)（Support Vector Machine，SVM）進(jìn)行比較，發(fā)現(xiàn)Universum模式的質(zhì)量會(huì)影響分類器的性能.CHEN等[4]發(fā)現(xiàn)在目標(biāo)類之間分布的Universum模式對(duì)生成分類界面更有用.由相關(guān)實(shí)驗(yàn)可知，Universum學(xué)習(xí)可使模型更符合模式分布、結(jié)構(gòu)等，從而提高算法有效性.如今Universum學(xué)習(xí)已廣泛運(yùn)用于文本聚類[5]、身體姿勢(shì)識(shí)別[6]、Boosting策略[7]、降維技術(shù)[8]和多視角學(xué)習(xí)[9]等方面.

大部分?jǐn)?shù)據(jù)集擁有可以改進(jìn)分類器性能的局部信息或結(jié)構(gòu)[10]，而聚類是得到這些局部信息或結(jié)構(gòu)的一個(gè)較好的方法.聚類旨在把一個(gè)由所有模式組成的全局空間分成多個(gè)子集，這些子集被稱為簇、核或子類.它們有較高的簇內(nèi)相似度和較低的簇間相似度.一般地，每個(gè)簇也可被看作一個(gè)局部空間.典型的聚類方法有k均值（kmeans）[11]、合成聚類（Agglomerative Hierarchical Clustering， AHC）[12]和核聚類（Kernel Clustering， KC）[13].通過聚類，可以更好地挖掘模式的局部結(jié)構(gòu)信息.然而，k均值和AHC或生成的簇不一定合適，或計(jì)算復(fù)雜度高，或聚簇結(jié)果對(duì)初始設(shè)置敏感，所以相比而言，KC才是一個(gè)比較合適的聚類方法.

盡管如此，KC所使用的模式都是原始模式.如果可以得到除原始模式之外的新模式，則可以得到更多的模式信息，并進(jìn)一步提升聚類效果，從而提高分類器性能.鑒于此，本文借助Universum學(xué)習(xí)的優(yōu)點(diǎn)[59]，提出基于Universum學(xué)習(xí)的核聚類（Universum learningbased Kernel Clustering， UKC）方法.首先利用文獻(xiàn)[9]中使用的方法，通過Universum學(xué)習(xí)生成更多有用的Universum模式，然后把這些Universum模式和原始模式都用到原始的KC中，從而提升聚類效果.

1UKC方法

1.1生成Universum模式

采用文獻(xiàn)[9]中使用的方法來創(chuàng)建Universum模式.假設(shè)有兩類模式集，分別從一個(gè)類中選取一個(gè)模式，然后計(jì)算這兩個(gè)模式的均值，從而得到一個(gè)Universum模式.若兩類分別有a，b個(gè)模式，則可以得到a×b個(gè)Universum模式.

1.2KC生成簇

利用文獻(xiàn)[13]的方法生成簇.對(duì)一個(gè)兩類問題，把其中一類作為目標(biāo)類，另一類作為非目標(biāo)類.計(jì)算目標(biāo)類中尚未被簇所覆蓋的模式的均值，并逐步擴(kuò)大簇，直到遇到一個(gè)非目標(biāo)類模式為止，則一個(gè)簇生成完畢.針對(duì)該目標(biāo)類，重復(fù)上述步驟，直到目標(biāo)類中的每個(gè)模式都至少被一個(gè)目標(biāo)簇所覆蓋.

1.3更新簇

原始KC算法生成的簇僅包含原始訓(xùn)練模式的信息，而Universum模式往往包含更多的模式信息.為此，本文提出的UKC方法中，使用Universum模式來更新生成的簇，從而使得簇中包含更多的模式信息，并進(jìn)一步提升分類器性能.

假設(shè)有Universum模式集U={u1，u2，…，um}，相應(yīng)的簇集為C={C1，C2，…，Cn}.對(duì)任一簇Cj，其內(nèi)部所包含的Universum模式集為Uj={uj1，uj2，…，ujp}，訓(xùn)練模式集為Dj={dj1，dj2，…，djq}.

隨后計(jì)算該簇中所有模式的均值，即μj=（dj1+dj2+…+djq+uj1+uj2+…+ujp）/（p+q）.再計(jì)算Uj和Dj中所有模式到μj的距離，并記最大值為σj.從而，該簇的中心被更新為μj，寬度被更新為σj.

通過如上步驟，可以在Universum模式的幫助下，更新已有的簇，從而使得這些簇更加符合模式的結(jié)構(gòu)、分布和信息.

2實(shí)驗(yàn)

2.1實(shí)驗(yàn)設(shè)置

首先選擇24個(gè)UCI Machine Learning Repository數(shù)據(jù)集和5個(gè)圖像數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)（見表1），然后比較UKC或KC中生成的簇對(duì)分類器性能的影響.相關(guān)分類器為局部多核學(xué)習(xí)（Localized Multiple Kernel Learning， LMKL）[19]，三層結(jié)構(gòu)的HoKashyap修正算法（Threefold Structured Modified HoKashyap Algorithm， TSMHKA）[20]，基于切割的規(guī)范化圖像分割（Normalized Cutbased Graph Partitioning， NCGP）[21]，多分類器系統(tǒng)（Multiple Classifier System， MCS）[22]，徑向基網(wǎng)絡(luò)學(xué)習(xí)（Radial Basis Function Network Learning， RBFNL）[23]和多局部化的經(jīng)驗(yàn)核學(xué)習(xí)（Multiple Localized Empirical Kernel Learning， MLEKL）[24].最后，為驗(yàn)證Universum學(xué)習(xí)對(duì)KC的有效性，USVM和SUSVM也被用于實(shí)驗(yàn).進(jìn)一步，為選擇所有分類器的最佳參數(shù)，本文采用文獻(xiàn)[25]中的調(diào)參方式.

2.2實(shí)驗(yàn)分析

表2給出了使用KC和UKC時(shí)，生成的簇對(duì)相關(guān)分類器的平均性能影響.USVM和SUSVM的實(shí)驗(yàn)結(jié)果也在表2中給出.這里，性能對(duì)比主要體現(xiàn)在分類正確率、泛化性能、計(jì)算復(fù)雜性和計(jì)算效率方面.分類正確率越高，分類器對(duì)實(shí)際分類問題的預(yù)測(cè)能力越好；泛化性能越高，分類器對(duì)未知模式的預(yù)測(cè)能力越好；計(jì)算復(fù)雜性越高，分類器的復(fù)雜度越高，對(duì)問題的適應(yīng)能力越差；計(jì)算效率越高，分類器計(jì)算速度、算法執(zhí)行等方面的性能越好.為方便性能對(duì)比，規(guī)定基于KC的LMKL的各個(gè)指標(biāo)為1.泛化性能、計(jì)算復(fù)雜度和計(jì)算效率的計(jì)算方法都可以參考文獻(xiàn)[25]中給出的方法.從表2可知：（1）UKC生成的簇可以帶來更好的平均分類正確率、泛化性能和計(jì)算效率，計(jì)算復(fù)雜性更低；（2）就Universum學(xué)習(xí)而言，相比USVM和SUSVM，UKC可以給相關(guān)分類器帶來更好的性能；（3）從計(jì)算復(fù)雜度和計(jì)算效率而言，UKC不僅可以降低分類器的復(fù)雜度，還能提高計(jì)算效率；（4）從泛化能力的角度看，UKC可以給分類器帶來更好的性能，也能為基于局部結(jié)構(gòu)的分類器設(shè)計(jì)提供一個(gè)更合適的指導(dǎo)方向.

3結(jié)束語

一個(gè)好的聚類方法在發(fā)現(xiàn)模式的局部結(jié)構(gòu)和信

息方面有著重要的作用，且可以有效提高子類中所包含的模式信息的重要度.本文充分利用它們的優(yōu)點(diǎn)并提出基于Universum學(xué)習(xí)的核聚類（UKC）方法.利用Universum學(xué)習(xí)生成相應(yīng)的Universum模式，把這些模式用到原始的KC中，從而更新簇的信息.實(shí)驗(yàn)證實(shí)，具有UKC的分類器擁有更高的分類正確率和更低的泛化風(fēng)險(xiǎn)，同時(shí)在計(jì)算復(fù)雜性和計(jì)算效率上也具有優(yōu)勢(shì).

參考文獻(xiàn)：

[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]任蕾， 施朝健， 冉鑫. 結(jié)合局部和全局顯著性的海上小目標(biāo)檢測(cè)[J]. 上海海事大學(xué)學(xué)報(bào)， 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.

（編輯趙勉）