ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 基于形态相似距离的时间序列相似性度量 门连生 ，卫婧菲 ，李 中 ＭＥＮ Ｌｉａｎｓｈｅｎｇ ，ＷＥＩ Ｊｉｎｇｆｅｉ ，ＬＩ Ｚｈｏｎｇ １．晋城供电公司，山西晋城０４８０００ ２．华北电力大学电气与电子工程学院，河北保定０７１００３ １．Ｊｉｎｅｈｅｎｇ Ｐｏｗｅｒ Ｓｕｐｐｌｙ Ｃｏｍｐａｎｙ，Ｊｉｎｃｈｅｎｇ，Ｓｈａｎｘｉ ０４８０００，Ｃｈｉｎａ ２．Ｓｃｈｏｏｌ ｏｆＥｌｅｃｔｒｉｃａｌ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈ Ｃｈｉｎａ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ Ｕｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ，Ｈｅｂｅｉ ０７１００３，Ｃｈｉｎａ ＭＥＮ Ｌｉａｎｓｈｅｎｇ，ＷＥＩ Ｊｉｎｇｆｅｉ，ＬＩ Ｚｈｏｎｇ．Ｍｏｒｐｈｏｌｏｇｙ ｓｉｍｉｌａｒｉｔｙ ｄｉｓｔａｎｃｅ ｂａｓｅｄ ｔｉｍｅ ｓｅｒｉｅｓ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ— ｍｅｎｔ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１５，５１（４）：１２０—１２２． Ａｂｓｔｒａｃｔ：Ｔｉｍｅ ｓｅｒｉｅｓ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｆｕｎｄａｍｅｎｔａｌ ｔａｓｋｓ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ａｎａｌｙｚｉｎｇ，ａｎｄ ｔｈｅ ｋｅｙ ｔｏ ｓｉｍｉｌａｒｉｔｙ ｍａｔｃｈｉｎｇ．Ｉｎ ｖｉｅｗ ｏｆ ｓｈｏｒｔｃｏｍｉｎｇｓ ｏｆ Ｅｕｃｌｉｄｅａｎ ｄｉｓｔａｎｃｅ ｃａｎ ｎｏｔ ｃｏｍｐａｒｅ ｓｅｇｍｅｎｔ ｔｒｅｎｄ ｓｉｍｉｌａｒｉｔｙ ａｎｄ ｐａｔｔｅｒｎ ｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅ ｏｒ ｉｔｓ ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ ｅｘｉｓｔｉｎｇ ｄｉｓｃｒｅｔｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ，ｔｈｅ ｍｏｒｐｈｏｌｏｇｙ ｓｉｍｉｌａｒｉｔｙ ｄｉｓｔａｎｃｅ ｂａｓｅｄ ｔｉｍｅ ｓｅｒｉｅｓ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ ｒｅｏｒｇａｎｉｚａｔｉｏｎ ａｎｄ ｃｌｕｓｔｅｒｉｎｇ ｏｎ ｓｔａｎｄａｒｄ ｄａｔａ ｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｉｓ ｆｅａｓｉｂｌｅ ａｎｄ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ：ｔｉｍｅ ｓｅｒｉｅｓ；ｍｏｒｐｈｏｌｏｇｙ ｓｉｍｉｌａｒｉｔｙ ｄｉｓｔａｎｃｅ；ｓｉｍｉｌａｒｉｔｙ；ｃｌｕｓｔｅｒｉｎｇ 摘要：时间序列的相似性度量是时间序列分析的基础工作之一，是进行相似匹配的关键。针对欧几里德距离描述 分段趋势的不足和各种模式距离对应分段之间距离值的离散化问题，提出一种基于形态相似距离的时间序列相似 性度量方法，标准数据集上完成的识别和聚类实验表明了该方法的可行性和有效性。 关键词：时间序列；形态相似距离；相似性；聚类 文献标志码：Ａ 中图分类号：ＴＰ３１１ ｄｏｉ：１０．３７７８￣．ｉｓｓｎ．１００２．８３３１．１３１２—０１０７ １ 引言 时问序列是一种重要的数据对象，是某个物理量按 针对欧几里德距离描述分段趋势上的不足，我国学者提 出根据上升，保持和下降三种趋势的模式划分，计算其 模式距离来度量两个等长序列的趋势差异程度 ，文献 ［８］对其改进后提出了基于七元模式的形态距离，一定 程度上提高了度量的精度。这类模式距离保留了时间 序列的分段趋势信息，但分段模式的有限划分使任意两 照时间顺序观察得到的一串值，这些值可以是具体的实 数值，也可以是观察事件发生的数目或者特定模式的数 值。时间序列数据广泛存在于商业、金融、医药、天文气 象、航空航天等多个不同应用领域ｕ 。 时间序列数据一般规模巨大，具有时间连续性的特 点，甚至持续增长，这给时间序列的处理、分析和挖掘工 作带来了诸多困难。时间序列的相似搜索是时间序列 数据挖掘的一个研究热点 。 ，其中序列的近似表示和相 似性度量决定了相似匹配的效果，是解决相似性搜索的 关键 。 个序列对应分段间的距离值是离散的，相似匹配的精确 程度依赖于模式划分粒度。此外，文献【９］采用相邻线 段问的夹角构成角度序列，来近似表示时间序列，并用 夹角距离进行相似度度量，该方法具有平移和旋转不变 性的优点，但未能保留分段趋势信息，有些情况下并不 适用。文献【ｌ０］提出了时间序列的分段线性弧度表示 时间序列相似性的研究，很多研究采用了欧几里德 方法，定义了弧度距离及基于弧度距离的相似度量，文 距离或者变形，但基于点距离的欧几里德距离及其变形 对于对序列在时间轴上的偏移非常敏感，不具备形态识 别能力，不能识别时间序列在不同分辨率下的模式变化 。 中仿真结果表明该方法准确性较高并具有多分辨率条 件下的稳定性，但处理方法相对复杂。 动态时间弯曲（Ｄｙｎａｍｉｃ Ｔｉｍｅ Ｗａｒｐｉｎｇ，ＤＴＷ）距 作者简介：门连生（１９７３一），男，工程师，研究领域为电力信息分析、输配电工程；卫婧菲，女，电力系统及自动化专业本科生；李中 男，博士，副教授，研究领域为智能信息处理、电气设备故障诊断。Ｅ．ｍａｉｌ：ｊｃｍｅｎｌｓ＠１６３．ｃｏｒｎ 收稿日期：２０１３—１２—０８ 修凹口期：２０１４－０１一Ｏ９ 文章编号：１００２—８３３１（２０１５）０４．０１２０．０３ 门连生，卫婧菲，李 中：基于形态相似距离的时间序列相似性度量 ４０ ５０ ５０ ３５ ４０ ｊ四４Ｏ ，ｏ ｓｏ ２５ ３０ ２Ｏ ２Ｏ １Ｏ ２０ ０ ２０ ４０ ６０ ０ ２０ ４Ｏ ６０ ０ ２０ ４Ｏ ６Ｏ 时间点 时间点 时问点 （ａ）第１类样本 （ｂ）第２类样本 （ｅ）第３类样本 ５Ｏ ｊ四４０ 趔 ３０ ２０ ０ ２０ ４Ｏ ６Ｏ 时间点 时间点 时间点 （ｄ）第４类样本 （ｆ）第５类样本 （ｅ）第６类样本 图１各类测试数据样本 离在语音处理领域得到广泛的研究与应用。Ｂｅｒｎｄｔ和 分析可知，任意２个向量Ｘ 与ｘ 之间的形态相似 Ｃｌｉｆｏｒｄ最早将ＤＴＷ的概念应用到小型时间序列分析 距离满足以下约束： 领域，并在实验中取得了较好的结果ｎ”。动态时间弯曲 ＭｓＤ（ ，， ）∈［三２（ｘｊ，Ｘｋ），２Ｌ２（ｘｊ，Ｘｋ）］ （３） 距离可以有效地消除欧几里德距离的缺陷，它允许序列 并且，若Ｖ（ 一 ）， １，２，…， ，取值符号相同，则 在时间轴上的偏移，支持不同长度序列的相似度度量， 但计算复杂度高，很大程度上了其使用范围。 ｄＭＳＤ（ ，， ）＝ ２（ ，，ｘ ）；否贝０，Ｌ２（ｘｊ，Ｘｋ）＜ ＭＳＤ（ ，，Ｘｋ）≤ 针对现有方法的不足，本文提出在对时间序列分段 ２Ｌ：（ ， ）当且仅当满足∑（ 一Ｘｋｉ）＝０时，则有： 的基础上，采用形状相似距离进行时间序列的相似度计 ｉ＝】 算。分析介绍了形态相似距离（Ｍｏｒｐｈｏｌｏｇｙ Ｓｉｍｉｌａｒｉｔｙ ｄＭＳＤ（ｘｊ，Ｘｋ）＝２Ｌ２（ｘ，， ）。 Ｄｉｓｔａｎｃｅ，ＭＳＤ）及其性质，以ＵＣＩ标准时问序列数据为 测试对象，分别以欧几里德距离和形态相似距离作为相 ３测试数据 似度计算方法，完成了基于质心的识别和层次聚类仿真 为保避荚 方真的公正｝生，选择ｕｃＩ的ＫＤＤ ＡＲＣＨＩＶＥ 实验，并对实验结果进行了对比。 中的一个实例时间序列数据Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ Ｃｈａｒｔ Ｔｉｍｅ Ｓｅｒｉｅｓ作为测试研究对象。这些数据来源于工业 ２形状相似距离 生产控制图，由６００个时间序列样本组成，每个样本６０ 经典的欧几里德距离根据两个向量之间的差值的 个点，共６类，各类均含１００个样本 。表１说明了该数 绝对值计算得出，忽略了差值的符号和分布特征。文献 据集的基本构成和属性，图１中的（ａ）至（ｆ）依次显示了６ ［１２．１３］考虑向量差值分布的具体情况，提出了一种形态 类测试数据中的第１条时间序列样本。 相似距离用于相似度评估，该方法是对欧几里德距离进 表１ Ｓｙｎｔｈｅｔｉｃ Ｃｏｎ￣ｏｌ Ｃｈａｒｔ Ｔｉｍｅ Ｓｅｒｉｅｓ数据属性 行的修正，国际标准数据集上的对比仿真实验分析表明 对于包含对象形状特征数据的相似度计算，形态相似距 离比欧几里德距离具有更高的精确度。 形态相似距离的定义是：对于Ｐ个ｎ维向量ｘ ＝ （ ｆ１， ｆ２，…， ） ， ＝１，２，…，Ｐ，则 ，与 之间的形态 相似距离ｄＭＳＤ（ｘｊ， ）是： ｄＭＳＤ（ ，，ｘｋ）＝Ｌ２（ ，， ）×［２一ＡＳＤ（ｘｊ， ）／Ｌ１（ｘ，，ｘ ）］（１） ４仿真实验 上式中，Ｌ２（ｘｊ， ）是欧几里德距离，三 ，， ）是曼 为检验形态相似距离用于时间序列相似度计算的 哈顿距离，ＡＳＤ（ｘ，，ｘ ）是数据 与ｘ 的差值和绝对值 可行性和有效性，本文分别采用欧几里德距离和形态相 （Ａｂｓｏｌｕｔｅ ｓｕｍ ｏｆ ｔｈｅ ｄｉｆｅｒｅｎｃｅｓ），其定义为： 似距离两种相似度度量方法，在测试数据上完成了基于 ＡＳＤ（￣， ）：Ｉ∑（ 一Ｘｋｉ）（２） 质心的识别和层次聚类，用以比较这两种距离测量时间 ｌｉ＝１ 序列相似度的性能。 Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ４．１基于质心的识别 基于质心的识别过程是：分别计算求取各类样本的 算术平均值作为各类样本的质心，然后计算所有测试 样本与各类质心的距离，最后依据最邻近法则进行分类 识别。 按照Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ Ｃｈａｒｔ Ｔｉｍｅ Ｓｅｒｉｅｓ数据样 本的顺序，依次选取每类样本的２０条记录，合计１２０条 样本构成一组测试数据，照此方法共计可得到５组测试 数据。计算每一组测试数据各类样本的质心，分别以欧 上 ｒｆ』＝门上］ ｌ样本标号 厂 ｒ——１ ４ ６ ５ ７ ９ ８ ｌ ２ ３ 图２基于欧几里德距离的层次聚类结果 几里德距离和形态相似距离作为相似度测量标准，依据 组内所有样本距离各类质心的距离完成分类。５组的识 别结果记录在表２。 表２基ｆ不同距离的识别结果 组号一ｌ＿ １ １６ ９ ２ １４ ６ ３ １０ ５ ４ １６ ５ ５ １４ ８ 合计 ７０ ３３ 表２表明，在所有的５组测试数据中，形态相似距离 的错误识别数比欧几里德距离均有显著减少。在所有 ６００条样本中，形态相似距离和欧几里德距离无法正确 识别的样本数分别是３３和７０，错误识别率分别５．５％和 ｌ １．６６７％。显然，对于Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ Ｃｈａｒｔ Ｔｉｍｅ Ｓｅｒｉｅｓ 数据，形态相似距离的时问序列相似性计算精度比欧几 里德距离有显著优势。 ４．２ 聚类 聚类（Ｃｌｕｓｔｅｒｉｎｇ）是按照某个特定标准（一般为距 离准则）把一个数据集分割成不同的类或簇（Ｃｌｕｓｔｅｒ）， 使得类内相似性尽可能大，同时类问的差异性也尽可能 大。聚类算法众多，算法的选择取决于数据的类型、聚 类的目的与应用等因素。 本文采用时间序列分析中常用的层次聚类（Ｈｉｅｒａｒ． ｃｈｉｃａｌ Ｃｌｕｓｔｅｒ）算法，其中类的距离采用平均连通方法 （Ｇｒｏｕｐ．ａｖｅｒａｇｅ ｌｉｎｋ），分别采用欧几里德距离和形态相 似距离作为相似度测量标准进行聚类实验。 实验中，聚类数据选取了Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ Ｃｈａｒｔ Ｔｉｍｅ Ｓｅｒｉｅｓ数据中编号依次是［２０１，２０２，２０３，３０１，３０２， ３０３，５０１，５０２，５０３］的１２条样本，也即第３类、第４类和第 ６类中的前３个样本作为测试数据，并将其依次标号为１ 至１２，即标号１—３是上升趋势（Ｉｎｃｒｅａｓｉｎｇ ｔｒｅｎｄ），标号 ４－６是下降趋势（Ｄｅｃｒｅａｓｉｎｇ ｔｒｅｎｄ），标号７－９是快速下降 趋势（Ｄｏｗｎｗａｒｄ ｓｈｉｔｆ）。 分别以欧几里德距离和形态相似距离作为相似度测 量标准完成层次聚类，聚类结果分别示意如图２和图３。 ４ ６ ５ ／８ ９ ｌ ３ ２ 样本标号 图３ 基于形态相似距离的层次聚类结果 图２表明，基于欧几里德距离的层次聚类结果不尽 合理。对于所有ｌ２条样本划分为两个大类，合理区分 了时间序列的上升和下降趋势，但是对于两种下降趋势 的划分，显然出现了偏差，错误将下降趋势的标号５的 样本归类于快速下降趋势，说明该方法无法正确区分下 降和快速下降趋势，存在相当的误差。 图３中所有测试样本聚类正确，聚类结构良好，说 明基于形态相似距离的层次聚类结果明显优于基于欧 几里德距离的聚类，显然，形态相似距离的序列相似度 测量性能优于欧几里德距离。 ５结论与未来工作 时间序列是一类重要的复杂类型数据，时间序列的 相似度量是时问序列数据挖掘的重要任务之一。本文 提出分段后用形态相似距离计算时间序列的相似度，解 决了模式距离及其各种变形的离散化问题，标准数据集 上的实验分析表明，该方法能够较好地描述时间序列趋 势差异，计算简便，相比欧几里德距离具有更高的精度。 未来的工作是改进和完善基于形态相似距离的时 问序列相似度计算和应用，包括如何处理非等长序列的 计算以及研究设计各种基于分段线性表示（Ｐｉｅｃｅｗｉｓｅ Ｌｉｎｅａｒ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ＰＬＲ）的时间序列相似度量方法。 参考文献： ［１］Ａｉｇｎｅｒ Ｗ，Ｍｉｋｓｃｈ Ｓ，Ｍｆｉｌｌｅｒ Ｗ，ｅｔ ａ１．Ｖｉｓｕａｌ ｍｅｔｈｏｄｓ ｆｏｒ ａｎａｌｙｚｉｎｇ ｔｉｍｅ—ｏｒｉｅｎｔｅｄ ｄａｔａ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，２００８，１４（１）：４７—６Ｏ． ［２］Ｃｈｕｎｇ Ｆｕ—Ｌａｉ，Ｆｕ Ｔａｋ—Ｃｈｕｎｇ，Ｎｇ Ｖ，ｅｔ ａ１．Ａｎ ｅｖｏｌｕｔｉｏｎａｒｙ ａｐｐｒｏａｃｈ ｔｏ ｐａｔｔｅｒｎ－ｂａｓｅｄ ｔｉｍｅ ｓｅｒｉｅｓ ｓｅｇｍｅｎｔａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００４，８（５）：４７ １—４８９． （下转１４７页） 杨秀娟，董军，李慧慧：欧式空间中反向最远邻查询方法的研究 ２０１５，５１（４） 哈尔滨工程大学学报，２００８，２９（３）：２６１．２６５． １４７ 反向最远邻查询问题。为了更具实用性，下一步应将算 法应用到交通路网中。 ［８】Ｂｅｎｅｔｉｓ Ｒ Ｓ，Ｊｅｎｓｅｎ Ｃ，Ｋａｒｃｉａｕｓｋａｓ Ｇ，ｅｔ ａ１．Ｎｅａｒｅｓｔ ａｎｄ ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｑｕｅｒｉｅｓ ｆｏｒｍｏｖｉｎｇ ｏｂｊｅｃｔｓ［Ｃ］／／ 参考文献： ［１］Ｋｏｍ Ｆ，Ｍｕｔｈｕｋｒｉｓｈｎａｎ Ｓ，Ｓｒｉｖａｓｔａｖａ Ｄ．Ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈ－ ｂｏｒ ａｇｇｒｅｇａｔｅｓ ｏｖｅｒ ｄａｔａｓｔｒｅａｍｓ［Ｃ］／／ＶＬＤＢ，２００２：８１４－８２５． ［２］Ｂｅｎｅｔｉｓ Ｒ，Ｓ．Ｊｅｎｓｅｎ Ｃ，Ｋａｒｃｉａｕｓｋａｓ Ｇ，ｅｔ ａ１．Ｎｅａｒｅｓｔ ａｎｄ ＶＬＤＢ，２００６，１５（３）：２２９—２４９． ［９】Ｋｏｒｎ Ｆ，Ｍｕｔｈｕｋｒｉｓｈｎａｎ Ｓ．Ｉｎｆｌｕｅｎｃｅ ｓｅｔｓ ｂａｓｅｄ ｏｎ ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｑｕｅｒｉｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２０００ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ． Ｄａｌｉａｓ，Ｔｅｘａｓ，ＵＳＡ：ＡＣＭ Ｐｒｅｓｓ，２０００：２０１－２１２． ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｑｕｅｒｉｅｓ ｆｏｒｍｏｖｉｎｇ ｏｂｊｅｃｔｓ［Ｃ］／／ ＶＬＤＢ，２００６，１５（３）：２２９．２４９． ［１０］李博涵，郝忠孝．反向最远邻的有效过滤和查询算法［Ｊ］－，ｊ、 型微型计算机系统，２００９，３０（１０）：ｌ９４８．１９５１． ［１ １］Ｙａｏ Ｂ，Ｌｉ Ｆ，Ｋｕｍａｒ Ｐ．Ｒｅｖｅｒｓｅ ｆｕｒｔｈｅｓｔ ｎｅｉｇｈｂｏｒｓ ｉｎ ｓｐａｔｉａｌ ｄａｔａｂａｓｅｓ［Ｃ］／／ＩＣＤＥ，Ｓｈａｎｇｈａｉ，２００９：６６４—６７５． ［１２］Ｌｉｕ Ｊ，Ｃｈｅｎ Ｈ，Ｆｕｒｕｓｅ Ｋ，ｅｔ ａ１．Ａｎ ｅｆｉｃｉｆｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｅｖｅｒｓｅ ｆｕｒｔｈｅｓｔ ｎｅｉｇｈｂｏｒｓ ｑｕｅｒｙｗｉｔｈ ｍｅｔｒｉｃ ｉｎｄｅｘ［Ｃ］／／ ＤＥＸＡ．Ｂｅｒｌｉｎ：Ｈｅｉｄｅｌｂｅｒｇ，２０１０：４３７—４５１． 【３］Ｋａｎｇ Ｊ Ｍ，Ｍｏｋｂｅｌ Ｍ Ｆ，Ｓｈｅｋｈａｒ Ｓ，ｅｔ ａ１．Ｃｏｎｔｉｎｕｏｕｓ ｅｖａｌ— ｕａｔｉｏｎ ｏｆ ｍｏｎｏｃｈｒｏｍａｔｉｃ ａｎｄｂｉｃｈｒｏｍａｔｉｃ ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ［Ｃ】／／Ｉｓｔａｎｂｕｌ，Ｉｎ ＩＣＤＥ，２００７：８０６・８ １ ５． ［４］Ｃｈｅｏｎｇ Ｏ，Ｖｉｇｎｅｒｏｎ Ａ，Ｙｏｎ Ｊ．Ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｑｕｅｒｉｅｓ ｉｎ ｆｉｘｅｄ ｄｉｍｅｎｓｉｏｎ［Ｊ］．Ｉｎｔ Ｊ Ｃｏｍｐｕｔ Ｇｅｏｍｅｔｒｙ Ａｐｐｌ， ２０１１，２１（２）：１７９．１８８． ［５］Ｔｒａｎ Ｑ Ｔ，Ｔａｎｉａｒ Ｄ，Ｓａｆａｒ Ｍ．Ｂｉｃｈｒｏｍａｔｉｃ ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ． ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈ ｉｎ ｍｏｂｉｌｅ ｓｙｓｔｅｍｓ［Ｊ］．ＩＥＥＥ Ｓｙｓｔｅｍｓ Ｊｏｕｒｎａｌ （ＳＪ），２０１０，４（２）：２３０．２４２． ［１３］王宝文，彭川，陈子军，等．路网上的单色和双色反ｋ最远 邻查询［Ｊ】．计算机工程与设计，２０１２，３３（８）：３０９９－３１０４． ［１ ４】Ｔａｏ Ｙｕｆｅｉ，Ｐａｐａｄｉａｓ Ｄ，Ｌｉａｎ Ｘ，ｅｔ ａ１．Ｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎａｌ ｒｅｖｅｒｓｅ ｋｎｎ ｓｅａｒｃｈ［Ｃ］／／Ｔｈｅ ３２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ，Ｓｅｏｕｌ，Ｋｏｒｅａ，２００６：１２１－１６３． ［６］Ｔａｏ Ｙ，Ｙｉｕ Ｍ Ｌ，Ｍａｍｏｕｌｉｓ Ｎ．Ｒｅｖｅｒｓｅ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈ ｉｎ ｍｅｔｒｉｃ ｓｐａｃｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌ－ ｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，２００６，１８（９）：１２３９・１２５２． ［１ ５］Ｔａｏ Ｙ，Ｐａｐａｄｉａｓ Ｄ，Ｌｉａｎ Ｘ．Ｒｅｖｅｒｓｅ ｋＮＮ ｓｅａｒｃｈ ｉｎ ａｒｂｉ－ ｔｒａｒｙ ｄｉｍｅｎｓｉｏｎａｌｉｔｙ［Ｃ］／／ＶＬＤＢ，Ｔｏｒｏｎｔｏ，Ｃａｎａｄａ，２００４： ７４４—７５５． ［７］李松，郝忠孝．基于ｖ０ｒｏｎｏｉ图的反向最近邻查询方法研究［Ｊ】． （上接１２２页） ［３】林子雨，杨冬青，王腾蛟用基于移动均值的索引实现时间 序列相似查询［Ｊ］．软件学报，２００８，１９（９）：２３４９．２３６１． ［４］Ａ１一Ｎａｙｍａｔ Ｇ，Ｔａｈｅｒｉ Ｊ．Ｅｆｆｅｃｔｓ ｏｆ ｄｉｍｅｎ－ｓｉｏｎａｌｉｔｙ ｒｅｄｕｃｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ｏｎ ｔｉｍｅ ｓｅｒｉｅｓ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｍｅｎｔ［Ｃ］／／ Ｔｈｅ ６ｔｈ ＡＣＳ／ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ 研究［Ｊ］．电子与信息学报，２００７，２９（５）：１２２８—１２３１． ［９］张鹏，李学仁，张建业，等．时间序列的夹角距离及相似性 搜索［Ｊ】．模式识别与人工智能，２００８，２１（６）：７６３－７６７． ［１０］丁永伟，杨小虎，陈根才，等．基于弧度距离的时间序列相 似度量［Ｊ］．电子与信息学报，２０１１，３３（１）：１２２—１２８． ［１ １］Ｂｅｒｎｄｔ Ｄ，Ｃｌｉｆｏｒｄ Ｊ．Ｕｓｉｎｇ ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｒｐｉｎｇ ｔｏ ｆｉｎｄ ｐａｔｔｅｒｎｓ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ［Ｃ］／／ＡＡＡＩ・・９４ Ｗｏｒｋｓｈｏｐ ｏｎ Ｋｎｏｗｌ— ｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｉｎ Ｄａｔａｂａｓｅｓ（ＫＤＤ一９４），Ｓｅａｔｔｌｅ，Ｗａｓｈ－ ｉｎｇｔｏｎ，１９９４． Ｓｙｓｔｅｍｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，Ｄｏｈａ，Ｑａｔａｒ，Ｍａｒ ３ １－Ａｐｒ ４，２００８： １８８—１９５． ［５］王燕，马倩倩，韩萌．基于特征点分段的多元时间序列相似 性搜索［Ｊ】．计算机工程应用，２０１２，４８（３３）：１６２．１６６． ［６］Ｓｈａｔｋａｙ Ｈ，Ｚｄｏｎｉｋ Ｓ Ｂ．Ａｐｐｒｏｘｉｍａｔｅ ｑｕｅｒｉｅｓ ａｎｄ ｒｅｐｒｅｓｅｎ— ［１ ２］Ｌｉ Ｚｈｏｎｇ，Ｙｕａｎ Ｊｉｎｓｈａ，Ｚｈａｎｇ Ｗｅｉｈｕａ．Ｆｕｚｚｙ Ｃ—ｍｅａｎ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｍｏｒｐｈｏｌｏｇｙ ｓｉｍｉｌａｒｉｔｙ ｄｉｓｔａｎｃｅ［Ｃ］／／ＦＳＫＤ２００９， Ｔｉａｎｊｉｎ，Ｃｈｉｎａ，２００９：９０－９４． ［１ ３】Ｌｉ Ｚｈｏｎｇ，Ｙｕａｎ Ｊｉｎｓｈａ．Ａｎ ｅｓｔｉｍａｔｉｏｎ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ ｔａｔｉｏｎｓ ｆｏｒ ｌａｒｇｅ ｄａｔａ ｓｅｑｕｅｎｃｅｓ［ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ ２ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｅｗ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｏｆ ｖｅｃｔｏｒ ｄｉｆｆｅｒｅｎｃｅ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ，２０１１，１４（３）：１０６７—１０７４． ［１４］Ｐｈａｍ Ｄ Ｔ，Ｃｈａｎ Ａ Ｂ．Ｃｏｎｔｒｏｌ ｃｈａｒｔ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｕｓｉｎｇ ａ ｎｅｗ ｔｙｐｅ ｏｆ ｓｅｌｆ ｏｒｇａｎｉｚｉｎｇ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ［Ｃ］／／ Ｐｒｏｃ ｌｎｓｔｎ，Ｍｅｃｈ，Ｅｎｇｒｓ，１９９８，２１２（１）：１１５－１２７． Ｏｒｌｅａｎｓ，Ｌｏｕｉｓｉａｎａ，Ｆｅｂ ２６．Ｍａｒ １，１９９６：５３６．５４５． ［７】王达，荣冈．时间序列的模式距离［Ｊ］．浙江大学学报：工学 版，２００４，３８（７）：７９５．７９８． ［８］董晓莉，顾成奎，王正欧．基于形态的时间序列相似性度量
