aai09粗糙集高級人工智能史忠植

1、第九章 知識發(fā)現(xiàn) 粗糙集 史忠植 中科院計算所2/21/20221內(nèi)容一、概述二、知識分類三、知識的約簡四、決策表的約簡五、粗糙集的擴展模型六、粗糙集的實驗系統(tǒng)2/21/20222一、 概述 現(xiàn)實生活中有許多含糊現(xiàn)象并不能簡單地用真、假值來表示如何表示和處理這些現(xiàn)象就成為一個研究領(lǐng)域。早在1904年謂詞邏輯的創(chuàng)始人G.Frege就提出了含糊(Vague)一詞，他把它歸結(jié)到邊界線上，也就是說在全域上存在一些個體既不能在其某個子集上分類，也不能在該子集的補集上分類。 2/21/20223模糊集 1965年，Zadeh提出了模糊集，不少理論計算機科學家和邏輯學家試圖通過這一理論解決G.Frege的含

2、糊概念，但模糊集理論采用隸屬度函數(shù)來處理模糊性，而基本的隸屬度是憑經(jīng)驗或者由領(lǐng)域?qū)＜医o出，所以具有相當?shù)闹饔^性。 2/21/20224粗糙集的提出 20世紀80年代初，波蘭的Pawlak針對G.Frege的邊界線區(qū)域思想提出了粗糙集（Rough Set）他把那些無法確認的個體都歸屬于邊界線區(qū)域，而這種邊界線區(qū)域被定義為上近似集和下近似集之差集。由于它有確定的數(shù)學公式描述，完全由數(shù)據(jù)決定，所以更有客觀性 。2/21/20225粗糙集的研究 粗糙集理論的主要優(yōu)勢之一是它不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息。自提出以來，許多計算機科學家和數(shù)學家對粗糙集理論及其應(yīng)用進行了堅持不懈的研究，使之在理論上日

3、趨完善，特別是由于20世紀80年代末和90年代初在知識發(fā)現(xiàn)等領(lǐng)域得到了成功的應(yīng)用而越來越受到國際上的廣泛關(guān)注。2/21/20226粗糙集的研究 1991年波蘭Pawlak教授的第一本關(guān)于粗糙集的專著Rough Sets：Theoretical Aspects of Reasoning about Data 和1992年R.Slowinski主編的關(guān)于粗糙集應(yīng)用及其與相關(guān)方法比較研究的論文集的出版，推動了國際上對粗糙集理論與應(yīng)用的深入研究。1992年在波蘭Kiekrz召開了第1屆國際粗糙集討論會。從此每年召開一次與粗糙集理論為主題的國際研討會。 2/21/20227史忠植. 知識發(fā)現(xiàn). 北京:

4、清華大學出版社, 2002劉清. Rough Set及Rough推理. 北京: 科學出版社, 2001張文修等. Rough Set理論與方法. 北京: 科學出版社, 2001王國胤, Rough Set理論與知識獲取. 西安: 西安交通大學出版社, 2001曾黃麟. 粗集理論及其應(yīng)用(修訂版). 重慶: 重慶大學出版社, 1998 2/21/202282001年5月在重慶召開了“第1屆中國Rough集與軟計算學術(shù)研討會”，邀請了創(chuàng)始人Z. Pawlak教授做大會報告；2002年10月在蘇州 第2屆2003年5月在重慶 第3屆，同時舉辦“第9屆粗糙集、模糊集、數(shù)據(jù)挖掘和粒度-軟計算的國際會議”

5、 因非典推遲到10月中科院計算所、中科院自動化所、北京工業(yè)大學、西安交通大學、重慶郵電學院、山西大學、合肥工業(yè)大學、上海大學、南昌大學 2/21/20229二、 知識分類 基本粗糙集理論認為知識就是人類和其他物種所固有的分類能力。例如，在現(xiàn)實世界中關(guān)于環(huán)境的知識主要表明了生物根據(jù)其生存觀來對各種各樣的情形進行分類區(qū)別的能力。每種生物根據(jù)其傳感器信號形成復雜的分類模式，就是這種生物的基本機制。分類是推理、學習與決策中的關(guān)鍵問題。因此，粗糙集理論假定知識是一種對對象進行分類的能力。這里的“對象”是指我們所能言及的任何事物，比如實物、狀態(tài)、抽象概念、過程和時刻等等。即知識必須與具體或抽象世界的特定部

6、分相關(guān)的各種分類模式聯(lián)系在一起，這種特定部分稱之為所討論的全域全域或論域論域(universeuniverse)。對于全域及知識的特性并沒有任何特別假設(shè)。事實上，知識構(gòu)成了某一感興趣領(lǐng)域中各種分類模式的一個族集(family)，這個族集提供了關(guān)于現(xiàn)實的顯事實，以及能夠從這些顯事實中推導出隱事實的推理能力。2/21/202210二、 知識分類 為數(shù)學處理方便起見，在下面的定義中用等價關(guān)系來代替分類。一個近似空間近似空間(approximate space)（或知識庫知識庫）定義為一個關(guān)系系統(tǒng)（或二元組） K K=(U,R R) 其中U（為空集）是一個被稱為全域或論域(universe)的所有要討

7、論的個體的集合，R R是U上等價關(guān)系的一個族集。 2/21/202211二、 知識分類 設(shè)P PR R，且P P ，P P中所有等價關(guān)系的交集稱為P P上的一種難區(qū)分關(guān)系(indiscernbility relation)（或稱難區(qū)分關(guān)系），記作IND(P P)，即 xIND(p)= I xR RP 注意，IND(P P)也是等價關(guān)系且是唯一的。2/21/202212二、 知識分類 給定近似空間K K=(U, R R)，子集XU稱為U上的一個概念概念(concept)，形式上，空集也視為一個概念；非空子族集P PR R所產(chǎn)生的不分明關(guān)系IND(P P)的所有等價類關(guān)系的集合即U/IND(P P

8、)，稱為基本知識基本知識(basic knowledge)，相應(yīng)的等價類稱為基本概念基本概念(basic concept)；特別地，若關(guān)系QR R，則關(guān)系Q就稱為初等知識初等知識(elementary knowledge)，相應(yīng)的等價類就稱為初等概念初等概念(elementary concept)。 一般用大寫字母P,Q,R等表示一個關(guān)系，用大寫黑體字母P P,Q Q,R R等表示關(guān)系的族集；xR或R(x)表示關(guān)系R中包含元素xU的概念或等價類。為了簡便起見，有時用P P代替IND(P P)。 根據(jù)上述定義可知，概念即對象的集合，概念的族集（分類）就是U上的知識，U上分類的族集可以認為是U上的

9、一個知識庫，或說知識庫即是分類方法的集合。2/21/202213二、 知識分類 粗糙集理論與傳統(tǒng)的集合理論有著相似之處，但是它們的粗糙集理論與傳統(tǒng)的集合理論有著相似之處，但是它們的出發(fā)點完全不同。傳統(tǒng)集合論認為，一個集合完全是由其出發(fā)點完全不同。傳統(tǒng)集合論認為，一個集合完全是由其元素所決定，一個元素要么屬于這個集合，要么不屬于這元素所決定，一個元素要么屬于這個集合，要么不屬于這個集合，即它的隸屬函數(shù)個集合，即它的隸屬函數(shù) X X( (x x) ) 0,10,1。模糊集合對此做了。模糊集合對此做了拓廣，它給成員賦予一個隸屬度，即拓廣，它給成員賦予一個隸屬度，即 X X( (x x) ) 0,10

10、,1，使得模，使得模糊集合能夠處理一定的模糊和不確定數(shù)據(jù)，但是其模糊隸糊集合能夠處理一定的模糊和不確定數(shù)據(jù)，但是其模糊隸屬度的確定往往具有人為因素，這給其應(yīng)用帶來了一定的屬度的確定往往具有人為因素，這給其應(yīng)用帶來了一定的不便。而且，傳統(tǒng)集合論和模糊集合論都是把隸屬關(guān)系作不便。而且，傳統(tǒng)集合論和模糊集合論都是把隸屬關(guān)系作為原始概念來處理，集合的并和交就建立在其元素的隸屬為原始概念來處理，集合的并和交就建立在其元素的隸屬度度maxmax和和minmin操作上，因此其隸屬度必須事先給定（傳統(tǒng)集操作上，因此其隸屬度必須事先給定（傳統(tǒng)集合默認隸屬度為合默認隸屬度為1 1或或0 0）。在粗糙集中，隸屬關(guān)系

11、不再是一）。在粗糙集中，隸屬關(guān)系不再是一個原始概念，因此無需人為給元素指定一個隸屬度，從而個原始概念，因此無需人為給元素指定一個隸屬度，從而避免了主觀因素的影響。避免了主觀因素的影響。2/21/202214Information Systems/Tables IS is a pair (U, A) U is a non-empty finite set of objects. A is a non-empty finite set of attributes such that for every is called the value set of a.aVUa:. AaaV Age LEM

12、Sx 16-30 50 x2 16-30 0 x3 31-45 1-25x4 31-45 1-25x5 46-60 26-49x6 16-30 26-49x7 46-60 26-492/21/202215Decision Systems/Tables DS: is the decision attribute (instead of one we can consider more decision attributes). The elements of A are called the condition attributes. Age LEMS Walkx 16-30 50 yes x2

13、 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no),(dAUTAd 2/21/202216Issues in the Decision Table The same or indiscernible objects may be represented several times. Some of the attributes may be superfluous.2/21/202217難區(qū)分性Indiscernibility The equival

14、ence relation A binary relation which is reflexive (xRx for any object x) , symmetric (if xRy then yRx), and transitive (if xRy and yRz then xRz). The equivalence class of an element consists of all objects such that xRy.XXRXxXyRx2/21/202218難區(qū)分性Indiscernibility (2) Let IS = (U, A) be an information

15、system, then with any there is an associated equivalence relation: where is called the B-indiscernibility relation. If then objects x and x are indiscernible from each other by attributes from B. The equivalence classes of the B-indiscernibility relation are denoted by AB )()(,|) ,()(2xaxaBaUxxBINDI

16、S)(BINDIS),() ,(BINDxxIS.Bx2/21/202219難區(qū)分性實例 Indiscernibility The non-empty subsets of the condition attributes are 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. Age LEMS Walkx 16-30 50 yes x2 16-30 0 no x3 3

17、1-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no2/21/202220概念的邊界 知識的粒度性是造成使用已有知識不能精確地表示知識的粒度性是造成使用已有知識不能精確地表示某些概念的原因。這就產(chǎn)生了所謂的關(guān)于不精確的某些概念的原因。這就產(chǎn)生了所謂的關(guān)于不精確的“邊界邊界”思想。著名哲學家思想。著名哲學家FregeFrege認為認為“概念必須概念必須有明確的邊界。沒有明確邊界的概念，將對應(yīng)于一有明確的邊界。沒有明確邊界的概念，將對應(yīng)于一個在周圍沒有明確界線的區(qū)域個在周圍沒有明確界線的區(qū)

18、域”。粗糙集理論中的。粗糙集理論中的模糊性就是一種基于邊界的概念，即一個不精確的模糊性就是一種基于邊界的概念，即一個不精確的概念具有模糊的不可被明確劃分的邊界。為刻畫模概念具有模糊的不可被明確劃分的邊界。為刻畫模糊性，每個不精確概念由一對稱為上近似與下近似糊性，每個不精確概念由一對稱為上近似與下近似的精確概念來表示，它們可用隸屬函數(shù)定義的精確概念來表示，它們可用隸屬函數(shù)定義2/21/202221粗糙集的基本定義 知識的分類觀點 粗糙集理論假定知識是一種對對象進行分類的能力。而知識必須與具體或抽象世界的特定部分相關(guān)的各種分類模式聯(lián)系在一起，這種特定部分稱之為所討論的全域全域或論域論域(unive

19、rseuniverse)。為數(shù)學處理方便起見，在下面的定義中用等價關(guān)系來代替分類。2/21/202222粗糙集的基本定義定義定義1 1 一個近似空間近似空間(approximate space)(或知知識庫識庫)定義為一個關(guān)系系統(tǒng)(或二元組)K K=(U, R R)，其中U(為空集)是一個被稱為全域或論域(universe)的所有要討論的個體的集合，R R是U上等價關(guān)系的一個族集。定義定義2 2 設(shè)P PR R，且P P ，P P中所有等價關(guān)系的交集稱為P P上的一種不分明關(guān)系(indiscernbility relation)（或稱不可區(qū)分關(guān)系），記作IND(P P)P PP PRR)(xx

20、IND2/21/202223粗糙集的基本定義 定義定義3 3 給定近似空間K K=(U, R R)，子集XU稱為U上的一個概念概念(concept)，形式上，空集也視為一個概念；非空子族集P PR R所產(chǎn)生的不分明關(guān)系IND(P P)的所有等價類關(guān)系的集合即U/IND(P P)，稱為基本基本知識知識(basic knowledge)，相應(yīng)的等價類稱為基本基本概念概念(basic concept)；特別地，若關(guān)系QR R，則關(guān)系Q就稱為初等知識初等知識(elementary knowledge)，相應(yīng)的等價類就稱為初等概念初等概念(elementary concept)。2/21/202224上

21、近似、下近似和邊界區(qū)域定義定義5:X的下近似：R*(X)=x:(xU) (xRX ) X的上近似：R*(X)=x:(xU) (xRX )X的邊界區(qū)域：BNR(X)=R*(X)R*(X) 若BNR(X) ，則集合X就是一個粗糙概念。下近似包含了所有使用知識R可確切分類到X的元素，上近似則包含了所有那些可能是屬于X的元素。概念的邊界區(qū)域由不能肯定分類到這個概念或其補集中的所有元素組成。POSR(X)=R*(X)稱為集合X的R-正區(qū)域正區(qū)域，NEGR(X)=UR*(X)稱為集合X的R-反區(qū)域反區(qū)域。 2/21/202225Lower & Upper Approximations (2) :/

22、XYRUYXR :/XYRUYXRLower Approximation:Upper Approximation:2/21/202226新型的隸屬關(guān)系 傳統(tǒng)集合論中，一個元素的隸屬函數(shù)X(x)0,1。而粗糙集理論中，X(x)0,1 定義定義4 4 設(shè)XU且xU,集合X的粗糙隸屬函數(shù)粗糙隸屬函數(shù)(rough membership function) 定義為 )()()(xRcardxRXcardxRX 其中R是不分明關(guān)系，R(x)=xR=y:(yU)(yRx)(xRX=1當且僅當xRX )(xRX0當且僅當xRX )(xRX=0當且僅當xRX= 2/21/202227隸屬關(guān)系根據(jù)上面的定義，可以

23、得到以下性質(zhì)根據(jù)上面的定義，可以得到以下性質(zhì)(1 1）( (x x) )=1=1當且僅當當且僅當 x x R R X X；(2 2）( (x x) )00當且僅當當且僅當 x x R R X X ；(3 3）( (x x) )=0=0當且僅當當且僅當 x x R R X=X=。顯然有顯然有( (x x) ) 0,10,1。我們可以看到，這里的隸屬關(guān)系。我們可以看到，這里的隸屬關(guān)系是根據(jù)已有的分類知識客觀計算出來的，可以被解是根據(jù)已有的分類知識客觀計算出來的，可以被解釋為一種條件概率，能夠從全域上的個體加以計算，釋為一種條件概率，能夠從全域上的個體加以計算，而不是主觀給定的。而不是主觀給定的。2

24、/21/202228集近似Set Approximation Let T = (U, A) and let and We can approximate X using only the information contained in B by constructing the B-lower and B-upper approximations of X, denoted and respectively, where AB .UX XBXB, |XxxXBB. |XxxXBB2/21/202229集近似Set Approximation (2) B-boundary region of

25、X, consists of those objects that we cannot decisively classify into X in B. B-outside region of X, consists of those objects that can be with certainty classified as not belonging to X. A set is said to be rough if its boundary region is non-empty, otherwise the set is crisp. ,)(XBXBXBNB,XBU 2/21/2

26、02230集近似實例 Set Approximation Let W = x | Walk(x) = yes. The decision class, Walk, is rough since the boundary region is not empty. Age LEMS Walkx 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no.7, 5, 2,4, 3)(,6, 4, 3, 1,6, 1xxxWAUxxWBN

27、xxxxWAxxWAA2/21/202231集近似實例 Set Approximation (2)yesyes/nonox1,x6x3,x4x2, x5,x7AWWA2/21/202232UsetU/RR : subset of attributesXRXXRLower & 集近似圖示ns2/21/202233Lower & Upper Approximations(3) X1 = u | Flu(u) = yes = u2, u3, u6, u7 RX1 = u2, u3 = u2, u3, u6, u7, u8, u5X2 = u | Flu(u) = no = u1, u

28、4, u5, u8 RX2 = u1, u4 = u1, u4, u5, u8, u7, u6X1RX2RUHeadacheTemp.FluU1YesNormalNoU2YesHighYesU3YesVery-highYesU4NoNormalNoU5N N No o oH H Hi i ig g gh h hN N No o oU6NoVery-highYesU7N N No o oH H Hi i ig g gh h hY Y Ye e es s sU8NoVery-highNoThe indiscernibility classes defined by R = Headache, Te

29、mp. are u1, u2, u3, u4, u5, u7, u6, u8.2/21/202234Lower & 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, u6X1RX2Ru1u4u3X1X2

30、u5u7u2u6u82/21/202235例例1 1： 設(shè)有一知識庫K=U,p,q,r其中U=x1,x2,x3,x4,x5,x6,x7,x8且U/p=x1,x4,x5,x2,x8,x3,x6,x7U/q=x1,x3,x5,x6,x2,x4 ,x7,x8 U/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 對于U上的子集X1=x1,x4,x7可得到P* X1=x4x7=x4 ,x7P* X1=x1 ,x5x4x7=x1 ,x4 ,x5 ,x72/2

31、1/202236近似度Accuracy of Approximation where |X| denotes the cardinality of Obviously If X is crisp with respect to B. If X is rough with respect to B.| )(| )(|)(XBXBXB.X. 10B, 1)(XB, 1)(XB2/21/202237近似性質(zhì)Properties of ApproximationsYXYBXBYXBYBXBYXBUUBUB BBXBXXB)()()()()()()()(,)()()()()(YBXB)()(YBXBim

32、pliesand2/21/202238近似性質(zhì)Properties of Approximations (2)()()()()()()()()()()()()()()()(XBXBBXBBXBXBBXBBXBXBXBXBYBXBYXBYBXBYXBwhere -X denotes U - X.2/21/202239三、 知識的約簡 一般約簡 定義定義6 6 設(shè)R R是等價關(guān)系的一個族集，且設(shè)RR R。若IND(R R)=IND(R RR)，則稱關(guān)系R在族集R R之中是可省可省的(dispensable)否則就是不可省不可省的。若族集R R中的每個關(guān)系R都是不可省的則稱族集R R是獨立的獨立的(

33、independent)否則就是依賴的依賴的或非獨立非獨立的。 定義定義7 7 若Q QP P是獨立的并且IND(Q Q)=IND(P P)則稱Q Q是關(guān)系族集P P的一個約簡約簡(reduct) 。在族集P P中所有不可省的關(guān)系的集合稱為P P的核核(core) 以CORE(P P)來表示。 顯然，族集P P有多個約簡（約簡的不唯一性）。 定理定理1 1 族集P P的核等于P P的所有約簡的交集。即CORE(P P)=RED(P P) 2/21/202240例例2 2：取前面的例1若P=p,q,r則IND(P)=x1 ,x5,x2 ,x8,x3,x4,x6,x7IND(P-p)=x1 ,x5

34、,x2 ,x7 ,x8,x3,x4,x6IND(P)所以p是不可省的同理可得q、r是可省的。這樣由p,q,r三個等價關(guān)系組成的集合和p,q、p,r定義了相同的不分明關(guān)系。又IND(p,q)IND(p) IND(pq)IND(q)則p,q和p, r就是P的約簡而且p是P的核也就是說p是絕對不能省的 2/21/202241相對約簡定義定義8 8 設(shè)P P和Q Q是全域U上的等價關(guān)系的族集，所謂族集Q Q的P-P-正區(qū)域正區(qū)域(P-positive region of Q Q)，記作POSP P(Q Q)= = Q/UXP P*(X) 族集Q Q的P-P-正區(qū)域正區(qū)域是全域U的所有那些使用分類U/P

35、 P所表達的知識，能夠正確地分類于U/Q Q的等價類之中的對象的集合。定義定義9 9 設(shè)P P和Q Q是全域U上的等價關(guān)系的族集，RP P。若POSIND(P P)(IND(Q Q)= =POSIND(P P-R)(IND(Q Q) 則稱關(guān)系R在族集P P中是Q-Q-可省的可省的否則稱為Q-Q-不可省的不可省的如果在族集P P中的每個關(guān)系R都是Q Q-不可省的則稱P P關(guān)于Q Q是獨立的獨立的否則就稱為是依賴的依賴的。 2/21/202242相對約簡定義定義10 SP稱為P的Q-約簡約簡(Q-reduct)當且僅當S是P的Q-獨立的子族集且POSS(Q)=POSP(Q)；族集P中的所有Q-不可

36、省的初等關(guān)系的集合稱為族集P的Q-核核(Q-core)記作COREQ(P) 。下面的定理是定理定理1的拓廣。定理定理2 族集P的Q-核等于族集P的所有Q-約簡的交集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集P的所有Q-約簡的族集。2/21/202243知識的依賴性知識的依賴性可形式定義如下：定義定義11 設(shè)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

37、)=IND(Q)；3) 知識P和知識Q是獨立的獨立的，當且僅當PQ且QP均不成立，記作PQ。2/21/202244知識的依賴性依賴性也可以是部分成立的也就是從知識P能推導出知識Q的一部分知識，或者說知識Q只有一部分依賴于知識P的。部分依賴性（部分可推導性）可以由知識的正區(qū)域來定義?，F(xiàn)在我們形式地定義部分依賴性。定義定義12 設(shè)K=(U, R)是一個知識庫P, QR我們稱知識知識Q以依以依賴度賴度k(0 k 1)依賴于知識依賴于知識P記作PkQ當且僅當k=P(Q)=card(POSP(Q)/card(U) (6.8)(1) 若k=1則稱知識Q完全依賴于完全依賴于知識P，P1Q也記成PQ；(2)

38、若0k1則稱知識Q部分依賴于部分依賴于知識P；(3) 若k=0則稱知識Q完全獨立于完全獨立于與知識P。2/21/202245四、 決策表的約簡 決策表 決策表是一類特殊而重要的知識表達系統(tǒng)，它指當滿足某些條件時，決策（行為）應(yīng)當怎樣進行。多數(shù)決策問題都可以用決策表形式來表示，這一工具在決策應(yīng)用中起著重要的作用。 決策表可以定義如下： S=(U, A)為一信息系統(tǒng)，且C, DA是兩個屬性子集，分別稱為條件屬性和決策屬性，且CD=A，CD=，則該信息系統(tǒng)稱為決策表，記作T=(U, A, C, D)或簡稱CD決策表。關(guān)系IND(C)和關(guān)系IND(D)的等價類分別稱為條件類和決策類。 2/21/202

39、246 身高性別視力錄取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1 一決策表 身高、性別、視力為條件屬性，錄取為決策屬性 2/21/202247決策規(guī)則 決策表中的每一行對應(yīng)諸如 形式的決策規(guī)則，和分別稱為決策規(guī)則的前驅(qū)和后繼 。當決策表S中決策規(guī)則為真時，我們說該決策規(guī)則是S中一致的，否則說該決策規(guī)則是S中不一致的。若決策規(guī)則是S中一致的，相同的前驅(qū)必導致相同的后繼；但同一種后繼不一定必需是同一前驅(qū)產(chǎn)生的。 如表1第一行對應(yīng)決策規(guī)則： 身高(高)性別(男)視力(差) 錄取(否) 2/21/202248決策表的一致性命題命題1 1當且僅當 CD，決策表T=

40、(U, A, C, D)是一致的。由命題1，很容易通過計算條件屬性和決策屬性間的依賴程度來檢查一致性。當依賴程度等于1時，我們說決策表是一致的，否則不一致。2/21/202249決策表的分解 命題命題2 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可見，假設(shè)我們已計算出條件屬性的依賴度，若表的結(jié)果不一致，即依賴度小于1，則由命題2可以將表分解成兩個子表：其中一個表完全不一致，依賴度為0；另一

41、個表則完全一致，依賴度為1。當然，只有依賴度大于0且不等于1時，這一分解才能進行。2/21/202250表2 不一致決策表 a、b、c為條件屬性，d、e為決策屬性 1、5產(chǎn)生不一致Ua b c d e123456781 0 2 2 00 1 1 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 12/21/202251表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

42、2 0 10 1 1 0 12/21/202252一致決策表的約簡在我們制定決策時是否需要全部的條件屬性，能否進行決策表的約簡。約簡后的決策表具有與約簡前的決策表相同的功能，但是約簡后的決策表具有更少的條件屬性。一致決策表的約簡步驟如下：(1) 對決策表進行條件屬性的約簡，即從決策表中消去某一列；(主要研究點)(2) 消去重復的行；(3) 消去每一決策規(guī)則中屬性的冗余值。 2/21/202253條件屬性的約簡A.Skowron提出了差別矩陣，使核與約簡等概念的計算較為簡單，主要思想：設(shè)S=(U,A)為一個知識表示系統(tǒng)，其中U =x1,x2,xn，xi為所討論的個體，i=1,2,n，A =a1,

43、a2,am，aj為個體所具有的屬性，j=1,2,m。知識表達系統(tǒng)S的差別矩陣M(S)=cijnn，其中矩陣項定義如下： cij=aA：a(xi)a(xj)，i,j=1,2,n因此cij是個體xi與xj有區(qū)別的所有屬性的集合2/21/202254差別矩陣對應(yīng)的核與約簡核就可以定義為差別矩陣中所有只有一個元素的矩陣項的集合，即 CORE(A)=aA：cij=(a)，對一些i,j 相對于集合包含關(guān)系運算而言，若屬性集合BA是滿足下列條件 Bcij，對于M(S)中的任一非空項cij的一個最小屬性子集，則稱屬性集合BA是A的一個約簡。換言之，約簡是這樣的最小屬性子集，它能夠區(qū)分用整個屬性集合A可區(qū)分的所有對象。 2/21/202255Skowron的約簡方法對于每一個差別矩陣M(S)對應(yīng)唯一的差別函數(shù)fM(S)Discernibility Function，它的定義如下：信息系統(tǒng)S的差別函數(shù)fM(S)是一個有m-元變量a1, am(aiA，i=1,m)的布爾函數(shù)，它是cij的合取，cij是矩陣項cij中的各元素的析取，1j0， C(X, Y)=0 當card(x)=0。C(X, Y)表示把集合X歸類于集合Y的誤分類度，即有C(X, Y)100%的元素歸類錯誤。顯然，C(X, Y)=0時有XY。如此，可事先給定一錯誤分類率(00.5