（计算机软件与理论专业论文）话务数据实时回归分析系统的设计与实现.pdf

原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：监 矿 日期：丛型 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定。同意学校保留或向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山自、火 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或其他复制手段保存论文录i 汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 导师签名：盈魄氯二型坐 山东大学硕士学位论文 摘要 实时系统和其它一些动态环境经常会产生大量的( 可能无穷的) 流数据，如 本文中我们研究的电话网中的话务数据。这些数据由于量非常大从而不能在磁盘 上进行存储或多次扫描。我们能否对这些数据进行在线多维分析和数据挖掘，以 在情形变化时能够提醒并且帮助人们进行及时快速的、高效高质的响应? 这是一 个具有挑战性的任务。 在本文中，我们研究了一些对时序流数据进行在线的、多维回归分析方法， 主要有以下贡献： ( 1 ) 我们的分析表现在进行多维线性回归分析时只有一些少量的压缩回归 测量数据而不是整个流数据被记录下来； ( 2 ) 为了有利于在线流数据分析，我们提供了一个以回归值作为测量维、 以不规则时间轴作为时间维的部分物化的数据方模型，以便于减少保存在内存和 磁盘上的数据； ( 3 ) 在此回归分析中我们使用了一个基于异常引导的下钻方法。基于这个 设计，我们提出了有效的话务流数据分析算法并在性能分析中比较了所提出的算 法，证明了其能够在对多维流数据分析中有效地减少内存和时间的使用。 关键词：话务分析；流量采集：o l a p ：实时回归分析 山东大学硕士学位论文 a b s t r a c t r e a l t i m ep r o d u c t i o ns y s t e m sa n do t h e rd y n a m i ce n v i r o n m e n t so f t e ng e n e r a t e t r e m e n d o u s ( p o t e n t i a l l yi n f i n i t e ) a m o u n to fs t r e a md a t a ；t h ev o l u m eo fd a t ai st o o h u g et ob es t o r e do nd i s k so rs c a n n e dm u l t i p l et i m e s c a nw ep e r f o r mo i l l i n e ， m u l t i d i m e n s i o n a l a n a l y s i s a n dd a t am i n i n go fs u c hd a t at oa l e r t p e o p l ea b o u t d r a m a t i cc h a n g e so fs i t u a t i o n sa n dt oi n i t i a t et i m e l y , h i g h q u a l i t yr e s p o n s e s ? t h i si sa c h a l l e n g i n gt a s k i nt h i sp a p e r , w ei n v e s t i g a t em e t h o d sf o ro d l i n e m u l t i - d i m e n s i o n a lr e g r e s s i o n a n a l y s i so f t i m e s e r i e ss t r e a md a t a ，w i t ht h ef o l l o w i n gc o n t r i b u t i o n s ： ( 1 ) o u ra n a l y s i ss h o w st h a to n l yas m a l ln u m b e ro fc o m p r e s s e dr e g r e s s i o n m e a s u r e si n s t e a do ft h e c o m p l e t e s t r e a mo fd a t an e e dt ob e r e g i s t e r e d f o r m u l t i - d i m e n s i o n a ll i n e a rr e g r e s s i o na n a l y s i s ( 2 ) t of a c i l i t a t eo n l i n es t r e a md a t aa n a l y s i s ，ap a r t i a l l ym a t e r i a l i z e dd a t ac u b e m o d e l ，、v i mr e g r e s s i o na sm e a s u r e ，a n dat i l tt i m ef r a m ea si t st i m ed i m e n s i o n ，i s p r o p o s e dt om i n i m i z et h ea m o u n to f d a t at ob er e t a i n e di nm e m o r yo rs t o r e do nd i s k s ( 3 ) a ne x c e p t i o n - g u i d e d d r i l l i n ga p p r o a c h i s d e v e l o p e d f o r o n - l i n e ， m u l t i d i m e n s i o n a l e x c e p t i o i l - b a s e d r e g r e s s i o na n a l y s i s b a s e do nt h i sd e s i g n ， a l g o r i t h m s a r e p r o p o s e df o re f f i c i e n ta n a l y s i so ft i m e s e r i e sd a t as t r e a m s o u r p e r f o r m a n c es t u d yc o m p a r e st h ep r o p o s e da l g o r i t h m sa n di d e n t i f i e st h em o s t m e m o r y - a n dt i m e e f f i c i e n to n ef o rm u l t i - d i m e n s i o n a ls t r e a md a t aa n a l y s i s k e y w o r d s ：n e t w o r km e a s u r e m e n t ：t r a f f i cm e t e r ；o l a p ；r e a l - t i m er e g r e s s i o n a n a l y s i s 山东大学硕士学位论文 1 1 目前现状 第一章绪论 经过几年来数据仓库和o l a p 技术的研究和发展，大量的数据仓库和数据方 在应用中得到了成功地得到构建和配置，数据方在大多数数据仓库和关系数据库 系统中已经成为一个重要成分，并且在数据分析和智能决策支持中扮滨着重要角 色。 数据仓库和o l a p 技术是基于在多维空间对数据进行集成合并以促进有效 的快速的数据分析。数据全部或部分在多维和多层中聚集并以关系或多维数组形 式存储。在数据方中，维是一些分类的数据，例如产品、地区、时间等等，在本 文中主要用到时间维；测量是一些数字化的数据，象话务数据的总和、平均值、 变化等等。 o l a p 技术成功地由对静态的、事先集成的、历史性的数据的分析扩展到对 当前的、动态变化的数据进行分析，包括时序数据、科学数据、工程数据和一些 在动态环境中产生的数据，例如话务数据、电力供给、网络流量、股票交易、远 距离通信的流数据，w e b 点击流、天气和环境监测等等。然而动态环境的分析与 静态的相比，基本的差别是动态的主要依靠回归和趋势分析而不是简单的静态的 聚集。当前的数据方技术能够很好地进行静态的聚集统计，但不是设计用进行回 归和趋势分析。我们能否扩展数据方技术，构造一些特殊的数据方，以便在多维 空间中有效地执行回归和趋势分析? 这就是本次研究的任务。 本文中，我们分析了一种特殊的，具有时序特点的动态数据，称为流数据。 流数据是由动态环境产生的，具有量大、无穷尽、迅速变化的特点。采集时，这 些数据几乎常常具有低层次的、详细的、暂态的和些其它特点。为了寻找它的 些特点和趋势，有必要在某个提取层上进行回归分析，寻找数据的重要变化， 需要时下钻到一些更详细的层进行进一步的分析。 例如，我们在观察一个电话网络的话务数据时，要考虑其多种属性，也就是 数据的多个维，如考虑电话的呼损时，要考虑到时间、地点及原因等方面。其中 时间的单位有分钟、小时、日等：考虑原因时，又分为详细原因、总体因素。因 此我们在分析时不但要考虑数据的多个维还要考虑其多个层次。例如：我们采集 数据时以单个用户、分钟、详细原因( 如被叫忙、被叫不存在、缺少交换机资源 山东大学硕士学位论文 等) 为最小单位，但对大量的话务数据分析时就要在更高的层上进行，如某一局 向、某一天，呼损的原因则分用户、线路、设备等因素。平时我们只是在高层上 进行实时地观察数据，只要注意其接通率在一个正常的范围就可以了，如果发现 这些数据有明显的异常变化，则要及时下钻到下面的层上去寻找详细的原因。 概念上，对于多维分析，有人可能把这个流数据看成由一个测量、回归和一 些维组成的数据方，这些维由时间维、和些标准维( 例如地点、用户种类等) 组成。可是在实际上，是不可能实现这样的数据方，因为这种物化需要计算和存 贮大量的数据，所以要考虑一些有效的办法对这种数据进行系统的分析。 1 2 研究意义及创新点 在本次研究中，我们以话务数据为典型的想定，研究如何对流数据进行有效 的多维回归分析，并具有以下的特点： l 、 我们的研究表明在线性和多维线性回归分析中，仅仅用到少数的在 时间维和其它( 标准) 维回归测量而不是整个流数据都被用到。因为在多维空间 处理测量回归会占用更少的空间和时间，所以最好通过这样的回归测量来构建回 归( 测量) 方。 2 、 对于在线流数据分析，空间和时间是关健因素。为减少不必要的时 间和空间需求，我们建议只计算部分物化的数据方( 以回归作为测量，不规则时 间轴为时间维) 而不是全部物化的回归方，在时间维中，以不同的间隔记录时间， 以最小的间隔记录最近的时间，较远的时间则以较粗的间隔记录，间隔的粗细取 决于时间的远近和实际的应用。这种模型既满足大多分析任务的要求，又确保存 在内存的数据总数较少。 3 、考虑到在流数据分析中有限的内存空间，即使使用不规则时间轴， 保存事先计算的回归方也常常代价太高。我们建议只计算和存贮两个关键的层 ( 一些基本的方) 。( 1 ) 观察层( 0 1 a y e r ) ：是观察者或系统检测判断异常点，并下 钻到更深层去寻找相应的异常支持单元。( 2 ) 最小专注层( m l a y e r ) 是分析者想 观察的最低层，它常常是有价值或在实际中有兴趣去检测的流数据的细节。 4 、 只贮存回归方中的两个关键层使我们有一些空间来计算两层之间的 数据方。我们提供了两种办法来处理层间的数据方：( 1 ) 从m 1 a y e r 至d l a y e r 计 算数据方，但只保留一些异常单元；称为m o c u b i n g 方法；( 2 ) 沿一个普通的下 钻路径，由m l a y e r 到d l a y e r 聚集，使用计算数据方的方法计算其它的异常单元， 称为p o p u l a r p a t hc u b i n g 方法。在性能分析中，可以看到两种方法所用的内存较 少，所用的回归时间和检测异常的时间也很少。我们同时也比较了两中方法的优 山东大学硕士学位论文 2 1 数据仓库 第二章数据仓库和数据挖掘 数据仓库之父w h i n m o n 将数据仓库定义为：数据仓库是支持管理决策过程 的、面向主题的、集成的、随时间变化的、持久的数据集合。而从功能实现上， 数据仓库可以定义为：一个集成了多个分布式、自治或异构数据源上的数据储藏 室，以支持用户查询和分析。 2 1 1 数据仓库体系结构 常用的数据仓库体系结构如图2 1 所示，它集成数据源的数据，并将这些数 据放在数据仓库中，用户可咀直接从数据仓库访问数据。数据仓库由1 2 个数据源 单元和1 个存储和维护数据仓库实化视图单元组成。在数据源和数据仓库中通信 是假定f i f o ( 先进先出) ，下层每个数据源的数据库模型假定是关系数据模型， 并且假定一个数据源i 只有一个基本关系r j 。每个数据源是完全自主的，不同数 据源上产生的更新是不相关的，因而是不同步的。 图21 数据仓库体系结构 斯坦福大学提出了一个自动监测数据源更新并发送到数据仓库的体系模型， 称为w h i p s 系统，如图2 2 所示。它将数据仓库置于主动地位，可以检测每个 数据源自身的更新。一旦有更新产生，它将以异步的方式从数据源传送到数据 数据源自身的更新。一旦有更新产生，它将以异步的方式从数据源传送到数据 仓库。 山东大学硕士学位论文 缺点。 1 3 课题内容 网络测量是监控、管理电话网的基础手段，对其中话务数据进行采集和归并 后进行的实时分析是一项重要的经常性工作。本文以电话网中的话务分析为背 景，使用o l a p 技术，对数据进行了在线的、多维回归分析。 第二章介绍了数据仓库和数据挖掘的相关知识，重点介绍了数据挖掘各种不 同知识所采用的方法和技术手段；第三章介绍了o l a p 和数据方，其中对数据方 支持o l a p 目标的实现进行了描述；第四章从趋势分析和时序分析两方面介绍了 时序流数据挖掘；第五章介绍了本文的核心部分，话务数据实时回归分析系统的 设计与实现，介绍了不规则时间轴和关键层的概念，提供并比较了m o c u b i n g 和p o p u l a r p a t hc u b i n g 两种数据方计算方法的优劣并对系统性能和特点做了详细 的讨论。 山东大学硕士学位论文 2 1 数据仓库 第二章数据仓库和数据挖掘 数据仓库之父w h i n m o n 将数据仓库定义为：数据仓库是支持管理决策过程 的、面向主题的、集成的、随时间变化的、持久的数据集合。而从功能实现上， 数据仓库可以定义为：一个集成了多个分布式、自治或异构数据源上的数据储藏 室，以支持用户查询和分析。 2 1 1 数据仓库体系结构 常用的数据仓库体系结构如图2 1 所示，它集成数据源的数据，并将这些数 据放在数据仓库中，用户可以直接从数据仓库访问数据。数据仓库由n 个数据源 单元和1 个存储和维护数据仓库实化视图单元组成。在数据源和数据仓库中通信 是假定f i f o ( 先进先出) ，下层每个数据源的数据库模型假定是关系数据模型， 并且假定一个数据源i 只有一个基本关系r j 。每个数据源是完全自主的，不同数 据源上产生的更新是不相关的，因而是不同步的。 图2 ，1 数据仓库体系结构 斯坦福大学提出了一个自动监测数据源更新并发送到数据仓库的体系模型， 称为w h i p s 系统，如图2 2 所示。它将数据仓库置于主动地位，可以检测每个 数据源自身的更新。 一旦有更新产生，它将以异步的方式从数据源传送到数据 仓库。 山东大学硕士学位论文 2 1 2w h i p s 工作原理 图2 2 w h i p s 系统 如图2 2 所示，w h i p s 系统有两大主要组件组成：集成器组件，负责收集并 维护实化视图：查询处理器组件，负责相应用户的最终查询需要。当数据源产生 更新时监视器侦测更新并且发送它到集成器，集成器将数据源送来的必要信息集 成到数据仓库，然后决策支持从数据仓库的实化视图获取信息。 ( 1 ) 系统初始化和数据源启动：系统启动时，集成器公开他的身份并且创造 奄询处理器，所有其后启动的模块都与集成器相联系。 ( 2 ) 视图维护：当关系附的监测器侦测到它的数据源产生更新r j ，会立即 将这个更新转发到集成器，再由集成器转发到所有相关的视图管理器，视图管 理器则计算数据仓库实化视图的改变。如果这个过程中产生全局查询，则此查询 将被送到查询处理器，并由查询处理器联系相关的数据源包装器来进行计算。返 回的结果通过视图一致性算法作必要调整，视图管理器把这个调整后的查询结果 送到数据仓库的包装器，包装器将它作为一个单个的事务应用到数据仓库视图， 把数据仓库实化视图更新到与数据源一致的状态。 ( 3 ) 通信和消息顺序：通信消息在视图维护期间以并发方式传送，这意味着 在通信时某个模块的延迟将不会阻塞其它任何模块的处理进程。在w h i p s 体系 结构中，从一个数据源送来的消息可以通过两种途径到达视图管理器：监视器 集成器一 视图管理器。包装器一 查询处理器一 视图管理器。通过不同途径发送的 消息不能保证按顺序到达，而视图一致性算法需要知道当它收到一个查询结果 山东大学硕士学位论文 时，视图管理器之前的所有修改。一个可行的方法是让查询结果也经过集成器来 传送，并且从集成器到视图管理器同步传送更新，但那样就需要更多昂贵的同步 消息。另一个方法是用序号来解决，每一个监视器有他自己的序号，每个更新送 到集成器时都用一个序号标汜。 2 2 数据挖掘 随着计算机时代的到来和各行各业信息化、数字化的发展，产生了大量的 数据。传统的数据库技术和统计方法已不能满足人们对数据进行更高层次分析和 利用的要求，导致了“数据爆炸但知识贫乏”的现象，迫切需要新的技术和自动 化工具来帮助人们将海量数据转化为有用的信息和知识， 数据挖掘技术应允厩 生。 所谓的数据挖掘( d m ，d a t am i n i n g ) 就是从海量的数据中提取隐含在其中 人们事先未知的，但又是潜在有用的信息和知识，并将其表示成最终能被人理 解的模式的高级过程。数据挖掘产生于八十年代末期，是目前国际国内的研究 热点。它是数据库知识发现k d d ( k n o wl e d g ed i s c o v e r yi nd a t a b a s e ，缩写为k d d ) 的核心技术。数据挖掘的显著特点就是它强大的数据处理能力，能从大量的数 据中发现有用的规律、规则、联系、模式等知识。包括聚类分析、分类分析、时 间序列相似性分析、关联度分析、回归分析等。 数据挖掘是数据库研究中的一个极富应用前景的新领域。这一领域可以定义 为在大型数据库中高效地提取人们感兴趣的知识。这些知识是隐含的， 事先未 知的潜在有用信息。 对于数据挖掘，可作出如下不同的分类模式： ( 1 ) 依据所挖掘的数据库的种类进行分类。若挖掘系统从关系数据库中发现 知识，则相应系统为关系数据挖掘系统。其它数据库系统如面向对象的数据库、 演绎型数据库、空间数据库、时间数据库、多媒体数据库、异质数据库、主动数 据库、遗留数据库和i n t e m e t 信息库均可作为挖掘系统挖掘的对象。 ( 2 ) 依据挖掘知识的种类进行分类。数据挖掘系统可以发现几种典型的知 识，包括关联规则、特征规则、分类规则、区分规则、聚类规则等。 ( 3 ) 依据采用的技术进行分类。常用的数据挖掘技术主要有人工神经网络、 遗传算法、决策树、邻近搜索、规则推理、模糊逻辑等。 由于按挖掘知识的种类进行分类能够清晰地展现不同的数据挖掘需求和技 术，所以本文主要介绍挖掘各种不同知识所采用的方法和技术手段。 山东大学硕士学位论文 2 2 1 关联规则的挖掘 在数据挖掘的研究领域，对于关联规则挖掘的研究开展得比较积极和深入。 关联规则挖掘就是要找出隐藏在数据间的相互关系。它挖掘的般对象是事务数 据库，如对于零售业的销售事务数据库，决策者们总希望能够发现销售项目间 的主要关联，即一个事务中的某些项目的出现是否蕴涵了同一事务中其他项目 的出现。此问题的数学描述如下： 设i = i 1 ，i 2 ，i m 是m 个不同项目的集合，d 是一个事务集合。其 中的每一个事务t 都包含了属于i 的若干个项目， 即t i 。每个事务都有 个标识符t d 。设x 是一个项目集，称事务t 包含x 当且仅当x t 。一条关 联规则就是形如x j y 的蕴含式，其中x c i ，y c i ，且x a y = 中。如果事务 d 中有s 的事务在包含x 的同时也包含y ，则称规则在事务集d 中具有置信度 c 。如果事务集d 中s 的事务包含x u y ，则规则x j y 在d 中具有支持度s 。 置信度指示着蕴含的强度， 而支持度则指出了规则中模式出现的频度。具有高 置信度和高支持度的规则称为强规则。关联规则挖掘的任务就是在大型数据库中 发现强规则。在进行关联分析时，通常把问题分解成以下两步来解决： ( 1 ) 发现大项目集。所谓大项目集，是指其事务支持度高于预定义最小支 持度s 的项目集。 ( 2 ) 利用大项目集产生关联规则。 关联规则挖掘的速度和效率由第一步决定。所以很多研究都集中在这一问题 的解决上。a p r i o r i 算法和d h p 算法以及s e t m 算法都是关联规则的快速挖掘算 法。现在出现的许多新算法大多是在此基础上的改进。一般来讲，通过精减数 据库扫描、可调精度挖掘、并行数据挖掘等方法可以提高关联规则挖掘的效率。 2 2 2 特征规则挖掘 在数据库的原始概念层，数据和对象往往包含很详细的信息。人们希望能 将大数据集中的数据进行总结概括，并将其在更高的概念层次上呈现出来。如： 经销商们可能希望对一些销售活动中的交易集合进行概括、总结从而得到更一般 性的描述。这就要求数据挖掘系统具有数据概括的功能。数据概括是将数据库中 的大量相关数据从较低概念层次抽象为较高层次的过程。通常有两种方法可以有 效地进行数据概括： ( 1 1 数据方法 数据方法又称为多维数据库、联机分析处理、实视图。这种方法的思想是把 9 山东大学硕士学位论文 那些经常被查询到的尤其那些涉及聚集函数如计数、求和、求平均值、求最大、 最小值等的代价较高的计算进行具体化， 并将这些具体化的视图存储到多维数 据库( 数据方) 中以便于决策支持、知识发现及其它应用。聚集函数可以通过对 不同的属性集进行分组而预先计算。同一属性中的值也可被分组形成层次或网格 结构。可以通过上滚( r o l l u p ) 或掘进( d r i l l - d o w n ) 操作对一个多维数据方分别进行 概括和细化。上滚操作降低数据方的维数，把属性值提升到较高概念层次，而 掘进操作则相反。在数据分析中，由于许多聚集函数可能经常需要反复计算，因 此， 将它们事先计算并存储到多维数据方中可以保证快速响应以及从不同角度 和不同抽象层次上查看数据。 ( 2 ) 面向属性的归纳方法 面向属性的归纳方法是一种基于归纳的联机数据分析技术。这种方法采用类 s q l 数据挖掘查询语言对数据库进行数据挖掘查询以收集相关数据。在此相关 数据集上采用包括属性迁移、概念树攀登、属性闽值控制等一系列数据归纳技术 对其进行数据归纳【l 】。归纳出来的数据以归纳关系形式表达，在此归纳关系上 可以进行许多其它的操作或转换，将归纳后的数据转换成不同的知识或将其映 射成不同的形式。如：可以执行掘进或上滚操作来从不同的抽象层次上查看数 据；归纳关系可以被映射成可视化的总结表、图、曲线等呈现出来。 2 2 3 分类规则挖掘 数据分类是指在数据库的各个对象中找出共同特性，并按照一定的分类模 型对它们进行分类。为了构建这样的一个分类模型，需要一个样本数据库e 作 为训练集，e 中的每一个元组与大型数据库w 中的元组包含着同样的属性集， 并且每一个元组有一个已知的类标识。分类的目标是首先分析训练集数据，利 用数据的可用特征为每个类建立一个精确的描述或模型， 然后把这些模型用作 对数据库w 中其它数据进行分类或建立一个更好的描述，即分类规则。 常用的分类方法有基于决策树的分类方法、统计方法、粗集方法等。决策树 方法是利用信息论中的信息增益寻找数据库中具有最大信息量的属性字段， 建 立决策树的一个结点，再根据该属性字段的不同取值建立树的分枝，在每个分 支子集中重复建立树的下层结点和分支的过程。国际上最早的、也是最有影响的 决策树方法是q u i u l a n 研究的i d 2 3 方法【i 1 。i d 2 3 是一个典型的决策树学习系 统，它采用自顶向下不可撤回的策略，只搜索全部空间的一部分，能够保证 发现一棵简单( 并非总是最简) 的树。另外，线性回归和线性判别分析技术是用 于分类的经典统计方法。 山东大学硕士学位论文 2 2 4 聚类规则挖掘 将具体的或抽象的对象按照相似程度分类的过程称为聚类或非监督分类。它 与分类分析方法不同。聚类分析的输入集是一组未标定的记录，也就是说此时 输入的记录还没有被进行任何分类。其目的是根据定的规则，合理地划分记 录集合，并用显式或隐式方法描述不同的类别。而所依据的这些规则是由聚类 分析工具定义的。由于聚类分析可以采用不同的算法，所以对于相同的记录集 合可能有不同的划分1 2 j 。 在数据挖掘中，数据聚类是在大型多维数据集中通过距离测量发现聚类和 密集区。给定一个大型多维数据点集，数据空间通常并不是由数据点所均匀占 据，数据聚类需标识出稀疏区和密集区，发现数据集中数据的整体分布模式。 ( 1 ) 基于随机搜索的聚类规则挖掘 c l a r a n s 是一个基于随机搜索的聚类算法，它起源于统计学中的p a m 和 c l a r a 两个聚类算法。c l a r a n s 算法只搜索数据集的一个子集，并且在任 何给定的时间内它并不把自己限制于任何样本。这与c l a r a 不同，c l a r a 在 每一个搜索阶段均有一个固定样本，而c l a r a n s 在每一步搜索中都是随机地 选择样本。聚类过程可以呈现为搜索一个每一结点都可能为一个潜在解决方案的 图。新生成的聚类称为当前聚类的邻居，如果邻居比当前值好，则转移到邻居， 并重新处理过程；否则当前聚类产生个本地最佳值，然后随机选择一个结点 重新开始一个新的本地最佳值的搜索过程。一些新技术用来改进c l a m n s 聚 类算法的性能，其中主要是将原算法同r 树相集成，来消除原算法中存在的 缺陷。 ( 2 ) 特征聚类与特征聚类树 r 3 树并不总是可靠，并且r 3 树的构建可能是很费时的。于是，在r 3 树 基础上产生了另一种算法bi r c h ， 用来对大数据集聚类。该算法引入两个概 念：特征聚类和特征聚类树。一个特征聚类c f 是个三元组，总结了关于子 聚类的信息。一颗特征聚类树是带有两个参数：分支因子b 和闽值t 的平衡树。 分支因子指定了最大孩子数。阈值参数指定了存储在叶子结点的子聚类的最大直 径。通过改变闽值就可以改变树的大小。非叶子结点存储了它们孩子结点的c f 值的和。因此，它们总结了关于自己孩子的信息。当有数据点插入时，特征聚 类树被动态创建。如果插入操作以后存储在叶子结点的子聚类的直径大于阈值， 则叶子结点和其它可能的结点将分裂。在新结点的插入操作以后，关于它的信 息就传递到树根【“。如果存储一棵特征聚类树所需内存大小大于现有可用内存， 那么就要重新调整阂值并且要重建特征聚类树。 山东大学硕士学位论文 2 2 5 基于模式的相似性搜索 当在时间或时空数据库中搜索相似的模式时，通常用到两种查询： ( 1 1 相对于某一对象的相似性查询。这种查询对一组对象进行搜索以发现其 中的与被查询的对象间的距离在用户定义距离之内的一些对象。 ( 2 ) 所有的相似对查询。目的是发现所有的元素对，元素对中两两之间的 距离在用户定义的距离范围之内。解决相似性搜索问题，首先必须确定相似性 度量尺度。主要的相似性度量尺度有欧几里德距离和相关系数。 目前已经出现的模式相似性搜索方法很多。其中的层次扫描是一种特征抽取 和匹配算法，它使用相关系数作为目标序列和存储序列间的相似性度量，以目 标序列为基础，对存储序列的抽取特征执行适应性扫描。为了提高搜索效率，等 级扫描算法首先选择具有最大辨别力的特征子集来执行相关匹配，可能只有小部 分序列通过测试。然后下一个具有最大辨别力和特征被用来匹配，这个过程一 直重复至所有特征都用完。 山东大学硕士学位论文 第三章o l a p 和数据方 联机分析处理( 简称o n l i n ea n a l y t i c a lp r o c e s s i n go l a p ) 技术是近年来数据 库领域的研究重点和热点。它由关系数据库之父一i b m 公司的e f c o d d 于1 9 9 3 年 提出，e ，f c o d d 还同时提出了关于o l a p 产品的1 2 条评价准则，这些准则虽未得 到工业界的一致公认，但却使人们对o l a p 的概念、功能的认识基本趋于一致。 建立在数据仓库基础上的o l a p 以多维分析为基础，刻画了管理和决策过程中对 数据进行多层面、多角度分析处理的基本要求，满足了实际的需求，为企业管理 和决策活动提供了一个新的工具，也为决策支持系统的研制提供了新的思路。 o l a p 已成为智能决策支持系统中不可缺少的重要工具。如今，o l a p 技术本身 得到了极大发展，产品被推广使用。 o l a p 功能的强弱是决策支持系统性能的重要表现，也是o l a p 能否被广泛 应用的关键。从概念角度讲，o l a p 应该具有如下4 项功能( 3 】：11 ) 查询：通过一 个简单的通用界面，实现一个通用的综合查询，并能形成强有力的特定查询；2 ) 重构：灵活地定义维和维层次，以便产生多层次、多角度的数据视图，重构多维 数据库中的信息；3 ) 分类：用合适的方式分类或组合数据集，便于后期概括；4 ) 概括( 聚集) ：将数值型多集合值映射到单一综合值。 o l a p 支持最终用户对企业数据进行动态的多维分析，o l a p 分析过程是： 根据数据分析的要求从原始数据中构造各种数据方= ) 对数据方执行有关的操作 = ) 把结果返回给用户，所以决策者的查询无菲就是对数据方进行某种操作的过 程。数据方支持了o l a p 目标的实现，使得从大量细节性事务数据中提取有用信 息这个过程变得容易。它是数据仓库和o l a p 技术的核心概念，是把数据组织到 多维数据库中的技术。以多维方式组织和显示数据，是多维数据库的一个基本功 能。 3 1 数据方 一个数据数据方是一个数据集合，通常由数据仓库的子集构造，并组织和汇 总成一个由组维度和度量值定义的多维结构( 见图3 1 ) 。虽然术语锁2 据方” 使人想起3 个维度，但一个数据方可包含1 2 8 个维度。数据方在处理时，预先计算 好一些汇总数据，称为聚合，聚合提供了一种便于使用、快捷且响应时间一致的 数据查询机制。数据方在逻辑上般由一个事实数据表和多个维度表构成种星 山东大学硕士学位论文 形构架。构架的核心是事实数据表。事实数据表是数据方中度量值的源，维度表 是数据方中维度的源。数据方涉及的概念如下： ( 1 ) 维度是数据方的一种结构特性，是描述事实数据表中数据级别的有组织 的层次结构。这些级别通常描述相似成员的集合，用户要根据它们进行分析。例 如，某个地理维度可能包括国家、省以及城市等级别。 ( 2 ) 度量值是在数据方内，基于该数据方的事实数据表中某列的一组值，它 们通常是数字。度量值是进行聚合和分析的主要值。 ( 3 ) 成员属性是维度成员的一个可选特性，它为最终用户提供成员的其它信 息，仅从属于级别。成员属性在级别中创建，该级别应包含应用该成员属性的那 些成员。 3 2 数据方建模 图3 1 数据方示意图 数据方建模或多维数据模型是数据方研究的核心问题，理论界在数据方建模 方面所作的工作虽然不多，但探索性的研究却一直未停止过。文献【4 。j 提议将表 单看作是一个维域到指标域的笛卡尔积函数，导致了维和指标的非平等处理，这 反过来造成内容和结构无法分离。其中文献1 4 j 定义的操作符过于复杂，文献1 5 】则 导致立方及普通关系两种框架的非均衡处理。g y a s e n s 等在文献【6 中提出了一个 表格式二维数据库模型和一个表格式代数查询语言，可适用于所有可能的重构转 换，但没有分类函数和概要函数。后来文献f 3 j 提出了通过正交指令实现多维数据 概念模型。这个模型定义代数及微积分并使其等价，能够清楚地分离出结构和内 容，允许采用相当简单和透明的方法定义数据处理语言，特别是在表示数据方操 作符时十分简单。另外文献提出了数据方的三维数据模型以及应用于之上的 o l a p 操作的关系代数，模型简单、通用且直观。 近年来国内也展开了对o l a p 技术的研究并具有一定成果，文献1 7 定义了数 据方，提出了一个支持多维分析语义描述的形式化工具一数据方代数，概念清晰、 山东大学硕士学位论文 简单而易于理解，但对维层次以及基于维层次的钻取操作未深入探讨。文献 8 】 以偏序和映射为基础，提出了一种能够充分表达数据仓库复杂数据结构和语义的 多维数据模型，并提供一个以o l a p 操作为核心的操作代数，支持层次结构间的 复杂聚集操作序列。它利用层次结构间聚集函数的约束，提出定义层次游标的方 法来解决维层次结构选择问题，但由于在操作定义中包含了完全的维层次细节， 当维结构被改变时，o l a p 操作不得不重新定义。大连理工大学软件工程研究室 提出利用有向图机制定义复杂层次结构，也可以灵活解决变层次结构问题。 理论界共提出了1 0 多种多维数据模型肼2 8 2 9 删】，它们在数据结构的表达 能力上都有一定不足，都没有提供十分完整的数据方操作代数，不利于o l a p 查询的优化处理，也较少提供与维层次结构相关的o l a p 操作1 8 而相对来说， 文献口。9 】提出的多维数据模型是比较好的具有很强表达能力和比较完整o l a p 操 作的多维数据模型。 3 3 数据方计算 聚集与分层是o l a p 计算涉及的最重要的两个方面。 数据方计算的核心是聚集，聚集计算的性能如何往往成为应用中的瓶颈。聚 集是提前计算好的提炼数据，是为o l a p 系统提供快速查询的响应机制。在o l a p 应用中，响应速度是主要目标，为了使交互式的分析( 在几秒钟之内作出响应) 成 为可能，o l a p 数据库通常预先计算好不同细节层次和不同维属性集合上的聚 集。把所有可能的聚集( 即全聚集) 都计算出来，可以得到最快的系统查询响应时 问，但即使暂且不管计算聚集所花费的c p u 处理时间，只是随着维数的增加，这 样做就有可能导致数据爆炸( 在商业应用中，全聚集占据2 0 0 倍于原始数据的空 间) ，另外它的更新维护也需要花费很长时间，所以计算聚集时应在聚集所占用 的空间、c p u 处理时间和0 l a p 系统查询响应时间之间有一个权衡。 理论界在研究有效数据方算法、利用聚集数据来支持查询优化方面做了许多 工作叫1 2 1 4 川13 2 2 5 1 以及也进行了聚集更新维护的研究盼1 6 1 ，如今商业上关 系数据库管理系统产品的最新版本已提供了聚集优化和原始数据变化时聚集自 动更新功能。另外为避免数据爆炸，研究工作集中在限定空间中如何选择聚集层 的最佳子集【1 2 17 1 、聚集和索引结合【1 8 】上，这些都是实践上预先做出部分聚集的 方法，i n f o r m i x 公司的m e t a c u b e 产品和m i c r o s o f t 的d e c i s i o ns u p p o r ts e r v i c e s ( p l a t o ) 都采用了这种方法。 实践上预先做出部分聚集的算法的适用性前提是能利用底层聚集计算高层 聚集，所以聚集的复杂性在很大程度上还依赖于维层次中每个节点的展开。关于 山东大学硕士学位论文 聚集查询的多种有效办法已经开发，相比而言，关于分层结构的研究进展却不太 大，因为现有方法中没有将维和层次放在首要位置，所以包含维分层和它们之间 相互作用的基本属性查询相当难读写和优化。在这方面，l e h n e r r 研究了大范围 o l a p 应用中的建模问题，提出了一个嵌套的多维数据模型1 2 朝，b a r a l i s 拓展了数 据方操作去处理带分层结构的多维聚集，他们的主要观点是处理维功能独立的情 形所引发的分组冗余，从而找到了层次数据方优化的基础。 理想的维层次结构是o n t o ( 根到叶的所有路径等长) 、c o v e r i n g ( 邻近的双亲 和孩子相关) 和s t r i c t ( 每个孩子只有一个双) 亲的，但实际应用中不会完全遵从这 个固定规律，即出现了许多变层次结构问题。在这方面过去只有文献【1 9 1 作了关于 人工完成n o n c o v e r i n g 层次结构的汇总，近来文献1 2 0 1 第一次给出了把不规则的维 层次和事实一维关系转换成良构的算法，解决了现实中n o n - o n t o ，n o n c o v e r i n g ， n o n s t r i c t 的交层次结构问题。文献【2 ”是专门对数据仓库中分层结构的研究，它 克服了雪花模型支持维层次结构建模和表达有用o l a p 查询的局限性，将维数分 层概念摆在首要位置，很自然地扩展了分层结构的相关数据模式，另外还建立了 s q l ( h ) 模型，拓展s q l 语言为s q l ( h ) 语言，基于层次i o i n 算法，应用维索引 给出了直接计算s q l ( h ) 查询的算法，改变了以往涉及维层次结构查询冗长、难 写、难读、难优化的局面。 3 4 数据方操作 用户对基础数据多角度、多层面的一系列查询操作，我们称之为数据方操作， 包括选择( s e l e c t ) 、切片( s l i c e ) 、切块( d i c e ) 、旋转( p i v o t ) 、向下钻取( d r i l l d o w n ) 、 向上汇总( r o l l u p ) 等。19 9 5 年，g r a y a l 在这个领域发表了一篇很有影响力的论 文【9 1 ，提出了数据方操作符的建议，扩展t s q l 使其包含新的聚集类型，以后的 工作仍停留在逐渐扩展s q l 、开发一种和s q l 兼容的多维查询语言的思路上1 4 2 ”。 但许多类似s q l 语言的扩充没能实现重构和复杂聚集的能力。多维查询语言 n d s q l l 26 提出关系算法的扩展，能够解决大量不同成员数据库模式间的冲突， 能传递包含大量粒度聚集的o l a p 查询，包括了像c u b e 、r o l l u p 以及d r i l l d o w n 等操作符号，它直接重构任意数据库中的数据、直接针对任意其他数据库模式而 不需要外援及用主语言进行编程这一点上比已知查询语言优势明显。文献 3 5 1 研究 了数据方某一维中不同的层次类型，讨论了涉及层次的o l a p 操作特点，研究了 r o l l u p 和d r i l l d o w n 操作的不同行为，定义了隐含维概念，同时描述切片概念为 两种类型：p s l i c e 、t s l i c e ，并提出了改变维层次结构的操作符集，为模式设计和 数据分析阶段提供了一定的建模弹性。另外，区间聚集也是数据方上的典型操作， 6 山东大学硕士学位论文 文献1 2 7 】提出了刚引起重视的数据方上的区域查询求和问题，在算法上采用双重相 关前置求和技术来提高数据方的区域求和查询效率。这之前，文献弘5 j 提出了用前 缀汇总数组结构有效处n r a n g e s u m 、r a n g e c o u n t 、r a n g e a v e r l h - j 题，对于 r a n g e m a x 、r a n g e m i n 建议了基于四象限树扩展的层次树，而文献 3 3 1 提出了用最 大覆盖解决r a n g e m a x 、r a n g e m i n 处理的问题，效果比文献【3 4 】提出的好。 目前的o l a p 技术提供的集合运算符( 如求和、求平均) 和导向运算符( 如选 择、旋转、上钻与下钻) 必须完全靠分析员的直觉来操作，这使得分析过程变得 冗长，数据维数和长度的错误也会增加，目前有这样一种趋向，即理论界正着力 于加强o l a p 产品的性能，把o l a p 推向交互分析新时代一自动化时代。这个 领域最新的动向是试图通过挖掘源数据来加强o l a p 产品，如使用决策树分级器 来发现影响产品效益的因素 2 “、用多级集合中的关联规则逐渐地发现一个维中成 员间的细节关系1 2 。另外s a r a w a g a 发现分析员进行细节开发的一个重要原因是 为了研究细节数据的不规则性或数据的特例，根据这个发现，他提出了一种操作 方法发现那些特例，将分析员引导到他们感兴趣的领域，提出了单操作符 2 4 1 并开 发了此单项操作符的信息理论化公式用于表示那些简洁的、易于解释的原因，设 计了动态编程方法，减少了o l a p 分析过程的冗长和错误且使分析成为自动的交 互过程。同时，理论界也存在类似的另一思想一联机分析挖掘( o n l i n ea n a l y s i s ， 简称m i n i n go l a m ) ，它集成了技术和数据挖掘技o l a p 术，实现了二者的优势 互补，是一种交互式的分析方法。 3 5 小结 由c o d d 首先建立并由众多研究人员发展起来的关系数据库的成功应主要归 功于数据模型具有清晰的逻辑依据，虽然技术在理论界和实践界都得到重视，并 处于不断发o l a p 展中，然而到目前为止它还缺