劉　正,張國印,陳志遠(yuǎn)

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001)

?

基于特征加權(quán)和非負(fù)矩陣分解的多視角聚類算法

劉正,張國印,陳志遠(yuǎn)

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001)

摘要：為了在多視角聚類過程中同時考慮特征權(quán)重和數(shù)據(jù)高維性問題,提出一種基于特征加權(quán)和非負(fù)矩陣分解的多視角聚類算法(Multiview Clustering Algorithm based on Feature Weighting and Non-negative Matrix Factorization,FWNMF-MC).FWNMF-MC算法根據(jù)每個視角中每個特征在聚類過程中的重要性,自動賦予不同的權(quán)值.通過將每個視角空間中的特征矩陣分解為基矩陣與系數(shù)矩陣的乘積,將多視角數(shù)據(jù)從高維空間映射到低維空間.為了有效利用每個視角信息挖掘聚簇結(jié)構(gòu),最大化每個視角在低維空間的一致性.最后實(shí)驗(yàn)結(jié)果表明FWNMF-MC算法的聚類效果明顯優(yōu)于已有的4種有代表性的多視角聚類算法.

關(guān)鍵詞:多視角數(shù)據(jù);聚類;非負(fù)矩陣分解;特征權(quán)重

1引言

由于多視角聚類區(qū)別看待不同視角的信息,融合多種視角信息以提高聚類效果,是近年來備受關(guān)注的聚類范式.Grigorios等[1,2]通過泛化單視角混合模型提出基于范例混合模型的多視角聚類算法(Convex Mixture Models,CMMs).Long等[3]通過引入映射函數(shù),使得不同空間的模式具有可比性,從多個視角中學(xué)習(xí)最佳聚類模式.Bicke等[4]提出基于模型的多視角EM(Expectation-Maximization)算法.Blaschko等[5]提出了一種基于核典型相關(guān)分析的雙視角聚類算法(Kernel Canonical Correlation Analysis,KCCA),通過核典型相關(guān)分析將多視角數(shù)據(jù)映射到典型變量相關(guān)性較強(qiáng)的空間.Chaudhuri等[6]利用高斯和對數(shù)模型表示數(shù)據(jù)分布特性,通過CCA(Canonical Correlation Analysis)將多視角數(shù)據(jù)映射到子空間.Yu等[7]提出協(xié)同概率語義分析的方法(C-PLSA,Collaborative Probabilistic Latent Semantic Analysis),將兩個視角聚類結(jié)果的一致性最大化問題轉(zhuǎn)化為正則化問題.Zhuang等[8]考慮到特征主題對聚類結(jié)果的影響,提出基于PLSA(Collaborative Probabilistic Latent Semantic Analysis)的多視角學(xué)習(xí)算法.Tzortzis等[9]提出基于核的多視角聚類方法,利用核矩陣表示每個視角的信息.Liu等[10]考慮的數(shù)據(jù)的高維性,將特征矩陣分解為低維子空間基向量的線性組合,將高維多視角數(shù)據(jù)映射到低維空間.為了探測多視角數(shù)據(jù)內(nèi)部隱藏的任意形狀的聚簇結(jié)構(gòu),提出了基于譜圖劃分的多視角聚類算法[11～13].Bruno等[14]利用PLSA模型建立每個視角聚簇之間的關(guān)系,然后利用EM方法估計(jì)PLSA模型參數(shù),得到每個數(shù)據(jù)的后驗(yàn)概率.

以上多視角聚類算法并沒有考慮特征權(quán)重問題,然而多視角數(shù)據(jù)每個視角的特征對聚類的貢獻(xiàn)不同,應(yīng)該區(qū)別看待,不能簡單地將每個特征權(quán)重假設(shè)為1.為了考慮多視角數(shù)據(jù)的特征權(quán)重的問題,Chen等[15]基于k-means提出特征加權(quán)多視角聚類算法TW-k-means.TW-k-means算法根據(jù)特征的重要性,對特征賦予不同的權(quán)值.雖然基于k-means的特征加權(quán)多視角聚類算法TW-k-means考慮了數(shù)據(jù)特征權(quán)重[15],但是TW-k-means算法并沒有考慮數(shù)據(jù)高維性問題.然而多視角數(shù)據(jù)往往具有較高的特征維度,數(shù)據(jù)的高維性容易使聚類過程陷入“維數(shù)災(zāi)難”,影響聚類效果.

為了同時考慮多視角數(shù)據(jù)特征權(quán)重以及高維性問題,本文提出基于特征權(quán)重和非負(fù)矩陣分解的多視角聚類算法(FWNMF-MC).FWNMF-MC算法根據(jù)每個視角中不同特征對聚類過程的不同影響,自動賦予不同的權(quán)值.利用低維空間中基向量的線性組合重構(gòu)每個視角中原始空間中的特征向量,獲得多視角數(shù)據(jù)的低維表示,將多視角數(shù)據(jù)從高維空間映射到低維空間,解決數(shù)據(jù)的高維性問題.然后為了融合每個視角的信息,求解與每個視角的系數(shù)矩陣較近似的一致系數(shù)矩陣,根據(jù)一致系數(shù)矩陣得到聚類結(jié)果.

2基于特征加權(quán)和矩陣分解的多視角聚類算法

2.1建立模型

(1)

U(t),V(t),V*≥0

(2)

(3)

其中括號內(nèi)的值為Q(t)對角元素.矩陣U(t)正則化為UQ-1.因?yàn)閁VT=(UQ-1) (QVT),則相應(yīng)的矩陣V(t)正則化為V(t)Q(t).優(yōu)化問題(1)等價(jià)于如下優(yōu)化問題:

(4)

(5)

2.2迭代更新規(guī)則

2.2.1迭代更新W(t)

(6)

2.2.2迭代更新U(t)

固定矩陣V(t)、V*和W(t),以U(t)為變量最小化目標(biāo)函數(shù)J(U(t)).設(shè)φ為限制條件U≥0的拉格朗日因子,構(gòu)造如下拉格朗日函數(shù):

L(U(t))=tr(V(t)(U(t))TW(t)U(t)(V(t))T

-2V(t)(U(t))TW(t)X(t))+λtR(t)

+tr(φU(t))

其中R(t)=tr(V(t)Q(t)(Q(t))T(V(t))T

-2V(t)Q(t)(V*)T)

由等式(3)知:

求解R(t)關(guān)于U(t)的偏導(dǎo)數(shù)

由Karush-Kuhn-Tucker (KKT)條件知

-2W(t)X(t)V(t)+λtP(t)+φ

=0

(7)

(8)

根據(jù)式(7)和(8),可推導(dǎo)出以下更新規(guī)則

(9)

2.2.3迭代更新V(t)

固定矩陣U(t)、V*和W(t),以V(t)為變量最小化目標(biāo)函數(shù)J(V(t)).對于每個視角t(1≤t≤T),首先利用式(3)定義的矩陣Q(t)正則化矩陣U(t)的列向量:

U(t)←U(t)(Q(t))-1,V(t)←V(t)Q(t).

L(V(t))=tr(V(t)(U(t))TW(t)U(t)(V(t))T

-2V(t)(U(t))TW(t)X(t))

利用KKT條件,可得:

=0

(10)

(11)

由式(10)和(11)可得如下更新規(guī)則:

(12)

2.2.4迭代更新V*

固定矩陣U(t)、V(t)和W(t),以V*為變量最小化目標(biāo)函數(shù)J(V(t)).設(shè)η是約束條件V*≥0的拉格朗日乘子矩陣,構(gòu)建拉格朗日函數(shù)如下:

求解上式L(V*)關(guān)于V*的導(dǎo)數(shù),并令其為零

(13)

(14)

由式(13)和(14)可得如下更新規(guī)則:

(15)

綜上,FWNMF-MC算法計(jì)算步驟描述如算法1

2.3時間復(fù)雜度分析

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

3.1數(shù)據(jù)集介紹

3-Sources數(shù)據(jù)集是同時由BBC、Reuters和The Guardian三家新聞社報(bào)道的169條新聞組成.

Reuters Multilingual數(shù)據(jù)集是同時由5種語言描述的文本組成,將英文、德語和法語描述文本作為三個視角.

MSRC-v1數(shù)據(jù)集包含21個類別圖像[18],實(shí)驗(yàn)選擇其中7個類別.采用整體視覺特征(GVF,Global Visual Features)、局部視覺特征(LVF,Local Visual Features)作為第一和第二視角.

UCI Handwritten Digit數(shù)據(jù)集包含2000個0～9手寫數(shù)字圖像.

IAPR TC-12 Benchmark包含20000張照片和相應(yīng)的文本標(biāo)注信息.分別從類別building、mountain和 bicycle中隨機(jī)選出300張圖像,分別將文本標(biāo)注和圖像特征作為第一和第二視角.

3.2多視角聚類算法聚類效果對比分析

將FWNMF-MC與已有的4種有代表性的多視角聚類算法的聚類效果進(jìn)行對比,已有的算法包括基于核相關(guān)分析的算法(KCCA)[5]、基于協(xié)同正則譜聚類的算法(Co-reguSC)[13]、基于加權(quán)k-means的多視角算法(TW-k-means)[15]和基于非負(fù)矩陣分解的算法(MultiNMF)[10].另外,為了驗(yàn)證FWNMF-MC算法利用多視角信息的提高聚類效果的能力,將FWNMF-MC算法在多視角上的聚類效果與單一視角上的聚類效果進(jìn)行對比.在每個視角上運(yùn)行FWNMF-MC算法,最優(yōu)視角的聚類結(jié)果用Best single-view表示.聚類個數(shù)K設(shè)為數(shù)據(jù)集中的真實(shí)類別個數(shù),另外由于算法具有一定的隨機(jī)性,將運(yùn)行20次實(shí)驗(yàn)的平均值作為統(tǒng)計(jì)結(jié)果.參數(shù)α(1),α(1)和α(2)均設(shè)置為0.7.

圖1所示是KCCA、Co-reguSC、TW-k-means、MultiNMF和FWNMF-MC算法在不同數(shù)據(jù)集上聚類結(jié)果的標(biāo)準(zhǔn)互信息值(Normalized Mutual Information,NMI)[19].首先FWNMF-MC算法的聚類效果明顯優(yōu)于其他聚類算法,原因在于:FWNMF-MC算法區(qū)別看待不同的特征,賦予不同的權(quán)值,而KCCA、Co-reguSC和MultiNMF算法同等看待不同特征對聚類過程的影響,忽略了不同特征之間的差別,影響聚類效果.TW-k-means算法雖然考慮了不同特征的權(quán)值,但未對數(shù)據(jù)進(jìn)行降維,而實(shí)驗(yàn)數(shù)據(jù)集均為高維數(shù)據(jù),容易陷入“維數(shù)災(zāi)難”.而FWNMF-MC算法將高維數(shù)據(jù)映射到低維空間,自動實(shí)現(xiàn)降維,一定程度減弱了“維數(shù)災(zāi)難”對聚類效果的不利影響.其次,FWNMF-MC算法在多視角上的聚類結(jié)果明顯優(yōu)于最優(yōu)的單一視角聚類結(jié)果,說明FWNMF-MC算法能夠有效利用多種視角信息提高聚類效果.

3.3參數(shù)分析

參數(shù)α是一個很重要的參數(shù),通過調(diào)控參數(shù)α值的大小來調(diào)控聚類過程．調(diào)節(jié)權(quán)值的分布,α值越大數(shù)據(jù)權(quán)重越大,X1值越小數(shù)據(jù)權(quán)重越小.α的不同取值影響聚類的質(zhì)量,圖2所示為FWNMF-MC算法在不同參數(shù)值下聚類結(jié)果的NMI值.結(jié)果表明參數(shù)α(1),α(2)和α(3)取值0.6和0.8之間時NMI值達(dá)到最高,所以在3.2小節(jié)的實(shí)驗(yàn)中參數(shù)α(1),α(2)和α(3)均設(shè)置為0.7.

3.4運(yùn)行時間分析

比較FWNMF-MC算法與KCCA、Co-reguSC、TW-k-means 和MultiNMF算法的運(yùn)行速度.本實(shí)驗(yàn)環(huán)境為:操作系統(tǒng)為Windows XP,開發(fā)平臺為Matlab7.0,內(nèi)存為2GB,CPU主頻為3GHz.圖4所示為在Reuters數(shù)據(jù)集上隨著樣本數(shù)目的增加各個算法運(yùn)行時間的變化情況.結(jié)果表明TW-k-means、MultiNMF和FWNMF-MC算法運(yùn)行速度快于KCCA和Co-reguSC.原因在于KCCA和Co-reguSC需要進(jìn)行矩陣特征分解,消耗較多的時間.FWNMF-MC算法運(yùn)行速度稍快于TW-k-means但稍慢于MultiNMF算法,原因在于TW-k-means和FWNMF-MC算法聚類過程中需要計(jì)算每個特征的權(quán)值,消耗了一部分時間.另外,圖3所示結(jié)果表明,隨著數(shù)據(jù)規(guī)模的增多,FWNMF-MC算法乘線性增長,表明FWNMF-MC算法適用于分析大規(guī)模數(shù)據(jù).

4結(jié)論

本文提出了一種基于特征加權(quán)和非負(fù)矩陣分解的多視角聚類算法(FWNMF-MC).FWNMF-MC算法考慮不同特征的差異性,對不同的特征賦予不同的權(quán)值.實(shí)驗(yàn)表明,FWNMF-MC與已有的算法相比,FWNMF-MC算法能夠取得更好的聚類效果.另外,FWNMF-MC算法適用于處理大規(guī)模數(shù)據(jù).FWNMF-MC算法需要預(yù)先指定聚類數(shù)目,下一步的主要工作是研究如何自動確定聚類數(shù)目.

參考文獻(xiàn)

[1]Tzortzis G,Likas A.Convex mixture models for multi-view clustering[A].Proceedings of the International Conference on Artificial Neural Networks.part II[C].Berlin:Springer,2009.205-214.

[2]Tzortzis G,Likas A.Multiple view clustering using a weighted combination of exemplar-based mixture Models[J].IEEE Transactions on Knowledge and Data Engineering,2010,21(12):1925-1938.

[3]Long B,Philip S Y,Zhang Z F.A general model for multiple view unsupervised learning[A].Proceedings of the 8th SIAM International Conference on Data Mining[C].Philadelphia,USA:SIAM,2008.822-833.

[4]Bickel S,Scheffer T.Multi-view clustering[A].Proceedings of the IEEE Intenational Conference on Data Mining[C].Piscataway,USA:IEEE,2004.19-26.

[5]Blaschko M B,Lampert C H.Correlational spectral clustering[A].Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition[C].Piscataway,USA:IEEE,2008.1-8.

[6]Chaudhuri K,Kakade S M,Livescu K,Sridharan K.Multiview clustering via canonical correlation analysis[A].Proceedings of the 26th Annual International Conference on Machine Learning[C].New York,USA:ACM,2009.129-136.

[7]Jiang Yu,Liu Jing,Li Ze-chao,Lu Han-qing.Collaborative PLSA for multi-view clustering[A].Proceeding of the 21st International Conference on Pattern Recognition[C].Piscataway,USA:IEEE,2012.2997-3000.

[8]Zhuang Fu-zhen,George karypis,Ning Xia,He Qing,Shi Zhong-zhi.Multi-view learning via probabilistic latent semantic analysis[J].Information Sciences,2012,199:20-30.

[9]Tzortzis G,Likas A.Kernel-based weighted multi-view clustering[A].Proceedings of the IEEE Intenational Conference on Data Mining[C].Piscataway,USA:IEEE,2012.675-684.

[10]Liu Jia-lu,Wang Chi,Gao Jing,Han Jia-wei.Multi-view clustering via joint nonnegative matrix factorization[A].Proceedings of the 2013 SIAM International Conference on Data Mining[C].Philadelphia,USA:SIAM,2013.252-260.

[11]Kumar A,Daumé H.A co-training approach for multi-view spectral clustering[A].Proceeding of the 28th Intenational Conference on Machine Learning[C].New York,USA:ACM,2011.393-400.

[12]Xia Tian,Tao Da-cheng,Mei Tao,Zhang Yong-dong.Multiview spectral embedding[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2010,40(6):1438-1446.

[13]Kumar A,Rai Piyush,Daumé III H.Co-regularized multi-view spectral clustering[A].Proceeding of the Proceeding of the 23th Advances in Neural Information Processing Systems[C].Cambridge,USA:MIT Press 2011.1413-1421.

[14]Bruno E,Marchand-Maillet S.Multiview clustering:a late fusion approach using latent models[A].Proceedings of the 32nd international ACM SIGIR Conference on Research and Development in Information Retrieval[C].New York,USA:ACM,2009.736-737.

[15]Chen Xiao-jun,Xu Xiao-fei,Huang J Z,Ye Yun-Ming.TW-k-means:automated two-level variable weighting clustering algorithm for multiview data[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(4):932-944.

[16]李樂,張毓晉.非負(fù)矩陣分解算法綜述[J].電子學(xué)報(bào),2008,36(4):737-743.

Li Le,Zhang Yu-jin.A survey on algorithms of non-negative matrix factorization[J].Acta Electronic Sinica,2008,36(4):737-743.(in Chinese)

[17]鄧曉政,焦李成,盧山.基于非負(fù)矩陣分解的譜聚類集成SAR圖像分割[J].電子學(xué)報(bào),2011,39(2):2905-2909.

Deng Xiao-zheng,Jiao Li-cheng,Lu-shan.Spectral clustering ensemble applied to SAR image segmentation Using Nonnegative Matrix Factorization[J].Acta Electronic Sinica,2011,39(2):2905-2909.(in Chinese)

[18]Shotton J,Winn J,Rother C,Criminisi A.TextonBoost for image understanding:Multi-class object recognition and segmentation by jointly modeling texture,layout,and context[J].International Journal of Computer Vision,2009,81(1):2-23.

[19]Strehl A,Ghosh J.Cluster ensembles—a knowledge reuse framework for combining multiple partitions[J].Journal of Machine Learning Research,2002,3(3):583-617.

劉正男,1983年6月出生黑龍江哈爾濱.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士研究生.主要研究方向?yàn)閿?shù)據(jù)挖掘、社會網(wǎng)絡(luò).

E-mail:xskeyan@126.com.

張國印男,1962年9月生于黑龍江齊齊哈爾.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授、博士生導(dǎo)師.主要研究方向?yàn)樯鐣W(wǎng)絡(luò)、網(wǎng)絡(luò)與信息安全、嵌入式系統(tǒng)等.

陳志遠(yuǎn)男,1978年8月生于吉林扶余.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院講師.主要研究方向?yàn)槟Ｐ蜋z測、機(jī)器學(xué)習(xí).本文通信作者.

E-mail:harbour521@163.com.

A Multiview Clustering Algorithm Based on Feature Weighting and Non-negative Matrix Factorization

LIU Zheng,ZHANG Guo-yin,CHEN Zhi-yuan

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin,Heilongjiang150001,China)

Abstract:In order to simultaneously solve the two problems of feature weighting and high dimension in the process of multiview clustering,a multiview clustering algorithm based on feature weighting and non-negative matrix factorization (FWNMF-MC) is proposed.According to the importance of each feature,FWNMF-MC automatically assigns different weights to different features.Multiview data is mapped from high dimensional space to low dimensional space by factorizing feature matrices into basis matrices and coefficient matrices.In order to take advantage of multiview information to mine cluster structure,the consensus of each view is maximized in low dimensional space.The experiment results show the performence of FWNMF-MC algorithm is superior to four existing classical multiview clustering algorithms.

Key words:multiview data;clustering;non-negative matrix factorization;feature weighting

作者簡介

DOI:電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.006

中圖分類號:TP391

文獻(xiàn)標(biāo)識碼：A

文章編號：0372-2112 (2016)03-0535-06

基金項(xiàng)目:國家自然科學(xué)基金(No.60873038；No.71272216);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助(No.HEUCF100603,No.HEUCFZ1212)

收稿日期:2014-06-21;修回日期:2014-10-08;責(zé)任編輯：梅志強(qiáng)