第五章其他常用机器学习算法12学时

第五章其他常用机器学习算法（12学时K最近邻(k-NearestNeighbor，KNN)分类算法：基本介绍、算法述K-means聚类算法：算法简介、算法优点、算法缺点贝叶斯学习算法：贝叶斯网络、先验概率、后验概率、MA假设和一致学习器、贝叶斯最优分类器、朴素贝叶斯分类器；最大期望(EM)聚类算法：最大似然估计、Jensen型的1K邻分类方简单概K-近邻基本思K-最近邻算K-2简单概K不是事先通过数据来学好分类模型,再对未知样本分类，而带有标记的样本集，给一个3简单概目标函数近。这种方法为局部近。4简单概念--相样本为X=(x1,x2,…xn)

d(i,j)|xi1xj1||xi2xj2|...|xipxjp|jx2jx2jj距离近就相5K-近邻基本思 一个未知类的样本（要对其分类6d(d(X,Y)(xii1nK-最近邻样本：用n维数值属性表示 度量：点之间的距离（关系）7K-近邻算 8从数据集T中不断取从数据集T中不断取一直取出Kif|N|≤K,ifu∈Nsuchthatsim(t,u)≤sim(t,d),N=N-{u};//去t距离大的N=N∪{d};//加进t小的 classified;//N中的最多的类c赋给t9K-近邻分类方法也可作为预测方K-近邻方法的优基于距离的分类近邻的含义距离的计算基于距离的分类 的一个点。这样所有的Cj=(cj1,cj2,……Y=(y1,y2,……基于距离的分类CBACBA训练集（分3类 9个未分类数 将9个数据分基于距离的分类方C1,C2,…Cm//样本有m个类 //t属于的类 i：=1tomifdis（Ci，t）＜dist,C=K-NN算法例较 基于距离的K-NN分类方法例给样本数据集T={3,11,22}/1.K-NN算法例子T={(1,0),(1,2),(1,4),(2,1),(2,3),(3,1),(3,-3),(5,0), d={(3,1)},d={(3,-3)}, K-NN算法例子d={(5,0)},dt=sqr(5),N={(2,1),(2,3),(3,1),d={(5,-1)},dt=sqr(10),N={(2,1),(2,3),(3,1),d={(6,1)},dt=sqr(5),N={(2,3),(3,1),(5,0),决策树算决策树算法原属性→决策树算法原的函数H:→C的表示模型。决策树算法原1、创建决策树过预测果预测试22、使用决策树模型预测过决策树算法原定义给定一个训练数据集D＝，每 。决策树算法原 准则定义为在决策树算法中将训练数据集D 定义 属性Xi定义为决策树中每 的一个用 数据集的属性。Xi

{A1,A2,,Ah决策树算法原定义如果Xi是连续属性，那 中，就称为节点n 点定义如果Xi是离散属性，那么的形式为，其中，就称节点n 子集注意 决策树算法原 X收X收 按 点划分而成的决策树图与相关的具体例子决策树算法原X颜X颜收橙高中橙高中x1红绿蓝 低 决策树算法原XXYi颜色{ 按 子集划分而成的决策树（只能是二叉树）图与相关的具体例子9.1决策树算法原常用决策树算ID3是Quinlan于1986年，是机器学习中一种广ID3算定义9.6信息自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X体的不确定性。设某事物具有n种相互独立的可能结果(或称状态)：x1x2n

P(x1),P(x2),P(xn

p(xi)

那么，该事物所具有的不确定量为 H(X)

p(x1)I(x1)p(x2)I(x2)p(xn)I(xn)p(xi)log2P(xi9.2.1ID39.2.1ID3 9.2.1ID3设训练数据集

D1D2,n是n维有穷向量空间，其中D

dt1,t2,,tn

tjDj

j1,2,,

设PD和ND是D的两个子集，分别叫做正例集和反例集ID3算 ID3算I(p,n)

p

p

p

，它将A分为

望是，那么，以属性AE(A)

piniI(p,nvv

p gain(A)

I(p,n)

E(ID3算设训练数据集D一共有m类样例，每类样例数为：v1,v2。同样以属性A作为决策树的根，具有v

将D分为v个子

Ci,D/

，假设子集中任意元组属于类C的概用表示。那么pi该子集的信息量定义如下所示mI(er)

DDvE(A)vj

I(erC4.5（2）连续数（3）缺失数（4）规C4.5 属性选择度ID系列的算法为什么会产生归纳偏置归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来这些样例一致。所以，要描述IDC4.5 属性选择度（1）（2）靠近的根节点将会有优先生成树的。第9章决策树算 C4.5 属性选择度补I系列算法的不足就要舍弃信息增益这个度量而选择别的决策属性作为度量标准。Qilan在他6年中的 中提出了一种可以使用的度量标准：增益比率。增益比率通过加入一个被称为信息（splitinformation）的项来惩罚类似Date这样的属性，信息用来衡量属性数据的vvAj

er er C4.5 属性选择度GainRati(A)

Gain(A)SplitI(A)C4.5对连续数据的处C4.5对连续数据的处Step1根据训练数据集D中各个属性的值对该Step2利用其中各属性的值对该训练数据集动Step3在划分后的得到的不同的结果集中确定Step4针对这两边各部分的值分别计算它们的贝叶斯分类方贝叶斯方法产生和发 于1763年Bayes的 贝叶斯分类方。贝叶斯分类方法是基于贝叶斯定理的贝叶斯分类可与决策树和神经元网络相媲在大型数据库中它具有高准确度和高速网络则属性间依赖。贝叶斯分类方贝叶斯定朴素贝贝叶斯网贝叶斯定XX是由一些属性表示（但不知属于那类HX属于类CP(H|X)我们希望确定X条件下H成立的概率，X是给定观测样本（观测到一些属性），要确定X属于C的概率，用贝叶斯方法计算出来这是H的后验概率。P(H):H先验概率(任意一个样本属于C类的概率P(X)：X先验概率，具有这些特征的样本，属于C类的概P(X|H)：在H条件下,X成立的概率,这是X的后验概率

H|

)

X|H)P(HP(X一个例子的数据 如苹果颜色为红色，形状为圆举例X是颜色为红色，形状为圆的物体,不知道是什么东P(H|X):在X是颜色为红色，形状为圆的物体条件P(HP(H|X)（后验概率）比P(H)（先验概率）基于 P(XX先验概率，取出一个样本，其为红色且圆的P(H|X)P(H|X)

这这P(X):朴素贝叶斯分X由nX={x1,x2,……xn它代表n个属性A1,A2,……An一点取值,如属性值与其它属性取值无关。C…A1到An的取值都A1独立2，属性n假定有mC1C2，给一个测试样本Xx1x2，xn}有n个属性，不知道它属于那类，用贝叶斯方法，可求出X可能属于那类Ci，当且仅当：P(Ci|

)P(Cj|

)P(P(Ci|XP(CP(Ci|X)P(X|Ci)P(CiP(X

，最大的类Ci最大P(X最大

P(Ci|XP(Ci|X)P(X|Ci)P(CiP(XP(CiP(CiP(X|CiP(CiP(X|CiP(CiP(X|Ci

为等概P(P(X|Ci)P(Ci都可由数据计算P(X|CiP(P(X|CiP(Ci在属性独立的情况下，就是朴素贝叶斯的情P(XP(X|CiP(P(X|Ci )P( |Ci k1n其P(P(xk|Ci)Sik/Si是样本集中为Ci类的个数，而Sik是第k个属性取值xk为Ci类的个数，Ci类取值xk的概率就是总样本集为S，有m个类，每类分别有样S1,S2,…Sm,这样Ci类的概率就为P(Ci)si/S这样测试样本X属于那类就有公式计算P(P(X|Ci)P(CiP(P(Ci|X)P(X|Ci)P(CiP(X Y属于那类? puter=?（yes还是属 mm mmm mm595用贝叶斯公P(Y|CP(Y|Ci)P(CiP(CiP(CiP(Y|P(Y|cj)P(yi|cjnC仅为2类 puter=yes, P(Y|cj)P(Y|cj)P(yi|cjn样本Y的属性为4个（n=4），分别为//8次计 ”30”, y4=credit_rating=“fair”P( P( puter=“no”)= e=“medium” e=“medium” P(student=“yes” P(student=“yes” P(credit=“fair” P(credit=“fair” P(Y puter=“yes”)P(Y puter=“no”) =P(Y =P(Y P(YP(Y|C1)P(C1P(YP(Y|C2)P(C2因此，对于样本朴素贝叶斯分类预测结P(C1|Y)>P(C2样本Y为C1类 另一个例子另一个例子P(M)=7/20,P(N)=13/20P(A|M)*P(M)=0.021>P(A|N)*P(N)=0.0027贝叶斯网络方不确定理和知识表示成为人工智能最活跃 nnn形式上，贝叶斯网络可定义为二元组B=<G>。 网络蕴含了条件独立性假设；参数向量（局部X={X1,X2,…,Xn}的联合概率分布：其中Pai表示G中变量Xi的父结点集 贝