陳偉杰，鄭成勇，蔡圣杰，羅智玉

（五邑大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣東 江門 529000）

0 引 言

在傳統(tǒng)的模式識(shí)別中，若訓(xùn)練一個(gè)高效且準(zhǔn)確的分類器，大量的已標(biāo)記樣本是必不可少的。但在許多情況下，標(biāo)記樣本十分耗時(shí)耗力，導(dǎo)致每個(gè)類別的訓(xùn)練樣本很可能只有一個(gè)或者少量幾個(gè)，無法使分類器的分類精度得到有效提高。同時(shí)，很多的數(shù)據(jù)集也會(huì)存在樣本類別數(shù)量不平衡的問題。樣本數(shù)量不足以及樣本類別數(shù)量不平衡而導(dǎo)致分類器性能下降的問題統(tǒng)稱為少樣本問題。少樣本問題的本質(zhì)是訓(xùn)練樣本數(shù)量過少，大量的無標(biāo)記樣本信息無法得到應(yīng)用。

面對(duì)少樣本問題，文獻(xiàn)[2]提出通過數(shù)據(jù)增強(qiáng)的方法對(duì)原有的少量樣本數(shù)據(jù)集進(jìn)行樣本擴(kuò)充，待擴(kuò)充的樣本可以是未標(biāo)記樣本或者合成的已標(biāo)記虛擬樣本。

在少樣本條件下進(jìn)行樣本擴(kuò)充，第一步在于篩選可靠的無標(biāo)記樣本，即候選樣本選擇問題。篩選的原則是根據(jù)無標(biāo)記樣本與標(biāo)記樣本的相似性進(jìn)行篩選。如通過鄰域像素與中心標(biāo)記像素具有相似性，挑選相鄰像素加入標(biāo)記樣本集中。在同質(zhì)區(qū)的樣本均符合同質(zhì)準(zhǔn)則，則同質(zhì)區(qū)的樣本大概率屬于同一類，將同質(zhì)區(qū)的樣本添加進(jìn)標(biāo)記樣本集中。傳統(tǒng)的SMOTE（Synthetic Minority Oversampling Technique，合成少數(shù)過采樣技術(shù)）算法通過線性插值生成虛擬樣本，在線性空間中，通過投影擴(kuò)增虛擬樣本進(jìn)行樣本擴(kuò)充。

同時(shí)，聚類分析也應(yīng)用于樣本篩選中。如半監(jiān)督Kmeans 聚類算法是以K-means 聚類為基礎(chǔ)，將數(shù)據(jù)對(duì)象標(biāo)簽的分布作為初始的聚類分布進(jìn)行聚類，或者以標(biāo)簽信息作為輔助信息的半監(jiān)督聚類算法。考慮到無標(biāo)記樣本隱含的空間結(jié)構(gòu)信息，與半監(jiān)督分類結(jié)合，文獻(xiàn)[8]使用模糊C 均值聚類選取信息含量高的無標(biāo)記樣本賦予標(biāo)簽來輔助訓(xùn)練分類器，該方法有效考慮到樣本間的相似性以及隱含的空間數(shù)據(jù)信息。文獻(xiàn)[9]通過計(jì)算無標(biāo)記樣本與標(biāo)記樣本的距離，選取距離類中心最近的點(diǎn)進(jìn)行樸素貝葉斯分類，這也應(yīng)用了標(biāo)記樣本與無標(biāo)記樣本間的空間相似性。

篩選無標(biāo)記樣本后，更重要的是如何從候選樣本中選擇出各類擴(kuò)展訓(xùn)練樣本集、樣本擴(kuò)充方法問題。由于單個(gè)分類器局限性較大，通過經(jīng)驗(yàn)與先驗(yàn)知識(shí)可知，使用單個(gè)分類器對(duì)候選樣本進(jìn)行樣本選擇，往往會(huì)使分類決策存在一定的錯(cuò)誤。在訓(xùn)練樣本擴(kuò)充的過程中，若將賦予了錯(cuò)誤類標(biāo)記的樣本大量地添加至訓(xùn)練樣本集中，則會(huì)降低分類器的分類能力，造成分類錯(cuò)誤率的提高。

針對(duì)單一分類器的局限性較大的問題，文獻(xiàn)[10]提出了一種Co-training的算法，利用標(biāo)記樣本初始訓(xùn)練兩個(gè)分類器，通過兩個(gè)分類器賦予無標(biāo)記樣本偽標(biāo)簽，然后將每個(gè)分類器標(biāo)注后的樣本添加進(jìn)另一個(gè)分類器的訓(xùn)練樣本集中，并對(duì)另一個(gè)分類器進(jìn)行再次訓(xùn)練，使分類器的分類效果提高。隨后，文獻(xiàn)[11]提出了Tri-training算法，較Co-training 上增加了第三個(gè)分類器，前兩個(gè)分類器共同從候選樣本集中選擇擴(kuò)展訓(xùn)練樣本添加至第三個(gè)分類器的訓(xùn)練樣本集中，并再次訓(xùn)練第三個(gè)分類器。但在少樣本條件下，傳統(tǒng)的Tri-training 算法會(huì)因?yàn)闃?biāo)記樣本數(shù)量較少，導(dǎo)致分類器的差異性不足，無法有效提高分類器的分類性能。因此，文獻(xiàn)[12]通過主動(dòng)學(xué)習(xí)選取具有大量信息量的無標(biāo)記樣本，并通過差分算法得到最優(yōu)訓(xùn)練樣本集，并用此訓(xùn)練樣本集訓(xùn)練多個(gè)分類器，使多個(gè)分類器的差異性加大，提高了分類器的分類性能。這些算法的目的是獲取不同的訓(xùn)練樣本集，以此訓(xùn)練樣本集訓(xùn)練同一分類器，從而獲得多個(gè)差異性較大的分類器。這些方法的弱點(diǎn)在于盡管通過不同的擴(kuò)增樣本方法，使多個(gè)分類器的差異性增強(qiáng)，但單一分類器的局限性仍然存在。

針對(duì)上文所述候選樣本選擇問題以及樣本擴(kuò)充方法問題，本文提出一種K-最近鄰及多分類器協(xié)同的訓(xùn)練樣本擴(kuò)增分類框架。該分類框架在少量樣本的條件下，通過選擇多個(gè)分類器協(xié)同判別每類訓(xùn)練樣本的K-最近鄰樣本，擴(kuò)增訓(xùn)練樣本集，有效提高分類器的分類精度。

1 基于K-最近鄰及多分類協(xié)同判決的訓(xùn)練樣本擴(kuò)增分類方法

1.1 算法思想

在少樣本條件下，如何擴(kuò)增訓(xùn)練樣本是模式識(shí)別、半監(jiān)督分類中的重要問題。要進(jìn)行樣本擴(kuò)增，首要的問題是選擇哪些未標(biāo)記樣本去進(jìn)行擴(kuò)增，即候選樣本選擇問題；其次是如何從候選樣本中選擇出各類的擴(kuò)展訓(xùn)練樣本集，即樣本擴(kuò)充方法問題。針對(duì)候選樣本選擇問題，本文提出一種標(biāo)記樣本K-最近鄰候選樣本選擇法，通過搜索出各類的各個(gè)標(biāo)記樣本的個(gè)最近鄰的方法，來獲得各類的候選擴(kuò)增樣本集。針對(duì)樣本擴(kuò)充方法問題，本文提出一種多分類器協(xié)同判決樣本擴(kuò)增法：若多個(gè)分類器多數(shù)或一致將某候選樣本判決為某類，則將該候選樣本添加至該類的擴(kuò)展訓(xùn)練樣本集中。

本文所指某樣本的K-最近鄰，可以是樣本在特征空間中的距離（如人臉圖像所提特征之間的歐氏距離）度量意義下的最近鄰，也可以是幾何空間中的距離意義下的最近鄰（如圖像中的鄰域像素）。

提出K-最近鄰候選樣本選擇法的出發(fā)點(diǎn)如下：

1）可以快速縮小擴(kuò)增樣本的搜索范圍，加速樣本擴(kuò)增過程。

2）無論是空間距離下的最近鄰，還是特征距離意義下的最近鄰，某標(biāo)記樣本的K-最近鄰較大概率具有與該訓(xùn)練樣本一樣的類別，從該候選集中選擇擴(kuò)增樣本可以較好地保證標(biāo)記樣本與其擴(kuò)增樣本在類別上的一致性。

盡管各個(gè)標(biāo)記樣本的K-最近鄰候選擴(kuò)增樣本集具有較大概率屬于同一類，為進(jìn)一步避免其他類的未標(biāo)記樣本錯(cuò)誤加入某類的擴(kuò)增樣本集，提出使用多分類器協(xié)同判決樣本擴(kuò)增法。在少樣本條件下，通過少樣本訓(xùn)練好的單一分類器分類精度一般仍然較低，不足以將候選擴(kuò)增訓(xùn)練樣本正確識(shí)別為其所屬類別，但若多個(gè)分類器多數(shù)或一致將某候選擴(kuò)增樣本判決為某類，則將該候選樣本添加至該類的擴(kuò)增訓(xùn)練樣本集，出錯(cuò)的概率較低。

獲得擴(kuò)增訓(xùn)練樣本集后，利用訓(xùn)練樣本集及擴(kuò)增訓(xùn)練樣本集共同對(duì)多個(gè)分類器進(jìn)行訓(xùn)練，并對(duì)剩余的未標(biāo)記樣本進(jìn)行基于投票的分類判決。這樣做的好處是：

1）通過再次訓(xùn)練分類器，提高分類器的分類精度，正確識(shí)別剩余的未標(biāo)記樣本。

2）單一分類器識(shí)別過程中具有局限性，對(duì)某些較難識(shí)別的樣本難以識(shí)別為正確類別。通過多個(gè)分類器共同判別，在少樣本條件下，保障了剩余未標(biāo)記樣本的分類準(zhǔn)確率。

3）單一分類器可能在某一數(shù)據(jù)集上具有很高的分類精度，但在另外的數(shù)據(jù)集上，分類精度會(huì)劣于其他分類器。通過多分類器共同判別，可有效解決單一分類器的局限性，提高分類器的泛化能力。在對(duì)未知的數(shù)據(jù)集進(jìn)行分類時(shí)，可達(dá)到良好的分類結(jié)果。

1.2 K-最近鄰及多分類協(xié)同訓(xùn)練樣本擴(kuò)增分類方法

基于K-最近鄰及多分類協(xié)同判決的訓(xùn)練樣本擴(kuò)增分類方法具體描述如下：

輸入：標(biāo)記樣本集，未標(biāo)記樣本集，分類器集={,,…,f}，近鄰數(shù)，分類器分類一致率∈( 0,1 ]。

步驟1：使用標(biāo)記樣本集訓(xùn)練分類器集中的分類器。

步驟2：對(duì)任意∈，不妨設(shè)的類標(biāo)簽為，在中搜索出的個(gè)最近鄰，并將他們加入到標(biāo)簽為的候選訓(xùn)練樣本擴(kuò)增子集E中。

步驟3：對(duì)x∈E，若分類器集中的分類器有不少于100%的分類器將x判別為類別，則將x添加到，并標(biāo)記其分類標(biāo)簽為。

步驟4：若中還有未搜索過其K-最近鄰的標(biāo)記樣本，則返回步驟2，否則，執(zhí)行下一步。

步驟5：使用標(biāo)記樣本集及擴(kuò)增訓(xùn)練樣本集再次訓(xùn)練分類器集中的分類器。

步驟6：使用分類器集中的分類器，對(duì)剩余的未標(biāo)記樣本進(jìn)行分類，并基于投票法確定未標(biāo)記樣本的類別。

輸出：未標(biāo)記樣本集中各樣本的分類標(biāo)簽，擴(kuò)增訓(xùn)練樣本集中樣本的類別為其擴(kuò)增時(shí)確定的類別標(biāo)簽。

在上面的算法框架中，分類器集可采用各種常見的分類器。限于篇幅，本文考慮采用最近鄰分類算法（KNearest Neighbor，KNN）、支 持 向 量 機(jī) 分 類 算 法（Support Vector Machine，SVM）、集成隨機(jī)子空間KNN算法（Ensemble KNN，EKNN）以及集成隨機(jī)子空間鑒別算法（Ensemble Discriminate，ED）。

1）KNN：KNN 的分類策略是針對(duì)樣本空間里的某個(gè)未知類別樣本點(diǎn)，觀測(cè)它周圍的樣本是屬于哪一類的，如果與待測(cè)樣本距離最小的個(gè)樣本中屬于某類的樣本最多，即判定待測(cè)樣本為該類。

2）SVM：該分類器針對(duì)二分類問題，是定義在特征空間上間隔最大的線性分類器；由于包括核技巧，這在實(shí)質(zhì)上使SVM 成為非線性分類器。SVM 的學(xué)習(xí)算法就是求解凸二次規(guī)劃的最優(yōu)化算法。

3）EKNN：隨機(jī)子空間是在訓(xùn)練樣本的全部特征中，通過隨機(jī)選取部分特征來訓(xùn)練每個(gè)分類器，從而降低每個(gè)分類器的相關(guān)性，為集成學(xué)習(xí)的一種。集成學(xué)習(xí)需要多個(gè)弱學(xué)習(xí)器共同構(gòu)造成一個(gè)強(qiáng)分類器完成分類任務(wù)。該算法在集成學(xué)習(xí)中選擇的弱分類器為最近鄰分類器算法。

4）ED：隨機(jī)子空間是在訓(xùn)練樣本的全部特征中，通過隨機(jī)選取部分特征來訓(xùn)練每個(gè)分類器，從而降低每個(gè)分類器的相關(guān)性，為集成學(xué)習(xí)的一種。集成學(xué)習(xí)需要多個(gè)弱學(xué)習(xí)器共同構(gòu)造成一個(gè)強(qiáng)分類器完成分類任務(wù)。該算法在集成學(xué)習(xí)中選擇的弱分類器為高斯判別分析分類器算法。

步驟6 中的投票法，具體執(zhí)行時(shí)會(huì)遇到多個(gè)類別出現(xiàn)票數(shù)一樣多的情況，無法按少數(shù)服從多數(shù)原則確定未標(biāo)記樣本的類別。針對(duì)此問題，提出如下修正方法：

記分類器集中的分類器f（=1，2，…，）對(duì)中的擴(kuò)增樣本的分類與該樣本按步驟3 確定的標(biāo)簽一致的樣本個(gè)數(shù)為v，找出v所對(duì)應(yīng)的最大分類器f。在步驟6中，若存在或超過-1 個(gè)子分類器將未標(biāo)記樣本判別為某一類，則以該類作為該未標(biāo)記樣本的類別，否則用分類器f的分類結(jié)果作為其最終分類結(jié)果。

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

為了證明所提算法框架的有效性，需要同時(shí)與該算法所集成的分類器集的各個(gè)分類器進(jìn)行比較。本文算法與構(gòu)成本文算法的4種分類器算法，共5種算法。5個(gè)分類器在所有數(shù)據(jù)集上各重復(fù)10 次實(shí)驗(yàn)。在每一次實(shí)驗(yàn)中，通過將每一個(gè)數(shù)據(jù)集隨機(jī)劃分為兩部分，分別為標(biāo)記樣本集和測(cè)試樣本集。實(shí)驗(yàn)前，經(jīng)過反復(fù)驗(yàn)證選擇參數(shù)。

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

實(shí)驗(yàn)數(shù)據(jù)集共6 個(gè)，數(shù)據(jù)集描述如表1 所示。

表1 數(shù)據(jù)集描述

1）Lung_Cancer數(shù)據(jù)集：肺部癌癥數(shù)據(jù)集。具有5 個(gè)類別，每個(gè)樣本12 600 個(gè)特征，共203 個(gè)樣本。

2）divorce 數(shù)據(jù)集：離婚預(yù)測(cè)數(shù)據(jù)集。具有2 個(gè)類別，每個(gè)樣本54 個(gè)特征，共177 個(gè)樣本。

3）ORL_32×32 數(shù)據(jù)集：人臉圖像數(shù)據(jù)集，包含40 個(gè)人，每人10 張圖片，共400 張圖像。具有40 個(gè)類別，每個(gè)樣本1 024個(gè)特征，共400個(gè)樣本。

4）semeion 數(shù)據(jù)集：通過掃描80 人手寫的阿拉伯?dāng)?shù)字圖像集，每個(gè)裁剪圖像的分辨率為16×16，其中每個(gè)像素有256 個(gè)灰度級(jí)。具有10 個(gè)類別，每個(gè)樣本256 個(gè)特征，共1 593 個(gè)樣本。

5）Letter-recognition 數(shù)據(jù)集：字母信息識(shí)別數(shù)據(jù)集。具有26 個(gè)類別，每個(gè)樣本14 個(gè)特征，共20 000 個(gè)樣本。

6）Crowdsourced-Mapping 數(shù)據(jù)集：地球空間信息數(shù)據(jù)集。具有6 個(gè)類別，每個(gè)樣本28 個(gè)特征，共10 845 個(gè)樣本。

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

針對(duì)每個(gè)類別樣本總數(shù)的不同，實(shí)驗(yàn)分以下兩種情況：

情況一：針對(duì)樣本總數(shù)較少的數(shù)據(jù)集。每類的標(biāo)記樣本個(gè)數(shù)設(shè)置為2，3，4，5。經(jīng)反復(fù)測(cè)試，設(shè)置為3。由于每類樣本總數(shù)較少，故值不可設(shè)置過高。所選的數(shù)據(jù)集為divorce、Lung_Cancer 及ORL_32×32。

情況二：針對(duì)每類樣本總數(shù)較多的數(shù)據(jù)集，每類的標(biāo)記樣本個(gè)數(shù)設(shè)置為10，20，30，40。由于每類的樣本數(shù)較多，所以每個(gè)樣本與其同一類別的近鄰樣本的數(shù)目也較多，故將近鄰數(shù)值適當(dāng)增大。經(jīng)反復(fù)測(cè)試，設(shè)置為10。所選數(shù)據(jù)集為Crowdsourced-Mapping、semeion 以及Letter-recognition。

2.3 樣本擴(kuò)增對(duì)分類器分類精度的提升效果

為驗(yàn)證樣本擴(kuò)增對(duì)分類器性能的提升效果，針對(duì)情況一和情況二進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖1 所示。圖1的每個(gè)子圖的橫坐標(biāo)代表標(biāo)記樣本的個(gè)數(shù)，縱坐標(biāo)代表10 次實(shí)驗(yàn)每個(gè)分類器算法的平均分類精度；圖中的實(shí)線代表擴(kuò)增后分類器的分類精度，虛線代表擴(kuò)增前分類器的分類精度，每個(gè)子分類器擴(kuò)增前后的分類精度均由不同的符號(hào)進(jìn)行標(biāo)記。

圖1 在6 個(gè)數(shù)據(jù)集上四種算法使用數(shù)據(jù)擴(kuò)增和不使用數(shù)據(jù)擴(kuò)增的分類精度對(duì)比

從圖1 可以看出，基于多分類器協(xié)同判別的樣本擴(kuò)增能顯著提升各子分類器的分類精度。對(duì)于每類的樣本總數(shù)較少的情況一，隨著標(biāo)記樣本數(shù)的增加，擴(kuò)增后的分類效果更好。對(duì)于每類的樣本數(shù)目較多的情況二，隨著標(biāo)記樣本數(shù)的增加，多分類器協(xié)同判別擴(kuò)增后的分類精度的擴(kuò)增幅度在減小。

2.4 多分類器協(xié)同下的實(shí)驗(yàn)結(jié)果

在多個(gè)分類器協(xié)同判別每類個(gè)最近鄰樣本得到擴(kuò)增訓(xùn)練樣本集后，通過擴(kuò)增訓(xùn)練樣本集再次訓(xùn)練多個(gè)分類器，然后再次使用訓(xùn)練后的多個(gè)分類器對(duì)剩余未標(biāo)記樣本進(jìn)行協(xié)同分類，與使用擴(kuò)增訓(xùn)練樣本集的多個(gè)分類器的分類結(jié)果進(jìn)行對(duì)比，以檢驗(yàn)所提算法的有效性。實(shí)驗(yàn)結(jié)果如圖2 所示。其中，每個(gè)子圖的橫坐標(biāo)代表標(biāo)記樣本數(shù)，縱坐標(biāo)表示10 次實(shí)驗(yàn)每個(gè)分類算法的平均分類精度，vote 代表所提算法的實(shí)驗(yàn)結(jié)果。

從圖2a）～圖2c）可以看出，在不同的數(shù)據(jù)集上，組成多分類器協(xié)同判別框架的多個(gè)分類器各有優(yōu)劣，無任何分類器一致優(yōu)于其他分類器。在少樣本的條件下，所提算法的分類效果較組成多分類器協(xié)同判別算法的多個(gè)分類器算法的分類效果有所提高，并且穩(wěn)定性優(yōu)于組成多分類器協(xié)同判別算法的多個(gè)分類器算法。

從圖2d）～圖2f）可以看出，在數(shù)據(jù)集樣本總數(shù)較多的情況下，絕大多數(shù)情況下多分類器協(xié)同判別投票法接近或優(yōu)于組成協(xié)同判別分類框架的子分類器的最優(yōu)分類效果。個(gè)別不是最優(yōu)的情況下，也與組成多分類器協(xié)同判別算法框架的多個(gè)子分類器算法的最優(yōu)分類結(jié)果相差較少，且隨著擴(kuò)增訓(xùn)練樣本數(shù)量的增多，所提算法的分類結(jié)果更好。

圖2 在6 個(gè)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果

3 結(jié) 語(yǔ)

針對(duì)少樣本條件下的分類問題，本文提出一種基于K-最近鄰及多分類器協(xié)同的訓(xùn)練樣本擴(kuò)增分類框架。要進(jìn)行樣本擴(kuò)增，首要的問題是候選樣本選擇問題，其次是樣本擴(kuò)充方法問題。針對(duì)候選樣本選擇問題，本文通過搜索出各類各個(gè)標(biāo)記樣本的個(gè)最近鄰，獲得各類候選擴(kuò)增樣本集。針對(duì)樣本擴(kuò)充方法問題，通過使用多個(gè)分類器對(duì)候選擴(kuò)增樣本集進(jìn)行判別，若多數(shù)或一致將某候選樣本判決為某類，則將該候選樣本添加至該類的擴(kuò)展訓(xùn)練樣本集。獲得擴(kuò)增訓(xùn)練樣本集后，利用訓(xùn)練樣本集及擴(kuò)增訓(xùn)練樣本集共同對(duì)多個(gè)分類器進(jìn)行訓(xùn)練，并對(duì)剩余的未標(biāo)記樣本進(jìn)行基于修正的投票的分類判決。最后在多個(gè)數(shù)據(jù)集上驗(yàn)證了算法框架的有效性。在后續(xù)的工作中，將對(duì)算法框架中最優(yōu)參數(shù)的選取，擴(kuò)增樣本的正確標(biāo)簽率的提高以及本文算法的時(shí)間成本的減少等多個(gè)方面進(jìn)行探討，從而更好地提升本文算法框架的分類正確率。