基于最遠(yuǎn)總距離采樣的代價(jià)敏感主動(dòng)學(xué)習(xí)

任杰 閔帆 汪敏

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

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

中圖分類號(hà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 引言

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 三支決策

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

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

1.2 代價(jià)敏感主動(dòng)學(xué)習(xí)

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

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

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

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

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

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

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

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

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ù)抽出正例或反例時(shí)候，出現(xiàn)另一個(gè)對(duì)立的實(shí)例對(duì)于期望的影響很大，有如下公式成立：

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

2 代價(jià)敏感主動(dòng)學(xué)習(xí)問題描述

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

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

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

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

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

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

2.2 問題定義

問題1 代價(jià)敏感主動(dòng)學(xué)習(xí)。

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

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

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

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

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

3 CAFS算法

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

3.1 算法框架

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

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

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

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

有序號(hào)的程序——————————Shift+Alt+Y

程序前

1）

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

2）

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

3）

if（ySLf== y0）/*判斷最遠(yuǎn)的代表樣本點(diǎn)是否與初始樣本點(diǎ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模型計(jì)算要查詢標(biāo)簽個(gè)數(shù)的lookup方法，其中f是根據(jù)LUD模型以及代價(jià)函數(shù)所確定的正反例期望查詢數(shù)目，如式（6）所示：

f=

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

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

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

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

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

有序號(hào)的程序——————————Shift+Alt+Y

程序前

1）

for（xi∈X）

2）

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

3）

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

4）

end for

5）

i* ← lookup（y0）

6）

s ← （i*-SL.legth）

7）

return s

程序后

算法3介紹塊分裂條件以及如何迭代學(xué)習(xí)的過程。在選取最遠(yuǎn)總距離代表點(diǎn)后，需要得知該代表點(diǎ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ù)測(cè)標(biāo)簽合集li∈X。

有序號(hào)的程序——————————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時(shí)間復(fù)雜度分析

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

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

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

4 CAFS運(yùn)行實(shí)例

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

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

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

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

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

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

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

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

5.2 實(shí)驗(yàn)代價(jià)設(shè)置

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

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

其中：M1實(shí)驗(yàn)結(jié)果中將正例預(yù)測(cè)成反例的個(gè)數(shù)，M2為將反例預(yù)測(cè)成正例的個(gè)數(shù)，T為向?qū)＜也樵儗?shí)例的個(gè)數(shù)。

5.3 與代價(jià)敏感學(xué)習(xí)算法的對(duì)比實(shí)驗(yàn)

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

5.4 與其他代價(jià)敏感主動(dòng)學(xué)習(xí)算法的對(duì)比

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

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

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

5.5 與非代價(jià)敏感學(xué)習(xí)算法的對(duì)比實(shí)驗(yàn)

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

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

綜合以上實(shí)驗(yàn)結(jié)果，有如下結(jié)論：

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

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

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

6 結(jié)語

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

參考文獻(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)中，黃兵，等.決策粗糙集與代價(jià)敏感分類[J].計(jì)算機(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é)報(bào)（自然科學(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é)報(bào)，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.