1
$\begingroup$

My question: what is a "standard divisive hierarchical clustering algorithm".

I have a well-defined similarity matrix, and have already carried out a clustering (with spectral + genetic clustering algorithms), but it's quite complicated.

I would like to show that a run-of-the-mill divisive hierarchical clustering algorithm gives worse results (I have means of saying which results are better).

What's important: it MUST be (for reasons too political to explain) a divisive hierarchical algorithm, and it MUST use a similarity matrix (and not, for example, a distance matrix).

I would really appreciate any advice.

Improve this question
$\endgroup$
5
  • $\begingroup$ run-of-the-mill hierarchical clustering algorithm Which algorithm? $\endgroup$ – ttnphns May 14 '15 at 6:03
  • $\begingroup$ that's exactly my question - what is the most commonly (run-of-the-mill) used hierarchical clustering algorithm $\endgroup$ – ponadto May 14 '15 at 6:21
  • $\begingroup$ Agglomerative one, not divisive. $\endgroup$ – ttnphns May 14 '15 at 6:27
  • $\begingroup$ right, sorry, I should make that unambiguous. $\endgroup$ – ponadto May 14 '15 at 6:36
  • $\begingroup$ Unambiguous? The question still mentions divisive. Do you indeed mean agglomerative? As far as I know all those hierarchical agglomerative algorithms work on distances. Your question sounds like you know the answer already. "I would like to show that x gives worse results than y". You will first have to check whether that is the case, right? But if that is the answer you want there will always be ways to get it, especially if there are political reasons. I'm really not impressed with this question. Is there somewhere a respectable quest for objective validation in there? $\endgroup$ – micans May 15 '15 at 10:05
1
$\begingroup$

There are not many divisive hierarchical clusterings that I know of. In fact, I know exactly one such algorithm: DIANA (DIvisive ANAlysis or so) and I would not call it "popular", but exotic and only of historical interest. A divisive scheme needs to find the best of O(2^n) possible splits - this is very expensive, and even heuristics don't help that much to get a good result. Top-down isn't the method of choice.

Agglomerative methods are much more popular, but still scale badly, O(n^2) or worse (the standard HAC is O(n^3) runtime, O(n^2) memory). In many cases any O(n^2) method (in particular any that needs a full distance or similarity matrix) will be unacceptably expensive, which is why people keep on using k-means.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I've also heard of DIANA, and I agree - it's quite exotic (in the sense that few people use it). $\endgroup$ – ponadto May 14 '15 at 7:29
  • $\begingroup$ Nobody uses divisive much, because it's too expensive. There are O(2^n) possible splits if you work divisive, but only O(n^2) possible merges if you work agglomerative. Why do you insist on divisive schemes? $\endgroup$ – Has QUIT--Anony-Mousse May 14 '15 at 8:00
  • $\begingroup$ It seemed to me that the divisive scheme is more "natural" for my problem. I'm looking for clusters which correspond to "limbs" (like human-body limbs), i.e. semi-rigid regions, which are composed of many points which are mutually immobile within a given "limb". So, by analogy, I thought that it's more natural to notice human-body limbs going from "up to bottom", than starting from cells (or other microscopic objects) and merging them to build legs, hands, etc. $\endgroup$ – ponadto May 14 '15 at 8:35
  • $\begingroup$ That doesn't sound like its specific to divisive clustering. Could be agglomerative or density based as well. $\endgroup$ – Has QUIT--Anony-Mousse May 14 '15 at 8:37
  • $\begingroup$ @ponadto, You might perhaps want to consider decision tree (=classification tree, aspecially CHAID method) analysis. It is divisive, it is hierarchical, but it splits at any level (subgroup) by one of the variables only. And it needs dependent variable. So, it is not cluster analysis. $\endgroup$ – ttnphns May 14 '15 at 9:12

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.