Research On Multipartite Graph Oriented Time Series Analysis Methods

As an important data mining task, time series clustering has been received plenty of researches. The research work in time series clustering can be roughly classified into two categories: subsequence clustering and whole clustering. The former performs clustering on the subsequences in the single input time series, while the latter performs clustering on the input time series set. Many existing whole clustering algorithms focused on capturing time series' dynamic behavior characteristic, which is a summary of that time series, and consequently carry out the clustering on the bases of the dynamic behavior characteristics. For example, some methods first build Markov models to fit individual time series, and then do clustering on the resulting Markov models. However, all the existing whole clustering methods ignored two kinds of inter-time-series dynamic behavior: one is group-level interaction behavior, e.g. the merging and splitting of clusters; the other is individual-level interaction behavior, such as a time series' joining into or leaving a cluster. To solve this problem, this dissertation firstly proposes a special multipartite graph, which is called System Morphing Graph (SMG), to model the dynamic interaction behavior among time series. This multipartite graph can model and represent both the group-level behavior and the individual-level interaction inside a set of time series. With this graph, one can not only trace the course of changing, but also take advantages of the captured behavior. Secondly, this dissertation puts forward Morphing Cluster Dynamics Analysis (MCDA) algorithm to generate System Morphing Graphs from a set of time series. 3 major steps of this algorithm are timeline segmentation, TS segment clustering, and edge building. Three alternative implementation schemes are suggested for the segmentation step and the clustering step respectively, in order to adapt the MCDA algorithm to different datasets and different application requirements. To reasonably evaluate the quality of a generated SMG, we also bring forward several measures of SMG from different aspects ranging from group behavior aspect to individual behavior aspect. These measures are extensively used in the experiments to compare different MCDA implementations. We lastly propose two applications of MCDA to make use of the interaction behavior captured by SMG. The first application is anomaly detection, whose task is to discover the time series with unusual behavior inside a large time series set. Our solution to this problem is using system morphing graph to evaluate the exceptional degree of each time series and then regarding those time series with high exceptional degrees as anomaly. The second application is time series discretization, which is to transform a time series into a symbolic sequence. Our approach to it is building a system morphing graph from a time series set, and then using each morphing path as a discrete symbol, and at last transforms each time series to the sequence of its owning morphing paths. This approach not only discretizes time series, but also reduces or compresses the original data.