(浙江工業(yè)大學(xué)信息工程學(xué)院，浙江 杭州310023)

0 引 言

決策樹方法是最受歡迎的數(shù)據(jù)挖掘技術(shù)之一，主要用于分類和預(yù)測。學(xué)者提出了著名的ID3 決策樹分類方法[1]。然而實(shí)驗(yàn)表明ID3算法在構(gòu)造決策樹時(shí)有多值偏向的問題，以往大多數(shù)的學(xué)者都是通過實(shí)驗(yàn)研究多值偏向問題[2-5]。有學(xué)者首次提出一種理論分析多值偏向問題的方法[6]。然而文獻(xiàn)[6]在分析多值偏向問題時(shí)，理論的嚴(yán)密性及邏輯性不強(qiáng)，缺少實(shí)例驗(yàn)證。本文在文獻(xiàn)[6]基礎(chǔ)上，針對其不足，基于粗糙集理論引入屬性重要度概念，從理論上分析了屬性多值對信息熵的影響和屬性多值對其他屬性的重要性程度的影響兩個(gè)問題。最后通過實(shí)驗(yàn)表明理論分析方法的正確性與可行性。

1 ID3算法及粗糙集理論

1.1 ID3算法

算法的主要思想[7]:已知數(shù)據(jù)樣本集S，樣本個(gè)數(shù)s，樣本所屬類別集合為C，設(shè)共有m個(gè){c1，c2，…，cm-1，cm}，把S 分為m個(gè)樣本子集為S={S1，S2，…，Sm-1，Sm}，樣本集Si中樣本的個(gè)數(shù)為si。樣本集的信息熵表示為:

設(shè)樣本集集合S 中某個(gè)屬性為A，A 有n個(gè)不同的屬性值{a1，a2，…，an-1，an}?；贏的屬性值把S劃分為n個(gè)樣本子集:S={S1，S2，…，Sn-1，Sn}，sij表示為Sj(j=1，2，…，n)中屬于類ci(i=1，2，…，m)的個(gè)數(shù)，pij表示為樣本子集Sj中樣本屬于有類ci的概率:

子集Sj的信息熵為:

根據(jù)屬性A 劃分后的樣本集合的信息熵為:

信息增益:

選擇屬性對結(jié)點(diǎn)進(jìn)行劃分的標(biāo)準(zhǔn)就是選取信息增益最大的屬性。

1.2 粗糙集理論及屬性重要度

定義1 在信息表S中，對于屬性集I?A，可構(gòu)成對應(yīng)的二元等價(jià)關(guān)系:

式中，f(x)表示對象x 在屬性I 上的屬性值，稱為由I 構(gòu)成的不可分辨關(guān)系。

定義2 設(shè)X?U，A為屬性集合，X的A的下近似的定義:

式中，U/IND(A)表示對象集合關(guān)于屬性集合A的等價(jià)類集合。表示一定屬于X的對象集合。X的A的上近似的定義為:

定義3 在信息表中，存在屬性集P，Q?A，定義Q的P 正域表示為:

定義4 在信息表中，存在屬性集R?C，定義D 依賴于R的程度為:

定義5 存在屬性集R?C 及屬性r∈R，定義屬性重要性度為:

式中，Card(POSR(D))表示集合的基數(shù)，屬性重要度表示屬性r 在條件屬性集R 中對樣本分類的重要性程度。其中D為決策屬性。

2 多值偏向及屬性重要度分析

設(shè)A是樣本集的某個(gè)屬性，具有n個(gè)屬性{A1，A2，…，An-1，An}，該屬性把樣本集合S劃分為S ={S1，S2，…，Sn-1，Sn}?，F(xiàn)在把屬性值為An的樣本隨機(jī)的分拆為屬性值分別為A'n，A'n+1的樣本子集，與A1，A2，…，An-1構(gòu)成新的屬性A'，A'有n+1個(gè)屬性值:{A1，A2，…，An-1，A'n，An}，A'把樣本集S劃分為S={S1，S2，…，Sn-1，S'n，Sn+1}。

2.1 算法多值偏向理論分析

思路:比較分裂前后屬性A的信息熵大小及重要度，即Gain(S/A')和Gain(S/A)的大小及與I(A)的大小。

1)由粗糙集理論可知:

2)為方便計(jì)算，用p(ci/Aj)=pij，即表示屬性值等于Aj時(shí)樣本集屬于C =ci的概率。用p(Aj)表示屬性值為Aj時(shí)樣本子集的權(quán)值。比較Gain(S/A')與Gain(S/A)的大小。

對上式等式兩邊同除以p(An)，得:

由式(12)、(15)得:I(A')=I(A) Gain(S/A')≥Gain(S/A)，證明完畢。

2.2 屬性多值對其它屬性重要度的影響

假設(shè)屬性集為{A，B，C}，拆分屬性A的一個(gè)屬性值，然后計(jì)算屬性C的重要性程度。

式(17)、(18)中，Xn=X'n∪Xn+1。

式中，Xi屬于U/IND(A)，Yj屬于U/IND(B)。

式中，Xi屬于U/IND(A')，Yj屬于U/IND(B)。

式(19)、(20)中，Zi=Z'i(i=1，…，(n-1)m)，Znm=Z'(n-1)m∪Z'(n-1)m+1∪…∪Z'(n+1)m。{A，B，C}及{A'，B，C}中C的重要度分別為I(C，{ABC}，D)其中，Card(POSABC(D))=Card(POSA'BC(D))，所以只需決策樹要比較Card(POSAB(D))與Card(POSA'B(D))的大小。

比較式(21)、(22)，得到Card(POSAB(D))≤Card(POSA'B(D))，最終得到I(C，{ABC}，D)≥I'(C，{A'BC}，D)。證明了屬性集合中的某屬性的增加屬性降低其他屬性的屬性重要性程度。

3 實(shí)例

以下實(shí)例是判斷氣候各個(gè)因素是否適合外出旅游，如表1所示。

設(shè)U為全體樣本，Q=j5i0abt0b，P={a1，a2，a3，a4}為條件屬性集集合。

這里只計(jì)算屬性a1熵與a4的重要性屬性，拆分a5=rain的屬性值，形成新的屬性a'1，計(jì)算a1分裂前后a1的信息增益，得Gain(U/a1)=0.246，Gain(U/a1')=0.298。計(jì)算a1分裂前后的屬性a4重要度為:I(a4)=0.286，I(a4)' =0.143。實(shí)驗(yàn)結(jié)果驗(yàn)證了理論分析的正確性。

表1 氣候因素表

4 結(jié)束語

本文從理論的角度分析了決策樹ID3算法的多值偏向問題?；诖植诩碚摚雽傩灾匾?，證明了屬性在增加屬性值的時(shí)候，屬性信息熵增加，但是該屬性的屬性重要度沒有增加。本文最后還分析了屬性增加屬性值對其他屬性重要度的影響。本文的不足之處是沒有提出克服決策樹ID3 多值偏向的方法，下一步工作重點(diǎn)是修正決策樹ID3算法的多值偏向問題。

[1]Quinlan J R.Induction of Decision Tree[J].Machine Learning，1986，(1):81-106.

[2]劉小虎，李生.決策樹的優(yōu)化算法[J].軟件學(xué)報(bào)，1998，9(10):797-800.

[3]胡學(xué)鋼，張冬艷.基于粗糙集的混合變量決策樹構(gòu)造算法研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，30(3):257-260.

[4]朱顥東.ID3算法的改進(jìn)和簡化[J].上海交通大學(xué)學(xué)報(bào)，2010，44(7):883-886.

[5]張琳，陳燕，李桃迎，等.決策樹分類算法研究[J].計(jì)算機(jī)工程，2011，37(13):66-67.

[6]韓松來，張輝，周華平.決策樹算法中多值偏向問題的理論分析[C].北京:中國金屬學(xué)會，2005:133-140.

[7]Ding Baoshi，Zheng Yongqing，Zhang Shaoyu.A New Decision Tree Algorithm Based on Rough Set Theory[C].Wuhan:Asia-Pacific Conference on Information Processing，2009:326-329.