What algorithms are available to cluster sequences of data?

I have a data set containing points through time, generated by multiple Markov processes (each point in time contains N points). I know the statistical nature of the Markov processes (same for all), but my task is to determine which points go together (from the same process). Are there developed algorithms that address this type of problem? I should say my more general problem has missing data and an unknown number of processes, but I'd be interested in approaches to the "easy" version too, where there are no missing points and N is known.

• Do you have separate data streams, some of which are derived from identical Markov processes, so the goal is to identify which sequences come from the same process? OR do you have a set of points at each timepoint, where you lack knowledge not only of which sequence arises from which process, but you also don't know which point belongs to which sequence? Jul 24, 2017 at 20:09
• The latter. I have a bunch of points. Each point is derived from a process/sequence, but I don't know which one. Or put another way, I have N sequences of points, with all point thrown into a common bucket. My job is to group the points into the sequences they belong to. Let me know if that is still unclear. Jul 24, 2017 at 20:29
• Can you share the physical process that created this data? Jul 25, 2017 at 6:22
• I can't go into too much detail about my exact application, but imagine I had a video camera looking down at an ant hill and every second I grab a frame and use a neural net to identify the pixel locations of every ant. In the end I have a database full of ant locations at each time. I'd like to cluster the points (locations) into groups corresponding to each ant. When I'm done, I can connect the dots and show the path of each ant. Jul 25, 2017 at 15:21
• Your use case reminded me of the "mixture models". But seems to me that what you really want is some kind of tracking of objects on images. I would use the pixels of the objects to try to predict it's next move. On the next image you compare the prediction with all positions and the closest one form a connection that you want. If you have just x and y coordinates I would look for some method to uncover hidden processes over your set such as the mixture model. Jul 27, 2017 at 0:47

A few ideas...

K-means clustering

K-means clustering is a supervised learning technique in which you can

partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean.

However, this will require you to determine the number of clusters before hand. There are a few techniques that can assist you in this.

Model-based Clustering
Many coding environments have built in packages that algorithmically divide your data into the optimum size and number of clusters based on their common characteristics. For instance, this can be done in R using the mclust package.

This applies maximum likelihood estimators and Bayesian information criteria (BIC) to determine the size, shape, location, and number of clusters. This answer to this question has a worthwhile explanation of the mechanics. I have found using these techniques to be the most fruitful for large data projects.

Convex Hull (somewhat different than clustering, but could be useful to you) Similar to your ant hill example in the comment discussion, I have done some similar spatial work with player location in sports. For soccer players it is common to want to find the location in which a player is when a certain event takes place. One technique discussed by Applied Mathematics Professor David Sumpter in Sweden is taking the average of each player's locations (ant's location at a given time) and then building a convex hull around all the points that are within 1 standard deviation of the average location.