Rough Set-Based Decision Tree Construction Algorithm翻譯

1、基于決策樹(shù)構(gòu)造的粗糙集算法Sang-wook han 和 Tae-Ywern Kim漢陽(yáng)大學(xué)工業(yè)工程學(xué)院，Sungdong-gu, 韓國(guó)首爾133-791softhanhanyang.ac.kr, jykhanyang.ac.kr摘要：我們運(yùn)用粗糙集理論獲取決策樹(shù)的構(gòu)造知識(shí)。決策樹(shù)廣泛適用于機(jī)械學(xué)習(xí)。各種各樣決策方法的樹(shù)被開(kāi)發(fā)出來(lái)。我們的算法是一種新型樹(shù)結(jié)構(gòu)。它相比了對(duì)象的核心屬性并基于這些特點(diǎn)建立了決策樹(shù)。實(shí)驗(yàn)表明新算法比其他算法可以更有意義和更明確提取規(guī)則。關(guān)鍵字：粗糙集，決策樹(shù)，核1引言分類(lèi)是數(shù)據(jù)挖掘的重要組成部分，在這一過(guò)程中決策樹(shù)是被廣泛應(yīng)用的工具,因?yàn)樗麄兪侨菀自忈尩?、?zhǔn)確、快速。

2、粗糙集理論是一種數(shù)學(xué)技術(shù)用于分析不確切的,不確定的,或模糊的信息等方面的數(shù)據(jù)挖掘，比如人工智能和模式識(shí)別。各種各樣的方法提出了構(gòu)建決策樹(shù)，包括基于核心屬性的粗糙集理論,可以用來(lái)排除不必要的特征,從而對(duì)象創(chuàng)建一個(gè)數(shù)據(jù),約簡(jiǎn),粗糙近似的對(duì)象的簡(jiǎn)化版本。Weietal提出基于上下近似決策樹(shù)的粗糙集，而baietal 是基于核心屬性和熵的決策樹(shù)的代表。粗糙集理論有很多優(yōu)勢(shì),但它的主要好處是它不需要初步數(shù)據(jù)知識(shí)或另外的數(shù)據(jù)信息。雖然核屬性在粗糙集理論中最重要的概念,人們沒(méi)有做出嘗試建立決策樹(shù)，這種決策樹(shù)使用數(shù)據(jù)集的每一件物體比較。提出了一種新的決策樹(shù)分類(lèi)算法,這種算法使用核心屬性在數(shù)據(jù)分類(lèi)提供最重大的貢

3、獻(xiàn)。在第二部分,我們將討論粗糙集理論的有關(guān)概念。第三部分給出了新方法的基本入門(mén),并給出了一種簡(jiǎn)單的例子。第四部分計(jì)算實(shí)驗(yàn)來(lái)描述的方法。最后一部分進(jìn)行總結(jié)以及未來(lái)的研究方向。2粗糙集理論在粗糙集理論，知識(shí)的表示方法是通過(guò)做的信息系統(tǒng)，信息系統(tǒng)定義如下：S=(U,Q,V,f) 其中，U是非空有限對(duì)象集合；Q是記錄的屬性集合，V是屬性值集合，V=Vq ，對(duì)于qQ且Vq 是屬性q的值，并且U*Q V整體判決函數(shù)稱(chēng)為信息函數(shù)，例如：f（x，q）Vq，qQ，xU。一個(gè)決策表格式一個(gè)信息系統(tǒng)：Q=（）。C是條件屬性，D是決策屬性。在這個(gè)信息系統(tǒng)中，子集A包含于Q稱(chēng)為不可分辨關(guān)系，用IND（A）表示 IND(

4、A)是一個(gè)等價(jià)關(guān)系，IND(A)把U劃分為若干等價(jià)類(lèi)。這些等價(jià)類(lèi)是A中那些有不可分辨關(guān)系的對(duì)象的集合，這些劃分集表示為U/IND(A). 約簡(jiǎn)是指保持不可分辨關(guān)系的最小的屬性集。相對(duì)約簡(jiǎn)屬性集P,P包含于Q，P稱(chēng)為是Q的約簡(jiǎn)，表示為RED Q（P），如果P在Q的集合中式最小的，Q中所有不可約去的集合稱(chēng)為Q的核，并用CORE（Q）表示，當(dāng)aP,aCORE（Q），如果將屬性a從P中刪除，原始系統(tǒng)的決策性能將不會(huì)改變。否則,原系統(tǒng)的決定性能將會(huì)改變。約簡(jiǎn)和核使核心屬性在決策問(wèn)題中起很重要的作用,而且我們可以用它來(lái)創(chuàng)建簡(jiǎn)單規(guī)則的信息系統(tǒng)。Skowron提出了區(qū)分矩陣，這是一種解決代表性知識(shí)的方法。令S

5、=(U,Q,V,f)是一種信息系統(tǒng)。U=X1,X2Xn10;使用區(qū)分矩陣S,表示為M（S），定義n×n的矩陣為: for 因此，是識(shí)別對(duì)象和的所有屬性集。在區(qū)分矩陣中，因?yàn)?，?duì)角元素為空集。因此，在區(qū)分矩陣中上三角部分可以忽略。3 算法3.1基本算法在信息系統(tǒng)中, 當(dāng)我們比較對(duì)象Xi和對(duì)象Xi+1，條件屬性值和決策屬性值有四種可能的組合。表1給出了四種情況,通過(guò)對(duì)比兩個(gè)對(duì)象的條件屬性和決策屬性值。C表示條件屬性集合,C=c1,c2,cn,和D是一個(gè)決策屬性, D=d1、d2,dk。 如果我們假設(shè)有一個(gè)條件屬性“收入”和一個(gè)決策屬性的“買(mǎi)一部計(jì)算機(jī)”。這個(gè)條件屬性“收入”有兩個(gè)屬性值、

6、低和高,這個(gè)決策屬性的“買(mǎi)一部計(jì)算機(jī)”有兩個(gè)屬性值,買(mǎi)還是不買(mǎi)。表1 兩對(duì)象的對(duì)比條件情況條件屬性值決策屬性值（種類(lèi)）條件屬性Ci的判斷對(duì)象xi和xi+11相同相同積極2相同不同消極3不同相同消極4不同不同積極1) 情況1，如果信息系統(tǒng)只有一個(gè)規(guī)則，表1的情況1，我們可以立即直接推導(dǎo)情況1的規(guī)則，這種價(jià)值可能是積極的。表2直接歸納了這種類(lèi)型。表2 情況1：兩個(gè)對(duì)象的對(duì)比顧客ID收入（條件屬性）買(mǎi)電腦（決策屬性）規(guī)則條件屬性收入的判斷1低不買(mǎi)收入=低之后不買(mǎi)電腦積極2低不買(mǎi)2)情況2：從表1中情況2推導(dǎo)，表3給出了含糊的結(jié)果，這個(gè)結(jié)果可能是消極的。表3 情況2：兩個(gè)對(duì)象的對(duì)比顧客ID收入（條件屬

7、性）買(mǎi)電腦（決策屬性）規(guī)則條件屬性收入的判斷1低買(mǎi)收入=低之后電腦買(mǎi)還是不買(mǎi)消極2低不買(mǎi)3）情況3：在同一個(gè)等價(jià)類(lèi)的兩個(gè)事例可以歸納出兩種規(guī)則。可能的結(jié)果是消極的,因?yàn)樵诜诸?lèi)相同時(shí)，情況3比情況1的規(guī)則更多。決策樹(shù)的構(gòu)造的重要的一個(gè)步驟就是選擇能夠產(chǎn)生“最小樹(shù)”的節(jié)點(diǎn)屬性。一個(gè)最小樹(shù)有相對(duì)較少的樹(shù)枝：決策規(guī)則。表4 情況3：兩個(gè)對(duì)象對(duì)比顧客ID收入（條件屬性）買(mǎi)電腦（決策屬性）規(guī)則條件屬性收入的判斷1高買(mǎi)1）收入=高之后不買(mǎi)電腦2）收入=低之后電腦不買(mǎi)消極2低不買(mǎi)4） 情況4.第四種情況是積極的，很好地區(qū)分了屬于不同分類(lèi)的兩個(gè)實(shí)例。表5顧客ID收入（條件屬性）買(mǎi)電腦（決策屬性）規(guī)則條件屬性收入

8、的判斷1高買(mǎi)1）收入=高之后買(mǎi)電腦2）收入=低之后電腦不買(mǎi)積極2低不買(mǎi)情況3和4可以代表屬于相同類(lèi)別或不同類(lèi)別對(duì)象的典型例子。我們將應(yīng)用價(jià)值函數(shù)表示情況3和4計(jì)算分類(lèi)價(jià)值。我們的方法使用核心屬性,包括區(qū)別矩陣的功能,貢獻(xiàn)函數(shù)代替熵函數(shù)。Skowron和Rauszer認(rèn)為區(qū)別矩陣是一個(gè)n×n矩陣關(guān)于cij定義為(cij)=aQ:a(xi)a(xj) 如果d(xi)d(xj)對(duì)i，j=1,2n，a是條件屬性和d是決策屬性10.在這個(gè)例子中，條件屬性a是積極的。我們建議算法用Skowron 和Rauszer的想法,而且考慮對(duì)象的關(guān)系在同一類(lèi)型,并確定這是(cij)=aA:a(xi)a(xj

9、) 如果d(xi)=d(xj);條件屬性為消極情況10。熵cij是判別對(duì)象xi和xj的所有屬性集的。基于上述討論,我們分類(lèi)貢獻(xiàn)函數(shù)的定義如下:積極情況：（）I(Cijak)是（Cijak）的指數(shù)函數(shù)。如果條件屬性ak是cij的元素，則I（cijak）否則它為0.CCp表示消極情況分類(lèi)價(jià)值。分類(lèi)價(jià)值函數(shù),分類(lèi)貢獻(xiàn)是條件屬性ak的積極和消極情況之和。cijak空集。CCT表示整個(gè)分類(lèi)貢獻(xiàn)。從公式5中，我們可以選擇最大CCT（ak）的屬性。該屬性的最大貢獻(xiàn)對(duì)分類(lèi)。在區(qū)別矩陣有三個(gè)例子關(guān)于粗糙集：其一，沒(méi)有核心的屬性，第二個(gè)只有一個(gè)核心屬性，第三個(gè)案例不止一個(gè)核心屬性。該算法生成的決策樹(shù)如下：1）生成

10、區(qū)別矩陣，然后三種情況是：2）案（一）：如果沒(méi)有核心屬性，衡量約簡(jiǎn)中的每個(gè)屬性分類(lèi)貢獻(xiàn)CCT(aK）和選擇一CCT(aK）最大值 的個(gè)節(jié)點(diǎn)的條件屬性。 案例（二）：如果只有一個(gè)核心屬性，選擇為核心節(jié)點(diǎn)的屬性。 案例（三）：如果有多于一個(gè)核心屬性，測(cè)量分類(lèi)貢獻(xiàn)CCT(aK）的每個(gè)核心屬性。 3）選擇擴(kuò)展屬性作為每個(gè)級(jí)節(jié)點(diǎn)。 4）重復(fù)上述過(guò)程遞歸，直到在一個(gè)節(jié)點(diǎn)的對(duì)象都屬于同一類(lèi)。3.2 擴(kuò)展算法我們所建議的算法對(duì)比兩個(gè)對(duì)象，計(jì)算他們的對(duì)分類(lèi)的貢獻(xiàn)，并選擇更可區(qū)分的屬性作為一個(gè)節(jié)點(diǎn)。除了我們的算法，我們假設(shè)如果有焦點(diǎn)類(lèi)，它會(huì)產(chǎn)生更多的有意義的和有效

11、的結(jié)果。焦點(diǎn)分析的重點(diǎn)是在目標(biāo)市場(chǎng)營(yíng)銷(xiāo)，特殊的客戶需求分析，欺詐檢測(cè)重要，在不尋常情況的模型5。在第3.1節(jié)，我們的算法考慮內(nèi)在和超分類(lèi)的值，并選擇最大CCT(aK）的條件屬性aK作為一個(gè)節(jié)點(diǎn)，在擴(kuò)展算法中，我們只比較焦點(diǎn)分類(lèi)組與超類(lèi)的類(lèi)值值組，找出最大CCT(aK）。那沒(méi)有消極的例子，它可以選擇一個(gè)更極大貢獻(xiàn)的特殊屬性，分類(lèi)決策屬性值 另一個(gè)類(lèi)。例如，我們可以假設(shè)保險(xiǎn)數(shù)據(jù)表是在表6中所示的方式排列。如果我們?cè)诎才疟ｋU(xiǎn)='N'，我們?cè)诒容^和計(jì)算編號(hào)N的分類(lèi)函數(shù)（客戶ID 6，7和9）編號(hào)Y（客戶ID 1，2，3，4，5，8和10）。表6 區(qū)分矩陣ID年齡率（a）保險(xiǎn)費(fèi)

12、用率(b)會(huì)費(fèi)(c)健康檢查(d)安排保險(xiǎn)(D)145MNY255OYY344MNY455MNY535MNY654MYN724MYN845MNY955MYN1045MNY繼3.1節(jié)的程序，我們?yōu)楸?做區(qū)分矩陣如表7所示。表7 區(qū)分矩陣為表6123456789101a,b,da,b,da,d2b,ca,b,cc3a,b,da,da,b,d4b,da,b,dd5a,b,da,b,da,d678a,b,da,b,da,d910a,b,da,b,da,d核可以被定義為區(qū)分矩陣的所有單元素熵的集。表7 呈現(xiàn)出兩個(gè)核心屬性的c，d。我們可以計(jì)算C和D的分類(lèi) 貢獻(xiàn)如下：我們考慮在3.1節(jié)的負(fù)面情況

13、，但無(wú)論如何，當(dāng)我們使用擴(kuò)展算法時(shí)我們不考慮負(fù)面情況。當(dāng)CCp（d）是較CCp（c）更大，然后屬性d基于對(duì)分類(lèi)貢獻(xiàn)函數(shù)為標(biāo)準(zhǔn)為基礎(chǔ)而選為根節(jié)點(diǎn) 。這將產(chǎn)生如圖1所示的子樹(shù)。圖1 生成的子樹(shù)我們可以申請(qǐng)相同的子集進(jìn)程d = 直到在一個(gè)節(jié)點(diǎn)的對(duì)象都屬于同一類(lèi)。示例的結(jié)果如下，由這個(gè)例子中，判決結(jié)果樹(shù)，如圖2所示。健康檢查=N ，則安排保險(xiǎn)=Y；健康檢查=N ，會(huì)費(fèi)=O則安排保險(xiǎn)=Y；健康檢查=N ，會(huì)費(fèi)=M則安排保險(xiǎn)=N。圖2： 使用擴(kuò)展算法的決策樹(shù)結(jié)構(gòu)4 實(shí)驗(yàn)結(jié)果我們實(shí)施了來(lái)自美國(guó)加州大學(xué)歐文分校（UCL）機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)建議方法和擴(kuò)展方法在小樣本數(shù)據(jù)集。在先前的決定樹(shù)的研究中，yang

14、et，MinZ和JAIN，和 Tu和chung對(duì)比了他們提出的算法ID3 13，6，11。要測(cè)試我們所提出算法和擴(kuò)展算法的有效性和的準(zhǔn)確性，我們必須比較那些使用ID3算法獲得結(jié)果與算法C4.5的結(jié)果 。在WEKA3.4中的應(yīng)用了ID3和C4.5算法，這是一個(gè)基于數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)算法集合，這種算法是由Frank等4開(kāi)發(fā)的。（http:/www.cs.waikato.ac.nz/ml/weka/）。建議的算法在C中實(shí)現(xiàn)，要求英特爾奔騰處理器2.80千兆赫，2.81 GHz的CPU時(shí)鐘速度，在樣本數(shù)據(jù)集和數(shù)值數(shù)據(jù)中我們忽視了丟失的數(shù)據(jù)，并用10倍交叉驗(yàn)證。我們?cè)黾恿藰颖尽癶eart-h”和

15、“credit-g”來(lái)探討模式中的變化。表8顯示了每個(gè)算法的精度和表9列出他們的規(guī)則。在圖3顯示規(guī)則的數(shù)量。該建議的方法和擴(kuò)展方法構(gòu)造更簡(jiǎn)單決策樹(shù)方法比那些ID3方法所創(chuàng)建的。 C4.5算法性能更好，但如何才能解釋結(jié)果只用一個(gè)規(guī)則的情況下，如在心臟-h時(shí)，甲狀腺和生病。我們的算法似乎更有說(shuō)服力。表8 使用UCI數(shù)據(jù)四種不同決策樹(shù)方法規(guī)則數(shù)量規(guī)則數(shù)量數(shù)據(jù)庫(kù)ID3C4.5建議算法擴(kuò)展算法隱形眼鏡8455心高（100）1011213動(dòng)物園9766淋巴64141917心高（285）44265信貸 (500)309412522信貸(1000)708544235甲狀腺10011214生病8911

16、013表9 UCI數(shù)據(jù)的四種決策樹(shù)方法的精確度數(shù)據(jù)集元組條件屬性分類(lèi)精確度ID3C4.5建議算法擴(kuò)展算法隱形眼鏡24337183100100心高（100）1005296979393動(dòng)物園101157929296100淋巴14815475799390心高（285）2855275808197信貸 (500)500112637196100信貸(1000)1000112627198100甲狀腺377121492929294生病377320293939395我們使用的數(shù)據(jù)集的10倍交叉驗(yàn)證測(cè)試方法的準(zhǔn)確性。圖4給出了測(cè)試結(jié)果。在大多數(shù)情況下，我們的方法比C4.5算法準(zhǔn)確，心臟- H的例外。建議和擴(kuò)展算法

17、是有意義的事情，由此產(chǎn)生的結(jié)果樹(shù)考慮這些屬性，這些屬性能提供最大分的類(lèi)貢獻(xiàn)。圖3 規(guī)則數(shù)量的比較5 結(jié)論構(gòu)建一個(gè)最佳分類(lèi)決策樹(shù)是一個(gè)完整不確定多項(xiàng)式（NP完成）的問(wèn)題，因此它不能實(shí)現(xiàn)一個(gè)有效的算法。相反，必須采用啟發(fā)式算法11。建議的算法是一種邏輯推理樹(shù)的新概念。此外，當(dāng)擴(kuò)大算法有一個(gè)重點(diǎn)分類(lèi)，擴(kuò)大算法的性能更好的時(shí)候。  在UCI數(shù)據(jù)實(shí)驗(yàn)證明新概念的性能比ID3決策樹(shù)方法和C4.5方法更好。不過(guò)，建議和擴(kuò)展算法是獨(dú)一無(wú)二的，因?yàn)樗鼈兪褂么植诩碚摵头诸?lèi)屬性以最大貢獻(xiàn)的概念為基礎(chǔ)的對(duì)象。此外，建議的方法沒(méi)有數(shù)據(jù)預(yù)處理可誘導(dǎo)分類(lèi)規(guī)則。字符和象征型數(shù)據(jù)可以被應(yīng)用。盡管有上述優(yōu)點(diǎn)，當(dāng)決策表

18、時(shí)有許多不同的屬性或?qū)傩灾涤?jì)算約簡(jiǎn)集所需的時(shí)間可能會(huì)很長(zhǎng)，以及計(jì)算的最小約簡(jiǎn)問(wèn)題是NP -難問(wèn)題。Bazan等。建議減少約簡(jiǎn)計(jì)算的一個(gè)更有效的方法2。在我們的算法中包括歸納需要進(jìn)一步研究。參考文獻(xiàn)1. Bai, J., Fan, B., Xue, J.: Knowledge representation and acquisition approach based on decision tree. In: Proceedings of the, International Conference on Natural2. Language Processing and Knowledge En

19、gineering (October 2629, 2003), pp. 33538 (2003)3. Bazan, J., Skowron, A., Synak, P.: Dynamic reduct as a toll for extracting laws from decision tables. In: Ra, Z.W., Zemankova, M. (eds.) ISMIS 1994. LNCS, vol. 869, pp. 346355. Springer, Heidelberg (1994)4. Duda, R., Hart, P., Stork, D.: Pattern Cla

20、ssification, 2nd edn. Wiley, New York (2001)5. Frank, E., Hall, M., Trigg, L., WEKA, (2003), ttp:/www.cs.waikato.ac.nz/ml/weka6. Han, J., Kamber, M.: Data Mining, 2nd edn. pp. 285289 (2006)7. Minz, S., Jain, R.: Rough set based decision tree model for classification. In: Kambayashi,Y., Mohania, M.K.

21、, Wöß, W. (eds.) Data Warehousing and Knowledge Discovery. LNCS,vol. 2737, pp. 172181. Springer, Heidelberg (2003)8. Pawlak, Z.: Rough sets. International Journal of Computer and Information Science 11(1982)9. Quinlan, J.R.: Induction of decision trees. Machine Learning I, 81106 (1986)10. Quinlan, J.R.: Improved use of continuous attributes in C4.5. Artificial Intelligence 4, 7790 (1996)11. Skowron, A., Rauszer, C.M.: The discernibility matrices and functions in information systems, Institute of Computer