不协调信息系统快速属性分布约简方法

蒋云良; 杨章显; 刘勇

doi:10.3724/SP.J.1004.2012.00382

不协调信息系统快速属性分布约简方法

doi: 10.3724/SP.J.1004.2012.00382

蒋云良^1,2,3,
杨章显^2,3,
刘勇²

1.
湖州师范学院信息与工程学院湖州 313000;
2.
浙江大学工业控制国家重点实验室杭州 310027;
3.
杭州电子科技大学计算机学院杭州 310018

计量
- 文章访问数: 1899
- HTML全文浏览量: 68
- PDF下载量: 1003
- 被引次数: 0
出版历程
- 收稿日期: 2011-04-11
- 修回日期: 2011-10-28
- 刊出日期: 2012-03-20

Quick Distribution Reduction Algorithm in Inconsistent Information System

1.
School of Information and Engineering, Huzhou Teachers College, Huzhou 313000;
2.
National Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou 310027;
3.
School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018

摘要

摘要: 以条件信息熵为属性选择准则, 设计了基于哈希(Hash)分类的启发式后向贪心算法, 该算法以时间复杂度O (|A| |U| )求解不协调信息系统的分布约简, 其中|A| 是条件属性个数, |U| 是记录数, 并通过实验验证该算法的高效率.
- 不协调信息系统 /
- 分布约简 /
- 条件信息熵 /
- 哈希
Abstract: In this paper, the conditional entropy based criteria is adopted to select proper attribute distribution reduction in an inconsistent information system. The quick distribution reduction algorithm proposed in this paper employees a hash based heuristic backward greedy policy, which could achieve a time complexity of O(|A| |U| ), where |A| is the number of conditional attributes in the inconsistent information system, and |U| is the number of records in the inconsistent information system. At last, the efficiency of the quick distribution reduction algorithm is proved by comparable experiments.
- Inconsistent information system /
- distribution reduction /
- conditional information entropy /
- hash

HTML全文

参考文献(1)

[1]

Pawlak Z, Skowron A. Rudiments of rough sets. Information Sciences, 2007, 177(1): 3-27[2] Zhang Wen-Xiu, Wu Wei-Zhi, Liang Ji-Ye, Li De-Yu. Rough Set Theory and Approach. Beijing: Science Press, 2001(张文修, 吴伟志, 梁吉业, 李德玉. 粗糙集理论与方法. 北京: 科学出版社, 2001)[3] Wang Guo-Yin. Rough Set Theory and Knowledge Acquisition. Xi'an: Xi'an Jiaotong University Press, 2001(王国胤. Rough集理论与知识获取. 西安: 西安交通大学出版社, 2001)[4] Pawlak Z, Skowron A. Rough sets: some extensions. Information Sciences, 2007, 177(1): 28-40[5] Wang Jue, Wang Ren, Miao Duo-Qian, Guo Meng, Ruan Yong-Shao, Yuan Xiao-Hong, Zhao Kai. Data enriching based on rough set theory. Chinese Journal of Computers, 1998, 21(5): 393-400(王珏, 王任, 苗夺谦, 郭萌, 阮永韶, 袁小红, 赵凯. 基于Rough Set理论的"数据浓缩". 计算机学报, 1998, 21(5): 393-400)[6] Miao Duo-Qian, Hu Gui-Rong. A heuristic algorithm for reduction of knowledge. Journal of Computer Research and Development, 1999, 36(6): 681-684(苗夺谦, 胡桂荣. 知识约简的一种启发式算法. 计算机研究与发展, 1999, 36(6): 681-684)[7] Liu Yong, Xiong Rong, Chu Jian. Quick attribute reduction algorithm with Hash. Chinese Journal of Computers, 2009, 32(8): 1493-1499(刘勇, 熊蓉, 褚健. Hash快速属性约简算法. 计算机学报, 2009, 32(8): 1493-1499)[8] Skowron A, Rauszer C. The discernibility matrices and functions in information systems. Intelligent Decision Support: Handbook of Applications and Advances to Rough Sets Theory. Dordrecht: Kluwer Academic Publishers, 1992. 331-362[9] Zhong N, Dong J, Ohsuga S. Using rough sets with heuristics for feature selection. Journal of Intelligent Information Systems, 2001, 16(3): 199-214[10] Zhang Wen-Xiu, Mi Ju-Sheng, Wu Wei-Zhi. Knowledge reductions in inconsistent information systems. Chinese Journal of Computers, 2003, 26(1): 12-18(张文修, 米据生, 吴伟志. 不协调目标信息系统的知识约简. 计算机学报, 2003, 26(1): 12-18)[11] Yang Ming. An incremental updating algorithm of the computation of a core based on the improved discernibility matrix. Chinese Journal of Computers, 2006, 29(3): 407-413(杨明. 一种基于改进差别矩阵的核增量式更新算法. 计算机学报 2006, 29(3): 407-413)[12] Yang Ming. An incremental updating algorithm for attribute reduction based on improved discernibility matrix. Chinese Journal of Computers, 2007, 30(5): 815-822(杨明. 一种基于改进差别矩阵的属性约简增量式更新算法. 计算机学报, 2007, 30(5): 815-822)[13] Yao Y Y, Zhao Y. Discernibility matrix simplification for constructing attribute reducts. Information Sciences, 2009, 179(7): 867-882[14] Wang X L, Ma Y J, Li X. Data mining in inconsistent data. In: Proceedings of the International Conference on Internet Technology and Applications. Wuhan, China: IEEE, 2010. 1-5[15] Pei X B, Wang Y Z. Novel approaches to knowledge reduction in inconsistent decision systems. In: Proceedings of the IEEE International Conference on Natural Language Processing and Knowledge Engineering. Wuhan, China: IEEE, 2005. 746-749[16] Chen D G, Wang C Z, Hu Q H. A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets. Information Sciences, 2007, 177(17): 3500-3518[17] Leung Y, Ma J M, Zhang W X, Li T J. Dependence-space-based attribute reductions in inconsistent decision information systems. International Journal of Approximate Reasoning, 2008, 49(3): 623-630[18] Miao D Q, Zhao Y, Yao Y Y, Li H X, Xu F F. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model. Information Sciences, 2009, 179(24): 4140-4150[19] Qian Y H, Liang J, Li D Y, Wang F, Ma N N. Approximation reduction in inconsistent incomplete decision tables. Knowledge-Based Systems, 2010, 23(5): 427-433[20] Kryszkiewicz M. Comparative studies of alternative type of knowledge reduction in inconsistent systems. International Journal of Intelligent Systems, 2001, 16(1): 105-120[21] Wang Guo-Yin, Yu Hong, Yang Da-Chun. Decision table reduction based on conditional information entropy. Chinese Journal of Computers, 2002, 25(7): 759-766(王国胤, 于洪, 杨大春. 基于条件信息熵的决策表约简. 计算机学报, 2002, 25(7): 759-766)[22] Yuan Xiu-Jiu, Zhang Wen-Xiu. Studies on equivalence of the distribution reduction and the strictly convex function based reduction in decision tables. Systems Engineering, 2003, 21(5): 5-7(袁修久, 张文修. 决策表的分布约简和严凸函数下约简的等价性. 系统工程, 2003, 21(5): 5-7)[23] Wang G Y. Algebra view and information view of rough sets theory. Proceedings of SPIE, 2001, 4384: 200-207

施引文献

资源附件(0)

访问统计