论文部分内容阅读
摘要：该文提出了一种基于粗糙－模糊集理论的知识获取方法，该方法将粗糙集理论与模糊集理论相结合，先利用模糊集理论对决策表的连续属性进行模糊化，通过构建模糊相似矩阵进而划分论域；再利用粗糙模糊集理论进行属性约简，从而获取决策规则。最后，通过实例验证了该方法的有效性和实用性。
关键词：粗糙集；模糊集；属性约简；知识获取
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)23-1029-03
Knowledge Acquisition Approach Based on Rough-Fuzzy Sets
CAI Hong, YE Shui-sheng, ZHANG Yong
(Nanchang Hang Kong University, School of Computing, Nanchang 330063, China)
Abstract: This article presents an approach of knowledge acquisition based on rough and fuzzy sets, which combines features of rough sets and fuzzy sets. The continuous attributes in the decision table are fuzzified with fuzzy membership functions. The domain partition is accomplished after establishing fuzzy similarity matrix. Attributes reduction can be obtained using rough-fuzzy sets, and then decision rules can be acquired. At last, an example is illustrated and proves the approach is effective and practical.
Key words: rough sets; fuzzy sets; attributes reduction; knowledge acquisition
粗糙集理论是一种处理不完整和不确定信息的有效数学工具，它具有知识获取完全由数据驱动，不需额外信息的优点。但是，粗糙集理论直接处理连续属性的能力非常有限，因而连续属性的离散化成为制约粗糙集理论发展的难点。而模糊集可以通过模糊隶属度函数来刻画集合中子类边界的模糊性，两者正好互补。因此，本文将粗糙集与模糊集理论相结合，提出了一种基于粗糙－模糊集理论的知识获取方法，并通过实例验证了该方法的有效性。
1 基于模糊相似关系的论域划分模型
1.1 连续属性离散化
对于决策表中任一连续属性，根据值域的大小和属性值的分布，可以将其模糊化为k个语义变量，而这k个模糊划分的中心mi可由Kohonen网络自组织映射算法确定。
1.2 基于模糊相似关系的论域划分方法
1）利用数量积法建立模糊相似矩阵R=(rij)n*n，rij表示对象xi和xj的相似程度。rij定义如下：
2）在此基础上，引入置信水平λ，rij经过如下操作，得到普通相似矩阵Rλ。
3）基于模糊相似关系的论域划分方法
输入：决策表四元组，普通相似矩阵Rλ，其中A=C∪D，C为条件属性集合，D为决策属性集合。
输出：论域划分U/ND(Rλα) ={V1,V2,V3,…,Vt}。
Step 1：i←1, j←1, t←1, V1←{ u1 }
Step 2：if ( i与|U|相等) 划分完成退出
else 转向Step 3
Step 3：i←i+1, j←1
Step 4：if ( μa(ui) 与μa(vj)相等) Vj←Vj∪{ui},转向Step 2
else 转向Step 5
Step 5：j←j+1
Step 6：if (j大于t) t←t+1,Vt←{ui},转向Step 2
else 转向Step 4
2 基于属性依赖度的约简算法
2.1 模糊粗糙集的上、下近似和属性依赖度定义
根据基于模糊相似关系的论域划分方法，可以得到属性a∈A且在置信水平λ下对论域U的划分U/ND(Rλα) ，其中不同的属性可以采用不同的置信水平对论域进行划分，那么属性集A对论域U的划分可以表示为：
如果用Fi表示式（3）中的U/ND(Rλiαi)，那么式（3）可表示为：
2.2 基于属性依赖度的约简算法
基于属性依赖度的约简算法主要思想：首先令R为空集，依次把那些使γR(D)的增量达到最大的属性添加到集合R中，直到γR(D)达到最大，输出决策表的一个最小属性约简集合R。算法描述如下：
输入：决策表四元组< U, A, V, f >，属性依赖度RM(D)，其中A=C∪D，M?哿C。
输出：决策表的一个最小属性约简集合R。
Step 1：R←{ }, T←{ }, γbest(D)←0, γprev(D)←0
Step 2：T←R, γprev←γbest(D)
Step 3： , T←R∪{y}
Step 4：R←T, γbest(D)←γR∪(y)(D)
Step 5：if (γbest(D)与γprev(D)相等) 约简完成退出
else 转向Step 2
3 决策规则归纳算法
根据上面提出的粗糙－模糊集模型，进行决策规则归纳以获取知识，具体步骤如下：
1） 利用Kohonen网络自组织映射算法确定k个模糊划分的中心mi，并采用三角隶属度函数对连续属性进行模糊化；
2） 根据基于模糊相似关系的论域划分方法得到对整个论域的划分；
3） 根据基于属性依赖度的约简算法得到条件属性集的一个最小约简集；
4） 删除决策表中重复实例，归纳出决策规则。
4 实验
为了验证算法的有效性，将上述提出的基于粗糙－模糊集理论的知识获取方法应用于如表1所示的决策表中，其中C={a1, a2, a3, a4}，D={d}。
首先，对条件属性集C四个连续属性进行模糊化。利用Kohonen网络自组织映射算法确定5个模糊划分的中心mi，并采用三角隶属度函数对连续属性进行模糊化，其隶属度函数如图1和图2所示。
其次，根据基于模糊相似关系的论域划分方法得到对整个论域的划分。令λ=0.8。
再次，根据基于属性依赖度的约简算法得到条件属性集的一个最小约简集。
γc(D)=5/6，而γ{a2,a3,a4}(D)=1/3，γ{a1,a3,a4}(D)=2/3，γ{a1,a2,a4}(D)=1/2，γ{a1,a2,a3}(D)=5/6，可以得到约简集{a1, a2, a3}。
最后，删除决策表中重复实例，归纳出决策规则。
1）IF 1.4 ≤ a1 ≤ 1.9 and 1.6 ≤ a2 ≤ 1.8 THEN d=1;
2）IF 1.4 ≤ a1 ≤ 1.9 and 2.1 ≤ a2 ≤ 2.6 and 1.01 ≤ a3 ≤ 1.10 THEN d=1;
3）IF 1.4 ≤ a1 ≤ 1.9 and 2.1 ≤ a2 ≤ 2.6 and a3 = 0.78 THEN d=2;
4）IF 2.2 ≤ a1 ≤ 2.7 and 2.1 ≤ a2 ≤ 2.6 THEN d=2;
5）IF 3.1 ≤ a1 ≤ 3.8 and 2.1 ≤ a2 ≤ 2.6 THEN d=3;
6）IF 2.2 ≤ a1 ≤ 2.7 and 3.5 ≤ a2 ≤ 3.9 THEN d=3;
7）IF 3.1 ≤ a1 ≤ 3.8 and 3.5 ≤ a2 ≤ 4.9 THEN d=4;
8）IF a1 = 4.9 and 3.5 ≤ a2 ≤ 3.9 and 0.42 ≤ a3 ≤ 0.56 THEN d=4。
5 结论
本文提出的基于粗糙－模糊集理论的知识获取方法，是将粗糙集理论与模糊集理论相结合，先利用模糊集理论对决策表的连续属性进行模糊化处理，以避免直接离散化带来的信息丢失，再利用粗糙模糊集理论进行属性约简，进而获取决策规则，该方法为解决连续属性的规则获取问题提供了一条有效途径。
参考文献：
[1] 张化光,徐悦,孙秋野.基于模糊粗糙集的系统连续变量离散化方法[J].东北大学学报（自然科学版）,2008,(1):1-4.
[2] 吴山产,毛锋,王文渊,等.基于粗糙集的两种离散化算法的研究[J].计算机工程与应用,2004,40(26):68-69.
[3] 樊雷,雷英杰.基于直觉模糊粗糙集的一种知识获取方法[J].计算机工程与应用,2008,44(4):39-41.
[4] WU Wei-zhi,ZHANG Wen-xiu,LI Huai-zu. Knowledge acquisition in incomplete fuzzy information systems via the rough set approach[J]. Expert Systems,2003,20(5):280-286.
关键词：粗糙集；模糊集；属性约简；知识获取
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)23-1029-03
Knowledge Acquisition Approach Based on Rough-Fuzzy Sets
CAI Hong, YE Shui-sheng, ZHANG Yong
(Nanchang Hang Kong University, School of Computing, Nanchang 330063, China)
Abstract: This article presents an approach of knowledge acquisition based on rough and fuzzy sets, which combines features of rough sets and fuzzy sets. The continuous attributes in the decision table are fuzzified with fuzzy membership functions. The domain partition is accomplished after establishing fuzzy similarity matrix. Attributes reduction can be obtained using rough-fuzzy sets, and then decision rules can be acquired. At last, an example is illustrated and proves the approach is effective and practical.
Key words: rough sets; fuzzy sets; attributes reduction; knowledge acquisition
粗糙集理论是一种处理不完整和不确定信息的有效数学工具，它具有知识获取完全由数据驱动，不需额外信息的优点。但是，粗糙集理论直接处理连续属性的能力非常有限，因而连续属性的离散化成为制约粗糙集理论发展的难点。而模糊集可以通过模糊隶属度函数来刻画集合中子类边界的模糊性，两者正好互补。因此，本文将粗糙集与模糊集理论相结合，提出了一种基于粗糙－模糊集理论的知识获取方法，并通过实例验证了该方法的有效性。
1 基于模糊相似关系的论域划分模型
1.1 连续属性离散化
对于决策表中任一连续属性，根据值域的大小和属性值的分布，可以将其模糊化为k个语义变量，而这k个模糊划分的中心mi可由Kohonen网络自组织映射算法确定。
1.2 基于模糊相似关系的论域划分方法
1）利用数量积法建立模糊相似矩阵R=(rij)n*n，rij表示对象xi和xj的相似程度。rij定义如下：
2）在此基础上，引入置信水平λ，rij经过如下操作，得到普通相似矩阵Rλ。
3）基于模糊相似关系的论域划分方法
输入：决策表四元组
输出：论域划分U/ND(Rλα) ={V1,V2,V3,…,Vt}。
Step 1：i←1, j←1, t←1, V1←{ u1 }
Step 2：if ( i与|U|相等) 划分完成退出
else 转向Step 3
Step 3：i←i+1, j←1
Step 4：if ( μa(ui) 与μa(vj)相等) Vj←Vj∪{ui},转向Step 2
else 转向Step 5
Step 5：j←j+1
Step 6：if (j大于t) t←t+1,Vt←{ui},转向Step 2
else 转向Step 4
2 基于属性依赖度的约简算法
2.1 模糊粗糙集的上、下近似和属性依赖度定义
根据基于模糊相似关系的论域划分方法，可以得到属性a∈A且在置信水平λ下对论域U的划分U/ND(Rλα) ，其中不同的属性可以采用不同的置信水平对论域进行划分，那么属性集A对论域U的划分可以表示为：
如果用Fi表示式（3）中的U/ND(Rλiαi)，那么式（3）可表示为：
2.2 基于属性依赖度的约简算法
基于属性依赖度的约简算法主要思想：首先令R为空集，依次把那些使γR(D)的增量达到最大的属性添加到集合R中，直到γR(D)达到最大，输出决策表的一个最小属性约简集合R。算法描述如下：
输入：决策表四元组< U, A, V, f >，属性依赖度RM(D)，其中A=C∪D，M?哿C。
输出：决策表的一个最小属性约简集合R。
Step 1：R←{ }, T←{ }, γbest(D)←0, γprev(D)←0
Step 2：T←R, γprev←γbest(D)
Step 3： , T←R∪{y}
Step 4：R←T, γbest(D)←γR∪(y)(D)
Step 5：if (γbest(D)与γprev(D)相等) 约简完成退出
else 转向Step 2
3 决策规则归纳算法
根据上面提出的粗糙－模糊集模型，进行决策规则归纳以获取知识，具体步骤如下：
1） 利用Kohonen网络自组织映射算法确定k个模糊划分的中心mi，并采用三角隶属度函数对连续属性进行模糊化；
2） 根据基于模糊相似关系的论域划分方法得到对整个论域的划分；
3） 根据基于属性依赖度的约简算法得到条件属性集的一个最小约简集；
4） 删除决策表中重复实例，归纳出决策规则。
4 实验
为了验证算法的有效性，将上述提出的基于粗糙－模糊集理论的知识获取方法应用于如表1所示的决策表中，其中C={a1, a2, a3, a4}，D={d}。
首先，对条件属性集C四个连续属性进行模糊化。利用Kohonen网络自组织映射算法确定5个模糊划分的中心mi，并采用三角隶属度函数对连续属性进行模糊化，其隶属度函数如图1和图2所示。
其次，根据基于模糊相似关系的论域划分方法得到对整个论域的划分。令λ=0.8。
再次，根据基于属性依赖度的约简算法得到条件属性集的一个最小约简集。
γc(D)=5/6，而γ{a2,a3,a4}(D)=1/3，γ{a1,a3,a4}(D)=2/3，γ{a1,a2,a4}(D)=1/2，γ{a1,a2,a3}(D)=5/6，可以得到约简集{a1, a2, a3}。
最后，删除决策表中重复实例，归纳出决策规则。
1）IF 1.4 ≤ a1 ≤ 1.9 and 1.6 ≤ a2 ≤ 1.8 THEN d=1;
2）IF 1.4 ≤ a1 ≤ 1.9 and 2.1 ≤ a2 ≤ 2.6 and 1.01 ≤ a3 ≤ 1.10 THEN d=1;
3）IF 1.4 ≤ a1 ≤ 1.9 and 2.1 ≤ a2 ≤ 2.6 and a3 = 0.78 THEN d=2;
4）IF 2.2 ≤ a1 ≤ 2.7 and 2.1 ≤ a2 ≤ 2.6 THEN d=2;
5）IF 3.1 ≤ a1 ≤ 3.8 and 2.1 ≤ a2 ≤ 2.6 THEN d=3;
6）IF 2.2 ≤ a1 ≤ 2.7 and 3.5 ≤ a2 ≤ 3.9 THEN d=3;
7）IF 3.1 ≤ a1 ≤ 3.8 and 3.5 ≤ a2 ≤ 4.9 THEN d=4;
8）IF a1 = 4.9 and 3.5 ≤ a2 ≤ 3.9 and 0.42 ≤ a3 ≤ 0.56 THEN d=4。
5 结论
本文提出的基于粗糙－模糊集理论的知识获取方法，是将粗糙集理论与模糊集理论相结合，先利用模糊集理论对决策表的连续属性进行模糊化处理，以避免直接离散化带来的信息丢失，再利用粗糙模糊集理论进行属性约简，进而获取决策规则，该方法为解决连续属性的规则获取问题提供了一条有效途径。
参考文献：
[1] 张化光,徐悦,孙秋野.基于模糊粗糙集的系统连续变量离散化方法[J].东北大学学报（自然科学版）,2008,(1):1-4.
[2] 吴山产,毛锋,王文渊,等.基于粗糙集的两种离散化算法的研究[J].计算机工程与应用,2004,40(26):68-69.
[3] 樊雷,雷英杰.基于直觉模糊粗糙集的一种知识获取方法[J].计算机工程与应用,2008,44(4):39-41.
[4] WU Wei-zhi,ZHANG Wen-xiu,LI Huai-zu. Knowledge acquisition in incomplete fuzzy information systems via the rough set approach[J]. Expert Systems,2003,20(5):280-286.