An improved D-S evidence theory based neighborhood rough classification approach

Abstract

Neighborhood classifier, a common classification method, is applied in pattern recognition and data mining. The neighborhood classifier mainly relies on the majority voting strategy to judge each category. This strategy only considers the number of samples in the neighborhood but ignores the distribution of samples, which leads to a decreased classification accuracy. To overcome the shortcomings and improve the classification performance, D-S evidence theory is applied to represent the evidence information support of other samples in the neighborhood, and the distance between samples in the neighborhood is taken into account. In this paper, a novel attribute reduction method of neighborhood rough set with a dynamic updating strategy is developed. Different from the traditional heuristic algorithm, the termination threshold of the proposed reduction algorithm is dynamically optimized. Therefore, when the attribute significance is not monotonic, this method can retrieve a better value, in contrast to the traditional method. Moreover, a new classification approach based on D-S evidence theory is proposed. Compared with the classical neighborhood classifier, this method considers the distribution of samples in the neighborhood, and evidence theory is applied to describe the closeness between samples. Finally, datasets from the UCI database are used to indicate that the improved reduction can achieve a lower neighborhood decision error rate than classical heuristic reduction. In addition, the improved classifier acquires higher classification performance in contrast to the traditional neighborhood classifier. This research provides a new direction for improving the accuracy of neighborhood classification.

Keywords

Attribute reduction D-S evidence theory neighborhood classification rough set

1 Introduction

Granular computing simulates human thinking and solves large-scale and complex problems, which has broad application prospects in fields such as artificial intelligence, knowledge discovery, and image processing. As the main tools of granular computing, rough set, soft set, and fuzzy set are combined to solve uncertain decision-making problems. For example, the possibility m-polar fuzzy soft set is the combination of soft set and fuzzy set [15]. This model effectively handles the uncertainties during the decision-making problems. Soft β-rough set was generated by the combination of soft set and rough set. Through soft β-rough approximation and soft β-rough topology, this model determines the people most likely to be infected with new coronary pneumonia [9]. Based on fuzzy soft set, a new fuzzy soft expert system for lung cancer disease prediction is proposed [16].

Many strategies are applied to solve uncertainty and ambiguity issues [3]. The rough set is also applied to describe and address uncertain problems. The classical rough set model was first proposed by Polish mathematician Z. Pawlak [40, 41] in the last century. Using upper and lower approximation sets, the target concept can be characterized. Rough set theory has been further developed in recent years. For example, the target concept is integrated with topology to construct the generalized approximation operator [10]. In addition, rough set has also been researched in practical applications. By means of j-neighborhoods, complementary j-neighborhoods and j-adhesions, several types of j-covering approximations based rough set is proposed. The application of the novel types of covering-based rough set to the rheumatic fever is developed [20]. Although the rough set has developed to a certain degree, when encountering complex real-world issues, the traditional rough set is limited due to the exact demands of the definitions of lower and upper approximation sets. To address complex issues such as multisource data, incomplete data, numeric data, and fuzzy data, the classical rough set method has been further developed.

(1) Classical rough set cannot reflect the tolerance of the concept. To fill this gap, Yao et al. first combined probabilistic rough set and decision-making and proposed the Decision-Theoretic Rough Set (DTRS) model [35]. In light of DTRS, the framework of three-way decision was proposed [35], and many research results has been achieved [27]. For example, Huang et al. proposed a novel three-way neighborhood decision model to deal with incomplete hybrid information [25]. Wang et al. proposed a three-way decision model based on cumulative prospect theory [31]. Li et al. adopted a deep neural network framework for three-way decision image data analysis [11].

(2) Considering different levels of granularity, many research results have been achieved [39, 19]. For example, Zhu et al. developed a multi-granularity distance learning technique and learned distance variable in different granular spaces [21]. Huang et al. proposed two novel MG-IF-DTRS models, which are the fusion of multi-granulation, intuitionistic fuzzy, and risk decision [1]. Xu et al. constructed a novel information fusion approach, and then the uncertainty measures of fusion progression were studied [32]. Kong et al. also studied the multi-granulation method of information fusion in multi-source decision information system [26].

(3) As far as fuzzy environment is concerned, fuzzy rough set has been proposed, and some related issues have been investigated [6, 7]. For example, Ye et al. proposed a novel fuzzy rough set method, which handled multi-criteria decision-making problems under uncertain and fuzzy environments [13]. Zhan et al. developed a covering-based variable precision fuzzy rough set model to address the problem of misclassifications in decision-making [14]. Wang et al. proposed four uncertainty measures by introducing the notion of self-information to fuzzy rough approximations [5].

(4) In some cases, the data is presented in an incomplete form, because data measurement errors often occur in practical applications. Therefore, how to use rough set theory to mine knowledge from incomplete information systems is a popular topic [8]. For instance, Luo et al. proposed a novel dynamic probabilistic rough set model for the sake of processing incomplete data [2]. Qian et al. introduced a multi-granulation notion to an information system, which applies multiple tolerance relations to approximate the target concept [37]. Luo et al. studied several semantics issues between incomplete information system and rough set theory [12]. Moreover, Yang et al. performed systematic and landmark work on incomplete information systems and rough set theory, of which several achievements are referred to by researchers in the field of granular computing and knowledge discovery [34].

In addition, as far as numeric data are considered, the traditional approach usually involves transforming them into discrete data, which usually excludes some important information. To solve this issue, Lin introduced the neighborhood notion to rough set theory and proposed a novel rough set model [30]. Hu et al. redefined and interpreted Lin’s neighborhood rough set model from the perspective of the granular computing of mixed data [22]. In light of the k-nearest neighbor classification approach, Hu et al. proposed a rough set-based classification strategy called the neighborhood classifier [23]. Neighborhood rough set is an effective tool to tackle practical problems, and many scholars focus on this popular research topic [17, 18]. The classical neighborhood rough set also has several shortcomings. The classification method is simple, and the classification performance of attribute reduction reduct is insufficient. To solve these problems, some scholars have conducted additional research. For example, Yang et al. fused the pseudolabel to the neighborhood relationship to improve the performance of the neighborhood rough set model [33]. Wang et al. constructed new uncertainty measures in a neighborhood rough set framework and adopted it for attribute reduction [4]. These studies optimize the neighborhood relation and attribute reduction part of the neighborhood rough set, add restrictions to the neighborhood relation, and propose a new attribute importance index in the attribute reduction part. It should be noted that the attribute reduction and classification processes based on neighborhood rough set still have several shortcomings. The detail issues are as follows:

First, traditional heuristic attribute reduction may be insufficient when the attribute significance index is not monotonous. Because its termination threshold is fixed, it cannot retrieve an optimal value of classification. The neighborhood decision error rate (NDER) is selected as an example, as shown in Fig. 1.

Fig. 1

NDER variation with attribute increasing.

When the NDER value of the subset decreases to the threshold, i.e., the curve reaches point A, the algorithm is terminated. Compared with point B, the neighborhood decision error of A is far larger than that of point B. Therefore, the classical heuristic algorithm lacks good reduction performance for this category of data.

Second, in the traditional neighborhood classifier, majority voting strategy is widely applied, which is based on the number of samples in the neighborhood. It is simple, however, the distribution of samples has not been considered. As shown in Fig. 2, according to the traditional voting mechanism, one may assign the label of x to “+”. However, from the distribution of data in the neighborhood, one may realize that the data points with label “Δ” are closer than other data points with label “+”. From this point of view, the class label of x may be “Δ”. Therefore, the data distribution information should be considered when classification method is constructed.

Fig. 2

Majority voting strategy.

For the issues mentioned above, this paper puts forward a novel solution in two stages. On the one hand, a dynamic updating method is proposed to improve the attribute reduction algorithm when the attribute significance index is nonmonotonic. The termination threshold of the proposed reduction algorithm is dynamically optimized based on the searched values. Therefore, this method can retrieve the optimal value according to the termination threshold. Different from the traditional reduction set, which maintains the same classification effect as the original attribute set, the reduction set obtained by this algorithm can achieve a classification performance far superior to the original attribute set. The reduction set obtained by the proposed algorithm can better represent the resolution of the original attribute set and obtain good classification performance. On the other hand, to describe the closeness between samples, D-S evidence theory is also an effective method. For example, Denoeux first applied D-S evidence theory to the kNN algorithm [29]. Then, Zhang et al. further developed D-S evidence theory and applied it to an ensemble classification algorithm to improve the performance of the k-nearest neighbor classification method [38]. In light of the advantage of D-S evidence theory, this paper introduces D-S evidence theory into data information fusion. Through the information distribution of samples in the neighborhood, different classes of sample information are fused to obtain the evidence support information of samples to improve the accuracy of classification. Then, an improved D-S evidence theory-based neighborhood rough classification approach is discussed. The improved classification method refers to more information, which is more scientific and comprehensive, and can effectively improve the accuracy of classification.

The main structure of this paper is organized as follows: Section 2 mainly introduces the neighborhood rough set approach and its classifier implementation method. Section 3 proposes a novel classification method based on a neighborhood rough set that includes the implementations of attribute reduction and D-S neighborhood classification. Section 4 presents several comparisons and analyses the proposed algorithm of this paper through nine UCI datasets. Finally, we summarize the full paper in Section 5.

2 Preliminary knowledge

2.1 Neighborhood rough set and classification mechanism

Generally, the structural data of information system can be defined as IS =< U, AT, V, f >, where U is a non-empty set of samples, i.e., U = {x₁, x₂, . . . , x_n}, and it is called universe. AT is the set of attributes, and can be denoted as: AT = {a₁, a₂, . . . , a_m, d}, in which conditional attribute set C = {a₁, a₂, . . . , a_m} and decision attribute set D = {d} are considered simultaneously. V is the value range of attribute a, and f is the attribute mapping, f : U × a → V_a.

Definition 1. Let IS be an information system, ∀x_i ∈ U, B ⊆ C, the neighborhood of x_i with respect to attribute subspace B is defined as: $δ_{B} (x_{i}) = {x_{j} | x_{j} \in U, Δ_{B} (x_{i}, x_{j}) \leq δ}$ (1) where Δ_B is the distance function between any two samples with respect to attribute subspace B, and Δ satisfies the following properties:

Δ (x_i, x_j) ≥0;

Δ (x_i, x_j) =0, if x_i = x_j;

Δ (x_i, x_j) = Δ (x_j,x_i);

Δ (x_i, x_k) ≤ Δ (x_i, x_j) + Δ (x_j, x_k).

In this paper, the radial basis function kernel distance is selected. This is also known as Gaussian kernel distance. In this framework, the distance between any two samples x_i, x_j is written as

$\begin{matrix} Δ_{B}^{R} (x_{i}, x_{j}) \\ = 1 - exp (- \frac{\sum_{l = 1}^{| B |} {(f (x_{i}, a_{l}) - f (x_{j}, a_{l}))}^{2}}{2 σ^{2}}) \end{matrix}$ (2) where σ is a parameter. The value of the RBF kernel function decreases with distance and is between 0 and 1. Based on radial basis function kernel distance, the neighborhood rough set can be defined as follows.

Definition 2. Let IS be an information system, for arbitrary X ⊆ U, ∀x_i ∈ U, B ⊆ AT, the neighbor-hood of x_i in the attribute subspace B is denoted as δ_B (x_i), then the neighborhood based lower and upper approximation sets can be defined as: ${\underline{B}}_{δ} (X) = {x_{i} \in U : δ_{B} (x_{i}) \subseteq X}$ (3) ${\bar{B}}_{δ} (X) = {x_{i} \in U : δ_{B} (x_{i}) \cap X \neq \emptyset}$ (4)

In the neighborhood classification process, let δ_B (x_i) be the neighborhood of testing sample x_i, let x_j become the sample within neighborhood δ_B (x_i), and let its class label be expressed as ω_j. In terms of majority voting strategy, the class label of x_i can be obtained as follows: $ω = arg max_{ω_{m}} \sum_{x_{j} \in δ_{B} (x_{i})} I (ω_{j} = ω_{m})$ (5) where I (·) is the indicator function. Specific cases of majority voting are indicated in Example 1.

Example 1. Figure 2 shows a process of neighborhood classification in the universe space, where d₁ is labeled with “plus” and d₂ is labeled with “triangle”. Assume that sample x is the testing sample and that the circle neighborhood is assigned to sample x. The radius of neighborhood is δ and there are two classes of data in the neighborhood. In accordance with the majority voting strategy, testing sample x is classified into “plus” set.

2.2 D-S evidence theory

D-S evidence theory is a reasoning theory, that was first proposed by Dempster in 1967 and further developed by Shafer in 1976. Hence, it is also known as Dempster-Shafer’s evidence theory [29]. Suppose Ω is an exhaustive set of all possible values of variable x, and the elements in Ω are mutually exclusive. In evidence theory, Ω is called frame of discernment.

Definition 3. Suppose that A is an arbitrary subset of the discernibility frame Ω, which is corresponding to a number M ∈ [0, 1] and it satisfies the following condition:

$M (φ) = 0$ (6) $\sum_{A \subseteq Ω} M (A) = 1$ (7)

In above definition, M is called the basic probability distribution function of 2^Ω and M (A) is the basic probability number of A. In addition, for any A ⊆ Ω, if M (A) ≠0, then A is a focal elementof M.

In virtue of the basic probability distribution function, the belief function Bel and the plausibility function Pl of the proposition can be defined as follows:

$Bel (A) = \sum_{B \subseteq A} M (B)$ (8) $Pl (A) = 1 - Bel (\bar{A}) = \sum_{B \cap A \neq φ} M (B)$ (9)

Bel (A) represents the overall trust degree of A, and Pl (A) indicates the degree of not against A.

3 Classification learning method

3.1 An improved attribute reduction approach

Attribute reduction is one of the core issues of rough set theory [24]. By deleting redundant attributes, the data are reduced in dimension to achieve the purpose of data processing. Candidate attributes are selected by comparing the significance of attributes. Generally, approximate quality and information entropy are common indicators of attribute significance. Hu et al. considered that the samples in the boundary domain are not necessarily misclassified, and only a few samples are misclassified [24]. Therefore, in light of neighborhood rough set, Hu et al. proposed the neighborhood classification error rate notion (NDER) [24] from the perspective of sample error classification, and used it as an index to assess attribute subspace.

Let δ_B (x_i) be the neighborhood of sample x_i, and P (ω_j|δ_B (x_i)) (j = 1, 2, . . . , c) is the class probability of δ_B (x_i) under class ω_j. Owing to the class probability, the class label of sample x_i can be assigned, i.e., if $P (ω_{l} | δ_{B} (x_{i})) = max_{j} P (ω_{j} | δ_{B} (x_{i}))$ , then the class of sample x_i can be labeled as ω_l, which is expressed as: ND (x_i) = ω_l. Obviously, ND (x_i) = ω (x_i) means that the predicted class label of sample x_i is as same as the ground truth. Based on these discussions, one can determine that the loss function of sample misclassification is as follows: $λ (ω (x_{i}) | ND (x_{i})) = {\begin{matrix} 0, ω (x_{i}) = ND (x_{i}) \\ 1, ω (x_{i}) \neq ND (x_{i}) \end{matrix}$ (10)

Therefore, the neghborhood error rate can be denoted as follows: $NDER = \frac{1}{n} \sum_{i = 1}^{n} λ (ω (x_{i}) | ND (x_{i}))$ (11) where n is the number of samples.

In light of the neighborhood decision error rate, Hu et al. further proposed a novel attribute reduction approach, which is based on the neighborhood decision error rate [24]. The detailed definition can be found as follows.

Definition 4. Let IS be an information system, for arbitrary A⊆AT, A is regarded as a neighborhood decision error rate reduction of information system if and only if:

NDER_A ≤ NDER_AT;

∀A′ ⊂ A, then NDER_A′ > NDER_A.

The reduct set defined above deletes the redundant attributes in the information system, and reduces the neighborhood decision error rate of attribute set. In an information system, the reduced attribute subspace based on the neighborhood decision error rate can completely replace the original attribute set.

Having the definition of neighborhood decision error rate reduction in mind, ∀B ⊆ AT, a ∈ AT - B, the significance of attribute A with respect to attribute subset B is $SIG (a, B, D) = {NDER}_{B} - {NDER}_{B \cup {a}}$ (12)

To achieve the above attribute significance, the traditional heuristic algorithm can be applied. The classical heuristic algorithm is a commonly employed method for attribute reduction. In this strategy, attributes are selected by finding the maximum attribute significance. The classical heuristic algorithm is shown in Algorithm 1.

Table 4

Algorithm 1. Classical heuristic attribute reduction based on NDER.
Input: Information system IS =< U, AT, V, f >, neighborhood radius δ.
Output: Reduction attribute set B_reduct.
1. ∅ → B_reduct.
2. Do
3. ∀a_i ∈ C - B_reduct, compute SIG (a_i, B_reduct, D)
4. Select the maximum SIG (a_i, B_reduct, D) and
corresponding attributes a_j
5. If SIG (a_i, B_reduct, D) >0, then
B_reduct = B_reduct ∪ {a_i}
End If
6. Compute NDER_{B _reduct}.
7. Until NDER_{B _reduct} ≤ NDER_C
8. While \|B_reduct\| ≥ 2 and NDER_{B _reduct} ≤ NDER_C
∀c∈B, compute NDER_{B_reduct-c}
If NDER_{B_reduct-c} ≤ NDER_C
B_reduct = B_reduct - {c}
End If
End While
9. Return B_reduct.

The time complexity of Algorithm 1 is O (|U|² × |AT|²) where the length of attributes tested is |AT| and the complexity of calculating significance of candidate attributes is O (|U|² × |AT|). The classical heuristic algorithm is employed in most situations. However, there are some shortcomings of Algorithm 1 in some cases, which can be indicated in Example 2.

Example 2. In Fig. 2, suppose that the attribute set AT ={ a₁, a₂, a₃, a₄, a₅, a₆, a₇ }, and the NDER of AT is 0.58. The NDER of attribute set A ={ a₁, a₂ } is 0.58 which is the same as that of AT. In traditional heuristic algorithm, it means that the attribute A is the qualified set. However, the NDER of attribute set B ={ a₁, a₂, a₃ } is 0.47 which is lower than that of A. In the classical heuristic algorithm, the reduct of B is inaccessible because the iteration of the search has ceased at A.

In the rough set model, many indexes of attribute significance do not change monotonically with the increase of attributes, as does the neighborhood error rate. To obtain the attribute reduct set of this category of dataset, an improved heuristic reduction is developed by dynamically updating the standard to gain the minimum value of the neighborhood error rate. The algorithm of searching attribute reduct is shown in Algorithm 2.

Table 5

Algorithm 2. Improved heuristic attribute reduction based on NDER.
Input: Information system IS =< U, AT, V, f >, neighborhood radius δ.
Output: Reduction attribute set B_reduct.
1. ∅ → B_reduct.
2. Do
3. ∀a_i ∈ C - B_reduct, compute SIG (a_i, B_reduct, D)
4. Select the maximum SIG (a_i, B_reduct, D) and
corresponding attributes a_j
5. If SIG (a_i, B_reduct, D) >0, then
B_reduct = B_reduct ∪ {a_i}
End If
6. Compute NDER_{B _reduct}.
7. If NDER_{B _reduct} ≤ NDER_C
8. NDER_C = NDER_{B _reduct}
9. End If
10. If NDER_{B _reduct} > NDER_C & SIG (a_i, B_reduct, D) <0
11. NDET_{B _reudct} = NDET_{B _reudct} - {a_i}
12. Break
13. End If
14. Until \|B_redict\| = \|C\|
15. While \|B_reduct\| ≥ 2 and NDER_{B _reduct} ≤ NDER_C
∀ c ∈ B, compute NDER_{B_reduct-c}
If NDER_{B_reduct-c} ≤ NDER_C
B_reduct = B_reduct - {c}
End If
End While
16. Return B_reduct.

The time complexity of Algorithm 2 is the same as that of Algorithm 1 where the consumption is O (|U|² × |AT|²). Compared with the classical heuristic reduction algorithm, Algorithm 2 does not increase the time consumption but effectively improves the attribute reduction performance. The improved reduction set is deeper and more representative for attribute set data dimension reduction. It is able to effectively obtain regional extrema and greatly improve the progress of classification.

Example 3. Following Example 2, suppose the NDER value of attribute set B ={ a₁, a₂, a₃ } is 0.47. In Algorithm 2, the NDER of A is higher than that of B, and then the benchmark index is updated to 0.47. Furthermore, considering attribute set C ={ a₁, a₂, a₃, a₄ }, the NDER of C is 0.36 while the NDER of attribute set D ={ a₁, a₂, a₃, a₄, a₅ }, is 0.44. Since the NDER of B is higher than C, the benchmark index is updated as 0.36. However, when the NDER of D is higher than 0.36, the iteration ceases, and attribute set C is the qualified set. Compared with Algorithm 1, set C has better classification performance than attribute set A.

3.2 D-S neighborhood rough classification

The neighborhood classification method proposed by Hu et al. adopts the majority voting strategy, which ignores the case of different distributions of data. In this section, the majority voting strategy is altered under the framework of neighborhood classification, and the neighborhood rough classification method based on D-S evidence theory is proposed. The key to applying evidence theory to classification is to judge samples belonging to the same category based on the similarity of the samples. Within the k-nearest neighbor classification framework, Denoeux developed a novel approach to represent the relationship between categories and neighborhood samples [29].

For a testing sample, assume that π ={ X₁, X₂, … X_d } is the partition of universe U on decision attribute D, and d is the number of categories. ω_i ={ 1, 2, … d } is the class label of the sample. For any sample x_i in the neighborhood, its class label ω_i is marked as q. Then, (x_i, X_q) can be used as independent evidence to support the classification of x_t. The evidence information contained in it can be defined as follows: $M^{t, i} ({X_{q}}) = α = α_{0} \cdot e^{- γ_{q} \cdot Δ^{2}}$ (13) $M^{t, i} (π) = 1 - α$ (14) where 0 < α₀ < 1, γ_q > 0, Δ represents the kernel distance of radial basis function.

There are multiple samples in the neighborhood of testing sample x_t, and the evidence support of multiple samples for x_t is fused by evidence combination. Let $δ_{B}^{q} (x_{t})$ denote the sample with class q in the neighborhood of sample. In light of D-S evidence theory, the evidence support of the sample set to x_t can be expressed as $M_{q}^{t} = \oplus x_{i} \in δ_{B}^{q} (x_{t}) M^{t, i}$ , that is: $M_{q}^{t} ({X_{q}}) = 1 - \prod_{x_{i} \in δ_{B}^{q} (x_{t})} (1 - α_{0} \cdot e^{- γ q \cdot (Δ (x_{t}, x_{i}))^{2}})$ (15) $M_{q}^{t} (π) = 1 ∏_{x_{i} \in δ_{B}^{q} (x_{t})} (1 α_{0} \cdot e^{γ q \cdot (Δ (x_{t}, x_{i}))^{2}})$ (16)

Similarly, if different types of evidence $M_{q}^{t}$ are fused, then the evidence support $M^{t} = \oplus_{q = 1}^{d} M_{q}^{t}$ provided by all objects in the neighborhood can be obtained, and can be specifically expressed as follows:

$\begin{matrix} M^{t} ({X_{q}}) = \frac{M_{q}^{t} ({X_{q}}) \prod_{r \neq q} M_{r}^{t} (π)}{K} \\ q = 1, \dots, d \end{matrix}$ (17) $M^{t} (π) = \frac{\prod_{q = 1} M_{r}^{t} (π)}{K}$ (18) where K is a normalization factor, and its expression is presented as follows: $K = \sum_{q = 1}^{d} ({X_{q}}) \cdot \prod_{r \neq q} M_{q}^{t} (π) + \prod_{q = 1}^{d} M_{q}^{t} (π)$ (19)

On these basis notions, the belief function and plausibility function of sample x_t to a certain class X_q can be obtained ${Bel}^{t} ({X_{q}}) = M^{t} ({X_{q}})$ (20) ${Pl}^{t} ({X_{q}}) = M^{t} ({X_{q}}) + M^{t} (π)$ (21)

Let δ_B (x_i) be the neighborhood of sample x_i. x_j is the sample within the neighborhood, and its class label is ω_j. Then, due to D-S evidence theory, the class label of x_i can be obtained as follows: $ω = arg max_{ω_{i}} {Bel}^{t} ({X_{i}}) .$ (22)

In light of the above discussions, the detailed process of D-S evidence theory based neighborhood rough classification can be shown in Algorithm 3.

Table 6

Algorithm 3. Neighborhood rough classifier driven by D-S evidence theory
Input: Information system IS =< U, AT, V, f >, neighborhood radius δ, test sample x_t;
Output: Class label of x_t.
1. Compute universe U on decision attributes
\ D: π ={ X₁, X₂, … , X_d };
2. According to Algorithm 2, achieve attribute
\ reduction subset B;
3. ∀x_i, x_t ∈ U, the distance Δ_B (x_i, x_t) is computed;
4. In light of the distance, the neighborhood
\ of x_t can be obtained: δ_B (x_t);
5. ∀X_q ∈ π, compute $M_{q}^{t} ({X_{q}})$ and $M_{q}^{t} (π)$ ;
6. Compute M^t ({ X_q }) and M^t (π), Bel^t ({ X_q }) can be
obtained;
7. Due to the formula $ω = arg max_{ω_{i}} {Bel}^{t} ({X_{i}})$ , gain
\ the class label of sample x_t;
8. Output the class label of sample x_t

The time complexity of Algorithm 3 is mainly reflected in calculating the distance between the sample to be tested and the training sample. The calculated information is based on the distance. According to the above discussion, the time complexity of Algorithm 3 is O (|U| · |AT| · d).

4 Experimental analysis

To verify the effectiveness of the proposed attribute reduction method and D-S classification approach, several datasets are employed from UCI database. The detail information of datasets are shown in Table 1.

Table 1
Datasets from UCI

ID Datasets Instances Attributes Decision classes

1 Cardiotocography 2126 21 10

2 Contraceptive Method Choice 1473 9 3

3 Ionosphere 351 34 2

4 Page Blocks Classification 5473 10 5

5 Seeds 210 6 3

6 Sonar 208 17 2

7 Statlog (Image Segmentation) 2310 18 7

8 Steel Plates Faults 1941 27 2

9 WDBC 569 30 2

ID	Datasets	Instances	Attributes	Decision classes
1	Cardiotocography	2126	21	10
2	Contraceptive Method Choice	1473	9	3
3	Ionosphere	351	34	2
4	Page Blocks Classification	5473	10	5
5	Seeds	210	6	3
6	Sonar	208	17	2
7	Statlog (Image Segmentation)	2310	18	7
8	Steel Plates Faults	1941	27	2
9	WDBC	569	30	2

In this paper, the data are scattered by using 5-fold cross-validation. The dataset is divided into two parts: training set and testing set. The detailed process is as follows. Each dataset is partitioned into 5 disjoint groups such that U ={ U₁, U₂, U₃, U₄, U₅ }. For example, in the first round of calculation, U₂ ∪ U₃ ∪ U₄ ∪ U₅ is called the training set which is the supervised dataset used to learn the neighborhood rough set model and neighborhood classifier. U₁ is regarded as the testing set which is used to assess the classification prediction performance of the proposed method. The classification error rate is the measure employed in the experiment. In summary, the experiment is expected to verify that the proposed approach can improve the classification performance.

First, the performance of the improved attribute reduction approach is presented. Figure 3 shows the neighborhood decision error rate (NDER) values of the original, classical and improved reduction versions, with increasing universe. The red line represents the NDER values of improved attribute reduction, the blue line represents the NDER values of the classical heuristic reduction, and the black line denotes the NDER values of the original data. It is not difficult to note that, no matter how the universe increases, the improved reduction can achieve a lower NDER than the original dataset and heuristic reduction set, respectively. For example, in the dataset Sonar, the value of NDER from the original data is higher than 0.45 while the value of NDER deprived from classical reduction is higher than 0.2 and the value of NDER derived from improved reduction is lower than 0.2. The NDER derived from improved reduction is far lower than that of classical reduction and original data, which means that the improved reduction is able to avert several errors of classification. By observing nine datasets in Fig. 3, it is not difficult to find that the improved attribute reduction greatly improves the performance of neighborhood classification.

Fig. 3

NDER values comparisons of different reduction algorithm.

The results of nine datasets deprived from different reduction algorithms are recorded in Table 2. In other words, through different algorithms, the size of attributes and classification performance are shown. It is easy to reach the following two remarks.

Table 2

Attribute reduction comparison with different reduction algorithms

Data ID	Attributes number			NDER↓
	Original	Classical	Improved	Original	Classical	Improved
1	21	5.2±0.8	9.4±0.5	0.3208±0.0177	0.2894±0.0167	0.2255±0.0018
2	9	4.4±1.5	5.6±1.3	0.5397±0.0153	0.5390±0.0148	0.5324±0.0126
3	34	1.0±0.0	5.4±1.1	0.3782±0.0228	0.2507±0.0169	0.1652±0.0153
4	10	3.2±0.8	5.2±0.8	0.0642±0.0035	0.0626±0.0039	0.0597±0.0028
5	6	3.2±0.4	4.0±0.0	0.1083±0.0243	0.1048±0.0284	0.0833±0.0238
6	17	1.8±0.8	5.6±3.2	0.4074±0.0445	0.3605±0.0579	0.2392±0.0237
7	18	10.6±0.5	12.4±1.3	0.1645±0.0075	0.1630±0.0079	0.1594±0.0073
8	27	7.6±2.2	10.6±3.8	0.2477±0.0241	0.2428±0.0307	0.2342±0.0112
9	30	1.0±0.0	5.2±0.8	0.5347±0.0108	0.1151±0.0053	0.0378±0.0052

(1) From the viewpoint of attribute numbers, it is not difficult to note that both the improved reduction set and the heuristic reduction set have reduced the dimension of the dataset. However, compared with classical heuristic reduction, the improved reduction set retains further depth for attribute set reduction. For example, in the first dataset, the original dataset has 21 attributes while the classical reduction set owns 5 attributes, and the improved reduction set obtain 9 attributes. Compared with the classical reduction method, the improved approach can break through the original constraints, and find a more in-depth and representative attribute reduct set that gains better discrimination ability than the original set. Therefore, the reduction set can possess better classification performance.

(2) By comparing the values of NDER, it is easy to find that the neighborhood decision error rate of the improved reduction set is lower than that of the classical heuristic reduction set. For instance, in the third dataset, the value of NDER from the original data is approximately 0.37 when the value of NDER from classical reduction is approximately 0.2, and that from improved reduction is only approximately 0.16. Therefore, it is shown that the classification performance of the improved reduction method is better than that of the classical reduction approach. Moreover, in the first dataset, the fluctuation range of NDER deprived from improved reduction is 0.0228 while the range of NDER from classical reduction is 0.0169, and the range of original data is 0.0153. It is shown that the fluctuation of the neighborhood error rate of the improved reduction set is smaller and more stable than that of the classical heuristic reduction set. Therefore, the improved reduction algorithm improves the attribute reduction performance.

In the neighborhood classification comparisons, the results of the reduction set and original set in the traditional neighborhood classifier [23] and D-S improved classifier are shown in Fig. 4. For example, in the dataset Cardiotocography, the black curve is the classification accuracy of the data employed by the D-S improved classifier. The red curve is that of data classified by the neighborhood classifier. The black curve is always above the red curve regardless of whether the dataset is reduced. It is not difficult to find that the classification accuracy of the D-S neighborhood classifier is higher than that of the traditional neighborhood classifier. The neighborhood classification assessment of several datasets is shown in Fig. 4. The improved attribute set has higher classification performance than the original attribute set.

Fig. 4

Classification accuracies comparison with different algorithms.

Finally, as we all know, the classical neighborhood classifier ignores the distribution of samples in the neighborhood, resulting in a decrease in classification performance, so this method is proposed to solve this problem. To prove the effectiveness of the DSNEC algorithm, it is necessary to judge whether this method improves the classification performance effectively. The proposed classification algorithm DSNEC is further compared with several state-of-the-art classification approaches, such as: the classical voting based kNN (voting-kNN), weighted kNN [36], DS-kNN [29] and NEC [23]. Voting-kNN is represented as the classical kNN algorithm using a voting strategy. This algorithm is suitable for multiclassification problems with high accuracy and insensitivity to outliers. In the weighted kNN, the distance of each sample is considered. The classification accuracy is improved by adding weight to the distance. In the DS-kNN, k-neighbor evidence support is obtained through D-S evidence theory to improve the performance of the kNN algorithm. In the neighborhood classifier, the neighborhood is determined by distance and classification is performed by the principle of majority strategy. It is widely applied in classification applications. These classification methods are excellent and widely

applied in practical classification tasks. The proposed method in this paper is further improved according to common algorithms. These classification methods are employed as a comparative experiment which can further improve the rationality and persuasion of the experiment. Apparently, the first three classification methods are related with the parameter of k. In this paper, without loss of generality, the value of k is set as $\sqrt{n} / 2$ , where n is the number of samples in training set. The nine UCI datasets mentioned above are selected as samples, and these classification algorithms are employed as the comparison strategies of the proposed method. The average classification accuracy of the experimental results is presented in Table 3. It is not difficult to conclude that, within these nine datasets, the proposed DSNEC can achieve the highest classification accuracy in most datasets. For example: for the first dataset, the average classification accuracy of DSNEC is 0.98, which is much higher than the accuracy of kNN of 0.95. The accuracy of weighted-kNN is 0.96, the accuracy of DS-kNN is 0.95, and the accuracy of NEC is 0.97. For the third dataset, the average classification accuracy of DSNEC is 0.92, which is better than the accuracy of kNN of 0.87. The accuracy of weighted-kNN is 0.89, the accuracy of DS-kNN is 0.89, and the accuracy of NEC is 0.88. These data show that the classification performance of DSNEC is far superior to that of several other algorithms. This also indicates the effectiveness of the improvement in NEC. Although weighted-kNN, DS-kNN or NEC achieves the highest accuracy in some datasets, this is not a common result. Moreover, in this case, the classification results of DSNEC are also superior to those of the other algorithms. Therefore, it can be demonstrated that the proposed D-S neighborhood classification can effectively improve the performance of neighborhood classification.

Table 3

Classification comparison with several popular classification algorithms Data ID

	Voting-kNN	Weighted-kNN	DS-kNN	NEC	DSNEC
1	0.9578	0.9672	0.9598	0.9768	0.9887
2	0.7612	0.7895	0.7745	0.7675	0.7745
3	0.8789	0.8974	0.8976	0.8856	0.9287
4	0.9814	0.9879	0.9879	0.9832	0.9949
5	0.8742	0.8842	0.8912	0.8876	0.8998
6	0.7089	0.7385	0.7356	0.7243	0.7484
7	0.9785	0.9542	0.9875	0.9941	0.9941
8	0.6421	0.6637	0.6837	0.6542	0.6789
9	0.9578	0.9665	0.9687	0.9712	0.9712

5 Conclusion

Neighborhood classifier is a common classification method but it also has some shortcomings. The distribution of samples in the neighborhood is ignored, which decreases the accuracy of classification. To solve this problem, this paper introduces D-S evidence theory into the neighborhood classifier. Then a novel classification approach based on D-S evidence theory is proposed. In this approach, D-S evidence theory is applied to describe the closeness of samples. According to the distribution of samples in the neighborhood, the evidence information of samples is obtained which improves the classification performance. In addition, the dynamic updating strategy is applied to improve the attribute reduction algorithm. When the attribute significance index is not monotonous, the classical heuristic algorithm cannot retrieve the optimal value. However, in the improved algorithm, the termination threshold of the reduction algorithm is continuously optimized and then the method can achieve an effective value. Compared with traditional methods, the reduction set obtained by the proposed method has superior classification performance. Experimental results show that the improved reduction algorithm can not only improve the classification effect, but also represents the resolution of the original attribute set. In contrast to several common classification algorithms, the classification performance of the improved method based on D-S evidence theory is superior. Through the proposed method, the effect of classification is improved. In future work, this method can be applied to a tourism demand forecasting model, and improve the accuracy of time-series forecasting [28]. To further improve the method, the following directions can be followed:

In this paper, neighborhood decision error rate is employed as an index of attribute significance, other non-monotonic indexes will be studied in the future.

The improved reduction method has obtained better performance than the traditional heuristic algorithm. The maximum value will be obtained by the improved method.

Footnotes

Acknowledgments

The authors would like to express the sincere appreciation to the editor and anonymous reviewers for their insightful comments, which greatly improve the quality of this paper. This work is supported by the Natural Science Foundation of China (Nos. 62006128, 61976120, 62076111), Jiangsu Innovation and Entrepreneurship Program, Natural Science Foundation of Jiangsu Province (No. BK20191445), Natural Science Foundation of Jiangsu Higher Education Institutions of China (No. 20KJB520009), Qing Lan Project of Jiangsu Province, Science and Technology Project of Nantong City (No. JC2020141), Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. SJCX21_1447) and College Students’ Innovative Entrepreneurial Training Plan Program (No. 202110304024Z).

References

Huang

, Li

, Feng

, et al. Inclusion measure-based multi-granulation intuitionistic fuzzy decision-theoretic rough sets and their application to ISSA, Knowledge-Based Systems 138 (2017), 220–231.

Luo

, Li

and Yao

Dynamic probabilistic rough sets with incomplete data, Information Sciences 417 (2017), 39–54.

Ritwika

, Santonab

and Shankar

An integrated D-MARCOS method for supplier selection in an iron and steel industry, Decision Making: Applications in Management and Engineering 3(2) (2020), 49–69 .

Wang

, Huang

, Shao

, et al. Feature selection based on neighborhood self-information, IEEE Transactions on Cybernetics 50(9) (2020), 4031–4042.

Wang

, Huang

, Ding

, et al. Attribute reduction with fuzzy rough self-information measures, Information Sciences 549 (2021), 68–86.

Liang

, Liu

and Quan

Information aggregation of hesitant fuzzy interval sets for multicriteria decision-making, Computing in Science & Engineering 20(2) (2018), 38–51.

Liang

, Xu

, Liu

, et al. Method for three-way decisions using ideal TOPSIS solutions at Pythagorean fuzzy information, Information Sciences 435 (2018), 282–295.

Liu

, Liang

and Wang

A novel three-way decision model based on incomplete information system, Knowledge-Based System 91 (2016), 32–45.

EI-Bably

M.K.

and EI-Atik , Abd El Fattah Soft β-rough sets and their application to determine COVID-19, Turkish Journal of Mathematics 45 (2021), 1133–1148.

10.

EI-Bably

M.K.

, Fleifel

K.K.

and Embaby

O.A.

Topological approaches to rough approximations based on closure operators, Granular Computing (2021). https://doi.org/10.1007/s41066-020-00247-x.

11.

, Zhang

, Zhou

, et al. Cost-sensitive sequential three-way decision modeling using a deep neural network, International Journal of Approximate Reasoning 85 (2017), 68–78.

12.

Luo

, Fujita

, Yao

, et al. On modeling similarity and three-way decision under incomplete information in rough set theory, Knowledge-Based Systems 191 (2020), 105251.

13.

, Zhan

, Ding

, et al. A novel fuzzy rough set model with fuzzy neighborhood operators, Information Sciences 544 (2020), 266–297.

14.

Zhan

, Jiang

and Yao

Covering-based variable precision fuzzy rough sets with PROMETHEE-EDAS methods, Information Sciences 538 (2020), 314–336.

15.

Ahmed

, Mostafa

, Sheng and Hong

Possibility m-polar fuzzy soft sets and its application in decision-making problems, Journal of Intelligent & Fuzzy Systems 37(1) (2019), 929–940.

16.

Ahmed

, Mostafa , Sheng

and Hong,

A new expert system in prediction of lung cancer disease based on fuzzy soft sets, Soft Computing 24 (2020), 14179–14207.

17.

Liu

, Yang

, Yu

, et al. Rough set based semi-supervised feature selection via ensemble selector, Knowledge-Based System 165 (2019), 282–296.

18.

Liu

, Yang

, Fujita

, et al. An efficient selector for multi-granularity attribute reduction, Information Sciences 505 (2019), 457–472.

19.

Yang

, Xu

, Zhang

, et al. Multi-granulation method for information fusion in multi-source decision information system, International Journal of Approximate Reasoning 122 ( (2020), 47–65.

20.

Nawar

A.S.

, El-Bably

M.K.

and Abd

El-A.

El Fattah, Certain types of coverings based rough sets with application, Journal of Intelligent & Fuzzy Systems 39(3) (2020), 3085–3098.

21.

Zhu

, Hu

, Zuo

, et al. Multi-granularity distance metric learning via neighborhood granule margin maximization, Information Sciences 282 (2014), 321–331.

22.

, Yu

, Liu

, et al. Neighborhood rough set based heterogeneous feature subset selection, Information Sciences 178 (2008), 3577–3594.

23.

, Yu

and Xie

Neighborhood classifiers, Expert Systems with Applications 34 (2008), 866–876.

24.

, Pedrycz

, Yu

, et al. Selecting discrete and continuous features based on neighborhood decision error minimization, IEEE Transactions on System Man and Cybernetics, Part B 40 (2010), 137–150.

25.

Huang

, Li

, Huang

, et al. Incremental three-way neighborhood approach for dynamic incomplete hybrid data, Information Sciences 541 (2020), 98–122.

26.

Kong

, Zhang

, Xu

, et al. Attribute reducts of multi-granulation information system, Artificial Intelligence Review 53 (2020), 1353–1371.

27.

Zhang

, Huang

and Wang

A novel sequential three-way decision model with autonomous error correction, Knowledge-Based System 212 (2021), 106526.

28.

Haresh

, Kriti

and Samarjit

A rough set approach for forecasting models, Decision Making: Applications in Management and Engineering 3(1) (2020), 1–21.

29.

Denoeux

A-nearest neighbor classification rule based on Dempster-Shafer theory, IEEE Transactions on System Man and Cybernetics 25 (1995), 804–813.

30.

Lin

Neighborhood systems and relational databases, Proceedings of the 1988 ACM sixteenth annual conference on Computer science-CSC ’88, Atlanta, Georgia, USA, ACM Press: (1998), 725–726.

31.

Wang

, Li

, Zhang

, et al. A three-way decision model based on cumulative prospect theory, Information Sciences 519 (2020), 74–92.

32.

and Yu

A novel approach to information fusion in multi-source datasets: A granular computing viewpoint, Information Sciences 378 (2017), 410–423.

33.

Yang

, Liang

, Yu

, et al. Pseudo-label neighborhood rough set: Measures and attribute reductions, International Journal of Approximate Reasoning 105 (2019), 112–129.

34.

Yang

and Yang

Incomplete information system and rough set theory: Model and attribute reductions, Science Press: Springer (2012).

35.

Yao

and Wang

A decision theoretic framework for approximating concepts, International Journal of Man-Machine Studies 37 (1992), 793–809.

36.

, Zhao

, Chi

, et al. Design and implementation of a parallel geographically weighted-nearest neighbor classifier, Computer Geoscience 127 (2019), 111–122.

37.

Qian

, Liang

and Dang

Incomplete multi-granulation rough set, IEEE Transactions on Systems Man & Cybernetics 40 (2010), 420–431.

38.

Zhang

, Gao

, Wang

, et al. A novel ensemble method for-nearest neighbor, Pattern Recognition 85 (2019), 13–25.

39.

Jiang

, Dou

, Song

, et al. Data-guided multi-granularity selector for attribute reduction, Applied Intelligence 51 (2021), 876–888.

40.

Pawlak

Rough set theory and its applications to data analysis, Cybernetics and Systems 29 (1998), 661–688.

41.

Pawlak

Rough sets and intelligent data analysis, Information Sciences 147 (2002), 1–12.