# Approximate Accuracy Approaches to Attribute Reduction for Information Systems

Authors: Deshan Liu; Dapeng Wang; Deqin Yan; Yu Sang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

The key problem for attribute reduction to information systems is how to evaluate the importance of an attribute. The algorithms are challenged by the variety of data forms in information system. Based on rough sets theory we present a new approach to attribute reduction for incomplete information systems and fuzzy valued information systems. In order to evaluate the importance of an attribute effectively, a novel algorithm with rigorous theorem is proposed. Experiments show the effect of proposed algorithm.


---

## Body

## 1. Introduction

There are various kinds of data in information systems, such as real value attribute, symbol attribute, and fuzzy sets attribute. The variety of data forms in information system gives a challenge to attribute algorithms. How to evaluate the importance of an attribute is a key problem for attribute reduction, and this also is hot point of study for researchers [1–6]. In [7] fuzzy discernibility matrix was studied for depicting the relationship for attributes in information system. Chen et al. [2] argued that the heuristic algorithm in [7] usually cannot find a proper reduct but an overcut-reduct or subreduct due to their stop criteria; based on the minimal elements in discernibility matrix, they proposed an attribute reduction algorithm with fuzzy rough sets. In [8], fuzzy rough sets attribute reduction was approached by a new construction of discernibility matrix. Rough set provides an important tool for data mining and knowledge discovery, and its application results attract more and more attention [1, 9–15]. Attribute reduction for information system by using discernibility matrix is an important application of rough set theorem. The concept and structure of the traditional discernibility matrix are based on attribute and whose attribute values are symbol [3, 10], which are also research hotspots in rough set’s theorem and application field. However, it is difficult to apply the traditional discernibility matrix in incomplete information system, the real value attribute information system, and fuzzy information systems. Although extended rough set model and continuous attributes real value segmentation method are proposed [2, 13, 16, 17], there are also many problems related to traditional discernibility matrix. In particular, the capacity of reduction is greatly reduced because the threshold which decides equivalence of discernibility matrix is artificial. In this paper, a new concept of soft discernibility matrix is proposed, and related theorems as well as examples are given. We could make attributes reduction for incomplete information system, fuzzy information systems by soft discernibility matrix. Experiments show the effect of proposed algorithm.


## 2. Basic Concepts

LetS=(U,Q,V,F) be an information system, where U={x1,x2,…,xn} a universe, Q is attribute set, V is attribute value set, and F is the mapping of U×Q→V. For convenient explanation, we assume that attribute sets include m condition attributes C={C1,C2,…,Cm} and one decision attribute D (with values D1,D2,…,Ds). Let {Y1,Y2,…,Ys} be a partition equivalence class derived by decision attribute D in which
(1)Yi={x∈U∣F(x,D)=Di},i=1,2,…,s.Eachxi and its attribute value are called information rule in information system; in this paper, we call it xi rule for short. The attribute value of an attribute a (a∈C or a∈D) under rule of xi is denoted by F(xi,a).If each attribute value in information systems is known, the system is called complete information system. In some cases, the information system is called incomplete information system in which some attribute values are unknown. Generally, attribute value setVis a symbol set in information system S=(U,Q,V,F). The system is called fuzzy attribute information system when attribute set V is fuzzy set. The system is real value information system or continuous attribute information systems when attribute value set V is real value.Based on rough sets [9], we give the following Definitions 1–4.Definition 1.
LetX⊆U be subset of universe and P⊆C, the lower approximation value of X about P is
(2)P-X={x∈U∣[x]P⊆X},
and [x]P is the set which is made up of equivalence class elements in U and equivalence relation P.Definition 2.
LetU be a universe, P and Q are equivalence relation clusters in U, and the P positive universe of Q is defined as POSP(Q)=∪X∈U/QP-(X).Definition 3.
ForP⊆C, approximation accuracy of partition {Y1,Y2,…,Yk} is
(3)γP=∑i=1kcard(P-Yi)card(U),
where card() is cardinal number of set.Definition 4.
ForP⊆C, if γP=γC and there does not exist a R being R⊂P and γR≠γP, P is called one attribute reduction of C.
The whole intersection set of attribute reduction ofC is called core of C, which is denoted as Core(C).Definition 5 (see [10]).
Given an information systemS, the elements of discernibility matrix M=(mij) are
(4)mij={a∈C∣F(xi,a)≠F(xj,a)},ifF(xi,D)≠F(xj,D),mij=Φ,ifF(xi,D)=F(xj,D),
where Φ is empty set.
Paper [10] pointed out that if an element in discernibility matrix includes only one attribute, this attribute is core.


## 3. Soft Discernibility Matrix

### 3.1. Probability Discernibility Matrix

Suppose thatS=(U,Q,V,F) is incomplete information system, V is attribute value set, * represents uncertain attribute value in information system, and v is the total number of types of attribute value in the system. The matrix which is constructed by incomplete information system is called the probability discernibility matrix.Definition 6.
Given incomplete information systemS, we denote
(5)m1={a∈C∣F(xi,a)≠F(xj,a)}.
If one of F(xi,a) and F(xj,a) is *,
(6)m2={(1-1v)a∈C}.
If both F(xi,a) and F(xj,a) are *,
(7)m3={(1-1v2)a∈C}.
The elements in M=(mij) probability discernibility matrix are
(8)mij=m1∪m2∪m3,mij=Φ,ifF(xi,D)=F(xj,D),
where Φ is empty set.
In probability differential matrix,mij is an element set which is composed of the attribute symbols being with coefficient or weight.
Given an attributea∈P⊆C, for any two rules xi and xj, ifF(xi,a) and F(xj,a) are known (namely, being certain value or symbol), we denote a∈P1;if one ofF(xi,a) and F(xj,a) is *, we denote a∈P2;if
bothF(xi,a) and F(xj,a) are *, we denote a∈P3.Definition 7.
Given incomplete information systemS, the similarity of rule xi and rule xj in the set of P⊆C is defined as follows.
For every attribute,a⊆P1 satisfy F(xi,a)=F(xj,a) or P1 is empty set; let s0=1; otherwise let
(9)s0=0,sij=s0vk+2m,
where k=card(P2), m=card(P3).
Suppose the subscript set ofYi which belongs to one partition of U derived from equivalence class of D is δi; if t∈δi, we denote s-t=∑j∉δistj. If s-t>1, we let s-t=1.Definition 8.
ForP⊆C and a partition {Y1,Y2,…,Ys}, the approximate accuracy of P can be defined as follows:
(10)λP=∑i=1scard(P-Yi)card(U),
where card(P-Yi)=card(δi)-∑t∈δis-t.Definition 9.
ForP⊆C, if λP=λC and there does not exist R⊂P satisfying λR=λC, then P is called one attribute reduction of C. All the intersection of attribute reduction of C is called core of C and is denoted as Core(C).
In probability discernibility matrix, if there is only one attribute in an element, the included attribute is called single attribute. If there are two or more attributes, the included attributes are called multiattribute items.Theorem 10.
The single attribute whose coefficient in probability discernibility matrix is 1 is core attribute of corresponding incomplete information system.Proof.
In probability discernibility matrix, single attribute is the attribute that under which two different rules (with different decision attribute value) have different attribute value but have the same attribute value under the other condition attributes. We can conclude from Definitions6 and 8 that if single attributes are deleted, λP must be reduced. And then according to Definition 9, we can conclude that the attribute must be core attribute. So the theorem is correct.In information system, the importance of one attribute could be determined by its impact to approximate accuracy of corresponding information systems. The attribute which has larger impact on approximate accuracy is more important than that one which has smaller impact. The attributes which could be reduced are called unimportant attribute.Theorem 11.
In probability discernibility matrix,(1)
if two attributes are single attribute, the attribute whose sum of the coefficients is larger is more important;(2)
if an attribute is always being with another attribute whose coefficient is 1 in same element set then the attribute must be unimportant.Proof.
(1) If two attributes are single attribute, from Definitions7 and 8, we can see that their impact on λP is determined by 6 the sum of coefficient in the single attribute.
The larger the sum of coefficient is, the more impact onλP is, so it is more important.
(2) If an attribute is always being with another attribute whose coefficient is 1 in same element set then the attribute is certainly or possibly with different values under different rules. We can conclude form Definition7 that s0=0, so sij=0. We know that the attribute has no impact on λP according to Definitions 7 and 8, so this attribute is unimportant.


### 3.2. Fuzzy Discernibility Matrix

For convenience of explanation, we suppose that each attribute has single value for each rule in the fuzzy information system.For fuzzy attribute information systems, the concept of equivalence class is no longer applicable, so traditional method could not be used to construct discernibility matrix. In fact, equivalence class represents a correlationship. If the correlation is seen as similarity, then the equivalence can be seen as the association with the value of 1; therefore, the equivalence is a special case of similarity. Each rule is viewed as one fuzzy set constructed by each condition attribute value when we are constructing fuzzy discernibility matrix and investigate similarities between fuzzy set.Definition 12.
Given fuzzy information systemS, the element in fuzzy discernibility matrix M=(mij) is defined as follows:
(11)mij={fi,j,1C1,fi,j,2C2,…,fi,j,mCm},
where fi,j,k=Si,jk-Si,j(k=1,2,…,m). Si,j is fuzzy similarity of xi and xj in the case that F(xi,D)≠F(xj,D). Si,jk is fuzzy similarity in the case that Ck attribute is deleted.From Definition12 we can conclude that each element in fuzzy discernibility matrix is condition attribute set, and it corresponds to a fuzzy set F={fi,j,1,fi,j,2,…,fi,j,m}.Here we denotefk=∑i,jfi,j,k as the sum of coefficients of Ck.In paper [16], the authors give a similarity measure formula. Suppose that A, B are two fuzzy set; then similarity measure base on inclusion degree is
(12)H(A,B)=1n∑Count(A∩BA∪B),
and similarity measure base on close degree is
(13)D(A,B)=∑Count(A∩B)∑Count(A∪B).Given a fuzzy attribute information systemS, the similarity of rule xi and xj is denoted as Sij. For each Yi⊂U derived from equivalence class of D, let the subscript set of Yi be δi; if t∈δi, we denote
(14)s-t=∑j∉δistj.Definition 13.
ForP⊆C, approximation accuracy of partition {Y1,Y2,…,Yk} is
(15)λP=∑i=1kcard(P-Yi)card(U),
where card(P-Yi)=card(δi)-∑t∈δis-t. λC is called approximate accuracy of fuzzy information system.Definition 14.
An attributea∈C satisfying λC-{a}<λC is called core attribute. The core attribute of system denotes Core(C).
As to attribute reduction, the importance of an attribute depends on its impact on approximate accuracyλC.Theorem 15.
An attribute with larger sum of coefficient in all the elements of fuzzy discernibility matrix is more important.Proof.
We can conclude form Definition12 that the sum of coefficients in all elements can be described as
(16)fk=∑t⊆Us-tk-s-t,
where
(17)s-t=∑j∉δiSt,j,s-tk=∑j∉δiSt,jk.
From Definitions 13 and 14, we can conclude that the size of approximate accuracy depends on the size of fk. The attribute with larger coefficient has more impact on λC-{Ck}, so it is more important.Theorem 16.
In fuzzy discernibility matrix, for an attribute, if sum of coefficient in all elements is larger than 0, then the attribute is core attribute.Proof.
We can conclude the proof of Theorem10 that λC could turns larger if Ck is reduced in the case of fk>0, and then Ck is core attribute.We can make attribute reduction in fuzzy information system by use of Definitions12–14 and Theorems 15–16.


## 3.1. Probability Discernibility Matrix

Suppose thatS=(U,Q,V,F) is incomplete information system, V is attribute value set, * represents uncertain attribute value in information system, and v is the total number of types of attribute value in the system. The matrix which is constructed by incomplete information system is called the probability discernibility matrix.Definition 6.
Given incomplete information systemS, we denote
(5)m1={a∈C∣F(xi,a)≠F(xj,a)}.
If one of F(xi,a) and F(xj,a) is *,
(6)m2={(1-1v)a∈C}.
If both F(xi,a) and F(xj,a) are *,
(7)m3={(1-1v2)a∈C}.
The elements in M=(mij) probability discernibility matrix are
(8)mij=m1∪m2∪m3,mij=Φ,ifF(xi,D)=F(xj,D),
where Φ is empty set.
In probability differential matrix,mij is an element set which is composed of the attribute symbols being with coefficient or weight.
Given an attributea∈P⊆C, for any two rules xi and xj, ifF(xi,a) and F(xj,a) are known (namely, being certain value or symbol), we denote a∈P1;if one ofF(xi,a) and F(xj,a) is *, we denote a∈P2;if
bothF(xi,a) and F(xj,a) are *, we denote a∈P3.Definition 7.
Given incomplete information systemS, the similarity of rule xi and rule xj in the set of P⊆C is defined as follows.
For every attribute,a⊆P1 satisfy F(xi,a)=F(xj,a) or P1 is empty set; let s0=1; otherwise let
(9)s0=0,sij=s0vk+2m,
where k=card(P2), m=card(P3).
Suppose the subscript set ofYi which belongs to one partition of U derived from equivalence class of D is δi; if t∈δi, we denote s-t=∑j∉δistj. If s-t>1, we let s-t=1.Definition 8.
ForP⊆C and a partition {Y1,Y2,…,Ys}, the approximate accuracy of P can be defined as follows:
(10)λP=∑i=1scard(P-Yi)card(U),
where card(P-Yi)=card(δi)-∑t∈δis-t.Definition 9.
ForP⊆C, if λP=λC and there does not exist R⊂P satisfying λR=λC, then P is called one attribute reduction of C. All the intersection of attribute reduction of C is called core of C and is denoted as Core(C).
In probability discernibility matrix, if there is only one attribute in an element, the included attribute is called single attribute. If there are two or more attributes, the included attributes are called multiattribute items.Theorem 10.
The single attribute whose coefficient in probability discernibility matrix is 1 is core attribute of corresponding incomplete information system.Proof.
In probability discernibility matrix, single attribute is the attribute that under which two different rules (with different decision attribute value) have different attribute value but have the same attribute value under the other condition attributes. We can conclude from Definitions6 and 8 that if single attributes are deleted, λP must be reduced. And then according to Definition 9, we can conclude that the attribute must be core attribute. So the theorem is correct.In information system, the importance of one attribute could be determined by its impact to approximate accuracy of corresponding information systems. The attribute which has larger impact on approximate accuracy is more important than that one which has smaller impact. The attributes which could be reduced are called unimportant attribute.Theorem 11.
In probability discernibility matrix,(1)
if two attributes are single attribute, the attribute whose sum of the coefficients is larger is more important;(2)
if an attribute is always being with another attribute whose coefficient is 1 in same element set then the attribute must be unimportant.Proof.
(1) If two attributes are single attribute, from Definitions7 and 8, we can see that their impact on λP is determined by 6 the sum of coefficient in the single attribute.
The larger the sum of coefficient is, the more impact onλP is, so it is more important.
(2) If an attribute is always being with another attribute whose coefficient is 1 in same element set then the attribute is certainly or possibly with different values under different rules. We can conclude form Definition7 that s0=0, so sij=0. We know that the attribute has no impact on λP according to Definitions 7 and 8, so this attribute is unimportant.


## 3.2. Fuzzy Discernibility Matrix

For convenience of explanation, we suppose that each attribute has single value for each rule in the fuzzy information system.For fuzzy attribute information systems, the concept of equivalence class is no longer applicable, so traditional method could not be used to construct discernibility matrix. In fact, equivalence class represents a correlationship. If the correlation is seen as similarity, then the equivalence can be seen as the association with the value of 1; therefore, the equivalence is a special case of similarity. Each rule is viewed as one fuzzy set constructed by each condition attribute value when we are constructing fuzzy discernibility matrix and investigate similarities between fuzzy set.Definition 12.
Given fuzzy information systemS, the element in fuzzy discernibility matrix M=(mij) is defined as follows:
(11)mij={fi,j,1C1,fi,j,2C2,…,fi,j,mCm},
where fi,j,k=Si,jk-Si,j(k=1,2,…,m). Si,j is fuzzy similarity of xi and xj in the case that F(xi,D)≠F(xj,D). Si,jk is fuzzy similarity in the case that Ck attribute is deleted.From Definition12 we can conclude that each element in fuzzy discernibility matrix is condition attribute set, and it corresponds to a fuzzy set F={fi,j,1,fi,j,2,…,fi,j,m}.Here we denotefk=∑i,jfi,j,k as the sum of coefficients of Ck.In paper [16], the authors give a similarity measure formula. Suppose that A, B are two fuzzy set; then similarity measure base on inclusion degree is
(12)H(A,B)=1n∑Count(A∩BA∪B),
and similarity measure base on close degree is
(13)D(A,B)=∑Count(A∩B)∑Count(A∪B).Given a fuzzy attribute information systemS, the similarity of rule xi and xj is denoted as Sij. For each Yi⊂U derived from equivalence class of D, let the subscript set of Yi be δi; if t∈δi, we denote
(14)s-t=∑j∉δistj.Definition 13.
ForP⊆C, approximation accuracy of partition {Y1,Y2,…,Yk} is
(15)λP=∑i=1kcard(P-Yi)card(U),
where card(P-Yi)=card(δi)-∑t∈δis-t. λC is called approximate accuracy of fuzzy information system.Definition 14.
An attributea∈C satisfying λC-{a}<λC is called core attribute. The core attribute of system denotes Core(C).
As to attribute reduction, the importance of an attribute depends on its impact on approximate accuracyλC.Theorem 15.
An attribute with larger sum of coefficient in all the elements of fuzzy discernibility matrix is more important.Proof.
We can conclude form Definition12 that the sum of coefficients in all elements can be described as
(16)fk=∑t⊆Us-tk-s-t,
where
(17)s-t=∑j∉δiSt,j,s-tk=∑j∉δiSt,jk.
From Definitions 13 and 14, we can conclude that the size of approximate accuracy depends on the size of fk. The attribute with larger coefficient has more impact on λC-{Ck}, so it is more important.Theorem 16.
In fuzzy discernibility matrix, for an attribute, if sum of coefficient in all elements is larger than 0, then the attribute is core attribute.Proof.
We can conclude the proof of Theorem10 that λC could turns larger if Ck is reduced in the case of fk>0, and then Ck is core attribute.We can make attribute reduction in fuzzy information system by use of Definitions12–14 and Theorems 15–16.


## 4. Attribute Reduction

To illustrate the application of soft discernibility matrix, we give two application examples of attribute reduction in incomplete information and fuzzy information system.


### 4.1. Reduction for Incomplete Information System

The method utilizing probability discernibility matrix for attribute reduction in incomplete information is as follows.The first step of attribute reduction on incomplete information system is constructing corresponding discernibility matrix according to Definition6 and then finding out core attribute and unimportant attribute according to Theorems 10 and 11. The core attributes are retained and the unimportant attributes are deleted. As to other attributes, the most important attributes are joined into reduction set based on their impact on approximate accuracy continuously.Table1 is incomplete information system, in which a, b, c, and d are condition attribute and e is decision attribute.Table 1
Incomplete information system.
U
a
b
c
d
e
X
1
1
1
1
0
1
X
2
1
1
1
*
1
X
3
1
1
*
0
1
X
4
1
0
1
0
0
X
5
1
1
0
1
0
X
6
*
0
*
1
0
X
7
1
0
*
1
2
X
8
0
1
0
1
2In Table1, the values of attribute are 0 or 1, v=2. We can obtain the elements of probability discernibility matrix M based on Definition 6:
(18)mi,i=Θ(i=1,2,…,8),m2,1=m5,4=m8,7=Θ,m3,1=m3,2=Θ,m6,4=m6,5=Θ,m4,1={b},m4,2={b,kd},m4,3={b,kc},m5,1={c,d},m5,2={kc,kd},m5,3={kc},m6,1={ka,b,kc,d},m6,2={ka,b,kc,kd},m6,3={ka,b,k2c,d},m7,1={b,kc,d},m7,2={b,kc,kd},m7,3={b,k2c,d},m7,4={kc,d},m7,5={b,kc},m7,6={ka,k2c},m8,1={a,c,d},m8,2={a,c,kd},m8,3={a,kc,d},m8,4={a,b,c,d},m8,5={a},m8,6={ka,kc},
where Θ is empty set, k=1/v.Because the discernibility matrix is symmetrical, so we only give out lower triangular elements of discernibility matrixM. We can see that a, b, and c are all single attribute according to probability discernibility matrix M, so they are core attributes. The approximate accuracy of incomplete information system condition attribute in table is λC=(1/8)(5+k3). The approximate accuracy λC remains unchanged, even though attribute d is deleted. So the incomplete information system in Table 1 can be reduced as a, b, and c.We can realize attribute reduction for fuzzy information system based on fuzzy discernibility matrix according to definitions and theorems in Section3.2. Table 2 is a fuzzy attribute information system, in which a, b, and c are condition attributes and d is decided attribute.Table 2
Fuzzy attribute information system.
U
a
b
c
d
X
1
0.1
0.5
0.8
0
X
2
0.2
0.3
0.9
0
X
3
0.8
0.6
0.7
1
X
4
0.6
0.5
0.3
1
X
5
0.4
0.4
0.6
2


### 4.2. Reduction for Fuzzy Information System

Given a fuzzy information system, at first similarity,Sij between rules xi and xj is computed, and then fuzzy discernibility matrix M=(mij) could be determined based on Definition 12. Based on M, we construct a new discernibility matrix M* according to following step.Initiatemij* the elements of M* to be null sets.For each element,(19)mij={fi,j,1C1,fi,j,2C2,…,fi,j,mCm}.
Compute
(20)ε=fi,j,k-Si,j,(k=1,2,…,m).
If ε>0, the corresponding attribute Ck is joined into element mij*.The new matrixM* has the traditional form of discernibility matrix. At last, attribute reduction of fuzzy information system could be obtained by discernibility function which is composed of logical computation among elements.The discernibility matrix (lower triangle) could be computed based on similarity measure of closeness degree. The following elements of discernibility matrixM* is obtained from the fuzzy attribute system Table 2 (Θ is empty set):
(21)mi,i*=Θ,(i=1,2,…,5),m2,1*=m4,3*=Θ,m3,1*=m3,2*=m5,1*=m5,2*={a},m4,1*=m4,2*={a,c},m5,3*={a,b},m5,4*={c}.
We can conclude that attributes a, c are single attributes, so a, c are core attributes.The discernibility matrixM* could be reduced as (a,c) based on difference function f(S)=(a)∧(c)∧(a∨c)∧(a∨b).


## 4.1. Reduction for Incomplete Information System

The method utilizing probability discernibility matrix for attribute reduction in incomplete information is as follows.The first step of attribute reduction on incomplete information system is constructing corresponding discernibility matrix according to Definition6 and then finding out core attribute and unimportant attribute according to Theorems 10 and 11. The core attributes are retained and the unimportant attributes are deleted. As to other attributes, the most important attributes are joined into reduction set based on their impact on approximate accuracy continuously.Table1 is incomplete information system, in which a, b, c, and d are condition attribute and e is decision attribute.Table 1
Incomplete information system.
U
a
b
c
d
e
X
1
1
1
1
0
1
X
2
1
1
1
*
1
X
3
1
1
*
0
1
X
4
1
0
1
0
0
X
5
1
1
0
1
0
X
6
*
0
*
1
0
X
7
1
0
*
1
2
X
8
0
1
0
1
2In Table1, the values of attribute are 0 or 1, v=2. We can obtain the elements of probability discernibility matrix M based on Definition 6:
(18)mi,i=Θ(i=1,2,…,8),m2,1=m5,4=m8,7=Θ,m3,1=m3,2=Θ,m6,4=m6,5=Θ,m4,1={b},m4,2={b,kd},m4,3={b,kc},m5,1={c,d},m5,2={kc,kd},m5,3={kc},m6,1={ka,b,kc,d},m6,2={ka,b,kc,kd},m6,3={ka,b,k2c,d},m7,1={b,kc,d},m7,2={b,kc,kd},m7,3={b,k2c,d},m7,4={kc,d},m7,5={b,kc},m7,6={ka,k2c},m8,1={a,c,d},m8,2={a,c,kd},m8,3={a,kc,d},m8,4={a,b,c,d},m8,5={a},m8,6={ka,kc},
where Θ is empty set, k=1/v.Because the discernibility matrix is symmetrical, so we only give out lower triangular elements of discernibility matrixM. We can see that a, b, and c are all single attribute according to probability discernibility matrix M, so they are core attributes. The approximate accuracy of incomplete information system condition attribute in table is λC=(1/8)(5+k3). The approximate accuracy λC remains unchanged, even though attribute d is deleted. So the incomplete information system in Table 1 can be reduced as a, b, and c.We can realize attribute reduction for fuzzy information system based on fuzzy discernibility matrix according to definitions and theorems in Section3.2. Table 2 is a fuzzy attribute information system, in which a, b, and c are condition attributes and d is decided attribute.Table 2
Fuzzy attribute information system.
U
a
b
c
d
X
1
0.1
0.5
0.8
0
X
2
0.2
0.3
0.9
0
X
3
0.8
0.6
0.7
1
X
4
0.6
0.5
0.3
1
X
5
0.4
0.4
0.6
2


## 4.2. Reduction for Fuzzy Information System

Given a fuzzy information system, at first similarity,Sij between rules xi and xj is computed, and then fuzzy discernibility matrix M=(mij) could be determined based on Definition 12. Based on M, we construct a new discernibility matrix M* according to following step.Initiatemij* the elements of M* to be null sets.For each element,(19)mij={fi,j,1C1,fi,j,2C2,…,fi,j,mCm}.
Compute
(20)ε=fi,j,k-Si,j,(k=1,2,…,m).
If ε>0, the corresponding attribute Ck is joined into element mij*.The new matrixM* has the traditional form of discernibility matrix. At last, attribute reduction of fuzzy information system could be obtained by discernibility function which is composed of logical computation among elements.The discernibility matrix (lower triangle) could be computed based on similarity measure of closeness degree. The following elements of discernibility matrixM* is obtained from the fuzzy attribute system Table 2 (Θ is empty set):
(21)mi,i*=Θ,(i=1,2,…,5),m2,1*=m4,3*=Θ,m3,1*=m3,2*=m5,1*=m5,2*={a},m4,1*=m4,2*={a,c},m5,3*={a,b},m5,4*={c}.
We can conclude that attributes a, c are single attributes, so a, c are core attributes.The discernibility matrixM* could be reduced as (a,c) based on difference function f(S)=(a)∧(c)∧(a∨c)∧(a∨b).


## 5. Conclusion

In this paper, a new concept of soft discernibility matrix is proposed; related theorems as well as corresponding application are given. Because soft discernibility matrix could be used in the attribute reduction of incomplete information system, fuzzy information system, it could provide important research basis for attribute reduction of real attribute information system; the method proposed in this paper is of wide application significance in practice. The new concept and related method for attribute reduction are a development to the study for information system and data mining.



---

*Source: 382967-2014-04-30.xml*