&nbsp;Value reduction algorithm based on decision information entropy <br><br>

PDF(305796 KB)

Journal of Nanjing University(Natural Sciences) ›› 2010, Vol. 46 ›› Issue (5) : 477-486.

Value reduction algorithm based on decision information entropy

Hu Feng 1 , Zhang Jie 1 , J i Zhao Ming 2 , Yi Xing Hui 1

Author information +

History +

Abstract

The research of value reduction is one of the key points in rough set theory. High efficient value reduction algorithms can help make decisions quickly. The present algorithms are either with low recognition rate or
with higher time complexity, moreover, they cannot reflect the change of decision capacity of decision rules objectively. In order to overcome these shortcomings, the paper uses the advantages that the confidence level and
decision information entropy can reflect the change of decision capacity of decision rules objectively, a value reduction algorithm based on decision information entropy is proposed. The algorithm uses equivalent division and
tolerance relation to divide decision table in properties space, then according to confidence level and decision information entropy determine whether property value for each decision is removed or not, finally get the correct
recognition rate that closes to the existing algorithm? s, and the running time is much lower. The algorithm steps are given in detail and related examples are illustrated, and do comparative experiment with heuristic value reduction and
value reduction based on decision matrix, T he experiment results prove the feasibility of the proposed algorithm.

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

Hu Feng 1 , Zhang Jie 1 , J i Zhao Ming 2 , Yi Xing Hui 1 . Value reduction algorithm based on decision information entropy

[J]. Journal of Nanjing University(Natural Sciences), 2010, 46(5): 477-486

References

[ 1 ] Pawlak Z. Rough set. International Journal of Computer and Information Science, 1982, 11 ( 5) : 341~ 356.
[ 2 ] Liu Q, Huang Z H, Liu S H, et al. decision rules with rough operator and soft computing of data mining. Journal of Computer Research and
Development, 1999, 36(7) : 800~ 804. (刘清, 黄兆华, 刘少辉等. 带 Rough 算子的决策规则及数据挖掘中的软计算. 计算机研究与发展, 1999, 36(7): 800~ 804) .
[ 3 ] Chang L Y, Wang G Y, Wu Y. An approach for attribute reduction and rule generation based on rough set theory. Journal of Software, 1999,
10( 11): 1206~ 1211. (常犁云, 王国胤, 吴渝. 一种基于 Rough Set 理论的属性约简及规则提取方法. 软件学报, 1999, 10 ( 11): 1206 ~ 1211) .
[ 4 ] Wang G Y. Rough set theory and knowledge acquisition. Xi- an: Xi- an Jiaotong University Press, 2001, 226. ( 王国胤. Rough 集理论与知识获取. 西安: 西安交通大学出版社, 2001, 226).
[ 5 ] Nguyen H S. Approximate boolean reasoning: Foundations and applications in data mining. Transaction on Rough Set V, 4100, 2006, 334~ 506.
[ 6 ] Pawlak Z, Skowron A. Rough sets and boolean reasoning. Information Sciences, 2007, 177: 41~ 73.
[ 7 ] Hou L J, Wang G Y, Wu Y. Discretization in rough set theory. Computer Sciences, 2000, 27 (12) : 89~ 94. (侯利娟, 王国胤, 吴? 渝. 粗糙集理论中的离散化问题. 计算机科学, 2000, 27 (12) : 89~ 94) .
[ 8 ] Liu S H, Sheng Q J, Shi Z Z. A new method for fast computing positive region. Journal of Computer Research and Development, 2003, 40
(5) : 637~ 642. ( 刘少辉, 盛秋戬, 史忠植. 一种新的快速计算正区域的方法. 计算机研究与发展, 2003, 40(5): 637~ 642) .
[ 9 ] Xu Z Y, Liu Z P, Yang B R, etal. A quick attribute reduction algorithm with complexity of max( O( | C| | U | ), O( | C| | U/ C| )) . Chinese Journal of Computers, 2006, 29( 3) : 391~ 399.
( 徐章艳, 刘作鹏, 杨炳儒等. 一个复杂度为 max (O(| C| | U| ) , O( | C| | U/ C| )) 的快速属性约简算法. 计算机学报, 2006, 29( 3) : 391~ 399) .
[ 10] Qin C, Huang H, Shi H J, et al. New method of data discretization based on rough set theory. Computer Engineering and Aplications, 2008, 44
(35) : 148~ 150. (秦川, 黄欢, 施化吉等. 基于区分矩阵的数据离散化算法. 计算机工程与应用, 2008, 44(35) : 148~ 150).
[ 11] Tian W D, Zhou C D, Hu X G, et al. A simplified -discernibility -matrix-based algorithm for attribute reduction in rough set. Computer Science, 2008, 3( 35): 209~ 212. ( 田卫东, 周创德,
胡学钢等. 基于简化分辨矩阵的粗糙集属性约简算法. 计算机科学, 2008, 3( 35) : 209~ 212) .
[ 12] Wang J, Wang J. Reduction algorithms based on discernibility matrix: T he order attributes method. Journal of Computer Science and T echnology, 2001, 16( 6) : 489~ 504.
[ 13] Wu Z F, Ji G L. Attribute reduction and rule extraction algorithms based on decision matrices. Computer Applications, 2005, 25 ( 3): 639~ 642. ( 武志峰, 吉根林. 一种基于决策矩阵的属性约简及规则提取算法. 计算机应用, 2005, 25( 3) : 639~ 642) .
[ 14] Rao H, Xia Y J, Li W Z. Algorithm for rule extraction based on discernibility matrix and attribute significance. Computer Engineering and
Applications, 2008, 44( 23): 163~ 165. ( 饶泓, 夏叶娟, 李娒竹. 基于分辨矩阵和属性重要度的规则提取算法. 计算机工程与应用, 2008, 44( 23): 163~ 165).
[ 15] Xie H, Cheng H Z, Niu D X. Discretization of continuous attributes in rough set theory based on information entropy. Chinese Journal of Computers, 2005, 28( 9) : 1570~ 1574.
( 谢宏, 程浩忠, 牛东晓. 基于信息熵的粗糙集连续属性离散化算法. 计算机学报, 2005, 28( 9) : 1570~ 1574) .
[ 16] Bai G Z, Pei Z L, Wang J, et al. Attribute discretization method based on rough set theory and information entropy. Application Research
of Computers, 2008, 6(25) : 1701~ 1703. ( 白根柱, 裴志利, 王建等. 基于粗糙集理论和信息熵的属性离散化方法. 计算机应用研究, 2008, 6 ( 25): 1701~ 1703).
[ 17] Wang G Y, Yu H, Yang D C. Decision table reduction based on conditional information entropy. Chinese Journal of Computers, 2002, 25 ( 7) : 759~ 766. (王国胤, 于? 洪, 杨大春. 基于条件信息熵的决策表约简. 计算机学报, 2002, 25( 7) : 759~ 766) .
[ 18] Liu Q H, Li F, M in F, et al. An efficient knowledge reduction algorithm based on new conditional information entropy. Control and Decision, 2005, 8(20) : 878~ 882. ( 刘启和, 李凡, 闵帆等. 一种基于新的条件信息熵的高效知识约简算法. 控制与决策, 2005, 8( 20) :878~ 882) .
[ 19] Chen J, Jiang Z H, Zhao Y S. Decision table reduction algorithm based on extended informa tion entropy. Computer Engineering and Applications, 2007, 43(7): 167~ 170.
( 陈杰, 蒋祖华, 赵云松. 基于扩展的信息熵的决策表属性约简算法. 计算机工程与应用, 2007, 43( 7) : 167~ 170) .
[ 20] Xu J C, Sun L. New reduction method based on decision information entropy in decision table. Journal of Chongqing University of Posts and Telecommunications( Natural Sciences), 2009,
21( 4) : 1~ 5. (徐久成, 孙林. 一种新的基于决策熵的决策表约简方法. 重庆邮电大学学报( 自然科学), 2009, 21(4): 1~ 5).
[ 21] Jiang S Y, Lu Y S. T wo new reduction definitions of decision table. Journal of Chinese Computer Systems, 2006, 27( 3): 512~ 516. ( 蒋思
宇, 卢炎生. 两种新的决策表属性约简概念. 小型微型计算机系统, 2006, 27(3): 512~ 516).
[ 22] Xu Z Y, Song W, Yang B R, et al. Note on . Two new reduction definition of decision table/. Journal of Chinese Computer Systems, 2007, 9(9): 1686~ 1690. (徐章艳, 宋? 威, 杨炳
儒等. 关于. 两种新的决策表属性约简概念/ 的注记. 小型微型计算机系统, 2007, 9( 9): 1686~ 1690).
[ 23] Huang B, Zhou X Z, Shi Y C. Entropy of knowledge and rough set based on general binary relation. Systems Engineering- T heory and
Practice, 2004, 24( 1): 93~ 96. ( 黄兵, 周献中, 史迎春. 基于一般二元关系的知识粗糙熵和粗集粗糙熵. 系统工程理论与实践, 2004, 24 (1) : 93~ 96).
[ 24] He X G, Huang B, Wen P C. A heuristic algorithm for reduction of knowledge under incomplete information systems. Piezoelectrics and
Acoustooptics, 2004, 26( 2): 158~ 160. ( 何先刚, 黄兵, 温平川. 不完备信息系统中知识约简的一种启发式算法. 压电与声光, 2004, 26 (2) : 158~ 160).
[ 25] He L, Hu F. Attribute reduction algorithm based on tolerance relation under attribute order. Computer Applications, 2008, 28 ( 9): 2443~ 2445. ( 何利, 胡峰. 属性序下基于容差关系的属性约简算法. 计算机应用, 2008, 28(9) : 2443~ 2445).
[ 26] Sun L, Xu J C, M a Y Y. Algorithm for rules extraction of decision tree based on decision information entropy. Computer Technology and Development, 2007, 17( 6) : 97~ 100. (孙? 林,
徐久成, 马媛媛. 基于决策熵的决策树规则提取方法. 计算机技术与发展, 2007, 17( 6) : 97~ 100) .
[ 27] Hu F, Zhang J, Liu J, et al. Knowledge reduction for huge data based on rough set theory. Journal of Chongqing University of Posts and
Telecommunications( Natural Sciences), 2009,21( 4) : 455~ 461. (胡峰, 张杰, 刘静等. 一种基于 Rough 集的海量数据属性约简方法. 重庆邮电大学学报( 自然科学) , 2009, 21( 4) : 455~ 461) .
[ 28] Wu X D, Zhang S C. Synthesizing high-fre quency rules form different data sources. IEEE Transaction on Knowledge and Data Engineering, 2003, 15( 2) : 353~ 367.
[ 29] Zheng Z, Wang G Y. RRIA: A rough set and rule tree based incremental knowledge acquisition algorithm. Fundamenta Informaticae, 2004, 59(3- 3) : 299~ 314.
[ 30] Wang G Y, Zheng Z, Zhang Y. RIDAS - A rough set based intelligent data analysis system. The 1 st International Conference on Machine Learning and Cybernetics ( ICMLC2002) , 2002: 646~ 649.
[ 31] Hu F, Wang G Y. Quick reduction algorithm based on attribute order. Chinese Journal of Compuers, 2007, 30( 8) : 1429~ 1435) . ( 胡峰, 王国胤. 属性序下的快速约简算法. 计算机学报, 2007, 30(8): 1429~ 1435) .
[ 32] Hu F, Wang G Y. Analysis of the complexity of quick sort for two dimension table. Chinese Journal of Computers, 2007, 30( 6): 693~ 698.
(胡峰, 王国胤. 二维表快速排序的复杂度分析. 计算机学报, 2007, 30( 6) : 963~ 968) .
[ 33] Liu S H, Sheng Q J, Wu B, et al. Research on efficient algorithms for rough set methods. Chinese Journal of Computers, 2003, 5( 26) : 524~
529. (刘少辉, 盛球戬, 吴? 斌等. Rough 集理论高效算法的研究. 计算机学报, 2003, 5( 26): 524~ 529).
[ 34] Zhang Y P, Du L, Zhao S. Increment learning algorithm for structural covering method. Journal of Nanjing University ( Natural Sciences),
2009, 45( 5): 699~ 704. ( 张燕平, 杜玲, 赵姝. 构造性覆盖方法的增量学习算法. 南京大学学报( 自然科学), 2009, 45(5): 699~ 704).