substring clustering with noise

Question

I have sequence which is a repetition of a few strings. I have identified the start and end markers of these strings in the sequence and now, I want to cluster similar strings together. The problem is there is a lot of noise. E.g say the strings in the sequence are ABC, BD, EF. and we have a sequence ABGC'BTD'BD'EF'EOF'ABQC'. Here I want to cluster ABGC and ABQC together. How can I do this when there is almost 30-50% noise. If there is some way to remove the noise first and then cluster them, that would work too. Also, the markers are being learnt in an unsupervised manner so you don't know the processes in it beforehand. You can assume the noise to be random.

Answer 1

First, you must define a distance that is good for your purpose : how close two substrings are :

• How close "ABC" is to "ABGC" ?
• How close "ABC" is to "BD" ?

Naturally it would be something like the Levenshtein distance or another edit distance. If the substrings vary a lot in length you may divide the raw edit distance by the length.

Then find a good clustering algorithm. K-means can't do it since it requires a vector space. There is a discussion about it here : Clustering a long list of strings (words) into similarity groups

Answer 2

There has been a lot of work on this before.

Get books on bioinformatics and sequential pattern mining.

E.g. the SPADE algorithm.