Dynamic order Markov model for categorical sequence clustering.

Area of Science:

• Machine Learning
• Data Mining
• Bioinformatics

Background:

• Markov models are standard for sequential data analysis, capturing temporal dependencies.
• Conventional models assume consecutive states, limiting their ability to detect noisy or disrupted patterns.
• This limitation hinders the discovery of valuable information within sequential datasets.

Purpose of the Study:

• To generalize conventional Markov models for enhanced categorical sequence clustering.
• To introduce a model capable of identifying and utilizing sparse patterns with adaptive lengths.
• To develop a novel similarity measure for comparing sequences and clusters.

Main Methods:

• Proposing the Dynamic order Markov model (DOMM) to handle variable-length sparse patterns with wildcards.
• Developing a sparse pattern detector (SPD) using probability suffix trees (PST) for discovering both sparse and consecutive patterns.
• Implementing a divisive clustering algorithm (DMSC) tailored for the DOMM framework.

Main Results:

• The DOMM effectively identifies sparse patterns, extracting significant statistical information obscured by noise.
• The proposed SPD and DMSC algorithms successfully cluster categorical sequences.
• Experimental results on real-world datasets show the model's promising performance in sequence clustering.

Conclusions:

• The Dynamic order Markov model (DOMM) offers a significant advancement over traditional Markov models for sequence analysis.
• DOMM's ability to detect sparse patterns improves the accuracy and robustness of categorical sequence clustering.
• The developed methods provide a powerful tool for uncovering complex patterns in sequential data.