# Partitional vs. hierarchical clustering with distance matrix

I am exploring the flexibility of partitional clustering algorithms. In particular, I would like to introduce more general distances than the ones which are used by default.

Let us consider, for simplicity, dbscan contained in the R-package fpc. It allows the user to specify a "data matrix, data.frame, dissimilarity matrix or dist-object".

My idea would be to compute the distance matrix of the given data w.r.t. my chosen distance, and run dbscan.

Here comes the point where I am stuck. Is it true that specifying a distance matrix should lead inevitably to a hierarchical clustering? My intuition says that a hierarchical clustering in presence of a distance matrix makes more sense that a partitional one on the elements of the matrix itself. As I am no expert in clustering, I cannot judge the above statement properly.

Would you use a partitional algorithm on the distance matrix of a given dataset? Is this correct?

Thank you all!

You may want to read up on Generalized DBSCAN. DBSCAN itself only needs a binary decision.

So in fact, you can map the matrix to a binary matrix $x\ge\varepsilon$ and then set $\varepsilon=.5$ and you will get the exact same result with DBSCAN. It only needs a predicate of "is a neighbor", not an actual measure of neighborness.

There exist improved versions of DBSCAN for a long time, namely OPTICS, and just this year DBSCAN was revisited, incorporating ideas from OPTICS, as HDBSCAN*. Both of these actually produce a hierarchy.

Putting restrictions on the distance functions is mostly of interest for performance. Some distances can be accelerated with index structures, at which point these algorithm can run in less than $\mathcal O(n^2)$. Anything that is based on a distance matrix will obviously need at least $\mathcal O(n^2)$ memory and runtime.

The R options for clustering are in my opinion not very good. fpc is really slow. For clustering, I perfer ELKI. It is very flexible; if you are interested in evaluating the flexibility of clustering algorithms you should probably have a good look at it. It also has support for index structures.

• -thanks for your answer (as usual!). I do appreciate A LOT the time you spend to help me :-) . I have seen ELKI few days ago...it looks cool. OPTICS seems quite good as well! Unfortunately there are still some missing pieces in my mind. For example: if I produce a (symmetric) distance matrix from my data, let us say with entries $(0,1,2,\sqrt{5}):=x$, then what does dbscan do? Does it begin to cluster the vector $x$ using the eps threshold? If yes...then I am confused: I used an ad hoc distance to get $x$ and dbscan uses its default one on it... – Avitus Aug 19 '13 at 21:02
• I don't understand your last sentence. If dbscan is given a precomputed matrix, it will not need to re-compute any distance. – Anony-Mousse Aug 19 '13 at 23:11
• If dbscan is given the precomputed distance matrix, then it will begin to cluster the components of $x$ (as above), am I right? If yes, it will begin to check if there exist components of $x$ whose distance is <= eps from an initially selected component. To do so, dbscan must know what does it mean "distance <=eps". This is my issue: I used an ad hoc distance to produce the distance matrix, but after its computation dbscan checks the "eps" condition using a default one. I am sorry if this makes no sense! It would be great you I could find the flaw(s) in what is above – Avitus Aug 20 '13 at 6:44
• It will not cluster the distance matrix. It will cluster the column indexes. Objects $i$ and $j$ are connected iff $x_{ij}\leq\varepsilon$. That's how distance matrixes work... – Anony-Mousse Aug 20 '13 at 7:00
• I see: so in presence of a distance matrix, no "<=eps" condition is checked AT ALL by dbscan. Unfortunately, one has to compute the entries of it :) Now it is clear, thanks @Anony-Mousse! – Avitus Aug 20 '13 at 7:16