劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立?

齊志鑫,王宏志,周 雄,李建中,高 宏

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

分類是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中常見的一類任務(wù),該任務(wù)從訓(xùn)練數(shù)據(jù)中提取模型,再利用該模型預(yù)測未知的數(shù)據(jù)類別[1].目前,有很多用于完成分類任務(wù)的方法被提出,如決策樹[2]、貝葉斯網(wǎng)[3]、神經(jīng)網(wǎng)絡(luò)[4]、基于實例的推理[5]等.在這些方法中,決策樹憑借易解釋、計算效率高、能夠生成易理解的分類規(guī)則等優(yōu)勢得到了眾多關(guān)注,并被廣泛應(yīng)用于分類任務(wù)中[6].

起初,大量決策樹研究著眼于最大化分類準(zhǔn)確率或最小化分類誤差[7-9].然而,由于一個分類任務(wù)可能產(chǎn)生多種類型的代價,越來越多的研究工作關(guān)注于代價敏感決策樹的建立[10-12].在目前研究的代價類型中,兩種最常見的代價是誤分類代價和測試代價[13].誤分類代價是指一個屬于類j的實例被誤分類為類i的代價,而誤分類所產(chǎn)生的代價常常是不均衡的.例如,將一個病人診斷為健康的代價往往比將一個健康的人診斷為病人的代價大很多.除了誤分類代價,每一次測試也關(guān)聯(lián)著相應(yīng)的代價.例如在醫(yī)療診斷中,每一次血常規(guī)檢測都存在一個相關(guān)聯(lián)的代價[1].

現(xiàn)如今,隨著數(shù)據(jù)量急劇增長,劣質(zhì)數(shù)據(jù)的出現(xiàn)也愈發(fā)頻繁[14].在建立代價敏感決策樹時,訓(xùn)練數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)會對分裂屬性的選擇和決策樹結(jié)點(diǎn)的劃分造成一定的影響.因此在進(jìn)行分類任務(wù)前,需要提前對數(shù)據(jù)進(jìn)行劣質(zhì)數(shù)據(jù)清洗.然而在實際應(yīng)用中,由于數(shù)據(jù)清洗工作所需要的時間和金錢代價往往很高,許多用戶給出了自己可接受的數(shù)據(jù)清洗代價最大值,并要求將數(shù)據(jù)清洗的代價控制在這一閾值內(nèi)[15].因此,除了誤分類代價和測試代價以外,劣質(zhì)數(shù)據(jù)的清洗代價也是代價敏感決策樹建立過程中的一個重要因素.然而,現(xiàn)有代價敏感決策樹建立的相關(guān)研究沒有考慮數(shù)據(jù)質(zhì)量問題.為了彌補(bǔ)這一空缺,本文將劣質(zhì)數(shù)據(jù)的清洗代價納入代價敏感決策樹建立問題的考慮因素中,該問題帶來了以下挑戰(zhàn).

(1) 由于清洗后的數(shù)據(jù)將用于建立代價敏感決策樹,第 1個挑戰(zhàn)是如何將代價敏感決策樹的建立目標(biāo)融合到數(shù)據(jù)清洗方法中;

(2) 由于不同用戶設(shè)定的數(shù)據(jù)清洗代價閾值不同,不同數(shù)據(jù)集中劣質(zhì)數(shù)據(jù)所占比率不同,第 2個挑戰(zhàn)是針對不同的情況,如何選擇最優(yōu)的代價敏感決策樹建立方法.

鑒于這兩點(diǎn)挑戰(zhàn),本文從問題定義入手,將用戶設(shè)定的數(shù)據(jù)清洗代價閾值納入到代價敏感決策樹建立的問題中.然后,針對這一問題給出融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法.最后,測試改變用戶設(shè)定的數(shù)據(jù)清洗代價閾值或改變數(shù)據(jù)集中劣質(zhì)數(shù)據(jù)比率時不同方法的總代價、分類準(zhǔn)確率和效率,從而得出不同情況下最優(yōu)的代價敏感決策樹建立方法.本文的主要貢獻(xiàn)有以下幾點(diǎn).

(1) 研究了劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立問題,是目前首個考慮到代價敏感決策樹建立過程中的數(shù)據(jù)質(zhì)量問題的工作;

(2) 針對劣質(zhì)數(shù)據(jù)上的代價敏感決策樹建立問題,本文提出了 3種融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法,即融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法、融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法、融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法;

(3) 本文通過大量實驗驗證了所提出的3種代價敏感決策樹建立方法的總代價、分類準(zhǔn)確率和分類效率,并給出了不同情況下最優(yōu)的代價敏感決策樹建立方法.

本文第 1節(jié)對代價敏感決策樹建立問題相關(guān)的研究工作進(jìn)行總結(jié).第 2節(jié)對本文問題相關(guān)的定義進(jìn)行介紹.第3節(jié)對本文提出的3種融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法進(jìn)行詳細(xì)地闡述.第4節(jié)對本文的實驗評估過程和實驗結(jié)果進(jìn)行討論和分析,并給出實驗結(jié)論.第 5節(jié)總結(jié)全文,并對未來值得關(guān)注的研究方向進(jìn)行初步探討.

1 相關(guān)工作

目前,代價敏感決策樹建立問題的研究目標(biāo)主要包括3種:第1種是最小化決策樹的誤分類代價;第2種是最小化決策樹的測試代價;第 3種是最小化決策樹的誤分類代價和測試代價總和[13].本文選擇的研究目標(biāo)是第3種.

針對不同的問題目標(biāo),許多代價敏感決策樹建立方法被提出.這些方法可以分為兩大類.

· 第1類是采用貪心的方法來建立一棵單獨(dú)的決策樹,例如:CS-ID3算法[16]采用基于熵的選擇方法在決策樹建立過程中最小化代價,AUCSplit算法[17]在決策樹建立之后最小化代價;

· 第2類是非貪心的方法,該方法生成多個決策樹,例如遺傳算法ICET[18]、將現(xiàn)有基于準(zhǔn)確率的方法包裝在一起的MetaCost算法[19].

按照時間順序來看,Hunt等人首先發(fā)現(xiàn)了誤分類和測試對人們的決策存在一定的影響,并提出了概念學(xué)習(xí)系統(tǒng)框架[20].隨后,ID3算法[21]采用了概念學(xué)習(xí)系統(tǒng)框架的部分思想,并使用了信息論評估參數(shù)來選擇特征.在信息論方法被提出后,許多在決策樹建立過程中最小化代價的方法被陸續(xù)提出,如CS-ID3算法[16]、EG2算法[22].然后,在決策樹建立后最小化代價的方法被提出,如 AUCSplit算法[17].之后,遺傳方法如 ICET算法[18]、提升法如UBoost算法[23]、裝袋法如MetaCost算法[19]等被提出.隨后,多重結(jié)構(gòu)的方法如LazyTree算法[24]、隨機(jī)方法如ACT算法[25]、TATA算法[26]被陸續(xù)提出.

在最小化代價敏感決策樹的誤分類代價和測試代價的基礎(chǔ)上,有研究著眼于包含其他限制因素的代價敏感決策樹建立問題.例如:由于有些分類任務(wù)需要在規(guī)定的時間內(nèi)完成,在時間限制下的代價敏感決策樹建立方法被提出[1].有時用戶會對分類任務(wù)的準(zhǔn)確率提出預(yù)期的要求,因此面向用戶需求的代價敏感決策樹建立方法被提出[27].然而,目前并未有研究關(guān)注劣質(zhì)數(shù)據(jù)上的代價敏感決策樹建立.因此,本文將彌補(bǔ)這一空缺.

2 問題定義

本節(jié)將對劣質(zhì)數(shù)據(jù)上代價敏感決策樹建立問題的相關(guān)定義進(jìn)行介紹.

2.1 決策樹

決策樹T具有樹結(jié)構(gòu),是有向無環(huán)圖的一個特例.決策樹中包含根結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)和葉子結(jié)點(diǎn)的有限集合、連接兩個結(jié)點(diǎn)的邊的集合.圖1是決策樹的實例.

Fig.1 An instance of decision tree圖1 決策樹實例

如圖1所示,ni表示第i個結(jié)點(diǎn).如果ni是內(nèi)部結(jié)點(diǎn),那么該結(jié)點(diǎn)會關(guān)聯(lián)著屬性a(ni),a(ni)被稱為在結(jié)點(diǎn)ni中被用到的測試屬性.如果ni是葉子結(jié)點(diǎn),那么該結(jié)點(diǎn)關(guān)聯(lián)著一個類別標(biāo)簽值.本文用inter(T)表示T中所有內(nèi)部結(jié)點(diǎn)的集合,用leaf(T)表示T中所有葉子結(jié)點(diǎn)的集合,Ti表示T中根為ni的子樹.

本文用有序?qū)?ni,nj)表示決策樹中一條關(guān)聯(lián)著結(jié)點(diǎn)ni和nj的邊,其中,ni是nj的父結(jié)點(diǎn).當(dāng)ni是關(guān)聯(lián)測試屬性a(ni)的內(nèi)部結(jié)點(diǎn)時,邊(ni,nj)關(guān)聯(lián)一個單獨(dú)的值或一個值集合,這些值都是a(ni)可能的屬性值.決策樹中的一條路徑是邊的一個序列,本文用path(ni,nj)表示從ni到nj的路徑.假設(shè)ni到nj之間的序列是n1,n2,…,nm,那么path(ni,nj)={(ni,n1),(n1,n2),…,(nm,nj)},本文用n(ni,nj)={n1,n2,n3,…,nm}表示從ni到nj的路徑上所有中間結(jié)點(diǎn)的集合.

決策樹分類器通過在訓(xùn)練數(shù)據(jù)集D上學(xué)習(xí)構(gòu)建而成,dk表示D中的第k條記錄.每條記錄由屬性值集合和類別標(biāo)簽構(gòu)成.本文用a表示屬性值集合,ax表示a中的第x個屬性.表1是訓(xùn)練數(shù)據(jù)集的一個實例,每一條記錄由ID、5個屬性和1個類別標(biāo)簽組成.

Table 1 An instance of training dataset表1 訓(xùn)練數(shù)據(jù)集實例

本文用D(ni)表示D中屬性值遵循path(root,ni)中邊上屬性值的記錄集合,這說明D(ni)是滿足path(root,ni)上所有測試的記錄集合.D(root)表示整個訓(xùn)練數(shù)據(jù)集D,|D(ni)|表示D(ni)中的記錄個數(shù).根據(jù)表1中的訓(xùn)練數(shù)據(jù)集構(gòu)建的決策樹如圖2所示.

Fig.2 Decision tree trained by Table 1圖2 根據(jù)表1訓(xùn)練成的決策樹

2.2 誤分類代價和測試代價

誤分類代價是指一個屬于類j的實例被誤分類為類i的代價.假設(shè)訓(xùn)練數(shù)據(jù)集中有m個類別,那么誤分類代價矩陣可以用m×m的矩陣表示,見表2.本文用ClassCost(i,j)表示當(dāng)一個實例屬于類j時,將其誤分類為類i的代價.從表2可知,ClassCost(T,T)=0,ClassCost(T,F)=10,ClassCost(F,T)=20,ClassCost(F,F)=0.

Table 2 A matrix of misclassification costs表2 誤分類代價矩陣

當(dāng)為葉子結(jié)點(diǎn)分配一個標(biāo)簽時,可能會導(dǎo)致該葉子結(jié)點(diǎn)關(guān)聯(lián)的記錄產(chǎn)生一定的誤分類代價.因此,本文用ClassCost(ni,lj)表示給結(jié)點(diǎn)ni分配標(biāo)簽為lj的葉子結(jié)點(diǎn)時產(chǎn)生的誤分類代價,即:

例如,對于表1中的訓(xùn)練數(shù)據(jù),ClassCost(root,T)=0+10+10+0+0+10+10+10=50,ClassCost(root,F)=20+0+0+20+20+0+0+0=60.

本文用TestCost(ax)表示對屬性ax進(jìn)行測試所需要的代價,用ArrCost(ni,T)表示一條記錄從T的根結(jié)點(diǎn)到達(dá)ni所需的總測試代價,即.表1中屬性的測試代價見表3.從表3可知,ArrCost(n01,T)=4,ArrCost(n011,T)=4+6=10.

Table 3 TestCost of attributes表3 屬性的測試代價

每一條記錄都會經(jīng)過從決策樹根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的測試,因此,結(jié)點(diǎn)ni中的記錄到達(dá)ni所花費(fèi)的總測試代價為ArrCost(ni,T)×|D(ni)|.此外,ni獲得一個類別標(biāo)簽時會產(chǎn)生一定的誤分類代價.本文用NodeCost(ni)表示誤分類代價和測試代價的總代價.如果將結(jié)點(diǎn)ni作為一個葉子結(jié)點(diǎn),則

例如,對于圖2中的決策樹,NodeCost(root)=50+0×8=50,NodeCost(n01)=20+4×3=32.

圖2中其余結(jié)點(diǎn)的NodeCost值見表4.

Table 4 NodeCost of nodes表4 結(jié)點(diǎn)的NodeCost值

本文用TreeCost(T)表示決策樹T的總代價,即.例如,圖2中決策樹的總代價為TreeCost(T)=NodeCost(n011+n012+n021+n022+n03)=10+20+14+7+8=59.

2.3 檢測代價和修復(fù)代價

劣質(zhì)數(shù)據(jù)清洗工作往往由錯誤檢測和修復(fù)兩部分組成[28].在對訓(xùn)練數(shù)據(jù)集進(jìn)行清洗的過程中,首先需要對數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)進(jìn)行檢測,然后針對檢測到的劣質(zhì)數(shù)據(jù)進(jìn)行相應(yīng)的修復(fù).數(shù)據(jù)集中的每一個屬性都對應(yīng)著檢測該屬性值中可能存在的錯誤所需要花費(fèi)的代價和修復(fù)該屬性錯誤值所需要花費(fèi)的代價.

本文用DetCost(ax)表示對屬性ax中的每個值進(jìn)行錯誤檢測所需要花費(fèi)的代價.因此,對屬性ax中全部屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測所需要的代價是DetCost(ax)×|ax|.如果檢測到屬性ax中的劣質(zhì)數(shù)據(jù)個數(shù)為|Er(ax)|,那么對屬性ax中的全部劣質(zhì)數(shù)據(jù)值進(jìn)行修復(fù)所需要的代價是Rep(ax)×|Er(ax)|,其中,Rep(ax)是修復(fù)屬性ax中的每個劣質(zhì)數(shù)據(jù)值所需要的代價.在本文中,xd表示屬性ax中完成了劣質(zhì)數(shù)據(jù)檢測的屬性值個數(shù),xr表示屬性ax中完成了劣質(zhì)數(shù)據(jù)修復(fù)的屬性值個數(shù).然而在實際應(yīng)用中,由于數(shù)據(jù)清洗工作所需要的時間和金錢代價往往很高,許多用戶給出了自己可接受的數(shù)據(jù)清洗代價最大值.因此,本文用MaxCost表示用戶可接受的數(shù)據(jù)清洗代價閾值,并將數(shù)據(jù)清洗的代價控制在這一閾值內(nèi).

2.4 劣質(zhì)數(shù)據(jù)上代價敏感決策樹建立問題

給定一個訓(xùn)練數(shù)據(jù)集、用戶設(shè)定的數(shù)據(jù)清洗代價最大值、誤分類代價矩陣、每個屬性對應(yīng)的測試代價、檢測代價和修復(fù)代價,劣質(zhì)數(shù)據(jù)上代價敏感決策樹建立問題定義如下:基于訓(xùn)練數(shù)據(jù)集,建立一個代價敏感決策樹,使得該決策樹的誤分類代價和測試代價總和最小,且清洗該數(shù)據(jù)集的檢測代價和修復(fù)代價總和不超過用戶設(shè)定的數(shù)據(jù)清洗閾值.

該問題的形式化描述是已知訓(xùn)練數(shù)據(jù)集D,數(shù)據(jù)清洗代價最大值MaxCost,誤分類代價ClassCost(ni,lj),測試代價TestCost(ax),檢測代價DetCost(ax)和修復(fù)代價,建立T,使得:

其中,

3 融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法

為了解決劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立問題,本文提出了 3種融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法,即融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法、融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法和融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法.本節(jié)將分別對這 3種代價敏感決策樹建立方法進(jìn)行闡述,并對各個方法的適用情況進(jìn)行討論.

3.1 融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法

由于代價敏感決策樹的建立目標(biāo)是最小化誤分類代價和測試代價的總和,因此可以將誤分類代價和測試代價總和的減少程度作為決策樹分裂屬性選取的標(biāo)準(zhǔn).本文定義了分裂屬性收益的概念來表示誤分類代價和測試代價總和的減少程度.

本文用Benefit(ax,ni)表示用屬性ax分裂結(jié)點(diǎn)ni的收益,結(jié)點(diǎn)ni會被分裂為若干個孩子結(jié)點(diǎn).分裂屬性收益Benefit(ax,ni)定義為

例如在圖2中,NodeCost(n01)=32,NodeCost(n011)=10,NodeCost(n012)=20.因此,Benefit(a2,n01)=32-(10+20)=2.

融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法的過程如下:在決策樹建立的每一步中,選擇收益最大的分裂屬性;先對該分裂屬性中的值進(jìn)行劣質(zhì)數(shù)據(jù)檢測和修復(fù),再將該屬性用于決策樹的分裂過程中;當(dāng)所花費(fèi)的清洗代價達(dá)到用戶設(shè)定的最大值后,不再對后續(xù)的分裂屬性進(jìn)行清洗,直接用于決策樹的分裂過程中;當(dāng)結(jié)點(diǎn)中所有記錄所對應(yīng)的類別標(biāo)簽相同,或沒有分裂屬性的收益為正值時不再對該結(jié)點(diǎn)進(jìn)行分裂,將其標(biāo)記為葉子結(jié)點(diǎn),其類別標(biāo)簽為使得誤分類代價最小的類別.

上述過程中,基于分裂屬性收益的分步清洗算法見算法1.算法的輸入是待清洗的訓(xùn)練數(shù)據(jù)集、用戶給定的清洗代價閾值、數(shù)據(jù)集中每個屬性對應(yīng)的劣質(zhì)數(shù)據(jù)檢測代價和修復(fù)代價.首先,對根結(jié)點(diǎn)的分裂屬性收益進(jìn)行計算,選取收益最大的屬性作為分裂屬性(第1行～第5行).對該屬性中的屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測和修復(fù),并計算剩余的清洗代價是否足夠?qū)τ?xùn)練數(shù)據(jù)集中該屬性的全部屬性值進(jìn)行檢測:如果足夠,那么對該屬性的所有屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測(第 6行～第 9行);如果不足夠,那么對該屬性部分屬性值進(jìn)行檢測(第 10行～第 14行).在檢測出分裂屬性中包含的劣質(zhì)數(shù)據(jù)后,對劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù),并計算剩余的清洗代價是否足夠?qū)θ苛淤|(zhì)數(shù)據(jù)進(jìn)行修復(fù):如果足夠,那么對該屬性中包含的所有劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù)(第15行～第17行);如果不足夠,那么對部分劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù)(第18行～第21行).然后,繼續(xù)為下一個結(jié)點(diǎn)尋找分裂屬性并清洗(第22行).當(dāng)清洗代價達(dá)到用戶給定的閾值或決策樹中全部結(jié)點(diǎn)都被清洗完畢后,返回清洗后的訓(xùn)練數(shù)據(jù)集(第23行).

算法1.基于分裂屬性收益的分步清洗算法.

輸入:訓(xùn)練數(shù)據(jù)集Dm×n,清洗代價閾值 MaxCost,每個屬性x∈{1,2,…,n}的劣質(zhì)數(shù)據(jù)檢測代價Det(ax)和修復(fù)代價Rep(ax);

輸出:清洗后的訓(xùn)練數(shù)據(jù)集Dm×n.

算法1的時間復(fù)雜度取決于決策樹中的結(jié)點(diǎn)個數(shù)N、訓(xùn)練數(shù)據(jù)集中的屬性個數(shù)n和記錄個數(shù)m.假設(shè)劣質(zhì)數(shù)據(jù)檢測函數(shù)Detect(x)的時間復(fù)雜度為O(f(x)),劣質(zhì)數(shù)據(jù)修復(fù)函數(shù)Repair(x)的時間復(fù)雜度為O(g(x)),當(dāng)max(f(x),g(x))≥nlogn時,算法1的時間復(fù)雜度是O(Nmax(f(x),g(x)));當(dāng)max(f(x),g(x))

融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法盡可能地將代價敏感決策樹中前幾層的分裂屬性進(jìn)行清洗后再用于分裂過程.由于決策樹中層次低的分裂結(jié)點(diǎn)重要性高于層數(shù)高的分裂結(jié)點(diǎn),所以該方法保證了決策樹結(jié)點(diǎn)分裂的有效性,有效降低了決策樹的誤分類代價和測試代價總和,使得決策樹在后續(xù)的分類任務(wù)中受訓(xùn)練數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)影響較小.然而,當(dāng)用戶設(shè)定的清洗代價閾值較小時,該方法可能會對清洗代價高的屬性優(yōu)先進(jìn)行清洗,使得能夠被清洗到的屬性個數(shù)較少,從而導(dǎo)致在這種情況下,該方法對劣質(zhì)數(shù)據(jù)的清洗效果不大.

3.2 融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法

為了解決融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法所存在的問題,本文將數(shù)據(jù)清洗代價考慮到數(shù)據(jù)清洗算法中,希望選擇收益高且清洗代價低的屬性優(yōu)先進(jìn)行清洗.本文定義了收益與清洗代價比來平衡分裂屬性收益和清洗代價這兩個沖突的因素,即Benefit(ax,n0)/(Det(ax)+Rep(ax)),其中,Benefit(ax,n0)是屬性ax在決策樹根結(jié)點(diǎn)n0時的分裂屬性收益,Det(ax)和Rep(ax)分別是對屬性ax的每個屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測和修復(fù)的代價.

融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法的過程如下:將訓(xùn)練數(shù)據(jù)集中的各個屬性按照收益與清洗代價比進(jìn)行排序,按照順序進(jìn)行一次性數(shù)據(jù)清洗.在每一次選擇分裂屬性時,對每個屬性重新計算分裂屬性收益Benefit(ax,n0),選擇收益最大的屬性作為分裂屬性.當(dāng)結(jié)點(diǎn)中所有記錄所對應(yīng)的類別標(biāo)簽相同,或沒有分裂屬性的收益為正值時停止對該結(jié)點(diǎn)的分裂,將其標(biāo)記為葉子結(jié)點(diǎn),其類別標(biāo)簽為使得誤分類代價最小的類別.

上述過程中基于分裂屬性收益和清洗代價的一次性清洗算法見算法 2.算法的輸入是待清洗的訓(xùn)練數(shù)據(jù)集、用戶給定的清洗代價閾值、數(shù)據(jù)集中每個屬性對應(yīng)的劣質(zhì)數(shù)據(jù)檢測代價和修復(fù)代價.首先,對每個屬性在根結(jié)點(diǎn)的收益與清洗代價比從大到小排序(第1行～第4行).按照順序選取屬性進(jìn)行劣質(zhì)數(shù)據(jù)檢測和修復(fù)(第5行、第6行).計算剩余的清洗代價是否足夠?qū)τ?xùn)練數(shù)據(jù)集中該屬性的全部屬性值進(jìn)行檢測:如果足夠,那么對該屬性的所有屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測(第7行～第10行);如果不足夠,那么對該屬性部分屬性值進(jìn)行檢測(第11行～第15行).在檢測出分裂屬性中包含的劣質(zhì)數(shù)據(jù)后,對劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù),并計算剩余的清洗代價是否足夠?qū)θ苛淤|(zhì)數(shù)據(jù)進(jìn)行修復(fù):如果足夠,那么對該屬性中包含的所有劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù)(第16行～第18行);如果不足夠,那么對部分劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù)(第19行～第22行).然后,按照順序?qū)ο乱粋€屬性進(jìn)行清洗(第23行).當(dāng)清洗代價達(dá)到用戶給定的閾值或全部屬性都被清洗完畢后,返回清洗后的訓(xùn)練數(shù)據(jù)集(第24行).

算法2.基于分裂屬性收益和清洗代價的一次性清洗算法.

輸入:訓(xùn)練數(shù)據(jù)集Dm×n,清洗代價閾值MaxCost,每個屬性x∈{1,2,…,n}的劣質(zhì)數(shù)據(jù)檢測代價Det(ax)和修復(fù)代價Rep(ax);

輸出:清洗后的訓(xùn)練數(shù)據(jù)集Dm×n.

算法 2的時間復(fù)雜度取決于訓(xùn)練數(shù)據(jù)集中的屬性個數(shù)n和記錄個數(shù)m.假設(shè)劣質(zhì)數(shù)據(jù)檢測函數(shù)Detect(x)的時間復(fù)雜度為O(f(x)),劣質(zhì)數(shù)據(jù)修復(fù)函數(shù)Repair(x)的時間復(fù)雜度為O(g(x)),算法 2的時間復(fù)雜度是O(nlogn×max(f(x),g(x))).

融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法盡可能地優(yōu)先清洗收益大且清洗代價小的屬性.該方法提前將數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)清洗完畢,使得在決策樹建立過程中能夠直接利用清洗后的屬性收益選取分裂屬性,很大程度上降低了劣質(zhì)數(shù)據(jù)對決策樹的影響.此外,該方法采用一次性清洗策略,與分步清洗策略相比節(jié)約了時間.然而,該方法一次性清洗到的屬性不一定都會在后續(xù)的決策樹建立過程中被選作分裂屬性.因此,在劣質(zhì)數(shù)據(jù)比例較大的情況下,該方法可能沒有清洗到?jīng)Q策樹建立過程中的某些分裂屬性,導(dǎo)致數(shù)據(jù)清洗過程對分類任務(wù)的作用不大.

3.3 融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法

為了解決融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法所存在的問題,本文提出了融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法.該方法的過程如下:在決策樹建立的每一步中,選擇收益與清洗比最大的分裂屬性;對該屬性中的值進(jìn)行劣質(zhì)數(shù)據(jù)檢測和修復(fù),再將該屬性用于決策樹的分裂過程中;所花費(fèi)的清洗代價達(dá)到了用戶設(shè)定的代價閾值時,不再對后續(xù)的分裂屬性進(jìn)行清洗;結(jié)點(diǎn)中所有記錄所對應(yīng)的類別標(biāo)簽相同,或沒有分裂屬性的收益為正值時,停止對該結(jié)點(diǎn)的分裂,將其標(biāo)記為葉子結(jié)點(diǎn),其類別標(biāo)簽為使得誤分類代價最小的類別.

上述過程中,基于分裂屬性收益和清洗代價的分步清洗算法見算法3.算法的輸入是待清洗的訓(xùn)練數(shù)據(jù)集、用戶給定的清洗代價閾值、數(shù)據(jù)集中每個屬性對應(yīng)的劣質(zhì)數(shù)據(jù)檢測代價和修復(fù)代價.

首先,對根結(jié)點(diǎn)的收益與清洗代價比進(jìn)行計算,選取比值最大的屬性作為分裂屬性(第1行～第5行).對該屬性中的屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測和修復(fù),計算剩余的清洗代價是否足夠?qū)τ?xùn)練數(shù)據(jù)集中該屬性的全部屬性值進(jìn)行檢測:如果足夠,那么對該屬性的所有屬性值進(jìn)行劣質(zhì)數(shù)據(jù)檢測(第6行～第9行);如果不足夠,那么對該屬性部分屬性值進(jìn)行檢測(第10行～第14行).在檢測出分裂屬性中包含的劣質(zhì)數(shù)據(jù)后,對劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù),并計算剩余的清洗代價是否足夠?qū)θ苛淤|(zhì)數(shù)據(jù)進(jìn)行修復(fù):如果足夠,那么對該屬性中包含的所有劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù)(第15行～第17行);如果不足夠,那么對部分劣質(zhì)數(shù)據(jù)進(jìn)行修復(fù)(第18行～第21行).然后,繼續(xù)為下一個結(jié)點(diǎn)尋找分裂屬性并清洗(第 22行).當(dāng)清洗代價達(dá)到用戶給定的閾值或決策樹中全部結(jié)點(diǎn)都被清洗完畢后,返回清洗后的訓(xùn)練數(shù)據(jù)集(第23行).

算法3.基于分裂屬性收益和清洗代價的分步清洗算法.

輸入:訓(xùn)練數(shù)據(jù)集Dm×n,清洗代價閾值MaxCost,每個屬性x∈{1,2,…,n}的劣質(zhì)數(shù)據(jù)檢測代價Det(ax)和修復(fù)代價Rep(ax);

輸出:清洗后的訓(xùn)練數(shù)據(jù)集Dm×n.

算法3的時間復(fù)雜度取決于決策樹中的結(jié)點(diǎn)個數(shù)N、訓(xùn)練數(shù)據(jù)集中的屬性個數(shù)n和記錄個數(shù)m.假設(shè)劣質(zhì)數(shù)據(jù)檢測函數(shù)Detect(x)的時間復(fù)雜度為O(f(x)),劣質(zhì)數(shù)據(jù)修復(fù)函數(shù)Repair(x)的時間復(fù)雜度為O(g(x)),當(dāng)max(f(x),g(x))≥nlogn時,算法3的時間復(fù)雜度是O(Nmax(f(x),g(x)));當(dāng)max(f(x),g(x))

融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法將收益大且清洗代價小的屬性選為分裂屬性并優(yōu)先進(jìn)行清洗.在決策樹建立的每一步中,分裂屬性被清洗完畢后再用于分裂.由于決策樹中層數(shù)低的分裂結(jié)點(diǎn)重要性高于層數(shù)高的分裂結(jié)點(diǎn),該方法保證了決策樹結(jié)點(diǎn)分裂的有效性,有效降低了決策樹的誤分類代價和測試代價總和,使得決策樹在后續(xù)的分類任務(wù)中受訓(xùn)練數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)影響較小.

3.4 適用情況討論和時間復(fù)雜度比較

當(dāng)用戶設(shè)定的數(shù)據(jù)清洗代價閾值較小時,融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法可能會對清洗代價高的屬性優(yōu)先進(jìn)行清洗,使得能夠被清洗到的屬性個數(shù)較少,對劣質(zhì)數(shù)據(jù)的清洗效果不大.因此,該方法不適用于這種情況.而融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法優(yōu)先對收益大且清洗代價小的屬性進(jìn)行清洗,避免了優(yōu)先清洗代價高的屬性,保證了數(shù)據(jù)清洗的效果和決策樹結(jié)點(diǎn)分裂的有效性.因此,該方法適用于這種情況.

當(dāng)劣質(zhì)數(shù)據(jù)比例較大時,融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法一次性清洗到的屬性不一定都會在后續(xù)的決策樹建立過程中被選作分裂屬性.該方法可能沒有清洗到?jīng)Q策樹建立過程中的某些分裂屬性,導(dǎo)致數(shù)據(jù)清洗過程對分類任務(wù)的作用不大.因此,該方法不適用于這種情況.而融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法在決策樹建立的每一步中選擇分裂屬性,將其清洗完畢后再用于分裂.該方法保證了數(shù)據(jù)清洗的效果和決策樹結(jié)點(diǎn)分裂的有效性,有效降低了決策樹的誤分類代價和測試代價總和,使得決策樹在后續(xù)的分類任務(wù)中受訓(xùn)練數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)影響較小.因此,該方法適用于這種情況.

此外,為了方便讀者選擇最適合的數(shù)據(jù)清洗算法完成劣質(zhì)數(shù)據(jù)上的代價敏感決策樹建立,表5從時間復(fù)雜度方面對本文所提出的3種清洗算法進(jìn)行了比較,時間復(fù)雜度分析的詳細(xì)過程參見本文第3.1節(jié)～第3.3節(jié).

Table 5 Comparison of time complexity of three algorithms表5 3種算法的時間復(fù)雜度比較

4 實驗評估

為了驗證所提出方法的性能,本文從3個方面對所提出的3種融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法進(jìn)行了測試:(1) 利用本文所提出的方法建立的代價敏感決策樹用于分類時產(chǎn)生的誤分類代價和測試代價總和;(2) 利用本文所提出的方法建立的代價敏感決策樹的分類準(zhǔn)確率;(3) 利用本文所提出的方法建立的代價敏感決策樹的分類效率.

本實驗使用的數(shù)據(jù)集是UCI公測集上的6個經(jīng)典數(shù)據(jù)集,其基本信息見表6.在實驗過程中,本文選用了劣質(zhì)數(shù)據(jù)中的不一致數(shù)據(jù)進(jìn)行實驗,根據(jù)在不同數(shù)據(jù)集上定義的函數(shù)依賴,向訓(xùn)練數(shù)據(jù)集中人為注入錯誤.本實驗采用10折交叉驗證方法,隨機(jī)生成訓(xùn)練集和測試集,并將在測試集上進(jìn)行分類任務(wù)的結(jié)果取平均值作為最終的實驗結(jié)果.

Table 6 Datasets information表6 數(shù)據(jù)集信息

所有實驗均在因特爾i7CPU@2.4GHz,8GB內(nèi)存,1TB硬盤的電腦上完成,所有算法均用Python語言編寫.

本實驗分別對以下4種代價敏感決策樹進(jìn)行了評估和比較.

(1) T1:隨機(jī)對訓(xùn)練數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)進(jìn)行清洗,再根據(jù)分裂屬性收益建立的代價敏感決策樹;

(2) T2:采用融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹;

(3) T3:采用融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹;

(4) T4:采用融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹.

4.1 分類任務(wù)產(chǎn)生的總代價

為了驗證所提出的代價敏感決策樹建立方法的有效性,本文對上述 4種代價敏感決策樹用于分類任務(wù)時產(chǎn)生的誤分類代價和測試代價總和(即TreeCost)進(jìn)行了比較.首先,通過改變用戶給定的清洗代價最大值,測試分類任務(wù)產(chǎn)生的總代價所發(fā)生的變化.實驗結(jié)果如圖3所示.

Fig.3 Comparison experiments varying MaxCost圖3 改變MaxCost值時的對比實驗

從圖3中能夠觀察到,決策樹T2和T4的總代價始終小于T1和T3,而T3的總代價往往小于T1.此外,從圖3(a)、圖3(d)～圖3(f)中可以看出:當(dāng)用戶設(shè)定的清洗代價最大值MaxCost≤40%時,決策樹T4的總代價小于T2;當(dāng) MaxCost>40%時,T2的總代價小于 T4.在圖3(b)和圖3(c)中,當(dāng) MaxCost≤50%時, T4的總代價小于 T2;當(dāng)MaxCost>50%時,T2的總代價小于 T4.這是由于當(dāng)用戶給定的清洗代價較高時,只考慮分裂屬性收益而不考慮清洗代價,也能夠清洗到較多的分裂屬性;而當(dāng)用戶給定的清洗代價較低時,如果不考慮屬性對應(yīng)的清洗代價,可能會優(yōu)先清洗收益高但清洗代價也高的分裂屬性,導(dǎo)致總清洗代價很快被用完,而能夠被清洗的分裂屬性卻很有限,從而影響了代價敏感決策樹的總代價.

因此可以得出結(jié)論:當(dāng)用戶設(shè)定的清洗代價最大值較小時,代價敏感決策樹 T4的總代價最小,即采用融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹最優(yōu);當(dāng)用戶設(shè)定的清洗代價最大值較大時,代價敏感決策樹T2的總代價最小,即采用融合基于分裂屬性收益的分步清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹最優(yōu).

此外,沒有進(jìn)行數(shù)據(jù)清洗而直接構(gòu)建的代價敏感決策樹的總代價明顯高于融合數(shù)據(jù)清洗方法構(gòu)建的代價敏感決策樹.由此可知,采用融合數(shù)據(jù)清洗的代價敏感決策樹建立方法大幅度節(jié)省了誤分類代價和測試代價.因此,數(shù)據(jù)清洗過程對于劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立是十分必要的.

然后,本文通過改變訓(xùn)練數(shù)據(jù)集中的錯誤率來評估分類任務(wù)產(chǎn)生的總代價所發(fā)生的變化.實驗結(jié)果如圖4所示.

Fig.4 Comparison experiments varying error rate圖4 改變錯誤率時的對比實驗

從圖4中能夠觀察到:決策樹T3和T4的總代價始終小于T1和T2,而T2的總代價往往小于T1.此外,從圖4(a)、圖4(c)～圖4(e)中可以看出:當(dāng)訓(xùn)練數(shù)據(jù)集中的錯誤率小于等于40%時,決策樹T3的總代價小于T4;當(dāng)錯誤率大于40%時,T4的總代價小于T3.在圖4(b)和圖4(f)中,當(dāng)錯誤率小于等于30%時,T3的總代價小于T4;當(dāng)錯誤率值大于30%時,T4的總代價小于T3.這是由于決策樹T3用到的一次性清洗算法并不能保證清洗到的屬性在建立決策樹的過程中被選做分裂屬性.在訓(xùn)練數(shù)據(jù)集錯誤率較高的時候,可能導(dǎo)致許多存在劣質(zhì)數(shù)據(jù)的分裂屬性并沒有被清洗到,從而影響了代價敏感決策樹分類時的總代價.

此外,通過圖4可以看出:當(dāng)錯誤率上升時,總代價也不斷增大.這是由于訓(xùn)練數(shù)據(jù)集中的劣質(zhì)數(shù)據(jù)增多,使得代價敏感決策樹的結(jié)構(gòu)更加復(fù)雜,結(jié)點(diǎn)數(shù)目增加,相應(yīng)地,測試代價增大,總代價增大.

因此可以得出結(jié)論:當(dāng)錯誤率較小時,代價敏感決策樹 T3的總代價最小,即采用融合基于分裂屬性收益和清洗代價的一次性清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹最優(yōu);當(dāng)錯誤率較大時,代價敏感決策樹T4的總代價最小,即采用融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹最優(yōu).

綜上所述,當(dāng)錯誤率較大,而用戶設(shè)定的清洗代價最大值較小時,代價敏感決策樹 T4的總代價最小,即采用融合基于分裂屬性收益和清洗代價的分步清洗算法的代價敏感決策樹建立方法建立的代價敏感決策樹最優(yōu).

4.2 分類任務(wù)的準(zhǔn)確率

為驗證所提出的代價敏感決策樹建立方法的有效性,本文對 4種代價敏感決策樹的分類準(zhǔn)確率進(jìn)行了比較.實驗結(jié)果見表7,其中,MaxCost為0%的情況表示沒有對劣質(zhì)數(shù)據(jù)進(jìn)行清洗,直接構(gòu)建代價敏感決策樹.

Table 7 Experimental results of classification accuracy表7 分類準(zhǔn)確率的實驗結(jié)果

從表7可以看出,代價敏感決策樹T1～ T4在分類準(zhǔn)確率上相差極小.因此,在選擇代價敏感決策樹建立方法時,可以不必將分類準(zhǔn)確率作為考慮因素.此外,沒有進(jìn)行數(shù)據(jù)清洗而直接構(gòu)建的代價敏感決策樹(即 MaxCost為0%)的分類準(zhǔn)確率比融合數(shù)據(jù)清洗方法構(gòu)建的代價敏感決策樹至少低7.23%(根據(jù)表7中的平均值計算).由此可知,采用融合數(shù)據(jù)清洗的代價敏感決策樹建立方法能夠有效提高決策樹的分類質(zhì)量.因此,數(shù)據(jù)清洗過程對于劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立是十分必要的.

4.3 分類任務(wù)的效率

為了驗證所提出的代價敏感決策樹建立方法的有效性,本文對 4種代價敏感決策樹的分類效率進(jìn)行了比較.實驗結(jié)果見表8.從表8可以看出,代價敏感決策樹T1～T4在分類效率上相差極小.因此,在選擇代價敏感決策樹建立方法時,可以不必將分類效率作為考慮因素.

Table 8 Experimental results of classification efficiency (ms)表8 分類效率的實驗結(jié)果 (毫秒)

Table 8 Experimental results of classification efficiency (Continued) (ms)表8 分類效率的實驗結(jié)果(續(xù)) (毫秒)

綜合上述實驗,本文對所提出的 3種代價敏感決策樹建立方法進(jìn)行了充分地比較.根據(jù)實驗結(jié)果,3種方法的具體適用情況見表9.

Table 9 Applicable conditions of three methods表9 3種方法的適用情況

5 結(jié) 論

本文研究了劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立問題.首先對決策樹、誤分類代價、測試代價、檢測代價和修復(fù)代價等相關(guān)概念進(jìn)行了介紹,并對本文的研究問題進(jìn)行了定義;然后,本文提出了3種融合數(shù)據(jù)清洗算法的代價敏感決策樹建立方法;最后,本文通過大量實驗驗證了 3種方法的總代價、分類準(zhǔn)確率和分類效率,并給出了不同情況下最優(yōu)的代價敏感決策樹建立方法.