The question is in the title. I'm looking at clustering sequences and have created a short-list of approaches:
- Clustering on Edit Distance:
- Needleman-Wunsch: Similarity measure (used in ESAC)
- Levenshtein distance: Dissimilarity measure, equivalent to Nedleman-Wunsch.
- Both of above have updated adaptations which weight operations.
- LCS: Similar to the last two, but only allows for insertions and deletions.
- Hamming Distance: Like Needleman/Levenshtein but does not take alignment into account.
- Dynamic Time Warping: Similarity measure that is robust to differences in timing between the sequences being compared. Example scoring the similarity in the gaits of two different people walking at different speeds.
- Persistent Homology: Topological similarity clustering.
- Self Organizing Maps: Maps a (usually) 2D grid space of nodes that naturally cluster together. Can take temporal order into account, depending on implementation (TKM, SOFM-S, SARDNET)
We've started preliminary work on clustering based on edit distance, as it seems very straightforward to string it together with KMeans or KMedoids or even Spectral Clustering.
From a personal standpoint, I'm interested in SOMs and Persistent Homology, as they are incredibly interesting from an academic standpoint. However, we are currently not clear on how much data our customer is going to be able to provide. Since SOMs are classified as a neural network, I'm wondering if they come with the typical restriction of needing a ton of data.
I want to be able to take a deep dive into these interesting models, but I can't justify doing it on company time unless I can assure them that they will work reasonably well on small datasets.