一種新的基于粗糙集的概念模糊化決策樹算法

摘 要：提出了一種新的基于粗糙集的概念模糊化決策樹算法。本算法將利用屬性歸納和概念模糊化的方法刪除不能反映概化信息的屬性，結合模糊粗糙決策樹算法，提取對決策有潛在價值的知識和規則。

關鍵詞：粗糙集；屬性歸納；模糊化；決策樹

本文采用決策屬性對分類屬性的依賴度作為決策樹構建過程中的屬性選擇的依據，針對海量數據在作語義決策時會遇到數據重復、數據冗余等情況，利用屬性歸納和概念模糊化的方法刪除不能反映概化信息的屬性，模糊化反映全局信息的屬性，結合模糊粗糙決策樹算法，提取對決策有潛在價值的知識和規則。

一、基于概念層次的模糊粗糙決策樹算法

1.模糊粗糙決策樹

定義4：模糊數學用0～1間的數字，來刻畫某個對象隸屬于某個概念的程度，這個數字就稱為隸屬度。

例1中各個條件屬性采用的隸屬度函數①表示如下：

■

圖1“收入”和“年齡”兩個條件屬性的隸屬度函數

■，

X∈{高，中，低}

■，

X∈{經常，一般}

定義5：決策屬性對條件屬性的依賴度是決策樹歸納的屬性選擇的依據。利用依賴度γ進行模糊劃分的方法遵循以下3個策略：

（1）如果完全是以模糊方法進行的劃分，則■（y）=1；

（2）如果一部分是以模糊方法進行的劃分，則0<■（y）<1；

（3）如果完全不是以模糊方法進行的劃分，則■（y）>1；

依賴度的計算步驟如下：

（1）計算Fjk在模糊正域的隸屬度：

μl（Fjk）=■max{1-■（xij），μl（yi）}

？坌k=1，···，cj；？坌l=1，···，q

（2）計算xj對模糊正域的隸屬度：

■

（3）計算y在FV/xj）下的隸屬度：

■

以附錄年齡屬性（設為C）為例，說明依賴度的計算過程如下：

Step1：計算劃分在模糊正域的隸屬度

max[1-μold（x1c），μdon'tbuy]=1

μdon’tbuy（old）=inf{1，1，1，1，1，1，1，1，0.1，0.75，1，1，1，1}=1

μbuy（old）=inf{0，1，0.1，1，1，1，1，1，0.1，1，1，0.1，0.5，1}=0

Step2：計算對Xc模糊正區域的隸屬度

μpos（old）=sup{μdon'tbuy（old），μbuy（old）}=1

■

Step3：計算y對C的依賴度為

γc（y）=■=0.3164

同理γ性能要求=0.2857，γ收入=0，γ使用頻率=0，所以選擇年齡屬性為根結點。

定義6：模糊分類規則的真實度β的定義：

當μ=min（■，■）時

β（FV∩Fjk，l）=■

在決策樹的構建過程中，計算每個結點對應的規則真實度β，是一個很重要的參數。如果β大于規定的閾值βth，則該結點作為葉結點，并產生一條模糊分類則，并且結束該分支。

以表2為例，在定義2得到的結果基礎上，劃分根結點為{青年，中年，老年}，訓練模式為{2，5，6，8，14}，{4，7，10，11，13}，{1，3，9，12}，從根結點劃分的老年分支，肯定買電腦的因素1≥βth，它能產生葉節點“不購買”。對中年分支β（中年，購買）=0.4566，β（中年，購買）=0.5454，由于β<βth，所以它應該被繼續被劃分。

2.基于概念層次的模糊粗糙決策樹算法

本算法的主要思想是：對于原始數據給定每層概念范圍的離散屬性，利用面向屬性的歸納進行語義概念提升和概念模糊化；對于沒有給定范圍的概念的連續屬性，在確定劃分的聚類個數后，利用k-means聚類算法進行屬性的劃分。在此基礎上進一步建立模糊粗糙決策樹。通過特征空間的模糊劃分計算每個屬性的依賴度γ，選擇γ最高的結點作為父結點，利用其模糊劃分產生子結點，如果該結點的子結點分割模糊熵大于閾值即βchild-node≥βth，則子結點作為葉結點，否則繼續劃分，若還存在候選結點則循環以上的操作。

二、總結

我們用UCI數據集中adult數據庫部分數據作為數據集來驗證算法的有效性。它是Barry Becker在1994年從人口普查數據庫中提取的，為了直觀起見，我們選擇其中連續屬性（年齡、資產負債、資本總額）和離散屬性（工作類別、教育程度、崗位類別、性別、結婚狀況）為條件屬性，收入情況為決策屬性，對本算法的性能進行分析，可以發現模糊粗糙決策樹在執行時間、分類精度上優于模糊決策樹，在生成的規則上少于粗糙約簡樹，從而驗證了本算法在語義處理上具有一定的優越性。

表3 評價結果

■

參考文獻：

王大玲，于戈，等.基于概念層次樹的數據挖掘算法的研究與實現[J].計算機科學，2001，（28）：88-91.

作者簡介：吳曉明，女，1981年3月生，山東省海陽市，高等數學講師，研究方向：高等數學、數學分析、概率統計。