On Cluster-based Algorithms

I no longer post neuro/stroke-related blog, but more and more machine learning stuffs. Well, "Big Data" and AI/Machine Learning have entered a new beginning worldwide; it becomes a trend now. And this post is inspired by what I found from several online sources regarding clustering algorithms.

What and Why?
Generally speaking, cluster analysis means you group the dataset into different groups or clusters. It is commonly used to identify the underlying structures or patterns in the data. Cluster types are usually not known beforehand. Technically, any cluster-based algorithms try to maximize within-group similarity and maximize between-group distance. In machine learning, clustering is considered unsupervised learning, i.e. an algorithm that tries to discover unknown patterns in the dataset without any known reference (teacher), or prior knowledge of the labels. Lastly, clustering is related to a similar (but not the same!) algorithm called 'classification' which works on reference or labeled data through supervised learning processes. Look at the table below.

Cluster analyses have been widely used in data mining, biomedical research (genetic sequencing, phylogenetic, evolution), image processing, business analytics and social media, etc.

About k-means Algorithm
Let's talk about one of the most popular unsupervised learning algorithms out there, the k-means. This algorithm tries to partition the dataset into k distinct clusters (sub-groups), where each point or observation belongs to only one cluster. Before running the iteration, pre-processing ensures that the dataset belongs to the same scale on the coordinates. If these data points are not normalized, then it may lead to false grouping. Often, missing values are sometimes suboptimal to clustering.

Once your data is ready, we will start the k-means. As with any machine learning techniques, k-means involves an iterative process up to a termination point. In each iteration, it computes the cluster’s centroid, which is the arithmetic mean of all the data points that belong to that cluster.

Step1: Define the number of clusters, k.
Step2: Randomly select k different points to serve as the cluster centroid.
Step3: Assign all other data points to a cluster whose centroid is the nearest.
Step4: After that, calculate the new centroid position for each cluster.
Step5: Repeat Step 3 & 4 until the process reaches the termination criteria.

Objective: to minimize the sum of the squared within-cluster distance, that is, the
Euclidean distance between the data points and the cluster’s centroid.Termination criteria may include: centroids location do not change after some iterations, data points remain in the same cluster, or the user-defined max. number of iterations (e.g. 100) has been reached.

Refer to the GIF animation below. Each centroid is depicted as a white cross. Prior to grouping, data points are still black in color. After the grouping is done, the data points change color accordingly. In each iteration, k-means minimizes the total within-cluster distance which results in a new centroid location, and a shift in the color shade after. Indeed, some points can be reassigned to a different cluster in each iteration. The right panel shows what is known as the "Elbow method" (Fig-1).

Fig-1: Step-by-step process showing k-means clustering algorithm and its performance indicator (*).

In another example below, the initial guess produces three centroid locations in the left panel. The right panel shows the final outcome.

Fig-2: Initial and final centroid position of three different clusters (k = 3) after the iteration process stopped.

where w_ik= 1 for point x_i if it belongs to a certain cluster k; otherwise, w_ik= 0; and μ_k is the centroid of the x_i’s cluster. Minimizing this function contains two parts: first we differentiate J with respect to w_ik first and update the cluster assignments. Following this, we differentiate J with respect to μ_k, and recompute the centroids after the cluster assignments from the previous step.

How do we know whether our k-means has done a good job? Although a visual inspection is easy, one quantitative way is to see whether the # of clusters is already 'good enough' by using some evaluation metrics.

The first type is called the elbow-method, which uses the within-cluster sum of squared distance mentioned earlier. As shown in the figure above, the "elbow" here refers to the profound deflection downward that signifies a maximum improvement in the sum of squared distance. It is crucial to note that this metric continues to decrease monotonically as k increases.

The silhouette method, on the other hand, determines the degree of separation between clusters. It computes a certain coefficient whose value can take up anything in the interval [-1, 1]. Therefore, ideally the value should be as big as possible and closer to 1 to have a good clustering.

Hierarchical Clustering
In hierarchical clustering (HC), grouping is done in steps between two closest or most similar points, to produce certain hierarchy that is depicted as a dendrogram. There are essentially two techniques, the more popular agglomerative HC (bottom-up approach) and the divisive HC (top-down approach). Refer to the following Fig-3 for an illustration.

Fig-3: Two main types of hierarchical clustering, a different way of doing cluster-based analysis (tds com).

Refer to the nice GIF animation below with the different colors in each iteration. The vertical axis is a measure of similarity or closeness of either individual data points or clusters. The height of this vertical axis (Fig. 4) represents the Euclidean distance between the relevant data items grouped together.

Fig-4: Step-by-step process showing agglomerative HC algorithm and its dendrogram with colour-coding (*).

Suppose we work with the agglomerative HC:

Step1: Begin by treating each data point or observation as a separate cluster.
Step2: Compute a distance metric to identify the two points that are closest together.
Step3: Then, merge two points as a new cluster (linkage).
Step4: Repeat Step 2 & 3 for any pair of clusters obtained earlier until it reaches k clusters.

A set of distance or proximity metric between two data points/clusters is used, such as Euclidean distance, maximum distance, Manhattan distance, cosine distance, etc. This matrix is updated in each iteration to display the distance between the pair. 

The order in which clusters are joined is controlled by the linkage methods, meaning the manner you link the two clusters and categorize them hierarchically. There are generally 3 types of linkage in HC, the choice of which is up to us:
   (a) Single linkage: nearest-neighbour distance.
   (b) Complete linkage: furthest-neighbour distance.
   (c) Average linkage: taking the average distance.
   (d) Ward's method: taking the minimum sum of squared distance.

With the Ward's method, the sum of squares starts out at zero, because every point is in its own cluster. It then grows as more clusters are merged in the second iteration (each cluster now consists of more data). Given two pairs of clusters whose centers are equally far apart, Ward’s method will prefer to merge the smaller ones.
Refer to the diagram for more information on the agglomerative hierarchical clustering.


Final notes: Model-based approach
Now let's contrast the two algorithms. Clustering results are much more reproducible (consistent) in the HC if we were to repeat the analysis multiple times. Conversely, different results can be obtained in k-means since we started of with random centroids for every fresh analysis. Care should then be taken in choosing which algorithm and in interpreting the results. Another thing to note is that HC is computationally expensive and cannot handle big data well, but k-means clustering can. The time complexity of k-means is linear, i.e. O(n); while that of HC follows power rule, i.e. O(n²).

Although the k-means algorithm is popular, it suffers some drawbacks. First, the shape of the data is best to be spherical. It will be sub-optimal when the shape of data deviates from spherical shapes. Moreover, it will be confused when there are potentially two overlapping clusters as there is no obvious measure of uncertainty. This is because k-means is hard clustering, no way for a probabilistic partitioning. Lastly, although some methods exist to 'predict' the best number of clusters, it does not know the number of clusters from the data and requires it to be pre-defined.

Traditional clustering algorithms presented here are heuristic-based algorithms that derive clusters directly based on the data. In contrast, another form of clustering, model-based clustering attempts to address this concern and provide a soft assignment where observations have a probability of belonging to each cluster, hence, incorporating a measure of probability or uncertainty to the cluster assignments. For high-dimensional data, model-based approaches are preferred with some iterative methods called the Expectation-Maximization (EM). Unlike the k-means method which uses the Euclidean distance while calculating the distance between each point, the EM method uses more sophisticated statistical models, Gaussian Mixture Model (GMM), so making this a model-based approach. 

Briefly, the EM algorithm is often used to provide the functions more effectively. In the E-step, data points are assigned to the closest cluster according to the highest likelihood. In the M-step, the new centroid of each cluster is computed. In other words, assign the data point x_i to the closest cluster judged by its sum of squared distance from the cluster’s centroid. Iteration stops if the likelihood converges or stabilizes.

(*) Nice tutorial on k-Means
[*] Image source: Giphy website.