Algorithms
This section contains links to information, examples, use cases, etc. for the various algorithms we intend to implement. Click the individual links to learn more. The initial algorithms descriptions have been copied here from the original project proposal. The algorithms are grouped by the application setting, they can be used for. In case of multiple applications, the version presented in the paper was chosen, versions as implemented in our project will be added as soon as we are working on them.
Original Paper: Map Reduce for Machine Learning on Multicore
Papers related to Map Reduce:
- Evaluating MapReduce for Multi-core and Multiprocessor Systems
- Map Reduce: Distributed Computing for Machine Learning
For Papers, videos and books related to machine learning in general, see Machine Learning Resources
All algorithms are either marked as integrated, that is the implementation is integrated into the development version of Mahout. Algorithms that are currently being developed are annotated with a link to the JIRA issue that deals with the specific implementation. Usually these issues already contain patches that are more or less major, depending on how much work was spent on the issue so far. Algorithms that have so far not been touched are marked as open.
What, When, Where, Why (but not How or Who) - Community tips, tricks, etc. for when to use which algorithm in what situations, what to watch out for in terms of errors. That is, practical advice on using Mahout for your problems.
Classification
A general introduction to the most common text classification algorithms can be found at Google Answers: http://answers.google.com/answers/main?cmd=threadview&id=225316 For information on the algorithms implemented in Mahout (or scheduled for implementation) please visit the following pages.
Logistic Regression (SGD)
Support Vector Machines (SVM) (open: MAHOUT-14, MAHOUT-232 and MAHOUT-334)
Perceptron and Winnow (open: MAHOUT-85)
Neural Network (open, but MAHOUT-228 might help)
Random Forests (integrated - MAHOUT-122, MAHOUT-140, MAHOUT-145)
Restricted Boltzmann Machines (open, MAHOUT-375, GSOC2010)
Online Passive Aggressive (integrated, MAHOUT-702)
Boosting (awaiting patch commit, MAHOUT-716)
Hidden Markov Models (HMM) (MAHOUT-627, MAHOUT-396, MAHOUT-734) - Training is done in Map-Reduce
Clustering
Canopy Clustering (MAHOUT-3 - integrated)
K-Means Clustering (MAHOUT-5 - integrated)
Fuzzy K-Means (MAHOUT-74 - integrated)
Expectation Maximization (EM) (MAHOUT-28)
Mean Shift Clustering (MAHOUT-15 - integrated)
Hierarchical Clustering (MAHOUT-19)
Dirichlet Process Clustering (MAHOUT-30 - integrated)
Latent Dirichlet Allocation (MAHOUT-123 - integrated)
Spectral Clustering (MAHOUT-363 - integrated)
Minhash Clustering (MAHOUT-344 - integrated)
Top Down Clustering (MAHOUT-843 - patch reviewed)
Pattern Mining
Parallel FP Growth Algorithm (Also known as Frequent Itemset mining)
Regression
Locally Weighted Linear Regression (open)
Dimension reduction
Singular Value Decomposition and other Dimension Reduction Techniques (available since 0.3)
Stochastic Singular Value Decomposition
Principal Components Analysis (PCA) (open)
Independent Component Analysis (open)
Gaussian Discriminative Analysis (GDA) (open)
Evolutionary Algorithms
see also: MAHOUT-56 (integrated)
You will find here information, examples, use cases, etc. related to Evolutionary Algorithms.
Introductions and Tutorials:
Examples:
Recommenders / Collaborative Filtering
Mahout contains both simple non-distributed recommender implementations and distributed Hadoop-based recommenders.
- Non-distributed recommenders ("Taste") (integrated)
- Distributed Item-Based Collaborative Filtering (integrated)
- Collaborative Filtering using a parallel matrix factorization (integrated)
- First-timer FAQ
Vector Similarity
Mahout contains implementations that allow one to compare one or more vectors with another set of vectors. This can be useful if one is, for instance, trying to calculate the pairwise similarity between all documents (or a subset of docs) in a corpus.
- RowSimilarityJob – Builds an inverted index and then computes distances between items that have co-occurrences. This is a fully distributed calculation.
- VectorDistanceJob – Does a map side join between a set of "seed" vectors and all of the input vectors.
Other
Non-MapReduce algorithms
Some algorithms and applications appeared on the mailing list, that have not been published in map reduce form so far. As we do not restrict ourselves to Hadoop-only versions, these proposals are listed here.