# Kernel Neighborhood Rough Sets Model and Its Application

Authors: Kai Zeng; Siyuan Jing
Journal: Complexity
 (2018)

---

## Abstract

Rough set theory has been successfully applied to many fields, such as data mining, pattern recognition, and machine learning. Kernel rough sets and neighborhood rough sets are two important models that differ in terms of granulation. The kernel rough sets model, which has fuzziness, is susceptible to noise in the decision system. The neighborhood rough sets model can handle noisy data well but cannot describe the fuzziness of the samples. In this study, we define a novel model called kernel neighborhood rough sets, which integrates the advantages of the neighborhood and kernel models. Moreover, the model is used in the problem of feature selection. The proposed method is tested on the UCI datasets. The results show that our model outperforms classic models.


---

## Body

## 1. Introduction

Rough set theory, which was proposed by Pawlak in 1982, is a powerful mathematical method to study incomplete and imprecise information. This theory has been successfully applied to many fields, such as data mining, decision-making, pattern recognition, machine learning, and intelligent control [1–4]. Kernel rough sets [5] and neighborhood rough sets [6] are two important models in rough set theory.Hu innovatively proposed the kernel rough sets model [5, 7]. A Gaussian kernel rough sets model-based feature selection method was discussed in [8]. The information fusion problem of imperfect images has also been studied based on Hu’s research [9]. Ghosh et al. proposed an efficient Gaussian kernel-based fuzzy rough sets approach for feature selection [10]. A novel fuzzy rough sets model was constructed by combining the hybrid distance and the Gaussian kernel in [11]. A new feature selection method based on kernel fuzzy rough sets and a memetic algorithm were proposed for the transient stability assessment of power systems [12]. In these studies, the information granules are constructed in the kernel structure. The “min” and “max” aggregation operations are used in approximation calculations [13–15]. That is, the decision for a sample is dependent on the nearest sample [7]. The computation of the lower approximation comes with risks if there is noise in the datasets [16]. Data noise can lead to an increase in the classification error rate by using the kernel rough sets model [16].Neighborhood is an important concept in classification and clustering. To formulate the notion of approximation, the neighborhood system was introduced into the relational model by Lin [17–19]. Yao presented a framework for the formulation, interpretation, and comparison of neighborhood systems and rough sets approximations [20]. Hu et al. investigated the issue of heterogeneous feature subset selection based on neighborhood rough sets [6, 21]. Based on neighborhood granulation, samples are constructed as a family of neighborhood granules to approximate the object sets. The neighborhood model can handle noisy data well based on the tolerance neighborhood relation and probabilistic theory [22]. However, the main limitation of this model is that it cannot describe the fuzziness of samples [16].Overall, the kernel rough sets model, which has fuzziness, is susceptible to noise in the decision system. The neighborhood rough sets model can handle noisy data but cannot describe the fuzziness of samples. That is, we can construct a new model by the combination of advantage of kernel and neighborhood rough sets.On the other hand, increasing amounts of high-dimensional data must be processed for some real applications. Currently, feature selection plays an important role in machine learning and data mining. Neighborhood rough sets and kernel rough sets are widely used in feature selection [23–26]. We also can deal with the feature selection problem by using the new rough sets model.Based on the motivations above, the contributions of this paper include the following: (1) We define a novel model, the kernel neighborhood rough sets model, which integrates the advantages of the neighborhood and kernel models. (2) Moreover, the model is used in the problem of feature selection. (3) The proposed method is tested on the UCI datasets. The results show that our model yields a better performance than classic models.This paper is organized as follows. In Section2, some basic concepts regarding neighborhood rough sets and kernel rough sets are briefly reviewed. In Section 3, the kernel neighborhood rough sets (KNRS) model is investigated in detail. Section 4 shows the application of KNRS to feature evaluation and feature selection. Numerical experiments are reported in Section 5. Finally, Section 6 concludes the paper.


## 2. Preliminary Knowledge

In this section, we review the kernel rough sets (KRS) model [5] and the neighborhood rough sets (NRS) model [6].


### 2.1. Kernel Rough Sets (KRS) Model

Definition 1.
SupposeU is a nonempty finite set of objects and k is a Gaussian kernel function kxi,xj=exp−xi−xj2/2δ2, where xi−xj2 is the Euclidean distance. Therefore, U,A,k is a kernel approximation space, where
(1)
kxi,xi=1,
(2)
kxi,xj=kxj,xi,
(3)
kxi,xj∈0,1.Definition 2.
Given a kernel approximation spaceU,A,k, X∈FU is a fuzzy subset of U, and we define the lower and upper approximations of X on the space U,A,k as follows:
(1)K¯Xx=infy∈Umax1−kx,y,Xy,K¯Xx=supy∈Uminkx,y,Xy.


### 2.2. Neighborhood Rough Sets (NRS) Model

Pawlak rough sets theory works only on data sets with discrete attributes [27]. Hu et al. introduced a neighborhood rough sets model for heterogeneous data to avoid discretization. The definition is as follows [6, 28].Definition 3.
SupposeU is a nonempty finite set of objects and Δ is a given distance function. A is a set of features. Therefore, U,A,δ is a neighborhood approximation space, where
(1)
Δxi,xj≥0, if and only if xi=xj, Δxi,xj=0,
(2)
Δxi,xj=Δxj,xi,
(3)
Δxi,xk≤Δxi,xj+Δxj,xk.Definition 4.
Given a neighborhood approximation spaceU,A,δ, ∀x∈U, and δ≥0, δx is a δ neighborhood of x whose center is x and the radius is δ, where δx=x∣Δx,y≤δ,x∈U.
Here,δx can be considered to be the neighborhood granule.Remark 1.
Given two pointsxi=xi1,xi2,…,xin and xj=xj1,xj2,…,xjn in N-dimensional Euclidean space, the distance between them can be computed as
(2)Δxi,xj=∑l=1Ndalxi,xj2,dalxi,xj=nom_diffalxi,xjalisanominalattribute,num_diffalxi,xjalisanumericalattribute,where nom_diffalxi,xj=0ifxil=xjl,1ifxil≠xjl,and num_diffalxi,xj=xil−xjl/maxVal−minVal.Definition 5.
Given a neighborhood approximation spaceU,A,δ, for any subset X⊆U, we define the lower and upper approximations of X on the space U,A,δ, respectively, as follows:
(3)N¯X=x∈Xδx⊆X,N¯X=x∈Xδx⋂X≠∅.
The definitions of the lower and upper approximations are the most important concepts in KRS and NRS.


## 2.1. Kernel Rough Sets (KRS) Model

Definition 1.
SupposeU is a nonempty finite set of objects and k is a Gaussian kernel function kxi,xj=exp−xi−xj2/2δ2, where xi−xj2 is the Euclidean distance. Therefore, U,A,k is a kernel approximation space, where
(1)
kxi,xi=1,
(2)
kxi,xj=kxj,xi,
(3)
kxi,xj∈0,1.Definition 2.
Given a kernel approximation spaceU,A,k, X∈FU is a fuzzy subset of U, and we define the lower and upper approximations of X on the space U,A,k as follows:
(1)K¯Xx=infy∈Umax1−kx,y,Xy,K¯Xx=supy∈Uminkx,y,Xy.


## 2.2. Neighborhood Rough Sets (NRS) Model

Pawlak rough sets theory works only on data sets with discrete attributes [27]. Hu et al. introduced a neighborhood rough sets model for heterogeneous data to avoid discretization. The definition is as follows [6, 28].Definition 3.
SupposeU is a nonempty finite set of objects and Δ is a given distance function. A is a set of features. Therefore, U,A,δ is a neighborhood approximation space, where
(1)
Δxi,xj≥0, if and only if xi=xj, Δxi,xj=0,
(2)
Δxi,xj=Δxj,xi,
(3)
Δxi,xk≤Δxi,xj+Δxj,xk.Definition 4.
Given a neighborhood approximation spaceU,A,δ, ∀x∈U, and δ≥0, δx is a δ neighborhood of x whose center is x and the radius is δ, where δx=x∣Δx,y≤δ,x∈U.
Here,δx can be considered to be the neighborhood granule.Remark 1.
Given two pointsxi=xi1,xi2,…,xin and xj=xj1,xj2,…,xjn in N-dimensional Euclidean space, the distance between them can be computed as
(2)Δxi,xj=∑l=1Ndalxi,xj2,dalxi,xj=nom_diffalxi,xjalisanominalattribute,num_diffalxi,xjalisanumericalattribute,where nom_diffalxi,xj=0ifxil=xjl,1ifxil≠xjl,and num_diffalxi,xj=xil−xjl/maxVal−minVal.Definition 5.
Given a neighborhood approximation spaceU,A,δ, for any subset X⊆U, we define the lower and upper approximations of X on the space U,A,δ, respectively, as follows:
(3)N¯X=x∈Xδx⊆X,N¯X=x∈Xδx⋂X≠∅.
The definitions of the lower and upper approximations are the most important concepts in KRS and NRS.


## 3. Kernel Neighborhood Rough Sets (KNRS) Model

In this section, we study the KNRS model. The definitions and theorems of KNRS are discussed in detail. The kernel neighborhood decision system is also investigated.


### 3.1. Kernel Neighborhood Rough Sets

Definition 6.
Given a kernel neighborhood approximation spaceU,A,k,δ, δ≥0, where k is a Gaussian kernel function, ∀x,y∈U; thus, xkδ is a kernel neighborhood granule of x, where
(4)xkδ=0kx,y<δ,kx,ykx,y≥δ.Definition 7.
Given a kernel neighborhood approximation spaceU,A,k,δ, δ≥0, where k is a kernel function, for any fuzzy subset X⊆FU; we define the lower and upper approximations of X on the space U,A,k,δ, respectively, as follows:
(5)N¯X=xi∈Xxkδ⊆X,N¯X=xi∈Xxkδ⋂X≠∅.
The method defined above is crisp and has no noise tolerance ability. Here, we propose an improved model that is called variable precision lower and upper approximation.Definition 8.
Given a kernel neighborhood approximation spaceU,A,k,δ, δ≥0, where k is a kernel function, for any fuzzy subset X⊆FU; the variable precision lower and upper approximations of X are defined as follows, where ∣∗∣ denotes the cardinality of the specified set:
(6)KN¯αX=xi∈Xxkδ⋂Xxkδ≥α,KN¯αX=xi∈Xxkδ⋂Xxkδ>1−α.Then, 0.5≤α≤1 as in [22].Example 1.
Consider a kernel neighborhood approximation spaceU,A,k,δ, where U=u1,u2,u3,u4,u5, A=a1,a2,a3, δ=0.5, α=0.9, and k is a kernel function. The details are listed in Table 1.Table 1
Approximation space.
ID
a1
a2
a3
u1
0.1
0.2
0.3
u2
0.2
0.2
0.3
u3
0.3
0.1
0.1
u4
0.8
0.7
0.8
u5
0.9
0.9
0.7The relation matrix is presented in Table2. Each line is the kernel neighborhood granule of ui.Table 2
Relation matrix.
ID
u1
u2
u3
u4
u5
u1
1
0.90
0.74
0
0
u2
0.90
1
0.78
0
0
u3
0.74
0.78
1
0
0
u4
0
0
0
1
0.88
u5
0
0
0
0.88
1Given a fuzzy setX=0.9/u1,0.8/u2,0.9/u3,0.3/u4,0.1/u5, we obtain KN¯αX=KN¯αX=u1,u2,u3.Definition 9.
Given a kernel neighborhood approximation spaceU,A,k,δ, where δ≥0 and k is a kernel function, for any fuzzy subset X⊆FU, the positive, negative, and boundary regions of X in the space U,A,k,δ are, respectively, expressed as follows:
(7)POSX=KN¯X,NEGX=U−KN¯X,BNX=KN¯X−KN¯X.Theorem 1.
Given a kernel neighborhood approximation spaceU,A,k,δ, where δ1≤δ2≤0, then
(1)
xkδ1⊇xkδ2,
(2)
KN¯δ1X⊆KN¯δ2X,
(3)
KN¯δ1X⊆KN¯δ2X.Proof.
Ifδ1≤δ2≤0, then xkδ1⊇xkδ2. Assuming that xkδ1⊆X, then xkδ2⊆X. That is, x∈KN¯δ2X if x∈KN¯δ1X but not vice versa. Similarly, we obtain KN¯δ1X⊆KN¯δ2X.


### 3.2. Kernel Neighborhood Decision System

A kernel neighborhood approximation space is called a variable precision kernel neighborhood decision system which is denoted byU,C∪D,k,δ,α. C and D are condition and decision features, respectively.Definition 10.
Consider a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. We, respectively, define the lower and upper approximations of D with respect to feature subset B as follows:
(8)KN¯BαD=⋃i=1nKN¯BαDi,KN¯BαD=⋃i=1nKN¯BαDi.Definition 11.
Consider a variable precision kernel neighborhood decision system,U,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. The positive, negative, and boundary regions of D in the space U,A,k,δ are, respectively, defined as follows:
(9)POSBD=KN¯BD,NEGBD=U−KN¯BD,BNBD=KN¯BD−KN¯BD.
The size of the boundary increases the uncertainty in the decision system. The samples in the boundary generally have the same condition features but belong to different decision classes. This discrepancy leads to the poor classification performance of the employed algorithms. We should select a proper feature subset that increases the size of the positive region and decreases the size of the boundary region.Definition 12.
Consider a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. The dependency degree of D relative to B is defined as follows:
(10)γB=POSBDU.
The dependency degree reflects the approximating power of a condition feature set. A higher approximation degree means that the samples that are described by feature subsetB are more consistent with decision D.Theorem 2.
Given a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where C1⊆C2⊆C, then
(1)
xkδ,C1⊇xkδ,C2,
(2)
KN¯C1D⊆KN¯C2D,
(3)
POSC1D⊆POSC2D.Proof.
Ifδ1⊆δ2⊆0, then xkδ,C1⊇xkδ,C2. Assuming that xkδ,C1⊆D, then xkδ,C2⊆D. That is, x∈KN¯C2D if x∈KN¯C1D but not vice versa. Similarly, we obtain POSC1D⊆POSC2D.


## 3.1. Kernel Neighborhood Rough Sets

Definition 6.
Given a kernel neighborhood approximation spaceU,A,k,δ, δ≥0, where k is a Gaussian kernel function, ∀x,y∈U; thus, xkδ is a kernel neighborhood granule of x, where
(4)xkδ=0kx,y<δ,kx,ykx,y≥δ.Definition 7.
Given a kernel neighborhood approximation spaceU,A,k,δ, δ≥0, where k is a kernel function, for any fuzzy subset X⊆FU; we define the lower and upper approximations of X on the space U,A,k,δ, respectively, as follows:
(5)N¯X=xi∈Xxkδ⊆X,N¯X=xi∈Xxkδ⋂X≠∅.
The method defined above is crisp and has no noise tolerance ability. Here, we propose an improved model that is called variable precision lower and upper approximation.Definition 8.
Given a kernel neighborhood approximation spaceU,A,k,δ, δ≥0, where k is a kernel function, for any fuzzy subset X⊆FU; the variable precision lower and upper approximations of X are defined as follows, where ∣∗∣ denotes the cardinality of the specified set:
(6)KN¯αX=xi∈Xxkδ⋂Xxkδ≥α,KN¯αX=xi∈Xxkδ⋂Xxkδ>1−α.Then, 0.5≤α≤1 as in [22].Example 1.
Consider a kernel neighborhood approximation spaceU,A,k,δ, where U=u1,u2,u3,u4,u5, A=a1,a2,a3, δ=0.5, α=0.9, and k is a kernel function. The details are listed in Table 1.Table 1
Approximation space.
ID
a1
a2
a3
u1
0.1
0.2
0.3
u2
0.2
0.2
0.3
u3
0.3
0.1
0.1
u4
0.8
0.7
0.8
u5
0.9
0.9
0.7The relation matrix is presented in Table2. Each line is the kernel neighborhood granule of ui.Table 2
Relation matrix.
ID
u1
u2
u3
u4
u5
u1
1
0.90
0.74
0
0
u2
0.90
1
0.78
0
0
u3
0.74
0.78
1
0
0
u4
0
0
0
1
0.88
u5
0
0
0
0.88
1Given a fuzzy setX=0.9/u1,0.8/u2,0.9/u3,0.3/u4,0.1/u5, we obtain KN¯αX=KN¯αX=u1,u2,u3.Definition 9.
Given a kernel neighborhood approximation spaceU,A,k,δ, where δ≥0 and k is a kernel function, for any fuzzy subset X⊆FU, the positive, negative, and boundary regions of X in the space U,A,k,δ are, respectively, expressed as follows:
(7)POSX=KN¯X,NEGX=U−KN¯X,BNX=KN¯X−KN¯X.Theorem 1.
Given a kernel neighborhood approximation spaceU,A,k,δ, where δ1≤δ2≤0, then
(1)
xkδ1⊇xkδ2,
(2)
KN¯δ1X⊆KN¯δ2X,
(3)
KN¯δ1X⊆KN¯δ2X.Proof.
Ifδ1≤δ2≤0, then xkδ1⊇xkδ2. Assuming that xkδ1⊆X, then xkδ2⊆X. That is, x∈KN¯δ2X if x∈KN¯δ1X but not vice versa. Similarly, we obtain KN¯δ1X⊆KN¯δ2X.


## 3.2. Kernel Neighborhood Decision System

A kernel neighborhood approximation space is called a variable precision kernel neighborhood decision system which is denoted byU,C∪D,k,δ,α. C and D are condition and decision features, respectively.Definition 10.
Consider a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. We, respectively, define the lower and upper approximations of D with respect to feature subset B as follows:
(8)KN¯BαD=⋃i=1nKN¯BαDi,KN¯BαD=⋃i=1nKN¯BαDi.Definition 11.
Consider a variable precision kernel neighborhood decision system,U,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. The positive, negative, and boundary regions of D in the space U,A,k,δ are, respectively, defined as follows:
(9)POSBD=KN¯BD,NEGBD=U−KN¯BD,BNBD=KN¯BD−KN¯BD.
The size of the boundary increases the uncertainty in the decision system. The samples in the boundary generally have the same condition features but belong to different decision classes. This discrepancy leads to the poor classification performance of the employed algorithms. We should select a proper feature subset that increases the size of the positive region and decreases the size of the boundary region.Definition 12.
Consider a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. The dependency degree of D relative to B is defined as follows:
(10)γB=POSBDU.
The dependency degree reflects the approximating power of a condition feature set. A higher approximation degree means that the samples that are described by feature subsetB are more consistent with decision D.Theorem 2.
Given a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where C1⊆C2⊆C, then
(1)
xkδ,C1⊇xkδ,C2,
(2)
KN¯C1D⊆KN¯C2D,
(3)
POSC1D⊆POSC2D.Proof.
Ifδ1⊆δ2⊆0, then xkδ,C1⊇xkδ,C2. Assuming that xkδ,C1⊆D, then xkδ,C2⊆D. That is, x∈KN¯C2D if x∈KN¯C1D but not vice versa. Similarly, we obtain POSC1D⊆POSC2D.


## 4. Feature Selection Based on KNRS

One of the most important applications of the information rough sets theory is the evaluation of the classification power of the attributes. In this section, we define the significance of the feature subsets. The feature selection algorithm is also discussed.Definition 13.
Consider a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where δ≥0, 0.5≤α≤1, and k is a kernel function. Suppose B⊆C and U/D=D1,D2,…,Dn. The significance of feature a in B is defined as follows:
(11)SIGa,B,D=γBD−γB−aD.
SIGa,B,D is used to evaluate the significance of attribute a in subset B. That is, a is an important feature if it increases the dependency degree of subset B. As mentioned in Definition 11, we need subset B to be more consistent with decision D. Thus, we define the feature selection algorithm as follows.It is impractical to obtain the optimal subset of features from2n−1 candidates through an exhaustive search, where n is the number of features. We use a forward greedy search algorithm, which is usually more efficient than a standard brute-force exhaustive search [4]. That is, one starts with an empty set of attributes and adds features to the subset of selected attributes one by one. Each selected attribute maximizes the increment of significance of the current subset.Corollary 1.
Given a variable precision kernel neighborhood decision systemU,C∪D,k,δ,α, where C1⊆C2⊆C, if x∈POSC1D, thenx∈POSC2D.Proof.
Please refer to the proof of Theorem2.
Corollary1 shows that an object must belong to the positive region with respect to the feature sets (such as C2) if the object belongs to the positive region with respect to the feature subset (such as C1, where C1⊆C2⊆C). Therefore, it is unnecessary to consider every object when computing the positive region. Then, we can obtain a fast feature selection algorithm by improving Algorithm 1.Algorithm 1: Feature selection based on a kernel neighborhood rough set (FSKNRS).
Input: decision systemU,C∪D,k,δ,α and stopping threshold ε
Output: selected featuresred
1.red←∅
2. whilered≠C
3.  for eachai∈C−red
4.   computePOSred∪aiD/U
5.   computeSIGai,red,D=POSred∪aiD/U−POSredD/U
6.  end for
7. find the maximal significance and the corresponding attributeai
8.  ifSIGai,red,D>ε
9.red←red∪ai
10.  else
11.   exit while
12.  end if
13. end while
14. returnred


## 5. Experimental Analysis

In this section, we evaluate the effectiveness of KNRS through a series of experiments. The data sets are downloaded from the UCI machine learning repository (http://archive.ics.uci.edu/ml/index.php) as [3] and are described in Table 3. The numerical attributes of the samples are linearly normalized as follows:
(12)x=x−xminx−maxxmin,where xmin and xmax are the bounds of the given attribute. Two popular machine leaning algorithms, namely, CART and RBF SVM, are used to evaluate the quality of the selected features. The experiments are run in a 10-fold cross-validation mode. The parameters of CART and RBF SVM are set to the default values (by using MATLAB toolkit osu_svm3.00).Table 3
Data description [3].
ID
Data
Samples
Features
Class
1
Wine
178
13
3
2
wdbc
569
31
2
3
Heart
270
13
2
4
Glass
214
9
7
5
Anneal
798
38
6


### 5.1. Discussion of the Parameters

The neighborhood metricδ and precision degree α are two key parameters that affect the feature selection results. Here, δ and α are analyzed through a series of experiments. We set δ from 0.05 to 0.95 with a step size of 0.1. We set the precision degree α from 0.5 to 0.95 with a step size of 0.05. The evaluation criterion is the classification accuracy in the selected feature subset with parameters δ and α.According to Figures1–5, on most of the data sets, higher precision is achieved in a larger area when δ is between 0.5 and 0.95 and α is between 0.5 and 0.75. That is, the FNRS model is feasible and stable in most cases.Figure 1
Classification accuracy withδ and α on wine.Figure 2
Classification accuracy withδ and α on wdbc.Figure 3
Classification accuracy withδ and α on glass.Figure 4
Classification accuracy withδ and α on heart.Figure 5
Classification accuracy withδ and α on anneal.


### 5.2. Effectiveness of the Fast Feature Selection

We propose feature selection based on a kernel neighborhood rough set (Algorithm1: FSKNRS) and a fast version (Algorithm 2: FFSKNRS). We evaluated the run times of the two methods. The results are listed in Table 4. The fast feature selection algorithm that is based on KNRS yields a better performance than Algorithm 1 is.Algorithm 2: Fast feature selection based on a kernel neighborhood rough set (FFSKNRS).
Input: decision systemU,C∪D,k,δ,α and stopping threshold ε
Output: selected featuresred
1.red←∅, S←U
2. whilered≠C
3.  for eachai∈C−red
4.   for each objectoj∈S
5.    ifoj∈POSD
6.S←S−oj
7.   end for
8.   computePOSred∪aiD/U by the object subset U−S
9.   computeSIGai,red,D=POSred∪aiD/U−POSredD/U
10.  end for
11.  find the maximal significance and the corresponding attributeai
12.  ifSIGai,red,D>ε
13.red←red∪ai
14.  else
15.   exit while
16.  end if
17. end while
18. returnredTable 4
Comparison of run times (sec).
Data
Algorithm1: FSKNRS
Algorithm2: FFSKNRS
Wine
0.27
0.15
wdbc
10.4
2.43
Glass
0.31
0.23
Heart
0.64
0.21
Anneal
13.01
3.33
Average
4.93
1.27


### 5.3. Comparison of the Effectiveness in Feature Selection

In this section, we select KRS [5], NRS [22], and neighborhood entropy (NE) [28] as the comparison models with KNRS. The feature subsets that are selected by different algorithms are presented in Table 5. The features are presented in the order in which they were added to the feature space.Table 5
Subsets of the features selected with KNRS, KRS, NRS, and NE.
Data
KNRS
KRS
NRS
NE
Wine
12, 13, 2, 1
13, 10, 7, 1, 5, 2, 12
13, 10, 7, 6, 1
7, 1, 11, 4
wdbc
29, 22, 23, 26
24, 29, 23, 13, 22, 26, 10
9, 23, 22, 26, 31, 13
24, 29, 23
Glass
3, 9, 4, 5, 1, 2, 7
N/A
8, 4, 7, 5, 9, 3, 1, 2
3, 7, 4, 9, 5, 1
Heart
3, 13, 12, 11, 2
2, 3,12, 11, 13, 7, 1
10, 2, 8, 4, 1, 3, 5
13, 12, 3, 10, 1, 4, 5
Anneal
12, 3, 8, 5
5, 12, 7, 3, 1
12, 5, 3, 7, 9, 13
12, 3, 8, 5
Average
4.8
6.5
6.4
4.8The KNS model cannot obtain any subsets of the data set “glass.” Most of the feature subsets are slightly different. A small difference in feature quality may lead to a completely different ranking. The orders of the feature subsets reflect the relative significance of the features in terms of the corresponding measures. Therefore, the large differences among these selected features are due to the differences in the qualities of the feature measures.Then, we build classification models with the selected features and test their classification performance based on a 10-fold cross-validation. The average value and standard deviation are used to measure the classification performance. We compare KNRS, KRS, NRS, and NE in Tables6 and 7, where the learning algorithms of CART and RBF SVM are used to evaluate the selected features.Table 6
Classification accuracies based on CART (%).
Data
KNRS
KRS
NRS
NE
Wine
90.00 ± 8.20
87.50 ± 9.73
91.11 ± 8.76 (∗)
89.93 ± 8.57
wdbc
92.11 ± 3.60
91.93 ± 3.22
93.84 ± 4.43
93.85 ± 2.38 (∗)
Glass
66.93 ± 11.44 (∗)
0
66.90 ± 11.44
65.13 ± 14.65
Heart
81.85 ± 7.90 (∗)
75.93 ± 5.01
68.52 ± 7.25
80.00 ± 7.65
Anneal
95.55 ± 1.82
96.44 ± 1.27
98.99 ± 0.82 (∗)
95.55 ± 1.82
Average
85.288
70.36
83.872
84.892Table 7
Classification accuracies based on RBF SVM (%).
Data
KNRS
KRS
NRS
NE
Wine
97.78 ± 3.88 (∗)
97.7 ± 3.88
97.22 ± 3.93
94.93 ± 4.12
wdbc
96.85 ± 2.70
96.84 ± 1.81
97.20 ± 1.69 (∗)
96.66 ± 1.75
Glass
67.86 ± 11.70 (∗)
0
67.8 ± 11.70
64.08 ± 11.22
Heart
82.22 ± 7.96
81.11 ± 8.98
77.78 ± 10.33
84.07 ± 7.82 (∗)
Anneal
94.77 ± 2.22
96.33 ± 1.18
98.66 ± 0.71 (∗)
94.77 ± 2.22
Average
87.896
74.396
87.732
86.902The comprehensive correlation results are shown in Table8. The number of wins for KNRS, KRS, NRS, and NE are 4, 0, 4, and 2, respectively. KNRS achieves the highest average classification accuracy by using fewer features. It is thus concluded that KNRS outperforms the other feature measures. We can interpret the results from two aspects. For the kernel model (KRS), the lower approximation is computed by the “min” operation. Then, the decision on a sample is dependent on the nearest sample. This procedure can lead to a decision error if the nearest sample is a noise point. We obtain a lower classification accuracy when there is considerable data noise in the samples. In contrast, neighborhood-based binary relations can only be expressed in terms of 0 or 1. Neighborhood models (such as NRS and NE) cannot describe the fuzziness delicately like the kernel model. KNRS is a better choice because it integrates the advantages of the kernel and neighborhood models.Table 8
Comprehensive correlations of the models.
Data
Win
Average accuracy
Average number of features
KNRS
4
86.59
4.8
KRS
0
72.37
6.5
NRS
4
85.80
6.4
NE
2
85.89
4.8


## 5.1. Discussion of the Parameters

The neighborhood metricδ and precision degree α are two key parameters that affect the feature selection results. Here, δ and α are analyzed through a series of experiments. We set δ from 0.05 to 0.95 with a step size of 0.1. We set the precision degree α from 0.5 to 0.95 with a step size of 0.05. The evaluation criterion is the classification accuracy in the selected feature subset with parameters δ and α.According to Figures1–5, on most of the data sets, higher precision is achieved in a larger area when δ is between 0.5 and 0.95 and α is between 0.5 and 0.75. That is, the FNRS model is feasible and stable in most cases.Figure 1
Classification accuracy withδ and α on wine.Figure 2
Classification accuracy withδ and α on wdbc.Figure 3
Classification accuracy withδ and α on glass.Figure 4
Classification accuracy withδ and α on heart.Figure 5
Classification accuracy withδ and α on anneal.


## 5.2. Effectiveness of the Fast Feature Selection

We propose feature selection based on a kernel neighborhood rough set (Algorithm1: FSKNRS) and a fast version (Algorithm 2: FFSKNRS). We evaluated the run times of the two methods. The results are listed in Table 4. The fast feature selection algorithm that is based on KNRS yields a better performance than Algorithm 1 is.Algorithm 2: Fast feature selection based on a kernel neighborhood rough set (FFSKNRS).
Input: decision systemU,C∪D,k,δ,α and stopping threshold ε
Output: selected featuresred
1.red←∅, S←U
2. whilered≠C
3.  for eachai∈C−red
4.   for each objectoj∈S
5.    ifoj∈POSD
6.S←S−oj
7.   end for
8.   computePOSred∪aiD/U by the object subset U−S
9.   computeSIGai,red,D=POSred∪aiD/U−POSredD/U
10.  end for
11.  find the maximal significance and the corresponding attributeai
12.  ifSIGai,red,D>ε
13.red←red∪ai
14.  else
15.   exit while
16.  end if
17. end while
18. returnredTable 4
Comparison of run times (sec).
Data
Algorithm1: FSKNRS
Algorithm2: FFSKNRS
Wine
0.27
0.15
wdbc
10.4
2.43
Glass
0.31
0.23
Heart
0.64
0.21
Anneal
13.01
3.33
Average
4.93
1.27


## 5.3. Comparison of the Effectiveness in Feature Selection

In this section, we select KRS [5], NRS [22], and neighborhood entropy (NE) [28] as the comparison models with KNRS. The feature subsets that are selected by different algorithms are presented in Table 5. The features are presented in the order in which they were added to the feature space.Table 5
Subsets of the features selected with KNRS, KRS, NRS, and NE.
Data
KNRS
KRS
NRS
NE
Wine
12, 13, 2, 1
13, 10, 7, 1, 5, 2, 12
13, 10, 7, 6, 1
7, 1, 11, 4
wdbc
29, 22, 23, 26
24, 29, 23, 13, 22, 26, 10
9, 23, 22, 26, 31, 13
24, 29, 23
Glass
3, 9, 4, 5, 1, 2, 7
N/A
8, 4, 7, 5, 9, 3, 1, 2
3, 7, 4, 9, 5, 1
Heart
3, 13, 12, 11, 2
2, 3,12, 11, 13, 7, 1
10, 2, 8, 4, 1, 3, 5
13, 12, 3, 10, 1, 4, 5
Anneal
12, 3, 8, 5
5, 12, 7, 3, 1
12, 5, 3, 7, 9, 13
12, 3, 8, 5
Average
4.8
6.5
6.4
4.8The KNS model cannot obtain any subsets of the data set “glass.” Most of the feature subsets are slightly different. A small difference in feature quality may lead to a completely different ranking. The orders of the feature subsets reflect the relative significance of the features in terms of the corresponding measures. Therefore, the large differences among these selected features are due to the differences in the qualities of the feature measures.Then, we build classification models with the selected features and test their classification performance based on a 10-fold cross-validation. The average value and standard deviation are used to measure the classification performance. We compare KNRS, KRS, NRS, and NE in Tables6 and 7, where the learning algorithms of CART and RBF SVM are used to evaluate the selected features.Table 6
Classification accuracies based on CART (%).
Data
KNRS
KRS
NRS
NE
Wine
90.00 ± 8.20
87.50 ± 9.73
91.11 ± 8.76 (∗)
89.93 ± 8.57
wdbc
92.11 ± 3.60
91.93 ± 3.22
93.84 ± 4.43
93.85 ± 2.38 (∗)
Glass
66.93 ± 11.44 (∗)
0
66.90 ± 11.44
65.13 ± 14.65
Heart
81.85 ± 7.90 (∗)
75.93 ± 5.01
68.52 ± 7.25
80.00 ± 7.65
Anneal
95.55 ± 1.82
96.44 ± 1.27
98.99 ± 0.82 (∗)
95.55 ± 1.82
Average
85.288
70.36
83.872
84.892Table 7
Classification accuracies based on RBF SVM (%).
Data
KNRS
KRS
NRS
NE
Wine
97.78 ± 3.88 (∗)
97.7 ± 3.88
97.22 ± 3.93
94.93 ± 4.12
wdbc
96.85 ± 2.70
96.84 ± 1.81
97.20 ± 1.69 (∗)
96.66 ± 1.75
Glass
67.86 ± 11.70 (∗)
0
67.8 ± 11.70
64.08 ± 11.22
Heart
82.22 ± 7.96
81.11 ± 8.98
77.78 ± 10.33
84.07 ± 7.82 (∗)
Anneal
94.77 ± 2.22
96.33 ± 1.18
98.66 ± 0.71 (∗)
94.77 ± 2.22
Average
87.896
74.396
87.732
86.902The comprehensive correlation results are shown in Table8. The number of wins for KNRS, KRS, NRS, and NE are 4, 0, 4, and 2, respectively. KNRS achieves the highest average classification accuracy by using fewer features. It is thus concluded that KNRS outperforms the other feature measures. We can interpret the results from two aspects. For the kernel model (KRS), the lower approximation is computed by the “min” operation. Then, the decision on a sample is dependent on the nearest sample. This procedure can lead to a decision error if the nearest sample is a noise point. We obtain a lower classification accuracy when there is considerable data noise in the samples. In contrast, neighborhood-based binary relations can only be expressed in terms of 0 or 1. Neighborhood models (such as NRS and NE) cannot describe the fuzziness delicately like the kernel model. KNRS is a better choice because it integrates the advantages of the kernel and neighborhood models.Table 8
Comprehensive correlations of the models.
Data
Win
Average accuracy
Average number of features
KNRS
4
86.59
4.8
KRS
0
72.37
6.5
NRS
4
85.80
6.4
NE
2
85.89
4.8


## 6. Conclusion and Future Work

As we know that, genetic algorithms and neural networks are famous mathematical model for pattern recognition, machine learning, and intelligent control. However, rough sets theory has also been successfully applied to these fields [5, 13, 15]. In this study, we define a novel model, the kernel neighborhood rough sets model, which integrates the advantages of the neighborhood and kernel models. Moreover, the model is used in the problem of feature selection. The parameters of KNRS are also discussed in detail. Then, we evaluate the effectiveness of the fast feature selection algorithm. A comparison of the results shows that our model yields a better performance than classic models.There are two potential directions for future work. First, many other rough sets models can be incorporated into KNRS, such as fuzzy rough sets and Pawlak rough sets. Evaluating the significance of features by using the confluent modes is an important issue. Second, the application of our model to big data is necessary. Consequently, the development of a version of KNRS within a distributed framework requires further attention.



---

*Source: 1342562-2018-08-23.xml*