|
|
|
| Fast Attribute Reduction Algorithm Based on Row Storage |
| LIANG Bao-Hua, WANG Shi-Yi |
| College of Information Engineering, Chaohu University, Hefei 238000 |
|
|
|
|
Abstract The existing attribute reduction algorithms mainly focus on the area of resident data in the memory. To decrease the accessing disk I/O times, a row storage mode is proposed. In this mode, not all data are required storing in the main memory. During the reducing process, the sub divisions of same category are collected into one array to get the simplified decision table quickly. Meanwhile, the indiscernibility degree is introduced as the measurement of the attribute importance. Then, a fast attribute reduction algorithm is proposed. Its time complexity and space complexity are low. The examples and experimental results show the effectiveness and feasibility of the proposed algorithm.
|
|
Received: 11 July 2014
|
|
|
|
|
|
[1] Pawlak Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11(5): 341-365
[2] Wang G Y. Rough Sets Theory and Knowledge Acquisition. Xi′an, China: Xi′an Jiaotong University Press, 2001 (in Chinese)
(王国胤.Rough集理论与知识获取.西安:西安交通大学出版社, 2001)
[3] Xu Z Y, Liu Z P, Yang B R, et al. A Quick Attribute Reduction Algorithm with Complexity of max(O(CU),O(C2U/C)). Chinese Journal of Computers, 2006, 29(3): 391-399 (in Chinese)
(徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(CU),O(C2U/C))的快速属性约简算法.计算机学报, 2006, 29(3): 391-399)
[4] Liu S H, Sheng Q J, Wu B, et al. Research on Efficient Algorithms for Rough Set Methods. Chinese Journal of Computers, 2003, 26(5): 524-529 (in Chinese)
(刘少辉,盛秋戬,吴 斌,等.Rough集高效算法的研究.计算机学报, 2003, 26(5): 524-529)
[5] Zhang W X, Mi J S, Wu W Z. Knowledge Reductions in Inconsistent Information Systems. Chinese Journal of Computers, 2003, 26(1): 12-18 (in Chinese)
(张文修,米据生,吴伟志.不协调目标信息系统的知识约简.计算机学报, 2003, 26(1): 12-18)
[6] 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 (in Chinese)
(王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759-766)
[7] Hu K Y. Research on Concept Lattice and Rough Set Based Data Mining Methods. Ph.D Dissertation. Beijing, China: Tsinghua University, 2001 (in Chinese)
(胡可云.基于概念格和粗糙集的数据挖掘方法研究.博士学位论文.北京:清华大学, 2001)
[8] Han S Q, Wang J. Reduct and Attribute Order. Journal of Computer Science and Technology, 2004, 19(4): 429-449
[9] Tao Z, Xu B D, Wang D W, et al. Rough Set Knowledge Reduction Approach Based on GA. Systems Engineering, 2003, 21(4): 116-122 (in Chinese)
(陶 志,许宝栋,汪定伟,等.基于遗传算法的粗糙集知识约简方法.系统工程, 2003, 21(4): 116-122)
[10] Zhu J H, Pan F. Rough Set Knowledge Reduction Based on Ant Colony Algorithm. Journal of Southeast University: Natural Science Edition, 2005, 35(Z2): 63-66 (in Chinese)
(朱江华,潘 丰.基于蚁群算法的粗糙集知识约简.东南大学学报:自然科学版, 2005, 35(Z2): 63-66)
[11] Wong S K M, Ziarko W. On Optimal Decision Rules in Decision Tables. Bulletin of the Polish Academy of Sciences Mathematics, 1985, 33(11/12): 693-696
[12] Liu Y, Xiong R, Chu J. Quick Attribute Reduction Algorithm with Hash. Chinese Journal of Computers, 2009, 32(8): 1493-1499 (in Chinese)
(刘 勇,熊 蓉,褚 健.Hash快速属性约简算法.计算机学报, 2009, 32(8): 1493-1499)
[13] Liang B H, Wang S Y, Cai M. Heuristic Attribute Reduction Algorithm Based on Order Table. Computer Engineering, 2012, 38(2): 51-53 (in Chinese)
(梁宝华,汪世义,蔡 敏.基于顺序表的启发式属性约简算法.计算机工程, 2012, 38(2): 51-53)
[14] Yang M. An Incremental Updating Algorithm for Attribute Reduction Based on Improved Discernibility Matrix. Chinese Journal of Computers, 2007, 30(5): 815-822 (in Chinese)
(杨 明.一种基于改进差别矩阵的属性约简增量式更新算法.计算机学报, 2007, 30(5): 815-822) |
|
|
|
2015, Vol. 28 
