基于張量距離的高階近鄰傳播聚類算法

鉉 巖, 周傳生

(1. 沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034; 2. 沈陽師范大學(xué) 教育技術(shù)學(xué)院, 沈陽 110034)

?

基于張量距離的高階近鄰傳播聚類算法

鉉 巖1, 周傳生2

(1. 沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034; 2. 沈陽師范大學(xué) 教育技術(shù)學(xué)院, 沈陽 110034)

近鄰傳播算法(AP)不需要事先指定聚類數(shù)目,在程序運行過程中,能夠自動識別聚類中心及聚類數(shù)目。在同一批數(shù)據(jù)集上,AP算法聚類結(jié)果穩(wěn)定,魯棒性好。除此之外,AP聚類算法可以采用多種距離度量方式,聚類結(jié)果精確。針對近鄰傳播算法(AP)不能對異構(gòu)數(shù)據(jù)進行聚類的問題,提出一種基于張量距離的高階AP聚類算法。該算法首先利用張量表示異構(gòu)數(shù)據(jù)對象,然后將張量距離引入AP聚類算法,用來度量異構(gòu)數(shù)據(jù)對象在張量空間的相似度。張量距離的引入,不但能夠度量異構(gòu)數(shù)據(jù)對象在數(shù)值上的差異,同時能夠度量異構(gòu)數(shù)據(jù)對象在高階空間中位置的差異性,有效的捕捉異構(gòu)數(shù)據(jù)對象的分布特征。實驗結(jié)果表示,提出的高階AP算法能夠有效的對異構(gòu)數(shù)據(jù)對象進行聚類。

聚類; 異構(gòu)數(shù)據(jù); 張量距離; AP算法

0 引 言

近年來,隨著物聯(lián)網(wǎng)、電子商務(wù)和云計算的發(fā)展,產(chǎn)生了越來越多的異構(gòu)數(shù)據(jù)集[1]。作為數(shù)據(jù)挖掘的典型技術(shù),聚類采用無監(jiān)督學(xué)習(xí)的方式,將數(shù)據(jù)集劃分成多個簇[2]。使得簇內(nèi)數(shù)據(jù)對象之間的相似性盡可能大,簇間數(shù)據(jù)對象的相似性盡可能小[3]。經(jīng)過數(shù)十年的發(fā)展,多種典型的聚類算法被相繼提出。然而這些經(jīng)典的聚類算法都只能對結(jié)構(gòu)化數(shù)據(jù)進行聚類,難以直接對異構(gòu)數(shù)據(jù)聚類。

近鄰傳播算法(Affinity Propagation Clustering, AP)是由Brendan J. Frey和Delbert Dueck于2007年在《Science》雜志上提出的一種新的聚類算法[4]。AP算法不需要事先指定聚類數(shù)目。在同一批數(shù)據(jù)集上,AP算法聚類結(jié)果穩(wěn)定,魯棒性好[5]。除此之外,AP聚類算法可以采用多種距離度量方式,聚類結(jié)果精確[6]。然而AP算法不支持對異構(gòu)數(shù)據(jù)的聚類。為了解決這個問題,本文提出一種基于張量距離的高階近鄰傳播算法。

1 相關(guān)工作

1.1 近鄰傳播聚類算法

AP聚類算法以相似度矩陣S對角線上的數(shù)值s(k,k)作為k點能否成為聚類中心的評判標準,即該值越大,成為聚類中心的可能性就越大,這個值又稱作參考度p(preference)[7]。

為了計算參考度,AP聚類算法引入2個信息傳播矩陣,即吸引度矩陣R和歸屬度矩陣A。吸引度值r(i,k)表示從點i發(fā)送到候選聚類中心k的數(shù)值消息,反映k點是否適合作為i點的聚類中心。計算公式如下:

(1)

歸屬度值a(i,k)是從候選聚類中心k發(fā)送到i的數(shù)值消息,反映i點是否選擇k作為其聚類中心。計算公式如下:

(2)

(3)

r(i, k)與a (i, k)越強,則k點作為聚類中心的可能性就越大,并且i點隸屬于以k點為聚類中心的聚類的可能性也越大。

1.2 異構(gòu)數(shù)據(jù)聚類相關(guān)工作

近年來,隨著異構(gòu)數(shù)據(jù)在諸多領(lǐng)域的迅速增加,多種針對異構(gòu)數(shù)據(jù)的聚類算法被相繼提出[8]。具有代表性的雙模態(tài)聚類算法是由Long等人提出的塊值分解算法和HF-ART算法[9]。

受到雙模態(tài)異構(gòu)數(shù)據(jù)聚類算法的啟發(fā),研究人員提出了多種針對多模態(tài)異構(gòu)數(shù)據(jù)聚類的算法。最為典型的由Long等人提出的頻譜關(guān)聯(lián)聚類算法和由Hen等人提出的對稱非負矩陣分解算法[10]。由Bekkerman等人提出的聯(lián)合馬爾科夫隨機場算法,同時能夠用于半監(jiān)督學(xué)習(xí)等應(yīng)用[11]。

2 基于張量距離的高階近鄰傳播算法

2.1 基于張量模型的異構(gòu)數(shù)據(jù)表示

為了能夠?qū)Ω鞣N異構(gòu)數(shù)據(jù)對象進行統(tǒng)一表示,本文利用張量模型表示異構(gòu)數(shù)據(jù)對象。張量在數(shù)學(xué)上可以看作是向量的擴展,例如在同構(gòu)的意義下,一階張量為一個向量Rd,N階張量表示為RI1×I2…×IN,其中N表示張量的階數(shù),In表示張量第n階上的維數(shù)[12]。

對于異構(gòu)數(shù)據(jù)對象而言,通用的張量表示模型定義為:T∈RIt×IS×Iu×…×Ip。在張量模型中,數(shù)據(jù)的特征表示為張量的階。

2.2 基于張量距離的高階近鄰傳播算法

在彎頭1入口處泥漿流體產(chǎn)生切向分速度，二次流開始發(fā)展；在彎頭1出口處可以觀察到完全發(fā)展的二次流；在彎頭2出口處分速度值最大，二次流強度最強；泥漿在離開彎頭部分以后，不再受到離心力的作用，混合相垂直分速度逐漸減小，但由圖5e)、圖5f)可看出X=5D處二次流仍有一定存留，在X=20D處二次流已基本消失。爬坡管內(nèi)泥漿所受到的離心力沿流動方向不斷變化，當(dāng)流經(jīng)彎頭2時與彎頭1中離心力方向相反，彎頭2入口面二次流強度較彎頭1出口明顯降低，在流過彎頭2后渦流方向改變。

在將異構(gòu)數(shù)據(jù)對象表示為張量之后,為了度量數(shù)據(jù)對象在高階張量空間的獨立,本文將張量距離引入近鄰傳播算法。

對于給定的2個張量X∈RI1×I2×…×In和Y∈RI1×I2×…×In,x和y分別表示張量X和Y向量展開后的表示,則張量X和Y之間的張量距離定義為[13]:

(4)

其中,glm是系數(shù),G是系數(shù)矩陣。

引入張量距離的高階近鄰傳播聚類算法的主要步驟如下:

步驟1 根據(jù)式(4)計算異構(gòu)數(shù)據(jù)對象之間的距離,初始化相似度矩陣S;

步驟2 根據(jù)式(1)計算樣本點間的吸引度值;

步驟3 根據(jù)式(2)和式(3)計算樣本點間的歸屬度值;

步驟4 根據(jù)式(5)～式(7)更新吸引度矩陣和歸屬度矩陣;

(5)

(6)

(7)

步驟5 如果迭代次數(shù)超過設(shè)定的最大值或者聚類中心不再變化,終止計算,根據(jù)P值確定聚類中心并且確定各個樣本點所屬的類別;否則返回步驟2,繼續(xù)執(zhí)行。

3 實驗與分析

本節(jié)通過將本文提出的高階近鄰傳播聚類算法和HOPCM算法、傳統(tǒng)近鄰傳播算法進行對比來驗證高階近鄰傳播聚類算法的有效性[14]。實驗采用2個典型的異構(gòu)數(shù)據(jù)集:NUS-WIDE和CUAVE。

3.1 評價指標

為了驗證基于計算模型的高階可能性聚類算法的有效性,實驗采用E*和RandIndex(RI)作為評價指標[15]。E*用來評估聚類算法產(chǎn)生的聚類中心的準確率,計算方法如公式(8)所示。

(8)

RI用來評估一個聚類將多少個數(shù)據(jù)對象劃分到正確的簇中。設(shè)數(shù)據(jù)集X的一個聚類結(jié)構(gòu)為C={C1,C2,…,CM},數(shù)據(jù)集的一個劃分為P={p1,p2,…,pS},可通過比較C和P以及鄰近矩陣與P來評價聚類的質(zhì)量。對數(shù)據(jù)集中任一點計算下列項:

SS:如果2個點屬于C中同一簇,且P中同一組;

SD:如果2個點屬于C中同一簇,但P中屬于不同組;

DS:如果2個點不屬于C中同一簇,而P中屬于同一組;

DD:如果2個點不屬于C中同一簇,且P中屬于不同組。

設(shè)a,b,c,d分別表示SS,SD,DS,DD的數(shù)目,則a+b+c+d=M為數(shù)據(jù)集中所有對的最大數(shù),即M=N(N-1)/2。其中:N為數(shù)據(jù)集中點的總數(shù)。RI指標的計算方式如公式(9)所示:

(9)

通常,RI值越高,表明聚類算法的結(jié)果越精確。

3.2 NUS-WIDE數(shù)據(jù)集

NUS-WIDE數(shù)據(jù)集是最大的帶有標記的Web圖像數(shù)據(jù)集,包含269,648張圖像。每張圖像均用文本進行標注。為了驗證4種算法的魯棒性,從NUS-WIDE數(shù)據(jù)集中隨機選取部分圖片,構(gòu)成8個數(shù)據(jù)子集,每個數(shù)據(jù)子集含有1萬張圖片,共14個類。在全部數(shù)據(jù)子集上進行實驗,對每個算法,執(zhí)行5次實驗,聚類結(jié)果如圖1和圖2所示。

圖1 聚類結(jié)果:E*

圖2 聚類結(jié)果:RI

圖1顯示了在整個數(shù)據(jù)子集上3個聚類算法獲得到E*值,從實驗結(jié)果中可以看到,在大部分情況下,提出的高階近鄰傳播聚類算法得到的E*值最小。

圖2顯示本文提出的高階近鄰傳播聚類算法得到的RI值最大,也就是說本文提出的聚類算法聚類結(jié)果比HOCPM算法更為準確。

3.3CUAVE數(shù)據(jù)集

表1 聚類結(jié)果

CUAVE數(shù)據(jù)集中包括36名志愿者,每個志愿者分別讀0到9這10個數(shù)字5次,構(gòu)成一個同時包含語音和文本的異構(gòu)數(shù)據(jù)集。為了驗證本文提出的算法的有效性,為數(shù)據(jù)集中每個數(shù)據(jù)對象加上文本標記。在CUAVE數(shù)據(jù)集上執(zhí)行每個算法5次,聚類結(jié)果如表1所示。

由于CUAVE數(shù)據(jù)集不存在理想的聚類中心,因此本文通過RI指標評估算法的聚類性能。從表1可以看出,在5次實驗中本文提出的高階近鄰聚類算法獲得到RI值最大。

4 結(jié) 論

本文提出一種基于張量距離的高階近鄰傳播算法,用于對異構(gòu)數(shù)據(jù)進行聚類。為了能夠?qū)悩?gòu)數(shù)據(jù)對象進行統(tǒng)一表示,采用張量模型對異構(gòu)數(shù)據(jù)對象進行表示。通過在近鄰傳播算法中引入張量距離度量數(shù)據(jù)對象在高階張量空間的相似性,捕捉異構(gòu)數(shù)據(jù)的分布特征,提高聚類精度。實驗結(jié)果表明本文提出的算法能夠有效的對異構(gòu)數(shù)據(jù)進行聚類,比當(dāng)前算法聚類精確度高。

[1]李朋,劉天華. 云平臺下基于粗糙集的并行算法的研究[J]. 沈陽師范大學(xué)學(xué)報(自然科學(xué)版), 2015,33(2):274-278.

[2]ZHANG Qingchen, YANG L T Y, CHEN Zhikui. Privacy preserving deep computation model on cloud for big data feature learning[J]. IEEE Transactions on Computers, 2015,DOI:10.1109/TC.2015.2470255.

[3]ZHANG Qingchen, CHEN Zhikui. A weighted kernel possibilistic c-means algorithm based on cloud computing for clustering big data[J].International Journal of Communication Systems, 2014, 27(9):1378-1391.

[4]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007,315:972-976.

[5]郭秀娟,陳瑩. AP聚類算法的分析與應(yīng)用[J].吉林建筑大學(xué)學(xué)報, 2013,30(4):58-61.

[6]劉曉勇,付輝. 一種快速AP聚類算法[J]. 山東大學(xué)學(xué)報(工學(xué)版), 2011,41(4):20-23.

[7]董俊,王鎖萍,熊范綸. 可變相似性度量的近鄰傳播聚類[J].電子信息學(xué)報, 2010,32(3):509-514.

[8]LONG B, ZHANG Z, WU X, et al. Spectral clustering for multi-type relational data[C]∥The 23rd International Conference on Machine learning. New York: ACM Press, 2006:585-592.

[9]MENG L, TAN A, XU D. Semi-supervised heterogeneous fusion for multimedia data co-clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2014,26(9):2293-2306.

[10]GU Q, ZHOU J. Co-clustering on manifolds[C]∥Proc of 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2009:359-367.

[11]BEKKERMAN R, SAHAMI M, LEARNED M E. Combinatorial Markov random fields[C]∥Proc. of European Conference on Principles and Practice of Knowledge Discovery in Databases. Berlin: Springer Press, 2006:30-41.

[12]KUANG L, HAO F, YANG L T, et al. A tensor-based approach for big data representation and dimensionality reduction[J]. Emerging Topics in Computing,IEEE Transactions on, 2014,2(3):280-291.

[13]LIU Y, LIU Y, CHAN K, Tensor distance based multilinear locality preserved maximum information embedding[J]. IEEE Transactions on Neural Networks, 2010,21(11):1848-1854.

[14]ZHANG Qingchen, YANG L T, CHEN Zhikui, et al. A high-order possibilistic c-means algorithm for clustering incomplete multimedia data[J].IEEE Systems Journal, 2015,DOI:10.1109/JSYST.2015.2423499.

[15]HAVENS T C, BEZDEK J C, HALL L O, et al. Fuzzy c-means algorithms for very large data[J]. IEEE Transactions on Fuzzy Systems, 2012,20(6):1130-1147.

A high-order affinity propagation clustering algorithm based on tensor distance

XUANYan1,ZHOUChuansheng2

(1. Software College, Shenyang Normal University, Shenyang 110034, China;2. College of Education Technology, Shenyang Normal University, Shenyang 110034, China)

Affinity propagation (AP) algorithm does not need to specify the number of clustering. When running the program, it can automatically identify the clustering center and the number of clustering. On the same data set, the result of AP clustering algorithm is stable and has good robustness. In addition, AP clustering algorithm can get accurate clustering results by using a variety of distance measuring methods. But current affinity propagation algorithm cannot be applied to heterogeneous data clustering. Aiming at this problem, the paper proposes a high-order affinity propagation algorithm based on tensor distance (HTDAP) for clustering heterogeneous data. The proposed algorithm represents each heterogeneous data object by the tensor, and introduces the tensor distance to measure the similarity between two objects. The tensor distance can capture the distribution features of the heterogeneous data sets in the high-order space by calculating the distance of the numerical values between the objects and measure the difference among the coordinate positions. Experimental results show the proposed scheme is effective in heterogeneous data clustering.

clustering; heterogeneous data; tensor distance; affinity propagation

2015-10-09。

遼寧省科技廳高等學(xué)校本科專業(yè)設(shè)置預(yù)測系統(tǒng)研究項目(遼教函[1008]225號)。

鉉 巖(1988-),女,內(nèi)蒙古赤峰人,沈陽師范大學(xué)碩士研究生; 通信作者: 周傳生(1966-),男,安徽霍邱人,沈陽師范大學(xué)教授。

1673-5862(2016)01-0096-04

TP391

A

10.3969/ j.issn.1673-5862.2016.01.022