K线的字符串表示及距离

1、苏州大学本科生毕业论文目录1 引言12 时间序列22.1 时间序列表示22.2 时间序列的相似性度量33 符号聚合近似43.1 通过PAA降低维度53.2 离散化63.3 距离测量74 用SAX来研究K线105 结论1619K线的字符串表示及距离摘要：时间序列与我们生活密切相关，对时间序列的研究能有效帮我们预测诸如气象，股价之类的信息。符号聚合近似法是一种有效的时间序列降维技术，其对时间序列相似性的度量是时间序列挖掘中的基础工作。本文详细研究该方法，并对其在K线中的相似性度量进行应用。关键词：时间序列 相似性 符号化 K线Abstract: Time series is closely rel

2、ated to our life. The study of time series can effectively help us forecast information such as weather, stock prices and the like. Symbolic Aggregation Approximation is an effective time series dimension reduction technique. Its measure of the similarity of time series is the basic work in time ser

3、ies mining. This article studies the method in detail and applies its similarity measure in the K-line.Key words：Time series Similarity Symbolic K-line.1 引言当我们看到手中的股票暴跌时，在捶胸顿足的同时有没有想过要是自己能提前预测未来的行情该多好。而K线无疑就是我们研究股票最好的工具，如果把每日数据放在一张纸上，就能得到日K线图，同样的方法也可画出周K线图、月K线图。K线图直观、立体感强、携带信息量大，因其细腻独到的标画方式而被引入到股市及期

4、货市场，股市及期货市场中的K线图的画法包含四个数据，即开盘价、最高价、最低价、收盘价，所有的k线都是围绕这四个数据展开，因此K线可以反映大势的状况和价格信息，是历史数据的客观反映，能够表现当前市场的需求，并且往往暗藏未来价格涨幅变动信息，对一支票过去历史数据波动的研究，往往可以对其自身，以及其他股票的未来价格变动作出一些合理预测。在此基础上，我们如果能找到一段之前的某个与现在走势相似的股票，就可以根据这段相似走势K线来对之后的走势进行合理预测，现在的问题是两段K线的相似性该怎么来衡量？基于此想法，我们找一个合适的模型时间序列来研究K线。2 时间序列时间序列是一种常见的与时间有关的数据，是指将某

5、种现象某一个统计指标在不同时间上的各个数值，按时间先后顺序排列而形成的序列。时间序列法是一种定量预测方法，亦称简单外延方法。在统计学中作为一种常用的预测手段被广泛应用。时间序列分析在第二次世界大战前应用于经济预测。二次大战中和战后，在军事科学、空间科学、气象预报和工业自动化等部门的应用更加广泛。时间序列分析(Time series analysis)是一种动态数据处理的统计方法。该方法基于随机过程理论和数理统计学方法，研究随机数据序列所遵从的统计规律，以用于解决实际问题。其中的流式时间序列相对静态时间序列而言，具有无穷、连续、实时和快速等特点，在传感器网络、金融等领域广泛存在，随着慢慢到来的大

6、数据时代，我们有能力采集和存储更多的流式时间序列。那么如何在其中获取有价值的数据呢？时间序列数据挖掘是一种常用方法【5】。和其它数据挖掘方法一样，时间序列的相似性度量是一项基础性工作，同时也是分类、聚类、规律发现、模式识别等工作的子进程。所以我们的想法是要找到一段相似的K线，就是要从一个大型的数据库中找出最相似的序列，然后对两个序列进行比较，最简单的方法当然是直观观察，不过该方法局限性太大，并且无法用具体的数据说明相似度。为此，我们需要先来“量化”时间序列。2.1 时间序列表示与计算机科学中的大多数问题一样，选择一个合适的时间序列的表示对时间序列数据挖掘的简易性和效率有非常大的影响。考虑到这一

7、点，我们已经有了大量的时间序列表示方法，包括傅里叶变换（DFT），离散小波变换（DWT），分段线性（PAA）和分段常数模型（APCA）和奇异值分解（SVD）。图1显示了常用的表示。傅里叶变换 分段线性逼近 哈尔小波变换 分段常数模型 图1：每一个表示可视为尝试用基函数的线性组合近似信号。图片来自文献【4】然而，这些表示虽然有许多优点，但是同样还是有很多局限之处。举个简单的例子，离散小波变换具有有用的多分辨率属性，但是只限于长度为2的整数幂的时间序列。上述所有的表示还有个重要的特征是它们是具有实值的，这就限制了它们的算法、数据结构和可用定义。例如，在异常检测中，我们不能有意义地定义观察任意特定小

8、波集合的概率，因为观察任何实数的概率均为0。这种限制使得研究人员开始考虑使用时间序列的符号表示。于是之后出现了诸如SAX一样的符号化距离表示方法。2.2 时间序列的相似性度量到目前为止，时间序列相似性搜索问题已经提出了十多年左右的时间，但是相似性依然是个很模糊的概念，如果有两条时间序列能几乎重合在一起，也就是每个时间点上的值靠得很近，我们自然会说他们是相似的，为此出现了很多用距离的概念来衡量相似性的方法，确实，相似性和距离两个概念是紧密相关的，并且能互相转化。这段时间内，先后出现了各种面向相似性搜索的时间序列近似表示的方法，现在将时间序列的常见的相似度计算归纳如下：（1） 欧氏距离。也称明可夫

9、斯基距离，欧氏距离是其中的特殊情况，体现的是基于距离的相似度，计算简单、直观、便于理解。大多数情况下，时间序列的长度增加也不会明显增加欧式距离的复杂性，但是欧氏距离局限性也是最大的，当时间序列长度不等，或者存在异常数据点时，欧氏距离对相似性的计算效果不好，而且精度低。（2） 基于最大公共子串的距离【1】。如果两条时间序列大部分都很相似，只有某段时间内发生了突然的波动，该方法是计算两条时间序列间具有的公共长度子串，并用该长度与两个时间序列内较长的序列的长度的比值作为相似性的度量。但由于时间序列可能是一段很长的序列，获取公共子串会有一定难度。而且尽管两个时间序列会很相似，但是数值上细微的偏差可能会

10、使公共子串长度变小，从而影响到度量的结果。（3） DTW算法。动态时间弯曲DTW是一种在语音识别领域得到首次应用的，准确性高的时间序列相似性度量方法。它区别于传统的欧几里的距离，其不同在于动态时间弯曲可以通过弯曲时间序列的时间区域从而对时间序列的数据点进行匹配，这样我们不单单能够得到更好的形态度量的效果，更重要的是我们能够度量两条不等长的时间序列。DTW算法就是寻找两个时间序列间最优弯曲路径的过程，具体过程是对时间序列延展或者压缩，调整时间序列间不同时间点的元素之间的对应关系，使有相同特征的数据点尽量被互相匹配，然后把这些相似点之间的距离相加，从而获得最小的弯曲距离累加和，这些相似点之间的对应

11、关系形成的路径称为弯曲路径，这个最小值成为动态时间弯曲距离。同样的，DTW算法计算也很复杂，而且在匹配时忽略时间上的差异，容易造成时域差异过大的情况。 （4） 基于形态的距离【2】。顾名思义，这是对时间序列的形态进行的度量，是上升、保持或者下降。但是这种方法也只能对时间序列做一个粗糙的分类。若是用几何性质进行度量相似度，比如，用相邻两点间连线和时间轴之间的夹角进行相似度计算，就能更好地反映相似度，但是同样的，这个方法对时间序列的信息挖掘不够完整。现在最为有效的方法，还是基于符号聚合近似的方法SAX（Symbolic Aggregate Approximation），该方法是把时间序列转换为分段

12、聚合近似，再转化成字符串，再计算字符串间距离，能较好得还原时间序列的形态特征，但是相对的计算会很复杂。下文中将对该方法做详细展开。3 符号聚合近似符号聚合近似SAX是一种有效的对时间序列数据降维离散的方法，因其简单实用而被广泛运用。主要做法是将任意长度为n的时间序列C简化为任意长度为w的字符串（w n，通常为w 2.下表总结了本节和后续章节中使用的主要符号。C时间序列C = c1，.，cnC时间序列的分段聚集逼近C = c1，.，cwC时间序列C = c1，.，cw的符号表示w表示时间序列C的PAA段的数量a字母大小（例如，对于字母表= a，b，c，a = 3）为了便于后续计算，我们首先要将采

13、集到股票数据进行预先处理，我们将参考股票具有研究意义的30天的价格变动以向量方式记录，记为X=（x1,x2,xn），同样的我们将测量股票要测量的30天价格变动也用向量方式记录，记为Y=（y1,y2,yn），其中n为选取的K线图某时刻的时序标号，n=1为起点时刻，在这里我们选取的是30天，所以n=30为终点时刻。xm为第m时刻的K线图的收盘价格。由于股票价格差别巨大，所以要进行规范处理，把所有股票的价格变动都转化为-11之间。具体方法如下：SAX的具体做法可总结为：规范化:先把时间序列规范化为平均值为0，标准差为1的时间序列C转化为PAA（Piecewise Aggregate Approxim

14、ation）：把C转化成分段聚合近似PAA，得C 离散化：参照表格将分段聚集逼近转化成字符串表示这样的离散化过程是独一无二的，因为它使用了原始时间序列和符号字符串之间的中间表示。因为我们先将数据转换为分段聚合近似（PAA）表示，然后将PAA表示符号化为离散的字符串了。这样做有两个重要的优点：(1) 维度降低：我们可以使用明确定义的和记录的降维工具PAA ，从n维降低到了w维，并且缩减之后会自动转到符号表示。(2)下限：证明两个符号字符串之间的距离测量值下界与原始时间序列之间的真实距离其实并不重要。我们证明下界的关键观察是集中证明符号距离度量下限PAA距离度量。然后，我们可以通过简单地指出PAA

15、表示本身的现有证明，通过传递性证明期望的结果。在考虑符号扩展之前，我们先来简要回顾一下PAA技术。3.1 通过PAA降低维度长度为n的时间序列C可以用向量C= C1, CW 在一个w维的空间里表示。C的第i个元素是由以下等式计算：（1）简单地说，为了将时间序列从n维减小到w维，将数据分成w个相等大小的“帧”。计算帧内数据的平均值并且这些值的向量变成数据减少的表示。该表示可以被视为尝试用图2所示的盒基函数的线性组合近似原始时间序列。图片来自文献【4】图2：可以将PAA表示形象化为试图用盒基函数的线性组合对时间序列进行建模。在这种情况下，长度128的序列减少到8个维度PAA降维虽然直观且简单，但已

16、被证明可以与更复杂的降维技术如傅立叶变换和离散小波变换相媲美。在将每个时间序列转换为PAA之前，我们需要规范化每个时间序列的均值为零和标准偏差为1表示，因为很明显，将时间序列与不同的偏移和幅度进行比较是没有意义的。3.2 离散化将时间序列数据库转换为PAA后，我们可以应用进一步的转换来获得离散表示。我们希望有一种能产生具有等概率的符号的离散化技术。这非常容易实现，因为规范化的时间序列具有高斯分布。为了说明这一点，我们从8个不同的时间序列中提取了长度为128的子序列，并绘制了数据的正态概率图，如图3所示。图片来自文献【4】图3：来自8个不同数据集的来自长度为128的子序列的值的累积分布的正态概率

17、图。该图的高度线性特性强烈表明数据来自高斯分布鉴于规范化的时间序列具有高度的高斯分布，我们现在可以简单地定义在高斯曲线下产生相同大小区域的“断点”。定义1:断点：断点是一个有序数列表B =1,a-1，使得从i到 i+1的N(0,1) 高斯曲线下面积=1/a （通常0和a定义为-和）这些断点可以通过在统计表中查找来确定。例如，下表给出了断点一个从a等于3到10的值。表格来自文献【4】表3：查找表，其包含将任意数量（从3到10）的等概率区域中的高斯分布划分的断点一旦获得断点，我们就可以按照以下方式得到时间序列的离散表示。我们首先获得时间序列的PAA。 将低于最小断点的所有PAA系数映射到符号“a”

18、，将大于或等于最小断点且小于第二小断点的所有系数映射到符号“b”等。图4显示了这个概念。图片来自文献【4】图4：通过首先获得PAA近似值，然后使用预定断点将PAA系数映射到SAX符号来离散化时间序列。 在上面的例子中，当n = 128，w = 8和a = 3时，时间序列被映射到单词baabccbc值得注意的是，在本例中，3个符号“a”，“b”和“c”大致等于我们所需的等概率。我们称代表一个子序列的符号的连接为单词。定义2：单词：长度为n的子序列C可以表示为一个单词 = 1 , w ，让alphai代表字母表的第i个元素，也就是alpha1 = a，alpha2=b,然后从PAA 近 似至如下获

19、得到单词的映射：i=alphaj , iif j-1Cij (2) 我们现在定义了SAX，这是我们的符号表示（PAA表示仅仅是获得符号表示所需的中间步骤）。3.3 距离测量在介绍了时间序列的新表示之后，我们现在可以定义一个距离度量。 到目前为止，最常见的时间序列距离测量是欧几里得距离。给定具有相同长度n的两个时间序列Q和C，方程 3定义了它们的欧几里德距离，图5.A说明了该度量的直观表示。 (3)如果我们将原始子序列转换成PAA表示成Q和C，则使用方程 1，那么我们可以通过下式获得原始子序列之间的欧几里得距离的下界逼近： (4)这一测量如图5B所示。 DR（Q,C）下界低于真实的欧几里德距离。

20、如果我们进一步将数据转换为符号表示，我们可以定义一个MINDIST函数，该函数返回两个单词的原始时间序列之间的最小距离： (5)该函数类似于公式4， 除了两个PAA系数之间的距离已经被替代为子函数dist（）之外。 dist（）函数可以使用表查找来实现，如下表所示。表：MINDIST函数使用的查找表。 该表是基数为4的字母表，即a = 4。 两个符号之间的距离可以通过检查相应的行和列来读取。 例如，dist（a，b）= 0，dist（a，c）= 0.67。任何查找表的单元格（r，c）中的值可以通过以下表达式计算。对于给定的字母大小a的值，该表只需计算一次，然后存储以便快速查找。 MINDIST

21、功能可以在图5.C中看到。图片来自文献【4】图5：在这项工作中讨论的三种表征的直观表示，以及在它们上定义的距离度量。 A）两个时间序列之间的欧几里得距离可以被看作是每对对应点的平方差之和的平方根。B）为PAA近似定义的距离量度可以被看作每对相应PAA系数之间的平方差的总和的平方根乘以压缩率的平方根。 C）时间序列的两个SAX表示之间的距离需要查找每对符号之间的距离，对它们进行平方，将它们相加，取平方根，最后乘以压缩率的平方根如果我们要使用时间序列的符号表示，那么我们必须解决一个问题。 如果我们希望近似于主内存中的海量数据集，那么必须选择参数w和a，使得近似可以充分利用主存储器。 在控制近似元素

22、的数量的参数w和控制每个近似元素的粒度的值之间存在明显的折衷。由于数据高度依赖，因此无法通过分析确定最佳权衡。然而，我们可以通过一个简单的实验来凭经验确定最佳值。既然我们希望达到最小的下限，我们可以简单地估计所有可能的参数的下限，并选择最佳的设置。文献【4】中，作者通过从UCR【4】时间序列数据挖掘档案中取得的50个时间序列数据库的串联进行了这样的测试。 对于每个参数组合，我们对长度为256的子序列进行100,000次实验的平均结果。图6展示了该结果。图6：a = 3 . 11和w = 2 . 8的叉积下经验估计的下界紧性。 较暗的柱状图显示了需要大致相等的空间来存储每个可能的字的参数组合（大

23、约4兆字节）结果表明，使用一个较小的值a可以到达下界，但是对于大的值会有收益递减。结果还表明，参数不是太重要; 在5到8范围内的字母大小都是不错的选择。4 用SAX来研究K线以上研究，让我们对时间序列有了一定的了解，现回归本文一开始的问题，我们用符号聚合方法来对K线进行研究。现选取万兴科技2018/02/22至2018/04/20时间段的K线走势以及朗姿股份2015/03/26至2015/06/16的K线走势，如下图所示：从图中直观上可以看出，这两段区间走势非常相似。现在用上述的分段聚合近似方法来进行验证。我们从网上获得两只股票的真实数据如下：万兴科技朗姿股份此例中，我们选取两只K线收盘价数据

24、来研究，并先将其正规化，为方便起见，我们记万兴科技为股票A,朗姿股份为股票B，股票A拟合图像如下。股票A走势（1） 运用公式1对股票 A进行PAA降维，取w=6得到下图：（2） 我们接下来进行离散化，由于有了上面的讨论，我们不妨选取a=6，于是就有了1至5五个断点，所以离散化的图如下所示：于是得到了股票A的离散化表示的单词为bbcdee.同理我们对股票B进行分析，股票B的图像拟合如下：股票B走势（1） 运用公式1对股票B进行PAA降维，w=6得到下图：（2） 接下来对其进行离散化，同理选取a=6，离散化的图如下所示：于是我们同样得到了股票B的离散化表示的单词为bbcded.由公式（5）可计算得MINDIST（A,B）=0，从结果可以看出，两条曲线几乎是重合的。确实是如此，所以我们需要再取更高的精度，取w=30，a=9，于是就有了1至8八个断点，同样的方法得