Computer Science ›› 2016, Vol. 43 ›› Issue (12): 71-78.doi: 10.11896/j.issn.1002-137X.2016.12.012

Previous Articles     Next Articles

Incrementally Updating Approximations Approach in Dominance-based Rough Set for Multi-criteria Classification Problems

LI Yan, JIN Yong-fei, WU Ting-ting, GUO Na-na and YU Qun   

  • Online:2018-12-01 Published:2018-12-01

Abstract: In the framework of dominance-based rough set approach(DRSA),dominance relations are used to handle preference ordered attributes contained in data and these attributes are also called as criteria.DRSA has been widely used in multi-criteria decision-making problems.In real applications,however,due to the variations of attribute set and object set,the information systems are often updated from time to time.Under such dynamic environment,the approximation sets in DRSA are required to be updated correspondingly for their future use in feature reduction,rule extraction,and finally in decision-making.In this paper,focusing on multi-criteria classification problems,we developed incremental methods to update set approximations when an object is inserted or deleted.The updating principles in difference cases were discussed and related theoretical results were given with detailed proofs.Two incremental algorithms,DRSA1 and DRSA2,were proposed to update approximations sets when an object is deleted or inserted respectively.Illustrative examples were also given to support the effectiveness of the proposed incremental methods.The experimental results on UCI data sets demonstrate the obvious improvement for non-incremental method (classic DRSA) in terms of efficiency and scalability by using the incremental approach.

Key words: Dominance relation-based rough set,Multi-criteria classification,Information system,Approximations,Incremental updating

[1] Pawlak Z.Rough sets:theoretical aspects of reasoning about data[M].Kluwer Academic Publishers,Dordrecht,1991
[2] Qian Y H,Liang J Y,Pedrycz W.An efficient accelerator for attribute reduction from incomplete data in rough set framework[J].Pattern Recognition,2011,44(8):1658-1670
[3] Liu F,Li T R.Method for Attribute Reduction Based on Rough Sets Boundary Regions[J].Computer Science,2016,3(3):242-284(in Chinese) 刘芳,李天瑞.基于边界域的不完备信息系统属性约简方法[J].计算机科学,2016,43(3):242-284
[4] Blaszczynski J,Greco S,Slowinski R.Inductive discovery of laws using monotonic rules[J].Engineering Applications of Artificial Intelligence,2012,25(2):284-294
[5] Abbas A,Liu J.Designing an intelligent recommender system using partial credit model and Bayesian rough set[J].Internatio-nal Arab Journal of Information Technology,2012,9(2):179-187
[6] Chang B,Hung H.A study of using RST to create the supplier selection model and decision making rules[J].Expert Systems with Applications,2010,37(12):8284-8295
[7] Jiao N.Research on Vertical Segmentation Knowledge Reduc-tion Algorithm Based on Tolerance Rough Set Theory[J].Computer Science,2016,43(1):49-52(in Chinese) 焦娜.相容关系下的分割知识约简算法的研究[J].计算机科学,2016,43(1):49-52
[8] Greco S,Matarazzo B,Slowinski R.Rough sets theory for multicriteria decision analysis[J].European Journal of Operational Research,2001,129(1):1-47
[9] Greco S,Matarazzo B,Slowinski R.Rough approximation bydominance relations[J].International Journal of Intelligent Systems,2002,17(2):153-171
[10] Greco S,Slowinski R,Matarazzo B,et al.Variable consistencymodel of dominance-based rough sets approach[C]∥Proc.of International Conference on Rough Sets and Current Trends in Computing.Springer-Verlage,2000:170-181
[11] Hu Q H,Yu D R,Guo M Z.Fuzzy preference based rough sets[J].Information Sciences,2010,180(10):2003-2022
[12] Hu Q H,Pan W W,Zhang L,et al.Feature selection for monotonic classification[J].IEEE Transactions on Fuzzy Systems,2012,20(1):69-81
[13] Hu Q H,Che X J,Zhang L,et al.Rank entropy based decision trees for monotonic classification[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(11):2052-2064
[14] Karami J,Alimohammadi A,Seifouri T.Water quality analysis using a variable consistency dominance-based rough set approach[J].Computers Environment and Urban Systems,2014,43(1):25-33
[15] Peters G,Poon S.Analyzing IT business values-A dominancebased rough sets approach perspective[J].Expert Systems with Applications,2011,8(9):11120-11128
[16] Liou J H,Tzeng G H.A dominance-based rough set approach to customer behavior in the airline market[J].Information Sciences,2010,180(11):2230-2238
[17] Huang B,Zhuang Y L,Li H X,et al.A Dominance Intuitionistic Fuzzy-Rough Set Approach and its Applications[J].Applied Mathematical Modeling,2013,37(12/13):7128-7141
[18] Chakhar S,Saad I.Dominance-based rough set approach forgroups in multicriteria classification problems[J].Decision Support Systems,2012,54(1):372-380
[19] Li T R,Ruan D,Geert W,et al.A rough sets based characteristic relation approach for dynamic attribute generalization in data mining[J].Knowledge-based Systems,2007,20(5):485-494
[20] Liu D,Li T R,Zhang J B.Incremental updating approximations in probabilistic rough sets under the variation of attributes[J].Knowledge-based Systems,2015,73(81):81-96
[21] Wang F,Liang J Y,Qian Y H.Attribute reduction:A dimension incremental strategy[J].Knowledge-Based Systems,2003,9(6):95-108
[22] Li S Y,Li T R,Liu D.Incremental updating approximations in dominance-based rough sets approach under the variation of the attribute set[J].Knowledge-based Systems,2013,40(1):17-26
[23] Chen H M,Li T R,Qiao S,et al.A rough set based dynamic maintenance approach for approximations in coarsening and refining attribute values[J].International Journal of Intelligent Systems,2010,25(10):1005-1026
[24] Chen H M,Li T R,Ruan D.Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining[J].Knowledge-Based Systems,2012,31(7):140-161
[25] Chen H M,Li T R,Ruan D.Dynamic maintenance of approximations under a rough-set based variable precision limited tole-rance relation[J].Journal of Multiple Valued Logic and Soft Computing,2012,18(5/6):577-598
[26] Li S Y,Li T R.Incremental update of approximations in dominance-based rough sets approach under the variation of attribute values[J].Information Sciences,2015,294(c):348-361
[27] Luo C,Li T R,Chen H M,et al.Fast algorithms for computing rough approximations inset-valued decision systems while updating criteria values[J].Information Sciences,2015,9(c):221-242
[28] Zhang J B,Li T R,Ruan D,et al.Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems[J].International Journal of Approximate Reaso-ning,2012,53(4):620-635
[29] Luo C,Li T R,Chen H M.Dynamic maintenance of approximations in set-valued ordered decision systems under the attribute generalization[J].Information Sciences,2014,257(2):210-228
[30] Shan N,Ziarko W.Data-based acquisition and incremental modification of classification rules[J].Computational Intelligence,1995,11(2):357-370
[31] Bang W C,Zeungnam B.New incremental learning algorithm in the framework of rough set theory[J].International Journal of Fuzzy Systems,1999,1(1) :25-36
[32] Tong L,An L.Incremental learning of decision rules based on rough set theory[J].Proc.of World Congress on Intelligent Control and Automation,2002,1(11):420-425
[33] Hu F,Wang G Y,Huang H,et al.Incremental attribute reduction based on elementary sets[M]∥Rough Sets,Fuzzy Sets,Data Mining,and Granular Computing.Springer Berlin Heidelberg,2005:185-193
[34] Jing Y G,Li T R,Huang J F,et al.An incremental attribute reduction approach based on knowledge granularity under the attribute generalization[J].International Journal of Approximate Reasoning,2016,76(6):80-95
[35] Jing Y G,Li T R,Luo C,et al.An incremental approach for attribute reduction based on knowledge granularity[J].Know-ledge-Based Systems,2016,4(1):24-38
[36] Shu W H,Shen H.Incremental feature selection based on rough set in dynamic incomplete data[J].Pattern Recognition,2014,7(12):3890-3906
[37] Liang J Y,Wang F,Dang C Y,et al.A group incremental approach to feature selection applying rough set technique[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(2):294-308
[38] Zhang J B,Li T R,Ruan D,et al.Neighborhood rough sets for dynamic data mining[J].International Journal of Intelligent Systems,2012,27(4):317-342
[39] Liu D,Li T R,Ruan D,et al.An incremental approach for inducing knowledge from dynamic information systems[J].Fundamenta Informaticae,2009,94(2):245-260
[40] Liu D,Li T R,Ruan D,et al.Incremental learning optimization on knowledge discovery in dynamic business intelligent systems[J].Journal of Global Optimization,2011,51(2):325-344
[41] Chen H M,Li T R,Ruan D,et al.A rough-set based incremental approach for updating approximations under dynamic maintenance environments[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(2):274-284
[42] Zhang J B,Li T R,Chen H M.Composite rough sets for dyna-mic data mining[J].Information Sciences,2014,257(2):81-100
[43] Luo C,Li T R,Chen H M,et al.Incremental approaches for updating approximations in set-valued ordered information systems[J].Knowledge-Based Systems,2013,50(50):218-233
[44] Li S Y,Li T R,Liu D.Dynamic maintenance of approximations in dominance-based rough set approach under the variation of the object set[J].International Journal of Intelligent Systems,2013,28(8):729-751
[45] Chen J,Wang G Y,Hu J.Positive domain reduction based on dominance relation in inconstant system[J].Computer Science,2008,35(3):216-218(in Chinese) 陈娟,王国胤,胡军.优势关系下不协调信息系统的正域约简[J].计算机科学,2008,5(3):216-218
[46] Li Y,Sun N X,Zhao J,et al.Reductions based on dominance-equivalence relations and rules extraction methods[J].Computer Science,2011,38(11):220-224(in Chinese) 李艳,孙娜欣,赵津,等.基于优势-等价关系的几种约简及规则抽取方法[J].计算机科学,2011,8(11):220-224
[47] Bache K,Lichma M.UCI Macine Learning Repository.

No related articles found!
Full text



No Suggested Reading articles found!