《《Efficient algorithms for segmentation of item-set time series 》.pdf

Data Min Knowl Disc (2008) 17:377–401 DOI 10.1007/s10618-008-0095-0 Efficient algorithms for segmentation of item-set time series Parvathi Chundi · Daniel J. Rosenkrantz Received: 5 February 2008 / Accepted: 28 March 2008 / Published online: 18 April 2008 Springer Science+Business Media, LLC 2008 Abstract We propose a special type of time series, which we call an item-set time series, to facilitate the temporal analysis of software version histories, email logs, stock market data, etc. In an item-set time series, each observed data value is a set of discrete items. We formalize the concept of an item-set time series and present effi- cient algorithms for segmenting a given item-set time series. Segmentation of a time series partitions the time series into a sequence of segments where each segment is constructed by combining consecutive time points of the time series. Each segment is associated with an item set that is computed from the item sets of the time points in that segment, using a function which we call a measure function. We then define a concept called the segment difference, which measures the difference between the item set of a segment and the item sets of the time points in that segment. The segment difference values are required to construct an optimal segmentation of the time series. We describe novel and efficient algorithms to compute segment difference values for each of the measure functions described in the paper. We outline a dynamic programming based scheme to construct an optimal segmentation of the given item-set time series. We use the item-set time series segmentation techniques to analyze the temporal content of three different data sets–Enron email, stock market data, and a synthetic data set. The experimental results show that an optimal segmentation of item-set time series data captures much more temporal content than a segmentation constructed based on Responsible editor: Eamonn Keogh. P. Chundi ( )