粗集理論屬性約簡的關(guān)鍵技術(shù)研究

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

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

中圖分類號：TP311.1 文獻標識碼：A 文章編號：1007—9599 （2012） 14—0000—02

一、引言

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

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

二、相關(guān)概念

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

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

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

三、決策表離散化

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

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

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

1.等寬劃分算法

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

2.等頻劃分算法

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

3.均值聚類算法

均值聚類算法是根據(jù)用戶指定劃分區(qū)間數(shù)目K，從數(shù)據(jù)集合中隨機選擇K個數(shù)據(jù)作為K個初始區(qū)間的重心，然后分別計算數(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ù)條件屬性和決策屬性值自動選取區(qū)間斷點。其基本原理是根據(jù)每個屬性的屬性值從小到大的順序來對所有的決策表實例進行排序。如果相鄰的兩個實例的條件屬性值和決策屬性值都不同，則將這兩個屬性值的平均值作為斷點值。該算法的缺點是在離散化過程中沒有考慮條件屬性之間的相關(guān)性，而且可能產(chǎn)生冗余斷點。一般改進算法是在判斷候選斷點相鄰的兩個屬性值所屬等價類中出現(xiàn)頻率最多的決策值集合是否存在包含關(guān)系，如果存在包含關(guān)系，則舍棄該斷點。

四、缺失值處理

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

（一）平均值插補

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

（二）同類均值插補

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

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

（三）多重替代法

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

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

五、屬性重要性計算方法分析

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

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

方法一：屬性重要性

方法二：屬性重要性

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

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

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

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

六、結(jié)束語

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

參考文獻：

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

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

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

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