Symbolic Sequence Classification in the Fractal Space

Sequence classification has a range of applications and attracted a lot of attentions. Different from feature vectors, symbolic sequences have no explicit features. Due to this limitation, even with sophisticated feature selection techniques, the dimension of potential feature space could be very high, making classification methods hard to capture the nature of sequences. In this paper, we propose a novel scheme that first constructs a new lower dimensional representation space for symbolic sequences. Next, we carry out learning in this newly generated space rather than on the sequences. The first step is implemented with a chaos game representation, which converts a long sequence into a graphical form by applying an iterated function system on the input. For this reason, this new target space is referred as "fractal space" in this paper. The second step consists of carrying out sequence comparison and quantitative analysis with an alignment-free measure based on the holistic features from the sequences. This scheme is highly flexible and could permit high-performance implementation. The experimental results demonstrate the effectiveness and efficiency of our proposed approach.