基于趋势特征的时间序列符号聚集近似表示方法

针对时间序列数据降维过程中易丢失趋势特征信息的问题,提出一种基于趋势特征的时间序列符号聚集近似表示方法,除保留各序列分段的均值特征外,采用分段的趋势距离因子及趋势形态因子共同描述序列趋势特征;并给出了满足下界密封性的距离度量方法,从而更好地表示具有不同趋势特征的时间序列。在公共数据集上的实验结果表明,该方法在分类误报率、降维比率等方面比符号聚集近似方法（SAX）和基于趋势距离的时间序列符号近似表示方法（SAX＿TD）有10%以上的下降,并具有更好的下界密封性。实验结果证明,该算法在进行时间序列压缩的同时充分保留时间序列的趋势变化形态,从而提高时间序列数据挖掘的效率。     

面向时间序列分类任务的SAX方法特性及可视化探索

针对时间序列特征SAX表示方法的信息损失及保留情况,利用信息嵌入成本(IEC)这一度量手段来分析SAX方法的内在统计特性,并通过复杂网络表示方法建立时间序列的图形化表示,达到时间序列数据分析及可视化的目的.对于时间序列数据,首先进行SAX特征表示并计算其IEC值;然后对原始时间序列及其SAX表示分别进行分类并对比分类错误率,分析IEC分值与分类错误率的关系;最后根据数据自身特点及IEC分值选取具有代表性的数据集,将SAX表示转化为马尔科夫转移矩阵,进而采用复杂网络表示方法进行可视化展示.对原始时间序列采用分位数离散化特征表示方法,与SAX方法进行可视化效果对比的实验结果表明,SAX方法能在有效降低复杂性的同时保留原始时间序列中的核心信息.文中提供了IEC分值作为SAX方法有效性判别的一个参照标准,并建立了一个有效的分析评估与可视化方法框架.     

融合趋势信息的时间序列符号聚合近似方法

为解决符号聚合近似方法（SAX）表示时间序列时忽略序列局部趋势的问题,提出一种融合形态趋势信息的时间序列符号聚合近似方法。该方法以子序列段中的最大值和最小值以及它们两者之间的相对位置为依据,定义一种新的趋势指标来描述子序列段的趋势,并使用融合趋势指标的符号矢量来近似表示时间序列。针对所提表示方法,给出一种新的距离度量方法,并在UCR数据集和电机转矩数据集上进行分类实验,实验结果表明,所提方法在绝大多数数据集上获得了较SAX方法更高的分类准确率,能够有效弥补SAX方法表示时间序列时忽略局部趋势的不足。     

改进的多元时间序列符号化表示方法研究

符号化表示技术,可以有效降低时间序列的维度,是实现海量时间序列数据挖掘的基础.聚类结果的精度是运用聚类方法对多元时间序列进行符号化表示的关键.运用共同马氏距离虽然可以实现多元时间序列的符号化表示,但忽略了不同类样本数量对聚类结果的影响,从而降低了符号化表示的有效性.针对上述问题,提出一种改进共同马氏距离的多元时间序列符号化表示方法,通过改进共同协方差矩阵的计算方法,优化了聚类结果,从而提高了符号化表示的有效性.仿真结果表明,改进后的方法可以更加有效地对多元时间序列进行符号化表示.     

基于截止投票的SVM集成快速分类方法

通过充分利用多个基分类器间的差异,集成分类器能够有效提高泛化精度,但是分类复杂度也随之增加.针对一类典型基于重采样和投票法的集成分类器,根据少数服从多数原则,在不影响分类精度的前提下给出了硬截止投票方法;针对基于Bagging的SVM集成的特点,引入概率分析,分析根据集成中部分投票预测集成结果的损失概率,给出了基于损失概率的软截止投票方法,该方法可推广到其他基于重采样技术与投票法的集成分类系统.对一个人工数据集和两个UCI数据集的实验表明该方法在保证分类精度的前提下,大幅提高了分类速度.     

基于区间的时间序列分类算法的研究

时间序列分类是时间序列数据挖掘的一个分支,针对传统时间序列分类模型存在的失真的问题,文章提出了基于区间权值的集成算法EAIW(Ensemble AlgorithmofInterval Weights)。首先利用区间权值计算方法,为时间序列的不同区间赋予不同的权值,对计算做了并行化处理,以解决子序列特征不明显的问题。进而确定集成分类器的基分类器,以保证集成分类器的性能。然后,在训练集上训练集成分类器,并行化改进集成分类器训练、分类较为耗时的部分。文章将提出的算法在时间序列分类数据库上进行了实验,结果表明提出的算法比基准算法最优正确率数目高25%,并且算法在并行化之后具备可伸缩性。     

基于形态特征的时间序列符号聚合近似方法

由于形态特征能够较为客观地反映时间序列的变化趋势,在时间序列数据降维过程中,形态特征的提取能够保留较为充分的数据信息,为提高后期的时序数据挖掘的效率提供可靠的保障。文中提出基于形态特征的时间序列符号聚合近似方法,综合考虑分段序列的均值和数据分布的形态特征,并且通过论域转化对它们实现符号转化。在相同的压缩比环境下,与传统符号化表示方法相比,该方法能更好地提供原始时间序列数据信息,进而提高时间序列数据挖掘的效率。     

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

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

基于分段线性方法的瓦斯浓度时间序列模式表示

指出直接采用原始瓦斯浓度时间序列进行短期浓度预测、相似性查询、时间序列分类和聚类等数据挖掘工作不但效率低下,而且会影响时间序列数据挖掘的准确性和可靠性;提出了一种采用分段线性方法的时间序列模式表示方法。采用分段线性表示方法对瓦斯浓度时间序列进行模式表示后可换来较小的存储和计算代价,只保留了时间序列的主要形态,去除了细节干扰,更能反映出时间序列的自身特征,有利于提高数据挖掘的效率和准确性。     

基于排列熵的SAX特征表示方法复杂度及相关特性研究

符号化聚合近似SAX方法是典型且行之有效的符号化特征表示方法。目前对SAX方法实践应用较多,然而对其内在特性,如复杂度、信息损失、相关性及周期性等方面的分析研究却相对较为少见。运用排列熵来度量SAX方法的复杂度及相关特性的统计学特征,通过在实验数据集以及真实生理数据上的实验表明,SAX方法可以明显降低特征表示的复杂度,冗余效应也得到了缓解;此外,SAX较好地保留了采用自相关函数ACF度量的内在相关性。本文工作可以对SAX方法及其进一步应用提供支撑,为新的符号化特征表示方法的设计与评估提供分析与统计工具。     

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

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

基于OLPP符号表示的时间序列分类算法

基于符号表示的时间序列分类方法是时间序列数据挖掘的关键技术.大部分现有方法主要针对单个时间序列样本进行符号表示,没有考虑样本间的近邻关系对符号化分类的影响.对此提出一种基于正交局部保持映射(Orthogonal Locality Preserving Projection,OLPP)的时间序列符号表示方法.使用OLPP...     

基于统计特征的时序数据符号化算法

为克服SAX(符号聚合近似)算法对时序信息描述不完整的缺陷,提出基于统计特征的时序数据符号化算法,与SAX不同的是,该算法将时序符号看作矢量,而各时序子段的均值和方差则分别作为描述其平均值及发散程度的分量.由于该算法能够比SAX提供更多的描述信息,因而在时序数据挖掘应用中能够获得比SAX更精确的结果.大量的实验也证实了它的出色表现.     

A non-parametric symbolic approximate representation for long time series

For long time series, it is crucial to design low-dimensional representations that preserve the fundamental characteristics of a series. However, most of the approximate representations require the setting of many input parameters. The main defect of working with parameter-laden algorithms is that incorrect settings may cause an algorithm to fail in achieving the best performance, which is the ability of reducing the dimensionality and retaining the shape information. This is especially likely when the selection of the suitable parameter is not trivial or easy for the user. In this paper, we introduce a new approximate representation of time series, the non-parametric symbolic approximate representation (NSAR), which is based on multi-scale, the approximate coefficients of discrete wavelet transform (DWT) and key points. The novelty of the proposed representation is firstly that it uses a hierarchical mechanism to retain shape information of the original time series. Next, the proposed representation is symbolic in employing key points and encoding in approximate coefficients, so it can greatly reduce the dimension of the original time series and potentially allows the application of text-based retrieval techniques. The proposed representation is fast, automatic, and with no parameter tuning by user. To show the efficacy of the new representation, we performed experiments with real and synthetic data. Experimental results show that NSAR can preserve more fundamental characteristics of a series than symbolic approximate representation (SAX) in the same compression ratio, automatically determine the optimal decomposition level for DWT, and has better performance than SAX in the best matching queries.     

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.

     

Experiencing SAX: a novel symbolic representation of time series

Many high level representations of time series have been proposed for data mining, including Fourier transforms, wavelets, eigenwaves, piecewise polynomial models, etc. Many researchers have also considered symbolic representations of time series, noting that such representations would potentiality allow researchers to avail of the wealth of data structures and algorithms from the text processing and bioinformatics communities. While many symbolic representations of time series have been introduced over the past decades, they all suffer from two fatal flaws. First, the dimensionality of the symbolic representation is the same as the original data, and virtually all data mining algorithms scale poorly with dimensionality. Second, although distance measures can be defined on the symbolic approaches, these distance measures have little correlation with distance measures defined on the original time series. In this work we formulate a new symbolic representation of time series. Our representation is unique in that it allows dimensionality/numerosity reduction, and it also allows distance measures to be defined on the symbolic approach that lower bound corresponding distance measures defined on the original series. As we shall demonstrate, this latter feature is particularly exciting because it allows one to run certain data mining algorithms on the efficiently manipulated symbolic representation, while producing identical results to the algorithms that operate on the original data. In particular, we will demonstrate the utility of our representation on various data mining tasks of clustering, classification, query by content, anomaly detection, motif discovery, and visualization.     

一种基于关键点的SAX改进算法

SAX(symbolic aggregate approximation)是一种符号化的时间序列相似性度量方法,该方法在对时间序列划分时,采用了PAA算法的均值划分,但均分点无法有效描述序列的形态变化,导致序列间对应分段均值相似的情况下,SAX无法有效区分序列之间的相似度.在SAX算法的基础上,提出了基于关键点的SAX改进算法(KP_SAX),该算法的相似性度量公式既可描述时间序列自身数值变化的统计规律,又可描述时间序列形态变化.实验结果表明:KP_SAX虽然部分提高了算法的复杂度,但可在SAX算法无法计算序列相似度的情况下,有效计算各序列间的相似度距离,达到了改进的目的.     

Silhouette-based human action recognition using SAX-Shapes

Human action recognition is an important problem in Computer Vision. Although most of the existing solutions provide good accuracy results, the methods are often overly complex and computationally expensive, hindering practical applications. In this regard, we introduce the combination of time-series representation for the silhouette and Symbolic Aggregate approXimation (SAX), which we refer to as SAX-Shapes, to address the problem of human action recognition. Given an action sequence, the extracted silhouettes of an actor from every frame are transformed into time series. Each of these time series is then efficiently converted into the symbolic vector: SAX. The set of all these SAX vectors (SAX-Shape) represents the action. We propose a rotation invariant distance function to be used by a random forest algorithm to perform the human action recognition. Requiring only silhouettes of actors, the proposed method is validated on two public datasets. It has an accuracy comparable to the related works and it performs well even in varying rotation.