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

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

A Key Point Based SAX Improving Algorithm

SAX(symbolic aggregate approximation)is a kind of symbolic time series similarity measurement method,which can not distinguish the similarity between series effectively in the circumstance that the corresponding values are similar between two sub-segments of time series.In this work,an improved SAX algorithm is proposed based on key points named as KP-SAX.The similarity distance of KP_SAX describes not only the statistical discipline of time series numerical change,but also the trend of time series.The time and space complexity of the algorithm are also analyzed.The experimental results show the superiority of our approaches as compared with the similarity measures of SAX.