what is the appropriate one-class classifier for sequenced categorical data?

Question

Can someone suggest an algorithm for an outlier detection system? My requirements are:

1. it supposed to be a one class classifier, where on training phase, it only fed 'normal' data
2. however the normal class can have multiple sub-class. (we can see it as multi-class classification with an 'other' class, where this 'other' class is never learned)
3. all features are categorical
4. features have sequence relation, so I need it analysed in sequence.
5. I need a lighter algorithm for real time application
6. optionally - I need an on-line learning capability

I have tried HMM. However it still very heavy to my liking. Furthermore it required me to create different model for each sub-normal-class.

Next I tried one-class-svm (with one hot encoder). It was light enough. However results was incorrect. I'm guessing it was because this approach is not appropriate for sequence analysis?

Now I am in the middle of Neural Network trial. I read that Autoencoder is an approach for one-class-classification. My results so far is not satisfying in term of learning time and detection results.

Can someone suggest a better (machine learning algorithm) approach?

Answer 1

A solution could be to determine a set of representative sequences (using for instance the TraMineR R package). Outliers would then be sequences that lie at more than a given threshold distance from any representative. See Gabadinho and Ritschard (2013) for details on representative sequences and Studer and Ritschard (2016) for a discussion on the distances that could be used.

An alternative is to fit probabilistic suffix trees on the sequences with the PST R package, and then to consider the likelihood of the additional sequences for the fitted tree. Unlikely sequences would be outliers.

Hope this helps.