Attributes correlation coefficients and their application to attributes reduction

Abstract

In this paper, information entropy about logarithmic form is used to measure uncertainty of knowledge, and the correlation connection between information entropy, conditional information entropy, joint information entropy and mutual information entropy are analyzed. Correlation coefficient ρ (B, C) between two attribute subsets in random information systems and ρ (C/-B) for a conditional attributes set B relative to another condition attributes set C w.r.t. the decision attributes set D in random decision information systems are introduced. The properties of correlation coefficients are discussed, and some concepts about random information systems and random decision information systems, such as indispensable attributes, consistent attributes and core attributes, etc, are described by using correlation coefficients. Some new methods of attribute reduction are proposed by using correlation coefficients, the corresponding algorithms based on attribute correlation coefficient are given in random information systems and in random decision information systems, the listed examples and the experimental result show that the algorithms are effective.

Keywords

Random decision information system probability distribution of attributes set information entropy of attributes set correlation coefficient attribute reduction

1 Introduction

Feature selection (or attribute reduction) is a key step of knowledge discovery or data mining. An attribute subset selection involves determining a relevant subset of attributes for using knowledge discovery model. There are three categories of the attribute extraction algorithms, namely, filters, wrappers, and embedded methods [1, 2]. Attribute reduction is an aspect of knowledge discovery, which is also a feature selection method in essence. The rough set theory, introduced by Pawlak, has been conceived as a widely used tool to reduct attributes [3], and hence attribute reduction is one of the most important work in rough set theory. As we all known that attribute reduction is inefficient and NP-Hard problem [4]. And hence many scholars from different perspective, applying various research strategies and research methods, makes the attribute reduction algorithm based on rough set theory appearing constantly [5 –8].

A decision rule in a decision information system is a combination of conditional attribute values and decision attribute values connected by some logical connectives. In order to get some simple decision rules in a decision information system the conditional attributes must be reduced, the essence of conditional attribute reduction of decision information system is to find a minimum set of attributes in a conditional attribute set [9 –14]. In all attribute reduction methods, using the information entropy to attribute reduction is an important one. Miao et al. introduced Shannon information Entropy in information system and proposed attribute reduction algorithm based on mutual information [7, 9]. Wang et al. proposed attribute reduction algorithm based on conditional information entropy [10, 11]. Liang et al. defined the concept of information measure in information system, and proposed an attribute reduction algorithm based on information measure [13]. Qian et al. proposed a positive approximation which is used to accelerate algorithms of heuristic attribute reduction [14]. Zhang et al. studied the uncertainty measure of attribute and attribute set of random decision information system and random fuzzy information system, and used the uncertainty measure to carry out attribute reduction [15]. Liu et al. proposed the corresponding attribute reduction algorithm based on the conditional entropy theory [16]. Liu et al. proposed the corresponding attribute reduction algorithm based on the conditional entropy theory [17]. Batle et al. discuss both quantum entanglement and nonlocality (implied by the violation of Bell inequalities) constitute quantum correlations that cannot be arbitrarily shared among subsystems [18 –24].

With the emergence of big data, in order to meet the demand of processing performance and real-time response requirements is a key issue that can enhance efficiency of data preprocessing, and hence many updating algorithms have been successfully applied to massive data processing and interactive applications. In processing the attribute reduction of information system in which the real data vary dynamically with time, Lang et al. investigate the mechanisms of updating the attribute reductions by the utilization of the previously results in dynamic covering decision information systems and design incremental algorithms for attribute reduction of dynamic covering decision information systems [25]. Considering the large-scale and streaming arrivals of data characteristics in the era of big data, Chen et al. proposed a hybrid parallel solution approach on the Apache Spark Platform combining data-parallel and task-parallel optimization, benefiting from the data-parallel and task-parallel optimization, the data transmission cost are effectively reduced and the performance of the algorithms are obviously improved [26].

The present paper focus on discussing two new correlation coefficients and applying them to the attributes reduction in random information systems and in random decision information systems. Firstly, probability distribution, joint probability distribution and conditional probability distribution based on random information systems and random decision information systems are given. Information entropy about logarithmic form is introduced to measure uncertainty of knowledge, and the correlation connection between information entropy, conditional information entropy, joint information entropy and mutual information entropy are analyzed. Secondly, correlation coefficient ρ (B, C) between two attribute subsets in random information systems and ρ (C/B) for a conditional attributes set B relative to another condition attributes set C with respect to (w.r.t., for short) the decision attributes set D in random decision information systems are introduced. The properties of correlation coefficients are discussed, and some concepts about random information systems and random decision information systems, such as indispensable attributes, consistent attributes and core attributes, etc, are described by using correlation coefficient. Thirdly, some new methods of attribute reduction are proposed by using correlation coefficients, the corresponding algorithms based on attribute correlation coefficient are given in random information systems and in random decision information systems, the listed examples and the experimental result show that the algorithms are effective.

2 Information entropy of attributes in random information systems

An information system (or database system) is a quarter-nary form (U, A, V, F), where U = {x₁, x₂, ⋯ , x_n} is object set, every x_k is called an object; A = {a₁, a₂, ⋯ , a_m} is attribute set, every a_k is called an attribute; V = ⋃ _{a_k∈AV^(a_k)} is attribute value set, V^(a_k) is the value domain of attribute a_k, F = {f_{a
_k} : U → V^(a_k), k ⩽ m} is relation set from U to A. If the attributes set of an information system is partitioned into A and D then it is called decision information system, A is referred to as condition attributes set and D is referred to as decision attributes set. An information system is referred to as random information system if there is a normal probability measure P on U, where a normal probability measure P means that ∀x ∈ U, P ({x}) >0 and ∑_x∈UP ({x}) =1.

In an information system, the relation set F shows the connection between object set and attribute set and gives the information source of knowledge discovery. For example, f_{a
_k} (x_i) = v means that the attribute value of attribute a_k of object x_i is v.

In a random information system ((U, P) , A, V, F), for a ∈ A, $V^{(a)} = {v_{1}^{(a)}, v_{2}^{(a)}, \dots, v_{m}^{(a)}}$ , we can give the probability distribution P (a) as Table 1.

Table 1
Probability distribution of attribute a

a $v_{1}^{(a)}$ $v_{2}^{(a)}$ ⋯ $v_{m}^{(a)}$

p ^(a) $p (v_{1}^{(a)})$ $p (v_{2}^{(a)})$ ⋯ $p (v_{m}^{(a)})$

a	$v_{1}^{(a)}$	$v_{2}^{(a)}$	⋯	$v_{m}^{(a)}$
p ^(a)	$p (v_{1}^{(a)})$	$p (v_{2}^{(a)})$	⋯	$p (v_{m}^{(a)})$

Where $p (v_{i}^{(a)}) = P ({x | f (x, a) = v_{i}^{(a)}}) (i = 1, 2,$ ⋯, m) is the probability of attribute a taking value $v_{i}^{(a)}$ .

Analogously, we can give the joint probability distribution P (ab) and the conditional probability distribution P (b/a) as Tables 2 and 3 respectively.

Table 2

Joint probability distribution of a and b

	$v_{1}^{(b)}$	$v_{2}^{(b)}$	⋯	$v_{q}^{(b)}$
$v_{1}^{(a)}$	$p (v_{1}^{(a)}, v_{1}^{(b)})$	$p (v_{1}^{(a)}, v_{2}^{(b)})$	⋯	$p (v_{1}^{(a)}, v_{q}^{(b)})$
$v_{2}^{(a)}$	$p (v_{2}^{(a)}, v_{1}^{(b)})$	$p (v_{2}^{(a)}, v_{2}^{(b)})$	⋯	$p (v_{2}^{(a)}, v_{q}^{(b)})$
⋮	⋮	⋮	⋱	⋮
$v_{m}^{(a)}$	$p (v_{m}^{(a)}, v_{1}^{(b)})$	$p (v_{m}^{(a)}, v_{2}^{(b)})$	⋯	$p (v_{m}^{(a)}, v_{q}^{(b)})$

Table 3

Conditional probability distribution of b given a

	$v_{1}^{(b)}$	$v_{2}^{(b)}$	⋯	$v_{q}^{(b)}$
$v_{1}^{(a)}$	$p (v_{1}^{(b)} / v_{1}^{(a)})$	$p (v_{2}^{(b)} / v_{1}^{(a)})$	⋯	$p (v_{q}^{(b)} / v_{1}^{(a)})$
$v_{2}^{(a)}$	$p (v_{1}^{(b)} / v_{2}^{(a)})$	$p (v_{2}^{(b)} / v_{2}^{(a)})$	⋯	$p (v_{q}^{(b)} / v_{2}^{(a)})$
⋮	⋮	⋮	⋱	⋮
$v_{m}^{(a)}$	$p (v_{1}^{(b)} / v_{m}^{(a)})$	$p (v_{2}^{(b)} / v_{m}^{(a)})$	⋯	$p (v_{q}^{(b)} / v_{m}^{(a)})$

Where $p (v_{i}^{(a)}, v_{j}^{(b)}) = P ({x | f (x, a) = v_{i}^{(a)}$ and $f (x, b) = v_{j}^{(b)}})$ (i = 1, 2, ⋯ , m, j = 1, 2, ⋯ , q) is the joint probability of attribute a taking value $v_{i}^{(a)}$ and b taking value $v_{j}^{(b)}$ .

Where $p (v_{j}^{(b)} / v_{i}^{(a)}) = \frac{p (v_{i}^{(a)}, v_{j}^{(b)})}{p (v_{i}^{(a)})} (i = 1, \dots, m, j$ = 1, ⋯ , q) is the conditional probability of attribute b taking value $v_{j}^{(b)}$ given a taking value $v_{i}^{(a)}$ .

Analogously, we can obtain joint probability distribution P (B ∪ C) of two attribute subsets B and C and the conditional probability distribution P (C/B) of C given B. The above probability distribution have the following properties: (1) If a ∈ B then the joint probability distribution of {a} and B is same as the joint probability distribution of {a} and B - {a}, and it equal to the probability distribution of B. (2) The conditional probability distribution P (a/B) of {a} given B is same as the conditional probability distribution P (a/(B - {a})) of {a} given B - {a}. (3) If the probability distribution of B is same as the probability distribution of C, then the joint probability distribution P (B ∪ C) is same as the probability distribution P (B) (or P (C)).

If the attribute values in random information system are numerical, then the probability distribution of attributes subset can be regarded as the probability distribution of random variables. Hence an attribute a determines a random variable and an attributes subset B = {a₁, a₂, ⋯ , a_q} determines a q-dimensional random vector, these random variables or random vectors are denoted as a and B. But in general, the values of attribute a may not be numerical values, and then the probability distribution defined as above may not be the probability distribution of random variables. Hence the probability analysis method is not suitable for analyzing the random information system. But since the symbols used to describe the information sources is not necessarily the numerical values in Shannon information entropy theory, so we can use the Shannon information entropy theory to analyze the random information system.

Definition 2.1. Let ((U, P) , A, V, F) be a random information system, the information entropy of attribute a is defined by $H (a) = - \sum_{i = 1}^{m} p (v_{i}^{(a)}) {log}_{2} p (v_{i}^{(a)}) .$

The joint information entropy of attribute a and b is defined by $H (ab) = - \sum_{i = 1}^{m} \sum_{j = 1}^{q} p (v_{i}^{(a)}, v_{j}^{(b)}) {log}_{2} p (v_{i}^{(a)}, v_{j}^{(b)}) .$

The conditional information entropy of attribute b given a is defined by $H (b / a) = - \sum_{i = 1}^{m} \sum_{j = 1}^{q} p (v_{i}^{(a)}, v_{j}^{(b)}) {log}_{2} p (v_{j}^{(b)} / v_{i}^{(a)}) .$

The average mutual information of attribute a and b is defined by $I (a, b) = H (b) - H (b / a) .$

Analogously, the above definition can be generalized to the case of subset of attributes. The following properties hold for information entropy.

Proposition 2.2.

H (B/C) ⩽ H (B), and if A and B are independent then the equality holds;

H (CB) = H (C) + H (B/C) = H (C) + H (B) - I (C, B);

I (C, B) = H (B) - H (B/C) ⩾0;

I (C, B) = H (C) + H (B) - H (CB).

Proposition 2.3. Let ((U, P) , A, V, F) be a random information system, Q = {a₁, ⋯ , a_q}, S = {b₁, ⋯ , b_s} ⊆ A. If the probability distribution of Q and S satisfy the following condition: $P {a_{i} = v_{ik}^{(a_{i})} | a_{i} \in Q} = \sum P {b_{j} = v_{jl}^{(b_{j})} | b_{j} \in S},$ then H (Q) ⩽ H (S). And if the right of above equation has at least two non-zero items, then H (Q) < H (S).

Proof. By the monotone increasing properties of information entropy, we have that

$\begin{matrix} H (S) & = & H (p_{11}, \dots, p_{1 i_{1}}; p_{21}, \dots, p_{2 i_{2}}; \dots; p_{n 1}, \dots, p_{1 i_{n}}) \\ = & H (p_{1}, \dots, p_{n}) + p_{1} H (\frac{p_{11}}{p_{1}}, \dots, \frac{p_{1 i_{1}}}{p_{1}}) \\ + \dots + p_{n} H (\frac{p_{n 1}}{p_{n}}, \dots, \frac{p_{1 i_{n}}}{p_{n}}), \end{matrix}$

where $\sum_{i = 1}^{n} p_{i} = 1$ , $\sum_{j = 1}^{i_{k}} p_{kj} = p_{k}$ (k = 1, ⋯ , n). If i_k > 1 then the item k in the right of the above equation is not 0, and hence H (Q) ⩽ H (S). Further, if the right of the above equation has at least two non-zero items, then H (Q) < H (S).

Corollary 2.4. Let ((U, P) , A, V, F) be a random information system. If Q, S ⊆ A, Q ⊆ S and the probability distributions of Q and S are different, then H (Q) < H (S).

Proof. Since Q ⊆ S and the probability distributions of Q and S are different, we know that the probability distributions of Q and S satisfy the condition of Proposition 2.3. Hence H (Q) < H (S).

Example 2.5. A car information system as shown in Table 4, in which a₁ =“price”, a₂ =“internal design”, a₃ =“engine”, a₄ =“acceleration performance”, hig. = high, cro. = crowd, spa. = spacious, gas. = gasoline, die. = diesel, mid. = middle. A normal probability distribution P on U as follows: P ({u₁}) = 1/ - 4, P ({u₂}) = 1/ - 4, P ({u₃}) = 1/ - 8, P ({u₄}) = 1/ - 8, P ({u₅}) = 1/ - 4.

Table 4

A car information system

U	a ₁	a ₂	a ₃	a ₄
u ₁	low	cro.	gas.	low
u ₂	low	spa.	die.	mid.
u ₃	hig.	cro.	die.	hig.
u ₄	hig.	cro.	die.	mid.
u ₅	low	spa.	gas.	mid.

Using the probability distribution P on U, we can compute the probability distribution of attributes. For example, the probability distribution P (a₂) of attribute a₂ as shown in Table 5.

Table 5

Probability distribution of attribute a₂

	p(cro.)	p(spa.)
p	$\frac{1}{2}$	$\frac{1}{2}$

The joint probability distribution P (a₂a₃) of attributes a₂ and a₃ as shown in Table 6.

Table 6

Joint probability distribution of attribute a₂ and a₃

	p(cro.,gas.)	p (cro.,die.)	p (spa.,gas.)	p (spa.,die.)
p (a₂, a₃)	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{4}$

The conditional probability distribution p (a₃/a₂) of attribute a₃ given a₂ as shown in Table 7.

Table 7

Conditional probability distribution of attribute a₃ given a₂

	p (gas./cro.)	p (die./cro.)	p (gas./spa.)	p (die./spa.)
p (a₃/a₂)	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$

3 Correlation coefficient of attributes set

3.1 Correlation coefficient of attributes subset in random information system

Definition 3.1 Let ((U, P) , A, V, F) be a random information system and B, C ⊆ A. The correlation coefficient of attribute subsets B and C is defined as $ρ (B, C) = \frac{I (B, C)}{\sqrt{H (B)} \sqrt{H (C)}} .$

Proposition 3.2.

0 ⩽ ρ (B, C) ⩽1.

If random vector B and C are independent, then ρ (B, C) =0.

ρ (B, C) =1 if and only if the probability distribution of B is same as the probability distribution of C.

a is indispensable w.r.t. A if and only if ρ (A, A - {a}) =1.

Core (A) = {a ∈ A|ρ (A - {a} , A) <1}.

Proof.

By Proposition 2.2, we have that

$I (B, C) = H (C) - H (C / B) = H (B) - H (B / C) ⩾ 0 .$

Hence ρ (B, C) ⩾0. Since

$\begin{matrix} I (B, C)^{2} & = (H (C) - H (C / B)) (H (B) - H (B / C)) \\ ⩽ H (B) H (C), \end{matrix}$

we know that $I (B, C) ⩽ \sqrt{H (B)} \sqrt{H (C)}$ . Therefore ρ (B, C) ⩽1.

If random vectors B and C are independent, then H (B/C) = H (B), H (C/B) = H (C). It follows that I (B, C) =0. Hence ρ (B, C) =0.

Suppose that the probability distribution of B is same as the probability distribution of C, then the joint probability distribution of B and C is also same as the probability distribution of B (or C). Hence the conditional probability distribution of B given C and the conditional probability distribution of C given B are taking value 0 or 1. Hence the conditional information entropy H (B/C) = H (C/B) =0. It follows that $I (B, C) = \sqrt{H (B)} \sqrt{H (C)}$ . Therefore ρ (B, C) =1.

Conversely, suppose that ρ (B, C) =1. Then H (B/C) = H (C/B) =0. By the definition of conditional information entropy, we know that p (b_i, c_j) =0 or p (b_i, c_j) = p (b_i) = p (c_j) for any b_i ∈ B and c_j ∈ C. This shows that the probability distribution of B is same as the probability distribution of C.

a is indispensable w.r.t. A if and only if the probability distribution of A - {a} is same as the probability distribution of A, and if and only if ρ (A, A - {a}) =1 by (3).

By the definition of core and (4), we concludes Core (A) = {a ∈ A|ρ (A - {a} , A) <1}.

Definition 3.3. Let ((U, P) , A, V, F) be a random information system. For C ⊆ A, a ∈ A - C, the correlation coefficient of a w.r.t. C is defined as $η_{C} (a) = ρ (C \cup {a}, C) .$

Proposition 3.4.

0 ⩽ η_C (a) ⩽1;

Core (A) = {a ∈ A|η_A-{a} (a) <1};

If C ⊆ B, then η_C (a) ⩽ η_B (a).

Proof. The proof of (1) and (2) are obviously, in the following we prove that (3).

By the properties of information entropy, we have that if C ⊆ B then H (C) ⩽ H (B), H (a/B) ⩽ H (a/C). Hence $\begin{matrix} η_{C} (a) & = & ρ (C \cup {a}, C) = \frac{I (C \cup {a}, C)}{\sqrt{H (C \cup {a})} \sqrt{H (C)}} \\ = & \frac{H (C)}{\sqrt{H (C \cup {a})} \sqrt{H (C)}} = \frac{\sqrt{H (C)}}{\sqrt{H (C \cup {a})}} \\ = & \sqrt{\frac{H (C)}{H (C) + H (a / C)}} = \sqrt{\frac{1}{1 + \frac{H (a / C)}{H (C)}}} \\ ⩽ & \sqrt{\frac{1}{1 + \frac{H (a / B)}{H (B)}}} = η_{B} (a) . \end{matrix}$

Example 3.5. We consider the car information system as shown in Example 2.5.

ρ (A - {a₁} , A) = ρ (A - {a₃} , A) =1, ρ (A - {a₂} , A) =0.943. Let C = {a₂, a₃} , $η_{C} (a_{1}) = \sqrt{\frac{1.906}{2.25}} = 0.9023$ , $η_{C} (a_{4}) = \sqrt{\frac{1.906}{2.25}} = 0.9023$ .

3.2 Correlation coefficient of attribute set w.r.t. the decision attribute in random decision information system

Definition 3.6. Let ((U, P) , A ∪ D, V, F) be a random decision information system and B, C ⊆ A. Denote $I (D, C / - B) = H (B) - H (D / - (B \cup C)) .$

Define a correlation ρ (C/B) of two attribute subsets B and C w.r.t. the decision attribute D as follows: $ρ (C / B) = \frac{I (D, C / B)}{H (D / B)},$ and if H (D/B) =0, then set ρ (C/B) =0.

Lemma 3.7. Let ((U, P) , A ∪ D, V, F) be a random decision information system and C ∪ {a} ⊆ A. If the probability distribution of C and C ∪ {a} satisfy: a term (or some terms) in C can be represented as the sum of some terms in C ∪ {a}, and the rest terms are the same. Then H (D/(C ∪ {a})) ⩽ H (D/C).

Proof. We assume that $v^{(a)} = {v_{1}^{(a)}, v_{2}^{(a)}}$ and there only is a term in probability distribution of C can be represented as the sum of some terms in probability distribution of C ∪ {a}. We denote simply

$\begin{matrix} (v_{1}^{(a)}) = {x | F (x, a) = v_{1}^{(a)}}, \\ [v^{(a)}]_{b \in C \cup {a}} = {x | F (x, b) = v^{(b)}, b \in C \cup {a}}, \\ ([v^{(b)}]_{b \in C}, v^{(a)}) = {x | F (x, b) = v^{(b)}, b \in C, F (x, a) = v^{(a)}} \\ (v^{(d)}, [v^{(b)}]_{b \in C}) = {x | F (x, d) = v^{(d)}, d \in D, \\ F (x, b) = v^{(b)}, b \in C}, \\ (v^{(d)}, [v^{(b)}]_{b \in C}, v_{1}^{(a)}) = {x | F (x, d) = v^{(d)}, d \in D, \\ F (x, b) = v^{(b)}, b \in C, F (x, a) = v_{1}^{(a)}} . \end{matrix}$

then we have

$\begin{matrix} P ([v_{j_{0}}^{(a)}]_{b \in C \cup {a}}) = P ([v_{j_{0}}^{(a)}]_{b \in C}, v_{1}^{(a)}) + P ([v_{j_{0}}^{(a)}]_{b \in C}, v_{2}^{(a)}), \\ P (v^{(d)}, [v_{j_{0}}^{(a)}]_{b \in C \cup {a}}) = P (v^{(d)}, [v_{j_{0}}^{(a)}]_{b \in C}, v_{1}^{(a)}) \\ + P (v^{(d)}, [v_{j_{0}}^{(a)}]_{b \in C}, v_{2}^{(a)}) . \end{matrix}$

Hence $\begin{matrix} H_{Δ} = H (D / C) - H (D / (C \cup {a})) \\ = - \sum_{v^{(d)}} \sum_{v^{(b)}} P (v^{(d)}, [v^{(b)}]_{b \in C}) {log}_{2} \frac{P (v^{(d)}, [v^{(b)}]_{b \in C})}{P ([v^{(b)}]_{b \in C})} \\ + \sum_{v^{(d)}} \sum_{v^{(b)}} P (v^{(d)}, [v^{(b)}]_{b \in C \cup {a}}) {log}_{2} \frac{P (v^{(d)}, [v^{(b)}]_{b \in C \cup {a}})}{P ([v^{(b)}]_{b \in C \cup {a}})} \\ = - \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C})}{P ([v_{j_{0}}^{(b)}]_{b \in C})} \\ + \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})} \\ + \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})} \\ = - \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C})}{P ([v_{j_{0}}^{(b)}]_{b \in C})} \\ - \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C})}{P ([v_{j_{0}}^{(b)}]_{b \in C})} \\ + \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})} \\ + \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)}) {log}_{2} \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})} \\ = \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) {log}_{2} (\frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})} \\ \times \frac{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) + P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) + P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}) \\ + \sum_{v^{(d)}} P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) {log}_{2} (\frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})} \\ \times \frac{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) + P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)}) + P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}) . \end{matrix}$

In the following we denote simply

$p_{1} = P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})$ , $p_{2} = P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})$ , $q_{1} = P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})$ , $q_{2} = P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C},$ $v_{2}^{(a)})$ .

Then

$\begin{matrix} H_{Δ} & = & \sum_{v^{(d)}} (p_{1} {log}_{2} (\frac{p_{1}}{q_{1}} \times \frac{q_{1} + q_{2}}{p_{1} + p_{2}}) + p_{2} {log}_{2} (\frac{p_{2}}{q_{2}} \times \frac{q_{1} + q_{2}}{p_{1} + p_{2}})) \\ = & \sum_{v^{(d)}} (p_{1} {log}_{2} (\frac{p_{1} + λ p_{2}}{p_{1} + p_{2}}) + p_{2} {log}_{2} (\frac{λ^{- 1} p_{1} + p_{2}}{p_{1} + p_{2}})), \end{matrix}$

where $λ = \frac{q_{2}}{p_{2}} / - \frac{q_{1}}{p_{1}} = \frac{p_{1} q_{2}}{p_{2} q_{1}}$ . Denote $f_{d} = p_{1} {log}_{2} (\frac{p_{1} + λ p_{2}}{p_{1} + p_{2}}) + p_{2} {log}_{2} (\frac{λ^{- 1} p_{1} + p_{2}}{p_{1} + p_{2}}) .$

Then $\frac{{df}_{d}}{d λ} = \frac{p_{1} p_{2}}{p_{1} + λ p_{2}} - \frac{p_{1} p_{2}}{λ (p_{1} + λ p_{2})} .$

Hence ${\begin{matrix} \frac{{df}_{d}}{d λ} < 0, 0 < λ < 1, \\ \frac{{df}_{d}}{d λ} = 0, λ = 1, \\ \frac{{df}_{d}}{d λ} > 0, λ > 1 . \end{matrix}$

Thus when $λ = \frac{q_{2}}{p_{2}} / - \frac{q_{1}}{p_{1}} = 1$ the function f_d takes the minimum value f_d|_λ=1 = 0. Therefore only if $\frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{1}^{(a)})} = \frac{P (v^{(d)}, [v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}{P ([v_{j_{0}}^{(b)}]_{b \in C}, v_{2}^{(a)})}$ we have H_Δ = 0, in other cases H_Δ > 0. This shows the Lemma 3.7.

Theorem 3.8. If H (D/(C ∪ {a})) = H (D/C), then the conditional distribution P (D/(C ∪ {a})) = P (D/C).

Proof. According to the Lemma 3.7, the conditional information entropy increases monotonically with the number of condition attributes, and only when the conditional probability terms of the added attribute relative to the decision attribute are equal to each other the conditional information entropy can not change. Since H (D/(C ∪ {a})) can be computed by adding the conditional attribute a to C, we know that if H (D/(C ∪ {a})) = H (D/C) then the conditional probability terms of conditional attributes set C relative to the decision attributes D are equal to the conditional probability terms of conditional attributes set C ∪ {a} relative to the decision attributes D. Hence after adding the conditional attribute a the conditional probability terms of each conditional attribute values will not change. Therefore P (D/(C ∪ {a})) = P (D/C).

Theorem 3.9. Let ((U, P) , A ∪ D, V, F) be a random decision information system and B, C ⊆ A. Then

0 ⩽ ρ (C/B) ⩽1;

If C ⊆ B then ρ (C/B) =0;

ρ (C/B) =1 if and only if the probability distribution of B ∪ C is the same as the probability distribution of D.

Proof.

By Lemma 3.7 we have H (D/(B∪ C)) ⩽ H (D/B) then I (D, C/B) ⩾0 and I (D, C/B) = H (D/B) - H (D/(C ∪ B)) ⩽ H (D/B). Hence we obtain 0 ⩽ ρ (C/B) ⩽1.

If C ⊆ B then H (D/(B ∪ C)) = H (D/B). Thus I (D, C/B) =0, so ρ (C/B) =0.

If the probability distribution of B ∪ C is the same as the probability distribution of D, then the joint probability distribution P (B ∪ C ∪ D) is the same as the probability distribution of P (D). Hence the conditional probability distribution P (D/(B ∪ C)) taking value 0 or 1. This shows that H (D/(B ∪ C)) =0, so I (D, C/B) = H (D/B). Therefore ρ (C/B) =1.

Conversely, if ρ (C/B) =1 then H (D/(B ∪ C)) =0. By the definition of conditional entropy we have that P ({a_i} , {d_j} _{d_j∈D}) =0 or P ({a_i} , {d_j} _{d_j∈D}) = P ({d_j} _{d_j∈D}) for each attribute value a_i of B ∪ C and each values set {d_j} _{d_j∈D} of D. This shows that the probability distribution of B ∪ C is the same as the probability distribution of D.

4 Attribute reduction methods based on correlation coefficients

4.1 Attribute reduction based on correlation coefficients in a random information system

Let Q = {a₁, a₂, ⋯ , a_q} and a ∈ Q. If the probability distribution of Q - {a} is same as the probability distribution of Q, then a is called dispensable w.r.t. Q else a is called indispensable. If every attribute in Q is indispensable then Q is called an indispensable attribute subset. The set of allA-indispensable attributes of A is called a core of A, denote it by Core (A).

Definition 4.1. Let ((U, P) , A, V, F) be a random information system and Q ⊆ A. If Q is an indispensable attributes subset, the probability distribution of Q is equal to the probability distribution of A and the probability distribution of every subset of Q is not equal to the probability distribution of A, then Q is referred to as a reduction of A.

Obviously, an attribute set A may have more than one reduction, the intersection of all reduction is just the core of A.

By the Proposition 3.2 and 3.4, we have the following theorem.

Theorem 4.2. Let ((U, P) , A, V, F) be a random information system. For C ⊆ A, if

H (C) = H (A),

∀a ∈ C, η_C (a) <1,

then C is a reduction of A.

Using Theorem 4.2, we can give the following algorithm for attribute reduction.

Algorithm 4.3. Attribute reduction algorithm for a random information system based on attribute correlation coefficients (CCAR)

Input: A random information system ((U, P) , A, V, F).

Output: An attribute reduction Q of A.

Step 1. Computing the probability distribution of A.

Step 2. Computing the information entropy H (A) of A.

Step 3. Computing the core of A: Core (A) = {a ∈ A|η_A-{a} (a) <1}. If H (Core (A)) = H (A) then the algorithm terminates and Core (A) is the minimal reduction else go to Step 4.

Step 4. (Begin with Core (A), construct the attributes subset C of A by adding continuously the attribute with the minimum correlation coefficient)

Set C : = Core (A).

While H (C) ≠ H (A) Do

∀a ∈ A - C, computing η_C (a),

take attribute a satisfying η_C (a) = min{η_C (a′) |a′ ∈ A - C}, and let C : = C ∪ {a},

compute H (C).

Endwhile

Step 5. (Get a attribute reduction Q of A)

Set C′ = C - Core (A) , |C′| = N,

For i = 1 to N Do

delete the ith attributes a_i from C′,

compute H (C′ ∪ Core (A)),

if H (C′ ∪ Core (A)) ≠ H (A) then C′ : = C′ ∪ {a_i}.

Endfor

Step 6. Let Q : = C′ ∪ Core (A). The algorithm terminates, and Q is a reduction of A.

In the following we discuss the time complexity of the algorithm CCAR. The time complexity of a traditional heuristic reduction algorithm based on information entropy given in [14] is O (|A|²|U| + |A||U|²), which include the computational time of partition and entropy.

At Step 1, the time complexity of computing the probability distribution of A is O (|A| (∑_{a_k∈A}v_k)), where v_k is the number of attribute value of attribute a_k. In a large decision information system, the values of attribute a_k are usually not particularly scattered, hence we obtain ∑_{a_k∈A}v_k < |U| [29]. Thus the time complexity of computing the probability distribution of A is usually less than O (|A||U|).

At Step 2, the time complexity of computing H (A) is O (∑_{a_k∈A}v_k), which is less than O (|U|).

At Step 3, all the η_A-{a} (a) need to be computed we know the time complexity of computing Core (A) is O (|A||U|).

At Step 4, the time complexity of computing all η_C (a)(a ∈ A, C ⊆ A) is (|A| + (|A|-1) + ⋯ +1) × |U| = O (|A|²|U|). The time complexity to choose minimum relatively correlation attribute is $((| A | - 1) + (| A | - 2) + \dots + 1) \times \frac{| U |}{2} = O (| A |^{2} | U |)$ . The time complexity of computing all H (A) is O (|A||U|). So the price of step 4 is O (|A|²|U|).

At Step 5, the time complexity of computing all H (C′ ∪ Core (A)) is less than O (|A||U|).

Hence the time complexity of algorithm CCAR is O (|A|²|U|).

Example 4.4. Compute the attribute reduction of the car information system in Example 2.5 by using CCAR.

Step 1A. Computing the probability distribution of A (omitted).

Step 2A. Computing the joint information entropy of A: H (A) =2.25.

Step 3A. By computing we have that η_A-{a₁} (a₁) = η_A-{a₃} (a₃) =1, η_A-{a₄} (a₄) =1, η_A-{a₂} (a₂) =0.943. Hence Core (A) = {a₂}; Since H (Core (A)) =0.955. H (Core (A)) ≠ H (A), go to Step 4A.

Step 4A. Set C : = Core (A) = {a₂}. Since H (Core(A)) ≠ H (A) we need to compute η_C (a₁) = ρ ({a₁, a₂} , {a₂}) =0.7389, η_C (a₃) =0.7078, η_C (a₄) =0.7389. The smallest one in {η_C (a₁) , η_C (a₃) , η_C (a₄)} is η_C (a₃), and hence we take a′ = a₃, C : = C∪ {a₃} = {a₂, a₃}. By computing we have that H (C)= 1.906.

Since H (C) ≠ H (A) we compute η_C (a₁) = ρ ({a₁, a₂, a₃} , {a₂, a₃}) = 0.9203, η_C (a₄) =0.9203. The smallest one in {η_C (a₁) , η_C (a₄)} is η_C (a₄) (or η_C (a₁)), and hence we take a′ = a₄, C : = C ∪ {a₄} = {a₂, a₃, a₄}. By computing we have that H (C) =2.25. Since H (C) = H (A), go to Step 5A.

Step 5A. Set C′ : = C - Core (A) = {a₃, a₄}, N : = |C′|=2.

Firstly, we take a_i = a₃, C′ : = C′ - {a₃} = {a₄}.By computing we have that H (C′ ∪ Core (A))= H ({a₂, a₄}) =1.75. Since H (C′∪ Core (A)) ≠H (A), we get C′ : = C′ ∪ {a₃} = {a₃, a₄}.

Second, we take a_i = a₄, C′ : = C′ - {a₄} = {a₃}. By computing we have that = H ({a₂, a₃}) =1.906. Since H (C′ ∪ Core (A))≠H (A), we get C′ : = C′ ∪ {a₃} = {a₃, a₄}.

Step 6A. Q : = C′ ∪ Core (A) = {a₂, a₃, a₄}. The algorithm is completed, and Q = {a₂, a₃, a₄} is a reduction of A.

The process of attribute reduction are simply listed in Table 8.

Table 8
Attribute reduction process of the car information system

Step 1A Computing the probability distribution of A

Step 2A Computing H (A) =2.25

Step 3A Finding Core (A) = {a₂}

Step 4A Computing the possible reduction sets step by step: C : = {a₂, a₃}, C : = {a₂, a₃, a₄}

Step 5A Computing the non-core reduction set C′ = {a₃, a₄}

Step 6A Getting the reduction Q = {a₂, a₃, a₄}

4.2 Attribute reduction based on correlation coefficients in a random decision information system

Let ((U, P) , A ∪ D, V, F) be a random decision information system. For C ⊆ A, attribute subset C is said consistent with the decision attribute subset D, if each probability term of the probability distribution P (D) of D is same as the probability term in P (C), or it can be expressed as the sum of some probability terms in P (C). If a conditional attribute set A is consistent w.r.t. decision attribute D, we call it as consistent random decision information system. For C ⊆ A and a ∈ C, if the conditional probability distribution P (D/(C - {a})) and P (D/C) are the same, then a is called dispensable w.r.t. the decision attribute subset D, otherwise it is called indispensable. If each attribute in C is indispensable, then C is called an indispensable attribute set. The set of all the indispensable attributes of A is called the core of A and is denoted by Core (A).

Definition 4.5. Let ((U, P) , A ∪ D, V, F) be a random decision information system and Q ⊆ A. If Q is an indispensable attribute subset, the conditional probability distribution P (D/Q) is equal to the conditional probability distribution of P (D/A) and the conditional probability distribution of every subset of Q is not equal to the conditional probability distribution of P (D/A), then Q is referred to as a reduction of A.

Theorem 4.6. Suppose that ((U, P) , A ∪ D, V, F) is a random decision information system, C ⊆ A, then

a ∈ C is dispensable if and only if ρ ({a}/ - (C - {a})) =0.

C is consistent w.r.t. decision attribute D, if and only if for any a ∈ C, ρ ({a}/ - (C - {a})) =1.

Core (A) = {a ∈ A|ρ ({a}/ - (A - {a})) >0}.

Proof.

If a is dispensable, then the conditional probability distributions P (D/C - {a}) are the sames as P (D/A). Then H (D/C - {a}) = H (D/C). Hence I (D, {a}/ - C - {a}) =0. Thus ρ ({a}/ - (C - {a})) =0.

Conversely, let ρ ({a}/ - C - {a}) =0. ThenI (D, {a}/ - C - {a}) =0. This means that H (D/C - {a}) = H (D/C). By Proposition 3.6 we have P (D/ - C) = P (D/ - C ∪ {a}). Thus a is dispensable.

Because C is consistent w.r.t. decision attribute D, a term in P (D) equals to a term in P (C) or equals to the sum of some terms in P (C). Hence P (C) = P (C ∪ D). Then

$H (D / C) = - \sum P (C \cup D) log \frac{P (C \cup D)}{P (C)} = 0 .$

Hence $\begin{matrix} ρ ({a} / - (C - {a})) = \frac{I (D, {a} / (C - {a}))}{H (D / (C - {a}))} \\ = \frac{H (D / (C - {a})) - H (D / C)}{H (D / (C - {a}))} = \frac{H (D / (C - {a}))}{H (D / (C - {a}))} = 1 . \end{matrix}$

Conversely, let ρ ({a}/ - C - {a}) =1. Then $H (D / C) = - \sum P (C \cup D) log \frac{P (C \cup D)}{P (C)} = 0$ . This means that each term in the above equation is 0. Hence P (C) = P (C ∪ D). Therefore C is consistent w.r.t. decision attribute D.

(3) By the mean of Core (A) and (1), we can obtain it.

By Theorem 4.6, the below conclusion is obtained.

Theorem 4.7. Let ((U, P) , A ∪ D, V, F) be a random decision information system. For C ⊆ A, if

H (D/ - A) = H (D/ - C),

∀a ∈ A, ρ ({a}/ - (C - {a})) >0,

then C is a reduction of A.

Based on the Theorem 4.7, we give an algorithm for attribute reduction in random decision information systems.

Algorithm 4.8. Attribute reduction algorithm for a random decision information system based on attribute correlation coefficients (CCDAR)

Input: A random decision information system ((U, P) , A ∪ D, V, F).

Output: Reduction Q of A.

Step 1. Compute the probability distribution of conditional attribute set A.

Step 2. Compute the conditional information entropy H (D/A) of A.

Step 3. Compute Core (A) = {a ∈ A|η_A-{a} (a) <1}.

If H (D/Core (A)) = H (D/A), then the algorithm terminates (Core (A) is the reduction).

Step 4. (Begin with Core (A), construct the attributes subset C of A by adding continuously the attribute with the minimum correlation coefficient) $C : = Core (A) .$

While H (D/C) ≠ H (D/A) Do

For each a ∈ A - C, compute ρ ({a}/ -(C - {a})),

Select the attribute a such that ρ ({a}/ -(C - {a})) = min {ρ ({b}/ - (C - {b})) |b ∈ A - C} and C : = C ∪ {a},

Compute H (D/C).

Endwhile

Step 5. (Getting the relative reduction Q of A) $C^{'} : = C - Core (A), | C^{'} | = N .$

For i = 1 to N Do

Delete the attribute a_i from C′,

Compute H (D/C′ ∪ Core (A)),

If H (D/C′ ∪ Core (A)) ≠ H (D/A) then C′: = C′ ∪ {a_i}.

End for

Step 6. Let Q : = C′ ∪ Core (A). The algorithm terminates, and Q is a A reduction of conditional attribute subset.

In the following we discuss the time complexity of the algorithm CCDAR.

At Step 1, the time complexity of computing the probability distribution of conditional attribute set A is O (|A| (∑_{a_k∈A}v_k)), where v_k is the number of attribute value of attribute a_k. In a large decision information system, the values of attribute a_k are usually not particularly scattered, hence we obtain ∑_{a_k∈A}v_k < |U| [29]. Thus the time complexity of computing the probability distribution of conditional attribute set A less than O (|A||U|).

At Step 2, the time complexity of computing H (D/A) is O (∑_{a_k∈A∪D}v_k), followed the analysis in the above step we obtain ∑_{a_k∈A∪D}v_k < |U|. Hence the time complexity of computing H (D/A) less than O (|U|).

At Step 3, need to compute ρ ({a}/ - (A - {a})) for all a ∈ A in computing Core (A), the time complexity of computing Core (A) is O (|U||A|).

At Step 4, the time complexity of computing all ρ ({a}/ - (C - {a}))(a ∈ C, C ⊆ A) is O ((|A| + (|A|-1) + ⋯ +1) |U|) = O (|A|²|U|).

At Step 5, the time complexity of computing all H (D/C′ ∪ Core (A)) is less than O (|A||U|).

Hence the time complexity of algorithm CCDAR is O (|A|²|U|).

In the following we give an example to illustrate the application of algorithm.

Table 9
A car decision information system

U a ₁ a ₂ a ₃ a ₄ d

u ₁ low cro. gas. low poor

u ₂ low spa. die. mid. good

u ₃ hig. cro. die. hig. good

u ₄ hig. cro. die. mid. poor

u ₅ low spa. gas. mid. good

U	a ₁	a ₂	a ₃	a ₄	d
u ₁	low	cro.	gas.	low	poor
u ₂	low	spa.	die.	mid.	good
u ₃	hig.	cro.	die.	hig.	good
u ₄	hig.	cro.	die.	mid.	poor
u ₅	low	spa.	gas.	mid.	good

Example 4.9. A car decision information system as shown in Table 9, where a₁ =“price”, a₂ =“internal design”, a₃ =“engine”, a₄ =“acceleration performance”, hig. = high, cro. = crowd, spa. = spacious, gas. = gasoline, die. = diesel, mid. = middle. A normal probability distribution P on U as follows: P ({u₁}) = 1/ - 4, P ({u₂}) = 1/ - 4, P ({u₃}) = 1/ - 8, P ({u₄}) = 1/ - 8, P ({u₅}) = 1/ - 4.

We find the attribute reduction of the conditional attributes set A by using CCDAR

Step lA. Computing the probability distribution of A (omitted).

Step 2A. Computing the conditional information entropy of A: H ({d}/ - A) =0.

Step 3A. By computing we have ρ ({a₁}/ - (A - {a₁}))= 0, ρ ({a₂}/ - (A - {a₂})) =0, ρ ({a₃}/ - (A - {a₃})) =1, ρ ({a₄}/ - (A - {a₄})) =1. Hence Core (A) = {a₃, a₄}. Since H ({d}/ - Core (A)) =0.451, H ({d}/ -Core (A)) ≠ H ({d}/ - A), go to Step 4A.

Step 4A. Set C : = Core (A) = {a₃, a₄}. Since H ({d}/ - Core (A)) ≠ H (A), we need to compute ρ ({a₁}/ - A - {a₁}) = ρ ({a₁}/ - {a₃, a₄}) =1, ρ ({a₂}/ -A - {a₂}) =1. Taking a = a₁, C : = C ∪ {a₁} = {a₁, a₃, a₄}. By computing we have H ({d}/ - C) =0. Since H ({d}/ - A) = H ({d}/ - C), go to Step 5A.

Step 5A. Set C′ : = C - Core (A) = {a₁}, N : =|C′|=1. Taking a_i = a₁, C′ : = C′ - {a₁} = φ. By computing we have H ({d}/ - C′ ∪ Core (A)) = H ({d}/ - {a₁, a₃, a₄}) =0.344. Since H ({d}/ - C′∪Core (A)) ≠ H ({d}/ - A), we get C′ : = C′ ∪ {a₁} = {a₁}.

Step 6A. Let Q = C′ ∪ Core (A) = {a₁, a₃, a₄}. Algorithm is completed, and Q = {a₁, a₃, a₄} is a reduction of A.

The process of attribute reduction are simply listed in Table 10.

Table 10

Attribute reduction process of the car decision information system

Step 1A	Computing the probability distribution of A
Step 2A	Computing H ({d}/ - A) =0
Step 3A	Finding Core (A) = {a₃, a₄}
Step 4A	Computing the possible reduction sets step by step: C : = {a₁, a₃, a₄}
Step 5A	Computing the non-core reduction set C′ = {a₁}
Step 6A	Getting the reduction Q = {a₂, a₃, a₄}

5 Experiments

To show the utility of the algorithm CCDER (Algorithm 4.8) we implement this algorithm by using MTLAB programming language. The computing environment is a PC (Pentium T3400 2.16G CPU, 2-GB memory, Windows XP operating system). It is hard to find an instances of large random information system, so the test data sets are selected from UCI machine learning repository (http://archive.ics.uci.edu/ml/), which are be viewed as random decision information systems with the uniform probability distribution, to compute the probability distribution. The description of data sets is shown in Table 11. In the data sets, Mushroom, Soybean and Dermatolog are three data sets with missing values, and for a uniform treatment of all data sets, we remove the objects with missing values. Connect-4 has a much large number of objects relative to the other five data sets, so we select the first 20% of them. In these experiments, we select two attribute reduction algorithms, one is the accelerated algorithm of attribute reduction which remains the conditional entropy of target decision unchanged (FSPA-SCE) [14], and the other the incremental attribute reduction based on relational matrix (IARRMKG) [28].

Table 11
Data sets description

Data sets Samples number Attributes number

Soybean 254 35

Dermatology 358 34

Tic-tac-toc 958 9

Mushroom 5644 22

Chess 3196 36

Connect-4 13512 42

Data sets	Samples number	Attributes number
Soybean	254	35
Dermatology	358	34
Tic-tac-toc	958	9
Mushroom	5644	22
Chess	3196	36
Connect-4	13512	42

The test results are listed in the Tables 12 and 13. As we can see that the reduction effect of the algorithms CCDAR, FSPA-SCE and IARRMKG are almost same, but the computational time of the algorithm CCDER is better than the algorithms FSPA-SCE and IARRMKG.

Table 12

Comparison of computational time (second) between different algorithms

Data sets	FSPA-SCE	IARRMKG	CCDAR
Soybean	11.35	15.64	10.98
Dermatology	2.32	3.18	2.26
Tic-tac-toc	4.56	6.48	4.48
Mushroom	236.78	1286.25	205.87
Chess	165.83	892.16	139.46
Connect-4	520.24	2786.80	476.32

Table 13

Comparison of attribute reduction number between different algorithms

Data sets	Before reduction	After reduction
		FSPA-SCE	IARRMKG	CCDAR
Soybean	35	15	16	16
Dermatology	34	11	12	10
Tic-tac-toc	9	8	8	8
Mushroom	22	4	5	5
Chess	36	29	30	29
Connect-4	42	33	33	32

6 Conclusions

In this paper, we study two new correlation coefficients and apply them to the attributes reduction. The concepts of information entropy about logarithmic form, conditional information entropy, joint information entropy and mutual information entropy are introduced and the connection between them is analyzed. Two new correlation coefficients are introduced, one is ρ (B, C) to describe the correlation between two attribute subsets B and C in random information system, and the other is ρ (C/B) of a conditional attributes set B relative to another condition attributes set C w.r.t. the decision attributes set D in random information system. The properties of correlation coefficient are discussed, and the concepts of indispensable attributes, consistent attributes and core attributes in random information systems or random decision information systems are described by the correlation coefficient. Based on the correlation coefficient ρ (B, C) we propose a new attribute reduction algorithm CCAR in random information systems, and based on the correlation coefficient ρ (C/B) we propose a new attribute reduction algorithm CCDAR in random decision information systems. We analyze the time complexity of algorithm CCAR and algorithm CCDAR. The listed examples and the experimental results show that the algorithms are effective.

The present paper focuses only on studying the correlation coefficients w.r.t. Shannon’s information entropy, which are used to describe indispensable attributes, consistent attributes and core attributes, etc, and are applied to attribute reduction in random information systems or random decision information systems respectively. In order to respond to the demand of updating dynamically the attribute reduction of information systems or decision information systems in big data environment, our future work will discuss two correlation coefficients ρ (B, C) and ρ (C/B) change with objects, attributes and their values, and then propose the application of correlation coefficients to the intersection of high-dimension data sets, distributed computing, big data mining and deep learning, etc.

Footnotes

Acknowledgments

This work has been supported by the Industry-University-Research Innovation Fund of Ministry of Education (No. 2018A02014), the Natural Science Foundation of Hunan Province (No. 2018JJ2371, No. 2017JJ2241).

References

Guyon

, Elisseeff

, An introduction to variable and feature selection, Journal of Machine Learning Research 3 (2003), 1157–1182.

Eroglua

D.Y.

, Kilic

, A novel hybrid genetic local search algorithm for feature selection and weighting with an application in strategic decision making in innovation management, Information Sciences 405 (2017), 18–32.

Pawlak

, Rough sets theoretical aspects of reasoning about data, Bosten, Kluwer Academic Publishers 1991.

Zhang

W.X.

, Liang

, Wu

W.Z.

, Information systems and knowledge discoveries, Beijing, Science in China Press, 2003.

Liang

J.Y.

, Xu

Z.B.

, The algorithm on knowledge reduction in incomplete information systems, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(1) (2002), 95–103.

W.Z.

, Attribute reduction based on evidence theory in incomplete decision systems, Information Science 178 (2008), 1355–1371.

Miao

D.Q.

, Wang

, An information representation of the concepts and operations in rough set theory, Journal of Software 10(2), (1999), 113–116.

, Zhang

J.L.

, Rough set models based on random fuzzy sets and belief function of fuzzy sets, International Journal General Systems 41 (2012), 123–141.

Miao

D.Q.

, Hu

G.R.

, A heuristic algorithm for reduction of knowledge, Journal of Computer Research and Development 36(6) (1999), 681–684.

10.

Wang

G.Y.

, Yu

, Yang

D.C.

, Decision table reduction based on conditional information entropy, Chinese Journal of Computers 25(7) (2002), 759–766.

11.

Q.H.

, Che

X.J.

, Zhang

et al, Rank entropy based decision trees for monotonic classification, IEEE Transactions on Knowledge and Data Engineering 24 (2012), 2052–2064.

12.

W.S.

, Hu

B.Q.

, Attribute reduction in ordered decision tables via evidence theory, Information Science 364-365 (2016), 91–110.

13.

Liang

J.Y.

, Wei

, Qian

Y.H.

, An incremental kernel solution method based on conditional entropy, System Engineering Theory and Practice 28(4) (2008), 81–89.

14.

Qian

Y.H.

, Liang

J.Y.

, Pedrycz

, Dang

C.Y.

, Positive approximation: An accelerator for attribute reduction in rough set theory, Artificial Intelligence 174 (2010), 597–618.

15.

Zhang

J.L.

, Liu

X.L.

, Fuzzy belief measure in random fuzzy information systems and its application to know-ledge reduction, Neural Computing and Applications 22 (2013), 1419–1431.

16.

Liu

H.T.

, Xu

X.Y.

, Xie

et al, Research on incremental attribute reduction algorithm under the information view, Micro Computer System Information 37(2) (2016), 375–380.

17.

Liu

, Liang

J.Y.

, Wei

et al, A scientific conditional entropy incremental algorithm for attribute reduction based on conditional entropy, Computer Science 38(1) (2011), 229–231.

18.

Batle

, Naseri

, Ghoranneviss

et al, Shareability of correlations in multiqubit states: Optimization of nonlocal monogamy inequalities, Physical Review A 95(3) (2017), 032123.

19.

Naseri

et al, A scheme for secure quantum communication network with authentication using GHZ-like states and cluster states controlled teleportation, Quantum Information Processing 14(11) (2015), 4279–4295.

20.

Farouk

, Batle

, Elhoseny

et al, Robust general N user authentication scheme in a centralized quantum communication network via generalized GHZ states, Frontiers of Physics 13(2) (2018), 130306.

21.

Farouk

, Zakaria

, Megahed

et al, A generalized architecture of quantum secure direct communication for N-disjointed users with authentication, Scientific Reports 5 (2015), 16080.

22.

Batle

, Ciftja

, Naseri

et al, Equilibrium and uniform charge distribution of a classical two-dimensional system of point charges with hard-wall confinement, Physica Scripta 92(5) (2017), 055801.

23.

Gao

, Guirao

J.L.G.

, Abdel-Aty

et al, An independent set degree condition for fractional critical deleted graphs, Discrete and Continuous Dynamical Systems-Series S 12(4-5) (2019), 877–886.

24.

Obada

A.-S.F.

, Abo-Kahla

D.A.M.

, Abdel-Aty

, The quantum computational speed of a single Cooper-pair box, Physica E: Low-Dimensional Systems and Nano-structures 43(10) (2011), 1792–1797.

25.

Lang

G.M.

, Cai

M.J.

, Fujita

, Xiao

Q.M.

, Related families-based attribute reduction of dynamic covering decision information systems, Knowledge-Based Systems (2018). doi:10.1016/j.knosys.2018.05.0198

26.

Chen

J.G.

, Li

K.L.

, Rong

H.G.

et al, A periodicity-based parallel time series prediction algorithm in cloud computing environments, Information Sciences (2018). doi:10.1016/j.ins.2018.06.045

27.

, Li

S.B.

, Information theory basis and its application, Beijing, Tsinghua University Press, 2005.

28.

Zhang

, Wang

, Hong

T.T.

, Incremental attribute reduction based on relational matrix, Journal of Chinese Computer Systems 39(5) (2018), 1000–1004.

29.

Z.Y.

, Liu

Z.P.

, Yang

B.R.

et al, A quick attribute reduction algorithm with complexity max(O (|C||U|) , O (|C|²|U/C|)), Chinese Journal of Computers 29(3) (2006), 391–399.

Attributes correlation coefficients and their application to attributes reduction

Abstract

Keywords

1 Introduction

2 Information entropy of attributes in random information systems

Table 1 Probability distribution of attribute a a v 1 ( a ) v 2 ( a ) ⋯ v m ( a ) p (a) p ( v 1 ( a ) ) p ( v 2 ( a ) ) ⋯ p ( v m ( a ) )

3.1 Correlation coefficient of attributes subset in random information system

3.2 Correlation coefficient of attribute set w.r.t. the decision attribute in random decision information system

4 Attribute reduction methods based on correlation coefficients

4.1 Attribute reduction based on correlation coefficients in a random information system

Table 9 A car decision information system U a 1 a 2 a 3 a 4 d u 1 low cro. gas. low poor u 2 low spa. die. mid. good u 3 hig. cro. die. hig. good u 4 hig. cro. die. mid. poor u 5 low spa. gas. mid. good

Table 11 Data sets description Data sets Samples number Attributes number Soybean 254 35 Dermatology 358 34 Tic-tac-toc 958 9 Mushroom 5644 22 Chess 3196 36 Connect-4 13512 42

Footnotes

Acknowledgments

References

Table 1
Probability distribution of attribute a

a $v_{1}^{(a)}$ $v_{2}^{(a)}$ ⋯ $v_{m}^{(a)}$

p ^(a) $p (v_{1}^{(a)})$ $p (v_{2}^{(a)})$ ⋯ $p (v_{m}^{(a)})$

Table 9
A car decision information system

U a ₁ a ₂ a ₃ a ₄ d

u ₁ low cro. gas. low poor

u ₂ low spa. die. mid. good

u ₃ hig. cro. die. hig. good

u ₄ hig. cro. die. mid. poor

u ₅ low spa. gas. mid. good

Table 11
Data sets description

Data sets Samples number Attributes number

Soybean 254 35

Dermatology 358 34

Tic-tac-toc 958 9

Mushroom 5644 22

Chess 3196 36

Connect-4 13512 42