搜索
上海师范大学硕士学位论文时间序列挖掘和相似性查找技术的研究姓名：唐亮申请学位级别：硕士专业：计算机应用指导教师：张文龙20040420摘要上海师范大学硕士学位论文I摘摘摘摘要要要要时间序列(TimeSeries)是一种重要的数据对象在现实生活中的许多领域中都广泛存在如股票价格商品销售数据气象数据等等随着时间推移这类数据的存储规模呈现爆炸式地增长因此对这些海量的时序数据如何进行有效的知识发现挖掘其内在的各种变化模式对于用户给定具有各种抽象含义的变化模式如何在海量时间序列库中进行相似性的检索等应用分析是一个挑战性的具有重要意义的理论和实际应用课题对于我们正确认识事物变化科学进行决策识别各种异常行为等具有重要的指导意义本文在分析时间序列特点和实际应用需求的基础上针对时间序列的挖掘与相似性查找一些关键技术进行了研究具体包括特征模式挖掘多序列关联模式挖掘相似性模式查找等方面所做的工作和取得的创新成果体现在以下三个方面1时间序列特征模式挖掘研究首次提出了一种基于互关联后继树模型的时序特征模式挖掘方法不同于传统处理模式该方法在序列分段上采用了一种新颖的基于重要点的时间序列线段化算法再符号化过程中采用基于相对斜率的局部符号化方法既减少计算复杂度又避免了噪声的影响在挖掘算法实现上根据序列特征模式的有序性和重复性提出了一种无须生成大量的候选模式集的互关联后继树挖掘算法极大地提高了挖掘效率实验结果表明挖掘结果不仅是一种图形化的描述而且还具有明确的实际含义大大有利于在实际中的应用2多时间序列间关联模式挖掘研究针对更有分析价值的多序列关联模式进一步提出一种新颖的关联模式挖掘方法该方法利用Allen区间逻辑关系来描述时间序列模式的关联关系避免了传统方法在关联关系描述的上非同步性然后通过时间观测窗口来构造出一种包含并行模式和串行模式的特殊形式模式序列最后在此基础上构造一种广义的互关联后继树模型然后用前面挖掘思路实现关联模式的挖掘实验结果显示该新方法比传统的Apriori算法具有更好的挖掘效率和挖掘效果3时间序列相似性查找研究分析比较了根据时间序列与全文序列的异同采用了全文索引技术首次提出了一种基于互关联后继树的时间序列相似性查找方法该方法提出通过基于摘要上海师范大学硕士学位论文II重要点分段技术的分段动态挖掘距离作为相似性度量既保证了度量的鲁棒性又减少计算复杂度利用各个分段的抽取六个主要特征将时间序列转化成一种特定的符号序列在此基础上利用海量全文索引结构实现了相似性的索引查找在理论上证明了该方法不仅保证索引查找的结果不会出现任何错误的丢失而且在实验结果上也显示该方法比传统的方法具有明显的优势关键词关键词关键词关键词时间序列数据挖掘相似性查询互关联后继树模型ABSTRACT上海师范大学硕士学位论文第III页ABSTRACTTimeseriesisakindofimportantdataexistinginalotoffields,suchasstock,weather,etc.Withtimemoving,thisdataoftimeserieswillexplodeincreasing.Soitisimportantandchallengingsubjecttoresearchhowdiscoveryvaluableknowledgeinlarge-scaletimeseriesdatabase,andhowtosearchbasedsimilaritywhileusergiveagraphicquerypattern.Theseresearcheswillhelpustodiscoverchangingordevelopingprincipleofthings,supporttodecision-making,etc.Thethesisaddressesseveralkeytechnicalproblemsofpatternmininganditssearchbasedsimilarityintimeseries,whichcoversfeaturepatternsandrelationshippatternsmining,patternsearchbasedsimilarityintimeseriesandstreamtimeseriesandissuesconcerningapplicationsystemimplementationorientedtoanalysis.Majorcontributionsofthisthesisinclude:1.ResearchofminingfeaturepatternsintimeseriesAnovelmethodisproposedtodiscoveryfrequentpatternfromtimeseries.Differenttoexitingmethods,itfirstsegmentstimeseriesbasedonaseriesofperceptuallyimportantpoints,andthentimeseriesareconvertedintomeaningfulsymbolssequencesintermsofdomainknowledgeandtherelativescopeofeachlinearsegment.Afterthat,wedesignedanewdatamodel,calledInter-RelatedSuccessiveTreesIRST,tofindfrequentpatternsfrommultipletimeserieswithoutgenerationlotsofcandidatepatterns.Experimentillustratesthatthemethodissimplerandmoreflexible,efficientanduseful,comparedwiththepreviousmethods.2.ResearchofMiningRelationshipPatternsinMultipleTimeSeriesAnalgorithmfordiscoveryfrequentpatternsinmultipletimeserieswillbeproposed.Inthisalgorithm,firstlythestatesrelationshipbetweenintimeseriesisrepresentedtoAllentemporallogic,thenuseaslidingwindowstoexaminetheorderoroccurrelationshipofstatesandobtainaparticularlysequence.Onthebasisofthesequence,wedevelopedacalledGIRSTmodeltoachievefindingthefrequentrelationshippatternsinmultipletimeseries.Experimentsshows,comparedwiththepreviousmethods,themethodismoresimple,efficientandmoreappliedvalue.ABSTRACT上海师范大学硕士学位论文第IV页3.ResearchofsimilarsearchintimeseriesAnovelmethodisproposedtofastsearchsimilarpatternintimeseriesusingfulltextindextechnique.Themethodfirstsegmentstimeseriesbasedonaseriesofperceptuallyimportantpoints,usesegmentdynamictimewarpingdistanceasmeasurement,andthentimeseriesareconvertedintomeaningfulsymbolsequencesintermsofthesegment’sfeaturesandMATHcategorization.Afterthat,useaboveindexmodel-IRST,toachievefastsimilarityretrievalinmultipletimeseries.Themethodisprovednotanyfalsedismissinthetheoryandexperimentsshowithasmoreefficientsearchandallowsdifferentlengthsmatching,comparedwiththepreviousmethods.KeywordTimeseries,DataMining,SearchBasedSimilarity,Inter-RelatedSuccessiveTreesIRST第一章绪论上海师范大学硕士学位论文第1页第一章第一章第一章第一章绪论绪论绪论绪论本章一方面阐述本文的研究背景包括时间序列挖掘和相似性查找的基本问题以及目前在这方面的研究现状与已有成果另一方面介绍本文的研究目的研究内容以及组织结构1.1研究背景研究背景研究背景研究背景随着计算机信息系统的日益普及大容量存储技术的发展以及条形码等数据获取技术的广泛应用人们在日常事务处理和科学研究中积累了大量的各种类型的数据在这些保存的数据中其绝大部分都是呈现时间序列类型的数据所谓时间序列类型数据就是按照时间先后顺序排列各个观测记录的数据集[ACD83]时间序列在社会生活中各个领域中都大量广泛存在如金融证券市场中每天的股票价格变化商业零售行业中某项商品每天的销售额气象预报研究中某一地区的每天气温与气压的读数以及在生物医学中某一症状病人在每个时刻的心跳变化等等如图1-1不仅如此时间序列也是反映事物运动发展变化的一种昀常见的图形化描述方式例如在1974年到1989年中对15种具有国际影响的报纸中对其所包含的各种图形进行采样统计结果发现其中至少75%是采用时间序列的图形方式进行描述的[Tuf83]通过曲线打点的方式非常有利于人们在高级层次上来展现和理解事物的变化而且人类早在10世纪前就知道通过可视化时间序列来展现事物的变化发展[Fun73]图1-1几种不同领域的时间序列然而我们应该注意到时间序列不仅是对历史事件的记录展现事物变化的显示方式随着时间推移和时间序列数据的大规模增长如何对这些海量的时间序1股票序列2气压序列3心跳序列第一章绪论上海师范大学硕士学位论文第2页列进行分析处理挖掘其背后蕴涵的价值信息对于我们揭示事物发展变化的内部规律以及不同的事物之间的相互作用关系为人们正确认识事物和科学决策提供依据等等具有重要的实际意义因此有关时间序列分析的研究一直以来就受到了许多研究人员的广泛重视成为一个具有重要理论和实用价值的热点研究课题时间序列分析昀早是传统概率统计学的一个重要研究领域并且经过数十年的研究已奠定了自己的理论基础[PW83][WZZ96]传统的时间序列分析着重研究具有随机性的动态数据研究方法着重于全局模型的构造常用的方法有自回归滑动平均ARMA等[BO93]ARMA方法是一种线性分析方法它要求时间序列必须是平稳的并要求ARMA模型所产生的时间序列与时间观测序列的误差互不相关并呈正态分布而对于绝大多数实际系统所产生的时间序列如股市价格综合指数来说这种平稳性假设以及误差的互不相关性和正态分布往往很难满足此外传统时间序列分析的任务仅仅是为了对系统整体行为的预测而在实际分析中我们需要对时间序列局部特征进行分析如发现经常出现变化模式比较不同序列在某段时间内其运动变化是否相似等等这些分析方法在许多应用领域中同样具有重要的意义例如下面一些典型应用z在整个证券市场中找出股价与1见图1-1相似变化的股票序列再者说给定一个特定时间序列变化模式其长度小于序列1的长度要求从1中与之相匹配的子序列z在气象预报分析中对于