數(shù)據(jù)挖掘與知識發(fā)現(xiàn)

第6章基于粗糙集（RoughSet）理論

的數(shù)據(jù)挖掘技術粗糙集理論是由波蘭華沙理工大學數(shù)學家Z.Pawlak于1982年提出的一種數(shù)據(jù)分析理論，該理論在分類意義下定義了模糊性和不確定性兩個概念。是一種處理不完整數(shù)據(jù)、不精確知識的表達、學習、歸納等的一-種新型數(shù)學工具。粗集理論的重要特點是：不需要任何附加信息或先驗知識，直接從所需處理的數(shù)據(jù)本身所提供的信息出發(fā)找出問題的內在規(guī)律。目前，大多數(shù)數(shù)據(jù)挖掘工具軟件（如：AQ系統(tǒng)、IDS系統(tǒng)等）都是基于集合論開發(fā)的，其中粗糙集（RS）理論使用最廣，也最布?開展前途。由于RS是研究不精確和不確定知識的一種數(shù)據(jù)工具，如，知識的含糊性，主要包括：①術語的模糊性，如高矮；②數(shù)據(jù)的不確定性，如噪聲；③知識自身的不確定性，如規(guī)那么的前后件間的依賴關系不完全可靠等。所以，它同其它不確定問題理論，如，概率統(tǒng)計理論中的概率分布、模糊理論不能處理不完整數(shù)據(jù)且需提供隸屬函數(shù)這種先驗知識、D-S證據(jù)理論中的基本概率賦值等相比，更具實用性。粗集理論的主要思想：是在保持分類能力不變的前提下，通過知識約簡，導出問題的決策或分類規(guī)那么。目前，RS理論已成功地應用于機器學習、過程控制、模式識別、數(shù)據(jù)挖掘、預測、故障診斷、決策分析和人工神經(jīng)網(wǎng)絡等領域，成為其它不確定理論的一種補充,有著不可替代的優(yōu)越性。?核可解釋為在知識約簡時它是不能消去的知識特征集合?！纠纭吭OK=（U,R）是一個知識庫，其中〃=區(qū)』，…，/），R={R”&,&}，且U/R、={{xpx4,x5},{x2,x8),{j;3},{x6,x7})U/R2={{x1,x3,x5),{x6},{x2,x4,j:7,x8})U/%={“],%},{“"2,與，/}，{工3，匕}}那么得關系加4（R）的等價類為U/加d(R)={{再,％5},{%2,“8}，{巧}，{匕}，{%}，{%7}}（注：u/〃h（r）是通過計算（u/與nu/Qnu/6獲得的）故由計算:u/ind(R-{Rx})={{x1,x5},{x2,x7,x8}Jx3},{x4},{x6})豐U/indg(注：U/ind(R-{/?,))是通過計算U/R2C\U/R.獲得的)說明關系叫為R中必要的。對于關系R?,有U/ind(R-{7?2})={{Xj,x5},{x2,x8},{x3},{x4},{x6},{x7}}=ind(R)故R?是R中不必要的。同理，&也是R中不必要的，即有U/ind(R-{&})={{司,毛},{x2,x8),(x3},{x4},{x6},{x7)}=ind(R)但U/R-{R2,Ry}=U/R]={{x1,x4,x5),{x2,x8),{x3},{x6,x7}}wU/加d(R)且有U/山d({K,&})hU/加d(K),U1加d({^，&})工U/〃以(R2)所以，｛R-R?｝為獨立的且為R的一個約簡。同理，｛叫,R-J也是獨立的且為R的一個約簡。那么一個核core(R);｛叫,與｝。｛叫,&｝=｛RJ?.知識的相對約簡、相對核概念令P和Q為U中的等價關系，Q的P正域記為R，Sp(Q),即PosP(Q)=UPXXeU/Q_所以，Q的P正域是U中所有根據(jù)分類U/P的信息可以準確地劃分到關系Q的等價類中去的對象集合。令P和Q為等價關系族，RwP,如果尸%,/(p)(力以(Q))=P%d(p.用的d(Q))那么稱R為P中Q不必要的；否那么為必要的。為簡單起見，用Rz%(Q)代替P3'MP)a〃"(Q))。如果P中的每個R都為Q必要的，那么稱P為Q獨立的(或P相對于Q獨立)。設SqP,S為P的Q約簡當且僅當S是P的Q獨立子族且Poss(Q)=R?Sp(Q)。P的Q約簡簡稱為相對約簡。P中所有Q必要的原始關系構成的集合稱為P的Q的核。簡稱相對核，記為coreQ(P).定理：c"eQ(P)=OedQ(P),其中&/q(P)是所有P的Q約簡構成的集合?！纠纭吭OK=(U,P)是一個知識庫，其中。=｛和々，…，4｝，P=｛R1,R2，R3｝，且UIR、={{xpx3,x4,x5,x6,x7),{x2,x8)|UiR?=｛區(qū)，七,工25｝,｛12，16，工7，工8｝｝U/%={{%1，工5，尢6}，{々，加工8)，{13，3}那么由P導出的分類為U/歷d(P)={{否,匕}，(犬3，匕)，{工2，工8}，{工6}，{與}}假設等價關系Q有以下等價類:。/(?={口］，與，4}，*3，匕}，{工2，工7}，■}}那么Q的P正域為:Posp(Q)=(x),x51u{x^X4}U{^6}U{A：7}={xi,x3,x4,x5,x6,x1}又U/(P-{R[})=0/{/?2，&}={{和為}，{%3，匕}，{%2，力7，力8}，{4}}所以R，S{PT%)}(Q)={xpx5}U{x3,x4}U{x6}={xpx3,x4,x5,x6}PoSp(Q)故但凡P中Q必要的。同理得，魚為P中Q不必要的；&為P中Q必要的。這樣，P的Q核為{R1,R-J，即co%q(P)={R1,&},它也是P的Q約簡。.知識表達系統(tǒng)知識表達在智能數(shù)據(jù)處理中占有十分重要的地位。形式上，一個知識表達系統(tǒng)可定義為四元組S=(U,AVJ),其中，U：對象的非空有限集合，稱為論域；A：屬性的非空有限集合；V=U匕，匕是屬性。的值域；aeA/:UxAfV是一個信息函數(shù)，它為每個對象的每個屬性賦予一個信息值，即V.r€U,Vq￡AJ(x,a)gVa知識表達系統(tǒng)也稱為信息系統(tǒng)。通常用S=(U,A)來代替S=(C/,AV,/)o

知識表達系統(tǒng)的數(shù)據(jù)以關系表的形式表示。關系表的行對應要研究的對象，列對應對象的屬性，對象的信息是通過指定對象的各屬性值來表達。顯然，一個屬性對應一個等價關系，一個表可以看作是定義了一族等價關系，即知識庫?！纠纭?，一個關于某些病人的知識表達系統(tǒng)，那么U=｛ei'.‘es,G，%,,｝，A=｛頭痛，肌肉痛，體溫｝病人潮肌肉痛體溫是是正常%是是高%是是很高/否是正常%否否高否是很高令PqA,定義屬性集P的不可分關系加d(P)為ind｛P｝=｛(x9y)eUxU\X/agP,f(x,a)=f(y9a)｝如果(x,y)gincl(P),那么稱x和y是P不可區(qū)分的。容易證明，,不可分關系山。(P)是U上的等價關系。假設取屬性集P=｛頭痛，肌肉痛｝,那么有。/尸=｛｛，,02,%｝，回，，｝，｛為｝｝即P的基本集為｛《，/勺｝，匕，〃｝，｛%｝假設取X=｛6,64,6｝,那么PX=PoSp(X)={eA,eb}\PX={e[,e2,ei,e4,e6}N%(X)=U-PX={%}；Bnp(X)={ene2,e3}而U"?〃-A)={{《},{%},{G}，{0}，{%}，{〃}}U"?〃或A-{頭痛})={{,,/},{g},{6,/}，仁}}工。/山d(A)U/加d(A-肌肉痛)={{q},?圖/4匕},{%}，{《}}=U"〃d(A)U/ind(A-{體溫})={{,,6，6}，{/，/},{/}}wU/山d(A)所以，經(jīng)約簡知，屬性集{頭痛、肌肉痛、體溫}有一個約簡{頭痛，體溫}且co砥A)=(頭痛,體溫}。.決策表決策表是一類特殊而重要的知識表達系統(tǒng)。多數(shù)決策問題都可以用決策表形式來表達，這一工具在決策應用中起著重要的作用。設S=(U,AK/)為一知識表達系統(tǒng)，4=cuncno=。，c稱為條件屬性集,D稱為決策屬性集。具有條件屬性和決策屬性的知識表達系統(tǒng)稱為決策表?！纠纭恳粋€關于某些病人的決策表如下，其中(7={《,/，…，4}，c={頭痛，肌肉痛，體溫},D={流感}。令孰二頭痛，C2二肌肉痛，。3=體溫，那么u/{CJ={[e^e2,e3},{/,仁，/，。，41)^/{C2}={{e,,e2,e3,e4,e6,e8},{e5,e7})條件屬性決策屬性沆感^/{C3}={{e1,e4},{e2,e5,e7},{e3,^6,e8})病人郵肌肉痛體溫&是是正常否u/{GC}={化，出勺}，怙，/，/},{生勺}}是是高是U/{C、,。3}二{{《1},卜2}'{，3},{，},{%,，}'{分,/}}是是很高是否是正常否U/{。2,G}={{^1，64}，{《2}，{%，67}，{,3,66,08})%否否高否U/C={{,},{g},{6},{ej{%，。)，&，/}}繪否是很高是%否否高是U/D={{e2,e?t,e(),e1],{el,e4,e5,e8}}%否是很高否因為Posc(D)={e}]\J{e2}U{e3}U{e4)=(el9e2,e39e4}且有Pos{C_{C}}(D)={e}ie2,e4}工Posc(D)PoS{ctjh(D)={el,e2,e3,e4]=Posc{D}

PoS｛CTG）｝（O）=。，PoSc（D）PoS｛ctg，C2“（°）=｛?^41Posc（D）&S｛c-gc”（Q）=。hPosc（D）所以C的D約簡（相對約簡）為C-｛C2｝=｛G，C3｝，C的D核（相對核）也為｛G，G｝。在決策表中，不同的屬性可能具有不同的重要性。為了找出某些屬性（或屬性集）的重要性（significance）,我們的方法是：從表中去掉一些屬性，現(xiàn)來考察沒有該屬性后分類會怎樣變化。假設去掉該屬性相應分類變化較大，那么說明該屬性的強度大，即重要性高；反之重要性低。對屬性的重要性問題，我們也可用依賴度定義來說明：定義令C和D分別為條件屬性和決策屬性，那么k=yk=yc(D)=k=yc(D)=Posc(D)

\U\稱為D依賴于C的依賴度。如，上例中k=yc（D）=P°：；*k=yc(D)=Posc(D)

\U\I。I8分依賴于C,依賴度為0.5。定義屬性子集C，C關于D的重要性為be（C）=/c（O）-，dc（D）特別地，當C'=｛。｝時，屬性acC關于D的重要性為crcD（^）=rc（￡＞）-rc-M（D）如，上例中，有（頭痛）=4/8-3/8=1/8肌肉痛）=4/8-4/8=0%（體溫）=4/8-0=4/8由此知，在決策表中，｛體溫｝最重要；其次是｛頭痛｝;｛肌肉痛｝是不重要的。在決策表中，最重要的是決策規(guī)那么的產(chǎn)生。設S=（U,AVJ）是一個決策表，A=CUD,CnD=。。令X,和匕分別代表U/C與U/D中的各個等價類，des（Xj）,des（"）分別表示對等價類X,和匕的描述，即等價類X,和匕對各屬性值的特定取值。決策規(guī)那么定義如下：%:fdesQj）,-D。\YC\X\規(guī)那么確實定因子〃（Xj,匕）=———,0<4（Xj,匕）<1IXj|當”（Xj,匕）=1時，「是確定的；當時，為是不確定的。注：在產(chǎn)生決策規(guī)那么之前，可首先對決策表中的屬性進行約簡?！纠纭繉ι侠又校瑢Ρ磉M行屬性約簡得下表。這里，U={q,e2「、/},C={頭痛，體溫},D={流感}。決策屬比那么^/C-{XPX2,X3,X4,X5,X6}病人5ys體溫而總A是正京否其中，x,={e,}fX2={e2},X3=(e3|,%是高是%是很高jaX5={es,e7),X6={/,/}舌正常否%否有否°，否很高是U/D={Y},Y2}外否高是%否很育者其中，X={0，/,繪，今},%={?1，%，4,4}X4={e4}f確定性規(guī)那么有：?。海^痛，是）且（體溫，正常）f（流感，否）%：（頭痛，是）且（體溫，高）一（流感，是）「霜：（頭痛，是）且（體溫，很圖）f（流感，是）「42：（頭痛，否）且（體溫，正'吊,）f（流感，否）不確定性規(guī)那么有：心：（頭痛，否）且（體溫，高）f（流感，是），規(guī)那么確實定因子為0.5公：（頭痛，否）且（體溫，高）一（流感，否），規(guī)那么確實定因子為0.5%：（頭痛，否）且（體溫，很高）一（流感，是），規(guī)那么確實定因子為0.5%：（頭痛，否）且（體溫，很高）-*（流感，否），規(guī)那么確實定因子為0.5.粗糙集理論的基本概念（1）知識和知識庫設①為論域，任何子集XqU,稱為U中的一個概念或范疇，規(guī)定空集中也是一個概念。U中的一個概念族稱為關于U的抽象知識，簡稱知識。這里，主要對U上能形成劃分的那些知識感興趣。一個劃分F定義為：F={X-X2,…,X",其中，X,uU;X,￥（D,X,cX；=O,z>/;uX,=Ul7I7IJ7"7.7,1=1（顯然，一個劃分就是一條知識）U上的一族劃分稱為關于U的一個知識庫（knowledgebase）o設R是U上的一個等價關系，U/R表示R的所有等價類構成的集合，即U/R={[x]R\xeU].[幻犬表示包含元素xwU的R等價類?！纠纭靠紤]一組兒童的集合，A={（張，9）,（王，9）,（李，9）,（趙，9）,（劉，7）,（洪，7）,（梁，7）,（黃，5）,（陳，5）,（段，8）}0那么具有“相同年齡”關系R的等價類如下：匹二{（張，9）,（王，9）,（李，9）,（趙，9）}72={（劉，7）,（洪，7）,（梁，7）}乃3={（黃，5）,（陳，5）}%={（段，8）}即A/R={勺，42，43，町}一個知識庫就是一個關系系統(tǒng)K=（SR）,R是U上的一族等價關系。假設等價關系族P=R,且P#①，那么CP也是一個等價關系（即P中所有等價關系的交集),稱CP為P上的不可區(qū)分關系(indiscernibility)，記為ind(P),且有國i=nm。⑴那么U/加d(P)表示與等價關系族P相關的知識，稱為K中關于U的P基本知識(P基本集)。為簡單起見，用U/P代替U/〃0(P)。不可分辯關系概念是RS理論的基礎，它揭示出論域知識的顆粒狀結構。山或P)的等價類⑶源⑺稱為知識P的基本概念或基本范疇。特別的，如果QeR,那么稱。為K中關于U的Q初等知識。Q的等價類為知識R的。初等概念或初等范疇。當K=(U,R)為一知識庫，加或K)定義為K中所有等價關系的族，記作ind(K)=｛山d(P)|"尸三陽(說明K是由所有基本知識組成的集合)【例如】一玩具積木的知識表達系統(tǒng)由此得三個等價類:積木顏色形狀論域〃=｛用,々，…，/｝，如果根據(jù)某一屬性描述這些積體枳X】紅圓小x2-&方大木情況，就可按顏色、形狀和體積分類。換言之，可以定義X,紅三角型小——三個等價關系(即屬性)：顏色與、形狀凡、體積尺。4藍三角坦小X,黃回小、按分：芭,當,與一紅；灰,匕一藍；八,工6，%—黃X，黃方小J紅三角型按凡分：冷々一圓；工2，工6一方；七，匕，匕，工8一三角型*8黃三角型大按'分：X2>-%,冬一大;再，了3，“4，均，工6一?小。U/R1={{x1,x3,x7},{a:2,x4},{^5,x6,x8))U/R2={{xi,x5},{x2,x6},{x3,x4,x7,x8))U/R3=｛｛工2，七，/｝，｛%，工3，工4，/，4)｝這三個等價類均是由知識庫k=(u,｛m，R2，R3｝)中的初等概念(初等范疇)構成的。它的基本范疇是初等范疇的交集構成的，如(jf1,x3,x7｝A｛j:3,x4,x7,x8)=｛x3,x7)紅色三角形(x2,x4)n(x2,x6J=｛x2｝藍色方形(x5,x6,x8)A(x3,x4,x7,x8)=｛/｝黃色三角形上面是｛R1,RJ的基本范疇。｛xj,x3,x7｝n｛x3,x4,x7,x8｝n｛x2,x7,x8｝=｛x7｝紅色大三角形這是｛R「R?,&｝的基本范疇?！?，工3，七｝1)｛工2，E｝=｛內，M3，與，工2，匕｝--紅色或藍色，為｛RJ的范疇。注：(1)有些范疇在這個知識庫是無法得到的，如｛看,匕｝口區(qū),看｝=?！f明知識庫中不存在藍色圓形，為空范疇。｛芭,當,看｝「｛々》6｝=。---說明知識庫中不存在紅色方形，為空范疇。(2)上例容易求出U/｛R1,4｝、〃/｛%,&｝、〃/｛0,&)和U/R=U/｛R”R2，RJU-｝二。/凡0"/穴2=｛｛再｝，｛占｝，｛巧，"7｝，｛七｝，｛“5｝，｛%｝，｛/｝｝。/｛a,&｝=。/叫「。/'=｛區(qū)，巧｝，出｝，｛5)，｛“，展，/｝，｛4｝｝U/｛犬2，火3｝="/穴2-0/&=｛｛再，&｝，｛%2｝，*3，相｝，｛與，/｝，(工6｝｝U/R=U/g7。/&門。/&=｛｛再｝，｛々｝，｛上｝，｛￡｝，出｝，｛會用匕｝,｛/｝｝(3)假設一個知識系統(tǒng)，u=U，w，…,4｝，給定一個等價關系簇R=｛凡,Rz,R.J，且有以下等價類：U/R]={{斗,X4，匕}，{%2，/}，{匕}，*6,}}uIR?={{x,,x5,x3},{x6},{x4,x2,x7,x8})U!Ry={{x2,x7,x8|,{xpx5),{A-4,x3,x6))試求：UIR,U/{R-R}},U/{R-R2},U/{R-R3}《自己思考》定義：設K=(U,P)和K=(U,Q)為兩個知識庫，假設ind(P)=山d(Q),即U/P=SQ,那么稱K和K'(P和Q)是等價的，記作KnK'(P二Q)。(說明K和K'有同樣的基本范疇)設K=(U,P)和K=(U,Q)為兩個知識庫，當加d(P)u加d(Q)時，稱知識P(知識庫K)比知識Q(知識庫K')更精細，或Q比P更粗糙。當P比Q更精細時，也稱P為Q的特化，Q為P的推廣。這就意味著，推廣是將某些范疇組合在一起，而特化那么是將范疇分割成更小的單元。(2)不精確范疇、近似與粗糙集令XqU,R為U上的一個等價關系。當X能表達成某些R基本范疇的并時，那么稱X是R可定義的；否那么不可定義的。R可定義集是論域的子集，它可在知識庫中精確地定義。而R的不可定義集不能在這個知識庫中定義。R的可定義集也稱為精確集，而A的不可定義集也稱為A的非精確集或尺的粗糙集。當存在等價關系R^ind(K)且X為R精確集時，集合XqU稱為K中的精確集;當對于任何X都是R粗糙集，那么X稱為K中的粗糙集。定義：設給定知識庫K=(U,R),對于每個子集XqU和一個等價關系Rwind(K),定義兩個子集:RX=\J{YeU/R\Y^X]

RX=\J{YeU/R\YC\X^</f]分別稱為X的R下近似(lowerapproximation)和R上近似(upperapproximation)o上下近似也可用下面的等式表達:RX={xeU\[x]RqX}--由根據(jù)知識R判斷肯定屬于X的U中元素組成RX={xeU\[x]RnXw0}…由根據(jù)知識R判斷可能屬于X的U中元素組成集合B?(X)=AX-RX稱為X的R邊界域；PoSr(X)=RX稱為X的R正域；Negr(X)=U-RX稱為X的R負域。顯然，RX=PosR(X)\jBnR(X)【例如】應用近似集合的概念，根據(jù)粗集的定義，來研究或分析一些人的受教育程度與就業(yè)的關系問題。受教育程度與就業(yè)的情況如下表所示。受教育者受教育程度就業(yè)情況王局中無馬高中有李小學無劉大學有趙研究生有解：由受教育程度與就業(yè)情況知識表達數(shù)據(jù)表知，研究對象:受教育的人：U={王，馬，李，文IJ,趙}受教育程度：｛高中，小學，大學，研究生｝四種，即等價關系R=｛LLX，%｝,其中y產(chǎn)｛王,馬｝,匕=｛李｝，匕=｛劉），匕=｛趙）就業(yè)情況：｛有，無｝兩種。設x為定義有工作的人為一種分類子集，那么有工作的人的子集x二｛馬，劉，趙｝那么根據(jù)粗集的定義，有poSr（x）=r（x）=xul=｛劉，趙｝A（x）=xU%U%=｛劉,趙,王,馬｝NEGr（X）=U-R（＜X）=Y2=｛李｝B%（X）=R（X）-R（X）=X=｛王，馬｝所以，根據(jù)粗集中R（x）、R（X）、NEGr（X）、3曲（X）的意義，可得受教育程度與就業(yè)的情況表達如下：根據(jù)R（X）,規(guī)那么1：if（大學）or（研究生）then（一定有工作）根據(jù)R（X）,規(guī)那么2：if（高中、大學）or（研究生）then（可能有工作）根據(jù)8〃r（X）,規(guī)那么3：if（高中）then（可能有、也可能無工作）根據(jù)NEGr（X）,規(guī)那么4：if（小學）［hen（無工作）定理1：（1）X為R可定義集當且僅當HX=RXX為R粗糙集當且僅當HXwRx定理2：（1）RXqXqRXRgRge，RU=RU=U

R(X\JY)=RXIJRY；R(XC\Y)=RXC\RYXqYnRXq/?y；XqYn