基于时间序列演变分析的有效相似性定义和聚类

Ｃｏｍｐｕｉｅｒ　，　ｎｅｅｒｉｎｇ　ａｌＴ　０ｄ　Ａｐｐｌｉｃ（ｕｉｏｎｓ计算机工程与应用　基于时间序列演变分析的有效相似性定义和聚类　周原冰，左新强，顾杰，赵春晖　ＺＨＯＵ　Ｙｕａｎ—ｂｉｎｇ，ＺＵＯ　Ｘｉｎ—ｑｉａｎｇ，ＧＵ　Ｊｉｅ，ＺＨＡＯ　Ｃｈｕｎ—ｈｕｉ　国网北京经济技术研究院，北京１００７６１　Ｓｌａｔｅ　Ｐｏｗｅｒ　Ｅｃｏｎｏｍｉｃ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ　１００７６１，Ｃｈｉｎａ　Ｅ—ｍａｉｌ：ｚｈｏｕｙｃ　ａｎｂｉｎｇ＠ｃｈｉｎａｓｐｅｒｉ．ｃｏｍ．ｃｎ　ＺＨＯＵ　Ｙｕａｎ－ｂｉｎｇ，ＺＵＯ　Ｘｉｎ—ｑｉａｎｇ，ＧＵ　Ｊｉｅ，ｅｔ　ａ１．Ｅｆｆｅｃｔｉｖｅ　ｓｉｍｉｌａｒｉｔｙ　ｄｅｆｉｎｉｔｉｏｎ　ａｎｄ　ｃｌｕｓｔｅｒｉｎｇ　ｔｈｒｏｕｇｈ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｅｖｏｌｕｔｉｏｎ　ａｎａｌｙｓｉｓ，．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．２００８．４４（１０）：１３８－１４１．　Ａｂｓｔｒａｃｔ：Ｔｉｒｒｅ　ｓｅｒｉｅｓ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｗｉｄｅｌｙ—ｕｓＩＩｌｆ　ｄａｔａ　ｉｎ　ｂｕｓｉｎｅｓｓ　ｚｐｐｌｉｃａｔｉｏｎｓ．ｅ．ｇ．ｐｏｗｅｒ　ｌｏａｄ　ｓｅｑｕｅｎｃｅ．ｗｅｂ　ｌｏｇ　ｅｔｃ．ｈ　ｉｓ　Ｖｅｒｖ　ｉｍｐｏｒｔａｎｔ　ｔｏ　ｍｉｎｅ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｆｏｒ　ｓｕｐｐｏｒｔｉｎｇ　ｄｅｅｉｓｉｏｌｌ—ｍａｋｉｎｇ．Ｅｓｐｅｃｉａｌｌｙ．ｄｅｔｅｒｍｉｎｉｎｇ　ｔｈｅ　ｓｉｍｉｌａｒｉｔｙ　ｏｆ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｐｌａｙｓ　ａ　ｋｅｙ　ｐａｒｔ　ｉｎ　ｖａｒｉｏｕｓ　ｐｒｏｂｌｅｍｓ．ｅ．ｇ．ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｆｅａｔｕｒｅｓ　ｏｆ　ｅｌｅｔｒｉｅｉｔｙ　ｄｅｍａｎｄ　ｆｏｒ　ｅａｃｈ　ｄｉｓｔｒｉｃｔ．Ｔｈｅ　ｐｒｅｖｉｏ￣ｍａｎａｇｉｎｇ　ａｎｄ　ｍｉｎｉｎｇ　ｄａｔａ，ｈａｒｄｌｙ　ｏｒ　ｄｏ　ｎｏｔ　ｅｎｏｕｇｈ　ｕｓｅ　ｔｈｅ　ｅ￣ｏｌｕｔｉｏｎ￣ｍｅｔｈｏｄｓ．ｉｎ　ｔｈｅ　ｃｏｎｔｅｎｔ　ｏｆ　ｉａｌｔｙ　ｏｆ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｔｏ　ｍｅａｓｕｒｅ　ｓｉｍｉｌａｒｉｔｙ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａｎ　ｕｎｅｘｐｌｏｒｅｄ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ　ａｐｐｒｏａｃｈ　ｂａｓｅｄ　ｏｎ　ｅｖｏｌｕｔｉｏｎ　ａｎａｌｙｓｉｓ　ｃｆ　ｔｉｍｅ　ｓｅｒｉｅｓ，ａｎｄ　ｔｈｉｓ　ａｐｐｒｏａｃｈ　ｑｕａｎｔｉｆｉｅｓ　ｔｈｅ　ｅｖｏｌｕｔｉｏｎ　ｔｒｅｎｄ　ｔｏ　ｅｏｎｓｔｒｕ￣ｅｆｆｅｃｔｉｖｅ　ｓｉｍｉｌａｒｉｔｙ　ｄｅｆｉｎｉｔｉｏｎ，ｔｅｎｎｅｄ　Ｓｉｍｉｌａｒｉｔｙ　ｗｉｔｈ　Ｅｖｏｌｕｔｉｏｎ　Ａｎａｌｙｓｉｓ　（ＳＥＡ）．Ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｓｔｒａｔｅｇｙ　ｂａｓｅｄ　ｏｎ　ＳＥＡ　ｉｓ　ａｌｓｏ　ｐｒｏｖｉｄｅｄ．Ｔｈｅ　ｓｕｐｅｒｉｏｒ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｏｆ　ｃｏｍｐａｒｅｄ　ｍｅｔｈｏｄｓ　ｏｎ　ｌ　ｅａｌ　ｄａｔａ　ｓｅｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｔｈｅ　ｍｅｔｈｏｄ　ｐｒｏｐｏｓｅｄ，ａｎｄ　ｔｈｕｓ　ｉｍｐｌｙ　ｔｈｅ　ｉｍｐｏｒｔａｎｔ　ｓｉｇｎｉｆｉｃａｎｃｅ　ｃｆ　ｅｖｏｌｔｉｏｎ　ａｎａｌｙｓｉｓｕ　ｆｏｒ　ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓｕｒｅ（）ｆ　ｔｉｒｒｅ　ｓｅｒｉｅｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｔｉｒｒ　ｅ　ｓｅｒｉｅｓ；ｓｉｍｉｌａｒｉｔｙ　ｄｅｆｉｎｉｔｉｏｎ；ｅｖｏｌｕｔｉｏｎ　ａｎａｌｙｓｉｓ；ｃｌｕｓｔｅｒｉｎｇ　摘要：时间序列广泛存在于商业应用中，比如电力负荷序列、网络日志等　挖掘时间序列数据对决策分析非常重要，特别地，决定　时间序列的相似性在各种实际问题中起关键的作用，比如分析各个区域的电力需求特征。以前的相似性度量方法从未使用过演变　这种特性去度量时间序列的相似性，基于演变分析提出了有效的时间序列相似性度量方法（ＳＥＡ），该方法通过量化演变趋势构建　了有效的相似性定义，并且提出了基于该方法的聚类策略．　通过在实际数据集上和其它方法的实验比较，证明了提出方法的有效　性，因此也证明了时间序列演变分析对相似性度量的重要意义。　关键词：时间序列；相似性定义；演变分析；聚类　文章编号：１００２．一８３３ｌ（２００８）１０—０１３８—０４　文献标识码：Ａ　中图分类　：ＴＰ３９１　４１　１前言　时间序列作为一种有时问标志的数据类型，在各种领域中　都有应用，如电力负荷序列、股票数据、传感器数据、室内温度　数据、人口数据等。对于时问序列数据管理和挖掘系统来说，相　似性定义是一个基本的需求，它决定了范围查询和ＫＮＮ（Ｋ—　Ｎｅａｒｅｓｔ　Ｎｅｉｇｈｂｏｒ）查询的返回结果，同时严重地影响分类和聚　类等应用的精度，因此吸引了大量的研究工作者设计有效的相　似性定义（或者是距离公式）。在相关的搜索和数据挖掘领域，　如下：　（１）时间序列　和ｌ，的相似性描述了ｘ演变为ｙ的概率　（或者ｙ演变为ｘ）；　（２）　的演变具有方向和大小，也就是说　的每一维具有　不同的变化权重，在有些方向上，　不能到达；　（３）在某一时刻，数据的演变趋势可以通过下一时刻的数　值得到。　由于演变趋势是时问序列所固有的本质，凶此如果一个时　问序列演变为另一个的概率很大，那么它们就具有相似的本　质，这是使用演变分析来度量时问序列相似性的核心思想。明　显地，在某个确定的潜在规则下，将一个给定的时问序列变为　一以前的方法大多数将时间序列直接作为高维数据来度量，但是　都没有涉及到时间序列的本质的演变特性，这种特性描述了一　个变量随时间变化的趋势，比如每天的股票价格。　演变分析已经研究了很多年…，然而没有任何工作通过时　个随机的序列（潜在随机变化）几乎是不可能的，除非这个规　则是完全随机的，一般来说，任何时　序列的变化都具有一定　间序列的本质演变去提高相似度量的效果，在本文中，提出了　一个新的基于演变分析的时间序列相似性定义，主要的思想　的限制，比如每天的温度几乎不可能高于６０￣Ｃ，所以时间序列　作者简介：周原冰（１９７１一），男，高级工程师，主要研究领域为电力信息资源管理与决策支持、电力经济技术分析等；左新强（１９８２一），男，硕士，主　要研究领域为数据挖掘、数据库；顾杰（１９８３一），硕士，主要研究领域为数据挖掘；赵春晖（１９７４一），女，高级工程师，主要研究领域为软　件工程。　收稿日期：２００７一－Ｃ７—２．３　修回ｆ１期：２００７—１０—２４　维普资讯 http://www.cqvip.com 周原冰，左新强，顾　杰，等：基于时间序列演变分析的有效相似性定义和聚类　———————＝；＝＝＝＝＝＝＝＝＝＝——————＝；＝＝＝＝２　＝＝—————；＝；＝＝＝＝＝　＝＝—————＝＝＝＝　——————；＝＝＝＝　＝　—————＝＝＝＝一一２００８．４４（１Ｏ）　１３９　＝＝　＝—————＝＝一，　的演变是具有一定规则或者限制的。提出的方法使用方向和大　小量化地描述演变趋势，它们由时间序列在所有维度上的变化　权重以及分布决定，时间序列中随时问连续变化的值满足分析　趋势的需求，因此使用连续的值来判断前一时刻的演变趋势。　步骤１映射：一个长度为ｎ的时问序列被映射到ｎ一１维　的空间中；　步骤２演变趋势分析：用一个向量去表示时间序列的演　变趋势；　在提出的方法中，首先用一个映射的方法将时间序列转换　为一个向量，该向量在高维空间中有一个起始点代表数据本　身，它的方向和模代表其演变的方向和大小，则在其它方向上　演变的大小可以通过投影来计算得到。时间序列　和ｌ，的相　步骤３相似性距离：设汁一个有效的公式去计算两个时　间序列的距离。　３．１演变趋势映射　Ｘ＝ｘ　，…，‰表示一个时间序列，其中每个值鼍对应一　个时间点，Ｘ［ｉｌ＝ｘ　表示在第　个取样时问点上的值，ＩＸＩ＝ｎ表示　时间序列　的长度为ｎ，映射过程通过以下步骤完成：　似性距离是由　的演变向量在　一墨方向上的投影和它们之　问空间距离决定的，其中鼍和　分别是　和ｌ，映射向量。基　于相似性定义，又提出了一个有效的聚类方法，最后，给出了实　验，结果汪明了提出方法的有效性。本文的主要贡献主要包括：　（１）在演变分析和时间序列相似性定义之间构建了一个有　意义的连接；　（２）通过量化时序数据的演变趋势，设计了一个基于演变　分析的有效相似性度量；　（３）提出了一个有效的聚类方法。　２相关工作　近些年，在时间序列研究方面，有很多的工作和成果，如时　问序列的分类Ｉ”Ｉ、聚类　ｓＩ、变化监测ｌ】ＵＩ、降维等Ｉ　－　Ｉ。在这些应用　中，相似性度量是一个基本的过程，而且对系统的性能有很大　影响。欧式距离（Ｅｕｃｌｉｄｅａｎ　Ｄｉｓｔａｎｃｅ）是最流行的度量方法，因　为它简单而且快速，并且能够支持各种索引技术，然而它不能　处理局部的时间弯曲，这对时间序列度量方法的可用性是非常　重要。ＢｅｒｎｄｔＩ　’等提出用ＤＴＷ（Ｄｙｎａｍｉｃ　Ｔｉｍｅ　Ｗａｒｐｉｎｇ）去度量　时间序列的形似性，它允许时间轴上的弯曲，但是它对噪音很　敏感，主要是由于它的连续弯曲路径造成的；ＬＣＳＳ（Ｌｏｎｇｅｓｔ　Ｃｏｍｍｏｎ　Ｓｕｂｓｅｑｕｅｎｃｅ）具有抗噪音能力，但是由于不同的间隔　存在于相似的形状中，造成了度量时的不准确『　；近来，Ｌｅｉ等分　别提出了ＥＲＰ（Ｅｄｉｔ　ｄｉｓｔａｎｃｅ　ｗｉｔｈ　Ｒｅａｌ　Ｐｅｎａｌｔｙ）１５１和ＥＤＲ（Ｅｄｉｔ　Ｄｉｓｔａｎｃｅ　ｏｎ　Ｒｅａｌ　ｓｅｑｕｅｎｃｅ）１６１来度量多维时间序列的相似性，　ＥＲＰ对噪音也很敏感，ＥＤＲ虽然不满足三角不等式，但是给出　了一个近似的三角不等式。近期，Ｍｅｇａｌｏｏｉｋｏｎｏｍｏｕ等提出了一　种时间序列的多分解表示方法，并使用多层直方图模型来度量　新的表示之间的距离１　Ｉ，Ｖｌａｃｈｏｓ等通过萃取的周期特征来度　量相似性，而不是时间点上的数值。在相似性度量之前，有一个　简单但是非常重要的预处理，就是归一化Ｉ　Ｉ，它是为了去除时　问序列上值的绝对大小对相似性度量的影响　。　虽然已经提出了多种相似性度量方法来提高效果，但是度　量的结果还是要依赖于数据和任务本身，造成很多方法在实际　中不可用，这主要是因为以前的方法从未考虑过数据的本质特　征，也就是说它们的度量过程和数据本身是无关的。演变分析　是一种发现事物发展规律或者趋势的技术，可以被用来分析时　间序列的本质趋势…Ｉ。本文通过将的演变分析引入到度量过程　中来提高相似性度量的效果。　３基ｆ演变分析的相似性：ＳＥＡ　通过估计时间序列之间的演变概率，提出的方法ＳＥＡ设　计了全新的度量机制，其中演变概率是通过时间序列的演变趋　势和普通的距离公式计算得到的。方法的主要步骤包括：　（１）Ｘ被映射为ｎ一１维空间中的点，定义为　＝（　…，　．）（ｏｒ　）。这个简单的过程主要是为了保留原始序列的静态　信息，它定义了演变的基本点，也就是开始点。　（２）演变向量被形式化地定义为　＝（　一　Ｘ３－Ｘ　，…，％一　）。这一步使用一阶差分来描述　的趋势，考虑时问序列的　意义，　正是　的下一个抽样值，因此使用Ｘｉ＋１－Ｘ　来描述鼍的　动态趋势是有道理的。在ＳＥＡ中，使用　来表示　拥有最大　演变概率的方向，也就是说　最容易向这个方向演变，然后，　通过在某个方向映射来得到　在下一个时问点向该方向演变　的概率。　（３）Ｘ被表示为一个特殊的向量，定义为　＝（　，　），它拥　有一个确定的起始点　，而不允许平移，ｘ　的方向和模定义为　的方向和模。事实上，　的结束点就是（　…　），也就是　在下一个时刻的值。　以上的定义可以通过以下的例子说明：　＝（４，５，６，７）的长　度等于４，然后　将被映射到三维空问中，其中　＝（４，５，６），　Ｘ＝（１，１，１）。　３．２演变相似性距离　在给定时间序列的岸边趋势映射后，本节将定义两个序列　问的演变相似性距离（Ｅｖｏｌｕｔｉｏｎ　Ｓｉｍｉｌａｒｉｔｙ　Ｄｉｓｔａｎｃｅ，ＥＳＤ）。给　定两个时问序列　和】，，长度均为ｎ，通过以下三步来计算它　们之间的相似性（或者说不相似性），如图Ｉ所示。　＝墨　其中　・（　—　）表示　和（　—　）的叉积，Ｉ　—　Ｉ是（　—Ｘ）　的模。　（３）计算Ｘ和ｙ、的空问距离，记为ｄ（　，　），其中ｄ是欧　维普资讯 http://www.cqvip.com １４０　２００８，４４（１０）　Ｃｏｍｐｕｔｅｒ　Ｅ，　ｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　ＨＡＣ）ｉｘ‘的，首先，两种时问序列关系定义如下：　定义２可达眭。假如Ｅｒ＞０，则定义为　是可达ｙ的，否　则，Ｘ是不可达ｌ，的。　定义３连通性。假如ｘ是可达ｌ，的或者ｙ是可达ｘ的　（Ｅ：＞０或者Ｅ　＞０），则定义为　和ｙ是连通的，否则它们是不　连通的。这个关系满足对称性，但是不满足传递性，可以通过以　下的例子征　ｊ：　＝（０，０，１），则Ｘ＝（０，０），　＝（０，１）；　＝（２，１，１），ｌ』｛０　ｙ‘＝　（２，１），　＝（一１，０）；　（３，４，４），则ｚ　＝（３，４），　＝（１，０）那么可以　Ｏ＜０￣　ｄ６）＞　假如＠是可导的，则以上属性可以被描述为ｄｄａ得到，Ｅ：＞０，Ｅ。＞０，但是Ｅ　＜０且Ｅ　＜０，根于居连通性的定义，虽　然ｘ和ｙ连通，ｘ和ｚ连通，但是ｙ和ｚ是不连通的　不同于普通的层次聚类，提出的聚类策略中增』Ｊｕ了以下　约束：　聚类约束：在聚类凝聚过程Ｌ｝ｌ，ｘ可以被分到类Ｃ　Ｌ｝ｌ，仅　Ｃ中至少有一个时　序列和ｘ连通。　那么可以通过ｉ；芝置不连通的序列　的距离为无穷大（　）　来的得到新的层次聚类算法，　为无限的距离存在ｆ聚类过　６　５６．０、＋　置ｆ．　　，●‘。５　５　Ｘ　，　、／　／ｌ　程中，则需要重新设汁方法去汁算类之问的距离以及聚类结　束条件。首先定义两个类之间的连通度（Ｃｏｎｎｅｃｔｉｖｅ一１）ｅｇｒｅｅ，　、　Ｉ　Ｖ　、、　ＣｏｎｎＤ），给定两个类　＝　．，Ａ　，…，　和Ｂ＝Ｂ．，　，…，　，其Ｉ｝Ｊ　Ａ，（１≤ｉ≤ｎ）和Ｂ　（１＜－ｊ≤ｍ）是类中的时问序列，Ｉ１币¨ｉｎ分别是　类　和类　的大小，！Ｊ！ｌｊ　和　的连通度定义如下：　ＣｏｎｎＤ　Ａ　Ｂ　）＝　．一、　　｜一（．）（：　Ｉ＇　’　ａｌ。１【　—　—　一　一　。　ｉ｝。（３）　（）　ｎｘ，ｎ　要汁算两个类之间的距离，需要度量两个Ｉ大Ｊ素，丰要包括　连通度（Ｃｏｎｎｅｃｔｉｖｅ—Ｄｅｇｒｅｅ，ＣｏｎｎＤ）和一般化距离（Ｇｅｎｅｒａｌ—　６．０　５　．　５　５　、　ｘ　Ｘ，／Ａｉ／　Ｄｉｓｔａｎｏｅ，ＧｅｎＤ），其中ＧｅｎＤ的计算和普通的ＨＡＣ中的类　距　基本相似，比如最小距离、最大距离、完全距离和平均距离。给　定类Ａ、Ｂ、Ｃ和Ｄ，通过以下方法，比较　、　和ｃ、Ｄ的类　距（ＣＤｉｓｔａｎｅｅ），找到距离较小的两个类，在聚类过程中将它　们合并：　（１）ＣＤｉｓｔｔａｎｃｅ（Ａ，Ｂ）＜ＣＤｉｓｔａｎｃｅ（Ｃ，Ｄ），假如ＣｏｎｎＤ（Ａ，Ｂ）＞　ＣｏｎｎＤ（Ｃ，Ｄ）或者ＣｏｎｎＤ（Ａ，Ｂ）＝ＣｏｎｎＤ（Ｃ，Ｄ）而且Ｇｅｎ１）（Ａ，Ｂ）＜　ＧｅｎＤ（Ｃ，Ｄ）；　５、、＼、一｜　一　一‘４　一ｊ　一一一　一。　（２）Ｃ１）ｉｓｔｔａｎｃｅ（　，Ｂ）＝ＣＤｉｓｔａｎｅｅ（Ｃ，Ｄ），假如ＣｏｎｎＤ（Ａ，Ｂ）＝　ＣｏｎｎＤ（Ｃ．Ｄ）＾ＧｅｎＤ（Ａ，Ｂ）＝ＧｅｎＤ（Ｃ，Ｄ）　．　也就是说，汁算类间距的时候，ＣｏｎｎＤ比ＧｅｎＤ的优先级高；此　外，汁算ＧｅｎＤ时，取消遇到的无限距离（两个时　序列是不连　通的），以便得到有限的结果。在聚类中，为了满足提出的聚类　约束，除了传统ＨＡｃ的类数和最大距离外，增』Ｊｕ了新的结束条　件如下：　新的聚类连通性结束条件：对于当前任意的两个类　和　Ｂ，Ｃｏｎｎ（Ａ，Ｂ）＝０。　完整聚类算法（使用类数作为结束条件之一）如下：　Ｆｕｎｃ　ｔｉ　基于ＳＥＡ的层次距离算法　输入：Ｔ，ｎ，　；／／Ｔ是包含所有时『日Ｊ序列的集合　是７１的大小；　是预没的类数　输出：｛ｃ　，Ｃ！，…，　）／／ｃ　是第ｉ个类，ｍ≥　１．ｆ０ｒ　１：　２．　３．ｅｎｄ　初始化Ｃ　｛　ｌｉＴ，是丁中第ｉ个序列　４ｗｈｉｌ　，　＞　维普资讯 http://www.cqvip.com

周原冰，左新强，顾　杰，等：基于时间序列演变分析的有效相似性定义和聚类　２００８．４４（１０）　１４１　５．　汁算两两类之问的ＧｏｎｎＤ和ＧｅｎＤ　６．　ｉｆ（连通性结束条件满足）　７．　ｒｅｔｕｒｎ当前的类集合　８．　ｅｌｓｅ　９．　合并ＣＤｉｓｔａｎｃｅ最小的两个类　ｌ０．　ｎ￣／２－ｌ　ｌ１．　ｅｎｄ　ｌ２．ｅｎｄ　１３．ｒｅｔｕｒｎ当前的类集合　５实验评价　在本章中，通过聚类实验（ｃｌｕｓｔｅｒｉｎｇ）来测试提出的方法和　其他方法的性能，公用的实际数据集被用在测试中。　５．１实验框架　比较的方法主要有：欧式距离（ＥＤ）、ＤＴＷ、ＬＣＳＳ、ＥＤＲ以　及本文提出的方法ＳＥＡ。　实验数据：ＴＥＭＰ是一个温度数据集　，包括美国３０个地　方２０００年的温度，每一个时问序列代表一个地方３６６天的温　度变化，根据地理位置３０个时问序列被分为４类，作为度量标　准结果。　评价方法：凝聚的层次聚类用来实现其它方法的聚类实　验，其中簇间距使用完全距离（ｃｏｍｐｌｅｔｅ　ｄｉｓｔａｎｃｅ）计算，使用一　种常见方法来度量聚类的精度，给定每个方法的聚类结果ｃ　＝　ｃ　，ｃ：　，…，　和从先验的分类信息中得到的标准结果Ｃ＝Ｃ　，　ｃ　，…，　，则聚类精度可由以下公式计算［ｓｌ：　ｓｊ　（Ｃｉ，　ｍａｘｊＳｉｌｌｌ（Ｃｉ，Ｇ　）　Ｓｉｍ（Ｃ。Ｃ　）＝　Ｓｉｍ（Ｃ　，Ｃ）的汁算和Ｓｉｍ（Ｃ，Ｃ　）类似，因为Ｓｉｍ（Ｃ，Ｃ　）和　Ｓｉｍ（Ｃ　，Ｃ）不对称，故都被作为最终结果。　５．２实验结果　图３给出了在ＴＥＭＰ数据集上的聚类结果，从图中可以看　出，ＳＥＡ的精度比其它方法都要高，这说明了提出的方法能够　更准确地度量时问序列的相似性，进一步表明了演变分析对时　间序列度量和聚类的重要提高。　ｌ剞３聚类精度比较　６　结论和总结　本文通过研究演变分析，提出了有效的时问序列相似性定　ｉｌｔｔｐ：／／ｗｗｗ．ｅｓｅｅ．ｕｍｂｅ．ｅｄｕ／￣ｋａｌｐａｋｉｓ．　义，量化了演变趋势，将每一个时间序列转换为一个向量，该向　量表示了演变的方向和大小。通过将时间序列的演变向量映射　到指向其它序列的方向，给出了新的相似性度量公式，并且提　出了基于该方法的新的聚类策略。通过在真实数据集上的实　验，结果证明了提出方法的有效性，因此也证明了演变分析对　构建有力的相似性度量方法的重要性。　参考文献：　【１］Ｇｕｓｔａｖｏ　Ｄ，Ｂｅｒｎｄ　ｓ．Ｌｅａｒｎｉｎｇ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｅｖｏｌｕｔｉｏｎ　ｂｙ　ｕｎｓｕｐｅｒｖｉｓｅｄ　ｅｘｔｒａｃｔｉｏｎ　ｏｆ　ｃｏｒｒｅｌａｔｉｏｎｓ［Ｊ］、Ｐｈｙｓｉｃａｌ　Ｒｅｖｉｅｗ　Ｅ，ｌ９９５，５ｌ（３）：ｌ７８０—　１７９０．　【２］Ａｇｒａｗａｌ　Ｒ，Ｆａｌｏｕｔｓｏｓ　Ｃ，Ｓｗａｍｉ　Ａ　Ｎ．Ｅｆｆｃｉｅｎｔ　ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ　ｉｎ　ｓｅｑｕｅｎｃｅ　ｄａｔａｂａｓｅｓ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｄａｔａ　Ｏｒｇａｎｉｚａｔｉｏｎ　ａｎｄ　Ａｌｇｏｒｉｔｈｍｓ，Ｃｈｉｃａｇｏ，ＩｌＬｉｎｏｉｓ，１９９３：６９—８４．　［３］Ｂａｇｎａｌｌ　Ａ　Ｊ，Ｊａｎａｃｅｋ　Ｇ　Ｊ．Ｃｌｕｓｔｅｒｉｎｇ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｆｒｏｍ　ａｒｍａ　ｍｏｄｅｌｓ　ｗｉｔｈ　ｃｌｉｐｐｅｄ　ｄａｔａ　ＩＣ］／／ＡＣＭ　Ｉｎｔｅｍａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｓｅａｔｔｌｅ，２００４：４９—５８．　【４］Ｂｅｒｎｄｔ　Ｄ　Ｊ，Ｃｌｉｆｆｏｒｄ　Ｊ．Ｕｓｉｎｇ　ｄｙｎａｍｉｃ　ｔｉｍｅ　ｗａｒｐｉｎｇ　ｔｏ　ｆｉｎｄ　ｐａｔｔｅｒｎｓ　ｉｎ　ｔｉｍｅ　ｓｅｒｉｅｓ【ｃ］／／ＡＡＡＩ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｍ　ｅＤ，ｉｎ　Ｄａｔａｂａｓｅ，Ｗａｓｈｉｎｇｔｏｎ，ｌ　９９４：３５９—３７０．　［５］Ｃｈｅｎ　Ｌｅｉ，Ｎｇ　Ｒ．Ｏｎ　ｔｈｅ　ｍａｒｒｉａｇｅ　ｏｆ　１１，ｎｏｒｍｓ　ａｎｄ　ｅｄｉｔ　ｄｉｓｔａｎｃｅ［Ｃ］／／　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｄａｔａ　Ｂａｓｅｓ，Ｔｏｒｏｎｔｏ，２００４：　７９２－８０３．　［６］Ｃｈｅｎ　Ｌｅｉ，Ｔａｍｅｒ　Ｏｚｓｕ　Ｍ，Ｏｒｉａ　Ｖ．Ｒｏｂｕｓｔ　ａｎｄ　ｆａｓｔ　ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ　ｆｏｒ　ｍｏｖｉｎｇ　ｏｂｊｅｃｔ　ｔｒａ＿ｊｅｃｔｏｒｉｅｓ［ｃ］，／ＡｃＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎ－　ｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，Ｂａｌｔｉｍｏｒｅ，Ｍａｒｙｌａｎｄ，２００５：４９ｌ一５０２．　【７］Ｇａｕｔａｍ　Ｄａｓ，Ｄｉｍｉｔｒｉｏｓ　Ｇｕｎｏｐｕｌｏｓ，Ｈｅｉｋｋｉ　Ｍａｎｎｉｌａ　Ｆｉｎｄｉｎｇ　ｓｉｍｉｌａｒ　ｔｉｍｅ　ｓｅｒｉｅｓ【ｃ］／／Ｅｕｒｏｐｅａｎ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ｏｆ　Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ，Ｌｏｎｄｏｎ，１９９７：８８—１００．　【８］Ｇａｖｒｉｌｏｖ　Ｍ，Ａｎｇｕｅｌｏｖ　Ｄ，Ｉｎｄｙｋ　Ｐ，ｅｔ　ａ１．Ｍｉｎｉｎｇ　ｔｈｅ　ｓｔ（）ｃｋ　ｍａｒｋｅｔ：　ｗｈｉｃｈ　ｍｅａｓｕｒｅ　ｉｓ　ｂｅｓｔ？［Ｃ］／／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｂｏｓｔｏｎ，２０００：４８７－４９６．　【９］Ｇｏｌｄｉｎ　Ｄ　Ｑ，Ｋａｎｅｌｌａｋｉｓ　Ｐ　Ｃ．Ｏｎ　ｓｉｍｉｌａｒｉｔｙ　ｑｕｅｒｉｅｓ　ｆｏｒ　ｔｉｍｅ—ｓｅｒｉｅｓ　ｄａｔａ：ｃｏｎｓｔｒａｉｎｔ　ｓｐｅｃｉｆｉｃａｔｉｏｎ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ［Ｃ］／／Ｉｎｔｅｍａｆｉｏｎａ］　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ａｎｄ　Ｐｒａｃｔｉｃｅ　ｏｆ　Ｃｏｎｓｔｒａｉｎｔ　Ｐｒｏｇｒａｍｍｉｎｇ，　Ｃａｓｓｉｓ，Ｆｒａｎｃｅ．１９９５：ｌ３７一ｌ５３．　［１０］Ｖａｌｅｒｙ　Ｇｕｒａｌｎｉｋ，Ｊａｉｄｅｅｐ　Ｓｒｉｖａｓｔａｖａ，Ｅｖｅｎｔ　ｄｅｔｅｃｔｉｏｎ　ｆｒｏｍ　ｔｉｍｅ　ｓｅ—　ｒｉｅｓ　ｄａｔａ［Ｃ］／／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖ——　ｃｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｎｅｗ　Ｙｏｒｋ，１９９９：３３—４２．　［１　１］Ｈａｎ　Ｊｉａ—ｗｅｉ，Ｋａｍｂｅｒ　Ｍ，Ｄａｔａ　ｍｉｎｉｎｇ　ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．　ＣＡ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒ，２０００．　［１２］Ｃｈａｋｒａｂａ￣ｉ　Ｋ，Ｋｅｏｇｈ　Ｅ，Ｍｅｈｒｏｔｒａ　Ｓ，ｅｔ　ａ１．Ｌｏｃａｌｌｙ　ａｄａｐｔｉｖｅ　ｄｉｍｅｎ—　ｓｉｏｎａｌｉｔｙ　ｒｅｄｕｃｔｉｏｎ　ｆｏｒ　ｉｎｄｅｘｉｎｇ　ｌａｒｇｅ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｄａｔａｂａｓｅｓ［Ｊ１ｌ　ＡＣＭ　Ｔｒａｎｓ　Ｄａｔａｂａｓｅ　Ｓｙｓｔ，２００２．２７（２）：１８８－２２８．　【１３］Ｌｅｅ　Ｓ　Ｌ，Ｃｈｕｎ　Ｓ　Ｊ，Ｋｉｍ　Ｄ　Ｈ，ｅｔ　ａ１．Ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ　ｆｏｒ　ｍｕｈｉｄｉ～　ｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｓｅｑｕｅｎｃｅｓ【ｃ１，／ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０００：５９９—６０８．　［１４］Ｍｅｇａｌｏｏｉｋ（ｍｏｍｏｕ　Ｖ，Ｗａｎｇ　Ｑ，Ｌｉ　Ｇ，ｅｔ　ａ１．Ａ　ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ　ｓｖｍ—　ｂｏｌｉｃ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｏｆ　ｔｉｍｅ　ｓｅｒｉｅｓ［ＣＪ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２　Ｉ　ｓｔ　Ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：１ＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，２００５：６６８—６７９．　［１５］Ｖｌａｃｈｏｓ　Ｍ，Ｙｕ　Ｐ　Ｓ，Ｃａｓｔｅｌｌｉ　Ｖ．Ｏｎ　ｐｅｒｉｏｄｉｃｉｔｙ　ｄｅｔｅｃｔｉｏｎ　ａｎｄ　ｓｔｕｒｃｔｕｒａｌ　ｐｅｒｉｏｄｉｃ　ｓｉｍｉｌａｒｉｔｙ［Ｃ］／／ＳＩＡＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ，Ｎｅｗｐｏｒｔ　Ｂｅａｃｈ，ＣＡ，２００５