Incremental update of approximations in dominance-based rough sets approach under the variation of attribute valuesby Shaoyong Li, Tianrui Li

Information Sciences


Received 25 July 2013

Received in revised form 2 September 2014


Rough set to acquire knowledge from information with preference ordered attribute domains and imations in DRSA, need to be updated for decision making and other related tasks. As a usen Theoretic h set mode cision Roug (VPRS) model in order to smooth away the influence of imprecise data to knowledge acquisition [60]. To deal with inco data, three extensions of RST were introduced as follows: an early extension of rough sets that can directly deal with plete data presented by Kryszkiewicz in [24] is under a tolerance relation. Stefanowski et al. extended the model of rou by using of a non-symmetric similarity relation in [47]. Grzymala-Busse proposed an extension of rough sets in terms of a 0020-0255/ 2014 Elsevier Inc. All rights reserved. ⇑ Corresponding author.

E-mail addresses: (S. Li), (T. Li).

Information Sciences 294 (2015) 348–361

Contents lists available at ScienceDirect

Information Sciencessubset of X, and its upper approximation contains X.

Many scholars generalized RST to handle various kinds of real-life problems [38]. Yao presented Decisio

Set (DTRS) based on the well-established Bayesian decision procedure [52]. It is a general probabilistic roug different probabilistic rough set models may be derived from DTRS [51]. Ziarko proposed Variation PreRough l since h Sets mplete incomgh setsRough Sets Theory (RST) introduced by Pawlak in the early 1980s can be used to process inconsistent information [36,37].

The key of RST is an indiscernibility relation, which partitions the object set of an information system into a collection of equivalence classes. By RST, an equivalence class is the smallest information unit of the information system, called the information granularity. The objects that belong to an equivalence class are indiscernible with respect to the available information. If a set can be exactly described by equivalence classes, then it is a crisp set; otherwise, it is a rough set. Any rough set can be characterized by two crisp sets: its lower and upper approximations. For any rough set X, its lower approximation is aApproximation

Dominance matrix

Incremental update

Decision making 1. Introductionful technique, the incremental update can be applied to process dynamic information with revising the obtained knowledge. In this paper, we propose an incremental approach for maintaining approximations of DRSA when attribute values vary over time. Some numerical examples illustrate that the incremental approach can renew approximations of DRSA without beginning from scratch. Experimental evaluations show that the incremental algorithm can effectively reduce the computational time in comparison with the non-incremental one when the ratio of the attribute values varied is less than a threshold.  2014 Elsevier Inc. All rights reserved.Accepted 28 September 2014

Available online 13 October 2014 decision classes. In many real-life applications, the information systems may evolve over time dynamically. In a dynamic information system, the obtained knowledge, e.g., approx-Incremental update of approximations in dominance-based rough sets approach under the variation of attribute values

Shaoyong Li, Tianrui Li ⇑

School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China a r t i c l e i n f o

Article history: a b s t r a c t

Dominance-based Rough Sets Approach (DRSA) has received much attention since it is able journal homepage: www.elsevier .com/locate / ins

S. Li, T. Li / Information Sciences 294 (2015) 348–361 349characteristic relation under the assumption that some of the missing attribute values are lost (e.g., they were erased) and some are ‘‘do not care’’ conditions (e.g., they are redundant or unnecessary tomake a decision or to classify a case) [19]. Dubois and Prade generalized the concept of rough sets to the fuzzy environment and initiated the concepts of rough fuzzy sets and fuzzy rough sets [12]. Greco et al. proposed Dominance-based Rough Sets Approach (DRSA) to deal withmissing data inmultiattribute and multi-criteria decision problems [14,15] and process information systems with preference-ordered attribute domains and decision classes [16]. Qian et al. extended Pawlak’s rough set model to a multi-granulation rough set model (MGRS) [43]. Following Qian’s viewpoint, Lin et al. extended MGRS from partition to covering [28].

As a kind of method that can be applied to assist multiple criteria decision making, DRSA has been received much attention. For example, Kotlowski et al. found that the notions of rough approximations of DRSA are excessively restrictive for the presence of noise in real-life problems. They proposed a probabilistic model based on DRSA to the problem of ordinal classification with monotonicity constraints [23]. Dembczynski et al. considered imprecise evaluations of objects on condition criteria and imprecise assignments of objects to decision classes. They reformulated the dominance principle and proposed second-order rough approximations [11]. Yang et al. proposed a novel dominance relation in incomplete interval-valued information systems [50]. For interval-valued information systems, Qian et al. introduced another ordering approach named as Kulisch-Miranker order [41], and Huang et al. proposed a graded dominance interval-valued relation based rough sets [21].

In some real-life problems, the information systems evolve with time since data is continually collected. For a dynamic information system, the granules related to knowledge acquirement may evolve over time [39]. In order to apply RST in dynamic information processing, many researchers integrated the incremental update technique to RST or its extensions [3–5,7–10,18,20,22,25–27,32,33,35,45,49,54,55,59]. Their studies may be divided into three main aspects as follows:  Variation of the object set