（计算机应用技术专业论文）数据库负载自适应实时在线聚类算法的设计与实现.pdf

太原理王大学工学硬士研究生学位论文 数据库负载自适应实时在线聚类算法的设计与实现 摘要 随着互联网和信息技术的发展，数据库系统变得越来越复杂，其数据 存储规模越来越庞大，管理数据库系统也变得越来越昂贵和繁琐。在传统 方式下，主要是依靠系统管理员的手工调节。但这样做无法针对资源利用 情况进行动态的调节；同时数据库管理员的费用也为数据库系统的维护带 来沉重的负担。自主数据库系统能够自动、主动地对自身进行管理，降低 了人为数据库管理的复杂度，从而降低人力成本和系统故障时带来的额外 成本。因此，数据库自主技术对于提高数据库系统在关键应用中的应用能 力，降低数据库系统的总体拥有成本，减少硬件、软件的投资浪费等都具 有非常重要的意义。 太原理工大学的牛保宁教授已经提出了数据库系统负载自适应的基本 框架。该框架由负载检测过程和负载控制过程组成，负载特征化部件、性 能预测部件、负载控制部件和系统监测部件参与其运作。在该框架中，系 统能够根据负载的一些特性自动的完成负载的性能预测、控制等功能。 在负载自适应数据库系统中，负载特征化部件是关键部分，它首先要 对负载分类，然后根据分类的情况预测负载性能。本文主要研究负载的分 类问题。由于负载的分类要求实时在线，所以分类必须简单快捷。因此， 本文提出一种基于先验知识的增量聚类算法。 本文首先介绍了该课题的研究背景，即：骞适应数据库的发展和研究 状况，以及数据挖掘技术的一些基本情况。 太原理工大学工学硕士研究生学位论文 接着介绍了聚类技术，包括聚类的定义，数据类型，以及聚类算法的 类型和常用的一些聚类算法。 然后介绍了在本文中用到的k - m e a n s 算法和增量聚类算法的思路，计 算过程，以及优缺点分析。 最后，介绍了基于特征向量的聚类算法和基于先验知识的增量聚类算 法，并用实验验证了上述两个算法的有效性。 本文的创新之处在于使用了基于先验知识的增量聚类算法，该算法中 的先验知识是指基于特征向量聚类算法的结果。也就是说，基于先验知识 的增量聚类算法是利用基于特征向量聚类算法的结果对负载分类，而且只 是对新增负载分类，不需要对所有的负载重新分类了。而基于特征向量的 聚类算法是在离线的时候，系统自动完成的。当系统在线时，只须对新增 负载分类。这样大大节省了时间和资源。 关键词：聚类算法，增量聚类算法，基于特征向量的聚类算法，基于先验 知识的增量聚类算法 一 太原理工大学工学硕士研究生学位论文 d e s i g na n dr e a i i z 蝴o no fo n l i n e c l u s t e ri nw o r k l o a d w i t ht h ed e v e l o p m e n to fi n t e r n e ta n di n f o r m a t i o nt e c h n o l o g y ，t h ed a t a b a s e m a n a g e m e n ts y s t e mb e c o m e sm o r ea n dm o r ec o m p l i c a t e d ，i ti sh u g e ra n dh u g e r t h a ti t sd a t as t o r et h es c a l e ，a n db e c o m em o r ea n dm o r ee x p e n s i v ea n dt e d i o u st o m a n a g et h ed a t a b a s es y s t e mt o o u n d e rt h et r a d i t i o n a lw a y ，i ti sm a i n l yt h ec r a f t r e g u l a t i o no fd e p e n d i n go nt h es y s t e mm a n a g e r b u ti ti su n a b l et oc a r r yo nt h e d y n a m i cr e g u l a t i o nt ot h es i t u a t i o no fu t i l i z a t i o no fr e s o u r c e st od oi t i nt h i s w a y ；a tt h es a m et i m et h ed a t a b a s ea d m i n i s t r a t o r se x p e n s e sb r i n gt h eh e a v y b u r d e nf o rt h em a i n t e n a n c eo ft h ed a t a b a s es y s t e mt o o t h ea u t o n o m i c t i c d a t a b a s es y s t e mc a nm a n a g eo n e s e l fa u t o m a t i c a l l ya n dv o l u n t a r i l y ，r e d u c et h e c o m p l e x i t yo fa r t i f i c i a l d a t ab a s ea d m i n i s t r a t i o n ，t h u st h ee x t r ac o s tb r o u g h t w h i l er e d u c i n gt h em a n p o w e rc o s ta n ds y s t e mt r o u b l e s o ，t h ei n d e p e n d e n t t e c h n o l o g yo ft h ed a t a b a s e ，f o ri m p r o v i n gt h ea p p l i c a t i o na b i l i t yi nt h ek e yi s u s e do fd a t a b a s e s y s t e m ，r e d u c e o v e r m l p o s s e s s i o nc o s t ，d a t a b a s e o f s y s t e m ，r e d u c eh a r d w a r e ，i n v e s t m e n to f s o f t w a r e h a v ei m p o r t a n tm e a n i n g p r o f e s s o rn i ub a o n i n go ft h e t a i y u a nu n i v e r s i t yo ft e c h n o l o g yh a v e a l r e a d yp u tf o r w a r dt h ef r a m e w o r kf o rw o r k l o a d t h i sf r a m e w o r k i sc o n p o s e do f t h ew o r k l o a dc o n t r o lp r o g r e s sa n dw o r k l o a dd e t e c t i o np r o g r e s s ，t h ep r o c e s s e s i i i 太原理工大学工学硕士研究生学位论文 a r ei nt u r nm a d eu po ff o u rf u n c t i o n a lc o m p o n e n t s w o r k l o a dc h a r a c t e r i z a t i o n ， p e r f o r m a n c em o d e l i n g ，w o r k l o a dc o n t r o l ，a n ds y s t e mm o n i t o r i n g i n t h i s f r a m e w o r k ，t h es y s t e mc a np r e d i c t ea n dc o n t r o lw o r k l o a da c c o r d i n gt ot h e p e r f o r m a n c eo fs o m ew o r k l o a d i nt h ew o r k l o a da d a p t i v ed a t a b a s es y s t e m ，w o r k l o a dc h a r a c t e r i z a t i o ni st h e k e yp a r t ，f i r s t l y ，i t s h o u l d c l a s s i f i c a t e ，t h e np r e d i c tw o r k l o a dp e r f o r m a n c e a c c o r d i n g t ot h es i t u a t i o nc l a s s i f i e d t h i st e x ti s m a i n l y r e s e a r c h c l a s s i f i c a t i o n 。b e c a u s et h ec l a s s i f i c a t i o no fw o r k l o a dr e q u i r e st h er e a l - t i m e o n l i n e ，i tm u s tb es i m p l ea n ds w i f t s o ，t h i st e x tp r o p o s e sac l u s t e rb a s e do n p r i o r i t i z e di n c r e m e n t a la l g o r i t h m 。 f i r s t l y ，t h i st e x th a si n t r o d u c e dt h er e s e a r c hb a c k g r o u n do ft h i ss u b j e c t ， n a m e l y ：t h ed e v e l o p m e n to ft h ea d a p t i v ed a t a b a s ea n ds t a t eo fs t u d y i n g ，a n dt h e d a t am i n i n gs o m eb a s i cs i t u a t i o n so ft e c h n o l o g y s e n c o d l y ，t h i s t e x th a si n t r o d u c e dc l u s t e r s t e c h n o l o g y ，i n c l u d i n g t h e d e f i n i t i o no ft h ed u s t e r ，t h et y p eo ft h ed a t a ，s o m ed u s t e r a l g o r i t h m s 。 t h i r d l y ，t h et e x ti n t r o d u c e dk - m e a n sa l g o r i t h ma n dt h ei n c r e m e n t a ld u s t e r a l g o r i t h m ，n d 也e 叠t h o u g h t ，m p u t a t i o n a lp r o c e s s ，d v a n t a g ea n dd i s a d v a n t a g e 。 f i n a l l y ，t h i st e x th a v ei n t r o d u c e do nt h ec l u s t e rb a s e do nf e a t u r ev e c t o r sa n d i n c r e a s e m e n t a ld u s t e rb a s e do np r i o r i t i z e d ，a n dh a sv e r i f i e dt h ev a l i d i 锣o f a b o v e m e n t i o n e dt w oa l g o r i t h m sw i t ht h ee x p e r i m e n t t h ei n n o v a t i o no ft h i st e x th a s u s i n gt h ei n c r e a s e m e n t a ld u s t e rb a s e do n p r i o r i t i z e d ，h ep r i o r i t i z e di nt h i sa l g o r i t h mr e f e r st ot h er e s u l tc l u s t e rb a s e do n i v 太原理工大学工学硕士研究生学位论文 f e a t u r ev e c t o r s t h a ti st os a y ，t h ei n c r e a s e m e n t a lc l u s t e rb a s e do np d o r i t i z e d b a s e do nd u s t e rb a s e do nf e a t u r ev e c t o r st oc h a s i f i c a t i o n ，a n dj u s tt ot h e n e w l y - i n c r e a s e dw o r k l o a dc l a s s i f i c a t i o n ，w i l l n o tn e e da l lw o r k l o a dt o l a s s i f i c a t ea g a i n a n dw h e na l g o r i t h mi no f f - l i n e ，t h es y s t e mw a sf i n i s h e d a u t o m a t i c a l l yo nt h ec l u s t e rb a s e do nf e a t u r ev e c t o r s w h e no n - l i n ef o rs y s t e m ， o n l yn e e dt oc l a s s i f i c a t et h en e w l y i n c r e a s e dw o r k l o a d s ot h i sm e a s u r e ss a v e t i m ea n dr e s o u r c eg r e a t l y k e yw o r d s ：c l u s t e ra l g o r i t h m ，i n c r e a s e m e n t a lc l u s t e ra l g o r i t h m ，d u s t e r b a s e do nf e a t u r ev e c t o r s ，i n c r e a s e m e n t a lc l u s t e rb a s e do n p d o r i t i z e d v 声明尸阴 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：立垄超爵期：銎劣：! ! 坌： 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩蓦器或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签：名：鱼趣日期： 例8 j 。，d + 导师獬墼 隰趔& l 太原理工大学工学硕士研究生学位论文 1 1 研究背景 第一章绪论 数据库是计算机科学技术中发展最快的领域之一，也是应用最广的技术之一，是计 算机信息系统与应用系统的构成基础。随着互联网和信息技术的发展，数据库系统变得 越来越复杂，其数据存储规模越来越庞大，管理数据库系统也变得越来越昂贵和繁琐。 在一定的资源环境和负载下，如何通过对数据库系统进行调整，以减少平均等待时间， 提高系统的吞吐量，最大化数据库系统的性能，成为数据库系统的一个重要环节。在传 统方式下，主要是依靠系统管理员的手工调节。但这样做不仅使得参数调节主观化，也 无法针对资源利用情况进行动态的调节；同时数据库管理员的费用也为数据库系统的维 护带来沉重的负担。自主数据库系统能够自动、主动地对自身进行管理，降低了人为数 据库管理的复杂度，从而降低人力成本和系统故障时带来的额外成本。因此，数据库自 主技术对于提高数据库系统在关键应用中的应用能力，降低数据库系统的总体拥有成 本，减少硬件、软件的投资浪费等都具有非常重要的意义。 1 1 1 选题的背景和意义 现代网络计算在从手工管理向自主计算【1 】演化的过程中，作为网络计算核心的数据 库管理系统必须能够以自主计算的方式参与到满足网络应用性能要求的过程之中。一方 面，满足网络应用的性能要求是现代网络计算的重中之重 2 1 。另一方面，随着数据库管 理系统负载的多样化和复杂化，手工管理其性能变得越来越困难。由于网络应用所产生 的负载增长迅速和难于预测，需要为每个网络应用制订灵活的、有保证的性能要求。近 几年出现的服务器整合把多个应用集成到同一台功能强大的服务器上，造成了多个应用 对共享资源的竞争，产生了一种动态的、具有多种性能要求和资源要求的负载。如何分 配数据库系统资源来满足多样化的网络应用的性能要求和资源要求是当代数据库管理 系统必须解决的难题。简单地极大化总体资源利用率并不能保证单个应用的性能要求得 到满足。更为复杂的是，每个应用或每类负载的性能要求与它的资源要求之间没有固定 的关系。此外，还要考虑负载的重要性。解决这一难题的出路在于采用自主计算技术， 太原理工大学工学硕士研究生学位论文 数据库管理系统需要具有自适应能力来应对负载的复杂多变。 处理负载复杂多变的两种途径是资源优化和负载自适应【3 】。资源优化通过改变系统 资源的分配来应对负载的变化和系统资源的变化，从而满足网络应用的性能要求。其优 点是总体资源利用充分，缺点是资源再分配是全局性的，不能针对单一应用进行微调。 数据库系统的负载自适应是一个性能管理过程，在这一过程中自主计算数据库系统通过 自动地控制和过滤负载、并有效地使用数据库系统资源来满足网络应用的性能要求。这 是种简便实用的技术。由于它不直接分配系统资源给应用，所以其实现不需要来自数 据库系统或操作系统底层的支持，然而其控制可以细化到单个请求。 根据牛保宁教授提出的负载自适应框架可以知道，自主数据库系统的负载自适应由 负载特征化、性能预测、负载控制和系统监测四部分组成。负载分类技术是负载特征化 的基础。分类的标准是性能要求和资源要求。按照性能分类是系统区别对待不同负载类 别从而满足应用性能要求的必然选择。按照资源要求分类是为了掌握负载的资源要求特 点，从而合理分配资源，做到合理利用资源。按照性能要求分类是简单条件分类。按照 资源分类没有具体的分类条件，需要按照负载的实际情况来动态地选择，是聚类。负载 自适应是在系统运行过程中进行的，所以负载分类技术必须是实时在线分类并做到简洁 快速。然而通用聚类算法全部是离线的，不仅响应时间长，而且要求数据是静态的。因 此，我们需要寻找一种动态的快速聚类算法。 综上所说，自主数据库系统的负载自适应中的在线聚类算法的实现是有实际意义 的，具有广阔的应用前景。 1 1 2 研究现状 数据库负载自适应技术国内有许多典型意义的研究，浙江大学董金祥、陈刚教授等 在“大型通用对象关系数据库管理系统研制及其应用力课题下，提出并最终设计得到了 基于可管理自治数据库元素的、多层的、分形的自治数据库体系结构，重点对自适应数 据库系统的安全管理和并行数据库负载均衡等问题展开研究【4 】嘲。华中科技大学冯玉才 教授以数据库系统d m 4 的网络子系统和加子系统为例，研究了数据库自调节技术 的实现【6 】。网络子系统和i o 子系统自调节功能的实现建立于在线反馈控制的自调节模 型之上。从d m 4 数据库系统的自调节技术实现中可以得出一个结论，那就是数据库的 自调节技术应当建立在监控、反馈、调节这样一个循环的控制机制之上。华中科技大学 王元珍教授对基于反馈回路的自调优模型的基础上设计与实现d b m s 资源自调优工具 2 太原理工大学工学硕士研究生学位论文 进行了研究阴。该工具能够根据资源利用情况，自动找到适合提高系统运行效率的d b m s 资源配置参数。给出了实现该系统时用到的诊断树、资源关系模型和资源调整规划算法。 可以说，国内在近几年对数据库自适应方面不同侧面的研究和探讨已经逐步形成热潮。 国外，对数据库自适应的研究起步较早，早在9 0 年代就有关于数据库系统负载自 适应技术的探讨jb r o w n 等人提出了一种内存分配和并发控制的算法【8 】以求满足不同类 别负载的相应时间。在进行性能预测时，不同类别之间由于资源共享而产生的相互影响 通过性能反馈来消除。p a n g 等人提出了“p r i o r i t y a d a p t a t i o nq u e r yr e s o u r c es c h e d u l i n g ” 算法【9 】，其目标是极小化多个负载类的查询超时的数量，并使得查询超时的数量按照系 统管理员定义的比例分布于各个负载类。其技术手段是：根据资源使用情况、负载特征 和实际性能来确定负载控制、内存分配和优先级调度。这些算法的共同之处是用经验公 式来确定负载控制方案，各个负载类的性能要求分别对待。其不足之处在于性能预测不 准确，支持的负载类少。 s c h r o e d e r 等人提出了用负载控制的方法来满足多个交易型负载的性能要求【1 0 l 。其 方案是在数据库系统之前设置一个负载管理器来截取查询请求并进行控制。这样做的好 处是避免修改数据库系统，但是其缺点也是明显的，负载管理器造成的延迟过大。 在w e bs e r v i c e 领域也有关于负载自适应技术的研究。m e n a s e 6 等人【1 l j 提出了用q o s c o n t r o l l e r 来管理w e bs e r v i c e 的负载。q o sc o n t r o l l e r 监视系统的运行，通过调节系统 参数来满足系统总的性能要求。q o sc o n t r o l l e r 使用排队网络模型作为系统性能模型， 结合组合搜索算法来确定要调节的参数值。p a c i f i c i 等人【1 2 1 提出了一个用于集群环境下 w e bs e r v i c e 的负载自适应方案。在该方案中，w e bs e r v i c e 在各自的网关被分为不同的 组，各个组具有相应的效能函数。服务器资源的分配是通过组内的并发控制进行的。通 过极大化系统的效能函数产生控制方案。m e n a s c 6 和p a c i f i c i 都假设请求的资源要求是 相似的以简化系统性能模型。或许这样的假设在w e bs e r v i c e 的环境中是可行的，然而， 在大型数据库系统中，查询的大小变化范围极大。有些查询只需千分之一秒，有些查询 却要运行几十分钟。因此需要不同于w e bs e r v i c e 的解决方案。 通过分析国内外数据库负载自适应的研究状态和发展动态，最近，太原理工大学的 牛保宁教授和加拿大q u e e n su n i v e r s i t y 以及i b mt o r o n t ol a b 合作提出了数据库系统的 负载自适应的基本框架【3 】。如图1 - 1 所示，该框架由负载检测过程和负载控制过程组成， 负载特征化部件、性能预测部件、负载控制部件和系统监测部件参与其运作。 3 太原理工大学工学硕士研究生学位论文 广一一一一一一1 剽一测部件i 一 了嘛 负载控 制部件 图卜1 负载自适应框架 r f i g u r ei - it h ef r a m e w o r kf o rw o r k l o a d 负载特征化部件测量负载参数并生成相应的负载预测模型。其目的是理解并确定负 载的资源要求和性能的关系，从而为负载控制奠定基础。性能预测部件通过建立描述系 统特性的性能模型来预测系统和应用的性能。性能模型的输入参数是由负载特征化部件 产生的负载特征参数，例如：资源要求、请求到达速率；输出参数是对系统和应用性能 的预测和资源使用参数。负载控制部件确定负载控制方案以满足应用的性能要求。根据 系统底层的支持的不同，控制方案可以是直接的资源分配、系统参数的调整以及负载过 滤。系统监测部件监视系统的运行，获取负载运行的性能参数和系统资源的使用情况。 这些数据反馈给负载特征化部件用来确定负载的变化，反馈给性能预测部件用来性能模 型的动态演化，反馈给负载控制部件用来出发负载控制的动作。 负载检测过程探测负载的变化、计算负载特征参数、预测负载的趋势。如图i - i 所 示，负载特征化部件和系统监测部件参与到负载检测过程中。负载特征化部件根据采集 到的负载数据和系统监测部件反馈的信息对负载分类，提取负载特征参数，计算资源要 求。负载控制过程的实质是分配资源，也就是确定分配给每个应用或负载类的资源的多 少。这需要建立性能模型。当负载变化被检测到时，负载控制部件决定是否要重新分配 资源。如果要重新分配资源，负载控制部件会同性能预测部件产生一个最优方案并执行 之。性能预测部件、负载控制部件和系统监测部件参与其负载控制过程的运作。知识库 负责存储负载特征化、预测和控制中产生的规则和策略，并通过监测部件得到结果来不 断优化知识库中的规则和策略。 本文主要研究的内容是负载的分类技术。负载分类技术是负载特征化的基础。分类 的标准是性能要求和资源要求。按照性能分类是系统区别对待不同负载类别从而满足应 4 j卜 控程 检 载过 载 负制 负 太原理工大学工学硕士研究生学位论文 用性能要求的必然选择。按照资源要求分类是为了掌握负载的资源要求特点，从而合理 分配资源，做到合理利用资源。按照性能要求分类是简单条件分类。按照资源分类没有 具体的分类条件，需要按照负载的实际情况来动态地选择，是聚类。由于负载自适应是 实时在线进行，所有技术都以支持在线使用为前提，所以研究的是实时在线的聚类技术， 而且要做到简洁快速。本文将重点研究增量聚类技术( i n c r e m e n t a lc l u s t e r i n g ) 。聚 类技术已经得到广泛而深入的研究，然而通用聚类算法全部是离线的，不仅响应时间长， 而且要求数据是静态的。因此，需要寻找一种动态的快速聚类算法。 1 2 数据挖掘技术介绍 1 2 1 数据挖掘概述 数据挖掘技术【1 3 】是人们长期对数据库技术进行研究和开发的结果。起初各种商业数 据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到 对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过 去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传 递。现在数据挖掘技术在商业应用中已经可以马上投入使用，因为对这种技术进行支持 的三种基础技术已经发展成熟，他们是： 1 、海量数据搜集。 2 、强大的多处理器计算机。 3 、数据挖掘算法。 商业数据库现在正在以一个空前的速度增长，并且数据仓库正在广泛地应用于各种 行业；对计算机硬件性能越来越高的要求，也可以用现在已经成熟的并行多处理机的技 术来满足；另外数据挖掘算法经过了这1 0 多年的发展也已经成为一种成熟，稳定，且 易于理解和操作的技术。 在海量的数据中，是否隐藏着有价值的东西? 如何充分有效地使用这些数据，并从 中发现内在的关系及其可以说明的问题呢? 数据挖掘技术可以解决这个问题。数据挖掘 ( d a t am i n i n g ) 又称知识发现( k d d ，k n o w l e d g ed is c o v e r yi nd a t a b a s e ) 。从广义来说， 就是从巨大的数据库中提炼我们感兴趣的东西，或者提炼出我们不易观察或断言的关 系，最后给出一个有用的并可以解释的结论；简单地说就是在数据中发现模式、知识或 5 太原理工大学工学硕士研究生学位论文 数据间的关系。 在新的数据库研究方向上，数据挖掘和数据库已经走得很近。比如数据仓库技术可 以看成是数据挖掘的一个预处理的过程，移动数据库、互联网数据库、海量数据库、并 行数据库、空间数据库等新型数据库的挖掘方法是数据挖掘的前沿课题之一。 数据挖掘的特点有三个方面【1 4 】： l 、数据挖掘的数据量是巨大的。因此，如何高效率地存取数据，如何根据一定应 用领域找出数据关系即提高算法的效率，以及是使用全部数据还是部分数据，都成为数 据挖掘过程中必须考虑的问题。 2 、数据挖掘面临的数据常常是为其他目的而收集的数据，这就为数据挖掘带来了 一定的困难，即一些很重要的数据可能被疏漏或丢失。因此未知性和不完全性始终贯穿 数据挖掘的全过程。 3 、数据挖掘常常要求算法主动地提示一些数据的内在关系。新颖性是衡量一个数 据挖掘算法好坏的重要标准。 显然，数据挖掘有别于传统的数据分析方法，它常常是在没有前提假设的情况下， 从事信息的挖掘与知识提取。数据挖掘工具能够对将来的趋势和行为进行预测，从而很 好地支持人们的决策。有些数据挖掘工具还能够解决一些很消耗人工时间的传统问题， 因为它们能够快速地浏览整个数据库，找出一些专家们不易察觉的极有用的信息。： 综上，数据挖掘的定义可以从技术和商业两个方面来考虑： 1 、技术上的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括好几 层含义：数据源必须是真实的、大量的、含噪声的：发现的是用户感兴趣的知识；发现 的知识要可接受、可理解、可运用：并不要求发现放之四海皆准的知识，仅支持特定的 发现问题。 2 、商业角度的定义 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务 数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。 6 太原理工大学工学硕士研究生学位论文 数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析， 揭示隐藏的、未知的或验证己知的规律性，并进一步将其模型化的先进有效的方法。 1 2 2 数据挖掘常用技术 人工智能、数据库技术、概率与数理统计是数据挖掘技术的三大支柱。人工智能中 一些已经成熟的方法和技术在数据挖掘中得以利用，例如：人工神经网络、决策树、遗 传算法、近邻搜索算法、规则推理、模糊逻辑等。 1 、关联分析( a s s o c i a t i o n ) 关联分析用于寻找数据库中值的相关性，目的就是为了挖掘出隐藏在数据间的相互 关系。常用的关联分析技术是关联规则和序列模式。关联规则用于寻找在同一个事件中 出现的不同项的相关性。序列模式与关联模式相仿，而把数据之间的关联性与时间联系 起来。为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。 2 、分类分析( c 1 a s s i f i c a t i o n ) 分类模式是使用一个分类函数( 分类器) ，能够把数据集中的数据项映射到某个给定 的类上。分类模式往往表现为一棵分类树，根据数据的值从树根开始搜索，沿着数据满 足的分支往上走，走到树叶就能确定类别。分类分析法的输入集是一组记录集合和几种 标记。 3 、聚类分析( c l u s t e ra n a l y s i s ) 聚类分析法的输入集是一组未标定的记录，也就是说此时输入的记录还没有被进行 任何分类。聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽 可能小。 4 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 神经网络近年来越来越受到人们的关注，因为它为解决复杂度很大的问题提供了一 种相对来说比较有效的简单方法。神经网络可以很容易地解决具有上百个参数的问题。 神经网络常用于两类问题：分类和回归。神经网络是建立在可以自学习的数学模型的基 础之上的。它可以对大量复杂的数据进行分析，并可以完成对人脑或其他计算机来说极 为复杂的模式抽取及趋势分析。神经网络系统由一系列类似于人脑神经元一样的处理单 元组成，称之为节点。这些节点通过网络彼此互连，如果有数据输入，它们便可以进行 确定数据模式的工作。 7 太原理工大学工学硕士研究生学位论文 5 、决策树( d e c i s i o nt r e e s ) 决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。决策树是 通过一系列规则对数据进行分类的过程。采用决策树，可以将数据规则可视化，其输出 结果也容易理解。决策树方法精确度比较高，不像神经网络那样不易理解，同时系统也 不需要长时间的构造过程，因此比较常用。 6 、遗传算法( g e n e t i ca l g o r i t h m s ) 遗传算法是一种基于生物进化理论的优化技术。其基本观点是“适者生存 ，用于 数据挖掘中，则常把任务表示为一种搜索问题，利用遗传算法强大的搜索能力找到最优 解。具体地讲，就是模仿生物进化的过程，反复进行选择、杂交和突变等遗传操作，直 至满足最优解。 7 、最近邻居方法 将数据集合中每一个记录进行分类的方法。它的基本思想是在给定数据后，考虑在 训练数据集，与该新数据距离最近( 最相似) 的所有数据，根据这些数据所属的类别判定 新数据所属的类别。 8 、统计分析法 1 在数据库或其它数据集的各项之间建立两种关系，即能用函数公式表示确定关系的 函数关系和不能用函数公式表示但有相关确定关系的相关关系，对它们的分析可采用回 归分析、相关分析、主成分分析等。 9 、可视化技术 数据集中包含大量的数据，并且在数据集背后也暗含着各种数据模型，将如此大量 的数据可视化需要复杂的数据可视化工具。数据挖掘和数据可视化可以很好地协作。就 数据可视化系统本身而言，由于数据集中的数据量很大，很容易使分析人员变得不知所 措，数据挖掘工具可以通过可视化技术，并且根据用户的需要来表示数据，为数据分析 人员提供很好的帮助。拓宽了传统的图表功能，使用户对数据剖析更清楚。 1 2 - 3 数据挖掘的对象 知识发现的范围非常广泛，可以是社会科学、商业、科学处理产生的数据或卫星观 测得到的数据。它们的数据结构也各不相同，可以是层次的、网状的、关系的和面向对 象的数据。 8 太原理工大学工学硕士研究生学位论文 就目前来看，数据挖掘未来的几个热点包括数据仓库的数据挖掘、网站的数据挖掘 及其文本的数据挖掘。下面就这几个方面加以简单介绍。 1 、数据仓库 从数据仓库进行知识发现就是从数据集中识别出有效的、新颖的、潜在有用的，以 及最终可理解的模式的非平凡过程。从关系数据库中进行数据挖掘是当前研究的比较多 的，目前研究的主要问题： ( 1 ) 超大数据量。数据库中数据的迅速增长是数据挖掘得以发展的原因之一，这 也正是对数据挖掘研究的挑战。枚举法、经验分析法对数兆字节、数以t 计字节的数据 显得无能为力，此时数据挖掘系统必须采用一定的数据汇集方法，根据用户定义的发现 任务，选择有关的域空间，采取随机抽样的方法，对样本进行分析。 ( 2 ) 动态变化的数据。数据的动态变化是大多数数据库的一个主要特点，一个联 机系统应能够保证数据的变化不会导致错误的发生0 ( 3 ) 噪声。由于人为因素的影响，如数据的手工录入以及主观选取数据等引起的 错误数据，使得数据具有噪声。带噪声的数据会影响抽取的模式的准确性，可造成最终 结果的不确定性。发现和表示这样的模式要用概率的方法，用概率来表示。 ( 4 ) 数据不完整。数据库中某些记录的属性域可能存在空值现象，另外对某一发 现来说还可能完全不存在其所必须的记录域，这造成了数据的不完整。这些都给发现、 评价和解释一些重要的模式带来困难。， ( 5 ) 冗余信息。数据库中同一信息有时存储在多个地方。函数依赖就是一个通常 的冗余形式。冗余信息可能造成错误的知识发现，至少有些发现是用户完全不感兴趣的。 为避免这种情况发生，系统需要知道数据库中有那些固有的依赖关系。 ( 6 ) 数据稀疏。数据库对应于可能的巨大发现空间，它的实际数据记录的密度非 常稀疏。 2 、文本的数据挖掘【明 页面模式抽取需要经过文本分析过程。文本分析过程就是分析文本，从中找出一些 特征，以利于将来的使用。举个例子，在客户服务中心，把同客户的谈话转化为文本数 据，再对这些数据进行挖掘，进而了解客户对服务的满意程度和客户的需求以及客户之 间的相互关系等信息。从这个例子可以看出，无论是在数据结构还是在分析处理方法方 面，文本数据挖掘和其他方面谈到的数据挖掘相差很大。一般地，文本分析有以下几个 9 太原理工大学工学硕士研究生学位论文 基本过程： ( 1 ) 语种识别。语种识别工具能自动发现文本使用的是何种语种。它利用文本内 容的一些线索去识别语种。如果文本使用两种语种，它能确定哪部分使用哪种语种，这 个确定过程是根据相应语种的训练文本训练的，同时还能通过训练识别其他语种。它可 以根据不同的语种自动组织索引数据，不同的语种有不同的查询结果，能将文本提交给 语种翻译器。 ( 2 ) 特征提取。特征提取主要是识别文本中词项的意义，提取过程是自动的。提 取的特征与分析文本的领域有关，且大部分就是文本集中表示的概念，因此特征提取是 一种强有力的文本挖掘技术。自动识别的特征可能包括如下几部分：人名、组织名、地 名、多字词、缩写，其他如日期、货币等。分析一文本时，特征识别工具采取两种模式： 一个是单独分析该文本；另一个是先根据其他相似的文本自动建立一个词典，然后在该 文本找到词典中出现的词项。如果分析的是文集，特征提取工具则先从许多文本中找到 一些特征，然后取最优的词汇。例如，它经常监测到几个不同的词确实是同一特征的不 同变形，那么就可以取其中一个( 通常是最长的一个) 作为该特征的规范形式。另外，。也 可以给每一个词赋予一个统计测度，该统计测度是具有同一意义的单词、词组韵测度之 和。 ( 3 ) 聚类。聚类是把一个文本集合分成几组的过程。每组中的文本在某种情况下 相似。如果把文本内容作为聚类的基础，那么不同的组就对应文本集中不同的主题。因 此聚类可用来找到集合包含什么内容，即通过识别在文本组中常用的一系列术语或单词 来描述主题。聚类也可以通过文本的长度、日期等特征来进行。因此，聚类可以描述整 个文本集的内容，找到其中隐含的相似关系，从而更容易找到相似或相关的信息。聚类 后，组内的文本相似度极大，组间的文本相似度极小。 ( 4 ) 分类。分类工具是把文本分配到己存在的类中，即己存在的“主题 中。如 果由人工分类，处理如此多的数据将是一个很巨大的工程，很不实际，而通过自动组织， 把文本分到相应的主题中，使之更容易浏览、查询，是一种数据组织的有力手段。目前 关于文本分类的文献较多：a p t 用决策树技术来获取分类器；y a n g 构造了一种近邻算法 进行分类；l e w i s 采用了一个线性分类器：c o h e n 设计了一种建立在权值更新基础上的 休眠专家算法。用以上所提及的一些方法对文本分类时，首先将网页表示为关键词或概 念向量，然后计算向量之间在向量空间中的距离，作为分类依据，如i a n g 距离计算训 l o 太原理工大学工学硕士研究生学位论文 练集中每一向量与待分类向量的距离，然后选取k 个最近距离进行综合分类；而l e w i s 先构成类别向量，然后以向量的内积计算待分类向量与类别向量的距离。 3 、w e b 信息【1 6 1 。 随着网络的不断发展，网络数据的规模呈指数级增长。用户面对如此众多的资源， 一方面为能获得丰富的信息而感到高兴，但另一方面又为如何从这些信息资源中快速地 找到自己所需要的东西而担忧，因此迫切需要一种高效快速的信息资源分析工具帮助用 户快速浏览网络，并能从这些大量的信息中找出隐含的内容，减少用户的负担。面对这 种需求，w e b 信息挖掘技术应运而生。它是根据面向i n t e r n e t 的分布式信息资源特点 的一种模式抽取过程，它不仅能查找到分布式信息资源中已经存在的信息，还能识别出 大量存在于数据中的隐含的、有效的规律。目前己有一些机构开展了w e b 信息挖掘工作。 i b m 公司建造了一个名为i n t e l l i g e n tm i n e r 的工具，它主要从四个方面分析文本：从 文本中抽取关键信息；根据主题组织文本；从文本集中找到一个模式描述该集合；使用 强有力的查询来检索文本。c m u 的d a y n ef r e i t a g 则利用一阶谓词，对大学生主页定义 类与类间关系，找出一些规律，构成知识库。e t z o n i 等则通过挖掘用户访问站点的记 录信息改善站点的设计，帮助用户更快地浏览该站点。 1 2 4 数据挖掘的过程 数据挖掘是一个多步骤的处理过程，这个过程是交互和迭代的，其中许多过程需要 用户参与。 1 、确定挖掘对象 清晰地定义问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结构是 不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲目性， 是不会成功的。 2 、数据准备 这个阶段又可以细分为三个步骤：数据选取、数据预处理和数据变换。 ( 1 ) 数据选取：是根据用户的挖掘目的，搜索所有与业务对象有关的内部和外部 数据信息，从数据源中提取与挖掘相关的数据。 ( 2 ) 数据预处理：是对选取