（计算机应用技术专业论文）基于索引的高效聚类孤立点算法分析.pdf

山东大学硕士学位论文 摘要 随着计算机应用的普及，尤其是数据库技术的广泛使用，以及互 联网应用的不断深入，业务数据量急剧增长，事实上，每两三年数据 就会翻倍。不幸的是，基于调查，9 3 以上的数据在进入业务系统以后， 从未得到使用。 面对海量数据，我们往往无所适从，无法发现数据中存在的关系 和规则，无法根据现有的数据预测未来的发展趋势， 导致了“我们淹 没在数据的海洋中，但却缺少知识”的现象。我们希望运用数据挖掘 技术从这些数据当中挖掘出知识来。大量数据的背后隐藏了很多具有 决策意义的信息，通过对海量数据的分析，发现数据之间的潜在联系， 为人们提供自动决策支持。数据挖掘利用各种分析工具在海量数据中 发现模型和数据间关系的过程，使用这些模型和关系可以进行预测， 它帮助决策者寻找数据间潜在的关联，发现被忽略的因素，因而被认 为是解决当今时代所面临的数据爆炸而信息贫乏问题的一种有效方 法。 本文对数据仓库技术和数据挖掘算法进行了研究，并对数据挖掘 算法根据实际需要作了改进： ( 1 ) 对聚类中的孤立点算法进行了分析，给出了算法描述，并就 算法的复杂度进行了分析。 ( 2 ) 针对当前的孤立点分析中需要对数据库进行多次扫描，计算 的复杂度较高，代价昂贵等问题，提出根据实际情况，提出了基于线 性时间选择算法计算最小距离点从而求解孤立点的设计思想，降低了 计算的复杂度，提高了效率，提高了数据挖掘的速度。 本文对数据挖掘技术中孤立点进行了算法分析研究，所形成的算 法对分析预测有一定的指导意义，该方法对孤立点分析中其他方面的 应用也有着较大的参考价值。 山东大学硕士学位论文 关键字：数据仓库、数据挖掘、孤立点、数据挖掘可视化 山东大学硕士学位论文 a b s t r a c t b u s i n e s sd a t aq u a n t i t yi si n c r e a s i n gv e r ys h a r p l y ，w i t ht h ep o p u l a r a p p l i c a t i o n o f c o m p u t e r a n dt h ef a s t p r o g r e s s o f i n t e r n e t ， e s p e c i a l l yt h ew i d eu s eo fd a t a b a s et e c h n o l o g y i nf a c tt h ed a t aq u a n t i t y isd o u b l ee v e r y2o r3 y e a r n e v e r t h e l e s s ，a c c o r d i n gt oi n v e s t i g a t i o n ， o v e r9 3 d a t ah a sn e v e rb e e nu s e da f t e ri tw a sp u ti nb u s i n e s ss y s t e m f a c i n gs oa b u n d a n td a t a ，w ed o n tk n o wh o wt od e a lw i t ha n dc a n t f i n dt h ee x i s t i n gr e l a t i o n sa m o n gd a t aa n dt h e i rr u l e s ，w ec a n ta l s o p r e d i c tt h ef u t u r ed e v e l o p i n gt r e n df r o me x is t i n gd a t a l e a d i n gt o t h e p h e n o m e n o nt h a t “w e a r e s u b m e r g e di n d a t a o c e a n ，b u t s h o r to f k n o w l e d g e ”s ow eh o p et h a tw ec a r lg a i nk n o w l e d g eb yd a t am i n i n g t e c h n o l o g y t h e r ei sm u c hi n f o r m a t i o nf o rd e c i s i o n m a k i n gu n d e ram a s s o fd a t a f i n d i n go u tp o t e n t i a lr e l a t i o n sa m o n gd a t ab ya n a l y z i n gp l e n t y o fd a t ap r o v i d e su ss u p p o r tf o ra u t od e c i s i o n m a k i n g d a t am i n i n gi sa p r o c e s st h a tw el o o kf o rm o d e l sa n dr e l a t i o n sa m o n gd a t af r o mam a s so f d a t ab ya l lk i n d so fa n a l y t i ct o o l s w i t ht h o s em o d e l sa n dr e l a t i o n sw e c a np r e d i c t t h o s eh e l pd e c is i o n m a k e rt of i n dp o t e n t i a ll i n k sa m o n g d a t aa n dn e g l e c t e df a c t o r s s od a t am i n i n gi sl o o k e da sa ne f f e c t i v e m e t h o dt os o l v et h ep r o b l e mt h a t f a c i n gt o om a n yd a t aw ec a n tg e t e n o u g hi n f o r m a t i o n ， i nt h i sp a p e r ，t h ea u t h o r i m p r o v e s t h ed a t a m i n i n ga l g o r i t h m a c c o r d i n g t o p r a c t i c a lr e q u i r e m e n tb y ar e s e a r c ho ft h ed a t a b a s e w a r e h o u s et e c h n o l o g ya n dd a t am i n i n ga l g o r i t h m ( 1 ) t h i sp a p e ra n a l y s e st h eo u t l i e r sa l g o r i t h mi nc l u s t e r ，g i v e s a d e s c r i p t i o no ft h i sa l g o r i t h ma n de x p l a i n si t sc o m p l e x i t y ( 2 ) a i m i n gt ot h ee x i s t i n gq u e s t i o n ，s u c ha sn e e d i n gs c a nd a t a b a s e 。v 山东大学硕士学位论文 t o om a n yt i m e s ，h i g hc o m p l e x i t ya n de x p e n s e s ，t h isp a p e rr a i s e s ac o n s t r u c t i o nt h i n k i n gw h i c hc o m p u t eo u t l i e r sb a s e do ua s e l e c t i v ea l g o r i t h mo fl i n e a rt i m e i tl o w st h ec o m p l e x i t yo f a l g o r i t h ma n de n h a n c e sc o m p u t i n ge f f i c i e n c y t h ea l g o r i t h mi nt h isp a p e rp r o v i d e sd i r e c t i v es i g n i f i c a n c ef o ro u r a n a l y s i sa n dp r e d i c t i o na n di s ag o o dr e f e r e n c et oo t h e ra p p l i c a t i o n so f o u t l i o r sa n a l y s is k e y w o r d s ：d a t a b a s ew a r eh o u s e d a t am i n i n g o u t l i e r s v i s i b i l i t yo fd a t am i n i n g v i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。 本人完全意识到本声明的法律责任由本人承担。 论文作者签名： 日 期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影e | 】、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：导师签名：游书i 七, 7 , _ 1 日导师签名：1 匾“ 日期：乙耐眨r 山东大学硕士学位论文 1 1 研究的意义 第一章绪论 随着因特网和w e b 的快速发展，人类己进入一个信息社会。在信 息爆炸的年代，更多的信息意味着更多的竞争。随着全球化竞争的加 剧，企业比任何时候都需要更快更好地做决策。在某种程度上，数据 就是企业最宝贵的资源；基于信息的决策能力就是企业的竞争力。然 而对任何组织或个人来说，海量的未能利用的数据并不是财富，而是 沉重的负担。 数据挖掘，顾名思义就是从大量的数据中挖掘出有用的信息，即 从大量的、不完全的、有噪声的、模糊的、随机的实际应用中发现隐 含的、规律性的、人们事先求知的，但又是潜在有用的并且最终可理 解的信息和知识的过程。 数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，简称 k d d ) ，又称为数据挖掘( d a t am i n i n g ) ，它是由数据库、机器学习、 统计学等多门学科形成的一门新兴学科。其目标是从大量原始数据中 挖掘出隐含的、有用的、未知的知识，所发现的知识可以是描述数据 特性的规则、频繁出现的模式、数据集中目标的聚类、预测模型等。 目前数据挖掘技术被认为具有广阔的研究前景。国外，在大型商业、 金融、保险、民航、电信等大型企业都开始得到应用。国内方面，目 前总体上仍处于起步研究阶段。 数据挖掘的大多数算法主要研究的问题是发现“大模式”，即输入 数据的主要特征；另一方面是研究“小模式”问题即孤立点挖掘，孤 立点探测和分析有非常广泛的应用，如欺诈监测、定制市场、医疗分 析等领域。当前关于孤立点算法方面的研究尚处在起步阶段，有关的 算法与应用还很不完善，基于此我们对相关算法进行了研究与分析， 山东大学硕士学位论文 以期找出一种较为有效实用的方法。 1 2 国内外研究现状 本论文数据挖掘的数据源是由数据仓库形成而来，因此对于数据 仓库的一些技术也是本论文研究一个重点。 1 2 1 数据仓库的研究现状分析 数据仓库作为一个新的研究领域，它的研究和应用得到了广泛的 关注，也很快成为数据库市场一个新的增长点。国外有许多厂家和公 司如i b m ，o r a c l e ，n c r 和m i c r o s o f t 等有实力的公司在这个领域进 行了深入的研究，相继( 通过收购或研发的途径) 推出了自己的数据仓库 解决方案。 在我国，数据仓库市场启动较晚，主要由于当时我国的应用基础 尚不完善及企业意识不足。但随着我国信息化建设的逐渐完善和应用 意识的提高，许多行业如电信、金融、税务等逐步认识到数据仓库技 术对于企业宏观发展所带来的巨大经济效益，纷纷建立起数据仓库系 统。o r a c l e ， i b m ， s y b a s e ，c a 及i n f o r m i x 等厂商也为我国提供大 型数据仓库解决方案，目前已经建设成功并已收回投资的项目主要有 招商银行系统和国信证券系统等。据c a r t n e rg r o u p 的一份数据仓库市 场占有率的报告显示，到2 0 0 3 年，美国的数据仓库销售额将占世界的 5 8 ，亚洲只占7 5 。从中不难看出我们的差距。和国外相比，国内 的数据仓库市场还不成熟，主要的原因有以下几个方面：首先，建设 数据仓库的前提是要有大量的数据，特别是历史数据。近几年来我国 数据库建设有了长足的发展，但与国外的发展程度相比仍相差2 0 多年 时问。目前国外数据库已是海量，雨国内除了银行、电信等少数行业 以外，数据积累都不够充分，数据库的规模也不大，并且有的数据库 建完以后常常没有钱维护，就变成了“死库”。其次，数据仓库应用主 山东大学硕士学位论文 要是一个建立的过程，实践性非常强，而从国内( 包括外企1 的情况来看， 真正能够完整实施数据仓库方案的人才严重匮乏，因此制约了国内数 据仓库市场的发展。第三，目前数据仓库工具没有国产的，由于东西 文化差异，数据表现不符合国内客户要求，必须重新定制开发应用界 面，从而延长了建设周期。同时数据仓库产品价格居高不下的原因也 影响了其在国内的推广。 另外，由于数据仓库技术体系的不成熟，无论在中国还是在世界 其它国家，数据仓库的应用受到了一定制约。首先，数据仓库技术还 没有达到数据库技术的成熟度和易用性，目前市场上的数据仓库产品 都是基于一个通用的技术平台设计的，虽然能解决不同用户的分析需 求，但没有将特殊领域的商业逻辑与数据仓库技术集成，因而分析效 果不可能达到峰值。其次，数据仓库的应用有两大类，一类是做分析 型工作的o l a p ，另类是做预测型工作的数据挖掘。目前基于数据挖 掘的算法层出不穷，还没有经历一个大浪淘沙的沉淀，而数据库中的 检索技术经过人们多年的摸索，已经形成几种固定成熟的技术模式， 这是数据仓库产品没有达到数据库产品实用性的另一个原因。所以目 前数据仓库技术的发展仍处于积累阶段。 虽然数据仓库技术还需要不断完善，但是其能带来的巨大经济效 益，使它的发展前景不可限量。据i d c 预测分析，从1 9 9 7 年到2 0 0 2 年，整个数据仓库市场将以平均每年2 0 5 的速度增长，到2 0 0 2 年将 超过2 9 0 亿美元。数据仓库应用所能够带来的巨大效益也必将刺激中 国数据仓库市场的发展。前些年，国内已经有不少的用户在m r p h 、 企业财务管理以及某些m i s 应用上有了原始数据的积累，若把这些现 成的东西插上决策分析的翅膀，必可使得当今的企业如虎添翼，成为 企业获得竞争优势的有力武器。总之，中国的数据仓库市场将前景广 阔，充满无限商机。 山东大学硕士学位论文 1 2 2 数据挖掘的现状分析 数据挖掘技术是近几年国内外迅速发展起来的一门交叉学科，涉 及到数据库、统计学、人工智能与机器学习等多个领域。计算机的应 用普及产生了大量的数据，数据挖掘就是利用上述学科的技术进行大 数据量的处理。数据挖掘的应用领域非常宽广，从农业生产的预测到 基因分类，从化学分子结构的识别到n b a 教练临场更换队员，从信用 卡欺诈到税务稽查，数据挖掘技术对未来社会的各个领域将起到越来 越主要的作用。 我国的数据挖掘技术一方面是科研机构停留在学术研究上，另一 方面是利用国外公司的软件产品解决具体问题。为了提高学术水平， 科研人员只得进行高水平但很难实用的算法研究：为了提高经济效益， 销售国外软件公司的产品最稳健。但是，数据挖掘技术在解决实际问 题的过程中需要的是成熟技术加针对具体问题的修正，因此，国内迫 切需要对国外十余年的数据挖掘具体技术进行剖析，在掌握核心技术 的前提下才能真正赶超。 1 23 信息的可视化现状分析 对于信息的可视化方面，许多的程序设计语言就开发了数据可视 化的功能，还有许多成熟的数据可视化工具，如：s p s s 集全公司资源 和努力下，全新的c l e m e n t i n e 7 0 ，m i c r o s o f t 公司的e x c e l ， o r a c l e 公司的o r a c l e ，s g i 公司的m i n e s e t ，另外许多的可视化编程工具都提 供了数据可视化方面的工具。 1 2 4 数据挖掘应用现状分析 数据挖掘的应用在理论上可以应用于许多的领域，针对不同的数 据挖掘算法，可以针对地使用于不同的领域。较典型的应用如下： 1 数据挖掘在电信行业的应用，主要包括： 山东大学硕士学位论文 ( 1 ) 客户消费模式分析，对客户历年来长话、市话、信息台的大 量详细话单、数据以及客户档案资料等相关数据进行关联分析，结合 客户的分类，可以从消费能力、消费习惯、消费周期等诸方面对客户 的话费行为进行分析和预测，从而为固定电话运营商的相关经营决策 提供依据。 ( 2 ) 客户市场推广分析。 ( 3 ) 客户欠费分析和动态防欺诈，通过数据挖掘，总结各种骗费、 欠费行为的内在规律，并建立一套欺诈和欠费行为的规则库。 ( 4 ) 客户流失分析，根据己有的客户流失数据，建立客户属性、 服务属性、客户消费情况等数据与客户流失概率相关联的数学模型， 找出这些数据之间的关系，并给出明确的数学公式。然后根据此模型 来监控客户流失的可能性，如果客户流失的可能性过高，则通过促销 等手段来提高客户忠诚度，防止客户流失的发生。这就彻底改变了以 往电信运营商在成功获得客户以后无法监控客户流失、无法有效实现 客户关怀的状况。 2 数据挖掘在保险寿险中的应用，针对寿险经营的特点，从不同的 角度对客户群体进行分类归纳，从而形成各种客户分布统计，作为管 理人员决策的依据。从寿险产品入手，分析客户对不同险种的偏好程 度，指导代理人进行重点推广。 3 数据挖掘在银行领域中的应用：主要应用于银行卡的业务方面， 一是需要掌握客户的消费习惯是否支持他有效利用贷记卡，从而实现 贷记卡先消费后还款的功能，二是需要了解该客户的信用情况，以避 免出现恶意透支等使银行遭受损失。银行业务人员掌握了数据挖掘工 具，支持他们按客户群对客户信息进行分析，那么，只要对某类客户 在过去一段时间内的银行卡交易状况进行分析，就可获得相当丰富的 业务信息。 4 数据挖掘在客户关系管理领域中的应用： ( 1 ) 客户群体分类分析：利用数据挖掘技术可对大量的客户分类， 山东大学硕士学位论文 提供针对性的产品和服务。 ( 2 ) 交叉销售：现代企业和客户之间的关系是经常变动的，一旦 拥有了新的客户，就要竭力完善这种关系，需要对其进行交叉销售， 为原有客户提供新的产品或服务。数据挖掘可以帮助你分析出最优的 合理的销售匹配。 ( 3 ) 客户的获得、流失和保持分析：企业的增长和发展壮大需要 不断维持老客户和获得新客户。数据挖掘可以帮助你识别出潜在的客 户群，提高市场活动的响应率，使你做到心中有数，有的放矢。 ( 4 ) 客户盈利能力分析和预测：数据挖掘技术可以用来分析和预 测不同市场活动情况下客户盈利能力的变化，帮助企业制定适合的市 场策略。 ( 5 ) 客户背景分析：数据挖掘可以从大量，表面无关的客户信息 中发现许多对商家有用的模式。 ( 6 ) 客户满意度分析：分析客户对企业产品和服务的满意度，可 以帮助企业改进客户营销策略，从而增加客户的忠诚度。 ( 7 ) 客户信用分析：分析客户信用，对商家很有意义，对不同信 用级别的客户，采取不同的赊销方案等。数据挖掘，可从大量历史数 据中分析出具体客户的信用等级。 另外，数据挖掘在医疗方面，证券领域也有不同程度的应用。 1 3 论文研究内容及组织 数据挖掘所处理的数据中有时会包括一些异常数据，检测这些异 常( 偏差) 很有意义。偏差包括很多潜在的知识。通过建立有效的索 引方式对这些离群数据进行分析研究，找出高效的查找知识的方法和 途径，降低数据交换的复杂性。本文即是在这个方向上作了一些初步 的探索，讨论了经典孤立点分析中的算法，提出了在新的索引机制下 进行孤立点分析的有效算法，这对于更好地从孤立数据中进行挖掘， 查找用户兴趣度高的知识，从而有效地解决问题提供了良好的选择。 山东大学硕士学位论文 本论文共分五章： 第一章：绪论。简要介绍了本课题的研究背景和意义，对研究内 容进行了阐述，最后列出了本论文的组织结构。 第二章：基础知识。我们分析了数据仓库的问题，如何建立事实 表，维度表以及数据仓库涉及的一些技术问题的内容，为数据挖掘的 数据源的形成做基础知识的准备。 第三章：我们分析了数据挖掘的问题，特别是孤立点分析的方法 及经典孤立点分析的算法进行了讨论，并对应用经典孤立点分析方法 计算的复杂度进行了分析。 第四章：论文讨论了聚类分析常用结构，针对本文提出了基于r 4 一 树应用线性时间索日l 方法计算第k 个最近邻算法从而对孤立点进行计 算的设计思想，降低了计算的复杂度，提高了计算效率，提高了数据 挖掘的速度，该方法也对今后的实际应用研究有参考意义。 最后，在第五章中我们对全文进行总结，并指出下一步的工作。 1 4 小结 本章简要介绍了本文的选题及其研究意义，分析了k d d 当前国内 外的研究现状及发展趋势，对论文的主要研究内容、实验背景等作了 简要说明。 山东大学硕士学位论文 第二章数据仓库和数据挖掘理论基础 2 1 数据仓库的产生 在市场经济的激烈竞争中，企业必须把业务经营同市场需求联系 起来，在此基础上做出科学、正确的决策，以求生存。为此，企业纷 纷建立起了自己的数据库，由计算机管理代替手工操作，以此来收集、 存储、管理业务操作数据，改善办公环境，提高操作人员的工作效率。 但是传统的数据库应用系统并不能很好地支持决策，因为它是面向业 务操作设计的，企业需要新的技术来弥补原有数据库系统的不足，需 要把已经广泛收集到的数据集成到数据仓库中，以从业务数据中提取 有用的信息，帮助他们在业务管理和发展上做出即时正确的判断。数 据仓库技术应运而生，成为信息技术领域非常热门的话题之一。 数据仓库是计算机和数据应用发展到一定阶段的必然产物。数据 仓库的目的是为了建立一种体系化的数据存储环境，将分析决策所需 的大量数据从传统的操作环境中分离出来，使分散、不一致的操作数 据转换成集成、统一的信息。企业内不同单位、不同角色的成员都可 以在此单一的环境之下，通过运用其中的数据与信息，发现全新的视 野和新的问题、新的分析与想法，进而发展出制度化的决策系统，并 获取更多经营效益。这种需要推动了数据仓库技术的发展。 完整的数据仓库应包括3 个方面的内容：数据仓库技术、联机分 析处理技术和数据挖掘( d a t am i n i n g ，d m ) 技术。 2 2 数据仓库的基本概念 2 2 1 数据仓库定义 2 0 世纪8 0 年代中期，“数据仓库”这个名词首次出现在号称“数据 山东大学硕士学位论文 仓库之父”w i l l i a me i n m o n 的建立数据仓库一书中。数据仓库的定 义历来没有一个公认的、被标准化的定义。不过随着人们对大型数据 系统研究、管理和维护等方面的深刻认识和不断完善，在总结、丰富 并集中多个企业信息的经验之后，都或多或少地指出了数据仓库有如 下几个特点并达到了共识：数据仓库中的数据是面向主题的、集成的、 不可更新的( 稳定的) 并随着时间不断变化的，建立数据仓库的目的是为 了更好地支持决策分析。 数据仓库是为决策服务的数据库系统。数据仓库的目标是达到有 效的决策支持。任何一个公司和企业，在业务处理、票据清单、账目 清算、客户服务、以及财务报告等方面，都存在大量的业务应用和技 术环节。数据仓库的作用在于：从这些应用系统中获取信息并转换到 一个新的数据库，通过对新库中的历史信息和面向主题的信息进行分 析，为决策提供支持。 2 2 2 数据仓库的基本特征 依据w h i n m o n 对数据仓库的定义来具体理解数据仓库的几个 关键特征。 1 数据仓库是面向主题组织数据的 这是与传统数据面向应用相对应的。数据仓库围绕一些主题，如 顾客、供应商、产品和销售组织。主题是一个抽象的概念，是在较高 层次上将企业信息系统中的数据按不同类别、不同侧面进行综合、归 类。这一特点也使得数据仓库是数据驱动面向主题的数据处理技术。 2 数据仓库是集成的 数据仓库中存储的数据从原来分散的各个子系统中提取出来，但 并不是原有数据的简单拷贝，而是经过统一并综合。这是因为： ( 1 ) 数据仓库的数据不能直接从原有数据库系统中得到，原有数 据库系统记录的是每一项业务处理的流水账，这些数据不适合于分析 处理。在进入数据仓库之前必须经过综合计算，抛弃分析处理不需要 山东大学硕士学位论文 的数据项，增加一些可能涉及的外部数据。 ( 2 ) 数据仓库每一个主题所对应的源数据在原分散数据库中有许 多重复或不一致之处，必须将这些数据转换成全局统一的定义，消除 不一致和错误之处，以保证数据的质量：显然，对不准确，甚至不正 确的数据分析得出的结果将不能用于指导企业做出科学的决策。 对源数据的集成是数据仓库建设中最关键，也是最复杂的一步。 3 数据仓库是稳定的 数据仓库中保存的是大量的经集成、加工过的综合性历史数据， 是供企业决策分析之用的，因此不允许在上面进行插入、删除和更新 操作。数据仓库中的数据需要按计划添加，但是依据一定的规则，原 始数据不会丢弃。因为数据仓库数据的操作只有两类：数据的初始化 装入和数据访问。数据一经装载放进数据仓库中就具有了相当的稳定 性，除非特别需要，其值一般都不会被更新，只做定期刷新。 4 数据仓库是随时间变化的 为适应决策分析的需要，数据仓库中的数据时限要远远长于操作 型环境中的数据。通常情况下，前者在5 1 0 年，而后者只有6 0 一9 0 天。 即数据仓库中的数据都是历史数据。因此，在数据仓库的关键数据中 一般都应含有时间项，使得随时间的趋向和变化可以用于数据分析研 究。 2 3 数据仓库系统 2 31 数据组织结构 数据仓库是以原有的关系数据库作为主要信息来源的，但它的数 据组织结构形式与数据库有很大区别，它将不同来源的数据综合后按 不同的粒度分别存贮。其中的数据可以分为：当前细节数据( c u r r e n t d e t a i ld a t a ) 、早期细节数据( o l d e rd e t a i ld a t a ) 、轻度综合数据( 1 i g h t l y s u m m a r i z e dd a t a ) 、高度综合数据( h i g h l ys u m m a r i z e dd a t a ) 和元数据 山东大学硕士学位论文 2 3 2 数据组织方式 数据仓库的数据组织方式可分为虚拟存储方式、基于关系表的存 储方式和多维数据库存储方式三种。 2 3 3 数据模型 星型模式和雪花模式是最常用的数据仓库结构模式。 1 星型模式 大多数数据仓库都采用“星型”模式来表示多维概念模型。数据 库中包括一个“事实表”，对于每一维都有一个“维表”。事实表中的 每条元组都包含有指向各个维表的外键和一些相应的测量数据，维表 中记录的是有关这一维的属性，如图2 1 所示。 从图2 1 中可以看出，事实表中的属性只是包含了一些指针f 即外 键) ，而对应的主键分别放在不同的维表中如“订单号”放在“订货表” 中，每个指针指向一个维表，这就构成了数据库的多维联系。相应每 个属性多维外键限定数字测量值。在每个维表中除包含每一维的主键 外，还有说明该维的一些其他属性字段。维表记录了维的层次关系。 在数据仓库中执行查询的分析过程，需要 中寻找数据。而星型模式使数据仓库的复杂查 层次比较上钻及下钻等操作完成。 在数据仓库中除了维表和事实表的数据外 的综合数据。预处理的综合数据可以通过创建 以提高查询数据的速度。 花大量时间在相关各表 询可以直接通过各维的 ，还包含一些已预处理 一些“概括表”进行存储， 山东大学硕士学位论文 图2 1 星型模式 2 雪花模式 “雪花模式”是对星型模式的扩展。如果某个顶点有多个归类层次， 就形成雪花型模式。它对星型模式的维表进一步层次化，原有的各维 表可能被扩展为小的事实表，形成一些局部的“层次”区域。它的优点 是：通过最大限度地减少数据存储量以及联合较小的维表来改善查询 性能。 雪花模式增加了用户必须处理的表数量，增加了某些查询的复杂 山东大学硕士学位论文 性。但这种方式可以使系统进步专业化和实用化，同时降低了系统 的通用程度。前端工具仍然要用户在雪花的逻辑概念模式上操作，然 后将操作转换为具体的物理模式，从而完成对数据的查询。 图2 2 所示的“产品”与“产品目录”，维表与事实表的关系区域，是 在数据仓库的数据组织上对用户查询需求的扩展。使用数据仓库和 o l a p 查询工具完成一些简单的二维或三维查询，既满足了用户对复杂 数据仓库查询的需求，又能够在无须访问过多数据的情况下，完成一 些简单查询功能。 订货表 订单号 订货日期 客户表 奎皇呈 客户名称 客户地址 销售员 盟宣虽量 销售员姓名 城市 事实表 订单号 熊笪旦墨 窒龃 产品号 旦翘握塑 地区名称 数量 总价 产品表 产品号 产品名称 产品目录 单价 图2 - 2 雪花模式 日期表 日期标识 日 月 地区表 垫噬 省别 目录表 产品目录 目录描述 省表 省别 舟西 山东大学硕士学位论文 2 3 4 数据仓库的体系结构 数据仓库系统( d a t aw a r e h o u s es y s t e r a ) - p e 以数据仓库为基础，通过 数据预处理技术、分析技术。完成对数据的转载和对信息提取的系统。 在数据仓库系统中元数据起着重要的作用，指导数据的采集和数据仓 库的建立。元数据是通过元数据管理工具建立的。数据仓库的体系结 构如图2 3 所示。 o d b c 、j d b c 、a d o 等 图2 3 数据仓库的体系结构 士 山东大学硕士学位论文 2 4 数据挖掘的概念 数据挖掘是从大量、不完全的、有噪声的、模糊的、随机的数据 中提取隐含在其中的、人们事先不知道的、但是潜在的有用信息和知 识的过程，即从存放在数据库、数据仓库或其他信息库中的大量数据 中挖掘有用知识的过程。它建立在数据库，尤其是数据仓库基础之上， 面向非专业用户，定位于桌面，支持即兴的联机查询。数据挖掘技术 能自动分析数据，进行归纳性推理和联想，寻找数据间内在的某些关 联，发掘潜在的、对信息预测和决策行为起着十分重要作用的模式， 从而建立新的业务模型，帮助决策者制定市场策略，做出正确决策。 数据挖掘是涉及多学科技术的集成，其中包括数据库技术、统计 学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信 息检索、图像与信号处理和空间数据分析等。数据挖掘可以从数据库 中提取知识、规律或高层信息，并可以从不同角度观察或浏览，发现 的知识可用于决策、过程控制、信息管理、查询处理等。因此，数据 挖掘被信息产业界认为是数据库系统最重要的前沿之一，是信息产业 最有前途的交叉学科。 数据挖掘( 知识发现) 过程分为下几个步骤： ( 1 ) 数据清理：消除噪音或不一致数据； ( 2 ) 数据集成：将多种数据源组合在一起； ( 3 ) 数据选择：从数据湾中检索与分析任务相关的数据； ( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总 或聚集操作； ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有用 模式； ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的 知识。 山东大学硕士学位论文 其中，数据挖掘步骤可以与用户或知识库交互，将有价值模式提 供给用户，或作为新的知识存放在知识库中，由上述步骤可以看出， 数据挖掘之前要将数据清理、集成、选择和变换，数据挖掘之后要将 结果可视化，而这些都是数据挖掘不可缺少的，如果将这些步骤从数 据挖掘中孤立出来与数据挖掘相并列，未免有些牵强。因此可以认为， 从狭义来讲数挖掘是数据库中知识发现过程的一个步骤，但从广义上 来说数据挖掘即数据库中的知识发现。 在实际应用中，数据挖掘的过程如下： ( 1 ) 分析问题：源数据数据库必须经过评估确认其是否符合数据 挖掘标准。以决定预期结果，也就选择了这项工作的最优算法。 ( 2 ) 提取、清洗和校验数据：提取的数据放在一个结构上与数据 模型兼容的数据库中。以统一的格式清洗那些不一致、不兼容的数据。 一旦提取和清理数据后，浏览所创建的模型，以确保所有的数据都已 经存在并且完整。 ( 3 ) 创建和调试模型：将算法应用于模型后产生一个结构。浏览 所产生的结构中数据，确认它对于源数据中“事实”的准确代表性，这 是很重要的一点。虽然可能无法对每一个细节做到这一点，但是通过 查看生成的模型，就可能发现重要的特征。 ( 4 ) 查询数据挖掘模型的数据：一旦建立模型，该数据就可用于 决策支持了。 ( 5 ) 维护数据挖掘模型：数据模型建立好后，初始数据的特征， 如有效性，可能发生改变。一些信息的改变会对精度产生很大的影响， 因为它的变化影响作为基础的原始模型的性质。因而，维护数据挖掘 摸型是十分重要的环节。 2 5 数据挖掘系统的组成 基于上述数据挖掘的广义观点，典型的数据挖掘系统一般具有以 下部分： 山东大学硕士学位论文 数据库、数据仓库或其他信息库：一个或一组数据库、数据仓库、 电子表格或其他类型的信息库：可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或 数据仓库服务器负责提取相关数据。 知识库：即领域知识，用于指导搜索或评估结果模式的兴趣度。 这种知识包括概念分层( 用于将属性或属性值组织成不同的抽象 层) 、用户确信方面的知识、兴趣度限制或阀值及元数据等。可以根据 非期望性评估模式的兴趣度使用这些知识。 数据挖掘引擎：是数据挖掘系统基本的部分，由一组功能模块组 成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常使用兴趣度度量，并与数据挖掘模式交互 以便将搜索聚焦在有价值的模式上。 图形用户界面有：用户和数据挖掘系统之间通信，允许用户与系 统交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据 数据挖掘的中间结果进行探索式数据挖掘。此外，还允许用户浏览数 据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对 模式可视化。 图2 4 数据挖掘系统组成图 山东大学硕士学位论文 2 6 数据挖掘中的数据预处理 目前所进行的关于数据挖掘的研究工作，大多着眼于数据挖掘算 法的探讨而忽视了对数据处理的研究。一些比较成熟的算法对其处理 的数据集合一般都有一定的要求，比如数据完整性好、数据的冗余性 少、属性之间的相关性小。然而；实际系统中的数据一般都具有不完 全性、冗余性和模糊性，很少能直接满足数据挖掘算法的要求。另外， 海量的实际数据中无意义的成分很多，严重影响了数据挖掘算法的执 行效率，而且由于其中的噪声干扰还会造成无效的归纳。预处理已经 成为数据挖掘系统实现过程中的关键问题。 2 6 1 原数据存在的问题 数据预处理是数据挖掘的重要一环，而且必不可少。要使挖掘内 核更有效地挖掘出知识，就必须为它提供干净、准确、简洁的数据。 然而实际应用系统中收集到的原始数据是脏的，通常存在以下几方 面的问题： 1 杂乱性 原始数据是从各个实际应用系统中获取的( 多种数据库、多种文件 系统) ，由于各应用系统的数据缺乏统一标准和定义，数据结构也有较 大的差异，因此各系统间的数据存在较大的不一致性，往往不能直接 拿来使用。 2 重复性 重复性是指对于同一个客观事物在数据库中存在其两个或两个以 上完全相同的物理描述。由于应用系统实际使用中存在的一些问题， 几乎所有应用系统中都存在数据的重复和信息的冗余现象。 3 不完整性 由于实际系统设计时存在的缺陷以及一些使用过程中人为因素所 造成的影响，数据记录中可能会出现数据属性的值丢失或不确定的情 山东大学硕士学位论文 况，还可能缺少必须的数据而造成数据不完整。实际使用的系统中， 存在大量的模糊信息，有些数据设置还具有一定的随机性质。 一个完整的数据挖掘系统必须包含数据预处理模块。它以发现任 务作为目标，以领域知识作为指导，用全新的“业务模型”来组织原来 的业务数据，舍弃一些与挖掘目标不相关的属性，为数据挖掘提供干 净、准确、更有针对性的数据，从而减少挖掘内核的数据处理量，提 高了挖掘效率，提高了知识发现的起点和知识的准确度。 2 6 2 预处理的基本功能 数据挖掘中的预处理主要是接受并理解用户的发现要求，确定发 现任务，抽取与发现好相关的知识源，根据背景知识中的约束性规则 对数据进行检查，通过清理和归纳等操作，生成供挖掘核心算法使用 的目标数据。数据预处理应该包括以下几方面的功能： 1 数据集成( d a t ai n t e g r a t i o n ) 数据集成主要是将多文件或多数据库运行环境中的异构数据进行 合并处理，解决语义模型性。该部分主要涉及数据的选择、数据的冲 突问题以及不一致数据的处理问题。用于进行知识发现的数据可能来 自多个实际系统，因而存在着异构数据的转换问题。另外，多个数据 源的数据之间还存在许多不一致的地方，如命名、结构、单位、含义 等。因此，数据集成并非是简单的复制过程。它需要统一原始数据中 的所有矛盾之处， 不一致等，从而把 成最初始的知识发 如字段的同名异义、异名同义、单位不统一、字长 原始数据在最低层次上加以转换、提炼和聚集，形 现状态空间。 另外，在数据集成中还应考虑数据类型的选择问题，应尽量选择 占物理空间较小的数据类型。 2 数据清洗( d a t ac l e a n i n g ) 数据清洗要去除源数据集中的噪声数据和无关数据，处理遗漏数 据和清洗脏数据，去除空白数据域和知识背景上的自噪声，考虑时问 山东大学硕士学位论文 顺序和数据变化等。主要包括重复数据处理和缺值数据处理，并完成 一些数据类型的转换。 数据清洗可以分为有监督和无监督两类。有监督过程是在领域专 家的指导下，分析收集的数据，去除明显错误的噪声数据和重复记录， 填补缺值数据：无监督过程是用样本数据训练算法，使其获得一定的 经验，并在以后的处理过程中自动采用这些经验完成数据清洗工作。 数据清洗的另一个重要内容是数据类型的转换，通常是指连续属 性的离散化。一般来说，与类别无关的离散化方法有等距区间法、等 频区间法和最大熵法。与类别有关的方法有划分法( s p l i t t i n g ) 禾i 归并法 ( m e r g i n g ) 等。通过离散化，可以有效地减少数据表的大小，提高分类 的准确性。 3 数据变换( d a t at r a n s f o r m s t i o n ) 数据变换主要是找到数据的特征表示，用维变换或转换方式减少 有效变量的数目；或找到数据的不变式，包括规格化、归纳、切换、 旋转和投影等操作。 规格化指将元组集按规格化条件进行合并，也就是属性值量纲的 归一化处理。规格化条件定义了属性的多个取值到给定虚拟值的对应 关系。对于不同的数值属性特点，般可分为取值连续和取值分散的 数值属性问题：归纳指元组属性值之间的i s 。a 语义关系。规格化和归 纳能大量减少元组个数，提高计算效率，同时，规格化和归纳过程提 高了知识发现的起点，使得个算法能够发现多层次的知识，适应不 同应用的需要。 我们还可以用多维数据立方( d a t ac u b e ) 来组织数据，采用数据仓 库中的切换、旋转和投影技术，把初始的知识状态空间按照不同的层 次、粒度和维度进行抽象和聚集( 即数据泛化) ，从而生成在不同抽象级 别上的知识基。 4 数据简化( d a t ar e d u c u o n ) 有些数据属性对发现任务是没有影响的，这些属性的加入会大大 山东大学硕士学位论文 影响挖掘效率，甚至还可能导致挖掘结果的偏差。因此，有效的缩减 数据是很有必要的。数据简化是在对发现任务和数据本身内容理解的 基础上，寻找依赖于发现目标的表达数据的有用特征，以缩减数据规 模，从而在尽可能保持数据原貌的前提下最大限度地精简数据量。它 主要有两个途径：属性选择和数据抽样，分别针对数据库中的属性和 记录。 ( 1 ) 属性选择包括针对属性进行剪枝、并枝、找方程和找相关等 操作。剪枝就是去除对发现任务没有贡献或贡献率低的属性域：并枝 就是对属性进行主成分分析，把相近的属性进行综合归并处理；找相 关，即因子分析，在取值无序且离散的属性之间寻找依赖关系，确定 某个特定属性对其他属性依赖的强弱并进行比较。通过属性选择能够 有效地减少属性，降低知识状态空间的维数， ( 2 ) 数据抽样就是进行数据记录之间的相关性分析，用少量的记 录基底的线性组合来表示大量的记录。它主要利用统计学中的抽样方 法，如简单随机抽样、等距抽样、分层抽样等，具体进行统计运算， 对于相同元组进行归并，并增加必要的支持度属性域。最简单的支持 度属性域就是相同元组的数目，或者占总元组的百分比，也可以是置 信度。最后去除那些支持度较低的元组可视为例外或噪声) 。 2 7 数据挖掘常用方法和技术 1 决策树方法：用树形结构来表示决策集合，这些决策集合通过对 数据集的分类产生规则。比较典型的决策树方法有i d 3 算法和c a r t ( 分类回归树) 算法等。 2 关联规则：目的就是挖掘出隐藏在数据间的相互关系。主要通过 可信度，支