基于子空間集成的多示例學習算法*

陳 濤

（深圳職業技術學院 教育技術與信息中心，廣東 深圳518055）

多示例學習是T.G.Dietterich 等人[1]在1997年研究藥物活性分子預測中提出的概念．它是通過對一組由多個示例組成的包訓練，預測未知包標簽的學習方法，被認為是一種新的機器學習框架，能被應用于解決預測藥物活性分子、文本分類、圖像檢索和分類等問題．

與有監督學習方法不同，多示例學習是對由多個示例組成的包進行學習和預測．包有標簽但沒有特征，示例有特征沒有標簽，包中的多個示例共享一個包的標簽．多示例學習框架中，訓練集由一組具有標簽的包組成，每個包中含有若干個沒有標簽的示例．若1 個包中至少有1 個正示例，則該包被標記為正包；若1 個包中所有示例都為負示例，則該包才被標記為負包．通過對訓練包的學習，希望學習系統能夠對新包標簽進行正確預測[2]．

近年來，有學者提出將示例特征空間變換為包特征空間[3,4]，將多示例學習轉換為有監督學習，如DD-SVM[5]、MILES[6]等算法．在集成學習算法上，蘇艷等[7]在2012年提出一種基于動態隨機特征子空間的半監督集成學習方法，應用到情感分類．王嬌等[8]提出將隨機子空間方法應用到半監督協同訓練學習．余國先等[9]將隨機子空間方法應用到基于圖的半監督學習分類，在人臉識別數據集上取得了較好的分類精度．

由于變換空間后的包特征維度較高，易帶來兩個問題：一是樣本數量小，特征維度高，使得分類器的泛化性能受到影響；二是在高維空間上的距離度量難以反映出樣本之間的近鄰結構信息，從而導致分類器的分類性能下降．針對這兩個問題，本文利用集成學習方法，通過多個弱分類器集成，來解決數據特征的高維問題以提高分類精度．

1 基于多個子空間集成的多示例學習分類器（MSEMIL）

一組有l個已標簽的多示例數據集L={＜B1,y1＞,＜B2,y2＞,...,＜Bl,yl＞}，u個未標簽的數據集U={Bl+1,Bl+2,...,Bl+u}，Bi= {Bi1,Bi2,...,Bini}，Bij∈Rd，i=1,...,n，j= 1,...,ni，ni為包Bi中的示例個數，d為示例的特征維數，yk∈{1 ,...,c},k=1,...,l，c為類別數，l+u=n．包Bi由多個示例Bij組成．包有標簽沒有特征；示例具有特征沒有標簽，包中的多個示例共享一個包的標簽．目標是在訓練集L上學習一個分類函數)(xf，使得 )(xf能正確預測未標簽包U的分類．

1.1 生成包特征

可以將多示例學習轉化為有監督學習，就需要先構造出一個包特征．一些文獻提出了不同的包特征生成方法，這里，我們采用MILES 算法[6]．其它包特征方法也適用MSEMIL 算法．

將一個包Bi向訓練集L中的所有示例（m個）映射，得到一個m維特征，映射公式為：

其中，Bij是包Bi的1 個示例．通過向所有示例投影映射，包中的多個示例特征融合為1 個新的包特征，每1 維代表包與1 個示例之間的相似度．2σ為1 個控制相似度取值大小的參數，這里取包Bi中所有示例與xk之間的歐氏距離均值．

將L+U中的每個包向L中的所有示例進行逐一投影映射，得到一個新的樣本集合X：

式（3）矩陣，列向量為一個包特征，列向量上的每一維是包與一個示例的相似度．由于包是向每一個示例進行的投影映射，這樣生成的包特征能夠不失真的反映包與示例間的關系．但是，會產生出2 個問題：1）例如MUSK2 數據集有6598 個示例，這樣，示例數較大，會產生高維特征問題；2）樣本數較大而維度較小，會產生過擬合問題．有必要對這些大量冗余或不相關屬性，先采取特征選擇或者約減．本文采用構造樣本子集和隨機選取特征子集的集成學習方法來處理這兩個問題．

1.2 生成T 個子空間

1.2.1 Bagging 法選取訓練樣本子集，與測試集組合形成Ts個樣本子集

多次Bagging 法，能得到多個訓練樣本子集．經過公式（1）后，得到訓練樣本集合X= ｛X1,X2,...,Xl｝．對訓練樣本集合進行Ts次Bagging 法，能得到Ts個訓練樣本子集Si(i∈ 1,...,Ts)．Si能被表示為：

得出Ts個訓練樣本子集 {S1,S2,...,STs}后，將它們分別與測試集組合，形成新的Ts個樣本子集{W1,W2,...,WTs}．

1.2.2 隨機選取特征子集

經過公式（1）映射函數后，得到的包特征是一個m維特征向量．即：有m維特征，F= ｛f1,f2,...,fm｝，fi是包中的一維特征．隨機選取特征子集方法，是在m維特征中隨機選取出d維，作為一個特征子集；接著重新在m維中隨機選取出d維特征；直至選取出Tf個特征子集為止．一個特征子集能表示為：

其中，f kj∈F（為特征集F中的一個特征，Fj?F為特征集F的一個子集，維度d＜m，Tf為隨機特征子空間的個數．

1.2.3 將Ts個樣本子集Wi向Tf個特征子集Fj上投影，得到T個子空間

將1 個樣本Xi向特征子集Fk=｛f1k,f2k,...,fdk｝投影，記為是指在原始特征為m維的Xi∈Rn×m上，選取出特征子集Fk上有的特征，去掉Fk子集上沒有的特征，形成新的d維特征的

令1 個樣本Xi向Tf個特征子集投票，能構造出Tf個新的樣本，有：

那么，一個樣本子集Wi，向Tf個特征子集的投影矩陣為：

將（7）投影矩陣的列向量看作一個子空間Rij，在每個子空間上訓練一個分類器，那么樣本子集Wi就有Tf個子空間，需要訓練Tf個子分類器．

總共能得到T=Ts×Tf個子空間．在每個子空間Rij(i∈1..Ts,j∈1..Tf)上訓練1 個子分類器Cij(Rij)，對測試集的分類結果為多個子分類器的集成投票．

1.3 在每個子空間上構造一個基礎子分類器

選用基于圖的半監督學習分類器LGC 作為子分類器[9]．LGC 方法是一個直推分類器，先需要構造出1 個圖，將多示例學習中的每個包作為圖中的1 個結點，結點之間采用邊權重連接．權重矩陣W能被表示為：

LGC 方法構造優化函數：

初始化y∈Rn×c向量，如果有已標記樣本xi屬于j類 (xi∈cj)，則yij=1，行向量yi的其余列被置為0；未標記樣本xk的行向量yk的所有列被置為0；f0=y．

計算出來的f∈Rn×c，是一個n×c矩陣，每一行向量fi代表樣本xi的分類結果，fij代表xi屬于類別jc的概率．如果需要判定樣本ix的分類類別，可以有：

1.4 合并子分類器的分類結果

這里，采用最大投票判別法集成子分類結果．把各個子分類器的輸出看作同等重要，選取少數服從多數的分類結果作為最后輸出．它被表示為：

昨晚妻子已向他提及這家新開的影樓。天下所有妻子都如她一般多疑嗎？還是他過于敏感？妻子問他，那家高美影樓的老板娘，你認識吧？

R為子分類器的個數．

2 實驗結果與分析

選取兩組實驗．第1 組為MSEMIL 算法在Corel圖像庫上進行分類，并與其它MIL 或MIL 集成學習算法作分類精度比較；第2 組為子空間參數對MSEMIL 算法分類精度影響．參數σ取各子空間上樣本兩兩之間的歐氏距離均值，k近鄰大小取5，參數α取值為0.2．取10 次隨機實驗結果的平均值．

實驗1：MSEMIL 算法的分類精度

通過在Corel 圖像集上的分類實驗，來驗證MSEMIL 算法的有效性．參與對比的6 個算法[5,6]有：MILES、DD-SVM、EM-DD 等3 個MIL 算法，和EMDD-bagging、MILES-LGC-bagging、MILESLGC-RS 等3 個MIL 集成學習算法．在Corel 2000數據集上的分類是一個多分類問題．MSEMIL、MILES-LGC-bagging、MILES-LGC-RS 等3 個算法采用半監督學習分類器作為基礎，能夠直接分類多類別問題．EM-DD-bagging 等其它4 個算法采用“一類反對余下類”的方法區分多類別，需要訓練c個分類器，選取輸出最大值的那個分類器作為圖像的標簽．實驗中，參數Ts取值15，Tf取值55，d取值120 時，獲得了實驗的最好性能．

第1 組實驗：在Corel 2000 數據集上的分類精度比較

選取Corel 2000 圖像庫作為圖像分類實驗的數據集．有20 類圖像，每類有100 幅圖像，共2000 幅圖像．采用DD-SVM[5]圖像分割方法，每個圖像被分割成5-10 個區域，每個區域用一個9維的特征表示．

為了考察未標簽圖像數對算法性能的影響，分別取100，間隔100，直到1000 幅訓練集圖像、未標簽圖像（測試集）數取時，執行實驗．MSEMIL 等7 個算法的分類精度如圖1所示．

第2 組實驗:子空間參數對MSEMIL 的分類精度影響

子空間參數有子空間的特征維數d和子空間個數T．其中，子空間個數受兩個參數影響T=Ts×Tf，一個是樣本子集個數Ts，一個是特征子集個數Tf．

圖1 在Corel 2000 圖像庫上的分類精度

實驗1：子空間的特征維數d對分類精度的影響

MSMIL 算法對子空間的特征維數d依賴較大，將d從50 增加到200，間隔10．Ts取15，Tf取50．圖7顯示了不同維數d時的分類精度變化：

從圖2可以看出，子空間特征維數d取50-120時，分類精度逐漸提高，到120 時，達到最高的分類精度86.8%．繼續增大維數d，分類精度不增反減．分析其原因，當d取較小的值時，子空間特征維數太小，子分類器得到的數據信息較少，不利于訓練分類器；當d取過大的值時，一是削弱了子空間之間的差異性，另一個是高維特征不利于LGC分類器上的圖的構建．

實驗2：特征子集個數Tf對分類精度的影響

考察特征子集個數Tf，取Tf從10 增加到70．Ts取15，d取120．圖3給出了不同的特征子集個數Tf的分類精度變化：

由圖3可以看出，特征子集個數Tf從10 增加到55 的過程中，分類精度穩步上升；從55 增加80 的過程中，分類精度變化不大．在特征子集維數d取120 的情況下，55 個子分類器的集成，已經能達到較好的精度，此時再增加特征子集個數Tf（等同于增加子分類器個數），也難以對分類精度有所提升．

圖2 不同子空間特征維數d 時分類精度

圖3 不同特征子集個數Tf 時分類精度

實驗3：樣本子集個數Ts對分類精度的影響

將樣本子集個數Ts從1 增加到20．Tf取55，d取120．圖4給出了不同的樣本子集個數Ts的分類精度變化：

從圖4可以看出，通過bagging 法構建多個樣本子集，增加了子分類器之間的差異性，能夠提高MSEMIL 的分類精度．當Ts取13 時，達到了最好的分類精度．但是，之后再增加樣本子集，并不能給MSEMIL 帶來分類精度的繼續提升．

圖4 不同樣本子集個數Ts 時分類精度

3 結 語

本文提出的基于多個子空間集成的多示例學習算法（MSEMIL），通過變換示例特征空間為包生成一個包特征，將多示例學習轉換為有監督學習．利用集成學習來處理包特征的高維問題，融合bagging 法構造樣本子集和概率選取特征子集，集成多個子空間上構造分類器的差異性．用半監督學習分類器作為基礎分類器，利用未標簽數據來參與學習，提高算法的分類精度．在Corel 數據集上的實驗表明，MSEMIL 具有分類精度高的特點．