一种基于粗糙集理论的规则核值的扩展算法

□肖志军， 蒙峭缘，陈寿辉

（1.玉林师范学院 计算机科学与工程学院，广西 玉林 537000；2.玉林市新桥高级中学，广西 玉林 537000）

一种基于粗糙集理论的规则核值的扩展算法

□肖志军1， 蒙峭缘1，陈寿辉2

（1.玉林师范学院 计算机科学与工程学院，广西 玉林 537000；2.玉林市新桥高级中学，广西 玉林 537000）

应用粗糙集的理论，提出一种基于规则核值的扩展算法。利用该算法对从信息数据进行约简，并求出规则的核值. 在规则核值的基础上对规则进行扩展，从而去除规则中的冗余条件，得到更加简化的规则.

粗糙集；约简；决策规则

粗糙集（Rough Sets）理论是波兰数学家Z.Pawlak在1982年提出的一种分析与处理模糊、不确定和不完整信息的数学工具[1,2].粗糙集理论引入了代数的等价类的概念，通过对一组关于一些现实的大量数据信息的分类，在保持分类能力不变的前提下，进行知识的约简，从而发现推理知识和分辨系统中的某些特点、过程、对象等.粗糙集理论不仅为信息科学和认知科学提供了新的科学理论和研究方法，也为信息处理提供了有效的处理技术[2,,3].

在基于粗糙集理论的研究中，属性约简和规则提取是其重要的研究内容.尽管现在已经证明求属性和属性值的约简以及最优约简是一个NP-Hard问题[4]，然而人们还是在努力找出更好的属性约简的方法.目前，国内外的学者对于属性约简一般采用启发式算法找出更优的属性约简，主要的方法有：基于正区域的属性约简[5]、基于信息熵的属性约简[6,7]、基于区分矩阵的属性约简[8,9].

本文主要根据粗糙集理论，借鉴启发式算法的优点，提出一种基于规则核值的扩展算法，它能对决策属性进行约简，并利用约简属性的核值进行扩展，从而抽取出简化的决策规则，以辅助决策.

1 粗糙集理论的基本概念

根据本文对粗糙集理论的应用，这里先介绍粗糙集理论的一些基本概念[3,10-12].

1.1 信息系统与决策表

粗糙集理论把客观世界或对象抽象为一个信息系统(Information System)[3].设S=＜U, A,V, f ＞为一信息系统，其中：U是对象(或事例)的有限非空集合，U={x1, x2, …, xn}，即S的论域；A是所研究对象的全部属性的有限非空集合，A={a1, a2, …, am}；V是所有属性的值域集，V={V1, V2, …, Vm}，其中Vi是属性ai的值域；f :U×A→V是一个信息函数(Information function)，即f(xi, aj)∈Vj，它指定U中每一对象x的属性值.信息系统的数据以关系表的形式表示，如果属性集A还分为条件属性集C和决策属性集D，这时的信息系统称为决策表(Decision Table)，常记为S=＜ U, C∪D, V, f ＞.

1.2 不可分辨关系

对于信息系统S中，对于任一个属性子集P∪C∪D，则P上的不可分辨关系（Indiscernibility Relation），记为ind(P)={(xi,xj)∈U×U|∀a∈P,f(xi,a)=f(xj,a)}.ind(P)是一个等价关系，U/ind(P)（简记为U/P）表示由等价关系ind(P)划分的所有等价类.

1.3 正域

令P和Q为U中的等价关系，Q的P的正域记为posp(Q)，即：其中

1.4 知识的相对约简和相对核

令P和Q为等价关系族，R∈P，如果

则称R为P中Q不必要；否则R为P中Q必要的.（posind(P)(ind(Q))可简记为posp(Q)）

如果P中的每个R都为Q必要的，则称P为Q独立的.

设T⊆P，T为P的Q约简当且仅当T是P的Q独立子族且posT(Q)=posp(Q).P的Q约简简称为相对约简，所有P的Q约简构成的集合记为redQ(P)． P中所有Q必要的初等关系构成的集合称为P的Q核，简称为相对核，记为coreQP，且有coreQ(P)=∩redQ(P).

1.5 属性的依赖度和重要性

设S=＜ U, C∪D, V, f ＞是一个决策表，属性集P，Q⊆C∪D，属性集Q对P的依赖度用γP(Q)表示，定义为：γP(Q)=|posp(Q)|/|U|.

在决策表中，不同的属性可能具有不同的重要性，属性子集C'⊆C关于D的重要性定义为：σCD(C')-γC(D)-γC-C'(D).

1.6 决策规则

设S=＜ U, C∪D, V, f ＞是一个决策表，令Xi和Yj分别代表U/C与U/D中的各个等价类，des(Xi)表示对等价类Xi的描述，即等价类Xi对于各条件属性值的特定取值；des(Yj)表示对等价类Yj的描述，即等价类Yj对于各决策属性值的特定取值.

决策规则定义如下：

1.7 区分矩阵

设S=＜U, C∪D, V, f ＞是一个决策表，决策表S的区分矩阵[3,10](Discernibility Matrix )是一个n×n矩阵，其任一元素为：

2 基于规则核值扩展算法的规则抽取

利用信息数据进行决策分析是数据挖掘的重要部分，通过决策分析可以挖掘出潜藏在数据内部的信息，得到辅助决策的规则.

对于信息数据的决策分析，分为属性约简和规则抽取两大步骤.

2.1 属性约简

在进行决策分析时，选取需要进行决策的属性（在此称为主属性）及对决策结果可能会有影响的属性进行分析.属性对于决策结果是否真的有影响或影响是多大，通过直接的观察，我们很难进行判断，因此，需要对这些属性进行筛选，剔除一些对评价结果没有影响或影响较小的属性，从而为规则抽取进行数据的准备.

具体的属性约简的实现方法如下：

算法1

Input: 决策表S=＜ U, C∪D ＞；

Output: 约简后的新的决策表S’=＜ U, red(C)∪D ＞；

步骤：

Step 1：构造以下集合或元素：

（1）U={r1, r2, …, rn}表示所有记录；

（2）C={a1, a2, …, am}表示参与决策分析的属性集；

（3）D={d}表示评定结果属性集；

（4）构建一个n×n的区分矩阵M，矩阵元素的初值均为空；

（5）c[i][j]用于存储区分矩阵中的元素M[i][j]内包含的属性个数，初值为0；

（6）T用于计算区分矩阵的极小析取范式，初值为1；

Step 2：划分等价类 U/ C，U/D，得到posC(D)，ind(D)；

Step 3：对于集合U中的任意两个ri和rj（i≠j，且i＜j,i,j=1,2,…,n）， 如果满足：

则将对应的ri.ak与rj.ak进行比较（这里ri.ak表示记录ri中的ak属性，k=1,2,…,m），如果ri.ak≠rj.ak，则将属性ak存入M[i][j]，统计M[i][j]中包含的属性个数并存入c[i][j]；

Step 4：取出c[i][j]的值为1且M[i][j]的值不为空的M[i][j]与区分矩阵中的其它非空元素进行比较，将含有M[i][j]中的属性的元素值都设为Φ；

Step 5：将区分矩阵中的非空元素进行以下运算：

Step 6：取出T中的每一个合取式，它们都是属性集C的约简.

Step 7：如有多个约简，按以下方式进行选择：

（1）如只有一个约简含有要进行决策分析的主属性，则就取该约简为属性集C的约简；

（2）如果有多个约简含有要进行决策分析的主属性，根据约简的重要性，取重要性最大的约简为属性集C的约简；

（3）如果约简中不包含要进行决策分析的主属性，则将主属性添加到约简中.

2.2 规则抽取

通过属性的约简，可以将决策表中对决策分析不必要的属性省略掉，从而实现决策表的约简.但是，属性约简只是在一定程度上去掉了决策表中的冗余属性，并没有充分去掉决策表中的冗余信息，这就需要对表中的属性值进行处理，约去多余的属性值，从而得到更加简约的决策信息.这里提出了一个基于规则核值的扩展算法.

抽取规则的具体实现方法如下：

算法2

Input:约简后的新的决策表S’=＜ U, red(C)∪D ＞；

Output:决策规则集；

步骤：

Step 1: 合并S’ 中相同的记录，得到新的记录集U；

Step 2: 构造以下集合或元素：

（1）U={r1, r2, …, rn}表示所有记录；

（2）red(C)=C={a1, a2, …, am}表示参与决策分析的属性集；

（3）D={d}表示综合评定结果属性集；

（4）构建一个n×(m+1)的决策矩阵M，并导入决策表中的数据；

Step 3: 划分等价类 U/ D={Y1,Y2,…,Yk}，U/ (C-{ai})={X1, X2, …, Xk}，其中i=1,2,…,m；

Step 4: 计算posC-{ai}(D)，i=1,2,…,m；

Step 5: 分别取出posC-{ai}(D)，i=1,2,…,m中的元素值r，将决策矩阵中的M[r][i]设为空，则这时的决策矩阵M中的元素是各条规则的核值；

Step 6: 构建core[i]用于保存U/D中一个等价类Yi中各条规则的核值，这里i=1,2,…,k；

Step 7: 对于U/D中的任意一个等价类Yi(i=1, 2, …, k)

如果|Yi|=1：

如果core[i]=Φ，则合取Yi中的规则的各属性值，作为关于等价类Yi一条规则；否则，合取Yi中规则的核值，作为关于等价类Yi一条规则；

如果|Yi| ＞ 1，取出决策矩阵M中对应规则的核值存入core[i]：

如果C-core[i]=Φ ，则Yi中各条规则的核值，分别作为关于等价类Yi一条规则；否则，对分别取出core[i]中每条规则的核值存入cr,对C-cr中的每一个属性{a}，计算Yi/(cr+{a})；

如果|Yi/(cr+{a})|＞1，则cr-{a}，合取cr中的规则核值，作为关于等价类Yi一条规则；否则，cr中继续添加C-cr中属性，直到C-cr=Φ，则合取cr中的规则核值，作为关于等价类Yi一条规则；

Step 8: 合并重复的规则，并析取等价类Yi(i=1,2,…,k)中的每条规则，作为关于等价类Yi一条规则，从而得到S的决策规则集.

这里提出的基于规则核值的扩展算法，直接利用规则的核值扩展后对相应的等价类的影响来对规则进行约简，从而能很好地剔除了冗余地规则属性值，得到了基于规则核值的极小化规则.

3 实例与实验分析

3.1 实例分析

为了说明本算法，这里通过两组测试数据说明其运算过程，并分别对基于规则核值的扩展算法的决策有效性及与性能进行比较测试.

3.1.1 决策有效性测试

算法的决策有效性测试数据如表3.1所示，其中条件属性为C={a1,a2,a3,a4}，决策属性为D={d}.

表3.1 算法的决策有效性测试数据

对表3.1中的数据进行数据约简，得到C的D约简是{a1,a2,a4}.

得到约简后的决策表如表3.2所示.

表3.2 约简后的等价决策数据

对表3.2中的数据进行属性值约简，根据矩阵M[n][k]中的值，可以推导出如表3.3所示的各规则的核值.

表3.3 各规则的核值

利用表3.3中的规则核值进行规则抽取，得到以下规则：

采用文献[3]中提出决策算法的极小化方法，可以得到规则：

或

对于测试数据和得到的测试结果的分析如下：

（1）选择的测试数据，基本包含了数据约简和规则抽取的各种情况，能对算法进行较全面的测试.

（2）数据约简得到的约简属性，与应用文献[3]中提出的区分矩阵和区分函数方法以及不相容算法，这两种方法直接推导出的约简结果是一致的.

（3）属性值约简得到的各规则核值，与采用文献[3]中提出的决策规则的约简算法，直接推导出的规则核值的结果是一致的.

（4）利用规则核值抽取出的规则，是采用文献[3]中提出的决策算法的极小化方法推导出的两组极小化规则中的更简洁的一组.

综合上述分析，应用决策分析的功能进行数据分析是可行的，得到的结果是正确的.

3.1.2 与其它算法的比较测试

决策算法比较测试数据如表3.4所示，其中条件属性为C={a1,a2,a3}，决策属性为D={d}.

表3.4 决策算法比较测试数据

对表3.4中的数据进行数据约简，得到C的D约简是{a1, a2 }或{a1, a3 }.选择约简{a1, a2}进行决策.得到约简后的决策表如表3.5所示.

表3.5 约简后的等价决策数据

对表3.5中的数据进行属性值约简，根据矩阵M[n][k]中的值，可以推导出如表3.6所示的各规则的核值.

表3.6 各规则的核值

利用表3.6中的规则核值进行规则抽取，得到以下规则：

应用文献[9]提出的值约简算法得到的规则是：

对于得到的测试结果的分析如下：

（1）对于d=2的规则，应用基于规则核值算法得到的结果比利用文献[7]提出的值约简算法得到的规则更简约.

（2）对于d=1的规则，两种算法得到规则是一样的.

（3）因为a1=2是d=2的规则核心条件，而a3是冗余属性，所以对于d=3的规则，a1=2和a3=3是冗余条件.应用基于规则核值算法都将其去除.

3.2 实验分析

为了进一步验证该算法，我们从UCI机器学习数据库中选择4个决策表为测试数据，对3个约简算法进行测试.

这里利用波兰华沙大学与挪威科技大学联合开发的Rosetta软件中的Boolean reasoning algorithm对非离散的决策表进行离散化，将离散化后的决策表分别应用Rosetta中的Johnson Reducer、文献[9]提出的值约简算法以及本文提出的算法进行属性约简和规则抽取，测试结果如3.7所示.

通过实验，利用本文算法约简后得到的属性除Iris Plants Database决策表外，除余3个决策表与Johnson Reducer算法和文献[9]提出的值约简算法得到的结果是一致的，而对于Iris Plants Database决策表本文算法与文献[9]提出的值约简算法得到的结果一致，这个结果比Johnson Reducer算法得到的结果更简约.

对于Balloon database1决策表，利用本文算法抽取出的规则与Johnson Reducer算法和文献[9]提出的值约简算法得到的结果一致，而随着决策表的实例数的增加，本文算法比Johnson Reducer算法和文献[9]提出的值约简算法抽取出的规则条数更少.

表3.7 约简算法比较

综合以上分析，应用基于规则核值算法得到的结果更简约和更合理.

5 结束语

本文应用粗糙集的理论，提出一个基于规则核值的扩展算法.求属性集的最小约简是一个NP问题，在对需要进行决策分析的属性进行约简时，根据主属性及相关属性的约简重要性，取重要性最大的近似最小约简为条件属性的约简，极好地保留了原决策系统的信息.利用决策矩阵导出约简属性的核值，并对核值进行扩展及选择，从而很好地去除了规则中的冗余属性值，得到更加简化的规则. ■

[1]Pawlak Z ． Rough sets[J],． International Journal of Information and Computer Science, 1982, 11(5): 341～356．

[2]张文修，吴伟志. 粗糙集理论介绍和研究综述[J]. 模糊系统与数学，2000，14(4)：1～12.

[3]张文修，吴伟志，梁吉业等.粗糙集理论与方法［M］.北京：科学出版社，2001.

[4]Wong S K M，Ziarko W． Optimal decision rules in decisiontabe． Bulletin of Polish Academy of Sciences, 1985, 33( 11-12): 693-696．

[5]Jelonek J, Krawiec K, Slowinski R． Rough set reduction of attributes and their domains for neural networks．International Journal of Computational Intelligence, 1995, 11( 2) : 339～ 347．

[6]苗夺谦，桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展，1999，36(6)：681-684.

[7]王国胤，于洪，杨大春.基于条件信息熵的决策约简[J].计算机学报，2002，25(7)：759-766.

[8]Hu X H, Cercone N． Learning in relational databases: a rough set approach[J]． Internation al Journal of Computational Intelligence, 1995, 11(2): 323-338

[9]常犁云,王国胤,吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J]. 软件学报，1999，10(11)：1206～1211

[10]Skowron A,Rauszer C． The Discernibility Matrices and Functions in Information System[J]． In:Slowinski R(ed)．Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory, Kluwer Academic Publishers,1992:331～362

[11]Zdzislaw Pawlak． Rough Sets and Decision Analysis[J]．INFOR, 2000, 38 (3):132～144．

[12]王珏，苗夺谦，周育健.关于Rough Set理论与应用的综述[J].模式识别与人工智能，1996，9(4)：337～343.

【责任编辑 谢文海】

An Expansion Algorithm Based on the Rule Core Value of the Rough Sets Theory

XIAO Zhi-jun1，MENG Qiao-yuan1，CHEN Shou-hui2
(1．College of Computer Science & Engineering, Yulin Normal University, Yulin, Guangxi 537000; 2． Yulin Xinqiao Middle School, Yulin, Guangxi 537000)

According to the rough set the theory, expansion algorithm method based on the rule core value is proposed, using this algorithm elimination rule in redundant attribute value, thus obtaining even more simplified rules．

rough sets; reduction; decision rule

TP311.13

A

1004-4671（2014）02-0106-07

2014-01-01

广西教育厅科研项目（201204LX350）；广西自然科学基金项目（2013GXNSFAA019078）；广西高等学校科研项目（201204LX342）；广西教育科学规划课题（2011C0079）。广西教育厅科研项目（2013LX111）。

肖志军（1975～），男，玉林师范学院计算机科学与工程学硕士，讲师，研究方向为数据挖掘理论、智能决策。