腦網(wǎng)絡(luò)分類中的改進(jìn)圖核

張森森，張大坤

(天津工業(yè)大學(xué) 天津市自主智能技術(shù)與系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，天津 300387)

1 引 言

腦網(wǎng)絡(luò)分類研究已成為腦網(wǎng)絡(luò)分析的一個(gè)重要分支，圖核能夠判斷兩個(gè)腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似性，圖核的性能對(duì)分類結(jié)果有著重要的影響[1].圖核主要分為3種：基于游走的圖核、基于路徑的圖核和基于子樹或子圖的圖核[2-5].目前，很多學(xué)者對(duì)圖核進(jìn)行了研究，接標(biāo)等人提出了子網(wǎng)核來度量腦網(wǎng)絡(luò)之間的相似性，并將其應(yīng)用于腦疾病分類[6]；蔣強(qiáng)榮等人提出一種間隔通路核，將其應(yīng)用于文本之間的相似性計(jì)算[7]，此外，蔣強(qiáng)榮等人將圖核與神經(jīng)網(wǎng)絡(luò)相結(jié)合用于蛋白質(zhì)的分類[8].Mautner Stefan等人將圖核應(yīng)用于RNA的分類，取得較好的分類效果[9]；然而，很多的圖核忽略了圖的標(biāo)簽信息，不能有效地區(qū)分腦網(wǎng)絡(luò)數(shù)據(jù)之間拓?fù)浣Y(jié)構(gòu)的差異[10].

因此，本文提出了一種改進(jìn)圖核，該圖核將路徑中的節(jié)點(diǎn)加上標(biāo)簽信息作為判斷腦網(wǎng)絡(luò)相似性的因素之一，能有效地區(qū)分腦網(wǎng)絡(luò)數(shù)據(jù)之間拓?fù)浣Y(jié)構(gòu)的差異性，進(jìn)而提高了腦網(wǎng)絡(luò)分類的準(zhǔn)確率.

2 改進(jìn)圖核研究

2.1 圖核簡(jiǎn)介

2.1.1 圖核的作用

腦網(wǎng)絡(luò)分類中關(guān)鍵的問題是判斷腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似性，圖核作為衡量結(jié)構(gòu)性數(shù)據(jù)之間相似性的一種方法，能夠有效地判斷腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似性.

2.1.2 構(gòu)建圖核的理論基礎(chǔ)

1999年，美國斯坦福大學(xué)的Hausler教授提出了R-convolution理論，這是目前構(gòu)建圖核的理論基礎(chǔ)[11，12].對(duì)于一對(duì)圖數(shù)據(jù)G(V1，E1)和H(V2，E2)，通過算法F對(duì)圖G、H進(jìn)行分解.分解后得到的子圖集合記為{g1，g2，…，gi，…gn}和{h1，h2，…，hi，…h(huán)n}.根據(jù)R-convolution理論圖核函數(shù)定義式如公式(1)所示.

(1)

2.2 圖的分解算法

給定腦網(wǎng)絡(luò)數(shù)據(jù)集中的任意腦網(wǎng)絡(luò)數(shù)據(jù)G(V，E)，其中V表示G的節(jié)點(diǎn)集，E表示G的邊集.以G中任一節(jié)點(diǎn)vi為中心構(gòu)建節(jié)點(diǎn)vi的子網(wǎng)絡(luò).首先，求出節(jié)點(diǎn)vi到網(wǎng)絡(luò)中其他節(jié)點(diǎn)的最短路徑長度，將到節(jié)點(diǎn)vi的最短路徑小于k的節(jié)點(diǎn)集作為第i個(gè)子圖的節(jié)點(diǎn)集，原圖中對(duì)應(yīng)的邊作為子圖的邊集.由此，可得到G的子圖集G={G1，G2…，G116}.對(duì)于樣本中的任意腦網(wǎng)絡(luò)都可按照上述方法構(gòu)建出子圖集.

2.3 子結(jié)構(gòu)相似性度量函數(shù)設(shè)計(jì)

腦網(wǎng)絡(luò)G中的任意兩個(gè)節(jié)點(diǎn)vi，vj之間的最短路徑記為pij如公式(2)所示：

pij=(vi，vk1，vk2，…，vkt，vj)

(2)

對(duì)于網(wǎng)絡(luò)中的任意的一條最短路徑pij，都可以通過L(節(jié)點(diǎn)集到標(biāo)簽集的映射函數(shù))將其映射為帶有標(biāo)簽信息的最短路徑.節(jié)點(diǎn)vi，vj之間的最短標(biāo)簽路徑的定義如公式(3)所示：

Lij=(L(vi)，L(vk1)，…，L(vkt)，L(vj))

(3)

給定兩個(gè)需要進(jìn)行比較的子網(wǎng)數(shù)據(jù)g1和g2.M1和M2別表示g1和g2中節(jié)點(diǎn)之間的最短標(biāo)簽路徑的集合，將M1和M2的并集記為M，對(duì)于其中任一子網(wǎng)數(shù)據(jù)gi定義其最短標(biāo)簽路徑的特征向量，向量的元素計(jì)算公式如公式(4)所示：

(4)

其中Lj∈M.g1和g2之間的相似性度量核函數(shù)的定義如公式(5)所示：

(5)

該函數(shù)將兩個(gè)子網(wǎng)絡(luò)中加入了節(jié)點(diǎn)標(biāo)簽的最短路徑作為判斷兩個(gè)子網(wǎng)絡(luò)結(jié)構(gòu)之間的相似性的重要因素，能有效地判斷子網(wǎng)間拓?fù)浣Y(jié)構(gòu)的差異.

2.4 改進(jìn)圖核的提出與設(shè)計(jì)

2.4.1 改進(jìn)圖核的提出

目前一般研究中采用的圖核在計(jì)算數(shù)據(jù)之間的相似性時(shí)忽略了圖的標(biāo)簽信息，不能有效地區(qū)分腦網(wǎng)絡(luò)數(shù)據(jù)之間拓?fù)浣Y(jié)構(gòu)的差異.為此，本文提出一種改進(jìn)圖核，即加入節(jié)點(diǎn)標(biāo)簽信息的圖核.

2.4.2 改進(jìn)圖核表達(dá)形式

給定腦網(wǎng)絡(luò)數(shù)據(jù)集中的兩組腦網(wǎng)絡(luò)數(shù)據(jù)F、H，采用2.2的分解算法構(gòu)建其子網(wǎng)絡(luò)集{F1，F(xiàn)2，…，F(xiàn)n}和{H1，H2，…，Hn}.由公式(5)計(jì)算子結(jié)構(gòu)的相似性α=δ(Fi，Hi)，則腦網(wǎng)絡(luò)F、H之間的圖核函數(shù)的定義如公式(6)所示：

(6)

其中，λi為權(quán)重系數(shù).

為了更好地利用類間信息，本研究希望建立的核能夠使得不同類之間的樣本的函數(shù)值較小，因此，定義目標(biāo)函數(shù)如公式(7)和公式(8)所示：

maxJ(λ1，λ2，…，λn)=

(7)

(8)

其中，D+表示數(shù)據(jù)集中的正例樣本集，D-表示數(shù)據(jù)集中反例樣本集.

確定權(quán)值系數(shù)后，圖核函數(shù)也隨之確定下來.對(duì)于2組新的腦網(wǎng)絡(luò)數(shù)據(jù)可直接使用公式(6)計(jì)算圖核函數(shù)值.

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)從ADNI數(shù)據(jù)庫下載了72組功能性腦影像數(shù)據(jù)，其中包括32例輕度認(rèn)知障礙患者(MCI)的腦影像數(shù)據(jù)和40例健康人(CN)的腦影像數(shù)據(jù)，并將上述兩類腦影像數(shù)據(jù)處理成腦網(wǎng)絡(luò)數(shù)據(jù).腦影像數(shù)據(jù)提供者具體參數(shù)如表1所示.

表1 腦影像數(shù)據(jù)來源信息表Table 1 Brain image data provider information

3.2 實(shí)驗(yàn)過程及結(jié)果分析

3.2.1 實(shí)驗(yàn)設(shè)計(jì)

腦網(wǎng)絡(luò)的分類是為了區(qū)分CN腦網(wǎng)絡(luò)數(shù)據(jù)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)，圖核計(jì)算的MCI腦網(wǎng)絡(luò)數(shù)據(jù)與CN腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似度越小越有利于提高分類準(zhǔn)確率.為了驗(yàn)證本文提出的改進(jìn)圖核的有效性，采用最短路徑核[4]、子樹核[5]、多頻融合圖核[13]、特征選擇圖核[14]和本文提出的改進(jìn)圖核在MCI腦網(wǎng)絡(luò)和CN腦網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，將圖核計(jì)算MCI腦網(wǎng)絡(luò)數(shù)據(jù)和CN腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似度作為圖核性能的評(píng)判標(biāo)準(zhǔn).

3.2.2 實(shí)驗(yàn)過程及結(jié)果

本文提出的改進(jìn)圖核、多頻融合圖核和特征選擇圖核采用Python語言編程實(shí)現(xiàn)，并從開源代碼庫(GitHub)中下載了Grakel軟件包來實(shí)現(xiàn)最短路徑核和子樹核.Grakel由Python語言編寫完成，實(shí)現(xiàn)了比較常用的圖核.在每次實(shí)驗(yàn)中從CN腦網(wǎng)絡(luò)數(shù)據(jù)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)集中各隨機(jī)抽取10個(gè)腦網(wǎng)絡(luò)數(shù)據(jù)分別記為DCN和DMCI，然后采用不同的圖核計(jì)算DCN和DMCI之間任意兩個(gè)腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似性.對(duì)于每一種圖核都可以得到10*10個(gè)實(shí)驗(yàn)結(jié)果.對(duì)上述實(shí)驗(yàn)過程進(jìn)行4輪實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖1所示，其中橫坐標(biāo)表示腦網(wǎng)絡(luò)數(shù)據(jù)，縱坐標(biāo)表示采用5種圖核分別計(jì)算的DCN和DMCI數(shù)據(jù)之間的相似度.

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

為了更加具體地反映不同核函數(shù)的性能，本文計(jì)算了每次實(shí)驗(yàn)中不同的圖核計(jì)算的CN腦網(wǎng)絡(luò)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似度的平均值，計(jì)算結(jié)果如圖2所示.由圖2可見：在每次實(shí)驗(yàn)中，最短路徑核計(jì)算的CN腦網(wǎng)絡(luò)數(shù)據(jù)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間的平均相似度最大，說明最短路徑核不能較好地區(qū)分兩類腦網(wǎng)絡(luò)數(shù)據(jù)；子樹核、多頻融合圖核和特征選擇圖核計(jì)算的數(shù)據(jù)之間的平均相似度均小于0.2，與最短路徑相比效果較好，能夠較好地區(qū)分兩類數(shù)據(jù)的差異；本文提出的改進(jìn)圖核計(jì)算的CN腦網(wǎng)絡(luò)數(shù)據(jù)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間的平均相似度明顯小于0.1，相比于最短路徑核、子樹核、多頻融合圖核和特征選擇圖核，改進(jìn)圖核函數(shù)計(jì)算的CN腦網(wǎng)絡(luò)數(shù)據(jù)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似度最小，說明改進(jìn)圖核能夠更好地反映CN腦網(wǎng)絡(luò)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間的差異，并能提高分類的準(zhǔn)確率.原因分析：本文提出的改進(jìn)圖核在計(jì)算的過程中加入了節(jié)點(diǎn)的標(biāo)簽信息，能夠更有效地區(qū)分腦網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的差異，因此能夠更加精確地反映腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似度.

圖1 DCN和DMCI之間的相似度對(duì)比實(shí)驗(yàn)結(jié)果圖Fig.1 Experimental results of similarity between DCN and DMCI

圖2 不同圖核計(jì)算的數(shù)據(jù)的平均相似度Fig.2 Average similarity of data calculated by different graph cores

4輪實(shí)驗(yàn)結(jié)果的最大值、最小值和平均值如表2所示，對(duì)其分析可見，本文提出的改進(jìn)圖核計(jì)算的CN腦網(wǎng)絡(luò)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間的相似度的最大值、最小值和平均值均小于子樹核、多頻融合圖核、特征選擇圖核和最短路徑核計(jì)算的對(duì)應(yīng)值.改進(jìn)圖核計(jì)算的CN腦網(wǎng)絡(luò)和MCI腦網(wǎng)絡(luò)數(shù)據(jù)間的平均相似度為0.055，子樹核計(jì)算的平均相似度為0.167，多頻融合圖核計(jì)算的平均相似度為0.182，特征選擇圖核計(jì)算的平均相似度為0.185，最短路徑核計(jì)算的平均相似度為0.488，改進(jìn)圖核計(jì)算的平均相似性相比于子樹核降低了67.06%，相比于多頻融合圖核降低了69.78%，相比于特征選擇圖核降低了70.20%，相比于最短路核降低了88.72%，可見本文提出的改進(jìn)圖核效果明顯.

表2 CN和MCI腦網(wǎng)絡(luò)數(shù)據(jù)間相似度表Table 2 Table of similarity between CN and MCI brain network data

4 總 結(jié)

為了提高圖核判斷CN和MCI腦網(wǎng)絡(luò)數(shù)據(jù)之間相似性的準(zhǔn)確性，本文提出了一種加入了節(jié)點(diǎn)標(biāo)簽信息的改進(jìn)圖核.改進(jìn)圖核將節(jié)點(diǎn)的標(biāo)簽信息作為判斷腦網(wǎng)絡(luò)相似性的重要因素之一，有效地反映了腦網(wǎng)絡(luò)數(shù)據(jù)之間拓?fù)浣Y(jié)構(gòu)的差異性，能夠提高腦網(wǎng)絡(luò)分類的準(zhǔn)確率.為了驗(yàn)證改進(jìn)圖核的有效性，采用改進(jìn)圖核、子樹核、多頻融合圖核、特征選擇圖核和最短路徑核在腦網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，改進(jìn)圖核計(jì)算的平均相似度比子樹核計(jì)算的平均相似度降低了67.06%、相比于多頻融合圖核降低了69.78%、相比于特征選擇圖核降低了70.20%、比最短路徑核計(jì)算的平均相似度降低了88.72%.實(shí)驗(yàn)結(jié)果較好地驗(yàn)證了本文提出的改進(jìn)圖核的有效性.