一種知識分類能力的量化表示法

一種知識分類能力的量化表示法

1知識的信息熵與劃分粒度表示厚存儲理論由波蘭科學家提出。這是處理不完整、不準確、不確定知識的新數(shù)學工具。厚存儲理論認為，知識是宇宙的劃分，這種分工與等價比是一致的。因此，pawlak根據(jù)等價比和集算法提出了知識的代表示。在知識的代表示中，多個元素的描述和操作的直觀性較低，難以理解其本質，在這一點上，許多算法的效率也不高。在同一問題的不同知識表的算法復雜性方面，模型理論中的許多概念和操作的直觀性較低，難以理解其本質，在這一點上，許多算法的效率也不高?；诖?，不同知識表的算法的復雜性是不同的。在此基礎上，基于此，苗建謙從一個新的角度重新審視知識。他認為，知識可以看作是由宇宙中的一組組成的干矩陣特征的隨機變量?；谛畔⒄摚ㄗh使用信息熵來表達知識并表示知識。在知識信息的表達中，知識的信息熵值越高，給人的信息量越大，分類能力越強，反之亦然。這種表示方法從更深層次上揭示了知識的本質。然而，在本文中，我們提出了一種知識表示方法，即粒度表示法。本文直接從劃分出發(fā)來研究知識.我們知道,每個劃分是由若干個劃分塊組成,而每個劃分塊又是論域的一個子集,本文稱之為一個劃分粒.對一個劃分粒來說如何度量它的大小呢?自然會想到用集合基數(shù)來度量.由粗糙集理論知,一個劃分它包含的劃分粒越多,它的分類能力就越強(因為論域中元素個數(shù)是固定不變的).而粒度是對粒大小的一種平均度量,因此對一個劃分來說,可以使用其中劃分粒的平均大小來度量它的分類能力.本文將知識看成是定義在由它導出的劃分粒基數(shù)上的隨機變量,并定義了隨機變量的概率分布.基于此概率分布定義知識的劃分粒度,它是劃分粒大小的概率平均,因此建立知識與劃分粒度間的關系,從而可使用劃分粒度來定量表示知識的分類能力,本文稱之為知識的劃分粒度表示.與已有的代數(shù)、信息表示法相比,劃分粒度表示具有形式簡單、易于計算且易于理解等特點.2p中的不可區(qū)分關系為了證明知識的代數(shù)表示與劃分粒度表示是等價的,下面先簡要回顧一下粗糙集理論中主要概念的代數(shù)定義.設R是集合U上的一個等價關系,U/R表示R的所有等價類構成的集合,[x]R表示x∈U的R等價類.一個知識庫就是一個關系系統(tǒng)S=(U,A),其中,U是非空有限集,稱為論域;A是定義在U上的一簇等價關系.若P?A,且P≠?,則∩P(P中所有等價關系的交集)也是一個等價關系,稱為U上的不可區(qū)分關系,記為IND(P).不可區(qū)分關系將論域U劃分為若干個等價類,在同一等價類中的元素關于P是不可區(qū)分的,且有[x]ΙΝD(Ρ)=∩R∈Ρ[x]R={y|a(x)=a(y),?a∈Ρ}.[x]IND(P)=∩R∈P[x]R={y|a(x)=a(y),?a∈P}.定義1令K=(U,P)和K′=(U,Q)為兩個知識庫,若IND(P)=IND(Q),即U/P=U/Q,則稱K和K′(P和Q)是等價的,記作K?K′(P?Q).定義2設U是論域,P是定義在U上的一簇等價關系,R∈P,如果IND(P)=IND(P-{R}),則稱R為P中不必要的,否則稱R為P中必要的.定義3設U是論域,P是定義在U上的一簇等價關系,如果每個R∈P都為P中必要的,則稱P為獨立的,否則稱P為依賴的.定義4設U是論域,P是定義在U上的一簇等價關系,P中所有必要關系組成的集合稱為P的核,記作CORE(P).定義5設U是論域,P是定義在U上的一簇等價關系,且Q?P,如果滿足:1)Q是獨立的;2)IND(Q)=IND(P);則稱Q為P的一個約簡.3數(shù)學期望本文認為論域U上的任一等價關系(劃分)可以看成是定義在它導出的劃分?；鶖?shù)上的隨機變量,因此可定義隨機變量的概率分布及其數(shù)學期望.數(shù)學期望是隨機變量的重要數(shù)字特征,它表示隨機變量的平均值.在本文中,該值等于由等價關系導出的劃分粒的平均長度,本文稱之為劃分粒度,它可以度量知識的分類能力.3.1[py1循環(huán)—劃分粒度的定義下面給出隨機變量(劃分)的概率分布及劃分粒度的定義.定義6設U是論域,P是集合U上的等價關系,記P在U上導出的劃分為X,其中X={X1,X2,…,Xm},稱|Xi|(i=1,2,…,m)為劃分粒Xi的長度,符號|·|表示集合的基數(shù).定義7設U是論域,P、Q是U上的兩個等價關系,記P、Q在U上導出的劃分分別為X、Y.其中X={X1,X2,…,Xm},Y={Y1,Y2,…,Yn},則P、Q在其導出的劃分粒長度上的概率分布分別為(X;p)=[|X1||X2|?|Xm|p(X1)p(X2)?p(Xm)]p)=[|X1|p(X1)|X2|p(X2)??|Xm|p(Xm)],(Y;p)=[|Y1||Y2|?|Ym|p(Y1)p(Y2)?p(Ym)]p)=[|Y1|p(Y1)|Y2|p(Y2)??|Ym|p(Ym)],其中p(Xi)=|Xi||U|?i=1,2,?,m;p(Yj)=|Yj||U|?j=1,2,?,n.定義8設U是論域,P、Q是U上的兩個等價關系,記P、Q在U上導出的劃分分別為X、Y.其中X={X1,X2,…,Xm},Y={Y1,Y2,…,Yn},則P、Q的聯(lián)合概率分布為(XY;p)=[|X1∩Y1|?|Xi∩Yj|?|Xm∩Yn|p(X1Y1)?p(XiYj)?p(XmYn)]?其中p(XiYj)=|Xi∩Yj||U|,i=1,2,…,m;j=1,2,…,n.定義9設U是論域,P是U上的等價關系,記P在U上導出的劃分為X.其中X={X1,X2,…,Xm},稱E(Ρ)=m∑i=1|Xi|p(Xi)=m∑i=1|Xi||Xi||U|為知識P的劃分粒度.注1對于信息系統(tǒng)而言,它的任意非空屬性子集都可看成是論域上的等價關系,因此它會導出對論域的劃分,所以可按定義9定義其劃分粒度.而我們知道?不是論域上的等價關系,因而也就不能導出對論域的劃分,所以根據(jù)定義9,E(?)是沒定義的,為了定義的完備性和計算方便,特約定E(?)=|U|+1.因此定義9可修正為定義9′.定義9′設U是論域,P是U上的等價關系,記P在U上導出的劃分為X.其中X={X1,X2,…,Xm},稱E(Ρ)={m∑i=1|Xi|p(Xi)=m∑i=1|Xi||Xi||U|,Ρ≠?|U|+1,Ρ=?為知識P的劃分粒度.知識的劃分粒度是對知識導出的劃分中各劃分?！捌骄?概率平均)長度的一種度量.它的值越小,表明劃分粒的平均長度越短.因為論域中元素個數(shù)是固定不變的,所以劃分粒就越多,表明該知識能區(qū)分開的對象就越多,因此其分類能力就越強.相反,劃分粒度越大,其分類能力就越弱.因此可以用知識的劃分粒度來度量其分類能力.定義10稱E(Ρ∪Q)=∑i,j|Xi∩Yj|p(XiYj)=∑i,j|Xi∩Yj||Xi∩Yj||U|為知識P和Q的聯(lián)合劃分粒度.定義11設R是論域U上的等價關系簇,P,Q∈R是U上的等價關系,若對?u,v∈U,有uPv?uQv,則稱P與Q相等,記作P=Q.若對?u,v∈U,有uPv?uQv,則稱P比Q細,或Q比P粗,記作P?Q.若P?Q且P≠Q,則稱P比Q嚴格細,或Q比P嚴格粗,記作P?Q.3.2類目的性質性質1設U是論域,P是U上的一個等價關系,P在U上導出的劃分為X={X1,X2,…,Xm},則1≤|U|m≤E(Ρ)≤|U|,其中m為P在U上導出的劃分粒的個數(shù).證明記|U|=n,|Xi|=ki,i=1,2,…,m,顯然有m≤n,由定義9′有E(Ρ)=∑i|Xi|2|U|=∑ik2in,因為k1+k2+…+km=n,所以n2=(k1+k2+?+km)2=k21+k22+?+k2m+2∑s＜tkskt≤m(k21+k22+?+k2m),(1)所以∑ik2i≥n2m,所以E(Ρ)=∑ik2in≥nm=|U|m≥1,由式(1)知,當且僅當ki=kj(i,j=1,2,…,m)(即所有劃分粒的長度均相等)時,E(P)取到最小值n/m.特別地,當m=n(即每個劃分粒中均只有一個元素)時,E(P)取到最小值1.又因為k21+k22+…+k2m≤(k1+k2+…+km)2=n2,所以E(Ρ)=∑ik2in≤n=|U|.等號成立當且僅當存在某個ki=|U|=n,其余的kj(j≠i),j=1,2,…,m全為0.證畢.該性質表明,當知識的劃分粒度越小時,它的分類能力越強;相反當知識的劃分粒度越大時,它的分類能力越弱.特別當m=|U|時,即每個劃分粒中只包含一個對象,此時該知識能把所有對象徹底區(qū)分開,當然它的分類能力達到最強.這與我們的理解是一致的.性質2設U是論域,P、Q是U上的兩個等價關系,記P、Q在U上導出的劃分分別為X、Y,其中X={X1,X2,…,Xm},Y={X1,X2,…,Xm-1,X′m,X′m+1},且Xm=X′m∪X′m+1,X′m∩X′m+1=?,則E(Ρ)=E(Q)+2|X′m||X′m+1||U|.證明由定義9′有E(Q)=m-1∑i=1|Xi|2|U|+|X′m|2|U|+|X′m+1|2|U|,E(Ρ)=m-1∑i=1|Xi|2|U|+|Xm|2|U|.因為Xm=X′m∪X′m+1,且X′m∩X′m+1=?,所以|Xm|=|X′m|+|X′m+1|,所以|Xm|2=(|X′m|+|X′m+1|)2=|X′m|2+|X′m+1|2+2|X′m|·|X′m+1|,所以E(Ρ)=E(Q)+2|X′m||X′m+1||U|.證畢.該性質表明,隨著劃分粒的個數(shù)增多,知識的劃分粒度減小,相應地其分類能力增強.而且可由該性質增量式地計算知識的劃分粒度.性質3設U是論域,P、Q是U上的兩個等價關系,則有E(P∪Q)≤min(E(P),E(Q)).證明設P、Q在U上導出的劃分分別為X、Y.其中X={X1,X2,…,Xm},Y={Y1,Y2,…,Yn},P、Q的概率分布分別為(X;p)=[|X1||X2|?|Xm|p(X1)p(X2)?p(Xm)],(Y;p)=[|Y1||Y2|?|Ym|p(Y1)p(Y2)?p(Ym)],由定義10有E(Ρ∪Q)=∑i,j|Xi∩Yj|2|U|=∑i|Xi∩Y1|2+|Xi∩Y2|2+?+|Xi∩Yn||U|.而E(Ρ)=∑i|Xi|2|U|,對于每一個i,因為|Xi∩Y1|+|Xi∩Y2|+…+|Xi∩Yn|=|Xi|,所以(|Xi∩Y1|+|Xi∩Y2|+…+|Xi∩Yn|)2=|Xi|2,即|Xi∩Y1|2+|Xi∩Y2|2+?+|Xi∩Yn|2+2∑j＜k|Xi∩Yj||Xi∩Yk|=|Xi|2.因為2∑j＜k|Xi∩Yj||Xi∩Yk|≥0,所以|Xi∩Y1|2+|Xi∩Y2|2+…+|Xi∩Yn|2≤|Xi|2,所以∑i∑j|Xi∩Yj|2≤∑i|Xi|2,所以E(P∪Q)≤E(P).且易證等號成立當且僅當對?Xi∈X,存在唯一的Yj∈Y,使得Xi?Yj,即P?Q.同理可證E(P∪Q)≤E(Q),等號成立當且僅當Q?P.因此證明了E(P∪Q)≤min(E(P),E(Q)).證畢.該性質表明知識的分類能力是隨著知識的增加而增強的.性質4設P、Q是論域U上的兩個等價關系,若P?Q則E(P)≤E(Q);若P?Q則E(P)<E(Q).證明易由性質2、性質3得到.證畢.該性質表明,知識越細則它的劃分粒度越小;相反知識越粗,它的劃分粒度越大.這與人們的理解是相一致的.4各條件選取理論依據(jù)及上假設以上分析了粗糙集理論中知識與其劃分粒度間的關系,可以看出利用劃分粒度能定量表示知識的分類能力.就信息系統(tǒng)而言,下面證明知識約簡的代數(shù)表示與劃分粒度表示是等價的.定理1設U是論域,P、Q是U上的兩個等價關系簇,若IND(P)=IND(Q),則E(P)=E(Q).證明因為IND(P)=IND(Q),所以P、Q導出的劃分相同,所以在它們各自導出的劃分塊的基數(shù)上的概率分布相同,所以E(P)=E(Q).證畢.該定理表明兩個代數(shù)表示下等價的知識具有相同的分類能力.注2該定理的逆不一定成立.定理2設U是論域,P、Q是U上的兩個等價關系簇,且P?Q,若E(P)=E(Q),則IND(P)=IND(Q).證明記U/IND(P)={X1,X2,…,Xm},U/IND(Q-P)={Y1,Y2,…,Yn},根據(jù)定義知E(Ρ)=∑i|Xi|2|U|?E(Q)=E(Ρ∪(Q-Ρ))=∑i,j|Xi∩Yj|2|U|=∑i∑j|Xi∩Yj|2|U|?對每個i,因為|Xi|=∑j|Xi∩Yj|,所以|Xi|2=(∑j|Xi∩Yj|)2=∑j|Xi∩Yj|2+2∑j＜k|Xi∩Yj|?|Xi∩Yk|?因為2∑j＜k|Xi∩Yj|?|Xi∩Yk|≥0,所以|Xi|2≥∑j|Xi∩Yj|2,所以∑i|Xi|2≥∑i∑j|Xi∩Yj|2,即E(P)≥E(Q),因此E(Ρ)=E(Q)?|Xi|2=∑j|Xi∩Yj|2?∑j＜k|Xi∩Yj|?|Xi∩Yk|=0?對每個j＜k,|Xi∩Yj|?|Xi∩Yk|=0.因為Yj、Yk取遍所有的劃分塊,而n∪j=1Yj=U?Xi?U,所以不可能對每對j<k,都有|Xi∩Yj|=|Xi∩Yk|=0,因此存在j、k使得|Xi∩Yj|=0而|Xi∩Yk|≠0,對|Xi∩Yk|≠0而言,若Xi?Yk,則存在正整數(shù)l≠k,使得Xi∩Yl≠?,這是不可能的.因為如果這樣的話,將有|Xi∩Yl|·|Xi∩Yk|≠0,因此∑j＜k|Xi∩Yj|?|Xi∩Yk|≠0,這與E(P)=E(Q)矛盾,所以對每個Xi,必存在Yk,使得Xi?Yk.因此有IND(P)?IND(Q-P),所以P?Q-P,所以IND(P∪(Q-P))=IND(P),即IND(Q)=IND(P).證畢.該定理表明,當兩個知識間存在包含關系時,可由它們的劃分粒度相等得出它們在代數(shù)表示下是等價的.定理3設U是論域,P是U上的一個等價關系簇,關系R∈P在P中是不必要的(冗余的),當且僅當E(P-{R})-E(P)=0.證明必要性.設R∈P在P中是不必要的,則有IND(P-{R})=IND(P),由定理1知E(P-{R})-E(P)=0.充分性.設E(P-{R})-E(P)=0,因為P-{R}?P,所以由定理2知IND(P-{R})=IND(P),以R∈P在P中是不必要的.證畢.該定理表明,給屬性子集中添加一個不必要的屬性不會改變劃分粒度的大小.推論R∈P在P中是必要的當且僅當E(P-{R})-E(P)>0.定理4設U是論域,P是U上的一個等價關系簇,P是獨立的當且僅當對任意R∈P,都有E(P-{R})-E(P)>0.證明由獨立性的定義和上述推論可得此結論.定理5設U是論域,P是U上的一個等價關系簇,Q?P是P的一個約簡的充分必要條件為1)E(P)=E(Q),2)對任意的R∈Q,E(Q-{R})-E(Q)>0.證明Q?P是P的一個約簡的充分必要條件為IND(P)=IND(Q)且Q是獨立的.因