# A Variable Precision Attribute Reduction Approach in Multilabel Decision Tables

Authors: Hua Li; Deyu Li; Yanhui Zhai; Suge Wang; Jing Zhang
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Owing to the high dimensionality of multilabel data, feature selection in multilabel learning will be necessary in order to reduce the redundant features and improve the performance of multilabel classification. Rough set theory, as a valid mathematical tool for data analysis, has been widely applied to feature selection (also called attribute reduction). In this study, we propose a variable precision attribute reduct for multilabel data based on rough set theory, calledδ-confidence reduct, which can correctly capture the uncertainty implied among labels. Furthermore, judgement theory and discernibility matrix associated with δ-confidence reduct are also introduced, from which we can obtain the approach to knowledge reduction in multilabel decision tables.


---

## Body

## 1. Introduction

Conventional supervised learning deals with the single-label data, where each instance is associated with a single class label. However, in many real-world tasks, one instance may simultaneously belong to multiple class lultilabel decision tablabels, for example, in text categorization problems, where every document may be labeled as several predefined topics, such as religion and political topics [1]; in image annotation problems, a photograph may be associated with more than one tag, such as elephant, jungle, and Africa [2]; in functional genomics, each gene may be related to a set of functional classes, such as metabolism, transcription, and protein synthesis [3]. Such data are called multilabel data.Owing to the high dimensionality of multilabel data, feature selection in multilabel learning will be necessary in order to reduce the redundant features and improve the performance of multilabel classification. Among various feature selection approaches, rough set theory, proposed by Pawlak [4], has attracted much attention due to its special advantage, that is, the capability of studying imprecise, incomplete, or vague information without requiring prior information.Feature selection in rough set theory is also called attribute reduction. Generally speaking, attribute reduction can be interpreted as a process of finding the minimal set of attributes that can preserve or improve one or several criteria. The minimal set of attributes is called an attribute reduct. In past few years, many researchers have done much work on attribute reduction and the summarization of important results has been done in [5, 6]. The idea of attribute reduction using positive region was first originated in [7, 8], aiming to remove redundant attributes as much as possible while retaining the so-called positive regions. Afterwards, Ziarko introduced the variable precision rough set model and β-reduct to improve the ability of modeling uncertain information [9]. Furthermore, Kryszkiewicz proposed five kinds of attribute reducts for inconsistent information systems [10] and the relationships in these five reducts and some related results are reconsidered and rectified in [11]. Applying discernibility matrix, Skowron and Rauszer [12] proposed an attribute reduction algorithm by computing disjunctive normal form, which is able to obtain all attribute reducts of a given information system. On the other hand, for obtaining a single reduct from a given information system in a relatively short time, many heuristic attribute reduction algorithms have been developed. In order to reduce computational time, Xu et al. [13] proposed a quick attribute reduction algorithm with complexity of max(O(|C||U|),O(|C|2|U/C|)). Further, Qian et al. [14] developed a common accelerator based on four kinds of heuristic reduction algorithms to improve the time efficiency of a heuristic search process.As far as we know, however, little work has been done on applying rough set theory to feature selection in multilabel learning. Although directly applying the existing attribute reduction methods to multilabel data is possible, it does not take into account the uncertainty conveyed by labels and thus can be enhanced further. In this paper, we propose a new attribute reduct for multilabel data, namely,δ-confidence reduct, which overcomes the limitations of existing attribute reduction methods to multilabel data. Furthermore, judgement theory and discernibility matrix associated with δ-confidence reduct are also established. These results provide approaches to knowledge reduction for multilabel data, which are significant in both the theoretic and applied perspectives.The rest of this paper is organized as follows. Some basic notions in rough set theory are briefly reviewed in Section2. Section 3 is devoted to introducing multilabel decision table and analyzing the limitations of the existing attribute reduction methods to multilabel data. In Section 4, the new attribute reduct, δ-confidence reduct, is proposed and the corresponding judgement theorem and discernibility matrix are also introduced. A computative example is also given to illustrate our approaches. Finally, in Section 5, we conclude the paper with a summary and outlook for further research.


## 2. Preliminaries

In this section, we will review several basic concepts in rough set theory.A decision table is an information systemS=(U,A∪D) with A∩D=∅, where U={x1,x2,…,xn} is a nonempty, finite set of objects called universe; A={a1,a2,…,ap} is a nonempty, finite set of condition attributes; D={d1,d2,…,dq} is a nonempty, finite set of decision attributes. Each nonempty subset B⊆A determines an indiscernibility relation in the following way:
(1)RB={(x,y)∈U×U:a(x)=a(y),∀a∈B}.
The indiscernibility relation RB partitions U into some equivalence classes given by U/RB={[x]B:x∈U}, where [x]B denotes the equivalence class determined by x with respect to B; that is,
(2)[x]B={y∈U:(x,y)∈RB}.LetX⊆U and B⊆A. One can define a lower approximation of X and an upper approximation of X by
(3)RB_(X)={x∈U:[x]B⊆X}=⋃‍{[x]B:[x]B⊆X},(4)RB¯(X)={x∈U:[x]B∩X≠∅}=⋃‍{[x]B:[x]B∩X≠∅},
respectively. The lower approximation is called the positive region of X and denoted alternatively as POSB(X). If RB_(X)≠RB¯(X), then X is called a rough set.Attribute reduct is one of the most important topics in rough set theory, which aims to delete the irrelevant or redundant attributes while retaining the discernible ability of original attributes. Among many attribute reduction methods, the positive region reduct [7, 8] is a representative method.Definition 1.
LetS=(U,A∪D) be a decision table and B⊆A. B is a positive region reduct of S if and only if B satisfies the following conditions:(1)
POSB(D)=POSA(D),(2)
POSB′(D)≠POSA(D) for any B′⊆B,
wherePOSB(D)=⋃i=1r‍POSB(Di) and Di(i=1,2,…,r) are the equivalence classes, called decision classes generated by the indiscernibility relation RD={(x,y)∈U×U:d(x)=d(y),∀d∈D}.


## 3. The Multilabel Data

In this section, we first introduce the multilabel decision table and then analyze the limitations of existing attribute reduction approaches to multilabel data.


### 3.1. The Multilabel Data

Multilabel data can be characterized by a multilabel decision tableS=(U,A,F,L,G) with A∩L=∅, where U={x1,x2,…,xn} is a nonempty finite set of objects, called universe; A={a1,a2,…,ap} is a nonempty finite set of condition attributes, called condition attribute set; F={ak:U→Vk,k=1,2,…,p} is a set of information functions with respect to condition attributes and Vk is the domain of ak; L={l1,l2,…,lq} is a nonempty finite set of q possible labels called label set; G={lk:U→Vk′,k=1,2,…,q} is a set of information functions with respect to labels and Vk′={0,1} is the domain of the label lk. If the object x is associated with label lk, then lk(x)=1; otherwise lk(x)=0. The 5-tuple (U,A,F,L,G) can be expressed more simply as (U,A,L) if F and G are understood.Some conventions in multilabel learning are shown as follows.(1)
The object having no labels is irrelevant to multilabel learning and thus is not taken into account in the setting [15, 16]. Note that this convention is a prerequisite for the proposed approach, as discussed in Section 4.(2)
Each label fromL associates with at least one object in U [17].The following example depicts a multilabel decision table in more detail.Example 2.
A multilabel decision tableS=(U,A,L) is presented in Table 1, which is a part of document topic classification problem. It consists of nine documents that belong to one or more of three labels: religion, science, and politics. It can be seen that U={x1,x2,x3,x4,x5,x6,x7,x8,x9}, A={a,b,c}, and L={l1,l2,l3}. Note that each object in U is associated with at least one label from L and each label from L is associated with at least one object in U.Table 1
A multilabel decision table.
U
a
b
c
l
1
l
2
l
3
x
1
2
1
0
1
0
0
x
2
2
1
1
1
0
0
x
3
2
1
0
1
1
0
x
4
1
3
0
1
1
1
x
5
1
3
0
0
1
0
x
6
3
2
1
1
1
1
x
7
1
3
0
0
1
1
x
8
2
3
0
0
1
0
x
9
2
3
0
0
1
1


### 3.2. The Limitations of Existing Attribute Reduction Approaches to Multilabel Data

In this section, we mainly analyze the limitations of existing attribute reduction approaches to multilabel data.For a multilabel decision tableS=(U,A,L), each label attribute can be viewed as a binary decision attribute and then form an indiscernibility relation RL as follows:
(5)RL={(x,y)∈U×U:l(x)=l(y),∀l∈L}.RL partitions U into a family of equivalence classes given by U/RL={D1,D2,…,Dr}. In this case, most existing attribute reduction approaches can be directly applied to multilabel data. Here we consider, for instance, positive region reduct, to delete redundant condition attributes in multilabel decision tables. The following example illustrates this process.Example 3.
For the multilabel decision tableS=(U,A,L) given by Table 1, we can conclude that
(6)URA={X1,X2,X3,X4,X5}={{x1,x3},{x2},{x4,x5,x7},{x6}{x8,x9}};URL={D1,D2,D3,D4,D5}={{x1,x2},{x3},{x4,x6}{x5,x8},{x7,x9}}.
Thus, we have POSA(D)={x2,x6}=X2∪X4. It means that the other equivalence classes X1, X3, and X5 in U/RA are all uncertain with respect to the label set L. For instance, consider the equivalence class X1={x1,x3}. Notice that x1 and x3 are indiscernible with respect to A while their respect label sets {l1} and {l1,l2} are discernible with respect to L. This means X1 is uncertain with respect to the label set L. Furthermore, we can calculate that
(7)UR{a,c}={Y1,Y2,Y3,Y4}={X1∪X5,X2,X3,X4}={{x1,x3,x8,x9},{x2},{x4,x5,x7},{x6}};UR{b,c}={Z1,Z2,Z3,Z4}={X1,X2,X3∪X5,X4}={{x1,x3},{x2},{x4,x5,x7,x8,x9},{x6}}.
Since X1, X3, and X5 are all uncertain with respect to L, they can be safely merged without any information loss. In other words, removing the attribute b or a is valid from the perspective of rough sets. Moreover, one can check that no more attributes can be removed from either {a,c} or {b,c}; so {a,c} and {b,c} are both positive region reducts.
However, notice that all objects inX1 must be associated with label l1 and may be associated with label l2 in the probability of 1/2 and must not be associated with label l3, whereas all objects in X5 must not be associated with label l1 and must be associated with label l2 and may be associated with label l3 in the probability of 1/2. Thus, the uncertainty of X1 and X5 is different, and the equivalence class Y1, the union of X1 and X5, cannot preserve the uncertainty conveyed by labels. This implies that {a,c} is not an appropriate attribute reduct. Similarly, {b,c} is also not an appropriate attribute reduct for multilabel data.Through the above analysis, we know that some positive region reducts cannot preserve uncertainty implied among labels for multilabel data. In fact, since the computation of positive region reduct has to refer to the indiscernibility relationRL, the uncertainty conveyed by labels may be not analyzed thoroughly. Furthermore, note that the uncertainty characterized by RL is also considered by the other existing attribute reduction methods; so they have the same limitations for multilabel data like positive region reduct. Thus it is necessary to reconsider attribute reduction method for multilabel data.


## 3.1. The Multilabel Data

Multilabel data can be characterized by a multilabel decision tableS=(U,A,F,L,G) with A∩L=∅, where U={x1,x2,…,xn} is a nonempty finite set of objects, called universe; A={a1,a2,…,ap} is a nonempty finite set of condition attributes, called condition attribute set; F={ak:U→Vk,k=1,2,…,p} is a set of information functions with respect to condition attributes and Vk is the domain of ak; L={l1,l2,…,lq} is a nonempty finite set of q possible labels called label set; G={lk:U→Vk′,k=1,2,…,q} is a set of information functions with respect to labels and Vk′={0,1} is the domain of the label lk. If the object x is associated with label lk, then lk(x)=1; otherwise lk(x)=0. The 5-tuple (U,A,F,L,G) can be expressed more simply as (U,A,L) if F and G are understood.Some conventions in multilabel learning are shown as follows.(1)
The object having no labels is irrelevant to multilabel learning and thus is not taken into account in the setting [15, 16]. Note that this convention is a prerequisite for the proposed approach, as discussed in Section 4.(2)
Each label fromL associates with at least one object in U [17].The following example depicts a multilabel decision table in more detail.Example 2.
A multilabel decision tableS=(U,A,L) is presented in Table 1, which is a part of document topic classification problem. It consists of nine documents that belong to one or more of three labels: religion, science, and politics. It can be seen that U={x1,x2,x3,x4,x5,x6,x7,x8,x9}, A={a,b,c}, and L={l1,l2,l3}. Note that each object in U is associated with at least one label from L and each label from L is associated with at least one object in U.Table 1
A multilabel decision table.
U
a
b
c
l
1
l
2
l
3
x
1
2
1
0
1
0
0
x
2
2
1
1
1
0
0
x
3
2
1
0
1
1
0
x
4
1
3
0
1
1
1
x
5
1
3
0
0
1
0
x
6
3
2
1
1
1
1
x
7
1
3
0
0
1
1
x
8
2
3
0
0
1
0
x
9
2
3
0
0
1
1


## 3.2. The Limitations of Existing Attribute Reduction Approaches to Multilabel Data

In this section, we mainly analyze the limitations of existing attribute reduction approaches to multilabel data.For a multilabel decision tableS=(U,A,L), each label attribute can be viewed as a binary decision attribute and then form an indiscernibility relation RL as follows:
(5)RL={(x,y)∈U×U:l(x)=l(y),∀l∈L}.RL partitions U into a family of equivalence classes given by U/RL={D1,D2,…,Dr}. In this case, most existing attribute reduction approaches can be directly applied to multilabel data. Here we consider, for instance, positive region reduct, to delete redundant condition attributes in multilabel decision tables. The following example illustrates this process.Example 3.
For the multilabel decision tableS=(U,A,L) given by Table 1, we can conclude that
(6)URA={X1,X2,X3,X4,X5}={{x1,x3},{x2},{x4,x5,x7},{x6}{x8,x9}};URL={D1,D2,D3,D4,D5}={{x1,x2},{x3},{x4,x6}{x5,x8},{x7,x9}}.
Thus, we have POSA(D)={x2,x6}=X2∪X4. It means that the other equivalence classes X1, X3, and X5 in U/RA are all uncertain with respect to the label set L. For instance, consider the equivalence class X1={x1,x3}. Notice that x1 and x3 are indiscernible with respect to A while their respect label sets {l1} and {l1,l2} are discernible with respect to L. This means X1 is uncertain with respect to the label set L. Furthermore, we can calculate that
(7)UR{a,c}={Y1,Y2,Y3,Y4}={X1∪X5,X2,X3,X4}={{x1,x3,x8,x9},{x2},{x4,x5,x7},{x6}};UR{b,c}={Z1,Z2,Z3,Z4}={X1,X2,X3∪X5,X4}={{x1,x3},{x2},{x4,x5,x7,x8,x9},{x6}}.
Since X1, X3, and X5 are all uncertain with respect to L, they can be safely merged without any information loss. In other words, removing the attribute b or a is valid from the perspective of rough sets. Moreover, one can check that no more attributes can be removed from either {a,c} or {b,c}; so {a,c} and {b,c} are both positive region reducts.
However, notice that all objects inX1 must be associated with label l1 and may be associated with label l2 in the probability of 1/2 and must not be associated with label l3, whereas all objects in X5 must not be associated with label l1 and must be associated with label l2 and may be associated with label l3 in the probability of 1/2. Thus, the uncertainty of X1 and X5 is different, and the equivalence class Y1, the union of X1 and X5, cannot preserve the uncertainty conveyed by labels. This implies that {a,c} is not an appropriate attribute reduct. Similarly, {b,c} is also not an appropriate attribute reduct for multilabel data.Through the above analysis, we know that some positive region reducts cannot preserve uncertainty implied among labels for multilabel data. In fact, since the computation of positive region reduct has to refer to the indiscernibility relationRL, the uncertainty conveyed by labels may be not analyzed thoroughly. Furthermore, note that the uncertainty characterized by RL is also considered by the other existing attribute reduction methods; so they have the same limitations for multilabel data like positive region reduct. Thus it is necessary to reconsider attribute reduction method for multilabel data.


## 4. The New Attribute Reduction Approach in Multilabel Data Decision Tables

In this section, we will introduce a new attribute reduct referred to asδ-confidence reduct and show some advantages of δ-confidence reduct in unraveling the uncertainty of multilabel data. Moreover, judgement theory and discernibility matrix associated with δ-confidence reduct are also established.


### 4.1.δ-Confidence Reduct in Multilabel Decision Tables

First, we present the following definition.Definition 4.
LetS=(U,A,L) be a multilabel decision table, where A={a1,a2,…,ap} and L={l1,l2,…,lq}. For each label li, one defines the label decision set as the collection of all possible objects having the label:
(8)Hi={x∈U:li(x)=1}.Considering Convention 1 of multilabel learning, one has∪i=1qHi=U; that is, H1,H2,…,Hq form a cover of U.In the following, we present a particular function to characterize the uncertainty implied among labels.Definition 5.
LetS=(U,A,L) be a multilabel decision table, let P(L) be the power set of label set L, and let H1,H2,…,Hq be q label decision sets. Given a subset B⊆A and δ∈[0,1], one defines a δ-confidence label function ηBδ:U→P(L), as follows:
(9)ηBδ(x)={{li∈L:|[x]B∩Hi||[x]B|≥δ}if0<δ≤1;{li∈L:|[x]B∩Hi||[x]B|>0}ifδ=0.Theδ-confidence label function ηBδ(x) is the collection of the labels that associate with at least δ% objects in [x]B. In other words, ηBδ(x) is the collection of the labels which associate with each object in [x]B by at least δ% confidence level.Example 6.
Consider the multilabel decision tableS=(U,A,L) given by Table 1. If δ=0.6, then the 0.6-confidence label function with respect to attribute set A can be calculated that
(10)ηA0.6(x1)=ηA0.6(x3)={l1},ηA0.6(x2)={l1},ηA0.6(x4)=ηA0.6(x5)=ηA0.6(x7)={l2,l3},ηA0.6(x6)={l1,l2,l3},ηA0.6(x8)=ηA0.6(x9)={l2}.We have the following property.Theorem 7.
LetS=(U,A,L) be a multilabel decision table, B,C⊆A. Then(1)
if0≤δ1≤δ2≤1, then ηBδ2(x)⊆ηBδ1(x);(2)
ifB⊆C, then ηB1(x)⊆ηC1(x)⊆ηC0(x)⊆ηB0(x);(3)
for anyx∈U, ηB0(x)≠∅;(4)
if[x]B=[y]B, then ηBδ(x)=ηBδ(y).Proof.
(1) Letli∈ηBδ2(x). Then we have |[x]B∩Hi|/[x]B≥δ2. Note that δ2≥δ1; thus |[x]B∩Hi|/[x]B≥δ1. It means that li∈ηBδ1(x). Therefore ηBδ2(x)⊆ηBδ1(x).
(2) SinceB⊆C, we have [x]C⊆[x]B.
Ifli∈ηB1(x), then [x]B⊆Hi. Since [x]C⊆[x]B, we have [x]C⊆Hi. Thus li∈ηC1(x). Therefore ηB1(x)⊆ηC1(x).
According to Theorem7 (1), we have ηC1(x)⊆ηC0(x).
Iflj∈ηC0(x), then [x]C∩Hj≠∅. Since [x]C⊆[x]B, we have [x]B∩Hj≠∅. That means lj∈ηB0(x). Therefore ηC0(x)⊆ηB0(x).
(3) If there existsx∈U such that ηB0(x)=∅, then [x]B∩Hi=∅,  i=1,2,…,q. Thus [x]B∩(H1∪H2∪⋯Hq)=∅. Since ∪i=1qHi=U, we have [x]B∩(H1∪H2∪⋯Hq)=[x]B∩U≠∅. It is a contradiction.
(4) It is straightforward by the definition ofηBδ(x) and [xB]=[y]B.Now we define the consistentδ-confidence set using δ-confidence label function. Furthermore, we present the definition of new attribute reduct.Definition 8.
LetS=(U,A,L) be a multilabel decision table and B⊆A. If ηBδ(x)=ηAδ(x), for all x∈U, one says that B is a consistent δ-confidence set of S. If B is a consistent δ-confidence set and no proper subset of B is a consistent δ-confidence set, then B is called a δ-confidence reduct of S.Aδ-confidence reduct is the minimal set of condition attributes that preserves the invariances of the δ-confidence label function of all objects in U.Example 9 (continued from Example6.).
For the multilabel decision tableS=(U,A,L) given by Table 1, we have
(11)η{a}0.6(x1)={l1,l2}≠ηA0.6(x1),η{b}0.6(x8)={l2,l3}≠ηA0.6(x8),η{c}0.6(x6)={l1}≠ηA0.6(x6),η{a,c}0.6(x1)={l2}≠ηA0.6(x1),η{b,c}0.6(x8)={l2,l3}≠ηA0.6(x8),η{a,b}0.6(x)=ηA0.6(x)for anyx∈U.
Therefore, we obtain the unique 0.6-confidence reduct: {a,b}.
Considering Example3, however, we know that {a,c} and {b,c} are two positive region reducts for the same multilabel decision table. We think δ-confidence reduct is more appropriate for multilabel data than positive region reduct. This is because δ-confidence label function can more reasonably characterize the uncertainty implied among labels than the indiscernibility relation RL.Note that the uncertainty characterized byRL is also considered by the other existing attribute reduction methods. Therefore, for multilabel data, δ-confidence reduct has significant advantages when compared with existing attribute reduction methods.


### 4.2. Discernibility Matric ofδ-Confidence Reduct

This section provides a discernibility matrice approach [12] to obtain all δ-confidence reducts. Firstly, we present the judgement theorem of consistent δ-confidence set.Theorem 10 (judgement theorem of consistentδ-confidence set).
LetS=(U,A,L) be a multilabel decision table, B⊆A and δ∈[0,1]. Then the following conditions are equivalent:(1)
B is a consistent δ-confidence set;(2)
for anyx,y∈U, if ηAδ(x)≠ηAδ(y), then [x]B∩[y]B=∅.Proof.
(
1
)
⇒
(
2
). If there exist x,y∈U such that [x]B∩[y]B≠∅, then [x]B=[y]B. By Theorem 7(4), we have ηBδ(x)=ηBδ(y). Note that B is a consistent δ-confidence set; we have ηBδ(x)=ηAδ(x) and ηBδ(y)=ηAδ(y). Therefore ηAδ(x)=ηAδ(y).
(
2
)
⇒
(
1
). Since B⊆A, it is easy to verify that I([x]B)={[y]A:[y]A⊆[x]B} forms a partition of [x]B.
For anyx∈U, if [y]A⊆[x]B, then [x]B∩[y]B≠∅. By the assumption we obtain ηAδ(x)=ηAδ(y).
Letli∈ηAδ(x). Then for all [y]A∈I([x]B), we have li∈ηAδ(y); that is to say, |[y]A∩Hi|/|[y]A|≥δ.
Therefore we have that(12)|[x]B∩Hi||[x]B|=∑{|[y]A∩Hi|:[y]A∈I([x]B)}|[x]B|=∑{|[y]A∩Hi||[y]A|·|[y]A||[x]B|:[y]A∈I([x]B)}⩾δ·∑{|[y]A||[x]B|:[y]A∈I([x]B)}=δ.
As a result, li∈ηBδ(x).
On the other hand, we assume thatli∈ηBδ(x); however, li∉ηAδ(x). For any [y]A∈I([x]B), we have ηAδ(x)=ηAδ(y); hence li∉ηAδ(y); that is to say, |[y]A∩Hi|/|[y]A|<δ. Since [x]B=∪{[y]A:[y]A∈I([x]B)}, we have
(13)|[x]B∩Hi||[x]B|=∑{|[y]A∩Hi|:[y]A∈I([x]B)}|[x]B|=∑{|[y]A∩Hi||[y]A|·|[y]A||[x]B|:[y]A∈I([x]B)}<δ·∑{|[y]A||[x]B|:[y]A∈I([x]B)}=δ.
Therefore li∉ηBδ(x), which is a contradiction.
Thus we conclude thatηAδ(x)=ηBδ(x) for any x∈U. According to Definition 8, we have that B is a consistent δ-confidence set.Theorem10 provides an approach to judge whether a subset of attributes is a consistent δ-confidence set in multilabel decision tables. Now we present a method for computing all δ-confidence reducts. First, we give the following notion.Definition 11.
LetS=(U,A,L) be a multilabel decision table and U/RA={X1,X2,…,Xm}. One denotes
(14)Δδ={([x]A,[y]A):ηAδ(x)≠ηAδ(y)}.
Byak(Xi) the value of ak with respect to the objects in Xi. Define
(15)Mδ(Xi,Xj)W={{ak∈A:ak(Xi)≠ak(Xj)},(Xi,Xj)∈Δδ;A,(Xi,Xj)∉Δδ.ThenMδ(Xi,Xj) is called δ-confidence discernibility attribute sets. And Mδ=(Mδ(Xi,Xj),i,j≤m) is called the δ-confidence discernibility matrix.For theδ-confidence discernibility matrix, we have the following property.Theorem 12.
The discernibility matrixMδ=(Mδ(Xi,Xj),i,j≤m) satisfies the following properties:(1)
Mδ is a symmetric matrix; that is, for any i,j≤m, Mδ(Xi,Xj)=Mδ(Xj,Xi);(2)
elements in the main diagonals are allA; that is, for any i≤m, Mδ(Xi,Xi)=A;(3)
for anyi,s,j≤m, Mδ(Xi,Xj)⊆Mδ(Xi,Xs)∪Mδ(Xs,Xj).Proof.
The proofs of (1) and (2) are straightforward. We only need to prove (3). If there existsak∈A such that ak∈Mδ(Xi,Xj) but ak∉Mδ(Xi,Xs)∪Mδ(Xs,Xj), that is, ak∉Mδ(Xi,Xs) and ak∉Mδ(Xs,Xj), then according to Definition 11, we have ak(Xi)=ak(Xs) and ak(Xs)=ak(Xj). Thus ak(Xi)=ak(Xj); that is, ak∉Mδ(Xi,Xj), a contradiction.In the following, we establish some connections between consistentδ-confidence set and discernibility matrix.Theorem 13.
LetS=(U,A,L) be a multilabel decision table, B⊆A and δ∈[0,1]. Then, B is a consistent δ-confidence set if and only if B∩Mδ(Xi,Xj)≠∅ for all (Xi,Xj)∈Δδ.Proof.
“⇒” For any (Xi,Xj)∈Δδ, there exist x,y∈U, such that Xi=[x]A and Xj=[y]A. From the definition of Δδ, we have ηAδ(x)≠ηAδ(y). Since B is a consistent δ-confidence set, we have [x]B∩[y]B=∅ from Theorem 10. Therefore there exists ak∈B such that ak(x)≠ak(y); that is, ak(Xi)≠ak(Xj). Hence ak∈Mδ(Xi,Xj); that is, B∩Mδ(Xi,Xj)≠∅.
“⇐” Let (Xi,Xj)∈Δδ. Since B∩Mδ(Xi,Xj)≠∅, for all (Xi,Xj)∈Δδ, there exists al∈B such that al∈Mδ(Xi,Xj). Then we have al(Xi)≠al(Xj); that is, al(x)≠al(y) for [x]A=Xi and [y]A=Xj. It means [x]B∩[y]B=∅. We then conclude that if (Xi,Xj)∈Δδ, that is, ηAδ(x)≠ηAδ(y), then [x]B∩[y]B=∅. It follows from Theorem 10 that B is a consistent δ-confidence set.Next we introduce the concept of discernibility function which helps us to computeδ-confidence reduct.Definition 14.
LetS=(U,A,L) be a multilabel decision table, let δ∈[0,1], and let Mδ=(Mδ(Xi,Xj),i,j≤m) be the δ-confidence discernibility matrix, where A={a1,…,ap}. A δ-confidence discernibility function FSδ for a multilabel decision table S is a boolean function of p boolean variables a~1,…,a~p corresponding to the attributes a1,…,ap, respectively, and is defined as follows:
(16)FSδ(a~1,…,a~p)=⋀{⋁Mδ(Xi,Xj),i,j≤m}=⋀{⋁Mδ(Xi,Xj),(Xi,Xj)∈Δδ},
where ⋁Mδ(Xi,Xj) is the disjunction of all variables a~ such that a∈Mδ(Xi,Xj).In the sequel we will writeai instead of a~i when no confusion arises. Furthermore, according to related logical knowledge, we have the following theorem.Theorem 15.
LetS=(U,A,L) be a multilabel decision table. Then an attribute subset B of A is a δ-confidence reduct of S if and only if ∧B is a prime implicant of S.Theorem15 provides a discernibility matrix based method to compute all δ-confidence reducts. The following example illustrates the validity of the approach.Example 16.
Consider the multilabel decision table given by Table1. We have U/RA={X1,…,X5}, where
(17)X1={x1,x3},X2={x2},X3={x4,x5,x7},X4={x6},X5={x8,x9}.
According to the calculation results of ηA0.6(x) in Example 6, we have
(18)Δ0.6={(X1,X3),(X1,X4),(X1,X5),(X2,X3),ww(X2,X4),(X2,X5),(X3,X4),(X3,X5),(X4,X5)}.
Note that ηA0.6(x1)=ηA0.6(x2)=ηA0.6(x3). Therefore (X1,X2)∉Δ0.6.
We can calculate theδ-confidence discernibility matrix shown in Table 2.
Consequently, we have(19)F=(a∨b∨c)∧(a∨b)∧(a)∧(b)∧(b∨c)=a∧b.
By Theorem15 we derive that {a,b} is the unique 0.6-confidence reduct which accords with the results in Example 9.Table 2
Theδ-confidence discernibility matrix M.
X
1
X
2
X
3
X
4
X
5
X
1
X
2
a
,
b
,
c
X
3
a
,
b
a
,
b
,
c
X
4
a
,
b
,
c
a
,
b
a
,
b
,
c
X
5
b
b
,
c
a
a
,
b
,
c


## 4.1.δ-Confidence Reduct in Multilabel Decision Tables

First, we present the following definition.Definition 4.
LetS=(U,A,L) be a multilabel decision table, where A={a1,a2,…,ap} and L={l1,l2,…,lq}. For each label li, one defines the label decision set as the collection of all possible objects having the label:
(8)Hi={x∈U:li(x)=1}.Considering Convention 1 of multilabel learning, one has∪i=1qHi=U; that is, H1,H2,…,Hq form a cover of U.In the following, we present a particular function to characterize the uncertainty implied among labels.Definition 5.
LetS=(U,A,L) be a multilabel decision table, let P(L) be the power set of label set L, and let H1,H2,…,Hq be q label decision sets. Given a subset B⊆A and δ∈[0,1], one defines a δ-confidence label function ηBδ:U→P(L), as follows:
(9)ηBδ(x)={{li∈L:|[x]B∩Hi||[x]B|≥δ}if0<δ≤1;{li∈L:|[x]B∩Hi||[x]B|>0}ifδ=0.Theδ-confidence label function ηBδ(x) is the collection of the labels that associate with at least δ% objects in [x]B. In other words, ηBδ(x) is the collection of the labels which associate with each object in [x]B by at least δ% confidence level.Example 6.
Consider the multilabel decision tableS=(U,A,L) given by Table 1. If δ=0.6, then the 0.6-confidence label function with respect to attribute set A can be calculated that
(10)ηA0.6(x1)=ηA0.6(x3)={l1},ηA0.6(x2)={l1},ηA0.6(x4)=ηA0.6(x5)=ηA0.6(x7)={l2,l3},ηA0.6(x6)={l1,l2,l3},ηA0.6(x8)=ηA0.6(x9)={l2}.We have the following property.Theorem 7.
LetS=(U,A,L) be a multilabel decision table, B,C⊆A. Then(1)
if0≤δ1≤δ2≤1, then ηBδ2(x)⊆ηBδ1(x);(2)
ifB⊆C, then ηB1(x)⊆ηC1(x)⊆ηC0(x)⊆ηB0(x);(3)
for anyx∈U, ηB0(x)≠∅;(4)
if[x]B=[y]B, then ηBδ(x)=ηBδ(y).Proof.
(1) Letli∈ηBδ2(x). Then we have |[x]B∩Hi|/[x]B≥δ2. Note that δ2≥δ1; thus |[x]B∩Hi|/[x]B≥δ1. It means that li∈ηBδ1(x). Therefore ηBδ2(x)⊆ηBδ1(x).
(2) SinceB⊆C, we have [x]C⊆[x]B.
Ifli∈ηB1(x), then [x]B⊆Hi. Since [x]C⊆[x]B, we have [x]C⊆Hi. Thus li∈ηC1(x). Therefore ηB1(x)⊆ηC1(x).
According to Theorem7 (1), we have ηC1(x)⊆ηC0(x).
Iflj∈ηC0(x), then [x]C∩Hj≠∅. Since [x]C⊆[x]B, we have [x]B∩Hj≠∅. That means lj∈ηB0(x). Therefore ηC0(x)⊆ηB0(x).
(3) If there existsx∈U such that ηB0(x)=∅, then [x]B∩Hi=∅,  i=1,2,…,q. Thus [x]B∩(H1∪H2∪⋯Hq)=∅. Since ∪i=1qHi=U, we have [x]B∩(H1∪H2∪⋯Hq)=[x]B∩U≠∅. It is a contradiction.
(4) It is straightforward by the definition ofηBδ(x) and [xB]=[y]B.Now we define the consistentδ-confidence set using δ-confidence label function. Furthermore, we present the definition of new attribute reduct.Definition 8.
LetS=(U,A,L) be a multilabel decision table and B⊆A. If ηBδ(x)=ηAδ(x), for all x∈U, one says that B is a consistent δ-confidence set of S. If B is a consistent δ-confidence set and no proper subset of B is a consistent δ-confidence set, then B is called a δ-confidence reduct of S.Aδ-confidence reduct is the minimal set of condition attributes that preserves the invariances of the δ-confidence label function of all objects in U.Example 9 (continued from Example6.).
For the multilabel decision tableS=(U,A,L) given by Table 1, we have
(11)η{a}0.6(x1)={l1,l2}≠ηA0.6(x1),η{b}0.6(x8)={l2,l3}≠ηA0.6(x8),η{c}0.6(x6)={l1}≠ηA0.6(x6),η{a,c}0.6(x1)={l2}≠ηA0.6(x1),η{b,c}0.6(x8)={l2,l3}≠ηA0.6(x8),η{a,b}0.6(x)=ηA0.6(x)for anyx∈U.
Therefore, we obtain the unique 0.6-confidence reduct: {a,b}.
Considering Example3, however, we know that {a,c} and {b,c} are two positive region reducts for the same multilabel decision table. We think δ-confidence reduct is more appropriate for multilabel data than positive region reduct. This is because δ-confidence label function can more reasonably characterize the uncertainty implied among labels than the indiscernibility relation RL.Note that the uncertainty characterized byRL is also considered by the other existing attribute reduction methods. Therefore, for multilabel data, δ-confidence reduct has significant advantages when compared with existing attribute reduction methods.


## 4.2. Discernibility Matric ofδ-Confidence Reduct

This section provides a discernibility matrice approach [12] to obtain all δ-confidence reducts. Firstly, we present the judgement theorem of consistent δ-confidence set.Theorem 10 (judgement theorem of consistentδ-confidence set).
LetS=(U,A,L) be a multilabel decision table, B⊆A and δ∈[0,1]. Then the following conditions are equivalent:(1)
B is a consistent δ-confidence set;(2)
for anyx,y∈U, if ηAδ(x)≠ηAδ(y), then [x]B∩[y]B=∅.Proof.
(
1
)
⇒
(
2
). If there exist x,y∈U such that [x]B∩[y]B≠∅, then [x]B=[y]B. By Theorem 7(4), we have ηBδ(x)=ηBδ(y). Note that B is a consistent δ-confidence set; we have ηBδ(x)=ηAδ(x) and ηBδ(y)=ηAδ(y). Therefore ηAδ(x)=ηAδ(y).
(
2
)
⇒
(
1
). Since B⊆A, it is easy to verify that I([x]B)={[y]A:[y]A⊆[x]B} forms a partition of [x]B.
For anyx∈U, if [y]A⊆[x]B, then [x]B∩[y]B≠∅. By the assumption we obtain ηAδ(x)=ηAδ(y).
Letli∈ηAδ(x). Then for all [y]A∈I([x]B), we have li∈ηAδ(y); that is to say, |[y]A∩Hi|/|[y]A|≥δ.
Therefore we have that(12)|[x]B∩Hi||[x]B|=∑{|[y]A∩Hi|:[y]A∈I([x]B)}|[x]B|=∑{|[y]A∩Hi||[y]A|·|[y]A||[x]B|:[y]A∈I([x]B)}⩾δ·∑{|[y]A||[x]B|:[y]A∈I([x]B)}=δ.
As a result, li∈ηBδ(x).
On the other hand, we assume thatli∈ηBδ(x); however, li∉ηAδ(x). For any [y]A∈I([x]B), we have ηAδ(x)=ηAδ(y); hence li∉ηAδ(y); that is to say, |[y]A∩Hi|/|[y]A|<δ. Since [x]B=∪{[y]A:[y]A∈I([x]B)}, we have
(13)|[x]B∩Hi||[x]B|=∑{|[y]A∩Hi|:[y]A∈I([x]B)}|[x]B|=∑{|[y]A∩Hi||[y]A|·|[y]A||[x]B|:[y]A∈I([x]B)}<δ·∑{|[y]A||[x]B|:[y]A∈I([x]B)}=δ.
Therefore li∉ηBδ(x), which is a contradiction.
Thus we conclude thatηAδ(x)=ηBδ(x) for any x∈U. According to Definition 8, we have that B is a consistent δ-confidence set.Theorem10 provides an approach to judge whether a subset of attributes is a consistent δ-confidence set in multilabel decision tables. Now we present a method for computing all δ-confidence reducts. First, we give the following notion.Definition 11.
LetS=(U,A,L) be a multilabel decision table and U/RA={X1,X2,…,Xm}. One denotes
(14)Δδ={([x]A,[y]A):ηAδ(x)≠ηAδ(y)}.
Byak(Xi) the value of ak with respect to the objects in Xi. Define
(15)Mδ(Xi,Xj)W={{ak∈A:ak(Xi)≠ak(Xj)},(Xi,Xj)∈Δδ;A,(Xi,Xj)∉Δδ.ThenMδ(Xi,Xj) is called δ-confidence discernibility attribute sets. And Mδ=(Mδ(Xi,Xj),i,j≤m) is called the δ-confidence discernibility matrix.For theδ-confidence discernibility matrix, we have the following property.Theorem 12.
The discernibility matrixMδ=(Mδ(Xi,Xj),i,j≤m) satisfies the following properties:(1)
Mδ is a symmetric matrix; that is, for any i,j≤m, Mδ(Xi,Xj)=Mδ(Xj,Xi);(2)
elements in the main diagonals are allA; that is, for any i≤m, Mδ(Xi,Xi)=A;(3)
for anyi,s,j≤m, Mδ(Xi,Xj)⊆Mδ(Xi,Xs)∪Mδ(Xs,Xj).Proof.
The proofs of (1) and (2) are straightforward. We only need to prove (3). If there existsak∈A such that ak∈Mδ(Xi,Xj) but ak∉Mδ(Xi,Xs)∪Mδ(Xs,Xj), that is, ak∉Mδ(Xi,Xs) and ak∉Mδ(Xs,Xj), then according to Definition 11, we have ak(Xi)=ak(Xs) and ak(Xs)=ak(Xj). Thus ak(Xi)=ak(Xj); that is, ak∉Mδ(Xi,Xj), a contradiction.In the following, we establish some connections between consistentδ-confidence set and discernibility matrix.Theorem 13.
LetS=(U,A,L) be a multilabel decision table, B⊆A and δ∈[0,1]. Then, B is a consistent δ-confidence set if and only if B∩Mδ(Xi,Xj)≠∅ for all (Xi,Xj)∈Δδ.Proof.
“⇒” For any (Xi,Xj)∈Δδ, there exist x,y∈U, such that Xi=[x]A and Xj=[y]A. From the definition of Δδ, we have ηAδ(x)≠ηAδ(y). Since B is a consistent δ-confidence set, we have [x]B∩[y]B=∅ from Theorem 10. Therefore there exists ak∈B such that ak(x)≠ak(y); that is, ak(Xi)≠ak(Xj). Hence ak∈Mδ(Xi,Xj); that is, B∩Mδ(Xi,Xj)≠∅.
“⇐” Let (Xi,Xj)∈Δδ. Since B∩Mδ(Xi,Xj)≠∅, for all (Xi,Xj)∈Δδ, there exists al∈B such that al∈Mδ(Xi,Xj). Then we have al(Xi)≠al(Xj); that is, al(x)≠al(y) for [x]A=Xi and [y]A=Xj. It means [x]B∩[y]B=∅. We then conclude that if (Xi,Xj)∈Δδ, that is, ηAδ(x)≠ηAδ(y), then [x]B∩[y]B=∅. It follows from Theorem 10 that B is a consistent δ-confidence set.Next we introduce the concept of discernibility function which helps us to computeδ-confidence reduct.Definition 14.
LetS=(U,A,L) be a multilabel decision table, let δ∈[0,1], and let Mδ=(Mδ(Xi,Xj),i,j≤m) be the δ-confidence discernibility matrix, where A={a1,…,ap}. A δ-confidence discernibility function FSδ for a multilabel decision table S is a boolean function of p boolean variables a~1,…,a~p corresponding to the attributes a1,…,ap, respectively, and is defined as follows:
(16)FSδ(a~1,…,a~p)=⋀{⋁Mδ(Xi,Xj),i,j≤m}=⋀{⋁Mδ(Xi,Xj),(Xi,Xj)∈Δδ},
where ⋁Mδ(Xi,Xj) is the disjunction of all variables a~ such that a∈Mδ(Xi,Xj).In the sequel we will writeai instead of a~i when no confusion arises. Furthermore, according to related logical knowledge, we have the following theorem.Theorem 15.
LetS=(U,A,L) be a multilabel decision table. Then an attribute subset B of A is a δ-confidence reduct of S if and only if ∧B is a prime implicant of S.Theorem15 provides a discernibility matrix based method to compute all δ-confidence reducts. The following example illustrates the validity of the approach.Example 16.
Consider the multilabel decision table given by Table1. We have U/RA={X1,…,X5}, where
(17)X1={x1,x3},X2={x2},X3={x4,x5,x7},X4={x6},X5={x8,x9}.
According to the calculation results of ηA0.6(x) in Example 6, we have
(18)Δ0.6={(X1,X3),(X1,X4),(X1,X5),(X2,X3),ww(X2,X4),(X2,X5),(X3,X4),(X3,X5),(X4,X5)}.
Note that ηA0.6(x1)=ηA0.6(x2)=ηA0.6(x3). Therefore (X1,X2)∉Δ0.6.
We can calculate theδ-confidence discernibility matrix shown in Table 2.
Consequently, we have(19)F=(a∨b∨c)∧(a∨b)∧(a)∧(b)∧(b∨c)=a∧b.
By Theorem15 we derive that {a,b} is the unique 0.6-confidence reduct which accords with the results in Example 9.Table 2
Theδ-confidence discernibility matrix M.
X
1
X
2
X
3
X
4
X
5
X
1
X
2
a
,
b
,
c
X
3
a
,
b
a
,
b
,
c
X
4
a
,
b
,
c
a
,
b
a
,
b
,
c
X
5
b
b
,
c
a
a
,
b
,
c


## 5. Conclusion

Theδ-confidence reduct presented in this paper is an attribute reduction method designed for multilabel decision tables. Compared with the existing attribute reduction methods, the δ-confidence reduct accurately characterizes uncertainty implied among labels; thus it is more appropriate for multilabel data. Moreover we proposed the corresponding discernibility matrix based method to compute δ-confidence reduct, which is significant in both the theoretic and applied perspectives. In further research, the property of δ-confidence reduct and corresponding heuristic algorithm will be considered.



---

*Source: 359626-2014-08-06.xml*