diff options
author | Patrick Wendell <pwendell@apache.org> | 2015-04-17 05:52:53 +0000 |
---|---|---|
committer | Patrick Wendell <pwendell@apache.org> | 2015-04-17 05:52:53 +0000 |
commit | d49935af658ee525496c7ac598f7352c7793d6f8 (patch) | |
tree | 1813e84df9974a07d595ba24f0fe0e832f182f05 /site/docs/1.3.1/mllib-frequent-pattern-mining.html | |
parent | 9695c4519404b689f29bc0fbc1a2eefa3eb33806 (diff) | |
download | spark-website-d49935af658ee525496c7ac598f7352c7793d6f8.tar.gz spark-website-d49935af658ee525496c7ac598f7352c7793d6f8.tar.bz2 spark-website-d49935af658ee525496c7ac598f7352c7793d6f8.zip |
Adding docs for 1.2.2 and 1.3.1
Diffstat (limited to 'site/docs/1.3.1/mllib-frequent-pattern-mining.html')
-rw-r--r-- | site/docs/1.3.1/mllib-frequent-pattern-mining.html | 253 |
1 files changed, 253 insertions, 0 deletions
diff --git a/site/docs/1.3.1/mllib-frequent-pattern-mining.html b/site/docs/1.3.1/mllib-frequent-pattern-mining.html new file mode 100644 index 000000000..7536c8778 --- /dev/null +++ b/site/docs/1.3.1/mllib-frequent-pattern-mining.html @@ -0,0 +1,253 @@ +<!DOCTYPE html> +<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]--> +<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]--> +<!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]--> +<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]--> + <head> + <meta charset="utf-8"> + <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> + <title>Frequent Pattern Mining - MLlib - Spark 1.3.1 Documentation</title> + + + + + <link rel="stylesheet" href="css/bootstrap.min.css"> + <style> + body { + padding-top: 60px; + padding-bottom: 40px; + } + </style> + <meta name="viewport" content="width=device-width"> + <link rel="stylesheet" href="css/bootstrap-responsive.min.css"> + <link rel="stylesheet" href="css/main.css"> + + <script src="js/vendor/modernizr-2.6.1-respond-1.1.0.min.js"></script> + + <link rel="stylesheet" href="css/pygments-default.css"> + + + <!-- Google analytics script --> + <script type="text/javascript"> + var _gaq = _gaq || []; + _gaq.push(['_setAccount', 'UA-32518208-2']); + _gaq.push(['_trackPageview']); + + (function() { + var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; + ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; + var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); + })(); + </script> + + + </head> + <body> + <!--[if lt IE 7]> + <p class="chromeframe">You are using an outdated browser. <a href="http://browsehappy.com/">Upgrade your browser today</a> or <a href="http://www.google.com/chromeframe/?redirect=true">install Google Chrome Frame</a> to better experience this site.</p> + <![endif]--> + + <!-- This code is taken from http://twitter.github.com/bootstrap/examples/hero.html --> + + <div class="navbar navbar-fixed-top" id="topbar"> + <div class="navbar-inner"> + <div class="container"> + <div class="brand"><a href="index.html"> + <img src="img/spark-logo-hd.png" style="height:50px;"/></a><span class="version">1.3.1</span> + </div> + <ul class="nav"> + <!--TODO(andyk): Add class="active" attribute to li some how.--> + <li><a href="index.html">Overview</a></li> + + <li class="dropdown"> + <a href="#" class="dropdown-toggle" data-toggle="dropdown">Programming Guides<b class="caret"></b></a> + <ul class="dropdown-menu"> + <li><a href="quick-start.html">Quick Start</a></li> + <li><a href="programming-guide.html">Spark Programming Guide</a></li> + <li class="divider"></li> + <li><a href="streaming-programming-guide.html">Spark Streaming</a></li> + <li><a href="sql-programming-guide.html">DataFrames and SQL</a></li> + <li><a href="mllib-guide.html">MLlib (Machine Learning)</a></li> + <li><a href="graphx-programming-guide.html">GraphX (Graph Processing)</a></li> + <li><a href="bagel-programming-guide.html">Bagel (Pregel on Spark)</a></li> + </ul> + </li> + + <li class="dropdown"> + <a href="#" class="dropdown-toggle" data-toggle="dropdown">API Docs<b class="caret"></b></a> + <ul class="dropdown-menu"> + <li><a href="api/scala/index.html#org.apache.spark.package">Scala</a></li> + <li><a href="api/java/index.html">Java</a></li> + <li><a href="api/python/index.html">Python</a></li> + </ul> + </li> + + <li class="dropdown"> + <a href="#" class="dropdown-toggle" data-toggle="dropdown">Deploying<b class="caret"></b></a> + <ul class="dropdown-menu"> + <li><a href="cluster-overview.html">Overview</a></li> + <li><a href="submitting-applications.html">Submitting Applications</a></li> + <li class="divider"></li> + <li><a href="spark-standalone.html">Spark Standalone</a></li> + <li><a href="running-on-mesos.html">Mesos</a></li> + <li><a href="running-on-yarn.html">YARN</a></li> + <li class="divider"></li> + <li><a href="ec2-scripts.html">Amazon EC2</a></li> + </ul> + </li> + + <li class="dropdown"> + <a href="api.html" class="dropdown-toggle" data-toggle="dropdown">More<b class="caret"></b></a> + <ul class="dropdown-menu"> + <li><a href="configuration.html">Configuration</a></li> + <li><a href="monitoring.html">Monitoring</a></li> + <li><a href="tuning.html">Tuning Guide</a></li> + <li><a href="job-scheduling.html">Job Scheduling</a></li> + <li><a href="security.html">Security</a></li> + <li><a href="hardware-provisioning.html">Hardware Provisioning</a></li> + <li><a href="hadoop-third-party-distributions.html">3<sup>rd</sup>-Party Hadoop Distros</a></li> + <li class="divider"></li> + <li><a href="building-spark.html">Building Spark</a></li> + <li><a href="https://cwiki.apache.org/confluence/display/SPARK/Contributing+to+Spark">Contributing to Spark</a></li> + <li><a href="https://cwiki.apache.org/confluence/display/SPARK/Supplemental+Spark+Projects">Supplemental Projects</a></li> + </ul> + </li> + </ul> + <!--<p class="navbar-text pull-right"><span class="version-text">v1.3.1</span></p>--> + </div> + </div> + </div> + + <div class="container" id="content"> + + <h1 class="title"><a href="mllib-guide.html">MLlib</a> - Frequent Pattern Mining</h1> + + + <p>Mining frequent items, itemsets, subsequences, or other substructures is usually among the +first steps to analyze a large-scale dataset, which has been an active research topic in +data mining for years. +We refer users to Wikipedia’s <a href="http://en.wikipedia.org/wiki/Association_rule_learning">association rule learning</a> +for more information. +MLlib provides a parallel implementation of FP-growth, +a popular algorithm to mining frequent itemsets.</p> + +<h2 id="fp-growth">FP-growth</h2> + +<p>The FP-growth algorithm is described in the paper +<a href="http://dx.doi.org/10.1145/335191.335372">Han et al., Mining frequent patterns without candidate generation</a>, +where “FP” stands for frequent pattern. +Given a dataset of transactions, the first step of FP-growth is to calculate item frequencies and identify frequent items. +Different from <a href="http://en.wikipedia.org/wiki/Apriori_algorithm">Apriori-like</a> algorithms designed for the same purpose, +the second step of FP-growth uses a suffix tree (FP-tree) structure to encode transactions without generating candidate sets +explicitly, which are usually expensive to generate. +After the second step, the frequent itemsets can be extracted from the FP-tree. +In MLlib, we implemented a parallel version of FP-growth called PFP, +as described in <a href="http://dx.doi.org/10.1145/1454008.1454027">Li et al., PFP: Parallel FP-growth for query recommendation</a>. +PFP distributes the work of growing FP-trees based on the suffices of transactions, +and hence more scalable than a single-machine implementation. +We refer users to the papers for more details.</p> + +<p>MLlib’s FP-growth implementation takes the following (hyper-)parameters:</p> + +<ul> + <li><code>minSupport</code>: the minimum support for an itemset to be identified as frequent. +For example, if an item appears 3 out of 5 transactions, it has a support of 3/5=0.6.</li> + <li><code>numPartitions</code>: the number of partitions used to distribute the work.</li> +</ul> + +<p><strong>Examples</strong></p> + +<div class="codetabs"> +<div data-lang="scala"> + + <p><a href="api/java/org/apache/spark/mllib/fpm/FPGrowth.html"><code>FPGrowth</code></a> implements the +FP-growth algorithm. +It take a <code>JavaRDD</code> of transactions, where each transaction is an <code>Iterable</code> of items of a generic type. +Calling <code>FPGrowth.run</code> with transactions returns an +<a href="api/java/org/apache/spark/mllib/fpm/FPGrowthModel.html"><code>FPGrowthModel</code></a> +that stores the frequent itemsets with their frequencies.</p> + + <div class="highlight"><pre><code class="language-scala" data-lang="scala"><span class="k">import</span> <span class="nn">org.apache.spark.rdd.RDD</span> +<span class="k">import</span> <span class="nn">org.apache.spark.mllib.fpm.</span><span class="o">{</span><span class="nc">FPGrowth</span><span class="o">,</span> <span class="nc">FPGrowthModel</span><span class="o">}</span> + +<span class="k">val</span> <span class="n">transactions</span><span class="k">:</span> <span class="kt">RDD</span><span class="o">[</span><span class="kt">Array</span><span class="o">[</span><span class="kt">String</span><span class="o">]]</span> <span class="k">=</span> <span class="o">...</span> + +<span class="k">val</span> <span class="n">fpg</span> <span class="k">=</span> <span class="k">new</span> <span class="nc">FPGrowth</span><span class="o">()</span> + <span class="o">.</span><span class="n">setMinSupport</span><span class="o">(</span><span class="mf">0.2</span><span class="o">)</span> + <span class="o">.</span><span class="n">setNumPartitions</span><span class="o">(</span><span class="mi">10</span><span class="o">)</span> +<span class="k">val</span> <span class="n">model</span> <span class="k">=</span> <span class="n">fpg</span><span class="o">.</span><span class="n">run</span><span class="o">(</span><span class="n">transactions</span><span class="o">)</span> + +<span class="n">model</span><span class="o">.</span><span class="n">freqItemsets</span><span class="o">.</span><span class="n">collect</span><span class="o">().</span><span class="n">foreach</span> <span class="o">{</span> <span class="n">itemset</span> <span class="k">=></span> + <span class="n">println</span><span class="o">(</span><span class="n">itemset</span><span class="o">.</span><span class="n">items</span><span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">"["</span><span class="o">,</span> <span class="s">","</span><span class="o">,</span> <span class="s">"]"</span><span class="o">)</span> <span class="o">+</span> <span class="s">", "</span> <span class="o">+</span> <span class="n">itemset</span><span class="o">.</span><span class="n">freq</span><span class="o">)</span> +<span class="o">}</span></code></pre></div> + + </div> + +<div data-lang="java"> + + <p><a href="api/java/org/apache/spark/mllib/fpm/FPGrowth.html"><code>FPGrowth</code></a> implements the +FP-growth algorithm. +It take an <code>RDD</code> of transactions, where each transaction is an <code>Array</code> of items of a generic type. +Calling <code>FPGrowth.run</code> with transactions returns an +<a href="api/java/org/apache/spark/mllib/fpm/FPGrowthModel.html"><code>FPGrowthModel</code></a> +that stores the frequent itemsets with their frequencies.</p> + + <div class="highlight"><pre><code class="language-java" data-lang="java"><span class="kn">import</span> <span class="nn">java.util.List</span><span class="o">;</span> + +<span class="kn">import</span> <span class="nn">com.google.common.base.Joiner</span><span class="o">;</span> + +<span class="kn">import</span> <span class="nn">org.apache.spark.api.java.JavaRDD</span><span class="o">;</span> +<span class="kn">import</span> <span class="nn">org.apache.spark.mllib.fpm.FPGrowth</span><span class="o">;</span> +<span class="kn">import</span> <span class="nn">org.apache.spark.mllib.fpm.FPGrowthModel</span><span class="o">;</span> + +<span class="n">JavaRDD</span><span class="o"><</span><span class="n">List</span><span class="o"><</span><span class="n">String</span><span class="o">>></span> <span class="n">transactions</span> <span class="o">=</span> <span class="o">...</span> + +<span class="n">FPGrowth</span> <span class="n">fpg</span> <span class="o">=</span> <span class="k">new</span> <span class="nf">FPGrowth</span><span class="o">()</span> + <span class="o">.</span><span class="na">setMinSupport</span><span class="o">(</span><span class="mf">0.2</span><span class="o">)</span> + <span class="o">.</span><span class="na">setNumPartitions</span><span class="o">(</span><span class="mi">10</span><span class="o">);</span> +<span class="n">FPGrowthModel</span><span class="o"><</span><span class="n">String</span><span class="o">></span> <span class="n">model</span> <span class="o">=</span> <span class="n">fpg</span><span class="o">.</span><span class="na">run</span><span class="o">(</span><span class="n">transactions</span><span class="o">);</span> + +<span class="k">for</span> <span class="o">(</span><span class="n">FPGrowth</span><span class="o">.</span><span class="na">FreqItemset</span><span class="o"><</span><span class="n">String</span><span class="o">></span> <span class="nl">itemset:</span> <span class="n">model</span><span class="o">.</span><span class="na">freqItemsets</span><span class="o">().</span><span class="na">toJavaRDD</span><span class="o">().</span><span class="na">collect</span><span class="o">())</span> <span class="o">{</span> + <span class="n">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="s">"["</span> <span class="o">+</span> <span class="n">Joiner</span><span class="o">.</span><span class="na">on</span><span class="o">(</span><span class="s">","</span><span class="o">).</span><span class="na">join</span><span class="o">(</span><span class="n">s</span><span class="o">.</span><span class="na">javaItems</span><span class="o">())</span> <span class="o">+</span> <span class="s">"], "</span> <span class="o">+</span> <span class="n">s</span><span class="o">.</span><span class="na">freq</span><span class="o">());</span> +<span class="o">}</span></code></pre></div> + + </div> +</div> + + + </div> <!-- /container --> + + <script src="js/vendor/jquery-1.8.0.min.js"></script> + <script src="js/vendor/bootstrap.min.js"></script> + <script src="js/main.js"></script> + + <!-- MathJax Section --> + <script type="text/x-mathjax-config"> + MathJax.Hub.Config({ + TeX: { equationNumbers: { autoNumber: "AMS" } } + }); + </script> + <script> + // Note that we load MathJax this way to work with local file (file://), HTTP and HTTPS. + // We could use "//cdn.mathjax...", but that won't support "file://". + (function(d, script) { + script = d.createElement('script'); + script.type = 'text/javascript'; + script.async = true; + script.onload = function(){ + MathJax.Hub.Config({ + tex2jax: { + inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], + displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], + processEscapes: true, + skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'] + } + }); + }; + script.src = ('https:' == document.location.protocol ? 'https://' : 'http://') + + 'cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'; + d.getElementsByTagName('head')[0].appendChild(script); + }(document)); + </script> + </body> +</html> |