grafos-ml/okapi

Large-scale ML & graph analytics on Giraph

Okapi

Overview

Okapi is a library of Machine Learning and graph mining algorithms for Giraph. The library includes state-of-the-art Collaborative Filtering algorithms used in recommendation systems as well as graph algorithms such as partitioning, clustering and sybil-detection for OSNs.

The Okapi library is developed by the Telefonica Research lab and is available as open source under the Apache License. We invite users to contribute to the library, to make it more robust and rich in features. Okapi is part of the Grafos.ML project.

For a full list of the provided algorithms, documentation, and instructions on how to use Okapi, please visit the Grafos.ML page.

Building

Although you can find pre-built packages on the Grafos.ML for different Hadoop distributions, you may very likely need to build the code youself. Go into $OKAPI_HOME, the directory where you cloned the code, and run:

mvn package

This will build the code and also run some tests. If you want to skip the tests, then run:

mvn package -DskipTests

After that, under $OKAPI_HOME/target, you should find a jar file with a name of the type:

okapi-${VERSION}-jar-with-dependencies.jar

Inside the jar, we package the Okapi library as well as all dependencies for convenience.

Running

Running an Okapi job does not differ from running an ordinary Giraph job. You can use the pre-built jars or the jar you built yourself to launch a Giraph job as described on the Giraph site. On our site, we also provide a web-based tool that helps you construct the command you need to execute. Check it out!

Collaborative Filtering

To run any of the CF algorithms, we suggest to use bin/runOkapi.py, i.e.:

python runOkapi.py SpitPrecision --local-scheduler --model-name Pop --fraction 1.0

This gives Precision@5, and uses evaluation procedure where we sample 100 items, mark them as irrelevant and rank all the list according to the predicted scores. We also provide some results. These are for reference only (default parameters, no cross-validation). Note, that many of these algorithms were not designed to run on data sets with ratings, others optimize rating prediction, therefore, we compare apples and boxes.

Okapi-0.3.2-SNAPSHOT and Movielens 1M dataset:

--model-name	Precision@5
Random	0.1529
Pop	0.7554
BPR	0.2412

okapi's Issues

Item-to-item similarity computation based on Jaccard coefficient

For each item returns a list of top-k most similar items.

k-means clustering implementation

Hello,

I would like to implement the k-means clustering algorithm for okapi and I would really appreciate your input regarding some implementation choices.

The algorithm partitions N data points (observations) into k clusters.
The standard algorithm is iterative and works as follows.

Input: data points of the form { pointID, coordinatesVector }
Output: { pointID, centerID } & coordinates of each of the k cluster centers. Cluster centers do not have to belong to the input points.
Initialization: randomly choose k points from input

In each iteration:

1. each data point is assigned to the cluster center which is closest to it, by means of euclidean distance
2. new cluster centers are recomputed, by calculating the arithmetic mean of the assigned points
   Convergence is reached when the positions of the cluster centers do not change.

In Giraph, each data point will correspond to a vertex and execute step 1. The positions of the k centers can be stored in an aggregator and updated by the Master.

The GPS paper describes a different version of the algorithm, where

1. cluster centers are randomly chosen in each iteration
2. distance from the centers is calculated based on shortest paths (edge weights)
3. convergence is reached when the edge cut is less than some threshold

Facebook seems to have followed a similar implementation.

In my view, it's better going for the standard implementation and once we have a stable implementation, maybe extend it to support edge-cut as converge criterion and/or other variations.
Let me know your thoughts!

Linear Regression

NPE in ALS

I get a NullPointerException while using ALS, causing the hadoop job to hang in the map phase:

java.lang.IllegalStateException: run: Caught an unrecoverable exception waitFor: ExecutionException occurred while waiting for org.apache.giraph.utils.ProgressableUtils$FutureWaitable@ae797e1
    at org.apache.giraph.graph.GraphMapper.run(GraphMapper.java:101)
    at org.apache.hadoop.mapred.MapTask.runNewMapper(MapTask.java:771)
    at org.apache.hadoop.mapred.MapTask.run(MapTask.java:375)
    at org.apache.hadoop.mapred.Child$4.run(Child.java:255)
    at java.security.AccessController.doPrivileged(Native Method)
    at javax.security.auth.Subject.doAs(Subject.java:415)
    at org.apache.hadoop.security.UserGroupInformation.doAs(UserGroupInformation.java:1132)
    at org.apache.hadoop.mapred.Child.main(Child.java:249)
Caused by: java.lang.IllegalStateException: waitFor: ExecutionException occurred while waiting for org.apache.giraph.utils.ProgressableUtils$FutureWaitable@ae797e1
    at org.apache.giraph.utils.ProgressableUtils.waitFor(ProgressableUtils.java:193)
    at org.apache.giraph.utils.ProgressableUtils.waitForever(ProgressableUtils.java:151)
    at org.apache.giraph.utils.ProgressableUtils.waitForever(ProgressableUtils.java:136)
    at org.apache.giraph.utils.ProgressableUtils.getFutureResult(ProgressableUtils.java:99)
    at org.apache.giraph.utils.ProgressableUtils.getResultsWithNCallables(ProgressableUtils.java:233)
    at org.apache.giraph.graph.GraphTaskManager.processGraphPartitions(GraphTaskManager.java:722)
    at org.apache.giraph.graph.GraphTaskManager.execute(GraphTaskManager.java:300)
    at org.apache.giraph.graph.GraphMapper.run(GraphMapper.java:91)
    ... 7 more
Caused by: java.util.concurrent.ExecutionException: java.lang.NullPointerException
    at java.util.concurrent.FutureTask.report(FutureTask.java:122)
    at java.util.concurrent.FutureTask.get(FutureTask.java:202)
    at org.apache.giraph.utils.ProgressableUtils$FutureWaitable.waitFor(ProgressableUtils.java:312)
    at org.apache.giraph.utils.ProgressableUtils.waitFor(ProgressableUtils.java:185)
    ... 14 more
Caused by: java.lang.NullPointerException
    at org.jblas.JavaBlas.rcopy(JavaBlas.java:198)
    at ml.grafos.okapi.cf.als.Als.updateValue(Als.java:150)
    at ml.grafos.okapi.cf.als.Als.compute(Als.java:121)
    at org.apache.giraph.graph.ComputeCallable.computePartition(ComputeCallable.java:247)
    at org.apache.giraph.graph.ComputeCallable.call(ComputeCallable.java:168)
    at org.apache.giraph.graph.ComputeCallable.call(ComputeCallable.java:71)
    at org.apache.giraph.utils.LogStacktraceCallable.call(LogStacktraceCallable.java:51)
    at java.util.concurrent.FutureTask.run(FutureTask.java:262)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
    at java.lang.Thread.run(Thread.java:724)

I used the following command to submit the job:

hadoop jar okapi-0.3.2-SNAPSHOT-jar-with-dependencies.jar org.apache.giraph.GiraphRunner -Dmapred.job.name=OkapiTrainModelTask -Dmapred.reduce.tasks=0 -libjars okapi-0.3.2-SNAPSHOT-jar-with-dependencies.jar -Dmapred.child.java.opts=-Xmx1g -Dgiraph.zkManagerDirectory=okapi/_bspaa12713563219 -Dgiraph.useSuperstepCounters=true ml.grafos.okapi.cf.als.Als -eif ml.grafos.okapi.cf.CfLongIdFloatTextInputFormat -eip okapi/data/c75153b91d2ac405f59afcb669e84e54 -vof org.apache.giraph.io.formats.IdWithValueTextOutputFormat -op Dave_out_1395916381 -w 1 -ca giraph.numComputeThreads=1 -ca minItemId=0 -ca maxItemId=2975 -ca iterations=2 -ca dim=2

Looking at jblas' source code, value.data seems to be null in updateValue()

Logistic Regression