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

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

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

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 approxi- mation 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.