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

聚类分析数据挖掘方法的研究与应用 摘要 随着信息技术的发展，数据挖掘技术得到了广泛的关注。在数据挖掘技术中 有很多研究领域，聚类分析数据挖掘就是其中一个重要的研究方向，对它进行深 入研究不仅有着重要的理论意义，而且有着重要的应用价值。聚类分析就是将一 组物理或抽象对象，分组为类似对象组成的多个簇，在同一个簇中的对象彼此相 似，不同簇中的对象彼此相异。目前，聚类分析已经广泛地应用于模式识别，数 据分析，图像处理，以及市场研究等。 在数据挖掘中，聚类是一个活跃的研究领域。目前在文献中存在大量的聚类 算法。算法的选择取决于数据的类型、聚类的目的和应用。聚类算法具体可以分 为划分方法，层次方法，基于密度的方法，基于网格的方法，以及基于模型的方 法等。其中，在中、小规模的数据聚类应用中，划分方法在可理解度、易训练性、 易实施性和通用性等方面优于其他的分类方法。 在以上研究的基础上，本文探讨了聚类技术在成人高校教学管理中的应用。 通过对计算机课程的相关教师“听课记录表”的数据分析，依据聚类挖掘的实施 流程，进行了各项数据预处理，应用划分方法中的k - m e a n s 算法，随机生成初始 的聚类，然后用反复迭代重新定位质心，改进聚类结果，最终使每个簇的平方误 差最小，完成了对教师“听课记录表”的c + + 语言的聚类实现，并对聚类结果进 行了分析和验证，得出了一些有实际意义的结论用于指导教学管理。 关键词：数据挖掘；聚类：划分方法；k - m e a n s 算法 i i a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，d a t am i n i n gh a sb e e n p a i da t t e n t i o ne x t e n s i v e l y a sw ek n o w ，d a t am i n i n gh a sal a r g er e s e a r c h s c o p e ，c l u s t e ra n a l y s i si s o n eo fi m p o r t a n tr e s e a r c hs u b j e c ti ni t r e s e a r c h i n gi n t ot h es u b j e c td e e p l yh a sm o s ti m p o r t a n tv a l u e sn o to n l y o nt h e o r e t i cb u ta l s oo na p p l i c a t i o n s c l u s t e r i n gd i v i d e sas e to f p h y s i c a lo ra b s t r a c to b j e c ti n t os e v e r a lc l u s t e r st h a tc o n s t i t u t e sf o r t h es i m i t a ro b j e c t ，t h eo b j e c ti nt h es a i i l eo fc l u s t e ra r es i m i l a re a c h o t h e r ，b u tt h eo b j e c ti nt h ed i f f e r e n tc l u s t e ra r ed i s s i m i i i r u d ee a c h o t h e r a tp r e s e n t ，c l u s t e r i n gh a sb e e na p p li e dt op a t t e r nr e c o g n i t i o n ， d a t aa n a l y s i s ，i m a g ep r o c e s s i n g ，a n dm a r k e tr e s e a r c h c l u s t e r i n gi sav e r ya c t i v er e s e a r c ha r e ai nd a t am i n i n g t h e r ea r e ag r e a tq u a n t i t i e so fc l u s t e r i n ga l g o r i t h m si nt h ed o c u m e n t a t i o n t o c h o o s eaa l g o r i t h mi sd e c i d e db yt h et y p eo ft h ed a t a ，t h ep u r p o s ea n d t h ea p p l i c a t i o no ft h ec l u s t e r i n g c l u s t e r i n ga l g o r i t h m sc a nb r a n c ho u t i n t ot h ep a r t i t i o n i n gm e t h o d ，t h eh i e r a r c h i c a lm e t h o d ，t h ed e n s i t y b a s e d m e t h o d ，t h eg r id - b a s e dm e t h o d ，a n dt h em o d e l b a s e dm e t h o de t c a m o n gt h e m ， i nm e d i u ma n ds m a l ls c a l ea p p l i c a t i o no fd a t ac l u s t e r i n g ，t h ep a r t i t i o n i n g m e t h o ds u r p a s st oo t h e rm e t h o d si nt h ee a s yc o m p r e h e n s i o n ，e a s yt r a i n i n g ， e a s ye x e c u t i o na n dg o o dc u r r e n c ye t c o nt h eb a s eo fa b o v es t u d i e s ，i nt h i sp a p e r ，w ep r o b e daa p p l i c a t i o n o fc l u s t e r i n gt e c h n o l o g yi nt h et e a c h i n gm a n a g e m e n to ft h eh i g h s c h 0 0 1 t h r o u g hd a t aa n a l y s i sf o r at a b l eo fh e a r i n gal e s s o n ”o fc o m p u t e r c l a s s a c c o r d i n gt oi m p l e m e n tf l o wo fc l u s t e r i n gm i n i n g ，w ec a r r i e do i l a l lk i n d so f d a t ap r e p r o c e s s i n g ，w eu s e dt h ep a r t i t i o n i n gm e t h o d s k - m e a n sa l g o r i t h m st og e n e r a t et h ef i r s tc l u s t e r ，t h e nu s e dt h e r e p l a c e m e n to v e ra n do v e rt ol o c a t em e a n si no r d e rt oi m p r o v i n gc l u s t e r i n g r e s u l t ，i nt h ee n d ，m a d et h es q u a r ee r r o rm i n i m u mo fe a c hc l u s t e rm i n i m u m ， i l l 聚类分析数据挖掘方法的研究与应用 c o m p l e t e dc l u s t e r i n go ft e a c h e r s ”at a b l eo fh e a r i n gal e s s o n u s i n g c hp r o g r a m t h e na n a l y z e da n dv e r i f i e dt h er e s u l t so fc l u s t e r i n g ，a n d c o n c l u d e ds o m er e s u l t so fh a v i n gm e a n i n gp r a c t i c a l l yt og u i d et e a c h i n g m a n a g e m e n t k e y w o r d ： d a t am i n i n g ：c l u s t e r i n g ：p a r t i t i o n i n gm e t h o d ：k m e a n sa l g o r i t h m 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机构的 学位或证书而使用过趵材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：7 易易签字日期：卯声矿月对七 学位论文版权使用授权书 本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期 驴t 。 ：7 士弓 1 年妒月刊日 学位论文作者毕业去向 工作单位： 通讯地址： 导师签名 签字日期 电话：；矽77 乃 邮编： 口t 耐 砸 邳矽 第一章绪论 第一章绪论 随着信息科学技术的发展，数据库管理系统应用越来越广泛，数据库的规模 也在不断地扩大，人们积累了海量的商业数据，例如客户数据、交易历史数据、 销售记录等等。这些数据库中蕴含着大量有价值的商业信息，目前应用的数据库 系统尽管可以高效地实现数据的录入、查询、统计等功能，却无法发现数据中存 在的关系和规则，无法根据现有的数据预测未来的发展趋势，这使得我们的企业 不得不两对“数据丰富，知识贫乏”【1 j 的尴尬处境。面对这种数据的汪洋大海， 如何从中发现有价值的信息成为一个急需解决的重要问题。例如：超市的经营者 希望将经常被同时购买的商品放在一起，以增加销售量：保险公司想知道购买保 险的客户一般具有哪些特征；医学研究人员希望从已有的成千上万份病例中找出 患某种疾病的病人的共同特征，从而为治愈这种疾病提供一些帮助。在这种应用 需求的驱动下，数据挖掘( d a t am i n i n g ) ，简称d m 研究应运而生。 1 1 数据挖掘概述 数据挖掘是人们多年来对数据库技术进行大量研究和开发的成果，在2 0 世 纪8 0 年代末有了很大的发展。数据挖掘是指从数据库或数据仓库的大量数据中 揭示出隐含的、先前未知的、潜在有用的信息的过程1 2 1 。它的目标是将大容量数 据转化为有用的知识和信息。数据挖掘不但可以帮助人们从数据库特别是数据仓 库的相关数据中提取出所感兴趣的知识、规律或更高层次的信息，而且也可以帮 助人们从不同程度上去分析它们，从而可以更有效地利用数据；它不仅可以用于 描述过去数据的发展过程，而且还能进一步预测未来的发展趋势。因此，数据挖 掘正成为一个新的、日益受到重视的热点研究领域。 谈到数据挖掘，必须提到数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) ，k d d 是于1 9 8 9 年在美国召开的第1 1 届国际人工智能联合会 议的专题讨论会上提出的。k d d 泛指所有从源数据中发现模式或联系的方法， 常用来描述整个数据挖掘的过程，包括最开始的制定业务目标到最终的结果分 析。关于k d d 与数据挖掘的关系有许多不同的观点，代表了不同的数据挖掘技 聚类分析数据挖掘方法的研究与应用 术含义。 第一种观点认为k d d 是数据挖掘的一个特例。这种看法认为既然数据挖掘 系统可以在关系数据库、事务数据库、空间数据库、时序数据库、文本数据库、 多媒体数据库以及w e b 等多种数据组织形式中发现知识，那么数据库中的知识 发现k d d 只是数据挖掘的一个方面f 3 】o 它是早期比较流行的观点，这种描述强 调了数据挖掘在数据形式上的多样性。 第二种观点认为数据挖掘是k d d 过程的一个步骤。这种观点的思想是：k d d 是从数据中发现知识的全部过程，而数据挖掘则是此全部过程中的一个特定的、 关键的步骤。虽然数据挖掘可以从多种数据库及数据仓库中挖掘知识，但是这些 数据都是和数据库技术相关的。而k d d 的过程包括数据清洗、数据集成、数据 选择、数据转换、数据挖掘、模式生成及评估等一系列步骤，它是一个更广义的 范畴【刀。把数据挖掘作为k d d 的一个重要步骤看待，可以使我们聚焦研究重点， 有效解决问题。目前，人们对数据挖掘算法的研究基本属于这样的范畴。 还有一部分人认为，k d d 与数据挖掘的含义基本相同，只是叫法不一样。 事实上，在许多的文献中以及许多场合中，这两个术语都不加区分被人们所使用。 因此也有人称知识发现为数据挖掘，一般可以不加区别地使用两者。 1 。2 数据挖掘过程 数据挖掘是一个多阶段数据处理过程，主要包括以下几个步骤： 第一步：了解应用领域的知识。在开始知识发现之前首先进行的同时也是最 重要的就是了解你的数据和业务问题。 第二步：数据集成与数据清洁。数据集成将与研究问题相关的多文件或多数 据库运行环境的数据进行合并处理，数据清洁则解决数据中的语义模糊性，纠正 不一致，处理数据中的遗漏、噪声和脏数据等。 第三步：数据归约与预处理。数据归约将得到数据集的压缩表示，在归约后 的数据集上挖掘将更有效，并产生相同或几乎相同的分析结果，从而提高数据挖 掘的质量。预处理则是针对特定的算法对数据进行有序的组织和排列。 第四步：选择数据挖掘功能。根据挖掘任务的需要选择相应的挖掘功能，例 如分类、聚类或关联规则挖掘等。 第一章绪论 达。 第五步：选择适合的数据挖掘算法进行数据挖掘。 第六步：模式评估。对挖掘出来的模式进行评估，可视化、转换和知识的表 第七步：知识的应用。 图1 1 显示了数据挖掘的基本过程。 图1 1 数据挖掘的基本过程 f i g 1 1 t h eb a s i c a lp r o c e s so fd a t am i n i n g 1 3 数据挖掘任务 识 比较典型的数据挖掘任务有概念描述( c o n c e p td e s c r i p t i o n ) 、关联分析 ( a s s o c i a t i o na n a l y s i s ) 、分类和预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) ，聚类分析 ( c l u s t e r i n ga n a l y s i s ) 、孤立点分析( o u t l i e rm i n i n g ) 等。 1 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是对一 个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情况的 概述总结就会获得所售电脑基本情况的一个整体概念( 如：基本上为p i i i 以上的 兼容机) 。对一含有大量数据的数据集合进行概述性的总结并获得简明、准确的 聚类分析数据挖掘方法的研究与应用 描述，这种描述就称为概念描述。概念描述分为特征化描述和区别性描述。前者 描述目标类数据的一般特征和特性的汇总，后者是将目标类对象的一般特性与一 个或多个对比类对象的特性比较【l 】。 获得概念描述的方法主要有两种：利用更为广义的属性，对所分析数据进 行概要总结，其中被分析的数据就称为目标数据集；对两类所分析的数据特点 进行对比并对对比结果给出概要性总结，而其中两类被分析的数据集分别被称为 目标数据集和对比数据集。 2 关联分析 从广义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是发现潜藏 在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。关联知识反 映一个事件和其他事件之间的依赖或关联。数据库中的数据一般都存在着关联关 系，这种关联是复杂的，有时是隐含的。关联分析的目的就是要找出数据库中隐 藏的关联信息。关联分析发现关联规则，这些规则展示属性一值频繁地在给定数 据集中一起出现的条件。这种关联关系有简单关联、时序关联、因果关联、数量 关联等。这些关联并不总是事先知道的，而是通过数据库中数据的关联分析获得 的，因而对商业决策具有新价值。简单关联，例如：购买面包的顾客中有9 0 的 人同时购买牛奶。时序关联，例如：若a t & t 股票连续上涨且d e c 股票不下跌， 则第三大i b m 股票上涨的可能性为7 5 。它在简单关联中增加了时间属性。 关联分析广泛应用于购物篮或事务数据分析。关联规则挖掘是关联知识发现 的最常用方法，其中最为著名的是a g r a w a l 等提出的a p r i o r i 及其改进算法，关 联挖掘的目的就是从数据库中挖掘出满足最低支持度和最低可信度的关联规则。 关联规则的研究和应用是数据挖掘中比较活跃和深入的分支，己经提出了许多关 联规则挖掘的理论和算法。 3 分类和预测 分类是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应用最 多。分类就是找出描述并区分数据类或概念的模型，以便能够使用模型预测类标 记未知的对象类。分类的目的是学会一个分类函数或分类模型( 也常常称作分类 器) 。要构造这样一个分类器，需要有一个训练样本数据作为输入。分类器的作 用就是能够根据数据的属性将数据分派到不同的组中。这样我们就可以利用该分 4 第一章绪论 类器来分析已有数据，并预测新数据将属于哪一个组，即数据对象的类标记，然 而，在某些应用中，人们可能希望预测某些空缺的或不知道的数据值，而不是类 标记。当被预测的是数值数据时，通常称之为预测。分类模式可以采用多种形式 表示，如分类规则，判定树，数学公式或神经网络。分类知识挖掘的一些有代表 性的技术有：决策树、贝叶斯分类、神经网络分类、遗传算法、类比学习和案例 学习，以及粗糙集和模糊集等方法。 分类应用的实例很多。例如，我们可以将银行网点分为好、一般和较差三种 类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况等， 并决定它们分类的关键属性及相互间关系。此后就可以根据这些关键属性对每一 个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。 4 聚类分析 。 一般把学习算法分成有导师( 或监督) 和无导师学习两种方式，主要区别是有 没有类信息作为指导。聚类是典型的无导师学习算法。聚类分析数据对象，而不 考虑已知的类标记，它将数据对象分组成为多个类或簇，同一个类中的对象具有 较高的相似度，而不同类中的对象差别较大。一般情况下，训练数据中不提供类 标记，聚类可以用于产生这种标记。聚类按照某个特定标准( 通常是某种距离) ， 最终形成的每个类，在空间上都是一个稠密的区域。所形成的每个类可以导出规 则。通过聚类技术可以把数据划分为一系列有意义的子集，进而实现对数据的分 析。例如，一个商业销售企业，可能关心哪些客户对制定的促销策略更感兴趣。 聚类分析与分类和预测不同，前者总是在类标识下寻求新元素属于哪个类；而后 者通过对数据的分析比较生成新的类标识，它以某种容易理解的形式展示给用 户，刻画了数据所蕴含的类知识。 分类和聚类技术互有交叉和补充。聚类技术主要是以统计方法、机器学习、 神经网络等方法为基础的。常用的聚类算法有基于划分、层次、密度、网格和模 型的五大类聚类算法。聚类分析有很广泛的应用，包括市场或客户分割、模式识 别、数据分析、图像处理及许多其它方面。 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不致，这 些数据对象是孤立点【9 】o 在挖掘正常类知识时，通常总是把它们作为噪音来处理。 聚类分析数据挖掘方法的研究与应用 因此以前许多数据挖掘方法都在正式进行数据挖掘之前就将这类孤立点数据作 为噪声或者意外而将其排出在数据挖掘的分析处理范围之外。然而在一些应用场 合中，如信用欺诈、入侵检测等小概率发生的事件往往比经常发生的事件更有挖 掘价值。因此当人们发现这些数据可以为某类应用提供有用信息时，就为数据挖 掘提供了一个新的研究课题，即孤立点分析。孤立点探测和分析对于欺诈探测、 定制市场、医疗分析及许多其他的任务是非常有用的。发现和检测孤立点的方法 主要有基于概率统计、基于距离和基于偏差等检测技术的三类方法。 l - 4 数据挖掘方法 主要的数据挖掘方法有遗传算法、粗集方法、决策树方法、神经网络方法。 1 遗传算法的基本原理是：类比生物进化过程，每一代同时存在许多不同的 种群个体( 染色体) 。这些染色体的适应性以适应性函数f ( x ) 表征，染色体的保 留与淘汰取决于它们对环境的适应能力，优胜劣汰。适应性函数f ( x ) 的构成与 目标函数密切相关，往往是目标函数的变种。遗传算子主要有3 种：选择( 复制) 算子、交叉( 重组) 算子和变异( 突变) 算子。遗传算法可起到产生优良后代的作用， 经过若干代遗传，将会得到满足要求的后代( 问题的解) 。 2 粗集方法的基本原理是：将数据库中的行元素看成对象，将列元素看成属 性。设r 为等价关系，定义为不同对象在某个( 或几个) 属性上取值相同。那些满 足等价关系的对象构成集合，称为该等价关系r 的等价类。设e 为条件属性上的 等价类，设y 为决策属性上的等价类，则e 和y 存在3 种情况：y 包含e 称为下 近似：y 与e 的交非空，称为上近似；y 与e 的交为空，称为无关。对下近似建 立确定性规则，对上近似建立不确定规则( 含可信度) ，对无关情况则不存在规则。 3 决策树方法是以信息论原理为基础，利用信息论中互信息( 信息增益) 寻找 数据库中具有最大信息量的字段，建立决策树的一个结点。然后再根据字段的不 同取值建立树的分支，在每个分支集中重复建立树的下层结点和分支。这种方法 实际上是依循信息论原理对数据库中存在的大量数据进行信息量分析，在计算数 据特征的互信息或信道容量的基础上提取出反映类别的重要特征。 4 神经网络方法的原理是：模拟人脑的神经元结构，以m p 模型和h e b b 学习 规则建立起前馈式网络、反馈式网络和自组织网络3 大类多种神经网络模型。基 第一章绪论 于神经网络的数据挖掘工具对于非线性数据具有快速建模能力，其挖掘的基本过 程是先将数据聚类，然后分类计算权值，神经网络的知识体现在网络连接的权值 上。 1 5 数据挖掘的应用与发展趋势 数据挖掘的应用极其广泛。目前，数据挖掘技术已经在许多行业都得到应用 并取得了一定的实效，其中包括天文学、生物医学、医疗保健、d n a 分析、银 行、金融、零售业和电信业等。 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量实 验和观测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化自动 分析工具要求迫切，这种需求推动了数据挖掘技术在科学研究领域的应用发展， 并且已获得一些重要成果。 数据挖掘在市场营销中的应用可分为两类：数据库市场营销和购物篮分析。 前者的任务是通过交互查询、数据分割和模型预测等方法来选择有潜力的顾客以 便向他们推销产品。后者的任务是分析市场销售数据以识别顾客的购买行为模 式，从而帮助确定商店货架的布局，促进商品的销售。 在银行业，数据挖掘主要用于信用欺诈的建模和预测、风险评估、趋势分析、 收益分析以及辅助直销活动。在金融市场，已将神经网络用于股票价格预测、购 买权交易、债券等级评定、资产组合管理、商品价格预测以及金融危机预测等方 面。 电信业已经从单纯的提供市话和长话服务演变成提供综合电信服务，如语 音，传真、寻呼、移动电话、图像、电子邮件、计算机和w 曲数据传输，以及 其他数据通信服务。而且随着许多国家对电信业的开放和通信技术的发展，电信 市场正在迅速扩张并愈发竞争激烈。因此，利用数据挖掘技术来帮助理解商业行 为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务质量是非常有必 要的。 数据挖掘语言的设计、高效的数据挖掘方法和集成的数据挖掘环境的建立以 及应用数掘挖掘技术解决大型应用问题，都是目前数据挖掘研究和应用开发所面 临的主要问题。 7 聚类分析数据挖掘方法的研究与应用 鉴于数据、数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许多 挑战性的课题，下面是数据挖掘的主要发展趋势，它反映了面对这些挑战的应对 策略。 1 算法效率和可伸缩住。目前，数据库的规模呈指数增长。据统计，数据和 计算资源的增长速度符合摩尔定理，每1 8 个月翻一番。因此，海量数据挖掘的 最大挑战不仅仅在于数据库的绝对规模，还在于数据挖掘系统能够处理这些持续 增长的数据集合。为了保证高效率，数据挖掘系统必须能有效地处理海量数据， 其算法必须是高效率和可伸缩的。 2 处理不同类型的数据和数据源。目前数据挖掘系统处理的数据库大多是关 系数据库。随着数据库应用范围的日益扩大和规模、功能的日益完善，数据库中 将包含大量复杂的数据类型。如结构化的数据，复杂的数据对象，混合文本，多 媒体数据，时空数据，事务数据及历史数据等，甚至出现新的数据库模型。因此， 保证数据挖掘系统能有效地处理此类数据库中的数据是至关重要的。 3 数据挖掘系统的交互性。数据挖掘中操作者的适当参与能加速数据挖掘过 程。一方面，交互界面接收用户的检索、查询要求和数据挖掘策略，为用户表达 要求和策略提供了方便；另一方面，交互界面又把生成的结果传递给用户，由于 生成的结果可以是多种多样，因此，准确而直观地描述挖掘结果和友好而高效的 用户界面一直是研究的重要课题。 4 w e b 挖掘。由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越 重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务， 将成为数据挖掘中一个最为重要和繁荣的子领域。 5 数据挖掘中的隐私保护与信息安全【2 0 1 。数据挖掘能从不同的角度、不同的 抽象层上看待数据，这将潜在地影响数据的私有性和安全性。随着计算机网络的 日益普及，研究数据挖掘可能导致的非法数据入侵是实际应用中需要解决的问题 之一。 6 探索新的应用领域。早期的数据挖掘主要集中在帮助企业提高竞争能力。 随着数据挖掘的日益普及，它的应用领域也在不断扩大。信息产业的发展为数据 挖掘提供了广阔的空间，数据挖掘技术的应用范围将不断得到拓宽，特别是在生 物工程、商业智能、网络服务等领域的应用将成为新的研究热点。同时由于通用 8 第一章绪论 数据挖掘系统在处理特定应用问题时有其局限性，因此，目前的一种趋势是开发 针对特定应用的数据挖掘系统。 7 数据挖掘语言的标准化。标准的数据挖掘语言或有关方面的标准化工作将 有助于数据挖掘系统的研究和开发，有利于用户学习和使用数据挖掘系统。研究 专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准 化。 8 可视化数据挖掘【1 9 1 。可视化数据挖掘是从大量数据中发现知识的有效途 径。目前数据挖掘的可视化仅体现在结果的简单描述，而数据可视化、挖掘过程 和结果可视化，将揭开数据挖掘神秘的面纱，使其变得更为生动、形象和具体。 数据和结果的图形展示可以放大、缩小、平移、旋转和变换角度，使分析人员和 用户更加容易理解，将大大推动数据挖掘工具在发现知识和数据分析中的应用。 因此，数据挖掘的可视化具有重要的理论意义和应用价值。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、 越来越复杂，数据挖掘将发挥出越来越大的作用。 1 6 论文的工作 在本章中，我们首先对数据挖掘问题进行了基本的概述，并对数据挖掘的过 程、任务和方法进行了介绍，最后对数据挖掘的应用和发展趋势做了探讨。由于 数据挖掘技术包含的内容很多，涉及到的知识领域也很广，在这里只做基本介绍。 在本论文中我们将就聚类分析数据挖掘中的相关问题进行深入的探讨。 在第二章中，我们介绍什么是聚类分析，数据挖掘对聚类的典型要求，重点 研究了聚类分析中的数据类型及各种数据类型的相异度计算，最后介绍了聚类的 分析过程和主要的聚类方法。 第三章我们研究进行聚类分析使用的各种方法，包括划分、层次、基于密度、 基于网格、基于模型等五种方法。特别是对比较容易理解概念、比较容易建立模 型的适合中、小规模数据聚类的方法，如，划分方法中的k - m e a n s 算法和p a m 算 法、层次方法中的单连接算法等进行了详细的研究。 第四章我们探讨了聚类技术在成人高校教学管理中的应用。通过对计算机课 程的相关教师“听课记录表”的数据分析，依据聚类挖掘的实施流程，进行了各 聚类分析数据挖掘方法的研究与应用 种数据预处理，最后应用划分方法中的k - m e a n s 算法，进行了聚类实现，得出了 一些有实际意义的结论。这些结论与学校的教学情况基本上是一致的，根据这些 结论可以采取针对性措施，用于提高学校的教学水平、教学质量。 第五章是总结和展望。回顾了全文的工作，探讨了不足和进一步的改进。 i o 第二章数据挖掘中的器类技术 第二章数据挖掘中的聚类技术 数据聚类( c l u s t e r i n g ) 在数据挖掘中是一项非常重要的任务，目前已经广 泛地应用于模式识别，数据分析，图像处理，以及市场研究。 本章首先介绍聚类分析的概念、应用以及数据挖掘对聚类分析的要求，接下 来详细介绍了聚类分析中的数据类型及各种数据类型的相异度计算，最后介绍了 聚类分析的过程和主要方法。 2 1 什么是聚类分析 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称 为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对 象彼此相似，与其它簇中的对象相异。 聚类分析已经广泛地用在许多应用中，包括模式识别，数据分析，图象处理 以及市场研究。通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分 布模式，以及数据属性之间的有趣的相互关系。 聚类的典型应用是什么? 在商务上，聚类能帮助市场分析人员从客户基本库 中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上， 聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的 认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及 根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。 聚类也能用于对w e b 上的文档进行分类，以发现信息。 作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布 的情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析。而且，聚类 分析可以作为其他算法( 如特征和分类等) 的预处理步骤，这些算法再在生成的 簇上进行处理。另外，聚类分析可以完成孤立点挖掘。许多数据挖掘算法试图使 孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用的。如在欺 诈探测中，孤立点可能预示着欺诈行为。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 聚类分析数据挖掘方法的研究与应用 数据挖掘对聚类的典型要求如下： 1 、可伸缩性：许多聚类算法在小于2 0 0 个数据对象的小数据集合上工作得 很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样 本上进行聚类可能会导致有偏差的结果。我们需要具有高度可伸缩性的聚类算 法。 2 、处理不同类型属性的能力：许多算法被设计用来聚类数值类型的数据。 但是，应用可能要示聚类其他类型的数据，如二元类型( b i n a r y ) ，分类标称 ( c a t e g o r i c a l n o m i n a l ) ，序数型( o r d i n a l ) 数据，或者这些数据类型的混合。 3 、发现任意形状的聚类：许多聚类算法基于欧几里得距离或者曼哈坦距离 度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的 球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重 要的。 4 、用于决定输入参数的领域知识最小化：许多聚类算法在聚类分析中要求 用户输入一空的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏 感。参数通常很难确定，特别是对于包含高维对象的数据集来说，更是如此。要 求用户输入参数不仅加重了用户的负担，也使得聚类的质量难以控制。 5 、处理噪声数据的能力：绝大多数现实世界中数据库都包含了孤立点，空 缺，未知数据或者错误的数据。些聚类算法对于这样的数据敏感，可能导致低 质量的聚类结果。 6 、对于输入记录的顺序不敏感：一些聚类算法对于输入数据的顺序是敏感 的。例如，同一个数据集合当以不同的顺序提交给同一个算法时，可能生成差别 很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。 7 、高维性( h i g hd i m e n s i o n a l i t y ) ：一个数据库或者数据仓库可能包含若 干维或者属性。许多聚类算法擅长处理低维的数据，可能只涉及两到三维。人类 最多在三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是 非常有挑战性的，特别是考虑到这样的数据可能非常稀疏，而且高度偏斜。 8 、基于约束的聚类：现实世界的应用可能需要在各种约束条件下进行聚类。 假设你的工作是在一个城市中给定数目的自动提款机( 即a t m ) 选择安放位置。 为了作出决定，你可以对住宅区进行聚类，同时考虑如城市的河流和公路网，每 第二章数据挖掘中的聚类技术 个地区的客户要求等情况。要找到既满足特定的约束，又具有良好聚类特性的数 据分组是一项具有挑战性的任务。 9 、可解释性和可用性；用户希望聚类结果是可解释的，可理解的，和可用 的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应用目标如何影 响聚类方法的选择也是一个重要的研究课题。1 。 2 2 聚类分析中的数据类型 下面，我们研究在聚类分析中经常出现的数据类型，以及如何对其进行预处 理。假设要聚类的数据集合包含n 个数据对象，这些数据对象可能表示人、房子、 文档、国家等。一般聚类算法选择如下两种有代表性的数据结构： 1 、数据矩阵( d a t am a t r i x ，或称为对象与变量结构) ：它用p 个变量( 也称为 度量或属性) 来表现n 个对象，例如用年龄、身高、体重、性别、种族等属 性来表现对象“人”。这种数据结构是关系表的形式，或者看成n x p ( n 个对 象p 个变量) 的矩阵。 z 1r x l d 工f x i d x x n d ( 2 1 ) 2 、相异度矩阵( d i s s i m “a r i t ym a t r i x ，或称为对象一对象结构) ：存储1 3 个对 象两两之间的近似性，表现形式是一个n 1 3 维的矩阵。 0 d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 d ( n ，1 ) d ( n ，2 ) 0 ( 2 2 ) 在这里d ( i ，j ) 是对象i 和对象j 之间相异性的量化表示，通常它是一个非 负的数值，当对象i 和j 越相似或“接近”，其值越接近0 ；两个对象越不同， 其值越大，而且d ( i ，j ) = d ( j ，i ) ，d ( i ，i ) = o 。 许多聚类算法以相异度矩阵为基础，如果数据是用数据矩阵的形式表现的， 在使用该算法之前要将数据矩阵转化为相异度矩阵。那么“如何估算相异度 聚类分析数据挖掘方法的研究与应用 d ( i ，j ) ? ”下面研究如何计算用区间标度变量，二元变量，标称、序数和比例标 度变量，或这些变量类型的组合来描述的对象的相异度( 相似度) 。 1 、区间标度变量：区间标度变量是一个粗略线性标度的连续度量。典型例 子包括重量和高度，经度和纬度坐标，以及大气温度等。 区间标度变量对象间的相异度d ( i ，j ) 是基于对象间的距离来计算的，最常 用的距离度量方法是欧几里德距离，它的定义如下： d ( i ，j ) = 如。1 ，f 2 + i x 旷f 2 + + k 一f 2 ( 2 3 ) 这里的i = ( x ，x i 2 ，x 。) 和i = ( 1 小x j 2 ，x j 。) 是两个p 维的数据对象。 另一个著名的度量方法是曼哈坦距离，其定义如下： d ( i ，j ) = k - - x 一+ k x ，：卜+ k b i ( 2 4 ) 上面的两种距离度量方法都满足对距离函数的如下数学要求： 1 ) d ( i ，j ) 0 ：距离是一个非负的数值。 2 ) d ( i ，i ) = o ：一个对象与自身的距离是0 。 3 ) d ( i ，j ) = d ( j ，i ) ：距离函数具有对称性。 4 ) d ( i ，j ) d ( i ，h ) + d ( h ，j ) ：从对象i 到对象j 的直接距离不会大于途经 任何其他对象h 的距离( 三角不等式) 。 明考斯基距离是欧几里得距离和曼哈坦距离的概化，它的定义如下： d ( i ，j ) = ( i x 。- - x ，f 9 十卜，：一x ，：9 + + i x ，一x ，1 9 ) i q ( 2 5 ) 这里的q 是一个正整数。当q = l 时，它表示曼哈坦距离，当q = 2 时表示欧几 里得距离。 例嘲1 ：对于一个4 维向量x ，= ( 1 ，0 ，1 ，0 ) 和x z = ( 2 ，l ，- 3 ，一1 ) ，两个向量 间的曼哈坦距离= 1 + 1 + 4 + 1 = 7 ，欧几里德距离= ( 1 + 1 + 1 6 + 1 ) ”2 = 4 3 6 。 2 、二元变量：一个二元变量只有两个状态：0 或1 ，0 表示该变量为空，1 表示该变量存在。例如，给出一个描述病人的变量s m o k e r ，1 表示病人抽烟，0 表示不抽烟。像处理区间标度变量一样来对待二元变量会误导聚类结果，所以要 采用特定的方法来计算其相异度。 “那么，怎样计算两个二元变量之间的相似度? ”一个方法涉及对给定的数 据计算相异度矩阵。如果假设所有的二元变量有相同的权重，我们得到一个两行 1 4 第二章数据挖掘中的聚类技术 两列的可能性表( 表2 - 1 ) 如下 表2 - 1 二元变量的可能性表 t a b l e2 - 1t h ep r o b a b i l i t yo fb i n a r yv a r i a b l e 对象j 10 求和 1 q r q + r 对象i o s ts + r 求和 q + s r + t p 在表中，q 是对于对象i 和j 值都为1 的变量的数目，r 是对于对象i 值为 1 而对象j 值为0 的变量的数目，s 是对于对象i 值为0 而对于对象j 值为1 的 变量的数目，t 是对于对象i 和j 值都为0 的变量的数目。变量的总数是p ， p 2 q + r + s + t “对称的二元变量和不对称的二元变量之间的区别是什么? ”如果它的两个 状态是同等价值的，并有相同的权重，那么该二元变量是对称的，也就是两个取 值o 或1 没有优先权。例如，属性“性别”就是这样的一个例子，它有两个值： “女性”和“男性”。基于对称二元变量的相似度称为恒定的相似度，即当一些 或者全部二元变量编码改变时，计算结果不会发生变化。对恒定的相似度来说， 评价两个对象i 和j 之间相异度的最著名的系数是简单匹配系数，其定义如下： d ( i ，j ) = 生 ( 2 6 ) q + ，+ s + t 如果两个状态的输出不是同样重要，那么该二元变量是不对称的。例如一个 疾病检查的肯定和否定的结果。根据惯例，我们将比较重要的输出结果，通常也 是出现几率较小的结果编码为1 ( 例如，h i v 阳性) ，而将另一种结果编码为0 ( 例 如，h i v 阴性) 。给定两个不对称的二元变量，两个都取值1 的情况( 正匹配) 被认为比两个都取值为0 的情况( 负匹配) 更有意义。因此，这样的二元变量经 常被认为好像只有一个状态。基于这样变量的相似度被称为非恒定的相似度。对 非恒定的相似度，最著名的评价系数是j a c c a r d 系数，在它的计算中，负匹配的 数目t 被认为是不重要的，因此被忽略。 聚类分析数据挖掘方法的研究与应用 d ( i ，j ) = 旦7 ( 2 7 ) g + r + 工 例“，假设一个病人记录表( 表3 - 2 ) 包含属性n a m e ( 姓名) ，g e n d e r ( 性别) ， f e v e r ( 发烧) ，c o u g h ( 感冒) ，t e s t 一1 ，t e s t 一2 ，t e s t 一3 ，t e s t 一4 ，这里的n a m e 是对象标识，g e n d e r 是对称的二元变量，其余的属性都是非对称的二元变量。 表2 2 大部分为二元属性的关系表“ t a b l e2 - 2t h er e l a t i o n s h i po ft h em a s so fb i n a r ya t t r i b u t i o n n a m e g e n d e r t e v e r c o u g h t e s t 一1t e s t - 2t e s t - 3t e s t 一4 j a c k mynpnnn m a r y f y np n pn j i m