Evaluation measures of goodness or validity of clustering (without having truth labels) [duplicate]

Question

I'm clustering a set of data but I don't have truth document that allow me to evaluate the result of clustering (I have unlabelled data), so I can not use an external evaluation measure. In this case, is there any efficient evaluation measures - internal cluster validity measures, that will allow me to incrementally evaluate the clustering result each time I cluster some new data to the current clustering?

Answer 1

Wang, Kaijun, Baijie Wang, and Liuqing Peng. "CVAP: Validation for cluster analyses." Data Science Journal 0 (2009): 0904220071.:

To measure the quality of clustering results, there are two kinds of validity indices: external indices and internal indices.

An external index is a measure of agreement between two partitions where the first partition is the a priori known clustering structure, and the second results from the clustering procedure (Dudoit et al., 2002).

Internal indices are used to measure the goodness of a clustering structure without external information (Tseng et al., 2005).

For external indices, we evaluate the results of a clustering algorithm based on a known cluster structure of a data set (or cluster labels).

For internal indices, we evaluate the results using quantities and features inherent in the data set. The optimal number of clusters is usually determined based on an internal validity index.

(Dudoit et al., 2002): Dudoit, S. & Fridlyand, J. (2002) A prediction-based resampling method for estimating the number of clusters in a dataset. Genome Biology, 3(7): 0036.1-21.

(Tseng et al., 2005): Thalamuthu, A, Mukhopadhyay, I, Zheng, X, & Tseng, G. C. (2006) Evaluation and comparison of gene clustering methods in microarray analysis. Bioinformatics, 22(19):2405-12.

---

In your case, you need some internal indices since you don't have labelled data. There exist tens of internal indices, like:

• Silhouette index (implementation in MATLAB)
• Davies-Bouldin
• Calinski-Harabasz
• Dunn index (implementation in MATLAB)
• R-squared index
• Hubert-Levin (C-index)
• Krzanowski-Lai index
• Hartigan index
• Root-mean-square standard deviation (RMSSTD) index
• Semi-partial R-squared (SPR) index
• Distance between two clusters (CD) index
• weighted inter-intra index
• Homogeneity index
• Separation index

Each of them have pros and cons, but at least they'll give you a more formal basis for your comparison. The MATLAB toolbox CVAP might be handy as it contains many internal validity indices.

Answer 2

An outline of internal clustering criteria (internal cluster validation indices)

This is the excerpt from my documentation of a number of popular internal clustering criteria I've programmed, as a user, for SPSS Statistics (see my web page).

1. Reflections

Internal clustering criteria or indices exist to assess internal validity of a partition of objects into groups (clusters or other classes).

Internal validity: general idea. Internal validity of a partition of a set of objects is its justifiedness from the perspective of that information about the set of objects which was used by the procedure having done the partition. Consequently, internal validity answers the question, was that characteristic of the objects information accounted of “successfully” or “fully” in the act of partition. (And contrary, external validity of a partition is how well the partition corresponds to that information about the set of objects which was not used in the act of partition.)

Internal validity: operationally. Internal validity of a grouping is greater when there greater is the extent of similar objects falling in the same group while dissimilar – in different groups. In other words, same-group points must, in majority, be more similar to each other than different-group points are. Or, to formulate in terms of density: the more dense are groups inside and the less is density outside them (or the more distant groups draw apart) the higher is internal validity. Different clustering criteria, depending on their formula, differently realize and accentuate that intuitive principle when testing internal validity.

What input. Partition (grouping) of objects, and set – data (cases X variables) or matrix of proximities between objects. The set provides information about similarity between the objects.

Partition/grouping: what. Internal clustering criteria are applicable not only to results of clustering. Any partition in classes of any origin (cluster analysis, machine or manual classification), if these groups do not intersect by membership of elements (while spatially, the classes might intersect), can be checked for internal validity by those indices. Criteria presented in this document are meant for nonhierarchical classification, That is, groups don’t divide in subgroups in the being assessed partition.

Usage: comparing different k. Most often, internal clustering criteria are used for comparing cluster partitions with different number of clusters k obtained via the same method of clustering (or other method of grouping) basing on the same input set (same proximity matrix or same data). The purpose of such comparison is to choose the best k, i.e. the partition with the most valid number of clusters. In that context internal clustering criteria are also called sometimes stopping rules of clusterization. See details further.

Usage: comparing different methods. You may also compare partitions (with the same or different number k of clusters/classes) given by different procedures/modes (for example, different methods of cluster analysis) basing on the same input set. Generally, it’s all the same for a criterion, which way – same or not – the being compared groupings were obtained, you may even don’t know which way it were. If you are comparing different methods under the same value of k you then are selecting the “better” method (at that k).

Usage: comparing not identical sets of objects. This is possible. One should understand that for a clustering criterion objects “i” in the set – are just anonymous rows. Therefore it will be correct to compare, by the criterion value, partitions P1 and P2 which partly or completely are comprised of not the same objects. At so doing k may be one or different in the partitions. However, if P1 and P2 consist of different number of objects one may use criterion only if it is insensitive to the number of objects N.

Usage: with different variants of input (not identical features or not identical proximity matrices). This is possible, but it is a subtle and problematic point. Speaking now here of the direct comparison of a criterion’s values val1 and val2, where val1 was obtained from input dataset (variables or proximities) X1 and partition P1, but val2 was obtained from dataset X2 and partition P2. Specifically:

1. Might compare partitions with the same k and gotten from the same method but differing on the used proximity measure between the objects. For example, one partition could be the result of clustering of matrix of euclidean distances (L2 norm), another – of matrix of Manhattan distances (L1 norm), third – of matrix of Minkovski distances with L3 norm. There is nothing formally illegitimate in such comparison – if you are ready to assume that different types of distances computed on the same data are immediately comparable in your case. But if they, the measures, have systematic difference for you – the difference one wants to level out (for instance, different lifting or range among values) – then do the corresponding “standardization” of the matrices before computing the clustering criterion. Considering the question of distance matrix transform it is also useful to inquire about how this or that clustering criterion reacts to transforming of matrix elements. “Universal” criteria like point-biserial correlation or C-index don’t react to addition of a constant to proximities, so the overall level of distance magnitudes in matrix is not important to them.

2. Might also compare partitions with the same k and after the same method, but differing on the set of attributes, variables in data. Here one have to repeat all those same warnings about comparability for you values of those different sets of variables: if they are incomparable (e.g. by level or range) – take care to bring them to comparability. Also, as a rule, clustering criteria aren’t indifferent to the number of variables: it would be incorrect, in general case, to compare directly criterion value obtained on data with 2 variables with value obtained on data with 5 variables.

3. Let’s say it separately about linear transformation of variables such as z-standardization. May one compare with a clustering criterion partitions (of the same k) of which one was received from raw data and the other was received from these same variables, only standardized? The answer to this question depends on a concrete criterion. If the criterion is insensitive to different linear transform of the variables, then you may.

Comparing different k: two types of criteria. Most often internal clustering criteria are used to select the optimal number of clusters k. (All those cluster partitions with different k must be obtained by you and be present in the dataset as the cluster membership variables; that is, a criterion assesses already existing, done partitions.) One looks at a plot where by X axis there go solutions with different number of clusters in ascending or descending order, – for example, k from 2 to 20, and by Y axis there deposits the index magnitude.

There are extremum criteria and elbow criteria. With extremum criteria, the higher is value (or inversely, lower – depending on the concrete criterion), the better is partition; consequently, absolutely best k corresponds to the maximal (or the minimal) criterion value when k runs consecutive values. With elbow criteria, their value monotonically increases (or inversely, decreases – depending on the concrete criterion) as k grows, and absolutely best k corresponds to the locus of edge of this tendency where subsequent increase of k no longer is accompanied by steep growth (decline) of the criterion. The advantage of extremum criteria over elbow criteria is that for any two k one can judge which is better k; therefore extremum criteria are applicable for comparisons not only of a series of consecutive values of k. Elbow criteria do not allow comparing nonadjacent k and generally pairs of k, because it is unclear by which “side” of these two k or maybe between them the elbow is located. This is an essential drawback of elbow indices.

Comparing different k: priority of sharpness over extremum. Need to say that in practice the sharpness on the bend – of a peak or an elbow – has major importance for extremum-type criteria too. On a plot of value profile of such a criterion by different consecutive k one should pay attention not only to max (or min, depending on the specific criterion) value in the profile, but to sharp bends tendency, not necessarily coinciding with max. If a partition with the given k is much better than partitions with k-1 and with k+1, i.e. there is a peak, then it is a strong argument for that k, even if there on the plot exist regions of k where the criterion is generally “better”. Even a one sided bend (elbow) may occur preferable to absolute max for extremum criteria. The reason for these advices is as follows.

The point is that various clustering indices have their peculiar small and having background, inherent character biases in respect to the number of clusters: some “prefer” many clusters while other – few clusters. And manifestation of these tendencies depends on peculiarities of the data: there is almost impossible to invent datasets with different k that would be equi-valid to each other, simultaneously for all possible criteria$^1$. Simulation experiments generating specified k clusters show that all criteria “are wrong” from time to time when clusters are mutually enough tight: they err in the sense that the overall max value does not match with the man-claimed number of the generated clusters. If to pay attention to peaks and elbows, rather than to max, then criteria are “wrong” less frequent in such experiments. (One should, however, realize the limitation of such simulation experiments in appraisal of the bias of clustering criteria: because a clustering criterion is not on the mission to discover the intended, at the generating, cluster structure, it simply assesses the sharpness of the structure as it turned out, while it might have turned out not at all such as it had been conceived at random generating.) By the idea, clustering criteria assisting to select a better k should have zero level base favouritism to k. Unfortunalely, this ideal is hardly likely achievable.

[$^1$ For example: let there be 2 round clusters in a 2-variable space (distance between them is 1), or 3 such clusters (triangle of them, distance between them is 1), or 4 such clusters (square of them, distance between the neighbours is 1). Specifics in disposition of the clusters are not the same in these three configurations (in the 2-cluster the data cloud is oblong; in the 4-cluster there exist between-cluster distances greater than 1) which complicates it to regard the three configurations equally internally valid by some “universal” internal validity. The very universal internal validity is what doesn’t exist. Some clustering criteria will respond to the above not sameness in the configurations by giving preference to one or another of them (and this is what enters the concept of the bias of a criterion towards k), while others – will not.]

Some criteria (for example BIC or PBM) consciously prefer solutions with small number of clusters, then it is said they “penalize for the excess of clusters”. C-Index, contrary, openly tends to reward solutions with a greater number of clusters.

Criterion vs eye. If data are interval, clusters are not infrequently discernible visually on scatterplots in space of the variables or their principal components. But eye has its own prejudices (apophenia) and it is just one of, and is not the best, clustering criteria. Often this or that clustering criterion based on a statistical formula will “uncover” clusters not noticeable to eye, which interpretation afterwards will confirm their validity by content.

Choosing criterion: data nature. Some criteria (1) require as input a set of data (cases x variables), and it is cases that are objects partitioned in clusters/classes. Some such criteria demand scale, quantitative variables; while other – categorical variables or mix of scale and categorical. Some criteria may be optimal for binary variables. Criteria of other type (2) are based on analysis of proximity matrix between objects. Often such criteria don’t care what – cases/respondents or variables/attributes – constitute the items broken in clusters, because a proximity matrix might exist for items of any nature. Some of the criteria of type (2) demand specific proximity measures, for example, euclidean distances. While to other criteria the kind of proximities is indifferent; those latter are called universal criteria. (But the “universality” question is more delicate than it seems, since these criteria do, for example, summation of proximities, and there rises theoretical question whether any or not any kind of proximities may be summed.) Some criteria (3) can be calculated equivalently from variables (scale) as well as from matrix (of euclidean distances).

Number of objects, or hilliness. There are criteria reacting to (proportionally equal) increase or decrease of frequency in clusters. That seems natural because adding objects into clusters amplifies relief of the distributional shape in the data, when clusters don’t coincide any much, and so the criterion value will expectedly enhance. But there are criteria that don’t react to such alteration of N: albeit it is important to such criteria that the density inside clusters be higher than outside clusters they do not reward strengthening of density through the increase of the number of objects in clusters.

Spatial shape. If a criterion requires scale data or euclidean distances, clusters might be of this or that configuration in the space. Here different clustering criteria have own preferences, i.e. they may reward, moderately, clusters exhibiting a specific spatial shape or relative position in the cluster solution. This quite intricate question can be split in three sub-questions: is the criterion sensitive, and how, (1) to the shape of cluster contours (round or oblong or curved); (2) to the rotation of oblong clusters relative one another, i.e. about their centroids; (3) to the rotation of the whole data cloud about its general centre (in the space of scale variables).

Remark for (1): there happens impression of false preference of round clusters. Not an existing clustering criterion demands clusters to nonoverlap by their margins in space, but the majority of cluster analysis methods output clusters exactly not overlapping in space. In these conditions (clusters are not allowed to superimpose physically) round clusters could get reseating closer to one another in space than oblong clusters with uncontrolled rotatedness, due to which the latter just have fewer chances to be encountered or be formed by clusterization in real investigation data – where, as we know, clusters are usually next to one another. Due to that phenomenon clustering criteria which are insensitive to cluster’s outline, such as Calinski-Harabasz, more often run into “good” solutions with round, rather than elongated, clusters. This doesn’t mean that these criteria themselves prefer round clusters.

Distributional shape in clusters. There are criteria giving preference to clusters with uniform, flat distribution inside (for example, hyperball), and there are criteria giving preference to clusters with bell-shape distribution inside (like normal distribution); while other criteria don’t take the shape of density distribution in a cluster as important.

Space dimension. One more not easy question – reaction of different clustering criteria to the increase of dimensionality of the space, which is “spanned” by the data split into clusters. That question is connected, among other things, to curse of dimensionality that “hang over” euclidean distances on which many clustering criteria are based.

Statistical significance. Internal clustering criteria are not accompanied by probabilistic p-value, since they don’t infer about population and they are busy just with the dataset at hand. Of course, a good cluster solution in the form of high value of the criterion may be the consequence of contingent peculiarities of the concrete sample, overfitting. Cross-validation by equivalent dataset (in the form of stability check and generalizability check) will always be helpful.

2. Example

Application of two clustering criteria for decision about the number of clusters in cluster analysis. Here is five pretty contacting clusters; eye does not recognize them at once.

With this data cloud, hierarchical cluster by average linkage analysis was done based on euclidean distances, and all cluster partitions from 15-cluster to 2-cluster were saved. Then used were 2 clustering criteria, Calinski–Harabasz and C-Index, in attempt to choose which solution is the best.

As seen on the left plot, Calinski–Harabasz quite easily (in the given example) managed the task, indicating at 5-cluster solution as absolutely the best. C-Index, however, recommends 15- or 9-cluster solutions (C-Index is “better” when lower). Nevertheless this needs to be ignored and needs to pay attention to the bend which C-Index gives at 5 cluster: 5-cluster solution is still good but 4-cluster is much worse. Therefore, the best solution to select is 5-cluster one even on the right plot.

Of course, one should understand that if cluster structure in your data is almost entirely absent then neither of all criteria will help choose the “correct” cluster solution, for there is no one. In such instances there’ll be no peaks or bends, but will be relatively smooth line trends, ascending, descending or horizontal – depending on the data and the criterion.

3. Some internal clustering criteria

[I'm not giving the formulas: please meet them as well as comments on each criterion's idea in the full document on the web page, collection "Internal clustering criteria"]

A. Clustering criteria based on ideology of analysis-of-variance in euclidean space. Based on ratios of sums-of-squares of deviations within and between clusters: B/W, B/T or W/T.

• Calinski–Harabasz is a multivariate analogue of Fisher’s F statistic. It recognizes well any convex clusters.
• Davies–Bouldin is similar to the former but without its tendency towards approximately same-sized, by the number of objects inside, clusters; Davies–Bouldin rather prefers clusters equally-distanced from each other.
• Cubic clustering criterion is like Calinski–Harabasz. It was (questionably) standardized for comparing results obtained on different data. Prefers spherical clusters.
• Log SS Ratio is akin to Calinski–Harabasz, but instead of normalizing B/W it uses logarithm.
• Log Det Ratio – logarithm of the inverted Wilks’ lambda; it is a MANOVA criterion considering volumetric property of the data cloud.

B. Clustering criteria professing univariate approach: analysis goes by each variable. These are fixed attributes: the data are not considered as lying in space where they might be arbitrarily rotated.

• Ratkowsky–Lance is designed for scale features (where it is based on the analysis-of-variance idea) as well as for categorical features (based on the chi-square statistic idea). Ratkowsky-Lance can be used also to assess the contribution of individual features to the quality of a clustering partition.
• AIC and BIC clustering criteria also allow for both scale and categorical attributes. These indices are linked to the idea of variational entropy. They put penalty for excess of clusters and thus make it possible to prefer groundedly a parsimonious (few clusters) solution.

C. Clustering criteria based on ideology of “cophenetic” correlation (correlation between likeness of objects and their falling into same cluster).

• Point-biserial correlation is usual Pearson r.
• Goodman–Kruskal Gamma is nonparametric, monotonic correlation.
• C-Index assesses how much close the cluster partition is to (unreachable) ideal one in the current setting. This criterion is equivalent to the rescaled Pearson r.

D. Other criteria:

• Dunn seeks for cluster solution with maximally demarcated, separated clusters – if possible, of approximately same physical size (diameter). The macro computes different versions of the criterion.
• McClain–Rao is the ratio of the average same-cluster distance to the average between-cluster distance among objects.
• PBM is eclectic criterion taking into account sums of deviations (not their squares) from centroids and separation between centroids.
• Silhouette statistic (the macro computes several versions of) is able to assess quality of clusterization of each separate object, not just of the entire cluster solution. The criterion measures justifiedness of putting objects in their clusters.

Summary of some properties of the criteria:

Answer 3

There are some internal clustering methods. In particular with respect to the distances of objects in the data set. See for example Silhouette coefficient [on Wikipedia].

You must however be aware that there are algorithms such as k-means that try to optimize exactly these parameters, and as such you introduce a particular type of bias; essentially this is prone to overfitting.

So when using internal evaluation methods, you need to be well aware of the properties of your algorithm and the actual measures. I'd even try to do some kind of cross validation, using only part of the data for clustering, and another part of the data set to validation. For the silhouette coefficient this will probably not be enough to make anything except k-means look good, but at least it should help comparing different k-means results with each other. Which - for this reason - is actually the main use of such a coefficient: comparing different results of the same algorithm with each other.

Sorry for only half-answering your question. I do not know if there is an "online version" of any such method available.

Have a look at your objectives, and see if you can derive any quality measure from this. In general, there is no such thing as the best clustering result for real data. It will always be only relative to a certain objective; and as such it can also overfit. k-means optimizes distances from centers; and supervised learners optimize for labels and are thus prone to overfit in reproducing the labels.

Answer 4

If your problem is to evaluate the clustering result among a list of clustering algorithms (i.e choosing the best clustering algorithm for a certain input dataset) another idea is to use an evaluation metric that someone else used as evaluation function to maximize, in order to create his clustering algorithm.

A very good example is given by this paper: Rock: a robust clustering algorithm for categorical attributes. In the section 3.3 (page 5) the authors present a criterion function to maximize.

In this case, the function considers the numbers of the "neighbors" that a certain point have in common with another point. A neighbor for the point x is a point n very similar to x (i.e such that an user-defined similarity metric between x and n, returns a very high score). So the idea is: if two points have in common a lot of "neighbors" then is a right thing to consider them in the same cluster.

In this way, using that evaluation function for the clustering results of two different algorithms, you can choose the high scored one.