An Update Method of Decision Implication Canonical Basis on Attribute Granulating

1  Introduction

Formal Concept Analysis (FCA) is a data analysis and processing tool proposed by Prof. Wille [1]. FCA has been widely studied [2–5] and applied in machine learning [6–8], data mining [9,10], information retrieval [11,12], conflict analysis [13–15] and recommendation systems [16–18].

In FCA, a formal context is a two-dimensional table that reflects relationships between objects and attributes. Attribute implication is a formal representation of knowledge in formal contexts. Since the number of (attribute) implications extracted from formal context is very large, Qu et al. [19] proposed decision implication to reduce the implications that occur between condition attributes or between decision attributes. Zhai et al. [20] studied the semantical and syntactical characteristics of decision implication from a logical perspective. In particular, in the syntactical aspect, Zhai et al. [20] proposed two inference rules, namely AUGMENTATION and COMBINATION, to perform knowledge reasoning among decision implications. Zhai et al. [21] further investigated the influences of the order and number of times of applying inference rules on knowledge reasoning and designed an optimal reasoning strategy.

The number of decision implications in decision contexts, however, is still huge. Thus, Zhai et al. [22] introduced decision premise and decision implication canonical basis (DICB), and proved that DICB is a complete, non-redundant and optimal set of decision implications. In other words, DICB can not only keep all the information in decision contexts (i.e., completeness), but also contain the least number of decision implications among all complete sets of decision implications (optimality). To generate DICB efficiently, Li et al. [23] proposed a true premise-based generation algorithm for DICB, and Zhang et al. [24] proposed an incremental generation algorithm for DICB.

In fact, researchers have investigated other forms of knowledge representation and reasoning besides decision implication, such as concept rules and granular rules [25,26]. Concept rules are decision implications where both premises and consequences are intents [25], and granular rules are decision implications where both premises and consequences are granular intents [25]. Based on these works, Qin et al. [27] investigated attribute (object)-oriented decision rule acquisition; Xie et al. [28] discussed decision rule acquisition in multi-granularity decision context; Zhi et al. [29] proposed a fuzzy rule acquisition method based on granule description in fuzzy formal context; Hu et al. [30] studied rules whose premises and consequences are dual (formal) concepts and formal (dual) concepts. Zhang et al. [31] compared concept rule, granular rule and decision implication, and found that concept rule has stronger knowledge representation capability than granular rule and decision implication has stronger knowledge representation capability than granular rule and concept rule, i.e., decision implication is the strongest form of knowledge representation and reasoning on decision context. Thus, it is recommended in [21] that a knowledge representation and reasoning system based on decision implication can be constructed in applications by using DICB as the knowledge base and CON-COMBINATION and AUGMENTATION as the inference engine [21].

On the other hand, since granular computing [32] is able to solve complex problems with multi-level structures and facilitate knowledge acquisition at different levels and granulations, many granulation methods have been developed in FCA such as relational granulation [33,34], attribute granulation [35–41], and object granulation [42]. This paper mainly focuses on knowledge discovery on attribute granulating.

The existing attribute granulation methods mainly focus on how to update concept lattice after transforming attribute granulation [35], aiming at reducing the complexity of regenerating concept lattice. For example, Belohlavek et al., Wan et al. and Zou et al. proposed some algorithms to update concept lattice on attribute granulating [35–37]; Shao et al. [38] proposed an algorithm to update object(attribute)-oriented multi-granularity concept lattice.

The existing studies did not take into account knowledge discovery on attribute granulating. Because decision implication is superior to concept rule and granular rule, the paper will examine the update of decision implication on attribute granulating; in particular, since DICB can efficiently represent all the information of decision implication [22], it is sufficient to examine the update of DICB. Thus, the aim of the paper is to examine the relationship between DICBs before and after granulation and find a more efficient method to generate the DICB of the granulation context.

This paper is organized as follows. Section 2 reviews the related concepts and properties of decision implication and DICB; Section 3 introduces granulation context and discusses the updates of decision premises (the premises of DICB) on attribute granulating; Section 4 proposes an incremental method for updating DICB; Section 5 concludes the paper.

2  Basic Notions

This section reviews the basic concepts and conclusions of decision implication and DICB; further details can be found in [19,20].

Definition 1 [19]: Decision context K is a triple K=(G,C∪D,IC∪⁡ID), where G denotes the set of objects, C denotes the set of condition attributes, D denotes the set of decision attributes, C∩D=∅, IC⊆G×C denotes the set of incidence relations between objects and condition attributes, and ID⊆G×D denotes the set of incidence relations between objects and decision attributes. For g∈G,m∈C or m∈D, (g,m)∈IC or (g,m)∈ID means “object g has attribute m”.

Definition 2 [19]: Let K=(G,C∪D,IC∪ID) be a decision context. For A⊆G, B1⊆C and B2⊆D, we define:

(1)   AC={m∈C|(g,m)∈IC,∀g∈A}

(2)   AD={m∈D|(g,m)∈ID,∀g∈A}

(3)   B1C={g∈G|(g,m)∈IC,∀m∈B1}

(4)   B2D={g∈G|(g,m)∈ID,∀m∈B2}

Proposition 1 [19]: Let K=(G,C∪D,IC∪ID) be a decision context. For A1,A2⊆C and B1,B2⊆D, we have:

(1)   A1⊆A2⟹A2C⊆A1C, B1⊆B2⟹B2D⊆B1D

(2)   (A1∪A2)C=A1C∩A2C, (B1∪B2)D=B1D∩B2D

(3)   (A1∩A2)C⊇A1C∪A2C, (B1∩B2)D⊇B1D∪B2D

Definition 3 [20]: Let K=(G,C∪D,IC∪ID) be a decision context. For A⊆C and B⊆D, if AC⊆BD, then A⇒B is called a decision implication of K, where A is the premise of A⇒B and B is the conclusion of A⇒B.

Definition 4 [22]: Let K=(G,C∪D,IC∪⁡ID) be a decision context. A set A⊆C is called a decision premise of K, if A satisfies the following conditions:

(1)   A is minimal with respect to ACD, i.e., if Ai⊂A, then AiCD⊆ACD;

(2)   A is proper, i.e.,

ACD⊃∪{AiCD|Ai⊂A is a decision premise of K}=∪{AiCD|Ai⊂A}(1)

The set

Kⅅ∗=∪{A⇒ACD|A is a decision premise of K}(2)

is called the decision implication canonical basis (DICB) of K.

Zhai et al. [22] proved that for any decision context, DICB is complete, non-redundant, and optimal. In other words, DICB can be considered as a complete (completeness) and compact (non-redundancy and optimality) knowledge representation in decision context. Furthermore, Li et al. [23] proved that the properness of decision premise implies minimality, i.e., A is a decision premise if and only if A is proper.

3  DICB on Attribute Granulating

This section introduces granulation context based on attribute granularity refinement [39] and studies the update of decision premises.

Definition 5: Let K=(G,C∪D,IC∪ID) be a formal context and a∈C. The attribute a can be refined to a set of attributes {a1,a2,…,an}, where aiC≠∅, aiC∩ajC=∅ for i≠j, and ∪i=1naiC=aC. The decision context Ka=(G,Ca∪D,ICa∪ID) is called a granulation context of K, where Ca=C∖{a}∪{a1,a2,…,an} and ICa={(g,m)|g∈G,m∈Ca,g∈mC}.

It can be seen from Definition 5 that the refinement of a divides a into n mutually exclusive attributes {a1,a2,…,an}, and any object cannot have any two of them at the same time. In other words, aiC, i=1,2,…,n constitute a partition of aC. Obviously, we have 1<n≤|aC|. In granulation context, since the attribute a has been refined, Ca thus removes a from C and adds the refined attributes {a1,a2,…,an}.

Example 1. A decision context for bank marketing is shown in Table 1, where G={g1,g2,g3,g4,g5,g6,g7,g8,g9} containing nine customers, and C={a,b,c,d,e,f,g} and D={h,i} representing the features of the customers, where a stands for whether the customer has a job, b stands for whether the customer is married, c stands for whether the customer has a bachelor’s degree or above, d stands for whether the customer has a credit default, e stands for whether the customer has a home loan, f stands for whether the customer has a personal loan, g stands for whether the customer has contacted other customers within six months, h stands for whether the customer has applied for a loan, and i stands for whether the customer will make a fixed deposit.

When attribute a is granulated, “has a job” is granulated into “doctor”, “teacher”, “civil servant”, “self-employed” and “other professions”, recorded as, a1: doctor, a2: teacher, a3: civil servant, a4: self-employed, a5: other profession.

The granulation context is shown in Table 2, where G={g1,g2,g3,g4,g5,g6,g7,g8,g9}, Ca=C∖{a}∪{a1,a2,a3,a4,a5}={b,c,d,e,f,g}∪{a1,a2,a3,a4,a5}={a1,a2,a3,a4,a5,b,c,d,e,f,g}, and D={h,i}.

According to [22], DICB can retain all the knowledge in decision context. Therefore, DICB after attribute granulation can also retain all the knowledge in granulation context. Furthermore, since decision premise determines DICB [22], the update of DICB can be reduced to the update of decision premises.

To simplify discussion, this paper divides the updates of decision premises into two steps, namely, the update of decision premises after deleting attribute a and the update of decision premises after adding granulation attributes {a1,a2,…,an}.

3.1 The Updates of Decision Premises after Deleting Attribute

After attribute a is removed from K=(G,C∪D,IC∪ID), the new decision context is denoted as:

Ka¯=(G,Ca¯∪D,Ia¯∪ID)(3)

where Ca¯ = C∖{a} and Ia¯⊆G×Ca¯∩IC. In order to avoid confusion, the operation (.)C in Ka¯ is denoted as (.)C¯. Since D does not change, (.)D is applicable in Ka¯.

Because decision premise is defined by the operator (.)CD, in order to examine the update of decision premise from K to Ka¯, it is necessary to examine the update from ACD to ACD¯, i.e., from ACD to AC¯D.

First, the following properties are given.

Proposition 2: For decision contexts K and Ka¯, let A⊆C. Then, the following conclusions hold:

(1)   If a∉A, then AC¯=AC, namely AC¯D=ACD

(2)   If a∈A, then AC¯D∪aCD⊆ACD

(3)   AC¯D⊆ACD

Proof: (1) If a∉A, by the definitions of (.)C and (.)C¯, we can obtain AC¯=AC and thus AC¯D=ACD.

(2) If a∈A, by the definitions of (.)C and (.)C¯, we have AC=(A∖{a}∪a)C=(A∖{a})C∩aC=AC¯∩aC. Thus, we obtain ACD=(AC¯∩aC)D⊇AC¯D∪aCD and thus AC¯D∪aCD⊆ACD.

(3) It follows from (1) and (2).

In order to generate the decision premises of Ka¯ by the decision premises of K, we classify the changes of decision premises from K to Ka¯ into three cases:

(1)   If A is a decision premise of K and A is also a decision premise of Ka¯, A is an unchanged decision premise.

(2)   If A is a decision premise of K and A is not a decision premise of Ka¯, A is an invalid decision premise.

(3)   If A is not a decision premise of K and A is a decision premise of Ka¯, A is a new decision premise.

The following conclusion identifies the characteristics of unchanged decision premises.

Proposition 3: For decision contexts K and Ka¯, if A is a decision premise of K, then A is an unchanged decision premise if and only if a∉A.

Proof: Sufficiency: By Proposition 2, if a∉A, then we have AC¯D=ACD. Furthermore, for Aj such that Aj⊂A, since a∉Aj, we have AjC¯D=AjCD. Because A is a decision premise of K, we have AC¯D=ACD⊃∪{AjCD|Aj⊂A}=∪{AjC¯D|Aj⊂A}. According to Definition 4, A is a decision premise of Ka¯.

Necessity: Since A is an unchanged decision premise, A is a decision premise of Ka¯.

The following conclusion identifies the characteristics of invalid decision premises.

Proposition 4: For decision contexts K and Ka¯, if A is a decision premise of K, then A is an invalid decision premise if and only if a∈A.

Proof: If A is a decision premise of K, then A is an invalid decision premise or an unchanged decision premise. In this case, if A is an invalid decision premise, A is not an unchanged decision premise and by Proposition 3, we have a∈A. Conversely, if a∈A, by Proposition 3, A is not an unchanged decision premise and A must be an invalid decision premise.

The following result shows that there does not exist new decision premise in Ka¯.

Proposition 5: For decision context Ka¯, there does not exist new decision premise.

Proof: Assume that A is a new decision premise of Ka¯. Since A is a decision premise of Ka¯, by the definition of Ka¯, we have a∉A and by Proposition 2, we have AC¯=AC. Thus, there does not exist new decision premise in Ka¯.

It can be seen from Proposition 5 that decision premises from K to Ka¯ can be divided into two categories: unchanged decision premise and invalid decision premise. Because the invalid decision premises do not hold in Ka¯, the decision premises in Ka¯ only contain the unchanged decision premises of K. In other words, no new decision premises should be added after removing the condition attribute, and new decision premises appear after adding granulation attributes.

3.2 The Updates of Decision Premise after Adding Granulation Attributes

This section examines the update of decision premise in Ka from decision premise in Ka¯ after adding the granulation attributes {a1,a2,…,an} to Ka¯.

Similarly, we classify the changes of decision premises from Ka¯ to Ka into three cases:

(1)   If A is a decision premise of Ka¯ and A is also a decision premise of Ka, A is an unchanged decision premise.

(2)   If A is a decision premise of Ka¯ and A is not a decision premise of Ka, A is an invalid decision premise.

(3)   If A is not a decision premise of Ka¯ and A is a decision premise of Ka, A is a new decision premise.

In order to avoid confusion, the operation (.)C in Ka is denoted as (.)C~. Since D does not change, (.)D is applicable in Ka. The properties of (.)C¯ and (.)C~ in Ka¯ and Ka are given below.

Proposition 6: For decision contexts Ka¯ and Ka, and A⊆Ca, the following conclusions hold:

(1)   If A⊆Ca¯, then AC¯=AC~, AC¯D=AC~D

(2)   If A⊈Ca¯, then (A∩Ca¯)C¯D⊆AC~D.

Proof: (1) By the definitions of (.)C~ and (.)C¯, it is obvious.

(2) By (1), we have (A∩Ca¯)C¯D=(A∩Ca¯)C~D, and by A∩Ca¯⊆A, we have (A∩Ca¯)C~D⊆AC~D and thus (A∩Ca¯)C¯D⊆AC~D.

The following conclusion identifies the characteristics of unchanged and invalid decision premises from Ka¯ to Ka.

Proposition 7: For decision contexts Ka¯ and Ka, if A is a decision premise of Ka¯, then A is a decision premise of Ka.

Proof: Since A is a decision premise of Ka¯, we have A⊆Ca¯⊆Ca and by Proposition 6, we have AC~D=AC¯D; furthermore, for Aj satisfying Aj⊂A⊆Ca¯⊆Ca, we have AjC~D=AjC¯D and thus AC~D=AC¯D⊃⋃{AjC¯D|Aj⊂A}=⋃{AjC~D|Aj⊂A}. It can be seen from Definition 4 that A is a decision premise of Ka¯.

Proposition 7 shows that all the decision premises of Ka¯ are the unchanged decision premises of Ka. Thus, according to the classification of decision premises of Ka, there does not exist invalid decision premise from Ka¯ to Ka.

Next, we discuss the new decision premises in Ka.

Proposition 8: If A is a new decision premise from Ka¯ to Ka, then there exists only one ai∈{a1,a2,…,an} such that ai∈A.

Proof: First, we will prove that there exists ai∈{a1,a2,…,an} such that ai∈A. Since A is a new decision premise from Ka¯ to Ka, A is not a decision premise of Ka¯ and A is a decision premise of Ka, i.e., we have AC¯D=⋃{AjC¯D|Aj⊂A} and AC~D⊃⋃{AjC~D|Aj⊂A}. If there does not exist ai∈{a1,a2,…,an} such that ai∈A, we have A⊆Ca¯. By Proposition 6, we have AC~D=AC¯D; similarly, for Aj satisfying Aj⊂A⊆Ca¯⊆Ca, we have AjC~D=AjC¯D and thus AC~D=AC¯D=⋃{AjC¯D|Aj⊂A}=⋃{AjC~D|Aj⊂A}, which contradicts with AC~D⊃⋃{AjC~D|Aj⊂A}. Thus, we have A⊈Ca¯, and there must exist ai∈{a1,a2,…,an} such that ai∈A.

Next, suppose that more than one attribute in {a1,a2,…,an} may be contained in A, say, {ai1,ai2,…,aik}⊆A, 2≤k≤n.

By the definition of redundant decision implication, a decision implication E⇒F is redundant with respect to a set L of decision implications if and only if for any T⊆Ca∪D, if T satisfies L, then T also satisfies E⇒F. Therefore, if any T⊆Ca∪D satisfies E⇒F, then E⇒F is redundant with respect to any L.

For any T⊆Ca∪D, by the definition of granulation attributes, there exists at most one ak∈{a1,a2,…,an} such that ak∈T. Therefore, we have {ai1,ai2,…,aik}⊈T, and since {ai1,ai2,…,aik}⊆A, we have A⊈T, i.e., T satisfies A⇒AC~D. Thus, A⇒AC~D is a redundant decision implication of Ka. Since DICB is non-redundant, A is not a decision premise, which contradicts with the fact that A is a new decision premise of Ka.

By the discussion in Sections 3.1 and 3.2, for a decision premise A of K, if a∉A, by Proposition 3 and Proposition 7, A must be a decision premise of Ka¯ and also a decision premise of Ka. In addition, by Proposition 7 and 8, the decision premises of Ka also include the new decision premises of the form {ai}∪E, where ai∈{a1,a2,…,an} and E⊆Ca¯, which can be generated based on true premise, as shown in Section 4.

4  Algorithm for Updating DICB on Attribute Granulating

By Section 3, some decision premises of Ka can be directly obtained by judging whether the attribute a is contained in the decision premises A of K, and other decision premises of Ka is of the form {ai}∪E. By Definition 4, in order to determine whether {ai}∪E is a decision premise, it is necessary to determine whether each subset of {ai}∪E is a decision premise. Due to the complexity of enumerating all the subsets of {ai}∪E, we propose a true premise [23] based algorithm for determining whether {ai}∪E is a decision premise, as well as updating DICB.

Firstly, Definition 6 gives the definition of true premise.

Definition 6 [23]: Let K=(G,C∪D,IC∪ID) be a decision context. For A⊆C and B⊆D, A is a true premises of B, if A satisfies the following conditions:

(1)   A is a premise of B (i.e., AC⊆BD).

(2)   For any Ai⊂A, Ai is not a true premise of B.

The following theorem shows the equivalence of the decision premise and the true premise.

Theorem 1 [23]: Let K=(G,C∪D,IC∪ID) be a decision context and A⊆C. Then, A is a decision premise if and only if A is a true premise of some d∈ACD.

According to Theorem 1, we can determine whether {ai}∪E is a decision premise of Ka by determining whether {ai}∪E is a true premise of some decision attributes. In other words, in order to generate the decision premises of the form {ai}∪E, it is sufficient to generate all the true premise of some d∈D that contains ai.

Definition 7 defines the symbols needed to calculate true premise.

Definition 7 [23]: Let K=(G,C∪D,IC∪ID) be a decision context. For d∈D and g∈G, denote d∉={g∈G|d∉gD} and define g↙d if the following conditions are satisfied:

(1)   g∈d∉;

(2)   For h∈G, if gC⊂hC, then d∈hD.

For d∈D, we denote Φ(d)={g∈G|g↙d}.

Definition 8 gives the concepts of candidate premise and candidate true premise, which are used in the process of generating true premise.

Definition 8 [23]: Let K=(G,C∪D,IC∪ID) is a decision context. For A⊆C, d∈D and P⊆Φ(d), we define:

(1)   If P=∅, or for any g∈P, we have A⊈gC, then A is called a candidate premise of d under P, denoted by A→Pd; otherwise, we denote A↛Pd.

(2)   If A→Pd, and for any Ai⊂A, we have Ai↛Pd, then A is called a candidate true premise of d under P, denoted by A⋅→Pd; otherwise, we denote A⋅↛Pd.

Proposition 9 [23]: Let K=(G,C∪D,IC∪ID) be a decision context. For A⊆C and d∈D, we have:

(1)   If A→Φ(d)d, then A is a premise of d.

(2)   If A⋅→Φ(d)d, then A is a true premise of d.

By Definition 7 and Proposition 9, true premise can be identified based on Φ(d) and on d∉. Since d∉ is unchanged on attribute granulating, we need to discuss the change of Φ(d) on attribute granulating. In Ka, Φ(d) is denoted as Φ′(d).

Proposition 10: Let K=(G,C∪D,IC∪ID) be a decision context and Ka=(G,Ca∪D,ICa∪ID) be a granulation context of K, and d∈D. Then we have:

(1)   Φ(d)⊆Φ′(d).

(2)   Φ′(d)=Φ(d)∪{g∈(aC∩d∉)∖Φ(d)|For any h∈d∉such that hC⊃gC,there does not exist ai∈Casuch that {g,h}⊆aiC~}.

Proof: (1) By the definitions of Φ(d) and Φ′(d), it is sufficient to prove that for g∈Φ(d), there does not exist h∈d∉ in Ka such that gC~⊂hC~.

If g∉aC, by the granulation process of a in Definition 5, for any ai∈Ca, we have g∉aiC~, i.e., gC=gC~. In Ka, for h∈d∉, we need to consider two cases: (a) If for any ai∈Ca, we have h∉aiC~, we obtain hC=hC~. From g∈Φ(d), it follows that there does not exist h∈d∉ such that gC⊂hC in K, i.e., there does not exist h∈d∉ such that gC~⊂hC~. (b) If there exists ai∈Ca such that h∈aiC~, by Definition 5, there exists only one ai∈Ca such that h∈aiC~. Then, we have hC~=hC∖{a}∪{ai}. Assume gC=gC~⊂hC~. By g∉aC, it is easy to prove that gC⊆hC∖{a}⊂hC. By the definition of Φ(d) and g∈Φ(d), we have d∈hD and thus h∉d∉, which contradicts with h∈d∉. Therefore, there does not exist h∈d∉ such that gC~⊂hC~.

If g∈aC, we assume g∉Φ′(d), i.e., there exists h∈d∉ in Ka such that gC~⊂hC~. By g∈aC and the granulation process of a, there exists only one ai∈Ca such that g∈aiC~, and since gC~⊂hC~, we have h∈aiC~ and thus {g,h}⊆aiC~. Since aiC~⊂aC, we have {g,h}⊂aC. From hC~=hC∖{a}∪{ai} and gC~=gC∖{a}∪{ai}, it follows hC∖{a}∪{ai}⊃gC∖{a}∪{ai}, i.e., hC⊃gC. By the definition of Φ(d) and g∈Φ(d), we have d∈hD and thus h∉d∉, which contradicts with h∈d∉. Thus, there does not exist h∈d∉ such that gC~⊂hC~.

(2) By the definition of Φ′(d), we have Φ′(d)={g∈d∉|for any h∈d∉,there is hC~⊅gC~}. By Conclusion (1), we have Φ(d)⊆Φ′(d)⊆d∉ and thus Φ′(d)=Φ(d)∪{g∈d∉∖Φ(d)|for any h∈d∉,hC~⊃gC~ holds}.

Next, we prove that for any g∈d∉∖Φ(d), we have a∈gC. Assume a∉gC, i.e., g∉aC. By g∉Φ(d), there exists h∈d∉ in K such that hC⊃gC. We need to consider two cases. (a) If h∈aC, by the granulation process of a in Definition 5, there exists only one ai∈Ca such that h∈aiC~. In this case, we have hC~=hC∖{a}∪{ai}. By a∉gC, we have hC∖{a}⊇gC and thus hC~⊃gC. By g∉aC and the proving process of (1), it is easy to prove gC=gC~, and we have hC~⊃gC~, i.e., h satisfies hC~⊃gC~ and h∈d∉. Thus, we have g∉Φ′(d), which contradicts with g∈Φ′(d). Thus, we obtain g∈aC. (b) If h∉aC, by g∉aC and the proving process of (1), we have gC=gC~ and hC=hC~, and thus hC~=hC⊃gC=gC~. Since hC~⊃gC~ and h∈d∉, we have g∉Φ′(d), which contradicts with g∈Φ′(d). Thus, we obtain g∈aC.

Combining with Φ′(d)=Φ(d)∪{g∈d∉∖Φ(d)|for any h∈d∉,hC~⊅gC~holds}, we obtain Φ′(d)=Φ(d)∪{g∈(aC∩d∉)∖Φ(d)|for any h∈d∉,hC~⊅gC~holds}. It is sufficient to prove that for g∈(aC∩d∉)∖Φ(d), the following two conditions are equivalent: Condition 1: For any h∈d∉, h satisfies hC~⊅gC~, and Condition 2: For any h∈d∉ such that hC⊃gC, there does not exist ai∈Ca such that {g,h}⊆aiC~.

First, we prove that if g∈(aC∩d∉)∖Φ(d) satisfies Condition 1, then g also satisfies Condition 2. Assume that there exists h∈d∉ such that hC⊃gC, and that there exists ai∈Ca such that {g,h}⊆aiC~. By g∈aC, we have a∈gC⊂hC and thus {g,h}⊆aC. Combining {g,h}⊆aC, {g,h}⊆aiC~ with the granulation process of a, we obtain hC~=hC∖{a}∪{ai} and gC~=gC∖{a}∪{ai}; since hC⊃gC, we have hC~⊃gC~. Thus, there is h∈d∉ such that hC~⊃gC~, which is contradictory to Condition 1.

Next, we prove that if g∈(aC∩d∉)∖Φ(d) satisfies Condition 2, then g also satisfies Condition 1. Assume h∈d∉. If hC⊃gC, according to Condition 2, there does not exist ai∈Ca such that {g,h}⊆aiC~. In this case, by g∈aC and h∈aC, according to the granulation process of a, there must exist aj,ak∈Ca such that g∈ajC~ and h∈akC~; because there does not exist ai∈Ca such that {g,h}⊆aiC~, we have aj≠ak, g∉akC~, and h∉ajC~, i.e., hC~⊅gC~. If hC⊅gC, we have hC⊅gC or hC=gC. If hC=gC, we have hC~=gC~, i.e., hC~⊅gC~. If hC⊅gC, we will prove hC~⊅gC~ in two cases. (a) If a∈hC, since hC⊅gC, there must exist b1∈C such that b1≠a, b1∈gC, and b1∉hC. It is easy to prove hC~⊅gC~. (b) If a∉hC, by the granulation process of a, there does not exist ai∈{a1,a2,…,an} such that ai∈hC~. By g∈aC and the granulation process of a, there is ai∈{a1,a2,…,an} such that ai∈gC~. Thus, we have hC~⊅gC~.

Next, we will generate the true premises of d that contains ai, starting from determining whether ai is a true premise of d.

Proposition 11: Let Ka=(G,Ca∪D,ICa∪ID) be a granulation context, d∈D, and ai∈{a1,a2,…,an}. Setting P=Φ′(d)∖aiC~≠∅, then we have {ai}⋅→Pd.

Proof: For any g∈P, we have ai∉gC~, i.e, {ai}⊈gC~, and thus {ai}→Pd. Furthermore, since {Ai|Ai⊂{ai}}={∅} and ∅⊆gC~, i.e., ∅↛Pd, by Definition 8, we have {ai}⋅→Pd.

At this time, we obtain the candidate true premise {ai} of d under P according to Proposition 11. Next, we need to gradually increase P to Φ(d) to determine whether {ai} is the true premise of d. In the incremental process, reference [23] classified candidate true premises into three cases (Definition 9) and discussed their properties (Proposition 12).

Definition 9 [23]: Let K=(G,C∪D,IC∪ID) be a decision context. For A⊆C, d∈D, P⊆Φ(d), and g∈Φ(d)∖P, we define:

(1)   If A⋅→Pd and A⋅→P∪{g}d, then A is called an unchanged candidate true premise of d under P∪{g}.

(2)   If A⋅→Pd and A⋅↛P∪{g}d, then A is called an invalid candidate true premise of d under P∪{g}.

(3)   If A⋅↛Pd and A⋅→P∪{g}d, then A is called a new candidate true premise of d under P∪{g}.

Proposition 12 [23]: Let K=(G,C∪D,IC∪ID) be a decision context. For A⊆C, d∈D, P⊆Φ(d) and g∈Φ(d)∖P, we have:

(1)   A is an unchanged candidate true premise of d under P∪{g} if and only if A⋅→Pd and A⊈gC.

(2)   A is an invalid candidate true premise of d under P∪{g} if and only if A⋅→Pd and A⊆gC.

(3)   A is a new candidate true premise of d under P∪{g} if and only if the following conditions hold:

a)   A⋅↛Pd

b)   There exists an invalid candidate true premise Am satisfying A=Am∪{a} for a∈C−gC

c)   For any Ai⊂A, we have Ai⋅↛P∪{g}d.

By Definition 9 and Proposition 12, the objects in the set Φ′(d)∩aiC~ can be gradually added into P. If {ai}⋅→Φ′(d)d, then {ai} is a true premise of d; otherwise {ai} is not a true premise of d. After adding g in Φ′(d)∩aiC~ to P, by Definition 9, {ai} may be an unchanged or an invalid candidate true premise of d under g. If {ai} is an unchanged candidate truth premise, we can continue to add the remaining objects in Φ′(d)∩aiC~ to P. If {ai} is an invalid candidate truth premise, by Proposition 12(3), A={ai}∪{b} can be generated, where b∈Ca−gC. In this case, it needs to further judge whether A={ai,b} is a new candidate true premise of d under P∪{g} by Proposition 12(3). If {ai,b} is a new candidate true premise, the remaining objects in Φ′(d)∩aiC~ should be gradually added to P∪{g} to determine whether {ai,b}⋅→Φ′(d)d holds according to the above process. By repeating the above process, one can generate all the true premises of d of the form {ai}∪E.

The above process can be further optimized. For example, Proposition 13 shows that if ai satisfies some conditions, ai is a true premise of d. In this case, except ai, all the sets of the form {ai}∪E (E≠∅) may not be the true premises of d, and there is no need to determine other sets {ai}∪E.

Proposition 13: Let Ka=(G,Ca∪D,ICa∪ID) be a granulation context, d∈D, Φ′(d)≠∅ and ai∈{a1,a2,…,an}. If aiC~∩Φ′(d)=∅, then {ai} is a true premise of d.

Proof: Let P={g|g∈Φ′(d)∖aiC~}. If aiC~∩Φ′(d)=∅, then we have P=Φ′(d). By Proposition 12, we obtain {ai}⋅→Pd, i.e., {ai}⋅→Φ′(d)d, and by Proposition 9, we know that ai is a true premise of d.

A true premise-based incremental method can then be proposed for generating DICB under attribute granulation, as shown in Algorithm 1.

In Algorithm 1, we first generate the unchanged decision premises by the decision premises of K according to the results in Section 3 (Steps 2–6), and then generate the new decision premise of Ka by generating the true premises of each d that contain ai (Steps 7–20). In Steps 7–20, for a decision attribute d, we first generate Φ′(d) by the function get_newgd (Step 8), then generate the new decision premises {ai}∪E for each ai by generator_newdp (Steps 10–13), and finally generate the decision implications of the new decision premises (Steps 14–18). In Steps 10–13, by Proposition 13, if aiC~∩Φ′(d)=∅, only ai is a true premise of d in the sets {ai}∪E. Otherwise, it is necessary to gradually add the objects in aiC~∩Φ′(d) by the function generator_newdp to obtain dpai, the set of all the true premises of d of the form {ai}∪E.