I have a large sequence of vectors of length N. I need some unsupervised learning algorithm to divide these vectors into M segments. E.g.:k-means is not suitable, because it puts similar elements from different locations into a single cluster.UPD:real data looks like this:I see here 3 clusters: [0..50], [50..200], [200..250]UPD 2:I use modified k-means and get this acceptable result:borders of clusters: [0, 38, 195, 246]
Algorithm for segmentation of sequence data
machine learning;clustering;sequence
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-processingPlease 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:ConclusionMy 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!UPDATELuckily 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(!) SolutionAccording 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 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.