王江晴，畢建權，帖軍，孫翀，艾勇

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

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

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

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

1 問題描述與形式化定義

MIL-GCC的目標是從訓練集中學習一組包圖結構與標記間的關系，用于對未知標記包分類．

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

2 構建包圖結構

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

定義2 包圖．對數(shù)據(jù)集D而言，包圖是指每個包Xi的圖結構信息，由節(jié)點集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中的帶標記的包映射成為一組帶標記的包圖之后，可以采用很多已有的方法挖掘包圖間的相關關系并建立分類器，例如建立一個圖核函數(shù)表示包圖之間的相似性，然后利用支持向量機SVM解決分類問題，或者通過挖掘所有包圖的頻繁項信息子圖表示其相似性，然后利用極限學習機ELM解決分類問題．雖然上述方法可以有較好的分類準確率，但是間接在包圖結構上建立分類器會造成模型運行效率低下問題，因此，本文基于直接在包圖結構上建立分類器的思想，利用圖卷積進行圖分類器的構建．

算法1 基于超示例的包圖結構構建算法輸入:數(shù)據(jù)集D,聚類簇數(shù)k和閾值β輸出:帶有標記的一組包圖gi,i∈{1,2,…,m}1for i in {1,2,…,m} do2隨機選擇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 構建圖分類器

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

(4)

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

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

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

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

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

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

4 實驗與分析

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

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

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

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

其中，N=10，sq表示第q次結果中所有Xi被正確分類的總數(shù)，tq表示第q次結果中樣本總數(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 實驗結果與分析

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

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

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

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

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

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

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

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

5 結語

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