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

芮 辰，陳艷平

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2.1 問(wèn)題描述

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

2.2 MIFK-means算法

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

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

2.2.1 歸一化過(guò)程

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

2)通過(guò)獲取Fisher向量之間的縮放內(nèi)積來(lá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)通過(guò)K個(gè)高斯分布的線性組合模型來(lái)擬合多示例數(shù)據(jù)。將其組成的高斯混合模型參數(shù)定義為λ={wk,μk,∑k,k=1,2,...,K}，其中wk，μk，∑k分別是高斯混合分布模型的權(quán)重，均值和協(xié)方差矩陣。

2.2.2 聚類過(guò)程

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

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

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

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

2)repeat

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

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

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

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

7)end

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

10)end

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

3.2 實(shí)驗(yàn)結(jié)果和分析

3.2.1 聚類效果對(duì)比

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

(7)

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

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

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

3.2.2 分類精度對(duì)比

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

表2 算法分類精度的比較

4 結(jié)語(yǔ)

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

注釋：

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