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

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

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

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

1.模糊粗糙決策樹

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

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

■

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

■，

X∈{高，中，低}

■，

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

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

（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對(duì)模糊正域的隸屬度：

■

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

■

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

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

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

■

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

γc（y）=■=0.3164

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

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

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

β（FV∩Fjk，l）=■

在決策樹的構(gòu)建過(guò)程中，計(jì)算每個(gè)結(jié)點(diǎn)對(duì)應(yīng)的規(guī)則真實(shí)度β，是一個(gè)很重要的參數(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)“不購(gòu)買”。對(duì)中年分支β（中年，購(gòu)買）=0.4566，β（中年，購(gòu)買）=0.5454，由于β<βth，所以它應(yīng)該被繼續(xù)被劃分。

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

本算法的主要思想是：對(duì)于原始數(shù)據(jù)給定每層概念范圍的離散屬性，利用面向?qū)傩缘臍w納進(jìn)行語(yǔ)義概念提升和概念模糊化；對(duì)于沒(méi)有給定范圍的概念的連續(xù)屬性，在確定劃分的聚類個(gè)數(shù)后，利用k-means聚類算法進(jìn)行屬性的劃分。在此基礎(chǔ)上進(jìn)一步建立模糊粗糙決策樹。通過(guò)特征空間的模糊劃分計(jì)算每個(gè)屬性的依賴度γ，選擇γ最高的結(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ù)庫(kù)部分?jǐn)?shù)據(jù)作為數(shù)據(jù)集來(lái)驗(yàn)證算法的有效性。它是Barry Becker在1994年從人口普查數(shù)據(jù)庫(kù)中提取的，為了直觀起見，我們選擇其中連續(xù)屬性（年齡、資產(chǎn)負(fù)債、資本總額）和離散屬性（工作類別、教育程度、崗位類別、性別、結(jié)婚狀況）為條件屬性，收入情況為決策屬性，對(duì)本算法的性能進(jìn)行分析，可以發(fā)現(xiàn)模糊粗糙決策樹在執(zhí)行時(shí)間、分類精度上優(yōu)于模糊決策樹，在生成的規(guī)則上少于粗糙約簡(jiǎn)樹，從而驗(yàn)證了本算法在語(yǔ)義處理上具有一定的優(yōu)越性。

表3 評(píng)價(jià)結(jié)果

■

參考文獻(xiàn)：

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

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