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

摘要 本文首先系统的介绍了数据挖掘的基本技术，重点介绍了聚类分析的相关技术。在深入分析 客户信息数据库c i d ( c u s t o m e ri n f o r m a t i o nd a t a b a s e ，c i d ) 数据的基础上，依据专家建议，确 定本文的挖掘目标：对银行客户进行聚类分析，在客户中发现不同的客户群，从而有助于金融政 策的调整和制定。 其次，针对c i d 数据库中数据的特点以及本文的研究目标，本文采用属性选择、数据清理、 属性重构、数据归约和数据变换等方法对c i d 数据库进行处理。数据预处理技术改进了数据的质 量，提高了聚类分析过程的精度和性能。 另外，本文着重对聚类算法进行了研究。由于c i d 数据库同时含有数值型数据和符号型数据， 本文选用k - m e a n s 算法及其变形作为主要方法，采用两种策略对c i d 数据库进行聚类分析：一 种是把符号类型的数据转化为数值型数据，用能处理数值型数据的k m e a n s 算法进行分析；另一 种是直接利用可以处理混合属性的k p r o t o t y p e s 算法来进行聚类分析。然后分别对这两种方法的 聚类结果进行了分析，并对这两者的效率进行了对比。直接k - m e a n s 算法其时间复杂性与对象数 目和聚类数目成比例，当对大型数据库进行分析时，其计算代价是相当高的。针对其在处理大数 据集时的不足，本文给出了基于k - d 树的k m e a n s 聚类分析算法。该方法采用k _ d 树作为主要的 存储结构，将数据信息存放在k - d 树中。实验表明，其运行效率较直接k m e a n s 算法有了明显的 提高，充分显示出采用k d 树作为存储结构的优点。 最后，本文总结了已有的研究工作，并对未来工作进行了展望。 关键词：数据挖掘，聚类分析，k m e a n s 算法k p r o t o t y p e s 算法，k - d 树 a b s t r a c t t h ef u n d a m e n t a l t e c h n i q u e so f d a t am i n i n gw e r ei n t r o d u c e df i r s t l yi nt h i sp a p e r , a n dt h e ne m p h a s i s o nt h er e l a t e dt e c h n o l o g yo fc l u s t e r i n g a n a l y s i s b a s e d o nt h ed e t a i l e da n a l y s i so nt h ec u s t o m e r i n f o r m a t i o nd a t a b a s e ，c i d ，a n dc o m b i n e dw i t ha d v i c ef r o me x p e a s ，t h em i n i n gg o a lw a ss e t u p ：m a k i n g c l u s t e r i n ga n a l y s i so nc u s t o m e ro fb a n k ，d i s c o v e r i n gd i f f e r e n tc u s t o m e rg r o u p s ，w h i c hi sh e l p f u lt ot h e m o d i f y i n ga n de s t a b l i s h i n go f f i n a n c i a lp o l i c y s e c o n d l y , t o w a r dt h ec h a r a c t e r i s t i c so fd a t ai nc i dd a t a b a s ea n do u rr e s e a r c ha i m s ，a t t r i b u t e s e l e c t i o n ，d a t ac l e a n i n g ，a f f r i b u t er e c o n s t r u c t i n g ，d a t ar e d u c t i o na n dd a t ai n v e r s i o ne t cw e r ea p p l i e dt o c i dd a t a b a s e t h ed a t aq u a l i t yw a si m p r o v e db yt h ed a t ap r e - p r o c e s s i n gt e c h n o l o g ya n dt h ep r e c i s i o n a n dp e r f o r m a n c ed u r i n gt h e s t a g eo f c l u s t e r i n ga n a l y s i sw e r ee n h a n c e d a l s o 1 t h i r d l y , t h er e s e a r c hw o r ko fp a p e rf o c u s e so nc l u s t e r i n ga l g o r i t h m ，b e c a u s eo f t h ec h a r a c t e r i s t i c s t h a tc i dd a t a b a s eh a sd a t ao fn u m e r i c a lv a l u et y p ea n ds y m b o lt y p e ，k - m e a n sa n di t sv a r i a n t sw e r e c h o s ea sm a i nm e t h o d ，a n dt w os t r a t e g i e st oc i dd a t a b a s ew e r et a k e n ：t h ef i r s ti sc o n v e r t i n gt h o s ed a t a o fs y m b o lv a l u et y p ei n t on u m e r i c a lv a l u e ，a n dw a sp r o c e s s e db yk - m e a n sw h i c hc a np r o c e s sd a t ao f n u m e r i c a lv a l u et y p e ；t h es e c o n di su t i l i z i n gd i r e c t l yk p r o t o t y p e sw h i c hc a i lp r o c e s sc o m b i n e dd a t a t y p ei n t oc l u s t e r i n ga n a l y s i s a n a l y s i so nd i f f e r e n tc l u s t e r i n gr e s u l ta n dc o m p a r i s o no f t h ee f f i c i e n c yo f t w o a l g o r i t h m sw e r ed o n ea l s o t h e t i m ec o m p l e x i t yo fk - m e a n sw a ss c a l e dt ot h eo b j e c tn u m b e ra n d c l u s t e rn u m b e r w h e na n a l y z i n gl a r g e - s c a l ed a t a b a s e ，t h ec o m p u f i n gc o s tw a sf a i r l yh i g h t o w a r dt h e d r a w b a c k so f p r o c e s s i n gl a r g ed a t a s e t ，t h i sp a p e r p r o v i d e dk - m e a n sc l u s t e r i n ga n a l y s i sa l g o r i t h mb a s e d o nk - dt r e et h i sm e t h o dt a k e sk - dt r e ea sp r i m a r ys t o r es t r u c t u r ea n ds t o r ed a t ai n f o r m a t i o ni n t ok - dt r e e e x p e r i m e n t ss h o wt h e r ei s ab i gi m p r o v e m e n tc o m p a r e dw i t hd i r e c tk m e a n sa l g o r i t h mi nr u n n i n g e f f i c i e n c y , a n dp r o v e dt h ea d v a n t a g eo f t a k i n gk - dt r e e “s t o r e s t r u c t u r e f i n a l l y , t h i sp a p e rp r o v i d e s ad e t a i l e ds u m m a r yt o w a r dt h o s er e s e a r c hw o r kd o n e ，a n dg i v ea p r o s p e c tt ot h en e x ts t e p k e y w o r d s ：d a t am i n i n g t c l u s t e r i n ga n a l y s i s rk m e a n sa l g o r i t h m ，k _ p r o t o t y p e sa l g o r i t h m ，k - dt r e e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得中国农业大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示了谢意。 研究生签名：时间：年月日 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件和磁盘，允许论文被查阅和借阅，可以用影印、缩印或扫描等复制 手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同媒体上发表、传 播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名 时间i年月日 时间：年月r 中国农业大学硕士学位论文第一章引言 1 1 课题背景和意义 第一章引言 随着我国市场经济的发展和加入世贸组织之后，各商业银行间的同业竞争会更加激烈，管 理现代化、决策科学化必将成为银行参与竞争、寻求发展的重要手段，而先进的计算机技术和 网络通讯技术已成为科学化管理和参与竞争的必备工具和先决条件。 作为社会经济核心的金融业，随着当前金融服务的全球化，中国的金融机构越来越多地参与 世界范围内的协作和竞争。加入w t o 后，更多的外资金融机构进入中国市场，在争夺优质客户、 优秀金融人才和扩大新业务市场占有率等方面，与中资金融机构展开激烈竞争，给中资金融机构 的经营、中央银行货币政策和我国金融监管体系带来新的压力，对中国金融行业核心竞争力的整 体提升提出了新的挑战。加强金融行业的信息化建设是应对挑战的关键手段，借助信息管理技术 实现业务和管理的升级，则是金融企业提升其核心竞争力的必然选择。 随着金融行业信息基础设施建设的不断完善，信息资源的开发得到了重视，金融企业已开始 应t f = j 信息技术对资金流、信息流、业务流进行全面的整合，金融行业进入了“数据大集中”时代。 如何使用数据挖掘技术处理海量的用户信息，并及时提供决策支持，成为摆在金融企业面前的新 课题。 1 1 ，1 我国金融业实施客户细分的必要性 按照国际权威罗纳德s t 史威福特先生( m r r o n a l dss w i f t ) 对客户管理”1 的一般定义，所谓 客户管理是指企业通过富有意义的交流沟通，理解并影响客户行为最终实现提高客户获得、客 户保留、客户忠诚和客户创利的目的。 对于我国金融业而言，与客户进行良好的沟通，真正提供以客户为中心的产品和服务是竞争 成败的关键。我国金融业在国内具有其他行业无可比拟的人才和技术优势，但在很大程度t 这些 优势并没有很好地转化为服务优势，创造出应有的效益。金融服务观念和服务管理薄弱，无论是 在外延上还是在内涵上都与优质的服务管理存在很大差距这也是造成我国金融业总体经营效益 不佳的根源之一。 客户细分是现代营销理念的产物，是第一二次世界大战后西方发达国家市场营销理论刊战略的 新发展。它主要是指企业在明确的战略、业务模式和专注市场中根据客户的价值、需求和偏好等 综合因素对丁客户进行分类，对不同的客户群提供具有针对性的产品、服务和营销模式。经过若 干年的发展，客户细分的理论和方法不断完善，而且被广泛地应用于营销实践。客户细分理论的 提出乖l 应硝是具有一定的客观基础的，它是商品经济发展和市场竞争日益激烈的产物。其理【 依 据士要有两个： 第一，客户需求的异质性。也就是院，并不是所有的客户需求都是相同的，只要存在两个以 l 的客户，需求就会不同。由丁i 客户需求、欲望及购买行为是多元的，所以客户在购买产品年使 川服务上的需求呈现较大的著异。客户需求的异质性是进行客户细分的内在依据。 中国农业大学硕士学位论文第一章引言 第二，企业资源的有限性和为了进行有效的市场竞争。现代企业由于受到i h 身实力的限制， 不可能捉供满足所有顾客需求的产品和服务。任何一个企业即便是处于市场领先地位，也不可能 在整个营销过程中占绝对优势。为了进行有效的竞争，企业必须进行客户细分，选择最有利可图 的目标客户群体，集中企业资源制定有效的竞争策略来增强自己的竞争优势。所以企业资源的有 限性和为了进行有效的市场竞争是进行客户细分的外在要求。 对于商业银行也是同样的道理，商业银行有着广大的客户群体，这些客户千差万别。对于不 同的客户，他们的需求又是千变万化的。银行不可能满足所有客户的需求，这不仅是由银行自身 物质条件所限制，而且从经济效益方面来看也是不可取的。故而，银行应该分辨出它能有效为之 服务的最有价值的客户，为他们提供更为个性化的服务，而不是四面出击兼顾每一个银行客户。 对商业银行来讲，在经营管理中进行客户细分的必要性主要表现在以下几个方面： 1 客户细分是实施客户经理制的必然要求。 当前，我国许多商业银行为了在激烈的市场竞争中取胜，纷纷实施客户经理制来加强其市场 营销的力度。实施客户经理制，首先就会要求对客户和市场进行细分，根据细分结果来决定客户 经理的配置，为重点客户和主要的市场配各重要的客户经理，以增强市场营销战略的有效性。 2 客户细分是优化商业银行资源配置的必然要求。 商业银行的各种资源，特别是财务资源是极其有限的，如何台理利用有限的资源并将有限的 资源投入到最有利可图的顾客身上，使每一项资源都应用在它最能显出价值的地方，用最少的投 入获取最大的收益，这些都需要银行在对客户进行细分的基础上才能做出有效的决策。 3 ，客户细分是促进商业银行进行内部改革的必然要求。 近年来我国商业银行都在按照现代商业银行的要求进行内部改革，精简分支机构和营业网 点，完善内部组织结构。但一个银行究竟是要设置哪些分支机构和营业网点? 内部要设置哪些组 织机构? 哪些地区应加强网点的设置? 哪些地区应逐渐退出? 这些都需要通过对客户市场进行 细分才能做出正确的抉择，要根据客户市场的分布来确定分支机构、营业网点和内部组织机构的 设置。 4 客户细分是商业银行了解竞争对手取得主动性的必然要求。 加入w t o 以后，外资银行大规模进入，我国银行业的竞争将日趋激烈。一个银行在确立自 己在市场竞争地位的过程中，仅仅了解客户的需求和自身条件往往是不够的，特别是在市场竞争 日茄激烈的今天，充分注重和研究竞争对手变得十分重要和关键。了解竞争对手的目的在于比较 自己相对丁i 竞争对手的优势和劣势，从而确立自己的目标市场和营销战略。这些都离不开对客户 进行细分。 5 客户细分是提高经营效益，实现银行价值最大化的必然要求。 财务管理的目标是使银行价值最大化，价值最火化是对银行价值创造的综合要求，它需要把 握很多冈素的影响，包括现在及可预期朱来的资本收益水平，是银行经营管理的练合反映。囡此 银行要实现价值最大化的目标，必然要求对客户进行细分，根据不周的目标客户选择合适的营销 策略创造最大的效益。 6客户细分是确立商业银行莘异化优势的根本保证。 过生商业银行所沿川的是一种人众化营销，商业银行面对所有的客户，提供相同的产鼎和服 务。随着当今市场格局的细化，专业群体逐步形成j 。告媒体和分销渠道的多元化使“所有人都 中国农业大学硕士学位论文 第一章引言 适用一种规格”的营销越来越困难。大众化营销已不适应当今市场的需要，转向细分营销是一种 必然。由于客户的欲望、自身的经济实力、所处的地理位置、对产品的使用态度和要求服务的习 惯各不相同客户细分则成为增加商业银行目标精确性的一种努力。在确定了客户细分后，商业 银行就必须进行分析从而确定为不同的细分客户群提供不同的服务并确立差异化优势。 1 1 2 我国金融业实施客户细分的可能性 最需要和可能实施客户管理的行业有两个基本条件l ： 第一，该行业有较为成熟的联机事务处理系统，它为数据仓库的建立提供客观条件； 第二，该行业面临市场竞争的压力，它为实施客户管理提供外在的动力。 我国金融业具有其他行业无可比拟的人才和技术优势，是传统的信息密集型行业，具有大型 数据库的坚实基础，已经积累了大量的数据。加上国内多年来对金融业的保护将在几年内随着中 国“入世”而被逐渐取消，我国金融业将面临来自国外商业银行竞争的巨大压力，客户资源的宝 贵将越来越多地被国内金融业所认识，如何在激烈的竞争中留住客户，保持原有的客户资源优势 并充分利用客户资源，将成为国内各商业银行首先要考虑的问题。因此，自身的条件和所面临的 外部环境决定了我国金融业必须要实施客户管理，并可能由此引发由传统银行模式向基于i n t e m e t 和信息技术的新型银行模式转变的革命。 综上所述，面对这一挑战，必须利用先进的计算机技术来解决银行客户管理中的问题。数据 挖掘从一开始就是面向应用的。“数据挖握”就是从大量的、不完全的、模糊的、随机的实际应 用数据中，提取隐含在其中的、人们事先不知道的、但又是有用信息的过程。根据决策目标，分 析海量数据、确立分析方法、构建数学模型、定制应用系统、提供决策支持正是数据挖掘的原则 和目标。这一新兴的数据管理技术，必将成为各行业数据管理的新热点，把行业信息化推向又一 个新高峰。 1 2 国内外研究和应用现状 1 2 1 数据挖掘技术的国内外研究现状 随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨论会更 名为国际会议，在加拿大蒙特利尔市召开了第一届k d d 国际学术会议，以后每年召开一次。近 年来，k d d 在研究和应用方面发展迅速，尤其是在商业和银行领域的应用比研究的发展速度还 要快。此外，数据库、人i ：智能、信息处理、知识l j 程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。不仅如此，在i n t e m e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威，在b t t p ：w w w , k d n u g g e t s c o r n s u b s c r i b e h t m l 上还可以f 载各种各样 的数据挖掘l ：具软件幂l 典型的样本数据仓库，供测试和评价。在网上，还有一些自由论坛，如 d me m a i lc l u b 人们通过电子邮件相互讨论d m 的热点问题。 i ；i 前，国外数据挖掘的发展趋势及其研究方向主要有pj 【7 j ： 1 应州的探索。 期的数据挖掘麻_ | _ j 土要集中在帮助企业提升竞争能力，随着数据挖掘的 目豁普及数据挖掘也在探索其他应_ 【 f j 领域，如生物医学，金融分析等，国外很多计算机公 中国农业大学硕士学位论文第一章引言 司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心进行这方面的工作， l t l ，j - ，一些公司的相关软件也开始在国内销售，如p l a t i n u m 、b o 以及i b m 。 2 数据挖掘语言的标准化。标准的数据挖掘语言或其他方面的标准化工作将有助于数据挖 掘的系统化开发，改进多个挖掘系统和功能间的互操作。 3 复杂数据类型挖掘的新方法。虽然在地理空间挖掘、多媒体挖掘、时序挖掘、序列挖掘 以及文本挖掘方面取得一些进展，但它们与实际应用需要仍存在很大的距离。 4 w e b 挖掘。万维网目前是一个巨大的、分布广泛的、全球性的信息服务中心，包含丰富 和动态的超链接信息，以及w e b 页面的访问和使用信息，为数据挖掘提供了丰富的资源。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科学基金首 次支持该领域的研究项目。国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司， 如清华大学、中科院计算技术研究所，复旦大学等。所涉及的研究领域很多，一般集中于学习算 法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研究。目前进行的大多数研究项目 是由政府资助进行的，如国家自然科学基金、8 6 3 计划、“九五”计划等。其中，中国科技大学、 华中科技大学等高校开展了对关联规则开采算法的优化和改造q 口7 j ；上海交通大学对分类方法和 决策支持系统进行了较深入的研究口8 i ：复旦大学研究了综合的数据挖掘解决方案”i 。同时，一些 数据挖掘的爱好者也成立一些论坛，如h t t p ：w w w d m g r o u p o r g c n 。此外。国内能够提供数据挖 掘的软件技术供应商也日渐增多。 1 2 2 数据挖掘技术在金融行业的应用现状 早在2 0 世纪9 0 年代初，蘸方发达国家商业银行就已开始基于金融电子化的客户管理方面的 研究，至今也已有约l o 年的历史。如英国巴克莱银行、汇丰银行、美国花旗银行等大银行都十 分重视对客户群的细分，并都有一套划分客户的办法。区分是否是重要客户，主要标准就是看给 银行带来利润的大小，同时要注意潜在的重点客户，即能给银行带来潜在利润的客户。国际银行 有一个公认的“二八”定律，一般地说，银行8 0 的利润来自2 0 的重点客户，所以银行必须集 中犬部分资源，为这2 0 的客户提供服务。 而我国银行虽然经过数十年改革发展进步显著，但银行客户管理水平仍然停留在表面和初级 状态。具体表现在没有真正建立以市场为导向、以客户为中心的业务流程体系，细分客户能力弱， 对客户缺乏针对性的分类指导，对重点客户、优良客户和一般客户遵循相同的业务操作流程，往 往产生劣质客户驱逐优良的现象。目前国内大部分银行虽有客户管理所需的数据库，也积累了一 些客户信息，但是缺乏有效的数据挖掘系统进行信息分析，各种数据也无法有效结合，基本无法 为银行决策层提供有效帮助，更无法从中了解客户的需求，为客户提供有针对性的服务。现在， 国内商业银行已经意识到这个问题，如中国农业银行正在开发客户管理系统，中国1 ：商银行也计 划在“十五”期问启动客户管理建设，借助客户管理来提升自身的核心竞争力。 目前在核心客户争夺战中，中资银行急需做两件事：第一，提升消费者数据库和管理信息系 统，以追踪不同顾客群的收益性，鉴别山最好的顾客。第二，必须迅速分割顾客基础，对那些最 铂吸引力的群体提供更加有特色的高质量产品和服务。 1 3 本文主要工作和纲要 本课题是在银行客户基本信息数据库的基础上，剥用数据挖掘中的聚类技术，对银行客户进 行聚类，在客户中发现不同的客户群，并将聚类结果递交给管理和决策人员以辅助决策。 管理和决策人员就可以在聚类结果的基础上，对不同的客户实施差别化、个性化的营销和服 务策略。如可以根据个人信用状况、收入情况、财产等将客户细分为黄金客户、重点客户、优质 客户、一般客户、限制客户、淘汰客户。在此基础上，实行不同的贷款审批和计划管理政策。如 对黄金客户贷款计划随报随批；对重点客户的贷款计划事先报告、优先安排；对优质客户贷款计 划只有通过存量结构调整，用清降计划进行安排；对调整、限制、淘汰类客户信用总量只准下降 不准增加等。 论文按照如下方式组织：第二章介绍了数据挖掘相关的概念和技术，重点介绍聚类分析相关 技术。第三章介绍了本文所使用的数据库，客户信息数据库c i d ，对其数据内容进行分析，确定 分析目标，并使用一系列数据预处理技术，将其整理成为适合聚类分析的数据存储形式。第四章 首先根据c i d 数据库的特点，利用k m e a n s 算法和k p r o t o t y p e s 算法分别对c i d 数据库进行聚 类分析，得出并分析聚类结果，然后对这两个算法在效率上进行对比。根据k m e a n s 算法在处理 大数据集时代价高的弱点，本文在k m e a n s 算法的基础上，提出基于k _ d 树的k m e a n s 聚类方法， 将其应用于c i d 数据库分析，同样得出聚类结果并进行了分析。经过实验，与直接k m e a n s 算 法相比，该算法大大的提高了聚类分析的效率。最后第五章归纳本文所做的工作并展望本课题所 涉及领域的未来工作。 中国农业大学硕 学位论文第二章数据挖掘技术概述 第二章数据挖掘技术概述 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，成千上万的数据库被用 于商业管理、政府办公、科学研究和工程开发等。随着数据的剧增，导致了“数据爆炸但知识贫 乏”的现象。人们越来越清晰的认识到：不能被数据的汪洋大海所淹没，必须采用更有效的方法 和工具使大量的数据变成为信息资源，并从中及时发现有用的知识，利用知识为企业自身的决策 和战略发展服务。在此背景下，数据挖掘( d a t a m i n i n g ) 技术应运而生，并在其发展过程中越来 越显示出强大的生命力。 2 1 数据挖掘技术简介 2 ，1 1 数据挖掘的概念 数据挖掘是指从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的高级处理 过程【”。它是数据库研究中的一个很有应用价值的新领域，融合了数据库、人工智能、机器学习、 统计学等多个领域的理论和技术。 还有一些术语，具有和数据挖掘类似但稍有不同的含义，如知识获取( k n o w l e d g ee x t r a c t i o n ) 、 模式分析( p a t t e m a n a l y s i s ) 、数据考古( d a t a a r c h a e o l o g y ) 、数据库中的知识发现k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 等。数据库中的知识发现是一个多步骤的处理过程p 】l “，一般分为： 1 ，问题定义：了解相关领域的有关情况，熟悉背景知识，弄清用户要求。 2 数据提取：根据要求从数据库中提取相关的数据。 3 数据预处理：主要对前一阶段产生的数据进行再加工，检查数据的完整性及数据的一致 性，对其中的噪声数据进行处理，对缺失的数据进行填补。 4 数据挖掘：运用选定的知识发现算法，从数据中提取出用户所需要的知识，这些知识可 以用一种特定的或常用的方式表示。 5 知识评估：根据某种兴趣度度量，如支持度，置信度，主观兴趣度，识别表示知识的真 止有趣的模式。 由此可见，数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一步。因此，人们 往往不加区别地使_ 【 jk d d 和数据挖掘。一般在研究领域被称作k d d ，在i ：程和应用领域则称之 为数据挖掘。本文采用数据挖掘的术语，其含义与k d d 相同，即它是一个包含多个步骤的处理 过程。 2 1 2 数据挖掘的发展历程 数据挖搠技术是人们长期对数据库技术进行研究和开发的结果。起初笄种商业数据是存储在 计算机的数据库中的，然后发展到可对数据库进行商向和访问，进而发展到对数据库的即时遍历， 数据挖捌使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行商嘟和遍历，并且 - 6 - 中国农业大学硕上学位论文第二章数据挖掘技术概述 能够找出过去数据之间的潜在联系。商业数据库现在正在以空前的速度增匠，并且与九十年代较 为成熟的数据仓库同样泛地应用于各种商业领域。从商业数据到商业信息的进化过程中，每一 步前进都是建立在上一步的基础上的。表2 1 给出了数据进化的四个阶段”j ，从中可以看到，第 四步进化是革命性的，因为从用户的角度来看，这一阶段的数据库技术已经可以快速地回答商业 上的很多问题了。 表2 - 1 数据挖掘的进化历程 进化阶段商业问题支持技术产品主要厂家产品特点 数据搜集“过去五年中我的总收计算机、磁带和磁i b m ， c d c 提供历史性的、静 ( 6 0 年代)入是多少? ”盘态的数据信息 数据访问在北京的分部去年三月o d b c 关系数据库o r a c l e 、s y b a s e 、在记录级提供历史 ( 8 0 年代)的销售额是多少? ”( r d b m s ) ，结构 i n f o r m i x 、i b m性的、动态数据信 化查询语言( s q l ) ， 息 数据仓库；“在北京的分部去年三月联帆分析处理p i l o t 、c o m s h a r c 、在各种层次上提供 决策支持的销售额是多少? 上海( o l a p ) 、多维数a r b o r 、c o g n o s 、回溯的、动态的数 ( 9 0 年代)据此可得出什么结论? ”据库、数据仓库 m i c r o s t r a t e g y 、b o 据信息 数据挖掘“下个月北京的销售会怎高级算法、多处理 p i l o t 、l o c k h e e d 、 发现隐藏在数据中 ( 正在流行)么样? 为什么? ”器计算机、海量数m m 、 s g i 、的知识，提供预测 据库 m i c r o s o 住 性的信息 2 1 3 数据挖掘的功能 数据挖掘的功能即指定数据挖掘任务中要找的模式类型pj 。数据挖掘所能发现的知识类型有 如下几种i j l l 6 1 ： 1 概念描述。概念描述是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念 描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类别 对象之间的区别。概念描述一般有两种方法：基于数据立方体o l a p 方法和面向属性归 纳的方法。概念描述允许数据集在多个抽象层概化，便于用户考察数据的一般行为。如 销售经理可能不想考察每个顾客的事务，而将顾客按地区分组，观察每组顾客的购买频 率和顾客的收入。 2 关联分析。数据间的关联性是数据库中存在的一类重要的可被发现的知识。关联规则挖 掘大量数据中项集之间有趣的关联或相互联系口】。从大量商务事务记录中发现有趣的关 联关系，可以帮助制定许多商务决策如分类设计、交叉购物、贱卖分析等。常见的关 联规则分析算法有：a 1 s 、s e t m 、a p r i o r i 、d h p 等，其中a p r i o r i 和d h p 是比较成功 的算法。 3 聚类。将物理或抽象对蒙的集合分组成为由类似的对象组成的多个类的过程称为聚类【3 1 。 在商务上，聚类能帮助市场分析人员从客户基本信息库中发现不同的客户群，并且川购 买模式米刻画不同的客户群的特祉。在生物学上，聚类能于推导植物和动物的分类， 对基冈进行分类，获得对种群中周有结构的认识。土要的聚类算法有k 中心点、c u r e 、 中国农业大学硕士学位论文 第二章数据挖掘技术概述 d b s c a n 、b i r c h 、s t i n g 等。 4 分类。分类是通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析模 型或挖掘分类规则，然后用这个分类规则对其他数据库中的记录进行分类。分类在信誉 证实、医疗诊断等方面应用广泛。主要的分类方法有判定树归纳、贝叶斯分类、神经网 络、基于案例的推理、遗传算法等。 5 预测趋势和行为。预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有 的属性值或值区间。一个典型的例子是市场预测问题，通过对过去有关促销的数据分析 来寻找未来投资中回报最大的用户，其他可预测的问题包括预报破产以及认定对指定事 件最可能做出反应的群体。主要的预测方法有线性回归、多元回归、广义线性模型等。 6 偏差检测。偏差检测即寻找观测结果与参照值之间有意义的差别。它被广泛应用于欺诈 监测、医疗等方面。偏差检测的方法包括统计学方法、基于距离的方法、基于偏移的方 法。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到宏观，以满 足不同用户、不同层次决策的需要。例如从一家超市的数据仓库中，可以发现的一条典型关联 规则可能是“买面包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客j l 乎都用信用 卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 2 1 4 数据挖掘常用方法 数据挖掘常用的方法包括【7 j ： 1 统计分析。统计分析方法是利用统计学、概率论的知识对关系中各属性进行统计分析， 找到它们之间存在的关系。 2 决策树。决策树方法是利用训练集生成一个测试函数，根据不同取值建立树的分支，在 每个分支子集中重复建立下层结点和分支，这样便形成一棵决策树，然后对决策树进行剪枝处理， 把决策树转化为规则，利用这些规则可以对新事例进行分类。 3 人1 ：神经网络。人工神经网络是在结构上模仿人的神经网络，通过训练来学习并具有联 想记忆功能的非线性模型。在数据挖掘中可用来进行分类、聚类，特征挖掘等操作。 4 遗传算法。遗传算法是一种优化技术，它利用生物进化的一系列概念进行问题的搜索 最终达到优化的目的，即试图通过组合或“繁殖”现存的摄好解法来产生更好的解法。在数据挖 掘中，往往把数据挖掘任务表达为一种搜索问题，利用遗传算法强大的搜索能力找到最终解。 5 ，r o u g h 集。r o u g h 集是一种处理含糊和不确定问题的新型数学：1 二具。利用r o u g h 集可以 处理的问题包括数据简化、数据相关性的发现、数据意义的评估、由数据产生决策算法、数据中 范式的发现及因果关系的发现等。 6 模糊逻辑。模糊逻辑融合了模糊集合乖l _ 二值逻辑概念，一个公式的真值，可取o ，i 区间 中任何值。在数据挖掘中，被用来进行证据合成、置信度计算等。 7 可视化技术。可视化技术采川直观的图形方式将信息模式、数据的关联或趋势呈现给决 策者，次策者可通过可视化技术交互分析数据关系。 另外本文主要州到数据挖掘中的聚类分析，f 面着重介绍与聚类分析有关的知识。 中国农业大学硕士学位论文第二章数据挖掘技术概述 2 2 聚类分析简介 何谓聚类就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程，其原则 是将对象根据最大的组内相似性和最小的组间相似性进行聚类或分组。 2 + 2 1 数据挖掘对聚类分析的典型要求 数据挖掘领域中的聚类分析，研究工作主要集中在为大型数据库的聚类分析寻找适当的方法 上。活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性， 高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。 聚类分析是一个具有很强挑战性的领域，它的一些潜在的应用对分析算法提出了特别的要 求，f 面列出一些典型的要求p j ： ( 1 ) 可伸缩性：这里的可伸缩性是指算法要能够处理大数据量的数据库对象，比如处理上 百万条记录的数据库。这就要求算法的时间复杂度不能太高，最好当然是多项式时间的算法。值 得注意的是，当算法不能处理大数据量时，用抽样的方法来弥补也不是一个好主意，因为这通常 导致歪曲的结果。 ( 2 ) 处理不同字段类型的能力：也即算法不仅要能处理数值型的字段，还要有处理其他类 型字段的能力，例如：布尔型、枚举型、序数型、以及混合型等。 ( 3 ) 发现具有任意形状的聚类的能力：很多聚类分析算法采用基于欧几里德距离的相似性 度量方法，这一类算法发现的聚类通常是一些球状的、大小和密度相近的类；但是，现实数据库 中的聚类可以是任意的形状，甚至是具有分形维度的形状，故要求算法有发现任意形状的聚类的 能力。 ( 4 ) 输入参数对领域知识的弱依赖性：很多聚类算法都要求用户输入一些参数，例如需要 发现的聚类数、结果的支持度、置信度等，聚类分析的结果通常都对这些参数很敏感，但另一方 面，对于高维数据，这些参数又是相当难以确定的。这样就加重了用户使用这个工具的负担，使 得分析的结果很难控制。一个好的聚类算法应该针对这个问题，给出一个好的解决方法。 ( 5 ) 能够处理异常数据：现实数据库中常常包含有异常数据，或者数据不完整，缺乏某些 字段的值，甚至是包含错误数据的现象，有一些聚类算法可能会对这些数据很敏感，从而导致错 误的分析结果。 ( 6 ) 结果对输入记录顺序的无关性：有些分析算法对记录的输入顺序是敏感的，也即，对同 一个数据集，将它以不同的顺序输入到分析算法，得到的结果会不同。 ( 7 ) 处理高维数据的能力：一个数据库或者数据仓库都有很多的字段或者既维，一些分析 算法在处理维数比较少的数据集时表现不错，例如两三个维的数据；人的理解能力也可以对两二 维数据的聚类分析结果的质量作出较好的判别但对丁高维数据就没有那么直观了。所以对丁高 维数据的聚类分析是很具有挑战性的，特别是考虑到在高维空间中，数据的分布是极其稀疏的， 而i 形状也可能是极其不规则的。 ( 8 ) 增加限制条件后的聚类分析能力：现实的应喇中总会山现各种其他限制，我们希望聚 类算法可以在考虑这些限制的情况r ，仍有较好的表现。 中国农业大学硕士学位论史 第二章数据挖掘技术概述 ( 9 ) 结果的可解释性和可用性：聚类的结果最终都是要面向用户的，所以结果应该是容易 解释和理解的，并且是可应用的。这就要求聚类算法必须与定的语义环境、语义解释相关联。 领域知识是如何影响聚类分析算法的设计是很重要的一个研究方面。 2 2 2 聚类分析中的数据类型 许多基于内存的聚类算法选择如下两种有代表性的数据结构1 3 】：数据矩阵和相异度矩阵。假 设要聚类的数据集合包含n 个数据对象，这些数据对象可能表示人、房子、文档、国家等。 ( 1 ) 数据矩阵( d a t am a t r i x ，或称为对象与变量结构) ：它用p 个变量( 也称为度量或属性) 来表现n 个对象，例如用年龄、身高、体重、性别、种族等属性来表现对象“人”。这种数据结 构是关系表的形式，或者看成n p ( n 个对象p 个变量) 的矩阵。 q i q ，d 1 ， q 【 l ( 2 ) 相异度矩阵( d i s s i m i l a r i t ym a t r i x ；：或称为对象一对象结构) ：存储n 个对象两两之间的近 似性，表现形式是一个n x l l 维的矩阵。 0 d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 ； ；i0 d ( n ，1 ) d ( n ，2 ) 0 在这里d o , j ) 是对象i 和对象j 之间相异性的量化表示，通常它是一个非负的数值，当对象i 和j 越相似或相近，其值越接近0 ；两个对象越不同，其值越火。既然d ( i , j ) = d o ，i ) ，而且d ( i ，i ) = o ， 我们可以得到形如上面的矩阵。 数据矩阵通常被称为二模( t w o m o d e ) 矩阵，而相异度矩阵被称为单模( o n e m o d e ) 矩阵。 这是因为前者的行和列代表不同的实体，而后者的行和列代表相同的实体。许多聚类算法以相异 度矩阵为基础。如果数据用数据矩阵的形式表现的在使用该类算法之前要将其转化为相异度矩 阵。 2 23 聚类分析中的相似性测度 聚类就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程，其原则是将 对象根据最人的组内相似性平【l 最小的组间相似性进行聚类或分组。冈此，相似性测量这一标准定 义的好坏将直接影响聚类算法优越性。 在数据挖捕中聚类分析的对象是实例，每个实例由不同的属性构成，这些属性主要分为数值 一1 0 中国农业大学硕士学位论文第二章数据挖掘技术概述 属性和符号属性，并且，要处理的往往是非常大量而复杂的数据集。闪此，传统的聚类方法必须 尽量满足如r 要求： ( 1 ) 能同时处理数值属性和符号属性。 ( 2 ) 面对数量繁多且仍在迅猛增长的数据集，算法要满足效率及增量性方面的要求。 聚类的解决方法有两大类：空间分割方法和层次聚类方法。空间分割方法是将整个数据对象 空间分解为一些小的子空间，每个子空间对应一个确定的类，可以多个子空间同属于一个类；层 次聚类方法则是将较小的数据对象子集合依据相似程度进行合并，这些小的数据对象子集合逐渐 合并成较大的数据对象子集合，从而构成一个类的层次。 聚类算法大致可以分为划分算法、层次算法、基于密度的算法、基于网格的算法和基于模型 的算法p j 。一般来说，它们所基于的相似性测量方法有三种，均用于数值属性的相似性测量、符 号属性相似性测量和同时用于数值属性和符号属性的混合性相似测量。 1 数值属性的相似性测量方法 数值属性的相似性测量方法大多直接或间接依赖于对象间的距离。常见的距离度量方法有欧 几里得距离( 又称为欧氏距离) 、曼哈坦距离和明考斯基距离。其中最常用的距离度量方法是欧 几里得距离，基于欧氏距离的聚类算法有分割算法中的k m e s 算法，