(计算机软件与理论专业论文)用于提高范围查询效率的多维聚簇算法研究.pdf_第1页
(计算机软件与理论专业论文)用于提高范围查询效率的多维聚簇算法研究.pdf_第2页
(计算机软件与理论专业论文)用于提高范围查询效率的多维聚簇算法研究.pdf_第3页
(计算机软件与理论专业论文)用于提高范围查询效率的多维聚簇算法研究.pdf_第4页
(计算机软件与理论专业论文)用于提高范围查询效率的多维聚簇算法研究.pdf_第5页
已阅读5页,还剩52页未读, 继续免费阅读

(计算机软件与理论专业论文)用于提高范围查询效率的多维聚簇算法研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

论文题目: 专业: 硕士生: 指导老师: 用于提高范围查询效率的多维聚簇算法研究 计算机软件与理论 王鹏 汤庸教授陈炬桦副教授 摘要 随着计算机技术与通讯技术的迅猛发展,与人们生活息息相关的数据变得越 来越多。对海量数据进行科学组织和管理的数据库在这期间得到了广泛的应用, 研究多维数据的存储与查询也随之成为数据库领域的一个热点。查询作为数据库 的一个重要功能,提高查询的效率对提升数据库性能来说十分重要。多属性范围 查询是针对多维数据进行查询的主要方式,这类查询一般返回一个记录的集合而 不是单个记录。提高多属性范围查询的效率是本文的研究目标。 数据库的文件系统主要包括索引文件和数据文件两部分。于是针对多属性范 围查询有两个改进效率的方向:一个是在设计更好的索引机制,另一个是在物理 层按照某种策略重新安排记录的排列顺序。本文将采用第二种方法来提高多属性 范围查询的效率,即通过多维聚簇的方式使数据文件中的记录以一个更理想的次 序存储在外存中,从而减少范围查询过程中的i o 时间。 本文在国内外现有多维聚簇的技术和方法上,对多维聚簇做了进一步探讨。 首先细致地分析了该问题,并针对该问题构造了数学模型。然后通过引入光谱算 法的思想为解决该n p 难问题提供了一种多项式时问内的近似解。接着采用记录 与记录集的几何中心的欧氏距离作为衡量记录与整体关联度大小的参数提出了 f p f 算法,它的时间复杂度和空间复杂度都优于光谱算法。最后通过实验来比较 了这些方法在多属性范围查询中的表现。 关键字:范围查询,多维聚簇,光谱算法,f p f 算法 币t l e :r e s e a r c ho fm u l t i d i m e n s i o n a ic l u s t e r i n ga l g o t h m st ol m p r o v et h e m 勾o r : n 锄e : e m c i e n c yo fr a n g eq u e r i e s c o m p u t e rs o r w a r ea n dt h e o d , p e n gw a n g s u p e r v i s o r : p r o f e s s o ry o n g g a s s o c i a t ep r o f e s s o rj l l h u ac h e n a b s t r a c t a st h ef a s td e v e l o p m e n to fc o m p u t e rt e c h n o l o g y 觚dc o m m u n i c a t i o nt e c h n o l o g y , t h ed a t aw h i c hi sc l o s e l yr e l a t e dt op e o p l e sl i v e sb e c o m e sm o r e 锄dm o r e t h e d a t a b a s ew h i c hi ss c i e n t m c a l l yo 唱a n i z i n g 锄dm a n a g i n gm a s sd a t ah a sb e e nw i d e l y u s e di nm a n yf i e l d s s t u d yo fm u l t i d i m e n s i o n a ld a t as t o r a g ea n d q u e d ,a l s ob e c o m e sa h o t s p o to fd a t a b a s e q u e j s 卸i m p o n a n t 如n c t i o no fd a t a b a s e ,s 0j m p r 0 v i n gt h e q u e d ,e 幅c i e n c yi si m p o n a n tt oe n h a n c et h ed a t a b a s ep e r f b 砷a n c e r a n g eq u e d ,i st h e m a i nf 0 册o fd a t a b a s eq u e d ,a n ds u c hq u e r yg e n e r a l l yr e t u m sac o n e c t i o no fr e c o r d s r a t h e rt h a l las i n g l er e c o r d ,l m p r o v i n gt h ee 币c i e n c yo fr a n g eq u e d ,i st h eo b j e c to f s t u d yi nm y t h e s i s i ng e n e r a l ,t h ed a t d b a s ef i l es y s t e mc o n s i s t so fi n d e xf i i e sa n dd a 组f i l e s 7 i | l u s , t h e r ea r et w od i r e c t i o n st oi m p r o v et h ee 硒c i e n c yo fr 锄g eq u e 叫0 1 1 1 ei sd e s i g n i n ga b e t t e ri n d e x ,a n dt h eo t h e ri sr e a 盯a n g i n gt h eo r d e ro fr e c o r d si nt h ep h y s i c a l l a y e r 1 n t h i st h e s i s ,t h es e c o n da p p r o a c h 晰b eu s e dt oi m p r o v et h ee m c i e n c yo f 聊1 9 e q u e 拶 w ew i l lu s em u l t i d i m e n s i o n a lc l u s t e r i n gt or e a r r a n g et h er e c o r d si no r d e rt or e d u c e t h ei ot i m eo ft h er a n g eq u e l nt h i st h e s i s ,w ew i l lf u n h e re x p l o r et h et e c h n i q u e sa n da p p r o a c h e so ft h e m u l t i d i m e n s i o n a l c l u s t e r i n g f i r s t l y , w e a n a l y z e t h e p r o b l e ma n d b u i l da m a t h e m a t i c a lm o d e l a n dt h e nd e v i s eam u l t i d i m e n s i o n a lc l u s t e r i n ga l g o r i t h mw h i c h b a s i c a l j yb o 丌0 w si d e af r o ms p e c t r a la l g o r i t h m t h e nw ed e v i s eam u l t i d i m e n s i o n a l c l u s t e r i n ga l g o r i t h mn a m e df p fa l g o r i t h mw h i c hh a sb e n e rt i m ea n ds p a c e c o m p l e x i t ) r f i n a li y ,、v ec o m p a l l et h e s ea l g o r i t s p e r f o r m a n c ei nm g eq u e r y t h r o u g hs o m ee x p e r i m e n t s k e yw o r d s :r 2 m g eq u e r y ;m u i t i d i m e n s i o n a lc i u s t e r i n g ,s p e c t r a la i g o r i t h m ,f p f a l g o r i t h m i v 论文原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独 立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体,均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名:至煎 日期:幽年妄盈驾立 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定,即:学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版,有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅,有权将学位论文的内容编入 有关数据库进行检索,可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名:王鹇 日期油争箩畔日 肺 桦一皿 眶晔 尊一, 雠岁 名国1娣冲 师期 导日 用于提高范嘲金询效率的多维聚簇算法研究第l 章引言 1 1 研究背景 第1 章引言 随着计算机技术和通讯技术的迅猛发展,人们获取信息的途径变得越来越 广,与人们生活息息相关的数据也变得越来越多,而且它们呈指数级增长。于是 如何对这些数据进行科学的组织和管理也就变得尤为重要了,而数据库很好地扮 演了这一管理者的角色。数据库在这期间得到了迅速的发展,其应用领域也变得 十分广泛。研究高维数据的存储与查询也成为了数据库领域的一个热点,高维数 据的应用涉及很多领域,如时态数掘库、多媒体数据库、地理信息系统等i 卜5 1 。 查询是数据库很重要的功能,提高查询的效率对提升数据库性能来说是至关 重要的,于是对提高查询效率的研究也就变得很有意义。高维数据的主要查询方 式是多属性的范围查询( r a n g eq u e 忉,这类查询一般返回一个记录的集合而不是 单个记录【6 l 。传统数掘库中多列属性组合的范围查询也可以看作是多属性范围查 询。 为了提高多属性范围查询的效率,首先需要知道这些数据文件的物理结构。 数据库管理系统的文件存储形式通常分为两个主要部分:数掘文件和索引文件。 因此一般有两个提高查询效率的方向:一个是设计更好的索引,另一个是更好地 组织数据文件。到目前为止,已有大量针对提高范围查询效率的研究,不过这些 研究大多关注的是索引部分,其实针对数据文件的研究也同样重要,我们可以从 另外一个角度来改进查询的效率。 众所周知,主存与磁盘交换的数据单位是物理块而不是记录,一个物理块一 般来 兑包含若干个记录。从外存中读取一个物理块的时i 、日j 丌销远大于从主存中读 取相同大小的数据,此外考虑寻道的时问丌销,在磁盘上读取不连续的物理块将 花费更多的时问,而主存则不存在这个问题( 事实上,在主存上读取任何数据都 只花费常数时问) 。在外存上访问数据的时问丌销为毫秒级,而在主存上访问数 据的时间丌销则仅为微秒级,这意味着在外存上访问数据比主存慢1 0 0 0 倍以上。 用于提高范围查询效率的多维聚簇算法研究第l 章引言 因此为了提高查询效率,在一次查询中应该读取尽可能少的物理块并使这些物理 块在外存的线性顺序中尽可能地紧挨着。故如果将有关联的记录存储在同一个物 理块或相物理邻的块中,那么就可以很好减少在查询中占据主要地位的i o 时i 、日j , 其中有关联的记录是指具有相同或相近查询属性的记录。本文将主要探讨如何将 数据文件中的记录安排在一个理想的顺序下,从而降低查询过程中的i o 时间。 给数据文件中的记录重新安排顺序这一过程可以看成对记录的多维聚簇 ( m u l t i d i m e n s i o n a lc l u s t e r i n g ) 【7 9 1 。本文的主要工作将围绕着多维聚簇进行。 1 2 国内外研究现状 目前对于提高范围查询的效率,大家更多的关注于高维索引的研究,在物理 层对数据重组的相关研究则相对较少,对多维聚簇算法的研究则更少。高维索引 主要由树结构演化而末,如今应用较为广泛的包括k d b t r e e 族和r t r e e 族l l o ,1 。 另外已有的多维聚簇算法主要包括排序算法、适应性算法、区域分裂算法和m d c 技术等。 1 2 1 高维索引 现在的高维索引主要从四种索引结构演化而来的:k d t r e e ,b t r e e , h a s h i n g ,s p a c ef i l l i n gc u r v e i l 2 ,13 1 。目前应用较为广泛的包括:山k d 1 r e e 结合 b t r e e 演变而来的k d b t r e e 族l i o 】、由b t r e e 演化而来的r t r e e 族】。k d t r e e 是二叉查找树在高维上的扩展,它的缺点是扇出太小从而引起树高太大,使得外 存访问次数偏高。k d b t r e e 在k d t 嗽的基础上吸收了b t r e e 的特点,增加了 节点的扇出从而克服了扇出过小的缺点。k d b t r e e 是一种空间划分( s p a c e d i v i d i n g ) 的索引,它具有向下分裂的特性,缺点是节点数过多,物理利用率低 l 1 0 1 i 悼钉。r t r e e 是b t r e e 在高维上的扩展,它的叶子结点保存着记录,非叶子 结点保存着最小外接矩形( m i n i m u mb o u n d i n gr e c t 觚d e ,m b r ) 1 1 6 l ,任何子孙结 点的m b r 都包含于其父亲结点的m b r 中。与k d b t r e e 相比,r 1 r e e 对于非 均匀分布的数据具有更好的性能。 2 用于提高范崮查询效率的多维聚簇算法研究 第l 章弓i 言 1 2 2 聚簇算法 ( 1 ) 传统聚簇算法 传统的聚簇算法主要基于排序来实现。这种方法需要知道各属性的查询频 率,而后根据查询频率的高低依次在这些属性上对记录进行排序。首先对查询频 率高的属性排序,然后在这个基础上对频率低的属性进行再次排序。对于属性的 排序又包括完全排序和部分排序两种策略。完全排序即对所有的属性集进行排 序,由于完全排序会花费过多时间,又有人提出了只针对部分属性集进行排序的 方法1 1 7 ,1 引。 ( 2 ) 适应性算法 c t y u 等提出一种减少磁盘寻道时间的适应性方法,其频繁地将相关的物 理块移动到相邻的位置。每次查询过后,在物理存储上对符合查询条件的记录进 行位置调整,根据设定的权值大小以一定的速度靠近质心( c e n t r o i d ) 。在这种方 法不需要预先知道记录访问频率,但是需要比较长时间才能发挥作用( 用于慢慢 的收集统计数据) ,因此在系统刚刚建立的时候该方法并不能提供帮助1 9 1 。 ( 3 ) 区域分裂算法 j 一h l e e 等人针对数据库物理层设计提出一种用于高维数据重组的区域分 裂策略。这种方法借鉴了二分法的思想,是个递归的过程。在该方法中,首先要 获取大量查询式样,并统计各属性的查询频率;接着选择出参与分裂的属性集, 将该属性集中的每个属性作为一个坐标轴,构造出一个空间即目标区域;最后按 照一定策略在各轴上对目标区域进行分裂,分裂过程可简单描述为:如果区域包 含记录数小于或等于块因子( 每个物理块存储的记录数) 则停止分裂并将这些记 录存储到一个新的物理块中,否则将目标区域分裂成两个大小相等的子区域,并 继续分裂这两个子区域。这种方法的局限在于需要预先获取大量的查询式样 1 2 0 - 2 2 l o ( 4 ) m d c 技术 s l s a m 和b b i s h w a r 娅j 锄等对d b 2 提出一种高维聚簇技术 ( m u l t i d i m e n s i o n a lc l u s t e r i n g ,m d c ) 。在该方法中,首先选取合适的块因子( 每 个物理块存储的记录数) 和聚簇属性集;而后进行聚簇操作使每个物理块中所有 的记录都满足这样的条件:聚簇属性集上任何属性的值均相等;接着针对聚簇属 用于提高范围查询效率的多维聚簇算法研究第l 章引言 性集中每一个属性都建立单独的索引,通过这些索引来进行查询。这种方法的不 足之处是:如果选择的块因子大小和聚簇属性集不妥便会适得其反,不但不能提 高查询效率反而会浪费大量的存储空间。另外在选择聚簇属性集时需要一些参 数:查询的工作量、执行频率和其他一些细节2 3 2 卯。 我们可以看到大部分已有的多维聚簇方法都依赖于某些假定,如已知某些统 计数据:查询式样、记录或物理块的访问频率等。得到统计数据是一个耗时耗力 的工作,因此在数据刚刚建立时以上大多数方法都不适用。虽然也存在一些不需 要预先统计数据的方法1 2 6 ,2 7 1 ,但是它们也有自己的局限性,比如这些方法只能应 用于某些确定的索引类型( 如k d t r e e ) ,其他多维索引结构就不能使用它的数据 文件。 1 3 本文的研究思路 从前文的论述中可知,目的对提高多属性范围查询效率的研究主要集中在高 维索引上,而关于多维聚簇的研究则较少。在我们掌握的材料中,现有的多维聚 簇算法大多依赖于统计数据或高层的索引类型,这使得这些方法都存在一些局限 性。我们觉得提出能够打破这些局限,既不依赖于预先的统计数据又不受限于高 层索引类型的多维聚簇算法是有价值的。 本论文的主要工作及创新点可以总结为以下两个方面: ( 1 ) 借鉴光谱算法的思想设计了一个多维聚簇算法 首先对多维聚簇问题进行分析,将其抽象成一个数学问题并建立相应的数学 模型。接着对已在组合优化问题中得到广泛应用的光谱算法进行探讨与学习。最 后通过借鉴光谱算法的思想为解决这个n p 难问题提供了一种多项式时问内的近 似解。 ( 2 ) 设计了一个全新的多维聚簇算法f p f 算法 进一步讨论多维聚簇的研究目标,采用记录与记录集的几何中心的欧氏距离 作为衡量记录与整体关联度大小的参数,提出一个新的多维聚簇算法( f p f 算法) , 它的时间复杂度和空问复杂度都优于光谱算法。最后根据实验结果比较了这两种 方法以及传统聚簇算法在多属性范围查询上的表现。 4 用于提高范瑚查询效率的多维聚簇算法研究第l 章引言 型。 本文设计的这两种算法都不需要预先获取统计数据,也不受限于高层索引类 1 4 论文的组织结构 本文一共分为六章,组织结构如下: 第l 章,介绍了多维聚簇的研究背景和意义,并提出本文工作的研究思路及 研究目标。 第2 章,分析多维聚簇问题,将其抽象成一个数学问题并建立相应的数学模 型,以便设计下文中的多维聚簇算法。 第3 章,首先简单介绍了图论中的光谱性质;然后介绍光谱性质在组合优化 问题中的应用;最后结合本文的研究对象,借鉴光谱算法的思想提出了应用于多 维聚簇的光谱算法。 第4 章,针对多维聚簇的研究目标,提出了籽l 略f p f 算法,而后在粗略f p f 算法的基础上做进一步改进设计了最终的f p f 算法,最后对f p f 算法进行分析, 并与光谱算法进行比较。 第5 章,出于比较算法的需要,设计并实现了模拟查询系统,利用该系统针 对二维和高维数据进行模拟查询,而后整理相关数据对传统聚簇算法、光谱算法 和f p f 算法进行比较,并得出相关的结论。 第6 章,对全文进行总结,针对本文工作中的不足,提出了进一步的研究方 向。 5 用于提高范h ;i 查询效率的多维聚簇算法研究 第2 章多维聚簇问题的数学模型 第2 章多维聚簇问题的数学模型 本章将对多维聚簇问题进行详细的分析,并对它的工作原理进行讨论,而后 我们将其抽象成一个数学问题,并给出相应的形式化定义。 2 1 多维聚簇问题的分析 为了更方便地分析与描述多维聚簇问题,本节针对二维的范围查询进行讨 论,但不失一般性,其结论可扩展至高维。另外记录是以物理块为单位存储在外 存中,每个物理块中包含的记录数称为块因子。 多维聚簇问题可以总结如下:在一个数掘文件中有刀个记录,每个记录拥有 一些属性,假设其中的属性x 和y 将要被查询( 称之为查询属性,q u e 巧i n g a t t r i b u t e s ) 。多维聚簇的目标就是通过对这些记录进行重组,使得对x 和,的任何 范围查询所需的i o 访问时日j 最少。而i o 访问时间主要由访问的物理块数决定, 这些被访问的物理块都包含着若干个符合查询条件的有效记录。我们知道物理块 线性存储于磁盘的磁道中,因此对记录的重组就是给所有记录安排一个理想的线 性顺序,然后根据块因子的大小将它们存储在外存的物理块中。 从另外一个角度考虑这个问题,所有记录可根据x 和y 的值映射成二维坐标 平面上的点。这种映射是可行的,因为所有数据类型均可映射为实数。于是在x 和y 上的范围查询就变成了坐标平面上的矩形框查询。范围查询的结果就是查询 矩形框内包含点的集合( 下文中的点即指记录) 。 这有一个重要的潜在性质:在平面坐标上距离越近的点越可能被同一个查询 矩形框包含。根据这个规律,多维聚簇要做的就是给出这样的线性序列:在平面 上越靠近的点在线性顺序中也离得越近。 为了更好地理解多维聚簇的工作原理,下面以一个例子来进行 兑明,在这个 例子中块因子为3 。在二维空问中,2 1 个记录分别映射为平面上的2 1 个点( 序号 从0 到2 0 ) ,其分布如图2 1 所示,图中的小矩形为查询矩形框。 7 用于提商范围仓向效牢的多维聚簇算法研究 第2 章多维聚簇问题的数学模型 图2 1 记录在二维空间卜的示意图 从图2 1 可以看到符合查询条件( 即位于查询矩形框内) 的记录有l 、4 、5 、8 、 1 0 、1 4 、1 8 和1 9 这8 个记录。另外在查询矩形框内的这8 个记录都距离很近, 倘若我们能给出一个线性顺序,使这8 个记录包含在尽可能少的物理块中,那么 就可以减少这次查询的i o 时间。下面我们在默认顺序、顺序一( 由光谱算法得 到) 和顺序二( 由f p f 算法得到) 这三种顺序下对这次查询进行比较: ( 1 ) 在默认顺序下,0 到2 0 号记录依次排列在7 个物理块中,如图2 2 所示。 在这种情况下,符合查询条件的8 个记录分布在o 、l 、2 、3 、4 、6 这六个物理 块中,于是这次查询一共需要访问6 个块。 oi23 4 5 6 o l 23 4 56 7891 01 11 21 31 41 51 61 71 81 9 2 0 图2 2 默认顺序 ( 2 ) 经第三章将要介绍的光谱算法多维聚簇后得到顺序一,如图2 3 所示。 这时,符合查询条件的8 个记录分布在2 、3 、4 、5 这四个物理块中,这次查询 一共需要访问4 个物理块。 l ol23 4 5 6 i 1 79o732 04i l21 81 9i851 3j 4l o 1 6 61 21 5 图2 3 经光曙算法多维聚簇后得剑的顺序一 3 用于提高范嘲查询效率的多维聚簇算法研究第2 章多维聚簇问题的数学模型 ( 3 ) 经第四章将要介绍的f p f 算法多维聚簇后得到顺序二,如图2 4 所示。 这时,符合查询条件的8 个记录分布在l 、2 、3 、4 这四个物理块中,这次查询 一共需要访问4 个物理块。 i o 1234 5 6 l 1 51 221 661 0851 41 31 91 8i4 l l 2 07o931 7 图2 4 经f p f 算法多维聚簇后得到的顺序二 在例子中,这次查询在默认顺序下需要访问6 个物理块,而经两种不同算 法多维聚簇后都只需访问4 个物理块。从理论上来说经过多维聚簇后,这次查询 花费的i o 时间为原来的刀3 ,当查询量较大时对查询效率的提高是很可观的。 另外经多维聚簇后,符合查询条件的8 个记录不但分布在更少的物理块中,而且 它们分布的物理块是相对连续的,这样可以减少磁盘的寻道时间,从另外一个角 度降低这次查询的i o 时间丌销。 2 2 多维聚簇问题的形式化定义 上一节对多维聚簇进行了详细的分析,下面将给出该问题的形式化定义,这 样能让我们在后面更好地解决该问题。该问题的形式化定义如下: 在七维空间中给定一个包含门个点的点集尸= 妇,力,胁) ,找出一个双射 函数万:p 一 l ,玎) 使得瞅砌取最大值,瞰兀) 定义如下; 缈( 7 r ) = d ( p ,一,) ( 7 r ( p ,) 一万o ,) ) 2 , p t ,pj e p 其中如,厅) 是点力和历的欧氏距离。在七维空间中对任意两点只( 。,x m ,) 和p ,( x ,l ,x 2 ,x 加) 有,( p ,p j ) = 瞅力这样定义是为了便于后文设计光谱算法,事实上职力还可被定义为 ( 万) = d ( p ,p ,) 4i 石( p ,) 一万( p ,) r , p t ,p i t p 其中肌,_ ,为任意正数,( 力仍然拥有我们所需要的性质( 当加= l ,玎= 2 时,( 力 变成瞰力) 。并不是因为所= 1 ,刀= 2 是最好的参数,只是取这样的参数最适合 设计光谱算法。 9 用于提高范围查询效率的多维聚簇算法研究 第2 章多维聚簇问题的数学模型 需说明的是,公式职砷是一个经验公式。其思想是:如果一个顺序万满足 我们的要求,令p ,和印为两个高度关联的记录,p j 和刃为关联很小的记录( 空 间上距离较远的两个记录) ,于是在一般情况下有矾p ,肌) d p 玉朋) 和1 7 r p ,) 一 却2 ) i 却,办成立。因为可以很容易地将所有的记录映射到 多维空问中一个较小的区域上,在这种情况下,对于大部分f 和,有( 砌j 巩的) 2 却,劫。如果( 却j ) 砌 ( 砌,) - 咖) ) 2 如3 ,p 4 ) 却,p 2 ) ,则:却,砌 ( 7 和,) 砌2 ) ) 2 + 却3 ,p 4 ) ( 嘲) 一却4 ) ) 2 如,助) ( 却j ) 一础4 ) ) 2 + 却3 ,肼) ( 砌,) 一 武阳) ) 2 成立,这是因为当口,6 ,c ,d 为实数时,如果口 6 c d 则口d + 6 c 口 c + 6x d 。 现在我们讨论解的一致性。当对任意7 妇,) 奶) 砌女) 时有却,仇) 撕,肌) 和如,依) 芝如,劫,则称石对该问题是一致的。这就是说在一个一致性解中, 对任意的点p ,、力和肌,若在线性顺序上相对于力来说,乃更靠近肌,则在对应 的空间中乃到肌的距离小于p ,到肌的距离。 很明显一致解并不一定存在( 其实经常不存在) 。这是因为将一个更高维的点 集变映射到较低维的空间上必将丢失一些信息,不可能在低维空间中仍保存所有 的信息。因此,需要做的就是找到一个相对的最好解。 不幸的是求解使职动取最优值的7 r 是一个n p 难问题1 2 8 1 。为找到最好的万 需要遍历所有可能的排列,这在现实应用中是不可行的( 因为所有可能的排列有 玎! 个) 。因此需要设计一种多项式时间的算法求得近似最优解。 我们发现这个问题与最小线性排列问题( m i n i m u ml i n e a ra r r a n g e m e n t , m i n l a ) 相似1 2 9 。,所以可以采用在解决m i n l a 问题中十分有效的算法( 光谱算 法) 作为一种解决方案1 3 2 - 3 4 1 。 2 3 本章小结 本章首先对多维聚簇问题进行了详细分析,指出了通过多维聚簇提高多属性 范围查询效率的工作原理。通过分析知道多维聚簇的目标是尽可能地将关联度较 大的记录存储在一个物理块或相邻的物理块中,本文后面的工作都将围绕这一目 l o 用于提高范嘲查询效率的多维聚簇算法研究第2 章多维聚簇问题的数学模型 标进行。对多维聚簇问题进行分析后给出了相应的形式化定义,将多维聚簇抽象 为一个数学问题:求解使经验公式职力取最优值的双射函数万。通过建立数学模 型可以发现多维聚簇问题与最小线性排列问题有着相似之处,这为解决多维聚簇 问题提供了新的思路。 用于提高范删查洵效率的多维聚簇算法研究第3 章光谱算法的研究 第3 章光谱算法的研究 本章将介绍图论中的光谱性质以及由光谱性质引申出来应用于组合优化问 题的光谱算法。通过借鉴光谱算法的思想,针对上文建立的数学模型设计一种应 用于多维聚簇的光谱算法( s p e c t r a la l g o t h m ,s a ) 。 3 1 光谱算法的数学背景 本节首先介绍将用到的一些数学知识,而后介绍l a p j a c i 锄矩阵的几个性质。 3 1 1 相关基础知识 以下为一些将要用到的定义和性质,主要涉及离散数学中的图论与线性代数 中特征值相关的知识1 3 5 ,3 6 1 。 定义3 一l 无向图:无向图是一个二元组 kd ,记做g ,其中: 1 y 为非空顶点集合。 2 为边集,其中元素为无序对( y j ,巧) ,1 ,吁y 。 定义3 2 度:无向图g = 中,对任意顶点,矿,以v 作为端点的边 数称之为v 的度数,记做谀v ) 。 定义3 3 无向简单图:既没有平行边又没有环的无向图称为无向简单图。 定义3 4 无向简单图的邻接矩阵:对于有刀个顶点的无向简单图g = , 它的邻接矩阵为一个刀x 刀矩阵,其中第,行第列的元素劬取值如下: f l 当顶点v ,与v ,相邻时 口“2 1o 其他 定义3 5 对角矩阵:所有非对角线上元素均为0 的,刀矩阵称为对角矩阵。 定义3 6 特征值、特征向量:令爿为一个刀,矩阵,若对于一个实数五,至 少存在一个非零向量f 使得 a 芎= 砭 则称卫是矩阵彳的一个特征值,亭是矩阵爿属于特征值2 的一个特征向量。 用于提高范围查询效率的多维聚簇算法研究第3 章光谱算法的研究 性质3 1 无向简单图的邻接矩阵具有这样的性质:第f 行所有元素的和刚好 等于顶点的度吠v 山 性质3 2 无向简单图的邻接矩阵具有这样的性质:口 ,= 毋,“ 1 ,2 ,刀 。 另外当户时,劬= o 。 性质3 3 特征值与特征向量之间的关系:特征向量不被特征值唯一决定。若 a 是该矩阵彳的一个特征值,善是矩阵彳属于特征值五的一个特征向量,显然对 于任何零实数七都有错是矩阵彳属于特征值a 的特征向量。 3 1 2 光谱性质 光谱性质( s p e c t i mp r o p e r t i e s ) 是图论中一个十分有意思的性质,本文将在后 面进行阐述,光谱性质中较为关键的一个概念是l a p l a c i a n 矩阵。在文献【3 7 】中作 者给定义了无向简单图g 的l a p l a c i a n 矩阵。对于无向简单图g = ,刀疗 矩阵月为图g 的邻接矩阵, ”矩阵d 图为g 的对角矩阵。图g 的l a p l a c i a n 矩阵由彳减d 得来,也是一个玎疗矩阵,其中各元素取值如下: fd ( v ) 扛 乞= 一l f 歹且_ 与相邻 10其他 对于l a p l a c i a n 矩阵厶令五是该矩阵的一个特征值,而f 是矩阵彳属于特 征值五的一个特征向量。刀个特征二元组q 。6 ) , l ,2 ,胛) 称为图g 的l a p l a c i a n 光谱或图g 的光谱。 性质3 _ 4l a p l a c i 觚光谱具有以下三个性质3 7 1 ,为了更好地理解这些性质以 及方便后面的算法设汁,本文对这些性质进行了证明。 1 所有的特征值均为非负实数。, 证明:令a 是该矩阵的任意一个特征值,而孝= ( 磊,磊,毛) 7 是矩阵彳属于特 征值a 的一个特征向量,则有: 善t 砖= 事l 芎 z f7 孝= f r 孝 ( 3 1 ) 由上的定义可知的元素为 乞= 兰琶 ;i 多 c 3 2 , 用于提高范围查询效率的多维聚簇算法研究第3 章光谱算法的研究 由此展开式( 3 一1 ) 中的右式有 开刀一 孝r 三孝= 等d ( u ) 一茧乞 打疗刀打 = 等一喜岛嘞 = 毒( 2 等一2 彭嘞) = i ,= lj = i ,= l = 去( 2 等一2 缶白嘞) j = 1 ,= 1j = 1 ,= l = 去( 等呀一2 磊彭吩+ 等口:f ,) 一 j = i ,= if ;l ,z l,= l ,= i ( 由性质3 - 1 得) = 寺( 等一2 茧乞+ 劈) ( 置换j 与力 , f = l ,t lf ;l ,= i,i lf = l = 去( 等一2 缶参+ 劈口 f ) ( 由性质3 - 2 得) - 一 j = l ,= if i l ,= ij = lj 车l = 去( 等吩一2 石彭+ 劈嘞) l = lj = l 1一一 = 去( 参一乞) 2 陪l ,= l 由式( 3 3 ) 可知 另外有 f r 三孝o 善r 孝= 等o 由式( 3 1 ) 、式( 3 4 ) 和式( 3 5 ) 可知a o ,证毕。 2 最小的特征值为0 。 ( 3 3 ) ( 3 _ 4 ) ( 3 - 5 ) 证明:因为l a p l a c i 柚光谱所有的特征值均为非负实数,所以只需证明o 是 1 5 、磊缶 鲥 2一 等 。硝 2+ 呀白 毒 时一 。瑚 2一 呀 等 。芦 。硝 q 一2 一一 用于提高范围查询效率的多维聚簇算法研究第3 章光谱算法的研究 它的一个特征值即可。而对于证明o 是它的一个特征值则只需证明存在非零向量 x 使得 厶= 昕 ( 3 6 ) 令x = ( 1 ,1 ,1 ) 7 ,由三中各元素的定义,展开式( 3 6 ) 中的左式,由性质3 1 得: 厶= 展开式( 3 6 ) 中的右式有 一口l 。 一口2 h d ( ) o x = 一 d ( h ) 一口l , j = l f 一 斗 d ( 屹) 一口:, j 吉l “2 什 d ( ) 一 扛l n 研 显然式( 3 6 ) 成立,证毕。 3 对于矩阵属于特征值五的特征向量工= ( 而,屯,而) 7 ,当见0 时有 一 y 置= o 一 j = i 证明:对于矩阵属于特征值力的特征向量x = ( 而,屯,毛) r 有: 由此得齐次方程组 d ( v 1 ) 一口2 l 一口棚 一口l 。 一口2 月 d ( ) 而 x 2 : x _ ( d ( ,1 ) 一见) j r l 一口1 2 而一一口h = 0 一口2 l 而+ ( d ( 屹) 一兄) x 2 一一口2 j t h = 0 一口一i 一2 x 2 + ( d ( 吒) 一2 ) = 0 将方程组中各式相加得 1 6 毛屯;l p。l z 用于提高范围查询效率的多维聚簇算法研究第3 章光谱算法的研究 由性质3 - l 和式( 3 7 ) 得 于是罗毛= o 成立,证毕。 一 f = l ( d ) 一名一口f ”五= o 扭l = l j 奉 厅 y 知。= o 一 f l l ( 3 7 ) 对于图g 的l a p l a c i 锄矩阵工有刀个特征值

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论