（农业电气化与自动化专业论文）数据挖掘及在绿地生态评价中的应用研究.pdf

摘要 数据挖掘及在绿地生态评价中的应用研究 摘要 信息社会中数据的爆炸性增长，决策者迫切需要将海量数据转换 成有价值的信息和知识。数据挖掘的出现为这一需要提供了有力的技 术支持。聚类分析是数据挖掘所采用的关键技术之一，它属于机器学 习中的无指导学习范畴，用于发现隐含于数据中的分类( 称为簇) ，使 得簇内对象尽可能相似而簇间对象尽可能相异。聚类分析在诸多领域 得到了广泛的研究和运用。 本文首先认真研究数据挖掘技术并且分析了基于聚类的数据挖 掘的基本原理，然后提出一个基于共享最近邻的聚类算法。该算法首 先找出每个数据对象的k 个( 由参数确定) 最近邻，然后根据共享最近 邻计算两两对象之间的相似度，并对每个数据对象计算其密度。于是 通过去除噪音数据，关联非噪音数据点与核心或代表点来构造簇。 其次，研究了生态适宜度评价的指标体系。适宜度是一定土地单 元的某种特殊利用方式与其生态环境协调关系的一种量度，适宜度评 价是生态规划的核，b 。但在过去园林绿地适宜度评价中，仅从土地单 元的立地条件出发评价一定土地单元是否适宜于建设园林绿地。本研 究依据景观生态学原理和方法，通过绿地景观类型与景观环境、景观 功能的关系研究，探讨景观适宜性的内涵及理论体系；筛选具稳定性、 主导性、可操作性的景观适宜度指标，构建合理的景观适宜度评价指 标体系；并基于园林绿地g i s ，分别从绿地的环境适应性、环境协调 性、生态功能、美学功能及绿地的景观适宜度上对武钢厂区园林绿地 适宜度进行评价。 最后，将基于共享最近邻的聚类算法用于园林绿地的生态适宜性 评价中。 关键词：数据挖掘聚类分析相似度共享最近邻适宜度评价 a b s t r a c t d a 丁am i n i n gt e c h n o l o g ya n dl t sa p p l i c a t l o n i ne c o l o g l c a le v a l u a t i o no fg r e e n l a n d l a n d s c a p e a b s t r a c t t h ee x p l o s i v eg r o w t ho fd a t ai ni n f o r m a t i o ns o c i e t ya n dt h ei n c r e a s i n g l ys e v e r e p r o b l e m so f a b u n d a n td a t a & s c a r c ek n o w l e d g e p u i lt h ed e m a n d so f p o w e r f u ld a t a a n a l y s i st o o l s d e c i s i o nm a k e r sn e e dt oc o n v e r tl a r g ev o l u m eo f d a t ai n t ov a l u a b l e i n f o r m a t i o na n dk n o w l e d g e t h ee m e r g e n c eo f d a t am i n i n gp r o v i d e ss t r o n gt e c h n i c a l s u p p o r tf o rt h eu r g e n tn e e d c l u s t e ra n a l y s i si s o n eo ft h ek e yt e c h n o l o g i e sd a t a m i n i n ge m p l o y s i tb e l o n g s t ou n s u p e r v i s e dl e a r n i n gi nm a c h i n e l e a r n i n g ，a n d i su s e d t od i s c o v e rg r o u p s ( c l u s t e r s ) i nt h eu n d e r l y i n gd a t as ot h a tt h ei n t r o c l u s t e rs i m i l a r i t y i sm a x i m i z e da n dt h ei n t e r - c l u s t e rs i m i l a r i t yi sm i n i m i z e d c l u s t e ra n a l y s i sh a sl o n g b e e ns t u d i e da n du s e di naw i d e v a r i e t yo f f i e l d s f i r s t l y , d a t am i n i n gt e c h n o l o g ya n da n a l y z e sp r i n c i p l e sa n dg e n e r a lm e t h o d so f c l u s t e r i n g - b a s e dd a t am i n i n gi ss t u d i e d t h e nan e wc l u s t e r i n ga l g o r i t h mi sp r e s e n t e d ， i , e t h es h a r e dn e a r e s tn e i g h b o rb a s e dc l u s t e r i n ga l g o r i t h m ，s n n ca l g o r i t h mf o r s h o r t t h i sa p p r o a c hf i r s t l yf i n dkn e a r e s tn e i g h b o r sf o re v e r yp o i n t ，t h e nd e f i n e sa n e w s i m i l a r i t ym e a s u r ew h i c h i sb a s e do nt h en u m b e ro fn e a r e s tn e i g h b o r ss h a r e db y t w op o i n t s ，a n dc a l c u l a t e st h ed e n s i t yo fe v e r yp o i n t n e x t ，t h i sa l g o r i t h mb u i l d s c l u s t e r sb ye l i m i n a t i n gn o i s ea n da s s o c i a t i n gn o n n o i s ep o i n t sw i t hr e p r e s e n t a t i v eo r c o r ep o i n t s s e c o n d l b a ne v a l u a t i o ni n d e x e ss y s t e mo i l s u i t a b i l i t y i s s t u d i e d s u i t a b i l i t y a n a l y s i si sas p e c i a lw a y u s e dt os t u d yt h er c l a t i o n s h i pb e t w e e nac e r t a i nl a n du n i t a n di t s e c o l o g i c a le n v i r o n m e n t w h i c hi s a l s oac o r eo fe c o l o g i c a lp l a n n i n g t h i s r e s e a r c h ，a c c o r d i n gt op r i n c i p l eo f t h el a n d s c a p ee c o l o g ya n di t sm e t h o d ，s t u d i e dt h e r e l a t i o n s h i pb e t w e e nt h el a n d s c a p et y p eo fg r e e n l a n d ，l a n d s c a p ee n v i r o n m e n ta n d i i a b s t r a c t l a n d s c a p e f u n c t i o n p r o b e di n t ot h ec o n n o t a t i o na n dt h e t 1 1 e o r e f i c a l s y s t e m o f l a n d s c a p es u i t a b i l i t y , f i n d a s e r y o fs u i t a b l e l a n d s c a p e i n d e x e sw i t h s t a b i l i t y , d o m i n a n t ，e f f e c t i v e n e s s ，a n dc o n s t r u c ta ne v a l u a t i o ni n d e x e ss y s t e mw h i c hi n c l u d e s t h e g r e e n l a n ds u i t a b i l i t y t ot h e e n v i r o n m e n t ，c i r c u m s t a n t i a lh a r m o n y , e c o l o g i c a l f u n c t i o na n da e s t h e t i cf u n c t i o n a tl a s t ，t h es h a r e dn e a r e s t n e i g h b o rb a s e dc l u s t e r i n ga l g o r i t h m ，i su s e di n e c o l o g i c a le v a l u a t i o no ns u i t a b i l i t yo f g r e e n l a n d l a n d s c a p e k e y w 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 ；s i m i l a r i t y ；s h a r e dn e a r e s t n e i g h b o r s ； s u i t a b i l i t ya n a l y s i s 1 i i 关于学位论文使用授权的说明 本人完全了解广西大学有关保留、使用学位论文的规定，即： 广西大学拥有在著作权法规定范围内学位论文的使用权，其中包 括：( 1 ) 已获学位的研究生必须按学校规定提交学位论文，学校可以 采用影印、缩印或其他复制手段保存研究生上交的学位论文；( 2 ) 为 教学和科研目的，学校可以将公开的学位论文作为资料在图书馆、资 料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内 容。 本人保证遵守上述规定。 ( 保密的论文在解密后遵守此规定) 作者签名：豳! 敛 r期：趔：丛 导师签名 日期 第1 章引言 第1 章引言 1 1 论文研究的目的和意义 随着社会的进步和经济的发展，如何协调人与自然的关系已成为园林和环 保工作者的首要任务。而园林绿地的建设与发展又是保护和改善城市环境极其 重要的一环。园林绿地在维持城市生态平衡、净化美化城市环境及维护市民身 心健康等方面起着其它城市景观要素不可替代的生态服务功能。随着现代城市 生态环境问题的日益突出、以及城市生活质量与居民需求层次的不断提高，以 改善城市生态环境、美化城市景观为目标的城市绿地系统建设已成为当前城市 建设和可持续发展战略的重要内容。然而，由于目前我国大多数城市结构均以 人和经济要素的流转为中心而构建，存在绿地景观面积有限、布局分散、树种 配置不合理、绿地可达性低等缺点“；同时，受“草坪热”、“广场风”的影 响，一些城市把园林绿化重点放在铺建大型草坪、广场上，致使城市园林绿地 生态结构简单脆弱，绿地的综合效能未能有效发挥，生态服务功能降低，据 k r e u t e r 等在美国s a na u t o n i o 地区的研究结果，在1 9 7 6 - 1 9 9 1 年间，由于城市扩大 使绿地每年生态系统服务功能降低1 5 4 。3 。 在生态评价的方法上，最初是采用因子叠加的人工作图的方式，如景观单 元法，筛网制图法和灰调子法等。其中以灰调子法最为重要，它是由美国景观 建筑大n i m c h a r g 所创，此法是在同一比例尺上用深浅不同的色调表示出不同的 适宜性等级，一般用深调子表示适宜度低的等级，用浅调子表示适宜度高的等 级，然后把所有的单因素按一定顺序叠加。后来又逐步建立和发展了地图重叠 法、权重法、因子组合法、g i s 方法”。这些评价方法在地域较小的范围内， 数据量不是很大的情况下，能够得到很好的评价结果。但是随着社会的发展， 越来越多的地方进行生态建设，得到了海量的数据，生态评价具有系统性、复 杂性的特点，在评价过程中涉及到的因子众多、不确定性大、目标复杂，计算 相当繁琐，要对这些海量、复杂的数据进行处理仅依靠原束的方法已经难以完 成，因此本课题提出了将数据挖掘技术应用于生念评价中。 数据挖掘是一种新兴的智能信息处理技术，随着相关信息技术的迅猛发展， 数据挖掘的应用领域不断地拓宽和深入。数据挖掘技术在商业方面应用较早， 第1 章引肓 它可以增强企业的竞争优势，缩短销售周期，降低生产成本，有助于制定市场 计划和销售策略。目前，已经成为电子商务中的关键技术。由于数据挖掘在开 发信息资源方面的优越性，已逐步推广到保险、医疗、军事、生物工程、商业 智能、制造业和电信等各个行业的应用。数据挖掘技术已经成功地应用到了很 多的领域，因此将数据挖掘技术应用于生态评价具有很大的现实意义。 1 2 国内外的研究及发展趋势 1 2 1 国内外的研究现状 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，目前各行 业存储了大量的数据，航空航天、气象、医疗、农业等行业尤为突出。传统的 数据分析手段难以应付，导致越来越严重的数据灾难，迫使决策者出现或是穷 于应付，或是置之不理的事实。关系数据库提供的简单查询及报表生成功能， 只能获得数据的表层信息，而不能获得数据属性的内在关系和隐含的信息，即 淹没了包含的知识，造成了资源的浪费。为了使消耗大量财力与物力所收集与 整理的宝贵数据资源得以利用，有效解决数据丰富性及知识贫乏性的矛盾，需 要新技术智能、自动地分析处理原始数据，促使了数据库中的知识发现( 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 ) ，也称为数据挖掘( d a t am i n i n g ) 技术的出现。 k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议上。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了7 次， 规模由原来的专题讨论会发展到国际学术大会。研究重点也逐渐从发现方法转 向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互 渗透。数据挖掘界于1 9 9 5 年召开了第一届知识发现与数据挖掘国际学术会议。 于1 9 9 8 年建立起一个新的学术组织a c m s i g k d d ( s p e c i a li n t e r e s t e dg r o u po n 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 ) 。a c m s i g k d d 于1 9 9 9 年组织了第五届知识 发现与数据挖掘国际学术会议( k d d 9 9 ) ，其他国际或地区性数据挖掘会议，如 “知识发现与数据挖掘太平洋亚洲会议”( p a k d d ) ，“数据库中知识发现原理 与实践欧洲会议”( p k d d ) 和“数据仓库与知识发现国际会议”( d a w a k ) 。数据 挖掘研究还发表在书籍、会议以及有关数据库、统计学、机器学习和数据可视 化的杂志上。这些都促成了数据挖掘技术的研究与发展”“。 因此，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也 第】章引言 纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g e a n dd a t a e n g i n e e r i n g 会刊领 先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的 最新成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系 统设计的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、 空值等问题，k d d 系统与其它传统的机器学习、专家系统、人工神经网络、数理 统计分析系统的联系和区别，以及相应的基本对策。 d m k d 应用取得了很大的成就。在多学科相互交融和相互促进的信息时代 d m k d 为大型数据库的利用提供了有效工具，是决策支持系统的一个重要组成 部分。在数据挖掘技术日益发展的同时，许多数据挖掘的商业软件工具也逐渐 问世。国外大约有1 5 0 家从事数据挖掘的软件公司。目前，世界上比较有影响 的典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n t m i n e r 、s g i 公司的v i i n e s e t 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s e s t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、加拿大s i m o nf r a s e r 大学开发的 d b m i n n e r 还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、q u e s t 等”。 目前，国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究 进一步发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提 高：传统的统计学回归法在k d d 中的应用：k d d 与数据库的紧密结合。在应用方 面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而 不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。 国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的 研究中心进行这方面的工作，此外，一些公司的相关软件也开始在国内销售， 如p l a t i n u m ，b o 以及i b m 。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所 涉及的研究领域很多，般集中于学习算法的研究、数据挖掘的实际应用以及 有关数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行 的，如国家自然科学基金、8 6 3 计划、“九五”计划等。南京大学的徐洁磐、陈 栋等人开发了一个原型系统：k n i g h t ，这是一个通用的d m 工具，可用于处理不同 领域的知识发现任务，主要有聚类分析、特征知识发现、分类规则发现、关联 规则发现、函数依赖发现及基于查询的知识发现等。中科院软件所史忠植研究 员领导的课题组在d m 技术的研究上也有大量成果，发表若干论文。李得毅院士、 第1 章引言 孟海军等人发表多篇论文”。 12 2 发展趋势 数据挖掘是一个跨学科交叉领域。涉及数据库技术、人工智能、机器学习、 神经网络、统计学、模式识别、知识库系统、知识获取、信息检索、高性能计 算和数据可视化等“”3 。数据挖掘是面向应用的一种技术。数据挖掘中发现的知 识都是相对的，是由特定前提和约束条件、面向特定领域的，同时还要能易于 被用户理解，最好能用自然语言表达发现结果“”。 数掘挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务分， 可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、 依赖关系或依赖模型发现、异常和趋势发现等等：根据挖掘对象分，有关系数据 库、面向对象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、 异质数据库、遗产数据库以及环球网w e b ：根据挖掘方法分，可粗分为：机器学习 方法、统计方法、神经网络方法和数据库方法。机器学习中，可细分为：归纳学 习方法( 决策树、规则归纳等) 、基于范例学习、遗传算法等。统计方法中，可 细分为：回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、费歇尔判别、 非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索性分析( 主元分析法、 相关分析法等) 等。神经网络方法中，可细分为：前向神经网络( b p 算法等) 、自 组织神经网络( 自组织特征映射、竞争学习等) 等。数据库方法主要是多维数据 分析或o l a p 方法，另外还有面向属性的归纳方法“。”1 。现在大多数数据挖掘领 域”的研究主要集中以下几个方面： ( 1 ) 应用方面 早期的数据挖掘应用主要集中在帮助企业提升竞争能力。随着数据挖掘的 同益普及，数据挖掘也日益探索其他应用范围，如生物医学、金融分析和电信 等领域。此外，随着电子商务和电子市场逐渐成为零售业的主流因素，数据挖 掘也在不断扩展其在商业领域的应用面，通用数据挖掘系统在通行处理特定应 用问题时有其局限性，因此目前的一种趋势是开发针对特定应用的数据挖掘系 统。 ( 2 ) 可伸缩的数据挖掘方法 与传统的数据分析方法相比，数据挖掘必须能够有效地处理大量数据，而 且尽可能是交互式的。由于数据量是在不断地激增，因此针对单独的和集成的 第1 章引言 数据挖掘功能的可伸缩算法显得十分重要。一个重要的方向是所谓基于约束的 挖掘。它致力于在增加用户交互的同时如何改进挖掘处理的总体效率。它提供 了额外的控制方法，允许用户说明和使用约束，引导数据挖掘系统对感兴趣模 式的搜索。 ( 3 ) 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成 数据库系统、数据仓库系统和w w w 已经成为信息处理环境中十分重要的 方面。数据挖掘系统的理想体系结构是与数据库和数据仓库系统的紧偶合方式。 事务管理、查询处理、联机分析处理和联机分析挖掘应集成在一个统一框架中。 这将保证数据的可获得性，数据挖掘的可移植性，可伸缩性，高可靠性，以及 对多维数据分析和探查的集成信息处理环境。 ( 4 ) 数据挖掘语言的标准化 标准的数据挖掘语言或其他方法的标准化工作将有助于数据挖掘的系统化 丌发，改进多个数据挖掘系统和功能间的互操作，促进数据挖掘系统在企业和 社会中的教育和使用。 ( 5 ) 可视化数据挖掘 可视化数据挖掘是从大量数据中发现知识的有效途径。系统研究和开发可 视化数据挖掘技术将有助于推进数据挖掘作为数据分析的基本工具。 ( 6 ) 复杂数据类型挖掘的新方法 复杂数据类型挖掘是数据挖掘中一项重要的前沿研究课题。虽然在地理空 间挖掘、多媒体挖掘、时序挖掘、离散挖掘以及文本挖掘方面取得一些进展， 但它们与实际应用的需要仍存在很大的距离对此需要进一步的研究，尤其是针 对上述数据类型的现存数据分析技术与数据挖掘方法集成起来的研究。 ( 7 ) w e b 挖掘 由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要的角色， 有关w e b 内容挖掘、w e b 曰志挖掘和因特网上的数据挖掘服务，将成为数据挖 掘中一个最为重要和繁荣的子领域。 ( 8 ) 数据挖掘中的隐私保护与信息安全 随着数据挖掘工具和电信与计算机网络的同益普及，数据挖掘要面对的一 个重要问题是隐私保护和信息安全。需要进一步开发有关方法，以便在适当的 信息访问和挖掘过程中确保隐私保护与信息安全。 第1 章引言 1 3 本论文的主要工作 收集数据挖掘的资料，研究数据挖掘的各种模型和算法，了解各种模型 和算法适用的不同领域以及完成的基本功能。 园林绿地景观适宜度理论与评价指标体系研究。从一定绿地单元上发挥 绿地最佳综合功能的角度，依据景观生态学原理研究绿地景观类型与景观环境、 景观功能的关系，探讨景观适宜性的内涵及理论体系；筛选具稳定性、主导性、 可操作性的景观适宜度指标，构建合理的景观适宜度评价指标体系。 园林绿地环境适应性、环境协调性、美学功能和生态功能的定量方法研 究。确定土壤地形等因子及功能区位、大气污染物( s 0 2 、t s p 等) 、绿地景观 美学特征的定量方法。 研究应用于生态评价的聚类分析算法，并进行相应的改进。 进行算法的性能测试，用改进的聚类算法对绿地适宜度进行评价。 1 4 本文的结构 全文共六章，内容安排如下： 第一章介绍论文的研究意义及国内外的发展现状及进展情况 第二章介绍数据挖掘的内容和聚类分析以及典型的聚类分析算法 第三章详细介绍改进的共享最近邻聚类算法 第四章园林绿地景观适宜度评价指标的建立以及定量研究 第五章实现改进的聚类算法并且应用于适宜度评价中 第六章进行论文总结及进一步的工作 6 第2 章数据挖掘中的聚类分析 第2 章数据挖掘中的聚类分析 2 1 数据挖掘技术的概述 2 ，1 1 数据挖掘的概念 对于数据挖掘( d m ，d a t am i n i n g ) ，一种比较公认的定义是w j f r a w l e y ， g p i a t e t s k y ，s h a p i r o 等人提出的：数据挖掘就是从大型数据库的数据中提取人们 感兴趣的知识。这些知识是隐含的、事先未知的潜在有用信息，提取的知识表 示为概念、规则、规律、模式等形式。这种定义把数据挖掘的对象定义为数据 库。而更广义的说法是：数据挖掘意味着在一些事实或观察数据的集合中寻找模 式的决策支持过程。它是一个利用各种工具在海量数据中发现模型和数据间关 系的过程。还有很多和这一术语相近的术语，如数据库中知识发现、信息发现、 知识抽取、智能数据分析、信息收获、和数据考古等”1 。 数据库中的知识发现( k d d , 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 ) 术语于1 9 8 9 年 出现，其描述性定义是f a y y a d 等给出的：数据库的知识发现是从数据中识别出有 效的、新颖的、潜在有用的、以及最终可理解的模式的高级过程“。 从定义可以看出，作为一个学术领域，数据挖掘和知识发现( k d d ) 具有很大 的重合度。所以一些学者认为数据挖掘和知识发现是等价的概念，人工智能领 域习惯称k d d ，而数据库领域习惯称数据挖掘。但也有些学者把数据挖掘视为 数据库中知识发现过程的一个基本步骤。知识发现过程主要包括：数据清理； 数据集成；数据选择；数据变换；数据挖掘；模式评估：知识表示。 数据挖掘步骤可以与用户或知识库交互。有用的模式提供给用户或作为新的知 识存放在知识库中。注意，根据这种观点，数据挖掘只是整个过程的一步，因 为它发现隐藏的模式。 2 1 2 数据挖掘的系统结构和步骤 本文采用数据挖掘的广义观点“z 4 - z s l ：认为数据挖掘是从存放在数据库、数 据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。基于这种观点，典 型的数据挖掘系统如图l l 所示。 第2 章数据挖掘中的聚类分析 图1 1 数据挖掘系统结构 f i g 1 1s y s t e m s t r u c t u r eo f d a t am i n n i n g 数据挖掘的过程可以粗略分为：问题定义、数据收集和预处理、数据挖掘算 法执行、以及结果的解释和评估，如图卜2 所示。 图1 2 数据挖掘过程 f i g 1 2 p r o c e s so f d a t a m i n n i n g ( 1 ) 数据定义( t a s kd e f m i t i o n ) 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何 种知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中， 数据挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对 数据挖掘的要求，另一方面通过对各种学习算法的对比而确定可用的学习算法。 后续的学习算法选择和数据集准备都是在此基础上进行的。 第2 章数据挖掘中的聚类分析 ( 2 ) 数据收集和预处理( d a t a p r e p a r a t i o na n dp r e p r o c e s s i n g ) 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。 数据选取的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ，是 根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般包括消除噪 声、推导计算缺值数据、消除重复记录、完成数据类型转换等。当数据挖掘的 对象是数据仓库时，一般来说，数据预处理已经在生成数据仓库时完成，数据 变换的主要目的是消减数据维数或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中 找出真f 有用的特征，以减少数据挖掘时要考虑的特征或变量个数。 ( 3 ) 数据挖掘( d a t am i n i n g ) 算法执行 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的，如 分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定 使用什么样的算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特 点，因此需要用与之相关的算法来挖掘：二是用户或实际运行系统的要求，有的 用户希望获取描述型的( d e s c r i p t i v e ) 容易理解的知识，葡有的用户只是获取预测 准确度尽可能高的预测型( p r e d i c t i v e ) 的知识。 ( 4 ) 结果解释和评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 数据挖掘阶段发现出来的模式，经过评估。可能存在冗余或无关的模式， 这时需要将其剔除。也有可能模式不满足用户要求，这时则需要整个发现过程 回退到前一阶段。重新选取数据、采用新的数据变换方法、设定新的参数值， 甚至换一种算法。另外，数据挖掘是面向最终用户的，因此需要对发现的模式 进行可视化，或者需要将结果转换为用户易懂的表示。 数据挖掘算法执行，仅仅是整个过程的一个步骤。数据挖掘质量的好坏有 两个影响要素：一是所采用的数据挖掘技术的有效性；二是用于挖掘的数据的质 量和数量。整个挖掘过程是一个不断反馈的过程。 213 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务 一般可以分为两种：描述和预测。描述性数据挖掘任务刻划数据库中数据的一 般特性。预测性挖掘任务在当前数据上进行推断，以进行预测。1 。 ( 1 ) 概念类描述：特征化和区分( c o n c e p t c l a s sd e s c r i p t i o n ： c h a r a c t e r i z a t i o n d i s c r i m i n a t i o n ) 9 第2 章数据挖掘中的聚类分析 概念描述以简洁汇总的形式描述给定的任务相关数据集，提供数据价值的 一般特性，一般应用于描述式数据挖掘。概念或类描述由特征化和比较或区分 组成，有两种一般方法：基于数据立方体o l a p 的方法和面向属性归纳的方法。包 括以下技术：数据聚焦、通过属性删除或属性概化概化数据、计数和聚集值累计、 属性概化控制和概化数据可视化。与机器学习算法相比。面向数据库的概念描 述导致在大型数据仓库中的有效性和可伸缩性。对基本方法加以修f ，概念描 述挖掘可以用增量方式、并行方式或分布方式进行。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析发现关联规则，这些规则展示属性值频繁地在给定数据集中一起 出现的条件。关联分析广泛用于购物篮、商务管理和决策分析，是商业分析中 应用最为广泛的一种数据挖掘方法和模式。有效的算法包括a p f i o r i 算法和频繁模 式增长( f p 一增长) 算法。并注重多层关联规则、多维关联规贝和基予约束的关联 规则的挖掘。 ( 3 ) 分类和预测分析( c l a s s i f i c a t i o n l p r e d i c t i o na n a l y s i s ) 分类和预测是数据分析的两种重要形式，可以用于提取描述重要数据类的 模型或预测未来的数据趋势。主要方法包括：决策树判定树，算法有i d 3 和c 4 。5 ， 剪枝算法，以及s l i q ，s p r i n t ，r a i n f o r e s t 和p u b l i c 等可伸缩算法。贝叶斯分 类和贝叶斯置信网络，这两种方法都基于后验概率的贝叶斯定理。后向传播， 是一种用于分类的神经网络算法，使用梯度下降方法。关联挖掘技术在大型 数据仓库中搜索频繁出现的模式，可以用于分类。卜最近邻分类、基于案例的 推理是基于要求的分类方法。在遗传算法中，规则群体通过交叉和变异操作 进化，直到群体中所有的规则都满足指定的阈值。粗糙集理论可以用来近似 地定义类，这些类根据可用的属性是不可区分的。模糊集方法用隶属函数替 换连续值属性的陡峭阈值。多策略学习方法。线性、非线性和广义线性回 归模型都可以用于预测。 ( 4 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) 属于无指导学习。对象根据最大化类内的相似性、最小化类内的相似性的 原则进行聚类或分组。聚类分析有广泛的应用包括市场或客户分割、模式识别、 生物学研究、空间数据分析、w e b 文档分类及其他方面。它可以用作独立的数据 挖掘工具来获得对数据分布的了解，也可以作为其他数据挖掘算法的预处理步 骤。 第2 章数据挖掘中的聚类分析 ( 5 ) 孤立点分析( o u t l i e rm i n i n g ) 对于欺诈探测、定制市场及医疗分析及其他任务是非常有用的。基于计算 机的孤立点挖掘方法包括统计学方法、基于距离的方法和基于偏差的方法。 ( 6 ) 演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋势并对其建模，包括时间序列数据 分析、序列或周期模式匹配和基于类似性的数据分析。演变分析可用于趋势分 析、相似性搜索、与时间有关的序列模式挖掘和周期模式挖掘。 ( 7 ) 复杂类型的数据挖掘 是数据挖掘技术的当前一个重要的研究领域，极大提升了数据分析能力的 深度和广度，主要包括：对象数据挖掘、空间数据挖掘、多媒体数据挖掘、时序 和序列数据挖掘、文本挖掘和w e b 挖掘等。 2 2 聚类分析的概述 聚类的输入是一组未分类的记录，而且事先也不知道要分成几类，它通过 分析数据，根据一定的分类准则，合理划分记录集合，从而确定每个记录所属 的类别。不同的聚类算法中，用于描述相似性的函数也有所不同，有的采用欧 氏距离或马氏距离，有的采用向量夹角的余弦，也有的采用其他的度量方法。 2 2 1 聚类分析定义 聚类问题的定义如下：在数据空闻a 中，数据集x 由许多数据点( 或数据对 象) 组成，数据点薯= ( 置一，翰) a ，的每个属性( 或特征、或维度) 既可 以是数值型的，也可以是枚举型的。数据集x 相当于是一个n x d 矩阵。假设数 据集中有个n 个对象矗，i = l ，n 。聚类的最终日的是把数据集x 划分为k 个分割c f ，i = l 一，七，也可能有些对象不属于任何一个分割，这些就是噪声 g 驯。所有这些分割与噪声的并集就是数据集x ，并且这些分割之间没有交集， 巳u x c l u u c k u c 。m j ，c i n c | = o 0 2 - 1 、 这些分割g 就是聚类。 采用不同的聚类方法，同一个记录集合可能有不同的划分结果。聚类的结 果与特征选取也有很大关系。例如对人进行聚类：可以根据身高分类，可以根据 第2 章数据挖掘中的聚类分析 肤色分类，也可以根据年龄分类。选取不同的特征，就会产生不同的结果。 2 2 2 基本数据结构 本小节讨论在聚类分析中经常出现的数据类型，以及如何对其进行预处理。 大多数聚类算法选择如下两种有代表性的数据结构： 1 数据矩阵 数据矩阵是一种对象与变量结构。它用p 个变量( 也称为度量或属性，即维) 来表现n 个对象。这种数据结构是关系表的形式，或者可以看成是n x p 的矩阵， 其中每一行为一个向量，代表一个数据对象。 1 _ ： x ，1 ： x n i ( 2 2 ) 2 相似矩阵 相似度矩阵( 或相异度矩阵) 是一种对象一对象结构。存储n 个对象两两之间 的近似性，表现为一个n x r 的对称矩阵。 j ( d ) d ( 2 ，j )1 ( o ) d ( 3 ，) d ( s ，2 ) 1 ( 0 ) i! ：l ( o 、 d ( n ，j ) d ( n ，2 ) 1 ( 0 ) ( 2 - 3 ) 其中d ( i ，1 是对象i 和，之间相似( 异) 性的量化表示，通常为一个非负的数 值。当对象i 和，越相似或越“接近”，其值就越大( 越接近0 ) ；反之，其值越接 近0 ( 大) 。因为d ( i ，) = d ( f ) ，而且d ( i ，f ) = 玎，因此有形如上式的对称矩阵。 由于相似度与相异度对于聚类而言是同等的度量，因此本文以下将统一使用相 似度这个概念来同时表示相异度或距离。 许多算法以相似度矩阵为基础，如果原始数据是以数据矩阵的形式表现的， 使用算法之前需要将数据矩阵经过一定的计算转换成为相似度矩阵。 22 3 簇的定义 聚类分析的结果中由相似的数据对象形成的一个分组称为簇( c l u s t e r ) 。由于 w ；知；啊 第2 章数据挖掘中的聚类分析 不同应用所要分析的具体数据具有不同的特征，因此聚类的目标簇具有不同的 形式和定义。目前，术语簇还没有一个精确统的定义。不过，文献中存在如 下一些常用的定义。 分离明显的簇：分离明显的簇由这样的一些点构成，簇内任意一点与簇 内其它所有点的距离都小于它与簇外任意一点的距离。 基于中心的簇：基于中心的簇由这样的一些点构成，簇内任意一点与簇 “中心点”的距离都小于它与其它簇的“中心点”的距离。这种簇的中 ，t l , 点通常是簇的质心一簇内所有点的平均值，或者是簇的形心 ( m e d o i d ) 一簇内“最具代表性”的点。 连续的簇：连续的簇( 最近邻或传递簇) 由这样的一些点构成，簇内任意 一点与簇内其它一个或多个点的距离小于它与簇外任意一点的距离。 基于密度的簇：基于密度的簇是一个由密集点组成的区域，与其它簇之 间被低密度的区域分隔开。这一定义通常用于探测不规则的或相互缠绕 的簇，同时需要处理噪音数据或孤立点。 基于相似性的簇：基于相似性的簇由“相似”点组成，并且不同簇的点 不相似。其中一种变化是将簇定义为一系列的点，这些点共同建立一个 具有同性质( 例如密度或形状) 的区域。 2 3 典型的聚类算法的研究 目前文献中存在大量的聚类算法。从算法聚类的策略来看，大体上可以分 为划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法 几类。下面将分别介绍其中较为典型的方法。 23 1 划分方法 给定一个包含”个数据对象的数据库，以及要生成簇的数目k ，一个基于划 分的聚类算法将数据对象组织为k 个划分f k n ) ，其中每个划分代表一个簇。 通常会采用一个划分准则( 常称为相似度函数，例如距离) ，以确定同一簇中的 对象是相似的，而不同簇中的对象是相异的。”。 典型的划分方法有驴平均法和_ | 广中心点法。 1 基于质心的k 一平均法 第2 章数据挖掘中的聚类分析 卜平均算法( k m e a n s ) 以k 为参数，把n 个对象分为k 个簇，使簇内具有较 高的相似度，而簇蒯的相似度较低。相似度的计算根据簇中对象的平均值( 被看 作簇的重心) 来进行。 卜平均算法首先随机选取k 个数据对象，每个对象代表一个簇的平均值或中 心点。其余的对象按照它们与这些平均值之间的距离，被赋予与之最相近的簇。 然后，算法对每个新簇重新计算其平均值。这个过程一直迭代直到一个准则函 数收敛为止。典型的准则函数是方差准则函数，定义为： e = ：，e 。卜m f f ( 2 - 4 ) 其中x 代表数据空间中给定的对象，m ，是簇c l 的平均值b 和m ，可以是任意维的 向量) 。该准则函数试图使结果簇内部尽可能地紧凑并相互分离。 扣平均算法的过程如图2 1 所示。假设有一个二维的数据集位于一个矩形区 域中。令k = 3 ，即用户想将该数据集聚类成三个簇。按照上述的算法，首先任意 的三个数据点被选作初始簇的平均值点( 图中用“+ ”标示) 。于是其余的每个点 被分配到距离最近的平均值点所代表的簇中，如图2 1 ( 口) 所示，每个簇的轮廓用 点虚线环绕表示。 每次划分后，簇中的元素只要发生了变化，都有可能改变簇的平均值。而 数据对象将随着新的簇的平均值重新分布，其结果如图2 1 ( 6 ) 所示，每个新簇的 轮廓用线段虚线环绕表示。 这一过程迭代的最终结果如图2 1 ( c ) 所示( 每个簇的轮廓用实线环绕) ，此时 每个簇中的数据对象不再重新分布，即使得上述的方差准则函数收敛。该结果 即为k 一平均算法的聚类结果。 图2 1k - 平均算法的聚类过程 f i g 2 ，1t h ec l u s t e r i n gp r o c e s so f k m e a n s 膏_ 平