Important Clustering Algorithms For Data Scientists In 2021

Introduction to Clustering Algorithms

What is clustering in data mining? ML (Machine Learning) uses the clustering algorithms technique to group data points. The clustering algorithm, when provided (set of) two data points, classifies each of these data points into specific groups. Theoretically, the same group data points in data mining clustering will have similar properties but use the and/or same features. Different group data have dissimilar properties and/or same/dissimilar features. Clustering is used in unsupervised learning for statistical data analysis, whose techniques are widely used across varied modern-day fields. The clustering algorithm is also used in data sciences to analyze and get gainful insights about the database clustering of data and its data-points group. 

Given below are 5- types of clustering algorithms that are a must for data scientists.

1. K-Means Clustering
2. Mean-Shift Clustering
3. DBSCAN- Density-Based Spatial Clustering of Applications with Noise
4. Expectation-Maximization (EM) Clustering using Gaussian Mixture Models (GMM)
5. Agglomerative Hierarchical Clustering

1) K-Means Clustering

K-Means is very popular in ML and data science learning as its clustering algorithm in data mining is easy to code and understand. It is performed as below.

• Select a number of groups/ classes based on distinctive grouping of data, and initialize the center points randomly.  All center points are represented by equal length vectors, while the data points are also vectors of varying lengths respective to the center. 
• Group classification is thus done using the closest center point to compute the data point’s distance.
• The group is recomputed with the classified points with the mean value vector defining the group.
• Such iterations are repeated until the group center value doesn’t change between iterations. One can also use iterations on random initialization of group centres to find the best run result of clustering data.

K-Means is fast and has a simple linear complexity of O(n), or distance of points from the center. The disadvantage is the inconsistencies caused by manual selection and classification of the classes and groups as also the random initialization of the centres providing inconsistent clustering results on different runs, non-repeatable results, etc. The K-Medians technique of the clustering algorithm uses the median group vector instead of iterating the group centres making the process less outlier-sensitive. However, this takes a lot of time when working with large data sets among the clustering algorithms since each iteration result will need the sorting process.

2) Mean-Shift Clustering

Mean shift clustering is a clustering algorithms technique wherein dense data point areas use a sliding-window centroid-based algorithm to locate the center group/class points. All center-point candidates are considered to be the mean value of the sliding-window points. Such windows are then sorted post-processing to remove duplicates and give the final set of group center points. It is achieved as below.

1. To begin with, a randomly selected circular sliding-window is defined as point C with kernel radius r. The hill-climbing mean shift algorithm shifts the kernel through successive iterations to regions having higher density and repeats the process till convergence is obtained.
2. In each step, the mean value of the points inside the window is used to move the mean center of the sliding window to high-density areas.
3. The density is proportional to the data points in it, and the mean value’s sliding window moved till it no longer accommodates any more data-points meaning no increase in data-points.
4. The iterations continue until all data points lie within its sliding window. If overlapping of multiple sliding windows occurs, the window having most data points is retained and data-points clustered as per their residing windows.

This method overcomes the selection of groups and cluster centres as the mean-values are discovered automatically. The clusters also exhibit data sense due to convergence to the areas having maximum data points intuitively. However, the radius definition of the window size can be non-trivial and disadvantageous types of clusters in data mining.

3) DBSCAN- Density-Based Spatial Clustering of Applications with Noise

The DBSCAN clustering algorithms technique is advantageous and similar to the mean-shift density-based clustered algorithm. 

The algorithm of DBSCAN takes an unvisited starting data-point arbitrarily and extracts the neighbourhood using distance ε (Epsilon) while marking the point as visited. All points are called neighbours if they reside within the distance.

1. When sufficient points (based on minPoints) are discovered, the clustering process begins with the new cluster’s first point being the current data point. If the number of points is insufficient, the algorithm marks it as visited and labels it as noise defect clustering.
2.  The first point of the new cluster uses the same distance ε to define its neighbourhood, thus creating an ε neighbourhood of clustered points, and the process repeats for all the new cluster points added to the group. This continues till all data points are labelled and visited.
3. When all points in the neighbourhood have been visited, a new unvisited data point is taken up for clustering. Thus all data points get marked as noise or are clustered under the visited label.

This method has the most robust clustering algorithms, which do not need the number of clusters to be preset. It can identify the noise outlier and the arbitrarily shaped, sized clusters, unlike the mean-shift technique. However, DBSCAN is a graph clustering algorithm non-performer with varying density clusters and high-dimensional data, since the cluster varies based on its minPoints and threshold distance ε, which varies when density changes occur. 

4) Expectation-Maximization (EM) Clustering using Gaussian Mixture Models (GMM)

One of the drawbacks of K-Means clustering algorithms is when two circular clusters centered at the same mean have different radii. K-Means uses median values to define the cluster center and doesn’t differentiate between the two clusters. It also fails when the sets are non-circular.

GMMs or Gaussian Mixture Models provide more flexibility since the Gaussian distributed data-points are not restricted to the definitions of using mean-value or being of circular shape. This method then has only two defining parameters, namely the standard deviation and the mean data-point, an elliptical shape, and can be used across Gaussian distributions on X or Y axes with the cluster defined by its distribution feature.

EM or Expectation–Maximization optimization algorithm finds the two parameters of the Gaussian distribution for each cluster and works as below. 

1. One has to select the number of clusters and initializing randomly the parameters of the Gaussian distribution for each cluster based on a guesstimate by looking through the data. The algorithm starts slowly and is quickly optimized based on the initial parameters defined.
2.  Given the cluster’s Gaussian distribution, the computation of probability takes place to check if the data point belongs to the defined cluster. The probability increases when the data point lies close to the Gaussian centre.
3. The next step uses a new optimized value for its parameters to increase the probability of the data point lying in the new cluster. These new parameters use the data points positional weighted sum, and the weights define the probability of the particular cluster containing the referenced data point.
4. The algorithm affects successive iterations till convergence is obtained until the changes between iterations become minimal.

The 2 key GMMs advantages are cluster covariance and flexibility in clustering algorithms. The standard deviation parameter means the cluster can take any shape making K-Means a clustering algorithms example of GMM over a circular distribution, while the use of probability means multiple clusters can exist at any given data point. When two distributions overlap, the clustering is defined by mixed membership as Y% to class-2 and X% to class-1.

5) Agglomerative Hierarchical Clustering

This method of clustering algorithms has categories, bottom-up and top-down. Bottom-up algorithms treat the data points as a single cluster till agglomeration merges clustered pairs to a single data point cluster. In HAC-hierarchical agglomerative clustering, a dendrogram or tree of network clustering is used, with the tree root being the unique sample gathering cluster and the leaves being single-sample clusters. The hybrid clustering algorithms process is similar and uses average linkage with a selected distance metric defining average distance of data points in a cluster pair and margining them till convergence is obtained by successive iterations.

Hierarchical clustering does not require us to specify the number of clusters, and we can even select which number of clusters looks best since we are building a tree. Additionally, the algorithm is not choice-of-distance-metric sensitive. It is, however, not very efficient and has a time complexity in the range of O(n³).

Conclusion

Hooray! These are the best of the 5-top clustering algorithms used in the clustering of data points.

If you are interested in making a career in the Data Science domain, our 11-month in-person PGDM in Data Science course can help you immensely in becoming a successful Data Science professional. 

ALSO READ

• RDBMS – A Comprehensive Guide (2021)