一種決策風險代價與屬性偏好融合的適應性決策樹算法

陳家俊，苗奪謙

1(皖西學院 電子與信息工程學院，安徽 六安 237012)

2(同濟大學 電子與信息工程學院，上海 201804)

3(同濟大學 嵌入式系統與服務計算教育部重點實驗室，上海 201804)

1 引 言

決策樹是機器學習中一種應用廣泛的監督式數據分類方法，具有分類精度高、速度快、生成的模式便于理解等優點受到廣泛關注.經典的決策樹算法ID3、C4.5和CART等算法及一系列的改進算法已被應用到相關分類問題中[1-3]，其中ID3算法的影響最大，但其以信息增益作為選擇劃分屬性的方法在實際應用中存在其局限性.文獻[4-7]對代價敏感決策樹進行了研究；文獻[8，9]分別從屬性的個人偏好、多值偏向以及誤分類代價角度對ID3算法進行改進，取得了較好的效果.粗糙集理論[10]是研究不精確、不確定性知識的數學工具，一些學者將粗糙集理論運用到決策樹算法[11-14]中，獲得滿足不同決策精度需求且結構簡單的決策樹.以上算法分別從不同角度來提高決策樹的性能和適用性，但隨著應用的推廣，決策樹模型將面臨更為復雜的應用環境，而現有決策樹在選擇劃分屬性時，不能充分考慮決策區域產生的客觀分類精度、區域誤判代價以及決策者對屬性的個人偏好等因素的影響.決策粗糙集模型[15-18]是經典粗糙集模型基于概率推廣的一種決策模型，通過條件概率來刻畫概念的相交程度，用兩個閾值(α、β)來定義概念的上下近似集，將決策空間表示為(α、β)-正、負和邊界域，適合處理很多具有不確定性因素產生的實際問題.由于知識的不確定性，決策者的每一步決策都會產生一定的決策風險，即可能將一部分對象被錯誤的劃分到不同的決策域中，從而影響決策規則的精確度，文獻[19-22]對決策粗糙集中決策風險代價問題及相關性質進行了研究.

本文在對基于信息熵和基于粗糙集的兩類決策樹算法的研究基礎上，充分考慮決策區域客觀分類精度、區域誤判代價以及決策者的屬性個人偏好等因素，將決策粗糙集模型引入到決策樹算法中，提出一種決策風險代價與屬性偏好融合的適應性決策樹算法.引入用戶偏好程度和決策風險損失函數的概念，通過構建適應度函數作為啟發式函數選擇劃分屬性，從而建立決策樹模型，在決策樹構建過程中，通過定義置信因子概念對決策樹進行剪枝，以免構建的決策樹過于龐大.理論和實驗分析驗證了算法的有效性和適應性.

2 預備知識

2.1 基于信息熵的決策樹算法

經典的決策樹算法及一系列的改進算法[1-4]是通過計算信息熵來選擇劃分屬性.以ID3算法為例，設S=(U，C∪D，V，F)為決策表信息系統，U中包含s個實例樣本，U={x1,x2，…，xs}，C和D分別稱為條件屬性集和決策屬性集，C包含m個屬性，C={c1,c2,…，cm}，D=D{D1,D2,…,Dk}表示樣本可以分為k類，每類的樣本數為sk，對應的概率為P={p1,p2,…,pk}，其中pk=sk/s，每個屬性ci有V個可能的取值{V1,V2,…,Vv}，當屬性ci取值為Vv時，得到的樣本集為Sv，則屬性ci的信息增益定義為：

Gainci(S)=Ent(s)-Entci(s)

(1)

其中：

由公式(1)可知，信息增益越大，意味著使用屬性Ci對樣本進行劃分所獲得的樣本純度提升越大，可以理解為通過屬性ci把樣本正確的劃分到某一類中其貢獻度越大，可稱Gainci(S)為屬性的貢獻度函數.以屬性的貢獻度作為劃分屬性的選擇標準構建決策樹，可以獲得較高的決策精度.但以信息增益構建的決策樹存在屬性多次檢驗、多值偏向等問題，決策樹構建過程中不能考慮到分類代價[5，6，8]、屬性的個人偏好等局限性.

2.2 基于粗糙集模型的決策樹

將粗糙集引入決策樹算法中，即在決策樹構建過程中充分考慮到屬性劃分時的近似分類精度.對于給定的信息系統S=(U,C∪D,V,F)，令B?C，設U/B={Y1,Y2,…,Yn}表示關于B的等價類集合，U/D={D1,D2,…Dm}表示關于D的等價類集合，若X?U，則X關于B的上、下近似集可表示為Bˉ(X)=∪{Yi|Yi∈U/BΛYi∪X≠?}和B_(X)=U{Yi|Yi∈U/BΛYi∩X?X}，則D的B正域可定義為：

POSB(D)=∪Di∈U/DB_(Di)

B相對決策屬性D的近似分類精度可定義為：

γB(D)=card(POSB(D)/card(U))

屬性ci在集合C中相對于決策屬性集D的重要性可定義為：

SGF(ci，C,D)=γC(D)-γC-{ci}(D)

通過計算近似分類精度和屬性的重要性，獲得重要性最大的屬性ci，以ci作為劃分屬性構造決策樹.這種構造方法充分考慮論域中具有確定性元素的影響，而忽視了部分不確定性元素也將起到重要作用.

本文在對以上兩類決策樹算法的研究基礎上，考慮到決策樹在構建過程中受條件屬性形成的劃分產生的客觀分類精度、區域誤判代價以及條件屬性的個人偏好等因素影響，引入決策粗糙集思想，通過決策分類精度和決策風險代價對屬性劃分標準進行改進.

3 決策粗糙集模型

對于四元組S=(U,C∪D,V,F)，其中U={x1,x2,…,xn}是非空有限對象集，C是條件屬性集，D是決策屬性集，C∩D=?，假設狀態集Ω={ω1,ω2,…,ωm}由m個決策類構成，m類分類問題可以轉換成m個兩類分類問題.對于任意決策類ωj(j=1，2，…，m)，用狀態集Ωj={ωj,ωj}表示對象是否屬于決策類ωj，用aPj,aBj,aNj表示決定將對象x分類到正域POS(ωj)、邊界域BND(ωj)和負域NEG(ωj)中的3種動作行為，若對象x屬于某個狀態時，采取不同的動作決策就會產生不同的損失，m個決策類的決策代價損失如表1所示.對于給定的對象x，用[x]B表示對象x關于B的等價類，對象x屬于ωj和不屬于ωj的條件概率分別表示為Pr(ωj|[x]B)=|[x]B∩ωj|/|[x]B|和Pr(ωj|[x]B)=|[x]B∩ωj|/|[x]B|，則對象x采取3種動作行為的期望損失分別表示為：

R(αPj|[x]B)=λPjωjPr(ωj|[x]B)+λPjωjPr(ωj|[x]B)

R(αBj|[x]B)=λBjωjPr(ωj|[x]B)+λBjωjPr(ωj|[x]B)

R(αNj|[x]B)=λNjωjPr(ωj|[x]B)+λNjωjPr(ωj|[x]B)

表1 m個決策類的代價損失矩陣Table 1 Cost loss matrix of m decision classes

考慮一組特殊的損失函數：

λPjωj≤λBjωj<λNjωj；λNjωj≤λBjωj<λPjωj

根據實際的應用情況，對于原本屬于ωj的對象分類到ωj的正域，其損失小于等于將其分類到邊界域的損失，且兩者的損失均小于將其劃分到負域的損失[15-17，23].令

(2)

根據yao三支決策語義規則可知1≥αj≥βj≥0.令λPP=λPjωj，λBP=λBjωj，λNP=λNjωj，λPN=λPjωj，λBN=λBjωj,λNN=λNjωj則每一個決策類對應的損失矩陣如表2所示.

表2 損失矩陣Table 2 Loss matrix

假設每一個決策類具有相同的損失矩陣，可計算得到α1=α2=αj=…=αm，β1=β2=βj=…=βm，后面敘述中用α,β表示.令決策屬性D導出的劃分為πD={D1,D2,…，Dm}，則決策粗糙集下的正區域、邊界域和負區域的決策規則如下[23]：

if Pr((Dmax([x]B)|[x]B)≥α,then[x]B?POS(α,β)(πD|πB)

if β

[x]B?BND(α,β)(πD|πB)

if Pr(Dmax|[x]B)≤β,then[x]B?NEG(α,β)(πD|πB)

令Pr(Dmax|[x]B)=l，則各個規則的風險表示如下[23]：

正規則的風險損失：lλPP+(1-l)λPN

邊界規則下的風險損失：lλBP+(1-l)λBN

負規則下的風險損失：lλNP+(1-l)λNN

定義1. 給定信息系統S=(D，C∪D，V,F)，令B?C，設πB表示關于B的等價類[x]B的集合，πD={D1,D2,…，Dm}表示關于D的等價類集合，則決策區域關于B的近似分類精度可定義為：

(3)

定義2. 給定信息系統S=(D，C∪D，V，F)，若屬性集合B?C，設πB表示關于B的等價類[x]B的集合，πD={D1,D2,…,Dm}表示決策屬性D導出的劃分集合，則屬性集合B的決策風險代價函數定義為：

CostB=∑xi∈POS(α,β)(πD|πB)(liλPP+(1-li)λPN)+
∑xj∈BND(α,β)(πD|πB)(ljλBP+(1-lj)λBN)+
∑xk∈NEG(α,β)(πD|πB)(lkλNP+(1-lk)λNN)

(4)

4 適應性決策樹算法

4.1 相關概念

在現實生活中，由于不同的人群對同一問題有不同的個人偏好，從而影響決策結果，因此，在討論決策問題時，確定決策者對某些特定問題偏好程度的大小就顯得非常重要.

定義3.(用戶偏好程度)用戶xi對屬性cj的主觀偏好程度φij可用主觀偏好矩陣描述[23]如下：

在實際應用中，通過針對不同應用領域統計分析，可以評估出不同人群對某種特定信息系統中屬性的偏好程度，從而得到用戶偏好矩陣.假設針對某一特定人群，具有相同的用戶偏好，記為φ={φ1,φ2，…，φn}.

定義4.(改進的貢獻度函數) 給定決策表信息系統S=(U,C∪D，V，F)，C是條件屬性，D為決策屬性，φ={φ1,φ2,…，φn}為用戶屬性偏好程度，對于?ci∈C={C1,C2,…,Cn}，則改進的貢獻度函數可定義為：

Si=h(φi,Gainai(S))

選取線性函數為：

Si=μφi+(1-μ)Gainai(S)

(5)

其中0≤μ≤1為用戶偏好程度和屬性貢獻度的調節系數.當μ=0時，僅考慮屬性貢獻度，當μ=1時僅考慮用戶偏好.

為了簡化模型，取3個變量的加權平均值函數，即：

(6)

其中0≤ki≤1,i=1,2,3;k1+k2+k3=1

這3個參數的設置需要一定的領域經驗值，對于不同領域的問題，因為考慮的因素不同，3個參數的取值可能有一定差異.

定義6. 給定決策表信息系統S=(U,C∪D，V，F)，C是條件屬性，D為決策屬性，令B?C，設πB表示關于B的等價類[x]B的集合，πD={D1，D2，…,Dm}表示關于D的等價類集合，由文獻[14]中定義3可得決策區域的可信度為：

μi=|[x]B∩Di|/|[x]B|(0≤μi≤1)則決策區域的置信因子可定義為：

δ[x]B(Di)={argmaxDi∈πDμi}i=1,2…m

(7)

δ[x]B(Di)表示對象x關于條件屬性B的等價類區域劃分到具有最大概率的Di決策類的可信度.

4.2 算法設計思路

由于基于信息熵的決策樹存在多值偏向、不能充分考慮決策區域的客觀分類精度、決策分類代價以及屬性偏好等局限性，而基于粗糙集的決策樹模型雖然考慮到了近似分類精度，但其是基于嚴格定義的等價類，應用過程中僅僅考慮論域中的確定性元素，而忽略了部分不確定性元素也將起到的重要作用.因此，算法引入決策粗糙集的思想，通過條件概率來刻畫概念的相交程度，放松了對近似邊界的嚴格定義，更適合于處理具有不確定性因素產生的實際問題.由于決策粗糙集對代價具有敏感性，算法根據三支決策原理，采用貝葉斯最小風險決策原則，獲取決策表中由條件屬性集合產生的決策風險代價.考慮到用戶在實際決策應用中存在屬性偏好問題，算法首先使用調節系數對屬性偏好程度和屬性的貢獻度進行調節，以改進條件屬性的貢獻度；再通過設置3個不同的參數構建適應度函數，以適應度函數作為啟發式函數選擇劃分屬性，從而建立決策樹模型.

4.3 算法描述

算法1.分類精度和決策代價求解算法

輸入：S=(U，C∪D，V，F)，損失矩陣(λij)2×3

輸出：近似分類精度和決策風險代價

Step1. 將損失矩陣λij中的值代入公式(2)，求出對應的α,β值；

Step2. 1)計算IND(C)和IND(D)，分別存放到equC和equD中，對每個Dj∈equD，計算每個[x]C∈equC相對于Dj的概率Pr(Dj|[x]C)；

2)for [x]Cin equC

for Djin equD

{根據α，β的值，確定劃分所在的區域(正區域、負區域和邊界域)}；

Step4. 根據公式(4)計算決策代價CostC；

算法2.適應性決策樹算法

輸入：S=(U，C∪D，V，F)，調節系數μ，閾值ρ，屬性C={c1,c2,…,cn}，屬性偏好列表，φ={φ1，φ2，…，φn}，參數K=(k1，k2,k3)

輸出：一棵決策樹

Step1. if當前樣本集全屬于同一類別D0then 返回 葉子結點D0；if C為空或樣本在C上取值相同then將D中樣本數最多的類標記為葉子結點；

Step2. 1)For ciin C

{根據公式(5)計算Si；

Step3.根據c*屬性對當前樣本進行劃分，計算每個劃分區域的置信因子δ[x]c*(Di)，并將其與閾值ρ進行比較；if δ[x]c*(Di)≥ρ then

{保留當前分支，并將Di對應的類標記為葉子結點，結束該劃分區域的計算；如果所有劃分區域運算結束，則轉入Step 5.}

else

{選擇該劃分區域作為當前樣本子集，轉入Step 1；}

Step4. 結束.

5 實驗分析

為驗證文中算法的有效性，首先將文中算法在文獻[3]中提供的西瓜數據集2.0上進行實例驗證，對數據進行預處理和轉換操作后得到樣本集合，該集合包含17條樣本實例和6個條件屬性：色澤(含0-青綠，1-烏黑，2-淺白)、根蒂(含0-蜷縮，1-稍蜷，2-硬挺)、敲聲(含0-濁響，1-沉悶，2-清脆)、紋理(含0-清晰，1-稍糊，2-模糊)、臍部(含0-凹陷，1-稍凹，2-平坦)、觸感(含0-硬滑，1-軟粘)；包含決策屬性：好瓜(含0-否，1-是).實驗在Win10環境下，采用開源的Python2.7編程實現.假設決策誤分損失矩陣如表3所示.

樣本集中隨機選取80%作為訓練集，其余20%作為測試集進行實驗，分別從決策樹的規模(葉子數/節點總數)、樹的深度和分類準確率這幾個方面分析用戶偏好程度和置信因子對實驗結果的影響.假設條件屬性的偏好度列表pref=[0.1，0.05，0.3，0.5，0.05，0.05]，K=(0.2,0.3,0.5)，當協調系數μ和ρ取不同值時得到實驗結果如表4所示.

表3 決策誤分損失矩陣Table 3 Misclassification Loss matrix

表4 西瓜數據集上的實驗結果Table 4 Result on watermelon data set

根據公式(5)知，μ值越大，在決策樹構建過程中屬性偏好程度所起的作用越大；從表4中可以看出μ取不同的值，其實驗結果差異較大，說明屬性偏好對決策精度的影響較大.當μ=0時，僅考慮屬性貢獻度，當μ=1時僅考慮用戶偏好，μ具體的取值，則需要根據不同領域具體需求決定.同時，實驗過程中采用置信因子概念，通過閾值ρ對決策樹進行剪枝，以防決策樹過于龐大.表4可以看出當ρ=0.7時，無論從規模、深度和分類正確率上都優于ρ=1(沒有剪枝的情況) 的實驗結果.

表5 數據集描述Table 5 Data sets description

為更進一步驗證該算法的有效性，選取西瓜數據集和UCI數據庫中提供的若干標準數據集作為實驗對象，數據集描述如表5所示.由于各數據集的屬性個數不同，假設每個條件屬性的偏好程度相等，令μ=0.5，K=(0.2,0.3,0.5)，ρ=0.7，將本文算法(用CPADT表示)與ID3算法和基于屬性重要度的粗糙集方法(用RSDT表示)在表5數據集上各進行10次實驗，以平均分類精度為最終實驗數據進行對比，實驗結果如圖1所示.可以看出本文算法有較高的平均分類精度.為驗證各參數所起作用的大小，對K參數選取幾組不同的值進行試驗，并計算在各數據集上10次實驗的平均分類精度，實驗結果如表6所示.

圖1 三種算法平均分類精度對比圖Fig.1 Classification accuracy of three algorithms

表6 數據集上平均分類準確率Table 6 Average accuracy on all data sets

從表6數據可以看出(k1,k2,k3)取不同的值其實驗結果有所區別，當參數值分布較均勻時，如表6中前兩組數據，獲得的實驗結果較穩定且分類準確率較高，說明算法能充分考慮近似分類精度、決策風險代價和屬性偏好等因素；當參數取值差異很大時，如表6中后兩組數據，平均分類正確率相對偏低.同時，當k1=0和k2=0時，實驗結果與參數分布均勻時的實驗結果變化不大，而當k3=0時獲得的實驗結果相對較低，說明在決策過程中，用戶的屬性偏好和屬性的貢獻度起決定性作用，直接影響著決策的精度；而決策區域的客觀分類精度和決策分類代價是存在的，其對決策精度影響的大小，取決于不同應用領域所研究的數據集的純度以及不同領域專家所給出的決策損失函數的大小.

6 總 結

本文在對決策樹算法與決策粗糙集模型的研究基礎上，將用戶偏好程度和決策風險代價引入決策樹算法中，通過構建適應度函數作為啟發式函數選擇劃分屬性，充分考慮了決策區域客觀存在的分類精度、誤分代價以及用戶對條件屬性的個人偏好問題，實驗結果分析說明該算法是有效的，且通過參數設置可以增強算法的適應性，滿足不同應用領域的需求.

：

[1] Quinland J R.Induction of decision trees[J].Machine Leaning，1981，1(1)：81-106.

[2] Quinland J R.C4.5：Programs for machine learning[M].San Francisco：Morgan Kaufman，1993.

[3] Zhou Zhi-hua.Machine learning[M].Beijing：Tsinghua University Press，2016.

[4] Lomax S.A survey of cost-sensitive decision tree induction algorithms[J].ACM Computing Surveys，2013，45(2)：1-35.

[5] Ruan Xiao-hong，Huang Xiao-meng，Yuan Ding-rong，et al.Classification algorithm based on heterogeneous cost-sensitive decision tree[J].Computer Science，2013，40(11A)：140-142.

[6] Chen Yen-liang，Wu Chia-chi，Kwei Tang.Time-constrained cost-sensitive decision tree induction[J].Information Sciences，2016，354(1)：140-152.

[7] Chen Qiu，Jiang Liang-xiao，Li Chao-qun.Randomly selected decision tree for test-cost sensitive learning[J].Applied Soft Computing，2017，53(8)：27-33.

[8] Zhou Mei-qin，Xu Zhang-yan，Chen Shi-xu，et al.Novel preference sensitive decision tree algorithm[J].Application Research of Computers，2016，33(10)：3001-3006.

[9] Dong Yue-hua，Liu Li.Decision tree optimisation algorithm based on equilibrium coefficient[J].Computer Application and Software，2016，33(7)：266-272.

[10] Miao Duo-qian，Li Dao-guo.Rough set theory，algorithm and application[M].Beijing：Science Press，2007.

[11]Mao Jin，Wang Shu-qin，Wang Ming-yang，et al.Rough set based approach for inducing decision trees[J].Knowledge-Based Systems，2007，20(8)：695-702.

[12] Chen Jia-jun，Huang Yuan-yuan.Decision tree construction algorithm for incomplete information system[C].2012 International Conference on Computational and Information Sciences，2012：404-407.

[13] Ding Chun-rong，Li Long-shu，Yang Bao-hua.Decision tree constructing algorithm based on rough set[J].Computer Engineering，2010，36(11)：75-77.

[14] Chen Jia-jun，Su Shou-bao，Xu Hua-li.Decision tree optimization algorithm based on multiscale rough set model[J].Journal of Computer Application，2011，31(12)：3243-3246.

[15] Xu Jiu-cheng，Du Li-na，Liu Yang-yang.Three-way decisions and vague sets[J].Journal of Chinese Computer System，2016，37(7)：1464-1468.

[16] Yu Hong，Wang Guo-yin，Li Tian-rui，et al.Three-way decisions：complex problem solving methods and practices[M].Beijing：Science Press，2015.

[17] Yao Yi-yu.Three-way decisions with probabilistic rough sets[J].Information Sciences，2010，180(3)：341-353.

[18] Zhang Xiao-hong，Miao Duo-qian，Liu Cai-hui.Constructive methods of rough approximation operators and multigranulation rough sets[J].Knowledge-Based Systems，2016，91：114-125.

[19] Dou Hui-li，Yang Xi-bei，Song Xiao-ning，et al.Decision-theoretic rough set：A multicost strategy[J].Knowledge-Based Systems，2016，91 ：71-83.

[20] Bi Zhong-qin，Xu Fei-fei，Lei Jing-sheng，et al.Attribute reduction in decision-theoretic rough set model based on minimum decision cost attribute reduction based on minimum decision cost[J].Concurrency and Computation：Practice and Experience，2016，28(15)：4125-4143.

[21] Ju Heng-rong，Yang Xi-bei，Yu Hua-long，et al.Cost-sensitive rough set approach[J].Information Sciences，2016，355(10):282-298.

[22] Yu Hong，Yao Yuan，Zhao Jun.An attribute reduction algorithm based on risk minimization[J].Journal of Nanjing University(Natural Sciences)，2013，49(2)：210-216.

[23] Zhang Qing-hua，Hu Rong-de，Yao Long-yang，et al.Risk DTRS attribute reduction based on attribute importance[J].Control and Decision，2016，31(7)：1199-1205.

附中文參考文獻：

[3] 周志華，著.機器學習[M].北京：清華大學出版社，2016.

[5] 阮曉宏，黃小猛，袁鼎榮，等.基于異構代價敏感決策樹的分類器算法[J].計算機科學，2013，40(11A)：140-142.

[8] 周美琴，徐章艷，陳詩旭，等.新型偏好敏感決策樹算法[J].計算機應用研究，2016，33(10)：3001-3006.

[9] 董躍華，劉 力.基于均衡系數的決策樹優化算法[J].計算機應用與軟件，2016，33(7)：266-272.

[10] 苗奪謙，李道國.粗糙集理論、算法與應用[M].北京：科學出版社，2007.

[13] 丁春榮，李龍澍，楊寶華.基于粗糙集的決策樹構造算法[J].計算機工程，2010，36(11)：75-77.

[14] 陳家俊，蘇守寶，徐華麗.基于多尺度粗糙集模型的決策樹優化算法[J].計算機應用，2011，31(12)：3243-3246.

[15] 徐久成，杜麗娜，劉洋洋.三支決策與Vague集[J].小型微型計算機系統，2016，37(7)：1464-1468.

[16] 于 洪，王國胤，李天瑞，等.三支決策：復雜問題求解方法與實踐[M].北京：科學出版社，2015.

[22] 于 洪，姚 園，趙 軍.一種有效的基于風險最小化的屬性約簡算法[J].南京大學學報：自然科學版，2013，49(2)：210-216.

[23] 張清華，胡榮德，姚龍洋，等.基于屬性重要度的風險決策粗糙集屬性約簡[J].控制與決策，2016，31(7)：1199-1205.