docs/v1.2/group__grp__assoc__rules.html - madlib-site - Git at Google

 <!-- HTML header for doxygen 1.8.4-->
 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
 <html xmlns="http://www.w3.org/1999/xhtml">
 <head>
 <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
 <meta http-equiv="X-UA-Compatible" content="IE=9"/>
 <meta name="generator" content="Doxygen 1.8.4"/>
 <meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/>
 <title>MADlib: Apriori Algorithm</title>
 <link href="tabs.css" rel="stylesheet" type="text/css"/>
 <script type="text/javascript" src="jquery.js"></script>
 <script type="text/javascript" src="dynsections.js"></script>
 <link href="navtree.css" rel="stylesheet" type="text/css"/>
 <script type="text/javascript" src="resize.js"></script>
 <script type="text/javascript" src="navtree.js"></script>
 <script type="text/javascript">
   $(document).ready(initResizable);
   $(window).load(resizeHeight);
 </script>
 <link href="search/search.css" rel="stylesheet" type="text/css"/>
 <script type="text/javascript" src="search/search.js"></script>
 <script type="text/javascript">
   $(document).ready(function() { searchBox.OnSelectItem(0); });
 </script>
 <script type="text/x-mathjax-config">
   MathJax.Hub.Config({
     extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
     jax: ["input/TeX","output/HTML-CSS"],
 });
 </script><script src="../mathjax/MathJax.js"></script>
 <link href="doxygen.css" rel="stylesheet" type="text/css" />
 <link href="madlib_extra.css" rel="stylesheet" type="text/css"/>
 <!-- google analytics -->
 <script>
   (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
   (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
   m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
   })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
   ga('create', 'UA-45382226-1', 'auto');
   ga('send', 'pageview');
 </script>
 </head>
 <body>
 <div id="top"><!-- do not remove this div, it is closed by doxygen! -->
 <div id="titlearea">
 <table cellspacing="0" cellpadding="0">
  <tbody>
  <tr style="height: 56px;">
   <td style="padding-left: 0.5em;">
    <div id="projectname">MADlib
    &#160;<span id="projectnumber">1.2</span> <span style="font-size:10pt; font-style:italic"><a href="../latest/./group__grp__assoc__rules.html"> A newer version is available</a></span>
    </div>
    <div id="projectbrief">User Documentation</div>
   </td>
   <!--BEGIN VERSIONS LINKS-->
     <td style="padding-left: 0.5em;">
       <div class="versionlist"><ul>
         <li class="head">More versions:</li>
         <li><a href="../v1.1/index.html">v1.1</li>
         <li><a href="../v1.0/index.html">v1.0</li>
         <li><a href="../v0.7/index.html">v0.7</li>
         <li><a href="../v0.5/index.html">v0.5</li></ul>
       </div>
     </td>
    <td>        <div id="MSearchBox" class="MSearchBoxInactive">
         <span class="left">
           <img id="MSearchSelect" src="search/mag_sel.png"
                onmouseover="return searchBox.OnSearchSelectShow()"
                onmouseout="return searchBox.OnSearchSelectHide()"
                alt=""/>
           <input type="text" id="MSearchField" value="Search" accesskey="S"
                onfocus="searchBox.OnSearchFieldFocus(true)"
                onblur="searchBox.OnSearchFieldFocus(false)"
                onkeyup="searchBox.OnSearchFieldChange(event)"/>
           </span><span class="right">
             <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
           </span>
         </div>
 </td>
  </tr>
  </tbody>
 </table>
 </div>
 <!-- end header part -->
 <!-- Generated by Doxygen 1.8.4 -->
 <script type="text/javascript">
 var searchBox = new SearchBox("searchBox", "search",false,'Search');
 </script>
 </div><!-- top -->
 <div id="side-nav" class="ui-resizable side-nav-resizable">
   <div id="nav-tree">
     <div id="nav-tree-contents">
       <div id="nav-sync" class="sync"></div>
     </div>
   </div>
   <div id="splitbar" style="-moz-user-select:none;"
        class="ui-resizable-handle">
   </div>
 </div>
 <script type="text/javascript">
 $(document).ready(function(){initNavTree('group__grp__assoc__rules.html','');});
 </script>
 <div id="doc-content">
 <!-- window showing the filter options -->
 <div id="MSearchSelectWindow"
      onmouseover="return searchBox.OnSearchSelectShow()"
      onmouseout="return searchBox.OnSearchSelectHide()"
      onkeydown="return searchBox.OnSearchSelectKey(event)">
 <a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Groups</a></div>

 <!-- iframe showing the search results (closed by default) -->
 <div id="MSearchResultsWindow">
 <iframe src="javascript:void(0)" frameborder="0"
         name="MSearchResults" id="MSearchResults">
 </iframe>
 </div>

 <div class="header">
   <div class="headertitle">
 <div class="title">Apriori Algorithm<div class="ingroups"><a class="el" href="group__grp__association__rules.html">Association rules</a></div></div>  </div>
 </div><!--header-->
 <div class="contents">
 <dl class="section user"><dt>About</dt><dd>This module implements the association rules data mining technique on a transactional data set. Given the names of a table and the columns, minimum support and confidence values, this function generates all single and multidimensional association rules that meet the minimum thresholds.</dd></dl>
 <p>Association rule mining is a widely used technique for discovering relationships between variables in a large data set (e.g items in a store that are commonly purchased together). The classic market basket analysis example using association rules is the "beer and diapers" rule. According to data mining urban legend, a study of customers' purchase behavior in a supermarket found that men often purchased beer and diapers together. After making this discovery, the managers strategically placed beer and diapers closer together on the shelves and saw a dramatic increase in sales. In addition to market basket analysis, association rules are also used in bioinformatics, web analytics, and several other fields.</p>
 <p>This type of data mining algorithm uses transactional data. Every transaction event has a unique identification, and each transaction consists of a set of items (or itemset). Purchases are considered binary (either it was purchased or not), and this implementation does not take into consideration the quantity of each item. For the MADlib association rules function, it is assumed that the data is stored in two columns with one item and transaction id per row. Transactions with multiple items will span multiple rows with one row per item.</p>
 <pre>
      tran_id | product
     ---------+---------
            1 | 1
            1 | 2
            1 | 3
            1 | 4
            2 | 3
            2 | 4
            2 | 5
            3 | 1
            3 | 4
            3 | 6
     ...
 </pre><p><b>Rules</b> </p>
 <p>Association rules take the form "If X, then Y", where X and Y are non-empty itemsets. X and Y are called the antecedent and consequent, or the left-hand- side and right-hand-side, of the rule respectively. Using our previous example, the association rule may state "If {diapers}, then {beer}" with .2 support and .85 confidence.</p>
 <p>Given any association rule "If X, then Y", the association rules function will also calculate the following metrics:</p>
 <ul>
 <li>Support: The ratio of transactions that contain X to all transactions, T <p class="formulaDsp">
 \[ S (X) = \frac{Total X}{Total transactions} \]
 </p>
 </li>
 <li>Confidence: The ratio of transactions that contain \( X,Y \) to transactions that contain \( X \). One could view this metric as the conditional probability of \( Y \) , given \( X \) . \( P(Y|X) \) <p class="formulaDsp">
 \[ C (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X)} \]
 </p>
 </li>
 <li>Lift: The ratio of observed support of \( X,Y \) to the expected support of \( X,Y \) , assuming \( X \) and \( Y \) are independent. <p class="formulaDsp">
 \[ L (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X) \cdot s(Y)} \]
 </p>
 </li>
 <li><p class="startli">Conviction: The ratio of expected support of \( X \) occurring without \( Y \) assuming \( X \) and \( \neg Y \) are independent, to the observed support of \( X \) occuring without \( Y \). If conviction is greater than 1, then this metric shows that incorrect predictions ( \( X \Rightarrow Y \) ) occur less often than if these two actions were independent. This metric can be viewed as the ratio that the association rule would be incorrect if the actions were independent (i.e. a conviction of 1.5 indicates that if the variables were independent, this rule would be incorrect 50% more often.)</p>
 <p class="formulaDsp">
 \[ Conv (X \Rightarrow Y) = \frac{1 - S(Y)}{1 - C(X \Rightarrow Y)} \]
 </p>
 </li>
 </ul>
 <p><b>Apriori</b> <b>algorithm</b> </p>
 <p>Although there are many algorithms that generate association rules, the classic algorithm used is called Apriori (which we implemented in this module). It is a breadth-first search, as opposed to depth-first searches like eclat. Frequent itemsets of order \( n \) are generated from sets of order \( n - 1 \). Using the downward closure property, all sets must have frequent subsets. There are two steps in this algorithm; generating frequent itemsets, and using these itemsets to construct the association rules. A simplified version of the algorithm is as follows, and assumes a minimum level of support and confidence is provided:</p>
 <p><em>Initial</em> <em>step</em> </p>
 <ol type="1">
 <li>Generate all itemsets of order 1</li>
 <li>Eliminate itemsets that have support is less than minimum support</li>
 </ol>
 <p><em>Main</em> <em>algorithm</em> </p>
 <ol type="1">
 <li>For \( n \ge 2 \), generate itemsets of order \( n \) by combining the itemsets of order \( n - 1 \). This is done by doing the union of two itemsets that have identical items except one.</li>
 <li>Eliminate itemsets that have (n-1) order subsets with insufficient support</li>
 <li>Eliminate itemsets with insufficient support</li>
 <li>Repeat until itemsets cannot be generated</li>
 </ol>
 <p><em>Association</em> <em>rule</em> <em>generation</em> </p>
 <p>Given a frequent itemset \( A \) generated from the Apriori algorithm, and all subsets \( B \) , we generate rules such that \( B \Rightarrow (A - B) \) meets minimum confidence requirements.</p>
 <dl class="section user"><dt>Input</dt><dd></dd></dl>
 <p>The input data is expected to be of the following form: </p>
 <pre>{TABLE|VIEW} <em>input_table</em> (
     <em>trans_id</em> INTEGER,
     <em>product</em> TEXT
 )</pre><p>The algorithm will map the product names to consective integer ids starting at 1. If they are already structured this way, then the ids will not change.</p>
 <dl class="section user"><dt>Usage</dt><dd><ul>
 <li>Association rules can be called by: <pre>SELECT <a class="el" href="assoc__rules_8sql__in.html#a68a256d98b82ac15bac7df92e806f6f8">assoc_rules</a>(
     <em>support</em>, <em>confidence</em>,'<em>tid_col</em>','<em>item_col</em>',
     '<em>input_table</em>','<em>output_schema</em>', <em> verbose </em>
     );</pre> This will generate all association rules that meet a minimum support of <em>support</em> and confidence of <em>confidence</em>.</li>
 <li>The results containing the rules, support, confidence, lift, and conviction are stored in the table assoc_rules in the schema specified by <em>output_schema</em>. <pre>
     Table "output_schema.assoc_rules"
       Column   |       Type       | Modifiers
    ------------+------------------+-----------
     ruleid     | integer          |
     pre        | text[]           |
     post       | text[]           |
     support    | double precision |
     confidence | double precision |
     lift       | double precision |
     conviction | double precision |
     Distributed by: (ruleid)</pre></li>
 </ul>
 </dd></dl>
 <p>The <code>pre</code> and <code>post</code> are the itemsets of left and right hand sides of the association rule respectively. The <code>support</code>, <code>confidence</code>, <code>lift</code>, and <code>conviction</code> columns are calculated as mentioned in the about section.</p>
 <pre><dl class="section user"><dt>Implementation Notes</dt><dd></dd></dl>
 <p>The association rules function will always create a table named assoc_rules.
 Please make a copy of this table before running the function again if you would
 like to keep multiple association rule tables.</pre><pre><dl class="section user"><dt>Examples</dt><dd></dd></dl>
 <p>Let us take a look at some sample transactional data and generate association rules:</pre><pre><div class="fragment"><div class="line">DROP TABLE <a class="code" href="robust_8sql__in.html#acede63ea5f809590ccf9745e97dc22c0">IF</a> EXISTS test_data;</div>
 <div class="line">CREATE TABLE test_data (</div>
 <div class="line">    trans_id INT</div>
 <div class="line">    , product text</div>
 <div class="line">);</div>
 <div class="line"></div>
 <div class="line">INSERT INTO test_data VALUES (1, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (1, <span class="stringliteral">&#39;diapers&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (1, <span class="stringliteral">&#39;chips&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (2, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (2, <span class="stringliteral">&#39;diapers&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (3, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (3, <span class="stringliteral">&#39;diapers&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (4, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (4, <span class="stringliteral">&#39;chips&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (5, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (6, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (6, <span class="stringliteral">&#39;diapers&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (6, <span class="stringliteral">&#39;chips&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (7, <span class="stringliteral">&#39;beer&#39;</span>);</div>
 <div class="line">INSERT INTO test_data VALUES (7, <span class="stringliteral">&#39;diapers&#39;</span>);</div>
 </div><!-- fragment --></pre><pre>Let \( min(support) = .25 \) and \( min(confidence) = .5 \), and the output schema be 'myschema'. For this example, we will set verbose to 'true' so that we have some insight into the progress of the function. We can now generate association rules as follows:</pre><pre><div class="fragment"><div class="line"><a class="code" href="robust_8sql__in.html#ac9ebd21770ba37efb90e1ccee36fc103">SELECT</a> * FROM MADlib.assoc_rules (.25, .5, <span class="stringliteral">&#39;trans_id&#39;</span>, <span class="stringliteral">&#39;product&#39;</span>, <span class="stringliteral">&#39;test_data&#39;</span>,<span class="stringliteral">&#39;myschema&#39;</span>, <span class="keyword">false</span>);</div>
 </div><!-- fragment --></pre><pre>This should generate this output:</pre><pre><div class="fragment"><div class="line"> output_schema | output_table | total_rules | total_time</div>
 <div class="line">---------------+--------------+-------------+-----------------</div>
 <div class="line"> myschema      | <a class="code" href="assoc__rules_8sql__in.html#af9456adb6dad01e452415b9a0a5371dc">assoc_rules</a>  |           7 | 00:00:03.162094</div>
 <div class="line">(1 row)</div>
 </div><!-- fragment --></pre><pre>The association rules are stored in the myschema.assoc_rules:</pre><pre><div class="fragment"><div class="line">select * from myschema.assoc_rules order by support desc;</div>
 <div class="line"> ruleid |       pre       |      post      |      support      |    confidence     |       lift        |    conviction</div>
 <div class="line">--------+-----------------+----------------+-------------------+-------------------+-------------------+-------------------</div>
 <div class="line">      4 | {diapers}       | {beer}         | 0.714285714285714 |                 1 |                 1 |                 0</div>
 <div class="line">      2 | {beer}          | {diapers}      | 0.714285714285714 | 0.714285714285714 |                 1 |                 1</div>
 <div class="line">      1 | {chips}         | {beer}         | 0.428571428571429 |                 1 |                 1 |                 0</div>
 <div class="line">      5 | {chips}         | {beer,diapers} | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857</div>
 <div class="line">      6 | {chips,beer}    | {diapers}      | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857</div>
 <div class="line">      7 | {chips,diapers} | {beer}         | 0.285714285714286 |                 1 |                 1 |                 0</div>
 <div class="line">      3 | {chips}         | {diapers}      | 0.285714285714286 | 0.666666666666667 | 0.933333333333333 | 0.857142857142857</div>
 <div class="line">(7 rows)</div>
 </div><!-- fragment --></pre><pre><dl class="section see"><dt>See Also</dt><dd>File <a class="el" href="assoc__rules_8sql__in.html" title="The assoc_rules function computes association rules for a given set of data. The data is assumed to h...">assoc_rules.sql_in</a> documenting the SQL function.
 </dd></dl>
 </pre></div><!-- contents -->
 </div><!-- doc-content -->
 <!-- start footer part -->
 <div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
   <ul>
     <li class="footer">Generated on Thu Jan 9 2014 20:35:40 for MADlib by
     <a href="http://www.doxygen.org/index.html">
     <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.4 </li>
   </ul>
 </div>
 </body>
 </html>
	<!-- HTML header for doxygen 1.8.4-->
	<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
	<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
	<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
	<meta http-equiv="X-UA-Compatible" content="IE=9"/>
	<meta name="generator" content="Doxygen 1.8.4"/>
	<meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/>
	<title>MADlib: Apriori Algorithm</title>
	<link href="tabs.css" rel="stylesheet" type="text/css"/>
	<script type="text/javascript" src="jquery.js"></script>
	<script type="text/javascript" src="dynsections.js"></script>
	<link href="navtree.css" rel="stylesheet" type="text/css"/>
	<script type="text/javascript" src="resize.js"></script>
	<script type="text/javascript" src="navtree.js"></script>
	<script type="text/javascript">
	$(document).ready(initResizable);
	$(window).load(resizeHeight);
	</script>
	<link href="search/search.css" rel="stylesheet" type="text/css"/>
	<script type="text/javascript" src="search/search.js"></script>
	<script type="text/javascript">
	$(document).ready(function() { searchBox.OnSelectItem(0); });
	</script>
	<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
	extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
	jax: ["input/TeX","output/HTML-CSS"],
	});
	</script><script src="../mathjax/MathJax.js"></script>
	<link href="doxygen.css" rel="stylesheet" type="text/css" />
	<link href="madlib_extra.css" rel="stylesheet" type="text/css"/>
	<!-- google analytics -->
	<script>
	(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]\|\|function(){
	(i[r].q=i[r].q\|\|[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
	m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
	})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
	ga('create', 'UA-45382226-1', 'auto');
	ga('send', 'pageview');
	</script>
	</head>
	<body>
	<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
	<div id="titlearea">
	<table cellspacing="0" cellpadding="0">
	<tbody>
	<tr style="height: 56px;">
	<td style="padding-left: 0.5em;">
	<div id="projectname">MADlib
	<span id="projectnumber">1.2</span> <span style="font-size:10pt; font-style:italic"><a href="../latest/./group__grp__assoc__rules.html"> A newer version is available</a></span>
	</div>
	<div id="projectbrief">User Documentation</div>
	</td>
	<!--BEGIN VERSIONS LINKS-->
	<td style="padding-left: 0.5em;">
	<div class="versionlist"><ul>
	<li class="head">More versions:</li>
	<li><a href="../v1.1/index.html">v1.1</li>
	<li><a href="../v1.0/index.html">v1.0</li>
	<li><a href="../v0.7/index.html">v0.7</li>
	<li><a href="../v0.5/index.html">v0.5</li></ul>
	</div>
	</td>
	<td> <div id="MSearchBox" class="MSearchBoxInactive">
	<span class="left">
	<img id="MSearchSelect" src="search/mag_sel.png"
	onmouseover="return searchBox.OnSearchSelectShow()"
	onmouseout="return searchBox.OnSearchSelectHide()"
	alt=""/>
	<input type="text" id="MSearchField" value="Search" accesskey="S"
	onfocus="searchBox.OnSearchFieldFocus(true)"
	onblur="searchBox.OnSearchFieldFocus(false)"
	onkeyup="searchBox.OnSearchFieldChange(event)"/>
	</span><span class="right">
	<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
	</span>
	</div>
	</td>
	</tr>
	</tbody>
	</table>
	</div>
	<!-- end header part -->
	<!-- Generated by Doxygen 1.8.4 -->
	<script type="text/javascript">
	var searchBox = new SearchBox("searchBox", "search",false,'Search');
	</script>
	</div><!-- top -->
	<div id="side-nav" class="ui-resizable side-nav-resizable">
	<div id="nav-tree">
	<div id="nav-tree-contents">
	<div id="nav-sync" class="sync"></div>
	</div>
	</div>
	<div id="splitbar" style="-moz-user-select:none;"
	class="ui-resizable-handle">
	</div>
	</div>
	<script type="text/javascript">
	$(document).ready(function(){initNavTree('group__grp__assoc__rules.html','');});
	</script>
	<div id="doc-content">
	<!-- window showing the filter options -->
	<div id="MSearchSelectWindow"
	onmouseover="return searchBox.OnSearchSelectShow()"
	onmouseout="return searchBox.OnSearchSelectHide()"
	onkeydown="return searchBox.OnSearchSelectKey(event)">
	<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark"> </span>Groups</a></div>

	<!-- iframe showing the search results (closed by default) -->
	<div id="MSearchResultsWindow">
	<iframe src="javascript:void(0)" frameborder="0"
	name="MSearchResults" id="MSearchResults">
	</iframe>
	</div>

	<div class="header">
	<div class="headertitle">
	<div class="title">Apriori Algorithm<div class="ingroups"><a class="el" href="group__grp__association__rules.html">Association rules</a></div></div> </div>
	</div><!--header-->
	<div class="contents">
	<dl class="section user"><dt>About</dt><dd>This module implements the association rules data mining technique on a transactional data set. Given the names of a table and the columns, minimum support and confidence values, this function generates all single and multidimensional association rules that meet the minimum thresholds.</dd></dl>
	<p>Association rule mining is a widely used technique for discovering relationships between variables in a large data set (e.g items in a store that are commonly purchased together). The classic market basket analysis example using association rules is the "beer and diapers" rule. According to data mining urban legend, a study of customers' purchase behavior in a supermarket found that men often purchased beer and diapers together. After making this discovery, the managers strategically placed beer and diapers closer together on the shelves and saw a dramatic increase in sales. In addition to market basket analysis, association rules are also used in bioinformatics, web analytics, and several other fields.</p>
	<p>This type of data mining algorithm uses transactional data. Every transaction event has a unique identification, and each transaction consists of a set of items (or itemset). Purchases are considered binary (either it was purchased or not), and this implementation does not take into consideration the quantity of each item. For the MADlib association rules function, it is assumed that the data is stored in two columns with one item and transaction id per row. Transactions with multiple items will span multiple rows with one row per item.</p>
	<pre>
	tran_id \| product
	---------+---------
	1 \| 1
	1 \| 2
	1 \| 3
	1 \| 4
	2 \| 3
	2 \| 4
	2 \| 5
	3 \| 1
	3 \| 4
	3 \| 6
	...
	</pre><p><b>Rules</b> </p>
	<p>Association rules take the form "If X, then Y", where X and Y are non-empty itemsets. X and Y are called the antecedent and consequent, or the left-hand- side and right-hand-side, of the rule respectively. Using our previous example, the association rule may state "If {diapers}, then {beer}" with .2 support and .85 confidence.</p>
	<p>Given any association rule "If X, then Y", the association rules function will also calculate the following metrics:</p>
	<ul>
	<li>Support: The ratio of transactions that contain X to all transactions, T <p class="formulaDsp">
	\[ S (X) = \frac{Total X}{Total transactions} \]
	</p>
	</li>
	<li>Confidence: The ratio of transactions that contain \( X,Y \) to transactions that contain \( X \). One could view this metric as the conditional probability of \( Y \) , given \( X \) . \( P(Y\|X) \) <p class="formulaDsp">
	\[ C (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X)} \]
	</p>
	</li>
	<li>Lift: The ratio of observed support of \( X,Y \) to the expected support of \( X,Y \) , assuming \( X \) and \( Y \) are independent. <p class="formulaDsp">
	\[ L (X \Rightarrow Y) = \frac{s(X \cap Y )}{s(X) \cdot s(Y)} \]
	</p>
	</li>
	<li><p class="startli">Conviction: The ratio of expected support of \( X \) occurring without \( Y \) assuming \( X \) and \( \neg Y \) are independent, to the observed support of \( X \) occuring without \( Y \). If conviction is greater than 1, then this metric shows that incorrect predictions ( \( X \Rightarrow Y \) ) occur less often than if these two actions were independent. This metric can be viewed as the ratio that the association rule would be incorrect if the actions were independent (i.e. a conviction of 1.5 indicates that if the variables were independent, this rule would be incorrect 50% more often.)</p>
	<p class="formulaDsp">
	\[ Conv (X \Rightarrow Y) = \frac{1 - S(Y)}{1 - C(X \Rightarrow Y)} \]
	</p>
	</li>
	</ul>
	<p><b>Apriori</b> <b>algorithm</b> </p>
	<p>Although there are many algorithms that generate association rules, the classic algorithm used is called Apriori (which we implemented in this module). It is a breadth-first search, as opposed to depth-first searches like eclat. Frequent itemsets of order \( n \) are generated from sets of order \( n - 1 \). Using the downward closure property, all sets must have frequent subsets. There are two steps in this algorithm; generating frequent itemsets, and using these itemsets to construct the association rules. A simplified version of the algorithm is as follows, and assumes a minimum level of support and confidence is provided:</p>
	<p><em>Initial</em> <em>step</em> </p>
	<ol type="1">
	<li>Generate all itemsets of order 1</li>
	<li>Eliminate itemsets that have support is less than minimum support</li>
	</ol>
	<p><em>Main</em> <em>algorithm</em> </p>
	<ol type="1">
	<li>For \( n \ge 2 \), generate itemsets of order \( n \) by combining the itemsets of order \( n - 1 \). This is done by doing the union of two itemsets that have identical items except one.</li>
	<li>Eliminate itemsets that have (n-1) order subsets with insufficient support</li>
	<li>Eliminate itemsets with insufficient support</li>
	<li>Repeat until itemsets cannot be generated</li>
	</ol>
	<p><em>Association</em> <em>rule</em> <em>generation</em> </p>
	<p>Given a frequent itemset \( A \) generated from the Apriori algorithm, and all subsets \( B \) , we generate rules such that \( B \Rightarrow (A - B) \) meets minimum confidence requirements.</p>
	<dl class="section user"><dt>Input</dt><dd></dd></dl>
	<p>The input data is expected to be of the following form: </p>
	<pre>{TABLE\|VIEW} <em>input_table</em> (
	<em>trans_id</em> INTEGER,
	<em>product</em> TEXT
	)</pre><p>The algorithm will map the product names to consective integer ids starting at 1. If they are already structured this way, then the ids will not change.</p>
	<dl class="section user"><dt>Usage</dt><dd><ul>
	<li>Association rules can be called by: <pre>SELECT <a class="el" href="assoc__rules_8sql__in.html#a68a256d98b82ac15bac7df92e806f6f8">assoc_rules</a>(
	<em>support</em>, <em>confidence</em>,'<em>tid_col</em>','<em>item_col</em>',
	'<em>input_table</em>','<em>output_schema</em>', <em> verbose </em>
	);</pre> This will generate all association rules that meet a minimum support of <em>support</em> and confidence of <em>confidence</em>.</li>
	<li>The results containing the rules, support, confidence, lift, and conviction are stored in the table assoc_rules in the schema specified by <em>output_schema</em>. <pre>
	Table "output_schema.assoc_rules"
	Column \| Type \| Modifiers
	------------+------------------+-----------
	ruleid \| integer \|
	pre \| text[] \|
	post \| text[] \|
	support \| double precision \|
	confidence \| double precision \|
	lift \| double precision \|
	conviction \| double precision \|
	Distributed by: (ruleid)</pre></li>
	</ul>
	</dd></dl>
	<p>The <code>pre</code> and <code>post</code> are the itemsets of left and right hand sides of the association rule respectively. The <code>support</code>, <code>confidence</code>, <code>lift</code>, and <code>conviction</code> columns are calculated as mentioned in the about section.</p>
	<pre><dl class="section user"><dt>Implementation Notes</dt><dd></dd></dl>
	<p>The association rules function will always create a table named assoc_rules.
	Please make a copy of this table before running the function again if you would
	like to keep multiple association rule tables.</pre><pre><dl class="section user"><dt>Examples</dt><dd></dd></dl>
	<p>Let us take a look at some sample transactional data and generate association rules:</pre><pre><div class="fragment"><div class="line">DROP TABLE <a class="code" href="robust_8sql__in.html#acede63ea5f809590ccf9745e97dc22c0">IF</a> EXISTS test_data;</div>
	<div class="line">CREATE TABLE test_data (</div>
	<div class="line"> trans_id INT</div>
	<div class="line"> , product text</div>
	<div class="line">);</div>
	<div class="line"></div>
	<div class="line">INSERT INTO test_data VALUES (1, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (1, <span class="stringliteral">'diapers'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (1, <span class="stringliteral">'chips'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (2, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (2, <span class="stringliteral">'diapers'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (3, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (3, <span class="stringliteral">'diapers'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (4, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (4, <span class="stringliteral">'chips'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (5, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (6, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (6, <span class="stringliteral">'diapers'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (6, <span class="stringliteral">'chips'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (7, <span class="stringliteral">'beer'</span>);</div>
	<div class="line">INSERT INTO test_data VALUES (7, <span class="stringliteral">'diapers'</span>);</div>
	</div><!-- fragment --></pre><pre>Let \( min(support) = .25 \) and \( min(confidence) = .5 \), and the output schema be 'myschema'. For this example, we will set verbose to 'true' so that we have some insight into the progress of the function. We can now generate association rules as follows:</pre><pre><div class="fragment"><div class="line"><a class="code" href="robust_8sql__in.html#ac9ebd21770ba37efb90e1ccee36fc103">SELECT</a> * FROM MADlib.assoc_rules (.25, .5, <span class="stringliteral">'trans_id'</span>, <span class="stringliteral">'product'</span>, <span class="stringliteral">'test_data'</span>,<span class="stringliteral">'myschema'</span>, <span class="keyword">false</span>);</div>
	</div><!-- fragment --></pre><pre>This should generate this output:</pre><pre><div class="fragment"><div class="line"> output_schema \| output_table \| total_rules \| total_time</div>
	<div class="line">---------------+--------------+-------------+-----------------</div>
	<div class="line"> myschema \| <a class="code" href="assoc__rules_8sql__in.html#af9456adb6dad01e452415b9a0a5371dc">assoc_rules</a> \| 7 \| 00:00:03.162094</div>
	<div class="line">(1 row)</div>
	</div><!-- fragment --></pre><pre>The association rules are stored in the myschema.assoc_rules:</pre><pre><div class="fragment"><div class="line">select * from myschema.assoc_rules order by support desc;</div>
	<div class="line"> ruleid \| pre \| post \| support \| confidence \| lift \| conviction</div>
	<div class="line">--------+-----------------+----------------+-------------------+-------------------+-------------------+-------------------</div>
	<div class="line"> 4 \| {diapers} \| {beer} \| 0.714285714285714 \| 1 \| 1 \| 0</div>
	<div class="line"> 2 \| {beer} \| {diapers} \| 0.714285714285714 \| 0.714285714285714 \| 1 \| 1</div>
	<div class="line"> 1 \| {chips} \| {beer} \| 0.428571428571429 \| 1 \| 1 \| 0</div>
	<div class="line"> 5 \| {chips} \| {beer,diapers} \| 0.285714285714286 \| 0.666666666666667 \| 0.933333333333333 \| 0.857142857142857</div>
	<div class="line"> 6 \| {chips,beer} \| {diapers} \| 0.285714285714286 \| 0.666666666666667 \| 0.933333333333333 \| 0.857142857142857</div>
	<div class="line"> 7 \| {chips,diapers} \| {beer} \| 0.285714285714286 \| 1 \| 1 \| 0</div>
	<div class="line"> 3 \| {chips} \| {diapers} \| 0.285714285714286 \| 0.666666666666667 \| 0.933333333333333 \| 0.857142857142857</div>
	<div class="line">(7 rows)</div>
	</div><!-- fragment --></pre><pre><dl class="section see"><dt>See Also</dt><dd>File <a class="el" href="assoc__rules_8sql__in.html" title="The assoc_rules function computes association rules for a given set of data. The data is assumed to h...">assoc_rules.sql_in</a> documenting the SQL function.
	</dd></dl>
	</pre></div><!-- contents -->
	</div><!-- doc-content -->
	<!-- start footer part -->
	<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
	<ul>
	<li class="footer">Generated on Thu Jan 9 2014 20:35:40 for MADlib by
	<a href="http://www.doxygen.org/index.html">
	<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.4 </li>
	</ul>
	</div>
	</body>
	</html>