Morphing cluster dynamics: time series clustering with multipartite graph

A new time series clustering algorithm named morphing cluster dynamics is put forward. This algorithm can capture two levels of inter-time-series interaction behavior among a large set of time series: (i) group level, which includes the merges and splits of clusters, and (ii) individual-to-group level, such as a time series joins or leaves a cluster. In order to do so, it first reduces the TS set into a system morphing graph, a multipartite graph is employed to represent the latent interactions, and then extract strong interaction patterns from this graph. A system morphing graph is built by three steps: firstly, the input time series set is divided into sets of segments along the time line, and each segment set serves as a partite of the graph; then, each segment set is clustered and the resulting clusters serves as the vertices in the graph; third, the edges are built according to member-sharing relationships between clusters. System morphing graphs can model the captured TS interactions. Because this algorithm both cuts and concatenates time series, it does not fit into either whole clustering or subsequence clustering.