（概率论与数理统计专业论文）基于聚类算法的数据挖掘技术的研究.pdf

13i “j ： 原创性声明 ! ! f 1 1 l l + l l l l l li l l l l l l l l l l l l u l i j i r l l i l l 0 y171i 9 j l l l7 r l l l l13iiii119ll f i l l 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：洫日期：鲨年j 月日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：导师签名 日期：婴年上月挈日 摘要 数据挖掘可以称为数据库中的知识发现，它是从大量数据中 发现并提取隐藏在其中的可信的、新颖的、有效的并能被人理解 的模式的高级处理过程。数据挖掘解决了传统分析方法的不足， 并能够对大规模数据的进行分析处理。数据挖掘从大量数据中提 取出隐藏在数据之后的有用的信息，为人们的正确决策提供了很 大的帮助。 近些年随着我国国民收入的提高和城市居民消费习惯的转 变，信用卡业务在中国得到了快速发展，为各个商业银行带来了 丰厚的客户资源及可观的利润。信用卡在中国市场的竞争也日趋 激烈，但是高度竞争使得各发卡银行对于审核申请信用卡的人的 限制趋于宽松，忽略了风险的管理和控制。 ( 1 ) 本文介绍了数据挖掘技术的发展现状和基本原理，并讨论 了数据挖掘技术在信用卡业务中的应用意义。 ( 2 ) 提出了一个集数据采集，转换和挖掘于一体的数据挖掘系 统，并对其主要功能进行了比较详细的介绍。 ( 3 ) 聚类分析在金融业方面的研究有很大的发掘空间。本文将 聚类分析方法引入到信用卡申请分析中。通过对客户的基本信 息，银行的基本信息等基本层面进行考察，建立了较为全面的综 合评价指标体系，来衡量该客户是否为银行需要的信用卡潜在客 户。实证研究表明该方法能够帮助银行审查潜在客户的申请具有 有效性和实用性。该模型稳健性好，易于理解，效率高，有助于 银行更加客观、一致、快速地对新申请人的信用卡申请做出判断， 更好地推动银行信用卡业务的发展，提高银行风险防范的能力。 ( 4 ) 本文对挖掘数据的采集系统的整体进行了调试，对数据挖 掘的结果进行了分析，并提出了下一步的具体工作。 关键字数据挖掘，聚类算法，信用卡 l a b s t r a c t t h ed a t am i n i n gi sa l s oc a l l e dt h ek 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 ，w h i c hd i s c o v e r sf r o ml a r g eq u a n t i t y o fd a t aa n df i n d a u t h e n t i c n o v e la n de f f e c t i v em o d e lt h a tc a nb ec o m p r e h e n d e db y p e o p l e d a t am i n i n gs o l v et h ei n a d e q u a c y o ft r a d i t i o n a l a n a l y s i s m e t h o d s ，a n di tc a nc o n d u c tl a r g e s c a l ed a t aa n a l y s i sa n dp r o c e s s i n g t h eu s e f u li n f o r m a t i o nf r o ml a r g ea m o u n t so fd a t at oe x t r a c th i d d e n i nt h ed a t ai nm i n i n gd a t ah e l pp e o p l em a k et h er i g h td e c i s i o n s b e c a u s eo ft h er a i s eo fi n c o m ea n dt h ec h a n g eo fc o n s u m e r s h a b i t ，c r e d i tc a r db u s i n e s sd e v e l o p e dr a p i d l yi n r e c e n ty e a r s t h e c r e d i tb u s i n e s sb e c o m e st h ec o r eb u s i n e s sw h i c hc a l lc a u s ep l e n t y o fc u s t o m e ra n dc o n s i d e r a b l ep r o f i tf o rb a n k s w i t ht h ec o m p e t e so f t h ec r e d i tc a r dm a r k e ti nc h i n ab e c o m ef i e r c ei n t e n s e l yd a yb yd a y ， t h ec a r d i s s u i n gb a n k sh a v er e v i e w e dt h er e s t r i c t i o n so fp e o p l ew h o a p p l y f o rc r e d i tc a r d sm o r e l o o s e l y ，a n di g n o r e d t h er i s k m a n a g e m e n ta n dc o n t r 0 1 f i r s t l y ，t h i sp a p e ri n t r o d u c e dd a t am i n i n gt e c h n o l o g ya n dt h e d e v e l o p m e n to fb a s i cp r i n c i p l e s ，a n d d i s c u s s e dt h ed a t am i n i n g t e c h n o l o g yi nt h ec r e d i tb u s in e s so fs i g n i f i c a n c e s e c o n d l y ，t h i sp a p e rp r o p o s e d as e to fd a t ac o l l e c t i o n ， c o n v e r s i o na n dm i n i n gd a t ac o l l e c t e di no n eo ft h em i n i n g s y s t e m s a n di td i s c u s si t sm a i nf u n c t i o ni nd e t a i l t h i r d l y ，t h e r ei sag r e a ts p a c et oe x p l o r ei nc l u s t e ra n a l y s i so f r e s e a r c hi nt h ef i n a n c i a li n d u s t r y t h i sp a p e ri n t r o d u c ec l u s t e r a n a l y s i sm e t h o dt ot h ea n a l y s i so fc r e d i tc a r da p p l i c a t i o n s t h r o u g h b a s i ci n f o r m a t i o nt oc u s t o m e r sa n dt h eb a n k sb a s i ci n f o r m a t i o n s u c hb a s i cd i m e n s i o n so f s t u d y ，i t e s t a b l i s h e dar e l a t i v e l y c o m p r e h e n s i v e a n d i n t e g r a t e d e v a l u a t i o ns y s t e mt om e a s u r e w h e t h e rt h ec u s t o m e r sc r e d i tc a r df o rt h eb a n k st o p o t e n t i a l c u s t o m e r s e m p i r i c a ls t u d i e sh a v es h o w nt h a tt h em e t h o dc a nh e l p t h eb a n k st or e v i e wa p p l i c a t i o n sf o rp o t e n t i a lc u s t o m e r sw i t h e f f e c t i v ea n dp r a c t i c a l t h em o d e li se a s yt ou n d e r s t a n d ，h i g h e f f i c i e n t ，a n di t sr o b u s t n e s si sg o o d t h em o d e lw i l lh e l pb a n k sm o r e o b je c t i v e ，c o n s i s t e n t ，f a s t t om a k e j u d g m e n t s t oc r e d i t c a r d t d d 一一 f o r v o l i c a n t s b e t t e r t et h eb a n kc r e d i tc ardapplications f o rn e wa p p l i c a n t sp e t t e rp r o m o t et i l ed a n kc r ， b u s i n e s sd e v e l o p m e n t ，a n de n h a n c et h ec a p a c i t y o fb a n kr i s k p r e v e n t i o n f i n a l l y ，m i n i n g d a t a a c q u i s i t i o ns y s t e m a r e d e b u g g i n g o v e r a l l y t h er e s u l t so ft e s ta r ea n a l y z e d a n dt h en e x ts t e p o ft h e c o n c r e t ew o r ka r ep r o p o s e d k e yw o r d s ：d a t am i n i n g ，c l u s t e ra n a l y s i s ，c r e d i tc a r d 1 1 1 摘要 目录 a b s t r a c t 目录 第一章绪论 。i 1 1 i v l 1 1 背景介绍1 1 1 1 数据挖掘技术1 1 1 2 聚类算法技术l 1 2 目前研究概况1 1 2 1 国外研究现状l 1 2 2 国内研究现状2 1 3 论文研究的内容和组织3 1 a 本章小结3 第二章数据挖掘 2 1 数据挖掘的定义。4 2 2 数据挖掘的步骤4 2 3 数据挖掘的功能5 2 4 数据挖掘的发展。7 2 5 本章小结7 第三章聚类分析8 3 1 聚类方法概述8 3 1 1 聚类分析在数据挖掘中的应用8 3 1 2 聚类分析算法的概念与基本分类8 3 1 3 距离与相似性的度量1 l 3 2 划分聚类方法1 4 3 2 1k 平均算法1 4 3 2 2p a m 算法1 6 3 2 3 改进的划分聚类算法1 8 3 3 层次聚类方法1 9 3 3 1a g n e s 算法19 3 3 2d i a n a 算法2 0 3 3 3 改进的层次聚类算法2 1 3 a 密度聚类方法2 3 3 5 其他聚类方法2 4 3 5 1s t i n g 算法2 4 3 5 2s o m 算法2 4 i v i 。 一- 3 5 3c o b w e b 算法2 5 3 5 4 模糊聚类算法f c m ? ：2 5 3 6 聚类算法的比较2 5 3 7 本章小结：j 2 6 第四章数据挖掘系统的设计与实现 4 1 系统总体构架j ：2 7 4 2 开发平台设计2 8 4 3 系统结构及功能设计2 9 4 3 1 数据库连接配置程序设计。3 0 4 3 2 数据采集程序设计3l 4 3 3 数据转换程序设计一3 2 4 3 4 聚类分析程序设计3 5 4 4 本章小结3 8 第五章实验结果与分析 3 9 5 1 进行聚类分析3 9 5 2 结果分析4 2 5 3 小结4 3 第六章总结与展望 4 4 6 1 总结。4 4 6 2 展望。4 4 附录 参考文献 致谢5 2 攻读硕士学位期间主要的研究成果。 v 中南大学硕十学位论文第一章绪论 1 1 背景介绍 1 1 1 数据挖掘技术 第一章绪论 近几十年来，伴随着信息技术的进步，人们生产和搜集数据的能力得到大幅 度提高。但是，由于信息过多，真正有用的知识却被隐藏在众多的信息中。在这 被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。要想使信息 发挥其应有的作用，必须从中提有用的“知识，否则大量的数据可能成为垃 圾，甚至成为包袱。数据挖掘( d a t am i n i n g ) 和知识发现( k n o w l e d g ed i s c o v e r i n g ) 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。在银行金融领 域，人们使用它进行客户细分；在零售行业，人们使用它来进行购物篮分析；在 信用卡行业，人们使用它来进行欺诈探测；税务部门使用它来进行偷漏税行为探 测，应用之广泛不胜枚举。另一方面，随着数据库技术的迅速发展以及数据库管 理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要 的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目 前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数 据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。 1 1 2 聚类算法技术 聚类分析是数据挖掘中的一项重要的研究课题，聚类的目标是在没有任何先 验知识的前提下，根据数据的相似性将数据聚合成不同的类( 或簇) ，使得相同类 中的元素尽可能的相似。不同类中的元素差别尽可能的大，因此又称为非监督分 类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 。聚类分析作为数据挖掘中的一个模块，既可以作 为一个单独的工具以发现数据库中数据分布的深层信息，也可以作为其它数据挖 掘算法的一个预处理步骤。 1 2 目前研究概况 1 2 1 国外研究现状 数据挖掘是一门新兴的边缘学科，涉及的学科领域和方法很多，汇集了来自 中南大学硕+ 学位论文第一章绪论 数据库技术、机器学习、模式识别、人工智能以及管理信息系统等各学科的成果。 多学科的相互交融和相互促进，使得数据挖掘这一学科得以蓬勃发展，而且已经 初具规模。目前，数据挖掘技术及知识发现被认为是数据库和人工智能领域中研 究、开发和应用最活跃的分支之一，是计算机科学界的研究热点。在美国国家科 学技术基金会( n s f ) 的数据库研究项目中，数据挖掘被列为最有价值的研究项目。 美国人工智能协会主的k d d 国际研讨会及数据库、人工智能、信息处理、知识 工程等领域的国际学术刊物都开辟了数据挖掘和知识发现专刊。在i n t e r n e t 上还 有许多关于数据挖掘的电子出版物。如自由论坛d me m a i lc i u b ，可以通过电子 邮件相互讨论数据挖掘和知识发现的热点问题。 此外，国外许多公司，如g e 、i b m ，非常重视数据挖掘技术的开发应用， 已经提出了基于数据挖掘的商业智能解决方案，相关软件也开始在销售。如通用 电器公司( g e ) 和法国飞机发动机制造公司( s n e c m a ) ，利用数据挖掘技术研制了 c a s s i o p e e 质量控制系统，用于诊断和预测波音7 3 7 的故障，带来了客观的经 济效益。i b m 公司的a d v a n c e d s c o u t 系统针对n b a 的数据，帮助教练优化战术 组合，一度在数据库界被传为佳话。最近，还有一些数据挖掘产品用来筛选 i n t e m e t 上的新闻，保护用户不受无聊电子邮件的干扰和商业推销，受到极大的 欢迎。 在2 0 世纪7 0 年代，对聚类算法已经有了比较深入的研究，聚类的方法主要 有统计学方法和机器学习的方法，在统计学中，聚类主要研究的是基于距离的聚 类分析。在机器学习中，主要体现在聚类学习的例子或数据对象没有类别标记， 需要聚类算法自动计算。近十几年来，随着数据库知识发现技术的兴起，对聚类 研究掀起了新的热潮，特别是和人工智能领域的结合，成为聚类研究的一个新的 热点。目前存在着大量的聚类算法，算法的选择取决于数据的类型、聚类的目的 和应用。从总体上来看聚类算法可以分为如下几大类：基于划分的方法、基于层 次的方法、基于密度的方法、基于网格的方法、基于模型的方法等。 一 1 2 2 国内研究现状 与国外相比，国内对数据挖掘的研究稍晚，还没有形成整体力量。目前，国 内已有一些科研单位和高等院校开展了知识发现和数据挖掘的基础理论及其应 用研究，这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海 军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用 进行了较深入的研究；北京大学也在丌展对数据立方体代数的研究；华中理工大 学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位 开展了对关联规则开采算法的优化和改造：南京大学、四川联合大学和上海交通 2 中南人学硕十学位论文，+ 第一章绪论 大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。南京大 学的徐洁磐、陈栋等人开发了个原型系统：k n i g h t ，这是一个通用的数据挖掘 工具，可用于处理不同领域的知识发现任务，主要有聚类分析、特征知识发现、 分类规则发现、关联规则发现、函数依赖发现及基于查询的知识发现等。 国内企业运用数据挖掘技术来协助业务活动的应用还处于起步阶段。成功应 用的案例还比较少，这对数据挖掘技术和工具的研究人员以及开发商来说，我国 是一个有巨大潜力的市场。 1 3 论文研究的内容和组织 本文的主要内容是研究作为数据挖掘技术重要组成部分的聚类分析技术。介 绍了数据挖掘的概念，发展以及现状，讨论了数据挖掘技术在信用卡申请中的应 用意义，采用数据挖掘技术中的聚类分析技术对银行关于信用卡申请的数据进行 挖掘。 本文的结构按以下方式进行组织。 。 第1 章介绍了数据挖掘技术和聚类算法的国内外研究现状及发展趋势，同时 提出本文的主要研究内容。 第2 章阐述了数据挖掘的概念、步骤和功能及其发展过程。 第3 章本章对聚类简单概括，然后重点介绍了划分聚类算法、层次聚类算法 和密度聚类算法，最后对其他方法进行了简要介绍。j 第4 章介绍了数据挖掘系统的各个模块的具体实现，包括数据库连接配置程 序设计，数据采集与数据转换程序设计以及聚类分析中的类平均法在程序中的具 体的实现方法。 第5 章 第6 章 1 4 本章，j 本章阐 和意义。最 中南大学硕士学位论文 第二：章数据挖掘 第二章数据挖掘 2 1 数据挖掘的定义 。 数据挖掘( d a t am i n i n g ，d 蛐，就是从大量的、不完全的、有噪声的、模糊 的、随机的数据中，提取隐含在其中的，人们事先不知的，但又是潜在有用的信 息和知识的过程。 数据挖掘是- - f l 来自各种不同领域的研究者共同关注的交叉性学科，受到多 个学科的影响，最主要的学科包括：数据库技术、统计学、人工智能、机器学习、 模式识别、高性能计算、可视化技术、信息科学等。 2 2 数据挖掘的步骤 数据挖掘的全过程描述如图2 1 所示： o o 数据库数据仓待定数据集模式 知识 图2 1 数据挖掘步骤示意图 整个数据挖掘过程是由若干挖掘步骤组成的，主要步骤有： ( 1 ) 数据清洗( d a t ac l e a m i n g ) ，其作用就是清除数据噪声和与挖掘主题明显无 关的数据。 ( 2 ) 数据集成( d a t ai n t e g r a t i o n ) ，其作用就是将来自多数据源中的相关数据组合 到一起。 ( 3 ) 数据转换( d a t at r a n s f o r m a t i o n ) ，其作用就是将数据转换为易于进行数据挖 掘的数据存储形式。 ( 4 ) 数据挖掘( d a t am i n i n g ) ，它是知识挖掘的一个基本步骤，其作用就是利用 智能方法挖掘数据模式或规律知识。 ( 5 ) 模式评估( p a t t e r ne v a l u a t i o n ) ，其作用就是根据一定评估标准从挖掘结果筛 选出有意义的模式知识。 4 中南大学硕士学位论文 第二章数据挖掘 ( 6 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ， 术，向用户展示所挖掘出的相关知识。 2 3 数据挖掘的功能 其作用就是利用可视化和知识表达技 数据挖掘大体上有两种功能，即预测验证功能和描述功能。前者指用数据 库的若干已知属性预测或验证其他未知属性值；后者指在找到描述数据的可理解 模式。图2 2 列出了数据挖掘的几项主要的功能。 图2 2 数据挖掘的功能 1 预测及验证功能 预测是通过对已知数据的分析处理，预测未知的数值或丢失的数据。趋势分 析是分析时态数据的变化趋势，根据以往的行为预测下一时刻可能发生的事件。 趋势分析和预测方法有很多，这里举出几个介绍如下。 ( 1 ) 统计方法 统计方法可以帮助找出与预测值相关的属性，根据相似数据的分析估算属性 值的分布情况，回归分析是一种常用的预测方法，他可以描述属性y 对属性集合 x 的依赖关系，其中】，称为目标属性，x 称为条件属性。利用回归分析就可以 得到一个函数表明目标属性与条件属性之间的依赖关系，既可以描述变量之i 日j 的 关系，也可根据这种关系进行预测。 ( 2 ) 关联规则方法 通过域划分把数值目标属性值转换为离散值，关联规则方法可以预测数值目 标的属性值。 关联规则用对条件属性的测试描述目标属性的性质，利用规则可以预测目标 属性的值。设y 称为目标属性，肖称为条件属性测试，关联规则工y = a 表示 元组t 满足测试x ，则f 得属性y 的值等于口的可能性较高。 ( 3 ) 决策树和归树方法 决策树是一个有根的树结构，每个内部结点都包含对条件属性的测试，元组 中南大学硕士学位论文第二章数据挖掘 经过内部结点的循环测试，最终达到叶节点，把该叶结点的取值作为元组的目标 属性的原测值。 回归树是一个有根的二叉树，每个内部结点包含对条件属性的测试，与决策 树不同的是，回归树的目标属性是数值型，叶结点的属性平均值作为数值目标属 性的预测值，通常用平均方差来估计回归树的精度。 ( 4 ) 序列模式挖掘方法 时态数据的存在使得有必要在知识发现的过程中考虑时间因素。序列模式是 关联规则在时间事件序列上的扩充，目的是从大量事件序列中发现频繁出现的事 件序列。序列模式挖掘在社会经济中可用来衡量事件序列关联性，预测日后的销 售模式。 2 描述功能 ( 1 ) 数据分类 数据分类( c l a s s i f i c a t i o n ) 就是找到数据库中一组对象的相同属性，根据分 类模型将它们分为不同类别的过程。分类是一种监督的学习方法，为构造分类模 型，往往会从示例数据库中选择一些样本数据作为训练集，另一些样本数据作为 测试集。通过分析训练集，构造体现其特征的模型，得到每个类的精确描述，然 后通过测试集的数据将其扩展为一种更好的分类模型。常用的分类方法有决策 树、贝叶斯方法、神经网络、遗传算法等。 ( 2 ) 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类就是将数据对象分组成为若干个类或簇， 在同一族中的对象之间具有较高的相似度，而不同的族中的对象之闻差别很大。 与分类不同的是，聚类要划分的类是未知的。聚类增强了人们对客观现实的认识， 是概念描述和偏差分析的先决条件。 ( 3 ) 数据汇总与归纳 概念层次是数据库中经常存在的一种结构，描述数据之间的从属关系。数据 库中的数据经常包括原始概念层上的详细信息，将一个数据集合归纳成搞概念层 次信息的过程称为数汇总。 ( 4 ) 概括 概括( s u m m a r i z a t i o n ) 的方法寻找数据集合的描述，可采用图标、关联规则 和可视化技术等。 ( 5 ) 构造依赖模式 构造依赖模式( d e p e n d e n c y p a t t e r n ) 的方法构造变量问函数依赖关系或相关 关系的模型。 ( 6 ) 偏差分析 6 中南大学硕士学位论文第二章数据挖掘 偏差分析( d e v i s a t i o nd e t e c t i o n ) 检测数据现状和历史记录或标准之间的差别， 发现结果与期望的偏离、反常实例等。 2 4 数据挖掘的发展 数据挖掘技术的发展是由于计算机及其相关技术的发展为其提供了研究和 应用的技术基础。归纳起来，下面相关技术的发展起到了决定性的作用： 1 数据库、数据仓库和i n t e r a c t 等信息技术的发展。随着数据库技术的不断 发展及数据库系统、数据仓库、i n t e r a c t 的广泛应用，人类积累的数据量正以指 数速度增长。这些庞大的数据中蕴藏着丰富的信息。但是仅仅依靠传统的数据检 索机制和统计分析方法还不能揭示出其中所蕴含的知识。数据挖掘技术正是在这 种强烈需求背景下，由数据库技术推动、演化而来的。数据库技术的不断成熟和 数据仓库的发展为数据挖掘提供了发挥作用的平台。 2 计算机性能的提高和先进的体系结构的发展。计算机存储设备性价比的 迅速提高，使许多企业有能力收集和存储海量数据，而计算机计算能力性价比的 提高，则为数据挖掘的实施扫清了障碍。随着计算机硬件性能的不断提高、数据 挖掘技术的不断改进，数据挖掘应用将会越来越普及。 3 统计学和人工智能等方法在数据分析中的研究和应用。数据挖掘技术继 承了统计学和人工智能解决问题的思想和研究成果。数据挖掘技术是应用需求推 动下多种学科融合的结果，上述的相关技术激发并且支持了数据挖掘技术的研究 和应用。 2 5 本章小结 本章阐述了数据挖掘的概念、步骤和功能及其发展过程。 7 中南大学硕十学位论文 第三章聚类分析 第三章聚类分析 “物以类聚，人以群分，聚类是人类一项基本的认识活动。聚类的用途是 非常广泛的。包括模式识别、数据分析、图像分析，以及市场研究。聚类就是将 数据对象分组成多个类或者簇，划分的原则是在同一个簇中的对象之间具有较高 的相似度，而不同类中的对象比较大。 3 1 聚类方法概述 3 1 1 聚类分析在数据挖掘中的应用 聚类分析在数据挖掘中应用主要在以下几个方面： 1 聚类分析可以作为其他算法的预处理步骤； 可以利用聚类进行数据预处理，将聚类结果用于进一步关联分析，以进一步 获得有用的信息。 2 可以作为一个独立的工具来获得数据的分布情况； 聚类分析是获得数据分布情况的有效方法，通过观察聚类得到的每一个簇的 特点，可以集中对特定的某些簇做进一步分析。 3 聚类分析可以完成孤立点挖掘。 许多数据挖掘算法试图使孤立点影响最小化，或者排除它们。然而孤立点本 身可能是非常有用的。 3 1 2 聚类分析算法的概念与基本分类 1 聚类概念 定义3 - 1 聚类分析的输入可以用一组有序对( x ，s ) 或( y ，d ) 表示，这里x 表 示一组样本，和分别是度量样本间相似度或相异度( 距离) 的标准。聚类系统的 输出是一个分区，若c = 晒，c 2 ，g ，其中c ；( 扛l ，2 ，后) 是x 的子集，如下 所示： quc 2u ug = x cu c j = o ，i j c 中的成员c l ，c 2 ，q 叫做类，每一个类都是通过一些特征描述的，通 常有如下集中的表现方式： 通过类的中心或类的边界点表示一个类 中市大学硕士学位论文、第二章聚类分析 使用聚类树中的节点图形化地表示个类 使用样本属性的逻辑表达式表示类 2 聚类分析的分类 聚类分析是一个活跃的研究领域，已经有大量的、经典的和流行的算法涌现， 例如k - 平均、k - 中心点、p a m 、c l a r a n s 、b i r t h 、c u r e 、o p t i c s 、d b s c a n 、 s t i n g 、c l i q u e 、w a v e c l u s t 等。很多文献从不同的角度对聚类分析方法进行 了分类，概括来讲，有如下几种分类方法。 按照聚类的标准，聚类方法可分为如下两种： ( 1 ) 统计聚类方法 统计聚类基于对象之间的几何距离。统计聚类分析包括系统聚类法、分解法、 加入法、动态聚类法、有序样品聚类法、有重叠聚类和模糊聚类等。这种聚类方 法是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分。 ( 2 ) 概念聚类方法 概念聚类方法基于对象具有的概念进行聚类。这里的距离不再是传统方法中 的几何距离，而是根据概念的描述来确定的。 按照聚类算法所处理的数据类型，聚类方法可分为三种： ( 1 ) 数值型数据聚类方法 数值型数据聚类方法所分析的数据属性为数值数据，因此可对所处理的数据 直接比较大小。目前，大多数的聚类算法都是基于数值型数据的。 ( 2 ) 离散型数据聚类方法 由于数据挖掘的内容经常含有非数值型的离散数据，提出了一些基于此类数 据的聚类算法，如k - m o d e ，r o c k 、c a c t u s 等。 ( 3 ) 混合型数据聚类方法 混合型数据聚类方法是同时处理数值数据和离散数据的聚类方法，这类聚类 方法通常功能非常强大，但性能往往不尽人意。典型算法有：k - 原型算法。 按照聚类的尺度，聚类方法可被分为以下三种： ( 1 ) 基于距离的聚类算法 距离是聚类分析常用的分类统计量。常用的距离定义有欧氏距离和马氏距 离。愈多聚类算法都是用各式各样的距离束衡量数据对象的相似度，如k 平均、 k - 中心点、b i r t h 、c u r e 等算法。算法通常需要给定的聚类数目k 或区分两个 类的最小距离。基于距离的聚类算法标准易于确定、容易理解，对数据维度具有 伸缩性，但只适用于欧几罩得空间和曼哈坦空间，对孤立点敏感。 ( 2 ) 基于密度的聚类算法 从广义上说，基于密度和基于网络的算法都可算作基于密度的算法。此类算 9 中南大学硕十学位论文 第三章聚类分析 法通常需要规定最小密度门限值。算法同样适合欧几里得空间和曼哈坦空间，对 噪声数据不敏感，可以发现不规则的类，但当类或子类的粒度小于密度计算单位 时，会被遗漏。 ( 3 ) 基于互联性的聚类算法 基于互联性( l i n k a g e - b a s e d ) 的聚类算法通常基于图和超图模型。他们通常 将数据集映像为图或超图，满足连接条件的数据数据对象之间的一条边，高度连 通的数据聚为一类。属于此类的方法有：r o c k 、c h a m e l e o n 、a r h p 、s t i r r 。 按照聚类分析算法的主要思路，它可以被归纳为如下几种： ( 1 ) 划分法( p a r t i t i o n n i n gm e t h o d s ) 给定一个包含, 个对象的数据集合，划分方法构建数据的k 个划分，每个划 分表示一个聚类，并且k 刀。而且，这k 个分组满足下列条件：每个组至少包 含一个对象；每个对象必须属于且只属于一个组( 在模糊划分技术中可放宽该要 求1 。对于给定的k ，划分方法首先创建一个初始划分。然后通过反复迭代的方 法改变分组，使得每一次改进之后的分组方案都较前一次好。好的划分的一般准 则是：同一分组中的距离越近越好，而不同分组中的距离越远越好。属于该类的 聚类算法有：k 平均算法、k 一中心点算法、k 模算法、k 原型算法、p a m 、c l a r a 、 c l a r a n s 。 ( 2 ) 层次法( h i e r a r c h i c a lm e t h o d s ) 层次法对给定的数据集合进行层次的分解。根据层次的分解如何形成，层次 法又可以分为凝聚的和分裂的。凝聚的方法，也称为自底向上的方法，一开始就 将每个对象作为单独的一个类，然后相继地合并相近的对象或类，直到所有的类 合并为一个或者达到终止条件。大多数的层次聚集方法属于这一类。分裂的方法， 也称为自顶向下的方法，初始时将所有的对象置于一个类中，在迭代的每一步中， 一个类被分为更小的类，直到最终每个对象在单独的一个类中或者达到终止条 件。层次法的代表算法有：b i r c h 算法和c u r e 算法。 ( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d s ) 基于密度的方法与其它方法的一个根本区别是，它不是基于各种各样的距离 的，而是基于密度的。这样就能克服基于距离的算法只能发现球形聚类的缺点， 可以发现任意形状的聚类。该方法的主要思想是：只要一个区域中对象或数据点 的密度超过某个阈值，就继续聚类。有代表性的基于密度的方法是：d b s c a n 算法、o p t i c s 算法和d e n c l u e 算法等。 ( 4 ) 基于网络的方法( g r i d b a s e dm e t h o d s ) 基于网格的方法首先将数据空问划分为有限个单元的网格结构，所有的处理 都是以单个的单元为对象的。该方法的主要优点是处理速度很快，其处理时间独 l o 中南人学硕士学位论文第三章聚类分析 立于数据对象的数目，只与量化空间中每一维的单元数目有关。代表算法有： s t i n g 、c l u i q u e 、w a v e c l u s t e r 、d b c l a s d 和o p t i g r i d 算法。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d s ) 基于模型的方法为每一个类假定二个模型，寻找数据对给定模型的最佳拟 合。这样一个模型可能是数据点在空间中的密度分布函数或者其他函数。它的潜 在的假定是：目标数据集是由系列的概率分布决定的。一个基于模型的算法可 能通过构建反映数据点空间分布的密度函数来定位聚类。有代表性的基于模型的 方法包括统计学方法和神经网络方法。 其中，前两种算法是根据统计学定义的距离进行度量的，也是最传统的方法， 只有这两种方法被收录到在m a t l a b 、s p s s 、和s a s 中。下面详细的介绍这两种 方法。 3 1 3 距离与相似性的度量 一个聚类过程的质量取决于对度量标准的选择，因此必须仔细选择度量标 准。下面对这些标准作简要介绍。 1 距离函数 按照距离公理，在定义测度时需要满足距离公理的四个条件：自相似性、最 小性、对称性以及三角不等性。常用的距离函数有如下几种： ( 1 ) 明可夫斯基距离( m i n k o w s k i ) 假定，x , y 是相应的特征，挖是特征的维数。j 和y 的明可夫斯基距离度量 的形式如下： d c x ，y ，= 喜il x ，一少，l ， 7lf =j 当，= 1 时，明可夫斯基距离演变为绝对值距离 d ( x ，少) = k 少，l 当r = 2 时，明可夫斯基距离演变为欧式距离 d c x ，少，= 喜i 誓，一少，1 2 2lf = lj ( 2 ) 二次型距离( q u a d r a t i c ) 二次型距离测度的形式如下： d ( x ，j ，) = ( ( z y ) ra ( x y ) ) 其中，a 是非负定矩阵。 中南大学硕士学位论文第三章聚类分析 当a 为单位矩阵时，二次型距离演变为欧氏距离： 当a 为对角矩阵时，二次型距离演变为加权欧氏距离， d ( x , y ) = 融洲 l 2l f i j 当彳为协方差矩阵时，二次型距离演变为马氏距离。 ( 3 ) 余弦距离 余弦距离的度量形式如下： x i y ， d ( x ，y ) = ( 4 ) 二元特征样本的距离度量 前面所阐述的集中距离度量对于包含连续特征的样本是很有效的，但对于包 含一些或全部不连续特征的样本，计算样本问的距离是比较困难的。下面我们介 绍几种二元类型数据的距离度量标准。假定x 和y 分别是n 维特征，工：和y i 分别 表示每维特征，且x ，和y ，的取值为二元类型数值 0 ，1 ) 。则工和y 的距离定义的常 规方法是先求出如下几个参数，然后采用s m c 、j a c c a r d 系数或r a o 系数。 a 是样本z 和y 中满足x ，= y i = l 的二元类型属性的数量。 b 是样本工和y 中满足x ，= 1 ，咒= l 的二元类型属性的数量。 c 是样本x 和y 中满足x ，= o 乃= l 的二元类型属性的数量。 d 是样本x 和y 中满足工，= y t = 0 的二元类型属性的数量。 简单匹配系数( s i m p l em a t e hc o e 伍c i e n t ，s m c ) ( 五y ) = 百瓦a + b 鬲 j a c c a r d 系数 r a o 系数 歌( x ，y ) = 百a 磊 & ( x ，y ) = 百磊a 砑“下，1 _ o t “ 上面我们所给出的距离函数，都是关于两个样本的距离的，为考察聚类的质 量，有时要计算类间的距离。下面介绍几种常见的类问距离计算方法。 1 2 中南大学硕士学位论文、第三章聚类分析 2 类问距离 设有两个类e 和e ，他们分别有加和，1 个元素，它们的中心分别是乞和。 设元素xec 口，y g ，这两个元素问的距离记为d ( 五y ) ，假如类间距离记为 d ( e ，c 6 ) 。 ， ( 1 ) 最短距