Information Technology Journal

Year: 2008 | Volume: 7 | Issue: 1 | Page No.: 170-174
DOI: 10.3923/itj.2008.170.174

Attribute Reduction in Consistent Decision Formal Context

Jian-Jun Qi and Ling Wei

Abstract: The theory of concept lattices is an efficient tool for knowledge discovery. One focus of knowledge discovery is knowledge reduction. In present study, decision formal context is defined firstly; then, reduction theory of decision formal context is proposed; finally, some judgment theorems of consistent sets and reducts about decision formal contexts are examined.

Keywords: attribute reduction, Decision formal context and concept lattice

INTRODUCTION

The concept lattice, also called Galois lattice, was proposed by Wille (1982). A concept lattice is an ordered hierarchy that is defined by a binary relationship between objects and attributes in a data set. As an efficient tool for data analysis and knowledge processing, the concept lattice has been applied to many fields.

Most of the researches on concept lattices concentrate on such topics as: Construction and pruning algorithm of concept lattices (Godin, 1995; Kuznetsov and Obiedkov, 2002), relationship between concept lattices and rough sets (Belohlavek, 2000; Kent, 1996; Qi et al., 2005; Saquer and Deogun, 2001; Zhang et al., 2006), acquisition of rules (Ganter et al., 2005; Godin, 1995), reduction of concept lattices (Zhang et al., 2005), applications (Formica, 2006; Rajapakse and Denham, 2006; Sutton and Maletic, 2007; Tonella, 2003).

Knowledge reduction is one of important problems in knowledge discovery. The authors have proposed reduction theory of concept lattices. The attribute reduction in concept lattices is to find a minimal concept lattice so that it can avoid redundancy but at the same time maintain structure consistence. This study defines the decision formal context and proposes the reduction theory of decision formal contexts, finally, obtains some judgment theorems about consistent sets and reducts.

PRELIMINARIES

Definition 1 (Ganter and Wille, 1999): A formal context (U, A, I) consists of two sets U and A and a relation I between U and A. The elements of U are called the objects and the elements of A are called the attributes of the context. In order to express that an object x is in a relation I with an attribute a, we write xIa or (x, a) I and read it as the object x has the attribute a.

In present study, U and A are finite sets and we represent a formal context using a table with 0 and 1, the rows of which are the objects and the columns the attributes. The number 1 in row x and column a means (x, a) I and (x, a) I is denoted by 0.

Ganter and Wille (1999) defined a pair of operators for X U and B A as follows:

X* is the set of attributes common to the objects in X and B* is the set of objects which have all attributes in B. XU, {x}* is denoted by x*; a A, {a}* denoted by a*. If xU, x*, a*A and aA, a*, a*U, we say the formal context (U, A, I) is canonical. All the contexts we discussed in this study are canonical.

Definition 2 (Ganter and Wille, 1999): A formal concept of the context (U, A, I) is a pair (X, B) with X U, B A, X* = B and X = B*. We call X the extent and B the intent of the concept (X, B). L(U, A, I) denotes the set of all concepts of the context (U, A, I).

In order to make this study well down, we give some explanation of symbols. For a formal context (U, A, I), D A, let I_D = I (UxD), then (U, D, I_D) is also a context. For any X U, X* is represented by X* in (U, A, I) and in (U, D, I_D). It is evident that I_A = I, = X*, = D and X*.

For a context (U, A, I), X₁, X₂, X U, B₁, B₂, B A, the following propositions can be proved easily (Ganter and Wille, 1999).

Definition 3 (Ganter and Wille, 1999): If (X₁, B₁) and (X₂, B₂) are concepts of a context (U, A, I), (X₁, B₁) is called a subconcept of (X₂, B₂), provided that X₁ X₂ (which is equivalent to B₁ B₂). In this case, (X₂, B₂) is a superconcept of (X₁, B₁) and we write (X₁, B₁)≤(X₂, B₂). The relation ≤ is called the hierarchical order (or simply order) of the concepts. The set of all concepts of (U, A, I) ordered in this way is also denoted by L(U, A, I) and is called the concept lattice of the context.

Theorem 1 (Ganter and Wille, 1999): The concept lattice L(U, A, I) is a complete lattice in which infimun and supremum are given by

ATTRIBUTE REDUCTION IN CONSISTENT DECISION FORMAL CONTEXT

Zhang et al. (2005) have proposed reduction theory based on classical formal context. Here, we define the consistence between two concept lattices firstly, based on which, we define the consistent sets and reducts. Finally, we get some judgment theorems about consistent sets and reducts.

A decision formal context we proposed has two kinds of attributes: a group of condition attributes a_i A and a group of decision attributes t_j T. With the same object set U, they can form two concept lattices L(U, A, I_UxA) and L(U, T, I_UxT), respectively. So, there is necessary to study the relationship between these two lattices.

Basic definitions
Definition 4: Let L(U, A₁, I₁) and L(U, A₂, I₂) are two concept lattices. If for any (x, B) L(U, A₂, I₂), there exists (X`, B`) L(U, A₁, I₁) such that X` = X, then we say L(U, A<sub>1</sub>, I<sub>1</sub>) is finer than L(U, A<sub>2</sub>, I<sub>2</sub>), denoted by L(U, A<sub>1</sub>, I<sub>1</sub>) ≤ L(U, A<sub>2</sub>, I<sub>2</sub>). In this case, we say (X`, B`) is equivalent to (X, B), denoted by (X`, B`) ↔ (X, B). If (X`, B`) ↔ (X, B), then we can get equivalent relation between two intents B` ↔ B.

Definition 5: A five-tuple (U, A, I, T, J) is called a decision formal context, if (U, A, I) and (U, T, J) are all contexts and A is called condition attribute set, T decision attribute set. I is a binary relation between U and A, J is a binary relation between U and T.

Definition 6: Let (U, A, I, T, J) be a decision formal context. If L(U, A, I) ≤ L(U, T, J), then we say (U, A, I, T, J) is consistent.

The classical formal context can be taken as a special decision formal context when T = A, J = I.

Definition 7: Let (U, A, I, T, J) be a decision formal context. If there exists D A such that (U, D, I_D, T, J) is also consistent, then we say D is a consistent set of (U, A, I, T, J). Further, d D, if (U, D- {d}, I_D-{d}, T, J) is not consistent, then D is called a reduct of (U, A, I, T, J). The intersection of all reducts of (U, A, I, T, J) is called core of (U, A, I, T, J), elements in which are called core attributes.

PROPERTIES AND AN EXAMPLE

Theorem 2: There must exist reducts for any consistent decision formal context.

Proof: Let (U, A, I, T, J) be a decision formal context. If a A, (U, A-{a}, I_A-{a}, T, J) is not consistent, then A itself is a reduct. If there exists an attribute a A such that (U, A-{a}, I_A-{a}, T, J) is consistent, then we examine the set B₁ = A- {a}. If any b₁ B₁ makes inconsistent, then B₁ is a reduct; otherwise, we examine B₁ - {b₁}. Repeating the above process, we can find at least one reduct of (U, A, I, T, J) since A is a finite set. So, there must exist reducts for any consistent decision formal context.

Generally speaking, there are multiple reducts about consistent decision formal context. An example is given as follows:

Example 1: Table 1 is a decision formal context (U, A, I, T, J), in which, object set is U = {1, 2, 3, 4, 5}, condition attribute set is A = {a, b, c, d, e} and decision attribute set is T = {f, g, h}. We examine its consistence and reducts.

There are 8 concepts about (U, A, I), whose lattice L(U, A, I) is shown in Fig. 1; while, there are 5 concepts about (U, T, J), whose lattice L(U, T, J) is shown in Fig. 2.

It is easy to see that this decision formal context is consistent, because for each concept in L(U, T, J), there exists an equivalent concept in L(U, A, I) such that two extents are equal. There are two reducts about this consistent decision formal context: D₁ = {a, b, c} and D₂ = {a, b, d}. In which, a and b are two core attributes. The corresponding concept lattices of two reducts and are shown in Fig. 3 and 4

In this example, we can get the following equivalence relationships between concepts and intents by Definition 4.

Between L(U, A, I) and L(U, T, J):

Between and L(U, T, J):

Between and L(U, T, J):

Using above definitions and theorems, we can obtain the following corollaries easily. Here, we only prove Corollary 1.

Corollary 1: Core is a reduct if and only if there is only one reduct.

Proof: Necessity. Suppose core K is a reduct and there are at least two reducts D_i D_j. Then, the core is K D_i D_j D_i. Since D_i is a reduct, its proper subset, here means the core, is impossible to be a reduct. Which is contradiction to assumption, so, we know if core is a reduct, then reduct is exclusive.

Sufficiency. It is clear.

Corollary 2: a A is not a core attribute if and only if A-{a} is consistent.

Corollary 3: a A is a core attribute if and only if A-{a} is inconsistent.

JUDGMENT THEOREMS OF CONSISTENT SETS

Theorem 3 (Judgment theorem 1 of consistent sets): Let (U, A, I, T, J) be a consistent decision formal context, D A, D ≠. Then,

D is a consistent set. ↔F T, F, (F** D)* = F*.

Proof: Necessity. Since D is a consistent set, L(U, D, I_D) ≤ L(U, T, J) holds. F T, F ≠, there is , soC D, (F*, C) L(U, D, I_D), thus, C* = F*. While , therefore, (F** D)* = F*.

Sufficiency. (X, B) L(U, T, J), (X, X*) L(U, A, I) holds since L(U, A, I) ≤ L(U, T, J). According to the known condition, (X* D)* = (B** D)* = B* = X holds, so . Thus L(U, D, I_D) ≤ L(U, T, J). So D is a consistent set.

Corollary 4: Let (U, A, I, T, J) be a consistent decision formal context, D A, D ≠. If D is a consistent set, then D* T*.

Proof: If D is a consistent set, it can be obtained that (T** D)* = T* by Theorem 3. Further, we know T** D D, so D* (T** D)* = T* holds.

Theorem 4 (Judgment Theorem 2 of consistent sets): Let (U, A, I, T, J) be a consistent decision formal context, D A, D ≠. Then,

D is a consistent set.↔F T, F, C D, C, C* = F*

Proof: Necessity. It can be proved by Theorem 3.

Sufficiency. Since C* = F* ⇒ C C** = F** and C D, we can obtain C F** D, (F** D)* C* = F*. Further, we have (F** D)* F* D* F*. Thus (F** D)* = F*. So, D is a consistent set by Theorem 3.

Theorem 5 (Judgment Theorem 3 of consistent sets): Let (U, A, I, T, J) be a consistent decision formal context, D A, D ≠. Then,

D is a consistent set. ↔e T, (e** D)* = e*

Proof: Necessity. It can be proved by Theorem 4.

Sufficiency. F T, F ≠, put F = {e_k| k τ}. According to the known condition, e_k F T, C_k D, C_k ≠, C_k* = e_k*. Thus, . Put , then C D, C ≠, C* = F*. So, D is a consistent set by Theorem 4.

Theorem 6 (Judgment Theorem 4 of consistent sets): Let (U, A, I, T, J) be a consistent decision formal context, D A, D ≠. Then,

D is a consistent set. ↔e T, (e** D)* = e*

Proof: Necessity. It can be proved by Theorem 3.

Sufficiency. We know, e T, (e** D)* = e*. Put C = e** D, then C D, C ≠, C* = e*. So, D is a consistent set by Theorem 5.

These four judgment theorems are obtained by considering either the properties of subset F T or properties of element e T. The relations among them are as follows.

Theorem 4 is a generalized result. For a nonempty subset F of decision attribute set T, this theorem examines if there exists a subset C D such that C* = F*. If there exists such C, then D is a consistent set. While, Theorem 3 shows that if there exists such C, then it must be embodied by C = F** D. Theorem 5 and 6 are convenient to operate, since they study the elements in T, not subsets of T and further, Theorem 6 gives an embodied expression of such C: C = e** D. Therefore, Theorem 4 has generalized significance, while Theorem 6 is easy to operate.

Example 2: If we continue with Example 1, we select D = {a, b, c, d} and judge if it is a consistent set by Theorem 6.

It is easy to compute the following results.

That is to say, for each element in decision attribute set T, the conditions of Theorem 6 are all satisfied. So, D is a consistent set.

Corollary 5: Let (U, A, I, T, J) be a consistent decision formal context, its core is K, K A. Then, there is one and only one reduct. ↔e T, (e** K)* = e*.

Proof: It can be proved by Corollary 1 and Theorem 6.

By Definition 7 and Theorem 6, the following theorem can be obtained immediately.

Theorem 7 (Judgment Theorem of reducts): Let (U, A, I, T, J) be a consistent decision formal context, D A, D ≠. Then, D is a reduct. ↔ e T, (e** D)* = e* and d D, e T, (e** (D-{d}))* e*.

Theorem 8: Let (U, A, I, T, J) be a consistent decision formal context, a A,

a is a core element. ↔ e T, a e**, (e** - {a})* e*.

Proof: a is a core element.

↔A-{a} is not a consistent set.

Example 3: If we continue with Example 1, we examine each element in A using Theorem 8.

For a A, there exists h T satisfying Theorem 8:

For b A, there exists f T satisfying Theorem 8:

But for c A, d A and e A, there is no corresponding elements in T satisfying Theorem 8.

So, there are two core elements in Example 1. They are a and b, respectively.

CONCLUSIONS

The theory of concept lattices is a very useful tool for knowledge discovery and its research focus on many aspects. This paper introduced the definition of decision formal context, based on which, reduction theory of decision formal context is proposed. Finally, some judgment theorems of consistent sets and reducts about decision formal contexts are examined.

ACKNOWLEDGMENTS

The authors gratefully acknowledge the support of the National Natural Science Foundation of China (No. 60433010 and No. 60672173) and the Doctor Research Fund of Northwest University in China.

REFERENCES