content/docs/0.9/libs/ml/als.html - flink-web - Git at Google

 <!--
 Licensed to the Apache Software Foundation (ASF) under one
 or more contributor license agreements.  See the NOTICE file
 distributed with this work for additional information
 regarding copyright ownership.  The ASF licenses this file
 to you under the Apache License, Version 2.0 (the
 "License"); you may not use this file except in compliance
 with the License.  You may obtain a copy of the License at

 http://www.apache.org/licenses/LICENSE-2.0

 Unless required by applicable law or agreed to in writing,
 software distributed under the License is distributed on an
 "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 KIND, either express or implied.  See the License for the
 specific language governing permissions and limitations
 under the License.
 -->
 <!DOCTYPE html>

 <html lang="en">
   <head>
     <meta charset="utf-8">
     <meta http-equiv="X-UA-Compatible" content="IE=edge">
     <meta name="viewport" content="width=device-width, initial-scale=1">
     <!-- The above 3 meta tags *must* come first in the head; any other head content must come *after* these tags -->

     <title>Apache Flink 0.9.0 Documentation: FlinkML - Alternating Least Squares</title>

     <link rel="shortcut icon" href="http://flink.apache.org/docs/0.9/page/favicon.ico" type="image/x-icon">
     <link rel="icon" href="http://flink.apache.org/docs/0.9/page/favicon.ico" type="image/x-icon">

     <!-- Bootstrap -->
     <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.4/css/bootstrap.min.css">
     <link rel="stylesheet" href="http://flink.apache.org/docs/0.9/page/css/flink.css">
     <link rel="stylesheet" href="http://flink.apache.org/docs/0.9/page/css/syntax.css">
     <link rel="stylesheet" href="http://flink.apache.org/docs/0.9/page/css/codetabs.css">

     <script type="text/x-mathjax-config">
         MathJax.Hub.Config({
         tex2jax: {
           inlineMath: [['$','$'], ['\\(','\\)']] },
         TeX: {
           equationNumbers: { autoNumber: "AMS" } }
         });
     </script>
     <script type="text/javascript"
             src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
     </script>

     <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
     <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
     <!--[if lt IE 9]>
       <script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
       <script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
     <![endif]-->
   </head>
   <body>


     <!-- Top navbar. -->
     <nav class="navbar navbar-default navbar-fixed-top">
       <div class="container">
         <!-- The logo. -->
         <div class="navbar-header">
           <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1">
             <span class="icon-bar"></span>
             <span class="icon-bar"></span>
             <span class="icon-bar"></span>
           </button>
           <div class="navbar-logo">
             <a href="http://flink.apache.org"><img alt="Apache Flink" src="http://flink.apache.org/docs/0.9/page/img/navbar-brand-logo.jpg"></a>
           </div>
         </div><!-- /.navbar-header -->

         <!-- The navigation links. -->
         <div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
           <ul class="nav navbar-nav">
             <li><a href="http://flink.apache.org/docs/0.9/index.html">Overview<span class="hidden-sm hidden-xs"> 0.9.0</span></a></li>

             <!-- Setup -->
             <li class="dropdown">
               <a href="http://flink.apache.org/docs/0.9/setup" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Setup <span class="caret"></span></a>
               <ul class="dropdown-menu" role="menu">
                 <li><a href="http://flink.apache.org/docs/0.9/setup/building.html">Get Flink 0.9-SNAPSHOT</a></li>

                 <li class="divider"></li>
                 <li role="presentation" class="dropdown-header"><strong>Deployment</strong></li>
                 <li><a href="http://flink.apache.org/docs/0.9/setup/local_setup.html" class="active">Local</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/setup/cluster_setup.html">Cluster (Standalone)</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/setup/yarn_setup.html">YARN</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/setup/gce_setup.html">GCloud</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/setup/flink_on_tez.html">Flink on Tez <span class="badge">Beta</span></a></li>

                 <li class="divider"></li>
                 <li><a href="http://flink.apache.org/docs/0.9/setup/config.html">Configuration</a></li>
               </ul>
             </li>

             <!-- Programming Guides -->
             <li class="dropdown">
               <a href="http://flink.apache.org/docs/0.9/apis" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Programming Guides <span class="caret"></span></a>
               <ul class="dropdown-menu" role="menu">
                 <li><a href="http://flink.apache.org/docs/0.9/apis/programming_guide.html"><strong>Batch: DataSet API</strong></a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/streaming_guide.html"><strong>Streaming: DataStream API</strong> <span class="badge">Beta</span></a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/python.html">Python API <span class="badge">Beta</span></a></li>

                 <li class="divider"></li>
                 <li><a href="scala_shell.html">Interactive Scala Shell</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/dataset_transformations.html">Dataset Transformations</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/best_practices.html">Best Practices</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/example_connectors.html">Connectors</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/examples.html">Examples</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/local_execution.html">Local Execution</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/cluster_execution.html">Cluster Execution</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/cli.html">Command Line Interface</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/web_client.html">Web Client</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/iterations.html">Iterations</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/java8.html">Java 8</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/apis/hadoop_compatibility.html">Hadoop Compatability <span class="badge">Beta</span></a></li>
               </ul>
             </li>

             <!-- Libraries -->
             <li class="dropdown">
               <a href="http://flink.apache.org/docs/0.9/libs" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Libraries <span class="caret"></span></a>
                 <ul class="dropdown-menu" role="menu">
                   <li><a href="http://flink.apache.org/docs/0.9/libs/spargel_guide.html">Graphs: Spargel</a></li>
                   <li><a href="http://flink.apache.org/docs/0.9/libs/gelly_guide.html">Graphs: Gelly <span class="badge">Beta</span></a></li>
                   <li><a href="http://flink.apache.org/docs/0.9/libs/ml/">Machine Learning <span class="badge">Beta</span></a></li>
                   <li><a href="http://flink.apache.org/docs/0.9/libs/table.html">Relational: Table <span class="badge">Beta</span></a></li>
               </ul>
             </li>

             <!-- Internals -->
             <li class="dropdown">
               <a href="http://flink.apache.org/docs/0.9/internals" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Internals <span class="caret"></span></a>
               <ul class="dropdown-menu" role="menu">
                 <li role="presentation" class="dropdown-header"><strong>Contribute</strong></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/how_to_contribute.html">How to Contribute</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/coding_guidelines.html">Coding Guidelines</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/ide_setup.html">IDE Setup</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/logging.html">Logging</a></li>
                 <li class="divider"></li>
                 <li role="presentation" class="dropdown-header"><strong>Internals</strong></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/general_arch.html">Architecture &amp; Process Model</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/types_serialization.html">Type Extraction &amp; Serialization</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/job_scheduling.html">Jobs &amp; Scheduling</a></li>
                 <li><a href="http://flink.apache.org/docs/0.9/internals/add_operator.html">How-To: Add an Operator</a></li>
               </ul>
             </li>
           </ul>
           <form class="navbar-form navbar-right hidden-sm hidden-md" role="search" action="http://flink.apache.org/docs/0.9/search-results.html">
             <div class="form-group">
               <input type="text" class="form-control" name="q" placeholder="Search all pages">
             </div>
             <button type="submit" class="btn btn-default">Search</button>
           </form>
         </div><!-- /.navbar-collapse -->
       </div><!-- /.container -->
     </nav>


 <!--Some of the Latex math notation has been adapted from Apache Spark MLlib's documentation-->
 $$
 \newcommand{\R}{\mathbb{R}}
 \newcommand{\E}{\mathbb{E}}
 \newcommand{\x}{\mathbf{x}}
 \newcommand{\y}{\mathbf{y}}
 \newcommand{\wv}{\mathbf{w}}
 \newcommand{\av}{\mathbf{\alpha}}
 \newcommand{\bv}{\mathbf{b}}
 \newcommand{\N}{\mathbb{N}}
 \newcommand{\id}{\mathbf{I}}
 \newcommand{\ind}{\mathbf{1}}
 \newcommand{\0}{\mathbf{0}}
 \newcommand{\unit}{\mathbf{e}}
 \newcommand{\one}{\mathbf{1}}
 \newcommand{\zero}{\mathbf{0}}
 \newcommand\rfrac[2]{^{#1}\!/_{#2}}
 \newcommand{\norm}[1]{\left\lVert#1\right\rVert}
 $$


     <!-- Main content. -->
     <div class="container">


 <div class="row">
   <div class="col-sm-10 col-sm-offset-1">
     <h1><a href="../ml">FlinkML</a> - Alternating Least Squares</h1>


 <ul id="markdown-toc">
   <li><a href="#description" id="markdown-toc-description">Description</a></li>
   <li><a href="#operations" id="markdown-toc-operations">Operations</a>    <ul>
       <li><a href="#fit" id="markdown-toc-fit">Fit</a></li>
       <li><a href="#predict" id="markdown-toc-predict">Predict</a></li>
     </ul>
   </li>
   <li><a href="#parameters" id="markdown-toc-parameters">Parameters</a></li>
   <li><a href="#examples" id="markdown-toc-examples">Examples</a></li>
 </ul>

 <h2 id="description">Description</h2>

 <p>The alternating least squares (ALS) algorithm factorizes a given matrix $R$ into two factors $U$ and $V$ such that $R \approx U^TV$.
 The unknown row dimension is given as a parameter to the algorithm and is called latent factors.
 Since matrix factorization can be used in the context of recommendation, the matrices $U$ and $V$ can be called user and item matrix, respectively.
 The $i$th column of the user matrix is denoted by $u_i$ and the $i$th column of the item matrix is $v_i$.
 The matrix $R$ can be called the ratings matrix with <script type="math/tex">(R)_{i,j} = r_{i,j}</script>.</p>

 <p>In order to find the user and item matrix, the following problem is solved:</p>

 <script type="math/tex; mode=display">\arg\min_{U,V} \sum_{\{i,j\mid r_{i,j} \not= 0\}} \left(r_{i,j} - u_{i}^Tv_{j}\right)^2 +
 \lambda \left(\sum_{i} n_{u_i} \left\lVert u_i \right\rVert^2 + \sum_{j} n_{v_j} \left\lVert v_j \right\rVert^2 \right)</script>

 <p>with $\lambda$ being the regularization factor, <script type="math/tex">n_{u_i}</script> being the number of items the user $i$ has rated and <script type="math/tex">n_{v_j}</script> being the number of times the item $j$ has been rated.
 This regularization scheme to avoid overfitting is called weighted-$\lambda$-regularization.
 Details can be found in the work of <a href="http://dx.doi.org/10.1007/978-3-540-68880-8_32">Zhou et al.</a>.</p>

 <p>By fixing one of the matrices $U$ or $V$, we obtain a quadratic form which can be solved directly.
 The solution of the modified problem is guaranteed to monotonically decrease the overall cost function.
 By applying this step alternately to the matrices $U$ and $V$, we can iteratively improve the matrix factorization.</p>

 <p>The matrix $R$ is given in its sparse representation as a tuple of $(i, j, r)$ where $i$ denotes the row index, $j$ the column index and $r$ is the matrix value at position $(i,j)$.</p>

 <h2 id="operations">Operations</h2>

 <p><code>ALS</code> is a <code>Predictor</code>.
 As such, it supports the <code>fit</code> and <code>predict</code> operation.</p>

 <h3 id="fit">Fit</h3>

 <p>ALS is trained on the sparse representation of the rating matrix:</p>

 <ul>
   <li><code>fit: DataSet[(Int, Int, Double)] =&gt; Unit</code></li>
 </ul>

 <h3 id="predict">Predict</h3>

 <p>ALS predicts for each tuple of row and column index the rating:</p>

 <ul>
   <li><code>predict: DataSet[(Int, Int)] =&gt; DataSet[(Int, Int, Double)]</code></li>
 </ul>

 <h2 id="parameters">Parameters</h2>

 <p>The alternating least squares implementation can be controlled by the following parameters:</p>

 <table class="table table-bordered">
     <thead>
       <tr>
         <th class="text-left" style="width: 20%">Parameters</th>
         <th class="text-center">Description</th>
       </tr>
     </thead>

     <tbody>
       <tr>
         <td><strong>NumFactors</strong></td>
         <td>
           <p>
             The number of latent factors to use for the underlying model.
             It is equivalent to the dimension of the calculated user and item vectors.
             (Default value: <strong>10</strong>)
           </p>
         </td>
       </tr>
       <tr>
         <td><strong>Lambda</strong></td>
         <td>
           <p>
             Regularization factor. Tune this value in order to avoid overfitting or poor performance due to strong generalization.
             (Default value: <strong>1</strong>)
           </p>
         </td>
       </tr>
       <tr>
         <td><strong>Iterations</strong></td>
         <td>
           <p>
             The maximum number of iterations.
             (Default value: <strong>10</strong>)
           </p>
         </td>
       </tr>
       <tr>
         <td><strong>Blocks</strong></td>
         <td>
           <p>
             The number of blocks into which the user and item matrix are grouped.
             The fewer blocks one uses, the less data is sent redundantly.
             However, bigger blocks entail bigger update messages which have to be stored on the heap.
             If the algorithm fails because of an OutOfMemoryException, then try to increase the number of blocks.
             (Default value: <strong>None</strong>)
           </p>
         </td>
       </tr>
       <tr>
         <td><strong>Seed</strong></td>
         <td>
           <p>
             Random seed used to generate the initial item matrix for the algorithm.
             (Default value: <strong>0</strong>)
           </p>
         </td>
       </tr>
       <tr>
         <td><strong>TemporaryPath</strong></td>
         <td>
           <p>
             Path to a temporary directory into which intermediate results are stored.
             If this value is set, then the algorithm is split into two preprocessing steps, the ALS iteration and a post-processing step which calculates a last ALS half-step.
             The preprocessing steps calculate the <code>OutBlockInformation</code> and <code>InBlockInformation</code> for the given rating matrix.
             The results of the individual steps are stored in the specified directory.
             By splitting the algorithm into multiple smaller steps, Flink does not have to split the available memory amongst too many operators.
             This allows the system to process bigger individual messages and improves the overall performance.
             (Default value: <strong>None</strong>)
           </p>
         </td>
       </tr>
     </tbody>
   </table>

 <h2 id="examples">Examples</h2>

 <div class="highlight"><pre><code class="language-scala" data-lang="scala"><span class="c1">// Read input data set from a csv file</span>
 <span class="k">val</span> <span class="n">inputDS</span><span class="k">:</span> <span class="kt">DataSet</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span>, <span class="kt">Double</span><span class="o">)]</span> <span class="k">=</span> <span class="n">env</span><span class="o">.</span><span class="n">readCsvFile</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span>, <span class="kt">Double</span><span class="o">)](</span>
   <span class="n">pathToTrainingFile</span><span class="o">)</span>

 <span class="c1">// Setup the ALS learner</span>
 <span class="k">val</span> <span class="n">als</span> <span class="k">=</span> <span class="nc">ALS</span><span class="o">()</span>
 <span class="o">.</span><span class="n">setIterations</span><span class="o">(</span><span class="mi">10</span><span class="o">)</span>
 <span class="o">.</span><span class="n">setNumFactors</span><span class="o">(</span><span class="mi">10</span><span class="o">)</span>
 <span class="o">.</span><span class="n">setBlocks</span><span class="o">(</span><span class="mi">100</span><span class="o">)</span>
 <span class="o">.</span><span class="n">setTemporaryPath</span><span class="o">(</span><span class="s">&quot;hdfs://tempPath&quot;</span><span class="o">)</span>

 <span class="c1">// Set the other parameters via a parameter map</span>
 <span class="k">val</span> <span class="n">parameters</span> <span class="k">=</span> <span class="nc">ParameterMap</span><span class="o">()</span>
 <span class="o">.</span><span class="n">add</span><span class="o">(</span><span class="nc">ALS</span><span class="o">.</span><span class="nc">Lambda</span><span class="o">,</span> <span class="mf">0.9</span><span class="o">)</span>
 <span class="o">.</span><span class="n">add</span><span class="o">(</span><span class="nc">ALS</span><span class="o">.</span><span class="nc">Seed</span><span class="o">,</span> <span class="mi">42L</span><span class="o">)</span>

 <span class="c1">// Calculate the factorization</span>
 <span class="n">als</span><span class="o">.</span><span class="n">fit</span><span class="o">(</span><span class="n">inputDS</span><span class="o">,</span> <span class="n">parameters</span><span class="o">)</span>

 <span class="c1">// Read the testing data set from a csv file</span>
 <span class="k">val</span> <span class="n">testingDS</span><span class="k">:</span> <span class="kt">DataSet</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span><span class="o">)]</span> <span class="k">=</span> <span class="n">env</span><span class="o">.</span><span class="n">readCsvFile</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span><span class="o">)](</span><span class="n">pathToData</span><span class="o">)</span>

 <span class="c1">// Calculate the ratings according to the matrix factorization</span>
 <span class="k">val</span> <span class="n">predictedRatings</span> <span class="k">=</span> <span class="n">als</span><span class="o">.</span><span class="n">predict</span><span class="o">(</span><span class="n">testingDS</span><span class="o">)</span></code></pre></div>


   </div>

   <div class="col-sm-10 col-sm-offset-1">
     <!-- Disqus thread and some vertical offset -->
     <div style="margin-top: 75px; margin-bottom: 50px" id="disqus_thread"></div>
   </div>
 </div>

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

     <!-- jQuery (necessary for Bootstrap's JavaScript plugins) -->
     <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.2/jquery.min.js"></script>
     <!-- Include all compiled plugins (below), or include individual files as needed -->
     <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.4/js/bootstrap.min.js"></script>
     <script src="http://flink.apache.org/docs/0.9/page/js/codetabs.js"></script>

     <!-- 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-52545728-1', 'auto');
       ga('send', 'pageview');
     </script>

     <!-- Disqus -->
     <script type="text/javascript">
     var disqus_shortname = 'stratosphere-eu';
     (function() {
         var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
         dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
         (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
     })();
 </script>
   </body>
 </html>
	<!--
	Licensed to the Apache Software Foundation (ASF) under one
	or more contributor license agreements. See the NOTICE file
	distributed with this work for additional information
	regarding copyright ownership. The ASF licenses this file
	to you under the Apache License, Version 2.0 (the
	"License"); you may not use this file except in compliance
	with the License. You may obtain a copy of the License at

	http://www.apache.org/licenses/LICENSE-2.0

	Unless required by applicable law or agreed to in writing,
	software distributed under the License is distributed on an
	"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	KIND, either express or implied. See the License for the
	specific language governing permissions and limitations
	under the License.
	-->
	<!DOCTYPE html>

	<html lang="en">
	<head>
	<meta charset="utf-8">
	<meta http-equiv="X-UA-Compatible" content="IE=edge">
	<meta name="viewport" content="width=device-width, initial-scale=1">
	<!-- The above 3 meta tags must come first in the head; any other head content must come after these tags -->

	<title>Apache Flink 0.9.0 Documentation: FlinkML - Alternating Least Squares</title>

	<link rel="shortcut icon" href="http://flink.apache.org/docs/0.9/page/favicon.ico" type="image/x-icon">
	<link rel="icon" href="http://flink.apache.org/docs/0.9/page/favicon.ico" type="image/x-icon">

	<!-- Bootstrap -->
	<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.4/css/bootstrap.min.css">
	<link rel="stylesheet" href="http://flink.apache.org/docs/0.9/page/css/flink.css">
	<link rel="stylesheet" href="http://flink.apache.org/docs/0.9/page/css/syntax.css">
	<link rel="stylesheet" href="http://flink.apache.org/docs/0.9/page/css/codetabs.css">

	<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
	tex2jax: {
	inlineMath: [['$','$'], ['\\(','\\)']] },
	TeX: {
	equationNumbers: { autoNumber: "AMS" } }
	});
	</script>
	<script type="text/javascript"
	src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
	</script>

	<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
	<!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
	<!--[if lt IE 9]>
	<script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
	<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
	<![endif]-->
	</head>
	<body>






	<!-- Top navbar. -->
	<nav class="navbar navbar-default navbar-fixed-top">
	<div class="container">
	<!-- The logo. -->
	<div class="navbar-header">
	<button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-example-navbar-collapse-1">
	<span class="icon-bar"></span>
	<span class="icon-bar"></span>
	<span class="icon-bar"></span>
	</button>
	<div class="navbar-logo">
	<a href="http://flink.apache.org"><img alt="Apache Flink" src="http://flink.apache.org/docs/0.9/page/img/navbar-brand-logo.jpg"></a>
	</div>
	</div><!-- /.navbar-header -->

	<!-- The navigation links. -->
	<div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
	<ul class="nav navbar-nav">
	<li><a href="http://flink.apache.org/docs/0.9/index.html">Overview<span class="hidden-sm hidden-xs"> 0.9.0</span></a></li>

	<!-- Setup -->
	<li class="dropdown">
	<a href="http://flink.apache.org/docs/0.9/setup" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Setup <span class="caret"></span></a>
	<ul class="dropdown-menu" role="menu">
	<li><a href="http://flink.apache.org/docs/0.9/setup/building.html">Get Flink 0.9-SNAPSHOT</a></li>

	<li class="divider"></li>
	<li role="presentation" class="dropdown-header"><strong>Deployment</strong></li>
	<li><a href="http://flink.apache.org/docs/0.9/setup/local_setup.html" class="active">Local</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/setup/cluster_setup.html">Cluster (Standalone)</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/setup/yarn_setup.html">YARN</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/setup/gce_setup.html">GCloud</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/setup/flink_on_tez.html">Flink on Tez <span class="badge">Beta</span></a></li>

	<li class="divider"></li>
	<li><a href="http://flink.apache.org/docs/0.9/setup/config.html">Configuration</a></li>
	</ul>
	</li>

	<!-- Programming Guides -->
	<li class="dropdown">
	<a href="http://flink.apache.org/docs/0.9/apis" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Programming Guides <span class="caret"></span></a>
	<ul class="dropdown-menu" role="menu">
	<li><a href="http://flink.apache.org/docs/0.9/apis/programming_guide.html"><strong>Batch: DataSet API</strong></a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/streaming_guide.html"><strong>Streaming: DataStream API</strong> <span class="badge">Beta</span></a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/python.html">Python API <span class="badge">Beta</span></a></li>

	<li class="divider"></li>
	<li><a href="scala_shell.html">Interactive Scala Shell</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/dataset_transformations.html">Dataset Transformations</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/best_practices.html">Best Practices</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/example_connectors.html">Connectors</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/examples.html">Examples</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/local_execution.html">Local Execution</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/cluster_execution.html">Cluster Execution</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/cli.html">Command Line Interface</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/web_client.html">Web Client</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/iterations.html">Iterations</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/java8.html">Java 8</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/apis/hadoop_compatibility.html">Hadoop Compatability <span class="badge">Beta</span></a></li>
	</ul>
	</li>

	<!-- Libraries -->
	<li class="dropdown">
	<a href="http://flink.apache.org/docs/0.9/libs" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Libraries <span class="caret"></span></a>
	<ul class="dropdown-menu" role="menu">
	<li><a href="http://flink.apache.org/docs/0.9/libs/spargel_guide.html">Graphs: Spargel</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/libs/gelly_guide.html">Graphs: Gelly <span class="badge">Beta</span></a></li>
	<li><a href="http://flink.apache.org/docs/0.9/libs/ml/">Machine Learning <span class="badge">Beta</span></a></li>
	<li><a href="http://flink.apache.org/docs/0.9/libs/table.html">Relational: Table <span class="badge">Beta</span></a></li>
	</ul>
	</li>

	<!-- Internals -->
	<li class="dropdown">
	<a href="http://flink.apache.org/docs/0.9/internals" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-expanded="false">Internals <span class="caret"></span></a>
	<ul class="dropdown-menu" role="menu">
	<li role="presentation" class="dropdown-header"><strong>Contribute</strong></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/how_to_contribute.html">How to Contribute</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/coding_guidelines.html">Coding Guidelines</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/ide_setup.html">IDE Setup</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/logging.html">Logging</a></li>
	<li class="divider"></li>
	<li role="presentation" class="dropdown-header"><strong>Internals</strong></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/general_arch.html">Architecture & Process Model</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/types_serialization.html">Type Extraction & Serialization</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/job_scheduling.html">Jobs & Scheduling</a></li>
	<li><a href="http://flink.apache.org/docs/0.9/internals/add_operator.html">How-To: Add an Operator</a></li>
	</ul>
	</li>
	</ul>
	<form class="navbar-form navbar-right hidden-sm hidden-md" role="search" action="http://flink.apache.org/docs/0.9/search-results.html">
	<div class="form-group">
	<input type="text" class="form-control" name="q" placeholder="Search all pages">
	</div>
	<button type="submit" class="btn btn-default">Search</button>
	</form>
	</div><!-- /.navbar-collapse -->
	</div><!-- /.container -->
	</nav>





	<!--Some of the Latex math notation has been adapted from Apache Spark MLlib's documentation-->
	$$
	\newcommand{\R}{\mathbb{R}}
	\newcommand{\E}{\mathbb{E}}
	\newcommand{\x}{\mathbf{x}}
	\newcommand{\y}{\mathbf{y}}
	\newcommand{\wv}{\mathbf{w}}
	\newcommand{\av}{\mathbf{\alpha}}
	\newcommand{\bv}{\mathbf{b}}
	\newcommand{\N}{\mathbb{N}}
	\newcommand{\id}{\mathbf{I}}
	\newcommand{\ind}{\mathbf{1}}
	\newcommand{\0}{\mathbf{0}}
	\newcommand{\unit}{\mathbf{e}}
	\newcommand{\one}{\mathbf{1}}
	\newcommand{\zero}{\mathbf{0}}
	\newcommand\rfrac[2]{^{#1}\!/_{#2}}
	\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
	$$


	<!-- Main content. -->
	<div class="container">


	<div class="row">
	<div class="col-sm-10 col-sm-offset-1">
	<h1><a href="../ml">FlinkML</a> - Alternating Least Squares</h1>



	<ul id="markdown-toc">
	<li><a href="#description" id="markdown-toc-description">Description</a></li>
	<li><a href="#operations" id="markdown-toc-operations">Operations</a> <ul>
	<li><a href="#fit" id="markdown-toc-fit">Fit</a></li>
	<li><a href="#predict" id="markdown-toc-predict">Predict</a></li>
	</ul>
	</li>
	<li><a href="#parameters" id="markdown-toc-parameters">Parameters</a></li>
	<li><a href="#examples" id="markdown-toc-examples">Examples</a></li>
	</ul>

	<h2 id="description">Description</h2>

	<p>The alternating least squares (ALS) algorithm factorizes a given matrix $R$ into two factors $U$ and $V$ such that $R \approx U^TV$.
	The unknown row dimension is given as a parameter to the algorithm and is called latent factors.
	Since matrix factorization can be used in the context of recommendation, the matrices $U$ and $V$ can be called user and item matrix, respectively.
	The $i$th column of the user matrix is denoted by $u_i$ and the $i$th column of the item matrix is $v_i$.
	The matrix $R$ can be called the ratings matrix with <script type="math/tex">(R)_{i,j} = r_{i,j}</script>.</p>

	<p>In order to find the user and item matrix, the following problem is solved:</p>

	<script type="math/tex; mode=display">\arg\min_{U,V} \sum_{\{i,j\mid r_{i,j} \not= 0\}} \left(r_{i,j} - u_{i}^Tv_{j}\right)^2 +
	\lambda \left(\sum_{i} n_{u_i} \left\lVert u_i \right\rVert^2 + \sum_{j} n_{v_j} \left\lVert v_j \right\rVert^2 \right)</script>

	<p>with $\lambda$ being the regularization factor, <script type="math/tex">n_{u_i}</script> being the number of items the user $i$ has rated and <script type="math/tex">n_{v_j}</script> being the number of times the item $j$ has been rated.
	This regularization scheme to avoid overfitting is called weighted-$\lambda$-regularization.
	Details can be found in the work of <a href="http://dx.doi.org/10.1007/978-3-540-68880-8_32">Zhou et al.</a>.</p>

	<p>By fixing one of the matrices $U$ or $V$, we obtain a quadratic form which can be solved directly.
	The solution of the modified problem is guaranteed to monotonically decrease the overall cost function.
	By applying this step alternately to the matrices $U$ and $V$, we can iteratively improve the matrix factorization.</p>

	<p>The matrix $R$ is given in its sparse representation as a tuple of $(i, j, r)$ where $i$ denotes the row index, $j$ the column index and $r$ is the matrix value at position $(i,j)$.</p>

	<h2 id="operations">Operations</h2>

	<p><code>ALS</code> is a <code>Predictor</code>.
	As such, it supports the <code>fit</code> and <code>predict</code> operation.</p>

	<h3 id="fit">Fit</h3>

	<p>ALS is trained on the sparse representation of the rating matrix:</p>

	<ul>
	<li><code>fit: DataSet[(Int, Int, Double)] => Unit</code></li>
	</ul>

	<h3 id="predict">Predict</h3>

	<p>ALS predicts for each tuple of row and column index the rating:</p>

	<ul>
	<li><code>predict: DataSet[(Int, Int)] => DataSet[(Int, Int, Double)]</code></li>
	</ul>

	<h2 id="parameters">Parameters</h2>

	<p>The alternating least squares implementation can be controlled by the following parameters:</p>

	<table class="table table-bordered">
	<thead>
	<tr>
	<th class="text-left" style="width: 20%">Parameters</th>
	<th class="text-center">Description</th>
	</tr>
	</thead>

	<tbody>
	<tr>
	<td><strong>NumFactors</strong></td>
	<td>
	<p>
	The number of latent factors to use for the underlying model.
	It is equivalent to the dimension of the calculated user and item vectors.
	(Default value: <strong>10</strong>)
	</p>
	</td>
	</tr>
	<tr>
	<td><strong>Lambda</strong></td>
	<td>
	<p>
	Regularization factor. Tune this value in order to avoid overfitting or poor performance due to strong generalization.
	(Default value: <strong>1</strong>)
	</p>
	</td>
	</tr>
	<tr>
	<td><strong>Iterations</strong></td>
	<td>
	<p>
	The maximum number of iterations.
	(Default value: <strong>10</strong>)
	</p>
	</td>
	</tr>
	<tr>
	<td><strong>Blocks</strong></td>
	<td>
	<p>
	The number of blocks into which the user and item matrix are grouped.
	The fewer blocks one uses, the less data is sent redundantly.
	However, bigger blocks entail bigger update messages which have to be stored on the heap.
	If the algorithm fails because of an OutOfMemoryException, then try to increase the number of blocks.
	(Default value: <strong>None</strong>)
	</p>
	</td>
	</tr>
	<tr>
	<td><strong>Seed</strong></td>
	<td>
	<p>
	Random seed used to generate the initial item matrix for the algorithm.
	(Default value: <strong>0</strong>)
	</p>
	</td>
	</tr>
	<tr>
	<td><strong>TemporaryPath</strong></td>
	<td>
	<p>
	Path to a temporary directory into which intermediate results are stored.
	If this value is set, then the algorithm is split into two preprocessing steps, the ALS iteration and a post-processing step which calculates a last ALS half-step.
	The preprocessing steps calculate the <code>OutBlockInformation</code> and <code>InBlockInformation</code> for the given rating matrix.
	The results of the individual steps are stored in the specified directory.
	By splitting the algorithm into multiple smaller steps, Flink does not have to split the available memory amongst too many operators.
	This allows the system to process bigger individual messages and improves the overall performance.
	(Default value: <strong>None</strong>)
	</p>
	</td>
	</tr>
	</tbody>
	</table>

	<h2 id="examples">Examples</h2>

	<div class="highlight"><pre><code class="language-scala" data-lang="scala"><span class="c1">// Read input data set from a csv file</span>
	<span class="k">val</span> <span class="n">inputDS</span><span class="k">:</span> <span class="kt">DataSet</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span>, <span class="kt">Double</span><span class="o">)]</span> <span class="k">=</span> <span class="n">env</span><span class="o">.</span><span class="n">readCsvFile</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span>, <span class="kt">Double</span><span class="o">)](</span>
	<span class="n">pathToTrainingFile</span><span class="o">)</span>

	<span class="c1">// Setup the ALS learner</span>
	<span class="k">val</span> <span class="n">als</span> <span class="k">=</span> <span class="nc">ALS</span><span class="o">()</span>
	<span class="o">.</span><span class="n">setIterations</span><span class="o">(</span><span class="mi">10</span><span class="o">)</span>
	<span class="o">.</span><span class="n">setNumFactors</span><span class="o">(</span><span class="mi">10</span><span class="o">)</span>
	<span class="o">.</span><span class="n">setBlocks</span><span class="o">(</span><span class="mi">100</span><span class="o">)</span>
	<span class="o">.</span><span class="n">setTemporaryPath</span><span class="o">(</span><span class="s">"hdfs://tempPath"</span><span class="o">)</span>

	<span class="c1">// Set the other parameters via a parameter map</span>
	<span class="k">val</span> <span class="n">parameters</span> <span class="k">=</span> <span class="nc">ParameterMap</span><span class="o">()</span>
	<span class="o">.</span><span class="n">add</span><span class="o">(</span><span class="nc">ALS</span><span class="o">.</span><span class="nc">Lambda</span><span class="o">,</span> <span class="mf">0.9</span><span class="o">)</span>
	<span class="o">.</span><span class="n">add</span><span class="o">(</span><span class="nc">ALS</span><span class="o">.</span><span class="nc">Seed</span><span class="o">,</span> <span class="mi">42L</span><span class="o">)</span>

	<span class="c1">// Calculate the factorization</span>
	<span class="n">als</span><span class="o">.</span><span class="n">fit</span><span class="o">(</span><span class="n">inputDS</span><span class="o">,</span> <span class="n">parameters</span><span class="o">)</span>

	<span class="c1">// Read the testing data set from a csv file</span>
	<span class="k">val</span> <span class="n">testingDS</span><span class="k">:</span> <span class="kt">DataSet</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span><span class="o">)]</span> <span class="k">=</span> <span class="n">env</span><span class="o">.</span><span class="n">readCsvFile</span><span class="o">[(</span><span class="kt">Int</span>, <span class="kt">Int</span><span class="o">)](</span><span class="n">pathToData</span><span class="o">)</span>

	<span class="c1">// Calculate the ratings according to the matrix factorization</span>
	<span class="k">val</span> <span class="n">predictedRatings</span> <span class="k">=</span> <span class="n">als</span><span class="o">.</span><span class="n">predict</span><span class="o">(</span><span class="n">testingDS</span><span class="o">)</span></code></pre></div>


	</div>

	<div class="col-sm-10 col-sm-offset-1">
	<!-- Disqus thread and some vertical offset -->
	<div style="margin-top: 75px; margin-bottom: 50px" id="disqus_thread"></div>
	</div>
	</div>

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

	<!-- jQuery (necessary for Bootstrap's JavaScript plugins) -->
	<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.2/jquery.min.js"></script>
	<!-- Include all compiled plugins (below), or include individual files as needed -->
	<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.4/js/bootstrap.min.js"></script>
	<script src="http://flink.apache.org/docs/0.9/page/js/codetabs.js"></script>

	<!-- 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-52545728-1', 'auto');
	ga('send', 'pageview');
	</script>

	<!-- Disqus -->
	<script type="text/javascript">
	var disqus_shortname = 'stratosphere-eu';
	(function() {
	var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
	dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
	(document.getElementsByTagName('head')[0] \|\| document.getElementsByTagName('body')[0]).appendChild(dsq);
	})();
	</script>
	</body>
	</html>