（计算机应用技术专业论文）基于多媒体空间数据库的时变模式挖掘.pdf

四川大学硕士学位论文 基于多媒体空间数据库的时变模式挖掘 计算机应用技术专业 研究生孙茜指导老师唐常杰 含有多媒体对象的时空间数据库的挖掘是一个应用前景广阔的重要课题。 研究者已经提出了许多关于时间、空间数据挖掘的技术和方法，尽管取得了令 人振奋的成果，但时空数据的挖掘还不能满足日益增长的需求。已有的方法 能很好地表达出对象之间的空闻关系和指定时段上复杂对象的空间关系的变化 模式。 本文提出了可以有效的挖掘出多媒体数据库中对象之间的空间模式的新方 法。主要工作包括： ( 1 ) 对空间多媒体对象，赋予对象坐标，从而计算出多媒体对象之间的空 间关系和方向关系，例如东北方、东南方、西北方、西南方等空间关系。 ( 2 ) 给多媒体数据对象加上了时态，对多个时段，分别挖掘每个时段的空 间模式。 ( 3 ) 研究了多媒体空间对象随时间变化的规律，提出了发现这种模式变化 的方法。 ( 4 ) 做了详细的实验和性能分析，比较了多种在不同的环境下的性能指标。 关键词：数据挖掘，多媒体数据库，空间模式，模式变化，频繁项集 四川大学硕士学位论文 m i n i n gt e m p o r a l p a t t e r n i ns p a t i a lm u l t i m e d i ad a t a b a s e s c o m p u t e ra p p l i c a t i o nm a j o r g r a d u a t es u nq i a n s u p e r v i s o rt a n gc h a n g j i e a b s t r a c tm i n i n gt e m p o r a l - s p a t i a ld a t a b a s ec o n t a i n i n gm u l t i m e d i ao b j e c t si s 缸 i m p o r t a n tr e s e a c hd k e e f i o nw i t hw i d ea p p l i c a t i o np r o s p e c t i o n m a n yt e c h n i q u e s a n dm e t h o d sf o rt e m p o r a ld a t am i n i n ga n ds p a t i a ld a t am i n i n gh a v eb e e np r o p o s e d a l t h o u g h ，i tg e t sa ne n c o u r a g i n ga c h i e v e m e n t , t h ec u r r e n tt e c h n i q u e sf o rm i n i n g t e m p o r a l - s p a t i a ld a t a n tm e e tt h ei n c r e a s i n gd e m a n d s t h ee x i s t i n gn a m n g m e t h o d sc a nn o tg i v ep e r f e c te x p r e s s i o nt os p a t i a lr e l a t i o n s h i p sa m o n go b j e c t sa n d d on o tc o n s i d e rt h et e m p o r a lc h a n g e so ft h es p a t i a lp a r e m si ns p e c i f i ct i m e i n t e r v a l t h i sp a p e r p r o p o s e sa ne f f e c t i v em e t h o dt od i s c o v e r yo fs p a t i a lp a t t e r n s a m o n g o b e c t si nm u l t i m e d i ad a t a b a s e s t h em a i nc o n t r i b u t i o n si n c l u d ： 1 g i v e sac o o r d i n a t et o e a c hs p a t i a lm u l t i m e d i ao b j e c ta n df i n d st h es p a t i a l r e l a t i o n s h i p sa n dd i r e c t i o n a lr e l a t i o n s h i p sa m o n gm u l t i m e d i ao b j e c t ss u c h a st h en o r t h e a s t ，s o u t h e a s t ，n o r t h w e s t ，a n ds o u t h w e s t , e t c 2 i n t r o d u c e st e m p o r a lc o n c e p tt os p a t i a lp a t t e r n si nm u l t i m e d i ad a t a b a s e s m i n i n gt h es p a t i a lp a r e m so f e a c ht i m ei n t e r v a l 3 r e s e a r c h e st h ev a r i a t i o n so fs p a t i a lr e l a t i o n s h i p sa m o n gm u l t i m e d i a o b j e c t sw i t ht h ev a r i a t i o na l o n gt i m e ，p r o p o s e sa ue f f e c t i v em e t h o d t of i n d t h et e m p o r a lv a r i a t i o n si ns p a t i a lp a t t e r n s 4 g i v e se x t e n s i v ee x p e r i m e n t sa n dp e r f o r m a n c es t u d y c o m p a r e st h e p e r f o r m a n c ei n d i f f e r e n t s y s t e mc o n d i t i o n s t h ep r o p o s e dm e t h o d i s s h o w nt od e l i v e re x c e l l e n tp e r f o r m a n c eu n d e rd i f f e r e n ts y s t e mc o n d i t i o n s k e yw o r d s ：d a t am i n i n g , m u l t i m e d i ad a t a b a s e ，s p a t i a lp a t t e r n , p a t t e r n c h a n g e ，f r e q u e n ti t e m s e t 四川大学硕士学位论文 关于论文使用授权的说明 本学位论文作者完全了解四川大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权四川大学可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学 位论文。 签名：盆整 导师签名： 日期：j 印1 年l f 月日 四川大学硕士学位论文 独创性声明 本人声明所星交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他入已经发表或撰写过的研究成果，也不包含为获得四川大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 作 四川大学硕士学位论文 第一章引言 1 1 研究背景 数据挖掘( d a t am i n i n g ) 技术目前在许多领域都有了研究与应用，早期的关 联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) l l 】针对市场上的交易，近年来关联规则挖掘 已经应用在许多其他的领域上。在相关性研究【3 】中，探讨客户的交易行为。例 如，可挖掘出关于客户行为的连续模式( s e q u e n t i a lp a t t e r n ) ，推测出某些客户买 了某一件商品后，紧接着会买么商品，从而获得商业利益。近年来，多媒体 数据大量增加，多媒体相关的数据挖掘得到研究者的重视，多媒体数据分析技 术也日益成熟【8 1 【1 3 】【1 5 】，用传统的统计学来分析多媒体对象，其描述能力比较弱， 难以发现某些有趣的信息，在一些特殊的领域中，对多媒体数据的挖掘提出了 更高的需求【7 】【2 2 1 。多媒体挖掘技术得到了研究者和开发者的重视，提出了多种 多媒体挖掘技术1 9 1 1 0 f f l 6 【1 7 】【1 8 】【2 0 】【2 ”。文献【1 6 1 1 7 1 研究了多媒体数据挖掘的特点， 设计了m u l t i m e d i a m i n e r 工具，可以从多媒体数据库中挖掘有用的信息，包括摘 要、分类、和关系等。 1 2 研究动机 o rz a i a n e 探讨了多媒体数据中对象之问的空间关系 1 7 1 ，提出将每一张 i m a g e 当作是一个事务( t r a n s a c t i o n ) ，从i m a g e 中所获取出的对象( o b j e c t s ) 当 作是组成事务的项( i t e m s ) 。o r z a i a n e 首先找出最常出现的对象，并且发掘 这些对象之间的关联规则，提出了具有空间关系的关联规则，指出对象的四种 空间关系： 1 h - n e x t - t o ：h - n e x t - t o ( 0 1 ，0 2 ) 代表d l 与d 2 的空间关系是水平的。 2 v n e x t - t o ：v - n e x t - t o ( o l ，0 2 ) 代表d i 与d 2 的空间关系是垂直的。 3 o v e r l a p ：o v e r l a p ( d l ，d 2 ) 代表q 与0 2 的空间关系是被覆盖到的。 4 i n c l u d e ：i n c l u d e ( o l ，0 2 ) 代表0 1 与0 2 的空间关系是0 1 包含。2 。 从上述四种空间关系中可以找出下面的关联规则： h - n e x t - t o ( 0 l ，0 2 ) a v - n e x t - t o ( d 3 ，0 4 ) o v e r l a p ( o l ，d 4 ) a 我们在实践中，观察到多媒体对象之间的更为细致的空间关系。本文给每 一个对象一个坐标，用坐标可以看出对象与对象之间的方向关系，并将方向 l 婴型查堂翌主! 丝堡奎 关系分为四种：东北方( n e ) 、东南方( s e ) 、西北方州w ) 、西南方( s w ) 。用本文 所提出的挖掘方法可产生的规则形如： a 0 2 ( n e ) j0 3 ( s e ) 亦即d 2 会出现在d 1 的东北方，紧接着d 3 也会出现在q 的东南方，本文把表示 的方法简化为 ，称之为空间模式( s p a t i a lp a t t e r n s ) 。 本文还探讨了时态多媒体数据库，挖掘出在每一个段时间内的空间模式， 并观察时段间空间模式的变化，形如： j 并称之为模式变化( p a t t e r nc h a n g e s ) 。 1 3 问题描述 对多媒体数据，划分成四个时段，每一个时段，都是由多媒体文件所组成 的。可以用已知的方法【8 】【1 3 l 【1 5 1 获取出多媒体文件中的对象，因此本文假定多媒 体数据库中的每一个文件都是由对象所组成的。 文献【1 5 1 1 6 】牛- 提出将每一张h a g e 当作是一个事务，从i m a g e q b 所获取出的对 象当作是事务的项，因此利用a p r i 嘶算法【2 】可以找出频繁项集( f r e q u e n ti t e m s e t ) 。 本文将一个多媒体数据当作一个事务，从数据中所获取出来的对象当作是事务 的项，这样，本文考虑的多媒体数据库就是由项所组成的一个一个的事务，再 由这些事务所组成的数据库。特别要说明的是，在本文的数据库中，有时间的 区段，每一个时间区段都包含一些事务。 在上述数据集合的基础上，本文将探讨下两个问题： 在指定时段中，对象之间存在有何种有趣味的空间关系? 在一个时段和此时段的下一个时段对象可能发生了改变，对象之间的 空间关系可能改变或消失，而这些改变将伴随着哪些有趣的信息? 这 些变化有何规律? 1 4 研究方法 本文讨论的对象是时态多媒体数据对象。本文用了两种方法研究。 1 找出数据库中各时段的空间模式，用本文提出的s p a t i a lp a t t e r n sm i l l 盯 算法，缩写为s p m i n e r g 法来完成。 ( a ) 、收集相同性质的多媒体数据，用已知的多媒体数据获取技术，将每 2 四川大学硕士学位论文 一个多媒体数据中的对象获取出来，组成本文所需的对象化的多媒体数据库 ( d ) ，数据库中的所有对象集合为o ，0 = o l ，0 2 ，q ) 。 ( b ) 、将每一个多媒体文件当作一个事务( t r a s a e t i o n ) ，以m 来表示， t = d l ，d 2 ，d ， 。由于数据库具有时段性，一个时段以t 来表示，例如本文 以一年为一个时段，收集五年中川大的照片，观察川大照片每年的空间模式。 ( c ) 、获取的对象，用x 、y 坐标来表示其位置，如图l - l 所示，o 的坐标以 ( 五，x ) 来表示，则( 五，r 0 = ( 7 5 , 4 5 ) 。在数据库中，用 来表示，所 以o l 的表示法为 。 ( 0 ，o ) 一x 图l t 对象空间关系坐标表示圈 ( d ) 、定义了四种空间关系，分别如下： 1 西北方0 叮w ) ：如图1 - i ，0 3 位于d 的西北方。 2 东北方烈e ) ：如图1 1 ，d 2 位于q 的东北方。 3 东南方( s e ) ：如图l 一1 ，d 位于q 的东南方。 4 西南方( s 9 0 ：如图1 - 1 ，d l 位于d 3 的西南方。 ( e ) 、设定最小支持度( m i n i m u ms u p p o r t ) ，每一个模式p 的支持度p a s u p ( p ) 来 表示，若po 且pm i ，则 婴型盔兰堡主兰竺堡苎 跏( p ) ：i m , p - c m 1 t a r n d 1 i 2 厶，厶) 2 厶，厶 1 厶，厶) 2 厶，厶)0 在表2 4 中，删除支持度小于2 的项集，剩下的项集构成厶，如表2 5 所示。 表2 - 5a p d o r i 算法：产生厶 项集支持度计数 ，l ) 2 l ，厶 3 ，厶 2 厶，厶 2 l1 2 ：! ! 接着产生c 3 如表2 - 6 所示。再删除支持度小于2 的项集之后，只剩下 l ，厶，厶) ，如表2 7 所示，无法再组合c ，所以a p r i 硪算法到此就结束了。 1 0 四川大学硕士学位论文 墨：! 垒! ：! ! ：! 簦生! 兰竺曼 项集支持度计数 ，l ，毛 1 ，厶，厶 1 ，l ，厶，厶， 1 厶，厶，厶) 1 厶，l ，厶 2 l ! ；：! ：! 21 型塑咝：主生刍 项集支持度计数 2 2 多媒体挖掘技术 多媒体挖掘技术现在已经得到了广泛的研究，文献【1 6 】【1 7 1 研究了多媒体数据 的特性，设计出m u l t i m e d i am i n e r t 具，针对多媒体数据库做挖掘，找出各种有 用的信息，包括摘要、分类、和关系等。文献8 b 3 l 【1 5 】提出了将每一张i m a g e 当作 是一个事务，从i m a g e q ，所获取出的对象当作是项，他们找出一个数据库中的频 繁项集，而其探讨的空间关系是两两对象之间的空间关系，以这一种关系为基 础，再来找出关联规则，如：i n c l u d e ( d l ，d 2 ) j o v e r l a p ( q ，0 4 ) 。本文的目的 只是这种关系，而是融合了时间属性的对象与对象之间的空问关系。 2 2 1 多媒体关联规则( m u l t i m e d i aa s s o c i a t i o nr u l e s ) 文献1 9 1 对多媒体关联规则的挖掘提出了一个m a x o c c u r 算法，如图2 4 所示。 四川大学硕士学位论文 b e g i n ( 1 ) 仍扣 c a n d i d a t el i t e m s e t sa n dt h e i r8 伽矽d 付 ( 2 ) f 1 4 - - ( s u f f i c i e n t l yf r e q u e n t1i t e m - s e t sa n dt h e i r 暑猢删】 ( 3 ) m 七_ m a x i m u m o c c t t r r e 1 1 c ei na ni m a g eo ff r e q u e n tli t e m - s e t s ) ( 4 ) c o u n t 稃o f k - i t e m - s e t s ( t o t a l 1 。明) 【5 ) f o r “+ - - 2 ；最一l 晚e 一t + 1 ) d o ( ( 6 )aj e - - ( 曩一1 阁曩一1 ) u 妇oxix r 一1a 掣f lac o u n * ( y ，x ) 扩， ( 1 5 ) ， ( 1 6 ) r e s u i t 扣u i 。毋ii l ac - s u p p o r t 厶 0 9 ，o i 。) 0 3 先扫描数据库一次，执步骤1 4 ，计算出每个对象出现的次数，如：0 6 出现在、厶、厶、与厶中，出现3 次，厶出现2 次，厶出现1 次，5 出现2 次， 所以d 6 的s u p p o r t = 8 ，n - 张i m a g e ，出现最大的次数是3 ，依此类推，结果如 表2 - 9 所示。 四川大学硕士学位论文 塞至! 兰竺竺堂鎏：主生9 皇翌塞 q 竖! 壁曼婴墼壁坚竺：q 竺坚婴塑 接着，将支持度小于o 。的给删除，得到如表2 1 0 的结果。 墨! ：! ! 竺竺竺墨鎏：主生互皇! 堡 q 堑! 璺曼些塑壁! ! 竺：竺! ! 竺竺望 0 6 q 8 6 3 2 接着简化整个数据库d l ，简化结果如表2 - “所示，每张i m a g e 只保留我们 所感兴趣的对象。 1 4 i 1 l i l t ，l 1 、l l l l 1 1 o o l 1 6 口侥伤班以侥凸防凸 四川大学硕士学位论文 耋：! ! 茎堡亘竺里竺茎垄壁垒 i m a g ei do b j e c t s d 6 ，d 6 ，d ) l d 6 ，d 6 ，d 9 ，d 9 ，q 。) 厶 d 6 ) l 0 9 ) 厶 d 6 ，d 6 ，q ，q ! ! 里l ：9 21 得到曩与m 之后，进入步骤5 的循环，首先要产生候选2 项集c ，利用e 的结果，来组合出所有可能的组合，如表2 一1 2 所示，在组合成c ，时，会考虑到 对象的最大出现次数m a x o c c u r r e n c e ，例如：织的m a x o c c u r r e n c e = 3 ，表示同 一张i m a g e 中，最多会有3 个d 6 ，所以在组成c 2 时，会有 d 6 ，0 6 ) 这种组合。表 2 1 2 中，前面的- - = n 组合方式与a p r i o d 算法相似，而后面的两列则是考虑了m a x o c c u r r e n c e 而得来的。 c 2 产生之后，必须计算每一个项集的支持度，例如： q ，q ) 这个项集， 要计算d 6 与d 9 同时出现在哪些i m a g e s q 。，由表2 1 1 的d 2 中发现，d 6 与q 同时 出现在l 与厶，所以 d 6 ，d 9 ) 的支持度为2 ，再考察项集 0 6 ，0 6 ) ，- - g k i m a g e 必须包含有两个0 6 ，其意义与 0 6 ，0 9 相同，必须要计算仗与0 6 同时出现在哪 些i m a g e s 中，由表2 - 1 1 的d 2 中发现，同时包含有两个0 6 的i m a g e 有五、厶与厶， 所以支持度为3 。计算完所有的项集的支持度，其结果如表2 1 2 所示。 墨：! ! ! 竺竺! 竺生鎏：主兰曼 o b j e c ts u p p o r t d 6 ，d l 。 1 d 6 ，0 9 2 d 9 ，q 。 2 0 6 ，仗， 3 0 9 ，0 9 2 璺型查堂堡主兰垡笙苎 接着产生频繁2 - 项集最，因为项集 0 6 ，d l 。) 的支持度小于o ，所以被删除， 其结果如表2 1 3 所示。 塞三! ! 坚竺竺竺兰鎏：主兰墨 o b j e c ts u p p o r t ， 0 6 ，q ) 2 0 9 ，0 1 。) 2 d 6 ，0 6 3 f 鱼! ：! i21 如此重复的产生候选k - 项集q 和频繁k - 项集e ，其结果分别如表2 1 4 、表 2 1 5 、表2 1 6 与表2 1 7 所示。 塞：! 生! ! ! ：竺! 坚鎏：主生刍 o b j e c ts u p p o r t d 9 ，0 9 ，0 1 。) 1 伉，d 6 ，q ) 2 0 6 ，d 9 ，0 9 ) 2 d 6 ，0 9 ，0 1 。) 1 l 量l ：受i ：鱼l ! ! 耋：! ! 坚竺! ! 竺竺鲨：主生墨 q 堕! 竺釜婴堕 d 6 ，0 0 ，0 9 ) 2 i 垡：g ：垒!1 1 6 四川大学硕士学位论文 考察多媒体关联规则。给定一个m i n i l l l u mc o n f i d e n c e = 1 0 0 ，可以产生如下 的多媒体关联规则： d 9 ，d 9 ) j d 6 ，0 6 ) 【1 0 0 】 d 6 ，0 9 ，q ) j d 6 h 1 0 0 】 d 6 ，d 6 j 岛) 1 0 0 1 d 9 ，d 9 ) j d 6 【1 0 0 吲 0 6 j 0 9 ) 1 0 0 】 2 2 2 空间关系 文献【1 9 】除了找出多媒体关联规则之外，还找出了它们之间的空间关系 ( s p a t i a lr e l a t i o n s h i p s ) ，再以一个空间关系当作一个项，找出空间关系之间的关 系，称之为具有空间关系的多媒体关联规则，图2 5 为相关研究19 1 中所提出的 m i n i n gm u l t i m e d i as p a t i a l 算法，缩写为m m s p a t i a l 算法。 图2 5 算法2 - - 4 ：m m - s p a t i a l 算法 上述算法与m a x o c c u r 舅t 法相似，输入有下列三种： 一个有空间关系的数据库d i ，每一张妇a g e 代表一个事务，而由i i n a g e s 1 7 四川大学硕士学位论文 中所获取出来的对象，当作是项集。 每一层属性的集合。 m i n i m u ms u p p o r t o 和i l l a x i m u l ns u p p o r t x 。 输出：f r e q u e n ts p a t i a lp r e d i c a t ec o n j u n c t i o n s 在相关研究中【1 9 1 举出了对象之间的空间关系有下列四种： i 、h - n e x t - t o ：h - n e x b t o ( q ，0 2 ) 代表q 与q 的空间关系是水平的。 2 、v - n e x t - t o ：v - n e x t - t o ( 0 i ，0 2 ) 代表d l 与d 2 的空间关系是垂直的。 3 、o v e r l a p ：o v e r l a p ( 0 1 ，0 2 ) 代表0 l 与d 2 的空间关系是有覆盖到的。 4 、i n c l u d e ：i n c l u d e ( q ，0 2 ) 代表0 1 与0 2 的空间关系是0 1 包含q 。 由图2 6 可以看出每种空间关系的情况。 0 囝 饧 囝 aa i s j e m a t ba _ x m e b a c o 嗌e b ba 6 _ m h ba m 删b a c o y m e d b y b ae o v e m b a o v e d 可n b 国 囝 饧 荔 u 囝囝囝 两 囝国 u 八 ，、 两两 唰 u 囝u 囝 圈2 - 6 对象间的空间关系 下面的例子说明了整个算法的流程，图2 7 是- + i m g e s 数据库的例子。 四川大学硬士学位论文 图2 7 对象化的| 皿a g c 数据库的例子 图2 - 7 怖a a g e s 中的对象有三种：、口、与o ，在这里，因为必须是两个 对象才会有一个空间关系，三个对象配合四种空间关系，总共有1 2 种可能性， 输入m i i l i m 岫s u p p o r t o = 3 - 与m a x i m u ms u p p o r t e t = 5 ，表2 1 8 是计算其存在的空 间关系的支持度后得到的结果。 表2 1 8 对象和支持度 p a i r so f o b j e c t s f r e q u e n c y ，) = o ，y 2 y l 0 。 2 、东南方( s e ) ：用 来表示d 2 在a 的东南方。 满足：x 2 一x 3 o ，y 2 - y 3 = 0 。 3 、西北方o 叮w ) ：用 来表示d 3 在q 的西北方。 满足：x 3 - x 2 = 0 。 4 、西南方( s w ) ：用 来表示q 在0 3 的西南方。 满足：x l - x 3 = = 0 ，y l y 3 ，q ，6 ，7 妈，1 5 ，2 5 ，1 2 , 2 7 ， ，“，1 7 ，1 0 ，7 ，1 0 ， ， 屯，1 5 ，1 6 ， ，q ，9 ，1 6 ， ，心，7 ，1 6 ，( 4 ，3 ，5 ，电，1 7 ，1 6 ， q ，1 5 ，2 5 ，1 2 ，1 7 设m i n i m u ms u p p o r t s 2 ，依据s p m i n e r $ 粼