Rate of change analysis for interestingness measures

Abstract

The use of association rule mining techniques in diverse contexts and domains has resulted in the creation of numerous interestingness measures. This, in turn, has motivated researchers to come up with various classification schemes for these measures. One popular approach to classify the objective measures is to assess the set of mathematical properties they satisfy in order to help practitioners select the right measure for a given problem. In this research, we discuss the insufficiency of the existing properties in the literature to capture certain behaviors of interestingness measures. This motivates us to adopt an approach where a measure is described by how it varies if there is a unit change in the frequency count $(f_{11},f_{10},f_{01},f_{00})$, at different preexisting states of the counts. This rate of change analysis is formally defined as the first partial derivative of the measure with respect to the various frequency counts. We use this analysis to define two novel properties, unit-null asymptotic invariance (UNAI) and unit-null zero rate (UNZR). UNAI looks at the asymptotic effect of adding frequency patterns, while UNZR looks at the initial effect of adding frequency patterns when they do not preexist in the dataset. We present a comprehensive analysis of 50 interestingness measures and classify them in accordance with the two properties. We also present multiple empirical studies, involving both synthetic and real-world datasets, which are used to cluster various measures according to the rule ranking patterns of the measures. The study concludes with the observation that classification of measures using the empirical clusters shares significant similarities to the classification of measures done through the properties presented in this research.

Appendices

Appendix A

1.1 Illustrative example of the UNAI and UNZR framework using Lift

In this sections, we consider the behavior of the popular interestingness measure, Lift, under the UNAI and UNZR properties defined in the previous section. Lift is defined as follows:

$$\begin{aligned} \hbox {Lift}(L) = \frac{P(A \cap B)}{P(A)\cdot P(B)} = \frac{f_{11}(f_{11} + f_{01} + f_{10} + f_{00})}{(f_{10} + f_{11})(f_{01}+f_{11})} \end{aligned}$$

(6)

Differentiating w.r.t to $f_{11}$ and simplifying, we get

$$\begin{aligned} \frac{\partial (L)}{\partial f_{11}} = \frac{2f_{10}f_{11}f_{01} + f_{10}f_{01}(f_{10} + f_{00} +f_{01}) - f^2_{11}f_{00}}{(f_{10} +f_{11})^2(f_{01} + f_{11})^2} \end{aligned}$$

(7)

We check the UNAI property for Lift by considering the derivative as $f_{11} \rightarrow \infty$

$$\begin{aligned} L_{f_{11}}(\infty ) = \lim _{f_{11} \longrightarrow \infty } \frac{\partial L}{\partial f_{11}} = \lim _{f_{11} \longrightarrow \infty } \frac{2f_{10}f_{11}f_{01} + f_{10}f_{01}(f_{10} + f_{00} +f_{01}) - f^2_{11}f_{00}}{(f_{10} + f_{11})^2(f_{01} +f_{11})^2}\nonumber \\ \end{aligned}$$

(8)

After algebraic simplification, we can say that the above function is equal to zero for all feasible combinations of $f_{00}$, $f_{10}$ and $f_{01}$. Hence, we can say that Lift satisfies UNAI with respect to $f_{11}$. Similarly, we check for UNAI property with respect to $f_{00}$, $f_{10}$, $f_{01}$.

$$\begin{aligned} L_{f_{00}}(\infty )= & {} \lim _{f_{00} \longrightarrow \infty } \frac{\partial L}{\partial f_{00}} = \frac{f_{11}}{(f_{01} +f_{11})(f_{10}+f_{11})} \end{aligned}$$

(9)

$$\begin{aligned} L_{f_{10}}(\infty )= & {} \lim _{f_{10} \longrightarrow \infty } \frac{\partial L}{\partial f_{10}} = 0 \end{aligned}$$

(10)

$$\begin{aligned} L_{f_{01}}(\infty )= & {} \lim _{f_{01} \longrightarrow \infty } \frac{\partial L}{\partial f_{01}} = 0 \end{aligned}$$

(11)

Here, it is evident that this function is not equal to 0 for all possible values of $f_{11}, f_{10}, f_{01}$. Hence, we say that $UNAI_{f_{00}}$ is not satisfied but I w.r.t to $UNAI_{f_{11}}, UNAI_{f_{01}}, UNAI_{f_{10}}$ is satisfied.

We check for the UNZR property for $f_{11}$ by taking the partial derivative at $f_{11}=0$, we get,

$$\begin{aligned} L_{f_{11}}(0) = \frac{\partial \hbox {L}}{\partial f_{11}}|_{f_{11}=0} = \frac{f_{10}+f_{00}+f_{01}}{f_{10}f_{01}} \end{aligned}$$

(12)

Similarly, taking the derivative with respect to $f_{00}, f_{10}, f_{01}$ at 0, we get

$$\begin{aligned} L_{f_{00}}(0)= & {} \frac{\partial \hbox {L}}{\partial f_{00}}\Big |_{f_{00}=0} = \frac{f_{11}}{(f_{11}+f_{10})(f_{11}+f_{01})} \end{aligned}$$

(13)

$$\begin{aligned} L_{f_{10}}(0)= & {} \frac{\partial \hbox {L}}{\partial f_{10}}\Big |_{f_{10}=0} = - \frac{(f_{01} + f_{00})}{(f_{11}+f_{01})f_{11}} \end{aligned}$$

(14)

$$\begin{aligned} L_{f_{01}}(0)= & {} \frac{\partial \hbox {L}}{\partial f_{01}}\Big |_{f_{01}=0} = - \frac{(f_{10} + f_{00})}{(f_{11}+f_{10})f_{11}} \end{aligned}$$

(15)

We see that for all feasible combinations $UNZR_{f_{11}}$ , $UNZR_{f_{10}}$ and $UNZR_{f_{01}}$ are satisfied. However, $UNZR_{f_{00}}$ is only partially satisfied. From Eq. 23, we can see that the following conditions are met: (i) For all feasible combinations of $f_{11}, f_{10}, f_{01}$, $L_{f_{00}}(0) \ge 0$. This passes the definition of partial satisfaction for UNZR as defined in the paper. At the same time, this does not fully satisfy the $UNZR_{f_{00}}$ property since there are values where it can be 0.¹

1.2 Illustrative example of the UNAI and UNZR framework using Piatetsky-Shapiro

In this section, we consider the behavior of another popular interestingness measure, Piatetsky-Shapiro (PS), under the UNAI and UNZR properties in the same way as in the previous section. PS is defined as follows:

$$\begin{aligned} \text {Piatetsky-Shapiro (PS)} = N ( P(A \cap B) - P(A) P(B) ) = f_{11} - \frac{(f_{11} + f_{01})(f_{11} + f_{10})}{f_{11} + f_{01} + f_{10} + f_{00}} \end{aligned}$$

(16)

Differentiating w.r.t to $f_{11}$ and simplifying, we get

$$\begin{aligned} \frac{\partial (\hbox {PS})}{\partial f_{11}} = \frac{(f_{01} + f_{00})(f_{10} + f_{00})}{(f_{11} + f_{01} + f_{10} + f_{00})^2} \end{aligned}$$

(17)

We check the UNAI property for PS by considering the derivative as $f_{11} \rightarrow \infty$

$$\begin{aligned} \hbox {PS}_{f_{11}}(\infty ) = \lim _{f_{11} \longrightarrow \infty } \frac{\partial {\hbox {PS}}}{\partial f_{11}} = \lim _{f_{11} \longrightarrow \infty } \frac{(f_{01} + f_{00})(f_{10} + f_{00})}{(f_{11} + f_{01} + f_{10} + f_{00})^2} \end{aligned}$$

(18)

After algebraic simplification, we can say that the above function is equal to zero for all feasible combinations of $f_{00}$, $f_{10}$ and $f_{01}$. Hence, we can say that Piatetsky-Shapiro satisfies UNAI with respect to $f_{11}$. Similarly, we check for UNAI property with respect to $f_{00}$, $f_{10}$, $f_{01}$. Hence, we can say that Piatetsky-Shapiro satisfies UNAI with respect to $f_{11}$. Similarly, we check for UNAI property with respect to $f_{00}, f_{10}, f_{01}$.

$$\begin{aligned} \text{ PS }_{f_{00}}(\infty )= & {} \lim _{f_{00} \longrightarrow \infty } \frac{\partial \hbox {PS}}{\partial f_{00}} = 0 \end{aligned}$$

(19)

$$\begin{aligned} \hbox {PS}_{f_{10}}(\infty )= & {} \lim _{f_{10} \longrightarrow \infty } \frac{\partial \hbox {PS}}{\partial f_{10}} = 0 \end{aligned}$$

(20)

$$\begin{aligned} \hbox {PS}_{f_{01}}(\infty )= & {} \lim _{f_{01} \longrightarrow \infty } \frac{\partial \hbox {PS}}{\partial f_{01}} = 0 \end{aligned}$$

(21)

Since Piatetsky-Shapiro satisfies $UNAI_{f_{11}}, UNAI_{f_{01}}, UNAI_{f_{10}}$ and $UNAI_{f_{00}}$, we say it satisfied UNAI.

Now we check for the UNZR property for $f_{11}$ by taking the partial derivative at $f_{11}=0$, we get,

$$\begin{aligned} \hbox {PS}_{f_{11}}(0) = \frac{\partial \hbox {L}}{\partial f_{11}}|_{f_{11}=0} = \frac{(f_{01} + f_{00})(f_{10} + f_{00})}{(f_{01} + f_{10} + f_{00})^2} \end{aligned}$$

(22)

Similarly, taking the derivative with respect to $f_{00}, f_{10}, f_{01}$ at 0, we get

$$\begin{aligned} \hbox {PS}_{f_{00}}(0)= & {} \frac{\partial \hbox {PS}}{\partial f_{00}}|_{f_{00}=0} = \frac{(f_{01} + f_{11})(f_{10} + f_{11})}{(f_{11} + f_{01} + f_{10})^2} \end{aligned}$$

(23)

$$\begin{aligned} \hbox {PS}_{f_{10}}(0)= & {} \frac{\partial \hbox {L}}{\partial f_{10}}|_{f_{10}=0} = - \frac{(f_{11} + f_{01})(f_{01} + f_{00})}{(f_{11} + f_{01} + f_{00})^2} \end{aligned}$$

(24)

$$\begin{aligned} \hbox {PS}_{f_{01}}(0)= & {} \frac{\partial \hbox {PS}}{\partial f_{01}}|_{f_{01}=0} = -\, \frac{(f_{11} + f_{10})(f_{10} + f_{00})}{(f_{11} + f_{10} + f_{00})^2} \end{aligned}$$

(25)

We see that for all feasible combinations $UNZR_{f_{11}}$ , $UNZR_{f_{10}}$ and $UNZR_{f_{01}}$ and $UNZR_{f_{00}}$ are satisfied. Therefore, we can say that Piatetsky-Shapiro satisfies the property UNZR as defined in the paper.

Appendix B: Clustering results from Sect. 5

The cluster memberships resulting from empirical analysis on the synthetic datasets are provided as an example of the details of cluster formation:

1.1 Sparse datasets

Synthetic dataset: Cluster A: {Recall, Precision, Confidence, Jaccard, F-Measure, Odd’s Ratio, Sebag Schoenauer, Support, Lift, Ganascia, Kulczynski-1, Relative Risk, Yule’s Q, Yule’s Y, Cosine, Odd Multiplier, Information Gain, Laplace, Zhang, Leverage, Examples and Counter Examples}, Cluster B: {Specificity, Negative Reliability, Accuracy, Descriptive Confirm, Causal Confirm, Piatetsky-Shapiro, Novelty, Causal Confidence, Certainty Factor, Loevinger, Conviction, Klosgen, 1-Way Support, 2-Way Support, Kappa, Putative Causal Dependency, Causal Confirm Confidence, Added Value, Collective Strength, Dependency}, Cluster C: {Mutual Information, Coverage, Prevalence, Least Contradiction, Normalized Mutual Information, Implication Index, Gini Index, Goodman Kruskal, J-Measure}.

1.1.1 Dense datasets

Synthetic dataset:Cluster A: {Recall, Odd’s Ratio, Specificity, Negative Reliability, Lift, Coverage, Piatetsky-Shapiro, Novelty, Yule’s Q, Yule’s Y, Odd Multiplier, Certainty Factor, Loevinger, Conviction, Information Gain, Klosgen, Zhang, 1-Way Support, 2-Way Support, Kappa, Putative Causal Dependency, Added Value, Collective Strength, Dependency}. Cluster B: {Precision, Confidence, Jaccard, F-Measure, Sebag Schoenauer, Support, Accuracy, Causal Confidence, Ganascia, Kulczynski-1, Prevalence, Relative Risk, Cosine, Least Contradiction, Descriptive Confirm, Causal Confirm, Laplace, Examples and Counter Examples, Causal Confirm Confidence}. Cluster C: {Mutual Information, Normalized Mutual Information, Implication Index, Gini Index, Goodman Kruskal, Leverage, J-Measure}.