高級(jí)數(shù)理邏輯 第八章

第八章粗糙集RoughSet

2/5/20231Roughsets的快速入門方法認(rèn)真研讀RoughSetsTheory的創(chuàng)始人、波蘭數(shù)學(xué)家Z.Pawlak于1982年發(fā)表的第一篇論文“RoughSets”?！咀ⅰ浚鹤詈弥苯娱喿x英文論文原文。

研讀王玨等人1996年在《模式識(shí)別與人工智能》上發(fā)表的關(guān)于RoughSets理論及其應(yīng)用的綜述性文章。參考史忠植編著的《高級(jí)人工智能》、《知識(shí)發(fā)現(xiàn)》等教材中討論粗糙集的有關(guān)章節(jié)?！咀ⅰ浚簢鴥?nèi)王國胤、劉清、張文修、曾黃麟等人先后出版了關(guān)于RoughSets的教材，也可適當(dāng)參考。2/5/20232Roughset快速入門方法（續(xù)）認(rèn)真研讀如下3篇典型的論文：

[1]Pawlak,Z.,etal.Roughsetapproachtomulti-attributedecisionanalysis.EuropeanJournalofOperationalResearch,72:443-459,1994[2]Grzymala-Busse,D.M.,etal.Theusefulnessofamachinelearningapproachtoknowledgeacquisition.ComputationalIntelligence.11(2):268-279,1995[3]Jelonek,J.,etal.Roughsetreductionofattributesandtheirdomainsforneuralnetworks.ComputationalIntelligence,11(2):339-347,19952/5/20233內(nèi)容提要一、粗糙集理論的發(fā)展概述二、粗糙集理論的基本原理三、知識(shí)的約簡四、決策表的約簡五、粗糙集的擴(kuò)展模型六、粗糙集的實(shí)驗(yàn)系統(tǒng)七、粒度計(jì)算簡介2/5/20234一、粗糙集理論的發(fā)展概述自然界中大部分事物所呈現(xiàn)的信息都是：

◆

不完整的、不確定的、模糊的和含糊的

◆經(jīng)典邏輯無法準(zhǔn)確、圓滿地描述和解決

粗糙集理論主要是為了描述并處理“含糊”信息。2/5/20235一、粗糙集理論的發(fā)展概述“含糊”（Vague）1904年謂詞邏輯創(chuàng)始人G.Frege(弗雷格)首次提出將含糊性歸結(jié)到“邊界線區(qū)域”(Boundaryregion)在全域上存在一些個(gè)體，它既不能被分類到某一個(gè)子集上，也不能被分類到該子集的補(bǔ)集上……“模糊集”（FuzzySets）1965年美國數(shù)學(xué)家L.A.Zadeh首次提出無法解決G.Frege提出的“含糊”問題未給出計(jì)算含糊元素?cái)?shù)目的數(shù)學(xué)公式……2/5/20236一、粗糙集理論的發(fā)展概述“粗糙集”（RoughSets）的提出1982年波蘭數(shù)學(xué)家Z.Pawlak首次提出將邊界線區(qū)域定義為“上近似集”與“下近似集”的差集指出在“真”、“假”二值之間的“含糊度”是可計(jì)算的給出計(jì)算含糊元素?cái)?shù)目的計(jì)算公式借鑒了集合論中的“等價(jià)關(guān)系”（不可區(qū)分關(guān)系）求取大量數(shù)據(jù)中的最小不變集合（稱為“核”）求解最小規(guī)則集（稱為“約簡”）……2/5/20237一、粗糙集理論的發(fā)展概述粗糙集理論中的一些基本觀點(diǎn)“概念”就是對(duì)象的集合“知識(shí)”就是將對(duì)象進(jìn)行分類的能力(“各從其類”)“知識(shí)”是關(guān)于對(duì)象的屬性、特征或描述的刻劃不可區(qū)分關(guān)系表明兩個(gè)對(duì)象具有相同的信息提出上近似集、下近似集、分類質(zhì)量等概念……2/5/20238一、粗糙集理論的發(fā)展概述粗糙集理論的主要優(yōu)勢(shì)之一是它不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息。許多計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家對(duì)粗糙集理論及其應(yīng)用進(jìn)行了堅(jiān)持不懈的研究，使之在理論上日趨完善，特別是由于20世紀(jì)80年代末和90年代初在知識(shí)發(fā)現(xiàn)等領(lǐng)域得到了成功的應(yīng)用而越來越受到國際上的廣泛關(guān)注。2/5/20239一、粗糙集理論的發(fā)展概述1970s，Pawlak和波蘭科學(xué)院、華沙大學(xué)的一些邏輯學(xué)家，在研究信息系統(tǒng)邏輯特性的基礎(chǔ)上，提出了粗糙集理論的思想。在最初的幾年里，由于大多數(shù)研究論文是用波蘭文發(fā)表的，所以未引起國際計(jì)算機(jī)界的重視，研究地域僅限于東歐各國。1982年，Pawlak發(fā)表經(jīng)典論文《Roughsets》，標(biāo)志著該理論正式誕生。2/5/202310一、粗糙集理論的發(fā)展概述1991年，Pawlak的第一本關(guān)于粗糙集理論的專著《Roughsets:theoreticalaspectsofreasoningaboutdata》；1992年，Slowinski主編的《Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory》的出版，奠定了粗糙集理論的基礎(chǔ)，有力地推動(dòng)了國際粗糙集理論與應(yīng)用的深入研究。1992年，在波蘭召開了第一屆國際粗糙集理論研討會(huì)，有15篇論文發(fā)表在1993年第18卷的

《Foundationofcomputinganddecisionsciences》上。2/5/202311一、粗糙集理論的發(fā)展概述1993和1994年，分別在加拿大、美國召開第二、三屆國際粗糙集與知識(shí)發(fā)現(xiàn)（或軟計(jì)算）研討會(huì)。1995年，Pawlak等人在《ACMCommunications》上發(fā)表“Roughsets”，極大地?cái)U(kuò)大了該理論的國際影響。1996～1999年，分別在日本、美國、美國、日本召開了第4-7屆粗糙集理論國際研討會(huì)。2000年，在加拿大召開了第二屆粗糙集與計(jì)算趨勢(shì)國際會(huì)議。2/5/202312一、粗糙集理論的發(fā)展概述2001～2002，中國分別在重慶、蘇州召開第一、二屆粗糙集與軟計(jì)算學(xué)術(shù)會(huì)議。2003年，在重慶召開粗糙集與軟計(jì)算國際研討會(huì)。2004年，在瑞典召開RSCTC國際會(huì)議（年會(huì)）。2005年，在加拿大召開RSFDGrC國際會(huì)議（年會(huì)）。2/5/202313一、粗糙集理論的發(fā)展概述2006第六屆中國粗糙集與軟計(jì)算學(xué)術(shù)研討會(huì)在浙江師范大學(xué)2007年粗糙集與軟計(jì)算、Web智能、粒計(jì)算聯(lián)合學(xué)術(shù)會(huì)議,山西大學(xué)

2008年第8屆中國粗糙集與軟計(jì)算學(xué)術(shù)會(huì)議、第2屆中國Web智能學(xué)術(shù)研討會(huì)、第2屆中國粒計(jì)算學(xué)術(shù)研討會(huì)聯(lián)合學(xué)術(shù)會(huì)議（CRSSC-CWI-CGrC2008）,河南師范大學(xué)……中科院計(jì)算所、中科院自動(dòng)化所、重慶郵電學(xué)院、南昌大學(xué)、西安交通大學(xué)、山西大學(xué)、合肥工業(yè)大學(xué)、北京工業(yè)大學(xué)、上海大學(xué)2/5/202314粗糙集理論的優(yōu)點(diǎn)及局限性主要優(yōu)點(diǎn)除數(shù)據(jù)集之外，無需任何先驗(yàn)知識(shí)（或信息）對(duì)不確定性的描述與處理相對(duì)客觀……【說明】：Bayes理論、模糊集理論、證據(jù)理論等都需要先驗(yàn)知識(shí)，具有很大的主觀性。2/5/202315粗糙集理論的優(yōu)點(diǎn)及局限性（續(xù)）局限性缺乏處理不精確或不確定原始數(shù)據(jù)的機(jī)制對(duì)含糊概念的刻劃過于簡單無法解決所有含糊的、模糊的不確定性問題需要其它方法的補(bǔ)充……解決辦法與模糊集理論相結(jié)合與Dempster-Shafer證據(jù)理論相結(jié)合……2/5/202316粗糙集理論的研究現(xiàn)狀在理論研究方面數(shù)學(xué)性質(zhì)：研究其代數(shù)與拓?fù)浣Y(jié)構(gòu)、收斂性等粗糙集拓廣：廣義粗糙集模型、連續(xù)屬性離散化與其它不確定性處理方法的關(guān)系和互補(bǔ)：與模糊集理論、Dempster-Shafer證據(jù)理論的關(guān)系和互補(bǔ)粒度計(jì)算：粗糙集理論是其重要組成之一高效算法：導(dǎo)出規(guī)則的增量式算法、簡約的啟發(fā)式算法、并行算法、現(xiàn)有算法的改進(jìn)……2/5/202317粗糙集理論的研究現(xiàn)狀（續(xù)）在數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用發(fā)現(xiàn)數(shù)據(jù)之間（精確或近似）的依賴關(guān)系評(píng)價(jià)某一分類（屬性）的重要性剔除冗余屬性數(shù)據(jù)集的降維發(fā)現(xiàn)數(shù)據(jù)模式挖掘決策規(guī)則在其它領(lǐng)域的應(yīng)用金融商業(yè)……2/5/202318粗糙集理論在知識(shí)發(fā)現(xiàn)中的作用在數(shù)據(jù)預(yù)處理過程中，粗糙集理論可以用于對(duì)遺失數(shù)據(jù)的填補(bǔ)。在數(shù)據(jù)準(zhǔn)備過程中，利用粗糙集理論的數(shù)據(jù)約簡特性，對(duì)數(shù)據(jù)集進(jìn)行降維操作。在數(shù)據(jù)挖掘階段，可將粗糙集理論用于分類規(guī)則的發(fā)現(xiàn)。2/5/202319粗糙集理論在知識(shí)發(fā)現(xiàn)中的作用（續(xù)）在數(shù)據(jù)挖掘階段的主要作用通過布爾推理挖掘出約簡的規(guī)則來解釋決策通過熵理論將規(guī)則的復(fù)雜性和預(yù)測的誤差分析溶入到無條件的度量中與模糊集理論、證據(jù)理論構(gòu)成復(fù)合分析方法搜尋隱含在數(shù)據(jù)中的確定性或非確定性的規(guī)則……在解釋與評(píng)估過程中，粗糙集理論可用于對(duì)所得到的結(jié)果進(jìn)行統(tǒng)計(jì)評(píng)估。2/5/202320二、粗糙集理論的基本原理知識(shí)分類分類是推理、學(xué)習(xí)與決策中的關(guān)鍵問題。粗糙集理論假定知識(shí)是一種對(duì)對(duì)象進(jìn)行分類的能力?！皩?duì)象”是指我們所能言及的任何事物，比如實(shí)物、狀態(tài)、抽象概念、過程和時(shí)刻等。知識(shí)必須與具體或抽象世界的特定部分相關(guān)的各種分類模式聯(lián)系在一起，這種特定部分稱為全域或論域(universe)。知識(shí)構(gòu)成了某一感興趣領(lǐng)域中各種分類模式的一個(gè)族集(family)。2/5/202321二、粗糙集理論的基本原理粗糙集理論與傳統(tǒng)的集合理論有著相似之處，但是它們的出發(fā)點(diǎn)完全不同。傳統(tǒng)集合論認(rèn)為，一個(gè)集合完全是由其元素所決定，一個(gè)元素要么屬于這個(gè)集合，要么不屬于這個(gè)集合，即它的隸屬函數(shù)X(x){0,1}。模糊集合給成員賦予一個(gè)隸屬度，即X(x)[0,1]，傳統(tǒng)集合論和模糊集合論都是把隸屬關(guān)系作為原始概念來處理，集合的并和交就建立在其元素的隸屬度max和min操作上，因此其隸屬度必須事先給定在粗糙集中，隸屬關(guān)系不再是一個(gè)原始概念，因此無需人為給元素指定一個(gè)隸屬度，從而避免了主觀因素的影響。2/5/202322二、粗糙集理論的基本原理“知識(shí)”的定義使用等價(jià)關(guān)系集R對(duì)離散表示的空間U進(jìn)行劃分，知識(shí)就是R對(duì)U劃分的結(jié)果。“知識(shí)庫”的形式化定義等價(jià)關(guān)系集R中所有可能的關(guān)系對(duì)U的劃分表示為：K=(U,R)基本概念2/5/202323基本概念（續(xù)1）“信息系統(tǒng)”的形式化定義S={U,Q,V,f}，U：對(duì)象的有限集Q：屬性的有限集，Q=CD，C是條件屬性子集，D是決策屬性子集V：，Vp是屬性P的域f：U×A→

V是總函數(shù)，使得

對(duì)每個(gè)xi

U,qA,有f(xi,q)Vq一個(gè)關(guān)系數(shù)據(jù)庫可看作一個(gè)信息系統(tǒng)，其“列”為“屬性”，“行”為“對(duì)象”。2/5/202324基本概念（續(xù)2）基本集合（Elementaryset）/原子(Atom)關(guān)系R的等價(jià)類(Equivalenceclasses)U/R表示近似空間A上所有的基本集合（原子）不可區(qū)分（等價(jià)、不分明）關(guān)系U為論域，R是UU上的等價(jià)(Equivalence)關(guān)系（即滿足自反、對(duì)稱、傳遞性質(zhì)）A={U,R}稱為近似空間，R為不分明關(guān)系(indiscernibility，或不可區(qū)分關(guān)系、等價(jià)關(guān)系)若x,yU，(x,y)R，則x,y在A中是不分明的（不可區(qū)分的）2/5/202325基本概念（續(xù)3）不可區(qū)分（等價(jià)、不分明）關(guān)系（續(xù)）設(shè)PQ，xi,xj

U,定義二元關(guān)系INDP稱為不分明關(guān)系為：稱xi,xj在S中關(guān)于屬性集P是不分明的，當(dāng)且僅當(dāng)p(xi)=p(xj)對(duì)所有的pP成立，即xi,xj不能用P中的屬性加以區(qū)別。若x,yU，(x,y)R，則x,y在A中是不分明的（不可區(qū)分的）對(duì)所有的pP，INDP是U上一種的等價(jià)關(guān)系2/5/202326factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynoticynightyes4sunnyicydayno5foggynoticyduskyes6mistynoticynightno不可區(qū)分關(guān)系（等價(jià)關(guān)系）示例2/5/202327可知，U={1,2,3,4,5,6}R=2{weather,road,time,accident}若P={weather,road}，則[x]IND(P)=[x]IND{weather}

[x]INP{road}={{1,3,6},{2,5},{4}}{{1,2,4},{3,5,6}}={{1},{2},{4},{3,6},{5}}不可區(qū)分關(guān)系（等價(jià)關(guān)系）示例（續(xù)）2/5/202328集合的上近似&下近似在信息系統(tǒng)S={U,Q,V,f}中，設(shè)XU是個(gè)體全域上的子集，PQ則X的下和上近似集及邊界區(qū)域分別為：

PX是XU上必然被分類的那些元素的集合，即包含在X內(nèi)的最大可定義集；

X是U上可能被分類的那些元素的集合，即包含X的最小可定義集。

Bnd(X)是既不能在XU上被分類，又不能在U-X上被分類的那些元素的集合。2/5/202329

集合的上、下近似概念示意圖X2/5/202330InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthat

foreveryiscalledthevaluesetofa.

AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-492/5/202331DecisionSystems/TablesDS:isthedecisionattribute

(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.

AgeLEMSWalkx１16-3050

yesx216-300nox331-451-25nox431-451-25yesx546-6026-49

nox616-3026-49yesx746-6026-49no2/5/202332不可區(qū)分性實(shí)例

Thenon-emptysubsetsoftheconditionattributesare{Age},{LEMS},and{Age,LEMS}.IND({Age})={{x1,x2,x6},{x3,x4},{x5,x7}}IND({LEMS})={{x1},{x2},{x3,x4},{x5,x6,x7}}IND({Age,LEMS})={{x1},{x2},{x3,x4},{x5,x7},{x6}}.

AgeLEMSWalkx１16-30

50yesx216-30

0nox331-45

1-25nox431-45

1-25yesx546-6026-49nox616-3026-49yesx746-60

26-49no2/5/202333近似實(shí)例LetW={x|Walk(x)=yes}.

Thedecisionclass,Walk,isroughsincetheboundaryregionisnotempty.

AgeLEMSWalkx１16-3050

yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no2/5/202334Lower&UpperApproximations(3)

X1={u|Flu(u)=yes}={u2,u3,u6,u7}

RX1={u2,u3}={u2,u3,u6,u7,u8,u5}X2={u|Flu(u)=no}={u1,u4,u5,u8}

RX2={u1,u4}={u1,u4,u5,u8,u7,u6}TheindiscernibilityclassesdefinedbyR={Headache,Temp.}are{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.2/5/202335UsetＸU/RR:subsetofattributesLower&集近似圖示ns2/5/202336新型的隸屬關(guān)系設(shè)XU且xU,集合X的粗糙隸屬函數(shù)(roughmembershipfunction)

定義為

其中R是不分明關(guān)系.R(x)=[x]R={y:(yU)(yRx)}=1當(dāng)且僅當(dāng)[x]RX>0當(dāng)且僅當(dāng)[x]RX

=0當(dāng)且僅當(dāng)[x]RX=

顯然有[0,1]。隸屬關(guān)系是根據(jù)已有的分類知識(shí)客觀計(jì)算出來的，不是主觀給定的。2/5/202337近似度

AccuracyofApproximation

where|X|denotesthecardinalityofObviouslyIfXiscrispwithrespecttoB.IfXisroughwithrespecttoB.2/5/202338近似性質(zhì)

PropertiesofApproximationsimpliesand2/5/202339近似性質(zhì)

PropertiesofApproximations(2)where-XdenotesU-X.2/5/202340三、知識(shí)的約簡一般約簡定義

設(shè)R是等價(jià)關(guān)系的一個(gè)族集，且設(shè)R’R。若IND(R)=IND(R–R’)，則稱關(guān)系R’在族集R之中是可省的(dispensable)，否則就是不可省的。若族集R中的每個(gè)關(guān)系R’都是不可省的﹐則稱族集R是獨(dú)立的(independent)，否則就是依賴的或非獨(dú)立的。定義

若QP是獨(dú)立的，并且IND(Q)=IND(P)，則稱Q是關(guān)系族集P的一個(gè)約簡(reduct)。在族集P中所有不可省的關(guān)系的集合稱為P的核(core)，以CORE(P)來表示。

族集P有多個(gè)約簡（約簡的不唯一性）。定理1

族集P的核等于P的所有約簡的交集。2/5/202341核是信息系統(tǒng)中一系列最重要的屬性。在大多數(shù)情況下，分類是由幾個(gè)甚至一個(gè)屬性來決定的，而不是由關(guān)系數(shù)據(jù)庫中的所有屬性的微小差異來決定。屬性約簡及核的概念為提取系統(tǒng)中重要屬性及其值提供了有力的數(shù)學(xué)工具。這種約簡是本著不破壞原始數(shù)據(jù)集的分類質(zhì)量的，通俗地說，它是完全“保真”的。三、知識(shí)的約簡2/5/202342設(shè)有一知識(shí)庫K={U,{p,q,r}}﹐其中

U={x1,x2,x3,x4,x5,x6,x7,x8}﹐且

U/p={{x1,x4,x5},{x2,x8},{x3},{x6,x7}} U/q={{x1,x3,x5},{x6},{x2,x4,x7,x8}} U/r={{x1,x5},{x6},{x2,x7,x8},{x3,x4}}

則[x1]p={x1,x4,x5}﹐[x1]q={x1,x3,x5}。

若P={p,q,r},

則IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}

對(duì)于U上的子集X1={x1,x4,x7}﹐可得到

P

X1={x4}∪{x7}={x4,x7}

X1={x1,x5}∪{x4}∪{x7}={x1,x4,x5,x7}IND(P-p})={{x1,x5},{x2,x7,x8},{x3},{x4},{x6}}IND(P)

所以p是不可省的，同理可得q、r是可省的。由{p,q,r}三個(gè)等價(jià)關(guān)系組成的集合和{p,q}、{p,r}定義了相同的不分明關(guān)系。

{p}是P的核﹐也就是說p是絕對(duì)不能省的

2/5/202343相對(duì)約簡定義設(shè)P和Q是全域U上的等價(jià)關(guān)系的族集，所謂族集Q的P-正區(qū)域(P-positiveregionofQ)，記作POSP(Q)=

P(X)族集Q的P-正區(qū)域是全域U的所有那些使用分類U/P所表達(dá)的知識(shí)，能夠正確地分類于U/Q的等價(jià)類之中的對(duì)象的集合。定義設(shè)P和Q是全域U上的等價(jià)關(guān)系的族集，RP。若

POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q))則稱關(guān)系R在族集P中是Q-可省的﹐否則稱為Q-不可省的﹔如果在族集P中的每個(gè)關(guān)系R都是Q-不可省的﹐則稱P關(guān)于Q是獨(dú)立的﹐否則就稱為是依賴的。

2/5/202344相對(duì)約簡定義SP稱為P的Q-約簡(Q-reduct)﹐當(dāng)且僅當(dāng)S是P的Q-獨(dú)立的子族集﹐且POSS(Q)=POSP(Q)；族集P中的所有Q-不可省的初等關(guān)系的集合﹐稱為族集P的Q-核(Q-core)﹐記作COREQ(P)。 下面的定理是定理1的拓廣。定理2

族集P的Q-核等于族集P的所有Q-約簡的交集。即

COREQ(P)=REDQ(P)

其中REDQ(P)是族集P的所有Q-約簡的族集。2/5/202345知識(shí)的依賴性

知識(shí)的依賴性可形式定義如下：定義

設(shè)K=(U,R)是一個(gè)近似空間，P,QR。1)知識(shí)Q依賴于知識(shí)P或知識(shí)P可推導(dǎo)出知識(shí)Q，當(dāng)且僅當(dāng)IND(P)IND(Q)﹐記作PQ；2)知識(shí)P和知識(shí)Q是等價(jià)的﹐當(dāng)且僅當(dāng)PQ且QP﹐即IND(P)=IND(Q)﹐記作P=Q，明顯地，P=Q當(dāng)且僅當(dāng)IND(P)=IND(Q)；3)知識(shí)P和知識(shí)Q是獨(dú)立的，當(dāng)且僅當(dāng)PQ且QP均不成立，記作PQ。2/5/202346知識(shí)的依賴性 依賴性也可以是部分成立的﹐也就是從知識(shí)P能推導(dǎo)出知識(shí)Q的一部分知識(shí)，或者說知識(shí)Q只有一部分依賴于知識(shí)P的。部分依賴性（部分可推導(dǎo)性）可以由知識(shí)的正區(qū)域來定義。定義1設(shè)K=(U,R)是一個(gè)知識(shí)庫﹐P,QR﹐我們稱知識(shí)Q以依賴度k(0k1)依賴于知識(shí)P﹐記作PkQ﹐當(dāng)且僅當(dāng)

k=P(Q)=card(POSP(Q))/card(U)(1)若k=1﹐則稱知識(shí)Q完全依賴于知識(shí)P，P1Q也記成PQ；(2)若0k1﹐則稱知識(shí)Q部分依賴于知識(shí)P；(3)若k=0﹐則稱知識(shí)Q完全獨(dú)立于與知識(shí)P。2/5/202347四、決策表的約簡決策表 決策表是一類特殊而重要的知識(shí)表達(dá)系統(tǒng)，它指當(dāng)滿足某些條件時(shí)，決策（行為）應(yīng)當(dāng)怎樣進(jìn)行。決策表可以定義如下：

S=(U,A)為一信息系統(tǒng)，且C,DA是兩個(gè)屬性子集，分別稱為條件屬性和決策屬性，且CD=A，CD=，則該信息系統(tǒng)稱為決策表，記作T=(U,A,C,D)或簡稱CD決策表。關(guān)系IND(C)和關(guān)系IND(D)的等價(jià)類分別稱為條件類和決策類。

2/5/202348

身高性別視力錄取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1一決策表身高、性別、視力為條件屬性，錄取為決策屬性

2/5/202349決策規(guī)則決策表中的每一行對(duì)應(yīng)諸如形式的決策規(guī)則，和分別稱為決策規(guī)則的前驅(qū)和后繼。當(dāng)決策表S中決策規(guī)則為真時(shí)，我們說該決策規(guī)則是S中一致的，否則說該決策規(guī)則是S中不一致的。若決策規(guī)則是S中一致的，相同的前驅(qū)必導(dǎo)致相同的后繼；但同一種后繼不一定必需是同一前驅(qū)產(chǎn)生的。 如表1第一行對(duì)應(yīng)決策規(guī)則： 身高(高)性別(男)視力(差)錄取(否)

2/5/202350決策表的一致性命題1

當(dāng)且僅當(dāng)CD，決策表T=(U,A,C,D)是一致的?？梢酝ㄟ^計(jì)算條件屬性和決策屬性間的依賴程度來檢查一致性。當(dāng)依賴程度等于1時(shí)，決策表是一致的，否則不一致。2/5/202351決策表的分解命題2

每個(gè)決策表T=(U,A,C,D)都可以唯一分解為兩個(gè)決策表T1=(U1,A,C,D)和T2=(U2,A,C,D)，這樣使得表T1中C1D和T2中C0D。這里U1=POSC(D)，U2=BNC(X)，XU|IND(D)。由命題2可見，假設(shè)我們已計(jì)算出條件屬性的依賴度，若表的結(jié)果不一致，即依賴度小于1，則由命題2可以將表分解成兩個(gè)子表：其中一個(gè)表完全不一致，依賴度為0；另一個(gè)表則完全一致，依賴度為1。只有依賴度大于0且不等于1時(shí)，這一分解才能進(jìn)行。2/5/202352表2不一致決策表

a、b、c為條件屬性，d、e為決策屬性

1、5產(chǎn)生不一致2、8產(chǎn)生不一致Uabcde1234567810220011122001111022102012201121112011012/5/202353表3完全一致的決策表Uabcde346720011110222201121112表4完全不一致的決策表Uabcde1258102200111210201011012/5/202354一致決策表的約簡在我們制定決策時(shí)是否需要全部的條件屬性，能否進(jìn)行決策表的約簡,使得約簡后的決策表具有與約簡前的決策表相同的功能，且約簡后的決策表具有更少的條件屬性。一致決策表的約簡步驟如下：

(1)對(duì)決策表進(jìn)行條件屬性的約簡，即從決策表中消去某一列；

(2)消去重復(fù)的行；

(3)消去每一決策規(guī)則中屬性的冗余值。

2/5/202355條件屬性的約簡A.Skowron提出了分明矩陣，使核與約簡等概念的計(jì)算較為簡單，主要思想：設(shè)S=(U,A)為一個(gè)知識(shí)表示系統(tǒng)，其中U={x1,x2,…,xn}，xi為所討論的個(gè)體，i=1,2,…,n，A={a1,a2,…,am}，aj為個(gè)體所具有的屬性，j=1,2,…,m。 知識(shí)表達(dá)系統(tǒng)S的分明矩陣M(S)=[cij]n×n，其中矩陣項(xiàng)定義如下：

cij={a∈A：a(xi)≠a(xj)，i,j=1,2,…,n}

因此cij是個(gè)體xi與xj有區(qū)別的所有屬性的集合2/5/202356分明矩陣對(duì)應(yīng)的核與約簡核可以定義為分明矩陣中所有只有一個(gè)元素的矩陣項(xiàng)的集合，即

CORE(A)={a∈A：cij=(a)，對(duì)一些i,j}

若屬性集合BA是滿足下列條件

B∩cij≠，對(duì)于M(S)中的任一非空項(xiàng)cij≠

的一個(gè)最小屬性子集，則稱屬性集合BA是A的一個(gè)約簡。約簡是這樣的最小屬性子集，它能夠區(qū)分用整個(gè)屬性集合A可區(qū)分的所有對(duì)象。2/5/202357Skowron的約簡方法每一個(gè)分明矩陣M(S)對(duì)應(yīng)唯一的分明函數(shù)fM(S)﹙DiscernibilityFunction﹚，其定義如下： 信息系統(tǒng)S的分明函數(shù)fM(S)是一個(gè)有m-元變量a1,…,am(ai∈A，i=1,…,m)的布爾函數(shù)，它是∨cij的合取，∨cij是矩陣項(xiàng)cij中的各元素的析取，1≤j<i≤n且cij≠Φ。 根據(jù)分明函數(shù)與約簡的對(duì)應(yīng)關(guān)系，A.Skowron提出了計(jì)算信息系統(tǒng)S的約簡RED(S)的方法：

1）計(jì)算信息系統(tǒng)S的分明矩陣M(S) 2）計(jì)算與分明矩陣M(S)對(duì)應(yīng)的分明函數(shù)fM(S) 3）計(jì)算分明函數(shù)fM(S)的最小析取范式，其中每個(gè)析取分量對(duì)應(yīng)一個(gè)約簡2/5/202358

采用分明矩陣的方法對(duì)條件屬性進(jìn)行約簡，考慮下面的決策表5，條件屬性為a,b,c,d，決策屬性為eU/Aabcdeu111210u200121u320210u400222u511210表52/5/202359表5對(duì)應(yīng)的分明矩陣uu1u2u3u4u5u1

u2a,bc,d

u3

a,c,d

u4a,bdca,d

u5

a,b,c,d

a,b,d

由下面的分明矩陣很容易得到核為{c}，分明函數(shù)fM(S)為c∧(a∨d)，即(a∧c)∨(c∧d)，得到兩個(gè)約簡{a,c}和{c,d}2/5/202360表6根據(jù)得到的兩個(gè)約簡，表5可以簡化為表6和表7U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222u5210表72/5/202361求最優(yōu)或次優(yōu)約簡所有約簡的計(jì)算是NP-hard問題，因此運(yùn)用啟發(fā)信息來簡化計(jì)算以找出最優(yōu)或次優(yōu)約簡是必要的。

現(xiàn)在在求最優(yōu)或次優(yōu)約簡的算法一般都使用核作為計(jì)算約簡的出發(fā)點(diǎn)，計(jì)算一個(gè)最好的或者用戶指定的最小約簡。算法將屬性的重要性作為啟發(fā)規(guī)則，按照屬性的重要度從大到小逐個(gè)加入屬性，直到該集合是一個(gè)約簡為止。

2/5/202362行的約簡

對(duì)決策表中的重復(fù)的行要?jiǎng)h除，因?yàn)樗鼈兊臈l件屬性和決策屬性都相同，都表示同一條決策規(guī)則。另外，決策規(guī)則的列表順序不是本質(zhì)性的，所以表6、表7都可進(jìn)行約簡，如表6可簡化為下表：U\Aaceu1120u2011u3220u4022表82/5/202363屬性值的約簡對(duì)于決策表而言，屬性值的約簡就是決策規(guī)則的約簡。決策規(guī)則的約簡是利用決策邏輯消去每個(gè)決策規(guī)則的不必要條件，針對(duì)每個(gè)決策規(guī)則，去掉表達(dá)該規(guī)則時(shí)的冗余屬性值，即要計(jì)算每條決策規(guī)則的核與約簡。2/5/202364非一致決策表的約簡對(duì)于一致的決策表比較容易處理，在進(jìn)行約簡時(shí)，只要判斷去掉某個(gè)屬性或某個(gè)屬性值時(shí)是否會(huì)導(dǎo)致不一致規(guī)則的產(chǎn)生。而對(duì)不一致表進(jìn)行約簡時(shí)就不能再使用這種方法了，一般采用下面的方法：一種是考慮正域的變化，另外一種是將不一致表分成完全一致表和完全不一致表兩個(gè)子表。非一致決策表的約簡步驟與一致決策表的約簡步驟類似。2/5/202365五、粗糙集的擴(kuò)展模型基本粗糙集理論的主要存在的問題是：

1)對(duì)原始數(shù)據(jù)本身的模糊性缺乏相應(yīng)的處理能力；

2)對(duì)于粗糙集的邊界區(qū)域的刻畫過于簡單；

3)粗糙集理論的方法在可用信息不完全的情況下將對(duì)象們歸類于某一具體的類，通常分類是確定的，但并未提供數(shù)理統(tǒng)計(jì)中所常用的在一個(gè)給定錯(cuò)誤率的條件下將盡可能多的對(duì)象進(jìn)行分類的方法，而實(shí)際中常常遇到這類問題。

2/5/202366可變精度粗糙集模型W.Ziarko提出了一種稱之為可變精度粗糙集模型，該模型給出了錯(cuò)誤率低于預(yù)先給定值的分類策略，定義了該精度下的正區(qū)域、邊界區(qū)域和負(fù)區(qū)域。下面扼要地介紹其思想：

一般地，集合X包含于Y并未反映出集合X的元素屬于集合Y的“多少”。為此，VPRS定義了它的量度：

C(X,Y)=1–card(XY)/card(X)當(dāng)card(x)>0，

C(X,Y)=0當(dāng)card(x)=0。

C(X,Y)表示把集合X歸類于集合Y的誤分類度，即有C(X,Y)100%的元素歸類錯(cuò)誤。顯然，C(X,Y)=0時(shí)有XY。如此，可事先給定一錯(cuò)誤分類率(0<0.5)，基于上述定義，我們有XY，當(dāng)且僅當(dāng)C(X,Y)。2/5/202367可變精度粗糙集模型 在此基礎(chǔ)上，設(shè)U為論域且R為U上的等價(jià)關(guān)系，U/R=A={X1,X2,…,Xk}，這樣，可定義集合X的-下近似為RX=Xi(XiX,i=1,2,…,k)

或

RX=Xi(C(Xi,X),i=1,2,…,k)， 并且RX稱為集合X的-正區(qū)域，集合X的-上近似為RX=Xi(C(Xi,X)<1–,i=1,2,…,k)， 這樣，-邊界區(qū)域就定義為：BNRX=Xi(<C(Xi,X)<1–)； -負(fù)區(qū)域?yàn)椋篘EGRX=Xi(C(Xi,X)1–)。 以此類推，我們還可以定義-依賴、-約簡等與傳統(tǒng)粗糙集模型相對(duì)應(yīng)的概念。2/5/202368基于粗糙集的非單調(diào)邏輯自粗糙集理論提出以來，粗糙集理論的研究者都很重視它的邏輯研究，試圖通過粗糙集建立粗糙邏輯，也相應(yīng)地發(fā)表了一系列的粗糙邏輯方面的論文。2/5/202369與其它數(shù)學(xué)工具的結(jié)合

D.Dudios和H.Prade由此提出了RoughFuzzySet和FuzzyRoughSet的概念

A.Skowron和J.Grazymala-Buss認(rèn)為，粗糙集理論可以看作證據(jù)理論的基礎(chǔ)。并在粗糙集理論的框架上重新解釋了證據(jù)理論的基本概念，特別是用上近似和下近似的術(shù)語解釋了信念(belief)和似然(plausibility)函數(shù)，進(jìn)而討論了兩者之間的互補(bǔ)問題。

2/5/202370六、粗糙集的實(shí)驗(yàn)系統(tǒng)在過去幾年中，建立了不少基于粗糙集的KDD系統(tǒng)，其中最有代表性的有LERS、ROSE、KDD-R等。

1．LERS LERS(LearningfromexamplesbasedonRoughSet)系統(tǒng)是美國Kansas大學(xué)開發(fā)的基于粗糙集的實(shí)例學(xué)習(xí)系統(tǒng)。它是用CommonLisp在VAX9000上實(shí)現(xiàn)的。LERS已經(jīng)為NASA的Johnson空間中心應(yīng)用了兩年。此外，LERS還被廣泛地用于環(huán)境保護(hù)、氣候研究和醫(yī)療研究

2/5/202371六、粗糙集的實(shí)驗(yàn)系統(tǒng)

2．ROSE

波蘭Poznan科技大學(xué)基于粗糙集開發(fā)了ROSE(RoughSetdataExplorer),用于決策分析。它是RoughDas&RoughClass系統(tǒng)的新版，其中RoughDas執(zhí)行信息系統(tǒng)數(shù)據(jù)分析任務(wù)，RoughClass支持新對(duì)象的分類，這兩個(gè)系統(tǒng)已經(jīng)在許多實(shí)際領(lǐng)域中得到應(yīng)用。

3．KDD—R KDD-R是由加拿大的Regina大學(xué)開發(fā)的基于可變精度粗糙集模型，采用知識(shí)發(fā)現(xiàn)的決策矩陣方法開發(fā)了KDD-R系統(tǒng)，這個(gè)系統(tǒng)被用來對(duì)醫(yī)學(xué)數(shù)據(jù)分析，以此產(chǎn)生癥狀與病證之間新的聯(lián)系，另外它還支持電信工業(yè)的市場研究。

2/5/202372粗糙集網(wǎng)站可以在http://www.cs.uregina.ca/~roughset的ElectronicBulletinoftheRoughSetCommunity中看到粗糙集研究的進(jìn)展。2/5/202373七、粒度計(jì)算粒度計(jì)算從廣義上來說是一種看待客觀世界的世界觀和方法論。

粒度計(jì)算的基本思想就是使用粒而不是對(duì)象為計(jì)算單元，使用粒、粒集以及粒間關(guān)系進(jìn)行計(jì)算或問題求解。2/5/202374粒度計(jì)算1997年LotfiA.Zadeh

提出了粒度的概念，他認(rèn)為在人類認(rèn)知中存在三種概念：粒度，組織與因果關(guān)系。從直觀的來講，?；婕暗綇恼w到部分的分解，而組織卻是從部分到整體的集成，而因果關(guān)系涉及原因與結(jié)果之間的聯(lián)系。對(duì)一個(gè)事物的粒化就是以可分辨性、相似性、鄰近性與功能性集聚有關(guān)的事物。粒度計(jì)算是信息處理的一種新的概念和計(jì)算范式，覆蓋了所有有關(guān)粒度的理論、方法、技術(shù)和工具的研究，主要用于處理不確定的、模糊的、不完整的和海量的信息。粗略地講，一方面它是模糊信息粒度理論、粗糙集理論、商空間理論、區(qū)間計(jì)算等的超集，另一方面是粒度數(shù)學(xué)的子集。具體地講，凡是在分析問題和求解問題中，應(yīng)用了分組、分類、聚類以及層次化手段的一切理論與方法均屬于粒度計(jì)算的范疇。信息粒度在粒度計(jì)算，詞計(jì)算，感知計(jì)算理論和精化自然語言中都有反映

2/5/202375粒度計(jì)算的必要性從哲學(xué)的角度看

Yager和Filev指出“人類已經(jīng)形成了世界就是一個(gè)粒度的觀點(diǎn)”以及“人們觀察、度量、定義和推理的實(shí)體都是粒度”。信息粒是一種抽象，它如同數(shù)學(xué)中的“點(diǎn)”、“線”、“面”一樣，在人類的思維和活動(dòng)中占有重要地位。從人工智能的角度看

張鈸院士指出“人類智能的公認(rèn)特點(diǎn)，就是人們能從極不相同的粒度上觀察和分析同一問題。人們不僅能在不同粒度的世界上進(jìn)行問題求解，而且能夠很快地從一個(gè)粒度世界跳到另一個(gè)粒度的世界，往返自如，毫無困難。這種處理不同世界的能力，正是人類問題求解的強(qiáng)有力的表現(xiàn)”。2/5/202376粒度計(jì)算的必要性從優(yōu)化論的角度來看

粒度計(jì)算的理論與方法在觀念上突破了傳統(tǒng)優(yōu)化思想的束縛，不再以數(shù)學(xué)上的精確解為目標(biāo)，即：需要的是很好地理解和刻畫一個(gè)問題，而不是沉溺于那些用處不大的細(xì)節(jié)信息上。粒度計(jì)算的方法不要求目標(biāo)函數(shù)和約束函數(shù)的連續(xù)性與凸性，甚至有時(shí)連解析表達(dá)式都不要求，而且對(duì)計(jì)算中數(shù)據(jù)的不確定性也有很強(qiáng)地適應(yīng)能力，計(jì)算速度也快，這些優(yōu)點(diǎn)使粒度計(jì)算具有更廣泛地應(yīng)用前景，所以，粒度計(jì)算理