aai09粗糙集高級(jí)人工智能史忠植

1、第九章 知識(shí)發(fā)現(xiàn) 粗糙集 史忠植 中科院計(jì)算所10/12/20221高級(jí)人工智能 史忠植內(nèi)容一、概述述二、知識(shí)識(shí)分類(lèi)三、知識(shí)識(shí)的約簡(jiǎn)簡(jiǎn)四、決策策表的約約簡(jiǎn)五、粗糙糙集的擴(kuò)擴(kuò)展模型型六、粗糙糙集的實(shí)實(shí)驗(yàn)系統(tǒng)統(tǒng)3/1/20202高級(jí)人工工智能史史忠植植一、概概述現(xiàn)實(shí)生活活中有許許多含糊糊現(xiàn)象并并不能簡(jiǎn)簡(jiǎn)單地用用真、假假值來(lái)表表示如如何表示示和處理理這些現(xiàn)現(xiàn)象就成成為一個(gè)個(gè)研究領(lǐng)領(lǐng)域。早早在1904年謂詞邏邏輯的創(chuàng)創(chuàng)始人G.Frege就提出了了含糊(Vague)一詞，他他把它歸歸結(jié)到邊邊界線上上，也就就是說(shuō)在在全域上上存在一一些個(gè)體體既不能能在其某某個(gè)子集集上分類(lèi)類(lèi)，也不不能在該該子集的的補(bǔ)集上上分

2、類(lèi)。3/1/20203高級(jí)人工工智能史史忠植植模糊集1965年，Zadeh提出出了模糊糊集，不不少理論論計(jì)算機(jī)機(jī)科學(xué)家家和邏輯輯學(xué)家試試圖通過(guò)過(guò)這一理理論解決決G.Frege的含含糊概念念，但模模糊集理理論采用用隸屬度度函數(shù)來(lái)來(lái)處理模模糊性，而基本本的隸屬屬度是憑憑經(jīng)驗(yàn)或或者由領(lǐng)領(lǐng)域?qū)＜壹医o出，所以具具有相當(dāng)當(dāng)?shù)闹饔^觀性。3/1/20204高級(jí)人工工智能史史忠植植粗糙集的的提出20世紀(jì)紀(jì)80年年代初，波蘭的的Pawlak針對(duì)G.Frege的邊界界線區(qū)域域思想提提出了粗粗糙集（RoughSet）他他把那些些無(wú)法確確認(rèn)的個(gè)個(gè)體都?xì)w歸屬于邊邊界線區(qū)區(qū)域，而而這種邊邊界線區(qū)區(qū)域被定定義為上上近似集集和

3、下近近似集之之差集。由于它它有確定定的數(shù)學(xué)學(xué)公式描描述，完完全由數(shù)數(shù)據(jù)決定定，所所以更有有客觀性性 。3/1/20205高級(jí)人工工智能史史忠植植粗糙集的的研究粗糙集理理論的主主要優(yōu)勢(shì)勢(shì)之一是是它不需需要任何何預(yù)備的的或額外外的有關(guān)關(guān)數(shù)據(jù)信信息。自自提出以以來(lái)，許許多計(jì)算算機(jī)科學(xué)學(xué)家和數(shù)數(shù)學(xué)家對(duì)對(duì)粗糙集集理論及及其應(yīng)用用進(jìn)行了了堅(jiān)持不不懈的研研究，使使之在理理論上日日趨完善善，特別別是由于于20世世紀(jì)80年代末末和90年代初初在知識(shí)識(shí)發(fā)現(xiàn)等等領(lǐng)域得得到了成成功的應(yīng)應(yīng)用而越越來(lái)越受受到國(guó)際際上的廣廣泛關(guān)注注。3/1/20206高級(jí)人工工智能史史忠植植粗糙集的的研究1991年波蘭蘭Pawlak教授的

4、的第一本本關(guān)于粗粗糙集的的專(zhuān)著RoughSets：Theoretical AspectsofReasoning about Data和1992年年R.Slowinski主主編的關(guān)關(guān)于粗糙糙集應(yīng)用用及其與與相關(guān)方方法比較較研究的的論文集集的出版版，推動(dòng)動(dòng)了國(guó)際際上對(duì)粗粗糙集理理論與應(yīng)應(yīng)用的深深入研究究。1992年年在波蘭蘭Kiekrz召開(kāi)了了第1屆屆國(guó)際粗粗糙集討討論會(huì)。從此每每年召開(kāi)開(kāi)一次與與粗糙集集理論為為主題的的國(guó)際研研討會(huì)。3/1/20207高級(jí)人工工智能史史忠植植研究現(xiàn)狀狀分析史忠植. 知識(shí)識(shí)發(fā)現(xiàn). 北京京:清清華大學(xué)學(xué)出版社社,2002劉清.RoughSet及Rough推理. 北京京

5、:科科學(xué)出版版社,2001張文修等等.RoughSet理理論與方方法.北北京: 科學(xué)學(xué)出版社社,2001王國(guó)胤, Rough Set理論論與知識(shí)識(shí)獲取. 西安安:西西安交通通大學(xué)出出版社, 2001曾黃麟. 粗集集理論及及其應(yīng)用用(修訂訂版). 重慶慶:重重慶大學(xué)學(xué)出版社社,19983/1/20208高級(jí)人工工智能史史忠植植研究現(xiàn)狀狀分析2001年5月月在重慶慶召開(kāi)了了“第1屆中國(guó)國(guó)Rough集集與軟計(jì)計(jì)算學(xué)術(shù)術(shù)研討會(huì)會(huì)”，邀邀請(qǐng)了創(chuàng)創(chuàng)始人Z.Pawlak教教授做大大會(huì)報(bào)告告；2002年10月在蘇蘇州第第2屆2003年5月月在重慶慶第第3屆屆，同時(shí)時(shí)舉辦“第9屆屆粗糙集集、模糊糊集、數(shù)數(shù)據(jù)挖掘

6、掘和粒度度-軟計(jì)計(jì)算的國(guó)國(guó)際會(huì)議議”因因非非典推遲遲到10月中科院計(jì)計(jì)算所、中科院院自動(dòng)化化所、北北京工業(yè)業(yè)大學(xué)、西安交交通大學(xué)學(xué)、重慶慶郵電學(xué)學(xué)院、山山西大學(xué)學(xué)、合肥肥工業(yè)大大學(xué)、上上海大學(xué)學(xué)、南昌昌大學(xué)3/1/20209高級(jí)人工工智能史史忠植植二、知知識(shí)分類(lèi)類(lèi)基本粗糙糙集理論論認(rèn)為知知識(shí)就是是人類(lèi)和和其他物物種所固固有的分分類(lèi)能力力。例如如，在現(xiàn)現(xiàn)實(shí)世界界中關(guān)于于環(huán)境的的知識(shí)主主要表明明了生物物根據(jù)其其生存觀觀來(lái)對(duì)各各種各樣樣的情形形進(jìn)行分分類(lèi)區(qū)別別的能力力。每種種生物根根據(jù)其傳傳感器信信號(hào)形成成復(fù)雜的的分類(lèi)模模式，就就是這種種生物的的基本機(jī)機(jī)制。分分類(lèi)是推推理、學(xué)學(xué)習(xí)與決決策中的的關(guān)鍵問(wèn)

7、問(wèn)題。因因此，粗粗糙集理理論假定定知識(shí)是是一種對(duì)對(duì)對(duì)象進(jìn)進(jìn)行分類(lèi)類(lèi)的能力力。這里里的“對(duì)對(duì)象”是是指我們們所能言言及的任任何事物物，比如如實(shí)物、狀態(tài)、抽象概概念、過(guò)過(guò)程和時(shí)時(shí)刻等等等。即知知識(shí)必須須與具體體或抽象象世界的的特定部部分相關(guān)關(guān)的各種種分類(lèi)模模式聯(lián)系系在一起起，這種種特定部部分稱(chēng)之之為所討討論的全域或論域(universe)。對(duì)于于全域及及知識(shí)的的特性并并沒(méi)有任任何特別別假設(shè)。事實(shí)上上，知識(shí)識(shí)構(gòu)成了了某一感感興趣領(lǐng)領(lǐng)域中各各種分類(lèi)類(lèi)模式的的一個(gè)族族集(family)，這個(gè)個(gè)族集提提供了關(guān)關(guān)于現(xiàn)實(shí)實(shí)的顯事事實(shí)，以以及能夠夠從這些些顯事實(shí)實(shí)中推導(dǎo)導(dǎo)出隱事事實(shí)的推推理能力力。3/1/202

8、010高級(jí)人工工智能史史忠植植二、知知識(shí)分類(lèi)類(lèi)為數(shù)學(xué)處處理方便便起見(jiàn)，在下面面的定義義中用等等價(jià)關(guān)系系來(lái)代替替分類(lèi)。一個(gè)近似空間間(approximatespace)（或知識(shí)庫(kù)）定義為為一個(gè)關(guān)關(guān)系系統(tǒng)統(tǒng)（或二二元組）K=(U,R)其中U（為空集集）是一一個(gè)被稱(chēng)稱(chēng)為全域域或論域域(universe)的所所有要討討論的個(gè)個(gè)體的集集合，R是U上等等價(jià)關(guān)系系的一個(gè)個(gè)族集。3/1/202011高級(jí)人工工智能史史忠植植二、知知識(shí)分類(lèi)類(lèi)設(shè)PR，且P ，P中所有等等價(jià)關(guān)系系的交集集稱(chēng)為P上的一種種難區(qū)分分關(guān)系(indiscernbility relation)（或稱(chēng)難難區(qū)分關(guān)關(guān)系），記作IND(P)，即xIN

9、D(p)= IxRRP注意，IND(P)也是等等價(jià)關(guān)系系且是唯唯一的。3/1/202012高級(jí)人工工智能史史忠植植二、知知識(shí)分類(lèi)類(lèi)給定近似似空間K=(U,R)，子集XU稱(chēng)為U上的一個(gè)個(gè)概念(concept)，形式上上，空集集也視為為一個(gè)概概念；非非空子族族集PR所產(chǎn)生的的不分明明關(guān)系IND(P)的所有等等價(jià)類(lèi)關(guān)關(guān)系的集集合即U/IND(P)，稱(chēng)為基本知識(shí)識(shí)(basicknowledge)，相應(yīng)的的等價(jià)類(lèi)類(lèi)稱(chēng)為基本概念念(basicconcept)；特別地地，若關(guān)關(guān)系QR，則關(guān)系系Q就稱(chēng)為初等知識(shí)識(shí)(elementaryknowledge)，相應(yīng)的的等價(jià)類(lèi)類(lèi)就稱(chēng)為為初等概念念(elementar

10、yconcept)。一般用大大寫(xiě)字母母P,Q,R等表示一一個(gè)關(guān)系系，用大大寫(xiě)黑體體字母P,Q,R等表示關(guān)關(guān)系的族族集；xR或R(x)表示關(guān)系系R中包含元元素xU的概念或或等價(jià)類(lèi)類(lèi)。為了了簡(jiǎn)便起起見(jiàn)，有有時(shí)用P代替IND(P)。根據(jù)上述述定義可可知，概概念即對(duì)對(duì)象的集集合，概概念的族族集（分分類(lèi)）就就是U上上的知識(shí)識(shí)，U上上分類(lèi)的的族集可可以認(rèn)為為是U上上的一個(gè)個(gè)知識(shí)庫(kù)庫(kù)，或說(shuō)說(shuō)知識(shí)庫(kù)庫(kù)即是分分類(lèi)方法法的集合合。3/1/202013高級(jí)人工工智能史史忠植植二、知知識(shí)分類(lèi)類(lèi)粗糙集理理論與傳傳統(tǒng)的集集合理論論有著相相似之處處，但是是它們的的出發(fā)點(diǎn)點(diǎn)完全不不同。傳傳統(tǒng)集合合論認(rèn)為為，一個(gè)個(gè)集合完完全是

11、由由其元素素所決定定，一個(gè)個(gè)元素要要么屬于于這個(gè)集集合，要要么不屬屬于這個(gè)個(gè)集合，即它的的隸屬函函數(shù)X(x)0,1。模模糊集合合對(duì)此做做了拓廣廣，它給給成員賦賦予一個(gè)個(gè)隸屬度度，即X(x)0,1，使使得模糊糊集合能能夠處理理一定的的模糊和和不確定定數(shù)據(jù)，但是其其模糊隸隸屬度的的確定往往往具有有人為因因素，這這給其應(yīng)應(yīng)用帶來(lái)來(lái)了一定定的不便便。而且且，傳統(tǒng)統(tǒng)集合論論和模糊糊集合論論都是把把隸屬關(guān)關(guān)系作為為原始概概念來(lái)處處理，集集合的并并和交就就建立在在其元素素的隸屬屬度max和min操操作上，因此其其隸屬度度必須事事先給定定（傳統(tǒng)統(tǒng)集合默默認(rèn)隸屬屬度為1或0）。在粗粗糙集中中，隸屬屬關(guān)系不不再是

12、一一個(gè)原始始概念，因此無(wú)無(wú)需人為為給元素素指定一一個(gè)隸屬屬度，從從而避免免了主觀觀因素的的影響。3/1/202014高級(jí)人工工智能史史忠植植InformationSystems/TablesISisa pair(U,A)Uisa non-emptyfiniteset of objects.Aisa non-emptyfiniteset of attributessuchthatforeveryiscalledthe value setofa.AgeLEMSx16-3050 x216-300 x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6

13、026-493/1/202015高級(jí)人工工智能史史忠植植DecisionSystems/TablesDS:isthedecisionattribute(insteadofonewecan consider moredecisionattributes).TheelementsofAarecalled theconditionattributes.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/1/202016高級(jí)人工工智能史史忠植植Is

14、suesinthe Decision TableThesameorindiscernible objectsmay be represented severaltimes.Some of theattributes maybesuperfluous.3/1/202017高級(jí)人工工智能史史忠植植難區(qū)分性性IndiscernibilityTheequivalencerelationA binaryrelationwhichisreflexive(xRxforany objectx) ,symmetric(ifxRythenyRx),andtransitive (ifxRyandyRzthenxRz

15、).Theequivalenceclassof an elementconsistsofallobjectssuch thatxRy.3/1/202018高級(jí)人工工智能史史忠植植難區(qū)分性性Indiscernibility(2)LetIS= (U,A)beaninformationsystem, thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandxareindiscerniblefrom eachotherbyattribute

16、sfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby3/1/202019高級(jí)人工工智能史史忠植植難區(qū)分性性實(shí)例IndiscernibilityThenon-empty subsetsofthe conditionattributes areAge,LEMS,andAge,LEMS.IND(Age) =x1,x2,x6, x3,x4, x5,x7IND(LEMS)= x1,x2,x3,x4,x5,x6,x7IND(Age,LEMS)=x1,x2,x3,x4,x5,x7,x6.AgeLEMSWalkx16-3

17、050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/1/202020高級(jí)人工工智能史史忠植植概念的邊邊界知識(shí)的粒粒度性是是造成使使用已有有知識(shí)不不能精確確地表示示某些概概念的原原因。這這就產(chǎn)生生了所謂謂的關(guān)于于不精確確的“邊邊界”思思想。著著名哲學(xué)學(xué)家Frege認(rèn)為“概念必必須有明明確的邊邊界。沒(méi)沒(méi)有明確確邊界的的概念，將對(duì)應(yīng)應(yīng)于一個(gè)個(gè)在周?chē)鷩鷽](méi)有明明確界線線的區(qū)域域”。粗粗糙集理理論中的的模糊性性就是一一種基于于邊界的的概念，即一個(gè)個(gè)不精確確的概念念具有模模糊的不不可被

18、明明確劃分分的邊界界。為刻刻畫(huà)模糊糊性，每每個(gè)不精精確概念念由一對(duì)對(duì)稱(chēng)為上上近似與與下近似似的精確確概念來(lái)來(lái)表示，它們可可用隸屬屬函數(shù)定定義3/1/202021高級(jí)人工工智能史史忠植植粗糙集的的基本定定義知識(shí)的分分類(lèi)觀點(diǎn)點(diǎn)粗糙集理理論假定定知識(shí)是是一種對(duì)對(duì)對(duì)象進(jìn)進(jìn)行分類(lèi)類(lèi)的能力力。而知知識(shí)必須須與具體體或抽象象世界的的特定部部分相關(guān)關(guān)的各種種分類(lèi)模模式聯(lián)系系在一起起，這種種特定部部分稱(chēng)之之為所討討論的全域或論域(universe)。為數(shù)學(xué)處處理方便便起見(jiàn)，在下面面的定義義中用等等價(jià)關(guān)系系來(lái)代替替分類(lèi)。3/1/202022高級(jí)人工工智能史史忠植植粗糙集的的基本定定義定義1一個(gè)近似空間間(appr

19、oximatespace)(或知識(shí)庫(kù))定義為為一個(gè)關(guān)關(guān)系系統(tǒng)統(tǒng)(或二二元組)K=(U,R)，其中U(為空集)是一個(gè)個(gè)被稱(chēng)為為全域或或論域(universe)的所有要要討論的的個(gè)體的的集合，R是U上等價(jià)關(guān)關(guān)系的一一個(gè)族集集。定義2設(shè)PR，且P，P中所有等等價(jià)關(guān)系系的交集集稱(chēng)為P上的一種種不分明明關(guān)系(indiscernbility relation)（或稱(chēng)不不可區(qū)分分關(guān)系），記作作IND(P)3/1/202023高級(jí)人工工智能史史忠植植粗糙集的的基本定定義定義3給定近似似空間K=(U,R)，子集XU稱(chēng)為U上的一個(gè)個(gè)概念(concept)，形式上上，空集集也視為為一個(gè)概概念；非非空子族族集PR所產(chǎn)

20、生的的不分明明關(guān)系IND(P)的所有等等價(jià)類(lèi)關(guān)關(guān)系的集集合即U/IND(P)，稱(chēng)為基本知識(shí)識(shí)(basicknowledge)，相應(yīng)的的等價(jià)類(lèi)類(lèi)稱(chēng)為基本概念念(basicconcept)；特別地地，若關(guān)關(guān)系QR，則關(guān)系系Q就稱(chēng)為初等知識(shí)識(shí)(elementaryknowledge)，相應(yīng)的的等價(jià)類(lèi)類(lèi)就稱(chēng)為為初等概念念(elementaryconcept)。3/1/202024高級(jí)人工工智能史史忠植植上近似、下近似似和邊界界區(qū)域定義5:X的下近近似：R*(X)=x:(xU) (xRX )X的上近近似：R*(X)=x:(xU) (xRX)X的邊界界區(qū)域：BNR(X)=R*(X)R*(X)若BNR(X)

21、 ，則集合X就是一一個(gè)粗糙糙概念。下近似似包含了了所有使使用知識(shí)識(shí)R可確確切分類(lèi)類(lèi)到X的的元素，上近似似則包含含了所有有那些可可能是屬屬于X的的元素。概念的的邊界區(qū)區(qū)域由不不能肯定定分類(lèi)到到這個(gè)概概念或其其補(bǔ)集中中的所有有元素組組成。POSR(X)=R*(X)稱(chēng)稱(chēng)為集合合X的R-正區(qū)域，NEGR(X)=UR*(X)稱(chēng)稱(chēng)為集合合X的R-反區(qū)域。3/1/202025高級(jí)人工工智能史史忠植植Lower& Upper Approximations (2)LowerApproximation:UpperApproximation:3/1/202026高級(jí)人工工智能史史忠植植新型的隸隸屬關(guān)系系傳統(tǒng)集合合論

22、中，一個(gè)元元素的隸隸屬函數(shù)數(shù)X(x)0,1。而而粗糙集集理論中中，X(x)0,1定義4設(shè)XU且xU,集合X的粗糙隸屬屬函數(shù)(roughmembershipfunction)定義為其中R是是不分明明關(guān)系，R(x)=xR=y:(yU)(yRx)=1當(dāng)且且僅當(dāng)xRX0當(dāng)且且僅當(dāng)xRX=0當(dāng)且且僅當(dāng)xRX=3/1/202027高級(jí)人工工智能史史忠植植隸屬關(guān)系系根據(jù)上面面的定義義，可以以得到以以下性質(zhì)質(zhì)(1）(x)=1當(dāng)且僅當(dāng)當(dāng)xRX；(2）(x)0當(dāng)且僅當(dāng)當(dāng)xRX；(3）(x)=0當(dāng)且僅當(dāng)當(dāng)xRX=。顯然有(x)0,1。我們們可以看看到，這這里的隸隸屬關(guān)系系是根據(jù)據(jù)已有的的分類(lèi)知知識(shí)客觀觀計(jì)算出出來(lái)的

23、，可以被被解釋為為一種條條件概率率，能夠夠從全域域上的個(gè)個(gè)體加以以計(jì)算，而不是是主觀給給定的。3/1/202028高級(jí)人工工智能史史忠植植集近似SetApproximationLetT =(U, A)andletandWecan approximateXusingonly theinformationcontainedinBbyconstructingtheB-lowerandB-upperapproximationsofX,denotedandrespectively,where3/1/202029高級(jí)人工工智能史史忠植植集近似SetApproximation(2)B-boundary re

24、gionofX,consistsofthoseobjects thatwecannot decisivelyclassifyintoXinB.B-outsideregionofX,consistsofthoseobjects thatcan be withcertainty classifiedasnot belongingtoX.A setissaid to beroughifitsboundaryregion is non-empty,otherwise thesetiscrisp. 3/1/202030高級(jí)人工工智能史史忠植植集近似實(shí)實(shí)例SetApproximationLetW= x |

25、Walk(x)= yes.Thedecisionclass,Walk,isroughsincetheboundaryregion is notempty.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/1/202031高級(jí)人工工智能史史忠植植集近似實(shí)實(shí)例SetApproximation (2)yesyes/nonox1,x6x3,x4x2, x5,x7AW3/1/202032高級(jí)人工工智能史史忠植植UsetU/RR :subsetofa

26、ttributesLower&集近似圖圖示ns3/1/202033高級(jí)人工工智能史史忠植植Lower& Upper Approximations(3)X1= u |Flu(u) =yes=u2, u3,u6,u7RX1= u2,u3=u2, u3,u6,u7,u8,u5X2= u |Flu(u) =no=u1, u4,u5,u8RX2=u1, u4= u1,u4, u5,u8,u7,u6Theindiscernibilityclasses definedbyR=Headache, Temp.areu1,u2,u3,u4,u5, u7,u6,u8.3/1/202034高級(jí)人工工智能史史忠植植Lo

27、wer& Upper Approximations(4)R=Headache, Temp.U/R= u1,u2,u3,u4,u5, u7,u6,u8X1= u |Flu(u) =yes= u2,u3,u6,u7X2= u |Flu(u) =no =u1,u4,u5,u8RX1=u2, u3=u2, u3,u6,u7,u8,u5RX2=u1, u4= u1,u4, u5,u8,u7,u6u1u4u3X1X2u5u7u2u6u83/1/202035高級(jí)人工工智能史史忠植植例1：設(shè)有一知知識(shí)庫(kù)K=U,p,q,r其中中U=x1,x2,x3,x4,x5,x6,x7,x8且U/p=x1,x4,x5,x2,

28、x8,x3,x6,x7U/q=x1,x3,x5,x6,x2,x4,x7,x8U/r=x1,x5,x6,x2,x7,x8,x3,x4則x1p=x1,x4,x5x1q= 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=x4x7=x4,x7P*X1=x1,x5x4x7=x1,x4,x5,x73/1/202036高級(jí)人工工智能史史忠植植近似度AccuracyofApproximationwhere|X|denotesthecardinalityofObviouslyIfXiscrispwith

29、 respecttoB.IfXisroughwith respecttoB.3/1/202037高級(jí)人工工智能史史忠植植近似性質(zhì)質(zhì)PropertiesofApproximationsimpliesand3/1/202038高級(jí)人工工智能史史忠植植近似性質(zhì)質(zhì)PropertiesofApproximations(2)where-XdenotesU -X.3/1/202039高級(jí)人工工智能史史忠植植三、知知識(shí)的約約簡(jiǎn)一般約簡(jiǎn)簡(jiǎn)定義6設(shè)R是等價(jià)關(guān)關(guān)系的一一個(gè)族集集，且設(shè)設(shè)RR。若IND(R)=IND(RR)，則稱(chēng)關(guān)關(guān)系R在族集R之中是可省的(dispensable)否則就就是不可省的。若族族集R中的每

30、個(gè)個(gè)關(guān)系R都是不可可省的則稱(chēng)族族集R是獨(dú)立的(independent)否則就就是依賴(lài)的或非獨(dú)立的。定義7若QP是獨(dú)立的的并且且IND(Q)=IND(P)則稱(chēng)Q是關(guān)系族族集P的一個(gè)約簡(jiǎn)(reduct)。在族集集P中所有不不可省的的關(guān)系的的集合稱(chēng)稱(chēng)為P的核(core)以CORE(P)來(lái)表示。顯然，族族集P有多個(gè)約約簡(jiǎn)（約約簡(jiǎn)的不不唯一性性）。定理1族集P的核等于于P的所有約約簡(jiǎn)的交交集。即即CORE(P)=RED(P)3/1/202040高級(jí)人工工智能史史忠植植例2：取前面的例1若P=p,q,r則則IND(P)=x1,x5,x2,x8,x3,x4,x6,x7IND(P-p)=x1,x5,x2,x7

31、,x8,x3,x4,x6IND(P)所以p是是不可省省的同同理可得得q、r是可省省的。這這樣由由p,q,r三個(gè)個(gè)等價(jià)關(guān)關(guān)系組成成的集合合和p,q、p,r定義了了相同的的不分明明關(guān)系。又IND(p,q)IND(p)IND(pq)IND(q)則則p,q和和p, r就是P的約簡(jiǎn)而且p是是P的核核也就就是說(shuō)p是絕對(duì)對(duì)不能省省的3/1/202041高級(jí)人工工智能史史忠植植相對(duì)約簡(jiǎn)簡(jiǎn)定義8設(shè)P和Q是全域U上的等價(jià)價(jià)關(guān)系的的族集，所謂族族集Q的P-正區(qū)域(P-positiveregionofQ)，記作POSP(Q)=P*(X)族集Q的P-正區(qū)區(qū)域是全域U的所有有那些使使用分類(lèi)類(lèi)U/P所表達(dá)的的知識(shí)，能夠正正

32、確地分分類(lèi)于U/Q的等價(jià)類(lèi)類(lèi)之中的的對(duì)象的的集合。定義9設(shè)P和Q是全域U上的等價(jià)價(jià)關(guān)系的的族集，RP。若POSIND(P)(IND(Q)=POSIND(P-R)(IND(Q)則則稱(chēng)關(guān)系系R在族族集P中是Q-可省省的否則稱(chēng)稱(chēng)為Q-不可可省的如果在在族集P中的每個(gè)個(gè)關(guān)系R都是Q-不可省省的則則稱(chēng)P關(guān)于Q是獨(dú)立的否則就就稱(chēng)為是是依賴(lài)的。3/1/202042高級(jí)人工工智能史史忠植植相對(duì)約簡(jiǎn)簡(jiǎn)定義10 SP稱(chēng)為P的Q-約簡(jiǎn)簡(jiǎn)(Q-reduct)當(dāng)當(dāng)且僅當(dāng)當(dāng)S是P的Q-獨(dú)立的的子族集集且POSS(Q)=POSP(Q)；族集集P中的所有有Q-不可省省的初等等關(guān)系的的集合稱(chēng)為族族集P的Q-核(Q-core)記

33、作COREQ(P) 。下面的定定理是定理1的拓廣。定理2族集P的Q-核等于于族集P的所有Q-約簡(jiǎn)的的交集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集集P的所有Q-約簡(jiǎn)的的族集。3/1/202043高級(jí)人工工智能史史忠植植知識(shí)的依依賴(lài)性知識(shí)的依依賴(lài)性可可形式定定義如下下：定義11設(shè)K=(U,R)是一個(gè)個(gè)近似空空間，P,QR。1)知知識(shí)Q依賴(lài)于于知識(shí)P或知識(shí)P可推導(dǎo)導(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)當(dāng)IND(P)=IND(Q)；3)知知識(shí)P和知識(shí)

34、Q是獨(dú)立的，當(dāng)且僅僅當(dāng)PQ且QP均不成立立，記作作PQ。3/1/202044高級(jí)人工工智能史史忠植植知識(shí)的依依賴(lài)性依賴(lài)性也也可以是是部分成成立的也就是是從知識(shí)識(shí)P能推導(dǎo)出出知識(shí)Q的一部分分知識(shí)，或者說(shuō)說(shuō)知識(shí)Q只有一部部分依賴(lài)賴(lài)于知識(shí)識(shí)P的。部分分依賴(lài)性性（部分分可推導(dǎo)導(dǎo)性）可可以由知知識(shí)的正正區(qū)域來(lái)來(lái)定義?，F(xiàn)在我我們形式式地定義義部分依依賴(lài)性。定義12設(shè)K=(U,R)是一個(gè)個(gè)知識(shí)庫(kù)庫(kù)P,QR我們稱(chēng)稱(chēng)知識(shí)Q以以依賴(lài)度度k(0k1)依賴(lài)于知知識(shí)P記作PkQ當(dāng)且僅僅當(dāng)k=P(Q)=card(POSP(Q)/card(U)(6.8)(1)若k=1則則稱(chēng)知識(shí)識(shí)Q完全依依賴(lài)于知識(shí)P，P1Q也記成PQ；(2

35、)若0k1則稱(chēng)稱(chēng)知識(shí)Q部分依依賴(lài)于知識(shí)P；(3)若k=0則則稱(chēng)知識(shí)識(shí)Q完全獨(dú)獨(dú)立于與知識(shí)P。3/1/202045高級(jí)人工工智能史史忠植植四、決決策表的的約簡(jiǎn)決策表決策表是是一類(lèi)特特殊而重重要的知知識(shí)表達(dá)達(dá)系統(tǒng)，它指當(dāng)當(dāng)滿足某某些條件件時(shí)，決決策（行行為）應(yīng)應(yīng)當(dāng)怎樣樣進(jìn)行。多數(shù)決決策問(wèn)題題都可以以用決策策表形式式來(lái)表示示，這一一工具在在決策應(yīng)應(yīng)用中起起著重要要的作用用。決策表可可以定義義如下：S=(U,A)為一信信息系統(tǒng)統(tǒng)，且C,DA是兩個(gè)屬屬性子集集，分別別稱(chēng)為條條件屬性性和決策策屬性，且CD=A，CD=，則則該信息息系統(tǒng)稱(chēng)稱(chēng)為決策表，記作T=(U,A,C,D)或簡(jiǎn)稱(chēng)稱(chēng)CD決策表。關(guān)系IND(

36、C)和關(guān)系系IND(D)的等價(jià)價(jià)類(lèi)分別別稱(chēng)為條條件類(lèi)和和決策類(lèi)類(lèi)。3/1/202046高級(jí)人工工智能史史忠植植身高性別視力錄取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1一一決策表表身高、性性別、視視力為條條件屬性性，錄取取為決策策屬性3/1/202047高級(jí)人工工智能史史忠植植決策規(guī)則則決策表中中的每一一行對(duì)應(yīng)應(yīng)諸如形式的決決策規(guī)則則，和分別稱(chēng)為為決策規(guī)規(guī)則的前前驅(qū)和后后繼。當(dāng)決策表表S中決決策規(guī)則則為真時(shí)，我們說(shuō)說(shuō)該決策策規(guī)則是是S中一一致的，否則說(shuō)說(shuō)該決策策規(guī)則是是S中不不一致的的。若決決策規(guī)則則是S中中一致的的，相同同的前驅(qū)驅(qū)必導(dǎo)致致相同的的后繼；但

37、同一一種后繼繼不一定定必需是是同一前前驅(qū)產(chǎn)生生的。 如表1第第一行對(duì)對(duì)應(yīng)決策策規(guī)則：身高(高高)性別(男男)視力(差差) 錄取取(否) 3/1/202048高級(jí)人工工智能史史忠植植決策表的的一致性性命題1當(dāng)且僅當(dāng)當(dāng)CD，決策表表T=(U,A,C,D)是一致的的。由命題1，很容易易通過(guò)計(jì)計(jì)算條件件屬性和和決策屬屬性間的的依賴(lài)程程度來(lái)檢檢查一致致性。當(dāng)當(dāng)依賴(lài)程程度等于于1時(shí)，我們們說(shuō)決策策表是一一致的，否則不不一致。3/1/202049高級(jí)人工工智能史史忠植植決策表的的分解命題2每個(gè)決策策表T=(U,A,C,D)都可以唯唯一分解解為兩個(gè)個(gè)決策表表T1=(U1,A,C,D)和T2=(U2,A,C,D

38、)，這樣使使得表T1中C1D和T2中C0D。這里U1=POSC(D)，U2=BNC(X)，XU|IND(D)。由命題2可見(jiàn)，假設(shè)我我們已計(jì)計(jì)算出條條件屬性性的依賴(lài)賴(lài)度，若若表的結(jié)結(jié)果不一一致，即即依賴(lài)度度小于1，則由由命題2可以將將表分解解成兩個(gè)個(gè)子表：其中一一個(gè)表完完全不一一致，依依賴(lài)度為為0；另另一個(gè)表表則完全全一致，依賴(lài)度度為1。當(dāng)然，只有依依賴(lài)度大大于0且且不等于于1時(shí)，這一分分解才能能進(jìn)行。3/1/202050高級(jí)人工工智能史史忠植植表2不不一一致決策策表a、b、c為條條件屬性性，d、e為決決策屬性性1、5產(chǎn)產(chǎn)生不一一致Ua b c d e123456781 0 2 2 00 1 1

39、 1 22 0 0 1 11 1 0 2 21 0 2 0 12 2 0 1 12 1 1 1 20 1 1 0 13/1/202051高級(jí)人工工智能史史忠植植表3完完全一致致的決策策表Ua b c d e34672 0 0 1 11 1 0 2 22 2 0 1 12 1 1 1 2表4完完全不不一致的的決策表表Ua b c d e12581 0 2 2 00 1 1 1 21 0 2 0 10 1 1 0 13/1/202052高級(jí)人工工智能史史忠植植一致決策策表的約約簡(jiǎn)在我們制制定決策策時(shí)是否否需要全全部的條條件屬性性，能否否進(jìn)行決決策表的的約簡(jiǎn)。約簡(jiǎn)后后的決策策表具有有與約簡(jiǎn)簡(jiǎn)前的決決

40、策表相相同的功功能，但但是約簡(jiǎn)簡(jiǎn)后的決決策表具具有更少少的條件件屬性。一致決策策表的約約簡(jiǎn)步驟驟如下：(1)對(duì)決策表表進(jìn)行條條件屬性性的約簡(jiǎn)簡(jiǎn)，即從從決策表表中消去去某一列列；(主主要研究究點(diǎn))(2)消去重復(fù)復(fù)的行；(3)消消去每每一決策策規(guī)則中中屬性的的冗余值值。 3/1/202053高級(jí)人工工智能史史忠植植條件屬性性的約簡(jiǎn)簡(jiǎn)A.Skowron提提出了差差別矩陣陣，使核核與約簡(jiǎn)簡(jiǎn)等概念念的計(jì)算算較為簡(jiǎn)簡(jiǎn)單，主主要思想想：設(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。知

41、識(shí)表達(dá)達(dá)系統(tǒng)S的差別矩矩陣M(S)=cijnn，其中矩矩陣項(xiàng)定定義如下下：cij=aA：a(xi)a(xj)，i,j=1,2,n因此cij是個(gè)體xi與xj有區(qū)別的的所有屬屬性的集集合3/1/202054高級(jí)人工工智能史史忠植植差別矩陣陣對(duì)應(yīng)的的核與約約簡(jiǎn)核就可以以定義為為差別矩矩陣中所所有只有有一個(gè)元元素的矩矩陣項(xiàng)的的集合，即CORE(A)=aA：cij=(a)，對(duì)一一些i,j相對(duì)于集集合包含含關(guān)系運(yùn)運(yùn)算而言言，若屬屬性集合合BA是滿足下下列條件件Bcij，對(duì)于M(S)中的任一一非空項(xiàng)項(xiàng)cij的一個(gè)最最小屬性性子集，則稱(chēng)屬屬性集合合BA是A的的一個(gè)約約簡(jiǎn)。換言之，約簡(jiǎn)是是這樣的的最小屬屬性子集

42、集，它能能夠區(qū)分分用整個(gè)個(gè)屬性集集合A可可區(qū)分的的所有對(duì)對(duì)象。3/1/202055高級(jí)人工工智能史史忠植植Skowron的約簡(jiǎn)簡(jiǎn)方法對(duì)于每一一個(gè)差別別矩陣M(S)對(duì)應(yīng)唯一一的差別別函數(shù)fM(S)DiscernibilityFunction，它的的定義如如下：信息系統(tǒng)統(tǒng)S的差別函函數(shù)fM(S)是一個(gè)有有m-元變量a1, am(aiA，i=1,m)的布爾函函數(shù)，它它是cij的合取，cij是矩陣項(xiàng)項(xiàng)cij中的各元元素的析析取，1j0，C(X, Y)=0當(dāng)card(x)=0。C(X, Y)表示把把集合X歸類(lèi)于于集合Y的誤分分類(lèi)度，即有C(X, Y)100%的元素素歸類(lèi)錯(cuò)錯(cuò)誤。顯顯然，C(X, Y)=0時(shí)時(shí)有XY。如此此，可事事先給定定一錯(cuò)誤誤分類(lèi)率率(00.5)，基基于上述述定義，我們有有XY，當(dāng)且且僅當(dāng)C(X, Y)。3/1/202065高級(jí)人工工智能史史忠植植可變精度度粗糙集集模型在此基礎(chǔ)礎(chǔ)上，設(shè)設(shè)U為論域且且R為U上的等價(jià)價(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稱(chēng)為集合合X的-正區(qū)域，集合X的-上近似為RX=Xi(C(Xi, X)1, i=1,2, k)，這樣，-邊界區(qū)域域就定義為為：BNRX=Xi(C(Xi, X)1)；-負(fù)