【作者】 范智华；

【导师】 王克宏；

【作者基本信息】 清华大学 ， 计算机科学与技术， 2004， 硕士

【摘要】 针对时间序列数据的聚类分析是一类重要的数据挖掘任务,得到了广泛和深入的研究。它可分为子序列聚类分析与整序列聚类分析两类,其中子序列聚类分析以时间序列所包含的子序列为聚类对象,而整序列聚类分析则以完整的时间序列作为聚类对象。现有整序列聚类方法片面重视单个时间序列的动态特性,却忽视了时间序列之间潜在的两种级别的动态交互行为:其一是群体级行为,例如聚类的合并和分裂;其二是个体级行为,如某个时间序列加入或退出某聚类。针对这一问题,本文首先基于图论理论,提出了以多部图为形式的时间序列动态交互行为模型。该多部图称为系统演化图,它同时实现了对时间序列之间的群体级动态交互行为和个体级动态交互行为的捕捉和建模。它不但能够追踪各个时间序列的来龙去脉,而且能对这些行为加以利用。接着,本文提出了生成系统演化图的算法,即演化聚类动态分析法。该算法通过切分、段表聚类、搜边等步骤将输入的时间序列集转化为系统演化图。其中切分和段表聚类两步均有三种可选的实现方式,以便于用户根据实际应用中数据集或要求的特殊性选取合适的算法实现形式。为了合理地评价生成的系统演化图的优劣,我们提出了从群体、个体行为捕捉能力等不同角度对系统演化图进行评测的若干种度量,并以这些度量为目标,对演化聚类动态分析算法进行了大量的实验分析。最后,作为应用,本文将使用演化聚类动态分析算法来解决两个实际问题。一是异常检测,其任务是从时间序列集中找出行为异常的时间序列。对此,我们提出了以系统演化图为基础的异常检测法,它在演化路径的基础上计算出每个时间序列相对于各大群体的异常程度,这样取得了直观上较好的结果。二是时间序列离散化,即把时间序列转化成一个符号序列。我们的方法以系统演化图为蓝本,首先把孤立的时间序列分配到最近的演化路径中去,然后以演化路径的标识作为每个时间序列在该时间段内的离散化符号。这样不仅能实现离散化,还可以达到数据缩减的功效。更多还原

【Abstract】 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 <WP=5>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.更多还原