Partitioning Data into Clusters

Cluster analysis is an unsupervised learning technique used for classification of data. Data elements are partitioned into groups called clusters that represent proximate collections of data elements based on a distance or dissimilarity function. Identical element pairs have zero distance or dissimilarity, and all others have positive distance or dissimilarity.

General clustering function.

The data argument of (RefLink[FindClusters, paclet:ref/FindClusters]) can be a list of data elements, associations, or rules indexing elements and labels.

Ways of specifying data in (RefLink[FindClusters, paclet:ref/FindClusters]).

(RefLink[FindClusters, paclet:ref/FindClusters]) works for a variety of data types, including numerical, textual, and image, as well as Boolean vectors, dates and times. All data elements (Subscript[e, i]) must have the same dimensions.

Here is a list of numbers:

data = {1.2, 9.1, 2.3, 35.4,35.7,  71.8};

(RefLink[FindClusters, paclet:ref/FindClusters]) clusters the numbers based on their proximity:

FindClusters[data]

The rule-based data syntax allows for clustering data elements and returning labels for those elements.

Here two-dimensional points are clustered and labeled with their positions in the data list:

data1={{1, 2}, {5, 7}, {0, 2}, {4, 7}} ;
FindClusters[data1-> Range[Length[data1]]]

The rule-based data syntax can also be used to cluster data based on parts of each data entry. For instance, you might want to cluster data in a data table while ignoring particular columns in the table.

Here is a list of data entries:

datarecords={{"Joe", "Smith",158,64.4},{"Mary", "Davis",137,64.4},{"Bob", "Lewis",141,62.8},{"John", "Thompson",235,71.1},{"Lewis", "Black",225,71.4},{"Sally", "Jones",168,62.},{"Tom", "Smith",243,70.9},{"Jane", "Doe",225,71.4}};

This clusters the data while ignoring the first two elements in each data entry:

FindClusters[Drop[datarecords,None,{1,2}]->datarecords]

In principle, it is possible to cluster points given in an arbitrary number of dimensions. However, it is difficult at best to visualize the clusters above two or three dimensions. To compare optional methods in this documentation, an easily visualizable set of two-dimensional data will be used.

The following commands define a set of 300 two-dimensional data points chosen to group into four somewhat nebulous clusters:

GaussianRandomData[n_Integer,p_,sigma_]:=Table[p+{Re[#],Im[#]}&[RandomReal[NormalDistribution[0,sigma]](E^(I RandomReal[{0,2π}]))],{n}];
datapairs=BlockRandom[
SeedRandom[1234];
Join[GaussianRandomData[100,{2,1},.3],GaussianRandomData[100,{1,1.8},.2],
GaussianRandomData[100,{1,1.1},.4],GaussianRandomData[100,{1.75,1.75},0.1]]];

This clusters the data based on the proximity of points:

cl=FindClusters[datapairs];

Here is a plot of the clusters:

ListPlot[cl]

With the default settings, (RefLink[FindClusters, paclet:ref/FindClusters]) has found the four clusters of points.

You can also direct (RefLink[FindClusters, paclet:ref/FindClusters]) to find a specific number of clusters.

This shows the effect of choosing 3 clusters:

ListPlot[FindClusters[datapairs,3]]

This shows the effect of choosing 5 clusters:

ListPlot[FindClusters[datapairs,5]]

Options for (RefLink[FindClusters, paclet:ref/FindClusters]).

In principle, clustering techniques can be applied to any set of data. All that is needed is a measure of how far apart each element in the set is from other elements, that is, a function giving the distance between elements.

(RefLink[FindClusters, paclet:ref/FindClusters])[{(Subscript[e, 1]),(Subscript[e, 2]),…},(RefLink[DistanceFunction, paclet:ref/DistanceFunction])->f] treats pairs of elements as being less similar when their distances f[(Subscript[e, i]),(Subscript[e, j])] are larger. The function f can be any appropriate distance or dissimilarity function. A dissimilarity function f satisfies the following:

If the (Subscript[e, i]) are vectors of numbers, (RefLink[FindClusters, paclet:ref/FindClusters]) by default uses a squared Euclidean distance. If the (Subscript[e, i]) are lists of Boolean (RefLink[True, paclet:ref/True]) and (RefLink[False, paclet:ref/False]) (or 0 and 1) elements, (RefLink[FindClusters, paclet:ref/FindClusters]) by default uses a dissimilarity based on the normalized fraction of elements that disagree. If the (Subscript[e, i]) are strings, (RefLink[FindClusters, paclet:ref/FindClusters]) by default uses a distance function based on the number of point changes needed to get from one string to another.

Distance functions for numerical data.

This shows the clusters in datapairs found using a Manhattan distance:

ListPlot[FindClusters[datapairs,DistanceFunction->ManhattanDistance]]

Dissimilarities for Boolean vectors are typically calculated by comparing the elements of two Boolean vectors u and v pairwise. It is convenient to summarize each dissimilarity function in terms of (Subscript[n, i,j]), where (Subscript[n, i,j]) is the number of corresponding pairs of elements in u and v, respectively, equal to i and j. The number (Subscript[n, i,j]) counts the pairs {i,j} in {(Subscript[u, 1]),(Subscript[v, 1])},{(Subscript[u, 2]),(Subscript[v, 2])}…, with i and j being either 0 or 1. If the Boolean values are (RefLink[True, paclet:ref/True]) and (RefLink[False, paclet:ref/False]), (RefLink[True, paclet:ref/True]) is equivalent to 1 and (RefLink[False, paclet:ref/False]) is equivalent to 0.

Dissimilarity functions for Boolean data.

Here is some Boolean data:

bdata={{False,False,False,False,False,True,False,False,True,False},{False,False,False,False,False,False,False,False,False,True},{False,False,False,True,False,False,True,False,False,True},{True,True,False,False,True,False,False,False,True,True},{True,True,False,False,True,True,True,True,True,True}};

These are the clusters found using the default dissimilarity for Boolean data:

FindClusters[bdata]

Dissimilarity functions for string data.

The edit distance is determined by counting the number of deletions, insertions, and substitutions required to transform one string into another while preserving the ordering of characters. In contrast, the Damerau–Levenshtein distance counts the number of deletions, insertions, substitutions, and transpositions, while the Hamming distance counts only the number of substitutions.

Here is some string data:

sdata={"The","quick","brown","fox","jumps","over","the","lazy","dog"};

This clusters the string data using the edit distance:

FindClusters[sdata]

The (RefLink[Method, paclet:ref/Method]) option can be used to specify different methods of clustering.

Explicit settings for the (RefLink[Method, paclet:ref/Method]) option.

By default, (RefLink[FindClusters, paclet:ref/FindClusters]) tries different methods and selects the best clustering.

The methods "KMeans" and "KMedoids" determine how to cluster the data for a particular number of clusters k.

The methods "DBSCAN", "JarvisPatrick", "MeanShift", "SpanningTree", "NeighborhoodContraction", and "GaussianMixture" determine how to cluster the data without assuming any particular number of clusters.

The methods "Agglomerate" and "Spectral" can be used in both cases.

This shows the clusters in datapairs found using the "KMeans" method:

ListPlot[FindClusters[datapairs,4,Method->"KMeans"]]

This shows the clusters in datapairs found using the "GaussianMixture" method:

ListPlot[FindClusters[datapairs,Method->"GaussianMixture"]]

Additional (RefLink[Method, paclet:ref/Method]) suboptions are available to allow for more control over the clustering. Available suboptions depend on the (RefLink[Method, paclet:ref/Method]) chosen.

Suboption for all methods.

The suboption "NeighborhoodRadius" can be used in methods "DBSCAN", "MeanShift", "JarvisPatrick", "NeighborhoodContraction", and "Spectral".

The suboption "NeighborsNumber" can be used in methods "DBSCAN" and "JarvisPatrick".

The suboption "InitialCentroids" can be used in methods "KMeans" and "KMedoids".

The suboption (RefLink[ClusterDissimilarityFunction, paclet:ref/ClusterDissimilarityFunction]) can be used in the method "Agglomerate".

The "NeighborhoodRadius" suboption can be used to control the average radius of the neighborhood of a generic point.

This shows different clusterings of datapairs found using the "NeighborhoodContraction" method by varying the "NeighborhoodRadius":

Grid[{Table[ListPlot[FindClusters[datapairs,Method->{"NeighborhoodContraction", "NeighborhoodRadius"->s}]], {s, {0.06, 0.08, 0.1}}]}, Frame->All]

The "NeighborsNumber" suboption can be used to control the number of neighbors in the neighborhood of a generic point.

This shows different clusterings of datapairs found using the "DBSCAN" method by varying the "NeighborsNumber":

table = Table[ListPlot[FindClusters[datapairs,Method->{"DBSCAN", "NeighborsNumber"->p}]], {p, {10, 20, 30, 50}}];
Grid[{table}, Frame->All]

The "InitialCentroids" suboption can be used to change the initial configuration in the "KMeans" and "KMedoids" methods. Bad initial configurations may result in bad clusterings.

This shows different clusterings of datapairs found using the "KMeans" method by varying the "InitialCentroids":

{p1, p2, p3, p4} = {{1,1}, {1,1.8}, {2,1}, {2,2}};
{q1, q2, q3, q4} = RandomReal[1, {4, 2}];
Grid[{Table[ListPlot[FindClusters[datapairs,4,Method->{"KMeans", "InitialCentroids"->s}]], {s, {{p1, p2, p3, p4}, {q1, q2, q3, q4}}}]}, Frame->All]

With (RefLink[Method, paclet:ref/Method])->{"Agglomerate",(RefLink[ClusterDissimilarityFunction, paclet:ref/ClusterDissimilarityFunction])->f}, the specified linkage function f is used for agglomerative clustering.

Possible values for the (RefLink[ClusterDissimilarityFunction, paclet:ref/ClusterDissimilarityFunction]) suboption.

Linkage methods determine this intercluster dissimilarity, or fusion level, given the dissimilarities between member elements.

With (RefLink[ClusterDissimilarityFunction, paclet:ref/ClusterDissimilarityFunction])->f, f is a pure function that defines the linkage algorithm. Distances or dissimilarities between clusters are determined recursively using information about the distances or dissimilarities between unmerged clusters to determine the distances or dissimilarities for the newly merged cluster. The function f defines a distance from a cluster k to the new cluster formed by fusing clusters i and j. The arguments supplied to f are (Subscript[d, ik]), (Subscript[d, jk]), (Subscript[d, ij]), (Subscript[n, i]), (Subscript[n, j]), and (Subscript[n, k]), where d is the distance between clusters and n is the number of elements in a cluster.

This shows different clusterings of datapairs found using the "Agglomerate" method by varying the (RefLink[ClusterDissimilarityFunction, paclet:ref/ClusterDissimilarityFunction]):

Grid[{Table[ListPlot[FindClusters[datapairs,4,Method->{"Agglomerate", ClusterDissimilarityFunction->s}]], {s, {"Single", "Average", "Complete"}}]}, Frame->All]

The (RefLink[CriterionFunction, paclet:ref/CriterionFunction]) option can be used to select both the method to use and the best number of clusters.

This shows the result of clustering using different settings for (RefLink[CriterionFunction, paclet:ref/CriterionFunction]):

Dis=MixtureDistribution[{2,2},{UniformDistribution[{{-3,3}, {-1,0}}],
UniformDistribution[{{-3,3},{ 2,3}}]}];
stripes=RandomVariate[Dis,3000];
ListPlot[stripes, PlotRange->All]

These are the clusters found using the default (RefLink[CriterionFunction, paclet:ref/CriterionFunction]) with automatically selected number of clusters:

ListPlot[FindClusters[stripes]]

These are the clusters found using the "CalinskiHarabasz" index:

ListPlot[FindClusters[stripes, CriterionFunction->"CalinskiHarabasz"]]