A Novel Approach for Clustering Categorical Time Series Using Dissimilarity Based Measure

A dissimilarity-based measure is considered to develop a framework for clustering categorical time series. By assessing both closeness of raw categorical values and proximity between dynamic behavior it measures the dissimilarity between two categorical time series. For the latter, the temporal correlation for categorical-valued sequences is computed using a particular index[1]. The dissimilarity measure is then used to perform clustering by considering a modified version of the k-modes algorithm specifically designed to provide with a better characterization of the clusters. Most of the clustering algorithms handling data with categorical attributes focus on the “static� nature of the problem. More specifically, the similarity search between two data objects is based on exact matches between attributes, without regarding proximity between temporal behaviors. This is equivalent to ignore the order of occurrence. Nevertheless, in many real applications the clustering task is precisely aimed to identify groups of data objects showing similar behavior over time. A typical example is the problem motivating the present work, namely identifying web-user profiles according to the browsing behavior on a particular web site. Model-based clustering assumes the dynamic structure of all data can be represented by Markov chain models. Distance-based clustering is a more intuitive approach which relies on the choice of a suitable measure of dissimilarity between data objects[2],[3].