基于粗集理论的数据约简及其在现代远程教育中应用的研究
|
摘要
随着网络和多媒体技术的飞速发展,现代远程教育作为一个新的教育模式正在对传统的教学模式产生深刻的变革。在这种新的教学模式中，各种各样的评价系统是现代远程教育体系结构中的重要组成部分之一。这些评价系统通过给出相关的评价指标，收集评价数据，经过数据挖掘，获得评价的决策。但是在网络环境中，这些评价系统在数据处理时会面临如下问题：
1． 数据量大
2． 数据不完备
3． 希望得到的知识是数据本身所含知识的真实反映，尽量减少外界的影响。
粗集理论由于其自身的特点恰好能够解决这三个问题。
粗集理论是Pawlak教授于1982年提出的用于处理不确定、不完整知识的数学工具，它涉及了数据的表达、学习、归纳的理论方法。和其它数学工具不同，粗集合理论不需要人们的先验知识做指导，也不受外界的影响，而是客观地反映数据集合所包含的信息，因此20年来越来越受到研究人员的普遍重视。粗集理论也逐渐成为KDD的有力的数学工具。
本论文将以远程教育应用为研究背景，集中研究不完备信息系统下的数据约简算法。不完备系统由于存在数据的缺失，传统的粗糙集模型就存在着局限性，因此必须对传统模型进行扩展。论文首先对粗糙集的相关理论做了一番介绍，然后针对已提出的容差关系模型的不足，提出一种改进容差关系模型，该模型更加符合客观实际，增加了灵活性。之后以该改进模型为基础，在不进行数据补齐的情况下，运用属性重要性和粗糙熵理论，在传统属性约简算法的基础上提出了能够处理不完备信息系统的属性约简算法，给出了算法的描述并进行了一定的性能分析。
经过属性约简后的决策表仍然有冗余信息，因此需要值约简，论文对二进制可分辨矩阵加以改进，提出多值可分辨矩阵，并在多值可分辨矩阵的基础上提出值约简算法，最后获取决策规则。论文最后以教师评价系统为例，将本论文提出的算法应用到该系统中，并和传统容差关系模型做了比较。
With the developmemt of the Internet and multimedia technology, modern remote education as has been deeply impacting the traditional teaching mode as a newly teaching mode. In this new mode, various evaluating systems is one of the important component in modern remote education architecture. These evaluating systems give inspectively evaluating indexes, collect evaluating data, and then obtain decision rules by data minging. But in network enviroment, there are some problems in data procession. These are:
1. Large amount of data
2. Incomplete data
3. The knowledge that we obtain is the truly reflection of the decision table without influence of ousider and priori knowledge.
Rough set theory is the tool to solve those problems.
Rough set theory proposed by Pawlak in 1982 is a mathimatic tool for handling uncertain and incomplete knowledge. It involves methods of data expressing、data learning、and data reducing. Rough set is so different from fuzzy set and other mathimatic tools that it does not need prediction of priori kownledge and is not impacted by outsider but reflect information in data objectively. So people take more and more concern on rough set in recent 20 years. Rough set becomes a powerful tool in KDD increasingly.
In this paper, remote education is taken as background to research data reduction in incmplete information system. Because of incomplete data in incomplete information system, the traditional rough set models are not suitable for incomplete system. So the traditional model must be extended to satisfy the incomplete system. in this paper, rough set theory is firstly introduced, and then an improved rough set model is proposed according to the shortcoming of extended model which has been proposed.The new model is more fit for reality and has more flexible.Then a new attributes reduction alogrims are proposed based on improved model applying importance of attributes and rough entropy theory.
But there is still redundant data in data table after attribute reduction. For each object, not all attribute value are necessary for last decision rule, so the reduction must
be done in further step to get rid of redundant information continuously. That is called
value reduction. The author improves the binary discernable matrix, come up with multi-value discernable matrix and apply it to give a value reduction alogrim by constructing multi-value discernable matrix for each object to obtain dicision rules.
In the last section of this paper, an application-----Teaching Evaluation System is given as application of rough set. All algorism given in this paper are applied in the application and be compared with tolerance relation.
1． 数据量大
2． 数据不完备
3． 希望得到的知识是数据本身所含知识的真实反映，尽量减少外界的影响。
粗集理论由于其自身的特点恰好能够解决这三个问题。
粗集理论是Pawlak教授于1982年提出的用于处理不确定、不完整知识的数学工具，它涉及了数据的表达、学习、归纳的理论方法。和其它数学工具不同，粗集合理论不需要人们的先验知识做指导，也不受外界的影响，而是客观地反映数据集合所包含的信息，因此20年来越来越受到研究人员的普遍重视。粗集理论也逐渐成为KDD的有力的数学工具。
本论文将以远程教育应用为研究背景，集中研究不完备信息系统下的数据约简算法。不完备系统由于存在数据的缺失，传统的粗糙集模型就存在着局限性，因此必须对传统模型进行扩展。论文首先对粗糙集的相关理论做了一番介绍，然后针对已提出的容差关系模型的不足，提出一种改进容差关系模型，该模型更加符合客观实际，增加了灵活性。之后以该改进模型为基础，在不进行数据补齐的情况下，运用属性重要性和粗糙熵理论，在传统属性约简算法的基础上提出了能够处理不完备信息系统的属性约简算法，给出了算法的描述并进行了一定的性能分析。
经过属性约简后的决策表仍然有冗余信息，因此需要值约简，论文对二进制可分辨矩阵加以改进，提出多值可分辨矩阵，并在多值可分辨矩阵的基础上提出值约简算法，最后获取决策规则。论文最后以教师评价系统为例，将本论文提出的算法应用到该系统中，并和传统容差关系模型做了比较。
With the developmemt of the Internet and multimedia technology, modern remote education as has been deeply impacting the traditional teaching mode as a newly teaching mode. In this new mode, various evaluating systems is one of the important component in modern remote education architecture. These evaluating systems give inspectively evaluating indexes, collect evaluating data, and then obtain decision rules by data minging. But in network enviroment, there are some problems in data procession. These are:
1. Large amount of data
2. Incomplete data
3. The knowledge that we obtain is the truly reflection of the decision table without influence of ousider and priori knowledge.
Rough set theory is the tool to solve those problems.
Rough set theory proposed by Pawlak in 1982 is a mathimatic tool for handling uncertain and incomplete knowledge. It involves methods of data expressing、data learning、and data reducing. Rough set is so different from fuzzy set and other mathimatic tools that it does not need prediction of priori kownledge and is not impacted by outsider but reflect information in data objectively. So people take more and more concern on rough set in recent 20 years. Rough set becomes a powerful tool in KDD increasingly.
In this paper, remote education is taken as background to research data reduction in incmplete information system. Because of incomplete data in incomplete information system, the traditional rough set models are not suitable for incomplete system. So the traditional model must be extended to satisfy the incomplete system. in this paper, rough set theory is firstly introduced, and then an improved rough set model is proposed according to the shortcoming of extended model which has been proposed.The new model is more fit for reality and has more flexible.Then a new attributes reduction alogrims are proposed based on improved model applying importance of attributes and rough entropy theory.
But there is still redundant data in data table after attribute reduction. For each object, not all attribute value are necessary for last decision rule, so the reduction must
be done in further step to get rid of redundant information continuously. That is called
value reduction. The author improves the binary discernable matrix, come up with multi-value discernable matrix and apply it to give a value reduction alogrim by constructing multi-value discernable matrix for each object to obtain dicision rules.
In the last section of this paper, an application-----Teaching Evaluation System is given as application of rough set. All algorism given in this paper are applied in the application and be compared with tolerance relation.
引文
[1] 何茜 现代远程教育教学效果反馈模型研究 硕士学位论文 重庆大学 2001
[2] Pawlak .Z Rough Sets Theory and Its Applications to Data Analysis[J] Cybernetics Systems,An Int I J 1998:29:661-668
[3] 曾黄麟 粗集理论及其应用----关于数据推理的新方法 重庆：重庆大学出版社 1996.9
[4] 王国胤 Rough 集理论与知识获取 西安：西安交通大学出版社 2001.5
[5] 张文修等 粗糙集理论与方法 北京： 科学出版社 2001
[6] Ivo Düntsch & Günther Gediga_ Rough set data analysis http://www.cosc.brocku.ca/~
duentsch/archive/rsda.pdf
[7] 黄兵 周献中 基于集对分析的不完备信息系统粗糙集模型 2002.9(专刊)计算机科学 1~3第二届中国Rough集与软计算学术研讨会 苏州 2002.10
[8] 周勇 毛宇光 王建东 中介粗集及其在数据挖掘中的应用 南京航空航天大学学报
Vol.32 No.6 Dec.2 0 0 0 609-613
[9] 赵卫东 吴明赞 不完全信息下的粗集拓展 计算机科学2002.9(专刊) 131~134 第二届中国Rough集与软计算学术研讨会 苏州 2002.10
[10] 叶东毅 Jelonek属性约简算法的一个改进 电子学报 Vol.28 No.12 2000.10 81~82
[11] 邓大勇 ,江 峰 ,刘 清 基于Rough集方法的数据约简与机器学习 计算机与现代化 2002年 第 1期 21~23
[12] 叶东毅 信息表相对属性约简的一个算法 福州大学学报(自然科学版) Vol.28 No.6 2000.11 7~9
[13] 叶东毅 陈昭炯 一个改进的粗糙集属性约简算法 福州大学学报(自然科学版) Vol.28 No.5 2000.10 9~12
[14] 叶东毅 黄翠微 基于逼近精度的一个粗糙集属性约简算法 福州大学学报(自然科学版) Vol.28 No.1 2000.2 7~10
[15] 曾黄麟：粗集理论极其应用专题研究（1~4），四川轻化工学院学报，1996，Vol,8,NO.1~4
[16] 李孟歆,吴成东 粗糙集理论及其应用 沈阳建筑工程学院学报 (自然科学版 ) Vol.17
No .4 2001.10 296~299
[17] Krolikowski R,Czyzewski A. Noise Reduction in Telecommunication Channels Using Rough Sets and Neural Networks. 7th International Workshop on New Directions in Rough Sets,Data Mining,and Granular-Soft Computing,1999,100~108
[18] Sui Yuefei The Entropy of Rough Relations in Rough Relational Databases http:// www.
wbmt.tudelft.nl/pto/research/conferences/ Proceedings/Sci2001/Paperspdf/P000559.PDF
[19] Guoyin Wang & Hong Yu Knowledge Reduction Based on Rough Set and Information Entropy http://www.wbmt.tudelft.nl/pto/research/conferences/ proceedings/Sci2001/ Paperspdf/IS0037804.PDF
[20] 梁吉业 孟晓伟 信息熵在粗糙集理论中的应用 山西大学学报(自然科学版) 25(3) 281~284 2002
[21] Z.Pawlak Granularity of knowledge, Indiscernibility and rough sets
http://www.wbmt.tudelft.nl/pto/research/conferences/Proceedings/Sci2001/Paperspdf/P000374.PDF
[22] 苗夺谦 范世栋 知识的粒度计算及其应用 系统工程理论与实践 2002.1第一期 48~56
[23] 郑芳,吴云志,杭小树. 粗集理论中知识粗糙性的研究.2002.4 计算机工程与应用 98-101
[24] 石峰 娄臻亮 张永清 一种改进的粗糙集属性约简启发式算法 上海交通大学学报 第26卷 第四期 2002年4月 478~481
[25] Miao Duoqian & Wang jue Information-Based Algorism for Reduction of Knowledge 1997 IEEE International conference on Intelligent processing system 1155~1158
[26] J.W.Guan Rough Computational Methods for information systems Artificial Intelligence 105(1998) 77~103
[27] Guoyin Wang Extension of Rough set under incomplete systems IEEE 2000 1098~1103
[28] Zbigniew Extensions and Intensions in the Rough Set theory Journal of information science 107(1998)149~167
[29] Keyun Hu Rough Set Theory under the Similarity Relations
http://www.wbmt.tudelft.nl/pto/research/conferences/Proceedings/Sci2001/Paperspdf/P000558.PDF
[30] P. J. Lingras&Y.Y.Yao Data Mining Using Extensions of the Rough Set Model
http://pc91066.cse.cuhk.edu.hk/TechDocs/Data%20Mining/ THEORY/lingras98.pdf
[31] Zhihai Wang & Shengfeng Tian, Houkuan Huang An Extended Tolerant Rough Set Model http://216.72.45.230:1081/ProceedingSCI/volumeXIV2001.htm
[32] 支天云 苗夺谦 二进制可辩矩阵的变换及高校属性约简算法的构造 计算机科学 2002 Vol.29 No.2 140~142
[33] 支天云等 基于差别矩阵的二进制信息系统的约简方法 山西大学学报(自然科学版) 25(1) 27~29
[34] 常犁云 王国胤 吴渝：一种基于Rough Set 的属性约简及规则提取方法 软件学报1999 10（11）：1206~1211
[35] 李玉榕 乔斌 粗糙集理论中的不确定性的粗糙信息熵表示 计算机科学 2002 Vol.29
No.5 101~103
[36] 侯丽珊 苗夺谦 一种带局部回溯的属性约简算法 计算机科学 2002 Vol.29 No.12 127~128
[37] liang jiye & Xu zhongben Uncertainty of Roughness of knowledge and Rough sets in incomplete information systems Peocedings of 3rd world comgresson Intelligent Control and Automation 2525~2529 2000
[38] Pawlak Z.Slowinski Rough set approach to multiattribute decision analysis, invited review[J].Eurpean Journal of operational Reserch,1994:72;443~459
[39] Liang Jiye &Li Deyu Information Measures of Roughness of Knowledge and Significance of
Attribute in Rough Set Theory 工程数学学报 第 1 7卷 增刊 2 0 0 0年 5月 106~108
[40] 曾黄麟 傅成华 姚毅 基于粗集方法的课堂教学质量评价子系统研究初探 四川轻化工学院学报 Vol.14 No.1 May 2001 1-4
[2] Pawlak .Z Rough Sets Theory and Its Applications to Data Analysis[J] Cybernetics Systems,An Int I J 1998:29:661-668
[3] 曾黄麟 粗集理论及其应用----关于数据推理的新方法 重庆：重庆大学出版社 1996.9
[4] 王国胤 Rough 集理论与知识获取 西安：西安交通大学出版社 2001.5
[5] 张文修等 粗糙集理论与方法 北京： 科学出版社 2001
[6] Ivo Düntsch & Günther Gediga_ Rough set data analysis http://www.cosc.brocku.ca/~
duentsch/archive/rsda.pdf
[7] 黄兵 周献中 基于集对分析的不完备信息系统粗糙集模型 2002.9(专刊)计算机科学 1~3第二届中国Rough集与软计算学术研讨会 苏州 2002.10
[8] 周勇 毛宇光 王建东 中介粗集及其在数据挖掘中的应用 南京航空航天大学学报
Vol.32 No.6 Dec.2 0 0 0 609-613
[9] 赵卫东 吴明赞 不完全信息下的粗集拓展 计算机科学2002.9(专刊) 131~134 第二届中国Rough集与软计算学术研讨会 苏州 2002.10
[10] 叶东毅 Jelonek属性约简算法的一个改进 电子学报 Vol.28 No.12 2000.10 81~82
[11] 邓大勇 ,江 峰 ,刘 清 基于Rough集方法的数据约简与机器学习 计算机与现代化 2002年 第 1期 21~23
[12] 叶东毅 信息表相对属性约简的一个算法 福州大学学报(自然科学版) Vol.28 No.6 2000.11 7~9
[13] 叶东毅 陈昭炯 一个改进的粗糙集属性约简算法 福州大学学报(自然科学版) Vol.28 No.5 2000.10 9~12
[14] 叶东毅 黄翠微 基于逼近精度的一个粗糙集属性约简算法 福州大学学报(自然科学版) Vol.28 No.1 2000.2 7~10
[15] 曾黄麟：粗集理论极其应用专题研究（1~4），四川轻化工学院学报，1996，Vol,8,NO.1~4
[16] 李孟歆,吴成东 粗糙集理论及其应用 沈阳建筑工程学院学报 (自然科学版 ) Vol.17
No .4 2001.10 296~299
[17] Krolikowski R,Czyzewski A. Noise Reduction in Telecommunication Channels Using Rough Sets and Neural Networks. 7th International Workshop on New Directions in Rough Sets,Data Mining,and Granular-Soft Computing,1999,100~108
[18] Sui Yuefei The Entropy of Rough Relations in Rough Relational Databases http:// www.
wbmt.tudelft.nl/pto/research/conferences/ Proceedings/Sci2001/Paperspdf/P000559.PDF
[19] Guoyin Wang & Hong Yu Knowledge Reduction Based on Rough Set and Information Entropy http://www.wbmt.tudelft.nl/pto/research/conferences/ proceedings/Sci2001/ Paperspdf/IS0037804.PDF
[20] 梁吉业 孟晓伟 信息熵在粗糙集理论中的应用 山西大学学报(自然科学版) 25(3) 281~284 2002
[21] Z.Pawlak Granularity of knowledge, Indiscernibility and rough sets
http://www.wbmt.tudelft.nl/pto/research/conferences/Proceedings/Sci2001/Paperspdf/P000374.PDF
[22] 苗夺谦 范世栋 知识的粒度计算及其应用 系统工程理论与实践 2002.1第一期 48~56
[23] 郑芳,吴云志,杭小树. 粗集理论中知识粗糙性的研究.2002.4 计算机工程与应用 98-101
[24] 石峰 娄臻亮 张永清 一种改进的粗糙集属性约简启发式算法 上海交通大学学报 第26卷 第四期 2002年4月 478~481
[25] Miao Duoqian & Wang jue Information-Based Algorism for Reduction of Knowledge 1997 IEEE International conference on Intelligent processing system 1155~1158
[26] J.W.Guan Rough Computational Methods for information systems Artificial Intelligence 105(1998) 77~103
[27] Guoyin Wang Extension of Rough set under incomplete systems IEEE 2000 1098~1103
[28] Zbigniew Extensions and Intensions in the Rough Set theory Journal of information science 107(1998)149~167
[29] Keyun Hu Rough Set Theory under the Similarity Relations
http://www.wbmt.tudelft.nl/pto/research/conferences/Proceedings/Sci2001/Paperspdf/P000558.PDF
[30] P. J. Lingras&Y.Y.Yao Data Mining Using Extensions of the Rough Set Model
http://pc91066.cse.cuhk.edu.hk/TechDocs/Data%20Mining/ THEORY/lingras98.pdf
[31] Zhihai Wang & Shengfeng Tian, Houkuan Huang An Extended Tolerant Rough Set Model http://216.72.45.230:1081/ProceedingSCI/volumeXIV2001.htm
[32] 支天云 苗夺谦 二进制可辩矩阵的变换及高校属性约简算法的构造 计算机科学 2002 Vol.29 No.2 140~142
[33] 支天云等 基于差别矩阵的二进制信息系统的约简方法 山西大学学报(自然科学版) 25(1) 27~29
[34] 常犁云 王国胤 吴渝：一种基于Rough Set 的属性约简及规则提取方法 软件学报1999 10（11）：1206~1211
[35] 李玉榕 乔斌 粗糙集理论中的不确定性的粗糙信息熵表示 计算机科学 2002 Vol.29
No.5 101~103
[36] 侯丽珊 苗夺谦 一种带局部回溯的属性约简算法 计算机科学 2002 Vol.29 No.12 127~128
[37] liang jiye & Xu zhongben Uncertainty of Roughness of knowledge and Rough sets in incomplete information systems Peocedings of 3rd world comgresson Intelligent Control and Automation 2525~2529 2000
[38] Pawlak Z.Slowinski Rough set approach to multiattribute decision analysis, invited review[J].Eurpean Journal of operational Reserch,1994:72;443~459
[39] Liang Jiye &Li Deyu Information Measures of Roughness of Knowledge and Significance of
Attribute in Rough Set Theory 工程数学学报 第 1 7卷 增刊 2 0 0 0年 5月 106~108
[40] 曾黄麟 傅成华 姚毅 基于粗集方法的课堂教学质量评价子系统研究初探 四川轻化工学院学报 Vol.14 No.1 May 2001 1-4