An Incremental Attribute Reduction Algorithm in Incomplete System

doi:10.3969/j.issn.1006-2475.2019.08.013

Abstract

Abstract: In practical applications, the data of information system is often dynamic. When the object is increased, the original attribute reduction set is not necessarily effective. An incremental attribute reduction algorithm based on the conditional entropy is proposed for the situation of incomplete decision system object being increased. Firstly, the conditional entropy in an incomplete decision system is defined, then the change mechanism of the conditional entropy and the influence on the reduction set are analyzed when the object is increased. An incremental attribute reduction algorithm is proposed, when the object is increased, the algorithm can be more efficient to reduce the attribute. Finally, experiments verify the effectiveness and efficiency of the proposed algorithm.

Key words: incomplete decision system, attribute reduction, conditional entropy, reduction set； incremental

CLC Number:

TP18

WANG Guang-qiong1,2 . An Incremental Attribute Reduction Algorithm in Incomplete System[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.08.013.

References

［1］ MAHAJAN P, KANDWAL R, VIJAY R. Rough set approach in machine learning: A review［J］. International Journal of Computer Applications, 2012,56(10):1-13.
［2］李华,江峰,于旭,等. 基于粒度决策熵的属性约简［J］. 计算机与现代化, 2018(4):7-12.
［3］高灿,周杰,高天宇,等. 不完备弱标记数据的粗糙协同学习模型［J］. 模式识别与人工智能, 2018,31(10):950-957.
［4］王宁,刘海园,周雪珂. 基于粗糙集的应急案例中概率规则挖掘方法［J］. 运筹与管理, 2018,27(12):84-94.
［5］张婷,张红云,王真. 基于三支决策粗糙集的迭代量化的图像检索算法［J］. 南京大学学报(自然科学), 2018,54(4):714-724.
［6］陈静雯,马福民,张腾飞,等. 基于最大粒的悲观邻域多粒度粗糙集规则获取算法［J］. 模式识别与人工智能, 2017,30(11):1048-1056.
［7］王妍,王凤桐,王俊陆,等. 基于泛化中心聚类的不完备数据集填补方法［J］. 小型微型计算机系统, 2017,38(9):2017-2021.
［8］武森,冯小东,单志广. 基于不完备数据聚类的缺失数据填补方法［J］. 计算机学报, 2012,35(8):1726-1738.
［9］王俊陆,王玲,王妍,等. 基于元组相似度的不完备数据填补方法研究［J］. 计算机科学, 2017,44(2):98-102，106.
［10］KRYSZKIEWICZ M. Rough set approach to incomplete information systems［J］. Information Sciences, 1998,112(1-4):39-49.
［11］STEFANOWSKI J， TSOUKIAS A. On the extension of rough sets under incomplete information［C］// International Workshop on New Directions in Rough Sets, Data Mining, and Granular-Soft Computing. 1999:73-81.
［12］王国胤. Rough集理论在不完备信息系统中的扩充［J］. 计算机研究与发展, 2002,39(10):1238-1243.
［13］WANG G Y, GUAN L H. Data-driven valued tolerance relation［C］// International Conference on Rough Sets & Knowledge Technology. 2012:11-19.
［14］杨习贝,颜旭,徐苏平,等. 基于样本选择的启发式属性约简方法研究［J］. 计算机科学, 2016,43(1):40-43.
［15］常红岩,蒙祖强. 一种新的决策粗糙集启发式属性约简算法［J］. 计算机科学, 2016,43(6):218-222.
［16］续欣莹,张扩,谢珺,等. 基于互信息下粒子群优化的属性约简算法［J］. 电子学报, 2017，45(11):2695-2704.
［17］韩丽丽,李龙澍. 基于Pawlak的决策粗糙集的属性约简研究［J］. 计算机与现代化, 2013(7):56-58.
［18］陈鑫影,李冠宇,刘彦含. 基于决策依赖度的粗糙集约简模型研究［J］. 系统工程理论与实践, 2016,36(2):505-516.
［19］WU W Z. Attribute reduction based on evidence theory in incomplete decision systems［J］. Information Sciences, 2008,178(5):1355-1371.
［20］王婷,徐章艳,朱金虎,等. 高效的不完备决策系统属性约简算法［J］. 小型微型计算机系统, 2016,37(7):1551-1556.
［21］杨霁琳,秦克云,裴峥. 不完备决策表中基于相似关系的属性约简［J］. 计算机工程, 2010,36(20):10-12.
［22］金玲玲,王喜凤,朱紫焱. 不完备信息系统的增量式约简算法［J］. 辽宁工程技术大学学报（自然科学版）, 2012，31(2):284-288.
［23］丁棉卫,张腾飞,马福民. 基于二进制区分矩阵的不完备系统增量式属性约简算法［J］. 计算机科学, 2017,44(7):244-250.
［24］滕书华,周石琳,孙即祥,等. 基于条件熵的不完备信息系统属性约简算法［J］. 国防科技大学学报, 2010,32(1):90-94.

[1]	LI Hua, JIANG Feng, YU Xu, DU Junwei, LIU Guozhu. Attribute Reduction Based on Granularity Decision Entropy [J]. Computer and Modernization, 2018, 0(04): 7-.
[2]	ZHAI Jun-chang1, CHE Wei-wei2. A Spam Filtering Algorithm Based on Conditional Entropy [J]. Computer and Modernization, 2014, 0(2): 129-132.
[3]	LU Guang;LI Xiang;WANG Biao. An Efficient Attribute Reduction Algorithm [J]. Computer and Modernization, 2013, 1(8): 68-72,7.
[4]	HAN Li-li;LI Long-shu. Researh on Attribute Reduction of Decision-theoretic Rough Set Model Based on Pawlak [J]. Computer and Modernization, 2013, 1(7): 56-058.
[5]	QI Yan-jun;ZHANG Bing-yi;FENG Zhi-yong . Game Level Automatic Generating Method Based on Data Mining and Data Fusion [J]. Computer and Modernization, 2013, 1(4): 10-14.
[6]	XIA Xianzhi;DU Xinyu;ZHENG Yangfei. Attribute Reduction Based on Ant Colony Genetic Algorithm [J]. Computer and Modernization, 2013, 1(1): 25-28.
[7]	WAN Fang;DENG Shao-bo;CHEN Lian;LIU Qing;. Attribute Value and Attribute Reduction Method Based on Consistent Decision Tables [J]. Computer and Modernization, 2012, 1(9): 61-64,1.
[8]	GAO Xiao-hong. Novel Attribute Reduction Algorithm of Decision System Based on Classification Quality [J]. Computer and Modernization, 2010, 1(01): 19-22.
[9]	WANG feng ;HOU haiping;SUN hui. Modified Heuristic Genetic Algorithm for Reduction of Attributes [J]. Computer and Modernization, 2008, 1(10): 1-4.