You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by pw...@apache.org on 2014/04/22 20:20:56 UTC
[3/3] git commit: [SPARK-1506][MLLIB] Documentation improvements for
MLlib 1.0
[SPARK-1506][MLLIB] Documentation improvements for MLlib 1.0
Preview: http://54.82.240.23:4000/mllib-guide.html
Table of contents:
* Basics
* Data types
* Summary statistics
* Classification and regression
* linear support vector machine (SVM)
* logistic regression
* linear linear squares, Lasso, and ridge regression
* decision tree
* naive Bayes
* Collaborative Filtering
* alternating least squares (ALS)
* Clustering
* k-means
* Dimensionality reduction
* singular value decomposition (SVD)
* principal component analysis (PCA)
* Optimization
* stochastic gradient descent
* limited-memory BFGS (L-BFGS)
Author: Xiangrui Meng <me...@databricks.com>
Closes #422 from mengxr/mllib-doc and squashes the following commits:
944e3a9 [Xiangrui Meng] merge master
f9fda28 [Xiangrui Meng] minor
9474065 [Xiangrui Meng] add alpha to ALS examples
928e630 [Xiangrui Meng] initialization_mode -> initializationMode
5bbff49 [Xiangrui Meng] add imports to labeled point examples
c17440d [Xiangrui Meng] fix python nb example
28f40dc [Xiangrui Meng] remove localhost:4000
369a4d3 [Xiangrui Meng] Merge branch 'master' into mllib-doc
7dc95cc [Xiangrui Meng] update linear methods
053ad8a [Xiangrui Meng] add links to go back to the main page
abbbf7e [Xiangrui Meng] update ALS argument names
648283e [Xiangrui Meng] level down statistics
14e2287 [Xiangrui Meng] add sample libsvm data and use it in guide
8cd2441 [Xiangrui Meng] minor updates
186ab07 [Xiangrui Meng] update section names
6568d65 [Xiangrui Meng] update toc, level up lr and svm
162ee12 [Xiangrui Meng] rename section names
5c1e1b1 [Xiangrui Meng] minor
8aeaba1 [Xiangrui Meng] wrap long lines
6ce6a6f [Xiangrui Meng] add summary statistics to toc
5760045 [Xiangrui Meng] claim beta
cc604bf [Xiangrui Meng] remove classification and regression
92747b3 [Xiangrui Meng] make section titles consistent
e605dd6 [Xiangrui Meng] add LIBSVM loader
f639674 [Xiangrui Meng] add python section to migration guide
c82ffb4 [Xiangrui Meng] clean optimization
31660eb [Xiangrui Meng] update linear algebra and stat
0a40837 [Xiangrui Meng] first pass over linear methods
1fc8271 [Xiangrui Meng] update toc
906ed0a [Xiangrui Meng] add a python example to naive bayes
5f0a700 [Xiangrui Meng] update collaborative filtering
656d416 [Xiangrui Meng] update mllib-clustering
86e143a [Xiangrui Meng] remove data types section from main page
8d1a128 [Xiangrui Meng] move part of linear algebra to data types and add Java/Python examples
d1b5cbf [Xiangrui Meng] merge master
72e4804 [Xiangrui Meng] one pass over tree guide
64f8995 [Xiangrui Meng] move decision tree guide to a separate file
9fca001 [Xiangrui Meng] add first version of linear algebra guide
53c9552 [Xiangrui Meng] update dependencies
f316ec2 [Xiangrui Meng] add migration guide
f399f6c [Xiangrui Meng] move linear-algebra to dimensionality-reduction
182460f [Xiangrui Meng] add guide for naive Bayes
137fd1d [Xiangrui Meng] re-organize toc
a61e434 [Xiangrui Meng] update mllib's toc
Project: http://git-wip-us.apache.org/repos/asf/spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/spark/commit/26d35f3f
Tree: http://git-wip-us.apache.org/repos/asf/spark/tree/26d35f3f
Diff: http://git-wip-us.apache.org/repos/asf/spark/diff/26d35f3f
Branch: refs/heads/master
Commit: 26d35f3fd942761b0adecd1a720e1fa834db4de9
Parents: bf9d49b
Author: Xiangrui Meng <me...@databricks.com>
Authored: Tue Apr 22 11:20:47 2014 -0700
Committer: Patrick Wendell <pw...@gmail.com>
Committed: Tue Apr 22 11:20:47 2014 -0700
----------------------------------------------------------------------
docs/mllib-basics.md | 476 ++++++++++++++++++++++
docs/mllib-classification-regression.md | 568 ---------------------------
docs/mllib-clustering.md | 44 +--
docs/mllib-collaborative-filtering.md | 78 ++--
docs/mllib-decision-tree.md | 185 +++++++++
docs/mllib-dimensionality-reduction.md | 86 ++++
docs/mllib-guide.md | 172 +++++---
docs/mllib-linear-algebra.md | 74 ----
docs/mllib-linear-methods.md | 389 ++++++++++++++++++
docs/mllib-naive-bayes.md | 115 ++++++
docs/mllib-optimization.md | 25 +-
mllib/data/sample_libsvm_data.txt | 100 +++++
12 files changed, 1543 insertions(+), 769 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-basics.md
----------------------------------------------------------------------
diff --git a/docs/mllib-basics.md b/docs/mllib-basics.md
new file mode 100644
index 0000000..710ce17
--- /dev/null
+++ b/docs/mllib-basics.md
@@ -0,0 +1,476 @@
+---
+layout: global
+title: <a href="mllib-guide.html">MLlib</a> - Basics
+---
+
+* Table of contents
+{:toc}
+
+MLlib supports local vectors and matrices stored on a single machine,
+as well as distributed matrices backed by one or more RDDs.
+In the current implementation, local vectors and matrices are simple data models
+to serve public interfaces. The underly linear algebra operations are provided by
+[Breeze](http://www.scalanlp.org/) and [jblas](http://jblas.org/).
+A training example used in supervised learning is called "labeled point" in MLlib.
+
+## Local vector
+
+A local vector has integer-typed and 0-based indices and double-typed values, stored on a single
+machine. MLlib supports two types of local vectors: dense and sparse. A dense vector is backed by
+a double array representing its entry values, while a sparse vector is backed by two parallel
+arrays: indices and values. For example, a vector $(1.0, 0.0, 3.0)$ can be represented in dense
+format as `[1.0, 0.0, 3.0]` or in sparse format as `(3, [0, 2], [1.0, 3.0])`, where `3` is the size
+of the vector.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+The base class of local vectors is
+[`Vector`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vector), and we provide two
+implementations: [`DenseVector`](api/mllib/index.html#org.apache.spark.mllib.linalg.DenseVector) and
+[`SparseVector`](api/mllib/index.html#org.apache.spark.mllib.linalg.SparseVector). We recommend
+using the factory methods implemented in
+[`Vectors`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vector) to create local vectors.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.{Vector, Vectors}
+
+// Create a dense vector (1.0, 0.0, 3.0).
+val dv: Vector = Vectors.dense(1.0, 0.0, 3.0)
+// Create a sparse vector (1.0, 0.0, 3.0) by specifying its indices and values corresponding to nonzero entries.
+val sv1: Vector = Vectors.sparse(3, Array(0, 2), Array(1.0, 3.0))
+// Create a sparse vector (1.0, 0.0, 3.0) by specifying its nonzero entries.
+val sv2: Vector = Vectors.sparse(3, Seq((0, 1.0), (2, 3.0)))
+{% endhighlight %}
+
+***Note***
+
+Scala imports `scala.collection.immutable.Vector` by default, so you have to import
+`org.apache.spark.mllib.linalg.Vector` explicitly to use MLlib's `Vector`.
+
+</div>
+
+<div data-lang="java" markdown="1">
+
+The base class of local vectors is
+[`Vector`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vector), and we provide two
+implementations: [`DenseVector`](api/mllib/index.html#org.apache.spark.mllib.linalg.DenseVector) and
+[`SparseVector`](api/mllib/index.html#org.apache.spark.mllib.linalg.SparseVector). We recommend
+using the factory methods implemented in
+[`Vectors`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vector) to create local vectors.
+
+{% highlight java %}
+import org.apache.spark.mllib.linalg.Vector;
+import org.apache.spark.mllib.linalg.Vectors;
+
+// Create a dense vector (1.0, 0.0, 3.0).
+Vector dv = Vectors.dense(1.0, 0.0, 3.0);
+// Create a sparse vector (1.0, 0.0, 3.0) by specifying its indices and values corresponding to nonzero entries.
+Vector sv = Vectors.sparse(3, new int[] {0, 2}, new double[] {1.0, 3.0});
+{% endhighlight %}
+</div>
+
+<div data-lang="python" markdown="1">
+MLlib recognizes the following types as dense vectors:
+
+* NumPy's [`array`](http://docs.scipy.org/doc/numpy/reference/generated/numpy.array.html)
+* Python's list, e.g., `[1, 2, 3]`
+
+and the following as sparse vectors:
+
+* MLlib's [`SparseVector`](api/pyspark/pyspark.mllib.linalg.SparseVector-class.html).
+* SciPy's
+ [`csc_matrix`](http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html#scipy.sparse.csc_matrix)
+ with a single column
+
+We recommend using NumPy arrays over lists for efficiency, and using the factory methods implemented
+in [`Vectors`](api/pyspark/pyspark.mllib.linalg.Vectors-class.html) to create sparse vectors.
+
+{% highlight python %}
+import numpy as np
+import scipy.sparse as sps
+from pyspark.mllib.linalg import Vectors
+
+# Use a NumPy array as a dense vector.
+dv1 = np.array([1.0, 0.0, 3.0])
+# Use a Python list as a dense vector.
+dv2 = [1.0, 0.0, 3.0]
+# Create a SparseVector.
+sv1 = Vectors.sparse(3, [0, 2], [1.0, 3.0])
+# Use a single-column SciPy csc_matrix as a sparse vector.
+sv2 = sps.csc_matrix((np.array([1.0, 3.0]), np.array([0, 2]), np.array([0, 2])), shape = (3, 1))
+{% endhighlight %}
+
+</div>
+</div>
+
+## Labeled point
+
+A labeled point is a local vector, either dense or sparse, associated with a label/response.
+In MLlib, labeled points are used in supervised learning algorithms.
+We use a double to store a label, so we can use labeled points in both regression and classification.
+For binary classification, label should be either $0$ (negative) or $1$ (positive).
+For multiclass classification, labels should be class indices staring from zero: $0, 1, 2, \ldots$.
+
+<div class="codetabs">
+
+<div data-lang="scala" markdown="1">
+
+A labeled point is represented by the case class
+[`LabeledPoint`](api/mllib/index.html#org.apache.spark.mllib.regression.LabeledPoint).
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.Vectors
+import org.apache.spark.mllib.regression.LabeledPoint
+
+// Create a labeled point with a positive label and a dense feature vector.
+val pos = LabeledPoint(1.0, Vectors.dense(1.0, 0.0, 3.0))
+
+// Create a labeled point with a negative label and a sparse feature vector.
+val neg = LabeledPoint(0.0, Vectors.sparse(3, Array(0, 2), Array(1.0, 3.0)))
+{% endhighlight %}
+</div>
+
+<div data-lang="java" markdown="1">
+
+A labeled point is represented by
+[`LabeledPoint`](api/mllib/index.html#org.apache.spark.mllib.regression.LabeledPoint).
+
+{% highlight java %}
+import org.apache.spark.mllib.linalg.Vectors;
+import org.apache.spark.mllib.regression.LabeledPoint;
+
+// Create a labeled point with a positive label and a dense feature vector.
+LabeledPoint pos = new LabeledPoint(1.0, Vectors.dense(1.0, 0.0, 3.0));
+
+// Create a labeled point with a negative label and a sparse feature vector.
+LabeledPoint neg = new LabeledPoint(1.0, Vectors.sparse(3, new int[] {0, 2}, new double[] {1.0, 3.0}));
+{% endhighlight %}
+</div>
+
+<div data-lang="python" markdown="1">
+
+A labeled point is represented by
+[`LabeledPoint`](api/pyspark/pyspark.mllib.regression.LabeledPoint-class.html).
+
+{% highlight python %}
+from pyspark.mllib.linalg import SparseVector
+from pyspark.mllib.regression import LabeledPoint
+
+# Create a labeled point with a positive label and a dense feature vector.
+pos = LabeledPoint(1.0, [1.0, 0.0, 3.0])
+
+# Create a labeled point with a negative label and a sparse feature vector.
+neg = LabeledPoint(0.0, SparseVector(3, [0, 2], [1.0, 3.0]))
+{% endhighlight %}
+</div>
+</div>
+
+***Sparse data***
+
+It is very common in practice to have sparse training data. MLlib supports reading training
+examples stored in `LIBSVM` format, which is the default format used by
+[`LIBSVM`](http://www.csie.ntu.edu.tw/~cjlin/libsvm/) and
+[`LIBLINEAR`](http://www.csie.ntu.edu.tw/~cjlin/liblinear/). It is a text format. Each line
+represents a labeled sparse feature vector using the following format:
+
+~~~
+label index1:value1 index2:value2 ...
+~~~
+
+where the indices are one-based and in ascending order.
+After loading, the feature indices are converted to zero-based.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+[`MLUtils.loadLibSVMData`](api/mllib/index.html#org.apache.spark.mllib.util.MLUtils$) reads training
+examples stored in LIBSVM format.
+
+{% highlight scala %}
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.util.MLUtils
+import org.apache.spark.rdd.RDD
+
+val training: RDD[LabeledPoint] = MLUtils.loadLibSVMData(sc, "mllib/data/sample_libsvm_data.txt")
+{% endhighlight %}
+</div>
+
+<div data-lang="java" markdown="1">
+[`MLUtils.loadLibSVMData`](api/mllib/index.html#org.apache.spark.mllib.util.MLUtils$) reads training
+examples stored in LIBSVM format.
+
+{% highlight java %}
+import org.apache.spark.mllib.regression.LabeledPoint;
+import org.apache.spark.mllib.util.MLUtils;
+import org.apache.spark.rdd.RDDimport;
+
+RDD[LabeledPoint] training = MLUtils.loadLibSVMData(sc, "mllib/data/sample_libsvm_data.txt")
+{% endhighlight %}
+</div>
+</div>
+
+## Local matrix
+
+A local matrix has integer-typed row and column indices and double-typed values, stored on a single
+machine. MLlib supports dense matrix, whose entry values are stored in a single double array in
+column major. For example, the following matrix `\[ \begin{pmatrix}
+1.0 & 2.0 \\
+3.0 & 4.0 \\
+5.0 & 6.0
+\end{pmatrix}
+\]`
+is stored in a one-dimensional array `[1.0, 3.0, 5.0, 2.0, 4.0, 6.0]` with the matrix size `(3, 2)`.
+We are going to add sparse matrix in the next release.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+The base class of local matrices is
+[`Matrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.Matrix), and we provide one
+implementation: [`DenseMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.DenseMatrix).
+Sparse matrix will be added in the next release. We recommend using the factory methods implemented
+in [`Matrices`](api/mllib/index.html#org.apache.spark.mllib.linalg.Matrices) to create local
+matrices.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.{Matrix, Matrices}
+
+// Create a dense matrix ((1.0, 2.0), (3.0, 4.0), (5.0, 6.0))
+val dm: Matrix = Matrices.dense(3, 2, Array(1.0, 3.0, 5.0, 2.0, 4.0, 6.0))
+{% endhighlight %}
+</div>
+
+<div data-lang="java" markdown="1">
+
+The base class of local matrices is
+[`Matrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.Matrix), and we provide one
+implementation: [`DenseMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.DenseMatrix).
+Sparse matrix will be added in the next release. We recommend using the factory methods implemented
+in [`Matrices`](api/mllib/index.html#org.apache.spark.mllib.linalg.Matrices) to create local
+matrices.
+
+{% highlight java %}
+import org.apache.spark.mllib.linalg.Matrix;
+import org.apache.spark.mllib.linalg.Matrices;
+
+// Create a dense matrix ((1.0, 2.0), (3.0, 4.0), (5.0, 6.0))
+Matrix dm = Matrices.dense(3, 2, new double[] {1.0, 3.0, 5.0, 2.0, 4.0, 6.0});
+{% endhighlight %}
+</div>
+
+</div>
+
+## Distributed matrix
+
+A distributed matrix has long-typed row and column indices and double-typed values, stored
+distributively in one or more RDDs. It is very important to choose the right format to store large
+and distributed matrices. Converting a distributed matrix to a different format may require a
+global shuffle, which is quite expensive. We implemented three types of distributed matrices in
+this release and will add more types in the future.
+
+***Note***
+
+The underlying RDDs of a distributed matrix must be deterministic, because we cache the matrix size.
+It is always error-prone to have non-deterministic RDDs.
+
+### RowMatrix
+
+A `RowMatrix` is a row-oriented distributed matrix without meaningful row indices, backed by an RDD
+of its rows, where each row is a local vector. This is similar to `data matrix` in the context of
+multivariate statistics. Since each row is represented by a local vector, the number of columns is
+limited by the integer range but it should be much smaller in practice.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+A [`RowMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.RowMatrix) can be
+created from an `RDD[Vector]` instance. Then we can compute its column summary statistics.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.Vector
+import org.apache.spark.mllib.linalg.distributed.RowMatrix
+
+val rows: RDD[Vector] = ... // an RDD of local vectors
+// Create a RowMatrix from an RDD[Vector].
+val mat: RowMatrix = new RowMatrix(rows)
+
+// Get its size.
+val m = mat.numRows()
+val n = mat.numCols()
+{% endhighlight %}
+</div>
+
+<div data-lang="java" markdown="1">
+
+A [`RowMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.RowMatrix) can be
+created from a `JavaRDD<Vector>` instance. Then we can compute its column summary statistics.
+
+{% highlight java %}
+import org.apache.spark.mllib.linalg.Vector;
+import org.apache.spark.mllib.linalg.distributed.RowMatrix;
+
+JavaRDD<Vector> rows = ... // a JavaRDD of local vectors
+// Create a RowMatrix from an JavaRDD<Vector>.
+RowMatrix mat = new RowMatrix(rows.rdd());
+
+// Get its size.
+long m = mat.numRows();
+long n = mat.numCols();
+{% endhighlight %}
+</div>
+</div>
+
+#### Multivariate summary statistics
+
+We provide column summary statistics for `RowMatrix`.
+If the number of columns is not large, say, smaller than 3000, you can also compute
+the covariance matrix as a local matrix, which requires $\mathcal{O}(n^2)$ storage where $n$ is the
+number of columns. The total CPU time is $\mathcal{O}(m n^2)$, where $m$ is the number of rows,
+which could be faster if the rows are sparse.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+`RowMatrix#computeColumnSummaryStatistics` returns an instance of
+[`MultivariateStatisticalSummary`](api/mllib/index.html#org.apache.spark.mllib.stat.MultivariateStatisticalSummary),
+which contains the column-wise max, min, mean, variance, and number of nonzeros, as well as the
+total count.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.Matrix
+import org.apache.spark.mllib.linalg.distributed.RowMatrix
+import org.apache.spark.mllib.stat.MultivariateStatisticalSummary
+
+val mat: RowMatrix = ... // a RowMatrix
+
+// Compute column summary statistics.
+val summary: MultivariateStatisticalSummary = mat.computeColumnSummaryStatistics()
+println(summary.mean) // a dense vector containing the mean value for each column
+println(summary.variance) // column-wise variance
+println(summary.numNonzers) // number of nonzeros in each column
+
+// Compute the covariance matrix.
+val Cov: Matrix = mat.computeCovariance()
+{% endhighlight %}
+</div>
+</div>
+
+### IndexedRowMatrix
+
+An `IndexedRowMatrix` is similar to a `RowMatrix` but with meaningful row indices. It is backed by
+an RDD of indexed rows, which each row is represented by its index (long-typed) and a local vector.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+An
+[`IndexedRowMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.IndexedRowMatrix)
+can be created from an `RDD[IndexedRow]` instance, where
+[`IndexedRow`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.IndexedRow) is a
+wrapper over `(Long, Vector)`. An `IndexedRowMatrix` can be converted to a `RowMatrix` by dropping
+its row indices.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.distributed.{IndexedRow, IndexedRowMatrix, RowMatrix}
+
+val rows: RDD[IndexedRow] = ... // an RDD of indexed rows
+// Create an IndexedRowMatrix from an RDD[IndexedRow].
+val mat: IndexedRowMatrix = new IndexedRowMatrix(rows)
+
+// Get its size.
+val m = mat.numRows()
+val n = mat.numCols()
+
+// Drop its row indices.
+val rowMat: RowMatrix = mat.toRowMatrix()
+{% endhighlight %}
+</div>
+
+<div data-lang="java" markdown="1">
+
+An
+[`IndexedRowMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.IndexedRowMatrix)
+can be created from an `JavaRDD<IndexedRow>` instance, where
+[`IndexedRow`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.IndexedRow) is a
+wrapper over `(long, Vector)`. An `IndexedRowMatrix` can be converted to a `RowMatrix` by dropping
+its row indices.
+
+{% highlight java %}
+import org.apache.spark.mllib.linalg.distributed.IndexedRow;
+import org.apache.spark.mllib.linalg.distributed.IndexedRowMatrix;
+import org.apache.spark.mllib.linalg.distributed.RowMatrix;
+
+JavaRDD[IndexedRow] rows = ... // a JavaRDD of indexed rows
+// Create an IndexedRowMatrix from a JavaRDD<IndexedRow>.
+IndexedRowMatrix mat = new IndexedRowMatrix(rows.rdd());
+
+// Get its size.
+long m = mat.numRows();
+long n = mat.numCols();
+
+// Drop its row indices.
+RowMatrix rowMat = mat.toRowMatrix();
+{% endhighlight %}
+</div></div>
+
+### CoordinateMatrix
+
+A `CoordinateMatrix` is a distributed matrix backed by an RDD of its entries. Each entry is a tuple
+of `(i: Long, j: Long, value: Double)`, where `i` is the row index, `j` is the column index, and
+`value` is the entry value. A `CoordinateMatrix` should be used only in the case when both
+dimensions of the matrix are huge and the matrix is very sparse.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+A
+[`CoordinateMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.CoordinateMatrix)
+can be created from an `RDD[MatrixEntry]` instance, where
+[`MatrixEntry`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.MatrixEntry) is a
+wrapper over `(Long, Long, Double)`. A `CoordinateMatrix` can be converted to a `IndexedRowMatrix`
+with sparse rows by calling `toIndexedRowMatrix`. In this release, we do not provide other
+computation for `CoordinateMatrix`.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.distributed.{CoordinateMatrix, MatrixEntry}
+
+val entries: RDD[MatrixEntry] = ... // an RDD of matrix entries
+// Create a CoordinateMatrix from an RDD[MatrixEntry].
+val mat: CoordinateMatrix = new CoordinateMatrix(entries)
+
+// Get its size.
+val m = mat.numRows()
+val n = mat.numCols()
+
+// Convert it to an IndexRowMatrix whose rows are sparse vectors.
+val indexedRowMatrix = mat.toIndexedRowMatrix()
+{% endhighlight %}
+</div>
+
+<div data-lang="java" markdown="1">
+
+A
+[`CoordinateMatrix`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.CoordinateMatrix)
+can be created from a `JavaRDD<MatrixEntry>` instance, where
+[`MatrixEntry`](api/mllib/index.html#org.apache.spark.mllib.linalg.distributed.MatrixEntry) is a
+wrapper over `(long, long, double)`. A `CoordinateMatrix` can be converted to a `IndexedRowMatrix`
+with sparse rows by calling `toIndexedRowMatrix`.
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.distributed.CoordinateMatrix;
+import org.apache.spark.mllib.linalg.distributed.MatrixEntry;
+
+JavaRDD<MatrixEntry> entries = ... // a JavaRDD of matrix entries
+// Create a CoordinateMatrix from a JavaRDD<MatrixEntry>.
+CoordinateMatrix mat = new CoordinateMatrix(entries);
+
+// Get its size.
+long m = mat.numRows();
+long n = mat.numCols();
+
+// Convert it to an IndexRowMatrix whose rows are sparse vectors.
+IndexedRowMatrix indexedRowMatrix = mat.toIndexedRowMatrix();
+{% endhighlight %}
+</div>
+</div>
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-classification-regression.md
----------------------------------------------------------------------
diff --git a/docs/mllib-classification-regression.md b/docs/mllib-classification-regression.md
deleted file mode 100644
index 2e0fa09..0000000
--- a/docs/mllib-classification-regression.md
+++ /dev/null
@@ -1,568 +0,0 @@
----
-layout: global
-title: MLlib - Classification and Regression
----
-
-* Table of contents
-{:toc}
-
-
-`\[
-\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}}
-\]`
-
-
-# Supervised Machine Learning
-Supervised machine learning is the setting where we are given a set of training data examples
-`$\{\x_i\}$`, each example `$\x_i$` coming with a corresponding label `$y_i$`.
-Given the training data `$\{(\x_i,y_i)\}$`, we want to learn a function to predict these labels.
-The two most well known classes of methods are
-[classification](http://en.wikipedia.org/wiki/Statistical_classification), and
-[regression](http://en.wikipedia.org/wiki/Regression_analysis).
-In classification, the label is a category (e.g. whether or not emails are spam), whereas in
-regression, the label is real value, and we want our prediction to be as close to the true value
-as possible.
-
-Supervised Learning involves executing a learning *Algorithm* on a set of *labeled* training
-examples. The algorithm returns a trained *Model* (such as for example a linear function) that
-can predict the label for new data examples for which the label is unknown.
-
-## Discriminative Training using Linear Methods
-
-### Mathematical Formulation
-Many standard *machine learning* methods can be formulated as a convex optimization problem, i.e.
-the task of finding a minimizer of a convex function `$f$` that depends on a variable vector
-`$\wv$` (called `weights` in the code), which has `$d$` entries.
-Formally, we can write this as the optimization problem `$\min_{\wv \in\R^d} \; f(\wv)$`, where
-the objective function is of the form
-`\begin{equation}
- f(\wv) :=
- \lambda\, R(\wv) +
- \frac1n \sum_{i=1}^n L(\wv;\x_i,y_i)
- \label{eq:regPrimal}
- \ .
-\end{equation}`
-Here the vectors `$\x_i\in\R^d$` are the training data examples, for `$1\le i\le n$`, and
-`$y_i\in\R$` are their corresponding labels, which we want to predict.
-
-The objective function `$f$` has two parts:
-The *loss-function* measures the error of the model on the training data. The loss-function
-`$L(\wv;.)$` must be a convex function in `$\wv$`.
-The purpose of the [regularizer](http://en.wikipedia.org/wiki/Regularization_(mathematics)) is to
-encourage simple models, by punishing the complexity of the model `$\wv$`, in order to e.g. avoid
-over-fitting.
-Usually, the regularizer `$R(.)$` is chosen as either the standard (Euclidean) L2-norm, `$R(\wv)
-:= \frac{1}{2}\|\wv\|^2$`, or the L1-norm, `$R(\wv) := \|\wv\|_1$`, see
-[below](#using-different-regularizers) for more details.
-
-The fixed regularization parameter `$\lambda\ge0$` (`regParam` in the code) defines the trade-off
-between the two goals of small loss and small model complexity.
-
-
-### Binary Classification
-
-**Input:** Datapoints `$\x_i\in\R^{d}$`, labels `$y_i\in\{+1,-1\}$`, for `$1\le i\le n$`.
-
-**Distributed Datasets.**
-For all currently implemented optimization methods for classification, the data must be
-distributed between processes on the worker machines *by examples*. Machines hold consecutive
-blocks of the `$n$` example/label pairs `$(\x_i,y_i)$`.
-In other words, the input distributed dataset
-([RDD](scala-programming-guide.html#resilient-distributed-datasets-rdds)) must be the set of
-vectors `$\x_i\in\R^d$`.
-
-#### Support Vector Machine
-The linear [Support Vector Machine (SVM)](http://en.wikipedia.org/wiki/Support_vector_machine)
-has become a standard choice for classification tasks.
-Here the loss function in formulation `$\eqref{eq:regPrimal}$` is given by the hinge-loss
-`\[
-L(\wv;\x_i,y_i) := \max \{0, 1-y_i \wv^T \x_i \} \ .
-\]`
-
-By default, SVMs are trained with an L2 regularization, which gives rise to the large-margin
-interpretation if these classifiers. We also support alternative L1 regularization. In this case,
-the primal optimization problem becomes an [LP](http://en.wikipedia.org/wiki/Linear_programming).
-
-#### Logistic Regression
-Despite its name, [Logistic Regression](http://en.wikipedia.org/wiki/Logistic_regression) is a
-binary classification method, again when the labels are given by binary values
-`$y_i\in\{+1,-1\}$`. The logistic loss function in formulation `$\eqref{eq:regPrimal}$` is
-defined as
-`\[
-L(\wv;\x_i,y_i) := \log(1+\exp( -y_i \wv^T \x_i)) \ .
-\]`
-
-
-### Linear Regression (Least Squares, Lasso and Ridge Regression)
-
-**Input:** Data matrix `$A\in\R^{n\times d}$`, right hand side vector `$\y\in\R^n$`.
-
-**Distributed Datasets.**
-For all currently implemented optimization methods for regression, the data matrix
-`$A\in\R^{n\times d}$` must be distributed between the worker machines *by rows* of `$A$`. In
-other words, the input distributed dataset
-([RDD](scala-programming-guide.html#resilient-distributed-datasets-rdds)) must be the set of the
-`$n$` rows `$A_{i:}$` of `$A$`.
-
-Least Squares Regression refers to the setting where we try to fit a vector `$\y\in\R^n$` by
-linear combination of our observed data `$A\in\R^{n\times d}$`, which is given as a matrix.
-
-It comes in 3 flavors:
-
-#### Least Squares
-Plain old [least squares](http://en.wikipedia.org/wiki/Least_squares) linear regression is the
-problem of minimizing
- `\[ f_{\text{LS}}(\wv) := \frac1n \|A\wv-\y\|_2^2 \ . \]`
-
-#### Lasso
-The popular [Lasso](http://en.wikipedia.org/wiki/Lasso_(statistics)#Lasso_method) (alternatively
-also known as `$L_1$`-regularized least squares regression) is given by
- `\[ f_{\text{Lasso}}(\wv) := \frac1n \|A\wv-\y\|_2^2 + \lambda \|\wv\|_1 \ . \]`
-
-#### Ridge Regression
-[Ridge regression](http://en.wikipedia.org/wiki/Ridge_regression) uses the same loss function but
-with a L2 regularizer term:
- `\[ f_{\text{Ridge}}(\wv) := \frac1n \|A\wv-\y\|_2^2 + \frac{\lambda}{2}\|\wv\|^2 \ . \]`
-
-**Loss Function.**
-For all 3, the loss function (i.e. the measure of model fit) is given by the squared deviations
-from the right hand side `$\y$`.
-`\[
-\frac1n \|A\wv-\y\|_2^2
-= \frac1n \sum_{i=1}^n (A_{i:} \wv - y_i )^2
-= \frac1n \sum_{i=1}^n L(\wv;\x_i,y_i)
-\]`
-This is also known as the [mean squared error](http://en.wikipedia.org/wiki/Mean_squared_error).
-In our generic problem formulation `$\eqref{eq:regPrimal}$`, this means the loss function is
-`$L(\wv;\x_i,y_i) := (A_{i:} \wv - y_i )^2$`, each depending only on a single row `$A_{i:}$` of
-the data matrix `$A$`.
-
-
-### Using Different Regularizers
-
-As we have mentioned above, the purpose of *regularizer* in `$\eqref{eq:regPrimal}$` is to
-encourage simple models, by punishing the complexity of the model `$\wv$`, in order to e.g. avoid
-over-fitting.
-All machine learning methods for classification and regression that we have mentioned above are
-of interest for different types of regularization, the 3 most common ones being
-
-* **L2-Regularization.**
-`$R(\wv) := \frac{1}{2}\|\wv\|^2$`.
-This regularizer is most commonly used for SVMs, logistic regression and ridge regression.
-
-* **L1-Regularization.**
-`$R(\wv) := \|\wv\|_1$`. The L1 norm `$\|\wv\|_1$` is the sum of the absolut values of the
-entries of a vector `$\wv$`.
-This regularizer is most commonly used for sparse methods, and feature selection, such as the
-Lasso.
-
-* **Non-Regularized.**
-`$R(\wv):=0$`.
-Of course we can also train the models without any regularization, or equivalently by setting the
-regularization parameter `$\lambda:=0$`.
-
-The optimization problems of the form `$\eqref{eq:regPrimal}$` with convex regularizers such as
-the 3 mentioned here can be conveniently optimized with gradient descent type methods (such as
-SGD) which is implemented in `MLlib` currently, and explained in the next section.
-
-
-### Optimization Methods Working on the Primal Formulation
-
-**Stochastic subGradient Descent (SGD).**
-For optimization objectives `$f$` written as a sum, *stochastic subgradient descent (SGD)* can be
-an efficient choice of optimization method, as we describe in the <a
-href="mllib-optimization.html">optimization section</a> in more detail.
-Because all methods considered here fit into the optimization formulation
-`$\eqref{eq:regPrimal}$`, this is especially natural, because the loss is written as an average
-of the individual losses coming from each datapoint.
-
-Picking one datapoint `$i\in[1..n]$` uniformly at random, we obtain a stochastic subgradient of
-`$\eqref{eq:regPrimal}$`, with respect to `$\wv$` as follows:
-`\[
-f'_{\wv,i} := L'_{\wv,i} + \lambda\, R'_\wv \ ,
-\]`
-where `$L'_{\wv,i} \in \R^d$` is a subgradient of the part of the loss function determined by the
-`$i$`-th datapoint, that is `$L'_{\wv,i} \in \frac{\partial}{\partial \wv} L(\wv;\x_i,y_i)$`.
-Furthermore, `$R'_\wv$` is a subgradient of the regularizer `$R(\wv)$`, i.e. `$R'_\wv \in
-\frac{\partial}{\partial \wv} R(\wv)$`. The term `$R'_\wv$` does not depend on which random
-datapoint is picked.
-
-
-
-**Gradients.**
-The following table summarizes the gradients (or subgradients) of all loss functions and
-regularizers that we currently support:
-
-<table class="table">
- <thead>
- <tr><th></th><th>Function</th><th>Stochastic (Sub)Gradient</th></tr>
- </thead>
- <tbody>
- <tr>
- <td>SVM Hinge Loss</td><td>$L(\wv;\x_i,y_i) := \max \{0, 1-y_i \wv^T \x_i \}$</td>
- <td>$L'_{\wv,i} = \begin{cases}-y_i \x_i & \text{if $y_i \wv^T \x_i <1$}, \\ 0 &
-\text{otherwise}.\end{cases}$</td>
- </tr>
- <tr>
- <td>Logistic Loss</td><td>$L(\wv;\x_i,y_i) := \log(1+\exp( -y_i \wv^T \x_i))$</td>
- <td>$L'_{\wv,i} = -y_i \x_i \left(1-\frac1{1+\exp(-y_i \wv^T \x_i)} \right)$</td>
- </tr>
- <tr>
- <td>Least Squares Loss</td><td>$L(\wv;\x_i,y_i) := (A_{i:} \wv - y_i)^2$</td>
- <td>$L'_{\wv,i} = 2 A_{i:}^T (A_{i:} \wv - y_i)$</td>
- </tr>
- <tr>
- <td>Non-Regularized</td><td>$R(\wv) := 0$</td><td>$R'_\wv = \0$</td>
- </tr>
- <tr>
- <td>L2 Regularizer</td><td>$R(\wv) := \frac{1}{2}\|\wv\|^2$</td><td>$R'_\wv = \wv$</td>
- </tr>
- <tr>
- <td>L1 Regularizer</td><td>$R(\wv) := \|\wv\|_1$</td><td>$R'_\wv = \mathop{sign}(\wv)$</td>
- </tr>
- </tbody>
-</table>
-
-Here `$\mathop{sign}(\wv)$` is the vector consisting of the signs (`$\pm1$`) of all the entries
-of `$\wv$`.
-Also, note that `$A_{i:} \in \R^d$` is a row-vector, but the gradient is a column vector.
-
-## Decision Tree Classification and Regression
-
-Decision trees and their ensembles are popular methods for the machine learning tasks of classification and regression. Decision trees are widely used since they are easy to interpret, handle categorical variables, extend to the multi-class classification setting, do not require feature scaling and are able to capture non-linearities and feature interactions. Tree ensemble algorithms such as decision forest and boosting are among the top performers for classification and regression tasks.
-
-### Basic Algorithm
-
-The decision tree is a greedy algorithm that performs a recursive binary partitioning of the feature space by choosing a single element from the *best split set* where each element of the set maximimizes the information gain at a tree node. In other words, the split chosen at each tree node is chosen from the set `$\underset{s}{\operatorname{argmax}} IG(D,s)$` where `$IG(D,s)$` is the information gain when a split `$s$` is applied to a dataset `$D$`.
-
-#### Node Impurity and Information Gain
-
-The *node impurity* is a measure of the homogeneity of the labels at the node. The current implementation provides two impurity measures for classification (Gini index and entropy) and one impurity measure for regression (variance).
-
-<table class="table">
- <thead>
- <tr><th>Impurity</th><th>Task</th><th>Formula</th><th>Description</th></tr>
- </thead>
- <tbody>
- <tr>
- <td>Gini index</td><td>Classification</td><td>$\sum_{i=1}^{M} f_i(1-f_i)$</td><td>$f_i$ is the frequency of label $i$ at a node and $M$ is the number of unique labels.</td>
- </tr>
- <tr>
- <td>Entropy</td><td>Classification</td><td>$\sum_{i=1}^{M} -f_ilog(f_i)$</td><td>$f_i$ is the frequency of label $i$ at a node and $M$ is the number of unique labels.</td>
- </tr>
- <tr>
- <td>Variance</td><td>Classification</td><td>$\frac{1}{n} \sum_{i=1}^{N} (x_i - \mu)^2$</td><td>$y_i$ is label for an instance, $N$ is the number of instances and $\mu$ is the mean given by $\frac{1}{N} \sum_{i=1}^n x_i$.</td>
- </tr>
- </tbody>
-</table>
-
-The *information gain* is the difference in the parent node impurity and the weighted sum of the two child node impurities. Assuming that a split $s$ partitions the dataset `$D$` of size `$N$` into two datasets `$D_{left}$` and `$D_{right}$` of sizes `$N_{left}$` and `$N_{right}$`, respectively:
-
-`$IG(D,s) = Impurity(D) - \frac{N_{left}}{N} Impurity(D_{left}) - \frac{N_{right}}{N} Impurity(D_{right})$`
-
-#### Split Candidates
-
-**Continuous Features**
-
-For small datasets in single machine implementations, the split candidates for each continuous feature are typically the unique values for the feature. Some implementations sort the feature values and then use the ordered unique values as split candidates for faster tree calculations.
-
-Finding ordered unique feature values is computationally intensive for large distributed datasets. One can get an approximate set of split candidates by performing a quantile calculation over a sampled fraction of the data. The ordered splits create "bins" and the maximum number of such bins can be specified using the `maxBins` parameters.
-
-Note that the number of bins cannot be greater than the number of instances `$N$` (a rare scenario since the default `maxBins` value is 100). The tree algorithm automatically reduces the number of bins if the condition is not satisfied.
-
-**Categorical Features**
-
-For `$M$` categorical features, one could come up with `$2^M-1$` split candidates. However, for binary classification, the number of split candidates can be reduced to `$M-1$` by ordering the categorical feature values by the proportion of labels falling in one of the two classes (see Section 9.2.4 in [Elements of Statistical Machine Learning](http://statweb.stanford.edu/~tibs/ElemStatLearn/) for details). For example, for a binary classification problem with one categorical feature with three categories A, B and C with corresponding proportion of label 1 as 0.2, 0.6 and 0.4, the categorical features are orded as A followed by C followed B or A, B, C. The two split candidates are A \| C, B and A , B \| C where \| denotes the split.
-
-#### Stopping Rule
-
-The recursive tree construction is stopped at a node when one of the two conditions is met:
-
-1. The node depth is equal to the `maxDepth` training paramemter
-2. No split candidate leads to an information gain at the node.
-
-### Practical Limitations
-
-The tree implementation stores an Array[Double] of size *O(#features \* #splits \* 2^maxDepth)* in memory for aggregating histograms over partitions. The current implementation might not scale to very deep trees since the memory requirement grows exponentially with tree depth.
-
-Please drop us a line if you encounter any issues. We are planning to solve this problem in the near future and real-world examples will be great.
-
-
-## Implementation in MLlib
-
-#### Linear Methods
-
-For both classification and regression algorithms with convex loss functions, `MLlib` implements a simple distributed version of
-stochastic subgradient descent (SGD), building on the underlying gradient descent primitive (as
-described in the
-<a href="mllib-optimization.html">optimization section</a>).
-All provided algorithms take as input a regularization parameter (`regParam`) along with various
-parameters associated with stochastic gradient
-descent (`stepSize`, `numIterations`, `miniBatchFraction`).
-For each of them, we support all 3 possible regularizations (none, L1 or L2).
-
-Available algorithms for binary classification:
-
-* [SVMWithSGD](api/scala/index.html#org.apache.spark.mllib.classification.SVMWithSGD)
-* [LogisticRegressionWithSGD](api/scala/index.html#org.apache.spark.mllib.classification.LogisticRegressionWithSGD)
-
-Available algorithms for linear regression:
-
-* [LinearRegressionWithSGD](api/scala/index.html#org.apache.spark.mllib.regression.LinearRegressionWithSGD)
-* [RidgeRegressionWithSGD](api/scala/index.html#org.apache.spark.mllib.regression.RidgeRegressionWithSGD)
-* [LassoWithSGD](api/scala/index.html#org.apache.spark.mllib.regression.LassoWithSGD)
-
-Behind the scenes, all above methods use the SGD implementation from the
-gradient descent primitive in MLlib, see the
-<a href="mllib-optimization.html">optimization</a> part:
-
-* [GradientDescent](api/scala/index.html#org.apache.spark.mllib.optimization.GradientDescent)
-
-#### Tree-based Methods
-
-The decision tree algorithm supports binary classification and regression:
-
-* [DecisionTee](api/scala/index.html#org.apache.spark.mllib.tree.DecisionTree)
-
-
-# Usage in Scala
-
-Following code snippets can be executed in `spark-shell`.
-
-## Linear Methods
-
-
-#### Binary Classification
-
-The following code snippet illustrates how to load a sample dataset, execute a
-training algorithm on this training data using a static method in the algorithm
-object, and make predictions with the resulting model to compute the training
-error.
-
-{% highlight scala %}
-import org.apache.spark.SparkContext
-import org.apache.spark.mllib.classification.SVMWithSGD
-import org.apache.spark.mllib.regression.LabeledPoint
-import org.apache.spark.mllib.linalg.Vectors
-
-// Load and parse the data file
-val data = sc.textFile("mllib/data/sample_svm_data.txt")
-val parsedData = data.map { line =>
- val parts = line.split(' ').map(_.toDouble)
- LabeledPoint(parts(0), Vectors.dense(parts.tail))
-}
-
-// Run training algorithm to build the model
-val numIterations = 100
-val model = SVMWithSGD.train(parsedData, numIterations)
-
-// Evaluate model on training examples and compute training error
-val labelAndPreds = parsedData.map { point =>
- val prediction = model.predict(point.features)
- (point.label, prediction)
-}
-val trainErr = labelAndPreds.filter(r => r._1 != r._2).count.toDouble / parsedData.count
-println("Training Error = " + trainErr)
-{% endhighlight %}
-
-
-The `SVMWithSGD.train()` method by default performs L2 regularization with the
-regularization parameter set to 1.0. If we want to configure this algorithm, we
-can customize `SVMWithSGD` further by creating a new object directly and
-calling setter methods. All other MLlib algorithms support customization in
-this way as well. For example, the following code produces an L1 regularized
-variant of SVMs with regularization parameter set to 0.1, and runs the training
-algorithm for 200 iterations.
-
-{% highlight scala %}
-import org.apache.spark.mllib.optimization.L1Updater
-
-val svmAlg = new SVMWithSGD()
-svmAlg.optimizer.setNumIterations(200)
- .setRegParam(0.1)
- .setUpdater(new L1Updater)
-val modelL1 = svmAlg.run(parsedData)
-{% endhighlight %}
-
-#### Linear Regression
-
-The following example demonstrate how to load training data, parse it as an RDD of LabeledPoint.
-The example then uses LinearRegressionWithSGD to build a simple linear model to predict label
-values. We compute the Mean Squared Error at the end to evaluate
-[goodness of fit](http://en.wikipedia.org/wiki/Goodness_of_fit).
-
-{% highlight scala %}
-import org.apache.spark.mllib.regression.LinearRegressionWithSGD
-import org.apache.spark.mllib.regression.LabeledPoint
-import org.apache.spark.mllib.linalg.Vectors
-
-// Load and parse the data
-val data = sc.textFile("mllib/data/ridge-data/lpsa.data")
-val parsedData = data.map { line =>
- val parts = line.split(',')
- LabeledPoint(parts(0).toDouble, Vectors.dense(parts(1).split(' ').map(_.toDouble)))
-}
-
-// Building the model
-val numIterations = 100
-val model = LinearRegressionWithSGD.train(parsedData, numIterations)
-
-// Evaluate model on training examples and compute training error
-val valuesAndPreds = parsedData.map { point =>
- val prediction = model.predict(point.features)
- (point.label, prediction)
-}
-val MSE = valuesAndPreds.map{case(v, p) => math.pow((v - p), 2)}.reduce(_ + _) / valuesAndPreds.count
-println("training Mean Squared Error = " + MSE)
-{% endhighlight %}
-
-
-Similarly you can use RidgeRegressionWithSGD and LassoWithSGD and compare training
-[Mean Squared Errors](http://en.wikipedia.org/wiki/Mean_squared_error).
-
-## Decision Tree
-
-#### Classification
-
-The example below demonstrates how to load a CSV file, parse it as an RDD of LabeledPoint and then perform classification using a decision tree using Gini index as an impurity measure and a maximum tree depth of 5. The training error is calculated to measure the algorithm accuracy.
-
-{% highlight scala %}
-import org.apache.spark.SparkContext
-import org.apache.spark.mllib.tree.DecisionTree
-import org.apache.spark.mllib.regression.LabeledPoint
-import org.apache.spark.mllib.linalg.Vectors
-import org.apache.spark.mllib.tree.configuration.Algo._
-import org.apache.spark.mllib.tree.impurity.Gini
-
-// Load and parse the data file
-val data = sc.textFile("mllib/data/sample_tree_data.csv")
-val parsedData = data.map { line =>
- val parts = line.split(',').map(_.toDouble)
- LabeledPoint(parts(0), Vectors.dense(parts.tail))
-}
-
-// Run training algorithm to build the model
-val maxDepth = 5
-val model = DecisionTree.train(parsedData, Classification, Gini, maxDepth)
-
-// Evaluate model on training examples and compute training error
-val labelAndPreds = parsedData.map { point =>
- val prediction = model.predict(point.features)
- (point.label, prediction)
-}
-val trainErr = labelAndPreds.filter(r => r._1 != r._2).count.toDouble / parsedData.count
-println("Training Error = " + trainErr)
-{% endhighlight %}
-
-#### Regression
-
-The example below demonstrates how to load a CSV file, parse it as an RDD of LabeledPoint and then perform regression using a decision tree using variance as an impurity measure and a maximum tree depth of 5. The Mean Squared Error is computed at the end to evaluate
-[goodness of fit](http://en.wikipedia.org/wiki/Goodness_of_fit).
-
-{% highlight scala %}
-import org.apache.spark.SparkContext
-import org.apache.spark.mllib.tree.DecisionTree
-import org.apache.spark.mllib.regression.LabeledPoint
-import org.apache.spark.mllib.linalg.Vectors
-import org.apache.spark.mllib.tree.configuration.Algo._
-import org.apache.spark.mllib.tree.impurity.Variance
-
-// Load and parse the data file
-val data = sc.textFile("mllib/data/sample_tree_data.csv")
-val parsedData = data.map { line =>
- val parts = line.split(',').map(_.toDouble)
- LabeledPoint(parts(0), Vectors.dense(parts.tail))
-}
-
-// Run training algorithm to build the model
-val maxDepth = 5
-val model = DecisionTree.train(parsedData, Regression, Variance, maxDepth)
-
-// Evaluate model on training examples and compute training error
-val valuesAndPreds = parsedData.map { point =>
- val prediction = model.predict(point.features)
- (point.label, prediction)
-}
-val MSE = valuesAndPreds.map{ case(v, p) => math.pow((v - p), 2)}.reduce(_ + _)/valuesAndPreds.count
-println("training Mean Squared Error = " + MSE)
-{% endhighlight %}
-
-
-# Usage in Java
-
-All of MLlib's methods use Java-friendly types, so you can import and call them there the same
-way you do in Scala. The only caveat is that the methods take Scala RDD objects, while the
-Spark Java API uses a separate `JavaRDD` class. You can convert a Java RDD to a Scala one by
-calling `.rdd()` on your `JavaRDD` object.
-
-# Usage in Python
-
-Following examples can be tested in the PySpark shell.
-
-## Linear Methods
-
-### Binary Classification
-The following example shows how to load a sample dataset, build Logistic Regression model,
-and make predictions with the resulting model to compute the training error.
-
-{% highlight python %}
-from pyspark.mllib.classification import LogisticRegressionWithSGD
-from pyspark.mllib.regression import LabeledPoint
-from numpy import array
-
-# Load and parse the data
-def parsePoint(line):
- values = [float(x) for x in line.split(' ')]
- return LabeledPoint(values[0], values[1:])
-
-data = sc.textFile("mllib/data/sample_svm_data.txt")
-parsedData = data.map(parsePoint)
-
-# Build the model
-model = LogisticRegressionWithSGD.train(parsedData)
-
-# Evaluating the model on training data
-labelsAndPreds = parsedData.map(lambda p: (p.label, model.predict(p.features)))
-trainErr = labelsAndPreds.filter(lambda (v, p): v != p).count() / float(parsedData.count())
-print("Training Error = " + str(trainErr))
-{% endhighlight %}
-
-### Linear Regression
-The following example demonstrate how to load training data, parse it as an RDD of LabeledPoint.
-The example then uses LinearRegressionWithSGD to build a simple linear model to predict label
-values. We compute the Mean Squared Error at the end to evaluate
-[goodness of fit](http://en.wikipedia.org/wiki/Goodness_of_fit).
-
-{% highlight python %}
-from pyspark.mllib.regression import LabeledPoint, LinearRegressionWithSGD
-from numpy import array
-
-# Load and parse the data
-def parsePoint(line):
- values = [float(x) for x in line.replace(',', ' ').split(' ')]
- return LabeledPoint(values[0], values[1:])
-
-data = sc.textFile("mllib/data/ridge-data/lpsa.data")
-parsedData = data.map(parsePoint)
-
-# Build the model
-model = LinearRegressionWithSGD.train(parsedData)
-
-# Evaluate the model on training data
-valuesAndPreds = parsedData.map(lambda p: (p.label, model.predict(p.features)))
-MSE = valuesAndPreds.map(lambda (v, p): (v - p)**2).reduce(lambda x, y: x + y) / valuesAndPreds.count()
-print("Mean Squared Error = " + str(MSE))
-{% endhighlight %}
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-clustering.md
----------------------------------------------------------------------
diff --git a/docs/mllib-clustering.md b/docs/mllib-clustering.md
index 0359c67..b3293af 100644
--- a/docs/mllib-clustering.md
+++ b/docs/mllib-clustering.md
@@ -1,19 +1,21 @@
---
layout: global
-title: MLlib - Clustering
+title: <a href="mllib-guide.html">MLlib</a> - Clustering
---
* Table of contents
{:toc}
-# Clustering
+## Clustering
Clustering is an unsupervised learning problem whereby we aim to group subsets
of entities with one another based on some notion of similarity. Clustering is
often used for exploratory analysis and/or as a component of a hierarchical
supervised learning pipeline (in which distinct classifiers or regression
-models are trained for each cluster). MLlib supports
+models are trained for each cluster).
+
+MLlib supports
[k-means](http://en.wikipedia.org/wiki/K-means_clustering) clustering, one of
the most commonly used clustering algorithms that clusters the data points into
predfined number of clusters. The MLlib implementation includes a parallelized
@@ -31,17 +33,14 @@ a given dataset, the algorithm returns the best clustering result).
* *initializiationSteps* determines the number of steps in the k-means\|\| algorithm.
* *epsilon* determines the distance threshold within which we consider k-means to have converged.
-Available algorithms for clustering:
-
-* [KMeans](api/scala/index.html#org.apache.spark.mllib.clustering.KMeans)
-
-
-
-# Usage in Scala
+## Examples
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
Following code snippets can be executed in `spark-shell`.
-In the following example after loading and parsing data, we use the KMeans object to cluster the data
+In the following example after loading and parsing data, we use the
+[`KMeans`](api/mllib/index.html#org.apache.spark.mllib.clustering.KMeans) object to cluster the data
into two clusters. The number of desired clusters is passed to the algorithm. We then compute Within
Set Sum of Squared Error (WSSSE). You can reduce this error measure by increasing *k*. In fact the
optimal *k* is usually one where there is an "elbow" in the WSSSE graph.
@@ -63,22 +62,22 @@ val clusters = KMeans.train(parsedData, numClusters, numIterations)
val WSSSE = clusters.computeCost(parsedData)
println("Within Set Sum of Squared Errors = " + WSSSE)
{% endhighlight %}
+</div>
-
-# Usage in Java
-
+<div data-lang="java" markdown="1">
All of MLlib's methods use Java-friendly types, so you can import and call them there the same
way you do in Scala. The only caveat is that the methods take Scala RDD objects, while the
Spark Java API uses a separate `JavaRDD` class. You can convert a Java RDD to a Scala one by
calling `.rdd()` on your `JavaRDD` object.
+</div>
-# Usage in Python
+<div data-lang="python" markdown="1">
Following examples can be tested in the PySpark shell.
-In the following example after loading and parsing data, we use the KMeans object to cluster the data
-into two clusters. The number of desired clusters is passed to the algorithm. We then compute Within
-Set Sum of Squared Error (WSSSE). You can reduce this error measure by increasing *k*. In fact the
-optimal *k* is usually one where there is an "elbow" in the WSSSE graph.
+In the following example after loading and parsing data, we use the KMeans object to cluster the
+data into two clusters. The number of desired clusters is passed to the algorithm. We then compute
+Within Set Sum of Squared Error (WSSSE). You can reduce this error measure by increasing *k*. In
+fact the optimal *k* is usually one where there is an "elbow" in the WSSSE graph.
{% highlight python %}
from pyspark.mllib.clustering import KMeans
@@ -91,7 +90,7 @@ parsedData = data.map(lambda line: array([float(x) for x in line.split(' ')]))
# Build the model (cluster the data)
clusters = KMeans.train(parsedData, 2, maxIterations=10,
- runs=10, initialization_mode="random")
+ runs=10, initializationMode="random")
# Evaluate clustering by computing Within Set Sum of Squared Errors
def error(point):
@@ -101,7 +100,6 @@ def error(point):
WSSSE = parsedData.map(lambda point: error(point)).reduce(lambda x, y: x + y)
print("Within Set Sum of Squared Error = " + str(WSSSE))
{% endhighlight %}
+</div>
-Similarly you can use RidgeRegressionWithSGD and LassoWithSGD and compare training Mean Squared
-Errors.
-
+</div>
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-collaborative-filtering.md
----------------------------------------------------------------------
diff --git a/docs/mllib-collaborative-filtering.md b/docs/mllib-collaborative-filtering.md
index 2f1f5f3..79f5e3a 100644
--- a/docs/mllib-collaborative-filtering.md
+++ b/docs/mllib-collaborative-filtering.md
@@ -1,12 +1,12 @@
---
layout: global
-title: MLlib - Collaborative Filtering
+title: <a href="mllib-guide.html">MLlib</a> - Collaborative Filtering
---
* Table of contents
{:toc}
-# Collaborative Filtering
+## Collaborative filtering
[Collaborative filtering](http://en.wikipedia.org/wiki/Recommender_system#Collaborative_filtering)
is commonly used for recommender systems. These techniques aim to fill in the
@@ -14,44 +14,43 @@ missing entries of a user-item association matrix. MLlib currently supports
model-based collaborative filtering, in which users and products are described
by a small set of latent factors that can be used to predict missing entries.
In particular, we implement the [alternating least squares
-(ALS)](http://www2.research.att.com/~volinsky/papers/ieeecomputer.pdf)
+(ALS)](http://dl.acm.org/citation.cfm?id=1608614)
algorithm to learn these latent factors. The implementation in MLlib has the
following parameters:
-* *numBlocks* is the number of blacks used to parallelize computation (set to -1 to auto-configure).
+* *numBlocks* is the number of blocks used to parallelize computation (set to -1 to auto-configure).
* *rank* is the number of latent factors in our model.
* *iterations* is the number of iterations to run.
* *lambda* specifies the regularization parameter in ALS.
-* *implicitPrefs* specifies whether to use the *explicit feedback* ALS variant or one adapted for *implicit feedback* data
-* *alpha* is a parameter applicable to the implicit feedback variant of ALS that governs the *baseline* confidence in preference observations
+* *implicitPrefs* specifies whether to use the *explicit feedback* ALS variant or one adapted for
+ *implicit feedback* data.
+* *alpha* is a parameter applicable to the implicit feedback variant of ALS that governs the
+ *baseline* confidence in preference observations.
-## Explicit vs Implicit Feedback
+### Explicit vs. implicit feedback
The standard approach to matrix factorization based collaborative filtering treats
the entries in the user-item matrix as *explicit* preferences given by the user to the item.
-It is common in many real-world use cases to only have access to *implicit feedback*
-(e.g. views, clicks, purchases, likes, shares etc.). The approach used in MLlib to deal with
-such data is taken from
-[Collaborative Filtering for Implicit Feedback Datasets](http://www2.research.att.com/~yifanhu/PUB/cf.pdf).
-Essentially instead of trying to model the matrix of ratings directly, this approach treats the data as
-a combination of binary preferences and *confidence values*. The ratings are then related
-to the level of confidence in observed user preferences, rather than explicit ratings given to items.
-The model then tries to find latent factors that can be used to predict the expected preference of a user
-for an item.
+It is common in many real-world use cases to only have access to *implicit feedback* (e.g. views,
+clicks, purchases, likes, shares etc.). The approach used in MLlib to deal with such data is taken
+from
+[Collaborative Filtering for Implicit Feedback Datasets](http://dx.doi.org/10.1109/ICDM.2008.22).
+Essentially instead of trying to model the matrix of ratings directly, this approach treats the data
+as a combination of binary preferences and *confidence values*. The ratings are then related to the
+level of confidence in observed user preferences, rather than explicit ratings given to items. The
+model then tries to find latent factors that can be used to predict the expected preference of a
+user for an item.
-Available algorithms for collaborative filtering:
+## Examples
-* [ALS](api/scala/index.html#org.apache.spark.mllib.recommendation.ALS)
-
-
-# Usage in Scala
-
-Following code snippets can be executed in `spark-shell`.
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
In the following example we load rating data. Each row consists of a user, a product and a rating.
-We use the default ALS.train() method which assumes ratings are explicit. We evaluate the recommendation
-model by measuring the Mean Squared Error of rating prediction.
+We use the default [ALS.train()](api/mllib/index.html#org.apache.spark.mllib.recommendation.ALS$)
+method which assumes ratings are explicit. We evaluate the
+recommendation model by measuring the Mean Squared Error of rating prediction.
{% highlight scala %}
import org.apache.spark.mllib.recommendation.ALS
@@ -64,8 +63,9 @@ val ratings = data.map(_.split(',') match {
})
// Build the recommendation model using ALS
+val rank = 10
val numIterations = 20
-val model = ALS.train(ratings, 1, 20, 0.01)
+val model = ALS.train(ratings, rank, numIterations, 0.01)
// Evaluate the model on rating data
val usersProducts = ratings.map{ case Rating(user, product, rate) => (user, product)}
@@ -85,19 +85,19 @@ If the rating matrix is derived from other source of information (i.e., it is in
other signals), you can use the trainImplicit method to get better results.
{% highlight scala %}
-val model = ALS.trainImplicit(ratings, 1, 20, 0.01)
+val alpha = 0.01
+val model = ALS.trainImplicit(ratings, rank, numIterations, alpha)
{% endhighlight %}
+</div>
-# Usage in Java
-
+<div data-lang="java" markdown="1">
All of MLlib's methods use Java-friendly types, so you can import and call them there the same
way you do in Scala. The only caveat is that the methods take Scala RDD objects, while the
Spark Java API uses a separate `JavaRDD` class. You can convert a Java RDD to a Scala one by
calling `.rdd()` on your `JavaRDD` object.
+</div>
-# Usage in Python
-Following examples can be tested in the PySpark shell.
-
+<div data-lang="python" markdown="1">
In the following example we load rating data. Each row consists of a user, a product and a rating.
We use the default ALS.train() method which assumes ratings are explicit. We evaluate the
recommendation by measuring the Mean Squared Error of rating prediction.
@@ -111,7 +111,9 @@ data = sc.textFile("mllib/data/als/test.data")
ratings = data.map(lambda line: array([float(x) for x in line.split(',')]))
# Build the recommendation model using Alternating Least Squares
-model = ALS.train(ratings, 1, 20)
+rank = 10
+numIterations = 20
+model = ALS.train(ratings, rank, numIterations)
# Evaluate the model on training data
testdata = ratings.map(lambda p: (int(p[0]), int(p[1])))
@@ -126,5 +128,13 @@ signals), you can use the trainImplicit method to get better results.
{% highlight python %}
# Build the recommendation model using Alternating Least Squares based on implicit ratings
-model = ALS.trainImplicit(ratings, 1, 20)
+model = ALS.trainImplicit(ratings, rank, numIterations, alpha = 0.01)
{% endhighlight %}
+</div>
+
+</div>
+
+## Tutorial
+
+[AMP Camp](http://ampcamp.berkeley.edu/) provides a hands-on tutorial for
+[personalized movie recommendation with MLlib](http://ampcamp.berkeley.edu/big-data-mini-course/movie-recommendation-with-mllib.html).
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-decision-tree.md
----------------------------------------------------------------------
diff --git a/docs/mllib-decision-tree.md b/docs/mllib-decision-tree.md
new file mode 100644
index 0000000..0693766
--- /dev/null
+++ b/docs/mllib-decision-tree.md
@@ -0,0 +1,185 @@
+---
+layout: global
+title: <a href="mllib-guide.html">MLlib</a> - Decision Tree
+---
+
+* Table of contents
+{:toc}
+
+Decision trees and their ensembles are popular methods for the machine learning tasks of
+classification and regression. Decision trees are widely used since they are easy to interpret,
+handle categorical variables, extend to the multiclass classification setting, do not require
+feature scaling and are able to capture nonlinearities and feature interactions. Tree ensemble
+algorithms such as decision forest and boosting are among the top performers for classification and
+regression tasks.
+
+## Basic algorithm
+
+The decision tree is a greedy algorithm that performs a recursive binary partitioning of the feature
+space by choosing a single element from the *best split set* where each element of the set maximizes
+the information gain at a tree node. In other words, the split chosen at each tree node is chosen
+from the set `$\underset{s}{\operatorname{argmax}} IG(D,s)$` where `$IG(D,s)$` is the information
+gain when a split `$s$` is applied to a dataset `$D$`.
+
+### Node impurity and information gain
+
+The *node impurity* is a measure of the homogeneity of the labels at the node. The current
+implementation provides two impurity measures for classification (Gini impurity and entropy) and one
+impurity measure for regression (variance).
+
+<table class="table">
+ <thead>
+ <tr><th>Impurity</th><th>Task</th><th>Formula</th><th>Description</th></tr>
+ </thead>
+ <tbody>
+ <tr>
+ <td>Gini impurity</td>
+ <td>Classification</td>
+ <td>$\sum_{i=1}^{M} f_i(1-f_i)$</td><td>$f_i$ is the frequency of label $i$ at a node and $M$ is the number of unique labels.</td>
+ </tr>
+ <tr>
+ <td>Entropy</td>
+ <td>Classification</td>
+ <td>$\sum_{i=1}^{M} -f_ilog(f_i)$</td><td>$f_i$ is the frequency of label $i$ at a node and $M$ is the number of unique labels.</td>
+ </tr>
+ <tr>
+ <td>Variance</td>
+ <td>Regression</td>
+ <td>$\frac{1}{n} \sum_{i=1}^{N} (x_i - \mu)^2$</td><td>$y_i$ is label for an instance,
+ $N$ is the number of instances and $\mu$ is the mean given by $\frac{1}{N} \sum_{i=1}^n x_i$.</td>
+ </tr>
+ </tbody>
+</table>
+
+The *information gain* is the difference in the parent node impurity and the weighted sum of the two
+child node impurities. Assuming that a split $s$ partitions the dataset `$D$` of size `$N$` into two
+datasets `$D_{left}$` and `$D_{right}$` of sizes `$N_{left}$` and `$N_{right}$`, respectively:
+
+`$IG(D,s) = Impurity(D) - \frac{N_{left}}{N} Impurity(D_{left}) - \frac{N_{right}}{N} Impurity(D_{right})$`
+
+### Split candidates
+
+**Continuous features**
+
+For small datasets in single machine implementations, the split candidates for each continuous
+feature are typically the unique values for the feature. Some implementations sort the feature
+values and then use the ordered unique values as split candidates for faster tree calculations.
+
+Finding ordered unique feature values is computationally intensive for large distributed
+datasets. One can get an approximate set of split candidates by performing a quantile calculation
+over a sampled fraction of the data. The ordered splits create "bins" and the maximum number of such
+bins can be specified using the `maxBins` parameters.
+
+Note that the number of bins cannot be greater than the number of instances `$N$` (a rare scenario
+since the default `maxBins` value is 100). The tree algorithm automatically reduces the number of
+bins if the condition is not satisfied.
+
+**Categorical features**
+
+For `$M$` categorical features, one could come up with `$2^M-1$` split candidates. However, for
+binary classification, the number of split candidates can be reduced to `$M-1$` by ordering the
+categorical feature values by the proportion of labels falling in one of the two classes (see
+Section 9.2.4 in
+[Elements of Statistical Machine Learning](http://statweb.stanford.edu/~tibs/ElemStatLearn/) for
+details). For example, for a binary classification problem with one categorical feature with three
+categories A, B and C with corresponding proportion of label 1 as 0.2, 0.6 and 0.4, the categorical
+features are orded as A followed by C followed B or A, B, C. The two split candidates are A \| C, B
+and A , B \| C where \| denotes the split.
+
+### Stopping rule
+
+The recursive tree construction is stopped at a node when one of the two conditions is met:
+
+1. The node depth is equal to the `maxDepth` training parammeter
+2. No split candidate leads to an information gain at the node.
+
+### Practical limitations
+
+1. The tree implementation stores an Array[Double] of size *O(#features \* #splits \* 2^maxDepth)*
+ in memory for aggregating histograms over partitions. The current implementation might not scale
+ to very deep trees since the memory requirement grows exponentially with tree depth.
+2. The implemented algorithm reads both sparse and dense data. However, it is not optimized for
+ sparse input.
+3. Python is not supported in this release.
+
+We are planning to solve these problems in the near future. Please drop us a line if you encounter
+any issues.
+
+## Examples
+
+### Classification
+
+The example below demonstrates how to load a CSV file, parse it as an RDD of `LabeledPoint` and then
+perform classification using a decision tree using Gini impurity as an impurity measure and a
+maximum tree depth of 5. The training error is calculated to measure the algorithm accuracy.
+
+<div class="codetabs">
+<div data-lang="scala">
+{% highlight scala %}
+import org.apache.spark.SparkContext
+import org.apache.spark.mllib.tree.DecisionTree
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.linalg.Vectors
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.impurity.Gini
+
+// Load and parse the data file
+val data = sc.textFile("mllib/data/sample_tree_data.csv")
+val parsedData = data.map { line =>
+ val parts = line.split(',').map(_.toDouble)
+ LabeledPoint(parts(0), Vectors.dense(parts.tail))
+}
+
+// Run training algorithm to build the model
+val maxDepth = 5
+val model = DecisionTree.train(parsedData, Classification, Gini, maxDepth)
+
+// Evaluate model on training examples and compute training error
+val labelAndPreds = parsedData.map { point =>
+ val prediction = model.predict(point.features)
+ (point.label, prediction)
+}
+val trainErr = labelAndPreds.filter(r => r._1 != r._2).count.toDouble / parsedData.count
+println("Training Error = " + trainErr)
+{% endhighlight %}
+</div>
+</div>
+
+### Regression
+
+The example below demonstrates how to load a CSV file, parse it as an RDD of `LabeledPoint` and then
+perform regression using a decision tree using variance as an impurity measure and a maximum tree
+depth of 5. The Mean Squared Error (MSE) is computed at the end to evaluate
+[goodness of fit](http://en.wikipedia.org/wiki/Goodness_of_fit).
+
+<div class="codetabs">
+<div data-lang="scala">
+{% highlight scala %}
+import org.apache.spark.SparkContext
+import org.apache.spark.mllib.tree.DecisionTree
+import org.apache.spark.mllib.regression.LabeledPoint
+import org.apache.spark.mllib.linalg.Vectors
+import org.apache.spark.mllib.tree.configuration.Algo._
+import org.apache.spark.mllib.tree.impurity.Variance
+
+// Load and parse the data file
+val data = sc.textFile("mllib/data/sample_tree_data.csv")
+val parsedData = data.map { line =>
+ val parts = line.split(',').map(_.toDouble)
+ LabeledPoint(parts(0), Vectors.dense(parts.tail))
+}
+
+// Run training algorithm to build the model
+val maxDepth = 5
+val model = DecisionTree.train(parsedData, Regression, Variance, maxDepth)
+
+// Evaluate model on training examples and compute training error
+val valuesAndPreds = parsedData.map { point =>
+ val prediction = model.predict(point.features)
+ (point.label, prediction)
+}
+val MSE = valuesAndPreds.map{ case(v, p) => math.pow((v - p), 2)}.reduce(_ + _)/valuesAndPreds.count
+println("training Mean Squared Error = " + MSE)
+{% endhighlight %}
+</div>
+</div>
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-dimensionality-reduction.md
----------------------------------------------------------------------
diff --git a/docs/mllib-dimensionality-reduction.md b/docs/mllib-dimensionality-reduction.md
new file mode 100644
index 0000000..4e9ecf7
--- /dev/null
+++ b/docs/mllib-dimensionality-reduction.md
@@ -0,0 +1,86 @@
+---
+layout: global
+title: <a href="mllib-guide.html">MLlib</a> - Dimensionality Reduction
+---
+
+* Table of contents
+{:toc}
+
+[Dimensionality reduction](http://en.wikipedia.org/wiki/Dimensionality_reduction) is the process
+of reducing the number of variables under consideration.
+It is used to extract latent features from raw and noisy features,
+or compress data while maintaining the structure.
+In this release, we provide preliminary support for dimensionality reduction on tall-and-skinny matrices.
+
+## Singular value decomposition (SVD)
+
+[Singular value decomposition (SVD)](http://en.wikipedia.org/wiki/Singular_value_decomposition)
+factorizes a matrix into three matrices: $U$, $\Sigma$, and $V$ such that
+
+`\[
+A = U \Sigma V^T,
+\]`
+
+where
+
+* $U$ is an orthonormal matrix, whose columns are called left singular vectors,
+* $\Sigma$ is a diagonal matrix with non-negative diagonals in descending order,
+ whose diagonals are called singular values,
+* $V$ is an orthonormal matrix, whose columns are called right singular vectors.
+
+For large matrices, usually we don't need the complete factorization but only the top singular
+values and its associated singular vectors. This can save storage, and more importantly, de-noise
+and recover the low-rank structure of the matrix.
+
+If we keep the top $k$ singular values, then the dimensions of the return will be:
+
+* `$U$`: `$m \times k$`,
+* `$\Sigma$`: `$k \times k$`,
+* `$V$`: `$n \times k$`.
+
+In this release, we provide SVD computation to row-oriented matrices that have only a few columns,
+say, less than $1000$, but many rows, which we call *tall-and-skinny*.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+{% highlight scala %}
+val mat: RowMatrix = ...
+
+// Compute the top 20 singular values and corresponding singular vectors.
+val svd: SingularValueDecomposition[RowMatrix, Matrix] = mat.computeSVD(20, computeU = true)
+val U: RowMatrix = svd.U // The U factor is a RowMatrix.
+val s: Vector = svd.s // The singular values are stored in a local dense vector.
+val V: Matrix = svd.V // The V factor is a local dense matrix.
+{% endhighlight %}
+</div>
+Same code applies to `IndexedRowMatrix`.
+The only difference that the `U` matrix becomes an `IndexedRowMatrix`.
+</div>
+
+## Principal component analysis (PCA)
+
+[Principal component analysis (PCA)](http://en.wikipedia.org/wiki/Principal_component_analysis) is a
+statistical method to find a rotation such that the first coordinate has the largest variance
+possible, and each succeeding coordinate in turn has the largest variance possible. The columns of
+the rotation matrix are called principal components. PCA is used widely in dimensionality reduction.
+
+In this release, we implement PCA for tall-and-skinny matrices stored in row-oriented format.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+The following code demonstrates how to compute principal components on a tall-and-skinny `RowMatrix`
+and use them to project the vectors into a low-dimensional space.
+The number of columns should be small, e.g, less than 1000.
+
+{% highlight scala %}
+val mat: RowMatrix = ...
+
+// Compute the top 10 principal components.
+val pc: Matrix = mat.computePrincipalComponents(10) // Principal components are stored in a local dense matrix.
+
+// Project the rows to the linear space spanned by the top 10 principal components.
+val projected: RowMatrix = mat.multiply(pc)
+{% endhighlight %}
+</div>
+</div>
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-guide.md
----------------------------------------------------------------------
diff --git a/docs/mllib-guide.md b/docs/mllib-guide.md
index 0963a99..c49f857 100644
--- a/docs/mllib-guide.md
+++ b/docs/mllib-guide.md
@@ -3,63 +3,121 @@ layout: global
title: Machine Learning Library (MLlib)
---
+MLlib is a Spark implementation of some common machine learning algorithms and utilities,
+including classification, regression, clustering, collaborative
+filtering, dimensionality reduction, as well as underlying optimization primitives:
-MLlib is a Spark implementation of some common machine learning (ML)
-functionality, as well associated tests and data generators. MLlib
-currently supports four common types of machine learning problem settings,
-namely classification, regression, clustering and collaborative filtering,
-as well as an underlying gradient descent optimization primitive and several
-linear algebra methods.
-
-# Available Methods
-The following links provide a detailed explanation of the methods and usage examples for each of them:
-
-* <a href="mllib-classification-regression.html">Classification and Regression</a>
- * Binary Classification
- * SVM (L1 and L2 regularized)
- * Logistic Regression (L1 and L2 regularized)
- * Linear Regression
- * Least Squares
- * Lasso
- * Ridge Regression
- * Decision Tree (for classification and regression)
-* <a href="mllib-clustering.html">Clustering</a>
- * k-Means
-* <a href="mllib-collaborative-filtering.html">Collaborative Filtering</a>
- * Matrix Factorization using Alternating Least Squares
-* <a href="mllib-optimization.html">Optimization</a>
- * Gradient Descent and Stochastic Gradient Descent
-* <a href="mllib-linear-algebra.html">Linear Algebra</a>
- * Singular Value Decomposition
- * Principal Component Analysis
-
-# Data Types
-
-Most MLlib algorithms operate on RDDs containing vectors. In Java and Scala, the
-[Vector](api/scala/index.html#org.apache.spark.mllib.linalg.Vector) class is used to
-represent vectors. You can create either dense or sparse vectors using the
-[Vectors](api/scala/index.html#org.apache.spark.mllib.linalg.Vectors$) factory.
-
-In Python, MLlib can take the following vector types:
-
-* [NumPy](http://www.numpy.org) arrays
-* Standard Python lists (e.g. `[1, 2, 3]`)
-* The MLlib [SparseVector](api/python/pyspark.mllib.linalg.SparseVector-class.html) class
-* [SciPy sparse matrices](http://docs.scipy.org/doc/scipy/reference/sparse.html)
-
-For efficiency, we recommend using NumPy arrays over lists, and using the
-[CSC format](http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html#scipy.sparse.csc_matrix)
-for SciPy matrices, or MLlib's own SparseVector class.
-
-Several other simple data types are used throughout the library, e.g. the LabeledPoint
-class ([Java/Scala](api/scala/index.html#org.apache.spark.mllib.regression.LabeledPoint),
-[Python](api/python/pyspark.mllib.regression.LabeledPoint-class.html)) for labeled data.
-
-# Dependencies
-MLlib uses the [jblas](https://github.com/mikiobraun/jblas) linear algebra library, which itself
-depends on native Fortran routines. You may need to install the
-[gfortran runtime library](https://github.com/mikiobraun/jblas/wiki/Missing-Libraries)
-if it is not already present on your nodes. MLlib will throw a linking error if it cannot
-detect these libraries automatically.
+* [Basics](mllib-basics.html)
+ * data types
+ * summary statistics
+* Classification and regression
+ * [linear support vector machine (SVM)](mllib-linear-methods.html#linear-support-vector-machine-svm)
+ * [logistic regression](mllib-linear-methods.html#logistic-regression)
+ * [linear least squares, Lasso, and ridge regression](mllib-linear-methods.html#linear-least-squares-lasso-and-ridge-regression)
+ * [decision tree](mllib-decision-tree.html)
+ * [naive Bayes](mllib-naive-bayes.html)
+* [Collaborative filtering](mllib-collaborative-filtering.html)
+ * alternating least squares (ALS)
+* [Clustering](mllib-clustering.html)
+ * k-means
+* [Dimensionality reduction](mllib-dimensionality-reduction.html)
+ * singular value decomposition (SVD)
+ * principal component analysis (PCA)
+* [Optimization](mllib-optimization.html)
+ * stochastic gradient descent
+ * limited-memory BFGS (L-BFGS)
+
+MLlib is currently a *beta* component under active development.
+The APIs may change in the future releases, and we will provide migration guide between releases.
+
+## Dependencies
+
+MLlib uses linear algebra packages [Breeze](http://www.scalanlp.org/), which depends on
+[netlib-java](https://github.com/fommil/netlib-java), and
+[jblas](https://github.com/mikiobraun/jblas).
+`netlib-java` and `jblas` depend on native Fortran routines.
+You need to install the
+[gfortran runtime library](https://github.com/mikiobraun/jblas/wiki/Missing-Libraries) if it is not
+already present on your nodes. MLlib will throw a linking error if it cannot detect these libraries
+automatically. Due to license issues, we do not include `netlib-java`'s native libraries in MLlib's
+dependency set. If no native library is available at runtime, you will see a warning message. To
+use native libraries from `netlib-java`, please include artifact
+`com.github.fommil.netlib:all:1.1.2` as a dependency of your project or build your own (see
+[instructions](https://github.com/fommil/netlib-java/blob/master/README.md#machine-optimised-system-libraries)).
To use MLlib in Python, you will need [NumPy](http://www.numpy.org) version 1.4 or newer.
+
+---
+
+## Migration guide
+
+### From 0.9 to 1.0
+
+In MLlib v1.0, we support both dense and sparse input in a unified way, which introduces a few
+breaking changes. If your data is sparse, please store it in a sparse format instead of dense to
+take advantage of sparsity in both storage and computation.
+
+<div class="codetabs">
+<div data-lang="scala" markdown="1">
+
+We used to represent a feature vector by `Array[Double]`, which is replaced by
+[`Vector`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vector) in v1.0. Algorithms that used
+to accept `RDD[Array[Double]]` now take
+`RDD[Vector]`. [`LabeledPoint`](api/mllib/index.html#org.apache.spark.mllib.regression.LabeledPoint)
+is now a wrapper of `(Double, Vector)` instead of `(Double, Array[Double])`. Converting
+`Array[Double]` to `Vector` is straightforward:
+
+{% highlight scala %}
+import org.apache.spark.mllib.linalg.{Vector, Vectors}
+
+val array: Array[Double] = ... // a double array
+val vector: Vector = Vectors.dense(array) // a dense vector
+{% endhighlight %}
+
+[`Vectors`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vectors$) provides factory methods to create sparse vectors.
+
+*Note*. Scala imports `scala.collection.immutable.Vector` by default, so you have to import `org.apache.spark.mllib.linalg.Vector` explicitly to use MLlib's `Vector`.
+
+</div>
+
+<div data-lang="java" markdown="1">
+
+We used to represent a feature vector by `double[]`, which is replaced by
+[`Vector`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vector) in v1.0. Algorithms that used
+to accept `RDD<double[]>` now take
+`RDD<Vector>`. [`LabeledPoint`](api/mllib/index.html#org.apache.spark.mllib.regression.LabeledPoint)
+is now a wrapper of `(double, Vector)` instead of `(double, double[])`. Converting `double[]` to
+`Vector` is straightforward:
+
+{% highlight java %}
+import org.apache.spark.mllib.linalg.Vector;
+import org.apache.spark.mllib.linalg.Vectors;
+
+double[] array = ... // a double array
+Vector vector = Vectors.dense(array) // a dense vector
+{% endhighlight %}
+
+[`Vectors`](api/mllib/index.html#org.apache.spark.mllib.linalg.Vectors$) provides factory methods to
+create sparse vectors.
+
+</div>
+
+<div data-lang="python" markdown="1">
+
+We used to represent a labeled feature vector in a NumPy array, where the first entry corresponds to
+the label and the rest are features. This representation is replaced by class
+[`LabeledPoint`](api/pyspark/pyspark.mllib.regression.LabeledPoint-class.html), which takes both
+dense and sparse feature vectors.
+
+{% highlight python %}
+from pyspark.mllib.linalg import SparseVector
+from pyspark.mllib.regression import LabeledPoint
+
+# Create a labeled point with a positive label and a dense feature vector.
+pos = LabeledPoint(1.0, [1.0, 0.0, 3.0])
+
+# Create a labeled point with a negative label and a sparse feature vector.
+neg = LabeledPoint(0.0, SparseVector(3, [0, 2], [1.0, 3.0]))
+{% endhighlight %}
+</div>
+</div>
http://git-wip-us.apache.org/repos/asf/spark/blob/26d35f3f/docs/mllib-linear-algebra.md
----------------------------------------------------------------------
diff --git a/docs/mllib-linear-algebra.md b/docs/mllib-linear-algebra.md
deleted file mode 100644
index 09598be..0000000
--- a/docs/mllib-linear-algebra.md
+++ /dev/null
@@ -1,74 +0,0 @@
----
-layout: global
-title: MLlib - Linear Algebra
----
-
-* Table of contents
-{:toc}
-
-
-# Singular Value Decomposition
-Singular Value `Decomposition` for Tall and Skinny matrices.
-Given an `$m \times n$` matrix `$A$`, we can compute matrices `$U,S,V$` such that
-
-`\[
- A = U \cdot S \cdot V^T
- \]`
-
-There is no restriction on m, but we require n^2 doubles to
-fit in memory locally on one machine.
-Further, n should be less than m.
-
-The decomposition is computed by first computing `$A^TA = V S^2 V^T$`,
-computing SVD locally on that (since `$n \times n$` is small),
-from which we recover `$S$` and `$V$`.
-Then we compute U via easy matrix multiplication
-as `$U = A \cdot V \cdot S^{-1}$`.
-
-Only singular vectors associated with largest k singular values
-are recovered. If there are k
-such values, then the dimensions of the return will be:
-
-* `$S$` is `$k \times k$` and diagonal, holding the singular values on diagonal.
-* `$U$` is `$m \times k$` and satisfies `$U^T U = \mathop{eye}(k)$`.
-* `$V$` is `$n \times k$` and satisfies `$V^T V = \mathop{eye}(k)$`.
-
-All input and output is expected in sparse matrix format, 0-indexed
-as tuples of the form ((i,j),value) all in
-SparseMatrix RDDs. Below is example usage.
-
-{% highlight scala %}
-
-import org.apache.spark.SparkContext
-import org.apache.spark.mllib.linalg.SVD
-import org.apache.spark.mllib.linalg.SparseMatrix
-import org.apache.spark.mllib.linalg.MatrixEntry
-
-// Load and parse the data file
-val data = sc.textFile("mllib/data/als/test.data").map { line =>
- val parts = line.split(',')
- MatrixEntry(parts(0).toInt, parts(1).toInt, parts(2).toDouble)
-}
-val m = 4
-val n = 4
-val k = 1
-
-// recover largest singular vector
-val decomposed = SVD.sparseSVD(SparseMatrix(data, m, n), k)
-val = decomposed.S.data
-
-println("singular values = " + s.toArray.mkString)
-{% endhighlight %}
-
-
-# Principal Component Analysis
-
-Computes the top k principal component coefficients for the m-by-n data matrix X.
-Rows of X correspond to observations and columns correspond to variables.
-The coefficient matrix is n-by-k. Each column of the return matrix contains coefficients
-for one principal component, and the columns are in descending
-order of component variance. This function centers the data and uses the
-singular value decomposition (SVD) algorithm.
-
-All input and output is expected in DenseMatrix matrix format. See the examples directory
-under "SparkPCA.scala" for example usage.