任杰 閔帆 汪敏

摘 要：主動學(xué)習(xí)旨在通過人機交互減少專家標(biāo)注，代價敏感主動學(xué)習(xí)則致力于平衡標(biāo)注與誤分類代價?；谌Q策（3WD）和標(biāo)簽均勻分布（LUD）模型，提出一種基于最遠(yuǎn)總距離采樣的代價敏感主動學(xué)習(xí)算法（CAFS）。首先，設(shè)計了最遠(yuǎn)總距離采樣策略，以查詢代表性樣本的標(biāo)簽;其次，利用了LUD模型和代價函數(shù)，計算期望采樣數(shù)目;最后，使用了k-Means聚類技術(shù)分裂已獲得不同標(biāo)簽的塊。CAFS算法利用三支決策思想迭代地進(jìn)行標(biāo)簽查詢、實例預(yù)測和塊分裂，直至處理完所有實例。學(xué)習(xí)過程在代價最小化目標(biāo)的控制下進(jìn)行。在9個公開數(shù)據(jù)上比較，CAFS比11個主流的算法具有更低的平均代價。

關(guān)鍵詞：主動學(xué)習(xí); k-Means聚類; 標(biāo)簽均勻分布; 三支決策

中圖分類號：TP181

文獻(xiàn)標(biāo)志碼：A

Cost-sensitive active learning through farthest distance sum sampling

REN Jie1， MIN Fan1*， WANG Min2

1.School of Computer Science， Southwest Petroleum University， Chengdu Sichuan 610500， China;

2.School of Electrical Engineering and Information， Southwest Petroleum University， Chengdu Sichuan 610500， China

Abstract：

Active learning aims to reduce expert labeling through man-machine interaction， while cost-sensitive active learning focuses on balancing labeling and misclassification costs. Based on Three-Way Decision （3WD） methodology and Label Uniform Distribution （LUD） model， a Cost-sensitive Active learning through the Farthest distance sum Sampling （CAFS） algorithm was proposed. Firstly， the farthest total distance sampling strategy was designed to query the labels of representative samples. Secondly， LUD model and cost function were used to calculate the expected sampling number. Finally， k-Means algorithm was employed to split blocks obtained different labels. In CAFS， 3WD methodology was adopted in the iterative process of label query， instance prediction， and block splitting， until all instances were processed. The learning process was controlled by the cost minimization objective. Results on 9 public datasets show that CAFS has lower average cost compared with 11 mainstream algorithms.

Key words：

active learning; k-Means clustering; label uniform distribution; Three-Way Decision （3WD）

0 引言

主動學(xué)習(xí)[1]是半監(jiān)督學(xué)習(xí)[2]的一種方式，旨在通過人機交互減少專家標(biāo)注的工作量。常用方法大致分為兩類：基于聚類的方法選擇具有代表性的對象，基于委員會的方法[3]選擇不確定性高的對象。Cohn等[4]提出了一種基于高斯模型和局部加權(quán)回歸模型的主動學(xué)習(xí)算法，應(yīng)用模型以及回歸使主動學(xué)習(xí)所需的訓(xùn)練樣本急劇減少。Wang等[5]提出了基于密度峰值聚類的主動學(xué)習(xí)算法，在相同的訓(xùn)練樣本基礎(chǔ)上使得算法的分類精度進(jìn)一步提高。目前主動學(xué)習(xí)已廣泛應(yīng)用于文本分類[6]、信息提取[7]、圖像分類[8]、語音識別[9]等領(lǐng)域。

代價敏感主動學(xué)習(xí)[10]致力于平衡標(biāo)注與誤分類代價。教師代價是專家標(biāo)注樣本標(biāo)簽的代價，誤分類代價是指將樣本錯誤分類的代價。該問題比經(jīng)典的主動學(xué)習(xí)更有實際意義，也更具一般性。Min等[11]利用k最近鄰（k-Nearest Neighbors， kNN）將總體根據(jù)代價分成3個部分，提出了基于kNN的三分代價敏感主動學(xué)習(xí)算法，該算法重復(fù)三分區(qū)過程從而減少了總代價;但該算法并未考慮塊內(nèi)采樣數(shù)目。Wu等[12]建立了標(biāo)簽均勻分布模型，在代價的基礎(chǔ)上利用標(biāo)簽均勻分布（Label Uniform Distribution， LUD）模型計算每塊內(nèi)最優(yōu)的采樣數(shù)目，進(jìn)一步降低了代價;但其采樣策略沒有考慮樣本點的信息量，使得代價依然有可優(yōu)化的空間。

本文提出一種基于最遠(yuǎn)總距離采樣的代價敏感主動學(xué)習(xí)算法（Cost-sensitive Active learning through the Farthest distance sum Sampling， CAFS）。該算法有如下特點：

1）利用三支決策（Three-Way Decision， 3WD）的思想，使學(xué)習(xí)過程更加完善。算法迭代地進(jìn)行標(biāo)簽查詢、實例預(yù)測和塊分裂，直至處理完所有實例。方案在查詢過程中進(jìn)行分類，不需要引入其他的分類器。

2）提出了最遠(yuǎn)總距離策略以獲得需查詢標(biāo)簽的樣本。針對隨機采樣采樣的不足，該策略綜合考慮了某塊內(nèi)已查詢的所有樣本和信息量，可獲得更具代表性樣本。

3）采用LUD模型計算塊內(nèi)需要查詢的樣本數(shù)，并設(shè)置閾值，對過小的塊進(jìn)行總體查詢，使得采樣數(shù)目在此情況下達(dá)到最優(yōu)。該模型對不同的數(shù)據(jù)集有較好的適用性。

4）采用了高效的k-Means聚類算法。該算法使用距離函數(shù)表達(dá)對象的相似性，與最遠(yuǎn)總距離采樣策略配合可以獲得很好效果。

本文在9個數(shù)據(jù)集上與11個主流算法進(jìn)行了比較，結(jié)果表明，CAFS算法在平均代價方面優(yōu)于對比算法。

1 相關(guān)工作

1.1 三支決策

三支決策（Three-Way Decision， 3WD）[13]是一種符合人類認(rèn)知的決策模式。它是實現(xiàn)二支決策的一個中間步驟，在實際決策的過程中，對于具有充分把握接受或拒絕的事物能夠立即作出快速的判斷，對于那些不能立即作出決策的事件，則進(jìn)行延遲決策。三支決策是一種包含三個部分或三個操作的分治方法，也是決策理論粗糙集的延伸。

很多理論和應(yīng)用使用了三支決策的方法及思想。其中三支形式概念分析和三支認(rèn)知計算衍生出了概念學(xué)習(xí)和多粒度認(rèn)識操作。通過決策粗糙集理論和屬性約簡方法將三支決策理論粗糙集與代價敏感相結(jié)合[14]，在樣本上得出最優(yōu)測試屬性，并依據(jù)最優(yōu)測試屬性在測試集上計算，使得分類結(jié)果具有最小誤分類代價和測試代價?；谌Q策的多粒度粗糙集理論[15]通過分析三支決策與概率粗糙集、決策粗糙集間的關(guān)系以及在屬性約簡的相關(guān)知識，給出了在醫(yī)學(xué)、工程方向的應(yīng)用和三支決策未來的發(fā)展方向。三支鄰域粗糙集模型[16]根據(jù)錯誤率和多粒度構(gòu)建不同的鄰域系統(tǒng)，證明了可變精度粗糙集和多粒度粗糙集是鄰域系統(tǒng)粗糙集模型的特例。

1.2 代價敏感主動學(xué)習(xí)

代價敏感主動學(xué)習(xí)在主動學(xué)習(xí)的基礎(chǔ)上，考慮了在學(xué)習(xí)過程中的代價敏感性，為不同的類別提供了不同的代價權(quán)重以及教師代價，在代價函數(shù)的約束下進(jìn)行學(xué)習(xí)。

由于代價敏感學(xué)習(xí)更具實際意義，從而受到很多學(xué)者的關(guān)注，如文獻(xiàn)[10]中引入了代價敏感主動學(xué)習(xí)，并提出在未標(biāo)記數(shù)據(jù)下的分類概率和基于分類概率的抽樣和決策。Settles等[17]分析了4個真實的文字和圖像領(lǐng)域的教師代價，給出了某些具體領(lǐng)域的教師代價的特征。Liu等[18]將聯(lián)系教師代價與距離，使代價敏感主動學(xué)習(xí)在空間數(shù)據(jù)上展開。Zhao等[19]通過優(yōu)化兩種代價處理不平衡URL檢測任務(wù)的問題，使代價敏感主動學(xué)習(xí)在URL檢測問題上優(yōu)于一般檢測學(xué)習(xí)算法。Chen等[20]提出了最大預(yù)期代價和代價加權(quán)邊際最小策略，使多類代價敏感主動學(xué)習(xí)表現(xiàn)更加突出。Demir等[21]通過在遙感圖像分類中，使用成本函構(gòu)建教師代價利用了遙感圖像的特性，使代價的定義更為全面。Huang等[22]通過非度量多位縮放將代價信息嵌入到特殊隱藏空間中的距離中，從隱藏空間的距離定義樣本的不確定性，使學(xué)習(xí)過程選擇更有效的樣本。

1.3 標(biāo)簽均勻分布模型

目前，數(shù)據(jù)集中大量標(biāo)簽未知是造成多種學(xué)習(xí)任務(wù)結(jié)果不理想的重要原因之一，主動學(xué)習(xí)算法正是此類問題的合理解決方案。對于大量標(biāo)簽未知的數(shù)據(jù)，我們很迫切地需要知道數(shù)據(jù)的結(jié)構(gòu)以及分布，所以很容易基于現(xiàn)實模型或者簡單的理論分析來假設(shè)一種分布模型，應(yīng)用數(shù)據(jù)本身的結(jié)構(gòu)在滿足任務(wù)目標(biāo)的前提下降低學(xué)習(xí)過程中的代價。

基于最遠(yuǎn)總距離采樣的代價敏感主動學(xué)習(xí)CAFS算法應(yīng)用簡單的均勻分布統(tǒng)計模型，利用概率和均值估計二分類數(shù)據(jù)中的正反例的個數(shù)。同時為了減少總教師代價，在均勻分布的基礎(chǔ)上，利用期望數(shù)目和代價函數(shù)計算最優(yōu)采樣數(shù)目。

CAFS算法采用標(biāo)簽均勻分布模型，即在總體分布未知的情況下，假設(shè)二分類總體中抽到正反例的概率相同。其概率如下：

p（R*=i）=1n+1; 0≤i≤n（1）

在標(biāo)簽均勻分布模型中，如果在總體X中隨機選取R個正例和B個反例，那么在總體中有R*個正例的概率則為：

b（R*R，B;n）=ARR*·ABn-R*∑ni=RARiABn-i（2）

在上述假設(shè)以及概率公式成立的情況下，正反例在總體X中期望的數(shù)目為：

b（n，R，B）=（n，B，R）=∑n-Ri=RiARiABn-in∑n-Ri=RARiABn-i（3）

當(dāng)在連續(xù)抽出正例或反例時候，出現(xiàn)另一個對立的實例對于期望的影響很大，有如下公式成立：

（n，R，0）>（n，2R-1，1）（4）

2 代價敏感主動學(xué)習(xí)問題描述

為介紹CAFS算法，表1列出了本文使用的符號以及含義。

2.1 數(shù)據(jù)模型

CAFS算法使用如下數(shù)據(jù)模型。

定義1 教師誤分類代價敏感決策系統(tǒng)（Teacher-and-Misclassification-Cost-sensitive Decision System， TMC-DS），是七元組：

S=（U，C，d，V，I，m，t）（5）

其中：U是有限的實例集合，C是條件屬性的集合，d是代價屬性，V=∪a∈C∪syggg00Va，Va是屬性a的屬性值，I：U×（C∪syggg00）→ V是信息函數(shù)，m：Vd×Vd → R+∪{0}是誤分類代價函數(shù)，t∈R+∪{0}是教師代價。

2.2 問題定義

問題1 代價敏感主動學(xué)習(xí)。

輸入：一個代價敏感決策系統(tǒng)七元組TMC-DS;

輸出：專家查詢的實例集合Ut，預(yù)測標(biāo)簽lU-Ut。

優(yōu)化目標(biāo)：min cost=（tUt+∑Ui=1m（li，yi））/U

輸入的是不含標(biāo)記的代價敏感決策系統(tǒng)TMC-DS。輸出包含兩個部分：其一是實例子集Ut其中的標(biāo)簽是查詢或者由專家給出;其二是剩余實例的預(yù)測標(biāo)簽lU-Ut。

優(yōu)化目標(biāo)是通過減少教師代價和誤分類代價使平均代價達(dá)到最小，其中t×Ut是總教師代價，∑Ui=1m（li，yi）是總的誤分類代價。其中教師代價和誤分類代價是在獲得Ut之后計算得到的，Ut并不是用戶指定的。而隨著Ut大小的增加，教師代價呈線性增長，誤分類代價可能會減少，本文的CAFS算法找到了一個教師代價與誤分類代價的相對平衡點。

3 CAFS算法

本章將詳細(xì)介紹CAFS算法的執(zhí)行過程，其中包括CAFS算法總體流程、根據(jù)LUD模型以及代價函數(shù)計算出最優(yōu)采樣數(shù)目的lookup方法、根據(jù)最遠(yuǎn)總距離采樣策略利用k-Means聚類對塊進(jìn)行分裂并迭代學(xué)習(xí)的splitAndLearn方法。

3.1 算法框架

基于最遠(yuǎn)總距離采樣的代價敏感主動學(xué)習(xí)CAFS的算法框架如算法1所示，其中第2）行是為了在塊中尋找最遠(yuǎn)總距離的代表點，之后的步驟會確定當(dāng)前塊是否需要分塊迭代學(xué)習(xí)。

算法1 基于最遠(yuǎn)總距離采樣的代價敏感主動學(xué)習(xí)算法（CAFS）。

輸入：樣本總體U，算法2（lookup）最優(yōu)采樣數(shù)目s;

輸出：預(yù)測標(biāo)簽集合lU-Ut。

有序號的程序——————————Shift+Alt+Y

程序前

1）

for（xi∈U && （R or B）

2）

SLf ← findFarthest（Ut）;/*結(jié)合已經(jīng)查詢的實例結(jié)合中尋找最遠(yuǎn)距離點*/

3）

if（ySLf== y0）/*判斷最遠(yuǎn)的代表樣本點是否與初始樣本點的標(biāo)簽相同*/

4）

Ut ← SLf

5）

continue

6）

else

7）

splitAndLearn/*分裂迭代學(xué)習(xí)算法3 */

8）

end if

9）

end for

10）

return lU-Ut

程序后

算法2是CAFS算法中根據(jù)LUD模型計算要查詢標(biāo)簽個數(shù)的lookup方法，其中f是根據(jù)LUD模型以及代價函數(shù)所確定的正反例期望查詢數(shù)目，如式（6）所示：

f=

m（-，+）N（1-（N，R，0））+tR， 已標(biāo)記實例為正例

m（+，-）N（1-b（N，0，B））+tB，已標(biāo)記實例為反例（6）

算法2 最優(yōu)標(biāo)簽查詢數(shù)目計算算法（lookup）。

輸入：數(shù)據(jù)塊的大小n，第一個抽出的樣本標(biāo)簽y0;

輸出：最優(yōu)采樣數(shù)s。

有序號的程序——————————Shift+Alt+Y

程序前

1）

for（xi∈X）

2）

SLf ← boughti/*記錄已購買的標(biāo)簽*/

3）

i（r*，b*）← f/*根據(jù)式（6）計算期望查詢數(shù)目 */

4）

end for

5）

i* ← lookup（y0）

6）

s ← （i*-SL.legth）

7）

return s

程序后

算法3介紹塊分裂條件以及如何迭代學(xué)習(xí)的過程。在選取最遠(yuǎn)總距離代表點后，需要得知該代表點與之前查詢的塊標(biāo)簽是否一致。如果一致，繼續(xù)利用最遠(yuǎn)距離采樣策略采樣直至達(dá)到最優(yōu)采樣數(shù)s，否則利用k-Means聚類算法分裂該塊并迭代學(xué)習(xí)的過程。

算法3 塊分裂迭代學(xué)習(xí)算法（splitAndLearn）。

輸入：數(shù)據(jù)塊X;

輸出：數(shù)據(jù)塊的X的預(yù)測標(biāo)簽合集li∈X。

有序號的程序——————————Shift+Alt+Y

程序前

1）

if（SL.length

2）

SLnew ← findFarthest（Ut）

3）

if（ySLnew≠yX0）

4）

X1，X2 ← kMeansCluter（X）

5）

lX1 ← CAFS（X1）

6）

lX2 ← CAFS（X2）

7）

end if

8）

else

9）

end if

10）

return li∈X

程序后

3.2 CAFS時間復(fù)雜度分析

基于最遠(yuǎn)總距離采樣的代價敏感主動學(xué)習(xí)算法（CAFS）的時間復(fù)雜度如表2所示。

在實際算法過程中，時間復(fù)雜度會隨著數(shù)據(jù)集變化而變化。在最優(yōu)情況下，數(shù)據(jù)集中的實例個數(shù)趨于無窮時且為同一標(biāo)簽時，時間復(fù)雜度為Ο（n log n）。在最壞的情況下，且不同標(biāo)簽數(shù)據(jù)分布極為密集時，算法需要遞歸循環(huán)log n次。即：

log n×（Ο（n log n）+Θ（n log n）+Ο（n））=Ο（n2）

4 CAFS運行實例

CAFS算法首先掃描塊內(nèi)已經(jīng)標(biāo)注的實例，查看該塊是否需要分裂，之后計算需要查詢的個數(shù)，以最遠(yuǎn)總距離采樣策略選取代表點并查詢標(biāo)簽，在滿足最優(yōu)采樣數(shù)目s后預(yù)測其他未標(biāo)記數(shù)據(jù)。為了更好地展示CAFS算法的學(xué)習(xí)過程，以下將利用小型的數(shù)據(jù)集描述CAFS算法的學(xué)習(xí)過程。

如圖1運行實例，首先，對數(shù)據(jù)進(jìn)行初始化圖1（a），并記錄數(shù)據(jù)中的第一個實例，然后如圖1（b）采用最遠(yuǎn)總距離樣本采樣策略選取代表性樣本點查詢。如圖1（c），很明顯兩個實例的標(biāo)簽不同，此時利用k-Means聚類對數(shù)據(jù)塊進(jìn)行分裂處理。對分裂后的數(shù)據(jù)塊采樣同樣的策略迭代學(xué)習(xí)，如圖1（d） （e）。由于本次運行實例采用極具代表性的數(shù)據(jù)，所以在數(shù)據(jù)塊的最優(yōu)查詢數(shù)目s的前提下兩個塊中的樣本標(biāo)簽相同，根據(jù)CAFS算法的策略，如圖1（f）會對剩余的實例進(jìn)行預(yù)測，即完成本次過程。

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

實驗運行在64位16GB RAM的Windows10的個人電腦上，其中處理器為i7-7700HQ 2.80GHz，并利用Java在Eclipse上實現(xiàn)。

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

實驗數(shù)據(jù)集來源于UCI機器學(xué)習(xí)倉庫和IDA基準(zhǔn)倉庫，表3列出了數(shù)據(jù)集的基本信息，這些數(shù)據(jù)集一部分是人造數(shù)據(jù)集，大部分來源于現(xiàn)實生活，涵蓋了生物學(xué)、金融學(xué)、計算機、通信、植物學(xué)、醫(yī)療和質(zhì)譜分析等領(lǐng)域。

實驗選取11個相關(guān)的算法進(jìn)行了對比，并根據(jù)CAFS算

法特點分成了三組進(jìn)行了相關(guān)實驗：1）與同類的代價敏感學(xué)習(xí)算法進(jìn)行對比;2）與代價敏感的主動學(xué)習(xí)算法進(jìn)行對比;3）代價敏感學(xué)習(xí)與非代價敏感學(xué)習(xí)算法對比，而且為了將非代價敏感學(xué)習(xí)與代價敏感學(xué)習(xí)進(jìn)行代價方面的對比，利用實驗中的代價誤分類代價設(shè)置，將非代價敏感學(xué)習(xí)的結(jié)果統(tǒng)一成代價進(jìn)行比較。

5.2 實驗代價設(shè)置

m表示誤分類代價矩陣，m（+，-）=4表示將正例預(yù)測成反例的代價為4，m（-，+）=2表示將反例預(yù)測成正例的代價為2。另外設(shè)置t=1是指查詢一個實例的教師代價是1。實驗中的平均代價計算公式則為：

AverageCost=（M1m（+，-）+M2m（-，+）+tT）/n（7）

其中：M1實驗結(jié)果中將正例預(yù)測成反例的個數(shù)，M2為將反例預(yù)測成正例的個數(shù)，T為向?qū)＜也樵儗嵗膫€數(shù)。

5.3 與代價敏感學(xué)習(xí)算法的對比實驗

本節(jié)將CAFS算法與代價敏感邏輯回歸算法（Cost Sensitive Logistic Regression algorithm， CSLR）[23]、代價敏感決策樹算法（Cost Sensitive Decision Tree algorithm， CSDT）[24]和代價敏感隨機森林算法（Cost Sensitive Random Forest algorithm， CSRF）[25]在9個公開數(shù)據(jù)集上進(jìn)行了對比，并以平均代價（根據(jù)式（7）計算）為唯一參照，結(jié)果如表4所示。其中“—”表示CSLR在Arcene數(shù)據(jù)集上運行超過5h也沒有產(chǎn)生結(jié)果;平均排名則指算法在所有數(shù)據(jù)集上表現(xiàn)排名的均值。從表4中看出，CAFS的平均代價相對于CSLR、CSDT、CSRF分別降低了56%、27%、32%。

5.4 與其他代價敏感主動學(xué)習(xí)算法的對比

本節(jié)實驗選取了5個代價敏感主動學(xué)習(xí)算法進(jìn)行比較。其中：ALCE（Active Learning Embed Cost algorithm）[25]為代價嵌入主動學(xué)習(xí)算法，CWMM（Cost Weight Minimum Margin algorithm）為代價權(quán)重最小邊緣算法，MEC（Maximum Expected Cost algorithm）為最大期望代價算法，TALK（Tri-partition Active Learning through K-nearest neighbors algorithm）為基于k近鄰的三支決策主動學(xué)習(xí)算法，CADU（Cost-sensitive Active learning algorithm with a label Uniform Distribution model）為基于密度聚類的代價敏感主動學(xué)習(xí)算法。

對ALCE、CWMM和MEC進(jìn)行了5次重復(fù)實驗，以保證實驗結(jié)果的準(zhǔn)確性;而且由于數(shù)據(jù)順序不影響TALK、CADU和CAFS的結(jié)果，即實驗的結(jié)果穩(wěn)定，所以只進(jìn)行1次實驗。其中CAFS和CADU不需要已經(jīng)標(biāo)記的初始訓(xùn)練集;而且采樣數(shù)目是CWMM和MEC的參數(shù)，為了保證實驗結(jié)果的有效性，將采樣數(shù)目設(shè)置為CAFS、TALK CADU的計算值。

表5顯示在9個數(shù)據(jù)集上，CAFS在大部分?jǐn)?shù)據(jù)集上表現(xiàn)優(yōu)異，其中平均代價相對于ALCE，CWMM，MEC，TALK，CADU算法分別降低了30%、37%、35%、27%、10%，在平均排名上也取得了最好的成績。

5.5 與非代價敏感學(xué)習(xí)算法的對比實驗

最后，為了實驗的完整性，CAFS與3個非代價敏感學(xué)習(xí)算法——投票熵采樣算法（Vote Entropy Sampling algorithm， VES）、一致熵采樣算法（Consensus Entropy Sampling algorithm， CES）和最大分歧采樣算法（Max Disagreement Sampling algorithm， MDS）進(jìn)行對比。三種算法選取了不同的采樣方案，其中VES是投票熵采樣算法，CES是一致熵采樣算法，MDS是最大分歧采樣算法，并且有3個基本分類器組成，分別是決策樹[26]、隨機森林[27]和帶徑向基函數(shù)（Radial Basis Function， RBF）內(nèi)核的支持向量機（Support Vector Machine， SVM）[28]。因為某些算法在單次實驗中會有結(jié)果的偏差，所以進(jìn)行了5次實驗。實驗結(jié)果如表6所示，由于非代價敏感學(xué)習(xí)算法不考慮代價因素，所以在為保證實驗結(jié)果的統(tǒng)一性，計算平均代價時會根據(jù)學(xué)習(xí)結(jié)果與代價設(shè)置進(jìn)行代價計算。由表6可以看出，CAFS算法在4個算法中平均排名最好，并且平均代價對應(yīng)于VES、CES、MDS算法分別降低了13.8%、14.34%、19.67%。

5.6 實驗結(jié)果分析

綜合以上實驗結(jié)果，有如下結(jié)論：

1）CAFS算法與主流的代價敏感學(xué)習(xí)CSLR、CSDT和CSRF相比，平均代價是最低的。

2）CAFS與同類的代價敏感主動學(xué)習(xí)算法CWMM、MEC、TALK和CADU相比，實驗結(jié)果是最優(yōu)的。

實驗結(jié)果表明CAFS算法能夠有效地降低總代價。

6 結(jié)語

本文提出的基于最遠(yuǎn)總距離采樣的主動學(xué)習(xí)算法，建立了LUD模型，并提出了最遠(yuǎn)總距離采樣的策略。利用3WD思想使得學(xué)習(xí)的過程更加完善。標(biāo)簽均勻分布模型在給定的代價以及假設(shè)的均勻分布的條件下，可獲得最優(yōu)的采樣數(shù)目。最遠(yuǎn)總距離采樣策略，綜合考慮了信息量和樣本的總體特性，使得選擇的樣本更具代表性。下一步的主要工作包含兩個方面：其一是將LUD模型推廣到多類別的學(xué)習(xí)任務(wù)中;其二是設(shè)計更加合適的樣本采樣策略，進(jìn)一步減小算法的代價，提高預(yù)測精度。

參考文獻(xiàn) （References）

[1]SETTLES B. Active learning [J]. Synthesis Lectures on Artificial Intelligence and Machine Learning， 2012， 6（1）： 1-114.

SETTLES B. Active Learning [M]. San Rafael， CA： Morgan and Claypool Publishers， 2012： 1-114.

[2]ZHU X， GOLDBERG A B. Introduction to Semi-Supervised Learning [M]. San Rafael， CA： Morgan and Claypool Publishers， 2009： 130.

[3]SEUNG H S， OPPER M， SOMPOLINSKY H. Query by committee [C]// COLT 1992： Proceedings of the 5th Annual ACM Conference on Computational Learning Theory. New York： ACM， 1992：287-294.

[4]COHN D A， GHAHRAMANI Z， JORDAN M I， et al. Active learning with statistical models [J]. Journal of Artificial Intelligence Research， 1996， 4（1）： 129-145.

[5]WANG M， MIN F， ZHANG Z H， et al. Active learning through density clustering [J]. Expert Systems with Applications， 2017， 85： 305-317.

[6]TONG S， KOLLER D. Support vector machine active learning with applications to text classification [J]. Journal of Machine Learning Research， 2001， 2（1）： 45-66.

[7]THOMPSON C A. Active learning for natural language parsing and information extraction[C]// ICML 1999： Proceeding of the 16th International Conference on Machine Learning. San Francisco， CA： Morgan Kaufmann Publishers， 1999： 406-414.

[8]ZHANG C， CHEN T. An active learning framework for content-based information retrieval [J]. IEEE Transactions on Multimedia， 2002， 4（2）： 260-268.

[9]YU D， VARADARAJAN B， DENG L， et al. Active learning and semi-supervised learning for speech recognition： a unified framework using the global entropy reduction maximization criterion [J]. Computer Speech and Language， 2010， 24（3）： 433-444.

[10]MARGINEANTU D D. Active cost-sensitive learning [C]// IJCAI 2005： Proceedings of the 19th International Joint Conference on Artificial Intelligence. San Francisco， CA： Morgan Kaufmann Publishers， 2005： 1622-1623.

[11]MIN F， LIU F L， WEN L Y， et al. Tri-partition cost-sensitive active learning through kNN [J]. Soft Computing， 2017， 23（5）： 1557-1572.

[12]WU Y X， MIN X Y， MIN F， et al. Cost-sensitive active learning with a label uniform distribution model [J]. International Journal of Approximate Reasoning， 2019， 105： 49-65.

[13]YAO Y. Three-way decision： an interpretation of rules in rough set theory [C]// Proceedings of the 2009 International Conference on Rough Sets and Knowledge Technology， LNCS 5589. Berlin： Springer， 2009： 642-649.

[14]李華雄，周獻(xiàn)中，黃兵，等.決策粗糙集與代價敏感分類[J].計算機科學(xué)與探索，2013，7（2）：126-135.（LI H X， ZHOU X Z， HUANG B， et al. Decision-theoretic rough set and cost-sensitive classification [J]. Journal of Frontiers of Computer Science and Technology， 2013， 7（2）： 126-135.）

[15]劉盾，李天瑞，李華雄.粗糙集理論：基于三支決策視角[J].南京大學(xué)學(xué)報（自然科學(xué)版），2013，49（5）：574-581. （LIU D， LI T R， LI H X. Rough set theory： a three-way decisions perspective [J]. Journal of Nanjing University （Natural Science）， 2013， 49（5）： 574-581）

[16]楊習(xí)貝，楊靜宇.鄰域系統(tǒng)粗糙集模型[J].南京理工大學(xué)報，2012，36（2）：291-295.（YANG X B， YANG J Y. Rough set model based on neighborhood system [J]. Journal of Nanjing University of Science and Technology， 2012， 36（2）： 291-295.）

[17]SETTLES B， CRAVEN M， Friedland L. Active learning with real annotation costs [C]// NIPS-CSL 2008： Proceedings of the NIPS workshop on cost-sensitive learning. Neural Information Processing Systems， 2008： 1-10.

SETTLES B， CRAVEN M， Friedland L. Active learning with real annotation costs [EB/OL]. [2018-12-13]. https：//www.researchgate.net/publication/228770726_Active_learning_with_real_annotation_costs.

[18]LIU A， JUN G， GHOSH J. Spatially cost-sensitive active learning [C]// SDM 2009： Proceedings of the 2009 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2009： 814-825.

[19]ZHAO P L， HOI S C H. Cost-sensitive online active learning with application to malicious URL detection [C]// KDD 2013： Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2013： 919-927.

[20]CHEN P-L， LIN H-T. Active learning for multiclass cost-sensitive classification using probabilistic models [C]// TAAI 2013： Proceedings of the 2013 Conference on Technologies and Applications of Artificial Intelligence. Washington， DC： IEEE Computer Society， 2013： 13-18.

[21]DEMIR B， MINELLO L， BRUZZONE L. Definition of effective training sets for supervised classification of remote sensing images by a novel cost-sensitive active learning method [J]. IEEE Transactions on Geoscience and Remote Sensing， 2014， 52（2）： 1272-1284.

[22]HUANG K-H， LIN H-T. A novel uncertainty sampling algorithm for cost-sensitive multiclass active learning [C]// ICDM 2016： Proceedings of the 2016 IEEE 16th International Conference on Data Ming. Piscataway， NJ： IEEE， 2016： 925-930.

[23]BAHNSEN A C， AOUADA D， OTTERSTEN B. Example-dependent cost-sensitive logistic regression for credit scoring [C]// ICMLA 2014： Proceedings of the 2014 13th International Conference on Machine Learning and Application. Washington， DC： IEEE Computer Society， 2014： 263-269.

[24]BAHNSEN A C， AOUADA D， OTTERSTEN B. Example-dependent cost-sensitive decision trees[J]. Expert Systems with Applications， 2015， 42（19）： 6609-6619.

[25]BAHNSEN A C， AOUADA D， OTTERSTEN B. Ensemble of example-dependent cost-sensitive decision trees [J]. arXiv preprint arXiv：1505.04637.

BAHNSEN A C， AOUADA D， OTTERSTEN B. Ensemble of example-dependent cost-sensitive decision trees [EB/OL]. [2018-12-13]. https：//arxiv.org/pdf/1505.04637v1.pdf.

[26]QUINLAN J R. Induction of decision trees [J]. Machine Learning， 1986， 1（1）： 81-106.

[27]LIAW A， WIENER M. Classification and regression by random forest [J]. R News， 2002， 2/3： 18-22.

[28]CRISTIANINI N， SHAWE T J. An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods [M]. Cambridge， Eng.： Cambridge University Press， 2000： 46-71.

This work is partially supported by the Scientific Innovation Group for Youths of Sichuan Province （2019JDTD0017）， the Applied Basic Research Project of Sichuan Province （2017JY0190）.

REN Jie， born in 1996， M. S. candidate. His research interests include active learning， data mining.

MIN Fan， born in 1973， Ph. D.， professor. His research interests include granular computing， recommender system， active learning.

WANG Min， born in 1980， M. S.， associate professor. Her research interests include data mining， active learning.