You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by ma...@apache.org on 2013/10/09 08:45:08 UTC
[01/10] git commit: Adding algorithm for implicit feedback data to ALS
Updated Branches:
refs/heads/master e67d5b962 -> 3218fa795
Adding algorithm for implicit feedback data to ALS
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/737f01a1
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/737f01a1
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/737f01a1
Branch: refs/heads/master
Commit: 737f01a1ef49e4a12f24799c4324b3a60712758e
Parents: a106ed8
Author: Nick Pentreath <ni...@gmail.com>
Authored: Fri Sep 6 14:45:05 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Fri Sep 6 14:45:05 2013 +0200
----------------------------------------------------------------------
.../apache/spark/mllib/recommendation/ALS.scala | 202 ++++++++++++++++---
.../mllib/recommendation/JavaALSSuite.java | 77 +++++--
.../spark/mllib/recommendation/ALSSuite.scala | 71 +++++--
3 files changed, 296 insertions(+), 54 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/737f01a1/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
----------------------------------------------------------------------
diff --git a/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala b/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
index be002d0..00b46ae 100644
--- a/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
+++ b/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
@@ -21,7 +21,8 @@ import scala.collection.mutable.{ArrayBuffer, BitSet}
import scala.util.Random
import scala.util.Sorting
-import org.apache.spark.{HashPartitioner, Partitioner, SparkContext}
+import org.apache.spark.broadcast.Broadcast
+import org.apache.spark.{Logging, HashPartitioner, Partitioner, SparkContext}
import org.apache.spark.storage.StorageLevel
import org.apache.spark.rdd.RDD
import org.apache.spark.serializer.KryoRegistrator
@@ -61,6 +62,12 @@ case class Rating(val user: Int, val product: Int, val rating: Double)
/**
* Alternating Least Squares matrix factorization.
*
+ * ALS attempts to estimate the ratings matrix `R` as the product of two lower-rank matrices,
+ * `X` and `Y`, i.e. `Xt * Y = R`. Typically these approximations are called 'factor' matrices.
+ * The general approach is iterative. During each iteration, one of the factor matrices is held
+ * constant, while the other is solved for using least squares. The newly-solved factor matrix is
+ * then held constant while solving for the other factor matrix.
+ *
* This is a blocked implementation of the ALS factorization algorithm that groups the two sets
* of factors (referred to as "users" and "products") into blocks and reduces communication by only
* sending one copy of each user vector to each product block on each iteration, and only for the
@@ -70,11 +77,21 @@ case class Rating(val user: Int, val product: Int, val rating: Double)
* vectors it receives from each user block it will depend on). This allows us to send only an
* array of feature vectors between each user block and product block, and have the product block
* find the users' ratings and update the products based on these messages.
+ *
+ * For implicit preference data, the algorithm used is based on
+ * "Collaborative Filtering for Implicit Feedback Datasets", available at
+ * [[http://research.yahoo.com/pub/2433]], adapted for the blocked approach used here.
+ *
+ * Essentially instead of finding the low-rank approximations to the rating matrix `R`,
+ * this finds the approximations for a preference matrix `P` where the elements of `P` are 1 if r > 0
+ * and 0 if r = 0. The ratings then act as 'confidence' values related to strength of indicated user
+ * preferences rather than explicit ratings given to items.
*/
-class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var lambda: Double)
- extends Serializable
+class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var lambda: Double,
+ var implicitPrefs: Boolean, var alpha: Double)
+ extends Serializable with Logging
{
- def this() = this(-1, 10, 10, 0.01)
+ def this() = this(-1, 10, 10, 0.01, false, 1.0)
/**
* Set the number of blocks to parallelize the computation into; pass -1 for an auto-configured
@@ -103,6 +120,16 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
this
}
+ def setImplicitPrefs(implicitPrefs: Boolean): ALS = {
+ this.implicitPrefs = implicitPrefs
+ this
+ }
+
+ def setAlpha(alpha: Double): ALS = {
+ this.alpha = alpha
+ this
+ }
+
/**
* Run ALS with the configured parameters on an input RDD of (user, product, rating) triples.
* Returns a MatrixFactorizationModel with feature vectors for each user and product.
@@ -147,19 +174,24 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
}
}
- for (iter <- 0 until iterations) {
+ for (iter <- 1 to iterations) {
// perform ALS update
- products = updateFeatures(users, userOutLinks, productInLinks, partitioner, rank, lambda)
- users = updateFeatures(products, productOutLinks, userInLinks, partitioner, rank, lambda)
+ logInfo("Re-computing I given U (Iteration %d/%d)".format(iter, iterations))
+ // YtY / XtX is an Option[DoubleMatrix] and is only required for the implicit feedback model
+ val YtY = computeYtY(users)
+ val YtYb = ratings.context.broadcast(YtY)
+ products = updateFeatures(users, userOutLinks, productInLinks, partitioner, rank, lambda,
+ alpha, YtYb)
+ logInfo("Re-computing U given I (Iteration %d/%d)".format(iter, iterations))
+ val XtX = computeYtY(products)
+ val XtXb = ratings.context.broadcast(XtX)
+ users = updateFeatures(products, productOutLinks, userInLinks, partitioner, rank, lambda,
+ alpha, XtXb)
}
// Flatten and cache the two final RDDs to un-block them
- val usersOut = users.join(userOutLinks).flatMap { case (b, (factors, outLinkBlock)) =>
- for (i <- 0 until factors.length) yield (outLinkBlock.elementIds(i), factors(i))
- }
- val productsOut = products.join(productOutLinks).flatMap { case (b, (factors, outLinkBlock)) =>
- for (i <- 0 until factors.length) yield (outLinkBlock.elementIds(i), factors(i))
- }
+ val usersOut = unblockFactors(users, userOutLinks)
+ val productsOut = unblockFactors(products, productOutLinks)
usersOut.persist()
productsOut.persist()
@@ -168,6 +200,41 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
}
/**
+ * Computes the (`rank x rank`) matrix `YtY`, where `Y` is the (`nui x rank`) matrix of factors
+ * for each user (or product), in a distributed fashion. Here `reduceByKeyLocally` is used as
+ * the driver program requires `YtY` to broadcast it to the slaves
+ * @param factors the (block-distributed) user or product factor vectors
+ * @return Option[YtY] - whose value is only used in the implicit preference model
+ */
+ def computeYtY(factors: RDD[(Int, Array[Array[Double]])]) = {
+ implicitPrefs match {
+ case true => {
+ Option(
+ factors.flatMapValues{ case factorArray =>
+ factorArray.map{ vector =>
+ val x = new DoubleMatrix(vector)
+ x.mmul(x.transpose())
+ }
+ }.reduceByKeyLocally((a, b) => a.addi(b))
+ .values
+ .reduce((a, b) => a.addi(b))
+ )
+ }
+ case false => None
+ }
+ }
+
+ /**
+ * Flatten out blocked user or product factors into an RDD of (id, factor vector) pairs
+ */
+ def unblockFactors(blockedFactors: RDD[(Int, Array[Array[Double]])],
+ outLinks: RDD[(Int, OutLinkBlock)]) = {
+ blockedFactors.join(outLinks).flatMap{ case (b, (factors, outLinkBlock)) =>
+ for (i <- 0 until factors.length) yield (outLinkBlock.elementIds(i), factors(i))
+ }
+ }
+
+ /**
* Make the out-links table for a block of the users (or products) dataset given the list of
* (user, product, rating) values for the users in that block (or the opposite for products).
*/
@@ -251,7 +318,9 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
userInLinks: RDD[(Int, InLinkBlock)],
partitioner: Partitioner,
rank: Int,
- lambda: Double)
+ lambda: Double,
+ alpha: Double,
+ YtY: Broadcast[Option[DoubleMatrix]])
: RDD[(Int, Array[Array[Double]])] =
{
val numBlocks = products.partitions.size
@@ -265,7 +334,9 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
toSend.zipWithIndex.map{ case (buf, idx) => (idx, (bid, buf.toArray)) }
}.groupByKey(partitioner)
.join(userInLinks)
- .mapValues{ case (messages, inLinkBlock) => updateBlock(messages, inLinkBlock, rank, lambda) }
+ .mapValues{ case (messages, inLinkBlock) =>
+ updateBlock(messages, inLinkBlock, rank, lambda, alpha, YtY)
+ }
}
/**
@@ -273,7 +344,7 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
* it received from each product and its InLinkBlock.
*/
def updateBlock(messages: Seq[(Int, Array[Array[Double]])], inLinkBlock: InLinkBlock,
- rank: Int, lambda: Double)
+ rank: Int, lambda: Double, alpha: Double, YtY: Broadcast[Option[DoubleMatrix]])
: Array[Array[Double]] =
{
// Sort the incoming block factor messages by block ID and make them an array
@@ -298,8 +369,14 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
fillXtX(x, tempXtX)
val (us, rs) = inLinkBlock.ratingsForBlock(productBlock)(p)
for (i <- 0 until us.length) {
- userXtX(us(i)).addi(tempXtX)
- SimpleBlas.axpy(rs(i), x, userXy(us(i)))
+ implicitPrefs match {
+ case false =>
+ userXtX(us(i)).addi(tempXtX)
+ SimpleBlas.axpy(rs(i), x, userXy(us(i)))
+ case true =>
+ userXtX(us(i)).addi(tempXtX.mul(alpha * rs(i)))
+ SimpleBlas.axpy(1 + alpha * rs(i), x, userXy(us(i)))
+ }
}
}
}
@@ -311,7 +388,10 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
// Add regularization
(0 until rank).foreach(i => fullXtX.data(i*rank + i) += lambda)
// Solve the resulting matrix, which is symmetric and positive-definite
- Solve.solvePositive(fullXtX, userXy(index)).data
+ implicitPrefs match {
+ case false => Solve.solvePositive(fullXtX, userXy(index)).data
+ case true => Solve.solvePositive(fullXtX.add(YtY.value.get), userXy(index)).data
+ }
}
}
@@ -381,7 +461,7 @@ object ALS {
blocks: Int)
: MatrixFactorizationModel =
{
- new ALS(blocks, rank, iterations, lambda).run(ratings)
+ new ALS(blocks, rank, iterations, lambda, false, 1.0).run(ratings)
}
/**
@@ -419,6 +499,68 @@ object ALS {
train(ratings, rank, iterations, 0.01, -1)
}
+ /**
+ * Train a matrix factorization model given an RDD of 'implicit preferences' given by users
+ * to some products, in the form of (userID, productID, preference) pairs. We approximate the
+ * ratings matrix as the product of two lower-rank matrices of a given rank (number of features).
+ * To solve for these features, we run a given number of iterations of ALS. This is done using
+ * a level of parallelism given by `blocks`.
+ *
+ * @param ratings RDD of (userID, productID, rating) pairs
+ * @param rank number of features to use
+ * @param iterations number of iterations of ALS (recommended: 10-20)
+ * @param lambda regularization factor (recommended: 0.01)
+ * @param blocks level of parallelism to split computation into
+ * @param alpha confidence parameter (only applies when immplicitPrefs = true)
+ */
+ def trainImplicit(
+ ratings: RDD[Rating],
+ rank: Int,
+ iterations: Int,
+ lambda: Double,
+ blocks: Int,
+ alpha: Double)
+ : MatrixFactorizationModel =
+ {
+ new ALS(blocks, rank, iterations, lambda, true, alpha).run(ratings)
+ }
+
+ /**
+ * Train a matrix factorization model given an RDD of 'implicit preferences' given by users to
+ * some products, in the form of (userID, productID, preference) pairs. We approximate the
+ * ratings matrix as the product of two lower-rank matrices of a given rank (number of features).
+ * To solve for these features, we run a given number of iterations of ALS. The level of
+ * parallelism is determined automatically based on the number of partitions in `ratings`.
+ *
+ * @param ratings RDD of (userID, productID, rating) pairs
+ * @param rank number of features to use
+ * @param iterations number of iterations of ALS (recommended: 10-20)
+ * @param lambda regularization factor (recommended: 0.01)
+ */
+ def trainImplicit(ratings: RDD[Rating], rank: Int, iterations: Int, lambda: Double, alpha: Double)
+ : MatrixFactorizationModel =
+ {
+ trainImplicit(ratings, rank, iterations, lambda, -1, alpha)
+ }
+
+ /**
+ * Train a matrix factorization model given an RDD of 'implicit preferences' ratings given by
+ * users to some products, in the form of (userID, productID, rating) pairs. We approximate the
+ * ratings matrix as the product of two lower-rank matrices of a given rank (number of features).
+ * To solve for these features, we run a given number of iterations of ALS. The level of
+ * parallelism is determined automatically based on the number of partitions in `ratings`.
+ * Model parameters `alpha` and `lambda` are set to reasonable default values
+ *
+ * @param ratings RDD of (userID, productID, rating) pairs
+ * @param rank number of features to use
+ * @param iterations number of iterations of ALS (recommended: 10-20)
+ */
+ def trainImplicit(ratings: RDD[Rating], rank: Int, iterations: Int)
+ : MatrixFactorizationModel =
+ {
+ trainImplicit(ratings, rank, iterations, 0.01, -1, 1.0)
+ }
+
private class ALSRegistrator extends KryoRegistrator {
override def registerClasses(kryo: Kryo) {
kryo.register(classOf[Rating])
@@ -426,29 +568,37 @@ object ALS {
}
def main(args: Array[String]) {
- if (args.length != 5 && args.length != 6) {
- println("Usage: ALS <master> <ratings_file> <rank> <iterations> <output_dir> [<blocks>]")
+ if (args.length < 5 || args.length > 9) {
+ println("Usage: ALS <master> <ratings_file> <rank> <iterations> <output_dir> " +
+ "[<lambda>] [<implicitPrefs>] [<alpha>] [<blocks>]")
System.exit(1)
}
val (master, ratingsFile, rank, iters, outputDir) =
(args(0), args(1), args(2).toInt, args(3).toInt, args(4))
- val blocks = if (args.length == 6) args(5).toInt else -1
+ val lambda = if (args.length >= 6) args(5).toDouble else 0.01
+ val implicitPrefs = if (args.length >= 7) args(6).toBoolean else false
+ val alpha = if (args.length >= 8) args(7).toDouble else 1
+ val blocks = if (args.length == 9) args(8).toInt else -1
+
System.setProperty("spark.serializer", "org.apache.spark.serializer.KryoSerializer")
System.setProperty("spark.kryo.registrator", classOf[ALSRegistrator].getName)
System.setProperty("spark.kryo.referenceTracking", "false")
System.setProperty("spark.kryoserializer.buffer.mb", "8")
System.setProperty("spark.locality.wait", "10000")
+
val sc = new SparkContext(master, "ALS")
val ratings = sc.textFile(ratingsFile).map { line =>
- val fields = line.split(',')
+ val fields = line.split("\\D{2}|\\s|,")
Rating(fields(0).toInt, fields(1).toInt, fields(2).toDouble)
}
- val model = ALS.train(ratings, rank, iters, 0.01, blocks)
+ val model = new ALS(rank = rank, iterations = iters, lambda = lambda,
+ numBlocks = blocks, implicitPrefs = implicitPrefs, alpha = alpha).run(ratings)
+
model.userFeatures.map{ case (id, vec) => id + "," + vec.mkString(" ") }
.saveAsTextFile(outputDir + "/userFeatures")
model.productFeatures.map{ case (id, vec) => id + "," + vec.mkString(" ") }
.saveAsTextFile(outputDir + "/productFeatures")
println("Final user/product features written to " + outputDir)
- System.exit(0)
+ sc.stop()
}
}
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/737f01a1/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
----------------------------------------------------------------------
diff --git a/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java b/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
index 3323f6c..ec545ef 100644
--- a/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
+++ b/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
@@ -19,6 +19,7 @@ package org.apache.spark.mllib.recommendation;
import java.io.Serializable;
import java.util.List;
+import java.lang.Math;
import scala.Tuple2;
@@ -48,7 +49,7 @@ public class JavaALSSuite implements Serializable {
}
void validatePrediction(MatrixFactorizationModel model, int users, int products, int features,
- DoubleMatrix trueRatings, double matchThreshold) {
+ DoubleMatrix trueRatings, double matchThreshold, boolean implicitPrefs, DoubleMatrix truePrefs) {
DoubleMatrix predictedU = new DoubleMatrix(users, features);
List<scala.Tuple2<Object, double[]>> userFeatures = model.userFeatures().toJavaRDD().collect();
for (int i = 0; i < features; ++i) {
@@ -68,12 +69,32 @@ public class JavaALSSuite implements Serializable {
DoubleMatrix predictedRatings = predictedU.mmul(predictedP.transpose());
- for (int u = 0; u < users; ++u) {
- for (int p = 0; p < products; ++p) {
- double prediction = predictedRatings.get(u, p);
- double correct = trueRatings.get(u, p);
- Assert.assertTrue(Math.abs(prediction - correct) < matchThreshold);
+ if (!implicitPrefs) {
+ for (int u = 0; u < users; ++u) {
+ for (int p = 0; p < products; ++p) {
+ double prediction = predictedRatings.get(u, p);
+ double correct = trueRatings.get(u, p);
+ Assert.assertTrue(String.format("Prediction=%2.4f not below match threshold of %2.2f",
+ prediction, matchThreshold), Math.abs(prediction - correct) < matchThreshold);
+ }
}
+ } else {
+ // For implicit prefs we use the confidence-weighted RMSE to test (ref Mahout's implicit ALS tests)
+ double sqErr = 0.0;
+ double denom = 0.0;
+ for (int u = 0; u < users; ++u) {
+ for (int p = 0; p < products; ++p) {
+ double prediction = predictedRatings.get(u, p);
+ double truePref = truePrefs.get(u, p);
+ double confidence = 1.0 + /* alpha = */ 1.0 * trueRatings.get(u, p);
+ double err = confidence * (truePref - prediction) * (truePref - prediction);
+ sqErr += err;
+ denom += 1.0;
+ }
+ }
+ double rmse = Math.sqrt(sqErr / denom);
+ Assert.assertTrue(String.format("Confidence-weighted RMSE=%2.4f above threshold of %2.2f",
+ rmse, matchThreshold), Math.abs(rmse) < matchThreshold);
}
}
@@ -83,12 +104,12 @@ public class JavaALSSuite implements Serializable {
int iterations = 15;
int users = 10;
int products = 10;
- scala.Tuple2<List<Rating>, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
- users, products, features, 0.7);
+ scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
+ users, products, features, 0.7, false);
JavaRDD<Rating> data = sc.parallelize(testData._1());
MatrixFactorizationModel model = ALS.train(data.rdd(), features, iterations);
- validatePrediction(model, users, products, features, testData._2(), 0.3);
+ validatePrediction(model, users, products, features, testData._2(), 0.3, false, testData._3());
}
@Test
@@ -97,14 +118,46 @@ public class JavaALSSuite implements Serializable {
int iterations = 15;
int users = 20;
int products = 30;
- scala.Tuple2<List<Rating>, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
- users, products, features, 0.7);
+ scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
+ users, products, features, 0.7, false);
JavaRDD<Rating> data = sc.parallelize(testData._1());
MatrixFactorizationModel model = new ALS().setRank(features)
.setIterations(iterations)
.run(data.rdd());
- validatePrediction(model, users, products, features, testData._2(), 0.3);
+ validatePrediction(model, users, products, features, testData._2(), 0.3, false, testData._3());
+ }
+
+ @Test
+ public void runImplicitALSUsingStaticMethods() {
+ int features = 1;
+ int iterations = 15;
+ int users = 40;
+ int products = 80;
+ scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
+ users, products, features, 0.7, true);
+
+ JavaRDD<Rating> data = sc.parallelize(testData._1());
+ MatrixFactorizationModel model = ALS.trainImplicit(data.rdd(), features, iterations);
+ validatePrediction(model, users, products, features, testData._2(), 0.4, true, testData._3());
+ }
+
+ @Test
+ public void runImplicitALSUsingConstructor() {
+ int features = 2;
+ int iterations = 15;
+ int users = 50;
+ int products = 100;
+ scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
+ users, products, features, 0.7, true);
+
+ JavaRDD<Rating> data = sc.parallelize(testData._1());
+
+ MatrixFactorizationModel model = new ALS().setRank(features)
+ .setIterations(iterations)
+ .setImplicitPrefs(true)
+ .run(data.rdd());
+ validatePrediction(model, users, products, features, testData._2(), 0.4, true, testData._3());
}
}
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/737f01a1/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
----------------------------------------------------------------------
diff --git a/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala b/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
index 347ef23..1ab181d 100644
--- a/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
+++ b/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
@@ -34,16 +34,19 @@ object ALSSuite {
users: Int,
products: Int,
features: Int,
- samplingRate: Double): (java.util.List[Rating], DoubleMatrix) = {
- val (sampledRatings, trueRatings) = generateRatings(users, products, features, samplingRate)
- (seqAsJavaList(sampledRatings), trueRatings)
+ samplingRate: Double,
+ implicitPrefs: Boolean): (java.util.List[Rating], DoubleMatrix, DoubleMatrix) = {
+ val (sampledRatings, trueRatings, truePrefs) =
+ generateRatings(users, products, features, samplingRate, implicitPrefs)
+ (seqAsJavaList(sampledRatings), trueRatings, truePrefs)
}
def generateRatings(
users: Int,
products: Int,
features: Int,
- samplingRate: Double): (Seq[Rating], DoubleMatrix) = {
+ samplingRate: Double,
+ implicitPrefs: Boolean = false): (Seq[Rating], DoubleMatrix, DoubleMatrix) = {
val rand = new Random(42)
// Create a random matrix with uniform values from -1 to 1
@@ -52,14 +55,20 @@ object ALSSuite {
val userMatrix = randomMatrix(users, features)
val productMatrix = randomMatrix(features, products)
- val trueRatings = userMatrix.mmul(productMatrix)
+ val (trueRatings, truePrefs) = implicitPrefs match {
+ case true =>
+ val raw = new DoubleMatrix(users, products, Array.fill(users * products)(rand.nextInt(10).toDouble): _*)
+ val prefs = new DoubleMatrix(users, products, raw.data.map(v => if (v > 0) 1.0 else 0.0): _*)
+ (raw, prefs)
+ case false => (userMatrix.mmul(productMatrix), null)
+ }
val sampledRatings = {
for (u <- 0 until users; p <- 0 until products if rand.nextDouble() < samplingRate)
yield Rating(u, p, trueRatings.get(u, p))
}
- (sampledRatings, trueRatings)
+ (sampledRatings, trueRatings, truePrefs)
}
}
@@ -85,6 +94,14 @@ class ALSSuite extends FunSuite with BeforeAndAfterAll {
testALS(20, 30, 2, 15, 0.7, 0.3)
}
+ test("rank-1 matrices implicit") {
+ testALS(40, 80, 1, 15, 0.7, 0.4, true)
+ }
+
+ test("rank-2 matrices implicit") {
+ testALS(50, 100, 2, 15, 0.7, 0.4, true)
+ }
+
/**
* Test if we can correctly factorize R = U * P where U and P are of known rank.
*
@@ -96,11 +113,14 @@ class ALSSuite extends FunSuite with BeforeAndAfterAll {
* @param matchThreshold max difference allowed to consider a predicted rating correct
*/
def testALS(users: Int, products: Int, features: Int, iterations: Int,
- samplingRate: Double, matchThreshold: Double)
+ samplingRate: Double, matchThreshold: Double, implicitPrefs: Boolean = false)
{
- val (sampledRatings, trueRatings) = ALSSuite.generateRatings(users, products,
- features, samplingRate)
- val model = ALS.train(sc.parallelize(sampledRatings), features, iterations)
+ val (sampledRatings, trueRatings, truePrefs) = ALSSuite.generateRatings(users, products,
+ features, samplingRate, implicitPrefs)
+ val model = implicitPrefs match {
+ case false => ALS.train(sc.parallelize(sampledRatings), features, iterations)
+ case true => ALS.trainImplicit(sc.parallelize(sampledRatings), features, iterations)
+ }
val predictedU = new DoubleMatrix(users, features)
for ((u, vec) <- model.userFeatures.collect(); i <- 0 until features) {
@@ -112,12 +132,31 @@ class ALSSuite extends FunSuite with BeforeAndAfterAll {
}
val predictedRatings = predictedU.mmul(predictedP.transpose)
- for (u <- 0 until users; p <- 0 until products) {
- val prediction = predictedRatings.get(u, p)
- val correct = trueRatings.get(u, p)
- if (math.abs(prediction - correct) > matchThreshold) {
- fail("Model failed to predict (%d, %d): %f vs %f\ncorr: %s\npred: %s\nU: %s\n P: %s".format(
- u, p, correct, prediction, trueRatings, predictedRatings, predictedU, predictedP))
+ if (!implicitPrefs) {
+ for (u <- 0 until users; p <- 0 until products) {
+ val prediction = predictedRatings.get(u, p)
+ val correct = trueRatings.get(u, p)
+ if (math.abs(prediction - correct) > matchThreshold) {
+ fail("Model failed to predict (%d, %d): %f vs %f\ncorr: %s\npred: %s\nU: %s\n P: %s".format(
+ u, p, correct, prediction, trueRatings, predictedRatings, predictedU, predictedP))
+ }
+ }
+ } else {
+ // For implicit prefs we use the confidence-weighted RMSE to test (ref Mahout's tests)
+ var sqErr = 0.0
+ var denom = 0.0
+ for (u <- 0 until users; p <- 0 until products) {
+ val prediction = predictedRatings.get(u, p)
+ val truePref = truePrefs.get(u, p)
+ val confidence = 1 + 1.0 * trueRatings.get(u, p)
+ val err = confidence * (truePref - prediction) * (truePref - prediction)
+ sqErr += err
+ denom += 1
+ }
+ val rmse = math.sqrt(sqErr / denom)
+ if (math.abs(rmse) > matchThreshold) {
+ fail("Model failed to predict RMSE: %f\ncorr: %s\npred: %s\nU: %s\n P: %s".format(
+ rmse, truePrefs, predictedRatings, predictedU, predictedP))
}
}
}
[03/10] git commit: Merge remote-tracking branch 'upstream/master'
into implicit-als
Posted by ma...@apache.org.
Merge remote-tracking branch 'upstream/master' into implicit-als
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/1cbdcb9c
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/1cbdcb9c
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/1cbdcb9c
Branch: refs/heads/master
Commit: 1cbdcb9cb6cbfea2831db01e2a109c10f8bd30ae
Parents: d952f04 232765f
Author: Nick Pentreath <ni...@gmail.com>
Authored: Fri Oct 4 13:25:34 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Fri Oct 4 13:25:34 2013 +0200
----------------------------------------------------------------------
assembly/pom.xml | 2 +-
bagel/pom.xml | 2 +-
core/pom.xml | 2 +-
.../scala/org/apache/spark/SparkContext.scala | 13 +-
.../scala/org/apache/spark/TaskEndReason.scala | 8 +-
.../org/apache/spark/api/java/JavaRDDLike.scala | 10 +
.../org/apache/spark/executor/Executor.scala | 26 +-
.../main/scala/org/apache/spark/rdd/RDD.scala | 38 +-
.../apache/spark/scheduler/DAGScheduler.scala | 6 +-
.../spark/scheduler/DAGSchedulerEvent.scala | 1 -
.../org/apache/spark/scheduler/JobLogger.scala | 1 -
.../scala/org/apache/spark/scheduler/Pool.scala | 121 +++++++
.../apache/spark/scheduler/Schedulable.scala | 46 +++
.../spark/scheduler/SchedulableBuilder.scala | 150 ++++++++
.../spark/scheduler/SchedulingAlgorithm.scala | 81 +++++
.../apache/spark/scheduler/SchedulingMode.scala | 29 ++
.../apache/spark/scheduler/SparkListener.scala | 1 -
.../org/apache/spark/scheduler/StageInfo.scala | 2 +-
.../spark/scheduler/TaskDescription.scala | 37 ++
.../org/apache/spark/scheduler/TaskInfo.scala | 72 ++++
.../apache/spark/scheduler/TaskLocality.scala | 32 ++
.../org/apache/spark/scheduler/TaskResult.scala | 15 +-
.../apache/spark/scheduler/TaskScheduler.scala | 5 +-
.../spark/scheduler/TaskSchedulerListener.scala | 1 -
.../apache/spark/scheduler/TaskSetManager.scala | 48 +++
.../scheduler/cluster/ClusterScheduler.scala | 57 ++-
.../cluster/ClusterTaskSetManager.scala | 169 ++++-----
.../apache/spark/scheduler/cluster/Pool.scala | 121 -------
.../spark/scheduler/cluster/Schedulable.scala | 48 ---
.../scheduler/cluster/SchedulableBuilder.scala | 137 --------
.../scheduler/cluster/SchedulingAlgorithm.scala | 81 -----
.../scheduler/cluster/SchedulingMode.scala | 29 --
.../cluster/StandaloneClusterMessage.scala | 1 +
.../cluster/StandaloneSchedulerBackend.scala | 1 +
.../scheduler/cluster/TaskDescription.scala | 37 --
.../spark/scheduler/cluster/TaskInfo.scala | 72 ----
.../spark/scheduler/cluster/TaskLocality.scala | 32 --
.../scheduler/cluster/TaskResultGetter.scala | 124 +++++++
.../scheduler/cluster/TaskSetManager.scala | 51 ---
.../mesos/CoarseMesosSchedulerBackend.scala | 286 +++++++++++++++
.../cluster/mesos/MesosSchedulerBackend.scala | 345 +++++++++++++++++++
.../spark/scheduler/local/LocalScheduler.scala | 8 +-
.../scheduler/local/LocalTaskSetManager.scala | 21 +-
.../mesos/CoarseMesosSchedulerBackend.scala | 286 ---------------
.../scheduler/mesos/MesosSchedulerBackend.scala | 343 ------------------
.../org/apache/spark/storage/BlockManager.scala | 27 +-
.../org/apache/spark/storage/MemoryStore.scala | 14 +-
.../apache/spark/ui/UIWorkloadGenerator.scala | 2 +-
.../org/apache/spark/ui/exec/ExecutorsUI.scala | 2 +-
.../org/apache/spark/ui/jobs/IndexPage.scala | 2 +-
.../spark/ui/jobs/JobProgressListener.scala | 4 +-
.../apache/spark/ui/jobs/JobProgressUI.scala | 4 +-
.../org/apache/spark/ui/jobs/PoolTable.scala | 3 +-
.../org/apache/spark/ui/jobs/StagePage.scala | 6 +-
.../org/apache/spark/ui/jobs/StageTable.scala | 3 +-
.../org/apache/spark/DistributedSuite.scala | 13 -
.../org/apache/spark/LocalSparkContext.scala | 10 +-
.../org/apache/spark/SharedSparkContext.scala | 6 +-
.../scala/org/apache/spark/ThreadingSuite.scala | 45 ++-
.../scala/org/apache/spark/rdd/RDDSuite.scala | 39 ++-
.../spark/scheduler/DAGSchedulerSuite.scala | 4 +-
.../cluster/ClusterSchedulerSuite.scala | 15 +-
.../cluster/ClusterTaskSetManagerSuite.scala | 58 +++-
.../cluster/TaskResultGetterSuite.scala | 113 ++++++
docs/_config.yml | 4 +-
docs/running-on-yarn.md | 1 +
ec2/README | 2 +-
ec2/spark_ec2.py | 106 ++++--
examples/pom.xml | 2 +-
make-distribution.sh | 2 +-
mllib/pom.xml | 2 +-
pom.xml | 3 +-
project/SparkBuild.scala | 7 +-
python/pyspark/shell.py | 2 +-
repl-bin/pom.xml | 2 +-
repl/pom.xml | 2 +-
.../org/apache/spark/repl/SparkILoop.scala | 2 +-
spark-class | 12 +-
streaming/pom.xml | 2 +-
tools/pom.xml | 2 +-
yarn/pom.xml | 2 +-
.../org/apache/spark/deploy/yarn/Client.scala | 7 +-
.../spark/deploy/yarn/ClientArguments.scala | 6 +
.../spark/deploy/yarn/WorkerRunnable.scala | 5 +-
84 files changed, 2026 insertions(+), 1515 deletions(-)
----------------------------------------------------------------------
[04/10] git commit: Reverting to using comma-delimited split
Posted by ma...@apache.org.
Reverting to using comma-delimited split
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/0bd9b373
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/0bd9b373
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/0bd9b373
Branch: refs/heads/master
Commit: 0bd9b373d1d37a3df7a504098abcbd7421cf7477
Parents: 1cbdcb9
Author: Nick Pentreath <ni...@gmail.com>
Authored: Fri Oct 4 13:30:33 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Fri Oct 4 13:30:33 2013 +0200
----------------------------------------------------------------------
.../src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/0bd9b373/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
----------------------------------------------------------------------
diff --git a/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala b/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
index 00b46ae..5935d27 100644
--- a/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
+++ b/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
@@ -588,7 +588,7 @@ object ALS {
val sc = new SparkContext(master, "ALS")
val ratings = sc.textFile(ratingsFile).map { line =>
- val fields = line.split("\\D{2}|\\s|,")
+ val fields = line.split(',')
Rating(fields(0).toInt, fields(1).toInt, fields(2).toDouble)
}
val model = new ALS(rank = rank, iterations = iters, lambda = lambda,
[07/10] git commit: Adding implicit feedback ALS to MLlib user guide
Posted by ma...@apache.org.
Adding implicit feedback ALS to MLlib user guide
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/93b96b44
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/93b96b44
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/93b96b44
Branch: refs/heads/master
Commit: 93b96b44d778716a4e76bdcf68d6a07694a06460
Parents: c6ceaea
Author: Nick Pentreath <ni...@gmail.com>
Authored: Fri Oct 4 14:39:44 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Fri Oct 4 14:39:44 2013 +0200
----------------------------------------------------------------------
docs/mllib-guide.md | 24 ++++++++++++++++++++----
1 file changed, 20 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/93b96b44/docs/mllib-guide.md
----------------------------------------------------------------------
diff --git a/docs/mllib-guide.md b/docs/mllib-guide.md
index f991d86..c1ff9c4 100644
--- a/docs/mllib-guide.md
+++ b/docs/mllib-guide.md
@@ -144,10 +144,9 @@ Available algorithms for clustering:
# Collaborative Filtering
-[Collaborative
-filtering](http://en.wikipedia.org/wiki/Recommender_system#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
-missing entries of a user-product association matrix. MLlib currently supports
+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
@@ -158,7 +157,24 @@ following parameters:
* *numBlocks* is the number of blacks 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.
+* *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
+
+## 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://research.yahoo.com/pub/2433).
+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:
[05/10] git commit: Fixing closing brace indentation
Posted by ma...@apache.org.
Fixing closing brace indentation
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/6a7836cd
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/6a7836cd
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/6a7836cd
Branch: refs/heads/master
Commit: 6a7836cddcf3ae0322e76cd5f79f6dd9ea73a09c
Parents: 0bd9b37
Author: Nick Pentreath <ni...@gmail.com>
Authored: Fri Oct 4 13:33:01 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Fri Oct 4 13:33:01 2013 +0200
----------------------------------------------------------------------
.../java/org/apache/spark/mllib/recommendation/JavaALSSuite.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/6a7836cd/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
----------------------------------------------------------------------
diff --git a/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java b/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
index ec545ef..c8e59f7 100644
--- a/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
+++ b/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
@@ -90,8 +90,8 @@ public class JavaALSSuite implements Serializable {
double err = confidence * (truePref - prediction) * (truePref - prediction);
sqErr += err;
denom += 1.0;
- }
}
+ }
double rmse = Math.sqrt(sqErr / denom);
Assert.assertTrue(String.format("Confidence-weighted RMSE=%2.4f above threshold of %2.2f",
rmse, matchThreshold), Math.abs(rmse) < matchThreshold);
[09/10] git commit: Merge branch 'master' into implicit-als
Posted by ma...@apache.org.
Merge branch 'master' into implicit-als
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/a5e58b8f
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/a5e58b8f
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/a5e58b8f
Branch: refs/heads/master
Commit: a5e58b8f980fe49d02dce83e366f0ea0cf070d76
Parents: b0f5f4d d585613
Author: Nick Pentreath <ni...@gmail.com>
Authored: Mon Oct 7 11:46:17 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Mon Oct 7 11:46:17 2013 +0200
----------------------------------------------------------------------
assembly/pom.xml | 18 +--
bagel/pom.xml | 8 +-
core/pom.xml | 15 +-
.../scala/org/apache/spark/CacheManager.scala | 4 +-
.../scala/org/apache/spark/SparkContext.scala | 39 ++++--
.../spark/api/python/PythonPartitioner.scala | 10 +-
.../org/apache/spark/api/python/PythonRDD.scala | 6 +-
.../org/apache/spark/deploy/JsonProtocol.scala | 3 +-
.../apache/spark/deploy/SparkHadoopUtil.scala | 12 +-
.../scala/org/apache/spark/rdd/HadoopRDD.scala | 140 ++++++++++++++++---
.../scala/org/apache/spark/util/Utils.scala | 13 ++
.../spark/scheduler/SparkListenerSuite.scala | 6 +-
.../org/apache/spark/util/UtilsSuite.scala | 11 ++
docs/_layouts/global.html | 4 +-
ec2/spark_ec2.py | 4 +-
examples/pom.xml | 30 ++--
mllib/pom.xml | 8 +-
pom.xml | 7 +-
python/pyspark/rdd.py | 10 +-
python/pyspark/serializers.py | 4 +
repl-bin/pom.xml | 10 +-
repl/pom.xml | 20 +--
streaming/pom.xml | 9 +-
tools/pom.xml | 8 +-
yarn/pom.xml | 6 +-
25 files changed, 293 insertions(+), 112 deletions(-)
----------------------------------------------------------------------
[10/10] git commit: Merge pull request #4 from MLnick/implicit-als
Posted by ma...@apache.org.
Merge pull request #4 from MLnick/implicit-als
Adding algorithm for implicit feedback data to ALS
This PR adds the commonly used "implicit feedack" variant to ALS.
The implementation is based in part on Mahout's implementation, which is in turn based on [Collaborative Filtering for Implicit Feedback Datasets](http://research.yahoo.com/pub/2433). It has been adapted for the blocked approach used in MLlib.
I have tested this implementation against the MovieLens 100k, 1m and 10m datasets, and confirmed that it produces the same RMSE score as Mahout, as well as my own port of Mahout's implicit ALS implementation to Spark (not that RMSE is necessarily the best metric to judge by for implicit feedback, but it provides a consistent metric for comparison).
It turned out to be more straightforward than I had thought to add this. The main additions are:
1. Adding `implicitPrefs` boolean flag and `alpha` parameter
2. Added the `computeYtY` method. In each least-squares step, the algorithm requires the computation of `YtY`, where `Y` is the {user, item} factor matrix. Since the factors are already block-distributed in an `RDD`, this is quite straightforward to compute but does add an extra operation over the explicit version (but only twice per iteration)
3. Finally the actual solve step in `updateBlock` boils down to:
* a multiplication of the `XtX` matrix by `alpha * rating`
* a multiplication of the `Xty` vector by `1 + alpha * rating`
* when solving for the factor vector, the implicit variant adds the `YtY` matrix to the LHS
4. Added `trainImplicit` methods in the `ALS` object
5. Added test cases for both Scala and Java - based on achieving a confidence-weighted RMSE score < 0.4 (this is taken from Mahout's test cases)
It would be great to get some feedback on this and have people test things out against some datasets (MovieLens and others and perhaps proprietary datasets) both locally and on a cluster if possible. I have not yet tested on a cluster but will try to do that soon.
I have tried to make things as efficient as possible but if there are potential improvements let me know.
The results of a run against ml-1m are below (note the vanilla RMSE scores will be very different from the explicit variant):
**INPUTS**
```
iterations=10
factors=10
lambda=0.01
alpha=1
implicitPrefs=true
```
**RESULTS**
```
Spark MLlib 0.8.0-SNAPSHOT
RMSE = 3.1544
Time: 24.834 sec
```
```
My own port of Mahout's ALS to Spark (updated to 0.8.0-SNAPSHOT)
RMSE = 3.1543
Time: 58.708 sec
```
```
Mahout 0.8
time ./factorize-movielens-1M.sh /path/to/ratings/ml-1m/ratings.dat
real 3m48.648s
user 6m39.254s
sys 0m14.505s
RMSE = 3.1539
```
Results of a run against ml-10m
```
Spark MLlib
RMSE = 3.1200
Time: 162.348 sec
```
```
Mahout 0.8
real 23m2.220s
user 43m39.185s
sys 0m25.316s
RMSE = 3.1187
```
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/3218fa79
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/3218fa79
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/3218fa79
Branch: refs/heads/master
Commit: 3218fa795ff3ddee855772184aebe99098701d4f
Parents: e67d5b9 a5e58b8
Author: Matei Zaharia <ma...@eecs.berkeley.edu>
Authored: Tue Oct 8 23:44:55 2013 -0700
Committer: Matei Zaharia <ma...@eecs.berkeley.edu>
Committed: Tue Oct 8 23:44:55 2013 -0700
----------------------------------------------------------------------
docs/mllib-guide.md | 24 ++-
.../apache/spark/mllib/recommendation/ALS.scala | 199 ++++++++++++++++---
.../mllib/recommendation/JavaALSSuite.java | 85 ++++++--
.../spark/mllib/recommendation/ALSSuite.scala | 75 +++++--
4 files changed, 320 insertions(+), 63 deletions(-)
----------------------------------------------------------------------
[06/10] git commit: Style fix using 'if' rather than 'match' on
boolean
Posted by ma...@apache.org.
Style fix using 'if' rather than 'match' on boolean
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/c6ceaeae
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/c6ceaeae
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/c6ceaeae
Branch: refs/heads/master
Commit: c6ceaeae50c7b5d69bb9897af32f537bfbde152d
Parents: 6a7836c
Author: Nick Pentreath <ni...@gmail.com>
Authored: Fri Oct 4 13:52:53 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Fri Oct 4 13:52:53 2013 +0200
----------------------------------------------------------------------
.../apache/spark/mllib/recommendation/ALS.scala | 27 ++++++++++----------
1 file changed, 13 insertions(+), 14 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/c6ceaeae/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
----------------------------------------------------------------------
diff --git a/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala b/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
index 5935d27..36853ac 100644
--- a/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
+++ b/mllib/src/main/scala/org/apache/spark/mllib/recommendation/ALS.scala
@@ -207,20 +207,19 @@ class ALS private (var numBlocks: Int, var rank: Int, var iterations: Int, var l
* @return Option[YtY] - whose value is only used in the implicit preference model
*/
def computeYtY(factors: RDD[(Int, Array[Array[Double]])]) = {
- implicitPrefs match {
- case true => {
- Option(
- factors.flatMapValues{ case factorArray =>
- factorArray.map{ vector =>
- val x = new DoubleMatrix(vector)
- x.mmul(x.transpose())
- }
- }.reduceByKeyLocally((a, b) => a.addi(b))
- .values
- .reduce((a, b) => a.addi(b))
- )
- }
- case false => None
+ if (implicitPrefs) {
+ Option(
+ factors.flatMapValues{ case factorArray =>
+ factorArray.map{ vector =>
+ val x = new DoubleMatrix(vector)
+ x.mmul(x.transpose())
+ }
+ }.reduceByKeyLocally((a, b) => a.addi(b))
+ .values
+ .reduce((a, b) => a.addi(b))
+ )
+ } else {
+ None
}
}
[08/10] git commit: Bumping up test matrix size to eliminate random
failures
Posted by ma...@apache.org.
Bumping up test matrix size to eliminate random failures
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/b0f5f4d4
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/b0f5f4d4
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/b0f5f4d4
Branch: refs/heads/master
Commit: b0f5f4d441119662c09572de697b2d9943f703ef
Parents: 93b96b4
Author: Nick Pentreath <ni...@gmail.com>
Authored: Mon Oct 7 11:44:22 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Mon Oct 7 11:44:22 2013 +0200
----------------------------------------------------------------------
.../spark/mllib/recommendation/JavaALSSuite.java | 16 ++++++++--------
.../spark/mllib/recommendation/ALSSuite.scala | 8 ++++----
2 files changed, 12 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/b0f5f4d4/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
----------------------------------------------------------------------
diff --git a/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java b/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
index c8e59f7..eafee06 100644
--- a/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
+++ b/mllib/src/test/java/org/apache/spark/mllib/recommendation/JavaALSSuite.java
@@ -102,8 +102,8 @@ public class JavaALSSuite implements Serializable {
public void runALSUsingStaticMethods() {
int features = 1;
int iterations = 15;
- int users = 10;
- int products = 10;
+ int users = 50;
+ int products = 100;
scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
users, products, features, 0.7, false);
@@ -116,8 +116,8 @@ public class JavaALSSuite implements Serializable {
public void runALSUsingConstructor() {
int features = 2;
int iterations = 15;
- int users = 20;
- int products = 30;
+ int users = 100;
+ int products = 200;
scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
users, products, features, 0.7, false);
@@ -133,8 +133,8 @@ public class JavaALSSuite implements Serializable {
public void runImplicitALSUsingStaticMethods() {
int features = 1;
int iterations = 15;
- int users = 40;
- int products = 80;
+ int users = 80;
+ int products = 160;
scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
users, products, features, 0.7, true);
@@ -147,8 +147,8 @@ public class JavaALSSuite implements Serializable {
public void runImplicitALSUsingConstructor() {
int features = 2;
int iterations = 15;
- int users = 50;
- int products = 100;
+ int users = 100;
+ int products = 200;
scala.Tuple3<List<Rating>, DoubleMatrix, DoubleMatrix> testData = ALSSuite.generateRatingsAsJavaList(
users, products, features, 0.7, true);
http://git-wip-us.apache.org/repos/asf/incubator-spark/blob/b0f5f4d4/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
----------------------------------------------------------------------
diff --git a/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala b/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
index 1ab181d..fafc5ec 100644
--- a/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
+++ b/mllib/src/test/scala/org/apache/spark/mllib/recommendation/ALSSuite.scala
@@ -87,19 +87,19 @@ class ALSSuite extends FunSuite with BeforeAndAfterAll {
}
test("rank-1 matrices") {
- testALS(10, 20, 1, 15, 0.7, 0.3)
+ testALS(50, 100, 1, 15, 0.7, 0.3)
}
test("rank-2 matrices") {
- testALS(20, 30, 2, 15, 0.7, 0.3)
+ testALS(100, 200, 2, 15, 0.7, 0.3)
}
test("rank-1 matrices implicit") {
- testALS(40, 80, 1, 15, 0.7, 0.4, true)
+ testALS(80, 160, 1, 15, 0.7, 0.4, true)
}
test("rank-2 matrices implicit") {
- testALS(50, 100, 2, 15, 0.7, 0.4, true)
+ testALS(100, 200, 2, 15, 0.7, 0.4, true)
}
/**
[02/10] git commit: Merge remote-tracking branch 'upstream/master'
into implicit-als
Posted by ma...@apache.org.
Merge remote-tracking branch 'upstream/master' into implicit-als
Project: http://git-wip-us.apache.org/repos/asf/incubator-spark/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-spark/commit/d952f04c
Tree: http://git-wip-us.apache.org/repos/asf/incubator-spark/tree/d952f04c
Diff: http://git-wip-us.apache.org/repos/asf/incubator-spark/diff/d952f04c
Branch: refs/heads/master
Commit: d952f04c8e588977ade5a5694052232881374c73
Parents: 737f01a 119de80
Author: Nick Pentreath <ni...@gmail.com>
Authored: Mon Sep 23 13:07:40 2013 +0200
Committer: Nick Pentreath <ni...@gmail.com>
Committed: Mon Sep 23 13:07:40 2013 +0200
----------------------------------------------------------------------
assembly/README | 11 +-
assembly/pom.xml | 6 +
conf/fairscheduler.xml.template | 18 +-
conf/metrics.properties.template | 50 ++-
core/pom.xml | 9 +
.../scala/org/apache/spark/CacheManager.scala | 8 +-
.../scala/org/apache/spark/SparkContext.scala | 25 +-
.../main/scala/org/apache/spark/SparkEnv.scala | 2 +-
.../scala/org/apache/spark/TaskContext.scala | 1 +
.../org/apache/spark/deploy/DeployMessage.scala | 4 +
.../org/apache/spark/deploy/JsonProtocol.scala | 4 +-
.../apache/spark/deploy/LocalSparkCluster.scala | 2 +-
.../org/apache/spark/deploy/master/Master.scala | 21 +-
.../org/apache/spark/executor/Executor.scala | 2 +-
.../apache/spark/executor/ExecutorSource.scala | 5 +-
.../apache/spark/metrics/MetricsConfig.scala | 7 +-
.../apache/spark/metrics/sink/GangliaSink.scala | 82 +++++
.../spark/metrics/sink/MetricsServlet.scala | 11 +-
.../spark/network/netty/ShuffleSender.scala | 3 +-
.../main/scala/org/apache/spark/rdd/RDD.scala | 17 +
.../apache/spark/scheduler/DAGScheduler.scala | 12 +-
.../spark/scheduler/DAGSchedulerSource.scala | 6 +-
.../org/apache/spark/scheduler/ResultTask.scala | 6 +-
.../apache/spark/scheduler/ShuffleMapTask.scala | 2 +-
.../scheduler/cluster/ClusterScheduler.scala | 2 +-
.../cluster/ClusterTaskSetManager.scala | 4 +-
.../scheduler/cluster/SchedulableBuilder.scala | 6 +-
.../cluster/SparkDeploySchedulerBackend.scala | 12 +-
.../spark/scheduler/local/LocalScheduler.scala | 2 +-
.../spark/storage/BlockManagerSource.scala | 6 +-
.../org/apache/spark/storage/DiskStore.scala | 2 +-
.../org/apache/spark/storage/StorageLevel.scala | 6 +-
.../scala/org/apache/spark/ui/SparkUI.scala | 7 +-
.../scala/org/apache/spark/ui/UIUtils.scala | 39 ++-
.../apache/spark/ui/UIWorkloadGenerator.scala | 4 +-
.../spark/ui/jobs/JobProgressListener.scala | 2 +-
.../org/apache/spark/ui/jobs/PoolTable.scala | 3 +-
.../org/apache/spark/ui/jobs/StageTable.scala | 7 +-
.../org/apache/spark/ui/storage/IndexPage.scala | 2 +-
.../scala/org/apache/spark/util/Utils.scala | 26 +-
.../org/apache/spark/CacheManagerSuite.scala | 91 ++++++
.../scala/org/apache/spark/JavaAPISuite.java | 2 +-
.../apache/spark/deploy/JsonProtocolSuite.scala | 92 ++++++
.../spark/metrics/MetricsConfigSuite.scala | 19 +-
.../scala/org/apache/spark/rdd/RDDSuite.scala | 14 +-
.../cluster/ClusterSchedulerSuite.scala | 8 +-
.../scheduler/local/LocalSchedulerSuite.scala | 8 +-
.../scala/org/apache/spark/ui/UISuite.scala | 2 +-
docs/_config.yml | 2 +-
docs/_layouts/global.html | 9 +-
docs/building-with-maven.md | 6 +-
docs/cluster-overview.md | 117 +++++++
docs/configuration.md | 34 +-
docs/contributing-to-spark.md | 24 +-
docs/ec2-scripts.md | 8 +-
docs/hadoop-third-party-distributions.md | 118 +++++++
docs/hardware-provisioning.md | 4 +-
docs/img/cluster-overview.png | Bin 0 -> 28011 bytes
docs/img/cluster-overview.pptx | Bin 0 -> 51771 bytes
docs/img/spark-logo-hd.png | Bin 0 -> 13512 bytes
docs/index.md | 26 +-
docs/job-scheduling.md | 168 ++++++++++
docs/mllib-guide.md | 192 ++++++++++-
docs/monitoring.md | 70 ++++
docs/python-programming-guide.md | 14 +-
docs/quick-start.md | 70 ++--
docs/running-on-mesos.md | 48 ++-
docs/running-on-yarn.md | 35 +-
docs/scala-programming-guide.md | 4 +-
docs/spark-standalone.md | 46 ++-
.../root/spark-ec2/ec2-variables.sh | 17 +
ec2/spark_ec2.py | 11 +-
examples/pom.xml | 14 -
make-distribution.sh | 2 +-
mllib/data/sample_svm_data.txt | 322 +++++++++++++++++++
.../apache/spark/mllib/classification/SVM.scala | 13 +-
.../mllib/regression/LinearRegression.scala | 4 +-
pom.xml | 236 +++++++-------
project/SparkBuild.scala | 17 +-
project/project/SparkPluginBuild.scala | 19 +-
python/pyspark/__init__.py | 5 +-
python/pyspark/context.py | 11 +
python/pyspark/rdd.py | 19 ++
python/pyspark/shell.py | 1 +
python/pyspark/storagelevel.py | 43 +++
repl-bin/pom.xml | 10 -
repl/pom.xml | 12 -
run-example | 8 +-
yarn/pom.xml | 66 ++--
.../spark/deploy/yarn/ApplicationMaster.scala | 78 +++--
.../yarn/ApplicationMasterArguments.scala | 2 +-
.../org/apache/spark/deploy/yarn/Client.scala | 5 +-
.../spark/deploy/yarn/ClientArguments.scala | 2 +-
.../spark/deploy/yarn/WorkerRunnable.scala | 3 +-
.../deploy/yarn/YarnAllocationHandler.scala | 13 +-
.../cluster/YarnClusterScheduler.scala | 3 +
96 files changed, 2068 insertions(+), 543 deletions(-)
----------------------------------------------------------------------