面向多視角數(shù)據(jù)的極大熵聚類算法*

張丹丹，鄧趙紅，王士同

江南大學(xué)數(shù)字媒體學(xué)院，江蘇無錫214122

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0554-11

?

面向多視角數(shù)據(jù)的極大熵聚類算法*

張丹丹+，鄧趙紅，王士同

江南大學(xué)數(shù)字媒體學(xué)院，江蘇無錫214122

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0554-11

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 61170122 (國家自然科學(xué)基金); the New Century Excellent Talent Foundation from MOE of China under Grant No. NCET-12-0882 (教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃).

Received 2015-05,Accepted 2015-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-08-11, http://www.cnki.net/kcms/detail/11.5602.TP.20150811.1519.004.html

摘要：當(dāng)前，極大熵聚類（maximum entropy clustering，MEC）在面對多視角聚類任務(wù)時(shí)，是將多視角樣本合并成為一個(gè)整體樣本再進(jìn)行處理，然而這樣會破壞各視角的獨(dú)立性特征，進(jìn)而影響最終的劃分結(jié)果。針對該問題，首先提出多視角協(xié)同劃分極大熵聚類算法（multi-view collaborative partition MEC，CoMEC），該算法加book=555,ebook=109入一個(gè)協(xié)調(diào)各視角空間劃分的約束項(xiàng)，使得每一視角在單獨(dú)聚類過程中考慮到其他視角的影響；然后通過區(qū)分每個(gè)視角的重要性將CoMEC算法擴(kuò)展為視角加權(quán)版本，即視角加權(quán)協(xié)同劃分極大熵聚類算法（view weighted collaborative partition MEC，W-CoMEC）；最后利用幾何均值的集成策略得到全局性的劃分結(jié)果。在人工數(shù)據(jù)集以及UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均顯示所提算法較之已有的聚類技術(shù)在應(yīng)對多視角聚類任務(wù)時(shí)具有更好的聚類性能。

關(guān)鍵詞：熵；多視角聚類；劃分；權(quán)值；集成策略；UCI數(shù)據(jù)集

1　引言

眾所周知，聚類的目的是將對象或數(shù)據(jù)樣本劃分為組或類，而在相同組或類的對象或數(shù)據(jù)樣本相對具有相似性，不同組或類的對象或數(shù)據(jù)樣本則相對具有不相似性。聚類作為一種無監(jiān)督學(xué)習(xí)技術(shù)，是數(shù)據(jù)挖掘、模式識別等領(lǐng)域的重要研究內(nèi)容之一，在識別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用。然而，由于現(xiàn)代技術(shù)的發(fā)展，數(shù)據(jù)復(fù)雜性隨之不斷提高，使得聚類算法的研究面臨更大的挑戰(zhàn)。

當(dāng)前，人們對經(jīng)典的聚類分析方法的研究不斷深入，其中經(jīng)典的極大熵聚類（maximum entropy clustering，MEC）算法[1]已成為眾人研究的重點(diǎn)，相關(guān)文獻(xiàn)[2-5]給出了很多有關(guān)MEC算法的研究成果。由于數(shù)據(jù)復(fù)雜性提高，人們在觀察復(fù)雜數(shù)據(jù)集時(shí)，往往可以通過多個(gè)視角來詮釋，即得到多視角數(shù)據(jù)。多視角數(shù)據(jù)是指一些事物或?qū)ο髲牟煌瑢傩钥臻g有多個(gè)視角或特征組，它是從不同角度綜合多種類型屬性特征的結(jié)果。例如一個(gè)銀行客戶數(shù)據(jù)集，可以被分為表示客戶的人口信息的人口統(tǒng)計(jì)視角、顯示有關(guān)客戶賬戶信息的賬戶視角和描述客戶消費(fèi)行為的消費(fèi)視角。多視角聚類算法的研究也成為當(dāng)前研究的重點(diǎn)。研究表明，極大熵聚類算法主要是針對單一視角數(shù)據(jù)的聚類方法，該算法在面對多視角聚類任務(wù)時(shí)，只能單獨(dú)對每一個(gè)視角進(jìn)行獨(dú)立聚類分析以獲取各視角下的聚類結(jié)果，然后使用集成學(xué)習(xí)機(jī)制[6-7]將每一視角下的聚類結(jié)果進(jìn)行統(tǒng)一，最終得到全局意義下的聚類結(jié)果。但是，人為地把多視角數(shù)據(jù)分解為多個(gè)單一視角數(shù)據(jù)進(jìn)行處理，會因各個(gè)視角的聚類結(jié)果存在明顯差異而給最終獲取的全局聚類結(jié)果帶來不好的影響，使得最終的全局聚類結(jié)果出現(xiàn)惡化，最終造成算法性能較差或不穩(wěn)定。對此，本文提出對各視角共性和差異性綜合考慮的新方法，首先通過協(xié)同劃分學(xué)習(xí)參數(shù)協(xié)調(diào)各個(gè)視角的空間劃分，提出多視角協(xié)同劃分極大熵聚類算法（multiview collaborative partition MEC，CoMEC）；繼而，通過給每個(gè)視角添加權(quán)值，表示不同視角的重要性程度，以達(dá)到更好的聚類性能，提出增強(qiáng)版本算法，即視角加權(quán)協(xié)同劃分極大熵聚類算法（view weighted collaborative partition MEC，W-CoMEC）。

當(dāng)前，針對多視角數(shù)據(jù)的聚類問題，相關(guān)的可利用聚類技術(shù)包括如下幾個(gè)方面的進(jìn)展。

首先，基于多視角學(xué)習(xí)技術(shù)的聚類方法近年來受到廣泛的關(guān)注。如文獻(xiàn)[8]提出了可用于解決多視角聚類問題的協(xié)同聚類算法Co-EM（collaborative EM）。同樣文獻(xiàn)[9]基于協(xié)同思想提出了一種雙視角譜聚類算法。文獻(xiàn)[10]利用圖論的知識提出了多視角譜聚類算法。此外，文獻(xiàn)[11]首次在經(jīng)典的模糊C均值（fuzzy C-means，F(xiàn)CM）算法中采用協(xié)同聚類的思想，提出了CoFC（collaborative fuzzy clustering）算法。文獻(xiàn)[12]同樣基于FCM算法提出多視角模糊聚類算法Co-FKM（collaborative fuzzy K-means），相關(guān)文獻(xiàn)的實(shí)驗(yàn)表明Co-FKM算法較之一些相關(guān)多視角算法具有一定的優(yōu)勢。此外，文獻(xiàn)[13]以經(jīng)典的K-means算法為框架，提出了一種多視角K-means聚類方法，即多視角雙層變量自動加權(quán)聚類算法TWKM （TW-K-means），該文獻(xiàn)的實(shí)驗(yàn)展現(xiàn)出TWKM算法處理多視角聚類任務(wù)的良好性能。

此外，針對多視角數(shù)據(jù)的聚類問題，相關(guān)的聚類技術(shù)還有多任務(wù)聚類技術(shù)、組合聚類技術(shù)及基于樣本與特征空間的協(xié)同聚類技術(shù)。如文獻(xiàn)[14]的LSSMTC（learning the shared subspace for multi-task clustering）算法是一個(gè)典型的應(yīng)用多任務(wù)聚類技術(shù)的算法。該算法把各視角看作一個(gè)單一聚類任務(wù)，且考慮的是任務(wù)之間的相似性，不同任務(wù)對應(yīng)不同的聚類對象；另外，該算法要求每個(gè)視角的數(shù)據(jù)樣本特征數(shù)相等，即其不能處理各視角樣本特性數(shù)不等的多視角聚類任務(wù)。文獻(xiàn)[14]中的組合K-means （CombKM）算法則是采用組合聚類技術(shù)的思想，在處理多視角數(shù)據(jù)時(shí)，將不同視角下的樣本特征組合為一個(gè)整體進(jìn)行處理，這種做法破壞了各視角間的獨(dú)立性，進(jìn)而影響最終的聚類結(jié)果。文獻(xiàn)[15]基于樣本與特征空間的協(xié)同聚類技術(shù)提出了Co-clustering （collaborative clustering）算法。該算法在處理多視角聚類任務(wù)時(shí)，不僅采用組合聚類思想對樣本進(jìn)行聚類，同時(shí)還考慮了對特征的劃分。然而由于其采用了與組合聚類相同的思想，使得其對特征空間的劃分相對粗糙，最終的聚類結(jié)果不理想。

本文組織結(jié)構(gòu)如下：第2章簡要介紹了MEC算法；第3章提出了一種多視角協(xié)同劃分極大熵聚類算法；第4章提出了增強(qiáng)的版本，即視角加權(quán)協(xié)同劃分極大熵聚類算法；第5章分別在人工模擬數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集上驗(yàn)證了所提算法的性能，并與相關(guān)算法進(jìn)行了比較；第6章總結(jié)全文。

2　極大熵聚類算法

對于樣本集X={x1,x2,...,xn}，根據(jù)某種相似性測量，它被聚類成c(2≤c≤n)個(gè)子類，各類中心用矩陣Z=[z1,z2,…,zc]表示；劃分可用矩陣U=[uij]∈Rcn表示，其中每一項(xiàng)滿足如下的約束：

極大熵聚類算法的目標(biāo)函數(shù)定義為：

這里‖°‖表示歐幾里德距離；參數(shù)γ是非負(fù)常數(shù)。對于目標(biāo)函數(shù)（1），利用拉格朗日極值求解方法，得到類中心及劃分矩陣的優(yōu)化迭代公式，如定理1所示。

定理1 P(U, Z)取極小值的必要條件為：

式中，i=1,2,…,c, j=1,2,…,n

根據(jù)定理1，極大熵聚類算法可描述如下：

算法1極大熵聚類算法

輸入：樣本集X={x1,x2,…,xn}，聚類類別c(2≤c≤n)，迭代閾值ε，迭代次數(shù)r，參數(shù)γ。

輸出：全局性的模糊劃分矩陣U，聚類中心矩陣Z。

步驟1初始化劃分矩陣U(0)；

步驟2根據(jù)式（2）更新類中心Z(r)；

步驟3根據(jù)式（3）更新隸屬度U(r)為U(r+1)；

步驟4若‖U(r+1)-U(r)‖F(xiàn)≤ε，則算法迭代循環(huán)停止，否則返回步驟2。

上述算法中‖°‖F(xiàn)表示Frobenius范數(shù)。極大熵聚類算法是針對單一視角數(shù)據(jù)的經(jīng)典算法，在面向多視角數(shù)據(jù)時(shí)，采用與處理單一視角數(shù)據(jù)相同的思想處理多視角數(shù)據(jù)，這極大地影響了極大熵聚類算法的性能。針對此問題，本文首先提出了一個(gè)面向多視角數(shù)據(jù)的聚類算法，即多視角協(xié)同劃分極大熵聚類算法。

3　多視角協(xié)同劃分極大熵聚類算法

3.1改進(jìn)的目標(biāo)函數(shù)

根據(jù)上文對極大熵聚類算法面對多視角聚類任務(wù)的局限性分析，本文首先提出了一種多視角極大熵聚類算法，即多視角協(xié)同劃分極大熵聚類算法。

對于一個(gè)有k個(gè)視角的多視角樣本集X={view1, view2,…,viewk}，其第k個(gè)視角的樣本集可表示為viewk={x1,k,x2,k,…,xN,k}。對該多視角數(shù)據(jù)樣本進(jìn)行聚類時(shí)，根據(jù)某種相似性度量，把每一視角聚類為c(2≤c≤n)類，用矩陣Uk=[uij,k]表示第k個(gè)視角的劃分隸屬度，第k個(gè)視角的聚類中心可用矩陣Zk=[z1,k, z2,k,…,zc,k]表示。則多視角協(xié)同劃分極大熵聚類算法的目標(biāo)函數(shù)可表示如下：

對于目標(biāo)函數(shù)（4）滿足如下約束條件：

這里‖°‖表示歐幾里得距離。式（5）中參數(shù)λ為協(xié)同學(xué)習(xí)參數(shù)，用來調(diào)控中各視角間協(xié)同學(xué)習(xí)的程度。參數(shù)γ、λ為非負(fù)常數(shù)。

最后，根據(jù)獲取的各視角的劃分，利用如下的集成方法得到最終具備全局特性的空間劃分矩陣：

3.2目標(biāo)函數(shù)的優(yōu)化

對于目標(biāo)函數(shù)（4），如下定理成立：

定理2當(dāng)U固定時(shí)，P(U,Z)取得極小值的必要條件為：

定理3當(dāng)Z固定時(shí)，P(U,Z)取極小值的必要條件為：

分別對uij,t,χ求導(dǎo)，并使得導(dǎo)數(shù)為0，得到：

由式（9）和式（10）即可得到：

3.3算法描述

根據(jù)上節(jié)推導(dǎo)出的參數(shù)學(xué)習(xí)規(guī)則，給出算法的具體步驟如下：

算法2多視角協(xié)同劃分極大熵聚類算法

輸入：多視角樣本集X={view1,view2,…,viewk}共k個(gè)視角，其中viewk={x1,k,x2,k,…,xn,k}，聚類類別c(2≤c≤n)，迭代閾值ε，迭代次數(shù)l，參數(shù)λ、γ。

輸出：全局性的模糊劃分矩陣Uˉ，各視角聚類中心點(diǎn)Zi,k。

步驟1隨機(jī)產(chǎn)生各視角的模糊隸屬度uij,t(1≤t≤k)；

步驟2根據(jù)式（7）更新各視角下的中心點(diǎn)Zi,k；

步驟3根據(jù)式（8）更新各視角下的隸屬度uij,t；

步驟5算法收斂后，得到各視角下的隸屬度；

步驟6根據(jù)步驟5所獲取的各視角下的隸屬度uij,t，利用式（6）獲取具備全局特性的空間劃分矩陣Uˉ。

4　視角加權(quán)協(xié)同劃分極大熵聚類算法

本文在多視角協(xié)同劃分極大熵聚類算法的基礎(chǔ)上，提出了一個(gè)增強(qiáng)版本的聚類算法。該算法在處理多視角聚類任務(wù)時(shí)，不僅考慮了各視角的協(xié)同劃分，而且通過給每個(gè)視角添加一個(gè)表示其重要性程度的權(quán)值，使得不同視角達(dá)到更好的協(xié)調(diào)聚類性能。

4.1視角加權(quán)協(xié)同劃分極大熵聚類算法

根據(jù)以上對視角加權(quán)協(xié)同劃分極大熵聚類算法的介紹，其目標(biāo)函數(shù)可表示如下：

上式滿足如下約束：

其中，W=[wk]是分配給各個(gè)視角的權(quán)重矩陣，它的每個(gè)元素表示對應(yīng)視角的重要性程度；是協(xié)同劃分項(xiàng)，其表示如式（5）所示；參數(shù)γ、η、λ為非負(fù)常數(shù)。

香農(nóng)熵正則化項(xiàng)在自適應(yīng)調(diào)整權(quán)值方面的有效性在相關(guān)文獻(xiàn)已得到充分的體現(xiàn)，例如在本文研究的極大熵聚類的概率劃分方面的成功應(yīng)用。為了確保視角W的協(xié)同劃分，式（11）引入了香農(nóng)熵正則化項(xiàng)，這使得在多視角聚類過程中各視角的權(quán)值得到更好的協(xié)調(diào)，進(jìn)而得到更佳的視角劃分結(jié)果。

最后，類似于多視角協(xié)同劃分極大熵聚類算法，其增強(qiáng)方法根據(jù)獲取的各視角的劃分，同樣利用幾何均值的集成方法得到最終具備全局特性的空間劃分矩陣，具體見式（6）。

4.2目標(biāo)函數(shù)的優(yōu)化

對于目標(biāo)函數(shù)（11），如下定理成立：

定理4當(dāng)U、W固定時(shí)，P(U,Z,W)取得極小值的必要條件為：

定理5當(dāng)Z、W固定時(shí)，P(U,Z,W)取極小值的必要條件為：

上式分別對uij,t,χ1求導(dǎo)，并使得導(dǎo)數(shù)為0，得到：

由式（14）和式（15）即可得到：

定理6當(dāng)U、Z固定時(shí)，P(U,Z,W)取極小值的必要條件為：

上式分別對wt、χ2求導(dǎo)，并使得導(dǎo)數(shù)為0，得到：

由式（17）和式（18）即可得到：

4.3算法描述

根據(jù)上節(jié)推導(dǎo)出的參數(shù)學(xué)習(xí)規(guī)則，下面給出增強(qiáng)版本W(wǎng)-CoMEC算法的具體步驟如下。

算法3視角加權(quán)協(xié)同劃分極大熵聚類算法

輸入：多視角樣本集X={view1,view2,…,viewk}共k個(gè)視角，其中viewk={x1,k,x2,k,…,xn,k}，聚類類別c(2≤c≤n)，迭代閾值ε，迭代次數(shù)l，參數(shù)γ、η、λ。

輸出：全局性的模糊劃分矩陣Uˉ，各視角聚類中心點(diǎn)Zi,k，視角權(quán)重矩陣W={wk}。

步驟1隨機(jī)產(chǎn)生各視角的模糊隸屬度uij,t(1≤t≤k)，隨機(jī)產(chǎn)生視角權(quán)重矩陣W={wk}；

步驟2根據(jù)式（12）更新各視角下的中心點(diǎn)Zi,k；

步驟3根據(jù)式（13）更新各視角下的隸屬度uij,t；

步驟4根據(jù)式（16）更新視角權(quán)重矩陣W={wk}；

步驟5如果‖Pl+1-Pl‖<ε，則算法迭代循環(huán)停止，否則跳回步驟2；

步驟6算法收斂后，得到各視角下的隸屬度；

步驟7根據(jù)步驟6所獲取的各視角下的隸屬度uij,t，利用式（6）獲取具備全局特性的空間劃分矩陣Uˉ。

4.4時(shí)間算法復(fù)雜度和收斂性分析

本節(jié)對算法的時(shí)間復(fù)雜度描述如下：對多視角協(xié)同劃分極大熵聚類算法，即CoMEC算法，其時(shí)間復(fù)雜度為O(tknc+tkc)；對其增強(qiáng)版本的視角加權(quán)協(xié)同劃分極大熵聚類算法，即W-CoMEC算法，由于該算法考慮到各視角的影響，故其時(shí)間復(fù)雜度為O(tk+ tknc+tkc)。其中t是算法迭代的總次數(shù)，k是數(shù)據(jù)集的視角個(gè)數(shù)，n是數(shù)據(jù)集的大小，c是類別數(shù)。由以上兩種算法的時(shí)間復(fù)雜度可知，考慮視角加權(quán)的WCoMEC算法和未考慮視角加權(quán)的CoMEC算法的時(shí)間復(fù)雜度數(shù)量級相差不大，具有相同的階次。

文獻(xiàn)[3]對MEC算法的收斂性已經(jīng)給出了收斂性分析，而根據(jù)相關(guān)收斂性理論[16-17]可知，W-CoMEC算法也是滿足Zangwill收斂性定理的條件的。

5　實(shí)驗(yàn)研究

為了驗(yàn)證本文算法處理多視角聚類任務(wù)的有效性，將分別對人工模擬數(shù)據(jù)集以及UCI標(biāo)準(zhǔn)多視角數(shù)據(jù)[18]進(jìn)行實(shí)驗(yàn)分析與評估。有關(guān)模擬數(shù)據(jù)集與真實(shí)數(shù)據(jù)集的詳細(xì)內(nèi)容將分別于下文給出，相關(guān)UCI標(biāo)準(zhǔn)多視角數(shù)據(jù)集的基本信息可見表1。為了對本文算法的聚類性能做出合理的判斷，也將給出與相關(guān)聚類算法的性能比較。實(shí)驗(yàn)中采用的相關(guān)聚類算法有MEC算法[1]、多視角模糊聚類算法Co-FKM[12]、多視角雙層變量自動加權(quán)聚類算法TWKM[13]、基于多任務(wù)學(xué)習(xí)框架的LSSMTC算法[14]、基于多任務(wù)的組合K-means算法（CombKM）[14]及基于樣本與特征空間協(xié)同聚類的Co-clustering算法[15]。

另外，本文采用如下兩種常用的評價(jià)指標(biāo)評估各聚類算法的聚類性能，即pairwise Precision[19]和NMI（normalized mutual information）[20-21]：

Table 1 Real multi-view UCI datasets表1　UCI真實(shí)多視角數(shù)據(jù)集

其中，f11表示數(shù)據(jù)點(diǎn)具有相同的類標(biāo)簽并且屬于同一類的配對點(diǎn)數(shù)目，而f00則表示數(shù)據(jù)點(diǎn)具有不同的類標(biāo)簽并且屬于不同類的配對點(diǎn)數(shù)目；Nij表示第i個(gè)聚類與類j的契合程度，Ni表示第i個(gè)聚類所包含的數(shù)據(jù)樣本量，Nj表示類j所包含的數(shù)據(jù)樣本量，而N表示整個(gè)數(shù)據(jù)樣本的總量大小。

以上兩種性能指標(biāo)，其取值范圍均為[0, 1]，取值越接近1，表示算法的聚類性能越好。

本文所顯示的評價(jià)指標(biāo)的均值和方差均為最優(yōu)參數(shù)下運(yùn)行10次得到的。

5.1人工模擬數(shù)據(jù)集實(shí)驗(yàn)

為了有效驗(yàn)證本文算法的聚類性能，在人工模擬數(shù)據(jù)集實(shí)驗(yàn)部分，針對UCI數(shù)據(jù)庫中真實(shí)數(shù)據(jù)集Iris，抽取其中三維特征，將每一維特征看作一個(gè)視角，進(jìn)而構(gòu)造出具有3個(gè)視角樣本的多視角模擬數(shù)據(jù)集irisMoni。其中每個(gè)視角都由3類樣本組成，該數(shù)據(jù)集每個(gè)視角的具體信息如圖1所示。

Table 2 Definitions and settings of related notations表2　參數(shù)定義與設(shè)置

Fig.1 IrisMoni corresponding datasets under each view圖1　數(shù)據(jù)集IrisMoni各個(gè)視角樣本直觀圖

觀察圖1可以發(fā)現(xiàn)，在IrisMoni數(shù)據(jù)集的3個(gè)視角樣本數(shù)據(jù)中，視角1和視角2的3類樣本間都會出現(xiàn)一定的重疊現(xiàn)象，而視角3卻能夠清晰地顯示出3個(gè)類別的樣本，即視角3具備清晰的聚類特性。若使用現(xiàn)有的傳統(tǒng)單一視角聚類算法對此類聚類任務(wù)進(jìn)行分析，得到的聚類結(jié)果將會受到視角1及視角2的影響，進(jìn)而使得整體的聚類性能受到影響。對此，本文算法及相關(guān)算法均在該人工模擬數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，得到的實(shí)驗(yàn)數(shù)據(jù)結(jié)果如表3及圖2所示。

Fig.2 Weight of each view for IrisMoni datasets with W-CoMEC algorithm圖2　W-CoMEC算法獲取的IrisMoni數(shù)據(jù)集各視角權(quán)重

對表3的結(jié)果進(jìn)行分析可以發(fā)現(xiàn)，與當(dāng)前多任務(wù)的LSSMTC算法、組合任務(wù)的CombKM算法及基于樣本空間與特征空間協(xié)同分析的Co-clustering算法相比，多視角極大熵聚類算法CoMEC和W-CoMEC的聚類結(jié)果均明顯優(yōu)于它們的聚類性能；而與單一視角的極大熵聚類算法MEC相比，CoMEC和WCoMEC亦展現(xiàn)出穩(wěn)定的聚類性能。且由表3的評價(jià)指標(biāo)也可以直觀地看到，W-CoMEC算法較CoMEC算法較之于多視角模糊聚類算法Co-FKM具有更好的聚類性能。此外，與多視角雙層變量自動加權(quán)聚類算法TWKM相比，CoMEC算法略顯不足，而其增強(qiáng)版本W(wǎng)-CoMEC算法的性能與之相當(dāng)，這也體現(xiàn)了面向多視角數(shù)據(jù)的極大熵聚類方法具有處理多視角聚類任務(wù)的性能。

從圖2中展示出的增強(qiáng)版本W(wǎng)-CoMEC算法在IrisMoni數(shù)據(jù)集各視角權(quán)重分布情況也可以知道，該算法使得最佳視角權(quán)重達(dá)到最大，有效利用了最佳視角，進(jìn)而獲取了更為合理的空間劃分結(jié)果。

綜上，各實(shí)驗(yàn)指標(biāo)的數(shù)據(jù)顯示，W-CoMEC算法利用視角加權(quán)的協(xié)同劃分的思想，使其可以有效處理多視角聚類任務(wù)，并表現(xiàn)出一定的聚類優(yōu)勢。

5.2多視角真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

本節(jié)選擇經(jīng)典機(jī)器學(xué)習(xí)數(shù)據(jù)庫UCI中的兩個(gè)具備多視角特性的數(shù)據(jù)集，即IS數(shù)據(jù)集和WTP數(shù)據(jù)集，針對這兩種真實(shí)多視角數(shù)據(jù)集來進(jìn)一步進(jìn)行性能評估。這兩種數(shù)據(jù)集的相關(guān)信息已在表1中給出，對這兩種多視角數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果如表4和表5。

由于LSSMTC算法本身的局限性，它需要在各視角樣本的維數(shù)相等的多視角數(shù)據(jù)中才能使用該算法，從而LSSMTC算法無法處理IS和WTP各視角維數(shù)均不相等的數(shù)據(jù)樣本。

Table 3 Experimental results of several algorithms on IrisMoni datasets表3　各算法在IrisMoni數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

此外，觀察表4和表5中的實(shí)驗(yàn)結(jié)果可知，與LSSMTC、CombKM和Co-clustering算法相比，本文多視角極大熵聚類算法性能上有了進(jìn)一步的改進(jìn)。在比較的幾種算法中，MEC和CombKM算法僅實(shí)現(xiàn)了各視角數(shù)據(jù)的簡單融合，因而性能較差。雖然Coclustering聚類針對多視角數(shù)據(jù)已具有一定的各視角之間的協(xié)作學(xué)習(xí)能力，但協(xié)作學(xué)習(xí)的程度不夠充分。而本文CoMEC算法僅實(shí)現(xiàn)了各視角的協(xié)同劃分，因此與視角加權(quán)的W-CoMEC算法相比，聚類性能較差。而與多視角模糊聚類算法Co-FKM相比，在IS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。顯示出該算法優(yōu)于本文多視角極大熵聚類算法，在WTP數(shù)據(jù)集上卻不及本文算法的性能；與K-means框架的多視角雙層變量自動加權(quán)聚類算法TWKM相比，在IS數(shù)據(jù)集和WTP數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果均展現(xiàn)出本文算法的聚類性能優(yōu)勢。

綜上，較之于幾種相關(guān)的算法，本文算法針對多視角數(shù)據(jù)采用視角加權(quán)的協(xié)同劃分策略，最終得到具有全局最優(yōu)劃分的聚類性能，使得經(jīng)典的極大熵聚類算法具有處理多視角數(shù)據(jù)的性能。

Table 4 Experimental results of several algorithms on IS datasets表4　各算法在IS數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

Table 5 Experimental results of several algorithms on WTP datasets表5　各算法在WTP數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果記錄

5.3運(yùn)行時(shí)間比較

本節(jié)針對IS和WTP兩個(gè)真實(shí)數(shù)據(jù)集，將本文提出的新算法及其他對比算法在對應(yīng)數(shù)據(jù)集上的運(yùn)行時(shí)間進(jìn)行比較，具體如表6所示。由于LSSMTC算法要求各數(shù)據(jù)樣本維數(shù)相等無法使用，故未能記錄該算法的運(yùn)行時(shí)間。表6中記錄均是算法在各個(gè)數(shù)據(jù)集上在給定參數(shù)時(shí)運(yùn)行一次所用的時(shí)間，單位為秒。

由表6中的結(jié)果可以看出，在IS和WTP真實(shí)數(shù)據(jù)集上，本文提出的兩種新算法運(yùn)行一次所用的時(shí)間都與MEC算法和CombKM算法差不多，與Coclustering算法相比，運(yùn)行時(shí)間方面展現(xiàn)了較大的優(yōu)勢。同時(shí)，與Co-FKM和TWKM兩種多視角聚類算法相比，運(yùn)行時(shí)間方面同樣也展現(xiàn)出了一定的優(yōu)勢。

6　結(jié)束語

Table 6 Running time of several algorithms on IS and WTP datasets表6　各種算法在IS和WTP數(shù)據(jù)集上運(yùn)行時(shí)間　s

本文在經(jīng)典MEC算法框架上，通過引入?yún)f(xié)同劃分技術(shù)和視角加權(quán)技術(shù)，提出了多視角協(xié)同劃分極大熵聚類算法及其增強(qiáng)版本的視角加權(quán)協(xié)同劃分極大熵聚類算法。在協(xié)同劃分學(xué)習(xí)參數(shù)的作用下，使得各個(gè)視角之間協(xié)調(diào)作用更加靈活，同時(shí)視角權(quán)重凸顯出了最佳視角，進(jìn)而使得極大熵聚類算法具有處理多視角聚類任務(wù)的性能，并體現(xiàn)出一定的聚類優(yōu)勢。而本文實(shí)驗(yàn)部分中無論是模擬數(shù)據(jù)集還是UCI真實(shí)數(shù)據(jù)集得到的對比數(shù)據(jù)，均顯示出本文方法具有處理多視角數(shù)據(jù)的聚類性能，并且在模擬數(shù)據(jù)集和WTP真實(shí)數(shù)據(jù)集上體現(xiàn)出更好的聚類性能。但由于本文采用的MEC框架中歐式距離的使用，使得在面對高維多視角聚類問題時(shí)仍面臨一定的考驗(yàn)，當(dāng)前距離學(xué)習(xí)方法的研究也成為后人研究的熱點(diǎn)，針對歐式距離的局限性，距離學(xué)習(xí)在多視角聚類中的應(yīng)用將會成為今后研究的重點(diǎn)。特別地，近年來廣受關(guān)注的軟子空間聚類對于高維數(shù)據(jù)聚類展現(xiàn)出了有希望的性能，因而本文的多視覺學(xué)習(xí)策略和軟子空間聚類技術(shù)融合來開發(fā)新的算法亦將是非常有意義的工作。

References:

[1] Li R P, Mukaidono M.Amaximum-entropy approach to fuzzy clustering[C]//Proceedings of the 4th IEEE International Conference on Fuzzy Systems and the 2nd International Fuzzy Engineering Symposium, Yokohama, Japan, Mar 20-24, 1995. Piscataway, USA: IEEE, 1995: 2227-2232.

[2] Karayiannis N B. MECA: maximum entropy clustering algorithm[C]//Proceedings of the 3rd IEEE Conference on Computational Intelligence, Orlando, USA, Jun 26-29, 1994. Piscataway, USA: IEEE, 1994: 630-635.

[3] Zhang Zhihua, Zheng Nanning, Shi Gang. Maximum entropy clustering algorithm and its global convergence analysis[J]. Science: E Series, 2001, 31(1): 59-70.

[4] Deng Zhaohong, Wang Shitong, Wu Xisheng, et al. Robust maximum entropy clustering algorithm RMEC and its outlier labeling[J]. Engineering Science, 2004, 6(9): 38-45.

[5] Qian Pengjiang, Sun Shouwei, Jiang Yizhang, et al. Knowledge transfer based maximum entropy clustering[J]. Control and Decision, 2015, 30(6): 1000-1006.

[6] Asur S, Ucar D, Parthasarathy S. An ensemble framework for clustering protein-protein interaction networks[J]. Bioinformatics, 2007, 23(13): i29-i40.

[7] Wang Hongjun, Shan Hanhuai, Banerjee A. Bayesian cluster ensembles[J]. Statistical Analysis and Data Mining: The ASAData Science Journal, 2011, 4(1): 54-70.

[8] Yamanishi Y, Vert J P, Kanehisa M. Protein network inference from multiple genomic data: a supervised approach[J]. Bioinformatics, 2004, 20(S1): i363-i370.

[9] Virginia R de Sa. Spectral clustering with two views[C]// Proceedings of the 22nd International Conference on Machine Learning Workshop on Learning, Multiple Views, Bonn, Germany, Aug 7-11, 2005. New York, USA: ACM, 2005: 20-27.

[10] Zhou Dengyong, Burges C J C. Spectral clustering and transductive learning with multiple views[C]//Proceedings of the 24th International Conference on Machine Learning, Corvallis, USA, Jun 20-24, 2007. New York, USA: ACM, 2007: 1159-1166.

[11] Pedrycz W. Collaborative fuzzy clustering[J]. Pattern Recognition Letter, 2002, 23(14): 1675-1686.

[12] Cleuziou G, Exbrayat M, Martin L, et al. CoFKM: a centralized method for multiple-view clustering[C]//Proceedings of the 9th IEEE International Conference on Data Mining, Miami, USA, Dec 6-9, 2009. Piscataway, USA: IEEE, 2009: 752-757.

[13] Chen Xiaojun, Xu Xiaofei, Huang J Z, et al. 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.

[14] Gu Quanquan, Zhou Jie. Learning the shared subspace for multi-task clustering and transductive transfer classification [C]//Proceedings of the 19th IEEE International Conference on Data Mining, Miami, USA, Dec 6-9, 2009. Piscataway, USA: IEEE, 2009: 159-168.

[15] Gu Quanquan, Zhou Jie. Co-clustering on manifolds[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, Jun 28-Jul 1, 2009. New York, USA: ACM, 2009: 359-368.

[16] Zangwill W I. Convergence conditions for nonlinear programming algorithms[J]. Management Science, 1969, 16(1): 1-13.

[17] Luenberger D G, Ye Yinyu. Linear and nonlinear programming[M]. [S.l.]: Springer Science & Business Media, 2008.

[18] Bache K, Lichman M. UCI machine learning repository[EB/OL]. (2013)[2015-03-12]. http://archive.ics.uci.edu/ml.

[19] Liu Yi, Jin Rong, Jain A K. Boostcluster: boosting clustering by pairwise constraints[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, USA, Aug 12-15, 2007. New York, USA:ACM, 2007: 450-459.

[20] Jing Liping, Ng M K, Huang J Z. An entropy weighting kmeans algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(8): 1026-1041.

[21] Deng Zhaohong, Choi K S, Chung F L, et al. Enhanced softsubspace clustering integrating within-cluster and betweencluster information[J]. Pattern Recognition, 2010, 43(3): 767-781.

附中文參考文獻(xiàn)：

[3]張志華,鄭南寧,史罡.極大熵聚類算法及其全局收斂性分析[J].中國科學(xué): E輯, 2001, 31(1): 59-70.

[4]鄧趙紅,王士同,吳錫生,等.魯棒的極大熵聚類算法RMEC及其例外點(diǎn)標(biāo)識[J].中國工程科學(xué), 2004, 6(9): 38-45.

[5]錢鵬江,孫壽偉,蔣亦樟,等.知識遷移極大熵聚類算法[J].控制與決策, 2015, 30(6): 1000-1006.

ZHANG Dandan was born in 1992. She is an M.S. candidate at School of Digital Media, Jiangnan University. Her research interests include artificial intelligence and intelligent computation.

張丹丹（1992—），女，江南大學(xué)數(shù)字媒體學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槿斯ぶ悄埽悄苡?jì)算。

DENG Zhaohong was born in 1982. He is an associate professor at School of Digital Media, Jiangnan University. His research interests include fuzzy modeling and intelligent computation.

鄧趙紅（1982—），男，博士，江南大學(xué)數(shù)字媒體學(xué)院副教授，主要研究領(lǐng)域?yàn)槟：?，智能?jì)算。

WANG Shitong was born in 1964. He is a professor at School of Digital Media, Jiangnan University. His research interests include artificial intelligence, pattern recognition and bioinformatics.

王士同（1964—），男，江南大學(xué)數(shù)字媒體學(xué)院教授，主要研究領(lǐng)域?yàn)槿斯ぶ悄埽Ｊ阶R別，生物信息。

Maximum Entropy Clustering Algorithm for Multi-View Data?

ZHANG Dandan+, DENG Zhaohong, WANG Shitong
School of Digital Media, Jiangnan University, Wuxi, Jiangsu 214122, China

+ Corresponding author: E-mail: zdd1226394625@163.com

ZHANG Dandan, DENG Zhaohong, WANG Shitong. Maximum entropy clustering algorithm for multi-view data. Journal of Frontiers of Computer Science and Technology, 2016, 10(4): 554-564.

Abstract:Currently, the maximum entropy clustering (MEC) merges the multi-view samples to process the multi-view clustering task. However, this will damage the independence of each view, and affect the final partition results. Aiming at this problem, this paper proposes a multi- view collaborative partition maximum entropy clustering (CoMEC) algorithm, which joins a constraint to coordinate each perspective space partition, to make each view in a separate clustering process consider the influence of other views. Then this paper proposes the enhanced weighted view version called W-CoMEC by identifying the importance of each view. Finally this paper applies the geometric average integration strategy to obtain the global partition results. The experimental results on a synthetic multi-view dataset and several UCI real-world multi-view datasets show that the proposed algorithm outperforms or is at least comparable to the existing clustering technology in dealing with multi-view clustering task.

Key words:entropy; multi-view clustering; partition; weight; integration strategy; UCI dataset

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

中圖分類號：TP18

doi:10.3778/j.issn.1673-9418.1505041