# 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.

FindClusters[data] | partition data into lists of similar elements |

FindClusters[data,n] | partition data into at most n lists of similar elements |

The data argument of FindClusters can be a list of data elements, associations, or rules indexing elements and labels.

{e_{1},e_{2},…} | data specified as a list of data elements e_{i} |

{e_{1}v_{1},e_{2}v_{2},…} | data specified as a list of rules between data elements e_{i} and labels v_{i} |

{e_{1},e_{2},…}{v_{1},v_{2},…} | data specified as a rule mapping data elements e_{i} to labels v_{i} |

key_{1}e_{1},key_{2}e_{2…} > | data specified as an association mapping elements e_{i} to labels key_{i} |

Ways of specifying data in FindClusters.

FindClusters works for a variety of data types, including numerical, textual, and image, as well as Boolean vectors dates and times. All data elements e_{i} must have the same dimensions.

In[1]:= |

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

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.

In[4]:= |

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.

In[6]:= |

In[7]:= |

With the default settings, FindClusters has found the four clusters of points.

You can also direct FindClusters to find a specific number of clusters.

option name | default value | |

CriterionFunction | Automatic | criterion for selecting a method |

DistanceFunction | Automatic | the distance function to use |

Method | Automatic | the clustering method to use |

PerformanceGoal | Automatic | aspect of performance to optimize |

Weights | Automatic | what weight to give to each example |

Options for 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.

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

If the e_{i} are vectors of numbers, FindClusters by default uses a squared Euclidean distance. If the e_{i} are lists of Boolean True and False (or 0 and 1) elements, FindClusters by default uses a dissimilarity based on the normalized fraction of elements that disagree. If the e_{i} are strings, FindClusters by default uses a distance function based on the number of point changes needed to get from one string to another.

EuclideanDistance[u,v] | the Euclidean norm |

SquaredEuclideanDistance[u,v] | squared Euclidean norm |

ManhattanDistance[u,v] | the Manhattan distance |

ChessboardDistance[u,v] | the chessboard or Chebyshev distance |

CanberraDistance[u,v] | the Canberra distance |

CosineDistance[u,v] | the cosine distance |

CorrelationDistance[u,v] | the correlation distance 1-(u-Mean[u]).(v-Mean[v])/(Abs[u-Mean[u]]Abs[v-Mean[v]]) |

BrayCurtisDistance[u,v] | the Bray–Curtis distance |

Distance functions for numerical data.

Dissimilarities for Boolean vectors are typically calculated by comparing the elements of two Boolean vectors and pairwise. It is convenient to summarize each dissimilarity function in terms of , where is the number of corresponding pairs of elements in and , respectively, equal to and . The number counts the pairs in , with and being either 0 or 1. If the Boolean values are True and False, True is equivalent to 1 and False is equivalent to 0.

MatchingDissimilarity[u,v] | simple matching (n_{10}+n_{01})/Length[u] |

JaccardDissimilarity[u,v] | the Jaccard dissimilarity |

RussellRaoDissimilarity[u,v] | the Russell–Rao dissimilarity (n_{10}+n_{01}+n_{00})/Length[u] |

SokalSneathDissimilarity[u,v] | the Sokal–Sneath dissimilarity |

RogersTanimotoDissimilarity[u,v] | the Rogers–Tanimoto dissimilarity |

DiceDissimilarity[u,v] | the Dice dissimilarity |

YuleDissimilarity[u,v] | the Yule dissimilarity |

Dissimilarity functions for Boolean data.

In[12]:= |

EditDistance[u,v] | the number of edits to transform u into string v |

DamerauLevenshteinDistance[u,v] | Damerau–Levenshtein distance between u and v |

HammingDistance[u,v] | the number of elements whose values disagree in u and v |

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.

In[14]:= |

The Method option can be used to specify different methods of clustering.

"Agglomerate" | find clustering hierarchically |

"Optimize" | find clustering by local optimization |

"DBSCAN" | density-based spatial clustering of applications with noise |

"GaussianMixture" | variational Gaussian mixture algorithm |

"JarvisPatrick" | Jarvis–Patrick clustering algorithm |

"KMeans" | k-means clustering algorithm |

"KMedoids" | partitioning around medoids |

"MeanShift" | mean-shift clustering algorithm |

"NeighborhoodContraction" | displace examples toward high-density region |

"SpanningTree" | minimum spanning tree-based clustering algorithm |

"Spectral" | spectral clustering algorithm |

Explicit settings for the Method option.

By default, 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.

Additional Method suboptions are available to allow for more control over the clustering. Available suboptions depend on the Method chosen.

"NeighborhoodRadius" | specifies the average radius of a neighborhood of a point |

"NeighborsNumber" | specifies the average number of points in a neighborhood |

"InitialCentroids" | specifies the initial centroids/medoids |

ClusterDissimilarityFunction | specifies the intercluster dissimilarity |

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 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.

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

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.

With Method->{"Agglomerate",ClusterDissimilarityFunction->f}, the specified linkage function f is used for agglomerative clustering.

"Single" | smallest intercluster dissimilarity |

"Average" | average intercluster dissimilarity |

"Complete" | largest intercluster dissimilarity |

"WeightedAverage" | weighted average intercluster dissimilarity |

"Centroid" | distance from cluster centroids |

"Median" | distance from cluster medians |

"Ward" | Ward's minimum variance dissimilarity |

f | a pure function |

Possible values for the ClusterDissimilarityFunction suboption.

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

With 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 d_{ik}, d_{jk}, d_{ij}, n_{i}, n_{j}, and n_{k}, where d is the distance between clusters and n is the number of elements in a cluster.

The CriterionFunction option can be used to select both the method to use and the best number of clusters.

"StandardDeviation" | root-mean-square standard deviation |

"RSquared" | R-squared |

"Dunn" | Dunn index |

"CalinskiHarabasz" | Calinski–Harabasz index |

"DaviesBouldin" | Davies–Bouldin index |

Automatic | internal index |