clustering methods in machine learning

 

Different Clustering Methods

Hierarchical Methods

• Agglomerative hierarchical clustering — Each object initially represents a cluster of its own. Then clusters are successively merged until the desired cluster structure is obtained. 
• Divisive hierarchical clustering — All objects initially belong to one cluster. Then the cluster is divided into sub-clusters, which are successively divided into their own sub-clusters. This process continues until the desired cluster structure is obtained.

The hierarchical clustering methods could be further divided according to the manner that the similarity measure is calculated

• Single-link clustering (also called the connectedness, the minimum method or the nearest neighbor method) — methods that consider the distance between two clusters to be equal to the shortest distance from any member of one cluster to any member of the other cluster. If the data consist of similarities, the similarity between a pair of clusters is considered to be equal to the greatest similarity from any member of one cluster to any member of the other cluster.
• Complete-link clustering (also called the diameter, the maximum method or the furthest neighbor method) - methods that consider the distance between two clusters to be equal to the longest distance from any member of one cluster to any member of the other cluster.
• Average-link clustering (also called minimum variance method) - methods that consider the distance between two clusters to be equal to the average distance from any member of one cluster to any member of the other cluster. 

Generally, hierarchical methods are characterized with the following strengths: 

• Versatility — The single-link methods, for example, maintain good performance on data sets containing non-isotropic clusters, including wellseparated, chain-like and concentric clusters. 
• Multiple partitions — hierarchical methods produce not one partition, but multiple nested partitions, which allow different users to choose different partitions, according to the desired similarity level. 

The main disadvantages of the hierarchical methods are: 

• Inability to scale well — The time complexity of hierarchical algorithms is at least O (m2 ) (where m is the total number of instances), which is non-linear with the number of objects. Clustering a large number of objects using a hierarchical algorithm is also characterized by huge I/O costs. 
• Hierarchical methods can never undo what was done previously. Namely there is no back-tracking capability.

K - Means Clustering

This algorithm partitions the data into K clusters (C1, C2, . . . , CK), represented by their centers or means. The center of each cluster is calculated as the mean of all the instances belonging to that cluster.

The algorithm starts with an initial set of cluster centers, chosen at random or according to some heuristic procedure. In each iteration, each instance is assigned to its nearest cluster center according to the Euclidean distance between the two. Then the cluster centers are re-calculated. The center of each cluster is calculated as the mean of all the instances belonging to that cluster.

A number of convergence conditions are possible. For example, the search may stop when the partitioning error is not reduced by the relocation of the centers. This indicates that the present partition is locally optimal. Other stopping criteria can be used also such as exceeding a pre-defined number of iterations. 

Input: S (instance set), K (number of cluster)

Output: clusters

1. : Initialize K cluster centers.
2. : while termination condition is not satisfied do
3. : Assign instances to the closest cluster center.
4. : Update cluster centers based on the assignment.
5. : end while

The K-means algorithm may be viewed as a gradient-decent procedure, which begins with an initial set of K cluster-centers and iteratively updates it so as to decrease the error function. 

 The complexity of T iterations of the K-means algorithm performed on a sample size of m instances, each characterized by N attributes, is: O(T ∗ K ∗ m ∗ N). This linear complexity is one of the reasons for the popularity of the Kmeans algorithms. Even if the number of instances is substantially large, this algorithm is computationally attractive. Thus, the K-means algorithm has an advantage in comparison to other clustering methods (e.g. hierarchical clustering methods), which have non-linear complexity.

Other reasons for the algorithm’s popularity are its ease of interpretation,simplicity of implementation, speed of convergence and adaptability to sparse data. In addition, this algorithm is sensitive to noisy data and outliers (a single outlier can increase the squared error dramatically); it is applicable only when mean is defined (namely, for numeric attributes);and it requires the number of clusters in advance, which is not trivial when no prior knowledge is available. The use of the K-means algorithm is often limited to numeric attributes.

Graph-Theoretic Clustering

Graph theoretic methods are methods that produce clusters via graphs. The edges of the graph connect Inconsistent edges are edges whose weight (in the case of clustering-length) is significantly larger than the average of nearby edge lengths.

Density-based Methods

Density-based methods assume that the points that belong to each cluster are drawn from a specific probability distribution. The overall distribution of the data is assumed to be a mixture of several distributions. The aim of these methods is to identify the clusters and their distribution parameters. These methods are designed for discovering clusters of arbitrary shape.
The idea is to continue growing the given cluster as long as the density (number of objects or data points) in the neighborhood exceeds some threshold. Namely, the neighborhood of a given radius has to contain at least a minimum number of objects. When each cluster is characterized by local mode or maxima of the density function, these methods are called mode-seeking.

Model-based Clustering Methods

These methods attempt to optimize the fit between the given data and some mathematical models. Unlike conventional clustering, which identifies groups of objects, model-based clustering methods also find characteristic descriptions for each group, where each group represents a concept or class. The most frequently used induction methods are decision trees and neural networks.

Decision Trees 

In decision trees, the data is represented by a hierarchical tree, where each leaf refers to a concept and contains a probabilistic description of that concept.

Neural Networks

This type of algorithm represents each cluster by a neuron or “prototype”. The input data is also represented by neurons, which are connected to the prototype neurons. Each such connection has a weight, which is learned adaptively during learning. 
A very popular neural algorithm for clustering is the self-organizing map (SOM). This algorithm constructs a single-layered network. The learning process takes place in a “winner-takes-all” fashion: 

• The prototype neurons compete for the current instance. The winner is the neuron whose weight vector is closest to the instance currently presented. 
• The winner and its neighbors learn by having their weights adjusted. 

The SOM algorithm is successfully used for vector quantization and speech recognition. It is useful for visualizing high-dimensional data in 2D or 3D space. However, it is sensitive to the initial selection of weight vector, as well as to its different parameters, such as the learning rate and neighborhood radius.