Sequential clustering algorithm

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?

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

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.

• 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? – Max Feb 21 '11 at 21:37
• I ended up implementing a variation of this algorithm with a metric called Dunn’s clustering validity index – Max Feb 28 '11 at 16:26