摘要：粗集理論可以通過不可分辨關(guān)系發(fā)現(xiàn)問題的內(nèi)在規(guī)律，而通常情況下，隨機(jī)采集得到數(shù)據(jù)集合中的連續(xù)屬性值、缺失值、冗余屬性等是普遍存在的。文章重點(diǎn)研究了粗集理論應(yīng)用中屬性離散化及缺失值處理、屬性重要性計(jì)算等典型方法和特點(diǎn)，便于進(jìn)一步優(yōu)化和改進(jìn)屬性約簡算法效率。

關(guān)鍵詞：粗集；屬性約簡；離散化；屬性重要性；缺失值

中圖分類號(hào)：TP311.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007—9599 （2012） 14—0000—02

一、引言

波蘭數(shù)學(xué)家Pawlak Z教授提出的粗集理論可以根據(jù)給定的數(shù)據(jù)集合進(jìn)行規(guī)則獲取，它建立在分類機(jī)制的基礎(chǔ)上，將分類理解為在特定空間上的等價(jià)關(guān)系，將不精確或不確定的知識(shí)用已知的知識(shí)庫中的知識(shí)來近似模擬，在處理冗余、不確定、噪聲、動(dòng)態(tài)數(shù)據(jù)等方面有著較強(qiáng)的應(yīng)用優(yōu)勢，已成為數(shù)據(jù)挖掘領(lǐng)域知識(shí)獲取的重要途徑。

利用屬性約簡來進(jìn)行知識(shí)規(guī)則獲取是粗集理論的核心內(nèi)容之一，而通常情況下，在數(shù)據(jù)隨機(jī)采集得到的近似空間中，信息缺失、連續(xù)屬性值空間、冗余屬性和屬性值是普遍存在的，影響產(chǎn)生決策規(guī)則的正確性和簡潔性。本文重點(diǎn)研究了屬性約簡過程中決策表離散化、缺失值處理、屬性重要性的計(jì)算方法等關(guān)鍵技術(shù)。

二、相關(guān)概念

定義1：決策表包含了對象屬性及屬性值集合，是一類特殊的知識(shí)表達(dá)系統(tǒng)，可以描述為

其中A=C∪D是屬性集合，C、D分別為條件屬性和決策屬性。

下近似集合是U中所有X子集的并集，上近似集合是U中所有與X的交集不為空的子集的并集。邊界域、正區(qū)域、負(fù)區(qū)域定義如下：

三、決策表離散化

在進(jìn)行多屬性的決策分析時(shí)，屬性之間往往不是相互獨(dú)立或者服從某種分布規(guī)律的，粗集理論作為一種集合理論，處理的對象是離散變量，因此必須將連續(xù)變量科學(xué)、合理的轉(zhuǎn)變稱為符合實(shí)際數(shù)據(jù)分布特征的離散量。數(shù)據(jù)的離散化處理實(shí)際上就是根據(jù)某種相似性或者相異性來對數(shù)據(jù)進(jìn)行分類，對數(shù)據(jù)進(jìn)行泛化。

根據(jù)在離散過程中是否考慮類別屬性，可以將離散化方法分成無監(jiān)督和有監(jiān)督兩類。

（一）無監(jiān)督離散化方法：

1.等寬劃分算法

該算法按照用戶要求的區(qū)間數(shù)目將連續(xù)數(shù)值的值域進(jìn)行平均等寬度的劃分，即每個(gè)區(qū)間寬度為 （Xmax—Xmin）/K。其缺點(diǎn)是當(dāng)區(qū)域存在偏斜很嚴(yán)重的點(diǎn)時(shí)誤差較大。

2.等頻劃分算法

等頻算法仍按照用戶要求將連續(xù)屬性值域空間劃分為K個(gè)區(qū)間，每個(gè)區(qū)間包含對象數(shù)目相同，即K個(gè)區(qū)間內(nèi)，每個(gè)區(qū)間包含M/K個(gè)近似值點(diǎn)。

3.均值聚類算法

均值聚類算法是根據(jù)用戶指定劃分區(qū)間數(shù)目K，從數(shù)據(jù)集合中隨機(jī)選擇K個(gè)數(shù)據(jù)作為K個(gè)初始區(qū)間的重心，然后分別計(jì)算數(shù)據(jù)對象與各重心的歐式距離，如果某數(shù)據(jù)距離某重心最近，則將其劃歸該重心區(qū)間，重復(fù)過程完成所有對象的聚類。

無監(jiān)督離散化過程不考慮信息系統(tǒng)的類別屬性和不可分辨關(guān)系，且都需要人為確定劃分區(qū)間數(shù)量，不能保證離散質(zhì)量。

（二）有監(jiān)督離散化方法

有監(jiān)督離散化Naive Scaler算法在離散過程中考慮了信息系統(tǒng)的不可分辨關(guān)系，可以根據(jù)條件屬性和決策屬性值自動(dòng)選取區(qū)間斷點(diǎn)。其基本原理是根據(jù)每個(gè)屬性的屬性值從小到大的順序來對所有的決策表實(shí)例進(jìn)行排序。如果相鄰的兩個(gè)實(shí)例的條件屬性值和決策屬性值都不同，則將這兩個(gè)屬性值的平均值作為斷點(diǎn)值。該算法的缺點(diǎn)是在離散化過程中沒有考慮條件屬性之間的相關(guān)性，而且可能產(chǎn)生冗余斷點(diǎn)。一般改進(jìn)算法是在判斷候選斷點(diǎn)相鄰的兩個(gè)屬性值所屬等價(jià)類中出現(xiàn)頻率最多的決策值集合是否存在包含關(guān)系，如果存在包含關(guān)系，則舍棄該斷點(diǎn)。

四、缺失值處理

不完備信息表的缺失值會(huì)影響屬性約簡和決策規(guī)則的提取。當(dāng)缺失值記錄數(shù)量遠(yuǎn)小于整體信息量情況下，可以將缺失屬性值對象直接刪除，得到完備信息表。但當(dāng)不符合這種情況時(shí)，就需要采用某種方法補(bǔ)齊信息表中的缺失數(shù)據(jù)。

（一）平均值插補(bǔ)

代表性的有Mean Completer算法，該類算法的基本原理是：如果缺失數(shù)值型屬性值，就根據(jù)該屬性取值空間的平均值來填補(bǔ)屬性值；如果缺失的屬性值是非數(shù)值型的，就用該屬性取值空間中出現(xiàn)頻率最高的值來填補(bǔ)缺失值。

（二）同類均值插補(bǔ)

代表性的有Conditioned Mean Completer算法，該類算法中缺失屬性值的補(bǔ)齊也是根據(jù)該屬性取值空間的平均值，區(qū)別在于求平均值的取值空間是從具有相同決策屬性值的實(shí)例中取得。

以上兩類缺失數(shù)據(jù)補(bǔ)齊方法均以最大概率取值來填補(bǔ)缺失屬性值，具有較好的可行性。缺點(diǎn)是在缺失值補(bǔ)齊過程中可能引入新的沖突信息。

（三）多重替代法

受貝葉斯估計(jì)啟發(fā)，多值替代法的基本思想是認(rèn)為待插補(bǔ)的值是隨機(jī)的、已觀測到的值。用一系列可能的值來插補(bǔ)缺失值，然后再加上不同的噪聲，用統(tǒng)計(jì)分析過程對多次插補(bǔ)產(chǎn)生的多個(gè)數(shù)據(jù)集進(jìn)行分析綜合，得到總體參數(shù)的估計(jì)值。其本質(zhì)是產(chǎn)生缺失值的一個(gè)隨機(jī)樣本，然后根據(jù)某種選擇依據(jù)，選取最合適的插補(bǔ)值。

多重替代法基本步驟：①為每個(gè)缺失值產(chǎn)生一個(gè)可能的插補(bǔ)值集合，這些值反映了數(shù)據(jù)缺失導(dǎo)致的不確定性；每個(gè)值都可以被用來插補(bǔ)缺失值，產(chǎn)生若干個(gè)完備數(shù)據(jù)集合；②每個(gè)插補(bǔ)數(shù)據(jù)集合都用針對完整數(shù)據(jù)集的統(tǒng)計(jì)方法進(jìn)行統(tǒng)計(jì)分析；③對來自各個(gè)插補(bǔ)數(shù)據(jù)集的結(jié)果，根據(jù)評分函數(shù)進(jìn)行選擇，產(chǎn)生最終的插補(bǔ)值。

五、屬性重要性計(jì)算方法分析

差別矩陣算法、MIBARK算法、基于信息熵的屬性約簡算法[4]等都是利用屬性重要性作為啟發(fā)式信息，從決策系統(tǒng)中找出最優(yōu)約簡，屬性重要性的計(jì)算方法主要派生于不同的屬性依賴度的定義，以下對常見的方法進(jìn)行分析。

對于決策表T=〈U，C∪D〉，其中C、D分別為條件屬性和決策屬性，R C，a∈C—R。

方法一：屬性重要性

方法二：屬性重要性

以上兩種方法屬性重要性的定義均依賴于屬性集合正區(qū)域的確定。

方法三：利用差別矩陣中屬性出現(xiàn)的頻率函數(shù)p（a）來定義屬性重要性

方法四：信息熵算法中利用互信息變化來衡量屬性重要性，條件熵：

用屬性重要性作為啟發(fā)式信息屬性約簡算法的基本原理均是從尋找核屬性出發(fā)，根據(jù)不同方法計(jì)算各屬性重要性，逐步添加屬性重要性大的屬性到約簡集合中，直到能夠?qū)λ械膶ο筮M(jìn)行正確分類。此類算法的優(yōu)點(diǎn)是能夠以比較大的概率獲得條件屬性集的最小約簡，缺點(diǎn)如果屬性數(shù)量比較多，尋找核屬性的過程是非常耗費(fèi)時(shí)間的。

六、結(jié)束語

連續(xù)屬性離散化、決策表缺失值處理和屬性重要性判斷是決策表屬性約簡過程中的主要環(huán)節(jié)，其結(jié)果將直接影響決策規(guī)則產(chǎn)生的準(zhǔn)確性和效率，本文對屬性離散化及缺失值處理、屬性重要性計(jì)算等典型方法和特點(diǎn)進(jìn)行了重點(diǎn)分析，有助于更好的挖掘數(shù)據(jù)背后的內(nèi)在聯(lián)系和本質(zhì)規(guī)律，進(jìn)一步優(yōu)化和改進(jìn)屬性約簡算法效率。

參考文獻(xiàn)：

[1]史忠植.知識(shí)發(fā)現(xiàn).北京：清華大學(xué)出版社，2002

[2]江潔等.數(shù)據(jù)挖掘的粗集方法研究.北京航空航天大學(xué)學(xué)報(bào)，2001，10

[3]侯麗娟，王國雍等.粗糙集理論中的離散化問題.計(jì)算機(jī)科學(xué)，2000，27（12）：89—94

[4]李雄飛等.基于粗集理論的約簡算法.吉林大學(xué)學(xué)報(bào)，39（1），2003，26—29