6
$\begingroup$

Classic agglomerative hierarchical clustering methods are based on a greedy algorithm. This means that they (many of them) are prone to give sub-optimal solutions instead of the global optimum result, especially on later steps of agglomeration. To clarify: each of the agglomerative methods makes the best choice of which two clusters to merge on a given step $q$, the choice that minimizes (to value $\delta_q$) the coefficient of colligation $\delta$ on the step; however, it is not impossible that if the algo had chosen not the best but a bit worse choice on some previous step(s) it then would have been able to minimize the coefficient on step $q$ to value less than that $\delta_q$ while preserving monotonical growth of $\delta$. Globally optimal solution on step $q$ corresponds to the absolutely minimal such way achievable value $\delta_q$ with the restriction remaining that $\delta_q \ge \delta_{q-1} \ge \delta_{q-2} \cdots$.

Risk of sub-optimality is the main reason why hierarchical clustering is commonly not recommended with large amount of objects (say, more than several hundreds): the researcher typically wants few clusters and therefore looks at later steps, but if a later step is, say, a 1000th one, it is more suspicious for having gone astray from globally optimal partition possible on the 1000th step than, say, a 100th step gone from globally optimal partition possible on the 100th step. This looks a matter of dictum.

My question is what do you think about which among well-known agglomerative methods - single linkage, complete linkage, average linkage (within groups), average linkage (between groups), centroid, median, Ward's sum-of-squares - I'm mentioning those in SPSS, but there are other similar variants as well - are more and which are less prone to the sub-optimality flaw as the step number grows. Intuition suggests to me that single or complete linkage aren't prone at all and always give their globally best solutions, because these methods don't engage in computation of any statistics derivative from raw distances (e.g. centroids). I may be right as well as not. What are about the rest methods? Can someone here attempt to analyze the (relative) degree of local-optimum risk of the above concrete greedy algorithms?

Illustration. Fortunately, for Ward method we have clues to observe how sub-optimality accumulates as $q$ grows. Because there is a well-known iterative method that attempts to optimize the same function $\delta$ as Ward does; this is K-means clustering: both try to minimize pooled within-cluster sum-of-squares $^1$. We can do Ward clustering and on each step save cluster centres, and use those as initial centres in K-means procedure. Will K-means improve the Ward's solutions in terms of sum-of-squares?

[$^1$ Footnote: Ward minimizes the increase in sum-of-squares on its steps. Another hierarchical method, variance method MNVAR (see Podany, J., 1989, for various hierarchical methods), which is less well-known, minimizes mean-of-squares within clusters. Both these methods can be considered as a kin to K-Means, with Ward's being somewhat better minimizer of final SSwithin than MNVAR (my own simulation studies).]

Note. This illustration tests Ward's observed $\delta_q$ values not against its own global optimum values which we can't know because we are unable to try, for each step, all innumerable alternative reconstructions of earlier steps in order to find out the minimal possible $\delta_q$; it tests against K-means optimality (which is almost its global here because initial centres provided by Ward can be regarded reasonably good start for iterations).

Here is some data (5 not well separated clusters, 183 points). The data underwent both Ward clustering session and K-means clustering sessions, as described.

enter image description here

Results (value of $\delta$) for clusters 50 through 2 are shown below. Although the 2 curves are close to each other, K-means' values are somewhat better. That is, K-means is more optimal than Ward.

enter image description here

The last picture plots $\delta^{Ward}/\delta^{Kmeans}$. The trend is clearly seen: as the number of clusters diminishes (that is, step $q$ for Ward grows), Ward tends to become less optimal relative to K-means.

enter image description here

One tempting question would be whether the relative sub-optimality of Ward (the value of $\delta^{Ward}/\delta^{Kmeans}$) on these latest 49 steps of agglomeration would be higher if I analyzed in the same fashion 1830 data points instead of just 183.

$\endgroup$
  • $\begingroup$ Try non-spherical clusters, too. Or you might "overfit" your analysis to gaussian clusters. $\endgroup$ – Anony-Mousse Oct 23 '12 at 13:44
3
$\begingroup$

Sub-optimality with respect to what?

I have the impression that you are mixing up things a bit here.

Single linkage, average linkage, etc. are measure definitions, not algorithms

When it comes to actual algorithms, different choices exist. For single linkage for example there is the naive matrix-based algorithm in $O(n^3)$ which will always merge the minimum found in the current matrix, then eliminate rows. (As the matrix is $O(n^2)$ in size and it takes $O(n)$ iterations, this yields to the $O(n^3)$ runtime). But there is also a more efficient algorithm for single-linkage clustering called SLINK, which is in $O(n^2)$. I believe there is also CLINK for complete linkage, and some of the others may also have efficient algorithms for this problem. I figure that the complexity of $O(n^3)$ and the memory requirement of $O(n^2)$ are also the main motivation to not use it for larger data sets, along with the difficulties at choosing the appropriate cut through the dendrogram and the relative inability of the algorithm to cope with outliers.

SLINK and the naive algorithm should produce the same result though.

So how exactly do you expect a local optimum to happen, and with respect to what measure is it sub-optimal?

Update: for your extended question. Consider that there were some better merge possible at step q that the naive algorithm misses, there must have been a decision at step q-x where the algorithm should have made a different choice. So there must be a first level, where the two solutions diverge. At this single point, it must thus be required to make a suboptimal choice. Now to play really unfair, assume I modify the algorithm to save the very best split to this particular level (because I know where you are evaluating). I do singe link, but I always merge the second best solution, until I'm at level q. With your evaluation, this would be the best solution, as I have the minimum $\delta_q$ at this very level! But is it really the best solution if I postpone a good merge?!?

Technically, the solution of linkage clustering is not a single partitioning into q parts, but the whole dendrogram. So the other solution cannot be optimal either, because it is suboptimal much earlier.

Okay, so say you still want to restrict the algorithm also giving you k clusters, and only evaluate at this depth, not the whole dendrogram. Then indeed I believe you can get suboptimal solutions with some of the linkages. Most likely because outliers close to a cluster can bias the means to separate. But I'm not sure if there is an objective measure for this.

$\endgroup$
  • $\begingroup$ Thank you for the answer and for mentioning things like SLINK which I'm not familiar yet. But I'm talking of one-path agglomerative algorithm only (the one you called "naive matrix-based") and I don't treat single, average, etc. methods as different algorithms. I expanded my question a bit to make it clearer what I refer to as local and global optimum. Both are about the same measure (the same agglomeration method); I do not consider third-party density criteria. $\endgroup$ – ttnphns Oct 23 '12 at 0:37
  • $\begingroup$ See my updated answer. I belive there are much more important issues with hierarchical clustering (runtime, memory, and result complexity), and a hint of why you need to look at the previous levels, too, not just the one cut. $\endgroup$ – Anony-Mousse Oct 23 '12 at 6:30
  • $\begingroup$ Honestly, I failed to follow your logic starting from Now to play, just didn't understand; perhaps you would feel like unpacking your reasoning a bit for me to be able to get it. As for taking dendrogram as a whole, so the other solution cannot be optimal either, because it is suboptimal much earlier, I won't agree in my case. In my case I'm interested only in whether the currently latest coefficient $\delta_q$ could have been forced to be smaller (at cost of any detriment for prior steps), and how much smaller. And how this potential gap depends on $q$. $\endgroup$ – ttnphns Oct 23 '12 at 8:49
  • $\begingroup$ Try a single-link, which always merges the second best cluster. Until step q, where it performs the best merge it has been delaying until now. It will have a much better $\delta_q$ value! Yet the result is clearly not better. Thus, you cannot take $\delta_q$ as quality indicator. $\endgroup$ – Anony-Mousse Oct 23 '12 at 10:53
  • $\begingroup$ Ah, you say of a situation when a later link on a dendrogram lies lower than some earlier links. This "inversion" naturally occurs not very rarely with regular centroid/median methods, you probably know. It's no wonder. In such a case they recommend to reset the peculiar $\delta_q$ to the highest link among local subclusters, see example. So, this can be overcome. $\endgroup$ – ttnphns Oct 23 '12 at 12:07
2
$\begingroup$

A partial answer to your question follows. Single linkage clustering is equivalent to the computation of a minimal spanning tree (references are easy to find). If we disregard ties the result is garantueed to be an optimal solution, or one among a set of optimal solutions, in that the total branch length will be minimal. I think the naive construction process also garantuees the property that you ask for (when cutting a dendrogram). As for complete link clustering, I do not know, and I think it is a good question. A famous reference in this field is the book by Jardine and Simpson, mathematical taxonomy. They conclude that single linkage clustering, for all its shortcomings, is mathematically and conceptually the stand-out method and consider it the most appealing. I don't agree with that, but the book is a very good read. Perhaps their results might imply that the property you seek does not hold for complete link clustering, but this is speculation.

$\endgroup$
  • $\begingroup$ Thank you, I liked your response although it adds little to what I'm aware myself, in particularly regarding single linkage method; I've thought, it must be always fully optimal. Other methods intrigue me more. Thank you for regarding my question as good one. I've added something to it recently. $\endgroup$ – ttnphns Oct 23 '12 at 12:20
  • $\begingroup$ I think it is possible to construct an example with 6 points, where complete link clustering will give two clusters, with the largest pairwise distance among those two clusters a certain value delta. In that example, another partition into two clusters yields a smaller largest pairwise distance. It seems to me this will answer your question - is that correct? I don't have the book anymore, but this is exactly the kind of phenomenon that Jardine and Simpson study. $\endgroup$ – micans Oct 23 '12 at 15:21
2
$\begingroup$

Only single-linkage is optimal. Complete-linkage fails, so your intuition was wrong there. ;-)

As a simple example, consider the one-dimensional data set 1,2,3,4,5,6.

The (unique) optimum solution for complete linkage with two clusters is (1,2,3) and (4,5,6) (complete linkage height 2). The (unique) optimum solution with three clusters is (1,2), (3,4), (5,6), at linkage height 1. There exists no agglomerative hierarchy that contains both, obviously, because these partitions do not nest. Hence, no hierarchical clustering contains all optimal solutions for complete linkage. I would even expect complete linkage to exhibit among the worst gap between the optimum solution and the agglomerative solution at high levels, based on that example... An this example likely is a counter example for most other schemes (except single linkage, where this data set degenerates).

You may be interested in studying this article:

Gunnar E. Carlsson, Facundo Mémoli: Characterization, Stability and Convergence of Hierarchical Clustering Methods. Journal of Machine Learning Research 11: 1425-1470 (2010)

and the references contained therein, in particular also:

Kleinberg, Jon M. "An impossibility theorem for clustering." Advances in neural information processing systems. 2003.

These seem to indicate that given some mild stability requirements (which can be interpreted as uncertainty of our distance measurements), only single-linkage clustering remains. Which, unfortunately, is all but usable in most cases... so IMHO for practical purposes the authors overshoot a bit, neglecting usefulness of the result over pretty theory.

$\endgroup$
  • $\begingroup$ Ah, yes. That's quite clear. Thank you, Erich, for answering this old question. I upvoted all the answers to it. $\endgroup$ – ttnphns Mar 12 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.