《高級人工智能》第九章知識發(fā)現(xiàn)和數(shù)據(jù)挖掘VIP

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

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

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

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

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

其中U

（為空集）是一個被稱為全域或論域(universe)的所有要討論的個體的集合，R是U上等價關系的一個族集。

3/5/202511高級人工智能史忠植二、知識分類

設P

R，且P

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

RP

注意，IND(P)也是等價關系且是唯一的。3/5/202512高級人工智能史忠植二、知識分類

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

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

R所產(chǎn)生的不分明關系IND(P)的所有等價類關系的集合即U/IND(P)，稱為基本知識(basicknowledge)，相應的等價類稱為基本概念(basicconcept)；特別地，若關系Q

R，則關系Q就稱為初等知識(elementaryknowledge)，相應的等價類就稱為初等概念(elementaryconcept)。一般用大寫字母P,Q,R等表示一個關系，用大寫黑體字母P,Q,R等表示關系的族集；[x]R或R(x)表示關系R中包含元素x

U的概念或等價類。為了簡便起見，有時用P代替IND(P)。根據(jù)上述定義可知，概念即對象的集合，概念的族集（分類）就是U上的知識，U上分類的族集可以認為是U上的一個知識庫，或說知識庫即是分類方法的集合。3/5/202513高級人工智能史忠植二、知識分類

粗糙集理論與傳統(tǒng)的集合理論有著相似之處，但是它們的出發(fā)點完全不同。傳統(tǒng)集合論認為，一個集合完全是由其元素所決定，一個元素要么屬于這個集合，要么不屬于這個集合，即它的隸屬函數(shù)

X(x)

{0,1}。模糊集合對此做了拓廣，它給成員賦予一個隸屬度，即

X(x)

[0,1]，使得模糊集合能夠處理一定的模糊和不確定數(shù)據(jù)，但是其模糊隸屬度的確定往往具有人為因素，這給其應用帶來了一定的不便。而且，傳統(tǒng)集合論和模糊集合論都是把隸屬關系作為原始概念來處理，集合的并和交就建立在其元素的隸屬度max和min操作上，因此其隸屬度必須事先給定（傳統(tǒng)集合默認隸屬度為1或0）。在粗糙集中，隸屬關系不再是一個原始概念，因此無需人為給元素指定一個隸屬度，從而避免了主觀因素的影響。3/5/202514高級人工智能史忠植InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthatforeveryiscalledthevaluesetofa.

AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-493/5/202515高級人工智能史忠植DecisionSystems/TablesDS:isthedecisionattribute

(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.

AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/5/202516高級人工智能史忠植IssuesintheDecisionTableThesameorindiscernibleobjectsmayberepresentedseveraltimes.Someoftheattributesmaybesuperfluous.3/5/202517高級人工智能史忠植難區(qū)分性IndiscernibilityTheequivalencerelationAbinaryrelationwhichisreflexive(xRx

foranyobjectx),symmetric(ifxRythenyRx),andtransitive(ifxRyandyRz

thenxRz).TheequivalenceclassofanelementconsistsofallobjectssuchthatxRy.3/5/202518高級人工智能史忠植難區(qū)分性Indiscernibility(2)LetIS=(U,A)beaninformationsystem,thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandx’areindiscerniblefromeachotherbyattributesfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby3/5/202519高級人工智能史忠植難區(qū)分性實例

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-49no3/5/202520高級人工智能史忠植概念的邊界

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

為數(shù)學處理方便起見，在下面的定義中用等價關系來代替分類。3/5/202522高級人工智能史忠植粗糙集的基本定義

定義1一個近似空間(approximatespace)(或知識庫)定義為一個關系系統(tǒng)(或二元組)K=(U,R)，

其中U

(

為空集)是一個被稱為全域或論域(universe)的所有要討論的個體的集合，R是U上等價關系的一個族集。 定義2設P

R，且P

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

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

R所產(chǎn)生的不分明關系IND(P)的所有等價類關系的集合即U/IND(P)，稱為基本知識(basicknowledge)，相應的等價類稱為基本概念(basicconcept)；特別地，若關系Q

R，則關系Q就稱為初等知識(elementaryknowledge)，相應的等價類就稱為初等概念(elementaryconcept)。3/5/202524高級人工智能史忠植上近似、下近似和邊界區(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就是一個粗糙概念。下近似包含了所有使用知識R可確切分類到X的元素，上近似則包含了所有那些可能是屬于X的元素。概念的邊界區(qū)域由不能肯定分類到這個概念或其補集中的所有元素組成。POSR(X)=R*(X)稱為集合X的R-正區(qū)域，NEGR(X)=U–R*(X)稱為集合X的R-反區(qū)域。3/5/202525高級人工智能史忠植Lower&UpperApproximations(2)

LowerApproximation:UpperApproximation:3/5/202526高級人工智能史忠植新型的隸屬關系傳統(tǒng)集合論中，一個元素的隸屬函數(shù)

X(x)

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

X(x)

[0,1]

定義4設X

U且x

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

定義為

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

U)

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

X>0當且僅當[x]R

X

=0當且僅當[x]R

X=

3/5/202527高級人工智能史忠植隸屬關系根據(jù)上面的定義，可以得到以下性質(zhì)(1）(x)=1當且僅當[x]R

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

X

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

X=。顯然有(x)

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

B-outsideregionofX,consistsofthoseobjectsthatcanbewithcertaintyclassifiedasnotbelongingtoX.Asetissaidtoberough

ifitsboundaryregionisnon-empty,otherwisethesetiscrisp.

3/5/202530高級人工智能史忠植集近似實例SetApproximationLetW={x|Walk(x)=yes}.Thedecisionclass,Walk,isroughsincetheboundaryregionisnotempty.

AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no3/5/202531高級人工智能史忠植集近似實例

SetApproximation(2)yesyes/nono{{x1},{x6}}{{x3,x4}}{{x2},{x5,x7}}AW3/5/202532高級人工智能史忠植UsetＸU/RR:subsetofattributesLower&集近似圖示ns3/5/202533高級人工智能史忠植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}.3/5/202534高級人工智能史忠植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}u1u4u3X1X2u5u7u2u6u83/5/202535高級人工智能史忠植例1：設有一知識庫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}}

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

P*X1={x4}∪{x7}={x4,x7} P*X1={x1,x5}∪{x4}∪{x7}={x1,x4,x5,x7}3/5/202536高級人工智能史忠植近似度

AccuracyofApproximation

where|X|denotesthecardinalityofObviouslyIfXiscrispwithrespecttoB.IfXisroughwithrespecttoB.3/5/202537高級人工智能史忠植近似性質(zhì)PropertiesofApproximationsimpliesand3/5/202538高級人工智能史忠植近似性質(zhì)PropertiesofApproximations(2)where-XdenotesU-X.3/5/202539高級人工智能史忠植三、知識的約簡一般約簡

定義6設R是等價關系的一個族集，且設R

R。若IND(R)=IND(R–R)，則稱關系R在族集R之中是可省的(dispensable)﹐否則就是不可省的。若族集R中的每個關系R都是不可省的﹐則稱族集R是獨立的(independent)﹐否則就是依賴的或非獨立的。定義7

若Q

P是獨立的﹐并且IND(Q)=IND(P)﹐則稱Q是關系族集P的一個約簡(reduct)。在族集P中所有不可省的關系的集合稱為P的核(core)﹐以CORE(P)來表示。

顯然，族集P有多個約簡（約簡的不唯一性）。定理1族集P的核等于P的所有約簡的交集。即 CORE(P)=∩RED(P)3/5/202540高級人工智能史忠植

例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}三個等價關系組成的集合和{p,q}、{p,r}定義了相同的不分明關系。 又IND({p,q})

IND({p})﹐IND({p﹐q})

IND({q})﹐則{p,q}和{p,r}就是P的約簡﹐而且{p}是P的核﹐也就是說p是絕對不能省的

3/5/202541高級人工智能史忠植相對約簡 定義8設P和Q是全域U上的等價關系的族集，所謂族集Q的P-正區(qū)域(P-positiveregionofQ)，記作POSP(Q)=

P*(X) 族集Q的P-正區(qū)域是全域U的所有那些使用分類U/P所表達的知識，能夠正確地分類于U/Q的等價類之中的對象的集合。 定義9設P和Q是全域U上的等價關系的族集，R

P。若POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q))則稱關系R在族集P中是Q-可省的﹐否則稱為Q-不可省的﹔如果在族集P中的每個關系R都是Q-不可省的﹐則稱P關于Q是獨立的﹐否則就稱為是依賴的。3/5/202542高級人工智能史忠植相對約簡 定義10S

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

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

COREQ(P)=

REDQ(P)

其中REDQ(P)是族集P的所有Q-約簡的族集。3/5/202543高級人工智能史忠植知識的依賴性

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

R。1)知識Q依賴于知識P或知識P可推導出知識Q，當且僅當IND(P)

IND(Q)﹐記作P

Q；2)知識P和知識Q是等價的﹐當且僅當P

Q且Q

P﹐即IND(P)=IND(Q)﹐記作P=Q，明顯地，P=Q當且僅當IND(P)=IND(Q)；3)知識P和知識Q是獨立的，當且僅當P

Q且Q

P均不成立，記作P

Q。3/5/202544高級人工智能史忠植知識的依賴性 依賴性也可以是部分成立的﹐也就是從知識P能推導出知識Q的一部分知識，或者說知識Q只有一部分依賴于知識P的。部分依賴性（部分可推導性）可以由知識的正區(qū)域來定義。現(xiàn)在我們形式地定義部分依賴性。定義12設K=(U,R)是一個知識庫﹐P,Q

R﹐我們稱知識Q以依賴度k(0

k

1)依賴于知識P﹐記作P

kQ﹐當且僅當k=

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

若k=1﹐則稱知識Q完全依賴于知識P，P

1Q也記成P

Q；(2)

若0

k

1﹐則稱知識Q部分依賴于知識P；(3)

若k=0﹐則稱知識Q完全獨立于與知識P。3/5/202545高級人工智能史忠植四、決策表的約簡決策表 決策表是一類特殊而重要的知識表達系統(tǒng)，它指當滿足某些條件時，決策（行為）應當怎樣進行。多數(shù)決策問題都可以用決策表形式來表示，這一工具在決策應用中起著重要的作用。 決策表可以定義如下：

S=(U,A)為一信息系統(tǒng)，且C,D

A是兩個屬性子集，分別稱為條件屬性和決策屬性，且C

D=A，C

D=，則該信息系統(tǒng)稱為決策表，記作T=(U,A,C,D)或簡稱CD決策表。關系IND(C)和關系IND(D)的等價類分別稱為條件類和決策類。3/5/202546高級人工智能史忠植

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

3/5/202547高級人工智能史忠植決策規(guī)則 決策表中的每一行對應諸如

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

和

分別稱為決策規(guī)則的前驅(qū)和后繼。 當決策表S中決策規(guī)則

為真時，我們說該決策規(guī)則是S中一致的，否則說該決策規(guī)則是S中不一致的。若決策規(guī)則是S中一致的，相同的前驅(qū)必導致相同的后繼；但同一種后繼不一定必需是同一前驅(qū)產(chǎn)生的。

如表1第一行對應決策規(guī)則： 身高(高)

性別(男)

視力(差)錄取(否)

3/5/202548高級人工智能史忠植決策表的一致性

命題1 當且僅當

C

D，決策表T=(U,A,C,D)是一致的。 由命題1，很容易通過計算條件屬性和決策屬性間的依賴程度來檢查一致性。當依賴程度等于1時，我們說決策表是一致的，否則不一致。3/5/202549高級人工智能史忠植決策表的分解命題2 每個決策表T=(U,A,C,D)都可以唯一分解為兩個決策表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é)果不一致，即依賴度小于1，則由命題2可以將表分解成兩個子表：其中一個表完全不一致，依賴度為0；另一個表則完全一致，依賴度為1。當然，只有依賴度大于0且不等于1時，這一分解才能進行。3/5/202550高級人工智能史忠植表2不一致決策表

a、b、c為條件屬性，d、e為決策屬性1、5產(chǎn)生不一致Uabcde1234567810220011122001111022102012201121112011013/5/202551高級人工智能史忠植表3完全一致的決策表Uabcde346720011110222201121112表4完全不一致的決策表Uabcde1258102200111210201011013/5/202552高級人工智能史忠植一致決策表的約簡

在我們制定決策時是否需要全部的條件屬性，能否進行決策表的約簡。約簡后的決策表具有與約簡前的決策表相同的功能，但是約簡后的決策表具有更少的條件屬性。 一致決策表的約簡步驟如下： (1)對決策表進行條件屬性的約簡，即從決策表中消去某一列；(主要研究點)

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

3/5/202553高級人工智能史忠植條件屬性的約簡

A.Skowron提出了差別矩陣，使核與約簡等概念的計算較為簡單，主要思想：

設S=(U,A)為一個知識表示系統(tǒng)，其中U={x1,x2,…,xn}，xi為所討論的個體，i=1,2,…,n，A={a1,a2,…,am}，aj為個體所具有的屬性，j=1,2,…,m。

知識表達系統(tǒng)S的差別矩陣M(S)=[cij]n×n，其中矩陣項定義如下：

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

因此cij是個體xi與xj有區(qū)別的所有屬性的集合3/5/202554高級人工智能史忠植差別矩陣對應的核與約簡

核就可以定義為差別矩陣中所有只有一個元素的矩陣項的集合，即

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

相對于集合包含關系運算而言，若屬性集合B

A是滿足下列條件

B∩cij≠

，對于M(S)中的任一非空項cij≠

的一個最小屬性子集，則稱屬性集合B

A是A的一個約簡。 換言之，約簡是這樣的最小屬性子集，它能夠區(qū)分用整個屬性集合A可區(qū)分的所有對象。3/5/202555高級人工智能史忠植Skowron的約簡方法

對于每一個差別矩陣M(S)對應唯一的差別函數(shù)fM(S)﹙DiscernibilityFunction﹚，它的定義如下： 信息系統(tǒng)S的差別函數(shù)fM(S)是一個有m-元變量a1,…,am(ai∈A，i=1,…,m)的布爾函數(shù)，它是∨cij的合取，∨cij是矩陣項cij中的各元素的析取，1≤j<i≤n且cij≠Φ。

根據(jù)差別函數(shù)與約簡的對應關系，A.Skowron提出了計算信息系統(tǒng)S的約簡RED(S)的方法： 1）

計算信息系統(tǒng)S的差別矩陣M(S) 2）

計算與差別矩陣M(S)對應的差別函數(shù)fM(S) 3）計算差別函數(shù)fM(S)的最小析取范式，其中每個析取分量對應一個約簡3/5/202556高級人工智能史忠植

為了對決策表進行約簡，可以采用差別矩陣的方法對條件屬性進行約簡，對決策屬性相同的個體不予比較?？紤]下面的決策表5，條件屬性為a,b,c,d，決策屬性為eU/Aabcdeu110210u200121u320210u400222u511210表53/5/202557高級人工智能史忠植表5對應的差別矩陣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)，得到兩個約簡{a,c}和{c,d}3/5/202558高級人工智能史忠植表6根據(jù)得到的兩個約簡，表5可以簡化為表6和表7U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210表73/5/202559高級人工智能史忠植求最優(yōu)或次優(yōu)約簡

所有約簡的計算是NP-hard問題，因此運用啟發(fā)信息來簡化計算以找出最優(yōu)或次優(yōu)約簡是必要的。

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

3/5/202560高級人工智能史忠植行的約簡 對決策表中的重復的行要刪除，因為它們的條件屬性和決策屬性都相同，都表示同一條決策規(guī)則。另外，決策規(guī)則的列表順序不是本質(zhì)性的，所以表6、表7都可進行約簡，如表6可簡化為下表：U\Aaceu1120u2011u3220u4022表83/5/202561高級人工智能史忠植屬性值的約簡 對于決策表而言，屬性值的約簡就是決策規(guī)則的約簡。決策規(guī)則的約簡是利用決策邏輯消去每個決策規(guī)則的不必要條件，它不是整體上約簡屬性，而是針對每個決策規(guī)則，去掉表達該規(guī)則時的冗余屬性值，即要計算每條決策規(guī)則的核與約簡。3/5/202562高級人工智能史忠植非一致決策表的約簡 對于一致的決策表比較容易處理，在進行約簡時，只要判斷去掉某個屬性或某個屬性值時是否會導致不一致規(guī)則的產(chǎn)生。而對不一致表進行約簡時就不能再使用這種方法了，一般采用下面的方法：一種是考慮正域的變化，另外一種是將不一致表分成完全一致表和完全不一致表兩個子表。 非一致決策表的約簡步驟與一致決策表的約簡步驟類似。3/5/202563高級人工智能史忠植五、粗糙集的擴展模型 基本粗糙集理論的主要存在的問題是： 1)

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

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

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

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

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

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

100%