1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ -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... $\endgroup$ – Avitus Aug 19 '13 at 21:02
  • $\begingroup$ I don't understand your last sentence. If dbscan is given a precomputed matrix, it will not need to re-compute any distance. $\endgroup$ – Anony-Mousse Aug 19 '13 at 23:11
  • $\begingroup$ 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 $\endgroup$ – Avitus Aug 20 '13 at 6:44
  • 1
    $\begingroup$ 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... $\endgroup$ – Anony-Mousse Aug 20 '13 at 7:00
  • $\begingroup$ 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! $\endgroup$ – Avitus Aug 20 '13 at 7:16

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.