發(fā)信人: ashun (阿順), 信區(qū): DataMining
標  題: [轉載]  （五）：粗糙集
發(fā)信站: 南京大學小百合站 (Mon Sep 17 07:31:25 2001), 站內信件

【 以下文字轉載自 AI 討論區(qū) 】
【 原文由 Jove 所發(fā)表 】
粗糙集方法
　
粗糙集理論是一種研究不精確、不確定性知識的數(shù)學工具，由波蘭科學家Z. Pawlak在1
982年首先提出。知識工程研究中，一直存在著信息的含糊性（vagueness）等問題，含
糊性有三種，術語的模糊性，如高矮；數(shù)據(jù)的不確定性，如噪聲引起的；知識自身的不
確定性，如規(guī)則的前后件間的依賴關系并不是完全可靠的。人工智能的基礎理論之一－
經(jīng)典邏輯不足以解決這些不確定性問題。為此，人們提出了一些解決方法，包括統(tǒng)計方
法、模糊集理論，以及Dempster-Shaffer證據(jù)理論，但這些方法都有一些內在缺陷或限
定范圍；例如，基于統(tǒng)計的方法在理論上還令人難以信服，而模糊集方法則存在一個本
質問題即如何確定成員隸屬度。相比之下，粗糙集方法則有幾個優(yōu)點：不需要預先知道
的額外信息，如統(tǒng)計中要求的先驗概率和模糊集中要求的隸屬度；算法簡單、易于操作
。
隨著KDD的興起，粗糙集理論也受到KDD研究者的重視進而受到研究界的廣為注意。粗糙
集和KDD關系密切，它為KDD提供了一種新的方法和工具。首先，KDD 研究的實施對象多
為關系型數(shù)據(jù)庫。關系表可被看作為粗糙集理論中的決策表，這給粗糙集方法的應用帶
來極大的方便。第二，現(xiàn)實世界中的規(guī)則有確定性的，也有不確定性的。從數(shù)據(jù)庫中發(fā)
現(xiàn)不確定性的知識，為粗糙集方法提供了用武之地。第三，從數(shù)據(jù)中發(fā)現(xiàn)異常，排除知
識發(fā)現(xiàn)過程中的噪聲干擾也是粗糙集方法的特長。第四，運用粗糙集方法得到的知識發(fā)
現(xiàn)算法有利于并行執(zhí)行，這可極大地提高發(fā)現(xiàn)效率。對于大規(guī)模數(shù)據(jù)庫中的知識發(fā)現(xiàn)來
說，這正是求之不得的。第五，KDD中采用的其它技術，如神經(jīng)網(wǎng)絡的方法，不能自動地
選擇合適的屬性集，而利用粗糙集方法進行預處理，去掉多余屬性，可提高發(fā)現(xiàn)效率，
降低錯誤率。第六，粗糙集方法比模糊集方法或神經(jīng)網(wǎng)絡方法在得到的決策規(guī)則和推理
過程方面更易于被證實和檢測。
粗糙集基本概念
粗糙集的研究主要基于分類。分類和概念（concept）同義，一種類別對應于一個概念（
類別一般表示為外延即集合，而概念常以內涵的形式表示如規(guī)則描述）。知識由概念組
成，如果某知識中含有不精確概念，則該知識不精確。粗糙集對不精確概念的描述方法
是：通過上近似概念和下近似概念這兩個精確概念來表示。一個概念（或集合）的下近
似（lower approximation）概念（或集合）指的是，其下近似中的元素肯定屬于該概念
；一個概念（或集合）的上近似（upper approximation）概念（或集合）指的是，其上
近似中的元素可能屬于該概念。
信息系統(tǒng)（information system）：粗糙集把客觀世界或對象世界抽象為一個信息系統(tǒng)
，也稱屬性－值系統(tǒng)。一個信息系統(tǒng)Ｓ是一個四元組Ｓ＝＜Ｕ，Ａ，Ｖ，ｆ＞。其中，
U是對象（或事例）的有限集合，U＝{x1,x2,...,xn}；A是屬性的有限集合，A＝{A1,A2
,...Am}；V是屬性的值域集，V＝{V1,V2,...,Vm}，其中Vi是屬性Ai的值域。f是信息函
數(shù)（information function），ｆ：Ｕ×Ａ? Ｖ，f(xi,Aj)∈Vj。屬性集A常常又劃分為
兩個集合C和D，A＝C∪D，C∩D＝? ，C表示條件屬性集，D表示決策屬性集。D一般只有
一個屬性。
近似空間（approximation space）：近似空間是一個二元組＜Ｕ，Ｒ(Ｂ)＞，U同上，
B是A的屬性子集，R(B)是U上的二元等價關系，R(B) = {(x1,x2)|f(x1,b)=f(x2,b)，fo
r any b in B}。R(B)也稱無區(qū)別關系（indiscernibility relation）。R(B)把U劃分為
k個等價類X1,X2,...,Xk，記R*(B) = {X1,X2,...,Xk}。若無特別指明，后文中的R(B)有
時將簡稱為R，R*(B)簡稱為R*。對任意的x1,x2∈Xi，有(x1,x2)∈R；對任意的x1∈Xi,
 x2∈Xj, i1 j，有(x1,x2)? not∈ R。對于歸納或分類學習，要學習的概念一般根據(jù)決
策屬性集D來劃分，每個概念是R(D)上的一個等價類，共有#(R*(D))個概念。
下近似，上近似: 對任意一個概念（或集合）O，B是U的一個子集，對其作如下定義：O
的下近似定義為：，[x]R(B)表示x在R(B)上的等價類。O的上近似定義為：。
約簡或歸約子（reduct）：設有兩個屬性集B1,B2，B1是B2的真子集，如果R(B1) = R(B
2)，則稱B2可歸約為B1。如果屬性集B不可進一步歸約，則稱B是U的一個約簡或歸約子。

核（core）：U的所有約簡的交集稱為核。核可能為空。
屬性依賴度： 設有兩個屬性集P和Q，則P對Q的依賴度定義為：其中，表示集合X在屬性
集上的下近似。
屬性重要度（attributes significance）：設屬性集Bí C，C是條件屬性集，D是決策
屬性集，則屬性依賴度定義為：，表明從C中去除B后對分類決策的影響程度。
極大屬性集與極小極大規(guī)則轉換模型
約簡是粗糙集中一個非常重要的概念。針對約簡，我們提出了極大屬性集的概念。約簡
即極小屬性集，去掉約簡中的任何一個屬性，都將使得該屬性集對應的規(guī)則覆蓋反例，
即導致規(guī)則與例子的不一致。而對于極大屬性集，向它加入任何一個不屬于它的屬性，
則會使得該屬性集對應的規(guī)則覆蓋更少的正例。我們稱約簡對應的規(guī)則為極小規(guī)則，極
大屬性集對應的規(guī)則為極大規(guī)則。極大規(guī)則學習方法相對于極小規(guī)則學習具有以下幾個
優(yōu)點：⑴可以發(fā)現(xiàn)盡可能多的與類或概念相關的特征；⑵可以避免僅用最小特征集來區(qū)
分概念而導致忽視其他同等重要的特征；⑶當有效的相關特征較多時，可以改進預測精
度；⑷在數(shù)據(jù)稀疏情況下極小原則容易造成過分泛化。
基于極小規(guī)則和極大規(guī)則的概念，我們又提出了極小極大規(guī)則轉換模型。在該模型中，
極小規(guī)則和極大規(guī)則能相互生成。一般來說，極小和極大規(guī)則都不是唯一的；另外，我
們常常希望獲得的極小規(guī)則具有盡可能的簡潔形式（即極小屬性集盡可能的小），這也
是機器學習中很多歸納學習方法所追求的目標之一。由于在生成規(guī)則時要使用啟發(fā)式的
屬性選擇方法進行搜索，而各種選擇方法都是一種偏向（bias），有各自的特點和適用
范圍。極小極大模型為融合或綜合各種偏向提供了一種解決方案。通過使用該模型，我
們能獲得相當好的簡化規(guī)則，另外在處理不同特點的數(shù)據(jù)時都能獲得較好的結果。
連續(xù)屬性離散化
機器學習學習中很多方法要求屬性是離散的（discrete），特別是粗糙集方法只能處理
離散的屬性，而實際中很多屬性是連續(xù)值的（continuous）。因此有必要對連續(xù)屬性進
行離散化。離散屬性也稱符號的（symbolic）、或名稱的（nominal）、或類別的（cat
egorical）；連續(xù)屬性也稱實數(shù)的（real）、或有序的（ordered）、或數(shù)值的（numer
ical）。
連續(xù)屬性離散化的方法有很多種，我們認為可以從三個不同的角度對其進行分門別類。
①是否自動離散化：完全由人手工離散化，完全由機器自動離散化，機器輔助人離散化
。一般地，離散化是指機器自動離散化。②是否與分類或決策類別有關：一是考慮分類
類別；另一是不考慮分類類別，這種方法可用于非監(jiān)督學習或概念聚類學習，不過當用
于帶有類別標記的分類學習時效果肯定不會好于上面的方法。不考慮類別的離散化方法
一般有這樣幾種：等寬區(qū)間法（equal-width-intervals）、等頻區(qū)間法（equal-frequ
ency-intervals）和最大熵法（maximum entropy）。③從與類別有關的離散化策略上來
分：劃分法（splitting）和歸并法（merging），具體見下面小節(jié)。
劃分法的思路是，初始把整個屬性取值范圍作為一個離散屬性值（它與該段區(qū)間對應）
，然后對該區(qū)間進行劃分，一般是一分為二，即把一個區(qū)間分為兩個相鄰的區(qū)間，每個
區(qū)間對應一個離散的屬性值，該劃分可以一直進行下去，直到滿足某種停機條件，如該
區(qū)間上所有的類別都是同一類。劃分法又分動態(tài)型和靜態(tài)型（或預處理型）；而歸并法
只有靜態(tài)型。動態(tài)劃分主要與決策樹有關，它是一邊生成決策樹，一邊進行連續(xù)值區(qū)間
的劃分；具體說，決策樹法在選擇屬性-值時，對于連續(xù)屬性，它要尋找一個劃分點（c
ut-point），該點把該屬性的連續(xù)區(qū)間劃分為兩個區(qū)間；由于屬性-值的選擇是隨著樹的
生成而動態(tài)變化的，因此該離散化方法屬于動態(tài)劃分法。
歸并法的思路是，初始把整個屬性值區(qū)間當作一個離散的屬性值，然后逐個反復合并相
鄰的屬性值（即連續(xù)值區(qū)間），直到滿足某種停機條件。歸并法的實現(xiàn)有兩個影響要素
。一是如何判斷是否該歸并相鄰區(qū)間，二是最終的停機判斷。
判斷相鄰區(qū)間歸并的方法有兩種：一是基于c 2統(tǒng)計意義的判斷方法ChiMerge；另一是我
們提出的基于值差別度量的判斷VDMerge（Value-Difference-Metric Based Merging)，
值差別度量原本用于求離散屬性值間的距離，但反過來卻可用于連續(xù)屬性的離散化上。
停機判斷是：不存在滿足上述歸并條件的相鄰區(qū)間（但如果區(qū)間數(shù)超過了用戶給定的最
大離散屬性值數(shù)則還繼續(xù)歸并）。

--
            我看到一座座山,一座座山川

※ 來源:．南京大學小百合站 dii.nju.edu.cn．[FROM: graphics.nju.edu]
--
※ 轉載:．南京大學小百合站 bbs.nju.edu.cn．[FROM: 202.119.94.53]