时间序列相似度量的研究.docx

时间序列相似性度量的研究读书笔记一、文章主要内容时间序列的相似性度量是时间序列数据挖掘研究中的一个重要问题，是进行序列查询、分类、预测的一项基础工作。寻求一种好的度量对提高挖掘任务的效率和准确性有着至关重要的意义。目前从事这方面的研究除了少许理论论述外，几乎都采用一种固定的方法，即提出具体要求并提供实验数据。然而，大多数实验方法不是使用范围有限就是侧重点不同。为了提供一个比较全面的实验验证，用INN分类算法进行了大量的时间序列交叉验证实验。重新评估了其中的弹性度量，并使用不同应用领域的28个时间序列数据集进行比较，结果表明，该方法具有更高的准确性。二、文章重点内容1、时间序列的相似性度量时间序列的相似性度量是时间序列数据挖掘研究中的一个重要问题，能反映数据中基本的相似性，这一点为时间序列的相似性检索、分类、预测等尤其可取。因此合理的相似性度量能够提高数据挖掘的有效性和准确性。目前时间序列相似性度量，最常用的有欧氏距离(ED)和动态时间弯曲(DTW)。其它许多度量及它们的扩展已被广泛引用到文献和用于便利查询处理和时间序列数据挖掘。本文根据降维和压缩的方法定义距离度量。保证约简后的距离小于或等于原数据的真实距离。即满足无漏报原则，就是要求数据表示满足条件：DF(q，s)D(q，s)，其中：q是查询序列；s是数据集中的任意序列；是约简空间中的两序列距离；D是真实的两序列距离。2、DTWDTW允许时间序列的延伸或压缩，查找结果要优于ED。而且可采用下界函数加速查找速度。带有动态窗口的时间弯曲s，不仅能提高计算效率而且能提高相似性测量精度。另一组时间序列的相似性度量是在编辑距离概念的基础上形成的。它的思想是两个序列越相似，则将其中的一个序列通过插入、删除等操作变换成另一个序列所要做的功就越少。它们为时间序列的匹配定义了一系列操作及一个衡量这些操作所需的代价函数，事件序列间的相似距离就可以定义为将一个序列变换为另一个序列所需要操作的代价之和。然后，通过动态变换来计算编辑距离。最好的是LCSS，它利用最长公共子序列模型，适应设置的时间序列匹配字符的概念。阈值参数8已知，如果它们的距离少于。说明两个时间序列的两个点是匹配的。EDR是基于编辑距离的另一个相似性度量和LCSS相比，EDR也用了一个阈值参数8，参数的作用是量化一对点0或1之间的距离。EDR根据空白的长度增强数据率分配两个匹配部分间的差距。ERP距离包括了DTW 和EDR的优点。通过连续变化的参考点计算两个时间序列差距的距离。实质上，如果两个点之间的距离太大，ERP简单使用这些点中的一个和参考点计算之间的距离值。最近，计算编辑距离的一种新方法在文献9 4、数据世系分类按照数据世系包含的数据源类型不同，数据的世系可分为在不同数据源间的数据演化过程和相同数据源内部数据的演化过程，即模式级和实例级数据演化过程。（1）模式级数据世系：异构数据源间的数据共享问题一直是数据集成的核心问题之一。不同模式的数据源间进行的数据演化过程是数据集成的关键部分，由于不知道数据的具体形式从而无法标注数据项的世系，只能利用模式级数据问的对应关系追踪数据在不同模式间的演化过程。（2）实例级数据世系：用户通过查询所有可能的映射关系，找到模式级数据的世系，想要获取更细粒度的世系，还需要在某数据源内部考察数据的演化过程，即实例级数据的世系。和模式级数据的世系不同，实例级的数据项可以被显式地表达出来，通过对数据进行标注得到更细粒度的数据世系。5、数据世系的应用在科学数据管理、商业应用等领域，特别是在分布式环境下，数据世系的管理获得了一些成果，R. Bose将数据处理过程分为以下几种方式：基于脚本或程序运行的、基于查询的、基于工作流管理系统的和基于服务的方式。下表是典型的世系研究项目：系统或项目名 称数据处理架 构描 述科研机构OrchestraP2P异构数据共享环境中支持how世系追踪宾夕法尼亚大学SPIDER数据集成理解、提取和调试模式映射的工具加州大学圣克鲁兹分校WHIPS数据仓库数据仓库环境下世系追踪系统斯坦福大学DBNotes关系数据库关系数据库基础上的注释管理系统加州大学圣克鲁兹分校Mondrian关系数据库扩展DBNotes的注释管理系统爱丁堡大学Perm关系数据库运用查询重写技术追踪数据世系瑞士苏黎世大学ChimeraSOA表示和查询数据世系的虚拟数据网格原型系统美国阿贡国家实验室ESSW基于脚本运用于实验中自动记录数据和工作流世系的管理系统加州大学圣塔芭芭拉分校Tioga关系数据库细粒度的数据世系管理系统加州大学伯克利分校CMCSSOA以信息技术为基础、合成多尺度信息的化学科学知识库桑迪亚国家实验室、西北太平洋国家实验室等MyGridWFMS应用于生物领域的工作流管理系统曼彻斯特大学 PASOAWFMS工作流环境下跟踪数据和服务的质量和准确性南安普敦大学和卡蒂夫大学Trio关系数据库不确定数据库上的数据世系管理系统斯坦福大学The EU Provenance ProjectSOA基于SOA的世系查询系统欧盟资助的项目KarmaSOA/WFMS基于SOA封装的工作流世系查询系统印地安那大学VisTrailsWFMS新的工作流和世系管理系统支持数据探索和可视化犹他大学Wings/PegasusWFMS支持计算密集的分布式工作流的创建和执行南加州大学表 1：典型的世系研究项目6、数据世系的研究方向（1）数据空间中数据世系的管理（2）不确定数据的世系管理 （3）工作流世系的管理（4）数据世系的挖掘和可视化三、总结数据世系是数据管理的重要内容，自上世纪90年代以来得到了充分的关注。本文重点考察数据的演化过程，分别从模式级和实例级数据演化过程考虑数据世系的表示和查询技术的研究进展。模式级数据世系描述了不同数据源间数据的演化过程，重点总结了基于关系型数据的查询重写技术和广泛应用于数据集成和数据交换等领域的模式映射技术；实例级数据世系描述了同一数据源或同一模式实例内部数据的演化过程，重点介绍了关系型数据、XML数据、流数据世系的表示和查询等技术的研究现状；针对不确定性数据，总结了追踪数据以及不