smile.clustering
Clustering analysis. Clustering is the assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense. Clustering is a method of unsupervised learning, and a common technique for statistical data analysis used in many fields.
Hierarchical algorithms find successive clusters using previously established clusters. These algorithms usually are either agglomerative ("bottomup") or divisive ("topdown"). Agglomerative algorithms begin with each element as a separate cluster and merge them into successively larger clusters. Divisive algorithms begin with the whole set and proceed to divide it into successively smaller clusters.
Partitional algorithms typically determine all clusters at once, but can also be used as divisive algorithms in the hierarchical clustering. Many partitional clustering algorithms require the specification of the number of clusters to produce in the input data set, prior to execution of the algorithm. Barring knowledge of the proper value beforehand, the appropriate value must be determined, a problem on its own for which a number of techniques have been developed.
Densitybased clustering algorithms are devised to discover arbitraryshaped clusters. In this approach, a cluster is regarded as a region in which the density of data objects exceeds a threshold.
Subspace clustering methods look for clusters that can only be seen in a particular projection (subspace, manifold) of the data. These methods thus can ignore irrelevant attributes. The general problem is also known as Correlation clustering while the special case of axisparallel subspaces is also known as twoway clustering, coclustering or biclustering in bioinformatics: in these methods not only the objects are clustered but also the features of the objects, i.e., if the data is represented in a data matrix, the rows and columns are clustered simultaneously. They usually do not however work with arbitrary feature combinations as in general subspace methods.
Attributes
Members list
Type members
Classlikes
Hacking scaladoc issue8124. The user should ignore this object.
Hacking scaladoc issue8124. The user should ignore this object.
Attributes
 Supertypes

class Objecttrait Matchableclass Any
 Self type

$dummy.type
Value members
Concrete methods
Clustering Large Applications based upon RANdomized Search. CLARANS is an efficient medoidbased clustering algorithm. The kmedoids algorithm is an adaptation of the kmeans algorithm. Rather than calculate the mean of the items in each cluster, a representative item, or medoid, is chosen for each cluster at each iteration. In CLARANS, the process of finding k medoids from n objects is viewed abstractly as searching through a certain graph. In the graph, a node is represented by a set of k objects as selected medoids. Two nodes are neighbors if their sets differ by only one object. In each iteration, CLARANS considers a set of randomly chosen neighbor nodes as candidate of new medoids. We will move to the neighbor node if the neighbor is a better choice for medoids. Otherwise, a local optima is discovered. The entire process is repeated multiple time to find better.
Clustering Large Applications based upon RANdomized Search. CLARANS is an efficient medoidbased clustering algorithm. The kmedoids algorithm is an adaptation of the kmeans algorithm. Rather than calculate the mean of the items in each cluster, a representative item, or medoid, is chosen for each cluster at each iteration. In CLARANS, the process of finding k medoids from n objects is viewed abstractly as searching through a certain graph. In the graph, a node is represented by a set of k objects as selected medoids. Two nodes are neighbors if their sets differ by only one object. In each iteration, CLARANS considers a set of randomly chosen neighbor nodes as candidate of new medoids. We will move to the neighbor node if the neighbor is a better choice for medoids. Otherwise, a local optima is discovered. The entire process is repeated multiple time to find better.
CLARANS has two parameters: the maximum number of neighbors examined (maxNeighbor) and the number of local minima obtained (numLocal). The higher the value of maxNeighbor, the closer is CLARANS to PAM, and the longer is each search of a local minima. But the quality of such a local minima is higher and fewer local minima needs to be obtained.
====References:====
 R. Ng and J. Han. CLARANS: A Method for Clustering Objects for Spatial Data Mining. IEEE TRANS. KNOWLEDGE AND DATA ENGINEERING, 2002.
Value parameters
 data

the data set.
 distance

the distance/dissimilarity measure.
 k

the number of clusters.
 maxNeighbor

the maximum number of neighbors examined during a random search of local minima.
 numLocal

the number of local minima to search for.
Attributes
Deterministic annealing clustering. Deterministic annealing extends softclustering to an annealing process. For each temperature value, the algorithm iterates between the calculation of all posteriori probabilities and the update of the centroids vectors, until convergence is reached. The annealing starts with a high temperature. Here, all centroids vectors converge to the center of the pattern distribution (independent of their initial positions). Below a critical temperature the vectors start to split. Further decreasing the temperature leads to more splittings until all centroids vectors are separate. The annealing can therefore avoid (if it is sufficiently slow) the convergence to local minima.
Deterministic annealing clustering. Deterministic annealing extends softclustering to an annealing process. For each temperature value, the algorithm iterates between the calculation of all posteriori probabilities and the update of the centroids vectors, until convergence is reached. The annealing starts with a high temperature. Here, all centroids vectors converge to the center of the pattern distribution (independent of their initial positions). Below a critical temperature the vectors start to split. Further decreasing the temperature leads to more splittings until all centroids vectors are separate. The annealing can therefore avoid (if it is sufficiently slow) the convergence to local minima.
====References:====
 Kenneth Rose. Deterministic Annealing for Clustering, Compression, Classification, Regression, and Speech Recognition.
Value parameters
 alpha

the temperature T is decreasing as T = T * alpha. alpha has to be in (0, 1).
 data

the data set.
 k

the maximum number of clusters.
 splitTol

the tolerance to split a cluster.
 tol

the tolerance of convergence test.
Attributes
DensityBased Spatial Clustering of Applications with Noise. DBSCAN finds a number of clusters starting from the estimated density distribution of corresponding nodes.
DensityBased Spatial Clustering of Applications with Noise. DBSCAN finds a number of clusters starting from the estimated density distribution of corresponding nodes.
DBSCAN requires two parameters: radius (i.e. neighborhood radius) and the number of minimum points required to form a cluster (minPts). It starts with an arbitrary starting point that has not been visited. This point's neighborhood is retrieved, and if it contains sufficient number of points, a cluster is started. Otherwise, the point is labeled as noise. Note that this point might later be found in a sufficiently sized radiusenvironment of a different point and hence be made part of a cluster.
If a point is found to be part of a cluster, its neighborhood is also part of that cluster. Hence, all points that are found within the neighborhood are added, as is their own neighborhood. This process continues until the cluster is completely found. Then, a new unvisited point is retrieved and processed, leading to the discovery of a further cluster of noise.
DBSCAN visits each point of the database, possibly multiple times (e.g., as candidates to different clusters). For practical considerations, however, the time complexity is mostly governed by the number of nearest neighbor queries. DBSCAN executes exactly one such query for each point, and if an indexing structure is used that executes such a neighborhood query in O(log n), an overall runtime complexity of O(n log n) is obtained.
DBSCAN has many advantages such as
 DBSCAN does not need to know the number of clusters in the data a priori, as opposed to kmeans.
 DBSCAN can find arbitrarily shaped clusters. It can even find clusters completely surrounded by (but not connected to) a different cluster. Due to the MinPts parameter, the socalled singlelink effect (different clusters being connected by a thin line of points) is reduced.
 DBSCAN has a notion of noise.
 DBSCAN requires just two parameters and is mostly insensitive to the ordering of the points in the database. (Only points sitting on the edge of two different clusters might swap cluster membership if the ordering of the points is changed, and the cluster assignment is unique only up to isomorphism.)
On the other hand, DBSCAN has the disadvantages of
 In high dimensional space, the data are sparse everywhere because of the curse of dimensionality. Therefore, DBSCAN doesn't work well on highdimensional data in general.
 DBSCAN does not respond well to data sets with varying densities.
====References:====
 Martin Ester, HansPeter Kriegel, Jorg Sander, Xiaowei Xu (1996). A densitybased algorithm for discovering clusters in large spatial databases with noise". KDD, 1996.
 Jorg Sander, Martin Ester, HansPeter Kriegel, Xiaowei Xu. (1998). DensityBased Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. 1998.
Value parameters
 data

the data set.
 minPts

the minimum number of neighbors for a core data point.
 nns

the data structure for neighborhood search.
 radius

the neighborhood radius.
Attributes
DensityBased Spatial Clustering of Applications with Noise. DBSCAN finds a number of clusters starting from the estimated density distribution of corresponding nodes.
DensityBased Spatial Clustering of Applications with Noise. DBSCAN finds a number of clusters starting from the estimated density distribution of corresponding nodes.
Value parameters
 data

the data set.
 distance

the distance metric.
 minPts

the minimum number of neighbors for a core data point.
 radius

the neighborhood radius.
Attributes
DBSCAN with Euclidean distance. DBSCAN finds a number of clusters starting from the estimated density distribution of corresponding nodes.
DBSCAN with Euclidean distance. DBSCAN finds a number of clusters starting from the estimated density distribution of corresponding nodes.
Value parameters
 data

the data set.
 minPts

the minimum number of neighbors for a core data point.
 radius

the neighborhood radius.
Attributes
DENsity CLUstering. The DENCLUE algorithm employs a cluster model based on kernel density estimation. A cluster is defined by a local maximum of the estimated density function. Data points going to the same local maximum are put into the same cluster.
DENsity CLUstering. The DENCLUE algorithm employs a cluster model based on kernel density estimation. A cluster is defined by a local maximum of the estimated density function. Data points going to the same local maximum are put into the same cluster.
Clearly, DENCLUE doesn't work on data with uniform distribution. In high dimensional space, the data always look like uniformly distributed because of the curse of dimensionality. Therefore, DENCLUDE doesn't work well on highdimensional data in general.
====References:====
 A. Hinneburg and D. A. Keim. A general approach to clustering in large databases with noise. Knowledge and Information Systems, 5(4):387415, 2003.
 Alexander Hinneburg and HansHenning Gabriel. DENCLUE 2.0: Fast Clustering based on Kernel Density Estimation. IDA, 2007.
Value parameters
 data

the data set.
 m

the number of selected samples used in the iteration. This number should be much smaller than the number of data points to speed up the algorithm. It should also be large enough to capture the sufficient information of underlying distribution.
 sigma

the smooth parameter in the Gaussian kernel. The user can choose sigma such that number of density attractors is constant for a long interval of sigma.
Attributes
GMeans clustering algorithm, an extended KMeans which tries to automatically determine the number of clusters by normality test. The Gmeans algorithm is based on a statistical test for the hypothesis that a subset of data follows a Gaussian distribution. Gmeans runs kmeans with increasing k in a hierarchical fashion until the test accepts the hypothesis that the data assigned to each kmeans center are Gaussian.
GMeans clustering algorithm, an extended KMeans which tries to automatically determine the number of clusters by normality test. The Gmeans algorithm is based on a statistical test for the hypothesis that a subset of data follows a Gaussian distribution. Gmeans runs kmeans with increasing k in a hierarchical fashion until the test accepts the hypothesis that the data assigned to each kmeans center are Gaussian.
====References:====
 G. Hamerly and C. Elkan. Learning the k in kmeans. NIPS, 2003.
Value parameters
 data

the data set.
 k

the maximum number of clusters.
Attributes
Agglomerative Hierarchical Clustering. This method seeks to build a hierarchy of clusters in a bottom up approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. The results of hierarchical clustering are usually presented in a dendrogram.
Agglomerative Hierarchical Clustering. This method seeks to build a hierarchy of clusters in a bottom up approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. The results of hierarchical clustering are usually presented in a dendrogram.
In general, the merges are determined in a greedy manner. In order to decide which clusters should be combined, a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate metric, and a linkage criteria which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets.
Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances.
== References ==
 David Eppstein. Fast hierarchical clustering and other applications of dynamic closest pairs. SODA 1998.
Value parameters
 data

The data set.
 method

the agglomeration method to merge clusters. This should be one of "single", "complete", "upgma", "upgmc", "wpgma", "wpgmc", and "ward".
Attributes
Agglomerative Hierarchical Clustering. This method seeks to build a hierarchy of clusters in a bottom up approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. The results of hierarchical clustering are usually presented in a dendrogram.
Agglomerative Hierarchical Clustering. This method seeks to build a hierarchy of clusters in a bottom up approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy. The results of hierarchical clustering are usually presented in a dendrogram.
In general, the merges are determined in a greedy manner. In order to decide which clusters should be combined, a measure of dissimilarity between sets of observations is required. In most methods of hierarchical clustering, this is achieved by use of an appropriate metric, and a linkage criteria which specifies the dissimilarity of sets as a function of the pairwise distances of observations in the sets.
Hierarchical clustering has the distinct advantage that any valid measure of distance can be used. In fact, the observations themselves are not required: all that is used is a matrix of distances.
== References ==
 David Eppstein. Fast hierarchical clustering and other applications of dynamic closest pairs. SODA 1998.
Value parameters
 data

The data set.
 distance

the distance/dissimilarity measure.
 method

the agglomeration method to merge clusters. This should be one of "single", "complete", "upgma", "upgmc", "wpgma", "wpgmc", and "ward".
Attributes
KMeans clustering. The algorithm partitions n observations into k clusters in which each observation belongs to the cluster with the nearest mean. Although finding an exact solution to the kmeans problem for arbitrary input is NPhard, the standard approach to finding an approximate solution (often called Lloyd's algorithm or the kmeans algorithm) is used widely and frequently finds reasonable solutions quickly.
KMeans clustering. The algorithm partitions n observations into k clusters in which each observation belongs to the cluster with the nearest mean. Although finding an exact solution to the kmeans problem for arbitrary input is NPhard, the standard approach to finding an approximate solution (often called Lloyd's algorithm or the kmeans algorithm) is used widely and frequently finds reasonable solutions quickly.
However, the kmeans algorithm has at least two major theoretic shortcomings:
 First, it has been shown that the worst case running time of the algorithm is superpolynomial in the input size.
 Second, the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal learn.
In this implementation, we use kmeans++ which addresses the second of these obstacles by specifying a procedure to initialize the cluster centers before proceeding with the standard kmeans optimization iterations. With the kmeans++ initialization, the algorithm is guaranteed to find a solution that is O(log k) competitive to the optimal kmeans solution.
We also use kd trees to speed up each kmeans step as described in the filter algorithm by Kanungo, et al.
Kmeans is a hard clustering method, i.e. each sample is assigned to a specific cluster. In contrast, soft clustering, e.g. the ExpectationMaximization algorithm for Gaussian mixtures, assign samples to different clusters with different probabilities.
====References:====
 Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. An Efficient kMeans Clustering Algorithm: Analysis and Implementation. IEEE TRANS. PAMI, 2002.
 D. Arthur and S. Vassilvitskii. "Kmeans++: the advantages of careful seeding". ACMSIAM symposium on Discrete algorithms, 10271035, 2007.
 Anna D. Peterson, Arka P. Ghosh and Ranjan Maitra. A systematic evaluation of different methods for initializing the Kmeans clustering algorithm. 2010.
This method runs the algorithm for given times and return the best one with smallest distortion.
Value parameters
 data

the data set.
 k

the number of clusters.
 maxIter

the maximum number of iterations for each running.
 runs

the number of runs of KMeans algorithm.
 tol

the tolerance of convergence test.
Attributes
KModes clustering. KModes is the binary equivalent for KMeans. The mean update for centroids is replace by the mode one which is a majority vote among element of each cluster.
KModes clustering. KModes is the binary equivalent for KMeans. The mean update for centroids is replace by the mode one which is a majority vote among element of each cluster.
Attributes
Nonparametric Minimum Conditional Entropy Clustering. This method performs very well especially when the exact number of clusters is unknown. The method can also correctly reveal the structure of data and effectively identify outliers simultaneously.
Nonparametric Minimum Conditional Entropy Clustering. This method performs very well especially when the exact number of clusters is unknown. The method can also correctly reveal the structure of data and effectively identify outliers simultaneously.
The clustering criterion is based on the conditional entropy H(C  x), where C is the cluster label and x is an observation. According to Fano's inequality, we can estimate C with a low probability of error only if the conditional entropy H(C  X) is small. MEC also generalizes the criterion by replacing Shannon's entropy with HavrdaCharvat's structural αentropy. Interestingly, the minimum entropy criterion based on structural αentropy is equal to the probability error of the nearest neighbor method when α= 2. To estimate p(C  x), MEC employs Parzen density estimation, a nonparametric approach.
MEC is an iterative algorithm starting with an initial partition given by any other clustering methods, e.g. kmeans, CLARNAS, hierarchical clustering, etc. Note that a random initialization is NOT appropriate.
====References:====
 Haifeng Li. All rights reserved., Keshu Zhang, and Tao Jiang. Minimum Entropy Clustering and Applications to Gene Expression Analysis. CSB, 2004.
Value parameters
 data

the data set.
 distance

the distance measure for neighborhood search.
 k

the number of clusters. Note that this is just a hint. The final number of clusters may be less.
 radius

the neighborhood radius.
Attributes
Nonparametric Minimum Conditional Entropy Clustering.
Nonparametric Minimum Conditional Entropy Clustering.
Value parameters
 data

the data set.
 distance

the distance measure for neighborhood search.
 k

the number of clusters. Note that this is just a hint. The final number of clusters may be less.
 radius

the neighborhood radius.
Attributes
Nonparametric Minimum Conditional Entropy Clustering. Assume Euclidean distance.
Nonparametric Minimum Conditional Entropy Clustering. Assume Euclidean distance.
Value parameters
 data

the data set.
 k

the number of clusters. Note that this is just a hint. The final number of clusters may be less.
 radius

the neighborhood radius.
Attributes
Nonparametric Minimum Conditional Entropy Clustering.
Nonparametric Minimum Conditional Entropy Clustering.
Value parameters
 data

the data set.
 k

the number of clusters. Note that this is just a hint. The final number of clusters may be less.
 nns

the data structure for neighborhood search.
 radius

the neighborhood radius.
 tol

the tolerance of convergence test.
Attributes
The Sequential Information Bottleneck algorithm. SIB clusters cooccurrence data such as text documents vs words. SIB is guaranteed to converge to a local maximum of the information. Moreover, the time and space complexity are significantly improved in contrast to the agglomerative IB algorithm.
The Sequential Information Bottleneck algorithm. SIB clusters cooccurrence data such as text documents vs words. SIB is guaranteed to converge to a local maximum of the information. Moreover, the time and space complexity are significantly improved in contrast to the agglomerative IB algorithm.
In analogy to KMeans, SIB's update formulas are essentially same as the EM algorithm for estimating finite Gaussian mixture model by replacing regular Euclidean distance with KullbackLeibler divergence, which is clearly a better dissimilarity measure for cooccurrence data. However, the common batch updating rule (assigning all instances to nearest centroids and then updating centroids) of KMeans won't work in SIB, which has to work in a sequential way (reassigning (if better) each instance then immediately update related centroids). It might be because KL divergence is very sensitive and the centroids may be significantly changed in each iteration in batch updating rule.
Note that this implementation has a little difference from the original paper, in which a weighted JensenShannon divergence is employed as a criterion to assign a randomlypicked sample to a different cluster. However, this doesn't work well in some cases as we experienced probably because the weighted JS divergence gives too much weight to clusters which is much larger than a single sample. In this implementation, we instead use the regular/unweighted JensenShannon divergence.
====References:====
 N. Tishby, F.C. Pereira, and W. Bialek. The information bottleneck method. 1999.
 N. Slonim, N. Friedman, and N. Tishby. Unsupervised document classification using sequential information maximization. ACM SIGIR, 2002.
 Jaakko Peltonen, Janne Sinkkonen, and Samuel Kaski. Sequential information bottleneck for finite data. ICML, 2004.
Value parameters
 data

the data set.
 k

the number of clusters.
 maxIter

the maximum number of iterations.
 runs

the number of runs of SIB algorithm.
Attributes
Spectral Clustering. Given a set of data points, the similarity matrix may be defined as a matrix S where S_{ij} represents a measure of the similarity between points. Spectral clustering techniques make use of the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions. Then the clustering will be performed in the dimensionreduce space, in which clusters of nonconvex shape may become tight. There are some intriguing similarities between spectral clustering methods and kernel PCA, which has been empirically observed to perform clustering.
Spectral Clustering. Given a set of data points, the similarity matrix may be defined as a matrix S where S_{ij} represents a measure of the similarity between points. Spectral clustering techniques make use of the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions. Then the clustering will be performed in the dimensionreduce space, in which clusters of nonconvex shape may become tight. There are some intriguing similarities between spectral clustering methods and kernel PCA, which has been empirically observed to perform clustering.
====References:====
 A.Y. Ng, M.I. Jordan, and Y. Weiss. On Spectral Clustering: Analysis and an algorithm. NIPS, 2001.
 Marina Maila and Jianbo Shi. Learning segmentation by random walks. NIPS, 2000.
 Deepak Verma and Marina Meila. A Comparison of Spectral Clustering Algorithms. 2003.
Value parameters
 W

the adjacency matrix of graph.
 k

the number of clusters.
Attributes
Spectral clustering.
Spectral clustering.
Value parameters
 data

the dataset for clustering.
 k

the number of clusters.
 sigma

the smooth/width parameter of Gaussian kernel, which is a somewhat sensitive parameter. To search for the best setting, one may pick the value that gives the tightest clusters (smallest distortion, see { @link #distortion()}) in feature space.
Attributes
Spectral clustering with Nystrom approximation.
Spectral clustering with Nystrom approximation.
Value parameters
 data

the dataset for clustering.
 k

the number of clusters.
 l

the number of random samples for Nystrom approximation.
 sigma

the smooth/width parameter of Gaussian kernel, which is a somewhat sensitive parameter. To search for the best setting, one may pick the value that gives the tightest clusters (smallest distortion, see { @link #distortion()}) in feature space.
Attributes
XMeans clustering algorithm, an extended KMeans which tries to automatically determine the number of clusters based on BIC scores. Starting with only one cluster, the XMeans algorithm goes into action after each run of KMeans, making local decisions about which subset of the current centroids should split themselves in order to better fit the data. The splitting decision is done by computing the Bayesian Information Criterion (BIC).
XMeans clustering algorithm, an extended KMeans which tries to automatically determine the number of clusters based on BIC scores. Starting with only one cluster, the XMeans algorithm goes into action after each run of KMeans, making local decisions about which subset of the current centroids should split themselves in order to better fit the data. The splitting decision is done by computing the Bayesian Information Criterion (BIC).
====References:====
 Dan Pelleg and Andrew Moore. Xmeans: Extending Kmeans with Efficient Estimation of the Number of Clusters. ICML, 2000.
Value parameters
 data

the data set.
 k

the maximum number of clusters.