韓海韻，楊有龍，孫麗芹

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

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

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

目前許多多示例方法都對(duì)數(shù)據(jù)隱式地做出了假設(shè)：（1）正包中正示例的比例；（2）示例的分布。APR算法學(xué)習(xí)一個(gè)超矩形區(qū)域，正包中至少有一個(gè)示例在該超矩形內(nèi)，負(fù)包中所有示例都不在該矩形內(nèi)；DD算法學(xué)習(xí)一個(gè)概念點(diǎn)，正包中至少有一個(gè)示例離該點(diǎn)很近，負(fù)包中所有示例都遠(yuǎn)離該點(diǎn)，APR和DD都對(duì)正示例的分布做出了隱含假設(shè)：正示例來(lái)自一個(gè)緊湊的簇。因此，它們只在單模態(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]估計(jì)了正包中正示例的比例，假設(shè)正包中正示例的比例在所有包中都是相同的，是一個(gè)定值。MILIS要對(duì)負(fù)示例做高斯核密度估計(jì)，當(dāng)數(shù)據(jù)量較小時(shí)，估計(jì)是不準(zhǔn)確的。

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

1 相關(guān)知識(shí)

1.1 隨機(jī)子空間法

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

1.2 模糊C-均值聚類(lèi)

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

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

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

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

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

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

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

2.1 符號(hào)說(shuō)明

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

2.2 基于方差貢獻(xiàn)率的隨機(jī)子空間

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

子空間生成方法如下：

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

步驟2計(jì)算協(xié)方差矩陣的特征值λi以及對(duì)應(yīng)的特征向量，一個(gè)特征向量對(duì)應(yīng)一個(gè)新的特征方向，特征值用來(lái)描述對(duì)應(yīng)特征方向包含的信息量。

步驟3計(jì)算第i個(gè)新特征的方差貢獻(xiàn)率：

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

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

一方面，該子空間的生成方法是高效的，因?yàn)樘卣髦匾缘脑u(píng)估，不需要花費(fèi)額外的計(jì)算開(kāi)銷(xiāo)，而是重復(fù)利用了PCA時(shí)得到的方差貢獻(xiàn)率；另一方面，生成的子空間是有效的，因?yàn)樽涌臻g是基于特征選擇概率cr，而不是等概率生成的，包含信息越多的特征，越重要的特征，被選擇的可能性越大。因此，與完全隨機(jī)子空間相比，基于方差貢獻(xiàn)率生成的子空間刻畫(huà)數(shù)據(jù)的能力更強(qiáng)、更準(zhǔn)確，各子空間之間也具有差異性，在其內(nèi)訓(xùn)練學(xué)習(xí)器，效果可以得到保證。該子空間生成方法的偽代碼見(jiàn)算法1。

算法1基于方差貢獻(xiàn)率的隨機(jī)子空間

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

輸出：生成的隨機(jī)子空間H

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

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

5.forr=1,2,…,ddo

7.end

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

9.用式（3）計(jì)算r個(gè)新特征的方差貢獻(xiàn)cr=(cr1,cr2,…,cr r)

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

2.3 示例的正得分

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

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

正得分的計(jì)算方法如下：

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

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

步驟3計(jì)算每個(gè)子空間的每個(gè)簇中，示例來(lái)自正包的比例。

對(duì)于子空間Ht中的第n個(gè)簇，示例來(lái)自正包的比例是：

其中：

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

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

步驟4計(jì)算示例x ij的正得分S ij：

其中：

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

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

算法2正得分的計(jì)算

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

輸出：正得分S ij

1.fort=1,2,…,Rdo

2.用算法1生成子空間H t，然后將訓(xùn)練包中的示例在子空間Ht上投影，投影后，用FCM算法對(duì)示例進(jìn)行聚類(lèi)

3. forx ij∈Ddo

4.forn=1,2,…,Kdo

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

6.end

7.end

8.end

9.forxij∈Ddo

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

11.end

2.4 包代表示例的選擇策略

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

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

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

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

2.5 集成設(shè)計(jì)

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

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

2.6 包標(biāo)簽的預(yù)測(cè)

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

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

最后，將包Bi的決策值與0進(jìn)行比較，確定包Bi的標(biāo)簽L i。

2.7 算法步驟

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

步驟1（生成子空間）基于特征的方差貢獻(xiàn)率，生成多個(gè)隨機(jī)子空間。

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

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

步驟4（抽取訓(xùn)練子集）基于示例選擇概率，從每個(gè)包中隨機(jī)選出代表示例，作為基分類(lèi)器的訓(xùn)練子集，代表示例的標(biāo)簽是其所屬包的標(biāo)簽。

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

ISFC算法的完整偽代碼見(jiàn)算法3。

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

訓(xùn)練階段

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

輸出：集成分類(lèi)器C

1.用算法2計(jì)算每個(gè)示例xij的正得分Sij

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

3.C=?

4.fork=1,2,…,Mdo

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

6.C=C?Ck

7.end

測(cè)試階段

輸入：未標(biāo)記的測(cè)試包B u，集成分類(lèi)器C

輸出：預(yù)測(cè)的標(biāo)記L u

1.fork=1,2,…,Mdo

2.forxij∈Budo

3.用基分類(lèi)器Ck預(yù)測(cè)示例xij的標(biāo)簽y ij,k，然后用式（9）計(jì)算示例xij的決策值y ij

4.end

5.end

6.Lu=?

7.forB i∈Budo

8.用式（10）計(jì)算包B i的預(yù)測(cè)值yi，用式（11）確定包B i的標(biāo)簽L i

9.Lu=L u?L i

10.end

3 實(shí)驗(yàn)及分析

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental datasets

3.2 實(shí)驗(yàn)設(shè)置

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

對(duì)比算法為Citation-KNN、MILBoost[25]、Simple-MI、CCE、K-means-encoding（BoW）、RSIS和MILDM。選擇Citation-KNN，因?yàn)樗墙?jīng)典的包空間方法；選擇Simple-MI，因?yàn)樗僭O(shè)正包中全部都是正示例；選擇MILBoost，因?yàn)樗墙?jīng)典的多示例集成算法；選擇CCE和BoW，因?yàn)樗鼈兌际褂昧司垲?lèi)方法，此外，CCE也有SVM的集成過(guò)程；選擇RSIS，因?yàn)樗cISFC也降低了示例標(biāo)簽的歧義性，ISFC是其改進(jìn)算法；選擇MILDM，因?yàn)樗切阅芎芎玫那度肟臻g方法，優(yōu)于當(dāng)前大部分嵌入空間方法。

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

3.3.1 ISFC與其他多示例算法對(duì)比

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

表2 準(zhǔn)確率Table 2 Accuracy

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

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

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

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

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

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

表7報(bào)告了類(lèi)別不平衡問(wèn)題（Atoms、Bonds和Chains數(shù)據(jù)集）中，8個(gè)算法性能的平均排名?；跍?zhǔn)確率和AUC，ISFC均為第一，因?yàn)镮SFC在代表示例選擇過(guò)程中，從每個(gè)負(fù)包中選擇了兩個(gè)示例，在數(shù)據(jù)層面解決了類(lèi)別不平衡問(wèn)題，從而提高了分類(lèi)性能。

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

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

3.3.2 ISFC與完全隨機(jī)地選擇代表示例對(duì)比

選出的代表示例作為基分類(lèi)器的訓(xùn)練子集。對(duì)比實(shí)驗(yàn)完全隨機(jī)地選擇代表示例（簡(jiǎn)稱(chēng)隨機(jī)方法），它與ISFC的唯一區(qū)別在于代表示例的選擇方法，其他過(guò)程和參數(shù)完全相同。隨機(jī)方法包中每個(gè)示例被選擇的概率是相等的，ISFC是基于計(jì)算得到的示例選擇概率Pij選擇示例。

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

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

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

3.3.3 ISFC與單分類(lèi)器對(duì)比

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

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

圖2 ISFC與單分類(lèi)器的成對(duì)性能比較Fig.2 Pairwise performance comparison between ISFC and single classifiers

3.3.4 方差貢獻(xiàn)率的有效性驗(yàn)證

為驗(yàn)證ISFC算法中特征方差貢獻(xiàn)率度量的有效性，本文在14個(gè)數(shù)據(jù)集上進(jìn)行了一組ISFC與子空間是完全隨機(jī)生成的對(duì)比實(shí)驗(yàn)（簡(jiǎn)稱(chēng)隨機(jī)方法2），即每個(gè)特征被選為子空間特征的概率是相等的。實(shí)驗(yàn)結(jié)果見(jiàn)表8，ISFC在所有數(shù)據(jù)集上的準(zhǔn)確率和F分?jǐn)?shù)都高于隨機(jī)方法2，在除Musk2、Tiger和Atoms外的其他11個(gè)數(shù)據(jù)集上，ISFC的AUC均高于隨機(jī)方法2，特別地，在Musk1、EastWest、N.g.2、N.g.6、N.g.11、N.g.18數(shù)據(jù)集上，ISFC的優(yōu)勢(shì)較為明顯，準(zhǔn)確率分別高出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)分?jǐn)?shù)分別高出2.11%、3.70%、14.09%、5.94%、7.37%、4.35%，因此方差貢獻(xiàn)率度量是有效的。

表8 ISFC與隨機(jī)方法2的實(shí)驗(yàn)結(jié)果Table 8 Experimental results of ISFC and random method2%

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

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

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

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

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

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

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

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

3.3.6 隨機(jī)性分析

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

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

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

表9 100次重復(fù)實(shí)驗(yàn)性能的標(biāo)準(zhǔn)差Table 9 Standard deviation of performance for 100 repetitions %

3.3.7 時(shí)間復(fù)雜度分析

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

4 結(jié)束語(yǔ)

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

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