Time to Put Some Order - Cluster Your Data with Spark MLlib

"If you take a galaxy and try to make it bigger, it becomes a cluster of galaxies, not a galaxy. If you try to make it smaller than that, it seems to blow itself apart"

- Jeremiah P. Ostriker

In this chapter, we will delve deeper into machine learning and find out how we can take advantage of it to cluster records belonging to a certain group or class for a dataset of unsupervised observations. In a nutshell, the following topics will be covered in this chapter:

• Unsupervised learning
• Clustering techniques
• Hierarchical clustering (HC)
• Centroid-based clustering (CC)
• Distribution-based clustering (DC)
• Determining number of clusters
• A comparative analysis between clustering algorithms
• Submitting jobs on computing clusters

Unsupervised learning

In this section, we will provide a brief introduction to unsupervised machine learning technique with appropriate examples. Let's start the discussion with a practical example. Suppose you have a large collection of not-pirated-totally-legal mp3s in a crowded and massive folder on your hard drive. Now, what if you can build a predictive model that helps automatically group together similar songs and organize them into your favorite categories such as country, rap, rock, and so on. This act of assigning an item to a group such that a mp3 to is added to the respective playlist in an unsupervised way. In the previous chapters, we assumed you're given a training dataset of correctly labeled data. Unfortunately, we don't always have that extravagance when we collect data in the real-world. For example, suppose we would like to divide up a large...

Clustering techniques

In this section, we will discuss clustering techniques along with challenges and suitable examples. A brief overview of hierarchical clustering, centroid-based clustering, and distribution-based clustering will be provided too.

Unsupervised learning and the clustering

Clustering analysis is about dividing data samples or data points and putting them into corresponding homogeneous classes or clusters. Thus a trivial definition of clustering can be thought as the process of organizing objects into groups whose members are similar in some way.
A cluster is, therefore, a collection of objects that are similar between them and are dissimilar to the objects belonging to other clusters. As shown in Figure 2...

Centroid-based clustering (CC)

In this section, we discuss the centroid-based clustering technique and its computational challenges. An example of using K-means with Spark MLlib will be shown for a better understanding of the centroid-based clustering.

Challenges in CC algorithm

As discussed previously, in a centroid-based clustering algorithm like K-means, setting the optimal value of the number of clusters K is an optimization problem. This problem can be described as NP-hard (that is non-deterministic polynomial-time hard) featuring high algorithmic complexities, and thus the common approach is trying to achieve only an approximate solution. Consequently, solving these optimization problems imposes an extra burden and consequently...

Hierarchical clustering (HC)

In this section, we discuss the hierarchical clustering technique and its computational challenges. An example of using the bisecting K-means algorithm of hierarchical clustering with Spark MLlib will be shown too for a better understanding of hierarchical clustering.

An overview of HC algorithm and challenges

A hierarchical clustering technique is computationally different from the centroid-based clustering in the way the distances are computed. This is one of the most popular and widely used clustering analysis technique that looks to build a hierarchy of clusters. Since a cluster usually consists of multiple objects, there will be other candidates to compute the distance too. Therefore, with...

Distribution-based clustering (DC)

In this section, we will discuss the distribution-based clustering technique and its computational challenges. An example of using Gaussian mixture models (GMMs) with Spark MLlib will be shown for a better understanding of distribution-based clustering.

Challenges in DC algorithm

A distribution-based clustering algorithm like GMM is an expectation-maximization algorithm. To avoid the overfitting problem, GMM usually models the dataset with a fixed number of Gaussian distributions. The distributions are initialized randomly, and the related parameters are iteratively optimized too to fit the model better to the training dataset. This is the most robust feature of GMM and helps the model to...

Determining number of clusters

The beauty of clustering algorithms like K-means algorithm is that it does the clustering on the data with an unlimited number of features. It is a great tool to use when you have a raw data and would like to know the patterns in that data. However, deciding the number of clusters prior to doing the experiment might not be successful but may sometimes lead to an overfitting or underfitting problem. On the other hand, one common thing to all three algorithms (that is, K-means, bisecting K-means, and Gaussian mixture) is that the number of clusters must be determined in advance and supplied to the algorithm as a parameter. Hence, informally, determining the number of clusters is a separate optimization problem to be solved.

In this section, we will use a heuristic approach based on the Elbow method. We start from K = 2 clusters, and then we ran the...

A comparative analysis between clustering algorithms

Gaussian mixture is used mainly for expectation minimization, which is an example of an optimization algorithm. Bisecting K-means, which is faster than regular K-means, also produces slightly different clustering results. Below we try to compare these three algorithms. We will show a performance comparison in terms of model building time and the computional cost for each algorithm. As shown in the following code, we can compute the cost in terms of WCSS. The following lines of code can be used to compute the WCSS for the K-means and bisecting algorithms:

val WCSSS = model.computeCost(landRDD) // land RDD is the training set 
println("Within-Cluster Sum of Squares = " + WCSSS) // Less is better 

For the dataset we used throughout this chapter, we got the following values of WCSS:

Within-Cluster Sum of Squares of Bisecting...

Submitting Spark job for cluster analysis

The examples shown in this chapter can be made scalable for the even larger dataset to serve different purposes. You can package all three clustering algorithms with all the required dependencies and submit them as a Spark job in the cluster. Now use the following lines of code to submit your Spark job of K-means clustering, for example (use similar syntax for other classes), for the Saratoga NY Homes dataset:

# Run application as standalone mode on 8 cores 
SPARK_HOME/bin/spark-submit \   
--class org.apache.spark.examples.KMeansDemo \   
--master local[8] \   
KMeansDemo-0.1-SNAPSHOT-jar-with-dependencies.jar \   
Saratoga_NY_Homes.txt

# Run on a YARN cluster 
export HADOOP_CONF_DIR=XXX 
SPARK_HOME/bin/spark-submit \   
--class org.apache.spark.examples.KMeansDemo \   
--master yarn \   
--deploy-mode cluster \  # can be client for client mode...

Summary

In this chapter, we delved even deeper into machine learning and found out how we can take advantage of machine learning to cluster records belonging to a dataset of unsupervised observations. Consequently, you learnt the practical know-how needed to quickly and powerfully apply supervised and unsupervised techniques on available data to new problems through some widely used examples based on the understandings from the previous chapters. The examples we are talking about will be demonstrated from the Spark perspective. For any of the K-means, bisecting K-means, and Gaussian mixture algorithms, it is not guaranteed that the algorithm will produce the same clusters if run multiple times. For example, we observed that running the K-means algorithm multiple times with the same parameters generated slightly different results at each run.

For a performance comparison between...