Revealing Interesting If-Then Rules

Abstract

One of the challenges of data mining is revealing the interesting if-then rules in the mined dataset. We present two methods for the automated discovery of unexpected, and, thereby, interesting rules within the set of all the if-then rules previously revealed in the dataset. The first method calculates, for each rule, the probability that the rule exists accidentally. The lower this probability, the more unexpected the rule is. The second method calculates the conditional probability of the event described by the rule, given the relevant more basic rules. Once again, the lower this conditional probability, the more unexpected the rule is. These two methods are independent and can be combined.

1. Introduction

Several data mining algorithms reveal if-then rules in the mined data [1]. However, in many cases, the size of the analyzed data is enormous [2], and as a result, the number of rules is so big that the user cannot practically review all of them manually. Consequently, the user would like to have a method of accessing the most interesting rules among the discovered ones.

What makes a rule interesting? Several papers in data mining literature have addressed this issue. Two different interpretations of the concept of “interesting rules” can be found in this literature. Some papers, such as [3], refer to “interesting rules” in the sense of “rules that are best or optimal.” Other papers refer to another meaning of “interesting rules,” according to which an interesting rule satisfies the user’s curiosity. In this paper, we refer to this second meaning.

One can filter the non-interesting rules using the support and confidence levels [2, 4, 5]. The support level of an if-then rule denotes the number of records where the rule holds (both the rule’s conditions and conclusion are true) relative to the total number of records in the dataset. The user may determine the threshold of the support level, implying that rules having a support level below this threshold are not interesting. The confidence level designates the frequency of cases where both the rule’s conditions and conclusion hold relative to the cases where the rule’s conditions hold with or without the conclusion. (In other words, the confidence level denotes the rule probability. For example, If the value in field A is a, and value in field B is b, then there is an 80% probability that the value in field C is c). Obviously, a rule is interesting only if the confidence level is significantly higher than the primary frequency of the conclusion in the dataset. Once again, the user may determine a threshold implying that rules having a confidence level below this threshold are not interesting. However, this method alone cannot guarantee to reveal all the interesting rules. When either the support level and/or the confidence level are too high, interesting rules may be missed, and when they are too low, non-interesting rules may be revealed.

Following this line, it was suggested that other means should be used on top of the support level and confidence level to reveal the interesting rules. One suggestion was to measure how unexpected each rule is. The idea that unexpected phenomena are interesting was suggested already in the ancient world. In the twentieth century, it was mentioned in the Philosophy of Science by Agassi [6]. In the field of data mining, it was presented by Silberschatz and Tuzhilin [7, 8]. According to this view, users classify a rule as interesting when it is inconsistent with their expectations. In other words, rules are interesting when they are unexpected.

How can the level of a rule’s unexpectedness be measured? Liu and Hsu [9] and Liu, Hsu, and Chen [10] suggest measuring the extent of the rule’s unexpectedness by comparing the rule with a predefined set of expectations. At the preliminary stage, the users enter their expectations, and based on this set of expectations, the program calculates an evaluation of unexpectedness for each rule. Such an approach can be used when the user can formulate all the expected rules, but it is not easy. Moreover, since some of the discovered rules might result from noise, and obviously, the user does not expect these rules, they will be presented as unexpected and, thereby, interesting. Sahar [11] suggests a process where the system selects a few rules, the user marks the rules that are not interesting, and the program then automatically eliminates the other associated rules. Sahar reports that “by little over five iterations, this process often reduces the list of rules to half its original size.” However, in many cases, such a reduction is not sufficient. When the list of rules contains 10,000 rules, reducing the list to 5000 might not satisfy the user. They might instead prefer sorting the rules by their level of interestingness and reviewing just the 10 or 100 most interesting ones. Wesley Romão, Alex A. Freitas, and Itana M.de S. Gimenes [12] suggest using a genetic algorithm for revealing surprising if-then rules based on user-defined general impressions (subjective knowledge). A similar approach was proposed by Jyoti Vashishtha, Dharminder Kumar, Saroj Ratnoo, and Kapila Kundu [13].

In this paper, we suggest two additional methods for revealing the unexpected and, thereby interesting rules. Contrary to the previous methods, our methods reveal the unexpected rules automatically, that is, unassisted by the user. Moreover, these methods sort the rules by their level of unexpectedness and, thereby, interestingness.

The first method for measuring the degree of unexpectedness rests on the assumption that when the users have no preliminary knowledge about the relations among the fields and their values in the data, their “natural” expectation is that the relations are accidental. By calculating the probability that a given rule is accidental, we can therefore measure the extent to which the rule is unexpected. The logic underlying this idea is similar to that underlying the calculation of the significance level in classical statistical tests, such as t-test or F-test. These tests refer to the concept of α, which denotes the probability that the phenomenon is accidental. The lower this probability, the more significant the phenomenon is. Following the same line of thought, we calculate the probability that a given rule is accidental. The lower this probability, the more unexpected and, thereby, more interesting the rule is. In other words, we assume that the user expects accidental relations between the fields and their values. Each rule refutes this expectation. The level of the refutation can be measured by calculating the probability that the rule is accidental. The lower this probability, the more significant and interesting the rule is.

The second method for measuring the degree of unexpectedness rests on the assumption that the set of one-condition rules can be considered the user’s basic expectations. Given the one-condition rules, the conditional probability of the rules having more than one condition can then be calculated. The lower this conditional probability, the more unexpected the rule is. For example, suppose that the following three rules were discovered in the data: (1) If A then R, (2) If B then R, and (3) If A and B then NOT R. Rule (3) can be considered as unexpected relative to rules (1) and (2). Assuming that the user already knows rules (1) and (2), being one-condition rules, rule (3) turns out to be unexpected and thereby interesting. This approach can be elaborated by considering not just the one-condition rules as the basic expectations. Rather the conditional probability of any rules having more than one condition can be calculated given any rules, the conditions of which are a subset of the conditions of the rule under discussion. Thus a three-condition rule can be compared against the relevant one-condition and two-condition rules.

A similar approach was suggested by Suzuki [14]. He analyzed rule pairs such as “If A then B” and “If A and C then not B.” However, this approach does not calculate the conditional probability of the unexpected rule given the one-condition rules and is limited to pairs of if-then rules where the conclusions are inconsistent. Our approach covers the abovementioned rules pairs as a private case.

In what follows, we will present the algorithms for calculating the level of the unexpectedness of the rules according to these two methods.

2. If-then rules

There are several algorithms for revealing if-then rules in the data [2, 3]. For the sake of simplicity and without loss of generality, we will limit the discussion to association rules that are related to one Boolean field in the “then” part (the dependent variable).

Consider a dataset containing $n+1$ fields, among which one field is selected as the dependent variable, y. The remaining n fields $x_1,\dots ,x_n$ are considered as input data used for explaining the selected field y. Consider the most frequent case when field y is Boolean. Without loss of generality we assume $y\in \left\{0,1\right\}$.

Let $I_i=\left\{a_{i1},\dots ,a_{{\mathit{im}}_i}\right\}$ be the set of codes of values of variable (field) $x_i$. For example, if field $x_i$ is quantitative, $a_{\mathit{ij}}$ denotes the code of the interval of change of values of variable $x_i$. A single condition (1-condition) is a condition of the following type: $x_i=a_{\mathit{ij}},j\in \left\{1,\dots ,m_i\right\}$. A composite condition is a conjunction of q single conditions, $q=2,\dots ,n$. We will call a composite condition consisting of q single conditions q-condition. Thus, q-condition is a condition of the type: $\left(x_{i_1}=a_{i_1{j}_1}\right)\wedge \dots \wedge \left(x_{i_q}=a_{i_q{j}_q}\right)$.

An if-then rule is the following statement:

$$\text{If}\left(\text{the}q-\text{condition}\right)\text{then}y\mathit{\text{is}}{y}_1.$$E1

Rule’s probability (confidence level) = p.

Rule’s support level = s,

where $y_1$ belongs to the set of values of field y, that is, $y_1=1$ or $y_1=0$.

The number of records, s, at which both the rule’s condition (the q-condition) and the rule’s conclusion (y is y₁) are fulfilled is called the rule’s support level. (Contrary to other definitions of “support level” we refer to the number of records satisfying the rule rather than the percentage of records out of the total number of records in the dataset.) The rule’s probability, p, is the ratio of the rule’s support to the number of records satisfying the rule’s condition.

Let $p_a$ be the a priori probability that $y=1$. $p_a=\frac{M}{N}$, where N is the total number of records in the mined dataset, and M is the number of records at which $y=1$. Rules of type (1) can be interesting only if their probability significantly deviates from $p_a$. Formally, only the rules of type (1) in which $p\ge {\overline{p}}_1$ or $p\le {\overline{p}}_0$ can be interesting, where ${\overline{p}}_1>p_a$ and ${\overline{p}}_0<p_a$ are the predetermined values of a probability that y is y₁. Here we suppose that all the rules of type (1) are represented such that they have y is 1 in the “then” part. (Note that a rule having probability $p\le {\overline{p}}_0$ that y is y₁ is equivalent to the rule containing the same condition in the “if” part and having a probability $1-p\ge 1-{\overline{p}}_0$ that y is 0.) Moreover, the support level of an interesting rule must be not less than the pre-given value $s_{\min }$, that is, $s\ge s_{\min }$.

Assume that all the rules satisfying the abovementioned requirements have already been found. Then, a new problem unexpectedly arises. It turns out that the number of such rules can be so huge that it is quite impractical for the user to review all of them in order to select the interesting ones. The user can decrease the number of revealed rules by raising the minimum rule’s support level, $s_{\min }$ and/or the minimum rule’s probability (confidence level) ${\overline{p}}_1$, or by decreasing the value ${\overline{p}}_0$, but this can lead to missing rules having a low support level or a probability, not strongly deviating from $p_a$, which are nevertheless interesting.

3. Calculating the probability that a rule is accidental

This section will present the first method for measuring the degree of unexpectedness. We will present an algorithm for calculating the probability that a given if-then rule is accidental. As mentioned, the lower this probability, the more unexpected and interesting the rule is.

Let J be the set of all the discovered association rules. Consider a rule $j\in J$. Let us try to evaluate the significance level of the rule j, namely the probability that rule j in the investigated dataset exists not accidentally.

The significance level of rule j may be determined as $1-{\alpha }_j$, where ${\alpha }_j$ is the probability that the rule j in the investigated dataset exists by chance. To precisely define ${\alpha }_j$, assume that the rule j has probability $p_j\ge {\overline{p}}_1$ (that y is 1) and support level $s_j$. It is intuitively clear that there is a certain a priori probability that this rule, or any such rule where the probability is not less than $p_j$, will be revealed. ${\alpha }_j$ is this a priori probability. Formally, assume that $m_j$ records have been chosen at random from a dataset containing N records, among which there are $p_{a}N$ records where y is 1. Here $m_j=\frac{s_j}{p_j}$ is the number of records satisfying the condition of rule j. ${\alpha }_j$ is the probability that there are not less than $s_j$ records where y is 1 among these $m_j$ records. ${\alpha }_j$ is calculated by the formula of hypergeometric distribution, that is:

$${\alpha }_j=\sum _{k=s_j}^{m_j}{P}_{N,M}\left(m_j,k\right),$$E2

where

$$P_{N,M}\left(m_j,k\right)=\frac{\left(\begin{array}{l}k\\ M\end{array}\right)\cdot \left(\begin{array}{l}{m}_j-k\\ N-M\end{array}\right)}{\left(\begin{array}{l}{m}_j\\ N\end{array}\right)}$$E3

${\alpha }_j$ for the rule j with the probability $p_j\le {\overline{p}}_0$ that y is 1 (i.e., for a rule having the probability $1-p_j$ that y is 0, where $1-p_j\ge 1-{\overline{p}}_0$) implies the a priori probability that this rule, or any such rule where the probability that y is 1 is not greater than $p_j$, will be revealed. In this case, ${\alpha }_j$ is calculated as follows:

$${\alpha }_j=\sum _{k=0}^{s_j}{P}_{N,M}\left(m_j,k\right),$$E4

where $P_{N,M}\left(m_j,k\right)$ is calculated by formula (3).

To calculate $P_{N,M}\left(m_j,k\right)$ by formula (3), at first $ln\left(P_{N,M}\left(m_j,k\right)\right)$ is calculated by the approximation formula $ln\left(n!\right)\approx \left(n+0.5\right)ln\left(n\right)-n+0.5ln\left(2\pi \right)$. Then $e^{ln\left(P_{N,M}\left(m_j,k\right)\right)}$ is calculated.

The less ${\alpha }_j$, the greater the significance level of rule j. The significance level of rule j may be interpreted as the measure of the unexpectedness of this rule, thereby as a designation of the extent to which the rule is interesting.

Thus, we can calculate the significance level for each rule $j\in J$, and sort the array of all discovered rules by the descending order of the values of the significance level. This descending order allows the user to sort the rules by their level of unexpectedness according to the first criteria of unexpectedness.

Now, the first k rules of the sorted array can be considered unexpected and interesting. The number k may be determined based on the condition that the significance level of a rule is not less than a pre-given value. Another way of determining the boundary value for the significance level is as follows. The average value $\overline{a}$ of significance levels for all rules $j\in J$ and the corresponding standard deviation $\sigma$ are calculated. The value $\overline{a}+\sigma$ can be accepted as the boundary value for the significance level of an interesting rule.

4. Calculating the conditional probability of a rule given the basic trends

The previous section referred to the first method for measuring the degree of unexpectedness. We turn now to the second method. This method refers to rules having more than one condition. It calculates the conditional probability of each of these rules given the basic trends in the data.

Consider first an example. Assume that the a priori probability that y = 1 is 0.3, and we wish to find all the if-then rules having a probability (1) not less than ${\overline{p}}_1=0.4$, and (2) not greater than ${\overline{p}}_0$$=0.2$. Assume also that the following two rules were discovered (among other):

1. If x₁ is 3, then there is a probability of 0.45 that y is 1.

2. If x₁is 3 and x₂ is 5, then there is a probability of 0.85 that y is 0 (i.e., a probability of 0.15 that y is 1).

This pair of rules may be considered as unexpected because (1) the first rule states that under the condition x₁ is 3, the probability that y is 1 significantly deviates from $p_a$ in the upper side, and (2) when adding the condition x₂ is 5 to x₁ is 3, the probability that y is 1 unexpectedly deviates from $p_a$ in the opposite direction.

If the probability that y is 1 in the second rule were not 0.15 but, for example, 0.9, this fact would also be considered as unexpected, since adding the second condition to the first one leads to a sudden leap of probability. In this case, even if the first rule had not been revealed, the second rule would still be considered as unexpected. One can easily see the reason for this by considering why the first rule had not been discovered. The first rule’s support cannot be less than the second rule’s support $s\ge s_{\min }$. Consequently, the only possible reason for not discovering the first rule is the nonfulfillment of both, the condition that $p\ge {\overline{p}}_1$ and the condition that $p\le {\overline{p}}_0$, where p is the first rule’s probability. Hence, ${\overline{p}}_0<p<{\overline{p}}_1$ . Thus, analogously to the previous case, the addition of the condition x₂is 5 to x₁is 3 leads to an even greater leap of probability that y is 1.

Let us now give a formal definition for an unexpected rule (following the second method).

Definition: A rule containing q-condition (q > 1) in the “if” part, y is y₁ in the “then” part, and having probability P that y is y₁ is called unexpected if at least one of the following two requirements is fulfilled:

1. There is a rule containing y is not y₁ in the “then” part and $q_1$-condition ($q_1<q$) in the “if” part such that the set of 1-conditions entered in the $q_1$-condition is a subset of the set of 1-conditions entered in the q-condition.

2. There is no rule containing y is y₁ in the “then” part and $q_1$-condition ($q_1<q$) in the “if” part (where the set of 1-conditions entered in the $q_1$-condition is a subset of the set of 1-conditions entered in the q-condition) for which the inequality p<<P is not fulfilled, where p denotes a probability of such a rule. (If y₁ is 1, p is the probability that y is 1; if y₁ is 0, p is the probability that y is 0.)

The second requirement means that the probability that y is y₁ for any discovered rule with the above-defined $q_1$-condition in the “if” part and y is y₁ in the “then” part must be much less than P.

To reveal the unexpected rules according to the above definition, it is first necessary to precisely define the relation “<<”. Consider the following possible definitions for relation p<<P.

Assume that p is relatively small (for definiteness, $p<0.2$). To determine the lower boundary value for P, let us add a third of the length of the segment $\left[p,1\right]$ to p. We get the inequality $P\ge \frac{2p+1}{3}$. Let $0.2\le p<0.5$ . In this case, to determine the lower boundary value for P, let us add a half of the length of the segment $\left[p,1\right]$ to p. We get $P\ge \frac{p+1}{2}$ . Let $0.5\le p<0.7$. To determine the lower boundary value for P, let us add two thirds of the length of segment $\left[p,1\right]$ to p. We get $P\ge \frac{p+2}{3}$ . For the case when $0.7\le p<0.9$, let us define the relation p<<P as $P=1$. If $p\ge 0.9$, we will not define the relation p<<P, that is, in this case, the fulfillment of the first of the two abovementioned requirements is the necessary condition for accepting the rule having probability P as unexpected.

Another definition uses a notion of an expected probability for a rule containing the q-condition in the “if” part ($q>1$) and suspected as unexpected. Consider the set of 1-conditions entered in the q-condition. Let $p_i$ be the probability that y is 1 under ith 1-condition, $i=1,\dots ,q$. (Note that if for a fixed $i{p}_i\ge {\overline{p}}_1$ or $p_i\le {\overline{p}}_0$, then we have the corresponding rule with 1-condition.) Let $s_i$ be the number of records satisfying both the ith 1-condition and the condition y is 1. Then the number of records satisfying the ith 1-condition is $m_i=\frac{s_i}{p_i}$ . The probability that ith 1-condition is fulfilled on the set of records of the investigated dataset is $\frac{m_i}{N}$. Assume that all the events, each of which is defined by the set of records satisfying ith 1-condition, are independent. Then the expected number $k_{\mathit{ind}}$ of records satisfying all of these conditions can be calculated as follows:

$$k_{\mathit{ind}}=N\cdot \prod _{i=1}^q\frac{m_i}{N}$$E5

or

$$k_{\mathit{ind}}=\frac{{\prod }_{i=1}^q{m}_i}{N^{q-1}}$$E6

Assume that all the events, defined as “both the ith 1-condition and y is 1 are fulfilled,” are independent. Then the expected number of records satisfying all these events is

$$k_{\mathit{ind}}^{\left(1\right)}=M\cdot \prod _{i=1}^q\frac{s_i}{M}=\frac{\prod _{i=1}^q{s}_i}{M^{q-1}}$$E7

Assume that all the events, defined as “both the ith 1-condition, and y is 0 are fulfilled,” are independent. Then the expected number of records satisfying all these events is

$$k_{\mathit{ind}}^{\left(0\right)}=\left(N-M\right)\cdot \prod _{i=1}^q\frac{m_i-s_i}{N-M}=\frac{\prod _{i=1}^q\left(m_i-s_i\right)}{{\left(N-M\right)}^{q-1}}$$E8

Let us now calculate the expected probability $P_{\mathit{ind}}$ that y is 1 under the abovementioned assumptions:

$$P_{\mathit{ind}}=\frac{k_{\mathit{ind}}^{\left(1\right)}}{k_{\mathit{ind}}^{\left(1\right)}+k_{\mathit{ind}}^{\left(0\right)}}$$E9

After the transformations, we get:

$$P_{\mathit{ind}}=\frac{1}{1+A},$$E10

where

$$A={\left(\frac{p_a}{1-p_a}\right)}^{q-1}\cdot \prod _{i=1}^q\frac{1-p_i}{p_i}$$E11

Assume now that all the events, each of which is defined by the set of records satisfying ith 1-condition, are dependent to a maximal degree. In this case, the number $k_{\mathit{dep}}$ of records satisfying all the 1-conditions is equal to the minimum numbers of records satisfying each individual 1-condition, that is:

$$k_{\mathit{dep}}=\underset{i=1,\dots ,q}{}{m}_i$$E12

Let $i_0=\text{arg min}{m}_i$. The probability $P_{\mathit{dep}}$ that y is 1 for the rule containing all the 1-conditions is equal to $p_{i_o}$, i.e.

$$P_{\mathit{dep}}=p_{i_0}$$E13

Thus, we have considered two extreme cases where the 1-conditions are (1) independent and (2) dependent as much as possible. The extent of the dependency between the 1-conditions can be determined by the number of records satisfying all the 1-conditions. This is the number of records satisfying the q-condition of the rule, which is suspected as unexpected. Let us denote this number by K. It is obvious that $K\le k_{\mathit{dep}}$. The nearer K to $k_{\mathit{dep}}$, the greater the extent of dependency between the 1-conditions. If K is near to $k_{\mathit{ind}}$, then it can be assumed that the 1-conditions are independent or “almost” independent. In this case, when $K<k_{\mathit{ind}}$ we can say that the events, each of which is defined by the set of records satisfying ith 1-condition, are more inconsistent than independent. But, in this case, there is a very low chance of establishing the abovementioned rule with the q-condition as a result of nonfulfillment of the necessary condition $K\ge s_{\min }$.

Consider now function $P_{\exp }=P_{\exp }\left(K\right)$, where $P_{\exp }$ is the expected probability that y is 1 for the above rule with the q-condition. For the sake of simplicity, assume that this function is linear, for $k_{\mathit{ind}}\le K\le k_{\mathit{dep}}$. $P_{\exp }=P_{\mathit{ind}}$, if $K=k_{\mathit{ind}}$; $P_{\exp }=P_{\mathit{dep}}$, if $K=k_{\mathit{dep}}$. For extremely rare cases when $K<k_{\mathit{ind}}$, let us set $P_{\exp }=P_{\mathit{ind}}$. Then, $P_{\exp }$ is calculated as follows:

$$P_{\exp }=\frac{P_{\mathit{dep}}-P_{\mathit{ind}}}{k_{\mathit{dep}}-k_{\mathit{ind}}}\cdot \left(K-k_{\mathit{ind}}\right)+P_{\mathit{ind}},\text{if}{k}_{\mathit{ind}}\le K\le k_{\mathit{dep}}$$E14

$$P_{\exp }=P_{\mathit{ind}},\text{if}K<k_{\mathit{ind}}$$E15

where $k_{\mathit{ind}}$, $P_{\mathit{ind}}$, $k_{\mathit{dep}}$, $P_{\mathit{dep}}$ are calculated by formulas (6)–(13).

Thus, a rule containing the q-condition in the “if” part and having probability P that y is 1 can be defined as unexpected if $P_{\exp }$ << P. The definition for the relation “<<” was previously presented.

Assume that we have found the unexpected rule, containing q-condition in the “if” part, whose support level is S and the probability (confidence level) is P. We can determine the probability of the event described by this rule given the events described by each set of records defined by $i$th 1-condition such that this 1-condition belongs to the set of 1-conditions entered in the q-condition, $i=1,\dots ,q$. Note that the corresponding rule with the $i$th 1-condition has perhaps been revealed for all $i$ or some of them. If such a rule having $i$th 1-condition exists, let us denote the support level, the probability, and the number of records satisfying the rule’s condition by $s_i$, $p_i$, and $m_i$ respectively. In the case when a rule having $i$th 1-condition does not exist, we will use the same notations.

Let us define the level of unlikelihood $U_i$ of the unexpected rule relative to the rule $i$ as the probability of the existence of this unexpected rule provided that the rule $i$ holds (more precisely, provided that the $i$th 1-condition is defined by the three above parameters whose values are $s_i$, $p_i$, $m_i$). Hence, the level of unlikelihood $U_i$ can be calculated by the formula of the hypergeometric distribution:

$$U_i=\frac{\left(\begin{array}{l}S\\ s_i\end{array}\right)\cdot \left(\begin{array}{l}K-S\\ m_i-s_i\end{array}\right)}{\left(\begin{array}{l}K\\ m_i\end{array}\right)}$$E16

The maximum (or the minimum) of $U_i$ can be considered as the level of the unlikelihood of the unexpected rule.

The rules can then be sorted by their level of unlikelihood, and the higher this level, the higher the level of unexpectedness according to the second criteria.

5. Experiments with real data

The abovementioned two algorithms have been implemented in a commercial data mining tool, WizWhy, which can be downloaded from www.wizsoft.com.

In what follows, we present the reports issued by this tool in regard to the Diabetes dataset (www.ics.uci.edu/∼mlearn/MLRepository.html). We issued an analysis having the following thresholds:

Minimum support level: 20 records (The total number of records was 768.)

Minimum confidence level for if-then rules: 0.48 (The a priori probability was 0.349.)

Minimum confidence level for if-then-not rules: 0.79.

Two hundred twenty rules were discovered. The two rules having the lowest error probability (α being smaller than 0.0000001) were:

1. If Plasma glucose is 108.00 … 197.00 (average = 142.80)

   and Age is 29.00 … 81.00 (average = 42.39)

   Then Predict is 2

   Confidence level: Rule’s probability is 0.593

   Support level: The rule exists in 172 records.

2. If Plasma glucose is 0.00 … 107.00 (average = 90.65)

   Then Predict is not 2

   Confidence level: Rule’s probability is 0.875

   Support level: The rule exists in 253 records.

   These rules are the most interesting rules according to the first method. Thirty-four rules (out of the total 220 rules that were discovered) were unexpected according to the second method. The first rule in this list was:

3. If Number of times pregnant is 1.00 … 2.00 (average = 1.35)

   and Diastolic blood pressure is 64.00 … 88.00 (average = 74.20)

   and Age is 29.00 … 62.00 (average = 36.83)

   Then Predict is 2

   Confidence level: Rule’s probability is 0.550

   Support level: The rule exists in 22 records.

   Significance Level: Error probability < 0.01

   This rule was found to be unlikely relative to the following three rules and trends:

4. If Number of times pregnant is 1.00 … 2.00 (average = 1.43)

   Then Predict is not 2

   Confidence level: Rule’s probability is 0.798

   Support level: The rule exists in 190 records.

5. If Diastolic blood pressure is 64.00 … 88.00

   Then Predict is 2

   Confidence level: Trend’s probability is 0.369

   Support level: The trend exists in 190 records.

6. If Age is 29.00 … 81.00

   Then Predict is 2

   Confidence level: Trend’s probability is 0.491

   Support level: The trend exists in 197 records.

Note that rule # (4) says that if the number of pregnant is 1 or 2, then there is a high probability (0.798) that the value in the Predict field is not 2. However, following rule # (3), if the conditions presented in rules # (5) and (6) are added to the condition of rule # (4), then there is a high probability that the Predict field is 2. On the basis of the events described in rules # (4), (5), and (6), we should have expected that the confidence level in rule # (3) would have been 0.332, while in fact it is 0.55. In this sense, rule # (3) is unexpected and as such interesting.

Following experiments with the datasets in the abovementioned repository, these results are quite representative. On average, about 5% of the rules have an error probability lower than 0.01, and about another 5% are unexpected, according to the second method.

6. Conclusion

We have presented two methods for the automated discovery of unexpected and, thereby, interesting rules within the set of all the if-then rules previously revealed in the mined dataset.

The first method calculates, for each rule, the probability that the rule exists accidentally. The lower this probability, the more unexpected the rule is. The second method calculates the conditional probability of each rule having more than one condition, given the relevant more basic rules and trends. The lower this conditional probability, the more unexpected the rule is.

These two methods are independent, and it makes sense always to use both. One can calculate a combined score by multiplying the scores of the two methods. And since there are additional methods for revealing interesting rules (some of them were mentioned in the first section of this paper), one can develop a score that combines all these methods. The search for finding additional methods for revealing interesting rules and combining these methods is a project to be continued.

The author would like to thank Boris Levin and Ilya Vorobyov for helping to write this paper and to develop the software program presented in this paper.