【作者】 段江娇；

【导师】 施伯乐；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2008， 博士

【摘要】 近年来,时间序列数据挖掘的研究技术在很多领域得以应用。合适的时间序列模型是对序列特性的一种反映,由于基于模型的时间序列数据挖掘方法能够发现序列的内在规律,因此这种方法具有很好的研究前景。隐Markov模型(HiddenMarkov Model,HMM)是一种重要的时间序列模型,本文以HMM为基础,结合监测流数据处理等应用需求,对基于HMM的时间序列数据挖掘相关算法进行了研究,主要内容包括时间序列的识别、HMM的隐状态数的自动选择及初始化、基于HMM的时间序列聚类、股票价格序列的预测等。本文主要的成果包括:(1)HMM的隐状态数的自动选择及初始化针对传统基于BIC(Bayesian Information Criterion)的HMM选择方法的不足,如BIC候选模型多,从而导致算法的复杂度大,本文提出了基于聚类和BIC的HMM选择方法——CBIC(Clustering and BIC),基于相应的聚类结果初始化HMM。由于CBIC改变了BIC候选模型的首选方式,减少了不必要的候选HMM的训练,使得算法复杂度降低。在CBIC算法中,首先对观察数据聚类,聚类的个数是在一定的范围内变化。为了选取最可能的聚类,定义了序列中点的趋变度,并选取聚类结果中似然值序列的趋变度最大的聚类为最可能的聚类。为了提高聚类的效率,提出了混合高斯分布的峰度检测算法,并证明了非重叠的混合高斯分布的峰度值为3,而当各成分都不相同时,重叠的混合高斯分布峰度值不等于3。为了验证CBIC算法的有效性,分别在合成数据集与实际数据集上进行实验,结果表明CBIC算法的复杂性小,计算精度较传统方法高。(2)基于HMM的时间序列聚类由于基于HMM的时间序列层次聚类算法复杂度很高,因而将分区和分层结合的聚类方法有很大优势,如基于k-Means和分层结合的聚类方法Hier-k-HMMs、Hier-moHMMs方法,但是这种方法需要事先指定划分数、HMM的隐状态数和最终的聚类数,另外划分的初始化及HMM的初始化都对聚类质量有很大影响。针对这些不足,提出了一种基于HMM的时间序列聚类算法HBHCTS。采用基于距离阈值的初始分区生成方法,定义了基准概率,提出了一种有效的距离阈值设置方法。HBHCTS算法单遍扫描时间序列集形成初始分区,能以较高置信水平保证初始分区的正确性,避免了指定分区数,如Hier-moHMMs方法,而且HBHCTS使用第三章提出的CBIC方法,可以自动确定HMM的隐状态数和相应的HMM初始化。HBHCTS算法的优点为:1)不需要指定初始的聚类数及相应的初始化;2)不需要指定HMM的隐状态数及相应的初始化;3)可以清楚地给出类的表示;4)对序列长度不敏感;5)当有新的序列加入时,只是将新的序列与已有的类(模型)集合做比较,不需要所有的序列重新执行聚类算法,易于实现增量聚类,初始分区聚类适用于时间序列流数据处理。分别在合成数据集和实际的EEG数据集进行了实验,同Hier-moHMMs方法进行了比较,实验结果表明HBHCTS和CBIC方法是有效的。(3)股票价格序列的自适应预测结合股票价格序列的特点,提出了一种自适应的基于HMM的股票价格预测的方法。原始的IBM、Dell和Apple股票价格序列不适合建立HMM。通过研究股票收益率的短相关特征,认为IBM、Dell和Apple的收益率序列适合用HMM描述。采用本文提出的CBIC方法自动确定HMM隐状态数,在预测过程中当预测误差大于一定阈值时,采用模型自动更新方法建立新的模型。通过对股票价格序列的不同转换,建立相应的HMM,进行了单步值预测和趋势预测。单步值预测同Hassan等人的HMM fusion model方法、ARIMA方法进行了比较,实验结果表明所提出的预测算法在IBM、Dell和Apple股票价格预测中,比现有的不更新模型的方法能得到更好的结果。更多还原

【Abstract】 In recent years, there has been an explosion of interest in mining time series data. Model-based approach is one of the most promising approaches for time series data mining, since it can reveal the hidden characteristic of time series. Hidden Markov model (HMMs) is a main time series model. The paper focuses on the algorithms in HMM-based time series mining, while considering the requirement of data stream application. Main researches are as follows, identifying the time series, determining the number of hidden states of HMMs and initialization, clustering time series based on HMMs, predicting stock price time series based on HMMs. Main contributions are listed as follows.(1) Determining the hidden states number of HMMs and model initializationThere exists several shortcomings in tradition HMM selection method BIC(Bayesian Information Criterion), such as the high complexity raised from the excessive candidate models. A model selection method CBIC (Clustering and BIC) is proposed to overcome the shortcomings. The proposed method alternates the way in selecting the candidate models, avoids the excessive model training processes, and thus reduces the algorithm complexity. The method is based on clustering, in which the number of clusters is considered as the number of hidden states. Trend degree is defined as a criterion to select candidate model set. To improve the performance of clustering, the mixture of Gaussian distribution detection algorithm based on kurtosis computation is proposed. It is proved that the kurtosis of non-overlap Gaussian mixture equals 3, while the kurtosis of overlap Gaussian mixture is not 3, in which each component are different. The effectiveness of CBIC is compared to the BIC, and experiment results based on synthesized data and real world data show that CBIC is of less computation complexity and higher precision for time series representation.(2) Clustering time series based on HMMsModel-based clustering algorithm that combines partitional and hierarchical model based methods is popular, such as Hier-k-HMMs, Hier-moHMMs method. However, this combination method requires supplying the number of initial partition clusters, the hidden states number of HMM and final clusters in priori. Moreover, the initialization of HMM and partition has great effect in clustering quality. In this paper, a novel clustering algorithm HBHCTS (HMM-Based Hierarchical Clustering Time-Series) is proposed. The initial partition is generated by a distance threshold, which can be effectively determined based on basic HMM probability. The advantages of HBHCTS are as follows. 1) The number of initial partition clusters is not specified a priori. 2) The number of hidden states of HMM is not specified a priori. 3) The representation of clusters is explained easily. 4) The algorithm is not sensitive to sequence length. 5) The incremental clustering can be easily done and is adaptive to stream process. The experiment result shows that the proposed approach can achieve better performance in correctness rate than the traditional HMM-based clustering algorithm.(3) Adaptively predicting stock price time seriesAn adaptively predicting algorithm PAAMS (Prediction Algorithm based on Adaptive Model Selection) is proposed. By investigating on the short term characteristic of stock return rate series, it can be verified that the return rate series can be described by HMM, although the original stock price series is not suitable to be fitted with HMM. In PAAMS, the time series are transformed by two ways, and the fitted HMM is dynamically updated when the prediction mean error increases to a predefined threshold. During the update process, the model selection method CBIC is applied to get the best hidden state number and other model parameters. The feasibility and effectiveness of proposed prediction algorithm are explained. Experiments on IBM, Dell and Apple stock price data set are done and the results show that the precision of PAAMS algorithm is better than that of previous study on the same data sets based on fixed model techniques, such as HMM fusion model-based method.更多还原