基于多目標(biāo)最優(yōu)化的最小代價(jià)決策樹(shù)構(gòu)建與實(shí)現(xiàn)?

曹禮園 李深洛

（1.廣東科技學(xué)院 東莞 523083）（2.廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院 桂林 541004）

1 引言

確定挖掘方法、選擇挖掘?qū)ο蠹昂侠矶x挖掘約束是數(shù)據(jù)挖掘要面對(duì)三大難題，其中，挖掘方法的確定至關(guān)重要，而事選將問(wèn)題進(jìn)行分類(lèi)無(wú)疑大大簡(jiǎn)化確定挖掘方法程序。分類(lèi)器的構(gòu)建是分類(lèi)的主要程序，分類(lèi)器，通常是一個(gè)分類(lèi)函數(shù)或分類(lèi)模型，分類(lèi)器能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)映射到大數(shù)據(jù)庫(kù)里給定類(lèi)別中的某個(gè)最佳類(lèi)別。

決策樹(shù)（Decision Tree）應(yīng)用非常廣泛。本研究在構(gòu)建決策樹(shù)的過(guò)程中把誤分類(lèi)代價(jià)、測(cè)試代價(jià)、等待時(shí)間代價(jià)和信息增益率構(gòu)建最優(yōu)化問(wèn)題，作為屬性選擇的準(zhǔn)則，從而構(gòu)建最小代價(jià)決策樹(shù)。然后，對(duì)于有缺失值的數(shù)據(jù)，提出了具體的構(gòu)樹(shù)策略和測(cè)試策略。

2 構(gòu)建決策樹(shù)

相對(duì)傳統(tǒng)決策樹(shù)通常構(gòu)準(zhǔn)確率最高的決策樹(shù)，代價(jià)敏感決策樹(shù)構(gòu)造代價(jià)最小的決策樹(shù)。假設(shè)訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)都含有缺失值，我們的構(gòu)建決策樹(shù)包括以下三個(gè)步驟：1）選擇分列屬性；2）建立代價(jià)敏感決策樹(shù)；3）測(cè)試決策樹(shù)。

2.1 代價(jià)的定義

文獻(xiàn)［1］總結(jié)出9種主要的代價(jià)，它們是Cost of Misclassification Errors、Cost of Tests、Cost of Teacher、Cost of Intervention、Cost of Unwanted Achievements、Cost of Computation、Cost of Cases、Human-Computer Interaction Cost和 Cost of Instabili?ty。本文主要考慮測(cè)試代價(jià)、等待時(shí)間代價(jià)及誤分類(lèi)代價(jià)這三種代價(jià)。

1）誤分類(lèi)代價(jià)（MC）

誤分類(lèi)代價(jià)：由錯(cuò)誤的分類(lèi)而引發(fā)的懲罰代價(jià)。對(duì)于類(lèi)別標(biāo)簽為i的某一類(lèi)，其預(yù)測(cè)類(lèi)別為j，則誤分類(lèi)代價(jià)為 MCi，j，其中 MCi，j∈[0 ，+∞ ) 。在構(gòu)樹(shù)過(guò)程中，選擇屬性A作為分裂屬性，則其所引起的誤分類(lèi)代價(jià)為MC(A )，其中MC∈[0 ，+∞ )。

2）測(cè)試代價(jià)（TC）

測(cè)試代價(jià)：是獲取屬性值測(cè)試所需要的花費(fèi)，由所處理數(shù)據(jù)的領(lǐng)域提供。實(shí)際應(yīng)用中，測(cè)試代價(jià)要復(fù)雜得多，獲取屬性A的值，其測(cè)試代價(jià)為T(mén)C(A)，實(shí)際的值由領(lǐng)域?qū)＜医o出。

3）等待時(shí)間代價(jià)（WC）

等待時(shí)間代價(jià)：獲取屬性值等待測(cè)試結(jié)果所引發(fā)的代價(jià)。如果某屬性A的測(cè)試一定要等待另一個(gè)屬性B的結(jié)果出來(lái)才可以進(jìn)行，則屬性A等待時(shí)間代價(jià)與屬性B的等待時(shí)間代價(jià)相關(guān)，我們稱屬性B為屬性A的先驗(yàn)屬性。

等待代價(jià)并非一成不變，不同情境，不同的人群，即使是同一個(gè)測(cè)試，等待代價(jià)也可能是不一樣的。

因此，對(duì)于測(cè)試屬性A，其等待時(shí)間代價(jià)可以定義為WC(A)=WCT(A)⊕WCT(B)⊕WCS(A)，其中，WCT(A)表示測(cè)試屬性 A的實(shí)際的等待時(shí)間，WCT(B)表示屬性A的先驗(yàn)屬性B的實(shí)際等待時(shí)間，WCS(A)表示由于測(cè)試對(duì)象、資源等因素差異而引起的等待時(shí)間代價(jià)，WCS(A)由領(lǐng)域?qū)＜掖_定。因?yàn)閃CT(A)、WCT(B)和WCS(A)的度量標(biāo)準(zhǔn)不一樣，所以不能簡(jiǎn)單地相加，必須統(tǒng)一度量標(biāo)準(zhǔn)。在我們的定義中，用⊕連接WCT(A)、WCT(B)和WCS(A)，表示W(wǎng)C(A)是由這三者決定的。

2.2 分裂屬性的選擇

給定一個(gè)訓(xùn)練集 S={xn，yn}，n=1，…，N ；其中 N為樣本數(shù)，輸入向量 xn屬于某一值域X??D，yn屬于分類(lèi)標(biāo)簽集Υ={1，2，…，K}；每一實(shí)例{xn，yn}都是在某一未知分布分布D:Χ×Υ上相互獨(dú)立的［11］。相應(yīng)地，給定屬性測(cè)試代價(jià)集TC={TC(A)|A∈T}，屬性的等待時(shí)間代價(jià)集WC={WC(A)|A∈T}，T為所有屬性的集合。

代價(jià)敏感決策樹(shù)分裂屬性選擇的任務(wù)是利用訓(xùn)練集、測(cè)試代價(jià)集和等待時(shí)間代價(jià)集找出一個(gè)分裂屬性A，使得對(duì)于任意的A*∈T′，T′為所有待分裂屬性的集合，有

其中，GainRatio(A，S)表示屬性A的信息增益率。

如此，代價(jià)敏感決策樹(shù)分裂屬性的選擇就構(gòu)成了一個(gè)多目標(biāo)最優(yōu)化問(wèn)題。標(biāo)準(zhǔn)化各種代價(jià)和信息增益率后，用線性加權(quán)和法把多目標(biāo)最優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)最優(yōu)化問(wèn)題，得

2.3 建立代價(jià)敏感決策樹(shù)

我們的算法根據(jù)式（2）選擇使得F最小的屬性作為當(dāng)前分裂屬性，生成一個(gè)節(jié)點(diǎn)。類(lèi)似C4.5，我們的算法是根據(jù)局部最優(yōu)選擇的屬性，且是不能回溯的，所以最后有可能得不到全局最優(yōu)的決策樹(shù)。但是，采取局部最優(yōu)法能大大提高算法建樹(shù)的效率。

特別地，建樹(shù)的過(guò)程中要注意到以下三點(diǎn)。

第一，根據(jù)式（2），我們選擇使得F取到最小的屬性作為當(dāng)前節(jié)點(diǎn)，如果存在兩個(gè)或兩個(gè)以上的屬性同時(shí)使得F取到最小，那么我們?cè)龠M(jìn)一步根據(jù)以下的策略選擇屬性：

1）沒(méi)有標(biāo)準(zhǔn)化前具有更小誤分率代價(jià)MC的那個(gè)屬性；

2）沒(méi)有標(biāo)準(zhǔn)化前具有更小測(cè)試代價(jià)TC的那個(gè)屬性；

3）沒(méi)有標(biāo)準(zhǔn)化前具有更小等待時(shí)間代價(jià)WC的那個(gè)屬性。

根據(jù)實(shí)際應(yīng)用需求，優(yōu)先級(jí)策略2）和3）可以調(diào)換。因?yàn)榇鷥r(jià)敏感決策樹(shù)最終的目標(biāo)最主要是為了減小誤分類(lèi)代價(jià)（特別是在醫(yī)療診斷領(lǐng)域），所以把具有更小誤分類(lèi)代價(jià)的那個(gè)屬性優(yōu)先考慮。

第二，當(dāng)訓(xùn)練數(shù)據(jù)有缺失值時(shí)。文獻(xiàn)［14］實(shí)驗(yàn)驗(yàn)證了多種處理缺失值的方法來(lái)構(gòu)造代價(jià)敏感決策樹(shù)，得到結(jié)論：最好的方法是文獻(xiàn)［5］提出的內(nèi)部節(jié)點(diǎn)策略，即缺失的值不作為普通的輸入，而是根據(jù)誤分類(lèi)代價(jià)由內(nèi)部節(jié)點(diǎn)處理。因此，在訓(xùn)練數(shù)據(jù)時(shí)，我們將采用內(nèi)部節(jié)點(diǎn)的方法來(lái)處理缺失值來(lái)構(gòu)造我們的代價(jià)敏感決策樹(shù)。

第三，在怎樣的條件下停止建樹(shù)。類(lèi)似于C4.5，我們當(dāng)滿足以下兩個(gè)條件中的一個(gè)時(shí)，我們停止建樹(shù)。

1）在某一個(gè)節(jié)點(diǎn)處的所有的實(shí)例的類(lèi)標(biāo)簽是一樣的；

2）待分裂屬性的集合T′為空集。

當(dāng)沒(méi)有待分裂屬性，而節(jié)點(diǎn)中包含的實(shí)例的類(lèi)標(biāo)簽有多個(gè)時(shí)，此時(shí)，我們不能確定這個(gè)節(jié)點(diǎn)將作為標(biāo)注哪一個(gè)類(lèi)標(biāo)簽的葉子節(jié)點(diǎn)。在通常的決策樹(shù)中，那個(gè)類(lèi)標(biāo)簽包含的實(shí)例最多，則這個(gè)節(jié)點(diǎn)就被標(biāo)記為這個(gè)類(lèi)標(biāo)簽的葉子節(jié)點(diǎn)。在我們的算法中，代價(jià)敏感決策樹(shù)最終的目標(biāo)最主要是為了減小誤分類(lèi)代價(jià)。所以，對(duì)于每一個(gè)葉子節(jié)點(diǎn)，算法標(biāo)注其為某一個(gè)類(lèi)標(biāo)簽，最主要的是為了減小誤分類(lèi)代價(jià)。假設(shè)，某訓(xùn)練數(shù)據(jù)的類(lèi)標(biāo)簽Υ={1，2，…，K}有K個(gè)類(lèi)標(biāo)號(hào)，即訓(xùn)練數(shù)據(jù)中的實(shí)例可分成K類(lèi)。在某一節(jié)點(diǎn)，T′為空，這一節(jié)點(diǎn)中有 pi個(gè)實(shí)例的類(lèi)標(biāo)簽號(hào)是“i”，i=1，2，…，K。我們按照以下的標(biāo)準(zhǔn)來(lái)標(biāo)記這個(gè)節(jié)點(diǎn)。

即當(dāng)這個(gè)節(jié)點(diǎn)被標(biāo)記為“i”的葉子節(jié)點(diǎn)時(shí)，其引起的誤分類(lèi)代價(jià)最小。

2.4 測(cè)試決策樹(shù)

當(dāng)決策樹(shù)構(gòu)造完成后，我們就要用測(cè)試數(shù)據(jù)測(cè)試決策樹(shù)，驗(yàn)證決策樹(shù)是否滿足要求，即誤分類(lèi)代價(jià)、測(cè)試代價(jià)和等待時(shí)間代價(jià)是否滿足一定的標(biāo)準(zhǔn)，以達(dá)到實(shí)際的應(yīng)用需求。對(duì)于有缺失值的測(cè)試數(shù)據(jù)，文獻(xiàn)［3］提出了四種測(cè)試策略，并總結(jié)了這四種測(cè)試策略。文獻(xiàn)［3］總結(jié)出當(dāng)前的代價(jià)敏感決策樹(shù)測(cè)試策略主要有順序測(cè)試和批量測(cè)試這兩大類(lèi)測(cè)試策略，提出了一個(gè)把這兩種測(cè)試策略結(jié)合起來(lái)的混合策略。本文采取這種混合測(cè)試策略。具體如下：

首先，根據(jù)以下的公式計(jì)算每個(gè)屬性的效度（Utility）。

效度（Utility）是一個(gè)自然數(shù)，表示單位有形代價(jià)（TC+WC）的時(shí)間內(nèi)能使無(wú)形代價(jià)（MC）降低的能力。效度與分類(lèi)效果成比，效度越大，分類(lèi)效果越好。

其次，用式（4）計(jì)算批量屬性的效度。其中批量屬性應(yīng)滿足一下兩點(diǎn)：

1）這些屬性作為批量屬性是由領(lǐng)域?qū)＜覙?biāo)定的，且這些屬性之間有公共的一部分測(cè)試代價(jià)，這里命名為CC（Commom Cost）；

2）所有這些批量屬性的花費(fèi)的有型代價(jià)T_C（Tangible Cost）不能超過(guò)這次測(cè)試實(shí)例的總的資源。

批量屬性的效度計(jì)算公式如下：

最后，由以上兩步所計(jì)算的到效度最大的屬性首先進(jìn)行測(cè)試。當(dāng)效度最大的是單個(gè)屬性，則我們的測(cè)試策略可看作是順利測(cè)試策略；另一方面，當(dāng)效度最大的是批量屬性，則看作是批量測(cè)試策略。

當(dāng)所有的測(cè)試都完成或者測(cè)試實(shí)例的資源消耗完，則測(cè)試結(jié)束。

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

為了驗(yàn)證所提算法的有效性，我們從UCI機(jī)器學(xué)習(xí)倉(cāng)庫(kù)［15］選擇了兩個(gè)應(yīng)用非常廣泛且屬性值為離散的數(shù)據(jù)集，數(shù)據(jù)集的基本信息如表1所示。每個(gè)數(shù)據(jù)集我們把它分成兩份：訓(xùn)練集（60%）和測(cè)試集（40%）。由于數(shù)據(jù)集Car沒(méi)有缺失值，Mushroom有2480個(gè)缺失值（只占1.39%），我們?nèi)斯だ猛耆S機(jī)缺失（MCAR）機(jī)制分別把這兩個(gè)數(shù)據(jù)集的屬性缺失值比例占10%、20%、30%、40%、50%和60%。對(duì)于每個(gè)屬性的測(cè)試代價(jià)在［1，100］之間隨機(jī)分配，等待時(shí)間代價(jià)在［0，50］之間隨機(jī)分配。而誤分類(lèi)代價(jià)如表2和表3所示。特別地，誤分類(lèi)代價(jià)是一個(gè)相對(duì)值，它與測(cè)試代價(jià)和等待時(shí)間代價(jià)的衡量標(biāo)準(zhǔn)是不一樣。

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

表2 Mushroom數(shù)據(jù)集誤分類(lèi)代價(jià)

表3 Car數(shù)據(jù)集誤分類(lèi)代價(jià)

我們用三種不同的分裂屬性準(zhǔn)則來(lái)構(gòu)建不同缺失率下的代價(jià)敏感決策樹(shù)，分別是基于信息增益率的準(zhǔn)則（M1），基于最小總代價(jià)的準(zhǔn)則（M2），和我們的基于多目標(biāo)最優(yōu)化的準(zhǔn)則（M3）。其中，在我們的方法中，各種代價(jià)所取的權(quán)重一樣，即都是0.25。然后利用有缺失值得訓(xùn)練數(shù)據(jù)測(cè)試決策樹(shù)，M1用的是C4.5的方法處理缺失值，M2用的是文獻(xiàn)［4］的第1中方法處理缺失值，M3用的是本文提到的混合測(cè)試方法。實(shí)驗(yàn)結(jié)果如圖1、2所示。

圖1 Car數(shù)據(jù)集三種算法在不同缺失率下表現(xiàn)

圖2 Mushroom數(shù)據(jù)集三種算法在不同缺失率下表現(xiàn)

其中，平均總代價(jià)就是所有訓(xùn)練數(shù)據(jù)所引起的誤分類(lèi)代價(jià)、測(cè)試代價(jià)和等待時(shí)間代價(jià)三種代價(jià)和的平均。由圖1和圖2可以看出，隨著缺失率的增高，三種算法下的平均總代價(jià)（Average total cost）也隨著增大。這是由于隨著缺失率的增高，所構(gòu)建的決策樹(shù)性能隨著降低，且訓(xùn)練數(shù)據(jù)時(shí)測(cè)試代價(jià)和等待時(shí)間代價(jià)都要曾高。但是，相對(duì)于另外兩種算法，我們的算法表現(xiàn)得更好，效率更高。

4 結(jié)語(yǔ)

本文中我們把誤分類(lèi)代價(jià)、測(cè)試代價(jià)、等待時(shí)間代價(jià)和信息增益率構(gòu)造多目標(biāo)最優(yōu)化問(wèn)題模型，然后用線性加權(quán)和法把這個(gè)多目標(biāo)最優(yōu)化問(wèn)題轉(zhuǎn)化成單目標(biāo)最優(yōu)化問(wèn)題模型進(jìn)行求解，作為屬性選擇的準(zhǔn)則，而后構(gòu)建決策樹(shù)，應(yīng)用的一種混合的測(cè)試決策樹(shù)方法。實(shí)驗(yàn)結(jié)果表明，我們所提的算法效率高，應(yīng)用性強(qiáng)。但是，我們注意到，代價(jià)敏感決策樹(shù)最主要的是降低誤分類(lèi)代價(jià)，所以在后續(xù)的工作中，我們可以把各種代價(jià)有差別的對(duì)待構(gòu)造分層多目標(biāo)最優(yōu)化問(wèn)題的數(shù)學(xué)模型，在求解最優(yōu)值時(shí)把誤分類(lèi)代價(jià)首先考慮。

與此同時(shí)，過(guò)分地追求低誤分類(lèi)代價(jià)，有可能是以高誤分率為代價(jià)的［11］，誤分率過(guò)高這勢(shì)必會(huì)影響決策樹(shù)的實(shí)際應(yīng)用。所以在后續(xù)工作中，在構(gòu)建決策樹(shù)時(shí)有必要把誤分率也考慮進(jìn)去。