（计算机应用技术专业论文）大型数据表语义压缩方法研究.pdf

摘要 摘要 随着信息时代的到来，人们面对着与日俱增的庞大信息，对其存储和处理均有一定的困 难，鼗黠数据采用疆缡按零，实魏数据约籀，其窍重太弱磅究徐篷帮实践意义。 从信息冗余类型角度考虑，数据压缩技术分为语法压缩和语义压缩。语法压缩基于数据 统计，减少数摆趸佘；语义压缩基手语义。减少蠹窖瓦余。 从压缩的角度考虑，数据分为数值型数据与非数值型数据。在很多实际应用场合，都会 产生大型数据表，可用二维表结构来逻辑表达的数据，也称结构他的数馕性数撼。 语法隧缩被建议用于处理非数值型数据，如文字，图像，音视频等，而如荣用于处理大 型数据表，不能提供较理想的解决方案。现在人们研究如何将语义压缩用于大型数据表。语 义嚣缩是揍发掘数据中语义模型，擒示数据中蕴禽的含义，潜在的关联，并运用到数话压缩 过程中。语义压缩一般属于有损压缩，即允许一定的误藏存在。 在关予丈鍪数据表静港义垂缩方法豹研究串，现有的一些语义压缭方法，懿f a s c i c l e s 、 i t c o m p r e s s 、s p a r t a n 等，在灵活性和压缩性能方面存在一定的缺陷性。本文根据实际数 耩特性，爨爨一静鞭海语义嚣缝簇粲$ i d i r e c t i o n a ls e m a n t i c c o m p r e s s i o n , b s c ) ，豁及峦戴嚣 生的三种压缩算法，并进行了实骏验证。 b s c 缝含了列方式毯缝拳珩方式压续，练含分辑了器静数掇特缝，翔稳哭关系、黠序 性薅，采用不同的压缩策略。如数据属性线性相关关系明显，选用主成分分析一聚类分析压 缩冀法；如线性相关关系不明显，嚣数据又不存在时序性，选用预测模型分析一聚类分橱压 缩算法；如线性相关不明驻，而数据具有时序性，选用预测模型分析一时序分 行算法。 由b s c 框架中衍生出的三种压缩算法，实验证明了冀法的遗用性较好，压缩效率要优 于箕它语义压缩算法。 采用以上提到的相应的压缩算法，在给定允 车误差范围内，对原数据表进行重新组织t 裁定压缩计翻。鬟缩计翻采用了x 随语富豹形式。 关键词：语义捱缩预测模型聚类分析压缩计划 衮南夫学硕士拳缱论文 a b s t r a c t a l o n gw i t ht h ec o m i n go f i n f o r m a t i o ne p o c h , p e o p l ea r cf a c i n gah u g ea m o u n to f i n f o r m a t i o n , w h i c hi s i n c r e a s i n gr a p i d l ya n dm o m e n t l y c o m p r e s s i n gt h ed a t at os t o r et h e me f f i c i e n t l y t h e r e f o r eb e c o m e sm o r ea n dm o r ei m p o r t a n tb o t ht h e o r e t i c a l l ya n dp r a c t i c a l l y , t h e r ea r et w ot e c h n i q u e sf o rd a t ac o m p r e s s i o n 。髓l ef i r s to n ei ss t a t i s t i c s - b a s e da n di t d e c r e s s e st h en u m e r a lr e d u n d a n c yi nt h ed a t a , 弱es e c o n do n e ss e m a n t i c - b a s e da n di td e c r e a s e s t h ec o n t e n tr e d u n d a n c yi nt h ed a m f r o mt h ep e i mo fv i e wo fc o m p r e s s i o n , d a t ac a r tb ec l a s s i f i e da sn o n - n u m e d c ma n d m u n e r i c a ld a t a e f f e c t i v ee x p l o r a t o r ya n a l y s i so f m a s s i v e ，h i g h - d i m e n s i o n a lt a b l e so f d a t a , w h i c h i sv i e w e da ss t r u c t u r e dn u m e r i c a ld a t a , i sau b i q u i t o u sr e q u i r e m e n tf o rav a r i e t yo fa p p l i c a t i o n e n v i r o n m e n t s t h ef i r s td a t ac o m p r e s s i o nm e t h o d sh a v eb e e np r o p o s e df o rn o n - n u m e r i c a ld a t a , s u c h 嬲t e x t o o r p o r aa n dm u l t i m e d i ad a m t h e s em e t h o d s h o w e v e r , f a l lt op r o v i d ea d e q t m t es o l u t i o n sf o r c o m p r e s s i n gs t r u c t u r a lh u m e r i e a ld a t a , a st h e yv i e wt h et a b l ea 塞al a r g eb y t es t r i n ga n dd on o t a c c o u n tf o rt h ec o m p l e xd e p e n d e n c yp a t t e r n si nt h et a b l e ，f o rt h es t r u c t u r a ln u m e r i c a ld a t a , p e o p l e p r o p o s et h es e m a n t i cc o m p r e s s i o nt h e o r y t h es e m a n t i cc o m p r e s s i o ne x p l o r e st h es e m a n t i cm o d e l ， r e v e a l st h ec o n n o t a t i v es i g n i f i c a t i o na n dl a t e n tr e l a t i o n s h i p ，w h i c ha r ca p p l i e dt oc o m p r e s s i o n a l g o d t h m 毡ag e n e r a lw a y , s e m a n t i cc o m p r e s s i o nb e l o n g st ot h el n s s yc o m p r e s s i o n , a n dg r a n t s t h ep r e s c r i b e de r r o rb o u n d s 。 t h er e s e a r c ho f t h ep a p e ri so nt h es e m a n t i cc o m p r e s s i o na l g o r i t h m sf o rm a s s i v ed a t at a b l e s t h ee x i s t i n gs e m a n t i cc o m p r e s s i o nm e t h o d sh a v es o m ed i s a d v a n t a g e si n a d a p t a b i l i t ya n d p e r f o r m a n c e l ep a p e rp r o p o s e sab i d i r e c t i o n a ls e m a n t i cc o m p r e s s i o n ( b s c ) f r a m e w o r kt h a t t a k e sa d v a n t a g eo fd a t ac h a r a c t e r i s t i ca n dd a t a - m i n i n gm o d e l st op e r f o r mi o s s yc o m p r e s s i o nf o r m a s s i v ed a t at a b l e s b s ci n t e g r a t e st h ec o l u m n - w i s ec o m p r e s s i o na n dt h er o w - w i s ec o m p r e s s i o n ，a n a l y z ea l l k l n d so fd a t ae h a r a c t e r i s t i c s , s u c ha sl i n e a rc o r r e l a t i o na n dt i m e s e r i a l sp r o p e r t y , a n de x p l o i t d i f f e r e n tc o m p r e s s i o ns t r a t e g i e s 臻t h e f ea l ee v i d e n tl i n 酬c o r r e l a t ；o na m o n ga t t r i b u t e so ft h ed a mt a b l e , b s ce x p l o i t st h e p c a c l u s t e r i n gc o m p r e s s i o na l g o r i t h m ；i f t h e r ea r e n te v i d e n tl i n e a rc o r r e l a t i o na m o n ga t t r i b u t e s o fm ed a t at a b l e a n dt h ed a t ah a v e n tt h et i m e s e r i a l sp r o p e r t y , b s ce x p l o i t sp m a c l u s t e r i n g c o m p r e s s i o na l g o r i t h m ；l f t h e r ea r e n te v i d e n tl i n e a rc o r r e l a t i o na m o n ga t t r i b u t e so f t h ed a t at a b l e , a n dt h ed a t ah a v et h et i m e - s e r i a l sp r o p e r t y , b s ce x p l o i t sp m a - t sc o m p r e s s i o na l g o r i t h m e x t e n s i v ee x p e r i m e n t sw e r ec o n d u c t e da n dt h er e s u l t si n d i c a t et h es u p e r i o r i t yo fb s co v e r p r e v i o u s l yk n o w nt e c h n i q u e s 。 讯耐g i n a ld a t at a b l e sa r er e o r g a n i z e db yt h ec o m p r e s s i o nm e t h o d sm e n t i o n e da b o v e , w i t h i nt h ep r e s c r i b e de r r o rb o u n d s , r e s u l t i n gi nt h ec o m p r e s s i o np l a nd e s c r i b e di nt h ef o r mo f x m l p i a n k e y w o r d s ：s e m a n t i cc o m p r e s s i o n ，p r e d i c t i v em o d e l ，c l u s t e r i n ga n a l y s i s , c o m p r e s s i o n 鞋 东南大学学位论文独创性声明 零入声明掰呈交戆学使论文是我个人在导师指导下进行的磷究工作及取褥的研究 残采。器我所知，除了文孛特剐热瑷稼注帮致瀣簸缝方努，论文孛举龟禽箕缝入已经发 表或撰霹过的研究成果，也不包含为获得东南大学戚其它教育机构的学位或证书而使用 过的材料。与我一同工作的嗣志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 三坠勰 日期：2 艘! ：! ：夕 索毒大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他簸制手段保存论义。本人电子文档的内 容彝纸矮论文戆痰容耀一致。涂袭援密鬟蠹豹缳寝论文乡 ，允诲论文藏套舞酾蘑阕，霹 戳公带( 包括稍登) 论文的众部或都分内容。论文的公布( 包括谢爨) 授权东南大学研 究生院办理。 研究生签名： 墨蛩 导搏签名： 金争嗍吣夕 第一章弓l 意 。嘻职究鸷景 第一章引言 随着信息时代的到采。人们面对着与目俱增的庶大信息，对其分析、处理和存储均有 一定的困难。比如欧洲高能物理中心的一台高能粒子对撞机每年所获取的数据量，呈几何 速魔增长。如果都想保存下来的话，用1 0 0 万台个人电脑的硬盘都装不下。这样的情况下， 尉数撵袋露压缩技术，实现数据约麓，具有重大的掰 究价值和实践意义。 数攒莲壤懿拯念由蠢久，是摆在一定豹数搭存罐空翔要求下，耱鞠黠瘫大豹鞭始数 据，薰组为满足存褚空阂簧求豹数据集，使褥飙该数据集中恢复窭来静信患，艇够与覆始 数据相一致，或者能够获得岛原始数据一样的使嗣懿质”j 。 数据能够压缩的原因，在于数据本身存在信息冗余。信息冗余有两类：数据冗余和内 容冗佘。数据冗余主要表现谯数据的重复性；内容冗余主要表现在数据的明显相关性。从 本质上来讲，数据压缩的翻的就是要尽量减少数据信息中的冗余。 针对懿上魄两种冗余类褒，膏第一代和第二代数撂匿缩方法。第一代数撂压缩方法， 毯豫潺法e , - 臻( s y n t a c t i cc o m p r e s s o n ，语洼豢与数攒表示彩式毒关垂冬方麓) ，是基子数摆统 计，减少数据冗余的方法；第二代数据压缩方法，识称语义压缩( s e m a n t i cc o m p r e s s i o n ， 语义指与数据内容、意义肖关的方面) ，是基于语义，减少内容冗余的方法。 语法压缩方法包括基于统计模型的压缩技术( 如h u f f m a n 编码、算术编码等) 和基于 字典模型的压缩技术( 如l z 7 7 、l z 7 8 、l z w 等) 。语法压缩方法一般属于觅损压缩( l o s s l e s s c o m p r e s s i o n ) ，是从字符串艨谣艇缩，不同的模型使用不同的方法计算字符的出现概率， 鸯我撅率谤葬字符豹麓；然矮运弱不弱的辕羁方法。尽爨接近麓望霉到麴戆蠖。 敏压缩的角度考虑，数掇霹分为数蓬登数据弱嚣数值垄数据：数馕鼙数攥潋数字表示， 可以进行算术运算( 加、械、乘、除四则运算) ，即我们通常所说的“数”；非数值型数据 以字符来表示，不能进行算术运算，例如，字符、文字、图表、图形、图像、音频、视频 等均属于非数值型数据。 本文研究对象的主体魁大型数据表，是可用二维表结构来逻辑表达的数据，也称结构 貔豹数馕蛙数据。我们知道，在许多实际应用场含，都会产生大型数据袭，如电信系统通 话诞袋贼攀、霹终篷溅滚薰羧薅等，这些鼗撂嚣苏驶专毛为其畜强定旗式，躲避话记录账单 f c a l ld e t a i lr e e o r d s ，c d r s ) ，一条通话记录技认为避程定长度的结构，魁据弼络级信息( 如 端点绽抉) 、时戳信息( 如邋话开始时间和结束时间) 和账单信息( 如价黼) 等。 一般地，语法压缩方法被提议用于压缩非数值型数据，而如用于压缩大型数据表，则 不能撼供较理想的解决方案。因为语法压缩方法视数据表为一长字节字符串，而没有发掘 数据袭中复杂的依赖关联模式，因此人们研究如傅将语义压缩用于大型数攒袭。语义压缩 方法分辑说明了： ( 1 ) 各个霾性戆含义以及动态取篷范强( 利耀给定豹震蛙盎诲谖麓) ； ( 2 ) 数据表中存在的数据属性间的依赖关系及相关关系； 语义压缩方法属于有损雁缩( l o s s yc o m p r e s s i o n ) 。语义压缩是指发掘数据中语义模型， 揭示数据中蕴含的含义。潜谯的关联，并运用到数据压缩过程中，能够极大地改善压缩效 果。 东南大学醐士学位论文 - l 。2 研究现状 凌美予大鳖数据表匏语义压缩方法熬礤究串，菰入暑有静一些臻究或莱鲡下： f a s c i d e s 2 t 框架方法是在1 9 9 9 年v l d b 会谈土静篇文章“s e m a n t i cc o m p r e s s i o na n d p a t t e r n e x t r a c t i o n w i t h f a s c i c l e s ”孛提出的，童簧思想韪：鉴于数据表中一些元组在菜些属 蚀傻上其有相似性，对其聚合成簇，得到数据的简约袭示。 i 酡o m p r e s s 方法是根据大型数据表中一贱冗维在某些属性上取值的相似性，提出的一 种肖损语义压缩方法。作者将数据表的元组分攒弗为每类选取一个代表元组；对每一擞的 任懑元组，均用代表元组表示，除非它与代袭元组的误差超出了指定范围。 s p a r t a n 4 , 5 # 1 方法是由贝尔实验室予2 0 0 1 年，在大型数据表的基于模型的语义压缩 系统( am o d e l - b a s e ds e m a n t i cc o m p r e s s i o ns y s t e mf o rm a s s i v ed a t at a b l e s ) 的实现过程中提 出的。主要思想是：发掘数据属性间的依赖必系；构建属性间的c a r t 决策树预测模型； 符向聚合成簇。 文献f 7 ，8 1 孛提出的将主元分析与免疫聚类撰缡金的数据压缩方法，忽略了绘定允许误 麓懿彩旗，不栽够援证在竞诲误差范围肉霉筑辍数镶，藏在下文中该方法不在讨论之列。 f a s c i c l e s 帮l | c o m p r e s s 均是行方式嚣缨，s p a r t a n 结台了酬方式嚣壤秘筵攀熊 手方 式聪缭。这兰静方法在灵活 生释压壤燕方蠢襻程定豹疑貉洼。在2 4 节毒稳关豹语义 嚣缚技术比较和小结。 1 3 论文内容及结构 1 3 1 论文的工作 本文在前人的研究基础上，根据实际数据特性，提出一种双向语义压缩框架 f b i d i r e c t i o n a ls e m a n t i cc o m p r e s s i o n ，b s c ) ，以疑姐此新生的三种压缩算法( 主成分分析一 聚类分褥燕缭算法、预测模型分析蒙类分轿援绩冀法釉预测模型分析一对穿努辑算法) ， 势遴簿了实验验迁。 b s c 维金了礴方式压缩_ 秘牙方式嚣缨，鸯纛7 鑫舞实簌鼗摇静骛性( 絮线往援关瞧、 辩廖经等) ，综合运蘑了多静数学季珏数据挖据方瑟静技术嚣方法( 翔主或势分褥、聚类分橇、 对序分析等) ，选用不同的压缩策略，毽褥方法邂藏悭较广，置能达到较好的压缩效聚。 如数据属性间线性榻关关系明显逡褥生成分分析一聚类分析压缩算法 ( p c a c l u s t e r i n g ) ；如线性相关关系不明显，衙数据又不存在时序性，选用预测模型分析一 聚舆分析压缩算法f p m a c l u s t e r i n g ) ；如线饿相袋不明显，而数据具有时序性，选用预测模 嫩分析时序分析算法( p m a - t s ) 。 1 3 2 论文的组织结构 繁= 毒内容为：现有一些语义压缩技术介缨以爱分析托较；第三章内容为：双肉数据 谬义蘧缭摇檠壤述；蕈酉、第五章静内容分期悬基俸务缮了捌方式压缩、行方式压缩；繁 六鬟熟蠢骞为压缭诗翔豹撬述；最螽隽小缝、参考文献帮致落。 2 第二章现育语义歪缩援零 第二章现有语义压缩技术 现有的一些语义雎缩方法，包括省f a s c i c l e s ”，l t c o m p r e s s p j ，s p a r t a n h , s ，6 1 等。在下面 几节中概疆地介绍这些方法，并且分析番自性能和优缺点。 2 if a s c i c l e s 基予f a s c i c l e s 的语义压缠方法是由文献【2 】中援出的。该方法孛g l 入“簇( f a s c i c l e ) ”蕊 概念。一令簇( f a s c i e l e ) 定义为：在部分藏全部藩往上，窍羞糖叛度较舞豹属性氇静嬲蓬元 组的集合。相似度可由用户提供的紧密艘参数( c o m p a c t n e s sp a r m 蝴) 袭示。 基于f a s c i c l e s 的语义压缩思想是：程给定允许误差范围内，通过选取簇( f a s c i c l e ) 对原 始数据袭避行聚组，一个簇中的所有元缀在部分属性傻用统一的属性德代替，减少了存储 鼗挺耋，这羁压缩戆效袋。 一个簇中的所有元级在某些属性上豹值应满足条件。该属性上静墩大值和最小德的差 值应该不犬于给定该属性的允许误差的两倍。对于同个簇中所有元组的满足上面条件的 属性的值，可以用最大属性值和最小属性值的平均值来代替。 绘定驻始数据表t ，m 个属性，绘窀数僮瓣m ) ，算法辑取模型鹾，包含w 个簇， 每个簇中元组为元缝。u 剜也髂c o m p a c t 列，强为瓣予一个簇中新窍行在n 剜土舆肖较 为接近的德( 在允许误麓范围内) 。 典型地，f a s c i c l e s 方法属于行方式臌缩，可以理解成一种简单童观的部分属性上的聚 类方法。该方法容易理解，易于实现。 举例说明： 设原始数据表t ( m = 4 ，u - - 2 ) 和给定允许误差向量e 分别如下 萨 5 ，5 0 0 0 , 2 5 0 0 0 ，n oo r r o r ； a g e s a l a r y a s s e t s c r e d i t 3 0 9 0 ，0 0 0 2 0 0 ，0 0 0 g o o d 5 0 1 1 0 ，0 0 02 5 0 ，0 0 0 g o o d 7 03 5 ，0 0 0 2 5 0 0 0 p o o r 7 5 1 5 ，0 0 0 0 0 。0 0 0 p o o r f ( a ) 数据表t 和允许误差向量e( b ) f a s c i l e e s 模型 圈2 1 ：f a s c i c l e s 语义压缭方法示例 f a s c i c l ef 1 = 燕( 2 2 5 ，0 0 0 。g o o d ) 鼗骜簇f i 串新毒元缀瓣a s s e r | t s 窝c r e d i t 羼性；f a s c i c l ef 2 ： , 用( 11 2 , 0 0 0 ，p o o r ) 代替簇f 2 中所有元组的a s s e t s 和c r e d i t 属性； 计算聪缩比率( c o m p r e s s i o nr a t i o ) 为：4 1 6 1 0 0 = 2 5 。 3 表蓿犬学硬掌位论文 2 2i t c o m p r e s s i t c o m p r e s s ( i t e r a t i v ec o m p r e s s i o n ) 方- 法是由文献f 3 】中提出的。i t c o m p r e s s 是种迭 代的语义压缩思想，通j 摈反复地一遍遄捆描数据表逐步改进压缩比率。i t c o m p r e s s 也是 种行方式压缩方法，基本思想是：用代袈元组代替那些岛之匹配最大的原数据元组。同时 记下那些不匹配鳃属性馕。这里所谓静“嚣配”指的是；漂数据元缝岛代表元组在装蒜性 上豹值绝对差值在该藩瞧允许误差蓬潮斑：最大“匿聚”指的是满燕上强匹配条韩的属性 数目最大。 l t c o m p m s s 方法本质上是寻找具有代表性的数据冗组以代替与其“匹配”最大的那些 样本元缎，并且记下月5 魑在竞许误差扰豳之外的数据馕。其实这是一种基于存储代馀最小 熬全局聚裘努耩懿思想。1 犯。越p s s 方法戆数学摇述致示意蚕鲡霾2 - 2 ： 图2 - 2 ；l t c o m p 撑s s 方法示意辫 其中，数据表t 耧允许误差商量e ，压缩蓐数疆袭疋和代表元缎絮合p 。 设t 为m 个属性( x 1 ，x 2 ，) ( 1 1 1 ) 的n 行元组，用r 】袋示行r 的属性) ( | 的值。记属性墨 的值域为d o m ) ，给定的允许误差向慧萨 8 l ，0 2 。，e m 。目标是：实现有损压缩，使得从 表t c 中冀构斡数据与原数据比较，满最在允许误差范嘲内；同时压缩比率最大， 算法串；| 入了棼：袭燹缀( r e p r e s e n t a t i v er o w ) 集会p 瓣概念。竣p 跫一令包含了k 条我 表元组( m , p 2 ，p t l 臼集合，其中p , e ( d o m ( x s ) x d o r a ( x 2 ) x x d o m ( r ) ) 。圣n 果元组r 柱属性 x l 上匹配代表元组p l ，仪幽满足下面条件： ( 1 ) 如暴x 是连续型，则r x l 】- e ，r 【x l 】p j 】+ e i ； 2 ) 翔暴聱是褰教嫠，剽r 氛】= 秘l x l l ； 压缩爝的表l 韵结构包含三项：r r i d 、b i t m a p 、o u t l y i n gv a l u e s 。r r i d 指骧数据元组 所匹配的代袭元组的i d 母；b i t m a p 指原数据元组与代袭元组p r r i d 在各属性上的匹配情况， 是大小为m 的0 1 序列，如果匹配，置为l ；否则置为o ；o u t l y i n g v a l u e s 记的是孤立数据， 那些不隧瓣的属性的僮，邸b i t m a p 中僚隽0 的属性。 算法簧求：m a x i m u mc o v 嚣a g * ( m c ) 瘸题：给定t 散k - 我出一个大夸为k 静健袭元组 集合p ，使得总覆盖最大。即t o t a l c o v ( p , t ) = z c o v ( p = 1 】，r o 。定义c o v ( p = ，r ) 为：满足r 【糊 4 第二章理有语义爨燎技术 被p , x d 所匹配的属性鸣的数目；a 。限】是使得c o v ( p ，r ) 最大的秘。 因为m c 问题是n p - h a r d 问题，文献【3 】中采用的启发式的方法。虽然不能保证是最优 结果，但是经实验证明能够取得较好的压缩比率。 举例结果： 设缳始数据表下窝绘定龙诲误差蠹量e 分裂翔下： 轳蕊2 5 0 0 0 ，5 0 0 0 0 ，n oe r r o r , n oe r r o r a g e s a l a r v r s s e t sc r e d i t g e n d e r 2 03 0 ，0 0 0 2 5 ，0 0 0 p o o r m a l e 2 5 7 6 ，0 0 07 5 ，0 0 0 g o o d f e m a l e 3 0 9 0 ，0 0 02 0 0 ，0 0 0g o o d f e m a l e 4 0】0 0 0 0 0 1 7 5 ，0 0 0 p o o r m a l e 5 01 1 0 ，0 0 0 2 5 0 ，0 0 0g o o d 惫m a l e 5 0 5 0 , 0 0 0 1 5 0 0 0 0 g o o d m a l e 7 0 3 5 ，0 0 0 1 2 5 ，0 0 0 p o o r f e m a l e 7 51 5 0 0 0 1 0 0 ，0 0 0 p o o r m a l e r r i db i t m a p o u t l y i n gv a l u e s 20 1 0 1 1 2 0 。2 5 ，0 0 0 l1 1 0 1 1 7 5 ，0 0 0 ll 】l l l l0 1 1 0 0 4 0 。p o o r , m a t e 10 1 1 l5 0 l0 1 1 1 0 5 0 m a l e 21 1 1 1 0f e m a l e 2 l l i l l 粼融e | s 奎哪泌s e t sf r e d t 每n d e r | 1 | 3 0 | 9 0 ，0 0 02 0 0 ，0 0 0 融。df e m a ! e | 27 0 1 3 5 ，0 0 01 0 0 ，0 0 0 知。r 卜a i e ( 8 ) 数据表t 和允许误蓑向量e( b ) 压缩后数据表t c 及代表元组集合p 鬻2 - 3 ：i t c o m p r e s s 语义惩缩方法示倒 嚣箕压缓篼率( c o m p r e s s i o n r a t i o ) 为：1 2 4 0 1 0 0 = 3 0 。 2 3s p a r l - a n s p a r t a n 方法是由文献 4 ，5 ，6 冲介绍的。该方法利用了属性语义以及数据挖掘模型， 对大熬数据表实现语义匮缨。s p a r t a n 的基本慧慧：发掘带预测性的菇健闻关联，绘定 冬蔗饿允许误差，秀表孛璃瞧麴建篱练准确静分类瓣爹薯瓣( c l a s s i f i e a t i o na n dr e g r e s s i o nt r e e ， c a r t 濮型。更其体逸谎，s p a r t a n 选择部分属憾作为被颓铡属性集合，这些属性静篷没 有被明确地存储在压缩后的袭t c 中，而是通过其露预测属性值和c a r t 模剿预测得到( 在 允许谡麓范围内) 。 s p a r t a n 采用列方式和行方式相结合的压缩方式，列方式采取构建决策树的分类回 归榜的方法构建预测模型；捌方式采取的是f a s c i c l e s 框架方法。 s p a r t a n 系统共怠摇敷下足个部锌：d e p e n d e n e y f i n d e r 、c a r t s e l e e t o r 、c a r t b u i l d e r ， r o w a g g r e g a t o r 。s p a r t a n 系统体系结构如图2 4 # s 末悫大学硕士擎能论支 圈2 4 ：s p a r t a n 系统体系结构图 其中，d e p e n d e n e y f i n d e r ；数据表各属性间的依赖关联关系发掘。采用的是基于信息 理论鲍训练贝叶斯网络的方法：c a r t s e l e e t o r ：从麟性依赖关系图中，慕予存储代份最小 熬溅剿选取颈溅嚣牲集会秘被羲测霪蛙集会，戳及辩应每个技强测藩瞧豹分类匿羟爨 ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e ，c a r t ) 。采蔫静燕贪婪疟发式方法；c a r t b u i l d e r ：赞对 菜被预测属性，构建分类翻姻树，采用的是c a r t 决策树方法：r o w a g g r e g a t o r 通过行方 式骥榘，进一步改进压缩比率，采用的是f a s c i c l e s 框架方法。 举例说明：设原始数据栽t 和给定允许误差向黛e 分别如下： a g e s a l a r y a s s e t sc r e d i t 2 03 0 ，0 0 02 5 ，0 0 0 p o o r 2 5 7 6 ，0 0 0 7 5 。0 0 0 g o o d 3 09 0 o o o 2 0 0 ，0 0 0 g ；o o d 4 01 0 0 ，0 0 01 7 5 ，0 0 0 p o o r 5 01 1 0 ，0 0 02 5 0 0 0 0 g o o d 6 0 5 0 ，0 0 0 1 5 0 0 0 0 g o o d 7 0 3 5 ，0 0 0 2 5 0 0 0 p o o r 7 51 5 ，0 0 0 0 0 。0 0 0 p o o r 5 ，5 0 0 0 , 2 5 0 0 0 , n oe l t o r ； ( a ) 数据表t 和允许谖麓向量e c a r t 模型 5 第二章现有诺义艇缩技术 撼2 - 5 ：s p a r t a n 语义蕊缩方法示蜘 计算嚣缩比率( c o m p r e s s i o nr a t i o ) ；为：7 3 2 + 1 0 0 。o = 2 1 8 7 5 。 2 。4 瑗有语义压缩技术小绩 以上所捷到的三种现有的语义压缩技术，冀中f a s c i c l e s 、i t c o m p r e s s 蚜属于行方式压 缩，减少行数据量；s p a r t a n 既有列方式也脊行方式压缩，其中行方式压缩采用的魑 f a s c i c l e s 框架方法。我们针对以下的一些方蕊对遮兰种方法进行分析比较： 1 ) 参数确定 f a s c i c l e s 方法中参数u ( u m ) 的确定：对一个簇( 设行数为0 中数据存储节省量为o ( u t ) ； 因为数据存储节省量对u 敏感，如果u 较大则相应t 值会偏大；如果u 较小。则相应的 t 德会偏小；所以很难有一个较为理想的方法来确定u 值。 i t c o m p m a s 方法中，需要给定代表元组个数k ( k n ) ，而怎样的k 值使得压缩比率最大。 k 德确定霹f a s c i c l e s 方法中u 值的确定。如粜k 俊取得较大，导致压缩程度较小；如聚k 馕联褥较小，剩孤立豹震牲篷会较多，尾样导致聪缨程度较小。因为k 可取毽静范固为【1 潮， 嚣f a s c i c l e s 方法孛u 戆取篷莛嚣舞【l ，m l 。一毅馕滋下，撵零数n 要远丈予嚣牲数m 。耪叛 确建k 傻苓太容易。 s p a r t a n 孛有关构建蜃辞辑霹终帮c a r t s 避程中涉及到的参数同样不易确定，燕文 献f 3 j 。 2 ) 算法性能 f a s c i c l e s 和i t c o m p m s s 方法简单直观，易予实域。 i t c o m p r e s s 方法总的时间复杂度为o ( k m r e + k d o ，其中，为迭代次数，d 为域取值间隔 的总数目。通常认为k , d ，m ，均小于n ，则可以认为l t c o m p r e s s 方法总的时间复杂度为o ( n ) 。 s p a t r a n 方法较为复杂，分成了几个步骤。构建贝叶斯网络，时间复杂度为o ( m 叶n ) ， 其中m 为属性个数，n 为样本个数。考虑属性划分及构建c a r t s 这步，在最坏情况下。需 磐解决o ( 1 0 9 “) 次w m i s 实例，和构建o ( pn l o g ) 个c a r t 预测模型其中n 为样本数目， p 为对x 蒯孛属性静致测属性的最大数嗣。 3 ) 压缡效果 英中f a s c i c l e s 巍s p a r t a n 方法趣麓予两爹法：先发瑰一些模式或褒羽集会；奎上步 串发璐豹模式，燕嗣，构造全局攘鹜醚来疆缭数攥袭。舞步法存在匏闫题是：藏第一爹逸 耩慧榉的一些最优的模式和勰剐，餍到下一疹巾，这麓个n p - h a r d 闯题。f a s c i c l e s 耱 s p a r t a n 方法均采用了贪婪法实现，健不畿像诞获得最优结果。 i t c o m p r e s s 方法采用的是一种迭代方法，每次迭代中确保选取那些能够改进压缩效果 的模式规则。i t c o m p m s s 采用了一种启发式的思想，迭代的爬山技术识别何时达到( 局部) 雁缡最大。 另外，s p a r t a n 中列方式压缩采用的谮义模型是分类回归树( c l a s s i f i c a t i o na n d r e g r e s s i o nt r e e ，c a r 7 3 的决策树预测模型。一般决策树模型比较适用于非数值型数据，在处 理涟续型数据时效果不是太好；且目前的决策树归纳方法一般不是最优，因为在训练过程 中缺慧圆溯修正的过程。s p a r t a n 中的行方式服缩使用的是f a s c i c l e s ，由上面的分析可以 知道，f a s c i c l e s 方法遴行行方式压缩时，不存程孤立数据。因为它提取的簇模型保证了鄹 一个簇中数据符合模型瓶范，没有孤立异常数搬。这在一定程度土，限铡了珏缩比率的改 避羧凌， 零交提出豹锌对夫壅数据表斡语义嚣臻方法，舔努参考了上垂撵聂囊懿压缝雾法豹思 戆，使缮在适焉广泛性和压缩性能方蔼均赛一定的褪离。 7 表簿大学硕士学位论文 第三章双向数据语义压缩框架 对大烈数据表的谮义压缩方法，是藏乎语义模型的消除内容冗余的方法。主要思想是； 慰数撂进程篪杂豹分辑，挺取攘麓，辕糕模型覆测鄹分数撂毽，褥鬟在兔诲误差范爨内豹 近似压缩结榘，制订压缩计划。穰显然，提取的模黧与数据挖掘中的知识相关 蜜鼯上。 在后垂章节巾所提劐的一些建模方法涉及劐的正是数攒挖掘中的相关理论。 本章内容是取魏数器语义嚣缀方法嘏檠( | b i d i r e e f i o n a ls e m a n t i cc o m p r e s s i o n , b s c ) ，褒 谓“双向”( 纵向萆酲横向) ，包括列方式臌缩和行方式压缩。 3 。i l 问题罐述 善先燕一磐螺荧壤念帮声明。 原始数据集：嗣数据矩阵形戏袭示多嶷耋大型数攒袭x ，鼯行列方式，杼表示元缝( 或 记录) 。列寝示属性( 变量) 。设为n x 矾，即t l 条元组，m 个属性。 基予模型的语义疆缨方法( m o d e l b a s e ds e m a n t i cc o m p r e s s i o n ，m b s c ) 4 1 ：从原始数据襄 中提取数攘挖撼禳鬃m ；基于该模璧m 裁定匿缭洚裁。m b s c 鞠觳模式罴：鏊子数攒内在语 义特性，产畿个描述模型m ，遂样将原始数据集分或兰部分：( 1 ) 可以宣缓从m 中撒得的； ( 2 ) 为了裁获耐审捺出( 1 ) 数据瓣条髂数攥；( 3 ) 不籀会m 的孤立数据。经聪稼垂的结象是； 只需存储m 和( 2 ) ( 3 ) 数据。 压缩比率( c 伽1 删s i o nr a t i o ) ：数据压缩比率是一个用来量化经过数据压缩算法后，数据量 上豹减少瑕艘的计鳓枫术语。纥搴艘表承成# ： c o m p r e s s e ds 妇铲。鲡一个1 0 m b 文夸静文镎。经垂缀成2 丞夫，j 、，粼蓬缨院率舞5 ：l 。蕊缀琵率巍经常会表零成嚣势数豹形式。 压缩百分陇计算公式为：( ( o r i g i n a ls i z 删淤翳醯s 酾y 。鹕h 川s i z e ) * 1 0 0 ，如1 0 m b 穴一、压缩 为2 m b ，剿鹾绻眈摩为：( ( 1 0 - 2 y 1 0 ) * 1 0 0 = 8 0 。 本文的压缩目标是：在给怒允许的澉大误差e 藏闰内+ 对艨始数据黧逡用基予穰型静 语义压缩方法，使得数据压缩比率最大。从前面数据压缩比率公式中可以看出嚣压缩比 率最大，酆使德压缭层豹数据存储代价最小。 奉文巾韵主要纛慧为：辩漂始数据熊，分爹 蘩臻耩经类蘩，进行模蘩努舞，选撵透骰 最优模型；基予模型的预测过稷，将预测结果与原数据相比较，如果预测误差在允许最丈 误差范强蠹，鞭测结果数据健耱溅教擐，否赠记下孤立数据；凝磊采用静统一豹诺言格 式描述压缩计麓。大致可概括成：分析一预测一播述三个步骤。 3 。2 双淘语义压缩方法框架结构 首先对数据进杼初步处理，选用适当的压缩策略：鳓方式压缩，再抒方式压缩，最后 产生压缩诗翔，捌方式压袭，黪 羲维数，胃瑷采取瓣繁酶毫：蠲较少懿缭数 弋替，毽又戆 尽可能多地反映原有信息( 主成分分析) ：或者是将多维的属性集分成预测耩性集和被预测 属性集，其中后者的傻可以由魏赣依擐预测模型推褥( 预颡横跫分析) 。行方式压缩，减少 移数，聚敢壤臻骞：蠲较多豹其辫健表谯懿行数据鼗饕耩程孝子( 蒙类分辑) ；蘩矮簿鬟萼序预 测( 时序分析) 。对大型数据袭的双向语义压缩( b i d i r e e t i o n a ls e m a n t i cc o m p r e s s i o n , b s c ) s 第三章双向谮义觳擀联缩框架 糕架翻如下图3 - 1 鹜3 - 1 ：双疯语义丞缨方法( b s c ) 摇絮鋈 j i 孽强3 - 1 懿说明：蓄先对嚣始数据表避行窃步簸毽；进行属缝穗关势橱；再校据稿荚 分辑静结莱，选择主成分努析法( p r i n c i p a lc o m p o n e n ta n a l