# Test-Cost-Sensitive Attribute Reduction of Data with Normal Distribution Measurement Errors

Authors: Hong Zhao; Fan Min; William Zhu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The measurement error with normal distribution is universal in applications. Generally, smaller measurement error requires better instrument and higher test cost. In decision making, we will select an attribute subset with appropriate measurement error to minimize the total test cost. Recently, error-range-based covering rough set with uniform distribution error was proposed to investigate this issue. However, the measurement errors satisfy normal distribution instead of uniform distribution which is rather simple for most applications. In this paper, we introduce normal distribution measurement errors to covering-based rough set model and deal with test-cost-sensitive attribute reduction problem in this new model. The major contributions of this paper are fourfold. First, we build a new data model based on normal distribution measurement errors. Second, the covering-based rough set model with measurement errors is constructed through the “3-sigma” rule of normal distribution. With this model, coverings are constructed from data rather than assigned by users. Third, the test-cost-sensitive attribute reduction problem is redefined on this covering-based rough set. Fourth, a heuristic algorithm is proposed to deal with this problem. The experimental results show that the algorithm is more effective and efficient than the existing one. This study suggests new research trends concerning cost-sensitive learning.


---

## Body

## 1.  Introduction

The measurement error is the difference between a measurement value and its true value. It can come from the measuring instrument, from the item being measured, from the environment, from the operator, and from other sources [1]. As a plausible distribution for measurement errors, the normal distribution was put forward by Gauss in 1809. In fact, normal distribution is found to be applicable over almost the whole of science and engineering measurement. In data mining applications, the data model based on measurement errors is an important form of uncertain data (see, e.g., [2–4]).Test costs refer to time, money, or other resources spent in obtaining data items related to some object [5–10]. There are a number of measurement methods with different test costs to obtain a data item. Generally, higher test cost is required to obtain data with smaller measurement error. In data mining applications, we will select an attribute subset with appropriate measurement error to minimize the total test cost and at the same time preserve necessary information of the original decision system.An attribute reduct is a subset of attributes that are jointly sufficient and individually necessary for preserving a particular property of the given information table [11]. It is a key problem of rough set theory and has attracted much attention in recent years (see, e.g., [12–16]). As a generalization of attribute reduction, test-cost-sensitive attribute reduction [6] focuses on selecting a set of tests to satisfy a minimal test cost criterion.Recently, error-range-based covering rough set [4] was introduced to address error ranges. This theory is based on both covering-based rough set [17–23] and neighborhood rough set [24–28]. Moreover, in the new theory, the test-cost-sensitive attribute reduction problem deals with numeric data instead of nominal ones. Therefore, the problem is more challenging than the one defined in [6]. However, error-range-based covering rough set considers only uniform distribution errors, which are rather unrealistic.In this paper, we introduce normal distribution to build a new model of covering-based rough set to address normal distribution measurement errors (NDME) according to the “3-sigma" rule. The major contributions of this paper are fourfold. First, we introduce normal distribution to build a new data model based on measurement errors. The error range is computed according to the values of attributes instead of the fixed error range for different datasets. Second, we build the computational model, namely, the covering-based rough set with normal distribution measurement errors. Third, the minimal test cost attribute reduction problem is redefined in the new model. Fourth, we propose a heuristic algorithm to address the reduction problem. Specifically, aδ-weighted heuristic reduction algorithm is designed, where attribute significance is adjusted by δ-weighted test cost.Ten open datasets from the University of California-Irvine (UCI) library are employed to study the performance and effectiveness of our algorithm. We adopt three measures to evaluate the performance of the reduction algorithms from a statistical viewpoint. Experiments undertaken with open source software cost-sensitive rough sets (Coser) [29] validate the performance of this algorithm. Experimental results show that our algorithm can generate a minimal test cost reduct in most cases. At the same time, the proposed algorithm can achieve better performance and efficiency than the existing one [4].The rest of the paper is organized as follows: Section2 presents the data models with measurement errors and test costs, respectively. Section 3 describes the computational model, namely, covering-based rough set model with normal distribution measurement errors. The minimal test cost reduct problem under the new model is also defined in this section. Next, Section 4 presents a δ-weighted heuristic reduction algorithm and a competition approach. Experiment results and comparison with the existing work are discussed in Section 5. Finally, conclusions are drawn in Section 6.


## 2. Data Models

This section presents data models. First, we propose a decision system with normal distribution measurement errors, which is also called NEDS for brevity. Then, we introduce test costs to NEDS and define test-cost-sensitive decision systems with NDME.


### 2.1. Normal Distribution

Normal distribution is an important type in science and engineering measurement. It can be described by the probability density function(1)f(x)=12πσ2e-(x-μ)2/2σ2,
where the parameter μ is the mean which gives the location of the distribution and the parameter σ2 is the variance which gives the scale of the distribution.The cumulative distribution function (CDF)F(x) of a random variable is the probability of a value less than or equal to some value x:
(2)F(x)=∫-∞x‍f(x)dx,
where x∈ℝ. For a random variable X,
(3)F(x)=Pr(X≤x),
where the right-hand side represents the probability that the random variable X takes on a value less than or equal to x. The standard normal distribution appears with μ=0 and σ2=1. The equation becomes
(4)f(z)=12πe(-z2)/2.For a normal distribution, about 68.27% of values drawn from a normal distribution are within one standard deviation away from the mean; about 95.45% of the values lie within two standard deviations; nearly all values (99.73%) lie within 3 standard deviations of the mean, that is, “3-sigma" rule [30]. We use the following example to explain the relationship between standard deviation and confidence interval.Example 1.
Let standard deviation be 0.01, and let the mean be 0;  then we know that about 99% of the measurement errors are from −0.03 to+0.03.


### 2.2. Decision Systems with Measurement Errors

We introduce normal distribution measurement errors into our model [31] to make the model more realistic.Definition 2.
A decision system with normal distribution measurement errors (NEDS)S is the 6-tuple:
(5)S=(U,C,D,V={Va∣a∈C∪D},I={Ia∣a∈C∪D},n),
where U is the nonempty set called a universe and C and D are the nonempty sets of variables called conditional attributes and decision attributes, respectively. Va is the set of values for each a∈C∪D, and Ia:U→Va is an information function for each a∈C∪D. n:C→ℝ+∪{0} is the maximum value of measurement error. +n(a) and -n(a) are the upper confidence limit (UCL) and the lower confidence limit (LCL) of a∈C, respectively.Definition 3.
LettingS=(U,C,D,V,I,n) be a NEDS, the error range of attribute a is defined as
(6)n(a)=Λe(a),
where
(7)e(a)=Δ∑i=1ma(xi)m,
where Δ∈[0,1] is a user-specified parameter, a(xi) is the ith instance value of a∈C, i∈[1,m], and m is the number of instances. The precision of e(a) can be adjusted through Δ setting.From Definition3 we can see that the decision system with normal distribution measurement errors is a generalization of the decision system and the decision system with error range (DS-ER) (see, e.g., [4]). If all attributes are error free, that is Λ=0, a NEDS degrades to a DS. If the error range is a fixed value, that is Λ=1, a NEDS degrades to a DS-ER.We introduce how to deal with the abnormal value of measurement error. In applications, if the repeated measurement data satisfy(8)|xi-x-|>3σ,(i=1,2,…,N),
the xi would be considered as an abnormal value and be rejected, where xi is the ith measurement value and x- is the mean of all measurement values. This is the Pauta criterion of measurement error theory.Now, we investigate the relationship between the limit of confidence interval and the standard deviation in the following proposition.Proposition 4.
Let-n(a) and +n(a) be LCL and UCL, respectively, and let Pr be the confidence level. One has  the upper limit of confidence interval
(9)n(a)=3σ,
where Pr=99.73%.The value of exceed the three deviations is an abnormal error, which needs to be identified and removed from consideration. The standard normal distribution is a special case of the normal distribution. The limit of confidence interval is investigated in the following proposition.Proposition 5.
Let-n(a) and +n(a) be LCL and UCL of standard normal distribution measurement errors, respectively. One has
(10)n(a)=3.Proof.
The standard normal distribution is given by takingμ=0 mean and σ2=1 in a general normal distribution. n(a)=3σ, n(a)>0. Therefore (10) holds.In Definition3, a key parameter Λ is an adjusting factor. Now we introduce it by the following proposition.Proposition 6.
Let-n(a) and +n(a) be LCL and UCL of a∈C, respectively. Confidence intervals are stated at the Pr confidence level, and n(a)=3σ. According to (3), one has
(11)Pr(|x|≤n(a))=2F(n(a))-1.According to (3) and Proposition 6, if 2/3≤Λ<1, we have 2σ≤n(a)<3σ, 95.45%≤Pr<99.73%; if 1/3<Λ<2/3, we have σ<n(a)<2σ, 68.27%<Pr<95.45%, and if 0<Λ≤1/3, we have 0<n(a)≤σ, 0%<Pr≤68.27%.Large error ranges are pronounced with shorter reaction time than those with smaller error ranges. Small error ranges are pronounced with higher classification accuracies than those with larger ones. Generally, smaller measurement error requires better instrument and higher test cost. In many applications, it is impossible or unnecessary to distinguish objects or elements with small error range in a universe. One can adjust the size of the error range through theΛ setting to meet different requirements.


### 2.3. Test-Cost-Independent Decision System with Normal Distribution Measurement Errors

We introduce test costs to the data model. Now, we discuss the new model as follows.Definition 7.
A test-cost-independent decision system with normal distribution measurement errors (TCI-NEDS)S is the 7-tuple:
(12)S=(U,C,D,V,I,n,c),
where U,C,D,V,I, and n have the same meanings as in a NEDS, and c:C→ℝ+∪{0} is the test cost function. Test costs are independent of one another, that is, c(B)=∑a∈B‍c(a) for any B⊆C.Note that in this model, test costs are not applicable to decision attributes.In order to process and compare, the values of conditional attributes are normalized from their value into a range from 0 to 1 through the linear function(13)y=(x-min)(max-min),
where max and min are the maximal and minimal values of the attribute and x and y are the initial value and the normalized value, respectively.Table1 presents a decision system of Iris, whose conditional attributes are normalized values. Where C={SL, SW, PL, PW}, D={Class}, and U={x1,x2,…,x150}.Table 1
An example of numerical value attribute decision table.
Plant
SL
SW
PL
PW
Class
x
1
0.23529
0.77273
0.14286
0.04762
Setosa
x
2
0.29412
0.72727
0.11905
0.04762
Setosa
x
3
0.35294
0.09091
0.38095
0.42857
Versicolor
x
4
0.64706
0.31818
0.52381
0.52381
Versicolor
x
5
0.41176
0.31818
0.50000
0.42857
Versicolor
⋮
⋮
⋮
⋮
⋮
⋮
x
149
0.58824
0.54545
0.85714
1.00000
Virginica
x
150
0.44118
0.27273
0.64286
0.71429
Virginica


## 2.1. Normal Distribution

Normal distribution is an important type in science and engineering measurement. It can be described by the probability density function(1)f(x)=12πσ2e-(x-μ)2/2σ2,
where the parameter μ is the mean which gives the location of the distribution and the parameter σ2 is the variance which gives the scale of the distribution.The cumulative distribution function (CDF)F(x) of a random variable is the probability of a value less than or equal to some value x:
(2)F(x)=∫-∞x‍f(x)dx,
where x∈ℝ. For a random variable X,
(3)F(x)=Pr(X≤x),
where the right-hand side represents the probability that the random variable X takes on a value less than or equal to x. The standard normal distribution appears with μ=0 and σ2=1. The equation becomes
(4)f(z)=12πe(-z2)/2.For a normal distribution, about 68.27% of values drawn from a normal distribution are within one standard deviation away from the mean; about 95.45% of the values lie within two standard deviations; nearly all values (99.73%) lie within 3 standard deviations of the mean, that is, “3-sigma" rule [30]. We use the following example to explain the relationship between standard deviation and confidence interval.Example 1.
Let standard deviation be 0.01, and let the mean be 0;  then we know that about 99% of the measurement errors are from −0.03 to+0.03.


## 2.2. Decision Systems with Measurement Errors

We introduce normal distribution measurement errors into our model [31] to make the model more realistic.Definition 2.
A decision system with normal distribution measurement errors (NEDS)S is the 6-tuple:
(5)S=(U,C,D,V={Va∣a∈C∪D},I={Ia∣a∈C∪D},n),
where U is the nonempty set called a universe and C and D are the nonempty sets of variables called conditional attributes and decision attributes, respectively. Va is the set of values for each a∈C∪D, and Ia:U→Va is an information function for each a∈C∪D. n:C→ℝ+∪{0} is the maximum value of measurement error. +n(a) and -n(a) are the upper confidence limit (UCL) and the lower confidence limit (LCL) of a∈C, respectively.Definition 3.
LettingS=(U,C,D,V,I,n) be a NEDS, the error range of attribute a is defined as
(6)n(a)=Λe(a),
where
(7)e(a)=Δ∑i=1ma(xi)m,
where Δ∈[0,1] is a user-specified parameter, a(xi) is the ith instance value of a∈C, i∈[1,m], and m is the number of instances. The precision of e(a) can be adjusted through Δ setting.From Definition3 we can see that the decision system with normal distribution measurement errors is a generalization of the decision system and the decision system with error range (DS-ER) (see, e.g., [4]). If all attributes are error free, that is Λ=0, a NEDS degrades to a DS. If the error range is a fixed value, that is Λ=1, a NEDS degrades to a DS-ER.We introduce how to deal with the abnormal value of measurement error. In applications, if the repeated measurement data satisfy(8)|xi-x-|>3σ,(i=1,2,…,N),
the xi would be considered as an abnormal value and be rejected, where xi is the ith measurement value and x- is the mean of all measurement values. This is the Pauta criterion of measurement error theory.Now, we investigate the relationship between the limit of confidence interval and the standard deviation in the following proposition.Proposition 4.
Let-n(a) and +n(a) be LCL and UCL, respectively, and let Pr be the confidence level. One has  the upper limit of confidence interval
(9)n(a)=3σ,
where Pr=99.73%.The value of exceed the three deviations is an abnormal error, which needs to be identified and removed from consideration. The standard normal distribution is a special case of the normal distribution. The limit of confidence interval is investigated in the following proposition.Proposition 5.
Let-n(a) and +n(a) be LCL and UCL of standard normal distribution measurement errors, respectively. One has
(10)n(a)=3.Proof.
The standard normal distribution is given by takingμ=0 mean and σ2=1 in a general normal distribution. n(a)=3σ, n(a)>0. Therefore (10) holds.In Definition3, a key parameter Λ is an adjusting factor. Now we introduce it by the following proposition.Proposition 6.
Let-n(a) and +n(a) be LCL and UCL of a∈C, respectively. Confidence intervals are stated at the Pr confidence level, and n(a)=3σ. According to (3), one has
(11)Pr(|x|≤n(a))=2F(n(a))-1.According to (3) and Proposition 6, if 2/3≤Λ<1, we have 2σ≤n(a)<3σ, 95.45%≤Pr<99.73%; if 1/3<Λ<2/3, we have σ<n(a)<2σ, 68.27%<Pr<95.45%, and if 0<Λ≤1/3, we have 0<n(a)≤σ, 0%<Pr≤68.27%.Large error ranges are pronounced with shorter reaction time than those with smaller error ranges. Small error ranges are pronounced with higher classification accuracies than those with larger ones. Generally, smaller measurement error requires better instrument and higher test cost. In many applications, it is impossible or unnecessary to distinguish objects or elements with small error range in a universe. One can adjust the size of the error range through theΛ setting to meet different requirements.


## 2.3. Test-Cost-Independent Decision System with Normal Distribution Measurement Errors

We introduce test costs to the data model. Now, we discuss the new model as follows.Definition 7.
A test-cost-independent decision system with normal distribution measurement errors (TCI-NEDS)S is the 7-tuple:
(12)S=(U,C,D,V,I,n,c),
where U,C,D,V,I, and n have the same meanings as in a NEDS, and c:C→ℝ+∪{0} is the test cost function. Test costs are independent of one another, that is, c(B)=∑a∈B‍c(a) for any B⊆C.Note that in this model, test costs are not applicable to decision attributes.In order to process and compare, the values of conditional attributes are normalized from their value into a range from 0 to 1 through the linear function(13)y=(x-min)(max-min),
where max and min are the maximal and minimal values of the attribute and x and y are the initial value and the normalized value, respectively.Table1 presents a decision system of Iris, whose conditional attributes are normalized values. Where C={SL, SW, PL, PW}, D={Class}, and U={x1,x2,…,x150}.Table 1
An example of numerical value attribute decision table.
Plant
SL
SW
PL
PW
Class
x
1
0.23529
0.77273
0.14286
0.04762
Setosa
x
2
0.29412
0.72727
0.11905
0.04762
Setosa
x
3
0.35294
0.09091
0.38095
0.42857
Versicolor
x
4
0.64706
0.31818
0.52381
0.52381
Versicolor
x
5
0.41176
0.31818
0.50000
0.42857
Versicolor
⋮
⋮
⋮
⋮
⋮
⋮
x
149
0.58824
0.54545
0.85714
1.00000
Virginica
x
150
0.44118
0.27273
0.64286
0.71429
Virginica


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

Rough set theory is a powerful tool for dealing with uncertain knowledge in information systems [32]. It has been successfully applied to feature selection [33, 34], rule extraction [35–37], uncertainty reasoning [38, 39], decision evaluation [40, 41], granular computing [42–45], and so forth. Recently, covering-based rough set has attracted much research interest with significant achievements in both theory and application.The concept of neighborhood (see, e.g., [46–48]) has been applied to define different types of covering-based rough set [16–18]. From the different viewpoints, a neighborhood is called an information granule or a covering element. Figure 1 illustrates the neighborhoods of x in a two-dimensional real space [25]. For this type of neighborhood rough set model, the distance parameter δ is a user-specified parameter. Objects with a distance less than δ are viewed as neighbors. Recently, a new neighborhood is defined in [4]. The size of the neighborhood depends on error ranges of tests, and more objects fall into the neighborhood of xi for wider error ranges. Figure 2 illustrates this two-dimensional neighborhood.Figure 1
Conventional neighborhoods.Figure 2
Two-dimensional neighborhood with error ranges.In this section, we introduce normal distribution measurement errors to covering-based rough set. The new model is called covering-based rough set with normal distribution measurement errors. As mentioned early, if we do not consider errors, this mode degenerates to the classical decision system. Therefore, this model is a natural extension of classical one. Test-cost-sensitive attribute reduction problem on the covering-based rough set model with NDME is also proposed in this section.


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

According to “3-sigma" rule, we present a new model considering both error distribution and confidence interval. According to Definition2, we have defined a neighborhood in [31] as follows.Definition 8.
LetS=(U,C,D,V,I,n) be a decision system with normal distribution measurement errors. Given xi∈U and B⊆C, the neighborhood of xi with respect to normal distribution measurement errors on attribute set B is defined as
(14)nB(xi)={x∈U∣∀a∈B,|a(x)-a(xi)|≤2n(a)},
where n(a)=Λe(a) is the error boundary. It represents the error value of a in [-n(a),+n(a)].Measurement errors with no more than a difference of2n(a) should be viewed as the family of neighborhood granules. We explain why n(a) instead of e(a) was employed in (14) as the maximal distance. Although the value of error is within a certain range, there are significant differences among confidence intervals. As mentioned earlier, “3-sigma" rule states that for a normal distribution, different proportion values lie within different standard deviations of the mean. In particularly, the proportion is very close to 0 if data is more than three standard deviations from the mean.Therefore, measurement errors with no more than a difference ofn(a)=Λe(a) should be viewed as the family of neighborhood granules. Naturally, the size of the neighborhood depends on error ranges of tests and adjusting factor. Figure 3 shows the different sizes of neighborhood based on ±1σ, ±2σ, and ±3σ.Figure 3
Two-dimensional neighborhood based on different standard deviations.In the new model, the lower and upper approximations are defined as follows.Definition 9 (see [31]).
LetS=(U,C,D,V,I,n) be a decision system with normal distribution measurement errors, and let NB be a neighborhood relation induced by B⊆C. For any X⊆U, the lower and upper approximations of X in a neighborhood approximation space 〈U,NB〉 are defined as
(15)NB_(X)={xi∣xi∈U∧nB(xi)⊆X},NB-(X)={xi∣xi∈U∧nB(xi)∩X≠∅}.∀
X
⊆
U, NB-(X)⊇X⊇NB_(X). The boundary region of X in 〈U,NB〉 is defined as
(16)BNB(X)=NB-(X)-NB_(X).
The positive region of D with respect to B⊆C is defined as POSB(D)=⋃X∈U/D‍NB_(X) [49, 50].


### 3.2. Test-Cost-Sensitive Attribute Reduct Problem

Attribute reduction is a successful technique to remove redundant data and facilitate the mining task. A number of definitions of relative reducts exist [25, 38, 51, 52] for different rough set models. In this section, we define test-cost-sensitive attribute reduction on the covering-based rough set model with NDME.A minimal test cost reduct problem proposed in [6] can be redefined as follows. The problem of finding such a reduct is called the minimal test cost reduct problem.Problem 1.The minimal test cost reduct problem.Input: S=(U,C,D,V,I,n,c);Output: B⊆C;Constraint: POSB(D)=POSC(D);Optimization objective: min(c(B)).Compared with the classical minimal reduction problem, there are several differences as follows. The first is the input, where the test costs and measurement errors are the external information. The second is the optimization objective, which is to minimize the test cost instead of the number of features. We can adopt the addition-deletion strategy [15] to design our heuristic reduction algorithm.In order to address the constraint of the problem, we have defined an inconsistent object in [4]. Here we redefine it as follows.Definition 10.
LetS=(U,C,D,V,I,n) be a decision system with normal distribution measurement errors, B⊆C, and x∈U. In nB(x), any x*∈nB(x) is called an inconsistent object if D(x*)≠D(x). The set of inconsistent objects in nB(x) is
(17)icB(x)={x*∈nB(x)∣D(x*)≠D(x)}.We can evaluate the characteristics of the neighborhood block through the number of inconsistent objects, namely,|icB(x)|. From Definition 10 we know that given B⊆C, x∈POSC(D) if and only if icB(x)=∅. Consequently, the icB(x) is an important parameter when we compute the positive region. Therefore, the following proposition can be used as an alternative definition of a reduct.Proposition 11.
LetS=(U,C,D,V,I,n) be a NEDS. Any R⊆C is a decision-relative reduct if and only if(1)
∀x∈POSC(D),icR(x)=∅,(2)
∀x∈R,∃x∈POSC(D),st. icR-{a}(x)≠∅.Sometimes we are interested in minimal reduction or minimal test cost reduct (see, e.g., [6]). In this work, we focus on finding reducts with minimal test cost, that is, test-cost-sensitive attribute reducts. Because the TCI-NEDS is a natural extension of NEDS, concepts in the NEDS are also applicable to the TCI-NEDS. We introduce the following definition.Definition 12.
LetRed(S) denote the set of all reducts of a TCI-NEDS S=(U,C,D,V,I,n,c). Any R∈Red(S) where c(R)=min{c(R′)∣R′∈Red(S)} is called a minimal test cost reduct.According to this definition, we should compute all reducts firstly. Consequently, exhaustive algorithms are needed to address this problem. However, for large datasets, finding reducts with minimal test cost is NP hard. Therefore, we should propose a heuristic algorithm to deal with this problem for large datasets.


### 3.3. Evaluation Measures

In order to dispel the influence of subjective and objective factors, three evaluation measures are adopted to evaluate the performance of the proposed algorithm. We adopt the three measures proposed in [6] for this purpose. These are finding optimal factor (FOF), maximal exceeding factor (MEF), and average exceeding factor (AEF).LetK be the number of experiments and let k be the number of searched optimal reduct in the experiments. The finding optimal factor is a both qualitative and quantitative measure, which is defined as
(18)op=kK.The maximal exceeding factor describes the worst case of an algorithm, which is defined as(19)max1≤i≤Kef(Ri),
where ef(R)=(c(R)-c(R′))/(c(R′)) is the exceeding factor indicating the badness of a reduct, which is a quantitative measure, where R′ is an optimal reduct and R is the searched reduct.The average exceeding factor is defined as(20)∑i=1Kef(Ri)K,
which represents the whole performance of an algorithm.


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

According to “3-sigma" rule, we present a new model considering both error distribution and confidence interval. According to Definition2, we have defined a neighborhood in [31] as follows.Definition 8.
LetS=(U,C,D,V,I,n) be a decision system with normal distribution measurement errors. Given xi∈U and B⊆C, the neighborhood of xi with respect to normal distribution measurement errors on attribute set B is defined as
(14)nB(xi)={x∈U∣∀a∈B,|a(x)-a(xi)|≤2n(a)},
where n(a)=Λe(a) is the error boundary. It represents the error value of a in [-n(a),+n(a)].Measurement errors with no more than a difference of2n(a) should be viewed as the family of neighborhood granules. We explain why n(a) instead of e(a) was employed in (14) as the maximal distance. Although the value of error is within a certain range, there are significant differences among confidence intervals. As mentioned earlier, “3-sigma" rule states that for a normal distribution, different proportion values lie within different standard deviations of the mean. In particularly, the proportion is very close to 0 if data is more than three standard deviations from the mean.Therefore, measurement errors with no more than a difference ofn(a)=Λe(a) should be viewed as the family of neighborhood granules. Naturally, the size of the neighborhood depends on error ranges of tests and adjusting factor. Figure 3 shows the different sizes of neighborhood based on ±1σ, ±2σ, and ±3σ.Figure 3
Two-dimensional neighborhood based on different standard deviations.In the new model, the lower and upper approximations are defined as follows.Definition 9 (see [31]).
LetS=(U,C,D,V,I,n) be a decision system with normal distribution measurement errors, and let NB be a neighborhood relation induced by B⊆C. For any X⊆U, the lower and upper approximations of X in a neighborhood approximation space 〈U,NB〉 are defined as
(15)NB_(X)={xi∣xi∈U∧nB(xi)⊆X},NB-(X)={xi∣xi∈U∧nB(xi)∩X≠∅}.∀
X
⊆
U, NB-(X)⊇X⊇NB_(X). The boundary region of X in 〈U,NB〉 is defined as
(16)BNB(X)=NB-(X)-NB_(X).
The positive region of D with respect to B⊆C is defined as POSB(D)=⋃X∈U/D‍NB_(X) [49, 50].


## 3.2. Test-Cost-Sensitive Attribute Reduct Problem

Attribute reduction is a successful technique to remove redundant data and facilitate the mining task. A number of definitions of relative reducts exist [25, 38, 51, 52] for different rough set models. In this section, we define test-cost-sensitive attribute reduction on the covering-based rough set model with NDME.A minimal test cost reduct problem proposed in [6] can be redefined as follows. The problem of finding such a reduct is called the minimal test cost reduct problem.Problem 1.The minimal test cost reduct problem.Input: S=(U,C,D,V,I,n,c);Output: B⊆C;Constraint: POSB(D)=POSC(D);Optimization objective: min(c(B)).Compared with the classical minimal reduction problem, there are several differences as follows. The first is the input, where the test costs and measurement errors are the external information. The second is the optimization objective, which is to minimize the test cost instead of the number of features. We can adopt the addition-deletion strategy [15] to design our heuristic reduction algorithm.In order to address the constraint of the problem, we have defined an inconsistent object in [4]. Here we redefine it as follows.Definition 10.
LetS=(U,C,D,V,I,n) be a decision system with normal distribution measurement errors, B⊆C, and x∈U. In nB(x), any x*∈nB(x) is called an inconsistent object if D(x*)≠D(x). The set of inconsistent objects in nB(x) is
(17)icB(x)={x*∈nB(x)∣D(x*)≠D(x)}.We can evaluate the characteristics of the neighborhood block through the number of inconsistent objects, namely,|icB(x)|. From Definition 10 we know that given B⊆C, x∈POSC(D) if and only if icB(x)=∅. Consequently, the icB(x) is an important parameter when we compute the positive region. Therefore, the following proposition can be used as an alternative definition of a reduct.Proposition 11.
LetS=(U,C,D,V,I,n) be a NEDS. Any R⊆C is a decision-relative reduct if and only if(1)
∀x∈POSC(D),icR(x)=∅,(2)
∀x∈R,∃x∈POSC(D),st. icR-{a}(x)≠∅.Sometimes we are interested in minimal reduction or minimal test cost reduct (see, e.g., [6]). In this work, we focus on finding reducts with minimal test cost, that is, test-cost-sensitive attribute reducts. Because the TCI-NEDS is a natural extension of NEDS, concepts in the NEDS are also applicable to the TCI-NEDS. We introduce the following definition.Definition 12.
LetRed(S) denote the set of all reducts of a TCI-NEDS S=(U,C,D,V,I,n,c). Any R∈Red(S) where c(R)=min{c(R′)∣R′∈Red(S)} is called a minimal test cost reduct.According to this definition, we should compute all reducts firstly. Consequently, exhaustive algorithms are needed to address this problem. However, for large datasets, finding reducts with minimal test cost is NP hard. Therefore, we should propose a heuristic algorithm to deal with this problem for large datasets.


## 3.3. Evaluation Measures

In order to dispel the influence of subjective and objective factors, three evaluation measures are adopted to evaluate the performance of the proposed algorithm. We adopt the three measures proposed in [6] for this purpose. These are finding optimal factor (FOF), maximal exceeding factor (MEF), and average exceeding factor (AEF).LetK be the number of experiments and let k be the number of searched optimal reduct in the experiments. The finding optimal factor is a both qualitative and quantitative measure, which is defined as
(18)op=kK.The maximal exceeding factor describes the worst case of an algorithm, which is defined as(19)max1≤i≤Kef(Ri),
where ef(R)=(c(R)-c(R′))/(c(R′)) is the exceeding factor indicating the badness of a reduct, which is a quantitative measure, where R′ is an optimal reduct and R is the searched reduct.The average exceeding factor is defined as(20)∑i=1Kef(Ri)K,
which represents the whole performance of an algorithm.


## 4. Algorithm

Test-cost-sensitive attribute reduct problem is NP-hard problem. Therefore, heuristic algorithms are needed to calculate the possible reducts for large datasets. In order to evaluate the performance of a heuristic algorithm, we should find an optimal reduct from all reducts. Hence, exhaustive algorithms are also needed.In this section, we mainly present a heuristic algorithm and a competition approach to deal with the new problem. The exhaustive algorithm of [4] is adopted to find all reducts of datasets. It is based on backtracking where pruning techniques are crucial in reducing computation.


### 4.1. Theδ-Weighted Heuristic Reduction Algorithm

To design a heuristic algorithm, we employ an algorithm framework which is similar to the one proposed in [6]. The algorithm follows the typical addition-deletion strategies [15], which is listed in Algorithm 1. It constructs a superreduct and then reduces it to obtain a reduct. The algorithm is essentially different from the one in [6]. First, the input S is a test-cost-independent decision system with normal distribution measurement errors, which is more generalization than the TCI-ER. Second, test results are numerical with normal distribution measurement errors rather than only nominal. The key code of this framework is listed in lines 5 and 7, and the attribute significance function is redefined to obtain respective algorithm. The efficiency of the δ-weighted heuristic reduction algorithm will be discussed in Section 5.4.Algorithm 1:An addition-deletion test-cost-sensitive reduction algorithm.
Input: (U,C,D,{Va},{Ia},n,c)
Output: A reduct with minimal test cost
Method:
(1) B=∅;
//Attribute addition
(2) Ct = C;
(3) while (POSB (D) ≠POSC (D)) do
(4) for each a∈Ct  do
(5)   Compute f(B,a,c);
(6)  end for
(7)  Select a* with the maximal f(B,a*,c);
(8)  B = B∪{a*};Ct = Ct −{a*};
(9) end while
//Attribute deletion
(10) Ct = B;
(11) while (Ct≠∅) do
(12) Select a* with the maximal test cost.
(13)  Ct = Ct −{a*};
(14)  if (POSB-{a*}(D)= POSB(D)) then
(15)  B = B − {a*};
(16) end if
(17) end while
(18) return B;As previously mentioned,|icB(x)| is an important parameter in evaluating the quality of a neighborhood block. Now, we introduce the following concepts.Definition 13.
LetS=(U,C,D,V,I,n) be a NEDS, B⊆C, and x∈U. |icB(x)| is the number of inconsistent objects in neighborhood nB(x). The total number of inconsistent objects with respect to the positive region is
(21)pcB(S)=∑x∈POSC(D)|icB(x)|.Finally, we propose aδ-weighted heuristic information function:
(22)f(B,ai,c(ai))=Φ+δΦc(ai),
where Φ=pcB(S)-pcB∪{ai}(S) is necessary and indispensable, and it plays a dominant role in the heuristic information, where c(ai) is the test cost of ai and δ≥0 is a user-specified parameter. If δ=0, test costs are essentially not considered. If δ>0, tests with lower cost have bigger significance. Different δ settings can adjust the significance of test cost.


### 4.2. The Competition Approach

In order to obtain better results, the competition approach has been discussed in [6]. In the new environment, it is still valid because there is no universally optimal δ. In this approach, reducts complete against each other with only one winner, that is, a reduct with minimal test cost, which can be obtained using δ∈L:
(23)cL=minδ∈Lc(Rδ),
where Rδ is the reduct obtained by Algorithm 1 using the heuristic information, with the |L| sets of user-specified δ values.This approach can improve the quality of the result significantly. The algorithm runs|L| times with different δ values; hence, more runtime is needed. However, it is acceptable because the heuristic algorithm is fast.


## 4.1. Theδ-Weighted Heuristic Reduction Algorithm

To design a heuristic algorithm, we employ an algorithm framework which is similar to the one proposed in [6]. The algorithm follows the typical addition-deletion strategies [15], which is listed in Algorithm 1. It constructs a superreduct and then reduces it to obtain a reduct. The algorithm is essentially different from the one in [6]. First, the input S is a test-cost-independent decision system with normal distribution measurement errors, which is more generalization than the TCI-ER. Second, test results are numerical with normal distribution measurement errors rather than only nominal. The key code of this framework is listed in lines 5 and 7, and the attribute significance function is redefined to obtain respective algorithm. The efficiency of the δ-weighted heuristic reduction algorithm will be discussed in Section 5.4.Algorithm 1:An addition-deletion test-cost-sensitive reduction algorithm.
Input: (U,C,D,{Va},{Ia},n,c)
Output: A reduct with minimal test cost
Method:
(1) B=∅;
//Attribute addition
(2) Ct = C;
(3) while (POSB (D) ≠POSC (D)) do
(4) for each a∈Ct  do
(5)   Compute f(B,a,c);
(6)  end for
(7)  Select a* with the maximal f(B,a*,c);
(8)  B = B∪{a*};Ct = Ct −{a*};
(9) end while
//Attribute deletion
(10) Ct = B;
(11) while (Ct≠∅) do
(12) Select a* with the maximal test cost.
(13)  Ct = Ct −{a*};
(14)  if (POSB-{a*}(D)= POSB(D)) then
(15)  B = B − {a*};
(16) end if
(17) end while
(18) return B;As previously mentioned,|icB(x)| is an important parameter in evaluating the quality of a neighborhood block. Now, we introduce the following concepts.Definition 13.
LetS=(U,C,D,V,I,n) be a NEDS, B⊆C, and x∈U. |icB(x)| is the number of inconsistent objects in neighborhood nB(x). The total number of inconsistent objects with respect to the positive region is
(21)pcB(S)=∑x∈POSC(D)|icB(x)|.Finally, we propose aδ-weighted heuristic information function:
(22)f(B,ai,c(ai))=Φ+δΦc(ai),
where Φ=pcB(S)-pcB∪{ai}(S) is necessary and indispensable, and it plays a dominant role in the heuristic information, where c(ai) is the test cost of ai and δ≥0 is a user-specified parameter. If δ=0, test costs are essentially not considered. If δ>0, tests with lower cost have bigger significance. Different δ settings can adjust the significance of test cost.


## 4.2. The Competition Approach

In order to obtain better results, the competition approach has been discussed in [6]. In the new environment, it is still valid because there is no universally optimal δ. In this approach, reducts complete against each other with only one winner, that is, a reduct with minimal test cost, which can be obtained using δ∈L:
(23)cL=minδ∈Lc(Rδ),
where Rδ is the reduct obtained by Algorithm 1 using the heuristic information, with the |L| sets of user-specified δ values.This approach can improve the quality of the result significantly. The algorithm runs|L| times with different δ values; hence, more runtime is needed. However, it is acceptable because the heuristic algorithm is fast.


## 5. Experiments

### 5.1. Data Generation

Most datasets from the UCI library [53] have no intrinsic measurement errors and test costs. Therefore, in our experiments, we create these data to study the performance of the reduction algorithm. For example, measurement errors satisfy normal distribution and Pauta criterion. For the same object, the condition attribute with narrower error ranges should be more expensive. In this section, we will discuss the generation of both the measurement errors and test costs.Step 1. Ten datasets from the UCI Repository of Machine Learning Databases are selected, and these datasets are listed in Table 2. Each dataset should contain exactly one decision attribute  and have no missing value. In order to facilitate processing, firstly, we normalize the data items from their value into a range from 0 to 1. And then, missing values are directly set to 0.5.Table 2
Database information.
No.
Name
Domain
|
U
|
|
C
|
|
C
′
|
D
=
d
1
Iris
Zoology
150
4
4
Class
2
Glass
Manufacture
214
9
13
Type
3
Wine
Agriculture
178
13
21
Class
4
Wpbc
Clinic
198
33
65
Outcome
5
Wdbc
Clinic
569
30
58
Diagnosis
6
Credit
Commerce
690
15
23
Class
7
Image
Graphics
210
19
30
Class
8
Iono
Physics
351
34
68
Class
9
Liver
Clinic
345
6
8
Selector
10
Diab
Clinic
768
8
12
ClassStep 2. We produce the number of additional tests for one particular attribute. We generate a random integer k* in the range [0,k] and k≤5. That is, we have (k*+1) measurement methods to obtain values for each object. The number of tests including the additional ones for our experiments is |C′|, which is listed in Table 2.Step 3. We produce the n(a) for each original test according to (6) and (7). The n(a) is computed according to the value of databases without any subjectivity. Three kinds of error ranges of different databases are shown in Table 3. These error ranges are maximal, minimal, and average error ranges 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 3
Generated error ranges for different databases.
Datasets
Minimal
Maximal
Average
Iris
0.0042
0.0044
0.0043
Glass
0.0005
0.0059
0.0030
Wine
0.0031
0.0053
0.0040
Wpbc
0.0011
0.0056
0.0031
Wdbc
0.0006
0.0040
0.0023
Credit
0.0001
0.0056
0.0022
Image
0.0001
0.0065
0.0026
Iono
0.0045
0.0087
0.0061
Liver
0.0011
0.0065
0.0029
Diab
0.0009
0.0059
0.0031Step 4. We produce “new" data subject to error ranges. Letting a1 be the original test, we can add a random number in [-(i-1)n(a),(i-1)n(a)] to a1(x) to produce ai(x), where x∈U. The number is generated as follows.Lettingx1 and x2 be uniformly distributed on (0, 1), then
(24)y1(x1,x2)=-2lnx1cos(2πx2)
is a random number which has a normal distribution with μ=0 mean and σ2=1. From Proposition 4 we know the n(a)=3σ, and σ=(1/3)n(a).Since we need a random number in[-n(a),+n(a)], we let
(25)y(n(a),x1,x2)=13y1(x1,x2)n(a).Finally, the error range is(26)NDME={-n(a)ify<-n(a),n(a)ify>n(a),y(n(a),x1,x2)otherwise.
According to Definition 8, ±i*n(a) is the error range of the new test ai.The generated NDME with different error ranges are shown in Figure4. The generated NDME of different databases are shown in Figure 5.Figure 4
Normal distribution measurement errors with different error ranges.Figure 5
Normal distribution measurement errors of Iris, Glass, and Wdbc.Step 5. The test costs are produced, and they are always represented by positive integers. Let a1 be the original test and let a1 be the last test for one particular data item. c(al) is set to a random number in [1,100]. c(ai) where 1≤i<l is set to 2×c(ai+1). This setting guarantees that tests with narrower error ranges are more expensive.A dataset generated by this approach is listed in Table4. SL stands for sepal length, SW stands for sepal width, PL stands for petal length, and PW stands for petal width. SL-1, PL-1, and PL-2 indicate different revisions of the original data. There is only one method to obtain SW and PW.Table 4
A generated measurement error vector and a generated test cost vector (Iris).
a
SL
SL-1
SW
PL
PL-1
PL-2
PW
Original test
True
False
True
True
False
False
True
e
(
a
)
0.0043
0.0086
0.0041
0.0041
0.0082
0.0123
0.0041
c
(
a
)
28
14
81
376
188
94
91


### 5.2. Effectiveness of the Heuristic Algorithm

Letδ=2,3,4,…,9. The heuristic algorithm runs 800 times with different test cost settings and different δ setting on all datasets. Figures 6 and 7 show the results of FOF. For different settings of δ, the performance of the algorithm is completely different; that is, the test cost plays a key role in this heuristic algorithm. The results are incomparable to others when δ=0; hence, these results are not included in this experiment results.Figure 6
Finding optimal factor (datasets 1–5).Figure 7
Finding optimal factor (datasets 6–10).Figures8 and 9 show the results of MEF, which provide the worst case of the algorithm, and they should be viewed as a statistical measure. Figures 10 and 11 show the results of AEF. These display the overall performance of the algorithm from a statistical perspective.Figure 8
Maximal exceeding factor (datasets 1–5).Figure 9
Maximal exceeding factor (datasets 6–10).Figure 10
Average exceeding factor (datasets 1–5).Figure 11
Average exceeding factor (datasets 6–10).From the results we observe that the quality of the results varies for different datasets. It is related to the dataset itself because the error range and heuristic information are all computed according to the values of dataset. Then the AEF is less than 0.3 in most cases, which is acceptable. Although the results are generally acceptable, the performance of the algorithm should be improved. In Section5.3, we will address this issue further.


### 5.3. Comparison of Three Approaches

For the proposed algorithm,δ is a key parameter. Three approaches can be obtained with different setting of δ. The first approach is called nonweighting approach. It is the only one without taking into account test costs, which is implemented by setting δ=0. The second approach, called the best δ approach, is to choose the best δ value as depicted in Figures 6 through 11. The third approach is the competition approach discussed in Section 4.2. All three are based on Algorithm 1 and the same databases. Now we compare the performance of the proposed algorithm through three approaches mentioned in Section 4.Table5 lists results for all three approaches. From Table 5, we observe the following.(1)
The nonweighting approach almost does not find the optimal reduct. It is unacceptable from all three metrics.(2)
In most cases, the bestδ approach obtains optimal results. However, we have no idea how to obtain the best value of δ in real applications.(3)
The competition approach improves the quality of results significantly, and the runtime is acceptable for relatively small number ofδ.Table 5
Results forδ=0,δ with the optimal setting, and δ with a number of choices.
Dataset
FOF
MEF
AEF
δ
=
0
δ
=
δ
*
δ
∈
L
δ
=
0
δ
=
δ
*
δ
∈
L
δ
=
0
δ
=
δ
*
δ
∈
L
Iris
0.170
0.940
0.940
2.000
0.100
0.100
0.360
0.003
0.003
Glass
0.090
0.570
0.640
3.220
0.374
0.374
0.700
0.064
0.049
Wine
0.000
0.900
0.940
19.44
0.423
0.423
4.464
0.021
0.014
Wpbc
0.000
0.840
0.880
45.67
0.300
0.250
14.50
0.033
0.017
Wdbc
0.000
0.710
0.760
93.20
0.500
0.500
14.61
0.041
0.037
Credit
0.000
0.520
0.550
2.188
0.317
0.310
1.095
0.053
0.049
Image
0.000
0.680
0.790
31.43
0.406
0.269
5.417
0.053
0.032
Iono
0.000
0.500
0.630
46.60
0.765
0.544
10.28
0.084
0.054
Liver
0.040
0.780
0.910
4.125
0.275
0.181
0.921
0.023
0.008
Diab
0.000
0.640
0.700
3.788
0.481
0.481
1.278
0.048
0.033


### 5.4. Comparison with Existing Algorithm

Compared with an existing model [4], the major improvement is introduced in this section.First, the NDME was considered to data model, and covering-based rough set based on NDME has been proposed. In most cases, the measurement errors satisfy normal distribution instead of uniform distribution; hence, this new model has wider application areas.Second, comparing with the fix error range of different databases from [4], the proposed error ranges are adaptively generated according to the database values. Table 3 shows the generated error ranges for different databases. The error ranges for different attributes of the same database are completely different. For example, the maximal error range of Wdbc is 0.0040, and the minimal one is 0.0006.Third, aδ-weighted heuristic algorithm is developed to deal with the minimal test cost reduct problem. Our algorithm is compared with the λ-weighted algorithm [4] from effectiveness and efficiency. Since two different algorithms have different parameters, we compare the results of the competition approach on ten datasets. Figure 12 shows competition approach results of two algorithms. From the results we observe that(1)
on Wpbc and Iono datasets, two algorithms have the same performance;(2)
λ-weighted algorithm has better performance than our algorithm on Iris, Glass, and Credit datasets;(3)
however, our algorithm performs better than theλ-weighted algorithm on five datasets.Figure 12
Competition approach results of two algorithms.The efficiency comparison between theδ-weighted algorithm and λ-weighted one is depicted in Figure 13. From the results we note that our algorithm has an improvement in terms of runtime. Figure 14 shows the efficiency ratios of the δ-weighted algorithm and the λ-weighted algorithm.Figure 13
Efficiency comparison.Figure 14
Improving efficiency ratio.


## 5.1. Data Generation

Most datasets from the UCI library [53] have no intrinsic measurement errors and test costs. Therefore, in our experiments, we create these data to study the performance of the reduction algorithm. For example, measurement errors satisfy normal distribution and Pauta criterion. For the same object, the condition attribute with narrower error ranges should be more expensive. In this section, we will discuss the generation of both the measurement errors and test costs.Step 1. Ten datasets from the UCI Repository of Machine Learning Databases are selected, and these datasets are listed in Table 2. Each dataset should contain exactly one decision attribute  and have no missing value. In order to facilitate processing, firstly, we normalize the data items from their value into a range from 0 to 1. And then, missing values are directly set to 0.5.Table 2
Database information.
No.
Name
Domain
|
U
|
|
C
|
|
C
′
|
D
=
d
1
Iris
Zoology
150
4
4
Class
2
Glass
Manufacture
214
9
13
Type
3
Wine
Agriculture
178
13
21
Class
4
Wpbc
Clinic
198
33
65
Outcome
5
Wdbc
Clinic
569
30
58
Diagnosis
6
Credit
Commerce
690
15
23
Class
7
Image
Graphics
210
19
30
Class
8
Iono
Physics
351
34
68
Class
9
Liver
Clinic
345
6
8
Selector
10
Diab
Clinic
768
8
12
ClassStep 2. We produce the number of additional tests for one particular attribute. We generate a random integer k* in the range [0,k] and k≤5. That is, we have (k*+1) measurement methods to obtain values for each object. The number of tests including the additional ones for our experiments is |C′|, which is listed in Table 2.Step 3. We produce the n(a) for each original test according to (6) and (7). The n(a) is computed according to the value of databases without any subjectivity. Three kinds of error ranges of different databases are shown in Table 3. These error ranges are maximal, minimal, and average error ranges 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 3
Generated error ranges for different databases.
Datasets
Minimal
Maximal
Average
Iris
0.0042
0.0044
0.0043
Glass
0.0005
0.0059
0.0030
Wine
0.0031
0.0053
0.0040
Wpbc
0.0011
0.0056
0.0031
Wdbc
0.0006
0.0040
0.0023
Credit
0.0001
0.0056
0.0022
Image
0.0001
0.0065
0.0026
Iono
0.0045
0.0087
0.0061
Liver
0.0011
0.0065
0.0029
Diab
0.0009
0.0059
0.0031Step 4. We produce “new" data subject to error ranges. Letting a1 be the original test, we can add a random number in [-(i-1)n(a),(i-1)n(a)] to a1(x) to produce ai(x), where x∈U. The number is generated as follows.Lettingx1 and x2 be uniformly distributed on (0, 1), then
(24)y1(x1,x2)=-2lnx1cos(2πx2)
is a random number which has a normal distribution with μ=0 mean and σ2=1. From Proposition 4 we know the n(a)=3σ, and σ=(1/3)n(a).Since we need a random number in[-n(a),+n(a)], we let
(25)y(n(a),x1,x2)=13y1(x1,x2)n(a).Finally, the error range is(26)NDME={-n(a)ify<-n(a),n(a)ify>n(a),y(n(a),x1,x2)otherwise.
According to Definition 8, ±i*n(a) is the error range of the new test ai.The generated NDME with different error ranges are shown in Figure4. The generated NDME of different databases are shown in Figure 5.Figure 4
Normal distribution measurement errors with different error ranges.Figure 5
Normal distribution measurement errors of Iris, Glass, and Wdbc.Step 5. The test costs are produced, and they are always represented by positive integers. Let a1 be the original test and let a1 be the last test for one particular data item. c(al) is set to a random number in [1,100]. c(ai) where 1≤i<l is set to 2×c(ai+1). This setting guarantees that tests with narrower error ranges are more expensive.A dataset generated by this approach is listed in Table4. SL stands for sepal length, SW stands for sepal width, PL stands for petal length, and PW stands for petal width. SL-1, PL-1, and PL-2 indicate different revisions of the original data. There is only one method to obtain SW and PW.Table 4
A generated measurement error vector and a generated test cost vector (Iris).
a
SL
SL-1
SW
PL
PL-1
PL-2
PW
Original test
True
False
True
True
False
False
True
e
(
a
)
0.0043
0.0086
0.0041
0.0041
0.0082
0.0123
0.0041
c
(
a
)
28
14
81
376
188
94
91


## 5.2. Effectiveness of the Heuristic Algorithm

Letδ=2,3,4,…,9. The heuristic algorithm runs 800 times with different test cost settings and different δ setting on all datasets. Figures 6 and 7 show the results of FOF. For different settings of δ, the performance of the algorithm is completely different; that is, the test cost plays a key role in this heuristic algorithm. The results are incomparable to others when δ=0; hence, these results are not included in this experiment results.Figure 6
Finding optimal factor (datasets 1–5).Figure 7
Finding optimal factor (datasets 6–10).Figures8 and 9 show the results of MEF, which provide the worst case of the algorithm, and they should be viewed as a statistical measure. Figures 10 and 11 show the results of AEF. These display the overall performance of the algorithm from a statistical perspective.Figure 8
Maximal exceeding factor (datasets 1–5).Figure 9
Maximal exceeding factor (datasets 6–10).Figure 10
Average exceeding factor (datasets 1–5).Figure 11
Average exceeding factor (datasets 6–10).From the results we observe that the quality of the results varies for different datasets. It is related to the dataset itself because the error range and heuristic information are all computed according to the values of dataset. Then the AEF is less than 0.3 in most cases, which is acceptable. Although the results are generally acceptable, the performance of the algorithm should be improved. In Section5.3, we will address this issue further.


## 5.3. Comparison of Three Approaches

For the proposed algorithm,δ is a key parameter. Three approaches can be obtained with different setting of δ. The first approach is called nonweighting approach. It is the only one without taking into account test costs, which is implemented by setting δ=0. The second approach, called the best δ approach, is to choose the best δ value as depicted in Figures 6 through 11. The third approach is the competition approach discussed in Section 4.2. All three are based on Algorithm 1 and the same databases. Now we compare the performance of the proposed algorithm through three approaches mentioned in Section 4.Table5 lists results for all three approaches. From Table 5, we observe the following.(1)
The nonweighting approach almost does not find the optimal reduct. It is unacceptable from all three metrics.(2)
In most cases, the bestδ approach obtains optimal results. However, we have no idea how to obtain the best value of δ in real applications.(3)
The competition approach improves the quality of results significantly, and the runtime is acceptable for relatively small number ofδ.Table 5
Results forδ=0,δ with the optimal setting, and δ with a number of choices.
Dataset
FOF
MEF
AEF
δ
=
0
δ
=
δ
*
δ
∈
L
δ
=
0
δ
=
δ
*
δ
∈
L
δ
=
0
δ
=
δ
*
δ
∈
L
Iris
0.170
0.940
0.940
2.000
0.100
0.100
0.360
0.003
0.003
Glass
0.090
0.570
0.640
3.220
0.374
0.374
0.700
0.064
0.049
Wine
0.000
0.900
0.940
19.44
0.423
0.423
4.464
0.021
0.014
Wpbc
0.000
0.840
0.880
45.67
0.300
0.250
14.50
0.033
0.017
Wdbc
0.000
0.710
0.760
93.20
0.500
0.500
14.61
0.041
0.037
Credit
0.000
0.520
0.550
2.188
0.317
0.310
1.095
0.053
0.049
Image
0.000
0.680
0.790
31.43
0.406
0.269
5.417
0.053
0.032
Iono
0.000
0.500
0.630
46.60
0.765
0.544
10.28
0.084
0.054
Liver
0.040
0.780
0.910
4.125
0.275
0.181
0.921
0.023
0.008
Diab
0.000
0.640
0.700
3.788
0.481
0.481
1.278
0.048
0.033


## 5.4. Comparison with Existing Algorithm

Compared with an existing model [4], the major improvement is introduced in this section.First, the NDME was considered to data model, and covering-based rough set based on NDME has been proposed. In most cases, the measurement errors satisfy normal distribution instead of uniform distribution; hence, this new model has wider application areas.Second, comparing with the fix error range of different databases from [4], the proposed error ranges are adaptively generated according to the database values. Table 3 shows the generated error ranges for different databases. The error ranges for different attributes of the same database are completely different. For example, the maximal error range of Wdbc is 0.0040, and the minimal one is 0.0006.Third, aδ-weighted heuristic algorithm is developed to deal with the minimal test cost reduct problem. Our algorithm is compared with the λ-weighted algorithm [4] from effectiveness and efficiency. Since two different algorithms have different parameters, we compare the results of the competition approach on ten datasets. Figure 12 shows competition approach results of two algorithms. From the results we observe that(1)
on Wpbc and Iono datasets, two algorithms have the same performance;(2)
λ-weighted algorithm has better performance than our algorithm on Iris, Glass, and Credit datasets;(3)
however, our algorithm performs better than theλ-weighted algorithm on five datasets.Figure 12
Competition approach results of two algorithms.The efficiency comparison between theδ-weighted algorithm and λ-weighted one is depicted in Figure 13. From the results we note that our algorithm has an improvement in terms of runtime. Figure 14 shows the efficiency ratios of the δ-weighted algorithm and the λ-weighted algorithm.Figure 13
Efficiency comparison.Figure 14
Improving efficiency ratio.


## 6. Conclusions

In rough set model, measurement errors and test costs are all intrinsic to data. In this paper, we built a new covering-based rough set model considering measurement errors and test costs at four levels.(1)
At the data model level, a new data model with NDME and test cost was proposed. This model has more application areas because the measurement errors have certain universality.(2)
At the computational model level, we introduced a covering-based rough set with NDME. This model is generally more complex than that presented in this field.(3)
At the problem level, a minimal test cost reduct problem based on the new model was redefined.(4)
At the algorithm level, aδ-weighted heuristic algorithm was developed to deal with this reduct problem. Experimental results indicate the effectiveness and efficiency of the algorithm.In summary, the data model based on normal distribution measurement errors has the wide application scope. This study suggests new research trends of covering-based rough set and cost-sensitive learning.



---

*Source: 946070-2013-03-27.xml*