apriori.html

数据挖掘中的关联规则算法

(Attention: If you have a large number of items, setting the minimal
rule confidence to zero can result in <i>very</i> high memory
consumption.)</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="diff">Absolute Confidence Difference to Prior
    (option <tt>-ed</tt> or <tt>-e1</tt>)</a></h4>

<p>The simplest way to compare the two confidences is to compute the
absolute value of their difference. I.e., if "-&gt; bread" has a
confidence of 60% and "cheese -&gt; bread" has a confidence of 62%,
then the value of this measure is 2%. The parameter given via the
option <tt>-d</tt> to the program states a lower bound for this
difference. It follows that this measure selects rules the confidence
of which differs more than a given threshold from the corresponding
prior confidence. For example, with the option <tt>-d20</tt> (and, of
course, the option <tt>-ed</tt> to select the measure) for the item
"bread" only rules with a confidence less than 40% or greater than 80%
would be selected. Of course, for other items, with a different prior
confidence, the upper and lower bounds are different, too.</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="quotient">Difference of Confidence Quotient to 1
    (option <tt>-eq</tt> or <tt>-e2</tt>)</a></h4>

<p>An equally simple way to compare the two confidences is to compute
their quotient. Since either the prior or the posterior confidence
can be greater (which was handled by computing the absolute value
for the previous measure), this quotient or its reciprocal, whichever
is smaller, is then compared to one. A quotient of one says that the
rule is not interesting, since the prior and the posterior confidence
are identical. The more the quotient differs from one, the more
"interesting" the rule is. Hence, just as above, a lower bound for
this difference is given via the option <tt>-d</tt>. For the bread
example, with the option <tt>-d20</tt> rules with a confidence less
than or equal to (1 -20%) *60% = 0.8 *60% = 48% or a confidence greater
than or equal to 60% / (1 -20%) = 60% / 0.8 = 75% are selected. The
difference between this measure and the absolute confidence difference
to the prior is that the deviation that is considered to be significant
depends on the prior confidence. If it is high, then the deviation of
the posterior confidence must also be high, and if it is low, then
the deviation need only be low. For example, if "-&gt; bread" had a
confidence of only 30%, then the option <tt>-d20</tt> (just as above)
would select rules the confidence of which is less than 0.8 *30% = 24%
or greater than 30% /0.8 = 37.5%. As you can see, for a prior confidence
of 60% the deviation has to be at least 12%/15%, for a prior confidence
of 30% it has to be only 6%/7.5% in order to make a rule eligible.
The idea is that an increment of the confidence from 30% to 40% is more
important than an increment from 60% to 70%, since the relative change
is greater.</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="improve">Absolute Difference of Improvement Value to 1
    (option <tt>-ea</tt> or <tt>-e3</tt>)</a></h4>

<p>This measure is very similar to the preceding one. Actually, if
the confidence of a rule is smaller than the prior confidence, then
it coincides with it. The improvement value is simply the posterior
confidence divided by the prior confidence. It is greater than
one if the confidence increases due to the antecedent, and it is
smaller than one if the confidence decreases due to the antecedent.
By computing the absolute value of the difference to one, the
improvement value can easily be made a rule selection measure.
The advantage of this measure over the preceding one is that it is
symmetric w.r.t. changes of the confidence due to the antecedent of
a rule. For the bread example, with the option <tt>-d20</tt> rules with
a confidence less than or equal to (1 -20%) *60% = 0.8 *60% = 48% or a
confidence greater than or equal to (1 +20%) *60% = 1.2 * 60% = 72%
are selected. (Note the difference of 72% compared to 75% for the
preceding measure.) Similarly, for the second bread example
discussed above, the numbers are 0.8 *30% = 24% and 1.2 *30% = 36%.
Note that this is the only measure for which a value greater than 100
may be specified with the <tt>-d</tt> option, since it can exceed
100% if the posterior confidence of a rule exceeds twice the prior
confidence. (I am grateful to Roland Jonscher, who pointed out this
measure to me.)</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="info">Information Difference to Prior
    (option <tt>-ei</tt> or <tt>-e4</tt>)</a></h4>

<p>This measure is simply the information gain criterion that can be
used in decision tree learners like C4.5 to select the split attributes.
Its idea is as follows: Without any further information about other
items in the set, we have a certain probability (or, to be exact, a
relative frequency) distribution for, say "bread" and "no bread".
Let us assume it is 60% : 40% (prior confidence of the item "bread",
just as above). This distribution has a certain entropy</p>
<p>H = - P(bread)    log<sub>2</sub> P(bread)
       - P(no bread) log<sub>2</sub> P(no bread),</p>
<p>where P(bread) is equivalent to the support of "bread", which in
turn is equivalent to the prior confidence of "bread". The entropy of a
probability distribution is, intuitively, a lower bound on the number
of yes-no-questions you have to ask in order to determine the actual
value. This cannot be understood very well with only two possible
values, but it can be made to work for this case too. I skip the
details here, they are not that important.</p>

<p>After we get the information that the items in the antecedent of
the rule are present (say, cheese), we have a different probability
distribution, say 35% : 65%. I.e., P(bread|cheese) = 0.35 and
P(no bread|cheese) = 0.65. If we also know the support of the item
"cheese" (let it be P(cheese) = 0.4 and P(no cheese) = 0.6), then
we can also compute the probabilities P(bread|no cheese) = 0.77 and
P(no bread|no cheese) = 0.23. Hence we have two posterior probability
distributions. The question now is: How much information do we receive
from observing the antecedent of the rule? Information is measured
as a reduction of entropy. Hence the entropies of the two conditional
probability distributions (for "cheese" and "no cheese") are computed
and summed weighted with the probability of their occurrence (i.e.,
the relative frequency of "cheese" and "no cheese", respectively).
This gives the expected value of the posterior or conditional entropy.
The difference of this value to the prior entropy (see above) is the
gain in information from the antecedent of the rule or, as I called
it, the information difference to the prior.</p>

<p>The value that can be given via the <tt>-d</tt> option is a lower
bound for the information gain, measured in hundreds of a bit. Since
all items can only be present or absent, the information gain can be
at most one bit. Therefore a percent value is still reasonable.</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="chi2">Normalized</a> chi<sup>2</sup> Measure
    (option <tt>-ec</tt> or <tt>-e5</tt>)</h4>

<p>The chi<sup>2</sup> measure is well known from statistics. It is
often used to measure the difference between a supposed independent
distribution of two discrete variables and the actual joint distribution
in order to determine how strongly two variables depend on each other.
This measure (as it is defined in statistics) contains the number of
cases it is computed from as a factor. This is not very appropriate
if one wants to evaluate rules that can have varying support. Hence
this factor is removed by simply dividing the measure by the number
of items sets (the total number, i.e. with the names used above, the
number of sets in X). With this normalization, the chi<sup>2</sup>
measure can assume values between 0 (no dependence) and 1 (very strong
dependence). The value that can be given via the <tt>-d</tt> option is
a lower bound for the strength of the dependence of the head on the
body in percent (0 - no dependence, 100 - perfect dependence). Only
those rules are selected, in which the head depends on the body with
a higher degree of dependence.</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="behavior">Selection Behavior of the Measures</a></h4>

<p>In the directory <tt>apriori/doc</tt> you can find a Gnuplot script
named <tt>arem.gp</tt> (<tt>arem</tt> stands for additional rule
evaluation measures) which visualizes the behavior of the additional
rule evaluation measures. This script draws eight 3d graphs, one for
the absolute confidence difference, one for the difference of the
confidence quotient to one, three for the information difference to
the prior confidence and three for the normalized chi<sup>2</sup>
measure. All graphs show the value of an additional rule evaluation
measure over a plane defined by the prior and the posterior confidence
of a rule. The latter two measures need three graphs, since they depend
on the antecedent support of a rule as a third parameter. Setting a
minimal value for an additional rule evaluation measure is like
flooding the corresponding graph landscape up to a certain level
(given as a percentage, since all considered measures assume values
between 0 and 1). Only those rules are selected that sit on dry land.
</p>

<p>The first graph shows the behavior of the absolute confidence
difference. For the diagonal, i.e. the line where the prior and the
posterior confidence are identical, its value is zero (as expected).
The more the two confidences differ, the higher the value of this
measure gets, but in a linear way.</p>

<p>The second graph shows the behavior of the confidence quotient
to one. Again its value is zero for the diagonal (as the value of
all measures is) and becomes greater the more the prior and the
posterior confidence differ. But it is much steeper for a small
prior confidence than for a large one and it is non-linear.</p>

<p>The third to fifth graph show the information difference to the
prior confidence for an antecedent support (which is identical to the
rule support in my interpretation, see above) of 0.2 (20%), 0.3 (30%)
and 0.4 (40%). The regions at the margins, where the measure is zero,
correspond to impossible combinations of prior and posterior confidence
and antecedent support. As you can see, the valley gets narrower with
increasing antecedent support. I.e., with the same minimal value for
this measure, rules with low antecedent support need a higher confidence
difference to be selected than rules with a high antecedent support.
This nicely models the statistical significance of confidence changes.
If you only have a few cases to support your rule, even a large
deviation from the prior confidence can be explained by random
fluctuations, since only a few transactions need to be different to
produce a considerable change. However, if the antecedent support
is large, even a small deviation (in percent) has to be considered
significant (non random), since it takes a lot of changes to
transactions to produce even a small change in the percentage.
This dependence on the antecedent support of the rule and that the
valley is not pointed at the diagonal (which means that even a low
minimal value can exclude a lot of rules) is the main difference
between the information gain and the normalized chi<sup>2</sup>
measure on the one hand and the absolute confidence difference and
difference of the confidence quotient to one on the other.</p>

<p>The sixth to eighth graph show the normalized chi<sup>2</sup> measure
for an antecedent support of 0.2, 0.3, and 0.4. The valleys are very
similar to those for the information difference to the prior confidence,
they only have slightly steeper flanks, especially for low antecedent
support. So in practice there is no big difference between the
information difference and the normalized chi<sup>2</sup> measure.</p>

<table width="100%" border=0 cellpadding=0 cellspacing=0>
<tr><td width="95%" align=right><a href="#top">back to the top</a></td>
    <td width=5></td>
    <td><a href="#top"><img src="uparrow.gif" border=0></a></td></tr>
</table>

<!-- =============================================================== -->

<h4><a name="appear">Item Appearances</a></h4>

<p>My apriori program provides a simple way to restrict the rules to
generate w.r.t. the items that shall appear in them. It accepts a third
optional input file, in which item appearances can be given. For each
item it can be stated whether it may appear in the body (antecedent)