南京大学学报(自然科学版) ›› 2010, Vol. 46 ›› Issue (5): 477–486.

• •    下一篇

 基于决策熵的值约简算法*

 胡 峰 1 , 张杰 1 ** , 吉朝明 2 , 易兴辉 1   

  • 出版日期:2015-04-02 发布日期:2015-04-02
  • 作者简介: (1. 重庆邮电大学计算机科学与技术研究所, 2. 移动通信技术重点实验室, 重庆, 400065)
  • 基金资助:
     国家自然科学基金( 60573068, 60773113) , 重庆市自然科学基金( 2008BA2017, 2008BA2041) , 重庆市教育委员会
    科学技术研究项目( KJ090512)

 Value reduction algorithm based on decision information entropy

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

  • Online:2015-04-02 Published:2015-04-02
  • About author: (1. Institute of Computer Science and Technology, 2. Key Laboratory of Mobile Communications T echnology,
    Chongqing University of Post and Telecommunications, Chongqing, 400065, China)

PDF (PC)

680

摘要：   值约简是 Rough 集理论研究的核心内容之一, 高效的值约简算法可以有助于快速做出决策.目前的值算法要么识别率不高, 要么时间复杂度较高, 而且也不能客观地反映决策规则的决策能力的变
化情况. 为了尽量克服这些缺点, 文中利用置信度的概念以及决策熵能客观反映决策规则的决策能力的变化情况的优势, 提出了一种基于决策熵的值约简算法. 本算法采用了等价划分和容差关系在属性空间
上对决策表分解, 再根据置信度和决策熵判断每条决策规则中属性值是否该删除, 并最终得到正确识别率上接近已有的确定规则获取算法的识别率, 并且运行时间较低的结果. 文中算法给出了详细地步骤以
及相关实例说明, 并将本算法与启发式值约简和基于决策矩阵的值约简算法做对比实验, 实验结果表明, 文中算法是一种可行性的值约简方法.

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.

 [ 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).
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司