Abstract: A categorical sequence is composed of finite symbols which are arranged in a certain order.Nowadays,categorical sequences,such as gene sequences,protein sequences,and speech sequences,etc.,widely exist in many application domains of data mining.As a major method for sequence data mining,sequence clustering has a great value in identifying the intrinsic structural of sequence data,while it is also an open problem due to the difficulties in measuring the similarity between sequences.This paper proposed a new similarity measure for categorical sequences,and introduced a length-normalization factor to address the problem that the existing methods are sensitive to the sequences length,and to improve the effectiveness of measuring sequences similarity.Based on the new similarity measure,a new clustering method was proposed,where directed acyclic graphs are constructed according to the similarity between samples and a hierarchical clustering of categorical sequences is performed by graph partitioning.Experimental results on real-world datasets show that the new methods based on the normalized similarity measure are able to improve the clustering accuracy significantly.

Key words: Categorical sequence,Clustering,Similarity,Normalized variant