結(jié)合模糊聚類的多示例集成算法

韓海韻，楊有龍，孫麗芹

西安電子科技大學 數(shù)學與統(tǒng)計學院，西安 710126

1997年，Dietterich等人[1]在研究分子活性問題時發(fā)現(xiàn)：同一種分子在不同的條件下有不同的低能形狀，專家只知道該分子具有活性，但不知道是哪一種低能形狀對分子的活性起作用。若將有活性分子的全部低能形狀都作為正示例，無活性分子的全部低能形狀作為負示例，然后用傳統(tǒng)監(jiān)督分類器訓練，在預測階段，會導致很高的假陽性率，為此，Dietterich等人[1]提出了多示例學習。在多示例學習框架下，訓練對象是包，一個包中有多個示例，包的標簽是已知的，包中示例的標簽是未知的，多示例學習的目標是對未知包進行標記。標準多示例假設(shè)規(guī)定：正包中至少有一個正示例，負包中全部都是負示例。在分子活性預測問題中，分子由包表示，分子的低能形狀由示例表示，活性分子對應包的標簽為正，無活性分子對應包的標簽為負。多示例學習現(xiàn)已應用于更加廣泛的領(lǐng)域，如圖像分類、文本分類、目標識別、股票預測等。

目前，主要有三類多示例方法：示例空間的方法、包空間的方法、嵌入空間的方法。示例空間的方法認為具有區(qū)分度的信息存在于示例之間，訓練示例級的分類器，如APR[1]、Diverse Density[2]、mi-SVM[3]、RSIS[4]等；包空間的方法認為具有區(qū)分度的信息存在于包之間，把包視為一個整體，定義包之間的距離和相似性，訓練包級的分類器，如Citation-KNN[5]、CCE[6]、MinD[7]、BoW[8]等；嵌入空間的方法基于一組示例原型，將包映射到嵌入空間，在嵌入空間中，包由一個特征向量表示，然后用傳統(tǒng)的監(jiān)督算法學習分類器，如MILES[9]、MILIS[10]、MILDM[11]、MILMPC[12]等。

目前許多多示例方法都對數(shù)據(jù)隱式地做出了假設(shè)：（1）正包中正示例的比例；（2）示例的分布。APR算法學習一個超矩形區(qū)域，正包中至少有一個示例在該超矩形內(nèi)，負包中所有示例都不在該矩形內(nèi)；DD算法學習一個概念點，正包中至少有一個示例離該點很近，負包中所有示例都遠離該點，APR和DD都對正示例的分布做出了隱含假設(shè)：正示例來自一個緊湊的簇。因此，它們只在單模態(tài)分布的數(shù)據(jù)上效果較好，不適用于多模態(tài)分布的數(shù)據(jù)。Simple-MI[13-14]將包映射為最小最大向量，mi-SVM和MI-SVM[3]的初始階段，將包表示為其所包含示例的算數(shù)平均值，它們都假設(shè)了正包中全部都是正示例。SVR-SVM[15]和r-rule[16]估計了正包中正示例的比例，假設(shè)正包中正示例的比例在所有包中都是相同的，是一個定值。MILIS要對負示例做高斯核密度估計，當數(shù)據(jù)量較小時，估計是不準確的。

為解決上述問題，本文提出了基于模糊聚類的多示例集成算法ISFC（instance selection based on fuzzy clustering）。該算法對數(shù)據(jù)未做任何假設(shè)，是一個示例空間的方法，其將聚類和隨機子空間的特性與多示例學習相結(jié)合，提出“正得分”的概念，降低了示例標簽的歧義性，同時考慮到將負包中的負示例分類錯誤的代價更大，設(shè)計了一種改進的Bagging集成[17]策略，此外，該集成策略還解決了正包數(shù)量多、負包數(shù)量少情況下的類別不平衡問題。

1 相關(guān)知識

1.1 隨機子空間法

子空間，又叫屬性子集，是從初始的高維空間投影生成的低維屬性空間。不同的子空間提供了觀察數(shù)據(jù)的不同視角，顯然，從不同的子空間訓練出的個體學習器必然有所不同。隨機子空間算法[18]依賴于輸入屬性的擾動，從初始屬性集中提取出若干個屬性子集，再用提取出的屬性子集訓練不同的基學習器。一方面，隨機子空間法使得原始特征信息被充分利用，獲得多樣化的個體學習器；另一方面，由于屬性數(shù)量的減少，節(jié)省了時間開銷，避免了小樣本問題，消除了無關(guān)和冗余屬性對訓練過程的干擾。

1.2 模糊C-均值聚類

模糊C-均值（FCM）聚類[19-20]是K-Means聚類的改進算法，它在K-Means的基礎(chǔ)上引入了模糊理論，是一個軟聚類算法。一般的聚類算法將數(shù)據(jù)硬劃分，類別的劃分界限是明確的，數(shù)據(jù)對象嚴格地歸屬于某個類，屬于每個類的隸屬度取值為0或1的離散值。但在現(xiàn)實世界中，數(shù)據(jù)對象具有多樣性，在性態(tài)和類屬方面存在著模糊性，通常不完全歸屬于某個類，而是同時歸屬于多個類，且屬于每個類的程度是不同的。因此硬劃分聚類不能很好地反映對象和類別間的實際關(guān)系。FCM建立了數(shù)據(jù)對象與類別歸屬的模糊不確定描述，對象同時歸屬于多個類，屬于某個類的隸屬度取值為[0，1]上的連續(xù)值，刻畫了其屬于每個類的程度，與硬聚類相比，更加客觀地反映了數(shù)據(jù)對象與類別間的關(guān)系，提供了更加靈活的聚類結(jié)果，提高了聚類效果，與實際更為相符。

FCM是一個如式（1）的優(yōu)化問題：

其中u ij表示樣本x i屬于簇j的隸屬度，uij越接近1，則x i屬于簇j的可能性越大。K是簇的數(shù)量，n是示例的數(shù)量，c j是簇j的中心，p是平滑系數(shù)，用于控制算法的靈活性。

FCM迭代地計算隸屬度u ij和簇中心c j，以找到最佳隸屬度劃分，迭代的終止條件見式（2）：

其中s是當前的迭代次數(shù)，ε＞0是收斂閾值。

最終，可以得到一個隸屬度矩陣U∈Rn×K。例如，示例x i的聚類結(jié)果對應于隸屬度矩陣的第i行[0.2，0.5，0.15，0.15]，表明x i屬于第二個簇的可能性最大。

2 結(jié)合模糊聚類的多示例集成

2.1 符號說明

D={(B1,L1),(B2,L2),…,(B m,L m)}是訓練集，m是包的數(shù)量，B i={x i1,x i2,…,x ini}是第i個訓練包，n i是第i個包的示例數(shù)量，x ij∈Rd是第i個包中的第j個示例，L i是第i個包的標簽，Li∈{-1,1}。

2.2 基于方差貢獻率的隨機子空間

本文使用主成分分析（PCA）[21]對原始數(shù)據(jù)進行降維，PCA可以得到每個新特征的方差貢獻率，方差貢獻率表示一個特征包含的信息比例，能夠度量一個特征的重要程度。因此，本文基于特征的方差貢獻率構(gòu)造隨機子空間，方差貢獻率越大的特征，被選為子空間特征的概率越大，方差貢獻越小的特征，被選為子空間特征的概率越小。

子空間生成方法如下：

步驟1計算訓練數(shù)據(jù)的協(xié)方差矩陣。

步驟2計算協(xié)方差矩陣的特征值λi以及對應的特征向量，一個特征向量對應一個新的特征方向，特征值用來描述對應特征方向包含的信息量。

步驟3計算第i個新特征的方差貢獻率：

將其作為第i個新特征的權(quán)重，可以得到一個特征選擇概率分布cr=(cr1,cr2,…,cr r)。

步驟4基于特征選擇概率分布cr，選擇特征子集。

一方面，該子空間的生成方法是高效的，因為特征重要性的評估，不需要花費額外的計算開銷，而是重復利用了PCA時得到的方差貢獻率；另一方面，生成的子空間是有效的，因為子空間是基于特征選擇概率cr，而不是等概率生成的，包含信息越多的特征，越重要的特征，被選擇的可能性越大。因此，與完全隨機子空間相比，基于方差貢獻率生成的子空間刻畫數(shù)據(jù)的能力更強、更準確，各子空間之間也具有差異性，在其內(nèi)訓練學習器，效果可以得到保證。該子空間生成方法的偽代碼見算法1。

算法1基于方差貢獻率的隨機子空間

輸入：訓練集D，保留的方差比例α，選擇的特征比例β

輸出：生成的隨機子空間H

2.將數(shù)據(jù)居中Z=D-1·μT

4.計算特征值(λ1,λ2,…,λd)=特征值(Σ)

5.forr=1,2,…,ddo

7.end

8.降維，選擇最小的r，使得f(r)≥α

9.用式（3）計算r個新特征的方差貢獻cr=(cr1,cr2,…,cr r)

11.基于特征選擇概率cr，從r個新特征中隨機地選擇h個特征，得到子空間H

2.3 示例的正得分

聚類是在對象無標記信息的情形下，基于對象之間的相似性，將對象分組的方法。多示例學習中，正包中示例標簽是未知的，因此，可以通過聚類挖掘示例的信息。數(shù)據(jù)并不總是嚴格地屬于某個分組，F(xiàn)CM聚類算法能夠得到每個示例屬于每個簇的概率，因此該算法中示例和簇的關(guān)系，與實際相符。但由于缺少數(shù)據(jù)的先驗信息，如類別、形狀、密度等，一次聚類的結(jié)果往往不佳，在不同的子空間對數(shù)據(jù)進行聚類，能夠從不同的角度觀察數(shù)據(jù)，得到更全面的信息。

正得分用于衡量示例標簽為正的可能性，其借助了聚類和隨機子空間法，并結(jié)合了負包中全部都是負示例這一基本多示例假設(shè)。正得分的基本思想如下：聚類后，對于正包中的一個示例，如果它所在的簇，大部分的示例來自負包，則表明它與負示例的相似度較高，那么其標簽為負的可能性較大；反之，如果它所在的簇，只有很少的示例來自負包，則表明它與負示例的相似度較低，那么其標簽為負的可能性較小。

正得分的計算方法如下：

步驟1用算法1生成R個隨機子空間H1,H2,…,H R，H i?F，其中F是全空間。

步驟2將訓練包中的所有示例在子空間H1,H2,…,H R上投影，然后在每個子空間中將示例用FCM聚類。在每個子空間中，示例都被劃分為K個簇。

步驟3計算每個子空間的每個簇中，示例來自正包的比例。

對于子空間Ht中的第n個簇，示例來自正包的比例是：

其中：

C n,t是在子空間Ht中聚類后，屬于第n個簇的示例集合， |C n,t|是該集合的大小。

對于某一個子空間中的某一個簇，如果該簇中所有的示例都來自正包，那么P n(t)=1；如果該簇中所有的示例都來自負包，那么P n(t)=0。

步驟4計算示例x ij的正得分S ij：

其中：

u(x ij,n,t)是在子空間H t中用FCM算法聚類后，示例x ij屬于第n個簇的隸屬度。

正得分用來評估示例標簽為正的可能性，正得分越高，示例標簽為正的可能性就越大，因此其降低了包中示例標簽的歧義性。在目標識別和目標追蹤等領(lǐng)域，只知道包的標簽是不夠的，還需要知道包中哪個示例最有可能是正例，此時，包中正得分最高的示例，就是尋找的目標。計算正得分的偽代碼見算法2。

算法2正得分的計算

輸入：訓練集D，簇的數(shù)量K，子空間的數(shù)量R

輸出：正得分S ij

1.fort=1,2,…,Rdo

2.用算法1生成子空間H t，然后將訓練包中的示例在子空間Ht上投影，投影后，用FCM算法對示例進行聚類

3. forx ij∈Ddo

4.forn=1,2,…,Kdo

5.在子空間Ht聚類后，用式（4）計算第n個簇中，示例來自正包的比例Pn(t)，同時，得到示例xij屬于第n個簇的隸屬度u(x ij,n,t)

6.end

7.end

8.end

9.forxij∈Ddo

10.用式（6）計算x ij的正得分S ij

11.end

2.4 包代表示例的選擇策略

從每個正包中選出一個示例，從每個負包中選出合適數(shù)量的示例，作為包的代表示例，然后將它們作為基分類器的訓練子集，代表示例的標簽是其所屬包的標簽。代表示例選擇策略的基本思想如下：正包中至少包含一個正示例、一個假陽性和一個假陰性的示例都不一定導致錯誤的包標簽；而負包中全部都是負示例，一個假陽性的示例一定導致錯誤的包標簽[22-23]，所以，應盡可能地保證負包中的負示例被正確分類。

正包和負包中都是越“正”的示例，即正得分越高的示例，被選為代表示例的可能越大。對于正包來說，盡量避免了從中選出負示例；對于負包來說，其內(nèi)全部都是負示例，理論上，負包中所有示例的正得分都很低，本文仍然給予與正類相關(guān)性更強的那些示例更大被選的可能性，這樣能夠迫使訓練出的決策邊界移向正類，盡量保證負示例被正確分類。

根據(jù)上述策略選擇包的代表示例之前，需要借助一個soft-max函數(shù)，將示例的正得分S ij轉(zhuǎn)化為一個[0，1]之間的概率值，該值表示示例被選為代表示例的概率，稱為選擇概率。選擇概率與正得分是正相關(guān)的。對于任意一個包，其內(nèi)包含的所有示例的選擇概率的和為1，在包Bi中，示例x ij被選擇的概率為P ij：

其中τ＞0是溫度參數(shù)。當τ趨近于∞時，包中每個示例被選擇的概率幾乎相等；當τ趨近于0時，正得分最高的示例被選擇的概率趨近于1，正得分最低的示例被選擇的概率趨近于0。

2.5 集成設(shè)計

設(shè)計了一個Bagging集成的變體，由于支持向量機（SVM）的性能較好，所以將其作為基分類器。根據(jù)2.4節(jié)中的代表示例選擇策略，為每個基分類器提供不同的訓練子集。一般情況下，正包和負包中都選擇一個示例；在正包數(shù)量多、負包數(shù)量少的情況下，靈活地從每個負包中選擇合適數(shù)量的示例，從每個正包中仍然選擇一個示例，這樣在數(shù)據(jù)的層面上，解決了此種類別不平衡問題。因為負包中只包含負示例，所以無論從負包中選出多少示例，都不會導致錯誤的訓練集，而嚴格地限制從每個正包中選擇一個示例，是為了盡可能地避免從正包中選出負示例，從而防止訓練出的分類器錯誤地標記負示例。

各基分類器的訓練數(shù)據(jù)是基于示例選擇概率被隨機選擇的，一方面，隨機性保證了各基分器之間的差異性；另一方面，基于示例選擇概率，而不是等概率，保證了各基分類器的質(zhì)量。

2.6 包標簽的預測

首先，每個基分類器為每個示例預測一個標簽，第k個基分類器預測示例x ij的標簽為yij,k，y ij,k∈{-1,1}；其次，采用簡單平均法，結(jié)合各基分類器的預測結(jié)果，確定示例xij的最終決策值y ij，yij∈R。

其中M是集成規(guī)模；然后，根據(jù)標準多示例假設(shè)，確定包B i的最終決策值y i，y i∈R。

最后，將包Bi的決策值與0進行比較，確定包Bi的標簽L i。

2.7 算法步驟

綜上所述，本文提出的ISFC算法主要涉及5個步驟：

步驟1（生成子空間）基于特征的方差貢獻率，生成多個隨機子空間。

步驟2（計算示例的正得分）在生成的子空間，用模糊C-均值將訓練示例聚類，再根據(jù)聚類結(jié)果，計算每個示例的正得分，評估示例標簽為正的可能性。

步驟3（計算示例的選擇概率）將示例的正得分轉(zhuǎn)換為選擇概率，為盡可能地避免從正包中選出負示例和將負包中的負示例分類正確，正包和負包中的示例，都是正得分越高，選擇概率越大。

步驟4（抽取訓練子集）基于示例選擇概率，從每個包中隨機選出代表示例，作為基分類器的訓練子集，代表示例的標簽是其所屬包的標簽。

步驟5（確定包最終的標簽）采用簡單平均法，結(jié)合各基分類器的結(jié)果。

ISFC算法的完整偽代碼見算法3。

算法3結(jié)合模糊聚類的多示例集成算法

訓練階段

輸入：有標記的訓練包B l，集成規(guī)模M，子空間的數(shù)量R，子空間選取的特征比例β，簇的數(shù)量K，溫度τ

輸出：集成分類器C

1.用算法2計算每個示例xij的正得分Sij

2.用式（8）將正得分Sij轉(zhuǎn)換為選擇概率

3.C=?

4.fork=1,2,…,Mdo

5.基于示例選擇概率Pij從每個正包中選擇一個示例，從每個負包中選擇合適數(shù)量的示例，構(gòu)成訓練子集S k，然后用S k訓練基分類器C k

6.C=C?Ck

7.end

測試階段

輸入：未標記的測試包B u，集成分類器C

輸出：預測的標記L u

1.fork=1,2,…,Mdo

2.forxij∈Budo

3.用基分類器Ck預測示例xij的標簽y ij,k，然后用式（9）計算示例xij的決策值y ij

4.end

5.end

6.Lu=?

7.forB i∈Budo

8.用式（10）計算包B i的預測值yi，用式（11）確定包B i的標簽L i

9.Lu=L u?L i

10.end

3 實驗及分析

本文共進行了6組實驗。實驗一將ISFC與其他7個多示例算法進行了比較；實驗二驗證了正得分和代表示例選擇策略的有效性；實驗三驗證了集成設(shè)計的有效性；實驗四驗證了方差貢獻率度量的有效性；實驗五分析了ISFC的參數(shù)敏感性；實驗六分析了隨機性對ISFC性能的影響。此外，還對ISFC算法進行了時間復雜度分析。

3.1 數(shù)據(jù)集

本文針對4個不同的任務(wù)：藥物分析活性預測（Musk1、Musk2、Atom、Bonds、Chains），圖像分類（Tiger、Elephant、Fox），文本分類（新聞組N.g.1、N.g.2、N.g.6、N.g.10、N.g.11、N.g.13、N.g.18）和火車挑戰(zhàn)（EastWest），在16個多示例基準數(shù)據(jù)集上進行了實驗，表1描述了它們的相關(guān)細節(jié)信息。特別地，Atoms、Bonds、Chains數(shù)據(jù)集中正包數(shù)量是負包數(shù)量的2倍，是類別不平衡問題。新聞組數(shù)據(jù)集（N.g.）中，正包中正示例的比列很低，約為3%左右[24]。

表1 實驗數(shù)據(jù)集Table 1 Experimental datasets

3.2 實驗設(shè)置

為避免所選數(shù)據(jù)的偏倚，在除EastWest的其他15個數(shù)據(jù)集上進行10次10折交叉驗證，EastWest數(shù)據(jù)集包的數(shù)量較小，若同樣采用10次10折交叉驗證，會產(chǎn)生相同的訓練和測試數(shù)據(jù)，所以EastWest數(shù)據(jù)集進行了9次5折交叉驗證。本文報告了在所有測試數(shù)據(jù)上準確率和ROC曲線下的面積（AUC）的平均值，還報告了準確率95%的置信區(qū)間。

對比算法為Citation-KNN、MILBoost[25]、Simple-MI、CCE、K-means-encoding（BoW）、RSIS和MILDM。選擇Citation-KNN，因為它是經(jīng)典的包空間方法；選擇Simple-MI，因為它假設(shè)正包中全部都是正示例；選擇MILBoost，因為它是經(jīng)典的多示例集成算法；選擇CCE和BoW，因為它們都使用了聚類方法，此外，CCE也有SVM的集成過程；選擇RSIS，因為它與ISFC也降低了示例標簽的歧義性，ISFC是其改進算法；選擇MILDM，因為它是性能很好的嵌入空間方法，優(yōu)于當前大部分嵌入空間方法。

3.3 實驗結(jié)果及分析

3.3.1 ISFC與其他多示例算法對比

表2和表3分別報告了算法的準確率和AUC，表2的最后一列是準確率的95%置信區(qū)間，兩表的最后一行都是基于度量指標的算法平均排名。

表2 準確率Table 2 Accuracy

表3 ROC曲線下的面積Table 3 Area under ROC curve %

16個實驗數(shù)據(jù)集中，示例的分布是不同的，每個正包中正示例的比例也是不同的，基于準確率和AUC，ISFC的平均排名都是最高的，這表明示例的分布和正包中正示例的比例對ISFC性能的影響不大。ISFC在9個數(shù)據(jù)集上取得了最高的準確率，在8個數(shù)據(jù)集上取得了最高的AUC。在Bonds、Chains、EastWest、N.g.2、N.g.13這5個數(shù)據(jù)集上，ISFC的準確率具有明顯優(yōu)勢，分別比準確率第二高的算法高出3.15%、3.8%、3.66%、16.58%、1.4%；在EastWest、N.g.2、N.g.6、N.g.10、N.g.11這5個數(shù)據(jù)集上，ISFC的AUC具有明顯優(yōu)勢，分別比AUC第二高的算法高出10.23%、1.96%、1.02%、8.72%、1.7%。特別地，F(xiàn)ox數(shù)據(jù)集很難分類，每個算法在該數(shù)據(jù)集上的分類效果都較差，相比之下，ISFC在該數(shù)據(jù)集上取得了最高的準確率和AUC。

表4～6分別報告了8個算法在3種不同學習任務(wù)上性能的平均排名，在文本和圖像分類數(shù)據(jù)集上，基于準確率和AUC，ISFC的平均排名都是第一；在藥物分子活性預測數(shù)據(jù)集上，基于準確率，ISFC平均排名第二；基于AUC度量，ISFC平均排名第三。ISFC在文本分類任務(wù)中非常成功，在5個新聞組數(shù)據(jù)集上，獲得了最高的準確率和AUC。該類數(shù)據(jù)集中，正包中正示例的比例很低（3%左右），正包中的大部分示例對包的標簽是無效的。包空間和嵌入空間的方法分別直接，間接地學習包的整體結(jié)構(gòu)，如Citation-KNN、CCE、BoW、MILDM，當正包中有效示例非常少時，即正示例的比例較低時，正包的整體結(jié)構(gòu)與負包的整體結(jié)構(gòu)較為相似，此時正包和負包不容易區(qū)分，分類性能就會下降。

表4 圖像分類任務(wù)上的平均排名Table 4 Average ranking on image classification tasks

表5 文本分類任務(wù)上的平均排名Table 5 Average ranking on text classification tasks

表6 分子活性預測任務(wù)上的平均排名Table 6 Average ranking on molecular activity prediction tasks

表7報告了類別不平衡問題（Atoms、Bonds和Chains數(shù)據(jù)集）中，8個算法性能的平均排名。基于準確率和AUC，ISFC均為第一，因為ISFC在代表示例選擇過程中，從每個負包中選擇了兩個示例，在數(shù)據(jù)層面解決了類別不平衡問題，從而提高了分類性能。

表7 類別不平衡任務(wù)上的平均排名Table 7 Average ranking on imabalanced tasks

ISFC算法通過“正得分”衡量了示例為正例的可能性，降低了正包中示例標簽的歧義性。RSIS算法[4]是降低示例標簽歧義性的典型方法，也衡量了示例為正例的可能性。理論上，一方面，ISFC的子空間是基于特征的方差貢獻率生成的，包含信息量越多的特征被選為子空間特征的概率越大，而RSIS算法中，各特征被選為子空間特征的概率是相等的，相比之下，ISFC生成的子空間對數(shù)據(jù)的刻畫更加有效，在其內(nèi)訓練的學習器性能更好；另一方面，ISFC在子空間中用FCM算法將示例聚類，得到了每個示例屬于每個簇的隸屬度，并將其引入到正得分的計算，而RSIS用K-Means算法將示例聚類?，F(xiàn)實情況下，示例通常同時屬于多個簇，與K-Means相比，F(xiàn)CM這種軟聚類與實際更為相符，因此，與RSIS相比，ISFC通過方差貢獻率和模糊隸屬度，衡量示例為正例可能性的方法更加準確可靠。從實驗結(jié)果來看，ISFC性能的平均排名優(yōu)于RSIS，其在15個數(shù)據(jù)集上的準確率高于RSIS，在11個數(shù)據(jù)集上的AUC高于RSIS，同時在表4～7表明其在各類多示例任務(wù)上的表現(xiàn)也都優(yōu)于RSIS。因此，ISFC算法降低示例標簽歧義性的能力更強。

3.3.2 ISFC與完全隨機地選擇代表示例對比

選出的代表示例作為基分類器的訓練子集。對比實驗完全隨機地選擇代表示例（簡稱隨機方法），它與ISFC的唯一區(qū)別在于代表示例的選擇方法，其他過程和參數(shù)完全相同。隨機方法包中每個示例被選擇的概率是相等的，ISFC是基于計算得到的示例選擇概率Pij選擇示例。

如圖1展示了ISFC與隨機方法的成對性能比較，圖（a）是準確率，圖（b）是AUC，紅線表示函數(shù)y=x，橫軸表示隨機方法，縱軸表示ISFC。如果一顆綠星位于紅線的左上方，則表明ISFC在相應的數(shù)據(jù)集上表現(xiàn)更好。圖（a）上，綠星均位于紅線的左上方，表明在所有實驗數(shù)據(jù)集上，ISFC的準確率均高于隨機方法。大部分綠星與紅線的距離較遠，表明在大多數(shù)實驗數(shù)據(jù)集上，ISFC具有明顯優(yōu)勢，如在Musk1、Elephant、Chains、East-West和N.g.11上，分別高出隨機方法2.25%、5.05%、18.57%、12.23%、28.6%；圖（b）上，大部分的綠星位于紅線上方，表明在大部分數(shù)據(jù)集上，ISFC的AUC高于隨機方法，如在Musk1、Elephant、EastWest、N.g.2、N.g.11和N.g.18上，分別高出隨機方法4.1%、5.57%、5%、13.16%、16.24%、4.84%，優(yōu)勢也較為明顯。因此，本文提出的代表示例選擇策略是有效的。

圖1 ISFC與隨機方法的成對性能比較Fig.1 Pairwise performance comparison between ISFC and random methods

與隨機方法相比，ISFC的優(yōu)勢源于兩方面：首先，ISFC通過正得分評估了包中每個示例為正例的可能性，認為每個示例為正類的可能性是不同的；而隨機方法認為包中每個示例為正類的可能性是相同的，ISFC是更合理的，正得分盡可能地保證選出有用的示例，降低從正包中選出負示例的概率。其次，ISFC的代表示例選擇策略考慮到將負包中負示例分類錯誤的代價更大，而隨機方法沒有考慮到該問題，ISFC規(guī)定：正包和負包中，都是正得分越高的示例，被選擇的概率越大，這樣迫使分類器的決策邊界偏向正類，盡可能地避免將負示例預測錯誤，從而提升包標簽預測的準確率。

3.3.3 ISFC與單分類器對比

對比實驗單分類器與ISFC的唯一區(qū)別在于集成規(guī)模M的不同，單分類器中設(shè)置M=1，其他過程和實驗設(shè)置與ISFC完全相同。

如圖2展示了ISFC與單分類器的成對性能比較，所有的綠星都位于紅線的左上方，這表明在所有的實驗數(shù)據(jù)集上，ISFC的準確率和AUC都高于單分類器。在不同的數(shù)據(jù)集上，ISFC中的集成規(guī)模M是不同的，但都不同程度地提高了分類器的性能，如在Musk2、Fox、Chains、N.g.1、N.g.13數(shù)據(jù)集上的準確率分別高出單分類器6.34%、7.6%、4.42%、14.3%、19.6%；在Elephant、Fox、N.g.1、N.g.10、N.g.13數(shù)據(jù)集上的AUC分別高出單分類器10.35%、12.01%、17.02%、14.04%、36.76%。這表明各個基分類器是有效的，且它們之間具有差異性，集成設(shè)計是成功的。

圖2 ISFC與單分類器的成對性能比較Fig.2 Pairwise performance comparison between ISFC and single classifiers

3.3.4 方差貢獻率的有效性驗證

為驗證ISFC算法中特征方差貢獻率度量的有效性，本文在14個數(shù)據(jù)集上進行了一組ISFC與子空間是完全隨機生成的對比實驗（簡稱隨機方法2），即每個特征被選為子空間特征的概率是相等的。實驗結(jié)果見表8，ISFC在所有數(shù)據(jù)集上的準確率和F分數(shù)都高于隨機方法2，在除Musk2、Tiger和Atoms外的其他11個數(shù)據(jù)集上，ISFC的AUC均高于隨機方法2，特別地，在Musk1、EastWest、N.g.2、N.g.6、N.g.11、N.g.18數(shù)據(jù)集上，ISFC的優(yōu)勢較為明顯，準確率分別高出2.23%、7.78%、27.90%、10.20%、10.00%、22.30%，AUC分別高出3.55%、9.72%、21.54%、8.62%、4.98%、28.04%，F(xiàn)分數(shù)分別高出2.11%、3.70%、14.09%、5.94%、7.37%、4.35%，因此方差貢獻率度量是有效的。

表8 ISFC與隨機方法2的實驗結(jié)果Table 8 Experimental results of ISFC and random method2%

3.3.5 參數(shù)敏感性分析

本文在5個數(shù)據(jù)集上研究了參數(shù)變化對分類性能的影響，ISFC算法共涉及5個參數(shù)，生成子空間的數(shù)量R、子空間選取的特征比例β、聚類時簇的數(shù)量K、正分數(shù)轉(zhuǎn)換為示例選擇概率時的溫度τ、集成規(guī)模M。

從圖3（a）可以看出，在所研究的數(shù)據(jù)集上，當集成規(guī)模M＞10時，準確率的波動范圍是0.45%到1.8%，標準差在0.17%到0.5%之間，因此它對ISFC算法的性能沒有顯著影響，可以粗略調(diào)節(jié)。集成規(guī)模不敏感的原因是隨著集成規(guī)模的增加，訓練程度逐漸加深，分類器需要學習的模式已經(jīng)基本學到，此時再繼續(xù)增加集成規(guī)模，模型的表達能力不會大幅提升了。本文的集成設(shè)計是Bagging的一種變體，是并行式集成，該表現(xiàn)與Bagging和隨機森林類似，起始性能通常不佳，特別是集成中只包含一個基分類器時，但隨著基分類器數(shù)目的增加，它們的泛化誤差會收斂到一個更低的值，性能趨于穩(wěn)定。

從圖3（b）可以看出，子空間的數(shù)量R＞100時，準確率的波動范圍是0.6%到1.33%，標準差在0.17%到0.43%之間，因此該參數(shù)對ISFC算法的性能影響不大，可以粗略調(diào)節(jié)，其不敏感的原因與集成規(guī)模相同，當學習達到一定程度，性能趨于穩(wěn)定，繼續(xù)增加規(guī)模，性能不會顯著提升。

從圖3（c）可以看出，F(xiàn)CM聚類中簇的數(shù)量K是一個比較敏感的參數(shù)，在不同的數(shù)據(jù)集上，性能的變化沒有一致的趨勢，這是因為最佳簇的數(shù)量K與數(shù)據(jù)集本身有關(guān)，數(shù)據(jù)實際的分組情況是未知的，因此，該參數(shù)需要仔細調(diào)節(jié)。

圖3 ISFC在5個數(shù)據(jù)集上不同參數(shù)的準確性Fig.3 ISFC’s accuracy of different parameters on 5 datasets

從圖3（d）可以看出，溫度τ是一個非常敏感的參數(shù)，當它在{0.001，0.01，0.1，1，10}范圍內(nèi)變化時，準確率的波動范圍是1.4%到12.8%，標準差在0.5%到4.5%之間。如2.4節(jié)所述，如果溫度τ較低，則每次從包中選出的代表示例都是相同的，各基分類器的訓練子集非常相似，降低了基分類器之間的多樣性；如果溫度τ較高，那么每個示例被選擇的概率幾乎是相同的，與3.3.2小節(jié)中的對比實驗隨機方法非常接近，增加了從正包中選出負示例的風險，削弱了正得分的作用。該參數(shù)與正包中正示例的比例有關(guān)，而正包中正示例的比例是未知的，所以需要仔細調(diào)節(jié)。

從圖3（e）可以看出，生成子空間時所選特征的比例β在Tiger數(shù)據(jù)集上，對性能幾乎沒有影響；在N.g.2數(shù)據(jù)集上，有顯著影響；在其他3個實驗數(shù)據(jù)集上，有輕微影響?？傮w來看，隨著所選特征比例β的增加，準確率逐漸降低，原因是當所選特征比例過高時，會降低隨機子空間之間的多樣性，進而影響聚類的結(jié)果和正得分。實驗結(jié)果表明，β不宜過大，通常小于0.4時，效果較好。

3.3.6 隨機性分析

ISFC算法中有兩個隨機過程：隨機子空間的特征是基于特征的方差貢獻率隨機生成的，各基分類器的訓練數(shù)據(jù)是基于示例選擇概率隨機選擇的，因此本小節(jié)研究隨機性對ISFC算法性能的影響。

從理論上分析，一方面，子空間是基于特征的方差貢獻率生成的，包含信息量越多的特征，被選擇的概率越大，包含信息量越小的特征，被選擇的概率越小，這保證了各個子空間的有效性；另一方面，各基分類器的訓練數(shù)據(jù)是基于示例選擇概率隨機選擇的，示例選擇概率是由正得分轉(zhuǎn)換而來的，代表示例選擇策略規(guī)定：在正包和負包中，都是正得分越高的示例，被選擇的概率越大，包中每個示例被選擇的概率是不同的。一方面，從正包的角度來看，該選擇策略盡量避免了從正包中選出負示例，進而避免訓練出的示例級分類器預測出假正例；另一方面，從負包的角度來看，使得示例級分類器的決策邊界移向正類，增加了真負例的數(shù)量。因此，包的分類效果得到了保證，隨機性對分類器性能的影響不會很大。

從實驗上，本文在Musk1、Elephant、EastWest、Bonds、N.g.10和N.g.11數(shù)據(jù)集上進行實驗。在一個數(shù)據(jù)集上，用相同的實驗設(shè)置（交叉驗證的劃分和參數(shù)）重復實驗100次，然后計算100次實驗結(jié)果的標準差，實驗結(jié)果見表9，在Musk1、Elepahnt、Bonds、N.g.10、N.g.11數(shù)據(jù)集上，準確率的標準差分別為0.42%、0.32%、0.17%、0.79%、0.38%，AUC的標準差分別為0.43%、0.32%、0.19%、0.86%、0.38%，均較小，因此，隨機性對分類器性能的影響不大。

表9 100次重復實驗性能的標準差Table 9 Standard deviation of performance for 100 repetitions %

3.3.7 時間復雜度分析

ISFC的訓練階段包括兩個部分：計算正得分和訓練集成分類器。在正得分的計算階段，對所有訓練示例進行FCM聚類，需要計算訓練示例和簇中心的距離，F(xiàn)CM聚類的時間復雜度是O(nr KlR)，其中n為示例的數(shù)量，r為數(shù)據(jù)的維數(shù)，K為簇的個數(shù)，l為迭代次數(shù)，R為子空間的數(shù)量。在訓練集成分類器時，從每個包中選出的代表示例作為SVM的訓練數(shù)據(jù)，時間復雜度為O(m2rM)，這表明包的數(shù)量m對訓練時間的影響，比示例的數(shù)量n影響更大。

4 結(jié)束語

本文提出了一個新的多示例學習集成算法ISFC，該算法對示例的分布和正包中的正示例比例不做任何假設(shè)，同時解決了正包數(shù)量多，負包數(shù)量少的類別不平衡問題。ISFC算法利用隨機子空間法和模糊聚類算法，定義了示例的正得分，消除了正包中示例標簽的歧義性；然后考慮到多示例學習中，將負示例分類錯誤的代價更大，基于正得分設(shè)計了包代表示例的選擇策略；最后，選出的代表示例作為基分類器的訓練子集，訓練集成分類器。

在今后的工作中，可以對包進一步研究，使得從包中選出示例的數(shù)量更加靈活。這樣做有兩點好處：第一，類別不平衡問題可以在數(shù)據(jù)層面上進一步解決；第二，隨著樣本量的增加，可以學習到更好的分類器。此外，正得分可以應用于一些多示例學習的迭代方法，如MILES、MILIS和MIRSVM，將每個包中正得分最高的示例作為初始代表示例，以減少迭代次數(shù)。