Attribute selection approaches for incomplete interval-value data

Abstract

Attribute selection in an information system (IS) is an important issue when dealing with a large amount of data. An IS with incomplete interval-value data is called an incomplete interval-valued information system (IIVIS). This paper proposes attribute selection approaches for an IIVIS. Firstly, the similarity degree between two information values of a given attribute in an IIVIS is proposed. Then, the tolerance relation on the object set with respect to a given attribute subset is obtained. Next, θ-reduction in an IIVIS is studied. What is more, connections between the proposed reduction and information entropy are revealed. Lastly, three reduction algorithms base on θ-discernibility matrix, θ-information entropy and θ-significance in an IIVIS are given.

Keywords

Rough set theory IIVIS similarity degree algorithm

1 Introduction

Rough set theory was put forward by Pawlak [20 –23]. This theory is a significant approach for managing uncertainty. One of the advantages of rough set is that it does not need any preliminary or additional data information, but it is directly based on the original data, so it is more objective and credible. Many applications of rough set theory are connected with information systems (ISs) [2 , 27].

Information system (IS) based on rough set theory was also introduced by Pawlak. They may reveal large databases and knowledge discovery process mathematically. An interval-valued information system (IVIS) means an IS where its information values are interval numbers. An incomplete interval-valued information system (IIVIS) means an IVIS with missing values. As a common IS, IVISs have been studied by many scholars. For example, Dai et al. introduced θ-similarity entropy and then proposed θ-rough degree based on θ-similarity entropy to measure the uncertainty of rough sets in IIVISs. Yao [30] presented an interval set model for IVISs with upper and lower approximations, as well as introduced generalized decision logic; Leung et al. [15] investigated a rough set approach based on knowledge induction process for selecting decision rules with minimum feature sets in IVISs; Xie et al. [28] considered new measures of uncertainty for an IVIS; Yang et al. [31] raised a dominance relation and generated the optimal decision rules in IIVISs; Sakai et al. [25] developed a rule generation prototype system for incomplete information databases in Lipski that can process IVISs.

As an important tool for estimating incomplete information, information entropy has been applied. We refer to the articles about information entropy of other scholars. For instance, D $\ddot{u}$ ntsch and Gediga [5] applied Shannon’s entropy to the measurement of decision rules in rough set theory; Beaubouef et al. [1] discussed rough entropy which is applied to rough sets in general; Dai et al. [8] thought about entropy measure in set-value ISs; Qian et al. [24] considered fuzzy information entropy and granularity; Li et al. [16] used four kinds of entropy to measure uncertainty in fuzzy relation IS; Zhang et al. [32] investigated uncertainty measures in a fully fuzzy IS.

In general, some attributes in the same IIVIS are redundant. we want to find a reduct that has the fewest attributes. Attribute selection in a given IIVIS mean deleting irrelevant or unimportant attributes under the condition of keeping the classification ability of this IIVIS. As one of the core contents of rough set theory, attribute selection has attracted a great deal of attention. For instance, Zhang et al. [33] put forward multi-confidence rule acquisition and confidence-preserved attribute selection in interval-valued decision systems. Yang et al. [31] discussed dominance-based rough set approach to IIVIS.

Given an IIVIS, we define tolerance relation based on similarity degree and put forward a rough set model based on this relation. The θ-discernibility matrix of this IIVIS can be obtained by the given threshold θ. Reduction algorithms based on θ-discernibility matrix, θ-information entropy and θ-significance in an IIVIS are proposed. And the work process is displayed in Fig. 1.

Fig. 1

The work process of the paper.

The rest of this article is designed as follows. Section 2 retrospects the essential notions of binary relations, interval numbers and IIVISs. Section 3 gives similarity degree and tolerance relations in an IIVIS. Section 4 investigates θ-reduction in an IIVIS and reveals connections between the proposed the proposed reduction and information entropy. Section 5 obtains three algorithms on θ-reduction in an IIVIS. Section 6 compares with reduction in other kinds of ISs and concludes this article.

2 Preliminaries

In this section, the essential notions of binary relations, interval numbers and IIVISs are reviewed.

In this article, U signifies the finite universe, 2^U expresses a set of all subsets of U and |X| means the number of elements in X ∈ 2^U.

Put

$U = {u_{1}, u_{2}, \dots, u_{n}},$ $δ = U \times U, ▵ = {(u, u) : u \in U} .$

2.1 Binary relations

R is said to be a binary relation on U whenever R ⊆ U × U. If (u, v) ∈ R, then uRv.

Let R be a binary relation on U. Then R is regarded as a universal relation on U whenever R = δ; R is regarded as an identity relation on U whenever R =▵.

Assume that R is a binary relation on U. Then R is referred to as an equivalence relation on U, if R meets:

(1) reflexive: ∀ u ∈ U, uRu;

(2) symmetric: ∀ u, v ∈ U, uRv implies vRu;

(3) transitive: ∀ u, v, w ∈ U, uRv and vRw imply uRw.

In addition, R is said to be a tolerance relation on U if it is reflexive and symmetric.

2.2 Interval-valued numbers

Let $[R] = {m = [m^{-}, m^{+}] : m^{-}, m^{+} \in R, m^{-} \leq m^{+}} .$

For any m ∈ R, express $\bar{m} = [m, m]$ .

For any m, n ∈ [R], define

(1) m = n ⇒ m^- = n^-, m⁺ = n⁺.

(2) m ≤ n ⇒ m^- ≤ n^-, m⁺ ≤ n⁺; m < n ⇒ m ≤ n, m ≠ n.

Definition 2.1 ([18, 19]). Let m, n ∈ [R]. Then the possible degree of m relative to n is defined as follows: $p (m, n) = \min {1, \max {\frac{m^{+} - n^{-}}{(m^{+} - m^{-}) + (n^{+} - n^{-})}, 0}} .$

Proposition 2.2 ([11, 19]). The following properties hold:

(1) ∀ m, n ∈ [R], 0 ≤ p (m, n) ≤1;

(2) ∀ m ∈ [R], p (m, m) =0.5;

(3) ∀ m, n ∈ [R], p (m, n) + p (n, m) =1.

Definition 2.3 ([10]). Let m, n ∈ [R]. Then the similarity degree of m and n is defined as follows: $q (m, n) = 1 - | p (m, n) - p (n, m) | .$

Proposition 2.4 ([10]) The following properties hold:

(1) ∀ m, n ∈ [R], q (m, n) = q (n, m);

(2) ∀ m, n ∈ [R], 0 ≤ q (m, n) ≤1;

(3) ∀ m, n ∈ [R], q (m, n) =1 ⇒ m = n.

Example 2.5 ([9]). Pick m = [4, 10] and n = [6, 9]. Then $p (m, n) = \min {1, \max {\frac{10 - 6}{(10 - 4) + (9 - 6)}, 0}} = \frac{4}{9},$ $p (n, m) = \min {1, \max {\frac{9 - 4}{(10 - 4) + (9 - 6)}, 0}} = \frac{5}{9},$ $q (m, n) = 1 - | p (m, n) - p (n, m) | = 1 - | \frac{4}{9} - \frac{5}{9} | = \frac{8}{9} .$

2.3 An IIVIS

Definition 2.6 ([20]). Let U be a finite set of objects. A expresses a finite set of attributes. Then the ordered pair (U, A) is referred to as an information system (IS), if a ∈ A is able to decide a function a : U → V_a, where V_a = {a (u) : u ∈ U}.

If (U, A) is an IS. Given B ⊆ A. Then we can define $ind (B) = {(u, v) \in U \times U : \forall a \in B, a (u) = a (v)} .$

Evident, ind (B) is an equivalence relation on U, ind (B) = ⋂ _a∈Bind ({a}) .

Denote $[u]_{B} = {v \in U : (u, v) \in ind (B)} .$ Then [u] _B is known as the equivalence class of the object u under the equivalence relation ind (B).

Definition 2.7 ([20]). Suppose that (U, A) is an IS. Then (U, A) is known as an incomplete information system (IIS), if there are u ∈ U and a ∈ A such that a (u) is missing.

We call (U, A) is an IIS. Given B ⊆ A. Then a binary relation on U can be defined as

sim (B) = {(u, v) ∈ U × U : ∀ a ∈ B, a (u) = a (v) or a (u) = * or a (v) = *} ,

here * is a missing value.Evident, sim (B) is a tolerance relation on U and sim (B) = ⋂ _a∈Bsim ({a}) .

Let (U, A) be an IIS. For each a ∈ A, denote $V_{a}^{*} = V_{a} - {a (u) : a (u) = *} .$

$V_{a}^{*}$ means the set of all non-missing information values of the attribute a.

Definition 2.8 ([29]). Let (U, A) be an IS. (U, A) called an interval-valued information system (IVIS), for ∀ a ∈ A and u ∈ U, a (u) is an interval.

Definition 2.9 ([29]). Consider that (U, A) is an IS. (U, A) called an incomplete interval-valued IS (IIVIS), if (U, A) is both incomplete and interval-valued.

If B ⊆ A, then (U, B) is known as the subsystem of (U, A).

Example 2.10. Table 1 depicts an IIVIS (U, A) where U = {u₁, u₂, ⋯ , u₁₀} and A = {a₁, a₂, ⋯ , a₆}.

Table 1
An IIVIS

a ₁ a ₂ a ₃ a ₄ a ₅ a ₆

u ₁ [68.75,80.79] [12.06,22.79] [51.52,77.06] [30.61,45.38] [70.11,81.16] [30.35,33.43]

u ₂ [75.71,81.46] [11.97,19.62] [64.77,80.64] [36.87,43.52] [77.54,80.59] [30.35,33.43]

u ₃ * [23.24,34.75] [51.52,77.06] [30.61,45.38] [70.11,81.16] [31.24,35.75]

u ₄ [75.71,81.46] [11.97,19.62] * [43.26,54.95] [77.54,80.59] [30.35,33.43]

u ₅ * [12.06,22.79] [51.52,77.06] * [77.54,80.59] [30.35,33.43]

u ₆ [68.75,80.79] [12.06,22.79] [64.77,80.64] [43.26,54.95] * *

u ₇ [75.71,81.46] [11.97,19.62] [51.52,77.06] [43.26,54.95] [70.11,81.16] [31.24,35.75]

u ₈ * [23.24,34.75] [51.52,77.06] [36.87,43.52] [70.11,81.16] [30.35,33.43]

u ₉ [75.71,81.46] [11.97,19.62] * [36.87,43.52] [77.54,80.59] [30.35,33.43]

u ₁₀ [75.71,81.46] [23.24,34.75] [64.77,80.64] [30.61,45.38] [77.54,80.59] [30.35,33.43]

u ₁₁ [68.75,80.79] [12.06,22.79] [64.77,80.64] [43.26,54.95] [70.11,81.16] [31.24,35.75]

u ₁₂ [75.71,81.46] [23.24,34.75] [64.77,80.64] [36.87,43.52] * [31.24,35.75]

	a ₁	a ₂	a ₃	a ₄	a ₅	a ₆
u ₁	[68.75,80.79]	[12.06,22.79]	[51.52,77.06]	[30.61,45.38]	[70.11,81.16]	[30.35,33.43]
u ₂	[75.71,81.46]	[11.97,19.62]	[64.77,80.64]	[36.87,43.52]	[77.54,80.59]	[30.35,33.43]
u ₃	*	[23.24,34.75]	[51.52,77.06]	[30.61,45.38]	[70.11,81.16]	[31.24,35.75]
u ₄	[75.71,81.46]	[11.97,19.62]	*	[43.26,54.95]	[77.54,80.59]	[30.35,33.43]
u ₅	*	[12.06,22.79]	[51.52,77.06]	*	[77.54,80.59]	[30.35,33.43]
u ₆	[68.75,80.79]	[12.06,22.79]	[64.77,80.64]	[43.26,54.95]	*	*
u ₇	[75.71,81.46]	[11.97,19.62]	[51.52,77.06]	[43.26,54.95]	[70.11,81.16]	[31.24,35.75]
u ₈	*	[23.24,34.75]	[51.52,77.06]	[36.87,43.52]	[70.11,81.16]	[30.35,33.43]
u ₉	[75.71,81.46]	[11.97,19.62]	*	[36.87,43.52]	[77.54,80.59]	[30.35,33.43]
u ₁₀	[75.71,81.46]	[23.24,34.75]	[64.77,80.64]	[30.61,45.38]	[77.54,80.59]	[30.35,33.43]
u ₁₁	[68.75,80.79]	[12.06,22.79]	[64.77,80.64]	[43.26,54.95]	[70.11,81.16]	[31.24,35.75]
u ₁₂	[75.71,81.46]	[23.24,34.75]	[64.77,80.64]	[36.87,43.52]	*	[31.24,35.75]

Example 2.11. (Continued from Example 2.10) $V_{a_{1}}^{*} = {, [75.71, 81.46]}, V_{a_{2}}^{*} = V_{a_{2}} = {[12.06, 22.79], [11.97, 19.62], [23.24, 34.75]}, V_{a_{3}}^{*} = {[51.52, 77.06], [64.77, 80.64]}, V_{a_{4}}^{*} = {[30.61, 45.38], [36.87, 43.52], [43.26, 54.95]}, V_{a_{5}}^{*} = {[70.11, 81.16], [77.54, 80.59]}, V_{a_{6}}^{*} = {[30.35, 33.43], [31.24, 35.75]} .$

3 Tolerance relations in an IIVIS

In this section, the concept of IIVIS was proposed, the similarity degree between two information values on a given attribute in an IIVIS is constructed and the tolerance relation induced by a given subsystem is given.

3.1 The similarity degree between information values on an attribute in an IIVIS

Definition 3.1. Suppose that (U, A) is an IIVIS. Then ∀ u, v ∈ U, a ∈ A, the similarity degree between a (u) and a (v) is defined as follows:

s (a (u) , a (v)) = ${\begin{matrix} 1 & u = v; \\ \frac{1}{| V_{a}^{*} |^{2}} & u \neq v, a (u) = *, a (v) = *; \\ \frac{1}{| V_{a}^{*} |} & u \neq v, a (u) \neq *, a (v) = *; \\ \frac{1}{| V_{a}^{*} |} & u \neq v, a (u) = *, a (v) \neq *; \\ 1 & u \neq v, a (u) \neq *, a (v) \neq *, a (u) = a (v); \\ q (a (u), a (v)) & u \neq v, a (u) \neq *, a (v) \neq *, a (u) \neq a (v) . \end{matrix}$

For the convenience of expression, denote $s_{ij}^{k} = s (a_{k} (u_{i}), a_{k} (u_{j})) .$

$s_{ij}^{k}$ indicates the similarity degree between a_k (u_i) and a_k (u_j). This also expresses the similarity degree between two objects u_i and u_j with respect to the attribute a_k.

Example 3.2. (Continued from Example 2.10) ∀ i, j, k, $s_{ij}^{k}$ is obtained as follows (see Tables 2 –7).

Table 2
$s_{ij}^{1}$

$s_{ij}^{1}$ u ₁ u ₂ u ₃ u ₄ u ₅ u ₆ u ₇ u ₈ u ₉ u ₁₀ u ₁₁ u ₁₂

u ₁ 1 0.57 0.5 0.57 0.5 1 0.57 0.5 0.57 0.57 1 0.57

u ₂ 0.57 1 0.5 1 0.5 0.57 1 0.5 1 1 0.57 1

u ₃ 0.5 0.5 1 0.5 0.25 0.5 0.5 0.25 0.5 0.5 0.5 0.5

u ₄ 0.57 1 0.5 1 0.5 0.57 1 0.5 1 1 0.57 1

u ₅ 0.5 0.5 0.25 0.5 1 0.5 0.5 0.25 0.5 0.5 0.5 0.5

u ₆ 1 0.57 0.5 0.57 0.5 1 0.57 0.5 0.57 0.57 1 0.57

u ₇ 0.57 1 0.5 1 0.5 0.57 1 0.5 1 1 0.57 1

u ₈ 0.5 0.5 0.25 0.5 0.25 0.5 0.5 1 0.5 0.5 0.5 0.5

u ₉ 0.57 1 0.5 1 0.5 0.57 1 0.5 1 1 0.57 1

u ₁₀ 0.57 1 0.5 1 0.5 0.57 1 0.5 1 1 0.57 1

u ₁₁ 1 0.57 0.5 0.57 0.5 1 0.57 0.5 0.57 0.57 1 0.57

u ₁₂ 0.57 1 0.5 1 0.5 0.57 1 0.5 1 1 0.57 1

$s_{ij}^{1}$	u ₁	u ₂	u ₃	u ₄	u ₅	u ₆	u ₇	u ₈	u ₉	u ₁₀	u ₁₁	u ₁₂
u ₁	1	0.57	0.5	0.57	0.5	1	0.57	0.5	0.57	0.57	1	0.57
u ₂	0.57	1	0.5	1	0.5	0.57	1	0.5	1	1	0.57	1
u ₃	0.5	0.5	1	0.5	0.25	0.5	0.5	0.25	0.5	0.5	0.5	0.5
u ₄	0.57	1	0.5	1	0.5	0.57	1	0.5	1	1	0.57	1
u ₅	0.5	0.5	0.25	0.5	1	0.5	0.5	0.25	0.5	0.5	0.5	0.5
u ₆	1	0.57	0.5	0.57	0.5	1	0.57	0.5	0.57	0.57	1	0.57
u ₇	0.57	1	0.5	1	0.5	0.57	1	0.5	1	1	0.57	1
u ₈	0.5	0.5	0.25	0.5	0.25	0.5	0.5	1	0.5	0.5	0.5	0.5
u ₉	0.57	1	0.5	1	0.5	0.57	1	0.5	1	1	0.57	1
u ₁₀	0.57	1	0.5	1	0.5	0.57	1	0.5	1	1	0.57	1
u ₁₁	1	0.57	0.5	0.57	0.5	1	0.57	0.5	0.57	0.57	1	0.57
u ₁₂	0.57	1	0.5	1	0.5	0.57	1	0.5	1	1	0.57	1

Table 3

$s_{ij}^{2}$

$s_{ij}^{2}$	u ₁	u ₂	u ₃	u ₄	u ₅	u ₆	u ₇	u ₈	u ₉	u ₁₀	u ₁₁	u ₁₂
u ₁	1	0.82	0	0.82	1	1	0.82	0	0.82	0	1	0
u ₂	0.82	1	0	1	0.82	0.82	1	0	1	0	0.82	0
u ₃	0	0	1	0	0	0	0	1	0	1	0	1
u ₄	0.82	1	0	1	0.82	0.82	1	0	1	0	0.82	0
u ₅	1	0.82	0	0.82	1	1	0.82	0	0.82	0	1	0
u ₆	1	0.82	0	0.82	1	1	0.82	0	0.82	0	1	0
u ₇	0.82	1	0	1	0.82	0.82	1	0	1	0	0.82	0
u ₈	0	0	1	0	0	0	0	1	0	1	0	1
u ₉	0.82	1	0	1	0.82	0.82	1	0	1	0	0.82	0
u ₁₀	0	0	1	0	0	0	0	1	0	1	0	1
u ₁₁	1	0.82	0	0.82	1	1	0.82	0	0.82	0	1	0
u ₁₂	0	0	1	0	0	0	0	1	0	1	0	1

Table 4

$s_{ij}^{3}$

$s_{ij}^{3}$	u ₁	u ₂	u ₃	u ₄	u ₅	u ₆	u ₇	u ₈	u ₉	u ₁₀	u ₁₁	u ₁₂
u ₁	1	0.59	1	0.5	1	0.59	1	1	0.5	0.59	0.59	0.59
u ₂	0.59	1	0.59	0.5	0.59	1	0.59	0.59	0.5	1	1	1
u ₃	1	0.59	1	0.5	1	0.59	1	1	0.5	0.59	0.59	0.59
u ₄	0.5	0.5	0.5	1	0.5	0.5	0.5	0.5	0.25	0.5	0.5	0.5
u ₅	1	0.59	1	0.5	1	0.59	1	1	0.5	0.59	0.59	0.59
u ₆	0.59	1	0.59	0.5	0.59	1	0.59	0.59	0.5	1	1	1
u ₇	1	0.59	1	0.5	1	0.59	1	1	0.5	0.59	0.59	0.59
u ₈	1	0.59	1	0.5	1	0.59	1	1	0.5	0.59	0.59	0.59
u ₉	0.5	0.5	0.5	0.25	0.5	0.5	0.5	0.5	1	0.5	0.5	0.5
u ₁₀	0.59	1	0.59	0.5	0.59	1	0.59	0.59	0.5	1	1	1
u ₁₁	0.59	1	0.59	0.5	0.59	1	0.59	0.59	0.5	1	1	1
u ₁₂	0.59	1	0.59	0.5	0.59	1	0.59	0.59	0.5	1	1	1

Table 5

$s_{ij}^{4}$

$s_{ij}^{4}$	u ₁	u ₂	u ₃	u ₄	u ₅	u ₆	u ₇	u ₈	u ₉	u ₁₀	u ₁₁	u ₁₂
u ₁	1	0.79	1	0.16	0.33	0.16	0.16	0.79	0.79	1	0.16	0.79
u ₂	0.79	1	0.79	0.03	0.33	0.03	0.03	1	1	0.79	0.03	1
u ₃	1	0.79	1	0.16	0.33	0.16	0.16	0.79	0.79	1	0.16	0.79
u ₄	0.16	0.03	0.16	1	0.33	1	1	0.03	0.03	0.16	1	0.03
u ₅	0.33	0.33	0.33	0.33	1	0.33	0.33	0.33	0.33	0.33	0.33	0.33
u ₆	0.16	0.03	0.16	1	0.33	1	1	0.03	0.03	0.16	1	0.03
u ₇	0.16	0.03	0.16	1	0.33	1	1	0.03	0.03	0.16	1	0.03
u ₈	0.79	1	0.79	0.03	0.33	0.03	0.03	1	1	0.79	0.03	1
u ₉	0.79	1	0.79	0.03	0.33	0.03	0.03	1	1	0.79	0.03	1
u ₁₀	1	0.79	1	0.16	0.33	0.16	0.16	0.79	0.79	1	0.16	0.79
u ₁₁	0.16	0.03	0.16	1	0.33	1	1	0.03	0.03	0.16	1	0.03
u ₁₂	0.79	1	0.79	0.03	0.33	0.03	0.03	1	1	0.79	0.03	1

Table 6

$s_{ij}^{5}$

$s_{ij}^{5}$	u ₁	u ₂	u ₃	u ₄	u ₅	u ₆	u ₇	u ₈	u ₉	u ₁₀	u ₁₁	u ₁₂
u ₁	1	0.51	1	0.51	0.51	0.5	1	1	0.51	0.51	1	0.5
u ₂	0.51	1	0.51	1	1	0.5	0.51	0.51	1	1	0.51	0.5
u ₃	1	0.51	1	0.51	0.51	0.5	1	1	0.51	0.51	1	0.5
u ₄	0.51	1	0.51	1	1	0.5	0.51	0.51	1	1	0.51	0.5
u ₅	0.51	1	0.51	1	1	0.5	0.51	0.51	1	1	0.51	0.5
u ₆	0.5	0.5	0.5	0.5	0.5	1	0.5	0.5	0.5	0.5	0.5	0.25
u ₇	1	0.51	1	0.51	0.51	0.5	1	1	0.51	0.51	1	0.5
u ₈	1	0.51	1	0.51	0.51	0.5	1	1	0.51	0.51	1	0.5
u ₉	0.51	1	0.51	1	1	0.5	0.51	0.51	1	1	0.51	0.5
u ₁₀	0.51	1	0.51	1	1	0.5	0.51	0.51	1	1	0.51	0.5
u ₁₁	1	0.51	1	0.51	0.51	0.5	1	1	0.51	0.51	1	0.5
u ₁₂	0.5	0.5	0.5	0.5	0.5	0.25	0.5	0.5	0.5	0.5	0.5	1

Table 7

$s_{ij}^{6}$

$s_{ij}^{6}$	u ₁	u ₂	u ₃	u ₄	u ₅	u ₆	u ₇	u ₈	u ₉	u ₁₀	u ₁₁	u ₁₂
u ₁	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₂	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₃	0.58	0.58	1	0.58	0.58	0.5	1	0.58	0.58	0.58	1	1
u ₄	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₅	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₆	0.5	0.5	0.5	0.5	0.5	1	0.5	0.5	0.5	0.5	0.5	0.5
u ₇	0.58	0.58	1	0.58	0.58	0.5	1	0.58	0.58	0.58	1	1
u ₈	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₉	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₁₀	1	1	0.58	1	1	0.5	0.58	1	1	1	0.58	0.58
u ₁₁	0.58	0.58	1	0.58	0.58	0.5	1	0.58	0.58	0.58	1	1
u ₁₂	0.58	0.58	1	0.58	0.58	0.5	1	0.58	0.58	0.58	1	1

3.2 Tolerance relations in an IIVIS

Definition 3.3. Consider that (U, A) is an IIVIS. Given θ ∈ (0, 1] and B ⊆ A. Then a binary relation on U can be defined as follows: $R_{B}^{θ} = {(u, v) \in U \times U : \forall a \in B, s (a (u), a (v)) \geq θ} .$

Obviously, $R_{B}^{θ}$ is a tolerance relation on U and $R_{B}^{θ} = ⋂_{a \in B} R_{{a}}^{θ}$ .

$R_{{a}}^{θ}$ can be briefly expressed as $R_{a}^{θ}$ .

Proposition 3.4. Let (U, A) be an IIVIS. We can get the following properties.

(1) If B₁ ⊆ B₂ ⊆ A, then ∀ θ ∈ (0, 1], $R_{B_{2}}^{θ} \subseteq R_{B_{1}}^{θ};$

(2) If 0 ≤ θ₁ ≤ θ₂ ≤ 1, then ∀ B ⊆ A, $R_{B}^{θ_{2}} \subseteq R_{B}^{θ_{1}} .$

Proof. These are clear.□

Corollary 3.5. Assume that (U, A) is an IIVIS. If C ⊆ B ⊆ A and 0 ≤ θ₁ ≤ θ₂ ≤ 1, then $R_{B}^{θ_{2}} \subseteq R_{C}^{θ_{1}}$ .

Proof. This can be obtained from Proposition 3.4.□

Proposition 3.6. Suppose that (U, A) is an IIVIS. Then ∀ B, C ⊆ A and θ ∈ (0, 1], $R_{B}^{θ} \cap R_{C}^{θ} = R_{B \cup C}^{θ}$ .

Proof. “⇒” $\forall (u, v) \in R_{B}^{θ} \cap R_{C}^{θ},$ then $(u, v) \in R_{B}^{θ}$ and $(u, v) \in R_{C}^{θ}$ .

By Definition 3.3, we have

∀ a ∈ B, s (a (u) , a (v)) ≥ θ and ∀ a ∈ C, s (a (u) , a (v)) ≥ θ.

Then ∀ a ∈ B ∪ C, s (a (u) , a (v)) ≥ θ. By Definition 3.3, $(u, v) \in R_{B \cup C}^{θ}$ .

Consequently, $R_{B}^{θ} \cap R_{C}^{θ} \subseteq R_{B \cup C}^{θ}$ .

“ ⇐ " Owing to B ⊆ B ∪ C and C ⊆ B ∪ C, by Proposition 3.4, $R_{B \cup C}^{θ} \subseteq R_{B}^{θ}$ and $R_{B \cup C}^{θ} \subseteq R_{C}^{θ}$ . So $R_{B \cup C}^{θ} \subseteq R_{B}^{θ} \cap R_{C}^{θ}$ .□

Definition 3.7. Let (U, A) be an IIVIS. Given θ ∈ (0, 1] and B ⊆ A. Then the tolerance class of the object u ∈ U under the tolerance relation $R_{B}^{θ}$ is defined as $R_{B}^{θ} (u) = {v \in U : (u, v) \in R_{B}^{θ}} .$

Clearly, $R_{B}^{θ} (u) = ⋂_{a \in B} R_{a}^{θ} (u) .$

In addition, put $U / R_{B}^{θ} = {R_{B}^{θ} (u) : u \in U}$

Corollary 3.8. Suppose that (U, A) is an IIVIS.

(1) If C ⊆ B ⊆ A, then ∀ θ ∈ (0, 1] and u ∈ U, $R_{B}^{θ} (u) \subseteq R_{C}^{θ} (u)$ .

(2) If 0 ≤ θ₁ ≤ θ₂ ≤ 1, then ∀ B ⊆ A and u ∈ U, $R_{B}^{θ_{2}} (u) \subseteq R_{B}^{θ_{1}} (u)$ .

Proof. These can be obtained from Proposition 3.4. □

Corollary 3.9. Given that (U, A) is an IIVIS. If C ⊆ B ⊆ A, 0 ≤ θ₁ ≤ θ₂ ≤ 1 and u ∈ U, then $R_{B}^{θ_{2}} (u) \subseteq R_{C}^{θ_{1}} (u)$ .

Proof. This can be received by Corollary 3.8.□

Corollary 3.10. Consider that (U, A) is an IIVIS. Then ∀ B, C ⊆ A, θ ∈ (0, 1] and u ∈ U, $R_{B}^{θ} (u) \cap R_{C}^{θ} (u) = R_{B \cup C}^{θ} (u)$ .

Proof. This can be received from Proposition 3.6.□

Example 3.11. (Continued from Example 3.2)

Pick θ = 0.6. Then ∀ i, ∀ u ∈ U, the tolerance class $R_{a_{i}}^{θ} (u)$ of the object u under the tolerance relation $R_{a_{i}}^{θ}$ is obtained (see Tables 8, 9).

Table 8
$R_{a_{i}}^{θ} (u)$ (i = 1, 2, 3, θ = 0.6, u ∈ U)

$R_{a_{1}}^{θ} (u)$ $R_{a_{2}}^{θ} (u)$ $R_{a_{3}}^{θ} (u)$

u1 { u1,u6,u11} { u1,u2,u4,u5,u6,u7,u9,u11} { u1,u3,u5,u7,u8}

u2 { u2,u4,u7,u9,u10,u12} { u1,u2,u4,u5,u6,u7,u9,u11} { u2,u6,u10,u11,u12}

u3 { u3 } { u3,u8,u10,u12} { u1,u3,u5,u7,u8 }

u4 { u2,u4,u7,u9,u10,u12} { u1,u2,u4,u5,u6,u7,u9,u11} { u4 }

u5 { u5 } { u1,u2,u4,u5,u6,u7,u9,u11} { u1,u3,u5,u7,u8 }

u6 { u1,u6,u11} { u1,u2,u4,u5,u6,u7,u9,u11} { u2,u6,u10,u11,u12}

u7 { u2,u4,u7,u9,u10,u12} { u1,u2,u4,u5,u6,u7,u9,u11} { u1,u3,u5,u7,u8 }

u8 { u8 } { u3,u8,u10,u12} { u1,u3,u5,u7,u8 }

u9 { u2,u4,u7,u9,u10,u12} { u1,u2,u4,u5,u6,u7,u9,u11} { u9 }

u10 { u2,u4,u7,u9,u10,u12} { u3,u8,u10,u12} { u2,u6,u10,u11,u12}

u11 { u1,u6,u11} { u1,u2,u4,u5,u6,u7,u9,u11} { u2,u6,u10,u11,u12}

u12 { u2,u4,u7,u9,u10,u12} { u3,u8,u10,u12} { u2,u6,u10,u11,u12}

	$R_{a_{1}}^{θ} (u)$	$R_{a_{2}}^{θ} (u)$	$R_{a_{3}}^{θ} (u)$
u1	{ u1,u6,u11}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u1,u3,u5,u7,u8}
u2	{ u2,u4,u7,u9,u10,u12}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u2,u6,u10,u11,u12}
u3	{ u3 }	{ u3,u8,u10,u12}	{ u1,u3,u5,u7,u8 }
u4	{ u2,u4,u7,u9,u10,u12}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u4 }
u5	{ u5 }	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u1,u3,u5,u7,u8 }
u6	{ u1,u6,u11}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u2,u6,u10,u11,u12}
u7	{ u2,u4,u7,u9,u10,u12}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u1,u3,u5,u7,u8 }
u8	{ u8 }	{ u3,u8,u10,u12}	{ u1,u3,u5,u7,u8 }
u9	{ u2,u4,u7,u9,u10,u12}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u9 }
u10	{ u2,u4,u7,u9,u10,u12}	{ u3,u8,u10,u12}	{ u2,u6,u10,u11,u12}
u11	{ u1,u6,u11}	{ u1,u2,u4,u5,u6,u7,u9,u11}	{ u2,u6,u10,u11,u12}
u12	{ u2,u4,u7,u9,u10,u12}	{ u3,u8,u10,u12}	{ u2,u6,u10,u11,u12}

Table 9

$R_{a_{i}}^{θ} (u)$ (i = 4, 5, 6, θ = 0.6, u ∈ U)

	$R_{a_{4}}^{θ} (u)$	$R_{a_{5}}^{θ} (u)$	$R_{a_{6}}^{θ} (u)$
u ₁	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₁, u₃, u₇, u₈, u₁₁}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₂	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₂, u₄, u₅, u₉, u₁₀}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₃	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₁, u₃, u₇, u₈, u₁₁}	{u₃, u₇, u₁₁, u₁₂}
u ₄	{u₄, u₆, u₇, u₁₁}	{u₂, u₄, u₅, u₉, u₁₀}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₅	{u₅}	{u₂, u₄, u₅, u₉, u₁₀}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₆	{u₄, u₆, u₇, u₁₁}	{u₆}	{u₆}
u ₇	{u₄, u₆, u₇, u₁₁}	{u₁, u₃, u₇, u₈, u₁₁}	{u₃, u₇, u₁₁, u₁₂}
u ₈	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₁, u₃, u₇, u₈, u₁₁}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₉	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₂, u₄, u₅, u₉, u₁₀}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₁₀	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₂, u₄, u₅, u₉, u₁₀}	{u₁, u₂, u₄, u₅, u₈, u₉, u₁₀}
u ₁₁	{u₄, u₆, u₇, u₁₁}	{u₁, u₃, u₇, u₈, u₁₁}	{u₃, u₇, u₁₁, u₁₂}
u ₁₂	{u₁, u₂, u₃, u₈, u₉, u₁₀, u₁₂}	{u₁₂}	{u₃, u₇, u₁₁, u₁₂}

An algorithm for computing the tolerance class is designed as follows.

4 Attribute selection approaches for an IIVIS

4.1 θ-reduction, θ-core and θ-discernibility matrix in an IIVIS

Given an IIVIS (U, A), each subset B of A determines a tolerance relation (or indiscernibility relation) $R_{B}^{θ}$ .

Definition 4.1. Consider that (U, A) is an IIVIS. Given B ⊆ A and θ ∈ (0, 1].

(1) B is called θ-coordinate subset of A, if $R_{A}^{θ} = R_{B}^{θ}$ ;

(2) a ∈ B is called θ-independent in B, if $R_{B - {a}}^{θ} \neq R_{B}^{θ}$ ; B is called a θ-independent subset of A, if for each a ∈ B, a is θ-independent in B;

(3) B is called a θ-reduct of A, if B is called θ-coordinate subset of A and B is θ-independent.

“ $R_{A}^{θ} = R_{B}^{θ}$ " means that the subsystem (U, B) has the same classification ability as the system (U, A) with respect to a given θ.

In this paper, the family of all θ-coordinate subsets (resp., θ-reducts) of A is denoted by co^θ (A) (resp., red^θ (A)).

Obviously,

$\begin{matrix} B \in {red}^{θ} (A) \Leftrightarrow B \in {co}^{θ} (A), \forall a \in B, \\ B - {a} \notin {co}^{θ} (A) . \end{matrix}$

On the base of the previous analysis, B ∈ red^θ (A) means that B is a minimal attribute subset where the subsystem (U, B) has the same classification ability as the system (U, A) with respect to a given θ.

Proposition 4.2. Assume that (U, A) is an IIVIS. Given θ ∈ (0, 1]. Then there always exists a θ-reduct of A.

Proof. Suppose that ∀ a ∈ A, A - {a} ∉ co^θ (A). Then A ∈ red^θ (A).

Suppose that ∃ a₁ ∈ A, A - {a₁} ∈ co^θ (A). Then, we consider A - {a₁}. Again suppose that ∀ a ∈ A - {a₁}, (A - {a₁}) - {a} ∉ co^θ (A). Then A - {a₁} ∈ red^θ (A). Again suppose that ∃ a₂ ∈ A - {a₁}, (A - {a₁}) - {a₂} ∈ co^θ (A). Then, we consider A - {a₁, a₂}. Repeat this process. Since A is finite, we can find a θ-reduct of A.

Thus, there always exists a θ-reduct of A.□

Definition 4.3. Given that (U, A) is an IIVIS. Put θ ∈ (0, 1] ${core}^{θ} (A) = ⋂_{B \in {red}^{θ} (A)} B .$ Then core^θ (A) is called the θ-core of A. Moreover,

(1) a ∈ A is called a necessary θ-attribute, if a ∈ core^θ (A).

(2) a ∈ A is called a relatively necessary θ-attribute, if a ∈ ⋃ _{B∈red^θ(A)}B - core^θ (A).

(3) a ∈ A is called an unnecessary θ-attribute, if a ∈ A - ⋃ _{B∈red^θ(A)}B.

Definition 4.4. Suppose that (U, A) is an IIVIS. For any u, v ∈ U and θ ∈ (0, 1], put $D^{θ} (u, v) = {a \in A : s (a (u), a (v)) < θ} .$ Then

(1) D^θ (u, v) is called the θ-discernibility set on u and v.

(2) ^Dθ (A) = (d_ij) _n×n is called the θ-discernibility matrix where U = {u₁, u₂, ·· · , u_n} and d_ij = D^θ (u_i, u_j) (1 ≤ i, j ≤ n).

Example 4.5. (Continued from Example 2.10)

Pick θ = 0.6, ^Dθ (A) of A is obtained as follows:

$\begin{matrix} (\begin{matrix} \tilde{\emptyset} & {a_{1}, a_{3}, a_{5}} & {a_{1}, a_{2}, a_{6}} & {a_{1}, a_{3}, a_{4}, a_{5}} \\ \emptyset & A - {a_{4}} & {a_{3}, a_{4}} \\ \emptyset & A \\ \emptyset \end{matrix} \\ \begin{matrix} {a_{1}, a_{4}, a_{5}} & {a_{3}, a_{4}, a_{5}, a_{6}} & {a_{1}, a_{4}, a_{6}} & {a_{1}, a_{2}} \\ {a_{1}, a_{3}, a_{4}} & {a_{1}, a_{4}, a_{5}, a_{6}} & {a_{3}, a_{4}, a_{5}, a_{6}} & {a_{1}, a_{2}, a_{3}, a_{5}} \\ A - {a_{3}} & A & {a_{1}, a_{2}, a_{4}} & {a_{1}, a_{6}} \\ {a_{1}, a_{3}, a_{4}} & {a_{1}, a_{3}, a_{5}, a_{6}} & {a_{3}, a_{5}, a_{6}} & A - {a_{6}} \\ \emptyset & A - {a_{2}} & {a_{1}, a_{4}, a_{5}, a_{6}} & {a_{1}, a_{2}, a_{4}, a_{5}} \\ \emptyset & {a_{1}, a_{3}, a_{5}, a_{6}} & A \\ \emptyset & {a_{1}, a_{2}, a_{4}, a_{6}} \\ \emptyset \end{matrix} \\ \begin{matrix} {a_{1}, a_{3}, a_{5}} & {a_{1}, a_{2}, a_{3}, a_{5}} & {a_{3}, a_{4}, a_{6}} & A - {a_{4}} \\ {a_{3}} & {a_{2}} & {a_{1}, a_{4}, a_{5}, a_{6}} & {a_{2}, a_{5}, a_{6}} \\ A - {a_{4}} & {a_{1}, a_{3}, a_{5}, a_{6}} & {a_{1}, a_{2}, a_{3}, a_{4}} & {a_{1}, a_{3}, a_{5}} \\ {a_{3}, a_{4}} & {a_{2}, a_{3}, a_{4}} & {a_{1}, a_{3}, a_{5}, a_{6}} & A - {a_{1}} \\ {a_{1}, a_{3}, a_{4}} & {a_{1}, a_{2}, a_{3}, a_{4}} & A - {a_{2}} & A \\ A - {a_{2}} & A - {a_{3}} & {a_{5}, a_{6}} & A - {a_{3}} \\ {a_{3}, a_{4}, a_{5}, a_{6}} & A - {a_{1}} & {a_{1}, a_{3}} & {a_{2}, a_{3}, a_{4}, a_{5}} \\ {a_{1}, a_{2}, a_{3}, a_{5}} & {a_{1}, a_{3}, a_{5}} & A - {a_{5}} & {a_{1}, a_{3}, a_{5}, a_{6}} \\ \emptyset & {a_{2}, a_{3}} & A - {a_{2}} & {a_{2}, a_{3}, a_{5}, a_{6}} \\ \emptyset & A - {a_{3}} & {a_{5}, a_{6}} \\ \emptyset & {a_{1}, a_{2}, a_{4}, a_{5}} \\ \emptyset \end{matrix}) \end{matrix}$

4.2 Some properties

Proposition 4.6. Given that (U, A) is an IIVIS. Then for any u, v, w ∈ U and θ ∈ (0, 1],

(1) D^θ (u, u) =∅.

(2) D^θ (u, v) = D^θ (v, u).

(3) D^θ (u, v) ⊆ D^θ (u, w) ∪ D^θ (w, v).

Proof. (1) and (2) are obvious.

(3) Suppose that D^θ (u, v) ⊊ D^θ (u, w) ∪ D^θ (w, v). Then D^θ (u, v) - D^θ (u, w)∪ D^θ (w, v) ≠ ∅. Pick $a \in D^{θ} (u, v) - D^{θ} (u, w) \cup D^{θ} (w, v) .$

a ∈ D^θ (u, v) implies $(u, v) \notin R_{a}^{θ}$ .

Since a ∉ D^θ (u, w) ∪ D^θ (w, v), we have a ∉ D^θ (u, w) and a ∉ D^θ (w, v). Then $(u, w) \in R_{a}^{θ}$ and $(w, v) \in R_{a}^{θ}$ .

Consequently, D^θ (u, v) ⊆ D^θ (u, w) ∪ D^θ (w, v). □

Corollary 4.7. Let (U, A) be an IIVIS. Then for any u, v ∈ U and θ ∈ (0, 1]. Then d is a distance function on U where $d (u, v) = | D^{θ} (u, v) | .$

Proof. This holds by Proposition 4.6.□

Proposition 4.8. Assume that (U, A) is an IIVIS. Given θ ∈ (0, 1]. Then

$B \in {co}^{θ} (A) \Rightarrow if (u, v) \notin R_{A}^{θ}, then B \cap D^{θ} (u, v) \neq \emptyset .$

Proof. “⇒". Let $(u, v) \notin R_{A}^{θ}$ . Since B ∈ co^θ (A), we have $R_{B}^{θ} = R_{A}^{θ} .$ Then $(u, v) \notin R_{B}^{θ} .$ So there exists a ∈ B such that s (a (u) , a (v)) < θ. This implies a ∈ D^θ (u, v). Then a ∈ B ∩ D^θ (u, v).

Consequently, B ∩ D^θ (u, v) ≠ ∅ .

“⇐". Suppose B ∉ co^θ (A). Then $R_{B}^{θ} \neq R_{A}^{θ} .$ This implies $R_{B}^{θ} - R_{A}^{θ} \neq \emptyset .$ Pick $(u, v) \in R_{B}^{θ} - R_{A}^{θ} .$

Since $(u, v) \notin R_{A}^{θ}$ , we have B ∩ D^θ (u, v) ≠ ∅ .

Note that $(u, v) \in R_{B}^{θ}$ . Then for each a ∈ B, s (a (u) , a (v)) ≥ θ. So a ∉ D^θ (u, v) . Consequently, B ∩ D^θ (u, v) = ∅ . This is a contradiction.

Hence B ∈ co^θ (A).□

θ-discernibility sets can easily determine θ-reduction.

Theorem 4.9. Let (U, A) be an IIVIS. Then for any u, v ∈ U and θ ∈ (0, 1],

B ∈ red^θ (A) ⇒ (i) if $(u, v) \notin R_{A}^{θ}$ , then B∩ D^θ (u, v) ≠ ∅ ;

(ii) ∀ a ∈ B, $\exists (u_{a}, v_{a}) \in R_{A}^{θ}$ , (B - {b})∩ D^θ (u_a, v_a) = ∅.

Proof. This holds by Proposition 4.8.□

Proposition 4.10. Assume that (U, A) is an IIVIS. Given θ ∈ (0, 1], $| {red}^{θ} (A) | = 1 \Rightarrow {core}^{θ} (A) \in {red}^{θ} (A) .$

Proof. “⇒" is obvious.

“⇐". Denote red^θ (A) = {B_k : 1 ≤ k ≤ n}. We only need to prove n = 1.

Suppose n ≥ 2. Since core^θ (A) ∈ red^θ (A), there exists i such that core^θ (A) = B_i. Pick j ≠ i. Then $B_{i} = ⋂_{k = 1}^{n} B_{k} \subseteq B_{j}$ . Put B_i ≠ B_j. Consequently, B_i ⊂ B_j. Since B_j ∈ red^θ (A), we have B_i ∉ co^θ (A). Then B_i ∉ red^θ (A). This is a contradiction.

Thus n = 1.□

θ-discernibility sets can easily determine the θ-core.

Proposition 4.11. Provided that (U, A) is an IIVIS. Put θ ∈ (0, 1]. Then the following conditions are equivalent:

(1) a is a necessary θ-attribute;

(2) a is θ-independent in A;

(3) ∃ u, v ∈ U, D^θ (u, v) = {a}.

Proof.

(1) ⇒ (2). Let a be a necessary θ-attribute. Suppose that a is not θ-independent in A. Then $R_{A - {a}}^{θ} = R_{A}^{θ} .$ This implies A - {a} ∈ co^θ (A). Consider A - {a}, by Proposition 4.2, ∃ B ⊆ A - {a}, B ∈ red^θ (A).

B ⊆ A - {a} implies a ∉ B. Then a is not a necessary θ-attribute. This is a contradiction.

(2) ⇒ (1). Let a be θ-independent in A. Suppose that a is not a necessary θ-attribute. Then ∃ B ∈ red^θ (A), a ∉ B. So B ⊆ A - {a} ⊆ A. This implies $R_{B}^{θ} \supseteq R_{A - {a}}^{θ} \supseteq R_{A}^{θ} .$

Since B ∈ red^θ (A), we have $R_{B}^{θ} = R_{A}^{θ}$ . Then $R_{A - {a}}^{θ} = R_{A}^{θ} .$ So a is not θ-independent in A. This is a contradiction.

(2) ⇒ (3). Since a is θ-independent in A, we have $R_{A - {a}}^{θ} \neq R_{A}^{θ}$ . Then $R_{A - {a}}^{θ} - R_{A}^{θ} \neq \emptyset$ . Pick $(u, v) \in R_{A - {a}}^{θ} - R_{A}^{θ} .$ Denote A = {a₁, a₂, …, a_n}. Then ∃ j, a = a_j. So $(u, v) \in ⋂_{1 \leq i \leq n, i \neq j} R_{a_{i}}^{θ} - ⋂_{1 \leq i \leq n} R_{a_{i}}^{θ} .$ This implies that $(u, v) \notin R_{a_{j}}^{θ}$ and $(u, v) \in R_{a_{i}}^{θ} (i \neq j) .$

Then a_j ∈ D^θ (u, v), a_i ∉ D^θ (u, v) (i ≠ j) .

Consequently, D^θ (u, v) = {a_j} = {a}.

(3) ⇒ (2). Since ∃ u, v ∈ U, D^θ (u, v) = {a}, we have $(u, v) \notin R_{a}^{θ}, (u, v) \in R_{{a^{'}}}^{θ} (a^{'} \neq a) .$

Then $(u, v) \in R_{A - {a}}^{θ}$ . But $(u, v) \notin R_{A}^{θ}$ .

Consequently, $R_{A - {a}}^{θ} \neq R_{A}^{θ} .$ Hence a is θ-independent in A.□

Proposition 4.12. Let (U, A) be an IIVIS. Given a ∈ A and θ ∈ (0, 1]. Denote $Γ (a) = ⋃_{B \in {co}^{θ} (A)} R_{B - {a}}^{θ} .$ Then the following conditions are equivalent:

(1) a is an unnecessary θ-attribute;

(2) ∀ B ∈ co^θ (A), B - {a}∈ co^θ (A) ;

(3) $Γ (a) = R_{A}^{θ}$ ;

(4) $Γ (a) \subseteq R_{a}^{θ}$ .

Proof.

(1) ⇒ (2). Given B ∈ co^θ (A). By Proposition 4.2, ∃ C ⊆ B, C ∈ red^θ (A). Since a is an unnecessary θ-attribute, we have a ∉ C, which implies C ⊆ A - {a}. Then $C \subseteq B \cap (A - {a}) = B - {a} \subseteq B .$ We have $R_{C}^{θ} \supseteq R_{B - {a}}^{θ} \supseteq R_{B}^{θ} .$

Note that B ∈ co^θ (A) and C ∈ red^θ (A). Then $R_{B}^{θ} = R_{A}^{θ} = R_{C}^{θ}$ .

Consequently, $R_{B - {a}}^{θ} = R_{A}^{θ} .$

Hence B - {a} ∈ co^θ (A) .

(2) ⇒ (3) ⇒ (4) are obvious.

(4) ⇒ (1). Suppose that a is not an unnecessary θ-attribute. Then ∃ B ∈ red^θ (A), a ∈ B. This implies B - {a} ⊂ B. Since B ∈ red^θ (A), we have B - {a} ∉ co^θ (A). Then $R_{B - {a}}^{θ} - R_{A}^{θ} \neq \emptyset .$ B ∈ red^θ (A) implies $R_{B}^{θ} = R_{A}^{θ}$ . Then $R_{B - {a}}^{θ} - R_{B}^{θ} \neq \emptyset .$

Pick $(u, v) \in R_{B - {a}}^{θ} - R_{B}^{θ}$ . Note that $R_{B}^{θ} = R_{B - {a}}^{θ} \cap R_{a}^{θ}$ . Then $(u, v) \notin R_{a}^{θ}$ .

Since B ∈ co^θ (A) and $Γ (a) \subseteq R_{a}^{θ}$ , we have $R_{B - {a}}^{θ} \subseteq R_{a}^{θ}$ . Then $(u, v) \in R_{a}^{θ}$ . This is a contradiction.□

Theorem 4.13. Given that (U, A) is an IIVIS. Put θ ∈ (0, 1]. Then

(1) a is a necessary θ-attribute ⇒ A - {a} ∉ co^θ (A).

(2) a is a relatively necessary θ-attribute ⇒ A - {a} ∈ co^θ (A), $Γ (a) ⊊ R_{a}^{θ}$ .

(3) a is an unnecessary θ-attribute ⇒ ∀ B ∈ co^θ (A), B - {a} ∈ co^θ (A) .

Proof. These can be obtained by Propositions 4.11 and 4.12.□

Example 4.14. (Continued from Example 4.5)

Pick θ = 0.6, we have

(1) a₂, a₃ are two necessary θ-attributes.

(2) a₁, a₄, a₅ and a₆ are four relatively necessary θ-attributes.

4.3 Entropy measurement for an IIVIS

Definition 4.15. Suppose that (U, A) is an IIVIS. Given B ⊆ A and θ ∈ (0, 1]. Then θ-information entropy of the subsystem (U, B) with respect to θ is defined as $H^{θ} (B) = - \sum_{i = 1}^{n} \frac{1}{n} {log}_{2} \frac{| R_{B}^{θ} (x_{i}) |}{n} .$

Proposition 4.16. Assume that (U, A) is an IIVIS. Given B ⊆ A and θ ∈ (0, 1]. Then $0 \leq H^{θ} (B) \leq {log}_{2} n .$ Moreover, if $R_{B}^{θ}$ is a universal relation on U, then H^θ achieves the minimum value 0; if $R_{B}^{θ}$ is an identity relation on U, then H^θ achieves the maximum value log ₂n.

Proof. Since ∀ i, $1 \leq | R_{B}^{θ} (x_{i}) | \leq n$ , we have $0 \leq - {log}_{2} \frac{| R_{B}^{θ} (x_{i}) |}{n} \leq {log}_{2} n .$

By Definition 4.15, $0 \leq H^{θ} (B) \leq \log_{2} n .$

If $R_{B}^{θ}$ is an identity relation on U, then ∀ i, $| R_{B}^{θ} (x_{i}) | = 1$ . So H^θ (B) = log₂n.

If $R_{B}^{θ}$ is a universal relation on U, then ∀ i, $| R_{B}^{θ} (x_{i}) | = n$ . So H^θ (B) =0.□

Proposition 4.17. Assume that (U, A) is an IIVIS.

(1) If B₁ ⊆ B₂ ⊆ A, then for any θ ∈ (0, 1], H^θ (B₁) ≤ H^θ (B₂).

(2) If 0 < θ₁ ≤ θ₂ ≤ 1, then for any B ⊆ A, H^{θ
₁} (B) ≤ H^{θ
₂} (B).

Proof. These follow from Proposition 3.4.□

Theorem 4.18. Let (U, A) be an IIVIS. Given θ ∈ (0, 1] and B ⊆ A. Then $B \in co (A) \Leftrightarrow H^{θ} (B) = H^{θ} (A) .$

Proof. (1) ⇒ (2). This is obvious.

(2) ⇒ (1). Suppose H^θ (B) = H^θ (A). Then, we have $- \sum_{i = 1}^{n} \frac{1}{n} {log}_{2} \frac{| R_{B}^{θ} (x_{i}) |}{n} = - \sum_{i = 1}^{n} \frac{1}{n} {log}_{2} \frac{| R_{A}^{θ} (x_{i}) |}{n} .$

So $\sum_{i = 1}^{n} {log}_{2} \frac{| R_{B}^{θ} (x_{i}) |}{| R_{A}^{θ} (x_{i}) |} = 0 .$

Note that $R_{A}^{θ} \subseteq R_{B}^{θ}$ . Then ∀ i, $R_{A}^{θ} (x_{i}) \subseteq R_{B}^{θ} (x_{i})$ . This implies that $\forall i, {log}_{2} \frac{| R_{B}^{θ} (x_{i}) |}{| R_{A}^{θ} (x_{i}) |} \geq 0 .$

So ∀ i, ${log}_{2} \frac{| R_{B}^{θ} (x_{i}) |}{| R_{A}^{θ} (x_{i}) |} = 0 .$

This implies that ∀ i, $| R_{A}^{θ} (x_{i}) | = | R_{B}^{θ} (x_{i}) |$ .

Consequently, R_B = R_A .

Hence $B \in co (A) .$

(1) ⇒ (3). This is clear.

(3) ⇒ (1). The proof is similar to (2) ⇒ (1).□

Theorem 4.19. Let (U, A) be an IIVIS. Given θ ∈ (0, 1] and B ⊆ A. Then the following conditions are equivalent:

(1) B ∈ red (A);

(2) H^θ (B) = H^θ (A) and ∀ a ∈ B, H^θ (B - {a}) ≠ H^θ (A).

Proof. It can be proved by Theorem 4.18.□

Definition 4.20. Assume that (U, A) is an IIVIS. Given θ ∈ (0, 1], B ⊆ A and a ∈ A - B. Then θ-significance of an attribute a relative to B is defined as ${Sig}^{θ} (a, B) = H^{θ} (B) - H^{θ} (B - {a}) .$

We stipulate ${Sig}^{θ} (a, \emptyset) = 0 .$

Theorem 4.21. Let (U, A) be an IIVIS. Given θ ∈ (0, 1] and B ⊆ A. Then the following conditions are equivalent:

(1) B ∈ red (A);

(2) H^θ (B) = H^θ (A) and ∀ a ∈ B, Sig^θ (a, B) >0.

Proof. It follows from Theorem 4.21.□

5 Algorithms on θ-reduction in an IIVIS

It is more convenient to calculate all θ-reduction and the θ-core in an IIVIS by using the following θ-discernibility function.

Below, we give an algorithm on θ-reduction in an IIVIS by using mathematical logic.

“⋁”(disjunction), “⋀”(conjunction), “→”(implication), “↔”(biimplication) are propositional connectives in mathematical logic. They are read as “or”, “and”, “if-then”, “if and only if”, respectively.

Let (U, A) be an IIVIS. ∀ a ∈ A, we specify a Boolean variable “a”. If D^θ (u, v) = {a₁, a₂, ·· · , a_k} with u, v ∈ U, then we specify a Boolean function a₁ ∨ a₂ ∨ ·· · ∨ a_k.

Denote $⋁ {a_{1}, a_{2}, \cdot \cdot \cdot, a_{k}} or ⋁_{i = 1}^{k} a_{i} = a_{1} \lor a_{2} \lor \cdot \cdot \cdot \lor a_{k},$ $⋀ {a_{1}, a_{2}, \cdot \cdot \cdot, a_{k}} or ⋀_{i = 1}^{k} a_{i} = a_{1} \land a_{2} \land \cdot \cdot \cdot \land a_{k} .$

We stipulate that ∨ ∅ =1 and ∧ ∅ =0 where 0 and 1 are two Boolean constants.

Definition 5.1. Provided that (U, A) is an IIVIS. Given θ ∈ (0, 1]. Then the θ-discernibility matrix of A, denoted by ^Dθ (A) = (d_ij) _n×n, is define as

$Δ^{θ} (A) = ⋀ (⋁ d_{ij}) .$

Example 5.2. (Continued from Example 4.5)

Pick θ = 0.6, we have

Δ^0.6 (A) = a₃ ∧ a₂ ∧ (a₁ ∨ a₂) ∧ (a₃ ∨ a₄) ∧ (a₁ ∨ a₆) ∧ (a₅ ∨ a₆) ∧ (a₁ ∨ a₃) ∧ (a₂ ∨ a₃) ∧ (a₁ ∨ a₃ ∨ a₅) ∧ (a₁ ∨ a₂ ∨ a₆) ∧ (a₁ ∨ a₄ ∨ a₅) ∧ (a₁ ∨ a₄ ∨ a₆) ∧ (a₃ ∨ a₄ ∨ a₆) ∧ (a₁ ∨ a₃ ∨ a₄) ∧ (a₂ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₄) ∧ (a₂ ∨ a₃ ∨ a₄) ∧ (a₃ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₃ ∨ a₄ ∨ a₅) ∧ (a₃ ∨ a₄ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₄ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₅) ∧ (a₁ ∨ a₃ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄) ∧ (a₁ ∨ a₂ ∨ a₄ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₄ ∨ a₅] ∧ (a₂ ∨ a₃ ∨ a₅ ∨ a₆) ∧ (a₂ ∨ a₃ ∨ a₄ ∨ a₅) ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₄ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₃ ∨ a₄ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄ ∨ a₅) ∧ (a₂ ∨ a₃ ∨ a₄ ∨ a₅ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄ ∨ a₆) ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄ ∨ a₅ ∨ a₆)

Denote $L (A) = {⋁ d_{ij} : 1 \leq i, j \leq n} .$

A binary relation “≤” on L (A) is defined as follows:

$\begin{matrix} ⋁ d_{ij} \leq ⋁ d_{kl} \Rightarrow d_{ij} \subseteq d_{kl} for any ⋁ d_{ij}, \\ ⋁ d_{kl} \in L (A) . \end{matrix}$

For any ⋁d_ij, ⋁ d_kl ∈ L (A), we denote

$(⋁ d_{ij}) ⊔ (⋁ d_{kl}) = ⋁ (d_{ij} \cup d_{kl}),$

$(⋁ d_{ij}) ⊓ (⋁ d_{kl}) = ⋁ (d_{ij} \cap d_{kl}) .$

Proposition 5.3. (L (A) , ≤) is a poset.

Proof. (1) ⋁d_ij ≤ ⋁ d_ij for any ⋁d_ij ∈ L (A). (2) Given ⋁d_ij, ⋁ d_kl ∈ L (A). Suppose that ⋁d_ij ≤ ⋁ d_kl and ⋁d_kl ≤ ⋁ d_ij. Then d_ij ⊆ d_kl and d_kl ⊆ d_ij. This implies that d_ij = d_kl. So ⋁d_ij = ⋁ d_kl. (3) Given ⋁d_ij, ⋁ d_kl, ⋁ d_hv ∈ L (A). Suppose that ⋁d_ij ≤ ⋁ d_kl and ⋁d_kl ≤ ⋁ d_hv. Then d_ij ⊆ d_kl and d_kl ⊆ d_hv. This implies that d_ij ⊆ d_hv. So ⋁d_ij ≤ ⋁ d_hv. Consequently, (L (A) , ≤) is a poset.□

Proposition 5.4. Let (U, A) be an IIVIS. Given U = {u₁, u₂, ·· · , u_n} and θ ∈ (0, 1]. If {d_ij : 1 ≤ i, j ≤ n} is a topology on A, then (L (A) , ≤ , ⊔ , ⊓) is a lattice with top element and bottom element.

Proof. Denote τ = {d_ij : 1 ≤ i, j ≤ n}. By Proposition 5.3, (L (A) , ≤) is a poset. For ⋁d_ij, ⋁ d_kl ∈ L (A), since τ is a topology on A, we have d_ij ∪ d_kl ∈ τ, d_ij ∩ d_kl ∈ τ. This implies $(⋁ d_{ij}) ⊔ (⋁ d_{kl}) = ⋁ (d_{ij} \cup d_{kl}) \in L (A),$ $(⋁ d_{ij}) ⊓ (⋁ d_{kl}) = ⋁ (d_{ij} \cap d_{kl}) \in L (A) .$ Obviously, 1_L(A) = ∨ A, 0_L(A) =∨ ∅.

Consequently, (L (A) , ≤ , ⊔ , ⊓) is a lattice with top element and bottom element.□

Definition 5.5. Given an IIVIS (U, A). If θ ∈ (0, 1] and $Δ^{θ} (A) = ⋁_{k = 1}^{q} (⋀_{l = 1}^{p_{k}} a_{kl})$ , where every B_k = {a_kl : l ≤ p_k} ⊆ A has not repetitive elements, then $⋁_{k = 1}^{q} (⋀_{l = 1}^{p_{k}} a_{kl})$ is called the standard minimum formula of Δ^θ (A). We denote it by $Δ_{*}^{θ} (A)$ . That is, $Δ_{*}^{θ} (A) = ⋁_{k = 1}^{q} (⋀_{l = 1}^{p_{k}} a_{kl}) .$

Example 5.6. (Continued from Example 5.2)

Pick θ = 0.6, we have a₂ ∧ (a₁ ∨ a₂) = a₂, a₂∧ (a₂ ∨ a₃) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₆) = a₂, a₂ ∧ (a₂∨ a₅ ∨ a₆) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₄) = a₂, a₂ ∧ (a₂ ∨ a₃ ∨ a₄) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₅) = a₂, a₂∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₄ ∨ a₆) = a₂, a₂∧ (a₁ ∨ a₂ ∨ a₄ ∨ a₅) = a₂, a₂ ∧ (a₂ ∨ a₃ ∨ a₅ ∨ a₆) = a₂, a₂ ∧ (a₂ ∨ a₃ ∨ a₄ ∨ a₅) = a₂, a₂∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₅ ∨ a₆) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₄ ∨ a₅ ∨ a₆) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄ ∨ a₅) = a₂, a₂ ∧ (a₂ ∨ a₃ ∨ a₄ ∨ a₅ ∨ a₆) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨a₃∨ a₄ ∨ a₆) = a₂, a₂ ∧ (a₁ ∨ a₂ ∨ a₃ ∨ a₄ ∨ a₅ ∨ a₆) = a₂, a₃ ∧ (a₃ ∨ a₄) = a₃, a₃ ∧ (a₁ ∨ a₃) = a₃, a₃ ∧ (a₁ ∨ a₃ ∨ a₅) = a₃, a₃ ∧ (a₃ ∨ a₄ ∨ a₆) = a₃, a₃ ∧ (a₁ ∨ a₃ ∨ a₄) = a₃, a₃ ∧ (a₃ ∨ a₅ ∨ a₆) = a₃, a₃ ∧ (a₁ ∨ a₃ ∨ a₄ ∨ a₅) = a₃, a₃ ∧ (a₃ ∨ a₄ ∨ a₅ ∨ a₆) = a₃, a₃ ∧ (a₁ ∨ a₃ ∨ a₅ ∨ a₆) = a₃, a₃ ∧ (a₁ ∨ a₃ ∨ a₄ ∨ a₅ ∨ a₆) = a₃, (a₁ ∨ a₆) ∧ (a₁ ∨ a₄ ∨ a₆) = (a₁ ∨a₆) , (a₁ ∨ a₆) ∧ (a₁ ∨ a₄ ∨ a₅ ∨ a₆) = (a₁ ∨ a₆) .

Then Δ^0.6 (A) = a₂ ∧ a₃ ∧ (a₁ ∨ a₆) ∧ (a₅ ∨ a₆) ∧ (a₁ ∨ a₄ ∨ a₅) = (a₁ ∧ a₂ ∧ a₃ ∧ a₅) ∨ (a₁ ∧ a₂ ∧ a₃ ∧ a₆) ∨ (a₂ ∧ a₃ ∧ a₄ ∧ a₆) ∨ (a₂ ∧ a₃ ∧ a₅ ∧a₆) ∨ (a₁ ∧ a₂ ∧ a₃ ∧ a₄ ∧ a₅) ∨ (a₁ ∧ a₂ ∧ a₃ ∧ a₄ ∧ a₆) ∨ (a₁ ∧ a₂ ∧ a₃ ∧ a₅ ∧ a₆) ∨ (a₂ ∧ a₃ ∧ a₄ ∧ a₅ ∧ a₆).

Consequently, $Δ_{*}^{0.6} (A) = (a_{1} \land a_{2} \land a_{3} \land a_{5}) \lor (a_{1} \land a_{2} \land a_{3} \land a_{6}) \lor (a_{2} \land a_{3} \land a_{4} \land a_{6}) \lor (a_{2} \land a_{3} \land a_{5} \land a_{6}) \lor (a_{1} \land a_{2} \land a_{3} \land a_{4} \land a_{5}) \lor (a_{1} \land a_{2} \land a_{3} \land a_{4} \land a_{6}) \lor (a_{1} \land a_{2} \land a_{3} \land a_{5} \land a_{6}) \lor (a_{2} \land a_{3} \land a_{4} \land a_{5} \land a_{6})$ .

Theorem 5.7. Let (U, A) be an IIVIS. Given θ ∈ (0, 1]. If $Δ_{*}^{θ} (A) = ⋁_{k = 1}^{q} (⋀_{l = 1}^{p_{k}} a_{kl})$ is the standard minimum formula of Δ^θ (A), then ${red}^{θ} (A) = {B_{k} : k \leq q},$ where B_k = {a_kl : l ≤ p_k}.

Proof. (1) Given B_{k
₀} ∈ {B_k : k ≤ q}.

(i) Clearly, $Δ_{*}^{θ} (A) = ⋁_{k = 1}^{q} (⋀_{l = 1}^{p_{k}} a_{kl}) = ⋁_{k = 1}^{q} (⋀ B_{k})$ . Then $⋀ B_{k_{0}} \to Δ_{*}^{θ} (A)$ .

Since $Δ_{*}^{θ} (A) = Δ^{θ} (A) = ⋀ (⋁ d_{ij})$ , we have

$Δ_{*}^{θ} (A) \Rightarrow ⋁ d_{ij} for any 1 \leq i, j \leq n .$

Then ∀ u, v ∈ U, ⋀B_{k
₀} → ⋁ D^θ (u, v).

So $\forall (u, v) \notin R_{A}^{θ}$ , ⋀B_{k
₀} → ⋁ D^θ (u, v).

Now ⋀B_{k
₀} ⇒ a_{k
₀
l} for any l ≤ p_{k
₀} and ⋁D^θ (u, v) ↔ a for some a ∈ D^θ (u, v). Then $\forall (u, v) \notin R_{A}^{θ}$ , a_{k
₀
l} for any l ≤ p_{k
₀} → a for some a ∈ D^θ (u, v).

So $\forall (u, v) \notin R_{A}^{θ}$ , there exists l₀ ≤ p_{k
₀} such that a = a_{k
₀
l
₀}, i.e., a ∈ B_{k
₀} ∩ D^θ (u, v).

Consequently, $\forall (u, v) \notin R_{A}^{θ}$ , B_{k
₀}∩ D^θ (u, v) ≠ ∅.

By Proposition 4.8, B_{k
₀} ∈ co^θ (A).

(ii) To prove B_{k
₀} ∈ red^θ (A), by Theorem 3.8, we only need to show that

$\forall a \in B_{k_{0}}, \exists (u_{a}, v_{a}) \in R_{A}^{θ}, (B_{k_{0}} - {a}) \cap D^{θ} (u_{a}, v_{a}) = \emptyset .$

Suppose that ∃ a₀ ∈ B_{k
₀} such that (B_{k
₀} - {a₀})∩ D^θ (u, v) ≠ ∅ for any $(u, v) \notin R_{A}^{θ}$ . Pick a_xy ∈ (B_{k
₀} - {a₀}) ∩ D^θ (u, v). Then ⋀ (B_{k
₀} - {a₀}) → a_xy and a_xy → ⋁ D^θ (u, v).

Consequently, $\forall (u, v) \notin R_{A}^{θ}$ , ⋀ (B_{k
₀} - {a₀}) → ⋁ D^θ (u, v) .

$\forall (u, v) \in R_{A}^{θ}$ , we have D^θ (u, v) =∅. Then ⋀ (B_{k
₀} - {a₀}) → ⋁ D^θ (u, v) .

It follows that ∀ u, v ∈ U, ⋀ (B_{k
₀} - {a₀}) → ⋁ D^θ (u, v) .

Since $Δ_{*}^{θ} (A)$ contains all true explanations of Δ^θ (A), we have B_{k
₀} - {a₀} ∈ {B_k : k ≤ q}. Then

$(⋀ B_{k_{0}}) ⋁ (⋀ (B_{k_{0}} - {a_{0}}))$

$\begin{matrix} = ((⋀ (B_{k_{0}} - {a_{0}})) ⋀ {a_{0}}) ⋁ \\ ((⋀ (B_{k_{0}} - {a_{0}})) ⋀ 1) \end{matrix}$

= (⋀ (B_{k
₀} - {a₀})) ⋀ ({a₀} ⋁1)

= (⋀ (B_{k
₀} - {a₀})) ⋀ 1

= ⋀ (B_{k
₀} - {a₀}).

So B_{k
₀} ∉ {B_k : k ≤ q}. This is a contradiction.

Consequently, B_{k
₀} ∈ red^θ (A). This shows that red^θ (A) ⊇ {B_k : k ≤ q}.

(2) Let B ∈ red^θ (A). Then B ∈ co^θ (A). By Proposition 4.8, B∩ D^θ (u, v) ≠ ∅ for any $(u, v) \notin R_{A}^{θ}$ .

Similar to the proof of (1) (ii), we can show that B ∈ {B_k : k ≤ q} .

Consequently, red^θ (A) ⊆ {B_k : k ≤ q}.

Hence red^θ (A) = {B_k : k ≤ q} . □

When $\min_{1 \leq k \leq | A |} \max_{1 \leq i, j \leq | U |} s ((a_{k} (u_{i}), a_{k} (u_{j})) < θ,$ we have $R_{A}^{θ} = \emptyset$ and then red^θ (A) =∅.

In order to ensure that there always exists a θ-reduct of A, we demand

$\min_{1 \leq k \leq | A |} \max_{1 \leq i, j \leq | U |} s ((a_{k} (u_{i}), a_{k} (u_{j})) \geq θ .$

Example 5.8. (Continued from Example 5.6) Pick θ = 0.6.

From Example 5.6, we obtain Δ^0.6 (A) and $Δ_{*}^{0.6} (A)$ .

Consequently, red^0.6 (A) = {{a₁, a₂, a₃, a₅} , {a₁, a₂, a₃, a₆} , {a₂, a₃, a₄, a₆} , {a₂, a₃, a₅, a₆} , {a₁, a₂, a₃, a₄, a₅} , {a₁, a₂, a₃, a₄, a₆} , {a₁, a₂, a₃, a₅, a₆} , {a₂, a₃, a₄, a₅, a₆}},

Obviously, core^0.6 (A) = {a₂, a₃}

We can get reduction algorithm based on θ-discernibility matrix in Algorithm 2.

Below, we analyze the time complexity and space complexity of Algorithm 2. |A| and |U| are applied to respectively denote the the numbers of attributes and samples. It should be pointed out that, we need to compute such the tolerance relation matrices with respect to each attribute that cost O (|A||U|²) and the θ-discernibility matrix that cost O (|A| (|U|² - |U|)/2). We compute reduce set cost O (((|U|² - |U|)/2) ((|U|² - |U|)/2)). Thus, the overall time complexity of Algorithm 2 is O ((|U|⁴ + 2|U|³)/4 + (6|A||U|² + 1)/4 - |A||U|/2). The space for all the subsequent matrices and local variables can be reused. So, the space complexity of Algorithm 2 is O (|A||U|²).

Reduction algorithm based on θ-information entropy is obtained which is showed in Algorithm 3.

Algorithm 3 employs θ-information entropy H^θ to determine the optimal attribute which is added into the current selected attribute subset in each loop. In the worst case, this process is terminated when the whole feature set has been exhausted. The worst search time for a reduct will result in |A| evaluations. Thus, the overall time complexity of Algorithm 3 is O (|A||U|² + |A|). Also, at the initial stage, |C| fuzzy relation matrices of |U| × |U| are computed and stored corresponding to each individual features. Similarly, the space complexity of Algorithm 3 is O (|A||U|²).

We can get reduction algorithm based on θ-significance which is showed in Algorithm 4.

Here, the worst search time for a reduct will result in |A| (|A|+1)/2 evaluations. So the time complexity and space complexity of Algorithm 4 are O (|A||U|² + (|A|² + |C|)/2) and O (|A||U|²), respectively.

Example 5.9. In order to better prove the practical significance of Algorithms 2-4 for incomplete interval-value data, we select six data sets from the UCI database to do experiment. The data sets are described in Table 10. In fact, the data sets are real data. However, we need to study incomplete interval-value data. Therefore, we refer to the article of Lin [14] to change the real value data into interval-value data. Firstly, we get the standard deviation σ of the information value under attribute a_i. Secondly, the interval number a′ (x) converted from the information value of object x_i under attribute a_i can be obtained by formula a′ (x) = [a (x) - ξ σ, a (x) - ξ σ]. Where ξ is the parameter, here we take ξ = 0.1. lastly, we randomly missed at a probability of 0.05 in |U||A|. In summary, incomplete interval-value data is gained by this way.

Table 10
The testing data sets

No. Data sets Object Attribute

1 Wine 178 13

2 Breast-Tissue 106 9

3 Seeds 210 7

4 Wdbc 569 34

5 Leaf 340 15

6 Parkinsons 197 23

No.	Data sets	Object	Attribute
1	Wine	178	13
2	Breast-Tissue	106	9
3	Seeds	210	7
4	Wdbc	569	34
5	Leaf	340	15
6	Parkinsons	197	23

Based on the above preparation, we take the testing data sets to do experiments.

(1) We randomly generate six interval-value data sets with Table 10 and then use Algorithm 2 to reduce. The result of one experiment is shown in the table 11. We get 112 reduction sets, and the average size of these reduction sets is 9.4 on wine data, 13 reduction sets, and the average size of these reduction sets is 9.4 on Breast Tissue data, 14 reduction sets, and the average size of these reduction sets is 2.9 on seeds data, 2847 reduction sets, and the average size of these reduction sets is 22.2 on wdbc data, 97 reduction sets, and the average size of these reduction sets is 7.3 on leaf data, 110 reduction sets, and the average size of these reduction sets is 10.2 on parkinsons data,respectively. θ-discernibility matrix algorithm can obtain multiple reductions. Figures 2 –7 shows the number of attributes for each reduction with θ-discernibility matrix.

Fig. 2

Number of attributes by Algorithm 2(Wine).

Fig. 3

Number of attributes by Algorithm 2(Breast-Tissue).

Fig. 4

Number of attributes by Algorithm 2(Seeds).

Fig. 5

Number of attributes by Algorithm 2(Wbdc).

Fig. 6

Number of attributes by Algorithm 2(Leaf).

Fig. 7

Number of attributes by Algorithm 2(Parkinsons).

(2) Each time of Algorithm 3 is run, it will get a reduction set. Here we run it 20 times on each data set and get the reduction results in Table 12 as follows. Figure 8 shows the average of the number of selected features on each data set.

Table 11

Numbers of selected features with θ-discernibility matrix

Data sets	Raw date	Numbers of reduce sets	Average size of reduce sets
Wine	13	112	9.4
Breast-Tissue	9	13	3.1
Seeds	7	14	2.9
Wdbc	34	2847	22.2
Leaf	15	97	7.3
Parkinsons	23	110	10.2

Table 12

Numbers of selected features with θ-information entropy

Data sets	Raw date	θ-information entropy
Wine	13	3.9
Breast-Tissue	9	6.3
Seeds	7	5.2
Wdbc	34	5.6
Leaf	15	8.1
Parkinsons	23	7.5

Fig. 8

Number of attributes by Algorithm 3.

(3) Each time of Algorithm 4 is run, it will get a result. Here we run it 20 times and get the reduction results in Table 13 as follows. Figure 9 shows the average of the number of attributes each data set.

Table 13

Numbers of selected features with θ-significance

Data sets	Raw date	θ-significance
Wine	13	3.0
Breast-Tissue	9	3.2
Seeds	7	4.3
Wdbc	34	4.0
Leaf	15	4.1
Parkinsons	23	3.5

Fig. 9

Number of attributes by Algorithm 4.

6 Comparisons and conclusions

In this section, comparisons with reduction in other kinds of ISs are carried out and conclusions are given.

1) Aiming at the problem of attribute reduction in interval-value IS, Chen et al. [4] introduced a variable precision tolerance relation and a kind of maximal variable precision tolerance class. Then they defined a kind of discernibility function and relative discernibility function based on the discernibility matrix. Finally, they proposed attribute reduction and relative attribute reduction in interval-valued ISs.

2) Considering that the existing attribute reduction method for single valued data is not suitable for interval valued data. From the viewpoint of information theory, Dai et al. [6] raised attribute reduction in interval-valued data. They gave some information theory concepts in interval-valued IS. And thay put forward an information theory view for attribute reduction in interval-valued IS based on these concepts.

3) Zhang et al. [33] thought over compact decision rules in an interval-valued decision system for attribute reduction. First, they put forward the concept of interval-value granular rules in interval-value decision system. Next, they presented an index to measure the confidence of an interval-valued granular rule and defined implication relationship between the interval-valued granular rules whose confidences are not less than the threshold. Last, they proposed a confidence-preserved attribute reduction approach based on the implication relationship.

4) Generally, people study attribute selection from two aspects of relation reduction and information entropy reduction. In this way, two approaches of attribute selection are formed. This article has given attribute selection approaches for incomplete interval-value data. θ-reduction and θ-information entropy-reduction for incomplete interval-value data have been proposed. It is worth mentioning that connections between these two reducts have been researched. We has proved that these two reducts are essentially the same. This is one of the main contributions of this paper. By using these two approaches of attribute selection, reduction algorithms based on θ-discernibility matrix, θ-information entropy and θ-significance in an IIVIS have been given, respectively. Time complexity and space complexity of these three algorithms have been presented. In future work, we will study applications of attribute selection approaches for incomplete interval-value data.

Footnotes

Acknowledgments

The authors would like to thank the editors and the anonymous reviewers for their valuable comments and suggestions, which have helped immensely in improving the quality of the paper. This work is supported by National Natural Science Foundation of China (11971420), Natural Science Foundation of Guangxi (2018GXNSFDA294003, 2018GXNSFAA294134), Guangxi Higher Education Institutions of China ([2019] 52), Special Scientific Research Project of Young Innovative Talents in Guangxi (2019 AC20052), Key Laboratory of Software Engineering in Guangxi University for Nationalities (2018-18XJSY-03), Research Project of Institute of Big Data in Yulin (YJKY03) and Engineering Project of Undergraduate Teaching Reform of Higher Education in Guangxi (2017JGA179).

References

Beaubouef

, Petry

F.E.

and Arora

, Information-theoretic measures of uncertainty for rough sets and rough relational databases, Information Sciences 109 (1998), 185–195.

Blaszczynski

, Slowinski

and Szelag

, Sequential covering rule induction algorithm for variable consistency rough set approaches, Information Sciences 181(5) (2011), 987–1002.

Cornelis

, Jensen

, Martin

G.H.

and Slezak

, Attribute selection with fuzzy decision reducts, Information Sciences 180 (2010), 209–224.

Chen

Z.C.

and Qin

K.Y.

, Attribute reduction of interval-valued information system based on the maximal tolerance class, Fuzzy Systems and Mathematics 23(6) (2009), 126–132.

Duntsch

and Gediga

, Uncertainty measures of rough set prediction, Artificial Intelligence 106 (1998), 109–137.

Dai

J.H.

, Hu

, Zheng

G.J.

, Hu

Q.H.

, Han

H.F.

and Shi

, Attribute reduction in interval-valued information systems based on information entropies, Frontiers of Information Technology & Electronic Engineering 17(9) (2016), 919–928.

Dubois

and Prade

, Rough fuzzy sets and fuzzy rough sets, International Journal of General Systems 17(2-3) (1990), 191–209.

Dai

J.H.

and Tian

H.W.

, Entropy measures and granularity measures for interval-valued information systems, Information Sciences 240 (2013), 72–82.

Dai

J.H.

, Wang

W.T.

and Mi

J.S.

, Uncertainty measurement for interval-valued information systems, Information Sciences 251 (2013), 63–78.

10.

Dai

J.H.

, Wang

W.T.

, Xu

and Tian

H.W.

, Uncertainty measurement for interval-valued decision systems based on extended conditional entropy, Knowledge-Based Systems 27 (2012), 443–450.

11.

Facchinetti

, Ricci

and Muzzioli

, Note on ranking fuzzy triangular numbers, International Journal of Intelligent Systems 13 (1998), 613–622.

12.

Q.H.

, Pedrycz

, Yu

D.R.

and Lang

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

13.

Kryszkiewicz

, Rules in incomplete information systems, Information Sciences 113 (1999), 271–292.

14.

Lin

B.Y.

and Xu

W.H.

, Multi-granulation rough set for incomplete interval-valued decision information systems based on multithreshold tolerance relation, Symmetry 10(6) (2018), 208. https://doi.org/10.3390/sym10060208.

15.

Leung

, Fischer

M.M.

, Wu

W.Z.

and Mi

J.S.

, A rough set approach for the discovery of classification rules in interval-valued information systems, International Journal of Approximate Reasoning 47 (2008), 233–246.

16.

Z.W.

, Zhang

P.F.

, Ge

, Xie

N.X.

, Zhang

G.Q.

and Wen

C.F.

, Uncertainty measurement for a fuzzy relation information system, IEEE Transactions on Fuzzy Systems 27 (2019), 2338–2352.

17.

J.S.

, Leung

and Wu

W.Z.

, An uncertainty measure in partition-based fuzzy rough sets, International Journal of General Systems 34 (2005), 77–90.

18.

Nakahara

, User oriented ranking criteria and its application to fuzzy mathematical programming problems, Fuzzy Sets and Systems 94 (1998), 275–286.

19.

Nakahara

, Sasaki

and Gen

, On the linear programming problems with set coefficients, Computers and Industrial Engineering 23 (1992), 301–304.

20.

Pawlak

, Rough sets, International Journal of Computer and Information Science 11 (1982), 341–356.

21.

Pawlak

, Rough sets: Theoretical aspects of reasoning about data, Kluwer Academic Publishers, Dordrecht, (1991).

22.

Pawlak

and Skowron

, Rough sets and boolean reasoning, Information Sciences 177 (2007), 41–73.

23.

Pawlak

and Skowron

, Rudiments of rough sets, Information Sciences 177 (2007), 3–27.

24.

Qian

Y.H.

, Liang

J.Y.

, Wu

W.Z.

and Dang

C.Y.

, Information granularity in fuzzy binary GrC model, IEEE Transactions on Fuzzy Systems 19(2) (2011), 253–264.

25.

Sakai

, Nakata

and Slezak

, A prototype system for rule generation in Lipskiąŕs incomplete information databases, in: Proceedings of 13th Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (2011), 175–182.

26.

Thangavel

and Pethalakshmi

, Dimensionality reduction based on rough set theory: A review, Applied Soft Computing 9 (2009), 1–12.

27.

Wierman

M.J.

, Measuring uncertainty in rough set theory, International Journal of General Systems 28 (1999), 283–297.

28.

Xie

N.X.

, Liu

, Li

Z.W.

and Zhang

G.Q.

, New measures of uncertainty for an interval-valued information system, Information Sciences 470 (2019), 156–174.

29.

Yao

Y.Y.

and Noroozi

, Aunified framework for set-based computations, in: Proceedings of the 3rd International Workshop on Rough Sets and Soft Computing (1994), 10–12.

30.

Yao

Y.Y.

and Li

X.N.

, Comparison of rough-set and set-set models for uncertain reasoning, Fundamenta Informaticae 27 (1996), 289–298.

31.

Yang

X.B.

, Yu

D.J.

, Yang

J.Y.

and Wei

, Dominance-based rough set approach to incomplete interval-valued information system, Data and Knowledge Engineering 68(11) (2009), 1331–1347.

32.

Zhang

G.Q.

, Li

Z.W.

, Wu

W.Z.

, Liu

X.F.

and Xie

N.X.

, Information structures and uncertainty measures in a fully fuzzy information system, International Journal of Approximate Reasoning 101 (2018), 119–149.

33.

Zhang

, Mei

, Chen

and Li

, Multi-confidence rule acquisition and confidence-preserved attribute reduction in intervalvalued decision systems, International Journal of Approximate Reasoning 55(8) (2014), 1787–1804.

Attribute selection approaches for incomplete interval-value data

Abstract

Keywords

1 Introduction

2.1 Binary relations

2.2 Interval-valued numbers

2.3 An IIVIS

3.1 The similarity degree between information values on an attribute in an IIVIS

4.1 θ-reduction, θ-core and θ-discernibility matrix in an IIVIS

4.2 Some properties

4.3 Entropy measurement for an IIVIS

5 Algorithms on θ-reduction in an IIVIS

Table 10 The testing data sets No. Data sets Object Attribute 1 Wine 178 13 2 Breast-Tissue 106 9 3 Seeds 210 7 4 Wdbc 569 34 5 Leaf 340 15 6 Parkinsons 197 23

Footnotes

Acknowledgments

References

Table 10
The testing data sets

No. Data sets Object Attribute

1 Wine 178 13

2 Breast-Tissue 106 9

3 Seeds 210 7

4 Wdbc 569 34

5 Leaf 340 15

6 Parkinsons 197 23