当前位置： >>
基于数据挖掘的分类和聚类算法研究及R语言实现
暨南大学硕士学位论文暨南大学 硕士学位论文题名（中英对照） 基于数据挖掘的分类和聚类算法研究及 R 语言实现 ： A Study on Algorithm of Classification and ClusterBased on Data Mining and Realization by R programe 作者姓名： 方匡南指导教师姓名 及学位、职称：王斌会 博士教授学科、专业名称：经济学统计学论文提交日期：2007 年 5 月论文答辩日期：2007 年 6 月答辩委员会主席：论文评阅人：学位授予单位和日期：1基于数据挖掘的分类和聚类算法研究及 R 语言实现独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得暨南大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解暨南大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权暨南大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 （保密的学位论文在解密后适用本授权书）学位论文作者签名： 签字日期： 年 月 日导师签名： 签字日期： 年 月 日学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编：2暨南大学硕士学位论文摘要数据挖掘是个新兴的研究领域，涉及到统计学、数据库、机器学习等众多学科，正以其 强大的功能和广泛的应用受到高度的关注。数据挖掘的方法众多，其中分类、聚类方法是数 据挖掘应用最多的方法，而算法研究是数据挖掘研究领域的重中之重，算法的好坏直接影响 到数据挖掘的效率，所以本文主要深入系统地研究分类、聚类算法。虽然目前研究分类、聚 类算法的文章比较多，但大多数研究只停留在理论上的探讨，并没有相应的算法实现。本文 着重于算法实现的研究，在国内首次利用 R 语言实现数据挖掘算法，因为 R 语言相对于其他 一些软件有着免费、开放源代码、算法更新速度快等优点。 论文第一章介绍数据挖掘的研究背景、目的和意义以及研究方法和框架。第二章主要介 绍比较各分类算法及 R 语言实现，包括基于距离分类的 KNN 算法；基于决策树方法的 C4.5 算法、CART 算法；基于神经网络的 BP 算法。第三章主要介绍比较各种聚类算法及 R 语言实 现。具体介绍了划分方法的 K-means、pam、clara 算法；层次方法的 AGNES、DIANA 算法； 基于密度聚类方法的 DBSCAN 算法；基于模型聚类方法的 COBWEB、SOM 算法；基于模糊 聚类方法的 FCM 算法。 第四章实证分析主要以台湾教授蔡欣玲就护理人员离职调查的数据为 例，按数据挖掘的标准流程 CRISP-DM 进行分析，首先对数据作初步统计分析，掌握护理人 员的初步情况，再接着利用聚类方法来分析医院护理人员的离职意愿，然后利用分类方法建 立预测模型。第五章对本文的研究情况进行总结并展望。关键词：数据挖掘分类算法聚类算法R 语言实现3基于数据挖掘的分类和聚类算法研究及 R 语言实现ABSTRACT DataMing is a new study realm ，coming down to many subjects such as statistics、database、 machine learning and so on,it was paid high attention for its strong functions and broad application.DataMining has many methods , classification and cluster are two of the most applied methods,but algorithm study is the most important field in DataMing study ,whether the algorithm is good or bad will directly affect the efficiency of DataMing,so this paper will study deeply and systemly on classification and cluster algorithm.Although papers studying on classification and cluster algorithm are many ,but most of many just discussed on theory ,didn’t realize these algorithms.This paper will emphasize the realization of algorithm and realize algorithm by R programe first in china,because R programe has advantages such as free 、open source and algorithm updating quickly compared to other softwares. The first chapter of paper introduce the study background 、purposes and meaning andmeans and frame.The second chapter introduce and compare with every algorithm of classification and realized by R programe, including the KNN algorithm based on distance,the C4.5、CART algorithms based on decision tree and the BP algorithm based on neural network.then realize these algorithms by R programe。The third chapter introduce and compared with every algorithm of cluster and realized by R programe,including the K-means、pam、clara algorithms of partitioning methods,the AGNES、DIANA of hierarchical methods,the DBSCAN algorithms of density-based methods,the COBWEB 、 SOM algorithms of Model-Based clustering method and the FCM algorithm of Fuzzy clustering method. then realize these algorithms by R programe.The fourth chapter is demonstration , Taking the data about the job-leaving of nurses which collected by professor cai xinling TaiWan as an example,analyse the data following the standard flow CRISP-DM.First,simply analyse the data by statistics and understand the first-step knowloge ,then analyse the job-leaving willing by cluster method and establish predicted model by classification method.The fifth chapter summarize the paper and give expectation .KEYWORD： DataMiningclassification algorithmcluster algorithmrealization by Rprograme4暨南大学硕士学位论文目录中文摘要……………………………………………………………………………………………(Ⅰ) 英文摘要……………………………………………………………………………………………(Ⅱ) 目录…………………………………………………………………………………………………(Ⅲ) 1． 绪论………………………………………………………………………………………………1 1.1数据挖掘产生的背景和定义……………………………………………………………………1 1.2数据挖掘国内外发展现状………………………………………………………………………2 1.3 数据挖掘与传统统计之间的关系………………………………………………………………3 1.4 数据挖掘的主要应用分析………………………………………………………………………5 1.5 研究目的和意义…………………………………………………………………………………7 1.6 论文研究框架……………………………………………………………………………………7 1.7 数据挖掘算法的研究工具―R 语言……………………………………………………………82. 分类分析方法及 R 语言实现………………………………………………………………… 122.1 分类分析的基本概念、步骤及方法……………………………………………………………12 2.2 分类分析的评估标准……………………………………………………………………………13 2.3基于距离分类方法及R语言实现………………………………………………………………14 2.4基于决策树分类方法及R语言实现 2.5基于神经网络分类方法及R语言实现3. 聚类分析方法及R语言实现……………………………………………………………………283.1聚类分析基本概念及要求…………………………………………………………………………28 3.2聚类分析的数据类型及处理方法…………………………………………………………………29 3.3 划分聚类方法及 R 语言实现………………………………………………………………35 3.4 层次聚类方法及 R 语言实现 3.5 基于密度聚类方法及 R 语言实现 3.6 基于模型聚类方法及 R 语言实现 3.7 模糊聚类方法及 R 语言实现4. 实证分析………………………………………………………………………………………………544.1 研究背景……………………………………………………………………………………………54 4.2.数据整理……………………………………………………………………………………………54 4.3.数据初步统计分析…………………………………………………………………………………55 4.4.护理人员离职意愿的聚类及交叉分析……………………………………………………………585基于数据挖掘的分类和聚类算法研究及 R 语言实现4.5.护理人员离职预测模型的建立……………………………………………………………………61 4.6.小结…………………………………………………………………………………………………655. 总结与展望…………………………………………………………………………………………675.1 总结 5.2 展望 参考文献 …………………………………………………………………………………………………69 附录 ………………………………………………………………………………………………………71 在学期间发表论文及出版著作清单 致谢 ………………………………………………………………………………………………………826暨南大学硕士学位论文第 1 章 绪论1.1 数据挖掘产生的背景和定义1.1.1 数据挖掘产生的背景 随着信息科技的进步以及电子化时代的到来，人们以更快捷、更容易、更廉价的方式获 取和存储数据，使得数据及信息量以指数方式增长。据粗略估计，一个中等规模企业每天要 产生100MB以上的商业数据。而电信、银行、大型零售业每天产生的数据量以TB来计算。快 速增长的海量数据收集、存放在大型数据库中，如果没有强有力的工具，理解它们已经远远 超出了人的能力范围，收集在大型数据库中的海量而杂乱数据变成了“数据垃圾”“数据坟 、 墓” ，就如图1.1所示。高维海量的数据增加了传统统计分析方法的难度，这样，对大型数据的 处理和分析的需求显得越来越迫切。如何才能不被信息的汪洋大海所淹没，从中及时发现有 用的知识，提高信息利用率呢?要想使数据真正成为一个公司的资源，只有充分利用它为公司 自身的业务决策和战略发展服务才行。因此，面对“人们被数据淹没，人们却饥饿于知识” 的挑战，从数据库中发现知识(Knowledge Discovery in Databases)及其核心技术――数据 挖掘(Data Mining)便应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。图 1.1我们数据丰富但知识贫乏1.1.2 数据挖掘的定义 数据挖掘有广义和狭义之分。广义的数据挖掘，指从大量的数据中发现隐藏的、内在的 和有用的知识或信息的过程。狭义的数据挖掘是指知识发现中的一个关键步骤，是一个抽取 有用模式或建立模型的重要环节。在参考文献[17,23]中，知识发现是这样定义的:知识发现7基于数据挖掘的分类和聚类算法研究及 R 语言实现是识别出存在于数据库中有效的、新颖的、具有潜在价值的乃至最终可理解的模式的非平凡 过程。数据挖掘则是指从数据库的大量数据中揭示出隐含的、先前未知的并有潜在价值的信 息的非平凡过程[24，25]。 可见这两个术语的内涵大致相同。 对这两个术语更严格的区分是在 “知识发现96国际会议”上。Fayyad Piatetsky-Shapiro和Smyth指出[24，25]：“知识发现是从数据 库中发现知识的全部过程，而数据挖掘则是此全部过程的一个特定的关键步骤。这种定义把 数据挖掘的对象定义为数据库”。 数据挖掘更广义的定义是[26]:数据挖掘意味着在一些事实或观察数据的集合中寻找模式的 决策支持过程。实际上，数据挖掘的对象不仅是数据库，也可以是文件系统、或其它任何组 织在一起的数据集合。数据挖掘最新的对象是数据仓库。 一种较为公认的定义是由G.Piatetsky-Shapir等人提出的。数据挖掘是从大量的、不完全 的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的，但又是潜 在有用的信息和知识的过程.如图1.2。这个定义所包含的含义为:数据源必须是大量的、真实 的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；发现 的知识支持特定的被发现的问题。图 1.2 数据挖掘：在你的数据中搜索知识1.2 数据挖掘国内外发展现状1.2.1 国外数据挖掘发展现状 从数据库中发现知识(KDD)一词首次出现在1989年举行的第十一届国际联合人工智能学 术会议上。随后在1991年、1993年和1994年都举行KDD专题讨论会，汇集来自各个领域的研究 人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。 随着参与人员的不断增多，KDD国际会议发展成为年会。到目前为止，由美国人工智能协会主 办的KDD国际研讨会己经召开了8次，规模由原来的专题讨论会发展到国际学术大会，研究重8暨南大学硕士学位论文点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的 相互渗透。1999年，亚太地区在北京召开的第三届PAKDD会议收到158篇论文，空前热烈。IEEE 的KnowledgeandDataEngineering会刊率先在1993年出版了KDD技术专刊。并行计算、计算机 网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论， 甚至到了脍炙人口的程度。数据挖掘在1995年召开了第一届知识发现与数据挖掘国际学术会 议。该会议是由1989年至1994年举行的四次数据库中知识发现国际研讨会发展来的。数据挖 掘研究界于1998年建起了一个新的学术组织ACM-SIGKDD，即ACM下的数据库中知识发现专业组 (Special Interested Groupon Knowledge Discovery in Database).1999年ACM-SIGKDD组织 了第五届知识发现与数据挖掘国际学术会议(KDD'99)。专题杂志DataMining and Knowledge Discovery自1997年起有Kluwers出版社出版。ACM-SIGKDD还出版了一种季刊电子通信 SIGKDDExplorations。还有一些其他国际或地区性的数据挖掘会议如“知识发现与数据挖掘 太平洋亚洲会议”(PAKDD),“数据库与知识发现原理与实践欧洲会议”(PKADD)和“数据仓库 与知识发现国际会议(DaWaK)涉及数据挖掘的研究成果己在许多数据库国际会议论文集发表， 包括&ACM-SIGMOD数据管理国际会议”(SIGMOD),“超大型数据库国际会议” (VLDB),&ACM-SIGMOD-SIGART数据库原理研讨会”(PODS),“数据工程国际会议”(ICDE),“扩 展数据库技术国际会议”(EDBT),“数据库理论国际会议”(ICDT)“信息与知识管理国际会议” (CIKM), 数据库与专家系统应用国际会议” “ (DEXA)和 “数据库系统高级应用国际会议” (DASFAA) 数据挖掘的研究也发表在主要数据库杂志上，包括《IEEE知识与数据工程汇刊》(TKDE),(ACM 数据库系统汇刊》(TODS),(ACM杂志》(JACM),《信息系统》，(VLDA杂志》，《数据与知识工 程》，和《智能信息系统国际杂志》(JIIS)。此外，在Internet上还有不少KDD电子出版物， 其中以半月刊KnowledgeDiscoveryNuggets最为权威。目前，世界上比较有影响的典型数据挖 掘系统有:SAS公司的EnterpriseMiner,IBM公司的IntelligentMiner,SGI公司的 SetMiner,SPSS公司的Clementine,Sybase公司的WarehouseStudio,RuleQuestResearch公司 的See5、还有CoverStory, EXPLORA, KnowledgeDiscoveryWorkbench,Miner,Quest等。 1.2.2 国内数据挖掘发展现状 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及的研究领 域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研 究。目前进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、863计划、“九9基于数据挖掘的分类和聚类算法研究及 R 语言实现五”计划等，但还没有关于国内数据挖掘产品的报道。与国外相比，国内对数据挖掘的研究 稍晚，没有形成整体力量。1993年国家自然科学基金首次支持对该领域的研究项目。目前， 国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，如清华大学、 中科院计算技术研究所、空军第三研究所、海军装备论证中心等。北京系统工程研究所对模 糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研 究；华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则挖掘算法的优化和改造；南京大学、四川联合大学和上海交通大学等 单位探讨、研究了非结构化数据的知识发现以及Web数据挖掘。1.3 数据挖掘与传统统计之间的关系数据挖掘是揭示存在数据里的模式及数据间的关系的学科，它强调对大型数据的处理及 数据和知识间的潜在关系。统计学是一门关于数据资料的搜集、整理、分析和推理的科学。 数据挖掘和统计分析之间有明显的联系，它们有共同的目标，就是发现数据间隐藏的关系。 中华数据采矿协会会长谢邦昌认为硬要去区分数据挖掘和统计学的差异其实是没有太大意义 的。一般将之定义为数据挖掘技术的 CART、CHAID 或模糊计算等等理论方法，也都是由统计 学者根据统计理论所发展衍生，换另一个角度看，数据挖掘有相当大的比重是由高等统计学 中的多变量分析所支撑。但是为什么数据挖掘的出现会引发各领域的广泛关注呢？主要原因 在相较于传统统计分析而言，数据挖掘有下列几项特性： （1）处理大型数据更有优势，且无须太专业的统计背景去使用数据挖掘的工具； （2）数据挖掘技术不仅涉及统计学原理，而且包括数据库管理、人工智能、机器学习、模式 识别、以及数据可视化等技术。 （3） 数据挖掘核心是算法， 当然也考虑模型和可解释性问题， 但算法及可实现性是第一位的。 它所强调的首先是发现，其次才是解释。因而，数据挖掘并不过分依赖于严格的逻辑推理， 而是大量采用很多“黑箱”方法和本质上是探索性的方法。 （4）数据挖掘，作为很多学科交叉的结果继承了机器学习的“冒险”态度，比统计学更强调 实践性、探索性和灵活性。实际上，与现代科学中常见的“从假设出发演绎推理”的做法相 比，数据挖掘更多地是一个归纳过程。 数据挖掘不是为了替代传统的统计分析技术，相反它是统计学的延伸和扩展，但它并非是 统计学的一个分支，因为它还涉及了数据库管理、人工智能、机器学习能领域。数据挖掘的10暨南大学硕士学位论文出现为统计学提供了一个崭新的应用领域，也给统计学的理论研究提出了新的课题，它无疑 会推动统计学的发展。同时，虽然统计学不可能给出数据挖掘所有问题的答案，但它可以为 数据挖掘提供非常有参考价值的框架，能够极大地丰富数据挖掘的方法。1.4 数据挖掘的主要应用分析数据挖掘技术从一开始就是面向应用的。目前，在很多领域，数据挖掘(data mining)都 是一个很时髦的词，尤其是在如银行、电信、保险、交通、零售（如超级市场）等商业领域。 它的主要应用体现在以下几个方面: （1）科学研究应用 从科学研究方法学的角度看，随着先进的科学数据收集工具的使用，如观测卫星、遥感 器、DNA分子技术等，数据量非常大，传统的数据分析工具无能为力，因此必须有强大的智能 型自动数据分析工具才行。数据挖掘在天文学上有一个非常著名的应用系统:SKICAT，它是美 国加州理工学院喷气推进实验室(即设计火星探测器漫游者号的实验室)与天文科学家合作开 发的用于帮助天文学家发现遥远的类星体的一个工具。SKICAT既是第一个获得相当成功的数 据挖掘应用，也是人工智能技术在天文学和空间科学上第一批成功应用之一。利用SKICAT， 天文学家已发现了16个新的极其遥远的类星体.数据挖掘在生物学上的应用主要集中于分子 生物学特别是基因工程的研究上。近几年，通过用计算生物分子系列分析方法，尤其是基因 数据库搜索技术已在基因研究上作出了很多重大发现。 （2）市场营销 数据挖掘在营销业上的应用可分为两类:数据库营销(DatabaseMarketing)和购物篮分析 (BasketAnalysis)。数据库营销中，数据挖掘将用户进行分类，这样当一个新用户到来时， 通过顾客信息预测其购买的可能性，从而可以根据结果有针对性地对顾客进行推销。货篮分 析是分析市场销售数据以识别顾客的购买行为模式，例如:如果A商品被选购，那么B商品被购 买的可能性为95%，从而帮助确定商店货架的布局排放以促销某些商品，并且对进货的选择和 搭配上也更有目的性。这方面的系统有Opportunity Explorer，它可用于超市商品销售异常 情况的因果分析等;另外IBM公司也开发了识别顾客购买行为模式的一些工具Intelligent Miner和QUEST中的一部分。 （3）金融投资 典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般采用模型预测法(如11基于数据挖掘的分类和聚类算法研究及 R 语言实现神经网络或统计回归技术)。 数据挖掘可以通过对已有数据的处理， 找到数据对象之间的关系， 然后利用学习得到的模式进行合理的预测。这方面的系统有Fidelity StockSelector和LBS Capital Management。前者的任务是使用神经网络模型选择投资，后者则使用了专家系统、 神经网络和基因算法技术来辅助管理多达6亿美元的有价证券。 （4）欺诈甄别 银行或商业上经常发生诈骗行为，如恶性透支等，这些给银行和商业单位带未了巨大的 损失。进行诈骗甄别主要是通过总结正常行为和诈骗行为之间的关系，得到诈骗行为的一些 特性，这样当某项业务符合这些特征时，可以向决策人员提出警告。这方面应用非常成功的 系有FALCON系统和FAIS系统。FALCON是HNC公司开发的信用卡欺诈估测系统；它已被相当数量 的零售银行用于探测可疑的信用卡交易；FAIS则是一个用于识别与洗钱有关的金融交易的系 统，它使用的是一般的政府数据表单。 （5）产品制造 在产品的生产制造过程中常常伴随有大量的数据，如产品的各种加工条件或控制参数(如 时间、温度等控制参数)，这些数据反映了每个生产环节的状态，不仅为生产的顺利进行提供 了保证，而且通过对这些数据的分析，得到产品质量与这些参数之间的关系。这样通过数据 挖掘对这些数据的分析，可以对改进产品质量提出针对性很强的建议，而且有可能提出新的 更高效节约的控制模式，从而为制造厂家带来极大的回报。这方面的系统有CASSIOPEE(由 Acknosoft公司用KATE发现工具开发的)，已用于诊断和预测在制造波音飞机制造过程中可能 出现的问题。 （6）通信网络管理 在通信网络运行过程中，会产生一系列警告，这些警告有的可以置之不理，而有的如果 不及时采取措施则会带来不可挽回的损失。数据挖掘可以通过分析已有的警告信息的正确处 理方法以及警告之间的前后关系的记录，得到警告之间的序列模式规则，这些有价值的信息 可用于网络故障的定位检测和严重故障的预测等等任务中。这方面的系统有芬兰Helsinki大 学与一家远程通信设备制造厂家合作的TASA系统。 （7）Web 挖掘 上个世纪 90 年代网站热潮兴起，web 数据大量出现。由于 web 数据的特点非常适合进行 数据挖掘。因此，数据挖掘开始被广泛应用到 web 挖掘中，而且出现了一些专门从事 web 挖12暨南大学硕士学位论文掘的公司。比如 NetPerception 公司 1996 年 7 月成立，吸引了众多风险投资后，于 1999 年 4 月在 NASDAQ 上市。1.5 研究目的和意义2002 年 3 月，国家 973 信息技术与高性能软件基础规划项目首席科学家顾钧教授和中国 工程院院士李国杰教授提出，我国的软件开发要算法先行。这样，才能推动软件技术的研究 和开发，提高我国企业软件产品的技术竞争力和市场竞争力。算法是解决一个问题所要采取 的一系列步骤构成的计算方法。计算机求解一个实际问题的计算速度不仅仅与计算机的设备 水平有关，更取决于求解的算法技术水平的高低，而不同的计算方法使计算机的计算效率、 求解精度和对计算资源的需求有很大的差别。一个软件能否高效率地解决问题，其关键不再 编程技巧而在于解决问题的思路和方法，即算法。因此许多国家都高度重视对算法的研究， 已将如何提高算法的水平看作是一个提升国家技术竞争力的战略问题。 对于数据挖掘算法研究尤为重要，因为数据挖掘面对的是海量的数据，一个好的算法可 以大大提高计算速度，减少计算机资源的耗用。数据挖掘算法的研究是一个非常活跃的领域， 不断有新的算法提出。而分类、聚类算法研究又是数据挖掘算法研究的最活跃领域部分，分 类、聚类法也是数据挖掘过程中最常用的两种方法。所以对分类、聚类算法的研究显得尤为 重要。虽然目前研究分类、聚类算法的文章比较多，但大多数研究只停留在理论上的探讨， 并没有相应的算法实现。所以本文着重于算法实现的研究，在国内首次利用 R 语言实现数据 挖掘算法，因为 R 语言相对于其他一些软件有着免费、开放源代码、算法更新速度快等优点。1.6 论文研究框架论文第一章介绍数据挖掘的研究背景，研究目的和意义，及研究方法和工具。第二章主 要介绍比较分析各种分类算法及 R 语言实现， 具体介绍了基于距离分类的 KNN 算法； 基于决 策树方法的 C4.5 算法、CART 算法；基于神经网络的 BP 算法。第三章主要介绍比较分析各 种聚类算法及 R 语言实现。具体介绍了划分方法的 K-means、pam、clara 算法；层次方法的 AGNES、 DIANA 算法； 基于密度聚类方法的 DBSCAN 算法； 基于模型聚类方法的 COBWEB、 SOM 算法；基于模糊聚类方法的 FCM 算法。第四章实证分析主要以台湾教授蔡欣玲就护理 人员离职调查的数据为例，按数据挖掘的标准流程 CRISP-DM 进行分析，首先对数据作初步 统计分析，掌握护理人员的初步情况，再接着利用聚类方法来分析医院护理人员的离职意愿，13基于数据挖掘的分类和聚类算法研究及 R 语言实现然后利用分类方法建立预测模型，最后得出结论并提供政策参考。第五章对本文的研究情况 进行总结并展望。具体的研究框架见图 1.3绪论数据挖掘算法研究数据挖掘分类算法研究数据挖掘聚类算法研究基 于 距 离 算 法决 策 树 分 类神 经 网 分 类划 分 聚 类 算 法层 次 聚 类 算 法基 于 密 度 算 法模 糊 聚 类 算 法分类算法的 R 语言实现聚类算法的 R 语言实现实证分析结论与展望图 1.3论文研究框架1.7 数据挖掘算法的研究工具――R 语言1.7.1 R 语言简介 R 是一种为统计计算和图形显示而设计的语言环境，是贝尔实验室（Bell Laboratories）的14暨南大学硕士学位论文Rick Becker 、John Chambers 和 Allan Wilks 开发的 S 语言的一种实现，提供了一系列统计和 图形显示工具。S 语言也是目前比较流行的统计软件 S-PLUS 的基础。R 的创始人 Ross Ihaka 和 Robert Gentleman，由于这两位“R 之父”的名字都是以 R 开头，所以就命令为 R。 R 是一组数据操作，计算和图形显示工具的整合包。相对于其它同类软件，其特色在于： （1） 有效的数据处理和保存机制。 （2） 拥有一整套数组和矩阵操作运算符。 （3） 一系列连贯而又完整的数据分析中间工具。 （4） 图形统计可以对数据直接进行分析和显示，可用于多种图形设备。 （5） 一种相当完善、简洁和高效的程序设计语言。它包括条件语句、循环语句、用户自定 义的递归函数以及输入输出接口。 （6） R 是彻底面向对象的统计编程语言。 （7） R 和其它编程语言、数据库之间有很好的接口。 （8） R 是自由软件，可以光明正大的使用，但其功能不比任何其它同类软件差。 （9） R具有丰富的网上资源，更为重要一点的是R提供了非常丰富的程序包，除了推荐的标 准包外还有很多志愿者贡献的贡献包，可以直接利用这些包，大大提高工作效率。 1.7.2 R 语言与数据挖掘 数据挖掘工具可根据应用领域分为三类: （1） 通用单任务类。 仅支持KDD的数据采掘步骤， 并且需要大量的预处理和善后处理工作。 主要采用决策树、神经网络、基于例子和规则的方法，发现任务大多属于分类范畴。 （2）通用多任务类。可执行多个领域的知识发现任务，集成了分类、可视化、聚集、概 括等多种策略，如IBM公司的IntelligentMiner和Almaden研究中心开发的QUEST系统，SGI 公司开发的MineSet系统，加拿大SimonFraser大学开发的DBMiner系统，SPSS公司的 Clementine以及SGI公司的Mineset。 （3）专用领域类。特定领域的数据挖掘工具针对某个特定领域的问题提供解决方案。在 设计算法的时候，充分考虑到数据、需求的特殊性，并作了优化。现有的许多数据采掘系 统是专为特定目的开发的，用于专用领域的知识发现，对采掘的数据库有语义要求，挖掘 的知识和采用的方法也较单一，有些系统虽然能发现多种形式的知识，但基本器学习、统 计分析为主，计算量大。15基于数据挖掘的分类和聚类算法研究及 R 语言实现将目前典型的数据挖掘工具的特点整理成表1-1。表1-1 产品 供应商 典型的数据挖掘产品比较 特点描述 主要采用决策树， 自回归预测模型进行数据的分类和预测， 能够进行数据的获取、预处理等操作，并以图形方式表示。 集成了多种数据挖掘算法，具有面向对象的扩展的模块， 使用户算法和工具可以加到它的可视化编程环境中。 提供多种数据挖掘方法，它是基于数据立方体的联机分析 挖掘，包含多种有效的频繁模式挖掘功能和集成的可视化 分类方法 提供多种数据挖掘方法，具有多种统计分析工具。 集成多种数据挖掘算法，与 IBM DB/2 数据库紧密结合 具有强大的可视化工具、树可视化工具、图可视化工具和 多维数据分散可视化工具，用于实现数据和数据挖掘结果 的可视化。 集成多种数据挖掘算法，与 Oracle 数据库紧密结合 支持多种数据结构的挖掘，包括文本分析，预测，网络链 接分析，支持 Microsoft OLE DB for data mining. 集成的综合统计分析系统 基于 Java 的集成多种机器学习方法的系统， 具有开放式原 码的特点，能够集成用户的算法和工具，并具有跨平台的 优点CART&MARSSalfordClementineSPSSDBMiner Enterprise Miner Intelligent Miner MineSet Oracle Data Mining Suite Polyanalyst Statistic Data Miner WekaDBMinerSAS IBMSGIOracle Megaputer Intelligen ce Statsoft Universiy of Waicato数据挖掘的工具很多，但绝大部分产品的价格都是相对比较昂贵，而且除了 Weka 外其他 产品都不开放源代码。R 语言相对其他数据挖掘产品具有如下的优势： （1） R 语言是免费，可以不付任何费用而光明正大地使用。 （2） R 语言提供了丰富的数据挖掘算法程序包，比如 class 包可以实现 KNN、SOM 等分类 算法；cluster 包可以实现 pam、agnes、clara、mona 等算法；tree 包可以实现 CART 算 法等。 （3） R 语言可以通过 RWeka 程序包建立与 Weka 的连接， 可以自由地使用 Weka 软件的全部16暨南大学硕士学位论文算法。 （4） R 语言开放源代码，可以学习 R 语言经典源代码，在此基础上可以编写自己的算法。 这一点，对于科学研究者尤为重要。 （5）R 语言可以通过 RMySQL、ROracle、RODBC 等包分别与 MySQL、Oracle、ODBC 等 数据库建立连接。17基于数据挖掘的分类和聚类算法研究及 R 语言实现第 2 章 分类分析方法及 R 语言实现分类是数据挖掘的重要方法之一，它可以从内容丰富、蕴藏大量信息的数据库中提取描 述重要数据类的模型，用于作出智能的商务决策。分类的目的是学会一个分类函数或分类模 型（也称为分类器） ，该模型能把数据库中的数据项映射到给定类别中的某一个类别。分类可 用于预测，分类的输出是离散的类别值。分类具有广泛的应用，例如医疗诊断、信用卡系统 的信用分级、图像模式识别、植物分类、考古分类等。2.1 分类的定义、步骤及方法2.1.1 分类的定义 定义 2-1 给定一个数据库 D{t1，t2，…，tn}和一组类 C＝{C1，C2，…，Cm},分类问题就是 确定一个映射 f：D→C,每个元组 ti 被分配到一个类中。一个类 Cj 包含映射到该类中的所有元 组，即 Cj={ti|? (ti)=Cj,1≤i≤n,而且 ti ∈ D} 从上面的定义中,我们把分类看作是从数据库到一组类别的映射， 而且这些类是被事先定义 的，非交叠的。 2.1.2 分类的步骤 分类一般分为如下两个步骤[9]： 第一步，建立模型，描述预定的数据类集或概念集。通过分析由属性描述的数据库元组 来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号属性的属性确定。对于 分类，数据元组也称为样本、实例或对象。为建立模型而被分析的数据元组形成训练数据集。 训练数据集中的单个元组称为训练样本，并随机的由样本群选取。由于提供了每个训练样本 的类标号，该步也称为有指导的学习(即模型的学习在被告知每个训练样本属于哪个类的指导 下进行)。它不同于无指导的学习(如聚类)，那里每个训练样本的类标号是未知的，要学习的 类集合或数量也可能事先不知道。通常，学习模型用分类规则、决策树或数学公式的形式提 供。例如，给定一个顾客信用信息的数据库，可以学习分类规则，根据他们的信誉度优或良 来识别顾客(见图2.1)。这些规则可以用来为以后的数据样本分类，也能对数据库的内容提供 更好的理解。 第二步，使用模型进行分类(见图2.1)。首先评估模型(或分类方法)的预测准确率。保持 （holdout）方法是一种使用类标号样本测试集的简单方法。这些样本随机选取，并独立于训18暨南大学硕士学位论文练样本。模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比。对于每个测 试样本，将己知的类标号与该样本的学习模型类预测比较。模型的准确率如果根据训练数据 集评估，估计可能是乐观的，因此，一般使用测试集进行评估。如果认为模型的准确率可以 接受，就可以用它对类标号未知的数据元组或对象进行分类(这种数据在机器学习文献中也称 为未知的或先前未见到的数据)。例如，在图3.1中通过分析现有顾客数据学习得到的分类规则 可以用来预测新的或未来顾客的信誉度。图 2.1 数据分类过程：(a)学习：用分类算法分析训练数据。这里，类标号属性是 credit_rating，学习模型或分类法以分类规则形式提供。(b)分类：测试数据用于评 估分类规则的准确率。如果准确率是可以接受的，则规则用于新的数据元组分类2.1.3 分类器的构造方法 分类器的构造方法主要有统计方法、机器学习方法、神经网络方法等。统计方法主要包 括贝叶斯法和非参数法；机器学习方法主要包括决策树和规则归纳法；神经网络方法主要是 BP算法。本文将着重介绍以下几种分类方法：基于距离的分类方法、决策树分类方法、基于 神经网络分类方法。2.2 数据的预处理及分类方法的评估标准2.2.1 数据的预处理 在进行分类前，对数据的预处理可以提高分类预测的准确性、有效性和可伸缩性。分类 前一般要进行如下几种数据预处理：19基于数据挖掘的分类和聚类算法研究及 R 语言实现（1）数据清理：为了消除和减少数据噪声和处理缺失值的数据预处理。虽然大部分的分类算 法都会处理噪声和缺失值，但在进行分类对数据的清理可以减少学习时的混乱。 （2）相关性分析：数据中很多属性可能与分类预测任务不相关或是冗余的。因此在分类前进 行相关性分析可以删除学习过程中不相关的或冗余的属性，提高分类预测的效率和准确率。 （3）数据变换：分类前的数据变换主要有概念分层和规范化两种。概念分层就是把连续值属 性概化为离散的区间，压缩了原来的训练数据，学习时可以减少输入输出操作。规范化是将 给定属性的所有值按比例缩放，使得它们落入较小的指定区间，比如落入[0，1]内，可以防 止具有较大初始域的属性相对于具有较小初始域的属性权种过大，该方法常用于神经网络和 距离度量方法。 2.2.2 分类方法的评估标准 分类方法有很多种，它们各有所长，也各有所短。通过对它们进行研究和比较评估，一 来可以扬长避短，在特定情况下使用最优的分类方法，二来可以对其加以改进，使其性能得 到优化。可以根据下列标准对分类方法进行比较和评估： （1）准确率。指模型正确地预测新的或未见过的数据的类标号的能力，这也是模型的首要能 力。如果一个模型的分类准确率小于百分之五十，那么可以认为其结果是无价值的。在其他 条件等同的情况下，当然首选准确率高的分类方法。 （2）速度。指产生和使用模型的时间复杂度。产生模型的试验数据集通常是巨量的，因为一 般情况下其数量和分类准确率成正比。如果产生和使用模型的时间过长，将严重影响用户的 使用。 （3）稳健性。指给定噪声数据或具有空缺值的数据，模型正确预测的能力。现实中的数据库 通常有噪声，有时还很大。如果一个分类器不善于消除噪声的影响，将严重影响分类准确率。 （4）可伸缩性。指给定大量数据，有效的构造模型的能力。有些分类器在数据量很小的情况 下可以有效的构造模型，随着数据量的增大，其构造模型的能力显著下降，这最终也会影响 分类准确率。 （5）可解释性。指学习模型提供的理解和洞察的层次。2.3 基于距离的分类方法及R语言实现2.3.1 基于距离分类方法基本概念 定义2-2 给定一个数据库D{t1，t2，…，tn}和一组类C＝{C1，C2，…，Cm}。假定每个元组20暨南大学硕士学位论文包括一些数值型的属性值： i={ti1， i2， t t …， ik}， t 每个类也包含数值型属性值： Cj={Cj1， j2， C …， Cjk}，则分类问题是要分配每个ti到满足如下条件的类 Cj：dist(ti,Cj)≤dist(ti,Ck), ? Ck ∈ C,Ck≠Cj 其中,dist(ti,Cj)表示元组 ti 到类 Cj 的距离。 算法 2-1 阐述了简单的基于距离的方法，假定每个类 Ci 用类中心来表示，每个元组必须和各 个类的中心来比较，从而可以找出最近的类中心，得到确定的类标记，基于距离分类一个元 组的复杂性一般是 O(n)。 2.3.2 KNN 算法及 R 语言实现 （一） KNN 算法基本概念 K―最临近方法（k Nearest Neighbors,简称KNN）是实际运用中经常被采用的一种基于 距离的分类算法。KNN算法的基本思想：假定每个类包含多个训练数据，且每个训练数据都有 一个唯一的类别标记，计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的k 个训练数据，k个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。 （二）KNN算法代码 算法2-1 KNN算法 输入：训练数据T 最临近数目k 待分类的元组t 输出：输出类别c （1） N＝? （2） FOR each d ∈ T DO BEGIN （3） IF|N|≤k THEN （4） （5） （6） （7） N=N U {d}; ELSE IF ? u ∈ N such that dist(t,u)&dist(t,d) THEN BEGIN（8） N=N-{U} （9） N=N U {d} （10） END（11）END21基于数据挖掘的分类和聚类算法研究及 R 语言实现（12）C=class to which the most u ∈ N 在上述算法中T表示训练数据，假如T中有q个元组的话，则对一个元组进行分类的复杂度 为O(q)。如果对s个元组被分类的话，复杂度为O(sq）。由于必须对每个在训练数据中的元素 来比较，所以变成了复杂度为O(nq)的问题。鉴于训练数据是常数（尽管也许很大），复杂度 被看作O(n)。 （三） KNN算法R语言实现及实证分析 下面将用Fisher于1936年发表的鸢尾花（Iris）数据为例进行实证分析。数据是对3种鸢 尾花：setosa的鸢尾花、versicolor（杂色）的鸢尾花、virginica的鸢尾花各抽取一个容量 为50的样本， 测量其花萼长 （Sepal.Length ） 花萼宽 、 （Sepal.Width） 花瓣长 、 （Petal.Length） 、 花瓣宽（Petal.Width）。详细数据见附录1。 下面将用R语言class包的knn函数来做KNN算法分类，由于R中的datasets包已有Iris数据，以 及对应的3维数据Iris3，所以在R中可直接调用Iris3数据。决定每组取前30个数据为训练数 据，用来生成分类规则，取每组后20个数据为测试数据，测试分类的准确率。 程序如下：data(iris3) train &- rbind(iris3[1:30,,1], iris3[1:30,,2], iris3[1:30,,3]) #选前30个数据为训练数据 test &- rbind(iris3[31:50,,1], iris3[31:50,,2], iris3[31:50,,3])#剩下的为测试数据 cl &- factor(c(rep(&s&,30), rep(&c&,30), rep(&v&,30))) knn(train, test, cl, k = 3, prob=TRUE) attributes(.Last.value) #进行KNN算法分类分类结果见表2-1。表2-1类别\序号 setosa versicolor virginica 类别\序号 setosa versicolor 1 S C V 11 S C 2 S C V 12 S CKNN分类算法测试结果3 S C V 13 S C 4 S V V 14 S C 5 S C V 15 S C 6 S C V 16 S C 7 S C V 17 S C 8 S C V 18 S C 9 S C V 19 S C 10 S C V 20 S C22暨南大学硕士学位论文virginicaVVVVVVVVVV从测试结果来看，只有1例versicolor鸢尾花被错分到virginica鸢尾花上，准确率为98.3 ％，可见是相当高的。2.4 基于决策树分类及R语言实现2.4.1 决策树构造步骤 一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数 据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段， 决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题， 我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属 性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决 策树就对应着一组表达式规则。一棵典型的决策树如图4-3所示。它表示概念buys-computer （购买计算机），它预测AllElectronics的顾客是否可能购买计算机。内部节点用矩形表示， 而叶节点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。路径由根到 存放该样本预测的叶节点。决策树容易转换成分类规则。图2.2概念buys_computer的判定树，指出AllElectronics的顾客是否可能购买计算机。每个内部结点表示 一个属性上的测试，每个树叶结点代表一个类（buys_computer=yes,或buys_computer=no）2.4.2 决策树生成算法 决策树生成算法的流程图如图2.3 。 决策树生成的伪代码如下: 算法2-2 决策树生成算法23基于数据挖掘的分类和聚类算法研究及 R 语言实现ProcedureBuildTree(S,A) (S:训练样本集，A:分类属性集合) { 用样本集S创建节点N If A为空 then返回N If N纯(pure) then返回N else{ for 每一个属性A 估计该节点在A上的信息增益 选出最佳的属性A*, 将S分裂为Si， N长出分支 For each Si If Si为空 then返回叶节点 Else BuildTree(S,,A-A*) }由算法知，分割方法是决策树算法的关键。图2.3 决策树流程图根据分割方法的不同，目前决策树算法可分为两类：基于信息论（Information Theory）的 方法和最小Gini指标（Lowest Gini index）方法。对应前者算法主要有ID3、C4.5，对应后 者算法主要有CART、SLIQ和SPRINT。2.4.3 决策树修剪算法目前决策树修剪策略有三种：基于代价复杂度的修剪(Cost-Complexity Pruning)、悲观 修剪（Pessimistic Pruning）和MDL修剪（Minimum Description Length Pruning）。基于 代价复杂度的修剪使用了独立的样本集用于修剪，即与决策树生成过程所使用的样本集不同。 在很多情况下，特别是当训练集很小时，更期望将所有的样本既用于决策树的生成也用于决 策树的修剪。悲观修剪是Quinlan在1987年提出的，将所有的训练样本都用于决策树的生成与 修剪，经验表明，该方法产生的树太大并且有时精度不高，在实际使用过程用的较多的并且 效果较好的是MDL修剪。 2.4.4 C4.5算法及R语言实现 （一）C4.5算法基本概念24暨南大学硕士学位论文国际上最早，最有影响的决策树方法是Quinlan提出的ID3算法.ID3是一个典型的决策树 学习系统，它以信息熵作为分离目标评价函数，采用自顶向下不可返回的策略，搜出全部空 间的一部分，它确保决策树建立最简单，每次所做的测试数据最少。但由于ID3具有偏向于选 择属性较多的属性、学习简单的逻辑表达能力较差等缺点。Quilan在1993年提出了C4.5算法， 它既是ID3算法的后继，也成为以后诸多决策树算法的基础。 C4.5除了拥有ID3算法的功能外，还引入了新的方法和增加了新的功能。例如： （1） 用信息增益比例的概念替代信息增益 （2） 合并具有连续属性的值。 （3） 可以处理具有缺少属性值得训练样本。 （4） 通过使用不容的修剪技术以避免树的过渡拟合（overfitting） （5） K交叉验证 在应用于单机的决策树算法中，C4.5算法不仅分类准确率高而且是速度最快的。C4.5算 法在ID3的基础上加进了对连续型属性，属性值空缺情况的处理，对树剪枝也有了较成熟的 方法。算法2-4列出了C4.5算法的伪代码.其中，假设T代表当前样本集，当前候选属性集用 Tesattributelist表示。 （二）C4.5算法代码 算法2-3 C4.5算法（1） 创建根节点N; （2） IF T都属于同一类C，则返回N为叶节点，标记为类C； （3） IF T_attributelist为空或T中所剩的样本数少于某给定值 则返回N为叶节点，标记为T中出现最多的类； （4） FOR each T_attributelist中的属性计算信息增益率in （5） N的测试属性test_attribute=T_attributelist中具有最高信息增益率的属性； （6） IF测试属性为连续型 则找到该属性的分割阀值； （7） FOR each 由节点N长出的新叶节点{ IF 该叶节点对应的样本子集T’为空 则分裂该叶节点生成一个新叶节点，将其标记为T中出现最多的类；25基于数据挖掘的分类和聚类算法研究及 R 语言实现ELSE在该叶节点上执行C4.5formtree(T’,T’_attributelist),对它继续分 裂； } (8) 计算每个节点的分类错误，进行树剪枝。（三）C4.5算法的R语言实现及实证分析 要实现C4.5算法，R提供了一个程序包RWeka可以使用R语言来实现自由软件Weka的算法， Weka软件是用Java编写的用于数据挖掘机器学习的算法集，可以用来做数据的预处理、分类、 回归、聚类、关联规则以及可视化挖掘。 RWeka的使用条件是：R (&= 1.9.0), rJava (&= 0.3-6), grid 所以得事先安装rJava (&= 0.3-6), grid程序包。使用RWeka时推荐使用party (&= 0.8-0)程序包，该 包可以用拟合二叉树。Party包的使用条件是：(&= 2.0.1), survival, grid, modeltools (&= 0.2-3), coin (&= 0.3-8), zoo, sandwich (&= 1.1-1), strucchange我们将继续使用2.3.2中的Fisher于1936年发表的鸢尾花（Iris）数据为例。程序如下：library(RWeka) library(party) oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=0.3) data(iris) m1 &- J48(Species ~ ., data = iris) m1 table(iris$Species, predict(m1)) write_to_dot(m1) if(require(&party&, quietly = TRUE)) plot(m1) 结果分类规则如下： J48 pruned tree -----------------Petal.Width &= 0.6: setosa (50.0) Petal.Width & 0.6 | | | Petal.Width &= 1.7 | | Petal.Length &= 4.9: versicolor (48.0/1.0) Petal.Length & 4.926暨南大学硕士学位论文| | || || |Petal.Width &= 1.5: virginica (3.0) Petal.Width & 1.5: versicolor (3.0/1.0)Petal.Width & 1.7: virginica (46.0/1.0) : 5 9Number of LeavesSize of the tree :对应的决策树见图2.4表 2-2 观察\预测 setosa versicolor virginica C4.5 算法结果 setosa 50 0 0 versicolor 0 49 2 virginica 0 1 48图2.4 C4.5算法决策树从图2.4可以看出，第一分枝节点是属性petal.Width（花瓣宽），分成petal.width≤0.6 和petal.width&0.6两枝；在petal.width&0.6一枝上，第二分枝节点也是属性petal.Width， 分成petal.width≤1.7和petal.width&1.7两枝；在petal.width≤1.7一枝上，第三分枝节点是 属性petal.length(花瓣长)，分成petal.length≤4.9和petal.length〉4.9两枝；在 petal.length〉4.9一枝上，第四分枝节点是属性petal.Width，分成属性petal.Width≤1.5和 属性petal.Width&1.5两枝。表3-2行表示观察值的分类结果，列表示C4.5算法的预测结果， 从表3-2可以看出150的样本中出现错判的有3例，其中versicolor有1例错判为virginica， virginica有两例错判为versicolor，分类准确率为98％。 2.4.5 CART算法及R语言实现 （一）CART算法基本原理27基于数据挖掘的分类和聚类算法研究及 R 语言实现分类与回归树（Classification and Regression Tree,简称CART）算法是Breiman等人 在1984年提出来的一种算法。其数学模型在统计分析和数据挖掘技术方面是一个正在探索的 技术。按照CART的构建原理，可视之为数据分析的非参数过程，其特点是在计算过程中充分 利用二叉树的结构，即根节点包含所有样本，在一定的分割规则下根结点被分割为两个子节 点，这个过程又在子节点上重复进行，成为一个回归过程，直至不可再分成为叶节点为止。 该算法采用一种二分递归分割的技术，总是将当前样本集分割为两个子样本集，使得生成的 决策树的每个非叶节点都有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树.算法 3-5是CART算法的具体描述。其中，T代表当前样本集，当前候选属性集用Tattributelist表 示。与基于信息熵的理论不同，CART算法对每次样本集的划分计算GINI系数，GINI系数越小 则划分越合理。对样本集T,gini(T)=1-∑pj 其中Pj是类别J在T中出现的概率。若T被划分为s1 s2 T1,T2， 则此次划分的GINI系数为 ginisplit(T)= s gini(T1)+ s gini(T2)， 其中s为T中样本的个数，2S1，S2分别为T1,T2中的样本个数。对候选属性集中的每一个属性，CART算法计算该属性上梅种 可能划分的GINI系数，找到GINI系数最小的划分作为该属性上的最佳划分，然后比较所有候 选属性上最佳划分的GINI系数，拥有最小划分GINI系数的属性成为最终测试属性。与以前的 算法只为叶子节点分配类别不同，CART算法考虑到每个节点都有成为叶子节点的可能，对每 个节点(包括叶节点和非叶节点)都分配类别。分配类别的方法可以用当前节点中出现最多的 类别，也可以参考当前节点的分类错误或其它更复杂的方法。CART算法仍然使用后剪枝。在 树生成过程中，考虑到多展开一层就会有多一些的信息被发现，CART算法运行到不能再长出 分枝为止，从而得到一棵最大的决策树。然后CART对这棵超大的决策树进行剪枝。剪枝算法 使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出分类错误最小的子树 作为最终的分类模型。对于有些样本集，由于样本数太少而不能分出独立的测试样本集，则 CART算法采用一种称为交叉确定(crossvalidation)的剪枝方法。该方法将原始训练样本集分 成N份(假定每份的数据分布近似或相同)。N份中取第1份作为测试集，其余N-1份合并后用作 训练集，经过一次完整的建树和剪枝的过程，得到一棵局部决策树。然后选择第2份作为测试 集，将其余N-1份合并形成训练集，又得到一棵局部决策树。以此类推，直到N份样本集都做 了一次测试集为止。这样总共得到N棵局部决策树，综合这N棵局部决策树形成全局决策树。 这样形成的全局决策树在性能上非常近似于由包含所有样本的原始训练样本集而造成的过度 拟合问题。28暨南大学硕士学位论文（二）CART算法代码 CART算法描述 （1） 创建根节点N; （2） 为N分配类别； （3） IF T都属于同一类别OR T中只剩一个样本 则返回N为叶节点，为其分配类别； （4） FOR each T_attributelist 中的属性 执行该属性上的一个划分，计算此次划分的GINI系数； （5） N的测试属性test_attribute=T_attributelist中具有最小GINI系数的属性； （6） 划分T得T1、T2两个子集； （7） 调用cartformtree(T1); （8） 调用cartformtree(T2)； （三）CART算法的R语言实现及实证分析 我们将继续使用Fisher于1936年发表的鸢尾花（Iris）数据为例利用CART算法进行分类。 CART算法的程序包是tree，函数也是tree。程序如下：oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=0.7) library(tree) data(iris) ir.tr=tree(Species~.,iris) summary(ir.tr) plot(ir.tr);text(ir.tr) 分类规则如下： 节点), 分割点,记录数, 离差,y值（类别）, (y值概率)，*表示最终节点 1) root 150 329.600 setosa ( 0.33 0.33333 ) 2) Petal.Length & 2.45 50 0.000 setosa ( 1.00 0.00000 ) * #画决策树图 #对品种进行CART分类 #设置窗口参数3) Petal.Length & 2.45 100 138.600 versicolor ( 0.00 0.50000 ) 6) Petal.Width & 1.75 54 33.320 versicolor ( 0.41 0.09259 ) 9.721 versicolor ( 0.17 0.02083 ) 5.004 versicolor ( 0.00 0.20000 )* 0.000 versicolor ( 0.00 0.00000 )*2912) Petal.Length & 4.95 48 24) Sepal.Length & 5.15 5 25) Sepal.Length & 5.15 43基于数据挖掘的分类和聚类算法研究及 R 语言实现13) Petal.Length & 4.95 7) Petal.Width & 1.75 46 14) Petal.Length & 4.95 15) Petal.Length & 4.9567.638 virginica ( 0.33 0.66667 ) *9.635 virginica ( 0.74 0.97826 ) 6 40 5.407 virginica ( 0.67 0.83333 ) * 0.000 virginica ( 0.00 1.00000 ) *绘成相应的决策树见图2.5。图2.5CART树从图2.5可以看出,第一分枝节点是属性petal.length,分成petal.length&2.45和 petal.length≥2.45两枝;在petal.length ≥2.45一枝上按属性petal.width分成petal.width&1.75 和petal.width≥1.75两枝;在petal.width≥1.75一枝上按属性petal.length分成petal.length&4.95 和petal.length≥4.95两枝,而这两枝都属于virginica类;,同时在petal.width&1.75一枝上,按属性petal.length分成petal.length&4.95和petal.length≥4.95两枝,在petal.length≥4.95一枝都属于 virginica类, 而在petal.length&4.95一枝上按属性sepal.length分成sepal.length&5.15和sepal.length≥5.15两枝,这两枝都属于versicolor类。共分成6个叶节点，并且从分类结果看， 这6个叶节点从左到右的记录数分别是50、5、43、6、6、40。150例中错分的有4例，分类准 确率为97.33％。 2.5 基于神经网络分类方法及R语言实现 2.5.1 神经网络的基本原理 神经网络建立在有自学习能力的数学模型基础上，可以对复杂的数据进行分析，并完成 对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络的典型应用是建立分类 模型。神经网络将每一个连接看作一个处理单元(PE)，试图模拟人脑神经元的功能。神经网30暨南大学硕士学位论文络从经验中学习，常用于发现一组输入数据和一个结果之间的未知联系。同其它方法一样， 神经网络首先检测数据中存在的模式，再对从数据中发现的关系进行概括，然后给出预测结 果。神经网络由于能对复杂过程进行预测而受到了特别的关注。处理单元采用一系列数学函 数，通过汇总和转换对数据进行处理。一个处理单元的功能有限，但若干个处理单元连接起 来形成系统后，就可以创建一个智能模型。处理单元可以许多种不同的方式互连，为了更精 确地拟合需要为之建立模型的数据，它们可被反复训练若干次，成百次，甚至上千次。处理 单元要和输入输出单元连接起来。在网络训练过程中，需对输入单元和输出单元之间的连接 强度(即权值)进行修改。某一个连接强度的提高或减弱根据它对产生某一个结果的重要性进 行的。连接强度依赖于在反复训练过程中赋予它的权值。训练过程采用一种称为学习规则的 数学方法调节权值。神经网络的训练是根据历史样本数据反复进行的。训练过程中，处理单 元对数据进行汇总和转换，它们之间的连接被赋以不同的权值。也就是说，为了对每一个样 本的结果变量进行预测，一个网络要尝试各种不同的方案。当输出结果在指定的精度级别上 与已知结果吻合，或满足其它的结束准则时，网络的训练就不再进行。图 2.6一个多层前馈神经网络。训练样本 X={x1,x2,...,xi}馈入输入层。每层之间存在加权连接；其中，wij 表示由某层的单元 j 到前一层的单元 i 的权图2.6所示的神经网络是一个前馈网络，反向传播(BP)算法是一个用于前演网络的典型的 学习算法。在此神经网络中，每一个处理单元都接受许多的输入，而只产生一个输出，该输 出是所有输入权值和的非线性函数。赋给每一输入的权值是在训练过程(通常采用反向传播或 共扼梯度法)中通过将网络输出和目标结果进行比较得到的。将你想要网络产生的结果和网络 输出的结果进行比较，它们之间的差额即可用于调整权值。为了提高模型的精度需要反复调 节连接权值。隐层结点的数量也可以调节，而且，事实上也可以有多个隐含结点。输入层、 隐层和输出层结点的数量以及连接这些结点的权值的调节算法决定了神经网络的复杂性。一 般说来，需要在神经网络复杂性、精确度和建立神经网络模型所花费的时间之间进行综合考31基于数据挖掘的分类和聚类算法研究及 R 语言实现虑。由于隐层结点数量和连接权值对神经网络来说是至关重要的，所以有许多方法可用于确 定合适的隐层结点数量和调节权值。 2.5.2 神经网络的优缺点 神经网络的最大优点是它能精确地对复杂问题进行预测。在与其它方法进行的精度对比 测试中，神经网络的精确度是比较高的。 神经网络方法也有一些缺点： 第一，神经网络虽然在预测方面有用但却难于理解。诚然，早期的神经网络工具的确象 被指责的那样，是一种“黑盒子”预测引擎，但当今市场上的新型神经网络工具却有了明显 的改进。 第二，神经网络易于受训练过度的影响。如果对具有很强学习功能的神经网络用支持这 种功能的少量数据进行训练，开始时正如我们希望的那样，网络学习的是数据中的一般趋势， 但此后网络却不断地学习训练数据中非常具体的特征，这不是我们所希望的。这样的网络由 于记住了训练数据，缺乏概括能力。 如今的商用神经网络己有效地解决了这些问题。通过定期检查测试数据集的结果可以检 测训练过度问题。训练过程初期，训练和测试数据的误差都比较小。然而，如果网络的功能 超过了预定功能或是训练数据太小，这种情况就不再继续下去。在训练过程中，如果测试数 据开始产生错误结果，即使训练数据的结果仍然在不断提高，那么，即说明出现了训练过度. 另一个是神经网络的训练速度问题。构造神经网络时要求对其训练许多次，这意味着要获得 精确的神经网络，需要花费许多 时间。然而，所有的回归技术要收敛于某一结果都需要相当 的时间。而且，尽管BP网络较慢，但采用共扼梯度法可大大加快其训练的速度。 2.5.3 BP算法的R语言实现及实证分析 下面继续以Fisher于1936年发表的鸢尾花（Iris）数据为例，每个类别随机抽取25个样本 作为训练数据，然后以剩下的数据作为测试数据对分类的结果进行测试。可以使用nnet包做 前馈神经网络。 R语言程序如下：library(nnet) data(iris3) ir &- rbind(iris3[,,1],iris3[,,2],iris3[,,3])32暨南大学硕士学位论文targets &- class.ind( c(rep(&s&, 50), rep(&c&, 50), rep(&v&, 50)) ) samp &- c(sample(1:50,25), sample(51:100,25), sample(101:150,25)) ir1 &- nnet(ir[samp,], targets[samp,], size = 2, rang = 0.1, decay = 5e-4, maxit = 200) test.cl &- function(true, pred){ true &- max.col(true) cres &- max.col(pred) table(true, cres) } test.cl(targets[-samp,], predict(ir1, ir[-samp,])) 或者： ird &- data.frame(rbind(iris3[,,1], iris3[,,2], iris3[,,3]), species = c(rep(&s&,50), rep(&c&, 50), rep(&v&, 50))) ir.nn2 &- nnet(species ~ ., data = ird, subset = samp, size = 2, rang = 0.1, decay = 5e-4, maxit = 200) table(ird$species[-samp], predict(ir.nn2, ird[-samp,], type = &class&)) #对样本以外的数据的测试 #抽取25个样本分类结果整理成表2-3表2-3 基于神经网络BP算法的分类结果表2-3的行表示实际的分类情况，列表示观察\预测versicolor 24 0 1setosa 0 25 0virginica 1 0 24利用神经网络方法得出的预测分类结果。 versicolor 从表2-3可以看出75例中， 分类出错的是2 例，其中1例versicolor类被错判为 virginica类，1例virginica类被错判为 versicolor类，分类准确率是97.3％。 setosa virginica33基于数据挖掘的分类和聚类算法研究及 R 语言实现第3章 聚类分析方法及R语言实现3.1聚类分析基本概念及要求 3.1.1聚类分析基本概念聚类分析是数据挖掘的一项重要功能，而聚类算法是数据挖掘研究领域中一个非常活跃的 研究课题。聚类是把一组对象按照相似性归成若干类别，即“物以类聚”。它的目的是使得 属于同一类别的对象之间的距离尽可能的小，而不同类别的对象间的距离尽可能的大。聚类 的定义可以如下表示： 定义3-1 聚类分析的输入可以用一组有序对（X，s）或（X，d）表示，这里X表示一组样本， s和d分别是度量样本间相似度和相异度（比如距离）的标准。聚类分析的输出是一个分区， 若C＝{C1,C2,…,Ck},其中Ci（i＝1，2，…，k）是X的子集，如下所示： C1 U C2 U … U Ck=XC1∩C2=?,i≠j C中的成员C1,C2,…,Ck称为类，每一个类都是通过一些特征描述的，通常有如下集中表示方式： （1） 通过类的中心或类的边界点表示一个类。 （2） 使用聚类树中的结点图形化地表示一个类。 （3） 使用样本属性的逻辑表达式表示类。 聚类分析就是使用聚类算法来发现有意义的聚类，它的主要依据是把相似的样本归为一 类，而把差异大的样本区分开来，这样所生成的簇是一组数据对象的集合，这些对象与同一 个簇中的对象彼此相似，而与其他簇中的对象彼此相异。在许多应用中可以把一个簇中的数 据对象当做一个整体来对待。聚类分析是一种重要的人类行为，很小的时候人就可以通过不 断的改进下意识中的聚类模式来学会如何区分不同的动物或动物和植物。聚类分析已经广泛 应用在许多领域中，包括模式识别、数据分析、图象处理以及市场研究等。通过聚类人们能 够识别密集和稀疏的区域，因而发现全局的分布模式以及数据属性之间的有趣的相互联系。 作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每 个簇的特点，集中对特定的簇做进一步的分析。聚类分析也可以作为其他方法(如特征和分类 等)的预处理.34暨南大学硕士学位论文目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型，聚类的目的和应用。 如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能 揭示的结果。大体上，按照聚类算法的主要思路可以划分为如下几类：划分方法（partitioning 、层次方法（hierarchical methods） 、基于密度的方法（Density－based Methods） 、基 methods） 于模型的方法（model-based methods）等。一些聚类算法集成了多种聚类方法的思想，所以有 时将某个给定的算法划分为属于某类聚类方法是很困难的。此外，某些应用可能有特定的聚 类标准，要求综合多个聚类技术。3.1.2数据挖掘对聚类分析方法的要求数据挖掘技术的一个突出特点是处理巨大的、复杂的数据集，这对聚类分析技术提出了特 殊的挑战，要求算法具有可伸缩性、处理不同类型属性的能力、处理高维数据的能力等。具 体地说，数据挖掘对聚类的特殊要求如下[9]： （1）可伸缩性。许多聚类方法在小于1000个数据对象的小数据集合上工作得很好；但是，一 个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能导致较大 偏差。 （2）处理不同类型属性的能力。许多聚类方法只能聚类数值型数据。但是，在数据挖掘领域， 数据类型是多样的。 （3）用于决定输入参数的领域知识最少。许多聚类方法在聚类分析中要求用户输入一定的参 数，例如希望产生类的数目，而且聚类结果对于输入参数十分敏感。参数通常很难确定，特 别是对于包含高维对象的数据集来说，更是如此。要求用户输入参数不仅加重了用户的负担， 也使得聚类的质量难以控制。 （4）发现任意形状的聚类。许多聚类方法基于欧氏距离来决定聚类。基于这样的距离度量的 算法趋向于发现具有相似此尺度和密度的球状簇。 （5）处理噪声数据的能力。绝大多数的现实世界中的数据库都包含了异常值、缺失值或错误 的数据。有些聚类方法对于这样的数据较为敏感，可能导致低质量的聚类结果。 （6）对于输入数据的顺序不敏感。有些聚类方法对于输入数据的顺序是敏感的。例如，同一 个数据集合，当以不同的顺序提交给同一个方法时，可能生成差别很大的聚类结果。 （7）高维性。一个数据库或者数据仓库可能包含若干维或者属性。许多聚类方法擅长处理低 维的数据，可能只涉及两到三维。在高维空间中聚类数据对象是非常有挑战性的，特别是这35基于数据挖掘的分类和聚类算法研究及 R 语言实现样的数据可能非常稀疏，而且高度偏斜。 （8）基于约束的聚类。现实世界中的应用可能需要在各种约束条件下进行聚类。要找到既满 足特定的约束，又具有良好聚类特性的数据分组是一项具有挑战性的任务。 （9）可解释性和可用性。用户希望聚类结果是可解释的、可理解的、可用的。也就是说，聚 类可能需要和特定的语义解释和应用相联系。3.2聚类分析的数据类型及处理方法本节主要介绍聚类分析中经常出现的数据类型，以及在聚类之前如何对其进行预处理。许 多基于内存的聚类算法选择如下两种有代表性的数据结构： 数据矩阵（Data matrix，或称为对象属性结构） 表示数据对象数目，p 表示变量个数，这 ：n 是 n*p 维（n 个对象 p 个属性）的矩阵。?X ? ? ?XX11 X1221… … … …X1p X2p…X22…… n1Xn2Xnp? ? ? ?相异度矩阵（dissimilarity matrix，或称为对象-对象结构） ：存储 n 个对象两两之间的近 似性，表现形式是一个 n*n 维的矩阵。? d(2,1) 0 ? ? ? d(n,1) d(n,2)… …00… … … …0 0…0? ? ? ?其中 d(i,j)是对象 i 和对象 j 之间相异性的量化表示，通常它是一个非负的数值，当对 象 i 和 j 越相似， 其值越接近 0； 两个对象越不同， 其值越大。 而且有 d(i,j)=d(j,i)， d(i,i)=0。 数据矩阵经常被称为二模（two-mode）矩阵，而相异度矩阵被称为单模（one-mode）矩 阵。这是因为前者的行和列代表不同的实体，而后者的行和列代表相同的实体。许多聚类算 法以相异度矩阵为基础。如果数据是用数据矩阵的形式表现的，在使用该类算法之前要将其 转化为相异度矩阵。下面将讨论各种不同类型的数据的相异度的衡量方法。 （一） 区间尺度变量（Interval-Scaled Variable） 区间标度变量是一个线性标度的连续度量。 典型的例子包括重量和高度， 经度和纬度坐标， 以及大气温度。 选用的度量单位将直接影响聚类分析的结果。 例如， 将高度的度量单位由 “米” 改为“英尺” ，或者将重量的单位由“千克”改为“磅” ，可能产生非常不同的聚类结构。一36暨南大学硕士学位论文般而言，所用的度量单位越小，变量可能的值域就越大，这样对聚类结果的影响也越大。为 了避免对度量单位选择的依赖，数据应当标准化。标准化度量值试图给所有的变量相等的权 重。当没有关于数据的先验知识时，这样做是十分有用的。但是，在一些应用中，用户可能 想给某些变量较大的权重。例如，当对篮球运动员进行聚类时，我们可能愿意给高度变量较 大的权重。 为了实现度量值的标准化，一种方法是将原来的度量值转换为无单位的值。给定一个变量 f 的度量值，可以进行如下的变换： 1． 计算平均的绝对偏差（mean absolute deviation）Sf:1 sf= (|x1f-mf|+|x2f-mf|+…+|xnf-mf|) n（3.1）这里的 x1f,…,xnf 是 f 的 n 个度量值，mf 是 f 的平均值，即1 mf =n(|x1f +x2f+…+xnf)2． 计算标准化的度量值，或 z-score：zif =(xifCmf)/sf(3.2)这个平均的绝对偏差 sf 比标准的偏差对于异常值有 更好的稳健性。在计算平均绝对偏差时， 度量值与平均值的偏差没有被平方，因此异常值的影响在一定程度上被减小了。虽然存在更 好的对偏差的度量方法，例如中值绝对偏差（median absolute deviation） ，但采用平均绝 对偏差的优点在于孤立点的 z-score 值不会太小，因此孤立点仍可以被发现。 在标准化处理后，对象间的相异度（或相似度）是基于对象间的距离来计算的。最常用的 距离度量方法是欧几里得距离，它的定义如下：d(i,j)=（3.3）这里的 i=（xi1，xi2，…,xip）和 j=(xj1,xj2,…xjp)是两个 p 维的数据对象。 另一个著名的度量方法是曼哈顿距离，其定义如下：d（i，j）=|xi1-xj1|+|xi2-xj2|+…+|xip-xjp|(3.4)上面的两种距离度量方法都满足对距离函数的如下数学要求：1． d（i，j）≥0：距离是一个非负的数值。 2． d（i，i）=0：一个对象与自身的距离是 0。 3． d（i，j）=d（j，i） ：距离函数具有对称性。37基于数据挖掘的分类和聚类算法研究及 R 语言实现4． d（i，j）≤d（i，h）+d（h，j） ：从对象 i 到对象 j 的直接距离不会大于途径任何其他对象的距离。 明考斯基距离是欧几里得距离和曼哈顿距离的概化，它的定义如下：d（i，j）=（|xi1-xj1|q+|xi2-xj2|q+…+|xip-xjp|q）1/q(3.5)这里的 q 是一个正整数。当 q=1 时，它表示曼哈顿距离；当 q=2 表示欧几里得距离。 如果对每个变量根据其重要性赋予一个权重，加权的欧几里得距离可以计算如下：d（i，j）= w1|xi1-xj1|2+w2|xi2-xj2|2+…+wp|xip-xjp|2(3.6)（二） 二元变量（binary variable） 一个二元变量只有两个状态：0 或 1，0 表示该变量为空，1 表示该变量存在。例如，给出 一个描述病人的变量 smoker，1 表示病人抽烟，而 0 表示病人不抽烟。像处理区间标度变量 一样来对待二元变量会误导聚类结果，所以要采用特定的方法来计算其相异度。 如果假设所有的二元变量有相同的权重， 我们得到一个两行两列的可能性表 8.1。 在表中， q 是对对象 i 和 j 值都为 1 的变量的数目，r 是在对象 i 中值为 1，在对象 j 中值为 0 的变量 的数目，s 是在对象 i 中值为 0，在对象 j 中值为 1 的变量的数目，t 是在对象 i 和 j 中值都 为 0 的变量的数目。变量的总数是 p，p=q+r+s+t。表 3-1 二元变量的分布表对象 j 1 0 求和 1 q r q+r 对象 i 0 s t s+t 求和 q+s r+t p 如果它的两个状态有相同的权重,那么该二元变量是对称的，也就是两个取值 0 或 1 没有 优先权。例如，属性“性别”就是这样的一个例子，它有两个值： “女性”和“男性” 。基于 对称二元变量的相似度称为恒定的相似度，即当一些或者全部二元变量编码改变时，计算结 果不会发生变化。对恒定的相似度来说，评价两个对象 i 和 j 之间相异度的最著名的系数是 简单匹配系数，其定义如下： d(i,j)=q+r+s+tr+s（3.7）如果两个状态的输出不是同样重要，那么该二元变量是不对称的。例如一个疾病检查的肯 定和否定的结果。根据惯例，我们将比较重要的输出结果，通常也是出现几率较小的结果编38暨南大学硕士学位论文码为 1（例如，HIV 阳性） ，而将另一种结果编码为 0（例如 HIV 阴性） 。给定两个不对称的二 元变量，两个都取值 1 的情况（正匹配）被认为比两个都取值 0 的情况（负匹配）更有意义。 因此，这样的二元变量经常被认为好像只有一个状态。基于这样变量的相似度被称为非恒定 的相似度。对非恒定的相似度，最著名的评价系数是 Jaccard 系数，在它的计算中，负匹配 的数目被认为是不重要的，因此被忽略。 d(i,j)=q+r+sr+s（3.8）当对称的和非对称的二元变量出现在同一个数据集中，在描述的混合变量方法可以被应用。 （三） 名义变量（Nominal Variable） 名义变量是二元变量的推广，它可以具有多于两个的状态值。例如，map_color 是一个名义 变量，它可能有五个值：红色 ,黄色，绿色，粉红色，和蓝色。假设一个名义变量的状态数 目是 M。这些状态可以用字母，符号，或者一组整数（如 1，2，…,M）来表示。要注意这些 整数只是用于数据处理，并不代表任何特定的顺序。 名义变量两个对象 i 和 j 之间的相异度可以用简单匹配方法来计算： d(i,j)= pp-m(3.9)这里 m 是匹配的数目，即对 i 和 j 取值相同的变量的数目；而 p 是全部变量的数目。我们可 以通过赋权重来增加 m 的影响，或者赋给有较多状态的变量的匹配更大的权重。通过为每个 状态创建一个二元变量，可以用二元变量来表示名义变量。对一个有特定状态值的对象，对 应该状态值的二元变量值置为 1， 而其余的二元变量值置为 0。 例如， 为了对名义变量 map_color 进行编码，对应于上面所列的五种颜色分别创建一个二元变量。如果一个对象是黄色，那么yellow 变量被赋值为 1， 而其余的四个变量被赋值为 0。 对于这种形式的编码， 可以采用在 4.2.2节中讨论的方法来计算相异度。 （四）序数型变量（Ordinal variable） 一个离散的序数型变量类似于名义变量，除了序数型变量的 M 个状态是以有意义的序列排 序的。序数型变量对记录那些难以客观度量的主观评价是非常有用的。例如，职业的排列经 常按某个顺序，例如助理，副手，正职。一个连续的序数型变量看起来象一个未知刻度的连 续数据的集合，也就是说，值的相对顺序是必要的，而其实际的大小则不重要。例如，在某 个比赛中的相对排名（例如金牌，银牌，和铜牌）经常比事实的度量值更为必需。将区间标39基于数据挖掘的分类和聚类算法研究及 R 语言实现度变量的值域划分为有限个区间，从而将其值离散化，也可以得到序数型变量。一个序数型 变量的值可以映射为排序。例如，假设一个变量 f 有 Mf 个状态，这些有序的状态定义了一个 序列 1，…,Mf。 在计算对象的相异度时，序数型变量的处理与区间标度变量非常类似。假设 f 是用于描述 n 个对象的一组序数型变量之一，关于 f 的相异度计算包括如下步骤： (1)第 i 个对象的 f 值为 xif，变量 f 有 Mf 个有序的状态，对应于序列 1，…，Mf。用对应 的 rif 代替 xif，rif∈{1,…,Mf}。 (2)既然每个序数型变量可以有不同数目的状态，我们经常必须将每个变量的值域映射到 [0,1]上，以便每个变量都有相同的权重。这一点可以通过用 zif 代替 rif 来实现。r C1 Zif= if Mf-1(3.10)(3)相异度的计算可以采用 4.2.1 节所描述的任意一种距离度量方法， 采用 zif 作为第 i 个 对象的 f 值。 （五） 比例标度变量（Ratio-Scaled Variable） 比例标度型变量在非线性的刻度取正的度量值，例如指数，近似地遵循如下的公式AeBt 或 Ae-Bt（3.11）这里的 A 和 B 是正的常数。典型的例子包括细菌数目的增长，或者放射性元素的衰变。 目前计算用比例标度型变量描述的对象之间的相异度有三种方法： （1） 采用与处理区间标度变量同样的方法。但是，这种作法通常不是一个好的选择，因为刻度可能被扭曲了。 （2） 对比例标度型变量进行对数变换，例如对象 i 的 f 变量的值 xif 被变换为 yif，yif=log(xif)。变换得到的 yif 值可以采用在 3.2.1 节中描述的方法来处理。需要注意的是，对一些比例标度型变量，可以采用对数-对数或者其他形式的变换，具体的做法 取决于定义和应用。 （3） 将 xif 看作连续的序数型数据，将其秩作为区间标度的值来对待。（六）混合类型变量 前面讨论了计算由同种类型变量描述的对象之间的相异度的方法， 变量的类型可能是区间 标度变量,对称二元变量,不对称二元变量,名义变量,序数变量或者比例标度变量。但是在许多 真实的数据库中，对象是被混合类型的变量描述的。一般来说，一个数据库可能包含上面列40暨南大学硕士学位论文出的全部六种类型。 关于计算用混合类型变量描述的对象之间的相异度，一种方法是将变量按类型分组，对每 种类型的变量进行单独的聚类分析。如果这些分析得到兼容的结果，这种方法是可行的。但 是，在实际的应用中，这种情况是不大可能的。 另一个更可取的方法是将所有的变量一起处理，只进行一次聚类分析。一种技术将不同类 型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间[0,1]上。 假设数据集包含 p 个不同类型的变量，对象 i 和 j 之间的相异度 d(i,j)定义为 ∑δij(f)dij(f)d(i,j) =f=1 p p(3.11)(f)∑δij f=1如果 xif 或 xjf 缺失（即对象 i 或对象 j 没有变量 f 的度量值） ，或者 xif =xjf=0，且变量 f 是不对 称的二元变量，则指示项 δij(f)=0；否则，指示项 δij(f)=1。变量 f 对 i 和 j 之间相异度的计算方 式与其具体类型有关：(1)如果 f 是二元或名义变量：如果 xif =xjf，dij(f) =0；否则 dij(f)=1。jf (2)如果 f 是区间标度变量：dij(f)= max x if -min x ，这里的 h 包含了所有有变量 f 值的对象。 h hf h hf|x -x |(3)如果 f 是序数型或者比例标度型变量：计算秩 rif 和 zif=rifC1 ，将 zif 作为区间标度变量值对 Mf-1待。 这样，当描述对象的变量是不同类型时，对象之间的相异度也能够进行计算。3.3 划分聚类方法及 R 语言实现3.3.1 传统划分聚类方法 3.3.1.1k-means算法 (一) k-means基本原理 k-means算法以k为参数，把n个对象分为k个聚类，以使聚类内具有较高的相似度，而且 聚类间的相似度较低。相似度的计算是根据一个聚类中对象的平均值来进行。k-means算法的 处理流程如下:首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。 对剩余的每个对象，根据其与各个聚类中心的距离将它赋给最近的簇。然后重新计算每个簇41基于数据挖掘的分类和聚类算法研究及 R 语言实现的平均值作为聚类中心进行聚类。这个过程不断重复，直到准则函数收敛。通常，采用平方 误差准则，其定义如下:E = ∑ ∑ ( p ? mi ) 2i =1 p = Ci k其中，E为数据库中所有对象与相应聚类中心的均方差之和，P为代表对象空间中的一个点， mi为聚类Ci的均值(p和mi均是多维的)。该式所示聚类标准旨在使所有获得的聚类有以下特点: 各类本身尽可能的紧凑，而各类之间尽可能的分开。下面给出了k-means过程的概述[11]。 （二）k-means算法代码 算法3-1 根据聚类中的均值进行聚类划分的k-means算法。输入:聚类个数k，以及包含n个数据对象的数据库 输出:满足平方误差准则最小的k个聚类 处理流程: (1)从n个数据对象任意k个对象作为初始簇中心。 (2)循环下述流程(3)到(4)，直到每个聚类不再发生变化为止。 (3)根据每个簇中对象的均值(中心对象)，计算每个对象与这些中心对象的距离，并根据最小 距离重新对相应对象进行划分。 (4)重新计算每个(有变化)簇的均值。 该算方法过程的示例见图3.1。 （三）k-means算法评价 这个算法尝试找出使平方误差函数值最小的k个划分。 当结果是密集的， 而簇与簇之间区别 明显时，它的效果较好。对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复 杂度是O(nkt)，其中，n是所有对象的数目，k是簇的数目，t是迭代的次数。通常地，k&n， 且t&n。 这个算法经常以局部最优结束。 但是， k-means方法只有在簇的平均值被定义的情 况下才能使用。这可能不适用于某些应用， 例如涉及有分类属性的数据，要求用户必须 事先给出k(要生成的簇的数目)可以算是该 方法的一个缺点。这可能不适用于某些应用，图3.1 K-means迭代图例42暨南大学硕士学位论文例如涉及有分类属性的数据，要求用户必须事先给出k(要生成的簇的数目)可以算是该方法的 一个缺点。k-means方法不适合于发现非凸面形状的簇，或者大小差别 很大的簇.而且，它对 于“噪声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。k-means 方法有很多变种。它们可能在初始k个平均值的选择、相异度的计算和计算聚类平均值的策略 上有所不同。经常会产生较好的聚类结果的一个有趣策略是首先采用层次的凝聚算法决定结 果簇的数目，并找到一个初始的聚类，然后用迭代重定位来改进聚类结果。k-menas方法的一 个变体是k-模(k-modes)方法，它扩展了k-means方法，用模来代替类的平均值。采用新的相 异性度量方法来处理分类对象，采用基于频率的方法来修改聚类的模。k-means和k-modes方 法可以综合起来处理数值类型和分类类型属性的 数据，这就是k一原型方法。 3.3.1.2 k-medoids算法 （一）k-medoids基本原理 由于k-means算法中的各聚类按均值计算，一个异常数据的取值可能会很大，从而会影响 数据分布的估计，因此k-means算法对异常值很敏感。为此设想利用medoid来作为一个参考点 代替k-means算法中的各聚类的均值作为聚类中心。从而可以根据各对象与各参考点之间的距 离(差异性)之和最小化的原则，继续应用划分方法。这就构成了k-medoids算法。k-medoids 聚类算法的基本策略是:首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象 的距离分配给最近的一个簇，然后反复地用非代表对象来代替代表对象，以改进聚类的质量。 （二）k-medoids算法代码 算法3-2 根据聚类的中心对象(聚类代表)进行聚类划分的k-medoids算法。输入:聚类个数k，以及包含n个数据对象的数据库 输出:满足基于各聚类中心对象的方差最小标准的k个聚类 处理流程： (1)从n个数据对象任意选择k个对象作为初始聚类(中心)代表 (2)循环(3)到(5)直到每个聚类不再发生变化为止。 (3)依据每个聚类的中心代表对象，以及各对象与这些中心对 象间距离，并根据最小距离重新。对相应对象进行划分。 (4)任意选择一个非中心对象Orandom；计算其与中心对象Qj交换图3.2 k-medoids过程图例43基于数据挖掘的分类和聚类算法研究及 R 语言实现的整个成本S。 (5)若S为负值则交换Orandom与Qj以构成新聚类的k个中心对象。 （三）PAM算法简介 PAM(Partitioning around Medoid，围绕中心点的划分)是最早提出的k-medoids算法之一。 它试图对n个对象给出k个划分。最初随机选择k个中心点后，该算法反复地试图找出更好的中 心点。所有可能的对象对被分析，每个对中的一个对象被作是中心点，而另一个不是。对可 能的各种组合， 估算聚类结果的质量。 一个对象Oj被可以产生最大平方误差值减少的对象代替。 在一次迭代中产生的最佳对象的集合成为下次迭代的中心点。当n和k的值较大时，这样的计 算代价相当高。当存在“噪声”和孤立点数据时，k-medoids方法比k-means方法更稳健，这 是因为中心点不像平均值那么容易极端数据影响。 但是， k-medoids方法的执行代价比k-means 方法高。此外这两种方法都要求用户指定结果簇的数目k。 3.3.2 改进的划分聚类方法 典型的k-medoids划分算法，如PAM，对小的数据集合非常有效，但对大的数据集合没有良 好的可伸缩性。为了处理较大的数据集合，可以采用一个基于选择的方法CLARA(Clustering LARge Applications)。CLARA的主要思想是:不考虑整个数据集合，选择实际数据的一小部分 作为数据的样本，然后用PAM方法从样本中选择中心点。如果样本是以随机形式选取的，它应 当足以代表原来的数据集合。从中选出的代表对象(中心点)很可能与从整个数据集合中选出 的非常近似CLARA抽取数据集合的多个样本，对每个样本应用PAM算法，返回最好的聚类结果 作为输出。CLARA每步迭代的复杂度现在是O(ks2+k(n-k))),s是样本的大小，k是簇的数目，而 n是所有对象的总数.可见CLARA的有效性取决于样本的大小。要注意PAM在给定的数据集合中 寻找最佳的k个中心点，而CLARA在抽取的样本中寻找最佳的k}