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

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

史忠植中科院計(jì)算所7/24/20241高級(jí)人工智能史忠植內(nèi)容一、概述二、知識(shí)分類(lèi)三、知識(shí)的約簡(jiǎn)四、決策表的約簡(jiǎn)五、粗糙集的擴(kuò)展模型六、粗糙集的實(shí)驗(yàn)系統(tǒng)7/24/20242高級(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è)子集上分類(lèi)，也不能在該子集的補(bǔ)集上分類(lèi)。

7/24/20243高級(jí)人工智能史忠植模糊集1965年，Zadeh提出了模糊集，不少理論計(jì)算機(jī)科學(xué)家和邏輯學(xué)家試圖通過(guò)這一理論解決G.Frege的含糊概念，但模糊集理論采用隸屬度函數(shù)來(lái)處理模糊性，而基本的隸屬度是憑經(jīng)驗(yàn)或者由領(lǐng)域?qū)＜医o出，所以具有相當(dāng)?shù)闹饔^性。7/24/20244高級(jí)人工智能史忠植粗糙集的提出20世紀(jì)80年代初，波蘭的Pawlak針對(duì)G.Frege的邊界線區(qū)域思想提出了粗糙集（RoughSet）﹐他把那些無(wú)法確認(rèn)的個(gè)體都?xì)w屬于邊界線區(qū)域，而這種邊界線區(qū)域被定義為上近似集和下近似集之差集。由于它有確定的數(shù)學(xué)公式描述，完全由數(shù)據(jù)決定，，所以更有客觀性。7/24/20245高級(jí)人工智能史忠植粗糙集的研究粗糙集理論的主要優(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)注。7/24/20246高級(jí)人工智能史忠植粗糙集的研究1991年波蘭Pawlak教授的第一本關(guān)于粗糙集的專(zhuā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ì)。7/24/20247高級(jí)人工智能史忠植研究現(xiàn)狀分析史忠植.知識(shí)發(fā)現(xiàn).北京:清華大學(xué)出版社,2002劉清.RoughSet及Rough推理.北京:科學(xué)出版社,2001張文修等.RoughSet理論與方法.北京:科學(xué)出版社,2001王國(guó)胤,RoughSet理論與知識(shí)獲取.西安:西安交通大學(xué)出版社,2001曾黃麟.粗集理論及其應(yīng)用(修訂版).重慶:重慶大學(xué)出版社,1998

7/24/20248高級(jí)人工智能史忠植研究現(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é)

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

其中U

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

7/24/202411高級(jí)人工智能史忠植二、知識(shí)分類(lèi)

設(shè)P

R，且P

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

RP

注意，IND(P)也是等價(jià)關(guān)系且是唯一的。7/24/202412高級(jí)人工智能史忠植二、知識(shí)分類(lèi)

給定近似空間K=(U,R)，子集X

U稱(chēng)為U上的一個(gè)概念(concept)，形式上，空集也視為一個(gè)概念；非空子族集P

R所產(chǎn)生的不分明關(guān)系IND(P)的所有等價(jià)類(lèi)關(guān)系的集合即U/IND(P)，稱(chēng)為基本知識(shí)(basicknowledge)，相應(yīng)的等價(jià)類(lèi)稱(chēng)為基本概念(basicconcept)；特別地，若關(guān)系Q

R，則關(guān)系Q就稱(chēng)為初等知識(shí)(elementaryknowledge)，相應(yīng)的等價(jià)類(lèi)就稱(chēng)為初等概念(elementaryconcept)。一般用大寫(xiě)字母P,Q,R等表示一個(gè)關(guān)系，用大寫(xiě)黑體字母P,Q,R等表示關(guān)系的族集；[x]R或R(x)表示關(guān)系R中包含元素x

U的概念或等價(jià)類(lèi)。為了簡(jiǎn)便起見(jiàn)，有時(shí)用P代替IND(P)。根據(jù)上述定義可知，概念即對(duì)象的集合，概念的族集（分類(lèi)）就是U上的知識(shí)，U上分類(lèi)的族集可以認(rèn)為是U上的一個(gè)知識(shí)庫(kù)，或說(shuō)知識(shí)庫(kù)即是分類(lèi)方法的集合。7/24/202413高級(jí)人工智能史忠植二、知識(shí)分類(lèi)

粗糙集理論與傳統(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è)隸屬度，從而避免了主觀因素的影響。7/24/202414高級(jí)人工智能史忠植InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthatforeveryiscalledthevaluesetofa.

AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-497/24/202415高級(jí)人工智能史忠植DecisionSystems/TablesDS:isthedecisionattribute

(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.

AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no7/24/202416高級(jí)人工智能史忠植IssuesintheDecisionTableThesameorindiscernibleobjectsmayberepresentedseveraltimes.Someoftheattributesmaybesuperfluous.7/24/202417高級(jí)人工智能史忠植難區(qū)分性IndiscernibilityTheequivalencerelationAbinaryrelationwhichisreflexive(xRx

foranyobjectx),symmetric(ifxRythenyRx),andtransitive(ifxRyandyRz

thenxRz).TheequivalenceclassofanelementconsistsofallobjectssuchthatxRy.7/24/202418高級(jí)人工智能史忠植難區(qū)分性Indiscernibility(2)LetIS=(U,A)beaninformationsystem,thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandx’areindiscerniblefromeachotherbyattributesfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby7/24/202419高級(jí)人工智能史忠植難區(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-49no7/24/202420高級(jí)人工智能史忠植概念的邊界

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

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

定義1一個(gè)近似空間(approximatespace)(或知識(shí)庫(kù))定義為一個(gè)關(guān)系系統(tǒng)(或二元組)K=(U,R)，

其中U

(

為空集)是一個(gè)被稱(chēng)為全域或論域(universe)的所有要討論的個(gè)體的集合，R是U上等價(jià)關(guān)系的一個(gè)族集。 定義2設(shè)P

R，且P

，P中所有等價(jià)關(guān)系的交集稱(chēng)為P上的一種不分明關(guān)系(indiscernbilityrelation)（或稱(chēng)不可區(qū)分關(guān)系），記作IND(P)7/24/202423高級(jí)人工智能史忠植粗糙集的基本定義定義3給定近似空間K=(U,R)，子集X

U稱(chēng)為U上的一個(gè)概念(concept)，形式上，空集也視為一個(gè)概念；非空子族集P

R所產(chǎn)生的不分明關(guān)系IND(P)的所有等價(jià)類(lèi)關(guān)系的集合即U/IND(P)，稱(chēng)為基本知識(shí)(basicknowledge)，相應(yīng)的等價(jià)類(lèi)稱(chēng)為基本概念(basicconcept)；特別地，若關(guān)系Q

R，則關(guān)系Q就稱(chēng)為初等知識(shí)(elementaryknowledge)，相應(yīng)的等價(jià)類(lèi)就稱(chēng)為初等概念(elementaryconcept)。7/24/202424高級(jí)人工智能史忠植上近似、下近似和邊界區(qū)域 定義5:

X的下近似：R*(X)={x:(x

U)([x]R

X)} X的上近似：R*(X)={x:(x

U)([x]R

X

)} X的邊界區(qū)域：BNR(X)=R*(X)–R*(X)

若BNR(X)，則集合X就是一個(gè)粗糙概念。下近似包含了所有使用知識(shí)R可確切分類(lèi)到X的元素，上近似則包含了所有那些可能是屬于X的元素。概念的邊界區(qū)域由不能肯定分類(lèi)到這個(gè)概念或其補(bǔ)集中的所有元素組成。POSR(X)=R*(X)稱(chēng)為集合X的R-正區(qū)域，NEGR(X)=U–R*(X)稱(chēng)為集合X的R-反區(qū)域。7/24/202425高級(jí)人工智能史忠植Lower&UpperApproximations(2)

LowerApproximation:UpperApproximation:7/24/202426高級(jí)人工智能史忠植新型的隸屬關(guān)系傳統(tǒng)集合論中，一個(gè)元素的隸屬函數(shù)

X(x)

{0,1}。而粗糙集理論中，

X(x)

[0,1]

定義4設(shè)X

U且x

U,集合X的粗糙隸屬函數(shù)(roughmembershipfunction)

定義為

其中R是不分明關(guān)系，R(x)=[x]R={y:(y

U)

(yRx)}=1當(dāng)且僅當(dāng)[x]R

X>0當(dāng)且僅當(dāng)[x]R

X

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

X=

7/24/202427高級(jí)人工智能史忠植隸屬關(guān)系根據(jù)上面的定義，可以得到以下性質(zhì)(1）(x)=1當(dāng)且僅當(dāng)[x]R

X；(2）(x)>0當(dāng)且僅當(dāng)[x]R

X

；(3）(x)=0當(dāng)且僅當(dāng)[x]R

X=。顯然有(x)

[0,1]。我們可以看到，這里的隸屬關(guān)系是根據(jù)已有的分類(lèi)知識(shí)客觀計(jì)算出來(lái)的，可以被解釋為一種條件概率，能夠從全域上的個(gè)體加以計(jì)算，而不是主觀給定的。7/24/202428高級(jí)人工智能史忠植集近似SetApproximationLetT=(U,A)andletandWecanapproximateXusingonlytheinformationcontainedinBbyconstructingtheB-lowerandB-upperapproximationsofX,denotedandrespectively,where7/24/202429高級(jí)人工智能史忠植集近似SetApproximation(2)B-boundaryregionofX,consistsofthoseobjectsthatwecannotdecisivelyclassifyintoXinB.

B-outsideregionofX,consistsofthoseobjectsthatcanbewithcertaintyclassifiedasnotbelongingtoX.Asetissaidtoberough

ifitsboundaryregionisnon-empty,otherwisethesetiscrisp.

7/24/202430高級(jí)人工智能史忠植集近似實(shí)例SetApproximationLetW={x|Walk(x)=yes}.Thedecisionclass,Walk,isroughsincetheboundaryregionisnotempty.

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

SetApproximation(2)yesyes/nono{{x1},{x6}}{{x3,x4}}{{x2},{x5,x7}}AW7/24/202432高級(jí)人工智能史忠植UsetＸU/RR:subsetofattributesLower&集近似圖示ns7/24/202433高級(jí)人工智能史忠植Lower&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}Theindiscernibilityclassesdefinedby

R={Headache,Temp.}are

{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.7/24/202434高級(jí)人工智能史忠植Lower&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}u1u4u3X1X2u5u7u2u6u87/24/202435高級(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,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}7/24/202436高級(jí)人工智能史忠植近似度

AccuracyofApproximation

where|X|denotesthecardinalityofObviouslyIfXiscrispwithrespecttoB.IfXisroughwithrespecttoB.7/24/202437高級(jí)人工智能史忠植近似性質(zhì)PropertiesofApproximationsimpliesand7/24/202438高級(jí)人工智能史忠植近似性質(zhì)PropertiesofApproximations(2)where-XdenotesU-X.7/24/202439高級(jí)人工智能史忠植三、知識(shí)的約簡(jiǎn)一般約簡(jiǎn)

定義6設(shè)R是等價(jià)關(guān)系的一個(gè)族集，且設(shè)R

R。若IND(R)=IND(R–R)，則稱(chēng)關(guān)系R在族集R之中是可省的(dispensable)﹐否則就是不可省的。若族集R中的每個(gè)關(guān)系R都是不可省的﹐則稱(chēng)族集R是獨(dú)立的(independent)﹐否則就是依賴(lài)的或非獨(dú)立的。定義7

若Q

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

顯然，族集P有多個(gè)約簡(jiǎn)（約簡(jiǎn)的不唯一性）。定理1族集P的核等于P的所有約簡(jiǎn)的交集。即 CORE(P)=∩RED(P)7/24/202440高級(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ì)不能省的

7/24/202441高級(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的所有那些使用分類(lèi)U/P所表達(dá)的知識(shí)，能夠正確地分類(lèi)于U/Q的等價(jià)類(lèi)之中的對(duì)象的集合。 定義9設(shè)P和Q是全域U上的等價(jià)關(guān)系的族集，R

P。若POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q))則稱(chēng)關(guān)系R在族集P中是Q-可省的﹐否則稱(chēng)為Q-不可省的﹔如果在族集P中的每個(gè)關(guān)系R都是Q-不可省的﹐則稱(chēng)P關(guān)于Q是獨(dú)立的﹐否則就稱(chēng)為是依賴(lài)的。7/24/202442高級(jí)人工智能史忠植相對(duì)約簡(jiǎn) 定義10S

P稱(chēng)為P的Q-約簡(jiǎn)(Q-reduct)﹐當(dāng)且僅當(dāng)S是P的Q-獨(dú)立的子族集﹐且POSS(Q)=POSP(Q)；族集P中的所有Q-不可省的初等關(guān)系的集合﹐稱(chēng)為族集P的Q-核(Q-core)﹐記作COREQ(P)。

下面的定理是定理1的拓廣。 定理2族集P的Q-核等于族集P的所有Q-約簡(jiǎn)的交集。即

COREQ(P)=

REDQ(P)

其中REDQ(P)是族集P的所有Q-約簡(jiǎn)的族集。7/24/202443高級(jí)人工智能史忠植知識(shí)的依賴(lài)性

知識(shí)的依賴(lài)性可形式定義如下：定義11設(shè)K=(U,R)是一個(gè)近似空間，P,Q

R。1)知識(shí)Q依賴(lài)于知識(shí)P或知識(shí)P可推導(dǎo)出知識(shí)Q，當(dāng)且僅當(dāng)IND(P)

IND(Q)﹐記作P

Q；2)知識(shí)P和知識(shí)Q是等價(jià)的﹐當(dāng)且僅當(dāng)P

Q且Q

P﹐即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)P

Q且Q

P均不成立，記作P

Q。7/24/202444高級(jí)人工智能史忠植知識(shí)的依賴(lài)性 依賴(lài)性也可以是部分成立的﹐也就是從知識(shí)P能推導(dǎo)出知識(shí)Q的一部分知識(shí)，或者說(shuō)知識(shí)Q只有一部分依賴(lài)于知識(shí)P的。部分依賴(lài)性（部分可推導(dǎo)性）可以由知識(shí)的正區(qū)域來(lái)定義。現(xiàn)在我們形式地定義部分依賴(lài)性。定義12設(shè)K=(U,R)是一個(gè)知識(shí)庫(kù)﹐P,Q

R﹐我們稱(chēng)知識(shí)Q以依賴(lài)度k(0

k

1)依賴(lài)于知識(shí)P﹐記作P

kQ﹐當(dāng)且僅當(dāng)k=

P(Q)=card(POSP(Q))/card(U)(6.8)(1)

若k=1﹐則稱(chēng)知識(shí)Q完全依賴(lài)于知識(shí)P，P

1Q也記成P

Q；(2)

若0

k

1﹐則稱(chēng)知識(shí)Q部分依賴(lài)于知識(shí)P；(3)

若k=0﹐則稱(chēng)知識(shí)Q完全獨(dú)立于與知識(shí)P。7/24/202445高級(jí)人工智能史忠植四、決策表的約簡(jiǎn)決策表 決策表是一類(lèi)特殊而重要的知識(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,D

A是兩個(gè)屬性子集，分別稱(chēng)為條件屬性和決策屬性，且C

D=A，C

D=，則該信息系統(tǒng)稱(chēng)為決策表，記作T=(U,A,C,D)或簡(jiǎn)稱(chēng)CD決策表。關(guān)系IND(C)和關(guān)系IND(D)的等價(jià)類(lèi)分別稱(chēng)為條件類(lèi)和決策類(lèi)。7/24/202446高級(jí)人工智能史忠植

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

7/24/202447高級(jí)人工智能史忠植決策規(guī)則 決策表中的每一行對(duì)應(yīng)諸如

形式的決策規(guī)則，

和

分別稱(chēng)為決策規(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ī)則： 身高(高)

性別(男)

視力(差)錄取(否)

7/24/202448高級(jí)人工智能史忠植決策表的一致性

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

C

D，決策表T=(U,A,C,D)是一致的。 由命題1，很容易通過(guò)計(jì)算條件屬性和決策屬性間的依賴(lài)程度來(lái)檢查一致性。當(dāng)依賴(lài)程度等于1時(shí)，我們說(shuō)決策表是一致的，否則不一致。7/24/202449高級(jí)人工智能史忠植決策表的分解命題2 每個(gè)決策表T=(U,A,C,D)都可以唯一分解為兩個(gè)決策表T1=(U1,A,C,D)和T2=(U2,A,C,D)，這樣使得表T1中C

1D和T2中C

0D。這里U1=POSC(D)，U2=

BNC(X)，X

U|IND(D)。

由命題2可見(jiàn)，假設(shè)我們已計(jì)算出條件屬性的依賴(lài)度，若表的結(jié)果不一致，即依賴(lài)度小于1，則由命題2可以將表分解成兩個(gè)子表：其中一個(gè)表完全不一致，依賴(lài)度為0；另一個(gè)表則完全一致，依賴(lài)度為1。當(dāng)然，只有依賴(lài)度大于0且不等于1時(shí)，這一分解才能進(jìn)行。7/24/202450高級(jí)人工智能史忠植表2不一致決策表

a、b、c為條件屬性，d、e為決策屬性1、5產(chǎn)生不一致Uabcde1234567810220011122001111022102012201121112011017/24/202451高級(jí)人工智能史忠植表3完全一致的決策表Uabcde346720011110222201121112表4完全不一致的決策表Uabcde1258102200111210201011017/24/202452高級(jí)人工智能史忠植一致決策表的約簡(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ī)則中屬性的冗余值。

7/24/202453高級(jí)人工智能史忠植條件屬性的約簡(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ū)別的所有屬性的集合7/24/202454高級(jí)人工智能史忠植差別矩陣對(duì)應(yīng)的核與約簡(jiǎn)

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

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

相對(duì)于集合包含關(guān)系運(yùn)算而言，若屬性集合B

A是滿足下列條件

B∩cij≠

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

的一個(gè)最小屬性子集，則稱(chēng)屬性集合B

A是A的一個(gè)約簡(jiǎn)。 換言之，約簡(jiǎn)是這樣的最小屬性子集，它能夠區(qū)分用整個(gè)屬性集合A可區(qū)分的所有對(duì)象。7/24/202455高級(jí)人工智能史忠植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)7/24/202456高級(jí)人工智能史忠植

為了對(duì)決策表進(jìn)行約簡(jiǎn)，可以采用差別矩陣的方法對(duì)條件屬性進(jìn)行約簡(jiǎn)，對(duì)決策屬性相同的個(gè)體不予比較。考慮下面的決策表5，條件屬性為a,b,c,d，決策屬性為eU/Aabcdeu110210u200121u320210u400222u511210表57/24/202457高級(jí)人工智能史忠植表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}7/24/202458高級(jí)人工智能史忠植表6根據(jù)得到的兩個(gè)約簡(jiǎn)，表5可以簡(jiǎn)化為表6和表7U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210表77/24/202459高級(jí)人工智能史忠植求最優(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)為止。

7/24/202460高級(jí)人工智能史忠植行的約簡(jiǎn) 對(duì)決策表中的重復(fù)的行要?jiǎng)h除，因?yàn)樗鼈兊臈l件屬性和決策屬性都相同，都表示同一條決策規(guī)則。另外，決策規(guī)則的列表順序不是本質(zhì)性的，所以表6、表7都可進(jìn)行約簡(jiǎn)，如表6可簡(jiǎn)化為下表：U\Aaceu1120u2011u3220u4022表87/24/202461高級(jí)人工智能史忠植屬性值的約簡(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)。7/24/202462高級(jí)人工智能史忠植非一致決策表的約簡(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)步驟類(lèi)似。7/24/202463高級(jí)人工智能史忠植五、粗糙集的擴(kuò)展模型 基本粗糙集理論的主要存在的問(wèn)題是： 1)

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

對(duì)于粗糙集的邊界區(qū)域的刻畫(huà)過(guò)于簡(jiǎn)單； 3)粗糙集理論的方法在可用信息不完全的情況下將對(duì)象們歸類(lèi)于某一具體的類(lèi)，通常分類(lèi)是確定的，但并未提供數(shù)理統(tǒng)計(jì)中所常用的在一個(gè)給定錯(cuò)誤率的條件下將盡可能多的對(duì)象進(jìn)行分類(lèi)的方法，而實(shí)際中常常遇到這類(lèi)問(wèn)題。7/24/202464高級(jí)人工智能史忠植可變精度粗糙集模型

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

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

C(X,Y)=1–card(X

Y)/card(X)當(dāng)card(x)>0，C(X,Y)=0當(dāng)card(x)=0。 C(X,Y)表示把集合X歸類(lèi)于集合Y的誤分類(lèi)度，即有C(X,Y)

100%的