spark-master/mllib-frequent-pattern-mining.html


<!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 - spark.mllib - Spark 2.0.0 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">

        
    </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">2.0.0</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, Datasets 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="sparkr.html">SparkR (R 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>
                                <li><a href="api/R/index.html">R</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>
                            </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 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">v2.0.0</span></p>-->
                </div>
            </div>
        </div>

        <div class="container-wrapper">

            
                <div class="left-menu-wrapper">
    <div class="left-menu">
        <h3><a href="ml-guide.html">spark.ml package</a></h3>
        
<ul>

    <li>
        <a href="ml-guide.html">
            
                Overview: estimators, transformers and pipelines
            
        </a>
    </li>
    

    <li>
        <a href="ml-features.html">
            
                Extracting, transforming and selecting features
            
        </a>
    </li>
    

    <li>
        <a href="ml-classification-regression.html">
            
                Classification and Regression
            
        </a>
    </li>
    

    <li>
        <a href="ml-clustering.html">
            
                Clustering
            
        </a>
    </li>
    

    <li>
        <a href="ml-collaborative-filtering.html">
            
                Collaborative filtering
            
        </a>
    </li>
    

    <li>
        <a href="ml-advanced.html">
            
                Advanced topics
            
        </a>
    </li>
    

</ul>

        <h3><a href="mllib-guide.html">spark.mllib package</a></h3>
        
<ul>

    <li>
        <a href="mllib-data-types.html">
            
                Data types
            
        </a>
    </li>
    

    <li>
        <a href="mllib-statistics.html">
            
                Basic statistics
            
        </a>
    </li>
    

    <li>
        <a href="mllib-classification-regression.html">
            
                Classification and regression
            
        </a>
    </li>
    

    <li>
        <a href="mllib-collaborative-filtering.html">
            
                Collaborative filtering
            
        </a>
    </li>
    

    <li>
        <a href="mllib-clustering.html">
            
                Clustering
            
        </a>
    </li>
    

    <li>
        <a href="mllib-dimensionality-reduction.html">
            
                Dimensionality reduction
            
        </a>
    </li>
    

    <li>
        <a href="mllib-feature-extraction.html">
            
                Feature extraction and transformation
            
        </a>
    </li>
    

    <li>
        <a href="mllib-frequent-pattern-mining.html">
            
                <b>Frequent pattern mining</b>
            
        </a>
    </li>
    
        
<ul>

    <li>
        <a href="mllib-frequent-pattern-mining.html#fp-growth">
            
                FP-growth
            
        </a>
    </li>
    

    <li>
        <a href="mllib-frequent-pattern-mining.html#association-rules">
            
                association rules
            
        </a>
    </li>
    

    <li>
        <a href="mllib-frequent-pattern-mining.html#prefix-span">
            
                PrefixSpan
            
        </a>
    </li>
    

</ul>

    
    <li>
        <a href="mllib-evaluation-metrics.html">
            
                Evaluation metrics
            
        </a>
    </li>
    

    <li>
        <a href="mllib-pmml-model-export.html">
            
                PMML model export
            
        </a>
    </li>
    

    <li>
        <a href="mllib-optimization.html">
            
                Optimization (developer)
            
        </a>
    </li>
    

</ul>

    </div>
</div>
                <input id="nav-trigger" class="nav-trigger" checked type="checkbox">
                <label for="nav-trigger"></label>
                <div class="content-with-sidebar" id="content">
                    
                        <h1 class="title">Frequent Pattern Mining - spark.mllib</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&#8217;s <a href="http://en.wikipedia.org/wiki/Association_rule_learning">association rule learning</a>
for more information.
<code>spark.mllib</code> 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 &#8220;FP&#8221; 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 <code>spark.mllib</code>, 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><code>spark.mllib</code>&#8217;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/scala/index.html#org.apache.spark.mllib.fpm.FPGrowth"><code>FPGrowth</code></a> implements the
FP-growth algorithm.
It take a <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/scala/index.html#org.apache.spark.mllib.fpm.FPGrowthModel"><code>FPGrowthModel</code></a>
that stores the frequent itemsets with their frequencies.  The following
example illustrates how to mine frequent itemsets and association rules
(see <a href="mllib-frequent-pattern-mining.html#association-rules">Association
Rules</a> for
details) from <code>transactions</code>.</p>

    <p>Refer to the <a href="api/scala/index.html#org.apache.spark.mllib.fpm.FPGrowth"><code>FPGrowth</code> Scala docs</a> for details on the API.</p>

    <div class="highlight"><pre><span class="k">import</span> <span class="nn">org.apache.spark.mllib.fpm.FPGrowth</span>
<span class="k">import</span> <span class="nn">org.apache.spark.rdd.RDD</span>

<span class="k">val</span> <span class="n">data</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">textFile</span><span class="o">(</span><span class="s">&quot;data/mllib/sample_fpgrowth.txt&quot;</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="n">data</span><span class="o">.</span><span class="n">map</span><span class="o">(</span><span class="n">s</span> <span class="k">=&gt;</span> <span class="n">s</span><span class="o">.</span><span class="n">trim</span><span class="o">.</span><span class="n">split</span><span class="o">(</span><span class="sc">&#39; &#39;</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">=&gt;</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">&quot;[&quot;</span><span class="o">,</span> <span class="s">&quot;,&quot;</span><span class="o">,</span> <span class="s">&quot;]&quot;</span><span class="o">)</span> <span class="o">+</span> <span class="s">&quot;, &quot;</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>

<span class="k">val</span> <span class="n">minConfidence</span> <span class="k">=</span> <span class="mf">0.8</span>
<span class="n">model</span><span class="o">.</span><span class="n">generateAssociationRules</span><span class="o">(</span><span class="n">minConfidence</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">rule</span> <span class="k">=&gt;</span>
  <span class="n">println</span><span class="o">(</span>
    <span class="n">rule</span><span class="o">.</span><span class="n">antecedent</span><span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;[&quot;</span><span class="o">,</span> <span class="s">&quot;,&quot;</span><span class="o">,</span> <span class="s">&quot;]&quot;</span><span class="o">)</span>
      <span class="o">+</span> <span class="s">&quot; =&gt; &quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="n">consequent</span> <span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;[&quot;</span><span class="o">,</span> <span class="s">&quot;,&quot;</span><span class="o">,</span> <span class="s">&quot;]&quot;</span><span class="o">)</span>
      <span class="o">+</span> <span class="s">&quot;, &quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="n">confidence</span><span class="o">)</span>
<span class="o">}</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/scala/org/apache/spark/examples/mllib/SimpleFPGrowth.scala" in the Spark repo.</small></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>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.  The following
example illustrates how to mine frequent itemsets and association rules
(see <a href="mllib-frequent-pattern-mining.html#association-rules">Association
Rules</a> for
details) from <code>transactions</code>.</p>

    <p>Refer to the <a href="api/java/org/apache/spark/mllib/fpm/FPGrowth.html"><code>FPGrowth</code> Java docs</a> for details on the API.</p>

    <div class="highlight"><pre><span class="kn">import</span> <span class="nn">java.util.Arrays</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.List</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.api.java.JavaSparkContext</span><span class="o">;</span>

<span class="kn">import</span> <span class="nn">org.apache.spark.mllib.fpm.AssociationRules</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">&lt;</span><span class="n">String</span><span class="o">&gt;</span> <span class="n">data</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">textFile</span><span class="o">(</span><span class="s">&quot;data/mllib/sample_fpgrowth.txt&quot;</span><span class="o">);</span>

<span class="n">JavaRDD</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;&gt;</span> <span class="n">transactions</span> <span class="o">=</span> <span class="n">data</span><span class="o">.</span><span class="na">map</span><span class="o">(</span>
  <span class="k">new</span> <span class="n">Function</span><span class="o">&lt;</span><span class="n">String</span><span class="o">,</span> <span class="n">List</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;&gt;()</span> <span class="o">{</span>
    <span class="kd">public</span> <span class="n">List</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;</span> <span class="nf">call</span><span class="o">(</span><span class="n">String</span> <span class="n">line</span><span class="o">)</span> <span class="o">{</span>
      <span class="n">String</span><span class="o">[]</span> <span class="n">parts</span> <span class="o">=</span> <span class="n">line</span><span class="o">.</span><span class="na">split</span><span class="o">(</span><span class="s">&quot; &quot;</span><span class="o">);</span>
      <span class="k">return</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="n">parts</span><span class="o">);</span>
    <span class="o">}</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">&lt;</span><span class="n">String</span><span class="o">&gt;</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">&lt;</span><span class="n">String</span><span class="o">&gt;</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">&quot;[&quot;</span> <span class="o">+</span> <span class="n">itemset</span><span class="o">.</span><span class="na">javaItems</span><span class="o">()</span> <span class="o">+</span> <span class="s">&quot;], &quot;</span> <span class="o">+</span> <span class="n">itemset</span><span class="o">.</span><span class="na">freq</span><span class="o">());</span>
<span class="o">}</span>

<span class="kt">double</span> <span class="n">minConfidence</span> <span class="o">=</span> <span class="mf">0.8</span><span class="o">;</span>
<span class="k">for</span> <span class="o">(</span><span class="n">AssociationRules</span><span class="o">.</span><span class="na">Rule</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;</span> <span class="n">rule</span>
  <span class="o">:</span> <span class="n">model</span><span class="o">.</span><span class="na">generateAssociationRules</span><span class="o">(</span><span class="n">minConfidence</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="n">rule</span><span class="o">.</span><span class="na">javaAntecedent</span><span class="o">()</span> <span class="o">+</span> <span class="s">&quot; =&gt; &quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="na">javaConsequent</span><span class="o">()</span> <span class="o">+</span> <span class="s">&quot;, &quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="na">confidence</span><span class="o">());</span>
<span class="o">}</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/java/org/apache/spark/examples/mllib/JavaSimpleFPGrowth.java" in the Spark repo.</small></div>

  </div>

<div data-lang="python">

    <p><a href="api/python/pyspark.mllib.html#pyspark.mllib.fpm.FPGrowth"><code>FPGrowth</code></a> implements the
FP-growth algorithm.
It take an <code>RDD</code> of transactions, where each transaction is an <code>List</code> of items of a generic type.
Calling <code>FPGrowth.train</code> with transactions returns an
<a href="api/python/pyspark.mllib.html#pyspark.mllib.fpm.FPGrowthModel"><code>FPGrowthModel</code></a>
that stores the frequent itemsets with their frequencies.</p>

    <p>Refer to the <a href="api/python/pyspark.mllib.html#pyspark.mllib.fpm.FPGrowth"><code>FPGrowth</code> Python docs</a> for more details on the API.</p>

    <div class="highlight"><pre><span class="kn">from</span> <span class="nn">pyspark.mllib.fpm</span> <span class="kn">import</span> <span class="n">FPGrowth</span>

<span class="n">data</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">textFile</span><span class="p">(</span><span class="s">&quot;data/mllib/sample_fpgrowth.txt&quot;</span><span class="p">)</span>
<span class="n">transactions</span> <span class="o">=</span> <span class="n">data</span><span class="o">.</span><span class="n">map</span><span class="p">(</span><span class="k">lambda</span> <span class="n">line</span><span class="p">:</span> <span class="n">line</span><span class="o">.</span><span class="n">strip</span><span class="p">()</span><span class="o">.</span><span class="n">split</span><span class="p">(</span><span class="s">&#39; &#39;</span><span class="p">))</span>
<span class="n">model</span> <span class="o">=</span> <span class="n">FPGrowth</span><span class="o">.</span><span class="n">train</span><span class="p">(</span><span class="n">transactions</span><span class="p">,</span> <span class="n">minSupport</span><span class="o">=</span><span class="mf">0.2</span><span class="p">,</span> <span class="n">numPartitions</span><span class="o">=</span><span class="mi">10</span><span class="p">)</span>
<span class="n">result</span> <span class="o">=</span> <span class="n">model</span><span class="o">.</span><span class="n">freqItemsets</span><span class="p">()</span><span class="o">.</span><span class="n">collect</span><span class="p">()</span>
<span class="k">for</span> <span class="n">fi</span> <span class="ow">in</span> <span class="n">result</span><span class="p">:</span>
    <span class="k">print</span><span class="p">(</span><span class="n">fi</span><span class="p">)</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/python/mllib/fpgrowth_example.py" in the Spark repo.</small></div>

  </div>

</div>

<h2 id="association-rules">Association Rules</h2>

<div class="codetabs">
<div data-lang="scala">
    <p><a href="api/scala/index.html#org.apache.spark.mllib.fpm.AssociationRules">AssociationRules</a>
implements a parallel rule generation algorithm for constructing rules
that have a single item as the consequent.</p>

    <p>Refer to the <a href="api/java/org/apache/spark/mllib/fpm/AssociationRules.html"><code>AssociationRules</code> Scala docs</a> for details on the API.</p>

    <div class="highlight"><pre><span class="k">import</span> <span class="nn">org.apache.spark.mllib.fpm.AssociationRules</span>
<span class="k">import</span> <span class="nn">org.apache.spark.mllib.fpm.FPGrowth.FreqItemset</span>

<span class="k">val</span> <span class="n">freqItemsets</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="nc">Seq</span><span class="o">(</span>
  <span class="k">new</span> <span class="nc">FreqItemset</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="s">&quot;a&quot;</span><span class="o">),</span> <span class="mi">15L</span><span class="o">),</span>
  <span class="k">new</span> <span class="nc">FreqItemset</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="s">&quot;b&quot;</span><span class="o">),</span> <span class="mi">35L</span><span class="o">),</span>
  <span class="k">new</span> <span class="nc">FreqItemset</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="s">&quot;a&quot;</span><span class="o">,</span> <span class="s">&quot;b&quot;</span><span class="o">),</span> <span class="mi">12L</span><span class="o">)</span>
<span class="o">))</span>

<span class="k">val</span> <span class="n">ar</span> <span class="k">=</span> <span class="k">new</span> <span class="nc">AssociationRules</span><span class="o">()</span>
  <span class="o">.</span><span class="n">setMinConfidence</span><span class="o">(</span><span class="mf">0.8</span><span class="o">)</span>
<span class="k">val</span> <span class="n">results</span> <span class="k">=</span> <span class="n">ar</span><span class="o">.</span><span class="n">run</span><span class="o">(</span><span class="n">freqItemsets</span><span class="o">)</span>

<span class="n">results</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">rule</span> <span class="k">=&gt;</span>
  <span class="n">println</span><span class="o">(</span><span class="s">&quot;[&quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="n">antecedent</span><span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;,&quot;</span><span class="o">)</span>
    <span class="o">+</span> <span class="s">&quot;=&gt;&quot;</span>
    <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="n">consequent</span><span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;,&quot;</span><span class="o">)</span> <span class="o">+</span> <span class="s">&quot;],&quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="n">confidence</span><span class="o">)</span>
<span class="o">}</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/scala/org/apache/spark/examples/mllib/AssociationRulesExample.scala" in the Spark repo.</small></div>

  </div>

<div data-lang="java">
    <p><a href="api/java/org/apache/spark/mllib/fpm/AssociationRules.html">AssociationRules</a>
implements a parallel rule generation algorithm for constructing rules
that have a single item as the consequent.</p>

    <p>Refer to the <a href="api/java/org/apache/spark/mllib/fpm/AssociationRules.html"><code>AssociationRules</code> Java docs</a> for details on the API.</p>

    <div class="highlight"><pre><span class="kn">import</span> <span class="nn">java.util.Arrays</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.api.java.JavaSparkContext</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">org.apache.spark.mllib.fpm.AssociationRules</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.FPGrowth.FreqItemset</span><span class="o">;</span>

<span class="n">JavaRDD</span><span class="o">&lt;</span><span class="n">FPGrowth</span><span class="o">.</span><span class="na">FreqItemset</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;&gt;</span> <span class="n">freqItemsets</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">parallelize</span><span class="o">(</span><span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span>
  <span class="k">new</span> <span class="n">FreqItemset</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;(</span><span class="k">new</span> <span class="n">String</span><span class="o">[]</span> <span class="o">{</span><span class="s">&quot;a&quot;</span><span class="o">},</span> <span class="mi">15L</span><span class="o">),</span>
  <span class="k">new</span> <span class="n">FreqItemset</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;(</span><span class="k">new</span> <span class="n">String</span><span class="o">[]</span> <span class="o">{</span><span class="s">&quot;b&quot;</span><span class="o">},</span> <span class="mi">35L</span><span class="o">),</span>
  <span class="k">new</span> <span class="n">FreqItemset</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;(</span><span class="k">new</span> <span class="n">String</span><span class="o">[]</span> <span class="o">{</span><span class="s">&quot;a&quot;</span><span class="o">,</span> <span class="s">&quot;b&quot;</span><span class="o">},</span> <span class="mi">12L</span><span class="o">)</span>
<span class="o">));</span>

<span class="n">AssociationRules</span> <span class="n">arules</span> <span class="o">=</span> <span class="k">new</span> <span class="nf">AssociationRules</span><span class="o">()</span>
  <span class="o">.</span><span class="na">setMinConfidence</span><span class="o">(</span><span class="mf">0.8</span><span class="o">);</span>
<span class="n">JavaRDD</span><span class="o">&lt;</span><span class="n">AssociationRules</span><span class="o">.</span><span class="na">Rule</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;&gt;</span> <span class="n">results</span> <span class="o">=</span> <span class="n">arules</span><span class="o">.</span><span class="na">run</span><span class="o">(</span><span class="n">freqItemsets</span><span class="o">);</span>

<span class="k">for</span> <span class="o">(</span><span class="n">AssociationRules</span><span class="o">.</span><span class="na">Rule</span><span class="o">&lt;</span><span class="n">String</span><span class="o">&gt;</span> <span class="n">rule</span> <span class="o">:</span> <span class="n">results</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="n">rule</span><span class="o">.</span><span class="na">javaAntecedent</span><span class="o">()</span> <span class="o">+</span> <span class="s">&quot; =&gt; &quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="na">javaConsequent</span><span class="o">()</span> <span class="o">+</span> <span class="s">&quot;, &quot;</span> <span class="o">+</span> <span class="n">rule</span><span class="o">.</span><span class="na">confidence</span><span class="o">());</span>
<span class="o">}</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/java/org/apache/spark/examples/mllib/JavaAssociationRulesExample.java" in the Spark repo.</small></div>

  </div>
</div>

<h2 id="prefixspan">PrefixSpan</h2>

<p>PrefixSpan is a sequential pattern mining algorithm described in
<a href="http://dx.doi.org/10.1109%2FTKDE.2004.77">Pei et al., Mining Sequential Patterns by Pattern-Growth: The
PrefixSpan Approach</a>. We refer
the reader to the referenced paper for formalizing the sequential
pattern mining problem.</p>

<p><code>spark.mllib</code>&#8217;s PrefixSpan implementation takes the following parameters:</p>

<ul>
  <li><code>minSupport</code>: the minimum support required to be considered a frequent
sequential pattern.</li>
  <li><code>maxPatternLength</code>: the maximum length of a frequent sequential
pattern. Any frequent pattern exceeding this length will not be
included in the results.</li>
  <li><code>maxLocalProjDBSize</code>: the maximum number of items allowed in a
prefix-projected database before local iterative processing of the
projected database begins. This parameter should be tuned with respect
to the size of your executors.</li>
</ul>

<p><strong>Examples</strong></p>

<p>The following example illustrates PrefixSpan running on the sequences
(using same notation as Pei et al):</p>

<pre><code>  &lt;(12)3&gt;
  &lt;1(32)(12)&gt;
  &lt;(12)5&gt;
  &lt;6&gt;
</code></pre>

<div class="codetabs">
<div data-lang="scala">

    <p><a href="api/scala/index.html#org.apache.spark.mllib.fpm.PrefixSpan"><code>PrefixSpan</code></a> implements the
PrefixSpan algorithm.
Calling <code>PrefixSpan.run</code> returns a
<a href="api/scala/index.html#org.apache.spark.mllib.fpm.PrefixSpanModel"><code>PrefixSpanModel</code></a>
that stores the frequent sequences with their frequencies.</p>

    <p>Refer to the <a href="api/scala/index.html#org.apache.spark.mllib.fpm.PrefixSpan"><code>PrefixSpan</code> Scala docs</a> and <a href="api/scala/index.html#org.apache.spark.mllib.fpm.PrefixSpanModel"><code>PrefixSpanModel</code> Scala docs</a> for details on the API.</p>

    <div class="highlight"><pre><span class="k">import</span> <span class="nn">org.apache.spark.mllib.fpm.PrefixSpan</span>

<span class="k">val</span> <span class="n">sequences</span> <span class="k">=</span> <span class="n">sc</span><span class="o">.</span><span class="n">parallelize</span><span class="o">(</span><span class="nc">Seq</span><span class="o">(</span>
  <span class="nc">Array</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">),</span> <span class="nc">Array</span><span class="o">(</span><span class="mi">3</span><span class="o">)),</span>
  <span class="nc">Array</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="mi">1</span><span class="o">),</span> <span class="nc">Array</span><span class="o">(</span><span class="mi">3</span><span class="o">,</span> <span class="mi">2</span><span class="o">),</span> <span class="nc">Array</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">)),</span>
  <span class="nc">Array</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">),</span> <span class="nc">Array</span><span class="o">(</span><span class="mi">5</span><span class="o">)),</span>
  <span class="nc">Array</span><span class="o">(</span><span class="nc">Array</span><span class="o">(</span><span class="mi">6</span><span class="o">))</span>
<span class="o">),</span> <span class="mi">2</span><span class="o">).</span><span class="n">cache</span><span class="o">()</span>
<span class="k">val</span> <span class="n">prefixSpan</span> <span class="k">=</span> <span class="k">new</span> <span class="nc">PrefixSpan</span><span class="o">()</span>
  <span class="o">.</span><span class="n">setMinSupport</span><span class="o">(</span><span class="mf">0.5</span><span class="o">)</span>
  <span class="o">.</span><span class="n">setMaxPatternLength</span><span class="o">(</span><span class="mi">5</span><span class="o">)</span>
<span class="k">val</span> <span class="n">model</span> <span class="k">=</span> <span class="n">prefixSpan</span><span class="o">.</span><span class="n">run</span><span class="o">(</span><span class="n">sequences</span><span class="o">)</span>
<span class="n">model</span><span class="o">.</span><span class="n">freqSequences</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">freqSequence</span> <span class="k">=&gt;</span>
  <span class="n">println</span><span class="o">(</span>
    <span class="n">freqSequence</span><span class="o">.</span><span class="n">sequence</span><span class="o">.</span><span class="n">map</span><span class="o">(</span><span class="k">_</span><span class="o">.</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;[&quot;</span><span class="o">,</span> <span class="s">&quot;, &quot;</span><span class="o">,</span> <span class="s">&quot;]&quot;</span><span class="o">)).</span><span class="n">mkString</span><span class="o">(</span><span class="s">&quot;[&quot;</span><span class="o">,</span> <span class="s">&quot;, &quot;</span><span class="o">,</span> <span class="s">&quot;]&quot;</span><span class="o">)</span> <span class="o">+</span>
      <span class="s">&quot;, &quot;</span> <span class="o">+</span> <span class="n">freqSequence</span><span class="o">.</span><span class="n">freq</span><span class="o">)</span>
<span class="o">}</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/scala/org/apache/spark/examples/mllib/PrefixSpanExample.scala" in the Spark repo.</small></div>

  </div>

<div data-lang="java">

    <p><a href="api/java/org/apache/spark/mllib/fpm/PrefixSpan.html"><code>PrefixSpan</code></a> implements the
PrefixSpan algorithm.
Calling <code>PrefixSpan.run</code> returns a
<a href="api/java/org/apache/spark/mllib/fpm/PrefixSpanModel.html"><code>PrefixSpanModel</code></a>
that stores the frequent sequences with their frequencies.</p>

    <p>Refer to the <a href="api/java/org/apache/spark/mllib/fpm/PrefixSpan.html"><code>PrefixSpan</code> Java docs</a> and <a href="api/java/org/apache/spark/mllib/fpm/PrefixSpanModel.html"><code>PrefixSpanModel</code> Java docs</a> for details on the API.</p>

    <div class="highlight"><pre><span class="kn">import</span> <span class="nn">java.util.Arrays</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">java.util.List</span><span class="o">;</span>

<span class="kn">import</span> <span class="nn">org.apache.spark.mllib.fpm.PrefixSpan</span><span class="o">;</span>
<span class="kn">import</span> <span class="nn">org.apache.spark.mllib.fpm.PrefixSpanModel</span><span class="o">;</span>

<span class="n">JavaRDD</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;&gt;&gt;</span> <span class="n">sequences</span> <span class="o">=</span> <span class="n">sc</span><span class="o">.</span><span class="na">parallelize</span><span class="o">(</span><span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span>
  <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">),</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">3</span><span class="o">)),</span>
  <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">1</span><span class="o">),</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">3</span><span class="o">,</span> <span class="mi">2</span><span class="o">),</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">)),</span>
  <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">),</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">5</span><span class="o">)),</span>
  <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="mi">6</span><span class="o">))</span>
<span class="o">),</span> <span class="mi">2</span><span class="o">);</span>
<span class="n">PrefixSpan</span> <span class="n">prefixSpan</span> <span class="o">=</span> <span class="k">new</span> <span class="nf">PrefixSpan</span><span class="o">()</span>
  <span class="o">.</span><span class="na">setMinSupport</span><span class="o">(</span><span class="mf">0.5</span><span class="o">)</span>
  <span class="o">.</span><span class="na">setMaxPatternLength</span><span class="o">(</span><span class="mi">5</span><span class="o">);</span>
<span class="n">PrefixSpanModel</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="n">model</span> <span class="o">=</span> <span class="n">prefixSpan</span><span class="o">.</span><span class="na">run</span><span class="o">(</span><span class="n">sequences</span><span class="o">);</span>
<span class="k">for</span> <span class="o">(</span><span class="n">PrefixSpan</span><span class="o">.</span><span class="na">FreqSequence</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="nl">freqSeq:</span> <span class="n">model</span><span class="o">.</span><span class="na">freqSequences</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="n">freqSeq</span><span class="o">.</span><span class="na">javaSequence</span><span class="o">()</span> <span class="o">+</span> <span class="s">&quot;, &quot;</span> <span class="o">+</span> <span class="n">freqSeq</span><span class="o">.</span><span class="na">freq</span><span class="o">());</span>
<span class="o">}</span>
</pre></div>
    <div><small>Find full example code at "examples/src/main/java/org/apache/spark/examples/mllib/JavaPrefixSpanExample.java" in the Spark repo.</small></div>

  </div>
</div>


                </div>
            
             <!-- /container -->
        </div>

        <script src="js/vendor/jquery-1.8.0.min.js"></script>
        <script src="js/vendor/bootstrap.min.js"></script>
        <script src="js/vendor/anchor.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>