劉春英

0 引 言

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

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

定義1 決策表。

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

定義2 等價(jià)類。

設(shè)I＝（U，R），P?R，則∩P也是一個(gè)等價(jià)關(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)生的所有等價(jià)類用U／ind（P）表示，簡記為U／P。

定義3 等價(jià)關(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ù)知識(shí)P，U 中一定能和可能歸入X 的元素的集合，P（X）是根據(jù)知識(shí)P，U 中一定能和可能歸入X的元素的集合。posp（X）＝P（X）稱為X是R 的正域。若P，Q是U 中的等價(jià)關(guān)系，posp（Q）＝

定義4 依賴度。

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

定義5 核與約簡。

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

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

四元組I＝（U，R，V，f）是一個(gè)知識(shí)表達(dá)系統(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個(gè)條件屬性的取值范圍，決策屬性D與條件屬性ci的第cij個(gè)對(duì)象處的關(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個(gè)類別，對(duì)應(yīng)記錄數(shù)為Si（i＝1，2，…，m），則集合S的信息熵的計(jì)算公式:

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

于是以測(cè)試屬性A為分割點(diǎn)的信息增益為:

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

對(duì)ID3算法進(jìn)行改進(jìn)，1993年Quinlan提出的C4.5算法使用信息增益率作為分裂屬性的選擇標(biāo)準(zhǔn)，并且把連續(xù)屬性值離散化，使C4.5能夠?qū)Σ煌耆珨?shù)據(jù)進(jìn)行處理。1976年B Kss博士提出卡方自動(dòng)交互檢測(cè)算法（CHAID），CHAID以每個(gè)分類變量的不同值建立多個(gè)分支，依據(jù)卡方分布的值決定是否對(duì)結(jié)點(diǎn)進(jìn)行分裂，并且為缺失值單獨(dú)建立分支［6］。1984年 Breman等提出CART算法選擇GINI系數(shù)作為分裂屬性的選擇度量，對(duì)每個(gè)節(jié)點(diǎn)都進(jìn)行二元分裂，所選擇的分裂屬性都以不純度減少最大作為目標(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)鍵問題在于如何選擇分裂屬性，不同的決策樹生成算法采用不同的分裂屬性選擇方法。常用決策樹生成算法具有理論清晰、計(jì)算便利等優(yōu)點(diǎn)，但也存在以下不足:

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

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

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

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

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

四元組I＝（U，R，V，f）是一個(gè)知識(shí)表達(dá)系統(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越大，說明條件屬性對(duì)決策屬性的影響程度越大，同時(shí)表明此條件屬性所含有的信息量越大，對(duì)決策屬性的重要程度越高。當(dāng)大多數(shù)屬性數(shù)據(jù)量較大、個(gè)別屬性數(shù)據(jù)量較小時(shí)，常用決策樹生成算法偏向于選擇取值較多的屬性，而屬性值較多的屬性并不總是重要的屬性，從而掩蓋了取值較少的屬性的重要性。把屬性的關(guān)聯(lián)度引入作為選擇屬性的重要因素，以避免出現(xiàn)所選屬性與現(xiàn)實(shí)無關(guān)或大數(shù)據(jù)量屬性掩蓋小數(shù)據(jù)量屬性的錯(cuò)誤。

3.2 屬性約簡

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

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

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

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

5 分裂屬性的選擇

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

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

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

6 代價(jià)敏感決策樹生成方法

6.1 條件屬性約簡方法

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

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

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

步驟2:令B＝C0，對(duì)其余屬性x∈（C－B），分別計(jì)算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中所有屬性都進(jìn)行判斷。

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

6.2 代價(jià)敏感決策樹生成算法

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

輸出:代價(jià)敏感決策樹。

步驟1:利用條件屬性約簡方法對(duì)C進(jìn)行屬性約減為C″。

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

步驟3:對(duì)約減后的條件屬性集C″中的各個(gè)屬性計(jì)算它的性價(jià)比。

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

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

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

7 驗(yàn) 證

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

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

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

8 結(jié) 語

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

［1］ 朱顥東.ID3算法的改進(jìn)和簡化［J］.上海交通大學(xué)學(xué)報(bào)，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ìn)算法［J］.哈爾濱理工大學(xué)學(xué)報(bào)，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é)報(bào):自然科學(xué)版，2011，32（6）:534-537.

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

［7］ 李世娟，馬驥，白鷺.基于改進(jìn)的ID3算法的決策樹構(gòu)建［J］.沈陽大學(xué)學(xué)報(bào)，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.