K- Means Clustering Applications

k-means clustering is rather easy to apply to even large data sets, particularly when using heuristics such as Lloyd's algorithm. It has been successfully used in market segmentation, computer vision, and astronomy among many other domains. It often is used as a preprocessing step for other algorithms, for example to find a starting configuration.

Vector quantization

k-means originates from signal processing, and still finds use in this domain. For example, in computer graphics, color quantization is the task of reducing the color palette of an image to a fixed number of colors k. The k-means algorithm can easily be used for this task and produces competitive results. A use case for this approach is image segmentation. Other uses of vector quantization include non-random sampling, as k-means can easily be used to choose k different but prototypical objects from a large data set for further analysis.

Cluster analysis

In cluster analysis, the k-means algorithm can be used to partition the input data set into k partitions
(clusters).

However, the pure k-means algorithm is not very flexible, and as such is of limited use (except for when vector quantization as above is actually the desired use case). In particular, the parameter k is known to be hard to choose (as discussed above) when not given by external constraints. Another limitation is that it cannot be used with arbitrary distance functions or on non-numerical data. For these use cases, many other algorithms are superior.

Feature learning

k-means clustering has been used as a feature learning (or dictionary learning) step, in either (semi-)supervised learning or unsupervised learning. The basic approach is first to train a k-means clustering representation, using the input training data (which need not be labelled). Then, to project any input datum into the new feature space, an "encoding" function, such as the thresholded matrix-product of the datum with the centroid locations, computes the distance from the datum to each centroid, or simply an indicator function for the nearest centroid, or some smooth transformation of the distance. Alternatively, transforming the sample-cluster distance through a Gaussian RBF, obtains the hidden layer of a radial basis function network.

This use of k-means has been successfully combined with simple, linear classifiers for
semi-supervised learning in NLP (specifically for named entity recognition)and in computer vision. On an object recognition task, it was found to exhibit comparable performance with more sophisticated feature learning approaches such as autoencoders and restricted Boltzmann machines. However, it generally requires more data, for equivalent performance, because each data point only contributes to one "feature".

 

 

 

Software implementations

The following implementations are available under Free/Open Source Software licenses,with publicly available source code.

-     Accord.NET contains C# implementations for k-means, k-means++ and k-modes.

-     ALGLIB contains parallelized C++ and C# implementations for k-means and k-means++.

-     AOSP contains a Java implementation for k-means.

-     CrimeStat implements two spatial k-means algorithms, one of which allows the user to define the starting locations.

-     ELKI contains k-means (with Lloyd and MacQueen iteration, along with different initializations such as k-means++ initialization) and various more advanced clustering algorithms.

-     Julia contains a k-means implementation in the JuliaStats Clustering package.

-     KNIME contains nodes for k-means and k-medoids.

-    Mahout contains a MapReduce based k-means.

-    mlpack contains a C++ implementation of k-means.

-    Octave contains k-means.

-     OpenCV contains a k-means implementation.

-     Orange includes a component for k-means clustering with automatic selection of k and cluster silhouette scoring.

-     PSPP contains k-means, The QUICK CLUSTER command performs k-means clustering on the dataset.

-     R contains three k-means variations.

-     SciPy and scikit-learn contain multiple k-means implementations.

-     Spark MLlib implements a distributed k-means algorithm.

-     Torch contains an unsup package that provides k-means clustering.

-     Weka contains k-means and x-means.

...

Happy Pythoning...!!!