# Cost-Sensitive Feature Selection of Numeric Data with Measurement Errors

Authors: Hong Zhao; Fan Min; William Zhu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Feature selection is an essential process in data mining applications since it reduces a model’s complexity. However, feature selection with various types of costs is still a new research topic. In this paper, we study the cost-sensitive feature selection problem of numeric data with measurement errors. The major contributions of this paper are fourfold. First, a new data model is built to address test costs and misclassification costs as well as error boundaries. It is distinguished from the existing models mainly on the error boundaries. Second, a covering-based rough set model with normal distribution measurement errors is constructed. With this model, coverings are constructed from data rather than assigned by users. Third, a new cost-sensitive featureselection problem is defined on this model. It is more realistic than the existing feature selection problems. Fourth, both backtracking and heuristic algorithms are proposed to deal with the new problem. Experimental results show the efficiency of the pruning techniques for the backtracking algorithm and the effectiveness of the heuristic algorithm. This study is a step toward realistic applications of the cost-sensitive learning.


---

## Body

## 1. Introduction

Feature selection [1–3] is an essential process in data mining applications. The main aim of feature selection is to reduce the dimensionality of the feature space and to improve the predictive accuracy of a classification algorithm [4, 5]. In many domains, the misclassification costs [6–9] and the test costs [10, 11] must be considered in the feature selection process. Cost-sensitive feature selection [12–14] focuses on selecting a feature subset with a minimal total cost as well as preserving a particular property of the decision system [15, 16].Test costs and misclassification costs are two most important types of cost in cost-sensitive learning [17]. The test cost is money, time, or other resources we pay for collecting a data item of an object [18, 19]. The misclassification cost is the penalty we receive while deciding that an object belongs to class J when its real class is K [6, 8]. Some works have considered only misclassification costs [20], or only test costs [21–23]. However, in many applications, it is important to consider both types of costs together.Recently, the cost-sensitive feature selection problem for nominal datasets was proposed [17]. A backtracking algorithm has been presented to address this problem. However, this algorithm has been applied to only small datasets and addressed on only nominal data. In real applications, the data can be acquired from measurements with different errors. The measurement errors of the data have certain universality.In this paper, we propose the cost-sensitive feature selection problem of numerical data with measurement errors and deal with it through considering the trade-off between test costs and misclassification costs. The major contributions of this paper are fourfold. First, based on normal distribution measurement errors, we build a new data model to address test costs and misclassification costs as well as error boundaries. It is distinguished from the existing models [17] mainly on the error boundaries. Second, we construct a computational model of the covering-based rough set with normal distribution measurement errors. In fact, normal distribution [24, 25] is found to be applicable over almost the whole of science and engineering measurement. With this model, coverings are constructed from data rather than assigned by users. Third, the cost-sensitive feature selection problem is defined on this new model of covering-based rough set. It is more realistic than the existing feature selection problems. Fourth, a backtracking algorithm is proposed to find an optimal feature subset for small datasets. However, for large dataset, finding a minimal cost feature subset is NP-hard. Consequently, we propose a heuristic algorithm to deal with this problem.Six open datasets from the University of California-Irvine (UCI) library are employed to study the performance and effectiveness of our algorithms. Experiments are undertaken with open source software cost-sensitive rough sets (Coser) [26]. Experimental results show that the pruning techniques of the backtracking algorithm reduce searching operations by several orders of magnitudes. In addition, the heuristic algorithm can provide efficient solution to find an optimal feature subset in most cases. Even if the feature subset is not optimal, it is still acceptable from a statistical point of view.The rest of the paper is organized as follows. Section2 presents data models with test costs and misclassification costs as well as measurement errors. Section 3 describes the computational model, namely, covering-based rough set model with measurement errors. The feature selection with the minimal cost problem on the new model is also defined in this section. Then, Section 4 presents a backtracking algorithm and a heuristic algorithm to address this feature selection problem. In Section 5, we discuss the experimental settings and results. Finally, Section 6 concludes and suggests further research trends.


## 2. Data Models

Data models are presented in this section. First, we start from basic decision systems. Then, we introduce normal distribution errors to test and propose a decision system with measurement errors. Finally, we introduce a decision system based on measurement errors with test costs and misclassification costs.


### 2.1. Decision Systems

Decision systems are fundamental in data mining and machine learning. For completeness, a decision system is defined below.Definition 1 (see [27]).
A decision system (DS) is the 5-tuple:(1)S=(U,C,d,V={Va∣a∈C∪{d}},I={Ia∣a∈C∪{d}}{Va∣a∈C∪{d}}),
where U is a universal set of objects, C is a nonempty set of conditional attributes, and d is the decision attribute. For each a∈C∪{d}, Ia:U→Va. The set Va is the value set of attribute a, and Ia is the information function for each attribute a.In order to facilitate processing and comparison, the values of conditional attributes are normalized from their value into a range from 0 to 1. In fact, there are a number of normalization approaches. For simplicity, we employ the linear functiony=(x-min)/(max-min), where x is the initial value, y is the normalized value, and max and min are the maximal and minimal values of the attribute domain, respectively.Table1 is a decision system of Bupa liver disorder (Liver for short), in which conditional attributes are normalized values. Here, C= {Mcv, Alkphos, Sgpt, Sgot, Gammagt, Drinks}, d={Selector}, and U={x1,x2,…,x345}.Table 1
An example of numeric decision system (Liver).
Patient
Mcv
Alkphos
Sgpt
Sgot
Gammagt
Drinks
Selector
x
1
0.31
0.23
0.08
0.28
0.09
0.00
y
x
2
0.14
0.38
0.23
0.35
0.06
0.10
y
x
3
0.25
0.40
0.40
0.14
0.17
0.20
y
x
4
0.60
0.46
0.51
0.25
0.11
0.60
n
x
5
0.41
0.64
0.62
0.30
0.02
0.30
n
x
6
0.35
0.50
0.75
0.30
0.02
0.40
n
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
x
344
0.68
0.39
0.15
0.23
0.03
0.80
n
x
345
0.87
0.66
0.35
0.52
0.21
1.00
nLiver contains 7 attributes. The first 5 attributes are all blood tests which are thought to be sensitive to liver disorders that might arise from excessive alcohol consumption. The sixth attribute is the number of alcoholic drinks per day. Each line in Liver constitutes the record of a single male individual. The Selector attribute is used to split data into two sets.


### 2.2. A Decision System with Measurement Errors

In real applications, datasets often contain many continuous (or numerical) attributes. There are a number of measurement methods with different test costs to obtain a numerical data item. Generally, higher test cost is required to obtain data with smaller measurement error [28]. The measurement errors often satisfy normal distribution which is found to be applicable over almost the whole of science and engineering measurement. We include normal distribution measurement errors in our model to expand the application scope.Definition 2 (see [28]).
A decision system with measurement errors (MEDS)S is the 6-tuple:
(2)S=(U,C,d,V,I,n),
where U,C,d,V, and I have the same meanings as in Definition 1, n:C→ℝ+∪{0} is the maximal measurement error function, and ±n(a) is the error boundary of attribute a.Givenxi∈U, the error boundary of attribute a is given by
(3)n(a)=ΔΣi=1ma(xi)m,
where the regulator factor Δ∈[0,1] can adjust the error boundary.In applications, one can deal with the abnormal value of measurement error according to the Pauta criterion of measurement error theory, which is used to determine the abnormal values. That is, if the repeated measurement data satisfy|xi-x¯|>3σ, (i=1,2,…,N), the xi would be considered as an abnormal value and be rejected, where σ is the standard deviation, and x¯ is the mean of all measurement values.Recently, the concept of neighborhood (see, e.g., [29, 30]) has been applied to define different types of covering-based rough set [31–34]. A neighborhood based on static error range is defined [35]. Although showing similarities, it is essentially different from ours. The proposed neighborhood is considered as the distribution of the data error and the confidence interval. The neighborhood boundaries for different attributes of the same database are completely different. An example of neighborhood boundary vector is listed in Table 2.Table 2
An example of neighborhood boundary vector.
a
Mcv
Alkphos
Sgpt
Sgot
Gammagt
Drinks
n
(
a
)
0.069
0.087
0.086
0.036
0.026
0.017


### 2.3. A Decision System Based on Measurement Errors with Test Costs and Misclassification Costs

In many applications, the test cost must be taken into account [5]. Test cost is the money, time, or other resources that we pay for collecting a data item of an object [8, 9, 18, 19, 36]. In addition to the test costs, it is also necessary to consider misclassification costs. A decision cannot be made if the misclassification costs are unreasonable [5]. More recently, researchers have begun to consider both test costs and misclassification costs [8, 13, 17].Now, we take into account both test and misclassification costs as well as normal distribution measurement errors. We have defined this decision system in [37] as follows.Definition 3.
A decision system based on measurement errors with test costs and misclassification costs (MEDS-TM)S is the 8-tuple:
(4)S=(U,C,d,V,I,n,tc,mc),
where U,C,d,V,I, and n have the same meanings as Definition 2, tc:C→ℝ+∪{0} is the test cost function, and mc:k×k→ℝ+∪{0} is the misclassification cost function, where k=|Id|.Here, we consider only the sequence-independent test-cost-sensitive decision system. There are a number of test-cost-sensitive decision systems. A hierarchy of decision systems consisting of six models was proposed [18]. For any B⊆C, the test cost function tc is given by tc(B)=∑a∈B‍tc(a).The test cost function can be stored in a vector. An example of text cost vector is listed in Table3.Table 3
An example of test cost vector.
a
Mcv
Alkphos
Sgpt
Sgot
Gammagt
Drinks
tc
(
a
)
$26
$17
$34
$45
$38
$5The misclassification cost [38–40] is the penalty that we receive while deciding that an object belongs to class i when its real class is j [8]. The misclassification cost function mc is defined as follows:(1)
mc:k×k→ℝ+∪{0} is the misclassification cost function, which can be represented by a matrix MC={mck×k}, where k=|Id|,(2)
mc[m,n] is the cost of misclassifying an example from “class m" to “class n",(3)
mc[m,m]=0.The following example gives us an intuitive understanding of the decision system based on measurement errors with test costs and misclassification costs.Example 4.
Table1 is a Liver decision system. Tables 2 and 3 are error boundary vector and test cost vector of Liver decision system, respectively. consider
(5)mc=[020002000].
That is, the test costs of Mcv, Alkphos, Sgpt, Sgot, Gammagt, and Drinks are $26, $17, $34, $45, $38, and $5, respectively. In Liver dataset, the Selector field is used to split data into two sets. Here, a false negative prediction (FN), that is, failing to detect liver disorders, may well have fatal consequences, whereas a false positive prediction (FP), that is, diagnosing liver disorders for a patient that does not actually have them, may be less serious [41]. Therefore, a higher penalty of $2000 is paid for FN prediction and $200 is paid for FP prediction.Obviously, iftc and mc are not considered, the MEDS-TM degrades to a decision system with measurement errors (MEDS) (see, e.g., [28]). Therefore, the MEDS-TM is a generalization of the MEDS.


## 2.1. Decision Systems

Decision systems are fundamental in data mining and machine learning. For completeness, a decision system is defined below.Definition 1 (see [27]).
A decision system (DS) is the 5-tuple:(1)S=(U,C,d,V={Va∣a∈C∪{d}},I={Ia∣a∈C∪{d}}{Va∣a∈C∪{d}}),
where U is a universal set of objects, C is a nonempty set of conditional attributes, and d is the decision attribute. For each a∈C∪{d}, Ia:U→Va. The set Va is the value set of attribute a, and Ia is the information function for each attribute a.In order to facilitate processing and comparison, the values of conditional attributes are normalized from their value into a range from 0 to 1. In fact, there are a number of normalization approaches. For simplicity, we employ the linear functiony=(x-min)/(max-min), where x is the initial value, y is the normalized value, and max and min are the maximal and minimal values of the attribute domain, respectively.Table1 is a decision system of Bupa liver disorder (Liver for short), in which conditional attributes are normalized values. Here, C= {Mcv, Alkphos, Sgpt, Sgot, Gammagt, Drinks}, d={Selector}, and U={x1,x2,…,x345}.Table 1
An example of numeric decision system (Liver).
Patient
Mcv
Alkphos
Sgpt
Sgot
Gammagt
Drinks
Selector
x
1
0.31
0.23
0.08
0.28
0.09
0.00
y
x
2
0.14
0.38
0.23
0.35
0.06
0.10
y
x
3
0.25
0.40
0.40
0.14
0.17
0.20
y
x
4
0.60
0.46
0.51
0.25
0.11
0.60
n
x
5
0.41
0.64
0.62
0.30
0.02
0.30
n
x
6
0.35
0.50
0.75
0.30
0.02
0.40
n
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
x
344
0.68
0.39
0.15
0.23
0.03
0.80
n
x
345
0.87
0.66
0.35
0.52
0.21
1.00
nLiver contains 7 attributes. The first 5 attributes are all blood tests which are thought to be sensitive to liver disorders that might arise from excessive alcohol consumption. The sixth attribute is the number of alcoholic drinks per day. Each line in Liver constitutes the record of a single male individual. The Selector attribute is used to split data into two sets.


## 2.2. A Decision System with Measurement Errors

In real applications, datasets often contain many continuous (or numerical) attributes. There are a number of measurement methods with different test costs to obtain a numerical data item. Generally, higher test cost is required to obtain data with smaller measurement error [28]. The measurement errors often satisfy normal distribution which is found to be applicable over almost the whole of science and engineering measurement. We include normal distribution measurement errors in our model to expand the application scope.Definition 2 (see [28]).
A decision system with measurement errors (MEDS)S is the 6-tuple:
(2)S=(U,C,d,V,I,n),
where U,C,d,V, and I have the same meanings as in Definition 1, n:C→ℝ+∪{0} is the maximal measurement error function, and ±n(a) is the error boundary of attribute a.Givenxi∈U, the error boundary of attribute a is given by
(3)n(a)=ΔΣi=1ma(xi)m,
where the regulator factor Δ∈[0,1] can adjust the error boundary.In applications, one can deal with the abnormal value of measurement error according to the Pauta criterion of measurement error theory, which is used to determine the abnormal values. That is, if the repeated measurement data satisfy|xi-x¯|>3σ, (i=1,2,…,N), the xi would be considered as an abnormal value and be rejected, where σ is the standard deviation, and x¯ is the mean of all measurement values.Recently, the concept of neighborhood (see, e.g., [29, 30]) has been applied to define different types of covering-based rough set [31–34]. A neighborhood based on static error range is defined [35]. Although showing similarities, it is essentially different from ours. The proposed neighborhood is considered as the distribution of the data error and the confidence interval. The neighborhood boundaries for different attributes of the same database are completely different. An example of neighborhood boundary vector is listed in Table 2.Table 2
An example of neighborhood boundary vector.
a
Mcv
Alkphos
Sgpt
Sgot
Gammagt
Drinks
n
(
a
)
0.069
0.087
0.086
0.036
0.026
0.017


## 2.3. A Decision System Based on Measurement Errors with Test Costs and Misclassification Costs

In many applications, the test cost must be taken into account [5]. Test cost is the money, time, or other resources that we pay for collecting a data item of an object [8, 9, 18, 19, 36]. In addition to the test costs, it is also necessary to consider misclassification costs. A decision cannot be made if the misclassification costs are unreasonable [5]. More recently, researchers have begun to consider both test costs and misclassification costs [8, 13, 17].Now, we take into account both test and misclassification costs as well as normal distribution measurement errors. We have defined this decision system in [37] as follows.Definition 3.
A decision system based on measurement errors with test costs and misclassification costs (MEDS-TM)S is the 8-tuple:
(4)S=(U,C,d,V,I,n,tc,mc),
where U,C,d,V,I, and n have the same meanings as Definition 2, tc:C→ℝ+∪{0} is the test cost function, and mc:k×k→ℝ+∪{0} is the misclassification cost function, where k=|Id|.Here, we consider only the sequence-independent test-cost-sensitive decision system. There are a number of test-cost-sensitive decision systems. A hierarchy of decision systems consisting of six models was proposed [18]. For any B⊆C, the test cost function tc is given by tc(B)=∑a∈B‍tc(a).The test cost function can be stored in a vector. An example of text cost vector is listed in Table3.Table 3
An example of test cost vector.
a
Mcv
Alkphos
Sgpt
Sgot
Gammagt
Drinks
tc
(
a
)
$26
$17
$34
$45
$38
$5The misclassification cost [38–40] is the penalty that we receive while deciding that an object belongs to class i when its real class is j [8]. The misclassification cost function mc is defined as follows:(1)
mc:k×k→ℝ+∪{0} is the misclassification cost function, which can be represented by a matrix MC={mck×k}, where k=|Id|,(2)
mc[m,n] is the cost of misclassifying an example from “class m" to “class n",(3)
mc[m,m]=0.The following example gives us an intuitive understanding of the decision system based on measurement errors with test costs and misclassification costs.Example 4.
Table1 is a Liver decision system. Tables 2 and 3 are error boundary vector and test cost vector of Liver decision system, respectively. consider
(5)mc=[020002000].
That is, the test costs of Mcv, Alkphos, Sgpt, Sgot, Gammagt, and Drinks are $26, $17, $34, $45, $38, and $5, respectively. In Liver dataset, the Selector field is used to split data into two sets. Here, a false negative prediction (FN), that is, failing to detect liver disorders, may well have fatal consequences, whereas a false positive prediction (FP), that is, diagnosing liver disorders for a patient that does not actually have them, may be less serious [41]. Therefore, a higher penalty of $2000 is paid for FN prediction and $200 is paid for FP prediction.Obviously, iftc and mc are not considered, the MEDS-TM degrades to a decision system with measurement errors (MEDS) (see, e.g., [28]). Therefore, the MEDS-TM is a generalization of the MEDS.


## 3. Covering-Based Rough Set with Measurement Errors

As a technique to deal with granularity in information systems, rough set theory was proposed by Pawlak [42]. Since then, we have witnessed a systematic, worldwide growth of interest in rough set theory [43–52] and its applications [53, 54]. Recently, there has been growing interest in covering-based rough set. In this section, we introduce normal distribution measurement errors to covering-based rough set. The new model is called covering-based rough set with measurement errors. Then, we define a new cost-sensitive feature selection problem on this covering-based rough set.


### 3.1. Covering-Based Rough Set with Measurement Errors

The covering-based rough set with measurement errors is a natural extension of the classical rough set. If all attributes are error free, the covering-based rough set model degenerates to the classical one. With the definition of the MEDS, a new neighborhood is defined as follows.Definition 5 (see [28]).
LetS=(U,C,d,V,I,n) be a decision system with measurement errors. Given B⊆C and xi∈U, the neighborhood of xi with reference to measurement errors on the feature set B is defined as
(6)nB(xi)={x∈U∣∀a∈B,|a(x)-a(xi)|≤2n(a)}.
That means the value of the measurement error of attribute a in [-n(a),+n(a)]. According to Definition 5, we know that the neighborhood nB(xi) is the intersection of multiple basic neighborhoods. Therefore, we obtain
(7)nB(xi)=⋂a∈B‍n{a}(xi).Although showing similarities, the neighborhood defined in [35] is essentially different from ours in two ways. First, a fixed boundary of neighborhood is used for different datasets. In contrast, the boundaries of neighborhood in our model are computed according to the values of attributes. Then, the uniform distribution is considered in [35]. In contrast, we introduce the normal distribution to our model. As mentioned earlier, the normal distribution is found to be applicable over almost the whole of science measurement.Normal distribution is a plausible distribution for measurement errors. In statistics, “3-sigma” rule states that over 99.73% (95.45%) of measurement data will fall within three (two) standard deviations of the mean [55]. We introduce this rule to our model and present a new neighborhood considering both the error distribution and the confidence interval. The proportion of small measurement errors is higher than large ones. Any value in the measurement that exceeds the three standard deviations from the mean should be discarded. Therefore, the measurement errors with no more than a difference of 3σ (2σ) should be viewed as a granule. In view of this, we introduce the relationship between the error boundary and the standard deviation in the following proposition.Proposition 6.
Let the error boundaryn(a)=3σ and Pr be the confidence level. one has about Pr=99.73% of cases within n(a)=±3σ.According to Proposition6, we have about Pr=99.73% of cases within n(a)=±3σ. If n(a)=2σ, we have about Pr=95.45% of cases within ±n(a). According to Definition 5, every item belongs to its own neighborhood. This is formally given by the following theorem.Theorem 7.
LetS=(U,C,d,V,I,n) be a decision system with measurement errors and B⊆C. The set {nB(xi)∣xi∈U} is a covering of U.Proof.
Given for allx∈U, for all a∈B, |a(x)-a(x)|=0, |a(x)-a(x)|≤2n(a), x∈nB(x).
Therefore, for allx∈U, nB(x)≠∅, and for any B⊆C, ⋃x∈U‍nB(x)=U.
Hence, the set{nB(xi)∣xi∈U} is a covering of U. This completes the proof.Now, we discuss the lower and upper approximations as well as the boundary region of rough set in the new model.Definition 8 (see [28]).
LetS=(U,C,d,V,I,n) be a decision system with measurement errors and NB a neighborhood relation on U, where B⊆C. We call 〈U,NB〉 a neighborhood approximation space. For arbitrary X⊆U, the lower approximation and the upper approximation of X in 〈U,NB〉 are defined as
(8)NB_(X)={xi∣xi∈U∧nB(xi)⊆X},NB¯(X)={xi∣xi∈U∧nB(xi)∩X≠∅}.
The positive region of {d} concerning B⊆C is defined as POSB({d})=⋃X∈U/{d}‍NB_(X) [42, 56].Definition 9.
LetS=(U,C,d,V,I,n) be a decision system with measurement errors, for all X⊆U, NB¯(X)⊇X⊇NB_(X). The boundary region of X in 〈U,NB〉 is defined as
(9)BNB(X)=NB¯(X)-NB_(X).Generally, a covering is produced by a neighborhood boundary. The inconsistent object in a neighborhood is defined as follows.Definition 10 (see [28]).
LetS=(U,C,d,V,I,n) be a decision system with measurement errors, B⊆C, and x,y∈U. In the set of nB(x), for all y∈nB(x) is called an inconsistent object if d(y)≠d(x). The set of inconsistent objects in nB(x) is
(10)icB(x)={y∈nB(x)∣d(y)≠d(x)}.
The number of inconsistent objects is denoted as |icB(x)|.Using a specific example, we explain the lower approximations, the upper approximations, the boundary regions, and the inconsistent objects of the neighborhood.Example 11.
A decision system with neighborhood boundaries is given in Tables4 and 5. Table 4 is a subtable of Table 1. Let U={x1,x2,…,x6}, C={a1,a2,a3}, and D={d}={Selector}, where a1 = Mcv, a2 = Alkphos, and a3 = Sgpt. nB(x) are listed in Table 6, where B takes values listed as column headers, and x takes values listed in each row. According to Definition 10, the inconsistent object in n{a1}(x1) is ic{a1}(x1)={x5,x6}.
In addition,U is divided into a set of equivalence classes by {d}. U/{d}={{x1,x2,x3},{x4,x5,x6}}. Let X1={x1,x2,x3} and X2={x4,x5,x6}. NB_(X) and NB¯(X) are listed in the first part and the second part of Table 7, respectively. Here, B takes values listed as column headers, and X takes values listed in each row.
The positive regions and the boundary regions ofU on different test sets can be computed from Table 7:(1)
POS{a1}({d})={x2,x4}, BN{a1}({d})={x1,x3,x5,x6},(2)
POS{a1,a2}({d})={x1,x2,x4,x5}, BN{a1,a2}({d})={x3,x6},(3)
POS{a1,a3}({d})={x1,x2,x3,x4,x5,x6}, BN{a1,a3}({d})=∅,(4)
{a1,a3} has the same approximating power as C.Table 4
A subtable of theLiver decision system.
Patient
a
1
a
2
a
3
d
x
1
0.31
0.23
0.08
y
x
2
0.14
0.38
0.23
y
x
3
0.25
0.40
0.40
y
x
4
0.60
0.46
0.51
n
x
5
0.41
0.64
0.62
n
x
6
0.35
0.50
0.75
nTable 5
An example of adaptive neighborhood boundary vector.
a
a
1
a
2
a
3
Neighborhood boundaries
±
0.069
±
0.087
±
0.086Table 6
The neighborhood of objects on different test sets.
x
{
a
1
}
{
a
1
,
a
2
}
{
a
1
,
a
3
}
{
a
1
,
a
2
,
a
3
}
x
1
{
x
1
,
x
3
,
x
5
,
x
6
}
{
x
1
,
x
3
}
{
x
1
}
{
x
1
}
x
2
{
x
2
,
x
3
}
{
x
2
,
x
3
}
{
x
2
,
x
3
}
{
x
2
,
x
3
}
x
3
{
x
1
,
x
2
,
x
3
,
x
6
}
{
x
1
,
x
2
,
x
3
,
x
6
}
{
x
2
,
x
3
}
{
x
2
,
x
3
}
x
4
{
x
4
}
{
x
4
}
{
x
4
}
{
x
4
}
x
5
{
x
1
,
x
5
,
x
6
}
{
x
5
,
x
6
}
{
x
5
,
x
6
}
{
x
5
,
x
6
}
x
6
{
x
1
,
x
3
,
x
5
,
x
6
}
{
x
3
,
x
5
,
x
6
}
{
x
5
,
x
6
}
{
x
5
,
x
6
}Table 7
Approximations of object subsets on different test sets.
X
{
a
1
}
{
a
1
,
a
2
}
{
a
1
,
a
3
}
{
a
1
,
a
2
,
a
3
}
N
B
_
(
X
)
X
1
{
x
2
}
{
x
1
,
x
2
}
{
x
1
,
x
2
,
x
3
}
{
x
1
,
x
2
,
x
3
}
X
2
{
x
4
}
{
x
4
,
x
5
}
{
x
4
,
x
5
,
x
6
}
{
x
4
,
x
5
,
x
6
}
N
B
¯
(
X
)
X
1
{
x
1
,
x
2
,
x
3
,
x
5
,
x
6
}
{
x
1
,
x
2
,
x
3
,
x
6
}
{
x
1
,
x
2
,
x
3
}
{
x
1
,
x
2
,
x
3
}
X
2
{
x
1
,
x
3
,
x
4
,
x
5
,
x
6
}
{
x
3
,
x
4
,
x
5
,
x
6
}
{
x
4
,
x
5
,
x
6
}
{
x
4
,
x
5
,
x
6
}


### 3.2. Minimal Cost Feature Selection Problem

In this work, we focus on cost-sensitive feature selection based on test costs and misclassification costs. Unlike reduction problems, we do not require any particular property of the decision system to be preserved. The objective of feature selection is to minimize the average total cost through considering a trade-off between test costs and misclassification costs. Cost-sensitive feature selection problem is called thefeature selection with minimal average total cost (FSMC) problem.Problem 1.
The FSMC problem:input: S=(U,C,d,V,I,n,tc,mc),output: R⊆C,optimization objective: minimize the average total cost (ATC).The FSMC problem is a generalization of classical minimal reduction problem. On the one hand, several factors should be considered such as the test costs and misclassification costs as well as normal distribution measurement errors. These factors are all intrinsic to data in real applications. On the other hand, the minimal average total cost is the optimization objective through considering the trade-off between the two kinds of costs. Compared with the accuracy, the average total cost is more general metric in data mining applications [36]. The following is a five-step process to compute the average total cost.(1)
LetB be a selected feature set. Given for all x∈U, we compute the neighborhood space nB(x).(2)
LetU′=nB(x) and let d(x) be the decision value of object x. Let |Um′| and |Un′| be the number of m-class and n-class, respectively, where m,n∈{Id}. Let the misclassification cost MCm=mc[m,n]×|Um′| and MCn=mc[n,m]×|Un′|, respectively. In order to minimize the misclassification cost of the set U′, we assign one class d′(x) for all objects in U′. Let mc(U′,B) be the minimal value of MCm and MCn.(3)
For anyx∈U′, the assigned class d′(x)=n-class if mc(U′,B)=MCm and d′(x)=m-class if mc(U′,B)=MCn, where mc[m,n] is the cost of classifying an object of the m-class to the n-class.(4)
The decision value of the objectx depends on the value with the max number of d′(x). The misclassification cost of the object x is mc*(x). If d(x)=m and d′(x)=n, mc*(x)=mc[m,n]. Conversely, mc*(x)=mc[n,m] if d(x)=n and d′(x)=m. Therefore, we compute the average misclassification cost (AMC) as follows:
(11)mc¯(U,B)=∑x∈Umc*(x)|U|.(5)
The average total cost (ATC) is given by(12)ATC(U,B)=tc(B)+mc¯(U,B).The main aim of feature selection is to determine a minimal feature subset from a problem domain while retaining a suitably high accuracy in representing the original features [57]. In this context, rather than selecting a minimal feature subset, we choose a feature subset in order to minimize the average total cost. The minimal average total cost is given by
(13)ATC(U,B)=min{ATC(U,B′)∣B′⊆C}.The following example gives an intuitive understanding.Example 12.
A decision system with neighborhood boundaries is given by Tables4 and 5. Let C={a1,a2,a3}, B={a1,a2}, and D={d}. Let tc=[8,23,19] and mc=[0180600].Step 1.
n
B
(
x
i
) is the neighborhood of xi∈U, which is listed in Table 8. If xj∈nB(xi), the value at ith row and jth column is set to 1; otherwise, it is set to 0.Table 8
The neighborhood of objects onB{a1,a2}.
U
x
1
x
2
x
3
x
4
x
5
x
6
x
1
1
0
1
0
0
0
x
2
0
1
1
0
0
0
x
3
1
1
1
0
0
1
x
4
0
0
0
1
0
0
x
5
0
0
0
0
1
1
x
6
0
0
1
0
1
1Step 2.
Since the set ofnB(xi)⊆POSB({d}), the mc(nB(xi),B)=0, where i=1,2,4,5. The set of nB(x3)={x1,x2,x3,x6} has two kinds of classes, which should be adjusted to one class. Since mc(nB(x3),B)=min(60×1,180×3), for any x∈U′, d(x)= “y”. In the same way, in order to minimize the cost of mc(nB(x6),B)=min(60×2,180×1), we adjust all classes of elements in nB(x6) to “y”.Step 3.
We can obtain the new class of each test. We count the number of different classes of each test, which is listed in Table9.Table 9
The number of different classes.
d
x
1
x
2
x
3
x
4
x
5
x
6
y
2
2
4
0
1
2
n
0
0
0
1
1
1Step 4.
From Table9, we select dm with the maximal of d′(xi) as the class value of xi. The original decision attribute values d(x) and d′(x) are listed in Table 10. From this Table, we know d(x5)≠d′(x5) and d(x6)≠d′(x6). Therefore, the average misclassification cost mc¯(U,B)=(60+60)/6=20.Table 10
The difference of decision attributes.
U
x
1
x
2
x
3
x
4
x
5
x
6
d
′
(
x
)
Y
Y
Y
N
Y
Y
d
(
x
)
Y
Y
Y
N
N
NStep 5.
The average total cost isATC(U,B)=(8+23)+20=51.In order to search a minimal cost feature subset, we can define a problem to deal with this issue. Under the context of MEDS-TM, this problem will be called cost-sensitive feature selection problem or the minimal cost feature selection (FSMC) problem. Compared with the minimal test cost reduct (MTR) problem (see, e.g., [15, 16]), the FSMC problem should not only consider the test costs but also take the misclassification costs into account. When the misclassification costs are too large compared with test costs, the total test cost equals the total cost. In this case, the FSMC problem coincides with the MTR problem.


## 3.1. Covering-Based Rough Set with Measurement Errors

The covering-based rough set with measurement errors is a natural extension of the classical rough set. If all attributes are error free, the covering-based rough set model degenerates to the classical one. With the definition of the MEDS, a new neighborhood is defined as follows.Definition 5 (see [28]).
LetS=(U,C,d,V,I,n) be a decision system with measurement errors. Given B⊆C and xi∈U, the neighborhood of xi with reference to measurement errors on the feature set B is defined as
(6)nB(xi)={x∈U∣∀a∈B,|a(x)-a(xi)|≤2n(a)}.
That means the value of the measurement error of attribute a in [-n(a),+n(a)]. According to Definition 5, we know that the neighborhood nB(xi) is the intersection of multiple basic neighborhoods. Therefore, we obtain
(7)nB(xi)=⋂a∈B‍n{a}(xi).Although showing similarities, the neighborhood defined in [35] is essentially different from ours in two ways. First, a fixed boundary of neighborhood is used for different datasets. In contrast, the boundaries of neighborhood in our model are computed according to the values of attributes. Then, the uniform distribution is considered in [35]. In contrast, we introduce the normal distribution to our model. As mentioned earlier, the normal distribution is found to be applicable over almost the whole of science measurement.Normal distribution is a plausible distribution for measurement errors. In statistics, “3-sigma” rule states that over 99.73% (95.45%) of measurement data will fall within three (two) standard deviations of the mean [55]. We introduce this rule to our model and present a new neighborhood considering both the error distribution and the confidence interval. The proportion of small measurement errors is higher than large ones. Any value in the measurement that exceeds the three standard deviations from the mean should be discarded. Therefore, the measurement errors with no more than a difference of 3σ (2σ) should be viewed as a granule. In view of this, we introduce the relationship between the error boundary and the standard deviation in the following proposition.Proposition 6.
Let the error boundaryn(a)=3σ and Pr be the confidence level. one has about Pr=99.73% of cases within n(a)=±3σ.According to Proposition6, we have about Pr=99.73% of cases within n(a)=±3σ. If n(a)=2σ, we have about Pr=95.45% of cases within ±n(a). According to Definition 5, every item belongs to its own neighborhood. This is formally given by the following theorem.Theorem 7.
LetS=(U,C,d,V,I,n) be a decision system with measurement errors and B⊆C. The set {nB(xi)∣xi∈U} is a covering of U.Proof.
Given for allx∈U, for all a∈B, |a(x)-a(x)|=0, |a(x)-a(x)|≤2n(a), x∈nB(x).
Therefore, for allx∈U, nB(x)≠∅, and for any B⊆C, ⋃x∈U‍nB(x)=U.
Hence, the set{nB(xi)∣xi∈U} is a covering of U. This completes the proof.Now, we discuss the lower and upper approximations as well as the boundary region of rough set in the new model.Definition 8 (see [28]).
LetS=(U,C,d,V,I,n) be a decision system with measurement errors and NB a neighborhood relation on U, where B⊆C. We call 〈U,NB〉 a neighborhood approximation space. For arbitrary X⊆U, the lower approximation and the upper approximation of X in 〈U,NB〉 are defined as
(8)NB_(X)={xi∣xi∈U∧nB(xi)⊆X},NB¯(X)={xi∣xi∈U∧nB(xi)∩X≠∅}.
The positive region of {d} concerning B⊆C is defined as POSB({d})=⋃X∈U/{d}‍NB_(X) [42, 56].Definition 9.
LetS=(U,C,d,V,I,n) be a decision system with measurement errors, for all X⊆U, NB¯(X)⊇X⊇NB_(X). The boundary region of X in 〈U,NB〉 is defined as
(9)BNB(X)=NB¯(X)-NB_(X).Generally, a covering is produced by a neighborhood boundary. The inconsistent object in a neighborhood is defined as follows.Definition 10 (see [28]).
LetS=(U,C,d,V,I,n) be a decision system with measurement errors, B⊆C, and x,y∈U. In the set of nB(x), for all y∈nB(x) is called an inconsistent object if d(y)≠d(x). The set of inconsistent objects in nB(x) is
(10)icB(x)={y∈nB(x)∣d(y)≠d(x)}.
The number of inconsistent objects is denoted as |icB(x)|.Using a specific example, we explain the lower approximations, the upper approximations, the boundary regions, and the inconsistent objects of the neighborhood.Example 11.
A decision system with neighborhood boundaries is given in Tables4 and 5. Table 4 is a subtable of Table 1. Let U={x1,x2,…,x6}, C={a1,a2,a3}, and D={d}={Selector}, where a1 = Mcv, a2 = Alkphos, and a3 = Sgpt. nB(x) are listed in Table 6, where B takes values listed as column headers, and x takes values listed in each row. According to Definition 10, the inconsistent object in n{a1}(x1) is ic{a1}(x1)={x5,x6}.
In addition,U is divided into a set of equivalence classes by {d}. U/{d}={{x1,x2,x3},{x4,x5,x6}}. Let X1={x1,x2,x3} and X2={x4,x5,x6}. NB_(X) and NB¯(X) are listed in the first part and the second part of Table 7, respectively. Here, B takes values listed as column headers, and X takes values listed in each row.
The positive regions and the boundary regions ofU on different test sets can be computed from Table 7:(1)
POS{a1}({d})={x2,x4}, BN{a1}({d})={x1,x3,x5,x6},(2)
POS{a1,a2}({d})={x1,x2,x4,x5}, BN{a1,a2}({d})={x3,x6},(3)
POS{a1,a3}({d})={x1,x2,x3,x4,x5,x6}, BN{a1,a3}({d})=∅,(4)
{a1,a3} has the same approximating power as C.Table 4
A subtable of theLiver decision system.
Patient
a
1
a
2
a
3
d
x
1
0.31
0.23
0.08
y
x
2
0.14
0.38
0.23
y
x
3
0.25
0.40
0.40
y
x
4
0.60
0.46
0.51
n
x
5
0.41
0.64
0.62
n
x
6
0.35
0.50
0.75
nTable 5
An example of adaptive neighborhood boundary vector.
a
a
1
a
2
a
3
Neighborhood boundaries
±
0.069
±
0.087
±
0.086Table 6
The neighborhood of objects on different test sets.
x
{
a
1
}
{
a
1
,
a
2
}
{
a
1
,
a
3
}
{
a
1
,
a
2
,
a
3
}
x
1
{
x
1
,
x
3
,
x
5
,
x
6
}
{
x
1
,
x
3
}
{
x
1
}
{
x
1
}
x
2
{
x
2
,
x
3
}
{
x
2
,
x
3
}
{
x
2
,
x
3
}
{
x
2
,
x
3
}
x
3
{
x
1
,
x
2
,
x
3
,
x
6
}
{
x
1
,
x
2
,
x
3
,
x
6
}
{
x
2
,
x
3
}
{
x
2
,
x
3
}
x
4
{
x
4
}
{
x
4
}
{
x
4
}
{
x
4
}
x
5
{
x
1
,
x
5
,
x
6
}
{
x
5
,
x
6
}
{
x
5
,
x
6
}
{
x
5
,
x
6
}
x
6
{
x
1
,
x
3
,
x
5
,
x
6
}
{
x
3
,
x
5
,
x
6
}
{
x
5
,
x
6
}
{
x
5
,
x
6
}Table 7
Approximations of object subsets on different test sets.
X
{
a
1
}
{
a
1
,
a
2
}
{
a
1
,
a
3
}
{
a
1
,
a
2
,
a
3
}
N
B
_
(
X
)
X
1
{
x
2
}
{
x
1
,
x
2
}
{
x
1
,
x
2
,
x
3
}
{
x
1
,
x
2
,
x
3
}
X
2
{
x
4
}
{
x
4
,
x
5
}
{
x
4
,
x
5
,
x
6
}
{
x
4
,
x
5
,
x
6
}
N
B
¯
(
X
)
X
1
{
x
1
,
x
2
,
x
3
,
x
5
,
x
6
}
{
x
1
,
x
2
,
x
3
,
x
6
}
{
x
1
,
x
2
,
x
3
}
{
x
1
,
x
2
,
x
3
}
X
2
{
x
1
,
x
3
,
x
4
,
x
5
,
x
6
}
{
x
3
,
x
4
,
x
5
,
x
6
}
{
x
4
,
x
5
,
x
6
}
{
x
4
,
x
5
,
x
6
}


## 3.2. Minimal Cost Feature Selection Problem

In this work, we focus on cost-sensitive feature selection based on test costs and misclassification costs. Unlike reduction problems, we do not require any particular property of the decision system to be preserved. The objective of feature selection is to minimize the average total cost through considering a trade-off between test costs and misclassification costs. Cost-sensitive feature selection problem is called thefeature selection with minimal average total cost (FSMC) problem.Problem 1.
The FSMC problem:input: S=(U,C,d,V,I,n,tc,mc),output: R⊆C,optimization objective: minimize the average total cost (ATC).The FSMC problem is a generalization of classical minimal reduction problem. On the one hand, several factors should be considered such as the test costs and misclassification costs as well as normal distribution measurement errors. These factors are all intrinsic to data in real applications. On the other hand, the minimal average total cost is the optimization objective through considering the trade-off between the two kinds of costs. Compared with the accuracy, the average total cost is more general metric in data mining applications [36]. The following is a five-step process to compute the average total cost.(1)
LetB be a selected feature set. Given for all x∈U, we compute the neighborhood space nB(x).(2)
LetU′=nB(x) and let d(x) be the decision value of object x. Let |Um′| and |Un′| be the number of m-class and n-class, respectively, where m,n∈{Id}. Let the misclassification cost MCm=mc[m,n]×|Um′| and MCn=mc[n,m]×|Un′|, respectively. In order to minimize the misclassification cost of the set U′, we assign one class d′(x) for all objects in U′. Let mc(U′,B) be the minimal value of MCm and MCn.(3)
For anyx∈U′, the assigned class d′(x)=n-class if mc(U′,B)=MCm and d′(x)=m-class if mc(U′,B)=MCn, where mc[m,n] is the cost of classifying an object of the m-class to the n-class.(4)
The decision value of the objectx depends on the value with the max number of d′(x). The misclassification cost of the object x is mc*(x). If d(x)=m and d′(x)=n, mc*(x)=mc[m,n]. Conversely, mc*(x)=mc[n,m] if d(x)=n and d′(x)=m. Therefore, we compute the average misclassification cost (AMC) as follows:
(11)mc¯(U,B)=∑x∈Umc*(x)|U|.(5)
The average total cost (ATC) is given by(12)ATC(U,B)=tc(B)+mc¯(U,B).The main aim of feature selection is to determine a minimal feature subset from a problem domain while retaining a suitably high accuracy in representing the original features [57]. In this context, rather than selecting a minimal feature subset, we choose a feature subset in order to minimize the average total cost. The minimal average total cost is given by
(13)ATC(U,B)=min{ATC(U,B′)∣B′⊆C}.The following example gives an intuitive understanding.Example 12.
A decision system with neighborhood boundaries is given by Tables4 and 5. Let C={a1,a2,a3}, B={a1,a2}, and D={d}. Let tc=[8,23,19] and mc=[0180600].Step 1.
n
B
(
x
i
) is the neighborhood of xi∈U, which is listed in Table 8. If xj∈nB(xi), the value at ith row and jth column is set to 1; otherwise, it is set to 0.Table 8
The neighborhood of objects onB{a1,a2}.
U
x
1
x
2
x
3
x
4
x
5
x
6
x
1
1
0
1
0
0
0
x
2
0
1
1
0
0
0
x
3
1
1
1
0
0
1
x
4
0
0
0
1
0
0
x
5
0
0
0
0
1
1
x
6
0
0
1
0
1
1Step 2.
Since the set ofnB(xi)⊆POSB({d}), the mc(nB(xi),B)=0, where i=1,2,4,5. The set of nB(x3)={x1,x2,x3,x6} has two kinds of classes, which should be adjusted to one class. Since mc(nB(x3),B)=min(60×1,180×3), for any x∈U′, d(x)= “y”. In the same way, in order to minimize the cost of mc(nB(x6),B)=min(60×2,180×1), we adjust all classes of elements in nB(x6) to “y”.Step 3.
We can obtain the new class of each test. We count the number of different classes of each test, which is listed in Table9.Table 9
The number of different classes.
d
x
1
x
2
x
3
x
4
x
5
x
6
y
2
2
4
0
1
2
n
0
0
0
1
1
1Step 4.
From Table9, we select dm with the maximal of d′(xi) as the class value of xi. The original decision attribute values d(x) and d′(x) are listed in Table 10. From this Table, we know d(x5)≠d′(x5) and d(x6)≠d′(x6). Therefore, the average misclassification cost mc¯(U,B)=(60+60)/6=20.Table 10
The difference of decision attributes.
U
x
1
x
2
x
3
x
4
x
5
x
6
d
′
(
x
)
Y
Y
Y
N
Y
Y
d
(
x
)
Y
Y
Y
N
N
NStep 5.
The average total cost isATC(U,B)=(8+23)+20=51.In order to search a minimal cost feature subset, we can define a problem to deal with this issue. Under the context of MEDS-TM, this problem will be called cost-sensitive feature selection problem or the minimal cost feature selection (FSMC) problem. Compared with the minimal test cost reduct (MTR) problem (see, e.g., [15, 16]), the FSMC problem should not only consider the test costs but also take the misclassification costs into account. When the misclassification costs are too large compared with test costs, the total test cost equals the total cost. In this case, the FSMC problem coincides with the MTR problem.


## 4. Algorithms

We propose theδ-weighted heuristic algorithm to address the minimal cost feature selection problem. In order to evaluate the performance of a heuristic algorithm, an exhaustive algorithm is also needed. Exhaustive searches are also known as backtracking algorithms which look for every possible way to search for an optimal result. In this section, we review our exhaustive algorithm and propose a heuristic algorithm for this new feature selection problem.


### 4.1. The Backtracking Feature Selection Algorithm

We have proposed an exhaustive algorithm in [37] that is based on the backtracking. The backtracking algorithm can reduce the search space significantly through three pruning techniques. The backtracking feature selection algorithm is illustrated in Algorithm 1. In order to invoke this backtracking algorithm, several global variables should be explicitly initialized as follows:(1)
R=∅ is a feature subset with minimal average total cost,(2)
cmc=mc¯(U,R) is currently minimal average total cost,(3)
backtracking(R,0).Algorithm 1:A backtracking algorithm to the FSMC problem.
Input:  (U,C,d,{Va},{Ia},n,tc,mc), select tests R, current level test index lower bound l
Output:  A set of features R with ATC and cmc, they are global variables
Method:  backtracking
(
1
)   for (i=l; i<|C|; i + +)  do
(
2
)   B=R∪{ai}
//Pruning for too expensive test cost
(
3
)  if  (tc(B)>cmc)  then
(
4
)   continue;
(
5
)  end if
//Pruning for non-decreasing total cost and decreasing misclassification cost
(
6
)  if  ((ATC(U,B)≥ATC(U,R)) and (mc(B)<mc(R)) then
(
7
)   continue;
(
8
)  end if
(
9
)  if  (ATC(U,B)<cmc)) then
(
10
)   cmc=ATC(U,B); //Update the minimal total cost
(
11
)   R=B; //Update the set of features with minimal total cost
(
12
)  end if
(
13
)  backtracking (B,i+1);
(
14
)  end forA feature subset with the ATC will be stored inR at the end of the algorithm execution. Generally, the search space of the feature selection algorithm is 2|C|. In order to deal with this issue, there are a number of algorithms such as particle swarm optimization algorithms [58], genetic algorithms [1], and backtracking algorithms [59] in real applications.In Algorithm1, three pruning techniques are employed to reduce the search space in feature selection. Firstly, Line 1 indicates that the variable i starts from l instead of 0. Whenever we move forward through the recursive procedure, the lower bound is increased. And then, the second pruning technique is shown in Lines 3 through 5. In the real applications, the misclassification costs are nonnegative. In this way, the feature subsets B will be discarded if the test cost of B is larger than the current minimal average total cost (cmc). This technique can prune most branches. Finally, Lines 6 through 8 indicate that if the new feature subset produce a high cost along with decreasing misclassification cost, the current branch will never produce the feature subset with the minimal total cost.


### 4.2. Theδ-Weighted Heuristic Feature Selection Algorithm

In order to deal with the minimal feature selection problem, we design theδ-weighted heuristic feature selection algorithm. The algorithm framework is listed in Algorithm 2 containing two main steps. First, the algorithm adds the current best feature a to B according to the heuristic function f(B,ai,c(ai)) until B becomes a superreduct. Then, delete the feature a from B guaranteeing B with the current minimal total cost. In Algorithm 2, lines 5 and 7 contain the key code of the addition. Lines 10 to 14 show the steps of deletion.Algorithm 2:An addition-deletion cost-sensitive feature selection algorithm.
Input:  (U,C,d,{Va},{Ia},n,tc,mc)
Output:  A feature subset with minimal total cost
Method:
(
1
)  B=∅;
//Addition
(
2
)   CA=C;
(
3
)  while  (POSB(D)≠POSC(D)) do
(
4
)  for  each a∈CA  do
(
5
)   Compute f(B,a,c(a′));
(
6
)  end for
(
7
)  Select a′ with the maximal f(B,a′,c(a′));
(
8
)  B=B∪{a′}; CA=CA-{a′};
(
9
)   end while
//Deletion
(
10
)  while  (ATC(U,B)>ATC(U,B-{a})) do
(
11
)  for each a∈B do
(
12
)   Compute ATC(U,B-{a});
(
13
)  end for
(
14
)  Select a′ with the minimal ATC(U,B-{a′});
(
15
)  B=B-{a′};
(
16
)  end while
(
17
) return B;According to Definition10, the number of inconsistent objects |icB(x)| in neighborhood nB(x) is useful in evaluating the quality of a neighborhood block. Now, we introduce the following concepts.Definition 13 (see [35]).
LetS=(U,C,D,V,I,n) be a decision system with measurement errors, B⊆C, and x∈U. The total number of such objects with respect to U is
(14)ncB(S)=Σx∈U|icB(x)|,
and the positive region is
(15)pcB(S)=Σx∈POSC(D)|icB(x)|.According to Definition13, we know that B is a superreduct if and only if pcB(S)=0. Now, we propose the δ-weighted heuristic information function:
(16)f(B,ai,c(ai))=(pcB(S)-pcB∪{ai}(S))(1+δc(ai)),
where c(ai) is the test cost of the attribute ai, and δ≥0 is a user-specified parameter. In this heuristic information function, the attributes with lower cost have bigger significance. We can adjust the significance of test cost through different δ settings. If δ=0, test costs are essentially not considered.


## 4.1. The Backtracking Feature Selection Algorithm

We have proposed an exhaustive algorithm in [37] that is based on the backtracking. The backtracking algorithm can reduce the search space significantly through three pruning techniques. The backtracking feature selection algorithm is illustrated in Algorithm 1. In order to invoke this backtracking algorithm, several global variables should be explicitly initialized as follows:(1)
R=∅ is a feature subset with minimal average total cost,(2)
cmc=mc¯(U,R) is currently minimal average total cost,(3)
backtracking(R,0).Algorithm 1:A backtracking algorithm to the FSMC problem.
Input:  (U,C,d,{Va},{Ia},n,tc,mc), select tests R, current level test index lower bound l
Output:  A set of features R with ATC and cmc, they are global variables
Method:  backtracking
(
1
)   for (i=l; i<|C|; i + +)  do
(
2
)   B=R∪{ai}
//Pruning for too expensive test cost
(
3
)  if  (tc(B)>cmc)  then
(
4
)   continue;
(
5
)  end if
//Pruning for non-decreasing total cost and decreasing misclassification cost
(
6
)  if  ((ATC(U,B)≥ATC(U,R)) and (mc(B)<mc(R)) then
(
7
)   continue;
(
8
)  end if
(
9
)  if  (ATC(U,B)<cmc)) then
(
10
)   cmc=ATC(U,B); //Update the minimal total cost
(
11
)   R=B; //Update the set of features with minimal total cost
(
12
)  end if
(
13
)  backtracking (B,i+1);
(
14
)  end forA feature subset with the ATC will be stored inR at the end of the algorithm execution. Generally, the search space of the feature selection algorithm is 2|C|. In order to deal with this issue, there are a number of algorithms such as particle swarm optimization algorithms [58], genetic algorithms [1], and backtracking algorithms [59] in real applications.In Algorithm1, three pruning techniques are employed to reduce the search space in feature selection. Firstly, Line 1 indicates that the variable i starts from l instead of 0. Whenever we move forward through the recursive procedure, the lower bound is increased. And then, the second pruning technique is shown in Lines 3 through 5. In the real applications, the misclassification costs are nonnegative. In this way, the feature subsets B will be discarded if the test cost of B is larger than the current minimal average total cost (cmc). This technique can prune most branches. Finally, Lines 6 through 8 indicate that if the new feature subset produce a high cost along with decreasing misclassification cost, the current branch will never produce the feature subset with the minimal total cost.


## 4.2. Theδ-Weighted Heuristic Feature Selection Algorithm

In order to deal with the minimal feature selection problem, we design theδ-weighted heuristic feature selection algorithm. The algorithm framework is listed in Algorithm 2 containing two main steps. First, the algorithm adds the current best feature a to B according to the heuristic function f(B,ai,c(ai)) until B becomes a superreduct. Then, delete the feature a from B guaranteeing B with the current minimal total cost. In Algorithm 2, lines 5 and 7 contain the key code of the addition. Lines 10 to 14 show the steps of deletion.Algorithm 2:An addition-deletion cost-sensitive feature selection algorithm.
Input:  (U,C,d,{Va},{Ia},n,tc,mc)
Output:  A feature subset with minimal total cost
Method:
(
1
)  B=∅;
//Addition
(
2
)   CA=C;
(
3
)  while  (POSB(D)≠POSC(D)) do
(
4
)  for  each a∈CA  do
(
5
)   Compute f(B,a,c(a′));
(
6
)  end for
(
7
)  Select a′ with the maximal f(B,a′,c(a′));
(
8
)  B=B∪{a′}; CA=CA-{a′};
(
9
)   end while
//Deletion
(
10
)  while  (ATC(U,B)>ATC(U,B-{a})) do
(
11
)  for each a∈B do
(
12
)   Compute ATC(U,B-{a});
(
13
)  end for
(
14
)  Select a′ with the minimal ATC(U,B-{a′});
(
15
)  B=B-{a′};
(
16
)  end while
(
17
) return B;According to Definition10, the number of inconsistent objects |icB(x)| in neighborhood nB(x) is useful in evaluating the quality of a neighborhood block. Now, we introduce the following concepts.Definition 13 (see [35]).
LetS=(U,C,D,V,I,n) be a decision system with measurement errors, B⊆C, and x∈U. The total number of such objects with respect to U is
(14)ncB(S)=Σx∈U|icB(x)|,
and the positive region is
(15)pcB(S)=Σx∈POSC(D)|icB(x)|.According to Definition13, we know that B is a superreduct if and only if pcB(S)=0. Now, we propose the δ-weighted heuristic information function:
(16)f(B,ai,c(ai))=(pcB(S)-pcB∪{ai}(S))(1+δc(ai)),
where c(ai) is the test cost of the attribute ai, and δ≥0 is a user-specified parameter. In this heuristic information function, the attributes with lower cost have bigger significance. We can adjust the significance of test cost through different δ settings. If δ=0, test costs are essentially not considered.


## 5. Experiments

In this section, we try to answer the following questions by experimentation. The first two questions concern the backtracking algorithm, and the others concern the heuristic algorithm.(1)
Is the backtracking algorithm efficient?(2)
Is the heuristic algorithm appropriate for the minimal cost feature selection problem?(3)
How does the minimal total cost change for different misclassification cost settings?


### 5.1. Data Generation

Experiments are carried out on six standard datasets obtained from the UCI repository:Liver, Wdbc, Wpbc, Diab, Iono, and Credit. The first four datasets are from medical applications where Wpbc and Wdbc are the Wisconsin breast cancer prognosis and diagnosis datasets, respectively. The Liver and Diab are liver disorder and diabetes datasets, respectively. The iono stands for the Ionosphere, which is from physics applications. The Credit dataset is from commerce applications.Table11 shows a brief description of each dataset. Most datasets from the UCI library [60] have no intrinsic measurement errors, test costs, and misclassification costs. In order help to study the performance of the feature selection algorithm, we will create these data for experimentations.Table 11
Database information.
No.
Name
Domain
|
U
|
|
C
|
D
=
{
d
}
1
Liver
Clinic
345
6
Selector
2
Wdbc
Clinic
569
30
Diagnosis
3
Wpbc
Clinic
198
33
Outcome
4
Diab
Clinic
768
8
Class
5
Iono
Physics
351
34
Class
6
Credit
Commerce
690
15
ClassStep 1.
Each dataset should contain exactly one decision attribute and have no missing value. To make the data easier to handle, data items are normalized from their value into a range from 0 to 1.Step 2.
We produce then(a) for each original test according to (3). The n(a) is computed according to the value of databases without any subjectivity.
Three kinds of neighborhood boundaries of different databases are shown in Table12. These neighborhood boundaries are the maximal, the minimal, and the average neighborhood boundaries of all attributes, respectively. The precision of n(a) can be adjusted through Δ setting, and we set Δ to be 0.01 in our experiments.Table 12
Generated neighborhood boundaries for different databases.
Dataset
Minimal
Maximal
Average
Liver
0.022
0.130
±
0.058
Wdbc
0.012
0.080
±
0.046
Wpbc
0.022
0.112
±
0.062
Diab
0.018
0.118
±
0.062
Iono
0.090
0.174
±
0.122
Credit
0.002
0.112
±
0.044Step 3.
We produce test costs, which are always represented by positive integers. For anya∈U, c(a) is set to a random number in [12, 55] subject to the uniform distribution.Step 4.
The misclassification costs are always represented by nonnegative integers. We produce the matrix of misclassification costsmc as follows:(1)
mc[m,m]=0.(2)
mc[m,n] and mc[n,m] are set to a random number in [100,1000], respectively.


### 5.2. Efficiencies of the Two Algorithms

First, we study the efficiency of the backtracking algorithm. Specifically, experiments are undertaken with 100 different test cost settings. The search space and the number of steps for the backtracking algorithm are listed in Table13. From the results, we note that the pruning techniques significantly reduce the search space. Therefore, the pruning techniques are very effective.Table 13
Number of steps for the backtracking algorithm.
Dataset
Search space
Minimal steps
Maximal steps
Average steps
Liver
2
6
8
34
21.27
Wdbc
2
30
18
113
54.95
Wpbc
2
33
10
76
44.34
Diab
2
8
28
102
58.50
Iono
2
34
107
2814
663.41
Credit
2
15
105
2029
618.14Second, from Table13, we note that the number of steps does not simply rely on the size of the dataset. Wpbc is much larger than Credit; however, the number of steps is smaller. For some medium sized datasets, the backtracking algorithm is an effective method to obtain the optimal feature subset.Third, we compare the efficiency of the heuristic algorithm and the backtracking algorithm. Specifically, experiments are undertaken with 100 different test cost settings on six datasets listed in Table11. For the heuristic algorithm, λ is set to 1. The average and maximal run times for both algorithms are shown in Figure 1, where the unit of run time is on millisecond. From the results, we note that the heuristic algorithm is more stable in terms of run-time.Run time comparison: (a) maximal time and (b) average time.
(a)
(b)In a word, when we do not consider the run time, the backtracking algorithm is an effective method for many datasets. In real applications, when the run times of the backtracking algorithm are unacceptable, the heuristic algorithm must be employed.


### 5.3. Effectiveness of the Heuristic Algorithm

We letδ=1,2,…,9. The precision of n(a) can be adjusted through Δ setting, and we let Δ to be 0.01 on all datasets except Wdbc and Wpbc. The Δ=0.01 gets small neighborhood for Wdbc and Wpbc datasets; hence, we let Δ=0.05 for the two datasets. As mentioned earlier, the parameter Δ plays an important role. The data of our experiments come from real applications, and the errors are not given by the dataset. In this paper, we consider only some possible error ranges.The algorithm runs 100 times with different test cost settings and differentδ setting on all datasets. Figure 2 shows the results of finding optimal factors. From the results, we know that the test cost plays a key role in this heuristic algorithm. As shown in Figure 2, the performance of the algorithm is completely different for different settings of δ. Data for δ=0 are not included in the experiment results because respective results are incomparable to others. Figure 3 shows the average exceeding factors. These display the overall performance of the algorithm from a statistical perspective.Figure 2
Finding optimal factor.Figure 3
Average exceeding factor.From the results, we observe the following:(1)
the quality of the results is related to different datasets. It is because that the error range and heuristic information are all computed according to the values of dataset,(2)
the results of the finding optimal factor are acceptable on most of datasets exceptWdbc. The better results can be obtained through the smaller Δ; however, the number of selected features will be smaller,(3)
the average exceeding factor is less than 0.08 in most cases. In other words, the results are acceptable.


### 5.4. The Results for Different Cost Settings

In this section, we study the changes of the minimal total cost for different misclassification cost settings. Table14 is the optimal feature subset based on different misclassification costs for Wdbc dataset. The ratio of two misclassification costs is set 10 in this experiment.Table 14
The optimal feature subset based on different misclassification costs.
MisCost1
MisCost2
Test costs
Total cost
Feature subset
50
500
3.00
3.70
[
1
,
3
,
27
]
100
1000
4.00
4.35
[
1
,
3
,
15
,
29
]
150
1500
4.00
4.53
[
1
,
3
,
15
,
29
]
200
2000
4.00
4.70
[
1
,
3
,
15
,
29
]
250
2500
4.00
4.88
[
1
,
3
,
15
,
29
]
300
3000
5.00
5.00
[
1
,
12
,
15
,
27
]As shown in this table, when the misclassification costs are low, the algorithm avoids undertaking expensive tests.When the misclassification cost is too large compared with the test cost, the FSMC problem coincides with the MTR problem. Therefore, FSMC problem is a generalization of MTR problem.In the last row of Table14, the test cost of the subset [24, 31, 45, 55] equals the total cost; therefore, the misclassification cost is 0, and this feature subset is a reduct.The changes of test costs versus the average minimal total cost are also shown in Figure4. In real world, we could not select expensive tests when misclassification costs are low. Figure 4 shows this situation clearly. From the results, we observe the following.(1)
As shown in Figures4(a), 4(b), 4(e), and 4(f), when the test costs remain unchanged, the total costs increase linearly along with the increasing misclassification costs.(2)
If the misclassification costs are small enough, we may give up the test. Figure4(d) shows that when the misclassification costs are $30 and $300, the test cost is zero, and the total cost is the most expensive.(3)
As shown in Figures4(a) and 4(c), the total costs increase along with the increasing misclassification costs. The total costs remain the same when the total costs equal test costs.Test cost and average total cost: (a)Liver; (b) Wdbc; (c) Wpbc; (d) Diab; (e) Iono; (f) Credit.
(a)
(b)
(c)
(d)
(e)
(f)


## 5.1. Data Generation

Experiments are carried out on six standard datasets obtained from the UCI repository:Liver, Wdbc, Wpbc, Diab, Iono, and Credit. The first four datasets are from medical applications where Wpbc and Wdbc are the Wisconsin breast cancer prognosis and diagnosis datasets, respectively. The Liver and Diab are liver disorder and diabetes datasets, respectively. The iono stands for the Ionosphere, which is from physics applications. The Credit dataset is from commerce applications.Table11 shows a brief description of each dataset. Most datasets from the UCI library [60] have no intrinsic measurement errors, test costs, and misclassification costs. In order help to study the performance of the feature selection algorithm, we will create these data for experimentations.Table 11
Database information.
No.
Name
Domain
|
U
|
|
C
|
D
=
{
d
}
1
Liver
Clinic
345
6
Selector
2
Wdbc
Clinic
569
30
Diagnosis
3
Wpbc
Clinic
198
33
Outcome
4
Diab
Clinic
768
8
Class
5
Iono
Physics
351
34
Class
6
Credit
Commerce
690
15
ClassStep 1.
Each dataset should contain exactly one decision attribute and have no missing value. To make the data easier to handle, data items are normalized from their value into a range from 0 to 1.Step 2.
We produce then(a) for each original test according to (3). The n(a) is computed according to the value of databases without any subjectivity.
Three kinds of neighborhood boundaries of different databases are shown in Table12. These neighborhood boundaries are the maximal, the minimal, and the average neighborhood boundaries of all attributes, respectively. The precision of n(a) can be adjusted through Δ setting, and we set Δ to be 0.01 in our experiments.Table 12
Generated neighborhood boundaries for different databases.
Dataset
Minimal
Maximal
Average
Liver
0.022
0.130
±
0.058
Wdbc
0.012
0.080
±
0.046
Wpbc
0.022
0.112
±
0.062
Diab
0.018
0.118
±
0.062
Iono
0.090
0.174
±
0.122
Credit
0.002
0.112
±
0.044Step 3.
We produce test costs, which are always represented by positive integers. For anya∈U, c(a) is set to a random number in [12, 55] subject to the uniform distribution.Step 4.
The misclassification costs are always represented by nonnegative integers. We produce the matrix of misclassification costsmc as follows:(1)
mc[m,m]=0.(2)
mc[m,n] and mc[n,m] are set to a random number in [100,1000], respectively.


## 5.2. Efficiencies of the Two Algorithms

First, we study the efficiency of the backtracking algorithm. Specifically, experiments are undertaken with 100 different test cost settings. The search space and the number of steps for the backtracking algorithm are listed in Table13. From the results, we note that the pruning techniques significantly reduce the search space. Therefore, the pruning techniques are very effective.Table 13
Number of steps for the backtracking algorithm.
Dataset
Search space
Minimal steps
Maximal steps
Average steps
Liver
2
6
8
34
21.27
Wdbc
2
30
18
113
54.95
Wpbc
2
33
10
76
44.34
Diab
2
8
28
102
58.50
Iono
2
34
107
2814
663.41
Credit
2
15
105
2029
618.14Second, from Table13, we note that the number of steps does not simply rely on the size of the dataset. Wpbc is much larger than Credit; however, the number of steps is smaller. For some medium sized datasets, the backtracking algorithm is an effective method to obtain the optimal feature subset.Third, we compare the efficiency of the heuristic algorithm and the backtracking algorithm. Specifically, experiments are undertaken with 100 different test cost settings on six datasets listed in Table11. For the heuristic algorithm, λ is set to 1. The average and maximal run times for both algorithms are shown in Figure 1, where the unit of run time is on millisecond. From the results, we note that the heuristic algorithm is more stable in terms of run-time.Run time comparison: (a) maximal time and (b) average time.
(a)
(b)In a word, when we do not consider the run time, the backtracking algorithm is an effective method for many datasets. In real applications, when the run times of the backtracking algorithm are unacceptable, the heuristic algorithm must be employed.


## 5.3. Effectiveness of the Heuristic Algorithm

We letδ=1,2,…,9. The precision of n(a) can be adjusted through Δ setting, and we let Δ to be 0.01 on all datasets except Wdbc and Wpbc. The Δ=0.01 gets small neighborhood for Wdbc and Wpbc datasets; hence, we let Δ=0.05 for the two datasets. As mentioned earlier, the parameter Δ plays an important role. The data of our experiments come from real applications, and the errors are not given by the dataset. In this paper, we consider only some possible error ranges.The algorithm runs 100 times with different test cost settings and differentδ setting on all datasets. Figure 2 shows the results of finding optimal factors. From the results, we know that the test cost plays a key role in this heuristic algorithm. As shown in Figure 2, the performance of the algorithm is completely different for different settings of δ. Data for δ=0 are not included in the experiment results because respective results are incomparable to others. Figure 3 shows the average exceeding factors. These display the overall performance of the algorithm from a statistical perspective.Figure 2
Finding optimal factor.Figure 3
Average exceeding factor.From the results, we observe the following:(1)
the quality of the results is related to different datasets. It is because that the error range and heuristic information are all computed according to the values of dataset,(2)
the results of the finding optimal factor are acceptable on most of datasets exceptWdbc. The better results can be obtained through the smaller Δ; however, the number of selected features will be smaller,(3)
the average exceeding factor is less than 0.08 in most cases. In other words, the results are acceptable.


## 5.4. The Results for Different Cost Settings

In this section, we study the changes of the minimal total cost for different misclassification cost settings. Table14 is the optimal feature subset based on different misclassification costs for Wdbc dataset. The ratio of two misclassification costs is set 10 in this experiment.Table 14
The optimal feature subset based on different misclassification costs.
MisCost1
MisCost2
Test costs
Total cost
Feature subset
50
500
3.00
3.70
[
1
,
3
,
27
]
100
1000
4.00
4.35
[
1
,
3
,
15
,
29
]
150
1500
4.00
4.53
[
1
,
3
,
15
,
29
]
200
2000
4.00
4.70
[
1
,
3
,
15
,
29
]
250
2500
4.00
4.88
[
1
,
3
,
15
,
29
]
300
3000
5.00
5.00
[
1
,
12
,
15
,
27
]As shown in this table, when the misclassification costs are low, the algorithm avoids undertaking expensive tests.When the misclassification cost is too large compared with the test cost, the FSMC problem coincides with the MTR problem. Therefore, FSMC problem is a generalization of MTR problem.In the last row of Table14, the test cost of the subset [24, 31, 45, 55] equals the total cost; therefore, the misclassification cost is 0, and this feature subset is a reduct.The changes of test costs versus the average minimal total cost are also shown in Figure4. In real world, we could not select expensive tests when misclassification costs are low. Figure 4 shows this situation clearly. From the results, we observe the following.(1)
As shown in Figures4(a), 4(b), 4(e), and 4(f), when the test costs remain unchanged, the total costs increase linearly along with the increasing misclassification costs.(2)
If the misclassification costs are small enough, we may give up the test. Figure4(d) shows that when the misclassification costs are $30 and $300, the test cost is zero, and the total cost is the most expensive.(3)
As shown in Figures4(a) and 4(c), the total costs increase along with the increasing misclassification costs. The total costs remain the same when the total costs equal test costs.Test cost and average total cost: (a)Liver; (b) Wdbc; (c) Wpbc; (d) Diab; (e) Iono; (f) Credit.
(a)
(b)
(c)
(d)
(e)
(f)


## 6. Conclusions

In this paper, we built a new covering-based rough set model with normal distribution measurement errors. A new cost-sensitive feature selection problem is defined based on this model. This new problem has a wide application area for two reasons. One is that the resource that one can afford is often limited. The other is that data with measurement errors under considered is ubiquitous. A backtracking algorithm and a heuristic algorithm are designed. Experimental results indicate the efficiency of the backtracking algorithm and the effectiveness of the heuristic algorithm.With regard to future research, much work needs to be undertaken. First, other realistic data models with neighborhood boundaries can be built. Second, the current implementation of the algorithm deals only with binary class problems that is the principal limitation. In the future, the extending algorithm needs to be proposed to cope with multivariate class problems. A third point to be considered in future research is that one can borrow ideas from [61–63] to design other exhaustive and heuristic algorithms. In summary, this study suggests new research trends concerning covering-based rough set theory, feature selection problem, and cost-sensitive learning.



---

*Source: 754698-2013-04-15.xml*