基于局部加權的Citation-kNN算法

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

(哈爾濱工業大學計算機科學與技術學院 哈爾濱 150001)

1 引言

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

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

在多示例學習概念和算法提出以后，已經在多個領域得到了成功應用，如：藥物預測[1]；圖像分類、標注[7]、圖像分割[8]；視頻中人的識別[9]，股票選擇[10]；索引網頁推薦[11]；顯微鏡下的肺癌細胞圖像識別[12]等。

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

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

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

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

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

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

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

2.1 基于距離權值的算法改進

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

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

基于距離加權的類別決策函數定義為

圖2 距離權值解決的情況

本文所采用的距離加權函數為

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

2.2 基于離散度權值的算法改進

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

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

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

基于離散度加權的決策函數為

圖3 離散度權值所解決的情況

其中X為測試示例包，Ti為X投票集合中的訓練示例包，其標簽ci用+1或-1來表示，S(Ti)為訓練示例包的離散度權值，其定義為

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

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

圖4 訓練樣本中存在噪聲的情況

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

2.3 綜合加權算法

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

3 實驗結果

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

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

3.1 MUSK庫的實驗結果

MUSK庫包含MUSK1和MUSK2兩個分子構造數據集，每個數據集中包含多個示例包，每個示例包包含多個示例，每個示例代表一種分子構造方法，其特點如表3所示。

表2 加權方式的組合

表3 MUSK庫

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

表4 MUSK1和MUSK2上的實驗準確率(%)

本文所采用的方法與其他多示例學習算法在MUSK1和MUSK2庫上的性能比較結果如表5所示。

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

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

3.2 超聲乳腺腫瘤良惡性分類實驗

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

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

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

區域大小反映了所提取特征的分辨率，區域越小，則特征分辨率越高，不同區域之間的特征差異越??；區域越大，則特征分辨率越低，極端情況下，當區域大小為圖像大小時，則多示例學習問題被還原為傳統有監督學習問題，在區域大小的選擇上，存在著既能夠反映圖像的局部特征，又能夠使得區域之間的可分性較好的一些劃分，對于不同的圖像和不同的樣本庫，該劃分不盡相同。

圖5 示例包的構建

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

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

通過對實驗結果進行分析，發現被錯誤分類的樣本大部分集中在惡性樣本集合內，這說明庫中惡性樣本之間的差異性較良性樣本之間較大，使得惡性樣本不如良性樣本聚集，分布散亂，造成分類錯誤。

4 結束語

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

表6 不同加權方式時的分類準確率(%)

[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.