牛銀菊

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

Granular分析與決策規(guī)則算法

牛銀菊

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

基于論域劃分的粒度模型，提出了粒度間的偏序關(guān)系和擬序關(guān)系以及粒度的“和”運(yùn)算與“乘積”運(yùn)算;運(yùn)用粒度與二進(jìn)制數(shù)串一一對應(yīng)的基本思想，實(shí)現(xiàn)了上述序關(guān)系和運(yùn)算的“可計(jì)算性”，以此為工具討論了決策規(guī)則的提取問題。

粒度;二進(jìn)制數(shù)串;可計(jì)算模型;決策規(guī)則

1996年，Zadeh提出“詞計(jì)算 (Computing with Words，CW)理論”，通常認(rèn)為，這標(biāo)志著模糊粒度化理論的誕生［1］。波蘭學(xué)者Pawlak 1982年提出了Rough集理論［2］，由于本質(zhì)上表現(xiàn)了知識(shí)的顆粒性態(tài)，因而能夠有效表達(dá)不確定和不精確信息，在知識(shí)獲取和機(jī)器學(xué)習(xí)等重要領(lǐng)域獲得成功［3］。粒度計(jì)算主要包括兩方面內(nèi)容，一是如何構(gòu)建粒度，二是如何利用粒度進(jìn)行相關(guān)計(jì)算。中國學(xué)者張鈸和張鈴早在1990年就指出：“人類智能的一個(gè)公認(rèn)特點(diǎn)，就是人們能從極不相同的粒度上觀察和分析同一問題。人們不僅能在不同的粒度世界上進(jìn)行問題求解，而且能夠很快地從一個(gè)粒度跳到另一個(gè)粒度的世界，往返自如，毫無困難”［4］。在實(shí)際應(yīng)用中，由于觀察問題的角度和獲取對象特征信息的不同，可按問題需要，將復(fù)雜對象簡練成若干個(gè)保留重要特征和性能的點(diǎn)，從而便于分析，這種點(diǎn)就是不同粒度世界的代表。系統(tǒng)中粒度世界的構(gòu)建和粒度的計(jì)算，實(shí)際上就是在給定粒度基上的各種子集合之間的關(guān)系和轉(zhuǎn)換，正是由于這一點(diǎn)，使得粒計(jì)算具有基本的理論意義和廣泛的實(shí)用價(jià)值。

本文考慮論域U上由劃分形成的粒度，建立了粒度間關(guān)系和粒度的“乘積”與“和”的計(jì)算模型，并且應(yīng)用于決策規(guī)則的描述與獲取。本文內(nèi)容組織如下：第1節(jié)建立基于論域劃分的粒度模型，討論粒度間兩種基本關(guān)系，即“對角線”關(guān)系與“匹配”關(guān)系;第2節(jié)討論粒度的兩種基本運(yùn)算，即“和”運(yùn)算與“乘積”運(yùn)算;第3節(jié)應(yīng)用粒關(guān)系和粒運(yùn)算討論了決策規(guī)則獲取。

1 粒關(guān)系與粒運(yùn)算

1.1 粒度與粒 (單元)

設(shè)2U為U的冪集，2U的不包含空集?的一個(gè)子集族稱為U的一個(gè)劃分，如果該子集族滿足：①∪G=U;② X，Y∈G，如果X≠Y，則X∩Y=?。U上子集族G如果只滿足“①”，則稱G為U上的一個(gè)覆蓋。

定義1 設(shè)U是給定論域，G是U上的一個(gè)劃分，則稱G為U上的一個(gè)粒度 (granulation)，粒度中的每個(gè)元素稱為“粒”(Granule)或粒度單元。

1.2 粒關(guān)系

1.2.1 對角線關(guān)系

設(shè)G1和G2是論域U上的兩個(gè)粒度，考察2G1和G2的笛卡爾乘積2G1×G2。

定義2 設(shè)Ω?2G1，R=Ω×G2。如果?(a，b)∈R，都有a=b，則稱R是2G1×G2的對角線關(guān)系。如果2G1×G2的對角線關(guān)系R存在，則說明?g2∈G2，?G1＇?G1，成立∪G1＇=g2。這在直觀上表示G1比G2“細(xì)密”或G2比G1“粗糙”。

命題1 2G1×G2上對角線關(guān)系R存在??g2∈G2，?G1＇?G1，成立∪G1＇=g2。

證明 只需要證明對角線關(guān)系R存在??g2∈G2，?G1＇?G1，成立∪G1＇=g2

必要性 ?g1∈G1，由G2是劃分，?g2∈G2，成立g1∩g2≠?。由題設(shè)，?G1＇?G1，成立∪G1＇=g2，所以?g1＇?G1＇，使得 g1∩g1＇≠?，所以g1=g1＇，即 g1?g2。必要性得證。

充分性?g2∈G2∧?x∈g2，由于G1都是劃分，所以?g1∈G1，成立x∈g1x。由于R是對角線關(guān)系，則?g2＇∈G2，使得g1x?g2＇，即x∈g2∩g2＇≠?，所以 g2＇=g2，由此可知，g1x?g2。充分性得證。

定義3 設(shè)R=?2G1×G2。若?(a，b)∈R，都有a=b，則稱R是2G1×G2的部分對角線關(guān)系。

需要指出的是，由于G1和G2以及2G1和G2通常并不相同，所以2G1×G2中對角線關(guān)系甚至部分對角線關(guān)系可能都不存在;另外，對角線關(guān)系存在，部分對角線關(guān)系也存在，但反之不成立。

1.2.2 匹配關(guān)系

定義4 設(shè)R?G1×G2(?2G1×G2)，如果?(a，b)∈R，都有a?b，則稱R是G1×G2(?2G1×G2)的匹配關(guān)系。

定義5 設(shè)R?G1×G2，如果?δ＞0，使得?(g1，g2)∈R，成立|g1∩g2|/|g1|≥δ，則稱R為 G1×G2上的δ-匹配關(guān)系。

設(shè)R是G1×G2上的δ-匹配關(guān)系，如果R滿足對稱性質(zhì)，則稱R是強(qiáng)δ-匹配關(guān)系。顯然R是強(qiáng)δ -匹配關(guān)系??(g1，g2)∈R，成立|g1∩g2|≥δ|g1|∧|g1∩g2|≥δ|g2|。

1.3 粒度運(yùn)算

1.3.1 和粒度與積粒度

定義6 (粒度的和)兩個(gè)粒度G1和G2的和粒度G1+G2定義為在偏序關(guān)系“≤”之下的所有同時(shí)比G1和G2更粗糙的所有粒度集合的最小元。

定義7 (粒度的積)兩個(gè)粒度G1和G2的積G1×G2定義為在偏序關(guān)系“≤”之下的所有同時(shí)比G1和G2更細(xì)密的所有粒度集合的最大元。

由定義6和定義7可以知道，和粒度是所有比G1和G2更粗糙粒度中的最“細(xì)密”粒度，因此可以看作是G1和G2的“最小公倍數(shù)”;積粒度是所有比G1和G2更細(xì)密粒度中的最“粗糙”粒度，因此可以看作是G1和G2的“最大公約數(shù)”。

1.3.2 和粒度計(jì)算

設(shè)有兩個(gè)粒度 G={g1，g2，…，gm}和 G＇={g1＇，g2＇，…，gm＇}，則和粒度 G 和 G＇可以按照如下步驟求得：將G和G＇作為子集族進(jìn)行合并，得到U上覆蓋=∪{G，G＇}。對于X，Y∈F(G，G＇)，如果存在x1，x2，…，xk，并且 xj∩xj+1≠?(0≤j≤k-1)同時(shí) X∩x1≠?，Y∩xk≠?，則稱 X和 Y是連通的?？梢则?yàn)證，如此定義的連通關(guān)系是F(G，G＇)的等價(jià)關(guān)系。

在 F(G，G＇)求出所有的等價(jià)類 Li(1≤i≤P)，G+G＇={∪L1，∪L2，…，∪Lp}

1.3.3 積粒度計(jì)算

設(shè)有兩個(gè)粒度 G={g1，g2，…，gm}和 G＇={g1＇，g2＇，…，gm＇}，則積粒度 G × G＇={g1∩g1＇，g1∩g2＇，…，g1∩gn＇;g2∩g1＇，g2∩g2＇，…，g2∩gn＇;…;gm∩g1＇，gm∩g2＇，…，gm∩gn＇}。

2 基于二進(jìn)制的Granular計(jì)算

2.1 Granule的二進(jìn)制數(shù)表示

設(shè)給定論域U，其中的元素可以建立起某種序關(guān)系。將U中的元素按給定“序”排好順序。而G為U上給定的粒度。G中每個(gè)粒單元g對應(yīng)一個(gè)長度為|U|的二進(jìn)制數(shù)串。如果在每個(gè)粒單元g中出現(xiàn)U中某對象，由排好的順序，在數(shù)串的相應(yīng)位置上就用“1”表示，如果不出現(xiàn)，就在相應(yīng)位置上用“0”表示。這樣建立起來的粒單元與二進(jìn)制數(shù)串關(guān)系是一一對應(yīng)關(guān)系。

設(shè)符號(hào)“*”既可表示“0”，也可表示“1”，則稱“*”為通配符。由三值字符集合{0，1，*}產(chǎn)生的0、1串稱為二進(jìn)制數(shù)串模式 (schema)，簡稱為數(shù)串模式。例如01010，*1*001和01＊＊＊00等都是數(shù)串模式。

給定一個(gè)數(shù)串g，將g中所有的“0”替換為“*”，得到的數(shù)串模式稱為g對應(yīng)的1-模式。本文后述的數(shù)串模式都是指“1-模式”。

定義8 給定一個(gè)數(shù)串模式s與一個(gè)特定的數(shù)串g，如果s中的“1”全部對應(yīng)數(shù)串g中相應(yīng)位置上的“1”，則稱模式s與數(shù)串g匹配;如果只有s中的部分“1”對應(yīng)數(shù)串g中相應(yīng)位置上的“1”，則稱s與g部份匹配;如果s中的沒有“1”對應(yīng)于數(shù)串g中相應(yīng)位置上的“1”，則稱s與g完全不匹配;而模式s中出現(xiàn)“*”，可以對應(yīng)g中“0”也可對應(yīng)“1”。

2.2 基于數(shù)串模式的粒計(jì)算

2.2.1 基于數(shù)串模式的粒度運(yùn)算

給出粒度的二進(jìn)制數(shù)串表示后，U上粒度集合中兩個(gè)粒度G1和G2之間的運(yùn)算可以表示如下：①G1×G2：?g1∈G1，將g1對應(yīng)數(shù)串與G2中的每一個(gè)數(shù)串分別進(jìn)行數(shù)串的“合取”，運(yùn)算結(jié)果就是G1×G2中一組乘積粒度單元，取盡G1中的元素，則可得到G1×G2中所有乘積粒度單元。

② G1+G2：?g0∈G1，如果g21，g22，…，g2i∈G2，使得g0對應(yīng)模式與g21，g22，…，g2i中每一個(gè)至少部分匹配，計(jì)算g1∪g21∪…∪g2i，即進(jìn)行數(shù)串的“or”運(yùn)算;

對于新數(shù)串g1∪g21∪…∪g2i，設(shè)G1中與其模式至少部分匹配的元素為g11，g12，…，g1k，計(jì)算(g0∪g21∪g22∪…∪g2i)∪(g11∪g12∪…∪g2i);

對于(g0∪g21∪g22∪…∪g2i)∪(g11∪g12∪…∪g2i)，在G1中在進(jìn)行類似處理。經(jīng)過上述有限步計(jì)算過程，就可得到g0所在的“連通”等價(jià)類，從而得到G1+G2中的元素。有g(shù)0的任意性，即可求出G1+G2中的所有元素。

2.2.2 基于數(shù)串模式的粒度關(guān)系

給出粒度的二進(jìn)制數(shù)串表示后，U上粒度集合中兩個(gè)粒度G1和G2之間的關(guān)系可以表示如下：① R是2G1×G2上對角線關(guān)系??(a，b)∈R，∪a產(chǎn)生的“1-模式”與b完全匹配。其中∪a表示a中各個(gè)二進(jìn)制數(shù)串的“和”運(yùn)算 (按“2．2．1”)，而a∈2G1;

② R是G1×G2上匹配關(guān)系??(g1，g2)∈R，成立g1產(chǎn)生的“1-模式”與g2相匹配。

3 粒分析與決策規(guī)則

3.1 決策規(guī)則及其度量

通常，一個(gè)信息系統(tǒng)S=(U，A)確定U上一個(gè)粒度集合，如果將屬性集合A分為兩個(gè)不交的集合C，D：A=C∪D，C∩D=?，得到的S=(U，C，D)稱為決策系統(tǒng)或決策表。由C中粒度得到的乘積粒度稱為S的條件粒度，同理得到D的乘積粒度稱為S的決策粒度，分別記為GC和GD。

定義9 對于GC×GD中的元素(X，Y)，稱其為一條(形式)決策規(guī)則。對于決策規(guī)則(X，Y)定義：

① (X，Y)的支持度為 Sup(X，Y)=|X∩Y|;

② (X，Y)的可信度為 Rel(X，Y)=Sup(X，Y)/|U|;

③ (X，Y)的確定度為 Cer(X，Y)=Sup(X，Y)/|X|=|U|Rel(X，Y)/|X|;

④ (X，Y)的覆蓋度為 Cov(X，Y)=Sup(X，Y)/|Y|=|U|Rel(X，Y)/|Y|。

由上述可知，0 ≤Rel(X，Y)，Cer(X，Y)，Cov(X，Y)≤1。

可信度Rel(X，Y)表示規(guī)則(X，Y)在U中的強(qiáng)度;確定度Cer(X，Y)表示條件成立時(shí)，結(jié)論成立的概率;覆蓋度Cov(X，Y)形式上表明了規(guī)則(X，Y)的“逆”規(guī)則(Y，X)的確定性。

按照文［4］中思想，Cer(X，Y)表示在“X”發(fā)生之下“Y”發(fā)生的概率，即Cov(X，Y)=p(Y|X);Cov(X，Y)表示在“Y”發(fā)生之下“X”發(fā)生的概率，即Cov(X，Y)=p(X|Y)。由此看來，Cer(X，Y)本質(zhì)上反映了規(guī)則條件X對于結(jié)果Y的“覆蓋”程度，是對規(guī)則(X，Y)的說明和解釋;Cov(X，Y)本質(zhì)上也表明了結(jié)果Y對于條件X的“覆蓋”程度，在一定義意上對規(guī)則(X，Y)的說明和解釋。

如果R是GC×Dd中匹配關(guān)系，則R就是確定性決策規(guī)則集合，其中的元素(X，Y)都是確定性規(guī)則;如果R是GC×GD中δ-匹配關(guān)系，則R中的元素(X，Y)都是確定性度不小于δ的決策規(guī)則;如果R是GC×GD中強(qiáng)δ-匹配關(guān)系，則R中元素(X，Y)可以相互覆蓋或說明的程度都不小于“δ”。

一般而論，研究決策系統(tǒng)S=(U，C，D)，就是在給定確定度閾值δ情況下，找出所有確定度≥δ的決策規(guī)則集合，也就是說，要在GC×GD中發(fā)現(xiàn)“最大”的δ-匹配關(guān)系。

3.2 基于二進(jìn)制數(shù)決策規(guī)則算法

設(shè)X→Y是決策系統(tǒng)S(U，C，D)上的決策規(guī)則，而X和Y分別是條件粒度GC和決策粒度GD中的粒度單元。如果X和Y對應(yīng)的數(shù)串模式相匹配，則X→Y就是確定度為1的確定性規(guī)則，如果Y和X對應(yīng)的數(shù)串模式相匹配，則X→Y就是覆蓋度為1的完全可解釋性規(guī)則。上述過程中如果只是部分匹配或不匹配，則可以根據(jù)事先給定的確定度和覆蓋度閾值提取不確定和可以部分解釋的決策規(guī)則。

具體計(jì)算步驟為：①計(jì)算條件乘積粒度和決策乘積粒度;② 計(jì)算所有可能的X和Y的組合形式(X，Y);③計(jì)算某種可能組合形式相應(yīng)的各個(gè)參數(shù) (支持度，可信度，確定度和覆蓋度);④提取在給定信息系統(tǒng)中出現(xiàn)頻率大于或等于給定閾值的決策規(guī)則X→Y。

對于組合形式(X，Y)來說，通常X∩Y的二進(jìn)制表示中出現(xiàn)“1”的個(gè)數(shù)大于或等于給定閾值，則就可提取決策規(guī)則(X，Y)。由于滿足這種條件的決策規(guī)則(X，Y)的個(gè)數(shù)不會(huì)超過條件粒度GC或決策粒度GD的基數(shù)，所以從粒度到?jīng)Q策規(guī)則集合可以看作一種約簡。按照上述計(jì)算步驟，實(shí)際上可以將(X，Y)記為X∩Y，這樣，每一條決策規(guī)則對應(yīng)于乘積粒度GC×GD中的一個(gè)粒度單元，而這又相當(dāng)于X和Y對應(yīng)的二進(jìn)制數(shù)做關(guān)于“AND”的Boole運(yùn)算。

4 結(jié)語

本文基本內(nèi)容在于建立了粒度間的偏序關(guān)系、擬序關(guān)系以及“和”運(yùn)算與“乘積”運(yùn)算，其意義在于這些關(guān)系與運(yùn)算都是實(shí)際“可計(jì)算”的，而實(shí)現(xiàn)基本途徑是建立粒度與二進(jìn)制數(shù)串集合的對應(yīng)。最后，我們將上述思想和技術(shù)應(yīng)用于決策規(guī)則的提取。由于粒計(jì)算的根源來自于人的智能的模擬，所以如果有效地將其應(yīng)用到計(jì)算智能例如MAS中協(xié)調(diào)與沖突分析將是我們進(jìn)一步工作的方向。

［1］Zadeh L．The key roles of information granulation and fuzzy logic in human reasoning［C］//In：1996 IEEE Int Conf Fuzzy Systems，1996，1：8-11．

［2］Pawlak Z．Rough sets［J］．Communications of the ACM，1995，38(11)：89-85．

［3］Yao Y Y．Rough sets，neighborhood systems，Granular Computing［C］//Proceeding of 1999 IEEE Canadian Conference of Electrical and Computer Engineering Show Conference Center Edmonton．Canada：Albeta，1999，1553-1557．

［4］Zhang Bo，Zhang Lin．Problem solving theory and application［M］．Beijing：Publish House of Tsinghua University，1990．

Granular Analysis and Arithmetic Decision Roles

NIU Yin-ju
(College of Computer，Dongguan University of Technology，Dongguan 523808，China)

Based on the model of division in universe，the partial order relation and preorder relation among granules are discussed and the operation on sum and product of granules are studied．According to the basic thing about the binary expression of granules，the arithmetic on the order relation and operation which can be applied to the discovery of decision roles is obtained．

granule;binary expression;calculability model;decision roles

O141．4

A

1009-0312(2012)01-0006-04

2011-03-31

東莞市高等院?？蒲袡C(jī)構(gòu)科技計(jì)劃項(xiàng)目 (200910814044)。

牛銀菊 (1965—)，女，甘肅甘谷人，副教授，碩士，主要從事數(shù)值計(jì)算與分析研究。