一种改进的基于相对正域的增量式属性约简算法

广西师范大学学报（自然科学版） ›› 2013, Vol. 31 ›› Issue (3): 45-50.

一种改进的基于相对正域的增量式属性约简算法

申雪芬, 谢王君, 刘海峰, 续欣莹

太原理工大学信息工程学院,山西太原030024

收稿日期:2013-06-05 出版日期:2013-09-20 发布日期:2018-11-26
通讯作者: 谢王君(1979—),女,山西五台人,太原理工大学副教授,博士。E-mail:xiejun@tyut.edu.cn
基金资助:
国家自然科学基金资助项目(60975032);山西省回国留学人员科研资助项目(2008-25);山西省青年科技研究基金资助项目(2009021017-4);山西省回国留学人员科研资助项目(2013-033)

Improved Incremental Attribute Reduction Algorithm Based on Relative Positive Region

SHEN Xue-fen, XIE Jun, LIU Hai-feng, XU Xin-ying

Department of Information Engineering,Taiyuan University of Technology,Taiyuan Shanxi 030024,China

Received:2013-06-05 Online:2013-09-20 Published:2018-11-26

摘要/Abstract

摘要： 当决策系统增加新数据时,原约简集可能不再有效,这就需要对原约简集进行动态更新,目前已有的增量算法只研究了属性或样本的动态增加。本文从邻域粗糙集理论出发,详细分析系统在增加属性和样本数据后的变化规律,得到一种改进的增量式属性约简算法。该算法利用相对正域的概念对原约简集进行动态更新,可以处理属性和样本都增加的决策系统,有效地避免了二次约简过程。从理论上分析该算法的时间复杂度,实例表明该算法和传统算法的结论是一致的,实验证明该算法提高了计算效率。

关键词: 邻域系统, 增量式学习, 相对正域, 属性约简

Abstract: The original reduction set may be invalid when new data are added to the decision system.Most of the existing incremental algorithms focus on increasing attributes or increasing samples.This paper analyzes the changing rules of the decision system after adding new attributes and samples.An improved incremental attribute reduction algorithm is presented with the framework of neighborhood rough sets,which can update the original reduction set dynamically by using the idea of relative positive region,and handle the two situations of incremental data mentioned above at the same time.The time complexity of the presented algorithm was analyzed and compared with the classical algorithm.The experiment results show that this conclusion accords with the attribute reduction obtained from traditional algorithm and the efficiency is improved.

Key words: neighborhood system, incremental learning, relative positive region, attribute reduction

中图分类号:

TP181

申雪芬, 谢王君, 刘海峰, 续欣莹. 一种改进的基于相对正域的增量式属性约简算法[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 45-50.

SHEN Xue-fen, XIE Jun, LIU Hai-feng, XU Xin-ying. Improved Incremental Attribute Reduction Algorithm Based on Relative Positive Region[J]. Journal of Guangxi Normal University(Natural Science Edition), 2013, 31(3): 45-50.

参考文献

[1] PAWLAK Z.Rough set:theoretical aspects of reasoning about data[M].Netherlands:Kluwer Academic Publishers,1991:205-219.
[2] LIN T Y.Granular computing:practices,theories,and future directions[C]//Encyclopedia on Complexity of Syetems Science.Berlin:Springer,2009:4339-4355.
[3] HU Qing-hua,YU Da-ren,XIE Zong-xia.Neighborhood classifiers[J].Expert Systems with Applications,2008,34(2):866-876.
[4] 胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3):640-649.
[5] GUAN Li-he.An incremental updating algorithm of attribute reduction set in decision tables[C]//Sixth International Conference on Fuzzy Systems and Knowledge Discovery.Los Alamitos,CA:IEEE Computer Society,2009:421-425.
[6] 刘德银,刘文奇.一种增量式属性最小约简的粗糙集算法[J].计算机应用与软件,2011,28(9):257-259.
[7] 杨明.一种基于改进差别矩阵的属性约简增量式更新算法[J].计算机学报,2007,30(5):815-821.
[8] 李楠,谢娟英.基于邻域粗糙集的增量特征选择[J].计算机技术与发展,2011,21(11):149-155.
[9] 周君仪,杨习贝,杨静宇.邻域系统分层递阶结构分析[J].计算机科学与探索,2012,6(3):275-180.
[10] 杨习贝,杨静宇.邻域系统粗糙集模型[J].南京理工大学学报,2012,36(2):291-295.
[11] WANG Hui.Nearest neighbors by neighborhood counting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(6):942-953.
[12] 钱文彬,杨炳儒,徐章艳.一种基于决策表的属性约简增量式快速更新算法[J].小型微型计算机系统,2012,33(2):254-258.
[13] 王珏,石纯一.机器学习研究[J].广西师范大学学报:自然科学版,2003,21(2):1-15.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed