《不确定时间序列的相似性匹配问题研究硕士论文左彦飞》由会员分享，可在线阅读，更多相关《不确定时间序列的相似性匹配问题研究硕士论文左彦飞（56页珍藏版）》请在金锄头文库上搜索。
1、东华大学硕士学位论文不确定时间序列的相似性匹配问题研究姓名：左彦飞申请学位级别：硕士专业：计算机软件与理论指导教师：刘国华2012-02不确定时间序列的相似性匹配问题研究不确定性时间序列的相似性匹配问题研究摘要时间序列，就是按照时间先后顺序排列的记录序列。相似性匹配是时间序列的聚类、异常检测、模式发现等任务的基础操作之一。目前对时间序列相似性匹配的研究主要针对确定性数据，随着物联网、隐私保护等技术的发展，不确定时间序列将大量涌现，时间序列的相似性匹配技术面I 陆新的挑战。在不确定时间序列的情况下，两条序列之间的距离也是不确定的，所以无法直接利用确定性时间序列的相似性匹配方法。为了解决不确定时间
2、序列相似性匹配问题，我们建立了一种描述不确定时间序列的数据模型，在该模型下，不确定时间序列在每一时刻的数据点均由一个取样点( 鼢m p l e0 b S e r v a 舶璐) 的集合组成，并且每个取样点出现的概率相等，即服从离散型均匀分布；并且，时间序列中不同时刻的点相对独立。在此模型下，两条不确定时间序列之间的真实距离是由大量的可能距离( 以一定的概率值出现) 组成的，并且这些可能距离的数量为指数大小。所以，直接计算所有的可能距离的效率将非常低。因此，在所提出模型的基础上，本文提出了两种不确定时间序列相似性匹配算法：口J 职Q ( 均值法) 和纠嘧Q ( 聚类法) 。( 1 ) 口枷Q根据
3、查询序列和数据库中所存储的时序数据是否为确定性数据，将不确定时间序列相似性查询分为三种不同的类型；然后，对于每种类型，通过均值法( a v e m 咖gm I 汕o d ) 从不确定序列中提取出一条确定性序列来代表原序列，然后，采取确定性时间序列相似性匹配方法进行查询。( 2 ) 矗艘Q此算法主要通过两个步骤进行剪枝以降低计算复杂性：1 ) 通过聚类减小取样大小( s a n l p l es i z e ) ，以聚类后的每一个簇为单位计算距离，从而大大降低了计算复杂度。4不确定时间序列的相似性匹配问题研究2 ) 通过预先计算出小于给定阈值8 的距离个数的上界与下界，就能够得到这些距离出现概率
4、的上下界，从而通过概率的上下界过滤掉不必要的计算，减少计算量。实验表明，我们提出的两个不确定时间序列相似性匹配算法具有较好的性能和准确性。关键字：不确定时间序列、不确定数据模型、相似性匹配、概率范围查询、时间序列距离不确定时间序列的相似性匹配问题研究R s e a r c ho nU n c e r t a i nT i m eS e r i e sS i m i l a 哪M a t c h i n gA B S T R A C TAt i m es e r i e si sa q l l c er e c o r d s c o r d i I l gw i t ht l l ec h m
5、 n o l o 百c a lo m e f S i n l i l a r 时m 舢c l l i n gi so 鹏o fm e 眦d e r l 咖go p e m t i o 潞f 0 rt i l I 圮s e r i e sc l 璐t e 】妇g ，o u i e rd e t e 砸o na n dp a t t e md i S c o V e 巧协妇C m 眦y ，s t I l d yo ft i I l l es e r i e ss m l a r i t ym a t c l l i n gm a i n l yf o c u S e so n d e t e 础s
6、 t i c 嘶d e V e l o p m 僦0 f 恤删0 fm 姆a n d 脚a C y硼) t e c t i o nt c c h o l o 鼢硼c e n a i nt i I I l es e I i e s 谢nb ei nl a r j 薛舢n i b e r s 姐d 缅舱s 丽e ss i m i l a r 时m a t d I i n gt h I l o l o g yi sf a C i n gn e wc h a l l e n g e s I nt h ec 嬲eo f1 m 仪眦a i nt i I n es e r i e s ，m ed i s t
7、 a n c eb c 撕e e nt l l et w os e q u e n c e si su n c 嘲i n ，s ot h ew a yo fs 砌l 撕t ) rm a t c h i n go nd e t e 衄埘s t i ct i l n es e r i e sc 锄0 tu 删y I no r d e rt o l V et b ep r o b l 锄o f 珊1 c 涮nt i I I 圮s 甜e ss 砌l a r 姆m 删I 培，w eh l v ee s t a b l i s h e daC I a ：t a 如- 0 d e lt 0d e S c r
8、 i b et 1 1 eu n c 钮讹t i n l e - s e r i e s 1y n d e r 1 i sm o d e l ，也e 蛐p o i n ta te a c ht i m es 1 0 t 、鹪b u i l tu pb y l eS e to fo 鹋s 锄p l eo b s e r v a t i o 璐E h c hs 锄叩l i I l gp o i n th 弱t l l es 锄p r o b a b i l i 够o fo c c u r r e n c e ，t h a ti su n i f o m l yd i 妯b u t 沮a n dd
9、i 妇陆e n tt i m ep o i n t so ft l l e 廿m es 谢e si sr e l 撕V e l ym d 印e n d e n t I nt h i sm o d e l ，廿l e 协坞m s 咖ek 炯e e n 伽ou 1 1 c e r t a i l lt i r s 耐e sa c o n s i s t i l 培o fal a 玛e删m b e ro f p o s s i b l e ( 1 i s 切m e ( w 池ac e f t a i np r o b a b i l 时砌u e ) T h e f 0 陀，o nt l l eb a
10、 S i so f 也em o d e lp l j o p o s e db yt h i sp 币e r ，伽oa l 甾炳t l l m sh a V eb ep r o p o s e df o ru n c e n a i l lt i n l es 耐e ss i n l i l a r i 哆m a t c l l i n g ：口。碾Q ( m e 趾m c 也o d ) a n d七。嚏Q ( c l u s t 盯m e 廿1 0 d ) ( 1 ) 口- 袱QA c c o r d i I l gt 0 也eq u e 巧S e q l 砌ea I l dt i I n
11、es e r i e sd a 组s t o r e di nd a t a b a a r ew 1 1 甜l e rd 醣粕崎s t i c ，T h eu n C 谢n 血【1 i 】唱s e q u 肋c es i I I l i l 鲥晦q u e 巧i sd i v i d e d 缸ot h r d i 伍e 嗍tt ) ，p e s ；T h e 玛f o re a c ht y p e ，b yt 1 1 en l e a I 塔m e t h o d ( a 、r e 】鹆i n gm e m o d )舒缸a c t e d 丘0 mt h e q l l e 】eo f
12、u n c e r t 血1 t ) ro u to fad e 惋加1 i l l i s 6 c q l 橱et 0r e p r e s e n t 廿l eo r i g i n a ls e q l l e 】et a k cn l ed e t c r m i I l i S t i ct i I n e r i e ss i I I l i l a r i 锣m a t 曲I i l l gt l l eq l l e 呼6一至堕室堕塑壁型箜塑篁丝堕堡塑星堡壅一( 2 ) 氏艘Q 嘶sa 1 9 0 喇【l mi s 蛐恤伽班at w o s t e pp n m i n gt
13、or e d u c et 1 1 ec o m l ，u t 撕o n a lc o m e x 时： 1 ) u g h 也ec l u 贻t 0 川u c em es 锄p l es i z e ( s 锄一es i z e ) t 0c a l 砌a t em ed i s t a l 卫c et 0e a C hc h l s l | e r 雄e rc l u 舳g 弱al l I l i t ，也! e 把b yg r l e a u y 他d u c i n g 也ec 伽叩u t 撕伽I a lC o m p l e 】【i 够2 ) P r e c a l 砌a t e d
14、a 百v 锄t h l e s h o l d ，舶mm e 诎ro fu p p 髓锄dl 佣，e rb 0 眦d s ，w e 啪g e t 龇d i s t a n c et 0 雠p 砒a b i l 蚵0 f 恤u p 】p e ra n d 蛔嗽鼬埘删l 时o fm eu p p e ra n dl o w e rb o u n d s ，i tf i l 觚o u tu I l ：c e s s a r yc a l c u l 撕o n S 锄d龇r e d _ u c e 也e c o m p 呦t i o n a l c o m p l c X 诹 1 ke x p e 血
15、嗍n t ss h o wt 1 诅tn 圮t w ou n c e n I i l lt i m es 商e ss i m i l a r i 锣m a t c 艟n ga l g o r i t h mh 嬲b e 廿默p e 娟m 衄n c e 锄d c u r a c y Z u 0 鼬i ( C o m _ p u t e rS o f h a r ea n dT h e o 啪S u p e r v i s e db yL i uQ 1 0 h ：I l al 诬W D R D S ：u n c e f t a i nt i m e 嘶i e s ，u n c e n a j nd a ：t am o d e l ，s i m i l 撕锣m 舢c h i n g ，p m b a b i l i s t i cm g eq u e t i m es e r i e sd i s t a n c e7不确定时间序列的相似性匹配问题研究插图目录图1 1 不同领域的时间序列1 l图1 2 一条不确定时间序列1 3图1 3 不确定数据管理和分析的一般框架1 4图l - 4 一个可能世界样例15图1 5 不确定数据模型示意。1 6图1 6P R o I 算法的数据模型18图2 1 子序列匹配2 1图2 2 时间序列相似性匹配的通用框架
