基于重要点的时间序列固定分段数分段算法

基于重要点探测技术的时间序列线性分段算法能较好地保留序列的全局特征和拟合高精确度。传统的基于重要点时间序列分段算法,只能通过误差阈值来控制分段,该方法不能预计分段数量,不能适应后期要求分段数量一定的应用。提出一种基于序列重要点的时间序列固定分段数的分段算法—PLR_FPIP,该方法借用二叉树层次遍历的思路,重新调整原方法的分段次序,使用重要点组成的直线段近似描述时间序列,该方法能够在分段数量一定的情况下对时间序列分段。实验证明,该分段算法能在固定分段数的情况下反映时间序列的主体特征,算法简单快速,整体拟合误差小。     

基于重要点的多分辨率检索法的时间序列表示

时间序列的表示是时序数据挖掘的一个重要问题.重要点的分段表示法(IP)是目前应用最为广泛的时间序列特征提取方法之一,具有较好的数据压缩和去除噪声能力,但参数的选择对时间序列的近似效果有很大的影响而且难以找到重要的转折点.基于多分辨率的重要点检索分段方法(MIP)也是一种时间序列特征提取方法,该方法能很好地近似时间序列,但检索次数难以确定且运行效率比较低.为了改进以上两种方法的缺陷,提出了一种新的基于重要点的多分辨率检索表示法(MRIP).实验结果表明,与基于重要点分段方法相比,该方法误差更小,具有很好的压缩率,并能去除噪音干扰;与基于多分辨率的重要点检索分段方法相比,能较好地确定检索次数的范围,在近似效果相当的情况下,运算效率更高.     

基于多尺度的时间序列固定分段数线性表示

针对目前的时间序列线性表示方法多采用启发式方法提取局部特征点作为分段点,容易陷入局部最优化,不能很好地表示时间序列全局特征,而且多采用单一的拟合误差作为阈值,不能准确预计分段数量,不利于后期进行的时间序列分析应用的问题。提出了一种新的固定分段数的表示方法--PLR_BTBU,首先根据二叉树层次遍历的思想,提取时间序列全局特征点将时间序列初始分段,再通过斜率变化特征将整个时间序列符号化,以各初始分段内的符号特征来确定各初始分段中的分段点分布,最后采用一种改进的固定分段数的自底向上融合算法,将各个子序列逐步融合到要求的分段数。实验结果表明,与已有的方法相比,该方法不仅较好地保留时间序列的全局特征,而且拟合后的时间序列和原时间序列之间的拟合误差更小。     

基于时间序列分段的气象数据压缩算法

直接采用风速、温湿压等气象参数原始时间序列对其进行短期预测、相似匹配、分类聚类等数据挖掘工作不但效率低下,而且会影响时间序列数据挖掘的准确性和可靠性。提出了一种简单快速的基于特征点的筛选算法对时间序列进行分段线性表示。对气象参数等时间序列进行实验,并就计算性能和拟合误差与另外一种序列分段算法进行了对比分析,结果表明该方法能有效地提取序列的主要形态,同时降低对于阈值的依赖,具有计算代价小、快速方便、通用性强等特点,在气象数据压缩上具有较好的应用前景。     

基于斜率提取边缘点的时间序列分段线性表示方法

本文引入解析几何中的斜率，提出了一种新颖的基于斜率提取边缘点的时间序列分段线性表示方法SEEP。对于斜率变化范围比较集中的时间序列，SEEP表示方法有着非常好的效果，与以往的分段线性表示方法相比，SEEP表示方法与原始时间序列之间的拟合误差更小，而且要小很多；对于斜率变化范围比较大的时间序列，SEEP表示方法与原始时间序列之间的拟合误差，和以往的分段线性表示方法相比，也相差不大，并且SEEP表示方法计算简单，易于实现。算法的时间复杂度仅为O（n），     

时间序列高阶分段表示方法

针对分段线性表示(即一阶线性函数表示)或分段常数表示(即零阶函数表示)在时间序列近似表示中拟合误差较大的问题,提出时间序列高阶函数分段表示方法。通过建立高阶函数候选集模型,利用拟合误差指标选取最优函数,为保证在分段点处连续,引入断点处约束条件;在分段点选取方式上,设定观测值变化阈值及分段区间阈值,保证压缩率的同时,保留重要点信息。实验结果表明,该算法相对于分段线性表示和分段常数表示,能更好地拟合原始序列。     

基于时态边缘算子的时间序列分段线性表示

时间序列的分段线性表示算法通常基于单一的启发式规则,难以适用于不同数据特征的时间序列。借鉴了边缘算子的思想来提取时间序列的边缘点,提出了一种基于时态边缘算子的时间序列分段线性表示算法。在来自不同领域的公开数据集上进行的实验结果表明：与两种主要的分段线性表示算法相比,该算法具有更好的拟合性能,并且更为稳定,能够适用于各类不同数据特征的时间序列。     

基于趋势转折点的时间序列分段线性表示

分段线性表示是时间序列降维的有效方法。在总结分析序列趋势变化特点的基础上,提出了一种基于趋势转折点的时间序列分段线性表示算法。首先定义了趋势转折点作为时间序列分段点的备选集,以点到区域的距离度量趋势转折点的重要性,再根据给定的阈值选择重要趋势转折点作为分段点,对时间序列进行分段线性表示。通过与其他6种方法进行实验比较,结果表明：所提方法在具有较好的拟合质量和适应能力以及对转折点明显的序列,都表现出较强的抗噪声干扰能力。     

一种基于信息熵的时间序列分段线性表示方法

针对部分时间序列具有高维、大数据量及数据更新速度较快的特点, 导致在原始时间序列上难以进行数据挖掘的问题, 提出一种基于信息熵的时间序列分段线性表示方法——PLR_IE。该算法利用信息熵作为评判重要点数量的性能指标, 从序列中提取重要分段点的数量分布情况, 利用重要点组成的序列重新拟合原始时间序列, 为下一步数据挖掘提供基础。实验结果表明, 该方法能高效地提取出序列主要特征、拟合原始序列。     

基于双曲正切函数约束的时间序列建模表示

针对传统的时间序列分段算法往往忽略时间序列的时间特性，导致分段结果不够精确，对此，提出基于双曲正切函数约束的时间序列建模表示算法。该算法在分段聚合近似的基础上引入双曲正切函数并且提出了移动增强因子的概念，在考虑时间影响的基础上抽取出各个子序列所含信息量的差异完成最终的时间序列分段。实验表明该算法有较小的拟合误差，能够更好地利用分段后的序列，完成宏观的相似性查找等工作，并且满足时间序列动态增长的特点，算法的通用性、普适性、准确性均有所提高。     

基于多元时间序列的自适应贪婪高斯分段算法

现有多元时间序列分段算法中分段点的选择以及分段个数的确定往往需要分别独立完成,大大增加了算法的计算复杂度.为解决上述问题,提出一种基于多元时间序列的自适应贪婪高斯分段算法.该算法将多元时间序列各个分段所对应的数据解释为来自不同多元高斯分布的独立样本,进而将分段问题转化为协方差正则化的最大似然估计问题进行求解.为提高学习效率,采用贪婪搜寻方法使每个段的似然值最大化进而近似地找到最优分段点,并且在搜寻的过程中利用信息增益方法自适应地获取最优的分段个数,避免分段个数确定和分段点选择分别独立进行,从而减少计算的复杂度.基于多种领域的真实数据集实验结果表明,所提出方法的分段精度以及运行效率均优于传统方法,并且能够有效完成多元时间序列的异常检测任务.     

一种基于重要点的时间序列分割方法

分段线性表示是时间序列降维的有效方法,其关键在于分割点的确定。在时间序列分段线性表示的基础上,提出一种新的基于重要点的时间序列分割方法。与一般方法比较相邻三点关系不同的是,将时间窗扩展为前一重要点、待考察点和一个指定时间窗组成的区间,再通过比较数据点前后模式变化来确定重要点。通过与其他7种分割方法进行实验比较,证明该方法适应能力强,不但分割结果总体质量高,在压缩率相同时具有更小的拟合误差,而且能够有效滤除噪声,发现时间序列的模式特征。     

An iterative end point fitting based trend segmentation representation of time series and its distance measure

Symbolic approximation representation is a key problem in time series which can significantly affect the accuracy and efficiency of data mining. However, since currently used methods divide the original sequence into segments with equal size, they ignore one of the most important features of time series: the trend. To overcome the defect of equal-sized segmenting, we present a trend segmentation representation based on Iterative End Point Fitting algorithm (IEPF-TSR). Particularly, we use iterative end point fitting (IEPF) algorithm to search the break point of each segment and get the trend segmentation. Then a triplet based symbolic representation is proposed for each segment which includes the start point, mean and trend. Moreover, we define a new distance measure method based on trend segmentation representation (TSR-DIST) which can suit for two representations with different lengths, and prove it to be the lower bound of Euclidean distance. The experimental results on UCR datasets show that the proposed representation and distance measure achieve better performance than the state-of-the-art methods in the classification accuracy and the dimensionality reduction ratio.

     

基于KPCA和G-G聚类的多元时间序列模糊分段

针对传统的Gath-Geva(G-G)模糊分段方法需要人为设置参数,对高维时间序列分段效率低的问题,提出一种基于核主元分析(KPCA)和G-G聚类的多元时间序列模糊分段方法.首先,该算法利用KPCA方法对多元时间序列进行特征提取,去除冗余及无关变量的影响;然后,通过近邻传播算法(AP)得到分段数目的上界;最后,将时间信息考虑在内,基于所提出的MDBI有效值指标以及G-G模糊聚类在低维多元时间序列上实现多元时间序列的最佳模糊分段.实验结果表明,所提出算法可以快速有效地检测出时间序列的某种突然和渐近变化的趋势,在准确性和运行效率方面均得到了提升.     

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.     

基于Matrix Profile的时间序列分割技术改进

时间序列分割是数据挖掘领域中的一个重要研究方向.目前基于矩阵轮廓(matrix profile, MP)的时间序列分割技术得到了越来越多研究人员的关注,并且取得了不错的研究成果.不过该技术及其衍生算法仍然存在不足:首先,基于矩阵轮廓的快速低代价语义分割算法中对给定活动状态的时间序列分割时,最近邻之间通过弧进行连接,会出现弧跨越非目标活动状态匹配相似子序列问题;其次,现有提取分割点算法在提取分割点时采用给定长度窗口,容易得到与真实值偏差较大的分割点,降低准确性.针对以上问题,提出一种限制弧跨越的时间序列分割算法(limit arc curve cross-FLOSS, LAC-FLOSS),该算法给弧添加权重,形成一种带权弧,并通过设置匹配距离阈值解决弧的跨状态子序列误匹配问题.此外,提出一种改进的提取分割点算法(improved extract regimes, IER),它通过纠正弧跨越(corrected arc crossings, CAC)序列的形状特性,从波谷中提取极值,避免直接使用窗口在非拐点处取到分割点的问题.在公开数据集datasets＿seg和Mobi Act上面进行...     

融合视觉模型和最大类间方差的阈值分割算法

针对传统二维直方图的区域划分方法存在把图像的部分目标点和背景点错误划分为边缘点或噪声点,而把部分边缘点和噪声点划分为目标点和背景点的缺点,以及传统二维最大类间方差阈值分割算法的时间复杂度较高的缺点,提出了采用视觉模型构造二维直方图,并提出了该二维直方图的区域划分方法,同时还把提出的二维直方图应用到最大类间方差阈值分割算法中。根据分割时间、分类误差、均匀性等定量评价标准,做了一系列实验,与几种典型的二维阈值分割算法相比,提出的阈值分割算法在降低计算复杂度的同时还具有很好的分割性能。     

基于SLIC和区域生长的目标分割算法

传统区域生长算法的分割结果依赖于种子点的选取,且图像自身的噪声以及灰度值不均匀等问题易在分割目标过程中形成分割空洞,针对以上问题提出了基于超像素的改进区域生长算法。采用拉普拉斯锐化,增强待分割目标边界,之后根据像素灰度相似的特征采用SLIC（简单线性迭代聚类算法）超像素分割将原始图像分割成若干不规则区域,建立不规则区域间的无向加权图,选取种子区域,根据无向加权图以分割好的不规则区域为单位进行区域生长,最后在分割目标边缘处以像素为单位做区域生长,细化边界。对比于传统区域生长算法,改进后的算法在分割结果上受种子点选取影响较小,且能有效地解决分割空洞等问题。对比于聚类分割,Otsu（最大类间方差）阈值分割法等典型算法,该算法在分割精度上具有明显优势。