时间序列的快速相似性搜索改进算法

用技术　太原科技２０１０年第３期可　０　凹凰阅　Ｓ＠０—可匡＠　黪霉鍪餮鞣豢霉毒巷毳囊鏊囊囊穗　疆甏繇赣毽《囊毫鼍毯强誊琵罄ｌ　§ｌ毫馥疆｜§　鼋罄强ｌ魏ｇ　毯饕《繇ｌ　ｌ｜臻《鏊薯　。　一。　曩薯≯ｌ臻魏蕾Ｉ　｜≯１％　文章编号：１００６－－４８７７（２０１０）０３—００９０—０２　时闻赢　缺　镓　索改进　冰　刘利松，闫光辉，黄成，杨霞霞　（兰州交通大学电子与信息工程学院，甘肃兰州７３００７０）　摘要：针对时序数据进行相似性挖掘方法的研究，提出一种寻找已知序列的所有相似性子序列的方法，用该方法　对数据模拟．结果表明该算法提高了查询性能。　关键词：相似性挖掘：时间序列：数据挖掘　中图分类号：Ｏ２１１　文献标志码：Ａ　时间序列是指按时间顺序排列的一种数据，在　Ｄ（Ａ，　）＝　“时间序列”这一学科所研究的范围内，广义地指　三　组有序的随机数据【”。一般来说，时间序列的相似性　Ａ　Ｗｉ＊ＢＷ　Ｉ（　厶－Ａ　ＹＲ　）－（ＢＹＬｉ－ＢＹＲ　）Ｉ．　ｉ＝１　搜索可以分为两类：全序列搜索和子序列搜索闭。　１．２时间序列分段线性表示　在判定两时序的相似度上还会遇到一些问题，　时间序列分段线性表示（ＰＬＲ）是将时间序列　如高频噪声、时间轴上伸缩等，对于这些问题已提　数据基于时间表示成多段相邻的近似直线。在数据　出很多算法．如离散傅立叶变换四，离散小波变　挖掘领域，ＰＬＲ表示已经在下面一些领域得到应　换　，滑动平均聚集近似方法同等。笔者引用时间序　用：一是支持快速相似性搜索；二是支持时间序列　列分段表示思想，以某省电力公司ＥＲＰ系统业务量　新的距离度量。包括模糊查找、加权序列、ＤＴＷ距　统计数据为研究对象，提出一种快速相似性搜索的　离、信息反馈等；三是支持文本和数据序列。　优化算法。　２算法描述　１　时间序列相似性度量　２．１　ｓ７算法及其改进算法　相似性度量是衡量两个序列相似性的依据，是　基本搜素算法的本质就是搜索时序Ｑ沿着被搜　相似性查找的基础。下面分别从时间序列距离度量　索时序Ｒ滑动，当Ｑ与尺中子序列相匹配时计算　和时间序列分段表示来介绍。　其相似距离。Ｅａｍｏｎｎ　Ｋｅｏｇｈ曾提出的Ｓ７算法，有　１．１时间序列距离度量　效地解决了效率和时间轴方向的伸缩问题。但是，　１．１。１欧式类距离　ｓ７算法的执行效率较低，大部分时间都在构造表，　给定两个时间序列，　（Ｉ　ｌ＝　），Ｙ（Ｉ　ｌ，Ｉ＝ｍ），当　因此．王晓哗等人在其基础上提出了计算两个不等　／．ｔ￣－ｍ的，它们之问的Ｅｕｃｌｉｄｅａｎ距离定义为　长序列相似性算法，但该算法在排列组合时间序列　厂　————一　倾角上花费了大量时间，为此笔者在降低此算法的　Ｅ（Ｘ，Ｙ）＝、／∑（Ｖ　ｉ＝１　ｘｉ－ｙｉ）　．　时间复杂度方面作了一些研究，提出了一种快速搜　１．１．２　ＰＬＲ常用距离　索算法。　一个时间序列，将其线性分割为　段，用大　２．２快速搜索算法　写字母Ａ来表示：Ａ＝ｆＡＸＬ，ＡＸＲ，ＡＹＬ，ＡＹＲ，　输入数据。时间序列５。和５：，伸长和收缩范围　Ａ　｝。对于第ｉ段Ａ　，Ａ　＝（Ａ　厶，ＡＸＲ　，ＡＹＬ　，　ｓ　０，相似性距离　０。　ＡＹＲ　，ＡＷ　）分别为第ｉ段的起点横坐标，起点纵　输出数据。若相似，则输出相似子序列的起始　坐标，终点横坐标，终点纵坐标，第　段的权重。　点和相似性距离。　则距离Ｄ（Ａ．　定义为　算法描述。步骤１：比较Ｓ　和Ｓ：的长度，较长　【基金项目１兰州市科技计划项目（６０８７３１９６）　收稿日期：２０１０—０１—０５；修回日期：２０１０—０２—０６　作者简介：刘利松（１９８５一），男，陕西成阳人，在读硕士，主要从事数据挖掘研究，Ｅ－ｍａｉｌ：ｌｉｓｏｎｇ＿ｌｉｕ＠１６３．ｃｏｒｎ。　・９Ｄ・　应用技　太原科技　２０１　０年第３期　凰Ｄ　凰　圆＠０—　匡＠嗍　鬻　≯｜　冀∞｝ｌ　§蠹§謦　ｌ一一羹毒。一鼍％ｌ§　疆琵　§　壤　露譬｜　整誊蕾ｌ曩嚣ｌ巷ｇｌ整§鏊罄　｜謦　ｌ甏　的标记为　（长度为　），较短的标记为Ｑ（长度　为Ⅳ）；Ｒ和Ｑ的倾角相应地标记为ｒ和ｑ。步骤　２：标记出Ｑ两端的端点位置，左端子段记作　，　右端子段记作　，计算尺　和尺　的时间差，当两　表１中Ｃ１，Ｃ２，Ｃ３，Ｃ４，Ｃ５指该电力公司下　属的５家公司，由表１可以看出，Ｃ２和Ｃ３的业务　统计数据和ｃｌ相似，ｃ４与ｃ５相似。由于Ｃ１和　ｃ２这两个公司的业务发生时间及业务量的起伏相　似．可以认为其在人力资源管理上的管理方式也是　者的时间差刚好等于Ⅳ时，记录此子时间序列为　Ｒ　。步骤３：计算最大伸长和收缩角　和　，基　于以下公式：０　＝　一　，　＝Ｏ－ｅ；标记其为　（ｇ　，ｇ　一）和（９Ｒ　，ｇＲ～）。将　中满足此范　围的记作　。步骤４：计算Ｑ和Ｒ　的相似性距　类似的。这样，当其中一家公司改进业务管理方　法．就可以被与其他相似的公司所借鉴。　４结束语　对时间序列数据挖掘的研究越来越受到重视，　其在金融分析和科学实验分析等方面的应用也越来　越广泛。笔者基于Ｓ７算法的思想，对时间序列的　相似性搜索算法提出改进，克服了以前此类方法在　时问复杂度上的不足，实验过程中表现比较好的　性能　参考文献：　［１】杨叔子，吴雅．时间序列分析的工程应用【Ｍ【．武汉：华中理　工大学出版社，１９９１．　【２］　Ｆａｌｏｕｔｓｏｓ　Ｃ，Ｒａｎｇａｎａｔｈａｎ　Ｍ，Ｍａｎｏｌｏｐｏｕｌｏｓ　Ｙ．Ｆａｓｔ　Ｓｕｂｓｅ—　ｑｕｅｎｃｅ　Ｍａｔｃｈｉｎｇ　ｉｎ　Ｔｉｍｅ　Ｓｅｒｉｅｓ　Ｄａｔａｂａｓｅｓ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆＡＣＭ　ＳＩＧＭ０Ｄ．１　９９４．　离，如果相似性距离小于　，则输出Ｄ及Ｒ中Ｒ　的起点．否则输出“ＮＵＬＬ”。算法示意图见图１。　图１　时序Ｑ沿　滑动　３应用实例　以某省电力公司下属各供电及超高压公司ＥＲＰ　系统的人力资源模块维护员工工资业务的业务量统　计数据为例，使用ＡＢＡＰ开发平台，采用本文提出　的算法进行相似性搜索数据挖掘。该实验中记录业　务量数据４８２个，经分段处理，划分成３１个子段，　所有子段直线的倾斜角集合为尺；搜索时序Ｑ有５　［３】　Ａｇｒａｗａｌ　Ｒ，Ｆａｌｏｕｔｓｏｓ　Ｃ，Ｓｗａｍｉａ．Ｅｆｉｆｃｉｅｎｔ　ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ　ｉｎ　ｓｅｑｕｅｎｃｅ　ｄａｔａｂａｓｅｓ【Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　４ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｄａｔａ　Ｏｒｇａｎｉｚａ——ｔｉｏｎ　ａｎｄ　Ａｌｇｏｒｉｔｈｍｓ．Ｂｅｒｌｉｎ：Ｓｐ　ｒｉｎｇｅｒ２Ｖｅｒｌａｇ，１９９３：６９—８４．　【４】　Ｃｈａｋｒａｂａｒｔｉ　Ｋ，Ｏｒｔｅｇａ—Ｂｉｎｄｅｒｂｅｒｇｅｒ　Ｍ，Ｐｏｒｋａｅｗ　Ｋ，ｅｔ　ａ１．　Ｓｉｍｉｌａｒ　Ｓｈａｐｅ　Ｒｅｔｉｒｅｖａｌ　ｉｎ　ＭＡＲＳ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｕｌｉｍｅｄｉａ　ａｎｄ　Ｅｘｐｏ．ｔ　个子段，直线倾斜角集合为Ｑ。设占＝３，　＝５，实　验结果见表１。　表１相似性计算结果　公式编号　Ｃ１　Ｃ２　Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２０００：７０９—７１２．　Ｃ２　２．１２　Ｃ３　４．４３　３．２７　ｃ４　ｎｕＵ　ｎｕｌｌ　Ｃ５　ｎｕｌｌ　ｎＨ１１　［５５１　ＹｉｂＫ，ＦａｌｏｕｔｓｏｓＣ．ＦａｓｔＴｉｍｅ　ＳｅｑｕｅｎｃｅＩｎｄｅｘｉｎｇｆｏｒＡｒｂｉ—　ｔｒａｒｙ　ＬＰ　Ｎｏｒｍｓ【ｃ】／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２６ｔｈ　Ｉｎｔｅｎａｒｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｄａｔａｂａｓｅｓ（ＶＬＤＢ）．Ｃａｉｒｏ，Ｅｇｙｐｔ：　Ｍｏｒｇａｎ　Ｋａｕｆｉ￣ａａｎｎ，２０００：３８５－３９４．　Ｃ３　Ｃ４　ｎｕｕ　ｎｕｌｌ　４　５１　（责任编辑张怀琴）　Ｉｍｐｒｏｖｅｄ　Ａｌｇｏｒｉｔｈｍ　ｏｆ　Ｆａｓｔ　Ｓｉｍｉｌａｒｉｔｙ　Ｓｅａｒｃｈ　ｏｆ　Ｔｉｍｅ　Ｓｅｒｉｅｓ　Ｌｉｕ　Ｌｉ－ｓｏｎｇ，Ｙａｎ　Ｇｕａｎｇ－ｈｕｉ，Ｈｕａｎｇ　Ｃｈｅｎｇ，Ｙａｎｇ　Ｘｉａ－ｘｉａ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ，Ｌａｎｚｈｏｕ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００７０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｏ　ｄｉｒｅｃｔ　ｒｅｓｅａｒｃｈ　ｏｆ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｄａｔａ　ｕｓｉｎｇ　ｍｅｔｈｏｄ　ｏｆ　ｓｉｍｉｌａｒ　ｍｉｎｉｎｇ，ｔｈｅ　ａｕｔｈｏｒｓ　ｐｕｔ　ｆｏｒ－　ｗａｒｄ　ａ　ｍｅｔｈｏｄ　ｏｆ　ｓｉｍｉｌａｒ　ｓｕｂｓｅｑｕｅｎｃｅ　ｏｆ　ｇｉｖｅｎ　ｓｅｑｕｅｎｃｅ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｉｎｄｉｃａｔｅｄ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｍｐｒｏｖｅｄ　ｑｕｅｒｙ　ｐｅｒｆｏｒｍａｎｃｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｉｍｉｌａｒ　ｍｉｎｉｎｇ；ｔｉｍｅ　ｓｅｒｉｅｓ；ｄａｔａ　ｍｉｎｉｎｇ　・９　・