芮 辰，陳艷平

(1.合肥學(xué)院 實驗實訓(xùn)中心，安徽 合肥 230601；2.合肥學(xué)院 人工智能與大數(shù)據(jù)學(xué)院，安徽 合肥 230601)

多示例學(xué)習(xí)樣本由示例所組成的集合所構(gòu)成。Dietterich等人在通過機器學(xué)習(xí)方法研究麝香分子是否具有活性時發(fā)現(xiàn)[1]，分子具有多種形狀，我們只知道分子是否具有活性，無法得知哪一種形狀能夠讓該分子具有活性。傳統(tǒng)監(jiān)督學(xué)習(xí)中樣本和樣本類別一一對應(yīng)，而多示例學(xué)習(xí)中的樣本和包的類別是多對一的關(guān)系(如圖1所示)，人工篩選具有活性的麝香分子是一件非常耗時耗力的工作。由于具有活性的分子(正包)中包含大量噪聲(假正例)，監(jiān)督學(xué)習(xí)算法直接應(yīng)用于多示例問題時難以取得令人滿意的分類精度。多示例問題的發(fā)現(xiàn)拓展了傳統(tǒng)機器學(xué)習(xí)的研究領(lǐng)域，被認(rèn)為是一種新的機器學(xué)習(xí)框架。事實上，除藥物活性預(yù)測問題外，很多現(xiàn)實中的問題都屬于多示例問題的范疇。目前，多示例學(xué)習(xí)已被廣泛應(yīng)用于基于內(nèi)容的圖像檢索[2-3]，計算機輔助診斷[4-5]，計算機視覺等領(lǐng)域[6-7]。

圖1 多示例學(xué)習(xí)問題描述

在機器學(xué)習(xí)領(lǐng)域，在數(shù)據(jù)集不完整、數(shù)據(jù)集自身的標(biāo)記不完整或樣本從屬于某種類別的規(guī)則不明確時監(jiān)督學(xué)習(xí)算法的分類效果可能會受影響。聚類作為一類無監(jiān)督的機器學(xué)習(xí)算法，可以通過度量樣本之間的相似程度，將數(shù)據(jù)集劃分為多個不相交的、內(nèi)部具有高度相似性的聚簇(Cluster)，在數(shù)據(jù)的類別不明確或不完整的情況下，揭示樣本的分布規(guī)律。但多示例包中的大量假正例對聚類效果影響很大，將常規(guī)聚類算法直接應(yīng)用于多示例問題時，無法取得理想的分類精度。

本文設(shè)計了一種無監(jiān)督的多示例學(xué)習(xí)聚類算法，即MIFK-means。該方法首先通過Fisher編碼對多示例數(shù)據(jù)在實現(xiàn)歸一化的同時保留數(shù)據(jù)集原有的關(guān)鍵信息，有效降低多示例數(shù)據(jù)的學(xué)習(xí)復(fù)雜度。然后對轉(zhuǎn)換后的多示例數(shù)據(jù)集構(gòu)建聚類模型，擬合多示例數(shù)據(jù)的真實分布情況。實驗結(jié)果證明了該算法的有效性。

1 相關(guān)工作

近年來，為解決多示例問題，國內(nèi)外學(xué)者提出了兩類多示例學(xué)習(xí)算法。一類是針對多示例學(xué)習(xí)的特點量身定制的算法，如Dietterich等人提出了三種軸平行矩形APR算法[1]，能夠在數(shù)據(jù)集中用超矩形找到多示例數(shù)據(jù)每一維的上界和下界，從而找到真正例的集合。Maron設(shè)計了學(xué)習(xí)的Diverse Density(DD)算法，該方法可以在多示例數(shù)據(jù)集的示例空間內(nèi)通過梯度下降過程找到一個在概率上最可能是正示例的點。Zhang Qi和Goldman對DD算法進行了改進，提出基于期望最大化算法的DD算法，即EM-DD[8]。Zhang和Zhou通過關(guān)鍵示例的轉(zhuǎn)移提出了一種嵌入式的多示例算法MIKI[9]。另一類是對傳統(tǒng)的機器學(xué)習(xí)算法進行改進，使之適用于多示例問題。如Liu等人設(shè)計了一個多示例學(xué)習(xí)的卷積神經(jīng)網(wǎng)絡(luò)算法并將其應(yīng)用于多鏡頭人物識別中[10]。Gabriella Melki等人提出了多示例學(xué)習(xí)的包層次SVM算法MIRSVM[11]。Wang和Zucker首次通過懶惰學(xué)習(xí)方式，提出了基于概率的Bayesian-kNN算法和基于引證的Citation-kNN算法。Chevaleyre和Zucker提出了多示例學(xué)習(xí)的決策樹方法RIPPER-MI。J.Ramon和L.Ramon等人提出了多示例學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)框架。Zhang和Zhou設(shè)計了多示例學(xué)習(xí)的BP神經(jīng)網(wǎng)絡(luò)算法。Chen等人將多示例學(xué)習(xí)問題轉(zhuǎn)換為傳統(tǒng)的有監(jiān)督學(xué)習(xí)問題，提出了一種通過嵌入式示例選擇的多示例學(xué)習(xí)算法MILES[8]。謝紅薇和李曉亮提出了多示例學(xué)習(xí)的包層次K-means聚類算法MI_K-means[12]，該算法通過混合Hausdorff距離度量包之間的相似程度。

盡管以上算法在多示例數(shù)據(jù)的分類中取得了很高的精度，但卻未能揭示多示例數(shù)據(jù)真實的分布情況。聚類作為人工智能和數(shù)據(jù)挖掘領(lǐng)域的一種重要方法，可以通過無監(jiān)督方法揭示數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)和分布規(guī)律。但包層次的多示例聚類算法無法避免正包中大量的反示例對聚類的影響。本文提出的MIFK-means算法首先通過Fisher編碼對多示例數(shù)據(jù)集進行歸一化重新表示，再通過聚類擬合多示例數(shù)據(jù)真實的分布情況。在基準(zhǔn)數(shù)據(jù)集上的實驗結(jié)果表明，MIFK-means算法的分類精度可以與現(xiàn)有的經(jīng)典多示例學(xué)習(xí)算法相媲美，可以高效、精準(zhǔn)地對多示例數(shù)據(jù)進行聚類。

本文的其余部分安排如下。第二節(jié)介紹MIFK-means算法的詳細(xì)細(xì)節(jié)。第三節(jié)通過實驗驗證聚類效果和算法的有效性。最后，在第四節(jié)進行總結(jié)并展了未來的工作方向。

2 結(jié)合Fisher編碼的多示例聚類算法

2.1 問題描述

給定多示例數(shù)據(jù)集X={(Bi,label)|i=1,2,...,N}，其中Bi表示多示例數(shù)據(jù)包，label為數(shù)據(jù)包的類別，label={+1,-1}。令B+={bi|i=1,2,...,p}表示一個正包，B-={bj|i=1,2,...,n}表示一個反包。數(shù)據(jù)的維度為D，d表示多示例樣本的第d個維度。多示例問題是二分類問題，學(xué)習(xí)任務(wù)是正確預(yù)測包的類別為+1還是-1。

2.2 MIFK-means算法

基于內(nèi)容的圖像檢索(CBIR)是多示例學(xué)習(xí)的典型應(yīng)用之一。如圖2所示，在CBIR領(lǐng)域中，用戶感興趣的內(nèi)容可能僅僅是圖片中的一小部分(如圖2中的馬)，這部分興趣點可以理解為多示例正包中的真正例，如果一幅圖片中不包含任何用戶感興趣的內(nèi)容(不包含馬)，那么可以將整幅圖片理解為一個多示例反包。Fisher編碼是模式識別中用少量特征來描述圖像，從圖像中提取語義的一種編碼技術(shù)[13-14]。該方法通過對高斯分布的參數(shù)求偏導(dǎo)，再對結(jié)果進行歸一化處理從圖片中挖掘和擬合圖片特征?？梢允褂肍isher編碼在對多示例數(shù)據(jù)進行歸一化的同時，保留多示例數(shù)據(jù)包的原始語義。MIFK-means算法分兩步執(zhí)行：歸一化過程和聚類過程。算法的具體執(zhí)行步驟如下。

圖2 圖像具有多樣性的例子

2.2.1 歸一化過程

1)設(shè)λ為數(shù)據(jù)模型p(x;λ),x∈X,λ∈RD的參數(shù)，通過對數(shù)似然函數(shù)的梯度G(x)=?λlogp(x|λ)表征數(shù)據(jù)，該梯度描述了如何通過參數(shù)λ更好的擬合數(shù)據(jù)。

2)通過獲取Fisher向量之間的縮放內(nèi)積來定義數(shù)據(jù)的Fisher核函數(shù)k(x1,x2)=φ(x1)Tφ(x2)。其中，φ(x)=F-1/2?λlogp(x)，F(xiàn)為Fisher信息矩陣F=Ep(x)[G(x)G(x)T]。

3)通過K個高斯分布的線性組合模型來擬合多示例數(shù)據(jù)。將其組成的高斯混合模型參數(shù)定義為λ={wk,μk,∑k,k=1,2,...,K}，其中wk，μk，∑k分別是高斯混合分布模型的權(quán)重，均值和協(xié)方差矩陣。

2.2.2 聚類過程

影響K-means算法聚類效果的關(guān)鍵是初始聚類中心的選擇和數(shù)據(jù)相似度的度量方式。MI_K-means算法運行在包層次，聚類時從多示例數(shù)據(jù)包中通過隨機抽樣法確定初始聚類中心。但由于多示例包中的示例數(shù)各不相同，正包中含有大量假正例，每個多示例包在整個數(shù)據(jù)集中的權(quán)重事實上是不同的，因此隨機選取初始化聚類中心在一定程度上限值了MI_K-means算法的聚類效果和分類精度。此外，運行在包層次的MI_K-means算法使用Hausdorff距離度量多示例包之間的相似度，最大Hausdorff距離在聚類時受多示例包中離群示例的影響很大，最小Hausdorff距離只考慮了兩個多示例包中相似度最大的兩個示例，混合Hausdorff距離作為折中雖然能夠在一定限度上彌補最大和最小Hausdorff距離的弊端，但由于正包內(nèi)大量假正例的存在，始終無法避免多示例包中噪聲對包之間真實相似度的影響[12]。

本文提出的MIFK-means算法通過Fisher編碼，能夠在保留各個多示例包語義的前提下，通過高斯混合分布擬合示例數(shù)各不相同的多示例包，將多示例包歸一化為一個個維度相同的Fisher向量，從而將多示例問題轉(zhuǎn)化為了傳統(tǒng)的機器學(xué)習(xí)問題。MIFK-means算法運行在示例層，隨機初始化聚類中心點時，能夠不受各個多示例包權(quán)重的限值，數(shù)據(jù)相似度的度量方式也不必使用Hausdorff距離，而是使用傳統(tǒng)機器學(xué)習(xí)中更準(zhǔn)確的示例層次的相似度度量函數(shù)。從而可以進一步提升聚類效果，擬合多示例數(shù)據(jù)集。

給定經(jīng)過Fisher編碼歸一化后的多示例數(shù)據(jù)集X={x1,x2,...,xn}，聚類算法的執(zhí)行流程如下。

1)從X中隨機選取k個樣本初始化聚類中心μ={μ1,μ2,...,μk}

2)repeat

3)根據(jù)聚類中心μ={μ1,μ2,...,μk}確定各個樣本從屬的聚類

4)fori=1,2,...,n

5)計算樣本xi和各個聚類中心μj的相似度：dij=f(xi,μj)

6)將樣本xi分配到距離最近的那個聚類：Ck=Ck∪{xi}

7)end

8)forj=1,2,...,k

10)end

11)until 達(dá)到算法的收斂條件，即所有聚類中心μ={μ1,μ2,...,μk}不再改變

3 實驗結(jié)果與分析

本節(jié)介紹實驗數(shù)據(jù)集，評價聚類效果并分析實驗結(jié)果。實驗設(shè)備的主要性能參數(shù)為Intel i5-3570 CPU @ 3.40GHz * 4 CPUs，8 GB內(nèi)存。

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

麝香分子數(shù)據(jù)集是至今唯一的真實多示例數(shù)據(jù)集。分類任務(wù)是預(yù)測Musk1和Musk2兩個子集中的麝香分子是否具有活性。該數(shù)據(jù)集可以從UCI機器學(xué)習(xí)數(shù)據(jù)集倉庫中免費獲?、?。數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 數(shù)據(jù)集的詳細(xì)信息

3.2 實驗結(jié)果和分析

3.2.1 聚類效果對比

由于所有多示例數(shù)據(jù)在包層次都具有明確的類別，因此可以采用Rand Index指標(biāo)衡量通過聚類后正確決策的比例。定義TP和TN分別表示真正例和真反例數(shù)目，F(xiàn)P和FN分別表示假正例和假反例數(shù)目。則可以通過Rand Index測度(公示7)度量算法的劃分結(jié)果和人工劃分結(jié)果的耦合程度。

(7)

對于Musk1和Musk2數(shù)據(jù)集，將聚類數(shù)分別設(shè)置為10，20，30，40和50進行聚類效果實驗。圖3對比了MIFK-means算法和MI_K-means算法作用于麝香分子數(shù)據(jù)集時的聚類效果。

圖3 MI_K-means和MIFK-means算法在Musk數(shù)據(jù)集上的聚類效果對比

實驗結(jié)果表明， MIFK-means算法能夠在一定程度上避免MI_K-means聚類算法運行時包中示例權(quán)重的不同對聚類效果的影響，聚類效果優(yōu)于MI_K-means算法。

3.2.2 分類精度對比

盡管所有多示例包都有明確的標(biāo)記，但是正包中示例的標(biāo)記卻是未知的。包層次多示例分類算法難以避免正包中的反示例對分類精度的影響。而MIFK-means算法通過Fisher編碼在保留多示例包中語義的前提下將多示例分類問題轉(zhuǎn)化為了傳統(tǒng)的監(jiān)督學(xué)習(xí)分類問題，從而在一定程度上降低了正包中的噪聲對分類精度的影響。表2比較了MIFK-means算法和一些經(jīng)典多示例算法的分類精度。通過10折交叉驗證法進行實驗。每次實驗中，將多示例數(shù)據(jù)集平均分為10份，其中9份用作訓(xùn)練集，余下的1份用作測試集，10份樣本輪流作為測試集。MIFK-means算法重復(fù)執(zhí)行10次，取10次分類的平均值為10折倍交叉驗證的最終的分類精度，詳細(xì)的實驗結(jié)果列在表2中。實驗結(jié)果表明，MIFK-means算法的分類精度優(yōu)于MI_K-means算法，并且可以和現(xiàn)有的經(jīng)典多示例算法相媲美。

表2 算法分類精度的比較

4 結(jié)語

正包中大量的假正例掩蓋了多示例數(shù)據(jù)之間真實的相似性，為了排除假正例的干擾，MIFK-means算法首先通過Fisher矩陣在保留多示例數(shù)據(jù)包原有語義的前提下對多示例包進行歸一化，然后通過示例層次的K-means算法構(gòu)建多示例數(shù)據(jù)的聚類模型。實驗表明，該策略能夠有效提高多示例樣本的聚類效果。在未來的工作中，我們將進一步探索如何將MIFK-means算法應(yīng)用于大規(guī)模的多示例數(shù)據(jù)集，以及如何將該算法應(yīng)用于多示例學(xué)習(xí)的實際應(yīng)用場景中。

注釋：

① http://archive.ics.uci.edu/ml/machine-learning-databases/musk/.