牛银菊

(东莞理工学院 计算机学院，广东东莞 523808)

Granular分析与决策规则算法

牛银菊

(东莞理工学院 计算机学院，广东东莞 523808)

基于论域划分的粒度模型，提出了粒度间的偏序关系和拟序关系以及粒度的“和”运算与“乘积”运算;运用粒度与二进制数串一一对应的基本思想，实现了上述序关系和运算的“可计算性”，以此为工具讨论了决策规则的提取问题。

粒度;二进制数串;可计算模型;决策规则

1996年，Zadeh提出“词计算 (Computing with Words，CW)理论”，通常认为，这标志着模糊粒度化理论的诞生［1］。波兰学者Pawlak 1982年提出了Rough集理论［2］，由于本质上表现了知识的颗粒性态，因而能够有效表达不确定和不精确信息，在知识获取和机器学习等重要领域获得成功［3］。粒度计算主要包括两方面内容，一是如何构建粒度，二是如何利用粒度进行相关计算。中国学者张钹和张铃早在1990年就指出：“人类智能的一个公认特点，就是人们能从极不相同的粒度上观察和分析同一问题。人们不仅能在不同的粒度世界上进行问题求解，而且能够很快地从一个粒度跳到另一个粒度的世界，往返自如，毫无困难”［4］。在实际应用中，由于观察问题的角度和获取对象特征信息的不同，可按问题需要，将复杂对象简练成若干个保留重要特征和性能的点，从而便于分析，这种点就是不同粒度世界的代表。系统中粒度世界的构建和粒度的计算，实际上就是在给定粒度基上的各种子集合之间的关系和转换，正是由于这一点，使得粒计算具有基本的理论意义和广泛的实用价值。

本文考虑论域U上由划分形成的粒度，建立了粒度间关系和粒度的“乘积”与“和”的计算模型，并且应用于决策规则的描述与获取。本文内容组织如下：第1节建立基于论域划分的粒度模型，讨论粒度间两种基本关系，即“对角线”关系与“匹配”关系;第2节讨论粒度的两种基本运算，即“和”运算与“乘积”运算;第3节应用粒关系和粒运算讨论了决策规则获取。

1 粒关系与粒运算

1.1 粒度与粒 (单元)

设2U为U的幂集，2U的不包含空集Ø的一个子集族称为U的一个划分，如果该子集族满足：①∪G=U;② X，Y∈G，如果X≠Y，则X∩Y=Ø。U上子集族G如果只满足“①”，则称G为U上的一个覆盖。

定义1 设U是给定论域，G是U上的一个划分，则称G为U上的一个粒度 (granulation)，粒度中的每个元素称为“粒”(Granule)或粒度单元。

1.2 粒关系

1.2.1 对角线关系

设G1和G2是论域U上的两个粒度，考察2G1和G2的笛卡尔乘积2G1×G2。

定义2 设Ω⊆2G1，R=Ω×G2。如果∀(a，b)∈R，都有a=b，则称R是2G1×G2的对角线关系。如果2G1×G2的对角线关系R存在，则说明∀g2∈G2，∀G1＇⊆G1，成立∪G1＇=g2。这在直观上表示G1比G2“细密”或G2比G1“粗糙”。

命题1 2G1×G2上对角线关系R存在⇔∀g2∈G2，∃G1＇⊆G1，成立∪G1＇=g2。

证明 只需要证明对角线关系R存在⇔∀g2∈G2，∃G1＇⊆G1，成立∪G1＇=g2

必要性 ∀g1∈G1，由G2是划分，∃g2∈G2，成立g1∩g2≠Ø。由题设，∃G1＇⊆G1，成立∪G1＇=g2，所以∃g1＇⊆G1＇，使得 g1∩g1＇≠Ø，所以g1=g1＇，即 g1⊆g2。必要性得证。

充分性∀g2∈G2∧∀x∈g2，由于G1都是划分，所以∃g1∈G1，成立x∈g1x。由于R是对角线关系，则∃g2＇∈G2，使得g1x⊆g2＇，即x∈g2∩g2＇≠Ø，所以 g2＇=g2，由此可知，g1x⊆g2。充分性得证。

定义3 设R=⊆2G1×G2。若∀(a，b)∈R，都有a=b，则称R是2G1×G2的部分对角线关系。

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

1.2.2 匹配关系

定义4 设R⊆G1×G2(⊆2G1×G2)，如果∀(a，b)∈R，都有a⊆b，则称R是G1×G2(⊆2G1×G2)的匹配关系。

定义5 设R⊆G1×G2，如果∃δ＞0，使得∀(g1，g2)∈R，成立|g1∩g2|/|g1|≥δ，则称R为 G1×G2上的δ-匹配关系。

设R是G1×G2上的δ-匹配关系，如果R满足对称性质，则称R是强δ-匹配关系。显然R是强δ -匹配关系⇔∀(g1，g2)∈R，成立|g1∩g2|≥δ|g1|∧|g1∩g2|≥δ|g2|。

1.3 粒度运算

1.3.1 和粒度与积粒度

定义6 (粒度的和)两个粒度G1和G2的和粒度G1+G2定义为在偏序关系“≤”之下的所有同时比G1和G2更粗糙的所有粒度集合的最小元。

定义7 (粒度的积)两个粒度G1和G2的积G1×G2定义为在偏序关系“≤”之下的所有同时比G1和G2更细密的所有粒度集合的最大元。

由定义6和定义7可以知道，和粒度是所有比G1和G2更粗糙粒度中的最“细密”粒度，因此可以看作是G1和G2的“最小公倍数”;积粒度是所有比G1和G2更细密粒度中的最“粗糙”粒度，因此可以看作是G1和G2的“最大公约数”。

1.3.2 和粒度计算

设有两个粒度 G={g1，g2，…，gm}和 G＇={g1＇，g2＇，…，gm＇}，则和粒度 G 和 G＇可以按照如下步骤求得：将G和G＇作为子集族进行合并，得到U上覆盖=∪{G，G＇}。对于X，Y∈F(G，G＇)，如果存在x1，x2，…，xk，并且 xj∩xj+1≠Ø(0≤j≤k-1)同时 X∩x1≠Ø，Y∩xk≠Ø，则称 X和 Y是连通的。可以验证，如此定义的连通关系是F(G，G＇)的等价关系。

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

1.3.3 积粒度计算

设有两个粒度 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 基于二进制的Granular计算

2.1 Granule的二进制数表示

设给定论域U，其中的元素可以建立起某种序关系。将U中的元素按给定“序”排好顺序。而G为U上给定的粒度。G中每个粒单元g对应一个长度为|U|的二进制数串。如果在每个粒单元g中出现U中某对象，由排好的顺序，在数串的相应位置上就用“1”表示，如果不出现，就在相应位置上用“0”表示。这样建立起来的粒单元与二进制数串关系是一一对应关系。

设符号“*”既可表示“0”，也可表示“1”，则称“*”为通配符。由三值字符集合{0，1，*}产生的0、1串称为二进制数串模式 (schema)，简称为数串模式。例如01010，*1*001和01＊＊＊00等都是数串模式。

给定一个数串g，将g中所有的“0”替换为“*”，得到的数串模式称为g对应的1-模式。本文后述的数串模式都是指“1-模式”。

定义8 给定一个数串模式s与一个特定的数串g，如果s中的“1”全部对应数串g中相应位置上的“1”，则称模式s与数串g匹配;如果只有s中的部分“1”对应数串g中相应位置上的“1”，则称s与g部份匹配;如果s中的没有“1”对应于数串g中相应位置上的“1”，则称s与g完全不匹配;而模式s中出现“*”，可以对应g中“0”也可对应“1”。

2.2 基于数串模式的粒计算

2.2.1 基于数串模式的粒度运算

给出粒度的二进制数串表示后，U上粒度集合中两个粒度G1和G2之间的运算可以表示如下：①G1×G2：∀g1∈G1，将g1对应数串与G2中的每一个数串分别进行数串的“合取”，运算结果就是G1×G2中一组乘积粒度单元，取尽G1中的元素，则可得到G1×G2中所有乘积粒度单元。

② G1+G2：∀g0∈G1，如果g21，g22，…，g2i∈G2，使得g0对应模式与g21，g22，…，g2i中每一个至少部分匹配，计算g1∪g21∪…∪g2i，即进行数串的“or”运算;

对于新数串g1∪g21∪…∪g2i，设G1中与其模式至少部分匹配的元素为g11，g12，…，g1k，计算(g0∪g21∪g22∪…∪g2i)∪(g11∪g12∪…∪g2i);

对于(g0∪g21∪g22∪…∪g2i)∪(g11∪g12∪…∪g2i)，在G1中在进行类似处理。经过上述有限步计算过程，就可得到g0所在的“连通”等价类，从而得到G1+G2中的元素。有g0的任意性，即可求出G1+G2中的所有元素。

2.2.2 基于数串模式的粒度关系

给出粒度的二进制数串表示后，U上粒度集合中两个粒度G1和G2之间的关系可以表示如下：① R是2G1×G2上对角线关系⇔∀(a，b)∈R，∪a产生的“1-模式”与b完全匹配。其中∪a表示a中各个二进制数串的“和”运算 (按“2．2．1”)，而a∈2G1;

② R是G1×G2上匹配关系⇔∀(g1，g2)∈R，成立g1产生的“1-模式”与g2相匹配。

3 粒分析与决策规则

3.1 决策规则及其度量

通常，一个信息系统S=(U，A)确定U上一个粒度集合，如果将属性集合A分为两个不交的集合C，D：A=C∪D，C∩D=Ø，得到的S=(U，C，D)称为决策系统或决策表。由C中粒度得到的乘积粒度称为S的条件粒度，同理得到D的乘积粒度称为S的决策粒度，分别记为GC和GD。

定义9 对于GC×GD中的元素(X，Y)，称其为一条(形式)决策规则。对于决策规则(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)表示规则(X，Y)在U中的强度;确定度Cer(X，Y)表示条件成立时，结论成立的概率;覆盖度Cov(X，Y)形式上表明了规则(X，Y)的“逆”规则(Y，X)的确定性。

按照文［4］中思想，Cer(X，Y)表示在“X”发生之下“Y”发生的概率，即Cov(X，Y)=p(Y|X);Cov(X，Y)表示在“Y”发生之下“X”发生的概率，即Cov(X，Y)=p(X|Y)。由此看来，Cer(X，Y)本质上反映了规则条件X对于结果Y的“覆盖”程度，是对规则(X，Y)的说明和解释;Cov(X，Y)本质上也表明了结果Y对于条件X的“覆盖”程度，在一定义意上对规则(X，Y)的说明和解释。

如果R是GC×Dd中匹配关系，则R就是确定性决策规则集合，其中的元素(X，Y)都是确定性规则;如果R是GC×GD中δ-匹配关系，则R中的元素(X，Y)都是确定性度不小于δ的决策规则;如果R是GC×GD中强δ-匹配关系，则R中元素(X，Y)可以相互覆盖或说明的程度都不小于“δ”。

一般而论，研究决策系统S=(U，C，D)，就是在给定确定度阈值δ情况下，找出所有确定度≥δ的决策规则集合，也就是说，要在GC×GD中发现“最大”的δ-匹配关系。

3.2 基于二进制数决策规则算法

设X→Y是决策系统S(U，C，D)上的决策规则，而X和Y分别是条件粒度GC和决策粒度GD中的粒度单元。如果X和Y对应的数串模式相匹配，则X→Y就是确定度为1的确定性规则，如果Y和X对应的数串模式相匹配，则X→Y就是覆盖度为1的完全可解释性规则。上述过程中如果只是部分匹配或不匹配，则可以根据事先给定的确定度和覆盖度阈值提取不确定和可以部分解释的决策规则。

具体计算步骤为：①计算条件乘积粒度和决策乘积粒度;② 计算所有可能的X和Y的组合形式(X，Y);③计算某种可能组合形式相应的各个参数 (支持度，可信度，确定度和覆盖度);④提取在给定信息系统中出现频率大于或等于给定阈值的决策规则X→Y。

对于组合形式(X，Y)来说，通常X∩Y的二进制表示中出现“1”的个数大于或等于给定阈值，则就可提取决策规则(X，Y)。由于满足这种条件的决策规则(X，Y)的个数不会超过条件粒度GC或决策粒度GD的基数，所以从粒度到决策规则集合可以看作一种约简。按照上述计算步骤，实际上可以将(X，Y)记为X∩Y，这样，每一条决策规则对应于乘积粒度GC×GD中的一个粒度单元，而这又相当于X和Y对应的二进制数做关于“AND”的Boole运算。

4 结语

本文基本内容在于建立了粒度间的偏序关系、拟序关系以及“和”运算与“乘积”运算，其意义在于这些关系与运算都是实际“可计算”的，而实现基本途径是建立粒度与二进制数串集合的对应。最后，我们将上述思想和技术应用于决策规则的提取。由于粒计算的根源来自于人的智能的模拟，所以如果有效地将其应用到计算智能例如MAS中协调与冲突分析将是我们进一步工作的方向。

［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

东莞市高等院校科研机构科技计划项目 (200910814044)。

牛银菊 (1965—)，女，甘肃甘谷人，副教授，硕士，主要从事数值计算与分析研究。