基於概率粗糙集的決策樹生成方法

2023-10-24 16:19:32

專利名稱：基於概率粗糙集的決策樹生成方法
技術領域：
本發明涉及一種決策樹生成算法。特別是涉及一種基於概率粗糙集的決策樹生成方法。

背景技術：
決策樹是一種非常直觀的知識表示方法，同時也是高效的分類器。目前比較著名的決策樹生成算法是Quinlan.J 1986年提出的以信息熵下降速度為啟發信息選取節點的ID3算法、C4.5等，然而如何生成較小的樹，以及防止數據過擬合等問題，一直是研究的重點。
1.決策樹 決策樹是一個預測模型；他代表的是對象屬性與對象值之間的一種映射關係。樹中每個節點表示某個對象，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結點則對應從根節點到該葉節點所經歷的路徑所表示的對象的值。
決策樹有幾種產生方法

分類樹分析是當預計結果可能為兩種類型(例如男女，輸贏等)使用的概念。


回歸樹分析是當局域結果可能為實數(例如房價，患者住院時間等)使用的概念。


CART分析是結合了上述二者的一個概念。CART是Classification AndRegression Trees的縮寫.

enCHAID(Chi-Square Automatic Interaction Detector) 其中最著名的算法是ID3，C4.5和C5.0生成樹算法。他們使用了信息學理論中熵的概念。
2.粗糙集 20世紀70年代，波蘭學者Z.Pawlak和一些波蘭科學院，波蘭華沙大學的邏輯學家們，一起從事關於信息系統邏輯特性的研究。粗糙集理論就是在這些研究的基礎上產生的。1982年，Z.Pawlak發表了經典論文Rough Sets，宣告了粗糙集理論的誕生。粗糙集理論的觀點是「知識(人的只能)就是一種對對象進行分類的能力」，這裡的對象就是我們所言及的任何事物。
設U是我們感興趣的對象組成的非空有限集合，稱為一個論域。論域U的任何一個子集

稱為論域U的一個概念或範疇。為了規範化，我們認為空集也是一個概念，稱為空概念。
給定一個論域U和U上的一簇等價關係S，稱二元組K＝(U，S)是關於論域U的一個知識庫或近似空間。
給定論域U和U上的一簇等價關係S，若

且，

則∩P(P中所有等價關係的交集)仍然是論域U上的一個等價關係，稱為P上的不可分辨關係，記為IND(P)，也常簡記為P。而且， 集合的上近似和下近似。給定知識庫K＝(U，S)，其中U為論域，S表示論域U上的等價關係簇，則

和論域U上的一個等價關係R∈IND(K)，我們定義子集X關於知識的上近似和下近似分別為



集合

稱為X的R邊界域。POSR(X)＝R(X)稱為X的R正域。

稱為X的R負域。下近似R(X)或正域POSR(X)是由那些根據知識R判斷肯定屬於X的論域U中的元素組成的集合；上近似

是由那些根據知識判斷肯定屬於和可能屬於X的論域U中的元素組成的集合；R的邊界BNR(X)是由那些根據知識R既不能判斷肯定屬於X也不能判斷肯定不屬於X的論域中元素組成的集合；R負域NEGR(X)表示根據知識R判斷肯定不屬於X的論域U中元素組成的集合。
由於粗糙集中的影響關係過於嚴格，在實際應用中出現了許多問題，所以人們將二元等價關係推廣成了一般的二元關係，因此概率粗糙集中引入概率下近似的概念和概率上近似的概念，來更好的反應現實數據中可能出現的數據噪聲等問題。
概率下近似 設β為一個閥值，且0.5＜β≤1，則概率下近似定義為 RβX＝{x∈U P(X/[x]R)≥β} 其中 依賴度 依賴度反映了屬性之間的依賴程度。
w＝|POSAB|/|U 表示了，B對A的依賴程度，記作
知識約簡與核 知識約簡是智能信息處理中佔有重要的地位，也是粗糙集理論的核心內容之一。一般來講，知識庫中的知識並不是同等重要的，甚至其中某些知識是不必要的，或者說是冗餘的。所謂的知識約簡指的是在保持知識庫分類能力不變的條件下，刪除其中不必要的知識。
知識的約簡中有兩個重要的概念約簡和核。
給定一個知識庫K＝(U，S)和知識庫中的一個等價關係族


若 IND(P)＝IND(P-{R}) 成立，則稱知識R為P中不必要的，否則稱R為P中必要的。
如果對於每一個R∈P，R都為P中重要的，則稱P為獨立的，否則稱P是依賴的或不獨立的。
知識的約簡給定一個知識庫K＝(U，S)和知識庫中的一個等價關係族

對於任意的

若G滿足以下兩條 (1)G是獨立的 (2)IND(G)＝IND(P) 則稱G是P的一個約簡，記為G∈RED(P)，表示P的全體約簡組成的集合。顯然知識的任何一個約簡與知識本身對知識庫中的任意一個範疇的表達都是等同的，即他們對論域的分類能力相同。一般而言知識的約簡不唯一，可以有多種約簡。
知識的核給定一個知識庫K＝(U，S)和知識庫中的一個等價關係族

對於任意的R∈P，若R滿足 IND(P-{R})≠IND(P) 則稱P為R中必要的，P中所有必要的知識組成的集合稱為P的核，即為CORE(P)。核具有唯一性。
CORE(P)＝∩RED(P) 知識的相對約簡與相對核 知識的相對約簡給定一個知識庫K＝(U，S)和知識庫上的兩個等價關係族P，

對任意的

若G滿足以下兩條， (1)G是Q獨立的，即G是P的Q獨立子族， (2)posG(Q)＝posP(Q) 則稱G是P的一個Q約簡，或稱為P相對於Q的一個約簡，記為G∈REDQ(P)，其中G∈REDQ(P)表示P的全體Q約簡組成的集合。
顯然，知識的任何一個相對約簡與知識本身對知識庫中的任意一個範疇的表達都是相同的，即他們對論域的分類能力相同。一般而言，知識的相對約簡不唯一，可以有多個。
知識的相對核給定一個知識庫K＝(U，S)和知識庫上的兩個等價關係族P，

對任意的R∈P，若R滿足 posIND(P-{R)(IND(Q))＝posIND(P)(IND(Q)) 則稱R為P中Q必要的，P中所有所有Q必要的知識組成的集合稱為P的Q核，或稱為P的相對於Q的核，記為COREQ(P)。知識的相對核是唯一的。
COREQ(P)＝∩REDQ(P) 目前，一些基於粗糙集的決策樹生成算法不能很好的解決數據噪聲等問題。


發明內容
本發明所要解決的技術問題是，提供一種基於概率粗糙集理論，能夠有效的解決數據噪聲問題的基於概率粗糙集的決策樹生成方法。
本發明所採用的技術方案是一種基於概率粗糙集的決策樹生成方法，包括如下步驟 1)計算決策屬性對於條件屬性的依賴度 首先設置概率下近似中的β，其中0.5＜β≤1，通過使用概率下近似公式，計算每一條件屬性Xi，對決策屬性Y的概率下近似，然後計算決策屬性對條件屬性的依賴度，其中概率下近似計算公式如下所示， XiβY＝{x∈U|P(Y/[x]Xi)≥β} 則Y對Xi依賴度為， 其中，U代表論域，即全體記錄的集合，|U|代表記錄的個數； 2)對數據進行相對屬性約簡，獲取決策樹節點集 首先要獲得相對核，相對核的計算公式如下， COREQ(P)＝∩REDQ(P) 然後我們每次在剩餘的節點中選擇一個條件屬性，使得選擇此條件屬性後對於決策屬性的影響最大，也就是決策屬性對於當前屬性的集合依賴度最大。我們依次增加節點個數，直到獲得最大的獨立集，從而得到構造決策樹所需要節點集； 3)通過決策樹的節點集構造決策樹 建立決策樹的方式是，讓依賴度最大的節點作為根節點，然後對於分支，重新計算剩餘節點的依賴度信息，同時選擇依賴度最大的節點。
當節點不能確定最終類型，則通過重新計算依賴度信息，將剩餘節點中的依賴度最大的作為分支節點，從而生成最終的決策樹。
本發明的基於概率粗糙集的決策樹生成方法，最核心的思想就是首先通過相對約簡消除沒有用的屬性，這樣就可以得到用於生成決策樹的節點。然後始終選擇依賴度最大的節點來擴展生成樹，最終就生成了我們需要的決策樹。本發明能夠有效的解決數據噪聲問題。



圖1是本發明生成的決策樹。

具體實施例方式 下面結合實施例和附圖對本發明的基於概率粗糙集的決策樹生成方法做出詳細說明。
本發明的基於概率粗糙集的決策樹生成方法，涉及到使用概率粗糙集的知識生成決策樹，粗糙集是一種處理不確定性知識的有效工具，目前在數據挖掘領域應用十分廣泛。然而傳統的粗糙集由於對於影響的要求過於嚴格，因此在那些擁有數據噪聲等因素影響的情況下，無法有效的使用，而由於概率粗糙集模型中引入了概率下近似的概念，因此可以有效的解決這種數據噪聲問題，同時本發明使用基於粗糙集的屬性約簡方法，對於初始的數據進行進預處理，去除那些對於最終決策屬性沒有影響的屬性，然而要想獲取最小的約簡是一個NP難的問題，因此本發明首先通過分明矩陣法獲取核，然後每次在剩餘的條件屬性選擇一個條件屬性，使得選擇此條件屬性後對於決策屬性的影響最大，也就是決策屬性對於當前屬性的集合依賴度最大，依次增加節點個數，直到獲得最大的獨立集，這樣就可以獲得較佳的節點集合，同時採用的是概率粗糙集模型，因而可以防止過擬合問題。
本算法的實現方法如下 1、計算決策屬性對於條件屬性的依賴度 我們首先設置概率下近似中的β，其中0.5＜β≤1，我們一般取β的值應儘可能大，一般應在0.95以上，否則反而會由於β過小讓結果出現誤差，這與我們同時設置β來處理數據噪聲問題的初衷不符。通過使用概率下近似公式，計算每一條件屬性Xi，對決策屬性Y的概率下近似，然後計算決策屬性對條件屬性的依賴度。其中概率下近似計算公式如下所示， XiβY＝{x∈U|P(Y/[x]Xi)≥β} 則Y對Xi依賴度為， 其中，U代表論域，即全體記錄的集合，|U|代表記錄的個數；算法的描述如下， For對於每一個條件屬性Xi 計算其對決策屬性的依賴度信息，公式為 End 2、對數據進行相對屬性約簡，獲取決策樹節點集 首先要獲得相對核，相對核的計算公式如下， COREQ(P)＝∩REDQ(P) 我們可以通過分明矩陣法獲得相對核，這是一個很有效的已知算法，然後我們每次在剩餘的節點中選擇一個條件屬性，使得選擇此條件屬性後對於決策屬性的影響最大，也就是決策屬性對於當前屬性的集合依賴度最大，其中依賴度的計算公式如下所示， 我們依次增加節點個數，直到獲得最大的獨立集，所謂的獨立集就是我們上面提到的使得屬性集合中各個屬性都是必要的，所謂最大獨立集就是再添加任何一個屬性，此屬性都不再是必要的。此時最大的獨立集就是我們需要的決策樹的節點集。因此通過此種方法就可以去除不必要的條件屬性，同時也可以獲得符合我們需要的最終節點集。
屬性分為條件屬性和決策屬性，所謂的決策屬性是指我們要推出的結果屬性，如試驗中的Y，其餘的屬性為條件屬性，如試驗中的X1，X2，X3，X4。
因為可以有多種條件屬性的組合可以推出最終的決策屬性，如X1，X2可以推出Y，那麼X1，X2，X3一定也可以推出Y。
其中相對核是所有這些組合的交集，因此相對核指的就是必不可少的條件屬性，可以通過現有的公式計算相對核。
算法描述如下， Begin 首先獲取相對核，設其集合為S While不是最大獨立集 在剩餘的條件屬性中選擇添加此屬性後， 整個集合對決策屬性的影響最大的條件屬性，將其加入集合S End End 3、通過決策樹的節點集構造決策樹 通過第二步，我們已經獲得了決策樹中將會出現哪些節點，因此我們這一步的工作就是建立決策樹，建立決策樹的方式是，讓依賴度最大的節點作為根節點，然後對於分支，重新計算剩餘節點的依賴度信息，同時選擇依賴度最大的節點。
算法描述如下 設決策樹節點集中有p個節點 輸入(X1，X2，……，Xp，Y) 輸出決策樹 Begin 首先在節點集合中，選擇依賴度最大的節點作為根節點，如果其不能確定決策屬性的類型，則根據其取值建立相應的分支，並將各個分支存入鍊表T While T不為空 從T中取一個節點N If節點N不能確定決策類型 根據N的屬性值繼續劃分分支 在各個分支上計算決策屬性對於剩餘節點的依賴度信息 其中剩餘節點是指沒有出現在從根節點到此節點的節點序列中的節點 並將依賴度最大的屬性作為分支節點，並將分支信息存入T End 從T中刪除N這個節點 End End 通過以上方式，如果節點不能確定最終類型，則通過重新計算依賴度信息，將剩餘節點中的依賴度最大的作為分支節點，這樣就可以生成最終的決策樹。
下面給出一實例 1、計算各個條件屬性對決策屬性的依賴度，我們用r(X，Y)表示依賴度，則 各個屬性的等價類如下 U/X1＝{{1，2，3，13，14，15，16，19，20，25} {4，5，11，12，21，22，23}{6，7，8，9，10，17，18，24}} U/X2＝{{1，2，3，4，5，8，10，23，25} {6，7，13，14，17，18，19，20，21，22，24}{9，11，12，15，16}} U/X3＝ {{1，2，3，4，5，6，7，13，14，21，22，24，25}{8，9，10，11，12，15，16，17，18，19，20，23}} U/X4＝{{1，4，6，8，13，15，17，23，25} {3，5，7，9，12，14，16，18，19，22}{2，10，11，20，21，24}} U/Y＝ {{1，2，3，6，7，8，9，10，13，14，17，18，24，25}{4，5，11，12，15，16，19，20，21，22，23}} r(X1，Y)＝0.6 r(X2，Y)＝0 r(X3，Y)＝0 r(X3，Y)＝0 2、對數據進行相對屬性約簡，獲取決策樹節點集 我們通過計算得到的相對核為X1，X3，我此時已經可以正確分類，因此不需要再擴充節點，否則我們只需要選擇使得加入節點後對Y的影響最大的屬性即可，也就是使得Y對當前的屬性集合的依賴度最大，因此在本實驗中決策樹的節點集為{X1，X3} 3、通過決策樹的節點集構造決策樹 由於Y對X1的依賴度最大，因此首先我們選擇X1作為根節點，然後對於X1分別取1，2，3，然後對於不能正確分類的X1＝1的情況，我們繼續使用X3來分類，當X3取值為1時，結果為N，當X3取值2時，結果為Y嗎，因此，可以得到一個最終的決策樹如圖1所示。
通過對本算法的分析，我們可以看出，本算法首先獲取相對核，然後我們每次在剩餘條件屬性中選擇一個條件屬性，使得選擇此條件屬性後對於決策屬性的影響最大，直到獲得最大獨立集，此時我們就得到了構造決策樹時使用的節點集合，同時通過使用概率下近似可以更好的解決數據噪聲問題，當數據中存在數據噪聲時，由於我們使用的概率下近似，可以容忍一定程度的噪聲，因此得到具有更好泛化性的決策樹。
下面表1是本發明的實驗數據信息。
表1


權利要求
1.一種基於概率粗糙集的決策樹生成方法，其特徵在於，包括如下步驟
1)計算決策屬性對於條件屬性的依賴度
首先設置概率下近似中的β，其中0.5＜β≤1，通過使用概率下近似公式，計算每一條件屬性Xi，對決策屬性Y的概率下近似，然後計算決策屬性對條件屬性的依賴度，其中概率下近似計算公式如下所示，
則Y對Xi依賴度為，
其中，U代表論域，即全體記錄的集合，|U|代表記錄的個數；
2)對數據進行相對屬性約簡，獲取決策樹節點集
首先要獲得相對核，相對核的計算公式如下，
COREQ(P)＝∩REDQ(P)
然後我們每次在剩餘的節點中選擇一個條件屬性，使得選擇此條件屬性後對於決策屬性的影響最大，也就是決策屬性對於當前屬性的集合依賴度最大。我們依次增加節點個數，直到獲得最大的獨立集，從而得到構造決策樹所需要節點集；
3)通過決策樹的節點集構造決策樹
建立決策樹的方式是，讓依賴度最大的節點作為根節點，然後對於分支，重新計算剩餘節點的依賴度信息，同時選擇依賴度最大的節點。
2.根據權利要求1所述的基於概率粗糙集的決策樹生成方法，其特徵在於，當節點不能確定最終類型，則通過重新計算依賴度信息，將剩餘節點中的依賴度最大的作為分支節點，從而生成最終的決策樹。
全文摘要
一種基於概率粗糙集的決策樹生成方法，步驟為1)計算決策屬性對於條件屬性的依賴度；2)對數據進行相對屬性約簡，獲取決策樹節點集；3)通過決策樹的節點集構造決策樹，建立決策樹的方式是，讓依賴度最大的節點作為根節點，然後對於分支，重新計算剩餘節點的依賴度信息，同時選擇依賴度最大的節點。本發明最核心的思想就是首先通過相對約簡消除沒有用的屬性，這樣就可以得到用於生成決策樹的節點。然後始終選擇依賴度最大的節點來擴展生成樹，最終就生成了我們需要的決策樹。本發明能夠有效的解決數據噪聲問題。
文檔編號G06F17/30GK101819604SQ20101018102
公開日2010年9月1日 申請日期2010年5月24日 優先權日2010年5月24日
發明者劉江, 林利 申請人:天津大學