数据挖掘原理与算法教案

数据挖掘原理与算法教案

讲授：王志明

w3z2m

湖南农业大学理学院信息科学系

-来源网络，仅供个人学习参考

第一章绪论

教学目的：掌握数据挖掘的概念，背景，基本理论，基本应用，发展趋势

教学重点难点：数据挖掘的概念，粗糙集方法

教学课时：2 教学过程： 一、概念

数据挖掘(Datamining)属一交叉学科，融合了数据库技术(Database)，人工智能(ArtificialIntelligence)，机器学习(MachineLearning)，统计学(Statistics)，知识工程(KnowledgeEngineering),面向对象方法(Object-OrientedMethod)，信息检索(InformationRetrieval)，高性能计算(High-PerformanceComputing)以及数据可视化（DataVisualization）等技术。 联机事物处理（OnLineTransactionProcessing，OLTP）是在网络环境下的事务处理工作，以快速的响应和频繁的数据修改为特征，使用户利用数据库能够快速地处理具体的业务。 知识：广义讲就是数据、信息的表现形式。人们常把概念、规则、模式、规律和约束等看成知识。 数据挖掘：又称数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD),就是从大量数据中获取有效地、新颖的、潜在有用的、最终可理解的模式的非平凡过程。简单的说就是从大量数据中提取或挖掘知识。 数据仓库是面向主题的、集成的、稳定的，不同时间的数据集合，用于支持经营管理中决策制定过程。 二、数据挖掘产生与发展 1）查询、统计、报表等简单传统的数据处理无法获取知识。这样促使数据挖掘技术的发展。利用数据仓库存储数据。 2）数据挖掘技术产生的技术背景：（1）数据库、数据仓库、Internet等信息技术的发展；(2)计算机性能的提升；(3)统计学和人工智能等数据分析方法的应用。

3）数据挖掘技术发展应用以及重点需要的研究的方面： （1）商业中的应用 （2）与特定数据存储类型的适应问题 （3）大型数据的选择与规格化问题

（4）数据挖掘系统的构架与交互式挖掘技术 （5）数据挖掘语言与系统的可视化问题

（6）数据挖掘理论与算法研究 三、数据挖掘的分类

见书P11

-来源网络，仅供个人学习参考

四、广义知识挖掘

1、概念描述，包括特征性描述和区别性描述 2、数据分析，如求和，计数，平均，最大值等

3、多层次概念描述

（1）模式分层；（2）集合分组分层；（3）操作导出层；（4）基于规则分层

五、类知识挖掘

1、分类：决策树、贝叶斯分类、神经网络、遗传算法与进化理论、类比学习、

粗糙集、模糊集等

2、聚类：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法 六、预测型知识挖掘 1、趋势预测分析 2、周期分析模式 3、序列模式 4、神经网络 七、粗糙集方法 粗糙集（RoughSet）是波兰数学家Z.Pawlak于1982年提出的。粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。它用上、下近似（upperapproximation,lowerapproximation）两个集合来逼近任意一个集合，该集

合的边界线区域被定义为上近似集和下近似集之差集。 1、等价 粗糙集把客观世界抽象为一个信息系统，一个信息系统是一四元组S=(U，A，V，

f)的定义为: U:是一个非空有限对象(元组)集合, U={x1x2…xn},其中xi为对象(元组)。 A:是对象的属性集合,A={A1,A2,…,An},A常分为两个不相交的子集,即条件属性C和决策属性D,ACD V:是属性值的集合，V={V1,V2,…,Vn},Vi是Ai的值域。 f：是信息函数，f:UAV,f(xi,Aj)Vj

对于A中任意一个属性a,若两记录ei和ej它们的属性值相同，称ei和ej是对属性a的等价关系。属于同一等价关系的归位一个等价类。

2、上近似和下近似

1、设U是对象（事例）的集合U={x1x2…xn}；B是属性集A的子集，R(B)是U

-来源网络，仅供个人学习参考

上的二元等价关系，

R(B){(x1,x2)|f(x1,b)f(x2,b),bB}，

若对任意集合O，B是属性集A的子集，则O的下近似定义为：

BO{xU|[x]R(B)O},这里[x]R(B)表示x在R(B)上的等价类。

上近似定义为：BO{xU|[x]R(B)O},

3、约简

设有两属性集B1,B2,B1是B2的真子集，如果R(B1)R(B2)，则称B2可归约为B1，若属性

集B不可归约，则称B为U的一个约简或归约子。 4、依赖度 设有两属性集P和Q，则P对Q的属性依赖度定义为： rp(Q)#posp(Q)#U，其中posp(Q)xR(Q)*PX，PX表示集合X在属性集上的下近似。

设BC，C是条件属性和D是决策属性,则属性重要度定义为： 全集U可以划分为三个不相交的区域，即正域（Pos），负域（NEG）和边界（BND）：

从上面可见：A(X)A(X)BNDA(X) 用图说明正域、负域和边界，每一个小长方形表示一个等价类。

正域、负域和边界 NEG（X） A(X)Pos（X）= X BND（X） 正域 负域 边界

5、粗糙集

若A(X)A(X)，即BND(X)，即边界为空，称X为A的可定义集；否则X为A

不可定义的，即A(X)A(X)，称X为A的Rough集（粗糙集）。

6、规则的提取 通过分析U中的两个划分C{Ei}和D{Yj}之间的关系，把C视为分类条件，D

-来源网络，仅供个人学习参考

视为分类结论，我们可以得到下面的分类规则：

1）当EiYj，则有：rij：Des(Ei)Des(Yj)

Des(Ei)和Des(Yj)分别是等价集Ei和等价集Yj中的特征描述。

2）当EiYjEi时（Ei完全被Yj包含）即下近似，建立的规则rij是确定的，规则

的可信度cf=1.0。

3）当EiYjEi时（Ei部分被Yj包含）即上近似，建立的规则rij是不确定的，规则的可信度为： cf=EiYj Ei4)当EiYj时（Ei不被Yj包含），Ei和Yj不能建立规则。 7、举例(汽车数据) Power Turbo Weight ID Power Turbo Weight high yes med 6 medium yes light low no light 7 low no heavy medium yes light 8 high no heavy high no light 9 high yes med high yes med 10 low no heavy U={1,2,3,4,5,6,7,8,9,10} A={power,turbo,weight} V={low,high,medium,yes,no,light,heavy,med} C={power,turbo},D={weight} 按照C，则U分为： E1={1，5，9}，E2={2，7，10}，E3={3，6}，E4={4，8}

按照D，则U可分为

Y1={1,5,9},Y2={7,8,10},Y3={2,3,4,6}

P28

八、数据挖掘的应用

1、CRM（客户关系管理）的应用

2、体育竞技中的应用 3、商业银行的应用

ID 1 2 3 4 5 -来源网络，仅供个人学习参考

4、电信中的应用 5、科学探索中的应用 6、信息安全中的应用

-来源网络，仅供个人学习参考

第二章

教学目的：掌握知识发现过程以及数据处理有关概念的概念，基本应用

教学重点难点：知识发现技术要点、过程模型处理

教学课时：3 教学过程： 一、知识发现过程 1、大概过程

（1）问题定义阶段 （2）数据抽取阶段 目标数据（TargetData），是根据用户的需要从原始数据库中选取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。数据转换的主要目的是完成数据类型转换。尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。 （3）数据挖掘 首先要确定挖掘的任务或目的，如数据分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。实施数据挖掘算法，获取有用的模式 （4）知识评估阶段 获取的模式经过评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求。把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if...then…”规则。 2、数据清洗与预处理 目标数据（TargetData），是根据用户的需要从原始数据库中选取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。数据转换的主要目的是完成数据类型转换。尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。 二、数据库中的知识发现处理过程模型 1、阶梯处理过程模型

-来源网络，仅供个人学习参考

KDD过程

数据准备 数据挖掘 结果评价

结果表达和解释 数据挖掘 数据转换 预处理 数据选择 数据集成 目标数据 数据 数据源 转换数据 预处理后 数据 模式 知识 2、螺旋处理过程模型 G.H.John提出 定义问题 抽取数据 清洗数据 数据工程 算法工程 运行挖掘算法 分析结果

3、以用户为中心的处理模型

Brachman和Anand从用户角度对KDD处理过程进行了分析。

任务发现 数据发现 数据清洗

-来源网络，仅供个人学习参考

模型开发 数据分析 输出结果生成 4、联机KDD模型

传统数据挖掘的缺陷：（1）过分强调自动化，忽视交互性，导致用户对数据挖掘过程参与过程困难；（2）数据挖掘算法对用户是一个“黑盒”，只有在算法挖掘结束后，用户才能评价发现的模式，若对模式不满意，则重复挖掘过程，消耗资源；（3）传

统数据挖掘过程只能一次对一个数据集进行挖掘。

OLAM（OnLineAnalyticalMining）联机分析挖掘由OLAP发展而来。被分为几个层次： （1） L0层：数据集，包含了相关的数据库和数据仓库。 （2） L1层：形成支持OLAP和OLDM的数据集，主要由元数据集和数据立方体。 （3） L2层：是OLAP和OLDM的应用层，包含相互关联并协同工作的OLAM引擎

和OLAP引擎。L2接受数据挖掘请求，通过访问数据和元数据，完成数据挖掘和分析工作。 （4） L3层：是一个用户接口层，它主要承担用户请求的理解与挖掘结果的解释和表达等。 三、知识发现软件和工具的发展 1、的知识发现软件 2、横向的知识发现工具集(P52) DBMiner,Quest,IBMIntelligentMiner,Darwin,ReMind 3、纵向的知识发现解决方案 如证券系统的趋势预测；银行和电信行业的欺诈行为检测；基因分析系统中的DNA

识别等 4、KDD系统介绍 Quest： QUEST是IBM公司Almaden研究中心开发的一个多任务数据挖掘系统，目的是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有如下特点： 提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列模式发

现、时间序列聚类、决策树分类、递增式主动开采等。

各种开采算法具有近似线性（O(n)）计算复杂度，可适用于任意大小的数据库。

算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。

为各种发现功能设计了相应的并行算法。

DBMiner：

-来源网络，仅供个人学习参考

DBMiner是加拿大SimonFraser（加拿大名校-西蒙菲沙大学）大学开发的一个多任务数据挖掘系统，它的前身是DBLearn。该系统设计的目的是把关系数据库和数据开采集成在一起，以面向属性的多级概念为基础发现各种知识。DBMiner系统具有如下

特色：

能完成多种知识的发现：泛化规则、特性规则、关联规则、分类规则、演化知

识、偏离知识等。

综合了多种数据开采技术：面向属性的归纳、统计分析、逐级深化发现多级规

则、元规则引导发现等方法。

提出了一种交互式的类SQL语言——数据开采查询语言DMQL。

能与关系数据库平滑集成。 实现了基于客户/服务器体系结构的Unix和PC（Windows/NT）版本的系统。

四、知识发现项目的过程化管理（略） 五、数据挖掘语言介绍 -来源网络，仅供个人学习参考

第三章关联规则挖掘理论和算法

教学目的：掌握关联规则挖掘的概念，背景知识，了解常见关联规则挖掘的数据挖

掘算法

教学重点难点：关联规则挖掘常见算法

教学课时：6 教学过程：

关联规则挖掘最早由Agrawal于1993年提出，目的是发现交易数据库中不同商品

（项）之间的联系，这些规则找出顾客购买行为模式。

一、概念： 事务数据库：设I{i1,i2,...,im}是项（Item）的集合。记D{t1,t2,...,tn}为事务（Transaction）的集合（事务数据库），每个事务ti都对应I上的一个子集。 支持度：设I1I，项目集I1在数据集D上的支持度(support)是包含I1的事务在{tD|I1t}D中所占的百分比，即：support(I1)= D频繁项目集：对项目集I和事务数据库D，T中所有满足用户指定的最小支持度(minsupport)的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集(FrequentItemsets)或者大项目集(LargeItemsets)。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集(MaximumFrequentItemsets)或最大项目集(MaximumLargeItemsets)。 规则的可信度：一个定义在I和D上的形如I1I2的关联规则通过满足一定的可信度、信任度或置信度(Confidence)来给出，所谓可信度是指包含I1和I2的事务数与包含I1的事务数之比，即confidence(I1I2)P(I2/I1)I1,I2I,I1I2 support(I1I2)，其中support(I1)强关联规则：D在I上满足最小支持度和最小信任度的关联规则成为强关联规则（StrongAssociationRule） 我们一般所说的关联规则指强关联规则。一般地，给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。其划分为两个小问题：

（1） 发现频繁项目集：找出支持度大于最小支持度的项集，即频繁项集。 （2） 生成关联规则：根据定义，这些规则必须满足最小支持度和最小可信度。 例子：例子：讨论不购买商品与购买商品的关系。设交易集D，经过对D的分析，得

到表格:

买咖啡 不买咖合-来源网络，仅供个人学习参考

啡 买牛奶 20 不买牛70 奶 合计 90 10 100 5 75 5 计 25 设定minsupp=0.2,minconf=0.6,得到如下的关联规则： 买牛奶→买咖啡s=0.2 c=0.8 即80％的人买了牛奶就会买咖啡。 同时得到结论：90％的人肯定会买咖啡。 规则 买咖啡→不买牛奶s=0.7 c=0.78 支持度和可信度分别为0.7和0.78，更具有商业销售的指导意义。

二、经典的频繁项目集的生成算法 1、项目集空间理论 定理1频繁项集的所有非空子集都必须也是频繁的。 定理2非频繁项目集的超集是非频繁项目集。 2、Apriori算法 1、Apriori使用一种称作逐层搜索的迭代方法，“K-项集”用于探索“K+1-项集”。首先，找出频繁“1-项集”的集合。该集合记作L1。L1用于找频繁“2-项集”的集合L2，而L2用于找L3，如此下去，直到不能找到“K-项集”。找每个LK需要一次数据库扫描。 2、“K-项集”产生“K+1-项集” 设K-项集LK，K+1项集LK+1，产生LK+1的候选集CK+1。有公式：

CK+1=LKLK={XY，其中X，YLK，

|XY|=K+1}

其中C1是1-项集的集合，取自所有事务中的单项元素。

如：如L1={{A}，{B}}

C2={A}{B}={A，B}，且|AB|=2

L2={{A，B}，{A，C}}

C3={A，B}{A，C}={A，B，C}，且|ABC|=3

-来源网络，仅供个人学习参考

例1见P72

例2生成频繁项目集过程:

事务ID T1 T2 T3 T4 T5 T6 T7 T8 T9 事务的项目集 A,B,E B,D B,C A,B,D A,C B,C A,C A,B,C,E A,B,C 解: 1)在算法的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法扫描所有的事务，对每个项的出现次数计数。见图中第1列。 2)假定最小事务支持计数为2 （即min-sup=2/9=22%），可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。见图中第2列。

3)为发现频繁2-项集的集合L2，算法使用L1*L1来产生候选集C2。见图中第3列。 4)扫描D中事务，计算C2中每个候选项集的支持度计数，如图中的第4列。 5)确定频繁2-项集的集合L2，它由具有最小支持度的C2中的候选2-项集组成。见

图第5列

6)候选3-项集的集合C3的产生，得到候选集：

C3={{A，B，C}，{A，B，E}，{A，C，E}，{B，C，D}，{B，C，E}，{B，D，E}} 按Apriori性质，频繁项集的所有子集必须是频繁的。由于{A，D}，{C，D}，{C，

-来源网络，仅供个人学习参考

E}，{D，E}不是频繁项集，故C3中后4个候选不可能是频繁的，在C3中删除它们。

见图第6列。

扫描D中事务，对C3中的候选项集计算支持度计数，见图第7列。 7)确定L3，它由具有最小支持度的C3中候选3－项集组成，见图第8列。 8）按公式产生候选4－项集的集合C4，产生结果{A,B,C,E},这个项集被剪去，因为它的子集｛B,C,E｝不是频繁的。这样L4=Ф。此算法终止。L3是最大的频繁项集，

即：｛A,B,C｝和｛A,B,E｝。

3、定理:设项目集X，X1是X的一个子集，如果规则X->（l-X）不是强规则，那么

X1->(l-X1)一定不是强规则。 4、定理：设项目集X，X1是X的一个子集，如果规则Y->X是强规则，那么规则Y->X1

一定是强规则。 三、Apriori算法的性能瓶颈问题 1）多次扫描事务数据库，需要很大的I/O负载 2）可能产生庞大的候选集 四、Apriori算法改进 1、基于数据分割的方法 1）合理利用主存空间 2）支持并行挖掘算法 2、基于散列(Hash)的方法 Hash，一般翻译做“散列”，也有直接音译为”哈希“的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值.也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。 1995年，Park等提出一个基于散列技术的产生频繁项目集的算法。他们通过试验发现寻找频繁项目集的主要计算是在生成2-频繁项目集L2上。

例P75

3、基于采用（Sampling）的方法

1996年，Toivonen提出一个基于采用技术产生频繁项目集的算法。其思想是：先使用数据库的抽样数据得到一些可能成立的规则，然后利用数据库的剩余部分验证这些关联规则是否正确。有点是简单且显着降低因为挖掘所付出的I/O的代价。

缺点是抽样数据的选取以及由此而产生的结果的偏差过大。

-来源网络，仅供个人学习参考

五、对项目集空间理论的发展

随着数据库容量的增大，重复访问数据库将导致性能的低下，因此，探索新的理论和算法减少数据库的扫描次数和候选集空间的占用，采用并行挖掘等方式提高数据

挖掘效率已经成为研究的热点之一。 1、探索新的管理规则挖掘理论 2、提高裁减项目集格空间的效率

3、分布和并行环境下的关联规则挖掘问题

1）Close算法

在close算法中，也使用了迭代的方法：利用频繁闭合i-项目集记为FCi，生成频繁闭合(i+1)-项目集，记为FCi+1（i>=1）。首先找出候选1-项目集，记为FCC1，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集，然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1.再将它与自身链接，以得到候选项频繁闭合2-项目集FCC2，再经过修剪得到FC2，，再利用FC2推出FC3，如此下去，直到有某个值r使得候选频繁频繁闭合r-项目集FCCr

为空，这时算法结束。 例P80 其余算法略。 八、改善关联规则挖掘质量问题 衡量关联规则挖掘结果的有效性应该多方面考虑： 1） 准确性：挖掘出的规则必须反映数据的实际情况。 2） 实用性：挖掘出的规则必须是间接可用的，而且是针对挖掘目标的。

3） 新颖性：挖掘出的关联规则可以为用户提供新的有价值信息。 可以在用户主观和系统主观两个层面上考虑关联规则挖掘的质量问题。

1、用户主观层面 约束数据挖掘可以为用户参与知识发现工作提供一种有效的机制。

1） 知识类型的约束 2） 数据的约束 3） 维/层次约束 4） 知识内容的约束 5） 针对具体知识类型的约束

2、系统客观层面 九、约束数据挖掘问题 1、约束在数据挖掘中的作用 1）聚焦挖掘任务，提高挖掘效率

2）保证挖掘的精确性

-来源网络，仅供个人学习参考

3）控制系统的使用和规模

2、约束的类型

-来源网络，仅供个人学习参考

第四章分类方法

教学目的：掌握分类的概念，背景，基本理论，基本应用，发展趋势和常见分类算

法

教学重点难点：分类算法

教学课时：4 教学过程：

分类是数据挖掘中一项非常重要的任务，分类的目的是学会一个分类函数或者分类模型（常称为分类器），该模型能把数据库中的数据项映射到给定类别中的某一

类中。分类器的构造方法常见有：统计方法、机器学习、神经网络等。

统计方法：贝叶斯法、非参数法 机器学习方法：决策树法、规则归纳法 神经网络方法：BP算法 另外还有粗糙集、支持向量机等。 一、分类的基本概念 定义：给定一个数据库D{t1,t2,...,tn}和一组类C{C1,C2,...,Cm}，分类问题就是确定一个映射f:DC，每个元组ti被分配到一个类中，一个类Cj包含映射到该类中的所有元组，即Cj{ti|f(ti)Cj,1in,tiD}。 例如：见P115 一般，数据分类(DataClassification)分为两个步骤： （1）建立模型，描述预订的数据类集或概念集 训练数据集中的每个元组称为训练样本，是从样本中抽取的，训练又分有指导学习和无指导学习。 （3） 使用模型进行分类 二、基于距离的分类算法 1、定义：给定一个数据库D{t1,t2,...,tn}和一组类C{C1,C2,...,Cm}，对于任意的元组ti{ti1,ti2,...,tik}D,如果存在一个Cj，使得

则ti被分配到类Cj中，其中sim(ti,Cj)称为相似性。

实际中常用距离来表征，距离越近，相似性越大，距离越远，相似性越小。

例子P117

2、KK最近邻(k-NearestNeighbor，KNN)分类算法

K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，

-来源网络，仅供个人学习参考

也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更

为适合。

KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。 该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 例子P119 三、决策树分类 决策树是另外一种有效的生成分类器的方法。决策树方法采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向下的分支，在决策树的叶节点得到结论。故从决策树的根到叶节点的一条路径对应着一条合取规则。 基于决策树的分类算法的一个最大优点就是它在学习过程中不需要使用者了解很多背景知识（同时这也是其最大缺点），只要训练集能够用属性-结论表示出来就能用该算法学习。

例如：

则可以的决策树如下（算法以后再说）：

1、信息论概念

（1）信道模型

一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信

-来源网络，仅供个人学习参考

道）三者组成。

信源 U 信道 P(V/U) 信宿 V

(2)在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性，表示成 信息熵H（U） 在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。 如果干扰很小，不会对传递的信息产生任何可察觉的影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。 先验不确定性不能全部被消除，只能部分地消除。在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性，用条件熵表示H（U/V）。后验不确定性总要小于先验不确定性: H（U/V）＝H（U）－H（U/V） (3)互信息的计算

（a）设S为训练集，有n个特征（属性），表示为（A1，A2，...,An）。｜S｜表示例

子总数。

-来源网络，仅供个人学习参考

（b）S中有U1，U2两类。｜Ui｜表示Ui类例子数。 （c）特征Ak处有m个取值，分别为（V1，V2，...，，Vm）。 则Ui类出现概率为:P（Ui）=｜Ui｜/｜S｜，有p(Ui)1

i12Ui类中在特征Ak处取值Vj的例子集合Vij的条件概率为:P（Vj｜Ui）=｜Vij｜/｜Ui｜，

有p(Vj/Ui)1。

j1m在特征Ak处，取Vj值的例子集合的概率为:P（Vj）=｜Vj｜/｜S｜，有p(Vj)1j1m 在特征Ak处取Vj值的例子，属于Ui类的例子集合Uij的条件概率为:P（Ui｜Vj）=｜

Uij｜/｜Vj｜，则p(Ui/Vj)1 i12(C)自信息:消息Ui发生后所含有的信息量。它反映了消息Ui发生前的不确定性（随机性）。定义为： 以2为底，所得的信息量单位为bit。以e为底，所得的信息量单位为nat. (D)信息熵:自信息的数学期望。即信源输出后，每个消息所提供的信息量，也反映了信源输出前的平均确定性。定义为: 例如： X a1 a2 P(X) 0.99 0.01 Y b1 b2 P(Y) 0.5 0.5 则信息熵分别为: H（X）=-0.99log0.99-0.01log0.01=0.08bit H（Y）=-0.5log0.5-0.5log0.5=1bit 可见 H（Y）>H（X） 故信源Y比信源X的平均不确定性要大。

(E)平均互信息

定义为：I(U,V)=H（U）-H(U|V)

I（U,V）称为U和V之间的平均互信息.它代表接收到符号集V后获得的关于U的信

息量。

可见，熵（H（U）、H（U|V））只是平均不确定性的描述。熵差（H（U）-H（U|V））

是不确定性的消除，即互信息才是接收端所获得的信息量。

对输入端U只有U1，U2两类，互信息的计算公式为:

-来源网络，仅供个人学习参考

I(U,V)=H（U）-H(U|V)

决策树算法步骤：决策树生成和决策树修剪。

2、决策树生成算法

构造决策树的方法是采用自上而下的递归构造。 （1） 以代表训练样本的某个节点开始建树；

（2） 如果样本的哦偶在同一类中，则该节点成为树叶，并用该类标记； （3） 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最

好地将样本分类的属性。该属性成为该节点的“测试”或“判定”属性。

3、ID3算法 （1）主算法 ⒈从训练集中随机选择一个既含正例又含反例的子集（称为\"窗口\"）； ⒉用“建树算法”对当前窗口形成一棵决策树； ⒊对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；

⒋若存在错判的例子，把它们插入窗口，转2，否则结束。 主算法流程用下图表示。其中PE、NE分别表示正例集和反例集，它们共同组成训练集。PE’，PE’’和NE’，NE’’分别表示正例集和反例集的子集。主算法中每迭代循环一次，生成的决策树将会不相同。 训练集 PE、NE 取子集建窗口 窗口 PE`、NE` 生成决策树 测试PE、NE 扩展窗口 PE`=PE`+PE``NE`=NE`+NE`` 是 存在错判的 PE``，NE``吗 否 此决策树为最后结果 (2)建树算法

⒈对当前例子集合，计算各特征的互信息；

-来源网络，仅供个人学习参考

⒉选择互信息最大的特征Ak；

⒊把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；

⒋对既含正例又含反例的子集，递归调用建树算法；

⒌若子集仅含正例或反例，对应分枝标上P或N，返回调用处。

例： NO. 属性 类别 天气 气温 湿度 风 1 晴 热 高 无风 N 2 晴 热 高 有风 N 3 多云 热 高 无风 P 4 雨 适中 高 无风 P 5 雨 冷 正常 无风 P 6 雨 冷 正常 有风 N 7 多云 冷 正常 有风 P 8 晴 适中 高 无风 N 9 晴 冷 正常 无风 P 10 雨 适中 正常 无风 P 11 晴 适中 正常 有风 P 12 多云 适中 高 有风 P 13 多云 热 正常 无风 P 14 雨 适中 高 有风 N 解：⒈信息熵的计算 信息熵：H(U)P(ui)logP(ui) i类别出现概率：P(ui|i)|u|S|，对9个正例和5个反例有：P（u1）=9/14 =5/14

H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit

⒉条件熵计算

条件熵：H(U/V)P(vj)P(ui/vj)logP(ui/vj)

ji属性A1取值Vj时，类别Ui的条件概率：P(ui/vj)|ui||v|。 jA1=天气取值v1=晴，v2=多云，v3=雨

在A1处取值晴的例子5个，取值多云的例子4个，取值雨的例子5个，故：-来源网络，仅供个人学习参考

P（u2）

P（v1）=5/14P（v2）=4/14P（v3）=5/14

取值为晴的5个例子中有2个正例、3个反例，故：

P（u1/v1）=2/5，P（u2/v1）=3/5 同理有：P（u1/v2）=4/4，P（u2/v2）=0

P（u1/v3）=2/5，P（u2/v3）=3/5

H(U/V)=(5/14)((2/5)log(5/2)+(3/5)log(5/3))+(4/14)((4/4)log(4/4)+0)+(5/14

)((2/5)log(5/2)+(3/5)log(5/3))=0.694bit

⒊互信息计算 对A1=天气处有： I（天气）=H（U）-H（U|V）=0.94-0.694=0.246bit 类似可得： I（气温）=0.029bit I（湿度）=0.151bit I（风）=0.048bit ⒋建决策树的树根和分枝 ID3算法将选择互信息最大的特征天气作为树根，在14个例子中对天气的3个取值

进行分枝，3个分枝对应3个子集，分别是: F1={1，2，8，9，11}，F2={3，7，12，13}，F3={4，5，6，10，14} 其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。 ⒌递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息. （1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。

（2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分

枝标记P。

这样就得到下图的决策树。 4、对ID3的讨论

ID3在选择重要特征时利用了互信息的概念，算法的基础理论清晰，使得算法较

简单，是一个很有实用价值的示例学习算法。

该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。有人曾用4761个关于苯的质谱例子作了试验。其中正例2361个，反例2400个，每个例子

-来源网络，仅供个人学习参考

由500个特征描述，每个特征取值数目为6，得到一棵1514个结点的决策树。对正、反例各100个测试例作了测试，正例判对82个，反例判对80个，总预测正确率81%，

效果是令人满意的。

缺点：

（1）互信息的计算依赖于特征取值的数目较多的特征，这样不太合理。一种简单的办法是对特征进行分解，如上例中，特征取值数目不一样，可以把它们统统化为二值特征，如天气取值晴，多云，雨，可以分解为三个特征；天气—晴，天气—多云，天气—雨。取值都为“是”或“否”，对气温也可做类似的工作。这样就不

存在偏向问题了。 （2）用互信息作为特征选择量存在一个假设，即训练例子集中的正，反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同，这样计算训练集的互信息就有偏差。 （3）ID3在建树时，每个节点仅含一个特征，是一种单变元的算法，特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起，但联系还是松散的。 （4）ID3对噪声较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是特征值取错，二是类别给错。 （5）当训练集增加时，ID3的决策树会随之变化。在建树过程中，各特征的互信息会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。 -来源网络，仅供个人学习参考

天气

晴

多云

湿度 雨

风 P 高 正常 有风 无风

N P N P

ID3决策树

5、C4.5算法 ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3

基础上发展起来的决策树生成算法，由在1993年提出。 C4.5克服了ID3在应用中存在的不足，主要体现在以下几个方面：

(1)用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多

的属性的不足；

(2)在树构造过程中或者构造完成之后，进行剪枝；

(3)能够完成对连续属性的离散化处理；

(4)能够对于不完整数据的处理，例如未知的属性值；

(5)C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。

-来源网络，仅供个人学习参考

1.算法

设T为数据集，类别集合为{C1,C2,…,Ck}，选择一个属性V把T分为多个子集。设V有互不重合的n个取值{v1,v2,…,vn}，则T被分为n个子集T1,T2,…,Tn，这里

Ti中的所有实例的取值均为vi。

令：|T|为数据集T的例子数，|Ti|为v=vi的例子数，|Cj|=freq(Cj,T)，为Cj类的例

子数，|Cjv|是V=vi例子中，具有Cj类别例子数。

则有：

（1）类别Cj的发生概率：p(Cj)=|Cj|/|T|=freq(Cj,T)/|T|

（2）属性V=vi的发生概率：p(vi)=|Ti|/|T| （3）属性V=vi的例子中，具有类别Cj的条件概率：p(Cj|vi)=|Cjv|/|Ti|

Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，而C4.5采用属性的信息增益率（gainratio）来选择属性。 H(C)p(Cj)log(p(Cj))jj |Cj||T|log(|Cj||T|)(1)类别的信息熵：j1kfreq(Cj,T)|T|log2(freq(Cj,T)|T| )info(T)(2)类别条件熵 按照属性V把集合T分割，分割后的类别条件熵为： (3)信息增益（gain），即互信息 (4)属性V的信息熵 (5)信息增益率 C4.5对ID3改进是用信息增益率来选择属性。 理论和实验表明，采用“信息增益率”（C4.5方法）比采用“信息增益”（ID3

方法）更好，主要是克服了ID3方法选择偏向取值多的属性。 六、贝叶斯分类 一般来说分类是将未知样本分到预先已知类别的过程。常见的分类模型有神经网络模型、决策树模型、朴素贝叶斯分类模型等。在众多的分类模型中，基于贝叶斯定理的朴素贝叶斯模型应用极其广泛。 贝叶斯定理是英国着名数学家托马斯·贝叶斯于1763年提出来的。该定理使用统计学理论研究概率推导，即根据已经发生的事件来预测将来可能发生的事件，因此如果过去试验中事件的出现率已知，那么可以计算出未来试验中事件出现的概率。根据未来出现各种事件的概率的大小就可以判断各个事件发生的可能性，故贝叶斯

定理可以用来进行分类。

与其他模型相比，由于朴素贝叶斯模型基于贝叶斯理论，具有坚实的数学基础和稳定的分类效果，所需估计的参数很少，对缺失数据不太敏感，算法也比较简单，

-来源网络，仅供个人学习参考

因此用途甚广，如垃圾邮件过滤、人脸识别、图像去噪、入侵检测等。

<一>、贝叶斯定理

定义：设A,B是两个事件，且p(A)0，称

p(B/A)p(AB)(1) p(A)为在事件A发生的条件下事件B发生的概率。

由(1)式得A,B的联合概率公式p(AB)p(A)p(B/A)。

定义：设S为试验E的样本空间，B1,B2,,Bn为E的一组事件，若满足

(1)BiBj,ij,i,j1,2,,n；(2)B1B2,,BnS，则称B1,B2,,Bn为样本空间S的一

个划分。 定理：设试验E的样本空间为S，A为E的事件，B1,B2,,Bn为样本空间S的一个

划分且p(Bi)0(i1,2,,n)，则 p(A)p(B1)p(A/B1)p(Bn)p(A/Bn)(2) 称为全概率公式。 贝叶斯定理：设试验E的样本空间为S，A为E的事件，B1,B2,,Bn为样本空间S

的一个划分且p(Bi)0(i1,2,,n)，则 称为贝叶斯公式。 <二>、朴素贝叶斯分类器 为了详细论述朴素贝叶斯分类过程，我们先了解一些概念。 设每个样本数据具有m+1个属性，Ai(i1,2,,m)为条件属性，C为决策属性；aik表示第Ai个属性的第k个取值；cj是C的一个取值，表示第j类。另外，用A表示集合A中元素的个数。 所有样本数据的集合为A1A2Am，则每个数据样本也就是中的元素表示为一个m维特征向量X(x1,x2,,xm)，这里xi表示属性Ai的取值。T是训练集样本的集合。(X,cj)表示样本X属于cj类，那么分类问题就是决定p(cj/X)。若有多个类c1,c2,,cC，给定一个未知的数据样本X，若有p(cj/X)p(ci/X),i1,2,,C,ij，那

么称cj为X的最佳分类。我们称p(cj)为先验概率，p(cj/X)为后验概率，因此求X的

最佳分类即为求取最大的后验概率。根据贝叶斯定理，有

p(cj/X)p(cj)p(X/cj)p(X)，

-来源网络，仅供个人学习参考

由于p(X)对于所有的类而言是常数，因此只需要p(cj)p(X/cj)最大即可。若类的先验概率未知，则通常假定这些类是等概率的，即p(c1)p(c2)的样本数在总样本数中的比例来近似，即p(cj)CjT或者用属于cj类p(cC)，

，这种情况下只需对p(X/cj)最大

化，否则要对p(cj)p(X/cj)最大化。

当训练数据集的属性较多时，p(X/cj)的计算量可能比较大，因此朴素贝叶斯分类器基于一个简单的假设：在给定目标值时属性值之间相互条件。这样就有

p(X/cj)p(x1,x2,,xm/cj)p(xi/cj)。 i1m这样，对于给定的训练集D，决策属性包含c1,c2,,cC类，则最佳分类为：

p(cmax/X)maxp(cj/X)maxp(cj)p(x1,x2,p(X),xm/cj)(3) 或者为： p(cmax/X)maxp(cj/X)maxp(cj)p(xi/cj)i1mp(X)(4) <三>、举例说明 表1为一气候训练集。训练集大小为14个样本，共5个属性，其中4个条件属性，1个决策属性，决策属性的取值只有2种N和P，表示每个样本要么属于P类，要么

属于N类。 表错误!未指定顺序。气候训练集 决策属条件属性 性 outlook temperature humidity wind kind 1 sunny hot high weak N 2 sunny hot high strong N 3 overcast hot high weak P 4 rain mild high weak P 5 rain cool normal weak P 6 rain cool normal strong N -来源网络，仅供个人学习参考

7 overcast cool normal strong P 8 sunny mild high weak N 9 sunny cool normal weak P 10 rain mild normal weak P 11 sunny mild normal strong P 12 overcast mild high strong P 13 overcast hot normal weak P 14 rain mild high strong N 根据表1，对于测试样本：天气为sunny，气温为hot，湿度为high，风为weak

时属于哪一类呢？ 设测试样本为X={sunny，hot，high，weak}，要比较属于两类N和P的概率大小。根据公式(4)，由于p(X)对于这两类均一样，因此只要求公式(4)的分子即可。先求类别为N的概率p(N/X)： p(N/X)p(N)p(sunny/N)p(hot/N)p(high/N)p(weak/N)/p(X)

再求类别为P的概率p(P/X)： p(P/X)p(P)p(sunny/P)p(hot/P)p(high/P)p(weak/P)/p(X) 显然有p(N/X)p(P/X)。根据后验概率最大原则，X属于N类。 此外，可以用Weka软件进行朴素贝叶斯分类。步骤如下： (1)把训练集和测试样本均转换成Weka软件支持的arff格式文件； (2)在Weka程序的主界面，点击explorer进入到Wekaexplorer界面，在preprocess中点击openfile，选择训练集文件，点击classify中点击classifier选择bayes中的NaiveBayes即可； (3)在Testoptions中，选择Suppliedtestset，点击set，出现openfile按钮，

显然是选择测试集所在地文件； (4)在moreoptions下面得列表框中选择决策属性kind； (5)点击start按钮即完成了分类测试，测试结果在右边的ConfusionMatrix。 本例的测试结果ConfusionMatrix为表2。结果表明训练集为1个样本，这1个预测为N类，0个预测为P类。和我们手工计算出来的结果是一致的。

表错误!未指定顺序。表1的Weka软件分类结果 a b classfiedas 1 0 a=N 0 0 b=P 例如：见书34 其他分类算法略。

七、与分类有关的其他问题

1、分类数据预处理 （1）数据清理

-来源网络，仅供个人学习参考

（2）特征选择

（3）数据变换：平滑、聚集、数据概化、规范化、特征构造

2、分类器性能的表示与评估

分类器性能是评价分类算法的一个非常重要的因素。对于同样的数据，不同的

分类算法将产生不同的分类结果。（见书P156表格）

分类的准确率通常通过被正确分类的元组所占该类元组个数的百分比表示。加入只有两类（A类和B类），则分类器将产生四个可能的分类输出： A类数据被分入A类 A类数据被分入B类 B类数据被分入A类 B类数据被分入B类 定义：给定一个Cj和一个数据库元组ti，ti可能被分类器判定为属于Cj或不属于Cj，

其实ti本身可能属于Cj或不属于Cj，这样产生如下情况： 真正：判定ti在Cj中，实际上的确在其中。 假正：判定ti在Cj中，实际上不在其中。 真负：判定ti不在Cj中，实际上不在其中。 假负：判定ti不在Cj中，实际上的确在其中。 人们常用OC和ROC曲线表示假正和真正的关系。混淆矩阵是另外一种表示分类准确率的方法。 3、分类器的评估方法 一般情况下，先用一部分数据建立模型，然后再用剩下的数据来测试和验证这个得到的模型。如果训练集和测试集相同，那么模型的准确度难以令人信服。一般采用保持法和交叉验证方法。 （1）保持法：把给定的数据随机划分两个的集合：训练集和测试集。 （2）交叉验证：把数据随机分成不想交的n份，每份大小基本相等，训练和测试都进行n次。得到n个错误率，再把这些错误率平均。 第五章聚类方法 教学目的：掌握聚类的概念，背景，基本理论，基本应用，发展趋势

教学重点难点：聚类的概念，常见算法 教学课时：6 教学过程： 一、概述 簇（Cluster）:一个数据对象的集合。聚类分析把一个给定的数据对象集合分成不同的簇。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。聚类是一种无监督分类法:没有预先指定的类别；

“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。所谓类，通俗地说，就是指相似元素的集合。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析起源于分类学，但是聚类不等于分类。聚类与分类的不同在于，聚类所要求划分的类是未知的。在古老的分类学中，人们主要依靠经验和专业知识来实现分类，很少利用数学工具进行定量的分类。

-来源网络，仅供个人学习参考

随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学中，形成了数值分类学，之后又将多元分析的技术引入到数值分类学形成了聚类分析。聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚

类法、聚类预报法等。

聚类的典型应用是什么？在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。 1、数据挖掘中对聚类方法的要求： （1）可伸缩性 （2）具有处理不同类型属性的能力 （3）能够发现任意形状的聚类 （4）输入参数对领域知识的弱依赖性 （5）对于输入记录顺序不敏感 （6）挖掘算法应具有处理高维数据的能力 （7）处理噪声数据的能力 （8）基于约束的聚类 （9）挖掘出来的信息室可理解和可应用的 2、聚类分析在数据挖掘中的应用 （1）聚类分析可以作为其他算法的预处理步骤 （2）可以作为一个的工具来获得数据的分布情况 （3）聚类分析可以完成孤立点挖掘。 3、评价聚类方法好坏标准： 一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性；低的簇间相似性 二、基本概念和理论 1、 定义：聚类分析的输入为一组(X,s)或(X,d)表示，X表示一组样本，s和d分布式度量样本间相似度或相异度的标准。聚类系统的输出时对数据的区分结果，即

C{C1,C2,...,Ck},其中Ci是X的子集，且满足如下条件：

(1)C1C2...CkX;(2)CiCj,ij。C中的C1,C2,...,Ck称为类或簇。用类的中心

表示一个类是最常见的方式。 2、聚类分析方法的分类

常见算法有：k-均值，k-中心点，

PAM,CLARNS,BIRTH,CURE,OPTICS,DBSCAN,STING,CLIQUE,WaveCluster

（1）按照聚类的标准划分

1)统计聚类法

-来源网络，仅供个人学习参考

2）概念聚类法

（2）按照聚类算法所处理的数据类型划分

1）数值型数据聚类方法 2）离散型数据聚类方法 3）混合型数据聚类方法 （3）按照聚类尺度划分 1）基于举例的聚类算法 2）基于密度的聚类算法 3）基于互连性的聚类算法 （4）按照聚类算法的思路划分 1）划分法 2）层次法 3）基于密度的方法 4）基于网格的方法 5）基于模型的方法 3、距离和相似性的度量 这里用s(x,y)表示样本x和样本y的相似度，当x和y相似，则s(x,y)取值很大，当x和样本y的不相似时，s(x,y)取值很小。且满足s(x,y)=s(y,x)。一般把相似性度量标准化为0<=s(x,y)<=1。通常情况下，用特征空间中的距离作为度量标准来计算样本间的相异度。相异度用d(x,y)表示，通常称相异度为距离。当x和y相似时，

距离d(x,y)的取值很小，当x和y不相似时，距离就很大。 (1)距离函数 必须满足四个条件：d(x,x)=0；d(x,y)>0(xy)；d(x,y)=d(y,x)；d(x,y)<=d(x,z)+d(z,y) 1）明可夫斯基距离 设x和y是相应的特征，n是特征的维数。则定义： 当r=1时，演化为绝对值距离 当r=2时，为欧式距离 2）二次型距离 A为非负定矩阵。 当A为单位矩阵时，为欧式距离。 当A为对角阵时，为加权欧式距离 当A为协方差矩阵时，为马氏距离。

熟悉的欧氏距离虽然很有用，但也有明显的缺点。它将样品的不同属性（即各指标或各变量）之间的差别等同看待，这一点有时不能满足实际要求。例如，在教育研究中，经常遇到对人的分析和判别，个体的不同属性对于区分个体有着不同的重要

性。

马氏距离是由印度统计学家马哈拉诺比斯(P.C.Mahalanobis)提出的，表示数据的协方差距离。马氏距离有很多优点。它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据(即原始数据与均值之差）计

-来源网络，仅供个人学习参考

算出的二点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。

它的缺点是夸大了变化微小的变量的作用。

3）余弦距离

4）二元特征的样本距离

若特征为不连续的样本。假如x和y分别是n维特征，xi和yi的取值为（0，1）,

其中属性可以分几种情形：

（1） a是样本x和y中满足xi=yi=1的二元类型属性的数量 （2） b是样本x和y中满足xi=1,yi=0的二元类型属性的数量 （3） c是样本x和y中满足xi=0,yi=1的二元类型属性的数量 （4） d是样本x和y中满足xi=yi=0的二元类型属性的数量 则简单匹配系数定义为： a abcaRao系数定义为：Src(x,y) abcdJaccard定义为：Sjc(x,y)(2)类间距离 设有两类Ca和Cb，他们元素个数分别为m和h个，中心分别为ra和rb，设元素xCa，yCb，两元素间的距离记为d(x,y)，可以不同策略定义类间距离D(Ca,Cb)。

1）最短距离法：两类中最靠近的两元素距离为类间距离 2）最长距离法：两类中最远的两元素距离为类间距离 3）中心法：两类中心间的距离为类间距离 中心：假如Ci是一个聚类，使用Ci的所有数据点x，定义Ci的中心xi为：

这里ni为第i个聚类中的点数。 4）类平均法 将两个类中任意两个元素间的距离的平均值定义为类间距离 这里m和h是两个类中的元素个数 5）离差平方和 离差平方和用到了直径的概念。类的直径反映了类中各元素的差异，可定义为类中各元素至类中心的欧式距离之和。或者说，其量纲为距离的平方，即类Ca的直径表示为： 其中xa为Ca的类中心。 假设类Ca和Cb的直径分别为ra和rb，类CabCaCb直径为rab，则可定义类间距

离的平方为： 二、划分聚类方法

划分聚类方法是最基本的聚类方法，如k-平均、k-模、k-原型、k-中心点、PAM、

CLARANS等都是。

1、主要思想

给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划

-来源网络，仅供个人学习参考

分就代表一个簇(kn)。满足条件：（1）每一个簇至少包含一个对象。（2）每一个

对象属于且仅属于一个簇。

2、评价函数

聚类设计的评价函数考虑两个方面：每个簇应该是紧凑的，簇间距离应该尽量远。有一种直接方法就是观察聚类C的类内差异(C)和类间差异b(C)。简单的类内

差异就是计算类内的每一个点到它所属类中心的距离的平方和：

类间差异定义为类中心间的距离。 聚类C的总体评价可定义为b(C)/(C)

3、k-平均算法（k-means） 又称为k-均值算法。k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引

力中心）来进行计算的。 k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 k-means算法的准则函数定义为： 这里xi是簇Ci的平均值。 例见P173 4、算法性能分析 优点： （1）属经典算法，简单快速 （2）对处理大数据集，该算法是相对伸缩和高效率的。该算法以局部最优结束 （3）算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显时，效果较好 缺点：

（1）只有簇的平均值被定义的情况下才能使用。

（2）要求事先给出k可以算是一个缺点，对初值敏感，对不不同初值可能导致不同

的聚类结果。

（3）不适合于发现非凸面形状的簇或者大小差别很大的簇。对噪声和孤立点数据敏

感，少量该类数据能够对平均值产生较大影响。

改进：

-来源网络，仅供个人学习参考

提出了k-模块法，保留了k-平均值法的效率同时将k-平均的应用范围扩大到离散数据。K-原型可以对离散与数值属性两种混合的数据进行聚类，在k-原型中定义了一

个对数值与离散属性都计算的相异性度量标准。

5、PAM算法

PAM（partitioningaroundmedoid）是最早提出的k-中心点方法之一。它选用簇中位置最靠近中心的对象作为代表对象（中心点），试图对n个对象给出k个划分。

最初随机选择k个对象作为中心点，该算法反复用非代表对象（非中心点）代替中心点，试图找出更好的中心点，以改进聚类结果的质量。在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非中心点。 对所有可能的组合，估算聚类结果的质量。一个对象Oi被可以使最大平方误差减少的对象代替。在一次迭代中产生的最佳对象集合成为下次迭代的中心点。 判定一个对象Oh是否是当前一个代表对象Oi的好替代，对每一个非代表对象Oj

需要分情况考虑替换的代价。 对非代表对象Oj来说，上图给出了Oh替代Oi所化的代价。遍历所有j即得到总交换代价TCih。 该代价函数反映了替换前后平方误差值之间的差别。 若总代价为负，Oh可以替代Oi，否则说明当前的中心点是可接受的，在本次迭代中不发生变化。 算法步骤： step1.任意选择k个对象作为初始的类的中心点 step2.repeat step3.指派每个剩余对象给离它最近的中心点 step4.随机选择一个非中心点Oh step5.计算用Oh代替中心点Oi的总代价S step6.ifS<0,thenOh代替中心点Oi形成新的k个中心点集合 until不再发生变化。 算法性能： 有效消除了对孤立点数据的敏感性。比k-means方法更健壮，不易受极端数据的影响。

PAM对小数据集非常有效（如100个对象聚成5类），但对大数据集效率较低。

可扩展性差。

6、PAM算法的改进:CLARA

CLARA（ClusterLARgerApplication）:基于k-medoid类型的算法，能处理较大

的数据集合。

首先进行随机抽样，用PAM方法从样本中选择中心点。如果样本是以非常随机的

-来源网络，仅供个人学习参考

方式选取的，它应该足以代表原来的数据集合。从中选出的中心点很可能与从整体

集合中选出的非常近似。

CLARA可以抽取多个样本，对每个样本应用PAM算法，返回最好的聚类结果。

复杂度是O（ks2+k(n-k)）,其中s是样本大小。

如果样本发生倾斜，基于样本的一个好的聚类不一定代表整个数据集合的一个好的聚类。特别地，如果任何取样得到的中心点不包含最佳的中心点，CLARA算法不能

得到最佳聚类。 三、层次聚类方法

层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为凝聚的，的两种方案。 （1）凝聚的层次聚类是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足，绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上有所不同。 （2）的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。 层次凝聚的代表是AGNES算法，层次的代表是DIANA算法。

1、AGNEs算法 AGNES(AGglomerativeNESting)算法是凝聚的层次聚类方法。AGNES最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步地合并。例如，在簇A中的一个对象和簇B中的一个对象之间的距离是所有属于不同簇的对象之间最小的，AB可能被合并。这是一种单链接方法，其每一个簇都可以被簇中所有对象代表，两个簇间的相似度由这两个簇中距离最近的数据点的相似度来确定。聚类的合并过程反复进行直到所有的对象最终合并形成一个簇。在聚类中，用户能定义希望得到的簇数目作为一个结束条件。 算法描述: 输入:包含n个对象的数据库，终止条件簇的数目k 输出:k个簇，达到终止条件规定簇数目 (1)将每个对象当成一个初始簇；

(2)Repeat

(3)根据两个簇中最近的数据点找到最近的两个簇；

(4)合并两个簇，生成新的簇的集合；

(5)Until达到定义的簇的数目

AGNES算法比较简单，但经常会遇到合并点选择的苦难。如果在某一步没有很好

-来源网络，仅供个人学习参考

地选择出合并点，很可能导致低质量的聚类结果。而且此算法没有良好的可伸缩性，

算法复杂度较高。

算法性能：

（1）简单，但遇到合并点选择困难的情况。

（2）一旦一组对象被合并，不能撤销

（3）算法的复杂度为O(n2)，不适合大数据集计算

例：P181 2、DIANA算法

DIANA（DivisiveAnalysis）算法属于的层次聚类，首先将所有的对象初始化到一个簇中，然后根据一些原则（比如最邻近的最大欧式距离），将该簇分类。直到到达用户指定的簇数目或者两个簇之间的距离超过了某个阈值。

DIANA用到如下两个定义： （1）簇的直径：在一个簇中的任意两个数据点都有一个欧氏距离，这些距离中的最大值是簇的直径 （2）平均相异度（平均距离）： 算法描述： 输入：包含n个对象的数据库，终止条件簇的数目k 输出：k个簇，达到终止条件规定簇数目 （1）将所有对象整个当成一个初始簇 （2）For(i=1;i!=k;i++)DoBegin （3）在所有簇中挑选出具有最大直径的簇； （4）找出所挑出簇里与其他点平均相异度最大的一个点放入splintergroup，剩余

的放入oldparty中。 （5）Repeat （6）在oldparty里找出到splintergroup中点的最近距离不大于oldparty中点的

最近距离的点，并将该点加入splintergroup （7）Until没有新的oldparty的点被分配给splintergroup； （8）Splintergroup和oldparty为被选中的簇成的两个簇，与其他簇一起组成新的簇集合 （9）END

算法性能：缺点是已做的操作不能撤销，类之间不能交换对象。如果在某步没

有选择好点，可能会导致低质量的聚类结果。大数据集不太适用。

例P182

3、其他聚类算法

(1)BIRCH

-来源网络，仅供个人学习参考

BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)是一个综合的层次聚类算法。它用到了聚类特征(ClusteringFeature,CF)和聚类特征树(CFTree)两个概念，用于概括聚类描述。聚类特征树概括了聚类的有用信息，并且占用空间较元数据集合小得多，可以存放在内存中，从而可以提高算法在大型数据

集合上的聚类速度及可伸缩性。 BIRCH算法包括以下两个阶段：

（1）扫描数据库，建立动态的一棵存放在内存的CFTree。如果内存不够，则增

大阈值，在原树基础上构造一棵较小的树。

（2）对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。 由于CFTree的叶节点代表的聚类可能不是自然的聚类结果，原因是给定的阈值了簇的大小，并且数据的输入顺序也会影响到聚类结果。因此需要对叶节点进一步利用一个全局性的聚类算法，改进聚类质量。 (2)CURE CURE（ClusteringUsingRepresentatives）是一种针对大型数据库的高效的聚类算法。基于划分的传统的聚类算法得到的是球状的，相等大小的聚类，对异常数据比较脆弱。CURE采用了用多个点代表一个簇的方法，可以较好的处理以上问题。并且在处理大数据量的时候采用了随机取样，分区的方法，来提高其效率，使得其可以高效的处理大量数据。 算法流程:CURE的算法在开始时，每个点都是一个簇，然后将距离最近的簇结合，一直到簇的个数为要求的K。它是一种的层次聚类。算法分为以下6步：

1）从源数据对象中抽取一个随机样本S。 2）将样本S分割为一组划分。 3）对划分局部的聚类。 4）通过随机取样提出孤立点。如果一个簇增长得太慢，就去掉它。

5）对局部的簇进行聚类。 6）用相应的簇标签标记数据。 (3)DBSCAN DBSCAN(Density-BasedSpatialClusteringofApplacationswithNoise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的

空间数据库中发现任意形状的聚类。

DBSCAN算法描述:

输入:包含n个对象的数据库，半径e，最少数目MinPts;

输出:所有生成的簇，达到密度要求。

(1)Repeat

-来源网络，仅供个人学习参考

(2)从数据库中抽出一个未处理的点；

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

(5)UNTIL所有的点都被处理。

DBSCAN对用户定义的参数很敏感，细微的不同都可能导致差别很大的结果，而

参数的选择无规律可循，只能靠经验确定。

3、其他聚类略

-来源网络，仅供个人学习参考