Gap criterion clustering evaluation object
clustering.evaluation.GapEvaluation is an object consisting of sample data, clustering data, and gap criterion values used to evaluate the optimal number of clusters. Create a gap criterion clustering evaluation object using evalclusters.
Input data, specified as an N-by-P matrix. N is the number of observations, and P is the number of variables.
Data Types: single | double
Clustering algorithm, specified as one of the following.
|'kmeans'||Cluster the data in x using the kmeans clustering algorithm, with 'EmptyAction' set to 'singleton' and 'Replicates' set to 5.|
|'linkage'||Cluster the data in x using the clusterdata agglomerative clustering algorithm, with 'Linkage' set to 'ward'.|
|'gmdistribution'||Cluster the data in x using the gmdistribution Gaussian mixture distribution algorithm, with 'SharedCov' set to true and 'Replicates' set to 5.|
If Criterion is 'CalinskHarabasz', 'DaviesBouldin', or 'silhouette', you can specify a clustering algorithm using the function_handle (@) operator. The function must be of the form C = clustfun(DATA,K), where DATA is the data to be clustered, and K is the number of clusters. The output of clustfun must be one of the following:
A vector of integers representing the cluster index for each observation in DATA. There must be K unique values in this vector.
A numeric n-by-K matrix of score for n observations and K classes. In this case, the cluster index for each observation is determined by taking the largest score value in each row.
If Criterion is 'CalinskHarabasz', 'DaviesBouldin', or 'silhouette', you can also specify clust as a n-by-K matrix containing the proposed clustering solutions. n is the number of observations in the sample data, and K is the number of proposed clustering solutions. Column j contains the cluster indices for each of the N points in the jth clustering solution.
Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside single quotes (' '). You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.Example: 'KList',[1:5],'Distance','cityblock' specifies to test 1, 2, 3, 4, and 5 clusters using the sum of absolute differences distance measure.
Number of reference data sets generated from the reference distribution ReferenceDistribution, specified as the comma-separated pair consisting of 'B' and a positive integer value.
Distance metric used for computing the criterion values, specified as the comma-separated pair consisting of 'Distance' and one of the following.
|'sqEuclidean'||Squared Euclidean distance|
|'cityblock'||Sum of absolute differences|
|'cosine'||One minus the cosine of the included angle between points (treated as vectors)|
|'correlation'||One minus the sample correlation between points (treated as sequences of values)|
|'Hamming'||Percentage of coordinates that differ|
|'Jaccard'||Percentage of nonzero coordinates that differ|
For detailed information about each distance metric, see pdist.
You can also specify a function for the distance metric by using the function_handle (@) operator. The distance function must be of the form
d2 = distfun(XI,XJ),
where XI is a 1-by-n vector corresponding to a single row of the input matrix X, and XJ is an m2-by-n matrix corresponding to multiple rows of X. distfun must return an m2-by-1 vector of distances d2, whose kth element is the distance between XI and XJ(k,:).
If Criterion is 'silhouette', you can also specify Distance as the output vector output created by the function pdist.
When Clust a string representing a built-in clustering algorithm, evalclusters uses the distance metric specified for Distance to cluster the data, except for the following:
If Clust is 'linkage', and Distance is either 'sqEuclidean' or 'Euclidean', then the clustering algorithm uses Euclidean distance and Ward linkage.
If Clust is 'linkage' and Distance is any other metric, then the clustering algorithm uses the specified distance metric and average linkage.
In all other cases, the distance metric specified for Distance must match the distance metric used in the clustering algorithm to obtain meaningful results.
List of number of clusters to evaluate, specified as the comma-separated pair consisting of 'KList' and a vector of positive integer values. You must specify KList when clust is a clustering algorithm name string or a function handle. When criterion is 'gap', clust must be a string or a function handle, and you must specify KList.
Reference data generation method, specified as the comma-separated pair consisting of 'ReferenceDistributions' and one of the following.
|'PCA'||Generate reference data from a uniform distribution over a box aligned with the principal components of the data matrix x.|
|'uniform'||Generate reference data uniformly over the range of each feature in the data matrix x.|
Method for selecting the optimal number of clusters, specified as the comma-separated pair consisting of 'SearchMethod' and one of the following.
|'globalMaxSE'||Evaluate each proposed number of clusters in KList and
select the smallest number of clusters satisfying|
where K is the number of clusters, Gap(K) is the gap value for the clustering solution with K clusters, GAPMAX is the largest gap value, and SE(GAPMAX) is the standard error corresponding to the largest gap value.
|'firstMaxSE'||Evaluate each proposed number of clusters in KList and
select the smallest number of clusters satisfying|
where K is the number of clusters, Gap(K) is the gap value for the clustering solution with K clusters, and SE(K + 1) is the standard error of the clustering solution with K + 1 clusters.
Number of data sets generated from the reference distribution, stored as a positive integer value.
Clustering algorithm used to cluster the input data, stored as a valid clustering algorithm name string or function handle. If the clustering solutions are provided in the input, ClusteringFunction is empty.
Name of the criterion used for clustering evaluation, stored as a valid criterion name string.
Criterion values corresponding to each proposed number of clusters in InspectedK, stored as a vector of numerical values.
Distance measure used for clustering data, stored as a valid distance measure name string.
Expectation of the natural logarithm of W based on the generated reference data, stored as a vector of scalar values. W is the within-cluster dispersion computed using the distance measurement Distance.
List of the number of proposed clusters for which to compute criterion values, stored as a vector of positive integer values.
Natural logarithm of W based on the input data, stored as a vector of scalar values. W is the within-cluster dispersion computed using the distance measurement Distance.
Logical flag for excluded data, stored as a column vector of logical values. If Missing equals true, then the corresponding value in the data matrix x is not used in the clustering solution.
Number of observations in the data matrix X, minus the number of missing (NaN) values in X, stored as a positive integer value.
Optimal number of clusters, stored as a positive integer value.
Optimal clustering solution corresponding to OptimalK, stored as a column vector of positive integer values. If the clustering solutions are provided in the input, OptimalY is empty.
Reference data generation method, stored as a valid reference distribution name string.
Standard error of the natural logarithm of W with respect to the reference data for each number of clusters in InspectedK, stored as a vector of scalar values. W is the within-cluster dispersion computed using the distance measurement Distance.
Method for determining the optimal number of clusters, stored as a valid search method name string.
Standard deviation of the natural logarithm of W with respect to the reference data for each number of clusters in InspectedK. W is the within-cluster dispersion computed using the distance measurement Distance.
Data used for clustering, stored as a matrix of numerical values.
|increaseB||Increase reference data sets|
|addK||Evaluate additional numbers of clusters|
|compact||Compact clustering evaluation object|
|plot||Plot clustering evaluation object criterion values|
A common graphical approach to cluster evaluation involves plotting an error measurement versus several proposed numbers of clusters, and locating the "elbow" of this plot. The "elbow" occurs at the most dramatic decrease in error measurement. The gap criterion formalizes this approach by estimating the "elbow" location as the number of clusters with the largest gap value. Therefore, under the gap criterion, the optimal number of clusters occurs at the solution with the largest local or global gap value within a tolerance range.
The gap value is defined as
where n is the sample size, k is the number of clusters being evaluated, and Wk is the pooled within-cluster dispersion measurement
where nr is the number of data points in cluster r, and Dr is the sum of the pairwise distances for all points in cluster r.
The expected value is determined by Monte Carlo sampling from a reference distribution, and log(Wk) is computed from the sample data.
The gap value is defined even for clustering solutions that contain only one cluster, and can be used with any distance metric. However, the gap criterion is more computationally expensive than other cluster evaluation criteria, because the clustering algorithm must be applied to the reference data for each proposed clustering solution.
Evaluate the optimal number of clusters using the gap clustering evaluation criterion.
Load the sample data.
The data contains sepal and petal measurements from three species of iris flowers.
Evaluate the number of clusters based on the gap criterion values. Cluster the data using kmeans.
rng('default'); % For reproducibility eva = evalclusters(meas,'kmeans','gap','KList',[1:6])
eva = GapEvaluation with properties: NumObservations: 150 InspectecedK: [1 2 3 4 5 6] CriterionValues: [1x6 double] OptimalK: 4
The OptimalK value indicates that, based on the gap criterion, the optimal number of clusters is four.
Plot the gap criterion values for each number of clusters tested.
Based on the plot, the maximum value of the gap criterion occurs at five clusters. However, the value at four clusters is within one standard error of the maximum, so the suggested optimal number of clusters is four.
Create a grouped scatter plot to examine the relationship between petal length and width. Group the data by suggested clusters.
figure; PetalLength = meas(:,3); PetalWidth = meas(:,4); ClusterGroup = eva.OptimalY; figure; gscatter(PetalLength,PetalWidth,ClusterGroup,'rbgk','xod^');
The plot shows cluster 1 in the lower-left corner, completely separated from the other three clusters. Cluster 1 contains flowers with the smallest petal widths and lengths. Cluster 4 is in the upper-right corner, and contains flowers with the largest petal widths and lengths. Clusters 2 and 3 are near the center of the plot, and contain flowers with measurements between the two extremes.
 Tibshirani, R., G. Walther, and T. Hastie. "Estimating the number of clusters in a data set via the gap statistic." Journal of the Royal Statistical Society: Series B. Vol. 63, Part 2, 2001, pp. 411–423.