（计算机应用技术专业论文）数据挖掘中聚类分析的研究与应用.pdf

中文摘要 数据挖掘是目前信息领域和数据库技术的前沿研究课题，被公认为是最具发 展前景的关键技术之一。数据挖掘涉及到统计学、人工智能( 特别是机器学习) 、 模糊理论和数据库技术等多种技术，它强调的是大量数据和算法的可伸缩性，是 一门很接近实用的技术，其技术含量比较高，实现难度也较大。 聚类分析是数据挖掘的重要功能之一，近年来在该领域的研究取得了长足的 发展，出现了许多聚类分析方法，如划分聚类方法、层次聚类方法、基于密度的 聚类方法、基于网格的聚类方法、基于模型的聚类方法等。这些方法所涉及的领 域几乎遍及人工智能科学的方方面面，而且在特定的领域中，特定的情形下取得 了良好的效果。但是当处理数大量数据、具有复杂数据类型的数据集时，仍存在 若干尚未解决的问题。 本文系统地研究了数据挖掘的概念、功能、处理过程及技术算法，数据挖掘 的核心技术是数据挖掘的算法，本文就数据挖掘的算法做了分析和比较，选取了 k - - 平均算法和d b s c a n 算法做了深入的研究，并给出了一种基于距离的异常 数据挖掘算法。本文以山西省一所高职院校的学生成绩数据为背景，通过数据预 处理工作，应用以上几种算法对上述数据进行了聚类分析，实现了可视化，最终 挖掘到一定价值的信息。 关键词：数据挖掘聚类分析k 一平均算法d b s c a n 算法异常点 a b s t r a c t d a t am i n i n gi sas u p e r i o ra r e ai nt h ei n f o r m a t i o na n dd a t a b a s et e c h n o l o g y , a n di s c o m m o n l yc o n s i d e r e da so n eo f t h ek e yt e c h n o l o g yw i t hw i l dd e v e l o p i n gp e r s p e c t i v e d a t am i n i n gr e l a t e st os t a t i s t i c s ，a 1 ( e s p e c i a l l ym a c h i n el e a r n i n g ) ，f u z z yt h e o r y , d a t a b a s et e c h n o l o g yc t c ，h u g eq u a n t i t yd a t aa n dr e t r a c t i l eo f a k o r i t h ma r ee m p h a s i z e d ， i ti sa l s oat e c h n o l o g ya p p r o a c h i n ga p p l i e d ，s oi ti sd i f f i c u l tt or e a l i z e c l u s t e r i n ga n a l y s i si so n eo ft h em a i nf u n c t i o n so fd a t am i n i n g a st h e d e v e l o p m e n to f d a t am i n i n g ，an u m b e ro fc l u s t e r i n ga l g o r i t h m sh a v eb e e nf o u n d e d ， f o re x a m p l ep a r t i t i o n i n gm e t h o d s ，h i e r a r c h i c a lm e t h o d s , d e n s i t y b a s e dm e t h o d s ， g r i d - b a s e dm e t h o d s ，m o d e l - m e t h o d se t c t h e s em e t h o d sh a v er e l a t e dt oa l lo ff i e l d s o fa ns c i e n c e ，a n dh a v eg o tg r e a te f f e c ti ns p e c i f i cf i e l d sa n ds t a t e s ，b u tt h e s ea u m e e td i f f i c u l t i e sw h e np r o c e s s i n gh u g eq u a n t i t yd a t aw i t hc o m p l e xd a t at y p e i nt h i st h e s i s , w ed i s c u s s e dt h ec o n c e p t ，f u n c t i o nt y p e , p r o c e s s i n gp r o c e d u r ea n d t e c h n o l o g ya l g o r i t h m so fd a t am i n i n g t h em a i nt e c h n o l o g yo fd a t am i n i n gi sd a t a m i n i n ga l g o r i t h m ，s ow ea n a l y z e da n dc o m p a r e ds e v e r a ld a t am i n i n ga l g o r i t h m si n t h i st h e s i s ，a n dd i ds o m er e s e a r c hw o r ko nt h ek - m e a n sa l g o r i t h m ，d b s c a n a l g o r i t h m ，a n dp r o p o s e dt h ea l g o r i t h mf o rm i n i n go u t l i e rd a t ab a s e do nt h ed i s t a n c e b a s e do ng u d e n t sg r a d ed a t ao fac o l l e g ei ns h a n x ip r o v i n c e , w ea l s ou s e da b o v e a l g o r i t h mt oh a v ec l u s t e r i n ga n a l y s i s , a n dr e a l i z e di n f o r m a t i o nv i s u a l i z a t i o n f i n a l l y ， w ed i s c o v e r e ds o m ev a l u a b l ek n o w l e d g e k e yw o r d s ：d a t a m i n i n gc l u s t e r i n ga n a l y s i s k m e a n sa l g o r i t h m d b s c a na l g o r i t h mo u t l i e r s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘茔一或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：f q 聋等 签字同期：护年分月；口日 学位论文版权使用授权书 本学位论文作者完全了解叁洼盘生有关保留、使用学位论文的规定。 特授权丕鲞太鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名；同象平 签字日期：口万年矿月弓一日 导师签名：c 葬红尻乏 签字日期：多彩年沪月；。日 天津大学硕士学位论文 第一章引言 1 1 数据挖掘的研究现状 第一章引言 1 9 8 9 年举行的第l l 届国际联合人工智能联合会议上首次提出了基于数据库 的知识发现( k d d ，k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 的概念，其日的就是用机 器学习的方法来分析数据库管理系统中存储的数据，发现数据中隐藏的规则与知 识，以解决“数据爆炸但知识贫乏”的现象。到了1 9 9 5 年，在美国计算机年会 ( a c m ) 上，提出了数据挖掘( d m ，d a t a m i n i n g ) 的概念，数据挖掘是指使用 算法来抽取信息和模式，是k d d 过程极其重要的一个步骤，所以在使用数据挖 掘与知识发现这两个术语时常常不加以区分。 i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技 术专刊，并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数 据挖掘和知识发现列为专题和专刊讨论。近年来有关k d d 的国际研讨会已经召 开了多次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发 现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相 互渗透。 1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上有3 0 多家软件公司展示了数据挖掘软件产品，不少软件已经在北美和欧洲的国家得到 应用。i b m 公司发布了基于标准的数据挖掘技术一i b md b 2 智能挖掘器积分服 务，可用于个性化的解决方案。两大统计软件公司s a s 和s p s s 也推出了各自的数 据挖掘工具e n 唧r i s em i n e r 着l c l e m e n t i n e 。数据挖掘是数据库和信息决策领域的 最前沿的研究方向之一，已引起了国内外学术界的广泛关注。1 9 9 9 年，亚太地 区在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。数据挖掘和知 识发现成为当前计算机科学界的一大热点o 。 与国外相比，国内对数据挖掘的研究稍晚。1 9 9 3 年国家自然科学基金首次 支持对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识 发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、 空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法 在知识发现巾的应用进行了较深入的研究，北京大学也在开展对数据立方体代数 的研究，华中理工大学、复旦大学、浙江大学、中围科技大学、中科院数学研究 天津大学硕士学位论文 第一章引言 所、吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川 联合大学和上海交通大学等单位探讨研究了非结构化数据的知识发现以及w e b 数据挖掘。 人们已经认识到数据挖掘技术能将原始数据转换为有意义的形式，从中挖掘 潜在的巨大商业价值和所蕴含的科学知识，数据挖掘已成为电子商务淘金的首要 的手段。具有影响的“m 1 t 技术回顾”最近对数据挖掘技术极力赞扬，认为其已 成为十大新兴技术之一，将彻底改变数据库的处理模式。随着数据挖掘技术不断 被应用到新的领域和各种算法不断被应用到数据挖掘领域中，将更大激发数据挖 掘技术的潜力，进一步推进数挖掘技术的发展和普及。 1 2 数据挖掘的难点 k d d 的许多技术源于机器学习方法，但由于现实世界数据库存在一些固有的 特点，因此给k d d 带来一些难点2 。正是这些关键之处，才形成了k d d 领域自 己独特的研究方向。 ( 1 ) 算法的可伸缩性 在许多实际应用中，数据集的规模呈指数增长，将针对小型数据库设计的数 据挖掘算法应用于大型数据库时，许多算法的效率都很低。对于算法的可伸缩性 问题，抽样与并行化是两个有效的工具。 ( 2 ) 现实世界的数据 现实世界的数据是有噪声的，并且有许多缺失的属性值。遇到这些问题时， 算法应该可以处理。 ( 3 ) 动态变化的数据 虽然没有假定数据库是静态的，许多数据挖掘算法却是基于静态数据库设计 的，这就导致了当数据库发生任何变化时都要重新进行一遍数据挖掘算法。 ( 4 ) 使用方便 虽然有些算法非常有效，但由于难以理解和使用，从而导致算法不能彼用户 接受。 到日前为止，许多数据挖掘工作都只足专注于特定的算法来实现每个单独的 数据挖掘任务向并没有将数据挖掘任务进行抽象化。些数据库研究人员的个 日标就是完成抽象过程。 天津大学硕士学位论文 第一章引言 1 3 数据挖掘的发展趋势5 ( 1 ) 数据挖掘语言的标准化 标准的数据挖掘语言或其他方面的标准化工作将有助于数据挖掘的系统化 开发，改进多个数据挖掘系统和功能间的互操作，促进数据挖掘系统在企业和社 会中的推广应用。 ( 2 ) 可视化数据挖掘 可视化数据挖掘是从大量可视化数据( 如影像资料、图片等) 中发现知识的 有效途径。可视化信息传播已在现实生活中占据主流，研究和开发可视化数据挖 掘技术将会增强数据挖掘的分析功能，使之成为更有效的数据分析工具。 ( 3 ) 复杂数据类型挖掘的新方法 复杂数据类型挖掘是数据挖掘中一项重要的前沿研究课题。虽然在地理空间 挖掘、多媒体挖掘、时序挖掘、离散挖掘以及文本挖掘方面取得一些进展，但它 们与实际应用的需要仍存在很大的距离，对此需要进一步的研究，尤其是针对上 述数据类型的现存数据分析技术与数据挖掘方法集成起来的研究。 ( 4 ) w e b 挖掘 由于w e b 上存在海量数据信息，并且w e b 在当今社会扮演越来越重要的角 色，有关w e b f q 容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务，将成为数据 挖掘中一个最为重要和繁荣的子领域。 ( 5 ) 数据挖掘中的隐私保护与信息安全 随着数据挖掘工具和电信与计算机网络的日益普及，数据挖掘要面对的一个 重要问题是隐私保护和信息安全。需要进一步开发有关方法，以便在适当的信息 访问和挖掘过程中实现隐私保护与信息安全。 1 4 本文的主要工作 本文研究了基于数据挖掘库的数据挖掘技术，并应用了k 一平均算法、 d b s c a n 算法和基于距离的异常数据挖掘算法，实现了高职院校教学管理中学 生成绩的聚类分析。 第二章从数据挖掘的定义、功能、过程及其主要技术几个方面对数据挖掘技 术进行了系统的分析和研究。 第二章概述了聚类分析的概念、原理及其数据类型。 第四章介绍了聚类分析中常用的模型算法。 第五章以山西一所高职院校的学生成绩为数据源，通过k 一平均算法、 天津大学硕士学位论文第一章引言 d b s c a n 算法和基于距离的异常数据分析算法进行了聚类分析，并挖掘到一定 价值的信息。最后对本文的工作进行了总结并指出了此课题今后的研究方向。 天律大学硕士学位论文第二章数据挖掘概述 第二章数据挖掘概述 在网络信息化时代，大量信息给人们带来方便的同时也带来一系列问题：难 以消化，真假难辨，安全隐患，难以统一处理。与此同时，随着数据库技术的迅 速发展和广泛应用，人们积累的数据越来越多，传统的分析方法不能发现数据背 后隐藏的知识，导致了“数据爆炸但知识贫乏”的现象，数据挖掘便应运而生。 2 1 数据挖掘的概念 数据挖掘是- - f 受到来自各种不同领域的研究者关注的交叉学科，有许多不 同的术语名称，本文主要从技术角度和商业角度给出数据挖掘的定义巧。 2 1 1 数据挖掘的技术定义 从技术角度讲，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程。这个定义包括几层含义：数据源必须是真实的、大量的、 含噪声的：发现的是用户感兴趣的知识；发现的知识要可接受、可理解，在特定 的领域中具有实际应用价值。 从广义上理解，数据、信息都是知识的表现形式，但是习惯上更把概念、规 则、模式、规律和约束等看作知识，把数据看作是形成知识的源泉。原始数据可 以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、图形和 图像数据：甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的， 也可以是非数学的，可以是演绎的，也可以是归纳的。发现的知识可以被用于信 息管理，查询优化，决策支持和过程控制等方面，还町以用于数据自身的维护。 冈此，数据挖掘是门交叉学科，它把对数据的应用从低层次的简单查询，提升 到从数据中挖掘知识，捉供决策支持。 2 1 2 数据挖掘的商业定义 从商业府_ j 角度讲，数据挖掘是一种新的商业信息处理技术，其主要特点是 对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中 提取辅助商业决策的关键性数据。 天律大学硕士学位论文第二章数据挖掘概述 数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的 历史，现在分析这些数据不再是单纯为了研究的需要，更主要是为商业决策提供 真正有价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数 据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分 析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖 掘也因此而得名。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进行 探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的 先进有效的方法。 2 1 3 数据挖掘与数据仓库 成功的数据挖掘关键之一是通过访问正确的、完整的和集成的数据，才能进 行深层次的分析，寻求有益的信息。已经完成了数据清理、数据变换和数据集成 过程的数据仓库完全能够为数据挖掘提供所需要的挖掘数据，使数据挖掘免除了 数据准备的繁杂过程。大部分情况下，数据挖掘都要先把数据从数据仓库中拿到 数据挖掘库或数据集市中( 见图2 1 ) o 。数据挖掘库可能是数据仓库的一个逻 辑上的子集，而不一定非得是物理上单独的数据库。但如果你的数据仓库的计算 资源已经很紧张，最好还是建立一个单独的数据挖掘库。 图2 一l 数据挖掘库从数据仓库中得出 建立一个数据仓库足一i 负f i 人的工程，对于数据挖掘来说，数据仓库不是必 需的，可以把一个或几个事务数据库导到一个只读的数据库中，就把它当作数据 集市，然后在它上面进行数据挖掘( 幽2 - 2 ) 。 图2 2 数据挖掘库从事务数据库中得出 6 一 天津大学硕士学位论文 第二章数据挖掘概述 数据挖掘与数据仓库的应用已经紧密地捆绑在一起，数据挖掘技术对数据仓 库提出了更高的数据组织要求，希望数据仓库在数据挖掘技术对数据仓库中的数 据进行操作时能够提供更多、更详细的数据，并且要求数据仓库能够经受数据挖 掘技术对数据仓库中数据进行全方位的浏览和查询。 2 1 4 数据挖掘与在线分析处理 在线分析处理( o l a p ，o nl i n e a n a l y t i c a lp r o c e s s i n g ) 在数据仓库或数据集 市上进行，是决策支持领域的一部分。用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 工具或许能回答这些问题。 2 2 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖 掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下几类功能。 2 2 1 发现与预测 数据挖掘就像在“数据山”上寻找挖掘“知识舍块”，这就是数据挖掘的发 现功能。使用数据挖掘，不仅q 以在“数据山”中找到目前需要的“金矿”，还 可以帮助我们预测新的金矿在山的什么走向上，使我们尽快找到新的金矿，这就 是数据挖掘的预测功能。数据挖掘通过对大型数据库的分析与归纳，自动寻找预 测件信息以往斋要进行大量手工分析的问题如今可以迅速直接由数据本身得出 结论。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻 找未来投资中回报最大的用户，其它可预测的| j 题包括预报破产以及认定对指定 事件最可能做出反应的群体。 天津大学硕士学位论文第二章数据挖掘概述 2 2 2 关联规则挖掘 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是找出数据库中隐藏的关联规则或关联网。关联规则可 记为a j b ，a 称为前提，b 称为后续。由于数据库中数据量非常庞大，有时并 不知道数据库中数据的关联函数，即使知道也可能是不确定的，或带有一定的可 信度。因此利用关联规则挖掘所发现的规则性知识带有可信度。 2 2 3 数据聚类 聚类是把一组个体按照相似性归成若干类别，目的是使得属于同一类别的个 体之间的距离尽可能的小而不同类别上的个体间的距离尽可能的大。因为聚类前 不知道要把数据分成哪几类，每个类的性质是什么，因此聚类之后要由领域专家 来解释这样分组的意义。聚类增强了人们对客观现实的认识，是概念描述和偏差 分析的先决条件。聚类分析应用于数据库中，主要是将数据库中的记录划分为一 系列有意义的子集。 2 2 4 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。通过对目标类数据的一般特征( 共性) 进行汇总可以实 现特征性描述；将目标类对象的一般特征与一个或多个对比类对象的一般特征进 行比较可以实现区别性。区别性描述的方法很多，如决策树方法、遗传算法等。 2 2 5 偏差分析 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏 差包括很多潜存的知识，如分类中的反常实例、不满足规则的特例、观测结果与 模型预测值的偏差、量值随时间的变化等。一个典型的应用是榆测信用卡诈骗交 易并识别m 某些不规则数据的错误。实现偏差检测常用规则推理和人工神经元网 络技术，其关键是判断检测出的结果是属于噪声还是具有潜在意义并需要进一步 的分析。 2 2 6 演变分析 数据演变分析描述行为随时问变化的对象的规律或趋势，并对其进行建模。 天津大学硕士学位论文第二章数据挖掘概述 可以用变量过去的值来预测未来的值。例如对股票交易数据的演变分析，可以识 别整个股票市场和特定公司的股票演变规律，这种规律可以帮助预测股票市场的 未来走向，以便做出正确的投资决策。 2 3 数据挖掘的过程 数据挖掘是一个依赖应用的问题，不同的数据挖掘应用可能需要不同的数据 挖掘技术，处理流程可能也会有所不同，一般数据挖掘的过程如图2 3 所示。数 据挖掘过程不是线性的，要取得好的结果就要反复进行 反复的挖掘过程 数据选取耳标数据数据变换数据挖掘结果的解释评价与可视化 图2 - 3 数据挖掘的基本过程 2 3 1 确定业务对象 清晰定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的 最后结果是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖 掘是带有盲目性的，是不会成功的。在定义挖掘对象时，需要确定这样一些问题： 从何处入手；需要挖掘什么数据；需要多少数据；数据挖掘要进行到什么程度。 虽然在数据挖掘中，常常事先不能确定最后挖掘的结果到底是什么，有的挖掘技 术是不需要冈变量的无教师挖掘或聚类分析但是在为挖掘工具准备数据的过程 中就已经表明了挖掘者的意图。 2 3 2 数据准备 1 数据的选择 在确定数据挖掘的业务对象后，需要搜索所有与业务对象有关的内部数据和 外部数据，从中选择出适合于数据挖掘应用的数据。如果数据挖掘是基于数据仓 天津大学硕士学位论文第二章数据挖掘概述 库的，那么数据的选择比较简单，否则，就要从各种数据源选择数据，并将其集 成和合并到单一的数据挖掘库中，而且要协调来自多个数据源的数据在数值上的 差异。在数据选择时，还需要分析清楚那些数据是数据挖掘中比较重要的数据源。 2 数据的预处理 由于所选取的数据可能具有这样一些特性：巨量性、动态性、噪声性、缺值 和稀疏性，所以需要对其进行预处理，包括消除噪声或数据清洗、推导计算缺失 值、消除数据的不一致性、消除重复记录以及完成数据类型转换等。 在数据预处理完成后，有时需要建立一个数据挖掘库，因为操作性数据库和 共有数据仓库中所提供的数据格式并不满足数据挖掘的需要，而且数据挖掘的进 行还可能影响到其它系统的应用。 3 数据的变换 数据变换的主要目的是消减数据维数或降维，从初始特征中找出真正有用的 特征以减少数据挖掘时要考虑的特征或变量个数。另外，为了适应所选择的数据 挖掘算法和工具，也要对数据做一些相应的变换。如神经网络要求所有变量的取 值都在1 之间。 2 3 3 数据挖掘 根据用户的要求，首先确定数据挖掘是发现何种类型的知识。然后选择合适 的挖掘算法，这包括选取合适的模型和参数，并使挖掘算法与整个数据挖掘的评 判标准相一致。最后由挖掘系统对数据进行分析，实现自动挖掘。 2 3 4 结果的解释评价与可视化 对数据挖掘中抽取到的模式必须经过用户或机器的解释与评价，在此过程 中，为了取得更有效的知识，可能会返同前面处理的某些步骤反复进行。另外， 数据挖掘结果最终是面向用户的，囚此对发现的模式进行可视化处理，或者把结 果转换为用户易懂的表示方法也是必需的。 2 3 5 知识同化 数据挖掘的结果要能够在实际中得到应用，需要将分析得到的知识集成到业 务信息系统的组织机构中去，让其在系统中应用并得到检验。 天津大学硕士学位论文 第二章数据挖掘概述 2 4 数据挖掘技术 数据挖掘模型本质上可以分为预测型模型与描述型模型。预测型模型在可用 数据集的基础上生成新的、非同寻常的信息；描述型模型生成已知数据集所描述 的系统模型。常用的数据挖掘技术有以下几类7 ： 2 4 1 传统统计类方法 利用统计学原理对数据进行分析，可细分为相关分析、回归分析、判别分析、 聚类分析、邻近算法等。 2 4 2 决策树和决策规则 决策树和决策规则主要是为人工智能所开发的归纳学习方法，它采用“分而 治之”的方法将问题的搜索空间分为若干子集，是典型的属于以逻辑模型的方式 输出的分类方法的数据挖掘技术，它很擅长处理非数值型数据。 2 4 3 关联规则 规则推理是从统计意义上对数据中的“如果一那么”规则进行寻找和推导， 发现数据项之间的关系。发现的这些关系不是数据中固有的，也不表示任何因果 性和相关性，而是探测项目的普遍使用情况。 2 4 4 遗传算法 遗传算法本质上是一种不依赖具体问题的直接搜索方法，是一种基于进化理 论，并采用自然选择、遗传交叉及遗传变异等设计方法的优化技术。 遗传算法把问题表示成“染色体”，在算法中是以二进制编码的串。在执行 遗传算法之前，给出一群“染色体”作为假设解，然后将这些假设解置于问题的 “环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复 制，再通过交叉、变异过程产生更适应环境的新叶“染色体”群。这样，。代 一代地进化，最后就会收敛到最适应环境的个“染色体”一卜，它就是问题的最 优解。 遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制等方 面都得到应用。 天律大学硕士学位论文第二章数据挖掘概述 2 4 5 人工神经网络 人工神经网络通过学习待分析数据中的模式来构造模型，一般可对隐类型进 行分类，用于非线性的、复杂的数据。神经网络由“神经元”的互连或按层组织 的结点构成。神经网络模型由三个层次组成：输入层、中间层和输出层，如图 2 - 4 所示。在每一神经元求得输入值后，再汇总计算总输入值，由过滤机制比较 总输入值，然后确定网络的输出值。当修改连接层的“接度”或权值时，神经网 络就实现了“学习”或“训练”2 ”。 神经网络从经验中学习，经常用于发现一组输入数据和一个结果之间的未知 联系，能对许多复杂的构成进行预测，用于分类和回归。 神经元 2 4 6 模糊逻辑 图2 - 4 神经网络结构 基于规则的分类系统往往是以确定性的规则进行分类决策的，但在日常生活 和科学实验中，经常会碰到一些模糊性的概念和数据，将模糊逻辑引入其中，可 以实现较高抽象层次的处理，对于数据挖掘系统中的分类功能非常有用。在基于 规则的系统中使用模糊逻辑时，要考虑如何将连续的属性值映射到离散的分类 上；如果有多个模糊逻辑规则时，考虑如何选择可启用的规则。 天津大学硕士学位论文 第三章聚类分析概述 第三章聚类分析概述 聚类分析是将数据对象分组为多个类或簇( e l u s t e o 的数据挖掘技术，在数据 挖掘中，聚类分析主要集中在聚类方法的可伸缩性、对聚类复杂形状和复杂类型 的数据有效性、高维聚类分析技术以及针对大型数据库中混和数值和分类数据的 聚类方法上。聚类应用包括动植物分类、疾病分类、图像处理、模式识别、市场 研究、文本检索等领域。 3 1 聚类分析概念 聚类分析是依据样本间关联的度量标准将其自动分成几个类，且使同一类中 的样本相似，而属于不同类的样本相异的一组方法。一个聚类分析系统的输入是 一组样本和一个度量两个样本间相似度( 或相异度) 的标准，聚类分析的输出是 数据集的几个类( 簇) ，这些类构成一个分区或分区结构。聚类分析的一个附加 结果是对每个类的综合描述，这种结果对于更进一步深入分析数据集的特征是尤 其重要的。 3 1 1 聚类原理 在样本空间x 的聚类算法中，用一个数据向量表示一个样本x ( 或特征向量， 观察值) ，假设每一个样本x 。x ，i = l ，n 都用向量x i = x “，x 1 2 ，x l 。 来表示，m 的 值是样本的维数( 特征) ，n 是一个聚类过程的样本空间x 中的样本数。对于特定 的聚类问题，一个算法产生的簇可能有许多性质，最重要的一条性质就是“较高 的簇内相似性，较低的簇问相似性”8 。 由于相似度是定义一个聚类的基础，所以同一特征空间的两个簇的相似度的 度量标准对大多数聚类算法都是必不可少的。一般不是计算两个样本问的相似 度，而是用特征空间中的距离作为度量标准来计算两个样本间的相异度，对于某 个样本空间，距离的度量标准可以足度量的或是半度量的，以便用来量化样本的 相异度。 聚类中的“相异度”表示当x 和x 是两个相似样本时，s ( x ，x ) 的取值是很大 的，当x 和x 不相似时，s ( x ，x ) 的取值是很小的，而且相似度的度量标准s 具有 自反性： 天津大学硕士学位论文第三章聚类分析概述 s ( x ，x 户s ( x ，x ) ， v x ，x x 对于大多数聚类方法，相似度的度量标准可以标准化为： o l 。 ( 4 ) 通过随机采样消除异常数据，若一个簇增长太慢，就删除该簇。 ( 5 ) 对局部的簇进行再聚类，落在每个新形成的聚类中的代表点，则根据用 户定义的收缩因子a 收缩或向簇中心移动。这些点将用于代表并描绘出聚类的边 界。 ( 6 ) 对簇中的数据标记上相应簇标记。 c u r e 该算法的时间复杂度为o ( n ) ，最大问题是无法处理分类属性。 4 3 划分方法 划分聚类方法是给定一个1 1 个对象或元组的的数据库构建k 个划分的方法。 每个划分为一个聚簇，并且k 曼n 。每个组至少包含一个对象，每个对象必须属于 而且只能属于一个组( 模糊划分计算除外) 。所形成的聚类将使得一个客观划分 标准( 常称为相似函数) 最优化，从而使得一个聚类中对象是“相似”的，而不同 聚类中的对象是“不相似”的。 4 3 1 传统划分方法 最常见的划分方法就是k 一平均( k m e a n s ) 算法和k 一中心点( k - m e d o i d s ) 算法 【7 ) 1 k 一平均算法 k - - 平均算法是一种迭代的聚类算法，迭代过程中不断移动簇集中的对象直 至得到理想的簇集为止，每个簇用该簇中对象的平均值来表示。利用k 一平均算 法得到的簇，簇中对象的相似度很高，不同簇中对象之间的相异度也很高。处理 过程如下算法： ( 1 ) 从n 个数据对象随机选取k 个对象作为初始簇中心。 ( 2 ) 计算每个簇的平均值，并用该平均值代表相应的簇。 ( 3 ) 计算每个对象与这些中心对象的距离，爿根据最小距离重新对相应对象 进行划分。 ( 4 ) 转第二步，重新计算每个( 自变化) 簇的平均值。这个过程不断重复直到 某个准则函数不再明显变化或者聚类的对象不再变化为止。 一般，k 一平均算法的准则函数采用平方误差准则，定义为： e = 竺胙。l p - m ，i 公式( 4 1 ) 天津大学硕士学位论文 第四章聚类分析方法 其中，e 是数据集中所有对象与相应聚类中心的均方差之和，p 为给定的数据 对象，m 为聚类c 的均值( p 和m 均是多维的) 。 k 一平均算法对于大型数据库是相对可伸缩的和高效的，算法的时间复杂度 为o ( t k n ) ，其中t 为迭代次数。一般情况下结束于局部最优解。但是，k 一平均 算法必须在平均值有意义的情况下才能使用，对分类变量不适用，事先还要给定 生成簇的个数，对噪声和异常数据比较敏感，不能对非凸面形状的数据进行处理。 2 k - - 中心点算法 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 算法，也被称为k - - 中心点算法，每个簇 用接近中心点的一个对象来表示。首先为每个簇随意选择一个代表对象，剩余的 对象根据其与代表对象的距离分配给最近的一个簇，然后反复地用非代表对象来 代替代表对象，以提高聚类的质量。 处理过程如下算法： ( 1 ) 从1 1 个数据对象随机选择k 个对象作为初始聚类( 中心) 代表。 ( 2 ) 依据每个聚类的中心代表对象，以及各对象与这些中心对象间距离，并 根据最小距离重新对相应对象进行划分。 ( 3 ) 任意选择一个非中心对象o 。d 0 。，计算其与中心对象o 交换的整个距离 代价改变量。 ( 4 ) 若距离代价改变量为负值则交换o d 。与o 以构成新聚类的k 个中心对 象。 ( 5 ) 转第二步，重新计算每个( 有变化) 簇的中心点。这个过程不断重复直到 某个准则函数不再明显变化或者聚类的对象不再变化为止。 其中，准则函数可同k 一平均算法。 当存在噪声和异常点数据时，k - - 中心点算法比k 一平均算法更好，但k 一中 心点算法的计算代价较高，算法的时间复杂度蔓j o ( t k ( n k ) 2 ) ，不能很好地扩展到 大型数据库上去。 4 3 2 大型数据库的划分方法 c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a n d o m i z e ds e a r c h ) 将采 样技术和p a m 结合起来，c l a r a n s 在搜索的每步带一定的随机性地抽取一 个样本，抽样次数( n u m l o c a l ) 作为参数被用户输入。聚类过程可以被描述为对一 个图的搜索，图中的每个节点是一个潜在的解，也就是说，k 个中心点的集合。 在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居。随机尝 试的邻居的数目( m a x n e i i g h b o r ) 被用户定义的一一个参数加以限制。如果一个更好的 天津大学硕士学位论文 第四章聚类分析方法 邻居被发现，也就是说它有更小的平方一误差值，c l a r a n s 移到该邻居节点， 处理过程重新开始；否则当前的聚类达到了一个局部最优。如果找到一个局部最 优，c l a r a n s 从随机选择的节点开始寻找新的局部最优。 研究结果表明，当n u m l o c a l = 2 ，m a x n e i b o r = m a x ( ( o 0 1 2 5 k ( n k ) ) ，2 5 0 ) 时。 聚类效果较好。c l a r a n s 能够探测孤立点，但是c l a r a n s 算法的计算复杂度 大约是0 伽2 ) ，而且，它的聚类质量取决于所用的抽样方法2 。 4 4 基于密度的方法 由于基于距离的划分方法只能发现球形簇，不能发现其他形状的簇。密度聚 类则只要邻近区域的密度( 对象或数据点的数目) 超过某个阈值，就继续聚类。 也就是说，对给定类中的每个数据点，在一个给定的区域内必须至少包含某个数 目的点。这样，密度聚类方法就可以用来过滤“噪声”异常点数据，发现任意形 状的簇。 在密度聚类算法中，有基于高密度连接区域的d b s c a n ( d e n s i t y - b a s e d s p a t i a lc l u s t e d n go f a p p l i c a t i o nw i t hn o i s e ) 算法、通过对象排序识别聚类结构的 o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 算法和基于密度分布 函数聚类的d e n c l u e ( d e n s i t y b a s e dc l u s t e r i n g ) 算法。 d b s c a n 通过不断生长足够高密度区域来进行聚类，它能从含有噪声的空间 数据库中发现任意形状的聚类。d b s c a n 方法将一个聚类定义为一组“密度相连” 的点集。下面介绍d b s c a n 的基本思想，以及基本思想所涉及的一些概念4 。 ( 1 ) 对象的e 一邻域：给定对象的e 半径内的区域。 ( 2 ) 核心点：一个对象的e 一邻域至少包含最小数目( m i n p t s ) 个对象，则称该 对象为核心点。 ( 3 ) 直接密度可达：给定一组对象集合d ，如果p 是在q 的e 一邻域内，而 q 是个核心点，则称对象p 从对象q 出发是直接密度可达的。 ( 4 ) 密度可达：如果存在一个对象链p 1 ，p 2 ，p m ，其中p 1 = q ，t i p 。= p ，对于 p l d ，( i i n ) ，卧l 是从p 。关于e 和m i n p t s 直接密度可达的，则对象p 是从对象q 关于e 和m i n p t s 密度可达的。 ( 5 ) 密度相连：如果对象集合d 中存在一个对象o ，使得对象p 和q 是从o 关于和m i n p t s 密度可达的，则对象p 和q 是关于和m i n p t s 密度相连的。 ( 6 ) 边界点：非核心点，是从某 - 核心点直接密度可达的。 ( 7 ) 噪声：聚类结束时，不属于任何簇的点。 d b s c a n 算法首先需要用户给定聚类对象的半径e 一邻域和e 一邻域中最小 天津大学硕士学位论文 第四章聚类分析方法 包含的对象数m i n p t s ，然后算法检查某个对象e 邻域中的对象数，如果对象数 大于m i n p t s ，该对象就是核心对象，就构建以该对象为核心的新簇。然后，反 复寻找从这些核心对象出发在e 一邻域内的对象，这个寻找过程可能会合并一些 簇，直到没有新的对象可以添加到任何簇中为止。 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含 在任何簇中的对象被认为是“噪声”。如果采用空间索引，d b s c a n 的计算复杂 程度是o ( n l o g n ) ，否则，计算复杂度是0 ( n 2 ) 。该算法对用户定义的参数是敏感 的。 4 5 基于网格的方法 网格聚类方法是将对象空间量化为有限数目的单元，形成一个网格结构，所 有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点 是处理速度快，其处理时间独立于数据对象的数目，只与量化空间中每一维上的 单元数目有关。 在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d - b a s e dm e t h o d ) 算法、用小波转换方法进行聚类 的w a v e c l u s t e r 方法和在高维数据空问基于网格和密度的c l i q u e ( c l u s t e r i n gi n q u e s t ) 聚类方法。 w a v e c l u s t e r 方法首先通过在数据空问上强加一个多维网格结构来汇总数 据，每个网格单元汇总了一组映射到该单元中的点的信息，然后采用一种小波变 换来变换原特征空间，汇总信息在进行小波变换时使用，接着在变换后的空间中 找到聚类区域。 由于小波变换的特性使该算法具有很多优点：它能够有效地处理大数据集 合，发现任意形状的簇，成功地处理孤立异常点，对于输入的顺序不敏感，不要 求指定诸如结果簇的数目或邻域半径等输入参数。试验分析发现w a v e c l u s t e r 在 效率和聚类质量上优于c l a r a n s 和d b s c a n ，同时w a v e c l u s t e r 能够处理多达 2 0 维的数据，并且速度很快，复杂度是o ( n ) ”。 4 6 基于模型的方法 基于模型的聚类方法为每一个簇假定了一个模型，寻找数据对给定模型的最 佳拟合，它试图优化给定的数据和某些数学模型之间的适应性，基于模型的方法 经常假设数据是根据潜在的概率分布生成的，算法主要有统计学和神经网络两 天津大学硕士学位论文 第四章聚类分析方法 种。 c o b w e b 是一种流行的简单增量概念聚