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

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

關(guān)鍵詞：粗糙集；屬性歸納；模糊化；決策樹

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

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

1.模糊粗糙決策樹

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

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

■

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

■，

X∈{高，中，低}

■，

X∈{經(jīng)常，一般}

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

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

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

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

依賴度的計(jì)算步驟如下：

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

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

？坌k=1，···，cj；？坌l(wèi)=1，···，q

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

■

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

■

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

Step1：計(jì)算劃分在模糊正域的隸屬度

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：計(jì)算對Xc模糊正區(qū)域的隸屬度

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

■

Step3：計(jì)算y對C的依賴度為

γc（y）=■=0.3164

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

定義6：模糊分類規(guī)則的真實(shí)度β的定義：

當(dāng)μ=min（■，■）時

β（FV∩Fjk，l）=■

在決策樹的構(gòu)建過程中，計(jì)算每個結(jié)點(diǎn)對應(yīng)的規(guī)則真實(shí)度β，是一個很重要的參數(shù)。如果β大于規(guī)定的閾值βth，則該結(jié)點(diǎn)作為葉結(jié)點(diǎn)，并產(chǎn)生一條模糊分類則，并且結(jié)束該分支。

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

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

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

二、總結(jié)

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

表3 評價結(jié)果

■

參考文獻(xiàn)：

王大玲，于戈，等.基于概念層次樹的數(shù)據(jù)挖掘算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)，2001，（28）：88-91.

作者簡介：吳曉明，女，1981年3月生，山東省海陽市，高等數(shù)學(xué)講師，研究方向：高等數(shù)學(xué)、數(shù)學(xué)分析、概率統(tǒng)計(jì)。