Ganitha
Tresata is proud to release Ganitha, our first opensource library. Ganitha (derived from the Sanskrit word for mathematics, or science of computation) is a Scalding library with a focus on machinelearning and statistical analysis.
The current pieces to be opensourced are our integration of Mahout vectors into Scalding, our clustering (KMeans) implementation, and NaiveBayes classifiers.
GanithaMahout
To make mahout vectors usable in Scala/Scalding we did the following:

Pimp Mahout vectors: We used the pimpmylibrary pattern in Scala to make Mahout vectors more friendly to use (see
RichVector.scala
). Note that we decided to not implementRichVector
as anIndexedSeq
, but rather as anIterable
, for our first iteration. We also didn't implementIterableLike
(orIndexedSeqLike
) andCanBuildFrom
, which would allow operations likevector.take(3)
andvector.map(f)
to return new Mahout vectors. The reason for this was that we were not happy with the interaction between the builders and the pimpmylibrary pattern. We might still add these features in the future. As an alternative, we provided thevectorMap
methods that return Mahout vectors. Thanks toRichVector
, you can now do things like:scala> import com.tresata.ganitha.mahout._ scala> import com.tresata.ganitha.mahout.Implicits._ scala> // create a sparse vector of size 6 with elements 1, 3 and 5 nonzero scala> val v = RichVector(6, List((1, 1.0), (3, 2.0), (5, 3.0))) v: org.apache.mahout.math.Vector = {5:3.0,3:2.0,1:1.0}
(We can see it's using a Mahout
RandomAccessSparseVector
withv.getClass
). Likewise, we can create a dense vector with 3 elements as follows:scala> val v1 = RichVector(Array(1.0,2.0,3.0)) v1: org.apache.mahout.math.Vector = {0:1.0,1:2.0,2:3.0}
We can also perform basic math and vector operations (map, fold, etc.) on the vectors. Elements inside the vectors can be accessed and set (since Mahout vectors are mutable), however, this is not encouraged.
scala> (v + 2) / 2 res1: org.apache.mahout.math.Vector = {5:2.5,4:1.0,3:2.0,2:1.0,1:1.5,0:1.0} scala> v.map(x => x * 2).sum res2: Double = 12.0 scala> v.fold(0.0)(_ + _) res3: Double = 6.0 scala> v(3) res4: Double = 2.0 scala> v(3) = 3.0 scala> v res5: org.apache.mahout.math.Vector = {5:3.0,3:3.0,1:1.0} scala> v * v res6: org.apache.mahout.math.Vector = {5:9.0,3:4.0,1:1.0}
The
nonZero
method provides access to the nonzero elements as a scalaIterable
.scala> v.nonZero.toMap res7: scala.collection.immutable.Map[Int,Double] = Map(5 > 3.0, 3 > 3.0, 1 > 1.0)
Dense vectors can be converted to sparse, and vice versa.
scala> v1.toSparse.getClass res8: java.lang.Class[_ <: org.apache.mahout.math.Vector] = class org.apache.mahout.math.RandomAccessSparseVector
The
vectorMap
operation provides access to the assignment operation on a Mahout vector, but as a nonmutating operation (it creates a copy first).scala> v.vectorMap(x => x * 2) res9: org.apache.mahout.math.Vector = {5:6.0,3:4.0,1:2.0}

Make serialization transparent: Mahout's vectors come with a separate class called
VectorWritable
that implementsWritable
for serialization within Hadoop. The issue with this is that you cannot just registerVectorWritable
as a Hadoop serializer and be done with it. If you did this then you would have to constantly wrap your Mahout vectors in aVectorWritable
to make them serializable. To make the serialization transparent we addedVectorSerializer
, a Kryo serializer that defers toVectorWritable
for the actual work. All one has to do is registerVectorSerializer
with Kryo, and serialization works in Scalding. For example, if you are using aJobConf
you can write:VectorSerializer.register(job)
The same applies to a Scalding
Config
(which is aMap[AnyRef, AnyRef]
):VectorSerializer.register(config)
NaiveBayes classifying
A NaiveBayes classifier is a probabilistic classifier used in machinelearning that involves the application of Bayes' theorem. The underlying model is "naive" because of the assumption that the attributes are conditionally independent of each other. NaiveBayes learning is suprisingly effective in a wide range of applications, given the simplifying assumption of feature independence. Though not as powerful as decisiontree learning, it is considerably less computationally complex than many other forms of classifiers, and in many cases, the naive assumption has little impact on the quality of predictions.
Ganitha supplies three of the more popular forms of NaiveBayes classifiers: Gaussian, Multinomial, and Bernoulli. In gaussian NaiveBayes, a type of classifier used for continuous data, we are making the assumption that the features associated with each class lie along a normal distribution. In a multinomial or Bernoulli event model, we are dealing with discrete features, a common example being the classification of a document given the presence of words (features) in the text. In this case, each word has a score assigned to it for each label, or class. In multinomial NaiveBayes, each feature vector relates to the term frequency of the words found in the document or class. We make the 'bagofwords' assumption, in which documents are represented as a multiset of words, disregarding grammar or word order. In Bernoulli NaiveBayes, features represent binary occurences, and in this classification model, the absence of a word/feature has an effect on the calculated probabilities.
Each classifier consists of a training phase, where an NBModel
is constructed from the training set of data, and a classifying, or predicting, phase. In the classifying phase, each data point that is to be classified is given a probability (in this case a log probability is used) for each label, and the label with the highest, or maximum a posteriori probability is assigned to the data point.
KMeans clustering
Kmeans clustering consists of partitioning data points into k 'clusters' where each point belongs to the cluster with the nearest mean. The process of refining the centers of the clusters is commonly known as Lloyd's algorithm, however there exist heuristic algorithms to seed the initial selection of cluster centers in order to improve the rate of convergence of Lloyd's algorithm. KMeans++ offers an improvement over random initial selection, and more recently, KMeans offers an initialization technique that greatly cuts down on the number of iterations needed to determine initial clusters, a very desirable optimization in Hadoop applications, where significant overhead is involved in each iteration.
Ganitha provides an extensible interface for handling vector operations using different representations for data points, including Mahout vectors (which can contain categorical and textual features in addition to numerical). The VectorHelper
trait can be used to specify how vectors are defined from the input and how distances are calculated between vectors.
KMeans in Ganitha (currently) reads vectors from Cascading Sequence files, and the algorithm writes a list of vectoridclusterid pairs to a Tap, as well as a list of cluster ids with coordinates.
References
KMeans: Lloyd, S., "Least squares quantization in PCM". IEEE Trans. Information Theory, 28(2):129137, 1982.
KMeans++: Arthur, D. and Vassilvitskii, S. (2007). "kmeans++: the advantages of careful seeding". Proc. ACMSIAM Symp. Discrete Algorithms. pp. 1027–1035.
KMeans: Bahmani, B. et al. (2012). "Scalable kmeans++". Proceedings of the VLDB Endowment, 5(7), 622633.
Getting started with Ganitha and KMeans
Ganitha uses sbt for generating builds. To create a runnable jar distribution, run sbt update
and sbt assembly
. Unit tests are included and can be run using sbt test
.
To run KMeans clustering on a test set of data, stored as a commaseparated values file with a header (in this example, with a file on Hadoop named 100kPoints.csv with the header (id,x,y
), run the following command from within the ganitha directory:
hadoop jar ganithaml/target/scala2.10/ganithamlassembly0.1SNAPSHOT.jar com.twitter.scalding.Tool com.tresata.ganitha.ml.clustering.KMeansJob hdfs vecType StrDblMapVector distFn euclidean k 100 id id features x y input 100kPoints.csv vectors 100kVectors vectorOutput vectorAssignments clusterOutput centroids
This will use the id
columns as the vector id, and will encode the coordinates(x
and y
) as Map[String, Double]
vectors (using the StrDblMapVector
VectorHelper), under a Euclidean space, and run the algorithm on k=100 clusters. The output is written to a vectorAssignments
file on Hadoop, with the cluster centroids written to centroids
. The vectors
argument specifies a location for the Cascading Sequence file that serves as the input for KMeans
.
License
Copyright 2014 Tresata, Inc.
Licensed under the Apache License, Version 2.0: http://www.apache.org/licenses/LICENSE2.0