ck ( c_generator ) [1]. ,

《ck ( c_generator ) [1]. ,》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1000-9825/2002/13(03)0410-07©2002JournalofSoftware软件学报Vol.13,No.3非同步多时间序列中频繁模式的发现算法Ã李斌,谭立湘,解光军,李海鹰,庄镇泉(中国科学技术大学电子科学与技术系,安徽合肥230026)E-mail:binli@ustc.edu.cnhttp://www.ustc.edu.cn摘要:从多个时间序列中发现频繁模式在实际应用中具有非常重要的价值.已知文献所提供的方法均假设多时间序列是同步的,但是,在现实世界中,这一条件并不总能满足,许多情况下它们是非同步的.提出了一个从非同步多时间序列中发现频繁模式的算法.该

2、算法首先利用线性化分段表示法和矢量形态聚类实现时间序列的特征分割与符号化转换,然后通过将Agrawal关联模式发现算法的核心思想与时间序列最短实现表示方法相结合,实现了非同步多时间序列中多种结构频繁模式的发掘.与已有算法相比,该算法更简单、更灵活,并且不要求序列严格同步.实验结果证明了该算法的有效性.关键词:数据挖掘;时间序列;频繁模式;最短实现;符号化中图法分类号:TP18文献标识码:A时间序列是现实世界中最常见的数据形式之一,对时间序列进行分析,可以揭示事物运动、变化和发展的内在规律,对于人们正确认识事物并据此作出科学的决策具有重要的现实意义.数据挖掘利用机器学习等方法,从大

3、量历史数据中发现局部的、频繁出现的行为模式,是一种新的、很有前途的时间序列分析方法.在对金融领域的多个时间序列(如各种价格数据和指标数据)进行分析时,经常希望能够发现不同时间序列间可能存在的关联关系,这种关联关系一般表现为不同序列中频繁地同时或依次出现的变化模式.发现这种多时间序列中的频繁结构模式对于人们认识金融系统内在的相互影响并据此作出合理的决策具有重要的参考价值.本文提出了一个从多个时间序列中发现多种结构的频繁模式的数据挖掘算法.该算法首先利用线性化分段和矢量形态聚类方法实现时间序列中基本变化模式的分割与提取,将多个时间序列转换成离散的、非同步的[1][2]多个符号序列;然

4、后利用Agrawal关联模式发现算法的核心思想,结合“最短实现”表示方法,实现了非同步多符号序列中频繁模式的发现.该算法简单、直观,具有较高的实用价值.1相关工作[1]频繁模式的发现研究始于Agrawal提出的关联规则的发现研究,一直是数据挖掘研究中的一个重要课题.在文献[1]中,Agrawal给出了关于频繁模式的一个重要定理,即“任何频繁模式的子模式必定也是频繁的”.由该定理可以得到一个更为实用的推论,即“可以由已知频繁模式集产生更大长度的候选频繁模式”.HeikkiMannila将Agrawal关联规则发现算法的核心思想推广到事件序列,提出了事件序列中频繁情节的Ã收稿日期:2

5、000-06-15;修改日期:2000-09-26基金项目:国家重点基础研究发展规划973资助项目(G1998030413);国家教育部博士点基金资助项目(1999035808)作者简介:李斌(1970－),男,安徽合肥人,博士,讲师,主要研究领域为数据挖掘,神经网络,遗传算法;谭立湘(1970－),女,山东青岛人,讲师,主要研究领域为数据库,数据通信,多媒体;解光军(1970－),男,安徽合肥人,博士生,讲师,主要研究领域为神经网络,量子计算;李海鹰(1968－),男,安徽合肥人,博士生,讲师,主要研究领域为神经网络,电子商务;庄镇泉(1938－),男,福建泉州人,教授,博士生

6、导师,主要研究领域为智能信息处理.李斌等:非同步多时间序列中频繁模式的发现算法411[3]发现算法,事件序列可看作是一种离散的时间序列.[4]TimOates等人提出了从多个数据流中搜索关联模式的数据挖掘算法(MSDD),其中,多数据流表示为严格同步的多个符号序列.Oates等人给出了候选模式的产生和强关联模式的启发式搜索算法,但该算法要求数据序列必须是严格同步的.与Oates的挖掘算法相比,本文提出的从多个时间序列中发现频繁结构模式的挖掘算法对不同序列间是否同步没有限制,并且能够发现多种结构形式的频繁模式,具有更大的灵活性和较低的计算复杂度.2时间序列的符号化转换本文研究从时间

7、序列中发现各种频繁出现的结构模式,而以连续数值形式表示的时间序列不便于描述和计算,为此,需要将以数值形式表达的时间序列转换成以离散的、相对抽象的符号表示的符号序列.以后的挖掘算法都要在这个符号序列上展开,最后发现规则的有效性在很大程度上取决于符号表达的有效性.因此,我们希望在作符号化转换时所形成的符号种类数不要太多,每一个符号都尽可能代表一种基本的、相对独立的变化模式.我们称这种模式为“元模式”,它是构成模式及规则表达式的基本元素.[5]本文采用了一种基于线性化分段和矢量形态聚类