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

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

不同粒度时间序列相似性度量

现有的时间序列的相似性度量大多基于欧氏距离,并不适用于不同粒度时间序列的相似性匹配,无法直接对其相似性进行有效的度量,为此,提出一种基于对应差值比样本的相似性度量,用于不同粒度时间序列的相似性匹配.首先对不同时间粒度的时序数据进行阐述,并定义了对应差值比样本与相似度计算方法;接着提出基于它们的相似性匹配算法;最后实验证...     

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

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

基于涨落模式的时间序列相似性度量研究

时间序列形态相似性挖掘是目前时间序列数据挖掘研究的热点,然而由于时间序列数据背后真实系统的复杂性,加上观测条件的影响,时间序列会呈现多种相似性变形,如振幅伸缩、振幅漂移、线性漂移等。相似性变形并不会改变序列的形态特征,但现有的ED、DTW和L_p距离等相似性度量算法均不能有效支持识别各类相似性变形。本文首次提出涨落模式(FP)的概念,以涨落模式保存原序列的趋势变化信息,利用最长公共子序列算法计算涨落模式的相似度,消除振幅伸缩、振幅漂移和线性漂移等对相似性挖掘带来的影响,实现基于涨落模式的时间序列相似性度量。设置仿真数据集检验FP相似性度量的相似性变形支持性,同时在真实数据集上进行分类,依据分类准确性对算法鲁棒性进行评估,验证了本文提出的基于涨落模式的相似性度量算法在各类相似性形变上的有效支持性。     

基于云模型重叠度的相似性度量

云模型相似性是用来度量同类概念不同语言值的多个云之间关联程度的方法,相似云及其度量分析方法的提出是对云模型理论的扩展。针对目前相似性度量方法中时间复杂度过高和结果不稳定等不足,提出了一种基于云模型重叠度的相似性度量算法。首先,根据云模型期望、熵、超熵三个数字特征,定义两个云模型的位置关系和逻辑关系;其次,利用两个云的位置和形状特性,计算得到它们间的重叠度;最后,结合云模型重叠度与相似度的关系,将云模型的相似性度量转化为相应重叠部分的定量化描述。通过对时间序列分类实例的应用,验证了该算法在保证结果稳定度和正确率的前提下,与目前时间消耗较低的云模型相似度计算方法(LICM)相比,计算复杂度降低了50%,表明该算法具有可行性和有效性。     

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

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

基于数学形态学的时间序列相似性度量研究

时间序列相似性度量在挖掘时间序列模式,提取时间序列关联关系上发挥着重要作用。分析了当前主流的时间序列相似性度量算法,分别指出了各度量算法在度量时序数据相似性时存在的缺陷,并提出了基于数学形态学的时间序列相似性度量算法。通过将归一化的时间序列二值图像化表示,再引入了图像处理领域中的膨胀、腐蚀操作对时序数据进行形态变换分析,提高相似时序数据部分的抗噪性,同时又不降低时序数据非相似部分间的差异度,实现时序数据相似性度量分类精度的提高。在八种时间序列测试数据集合上进行分类实验,实验结果表明提出的基于数学形态学的时间序列相似性度量算法在时间序列分类精度上得到有效改善,相比于DTW相似性度量算法,分类精度平均水平提升了8.74%,最高提升20%。     

基于分层动态时间弯曲的序列相似性度量方法研究

为了更好地体现时间序列的形态特征,并探索更适合于较长时间序列之间相似性度量的方法,在动态时间弯曲算法的基础上进行改进,提出了基于分层动态时间弯曲的序列相似性度量方法。对时间序列进行多层次分段,并从分段中均匀抽取相对应的层次分段子序列,然后将层次分段子序列抽象为三维空间的点（反映了分段子序列的均值、长度和趋势）进行相似性度量,最后综合各个层次的相似性度量作为结果。实验表明,在参数设置合理的情况下,此方法能获得较高的序列相似性度量准确度和效率。     

多元时间序列相似性度量方法

现有的多元时间序列相似性度量方法 难以平衡度量准确性和计算效率之间的矛盾.针对该问题,首先,对多元时间序列进行多维分段拟合;然后,选取各分段上序列点的均值作为特征;最后,以特征序列作为输入,利用动态时间弯曲算法实现相似性度量.实验结果表明,所提出方法参数配置简单,能够在保证度量准确性的前提下有效降低计算复杂度.     

一种RDF图的语义相似性度量方法

在资源描述框架(RDF)图的语义相似性度量过程中,结构相似性和语义相似性计算不精确。针对该问题,提出结构语义(SAS)方法。结合改进的基于网络距离模型的语义距离公式、基于信息量模型的权重度量机制,计算概念节点的语义相似度,完善RDF图语义相似度算法,分析结构、深度和密度对RDF图语义相似性度量的影响。设计并实现原型系统,实验结果表明,该方法可有效保证RDF图的语义相似度与实际相符。     

基于SAX方法的时间序列分类问题的多阶段改进研究

分类问题是数据挖掘中的基本问题之一,时间序列的特征表示及相似性度量是时间序列数据挖掘中分类、聚类及模式发现等任务的基础。SAX方法是一种典型的时间序列符号化表示方法,在采用该方法的基础上对时间序列进行分类,不仅可以有效地降维、降噪,而且具有简单、直观等特点,但是该方法有可能造成信息损失并影响到分类结果的准确性。为了弥补信息损失对分类结果的影响,采用了集成学习中大多数投票方法来弥补BOP表示后的信息损失,从而提高整个分类器的效率。针对一些样本在BOP表示中都损失了相似的重要信息,以至于大多数投票无法进一步提高分类效率的问题,进一步提出了结合集成学习中AdaBoost算法,通过对训练样本权重的调整,从而达到以提高分类器性能来弥补信息损失的效果。实验结果表明,将BOP方法与集成学习相结合的方法框架,不仅能很好地处理SAX符号化表示中的信息损失问题,而且与已有方法相比,在分类准确度方面也有显著的提高。     

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

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

Improving the classification accuracy of streaming data using SAX similarity features

The classification accuracy of time series is highly dependent on the quality of used features. In this study, features of new type, called SAX (Symbolic Aggregate approXimation) similarity features, are presented. SAX similarity features are a combination of the traditional statistical number-based and the template-based classification. SAX similarity features are obtained from the data of the time window by first transforming the time series into a discrete presentation using SAX. Then the similarity between this SAX presentation and predefined SAX templates are calculated, and these similarity values are considered as SAX similarity features. The functioning of these features was tested using five different activity data sets collected using wearable inertial sensors and five different classifiers. The results show that the recognition rates calculated using SAX similarity features together with traditional features are much better than those obtained employing traditional features only. In 20 tested cases out of 23, the improvement is statistically significant according to the paired t-test.     

基于SAX方法的股票时间序列数据相似性度量方法研究

特定数据集上高效的相似性度量方法是目前时间序列数据挖掘领域研究的重点内容之一。针对经过SAX方法降维后的股票数据在相似性度量中缺乏趋势变化的动态信息这一问题,本文提出了一种融合了点距离与模式距离优点的新型相似性度量函数——复合距离函数,并通过实证分析验证了该距离函数在相似性度量中的有效性,为揭示股票数据间相互依赖的规律以及时间序列相似性问题的进一步研究提供了新思路。     

符号化近似SAX在时序数据挖掘中的应用研究

聚类是数据挖掘研究中最常见的一种方法,可以作为规则发现、异常发现等其它数据挖掘操作的基础,一直以来都是数据挖掘的研究热点之一。股票数据是一种典型的时间序列数据,利用股票数据进行时间序列数据挖掘的研究既有一定的实际应用价值,也是国内外的热点问题之一。文章首次将一种新型符号化方法SAX[1]应用到标准普尔500指数的股票数据的聚类研究中,使用传统的欧氏距离和动态时间弯曲两种时间序列相似性度量方法进行实验。实验结果表明将SAX应用到股票数据聚类操作,可以得到更好的趋势聚类效果和更高的效率。     

改进的SAX符号化算法在QAR数据中的应用

鉴于快速存取记录器（QAR）数据是结构非常复杂和数据量大的时间序列数据,直接采用传统的符号聚合近似算法（SAX）对QAR数据进行描述、存储、检索等操作时,不能克服时间序列幅度值伸缩和时间轴漂移等方面的不足。提出了改进的符号聚合近似算法,将快速存取记录器数据划分为起飞、巡航和降落三个阶段,并利用此改进的算法对巡航阶段进行填补,对不同长度的故障模型序列进行有效的相似性搜索。通过实验以及其在飞机故障诊断项目中的应用,证明了其可行性和有效性,从而提高了飞机的排故效率。     

基于分割模式的时间序列矢量符号化算法

针对符号化聚合近似算法(SAX)中时间序列必须等长分割的缺陷,提出一种基于分割模式的时间序列符号化算法(SMSAX)。利用三角阈值法对随机抽样的时间序列进行特征提取,计算时间序列最大压缩比,将其作为时间窗宽提取分割点,进而求出时间序列的分割模式。利用得到的分割模式对时间序列进行分割降维,通过均值和波动率对分割后的子序列进行向量符号化。根据时间序列特征对其进行不等长分割,并加入波动率消除奇异点的影响。实验结果表明,SMSAX能获得比SAX更精确的结果。     

Parallel similarity joins on massive high‐dimensional data using MapReduce

In this paper, we focus on high‐dimensional similarity join (HDSJ) using MapReduce paradigm. As the volume of the data and the number of the dimensions increase, the computation cost of HDSJ will increase exponentially. There is no existing effective approach that can process HDSJ efficiently, so we propose a novel method called symbolic aggregate approximation (SAX)‐based HDSJ to deal with the problem. SAX is the abbreviation of symbolic aggregate approximation that is a dimensionality reduction technique and widely used in time series processing, we use SAX to represent the high‐dimensional vectors in this paper and reorganize these vectors into groups based on their SAX representations. For the very high‐dimensional vectors, we also propose an improved SAX‐based HDSJ approach. Finally, we implement SAX‐based HDSJ and improved SAX‐based HDSJ on Hadoop‐0.20.2 and perform comprehensive experiments to test the performance, we also compare SAX‐based HDSJ and improved SAX‐based HDSJ with the existing method. The experiment results show that our proposed approaches have much better performance than that of the existing method. Copyright © 2015 John Wiley & Sons, Ltd.