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

鉉 巖, 周傳生

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

?

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

鉉 巖1, 周傳生2

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

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

聚類; 異構數據; 張量距離; AP算法

0 引 言

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

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

1 相關工作

1.1 近鄰傳播聚類算法

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

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

(1)

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

(2)

(3)

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

1.2 異構數據聚類相關工作

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

受到雙模態異構數據聚類算法的啟發,研究人員提出了多種針對多模態異構數據聚類的算法。最為典型的由Long等人提出的頻譜關聯聚類算法和由Hen等人提出的對稱非負矩陣分解算法[10]。由Bekkerman等人提出的聯合馬爾科夫隨機場算法,同時能夠用于半監督學習等應用[11]。

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

2.1 基于張量模型的異構數據表示

為了能夠對各種異構數據對象進行統一表示,本文利用張量模型表示異構數據對象。張量在數學上可以看作是向量的擴展,例如在同構的意義下,一階張量為一個向量Rd,N階張量表示為RI1×I2…×IN,其中N表示張量的階數,In表示張量第n階上的維數[12]。

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

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

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

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

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

(4)

其中,glm是系數,G是系數矩陣。

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

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

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

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

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

(5)

(6)

(7)

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

3 實驗與分析

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

3.1 評價指標

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

(8)

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

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

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

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

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

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

(9)

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

3.2 NUS-WIDE數據集

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

圖1 聚類結果:E*

圖2 聚類結果:RI

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

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

3.3CUAVE數據集

表1 聚類結果

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

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

4 結 論

本文提出一種基于張量距離的高階近鄰傳播算法,用于對異構數據進行聚類。為了能夠將異構數據對象進行統一表示,采用張量模型對異構數據對象進行表示。通過在近鄰傳播算法中引入張量距離度量數據對象在高階張量空間的相似性,捕捉異構數據的分布特征,提高聚類精度。實驗結果表明本文提出的算法能夠有效的對異構數據進行聚類,比當前算法聚類精確度高。

[1]李朋,劉天華. 云平臺下基于粗糙集的并行算法的研究[J]. 沈陽師范大學學報(自然科學版), 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聚類算法的分析與應用[J].吉林建筑大學學報, 2013,30(4):58-61.

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

[7]董俊,王鎖萍,熊范綸. 可變相似性度量的近鄰傳播聚類[J].電子信息學報, 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。

遼寧省科技廳高等學校本科專業設置預測系統研究項目(遼教函[1008]225號)。

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

1673-5862(2016)01-0096-04

TP391

A

10.3969/ j.issn.1673-5862.2016.01.022