基于局部加權(quán)的Citation-kNN算法

黃劍華 丁建睿 劉家鋒 張英濤

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)

1 引言

1997年，Dietterich等人[1]在對(duì)藥物活性預(yù)測(cè)問題的研究中，提出了多示例學(xué)習(xí)(Multi-Instance Learning, MIL)的概念。在傳統(tǒng)學(xué)習(xí)框架中，一個(gè)樣本代表一個(gè)示例，即樣本和示例是一一對(duì)應(yīng)的關(guān)系，同時(shí)示例的標(biāo)簽全部已知或者全部未知；而在多示例學(xué)習(xí)中，一個(gè)樣本被定義為一個(gè)包，其中包含了多個(gè)示例，即樣本和示例是一對(duì)多的對(duì)應(yīng)關(guān)系，同時(shí)樣本(包)的標(biāo)簽已知但是示例的標(biāo)簽未知。所以多示例學(xué)習(xí)中的訓(xùn)練樣本的歧義性與傳統(tǒng)學(xué)習(xí)中樣本的歧義性完全不同，這使得傳統(tǒng)學(xué)習(xí)方法難以解決多示例問題[2]。

文獻(xiàn)[1]提出了APR(Axis-Parallel Rectangle)學(xué)習(xí)算法來解決多示例藥物活性預(yù)測(cè)問題；Maron等人[3]提出了多樣性密度(Diverse Density, DD)算法；Wang等人[4]提出了Bayesian-kNN 和 Citation-kNN兩種算法；Zhang等人[5]將 DD 算法與 EM算法相結(jié)合提出了 EM-DD算法；Andrews 等人[6]對(duì)支持向量機(jī)進(jìn)行了擴(kuò)展，得到了多示例算法Bag-SVM和Inst-SVM。

在多示例學(xué)習(xí)概念和算法提出以后，已經(jīng)在多個(gè)領(lǐng)域得到了成功應(yīng)用，如：藥物預(yù)測(cè)[1]；圖像分類、標(biāo)注[7]、圖像分割[8]；視頻中人的識(shí)別[9]，股票選擇[10]；索引網(wǎng)頁推薦[11]；顯微鏡下的肺癌細(xì)胞圖像識(shí)別[12]等。

Citation-kNN算法通過結(jié)合惰性學(xué)習(xí)(lazy learning)和 Hausdorff距離，對(duì) k-近鄰算法進(jìn)行了擴(kuò)展，使其能夠處理多示例學(xué)習(xí)問題，并在標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集MUSK上取得了良好的結(jié)果。但其所采用的 0-1投票決策方式在實(shí)際應(yīng)用中存在著一定的缺陷。因?yàn)樵趯?shí)際分類系統(tǒng)中樣本庫(kù)并不是分布在連續(xù)的空間中，并且樣本也并不能均勻分布在包空間的任何一個(gè)角落，所以實(shí)際樣本庫(kù)缺乏足夠的樣本來表示完整的包空間。在這種不完全庫(kù)所能表達(dá)的特征空間中，樣本分布會(huì)表現(xiàn)出密集與稀疏，散亂與聚集等特征，同時(shí)樣本也可能在一個(gè)聚集的中心位置或不同聚集的交界處，而Citation-kNN的決策方式無法很好地解決這些特殊情況。

本文針對(duì) Citation-kNN算法的不足進(jìn)行了改進(jìn)，提出了基于局部加權(quán)的 Citation-kNN算法(Locally Weighted Citation-kNN, LWCitationkNN)。實(shí)驗(yàn)證明，該方法在標(biāo)準(zhǔn)庫(kù)MUSK1上的分類效果較Citation-kNN算法有明顯提高，同時(shí)，該方法在超聲乳腺腫瘤良惡性分類問題中也得到了很好的效果。

2 局部加權(quán)的 Citation-kNN(LW.CitationkNN)算法

本文提出的局部加權(quán)的 Citation-kNN算法(LWCitation-kNN)主要針對(duì) Citation-kNN 算法中決策部分的不足進(jìn)行了改進(jìn)，將包特征空間的分布形式進(jìn)行細(xì)分，得到兩種分布特征：距離分布和散亂分布。算法根據(jù)以上分布特征的具體情況設(shè)置相應(yīng)的權(quán)值和決策準(zhǔn)則。

LWCitation-kNN和Citation-kNN的算法流程如圖1所示。

圖1 LWCitation-kNN和Citation-kNN算法流程圖

不同于 Citation-kNN中的 0-1決策方式，在LWCitation-kNN中，根據(jù)樣本的分布情況，分別提出了基于距離權(quán)值、基于離散度權(quán)值以及綜合這兩種分布的決策方式。

2.1 基于距離權(quán)值的算法改進(jìn)

圖2是一種可能存在的包分布情況。

圖中中心位置的白色方塊為測(cè)試樣本，周圍的圓點(diǎn)為訓(xùn)練樣本，顏色代表其類別，數(shù)量分別為nb和nw。在圖中所示的分布情況中，nb/nw=1，若采用Citation-kNN的0-1投票方式，則很難確定測(cè)試樣本的類別。

基于距離加權(quán)的類別決策函數(shù)定義為

圖2 距離權(quán)值解決的情況

本文所采用的距離加權(quán)函數(shù)為

其中dmax和dmin分別為訓(xùn)練樣本到測(cè)試樣本的最大和最小距離，該距離可以細(xì)分為局部形式和全局形式，采用局部形式時(shí)，dmax和dmin為投票集合中的最大和最小距離；采用全局形式時(shí)，dmax和dmin為所有訓(xùn)練樣本到測(cè)試樣本的最大和最小距離。

2.2 基于離散度權(quán)值的算法改進(jìn)

離散度是用于描述特征空間中局部范圍內(nèi)的不同標(biāo)簽類別的樣本點(diǎn)相互摻雜程度，離散度反映了樣本局部范圍內(nèi)的可分程度。若在一個(gè)區(qū)域中心的樣本點(diǎn)的可分性很差，則說明這個(gè)區(qū)域的散亂程度高，同時(shí)這個(gè)區(qū)域的樣本點(diǎn)作為訓(xùn)練樣本(投票者)的投票可信度就小，即權(quán)值要小。

圖3是一種可能存在的包分布情況。

圖3中的測(cè)試樣本難以用Citation-kNN和基于距離權(quán)值的方法正確分類，但從離散度來看，上方白色訓(xùn)練樣本的離散度更低，其權(quán)值應(yīng)該更大，即測(cè)試樣本判為白色更加合理。

基于離散度加權(quán)的決策函數(shù)為

圖3 離散度權(quán)值所解決的情況

其中X為測(cè)試示例包，Ti為X投票集合中的訓(xùn)練示例包，其標(biāo)簽ci用+1或-1來表示，S(Ti)為訓(xùn)練示例包的離散度權(quán)值，其定義為

其中Ti為訓(xùn)練示例包，將Ti作為待測(cè)示例包，可以得到它的投票集合，Tk為Ti投票集合中的訓(xùn)練示例包，其標(biāo)簽ck用+1或-1來表示，W(·)為根據(jù)式(2)所得到的Ti投票集合中的訓(xùn)練示例包的距離加權(quán)值。

訓(xùn)練樣本中可能存在噪聲，在圖4所示的情況中，采用式(4)計(jì)算的離散度是相同的，但在圖4(b)中心的訓(xùn)練樣本修正為黑色更為合理。

圖4 訓(xùn)練樣本中存在噪聲的情況

為解決這類問題，可以采用帶有類別信息的離散度權(quán)值，對(duì)于不合理的訓(xùn)練樣本可以采用式(5)進(jìn)行修正：

2.3 綜合加權(quán)算法

綜合考慮上面兩種分布情況，將基于距離權(quán)值和基于離散度權(quán)值的方法相結(jié)合，得到基于綜合加權(quán)的Citation-kNN改進(jìn)算法，算法描述如表1所示。

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

本文的實(shí)驗(yàn)樣本庫(kù)分別采用標(biāo)準(zhǔn)數(shù)據(jù)集MUSK1和MUSK2和由哈爾濱醫(yī)科大學(xué)第二附屬醫(yī)院提供的乳腺超聲圖像庫(kù)。實(shí)驗(yàn)分為兩部分，第1部分是針對(duì)MUSK1和MUSK2標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，主要比較本文方法與標(biāo)準(zhǔn)Citation-kNN算法在該數(shù)據(jù)集上的分類效果；第2部分是針對(duì)超聲乳腺腫瘤圖像庫(kù)進(jìn)行實(shí)驗(yàn)，分別對(duì)比分析不同的加權(quán)方法下的分類效果，同時(shí)選擇適合于此類庫(kù)的最佳參數(shù)組合。

實(shí)驗(yàn)中采用交叉驗(yàn)證的方法，將數(shù)據(jù)集隨機(jī)分為10組，依次將其中1組作為測(cè)試樣本，其他9組作為訓(xùn)練樣本，在該訓(xùn)練樣本上選取參數(shù)cn,rn，并在測(cè)試樣本上進(jìn)行測(cè)試，最終結(jié)果取10次測(cè)試的平均值。實(shí)驗(yàn)采用準(zhǔn)確率(ACC)來評(píng)價(jià)不同算法在數(shù)據(jù)集上的分類性能，其中參數(shù)TP(True Positive)和FN(False Negative)是被正確和錯(cuò)誤判別的正例樣本數(shù)，而TN(True Negative)和FP(False Positive)是被正確以及錯(cuò)誤判別的反例樣本數(shù)，準(zhǔn)確率定義為式(6)：通過對(duì)前面局部加權(quán)方法進(jìn)行組合，可以得到8種加權(quán)方法，如表2所示。

3.1 MUSK庫(kù)的實(shí)驗(yàn)結(jié)果

MUSK庫(kù)包含MUSK1和MUSK2兩個(gè)分子構(gòu)造數(shù)據(jù)集，每個(gè)數(shù)據(jù)集中包含多個(gè)示例包，每個(gè)示例包包含多個(gè)示例，每個(gè)示例代表一種分子構(gòu)造方法，其特點(diǎn)如表3所示。

表2 加權(quán)方式的組合

表3 MUSK庫(kù)

實(shí)驗(yàn)中選擇reference集合大小取值范圍為2～10, citer集合大小取值范圍為0～10，在MUSK1和MUSK2上的實(shí)驗(yàn)結(jié)果如表4所示。

表4 MUSK1和MUSK2上的實(shí)驗(yàn)準(zhǔn)確率(%)

本文所采用的方法與其他多示例學(xué)習(xí)算法在MUSK1和MUSK2庫(kù)上的性能比較結(jié)果如表5所示。

表5 與其他算法的準(zhǔn)確率比較(%)

結(jié)果表明本文的權(quán)值設(shè)置方法在 MUSK庫(kù)上有較好的效果，在綜合加權(quán)方式下(W8)達(dá)到最佳性能。本文方法同樣具有較好的表現(xiàn)，準(zhǔn)確率要高于Bayesian-kNN和Diverse Density算法，但略低于iterated-discrim APR算法，由于該算法針對(duì)MUSK數(shù)據(jù)集進(jìn)行了優(yōu)化[13]，因此并不具有代表性；另外一個(gè)原因是 MUSK數(shù)據(jù)集符合多示例學(xué)習(xí)的標(biāo)準(zhǔn)定義，即：正例包中的正例數(shù)大于 1，負(fù)例包中所有示例均為負(fù)例，而Citation-kNN算法以及本文改進(jìn)的算法，屬于示例包級(jí)的算法，并沒有考慮包中示例的正負(fù)問題，因此針對(duì)MUSK數(shù)據(jù)集的性能提高不大。

3.2 超聲乳腺腫瘤良惡性分類實(shí)驗(yàn)

本文主要針對(duì)116幅乳腺超聲圖像(58例良性，58例惡性)進(jìn)行分類，用以驗(yàn)證本文方法的效果。這些乳腺超聲圖像來源于哈爾濱醫(yī)科大學(xué)第二附屬醫(yī)院的乳腺超聲圖像庫(kù)，圖像通過GE VIVID7超聲影像系統(tǒng)和5.6-14 MHz, 38 mm線性探頭采集。診斷結(jié)果均得到臨床手術(shù)證實(shí)。

在傳統(tǒng)超聲乳腺腫瘤分類系統(tǒng)中，每個(gè)圖像的特征信息需要在腫瘤感興趣區(qū)域(Region Of Interest, ROI)部分提取，為了避免非腫瘤ROI區(qū)域信息對(duì)最終分類的干擾，應(yīng)盡量提取出精準(zhǔn)的ROI區(qū)域，但是現(xiàn)有超聲腫瘤分割仍然是醫(yī)療圖像領(lǐng)域的一個(gè)難題，并沒有得到很好的解決[14]。同時(shí)在一些分類以及分割算法中，需要有醫(yī)生手動(dòng)提取的訓(xùn)練樣本作為系統(tǒng)的初始條件，手畫ROI邊界在訓(xùn)練樣本大量存在的時(shí)候是一項(xiàng)繁瑣的工作。為避免ROI區(qū)域的分割誤差對(duì)分類性能的影響，減輕醫(yī)生的工作負(fù)擔(dān)，本文將超聲圖像的分類問題轉(zhuǎn)為多示例學(xué)習(xí)問題來進(jìn)行處理。

將每幅超聲圖像劃分為等大小的子區(qū)域，每個(gè)子區(qū)域作為示例，整幅圖像作為示例包，提取每個(gè)子區(qū)域的紋理特征(灰度共生矩陣)[15]作為示例特征，如圖5所示。

區(qū)域大小反映了所提取特征的分辨率，區(qū)域越小，則特征分辨率越高，不同區(qū)域之間的特征差異越?。粎^(qū)域越大，則特征分辨率越低，極端情況下，當(dāng)區(qū)域大小為圖像大小時(shí)，則多示例學(xué)習(xí)問題被還原為傳統(tǒng)有監(jiān)督學(xué)習(xí)問題，在區(qū)域大小的選擇上，存在著既能夠反映圖像的局部特征，又能夠使得區(qū)域之間的可分性較好的一些劃分，對(duì)于不同的圖像和不同的樣本庫(kù)，該劃分不盡相同。

圖5 示例包的構(gòu)建

實(shí)驗(yàn)中選擇的子區(qū)域大小從 50×50～155×155(步長(zhǎng)為15)，reference集合大小取值范圍為2～10,citer集合大小取值范圍為0～10。表6中給出了對(duì)圖像進(jìn)行不同劃分時(shí)，采用不同加權(quán)方式時(shí)的分類準(zhǔn)確率與Citation-kNN, iterated-discrim APR方法準(zhǔn)確率的比較。

從實(shí)驗(yàn)結(jié)果來看，本文所采用的方法在不同的包構(gòu)建方式下要普遍高于Citation-kNN和iterateddiscrim APR的分類效果，在采用W8(全局距離加權(quán)+具有修正功能的離散度加權(quán))加權(quán)方式時(shí)，效果最佳，同時(shí)也說明iterated-discrim APR算法在其他數(shù)據(jù)集上表現(xiàn)并不理想。

通過對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，發(fā)現(xiàn)被錯(cuò)誤分類的樣本大部分集中在惡性樣本集合內(nèi)，這說明庫(kù)中惡性樣本之間的差異性較良性樣本之間較大，使得惡性樣本不如良性樣本聚集，分布散亂，造成分類錯(cuò)誤。

4 結(jié)束語

本文針對(duì)Citation-kNN算法進(jìn)行了改進(jìn)，充分考慮了樣本的分布特征，提出了基于樣本距離加權(quán)、基于樣本離散度加權(quán)的方法，并對(duì)多種組合方式進(jìn)行了實(shí)驗(yàn)。在標(biāo)準(zhǔn)數(shù)據(jù)集和乳腺超聲圖像數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該方法要明顯優(yōu)于Citation-kNN算法，具有良好的適應(yīng)性。同時(shí)，在超聲圖像庫(kù)上的實(shí)驗(yàn)結(jié)果表明，在醫(yī)學(xué)圖像分類中可以采用多示例學(xué)習(xí)方法，減少對(duì)感興趣區(qū)域(ROI)準(zhǔn)確定位的依賴，避免由于分割不準(zhǔn)確所帶來的特征提取誤差。在今后的工作中，將進(jìn)一步針對(duì)醫(yī)學(xué)圖像的特點(diǎn)，提取更為有效的特征，并探討擴(kuò)展傳統(tǒng)的多示例學(xué)習(xí)方法，使之符合醫(yī)學(xué)圖像結(jié)構(gòu)復(fù)雜，良惡性特征相互重疊等特性。

表6 不同加權(quán)方式時(shí)的分類準(zhǔn)確率(%)

[1]Dietterich T G, Lathrop R H, and Lozano-Pérez T. Solving the multiple-instance problem with axis-parallel rectangles[J].Artificial Intelligence, 1997, 89(1-2): 31-71.

[2]Foulds J and Frank E. A review of multi-instance learning assumptions[J].Knowledge Engineering Review, 2010, 25(1):1-25.

[3]Maron O and Lozano-Pérez T. A framework for multipleinstance learning[J].Advances in Neural Information Processing Systems, 1998,(10): 570-576.

[4]Wang J and Zucker J D. Solving the multiple-instance problem: a lazy learning approach[C]. Proceedings of the 17th International Conference on Machine Learning, San Francisco,CA, 2000: 1119-1125.

[5]Zhang Q and Goldman S A. EM-DD: an improved multipleinstance learning technique[J].Advances in Neural Information Processing Systems, 2002,(14): 1073-1080.

[6]Andrews S, Hofmann T, and Tsochantaridis I. Multiple instance learning with generalized support vector machines[C]. Proceedings of the National Conference on Artificial Intelligence, Edmonton, Alta., Canada, 2002: 943-944.

[7]Katsamanis A, Gibson J, Black M P,et al.. Multiple instance learning for classification of human behavior observations [C].Proceedings of Affective Computing and Intelligent Interaction, Memphis, TN, USA, 2011: 145-154.

[8]Vezhnevets A and Buhmann J. Towards weakly supervised semantic segmentation by means of multiple instance and multitask learning[C]. Proceedings of Computer Vision and Pattern Recognition, San Francisco, CA, United States, 2010:3249-3256.

[9]Guillaumin M, Verbeek J, and Schmid C. Multiple instance metric learning from automatically labeled bags of faces[C].Proceedings of European Conference on Computer Vision,Heraklion, Crete, Greece, 2010: 634-647.

[10]Tsoumakas G, Katakis I, and Vlahavas I. Mining Multi-Label Data, Data Mining and Knowledge Discovery Handbook[M].Berlin: Springer, 2010: 667-686.

[11]Zhou Z H, Jiang K, and Li M. Multi-instance learning based web mining[J].Applied Intelligence, 2005, 22(2): 135-147.

[12]Zhu Liang, Zhao Bo, and Gao Yang. Multi-class multiinstance learning for lung cancer image classification based on bag feature selection[C]. Fifth International Conference on Fuzzy Systems and Knowledge Discovery, FSKD, Jinan,China, 2008, 2: 487-492.

[13]Zhou Z H. Multi-instance learning from supervised view[J].Journal Computer Science and Technology, 2006, 21(5):800-809.

[14]Cheng H D, Shan Juan, Ju Wen,et al.. Automated breast cancer detection and classification using ultrasound images: a survey[J].Pattern Recognition, 2010, 43(1): 299-317.

[15]Liu B, Cheng H D, Huang J,et al.. Fully automatic and segmentation-robust classification of breast tumors based on local texture analysis of ultrasound images[J].Pattern Recognition, 2010, 43(1): 280-298.