第九章知識(shí)發(fā)現(xiàn)粗糙集

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

12/10/20223高級(jí)人工智能史忠植一、概述現(xiàn)實(shí)生活中有許多含糊現(xiàn)象并不能簡(jiǎn)單地模糊集1965年，Zadeh提出了模糊集，不少理論計(jì)算機(jī)科學(xué)家和邏輯學(xué)家試圖通過(guò)這一理論解決G.Frege的含糊概念，但模糊集理論采用隸屬度函數(shù)來(lái)處理模糊性，而基本的隸屬度是憑經(jīng)驗(yàn)或者由領(lǐng)域?qū)＜医o出，所以具有相當(dāng)?shù)闹饔^性。12/10/20224高級(jí)人工智能史忠植模糊集1965年，Zadeh提出了模糊集，不少理粗糙集的提出20世紀(jì)80年代初，波蘭的Pawlak針對(duì)G.Frege的邊界線區(qū)域思想提出了粗糙集（RoughSet）﹐他把那些無(wú)法確認(rèn)的個(gè)體都?xì)w屬于邊界線區(qū)域，而這種邊界線區(qū)域被定義為上近似集和下近似集之差集。由于它有確定的數(shù)學(xué)公式描述，完全由數(shù)據(jù)決定，，所以更有客觀性。12/10/20225高級(jí)人工智能史忠植粗糙集的提出20世紀(jì)80年代初，波蘭的Pawla粗糙集的研究粗糙集理論的主要優(yōu)勢(shì)之一是它不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息。自提出以來(lái)，許多計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家對(duì)粗糙集理論及其應(yīng)用進(jìn)行了堅(jiān)持不懈的研究，使之在理論上日趨完善，特別是由于20世紀(jì)80年代末和90年代初在知識(shí)發(fā)現(xiàn)等領(lǐng)域得到了成功的應(yīng)用而越來(lái)越受到國(guó)際上的廣泛關(guān)注。12/10/20226高級(jí)人工智能史忠植粗糙集的研究粗糙集理論的主要優(yōu)勢(shì)之一是它不需要任粗糙集的研究1991年波蘭Pawlak教授的第一本關(guān)于粗糙集的專著《RoughSets：TheoreticalAspectsofReasoningaboutData》和1992年R.Slowinski主編的關(guān)于粗糙集應(yīng)用及其與相關(guān)方法比較研究的論文集的出版，推動(dòng)了國(guó)際上對(duì)粗糙集理論與應(yīng)用的深入研究。1992年在波蘭Kiekrz召開(kāi)了第1屆國(guó)際粗糙集討論會(huì)。從此每年召開(kāi)一次與粗糙集理論為主題的國(guó)際研討會(huì)。12/10/20227高級(jí)人工智能史忠植粗糙集的研究1991年波蘭Pawlak教授的第一研究現(xiàn)狀分析史忠植.知識(shí)發(fā)現(xiàn).北京:清華大學(xué)出版社,2002劉清.RoughSet及Rough推理.北京:科學(xué)出版社,2001張文修等.RoughSet理論與方法.北京:科學(xué)出版社,2001王國(guó)胤,RoughSet理論與知識(shí)獲取.西安:西安交通大學(xué)出版社,2001曾黃麟.粗集理論及其應(yīng)用(修訂版).重慶:重慶大學(xué)出版社,1998

12/10/20228高級(jí)人工智能史忠植研究現(xiàn)狀分析史忠植.知識(shí)發(fā)現(xiàn).北京:清華大學(xué)出版社,研究現(xiàn)狀分析2001年5月在重慶召開(kāi)了“第1屆中國(guó)Rough集與軟計(jì)算學(xué)術(shù)研討會(huì)”，邀請(qǐng)了創(chuàng)始人Z.Pawlak教授做大會(huì)報(bào)告；2002年10月在蘇州第2屆2003年5月在重慶第3屆，同時(shí)舉辦“第9屆粗糙集、模糊集、數(shù)據(jù)挖掘和粒度-軟計(jì)算的國(guó)際會(huì)議”因非典推遲到10月中科院計(jì)算所、中科院自動(dòng)化所、北京工業(yè)大學(xué)、西安交通大學(xué)、重慶郵電學(xué)院、山西大學(xué)、合肥工業(yè)大學(xué)、上海大學(xué)、南昌大學(xué)

12/10/20229高級(jí)人工智能史忠植研究現(xiàn)狀分析2001年5月在重慶召開(kāi)了“第1屆中國(guó)Rough二、知識(shí)分類基本粗糙集理論認(rèn)為知識(shí)就是人類和其他物種所固有的分類能力。例如，在現(xiàn)實(shí)世界中關(guān)于環(huán)境的知識(shí)主要表明了生物根據(jù)其生存觀來(lái)對(duì)各種各樣的情形進(jìn)行分類區(qū)別的能力。每種生物根據(jù)其傳感器信號(hào)形成復(fù)雜的分類模式，就是這種生物的基本機(jī)制。分類是推理、學(xué)習(xí)與決策中的關(guān)鍵問(wèn)題。因此，粗糙集理論假定知識(shí)是一種對(duì)對(duì)象進(jìn)行分類的能力。這里的“對(duì)象”是指我們所能言及的任何事物，比如實(shí)物、狀態(tài)、抽象概念、過(guò)程和時(shí)刻等等。即知識(shí)必須與具體或抽象世界的特定部分相關(guān)的各種分類模式聯(lián)系在一起，這種特定部分稱之為所討論的全域或論域(universe)。對(duì)于全域及知識(shí)的特性并沒(méi)有任何特別假設(shè)。事實(shí)上，知識(shí)構(gòu)成了某一感興趣領(lǐng)域中各種分類模式的一個(gè)族集(family)，這個(gè)族集提供了關(guān)于現(xiàn)實(shí)的顯事實(shí)，以及能夠從這些顯事實(shí)中推導(dǎo)出隱事實(shí)的推理能力。12/10/202210高級(jí)人工智能史忠植二、知識(shí)分類基本粗糙集理論認(rèn)為知識(shí)就是人類和其他物二、知識(shí)分類為數(shù)學(xué)處理方便起見(jiàn)，在下面的定義中用等價(jià)關(guān)系來(lái)代替分類。一個(gè)近似空間(approximatespace)（或知識(shí)庫(kù)）定義為一個(gè)關(guān)系系統(tǒng)（或二元組）K=(U,R)

其中U（為空集）是一個(gè)被稱為全域或論域(universe)的所有要討論的個(gè)體的集合，R是U上等價(jià)關(guān)系的一個(gè)族集。

12/10/202211高級(jí)人工智能史忠植二、知識(shí)分類為數(shù)學(xué)處理方便起見(jiàn)，在下面的定義中用等價(jià)關(guān)二、知識(shí)分類

設(shè)PR，且P，P中所有等價(jià)關(guān)系的交集稱為P上的一種難區(qū)分關(guān)系(indiscernbilityrelation)（或稱難區(qū)分關(guān)系），記作IND(P)，即[x]IND(p)=I[x]R

RP

注意，IND(P)也是等價(jià)關(guān)系且是唯一的。12/10/202212高級(jí)人工智能史忠植二、知識(shí)分類設(shè)PR，且P，P中所有等價(jià)關(guān)系的二、知識(shí)分類

給定近似空間K=(U,R)，子集XU稱為U上的一個(gè)概念(concept)，形式上，空集也視為一個(gè)概念；非空子族集PR所產(chǎn)生的不分明關(guān)系IND(P)的所有等價(jià)類關(guān)系的集合即U/IND(P)，稱為基本知識(shí)(basicknowledge)，相應(yīng)的等價(jià)類稱為基本概念(basicconcept)；特別地，若關(guān)系QR，則關(guān)系Q就稱為初等知識(shí)(elementaryknowledge)，相應(yīng)的等價(jià)類就稱為初等概念(elementaryconcept)。一般用大寫(xiě)字母P,Q,R等表示一個(gè)關(guān)系，用大寫(xiě)黑體字母P,Q,R等表示關(guān)系的族集；[x]R或R(x)表示關(guān)系R中包含元素xU的概念或等價(jià)類。為了簡(jiǎn)便起見(jiàn)，有時(shí)用P代替IND(P)。根據(jù)上述定義可知，概念即對(duì)象的集合，概念的族集（分類）就是U上的知識(shí)，U上分類的族集可以認(rèn)為是U上的一個(gè)知識(shí)庫(kù)，或說(shuō)知識(shí)庫(kù)即是分類方法的集合。12/10/202213高級(jí)人工智能史忠植二、知識(shí)分類給定近似空間K=(U,R)，子集X二、知識(shí)分類

粗糙集理論與傳統(tǒng)的集合理論有著相似之處，但是它們的出發(fā)點(diǎn)完全不同。傳統(tǒng)集合論認(rèn)為，一個(gè)集合完全是由其元素所決定，一個(gè)元素要么屬于這個(gè)集合，要么不屬于這個(gè)集合，即它的隸屬函數(shù)X(x){0,1}。模糊集合對(duì)此做了拓廣，它給成員賦予一個(gè)隸屬度，即X(x)[0,1]，使得模糊集合能夠處理一定的模糊和不確定數(shù)據(jù)，但是其模糊隸屬度的確定往往具有人為因素，這給其應(yīng)用帶來(lái)了一定的不便。而且，傳統(tǒng)集合論和模糊集合論都是把隸屬關(guān)系作為原始概念來(lái)處理，集合的并和交就建立在其元素的隸屬度max和min操作上，因此其隸屬度必須事先給定（傳統(tǒng)集合默認(rèn)隸屬度為1或0）。在粗糙集中，隸屬關(guān)系不再是一個(gè)原始概念，因此無(wú)需人為給元素指定一個(gè)隸屬度，從而避免了主觀因素的影響。12/10/202214高級(jí)人工智能史忠植二、知識(shí)分類粗糙集理論與傳統(tǒng)的集合理論有著相似之處InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthatforeveryiscalledthevaluesetofa.

AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-4912/10/202215高級(jí)人工智能史忠植InformationSystems/TablesISiDecisionSystems/TablesDS:isthedecisionattribute

(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.

AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/10/202216高級(jí)人工智能史忠植DecisionSystems/TablesDS:IssuesintheDecisionTableThesameorindiscernibleobjectsmayberepresentedseveraltimes.Someoftheattributesmaybesuperfluous.12/10/202217高級(jí)人工智能史忠植IssuesintheDecisionTableTh難區(qū)分性IndiscernibilityTheequivalencerelationAbinaryrelationwhichisreflexive(xRxforanyobjectx),symmetric(ifxRythenyRx),andtransitive(ifxRyandyRzthenxRz).TheequivalenceclassofanelementconsistsofallobjectssuchthatxRy.12/10/202218高級(jí)人工智能史忠植難區(qū)分性IndiscernibilityTheequiva難區(qū)分性Indiscernibility(2)LetIS=(U,A)beaninformationsystem,thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandx’areindiscerniblefromeachotherbyattributesfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby12/10/202219高級(jí)人工智能史忠植難區(qū)分性Indiscernibility(2)LetIS難區(qū)分性實(shí)例IndiscernibilityThenon-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-49no12/10/202220高級(jí)人工智能史忠植難區(qū)分性實(shí)例IndiscernibilityThenon概念的邊界

知識(shí)的粒度性是造成使用已有知識(shí)不能精確地表示某些概念的原因。這就產(chǎn)生了所謂的關(guān)于不精確的“邊界”思想。著名哲學(xué)家Frege認(rèn)為“概念必須有明確的邊界。沒(méi)有明確邊界的概念，將對(duì)應(yīng)于一個(gè)在周圍沒(méi)有明確界線的區(qū)域”。粗糙集理論中的模糊性就是一種基于邊界的概念，即一個(gè)不精確的概念具有模糊的不可被明確劃分的邊界。為刻畫(huà)模糊性，每個(gè)不精確概念由一對(duì)稱為上近似與下近似的精確概念來(lái)表示，它們可用隸屬函數(shù)定義12/10/202221高級(jí)人工智能史忠植概念的邊界知識(shí)的粒度性是造成使用已有知識(shí)不能精確地表粗糙集的基本定義知識(shí)的分類觀點(diǎn) 粗糙集理論假定知識(shí)是一種對(duì)對(duì)象進(jìn)行分類的能力。而知識(shí)必須與具體或抽象世界的特定部分相關(guān)的各種分類模式聯(lián)系在一起，這種特定部分稱之為所討論的全域或論域(universe)。

為數(shù)學(xué)處理方便起見(jiàn)，在下面的定義中用等價(jià)關(guān)系來(lái)代替分類。12/10/202222高級(jí)人工智能史忠植粗糙集的基本定義知識(shí)的分類觀點(diǎn)12/8/202222高級(jí)人工粗糙集的基本定義

定義1一個(gè)近似空間(approximatespace)(或知識(shí)庫(kù))定義為一個(gè)關(guān)系系統(tǒng)(或二元組)K=(U,R)， 其中U(為空集)是一個(gè)被稱為全域或論域(universe)的所有要討論的個(gè)體的集合，R是U上等價(jià)關(guān)系的一個(gè)族集。 定義2設(shè)PR，且P，P中所有等價(jià)關(guān)系的交集稱為P上的一種不分明關(guān)系(indiscernbilityrelation)（或稱不可區(qū)分關(guān)系），記作IND(P)12/10/202223高級(jí)人工智能史忠植粗糙集的基本定義 定義1一個(gè)近似空間(approximat粗糙集的基本定義定義3給定近似空間K=(U,R)，子集XU稱為U上的一個(gè)概念(concept)，形式上，空集也視為一個(gè)概念；非空子族集PR所產(chǎn)生的不分明關(guān)系IND(P)的所有等價(jià)類關(guān)系的集合即U/IND(P)，稱為基本知識(shí)(basicknowledge)，相應(yīng)的等價(jià)類稱為基本概念(basicconcept)；特別地，若關(guān)系QR，則關(guān)系Q就稱為初等知識(shí)(elementaryknowledge)，相應(yīng)的等價(jià)類就稱為初等概念(elementaryconcept)。12/10/202224高級(jí)人工智能史忠植粗糙集的基本定義定義3給定近似空間K=(U,R上近似、下近似和邊界區(qū)域 定義5: X的下近似：R*(X)={x:(xU)([x]RX)} X的上近似：R*(X)={x:(xU)([x]RX)} X的邊界區(qū)域：BNR(X)=R*(X)–R*(X) 若BNR(X)，則集合X就是一個(gè)粗糙概念。下近似包含了所有使用知識(shí)R可確切分類到X的元素，上近似則包含了所有那些可能是屬于X的元素。概念的邊界區(qū)域由不能肯定分類到這個(gè)概念或其補(bǔ)集中的所有元素組成。POSR(X)=R*(X)稱為集合X的R-正區(qū)域，NEGR(X)=U–R*(X)稱為集合X的R-反區(qū)域。12/10/202225高級(jí)人工智能史忠植上近似、下近似和邊界區(qū)域 定義5:12/8/202225高級(jí)Lower&UpperApproximations(2)

LowerApproximation:UpperApproximation:12/10/202226高級(jí)人工智能史忠植Lower&UpperApproximations(新型的隸屬關(guān)系傳統(tǒng)集合論中，一個(gè)元素的隸屬函數(shù)X(x){0,1}。而粗糙集理論中，X(x)[0,1]定義4設(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=

12/10/202227高級(jí)人工智能史忠植新型的隸屬關(guān)系傳統(tǒng)集合論中，一個(gè)元素的隸屬函數(shù)X(x)隸屬關(guān)系根據(jù)上面的定義，可以得到以下性質(zhì)(1）(x)=1當(dāng)且僅當(dāng)[x]RX；(2）(x)>0當(dāng)且僅當(dāng)[x]RX；(3）(x)=0當(dāng)且僅當(dāng)[x]RX=。顯然有(x)[0,1]。我們可以看到，這里的隸屬關(guān)系是根據(jù)已有的分類知識(shí)客觀計(jì)算出來(lái)的，可以被解釋為一種條件概率，能夠從全域上的個(gè)體加以計(jì)算，而不是主觀給定的。12/10/202228高級(jí)人工智能史忠植隸屬關(guān)系根據(jù)上面的定義，可以得到以下性質(zhì)12/8/20222集近似SetApproximationLetT=(U,A)andletandWecanapproximateXusingonlytheinformationcontainedinBbyconstructingtheB-lowerandB-upperapproximationsofX,denotedandrespectively,where12/10/202229高級(jí)人工智能史忠植集近似SetApproximationLetT=(U集近似SetApproximation(2)B-boundaryregionofX,consistsofthoseobjectsthatwecannotdecisivelyclassifyintoXinB.

B-outsideregionofX,consistsofthoseobjectsthatcanbewithcertaintyclassifiedasnotbelongingtoX.Asetissaidtoberough

ifitsboundaryregionisnon-empty,otherwisethesetiscrisp.

12/10/202230高級(jí)人工智能史忠植集近似SetApproximation(2)B-boun集近似實(shí)例SetApproximationLetW={x|Walk(x)=yes}.Thedecisionclass,Walk,isroughsincetheboundaryregionisnotempty.

AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/10/202231高級(jí)人工智能史忠植集近似實(shí)例SetApproximationLetW=集近似實(shí)例

SetApproximation(2)yesyes/nono{{x1},{x6}}{{x3,x4}}{{x2},{x5,x7}}AW12/10/202232高級(jí)人工智能史忠植集近似實(shí)例

SetApproximation(2)yUsetＸU/RR:subsetofattributesLower&集近似圖示ns12/10/202233高級(jí)人工智能史忠植UsetＸU/RLower&集近似圖示ns12/8/20Lower&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}.12/10/202234高級(jí)人工智能史忠植Lower&UpperApproximationsXLower&UpperApproximations(4)R={Headache,Temp.}U/R={{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}}X1={u|Flu(u)=yes}={u2,u3,u6,u7}X2={u|Flu(u)=no}={u1,u4,u5,u8}RX1={u2,u3}

={u2,u3,u6,u7,u8,u5}RX2={u1,u4}={u1,u4,u5,u8,u7,u6}u1u4u3X1X2u5u7u2u6u812/10/202235高級(jí)人工智能史忠植Lower&UpperApproximations(例1：設(shè)有一知識(shí)庫(kù)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} P*X1={x1,x5}∪{x4}∪{x7}={x1,x4,x5,x7}12/10/202236高級(jí)人工智能史忠植例1：12/8/202236高級(jí)人工智能史忠植近似度

AccuracyofApproximation

where|X|denotesthecardinalityofObviouslyIfXiscrispwithrespecttoB.IfXisroughwithrespecttoB.12/10/202237高級(jí)人工智能史忠植近似度

AccuracyofApproximation1近似性質(zhì)PropertiesofApproximationsimpliesand12/10/202238高級(jí)人工智能史忠植近似性質(zhì)PropertiesofApproximatio近似性質(zhì)PropertiesofApproximations(2)where-XdenotesU-X.12/10/202239高級(jí)人工智能史忠植近似性質(zhì)PropertiesofApproximatio三、知識(shí)的約簡(jiǎn)一般約簡(jiǎn)

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

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

顯然，族集P有多個(gè)約簡(jiǎn)（約簡(jiǎn)的不唯一性）。定理1族集P的核等于P的所有約簡(jiǎn)的交集。即 CORE(P)=∩RED(P)12/10/202240高級(jí)人工智能史忠植三、知識(shí)的約簡(jiǎn)一般約簡(jiǎn)12/8/202240高級(jí)人工智能

例2： 取前面的例1﹐若P={p,q,r}﹐則IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{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)系。 又IND({p,q})IND({p})﹐IND({p﹐q})IND({q})﹐則{p,q}和{p,r}就是P的約簡(jiǎn)﹐而且{p}是P的核﹐也就是說(shuō)p是絕對(duì)不能省的

12/10/202241高級(jí)人工智能史忠植 例2：12/8/202241高級(jí)人工智能史忠植相對(duì)約簡(jiǎn) 定義8設(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ì)象的集合。 定義9設(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ú)立的﹐否則就稱為是依賴的。12/10/202242高級(jí)人工智能史忠植相對(duì)約簡(jiǎn) 定義8設(shè)P和Q是全域U上的等價(jià)關(guān)系的族集，所謂族相對(duì)約簡(jiǎn) 定義10SP稱為P的Q-約簡(jiǎn)(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-約簡(jiǎn)的交集。即 COREQ(P)=REDQ(P) 其中REDQ(P)是族集P的所有Q-約簡(jiǎn)的族集。12/10/202243高級(jí)人工智能史忠植相對(duì)約簡(jiǎn) 定義10SP稱為P的Q-約簡(jiǎn)(Q-reduct知識(shí)的依賴性

知識(shí)的依賴性可形式定義如下：定義11設(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。12/10/202244高級(jí)人工智能史忠植知識(shí)的依賴性 知識(shí)的依賴性可形式定義如下：12/8/2022知識(shí)的依賴性 依賴性也可以是部分成立的﹐也就是從知識(shí)P能推導(dǎo)出知識(shí)Q的一部分知識(shí)，或者說(shuō)知識(shí)Q只有一部分依賴于知識(shí)P的。部分依賴性（部分可推導(dǎo)性）可以由知識(shí)的正區(qū)域來(lái)定義。現(xiàn)在我們形式地定義部分依賴性。定義12設(shè)K=(U,R)是一個(gè)知識(shí)庫(kù)﹐P,QR﹐我們稱知識(shí)Q以依賴度k(0k1)依賴于知識(shí)P﹐記作PkQ﹐當(dāng)且僅當(dāng)k=P(Q)=card(POSP(Q))/card(U)(6.8)(1)

若k=1﹐則稱知識(shí)Q完全依賴于知識(shí)P，P1Q也記成PQ；(2)

若0k1﹐則稱知識(shí)Q部分依賴于知識(shí)P；(3)

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

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

12/10/202247高級(jí)人工智能史忠植

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

如表1第一行對(duì)應(yīng)決策規(guī)則： 身高(高)性別(男)視力(差)錄取(否)

12/10/202248高級(jí)人工智能史忠植決策規(guī)則 決策表中的每一行對(duì)應(yīng)諸如形式的決策規(guī)則決策表的一致性

命題1 當(dāng)且僅當(dāng)

CD，決策表T=(U,A,C,D)是一致的。 由命題1，很容易通過(guò)計(jì)算條件屬性和決策屬性間的依賴程度來(lái)檢查一致性。當(dāng)依賴程度等于1時(shí)，我們說(shuō)決策表是一致的，否則不一致。12/10/202249高級(jí)人工智能史忠植決策表的一致性12/8/202249高級(jí)人工智能史忠決策表的分解命題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可見(jiàn)，假設(shè)我們已計(jì)算出條件屬性的依賴度，若表的結(jié)果不一致，即依賴度小于1，則由命題2可以將表分解成兩個(gè)子表：其中一個(gè)表完全不一致，依賴度為0；另一個(gè)表則完全一致，依賴度為1。當(dāng)然，只有依賴度大于0且不等于1時(shí)，這一分解才能進(jìn)行。12/10/202250高級(jí)人工智能史忠植決策表的分解命題212/8/202250高級(jí)人工智能表2不一致決策表a、b、c為條件屬性，d、e為決策屬性1、5產(chǎn)生不一致Uabcde12345678102200111220011110221020122011211120110112/10/202251高級(jí)人工智能史忠植表2不一致決策表Uabcd表3完全一致的決策表Uabcde346720011110222201121112表4完全不一致的決策表Uabcde12581022001112102010110112/10/202252高級(jí)人工智能史忠植表3完全一致的決策表Uabcde3一致決策表的約簡(jiǎn)

在我們制定決策時(shí)是否需要全部的條件屬性，能否進(jìn)行決策表的約簡(jiǎn)。約簡(jiǎn)后的決策表具有與約簡(jiǎn)前的決策表相同的功能，但是約簡(jiǎn)后的決策表具有更少的條件屬性。 一致決策表的約簡(jiǎn)步驟如下： (1)對(duì)決策表進(jìn)行條件屬性的約簡(jiǎn)，即從決策表中消去某一列；(主要研究點(diǎn)) (2)消去重復(fù)的行； (3)消去每一決策規(guī)則中屬性的冗余值。

12/10/202253高級(jí)人工智能史忠植一致決策表的約簡(jiǎn) 在我們制定決策時(shí)是否需要全部的條件屬性，能條件屬性的約簡(jiǎn) A.Skowron提出了差別矩陣，使核與約簡(jiǎn)等概念的計(jì)算較為簡(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。 知識(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ū)別的所有屬性的集合12/10/202254高級(jí)人工智能史忠植條件屬性的約簡(jiǎn) A.Skowron提出了差別矩陣，使核與約簡(jiǎn)差別矩陣對(duì)應(yīng)的核與約簡(jiǎn)

核就可以定義為差別矩陣中所有只有一個(gè)元素的矩陣項(xiàng)的集合，即

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

相對(duì)于集合包含關(guān)系運(yùn)算而言，若屬性集合BA是滿足下列條件

B∩cij≠，對(duì)于M(S)中的任一非空項(xiàng)cij≠ 的一個(gè)最小屬性子集，則稱屬性集合BA是A的一個(gè)約簡(jiǎn)。 換言之，約簡(jiǎn)是這樣的最小屬性子集，它能夠區(qū)分用整個(gè)屬性集合A可區(qū)分的所有對(duì)象。12/10/202255高級(jí)人工智能史忠植差別矩陣對(duì)應(yīng)的核與約簡(jiǎn) 核就可以定義為差別矩陣中所有只有一個(gè)Skowron的約簡(jiǎn)方法

對(duì)于每一個(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ù)與約簡(jiǎn)的對(duì)應(yīng)關(guān)系，A.Skowron提出了計(jì)算信息系統(tǒng)S的約簡(jiǎn)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è)約簡(jiǎn)12/10/202256高級(jí)人工智能史忠植Skowron的約簡(jiǎn)方法 對(duì)于每一個(gè)差別矩陣M(S)對(duì)應(yīng)唯一 為了對(duì)決策表進(jìn)行約簡(jiǎn)，可以采用差別矩陣的方法對(duì)條件屬性進(jìn)行約簡(jiǎn)，對(duì)決策屬性相同的個(gè)體不予比較。考慮下面的決策表5，條件屬性為a,b,c,d，決策屬性為eU/Aabcdeu110210u200121u320210u400222u511210表512/10/202257高級(jí)人工智能史忠植 為了對(duì)決策表進(jìn)行約簡(jiǎn)，可以采用差別矩陣的方法對(duì)條件屬性進(jìn)行表5對(duì)應(yīng)的差別矩陣uu1u2u3u4u5u1

u2a,c,d

u3

a,c,d

u4a,dca,d

u5

a,b,c,d

a,b,d

由下面的差別矩陣很容易得到核為{c}，差別函數(shù)fM(S)為c∧(a∨d)，即(a∧c)∨(c∧d)，得到兩個(gè)約簡(jiǎn){a,c}和{c,d}12/10/202258高級(jí)人工智能史忠植表5對(duì)應(yīng)的差別矩陣uu1u2u3u4u5u1

u2a表6根據(jù)得到的兩個(gè)約簡(jiǎn)，表5可以簡(jiǎn)化為表6和表7U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210表712/10/202259高級(jí)人工智能史忠植表6根據(jù)得到的兩個(gè)約簡(jiǎn)，表5可以簡(jiǎn)化為表6和表7U\Aace求最優(yōu)或次優(yōu)約簡(jiǎn)

所有約簡(jiǎn)的計(jì)算是NP-hard問(wèn)題，因此運(yùn)用啟發(fā)信息來(lái)簡(jiǎn)化計(jì)算以找出最優(yōu)或次優(yōu)約簡(jiǎn)是必要的。

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

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

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

對(duì)于粗糙集的邊界區(qū)域的刻畫(huà)過(guò)于簡(jiǎn)單； 3)粗糙集理論的方法在可用信息不完全的情況下將對(duì)象們歸類于某一具體的類，通常分類是確定的，但并未提供數(shù)理統(tǒng)計(jì)中所常用的在一個(gè)給定錯(cuò)誤率的條件下將盡可能多的對(duì)象進(jìn)行分類的方法，而實(shí)際中常常遇到這類問(wèn)題。12/10/202264高級(jí)人工智能史忠植五、粗糙集的擴(kuò)展模型 基本粗糙集理論的主要存在的問(wèn)題是：1可變精度粗糙集模型 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)。12/10/202265高級(jí)人工智能史忠植可變精度粗糙集模型 W.Ziarko提出了一種稱之為可變精度可變精度粗糙集模型 在此基礎(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–)。 以此類推，我們還可以定義-依賴、-約簡(jiǎn)等與傳統(tǒng)粗糙集模型相對(duì)應(yīng)的概念。12/10/202266高級(jí)人工智能史忠植可變精度粗糙集模型 在此基礎(chǔ)上，設(shè)U為論域且R為U上的等價(jià)關(guān)相似模型在數(shù)據(jù)中存在缺失的屬性值的時(shí)候（在數(shù)據(jù)庫(kù)中很普遍），不分明關(guān)系或等價(jià)關(guān)系無(wú)法處理這種情形。為擴(kuò)展粗糙集的能力，有許多作者提出了用相似關(guān)系來(lái)代替不分明關(guān)系作為粗糙集的基礎(chǔ)。在使用相似關(guān)系代替粗糙集的不分明關(guān)系后，最重要的變化就是相似類不再形成對(duì)集合的劃分了，它們之間是相互重疊的。類似于等價(jià)類，可以定義相似集，即所有和某各元素x在屬性集合B上相似的集合SIMb(x)。值得注意的是SIMb(x)中的元素不一定屬于同一決策類，因此還需要定義相似決策類，即相似集對(duì)應(yīng)的決策類集合。12/10/202267高級(jí)人工智能史忠植相似模型在數(shù)據(jù)中存在缺失的屬性值的時(shí)候（在數(shù)據(jù)庫(kù)基于粗糙集的非單調(diào)邏輯

自粗糙集理論提出以來(lái)，粗糙集理論的研究者都很重視它的邏輯研究，試圖通過(guò)粗糙集建立粗糙邏輯，也相應(yīng)地發(fā)表了一系列的粗糙邏輯方面的論文。12/10/202268高級(jí)人工智能史忠植基于粗糙集的非單調(diào)邏輯12/8/202268高級(jí)人工智能與其它數(shù)學(xué)工具的結(jié)合

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

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

12/10/202269高級(jí)人工智能史忠植與其它數(shù)學(xué)工具的結(jié)合12/8/202269高級(jí)人工智能六、粗糙集的實(shí)驗(yàn)系統(tǒng)

在過(guò)去幾年中，建立了不少基于粗糙集的KDD系統(tǒng)，其中最有代表性的有LERS、ROSE、KDD-R等。 1．LERS LERS(LearningfromexamplesbasedonRoughSet)系統(tǒng)是美國(guó)Kansas大學(xué)開(kāi)發(fā)的基于粗糙集的實(shí)例學(xué)習(xí)系統(tǒng)。它是用CommonLisp在VAX9000上實(shí)現(xiàn)的。LERS已經(jīng)為NASA的Johnson空間中心應(yīng)用了兩年。此外，LERS還被廣泛地用于環(huán)境保護(hù)、氣候研究和醫(yī)療研究

12/10/202270高級(jí)人工智能史忠植六、粗糙集的實(shí)驗(yàn)系統(tǒng) 在過(guò)去幾年中，建立了不少基于粗糙集的K六、粗糙集的實(shí)驗(yàn)系統(tǒng)

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

12/10/202271高級(jí)人工智能史忠植六、粗糙集的實(shí)驗(yàn)系統(tǒng) 2．ROSE12/8/202271高級(jí)12/10/202272高級(jí)人工智能史忠植12/8/202272高級(jí)人工智能史忠植第九章知識(shí)發(fā)現(xiàn)粗糙集

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

12/10/202275高級(jí)人工智能史忠植一、概述現(xiàn)實(shí)生活中有許多含糊現(xiàn)象并不能簡(jiǎn)單地模糊集1965年，Zadeh提出了模糊集，不少理論計(jì)算機(jī)科學(xué)家和邏輯學(xué)家試圖通過(guò)這一理論解決G.Frege的含糊概念，但模糊集理論采用隸屬度函數(shù)來(lái)處理模糊性，而基本的隸屬度是憑經(jīng)驗(yàn)或者由領(lǐng)域?qū)＜医o出，所以具有相當(dāng)?shù)闹饔^性。12/10/202276高級(jí)人工智能史忠植模糊集1965年，Zadeh提出了模糊集，不少理粗糙集的提出20世紀(jì)80年代初，波蘭的Pawlak針對(duì)G.Frege的邊界線區(qū)域思想提出了粗糙集（RoughSet）﹐他把那些無(wú)法確認(rèn)的個(gè)體都?xì)w屬于邊界線區(qū)域，而這種邊界線區(qū)域被定義為上近似集和下近似集之差集。由于它有確定的數(shù)學(xué)公式描述，完全由數(shù)據(jù)決定，，所以更有客觀性。12/10/202277高級(jí)人工智能史忠植粗糙集的提出20世紀(jì)80年代初，波蘭的Pawla粗糙集的研究粗糙集理論的主要優(yōu)勢(shì)之一是它不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息。自提出以來(lái)，許多計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家對(duì)粗糙集理論及其應(yīng)用進(jìn)行了堅(jiān)持不懈的研究，使之在理論上日趨完善，特別是由于20世紀(jì)80年代末和90年代初在知識(shí)發(fā)現(xiàn)等領(lǐng)域得到了成功的應(yīng)用而越來(lái)越受到國(guó)際上的廣泛關(guān)注。12/10/202278高級(jí)人工智能史忠植粗糙集的研究粗糙集理論的主要優(yōu)勢(shì)之一是它不需要任粗糙集的研究1991年波蘭Pawlak教授的第一本關(guān)于粗糙集的專著《RoughSets：TheoreticalAspectsofReasoningaboutData》和1992年R.Slowinski主編的關(guān)于粗糙集應(yīng)用及其與相關(guān)方法比較研究的論文集的出版，推動(dòng)了國(guó)際上對(duì)粗糙集理論與應(yīng)用的深入研究。1992年在波蘭Kiekrz召開(kāi)了第1屆國(guó)際粗糙集討論會(huì)。從此每年召開(kāi)一次與粗糙集理論為主題的國(guó)際研討會(huì)。12/10/202279高級(jí)人工智能史忠植粗糙集的研究1991年波蘭Pawlak教授的第一研究現(xiàn)狀分析史忠植.知識(shí)發(fā)現(xiàn).北京:清華大學(xué)出版社,2002劉清.RoughSet及Rough推理.北京:科學(xué)出版社,2001張文修等.RoughSet理論與方法.北京:科學(xué)出版社,2001王國(guó)胤,RoughSet理論與知識(shí)獲取.西安:西安交通大學(xué)出版社,2001曾黃麟.粗集理論及其應(yīng)用(修訂版).重慶:重慶大學(xué)出版社,1998

12/10/202280高級(jí)人工智能史忠植研究現(xiàn)狀分析史忠植.知識(shí)發(fā)現(xiàn).北京:清華大學(xué)出版社,研究現(xiàn)狀分析2001年5月在重慶召開(kāi)了“第1屆中國(guó)Rough集與軟計(jì)算學(xué)術(shù)研討會(huì)”，邀請(qǐng)了創(chuàng)始人Z.Pawlak教授做大會(huì)報(bào)告；2002年10月在蘇州第2屆2003年5月在重慶第3屆，同時(shí)舉辦“第9屆粗糙集、模糊集、數(shù)據(jù)挖掘和粒度-軟計(jì)算的國(guó)際會(huì)議”因非典推遲到10月中科院計(jì)算所、中科院自動(dòng)化所、北京工業(yè)大學(xué)、西安交通大學(xué)、重慶郵電學(xué)院、山西大學(xué)、合肥工業(yè)大學(xué)、上海大學(xué)、南昌大學(xué)

12/10/202281高級(jí)人工智能史忠植研究現(xiàn)狀分析2001年5月在重慶召開(kāi)了“第1屆中國(guó)Rough二、知識(shí)分類基本粗糙集理論認(rèn)為知識(shí)就是人類和其他物種所固有的分類能力。例如，在現(xiàn)實(shí)世界中關(guān)于環(huán)境的知識(shí)主要表明了生物根據(jù)其生存觀來(lái)對(duì)各種各樣的情形進(jìn)行分類區(qū)別的能力。每種生物根據(jù)其傳感器信號(hào)形成復(fù)雜的分類模式，就是這種生物的基本機(jī)制。分類是推理、學(xué)習(xí)與決策中的關(guān)鍵問(wèn)題。因此，粗糙集理論假定知識(shí)是一種對(duì)對(duì)象進(jìn)行分類的能力。這里的“對(duì)象”是指我們所能言及的任何事物，比如實(shí)物、狀態(tài)、抽象概念、過(guò)程和時(shí)刻等等。即知識(shí)必須與具體或抽象世界的特定部分相關(guān)的各種分類模式聯(lián)系在一起，這種特定部分稱之為所討論的全域或論域(universe)。對(duì)于全域及知識(shí)的特性并沒(méi)有任何特別假設(shè)。事實(shí)上，知識(shí)構(gòu)成了某一感興趣領(lǐng)域中各種分類模式的一個(gè)族集(family)，這個(gè)族集提供了關(guān)于現(xiàn)實(shí)的顯事實(shí)，以及能夠從這些顯事實(shí)中推導(dǎo)出隱事實(shí)的推理能力。12/10/202282高級(jí)人工智能史忠植二、知識(shí)分類基本粗糙集理論認(rèn)為知識(shí)就是人類和其他物二、知識(shí)分類為數(shù)學(xué)處理方便起見(jiàn)，在下面的定義中用等價(jià)關(guān)系來(lái)代替分類。一個(gè)近似空間(approximatespace)（或知識(shí)庫(kù)）定義為一個(gè)關(guān)系系統(tǒng)（或二元組）K=(U,R)

其中U（為空集）是一個(gè)被稱為全域或論域(universe)的所有要討論的個(gè)體的集合，R是U上等價(jià)關(guān)系的一個(gè)族集。

12/10/202283高級(jí)人工智能史忠植二、知識(shí)分類為數(shù)學(xué)處理方便起見(jiàn)，在下面的定義中用等價(jià)關(guān)二、知識(shí)分類

設(shè)PR，且P，P中所有等價(jià)關(guān)系的交集稱為P上的一種難區(qū)分關(guān)系(indiscernbilityrelation)（或稱難區(qū)分關(guān)系），記作IND(P)，即[x]IND(p)=I[x]R

RP

注意，IND(P)也是等價(jià)關(guān)系且是唯一的。12/10/202284高級(jí)人工智能史忠植二、知識(shí)分類設(shè)PR，且P，P中所有等價(jià)關(guān)系的二、知識(shí)分類

給定近似空間K=(U,R)，子集XU稱為U上的一個(gè)概念(concept)，形式上，空集也視為一個(gè)概念；非空子族集PR所產(chǎn)生的不分明關(guān)系IND(P)的所有等價(jià)類關(guān)系的集合即U/IND(P)，稱為基本知識(shí)(basicknowledge)，相應(yīng)的等價(jià)類稱為基本概念(basicconcept)；特別地，若關(guān)系QR，則關(guān)系Q就稱為初等知識(shí)(elementaryknowledge)，相應(yīng)的等價(jià)類就稱為初等概念(elementaryconcept)。一般用大寫(xiě)字母P,Q,R等表示一個(gè)關(guān)系，用大寫(xiě)黑體字母P,Q,R等表示關(guān)系的族集；[x]R或R(x)表示關(guān)系R中包含元素xU的概念或等價(jià)類。為了簡(jiǎn)便起見(jiàn)，有時(shí)用P代替IND(P)。根據(jù)上述定義可知，概念即對(duì)象的集合，概念的族集（分類）就是U上的知識(shí)，U上分類的族集可以認(rèn)為是U上的一個(gè)知識(shí)庫(kù)，或說(shuō)知識(shí)庫(kù)即是分類方法的集合。12/10/202285高級(jí)人工智能史忠植二、知識(shí)分類給定近似空間K=(U,R)，子集X二、知識(shí)分類

粗糙集理論與傳統(tǒng)的集合理論有著相似之處，但是它們的出發(fā)點(diǎn)完全不同。傳統(tǒng)集合論認(rèn)為，一個(gè)集合完全是由其元素所決定，一個(gè)元素要么屬于這個(gè)集合，要么不屬于這個(gè)集合，即它的隸屬函數(shù)X(x){0,1}。模糊集合對(duì)此做了拓廣，它給成員賦予一個(gè)隸屬度，即X(x)[0,1]，使得模糊集合能夠處理一定的模糊和不確定數(shù)據(jù)，但是其模糊隸屬度的確定往往具有人為因素，這給其應(yīng)用帶來(lái)了一定的不便。而且，傳統(tǒng)集合論和模糊集合論都是把隸屬關(guān)系作為原始概念來(lái)處理，集合的并和交就建立在其元素的隸屬度max和min操作上，因此其隸屬度必須事先給定（傳統(tǒng)集合默認(rèn)隸屬度為1或0）。在粗糙集中，隸屬關(guān)系不再是一個(gè)原始概念，因此無(wú)需人為給元素指定一個(gè)隸屬度，從而避免了主觀因素的影響。12/10/202286高級(jí)人工智能史忠植二、知識(shí)分類粗糙集理論與傳統(tǒng)的集合理論有著相似之處InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthatforeveryiscalledthevaluesetofa.

AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-4912/10/202287高級(jí)人工智能史忠植InformationSystems/TablesISiDecisionSystems/TablesDS:isthedecisionattribute

(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.

AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/10/202288高級(jí)人工智能史忠植DecisionSystems/TablesDS:IssuesintheDecisionTableThesameorindiscernibleobjectsmayberepresentedseveraltimes.Someoftheattributesmaybesuperfluous.12/10/202289高級(jí)人工智能史忠植IssuesintheDecisionTableTh難區(qū)分性IndiscernibilityTheequivalencerelationAbinaryrelati