鄧超， 劉桂霞， 孫立巖， 王榮全

(1.吉林大學(xué) 軟件學(xué)院，吉林 長(zhǎng)春 130012； 2.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130012)

近鄰傳播聚類(lèi)算法(affinity propagation clustering AP算法)[1]是2007年由Frey等提出并發(fā)表在《Science》上的聚類(lèi)算法。與其他的 聚類(lèi)算法相比，AP算法有較高的精度，在應(yīng)用方面AP算法有較少的約束條件，但在適應(yīng)不同形式的數(shù)據(jù)方面相對(duì)不足，肖宇等[2]提出SAP(semi-supervised Affinity propagation)算法，利用數(shù)據(jù)中的先驗(yàn)信息，調(diào)整相似性矩陣，在先驗(yàn)性信息較多的情況下，算法適應(yīng)性較好。AP算法特點(diǎn)在于，參考度的值與聚類(lèi)結(jié)果相關(guān)，因此本文融合ECC[3]與CD[4]方法對(duì)AP算法進(jìn)行改進(jìn)，動(dòng)態(tài)設(shè)置參考度，不再簡(jiǎn)單的設(shè)置為所有數(shù)據(jù)中位數(shù)的值。

我們進(jìn)入了大數(shù)據(jù)時(shí)代，在大數(shù)據(jù)中挖掘出有用的信息，已經(jīng)成為科技發(fā)展的主流趨勢(shì)[5]。單一的串行模式耗時(shí)長(zhǎng)、效率低。為了解決這個(gè)問(wèn)題，一些大數(shù)據(jù)計(jì)算平臺(tái)隨之產(chǎn)生。其中基于內(nèi)存計(jì)算的Spark[6]分布式平臺(tái)倍受關(guān)注。它的生態(tài)圈十分豐富，包括特定場(chǎng)景下的計(jì)算庫(kù)(Streaming、SQL、MLlib、Graphx)。此外其數(shù)據(jù)保存在內(nèi)存中，減少了多次計(jì)算中磁盤(pán)的I/O開(kāi)銷(xiāo)。AP算法聚類(lèi)的過(guò)程中，需要在矩陣之間不斷地進(jìn)行迭代替換，算法運(yùn)算時(shí)間較長(zhǎng)，面對(duì)海量數(shù)據(jù)，單機(jī)串行實(shí)現(xiàn)AP算法，不能滿(mǎn)足實(shí)驗(yàn)計(jì)算需求。為了改進(jìn)對(duì)處理海量數(shù)據(jù)的適應(yīng)能力。本文提出基于Spark并行運(yùn)算改進(jìn)的AP算法SIAP(spark based on improved AP)，提高算法的運(yùn)行速率。

蛋白質(zhì)復(fù)合物是由2個(gè)以上功能相關(guān)且相互作用連接在一起的蛋白質(zhì)組成[7]。目前，蛋白質(zhì)復(fù)合物的識(shí)別手段分為生物實(shí)驗(yàn)和計(jì)算方法兩大類(lèi)，生物實(shí)驗(yàn)方法持續(xù)周期長(zhǎng)、實(shí)驗(yàn)成本高，而計(jì)算方法可以更好的彌補(bǔ)生物實(shí)驗(yàn)技術(shù)的不足。通過(guò)不斷的發(fā)展，出現(xiàn)很多蛋白質(zhì)復(fù)合物識(shí)別算法，MCODE算法檢測(cè)網(wǎng)絡(luò)中蛋白質(zhì)鏈接相對(duì)密集的簇為蛋白質(zhì)復(fù)合物[8]，PCP采用FS加權(quán)的方法構(gòu)造有權(quán)圖，然后在加權(quán)網(wǎng)絡(luò)中通過(guò)尋找稠密子圖預(yù)測(cè)蛋白質(zhì)復(fù)合物[9]。本文應(yīng)用AP算法識(shí)別蛋白質(zhì)復(fù)合物。首先，PPI數(shù)據(jù)形式多樣[10]，本文對(duì)數(shù)據(jù)進(jìn)行評(píng)分處理，并應(yīng)用Spark平臺(tái)對(duì)AP算法進(jìn)行并行化處理，并給出加速比圖示。最后分別在黑腹果蠅(dm)和人類(lèi)(hs)2個(gè)真實(shí)PPI數(shù)據(jù)集上對(duì)本文改進(jìn)的AP算法與原始的AP算法、clusterone[11]、OH-PIN[12]、IPCA[13]等算法進(jìn)行比較，最后引入F-Measure[14]評(píng)價(jià)指標(biāo)對(duì)結(jié)果進(jìn)行評(píng)估，并給出實(shí)驗(yàn)效果圖。

1 基于ECC與CD改進(jìn)的AP算法

1.1 AP算法

AP算法的基本思想基于數(shù)據(jù)點(diǎn)，在數(shù)據(jù)點(diǎn)之間進(jìn)行消息的傳遞，通過(guò)迭代運(yùn)算自動(dòng)識(shí)別聚類(lèi)中心。AP的計(jì)算過(guò)程是通過(guò)不斷更新吸引度矩陣和歸屬度矩陣實(shí)現(xiàn)的。

吸引度r(i,k)中,i為數(shù)據(jù)對(duì)象，k表示作為候選代表點(diǎn)的數(shù)據(jù)對(duì)象，r(i,k)則代表從點(diǎn)i發(fā)送到候選聚類(lèi)中心k的數(shù)值消息，反映的是k點(diǎn)是否適合作為i點(diǎn)的聚類(lèi)中心[15]。吸引度的定義為：

(1)

式中：s(i,k)表示i點(diǎn)與k點(diǎn)之間的相似度；a(i,k)代表歸屬度，表示從候選中心k發(fā)送到i的數(shù)值消息，反映i點(diǎn)是否選擇k作為聚類(lèi)中心[15]。歸屬度的定義為：

(2)

在算法的運(yùn)算過(guò)程中，產(chǎn)生的聚類(lèi)結(jié)果可能不穩(wěn)定，加入震蕩系數(shù)，用于調(diào)節(jié)算法的穩(wěn)定性：

rt+1(i,k)=λrt(i,k)+(1-λ)rt+1(i,k)

(3)

at+1(i,k)=λat(i,k)+(1-λ)at+1(i,k)

(4)

式中：t和t+1分別代表上一次和本次的迭代結(jié)果；λ為震蕩系數(shù)。

基于式(3)、(4)，AP算法的運(yùn)算過(guò)程如下：

1)輸入數(shù)據(jù)生成相似度矩陣，并設(shè)置參考度，在原始的算法中一般設(shè)為數(shù)據(jù)中位數(shù)的值。

2)輸入所需的最大迭代次數(shù)和震蕩變量λ的值，構(gòu)造初始為零矩陣的吸引度與歸屬度矩陣，并進(jìn)行矩陣的迭代，更新數(shù)據(jù)。

3)確定聚類(lèi)中心，以r(k,k)+a(k,k)>0為準(zhǔn)則，輸出聚類(lèi)中心以及每個(gè)點(diǎn)所屬的類(lèi)別，算法結(jié)束。

1.2 基于ECC與CD改進(jìn)的AP算法

實(shí)驗(yàn)中應(yīng)用的數(shù)據(jù)是無(wú)權(quán)的PPI數(shù)據(jù)，為了達(dá)到更好的實(shí)驗(yàn)結(jié)果，將PPI數(shù)據(jù)生成的網(wǎng)絡(luò)中的邊標(biāo)記權(quán)重[16]，ECC和CD是2種很有效的加權(quán)方法[3-4]：

(5)

(6)

式中Nu和Nv分別為蛋白質(zhì)u和v的鄰居數(shù)量。

本文將2種方法結(jié)合，使加權(quán)的精度更高。以此構(gòu)造相似度矩陣。權(quán)重公式定義為：

W(u,v)=βECC(u,v)+(1-β)CD(u,v)

(7)

在構(gòu)造相似度矩陣時(shí)，要設(shè)定參考度的值，傳統(tǒng)的AP算法將對(duì)角線(xiàn)設(shè)為統(tǒng)一的定值，本文應(yīng)用權(quán)重結(jié)果，動(dòng)態(tài)分配對(duì)角線(xiàn)的值，使鄰接邊多的并且具有更高權(quán)重值的數(shù)據(jù)點(diǎn)，賦值越大，加大成為聚類(lèi)中心的幾率。參考度為：

i,k,n∈m,s(i,k)>0

(8)

式中：s(i,k)為i行中大于0的值；n為當(dāng)前行s(i,k)的個(gè)數(shù);ave為所有邊權(quán)重的均值。

改進(jìn)的AP算法的運(yùn)算步驟如下：

1)根據(jù)式(7)、(8)，對(duì)輸入的數(shù)據(jù)進(jìn)行打分賦值，生成相似度矩陣，并得出參考度的值。

2)輸入最大迭代次數(shù)maxIter和震蕩變量λ的值，更新迭代吸引度矩陣和歸屬度矩陣。

3)以r(k,k)+a(k,k)>0為標(biāo)準(zhǔn)，輸出聚類(lèi)中心以及每個(gè)點(diǎn)所屬的類(lèi)別，算法結(jié)束。

2 基于Spark的改進(jìn)AP算法

Spark是一個(gè)高速運(yùn)算級(jí)別的，具有強(qiáng)大功能的開(kāi)源式計(jì)算引擎。有著Hadoop的MapReduce[17]中的優(yōu)點(diǎn)，并擴(kuò)展了MapReduce的計(jì)算模式，Spark的分布式計(jì)算更高效。Spark整體架構(gòu)基于4大部分Spark Streaming、Spark SQL、Mlib、Graphx,如圖1所示。

圖1 Spark架構(gòu)Fig.1 The architecture of Spark

Spark的主要核心是彈性分布式數(shù)據(jù)集，即RDD[18](resilient distributed datasets),RDD是一個(gè)只讀的，緩存在內(nèi)存中的數(shù)據(jù)集。在并行計(jì)算中應(yīng)用RDD可以減少內(nèi)外存的讀寫(xiě)操作。并且支持map、reduce、collect等數(shù)據(jù)操作。此外單機(jī)模式，應(yīng)用到大數(shù)據(jù)中會(huì)有很多限制，達(dá)不到運(yùn)算要求。Spark以集群的模式進(jìn)行部署，Spark子集群結(jié)構(gòu)如圖2所示。集群中一共有2類(lèi)節(jié)點(diǎn)，master負(fù)責(zé)資源管理，Slave則負(fù)責(zé)計(jì)算。

圖2 Spark子群結(jié)構(gòu)Fig.2 The subgroup structure of Spark

基于以上理論基礎(chǔ)，本文AP算法進(jìn)行并行化處理。此外在算法并行的過(guò)程中內(nèi)存會(huì)受到限制，RDD應(yīng)用的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)方式至關(guān)重要，本文將list類(lèi)型與tuple類(lèi)型相結(jié)合，以三元組的形式存儲(chǔ)數(shù)據(jù)，生成最小內(nèi)存的RDD，存儲(chǔ)結(jié)構(gòu)形式如下：

List[tuple(rowid,rowValues)],其中rowid為行號(hào)，rowValues為第rowid行的numpy數(shù)組。

讀取數(shù)據(jù)，2條數(shù)據(jù)之間有邊連接，則將數(shù)據(jù)的編號(hào)和邊的權(quán)值存儲(chǔ)在List里，2條數(shù)據(jù)之間沒(méi)有邊連接則不存儲(chǔ)。將相似性矩陣s,吸引度矩陣r，歸屬度矩陣a數(shù)據(jù)構(gòu)建RDD的操作如下所示：

s=sc.parallelize(l,NUM_PARTITIONS)；s=s.map(lambdax: f0(x,count))

其中f0為數(shù)據(jù)格式轉(zhuǎn)換函數(shù)，讀List進(jìn)行操作，轉(zhuǎn)換成數(shù)據(jù)矩陣中行的形式，并應(yīng)用map函數(shù)生成一個(gè)新的RDD。

a=sc.parallelize(range(count),NUM_PARTITIO-NS)；

a=a.map(lambdat:(t,np.zeros(count)))

r=sc.parallelize(range(count),NUM_PARTITIO-NS)；

r=r.map(lambdat:(t,np.zeros(count)))

其中NUM_PARTITIONS是并行分配的參數(shù),count為數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

基于Spark平臺(tái)SIAP算法具體執(zhí)行過(guò)程如下所示：

輸入：原始的PPI數(shù)據(jù)集，打分調(diào)節(jié)變量β，震蕩變量λ，最大迭代次數(shù)maxIter.

1)初始化：s[count][count]=0，r[count][count]=0，a[count][count]=0

2)根據(jù)式(7)計(jì)算相似度，為邊加權(quán)重,并存儲(chǔ)到s中

3)根據(jù)式(8)更新參考度的值s[i,i]

4)構(gòu)建s矩陣，r矩陣，a矩陣RDD

5)初始化i=1

6)根據(jù)式(3)更新吸引度矩陣r；

根據(jù)式(4)更新歸屬度矩陣a；

7)l=i+1,如果l

8)如果a(i,i)+r(i,i)>0:

則第i個(gè)數(shù)據(jù)為聚類(lèi)中心，存儲(chǔ)在數(shù)組centers中

9)數(shù)據(jù)分類(lèi)，計(jì)算找出a(i,i)+r(i,i)每行所屬聚類(lèi)中心的最大值，將該點(diǎn)分配到此聚類(lèi)中心。返回RDD所有元素

10)輸出結(jié)果，算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

本文將SIAP算法應(yīng)用于蛋白質(zhì)復(fù)合物識(shí)別中，以此來(lái)驗(yàn)證SIAP聚類(lèi)的加速效果，并根據(jù)F-measure將SIAP算法與AP、Cytoscape[19]軟件中的clusterone、OH-PIN、IPCA這4種算法進(jìn)行對(duì)比，實(shí)驗(yàn)中分別采用Drosophila melanogaster(dm)[20]數(shù)據(jù)集與Homo sapiens(hs)[21]數(shù)據(jù)集作為測(cè)試對(duì)象。參照集本文使用Vinayagam等的蛋白質(zhì)復(fù)合物數(shù)據(jù)集[22]。

3.1 實(shí)驗(yàn)環(huán)境

本文選擇Spark2.4.0作為數(shù)據(jù)計(jì)算框架，操作系統(tǒng)為Ubuntu16.04,python版本為3.5.2，Anaconda版本為4.2.0，分布式環(huán)境由5臺(tái)物理機(jī)組成，master為主節(jié)點(diǎn)，slave1～slave4為worker節(jié)點(diǎn)，各節(jié)點(diǎn)的配置如表1所示。

3.2 實(shí)驗(yàn)結(jié)果

在并行計(jì)算中采用加速比來(lái)驗(yàn)證效果，加速比是指，同一任務(wù)在單處理系統(tǒng)和并行處理系統(tǒng)中運(yùn)行消耗時(shí)間的比率。加速比定義為：

(9)

表1 實(shí)驗(yàn)環(huán)境配置參數(shù)

實(shí)驗(yàn)應(yīng)用黑腹果蠅(dm)和人類(lèi)(hs)2個(gè)真實(shí)數(shù)據(jù)集分別在2、4、8、16個(gè)節(jié)點(diǎn)上運(yùn)行SIAP算法，算法運(yùn)行時(shí)間如圖3所示。

圖3 算法運(yùn)行時(shí)間Fig.3 The runtime of algorithm

由圖3可知，針對(duì)2種數(shù)據(jù)集，隨著計(jì)算節(jié)點(diǎn)數(shù)的增加，2種數(shù)據(jù)集的運(yùn)行時(shí)間均呈現(xiàn)下降趨勢(shì)，并且接近線(xiàn)性趨勢(shì)。說(shuō)明算法有良好的拓展性，適用于處理不同的數(shù)據(jù)集，未呈現(xiàn)線(xiàn)性的原因是在算法運(yùn)行過(guò)程中，需要將數(shù)據(jù)分片處理，在不同的節(jié)點(diǎn)間，要進(jìn)行信息交流，數(shù)據(jù)傳遞需要消耗一部分時(shí)間。為了使對(duì)比更加明顯，針對(duì)2種數(shù)據(jù)集的算法加速比如圖4所示。

圖4 算法加速比Fig.4 The acceleration ratio of algorithm

從圖4中可以看出，隨著計(jì)算節(jié)點(diǎn)數(shù)的增加，加速比的增加趨勢(shì)形式正相關(guān)，但與線(xiàn)性趨勢(shì)有一定差距，隨著節(jié)點(diǎn)數(shù)的增多，差距略微變大。未呈現(xiàn)線(xiàn)性的原因，同樣是由于節(jié)點(diǎn)之間的信息傳遞需要一定的額外時(shí)間。通過(guò)Spark平臺(tái)的應(yīng)用，縮短了單線(xiàn)程運(yùn)算的時(shí)間，充分體現(xiàn)的算法的并行化的速度優(yōu)勢(shì)。

為了驗(yàn)證算法的準(zhǔn)確率，引入綜合評(píng)價(jià)指標(biāo)F值(F-Measure)對(duì)識(shí)別的蛋白質(zhì)復(fù)合物進(jìn)行評(píng)估,準(zhǔn)確率(precision)和召回率(recall)是F值的重要參數(shù)。準(zhǔn)確率是指算法識(shí)別的蛋白質(zhì)復(fù)合物中被匹配部分所占比例，召回率是指已知蛋白質(zhì)復(fù)合物中被匹配部分所占比例，具體為：

(10)

式中：TP是指算法識(shí)別出的蛋白質(zhì)復(fù)合物與已知復(fù)合物匹配的數(shù)值；FP是指算法識(shí)別出的蛋白質(zhì)復(fù)合物總數(shù)減去TP數(shù)的值；FN表示不能被算法識(shí)別出的蛋白質(zhì)復(fù)合物匹配的已知復(fù)合物的數(shù)值。

F值的定義為：

(11)

F值是綜合正確率與召回率的一種評(píng)估指標(biāo)，反映整體的綜合效果。F值越大，代表所得到的聚類(lèi)結(jié)果越好?；?個(gè)真實(shí)dm數(shù)據(jù)集與hs數(shù)據(jù)集，SIAP算法與原始的AP算法、clusterone、OH-PIN、IPCA這4個(gè)聚類(lèi)算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 算法對(duì)比結(jié)果Fig.5 The comparison result of algorithm

通過(guò)圖5分析可知SIAP與未改進(jìn)得AP算法在兩種數(shù)據(jù)集中，都有良好的聚類(lèi)效果。clusterone在2種數(shù)據(jù)集中，結(jié)果相差不大，也表明了clusterone聚類(lèi)算法對(duì)數(shù)據(jù)集的適應(yīng)能力。針對(duì)不同的數(shù)據(jù)集SIAP算法的精度高于其他聚類(lèi)算法，證明了SIAP算法的有效性。

4 結(jié)論

1)引入ECC和CD這2種加權(quán)方法，對(duì)無(wú)權(quán)的蛋白質(zhì)相互作用網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行加權(quán)處理。

2)設(shè)置動(dòng)態(tài)的參考度，將參考度與邊的緊密型關(guān)聯(lián)起來(lái)。

3)應(yīng)用Spark平臺(tái)對(duì)算法進(jìn)行并行化計(jì)算，縮短了算法的運(yùn)行時(shí)間，提高了算法的運(yùn)行速率。

實(shí)驗(yàn)中將SIAP與原始的AP算法以及clusterone、OH-PIN、IPCA算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明，SIAP算法在不同數(shù)據(jù)集上均有最高的F值，達(dá)到了良好的聚類(lèi)精度證明了算法的有效性。在接下來(lái)的研究中，將考慮生物意義，將聚類(lèi)算法與生物學(xué)信息相結(jié)合，提出更有效的蛋白質(zhì)復(fù)合物識(shí)別方法。