数据挖掘原理与实践蒋盛益版期末复习

第一章

数据挖掘定义

技术层面：数据挖掘就是从大量数据中，提取潜在有用的信息和知识的过程。

商业层面：数据挖掘就是一种商业信息处理技术，其主要特点是对大审业务数据进行抽取、转换、分析

和建模处理，从中提取辅助商业决策的关键性数据。

数据挖掘任务

预测任务

根据其它属性的值预测特定属性的值，如分类、回归、离群点检测。

描述任务

寻找概括数据中潜在联系的模式，如聚类分析、关联分析、演化分析、序列模式挖掘。

⑴分类(Classification)分析

分类分析，通过分析例如数据库中的数据为每个类别做出准确的描述或建立分析模型或挖掘出分

类规则，然后用此分类规则对其它数据库中的记录进行分类。

分类分析广泛应用于用户行为分析(受众分析)、风险分析、生物科学等。

(2)聚类(Clustering)分析

“物以类聚，人以群分“。聚类分析技术成图找出数据集中的共性和差异，并将具有共性的对象聚合

在相应的类中。聚类可以帮助决定哪些组合更有意义，广泛应用于客户细分、定向营销、信息检索等等。

(3)回归(Regression)分析

回归分析是确定两种或两种以上变数间相互依赖的定量关系的一种分析方法。其可应用于风险分析、

作文自动评分等领域。

(4)关联(Association)分析

关联分析，发现特征之间的相互依赖关系，通常是从给定的数据集中发现频繁出现的模式知识(又

称为关联规则)。关联分析广泛用于市场营销、事务分析等领域。

聚类与分类的主要区别

聚类与分类是容易混淆的两个概念，聚类是一种无指导的观察式学习，没有预先定义的类。而分类

问题是有指导的例如式学习，预先定义的类。

数据挖掘过程

数据挖掘和知识发现紧密相连。知识发现是从数据中发现有用知识的整个过程

■知识发现的主要步骤：

■数据清洗。其作用是去除数据噪声和与挖掘主题明显无关的数据。

■数据集成。其作用是将来自多数据源中的相关数据组合到一起。

■数据转换。其作用是将数据转换为易于进行数据挖掘的数据存储形式。

■数据挖掘。其作用是利用智能方法挖掘数据模式或规律知识。

■模式评估。其作用是根据一定评估标准从挖掘结果筛选出有意义的相关知识。

■知识表示.其作用是利用可视化和知识表达技术，向用户展示所挖掘的相关知识

从商业的角度看，数据挖掘过程可分为三个阶段

数据收集：数据收集容易且不引人注意，但却是数据挖掘的根底。知识是从海量数据里提取出来

的，因此要挖掘知识必须得收集一定量的数据。收集到的原始数据--般存在缺失值、错误值等问题，不

能直接用作知识提取的数据源,需要进行数据预处理。

知识提取：基于经过预处理的数据，使用各种数据挖掘方法（如分类、聚类、关联分析等）进行知识

提取，这是数据挖掘的核心局部。

知识辅助决策：数据挖掘技术已被广泛地应用于各领域，其提取出来的知识可以很好地辅助决策者

做出良好的决策

第二章

数据统计特征

数据的中心度量

1数据集"中心〃的最常用、最有效的数值度量是（算术）均值（mean）。

2设XLX2，…,XN是N个值的集合，那么该值集的均值定义为：

Z

X1+X]------Xz

3c=——

ZZ

截断均值：指定0和100间的百分位数p，丢弃高端和低端（p/2）%的数据•，然后用常规方法计算均值,

所得的结果即是截断均值。

中位数是p=100%时的截断均值，而标准均值是对应于p=0%的截断均值。

例：计算｛1,2,3,4,5,90｝值集的均值，中位数和p=40%的截断均值.

解：均值是17.5,中位数是35P=40%时的截断均值也是3.5

数据预处理

■数据清理

■数据集成

■数据变换

■数据归约

■数据离散化

数据清理一一噪声数据的平滑方法

■目前噪声数据的平滑方法包括：

■分箱：分箱方法通过考察“邻居〃（即周围的值）来平滑有序数据的值。

■聚类：聚类将类似的值组织成群或“簇”。

■回归：让数据适合一个函数来平滑数据。

数据平滑实例

■一组排序后的数据（单位：元）：4,8,15,21,21,24,25,28,34

■划分为等深的箱

□箱1:4,8,15

口箱2：21,21,24

口箱3：25,28,34

■用箱平均值进行平滑

□箱1:9,9,9（下同）

■用箱的边界进行平滑

□箱1：4.4.15

口箱2：21,21,24

口箱3:25,25,34

数据变换一一标准化

，K—niin

■最小-最大标准化：r=----------,优点：计算简单

max「Umian力

---------竺”----，mean是均值，stand_dev为标注差

■Z-score标准化：vaa

5tand-dev(),cl

■小数定标标准化：V=」一，其中，j是使max(|VI)<1的最小整数

10J

离散属性间的相关性计算

□离散型数据间相关性计算(互信息)

■特征x的信息燃

H(X)=_£P(g)log2(P(g))

■变量y后X的条件信息燧

H(X|y)=—£P®)£P(gg)log2(P(RM))

3£

■信息增益

IG(X\Y)=H(X)^H(X\Y)

数据对象之间的相异度

■距离：

□欧几里得距离

d(x,y)=-ykY

其中，n的维数(总特征数)，X〈和Yk分别表示X和Y的第k个分量

□闵可夫斯基(Minkowski)距高

“1

rv

dist=(£|pk-qk|)

*=i

□x=l,城市块(曼哈顿)距离

□x=2,欧几里得距离

□x=g,切比雪夫(Chebyshev)距离

二值属性

■二元数据相似性度量

Moi=xa0并且y取1的属性的个数

x取1并且y取0的属性的个数

Moo=xMX0并且y取0的属性的个数

Mu=x取1并且y取1的属性的个数

■简单匹配系数(SimpleMatchingCoefficient,SMC)：

SMC=值匹配的属性个数/属性个数

=(Mu+Moo)/(Moi4Mio+Mu+M(x))

■Jaccard系数

J=匹配的个数/不涉及0-0匹配的属性个数

=(Mu)/(Moi+Mio+Mu)

例子

X=(1000000000)

y=(0000001001)

Moi=2(x取0并且y取1的属性的个数)

Mio=1(x取1并且y取0的属性的个数)

Moo=7(x取0并且y取0的属性的个数)

Mn=0(x取1并且y取1的属性的个数)

SMC=(Mu+Moo)/(Moi+Mio+Mu+Moo)=(0+7)/(2+1+0+7)=0.7

J=Mn/(Moi+Mio+Mn)=O/(2+l+O)=O

2.18以下表格包含了属性name,gender,trait-1,trait-2,trait-3,及trait-4,这里的name是

对象的id,gender是一个对称的属性,剩余的trait属性是不对称的，描述了希望找到的笔友的个人特点。

假设有一个效劳是试图发现适宜的笔友。

nameJseneertrait-1trait-2trait-3trait-4

KeavnMNPPN

CarolineFNPPN

EnkMPNNP

对不对称的属性的值，值P被设为1,值N被设为0。

假设对■象(潜在的笔友)间的距离是基于不对称变量来计算的。

乞)计算对象间的简单匹配系数；

SMC(Keavn,Caroline)=(2+2i/(0+0+2+2)=1

SMC(Keavn,Erik)=(0+0)/(2+2+0+0)=0

SMC(Caroline,Erik):(0+0)/(2+2+0+0)=0

；b)计算对象间的Jaccard系数；

Jaccard(Keavn,Caroline)=2/(2+0+0)=1

Jaccard(Keavn,Erik)=0/(0+2+2)=0

Jaccard(Caroline,Erik)=0/(0+2+2)=0

⑹你认为哪两个人将成为最正确笔友？哪两个会是最不能相容的？

根据属性的匹配程度，Keavn和Caroline将成为最正确笔友，Caroline和Erik会

是最不能相容的

(d)假设我们将对称变量gender包含在我们的分析中。基于Jaccard系数，谁将是最和

谐的一对？为什么？

假设将对称变量gende「包含在分析中，设值M被设为1,值F被设为0,

Jaccard(Keavn,Caroline)=2/(2+1+0)=2/3

Jaccard(Keavn,Erik)=l/(l+2+2)=1/5

Jaccard(Caroline,Erik)=0/(0+2+3)=0

因为Jaccard(Keavn,Caroline)最大，因此，Keavn和Caroline是最和谐的一对。

第三章

分类的定义

□分类是数据挖掘中的一种主要分析手段

□分类的任务是对数据集进行学习并构造•个拥有预测功能的分类模型，用于预测未知样

本的类标号，如：

分类与回归的区别

□分类和回归都有预测的功能，但是：

■分类预测的输出为离散或标称的属性；

■回归预测的输出为连续属性值；

□分类与回归的例子：

■预测未来某银行客户会流失或不流失，这是分类任务；

■预测某商场未来一年的总营业额，这是回归任务。

分类与聚类的区别

□分类因为使用了类标号属性，属于有监督的学习方法

□聚类，事先没有使用任何类标号信息，属于尢监督的学习方法

决策树的根本概念

■决策树(DecisionTree)是一种树型结构，包括：决策节点(内部节点)、分支和叶节点三个局部。

■其中：

□决策节点代表某个测试，通常对应于待分类对象的某个属性，在该属性上的不同测试结

果对应一个分支。

□叶节点存放某个类标号值，表示一种可能的分类结果。

□分支表示某个决策节点的不同取值。

□决策树可以用来对未知样本进行分类，分类过程如下：从决策树的根节点开始，从上往

下沿着某个分支往下搜索，直到叶结点，以叶结点的类标号值作为该未知样本所属类标

号。

决策树的属性选择

■虽然可以采用任何一个属性对数据集进行划分，但最后形成的决策树会差异很大。需要寻找适

宜的属性选择方法。

■属性选择是决策树算法中重要的步骤，常见的属性选择标准包括信息增益和Gini系数。

□信息增益是决策树常用的分枝准则,在树的每个结点上选择具有最高信息增益的属性

作为当前结点的划分属性。

□Gini系数是一种不纯度函数.用来度量数据集(I勺数据关于类的纯度。

获得大小适宜的树

■决策树学习的目的是希望生成能够揭示数据集结构并且预测能力强的一棵树，在树完全生长的

时候有可能预测能力反而降低，为此通常需要获得大小适宜的树。

■一般来说有两种获取方法：

□一种为定义树的停止生长条件，常见条件包括最小划分实例数、划分阈值和最大树深度等。

□另一种方法是对完全生长决策树进行剪枝，方法是对决策树的子树进行评估，假设去掉

该子树后整个决策树表现更好，那么该子树将被剪枝。

ID3分类算法

■它使用信息增益(informationgain)作为属性的选择标准。

□首先检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值

建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅

包含同一个类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

■与ID3分类算法相关的根本概念包括：

□信息崎：用来度量一个属性的信息量。

假定S为训练集，S的目标属性C具有m个可能的类标号值，C={C1,C2,…,Cm},假

定训练集S中，Ci在所有样本中出现的频率为(i=l,2,3,…,m),那么该训练集S所包含

的信息嫡定义为：

EntropyiS)=Entropy{p},p2,...,p)=-glog2pi

/=1

爆越小表示样本对目标属性的分布越纯，反之牖越大表示样本对目标属性分布越混

乱。

信息燧例题

■考虑数据集weather如下，求weather数据集关「目标属性playball的麻

outlooktemperaturehumiditywindplayball

sunnyhothighweakno

sunnyhothighstrongno

overcasthothighweakyes

rainmildhighweakyes

raincoolnormalweakyes

raincoolnormalstrongno

overcastcoolnormalstrongyes

sunnymildhighweakno

sunnycoolnormalweakyes

rainmildnormalweakyes

sunnymildnormalstrongyes

overcastmildhighstrongyes

overcasthotnormalweakves

rainmildhighstrongno

■解答：令weather数据集为S,其中有14个样本,目标属性playball有2个值｛Cl=ye$,C2=no｝。14

个样本的分布为：

□9个样本的类标号取值为yes,5个样本的类标号取值为No。Cl=yes在所有样本S中出

现的概率为9/1乙，C2=no在所有样本S中出现的概率为5/14o

□因此数据集S的墙为：

959955

Entropy{S)=Entropy{——.——)=-----log--------------log,,——=0.94

141414921414214

□

信息增益

信息增益是划分前样本数据集的不纯程度(牖)和划分后样本数据集的不纯程度(端)的差值

□假设划分前样本数据集为S,并用属性A来划分样本集S,那么按属性A划分S的信息增

益Gain(S,A)为样本集S的燃减去按属性A划分S后的样本子集的燃：

GaiiXS,A)=Entropy[S)-Entropy

按属性A划分S后的样本子集的牖定义如下：假定属性A有k个不同的取值，从而

将S划分为k个样本子集｛S1,S2,…,Sk｝,那么按属性A划分S后的样本子集的信息增为：

Entropy^=-EntropyiS}

/-II3

其中|Si|(i,=l,2,…k)为样本子集Si中包含的样本数，|S|为样本集S中包含的样本数。

信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。

信息增益例题

■以数据集weather为例，设该数据集为S,假定用属性wind来划分S,求S对属性wind的信息

增益。

outlooktemperaturehumiditywindplayball

sunnyhothighweakno

sunnyhothighstrongno

overcasthothighweakyes

rainmildhighweakyes

raincoolnormalweakyes

raincoolnonnalstrongno

overcastcoolnormalstrongyes

sunnymildhighweakno

sunnycoolnormalweakyes

rainmildnonnalweakyes

sunnymildnormalstrongyes

overcastmildhighstrongyes

overcasthotnormalweakves

rainmildhighstrongno

■解答:

□(1)首先由前例il算得到数据集S的燧值为0.94：

□⑵属性wind有2个可,能的取值{weak,strong},它将S划分为2个子集：{S1,S2},S1为wind

属性取值为wea＜的样本子集，共有8个样本;S2为wind属性取值为strong的样本子集，

共有6个样本：下面分别计算样本子集S1和S2的燧。

对样本子集SI,playball=yes的有6个样本,playball=no的有2个样本,那么：

一—6]62]2

Entropy{Sx)=--log2---log2-=0.811

oooo

对样本子集S2,playball=yes的有3个样本,playball=no的有3个样本,那么:

Entropy[S^=-|log11log1

22=1

oo66

■利用属性wind划分S后的烯为:

S.I

1i

Entropy^S)=g~—Entropy(S)=-2-J—Entropy^S^4-Entropy{S2)

SI3S

o6

=—Entropy^Sx)+—Entropy\S^=0.571*0.811+0.428*1=0.891

■按属性wind划分数据集S所得的信息增益值为:

Gair^S,wind)=EntropyiS)-Entropywind{S}=0.94-0.891=0.049

ID3建树算法

■以weather数据集为例，讲解ID3的建立过程。

outlooktemperaturehumiditywindplayball

sunnyhothighweakno

sunnyhothighstrongno

overcasthothighweakyes

rainmildhighweakyes

raincoolnormalweakyes

raincoolnormalstrongno

overcastcoolnormalstrongyes

sunnymildhighweakno

sunnycoolnormalweakyes

rainmildnormalweakyes

sunnymildnormalstrongyes

overcastmildhighstrongyes

overcasthotnormalweakyes

rainmildhighstrongno

数据集的构成

■数据集具有属性：outlook,temperature,humidity,wind.

■outlook={sunny,overcast,rain}

■temperature={hot,mild,cool}

■humidity={high,normal}

■wind={weak,strong}

ID3建立决策树

■首先计算总数据集S对所有属性的信息增益，寻找根节点的最正确分裂属性:

■Gain(S,outlook)=0.246

■Gain(S,temperatjre)=0.029

■Gain(S,humidity)=0.152

■Gain(S,wind)=0049

■显然，这里。utlook属性具有最高信息增益值，因此将它选为根结点.

■以outlook做为根结点，继续往下：

■思想是，以。utlook的可能取值建立分支，对每个分支递归建立子树。

■因为outlook有3个可能值，因此对根结点建立3个分支{sunny,overcast,rain).

■首先对outlook的sunny分支建立子树。

□找出数据集中outlook：sunny的样本子集SMlookxunny，然后依次计算剩下三个属性对该

样本子集Swnny划分后的信息增益：

■Gain(S$umy/humidity)=0.971

■Gain(Ssureiy/temperature)=0.571

■Gain(SSUmy,wind)=0.371

显然humidity具有最高信息增益值，因此它被选为outlook结点下sunny分支下的决策结点

■采用同样的方法，依次对outlook的overcast分支、rain分支建立了•树，最后得到，果可以预测

类标号未知的样本的决策树。

ID3算法总结

■ID3算法是所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。

■ID3搜索的假设空间是可能的决策树的集合，搜索目的是构造与训练数据一致的一棵;夬策树，搜

索策略是爬山法，在构造决策树时从简单到豆杂，用信息烯作为爬山法的评价函数，

■ID3算法的核心是在决策树各级结点上选择属性，用信息增益作为属性选择的标准，使得在每个

非叶节点进行测试时能获得关于被测数据最大的类别信息，使得该属性将数据集分成子集后，

系统的燃值最小。

C4.5分类算法

■基于ID3算法中存在的缺乏，Quinlan于1993年对其做出改良，提出了改良的决策树分类算法

C4.5,该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改良：

□(1)能够处理连续型属性数据和离散型属性数据；

□(2)能够处理具有缺失值的数据；

□(3)使用信息增益率作为决策树的属性选择标准；

□(4)对生成的树进行剪枝处理，以获取简略的决策树；

□(5)从决策树到规则的自动产生。

C4.5算法的概念描述

假定5为训练集，目标属性C具有m个可能的取值，C={C1,C2,…,Cm},即训练集5的目标

属性具有m个类标号值C1,C2,…,Cm,C4.5算法所涉及的概念描述如下：

■(1)假定训练集5中，。在所有样本中出现的频率为pi(i=l,2,3,…,m),那么该集合5所包含

阳

的信息燧为：EntropyiS)=pilog2p1.

/-I

■(2)设用属性A来划分S中的样本，计算属性A对集合S的划分燧值EntropyMS)定义如下：

假设属性A为离散型数据，并具有k个不同的取值，那么属性A依据这k个不同取值

将S划分为k个子集{S1,S2,…,Sk},属性A划分S的信息燃为

IS/|

EntropyMS)=ZEntropyiS

/=1IS|

其中|Si|和⑸分别是Si和S中包含的样本个数。

如果属性A为连续型数据，那么按属性A的取值递增排序，洛每对相邻值的中点看作可能的分裂点，

对每个可能的分裂点，计算：

kI\sI

Entropy,{S}=L忖-yEntrapAS,)+忖L-y-Entropy^S

其中呈和SR分别对应于该分裂点划分的左右两局部子集，选择EntropyA(S)值最小的分裂点作为属性A

的最正确分裂点，并以该最正确分裂点按属性A对集合S的划分烟值作为属性A划分S的烯值。

■⑶C4.5以信息增益率作为选择标准，不仅考虑信息增益的大小程度，还兼顾为获得信息增益所

付出的“代价”：

■C4.5通过引入属性的分裂信息来调节信息增益，分裂信息定义为

初的)=母黑］。&等

□信息增益率定义为

GairkA)

GainRati&A)=

SplitE^A)

□这样如果某个属性有较多的分类取值，那么它的信息腐会偏大，但信息增益率由

于考虑了分裂信息而降低，进而消除了属性取值数目所带来的影响。

C4.5算法演示

■以weather数据集为例，演示C4.5算法对该数据集进行训练，建立一棵决策树的过程，对未知

样本进行预测。

Stepl:计算所有属性划分数据集S所得的信息增益分别为(参考ID3例题演示)：

Gain{S.outlook)—0.246

Gain{SJempei^ature)-0.029

Gain{Syhumidity)—0.152

Gain^S9wind)-0.049

Step2:计算各个属性的分裂信息和信息增益率

□以outlook属性为例，取值为overcast的样本有4条，取值为rain的样本有5条，取值

为sunny的样本有5条：

5R4456

SplitE…■M1Og2M-M1Og2M-M1Og2M=1-576

Gs%utlook

GainRatio^^=0.44

SPlitEoutlook

□同理依次计算其它属性的信息增益率分别如下:

0.029

GainRatio^^=0.019

尔呜351.556

Gain%飒0.152

GainRatio^^11m=0.152

SpEE行的丁

Gainwind_0.049

GainRatio^md==0.0497

SplitEwM"0^85

Step3:取值信息增益率最大的那个属性作为分裂结点，因此最初选择outlook属性作为决策树的

根结点，产生3个分支，如下：

Step4:对根结点的不同取值的分支，递归调用以上方法，求子树，最后通过C4.5获得的决策树

为

outlooks

贝叶斯分类方法

□贝叶斯分类方法是一种基于统计的学习方法。

□是一种利用概率统计知识进行学习分类的方法。

■如：预测一个数据对象属于某个类别的概率。

■如：计算邮件是垃圾邮件或合法邮件的概率，取概率大的为预测结果

□主要算法有：

■朴素贝叶斯分类算法

■贝叶斯信念网络分类算法等。

贝叶斯定理

■假定X为类标号未知的一个数据样本，H为样本X属于类别C的一个假设

□分类问题就是计算概率P(H|X)的问题，即给定观察样本X下假设H成立的

概率有多大。

□这里：

■P(H)表示假设H的先验概率(priorprobability)o

■P(X)表示慢本数据X的先验概率。

■P(H|X)表示在条件X下，假设H的后验概率(posteriorprobability)o

■P(X|H)表示在给定假设H的前提条件下，样本X的后验概率

例：

■假设数据集由三个属性构成：

□｛年龄、收入、是否购置计算机｝

□库本X为：｛35,4000,?｝

□假设H为：顾客将购置计算机。

□那么：

■P(H)表示任意给定的顾客将购置计算机的概率，而不考虑年龄、收入

其它信息。

■P(X)表示数据集中，样本年龄为35,工资为4000的概率。

■P(H|X)表示顾客的年龄和收入分别为35和4000,顾客购置计算机的概

率。

■P(X|H)表示顾客购置计算机，顾客年龄和收入属性值为35和4000的

概率。

■假设X,Y是一对随机变量，它们的：

□联合概率P(X=x,Y=y)是指X取值x且Y取值y的概率

□条件概率是指一随机变量在另一随机变量取值的情况下取某一个特定值的概

率。

■例如P(Y=y|X=x)是指在变量X取值x的情况卜，变量Y取值y的概率)。

■贝叶斯定理是指X和Y的联合概率和条件概率满足如下关系：

P(X,Y)=P(Y|X)P(X)=P｛X|K)P(K)

=>P｛Y|才)=MX丫)PyY｝

■例：考虑A和B两队之间的足球比赛：假设过去的比赛中，65%的比赛A对取胜，

35%的比赛B对取胜。A对胜的比赛中只有30%是在B对的主场，B对取胜的比赛中

75%是在主场。

■如果下一场比赛在B对的主场进行，请预测哪支球队最有可能胜出？

解答：根据贝叶斯定理，假定

■随机变量X代表东道主，X取值范围为｛A,B｝

■随机变量Y代表比赛的胜利者，取值范围为｛A,B｝。

■A对取胜的概率为0.65,表示为：P(Y=A)=0.65,

■B对取胜的概率为0.35,表示为：P(Y=B)=0.35,

■B对取胜时作为东道主的概率是0.75,表示为：

P(X=B|Y=B)=0.75z

■A对取胜时B对作为东道主的概率是0.3,表示为：

p(X=B|Y=A)=0.3,

■计算：

■下一场比赛在B对主场，同时A对胜出的概率表示为：P(Y=A|X=B)

□P(Y=A|X=B)=P(X=B|Y=A)*P(Y=A)/P(X=B)

=(0.3*0.65)/0.4575=0.4262

■下一场比赛在B对主场，同时B对胜出的概率表示为：P(Y=B|X=B)

□P(Y=B|X=B)=P(X=B|Y=B)*P(Y=B)/P(X=B)

=(0.75*0.35)/0.4575=0.5737

根据计算结果，可以推断出，下一场最有可能是B对胜出

P(X=B)的计算：

□P(X=B)=P(X=B/Y=A)+P(X=B,Y=B)

=P(Y=A|X=B)*P(X=B)+P(Y=B|X=B)*P(X=B)

=P(X=B|Y=A)*P(Y=A)+P(X=B|Y=B)*P(Y=B)

=0.3*0.65+0.75*0.35=0.195+0.2625=0.4575

朴素贝叶斯分类算法

■、朴素贝叶斯分类算法利用贝叶斯定理来预测一个未知类别的样本属于各个类别的可

能性，选择其中可能性最大的一个类别作为该样本的最终类别。

朴素贝叶斯分类算法演示

例子:对weather数据集使用朴素贝叶斯算法预测未知样本X={rainy,hot,normal,false,?}

的playball类标号属性的值。

■该问题描述如下：

■样本X={rainy,hot,normal,false,?}

■类标号playball有2个取值{yes,no)

■题目即求：

■样本X在play为yes的概率P(play=yes|X)

■和样本在play为no的概率P(play=no|X)

■样本X将被预测为概率值大的那个类。

解：

根据朴素贝叶斯定理：

P(play=yes|X)=P(X|play=yes)*P(play=yes)

=P(xl|play=yes)*P(x2|play=yes)*P(x31play=yes)*P(x4|play=yes)*P(play=yes)

其中：

P(xl|play=yes)=P(outlook=rainy|play=yes)=3/9

P(x21play=yes)=P(temperature=hot|play=yes)=2/9

P(x31play=yes)=P(humidity=normal|play=yes)=6/9

P(x41play=yes)=P(windy=false|play=yes)=6/9

P(play=yes)=9/14

因此：

P(play=yes|X)=l/3x2/9x2/3x2/3x9/14=0.0211

同样方法计算：

P(play=no|X)=P(X|play=no)*P(play=no)

=P(xl|play=no)*P(x21play=no)*P(x31play=no)*P(x41play=no)*P(play=no)

其中：

P(xl|play=no)=P(outlook=rainy|play=no)=2/5

P(x21play=no)=P(temperature=hot|play=no)=2/5

P(x31play=no)=P(humidity=normal|play=no)=l/5

P(x41play=no)=P(windy=false|play=no)=2/5

P(play=no)=9/14

因此：

P(play=no|X)=2/5x2/5xl/5x2/5x9/14=0.0082

■根据计算结果；

□P(play=yes|X)>P(play=no|X)

■所以：

□样本X={rainy,hot,normal,false,?}的play类标号值应为yes.

第四章

基于划分的聚类算法

给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一

个聚类，并且k<=n。也就是说，它将数据划分为k个组，同时满足如下的要求：

(1)每个组至少包含一个对象；

(2)每个对象必须属于且只属于一个组。

划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的

误差值，当目标函数值收敛时，得到最终聚类结果。这类方法分为基于质心的(Centroid-based)

划分方法和基于中心的(Medoid・based)划分方法

根本k-means聚类算法

k-means聚类算法：

⑴从数据集D中任意选择k个对象作为初始簇中心；

(2)repeat

(3)for数据集。中每个对象Pdo

(4)计算对象P到k个簇中心的距离

⑸将对象P指派到与其最近(距离最短)的簇；

(6)endfor

⑺计算每个簇中对象的均值，做为新的簇的中心；

(8)untilk个簇的簇中心不再发生变化

K-means算法采用<k,mean)来表示一个簇

k-means聚类算法例如

■例4.1对表4-1中二维数据，使用算法将其划分为2个簇，假设初始簇中

心选为P7(4,5),P10(5,5)o

表4-1k-means聚类过程例如数据集1

PIP2P3P4P5P6P7P8P9PIO

X3374384475

y4637855145

■解：图4・2显示了对于给定的数据集k-mea心聚类算法的执行过程。

⑴根据题目，假设划分的两个簇分别为C1和C2,中心分别为(4,5)和(5,5),下面计算10

个样本到这2个簇中心的距离，并将10个样本指派到与其最近的簇：

⑵第一轮迭代结果如下：

属于簇C1的样本有：｛P7,Pl,P2,P4,P5,P8｝

属于簇C2的样本有：｛PIO,P3,P6,P9｝

重新计算新的簇的中心，有：C1的中心为(3.5,5.167),C2的中心为(6.75,4.25)(簇

中心的计算方式是平均类中所有点)

⑶继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，第二轮迭代结果如

下：

属于簇C1的样本有:｛Pl,P2,P4,P5,P7,P10｝

属于簇C2的样本有：｛P3,P6,P8,P9｝

重新计算新的簇的中心，有：C1的中心为(3.67,5.83),C2的中心为(6.5,3.25)

⑷继续计算10个样本到新的簇的中心的距离，重新分配到新的簇中，发现簇中心不再发

生变化，算法终止。

K.均值算法练习

■设n=8,k=2

■第一次迭代：假定随机选择两个对象，如序号1和序号3当作初始点，分别找到离

两点最近的对象，并产生两个簇｛1,2｝和｛3,4,5,6,7,8｝

■对于产生的簇计算平均值(1.5,1)(3.5,3)

■第二次迭代:根据平均值调整对象所在的簇，重新聚类，得到新的簇｛1,2,3,4｝和

{5,6,7,8}。重新计算平均值(1.5,1.5)(4.5,33)

第三次迭代：按平均值重新聚类，簇保持不变，程序结束

平睡平睡新平端

船)船)修1)配)

1(L1)(L2)阳5M8}(1.5,1)(3.5,3)

2(3.5,3){12堀{闻8}(1.5,1.5)(4.5,35)

3(L5J5)R5,3.5){12”},{5,618}(1.5,1.5)(4.5,3.5)

K•均值算法应用实例

■根据2005・2010年的战绩，分析中国男足的地位

AIBIC

2006年世界杯2010年世界杯2007年亚洲杯

2

50509

3

42894

17153

5

25405

6

28402

7

50501

9

50409

克斯

坦

40405

50509

50505

50509

40409

403217

印尼EricZhgn^%TechBlog(http施oo2业cnbl呼com?

■其中包括两次世界杯和一次亚洲杯，提前对数据做如下预处理：对于世界杯，进入

决赛圈那么取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40,预选赛

小组未出现的赋予50。对于亚洲杯，前四名取其排名，八强赋予5,十六强赋予9,

预选赛没出现的赋予17。这样做是为了使得所有数据变为标量，便于后续聚类。

■对数据进行归一化：

AE1cID

12006年世界杯2010年世界杯2007年亚洲杯

2110.5

30.300.19

400.150.13

50.240.760.25

6沙特0.30.760.06

7110

810.760.5

910.760.5

10乌兹别克斯坦0.7