apriori.html

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

but it causes problems if some other measure is used. For these other
measures it is often much more appropriate to call the support of the
antecedent of the rule, i.e. the support of {A, B} in the example above,
the support of the rule.</p>

<p>The difference can also be stated in the following way: For [Agrawal
et al. 1993], the support of the rule is the (relative) number of cases
in which the rule is correct (i.e., in which the presence of the item C
follows from the presence of the items A and B), whereas for me (and
thus my apriori program) the support of a rule is the (relative) number
of cases in which it is applicable (i.e., in which the antecedent of the
rule holds), although in some of these cases it may be false (because
only the items A and B are present, but the item C is missing).</p>

<p>One reason for this, as already mentioned, is that the definition
of [Agrawal et al. 1993] does not work well for evaluation measures
other than rule confidence. This is explained in more detail below.
Another reason is that I prefer the support of a rule to say something
about the "statistical" support of a rule and its confidence, i.e.,
from how many cases the confidence is computed in order to express
how well founded the assertion about the confidence is.</p>

<p>Maybe an example will make this clearer. Suppose you have a die which
you suspect to be biased. To test this hypothesis, you throw the die,
say, a thousand times. 307 times the 6 turns up. Hence you assume that
the die is actually biased, since the relative frequency is about 30%
although for an unbiased die it should be around 17%. Now, what is the
"statistical" support of this assertion, i.e., on how many experiments
does it rest? Obviously it rests on all 1000 experiments and not only
on the 307 experiments in which the 6 turned up. This is so, simply
because you had to do 1000 experiments to find out that the relative
frequency is around 30% and not only the 307 in which a 6 turned up.</p>

<p>Or suppose you are doing an opinion poll to find out about the
acceptance of a certain political party, maybe with the usual question
"If an election were held next Sunday ...?" You ask 2000 persons, of
which 857 say that they would vote for the party you are interested in.
What is the support of the assertion that this party would get around
43% of all votes? It is the size of your sample, i.e., all 2000 persons,
and not only the 857 that answered in the positive. Again you had to ask
all 2000 people to find out about the percentage of 43%. Of course, you
could have asked fewer people, say, 100, of which, say, 43 said that
they would vote for the party, but then your assertion would be less
reliable, because it is less "supported". The number of votes for the
party could also be 40% or 50%, because of some random influences. Such
deviations are much less likely, if you asked 2000 persons, since then
the random influences can be expected to cancel out.</p>

<p>The rule support can be used to select association rules by stating
a lower bound for the support of a rule. This is equivalent to saying
that you are interested only in such rules that have a large enough
statistical basis (since my apriori program uses the term "support"
in my interpretation and not in the one used by [Agrawal et al. 1993]).
The default value for the support limit is 10%. It can be changed
with the option <tt>-s</tt>. If the number given is negative, it is
interpreted as an absolute number (number of transactions) rather than
a percentage. (Note that in this case the option <tt>-a</tt> reverses
its meaning: if it is not given only the absolute support is printed,
if it is added, the relative supoort is printed, too.) The lower bound
for the rule support is combined with the lower bound for the rule
confidence, i.e., my apriori program generates only rules the confidence
of which is greater than or equal to the confidence limit <i>and</i> the
support of which is greater than or equal to the support limit.</p>

<p>Despite the above arguments in favor of my definition of the support
of an association rule, a rule support compatibility mode is available.
With the option <tt>-o</tt> the original rule support definition can be
selected. In this case the support of an association rule is the support
of the set with the items in the antecedent and the consequent of the
rule, i.e. the support of a rule as defined in [Agrawal et al. 1993].
</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>

<!-- =============================================================== -->
<p><img src="line.gif" alt="" height=7 width=704></p>

<h3><a name="target">Target Types</a></h3>

<p>The target type, which can be selected via the option <tt>-t</tt>,
is either association rules (option <tt>-tr</tt>, default), frequent
item sets (option <tt>-ts</tt>), closed item sets (option <tt>-tc</tt>),
maximal item sets (option <tt>-tm</tt>), or association hyperedges
(option <tt>-th</tt>).</p>

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

<h4><a name="assrules">Association Rules (default, option -tr)</a></h4>

<p>By default my apriori program produces association rules with
a single item in the consequent. The restriction to single item
consequents is due to the following considerations: In the first place,
association rule mining usually produces too many rules even if one
confines oneself to rules with only one item in the consequent. So why
should one make the situation worse by allowing more than one item in
the consequent? (It merely blows up the output size.)</p>

<p>Secondly, I do not know any application in which rules with more
than one item in the consequent are of any real use. The reason, in
my opinion, is that such more complex rules add almost nothing to the
insights about the data set. To understand this, consider the simpler
rules that correspond to a rule with multiple items in the consequent,
that is, rules having the same antecedent and consequents with only
single items from the consequent of the complex rule. All of these
rules must necessarily be in the output, because neither their support
nor their confidence can be less than that of the more complex rule.
That is, if you have a rule c d &lt;- a b, you will necessarily also
have the rules c &lt;- a b and d &lt;- a b in the output. Of course,
these latter two rules together do <i>not</i> say the same as the more
complex rule. However, what do you gain from the additional information
the more complex rule gives you? How can you use it? And is this little
extra information worth having to analyze a much bigger rule set?</p>

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

<h4><a name="itemsets">Frequent Item Sets (option -ts)</a></h4>

<p>Sometimes one may not want to find association rules, but only the
frequent item sets underlying them. That is, one wants to find all
item sets with a support exceeding a certain threshold. My apriori
program supports this search, too: If the option <tt>-ts</tt> is
given, only frequent item sets are determined.</p>

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

<h4><a name="closed">Closed Item Sets (option -tc)</a></h4>

<p>A frequent item set is called <i>closed</i> if no superset has the
same support. If the option <tt>-tc</tt> is given, the found frequent
item sets are subsequently filtered and only the closed item sets
are kept.</p>

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

<h4><a name="maximal">Maximal Item Sets (option -tm)</a></h4>

<p>A frequent item set is called <i>maximal</i> if no superset is
frequent, i.e., has a support exceeding the minimal support. If the
option <tt>-tm</tt> is given, the found frequent item sets are
subsequently filtered and only the maximal item sets are kept.</p>

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

<h4><a name="hyperedges">Association Hyperedges (option -th)</a></h4>

<p>My apriori program can also find association hyperedges, i.e., sets
of items that are strongly predictive w.r.t. each other. In this mode
no rules are generated, only item sets are selected. The selection
criterion is as follows: Given an item set with enough support (option
<tt>-s</tt>), all rules are checked which can be formed using this set
with all items appearing in the rule. For example, for the item set
{a b c}, the rules c &lt;- a b, b &lt;- a c, a &lt;- b c would be
considered. The confidences of these rules are computed and averaged.
If the resulting average confidence is greater than the minimal
confidence (option <tt>-c</tt>), the item set is selected. (I am
grateful to Bastien Duclaux for requesting the possibility to generate
association hyperedges.)</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>

<!-- =============================================================== -->
<p><img src="line.gif" alt="" height=7 width=704></p>

<h3><a name="select">Extended Rule Selection</a></h3>

<p>If rules are selected using the rule confidence, the following
problem arises: "Good" rules (rules that are often true) are not
always "interesting" rules (rules that reveal something about the
interdependence of the items). You certainly know the examples that
are usually given to illustrate this fact. For instance, it is easy
to find out in a medical database that the rule "pregnant -&gt; female"
is true with a confidence of 100%. Hence it is a perfect rule, it
never fails, but, of course, this is not very surprising. Although
the measures explained below cannot deal with this problem (which is
semantical), they may be able to improve on the results in a related
case.</p>

<p>Let us look at the supermarket example again and let us assume
that 60% of all customers buy some kind of bread. Consider the rule
"cheese -&gt; bread", which holds with a confidence of, say, 62%.
Is this an important rule? Obviously not, since the fact that the
customer buys cheese does not have a significant influence on him/her
buying bread: The percentages are almost the same. But if you had set
a confidence limit of 60%, you would get both rules "-&gt; bread"
(confidence 60%) and "cheese -&gt; bread" (confidence 62%), although
the first would suffice (the first, since it is the simpler of the
two). The idea of all measures that can be used in addition or instead
of rule confidence is to handle such situations and to suppress the
second rule.</p>

<p>In addition, consider the following case: Assume that the confidence
of the rule "cheese -&gt; bread" is not 62% but 35%. With a confidence
limit of 60% it would not be selected, but it may be very important to
know about this rule! Together with cheese bread is bought much less
frequent than it is bought at all. Is cheese some kind of substitute
for bread, so that one does not need any bread, if one has cheese? Ok,
maybe this is not a very good example. However, what can be seen is
that a rule with low confidence can be very interesting, since it may
capture an important influence. Furthermore, this is a way to express
negation (though only in the consequent of a rule), since
"cheese -&gt; bread" with confidence 35% is obviously equivalent to
"cheese -&gt; no bread" with confidence 65%. This also makes clear
why the support of the item set that contains all items in the body
<i>and</i> the head of the rule is not appropriate for this measure.
An important rule may have confidence 0 and thus a support (in the
interpretation of [Agrawal et al. 1993]) of 0. Hence it is not
reasonable to set a lower bound for this kind of support.</p>

<p>I hope that the intention underlying all this is already clear:
Potentially interesting rules differ significantly in their confidence
from the confidence of rules with the same consequent, but a simpler
antecedent. Adding an item to the antecedent is informative only if it
significantly changes the confidence of the rule. Otherwise the simpler
rule suffices.</p>

<p>Unfortunately the measures other than rule confidence do not solve
the rule selection problem in the very general form in which it was
stated above. It is not that easy to deal with all rules that have a
simpler antecedent, to keep track of which of these rules were selected
(this obviously influences the selection of more complicated rules),
to deal with the special type of Poincare paradox that can occur, etc.
Hence the measures always compare the confidence of a rule with the
confidence of the rule with empty antecedent, i.e. with the relative
frequency of the consequent.</p>

<p>I call the confidence of a rule with empty antecedent the prior
confidence, since it is the confidence that the item in the consequent
of the rule will be present in an item set prior to any information
about other items that are present. The confidence of a rule with
non-empty antecedent (and the same consequent) I call the posterior
confidence, since it is the confidence that the item in the consequent
of the rule will be present after it gets known that the items in the
antecedent of the rule are present.</p>

<p>All measures that can be used in addition to rule confidence are
computed from these two values: the prior confidence and the posterior
confidence. Only those rules are selected for which the value of the
chosen additional evaluation measure exceeds or is equal to a certain
limit. The measures are chosen with the option <tt>-e</tt>, the limit
is passed to the program via the option <tt>-d</tt>. The default value
for the limit is 10%.</p>

<p>All additional rule evaluation measures are combined with the limits
for rule confidence and rule support. I.e., my apriori program selects
only those rules the confidence of which is greater than or equal to
the confidence limit, the support of which is greater than or equal to
the support limit, <i>and</i> for which the additional evaluation value
is greater than or equal to the limit for this measure. The default is
to use no additional evaluation measure, i.e., to rely only on rule
confidence and rule support. Of course you can remove the restriction
that the rule confidence must exceed a certain limit by simply setting
this limit to zero. In this case rules are selected using only the
limits for the rule support and the additional evaluation measure.