基于时间序列的相似子模式发现算法

基于时问序列的数据挖掘时，一般需要对时间序列离散化，再聚类成不同的子模式。已有的方法常忽略时间序列本身的位置和整体特征，并且计算量大。针对其不足，文中提出一种检索时间序列分段关键点的算法，以关键点为边界分段，使用形态距离测度和快速剪除的算法，高效简便地检索出相似子模式。     

基于符号化聚合近似的时间序列相似性复合度量方法

基于关键点的符号化聚合近似(SAX)改进算法(KP_SAX)在SAX的基础上利用关键点对时间序列进行点距离度量,能更有效地计算时间序列的相似性,但对时间序列的模式信息体现不足,仍不能合理地度量时间序列的相似性。针对SAX与KP_SAX存在的缺陷,提出了一种基于SAX的时间序列相似性复合度量方法。综合了点距离和模式距离两种度量,先利用关键点将分段累积近似(PAA)法平均分段进一步细分成各个子分段;再用一个包含此两种距离信息的三元组表示每个子分段;最后利用定义的复合距离度量公式计算时间序列间的相似性,计算结果能更有效地反映时间序列间的差异。实验结果显示,改进方法的时间效率比KP_SAX算法仅降低了0.96%,而在时间序列区分度性能上优于KP_SAX算法和SAX算法。     

基于导数序列的时间序列同构关系发现

时间序列子序列匹配作为时间序列检索、聚类、分类、异常监测等挖掘任务的基础被广泛研究。但传统的时间序列子序列匹配都是对精确相同或近似相同的模式进行匹配,为此定义了一种全新的具有相似发展趋势的序列模式——时间序列同构关系,经过数学推导给出了时间序列同构关系判定的法则,并基于此提出了同构关系时间序列片段发现的算法。该算法首先对原始时间序列进行预处理,然后分段拟合后对各时间序列分段进行同构关系判定。针对现实背景数据难以满足理论约束的问题,通过定义一个同构关系容忍度参数使实际时间序列数据的同构关系挖掘成为可能。实验结果表明,该算法能有效挖掘出满足同构关系的时间序列片段。     

时序数据库中快速相似搜索的算法研究

针对时间序列,本文提出了一种新的数据表示方法.该方法通过将时间序列分成若干段,并从每个分段中提取一个特征向量,从而用一个特征向量集作为该时间序列的逻辑表示.在此基础上,采用时间弯曲距离作为相似模型,提出了一种改进的KMP算法作为检索方法.此算法能够快速挖掘出时序数据库中与给定查询序列相似的所有(子)序列.该算法具有较高的效率.     

基于子序列相似性的时间序列语义挖掘算法

时间序列是对某个事物或系统进行连续同间隔测量得到的数值序列,挖掘时间序列中潜在的语义信息对于发现系统运行规律或识别系统突发异常至关重要,然而目前多数时间序列语义挖掘算法对于时间序列数据特征有一定的约束条件,难以处理海量且特征各异的时间序列数据。针对该问题,提出一种基于子序列相似性的时间序列语义挖掘算法。通过计算子序列的相似性,将时间序列分割成片段序列进行两级聚类,识别出时间序列中潜在的物理状态。引入基于概率的迭代模式,根据候选分段情况动态调整子序列被选为参考子序列的概率,保证参考子序列涵盖全部物理状态。实验结果表明,该算法在PAMAP、Barbet等5个真实数据集上的识别准确率均超过90%,相比于FLUSS、pHMM、AutoPlait算法具有更高的识别准确率与运行效率以及更强的通用性。     

基于符号化表示的时间序列频繁子序列挖掘

提出一种新的基于符号化表示的时间序列频繁子序列的挖掘算法。利用基于PAA的分段线性表示法进行降维,通过在高斯分布下设置断点,实现时间序列符号化表示,利用投影数据库挖掘频繁子序列。该算法简单、新颖,运行快速,简化了子序列支持数的计算。     

基于形态模式的时间序列相似性度量算法

时间序列的特征表示与相似性度量是时间序列数据挖掘的重要基础。针对现有的序列表示方法难以具体反映序列的形态变化趋势,导致相似度量结果不精确的问题,提出一种新的基于形态模式的相似性度量算法。该算法在分段线性表示的基础上,根据序列在不同时段的斜率变化情况,划分序列的分段形态模式并用特殊的字符进行表示,把时间序列转换成字符串序列,利用最长公共子序列方法计算字符串序列的距离作为时间序列之间的距离。最后通过实验验证该方法的有效性。理论分析和实验证明该方法对数据点的值不敏感,能够减少噪声的干扰,而且具有较高的准确性。     

一种时间序列快速分段及符号化方法

作为一类重要的复杂类型数据,时间序列已成为数据挖掘领域的热点研究对象之一.针对时间序列的挖掘通常首先需要将时间序列分段并转变为种类有限的符号序列,以利于进一步进行时间序列模式挖掘.针对当前的时间序列分段方法复杂度较大,效率不高等问题,本文提出了一种简单高效的基于拐点检测的时间序列分段方法,并且采用动态时间弯曲度量计算不等长子序列的相异度,最后运用层次化聚类算法实现子序列的分类及符号化.实验表明,本文所提出的方法切实可行,实验结果具有较为明显的物理意义.     

基于二次回归的时间序列分割算法

提出了基于关键点的时间序列分割算法。首先利用关键点方法压缩时间序列,完成时间序列的表示;然后利用二次回归及DTW方法完成时间序列的分割。分割后的时间序列主要用于异常模式的检测,有较好的效果。     

基于短序列分组和拼接策略的子序列快速查询算法

子序列查询技术在金融、商业、医疗等领域均有重要应用,但因DTW（dynamic time warping）等相似性比对算法的时间复杂度较高,子序列长度对检索时间影响很大,限制了数据集上长子序列检索的效率。针对这一问题提出一种子序列快速查询算法。首先对数据集中特定长度下所有子序列进行分组并标记出代表性子序列;然后在查询时将查询序列切分成定长的小段序列,并用DTW算法确定与小段序列相似的代表子序列候选集;最后对候选集进行序列拼接,获取到查询结果序列。实验表明新算法效率较典型算法提高约10倍。     

基于关键点的不同长度时间序列相似性度量

目前,时间序列的相似性大多是在原始序列上进行判断和比较的,原始序列维度较高,计算量大,不利于相似性比较。提出了新的关键点（转折点或极值点）算法,除利用常用的极值法求非单调序列的关键点外,还提出了求单调序列关键点的新算法,利用该算法可以压缩时间序列,降低维度,又能保持序列的轮廓。在关键点时间序列上提出了新的相似性判定算法,利用该算法可计算任意两序列的相似度,并且提高了相似性判定的鲁棒性,减少人为干预设置阈值带来的影响。实验结果表明,基于时间序列关键点的相似性算法能很好地判定任意两序列的相似性,减少了计算量,提高了鲁棒性及减少人为干扰,对时间序列数据挖掘中的聚类与预测有很好的帮助作用。     

一种时间序列动态聚类的算法

针对时间序列传统静态聚类问题,提出了对时间序列进行动态聚类的方法。该方法首先提取时间序列的关键点集合,根据改进的FCM算法找到动态特征明显的时间序列,再利用提出的动态聚类算法确定此类时间序列在不同时间段的所属类别,在改进的FCM算法中采用兰氏距离可以使其对奇异值不敏感。实验结果反映出动态特征明显的时间序列类别随时间演化的特性,表明了方法的可行性和有效性。与已有算法相比,该方法揭示了时间序列的部分动态特征。该方法还可以运用于研究数据挖掘的其他问题。     

时间序列相似性度量在水文数据挖掘中的应用研究

相似性度量方法是时间序列相似性研究的重要课题,同时也是水文时间序列相似性挖掘的关键问题之一.充分分析目前相似性度量的研究成果,结合水文时间序列相似性挖掘模型,通过实验探索适合水文数据特点的相似性度量方法.     

ESPSA: A prediction-based algorithm for streaming time series segmentation

Streaming time series segmentation is one of the major problems in streaming time series mining, which can create the high-level representation of streaming time series, and thus can provide important supports for many time series mining tasks, such as indexing, clustering, classification, and discord discovery. However, the data elements in streaming time series, which usually arrive online, are fast-changing and unbounded in size, consequently, leading to a higher requirement for the computing efficiency of time series segmentation. Thus, it is a challenging task how to segment streaming time series accurately under the constraint of computing efficiency. In this paper, we propose exponential smoothing prediction-based segmentation algorithm (ESPSA). The proposed algorithm is developed based on a sliding window model, and uses the typical exponential smoothing method to calculate the smoothing value of arrived data element of streaming time series as the prediction value of the future data. Besides, to determine whether a data element is a segmenting key point, we study the statistical characteristics of the prediction error and then deduce the relationship between the prediction error and the compression rate. The extensive experiments on both synthetic and real datasets demonstrate that the proposed algorithm can segment streaming time series effectively and efficiently. More importantly, compared with candidate algorithms, the proposed algorithm can reduce the computing time by orders of magnitude.     

时间序列数据挖掘的相似性度量综述

在时间序列数据挖掘中, 时间序列相似性是一个重要的概念. 对于诸多算法而言, 能否与一种合适的相似性度量方法结合应用, 对其挖掘性能有着关键影响. 然而, 至今仍没有统一的度量相似性的方法. 对此, 首先综述了常用的相似性度量方法, 分析了各自的优点与不足; 其次, 讨论了近年来出现的时序相似性的新解释及其度量方法; 再次, 探讨了相似性度量在时序挖掘任务中的应用以及与挖掘精度的关系; 最后给出了关于时序相似性度量进一步的研究方向.     

一种基于DTW聚类的水文时间序列相似性挖掘方法

水文时间序列相似性挖掘是水文时间序列挖掘的重要方面,对洪水预报、防洪调度等具有重要意义。针对水文数据的特点,提出了一种基于DTW聚类的水文时间序列相似性挖掘方法。该方法先对数据进行小波去噪、特征点分段以及语义划分,再基于DTW距离对划分后的子序列做层次聚类并符号化;然后根据符号序列间的编辑距离筛选候选集;最后通过序列间的DTW距离进行精确匹配,获取相似水文时间序列。以滁河六合站的日水位数据进行实验,结果表明,所提方法能够有效地缩小候选集,提高查找语义相似的水文时间序列的效率。     

一种基于始末距离的时间序列符号聚合近似表示方法

时间序列数据的特征表示方法是时间序列数据挖掘任务的关键技术,符号聚合近似表示(SAX)是特征表示方法中比较常用的一种。针对SAX算法在各序列段表示符号一致时无法区分时间序列间的相似性这一缺陷,提出了一种基于始末距离的时间序列符号聚合近似表示方法(SAX_SM)。由于时间序列有很强的形态趋势,因此文中提出的方法选用起点和终点来表示各个序列段的形态特征,并使用各序列段的形态特征和表示符号来近似表示时间序列数据,以将其从高维空间映射到低维空间;然后,针对起点和终点构建始末距离来计算两序列段间的形态距离;最后, 结合 始末距离和符号距离定义一种新的距离度量方式,以更客观地度量时间序列间的相似性。理论分析表明,该距离度量满足下界定理。在20组UCR时间序列数据集上的实验表明,所提SAX_SM方法在13个数据集中获得了最高的分类准确率(包含并列最大的),而SAX只在6个数据集中获得了最高的分类准确率(包含并列最大的),因此SAX_SM具有比SAX更优的分类效果。     

流程业实时数据压缩技术的研究与实现

流程工业存在着大量的秒级的时间序列数据，面对这样的海量高维数据，如何压缩存储和挖掘，是一个关键的问题。文章针对流程工业中实时数据存储的特点，提出了一种新型的适配性取样压缩方法，将实时数据流整合到数据库中，并分析了在压缩存储后的数据挖掘方法。以电厂实时系统为例，对其实现进行了论述。     

基于变化点的时间序列近似表示

时间序列的近似表示能够提高时间序列数据挖掘的效率和可靠性。提出了一种基于变化点的时间序列近似表示,具有简单直观、近似质量高、适应能力强等优点。在来自不同领域的真实数据集上的实验表明:与时间序列的重要点分段表示和分段常量表示相比,基于变化点的时间序列近似表示在近似质量和适应能力上都具有明显的优势。