# Algorithm for segmentation of sequence data

I have a large sequence of vectors of length N. I need some unsupervised learning algorithm to divide these vectors into M segments.

For example:

K-means is not suitable, because it puts similar elements from different locations into a single cluster.

Update:

The real data looks like this:

Here, I see 3 clusters: [0..50], [50..200], [200..250]

Update 2:

I used modified k-means and got this acceptable result:

Borders of clusters: [0, 38, 195, 246]

• The quality of question should be improved to get a proper answer e.g. do all sequences always change at the same point (like how you illustrated in the example)? – Kasra Manshaei Jun 14 '15 at 17:42
• My real data is more complicated. It is list of 9-dimension vectors. I will add picture to the main section. – generall Jun 14 '15 at 21:30

Please see my comment above and this is my answer according to what I understood from your question:

As you correctly stated you do not need Clustering but Segmentation. Indeed you are looking for Change Points in your time series. The answer really depends on the complexity of your data. If the data is as simple as above example you can use the difference of vectors which overshoots at changing points and set a threshold detecting those points like bellow: As you see for instance a threshold of 20 (i.e. $$dx<-20$$ and $$dx>20$$) will detect the points. Of course for real data you need to investigate more to find the thresholds.

## Pre-processing

Please note that there is a trade-off between accurate location of the change point and the accurate number of segments i.e. if you use the original data you'll find the exact change points but the whole method is to sensitive to noise but if you smooth your signals first you may not find the exact changes but the noise effect will be much less as shown in figures bellow:

## Conclusion

My suggestion is to smooth your signals first and go for a simple clustering mthod (e.g. using GMMs) to find an accurate estimation of the number of segments in signals. Given this information you can start finding changing points constrained by the number of segments you found from previous part.

I hope it all helped :)

Good Luck!

## UPDATE

Luckily your data is pretty straightforward and clean. I strongly recommend dimensionality reduction algorithms (e.g. simple PCA). I guess it reveals the internal structure of your clusters. Once you apply PCA to the data you can use k-means much much easier and more accurate.

## A Serious(!) Solution

According to your data I see the generative distribution of different segments are different which is a great chance for you to segment your time series. See this (original, archive, other source) which is probably the best and most state-of-the-art solution to your problem. The main idea behind this paper is that if different segments of a time series are generated by different underlying distributions you can find those distributions, set tham as ground truth for your clustering approach and find clusters.

For example assume a long video in which the first 10 minutes somebody is biking, in the second 10 mins he is running and in the third he is sitting. you can cluster these three different segments (activities) using this approach.

• Thanks for detailed response. As you can see above, I can not use thresholds for my real data sequence, I think, it is too complicated for it. I am trying to modify k-means algorithm, it will consider the condition of sequence (element can only belong to one of two neighboring clusters). I hope, that I do not reinvent the wheel. :) – generall Jun 14 '15 at 21:42
• I think your data is not so noisy (i.e. complicated) and you can go for threshold stuff. the point is that you have an impression of the data so u can use kinda supervised algorithm i.e. trying to learn thresholds (and hope it generalizes well!) . I also update my answer for a nice solution :) – Kasra Manshaei Jun 14 '15 at 22:13
• Thank you for the interesting links, I think, it can be used for my purpose, but for now, I use k-means with my modifications, which gives me acceptable results (pic. in question). – generall Jun 15 '15 at 20:28
• very nice results! smart move. I'm proud of you :D Good Luck! – Kasra Manshaei Jun 15 '15 at 21:58

K-means clustering is known to give local minima, depending on your initial initialisation of the cluster centres.

However, k-means segmentation can, I think, be solved globally, since we do not permute anything in finding the solution.

I can see from your comments that you did manage eventually to reach a segmentation. Would you be able to give some feedback, please? Is your solution the best solution? Or did you settle for a good enough solution?

• K-means segmentation can also give local minima, because you still need to chose initial medoids\centroids. My current solution is good enough for me, but I can't claim it is the best one. I can share details of my solution if you interested in it. – generall Jan 16 '16 at 18:08
• It depends how you implement it. In the meantime, I have found out in some literature that for segmentation, it's feasible to find the global minimum, in polynomial time. – Nolatar Jan 17 '16 at 9:30

Just as a suggestion: you might try using the DBSCAN algorithm, as it often works much better than K-means for clustering

Otherwise, if you want to try something new for clustering and learn some interesting stuff, I suggest you try some Topological Data Analysis through persistent diagrams. I'mma leave you here a nice easy intro :)