劉春英

0 引 言

決策樹方法是數(shù)據(jù)挖掘中最常用的一種方法，它具有較好的分類預(yù)測能力，并能方便提取決策規(guī)則。決策樹采用樹形結(jié)構(gòu)的表示方法，內(nèi)部結(jié)點代表測試屬性，分支代表測試屬性的不同取值，葉節(jié)點代表分類的結(jié)果。在構(gòu)建決策樹的過程中，首先從所有測試屬性中選擇一個屬性作為根節(jié)點，并根據(jù)此屬性的不同取值劃分成若干個分支，從上到下通過選擇不同的測試屬性遞歸構(gòu)造決策樹，直到葉子節(jié)點將測試樣本劃分為一類。常用的決策樹生成方法有ID3方法［1］、C4.5方法［2］、CART 方法［3］、SLIQ 方法和 SPRINT［4］方法等。常用的決策樹生成方法在選擇屬性分裂標(biāo)準(zhǔn)時以獲得分類準(zhǔn)確率為目標(biāo)，沒有考慮代價和自適應(yīng)性問題。在追求分類準(zhǔn)確率的前提下，綜合考慮代價和自適應(yīng)問題，提出了一種基于粗糙集的代價敏感決策樹自適應(yīng)生成方法。

1 相關(guān)概念和原理

定義1 決策表。

形式上，四元組I＝（U，R，V，f）是一個知識表達系統(tǒng)，其中U是對象的非空。U×R→V是一個信息函數(shù)，它為每個對象的每個屬性賦予一個信息值，即有限集合，稱為論域R是屬性的非空有限集合。其中是屬性r 的值域；f:?r∈R，x∈U，f（x，r）∈V，一般簡記為I＝（U，R）。如果R＝C∪D，其中C為條件屬性集合，D為決策屬性集合且C∩D＝／○，則這樣的知識表達系統(tǒng)稱為決策表。

定義2 等價類。

設(shè)I＝（U，R），P?R，則∩P也是一個等價關(guān)系，稱為P上的不可區(qū)分關(guān)系，記為ind（P），ind（R）＝｛（x，y）∈U2｜?a∈P，f（x，a）＝f（y，a）｝。由不可區(qū)分關(guān)系ind（P）產(chǎn)生的所有等價類用U／ind（P）表示，簡記為U／P。

定義3 等價關(guān)系。

設(shè)I＝（U，R），P?R，X?U，P（X）＝｛x∈U｜［x］p?X｝和P（X）＝｛x∈U｜［x］p∩X≠／○｝稱為X的P下近似和上近似。顯然P（X）是根據(jù)知識P，U 中一定能和可能歸入X 的元素的集合，P（X）是根據(jù)知識P，U 中一定能和可能歸入X的元素的集合。posp（X）＝P（X）稱為X是R 的正域。若P，Q是U 中的等價關(guān)系，posp（Q）＝

定義4 依賴度。

令I(lǐng)＝（U，R），P，Q?R，當(dāng)設(shè)k＝γp（Q）＝時，稱Q是k（0≤k≤1）度依賴于P。當(dāng)k＝1時，稱Q完全依賴于P；當(dāng)0＜k＜1時，稱Q部分依賴于P；k＝0時，稱Q不依賴于P。其中，｜U｜表示U 的基數(shù)。

定義5 核與約簡。

R中所有必要的屬性組成的集合稱為R的核，記作core（R）。如果?r∈R都是必要的，則稱R為獨立的，否則稱R為依賴的。設(shè)Q?R，如果信息系統(tǒng)I的一個約簡。核與約簡的關(guān)系為:core（R）＝∩red（R）。等式后邊表示屬性集的所有約簡的交集。

定義6 關(guān)聯(lián)度。

四元組I＝（U，R，V，f）是一個知識表達系統(tǒng)，其中R＝C∪D，C為條件屬性集合，D為決策屬性集合且C∩D≠／○，設(shè)VD｛dj｜j＝1，2，…，n｝為決策屬性的取值序列，ci＝｛cij｜i＝1，2，…，m；j＝1，2，…，n｝為第i個條件屬性的取值范圍，決策屬性D與條件屬性ci的第cij個對象處的關(guān)聯(lián)系數(shù)定義為:

分辯參數(shù)ρ∈［0，1］。決策屬性D與條件屬性ci的關(guān)聯(lián)度定義為:

2 常用決策樹生成方法和存在問題

2.1 常用決策樹生成方法

Quinlan在1979年提出ID3方法是最典型的決策樹生成算法，該方法以信息熵和信息增益度為分裂屬性選擇的衡量標(biāo)準(zhǔn)［5］。訓(xùn)練集S有m個類別，對應(yīng)記錄數(shù)為Si（i＝1，2，…，m），則集合S的信息熵的計算公式:

設(shè)測試屬性A具有a1，a2，…，ax等x個不同的屬性值，集合S被分成x個子集（S1，S2，…，Sx）。Sij代表Sj中包含類別Ci的記錄數(shù)，則測試屬性A的期望信息熵為:

于是以測試屬性A為分割點的信息增益為:

Gain（A）＝I（S1，S2，…，Sm）－E（A）

對ID3算法進行改進，1993年Quinlan提出的C4.5算法使用信息增益率作為分裂屬性的選擇標(biāo)準(zhǔn)，并且把連續(xù)屬性值離散化，使C4.5能夠?qū)Σ煌耆珨?shù)據(jù)進行處理。1976年B Kss博士提出卡方自動交互檢測算法（CHAID），CHAID以每個分類變量的不同值建立多個分支，依據(jù)卡方分布的值決定是否對結(jié)點進行分裂，并且為缺失值單獨建立分支［6］。1984年 Breman等提出CART算法選擇GINI系數(shù)作為分裂屬性的選擇度量，對每個節(jié)點都進行二元分裂，所選擇的分裂屬性都以不純度減少最大作為目標(biāo)。1996年Mehta等 提 出 的 SLIQ（Supervised Learing In Quest）算法利用預(yù)排序技術(shù)和寬度優(yōu)先策略，采用內(nèi)存交換技術(shù)解決了數(shù)據(jù)量大于內(nèi)存容量的問題［7］。

2.2 存在問題

決策樹生成算法的關(guān)鍵問題在于如何選擇分裂屬性，不同的決策樹生成算法采用不同的分裂屬性選擇方法。常用決策樹生成算法具有理論清晰、計算便利等優(yōu)點，但也存在以下不足:

1）沒有考慮屬性的關(guān)聯(lián)度，分裂結(jié)點的選擇偏向于取值較多的屬性，而屬性值較多的屬性并不總是重要的屬性。

2）沒有考慮獲取分裂屬性所付出的代價。

3）沒有考慮分裂屬性所造成的誤分類代價。

3 屬性的關(guān)聯(lián)度和屬性約簡

3.1 屬性的關(guān)聯(lián)度

四元組I＝（U，R，V，f）是一個知識表達系統(tǒng)，其中R＝C∪D，C＝｛ci｜i＝1，2，…，n｝為條件屬性集合，ci＝｛cij｜j＝1，2，…，n｝，D 為決策屬性集合且C∩D≠／○，決策屬性D與條件屬性ci的關(guān)聯(lián)度為:

屬性關(guān)聯(lián)度DRi越大，說明條件屬性對決策屬性的影響程度越大，同時表明此條件屬性所含有的信息量越大，對決策屬性的重要程度越高。當(dāng)大多數(shù)屬性數(shù)據(jù)量較大、個別屬性數(shù)據(jù)量較小時，常用決策樹生成算法偏向于選擇取值較多的屬性，而屬性值較多的屬性并不總是重要的屬性，從而掩蓋了取值較少的屬性的重要性。把屬性的關(guān)聯(lián)度引入作為選擇屬性的重要因素，以避免出現(xiàn)所選屬性與現(xiàn)實無關(guān)或大數(shù)據(jù)量屬性掩蓋小數(shù)據(jù)量屬性的錯誤。

3.2 屬性約簡

屬性的重要程度并不相同，有些屬性對分類結(jié)果并沒有任何影響，故在決策樹構(gòu)建過程中要進行屬性約簡。屬性約簡是在整個知識表達系統(tǒng)分類能力不變的情況下，刪除關(guān)聯(lián)度小的和不重要的屬性。屬性約簡首先從求核屬性集合開始，在求核基礎(chǔ)上依次順序添加一個約簡的屬性，通過計算條件屬性的關(guān)聯(lián)度決定約簡次序。

4 代價敏感學(xué)習(xí)

代 價 敏 感 學(xué) 習(xí) （Cost-Sensitive Learning，CSL）最早在醫(yī)療診斷中被提出，醫(yī)生在病情診斷過程中為病人的測試代價和期望得到的測試效果進行權(quán)衡。代價敏感學(xué)習(xí)定義為通過訓(xùn)練數(shù)據(jù)集訓(xùn)練出獲得最小測試代價以及誤分類代價的診斷學(xué)習(xí)系統(tǒng)［8］。因不同的屬性值所獲取的難易程度不同，代價敏感的決策樹構(gòu)建不只考慮分類的準(zhǔn)確率，同時考慮屬性的測試代價。代價敏感學(xué)習(xí)在構(gòu)建決策樹過程中，在誤分類代價和測試代價之間權(quán)衡，優(yōu)先選擇具有最高性能價格比的屬性作為分裂屬性，其分裂屬性選擇標(biāo)準(zhǔn)與常用的決策樹分類標(biāo)準(zhǔn)不同，存在很大的差別。屬性的性價比是指誤分類代價的減少值與其測試代價的比值，屬性Ai的性價比cost＿ratio（Ai）定義為:

Testcost（Ai）代表屬性Ai的測試代價，分母加1是為預(yù)防有的屬性測試代價為0，導(dǎo)致分母為0的錯誤情況出現(xiàn)。分母代表選用屬性Ai所帶來的誤分類代價的減少量，Mc代表沒有選Ai作為分裂屬性時的誤分類代價。假設(shè)Ai有n個不同的屬性值，則在分裂時可分成n個子結(jié)點（Node1，Node2，…，Noden），在這些子節(jié)點 Nodei中有pi個正例和ni個反例，設(shè)前r個子結(jié)點為正例結(jié)點，后（n－r）個為反例結(jié)點。

5 分裂屬性的選擇

在選擇分裂屬性時，要考慮分裂屬性的關(guān)聯(lián)度和屬性的性價比，最優(yōu)的結(jié)果是所選擇的分裂結(jié)點屬性關(guān)聯(lián)度強并且性價比較高。要在屬性重要度和性價比之間權(quán)衡，采用調(diào)和函數(shù)達到這個目的。對n個數(shù)據(jù)點x1，x2，…，xn的調(diào)和函數(shù)H（x）定義為:

屬性關(guān)聯(lián)度DR（Ai）和性價比cost＿ratio（Ai）對應(yīng)于調(diào)和函數(shù)的兩個數(shù)據(jù)點，屬性關(guān)聯(lián)度和性價比的調(diào)和值:

選用改進的信息增益作為分裂屬性的選擇公式，把屬性關(guān)聯(lián)度和性價比代入后信息增益公式改進為:

6 代價敏感決策樹生成方法

6.1 條件屬性約簡方法

輸入:四元組I＝（U，R，V，f）是一個決策表，其中R＝C∪D，C為條件屬性集合，D為決策屬性集合，且C∩D≠／○。

輸出:決策表I的一個條件屬性約簡。

步驟1:計算條件屬性C相對于決策屬性D的相對核C0＝CoreD（C）。

步驟2:令B＝C0，對其余屬性x∈（C－B），分別計算x與決策屬性的關(guān)聯(lián)度，并按照關(guān)聯(lián)度由大到小的次序排列得X＝（x1，x2，…，xm）。

步驟3:依次按照關(guān)聯(lián)度從大到小的次序把X中的屬性xi加入B:B←B∪｛xi｝。若γB（D）＝γC（D），則執(zhí)行步驟4，否則，反復(fù)執(zhí)行步驟3，直到把X中所有屬性都進行判斷。

步驟4:算法結(jié)束，B∪D決策表I的一個屬性約簡。

6.2 代價敏感決策樹生成算法

輸入:四元組I＝（U，R，V，f）是一個知識表達系統(tǒng)，其中，R＝C∪D，C為條件屬性集合，D為決策屬性集合，且C∩D≠／○。

輸出:代價敏感決策樹。

步驟1:利用條件屬性約簡方法對C進行屬性約減為C″。

步驟2:對約減后的條件屬性集C″中的各個屬性計算它的關(guān)聯(lián)度。

步驟3:對約減后的條件屬性集C″中的各個屬性計算它的性價比。

步驟4:計算屬性關(guān)聯(lián)度和性價比的調(diào)和值H（DR（Ai），cost＿ratio（Ai））。

步驟5:以 H（DR（Ai），cost＿ratio（Ai））做分裂屬性信息增益的參數(shù)，建立決策樹。

步驟6:采用與C4.5相同的規(guī)則后修剪方法對生成決策樹進行剪枝。

7 驗 證

為了驗證算法的有效性，取UCI中數(shù)據(jù)集中的數(shù)據(jù)進行試驗，基于關(guān)聯(lián)度的代價敏感決策樹生成方法（CSDT）和常用決策樹生成算法從分類準(zhǔn)確率和生成決策樹的結(jié)點總數(shù)進行比較。CSDT和常用決策樹生成方法比較結(jié)果見表1。

表1 CSDT和常用決策樹比較結(jié)果

從表1中可以看出，基于關(guān)聯(lián)度的代價敏感決策樹生成的方法有較好的平均分類精確度，同時，構(gòu)造的決策樹有較低的復(fù)雜性。

8 結(jié) 語

把屬性關(guān)聯(lián)度和代價敏感思想相結(jié)合，提出了一種基于關(guān)聯(lián)度的代價敏感決策樹生成方法。該方法在選擇分裂屬性時不但考慮屬性關(guān)聯(lián)度，而且還結(jié)合了代價敏感的思想。實驗結(jié)果證明，利用文中方法所構(gòu)造的決策樹具有較高的分類精度和較少的結(jié)點總數(shù)。

［1］ 朱顥東.ID3算法的改進和簡化［J］.上海交通大學(xué)學(xué)報，2010，3（7）:53-57.

［2］ Quinlan J R.C4.5:Programs for machine learning［M］.San Mateo，CA:Morgan Kaufmann，1993:32-48.

［3］ 宋廣玲，郝忠孝.一種基于CART的決策樹改進算法［J］.哈爾濱理工大學(xué)學(xué)報，2009，4（2）:89-93.

［4］ Sharer J，Agrawal R，Mehta M.Sprint:A scalable parallel classifier of data mining［M］.San Francisco，CA:Morgan Kaufmann，1996:544-555.

［5］ 劉澤，潘暉.基于ID3算法汽車變速箱故障診斷系統(tǒng)［J］.長春工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2011，32（6）:534-537.

［6］ 黃愛輝，陳湘濤.決策樹ID3算法的改進［J］.計算機工程與科學(xué)，2009（6）:25-30.

［7］ 李世娟，馬驥，白鷺.基于改進的ID3算法的決策樹構(gòu)建［J］.沈陽大學(xué)學(xué)報，2009（6）:45-49.

［8］ Turney P.Cost-sensitive classivication:Empirical evaluation of a hybrid genetic decision tree induction algorithm［J］.Journal of Artificial Intelligence Research，1995，2（3）:369-409.