一種基于聚類的圖卷積多示例學(xué)習(xí)算法

王江晴，畢建權(quán)，帖軍，孫翀，艾勇

(中南民族大學(xué) 計算機(jī)科學(xué)學(xué)院&湖北省制造企業(yè)智能管理工程技術(shù)研究中心，武漢 430074)

多示例學(xué)習(xí)的概念源自醫(yī)學(xué)領(lǐng)域制藥過程中何種分子適合制藥問題[1]，一個對象被定義為一個包，每個包由多個示例組成并由一個標(biāo)記與之對應(yīng)，學(xué)習(xí)的目的是建立一個學(xué)習(xí)器，對未知標(biāo)記的包進(jìn)行分類[2]．目前，多示例學(xué)習(xí)算法被成功地應(yīng)用到圖像分類與標(biāo)注[3]、自然語言處理[4]、股票趨勢預(yù)測[5]等領(lǐng)域．

近年來，多示例學(xué)習(xí)的研究可以分為挖掘示例間關(guān)系、挖掘包與標(biāo)記間關(guān)系和關(guān)鍵示例檢測[6,7]三種．MIGraph、miGraph方法[8]是典型的基于圖結(jié)構(gòu)挖掘示例間關(guān)系的多示例學(xué)習(xí)方法，核心思想是將包視為圖，包中的每個示例視為圖中的節(jié)點(diǎn)，分別利用ε-graph和親和度矩陣構(gòu)建包圖結(jié)構(gòu)，設(shè)計一個圖核函數(shù)來捕獲包圖間各節(jié)點(diǎn)的相似性，用以作為構(gòu)建分類器的依據(jù)．由于隨機(jī)選擇包中的示例構(gòu)建圖結(jié)構(gòu)，因此在模型分類準(zhǔn)確率上還有較大的提升空間．SCPMK_MIL方法[9]利用譜聚類方法獲取潛在的正示例代表，利用徑向基函數(shù)和金字塔核分別挖掘正示例間和負(fù)示例間的相似性，但未充分考慮包間的相似性問題．MI-SVM方法[10]和DD-SVM方法[11]使用有監(jiān)督學(xué)習(xí)的支持向量機(jī)SVM挖掘包與標(biāo)記間關(guān)系，雖然這些方法具有較好的泛化能力和小樣本學(xué)習(xí)能力，但是求解的目標(biāo)函數(shù)很難直接計算，導(dǎo)致訓(xùn)練效率較低．MGML-ELM方法[12]、BELM-MIL方法[13]和RBF-MIP方法[14]在此基礎(chǔ)上利用神經(jīng)網(wǎng)絡(luò)提高模型的訓(xùn)練效率，但是降低了模型的可解釋性，同時在基于圖結(jié)構(gòu)的方法中存在子圖轉(zhuǎn)為特征向量造成模型運(yùn)行效率低下等問題．

本文針對隨機(jī)選擇包中的示例構(gòu)建圖結(jié)構(gòu)和模型運(yùn)行效率低下的問題，提出了一種基于聚類的圖卷積多示例學(xué)習(xí)算法MIL-GCC(Multi-Instance Learning Algorithm of Graph Convolution Base on Clustering)．MIL-GCC主要分為2個步驟：(1)構(gòu)建包的圖結(jié)構(gòu)，利用k-means聚類方法獲取包中具有代表性的示例作為包圖中的節(jié)點(diǎn)，然后挖掘超示例間關(guān)系構(gòu)建包圖的邊；(2)構(gòu)建圖分類器，將構(gòu)建好的包圖結(jié)構(gòu)轉(zhuǎn)為鄰接矩陣的形式作為圖卷積層的輸入，利用圖卷積對節(jié)點(diǎn)重要度分?jǐn)?shù)進(jìn)行學(xué)習(xí)，篩選重要度分?jǐn)?shù)排序靠前的節(jié)點(diǎn)以及這些節(jié)點(diǎn)組成的包圖結(jié)構(gòu)作為模型分類的依據(jù)．

1 問題描述與形式化定義

MIL-GCC的目標(biāo)是從訓(xùn)練集中學(xué)習(xí)一組包圖結(jié)構(gòu)與標(biāo)記間的關(guān)系，用于對未知標(biāo)記包分類．

令X=d表示示例空間．定義D={(X1,y1),…,(Xi,yi),…，(Xm,ym)}表示具有m個包的MIL數(shù)據(jù)集，其中Xi={xi1,…,xij,…,xipi}?X被稱為一個包，yi∈Y={0,1}是Xi所屬的標(biāo)記；xij∈X是一個由d維特征向量表示的示例，即xij=[xij1,…，xijl,…，xijd]′;pi表示Xi中示例個數(shù)的總數(shù)．如果存在index∈{1,…，j,…，pi}，使得xi,index是一個正示例，則Xi是正包且yi=1；否則Xi是負(fù)包且yi=0．該模型的目標(biāo)是從數(shù)據(jù)集D中學(xué)習(xí)一個多示例分類器f∶2X→Y．

2 構(gòu)建包圖結(jié)構(gòu)

MIL-GCC算法的第1步是構(gòu)建包圖結(jié)構(gòu).包圖結(jié)構(gòu)的構(gòu)建可以分為兩部分，一部分是選取每個包中的超示例作為包圖的節(jié)點(diǎn)，另一部分是根據(jù)超示例間關(guān)系在定義好的約束條件下創(chuàng)建包圖的邊.本節(jié)首先對超示例、包圖的概念進(jìn)行了定義，然后對構(gòu)建包圖的具體實(shí)現(xiàn)進(jìn)行詳細(xì)的描述.

定義2 包圖．對數(shù)據(jù)集D而言，包圖是指每個包Xi的圖結(jié)構(gòu)信息，由節(jié)點(diǎn)集Vi={vi1,…，vij,…，vini}、邊集Ei={(via,vib),…，(vic,vid)}組成，其中，a,b,c,d∈{1,2,…,ni}且a≠b,c≠d,|Ei|=ei表示包圖中邊個數(shù)的總數(shù)．包圖簡記為：gi,i∈{1,2,…,m}.

(1)

其中，算法1中C(2S×2S)表示每個包聚類的搜索范圍，S=sqrt(pi/k)表示相鄰聚類中心的步長，pi代表第i個包中示例總數(shù)，k為第i個包中簇中心總數(shù)；l(ij)表示第i個包中第j個示例所屬的簇類別，初始值為-1；d(ij)表示第i個包中第j個示例到任意簇中心的距離，初始值為∞；dist表示包中任意示例與簇中心之間的歐式距離，計算公式如下：

(2)

(3)

通過算法1將數(shù)據(jù)集D中的帶標(biāo)記的包映射成為一組帶標(biāo)記的包圖之后，可以采用很多已有的方法挖掘包圖間的相關(guān)關(guān)系并建立分類器，例如建立一個圖核函數(shù)表示包圖之間的相似性，然后利用支持向量機(jī)SVM解決分類問題，或者通過挖掘所有包圖的頻繁項信息子圖表示其相似性，然后利用極限學(xué)習(xí)機(jī)ELM解決分類問題．雖然上述方法可以有較好的分類準(zhǔn)確率，但是間接在包圖結(jié)構(gòu)上建立分類器會造成模型運(yùn)行效率低下問題，因此，本文基于直接在包圖結(jié)構(gòu)上建立分類器的思想，利用圖卷積進(jìn)行圖分類器的構(gòu)建．

算法1 基于超示例的包圖結(jié)構(gòu)構(gòu)建算法輸入:數(shù)據(jù)集D,聚類簇數(shù)k和閾值β輸出:帶有標(biāo)記的一組包圖gi,i∈{1,2,…,m}1for i in {1,2,…,m} do2隨機(jī)選擇k個超示例簇中心{x′i1,…,x′is,…,x′iki}3初始化xij所屬類別為l(ij)=-1,距離d(ij)=∞4repeat5for x′ilin {x′i1,…,x′is,…,x′iki} do6for xijin C(2S×2S) do7 計算x′il與xij之間的歐式距離dist8 if dist

3 構(gòu)建圖分類器

本文利用公式(4)獲得每個包圖gi的鄰接矩陣信息，并作為圖卷積層的輸入．

(4)

在計算每個節(jié)點(diǎn)重要度分?jǐn)?shù)的基礎(chǔ)上，還考慮了包圖間的不同尺度問題，即對于任意2個包圖gi和gj，其中i≠j，存在ni≠nj和ei≠ej的情況，通過設(shè)置一個保留節(jié)點(diǎn)比例的超參數(shù)δ∈(0,1]，對每個zscorej進(jìn)行降排序，篩選前δni個節(jié)點(diǎn)進(jìn)行特征的學(xué)習(xí)．每次篩選相當(dāng)于對包圖結(jié)構(gòu)和特征進(jìn)行更新，具體的包圖結(jié)構(gòu)更新計算公式如下：

A′=Amask,mask,V′=Vmask,:,

其中，A′和V′分別表示保留節(jié)點(diǎn)之間的鄰接矩陣和節(jié)點(diǎn)特征矩陣；Amask,mask表示根據(jù)前δni個節(jié)點(diǎn)的節(jié)點(diǎn)索引mask對A同時進(jìn)行行切片和列切片；Vmask,:表示按照mask對V進(jìn)行列切片．

雖然通過層層丟棄節(jié)點(diǎn)的方式可以提高包圖中遠(yuǎn)距離節(jié)點(diǎn)的融合效率，但是會降低對所有節(jié)點(diǎn)信息的有效融合，因此，本文采用全局最大池化與全局平均池化[17]拼接的方式對包圖的全局信息進(jìn)行一次性融合，拼接過程如圖1所示．

圖1 全局平均池化與全局最大池化拼接過程Fig.1 Splicing process of global average pooling and global maximum pooling

最后將學(xué)習(xí)到的包圖全局信息用于分類．基于圖卷積的圖分類器模型相比于已有的基于SVM、ELM等分類模型，忽略了包圖中節(jié)點(diǎn)數(shù)和邊數(shù)對模型的影響，因此，在包圖中節(jié)點(diǎn)數(shù)和邊數(shù)較大時具有一定的優(yōu)勢．

4 實(shí)驗與分析

4.1 數(shù)據(jù)集與實(shí)驗環(huán)境

本文選取5個多示例學(xué)習(xí)基準(zhǔn)數(shù)據(jù)集(Musk1、Musk2、Elephant、Fox、Tiger)和1個真實(shí)圖像數(shù)據(jù)集(2000-Image)對提出的算法進(jìn)行評價．多示例學(xué)習(xí)基準(zhǔn)數(shù)據(jù)集的具體屬性信息見表1．2000-Image圖像數(shù)據(jù)集匯總包含20類COREL圖像，每個類別由100張像素為64×96的彩色圖像組成，每個圖像都視為一個包，圖像中的每個段被視為一個示例．

表1 多示例學(xué)習(xí)基準(zhǔn)數(shù)據(jù)集具體屬性信息Tab.1 Specific attribute information of multi-instance learning benchmark datasets

在實(shí)驗中，本文使用10倍交叉驗證來比較結(jié)果．將數(shù)據(jù)集分為10份，輪流將其中9份作為訓(xùn)練集，一份作為測試集，進(jìn)行實(shí)驗，將10次結(jié)果的準(zhǔn)確率的平均值作為算法的評判指標(biāo)，具體的計算公式如下：

其中，N=10，sq表示第q次結(jié)果中所有Xi被正確分類的總數(shù)，tq表示第q次結(jié)果中樣本總數(shù)．

實(shí)驗環(huán)境為16 G內(nèi)存的Windows10操作系統(tǒng)，其CPU為AMD Ryzen 5 4600U with Radeon Graphics，主頻為2.1 GHz，編程語言為Python 3.7.6．

4.2 實(shí)驗結(jié)果與分析

本文的實(shí)驗過程主要分為4個部分，第1部分是對數(shù)據(jù)集進(jìn)行預(yù)處理，即確定每個輸入數(shù)據(jù)集中示例規(guī)模的一致；第2部分是構(gòu)建包圖結(jié)構(gòu)，本文采用局部k-means方法獲取每個包中的超示例，然后根據(jù)邊成立的約束條件確定包圖結(jié)構(gòu)，并根據(jù)訓(xùn)練/測試集所占比隨機(jī)劃分訓(xùn)練/測試集；第3部分為了保證實(shí)驗對比的公平性，實(shí)驗對基于多示例多標(biāo)記的MGML-ELM方法進(jìn)行了單標(biāo)記的條件約束，然后和MIL-GCC分別進(jìn)行分類器的構(gòu)建；第4部分則是通過評判指標(biāo)對實(shí)驗結(jié)果進(jìn)行分析與總結(jié)．

影響實(shí)驗結(jié)果的參數(shù)主要有：示例的聚類數(shù)n，閾值β，圖卷積隱藏層層數(shù)h，節(jié)點(diǎn)保留比δ．為了確定模型的最優(yōu)分類準(zhǔn)確率，本文實(shí)驗依據(jù)表2的實(shí)驗各參數(shù)取值范圍分別對模型進(jìn)行準(zhǔn)確率的計算，其中，對于基準(zhǔn)數(shù)據(jù)集，在n=20,β=1,h=60,δ=0.6時，可達(dá)到最優(yōu)分類準(zhǔn)確率；對于圖像數(shù)據(jù)集，在n=100,β=1,h=120,δ=0.8時，可達(dá)到最佳分類準(zhǔn)確率．

表2 實(shí)驗各參數(shù)取值范圍Tab.2 The range of parameters in the experiment

實(shí)驗的對比結(jié)果見表3，通過在基準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集上與MIGraph[8]、miGraph[8]、MIKI[6]、MGML-ELM*(MGML-ELM進(jìn)行單標(biāo)記條件約束后的算法簡稱)[12]的比較，可以發(fā)現(xiàn)MIL-GCC在Musk1、Musk2數(shù)據(jù)集上沒有MIGraph、miGraph和MIKI分類準(zhǔn)確率高，但是，在圖像類數(shù)據(jù)集上相對其他3種方法具有很好的分類準(zhǔn)確率，同時從所有數(shù)據(jù)集平均準(zhǔn)確率的角度看，MIL-GCC具有一定的分類準(zhǔn)確率優(yōu)勢．

表3 基于各數(shù)據(jù)集下的各算法準(zhǔn)確率對比Tab.3 Comparison of accuracy of each algorithm based on each dataset %

經(jīng)實(shí)驗驗證，MIL-GCC在Musk1、Musk2數(shù)據(jù)集上準(zhǔn)確率不高的主要原因是，MIL-GCC在數(shù)據(jù)集預(yù)處理過程選擇局部k-means算法不利于挖掘Musk1、Musk2數(shù)據(jù)集中超示例相關(guān)性，采用k-means算法準(zhǔn)確率可達(dá)90%，但MIL-GCC在圖像數(shù)據(jù)集準(zhǔn)確率和總數(shù)據(jù)集的平均準(zhǔn)確率上未占優(yōu)勢．

同時，為了驗證MIL-GCC可以有效地提高算法的執(zhí)行效率，分別在基準(zhǔn)數(shù)據(jù)集和圖像數(shù)據(jù)集上與MIGraph、miGraph、MGML-ELM*算法進(jìn)行比較，對比結(jié)果如圖2所示，可以清晰地發(fā)現(xiàn)基于圖像數(shù)據(jù)集，MIL-GCC算法相對于其他3種算法需要的運(yùn)行時間較少，因此，MIL-GCC算法在處理規(guī)模較大的數(shù)據(jù)集時也具有一定的優(yōu)勢．

圖2 各算法執(zhí)行效率對比Fig.2 Comparison of execution efficiency of each algorithm

5 結(jié)語

本文提出的MIL-GCC算法通過利用局部k-means聚類方法確定構(gòu)建包圖的超示例的集合，然后通過挖掘示例間的相關(guān)性確定包圖結(jié)構(gòu)，最后基于圖卷積思想直接在包圖上建立圖分類器，忽略了包圖中節(jié)點(diǎn)數(shù)和邊數(shù)對圖分類模型的影響．實(shí)驗驗證了MIL-GCC的性能，同時在圖像分類領(lǐng)域有明顯的成效．然而，MIL-GCC在分子數(shù)據(jù)集上還存在提升的空間，因此，如何更充分地選擇構(gòu)建包圖的超示例成為下一步的主要工作．