5
$\begingroup$

I want to cluster elements in array. The crucial difference from a normal clustering algorithm is that the order of elements is significant. For instance if we look at a simple sequence of numbers like this:

1.1, 1.2, 1.0, 3.3, 3.3, 2.9, 1.0, 1.1, 3.0, 2.8, 3.2

It is obvious that there are two clusters in there (1.1, 1.2, 1.0, 1.0, 1.1) and (3.3, 3.3, 2.9, 3.0, 2.8, 3.2). What I want is to find sequential groups of similar elements

(1.1, 1.2, 1.0), (3.3, 3.3, 2.9), (1.0, 1.1), (3.0, 2.8, 3.2)

4 in this case. Of course I can run some variant of a normal clustering algorithm and then split clusters according elements' indices, but there's probably a simpler way to do this.

Is there any algorithm that I can use for this?

$\endgroup$
  • $\begingroup$ this looks like multiple change-point problem. I found this link which might be helpful. I hope someone will provide more details. $\endgroup$ – mpiktas Feb 21 '11 at 20:14
  • $\begingroup$ @mpiktas, thanks, it seems that "change-point" is the term that I was looking for. $\endgroup$ – Max Feb 21 '11 at 20:27
0
$\begingroup$

Constrained clustering maintains data order. There is a package in R called 'rioja' that implements this in the function 'chclust'.

The procedure isn't too complex though:

  1. Calculate inter-point distance
  2. Find the smallest distance between adjacent points
  3. Average the value of the two points to generate a single value
  4. Spit the list out again and start from one until you have a single point.

You need to maintain some sort of tree structure, but with some elementary programming experience you should be able to do it.

$\endgroup$
  • $\begingroup$ The change-point algorithms seem to be able to determine the optimal number of clusters. Is there any way to determine when to stop before single point is left? $\endgroup$ – Max Feb 21 '11 at 21:37
  • $\begingroup$ I ended up implementing a variation of this algorithm with a metric called Dunn’s clustering validity index $\endgroup$ – Max Feb 28 '11 at 16:26

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.