Attribute reduction is one of the key issues in rough set theory, and many algorithms have been proposed for static data set. Very little work has been done for incremental attribute reduction algorithm in era of big data. In this paper, the weakness of the existing incremental attribute reduction are analyzed. Then, two strategies of incremental attribute reduction algorithm for big data are designed, and an incremental attribute reduction algorithm using MapReduce is proposed. In order to reduce the computational complexity, our algorithm reuse the former Map results to speedup the computations of the equivalence classes. A new reduct can be updated by the old reduct effectively. This study gives some insights into how to conduct incremental attribute reduction for big data.
PawlakZ., Rough sets, International Journal of Computer and Information Sciences11 (1982), 341-356.
2.
SkowronxA. and SkowronC., The discernibility matrices and functions in information systems, in: Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory, SlowińskiR., ed., Kluwer, Dordrecht, 1992, pp. 331-362.
3.
QianY.H., LiangJ.Y., PedryczW. and DangC.Y., Positive approximation: An accelerator for attribute reduction in rough set theory, Artificial Intelligence174 (2010), 597-618.
4.
QianJ., MiaoD.Q., ZhangZ.H. and LiW., Hybrid approaches to attribute reduction based on indiscernibility and discernibility relation, International Journal of Approximate Reasoning52 (2011), 212-230.
5.
YangM., An incremental updating algorithm for attribute reduction based on improved discernibility matrix, Chinese Journal of Computers30 (2007), 815-822. (in Chinese)
6.
FanY.N., TsengT.L., ChernC.C. and HuangC.C., Rule induction based on an incremental rough set, Expert Systems with Applications36 (2009), 11439-11450.
7.
FengS.R. and ZhangD.Z., Effective incremental algorithm for attribute reduction, Control and Decision26(4) (2011), 495-500. (in Chinese)
8.
ZhangC.S. and RuanJ., An efficient incremental updating algorithm for knowledge reduction in information system, Electronics and Signal Processing97 (2011), 263-271.
9.
ZhangJ.B., LiT.R. and RuanD., Rough sets based incremental rule acquisition in set-valued information systems, Autonomous Systems: Developments and Trends391 (2012), 135-146.
10.
YinL.Z., YangC.H., WangX.L. and GuiW.H., An incremental algorithm for attribute reduction based on labeled discernibility matrix, Acta Automatica Sinica40(3) (2014), 397-404. (in Chinese)
11.
JingY.G., LiT.R., LuoC., HorngS.J., WangG.Y. and YuZ., An incremental approach for attribute reduction based on knowledge granularity, Knowledge-Based Systems104 (2016), 24-38.
12.
LuoC., LiT.R. and ChenH.M., Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization, Information Science257 (2014), 210-228.
13.
WangF., LiangJ.Y. and QianY.H., Attribute reduction: A dimension incremental strategy, Knowledge-Based System39 (2013), 95-108.
14.
WangF., LiangJ.Y., DangC.Y. and QianY.H., Attribute reduction for dynamic data sets, Applied Soft Computing13(1) (2013), 676-689.
15.
ChenH.M., LiT.R., LuoC., HorngS.J. and WangG.Y., A rough set-based method for updating decision rules on attribute values' coarsening and refining, IEEE Trans Knowl Data Eng26(12) (2014), 2886-2899.
16.
QianJ., YeF.Y. and LvP., 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, 4 (2010), 1848-1852.
17.
LiangJ.Y., WangF., DangC.Y. and QianY.H., A group incremental approach to feature selection applying rough set technique, IEEE Transactions on Knowledge and Data Engineering26(2) (2014), 294-308.
18.
DeanJ. and GhemawatS., MapReduce: Simplified data processing on large clusters, Communications of the ACM51 (2008), 107-114.
19.
QianJ., MiaoD.Q., ZhangZ.H. and YueX.D., Parallel attribute reduction algorithms using MapReduce, Information Sciences279 (2014), 671-690.
20.
LeeD. and KimJ.-S. and MaengS., Large-scale incrmental processing with MapReduce, Future Generation Computer Systems36 (2014) 66-79.
21.
ZhangJ.B., LiT.R., PanY., LuoC. and TengF., Parallel and Incremental algorithm for knowledge update based on rough sets in cloud platform, Journal of Software26 (2015), 1064-1078.
