多准则分类问题中近似集的增量更新方法

doi:10.11896/j.issn.1002-137X.2016.12.012

摘要/Abstract

摘要： 在优势关系粗糙集方法(DRSA)的框架下,优势关系可用于处理带有序关系属性(准则)的数据,并且已经被广泛用于处理多准则决策问题。然而在实际应用中,当属性集和对象集发生变化时,信息系统会随之不断更新。在这种动态环境下,DRSA中用于属性约简、规则提取以及决策制定的近似集需要得到相应的更新。针对对象集发生变化时(增加或删除一个对象)的多准则分类问题,采用增量方法来更新近似集并提出两种相应的更新算法DRSA1和DRSA2。同时,对不同情况下的更新原则进行了讨论并给出了相关的理论结果与详细的证明。最后给出算例,并在UCI数据集上进行大量的实验,与非增量的方法(传统的DRSA)进行对比,结果充分体现了所提增量方法的有效性与可扩展性。

关键词: 优势关系粗糙集,多准则分类,信息系统,近似集,增量更新

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

李艳,靳永飞,吴婷婷,郭娜娜,于群. 多准则分类问题中近似集的增量更新方法[J]. 计算机科学, 2016, 43(12): 71-78. https://doi.org/10.11896/j.issn.1002-137X.2016.12.012

LI Yan, JIN Yong-fei, WU Ting-ting, GUO Na-na and YU Qun. Incrementally Updating Approximations Approach in Dominance-based Rough Set for Multi-criteria Classification Problems[J]. Computer Science, 2016, 43(12): 71-78. https://doi.org/10.11896/j.issn.1002-137X.2016.12.012

参考文献

[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.http://archive.ics.uci.edu/ml

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed