高級人工智能

高級人工智能

第十一章

史忠植

中國科學院計算技術(shù)研究所粗糙集RoughSet

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

1/17/20233模糊集1965年，Zadeh提出了模糊集，不少理論計算機科學家和邏輯學家試圖通過這一理論解決G.Frege的含糊概念，但模糊集理論采用隸屬度函數(shù)來處理模糊性，而基本的隸屬度是憑經(jīng)驗或者由領域?qū)＜医o出，所以具有相當?shù)闹饔^性。1/17/20234粗糙集的提出20世紀80年代初，波蘭的Pawlak針對G.Frege的邊界線區(qū)域思想提出了粗糙集（RoughSet）﹐他把那些無法確認的個體都歸屬于邊界線區(qū)域，而這種邊界線區(qū)域被定義為上近似集和下近似集之差集。由于它有確定的數(shù)學公式描述，完全由數(shù)據(jù)決定，所以更有客觀性。1/17/20235粗糙集的研究粗糙集理論的主要優(yōu)勢之一是它不需要任何預備的或額外的有關(guān)數(shù)據(jù)信息。自提出以來，許多計算機科學家和數(shù)學家對粗糙集理論及其應用進行了堅持不懈的研究，使之在理論上日趨完善，特別是由于20世紀80年代末和90年代初在知識發(fā)現(xiàn)等領域得到了成功的應用而越來越受到國際上的廣泛關(guān)注。1/17/20236粗糙集的研究1991年波蘭Pawlak教授的第一本關(guān)于粗糙集的專著《RoughSets：TheoreticalAspectsofReasoningaboutData》和1992年R.Slowinski主編的關(guān)于粗糙集應用及其與相關(guān)方法比較研究的論文集的出版，推動了國際上對粗糙集理論與應用的深入研究。1992年在波蘭Kiekrz召開了第1屆國際粗糙集討論會。從此每年召開一次與粗糙集理論為主題的國際研討會。1/17/20237研究現(xiàn)狀分析2001年5月在重慶召開了“第1屆中國Rough集與軟計算學術(shù)研討會”，邀請了創(chuàng)始人Z.Pawlak教授做大會報告；2002年10月在蘇州第2屆中國粗糙集與軟計算學術(shù)研討會2003年5月在重慶第3屆中國粗糙集與軟計算學術(shù)研討會2004年10月中下旬在浙江舟山召開第4屆中國粗糙集與軟計算學術(shù)研討會2005年8月1日至5日在鞍山科技大學召開第五屆中國Rough集與軟計算學術(shù)研討會（CRSSC2005）2006第六屆中國粗糙集與軟計算學術(shù)研討會在浙江師范大學1/17/20238研究現(xiàn)狀分析2007年粗糙集與軟計算、Web智能、粒計算聯(lián)合學術(shù)會議,山西大學2008年第8屆中國粗糙集與軟計算學術(shù)會議、第2屆中國Web智能學術(shù)研討會、第2屆中國粒計算學術(shù)研討會聯(lián)合學術(shù)會議（CRSSC-CWI-CGrC2008）,河南師范大學中科院計算所、中科院自動化所、重慶郵電學院、南昌大學、西安交通大學、山西大學、合肥工業(yè)大學、北京工業(yè)大學、上海大學

1/17/20239研究現(xiàn)狀分析曾黃麟.粗集理論及其應用(修訂版).重慶:重慶大學出版社,1998劉清.RoughSet及Rough推理.北京:科學出版社,2001張文修等.RoughSet理論與方法.北京:科學出版社,2001王國胤.RoughSet理論與知識獲取.西安:西安交通大學出版社,2001史忠植.知識發(fā)現(xiàn).北京:清華大學出版社,2002苗奪謙//王國胤//劉清//林早陽//姚一豫.粒計算--過去現(xiàn)在與展望.科學出版社,2007

1/17/202310二、知知識識分類類基本粗粗糙集集理論論認為為知識識就是是人類類和其其他物物種所所固有有的分分類能能力。。例如，，在現(xiàn)現(xiàn)實世世界中中關(guān)于于環(huán)境境的知知識主主要表表明了了生物物根據(jù)據(jù)其生生存觀觀來對對各種種各樣樣的情情形進進行分分類區(qū)區(qū)別的的能力力。每每種生生物根根據(jù)其其傳感感器信信號形形成復復雜的的分類類模式式，就就是這這種生生物的的基本本機制制。分類是是推理理、學學習與與決策策中的的關(guān)鍵鍵問題題。因因此，，粗糙糙集理理論假假定知知識是是一種種對對對象進進行分分類的的能力力。這這里的的“對對象””是指指我們們所能能言及及的任任何事事物，，比如如實物物、狀狀態(tài)、、抽象象概念念、過過程和和時刻刻等等等。即即知識識必須須與具具體或或抽象象世界界的特特定部部分相相關(guān)的的各種種分類類模式式聯(lián)系系在一一起，，這種種特定定部分分稱之之為所所討論論的全域或論域(universe)。對對于全全域及及知識識的特特性并并沒有有任何何特別別假設設。事實上，知知識構(gòu)成了了某一感興興趣領域中中各種分類類模式的一一個族集(family)，，這個族集集提供了關(guān)關(guān)于現(xiàn)實的的顯事實，，以及能夠夠從這些顯顯事實中推推導出隱事事實的推理理能力。12/31/202211二、知識識分類為數(shù)學處理理方便起見見，在下面面的定義中中用等價關(guān)關(guān)系來代替替分類。一個近似空間(approximatespace)（或知識庫）定義為一一個關(guān)系系系統(tǒng)（或二二元組）K=(U,R)其中U（為空集集）是一個個被稱為全全域或論域域(universe)的所所有要討論論的個體的的集合，R是U上等價價關(guān)系的一一個族集。。12/31/202212二、知識識分類設PR，且P，P中所有等價價關(guān)系的交交集稱為P上的一種不不可區(qū)分關(guān)關(guān)系(indiscernbilityrelation)（或稱難區(qū)區(qū)分關(guān)系）），記作IND(P)，即[x]IND(p)=∩[x]RRP注意，IND(P)也是等價價關(guān)系且是是唯一的。。12/31/202213二、知知識分類類給定近似似空間K=(U,R)，子集XU稱為U上的一個個概念(concept)，形式上上，空集集也視為為一個概概念；非非空子族族集PR所產(chǎn)生的的不分明明關(guān)系IND(P)的所有等等價類關(guān)關(guān)系的集集合即U/IND(P)，稱為基本知識識(basicknowledge)，相應的的等價類類稱為基本概念念(basicconcept)；特別地地，若關(guān)關(guān)系QR，則關(guān)系系Q就稱為初等知識識(elementaryknowledge)，相應的的等價類類就稱為為初等概念念(elementaryconcept)。一般用大大寫字母母P,Q,R等表示一一個關(guān)系系，用大大寫黑體體字母P,Q,R等表示關(guān)關(guān)系的族族集；[x]R或R(x)表示關(guān)系系R中包含元元素xU的概念或或等價類類。為了了簡便起起見，有有時用P代替IND(P)。根據(jù)上述述定義可可知，概概念即對對象的集集合，概概念的族族集（分分類）就就是U上上的知識識，U上上分類的的族集可可以認為為是U上上的一個個知識庫庫，或說說知識庫庫即是分分類方法法的集合合。12/31/202214二、知識分分類粗糙集理論與與傳統(tǒng)的集合合理論有著相相似之處，但但是它們的出出發(fā)點完全不不同。傳統(tǒng)集集合論認為，，一個集合完完全是由其元元素所決定，，一個元素要要么屬于這個個集合，要么么不屬于這個個集合，即它它的隸屬函數(shù)數(shù)X(x){0,1}。。模糊集合對對此做了拓廣廣，它給成員員賦予一個隸隸屬度，即X(x)[0,1]，，使得模糊集集合能夠處理理一定的模糊糊和不確定數(shù)數(shù)據(jù)，但是其其模糊隸屬度度的確定往往往具有人為因因素，這給其其應用帶來了了一定的不便便。而且，傳傳統(tǒng)集合論和和模糊集合論論都是把隸屬屬關(guān)系作為原原始概念來處處理，集合的的并和交就建建立在其元素素的隸屬度max和min操作上，，因此其隸屬屬度必須事先先給定（傳統(tǒng)統(tǒng)集合默認隸隸屬度為1或或0）。在粗粗糙集中，隸隸屬關(guān)系不再再是一個原始始概念，因此此無需人為給給元素指定一一個隸屬度，，從而避免了了主觀因素的的影響。12/31/202215InformationSystems/TablesISisapair(U,A)Uisanon-emptyfinitesetofobjects.Aisanon-emptyfinitesetofattributessuchthatforeveryiscalledthevaluesetofa.AgeLEMSx１16-3050x216-300x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-4912/31/202216DecisionSystems/TablesDS:isthedecisionattribute(insteadofonewecanconsidermoredecisionattributes).TheelementsofAarecalledtheconditionattributes.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/31/202217IssuesintheDecisionTable相同同或或不不可可區(qū)區(qū)分分的的對對象象可可能能被被表表示示多多次次Thesameorindiscernibleobjectsmayberepresentedseveraltimes.有些屬性性可能是是多余的的Someoftheattributesmaybesuperfluous.12/31/202218不可區(qū)分分性IndiscernibilityTheequivalencerelationAbinaryrelationwhichisreflexive(xRxforanyobjectx),symmetric(ifxRythenyRx),andtransitive(ifxRyandyRzthenxRz).TheequivalenceclassofanelementconsistsofallobjectssuchthatxRy.12/31/202219不可區(qū)分分性Indiscernibility(2)LetIS=(U,A)beaninformationsystem,thenwithanythereisanassociatedequivalencerelation:whereiscalledtheB-indiscernibilityrelation.Ifthenobjectsxandx’areindiscerniblefromeachotherbyattributesfromB.TheequivalenceclassesoftheB-indiscernibilityrelationaredenotedby12/31/202220不可區(qū)區(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-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/31/202221概念的邊界界知識的粒度度性是造成成使用已有有知識不能能精確地表表示某些概概念的原因因。這就產(chǎn)產(chǎn)生了所謂謂的關(guān)于不不精確的““邊界”思思想。著名名哲學家Frege認為“概概念必須有有明確的邊邊界。沒有有明確邊界界的概念，，將對應于于一個在周周圍沒有明明確界線的的區(qū)域”。。粗糙集理理論中的模模糊性就是是一種基于于邊界的概概念，即一一個不精確確的概念具具有模糊的的不可被明明確劃分的的邊界。為刻畫模糊糊性，每個個不精確概概念由一對對稱為上近近似與下近近似的精確確概念來表表示，它們們可用隸屬屬函數(shù)定義義12/31/202222粗糙集的基本本定義知識的分類觀觀點粗糙集理論假假定知識是一一種對對象進進行分類的能能力。而知識識必須與具體體或抽象世界界的特定部分分相關(guān)的各種種分類模式聯(lián)聯(lián)系在一起，，這種特定部部分稱之為所所討論的全域或論域(universe)。為數(shù)學處理方方便起見，在在下面的定義義中用等價關(guān)關(guān)系來代替分分類。12/31/202223粗糙集的基本本定義定義1一個近似空間(approximatespace)(或知識庫)定義為一個個關(guān)系系統(tǒng)(或二元組)K=(U,R)，其中U(為空集)是一一個被稱為全全域或論域(universe)的所有要討論論的個體的集集合，R是U上等價關(guān)系的的一個族集。。定義2設PR，且P，P中所有等價關(guān)關(guān)系的交集稱稱為P上的一種不分分明關(guān)系(indiscernbilityrelation)（或稱不可區(qū)區(qū)分關(guān)系），，記作IND(P)12/31/202224粗糙集的基本本定義定義3給定近似空間間K=(U,R)，子集XU稱為U上的一個概念(concept)，形式上，空空集也視為一一個概念；非非空子族集PR所產(chǎn)生的不分分明關(guān)系IND(P)的所有等價類類關(guān)系的集合合即U/IND(P)，稱為基本知識(basicknowledge)，相應的等價價類稱為基本概念(basicconcept)；特別地，若若關(guān)系QR，則關(guān)系Q就稱為初等知識(elementaryknowledge)，相應的等價價類就稱為初等概念(elementaryconcept)。12/31/202225上近近似似、、下下近近似似和和邊邊界界區(qū)區(qū)域域定義義5:X的的下下近近似似：：R*(X)={x:(xU)([x]RX)}X的的上上近近似似：：R*(X)={x:(xU)([x]RX)}X的的邊邊界界區(qū)區(qū)域域：：BNR(X)=R*(X)––R*(X)若BNR(X)，，則集集合合X就就是是一一個個粗粗糙糙概概念念。。下下近近似似包包含含了了所所有有使使用用知知識識R可可確確切切分分類類到到X的的元元素素，，上上近近似似則則包包含含了了所所有有那那些些可可能能是是屬屬于于X的的元元素素。。概概念念的的邊邊界界區(qū)區(qū)域域由由不不能能肯肯定定分分類類到到這這個個概概念念或或其其補補集集中中的的所所有有元元素素組組成成。。POSR(X)=R*(X)稱稱為為集集合合X的的R-正區(qū)區(qū)域域，NEGR(X)=U––R*(X)稱稱為為集集合合X的的R-反區(qū)區(qū)域域。12/31/202226Lower&UpperApproximations(2)LowerApproximation:UpperApproximation:上近近似似、、下下近近似似和和邊邊界界區(qū)區(qū)域域12/31/202227新型的的隸屬屬關(guān)系系傳統(tǒng)集集合論論中，，一個個元素素的隸隸屬函函數(shù)X(x){0,1}。而而粗糙糙集理理論中中，X(x)[0,1]定義4設XU且xU,集合X的粗糙隸隸屬函函數(shù)(roughmembershipfunction)定義為為其中R是不不分明明關(guān)系系，R(x)=[x]R={y:(yU)(yRx)}=1當當且僅僅當[x]RX>0當當且僅僅當[x]RX=0當當且僅僅當[x]RX=12/31/202228隸屬關(guān)系顯然有[0,1]。。我們可以以看到，這這里的隸屬屬關(guān)系是根根據(jù)已有的的分類知識識客觀計算算出來的，，可以被解解釋為一種種條件概率率，能夠從從全域上的的個體加以以計算，而而不是主觀觀給定的。。12/31/202229集近似實實例SetApproximationLetW={x|Walk(x)=yes}.Thedecisionclass,Walk,isroughsincetheboundaryregionisnotempty.AgeLEMSWalkx１16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no12/31/202230集近似實實例SetApproximation(2)yesyes/nono{{x1},{x6}}{{x3,x4}}{{x2},{x5,x7}}AW12/31/202231UsetＸU/RR:subsetofattributes粗糙集近似圖圖示12/31/202232Lower&Upper近似(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/31/202233Lower&Upper近似(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/31/202234例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}Lower&Upper近似似(5)12/31/202235近似似度度AccuracyofApproximationwhere|X|denotesthecardinalityofObviouslyIfXiscrispwithrespecttoB.IfXisroughwithrespecttoB.12/31/202236近似性質(zhì)質(zhì)PropertiesofApproximationsimpliesand12/31/202237近似性質(zhì)質(zhì)PropertiesofApproximations(2)where-XdenotesU-X.12/31/202238三、知知識的約約簡一般約簡簡定義6設R是等價價關(guān)系系的一一個族族集，，且設設RR。若IND(R)=IND(R–R)，則稱稱關(guān)系系R在族集集R之中是是可省的(dispensable)﹐否則則就是是不可省省的。若若族集集R中的每每個關(guān)關(guān)系R都是不不可省省的﹐﹐則稱稱族集集R是獨立的的(independent)﹐否則則就是是依賴的的或非獨立立的。定義7若QP是獨立立的﹐﹐并且且IND(Q)=IND(P)﹐則稱稱Q是關(guān)系系族集集P的一個個約簡(reduct)。在族族集P中所有有不可可省的的關(guān)系系的集集合稱稱為P的核(core)﹐以CORE(P)來表示示。顯然，，族集集P有多個個約簡簡（約約簡的的不唯唯一性性）。。定理1族集P的核等等于P的所有有約簡簡的交交集。。即CORE(P)=∩RED(P)12/31/202239例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}三三個等價關(guān)關(guān)系組成的的集合和{p,q}、{p,r}定義義了相同的的不分明關(guān)關(guān)系。又IND({p,q})IND({p})﹐IND({p﹐q})IND({q})﹐則{p,q}和和{p,r}就是是P的約簡﹐而且{p}是P的的核﹐也就就是說p是是絕對不能能省的三、知識識的約簡12/31/202240相對約簡定義8設P和Q是全域U上的等價關(guān)關(guān)系的族集集，所謂族族集Q的P-正區(qū)域(P-positiveregionofQ)，記作POSP(Q)=P*(X)族集Q的P-正區(qū)域域是全域U的的所有那些些使用分類類U/P所表達的知知識，能夠夠正確地分分類于U/Q的等價類之之中的對象象的集合。。定義9設P和Q是全域U上的等價關(guān)關(guān)系的族集集，RP。若POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q))則稱稱關(guān)系R在在族集P中是Q-可省的的﹐否則稱為為Q-不可省省的﹔如果在族族集P中的每個關(guān)關(guān)系R都是是Q-不可省的的﹐則稱P關(guān)于Q是獨立的﹐否則就稱稱為是依賴的。12/31/202241相對對約約簡簡定義義10SP稱為為P的Q-約約簡簡(Q-reduct)﹐﹐當當且且僅僅當當S是P的Q-獨立的子族族集﹐且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-約簡的族集集。12/31/202242知識的依賴性性知識的依賴性性可形式定義義如下：定義11設K=(U,R)是一個近似似空間，P,QR。1)知識Q依賴于知識P或知識P可推導出知識Q，當且僅當IND(P)IND(Q)﹐記作PQ；2)知識P和知識Q是等價的﹐當且僅當PQ且QP﹐即IND(P)=IND(Q)﹐記作P=Q，明顯地，P=Q當且僅當IND(P)=IND(Q)；3)知識P和知識Q是獨立的，當且僅當PQ且QP均不成立，記記作PQ。12/31/202243知識的的依賴賴性依賴性性也可可以是是部分分成立立的﹐﹐也就就是從從知識識P能推導導出知知識Q的一部部分知知識，，或者者說知知識Q只有一一部分分依賴賴于知知識P的。部部分依依賴性性（部部分可可推導導性））可以以由知知識的的正區(qū)區(qū)域來來定義義?，F(xiàn)現(xiàn)在我我們形形式地地定義義部分分依賴賴性。。定義12設K=(U,R)是一一個知知識庫庫﹐P,QR﹐我們們稱知識Q以依依賴度度k(0k1)依賴于于知識識P﹐記作作PkQ﹐當且且僅當當k=P(Q)=card(POSP(Q))/card(U)(6.8)(1)若k=1﹐﹐則稱稱知識識Q完全全依賴賴于知識P，P1Q也記成成PQ；(2)若0k1﹐則則稱知知識Q部分分依賴賴于知識P；(3)若k=0﹐﹐則稱稱知識識Q完全全獨立立于與知識識P。12/31/202244四、決決策策表的的約簡簡決策表表決策表表是一一類特特殊而而重要要的知知識表表達系系統(tǒng)，，它指指當滿滿足某某些條條件時時，決決策（（行為為）應應當怎怎樣進進行。。多數(shù)數(shù)決策策問題題都可可以用用決策策表形形式來來表示示，這這一工工具在在決策策應用用中起起著重重要的的作用用。決策表表可以以定義義如下下：S=(U,A)為一一信息息系統(tǒng)統(tǒng)，且且C,DA是兩個個屬性性子集集，分分別稱稱為條條件屬屬性和和決策策屬性性，且且CD=A，CD=，，則該該信息息系統(tǒng)統(tǒng)稱為為決策表表，記記作T=(U,A,C,D)或簡簡稱CD決策表表。關(guān)關(guān)系IND(C)和關(guān)關(guān)系IND(D)的等價價類分別別稱為條條件類和和決策類類。12/31/202245

身高性別視力錄取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1一一決策表表身高、性性別、視視力為條條件屬性性，錄取取為決策策屬性四、決決策表的的約簡12/31/202246決策規(guī)則則決策表中中的每一一行對應應諸如形式的決決策規(guī)則則，和分別稱為為決策規(guī)規(guī)則的前前驅(qū)和后后繼。當決策表表S中決決策規(guī)則則為真時，，我們說說該決策策規(guī)則是是S中一一致的，，否則說說該決策策規(guī)則是是S中不不一致的的。若決決策規(guī)則則是S中中一致的的，相同同的前驅(qū)驅(qū)必導致致相同的的后繼；；但同一一種后繼繼不一定定必需是是同一前前驅(qū)產(chǎn)生生的。如表1第第一行對對應決策策規(guī)則：：身高(高高)性別(男男)視力(差差)錄取取(否)12/31/202247決策表的的一致性性命題1當且僅當當CD，決策表T=(U,A,C,D)是一致的。。由命題1，很容易通通過計算條條件屬性和和決策屬性性間的依賴賴程度來檢檢查一致性性。當依賴賴程度等于于1時，我們說說決策表是是一致的，，否則不一一致。12/31/202248決策表的分分解命題2每個決策表表T=(U,A,C,D)都可以唯一一分解為兩兩個決策表表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é)果果不一致，，即依賴度度小于1，，則由命題題2可以將將表分解成成兩個子表表：其中一一個表完全全不一致，，依賴度為為0；另一一個表則完完全一致，，依賴度為為1。當然然，只有依依賴度大于于0且不等等于1時，，這一分解解才能進行行。12/31/202249表2不不一致決決策表a、b、c為條件屬屬性，d、、e為決策策屬性1、5產(chǎn)生生不一致Uabcde123456781022001112200111102210201220112111201101決策表的分分解12/31/202250表3完全全一致的決決策表Uabcde346720011110222201121112表4完完全不一致致的決策表表Uabcde125810220011121020101101決策表的分分解12/31/202251一致決策表的的約簡在我們制定決決策時是否需需要全部的條條件屬性，能能否進行決策策表的約簡。。約簡后的決決策表具有與與約簡前的決決策表相同的的功能，但是是約簡后的決決策表具有更更少的條件屬屬性。一致決策表的的約簡步驟如如下：(1)對決策表進行行條件屬性的的約簡，即從從決策表中消消去某一列；；(主要研究究點)(2)消去重復的行行；(3)消去去每一決策規(guī)規(guī)則中屬性的的冗余值。12/31/202252條件屬性的約約簡A.Skowron提出出了分明矩陣，，使核核與約約簡等等概念念的計計算較較為簡簡單，，主要要思想想：設S=(U,A)為一個個知識識表示示系統(tǒng)統(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ū)別別的所所有屬屬性的的集合合12/31/202253分明矩矩陣對對應的的核與與約簡簡核就可可以定定義為為分明明矩陣陣中所所有只只有一一個元元素的的矩陣陣項的的集合合，即即CORE(A)={a∈∈A：：cij=(a)，，對一一些i,j}相對于于集合合包含含關(guān)系系運算算而言言，若若屬性性集合合BA是滿足足下列列條件件B∩cij≠，對于于M(S)中的任任一非非空項項cij≠的一個個最小小屬性性子集集，則則稱屬屬性集集合BA是A的一一個約約簡。。換言之之，約約簡是是這樣樣的最最小屬屬性子子集，，它能能夠區(qū)區(qū)分用用整個個屬性性集合合A可可區(qū)分分的所所有對對象。。12/31/202254Skowron的約約簡方方法對于每每一個個分明明矩陣陣M(S)對應唯唯一的的分明明函數(shù)數(shù)fM(S)﹙DiscernibilityFunction﹚，它它的定定義如如下：：信息系系統(tǒng)S的分明明函數(shù)數(shù)fM(S)是一個個有m-元變量量a1,…,am(ai∈A，i=1,…,m)的布爾爾函數(shù)數(shù)，它它是∨∨cij的合取取，∨∨cij是矩陣陣項cij中的各各元素素的析析取，，1≤j<i≤n且cij≠Φ。。根據(jù)分分明函函數(shù)與與約簡簡的對對應關(guān)關(guān)系，，A.Skowron提出了了計算算信息息系統(tǒng)統(tǒng)S的約簡簡RED(S)的方法法：1）計算信信息系系統(tǒng)S的分明明矩陣陣M(S)2）計算與與分明明矩陣陣M(S)對應的的分明明函數(shù)數(shù)fM(S)3））計計算算分明明函數(shù)數(shù)fM(S)的最最小小析析取取范范式式，，其其中中每每個個析析取取分分量量對對應應一一個個約約簡簡12/31/202255為了了對對決決策策表表進進行行約約簡簡，，可可以以采采用用分明明矩陣陣的的方方法法對對條條件件屬屬性性進進行行約約簡簡，，對對決決策策屬屬性性相相同同的的個個體體不不予予比比較較。?？伎紤]慮下下面面的的決決策策表表5，，條條件件屬屬性性為為a,b,c,d，，決決策策屬屬性性為為eU/Aabcdeu110210u200121u320210u400222u511210表5決策策表表約約簡簡12/31/202256表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}決策表約約簡12/31/202257表6根據(jù)得到的兩兩個約簡，表表5可以簡化化為表6和表表7U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210表7決策表約簡12/31/202258求最優(yōu)或次優(yōu)優(yōu)約簡所有約簡的計計算是NP-hard問題，因此運運用啟發(fā)信息息來簡化計算算以找出最優(yōu)優(yōu)或次優(yōu)約簡簡是必要的?！，F(xiàn)在在求最優(yōu)優(yōu)或次優(yōu)約簡簡的算法一般般都使用核作作為計算約簡簡的出發(fā)點，，計算一個最最好的或者用用戶指定的最最小約簡。算算法將屬性的的重要性作為為啟發(fā)規(guī)則，，按照屬性的的重要度從大大到小逐個加加入屬性，直直到該集合是是一個約簡為為止。12/31/202259行的約簡對決策表中中的重復的的行要刪除除，因為它它們的條件件屬性和決決策屬性都都相同，都都表示同一一條決策規(guī)規(guī)則。另外外，決策規(guī)規(guī)則的列表表順序不是是本質(zhì)性的的，所以表表6、表7都可進行行約簡，如如表6可簡簡化為下表表：U\Aaceu1120u2011u3220u4022表812/31/202260屬性值的約約簡對于決策表表而言，屬屬性值的約約簡就是決決策規(guī)則的的約簡。決決策規(guī)則的的約簡是利利用決策邏邏輯消去每每個決策規(guī)規(guī)則的不必必要條件，它不是整整體上約簡簡屬性，而而是針對每每個決策規(guī)規(guī)則，去掉掉表達該規(guī)規(guī)則時的冗冗余屬性值值，即要計計算每條決決策規(guī)則的的核與約簡簡。12/31/202261非一一致致決決策策表表的的約約簡簡對于于一一致致的的決決策策表表比比較較容容易易處處理理，，在在進進行行約約簡簡時時，，只只要要判判斷斷去去掉掉某某個個屬屬性性或或某某個個屬屬性性值值時時是是否否會會導導致致不不一一致致規(guī)規(guī)則則的的產(chǎn)產(chǎn)生生。。而對對不不一一致致表表進進行行約約簡簡時時就就不不能能再再使使用用這這種種方方法法了了，，一一般般采采用用下下面面的的方方法法：：一一種種是是考考慮慮正正域域的的變變化化，，另另外外一一種種是是將將不不一一致致表表分分成成完完全全一一致致表表和和完完全全不不一一致致表表兩兩個個子子表表。非一一致致決決策策表表的的約約簡簡步步驟驟與與一一致致決決策策表表的的約約簡簡步步驟驟類類似似。。12/31/202262五、粗糙集集的擴展模型型基本粗糙集理理論的主要存存在的問題是是：1)對原始數(shù)據(jù)本本身的模糊性性缺乏相應的的處理能力；；2)對于粗糙集的的邊界區(qū)域的的刻畫過于簡簡單；3)粗粗糙集理論的的方法在可用用信息不完全全的情況下將將對象們歸類類于某一具體體的類，通常常分類是確定定的，但并未未提供數(shù)理統(tǒng)統(tǒng)計中所常用用的在一個給給定錯誤率的的條件下將盡盡可能多的對對象進行分類類的方法，而而實際中常常常遇到這類問問題。12/31/202263可變精度粗糙糙集模型W.Ziarko提出了了一種稱之為為可變精度粗粗糙集模型，，該模型給出出了錯誤率低低于預先給定定值的分類策策略，定義了了該精度下的的正區(qū)域、邊邊界區(qū)域和負負區(qū)域。下面面扼要地介紹紹其思想：一般地，集合合X包含于Y并未反映出集集合X的元素屬于集集合Y的“多少”。。為此，VPRS定義了它的量量度：C(X,Y)=1–card(XY)/card(X)當card(x)>0，C(X,Y)=0當card(x)=0。C(X,Y)表示把集集合X歸類于于集合Y的誤誤分類度，即即有C(X,Y)100%的元元素歸類錯誤誤。顯然，C(X,Y)=0時有有XY。如此，可可事先給定一一錯誤分類率率(0<0.5)，，基于上述定定義，我們有有XY，當且僅當當C(X,Y)。12/31/202264可變精精度粗粗糙集集模型型在此基基礎上上，設設U為論域域且R為U上的等等價關(guān)關(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–)；-負區(qū)域為：NEGRX=Xi(C(Xi,X)1–)。以此類推，，我們還可可以定義-依賴、-約簡等與傳統(tǒng)粗粗糙集模型型相對應的的概念。12/31/202265相似模型型在數(shù)據(jù)中中存在缺缺失的屬屬性值的的時候（（在數(shù)據(jù)據(jù)庫中很很普遍）），不分分明關(guān)系系或等價價關(guān)系無無法處理理這種情情形。為為擴展粗粗糙集的的能力，，有許多多作者提提出了用用相似關(guān)關(guān)系來代代替不分分明關(guān)系系作為粗粗糙集的的基礎。。在使用相相似關(guān)系系代替粗粗糙集的的不分明明關(guān)系后后，最重重要的變變化就是是相似類類不再形形成對集集合的劃劃分了，，它們之之間是相相互重疊疊的。類類似于等等價類，，可以定定義相似似集，即即所有和和某各元元素x在在屬性集集合B上上相似的的集合SIMb(x)。。值得注注意的是是SIMb(x)中中的元素素不一定定屬于同同一決策策類，因因此還還需要定定義相似似決策類類，即相相似集對對應的決決策類集集合。12/31/202266基于粗糙集的的非單調(diào)邏輯輯自粗糙集理論論提出以來，，粗糙集理論論的研究者都都很重視它的的邏輯研究，，試圖通過粗粗糙集建立粗粗糙邏輯，也也相應地發(fā)表表了一系列的的粗糙邏輯方方面的論文。12/31/202267與其其它它數(shù)數(shù)學學工工具具的的結(jié)結(jié)合合D.Dudios和H.Prade由此此提提出出了了RoughFuzzySet和FuzzyRoughSet的概概念念A.Skowron和J.Grazymala-Buss認為為，，粗粗糙糙集集理理論論可可以以看看作作證證據(jù)據(jù)理理論論的的基基礎礎。。并并在在粗粗糙糙集集理理論論的的框框架架上上重重新新解解釋釋了了證證據(jù)據(jù)理理論論的的基基本本概概念念，，特特別別是是用用上上近近似似和和下下近近似似的的術(shù)術(shù)語語解解釋釋了了信信念念(belief)和似似然然(plausibility)函數(shù)數(shù)，，進進而而討討論論了了兩兩者者之之間間的的互互補補問問題題。。12/31/202268六、、粗粗糙糙集集的的實實驗驗系系統(tǒng)統(tǒng)在過過去去幾幾年年中中，，建建立立了了不不少少基基于于粗粗糙糙集集的的KDD系系統(tǒng)統(tǒng)，，其其中中最最有有代代表表性性的的有有LERS、、ROSE、、KDD-R等等。。1．．LERSLERS(LearningfromexamplesbasedonRoughSet)系系統(tǒng)統(tǒng)是是美美國國Kansas大大學學開開發(fā)發(fā)的的基基于于粗粗糙糙集集的的實實例例學學習習系系統(tǒng)統(tǒng)。。它它是是用用CommonLisp在在VAX9000上上實實現(xiàn)現(xiàn)的的。。LERS已已經(jīng)經(jīng)為為NASA的的Johnson空空間間中中心心應應用用了了兩兩年年。。此此外外，，LERS還還被被廣廣泛泛地地用用于于環(huán)環(huán)境境保保護護、、氣氣候候研研究究和和醫(yī)醫(yī)療療研研究究12/31/202269六、、粗粗糙糙集集的的實實驗驗系系統(tǒng)統(tǒng)2．．ROSE波蘭蘭Poznan科科技技大大學學基基于于粗粗糙糙集集開開發(fā)發(fā)了了ROSE(RoughSetdataExplorer),用用于于決決策策分分析析。。它它是是RoughDas&RoughClass系系統(tǒng)統(tǒng)的的新新版版，，其其中中RoughDas執(zhí)執(zhí)行行信信息息系系統(tǒng)統(tǒng)數(shù)數(shù)據(jù)據(jù)分分析析任任務務，，RoughClass支支持持新新對對象象的的分分類類，，這這兩兩個個系系統(tǒng)統(tǒng)已已經(jīng)經(jīng)在在許許多多實實際際領領域域中中得得到到應應用用。。3．KDD—RKDD-R是由由加拿拿大的的Regina大學學開發(fā)發(fā)的基基于可可變精精度粗粗糙集集模型型，采采用知知識發(fā)發(fā)現(xiàn)的的決策策矩陣陣方法法開發(fā)發(fā)了KDD-R系統(tǒng)統(tǒng)，這這個系系統(tǒng)被被用來來對醫(yī)醫(yī)學數(shù)數(shù)據(jù)分分析，，以此此產(chǎn)生生癥狀狀與病病證之之間新新的聯(lián)聯(lián)系，，另外外它還還支持持電信信工業(yè)業(yè)的市市場研研究。。12/31/202270七、粒粒度計計算粒度計計算從從廣義義上來來說是是一種種看待待客觀觀世界界的世世界觀觀和方方法論論。粒度計計算的的基本本思想想就是使使用粒而不是是對象為計算算單元元，使使用粒粒、粒粒集以以及粒粒間關(guān)關(guān)系進進行計計算或或問題題求解解。12/31/202271粒度計計算1997年年LotfiA.Zadeh提提出了了粒度度的概概念，，他認認為在在人類類認知知中存存在三三種概概念：：粒度度，組組織與與因果果關(guān)系系。從從直觀觀的來來講，，?；婕凹暗綇膹恼w體到部部分的的分解解，而而組織織卻是是從部部分到到整體體的集集成，，而因因果關(guān)關(guān)系涉涉及原原因與與結(jié)果果之間間的聯(lián)聯(lián)系。。對一一個事事物的的?；褪鞘且钥煽煞直姹嫘?、、相似似性、、鄰近近性與與功能能性集集聚有有關(guān)的的事物物。粒度計計算是是信息息處理理的一一種新新的概概念和和計算算范式式，覆覆蓋了了所有有有關(guān)關(guān)粒度度的理理論、、方法法、技技術(shù)和和工具具的研研究，，主要要用于于處理理不確確定的的、模模糊的的、不不完整整的和和海量量的信信息。。粗略略地講講，一一方面面它是是模糊糊信息息粒度度理論論、粗粗糙集集理論論、商商空間間理論論、區(qū)區(qū)間計計算等等的超超集，，另一一方面面是粒粒度數(shù)數(shù)學的的子集集。具具體地地講，，凡是是在分分析問問題和和求解解問題題中，，應用用了分分組、、分類類、聚聚類以以及層層次化化手段段的一一切理理論與與方法法均屬屬于粒粒度計計算的的范疇疇。信信息粒粒度在在粒度度計算算，詞詞計算算，感感知計計算理理論和和精化化自然然語言言中都都有反反映12/31/202272粒度計算算的必要要性從哲學的的角度看看Yager和Filev指出出“人類類已經(jīng)形形成了世世界就是是一個粒粒度的觀觀點”以以及““人們觀觀察、度度量、定定義和推推理的實實體都是是粒度””。信息粒粒是一種種抽象，，它如同同數(shù)學中中的“點點”、““線”、、“面””一樣，，在人類類的思維維和活動動中占有有重要地地位。從人工智智能的角角度看張鈸院士士指出““人類智智能的公公認特點點，就是是人們能能從極不不相同的的粒度上上觀察和和分析同同一問題題。人們們不僅能能在不同同粒度的的世界上上進行問問題求解解，而且且能夠很很快地從從一個粒粒度世界界跳到另另一個粒粒度的世世界，往往返自如如，毫無無困難。。這種處處理不同同世界的的能力，，正是人人類問題題求解的的強有力力的表現(xiàn)現(xiàn)”。12/31/202273粒度計算算的必要要性從優(yōu)化論論的角度度來看粒度計算算的理論論與方法法在觀念念上突破破了傳統(tǒng)統(tǒng)優(yōu)化思思想的束束縛，不不再以數(shù)數(shù)學上的的精確解解為目標標，即：：需要的的是很好好地理解解和刻畫畫一個問問題，而而不是沉沉溺于那那些用處處不大的的細節(jié)信信息上。。粒度計計算的方方法不要要求目標標函數(shù)和和約束函函數(shù)的連連續(xù)性與與凸性，，甚至有有時連解解析表達達式都不不要求，，而且對對計算中中數(shù)據(jù)的的不確定定性也有有很強地地適應能能力，計計算速度度也快，，這些優(yōu)優(yōu)點使粒粒度計算算具有更更廣泛地地應用前前景，所所以，粒粒度計算算理論的的研究對對推動優(yōu)優(yōu)化領域域的發(fā)展展極其重重要。12/31/202274粒度計算的必必要性從問題求解的的角度看用粒度計算的的觀點來分析析解決問題顯顯得尤為重要要，這樣就不不用局限于具具體對象的細細節(jié)。除此之之外，將復雜雜問題劃分為為一系列更容容易管理和更更小的子任務務，可以降低低全局計算代代價。從應用技術(shù)的的角度看圖像處理、語語音與字符識識別等，是計計算機多媒體體的核心技術(shù)術(shù)。這些信息息處理質(zhì)量的的好壞直接依依賴于分割的的方法和技術(shù)術(shù)，而粒度計算算的研究或許許能夠解決這這一問題。12/31/202275粒度計算的基基本問題兩大問題粒的構(gòu)造：處理粒的形成成、表