# A Novel Approach of Rough Conditional Entropy-Based Attribute Selection for Incomplete Decision System

Authors: Tao Yan; Chongzhao Han
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Pawlak's classical rough set theory has been applied in analyzing ordinary information systems and decision systems. However, few studies have been carried out on the attribute selection problem in incomplete decision systems because of its complexity. It is therefore necessary to investigate effective algorithms to deal with this issue. In this paper, a new rough conditional entropy-based uncertainty measure is introduced to evaluate the significance of subsets of attributes in incomplete decision systems. Furthermore, some important properties of rough conditional entropy are derived and three attribute selection approaches are constructed, including an exhaustive search strategy approach, a heuristic search strategy approach, and a probabilistic search strategy approach for incomplete decision systems. Moreover, several experiments on real-life incomplete data sets are conducted to assess the efficiency of the proposed approaches. The final experimental results indicate that two of these approaches can give satisfying performances in the process of attribute selection in incomplete decision systems.


---

## Body

## 1. Introduction

Rough set theory, proposed by Pawlak [1–3], is an extension of set theory for the study of the intelligent systems characterized by uncertain, imprecise, incomplete, and inconsistent data. It has been proven to be an innovative and efficient mathematic tool, compared with other traditional data processing strategies like PCA, neural networks, SVM and so forth [4–7]. Unlike those methods, rough set theory allows knowledge discovering process to be conducted automatically by the data themselves without any dependence on the prior knowledge. By using the concepts of upper and lower approximations in rough set model to deal with the data, knowledge hidden in information systems could be discovered and expressed in the form of decision rules. Rough set methodology presents a novel paradigm to deal with uncertainty and then it has been successfully applied into feature selection [8], rule extraction [9, 10], uncertainty reasoning [11–13], decision evaluation [14], granular computing [15, 16], and so on.It has been known that Pawlak’s classical rough set model can only be used to tackle the problems of complete information systems [17]. Nevertheless, because of the error of data measuring, the impreciseness from the limitation of data acquisition manners and other probable factors, in the real database it is inevitable to meet the empty values, which stand for the inaccessible information in the database for the moment. In other words, the incomplete information systems with missing values often exist in practical knowledge acquisition. For now, two main approaches have been proposed to cope with incomplete information systems. One is indirect approach, which transforms an incomplete information system into a complete information system by eliminating objects with missing values or filling up missing values with processed data. The other is direct approach, which extends some basic notions in the classical rough set models [18, 19]. In the past decade, with respect to different requirements, various extensions of the rough set models have been proposed, such as variable precision rough set models [20, 21], rough set models based on tolerance relation [22, 23], fuzzy rough set models [24], and weighted attributes values rough set models [25].In many fields such as data mining, machine learning, and pattern recognition, data sets containing huge numbers of attributes can often be encountered. In such cases, feature selection, or attribute reduction as we know, is necessary. It is well known that irrelevant and redundant attributes in input attributes not only complicate the problem but also degrade solution accuracy [26, 27]. As a significant step among data preprocessing procedures, the main objective of attribute selection is to determine a minimal attribute subset, which is also called reduction, from a problem domain, which can retain a relatively high accuracy in replacing the original attributes.In comparison with the study of attribute selection from complete information systems, scant effort has been made to develop the tolerance relation-based methods of attribute selection for incomplete information systems [28–31]. Furthermore, there is a lack of the study of attribute selection of incomplete decision systems, compared with the above. As an effective method for attribute selection, rough set can preserve the meaning of the attributes. The essence of rough set approach for attribute selection is to find a subset of attributes, which can predict the decision concepts as well as the original attribute set. So far, there have been some new widespread approaches which are usually considered to develop the classical rough set theory as follows: tolerance-based rough set model [32], covering rough set model [33, 34], and dominance-based rough set model [35, 36]. However, they still have some inherent disadvantages and are not suitable for attribute selection of incomplete decision systems.As we know, finding the minimal reduct in an incomplete decision system is an NP-hard problem [37]. The general method of solving this kind of problems is adopting a heuristic search, which always depends on the measurements associated with the attributes [38]. However, little investigation has addressed the issue of measuring the uncertainty of knowledge of the tolerance relation-based rough set models in incomplete decision system until now. Hence, a further study on uncertainty measures applicable for evaluating the roughness and accuracy of a set in an incomplete decision system is of both theoretical and practical importance.The main aim of this paper is to construct an effective uncertainty measure evaluating the roughness and accuracy of knowledge to find a heuristic attribute selection algorithm of incomplete decision systems. The rest of this paper is organized as follows. In Section2, we briefly review some fundamental concepts concerning the main subject of this paper. Section 3 introduces the concept of entropy-based uncertainty measures and demonstrates several heuristic attribute selection algorithms of incomplete decision systems. Experimental comparisons and results are illustrated and analyzed in Section 4. Finally, some conclusions are presented in Section 5.


## 2. Preliminary

Classical rough set theory is originated by Qian et al. to deal with imprecise or vague concepts [39]. In the last decade, many generalized rough set models have been proposed and developed. In this section, we will only introduce some notions being used in this paper.Pawlak’s classical rough set is to be defined at the first place. An information system in rough set theory is a pair(U,A), where U={x1,…,xn} denotes a nonempty finite set of objects, called universe of discourse, and A={a1,…,am} denotes a finite condition attribute set. With every attribute a∈A we associate a set Va, of its values, called the domain of a. Then, a data pattern (a1(x),…,am(x)) can be defined by the object x and attributes from A. A decision table, abbreviated as DT, is a special system with the form (U,C∪{d}), where d∉C denotes decision attribute. Let Vd denote the domain of decision attribute mapping d(x). For the application of pattern classification, the attribute set is just the feature set and the universe of the discourse may represent a training pattern set or a sign set of training pattern sets.LetR be an equivalence relation on U, which means relation R satisfies reflexivity, symmetry, and transitivity. Relation R generates a partition U/R=IND(R)={[x]R∣x∈U} on U, where IND(R) denotes the equivalence classes, as well as indiscernible class, generated by the equivalence relation R. These are also called elementary sets of R in rough set theory. Let ∅ denote the empty sets. For any X⊆U, we can describe X by elementary sets of R and the two sets
(1)R-(X)={[x]R∣[x]R⊆X},R-(X)={[x]R∣[x]R∩X≠∅}
which are called the lower and upper approximations of X, respectively. Then, the concepts of positive region,
(2)POS(X)=R-(X),
negative region,
(3)NEG(X)=U-R-(X),
boundary region,
(4)BN(X)=R-(X)-R-(X)={[x]R∣[x]R∩X≠∅}-{[x]R∣[x]R⊆X},
and approximation measure,
(5)αR(X)=|R-(X)||R-(X)|,
are introduced, where X≠∅. The lower approximation, which is equivalent to the positive region, is the complete set of the objects in the universe that can be unambiguously classified as belonging to the target set X. In contrast, the upper approximation is the complete set of the objects that are possibly members of the target set X. In other words, these objects cannot be positively classified as belonging to the complement of the target set X, that is, X¯. Furthermore, the negative region contains the set of objects that can be definitely ruled out as the members of the target set X. Finally, the approximation measure αR(X) is intended to capture the degree of completeness of our knowledge about the target set X.In most cases, some precise values of particular attributes in an information system are not known, which means missing or known partially. Then such a system is called an incomplete information system and is still denoted without any confusion by a pair(U,A). As for an incomplete information system, a missing value a(x) may be represented by the set of all the possible values for the corresponding attribute; that is, a(x)=Va. Moreover, if a(x) is known partially, for instance, which implies that a(x) cannot be b,c∈Va, then the value of a(x) is specified as Va-{b,c}.In what follows, we only take the consideration of the incomplete information systems with missing values. In such a case, the special symbol “*” is to be used to indicate that the specific value of an attribute is missing. Let S=(U,AT) be an incomplete information system. Each subset of attributes A⊆AT determines a similarity relation
(6)SIM(A)={(x,y)∈U×U∣∀a∈A,a(x)=a(y)∪a(x)=*∪a(y)=*}.
The incomplete information system can be described by a set-valued information system with a(x)=Va when a(x)=*. In such a case, the similarity relation SIM(A) can be equivalently defined as
(7)SIM(A)={(x,y)∈U×U∣∀a∈A,a(x)∩a(y)≠∅}.
With the similarity relation SIM(A), two objects are considered to be possibly indiscernible in terms of the values of attributes A. Furthermore, a similarity relation satisfies reflexive and symmetric, but may not be transitive, so it is one of the tolerance relations.


## 3. Rough Entropy-Based Uncertainty Measures

In this section, the concept of rough entropy is introduced to measure the uncertainty or roughness of knowledge in incomplete information systems. And then, some rough entropy-based uncertainty measures are presented in incomplete information systems and incomplete decision systems. Some important properties concerning the uncertainty measures are derived, respectively, and the relationship among them is discussed as well.For a given information system, we need to assess its uncertainty or roughness for a target object or a target decision. A form of uncertainty measure, which is called rough entropy, has been mentioned in rough sets, rough relational databases, and information systems to calculate the roughness of knowledge. The following definition gives the description of the rough entropy in incomplete information systems.


### 3.1. Rough Entropy in IIS and IDS

LetIIS=(U,A) denote an incomplete information system with *∈V and P⊆A, and U/SIM(P)={SP(u1),SP(u2),…,SP(u|U|)}. According to Shannon’s theory of information entropy, the rough entropy of knowledge P on U is denoted by
(8)EN(P)=-1|U|∑i=1|U|log21|SP(ui)|,
where 1/|SP(ui)| represents the probability of an element within the tolerance class SP(ui) [40].LetIIS=(U,A) be an incomplete information system, with P,Q⊆A. If there exists a one-to-one onto function h:U/SIM(P)→U/SIM(Q) such that |h(SP(ui))|=|SQ(ui)|=|SP(ui)| for any ui∈U, then EN(P)=EN(Q). Therefore, the rough entropy of knowledge is invariant with respect to the different set of tolerance classes that are size isomorphic.LetIDS=(U,C∪{d}) denote an incomplete decision system with *∈VC. For any subset of condition attributes B⊆C, a tolerance relation T, which is in generalized form of the former similarity relation, can be defined as
(9)TB={(x,y)∈U×U∣∀a∈B,a(x)=a(y)∪a(x)=*∪a(y)=*}.
Then, the tolerance class of an object x with respect to an attribute set B is defined as
(10)TB(x)={y∈U∣(x,y)∈TB}.
Obviously, relation T is reflexive and symmetric, but may not be transitive.Definition 1.
LetIDS=(U,C∪{d}), *∈VC be an incomplete decision system, then the generalized decision ∂B=U→Vd is defined as follows:
(11)∂B(x)={u∣y∈TB(x)∩u=d(y)}.Definition 2.
LetIDS=(U,C∪{d}), *∈VC be an incomplete decision system. Let ∂B=U→Vd be the generalized decision function. If |∂B(x)|=1 for any x∈U, then the incomplete decision is consistent, which implies that it is deterministic and definite, where |·| denotes the number of the elements of the set.
In what follows, we give an example, which was firstly shown by Kryszkiewicz [31], to demonstrate how tolerance relationship works in a specific incomplete decision system. Given an incomplete decision system shown in Table 1, where U={u1,u2,u3,u4,u5,u6}, C={Price,Mileage,Size,Max-speed} = {P,M,S,X} and d=Acceleration, and U/IND(d)={SGood,SPoor,SExcel}. By definition, we have
(12)TC(u1)={u1},TC(u1∩dGood)={u1},TC(u1∩dPoor)=TC(u1∩dExcellent)=∅,TC(u2)={u2,u6},TC(u2∩dGood)={u2,u6},TC(u2∩dPoor)=TC(u2∩dExcellent)=∅,TC(u3)={u3},TC(u3∩dPoor)={u3},TC(u3∩dGood)=TC(u3∩dExcellent)=∅,TC(u4)={u4,u5},TC(u4∩dGood)={u4},TC(u4∩dPoor)=∅,TC(u4∩dExcellent)={u5},TC(u5)={u4,u5,u6},TC(u5∩dGood)={u4,u6},TC(u5∩dPoor)=∅,TC(u5∩dExcellent)={u5},TC(u6)={u2,u5,u6},TC(u6∩dGood)={u2,u6},TC(u6∩dPoor)=∅,TC(u6∩dExcellent)={u5},UIND(d)={{u1,u2,u4,u6},{u3},{u5}}.
Consequently, we get |∂C(u1)|=|∂C(u2)|=|∂C(u3)|=|∂C(u4)|=|∂C(u5)|=|∂C(u6)|=1, which proves that the incomplete decision system is consistent.Table 1
An example of incomplete decision system.
Car
Price
Mileage
Size
Max-speed
Decision
1
High
High
Full
Low
Good
2
Low
*
Full
Low
Good
3
*
*
Compact
High
Poor
4
High
*
Full
High
Good
5
*
*
Full
High
Excellent
6
Low
High
Full
*
GoodDefinition 3.
LetIDS=(U,C∪{d}) be an incomplete decision system. Let B⊆C, then the attribute set B is a relative reduct of IDS, if and only if(1)
∂B(x)=∂A(x) for all x∈U,(2)
b∈B, ∂B-{b}≠∂Care satisfied simultaneously.


### 3.2. Conditional Entropy Measure for Incomplete Decision System

The rough entropy of knowledge inIIS and IDS has been discussed above. In this subsection, we will introduce a new form of conditional entropy and the mutual information based on the tolerance relationship to measure the uncertainty of knowledge in incomplete decision systems. And then, some important properties will be deduced.Definition 4.
Given a consistent incomplete decision system,IDS=(U,C∪{d}) and B⊆C. Let U/TB={TB(x1),TB(x2),…,TB(x|U|)}, U/d={d1,d2,…,dm}. The conditional entropy of B to d is defined as follows:
(13)EN(d∣B)=-∑i=1|U|p(TB(ui))×∑j=1|U/d|p(dj∣TB(ui))log2p(dj∣TB(ui)),
where
(14)p(TB(ui))=|TB(ui)||U|,i=1,2,…,|U|,p(dj∣TB(ui))=p(TB(ui),dj)p(TB(ui))=|TB(xi)∩dj||TB(xi)|,p(dj∣TB(ui))i=1,2,…,|U|,j=1,2,…,m.
Hence, we have
(15)EN(d∣B)=-∑i=1|U|p(TB(xi))∑j=1|U/d|p(dj∣TB(xi))log2p(dj∣TB(xi))=-∑i=1|U||TB(xi)||U|∑j=1|U/d||TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=∑i=1|U|∑j=1|U/d||TB(xi)∩dj||U|log2|TB(xi)||TB(xi)∩dj|.
It is obvious that EN(d∣B)=0 when TB(xi)∩dj=∅.Proposition 5.
LetIDS=(U,C∪{d}) be a consistent incomplete decision system. Then, we have EN(d∣C)=0.Proof.
SinceIDS is consistent, we have ∂C(xi)=1, xi∈U. This means that TC(xi)⊆dj, dj∈U/d, xi∈U.
Hence, we have(16)TC(xi)∩dr=∅,∀dr∈Ud,dr≠dj.
Consequently, we know that
(17)EN(d∣C)=-∑i=1|U|p(TC(xi))∑j=1|U/d|p(dj∣TC(xi))log2p(dj∣TC(xi))=-∑i=1|U||TC(xi)||U|∑j=1|U/d||TC(xi)∩dj||TC(xi)|log2|TC(xi)∩dj||TC(xi)|=-∑i=1|U||TC(xi)||U|(0+0+⋯+1log⁡1+0+⋯+0)=0.Proposition 6.
LetIDS=(U,C∪{d}) be a consistent incomplete decision system; B⊆C is a relative reduct of C relative to decision attribute d, if and only if(1)
EN(d∣C)=EN(d∣B);(2)
B′⊂B,EN(d∣B′)≠EN(d∣B).Proof.
(1) We first prove that ifEN(d∣C)=EN(d∣B), ∀B′⊂B, EN(d∣B′)≠EN(d∣B) then B⊆C is a relative reduct.
By Proposition5, we know that EN(d∣C)=0. Then EN(d∣B)=EN(d∣C)=0.
Since(18)0≤|TB(xi)||U|≤1,0≤|TB(xi)∩dj||TB(xi)|≤1,
we have
(19)|TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|≤0.
At the same time, we know thatEN(d∣B)=0 if and only if
(20)|TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=0,∀xi,dj.
This implies that there exists only one dj∈U/d such that TB(xi)⊆dj and TB(xi)∩dr=∅, ∀dr∈U/d, dr≠dj. This means that |∂B(xi)|=1, ∀xi∈U. Hence, we get ∂B=∂C.
From∀B′⊂B, EN(d∣B′)≠EN(d∣B), we have EN(d∣B′)≠0. It follows that there at least exist xi, dj, and dk such that TB′(xi)∩dj≠∅ and TB′(xi)∩dk≠∅. This means that |∂B(xi)|≥2. Hence, ∂B′≠∂B.
(2) We then prove that ifB⊆C is a relative reduct, then EN(d∣C)=EN(d∣B), ∀B′⊂B, EN(d∣B′)≠E(d∣B) hold.
SinceB⊆C is a relative reduct, we get ∂B=∂C; that is, |∂B(xi)|=|∂C(xi)|=1, ∀xi∈U. It follows that, ∀xi∈U, there exists dj∈U/d such that TB(xi)⊆dj and TB(xi)∩dr=∅, ∀dr∈U/d, dr≠dj.
It follows that(21)|TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=|TB(xi)||TB(xi)|log2|TB(xi)||TB(xi)|=1log⁡1=0,∀xi,dj.
Therefore, this means that
(22)∑j=1|U/d||TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=0,∀xi.
Consequently, we know
(23)EN(d∣B)=-∑i=1|U|p(TB(xi))∑j=1|U/d|p(dj∣TB(xi))log2p(dj∣TB(xi))=-∑i=1|U||TB(xi)||U|∑j=1|U/d||TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=-∑i=1|U||TB(xi)||U|·0=0.
For ∀B′⊂B, we know that ∂B′≠∂B; that is, there at least exists xi∈U such that ∂B′(xi)≠∂B(xi). It follows that |∂B′(xi)|>|∂B(xi)|=1. Thus, there at least exist dj∈U/d and dr∈U/d, dr≠dj such that
(24)TB′(xi)∩dj≠Ø,TB′(xi)∩dr≠Ø.
Then, we get EN(d∣B′)≠EN(d∣B).
From parts (1) and (2), we finally prove that the theorem holds.


## 3.1. Rough Entropy in IIS and IDS

LetIIS=(U,A) denote an incomplete information system with *∈V and P⊆A, and U/SIM(P)={SP(u1),SP(u2),…,SP(u|U|)}. According to Shannon’s theory of information entropy, the rough entropy of knowledge P on U is denoted by
(8)EN(P)=-1|U|∑i=1|U|log21|SP(ui)|,
where 1/|SP(ui)| represents the probability of an element within the tolerance class SP(ui) [40].LetIIS=(U,A) be an incomplete information system, with P,Q⊆A. If there exists a one-to-one onto function h:U/SIM(P)→U/SIM(Q) such that |h(SP(ui))|=|SQ(ui)|=|SP(ui)| for any ui∈U, then EN(P)=EN(Q). Therefore, the rough entropy of knowledge is invariant with respect to the different set of tolerance classes that are size isomorphic.LetIDS=(U,C∪{d}) denote an incomplete decision system with *∈VC. For any subset of condition attributes B⊆C, a tolerance relation T, which is in generalized form of the former similarity relation, can be defined as
(9)TB={(x,y)∈U×U∣∀a∈B,a(x)=a(y)∪a(x)=*∪a(y)=*}.
Then, the tolerance class of an object x with respect to an attribute set B is defined as
(10)TB(x)={y∈U∣(x,y)∈TB}.
Obviously, relation T is reflexive and symmetric, but may not be transitive.Definition 1.
LetIDS=(U,C∪{d}), *∈VC be an incomplete decision system, then the generalized decision ∂B=U→Vd is defined as follows:
(11)∂B(x)={u∣y∈TB(x)∩u=d(y)}.Definition 2.
LetIDS=(U,C∪{d}), *∈VC be an incomplete decision system. Let ∂B=U→Vd be the generalized decision function. If |∂B(x)|=1 for any x∈U, then the incomplete decision is consistent, which implies that it is deterministic and definite, where |·| denotes the number of the elements of the set.
In what follows, we give an example, which was firstly shown by Kryszkiewicz [31], to demonstrate how tolerance relationship works in a specific incomplete decision system. Given an incomplete decision system shown in Table 1, where U={u1,u2,u3,u4,u5,u6}, C={Price,Mileage,Size,Max-speed} = {P,M,S,X} and d=Acceleration, and U/IND(d)={SGood,SPoor,SExcel}. By definition, we have
(12)TC(u1)={u1},TC(u1∩dGood)={u1},TC(u1∩dPoor)=TC(u1∩dExcellent)=∅,TC(u2)={u2,u6},TC(u2∩dGood)={u2,u6},TC(u2∩dPoor)=TC(u2∩dExcellent)=∅,TC(u3)={u3},TC(u3∩dPoor)={u3},TC(u3∩dGood)=TC(u3∩dExcellent)=∅,TC(u4)={u4,u5},TC(u4∩dGood)={u4},TC(u4∩dPoor)=∅,TC(u4∩dExcellent)={u5},TC(u5)={u4,u5,u6},TC(u5∩dGood)={u4,u6},TC(u5∩dPoor)=∅,TC(u5∩dExcellent)={u5},TC(u6)={u2,u5,u6},TC(u6∩dGood)={u2,u6},TC(u6∩dPoor)=∅,TC(u6∩dExcellent)={u5},UIND(d)={{u1,u2,u4,u6},{u3},{u5}}.
Consequently, we get |∂C(u1)|=|∂C(u2)|=|∂C(u3)|=|∂C(u4)|=|∂C(u5)|=|∂C(u6)|=1, which proves that the incomplete decision system is consistent.Table 1
An example of incomplete decision system.
Car
Price
Mileage
Size
Max-speed
Decision
1
High
High
Full
Low
Good
2
Low
*
Full
Low
Good
3
*
*
Compact
High
Poor
4
High
*
Full
High
Good
5
*
*
Full
High
Excellent
6
Low
High
Full
*
GoodDefinition 3.
LetIDS=(U,C∪{d}) be an incomplete decision system. Let B⊆C, then the attribute set B is a relative reduct of IDS, if and only if(1)
∂B(x)=∂A(x) for all x∈U,(2)
b∈B, ∂B-{b}≠∂Care satisfied simultaneously.


## 3.2. Conditional Entropy Measure for Incomplete Decision System

The rough entropy of knowledge inIIS and IDS has been discussed above. In this subsection, we will introduce a new form of conditional entropy and the mutual information based on the tolerance relationship to measure the uncertainty of knowledge in incomplete decision systems. And then, some important properties will be deduced.Definition 4.
Given a consistent incomplete decision system,IDS=(U,C∪{d}) and B⊆C. Let U/TB={TB(x1),TB(x2),…,TB(x|U|)}, U/d={d1,d2,…,dm}. The conditional entropy of B to d is defined as follows:
(13)EN(d∣B)=-∑i=1|U|p(TB(ui))×∑j=1|U/d|p(dj∣TB(ui))log2p(dj∣TB(ui)),
where
(14)p(TB(ui))=|TB(ui)||U|,i=1,2,…,|U|,p(dj∣TB(ui))=p(TB(ui),dj)p(TB(ui))=|TB(xi)∩dj||TB(xi)|,p(dj∣TB(ui))i=1,2,…,|U|,j=1,2,…,m.
Hence, we have
(15)EN(d∣B)=-∑i=1|U|p(TB(xi))∑j=1|U/d|p(dj∣TB(xi))log2p(dj∣TB(xi))=-∑i=1|U||TB(xi)||U|∑j=1|U/d||TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=∑i=1|U|∑j=1|U/d||TB(xi)∩dj||U|log2|TB(xi)||TB(xi)∩dj|.
It is obvious that EN(d∣B)=0 when TB(xi)∩dj=∅.Proposition 5.
LetIDS=(U,C∪{d}) be a consistent incomplete decision system. Then, we have EN(d∣C)=0.Proof.
SinceIDS is consistent, we have ∂C(xi)=1, xi∈U. This means that TC(xi)⊆dj, dj∈U/d, xi∈U.
Hence, we have(16)TC(xi)∩dr=∅,∀dr∈Ud,dr≠dj.
Consequently, we know that
(17)EN(d∣C)=-∑i=1|U|p(TC(xi))∑j=1|U/d|p(dj∣TC(xi))log2p(dj∣TC(xi))=-∑i=1|U||TC(xi)||U|∑j=1|U/d||TC(xi)∩dj||TC(xi)|log2|TC(xi)∩dj||TC(xi)|=-∑i=1|U||TC(xi)||U|(0+0+⋯+1log⁡1+0+⋯+0)=0.Proposition 6.
LetIDS=(U,C∪{d}) be a consistent incomplete decision system; B⊆C is a relative reduct of C relative to decision attribute d, if and only if(1)
EN(d∣C)=EN(d∣B);(2)
B′⊂B,EN(d∣B′)≠EN(d∣B).Proof.
(1) We first prove that ifEN(d∣C)=EN(d∣B), ∀B′⊂B, EN(d∣B′)≠EN(d∣B) then B⊆C is a relative reduct.
By Proposition5, we know that EN(d∣C)=0. Then EN(d∣B)=EN(d∣C)=0.
Since(18)0≤|TB(xi)||U|≤1,0≤|TB(xi)∩dj||TB(xi)|≤1,
we have
(19)|TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|≤0.
At the same time, we know thatEN(d∣B)=0 if and only if
(20)|TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=0,∀xi,dj.
This implies that there exists only one dj∈U/d such that TB(xi)⊆dj and TB(xi)∩dr=∅, ∀dr∈U/d, dr≠dj. This means that |∂B(xi)|=1, ∀xi∈U. Hence, we get ∂B=∂C.
From∀B′⊂B, EN(d∣B′)≠EN(d∣B), we have EN(d∣B′)≠0. It follows that there at least exist xi, dj, and dk such that TB′(xi)∩dj≠∅ and TB′(xi)∩dk≠∅. This means that |∂B(xi)|≥2. Hence, ∂B′≠∂B.
(2) We then prove that ifB⊆C is a relative reduct, then EN(d∣C)=EN(d∣B), ∀B′⊂B, EN(d∣B′)≠E(d∣B) hold.
SinceB⊆C is a relative reduct, we get ∂B=∂C; that is, |∂B(xi)|=|∂C(xi)|=1, ∀xi∈U. It follows that, ∀xi∈U, there exists dj∈U/d such that TB(xi)⊆dj and TB(xi)∩dr=∅, ∀dr∈U/d, dr≠dj.
It follows that(21)|TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=|TB(xi)||TB(xi)|log2|TB(xi)||TB(xi)|=1log⁡1=0,∀xi,dj.
Therefore, this means that
(22)∑j=1|U/d||TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=0,∀xi.
Consequently, we know
(23)EN(d∣B)=-∑i=1|U|p(TB(xi))∑j=1|U/d|p(dj∣TB(xi))log2p(dj∣TB(xi))=-∑i=1|U||TB(xi)||U|∑j=1|U/d||TB(xi)∩dj||TB(xi)|log2|TB(xi)∩dj||TB(xi)|=-∑i=1|U||TB(xi)||U|·0=0.
For ∀B′⊂B, we know that ∂B′≠∂B; that is, there at least exists xi∈U such that ∂B′(xi)≠∂B(xi). It follows that |∂B′(xi)|>|∂B(xi)|=1. Thus, there at least exist dj∈U/d and dr∈U/d, dr≠dj such that
(24)TB′(xi)∩dj≠Ø,TB′(xi)∩dr≠Ø.
Then, we get EN(d∣B′)≠EN(d∣B).
From parts (1) and (2), we finally prove that the theorem holds.


## 4. Attribute Selection Approaches Based on Rough Conditional Entropy for IDS

Two important steps are contained in the procedure of attribute selection: evaluation of a candidate attribute subset and search strategy through the attribute space, which are all for finding the most significant attributes, that is, relative reduct. Therefore, we use the conditional entropy discussed previously in Section3 to evaluate the attribute subset and a measurement is defined as follows.Definition 7.
Given a consistent decision systemIDS=(U,C∪{d}), let B⊆C and a∈C-B. Then, the significance of attribute relative to B is defined as
(25)SIG(a,B,d)=EN(d∣B)-EN(d∣B∪{a}).
This definition describes the increment of discernibility power relative to the decision caused by involving attribute a. It implies that the larger the difference between EN(d∣B) and EN(d∣B∪{a}) is, the more significant the specific condition attribute a is for condition attribute subset B. Thus, it can be used as a new measurement for attribute selection in incomplete decision system. According to this new measurement, three attribute selection approaches based on different search strategies are proposed, respectively, in the following subsections.


### 4.1. Breadth-First: Exhaustive Search

Breadth-first is one of earliest feature selection or attribute selection algorithms in machine learning area. It begins with an empty attribute set and carries out search process with breadth-first strategy until it finds a minimal subset that satisfies stop criterion. Since the Breadth-first algorithm adopts an exhaustive search strategy, it can guarantee an optimal solution [41]. Then, we present the Breadth-first approach for attribute selection of incomplete decision system as shown in Algorithm 1.Algorithm 1:Breadth-first.
Input: An incomplete decision system(U,C∪{d}).
Output: An attribute selection resultR.
(1) For everysize=0 to |C|
(2) For all subset SelectAttr with|SelectAttr|=size
(3) IfEN(d∣SelectAttr)≠EN(d∣C), go to Step  2, otherwise return R=SelectAttr
(4) End
(5) EndExample 8.
Given the incomplete decision system shown in Table2, we have
(26)C={P,M,S,X},Ud={{u1,u2,u4,u6},{u3},{u5}},TC(u1)=TC(u2)=TC(u6)={u1,u2,u6},TC(u3)={u3},TC(u4)={u4},TC(u5)={u5}.
According to the previous definition of rough conditional entropy, we can simply get
(27)EN(d∣C)=-[3*36*(33log233)+16*(1log21)+16*(1log21)+16*(1log21)]=0.
Consequently, we can deduce other conditional entropy values with respect to the different condition attributes in the same way as follows:
(28)TP(u1)=TP(u4)={u1,u2,u3,u4,u6},TP(u2)=TP(u3)=TP(u6)={u1,u2,u3,u4,u5,u6},TP(u5)={u2,u3,u5,u6},EN(d∣{P})=-[2*56*(45log245+15log215)+3*66*(46log246+16log216+16log216)+46*(24log224+14log214+14log214)]=5.9581,TM(u1)=TM(u2)=TM(u3)=TM(u4)=TM(u5)=TM(u6)={u1,u2,u3,u4,u5,u6},EN(d∣{M})=-[6*66*(46log246+16log216+16log216)]=7.5098,TS(u1)=TS(u2)=TS(u4)=TS(u5)=TS(u6)={u1,u2,u4,u5,u6},TS(u3)={u3},EN(d∣{S})=-[5*56*(45log245+15log215)+16*(1log21)]=3.0080,TX(u1)=TX(u2)=TX(u6)={u1,u2,u6},TX(u3)=TX(u4)=TX(u5)={u3,u4,u5},EN(d∣{X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774.
Then, we calculate the rough conditional entropy values with respect to different combinations of two condition attributes:
(29)TP,M(u1)=TP,M(u4)={u1,u2,u3,u4,u6},TP,M(u2)=TP,M(u3)=TP,M(u6)={u1,u2,u3,u4,u5,u6},TP,M(u5)={u2,u3,u5,u6},EN(d∣{P,M})=-[2*56*(45log245+15log215)+3*66*(46log246+16log216+16log216)+46*(24log224+14log214+14log214)]=5.9581,TP,S(u1)=TP,S(u4)={u1,u2,u4,u6},TP,S(u2)=TP,S(u6)={u1,u2,u4,u5,u6},TP,S(u3)={u3},TP,S(u5)={u2,u5,u6},EN(d∣{P,S})=-[2*46*(44log244)+2*56*(45log245+15log215)+16*(1log21)+36*(23log223+13log213)]=1.6624,TP,X(u1)=TP,X(u2)=TP,X(u6)={u1,u2,u6},TP,X(u3)={u3,u4,u5},TP,X(u4)={u3,u4},TP,X(u5)={u3,u5},EN(d∣{P,X})=-[3*36*(33log233)+36*(13log213+13log213+13log213)+26*(12log212+12log212)+26*(12log212+12log212)]=1.4591,TM,S(u1)=TM,S(u2)=TM,S(u4)=TM,S(u5)=TM,S(u6)={u1,u2,u4,u5,u6},TM,S(u3)={u3},EN(d∣{M,S})=-[5*56*(45log245+15log215)+16*(1log21)]=3.0080,TM,X(u1)=TM,X(u2)=TM,X(u6)={u1,u2,u6},TM,X(u3)=TM,X(u4)=TM,X(u5)={u3,u4,u5},EN(d∣{M,X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774,TS,X(u1)=TS,X(u2)=TS,X(u6)={u1,u2,u6},TS,X(u3)={u3},TS,X(u4)=TS,X(u5)={u4,u5},EN(d∣{S,X})=-[3*36*(33log233)+16*(1log21)+2*26*(12log212+12log212)]=0.6667.
Finally, we calculate the rough conditional entropy values with respect to different combinations of three condition attributes:
(30)TP,M,S(u1)=TP,M,S(u4)={u1,u2,u4,u6},TP,M,S(u2)=TP,M,S(u6)={u1,u2,u4,u5,u6},TP,M,S(u3)={u3},TP,M,S(u5)={u2,u5,u6},EN(d∣{P,M,S})=-[2*46*(44log244)+2*56*(45log245+15log215)+16*(1log21)+36*(23log223+13log213)]=1.6624,TP,M,X(u1)=TP,M,X(u2)=TP,M,X(u6)={u1,u2,u6},TP,M,X(u3)={u3,u4,u5},TP,M,X(u4)={u3,u4},TP,M,X(u5)={u3,u5},EN(d∣{P,M,X})=-[3*36*(33log233)+36*(13log213+13log213+13log213)+26*(12log212+12log212)+26*(12log212+12log212)]=1.4591,TP,S,X(u1)=TP,S,X(u2)=TP,S,X(u6)={u1,u2,u6},TP,S,X(u3)={u3},TP,S,X(u4)={u4},TP,S,X(u5)={u5},EN(d∣{P,S,X})=-[3*36*(33log233)+16*(1log21)+16*(1log21)+16*(1log21)]=0.
Since EN(d∣{P,S,X})=EN(d∣C)=0, we obtain the desired attribute set of selected {P,S,X}, which is a relative reduct of the original condition attribute set C. It also means that the search procedure ends at this step and it is not necessary to calculate the entropy value of the last combination of three attributes {M,S,X} anymore. The detailed search procedure is illustrated in Figure 1.Table 2
Another example of incomplete decision system.
Car
Price
Mileage
Size
Max-speed
Decision
1
High
High
Full
Low
Good
2
*
*
Full
Low
Good
3
*
*
Compact
High
Poor
4
High
*
Full
High
Good
5
Low
*
Full
High
Excellent
6
*
High
Full
Low
GoodFigure 1
The flow chart of the Breadth-first algorithm.


### 4.2. Depth-First: Heuristic Search

We can also use heuristic search or greed search to find attribute reduction. At the very beginning, the candidate attribute subset is empty. Then, a new attribute which can maximize the significance measure is added to the selected attribute subset each time, until the stop criterion is satisfied. Depth-first algorithm is fast, close to optimal, and deterministic [42]. Here, we present the Depth-first approach for incomplete decision system, as shown in Algorithm 2.Algorithm 2:Depth-first.
Input: An incomplete decision system(U,C∪{d}).
Output: A selected attribute subsetR.
(1) InitializeSelectAttr=⌀, unSelectAttr=C
(2)For every attribute ai∈unSelectAttr, SelectAttr=SelectAttr∪{ai},
calculate the tolerance class of object ui, TAttr(ui)
(3)Calculate the conditional entropy EN(d∣SelectAttr)=EN(d∣SelectAttr∪{ai})
(4)Choose the attribute a which minimizes EN(d∣SelectAttr∪{a}), that is
choose the attribute with the maximum significance measure SIG(a,SelectAttr,d)
(5)SelectAttr=SelectAttr∪{a}, unSelectAttr=unSelectAttr-{a}
(6)If EN(d∣SelectAttr)≠EN(d∣C), go to Step  2, otherwise R=SelecAttr
(7) EndExample 9.
Given the incomplete decision system shown in Table2, we have
(31)SelectAttr=∅,unSelectAttr=C={P,M,S,X},Ud={{u1,u2,u4,u6},{u3},{u5}},EN(d∣{P})=-[2*56*(45log245+15log215)+3*66*(46log246+16log216+16log216)+46*(24log224+14log214+14log214)]=5.9581,EN(d∣{M})=-[6*66*(46log246+16log216+16log216)]=7.5098,EN(d∣{S})=-[5*56*(45*log245+15*log215)+16*(1log21)]=3.0080,EN(d∣{X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774.
Since EN(d∣{X}) has the minimum conditional entropy value, we choose the attribute X as one of selected attributes. Therefore, we can get
(32)SelectAttr=SelectAttr∪{X}={X},unSelectAttr=unSelectAttr-{X}={P,M,S}.
Since EN(d∣{X})≠EN(d∣C), we still need to add more attributes to SelectAttr. On the basis of the rule of heuristic search, we only need to test and compare the conditional entropy values of the subsets in which the condition attribute X is included:
(33)EN(d∣{P,X})=-[3*36*(33log233)+36*(13log213+13log213+13log213)+26*(12log212+12log212)+26*(12log212+12log212)]=1.4591,EN(d∣{M,X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774,EN(d∣{S,X})=-[3*36*(33log233)+16*(1log21)+2*26*(12log212+12log212)]=0.6667.
As previously mentioned, since EN(d∣{S,X}) is the minimum, we choose the attribute S as another selected attribute. Thus we have
(34)SelectAttr=SelectAttr∪{S}={S,X},unSelectAttr=unSelectAttr-{S}={P,M}.
Since EN(d∣{S,X})≠EN(d∣C), it is still necessary to choose more attributes to add to the selected attributes in which attributes S,X are definitely included:
(35)EN(d∣{P,S,X})=-[3*36*(33log233)+16*(1log21)+16*(1log21)+16*(1log21)]=0,EN(d∣{M,S,X})=-[3*36*(33log233)+16*(1log21)+2*26*(12log212+12log212)]=0.6667.
Obviously, since EN(d∣{P,S,X}) is the minimum, we choose the attribute P. Thus, we have
(36)SelectAttr=SelectAttr∪{P}={P,S,X},unSelectAttr=unSelectAttr-{P}={M}.
And since EN(d∣{P,S,X})=EN(d∣C)=0, the stop criterion is satisfied and the algorithm terminates. Hence, the final result of attributes selection is R={P,S,X}. The detailed procedure of the Depth-first algorithm is shown in Figure 2.Figure 2
The flow chart of the Depth-first algorithm.


### 4.3. LVF: Probabilistic Search

Las Vegas algorithm is new for attribute subset selection and can make probabilistic choices of subsets in search of an optimal set. Las Vegas Filter, which is abbreviated as LVF, is a probabilistic algorithm where probabilities of generating any subset are equal [43]. In this paper, we use the investigated conditional entropy as LVF’s evaluation measurement. It generates attribute subsets randomly with equal probability and records the minimal size of attributes subset satisfying the stop criterion of maximum tries times. LVF is fast and efficient in reducing the number of candidate features in the early stages and can produce optimal solutions if the computing resources permit. The LVF approach for attribute selection in incomplete decision system is given, as shown in Algorithm 3.Algorithm 3:LVF.
Input: An incomplete decision system(U,C∪{d}) and MaxTries.
Output: A selected attribute subsetR.
(1) Initialize SelectAttr=C
(2) For j=0 to MaxTries
(3)  Randomly choose a subset of condition attributes Sj
(4)  If EN(d∣Sj)=EN(d∣C) and |Sj|<|SelectAttr|
(5)  SelectAttr=Sj
(6) End
(7)R=SelecAttr


## 4.1. Breadth-First: Exhaustive Search

Breadth-first is one of earliest feature selection or attribute selection algorithms in machine learning area. It begins with an empty attribute set and carries out search process with breadth-first strategy until it finds a minimal subset that satisfies stop criterion. Since the Breadth-first algorithm adopts an exhaustive search strategy, it can guarantee an optimal solution [41]. Then, we present the Breadth-first approach for attribute selection of incomplete decision system as shown in Algorithm 1.Algorithm 1:Breadth-first.
Input: An incomplete decision system(U,C∪{d}).
Output: An attribute selection resultR.
(1) For everysize=0 to |C|
(2) For all subset SelectAttr with|SelectAttr|=size
(3) IfEN(d∣SelectAttr)≠EN(d∣C), go to Step  2, otherwise return R=SelectAttr
(4) End
(5) EndExample 8.
Given the incomplete decision system shown in Table2, we have
(26)C={P,M,S,X},Ud={{u1,u2,u4,u6},{u3},{u5}},TC(u1)=TC(u2)=TC(u6)={u1,u2,u6},TC(u3)={u3},TC(u4)={u4},TC(u5)={u5}.
According to the previous definition of rough conditional entropy, we can simply get
(27)EN(d∣C)=-[3*36*(33log233)+16*(1log21)+16*(1log21)+16*(1log21)]=0.
Consequently, we can deduce other conditional entropy values with respect to the different condition attributes in the same way as follows:
(28)TP(u1)=TP(u4)={u1,u2,u3,u4,u6},TP(u2)=TP(u3)=TP(u6)={u1,u2,u3,u4,u5,u6},TP(u5)={u2,u3,u5,u6},EN(d∣{P})=-[2*56*(45log245+15log215)+3*66*(46log246+16log216+16log216)+46*(24log224+14log214+14log214)]=5.9581,TM(u1)=TM(u2)=TM(u3)=TM(u4)=TM(u5)=TM(u6)={u1,u2,u3,u4,u5,u6},EN(d∣{M})=-[6*66*(46log246+16log216+16log216)]=7.5098,TS(u1)=TS(u2)=TS(u4)=TS(u5)=TS(u6)={u1,u2,u4,u5,u6},TS(u3)={u3},EN(d∣{S})=-[5*56*(45log245+15log215)+16*(1log21)]=3.0080,TX(u1)=TX(u2)=TX(u6)={u1,u2,u6},TX(u3)=TX(u4)=TX(u5)={u3,u4,u5},EN(d∣{X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774.
Then, we calculate the rough conditional entropy values with respect to different combinations of two condition attributes:
(29)TP,M(u1)=TP,M(u4)={u1,u2,u3,u4,u6},TP,M(u2)=TP,M(u3)=TP,M(u6)={u1,u2,u3,u4,u5,u6},TP,M(u5)={u2,u3,u5,u6},EN(d∣{P,M})=-[2*56*(45log245+15log215)+3*66*(46log246+16log216+16log216)+46*(24log224+14log214+14log214)]=5.9581,TP,S(u1)=TP,S(u4)={u1,u2,u4,u6},TP,S(u2)=TP,S(u6)={u1,u2,u4,u5,u6},TP,S(u3)={u3},TP,S(u5)={u2,u5,u6},EN(d∣{P,S})=-[2*46*(44log244)+2*56*(45log245+15log215)+16*(1log21)+36*(23log223+13log213)]=1.6624,TP,X(u1)=TP,X(u2)=TP,X(u6)={u1,u2,u6},TP,X(u3)={u3,u4,u5},TP,X(u4)={u3,u4},TP,X(u5)={u3,u5},EN(d∣{P,X})=-[3*36*(33log233)+36*(13log213+13log213+13log213)+26*(12log212+12log212)+26*(12log212+12log212)]=1.4591,TM,S(u1)=TM,S(u2)=TM,S(u4)=TM,S(u5)=TM,S(u6)={u1,u2,u4,u5,u6},TM,S(u3)={u3},EN(d∣{M,S})=-[5*56*(45log245+15log215)+16*(1log21)]=3.0080,TM,X(u1)=TM,X(u2)=TM,X(u6)={u1,u2,u6},TM,X(u3)=TM,X(u4)=TM,X(u5)={u3,u4,u5},EN(d∣{M,X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774,TS,X(u1)=TS,X(u2)=TS,X(u6)={u1,u2,u6},TS,X(u3)={u3},TS,X(u4)=TS,X(u5)={u4,u5},EN(d∣{S,X})=-[3*36*(33log233)+16*(1log21)+2*26*(12log212+12log212)]=0.6667.
Finally, we calculate the rough conditional entropy values with respect to different combinations of three condition attributes:
(30)TP,M,S(u1)=TP,M,S(u4)={u1,u2,u4,u6},TP,M,S(u2)=TP,M,S(u6)={u1,u2,u4,u5,u6},TP,M,S(u3)={u3},TP,M,S(u5)={u2,u5,u6},EN(d∣{P,M,S})=-[2*46*(44log244)+2*56*(45log245+15log215)+16*(1log21)+36*(23log223+13log213)]=1.6624,TP,M,X(u1)=TP,M,X(u2)=TP,M,X(u6)={u1,u2,u6},TP,M,X(u3)={u3,u4,u5},TP,M,X(u4)={u3,u4},TP,M,X(u5)={u3,u5},EN(d∣{P,M,X})=-[3*36*(33log233)+36*(13log213+13log213+13log213)+26*(12log212+12log212)+26*(12log212+12log212)]=1.4591,TP,S,X(u1)=TP,S,X(u2)=TP,S,X(u6)={u1,u2,u6},TP,S,X(u3)={u3},TP,S,X(u4)={u4},TP,S,X(u5)={u5},EN(d∣{P,S,X})=-[3*36*(33log233)+16*(1log21)+16*(1log21)+16*(1log21)]=0.
Since EN(d∣{P,S,X})=EN(d∣C)=0, we obtain the desired attribute set of selected {P,S,X}, which is a relative reduct of the original condition attribute set C. It also means that the search procedure ends at this step and it is not necessary to calculate the entropy value of the last combination of three attributes {M,S,X} anymore. The detailed search procedure is illustrated in Figure 1.Table 2
Another example of incomplete decision system.
Car
Price
Mileage
Size
Max-speed
Decision
1
High
High
Full
Low
Good
2
*
*
Full
Low
Good
3
*
*
Compact
High
Poor
4
High
*
Full
High
Good
5
Low
*
Full
High
Excellent
6
*
High
Full
Low
GoodFigure 1
The flow chart of the Breadth-first algorithm.


## 4.2. Depth-First: Heuristic Search

We can also use heuristic search or greed search to find attribute reduction. At the very beginning, the candidate attribute subset is empty. Then, a new attribute which can maximize the significance measure is added to the selected attribute subset each time, until the stop criterion is satisfied. Depth-first algorithm is fast, close to optimal, and deterministic [42]. Here, we present the Depth-first approach for incomplete decision system, as shown in Algorithm 2.Algorithm 2:Depth-first.
Input: An incomplete decision system(U,C∪{d}).
Output: A selected attribute subsetR.
(1) InitializeSelectAttr=⌀, unSelectAttr=C
(2)For every attribute ai∈unSelectAttr, SelectAttr=SelectAttr∪{ai},
calculate the tolerance class of object ui, TAttr(ui)
(3)Calculate the conditional entropy EN(d∣SelectAttr)=EN(d∣SelectAttr∪{ai})
(4)Choose the attribute a which minimizes EN(d∣SelectAttr∪{a}), that is
choose the attribute with the maximum significance measure SIG(a,SelectAttr,d)
(5)SelectAttr=SelectAttr∪{a}, unSelectAttr=unSelectAttr-{a}
(6)If EN(d∣SelectAttr)≠EN(d∣C), go to Step  2, otherwise R=SelecAttr
(7) EndExample 9.
Given the incomplete decision system shown in Table2, we have
(31)SelectAttr=∅,unSelectAttr=C={P,M,S,X},Ud={{u1,u2,u4,u6},{u3},{u5}},EN(d∣{P})=-[2*56*(45log245+15log215)+3*66*(46log246+16log216+16log216)+46*(24log224+14log214+14log214)]=5.9581,EN(d∣{M})=-[6*66*(46log246+16log216+16log216)]=7.5098,EN(d∣{S})=-[5*56*(45*log245+15*log215)+16*(1log21)]=3.0080,EN(d∣{X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774.
Since EN(d∣{X}) has the minimum conditional entropy value, we choose the attribute X as one of selected attributes. Therefore, we can get
(32)SelectAttr=SelectAttr∪{X}={X},unSelectAttr=unSelectAttr-{X}={P,M,S}.
Since EN(d∣{X})≠EN(d∣C), we still need to add more attributes to SelectAttr. On the basis of the rule of heuristic search, we only need to test and compare the conditional entropy values of the subsets in which the condition attribute X is included:
(33)EN(d∣{P,X})=-[3*36*(33log233)+36*(13log213+13log213+13log213)+26*(12log212+12log212)+26*(12log212+12log212)]=1.4591,EN(d∣{M,X})=-[3*36*(33log233)+3*36*(13log213+13log213+13log213)]=2.3774,EN(d∣{S,X})=-[3*36*(33log233)+16*(1log21)+2*26*(12log212+12log212)]=0.6667.
As previously mentioned, since EN(d∣{S,X}) is the minimum, we choose the attribute S as another selected attribute. Thus we have
(34)SelectAttr=SelectAttr∪{S}={S,X},unSelectAttr=unSelectAttr-{S}={P,M}.
Since EN(d∣{S,X})≠EN(d∣C), it is still necessary to choose more attributes to add to the selected attributes in which attributes S,X are definitely included:
(35)EN(d∣{P,S,X})=-[3*36*(33log233)+16*(1log21)+16*(1log21)+16*(1log21)]=0,EN(d∣{M,S,X})=-[3*36*(33log233)+16*(1log21)+2*26*(12log212+12log212)]=0.6667.
Obviously, since EN(d∣{P,S,X}) is the minimum, we choose the attribute P. Thus, we have
(36)SelectAttr=SelectAttr∪{P}={P,S,X},unSelectAttr=unSelectAttr-{P}={M}.
And since EN(d∣{P,S,X})=EN(d∣C)=0, the stop criterion is satisfied and the algorithm terminates. Hence, the final result of attributes selection is R={P,S,X}. The detailed procedure of the Depth-first algorithm is shown in Figure 2.Figure 2
The flow chart of the Depth-first algorithm.


## 4.3. LVF: Probabilistic Search

Las Vegas algorithm is new for attribute subset selection and can make probabilistic choices of subsets in search of an optimal set. Las Vegas Filter, which is abbreviated as LVF, is a probabilistic algorithm where probabilities of generating any subset are equal [43]. In this paper, we use the investigated conditional entropy as LVF’s evaluation measurement. It generates attribute subsets randomly with equal probability and records the minimal size of attributes subset satisfying the stop criterion of maximum tries times. LVF is fast and efficient in reducing the number of candidate features in the early stages and can produce optimal solutions if the computing resources permit. The LVF approach for attribute selection in incomplete decision system is given, as shown in Algorithm 3.Algorithm 3:LVF.
Input: An incomplete decision system(U,C∪{d}) and MaxTries.
Output: A selected attribute subsetR.
(1) Initialize SelectAttr=C
(2) For j=0 to MaxTries
(3)  Randomly choose a subset of condition attributes Sj
(4)  If EN(d∣Sj)=EN(d∣C) and |Sj|<|SelectAttr|
(5)  SelectAttr=Sj
(6) End
(7)R=SelecAttr


## 5. Experiments

In this section, the performances of our attribute selection algorithms given in previous section are demonstrated and compared. Several real-life incomplete data sets from UCI Repository of Machine Learning Database at the University of California are used in our experiments. These experiments are performed on a personal computer with Windows 7, Intel (R) Core (TM) i3 CPU 2.13 GHz, and 4 GB RAM. The objective of these experiments is to evaluate the effectiveness and efficiency of the previous algorithms. The summary and statistic of the experimental data sets are shown in Table3 and Figure 3, respectively.Table 3
The summary of experimental data sets.
Data sets
Instances
Condition attributes
Missing values
Decision classes
Incomplete rate (%)
Lung cancer
32
56
5
3
0.28
Large soybean
307
35
712
19
6.63
Dermatology
366
34
8
6
0.06
Breast cancer
699
10
16
2
0.23
Credit
690
15
71
2
0.69
Hepatitis
155
19
167
2
5.67The statistical result of experimental data sets.
(a)
(b)
(c)
(d)
(e)Since some incomplete data sets contain continuous condition attribute values, we conduct a discretization preprocess to turn these continuous values into discrete ones before carrying out attribute selection. The aim of this step is to compress the data and reduce the time consumption of subsequent attribute selection. The running time of each algorithm is average CPU time, expressed in seconds.In Breadth-first algorithm, we terminate the program when it runs beyond 5000 seconds. Moreover, we set the parameter MaxTries in LVF algorithm to variant values for different incomplete data sets, according to their sizes. The running time and the size of attribute selection results are highly concerned with the choice of the parameter MaxTries. It means that when MaxTries grows, the running time of LVF approach increases linearly and the size of selected attribute subset decreases. Both of them for each attribute selection approach are shown in Table4. The running time of each approach is the average CPU time, expressed in seconds. We can easily find that Breadth-first approach takes much more time, even more than 5000 seconds, to obtain an attribute reduction, compared with the other two approaches. Three data sets out of six are too large in scale to calculate in limited time. Furthermore, it is also easy to be observed in Table 4 that Depth-first approach tends to select fewer attributes than LVF approach. In other words, the size of attribute subset selected by Depth-first approach intends to be smaller than that of attribute subset selected by LVF approach. And Depth-first approach consumes less time than the other two approaches in most instances. The time consumptions of Breadth-first approach, Depth-first approach, and LVF approach for attribute selection are O(2|C|·|U|2), O(|C|4|U|2), and O(MaxTries·|C||U|2), respectively, where MaxTries, |C|, and |U| denote the MaxTries parameter in LVF approach, the total numbers of the condition attributes, and instances in incomplete data sets, respectively. The relationships between incomplete data sets and the number of selected attributes, the running time of attribute selection, are illustrated in Figures 4 and 5.Table 4
Size of selected attribute subsets and running time.
Data sets
Breadth-first
Depth-first
LVF
Full attr.
Size
Time (s)
Size
Time (s)
Size
Time (s)
MaxTries
Size
Lung cancer
4
227.59
4
0.68
5
7.34
10000
56
Large soybean
N/A
>5000
14
80.99
23
806.38
5000
35
Dermatology
N/A
>5000
6
58.22
11
44.83
200
34
Breast cancer
5
367.37
5
51.59
5
91.29
100
10
Credit
N/A
>5000
7
89.94
9
90.75
100
15
Hepatitis
5
349.07
6
6.07
6
35.22
500
19Figure 4
Number of selected attributes versus data set.Figure 5
Running time of attribute selection versus data set.The final part of our experiments is to compare and evaluate the efficiency of the proposed algorithms in practical classification tasks. For each of the six data sets in Table5, we employ the SVM-RBF classifier, which is one of the most frequently used classifiers. We also apply the 10-fold cross-validation method to estimate the classification accuracy with respect to the reducts generated by the proposed algorithms. In each fold, the redundant attributes from the current training set are removed at the beginning, according to the proposed algorithms. Then, the test set is classified by using the rules generated from the training set. The final results of classification accuracies are shown in Table 5. It can be seen that, by using attribute selection algorithms, the classification accuracies for incomplete data sets are all raised in different degrees, compared with the classification accuracy for the original full attributes. It also can be noticed that the Depth-first algorithm exhibits the highest classification accuracy on each incomplete data set. Therefore, the experimental results demonstrate that the proposed algorithms are effective for attribute selection tasks in application domains.Table 5
Performance of attribute selection algorithms with SVM-RBF classifier.
Data sets
Classification accuracy (%)
Breadth-first
Depth-first
LVF
Full attr.
Lung cancer
66.92
76.42
69.26
66.67
Large soybean
N/A
95.21
94.74
92.98
Dermatology
N/A
91.22
91.32
83.38
Breast cancer
97.11
97.11
96.18
95.69
Credit
N/A
84.77
81.69
80.88
Hepatitis
83.75
85.00
82.50
78.75


## 6. Conclusion

In this paper, a rough conditional entropy-based attribute selection approach is proposed to evaluate the significance of condition attributes and find the minimal reduct in incomplete decision systems. By this measure, three types of attribute selection approaches, including the exhaustive search strategy approach Breadth-first, the heuristic search strategy approach Depth-first, and the probabilistic search approach LVF, are constructed. To evaluate the effectiveness of the introduced approaches, experiments on several real-life incomplete data sets are conducted. The experimental results suggest that Depth-first and LVF approaches are practical for attribute selection for classification of high-dimensional data with thousands of condition attributes, and they can efficiently enhance classification accuracy with predominant attributes. However, the process of examining exhaustively all combinations of condition attributes for finding the optimal one is an NP-hard problem. So far, it still cannot be easily calculated by our approaches if there are hundreds of thousands of condition attributes in a complex incomplete decision system. Therefore, for large data sets, to reduce the time consumption of the process of attribute selection, more applicable approaches such as parallel heuristic algorithms are desirable for incomplete decision systems with large scale. This issue needs to be investigated in the future.



---

*Source: 728923-2014-02-12.xml*