An Incremental Algorithm for Attribute Reduction Based on Labeled Discernibility Matrix
-
摘要: 针对现有增量式属性约简算法中存在的约简传承性差以及不完备现象,提出基于标记可辨识矩阵的增量式属性约简算法.本文首先定义了标记函数,对样本之间的可辨识性进行分类,并将之引入一个新的可辨识矩阵,在新增样本时,结合标记信息可以快速识别可辨识矩阵元素集的异动,获得强传承性的约简超集,在此基础上,设计与标记可辨识矩阵匹配的必要矩阵,用以快速判断并删除冗余属性,确保约简的完备性. 理论分析以及实验测试表明,本算法具有约简传承性强,约简集完备等特点,具有较强的实用性.Abstract: In order to improve the inheritance rate of reducts and obtain the complete reducts, an incremental algorithm for attribute reduction based on labeled discernibility matrix is proposed. The label function is first defined to classify the discernibility relationships of all object pairs. The labeled discernibility matrix is then proposed to find out the changed elements and compute a supper set of reducts quickly when a new object is added. At the same time, a necessary matrix corresponding to the labeled discernibility matrix is presented. It is used to delete the redundant attributes for a complete reduct. Theoretical analysis and experimental results show that the reducts calculated by the proposed algorithm are complete and have the characteristic of high inheritance rate.
-
[1] Xiao Di, Hu Shou-Song. Real rough set theory and attribute reduction. Acta Automatica Sinica, 2007, 33(3): 253-258(肖迪, 胡寿松. 实域粗糙集理论及属性约简. 自动化学报, 2007, 33(3): 253-258) [2] Yin Lin-Zi, Yang Chun-Hua, Gui Wei-Hua, Li Yong-Gang. Hierarchical reduction of rules. CAAI Transactions on Intelligent Systems, 2008, 3(6): 492-497(尹林子, 阳春华, 桂卫华, 李勇刚. 规则分层约简算法. 智能系统学报, 2008, 3(6): 492-497) [3] [3] Fan Y N, Tseng T L, Chern C C, Huang C C. Rule induction based on an incremental rough set. Expert Systems with Applications, 2009, 36(9): 11439-11450 [4] [4] Fan Y N, Chern C C. An agent model for incremental rough set-based rule induction in customer relationship management. Hybrid Artificial Intelligent Systems, 2012, 7208: 1-12 [5] [5] Zhang J B, Li T R, Ruan D. Rough sets based incremental rule acquisition in set-valued information systems. Autonomous Systems: Developments and Trends, 2012, 391: 135-146 [6] [6] Hu F, Wang G Y, Huang H, Wu Y. Incremental attribute reduction based on elementary sets. In: Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Regina, Canada: Springer-Verlag, 2005. 185-193 [7] Hu Feng, Dai Jin, Wang Guo-Yin. Incremental algorithms for attribute reduction in decision table. Control and Decision, 2007, 22(3): 268-272, 277(胡峰, 代劲, 王国胤. 一种决策表增量属性约简算法. 控制与决策, 2007, 22(3): 268-272, 277) [8] [8] Qian J, Ye F Y, Lv P. An incremental attribute reduction algorithm in decision table. In: Proceedings of the 7th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). Yantai, China: IEEE, 2010, 4: 1848-1852 [9] 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) [10] Feng Shao-Rong, Zhang Dong-Zhan. Effective increment algorithm for attribute reduction. Control and Decision, 2011, 26(4): 495-500(冯少荣, 张东站. 一种高效的增量式属性约简算法. 控制与决策, 2011, 26(4): 495-500) [11] Xu Y T, Wang L S, Zhang R Y. A dynamic attribute reduction algorithm based on 0-1 integer programming. Knowledge-Based Systems, 2011, 24(8): 1341-1347 [12] Jiang Yun-Liang, Yang Zhang-Xian, Liu Yong. Quick distribution reduction algorithm in inconsistent information system. Acta Automatica Sinica, 2012, 38(3): 382-388(蒋云良, 杨章显, 刘勇. 不协调信息系统快速属性分布约简方法. 自动化学报, 2012, 38(3): 382-388) [13] Yao Y Y, Zhao Y. Discernibility matrix simplification for constructing attribute reducts. Information Sciences, 2009, 179(7): 867-882 [14] Zhang C S, Ruan J. An efficient incremental updating algorithm for knowledge reduction in information system. Electronics and Signal Processing, 2011, 97: 263-271 [15] Liu Yang, Feng Bo-Qin, Zhou Jiang-Wei. Complete algorithm of increment for attribute reduction based on discernibility matrix. Journal of Xi'an Jiaotong University, 2007, 41(2): 158-161, 208 (刘洋, 冯博琴, 周江卫. 基于差别矩阵的增量式属性约简完备算法. 西安交通大学学报, 2007, 41(2): 158-161, 208)
点击查看大图
计量
- 文章访问数: 1726
- HTML全文浏览量: 91
- PDF下载量: 1152
- 被引次数: 0