# Pseudolabel Decision-Theoretic Rough Set

Authors: Xun Wang; Wendong Zhang; Dun Liu; Hualong Yu; Xibei Yang; Xin Yang
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

In decision-theoretic rough set (DTRS), the decision costs are used to generate the thresholds for characterizing the probabilistic approximations. Similar to other rough sets, many generalized DTRS can also be formed by using different binary relations. Nevertheless, it should be noticed that most of the processes for calculating binary relations do not take the labels of samples into account, which may lead to the lower discrimination; for example, samples with different labels are regarded as indistinguishable. To fill such gap, the main contribution of this paper is to propose a pseudolabel strategy for constructing new DTRS. Firstly, a pseudolabel neighborhood relation is presented, which can differentiate samples by not only the neighborhood technique but also the pseudolabels of samples. Immediately, the pseudolabel neighborhood decision-theoretic rough set (PLNDTRS) can be constructed. Secondly, the problem of attribute reduction is explored, which aims to further reduce the PLNDTRS related decision costs. A heuristic algorithm is also designed to find such reduct. Finally, the clustering technique is employed to generate the pseudolabels of samples; the experimental results over 15 UCI data sets tell us that PLNDTRS is superior to DTRS without using pseudolabels because the former can generate lower decision costs. Moreover, the proposed heuristic algorithm is also effective in providing satisfied reducts. This study suggests new trends concerning cost sensitivity problem in rough data analysis.


---

## Body

## 1. Introduction

Different from classical rough set and its various generalizations [1–3], decision-theoretic rough set (DTRS) [4–6] has been demonstrated to be useful in many cost related problems [7–11]. Such model introduces not only the Bayesian decision but also the minimal risk into the construction of lower and upper approximations. Immediately, the thresholds for defining approximations have clear explanations.From the viewpoint of granular computing [12], binary relation provides us with an effective mechanism for realizing information granulation. Therefore, the model of DTRS is used to characterize the relationship between the result of information granulation (information granules) and decision classes through considering the problem of costs. Consequently, DTRS may contain two important aspects: (1) information granulation and (2) decision costs. On the one hand, different types of information granulations may be used to construct different models [4, 13–19]. For example, the classical DTRS is formed based on the indiscernibility relation [4]; similar to Pawlak’s rough set, such model is only useful in analyzing categorical data; Li et al. [16] have proposed a neighborhood based DTRS, in which the result of information granulation is expressed by neighborhoods of samples; Song et al. [15] have proposed a fuzzy based DTRS, in which the result of information granulation is reflected by fuzzy relation. These representative results are suitable for analysing data with continuous or even mixed values. On the other hand, different problems related to costs also provide us with more directions for studying DTRS [20, 21]. For instance, Dou et al. [10] have taken the characteristics of multiplicity and variability of costs into consideration; they proposed three different multicost based DTRS; Liang et al. [22] have introduced the interval-value based cost into DTRS, which enlarges the application range of DTRS; to solve the problem of multiclass decision effectively, Yang et al. [23] have proposed a sequential three-way approach.From discussions above, it should be emphasized that though different binary relations have been used in constructing DTRS, few of them take the labels of samples into account. Therefore, the ability to discriminate may not perform well. This is mainly because for any two samples their similarity is only determined by attributes or features regardless of the labels of such two samples. Consequently, samples with different labels may meet the requirement of binary relation, which will produce the extra decision costs [5].What is more, in the studies of neighborhood systems [24–26], is that using distance functions is a very common and useful method. For example, Hu et al. [27] proposed a neighborhood based rough set model, which is easy to understand and implement; Li et al. [16] have replaced the equivalence class used in traditional DTRS by neighborhood relation. Correspondingly, we can use the neighborhood relation in this paper.Take a binary classification task as an example (see Figure1). There are 5 samples in the neighborhood of sample y except y itself. That is, any one of the samples xi (i=1,2,3,4,5) and y satisfies the neighborhood relation. In addition, samples x1,x2, and x3 have the label of triangle, while x4 and x5 have the label of square. Obviously, y will be misclassified if the majority rule is employed; such misclassification may produce additional cost if the cost sensitivity problem is considered. To reduce this type of the misclassification and the corresponding cost, a natural thinking is to use a smaller scale of neighborhood [28]. However, it does not always work. For example, in Figure 1, if the value of radius keeps reducing, then it is possible that only x2 is in the neighborhood of y if the reflexivity is ignored. In this case, y will also be misclassified.Figure 1
A small example.Why reducing the value of radius is not always an effective way? This is mainly because the distance between samples is only determined by the condition attributes or features, while ignoring the label information of samples. The lower quality of attributes may not be good enough for providing better discrimination. From this point of view, new technique for measuring the similarity between samples, which considers the information provided by the labels, has become a necessity.As we all know, in rough set theory, decision attribute offers us the labels of samples. However, these labels cannot be directly used, mainly because the labels over decision attribute are used to generate decision classes for constructing approximations. It is unreasonable to approximately characterize the decision classes by using the information which is derived from the decision attribute itself. For such reason, new sources of the labels of samples should be considered. Fortunately, motivated by the results of pseudolabel strategy in unsupervised and semisupervised learning tasks [29–34], we know that the pseudolabels of samples provide us with another representation of labels. Therefore, it may be a useful attempt for us to introduce the pseudolabel strategy into DTRS.Figure2 reports the framework of our study. It must be emphasized that our research is based on neighborhood related DTRS. The reason is that neighborhood is suitable for dealing with complex data with simple structure. Furthermore, neighborhood offers us a natural structure of multigranularity with the variation of radii. Obviously, following Figure 2, our main contribution is the pseudolabel strategy. In other words, the neighborhood of sample is determined by not only the binary relation, but also the pseudolabels. Correspondingly, the superiority of the pseudolabel strategy is that it can take the labels of samples into account, which the discrimination of samples can be improved.Figure 2
The framework of this paper.The remainder of this paper is organized as follows. The basic knowledge about decision-theoretic rough set and neighborhood rough set is presented in Section2. In Section 3, the model of pseudolabel neighborhood decision-theoretic rough set (PLNDTRS) is proposed. To further reduce the decision costs, the problem of attribute reduction is explored in Section 4. In Section 5, not only the experimental comparisons will be presented, but also the effectiveness of our strategy will be analyzed. The paper is ended with conclusions and perspectives for future work in Section 6.


## 2. Preliminary Knowledge

### 2.1. Decision-Theoretic Rough Set

In this section, some basic notions about DTRS [5, 16] are presented. Similar to the introduction of other rough sets, the concept of decision system should be firstly described for simplifying the subsequent discussions.Definition 1.
A decision system can be represented asDS=<U,AT,d>, in which U={x1,x2,…,xn} is a nonempty finite set of samples, called the universe; AT is the set of condition attributes; d is the decision attribute. ∀x∈U, d(x) expresses the label of sample x, and a(x) denotes the value that x holds on condition attribute a (∀a∈AT).Given a decision systemDS, the classification task will be considered in this paper and then labels of samples are discrete. Consequently, an equivalence relation over d can be obtained such that IND(d)={(x,y)∈U×U:d(x)=d(y)}. Immediately, U/IND(d)={X1,X2,…,Xq} is regarded as the partition determined by IND(d). ∀Xk∈U/IND(d), Xk is the set of samples with same label and then it is referred to as the k-th decision class. Specially, the decision class which contains sample x is denoted by [x]d.To know what is DTRS, the following notions should be given. LetΩ = {X,~X} indicate that a sample x is in X or out of X, that is, the states of x. The conditional probability of x in X can be obtained such that Pro(X|[x])=|X∩[x]|/|[x]|, in which [x] is the information granule [35, 36] of x generated by using condition attributes and |X| is the cardinal number of set X. For example, the equivalence classes derived by the equivalence relation over condition attributes AT can be regarded as information granules.Furthermore,∀X⊆U, three actions in A={aP,aB,aN} indicate x belongs to X or x belongs to X possibly or x does not belong to X. Therefore, the loss function regarding the costs of three actions in two different states is given in Table 1. In Table 1, λ∗P(∗∈{P,B,N}) denote the costs for taking action aP, aB, or aN when the x actual belongs to X, and λ∗N(∗∈{P,B,N}) denote the costs for taking action aP, aB, or aN when the x actual does not belong to X.Table 1
The loss function regarding the costs of three actions in two states.
X ~ X aP λ P P λ P N aB λ B P λ B N aN λ N P λ N NFollowing the costs shown in Table1 and the conditional probability, the Bayesian costs for three different decisions can be defined as (1)RP=RaP∣x=λPP·ProX∣x+λPN·Pro~X∣x;RB=RaB∣x=λBP·ProX∣x+λBN·Pro~X∣x;RN=RaN∣x=λNP·ProX∣x+λNN·Pro~X∣x.Correspondingly, the following minimum-cost decision rules can be derived:(P)IfRP≤RBandRP≤RN,thenx∈POS(X);(B)IfRB≤RPandRB≤RN,thenx∈BND(X);(N)IfRN≤RPandRN≤RB,thenx∈NEG(X);where POS(X) denotes the positive region of X, BND(X) denotes the boundary region of X, and NEG(X) denotes the negative region of X. Samples in POS(X) indicate that these samples belong to X determinately, samples in BND(X) indicate that these samples belong to X possibly, and samples in NEG(X) indicate that these samples do not belong to X.SincePro(X∣[x])+Pro(~X∣[x])=1, we also assume a reasonable loss function with the conditions such that 0 ≤λPP≤λBP≤λNP and 0 ≤λNN≤λBN≤λPN; decision rules (P), (B), and (N) can be expressed as [10, 37]:(P)IfPro(X∣[x])≥αandPro(X∣[x])≥γ,thenx∈POS(X);(B)IfPro(X∣[x])≤αandPro(X∣[x])≥β,thenx∈BND(X);(N)IfPro(X∣[x])≤βandPro(X∣[x])≤γ,thenx∈NEG(X);where three parametersα, β, and γ are (2)α=λPN-λBNλPN-λBN+λBP-λPP;β=λBN-λNNλBN-λNN+λNP-λBP;γ=λPN-λNNλPN-λNN+λNP-λPP.In addition, if we assume the following condition for the loss function [5, 37]: (3)λNP-λBPλBN-λNN>λBP-λPPλPN-λBN,then we have 0≤β<γ<α≤1. In this case, the final decision rules associated with the conditional probability and thresholds can be obtained: (P)IfPro(X∣[x])≥α, then x∈POS(X);(B)Ifβ<Pro(X∣[x])<α, then x∈BND(X);(N)IfPro(X∣[x])≤β, then x∈NEG(X).If we denotep=Pro(X∣[x]), then we have the following Bayesian costs for three different rules: (4)Cost  of  positive  rule:p·λPP+1-p·λPN;Cost  of  boundary  rule:p·λBP+1-p·λBN;Cost  of  negative  rule:p·λNP+1-p·λNN.From discussions above, the decision-theoretic based lower and upper approximations ofX⊆U are(5)X_α,β=x∈U:ProX∣x≥α;(6)X¯α,β=x∈U:ProX∣x>β.The pair[X_(α,β),X¯(α,β)] is referred to as a decision-theoretic rough set of X, POS(X)=X_(α,β) is the decision-theoretic positive region of X, BND(X)=X¯(α,β)-X_(α,β) is the decision-theoretic boundary region of X, and NEG(X)=U-X¯(α,β) is the decision-theoretic negative region of X.


### 2.2. Neighborhood Rough Set

Neighborhood rough set is another generalization of classical rough set. There are two main advantages for neighborhood rough set: (1) it is suitable for dealing with continuous data or even mixed data, mainly because the neighborhood relation is constructed based on the consideration of distance between samples; (2) the scale of neighborhood provides us with a flexible technique to measure the granularity [38] and then the structure of multigranularity [39, 40] can be naturally formed.Definition 2.
Given a decision systemDS and a neighborhood radius δ∈(0,1], ∀A⊆AT, the neighborhood relation in terms of A can be defined as [27]:(7)δA=x,y∈U×U:ΔAx,y≤δ,∀x∈U; the neighborhood of x is then defined as (8)δAx=y∈U:ΔAx,y≤δ,where Δ is a metric function and the Euclidean distance is a widely accepted form such that (9)ΔAx,y=∑a∈Aax-ay2.Obviously, the neighborhood relation shown in Equation (7) is one of the binary relations; it is reflexive and symmetric. Moreover, it is not difficult to observe that the neighborhood relation produces neighborhood based information granule [41], in which samples are considered similar to the central sample. The size of the neighborhood is determined by the radius δ. If different values of δ are used, then different results of neighborhood relations will be generated. Generally speaking, smaller value of δ will generate finer neighborhood relation while greater value of δ will generate coarser neighborhood relation.Definition 3.
Given a decision systemDS, ∀X⊆U, and ∀A⊆AT, the neighborhood lower and upper approximations of X with respect to A are defined as(10)N_AX=x∈U:δAx⊆X;(11)N¯AX=x∈U:δAx∩X≠∅.The pair [N_A(X), N¯A(X)] is referred to as a neighborhood rough set of X.Proposition 4.
[27] Given a decision system DS and two radii such that δ1≤δ2, then we have δ1(x)⊆δ2(x) for each x∈U.Proposition 5.
[27] Given a decision system DS, ∀A⊆AT, ∀x∈U, and δ∈(0,1], then we have δAT(x)⊆δA(x).Proposition 6.
[27] Given a decision system DS, ∀A⊆AT, ∀x∈U, and δ∈(0,1], then we have N_A(X)⊆N_AT(X) and N¯A(X)⊇N¯AT(X).Propositions5 and 6 tell us that if the number of used attributes is increasing, then the size of the neighborhood will be reduced; it follows that the lower approximation will be expanded and the upper approximation will be narrowed.


### 2.3. Neighborhood Decision-Theoretic Rough Set

One of the main motivations of neighborhood decision-theoretic rough set (NDTRS) is that the classical DTRS can only be used to deal with categorical data. Therefore, to further expand the applications of DTRS, the information granule [x] in DTRS is replaced by neighborhood in NDTRS; that is, ∀A⊆AT; the conditional probability is Pro(X∣δA(x))=|X∩δA(x)|/|δA(x)|. Immediately, given a decision system DS, ∀X⊆U, and ∀A⊆AT, the neighborhood decision-theoretic based lower and upper approximations of X are [16](12)N_Aα,βX=x∈U:Pro(X∣δAx≥α;(13)N¯Aα,βX=x∈U:Pro(X∣δAx>β.Correspondingly, the positive, boundary and negative regions ofX are (14)POSAα,βX=N_Aα,βX;BNDAα,βX=N¯Aα,βX-N_Aα,βX;NEGAα,βX=U-N¯Aα,βX.


## 2.1. Decision-Theoretic Rough Set

In this section, some basic notions about DTRS [5, 16] are presented. Similar to the introduction of other rough sets, the concept of decision system should be firstly described for simplifying the subsequent discussions.Definition 1.
A decision system can be represented asDS=<U,AT,d>, in which U={x1,x2,…,xn} is a nonempty finite set of samples, called the universe; AT is the set of condition attributes; d is the decision attribute. ∀x∈U, d(x) expresses the label of sample x, and a(x) denotes the value that x holds on condition attribute a (∀a∈AT).Given a decision systemDS, the classification task will be considered in this paper and then labels of samples are discrete. Consequently, an equivalence relation over d can be obtained such that IND(d)={(x,y)∈U×U:d(x)=d(y)}. Immediately, U/IND(d)={X1,X2,…,Xq} is regarded as the partition determined by IND(d). ∀Xk∈U/IND(d), Xk is the set of samples with same label and then it is referred to as the k-th decision class. Specially, the decision class which contains sample x is denoted by [x]d.To know what is DTRS, the following notions should be given. LetΩ = {X,~X} indicate that a sample x is in X or out of X, that is, the states of x. The conditional probability of x in X can be obtained such that Pro(X|[x])=|X∩[x]|/|[x]|, in which [x] is the information granule [35, 36] of x generated by using condition attributes and |X| is the cardinal number of set X. For example, the equivalence classes derived by the equivalence relation over condition attributes AT can be regarded as information granules.Furthermore,∀X⊆U, three actions in A={aP,aB,aN} indicate x belongs to X or x belongs to X possibly or x does not belong to X. Therefore, the loss function regarding the costs of three actions in two different states is given in Table 1. In Table 1, λ∗P(∗∈{P,B,N}) denote the costs for taking action aP, aB, or aN when the x actual belongs to X, and λ∗N(∗∈{P,B,N}) denote the costs for taking action aP, aB, or aN when the x actual does not belong to X.Table 1
The loss function regarding the costs of three actions in two states.
X ~ X aP λ P P λ P N aB λ B P λ B N aN λ N P λ N NFollowing the costs shown in Table1 and the conditional probability, the Bayesian costs for three different decisions can be defined as (1)RP=RaP∣x=λPP·ProX∣x+λPN·Pro~X∣x;RB=RaB∣x=λBP·ProX∣x+λBN·Pro~X∣x;RN=RaN∣x=λNP·ProX∣x+λNN·Pro~X∣x.Correspondingly, the following minimum-cost decision rules can be derived:(P)IfRP≤RBandRP≤RN,thenx∈POS(X);(B)IfRB≤RPandRB≤RN,thenx∈BND(X);(N)IfRN≤RPandRN≤RB,thenx∈NEG(X);where POS(X) denotes the positive region of X, BND(X) denotes the boundary region of X, and NEG(X) denotes the negative region of X. Samples in POS(X) indicate that these samples belong to X determinately, samples in BND(X) indicate that these samples belong to X possibly, and samples in NEG(X) indicate that these samples do not belong to X.SincePro(X∣[x])+Pro(~X∣[x])=1, we also assume a reasonable loss function with the conditions such that 0 ≤λPP≤λBP≤λNP and 0 ≤λNN≤λBN≤λPN; decision rules (P), (B), and (N) can be expressed as [10, 37]:(P)IfPro(X∣[x])≥αandPro(X∣[x])≥γ,thenx∈POS(X);(B)IfPro(X∣[x])≤αandPro(X∣[x])≥β,thenx∈BND(X);(N)IfPro(X∣[x])≤βandPro(X∣[x])≤γ,thenx∈NEG(X);where three parametersα, β, and γ are (2)α=λPN-λBNλPN-λBN+λBP-λPP;β=λBN-λNNλBN-λNN+λNP-λBP;γ=λPN-λNNλPN-λNN+λNP-λPP.In addition, if we assume the following condition for the loss function [5, 37]: (3)λNP-λBPλBN-λNN>λBP-λPPλPN-λBN,then we have 0≤β<γ<α≤1. In this case, the final decision rules associated with the conditional probability and thresholds can be obtained: (P)IfPro(X∣[x])≥α, then x∈POS(X);(B)Ifβ<Pro(X∣[x])<α, then x∈BND(X);(N)IfPro(X∣[x])≤β, then x∈NEG(X).If we denotep=Pro(X∣[x]), then we have the following Bayesian costs for three different rules: (4)Cost  of  positive  rule:p·λPP+1-p·λPN;Cost  of  boundary  rule:p·λBP+1-p·λBN;Cost  of  negative  rule:p·λNP+1-p·λNN.From discussions above, the decision-theoretic based lower and upper approximations ofX⊆U are(5)X_α,β=x∈U:ProX∣x≥α;(6)X¯α,β=x∈U:ProX∣x>β.The pair[X_(α,β),X¯(α,β)] is referred to as a decision-theoretic rough set of X, POS(X)=X_(α,β) is the decision-theoretic positive region of X, BND(X)=X¯(α,β)-X_(α,β) is the decision-theoretic boundary region of X, and NEG(X)=U-X¯(α,β) is the decision-theoretic negative region of X.


## 2.2. Neighborhood Rough Set

Neighborhood rough set is another generalization of classical rough set. There are two main advantages for neighborhood rough set: (1) it is suitable for dealing with continuous data or even mixed data, mainly because the neighborhood relation is constructed based on the consideration of distance between samples; (2) the scale of neighborhood provides us with a flexible technique to measure the granularity [38] and then the structure of multigranularity [39, 40] can be naturally formed.Definition 2.
Given a decision systemDS and a neighborhood radius δ∈(0,1], ∀A⊆AT, the neighborhood relation in terms of A can be defined as [27]:(7)δA=x,y∈U×U:ΔAx,y≤δ,∀x∈U; the neighborhood of x is then defined as (8)δAx=y∈U:ΔAx,y≤δ,where Δ is a metric function and the Euclidean distance is a widely accepted form such that (9)ΔAx,y=∑a∈Aax-ay2.Obviously, the neighborhood relation shown in Equation (7) is one of the binary relations; it is reflexive and symmetric. Moreover, it is not difficult to observe that the neighborhood relation produces neighborhood based information granule [41], in which samples are considered similar to the central sample. The size of the neighborhood is determined by the radius δ. If different values of δ are used, then different results of neighborhood relations will be generated. Generally speaking, smaller value of δ will generate finer neighborhood relation while greater value of δ will generate coarser neighborhood relation.Definition 3.
Given a decision systemDS, ∀X⊆U, and ∀A⊆AT, the neighborhood lower and upper approximations of X with respect to A are defined as(10)N_AX=x∈U:δAx⊆X;(11)N¯AX=x∈U:δAx∩X≠∅.The pair [N_A(X), N¯A(X)] is referred to as a neighborhood rough set of X.Proposition 4.
[27] Given a decision system DS and two radii such that δ1≤δ2, then we have δ1(x)⊆δ2(x) for each x∈U.Proposition 5.
[27] Given a decision system DS, ∀A⊆AT, ∀x∈U, and δ∈(0,1], then we have δAT(x)⊆δA(x).Proposition 6.
[27] Given a decision system DS, ∀A⊆AT, ∀x∈U, and δ∈(0,1], then we have N_A(X)⊆N_AT(X) and N¯A(X)⊇N¯AT(X).Propositions5 and 6 tell us that if the number of used attributes is increasing, then the size of the neighborhood will be reduced; it follows that the lower approximation will be expanded and the upper approximation will be narrowed.


## 2.3. Neighborhood Decision-Theoretic Rough Set

One of the main motivations of neighborhood decision-theoretic rough set (NDTRS) is that the classical DTRS can only be used to deal with categorical data. Therefore, to further expand the applications of DTRS, the information granule [x] in DTRS is replaced by neighborhood in NDTRS; that is, ∀A⊆AT; the conditional probability is Pro(X∣δA(x))=|X∩δA(x)|/|δA(x)|. Immediately, given a decision system DS, ∀X⊆U, and ∀A⊆AT, the neighborhood decision-theoretic based lower and upper approximations of X are [16](12)N_Aα,βX=x∈U:Pro(X∣δAx≥α;(13)N¯Aα,βX=x∈U:Pro(X∣δAx>β.Correspondingly, the positive, boundary and negative regions ofX are (14)POSAα,βX=N_Aα,βX;BNDAα,βX=N¯Aα,βX-N_Aα,βX;NEGAα,βX=U-N¯Aα,βX.


## 3. Pseudolabel Neighborhood Decision-Theoretic Rough Set (PLNDTRS)

Though NDTRS uses the neighborhood relation to replace the indiscernibility relation for realizing information granulation, the derived neighborhoods are still closely related to the distances which are determined by the values of condition attributes or features. However, it is well known that the Euclidean distance does not always perform well for distinguishing samples, especially in high-dimensional data. Therefore, new techniques have become the necessary issues to be addressed.Following the construction of distance based neighborhood relation, that is, Equation (7), it is not difficult to observe that such strategy does not take the labels of samples into consideration. Therefore, it is possible that different samples with different labels may fall into the same neighborhood. From this point of view, if the labels of samples are used, then such situation may be relieved. Nevertheless, the raw labels of samples in decision system are not suitable for directly using, mainly because we cannot approximate the decision classes generated by decision attribute through using the label provided by the decision attribute itself. For such reason, we will further expand decision system DS by additional information of pseudolabels. The sources of pseudolabels may be derived from clustering analysis, classification analysis, label propagation [42], and so on.Formally, a pseudolabel decision system can be represented asDSPL=<U,AT,d,dATPL>, in which U, AT, and d are similar to those in decision system DS, respectively; dATPL is the pseudolabel decision attribute, ∀x∈U, dATPL(x) is the pseudolabel of x that is derived from a learning approach over AT. And the learning approach is k-means clustering in this paper.Since both condition attributes and pseudolabels of samples exist in the pseudolabel neighborhood decision system, we can define the following pseudolabel neighborhood relation for replacing the traditional neighborhood relation shown in Equation (7).Definition 7.
Given a pseudolabel decision systemDSPL and a neighborhood radius δ∈(0,1],∀A⊆AT, the pseudolabel neighborhood relation is defined as (15)δAPL=x,y∈U×U:ΔAx,y≤δ∧dAPLx=dAPLy.Following Definition7, ∀x∈U, the pseudolabel neighborhood of x is then defined as (16)δAPLx=y∈U:ΔAx,y≤δ∧dAPLx=dAPLy.Obviously, in Definition7, two constraints have been employed to construct the pseudolabel neighborhood relation: (1) similar to previous neighborhood relation shown in Equation (7), the distance between two samples should be less than or equal to the given radius; (2) two samples must have same pseudolabel.Proposition 8.
Given a pseudolabel decision systemDSPL, ∀A⊆AT, we have δAPL(x)⊆δA(x).Proof.
It can be derived directly from Equations (8) and (16).The above proposition tells us that, by comparing the traditional approach, our pseudolabel strategy can derive a finer neighborhood relation which provides higher performance of discrimination, mainly because the samples with different pseudolabels should be deleted from the neighborhood.Naturally, following Equation (16), the pseudolabel neighborhood decision-theoretic rough set (PLNDTRS) can be formed as Definition 9 shows.Definition 9.
Given a pseudolabel decision systemDSPL, ∀X⊆U, and ∀A⊆AT, the pseudolabel neighborhood lower and upper approximations of X are(17)PLN_Aα,βX=x∈U:ProX∣δAPLx≥α;(18)PLN¯Aα,βX=x∈U:ProX∣δAPLx>β.The pair[PLN_A(α,β)(X),PLN¯A(α,β)(X)] is referred to as a PLNDTRS of X. Correspondingly, the pseudolabel positive, boundary, and negative regions of X are (19)PLPOSAα,βX=PLN_Aα,βX;PLBNDAα,βX=PLN¯Aα,βX-PLN_Aα,βX;PLNEGAα,βX=U-PLN¯Aα,βX.Example 10.
For readers’ convenience, we can take an example to show the difference between NDTRS and PLNDTRS. Figure3 shows us a binary classification problem. Two classes of samples are represented by blue “·” and red “+”, respectively.
(1) Let us investigate subfigure (a); suppose thatx is a testing sample for classification; based on the given radius δ, 8 samples fall into the neighborhood of x except x itself; they are y1,…,y8. Obviously, samples y1,y4, and y6 have the label of blue “·” and samples y2,y3,y5,y7, and y8 have the label of red “+”. We then conclude that x will be misclassified if the majority rule is employed, mainly because the majority rule classifies sample x into the class of red “+” while the real label of x is blue “·”.
Furthermore, if the value ofα is 0.3, then by Euation (12), we can conclude that x belongs to the lower approximations of both two different classes. The reason is that Pro(X1∣δA(x))=0.44 and Pro(X2∣δA(x))=0.56 if X1 indicates the class of blue “·” while X2 indicates the red “+”. Obviously, it is an inconsistent case and there is a conflict between two different lower approximations.
(2) Let us investigate subfigure (b) which shows us both the real labels and the pseudolabels of samples. The real labels are same to those in subfigure (a); the pseudo labels of samples are denoted by “△” and “◯”, respectively. Obviously, y1,y2,y3,y7, and y8 have the same pseudolabel (“◯”) while y4,y5,y6, and x have another same pseudolabel (“△”). Based on the expression of Definition 7, y1,y2,y3,y7, and y8 should be deleted from the neighborhood of x, mainly because, by comparing x, these samples have different pseudolabels. Immediately, y4,y5, and y6 are in the pseudolabel neighborhood of sample x. Therefore, sample x can be correctly classified if the majority rule is used.
In addition, if the value ofα is 0.3, then, by Equation (17), we can observe that x belongs to the lower approximation of the class of blue “·” while it does not belong to the lower approximation of the class of red “+”, mainly because Pro(X1∣δAPL(x))=0.75 and Pro(X2∣δAPL(x))=0.25. In other words, there is no conflict between such two different lower approximations.Figure 3
The difference between NDTRS and PLNDTRS.
(a)
NDTRS (b)
PLNDTRSThe above example tells us that our pseudolabel neighborhood approach can not only provide us with better classification performance, but also remove the conflict case between the results of lower approximations.Similar to what have been addressed for NDTRS in [16], we can also obtain the following results for PLNDTRS.Proposition 11.
Given a pseudolabel decision systemDSPL and two values α1, α2, if α1≤α2, then ∀A⊆AT and ∀X⊆U; we have PLPOSA(α2,β)(X)⊆PLPOSA(α1,β)(X).Proof.
∀ y ∈ P L P O S A ( α 2 , β ) ( X ), by Definition 9 and Equation (19), we have Pro(X∣δAPL(y))≥α2. Since α1≤α2, we then have Pro(X∣δAPL(y))≥α1; it follows that y∈PLPOSA(α1,β)(X); that is, PLPOSA(α2,β)(X)⊆PLPOSA(α1,β)(X) is proved.Proposition 12.
Given a pseudolabel decision systemDSPL and two values β1, β2, if β1≤β2, then ∀A⊆AT and ∀X⊆U; we have PLBNDA(α,β2)(X)⊆PLBNDA(α,β1)(X).Proof.
For∀y∈PLBNDA(α,β2)(X), by Definition 9, we have Pro(X∣δAPL(y))>β2. Since β1≤β2, we then have Pro(X∣δAPL(y))>β1; it follows that y∈PLBNDA(α,β1)(X); that is, PLBNDA(α,β2)(X)⊆PLBNDA(α,β1)(X) is proved.The above two propositions suggest that we can also adjust the size of positive region or the boundary region ofX by modifying the values of α and β in PLNDTRS.


## 4. Attribute Reduction in PLNDTRS

### 4.1. Aim of Attribute Reduction

Attribute reduction [43] plays a crucial role in the development of rough set. Different from previous feature selections in the field of Machine Learning, attribute reduction has clear explanations with respect to different constraints. For example, if the positive region is expected to be preserved, then attribute reduction may be defined as a minimal subset of the condition attributes which preserves the positive region.Up to now, through considering various constraints, a lot of the researchers have proposed so many different definitions of attribute reductions [43–48]. It should be noticed that, for DTRS related attribute reductions, decision costs provide us with an interesting topic [11, 49, 50]. In other words, it is frequently expected that, through using attribute reduction, the obtained subset of the condition attributes may provide lower or minimal value of decision cost. Therefore, in the following of this section, the attribute reduction will be further explored for achieving lower decision cost based on PLNDTRS.Firstly, given a pseudolabel decision systemDSPL, let us review how to calculate the decision costs. ∀A⊆AT and suppose that U/IND(d)={X1,X2,…,Xq}; the total decision cost is (20)COSTAPL=COSTAPLPOS+COSTAPLBND+COSTAPLNEG;where (21)COSTAPLPOS=∑j=1q∑x∈PLPOSAα,βXjProXj∣δAPLx·λPP+1-ProXj∣δAPLx·λPN;(22)COSTAPLBND=∑j=1q∑x∈PLBNDAα,βXjProXj∣δAPLx·λBP+1-ProXj∣δAPLx·λBN;(23)COSTAPLNEG=∑j=1q∑x∈PLNEGAα,βXjProXj∣δAPLx·λNP+1-ProXj∣δAPLx·λNN.C O S T A P L indicates the total decision cost, COSTAPLPOS indicates the decision cost of positive region, COSTAPLBND indicates the decision cost of boundary region, and COSTAPLNEG is the decision cost of negative region.Similar to other DTRS, the decision costs of our PLNDTRS are not always monotonic if the used condition attributes vary. For example, if the number of used condition attributes has been reduced, then the derived decision costs may increase or decrease. Therefore, our definition attribute reduction will be presented, which aims to achieve the lower decision cost through selecting a subset of the condition attributes.Definition 13.
Given a pseudolabel decision systemDSPL, ∀A⊆AT, A is referred to as a reduct in DSPL if and only if (1)
COSTAPL≤COSTATPL and A≠∅;(2)
∀B⊂A, COSTBPL>COSTAPL.Example 14.
Table2 is a small example of pseudolabel decision system which contains 10 samples. All of these samples are described by five condition attributes such that AT={a1,a2,a3,a4,a5}. The pseudolabels of samples are obtained by clustering technique.
Assuming thatδ=0.2 and the parameters in loss function are λPP=λNN=0, λPN=1, λNP=0.95, λBP=0.16, λBN=0.39, then we can calculate two thresholds such that α=0.7922 and β=0.3305. The decision cost based on the whole condition attribute set AT, that is, COSTATPL, is 1.2983.
By computation, the decision cost based on{a3,a5} is 0.8633, which is lower than COSTATPL. Furthermore, if we remove the attribute a5, then the decision cost based on {a3} is 2.0017; if we remove the attribute a3, then the decision cost based on {a5} is 1.4983. Obviously, both the decision cost based on {a3} and the decision cost based on {a5} are higher than the decision cost based on {a3,a5}; that is, neither a3 nor a5 can be removed for generating lower decision cost. Therefore, the condition attributes set {a3,a5} is a reduct in Table 2.Table 2
A small example of pseudolabel decision system.
a 1 a 2 a 3 a 4 a 5 d d P L x 1 0.5402 0.8300 0.4755 0.0212 0.4771 1 # x 2 0.9538 0.4890 0.5832 0.8799 0.6534 1 # x 3 0.2089 0.7607 0.2605 0.7981 0.9665 2 # x 4 0.1163 0.9151 0.0848 0.3241 0.3130 1 # x 5 0.6462 0.9009 0.2981 0.6690 0.0764 3 # x 6 0.1084 0.2142 0.9171 0.2962 0.7914 3 ∗ x 7 0.9834 0.5470 0.4705 0.9299 0.3653 2 # x 8 0.2483 0.7847 0.2694 0.2819 0.5850 1 # x 9 0.6063 0.1944 0.7629 0.1688 0.1833 2 + x 10 0.8166 0.7468 0.7721 0.7451 0.0769 2 ∗


### 4.2. Algorithm to Compute Reduct

Presently, in the field of rough set, it is well known that obtaining all reducts is an NP-hard problem [51, 52]; it follows that many heuristic algorithms for finding reducts have been studied [45, 53]. Generally speaking, a heuristic algorithm contains two core aspects: heuristic information and searching strategy.In the heuristic algorithm, the fitness function can be used to characterize the heuristic information. For example, in Definition13, the decision cost COSTAPL should be used to construct fitness function because the aim of Definition 13 is to find a subset of condition attributes which derives lower decision cost.With regard to the searching strategies in the heuristic algorithm, two approaches have been considered. One is directional searching and the other is nondirectional searching. The directional searching strategy can be further categorized into deletion method, addition method, and addition-deletion method [54]. Nondirectional searching strategy is usually applied to evolutionary algorithms, swarm algorithms, and other population-based metaheuristic algorithms for optimization problems.In the context of this paper, we will use the addition method to compute the reduct; that is, the searching strategy is directional searching. To achieve that, the fitness function for measuring the significance of the condition attribute should be presented. The detailed form is shown in the following definition.Definition 15.
Given a pseudolabel decision systemDSPL, ∀A⊆AT, and ∀a∈AT-A, the fitness value of attribute a is(24)Siga,A,d=COSTA∪aPL-COSTAPL.Obviously, the above fitness function displays the significance or importance of an attribute. IfSig(a,A,d)≥0, then the attribute a cannot be added into A because the decision cost will be increased; if Sig(a,A,d)<0, then the attribute a can be added into A possibly because the decision cost will be decreased.In the procedure of adding attributes, ifCOSTAPL≤COSTATPL, then we will stop such procedure and output the final reduct A. The detailed process is shown in Algorithm 1 [16, 49].Algorithm 1:Compute reduct based on PLNDTRS.
Inputs: A decision system DS. Outputs: A reduct A. Step  1:  ∀xi∈U, obtain dATPL(xi) by k-means clustering. / / k is same to the number of decision classes in DS. Step  2: Compute COSTATPL; Step  3:  A=∅ and let COSTAPL be a value which is greater than COSTATPL; Step  4:  While C O S T A P L >  C O S T A T P L; (1) ∀AT-A, ∀xi∈U, compute dA∪{a}PL(xi); (2) ∀AT-A, compute Sig(a,A,d); (3) Select the attribute a such that a=argmin⁡{Sig(a,A,d):∀a∈AT-A}; (4) A=A∪{a}; (5) Compute COSTAPL; End While. Step  5: Output A.In Algorithm1, following the basic structure of k-means clustering, in Step 1, the time complexity of computing pseudolabels of samples is O(k·T·|U|), in which k is the number of clusters and T is the number of iterations. The time complexity of Step 2 is O(|U|2·|AT|) because it is required to compare any two samples in U over condition attributes AT for generating neighborhoods. Step 4 is the iteration process of adding attributes into the reduct. The time complexity of Step 4 is O(|U|2·|AT|2) since, in the worst case, such looping should be executed |AT| times. To sum up, we can conclude that the whole time complexity of Algorithm 1 is O(k·T·|U|+|U|2·|AT|2).


## 4.1. Aim of Attribute Reduction

Attribute reduction [43] plays a crucial role in the development of rough set. Different from previous feature selections in the field of Machine Learning, attribute reduction has clear explanations with respect to different constraints. For example, if the positive region is expected to be preserved, then attribute reduction may be defined as a minimal subset of the condition attributes which preserves the positive region.Up to now, through considering various constraints, a lot of the researchers have proposed so many different definitions of attribute reductions [43–48]. It should be noticed that, for DTRS related attribute reductions, decision costs provide us with an interesting topic [11, 49, 50]. In other words, it is frequently expected that, through using attribute reduction, the obtained subset of the condition attributes may provide lower or minimal value of decision cost. Therefore, in the following of this section, the attribute reduction will be further explored for achieving lower decision cost based on PLNDTRS.Firstly, given a pseudolabel decision systemDSPL, let us review how to calculate the decision costs. ∀A⊆AT and suppose that U/IND(d)={X1,X2,…,Xq}; the total decision cost is (20)COSTAPL=COSTAPLPOS+COSTAPLBND+COSTAPLNEG;where (21)COSTAPLPOS=∑j=1q∑x∈PLPOSAα,βXjProXj∣δAPLx·λPP+1-ProXj∣δAPLx·λPN;(22)COSTAPLBND=∑j=1q∑x∈PLBNDAα,βXjProXj∣δAPLx·λBP+1-ProXj∣δAPLx·λBN;(23)COSTAPLNEG=∑j=1q∑x∈PLNEGAα,βXjProXj∣δAPLx·λNP+1-ProXj∣δAPLx·λNN.C O S T A P L indicates the total decision cost, COSTAPLPOS indicates the decision cost of positive region, COSTAPLBND indicates the decision cost of boundary region, and COSTAPLNEG is the decision cost of negative region.Similar to other DTRS, the decision costs of our PLNDTRS are not always monotonic if the used condition attributes vary. For example, if the number of used condition attributes has been reduced, then the derived decision costs may increase or decrease. Therefore, our definition attribute reduction will be presented, which aims to achieve the lower decision cost through selecting a subset of the condition attributes.Definition 13.
Given a pseudolabel decision systemDSPL, ∀A⊆AT, A is referred to as a reduct in DSPL if and only if (1)
COSTAPL≤COSTATPL and A≠∅;(2)
∀B⊂A, COSTBPL>COSTAPL.Example 14.
Table2 is a small example of pseudolabel decision system which contains 10 samples. All of these samples are described by five condition attributes such that AT={a1,a2,a3,a4,a5}. The pseudolabels of samples are obtained by clustering technique.
Assuming thatδ=0.2 and the parameters in loss function are λPP=λNN=0, λPN=1, λNP=0.95, λBP=0.16, λBN=0.39, then we can calculate two thresholds such that α=0.7922 and β=0.3305. The decision cost based on the whole condition attribute set AT, that is, COSTATPL, is 1.2983.
By computation, the decision cost based on{a3,a5} is 0.8633, which is lower than COSTATPL. Furthermore, if we remove the attribute a5, then the decision cost based on {a3} is 2.0017; if we remove the attribute a3, then the decision cost based on {a5} is 1.4983. Obviously, both the decision cost based on {a3} and the decision cost based on {a5} are higher than the decision cost based on {a3,a5}; that is, neither a3 nor a5 can be removed for generating lower decision cost. Therefore, the condition attributes set {a3,a5} is a reduct in Table 2.Table 2
A small example of pseudolabel decision system.
a 1 a 2 a 3 a 4 a 5 d d P L x 1 0.5402 0.8300 0.4755 0.0212 0.4771 1 # x 2 0.9538 0.4890 0.5832 0.8799 0.6534 1 # x 3 0.2089 0.7607 0.2605 0.7981 0.9665 2 # x 4 0.1163 0.9151 0.0848 0.3241 0.3130 1 # x 5 0.6462 0.9009 0.2981 0.6690 0.0764 3 # x 6 0.1084 0.2142 0.9171 0.2962 0.7914 3 ∗ x 7 0.9834 0.5470 0.4705 0.9299 0.3653 2 # x 8 0.2483 0.7847 0.2694 0.2819 0.5850 1 # x 9 0.6063 0.1944 0.7629 0.1688 0.1833 2 + x 10 0.8166 0.7468 0.7721 0.7451 0.0769 2 ∗


## 4.2. Algorithm to Compute Reduct

Presently, in the field of rough set, it is well known that obtaining all reducts is an NP-hard problem [51, 52]; it follows that many heuristic algorithms for finding reducts have been studied [45, 53]. Generally speaking, a heuristic algorithm contains two core aspects: heuristic information and searching strategy.In the heuristic algorithm, the fitness function can be used to characterize the heuristic information. For example, in Definition13, the decision cost COSTAPL should be used to construct fitness function because the aim of Definition 13 is to find a subset of condition attributes which derives lower decision cost.With regard to the searching strategies in the heuristic algorithm, two approaches have been considered. One is directional searching and the other is nondirectional searching. The directional searching strategy can be further categorized into deletion method, addition method, and addition-deletion method [54]. Nondirectional searching strategy is usually applied to evolutionary algorithms, swarm algorithms, and other population-based metaheuristic algorithms for optimization problems.In the context of this paper, we will use the addition method to compute the reduct; that is, the searching strategy is directional searching. To achieve that, the fitness function for measuring the significance of the condition attribute should be presented. The detailed form is shown in the following definition.Definition 15.
Given a pseudolabel decision systemDSPL, ∀A⊆AT, and ∀a∈AT-A, the fitness value of attribute a is(24)Siga,A,d=COSTA∪aPL-COSTAPL.Obviously, the above fitness function displays the significance or importance of an attribute. IfSig(a,A,d)≥0, then the attribute a cannot be added into A because the decision cost will be increased; if Sig(a,A,d)<0, then the attribute a can be added into A possibly because the decision cost will be decreased.In the procedure of adding attributes, ifCOSTAPL≤COSTATPL, then we will stop such procedure and output the final reduct A. The detailed process is shown in Algorithm 1 [16, 49].Algorithm 1:Compute reduct based on PLNDTRS.
Inputs: A decision system DS. Outputs: A reduct A. Step  1:  ∀xi∈U, obtain dATPL(xi) by k-means clustering. / / k is same to the number of decision classes in DS. Step  2: Compute COSTATPL; Step  3:  A=∅ and let COSTAPL be a value which is greater than COSTATPL; Step  4:  While C O S T A P L >  C O S T A T P L; (1) ∀AT-A, ∀xi∈U, compute dA∪{a}PL(xi); (2) ∀AT-A, compute Sig(a,A,d); (3) Select the attribute a such that a=argmin⁡{Sig(a,A,d):∀a∈AT-A}; (4) A=A∪{a}; (5) Compute COSTAPL; End While. Step  5: Output A.In Algorithm1, following the basic structure of k-means clustering, in Step 1, the time complexity of computing pseudolabels of samples is O(k·T·|U|), in which k is the number of clusters and T is the number of iterations. The time complexity of Step 2 is O(|U|2·|AT|) because it is required to compare any two samples in U over condition attributes AT for generating neighborhoods. Step 4 is the iteration process of adding attributes into the reduct. The time complexity of Step 4 is O(|U|2·|AT|2) since, in the worst case, such looping should be executed |AT| times. To sum up, we can conclude that the whole time complexity of Algorithm 1 is O(k·T·|U|+|U|2·|AT|2).


## 5. Experimental Analyses

In this section, to evaluate the performance of PLNDTRS and corresponding algorithm to compute reduct, 15 UCI data sets have been selected to conduct the experiments. The details of these data are shown in Table3. All the experiments have been carried out on a personal computer with Windows 10, Intel Core i5 3230M CPU (2.60GHz), and 4.00 GB memory. The programming platform is MATLAB R2018a.Table 3
A description of data sets.
ID Data sets Samples Attributes Decision classes 1 Abalone 4177 7 29 2 Breast Cancer Wisconsin (Diagnostic) 569 30 2 3 Caffeine Consumption 1885 12 7 4 Cardiotocography 1216 21 10 5 Dermatology 366 36 6 6 E. coli 336 7 8 7 Glass Identification 214 9 6 8 LSVT Voice Rehabilitation 126 257 2 9 Page Blocks Classification 5473 10 5 10 Ring 7400 20 2 11 Statlog (Image Segmentation) 2310 18 7 12 Urban Land Cover 675 147 9 13 Waveform Database Generator 5000 21 3 14 Wine 178 13 3 15 Yeast 1484 8 10In the experiments,k-means clustering is employed to produce pseudolabels, and the value of k is the number of decision classes. For all the experiments in this section, 10 different values of δ have been used; they are δ=0.03,0.06,…,0.3. Moreover, not only the 10-fold cross-validation is employed in our experiments, but also 10 different groups of loss functions are generated randomly for each cross-validation. Therefore, for each radius δ, each data set will be tested 100 times.


### 5.1. Experiments on Raw Attributes

In what follows, the decision costs obtained by NDTRS and PLNDTRS in terms of raw attributes will be compared. The forms of these decision costs have been shown in Equations (20)-(23). The detailed results are shown in Table 4.Table 4
Comparisons of different decision costs in terms of raw attributes (smaller values are underlined).
Total costs Costs of positive region Costs of boundary region Costs of negative region ID NDTRS PLNDTRS NDTRS PLNDTRS NDTRS PLNDTRS NDTRS PLNDTRS  1 515.7637 505.4116 3.1993 4.0853 466.0496 448.8289 46.5148 52.4974 2 50.8504 26.4840 31.3946 23.0951 19.4558 3.3889 0.0000 0.0000 3 399.2153 388.7867 100.7310 93.6039 297.0621 293.5297 1.4220 1.6532 4 424.4182 397.1313 31.8888 33.7502 357.4530 336.0896 35.0765 27.2915 5 22.3292 6.4481 5.3326 4.2677 16.8490 2.1804 0.1475 0.0000 6 49.7287 36.9805 13.7807 11.7077 35.2870 24.8976 0.6611 0.3752 7 48.5359 45.3767 2.1099 1.7737 45.7020 43.1462 0.7239 0.4568 8 28.0053 27.6984 2.3890 2.3280 25.6164 25.3704 0.0000 0.0000 9 247.8693 221.4285 176.073 149.7464 70.7042 71.6207 0.9431 0.0613 10 640.0481 634.8294 364.5238 360.2211 275.5243 274.6083 0.0000 0.0000 11 272.5914 249.7893 43.8713 41.2862 214.8033 206.0070 13.9169 2.4961 12 131.3945 97.1666 20.5268 26.6987 107.7290 69.9520 3.1387 0.5159 13 967.5386 944.4428 209.2039 194.6551 758.3347 749.7877 0.0000 0.0000 14 8.7816 3.9627 4.8234 2.3965 3.9583 1.5662 0.0000 0.0000 15 381.1040 361.9059 11.7836 21.0489 319.6782 315.4133 49.6422 25.4437Through a careful investigation of Table4, it is not difficult to draw the following conclusion.For all the data sets, the total decision costs generated by PLNDTRS are lower than those generated by NDTRS. This is mainly because (1) most of the decision costs of PLNDTRS based positive region are lower than those of NDTRS based positive region; (2) most of the decision costs of PLNDTRS based boundary region are lower than those of NDTRS based boundary region. From this point of view, by comparing NDTRS, our pseudolabel strategy does work for reducing the decision costs.


### 5.2. Experiments on Attribute Reduction

In this subsection, to show the efficiency of the proposed attribute reduction shown in Definition13, the decision costs derived by the obtained reducts will be compared.Figure4 shows us the detailed change trend lines of decision costs. It should be noticed that the decision costs shown in Figure 4 are total decision costs instead of the decision costs of three different regions. In each subfigure of Figure 4, the x-coordinate pertains to value of δ, whereas the y-coordinate concerns the values of costs.Figure 4
A comparison among different decision costs.The detailed legends used in Figure4 are (1) Raw-Attributes: NDTRS based on the original attributes; (2) NDTRS-Reduct: NDTRS based on the attribute reduction proposed in [16] (similar to our Definition 13, the aim of this attribute reduction is also to find a minimal subset of the condition attributes which can decrease the total decision cost); (3) PLRaw-Attributes: PLNDTRS based on the original attributes; (4) PLNDTRS-Reduct: PLNDTRS based on the attribute reduction proposed in Definition 13.With a deep investigation of Figure4, it is not difficult to observe the following.(1)
By comparing with Raw-Attributes, PLRaw-Attributes may offer the lower decision costs. This observation is consistent with what have been addressed in Section5.1; that is, our pseudolabel approach does decrease the total decision costs.(2)
By comparing with NDTRS-Reduct, PLNDTRS-Reduct also provides us with the lower decision costs. In other words, through attribute reductions, our pseudolabel approach can find subsets of attributes which offer smaller decision costs though the aims of attribute reductions based on NDTRS and PLNDTRS are the same.(3)
In most data sets, both NDTRS-Reduct and PLNDTRS-Reduct do reduce the decision costs. That is to say, both the attribute reductions proposed by Li et al. in [16] and us are effective.(4)
With the increasing of value ofδ, in most data sets, four different types of decision costs will increase. This is mainly because if the value of δ is greater, then the size of the neighborhood will be larger; it follows that the positive region shows shrinking and the negative region will be expanded. Correspondingly, the decision costs with respect to different regions will be changed.Furthermore, the decision costs related to three different regions are shown in Table5.Table 5
Decision costs related to three different regions (smaller values are underlined).
Costs of positive region Costs of boundary region Costs of negative region ID NDTRS-Reduct PLNDTRS-Reduct NDTRS-Reduct PLNDTRS-Reduct NDTRS-Reduct PLNDTRS-Reduct  1 3.3083 2.5927 144.6449 137.0848 28.6878 28.2077 2 3.5871 2.7336 3.5886 0.9952 0.0000 0.0000 3 27.4517 22.2394 47.4321 45.5593 0.4478 0.5550 4 4.4652 5.6460 53.4615 57.5998 22.9725 11.2165 5 1.3671 1.4976 5.5215 3.5962 0.2970 0.1747 6 0.8422 0.5908 2.9842 2.6384 0.0727 0.0283 7 1.4726 1.0331 8.6575 6.3638 0.2810 0.2297 8 0.5302 0.5050 0.9215 0.8607 0.0000 0.0000 9 48.6126 40.8185 32.7738 30.1912 0.0378 0.1700 10 141.8567 104.5482 79.8204 132.0821 0.0000 0.0000 11 9.9494 9.8133 26.6506 33.9288 44.3499 33.8493 12 1.1821 3.7938 4.7748 11.7701 14.6167 1.5715 13 19.0932 17.6336 73.3651 77.0279 0.0276 0.0451 14 0.2434 0.0585 0.3966 0.1073 0.0029 0.0000 15 2.1211 3.3493 37.0947 50.0695 35.3422 14.4422With a careful investigation of Table5, we notice that the reducing of total decision costs shown in Figure 4 mainly comes from the reducing of costs of positive region and costs of boundary region. This result is consistent with what have been addressed in Section 5.1.Furthermore, to further demonstrate the effectiveness of our attribute reduction based on PLNDTRS, we will compare it with other popular attribute reduction methods in DTRS; they are (1) POS-Reduct (positive region extension based attribute reduction [8, 14, 49]) and NON-NEG-Reduct (nonnegative region extension based attribute reduction [49]). The details are shown in Figure 5.Figure 5
A comparison among decision costs derived by different reducts.By Figure5, it is not difficult to observe the following.(1)
Generally speaking, if the value ofδ increases, then the decision costs obtained by four different reducts increase. In other words, the performances of different reducts are closely related to the scales of radii.(2)
In most cases, the decision costs derived from “PLNDTRS-Reduct” are lower than those derived from “NDTRS-Reduct,” “POS-Reduct,” and “NON-NEG-Reduct.” Take “Yeast” data set as an example; ifδ=0.12, then the decision cost related to “PLNDTRS-Reduct” is 105 while the decision cost related to “NDTRS-Reduct” is 120; the decision cost related to “POS-Reduct” is 121 and the decision cost related to “NON-NEG-Reduct” is 138. From this point of view, we can say that our pseudolabel strategy is superior to several previous research results about attribute reduction in DTRS.Finally, we will also compare the lengths of different reducts and the time consumptions for computing these reducts. The details are shown in Tables6 and 7.Table 6
The average lengths of different reducts (shorter lengths are underlined).
ID NON-NEG-Reduct POS-Reduct NDTRS-Reduct PLNDTRS-Reduct 1 1.00 2.56 2.76 3.50 2 1.00 2.10 1.80 3.20 3 1.00 1.37 2.40 2.80 4 1.70 7.00 9.40 10.23 5 1.00 6.00 5.77 8.13 6 1.00 3.77 3.30 5.23 7 1.00 3.90 4.20 3.33 8 1.00 1.00 1.03 1.03 9 1.00 1.00 4.06 6.16 10 1.00 16.50 17.76 17.80 11 2.50 4.13 7.00 6.76 12 1.97 4.37 12.47 37.80 13 2.70 6.86 8.73 8.83 14 1.00 4.53 4.67 5.03 15 2.70 4.30 3.70 5.50Table 7
The time consumptions (seconds) for computing different reducts (lower consumptions are underlined).
ID NON-NEG-Reduct POS-Reduct NDTRS-Reduct PLNDTRS-Reduct 1 27.7031 29.4720 97.7107 182.7403 2 1.2874 1.3160 1.8312 3.2800 3 2.6965 2.7879 8.5677 11.7441 4 10.4468 18.8002 61.4017 81.0210 5 0.1894 0.5577 0.5562 6.0147 6 0.0452 0.0657 0.1860 0.5958 7 0.0234 0.0366 0.1176 0.3378 8 1.1789 1.0911 1.2891 2.3478 9 48.4413 24.2008 241.5598 344.9764 10 243.8521 1146.7207 3521.3002 3619.4430 11 15.8729 11.9315 611.5846 915.7841 12 5.2911 6.0499 45.5096 271.2546 13 188.2825 217.8035 791.8680 830.0859 14 0.0215 0.0449 0.1320 0.4860 15 2.0325 1.4747 3.7970 7.3192Following Tables6 and 7, it is not difficult to observe that more time is required to compute PLNDTRS-reduct. The main reason includes two aspects: (1) for each iteration in computing reduct, the pseudolabels of samples should be regenerated; this has been pointed out in (1) of Step 4 in Algorithm 1; (2) based on Table 6, more attributes are required to construct reducts; such fact indicates that more iterations should be executed.Moreover, it must be emphasized that though the time consumptions of calculating NON-NEG-Reduct and POS-Reduct are lower, such two types of reducts may not be good enough for providing smaller values of decision costs. This fact can be observed in Figure5 clearly. From this point of view, our pseudolabel strategy based attribute reduction is superior to previous researches though our approach requires more time to obtain reduct.


### 5.3. Statistical Comparisons of Reducts

In this section, we will make the statistical comparisons between PLNDTRS-Reduct and NDTRS-Reduct. The Wilcoxon signed rank test [55] will be selected for comparing such two reducts. The purpose of this computation is trying to reject the null hypothesis that the two reducts perform equally well.For each data set, we have used 10 different radii to obtain reducts; it follows that 10 decision costs will be generated by each algorithm. Take the data “Caffeine Consumption” for instance, the 10 total decision costs derived from NDTRS-Reduct are “54.9455, 60.6065, 70.4899, 75.1574, 77.0271, 81.4503, 83.2687, 82.8129, 82.6185, 84.9391” while the 10 total decision costs derived from PLNDTRS-Reduct are “47.6352, 57.7943, 63.3378, 69.9135, 73.6124, 76.0755, 78.9889, 81.4714, 81.2164, 83.4922;” the correspondingp-value of Wilcoxon signed rank test is then 0.002. p-value is the probability of observing the given result, or one more extreme, by chance if the null hypothesis is true. The detailed results of p-values are shown in Table 8.Table 8
p-values of Wilcoxon signed rank test for comparing reducts (higher p-values are italic).
Total costs Costs of positive region Costs of boundary region Costs of negative region ID NDTRS-Reduct & NDTRS-Reduct & NDTRS-Reduct & NDTRS-Reduct & PLNDTRS-Reduct PLNDTRS-Reduct PLNDTRS-Reduct PLNDTRS-Reduct  1 0.0020 0.0977 0.0273 0.9219 2 0.0020 0.0020 0.0020 1.0000 3 0.0020 0.0098 0.6953 0.3750 4 0.0059 0.2754 0.5566 0.0098 5 0.0020 0.9219 0.0195 0.1563 6 0.0020 0.0098 0.0020 0.1309 7 0.0020 0.0645 0.0020 0.2754 8 0.0020 0.0039 0.0400 1.0000 9 0.0098 0.0020 0.0050 0.0095 10 0.0488 0.0039 0.0059 1.0000 11 0.0316 0.0695 0.0050 0.0039 12 0.0137 0.0371 0.0195 0.0020 13 0.0195 0.0020 0.0137 1.0000 14 0.0020 0.0078 0.0020 1.0000 15 0.0020 0.0488 0.1993 0.0020Following the results of Table8, if the significance level is given by 0.05, we therefore reject the null hypothesis. In Table 8, we notice that most of the p-values are lower than 0.05. In other words, from the viewpoint of costs, reducts based on NDTRS and those based on our PLNDTRS do not perform equally well though the aim of such two reducts is the same.Remark 16.
Most of thep-values in “costs of negative region” are equal to 1. This is mainly because, based on NDTRS-Reduct and PLNDTRS-Reduct, the decision costs of negative region are 0 in most cases.


## 5.1. Experiments on Raw Attributes

In what follows, the decision costs obtained by NDTRS and PLNDTRS in terms of raw attributes will be compared. The forms of these decision costs have been shown in Equations (20)-(23). The detailed results are shown in Table 4.Table 4
Comparisons of different decision costs in terms of raw attributes (smaller values are underlined).
Total costs Costs of positive region Costs of boundary region Costs of negative region ID NDTRS PLNDTRS NDTRS PLNDTRS NDTRS PLNDTRS NDTRS PLNDTRS  1 515.7637 505.4116 3.1993 4.0853 466.0496 448.8289 46.5148 52.4974 2 50.8504 26.4840 31.3946 23.0951 19.4558 3.3889 0.0000 0.0000 3 399.2153 388.7867 100.7310 93.6039 297.0621 293.5297 1.4220 1.6532 4 424.4182 397.1313 31.8888 33.7502 357.4530 336.0896 35.0765 27.2915 5 22.3292 6.4481 5.3326 4.2677 16.8490 2.1804 0.1475 0.0000 6 49.7287 36.9805 13.7807 11.7077 35.2870 24.8976 0.6611 0.3752 7 48.5359 45.3767 2.1099 1.7737 45.7020 43.1462 0.7239 0.4568 8 28.0053 27.6984 2.3890 2.3280 25.6164 25.3704 0.0000 0.0000 9 247.8693 221.4285 176.073 149.7464 70.7042 71.6207 0.9431 0.0613 10 640.0481 634.8294 364.5238 360.2211 275.5243 274.6083 0.0000 0.0000 11 272.5914 249.7893 43.8713 41.2862 214.8033 206.0070 13.9169 2.4961 12 131.3945 97.1666 20.5268 26.6987 107.7290 69.9520 3.1387 0.5159 13 967.5386 944.4428 209.2039 194.6551 758.3347 749.7877 0.0000 0.0000 14 8.7816 3.9627 4.8234 2.3965 3.9583 1.5662 0.0000 0.0000 15 381.1040 361.9059 11.7836 21.0489 319.6782 315.4133 49.6422 25.4437Through a careful investigation of Table4, it is not difficult to draw the following conclusion.For all the data sets, the total decision costs generated by PLNDTRS are lower than those generated by NDTRS. This is mainly because (1) most of the decision costs of PLNDTRS based positive region are lower than those of NDTRS based positive region; (2) most of the decision costs of PLNDTRS based boundary region are lower than those of NDTRS based boundary region. From this point of view, by comparing NDTRS, our pseudolabel strategy does work for reducing the decision costs.


## 5.2. Experiments on Attribute Reduction

In this subsection, to show the efficiency of the proposed attribute reduction shown in Definition13, the decision costs derived by the obtained reducts will be compared.Figure4 shows us the detailed change trend lines of decision costs. It should be noticed that the decision costs shown in Figure 4 are total decision costs instead of the decision costs of three different regions. In each subfigure of Figure 4, the x-coordinate pertains to value of δ, whereas the y-coordinate concerns the values of costs.Figure 4
A comparison among different decision costs.The detailed legends used in Figure4 are (1) Raw-Attributes: NDTRS based on the original attributes; (2) NDTRS-Reduct: NDTRS based on the attribute reduction proposed in [16] (similar to our Definition 13, the aim of this attribute reduction is also to find a minimal subset of the condition attributes which can decrease the total decision cost); (3) PLRaw-Attributes: PLNDTRS based on the original attributes; (4) PLNDTRS-Reduct: PLNDTRS based on the attribute reduction proposed in Definition 13.With a deep investigation of Figure4, it is not difficult to observe the following.(1)
By comparing with Raw-Attributes, PLRaw-Attributes may offer the lower decision costs. This observation is consistent with what have been addressed in Section5.1; that is, our pseudolabel approach does decrease the total decision costs.(2)
By comparing with NDTRS-Reduct, PLNDTRS-Reduct also provides us with the lower decision costs. In other words, through attribute reductions, our pseudolabel approach can find subsets of attributes which offer smaller decision costs though the aims of attribute reductions based on NDTRS and PLNDTRS are the same.(3)
In most data sets, both NDTRS-Reduct and PLNDTRS-Reduct do reduce the decision costs. That is to say, both the attribute reductions proposed by Li et al. in [16] and us are effective.(4)
With the increasing of value ofδ, in most data sets, four different types of decision costs will increase. This is mainly because if the value of δ is greater, then the size of the neighborhood will be larger; it follows that the positive region shows shrinking and the negative region will be expanded. Correspondingly, the decision costs with respect to different regions will be changed.Furthermore, the decision costs related to three different regions are shown in Table5.Table 5
Decision costs related to three different regions (smaller values are underlined).
Costs of positive region Costs of boundary region Costs of negative region ID NDTRS-Reduct PLNDTRS-Reduct NDTRS-Reduct PLNDTRS-Reduct NDTRS-Reduct PLNDTRS-Reduct  1 3.3083 2.5927 144.6449 137.0848 28.6878 28.2077 2 3.5871 2.7336 3.5886 0.9952 0.0000 0.0000 3 27.4517 22.2394 47.4321 45.5593 0.4478 0.5550 4 4.4652 5.6460 53.4615 57.5998 22.9725 11.2165 5 1.3671 1.4976 5.5215 3.5962 0.2970 0.1747 6 0.8422 0.5908 2.9842 2.6384 0.0727 0.0283 7 1.4726 1.0331 8.6575 6.3638 0.2810 0.2297 8 0.5302 0.5050 0.9215 0.8607 0.0000 0.0000 9 48.6126 40.8185 32.7738 30.1912 0.0378 0.1700 10 141.8567 104.5482 79.8204 132.0821 0.0000 0.0000 11 9.9494 9.8133 26.6506 33.9288 44.3499 33.8493 12 1.1821 3.7938 4.7748 11.7701 14.6167 1.5715 13 19.0932 17.6336 73.3651 77.0279 0.0276 0.0451 14 0.2434 0.0585 0.3966 0.1073 0.0029 0.0000 15 2.1211 3.3493 37.0947 50.0695 35.3422 14.4422With a careful investigation of Table5, we notice that the reducing of total decision costs shown in Figure 4 mainly comes from the reducing of costs of positive region and costs of boundary region. This result is consistent with what have been addressed in Section 5.1.Furthermore, to further demonstrate the effectiveness of our attribute reduction based on PLNDTRS, we will compare it with other popular attribute reduction methods in DTRS; they are (1) POS-Reduct (positive region extension based attribute reduction [8, 14, 49]) and NON-NEG-Reduct (nonnegative region extension based attribute reduction [49]). The details are shown in Figure 5.Figure 5
A comparison among decision costs derived by different reducts.By Figure5, it is not difficult to observe the following.(1)
Generally speaking, if the value ofδ increases, then the decision costs obtained by four different reducts increase. In other words, the performances of different reducts are closely related to the scales of radii.(2)
In most cases, the decision costs derived from “PLNDTRS-Reduct” are lower than those derived from “NDTRS-Reduct,” “POS-Reduct,” and “NON-NEG-Reduct.” Take “Yeast” data set as an example; ifδ=0.12, then the decision cost related to “PLNDTRS-Reduct” is 105 while the decision cost related to “NDTRS-Reduct” is 120; the decision cost related to “POS-Reduct” is 121 and the decision cost related to “NON-NEG-Reduct” is 138. From this point of view, we can say that our pseudolabel strategy is superior to several previous research results about attribute reduction in DTRS.Finally, we will also compare the lengths of different reducts and the time consumptions for computing these reducts. The details are shown in Tables6 and 7.Table 6
The average lengths of different reducts (shorter lengths are underlined).
ID NON-NEG-Reduct POS-Reduct NDTRS-Reduct PLNDTRS-Reduct 1 1.00 2.56 2.76 3.50 2 1.00 2.10 1.80 3.20 3 1.00 1.37 2.40 2.80 4 1.70 7.00 9.40 10.23 5 1.00 6.00 5.77 8.13 6 1.00 3.77 3.30 5.23 7 1.00 3.90 4.20 3.33 8 1.00 1.00 1.03 1.03 9 1.00 1.00 4.06 6.16 10 1.00 16.50 17.76 17.80 11 2.50 4.13 7.00 6.76 12 1.97 4.37 12.47 37.80 13 2.70 6.86 8.73 8.83 14 1.00 4.53 4.67 5.03 15 2.70 4.30 3.70 5.50Table 7
The time consumptions (seconds) for computing different reducts (lower consumptions are underlined).
ID NON-NEG-Reduct POS-Reduct NDTRS-Reduct PLNDTRS-Reduct 1 27.7031 29.4720 97.7107 182.7403 2 1.2874 1.3160 1.8312 3.2800 3 2.6965 2.7879 8.5677 11.7441 4 10.4468 18.8002 61.4017 81.0210 5 0.1894 0.5577 0.5562 6.0147 6 0.0452 0.0657 0.1860 0.5958 7 0.0234 0.0366 0.1176 0.3378 8 1.1789 1.0911 1.2891 2.3478 9 48.4413 24.2008 241.5598 344.9764 10 243.8521 1146.7207 3521.3002 3619.4430 11 15.8729 11.9315 611.5846 915.7841 12 5.2911 6.0499 45.5096 271.2546 13 188.2825 217.8035 791.8680 830.0859 14 0.0215 0.0449 0.1320 0.4860 15 2.0325 1.4747 3.7970 7.3192Following Tables6 and 7, it is not difficult to observe that more time is required to compute PLNDTRS-reduct. The main reason includes two aspects: (1) for each iteration in computing reduct, the pseudolabels of samples should be regenerated; this has been pointed out in (1) of Step 4 in Algorithm 1; (2) based on Table 6, more attributes are required to construct reducts; such fact indicates that more iterations should be executed.Moreover, it must be emphasized that though the time consumptions of calculating NON-NEG-Reduct and POS-Reduct are lower, such two types of reducts may not be good enough for providing smaller values of decision costs. This fact can be observed in Figure5 clearly. From this point of view, our pseudolabel strategy based attribute reduction is superior to previous researches though our approach requires more time to obtain reduct.


## 5.3. Statistical Comparisons of Reducts

In this section, we will make the statistical comparisons between PLNDTRS-Reduct and NDTRS-Reduct. The Wilcoxon signed rank test [55] will be selected for comparing such two reducts. The purpose of this computation is trying to reject the null hypothesis that the two reducts perform equally well.For each data set, we have used 10 different radii to obtain reducts; it follows that 10 decision costs will be generated by each algorithm. Take the data “Caffeine Consumption” for instance, the 10 total decision costs derived from NDTRS-Reduct are “54.9455, 60.6065, 70.4899, 75.1574, 77.0271, 81.4503, 83.2687, 82.8129, 82.6185, 84.9391” while the 10 total decision costs derived from PLNDTRS-Reduct are “47.6352, 57.7943, 63.3378, 69.9135, 73.6124, 76.0755, 78.9889, 81.4714, 81.2164, 83.4922;” the correspondingp-value of Wilcoxon signed rank test is then 0.002. p-value is the probability of observing the given result, or one more extreme, by chance if the null hypothesis is true. The detailed results of p-values are shown in Table 8.Table 8
p-values of Wilcoxon signed rank test for comparing reducts (higher p-values are italic).
Total costs Costs of positive region Costs of boundary region Costs of negative region ID NDTRS-Reduct & NDTRS-Reduct & NDTRS-Reduct & NDTRS-Reduct & PLNDTRS-Reduct PLNDTRS-Reduct PLNDTRS-Reduct PLNDTRS-Reduct  1 0.0020 0.0977 0.0273 0.9219 2 0.0020 0.0020 0.0020 1.0000 3 0.0020 0.0098 0.6953 0.3750 4 0.0059 0.2754 0.5566 0.0098 5 0.0020 0.9219 0.0195 0.1563 6 0.0020 0.0098 0.0020 0.1309 7 0.0020 0.0645 0.0020 0.2754 8 0.0020 0.0039 0.0400 1.0000 9 0.0098 0.0020 0.0050 0.0095 10 0.0488 0.0039 0.0059 1.0000 11 0.0316 0.0695 0.0050 0.0039 12 0.0137 0.0371 0.0195 0.0020 13 0.0195 0.0020 0.0137 1.0000 14 0.0020 0.0078 0.0020 1.0000 15 0.0020 0.0488 0.1993 0.0020Following the results of Table8, if the significance level is given by 0.05, we therefore reject the null hypothesis. In Table 8, we notice that most of the p-values are lower than 0.05. In other words, from the viewpoint of costs, reducts based on NDTRS and those based on our PLNDTRS do not perform equally well though the aim of such two reducts is the same.Remark 16.
Most of thep-values in “costs of negative region” are equal to 1. This is mainly because, based on NDTRS-Reduct and PLNDTRS-Reduct, the decision costs of negative region are 0 in most cases.


## 6. Conclusions and Further Perspectives

By considering the label information of samples, a framework of pseudolabel strategy has been introduced into the model of decision-theoretic rough set. Different from the traditional constructions of decision-theoretic rough set, our approach is achieved by not only the distance based neighborhood, but also the pseudolabels of samples. The experimental results have demonstrated that our pseudolabel approach can reduce the decision costs which are closely related to decision-theoretic rough set. Moreover, the attribute reduction based on our pseudolabel strategy can also provide attributes with better performances if decision costs are taken into consideration.The following topics are challenges for further research.(1)
Only thek-means clustering approach is used to generate pseudolabels of samples; the label propagation or supervised approach will be further explored.(2)
Through using pseudolabel strategy, how to design quick process to compute reduct for large scale data [56–58] is another interesting topic to be addressed.



---

*Source: 6810796-2019-03-19.xml*