基于關聯(lián)度的代價敏感決策樹生成方法

劉春英

0 引 言

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

1 相關概念和原理

定義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 等價類。

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

定義3 等價關系。

設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 中的等價關系，posp（Q）＝

定義4 依賴度。

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

定義5 核與約簡。

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

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

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

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

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

2.1 常用決策樹生成方法

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

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

2.2 存在問題

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

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

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

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

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

3.1 屬性的關聯(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的關聯(lián)度為:

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

3.2 屬性約簡

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

4 代價敏感學習

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

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

5 分裂屬性的選擇

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

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

選用改進的信息增益作為分裂屬性的選擇公式，把屬性關聯(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與決策屬性的關聯(lián)度，并按照關聯(lián)度由大到小的次序排列得X＝（x1，x2，…，xm）。

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

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

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

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

輸出:代價敏感決策樹。

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

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

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

步驟4:計算屬性關聯(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ù)進行試驗，基于關聯(lián)度的代價敏感決策樹生成方法（CSDT）和常用決策樹生成算法從分類準確率和生成決策樹的結點總數(shù)進行比較。CSDT和常用決策樹生成方法比較結果見表1。

表1 CSDT和常用決策樹比較結果

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

8 結 語

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

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

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

［7］ 李世娟，馬驥，白鷺.基于改進的ID3算法的決策樹構建［J］.沈陽大學學報，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.