Printer Friendly

Rule acquisition in formal decision contexts based on formal, object-oriented and property-oriented concept lattices.

1. Introduction

Formal concept analysis (FCA) is a field of applied mathematics based on the mathematization of formal concepts and conceptual hierarchy [1]. This theory starts with the notion of a formal context (G,M, I) consisting of an object set G, an attribute setM, and an incidence relation I between G and M [2]. Its key characteristic lies in the conceptual unfolding of data. Nowadays, FCA has been applied in many domains such as information retrieval [3], machine learning [4], knowledge discovery [5-15], and software engineering [16, 17]. What is more, it has shown a trend of multidisciplinary intersection.

In FCA, a basic way of describing dependencies between the attributes of a formal context is via implications [18, 19] or association rules [20]. Considering that directly deriving these types of rules from a formal context involves so many calculations and the number of rules is generally large, some researchers [21-23] discussed how to efficiently mine implications/association rules from a formal context and eliminate superfluous rules as many as possible. This issue was also investigated in generalized formal contexts [24].

In the real world, a formal context often contains target attributes for the purpose of making decision analysis. A formal context equipped with additional target attributes is called a formal decision context [25] (or a decision formal context sometimes) which is in fact a training context [26]. Note that rule acquisition is one of the main purposes in the analysis of formal decision contexts and in recent years this issue has attracted much attention from the Chinese FCA community. For instance, Zhang and Qiu [25] put forward the first type of rules, called decision rules, in formal decision contexts through combining conditional formal concepts with decision formal concepts. In order to eliminate superfluous decision rules, Li et al. [27] proposed the notion of a nonredundant decision rule and an approach to extract all nonredundant decision rules from a formal decision context, which was improved in [28] by integrating granular computing into decision rules for decreasing computation time. Moreover, the notion of a decision rule was extended into the cases of incomplete formal decision contexts [29] and real formal decision contexts [30, 31]. Besides, Qu et al. [32] presented the second type of rules, called decision implications, whose premises and conclusions are taken from conditional attributes and decision attributes, respectively. It should be pointed out that decision rules are special decision implications. Following the above discussion, Zhai et al. [33] discussed the semantical and syntactical aspects of decision implications. Additionally, based on granular computing, Wu et al. [34] defined the third type of rules, called granular rules, which are special decision rules, with their premises and conclusions being the intents of conditional formal concepts and decision formal concepts, respectively. A detailed investigation on relation between granular rules and decision rules can also be found in [28].

The aforementioned types of rules in formal decision contexts, which were investigated within the framework of classical FCA, can be viewed as [conjunction]-rules since all of them have the following form: "if conditions 1, 2, ..., and m hold, then decisions hold." Considering that object-oriented concept lattice [35] and property-oriented concept lattice [36] possess useful characteristics from both FCA and rough set theory [37] for data analysis and they have been proven to be beneficial to knowledge discovery [38, 39], this study puts forward two new types of rules, called [disjunction]-rules and [disjunction]-[conjunction] mixed rules, using formal, object-oriented, and property-oriented concept lattices. The current work can enrich the existing rule acquisition theory in formal decision contexts.

The rest of this paper is organized as follows. Section 2 reviews some basic notions and properties related to formal, object-oriented, and property-oriented concept lattices. Section 3 discusses the issue of rule acquisition in formal decision contexts based on formal, object-oriented, and property-oriented concept lattices. More specifically, the notions of a [disjunction]-rule and a [disjunction]-[conjunction] mixed rule are proposed. Furthermore, we put forward approaches to derive all non-redundant [disjunction]-rules and [disjunction]-[conjunction] mixed rules from a formal decision context. Section 4 makes a comparison of the inclusion and inference relationships among [disjunction]-rules, [disjunction]-[conjunction] mixed rules, and [conjunction]-rules. Section 5 conducts some numerical experiments to compare the performances of the proposed rule acquisition algorithms and the existing one.

2. Preliminaries

In what follows, we briefly recall some basic notions and properties related to formal, object-oriented, and property-oriented concept lattices.

Definition 1 (see [1]). A formal context is a triple (G,M, I) including an object setG, an attribute setM, and an incidence relation I [subset or equal to] GxM, in which(x, a) [member of] I indicates that the object x has the attribute a and (x, a) [not member of] I means the opposite.

Definition 2 (see [25]). A formal context (G,M, I) is said to be regular if, for any (x, a) [member of] GxM, the following conditions hold:

(i) there exist [a.sub.1], [a.sub.2][member of] M such that (x, [a.sub.1]) [member of] I and (x, [a.sub.2]) [not member of] I;

(ii) there exist [x.sub.1], [x.sub.2][member of] G such that ([x.sub.1], a) [member of] I and ([x.sub.2], a) [not member of] I.

Without loss of generality, the formal contexts discussed hereinafter are all assumed to be regular.

In order to derive formal, object-oriented, and property-oriented concept lattices, the following six operators are needed: for any X [subset or equal to] G and B [subset or equal to] M,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Note that the pair of operators ([up arrow], [down arrow]) forms an antitone Galois connection, while the pairs of operators ([??],[??]) and ([??], [??]) formisotone Galois connections [39].More properties about these operators can be found below.

Proposition 3 (see [2, 35, 36]). Let (G,M, I) be a formal context. For X,[X.sub.1], [X.sub.2][subset or equal to] G and B, [B.sub.1], [B.sub.2][subset or equal to] M, the following properties hold:

(i) [X.sub.1][subset or equal to] [X.sub.2][??][X.sup.[up arrow].sub.2][subset or equal to] [X.sup.[up arrow].sub.1], [X.sup.[??].sub.1][subset or equal to] [X.sup.[??].sub.2], [X.sup.[??].sub.1][subset or equal to] [X.sup.[??].sub.2] ;

(ii) [B.sub.1][subset or equal to] [B.sub.2][??] [B.sup.[down arrow].sub.2][subset or equal to] [B.sup.[down arrow].sub.1], [B.sup.[??].sub.1] [subset or equal to] [B.sup.[??].sub.2], [B.sup.[??].sub.1][subset or equal to] [B.sup.[??].sub.2] ;

(iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(v) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(vi) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Definition 4 (see [1, 2, 35, 36]). Let (G,M, I) be a formal context, X [subset or equal to] G, and B [subset or equal to] M. If [X.sup.[up arrow]] = B and [B.sup.[down arrow]]= X, then (X, B) is called a formal concept; if X[??]= Band [B.sup.[??]] = X, then (X, B) is called an object-oriented concept; if X[??] = B and [B.sup.[??]] = X, then (X, B) is called a property-oriented concept. For each of the cases, X and B are called the extent and intent of (X, B), respectively.

When the formal, object-oriented, and property-oriented concepts of a formal context (G,M, I) are, respectively, ordered by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

they form complete lattices which are called the formal, object-oriented, and property-oriented concept lattices [1, 35, 36] of the formal context (G,M, I), respectively. Hereinafter, we denote formal concept lattice by [[B.bar].sub.F](G,M, I), object-oriented concept lattice by [[B.bar].sub.O](G,M, I), and property-oriented concept lattice by [[B.bar].sub.p](G,M, I).

In the concept lattices [[B.bar].sub.F](G,M, I), [[B.bar].sub.O](G,M, I), and [[B.bar].sub.p](G,M, I), the infimum and supremum of two concepts ([X.sub.1], [B.sub.1]) and ([X.sub.2], [B.sub.2]) are, respectively, defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

It should be pointed out that the relation among formal, object-oriented, and property-oriented concept lattices was discussed in [38, 39], and knowledge reduction of object-oriented and/or property-oriented concept lattices was investigated in [7, 40, 41].

3. Rule Acquisition in Formal Decision Contexts Based on Formal, Object-Oriented, and Property-Oriented Concept Lattices

Definition 5 (see [25, 26]). A formal decision context is a quintuple (G,M, I,N, J), where (G,M, I) and (G,N, J) with M[intersection]N = 0 are two formal contexts. Here, M and N are called the conditional attribute set and the decision attribute set of (G,M, I,N, J), respectively.

Like the formal context, a formal decision context [PI] = (G,M, I,N, J) is also said to be regular [27] if both (G,M, I) and (G,N, J) are regular. Hereinafter, the concerned formal decision contexts are all assumed to be regular. Moreover, for convenience, [[B.bar].sub.F](G,M, I), [[B.bar].sub.O] (G,M, I),and [[B.bar].sub.p](G,M, I) are, respectively, called conditional formal, object-oriented, and property-oriented concept lattices of [PI], and [[B.bar].sub.F](G,N, J),[[B.bar].sub.O](G,N, J), and [[B.bar].sub.p](G,N, J) are, respectively, called decision formal, object-oriented, and property-oriented concept lattices of [PI].

To the best of our knowledge, the existing work of rule acquisition in formal decision contexts is based on (conditional and decision) formal concept lattices only, and the derived rules B [right arrow] C with B [subset or equal to] M and C [subset or equal to] N can be viewed as [conjunction]-ones since they have the following form: "any object having all conditional attributes of B also has all decision attributes of C." Up to now, such kinds of [conjunction]-rules have successfully been applied to radar fault diagnosis under incomplete environment [42].

In order to widen the domain of application of rule acquisition, now we continue to put forward two new types of rules, called [disjunction]-rules and [disjunction]-[conjunction] mixed rules, based on formal, object-oriented, and property-oriented concept lattices.

3.1. Rule Acquisition Based on Formal and Object-Oriented Concept Lattices. In this subsection, we propose the notion of a [disjunction]-rule in formal decision contexts based on formal and object-oriented concept lattices.

Definition 6. Let [PI] = (G,M, I,N, J) be a formal decision context, let [[B.bar].sub.O](G,M, I) be the object-oriented concept lattice of (G,M, I), and let [[B.bar].sub.F](G,N, J) be the formal concept lattice of (G,N, J). For any (X, B) [member of] [[B.bar].sub.O](G,M, I) and (Y, C) [member of] [[B.bar].sub.F](G,N, J), if X [not equal to] 0, Y [not equal to] G, and X [subset or equal to] Y, then the expression B[[right arrow].sub.[disjunction]]C is called a [disjunction]-rule generated between the object-oriented concept (X, B) and formal concept (Y, C). Here, B and C are called the premise and conclusion of the [disjunction]-rule B [right arrow] C, respectively. The set of all the [disjunction]-rules generated between the object-oriented concepts in[[B.bar].sub.O](G,M, I) and the formal concepts in [[B.bar].sub.F](G,N, J) is denoted by [R.sub.O]([PI]).

Thus, for any B[[right arrow].sub.[disjunction]]C [member of] [R.sub.O]([PI]), we conclude that each x [member of] G having at least one conditional attribute in B has all the decision attributes in C. More specifically, if B = {[b.sub.1], [b.sub.2], ..., [b.sub.s]} and C = {[c.sub.1], [c.sub.2], ..., [c.sub.t]}, then B[[right arrow].sub.[disjunction]]C means that "if [b.sub.1] [disjunction] [b.sub.2] [disjunction] ... [disjunction] [b.sub.s], then [c.sub.1] [conjunction] [c.sub.2] [conjunction] ... [conjunction] [c.sub.t]," where [disjunction] and [conjunction] denote logical disjunction and conjunction operators.

It should be pointed out that the [disjunction]-rules have something to do with both the attribute implication rules and the association rules (see, e.g., [18, 19] for the detailed introduction of the attribute implication rules and, e.g., [20, 23] for that of the association rules). Concretely, a [disjunction]-rule B[[right arrow].sub.[disjunction]]C with B = {[b.sub.1], [b.sub.2], ..., [b.sub.s]} and C = {[c.sub.1], [c.sub.2], ..., [c.sub.t]} can be integrated by the following attribute implication rules (or association rules with their confidences being one):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

However, an attribute implication rule may not be a [disjunction]-rule since its premise is not an expression of disjunction of conditional attributes except a singleton set. Yet, an association rule may not be a [disjunction]-rule since its confidence is often less than one.

Definition 7. Let [PI] = (G,M, I,N, J) be a formal decision context. For [B.sub.1][[right arrow].sub.[disjunction]][C.sub.1], [B.sub.2][[right arrow].sub.[disjunction]][C.sub.2][member of] [R.sub.O]([PI]), if [B.sub.2][subset or equal to] [B.sub.1] and [C.sub.2] [subset or equal to] [C.sub.1], one says that [B.sub.2][[right arrow].sub.[disjunction]][C.sub.2] can be implied by [B.sub.1][[right arrow].sub.[disjunction]][C.sub.1]. One denotes this implication relationship by [B.sub.1][[right arrow].sub.[disjunction]][C.sub.1][??] [B.sub.2][[right arrow].sub.[disjunction]][C.sub.2]. For any B[[right arrow].sub.[disjunction]]C [member of] [R.sub.O]([PI]), if there exists [B.sub.0][[right arrow].sub.[disjunction]][C.sub.0][member of] [R.sub.O]([PI]) \ {B[[right arrow].sub.[disjunction]]C} such that [B.sub.0][[right arrow].sub.[disjunction]][C.sub.0][??] B[[right arrow].sub.[disjunction]]C, thenB[[right arrow].sub.[disjunction]]C is said to be redundant in [R.sub.O]([PI]); otherwise, B[[right arrow].sub.[disjunction]]C is said to be nonredundant in [R.sub.O]([PI]). We denote by [R.sup.*.sub.O]([PI]) the set of all of the nonredundant [disjunction]-rules in [R.sub.O]([PI]).

It can be known from Definition 7 that, for a given formal decision context, it is more appealing to extract the nonredundant [disjunction]-rules since they can imply others.

ALGORITHM 1: Deriving the nonredundant [disjunction]-rules from a
formal decision context.

Input: A formal decision context [PI] = (G,M, I,N, J).
Output: All the nonredundant [disjunction]-rules of [PI].
     (1) Initialize [OMEGA] = 0.
     (2) Construct the object-oriented concept lattice [[B.bar].sub.O]
     (G,M, I) and the formal concept lattice [[B.bar].sub.F](G,N, J).
     (3) For every ((X, B), (Y, C)) [member of] [[U.bar].sub.O](G,M,
     I) x [[U.bar].sub.F](G,N, J) with X [not equal to] 0 and Y
     [not equal to] G, if [[alpha].sub.O](X, Y) = 1 and [[beta].sub.O]
     (X, Y) = 1, then[OMEGA] [left arrow] [OMEGA][union]
     {B[[right arrow].sub.[disjunction]]C}.
     (4) Output [OMEGA] and end the algorithm.


Let [PI] = (G,M, I,N, J) be a formal decision context. Denote

[[U.bar].sub.O](G, M, I) = {X | (X, B) [member of] [[B.bar].sub.O](G, M, I)}, [[U.bar].sub.F](G, N, J) = {Y | (Y, C) [member of] [[B.bar].sub.F](G, N, J)}. (5)

For any (X, Y) [member of] [[U.bar].sub.O](G,M, I) x [[U.bar].sub.F](G,N, J), define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Theorem 8. For a formal decision context[PI] = (G,M, I,N, J), (X, B) [member of] [[B.bar].sub.O](G,M, I), (Y,C) [member of] [[B.bar].sub.F](G,N, J), and B[[right arrow].sub.[disjunction]]C [member of] [R.sub.O]([PI]). Then, B[[right arrow].sub.[disjunction]]C is redundant in [R.sub.O]([PI]) if and only if [[alpha].sub.O](X, Y) = 0 or [[beta].sub.O](X, Y) = 0, or, equivalently, B[[right arrow].sub.[disjunction]]C is nonredundant in [R.sub.O]([PI]) if and only if [[alpha].sub.O](X, Y) = 1 and [[beta].sub.O](X, Y) = 1.

Proof. Necessity. If B[[right arrow].sub.[disjunction]]C is redundant in [R.sub.O]([PI]), there exists [B.sub.0][[right arrow].sub.[disjunction]][C.sub.0][member of] [R.sub.O]([PI]) {B[[right arrow].sub.[disjunction]]C} such that ([X.sub.0], [B.sub.0]) [member of] [[B.bar].sub.O](G,M, I), ([Y.sub.0], [C.sub.0]) [member of] [[B.bar].sub.F](G,N, J), and [B.sub.0][right arrow] [disjunction][C.sub.0] [??] B[[right arrow].sub.[disjunction]]C. By Definition 7, it follows that B [subset or equal to] [B.sub.0] and C [subset or equal to] [C.sub.0], which implies that X [subset or equal to] [X.sub.0] and [Y.sub.0][subset or equal to] Y. Noting that [X.sub.0][subset or equal to] [Y.sub.0] and [B.sub.0][[right arrow].sub.[disjunction]][C.sub.0] is different from B[[right arrow].sub.[disjunction]]C, we conclude that X [subset] [X.sub.0][subset or equal to] [Y.sub.0][subset or equal to] Y or X [subset or equal to] [X.sub.0][subset or equal to] [Y.sub.0][subset] Y. Consequently, [[alpha].sub.O](X, Y) = 0 or [[beta].sub.O](X, Y) = 0.

Sufficiency. If [[alpha].sub.O](X, Y) = 0 or [[beta].sub.O](X, Y) = 0, we can prove that B[[right arrow].sub.[disjunction]]C is redundant in [R.sub.O]([PI]). In fact, when [[alpha].sub.O](X, Y) = 0, there exists [X.sub.0][member of] [[U.bar].sub.O](G,M, I) such that X [subset] [X.sub.0][subset or equal to] Y. Suppose ([X.sub.0], [B.sub.0]) [member of] [[B.bar].sub.O](G,M, I). Then, [B.sub.0][[right arrow].sub.[disjunction]]C [??] B[[right arrow].sub.[disjunction]]C. As a result, B[[right arrow].sub.[disjunction]] C is redundant in [R.sub.O]([PI]). When [[beta].sub.O](X, Y) = 0, there exists [Y.sub.0][member of] [[U.bar].sub.F](G,N, J) such that X [subset or equal to] [Y.sub.0][subset] Y. Suppose ([Y.sub.0], [C.sub.0]) [member of] [[B.bar].sub.F](G,N, J). Then, B[[right arrow].sub.[disjunction]][C.sub.0][??] B[[right arrow].sub.[disjunction]]C. Consequently, B[[right arrow].sub.[disjunction]]C is redundant in [R.sub.O]([PI]).

Now, we are ready to put forward a method to derive the nonredundant [disjunction]-rules from a formal decision context. The method can briefly be described as in Algorithm 1.

Note that the object-oriented concept lattice of (G,M, I) can be derived from the formal concept lattice of the complementary formal context of (G,M, I) [39]. Then, it is easy to prove that the time complexity of Algorithm 1 is

O(([absolute value of G] + [absolute value of M]) [absolute value of M][absolute value of [L.sub.O]] + ([absolute value of G] + [absolute value of N]) [absolute value of N][absolute value of [L.sub.F]]+ [absolute value of G][[absolute value of [L.sub.O]] .sup.2] [absolute value of [L.sub.F]] + [absolute value of G][absolute value of [L.sub.O]][[absolute value of [L.sub.F]].sup.2]),(7)

where [absolute value of [L.sub.O]] denotes the cardinality of the object-oriented concept lattice of (G,M, I) and [absolute value of [L.sub.F]] denotes that of the formal concept lattice of (G,N, J).

Example 9. Table 1 depicts a formal decision context [PI] = (G,M, I,N, J), where G = {1, 2, 3, 4, 5}, M = {a, b, c, d, e, f}, and N = {[d.sub.1], [d.sub.2], [d.sub.3]}. The object-oriented concept lattice of (G,M, I) is shown in Figure 1 and the formal concept lattice of (G,N, J) is shown in Figure 2.

According to Algorithm 1, we can derive the following nonredundant [disjunction]-rules from [PI]:

[r.sub.1]: if c, then [d.sub.1] and [d.sub.2];

[r.sub.2]: if e, then [d.sub.2] and [d.sub.3];

[r.sub.3]: if b, c, d, e, or f, then [d.sub.2].

It should be pointed out that [r.sub.3] can be divided into the following attribute implication rules:

[r.sub.3](1): if b, then [d.sub.2];

[r.sub.3](2): if c, then [d.sub.2];

[r.sub.3](3): if d, then [d.sub.2];

[r.sub.3](4): if e, then [d.sub.2];

[r.sub.3](5): if f, then [d.sub.2].

3.2. Rule Acquisition Based on Formal and Property-Oriented Concept Lattices. In this subsection, we continue to put forward the notion of a [disjunction]-[conjunction] mixed rule in formal decision contexts based on formal and property-oriented concept lattices.

Definition 10. Let [PI] = (G,M, I,N, J) be a formal decision context, let [[B.bar].sub.p](G,M, I) be the property-oriented concept lattice of (G,M, I), and let [[B.bar].sub.F](G,N, J) be the formal concept lattice of (G,N, J). For any (X, B) [member of] [[B.bar].sub.p](G,M, I) and (Y,C) [member of] [[B.bar].sub.F](G,N, J), if X [not equal to] 0, Y [not equal to] G, and X [subset or equal to] Y, then the expression B[[right arrow].sub.[disjunction][conjunction]]C is called a [disjunction]-[conjunction] mixed rule generated between the property-oriented concept (X, B) and the formal concept (Y,C). Here, B and C are called the premise and conclusion of the [disjunction]-[conjunction] mixed rule B [right arrow] C, respectively. The set of all of the [disjunction]-[conjunction] mixed rules generated between the property-oriented concepts in [[B.bar].sub.p](G,M, I) and the formal concepts in [[B.bar].sub.F](G,N, J) is denoted by [R.sub.P]([PI]).

Thus, for any B[[right arrow].sub.[disjunction][conjunction]]C [member of] [R.sub.P]([PI]), we conclude that each object having at least one conditional attribute in B and no conditional attribute in M B has all the decision attributes in C. More specifically, if B = {[b.sub.1], [b.sub.2], ..., [b.sub.s]}, M \ B = {[b.sub.s+1], [b.sub.s+2], ..., [b.sub.n]}, and C = {[c.sub.1], [c.sub.2], ..., [c.sub.t]}, then B[[right arrow].sub.[disjunction][conjunction]]C means the following: "if [b.sub.1][disjunction] [b.sub.2] [disjunction] ... [disjunction] [b.sub.s] and [logical not][b.sub.s+1] [conjunction][logical not][b.sub.s+2] [conjunction] ... [conjunction] [logical not][b.sub.n], then [c.sub.1][conjunction] [c.sub.2][conjunction] ... [conjunction] [c.sub.t]," where [disjunction], [conjunction], and [logical not] denote logical disjunction, conjunction, and negation operators, respectively.

It should be pointed out that the [disjunction]-[conjunction] mixed rules have something to do with both the attribute implication rules and the association rules. Concretely, a [disjunction]-[conjunction] mixed rule B[[right arrow].sub.[disjunction][conjunction]]C with B = {[b.sub.1], [b.sub.2], ..., [b.sub.s]}, M \ B = {[b.sub.s+1], [b.sub.s+2], ..., [b.sub.n]}, and C = {[c.sub.1], [c.sub.2], ..., [c.sub.t]} can be integrated by the following attribute implication rules (or association rules with their confidences being one):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

However, an attribute implication rule may not be a [disjunction]-[conjunction] mixed rule since its premise is generally not an expression of disjunction and conjunction of conditional attributes. Yet, an association rule may not be a [disjunction]-[conjunction] mixed rule since its confidence is often less than one.

Definition 11. Let [PI] = (G,M, I,N, J) be a formal decision context. For any [B.sub.1][[right arrow].sub.[disjunction][conjunction]][C.sub.1], [B.sub.2][[right arrow].sub.[disjunction][conjunction]][C.sub.2][member of] [R.sub.P]([PI]), if [B.sub.2][subset or equal to] [B.sub.1] and [C.sub.2][subset or equal to] [C.sub.1], one says that [B.sub.2][[right arrow].sub.[disjunction][conjunction]][C.sub.2] can be implied by [B.sub.1][[right arrow].sub.[disjunction][conjunction]][C.sub.1]. One denotes this implication relationship by [B.sub.1][[right arrow].sub.[disjunction][conjunction]][C.sub.1][??] [B.sub.2][[right arrow].sub.[disjunction][conjunction]][C.sub.2]. For any B[[right arrow].sub.[disjunction][conjunction]]C [member of] [R.sub.P]([PI]), if there exists [B.sub.0][[right arrow].sub.[disjunction][conjunction]][C.sub.0][member of] [R.sub.P]([PI]) \ {B[[right arrow].sub.[disjunction][conjunction]]C} such that [B.sub.0][[right arrow].sub.[disjunction][conjunction]][C.sub.0][??] B[[right arrow].sub.[disjunction][conjunction]]C, then B[[right arrow].sub.[disjunction][conjunction]]C is said to be redundant in [R.sub.P]([PI]); otherwise, B[[right arrow].sub.[disjunction][conjunction]]C is said to be nonredundant in [R.sub.P]([PI]). One denotes by [R.sup.*.sub.P]([PI]) the set of all the nonredundant [disjunction]-[conjunction] mixed rules in [R.sub.P]([PI]).

It can be known from Definition 11 that, for a given formal decision context, it is more appealing to extract the nonredundant [disjunction]-[conjunction] mixed rules since they can imply the remainder.

Let [PI] = (G,M, I,N, J) be a formal decision context. Denote

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

For any (X, Y) [member of] [[U.bar].sub.P](G,M, I) x [[U.bar].sub.F](G,N, J), one defines

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

ALGORITHM 2: Deriving the nonredundant [disjunction]-[conjunction]
mixed rules from a formal decision context.

Input: A formal decision context [PI] = (G,M, I,N, J).
Output: All the nonredundant [disjunction]-[conjunction] mixed rules
of [PI].
      (1) Initialize [OMEGA] = 0.
      (2) Construct the property-oriented concept lattice
      [[B.bar].sub.p](G,M, I) and the formal concept lattice
      [[B.bar].sub.F](G,N, J).
      (3) For every ((X, B), (Y, C)) [member of] [[U.bar].sub.P]
          (G,M, I) x [[U.bar].sub.F](G,N, J) with X [not equal to] 0
          and Y [not equal to] G, if [[alpha].sub.P](X, Y) = 1 and
          [[beta].sub.P](X, Y) = 1,
          then [OMEGA] [left arrow] [OMEGA][union]
          {B[[right arrow].sub.[disjunction][conjunction]]C}.
     (4) Output [OMEGA] and end the algorithm.


Theorem 12. For a formal decision context [PI] = (G,M, I, N, J), (X, B) [member of] [[B.bar].sub.p](G,M, I), (Y,C) [member of] [B.bar].sub.F](G,N, J), and B[[right arrow].sub.[disjunction][conjunction]]C [member of] [R.sub.P]([PI]). Then, B[[right arrow].sub.[disjunction][conjunction]]C is redundant in [R.sub.P]([PI]) if and only if [[alpha].sub.P](X, Y) = 0 or [[beta].sub.P](X, Y) = 0, or, equivalently, B[[right arrow].sub.[disjunction][conjunction]]C is nonredundant in [R.sub.P]([PI]) if and only if [[alpha].sub.P](X, Y) = 1 and [[beta].sub.P](X, Y) = 1.

Proof. It is similar to the proof of Theorem 8.

Now, we are ready to propose an approach to derive all the nonredundant [disjunction]-[conjunction] mixed rules from a formal decision context. The detailed steps are given in Algorithm 2.

Note that the property-oriented concept lattice of (G,M, I) can be derived from the formal concept lattice of the complementary formal context of (G,M, I) [39]. Then, it is easy to prove that the time complexity of Algorithm 2 is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (11)

where [absolute value of [L.sub.P]] denotes the cardinality of the property-oriented concept lattice of (G,M, I) and [absolute value of [L.sub.F]] denotes that of the formal concept lattice of (G,N, J).

Example 13. Let [PI] = (G,M, I,N, J) be the formal decision context in Table 1, where G = {1, 2, 3, 4, 5}, M = {a, b, c, d, e, f}, and N = {[d.sub.1], [d.sub.2], [d.sub.3]}. The property-oriented concept lattice of (G,M, I) is shown in Figure 3 and the formal concept lattice of (G,N, J) can be found in Figure 2.

According to Algorithm 2, we can derive the following nonredundant [disjunction]-[conjunction] mixed rule from [PI]:

r': if b, d, e, or f and [logical not]a and [logical not]c, then [d.sub.2] and [d.sub.3].

It should be pointed out that r' can be divided into the following attribute implication rules:

[r'.sub.1]: if b, [logical not]a, and [logical not]c, then [d.sub.2] and [d.sub.3]; [r'.sub.2]: if d, [logical not]a, and [logical not]c, then [d.sub.2] and [d.sub.3]; [r'.sub.3]: if e, [logical not]a, and [logical not]c, then [d.sub.2] and [d.sub.3]; [r'.sub.4]: if f, [logical not]a, and [logical not]c, then [d.sub.2] and [d.sub.3].

4. A Comparison of Rules in Terms of Inclusion and Inference Relationships

In Section 3, we have compared the [disjunction]-rules and [disjunction]-[conjunction] mixed rules with the attribute implication rules and association rules. In this section, we continue to make a comparison of [disjunction]-rules, [disjunction]-[conjunction] mixed rules, and decision rules in terms of inclusion and inference relationships. Before embarking on this issue, we introduce the notion of a decision rule in formal decision contexts.

Definition 14 (see [27]). Let [PI] = (G,M, I,N, J) be a formal decision context, let [[B.bar].sub.F](G,M, I) be the formal concept lattice of (G,M, J), and let [[B.bar].sub.F](G,N, J) be the formal concept lattice of (G,N, J). For any (X, B) [member of] [[B.bar].sub.F](G,M, I) and (Y,C) [member of] [[B.bar].sub.F](G,N, J), if X, B, Y, and C are all nonempty and X [subset or equal to] Y, then the expression B[[right arrow].sub.[conjunction]]C is called a decision rule generated between the formal concepts (X, B) and (Y,C). Here, B and C are called the premise and conclusion of the decision rule B[[right arrow].sub.[conjunction]]C, respectively. The set of all the decision rules generated between the formal concepts in [[B.bar].sub.F](G,M, I) and those in [[B.bar].sub.F](G,N, J) is denoted by [R.sub.F]([PI]).

Definition 15 (see [27]). Let [PI] = (G,M, I,N, J) be a formal decision context. For [B.sub.1][[right arrow].sub.[conjunction]][C.sub.1], [B.sub.2][[right arrow].sub.[conjunction]][C.sub.2][member of] [R.sub.F]([PI]), if [B.sub.1][subset or equal to] [B.sub.2] and [C.sub.2][subset or equal to] [C.sub.1], one says that [B.sub.2][[right arrow].sub.[conjunction]][C.sub.2] can be implied by [B.sub.1][[right arrow].sub.[conjunction]][C.sub.1]. One denotes this implication relationship by [B.sub.1][[right arrow].sub.[conjunction]][C.sub.1][??] [B.sub.2][[right arrow].sub.[conjunction]][C.sub.2]. For any B[[right arrow].sub.[conjunction]]C [member of] [R.sub.F]([PI]), if there exists [B.sub.0][[right arrow].sub.[conjunction]][C.sub.0][member of] [R.sub.F]([PI])\{B[[right arrow].sub.[conjunction]]C} such that [B.sub.0][[right arrow].sub.[conjunction]][C.sub.0][??] B[[right arrow].sub.[conjunction]]C, then B[[right arrow].sub.[conjunction]]C is said to be redundant in [R.sub.F]([PI]); otherwise, B[[right arrow].sub.[conjunction]]C is said to be nonredundant in [R.sub.F]([PI]). One denotes by [R.sup.*.sub.F]([PI]) the set of all the nonredundant decision rules in [R.sub.F]([PI]).

Thus, for any B[[right arrow].sub.[conjunction]]C [member of] [R.sub.F]([PI]), one concludes that each object having all the conditional attributes in B also has all the decision attributes in C. More specifically, if B = {[b.sub.1], [b.sub.2], ..., [b.sub.s]} and C = {[c.sub.1], [c.sub.2], ..., [c.sub.t]}, then B[[right arrow].sub.[conjunction]]C means the following: "if [b.sub.1][conjunction] [b.sub.2][conjunction] ... [conjunction] [b.sub.s], then [c.sub.1][conjunction] [c.sub.2][conjunction] ... [conjunction] [c.sub.t]," where [conjunction] denotes logical conjunction operator. Moreover, it is easy to observe that decision rules, [disjunction]-rules, and [disjunction]-[conjunction] mixed rules are different from each other in terms of their logical reasoning methodologies.

The following example is used to show that there does not exist inclusion relationship among decision rules, [disjunction]-rules, and [disjunction]-[conjunction] mixed rules. That is, we need to confirm three statements: (1) a decision rule may not be a [disjunction]-rule or [disjunction]-[conjunction] mixed rule; (2) a [disjunction]-rule may not be a decision rule or [disjunction]-[conjunction] mixed rule; (3) a [disjunction]-[conjunction]mixed rule may not be a decision rule or [disjunction]-rule.

Example 16. Let [PI] = (G,M, I,N, J) be the formal decision context in Table 1, where G = {1, 2, 3, 4, 5}, M = {a, b, c, d, e, f}, and N = {[d.sub.1], [d.sub.2], [d.sub.3]}. The formal concept lattice of (G,M, I) is shown in Figure 4 and that of (G,N, J) can be found in Figure 2.

According to the algorithm in [28] (interested readers can refer to [28] about how to efficiently derive all the nonredundant decision rules froma formal decision context), we can derive the following nonredundant decision rules from [PI]:

[r".sub.1] : if a, b, and f, then [d.sub.1] and [d.sub.2]; [r".sub.2] : if b, d, e, and f, then [d.sub.2] and [d.sub.3]; [r".sub.3] : if b and f, then [d.sub.2].

Combining these decision rules with the results obtained in Examples 9 and 13, we conclude that there does not exist inclusion relationship among decision rules, [disjunction]-rules, and [disjunction]-[conjunction] mixed rules.

Moreover, the following example is used to show that there does not exist inference relationship among decision rules, [disjunction]-rules, and [disjunction]-[conjunction] mixed rules, where the inference rule is described as follows [32]:

[OMEGA] :[B.sub.1][??] [C.sub.1], [B.sub.1][subset or equal to] [B.sub.2], [C.sub.2][subset or equal to] [C.sub.1]/[B.sub.2][??] [C.sub.2]. (12)

Note that the negation of a conditional attribute is treated as a new one and it is different from others.

Example 17. Let [PI] = (G,M, I,N, J) be the formal decision context in Table 1, where G = {1, 2, 3, 4, 5}, M = {a, b, c, d, e, f}, and N = {[d.sub.1], [d.sub.2], [d.sub.3]}. Then, according to the discussion in Examples 9, 13, and 16, we have the following:

(i) the decision rule [r".sub.1] cannot be implied by the [disjunction]-rules [r.sub.1], [r.sub.2], [r.sub.3](1), [r.sub.3](2), [r.sub.3](3), [r.sub.3](4), and [r.sub.3](5) based on the inference rule [OMEGA], neither can the [disjunction]-[conjunction] mixed rules [r'.sub.1], [r'.sub.2], [r'.sub.3], and [r'.sub.4];

(ii) each of the [disjunction]-rules [r.sub.1], [r.sub.2], [r.sub.3](1), [r.sub.3](2), [r.sub.3](3), [r.sub.3](4), and [r.sub.3](5) cannot be implied by the decision rules [r".sub.1], [r".sub.2], and [r".sub.3] based on the inference rule [OMEGA], neither can the [disjunction]-[conjunction] mixed rules [r'.sub.1], [r'.sub.2], [r'.sub.3], and [r'.sub.4];

(iii) each of the [disjunction]-[conjunction] mixed rules [r'.sub.1], [r'.sub.2], and [r'.sub.4] cannot be implied by the decision rules [r".sub.1], [r".sub.2], and [r".sub.3] based on the inference rule [OMEGA], neither can the [disjunction]-rules [r.sub.1], [r.sub.2], [r.sub.3](1), [r.sub.3](2), [r.sub.3](3), [r.sub.3](4), and [r.sub.3](5).

5. Experiments

Although, according to the discussion in Section 4, there does not exist inclusion or inference relationships among decision rules, [disjunction]-rules, and [disjunction]-[conjunction] mixed rules, it is still necessary to conduct some experiments to compare the proposed rule acquisition algorithms with the existing one in [27] in terms of the running efficiency.

In the experiments, eight real-life databases, including Bacteria [43], Zoo [44], Breast Tissue [44], Acute Inflammations [44], Servo [44], Wine [44], Balance Scale [44], and Car Evaluation [44], are analyzed to achieve the task of comparing the running efficiency. The detailed information about the eight chosen real-life databases is shown in Table 2.

For each of the chosen databases, we took the classification attribute(s) as the decision attribute(s) and other attributes as the conditional attributes. Then, the scaling approach [2] was used to transform the eight chosen databases into formal decision contexts. More specifically, discrete (but not Boolean) or continuous attributes were converted into Boolean ones. The detailed information about the conversion is listed in Table 3, where "/" means "taking no action" and "trisection" means "classifying the values of each continuous attribute, from small to large, into three pairwise disjoint intervals whose lengths are the same." We denote by data sets 1, 2, 3, 4, 5, 6, 7, and 8 the formal decision contexts which were obtained by applying the scaling approach (exactly, nominal scale and/or ordinal scale) to the eight chosen databases.

In the experiments, we still denote the proposed rule acquisition algorithms by Algorithms 1 and 2 (see Sections 3.1 and 3.2 for details) and the existing one in [27] by Algorithm 3. Then, Algorithms 1, 2, and 3 were applied to data sets 1, 2, 3, 4, 5, 6, 7, and 8. The corresponding running time is reported in Table 4 in which "Size" is the Cartesian product of the object set, conditional attribute set, and decision attribute set of the concerned formal decision context and [R.sup.*.sub.O]([PI]), [R.sup.*.sub.P]([PI]), and [R.sup.*.sub.F]([PI]) are the nonredundant [disjunction]-rules, [disjunction]-[conjunction] mixed rules, and decision rules, respectively. It can be seen from Table 4 that, by the running time, Algorithms 1, 2, and 3 are all acceptable, and which one being more efficient than another seems to be dependent on the given databases including density and scaling approach.

6. Conclusion and Future Work

Rule acquisition is one of the main purposes in the analysis of formal decision contexts. Although there have been several types of rules in formal decision contexts such as decision rules, decision implications, and granular rules, these rules are all [conjunction]-ones since they have the following form: "if conditions 1, 2, ..., and m hold, then decisions hold." In order to enrich the existing rule acquisition theory in formal decision contexts, we have proposed two new types of rules, called [disjunction]-rules and [disjunction]-[conjunction]mixed rules, based on formal, object-oriented, and property-oriented concept lattices. Moreover, a comparison of [disjunction]-rules, [disjunction]-[conjunction] mixed rules, and [conjunction]-rules has been made from the perspectives of inclusion and inference relationships. Finally, some numerical experiments have been conducted to compare the proposed rule acquisition algorithms with the existing one in terms of the running efficiency.

From the point of view of real applications, the results obtained in this paper need to be further extended to the cases of fuzzy formal decision contexts [45], incomplete formal decision contexts [29], and real formal decision contexts [30, 31] since in the real world the relationship between some objects and attributes of a formal decision context may be fuzzy-valued, interval-valued, or even real-valued. This issue will be discussed in our future work.

http://dx.doi.org/10.1155/2014/685362

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (nos. 61305057, 61202018, 61203283, and 11371014) and the Natural Science Research Foundation of Kunming University of Science and Technology (no. 14118760).

References

[1] R. Wille, "Restructuring lattice theory: an approach based on hierarchies of concepts," in Ordered Sets, pp. 445-470, Reidel, Dordrecht, The Netherlands, 1982.

[2] B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, New York, NY, USA, 1999.

[3] C. Carpineto and G. Romano, "Exploiting the potential of concept lattices for information retrieval with CREDO," Journal of Universal Computer Science, vol. 10, no. 8, pp. 985-1013, 2004.

[4] S. O. Kuznetsov, "Machine learning on the basis of formal concept analysis," Automation and Remote Control, vol. 62, no. 10, pp. 1543-1564, 2001.

[5] J. Poelmans, P. Elzinga, S. Viaene, and G. Dedene, "Formal concept analysis in knowledge discovery: a survey," in Proceedings of the 18th International Conference on Conceptual Structures, pp. 139-153, Kuching, Sarawak, Malaysia, 2010.

[6] W. Zhang, L. Wei, and J. Qi, "Attribute reduction theory and approach to concept lattice," Science in China F: Information Sciences, vol. 48, no. 6, pp. 713-726, 2005.

[7] M. Liu, M. W. Shao, W. X. Zhang, and C. Wu, "Reduction method for concept lattices based on rough set theory and its application," Computers & Mathematics with Applications, vol. 53, no. 9, pp. 1390-1410, 2007.

[8] T.-J. Li and W.-Z. Wu, "Attribute reduction in formal contexts: a covering rough set approach," Fundamenta Informaticae, vol. 111, no. 1, pp. 15-32, 2011.

[9] J. Mi, Y. Leung, and W. Wu, "Approaches to attribute reduction in concept lattices induced by axialities," Knowledge-Based Systems, vol. 23, no. 6, pp. 504-511, 2010.

[10] L. Wei and J. Qi, "Relation between concept lattice reduction and rough set reduction," Knowledge-Based Systems, vol. 23, no. 8, pp. 934-938, 2010.

[11] C. Aswani Kumar and S. Srinivas, "Concept lattice reduction using fuzzy K-Means clustering," Expert Systems with Applications, vol. 37, no. 3, pp. 2696-2704, 2010.

[12] L. D. Wang and X. D. Liu, "Concept analysis via rough set and AFS algebra," Information Sciences, vol. 178, no. 21, pp. 4125-4137, 2008.

[13] L. K. Guo, F. P. Huang, Q. G. Li, and G. Q. Zhang, "Power contexts and their concept lattices," Discrete Mathematics, vol. 311, no. 18-19, pp. 2049-2063, 2011.

[14] M. W. Shao and H. Z. Yang, "Two kinds of multi-level formal concepts and its application for sets approximations," International Journal of Machine Learning and Cybernetic, vol. 4, no. 6, pp. 621-630, 2013.

[15] D. Pei and J. Mi, "Attribute reduction in decision formal context based on homomorphism," International Journal of Machine Learning and Cybernetics, vol. 2, no. 4, pp. 289-293, 2011.

[16] G. Snelting, "Reengineering of Configurations Based on Mathematical Concept Analysis," ACM Transactions on Software Engineering and Methodology, vol. 5, no. 2, pp. 146-189, 1996.

[17] S. Sampath, S. Sprenkle, E. Gibson, L. Pollock, and A. S. Greenwald, "Applying concept analysis to user-session-based testing of web applications," IEEE Transactions on Software Engineering, vol. 33, no. 10, pp. 643-658, 2007.

[18] J. L. Guigues and V. Duquenne, "Famille minimales d'implications informatives resultant d'un tableau de donnees binaries," Mathematiques et Sciences Humaines, vol. 95, pp. 5-18, 1986.

[19] M. Luxenburger, "Implications partielles dans un contexte," Mathematiques Informatique et Sciences Humaines, vol. 113, pp. 35-55, 1991.

[20] N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, "Efficient mining of association rules using closed itemset lattices," Information Systems, vol. 24, no. 1, pp. 25-46, 1999.

[21] K. Qu and Y. Zhai, "Generating complete set of implications for formal contexts," Knowledge-Based Systems, vol. 21, no. 5, pp. 429-433, 2008.

[22] C. A. Kumar, "Fuzzy clustering-based formal concept analysis for association rules mining," Applied Artificial Intelligence, vol. 26, no. 3, pp. 274-301, 2012.

[23] M. J. Zaki, "Mining non-redundant association rules," Data Mining and Knowledge Discovery, vol. 9, no. 3, pp. 223-248, 2004.

[24] Y. Zhai, D. Li, and K. Qu, "Fuzzy decision implications," Knowledge-Based Systems, vol. 37, pp. 230-236, 2013.

[25] W. X. Zhang and G. F. Qiu, Un certain Decision Making Based on Rough Sets, Tsinghua University Press, Beijing, China, 2005.

[26] S. O. Kuznetsov, "Complexity of learning in concept lattices from positive and negative examples," Discrete Applied Mathematics, vol. 142, no. 1-3, pp. 111-125, 2004.

[27] J.Li, C.Mei, and Y.Lv, "Knowledge reduction in decision formal contexts," Knowledge-Based Systems, vol. 24, no. 5, pp. 709-715, 2011.

[28] J. Li, C. Mei, A. K. Cherukuri, and X. Zhang, "On rule acquisition in decision formal contexts," International Journal of Machine Learning and Cybernetics, vol. 4, no. 6, pp. 721-731, 2013.

[29] J. Li, C. Mei, and Y. Lv, "Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction," International Journal of Approximate Reasoning, vol. 54, no. 1, pp. 149-165, 2013.

[30] J. Li, C. Mei, and Y. Lv, "Knowledge reduction in real decision formal contexts," Information Sciences, vol. 189, pp. 191-207, 2012.

[31] H. Yang, L. Yee, and M. Shao, "Rule acquisition and attribute reduction in real decision formal contexts," Soft Computing, vol. 15, no. 6, pp. 1115-1128, 2011.

[32] K. S.Qu, Y. H. Zhai, J.Y. Liang, andM. Chen, "Study of decision implications based on formal concept analysis," International Journal of General Systems, vol. 36, no. 2, pp. 147-156, 2007.

[33] Y. H. Zhai, D. Y. Li, and K. S. Qu, "Decision implications: a logical point of view," International Journal of Machine Learning and Cybernetics, 2013.

[34] W. Z. Wu, Y. Leung, and J. S. Mi, "Granular computing and knowledge reduction in formal contexts," IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 10, pp. 1461-1474, 2009.

[35] Y. Y. Yao, "Concept lattices in rough set theory," in Proceedings of Annual Meeting of the North American Fuzzy Information Processing Society, pp. 796-801, Banff, Canada, June 2004.

[36] I. Duntsch and G. Gediga, "Approximation operators in qualitative data analysis," in Theory and Applications of Relational Structures as Knowledge Instruments, pp. 214-230, Springer, Berlin, Germany, 2003.

[37] Z. Pawlak, "Rough sets," International Journal of Computer and Information Sciences, vol. 11, no. 5, pp. 341-356, 1982.

[38] X. Wang and W. X. Zhang, "Relations of attribute reduction between object and property oriented concept lattices," Knowledge-Based Systems, vol. 21, no. 5, pp. 398-403, 2008.

[39] J. Medina, "Relating attribute reduction in formal, object-oriented and property-oriented concept lattices," Computers & Mathematics with Applications, vol. 64, no. 6, pp. 1992-2002, 2012.

[40] J. M. Ma, Y. Leung, and W. X. Zhang, "Attribute reductions in object-oriented concept lattices," International Journal of Machine Learning and Cybernetics, 2014.

[41] L. Wei, X. H. Zhang, and J. J. Qi, "Granular reduction of property-oriented concept lattices," in Proceedings of the 18th International Conference on Conceptual Structures, pp. 154-164, Sarawak, Malaysia, 2010.

[42] Y. Wen, M. Q. Xiao, Y. D. Wang, and D. P. Qu, "Diagnostic rule acquisition from incomplete information based on concept lattices," Journal of Vibration, Measurement and Diagnosis, vol. 33, no. 5, pp. 886-891, 2013 (Chinese).

[43] A. H. Fielding, Clustering and Classification Techniques for the Biosciences, Cambridge University Press, London, UK, 2007.

[44] A. Frank and A. A. Asuncion, "UCI machine learning repository," Irvine, Calif, USA, University of California, School of Information and Computer Science, 2010, http://archive.ics.uci.edu/ml.

[45] D. Pei, M. Z. Li, and J. S. Mi, "Attribute reduction in fuzzy decision formal contexts," in Proceedings of the International Conference on Machine Learning and Cybernetics (ICMLC '11), pp. 204-208, IEEE Press, Guilin, China, July 2011.

Yue Ren, (1) Jinhai Li, (1) Cherukuri Aswani Kumar, (2) andWenqi Liu (1)

(1) Faculty of Science, Kunming University of Science and Technology, Kunming, Yunnan 650500, China

(2) School of Information Technology and Engineering, VIT University, Vellore 632014, India

Correspondence should be addressed to Jinhai Li; jhlixjtu@163.com

Received 18 June 2014; Accepted 10 July 2014; Published 3 August 2014

Academic Editor: Yunqiang Yin

TABLE 1: A formal decision context n = (G,M,I,N,J).

u    a   b   c   d   e   f   [d.sub.1]   [d.sub.2]   [d.sub.3]

1    1   1   0   0   0   1       1           1           0
2    1   0   0   0   0   0       0           1           1
3    1   1   1   1   0   1       1           1           0
4    0   1   0   1   1   1       0           1           1
5    1   0   0   0   0   0       1           0           0

TABLE 2: The detailed information about the eight chosen databases
in the experiments.

Database              Instances   Classification attribute(s)

Bacteria                 17         1 (discrete, 6 values)
Zoo                      101        1 (discrete, 7 values)
Breast Tissue            106        1 (discrete, 6 values)
Acute Inflammations      120              2 (Boolean)
Servo                    167            1 (continuous)
Wine                     178        1 (discrete, 3 values)
Balance Scale            625        1 (discrete, 3 values)
Car Evaluation          1,728       1 (discrete, 4 values)

Database                           Other attributes

Bacteria                             16 (Boolean)
Zoo                   15 (Boolean), 1 (discrete but not Boolean)
Breast Tissue                       9 (continuous)
Acute Inflammations           5 (Boolean), 1 (continuous)
Servo                        4 (discrete but not Boolean)
Wine                                13 (continuous)
Balance Scale                4 (discrete but not Boolean)
Car Evaluation               6 (discrete but not Boolean)

TABLE 3: Converting the eight chosen databases into formal
decision contexts.

                                    Data preprocessing

Database              Conditional attributes   Decision attributes

Bacteria                        /                       /
Zoo                             /                       /
Breast Tissue               Trisection                  /
Acute Inflammations     Trisection for 1st              /
Servo                           /                  Trisection
Wine                        Trisection                  /
Balance Scale                   /                       /
Car Evaluation                  /                       /

                                          Scaling

Database              Conditional attributes   Decision attributes

Bacteria                        /                 Nominal scale
Zoo                   Nominal scale for 13th      Nominal scale
Breast Tissue             Ordinal scale           Nominal scale
Acute Inflammations   Ordinal scale for 1st             /
Servo                     Nominal scale           Ordinal scale
Wine                      Ordinal scale           Nominal scale
Balance Scale             Nominal scale           Nominal scale
Car Evaluation            Nominal scale           Nominal scale

TABLE 4: A contrast between the proposed rule acquisition algorithms
and the existing one in terms of the running time.

Database          Size        [R.sup.*.sub.O]   [R.sup.*.sub.P]
                                ([product])       ([product])

Data set 1    17 x 16 x 6            2                 4
Data set 2    101 x 21 x 7           3                 9
Data set 3    106 x 26 x 6           2                 0
Data set 4    120 x 8 x 2            4                 3
Data set 5    167 x 19 x 3          167               23
Data set 6    178 x 39 x 3           3                17
Data set 7    625 x 20 x 3           2                 5
Data set 8   1,728 x 21 x 4          1                 3

Database     [R.sup.*.sub.F]   Algorithm 1
               ([product])

Data set 1          6             0.14
Data set 2          9             41.57
Data set 3          5             0.13
Data set 4          5             0.06
Data set 5         27           11585.91
Data set 6         30            4865.34
Data set 7          3             48.88
Data set 8          1            430.41

Database     Running time(s)   Algorithm 3
               Algorithm 2        [27]

Data set 1        0.19            0.08
Data set 2        39.81           1.13
Data set 3        0.11            0.06
Data set 4        0.05            0.11
Data set 5      13198.84          1.66
Data set 6       5088.11          23.12
Data set 7        73.34          136.25
Data set 8       522.78          1981.81
COPYRIGHT 2014 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Ren, Yue; Li, Jinhai; Kumar, Cherukuri Aswani; Liu, Wenqi
Publication:The Scientific World Journal
Article Type:Report
Date:Jan 1, 2014
Words:8667
Previous Article:Synthesis of cobalt oxides thin films fractal structures by laser chemical vapor deposition.
Next Article:Analyzing patients' values by applying cluster analysis and LRFM model in a pediatric dental clinic in Taiwan.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters