曹禮園 李深洛

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

1 引言

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

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

2 構(gòu)建決策樹

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

2.1 代價的定義

文獻［1］總結(jié)出9種主要的代價，它們是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。本文主要考慮測試代價、等待時間代價及誤分類代價這三種代價。

1）誤分類代價（MC）

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

2）測試代價（TC）

測試代價：是獲取屬性值測試所需要的花費，由所處理數(shù)據(jù)的領域提供。實際應用中，測試代價要復雜得多，獲取屬性A的值，其測試代價為TC(A)，實際的值由領域?qū)＜医o出。

3）等待時間代價（WC）

等待時間代價：獲取屬性值等待測試結(jié)果所引發(fā)的代價。如果某屬性A的測試一定要等待另一個屬性B的結(jié)果出來才可以進行，則屬性A等待時間代價與屬性B的等待時間代價相關，我們稱屬性B為屬性A的先驗屬性。

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

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

2.2 分裂屬性的選擇

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

代價敏感決策樹分裂屬性選擇的任務是利用訓練集、測試代價集和等待時間代價集找出一個分裂屬性A，使得對于任意的A*∈T′，T′為所有待分裂屬性的集合，有

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

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

2.3 建立代價敏感決策樹

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

特別地，建樹的過程中要注意到以下三點。

第一，根據(jù)式（2），我們選擇使得F取到最小的屬性作為當前節(jié)點，如果存在兩個或兩個以上的屬性同時使得F取到最小，那么我們再進一步根據(jù)以下的策略選擇屬性：

1）沒有標準化前具有更小誤分率代價MC的那個屬性；

2）沒有標準化前具有更小測試代價TC的那個屬性；

3）沒有標準化前具有更小等待時間代價WC的那個屬性。

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

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

第三，在怎樣的條件下停止建樹。類似于C4.5，我們當滿足以下兩個條件中的一個時，我們停止建樹。

1）在某一個節(jié)點處的所有的實例的類標簽是一樣的；

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

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

即當這個節(jié)點被標記為“i”的葉子節(jié)點時，其引起的誤分類代價最小。

2.4 測試決策樹

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

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

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

其次，用式（4）計算批量屬性的效度。其中批量屬性應滿足一下兩點：

1）這些屬性作為批量屬性是由領域?qū)＜覙硕ǖ模疫@些屬性之間有公共的一部分測試代價，這里命名為CC（Commom Cost）；

2）所有這些批量屬性的花費的有型代價T_C（Tangible Cost）不能超過這次測試實例的總的資源。

批量屬性的效度計算公式如下：

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

當所有的測試都完成或者測試實例的資源消耗完，則測試結(jié)束。

3 實驗結(jié)果及分析

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

表1 實驗數(shù)據(jù)集

表2 Mushroom數(shù)據(jù)集誤分類代價

表3 Car數(shù)據(jù)集誤分類代價

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

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

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

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

4 結(jié)語

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

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