基于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.

（編輯趙勉）