International Journal of Computational Intelligence Systems

<Previous Article In Issue
Download article (PDF)
Next Article In Issue>
Volume 12, Issue 2, 2019, Pages 914 - 928

Dynamic Knowledge Update Using Three-Way Decisions in Dominance-Based Rough Sets Approach While the Object Set Varies

Authors
Lei Wang1, 2, *, Min Li1, 2, Jun Ye1, 2, Xiang Yu1, 2, Ziqi Wang3, Shaobo Deng1, 2
1College of Information Engineering, Nanchang Institute of Technology, Nanchang, Jiangxi, 330099, China
2Jiangxi Provincial Key Laboratory of Water Information Cooperative Sensing and Intelligent Processing, Nanchang, Jiangxi, 330099, China
3Shenzhen HeXunHuaGu Information Technology Co., Ltd. Guangzhou Branch, Guangzhou, Guangdong, 510620, China
*Corresponding author. Email: ezhoulei@163.com
Corresponding Author
Lei Wang
Received 6 January 2019, Accepted 1 August 2019, Available Online 22 August 2019.
DOI
10.2991/ijcis.d.190807.001How to use a DOI?
Keywords
Dominance-based rough sets approach (DRSA); Three-way decisions (3wds); Approximations; Dynamic maintenance; Vector inner product
Abstract

Dominance-based rough set approach is the extension of classical Pawlak rough set theories and methodologies, in which the information with preference-ordered relation on the domain of attribute value is fully considered. In the dominance-based information system, upper and lower approximations will be changed while the object set varies over time and the approximations need to be updated correspondingly for their variations result in changes of knowledge and rules. Considering that three-way decisions is a special class of general and effective human ways of problem solving and information processing, a new incremental maintenance mechanism using three-way decisions is proposed in this paper, namely, the universe is divided into three pair-wise disjoint subsets firstly, then appropriate strategies are developed and acted on each subsets. Furthermore, the corresponding methods for updating the approximations of upward unions and downward unions of decision classes are analyzed systematically under the variations of object set in the dominance-based information system from the perspective of three-way decisions. Moreover, considering vector representation and calculation is intuitive and concise, two incremental update algorithms of approximations are suggested and implemented in the MATLAB platform. Finally, some tests on data sets from UCI (UC Irvine Machine Learning Repository) are undertaken to verify the effectiveness of the proposed methods. Compared with the non-incremental updating methods, the proposed incremental updating method with three-way decisions generally exhibits a better performance.

Copyright
© 2019 The Authors. Published by Atlantis Press SARL.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION

Rough set theory (RST) provides a powerful mathematical tool for modeling and processing problems with incomplete, imprecise, uncertain and vague information [1] and it is one of the three primary models of Granular Computing [2] (GrC). The recent two decades have witnessed the booming interest and growing development in research of RST and its applications. As a kind of information processing tools, RST has been widely applied to the fields of artificial intelligence and cognitive sciences, such as pattern recognition [3], knowledge discovery [4,5], decision making [6,7], inductive reasoning [8] and machine learning [9]. In multiple-criteria decision making problems, attributes with preference-order domain (Criteria) constitute an important kind of attribute and should be brought to our great attention. However, only attribute values themselves, by which to tell one object from another, are considered and the preference-order relations among criteria values domain are not considered in RST. On this account, the information with preference-order attribute values domain cannot be processed by RST. Greco et al. [10–12] proposed the Dominance-based Rough Set Approach (DRSA) to address this issue, in which the innovation mainly lies in the substitution of the indiscernibility relation by dominance relation. Comparing with the decision rules derived from RST, those derived from DRSA are easy to understand as well as consistent with the practical situation due to the fact that the ordering properties of attributes are taken into account in DRSA. In real-life application, information system (IS) always varies with time for the generation and the collection of data are dynamic, called dynamic IS, it can cause the corresponding changes of the approximations of a concept from which the knowledge are acquired [13]. So updates of the approximations are of great importance for knowledge maintenance and other related tasks. Incremental update scheme is an effective and efficient technique for knowledge update, which enables to acquire new knowledge on the basis of prior knowledge without recalculation from scratch under variation of IS. A great deal of researches have been done in the area of incremental knowledge maintenance under rough sets methodologies. In general, the researches on incremental knowledge update can be fallen into four categories owing to the fact that ISs evolve over time with four levels of variational situations, i.e., (1) incremental knowledge update while the object set varies [14–17]; (2) incremental knowledge update while the attribute set varies [18–23]; (3) incremental knowledge update while the attribute values vary [24–27]; (4) incremental knowledge update under the simultaneous variations of object set and attribute set (or object set and attribute value, attribute set and attribute value) [28–32]. All these researches will help decision makers update knowledge from different perspectives in different kinds of ISs. Some achievements based on rough set methodologies under the changed IS are as follows:

Li et al. presented a new approach for incrementally updating approximations of a concept under the characteristic relation-based rough sets when the attribute set varies over time for dynamic attribute generalization, which can deal with the case of adding and removing some attributes simultaneously in the IS [14]. Huang et al. proposed mechanisms for updating approximations in probabilistic set-valued IS with the variation of attributes [31]. Zhang et al. developed the change of approximations in neighborhood decision systems when the object set evolves over time, and proposed two fast incremental algorithms for updating approximations when multiple objects enter into or get out of the neighborhood decision table [15]. Considering dynamic updating of attribute reduction for data vary with time, Jing et al. examined an incremental attribute reduction algorithm with a multi-granulation view to maintenance reduct of large-scale data sets dynamically [33,34]. Liu et al. proposed some relevant strategies and algorithms for incremental learning knowledge in probabilistic rough sets when attributes evolve with time [22]. Zhang et al. suggested an incremental methods for updating rough approximations in interval-valued ISs while attributes set evolves [18]. Luo et al. developed an incremental learning technique for hierarchical multi-criteria classification while attribute values vary across different levels of granulations [25]. He further analyzed the updating mechanisms of approximations under the variation of the object set and criteria values respectively in set-valued-ordered IS and set-valued decision system [35]. Zhang et al. examined the updating approach of approximations of the concept in set-valued IS by using matrix under the variation of attribute set [36]. Wang et al. proposed an incremental matrix method for updating approximations under the variable precision rough set model at insertion or deletion of a single object [37]. Huang et al. introduced an incremental mechanisms for updating rough fuzzy approximations with simultaneous variation of objects and attributes set by using matrix operator [31].

The theory of three-way decisions was introduced by Yao in order to model a particular class of human heuristic ways of problem solving and information processing [38,39] and its essential ideas are widely applied in many fields and disciplines. As for the application of three-way decisions in dynamic knowledge update field. Yu et al. proposed a new tree-based incremental overlapping clustering method using the three-way decision theory in order to efficiently update the clustering when the data changes [40]. Yang et al. proposed a unified model of sequential three-way decisions and multi-level incremental processing for complex problem solving [28,41], then they suggested an unified dynamic framework of decision-theoretic rough sets for incrementally updating three-way probabilistic regions [42].

In this paper, inspired by the trisecting-and-acting model of three-way decisions proposed by Yao, the essential ideas of the trisecting-and-acting model, namely, tri-partition and action are applied to analyze the incremental update mechanisms of approximations with the variation of objects set in dynamic dominance-based IS. Subsequently, the updates of the approximations is realized by using column vector as representation tool as well as computational tool, considering that the column vector is concise and intuitional in representation and operation. Our research motivation is to investigate incremental update of approximations from a new view and to exploit its feasibility and efficiency.

The remainder of the paper is organized as follows: In Section 2, some basic concepts of DRST as well as relevant operations of Boolean column vector are introduced. Under the variation of the object set, the re-judgement of existing relationship between subsets is examined in Section 3, the analyses on incremental update of approximations with three-way decisions and its corresponding illustrated example are presented in Sections 4 and 5, respectively. In Section 6, we propose two incremental algorithms using vector operations for computing approximations based on the preceding analyses. Performance evaluations are illustrated in Section 7. The paper ends with conclusions and further research topics in Section 8.

There are two contributions from our research. One is to provide a three-way decisions perspective on incremental update of approximations in DRSA. The other is an application of Boolean column vector inner product in judging the relationship (inclusion or intersection) between two sets, by which some objects need to be merged to the prior approximations and some other objects need to be removed from the prior approximations during the incremental update process of approximations.

2. PRELIMINARIES

2.1. Symbol Notation

For the sake of convenience, the symbols used in this paper and their corresponding meanings are listed in Table 1.

Symbol Meaning
X The column vector of subset X
DP, DPT Dominance relation matrix and its transposed matrix
P_Cln⩾, P_Cln′⩾ The column vector of P_Cln⩾ before and after insertion or removal of object
P¯Cln⩾, P¯Cln′⩾ The column vector of P¯Cln⩾ before and after insertion or removal of object
P_Cln⩽, P_Cln′⩽ The column vector of P_Cln⩽ before and after insertion or removal of object
P¯Cln⩽, P¯Cln′⩽ The column vector of P¯Cln⩽ before and after insertion or removal of object
ones(n, 1), ones(1, n) The n-dimensional row and column vector with all the components are equal to 1
|⋅| The cardinality of set
[ A;B] A column vector which is constructed though concatenation of column vector A and B
A[m:n] Column sub-vector which consist of rows m-n of column vector A
Table 1

Description of symbols.

2.2. The Basic Concepts of Dominance-Based Rough Set Approach

Some basic concepts of RST and DRSA are briefly reviewed in this subsection [1,10–12].

An IS is a quadruple IS=U,C∪d,V,f, where U=u1,u2,…,un is a non-empty finite set of objects, called the universe. C is a non-empty finite set of condition attributes and d is a decision attribute with C∩d=ϕ. V=VC∪Vd, where V is the domain of all attributes, VC is the domain of all condition attributes and Vd is the domain of the decision attribute d; f is a mapping from U×C∪d to V.

In an IS, OB∈2U∧OB≠ϕ and P∈2C∧P≠ϕ. Where 2U and 2C is the power set of U and C respectively. If there is a preference (decreasing or increasing) relation on two elements x and y of OB for all a∈P, denoted by xDPy. DP is a dominance relation on universe U with respect to the attribute set P.

DP=x,y∈U×U| fx,a⩾fy,a,∀a∈P.

In Ref. [10], the granules of knowledge of element x used in DRSA for approximation of the unions Cln⩾ and Cln⩽, namely, the P-dominating set and P-dominated set of element x were defined, respectively, as follows:

DP+x=y∈U| yDPx.
DP−x=y∈U|xDPy.

The equivalence classes partition of universe U by the decision attribute d is denoted as U/INDd, called set of decision classes. Let U/INDd=Cln,n∈T,T=1,…,m. m denotes the number of decision classes. ∀r,s∈T such that r>s, it means the objects from Clr are preferred to the objects from Cls. In DRSA, an upward union and a downward union of decision classes, denoted as Cln⩾=∪n′⩾nCln′ and Cln⩽=∪n′⩽nCln′ respectively, are no other than the concepts to be approximated and the definitions of approximation were given in Ref. [10].

Definition 1.

Assume that IS is an information system, P⊆C, n∈T. The definitions of lower and upper approximations of Cln⩾ and Cln⩽ are respectively as follows:

P_Cln⩾=x∈U|DP+x⊆Cln⩾.
P¯Cln⩾=x∈U|DP−x∩Cln⩾≠ϕ.
P_Cln⩽=x∈U|DP−x⊆Cln⩽.
P¯Cln⩽=x∈U|DP+x∩Cln⩽≠ϕ.

2.3. Brief Introduction to Three-Way Decisions

In this subsection, we briefly introduce the essential ideas of three-way decisions and trisecting-and-acting model used in this research.

Three-way decisions, proposed by Yao, is a general and effective human heuristic way to problem solving and information processing, their aim is to make fast, low cost and/or high benefit decisions in solving problems with uncertainty and imprecision [38,39,43,44]. The essential ideas of three-way decisions are described in term of a ternary classification according to evaluations of a set of criteria [38]. The two basic tasks of three-way decisions, which gives rise to a trisecting-and-acting model of three-way decisions, are trisecting and acting. Trisecting, namely, tri-partition is to divide a whole into three pair-wise disjoint parts or regions and acting is to develop an appropriate strategy on each part or region [39]. In many real applications, trisecting-and-acting model can turn complexity into simplicity [39] due to its firm cognitive basis and appropriate strategies and it would be a simple, general and flexible model.

2.4. The Boolean Column Vector

The basic concepts of Boolean column vector as well as the operations on Boolean Column vector (including the operations we proposed) are introduced in this subsection [45–47]. Definition 2 is quoted from Ref. [45], Definition 3 is quoted from Ref. [46] and Definition 7 is quoted from Ref. [47]. The vector inner product will be used in analyses on incremental updates of approximations of unions of decision classes, the other operations of vector will be used in the incremental update matrix algorithms of the unions’ approximations at insertion or deletion of an object in Section 6.

Definition 2.

Assume that U=u1,u2,…,un is a non-empty finite set of objects, called the universe, and X⊆U. Then the column vector representation of subset X is as follows:

Xn×1=x1x2…xn=x1,x2,…,xnT.
where xi=1ui∈X0ui∉X,

In Formula (8), the location of object ui in the universe U is i, denoted as Locui,U=i.

Example 1.

Assume that U=u1,u2,u3,u4,u5,u6,u7,u8 and A=u1,u3,u5,u7,u8, B=u2,u3,u4,u5,u7, then

A=a1,a2,a3,a4,a5,a6,a7,a8T=1,0,1,0,1,0,1,1T.
B=b1,b2,b3,b4,b5,b6,b7,b8T=0,1,1,1,1,0,1,0T.

Example 2.

Suppose U=u2,u1,u7,u4,u8,u6,u3,u5, then Locu7,U=3, Locu8,U=5, Loc(u5,U)=8.

2.4.1. Operations on Boolean column vector

Assume set X, Y and Z are subsets of university U and their corresponding n-dimension Boolean column vectors are X, Y, Z respectively and X=x1,x2,…,xnT, Y=y1,y2,…,ynT, Z=z1,z2,…,znT.

Definition 3.

Let

X,Y=XT⋅Y=∑i=1mxi⋅yi.

X,Y is called inner product of column vector.

The following formulas are easy to gained from Definition 3.

X,Y=0⇔X∩Y=ϕ.
X,Y=|X|⇔X⊆Y.
X,Y=|Y|⇔Y⊆X.

Vector Inner product can be used to judge the intersection or inclusion between two sets.

Example 3.

(Continuation of Example 1)

A,B=∑i=18ai⋅bi=3 and A∩B≠ϕ.

Taking into account the characteristics of Boolean column vector, we defined their operations corresponding to the intersection, union and difference of two sets respectively as follows:

Definition 4.

Let

Z=X⋅∗Y.
where zi=1xi=1∧yi=10others  i=1,2,…,n

⋅∗ is called operator of column vector multiplication. It can be used to calculate the intersection of two sets.

Example 4.

(Continuation of Example 1)

Let D=A⋅∗B=0,0,1,0,1,0,1,0. So D=u3,u5,u7 and set D is the intersection of set A and set B.

Definition 5.

Let

Z=X+Y.
where zi=0xi=0∧yi=01others  i=1,2,…,n

Z is called summation of X and Y. It can be used to calculate the union of two sets.

Example 5.

(Continuation of Example 1)

Let D=A+B=1,1,1,1,1,0,1,1. So D=u1,u2,u3,u4,u5,u7,u8 and set D is the union of set A and set B.

Definition 6.

Let

Z=X−Y.
where zi=1xi=1∧yi=00others  i=1,2,…,n

Z is called difference of X and Y. It can be applied to calculate the difference of two sets.

Example 6.

(Continuation of Example 1)

Let D=A−B=1,0,0,0,0,0,0,1. So D=u1,u8 and set D is the subtraction of set A and set B.

Definition 7.

Assume that X and Y are two non-empty sets, the inclusion degree of X in Y is denote as CX,Y.

CX,Y=|X∩Y||X|=X,YX,X.

It is obviously that 0⩽C⩽1.

Inclusion degree can be used to judge the relationship of two sets. The following formulas are easy to gained from Definitions 7 and 3.

CX,Y=0⇔X,Y=0⇔X∩Y=ϕ.
CX,Y=1⇔X,Y=|X|⇔X⊆Y.
CY,X=1⇔X,Y=|Y|⇔Y⊆X.

Example 7.

(Continuation of Example 1)

CA,B=|A∩B||A|=A,BA,A=35=0.6 and A∩B≠ϕ.

3. THE RE-JUDGEMENT OF EXISTING RELATIONSHIP BETWEEN SUBSETS UNDER VARIATIONS OF OBJECTS

According to the definitions of approximations, the judgement of inclusion relationship or intersection relationship between two subsets of universe is a prerequisite for calculating approximations in RST. However, the pre-existing relationship between two subsets will change after new objects are inserted into the universe or the original objects are removed from the universe, so the relationship between two subsets remains to be re-judged. In this paper, Boolean column vector is employed to denote the subsets of the universe, and the problem that judge one object belongs to approximations of upward (downward) unions or not can be transformed into the operations of Boolean column vectors and the subsequent simple numeric comparison. In short, the vector approach of dynamic maintenance and update of approximations at variation of objects is that of incremental maintenance and update of approximations via operations on column vectors. Therefore, the research of this section is the foundation of follow-up analyses on incremental update of approximations from perspective of trisecting and acting.

Suppose that set A and set B are two non-empty subsets of the universe U. A′ and B′ denote updated A and updated B, respectively, after x+ is inserted into U or x− is removed from U respectively.

The Lemma 1 and Lemma 2 can be applied to re-judge the relationship between set A and set B after object x+ is inserted into universe U.

Lemma 1.

Assume that A⊈B i.e.,0<A,B<min|A|,|B|, then

A∩B≠ϕ⇒A′∩B′≠ϕ∧A′⊈B′.
A∩B=ϕ∧x+∈A′∩B′⇒A′∩B′≠ϕ.

The equivalent expressions of column vector are as follows:

A,B≠0⇒0<A′,B′<min|A′|,|B′|.
A,B=0∧x+∈A′∩B′⇒A′,B′=1.

Lemma 2.

Assume that A⊆B i.e.,A,B=|A|, the inclusion relationship between A and B will be changed after x+ is inserted into U if and only if x+∈A′∧x+∉B′.

A⊆B and x+∈A′∧x+∉B′⇒A′⊈B′.

Its equivalent expression of column vector’s inner product is as follows:

A,B=|A| and x+∈A′∧x+∉B′⇒A′,B′≠|A′|.

Proof.

The above conclusions can be driven easily from connotation of the inclusion relation between two sets.

Lemma 2 can be demonstrated by the Venn diagram in the Fig. 1.

Figure 1

The change of inclusion relation between two subsets after insertion of object x+.

Similarly, the Lemma 3 and Lemma 4 can be applied to re-judge the relationship between set A and set B after object x− is removed from universe U.

Lemma 3.

Assume that A⊈B, then

x−∈A∩B⇒A′⊈B.
A∩B=ϕ∨A∩B=x−⇒A′∩B′=ϕ.

The equivalent expressions of column vector are as follows:

A,B≠0∧x−∉A∩B⇒A′,B′≠0.
A,B=0∨A∩B=x−⇒A′,B′=0.

Lemma 4.

Assume that A⊆B, then

A⊆B⇒A′⊆B′.

Its equivalent expression of column vector’s inner product is as follows:

A,B=|A|⇒A′,B′=|A′|.

Proof.

The above conclusions can be driven easily from connotation of the inclusion relation. As shown in the Venn diagram in Fig. 2, three cases are considered, i.e., x−∈A, x−∈AC∩B and x−∈AC∩Bc.

Figure 2

The inclusion relation between two subsets remains unchanged after deletion of object x−.

Lemma 4 demonstrates that the removal of single object from the universe will not alter the existing inclusion relationship between two subsets.

4. THE ANALYSES ON INCREMENTAL UPDATE OF APPROXIMATIONS WITH THREE-WAY DECISIONS

In this section, a trisecting-and-acting model is presented to update approximations in DRSA incrementally and then the methods of tri-partition of universe at insertion or removal of one object are discussed.

4.1. A Trisecting-and-Acting Model for Incremental Update of Approximations in DRSA

The incremental update method of approximations is just the method in which updated approximations can be acquired on the basis of the approximations prior to update by some certain operations and it is not necessary to recompute from scratch. As for the incremental update using three-way decisions, the certain operations refer to trisecting and acting.

We take the update of P_Cln⩾ under the insertion of one object x+ as an example to demonstrate the divide-and-conquer method in trisecting-and-acting model for incremental update of approximations.

Above all, the objects in the universe U′ can be partitioned into three pair-wise disjoint parts, as shown in Fig. 3.

Figure 3

The unified framework of update of approximations.

The first part consists of all the objects which do not belong to the original approximation and belong to the updated approximation simultaneously, denoted as N, shown in Formula (32).

N=x∈U|x∉P_Cln⩾∧x∈P_Cln′⩾.

The second part consists of all the objects which belong to the approximation before update and no longer belong to the approximation after update, denoted as M, shown in Formula (33).

M=x∈U|x∈P_Cln⩾∧x∉P_Cln′⩾.

The rest objects of the universe constitute the third part, i.e., the third part is composed of all the objects except for the first part and the second part, denoted as O and shown in Formula (34).

O=x|x∉P_Cln⩾∧x∉P_Cln′⩾∨   x∈P_Cln⩾∧x∈P_Cln′⩾.

It’s worth noting that the inserted object x+ is a special object. x+ may be belongs to either the set N or the set O and we need to determine which set x+ belong to.

Secondly, the different strategy will be developed and adopted in the different part after trisection. It is obviously that the strategies should be developed and adopted only in the set N and the set M after tri-partition of universe.

So the incremental update of P_Cln⩾ can be finished by the following three steps:

  1. Computes the set M and the set N.

  2. Subtracts the set M from P_Cln⩾, assume that the intermediate result is P_″Cln⩾.

  3. Computes the union set of P_″Cln⩾ and the set N, so the updated approximation P_Cln′⩾ is gained.

Thus, the incremental update of P_Cln⩾ is more appropriately formulated as the following formula:

P_Cln′⩾=P_Cln⩾−M∪N.

The incremental update of P_Cln⩾ follows Formula (35) after tri-partition of universe. And the incremental update of P¯Cln⩾, P_Cln⩽ and P¯Cln⩽ are similar with that of P_Cln⩾.

As for the case of object’s deletion, the process of incremental update of approximations is similar with that of object’s insertion, so it is not discussed again.

In the following subsections, under the unified frame of trisecting-and-acting model, only methods of tri-partition are discussed for update on dynamic environment of insertion and removal of one object, respectively. What’s more, it can be simplified as a series of calculational formulas of the set M and N. The inner product of Boolean column vectors is employed to judge the relationship between two sets in the proof of the theorems.

4.2. The Update of Approximations Using Trisecting-and-Acting Model at Insertion of Object

Supposing x+ is the inserted object and Locx+,U=i.

4.2.1. The update of unions of decision classes

Supposing that Cln′ is the decision class to which inserted object x+ belongs.

  1. The update of upward unions of decision classes

    The updated upper unions of decision classes is as following formula:

    Cln′⩾=Cln⩾∪x+n′⩾nCln⩾n′<n.

    The corresponding column vector of the updated upward unions of decision classes can be denoted as

    Cln′⩾=Cln⩾1:i−1;1;Cln⩾i+1:mn′⩾nCln⩾1:i−1;0;Cln⩾i+1:mn′<n.

  2. The update of downward unions of decision classes

    The updated downward unions of decision classes is as following formula:

    Cln′⩽=Cln⩽∪x+n′⩽nCln⩽n′>n.

    The corresponding column vector of the updated upward union set can be denoted as

    Cln′⩽=Cln⩽1:i−1;1;Cln⩽i+1:mn′⩽nCln⩽1:i−1;0;Cln⩽i+1:mn′>n.

It is obviously that the dimension of updated column vector will increase to n + 1 after removal of x+.

4.2.2. Trisection of universe at insertion of object

The calculations of the set N and M are discussed in Theorems 1–4 respectively. The computational results lead to tri-partition of universe naturally.

  • The computational formula of the set M and N for incremental update of P_Cln⩾

    Theorem 1.

    M=ϕn′⩾nu|u∈DP′−x+∧u∈P_Cln⩾n′<n.
    N=x+n′⩾n∧DP′+x+⊆Cln′⩾ϕn′<n.

    Proof.

    n′⩾n: x+∈Cln′⩾.

    Case 1: If DP′+x+⊆Cln′⩾, i.e., Cln′⩾DP′+x+=|DP′+x+|, we have x+∈P_Cln′⩾.

    Case 2: Assume that v∉P_Cln⩾, then DP+v⊈Cln⩾, we have Cln⩾,DP+v≠|DP+v|, and Cln′⩾,DP′+v≠|DP′+v| still holds after x+ is inserted into U (Lemma 1).

    To sum up, N=x+ while DP′+x+⊆Cln′⩾.

    Case 3: Assume that u∈P_Cln⩾, then DP+v⊆Cln⩾, we have Cln⩾,DP+u=|DP+u|, For x+∈Cln′⩾,Cln′⩾,DP′+u=|DP′+u| still holds after x+ is inserted into U (Lemma 2).

    So, M=ϕ.

    n′<n:

    Case 1: For x+∉Cln′⩾ and x+∈DP′+x+, we have Cln′⩾DP′+x+≠|DP′+x+|, so x+∉N.

    Case 2: Assume that v∉P_Cln⩾, then DP+v⊈Cln⩾, we have Cln⩾,DP+v≠|DP+v|, and Cln′⩾DP′+v≠|DP′+v| still holds after x+ is inserted into U (Lemma 1).

    So, N=ϕ.

    Case 3: Assume that u∈P_Cln⩾, then DP+u⊆Cln⩾, we have Cln⩾,DP+u=|DP+u|. For x+∉Cln′⩾ and if x+∈DP′+u, i.e., u∈DP′−x+, then Cln′⩾DP′+u≠|DP′+u| (Lemma 2).

    So, M=u|u∈DP′−x+∧u∈P_Cln⩾.

  • The computational formula of the set M and N for incremental update of P¯Cln⩾

    Theorem 2.

    M=ϕ.
    N=v|v∈DP′+x+∧v∉P¯Cln⩾  n′⩾nx+    n′<n∧DP′−x+∩Cln′⩾≠ϕ.

    Proof.

    Assume that v∈P¯Cln⩾, then DP−v∩Cln⩾≠ϕ, and DP′−v∩Cln′⩾≠ϕ still holds after x+ is inserted (Lemma 1).

    So, M=ϕ.

    n′⩾n:x+∈Cln′⩾.

    Case 1: For x+∈DP−x+, we have DP′−x+∩Cln′⩾≠ϕ, i.e., DP′−x+,Cln′⩾≠0, so x+∈N.

    Case 2: Assume that v∉P¯Cln⩾, then DP−v∩Cln⩾=ϕ. For x+∈Cln′⩾, and if x+∈DP′−v, i.e., v∈DP′+x+, then DP′−v∩Cln′⩾≠ϕ, thus v∈P¯Cln′⩾ (Lemma 1).

    So, N=v|v∉P¯Cln⩾∧v∈DP+x+∪x+=v|v∉P¯Cln⩾∧v∈DP+x+.

    n′<n:x+∉Cln′⩾

    Case 1: If DP′−x+∩Cln′⩾≠ϕ, i.e., DP′−x+,Cln′⩾≠0, then x+∈N.

    Case 2: Assume that v∉P¯Cln⩾, then DP−v∩Cln⩾=ϕ. For x+∉Cln′⩾, no matter whether x+∈DP′−v or not, DP′−v∩Cln′⩾=ϕ still holds after x+ is inserted into U (Lemma 1), thus, v∉P¯Cln′⩾.

    To sum up, N=x+ when DP′−x+∩Cln′⩾≠ϕ.

  • The computational formula of the set M and N for incremental update of P_Cln⩽

    Theorem 3.

    M=u|u∈DP′+x+∧u∈P_Cln⩽n′>nϕn′⩽n.
    N=ϕn′>nx+n′⩽n∧DP′−x+⊆Cln′⩽.

    Proof.

    The proof of Theorem 3 is similar to that of Theorem 1.

  • The computational formula of the set M and N for incremental update of P¯Cln⩽

    Theorem 4.

    M=ϕ.
    N=x+    n′>n∧DP′+x+∩Cln′⩽≠ϕv|v∈DP′−x+∧v∉P¯Cln⩽  n′⩽n.

    Proof.

    The proof of Theorem 4 is similar to that of Theorem 2.

4.3. The Update of Approximations Using Trisecting-and-Acting Model at Deletion of Object

Supposing x− is the deleted object and Loc(x−,U)=i.

4.3.1. The update of unions of decision classes

Supposing that Cln′ is the decision class to which x− belongs.

  1. The update of upward unions of decision classes

    The updated upward unions of decision classes is as following formula:

    Cln′⩾=Cln⩾−x−n′⩾nCln⩾n′<n.

    The corresponding column vector of the updated upward union set can be denoted as

    Cln′⩾=Cln⩾1:i−1;Cln⩾i+1:m.

  2. The update of downward unions of decision classes

    The updated downward unions of decision classes is as following formula:

    Cln′⩽=Cln⩽−x−n′⩽nCln⩽n′>n.

    The corresponding column vector of the updated upward unions can be denoted as

    Cln′⩽=Cln⩽1:i−1;Cln⩽i+1:m.

    It is obviously that the dimension of updated column vector will decrease to n−1 after removal of x−.

4.3.2. Trisection of universe at deletion of object

The calculations of the set N and M are discussed in Theorem 5–8, respectively. The computational results lead to tri-partition of universe naturally.

  • The computational formula of the set M and N for incrementally update of P_(Cln⩾)

    Theorem 5.

    M=x−n′⩾n∧x−∈P_Cln⩾ϕn′<n.
    N=ϕn′⩾nv|v∉P_Cln⩾∧v∈DP−x− ∧DP′+v⊆Cln′⩾n′<n.

    Proof.

    M=u|u∈P_Cln⩾∧u∉P_Cln′⩾ =u|DP+u⊆Cln⩾∧DP′+u⊈Cln′⩾.

    u∈P_Cln′⩾ will still hold after x− is removed (Lemma 4). When n′⩾n, we have x−∈Cln⩾. If x−∈P_Cln⩾, then M=x−.

    N=v|v∉P_Cln⩾∧u∈P_Cln′⩾ =v|DP+v⊈Cln⩾∧DP′+v⊆Cln′⩾.

    When n′⩾n, we have x−∈Cln⩾. DP′+v⊈Cln′⩾ will still hold after x− is removed (lemma 3), so N=ϕ.

    When n′<n, we have x−∉Cln⩾. If x−∈DP+v, i.e., v∈DP−x− and DP′+v⊆Cln′⩾, then v∈P_Cln′⩾.

    So N=v|v∉P_Cln⩾∧v∈DP−x−∧DP′+v⊆Cln′⩾.

  • The computational formula of the set M and N for incrementally update of P¯Cln⩾

    Theorem 6.

    M=x−n′<n ∧x−∈P¯Cln⩾x−∪u|u∈P¯Cln⩾∩ DP+x−∧DP′−u∩Cln′⩾=ϕn′⩾n.
    N=ϕ.

    Proof.

    M=u|u∈P¯Cln⩾∧u∉P¯Cln′⩾ =u|DP−u∩Cln⩾≠ϕ∧DP′−u∩  Cln′⩾=ϕ.

    When n′⩾n, we have x−∈Cln⩾, so DP−x−∩Cln⩾≠ϕ, i.e., x−∈M. And if u∈DP+x−, i.e., x−∈DP−u and DP′−u∩Cln′⩾=ϕ, then u∉P¯Cln′⩾.

    To sum up, M=x−∪u|u∈P¯Cln⩾∩ DP+x−∧DP′−u∩Cln′⩾=ϕ

    When n′<n, we have x−∉Cln⩾, DP′−u∩Cln′⩾≠ϕ still hold after x− is removed. If DP−x−∩Cln⩾≠ϕ, then M=x−.

    N=v|v∉P¯Cln⩾∧u∈P¯Cln′⩾ =v|DP−v∩Cln⩾=ϕ∧DP′−v∩Cln′⩾≠ϕ.

    For DP′−v∩Cln′⩾=ϕ will still hold after x− is removed (Lemma 3). So, N=ϕ.

  • The computational formula of the set M and N for incrementally update of P_Cln⩽

    Theorem 7.

    M=x−n′⩽n∧x−∈P_Cln⩽ϕn′>n.
    N=ϕn′⩽nv|v∉P_Cln⩽∧v∈DP+x− ∧DP′−v⊆Cln′⩽n′>n.

    Proof.

    The proof of Theorem 7 is similar to that of Theorem 5.

  • The computational formula of the set M and N for incremental update of P¯Cln⩽

    Theorem 8.

    M=x−∪u|u∈P¯(Cln⩽)∩ DP−x−∧DP′+u∩Cln′⩽=ϕn′⩽nx−n′>n ∧x−∈P¯Cln⩽.
    N=ϕ.

    Proof.

    The proof of Theorem 8 is similar to that of Theorem 6.

5. ILLUSTRATIVE EXAMPLE

Consider the following example (See Table 2). A set of 16 objects is described by the set of 3 attributes (criteria) C=c1,c2,c3. The decision attribute d classifies objects into three decision classes Cl1, Cl2 and Cl3 which are preference-ordered according to increasing class number.

Object c1 c2 c3 d
o1 0.8 0.5 1.5 Cl1
o2 1  1.5 8  Cl1
o3 1  3  5  Cl1
o4 2.5 4  11   Cl2
o5 1.2 1  7  Cl2
o6 1.9 4.5 14   Cl2
o7 2.8 5.5 15   Cl3
o8 2.4 4  13   Cl3
o9 0.6 3  6  Cl2
o10 2  2.5 6  Cl1
o11 2.4 3.5 9  Cl3
o12 1.6 3  12   Cl2
o13 1.8 5  9.5 Cl2
o14 0.6 2  2.5 Cl1
o15 1  2  4.5 Cl2
o16 3  4.5 9  Cl3
Table 2

Illustrative data table.

Cl1⩽=o1,o2,o3,o10,o14.Cl2⩽=o1,o2,o3,o4,o5,o6,o9,o10,o12,o13,o14,o15.Cl2⩾=o4,o5,o6,o7,o8,o9,o11,o12,o13,o15,o16.Cl3⩾=o7,o8,o11,o16.

Let P=C, the approximations of upward and downward unions of decision classes are

P_Cl1⩽=o1,o2,o14.P¯Cl1⩽=o1,o2,o3,o10,o14,o15.P_Cl2⩽=o1,o2,o3,o5,o6,o9,o10,o12,o13,o14,o15.P¯Cl2⩽=o1,o2,o3,o4,o5,o6,o9,o10,o11,o12,o13,.  o14,o15.P_Cl2⩾=o4,o5,o6,o7,o8,o9,o11,o12,o13,o16.P¯Cl2⩾=o3,o4,o5,o6,o7,o8,o9,o10,o11,o12,o13,  o15,o16.P_Cl3⩾=o7,o8,o16.P¯Cl3⩾=o4,o7,o8,o11,o16.

Now we consider the following two cases at time t + 1:

  • A new object o17 inserts the IS (See Table 3).

    Object c1 c2 c3 d
    o1 0.8 0.5 1.5 Cl1
    o2 1  1.5 8  Cl1
    o3 1  3  5  Cl1
    o4 2.5 4  11   Cl2
    o5 1.2 1  7  Cl2
    o6 1.9 4.5 14   Cl2
    o7 2.8 5.5 15   Cl3
    o8 2.4 4  13   Cl3
    o9 0.6 3  6  Cl2
    o10 2  2.5 6  Cl1
    o11 2.4 3.5 9  Cl3
    o12 1.6 3  12   Cl2
    o13 1.8 5  9.5 Cl2
    o14 0.6 2  2.5 Cl1
    o15 1  2  4.5 Cl2
    o16 3  4.5 9  Cl3
    o17 1.8 2.8 3.5 Cl2
    Table 3

    Insertion of one object.

    Cl1⩽′=o1,o2,o3,o10,o14.Cl2⩽′=o1,o2,o3,o4,o5,o6,o9,o10,o12,o13,o14,o15,o17.Cl2⩾′=o4,o5,o6,o7,o8,o9,o11,o12,o13,o15,o16,o17.Cl3⩾′=o7,o8,o11,o16.

    The DP′−o17 and DP′+o17 should be calculated firstly.

    DP′−o17=o1,o14,o17.DP′+o17=o4,o6,o7,o8,o11,o13,o16,o17.

    According to Theorems 1–4, we have

    P_Cl1⩽′=P_Cl1⩽−M∪N=P_Cl1⩽−ϕ∪ϕ =o1,o2,o14.
    P¯Cl1⩽′=P¯Cl1⩽−M∪N=P¯Cl1⩽−ϕ∪ϕ=o1,o2,o3,o10,o14,o15.
    P_Cl2⩽′=P_Cl2⩽−M∪N=P_Cl2⩽−ϕ∪o17=o1,o2,o3,o5,o6,o9,o10,o12,o13,o14,o15,o17.
    P¯Cl2⩽′=P¯Cl2⩽−M∪N=P¯Cl2⩽−ϕ∪o17=o1,o2,o3,o4,o5,o6,o9,o10,o11,o12,o13,o14,o15,o17.
    P_Cl2⩾′=P_Cl2⩾−M∪N=P_Cl2⩾−ϕ∪o17=o4,o5,o6,o7,o8,o9,o11,o12,o13,o16,o17.
    P¯Cl2⩾′=P¯Cl2⩾−M∪N=P¯Cl2⩾−ϕ∪o17=o3,o4,o5,o6,o7,o8,o9,o10,o11,o12,o13,o15,    o16,o17.
    P_Cl3⩾′=P_Cl3⩾−M∪N=P_Cl3⩾−ϕ∪ϕ =o7,o8,o16.
    P¯Cl3⩾′=P¯Cl3⩾−M∪N=P¯Cl3⩾−ϕ∪ϕ =o4,o7,o8,o11,o16.

  • The object o10 gets out of the IS (See Table 4).

    Cl1⩽′=o1,o2,o3,o14.Cl2⩽′=o1,o2,o3,o4,o5,o6,o9,o12,o13,o14,o15.Cl2⩾′=o4,o5,o6,o7,o8,o9,o11,o12,o13,o15,o16.Cl3⩾′=o7,o8,o11,o16.
    DP′−o10=o1,o10,o14,o15.DP′+o10=o4,o7,o8,o10,o11,o16.
    Object cl c2 c3 d
    o1 0.8 0.5 1.5 Cl1
    o2 1  1.5 8  Cl1
    o3 1  3  5  Cl1
    o4 2.5 4  11   Cl2
    o5 1.2 1  7  Cl2
    o6 1.9 4.5 14   Cl2
    o7 2.8 5.5 15   Cl3
    o8 2.4 4  13   Cl3
    o9 0.6 3  6  Cl2
    o11 2.4 3.5 9  Cl3
    o12 1.6 3  12   Cl2
    o13 1.8 5  9.5 Cl2
    o14 0.6 2  2.5 Cl1
    o15 1  2  4.5 Cl2
    o16 3  4.5 9  Cl3
    Table 4

    Deletion of one object.

    According to Theorem 5–8, we have

    P_Cl1⩽′=P_Cl1⩽−M∪N=o1,o2,o14−ϕ∪ϕ =o1,o2,o14.
    P¯Cl1⩽′=P¯Cl1⩽−M∪N=o1,o2,o3,o10,o14,o15−o10∪ϕ=o1,o2,o3,o14,o15.
    P_Cl2⩽′=P_Cl2⩽−M∪N=P_Cl2⩽−o10∪ϕ =o1,o2,o3,o5,o6,o9,o12,o13,o14,o15.
    P¯Cl2⩽′=P¯Cl2⩽−M∪N=P¯Cl2⩽−o10∪ϕ =o1,o2,o3,o4,o5,o6,o9,o11,o12,o13,  o14,o15.
    P_Cl2⩾′=P_Cl2⩾−M∪N=P_Cl2⩾−ϕ∪ϕ =o4,o5,o6,o7,o8,o9,o11,o12,o13,o16.
    P¯Cl2⩾′=P¯Cl2⩾−M∪N=P¯Cl2⩾−o10∪ϕ =o3,o4,o5,o6,o7,o8,o9,o11,o12,o13,  o15,o16.
    P_Cl3⩾′=P_Cl3⩾−M∪N=o7,o8,o16−ϕ∪ϕ =o7,o8,o16.
    P¯Cl3⩾=P¯Cl3⩾−M∪N=o4,o7,o8,o11,o16−ϕ∪ϕ =o4,o7,o8,o11,o16.

6. INCREMENTAL UPDATE MATRIX ALGORITHM OF THE UNION SET’S APPROXIMATIONS AT INSERTION OR DELETION OF ONE OBJECT

According to the preceding methods using trisecting and acting in update of approximations at object’s insertion or removal, their corresponding incremental update algorithms are proposed. All the algorithms are described by matrix considering that representation and calculation of matrix are intuitive and concise.

The Algorithm 1 is finished.

Assume that number of objects, number of attributes and number of dominance classes are n1, n2 and m, respectively. The time complexity of Algorithm 1 is equal to Om⋅8+2⋅n2⋅n1. Thus it approximately equal to Om⋅n2⋅n1.

Algorithm 1: A matrix-based incremental algorithm for updating approximations of unions of decision classes when a new object adds to an information system.

Input:

(1) DP at time t.

(2) ∀n∈T,P_Cln⩾,P¯Cln⩾,P_Cln⩽,P¯Cln⩽ at time t.

(3) An inserted object x+.

Output:

∀n∈T,P_Cln′⩾,P¯Cln′⩾,P_Cln′⩽,P¯Cln′⩽.

Begin

Compute DP+x+ and DP−x+.

Update DP at time t to D′P at time t + 1.//insert DP+x+ and DP−x+ //after the (i−1)th column and after the (i−1)th row.

Update Cln⩾ and Cln⩽ at time t to Cln′⩾ and Cln′⩽ at time t + 1.

For n = 1, …, m do

If(n < g) Then// g is the index of the class which the object x+ is

// assigned

If DP+x+,Cln⩾==|DP+x+|, Then P_(Cln⩾)←P_(Cln⩾)+x+

End.

If DP:g,P¯Cln⩾==0, Then P¯Cln⩾←P¯Cln⩾+DP+x+

End.

If DP:g,P_Cln⩽!=0, Then P_Cln⩽←P_Cln⩽−DP+x+,

P_Cln⩽ End.

If DP:g,Cln⩽!=0, Then P¯Cln⩽←P¯Cln⩽+x+

End.

End.

If(n == g) Then

If DP+x+,Cln⩾==|DP+x+|, Then P_Cln⩾←P_Cln⩾+x+

End.

If DP:g,P¯Cln⩾==0, Then P¯Cln⩾←P¯Cln⩾+DP+x+

End.

If DPg:,Cln⩽!=|DPg:|, Then P_Cln⩽←P_Cln⩽+x+

End.

P¯Cln⩽←P¯Cln⩽+DP−x+

End.

If(n > g) Then

If DPg:,Cln⩾!=0, Then P_Cln⩾←P_Cln⩾−An End.

If DPg:,Cln⩾!=0, Then P¯Cln⩾←P¯Cln⩾+x+ End.

If DPg:,Cln⩽==|DPg:|, Then P_Cln⩽←P_Cln⩽+x+

End.

P¯Cln⩽←P¯Cln⩽+DP−x+.

End.

End.

Return P_Cln⩾, P¯Cln⩾, P_Cln⩽ and P¯Cln⩽ at time t + 1.

End.

The Algorithm 2 is finished.

Similar to Algorithm 1, the time complexity of Algorithm 2 is approximately equal to O(m⋅n2⋅n1).

The non-incremental algorithm for computing the approximations is given below in order to compare its performance with that of the incremental algorithm in the next subsection.

Algorithm 2: A matrix-based incremental algorithm for updating approximation of unions of decision classes when an object gets out of an information system.

Input:

(1) DP at time t.

(2) ∀n∈T,P_Cln⩾,P¯Cln⩾,P_Cln⩽,P¯Cln⩽ at time t.

(3) An deleted object x−.

Begin

Update DP at time t.//delete the i th column and the i th row

Update Cln⩾ and Cln⩽ at time t.

For n = 1, …, m do

If (n < g) Then// g is the index of the class which the object x−

//is assigned.

If DP+x−,Cln⩾==|DP+x−|, Then P_Cln⩾←P_Cln⩾−x−

End.

P¯Cln⩾←P¯Cln⩾−x−.

For each u∈P¯Cln⩾∩DP+x−

If DP−′u,Cln⩾′==0, Then P¯Cln⩾←P¯Cln⩾−u End.

End

For each u∈DP+x−∧u∉P_Cln⩽

If DP−′u,Cln⩽′=|DP−′u|, Then P¯Cln⩽←P¯Cln⩽+u

End.

End

If DP+x−,Cln⩽≠0, Then P¯Cln⩽←P¯Cln⩽−x− End.

End.

If(n == g) Then

If DP+(x−),Cln⩾==|DP+x−|, Then P_Cln⩾←P_Cln⩾−x−

End.

P¯Cln⩾←P¯Cln⩾−x−

For each u∈P¯Cln⩾∩DP+x−

If DP−′u,Cln⩾′==0, Then P¯Cln⩾←P¯Cln⩾−u End.

End.

If DP−x−,Cln⩽==|DP−x−|, Then P_Cln⩽←P_Cln⩽−x−

End.

For each u∈P¯Cln⩽∩DP−′x−

If DP′+u,Cln′⩽==0, Then P¯Cln⩽←P¯Cln⩽−u End.

End.

End.

If (n > g) Then

For each u∉P_Cln⩾∧u∈DP−x−

If DP+′u,Cln⩾′==|DP+′u|, Then P_Cln⩾←P_Cln⩾+u

End.

End.

If DP−x−,Cln⩾≠0, Then P¯Cln⩾←P¯Cln⩾−x− End.

If DP−x−,Cln⩽==|DP−x−|, Then P_Cln⩽←P_Cln⩽−x−

End.

For each u∈P¯Cln⩽∩DP−′x−

If DP′+u,Cln′⩽==0, Then P¯Cln⩽←P¯Cln⩽−u End.

End

End.

End.

The Algorithm 3 is finished.

The time complexity of Algorithm 3 is equal to Om⋅n12⋅n2+8+8⋅n1. It is approximately equal to Om⋅n12⋅n2.

Algorithms 1–3 have the same space complexity due to the same memory space.

Algorithm 3: A matrix-based algorithm for computing approximations of unions of decision classes.

Input:

IS=U,C∪d,V,f,U/INDd.

Output:

∀n∈T,P_Cln⩾,P¯Cln⩾,P_Cln⩽,P¯Cln⩽.

Begin

Computing Dp, Cln⩾, Cln⩽ by using IS.

Computing matrix multiplications Dp·Cln⩾, DpT·Cln⩾, Dp·Cln⩽ and DpT• Cln⩽. Denote by M1, M2, M3 and M4 respectively.

Computing Column Vector by sum of row sumDnT,2 and sumDn,2.

P_Cln⩾←M1⩾sumDpT,2.

P¯Cln⩾←M2⩾onesn,1.

P_Cln⩽←M3⩾sumDp,2.

P¯Cln⩽←M4⩾onesn,1.

End.

7. THE TEST AND EVALUATION IN UCI DATA SET

Three data sets are selected (i.e., ‘Wine’ data set, ‘Car evaluation’ data set and ‘Abalone’ data set) from the machine learning data repository UCI (http://archive.ics.uci.edu/ml/) to test the performance of Algorithms 1 and 2 proposed in this paper and the existing Algorithm 3 (non-incremental updating algorithm) in order to verify the effectiveness of the proposed algorithms. Descriptions of the selected data sets are shown in Table 5.

Name Number of Attributes Number of Objects Number of Classes
Wine 13 178 3
Car evaluation 6 1728 4
Abalone 8 4177 29
Table 5

A descriptions on the selected three data sets.

Experimental Platform: CPU Intel Core i7-4510U (2.00 GHz), 8.0G Memory, Windows 8 operation system, Matlab7.0 development tool. Experimental method is as follows:

To show the time efficiency of dynamic algorithm (Algorithms 1 and 2) and compare with the existing static algorithm (Algorithm 3), each of selected data sets is divided into 10 sub-data sets. The generation of sub-data set follows four principles, take the ‘wine’ data set as an example to explain how to generate sub-data set from whole data set. Firstly, the ‘wine’ data set is divided into 10 subsets, each sub-data set is named as wine 1, wine 2, wine 3, wine 4, … and wine 10, respectively. Secondly, the size of wine 1, wine 2, wine 3, … and wine 9 is one-tenth, two-tenths, three-tenths, … and nine-tenths of that of ‘wine’ data set, respectively, wine 10 is the copy of wine data set. Thirdly, there exists the following inclusion relation among these ten sub-data sets, the wine 10 contains wine 9, wine 9 contains wine 8, …, wine 3 contains wine 2 and wine 2 contains wine1. Fourthly, the number of objects in a certain class of each sub-data set should be proportional to the size of the sub-data set in order to keep the original proportion of distribution of each class in whole data set. The distributions of each class in sub-data set of ‘wine’ are shown in Table 6.

Sub-Data Set Total Objects Objects in Class 1 Objects in Class 2 Objects in Class 3
Wine 1 18 6 7 5
Wine 2 36 12 14 10
Wine 3 54 18 21 15
Wine 4 72 24 28 20
Wine 5 90 31 35 24
Wine 6 107 36 42 29
Wine 7 125 42 49 34
Wine 8 142 48 56 38
Wine 9 160 54 63 43
Wine 10 178 59 71 48
Table 6

The distribution of classes in each subset of Wine.

The running time of the proposed Algorithms 1 and 2 and the existing Algorithm 3 can be gained by executing the corresponding programs on each of these 10 sub-data sets. Concerned programs which update four approximations of DRSA while object set varies are all developed on Matlab7.0 platform.

The experimental results are depicted in Fig. 4, where the x-coordinate pertains to the test sub-data sets, while y-coordinate concerns the computing time of updating approximations. The following conclusions can be drawn from the experimental results on three UCI data sets:

  1. The incremental updating matrix algorithms (Algorithms 1 and 2) have more effectiveness compared to the non-incremental updating matrix algorithm (Algorithm 3), showing that the time consume in incremental updating algorithm is obviously less that of the non-incremental ones.

  2. For the same data set, the computational times of the incremental updating matrix algorithms and the non-incremental updating matrix algorithm all grow up with the increasing size of sub-data set. Furthermore, Algorithms 1 and 2 are much more faster than Algorithm 3, and the difference between incremental algorithms and the non-incremental algorithm are getting larger and larger while the size of sub-data set increases.

  3. The running times of Algorithm 3 increases sharply with the increasing size of data while the running times of Algorithms 1 and 2 increase very slowly, demonstrating that the larger the size of data, the greater the advantage of Algorithms 1 and 2.

  4. For the incremental update algorithm, the running time of object’s insertion is more less than that of object’s deletion in the same sub-data set. The reason is that there are more loop structure in Algorithm 2, which lead to more time consume.

Figure 4

The curve of time-consuming for updating of approximations at insertion or deletion of a one objects.

It can be seen from the above four conclusions that the incremental update approaches of approximations with trisecting-and-acting model of three-way decisions are feasible and outperform the existing non-incremental approach.

8. CONCLUSIONS

Incrementally updating approximations in rough sets is a critical issue for knowledge update, maintenance and data mining related task in dynamic IS. In this paper, considering the dynamic scenario of one object’s insertion or deletion, an incremental updated mechanism of approximations in DRSA is introduced from the perspective of three-way decisions and three update steps are derived from the updated mechanism. Then we suggested a concrete incremental updating approach of approximations in DRSA while the object set varies, in which Boolean column vectors are used as an expression tool of subsets as well as a calculation tool of approximations. The proposed methods can effectively update the four approximations of DRSA on the basis of the prior approximations. With a numerical example and some test results on UCI data set, we can conclude that the proposed incremental vector method for updating the approximations of DRSA is feasible and can effectively reduce the computational time in comparison to the existing non-incremental vector method when the set of objects changes. One of the further work is to investigate the approaches for updating approximations of DRSA under variations of attribute and attribute value and study the corresponding vector-based incremental algorithms.

CONFLICT OF INTEREST

The authors declare no conflicts of interest.

AUTHORS' CONTRIBUTIONS

All authors have contributed to this paper. The individual responsibilities and contribution of all authors can be described as follows: The idea of this paper was put forward by Lei Wang, he also wrote the paper. Min Li summarized the existing work of the research problem and presented the illustrative example in Section 5. The works in Section 3 were done by Jun Ye. The submission and revision of this paper was completed by Lei Wang and Xiang Yu. The tests on UCI data sets were performed by Ziqi Wang and Shaobo Deng. The other works of this paper were done by Lei Wang.

Funding Statement

This work was supported by the fund of Development Plan of Jiangxi Province of China for the Young and Middle-Aged Teachers in Universities to Pursue Study Abroad as a Visiting Scholar (Jiangxi Education Administration Letter [2016] No. 169), the National Natural Science Foundation of China (Nos. 61562061, 6136304 and 61703199), and the fund of Science and Technology Project of Ministry of Education of Jiangxi province of China (No. GJJ170995).

ACKNOWLEDGMENTS

The author would like to thank reviewers of the paper for their constructive comments which greatly improve the quality of this paper. This work was supported by the fund of Development Plan of Jiangxi Province of China for the Young and Middle-Aged Teachers in Universities to Pursue Study Abroad as a Visiting Scholar (Jiangxi Education Administration Letter [2016] No. 169), the National Natural Science Foundation of China (No. 61562061, No. 61363047, No. 61703199), and the fund of Science and Technology Project of Ministry of Education of Jiangxi province of China (No. GJJ170995).

REFERENCES

2.Y.Y. Yao, Granular computing: basic issues and possible solutions, in Proceedings of 5th Joint Conference on Information Sciences (Atlantic City, New Jersey), 2000, pp. 186-189.
37.L. Wang, T.R. Li, Q. Liu, and M. Li, A mtrix-based approach for maintenance of approximations under the variation of object set, J. Comput. Appl. Dev., Vol. 50, 2013, pp. 1992-2004.
45.G.L. Liu, The Axiomatization of the rough set upper approximation operations, Fundam. Inform., Vol. 69, 2006, pp. 331-342.
<Previous Article In Issue
Download article (PDF)
Next Article In Issue>
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
12 - 2
Pages
914 - 928
Publication Date
2019/08/22
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.d.190807.001How to use a DOI?
Copyright
© 2019 The Authors. Published by Atlantis Press SARL.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

risenwbib
TY  - JOUR
AU  - Lei Wang
AU  - Min Li
AU  - Jun Ye
AU  - Xiang Yu
AU  - Ziqi Wang
AU  - Shaobo Deng
PY  - 2019
DA  - 2019/08/22
TI  - Dynamic Knowledge Update Using Three-Way Decisions in Dominance-Based Rough Sets Approach While the Object Set Varies
JO  - International Journal of Computational Intelligence Systems
SP  - 914
EP  - 928
VL  - 12
IS  - 2
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.190807.001
DO  - 10.2991/ijcis.d.190807.001
ID  - Wang2019
ER  -