|
|
|
| Efficient Incremental Updating Algorithm for Core AttributeBased on Information Entropy |
| QIAN Wen-Bin1,2,YANG Bing-Ru1,2,XU Zhang-Yan3,ZHANG Chang-Sheng1,2 |
1. School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083
2.Beijing Key Laboratory of Knowledge Engineering for Materials Science,University of Science and Technology Beijing,Beijing 10083
3.College of Computer Science and Information Technology,Guangxi Normal University,Guilin 541004 |
|
|
|
|
Abstract Since the efficiency of the algorithms for core attribute based on information entropy is not well,the binary discernibility matrix from information view is defined. And it is proved theoretically that the core attribute based on the binary discernibility matrix is equivalent to that based on information entropy. The objects in the decision table are categorized into a consistent set and an inconsistent set,which effectively reduces the search space of algorithm for core attribute. Additionally,for dynamic decision table,the incremental updating mechanism for core attribute is discussed. Based on the mechanism,an efficient incremental updating algorithm for core attribute based on information entropy is proposed. The example analysis and experimental results show that the proposed algorithm outperforms other similar algorithms.
|
|
Received: 10 May 2011
|
|
|
|
|
|
[1]Pawlak Z,Skowron A. Rudiments of Rough Sets. Information Sciences,2007,117(1): 3-27
[2] Pawlak Z. Skowron A. Rough Sets: Some Extensions.Information Sciences,2007,117(1): 28-40
[3] Chang Liyun,Wang Guoyin,Wu Yu. An Approach for Attribute Reduction and Rule Generation Based on Rough Set Theory. Journal of Software,1999,10(11): 1206-1211 (in Chinese)
(常犁云,王国胤,吴 渝.一种基于Rough Set理论的属性约简及规则提取方法.软件学报,1999,10(11): 1206-1211)
[4] Huang Bing,Zhou Xianzhong. Matrix Computation for Rule Extraction in Inconsistent Decision Tables. Systems Engineering and Electronics,2005,27(3): 441-445 (in Chinese)
(黄 兵,周献中.不一致决策表中规则提取的矩阵算法.系统工程与电子技术,2005,27(3): 441-445)
[5] Hu Feng,Wang Guoyin.Quick Algorithm for Certain Rule Acquisition Based on Divide and Conquer Method. Pattern Recognition and Artificial Intelligence,2010,23(3): 349-356 (in Chinese)
(胡 峰,王国胤.基于分治法的快速确定规则获取算法.模式识别与人工智能,2010,23(3): 349-356)
[6] Liu Shaohui,Sheng Qiujian,Wu Bin,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)
[7] Xu Zhangyan,Liu Zhuopeng,Yang Bingru. A Quick Attribution Reduction Algorithm with Complexity of max {O(UC),O(C2U/C)}. Chinese Journal of Computer,2006,29(3): 391-399 (in Chinese)
(徐章艳,刘作鹏,杨炳儒.一个复杂度为max{O(UC),O(C2U/C)}的快速属性约简算法.计算机学报,2006,29(3): 391-399)
[8] Hu Feng,Wang Guoyin. Quick Reduction Algorithm Based on Attribute Order. Chinese Journal of Computers,2007,30(8):1429-1435 (in Chinese)
(胡 峰,王国胤.属性序下的快速约简算法.计算机学报,2007,30(8): 1429-1435)
[9] Teng Shuhua,Zan Decai,Sun Jixiang,et al. Attribute Reduction Algorithm Based on Common Discernibility Degree. Pattern Recognition and Artificial Intelligence,2010,23(5): 630-638 (in Chinese)
(滕书华,昝德才,孙即祥,等.基于同可区分度的属性约简算法.模式识别与人工智能,2010,23(5): 630-638)
[10] Liu Shaohui,Sheng Qiujian,Shi Zhongzhi. A New Method for Fast Computing Positive Region. Journal of Computer Research and Development,2003,40(5): 637-642 (in Chinese)
(刘少辉,盛秋戬,史忠植.一种新的快速计算正区域的方法.计算机研究与发展,2003,40(5): 637-642)
[11] Ge Hao,Li Longshu,Yang Chuanjian. Quick Algorithm for Computing Core Attribute. Control and Decision,2009,24(5): 738-742 (in Chinese)
(葛 浩,李龙澍,杨传健.一种核属性快速求解算法.控制与决策,2009,24(5): 738-742)
[12] He Xiaohua,Cercone N. Learning in Relational Databases: A Rough Set Approach. Computational Intelligence,1995,11(2): 323-338
[13] Ye Dongyi,Chen Zhaojiong. A New Discernibility Matrix and the Computation of a Core. Acta Electronica Sinica,2002,30(7): 1086-1088 (in Chinese)
(叶东毅,陈昭炯.一个新的差别矩阵及其求核方法.电子学报,2002,30(7): 1086-1088)
[14] Wang Guoyin. Calculation Methods for Core Attributes of Decision Table. Chinese Journal of Computers,2003,26(5): 611-615 (in Chinese)
(王国胤.决策表核属性的计算方法.计算机学报,2003,26(5): 611-615)
[15] Liang Jiye,Wei Wei,Qian Yuhua. An Incremental Approach to Computation of a Core Based on Conditional Entropy,Systems Engineering—Theory Practice,2008,28(4): 81-89 (in Chinese)
(梁吉业,魏 巍,钱宇华.一种基于条件熵的增量核求解方法.系统工程理论与实践,2008,28(4): 81-89)
[16] Xu Zhangyan,Yang Bingru,Song Wei. Comparative Study of Different Attribute Reduction Based on Decision Table. Chinese Journal of Electronics,2006,15(4): 953-956 |
|
|
|
2013, Vol. 26 
