A Review on Rough Set-Based Interrelationship Mining

Interrelationship mining, proposed by the authors, aims at extracting characteristics of objects based on interrelationships between attributes. Interrelationship mining is an extension of rough set-based data mining, which enables us to extract characteristics based on comparison of values of two different attributes such that “the value of attribute a is higher than the value of attribute b.” In this paper, we mainly review theoretical aspects of rough set-based interrelationship mining.

The authors would like to thank the anonymous reviewers for their valuable comments.This work was supported by JSPS KAKENHI Grant Number JP25330315.

Authors and Affiliations

1. College of Information and Systems, Muroran Institute of Technology, Mizumoto 27-1, Muroran, 050-8585, Japan

   Yasuo Kudo

2. Faculty of Science and Technology, Chitose Institute of Science and Technology, 758-65 Bibi, Chitose, 066-8655, Japan

   Tetsuya Murai

Corresponding author

Correspondence to Yasuo Kudo .

Editors and Affiliations

1. University of Skövde, School of Informatics University of Skövde, Skövde, Sweden

   Vicenç Torra

2. University of Skövde, School of Informatics University of Skövde, Skövde, Sweden

   Anders Dahlbom

3. Toho Gakuen , Tokyo, Japan

   Yasuo Narukawa

Proofs of Theoretical Properties

Proposition 1

Let S be a decision table, \(\mathsf{a},\mathsf{b}\in C\) be condition attributes in S, \(R\subseteq V_{\mathsf{a}}\times V_{\mathsf{b}}\) be a binary relation, and \(S_{int}\) be an information table \(S_{int}\) for interrelationship mining with respect to S such that \(R\in \{R_{\mathsf{a}\times \mathsf{b}}\}\). The following equality holds:

where \(IND_{S}(\mathsf{a}R \mathsf{b})\) is the indiscernibility relation for S defined by (12), and \(IND_{S_{int}}(\{\mathsf{a}\mathsf{R}\mathsf{b}\})\) is the indiscernibility relation for \(S_{int}\) by a singleton \(\{\mathsf{a}\mathsf{R}\mathsf{b}\}\) of an interrelated condition attribute defined by (2).

Proof

Suppose \((x,y)\in IND_{S}(\mathsf{a}R \mathsf{b})\) holds. By the definition of \(IND_{S}(\mathsf{a}R \mathsf{b})\) by (12), \(x\in R(\mathsf{a},\mathsf{b})\) holds if and only if \(y\in R(\mathsf{a},\mathsf{b})\) holds. Therefore, for the interrelated condition attribute \(\mathsf{a}\mathsf{R}\mathsf{b}\), it implies that either \(\rho (x,\mathsf{a}\mathsf{R}\mathsf{b})=\rho (y,\mathsf{a}\mathsf{R}\mathsf{b})=1\) or \(\rho (x,\mathsf{a}\mathsf{R}\mathsf{b})=\rho (y,\mathsf{a}\mathsf{R}\mathsf{b})=0\) holds, which concludes \((x,y)\in IND_{S_{int}}(\{\mathsf{a}\mathsf{R}\mathsf{b}\})\). The converse is also proved similarly.

Proposition 2

Let S be a decision table and \(S_{int}\) be an information table for interrelationship mining with respect to S. The following equality holds:

where \(IND_{S_{int}}(AT)\) is the indiscernibility relation for \(S_{int}\) by using all attributes in AT of the original decision table S, and \(IND_{S_{int}}(AT_{int})\) is the indiscernibility relation for \(S_{int}\) by using all attributes of \(S_{int}\) including interrelated condition attributes.

Proof

Because \(AT\subseteq AT_{int}\) by the definition of the information table \(S_{int}\) for interrelationship mining, \( IND_{S_{int}}(AT)\supseteq IND_{S_{int}}(AT_{int}) \) holds trivially. We show the converse set inclusion. Suppose \((x,y)\in IND_{S_{int}}(AT)\) holds. For any two attributes \(\mathsf{a},\mathsf{b}\in AT\) and any binary relation \(R\in \{R_{\mathsf{a}\times \mathsf{b}}\}\) such that \(R(\mathsf{a},\mathsf{b})\ne \emptyset \), the assumption \((x,y)\in IND_{S_{int}}(AT)\) implies that \(\rho (x,\mathsf{a})=\rho (y,\mathsf{a})\) and \(\rho (x,\mathsf{b})=\rho (y,\mathsf{b})\) hold. This implies that \((\rho (x,\mathsf{a}),\rho (x,\mathsf{b}))\in R\) holds if and only if \((\rho (y,\mathsf{a}),\rho (y,\mathsf{b}))\in R\) holds, i.e., \(x\in R(\mathsf{a},\mathsf{b})\) holds if and only if \(y\in R(\mathsf{a},\mathsf{b})\) holds. By the definition of attribute value assignment for interrelated attributes by (16), it concludes that \(\rho (x,\mathsf{a}\mathsf{R}\mathsf{b})=\rho (y,\mathsf{a}\mathsf{R}\mathsf{b})\) holds. Therefore, x is indiscernible from y by any interrelated attribute \(\mathsf{a}\mathsf{R}\mathsf{b}\) and \((x,y)\in IND_{S_{int}}(AT_{int})\) holds. This concludes the equality \( IND_{S_{int}}(AT)=IND_{S_{int}}(AT_{int}). \)

Corollary 1

Let S be a decision table and \(S_{int}\) be an information table for interrelationship mining with respect to S. For every decision class \(D\in \mathcal{D}\) of \(S_{int}\), The following equality holds:

where C is the set of all condition attributes of S and \(C_{int}=AT_{int}\setminus \{\mathsf{d}\}\) is the set of all condition attributes of \(S_{int}\) including interrelated condition attributes.

Proof

From the definitions of the decision table S, \(C=AT\setminus \{\mathsf{d}\}\) holds. By Proposition 2, it is easily confirmed that \(IND_{S_{int}}(C)=IND_{S_{int}}(C_{int})\) holds, which concludes \(\underline{C}(D)=\underline{C_{int}}(D)\) for every decision class \(D\in \mathcal{D}\) of \(S_{int}\).

Proposition 3

([7]) Let \(S_{int}\) be a decision table for interrelationship mining. If there exists a relative reduct \(A\subseteq AT_{int}\) of \(S_{int}\) that contains an interrelated attribute \(\mathsf{aRb}\), then there exists at least one relative reduct \(B\subseteq AT_{int}\) such that either \(\mathsf{a}\in B\) or \(\mathsf{b}\in B\) holds.

Proof

([7]) Suppose that the interrelated attribute \(\mathsf{aRb}\) by a binary relation R on \(V_{\mathsf{a}}\times V_{\mathsf{b}}\) appears in a relative reduct A. From the definition of relative reducts, there exist two elements \(x,y\in U\) such that x and y are discernible each other by A, however, x and y are not discernible by \(A'\mathop {=}\limits ^\mathrm{def}A\setminus \{\mathsf{aRb}\}\). This means that the values of x and y at \(\mathsf{aRb}\) are different each other, and without losing generality, we assume that \(\rho _{int}(x,\mathsf{aRb})=1\) and \(\rho _{int}(y,\mathsf{aRb})=0\). This assumption means \((\rho _{int}(x,\mathsf{a}), \rho _{int}(x,\mathsf{b}))\in R\) and \((\rho _{int}(y,\mathsf{a}), \rho _{int}(y,\mathsf{b}))\not \in R\) hold, respectively, which implies that either the values of x and y at \(\mathsf{a}\) are different or the values of x and y at \(\mathsf{b}\) are different. Again, without loosing generality, we assume that the values of x and y at \(\mathsf{a}\) are different. By this assumption, the subset \(A'\cup \{\mathsf{a}\}\) satisfies the condition 1) of relative reducts; the attribute \(\mathsf{a}\) can discern x from y and the subset \(A'\) can discern other elements that belong to different decision class each other. Moreover, the set \(B\subseteq A'\cup \{\mathsf{a}\}\) with no redundant attributes is a relative reduct and it is easily confirmed that \(\mathsf{a}\in B\). It concludes the proof.

Corollary 2

([7]) Let S be a decision table, and \(\mathsf{a}\) and \(\mathsf{b}\) be two condition attributes of S that do not appear in any relative reduct of S. Then, for any binary relation R on \(V_{\mathsf{a}}\times V_{\mathsf{b}}\) and the interrelated attribute \(\mathsf{a}\mathsf{R}\mathsf{b}\) by the binary relation R, the interrelated attribute \(\mathsf{a}\mathsf{R}\mathsf{b}\) does not appear in any relative reduct of the decision table \(S_{int}\) that are induced from the table S.

Proof

It is obvious from Proposition 3.

Proposition 4

([9]) Let \(B=\{\mathsf{a},\mathsf{b}\}\) be any set of two condition attributes in C, \(\mathsf{a}\mathsf{R}\mathsf{b}\in AT_{int}\) be an interrelated attribute based on the attributes \(\mathsf{a}, \mathsf{b}\in C\) and a binary relation \(R\subseteq V_{\mathsf{a}}\times V_{\mathsf{b}}\), and \(B'\subseteq AT_{int}\) be a set of attributes generated by replacing either the attribute \(\mathsf{a}\) or the attribute \(\mathsf{b}\) in B by the interrelated attribute \(\mathsf{a}\mathsf{R}\mathsf{b}\). The following equation holds:

Proof

Suppose that \(y\in [x]_B\) holds and let \(\rho (x,\mathsf{a})=v\) and \(\rho (x,\mathsf{b})=w\) be the values of x at the attributes \(\mathsf{a}\) and \(\mathsf{b}\), respectively. Because \(y\in [x]_B\), \(\rho (y,\mathsf{a})=v\) and \(\rho (y,\mathsf{b})=w\) also hold. In the binary relation \(R\subseteq V_{\mathsf{a}}\times V_{\mathsf{b}}\) that is used for constructing the interrelated attribute \(\mathsf{a}\mathsf{R}\mathsf{b}\in AT_{int}\), if \((v,w)\in R\) holds, it implies \( \rho (x,\mathsf{a}\mathsf{R}\mathsf{b}) = \rho (y,\mathsf{a}\mathsf{R}\mathsf{b}) =1 \); otherwise, if \((v,w)\not \in R\) holds, it implies \( \rho (x,\mathsf{a}\mathsf{R}\mathsf{b}) = \rho (y,\mathsf{a}\mathsf{R}\mathsf{b}) =0 \). Therefore, the object y is still indiscernible from x by replacing either \(\mathsf{a}\) or \(\mathsf{b}\) by \(\mathsf{a}\mathsf{R}\mathsf{b}\), which concludes \(y\in [x]_{B'}\).

Proposition 5

([9]) Suppose that \(B\subseteq AT_{int}\) is a subset of condition attributes in the information table \(S_{int}\) for interrelationship mining. For any two condition attributes \(\mathsf{a},\mathsf{b}\in B\), let a set \(B'\) be either \(B'=(B\setminus \{\mathsf{a}\})\cup \{\mathsf{a}\mathsf{R}\mathsf{b}\}\) or \(B'=(B\setminus \{\mathsf{b}\})\cup \{\mathsf{a}\mathsf{R}\mathsf{b}\}\). then the following inequality holds:

Proof

Let \(N_B\) and \(N_{B'}\) be the denominators of \(ACov(B)\) and \(ACov(B')\), respectively. By the definition of \(ACov(\cdot )\) by (9), it is sufficient to show \(N_{B'}\le N_B\). Let \(U/IND(B)\) and \(U/IND(B')\) be the sets of equivalence classes by the indiscernibility relations \(IND(B)\) and \(IND(B')\), respectively, and suppose that there are m equivalence classes in \(U/IND(B')\), i.e, there are m objects \(x_1,\ldots ,x_m\in U\) and \(U/IND(B')=\{[x_1]_{B'},\ldots ,[x_m]_{B'}\}\). By Proposition 4, for each equivalence class \([x_i]_{B'}\in U/IND(B')\), there exist \(k_i(\ge 1)\) equivalence classes \([y_{i_1}]_B,\ldots ,[y_{i_{k_i}}]_B\in U/IND(B)\) such that \([x_i]_{B'}=\bigcup _{j=i_1}^{i_{k_i}}[y_j]_B\) holds. Therefore, \(U/IND(B)=\{[y_{1_1}]_{B},\) \(\ldots ,[y_{1_{k_1}}]_{B},\) \(\ldots ,[y_{m_1}]_{B},\) \(\ldots ,[y_{m_{k_m}}]_{B}\}\). For each decision class \(D\in \mathcal{D}\), it is clear that \(D\cap [x_i]_{B'}\ne \emptyset \) holds if and only if there is at least one equivalence class \([y_{i_l}]_B\) such that \(D\cap [y_{i_l}]_B\ne \emptyset \) holds. This fact implies that \( |\{D\in \mathcal{D}\;|\;D\cap [x_i]_{B'}\ne \emptyset \}| \le \sum _{j=i_1}^{i_{k_i}}|\{D\in \mathcal{D}\;|\;D\cap [y_{j}]_B\ne \emptyset \}| \) holds, which concludes \(N_{B'}\le N_B\).

Corollary 3

([9]) Let B and \(B'\) in Proposition 5 be both relative reducts in the information table \(S_{int}\) for interrelationship mining such that \(ACov(B)\le ACov(B')\). The number of decision rules generated from \(B'\) is smaller than (or at least equal to) the number of decision rules generated from B.

Proof

It is obvious from Proposition 5.

Reprints and permissions

© 2017 Springer International Publishing AG

Policies and ethics