apriori.html

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

appearances file containing only an indicator like "both", which
does not restrict the appearance of any items.</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="output">Output Format</a></h3>

<h4><a name="ruleout">Output Format for Association Rules</a></h4>

<p>Each line of the output file contains one association rule in the
format</p>
<p><tt>c &lt;- a b ... (x%, y%)</tt></p>
<p>where a, b, and c are item identifiers, and</p>

<table border=0 cellpadding=0 cellspacing=0>
<tr><td valign=top>x</td><td width=10></td>
    <td>the percentage of transactions that contain all items appearing
    in the rule body (antecedent), that is, in the example above,
    a and b. (support of the rule, i.e., the support in my
    interpretation)</td>
<tr><td valign=top>y</td><td></td>
    <td>the confidence of the rule, which is computed as the quotient of
    the percentage of transactions that contain all items appearing in
    the rule body (antecedent) and the rule head (consequent) - that is,
    in the example above, a, b, and c - and the above percentage x.</td>
    </tr>
</table>

<p>If the option -o is used, x is replaced by the rule support in the
original definition (i.e., the one used by [Agrawal et al. 1993]),
namely the percentage of transactions that contain all items appearing
in the rule (antecedent) and the rule head (consequent), that is, in
the example above, a, b, and c. The value of y, however, is still
computed from the value of x as described above.</p>

<p>If the option -x is given, both types of rule support (support of
all items in the rule and support of the items in the body/antecedent
of the rule) will be printed. The confidence of a rule (see above) is
the quotient of the two support values (* 100%), i.e., a rule will
be printed as</p>
<p><tt>c &lt;- a b ... (x<sub>1</sub>%, x<sub>2</sub>%, y%)</tt></p>
<p>where x<sub>1</sub> is the support of the set of all items in the
rule, x<sub>2</sub> is the support of the set of items in the body
(antecedent) of the rule, and y = x<sub>1</sub>/x<sub>2</sub> * 100%
is the confidence of the rule.</p>

<p>If the option -a is given, the support percentage x is supplemented
by the absolute number of transactions underlying it:</p>
<p><tt>c &lt;- a b ... (x%/s, y%)</tt></p>
<p>where s is the absolute number of transactions. If the option -x is
given, the absolute support is printed for both types of rule support.
</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="setout">Output Format for Frequent Item Sets</a></h4>

<p>Each line of the output file contains one item set in the format</p>
<p><tt>a b c ... (x%)</tt></p>
<p>where a, b, and c are item identifiers and x is the percentage of
transactions that contain this item set (item set support).</p>

<p>If the option -a is given, this percentage is supplemented by the
absolute number of transactions underlying it:</p>
<p><tt>a b c ... (x%/s)</tt></p>
<p>where s is the absolute number of transactions.</p>

<p>If the option -x is given, the percentage of transactions that are
identical to the item set is printed, too (whereas the normal support
is the percentage of transactions that are a superset of the item set):
</p>
<p><tt>a b c ... (x%, %y)</tt></p>
<p>where x is the normal item set support and y is the percentage of
transactions identical to the item set. (This output option was added
in response to a request by Laura Maruster.) If the option -a is also
given, both percentages are supplemented by the absolute number of
transactions underlying these percentages.</p>

<p>Note that for frequent item sets the option -x cannot be combined
with the option -y. That is, in order to compute the second support
measure for item sets, the transactions have to be loaded into memory.
</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="edgeout">Output Format for Association Hyperedges</a></h4>

<p>Each line of the output file contains one hyperedge the format</p>
<p><tt>a b c ... (x%, y%)</tt></p>
<p>where a, b, and c are item identifiers, and</p>

<table border=0 cellpadding=0 cellspacing=0>
<tr><td valign=top>x</td><td width=10></td>
    <td>the percentage of transactions that contain all items appearing
    in the hyperedge, that is, in the example above, a, b, and c.</td>
    </tr>
<tr><td valign=top>y</td><td></td>
    <td>the average confidence of all rules that can be formed using
    the items in the hyperedge with all items appearing in the rule
    (see above), i.e., for the example above, the average confidence
    of the rules c &lt;- a b, b &lt;- a c, and a &lt;- b c.</td></tr>
</table>

<p>If the option -a is given, the support percentage x is supplemented
by the absolute number of transactions underlying it:</p>
<p><tt>a b c ... (x%/s, y%)</tt></p>
<p>where s is the absolute number of transactions.</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="compopt">Compilation Options</a></h3>

<p>The program can be compiled with two additional compilation options
(see <tt>makefile</tt>), namely <tt>-DBENCH</tt> and <tt>-DARCH64</tt>.
</p>

<p>Compiling the program with <tt>-DBENCH</tt> produces a version that
prints some benchmark information on termination, in particular about
the memory used during the item set tree construction (number of nodes,
counters, necessary counters, child pointers, necessary child pointers).
Collecting the memory usage information slightly, but negligibly
increases the execution time.</p>

<p>Compiling the program with <tt>-DARCH64</tt> produces a version for
64 bit machines (architecture model: pointers are 64 bits, integers are
32 bits wide), by removing some alignment issues in the transaction and
item set tree representations, which would otherwise lead to bus errors.
These adaptations slightly, but negligibly increase memory consumption.
(I am grateful to Anthony Casaletto, SPSS Inc., for helping me a lot to
identify these alignment problems, by compiling and testing the program
on a 64 bit machine, since I do not have access to one.)</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="copying">Copying</a></h3>

<p>apriori -
   find association rules/hyperedges with apriori algorithm<br>
   copyright &copy; 1996-2003  Christian Borgelt</p>

<p>This program is free software; you can redistribute it and/or
modify it under the terms of the
<a href="http://www.fsf.org/copyleft/lesser.html">
GNU Lesser (Library) General Public License</a> as published by the
<a href="http://www.fsf.org">Free Software Foundation</a>.</p>

<p>This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
<a href="http://www.fsf.org/copyleft/lesser.html">
GNU Lesser (Library) General Public License</a> for more details.</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="download">Download</a></h3>

<p><a href="http://fuzzy.cs.uni-magdeburg.de/~borgelt/apriori.html">
Download page</a> with most recent version.</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="contact">Contact</a></h3>

<table border=0 cellpadding=0 cellspacing=0>
<tr><td valign=top>Snail mail:</td><td width=10></td>
    <td><a href="http://fuzzy.cs.uni-magdeburg.de/~borgelt/index.html">
        Christian Borgelt</a><br>
        <a href="http://fuzzy.cs.uni-magdeburg.de/index.html">
        Working Group Neural Networks and Fuzzy Systems</a><br>
        <a href="http://www-iws.cs.uni-magdeburg.de/iws.html"> 
        Department of Knowledge Processing and Language Engineering</a><br>
        <a href="http://www.cs.uni-magdeburg.de/">
        School of Computer Science</a><br>
        <a href="http://www.uni-magdeburg.de/">
        Otto-von-Guericke-University of Magdeburg</a><br>
        Universit&auml;tsplatz 2<br>
        D-39106 Magdeburg<br>
        Germany</td></tr>
<tr><td valign=top>E-mail:</td><td></td>
    <td><a href="mailto:[e-mail]">
        [e-mail]</a><br>
        <a href="mailto:[e-mail]">
        [e-mail]</a></td></tr>
<tr><td>Phone:</td><td></td>
    <td>[phone]</td></tr>
<tr><td>Fax:</td><td></td>
    <td>[phone]</td></tr>
<tr><td>Office:</td><td></td>
    <td>29.015</td></tr>
</table>

<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>

<address>&copy; 2002-2004
<a href="mailto:[e-mail]">Christian Borgelt</a>
</address>
<!-- Created: Thu May 24 12:28:05 CEST 2001 -->
<!-- hhmts start -->
Last modified: Tue Nov 23 13:49:10 CET 2004
<!-- hhmts end -->
</body>
</html>