# Fuzzy Set-Valued Information Systems and the Algorithm of Filling Missing Values for Incomplete Information Systems

Authors: Zhaohao Wang; Xiaoping Zhang
Journal: Complexity
 (2019)

---

## Abstract

How to effectively deal with missing values in incomplete information systems (IISs) according to the research target is still a key issue for investigating IISs. If the missing values in IISs are not handled properly, they will destroy the internal connection of data and reduce the efficiency of data usage. In this paper, in order to establish effective methods for filling missing values, we propose a new information system, namely, a fuzzy set-valued information system (FSvIS). By means of the similarity measures of fuzzy sets, we obtain several binary relations in FSvISs, and we investigate the relationship among them. This is a foundation for the researches on FSvISs in terms of rough set approach. Then, we provide an algorithm to fill the missing values in IISs with fuzzy set values. In fact, this algorithm can transform an IIS into an FSvIS. Furthermore, we also construct an algorithm to fill the missing values in IISs with set values (or real values). The effectiveness of these algorithms is analyzed. The results showed that the proposed algorithms achieve higher correct rate than traditional algorithms, and they have good stability. Finally, we discuss the importance of these algorithms for investigating IISs from the viewpoint of rough set theory.


---

## Body

## 1. Introduction

The classical rough model [1] can be used to deal with complete information systems. In practice, the lack of some data in IISs [2–9] is inevitable. For example, because the data collection process may be imperfect, human or objective conditions result in data loss or unavailability. For data mining, these missing data may have a very important impact on final decision. Therefore, how to infer unknown information from known information has important theoretical and practical significance.Kryszkiewicz [10] defined tolerance relation in IISs to investigate IISs by using rough set approach. This tolerance relation assumed that the missing attribute values in IISs could be represented by a set of all possible values of the corresponding attributes from an optimistic perspective. Based on Kryszkiewicz’s research, Leung and Li [11] presented a method for obtaining the relative reduction in IISs. Subsequently, Stefanowski and Tsoukias [9] established a new rough set model based on the other relations in IISs. Authors [8, 11–17] gave different methods to induce binary relations from IISs, and studied IISs by means of rough set theory. They had two main ways to treat the missing values. One was to delete the missing values, and the other was to take the missing values as generic values.Based on the probability theory, Yuan et al. [18] filled the missing values in IISs by obtaining the sample that is the closest to the missing data sample in terms of Euclidean distance and correlation. Chen and Shao [19] used the Jackknife variance estimate to investigate the missing values. In addition, there are other methods to handle missing values in IISs. Wang et al. [20] addressed the missing values in IISs by means of the Hopfield neural network approach. Salama et al. [21] proposed a topology method to retrieve missing values in IISs. Clearly, these methods of filling missing values were founded through the other theories, such as, neural network and topology. In this paper, we establish a new method to fill missing values by means of rough set theory. Next, we state the motivation of giving this method. We know that the indiscernibility relation is a basic concept in rough set theory. Given a complete information system, we can establish an indiscernibility relation. Two objects are viewed as indiscernible if they have the same values for each attribute. Therefore, we think that if two objects possess more the same values of attributes, then they have the higher degree of indiscernibility. Based on the observation, we provide a method to fill missing values. By using this method, we can convert the missing values into fuzzy set values by evaluating the relationship between the attribute values of different objects, and then we can transform fuzzy set values into set values or real values according to the principle of maximum membership degree in fuzzy set theory. It is worth noting that, in order to construct this method, we established a new information system, namely, the fuzzy set-valued information system (FSvIS) which plays an important role in the method.The rest of this paper is organized as follows. In Section2, some basic concepts and notations of rough sets and fuzzy sets are given. In Section 3, we propose the fuzzy set-valued information system (FSvIS), and we induce some binary relations from FSvISs. Furthermore, we investigate the connections between these binary relations. In Section 4, we provide two methods of filling missing values. One is to fill missing values with fuzzy set values, and the other is to fill missing values with set values (or real values). In Section 5, we perform several experiments to analyze the effectiveness of the proposed methods. In Section 6, we apply the proposed methods of filling missing values to investigate IISs. Section 7 concludes this paper.


## 2. Basic Concepts and Properties

In this section, we review some basic concepts and notations in rough sets and fuzzy sets.


### 2.1. Basic Concepts for Rough Sets

In this subsection, we review some basic concepts related to general binary relations and information systems [22–24].Definition 1 (see [23]).
A general binary relation on a nonempty set U is a subset ofU×U. R is called(1)
Reflexive, if for anyx∈U, x,x∈R(2)
Symmetric, if for anyx,y∈U, x,y∈R implies y,x∈R(3)
Transitive, if for anyx,y,z∈U, x,y∈R and y,z∈R imply x,z∈R
Generally, ifR satisfies reflexive and symmetric, it is called a similarity relation; if R satisfies reflexive, symmetric, and transitive, then it is called an equivalence relation.
LetR be a general binary relation on U, for x∈U, and the successor neighbourhood Rx of x with respect to R is defined by(1)Rx=y∈Ux,y∈R.
A tripleU,Att,V is called an information system, where U is a finite nonempty set of objects called the universe, Att is a finite nonempty set of attributes, and V=∪a∈AttVa, where Va called the domain of a is a nonempty set of values of attribute a∈Att. If there exist x∈U and a∈Att such that the value ax of x under a is a missing value (a null of unknown value), denoted as “∗,” that is, ∃a∈Att, ∗∈Va, then the information system is called an incomplete information system (IIS).
In order to investigate theIIS by using rough set approach, Kryszkiewic [13] presented a way to induce a relation in the IIS U,Att,V as follows for B⊆Att:(2)TB=x,y∈U×Uax=ay∨ax=∗∨ay=∗,∀a∈B.
It is easy to check thatTB is reflexive and symmetric, that is to say, TB is a similarity relation on U.
In this paper, we callU,R a generalized approximation space, where R is a binary relation on a finite nonempty set U.Definition 2 (see [1]).
Given a generalized approximation spaceU,R and X⊆U, the lower approximation and upper approximation of X are defined as follows:(3)apr¯RX=x∈URx⊆X,apr¯RX=x∈URx∩X≠∅.
In [23], Wang et al. constructed an uncertainty measure in generalized approximation spaces, which is defined as follows:Definition 3.
LetU,R be a generalized approximation space. The entropy of R is defined as follows:(4)HR=−1U∑x∈UlogRxU.Proposition 1 (see [23]).
LetR1 and R2 be binary relations on U. If R1⊆R2, then HR1≥HR2.


### 2.2. Basic Concepts for Fuzzy Sets

In this section, we introduce some basic concepts and measures about fuzzy sets.A fuzzy subsetA of a nonempty set U is a map from U to 0,1 [25]. The collection of all fuzzy subsets of U is denoted as ℱU. Similarity measure is an important concept in fuzzy set theory, and it is defined as follows:Definition 4 (see [26]).
A functionS:ℱU×ℱU⟶0,1 is called a similarity measure on ℱU, if S satisfies the following properties:(1)
SU,∅=0 and SA,A=1 for all A∈ℱU(2)
SA,B=SB,A for all A,B∈ℱU(3)
For allA,B,C∈ℱU, A⊆B⊆C, then SA,C≤SB,C and SA,C≤SA,BParticularly, a similarity measure S is called a strictly similarity measure if it also satisfies(4)
SA,B=1 if and only if A=B, for all A,B∈ℱU
LetU=x1,x2,…xn and A,B∈ℱU. The most popular similarity measures include:(1)
Hamming similarity measure [27]:(5)SHA,B=1−1n∑i=1nAxi−Bxi.(2)
Euclidean similarity measure [27]:(6)SEA,B=1−1n∑i=1nAxi−Bxi21/2.(3)
Max-min similarity measure [28]:(7)SNA,B=∑i=1nAxi∧Bxi∑i=1nAxi∨Bxi.Remark 1.
In this paper, we always assume that∑i=1nAxi∨Bxi≠0.


## 2.1. Basic Concepts for Rough Sets

In this subsection, we review some basic concepts related to general binary relations and information systems [22–24].Definition 1 (see [23]).
A general binary relation on a nonempty set U is a subset ofU×U. R is called(1)
Reflexive, if for anyx∈U, x,x∈R(2)
Symmetric, if for anyx,y∈U, x,y∈R implies y,x∈R(3)
Transitive, if for anyx,y,z∈U, x,y∈R and y,z∈R imply x,z∈R
Generally, ifR satisfies reflexive and symmetric, it is called a similarity relation; if R satisfies reflexive, symmetric, and transitive, then it is called an equivalence relation.
LetR be a general binary relation on U, for x∈U, and the successor neighbourhood Rx of x with respect to R is defined by(1)Rx=y∈Ux,y∈R.
A tripleU,Att,V is called an information system, where U is a finite nonempty set of objects called the universe, Att is a finite nonempty set of attributes, and V=∪a∈AttVa, where Va called the domain of a is a nonempty set of values of attribute a∈Att. If there exist x∈U and a∈Att such that the value ax of x under a is a missing value (a null of unknown value), denoted as “∗,” that is, ∃a∈Att, ∗∈Va, then the information system is called an incomplete information system (IIS).
In order to investigate theIIS by using rough set approach, Kryszkiewic [13] presented a way to induce a relation in the IIS U,Att,V as follows for B⊆Att:(2)TB=x,y∈U×Uax=ay∨ax=∗∨ay=∗,∀a∈B.
It is easy to check thatTB is reflexive and symmetric, that is to say, TB is a similarity relation on U.
In this paper, we callU,R a generalized approximation space, where R is a binary relation on a finite nonempty set U.Definition 2 (see [1]).
Given a generalized approximation spaceU,R and X⊆U, the lower approximation and upper approximation of X are defined as follows:(3)apr¯RX=x∈URx⊆X,apr¯RX=x∈URx∩X≠∅.
In [23], Wang et al. constructed an uncertainty measure in generalized approximation spaces, which is defined as follows:Definition 3.
LetU,R be a generalized approximation space. The entropy of R is defined as follows:(4)HR=−1U∑x∈UlogRxU.Proposition 1 (see [23]).
LetR1 and R2 be binary relations on U. If R1⊆R2, then HR1≥HR2.


## 2.2. Basic Concepts for Fuzzy Sets

In this section, we introduce some basic concepts and measures about fuzzy sets.A fuzzy subsetA of a nonempty set U is a map from U to 0,1 [25]. The collection of all fuzzy subsets of U is denoted as ℱU. Similarity measure is an important concept in fuzzy set theory, and it is defined as follows:Definition 4 (see [26]).
A functionS:ℱU×ℱU⟶0,1 is called a similarity measure on ℱU, if S satisfies the following properties:(1)
SU,∅=0 and SA,A=1 for all A∈ℱU(2)
SA,B=SB,A for all A,B∈ℱU(3)
For allA,B,C∈ℱU, A⊆B⊆C, then SA,C≤SB,C and SA,C≤SA,BParticularly, a similarity measure S is called a strictly similarity measure if it also satisfies(4)
SA,B=1 if and only if A=B, for all A,B∈ℱU
LetU=x1,x2,…xn and A,B∈ℱU. The most popular similarity measures include:(1)
Hamming similarity measure [27]:(5)SHA,B=1−1n∑i=1nAxi−Bxi.(2)
Euclidean similarity measure [27]:(6)SEA,B=1−1n∑i=1nAxi−Bxi21/2.(3)
Max-min similarity measure [28]:(7)SNA,B=∑i=1nAxi∧Bxi∑i=1nAxi∨Bxi.Remark 1.
In this paper, we always assume that∑i=1nAxi∨Bxi≠0.


## 3. Fuzzy Set-Valued Information Systems (FSvISs)

In this section, we replace the real number in the real-valued information system with fuzzy set and propose a more general information system, that is, the fuzzy set-valued information system. It can be seen as a generalization of the probabilistic set-valued information system defined by Huang et al. [29].Definition 5.
A fuzzy set-valued information system (FSvIS) is a tripleU,Att,ℱV, where U is a nonempty set, Att is a set of attributes, and V is the basic set of attribute values. In addition, for all a∈Att and x∈U, the value ax of x under a is a fuzzy subset of V, that is, ax∈ℱV.
In some cases, if the attribute values are uncertain or missing, then it is reasonable to describe them with fuzzy set values. For example, in IISs, we may fill the missing values with fuzzy set values. In this paper, we will investigate IISs by means of FSvISs.Example 1.
Table1 gives a FSvIS U,Att,ℱV, where U=x1,x2,x3,x4,x5, Att=a1,a2,a3, and V=−1,0,1. In Table 1, a1x1=0.23/−1+0.42/0+0.76/1 represents the value of the object x1 under attribute a1. a1x1−1=0.23 is the grade of membership of −1 in a1x1.Table 1
A fuzzy set-valued information system.
Objects
a
1
a
2
a
3
x
1
0.23
/
−
1
+
0.42
/
0
+
0.38
/
1
0.45
/
−
1
+
0.22
/
0
+
0.15
/
1
0.32
/
−
1
+
0.21
/
0
+
0.58
/
1
x
2
0.15
/
−
1
+
0.23
/
0
+
0.76
/
1
0.15
/
−
1
+
0.26
/
0
+
0.89
/
1
0.28
/
0
+
0.85
/
1
x
3
0.25
/
−
1
+
0.43
/
0
+
0.36
/
1
0.43
/
−
1
+
0.26
/
0
+
0.12
/
1
0.33
/
−
1
+
0.22
/
0
+
0.57
/
1
x
4
0.21
/
−
1
+
0.41
/
0
+
0.35
/
1
0.14
/
−
1
+
0.25
/
0
+
0.87
/
1
0.34
/
−
1
+
0.20
/
0
+
0.59
/
1
x
5
0.37
/
−
1
+
0.86
/
0
0.42
/
−
1
+
0.24
/
0
+
0.13
/
1
0.73
/
−
1
+
0.15
/
0
+
0.23
/
1


### 3.1. The Similarity Relations in FSvISs

The rough set approach is applied for rule extractions and attribute reductions in information systems. The key problem is how to construct binary relations from information systems. Next, we will establish some similarity relations in FSvISs. Then, we establish the relationships between them.It is well known that, in fuzzy set theory, similarity measure is an important concept to evaluate the similarity degree between fuzzy sets.LetU,Att,ℱV be a FSvIS, S be a similarity measure and λ∈0,1. There is a common method to construct binary relation in terms of similarity measure as follows:(8)RBSλ=x,y∈U×USax,ay≥λ,∀a∈B,where ∅≠B⊆Att. Clearly, RBSλ is a binary relation on U. The successor neighbourhood of x∈U can be computed as follows:(9)RBSλx=y∈USax,ay≥λ,∀a∈B.In the following section, we limitB≠∅.By (1) of Definition4, RBSλ is reflexive. In addition, the symmetry of RBSλ is clear. Therefore, the following result is obvious.Proposition 2.
LetU,Att,ℱV be a FSvIS, S be a similarity measure, B⊆Att, and λ∈0,1. Then, the binary relation RBSλ is reflexive and symmetric.
Proposition2 shows that RBSλ is a similarity relation.Remark 2.
By equations (5)–(8), we can obtain three similarity relations: RBSHλ, RBSEλ, and RBSNλ.Proposition 3.
LetU,Att,ℱV be a FSvIS, S be a similarity measure, B⊆Att, and λ∈0,1. The following statements hold:(1)
If∅≠C⊆B, then RBSλ⊆RCSλ(2)
If0≤λ1≤λ2≤1, then RBSλ2⊆RBSλ1Proof.
(1)
We only need to prove that∀x∈U, RBSλx⊆RCSλx. ∀y∈RBSλx, by equation (9), we have that ∀a∈B, Sax,ay≥λ. By C⊆B, it is clear that ∀a∈C, Sax,ay≥λ. It follows from equation (7) that y∈RCSλx. Hence, RBSλx⊆RCSλx. Consequently, RBSλ⊆RCSλ.(2)
We only need to prove that∀x∈U, RBSλ2x⊆RBSλ1x. ∀y∈RBSλ2x, by equation (9), we have that ∀a∈B, Sax,ay≥λ2. By λ1≤λ2, it is clear that ∀a∈B, Sax,ay≥λ1. It follows from equation (8) that y∈RBSλ1x. Hence, RBSλ2x⊆RBSλ1x. Consequently, RBSλ2⊆RBSλ1.
In the following, we establish the relationships amongRBSHλ, RBSEλ, and RBSNλ. Firstly, we provide the connections among the similarity measures given by equations (5)–(7).Proposition 4.
Let U be a nonempty set. The following statements hold:(1)
∀A1,A2∈ℱU, SNA1,A2≤SHA1,A2(2)
∀A1,A2∈ℱU, SEA1,A2≤SHA1,A2Proof.
(1)
We may assume thatU=x1,x2,…,xn. Let A1,A2∈ℱU. It is easy to verify that(10)∑i=1nA1xi∨A2xi−∑i=1nA1xi∧A2xi=∑i=1nA1xi∨A2xi−A1xi∧A2xi=∑i=1nA1xi−A2xi,that is,(11)∑i=1nA1xi∨A2xi−∑i=1nA1xi∧A2xi=∑i=1nA1xi−A2xi.In addition, it is clear that(12)1n∑i=1nA1xi∨A2xi≤1.Therefore, by equations (11) and (12), we have that(13)∑i=1nA1xi−A2xi1n∑i=1nA1xi∨A2xi≤∑i=1nA1xi−A2xi=∑i=1nA1xi∨A2xi−∑i=1nA1xi∧A2xi.Thus,(14)∑i=1nA1xi∧A2xi≤∑i=1nA1xi∨A2xi−∑i=1nA1xi−A2xi1n∑i=1nA1xi∨A2xi.By Remark1, ∑i=1nA1xi∨A2xi≠0. Therefore,(15)∑i=1nA1xi∧A2xi∑i=1nA1xi∨A2xi≤1−1n∑i=1nA1xi−A2xi.By equations (5) and (7), we conclude that SNA1,A2≤SHA1,A2.(2)
LetA1,A2∈ℱU. Next, we will use mathematical induction to prove SEA1,A2≤SHA1,A2. If n=1, it is clear that SEA1,A2=SHA1,A2, which implies that SEA1,A2≤SHA1,A2 is true.Assume thatSEA1,A2≤SHA1,A2 is true when n=k. By equations (5) and (6), we have that(16)1−1k∑i=1kA1xi−A2xi21/2≤1−1k∑i=1kA1xi−A2xi,whereU=x1,x2,…,xk. This implies that(17)∑i=1kA1xi−A2xi2≤k⋅∑i=1kA1xi−A2xi2.Next, we shall prove that the conclusion is true whenn=k+1. By equation (5) and (6), we only need to prove that(18)1k+1∑i=1k+1A1xi−A2xi≤1k+1∑i=1k+1A1xi−A2xi21/2,that is,(19)∑i=1k+1A1xi−A2xi2≤k+1∑i=1k+1A1xi−A2xi2.For simplicity, we writeMi=A1xi−A2xi. Hence, we only need to prove that(20)∑i=1k+1Mi2≤k+1∑i=1k+1Mi2.In addition, equation (17) can be written by(21)∑i=1kMi2≤k⋅∑i=1kMi2.By equation (21), it is clear that(22)∑i=1k+1Mi2=∑i=1kMi+Mk+12=∑i=1kMi2+2Mk+1∑i=1kMi+Mk+12≤k⋅∑i=1kMi2+2Mk+1∑i=1kMi+Mk+12=k⋅∑i=1kMi2+∑i=1k2Mk+1Mi+Mk+12≤k⋅∑i=1kMi2+∑i=1kMk+12+Mi2+Mk+12=k⋅∑i=1kMi2+kMk+12+∑i=1kMi2+Mk+12=k⋅∑i=1k+1Mi2+∑i=1k+1Mi2=k+1∑i=1k+1Mi2.This completes the proof.According to Proposition4 and equation (8), the following result is obvious.Theorem 1.
LetU,Att,ℱV be a FSvIS, B⊆Att and λ∈0,1. Then, the following statements hold:(1)
RBSNλ⊆RBSHλ(2)
RBSEλ⊆RBSHλ


### 3.2. The Uncertainty Measures of FSvISs

In Section3.1, we establish three similarity relations in FSvISs. If we use the rough set approach to investigate FSvISs, we usually need to choose reasonable similarity relations according to the actual condition. Therefore, in this section, we discuss the uncertainty measures of these similarity relations so as to provide evidence for the choice of similarity relations.Proposition 5.
LetU,Att,ℱV be a FSvIS, B⊆Att and λ∈0,1. The following statements hold:(1)
∀X⊆U, apr¯RBSNλX⊇apr¯RBSHλX and apr¯RBSEλX⊇apr¯RBSHλX(2)
∀X⊆U, apr¯RBSNλX⊆apr¯RBSHλX and apr¯RBSEλX⊆apr¯RBSHλXProof.
It is straightforward from Theorem1 and Definition 2.Proposition 6.
LetU,Att,ℱV be a FSvIS, B⊆Att and λ∈0,1. The following statements hold:(1)
HRBSNλ≥HRBSHλ(2)
HRBSEλ≥HRBSHλProof.
It is straightforward from Theorem1 and Proposition 1.


## 3.1. The Similarity Relations in FSvISs

The rough set approach is applied for rule extractions and attribute reductions in information systems. The key problem is how to construct binary relations from information systems. Next, we will establish some similarity relations in FSvISs. Then, we establish the relationships between them.It is well known that, in fuzzy set theory, similarity measure is an important concept to evaluate the similarity degree between fuzzy sets.LetU,Att,ℱV be a FSvIS, S be a similarity measure and λ∈0,1. There is a common method to construct binary relation in terms of similarity measure as follows:(8)RBSλ=x,y∈U×USax,ay≥λ,∀a∈B,where ∅≠B⊆Att. Clearly, RBSλ is a binary relation on U. The successor neighbourhood of x∈U can be computed as follows:(9)RBSλx=y∈USax,ay≥λ,∀a∈B.In the following section, we limitB≠∅.By (1) of Definition4, RBSλ is reflexive. In addition, the symmetry of RBSλ is clear. Therefore, the following result is obvious.Proposition 2.
LetU,Att,ℱV be a FSvIS, S be a similarity measure, B⊆Att, and λ∈0,1. Then, the binary relation RBSλ is reflexive and symmetric.
Proposition2 shows that RBSλ is a similarity relation.Remark 2.
By equations (5)–(8), we can obtain three similarity relations: RBSHλ, RBSEλ, and RBSNλ.Proposition 3.
LetU,Att,ℱV be a FSvIS, S be a similarity measure, B⊆Att, and λ∈0,1. The following statements hold:(1)
If∅≠C⊆B, then RBSλ⊆RCSλ(2)
If0≤λ1≤λ2≤1, then RBSλ2⊆RBSλ1Proof.
(1)
We only need to prove that∀x∈U, RBSλx⊆RCSλx. ∀y∈RBSλx, by equation (9), we have that ∀a∈B, Sax,ay≥λ. By C⊆B, it is clear that ∀a∈C, Sax,ay≥λ. It follows from equation (7) that y∈RCSλx. Hence, RBSλx⊆RCSλx. Consequently, RBSλ⊆RCSλ.(2)
We only need to prove that∀x∈U, RBSλ2x⊆RBSλ1x. ∀y∈RBSλ2x, by equation (9), we have that ∀a∈B, Sax,ay≥λ2. By λ1≤λ2, it is clear that ∀a∈B, Sax,ay≥λ1. It follows from equation (8) that y∈RBSλ1x. Hence, RBSλ2x⊆RBSλ1x. Consequently, RBSλ2⊆RBSλ1.
In the following, we establish the relationships amongRBSHλ, RBSEλ, and RBSNλ. Firstly, we provide the connections among the similarity measures given by equations (5)–(7).Proposition 4.
Let U be a nonempty set. The following statements hold:(1)
∀A1,A2∈ℱU, SNA1,A2≤SHA1,A2(2)
∀A1,A2∈ℱU, SEA1,A2≤SHA1,A2Proof.
(1)
We may assume thatU=x1,x2,…,xn. Let A1,A2∈ℱU. It is easy to verify that(10)∑i=1nA1xi∨A2xi−∑i=1nA1xi∧A2xi=∑i=1nA1xi∨A2xi−A1xi∧A2xi=∑i=1nA1xi−A2xi,that is,(11)∑i=1nA1xi∨A2xi−∑i=1nA1xi∧A2xi=∑i=1nA1xi−A2xi.In addition, it is clear that(12)1n∑i=1nA1xi∨A2xi≤1.Therefore, by equations (11) and (12), we have that(13)∑i=1nA1xi−A2xi1n∑i=1nA1xi∨A2xi≤∑i=1nA1xi−A2xi=∑i=1nA1xi∨A2xi−∑i=1nA1xi∧A2xi.Thus,(14)∑i=1nA1xi∧A2xi≤∑i=1nA1xi∨A2xi−∑i=1nA1xi−A2xi1n∑i=1nA1xi∨A2xi.By Remark1, ∑i=1nA1xi∨A2xi≠0. Therefore,(15)∑i=1nA1xi∧A2xi∑i=1nA1xi∨A2xi≤1−1n∑i=1nA1xi−A2xi.By equations (5) and (7), we conclude that SNA1,A2≤SHA1,A2.(2)
LetA1,A2∈ℱU. Next, we will use mathematical induction to prove SEA1,A2≤SHA1,A2. If n=1, it is clear that SEA1,A2=SHA1,A2, which implies that SEA1,A2≤SHA1,A2 is true.Assume thatSEA1,A2≤SHA1,A2 is true when n=k. By equations (5) and (6), we have that(16)1−1k∑i=1kA1xi−A2xi21/2≤1−1k∑i=1kA1xi−A2xi,whereU=x1,x2,…,xk. This implies that(17)∑i=1kA1xi−A2xi2≤k⋅∑i=1kA1xi−A2xi2.Next, we shall prove that the conclusion is true whenn=k+1. By equation (5) and (6), we only need to prove that(18)1k+1∑i=1k+1A1xi−A2xi≤1k+1∑i=1k+1A1xi−A2xi21/2,that is,(19)∑i=1k+1A1xi−A2xi2≤k+1∑i=1k+1A1xi−A2xi2.For simplicity, we writeMi=A1xi−A2xi. Hence, we only need to prove that(20)∑i=1k+1Mi2≤k+1∑i=1k+1Mi2.In addition, equation (17) can be written by(21)∑i=1kMi2≤k⋅∑i=1kMi2.By equation (21), it is clear that(22)∑i=1k+1Mi2=∑i=1kMi+Mk+12=∑i=1kMi2+2Mk+1∑i=1kMi+Mk+12≤k⋅∑i=1kMi2+2Mk+1∑i=1kMi+Mk+12=k⋅∑i=1kMi2+∑i=1k2Mk+1Mi+Mk+12≤k⋅∑i=1kMi2+∑i=1kMk+12+Mi2+Mk+12=k⋅∑i=1kMi2+kMk+12+∑i=1kMi2+Mk+12=k⋅∑i=1k+1Mi2+∑i=1k+1Mi2=k+1∑i=1k+1Mi2.This completes the proof.According to Proposition4 and equation (8), the following result is obvious.Theorem 1.
LetU,Att,ℱV be a FSvIS, B⊆Att and λ∈0,1. Then, the following statements hold:(1)
RBSNλ⊆RBSHλ(2)
RBSEλ⊆RBSHλ


## 3.2. The Uncertainty Measures of FSvISs

In Section3.1, we establish three similarity relations in FSvISs. If we use the rough set approach to investigate FSvISs, we usually need to choose reasonable similarity relations according to the actual condition. Therefore, in this section, we discuss the uncertainty measures of these similarity relations so as to provide evidence for the choice of similarity relations.Proposition 5.
LetU,Att,ℱV be a FSvIS, B⊆Att and λ∈0,1. The following statements hold:(1)
∀X⊆U, apr¯RBSNλX⊇apr¯RBSHλX and apr¯RBSEλX⊇apr¯RBSHλX(2)
∀X⊆U, apr¯RBSNλX⊆apr¯RBSHλX and apr¯RBSEλX⊆apr¯RBSHλXProof.
It is straightforward from Theorem1 and Definition 2.Proposition 6.
LetU,Att,ℱV be a FSvIS, B⊆Att and λ∈0,1. The following statements hold:(1)
HRBSNλ≥HRBSHλ(2)
HRBSEλ≥HRBSHλProof.
It is straightforward from Theorem1 and Proposition 1.


## 4. Algorithms of Filling Missing Values in IISs

We know that complete information systems can be investigated by the rough set approach. In general, in order to discuss an IIS by means of rough set theory, we need to fill missing values in the IIS. That is to say, we first need to transform the IIS into a complete information system. In this section, we provide some methods to fill missing values in IISs. Note that data are often divided into two types: discrete data and continuous data. Next, we study the issue of filling missing data under two cases.


### 4.1. Algorithm of Filling Missing Values in IISs of Discrete Data

Clearly, the missing values possess the property of uncertainty; therefore, it is reasonable to use fuzzy set values (or set values) to fill missing values in IISs. In this section, we provide two schemes, namely, replacing the missing values with fuzzy set values and replacing the missing values with set values.


#### 4.1.1. Filling the Missing Values with Fuzzy Set Values

Next, we provide a method to fill missing values in IISs of discrete data. We replace the missing values with fuzzy set values. In fact, this method can transform IISs into FSvISs.In the IIS given by Table2, the value domain of a1 is L,H,N,∗, and the value of x2 under attribute a1 is the missing value, that is, a1x2=∗. We think that this missing value may be L or H or N. We cannot determine which one is a1x2, but we can find a way to evaluate the degree that L (or H or N) is a1x2. That is, we can replace the missing values with fuzzy sets on L,H,N. Next, we outline the main idea of filling missing data. The indiscernibility relation is a basic concept in rough set theory. Given a complete information system, we can establish an indiscernibility relation. Two objects are viewed as indiscernible if they have the same values for each attribute. Therefore, we think that if two objects possess more the same values of attributes, then they have the higher degree of indiscernibility. For example, in Table 2, a1x2=∗. x2 and x4 have the same values of five attributes a2,a3,a4,a5,a6; x2 and x3 have the same values of two attributes a2,a6. Thus, x2 and x4 have the higher degree of indiscernibility. That is to say, the possibility degree of a1x2=a1x4=H is more than that of a1x2=a1x3=N. Based on this observation, we obtain Algorithm 1.Table 2
An IIS of discrete data.
Objects
a
1
a
2
a
3
a
4
a
5
a
6
x
1
L
N
N
L
N
N
x
2
∗
H
H
H
H
H
x
3
N
H
N
N
N
H
x
4
H
H
H
H
H
H
x
5
N
H
N
N
N
HRemark 3.
In Step 2 of Algorithm1, Dxl,xi describes how many attributes for xl and xi have the same value. Thus, it can be used to characterize the degree of indiscernibility of xl and xi. In Step 3, tak/U can be considered as probability of the elements whose attribute values are t in U.Example 2.
In Table3, a1x5=∗. Clearly, Va1∗=L,H,N.Step 1: TakeL∈Va1∗. It is easy to compute that La1=x1,x4,x7,x8.Step 2: We can compute that(23)Dx5,x1=Dx5,x4=Dx5,x7=0,Dx5,x8=13.Thus,Dx5,La1=max0,1/3=1/3.Step 3:a1Fx5L=1/3.
Similarly, we can compute thata1Fx5H=1/3 and a1Fx5N=2/3. Therefore, we fill the missing value a1x5 with the following fuzzy set:(24)a1Fx5=1/3L+1/3H+2/3N.Table 3
Missing dataset.
Objects
a
1
a
2
a
3
x
1
L
N
N
x
2
H
L
H
x
3
N
H
N
x
4
L
L
L
x
5
∗
H
H
x
6
N
H
H
x
7
L
∗
L
x
8
L
H
N
x
9
∗
N
H
x
10
H
L
N


#### 4.1.2. Filling the Missing Values with Set Values

Based on the discussion of Section4.1.1, we can replace a missing value with a fuzzy set. In fact, we can transform the fuzzy set into a set by means of the maximum membership degree law. Let U,Att,V be an IIS of discrete data. Assume that akxl=∗, where xl∈U and ak∈Att. By Algorithm 1, we obtain the fuzzy set akFxl. Thus, we can use the following set to fill the missing value akxl:(25)akSxl=t∈Vak∗akFxlt=M,whereM=maxakFxltt∈Vak∗.Algorithm 1: Filling the missing values in IISs of discrete data with fuzzy set values.
LetU,Att,V be an IIS of discrete data. Assume that akxl=∗, where xl∈U and ak∈Att. Vak∗ denotes the set Vak−∗, that is, Vak∗=Vak−∗. We shall use a fuzzy set of Vak∗ to represent the missing value akxl, and we denote the fuzzy set by akFxl. Thus, ∀t∈Vak∗, we need to compute the membership degree akFxlt. Next, we establish the steps of filling the missing value akxl as follows:
Step 1:∀t∈Vak∗, compute tak=xi∈Uakxi=t
Step 2: ComputeDxl,tak=maxDxl,xixi∈tak, where Dxl,xi=aj∈Attajxl=ajxi/Att
Step 3: Assign a value toakFxlt, akFxlt=Dxl,tak,Dxl,tak≠0,tak/U,Dxl,tak=0.Example 3.
In Example2, we obtain that a1Fx5=1/3/L+1/3/H+2/3/N. Thus, the maximal membership degree M is 2/3, that is, M=2/3. By equation (25), we have that a1Sx5=N. That is to say, we can fill the missing value a1x5 with the set N. In Table 4, we know that a1x5 should be N. This coincides with the filling values by our algorithm.
In Table3, a1x9 and a2x7 are also missing. By Algorithm 1, we can obtain that(26)a1Fx9=1/3L+1/3H+1/3N,a2Fx7=2/3L+1/3H+1/3N.
Thus, we have thata1Sx9=L,H,N and a2Sx7=L.Table 4
Original dataset of Table3.
Objects
a
1
a
2
a
3
x
1
L
N
N
x
2
H
L
H
x
3
N
H
N
x
4
L
L
L
x
5
N
H
H
x
6
N
H
H
x
7
L
L
L
x
8
L
H
N
x
9
N
N
H
x
10
H
L
N


### 4.2. Algorithm of Filling Missing Values in IISs of Continuous Data

Similar to the discussion of Section4.1, we investigate the corresponding issues of IISs of continuous data in this section.


#### 4.2.1. Filling the Missing Values with Fuzzy Set Values

Similar to Algorithm1, we give Algorithm 2 to fill the missing value in IISs of continuous data.Example 4.
In this example, we discuss the Iris information system given by Table5 from UCI. Suppose that a1x5 and a2x7 in Table 5 are missing. We obtain Table 6. Next, we use the IIS given by Table 6 to illustrate Algorithm 2.
In Table6, a1x5=∗. Clearly, Va1∗=4.3,4.9,5.4,5.7,5.8,6.3,6.6. We take the thresholds λ1=0.2 and λ2=λ3=λ4=0.5.Step 1: Take4.3∈Va1∗. It is easy to compute that 4.3λ1a1=xi∈Ua1xi−4.3≤0.2=x1.Step 2: Sincea2x1−a2x5=0.5≤λ2=0.5, a3x1−a3x5=0.3≤λ3=0.5, and a4x1−a4x5=0.2≤λ4=0.5, it follows that aj∈Attajx5−ajx1≤λj=a2,a3,a4, and thus Dx5,x1=3/4. This implies that Dx5,4.3λ1a1=max3/4=0.75.Step 3:a1Fx54.3=0.75.
Similarly, we can compute thata1Fx54.9=0, a1Fx55.4=0.75, a1Fx55.7=0.75, a1Fx55.8=0.75, a1Fx56.3=0.25, and a1Fx56.6=0. Therefore, we fill the missing value a1x5 with the following fuzzy set:(27)a1Fx5=0.754.3+04.9+0.755.4+0.755.7+0.755.8+0.256.3+06.6.Table 5
Original dataset of Table6.
Objects
a
1
a
2
a
3
a
4
x
1
4.3
3
1.1
0.1
x
2
5.8
4
1.2
0.2
x
3
5.7
4.4
1.5
0.4
x
4
5.4
3.9
1.3
0.4
x
5
5.1
3.5
1.4
0.3
x
6
5.7
3.8
1.7
0.31
x
7
5.7
2.8
4.5
1.3
x
8
6.3
3.3
4.7
1.6
x
9
4.9
2.4
3.3
1
x
10
6.6
2.9
4.6
1.3Table 6
Missing dataset.
Objects
a
1
a
2
a
3
a
4
x
1
4.3
3
1.1
0.1
x
2
5.8
4
1.2
0.2
x
3
5.7
4.4
1.5
0.4
x
4
5.4
3.9
1.3
0.4
x
5
∗
3.5
1.4
0.3
x
6
5.7
3.8
1.7
0.31
x
7
5.7
∗
4.5
1.3
x
8
6.3
3.3
4.7
1.6
x
9
4.9
2.4
3.3
1
x
10
6.6
2.9
4.6
1.3Algorithm 2: Filling the missing values in IISs of continuous data with fuzzy set values.
LetU,Att,V be an IIS of continuous data. Assume that akxl=∗, where xl∈U and ak∈Att. Vak∗ denotes the set Vak−∗. We shall use a fuzzy set of Vak∗ to represent the missing value akxl, and we denote the fuzzy set by akFxl. Thus, ∀t∈Vak∗, and we need to compute the membership degree akFxlt. Next, we establish the steps of filling the missing value akxl as follows:
Step 1:∀t∈Vak∗, compute tλkak=xi∈Uakxi−t≤λk, where λk is a threshold on ak
Step 2: ComputeDxl,tλkak=maxDxl,xixi∈tλkak, where Dxl,xi=aj∈Attajxl−ajxi≤λj/Att.
Step 3: Assign a value toakFxlt, akFxlt=Dxl,tλkak,Dxl,tλkak≠0,tλkak/U,Dxl,tλkak=0.


#### 4.2.2. Filling the Missing Values with Real Values

Based on the discussion of Section4.2.1, we can replace a missing value with a fuzzy set. Clearly, we can transform the fuzzy set into real value by means of the maximum membership degree law. Let U,Att,V be an IIS of continuous data. Assume that akxl=∗, where xl∈U and ak∈Att. By Algorithm 2, we obtain the fuzzy set akFxl. Thus, we can use the following real value to fill the missing value akxl:(28)akRxl=∑t∈smdtsmd,where smd=t∈Vak∗akFxlt=M and M=maxakFxltt∈Vak∗.Example 5.
From Example4, we know that(29)a1Fx5=0.754.3+04.9+0.755.4+0.755.7+0.755.8+0.256.3+06.6.
By equation (28), we compute that(30)M=0.75,smd=4.3,5.4,5.7,5.8.
Thus, we obtain thata1Rx5=4.3+5.4+5.7+5.8/4=5.3.Remark 4.
By Table5, we know that a1x5 should be 5.1. By Example 5, we fill the value a1Rx5=5.3 under the assumption that a1x5 and a2x7 are missing. The deviation of a1x5 and a1Rx5=5.3 is within 0.2. This indicates that the method of filling missing value is effective.


## 4.1. Algorithm of Filling Missing Values in IISs of Discrete Data

Clearly, the missing values possess the property of uncertainty; therefore, it is reasonable to use fuzzy set values (or set values) to fill missing values in IISs. In this section, we provide two schemes, namely, replacing the missing values with fuzzy set values and replacing the missing values with set values.


### 4.1.1. Filling the Missing Values with Fuzzy Set Values

Next, we provide a method to fill missing values in IISs of discrete data. We replace the missing values with fuzzy set values. In fact, this method can transform IISs into FSvISs.In the IIS given by Table2, the value domain of a1 is L,H,N,∗, and the value of x2 under attribute a1 is the missing value, that is, a1x2=∗. We think that this missing value may be L or H or N. We cannot determine which one is a1x2, but we can find a way to evaluate the degree that L (or H or N) is a1x2. That is, we can replace the missing values with fuzzy sets on L,H,N. Next, we outline the main idea of filling missing data. The indiscernibility relation is a basic concept in rough set theory. Given a complete information system, we can establish an indiscernibility relation. Two objects are viewed as indiscernible if they have the same values for each attribute. Therefore, we think that if two objects possess more the same values of attributes, then they have the higher degree of indiscernibility. For example, in Table 2, a1x2=∗. x2 and x4 have the same values of five attributes a2,a3,a4,a5,a6; x2 and x3 have the same values of two attributes a2,a6. Thus, x2 and x4 have the higher degree of indiscernibility. That is to say, the possibility degree of a1x2=a1x4=H is more than that of a1x2=a1x3=N. Based on this observation, we obtain Algorithm 1.Table 2
An IIS of discrete data.
Objects
a
1
a
2
a
3
a
4
a
5
a
6
x
1
L
N
N
L
N
N
x
2
∗
H
H
H
H
H
x
3
N
H
N
N
N
H
x
4
H
H
H
H
H
H
x
5
N
H
N
N
N
HRemark 3.
In Step 2 of Algorithm1, Dxl,xi describes how many attributes for xl and xi have the same value. Thus, it can be used to characterize the degree of indiscernibility of xl and xi. In Step 3, tak/U can be considered as probability of the elements whose attribute values are t in U.Example 2.
In Table3, a1x5=∗. Clearly, Va1∗=L,H,N.Step 1: TakeL∈Va1∗. It is easy to compute that La1=x1,x4,x7,x8.Step 2: We can compute that(23)Dx5,x1=Dx5,x4=Dx5,x7=0,Dx5,x8=13.Thus,Dx5,La1=max0,1/3=1/3.Step 3:a1Fx5L=1/3.
Similarly, we can compute thata1Fx5H=1/3 and a1Fx5N=2/3. Therefore, we fill the missing value a1x5 with the following fuzzy set:(24)a1Fx5=1/3L+1/3H+2/3N.Table 3
Missing dataset.
Objects
a
1
a
2
a
3
x
1
L
N
N
x
2
H
L
H
x
3
N
H
N
x
4
L
L
L
x
5
∗
H
H
x
6
N
H
H
x
7
L
∗
L
x
8
L
H
N
x
9
∗
N
H
x
10
H
L
N


### 4.1.2. Filling the Missing Values with Set Values

Based on the discussion of Section4.1.1, we can replace a missing value with a fuzzy set. In fact, we can transform the fuzzy set into a set by means of the maximum membership degree law. Let U,Att,V be an IIS of discrete data. Assume that akxl=∗, where xl∈U and ak∈Att. By Algorithm 1, we obtain the fuzzy set akFxl. Thus, we can use the following set to fill the missing value akxl:(25)akSxl=t∈Vak∗akFxlt=M,whereM=maxakFxltt∈Vak∗.Algorithm 1: Filling the missing values in IISs of discrete data with fuzzy set values.
LetU,Att,V be an IIS of discrete data. Assume that akxl=∗, where xl∈U and ak∈Att. Vak∗ denotes the set Vak−∗, that is, Vak∗=Vak−∗. We shall use a fuzzy set of Vak∗ to represent the missing value akxl, and we denote the fuzzy set by akFxl. Thus, ∀t∈Vak∗, we need to compute the membership degree akFxlt. Next, we establish the steps of filling the missing value akxl as follows:
Step 1:∀t∈Vak∗, compute tak=xi∈Uakxi=t
Step 2: ComputeDxl,tak=maxDxl,xixi∈tak, where Dxl,xi=aj∈Attajxl=ajxi/Att
Step 3: Assign a value toakFxlt, akFxlt=Dxl,tak,Dxl,tak≠0,tak/U,Dxl,tak=0.Example 3.
In Example2, we obtain that a1Fx5=1/3/L+1/3/H+2/3/N. Thus, the maximal membership degree M is 2/3, that is, M=2/3. By equation (25), we have that a1Sx5=N. That is to say, we can fill the missing value a1x5 with the set N. In Table 4, we know that a1x5 should be N. This coincides with the filling values by our algorithm.
In Table3, a1x9 and a2x7 are also missing. By Algorithm 1, we can obtain that(26)a1Fx9=1/3L+1/3H+1/3N,a2Fx7=2/3L+1/3H+1/3N.
Thus, we have thata1Sx9=L,H,N and a2Sx7=L.Table 4
Original dataset of Table3.
Objects
a
1
a
2
a
3
x
1
L
N
N
x
2
H
L
H
x
3
N
H
N
x
4
L
L
L
x
5
N
H
H
x
6
N
H
H
x
7
L
L
L
x
8
L
H
N
x
9
N
N
H
x
10
H
L
N


## 4.1.1. Filling the Missing Values with Fuzzy Set Values

Next, we provide a method to fill missing values in IISs of discrete data. We replace the missing values with fuzzy set values. In fact, this method can transform IISs into FSvISs.In the IIS given by Table2, the value domain of a1 is L,H,N,∗, and the value of x2 under attribute a1 is the missing value, that is, a1x2=∗. We think that this missing value may be L or H or N. We cannot determine which one is a1x2, but we can find a way to evaluate the degree that L (or H or N) is a1x2. That is, we can replace the missing values with fuzzy sets on L,H,N. Next, we outline the main idea of filling missing data. The indiscernibility relation is a basic concept in rough set theory. Given a complete information system, we can establish an indiscernibility relation. Two objects are viewed as indiscernible if they have the same values for each attribute. Therefore, we think that if two objects possess more the same values of attributes, then they have the higher degree of indiscernibility. For example, in Table 2, a1x2=∗. x2 and x4 have the same values of five attributes a2,a3,a4,a5,a6; x2 and x3 have the same values of two attributes a2,a6. Thus, x2 and x4 have the higher degree of indiscernibility. That is to say, the possibility degree of a1x2=a1x4=H is more than that of a1x2=a1x3=N. Based on this observation, we obtain Algorithm 1.Table 2
An IIS of discrete data.
Objects
a
1
a
2
a
3
a
4
a
5
a
6
x
1
L
N
N
L
N
N
x
2
∗
H
H
H
H
H
x
3
N
H
N
N
N
H
x
4
H
H
H
H
H
H
x
5
N
H
N
N
N
HRemark 3.
In Step 2 of Algorithm1, Dxl,xi describes how many attributes for xl and xi have the same value. Thus, it can be used to characterize the degree of indiscernibility of xl and xi. In Step 3, tak/U can be considered as probability of the elements whose attribute values are t in U.Example 2.
In Table3, a1x5=∗. Clearly, Va1∗=L,H,N.Step 1: TakeL∈Va1∗. It is easy to compute that La1=x1,x4,x7,x8.Step 2: We can compute that(23)Dx5,x1=Dx5,x4=Dx5,x7=0,Dx5,x8=13.Thus,Dx5,La1=max0,1/3=1/3.Step 3:a1Fx5L=1/3.
Similarly, we can compute thata1Fx5H=1/3 and a1Fx5N=2/3. Therefore, we fill the missing value a1x5 with the following fuzzy set:(24)a1Fx5=1/3L+1/3H+2/3N.Table 3
Missing dataset.
Objects
a
1
a
2
a
3
x
1
L
N
N
x
2
H
L
H
x
3
N
H
N
x
4
L
L
L
x
5
∗
H
H
x
6
N
H
H
x
7
L
∗
L
x
8
L
H
N
x
9
∗
N
H
x
10
H
L
N


## 4.1.2. Filling the Missing Values with Set Values

Based on the discussion of Section4.1.1, we can replace a missing value with a fuzzy set. In fact, we can transform the fuzzy set into a set by means of the maximum membership degree law. Let U,Att,V be an IIS of discrete data. Assume that akxl=∗, where xl∈U and ak∈Att. By Algorithm 1, we obtain the fuzzy set akFxl. Thus, we can use the following set to fill the missing value akxl:(25)akSxl=t∈Vak∗akFxlt=M,whereM=maxakFxltt∈Vak∗.Algorithm 1: Filling the missing values in IISs of discrete data with fuzzy set values.
LetU,Att,V be an IIS of discrete data. Assume that akxl=∗, where xl∈U and ak∈Att. Vak∗ denotes the set Vak−∗, that is, Vak∗=Vak−∗. We shall use a fuzzy set of Vak∗ to represent the missing value akxl, and we denote the fuzzy set by akFxl. Thus, ∀t∈Vak∗, we need to compute the membership degree akFxlt. Next, we establish the steps of filling the missing value akxl as follows:
Step 1:∀t∈Vak∗, compute tak=xi∈Uakxi=t
Step 2: ComputeDxl,tak=maxDxl,xixi∈tak, where Dxl,xi=aj∈Attajxl=ajxi/Att
Step 3: Assign a value toakFxlt, akFxlt=Dxl,tak,Dxl,tak≠0,tak/U,Dxl,tak=0.Example 3.
In Example2, we obtain that a1Fx5=1/3/L+1/3/H+2/3/N. Thus, the maximal membership degree M is 2/3, that is, M=2/3. By equation (25), we have that a1Sx5=N. That is to say, we can fill the missing value a1x5 with the set N. In Table 4, we know that a1x5 should be N. This coincides with the filling values by our algorithm.
In Table3, a1x9 and a2x7 are also missing. By Algorithm 1, we can obtain that(26)a1Fx9=1/3L+1/3H+1/3N,a2Fx7=2/3L+1/3H+1/3N.
Thus, we have thata1Sx9=L,H,N and a2Sx7=L.Table 4
Original dataset of Table3.
Objects
a
1
a
2
a
3
x
1
L
N
N
x
2
H
L
H
x
3
N
H
N
x
4
L
L
L
x
5
N
H
H
x
6
N
H
H
x
7
L
L
L
x
8
L
H
N
x
9
N
N
H
x
10
H
L
N


## 4.2. Algorithm of Filling Missing Values in IISs of Continuous Data

Similar to the discussion of Section4.1, we investigate the corresponding issues of IISs of continuous data in this section.


### 4.2.1. Filling the Missing Values with Fuzzy Set Values

Similar to Algorithm1, we give Algorithm 2 to fill the missing value in IISs of continuous data.Example 4.
In this example, we discuss the Iris information system given by Table5 from UCI. Suppose that a1x5 and a2x7 in Table 5 are missing. We obtain Table 6. Next, we use the IIS given by Table 6 to illustrate Algorithm 2.
In Table6, a1x5=∗. Clearly, Va1∗=4.3,4.9,5.4,5.7,5.8,6.3,6.6. We take the thresholds λ1=0.2 and λ2=λ3=λ4=0.5.Step 1: Take4.3∈Va1∗. It is easy to compute that 4.3λ1a1=xi∈Ua1xi−4.3≤0.2=x1.Step 2: Sincea2x1−a2x5=0.5≤λ2=0.5, a3x1−a3x5=0.3≤λ3=0.5, and a4x1−a4x5=0.2≤λ4=0.5, it follows that aj∈Attajx5−ajx1≤λj=a2,a3,a4, and thus Dx5,x1=3/4. This implies that Dx5,4.3λ1a1=max3/4=0.75.Step 3:a1Fx54.3=0.75.
Similarly, we can compute thata1Fx54.9=0, a1Fx55.4=0.75, a1Fx55.7=0.75, a1Fx55.8=0.75, a1Fx56.3=0.25, and a1Fx56.6=0. Therefore, we fill the missing value a1x5 with the following fuzzy set:(27)a1Fx5=0.754.3+04.9+0.755.4+0.755.7+0.755.8+0.256.3+06.6.Table 5
Original dataset of Table6.
Objects
a
1
a
2
a
3
a
4
x
1
4.3
3
1.1
0.1
x
2
5.8
4
1.2
0.2
x
3
5.7
4.4
1.5
0.4
x
4
5.4
3.9
1.3
0.4
x
5
5.1
3.5
1.4
0.3
x
6
5.7
3.8
1.7
0.31
x
7
5.7
2.8
4.5
1.3
x
8
6.3
3.3
4.7
1.6
x
9
4.9
2.4
3.3
1
x
10
6.6
2.9
4.6
1.3Table 6
Missing dataset.
Objects
a
1
a
2
a
3
a
4
x
1
4.3
3
1.1
0.1
x
2
5.8
4
1.2
0.2
x
3
5.7
4.4
1.5
0.4
x
4
5.4
3.9
1.3
0.4
x
5
∗
3.5
1.4
0.3
x
6
5.7
3.8
1.7
0.31
x
7
5.7
∗
4.5
1.3
x
8
6.3
3.3
4.7
1.6
x
9
4.9
2.4
3.3
1
x
10
6.6
2.9
4.6
1.3Algorithm 2: Filling the missing values in IISs of continuous data with fuzzy set values.
LetU,Att,V be an IIS of continuous data. Assume that akxl=∗, where xl∈U and ak∈Att. Vak∗ denotes the set Vak−∗. We shall use a fuzzy set of Vak∗ to represent the missing value akxl, and we denote the fuzzy set by akFxl. Thus, ∀t∈Vak∗, and we need to compute the membership degree akFxlt. Next, we establish the steps of filling the missing value akxl as follows:
Step 1:∀t∈Vak∗, compute tλkak=xi∈Uakxi−t≤λk, where λk is a threshold on ak
Step 2: ComputeDxl,tλkak=maxDxl,xixi∈tλkak, where Dxl,xi=aj∈Attajxl−ajxi≤λj/Att.
Step 3: Assign a value toakFxlt, akFxlt=Dxl,tλkak,Dxl,tλkak≠0,tλkak/U,Dxl,tλkak=0.


### 4.2.2. Filling the Missing Values with Real Values

Based on the discussion of Section4.2.1, we can replace a missing value with a fuzzy set. Clearly, we can transform the fuzzy set into real value by means of the maximum membership degree law. Let U,Att,V be an IIS of continuous data. Assume that akxl=∗, where xl∈U and ak∈Att. By Algorithm 2, we obtain the fuzzy set akFxl. Thus, we can use the following real value to fill the missing value akxl:(28)akRxl=∑t∈smdtsmd,where smd=t∈Vak∗akFxlt=M and M=maxakFxltt∈Vak∗.Example 5.
From Example4, we know that(29)a1Fx5=0.754.3+04.9+0.755.4+0.755.7+0.755.8+0.256.3+06.6.
By equation (28), we compute that(30)M=0.75,smd=4.3,5.4,5.7,5.8.
Thus, we obtain thata1Rx5=4.3+5.4+5.7+5.8/4=5.3.Remark 4.
By Table5, we know that a1x5 should be 5.1. By Example 5, we fill the value a1Rx5=5.3 under the assumption that a1x5 and a2x7 are missing. The deviation of a1x5 and a1Rx5=5.3 is within 0.2. This indicates that the method of filling missing value is effective.


## 4.2.1. Filling the Missing Values with Fuzzy Set Values

Similar to Algorithm1, we give Algorithm 2 to fill the missing value in IISs of continuous data.Example 4.
In this example, we discuss the Iris information system given by Table5 from UCI. Suppose that a1x5 and a2x7 in Table 5 are missing. We obtain Table 6. Next, we use the IIS given by Table 6 to illustrate Algorithm 2.
In Table6, a1x5=∗. Clearly, Va1∗=4.3,4.9,5.4,5.7,5.8,6.3,6.6. We take the thresholds λ1=0.2 and λ2=λ3=λ4=0.5.Step 1: Take4.3∈Va1∗. It is easy to compute that 4.3λ1a1=xi∈Ua1xi−4.3≤0.2=x1.Step 2: Sincea2x1−a2x5=0.5≤λ2=0.5, a3x1−a3x5=0.3≤λ3=0.5, and a4x1−a4x5=0.2≤λ4=0.5, it follows that aj∈Attajx5−ajx1≤λj=a2,a3,a4, and thus Dx5,x1=3/4. This implies that Dx5,4.3λ1a1=max3/4=0.75.Step 3:a1Fx54.3=0.75.
Similarly, we can compute thata1Fx54.9=0, a1Fx55.4=0.75, a1Fx55.7=0.75, a1Fx55.8=0.75, a1Fx56.3=0.25, and a1Fx56.6=0. Therefore, we fill the missing value a1x5 with the following fuzzy set:(27)a1Fx5=0.754.3+04.9+0.755.4+0.755.7+0.755.8+0.256.3+06.6.Table 5
Original dataset of Table6.
Objects
a
1
a
2
a
3
a
4
x
1
4.3
3
1.1
0.1
x
2
5.8
4
1.2
0.2
x
3
5.7
4.4
1.5
0.4
x
4
5.4
3.9
1.3
0.4
x
5
5.1
3.5
1.4
0.3
x
6
5.7
3.8
1.7
0.31
x
7
5.7
2.8
4.5
1.3
x
8
6.3
3.3
4.7
1.6
x
9
4.9
2.4
3.3
1
x
10
6.6
2.9
4.6
1.3Table 6
Missing dataset.
Objects
a
1
a
2
a
3
a
4
x
1
4.3
3
1.1
0.1
x
2
5.8
4
1.2
0.2
x
3
5.7
4.4
1.5
0.4
x
4
5.4
3.9
1.3
0.4
x
5
∗
3.5
1.4
0.3
x
6
5.7
3.8
1.7
0.31
x
7
5.7
∗
4.5
1.3
x
8
6.3
3.3
4.7
1.6
x
9
4.9
2.4
3.3
1
x
10
6.6
2.9
4.6
1.3Algorithm 2: Filling the missing values in IISs of continuous data with fuzzy set values.
LetU,Att,V be an IIS of continuous data. Assume that akxl=∗, where xl∈U and ak∈Att. Vak∗ denotes the set Vak−∗. We shall use a fuzzy set of Vak∗ to represent the missing value akxl, and we denote the fuzzy set by akFxl. Thus, ∀t∈Vak∗, and we need to compute the membership degree akFxlt. Next, we establish the steps of filling the missing value akxl as follows:
Step 1:∀t∈Vak∗, compute tλkak=xi∈Uakxi−t≤λk, where λk is a threshold on ak
Step 2: ComputeDxl,tλkak=maxDxl,xixi∈tλkak, where Dxl,xi=aj∈Attajxl−ajxi≤λj/Att.
Step 3: Assign a value toakFxlt, akFxlt=Dxl,tλkak,Dxl,tλkak≠0,tλkak/U,Dxl,tλkak=0.


## 4.2.2. Filling the Missing Values with Real Values

Based on the discussion of Section4.2.1, we can replace a missing value with a fuzzy set. Clearly, we can transform the fuzzy set into real value by means of the maximum membership degree law. Let U,Att,V be an IIS of continuous data. Assume that akxl=∗, where xl∈U and ak∈Att. By Algorithm 2, we obtain the fuzzy set akFxl. Thus, we can use the following real value to fill the missing value akxl:(28)akRxl=∑t∈smdtsmd,where smd=t∈Vak∗akFxlt=M and M=maxakFxltt∈Vak∗.Example 5.
From Example4, we know that(29)a1Fx5=0.754.3+04.9+0.755.4+0.755.7+0.755.8+0.256.3+06.6.
By equation (28), we compute that(30)M=0.75,smd=4.3,5.4,5.7,5.8.
Thus, we obtain thata1Rx5=4.3+5.4+5.7+5.8/4=5.3.Remark 4.
By Table5, we know that a1x5 should be 5.1. By Example 5, we fill the value a1Rx5=5.3 under the assumption that a1x5 and a2x7 are missing. The deviation of a1x5 and a1Rx5=5.3 is within 0.2. This indicates that the method of filling missing value is effective.


## 5. Experiments and Effectiveness Analysis

In this section, we employ several experiments to show the effectiveness of the algorithms given by Section4. We compare the proposed methods with a representative algorithm. The summary information of experimental datasets is shown in Table 7. Adult dataset and Abalone dataset are taken from UCI (http://archive.ics.uci.edu/ml/datasets.php).Table 7
Detailed information of the datasets.
Index
Dataset
Data type
Objects
Attributes
1
Adult dataset
Nominal, numeric
48842
9
2
Abalone dataset
Numeric
4177
8


### 5.1. Effectiveness Analysis of the Algorithm of Filling Missing Values in IISs of Discrete Data

In this part, we will conduct two groups of experiments. They are used to compare the effectiveness of methods of filling missing values from different points of view. Frequency Estimator-based filling method (Algorithm FE) [30] is a common method of filling missing data. In this section, a comparison of the proposed methods with Algorithm FE is given.In Section4.1, we give the method of filling the missing values with fuzzy set values. Furthermore, we obtain the method of filling the missing values with set values. By combining Section 4.1.1 and Section 4.1.2, we design Algorithm FMvSV to fill the missing values with set values (Algorithm 3).Next, we provide a comparative study of the effectiveness for Algorithms FMvSV and FE. We first give a quantitative index of the effectiveness for filling missing values as follows.Algorithm 3: Algorithm FMvSV: filling the missing values with set values.
Input: An IIS U,Att,V of discrete data, where U=x1,x2,…,xn and Att=a1,a2,…,am
The missing values:ak1xw1,ak2xw2,…,akqxwq
Output: The filling set values: ak1Sxw1,ak2Sxw2,…,akqSxwq
(1)
for
i = 1 toqdo
(2)
for every t in Vaki∗ do
(3)
Computetaki=x∈Uakix=t
(4)
for every x in taki do
(5)
ComputeDxwi,x=a∈Attaxwi=ax/Att
(6)
end
(7)
ComputeDxwi,taki=maxDxwi,xx∈tak
(8)
if Dxwi,taki≠0 then
(9)
akiFxwit=Dxwi,taki
(10)
else
(11)
akiFxwit=taki/U
(12)
end if
(13)
end
(14)
M=maxakiFxwitt∈Vaki∗
(15)
akiSxwi=t∈Vaki∗akiFxwit=M
(16)
endAlgorithm 4: Algorithm FMvRV: filling the missing values with real values.
Input: An IIS U,Att of continuous data, where U=x1,x2,…,xn and Att=a1,a2,…,am.
The missing values:ak1xw1,ak2xw2,…,akqxwq. The threshold: λ1,λ2,…,λm.
Output: The filling real values: ak1Rxw1,ak2Rxw2,…,akqRxwq.
(1)
for
i = 1 toqdo
(2)
for every t in Vaki∗ do
(3)
Computetλkiaki=x∈Uakix−t≤λki
(4)
for every x in tλkiaki do
(5)
ComputeDxwi,x=al∈Attalxwi−alx≤λl/Att
(6)
end
(7)
ComputeDxwi,tλkiaki=maxDxwi,xx∈tλkiaki
(8)
ifDxwi,tλkiaki≠0 then
(9)
akiFxwit=Dxwi,tλkiaki
(10)
else
(11)
akiFxwit=tλkiaki/U
(12)
end if
(13)
end
(14)
M=maxakiFxwitt∈Vaki∗; smd=t∈Vaki∗akiFxwit=M
(15)
akiRxwi=∑t∈smdt/smd
(16)
endDefinition 6.
Given a complete information systemU,Att of discrete data, suppose that the values ak1xw1,ak2xw2,…,akqxwq are missing, and the filling set values are denoted as ak1Sxw1,ak2Sxw2,…,akqSxwq, respectively. Then, the correct rate of filling values is defined by(31)CR=∑i=1qpiq,where q is the number of the missing values, and(32)pi=1−akiSxwi−1Vaki∗,akixwi∈akiSxwi;0,Others.Example 6.
In Table4, a1x5=N, a1x9=N and a2x7=L. In Example 3, suppose that a1x5, a1x9, and a2x7 in Table 4 are missing. Then, we obtain that a1Sx5=N, a1Sx9=L,H,N and a2Sx7=L. Thus, by Definition 6, we can compute that(33)p1=1−a1sx5−1Va1∗=1−1−13=1,p2=1−a1sx9−1Va1∗=1−3−13=13,p3=1−a2sx7−1Va2∗=1−1−13=1.
Therefore, the correct rate of filling values isCR=p1+p2+p3/3=0.778.
In this section, we use some subsets of Adult dataset (see Table7) to experiment. We need to experiment with the discrete value. We randomly select some subsets of discrete values in Adult dataset. Table 8 gives three subsets of Adult dataset.Table 8
The subsets of Adult dataset used in Experiments1 and 2.
The name of dataset
The type of datasets
The type of attribute values
The number of objects
The number of attributes
AD200
Complete
Discrete
200
9
AD400
Complete
Discrete
400
9
AD800
Complete
Discrete
800
9Experiment 1.
The effects of experiment times on correct rates of filling values.
In this experiment, we mainly compare the efficiency of Algorithms FMvSV and FE by the dataset AD200 in Table8. The steps are as follows:(i)
2.5% attribute values are randomly selected from AD200 and supposed that they are missing(ii)
By means of Algorithms FMvSV and FE, we can fill these missing values, and we can obtain the correct rate of every algorithm
The steps (i) and (ii) are repeated ten times, and the corresponding results are summarized in Table9. Similarly, we also consider the cases of 5%,7.5%,10%,12.5%,15%,17.5%,20%, 22.5%, 25%,27.5%, and 30% missing values in AD200. The results are shown in Figures 1 and 2.
Figures1 and 2 show the following facts:(i)
The correct rate of Algorithm FMvSV is10%−20% higher than that of Algorithm FE.(ii)
The number of missing values is given, but the missing values in AD200 are not necessarily the same in each experiment. The correct rates of Algorithm FMvSV have little change in each experiment when the number of missing values in AD200 is a fixed value. However, in the similar case, the correct rates of Algorithm FE fluctuate obviously in each experiment. This indicates that Algorithm FMvSV does well in stability.
In Table9, the mean value of ten correct rates related to Algorithm FMvSV can be considered as the correct rate of Algorithm FMvSV for 2.5% missing values. The correct rate of Algorithm FE for 2.5% missing values can be obtained similarly. Furthermore, for 5%,7.5%,10%,12.5%,15%,17.5%,20%, 22.5%, 25%,27.5%, and 30% missing values in AD200, we also compute the correct rates of Algorithms FMvSV and FE. The results are shown in Table 10 and Figure 3.
Table10 and Figure 3 show that the correct rates of Algorithm FMvSV monotone decrease with the increase of missing values. However, the monotonicity of the correct rates of Algorithm FE is not obvious. In addition, Table 10 and Figure 3 also indicate that the effect of Algorithm FMvSV is better than that of Algorithm FE. Furthermore, when the missing values are increased to 30%, the correct rate of Algorithm FMvSV still achieves 64%.Table 9
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with2.5% missing values.
Times
1
2
3
4
5
6
7
8
9
10
FMvSV
0.87
0.777
0.807
0.762
0.799
0.788
0.815
0.804
0.776
0.789
FE
0.687
0.6
0.6
0.556
0.644
0.733
0.644
0.622
0.6
0.644Figure 1
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with2.5%−15% missing values. (a) 2.5% missing values. (b) 5% missing values. (c) 7.5% missing values. (d) 10% missing values. (e) 12.5% missing values. (f) 15% missing values.
(a)
(b)
(c)
(d)
(e)
(f)Figure 2
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with17.5%−30% missing values. (a) 17.5% missing values. (b) 20% missing values. (c) 22.5% missing values. (d) 25% missing values. (e) 27.5% missing values. (f) 30% missing values.
(a)
(b)
(c)
(d)
(e)
(f)Table 10
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with2.5%−30% missing values.
Missing values (%)
2.5
5
7.5
10
12.5
15
17.5
20
22.5
25
27.5
30
FMvSV
0.80
0.78
0.74
0.73
0.72
0.71
0.70
0.69
0.68
0.68
0.66
0.64
FE
0.63
0.59
0.58
0.59
0.58
0.57
0.58
0.58
0.57
0.58
0.57
0.55Figure 3
Comparison of correct rates of Algorithm FMvSV and Algorithm FE.Experiment 2.
The effects of data size on correct rates of filling values.
In this experiment, we use AD200, AD400, and AD800 to discuss the effects of data size on correct rates of Algorithms FMvSV and FE. For5%−60% missing values, similar to the calculating method of Table 10, we can obtain the correct rate of Algorithm FMvSV (or FE) in this experiment. The results are shown in Figure 4.
Figure4 reflects the following facts:(i)
When the data size increases under the same missing rate, the correct rate of Algorithm FMvSV remains basically the same and is higher than that of Algorithm FE. Therefore, for Algorithm FMvSV, we can divide a dataset into several small datasets, and then fill missing values to improve efficiency of it.(ii)
It is easy to see that as the data size increases, the difference between the correct rates of Algorithms FMvSV and FE becomes larger. This illustrates that as the data size increases, the advantage of Algorithm FMvSV is obvious, that is, Algorithm FMvSV has an advantage in processing big dataset and dynamically increasing dataset.Figure 4
Comparison of the correct rates of Algorithms FMvSV and FE in terms of (a) AD200, (b) AD400, and (c) AD800.
(a)
(b)
(c)


### 5.2. Effectiveness Analysis of the Algorithm of Filling Missing Values in IISs of Continuous Data

In this section, we also conduct two groups of experiments. They are still used to compare the effectiveness of algorithms of filling missing values from different points of view. Mean-based filling method (Algorithm MEAN) [31] is a common method of filling missing data for an IIS of continuous data. Next, a comparison of the proposed methods with Algorithm MEAN is provided.In Section4.2, we obtain the method of filling the missing values with real values. By combining Section 4.2.1 and Section 4.2.2, we design Algorithm FMvRV to fill the missing values with real values (Algorithm 4).Next, we provide a comparative study of the effectiveness for Algorithms FMvRV and MEAN. We first give a quantitative index of the effectiveness for filling missing values as follows.Definition 7.
Given a complete information systemU,Att of continuous data, suppose that the values ak1xw1,ak2xw2,…,akqxwq are missing, and the filling set values are denoted as ak1Rxw1,ak2Rxw2,…,akqRxwq, respectively. Then, the correct rate of filling values is defined by(34)CRC=ki,wiakixwi−akiRxwi≤λki,i=1,2,…,qq,where q is the number of the missing values, and λ1, λ2, …, and λq are thresholds corresponding to ak1, ak2, …, and akq.Example 7.
From Example5, we know that the thresholds are λ1=0.2,λ2=λ3=λ4=0.5, and a1Rx5=5.3. Similarly, we can compute that a2Rx7=3.15. It is clear that a1x5−a1Rx5=5.1−5.3=0.2≤λ1=0.2 and a2x7−a2Rx7=2.8−3.15=0.35≤λ2=0.5. Therefore, we can calculate the correct rate: CRC=1,5,2,7/2=2/2=1.
In this section, we use some subsets of Abalone dataset (see Table8) to experiment. Table 11 gives three subsets of Abalone dataset.Table 11
The subsets of Abalone dataset used in Experiments3 and 4.
The name of dataset
The type of dataset
The type of attribute value
The number of object
The number of attribute
AB200
Complete
Continuous
200
8
AB400
Complete
Continuous
400
8
AB800
Complete
Continuous
800
8Experiment 3.
The effects of experiment times on correct rates of filling values about continuous data.
In this experiment, we mainly compare the efficiency of Algorithms FMvRV and MEAN by AB200 in Table11. The steps are as follows:(i)
5% attribute values are randomly selected from AB200 and supposed that they are missing(ii)
By means of Algorithms FMvRV and MEAN, we can fill these missing values, and we can obtain the correct rate of every algorithm
The steps (i) and (ii) are repeated ten times, and the corresponding results are summarized in Table12. Similarly, we also consider the cases of 10%, 15%, 20%, 25%, and 30% missing values in AB200. The results are shown in Figure 5.
Figure5 shows that Algorithm FMvRV is more stable than Algorithm MEAN. Furthermore, the correct rate of Algorithm FMvRV is better than that of Algorithm MEAN. This indicates that Algorithm FMvRV can carry out more accurate forecast of missing values. It is meaningful to explore the correct classification of incomplete datasets.
In Table12, the mean value of ten correct rates related to Algorithm FMvRV can be viewed as the correct rate of Algorithm FMvRV for 5% missing values. The correct rate of Algorithm MEAN for 5% missing values can be computed similarly. Furthermore, for 10%, 15%, 20%, 25%, and 30% missing values in AB200, we also compute the correct rates of Algorithms FMvRV and MEAN. The results are shown in Figure 6.
Figure6 shows that the correct rates of Algorithm FMvRV monotone almost decrease with the increase of missing values. However, the monotonicity of the correct rates of Algorithm MEAN is not obvious. In addition, Figure 6 also indicates that the effect of Algorithm FMvRV is better than that of Algorithm MEAN. Furthermore, when the missing values are increased to 30%, the correct rate of Algorithm FMvRV is more than 85%. However, now, the correct rate of Algorithm MEAN is less than 60%. This indicates that Algorithm FMvRV is more conducive to predicting the missing values.Table 12
Comparison of the correct rates of Algorithms FMvRV and MEAN in terms of AB200 with5% missing values.
Times
1
2
3
4
5
6
7
8
9
10
FMvRV
0.925
0.838
0.888
0.925
0.95
0.938
0.925
0.9
0.913
0.925
MEAN
0.575
0.463
0.588
0.613
0.625
0.55
0.563
0.65
0.588
0.6Figure 5
Comparison of the correct rates of Algorithms FMvRV and MEAN in terms of AB200 with5%−30% missing values. (a) 5% missing values. (b) 10% missing values. (c) 15% missing values. (d) 20% missing values. (e) 25% missing values. (f) 30% missing values.
(a)
(b)
(c)
(d)
(e)
(f)Figure 6
Comparison of correct rates of Algorithm FMvRV and Algorithm MEAN.Experiment 4.
The effects of data size on correct rates of filling values about continuous data.
In this experiment, we use AB200, AB400, and AB800 to discuss the effects of data size on correct rates of Algorithms FMvRV and MEAN. For10%−30% missing values, similar to the calculating method of Table 12, we can obtain the correct rate of Algorithm FMvRV (or MEAN) in this experiment. The results are shown in Figure 7.
Figure7 reflects the following facts:(i)
When the data size increases, the correct rate of Algorithm FMvRV is higher than that of Algorithm MEAN.(ii)
When the missing values are less than30%, the correct rates of Algorithm FMvRV are almost unchanged and close to 90%. Now, the data size has little effect on the correct rates of Algorithm FMvRV. This illustrates that Algorithm FMvRV has obvious advantages in processing big dataset when the missing values are less than 30%.Figure 7
Comparison of the correct rates of Algorithms FMvRV and MEAN in terms of (a) AB200, (b) AB400, and (c) AB800.
(a)
(b)
(c)


## 5.1. Effectiveness Analysis of the Algorithm of Filling Missing Values in IISs of Discrete Data

In this part, we will conduct two groups of experiments. They are used to compare the effectiveness of methods of filling missing values from different points of view. Frequency Estimator-based filling method (Algorithm FE) [30] is a common method of filling missing data. In this section, a comparison of the proposed methods with Algorithm FE is given.In Section4.1, we give the method of filling the missing values with fuzzy set values. Furthermore, we obtain the method of filling the missing values with set values. By combining Section 4.1.1 and Section 4.1.2, we design Algorithm FMvSV to fill the missing values with set values (Algorithm 3).Next, we provide a comparative study of the effectiveness for Algorithms FMvSV and FE. We first give a quantitative index of the effectiveness for filling missing values as follows.Algorithm 3: Algorithm FMvSV: filling the missing values with set values.
Input: An IIS U,Att,V of discrete data, where U=x1,x2,…,xn and Att=a1,a2,…,am
The missing values:ak1xw1,ak2xw2,…,akqxwq
Output: The filling set values: ak1Sxw1,ak2Sxw2,…,akqSxwq
(1)
for
i = 1 toqdo
(2)
for every t in Vaki∗ do
(3)
Computetaki=x∈Uakix=t
(4)
for every x in taki do
(5)
ComputeDxwi,x=a∈Attaxwi=ax/Att
(6)
end
(7)
ComputeDxwi,taki=maxDxwi,xx∈tak
(8)
if Dxwi,taki≠0 then
(9)
akiFxwit=Dxwi,taki
(10)
else
(11)
akiFxwit=taki/U
(12)
end if
(13)
end
(14)
M=maxakiFxwitt∈Vaki∗
(15)
akiSxwi=t∈Vaki∗akiFxwit=M
(16)
endAlgorithm 4: Algorithm FMvRV: filling the missing values with real values.
Input: An IIS U,Att of continuous data, where U=x1,x2,…,xn and Att=a1,a2,…,am.
The missing values:ak1xw1,ak2xw2,…,akqxwq. The threshold: λ1,λ2,…,λm.
Output: The filling real values: ak1Rxw1,ak2Rxw2,…,akqRxwq.
(1)
for
i = 1 toqdo
(2)
for every t in Vaki∗ do
(3)
Computetλkiaki=x∈Uakix−t≤λki
(4)
for every x in tλkiaki do
(5)
ComputeDxwi,x=al∈Attalxwi−alx≤λl/Att
(6)
end
(7)
ComputeDxwi,tλkiaki=maxDxwi,xx∈tλkiaki
(8)
ifDxwi,tλkiaki≠0 then
(9)
akiFxwit=Dxwi,tλkiaki
(10)
else
(11)
akiFxwit=tλkiaki/U
(12)
end if
(13)
end
(14)
M=maxakiFxwitt∈Vaki∗; smd=t∈Vaki∗akiFxwit=M
(15)
akiRxwi=∑t∈smdt/smd
(16)
endDefinition 6.
Given a complete information systemU,Att of discrete data, suppose that the values ak1xw1,ak2xw2,…,akqxwq are missing, and the filling set values are denoted as ak1Sxw1,ak2Sxw2,…,akqSxwq, respectively. Then, the correct rate of filling values is defined by(31)CR=∑i=1qpiq,where q is the number of the missing values, and(32)pi=1−akiSxwi−1Vaki∗,akixwi∈akiSxwi;0,Others.Example 6.
In Table4, a1x5=N, a1x9=N and a2x7=L. In Example 3, suppose that a1x5, a1x9, and a2x7 in Table 4 are missing. Then, we obtain that a1Sx5=N, a1Sx9=L,H,N and a2Sx7=L. Thus, by Definition 6, we can compute that(33)p1=1−a1sx5−1Va1∗=1−1−13=1,p2=1−a1sx9−1Va1∗=1−3−13=13,p3=1−a2sx7−1Va2∗=1−1−13=1.
Therefore, the correct rate of filling values isCR=p1+p2+p3/3=0.778.
In this section, we use some subsets of Adult dataset (see Table7) to experiment. We need to experiment with the discrete value. We randomly select some subsets of discrete values in Adult dataset. Table 8 gives three subsets of Adult dataset.Table 8
The subsets of Adult dataset used in Experiments1 and 2.
The name of dataset
The type of datasets
The type of attribute values
The number of objects
The number of attributes
AD200
Complete
Discrete
200
9
AD400
Complete
Discrete
400
9
AD800
Complete
Discrete
800
9Experiment 1.
The effects of experiment times on correct rates of filling values.
In this experiment, we mainly compare the efficiency of Algorithms FMvSV and FE by the dataset AD200 in Table8. The steps are as follows:(i)
2.5% attribute values are randomly selected from AD200 and supposed that they are missing(ii)
By means of Algorithms FMvSV and FE, we can fill these missing values, and we can obtain the correct rate of every algorithm
The steps (i) and (ii) are repeated ten times, and the corresponding results are summarized in Table9. Similarly, we also consider the cases of 5%,7.5%,10%,12.5%,15%,17.5%,20%, 22.5%, 25%,27.5%, and 30% missing values in AD200. The results are shown in Figures 1 and 2.
Figures1 and 2 show the following facts:(i)
The correct rate of Algorithm FMvSV is10%−20% higher than that of Algorithm FE.(ii)
The number of missing values is given, but the missing values in AD200 are not necessarily the same in each experiment. The correct rates of Algorithm FMvSV have little change in each experiment when the number of missing values in AD200 is a fixed value. However, in the similar case, the correct rates of Algorithm FE fluctuate obviously in each experiment. This indicates that Algorithm FMvSV does well in stability.
In Table9, the mean value of ten correct rates related to Algorithm FMvSV can be considered as the correct rate of Algorithm FMvSV for 2.5% missing values. The correct rate of Algorithm FE for 2.5% missing values can be obtained similarly. Furthermore, for 5%,7.5%,10%,12.5%,15%,17.5%,20%, 22.5%, 25%,27.5%, and 30% missing values in AD200, we also compute the correct rates of Algorithms FMvSV and FE. The results are shown in Table 10 and Figure 3.
Table10 and Figure 3 show that the correct rates of Algorithm FMvSV monotone decrease with the increase of missing values. However, the monotonicity of the correct rates of Algorithm FE is not obvious. In addition, Table 10 and Figure 3 also indicate that the effect of Algorithm FMvSV is better than that of Algorithm FE. Furthermore, when the missing values are increased to 30%, the correct rate of Algorithm FMvSV still achieves 64%.Table 9
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with2.5% missing values.
Times
1
2
3
4
5
6
7
8
9
10
FMvSV
0.87
0.777
0.807
0.762
0.799
0.788
0.815
0.804
0.776
0.789
FE
0.687
0.6
0.6
0.556
0.644
0.733
0.644
0.622
0.6
0.644Figure 1
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with2.5%−15% missing values. (a) 2.5% missing values. (b) 5% missing values. (c) 7.5% missing values. (d) 10% missing values. (e) 12.5% missing values. (f) 15% missing values.
(a)
(b)
(c)
(d)
(e)
(f)Figure 2
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with17.5%−30% missing values. (a) 17.5% missing values. (b) 20% missing values. (c) 22.5% missing values. (d) 25% missing values. (e) 27.5% missing values. (f) 30% missing values.
(a)
(b)
(c)
(d)
(e)
(f)Table 10
Comparison of the correct rates of Algorithms FMvSV and FE in terms of AD200 with2.5%−30% missing values.
Missing values (%)
2.5
5
7.5
10
12.5
15
17.5
20
22.5
25
27.5
30
FMvSV
0.80
0.78
0.74
0.73
0.72
0.71
0.70
0.69
0.68
0.68
0.66
0.64
FE
0.63
0.59
0.58
0.59
0.58
0.57
0.58
0.58
0.57
0.58
0.57
0.55Figure 3
Comparison of correct rates of Algorithm FMvSV and Algorithm FE.Experiment 2.
The effects of data size on correct rates of filling values.
In this experiment, we use AD200, AD400, and AD800 to discuss the effects of data size on correct rates of Algorithms FMvSV and FE. For5%−60% missing values, similar to the calculating method of Table 10, we can obtain the correct rate of Algorithm FMvSV (or FE) in this experiment. The results are shown in Figure 4.
Figure4 reflects the following facts:(i)
When the data size increases under the same missing rate, the correct rate of Algorithm FMvSV remains basically the same and is higher than that of Algorithm FE. Therefore, for Algorithm FMvSV, we can divide a dataset into several small datasets, and then fill missing values to improve efficiency of it.(ii)
It is easy to see that as the data size increases, the difference between the correct rates of Algorithms FMvSV and FE becomes larger. This illustrates that as the data size increases, the advantage of Algorithm FMvSV is obvious, that is, Algorithm FMvSV has an advantage in processing big dataset and dynamically increasing dataset.Figure 4
Comparison of the correct rates of Algorithms FMvSV and FE in terms of (a) AD200, (b) AD400, and (c) AD800.
(a)
(b)
(c)


## 5.2. Effectiveness Analysis of the Algorithm of Filling Missing Values in IISs of Continuous Data

In this section, we also conduct two groups of experiments. They are still used to compare the effectiveness of algorithms of filling missing values from different points of view. Mean-based filling method (Algorithm MEAN) [31] is a common method of filling missing data for an IIS of continuous data. Next, a comparison of the proposed methods with Algorithm MEAN is provided.In Section4.2, we obtain the method of filling the missing values with real values. By combining Section 4.2.1 and Section 4.2.2, we design Algorithm FMvRV to fill the missing values with real values (Algorithm 4).Next, we provide a comparative study of the effectiveness for Algorithms FMvRV and MEAN. We first give a quantitative index of the effectiveness for filling missing values as follows.Definition 7.
Given a complete information systemU,Att of continuous data, suppose that the values ak1xw1,ak2xw2,…,akqxwq are missing, and the filling set values are denoted as ak1Rxw1,ak2Rxw2,…,akqRxwq, respectively. Then, the correct rate of filling values is defined by(34)CRC=ki,wiakixwi−akiRxwi≤λki,i=1,2,…,qq,where q is the number of the missing values, and λ1, λ2, …, and λq are thresholds corresponding to ak1, ak2, …, and akq.Example 7.
From Example5, we know that the thresholds are λ1=0.2,λ2=λ3=λ4=0.5, and a1Rx5=5.3. Similarly, we can compute that a2Rx7=3.15. It is clear that a1x5−a1Rx5=5.1−5.3=0.2≤λ1=0.2 and a2x7−a2Rx7=2.8−3.15=0.35≤λ2=0.5. Therefore, we can calculate the correct rate: CRC=1,5,2,7/2=2/2=1.
In this section, we use some subsets of Abalone dataset (see Table8) to experiment. Table 11 gives three subsets of Abalone dataset.Table 11
The subsets of Abalone dataset used in Experiments3 and 4.
The name of dataset
The type of dataset
The type of attribute value
The number of object
The number of attribute
AB200
Complete
Continuous
200
8
AB400
Complete
Continuous
400
8
AB800
Complete
Continuous
800
8Experiment 3.
The effects of experiment times on correct rates of filling values about continuous data.
In this experiment, we mainly compare the efficiency of Algorithms FMvRV and MEAN by AB200 in Table11. The steps are as follows:(i)
5% attribute values are randomly selected from AB200 and supposed that they are missing(ii)
By means of Algorithms FMvRV and MEAN, we can fill these missing values, and we can obtain the correct rate of every algorithm
The steps (i) and (ii) are repeated ten times, and the corresponding results are summarized in Table12. Similarly, we also consider the cases of 10%, 15%, 20%, 25%, and 30% missing values in AB200. The results are shown in Figure 5.
Figure5 shows that Algorithm FMvRV is more stable than Algorithm MEAN. Furthermore, the correct rate of Algorithm FMvRV is better than that of Algorithm MEAN. This indicates that Algorithm FMvRV can carry out more accurate forecast of missing values. It is meaningful to explore the correct classification of incomplete datasets.
In Table12, the mean value of ten correct rates related to Algorithm FMvRV can be viewed as the correct rate of Algorithm FMvRV for 5% missing values. The correct rate of Algorithm MEAN for 5% missing values can be computed similarly. Furthermore, for 10%, 15%, 20%, 25%, and 30% missing values in AB200, we also compute the correct rates of Algorithms FMvRV and MEAN. The results are shown in Figure 6.
Figure6 shows that the correct rates of Algorithm FMvRV monotone almost decrease with the increase of missing values. However, the monotonicity of the correct rates of Algorithm MEAN is not obvious. In addition, Figure 6 also indicates that the effect of Algorithm FMvRV is better than that of Algorithm MEAN. Furthermore, when the missing values are increased to 30%, the correct rate of Algorithm FMvRV is more than 85%. However, now, the correct rate of Algorithm MEAN is less than 60%. This indicates that Algorithm FMvRV is more conducive to predicting the missing values.Table 12
Comparison of the correct rates of Algorithms FMvRV and MEAN in terms of AB200 with5% missing values.
Times
1
2
3
4
5
6
7
8
9
10
FMvRV
0.925
0.838
0.888
0.925
0.95
0.938
0.925
0.9
0.913
0.925
MEAN
0.575
0.463
0.588
0.613
0.625
0.55
0.563
0.65
0.588
0.6Figure 5
Comparison of the correct rates of Algorithms FMvRV and MEAN in terms of AB200 with5%−30% missing values. (a) 5% missing values. (b) 10% missing values. (c) 15% missing values. (d) 20% missing values. (e) 25% missing values. (f) 30% missing values.
(a)
(b)
(c)
(d)
(e)
(f)Figure 6
Comparison of correct rates of Algorithm FMvRV and Algorithm MEAN.Experiment 4.
The effects of data size on correct rates of filling values about continuous data.
In this experiment, we use AB200, AB400, and AB800 to discuss the effects of data size on correct rates of Algorithms FMvRV and MEAN. For10%−30% missing values, similar to the calculating method of Table 12, we can obtain the correct rate of Algorithm FMvRV (or MEAN) in this experiment. The results are shown in Figure 7.
Figure7 reflects the following facts:(i)
When the data size increases, the correct rate of Algorithm FMvRV is higher than that of Algorithm MEAN.(ii)
When the missing values are less than30%, the correct rates of Algorithm FMvRV are almost unchanged and close to 90%. Now, the data size has little effect on the correct rates of Algorithm FMvRV. This illustrates that Algorithm FMvRV has obvious advantages in processing big dataset when the missing values are less than 30%.Figure 7
Comparison of the correct rates of Algorithms FMvRV and MEAN in terms of (a) AB200, (b) AB400, and (c) AB800.
(a)
(b)
(c)


## 6. Application of the Algorithms of Filling Missing Values in Investigating IISs

When we apply the rough set approach to investigate an IIS, a key step is to induce a binary relation from the IIS. For an IIS, we can provide three ways to obtain a binary relation from the IIS. LetU,Att,V be an IIS and B⊆Att. Then, the three ways are as follows:(1)
By equation (2), we can obtain the binary relation TB.(2)
By Algorithm1, we can fill the missing values in IISs with fuzzy set values. Then we can also view the other values of attributes as fuzzy set values, for example, in Table 3 of Example 2, a1x1=L, we can see a1x1 as the fuzzy set value a1x1=1/L+0/H+0/N. Based on this discussion, we can transform an IIS into a FSvIS. Thus, according to equation (8), we can obtain the binary relation RBSλ.(3)
In an IIS of discrete data, if the valueax of x under attribute a is not missing, we can view ax as a set value ax. Based on this consideration, we can use Algorithm FMvSV to transform an IIS into a set-valued information system. Then, we can obtain the following binary relation [32]:(35)TBsv=x,y∈U2ax∩ay≠∅,∀a∈B.In this section, through a comparative research on these binary relations induced from the same IIS, we further show that our algorithms are meaningful for the studies of IISs. We choose three datasets, i.e., Mammographic dataset, Abalone dataset, and Car dataset, to carry out the comparative research. The summary information of Mammographic dataset and Abalone dataset is shown in Table13. The Car dataset is shown in Table 14 [33]. Mammographic dataset and Abalone dataset are taken from UCI (http://archive.ics.uci.edu/ml/datasets.php).Table 13
Detailed information of the datasets.
Index
Dataset
The type of datasets
The type of attribute values
The number of objects
The number of attributes
1
Mammographic
Incomplete
Discrete
961
5
2
Breast cancer
Incomplete
Discrete
286
10Table 14
The incomplete information system about car dataset.
Price
Mileage
Size
Max-speed
x
1
High
Low
Full
Low
x
2
Low
∗
Full
Low
x
3
∗
∗
Compact
Low
x
4
High
∗
Full
High
x
5
∗
∗
Full
High
x
6
Low
High
Full
∗Firstly, we introduce a new measure to evaluate the similarity degree between binary relations.Definition 8.
LetR1 and R2 be binary relations on a nonempty set U. The similarity degree of R1 and R2 is defined as(36)SDR1,R2=R1∩R2R1∪R2.Example 8.
For the car dataset given by Table14, we can obtain the binary relations TB, TBsv, and RBSNλ as follows:(37)TBx1=x1,TBx2=x2,x6,TBx3=x3,TBx4=x4,x5,TBx5=x4,x5,x6,TBx6=x2,x5,x6;TBsvx1=x1,TBsvx2=x2,x6,TBsvx3=x3,TBsvx4=x4,x5,TBsvx5=x4,x5,TBsvx6=x2,x6;RBSNλx1=x1,RBSNλx2=x2,RBSNλx3=x3,RBSNλx4=x4,RBSNλx5=x5,RBSNλx6=x6;where we take λ=0.6. Similarly, for every dataset given by Table 13, we can also compute the corresponding binary relations TB, TBsv, and RBSNλ, where we choose λ=0.6. Then, by Definition 8, we calculate the similarity degrees between TB, TBsv, and RBSNλ. The result is shown in Table 15.
Table15 reflects the following facts.
We know that the binary relation induced by a dataset can be considered as the classification result of objects, where the elements in a successor neighbourhood with respect to the binary relation are a class. In this example, for Breast cancer dataset, the similarity degrees between relations are almost close to 1. This means that missing data have less impact on the classification of Breast cancer datasets. Thus, we may ignore these missing values in addressing this dataset. In contrast, the relations induced by Car dataset have low similarity degrees. This shows that missing values in Car dataset play an important role in the classification of this dataset. A natural question is which relation is better to investigate Car dataset. In Table15, we can see that the similarity degree between TBsv and TB is higher than that between TB and RBSNλ. Furthermore, the similarity degree between TBsv and RBSNλ is higher than that between TB and RBSNλ. This indicates that TBsv is a good choice to be used to investigate Car dataset. Note that TBsv is determined by using Algorithm FMvSV. This illustrates that Algorithm FMvSV is important for the studies of IISs.
At the end of this section, we apply the uncertainty measure to estimate the importance of the proposed algorithm. In Example8, we list three binary relations TB, TBsv, and RBSNλ with respect to Car dataset. By Definition 3, we can compute their entropies, which are shown in Table 16.
We know that entropy can measure the granularity of a binary. Proposition1 shows that the finer the binary relation is, the higher the entropy of it is. Conversely, if the entropy of the binary relation is high, then the binary relation should be fine. Thus, Table 16 indicates that TBsv and RBSNλ are finer than TB. That is to say, TBsv and RBSNλ can provide more information for the studies of IISs. According to the above discussion, we know that TBsv and RBSNλ are obtained in terms of the proposed algorithms. This illustrates that the proposed algorithms are useful for investigating IISs.
Finally, a similar discussion can also be made about continuous dataset. We omit it here.Table 15
Similarity degrees between binary relationsTB, TBsv, and RBSNλ.
Dataset
SD
T
B
,
R
B
S
N
λ
SD
T
B
,
T
B
s
v
SD
T
B
s
v
,
R
B
S
N
λ
Car
0.5
0.83
0.6
Mammographic
0.709
0.998
0.71
Breast cancer
0.933
1
0.933Table 16
The entropies ofTB, TBsv, and RBSNλ.
Dataset
H
T
B
H
T
B
s
v
H
R
B
S
N
λ
Car
1.723
1.918
2.585


## 7. Conclusion

This paper established the FSvIS, which is an extension of the PSvIS. By means of the FSvIS, we constructed some algorithms to fill missing values in IISs. We carried out several experiments to analyze the effectiveness of these algorithms. The experiment results indicated that these algorithms are useful to investigate the IISs. There are still many interesting issues worth studying. First, we will further study the relationship between FSvISs and the existing information systems and study the application of FSvISs. Second, we can apply uncertainty measures for fuzzy relations, which are established by [34], to investigate the fuzzy set-valued information system which is defined by this paper. Finally, we will conduct a more comprehensive analysis of the impact of missing values on IISs.



---

*Source: 3213808-2019-12-10.xml*