基于数据挖掘的分类和聚类算法研究及R语言实现

暨南大学 硕士学位论文

题名（中英对照）：基于数据挖掘的分类和聚类算法研究及R语言实现 A Study on Algorithm of Classification and Cluster

Based 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 and means 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： DataMining classification algorithm cluster algorithm realization by R

programe

4

暨南大学硕士学位论文

目录

中文摘要……………………………………………………………………………………………(Ⅰ) 英文摘要……………………………………………………………………………………………(Ⅱ) 目录…………………………………………………………………………………………………(Ⅲ) 1． 绪论………………………………………………………………………………………………1 1.1数据挖掘产生的背景和定义……………………………………………………………………1 1.2数据挖掘国内外发展现状………………………………………………………………………2 1.3数据挖掘与传统统计之间的关系………………………………………………………………3 1.4数据挖掘的主要应用分析………………………………………………………………………5 1.5研究目的和意义…………………………………………………………………………………7 1.6论文研究框架……………………………………………………………………………………7 1.7数据挖掘算法的研究工具—R语言……………………………………………………………8

2. 分类分析方法及R语言实现………………………………………………………………… 12

2.1分类分析的基本概念、步骤及方法……………………………………………………………12 2.2 分类分析的评估标准……………………………………………………………………………13 2.3基于距离分类方法及R语言实现………………………………………………………………14 2.4基于决策树分类方法及R语言实现 2.5基于神经网络分类方法及R语言实现

3. 聚类分析方法及R语言实现……………………………………………………………………28

3.1聚类分析基本概念及要求…………………………………………………………………………28 3.2聚类分析的数据类型及处理方法…………………………………………………………………29 3.3划分聚类方法及R语言实现………………………………………………………………35 3.4层次聚类方法及R语言实现 3.5基于密度聚类方法及R语言实现 3.6基于模型聚类方法及R语言实现 3.7模糊聚类方法及R语言实现

4. 实证分析………………………………………………………………………………………………

4.1研究背景…………………………………………………………………………………………… 4.2.数据整理…………………………………………………………………………………………… 4.3.数据初步统计分析…………………………………………………………………………………55 4.4.护理人员离职意愿的聚类及交叉分析……………………………………………………………58

5

基于数据挖掘的分类和聚类算法研究及R语言实现

4.5.护理人员离职预测模型的建立……………………………………………………………………61 4.6.小结…………………………………………………………………………………………………65

5. 总结与展望…………………………………………………………………………………………67

5.1总结 5.2展望

参考文献 …………………………………………………………………………………………………69 附录 ………………………………………………………………………………………………………71 在学期间发表论文及出版著作清单

致谢 ………………………………………………………………………………………………………82

6

暨南大学硕士学位论文

第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)一词首次出现在19年举行的第十一届国际联合人工智能学术会议上。随后在1991年、1993年和1994年都举行KDD专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增多，KDD国际会议发展成为年会。到目前为止，由美国人工智能协会主办的KDD国际研讨会己经召开了8次，规模由原来的专题讨论会发展到国际学术大会，研究重

8

暨南大学硕士学位论文

点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。1999年，亚太地区在北京召开的第三届PAKDD会议收到158篇论文，空前热烈。IEEE的KnowledgeandDataEngineering会刊率先在1993年出版了KDD技术专刊。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。数据挖掘在1995年召开了第一届知识发现与数据挖掘国际学术会议。该会议是由19年至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 数据库紧密结合

CART&MARS Salford

Clementine SPSS

DBMiner Enterprise Miner Intelligent Miner MineSet Oracle Data Mining Suite Polyanalyst Statistic Data

Miner

Weka

DBMiner

SAS IBM

SGI

Oracle

Megaputer

支持多种数据结构的挖掘，包括文本分析，预测，网络链

Intelligen

接分析，支持Microsoft OLE DB for data mining.

ce Statsoft

集成的综合统计分析系统

基于Java的集成多种机器学习方法的系统，具有开放式原

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

暨南大学硕士学位论文

包括一些数值型的属性值：ti={ti1，ti2，…，tik}，每个类也包含数值型属性值：Cj={Cj1，Cj2，…，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） N=NU{d}; （5） ELSE

（6） IF∃ u∈N such that dist(t,u)>dist(t,d) THEN （7） BEGIN （8） N=N-{U} （9） N=NU{d} （10） END （11）END

21

基于数据挖掘的分类和聚类算法研究及R语言实现

（12）C=class to which the most u∈N are classified;

在上述算法中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\

knn(train, test, cl, k = 3, prob=TRUE) #进行KNN算法分类 attributes(.Last.value)

分类结果见表2-1。

表2-1 KNN分类算法测试结果

类别\\序号 setosa versicolor virginica 类别\\序号 setosa versicolor

1 S C V 11 S C

2 S C V 12 S C

3 S C V 13S C

4 S V V 14S C

5 S C V 15S C

6 S C V 16S C

7 S C V 17S C

8 S C V 18 S C

9 S C V 19 S C

10S C V 20S C

22

暨南大学硕士学位论文

virginica V V V V V V V V V V

从测试结果来看，只有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中的属性计算信息增益率information gain ratio; （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\ 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.9

26

暨南大学硕士学位论文

| | | 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) Number of Leaves : 5 Size of the tree : 9

对应的决策树见图2.4

表2-2 C4.5算法结果

观察\\预测 setosa versicolorvirginica

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被划分为s1s2T1,T2，则此次划分的GINI系数为 ginisplit(T)=s gini(T1)+ s gini(T2)，其中s为T中样本的个数，

2

S1，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) #对品种进行CART分类 summary(ir.tr)

plot(ir.tr);text(ir.tr) #画决策树图 分类规则如下：

节点), 分割点,记录数, 离差,y值（类别）, (y值概率)，*表示最终节点 1) root 150 329.600 setosa ( 0.33333 0.33333 0.33333 )

2) Petal.Length < 2.45 50 0.000 setosa ( 1.00000 0.00000 0.00000 ) * 3) Petal.Length > 2.45 100 138.600 versicolor ( 0.00000 0.50000 0.50000 ) 6) Petal.Width < 1.75 33.320 versicolor ( 0.00000 0.90741 0.09259 ) 12) Petal.Length < 4.95 48 9.721 versicolor ( 0.00000 0.97917 0.02083 ) 24) Sepal.Length < 5.15 5 5.004 versicolor ( 0.00000 0.80000 0.20000 )* 25) Sepal.Length > 5.15 43 0.000 versicolor ( 0.00000 1.00000 0.00000 )*

29

基于数据挖掘的分类和聚类算法研究及R语言实现

13) Petal.Length > 4.95 6 7.638 virginica ( 0.00000 0.33333 0.66667 ) * 7) Petal.Width > 1.75 46 9.635 virginica ( 0.00000 0.02174 0.97826 ) 14) Petal.Length < 4.95 6 5.407 virginica ( 0.00000 0.16667 0.83333 ) * 15) Petal.Length > 4.95 40 0.000 virginica ( 0.00000 0.00000 1.00000 ) *

绘成相应的决策树见图2.5。

图2.5 CART树

从图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\

samp <- c(sample(1:50,25), sample(51:100,25), sample(101:150,25)) #抽取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\

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\"))

分类结果整理成表2-3

表2-3 基于神经网络BP算法的分类结果

表2-3的行表示实际的分类情况，列表示

观察\\预测 versicolor

24 0 1

setosa 0 25 0

virginica

1 0 24

利用神经网络方法得出的预测分类结果。versicolor从表2-3可以看出75例中，分类出错的是2例，其中1例versicolor类被错判为virginica类，1例virginica类被错判为versicolor类，分类准确率是97.3％。

setosa virginica

33

基于数据挖掘的分类和聚类算法研究及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的子集，如下所示： C1UC2U…UCk=X C1∩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，或称为对象属性结构）：n表示数据对象数目，p表示变量个数，这

是n*p维（n个对象p个属性）的矩阵。

⎡X

⎢⎢⎣X

X11X12

21

……… …

X1pX2p

…

X22

…

…n1

Xn2Xnp

⎤⎥ ⎥⎦

相异度矩阵（dissimilarity matrix，或称为对象-对象结构）：存储n个对象两两之间的近似性，表现形式是一个n*n维的矩阵。

⎡d(2,1)0

⎢⎢

⎣d(n,1)d(n,2)

…

…

00

……… …

00

…

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|) （3.1） n

这里的x1f,…,xnf 是f的n个度量值，mf 是f的平均值，即 1

mf =n(|x1f +x2f+…+xnf)

2． 计算标准化的度量值，或z-score： zif =(xif–mf)/sf (3.2)

这个平均的绝对偏差sf 比标准的偏差对于异常值有 更好的稳健性。在计算平均绝对偏差时，度量值与平均值的偏差没有被平方，因此异常值的影响在一定程度上被减小了。虽然存在更好的对偏差的度量方法，例如中值绝对偏差（median absolute deviation），但采用平均绝对偏差的优点在于孤立点的z-score值不会太小，因此孤立点仍可以被发现。

在标准化处理后，对象间的相异度（或相似度）是基于对象间的距离来计算的。最常用的距离度量方法是欧几里得距离，它的定义如下：

d(i,j)= （3.3）

这里的i=（xi1，xi2，…,xip）和j=(xj1,xj2,…)是两个p维的数据对象。

另一个著名的度量方法是曼哈顿距离，其定义如下： d（i，j）=|xi1-xj1|+|xi2-xj2|+…+|xip-| (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-|q）1/q (3.5)

这里的q是一个正整数。当q=1时，它表示曼哈顿距离；当q=2表示欧几里得距离。 如果对每个变量根据其重要性赋予一个权重，加权的欧几里得距离可以计算如下： d（i，j）=w1|xi1-xj1|2+w2|xi2-xj2|2+…+wp|xip-|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+t （3.7） 如果两个状态的输出不是同样重要，那么该二元变量是不对称的。例如一个疾病检查的肯定和否定的结果。根据惯例，我们将比较重要的输出结果，通常也是出现几率较小的结果编

r+s

38

暨南大学硕士学位论文

码为1（例如，HIV阳性），而将另一种结果编码为0（例如HIV阴性）。给定两个不对称的二元变量，两个都取值1的情况（正匹配）被认为比两个都取值0的情况（负匹配）更有意义。因此，这样的二元变量经常被认为好像只有一个状态。基于这样变量的相似度被称为非恒定的相似度。对非恒定的相似度，最著名的评价系数是Jaccard系数，在它的计算中，负匹配的数目被认为是不重要的，因此被忽略。 d(i,j)=q+r+s （3.8） 当对称的和非对称的二元变量出现在同一个数据集中，在描述的混合变量方法可以被应用。 （三） 名义变量（Nominal Variable）

名义变量是二元变量的推广，它可以具有多于两个的状态值。例如，map_color是一个名义变量，它可能有五个值：红色 ,黄色，绿色，粉红色，和蓝色。假设一个名义变量的状态数目是M。这些状态可以用字母，符号，或者一组整数（如1，2，…,M）来表示。要注意这些整数只是用于数据处理，并不代表任何特定的顺序。

名义变量两个对象i和j之间的相异度可以用简单匹配方法来计算： d(i,j)=p (3.9) 这里m是匹配的数目，即对i和j取值相同的变量的数目；而 p是全部变量的数目。我们可以通过赋权重来增加m的影响，或者赋给有较多状态的变量的匹配更大的权重。通过为每个状态创建一个二元变量，可以用二元变量来表示名义变量。对一个有特定状态值的对象，对应该状态值的二元变量值置为1，而其余的二元变量值置为0。例如，为了对名义变量map_color进行编码，对应于上面所列的五种颜色分别创建一个二元变量。如果一个对象是黄色，那么yellow变量被赋值为1，而其余的四个变量被赋值为0。对于这种形式的编码，可以采用在4.2.2

p-mr+s

节中讨论的方法来计算相异度。

（四）序数型变量（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–1

Zif=if (3.10)

Mf-1

(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=1pp

(3.11)

∑δij(f)

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)= maxxif-minx，这里的h包含了所有有变量f值的对象。

hhf

hhf

|x-x|

(3)如果f是序数型或者比例标度型变量：计算秩rif和zif=rif–1

，将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)2

i=1p=Cik

其中，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方法的一个缺点。这可能不适用于某些应用， 图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个中心点。如果任何取样得到的中心点不属于最佳的中心点，CLARA不能得到最佳聚类结果。例如，如果对象Oi是最佳的k个中心点之一，但它在取样的时候没有被选择，那CLARA将永远不能找到最佳聚类。这是为了效率而做的折中。如果样本发生偏斜，基于样本的一个好的聚类不一定代表了整个数据集合的一个好的聚类。

3.3.3 几种划分聚类算法的R语言实现及比较分析 （一）K-means算法的R语言实现及模拟分析

先用R模拟10000个均值为0，标准差为0.3的正态分布随机数据，再把这些随机数转化为

44

暨南大学硕士学位论文

10个变量，1000个对象的矩阵，然后再用同样方法模拟10000个均值为1，标准差为0.3的正态分布随机数，再转化为10个变量，1000个对象的矩阵，然后把这两矩阵合并为10个变量2000个样品的数据矩阵，然后利用K-means聚类方法聚成两类，观察其聚类效果如何。 R程序如下：

x <- rbind(matrix(rnorm(10000, sd = 0.3), ncol = 10),

matrix(rnorm(10000, mean = 1, sd = 0.3), ncol = 10)) colnames(x) <- c(\"x1\ cl <- Kmeans(x, 2) pch1=rep(\"1\ pch2=rep(\"2\

plot(x, col = cl$cluster,pch=c(pch1,pch2)) points(cl$centers, col = 3, pch = \"*\

聚类结果如图3.3，从聚类结果来看，K-means聚类方法可以完全准确地把均值为0，和均值为1的两类数据聚类开。图中绿色的*分别是两类的聚类中心。

图3.3 数据量为2000的K-means聚类效果图 图3.4 数据量为2000的pam算法聚类效果图

（二）Pam算法的R实现及模拟分析

Pam整合在cluster程序包里，所以在计算前先载入cluster包。利用（1）模拟的数据x用pam聚类方法进行模拟分析。R程序如下：

library(cluster) pamx=pam(x,2)

45

基于数据挖掘的分类和聚类算法研究及R语言实现

summary(pamx) plot(pamx,main=\"pam聚类方法的效果图\") （三）Clara算法的R实现及模拟分析

R程序如下： library（cluster） clarax=clara(x,2) clarax clarax$clusinfo

plot(clarax,main=\"clara算法聚类图\") 抽出的样本是：Best sample:

[1] 10 50 178 186 376 378 415 484 615 662 669 719 763 780 841 [16] 8 873 887 926 1011 1056 1093 1097 1215 1225 1282 1494 1520 15 1585 [31] 1590 1602 1605 1680 1729 1742 1753 1761 1768 15 1907 1909 1951 1984 size max_diss av_diss isolation [1,] 1000 1.755809 0.9829497 0.5902192 [2,] 1000 1.867952 1.0181780 0.6279163

图3.5 数据量为2000的clara算法聚类效果图 （四）K-means、pam、clara算法的模拟比较分析

上面分别模拟分析了数据量为2000的K-means、pam、clara算法，接下来要增大数据量为200000来比较分析各个算法的聚类效果。先生成1000000个均值为0，标准差为0.3的正态分布

随机数，然后转换成了10个变量，样品量为100000的数据矩阵，再生成1000000个均值为1，标准差为0.3的正态分布随机数，然后转换成10个变量，样品量为100000的数据矩阵，最后把

46

暨南大学硕士学位论文

这两个矩阵合并成10个变量，样品量为200000的数据矩阵。分别用K-means、pam、clara算法进行聚类，分析聚类结果并比较各算法的性能。

y <- rbind(matrix(rnorm(1000000, sd = 0.3), ncol = 10),

matrix(rnorm(1000000, mean = 1, sd = 0.3), ncol = 10)) colnames(y) <- c(\"y1\\"y2\ #K-means

cl <- K-means(y, 2) pch1=rep(\"1\ pch2=rep(\"2\

plot(y, col = cl$cluster,pch=c(pch1,pch2)) points(cl$centers, col = 3, pch = \"*\ #pam

pamx=pam(y,2)

plot(pamx,main=\"pam算法的聚类图\") #clara

clarax=clara(y,2)

plot(clarax,main=\"clara算法聚类图\")

Kmenas算法的聚类结果见图3.6,从图3.6可以看出，K-means可以很好地实现聚类，绿色*分别是两类的聚类中心。可见K-means算法实现简单、快速，对处理大型数据具有相对的可伸缩性和高效率。

图3.6 大型数据的K-means的聚类效果图 图3.7clara算法的聚类效果图

Pam算法的显示结果：

47

基于数据挖掘的分类和聚类算法研究及R语言实现

> pamy=pam(y,2)

错误在vector（”double”,length）:向量size的设定太大了 plot(pamy,main=\"pam算法的聚类图\")

错误在plot(pamy,main=\"pam算法的聚类图\")：找不到这个目标对象。

结果显示数据量太大，pam算法无法进行聚类，可见pam算法对小数据量是非常有效的，但对于大型数据其可伸缩性差，效率不高，甚至无法实现。

Clara算法结果见图3.7，可见clara算法对于大型数据能很好地进行聚类，具有良好的可伸缩性。与pam算法不同的是clara算法不是直接在给定的数据集合中寻找最佳的k个中心点，而是先抽取数据集合的多个样本，然后用pam方法在抽取得样本中寻找最佳的k个中心点返回最好的聚类结果作为输出。

3.4 层次聚类方法及R语言实现

3.4.1 层次聚类基本概念

层次聚类方法[1]（hierarchical methods）对给定的数据集进行层次的分解，直到某种条件满足为止，也称为系统聚类。具体又可分为凝聚、两种方案。

凝聚的层次聚类[4]是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原

子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足，绝大多数层次聚类方法属于这一类，他们只是在簇间相似度的定义上有所不同。

的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于 一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到某个终止条件。

凝聚层次聚类的代表是AGNES算法。层次聚类的代表是DIANA算法。

层次聚类要计算类与类之间（簇间）的距离，设有两个类Ca，Cb，分别有元素na、nb，元素x∈Ca,y∈Cb，元素间的距离记为d（x，y），类间距离记为D（Ca，Cb）。五个广泛采用的簇间距离度量方法如下：

（1） 最小距离法：Dmin(Ca,Cb) = min{d(x,y)|x∈Ca,y∈Cb} （2） 最大距离法：Dmax(Ca,Cb) = max{d(x,y)|x∈Ca,y∈Cb} （3） 中心法：Dmean(Ca,Cb) = | ma - mb |, ma,mb是簇Ca,Cb的平均值 （4） 类平均法：Davg(Ca,Cb) =nn∑x∈Ca ∑y∈Cbd(x,y)

ab

1

48

暨南大学硕士学位论文

（5）

离差平方和法：Dw2(Ca,Cb)=ra+b-ra-rb，ra=

∑(xi-ma)T(xi-mb)

n

i=1

其中，ra为类a直径,ra+b是类Ca+b的直径。 3.4.2 AGNES算法

（一）AGNES算法基本概念

AGNES（Agglomerative Nesting）算法[4]是凝聚的层次聚类方法。AGNES算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步地合并。例如C1中的一个对象之间的距离是所有属于不同簇的对象间的欧氏距离中最小的，C1，C2可能被合并。这是一种单一链接（Single-Link），其每个簇可以被簇中所有对象代表，两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。聚类的合并过程反复进行直到所有的对象最终合并形成一个簇。在聚类中，用户定义希望能得到的簇数目作为一个结束条件。 AGNES算法描述如下： （二）AGNES算法代码 算法3-3 AGNES算法

输入：包含n个对象的数据库，终止条件簇的数目k 输出：k个簇，达到终止条件规定数目 （1） 将每个对象当成一个初始簇 （2） REPEAT

（3） 根据两个簇中最近的数据点找到最近的两个簇； （4） 合并两个簇，生成新的簇的集合； （5） UNTIL 达到定义的簇的数目；

AGNES算法比较简单，但经常会遇到合并点选择的困难。这样的决定是非常关键的，因为一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做的处理不能撤销，聚类之间也不能交换对象。如果在某一步没有很好的合并选择，可能会导致低质量的聚类结果。而且，这种聚类方法不具有很好的可伸缩性，因为合并得决定需要检查和估算大量的对象或簇。该算法的复杂度为O（n2），该算法对n很大的情况不是很适用。 3.4.3 DIANA算法

49

基于数据挖掘的分类和聚类算法研究及R语言实现

（一）DIANA算法基本原理

DIANA（Divisive ANAlysis）算法属于的层次聚类。与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到某个终止条件。

在DIANA方法的处理过程中，所有的对象初始都放在一个簇中，根据一些原则（如簇中最临近对象的最大欧氏距离），将该簇。簇的过程反复进行，直到最终每个新的簇只包含一个对象。在聚类中，用户能定义希望得到的簇数目作为一个结束条件。同时它使用下面两种测度方法：

（1） 簇的直径：在一个簇中的任意两个数据点都有一个欧氏距离，这些距离中的最大值

就是簇的直径。

（2） 平均相异度（平均距离）：davg(Ci,Cj)=DIANA算法的描述如下： （二）DIANA算法代码 算法3-4 DIANA算法

输入：包含n个对象的数据库，终止条件簇的数目k 输出：k个簇，达到终止条件规定数目 （1） 将所有对象整个当成一个初始簇； （2） FOR (i=1,i≠k) DO BEGIN

（3） 在所有簇中挑出最大值直径的簇；

（4） 找出所挑中簇里与其他点平均相异度最大的一个点放入splinter group,剩余

的放入old party中； （5） REPEAT

（6） 在old party里找出到splinter group中点的最近距离不大于old party中点的最近

距离的点，并将该点加入splinter group;

（7） UNTIL 没有心的old party的点被分配给splinter group;

（8） splinter group和old party为被选中的簇成的两个簇，与其他簇一起组成新的

簇集合；

1

ninj

x∈Ciy∈Cj

∑∑X

i

x−y

50

暨南大学硕士学位论文

（9） END

层次聚类方法的缺点是已做的操作不能撤销，类之间不能交换对象。如果在某步没有选择好点，可能会导致低质量的聚类结果。而且，这种聚类方法不具有很好的可伸缩性，因为的决定需要检查和估算大量的对象或簇。 3.4.4 AGNES算法和DIANA算法的R语言实现及比较分析

下面将用cluster包提供的flower数据进行比较分析，这是关于18种普通花卉的资料。共有8个变量，各个变量意义如下：

V1：是否能过冬。两元变量，1表示能过冬，0表示不能过冬。

V2：是否生长在阴暗的地方。两元变量，1表示生长在阴暗的地方，0表示不是。 V3：是否有块茎。对称两元变量，1表示有块茎，0表示没有

V4：花卉颜色。名义变量，1是白色，2是黄色，3是粉红色，4是红色，5是蓝色 V5：所生长泥土。这是一个顺序变量，1表示干燥，2表示正常，3表示潮湿 V6：某人对这18种花卉的偏好选择。顺序变量，1到18表示其偏好顺序 V7：花卉高度。区间尺度变量，单位是厘米。

V8：花卉之间所需的距离间隔。区间尺度变量，单位是厘米。

可见，该数据类型有两元变量、名义变量、顺序变量、区间尺度变量等，是个比较复杂的问题。具体数据见表3-2。

表3-2 18种花卉的具体数据 序号

V1 V2 V3 V4 V5 V6 V7 V8 1 0 1 1 4 3 15 25 15 2 1 0 0 2 1 3 150 50 3 0 1 0 3 3 1 150 50 4 0 0 1 4 2 16 125 50 5 0 1 0 5 2 2 20 15 6 0 1 0 4 3 12 50 40 7 0 0 0 4 3 13 40 20 8 0 0 1 2 2 7 100 15 9 1 1 0 3 1 4 25 15 10 1 1 0 5 2 14 100 60 11 1 1 1 5 3 8 45 10 12 1 1 1 1 2 9 90 25 13 1 1 0 1 2 6 20 10 14 1 1 1 4 2 11 80 30 15 1 0 0 3 2 10 40 20

51

基于数据挖掘的分类和聚类算法研究及R语言实现

16 1 0 0 4 2 18 200 60 17 1 0 0 2 2 17 150 60 18 0 0 1 2 1 5 25 10

AGNES和DIANA算法的比较实证分析的R程序如下：

par(mfrow=c(1,2)) data(flower)

dai.f=daisy(flower,type=list(asymm=3,ordratio=7)) agn.f=agnes(dai.f,method=\"ward\")

plot(agn.f,which.plot=2,cex=0.7,yaxt=\"n\\"agnes算法的聚类图\") dia.f=diana(dai.f)

plot(dia.f,which.plot=2,main=\"diana算法的聚类图\") 聚类结果见图3.8

agnes算法的聚类图diana算法的聚类图0.81.0HeightHeight0.60.40.60.80.452351017361591381816171214114dai.fDivisive Coefficient = 0.681040.215167818161791311120.014dai.fAgglomerative Coefficient = 0.750.00.22

图3.8 AGNES算法和DIANA算法聚类比较图

从图3.8可以看出，大致上，AGNES算法和DIANA算法的聚类结果都可分成四类，结果整理成表3-3。

表3-3 AGNES算法和DIANA算法聚类结果比较

AGNES算法

第四类 9、13、15、10、11、12、14

DIANA算法 1、7、4 3、6、5 2、16、17、109、13、15、11、

12、14

从表3-3可以看出，AGNES算法和DIANA算法的聚类结果并不完全相等。这验证了层次聚类

52

第一类 第二类 1、6、7、3、5 4、8、18 第三类 2、16、17

暨南大学硕士学位论文

方法的缺点是已做的操作不能撤销，类之间不能交换对象。如果在某步没有选择好点，可能会导致低质量的聚类结果。此外，我们还可以看出，本例中只有18个数据，如果数据量很大，聚类的结果将无法解释，所以这种聚类方法不具有很好的可伸缩性。

3.5 基于密度聚类方法及R语言实现

绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的或凸形的簇，而在发现任意形状的簇上遇到了困难。在这种情况下提出了基于密度的另一类聚类方法。其主要思想是:只要临近区域的密度(对象或数据点的数目)超过某个阀值，就继续聚类。也就是说对给定类中的每个数据点在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇. 3.5.1 DBSCAN算法介绍 （一）DBSCAN算法基本原理

DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一个有代表性的基于密度的方法，它根据一个密度阀值来控制簇的增长。DBSCAN算法(基于高密度的聚类算法)将具有足够高密度的区域划分为簇，并可以在带有“噪声”的数据库中发现任意形状的簇。它定义簇为密度相连的点的最大集合。 在阐述该算法的基本思路之前先给出几个定义. 定义3-2 对象的ε-临域：给定对象在半径内的区域。

定义3-3 核心对象：如果一个对象的ε-临域至少包含最小数目MinPts个对象，则称该对象为核心对象。

定义3-4 直接密度可达：给定一个对象集合D，如果p是在q的ε-临域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。

定3-5 密度可达：如果存在一个对象链p1，p2，…，pn，p1＝q，pn＝p，对于pi∈D，1≤i≤n，pi+1是从pi关于ε和MinPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。 定义3-6 密度相连：如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连。

定义3-7 噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。

该算法的核心思想是:它通过检查数据库中的每个点的ε－邻域来寻找聚类。如果一个点P的

53

基于数据挖掘的分类和聚类算法研究及R语言实现

ε－邻域包含多于MinPts个点，则创建一个以P为核心对象的新簇.然后DBSCAN反复的寻找从这 些核心对象直接密度可达的对象，把这些密度可达的簇的合并，当没有新的点添加到任何簇时，聚类过程结束。DBSCAN算法描述如下： （二）DBSCAN算法代码 算法3-5 DBSCAN

输入：包含n个对象的数据库，半径ε,最少数目MinPts 输出：所有生成的簇，达到密度要求 （1） REPEAT

（2） 从数据库中抽取一个未处理的点

（3） IF抽出的点是核心点 THEN 找出所有从该点密度可达的对象，形成一个簇； （4） ELSE抽出的点是边缘点（非核心对象），跳出本次循环，寻找下一点； （5） UNTIL 所有点都被处理；

该算法的最大的优点是可以发现任意形状的簇，它主要缺点是它用户定义的参数非常的敏感，不同的ε和MinPts将对聚类的最终结果产生很大的影响，以至于导致差别巨大的聚类结果，而且这两个参数不好确定而且带有很大的主观色彩同时它也不具有很好的伸缩性，算法效率不是很高。

（三） DBSCAN的R语言实现

由于R语言没有提供现成的DBSCAN算法的函数，所以要自己编写DBSCAN函数。DBSCAN算法的R源程序见附录2。下面利用所编写的DBSCAN算法对flower数据作分析，flower具体数据见3.3。

设ε=0.65,MinPts=5。程序如下： library(cluster)

dflower <- daisy(flower,type = list(asymm = c(\"V1\norminal=4,ordinal=c(5,6),ordratio= 7, logratio= 8)) DBF=DBSCAN(dflower,eps=0.65,MinPts=5,distances=T) DBF

不同参数设置的DBSCAN聚类结果如下：

表3-4 ε=0.65,MinPts=5 DBSCAN聚类结果 序号

1 2 3 4 5 671011121314 15 16 1718

暨南大学硕士学位论文

所属类别 1 2 2 2 1 11222 1 2 2 2 2 2 2 2

如果设ε=0.75,MinPts=4时，则聚类结果如下：

表3-5 ε=0.75,MinPts=4 DBSCAN聚类结果 序号

1 2 3 4 5 672

82

92

1011121314 15 16 17182 2 2 2 2 2 2 2 2

所属类别 1 2 2 2 2 2

可见DBSCAN算法对ε和MinPts参数很敏感，这是DBSCAN算法的最大缺点。

3.6 基于模型聚类方法及R语言实现

基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。该方法经常是基于数据是根据潜在的概率分布生成的假设。基于模型的聚类方法主要有两类:统计学方法和神经网络方法。本文主要介绍基于统计学方法的概念聚类。 3.6.1 概念聚类方法基本原理

概念聚类[9]是机器学习中的一种聚类方法，给出一组未标记的对象，它产生对象的一个分类模式。与传统的聚类不同，概念聚类除了确定相似对象的分组外，还向前走了一步，为每组对象发现了特征描述，即每组对象代表了一个概念或类。因此，概念聚类是一个两步的过程:首先进行聚类，然后给出特征描述。在这里，聚类质量不再只是单个对象的函数，而且加入了如导出的概念描述的简单性和一般性等因素。概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概率度量.概率描述用于描述导出的概念。

COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性一值对来描述。COBWEB以一个分类树的形式创建层次聚类。分类树与决策树不同。分类树中的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的刘象。概率描述包括概念的概率和形如P(Ai＝Vij|Ck,)的条件概率，这里Ai=Vij是属性-值对，Ck是概念类(计数被累计并存储在每个计算概率的节点)。这就与决策树不同，决策树标记分支而非节点，而且采用逻辑描述符，而不是概率描述符。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数来沿着“最佳”匹配节点的路径在树中向下移动。COBWEB利用一个启发式评估方法(称为分类效用)来帮助进行树的构造。分类效用(Category Unility)定义如下:

55

基于数据挖掘的分类和聚类算法研究及R语言实现

P(Ck)∑i∑jp(Ai=Vij|Ck)2

∑P(C)[∑∑

k

k=1

i

n

22

p(A=V|C)−p(A=V)]∑∑iijkiijjij

(3.10)

n

∑∑

i

2

p(A=V)iijj

这里n是在树的某个层次上形成一个划分{C1,C2,⋯，Cn}的节点、概念或“种类”的数目。换句话说，在给定的划分中能够正确猜测期望的属性值的数目(这种期望数目对应于

P(Ck)∑i∑jp(Ai=Vij|Ck)2项中)，分类效用是随没有此种知识时期望的正确猜测的数目(对应

于∑i∑jp(Ai=Vij)2项)而增加的。其中:

(1)概率P(Ai=Vij|Ck)表示类内相似性。该值越大，共享该属性一值对的类成员比例就越大，更能预见该属性一值对是类成员。

(2)概率P(Ck|Ai=Vij)表示类间相异性。该值越大，在对照类中的对象的共享该属性一值对就越少，更能预见该属性一值对是类成员。

COBWEB也有其局限性。首先，它基于这样一个假设:在每个属性上的概率分布是彼此的。由于属性间经常是相关的，这个假设并不总是成立。此外，聚类的概率分布表示使得更新和存储聚类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。 3.6.2 COBWEB算法的R语言实现及模拟分析

下面利用RWeka包的函数Cobweb进行模拟分析，首先生成两个均值为0，标准差为0.5，长度为20的服从正态分布的数值向量，然后把这两个向量按列合并成变量为2，样品数为20的数据矩阵，接下来，再生成两个均值为5，标准差为0.5，长度为30的服从正态分布的数值向量，然后把这两个向量按列合并成变量为2，样品数为30的数据矩阵。再把这两个数据矩阵按行合并成变量为2，样品数为50的数据框。最后用COBWEB算法进行聚类分析。R程序如下： library(RWeka)

com=rbind(cbind(rnorm(20,0,0.5),rnorm(20,0,0.5)),cbind(rnorm(30,5,0.5),rnorm(30,5,0.5)#生成服从正态分布随机数

clas=factor(rep(2:1,c(20,30))) #生成因子形式数据

56

暨南大学硕士学位论文

dcom=data.frame(com,clas) #合并成数据框 cl <- Cobweb(dcom) cl

cl$class_ids

table(predict(cl), dcom$clas)

表3-6 COBWEB聚类结果 COBWEB聚类结果整理成表3-6。 从表3-6可以看出，COBWEB完全准确地把模拟数据聚成两类。

聚类结果\\原

始类别

1 30 0

2 0 20

3.7 模糊聚类方法及R语言实现

3.7.1 模糊聚类基本概念

1 2

前面介绍的几种聚类分析是一种硬划分，它把每个待识别的对象严格地划分到某个类中，具有非此即彼的性质，也就是说，一个数据点或者属于一个类，或者不属于一个类，而不存在重叠的情况。因此这种分类的界限是很明显的，而实际上大多数对象并没有严格的属性值，它们在形态和类属方面存在着中介性，适合进行软划分。Zadeh提出的模糊集理论为软划分提供了有力的分析工具，于是人们开始用模糊的方法来处理聚类问题，即模糊聚类分析。对于模糊集来说，一个数据点都是以一定程度属于某个类，也可以同时以不同的程度属于几个类。常用的模糊聚类算法是模糊C平均值FCM（Fuzzy C－Means）算法，该算法是在传统C均值算法中应用了模糊技术。FCM算法的步骤算法步骤如下: 输入：设定聚类数目c和参数b. 输出：聚类结果

（1）初始化各个聚类中心mi； （2）REPEAT；

（3）用当前的聚类中心计算隶属度函数； （4）用当前的隶属度函数更新计算各类聚类中心； （5）UNTIL各样本隶属度值稳定；

当算法收敛时，就得到了各类的聚类中心和各个样本对于各类的隶属度值从而完成了模糊聚类划分。如果需要，还可将模糊聚类结果进行去模糊化，即用一定的规则把模糊类分划分

57

基于数据挖掘的分类和聚类算法研究及R语言实现

转化为确定性分类。

3.7.2 FCM算法的R语言实现及模拟分析

下面将用R语言模拟分析FCM算法。先生成两个均值为0，标准差为0.5，长度为100的服从正态分布的数值向量，按列合并成2个变量数据量为100的数据矩阵，再生成两个均值为5，标准差为0.5，长度为150的服从正态分布的数值向量，按列合并成2个变量数据量为150的数据矩阵，然后生成两个均值为3.2，标准差为0.5，长度为300的服从正态分布的数值向量，按列合并成2个变量数据量为300的数据矩阵。最后把这三个数据矩阵按行合并，并用模糊聚类方法进行聚类，并分析聚类结果。 R程序如下：

library(cluster)

z=rbind(cbind(rnorm(100,0,0.5),rnorm(100,0,0.5)), cbind(rnorm(150,5,0.5),rnorm(150,5,0.5)), cbind(rnorm(300,3.2,0.5), rnorm(300,3.2,0.5))) z

fannyz=fanny(z,3,metric=\"SqEuclidean\") summary(fannyz)

plot(fannyz,main =\"模糊算法聚类图\")

模糊聚类效果见图3.10，从图3.10可以看出，模糊聚类很好地把数据聚成三类。

图3.10 模糊聚类效果图

58

暨南大学硕士学位论文

第4章 实证分析

本章主要以教蔡授欣玲就护理人员离职调查的数据为例，按数据挖掘的标准流程

CRISP-DM进行分析，首先对数据作初步统计分析，掌握护理人员的初步情况，再接着利用聚类方法来分析医院护理人员的离职意愿，然后利用分类方法建立医院护理人员离职的预测模型，最后得出结论并提供参考。

4.1 研究背景

护理人员的离职是一个世界范围内普遍存在的问题，它是造成护士短缺和护理质量下降的主要原因。很多国家对此都做了大量的研究，并采取了很多措施，但至今这个问题仍未得到很好的解决。我国的医院护理人员也存在工作压力大、薪酬少、在医院中地位低，社会给予关爱少等问题，从而造成我国的护理人员离职率偏高。护理人员的离职是一个非常重要的问题，它可造成许多方面的影响：（1）导致护理人员缺乏，影响护理质量以及护理业务的正常运作，从而可能影响广大患者的健康。（2）加重了其他护理人员的工作负荷，影响了她们的身心健康和家庭生活。（3）影响其他护士的士气和工作积极性，引发雪球效应，使离职率增加。（4）影响护理学科以及医学事业的发展。离职的护理人员中，很多是具有丰富的临床经验，业务熟练或具有较高知识水平的护士，是护理事业不可多得的人才。（5）造成国家教育经费及卫生资源的极大浪费。根据美国的一项研究，对每一个离职护士所造成的后果，需要平均花费6886至15125美元来弥补(包括重新招聘，职业培训，其他人员替代工作等)。

护理人员的离职过程常分为3个阶段：冲突期；发生于离职前的6～8个月，一般是因与各种工作有关的压力而致，若管理者在此期采取措施，可有效地防止离职的发生；增强期：离职的愿望增强，管理者在此期采取积极措施，有时也可改变其离职的决定；离职期：离职已无法控制。

所以护理人员离职率偏高问题应引起有关部门及社会的普遍关注，应把解决护理人员离职率偏高问题纳入到我国的医改范围内。而离职本身往往是潜在的，医院管理人员很难事先发现，而护理人员一旦离职，将会对医院的正常运作带来困难，尤其是一些技术性高的护理部门，所以就很有必要对护理人员的离职建立一个预警系统，及时发现护理人员的离职倾向，并作迅速地补救。

4.2 数据整理

59

基于数据挖掘的分类和聚类算法研究及R语言实现

该有效数据501例。为了便于分析，对各个问题进行编码，各编码含义如下：

M01：我愿意在这个工作上一直工作下去（打分，取值0-5分） M02：即使有别的机构来挖角，我也不会离开（打分，取值0-5分） M03：我打算辞去目前的工作（打分，取值0-5分） M04：对目前的工作，我觉得厌烦（打分，取值0-5分） M05：我想从事非护理工作事业（打分，取值0-5分）

M06：这个机构使我愿意作出好的工作表现（打分，取值0-5分） M07：我愿意接受分派至任何单位工作（打分，取值0-5分） M08；离职的念头曾在我脑中打转（打分，取值0-5分） M09；我设法要离开目前的工作（打分，取值0-5分） M10：我实际在找其它工作（打分，取值0-5分） M11：我庆幸当初选择目前这个工作（打分，取值0-5分） M12：合约期满后我将辞掉目前的工作（打分，取值0-5分） M13：继续留在这个工作上对我没有什么好处（打分，取值0-5分） SEX：性别。1表示女性，2表示男性 AGE：年龄

MAR：婚否。1表示未婚，2表示已婚，3表示拒答。

POST：职称。1表示实习护士，2表示合同护士，3表示护士，4表示护理师

DEPT：工作部门。1表示内外科病房，2表示加护病房，3表示急诊，4表示门诊，5表示精

神科病房，6表示妇产科病房，7表示儿科病房，8表示手术室，9表示恢复室，10表示洗肾室

4.3 数据初步统计分析

在进行聚类分类分析前，先进行初步统计分析，分别按性别、年龄组、婚否、职称、工作部门进行分类汇总，这样可以对护理人员的情况有了初步的了解。 （一）、按性别汇总

表4-1 按性别汇总 性别

女性 男性

频数 频率 累积频率 495 0.988 0.988 6 0.112 1

60

暨南大学硕士学位论文

总计

按性别汇总501 1 1

0.4按年龄组汇总0.80.60.40.00.2女性男性0.024及以下0.10.20.325-2930-3435-3940及以上

图4-1 图4-2

从表4-1和图4-1可以看出，护理人员绝大部分是女性，占98.8％。

（二）、按年龄组汇总

表4-2 按年龄汇总 年龄组

24及以下 25－29 30－34 35－39 40及以上 总计

频数 频率 累积频率 169 0.337 0.337 206 0.411 0.748 58 0.116 0.8 35 0.070 0.934 33 0.066 1 501 1 1

从表4-2和图4-2可以看出护理人员的大部分是年轻人，年龄在24及以下的占33.7％，25-29的占41.1％，29以下的占总的74.8％。

（三）、按婚否汇总

表4-3 按婚否汇总 婚否

未婚 已婚 拒答 总计

频数 频率 累积频率 353 0.705 0.705 145 0.2 0.994 3 0.006 1 501 1 1

61

基于数据挖掘的分类和聚类算法研究及R语言实现

0.70.60.50.40.30.20.00.1未婚已婚拒答0.00.10.20.30.40.50.6按婚否汇总按职位汇总实习护士合同护士护士护理师

图4-3 图4-4

从表4-3和图4-3可以看出，护理人员大部分是未婚的，占70.5％，而已婚的占28.9％，

拒答的占0.6％。

（四）、按职称汇总

表4-4 按职称汇总 职称

实习护士 合同护士 护士 护理师 总计

频数 频率 累积频率 36 0.072 0.072 26 0.052 0.124 307 0.613 0.737 132 0.263 1 501 1 1

从表4-4和图4-4可看出，大部分护理人员是护士职称，占61.3％，而护理师占26.3％。

（五）、按工作部门汇总

表4-5 按工作部门汇总

工作部门

内外科病房 加护病房 急诊 门诊 精神科病房 妇产科病房 儿科病房 手术室 恢复室 洗肾室 总计

频数 频率 累积频率 249 0.497 0.497 56 0.112 0.609 19 0.038 0.7 0.108 0.755 9 0.018 0.773 24 0.048 0.821 22 0.044 0.865 47 0.094 0.959 11 0.022 0.981 10 0.019 1 501 1 1

62

暨南大学硕士学位论文

图4-5

从表4-5和图4-5可以看出，护理人员的工作部门主要集中在内外科病房，其他病房分布相对比较均匀。

4.4 护理人员离职意愿的聚类及交叉分析

接下来将用K-means、pam、clara算法对护理人员进行聚类分析，挖掘哪些是高离职群、中离职群、低离职群，并比较分析这三种算法的聚类结果，最后选定一种聚类算法结果作后续分析。 4.4.1 聚类分析

4.4.1.1 K-means聚类结果分析

把K-means算法聚类结果整理成表5-7。

表4-7 K-means聚类结果表 聚类类别 频数

1 2 3 105 184 212

从表4-7可以看出，K-means算法把护理人员聚成三类，第1、2、3类的人数分别是105、

184、212。

4.4.1.2 pam聚类结果分析

把pam算法的聚类结果整理成表4-8，pam算法聚类效果图见图4-6。

表4-8 pam聚类结果分析表 聚类类别 频数

1 2 3 244 117 140

63

基于数据挖掘的分类和聚类算法研究及R语言实现

图4-6 pam算法聚类图 图4-7 clara算法聚类图

从表4-8和图4-6可以看出，pam算法把护理人员聚成三类，第1、2、3类的人数分别是

244、117、140。

4.4.1.3 clara聚类结果分析

把clara算法的聚类结果整理成表4-9，聚类效果图见图4-7。 表4-9 clara聚类结果分析表 聚类类别 频数

1 2 3 235 126 140

4.4.1.4 Kmean、pam、clara聚类结果比较分析

通过表4-7、4-8、4-9可以发现K-means和pam、clara聚类结果相差比较大，而pam和clara聚类结果比较接近，进一步分析，pam和clara聚类除了序号为18 38 171 185 214 324 369 476

499的聚类不同外，其他聚类结果均相同。可见clara算法对于大型数据能很好地进行聚类，具有良好的可伸缩性。与pam算法不同的是clara算法不是直接在给定的数据集合中寻找最佳的k个中心点，而是先抽取数据集合的多个样本，然后用pam方法在抽取得样本中寻找最佳的k个中心点返回最好的聚类结果作为输出。所以本文在这里选用clara的聚类结果。下面利用clara的聚类结果对各个类别以及问题（变量）进行均值分析，结果见表4-10。

表4-10 clara聚类结果均值分析表

变量

M01 M02 M03 M04

类1 类2 类3 平均分

3.1 4.1 2.0 3.0 3.5 4.4 2.3 3.4 3.0 4.2 1.9 3.0 2.9 3.9 2.2 3.0

暨南大学硕士学位论文

M05 M06 M07 M08 M09 M10 M11 M12 M13 平均分 人数 3.1 4.0 2.2 3.1 2.7 3.4 2.1 2.7 3.9 3.9 3.9 3.9 3.4 4.5 2.2 3.4 2.7 4.2 1.6 2.8 1.6 3.0 1.1 1.8 2.9 3.9 2.1 2.9 2.7 3.9 1.5 2.7 2.6 3.9 1.5 2.6 2.9 3.9 2.0 2.9 235 126 140 501

从表4-10可以看出类2的均值最高，为3.9分，可以定义为高离职群，有126位护理人员被划分为高离职群，占总数的25.1％；类1的均值次之，为2.9，可定义为中离职群，其中有235位护理人员被划分为中离职群，占总数的46.9％；类3的均值最低，为2.0，可定义为低离职群，其中有140位护理人员被划分为低离职群，占总数的28％。各变量的均值M07最高，为3.9；M10最低，为1.8，其余的大部分集中在3.0左右。 4.4.2 聚类结果交叉分析

上面通过clara算法聚类为三簇，分别为高离职群、中离职群、低离职群。接下来将用交叉分析来深入探讨各群的分布情况。 （一）按性别交叉分析

表4-11 按性别交叉分析表

性别 女性 男性 总计

中离职群 高离职群 低离职群 总计

232 125 138 495 3 1 2 6 235 126 140 501

从表4-11可以看出女性护理人员主要集中在中离职群，495位女性护理人员中232位为中离职群，占女性护理人员的46.9%。男性护理人员也主要集中在中离职群，6位男性护理人员中3位为中离职群，占50％。 （二）按年龄组交叉分析

表4-12 按年龄组交叉分析表

年龄组 24及以下 25－29 30－34 35－39 40及以上 总计

中离职群 高离职群 低离职群 总计 87 49 33 169 91 59 56 206 26 11 21 58 15 6 14 35 16 1 16 33 235 126 140 501

65

基于数据挖掘的分类和聚类算法研究及R语言实现

从表4-12可以看出，24岁及以下年龄组主要集中在中、高离职群，分别为87、49，两者占总数169的80.5％，25-29年龄组也主要集中在中、高离职群，分别为91、59，两者占总数

206的72.8％。30-34年龄组主要集中在中、低离职群，分别为26、21，两者占总数58的81％。35-39年龄组主要集中在中、低离职群，分别为15、14，两者占总数35的82.9％。40及以上年龄组也主要集中在中、低离职群，分别为16、16，两者占总数33的97％。从上面的分析，可以看出29岁以下的年轻护理人员主要其中在中、高离职群。而30岁以上的护理人员主要集中在中、低离职群，而且随着年龄的增大，中、低离职群所占的比例也在不断地增大。这是非常符合实际情况以及心理学原理。 （三）按婚否交叉分析

表4-13 按婚否交叉分析表

婚否 未婚 已婚 拒答 总计

中离职群 高离职群 低离职群 总计

173 94 86 353 60 32 53 145 2 0 1 3 235 126 140 501

从表4-13可以看出，未婚护理人员主要集中在中、高离职群，分别为173、94，两者占总数353的75.6％。而已婚护理人员主要集中在中、低离职群，分别为60，53，两者占总数

145的77.9％。这与未婚人员的家庭责任少，易不满于现状，易跳槽，而已婚人员家庭责任大，求稳的实际情况相符合。这也进一步证明了前面聚类结果的正确性。 （四）按职称交叉分析

表4-14 按职称交叉分析表 职称

实习护士 合同护士 护士 护理师 总计

中离职群 高离职群 低离职群 总计

18 11 7 36 9 6 11 26 147 86 74 307 61 23 48 132 235 126 140 501

从表4-14可以看出：实习护士主要集中在中、高离职群，分别为18、11，两者占总数36的80.5％；合同护士主要集中在中、低离职群，分别为9、11，两者占总数26的76.9％；护士主要集中在中、高离职群，分别为147、86，两者占总数的75.9％；护理师主要集中、低离职群，分别为61、48，两者占总数132的82.6％。 （五） 按工作部门交叉分析

66

暨南大学硕士学位论文

表4-15 按工作部门交叉分析表

工作部门 内外科病房 加护病房 急诊 门诊 精神科病房 妇产科病房 儿科病房 手术室 恢复室 洗肾室

总计

中离职群 高离职群 低离职群 总计

120 69 60 249 29 9 18 56 10 6 3 19 22 5 27 3 2 4 9 14 5 5 24 10 7 5 22 21 12 14 47 3 5 3 11 3 6 1 10 235 126 140 501

从表4-15可以看出：内外科病房护理人员主要集中在中、高离职群，分别为120、69，两者占总数249的75.9％；加护病房护理人员主要集中在中、低离职群，分别为29、18，两者占总数的83.9％；急诊护理人员主要集中在中、高离职群，分别为10、6，两者占总数19的84.2％；门诊护理人员主要集中在中、低离职群，分别为22、27，两者占总数的90.7％；精神科病房护理人员主要集中在中、低离职群，分别为3、4，两者占总数9的77.8％；妇产科病房的护理人员主要集中在中离职群，为14位，占总数24的58.4％。儿科病房护理人员主要集中在中、高离职群，分别为10、7，两者占总数22的77.3％；手术室护理人员主要集中在中、低离职群，分别为21、14，两者占总数47的74.5％；恢复室护理人员高离职群人数为5位，占总数11的45.4％；洗肾室护理人员主要集中在中、高离职群，分别为3、6，两者占总数10的90％。

4.5 护理人员离职预测模型的建立

4.5.1 KNN分类预测模型的建立

KNN方法的基本思想是假定每个类包含多个训练数据，且每个训练数据都有唯一的类别标记，计算每个训练数据到待分类对象的距离，取和待分类对象距离最近的k个训练数据，k个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。本文的数据量不是很大，而且为了便于与其它不同分类方法的可比性，KNN的训练数据、测试数据都选取全部数据，并设k＝5。分类预测结果如表4-16：

67

基于数据挖掘的分类和聚类算法研究及R语言实现

表4-16 KNN分类预测结果 聚 类 结 果

中离职群 高离职群 低离职群

分类预测结果 中离职群 高离职群 226 5 10 116 13 0

低离职群

4 0 127

从表4-16可以看出：中离职群里有5位被错分到高离职群，4位被错分到低离职群；高离职群里有10位被错分到中离职群；低离职群里有13位被错分到中离职群。共有32位分类错误，总的预测准确率为93.6％，并且并未出现高离职群被错分到低离职群和低离职群被错分到高离职群的现象，说明总的分类预测效果良好。 4.5.2 决策树分类预测模型的建立 4.5.2.1 分类回归树（CART）

CART在计算过程中充分利用二叉树的结构，即根节点包含所有样本，在一定的分割规则下根结点被分割为两个子节点，这个过程又在子节点上重复进行，成为一个回归过程，直至不可再分成为叶节点为止。该算法采用一种二分递归分割的技术，总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶节点都有两个分枝。利用CART算法得到的分类规则见附录2。该分类规则可以形象地由图4-9来展示。

图4-9 CART树

从附录2、图4-9可以看出：CART分类规则共有16个最终节点，错分率为11.78％，即

68

暨南大学硕士学位论文

预测准确率为88.22％，总体分类预测良好 4.5.2.2 C4.5决策树

C4.5算法是从ID3算法演变而来，除了拥有ID3算法的功能外，还增加了对连续型属性，属性值空缺情况的处理等功能，对树剪枝也有了较成熟的方法。C4.5是以信息增益比例作为分离目标评价函数，采用自顶向下不可返回的策略，搜出全部空间的一部分，它确保决策树建立最简单，每次所做的测试数据最少。利用C4.5算法得到的分类规则见附录3。把分类预测的结果整理成表4-17。

表4-17 C4.5分类预测结果整理

聚 类 结 果

中离职群 高离职群 低离职群

分类预测结果 中离职群 高离职群 低离职群

222 7 6 3 123 0 6 0 134

从表4-17可以看出：中离职群有7位被错分到高离职群，6位被错分到低离职群，高离职群有3位被错分到中离职群，低离职群有6位被错分到中离职群。共有22位被错分，分类预测准确率为95.6％，并且高离职群未被错分到低离职群，低离职群也未被错分到高离职群。总的来说，C4.5决策树的预测效果是优良。 4.5.3 BP神经网络分类预测模型的建立

神经网络建立在有自学习能力的数学模型基础上，可以对复杂的数据进行分析，并完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络的典型应用是建立分类模型。反向传播(BP)算法是一个用于前演网络的典型的学习算法。本例采用单隐藏层，2个隐藏单元，权重衰减参数是5e-4，初始权重取值范围为[-0.1,0.1],最大迭代次数为500。BP神经网络分类预测结果见表4-18。

表4-18 BP神经网络分类预测结果

聚 类 结 果

中离职群 高离职群 低离职群

分类预测结果 中离职群 高离职群 低离职群

230 4 1 4 122 0 2 0 138

从表4-18可以看出：中离职群有4位被错分到高离职群，1位被错分到低离职群，高离职群有4位被错分到中离职群，低离职群有2位被错分到中离职群。总共有11位错分，预测准确率为97.8％。并且高离职群未被错分到低离职群，低离职群也未被错分到高离职群。总的

69

基于数据挖掘的分类和聚类算法研究及R语言实现

来说，BP神经网络的预测效果是非常好！ 4.5.4 四种分类预测模型效果的比较分析

把上面介绍的四种分类算法预测效果进行比较分析，整理成表4-19。

表4-19 四种分类算法预测效果比较分析 预测方法 KNN CART

预测准确率 93.6％

各算法优缺点 需设置近邻参数k

不需设置参数，但分类准确率不是很高 不需设置参数，分类准确率也很高 需设置参数，分类准确率很高

88.22％

C4.5决策树 95.6％. BP神经网络 97.8％

从表4-19可以看出，C4.5决策树和BP神经网络的的预测效果比较好，可以考虑以后以这两种方法建立护理人员离职预测模型。

4.6 小结

通过上面的的分析，我们得出如下结论：

（1）从性别来分析，护理人员绝大部分是女性，占98.8％；从年龄组来看，护理人员的大部分是年轻人，年龄在29岁以下的占总的74.8％；从婚否来看，护理人员大部分是未婚的，占

70.5％；从职称来看，大部分护理人员是护士职称，占61.3％，而护理师占26.3％；从工作病房来看，护理人员的工作部门主要集中在内外科病房，占49.7％，其他病房分布相对比较均匀。

（2）通过clara聚类分析,我们把被调查的501位护理人员聚成高离职群、中离职群、低离职群三类。高离职群平均得分为3.9分，有126位护理人员被划分为高离职群，占总数的25.1％；中离职群平均得分为2.9，中有235位护理人员被划分为中离职群，占总数的46.9％；低离职群的平均得分为2.0，中有140位护理人员被划分为低离职群，占总数的28％。 （3）按性别交叉分析，女性护理人员主要集中在中离职群，495位女性护理人员中232位为中离职群，占女性护理人员的46.9%。男性护理人员也主要集中在中离职群；按年龄组交叉分析，29岁以下的年轻护理人员主要其中在中、高离职群。而30岁以上的护理人员主要集中在中、低离职群。按婚否交叉分析，未婚护理人员主要集中在中、高离职群。而已婚护理人员主要集中在中、低离职群；

按职称交叉分析，实习护士、护士主要集中在中、高离职群，合同护士、护理师主要集中在中、低离职群，按工作部门交叉分析，内外科病房、急诊、儿科病房、洗肾室护理人员主要集中在中、高离职群，加护病房、门诊、精神科病房、手术室护理人员主要集中在中、低离

70

暨南大学硕士学位论文

职群，妇产科病房的护理人员主要集中在中离职群，恢复室护理人员高离职群。

（4）通过分类预测分析，发现C4.5决策树和BP神经网络的的预测效果比较好，可以考虑以这两种方法建立护理人员离职预测模型。医院可以建立新员工进入摸底调查制度和定期对所有员工进行调查制度。以便及时发现有离职倾向的员工，进行培训教育，减少护理人员的离职率，或及时招新员工，维护医院的正常秩序。

71

基于数据挖掘的分类和聚类算法研究及R语言实现

第5章 结论与展望

本章对本文所做的主要工作进行总结，并对研究中存在的问题和有待进一步研究的问题进行分析，并在此基础上对数据挖掘的前景进行展望。

5.1 结论

分类、聚类方法由于其应用领域的广泛性而成为数据挖掘领域中的一个研究热点。本文的主要研究工作包括以下几个方面:

(1)系统地介绍了数据挖掘分类、聚类算法，并对它们进行了评述，指出了其存在的问题。 (2)用R语言实现文中介绍的各种分类、聚类算法，并用R语言模拟比较分析各种算法的优劣。(3)自行编写函数实现部分目前其他软件尚无法实现的算法。

(4)实证分析着重于数据挖掘的整体流程，利用聚类、分类方法对医院护理人员离职进行聚类、分类预测分析，通过实证分析比较各种算法在分析实际问题中的优劣，并建立一套医院护理人员离职预测模型。

本文的局限性及存在的不足之处有：

(1)由于国内适用于数据挖掘的数据比较难收集，本文实证分析的数据来自的调查结果，数据量相对来说还不够大，而且该数据不是来源于数据库，事先已经经过清洗。

（2）分类、聚类算法的研究更新速度很快，本文所涉及的算法还是非常有限的，需要在以后的工作学习中不断学习新的算法。

（3）分类、聚类方法只是数据挖掘比较常用、基础的两种方法，但数据挖掘还涉及到关联规则分析、时间序列分析、空间数据挖掘、文本挖掘等方法，要更加全面的掌握数据挖掘技巧还需以后要不断学习其它方法。

5.2展望

当前数据挖掘的研究正处在方兴未艾的发展阶段，以后还将形成更大的浪潮，研究的焦点可能会集中到以下几个方面:

(1)研究专门用于知识发现的数据挖掘语言。

(2)寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也便于在知识发现过程中的人机交互。

(3)研究在网络环境下的数据挖掘技术，特别是在Internet上建立数据挖掘服务器，与数据库

72

暨南大学硕士学位论文

服务器配合，实现数据挖掘。

(4)加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。

(5)高效率挖掘算法。为了能从大量数据中有效地抽取信息，数据挖掘算法必须是高效的，即算法的运行时间必须是可预测的和可接受的。

(6)提高数据挖掘结果的有效性、确定性和可表达性。己发现的知识应能准确地描述数据库中的内容，并能用于实际领域。对有缺陷的数据应当根据不确定性度量，以近似规则或定量规则形式表示出来。数据挖掘系统还应能很好地处理和抑制噪声数据。所以要研究度量知识质量的方法，包括模型和工具的实用性和可靠性。但无论怎样，需求牵引、市场驱动是永恒的，数据挖掘将首先满足信息时代用户的急需，大量面向应用的、高效的数据挖掘方法将不断涌现。

总的来说，数据挖掘的应用将会越来越广。目前在银行、电信、保险、CRM、交通、零售等商业领域应用比较多。以后在制造业、教育系统等领域将会有广泛应用，甚至可以这样说，只要哪里有大量的数据，哪里就会有数据挖掘的应用。

73

基于数据挖掘的分类和聚类算法研究及R语言实现

参考文献

【1】朱建平著.数据挖掘的统计方法及实践.北京：中国统计出版社.2005.10 【2】张尧庭、谢邦昌、朱世武编.数据采掘入门及应用.中国统计出版社.2001.11 【3】袁方、王煜、王丽娟等译.实用数据挖掘.北京：电子工业出版社.2004.6 【4】毛国君、段立娟等编著.数据挖掘原理与算法.清华大学出版社.2006.1 【5】邵峰晶、于忠清编著.数据挖掘原理于算法.中国水利水电出版社.2004.10

【6】J.Han,M.Kamber．数据挖掘概念与技术(影印版)．北京：高等教育出版社．2001.5 【7】王斌会著.经济管理模型的多变量统计方法及分析系统Qstat.北京.中国统计出版社.2005.7

【8】Margaret H.Dunham.DATA MINING Introductory and Advanced Topics.北京.清华大学出版社.2003.10 【9】范明、孟小峰等译.数据挖掘概念与技术.北京：机械工业出版社.2006.3 【10】朱扬勇、左子叶、张忠平等译.数据挖掘实践.北京：机械工业出版社.2003.9 【11】郭军华.数据挖掘中聚类分析研究 武汉理工大学硕士论文.2003.12 【12】孙孝萍.基于聚类的数据挖掘算法研究 西南石油学院硕士论文.2002.04 【13】孙雪莲.数据挖掘中分类算法研究.吉林大学硕士学位论文.2002.10 【14】王莉.数据挖掘中聚类方法的研究.天津大学博士学位论文.2003.12 【15】孙总参.数据挖掘中聚类算法的研究与应用.中国农业大学硕士论文.2004.05

【16】姜伟.基于数据挖掘聚类算法的研究及其应用.辽宁工程技术大学硕士学位论文.2004.02 【17】胡佩，夏绍伟，基于大型数据仓库的数据采掘:研究综述，软件学报，1998,90（1）:53-63 【18】丁国徽译.R导论.2005.6

【19】John Verzani.simpleR-Using R for Introductory Statistics 【20】Vincent ZooNEKYND.Statistics with R,28th August 2005

【21】W.N.Venables and B.D.Ripley.Modern Applied Statistics with S,Fourth edition,15 March 2002 【22】Luis Torgo.Data Mining with R:learning by case studies,may 22,2003

【23】Fayyad U,Piatetsky-ShapiroG,Smyth P, Knowledge discovery and data mining:towards a unifying

framework.In Proceedings of the International Conference on Knowledge Discovery and DataMining(KDD-96).1996

【24】Chen M-S.HanJ ,Yu P S .DataMining:An Overview from a Database Perspective. IEEE Trans.on

Knowledge and Data Eng.1996,8(6):866-883

【25】Piatetsky-Shapiro G.,Frawley W J.Knowledge Discoveryin Database.AAAI/MIT Press,1991 【26】Weldon Jay-Louise. Data Mining and Visualization. Database Programming and

Design,1996-9(5):21-24

【27】M.S.Aldenderfer,R.K.Blashfield:”Cluster Analysis”,Sage publications,1976

74

暨南大学硕士学位论文

【28】谢邦昌电子学校网站.http://bidm.stat.fju.edu.tw:81/ 【29】中国人民大学统计之都网站.http://cos.name/bbs 【30】R语言中国镜像. http://www.lmbe.seu.edu.cn/CRAN/ 【31】数据挖掘讨论组http://www.dmgroup.org.cn/

【32】数据仓库与数据挖掘－ITPUB论坛http://www.itpub.net/forum43.html 【33】诊断试验评价与数据挖掘http://vip.6to23.com/statdtedm/index.html 【34】王斌会、方匡南、谢佳斌.R语言统计分析软件教程.北京.中国教育文化出版社.2007.1

75

基于数据挖掘的分类和聚类算法研究及R语言实现

附录1 Fisher鸢尾花（Iris）数据

序号

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

花萼长

5.1 4.9 4.7 4.6 5.0 5.4 4.6 5.0 4.4 4.9 5.4 4.8 4.8 4.3 5.8 5.7 5.4 5.1 5.7 5.1 5.4 5.1 4.6 5.1 4.8 5.0 5.0 5.2 5.2 4.7 4.8 5.4 5.2 5.5 4.9 5.0 5.5 4.9 4.4 5.1 5.0 4.5 4.4 5.0 5.1 4.8 5.1 4.6 5.3

花萼宽

3.5 3.0 3.2 3.1 3.6 3.9 3.4 3.4 2.9 3.1 3.7 3.4 3.0 3.0 4.0 4.4 3.9 3.5 3.8 3.8 3.4 3.7 3.6 3.3 3.4 3.0 3.4 3.5 3.4 3.2 3.1 3.4 4.1 4.2 3.1 3.2 3.5 3.6 3.0 3.4 3.5 2.3 3.2 3.5 3.8 3.0 3.8 3.2 3.7

花瓣长

1.4 1.4 1.3 1.5 1.4 1.7 1.4 1.5 1.4 1.5 1.5 1.6 1.4 1.1 1.2 1.5 1.3 1.4 1.7 1.5 1.7 1.5 1.0 1.7 1.9 1.6 1.6 1.5 1.4 1.6 1.6 1.5 1.5 1.4 1.5 1.2 1.3 1.4 1.3 1.5 1.3 1.3 1.3 1.6 1.9 1.4 1.6 1.4 1.5

花瓣宽

0.2 0.2 0.2 0.2 0.2 0.4 0.3 0.2 0.2 0.1 0.2 0.2 0.1 0.1 0.2 0.4 0.4 0.3 0.3 0.3 0.2 0.4 0.2 0.5 0.2 0.2 0.4 0.2 0.2 0.2 0.2 0.4 0.1 0.2 0.2 0.2 0.2 0.1 0.2 0.2 0.3 0.3 0.2 0.6 0.4 0.3 0.2 0.2 0.2

类别

setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa setosa

76

暨南大学硕士学位论文

50 51 52 53 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 98 99 100 101 5.0 7.0 6.4 6.9 5.5 6.5 5.7 6.3 4.9 6.6 5.2 5.0 5.9 6.0 6.1 5.6 6.7 5.6 5.8 6.2 5.6 5.9 6.1 6.3 6.1 6.4 6.6 6.8 6.7 6.0 5.7 5.5 5.5 5.8 6.0 5.4 6.0 6.7 6.3 5.6 5.5 5.5 6.1 5.8 5.0 5.6 5.7 5.7 6.2 5.1 5.7 6.3 3.3 3.2 3.2 3.1 2.3 2.8 2.8 3.3 2.4 2.9 2.7 2.0 3.0 2.2 2.9 2.9 3.1 3.0 2.7 2.2 2.5 3.2 2.8 2.5 2.8 2.9 3.0 2.8 3.0 2.9 2.6 2.4 2.4 2.7 2.7 3.0 3.4 3.1 2.3 3.0 2.5 2.6 3.0 2.6 2.3 2.7 3.0 2.9 2.9 2.5 2.8 3.3 1.4 4.7 4.5 4.9 4.0 4.6 4.5 4.7 3.3 4.6 3.9 3.5 4.2 4.0 4.7 3.6 4.4 4.5 4.1 4.5 3.9 4.8 4.0 4.9 4.7 4.3 4.4 4.8 5.0 4.5 3.5 3.8 3.7 3.9 5.1 4.5 4.5 4.7 4.4 4.1 4.0 4.4 4.6 4.0 3.3 4.2 4.2 4.2 4.3 3.0 4.1 6.0 0.2 1.4 1.5 1.5 1.3 1.5 1.3 1.6 1.0 1.3 1.4 1.0 1.5 1.0 1.4 1.3 1.4 1.5 1.0 1.5 1.1 1.8 1.3 1.5 1.2 1.3 1.4 1.4 1.7 1.5 1.0 1.1 1.0 1.2 1.6 1.5 1.6 1.5 1.3 1.3 1.3 1.2 1.4 1.2 1.0 1.3 1.2 1.3 1.3 1.1 1.3 2.5 setosa versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor versicolor virginica

77

基于数据挖掘的分类和聚类算法研究及R语言实现

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 5.8 7.1 6.3 6.5 7.6 4.9 7.3 6.7 7.2 6.5 6.4 6.8 5.7 5.8 6.4 6.5 7.7 7.7 6.0 6.9 5.6 7.7 6.3 6.7 7.2 6.2 6.1 6.4 7.2 7.4 7.9 6.4 6.3 6.1 7.7 6.3 6.4 6.0 6.9 6.7 6.9 5.8 6.8 6.7 6.7 6.3 6.5 6.2 5.9 2.7 3.0 2.9 3.0 3.0 2.5 2.9 2.5 3.6 3.2 2.7 3.0 2.5 2.8 3.2 3.0 3.8 2.6 2.2 3.2 2.8 2.8 2.7 3.3 3.2 2.8 3.0 2.8 3.0 2.8 3.8 2.8 2.8 2.6 3.0 3.4 3.1 3.0 3.1 3.1 3.1 2.7 3.2 3.3 3.0 2.5 3.0 3.4 3.0 5.1 5.9 5.6 5.8 6.6 4.5 6.3 5.8 6.1 5.1 5.3 5.5 5.0 5.1 5.3 5.5 6.7 6.9 5.0 5.7 4.9 6.7 4.9 5.7 6.0 4.8 4.9 5.6 5.8 6.1 6.4 5.6 5.1 5.6 6.1 5.6 5.5 4.8 5.4 5.6 5.1 5.1 5.9 5.7 5.2 5.0 5.2 5.4 5.1 1.9 2.1 1.8 2.2 2.1 1.7 1.8 1.8 2.5 2.0 1.9 2.1 2.0 2.4 2.3 1.8 2.2 2.3 1.5 2.3 2.0 2.0 1.8 2.1 1.8 1.8 1.8 2.1 1.6 1.9 2.0 2.2 1.5 1.4 2.3 2.4 1.8 1.8 2.1 2.4 2.3 1.9 2.3 2.5 2.3 1.9 2.0 2.3 1.8 virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica virginica

78

暨南大学硕士学位论文

附录2 DBSCAN算法源程序

distvector <- function(x,data) {

ddata <- t(data)-x

dv <- apply(ddata^2,2,sum) }

#data：数据可以是nxp或距离矩阵 # eps：对象的ε-临域

# MinPts：类中包含的最小数目对象 # scale: 数据是否要标准化？

# distances:选TURE时表示数据是距离矩阵 # showplot: 计算过程是否要可视化？

# countmode:当计算过程空值DBSCAN将会给出相应的信息

DBSCAN <- function(data,eps,MinPts=5, scale=FALSE, distances=FALSE, showplot=FALSE,

countmode=c(1,2,3,5,10,100,1000,5000,10000,50000)){ data <- as.matrix(data) n <- nrow(data)

if (scale) data <- scale(data) unregpoints <- rep(0,n) e2 <- eps^2 cv <- rep(0,n) cn <- 0 i <- 1

for (i in 1:n){

if (i %in% countmode) cat(\"Processing point \ unclass <- cv<1 if (cv[i]==0){

if (distances) seeds <- data[i,]<=eps else{

seeds <- rep(FALSE,n)

seeds[unclass] <- distvector(data[i,],data[unclass,])<=e2 }

if (sum(seeds)+unregpoints[i]cn <- cn+1 cv[i] <- cn

seeds[i] <- unclass[i] <- FALSE

unregpoints[seeds] <- unregpoints[seeds]+1 while (sum(seeds)>0){

if (showplot) plot(data,col=1+cv) unclass[seeds] <- FALSE cv[seeds] <- cn ap <- (1:n)[seeds] print(ap)

seeds <- rep(FALSE,n) for (j in ap){

79

基于数据挖掘的分类和聚类算法研究及R语言实现

if (showplot) plot(data,col=1+cv) jseeds <- rep(FALSE,n)

if (distances) jseeds[unclass] <- data[j,unclass]<=eps else{

jseeds[unclass] <- distvector(data[j,],data[unclass,])<=e2 }

unregpoints[jseeds] <- unregpoints[jseeds]+1 if (cn==1)

cat(j,\" sum seeds=\ \" newseeds=\ if (sum(jseeds)+unregpoints[j]>=MinPts){ seeds[jseeds] <- cv[jseeds]==0 cv[jseeds & cv<0] <- cn }

} # for j

} # while sum seeds>0

} # else (sum seeds + ... >= MinPts) } # if cv==0 } # for i

if (sum(cv==(-1))>0){ noisenumber <- cn+1

cv[cv==(-1)] <- noisenumber } else

noisenumber <- FALSE

out <- list(classification=cv, noisenumber=noisenumber,

eps=eps, MinPts=MinPts, unregpoints=unregpoints) out

} # dbscan

# classification:分类向量

# noisenumber:分类向量中包含的噪音点数目 # unregpoints: 忽略...

80

暨南大学硕士学位论文

附录3 本文第四章R语言程序

oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=0.7) old.digits=options(\"digits') options(digits=2) library(foreign) m=read.spss (\"data.sav\") md=as.data.frame(m) # 描述统计分析 table(md$SEX)

table(md$SEX)/length(md$SEX) barplot(table(md$SEX)/length(md$SEX),col=4,names.arg=c(\"女性\男性\"),main=\"按性别汇总\")

gage=cut(md$AGE,breaks=c(min(md$AGE)-1,24,29,34,39,max(md$AGE))) table(gage)

table(gage)/length(md$AGE)

barplot(table(gage)/length(md$AGE),col=4,names.arg=c(\"24及以下\及以上\"),main=\"按年龄汇总\") table(md$MAR)

table(md$MAR)/length(md$MAR) barplot(table(md$MAR)/length(md$MAR),col=4,names.arg=c(\"未婚\已婚\拒答\"),main=\"按婚否拒答\") table(md$POST)

table(md$POST)/length(md$POST) barplot(table(md$POST)/length(md$POST),col=4,names.arg=c(\"实习护士\合同护士\护士\护理师\"),main=\"按职称汇总\") table(md$DEPT)

table (md$DEPT)/length(md$DEPT)

oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=0.52)

barplot( table(md$DEPT)/length(md$DEPT),col=4,names.arg=c(\"内外科病房\加护病房\急诊\门诊\精神科病房\妇产科病房\儿科病房\手术室\恢复室\洗肾室\"),main=\"按工作部门汇总\") #聚类分析 #K-means

km<- K-means(md[1:13], 3) kclust=km$cluster kclust table(kclust) #pam

81

基于数据挖掘的分类和聚类算法研究及R语言实现

library(cluster)

pammd=pam(md[,1:13],3) summary(pammd)

plot(pammd,main=\"pam算法聚类效果图\") pclust=pammd$cluster clust1 table(clust1) #clara

claram=clara(md[,1:13],3) claram claram$clusinfo

plot(claram,main=\"clara算法聚类效果图\") cclust=claram$cluster cclust table(cclust)

#三种聚类算法的结果比较 mdc=cbind(md[,1:18],cclust) which(kclust!=cclust) which(kclust!=pclust) which(pclust!=cclust) mdc1=mdc[mdc$cclust==1,] mdc2=mdc[mdc$cclust==2,] mdc3=mdc[mdc$cclust==3,] ma=apply(mdc[,1:13],2,mean) ma1=apply(md1[,1:13],2,mean) ma2=apply(md2[,1:13],2,mean) ma3=apply(md3[,1:13],2,mean) ma;ma1;ma2;ma3

mean(ma);mean(ma1);mean(ma2);mean(ma3) #聚类结果交叉分析 table(md$SEX,cclust) table(gage,cclust) table(md$MAR,cclust) table(md$POST,cclust) table(md$DEPT,cclust) #分类预测

82

暨南大学硕士学位论文

#Knn算法 library(class) mdctrain=mdc[,1:13] mdctest=mdc[,1:13] cltest=mdc[,19]

pred=knn(mdctrain, mdctest, cltest, k = 5, prob=TRUE) summary(pred) table(cltest,pred) #CART算法 library(tree)

cclust=as.factor(cclust) mdp=cbind(md[,1:13],cclust) mdp.tr=tree(cclust~.,mdp) mdp.tr

summary(mdp.tr) plot(mdp.tr);text(mdp.tr) #C4.5 library(RWeka) library(party)

oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=0.05) m1 <- J48(cclust ~ ., data = mdp) m1

table(mdp$cclust, predict(m1)) write_to_dot(m1)

if(require(\"party\ plot(m1) #nnet library(nnet)

mdp.nnet <- nnet(cclust ~ ., data = mdp, size =2, rang = 0.1, decay = 5e-4, maxit = 500) table(mdp$cclust, predict(mdp.nnet, mdp, type = \"class\"))

83

基于数据挖掘的分类和聚类算法研究及R语言实现

附录4 由CART算法得到的分类规则

节点） 分割属性 记录数 离差 所属类别 （各类别的概率）*表示最终节点

1) root 501 1061.000 1 ( 0.46906 0.25150 0.27944 ) 2) M09 < 2.5 220 298.400 3 ( 0.413 0.00000 0.58636 ) 4) M01 < 2.5 130 118.200 3 ( 0.16923 0.00000 0.83077 ) 8) M12 < 1.5 67 0.000 3 ( 0.00000 0.00000 1.00000 ) * 9) M12 > 1.5 63 81.520 3 ( 0.34921 0.00000 0.65079 ) 18) M13 < 2.5 49 46.740 3 ( 0.18367 0.00000 0.81633 ) 36) M08 < 2.5 26 0.000 3 ( 0.00000 0.00000 1.00000 ) * 37) M08 > 2.5 23 30.790 3 ( 0.39130 0.00000 0.60870 ) * 19) M13 > 2.5 14 7.205 1 ( 0.92857 0.00000 0.07143 ) * 5) M01 > 2.5 90 97.790 1 ( 0.76667 0.00000 0.23333 ) 10) M13 < 1.5 21 26.730 3 ( 0.33333 0.00000 0.66667 ) 20) M01 < 3.5 12 0.000 3 ( 0.00000 0.00000 1.00000 ) * 21) M01 > 3.5 9 9.535 1 ( 0.77778 0.00000 0.22222 ) * 11) M13 > 1.5 69 45.300 1 ( 0.855 0.00000 0.10145 ) 22) M04 < 2.5 20 24.430 1 ( 0.70000 0.00000 0.30000 ) * 23) M04 > 2.5 49 9.763 1 ( 0.97959 0.00000 0.02041 ) * 3) M09 > 2.5 281 466.000 1 ( 0.51246 0.44840 0.03915 ) 6) M09 < 3.5 148 1.300 1 ( 0.790 0.14865 0.06081 ) 12) M02 < 3.5 68 53.150 1 ( 0.86765 0.00000 0.13235 ) 24) M08 < 2.5 5 5.004 3 ( 0.20000 0.00000 0.80000 ) * 25) M08 > 2.5 63 34.930 1 ( 0.92063 0.00000 0.07937 ) 50) M01 < 2.5 17 20.600 1 ( 0.70588 0.00000 0.29412 ) * 51) M01 > 2.5 46 0.000 1 ( 1.00000 0.00000 0.00000 ) * 13) M02 > 3.5 80 94.110 1 ( 0.72500 0.27500 0.00000 ) 26) M13 < 3.5 56 45.930 1 ( 0.85714 0.14286 0.00000 ) * 27) M13 > 3.5 24 32.600 2 ( 0.41667 0.58333 0.00000 ) * 7) M09 > 3.5 133 1.100 2 ( 0.20301 0.78195 0.01504 ) 14) M04 < 3.5 88.0 2 ( 0.44444 0.51852 0.03704 ) 28) M03 < 3.5 21 29.780 1 ( 0.76190 0.14286 0.09524 ) * 29) M03 > 3.5 33 36.550 2 ( 0.24242 0.75758 0.00000 ) * 15) M04 > 3.5 79 25.510 2 ( 0.03797 0.96203 0.00000 ) *

注：例如 8) M12 < 1.5 67 0.000 3 ( 0.00000 0.00000 1.00000 ) * 表示第8个节点在M12上分割，M12<1.5 的记录有67个，离差为0，属于第3类（低离职群），*表示此节点是最终节点

84

暨南大学硕士学位论文

附录5 由C4.5算法得到的分类规则

M09 <= 2 | M13 <= 2 | | M01 <= 2

| | | M10 <= 1: 3 (100.0/3.0) | | | M10 > 1

| | | | M08 <= 2: 3 (4.0) | | | | M08 > 2: 1 (8.0/2.0) | | M01 > 2 | | | M12 <= 2 | | | | M05 <= 3

| | | | | M13 <= 1: 3 (14.0/1.0) | | | | | M13 > 1 | | | | | | M03 <= 2

| | | | | | | M02 <= 3: 3 (4.0) | | | | | | | M02 > 3

| | | | | | | | M07 <= 4: 1 (2.0) | | | | | | | | M07 > 4: 3 (2.0) | | | | | | M03 > 2: 1 (9.0/1.0) | | | | M05 > 3: 1 (6.0) | | | M12 > 2: 1 (18.0/1.0) | M13 > 2

| | M08 <= 1: 3 (3.0) | | M08 > 1

| | | M02 <= 1: 3 (3.0/1.0) | | | M02 > 1: 1 (47.0) M09 > 2 | M09 <= 3 | | M02 <= 3

| | | M02 <= 1: 3 (3.0) | | | M02 > 1

| | | | M08 <= 2: 3 (5.0/1.0) | | | | M08 > 2: 1 (60.0/2.0) | | M02 > 3 | | | M12 <= 4

| | | | M06 <= 2: 1 (20.0) | | | | M06 > 2 | | | | | M06 <= 4

| | | | | | M10 <= 1: 1 (17.0) | | | | | | M10 > 1 | | | | | | | M08 <= 4 | | | | | | | | M02 <= 4

85

基于数据挖掘的分类和聚类算法研究及R语言实现

| | | | | | | | | M13 <= 3: 1 (17.0/2.0) | | | | | | | | | M13 > 3: 2 (4.0/1.0) | | | | | | | | M02 > 4

| | | | | | | | | M12 <= 2: 1 (2.0) | | | | | | | | | M12 > 2: 2 (6.0/1.0) | | | | | | | M08 > 4: 2 (2.0) | | | | | M06 > 4: 2 (2.0) | | | M12 > 4

| | | | M11 <= 2: 1 (2.0) | | | | M11 > 2: 2 (8.0) | M09 > 3 | | M13 <= 2

| | | M08 <= 3: 3 (2.0) | | | M08 > 3 | | | | M09 <= 4

| | | | | M11 <= 3: 1 (11.0) | | | | | M11 > 3: 2 (3.0/1.0) | | | | M09 > 4: 2 (3.0/1.0) | | M13 > 2 | | | M03 <= 3 | | | | M04 <= 3

| | | | | M13 <= 4: 1 (10.0/1.0) | | | | | M13 > 4: 2 (3.0/1.0) | | | | M04 > 3: 2 (7.0) | | | M03 > 3 | | | | M04 <= 2

| | | | | M07 <= 4: 2 (3.0) | | | | | M07 > 4: 1 (2.0) | | | | M04 > 2: 2 (.0/2.0)

注：M10 <= 1: 3 (100.0/3.0) 表示在M10节点上分枝，M10<=1 的属于第3类，共有100个记录，其中有3个是其它类别被错分到第3类。

86

暨南大学硕士学位论文

在学期间发表论文及出版著作清单

1、货车超载背后的经济因素分析 发表在《中国统计》2006.11 2、多种抽样框误差的模型表示 发表在《统计与决策》2006.12 3、抽样框误差的测量和控制研究 发表在《统计与决策》2007.3 4、《R语言统计分析软件教程》 中国文化教育出版社，2007.1

5、《全面建设小康社会的必由之路－广东省城镇化进程研究》 经济科学出版社，2006.3

87

基于数据挖掘的分类和聚类算法研究及R语言实现

致谢

时间飞逝，转眼之间在暨南大学度过我的六年光阴，在这六年里我学习勤奋刻苦，图书馆、经济学院、成教搂、金陵1三楼自习室等地方度过了我无数的日日夜夜，想起考研、考博的时光，我经常在这些地方奋战到深夜，虽然辛苦，但现在想来更多的是充实和喜悦之情。 首先，衷心感谢我的导师王斌会教授，在我研究生学习期间给了我悉心的指导和无微不至的关怀，他以严谨的治学态度、勤奋的工作精神深深地感染着我。无论是在平时的科研活动还是毕业论文的撰写过程中，他都给予了我耐心的指导和帮助。在我研究过程中感到迷茫的时候，他以深厚的学术功底以及敏锐的洞察力给我启发、指明了研究的方向，使我顺利完成我的研究工作。

此外，在我的研究生学习期间，韩兆洲院长、郑少智副院长、统计系主任刘建平教授、雷钦礼教授、郭海华副教授、尹居良副教授、柳向东副教授、刘潇老师、彭向东、伍郁民老师、徐亚平老师以及其他老师都给予了我有益的指导和帮助，使我学到了许多知识，受益匪浅。在此一并表示衷心的感谢！

另外，还要感谢统计系的全体同学，在我学习期间对我学习、工作上的帮助！ 最后要感谢我的家人在我遇到困难时给予我莫大的帮助和鼓励！

再次感谢所有关心和支持过我的老师、同事、同学和家人，谨以此文作为献给他们的礼物! 由于水平有限，论文中难免有错漏之处，希望各位评阅老师不吝指教！

方匡南

88

暨南大学硕士学位论文

2007年4月25于暨南大学