k-近邻学习,朴素贝叶斯，期望最大化，最大熵模型算法介绍

k-近邻学习 k-Nearest Neighbor(KNN)

1. 算法描述

k-近邻学习是一种监督的分类回归方法。工作机制：给定测试样本，基于某种距离度量找出训练集中与其最接近的k和训练样本，然后基于这k个“邻居”的信息进行预测。通常，在分类任务中采用“投票法”；在回归任务中采用“平均法”（也可根据距离远近进行“加权”）。**三个基本要素：**k值得选择，距离度量及分类/回归决策规则。“懒惰学习”没有显示的训练过程。

1.1 距离度量

Lp距离：Lp(xi,xj)=(∑l=1n|xli−xlj|p)1p,p≥1，当p=2 称为“欧氏距离”(Eucliden distanceL2)，当p=1 称为“曼哈顿距离”，当p=∞ 时，它是各个坐标距离的最大值：L∞(xi,xj)=maxl|xli−xlj|
1.2 k值得选择

k值较小，相当于用较小的邻域进行预测，优点是可以学习的近似误差会减小，缺点是学习的估计误差会增大，k值的减小会使模型变复杂，容易过拟合；k值较大，相当于用较大的邻域进行预测，优点是可以减小学习的估计误差，缺点是学习的近似误差会增大。通常采用“交叉验证”来选取最优的k值。

2. 优缺点

优点：

1.简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；

2.可用于数值型数据和离散型数据；

3.训练时间复杂度为O(n)；无数据输入假定；

4.对异常值不敏感

5.KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练

6.计算时间和空间线性于训练集的规模

缺点：

1.计算复杂性高；空间复杂性高；

2.样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

3.KNN每一次分类都会重新进行一次全局运算，计算量太大。

4.最大的缺点是无法给出数据的内在含义。

5.k值大小的选择。

3. kd树

为了提高k近邻搜索的效率，考虑使用特殊的结构存储训练数据，以减少计算距离的次数。

kd树是一种对k维空间中的实例点进行存储以便进行快速检索的树形数据结构，kd树是二叉树，对k维空间的一个划分。

构造kd树：构造根节点，使根节点对应于k维空间包含所有实例点的超矩形区域；通过下面的递归，不断地对k维空间进行切分，生成子节点：在节点上选择一个坐标轴和该坐标轴上的一个切分点（选择中位数作为切分点得到的kd树是平衡点），将当前结点切分为左右子节点（将超矩形区域通过切分点且垂直切分轴的平面切分为两个子区域）；直到两个子节点不能再切分为止。

用kd树的最近邻搜索

在kd树中找出包含目标点x的叶节点：从根节点出发，递归地向下访问kd树。若目标点当前维的坐标小于切分点的坐标，则移动到左子节点，否则移动到右子节点，直到子节点为叶子结点为止。
以此叶节点为“当前最近点”。
递归的向上回退，在每个节点进行以下操作：

a) 如果该节点保存的实例点比当前最近点距离目标更近，则以该实例点为“当前最近点”。

b) 当前最近点一定存在于该节点一个子节点对应的区域。检查该子节点的父节点的另一个子节点对应的区域是否有更近的点（具体的，检查另一个子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距离目标更近的点，移动到另一个子结点。接着，递归的进行最近邻搜索。如果不相交，向上回退）。
当回退到根节点时，搜索结束。最后的“当前最近点”为目标点的最近邻点。

如果实例点是随机分布的，kd树搜索的平均计算复杂度是O(logm)，这里m是训练实例数。kd树更适用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

朴素贝叶斯，期望最大化，最大熵模型

1. 贝叶斯分类器

1.1 朴素贝叶斯(naive bayes)

朴素贝叶斯法是基于贝叶斯定理(P(A|B)=P(A)P(B|A)P(B) )与特征条件独立假设（分类的特征在类确定的条件下都是条件独立的）的分类方法。工作机制：对于给定训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的测试样本，利用贝叶斯定理求出后验概率最大的输出。设输入空间X⊆Rn为n维向量的集合，输出空间为类标记集合Y={c1,c2,⋯,cK} 。输入为特征向量x∈X，输出标记为y∈Y。X表示输入空间上的随机变量，Y表示输出空间上的随机变量，P(X,Y)表示X和Y的联合概率分布，且训练数据集D={(x1,y1),(x2,y3),⋯,(xm,ym)} 由P(X,Y)独立分布产生。

1.1.1 朴素贝叶斯算法流程

朴素贝叶斯分类时，对给定的输入x，通过学习得到的模型计算后验概率分布P(Y=ck|X=x)，将后验概率最大的类作为x的类输出。后验概率的计算根据贝叶斯定理进行：P(Y=ck|X=x)=P(X=x|Y=ck)P(Y=ck)P(X=x)=P(Y=ck)∏j=1nP(Xj=xj|Y=ck)P(X=x)

于是，朴素贝叶斯分类器可表示为：f(x)=argmaxckP(Y=ck)∏j=1nP(Xj=xj|Y=ck) 。

1.1.2 后验概率最大化的含义：等价于0-1损失函数时的期望风险最小化，期望风险函数为：Rexp(f)=E[L(Y,f(X))]，期望是对联合概率分布取的，由此取条件期望为： Rexp(f)=EX∑k=1K[L(ck,f(X))]P(ck|X)，为使期望风险最小化，只需对X=x逐个极小化，由此得：f(x)=argminy∈Y∑k=1KL(ck,y)P(ck|X=x)=argminy∈Y∑k=1KP(y≠ck|X=x)=argminy∈Y∑k=1K(1−P(y=ck|X=x))=argmaxy∈Y∑k=1KP(y=ck|X=x)后验概率最大化规则

1.1.3 朴素贝叶斯法的参数估计：在朴素贝叶斯法中，学习意味着估计先验概率和条件概率，可以应用极大似然估计法估计相应的概率。P(Y=ck)=∑i=1mI(yi=ck)m，设第j维特征xj可能的取值集合为{aj1,aj2,⋯,ajSj}，条件概率的极大似然估计为：P(Xj=ajl|Y=ck)=∑i=1mI(xji=ajl,yi=ck)∑i=1mI(yi=ck) 。

1.1.4 朴素贝叶斯算法流程：

计算先验概率及条件概率：P(Y=ck)和P(Xj=ajl|Y=ck)；
对于给定的实例x=(x1,x2,⋯,xn)T，计算P(Y=ck)∏j=1nP(Xj=xj|Y=ck)
确定实例x的类：y=argmaxckP(Y=ck)∏j=1nP(Xj=xj|Y=ck)。

1.1.5 贝叶斯估计：用极大似然估计可能会出现所要估计的概率值为0的情况，会影响到后验概率的计算结果模式分类产生偏差。解决这一问题的方法是采用贝叶斯估计。条件概率的贝叶斯估计为：Pλ(Xj=ajl|Y=ck)=∑i=1mI(xji=ajl,yi=ck)+λ∑i=1mI(yi=ck)+λ常取λ=1 称为拉普拉斯平滑。先验概率的贝叶斯估计为：P(Y=ck)=∑i=1mI(yi=ck)+λm+Kλ。

1.1.6 朴素贝叶斯算法的优缺点

优点：

1.生成式模型，通过计算概率来进行分类，可以用来处理多分类问题，

2.对小规模的数据表现很好，适合增量式训练，所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。

缺点：

1.对输入数据的表达形式很敏感，

2.由于朴素贝叶斯的“朴素”特点（特征条件独立），所以会带来一些准确率上的损失。

3.需要计算先验概率，分类决策存在错误率。

4.由于使用了样本属性独立性的假设，所以如果样本属性有关联时其效果不好。

2 半朴素贝叶斯分类器

基本思想：适当地考虑一些特征间的相互依赖信息，从而不需要进行完全联合概率计算，又不至于彻底忽略了比较强的特征依赖关系。“独依赖估计(One-Dependent Estimator,简称ODE)”：所谓“独依赖”就是假设每个特征在类别之外最多仅依赖于一个其他特征。比如，SPODE(Super-parent ODE)：假设所有特征都依赖于同一个特征，称为“超父”，然后通过交叉验证等模型选择方法确定超父特征。TAN(Tree Augment naive Bayes)：在最大带权生成树算法的基础上，通过条件互信息保留强相关特征之间的依赖性。AODE(Average ODE)：基于集成学习机制的独依赖分类器，AODE尝试将每个特征作为超父构建SPODE，然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果。考虑高阶依赖（对多个特征依赖），将ODE扩展到kODE。

3 贝叶斯网

贝叶斯网(Bayesian network)亦称“信念网”(belief network)，它借助有向无环图来刻画特征间的依赖关系，并使用条件概率表(Conditional Probability Table,DPT)来描述特征的联合概率分布。具体来说，一个贝叶斯网B由结构G和参数Θ两部分组成，B=<G,Θ>，网络结构G是一个有向无环图，其每个节点对应一个特征，若两个特征间存在直接依赖关系，则它们由一条边连接起来；参数Θ定量描述依赖关系，假设特征x在G中的父节点集为πi，则Θ包含了每个特征的条件概率表θxj|πj=PB(xj|πj) 。

3.1 结构

给定父节点集，贝叶斯网假设每个特征与它的非后裔特征独立，于是B=<G,Θ>将特征x1,x2,⋯,xn的联合概率分布定义为：PB(x1,x2,⋯,xn)=∏j=1nPB(xj|πj)=∏j=1nθxj|πj，三种典型的依赖关系结构如图所示：

k-近邻学习,朴素贝叶斯，期望最大化，最大熵模型算法介绍

在“同父”结构中，给定父节点x的取值，则y和z条件独立；在“顺序”结构中，给定节点x的取值，则y和z条件独立；在“V型”结构中，给定x的取值，则y和z必不独立，但若x的取值完全未知，y和z相互独立，称为“边际独立性”。可使用“有向分离”分析有向图中变量间的条件独立性。

3.2 学习

若网络结构已知，则贝叶斯网的学习过程相对简单，只需对训练样本“计数”，估计出每个节点的条件概率表。“评价搜索”：根据训练数据集来找出结构最“恰当”的贝叶斯网的常用方法。具体来说，我们先定义一个评分函数，以此来评价贝叶斯网与训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网。常用的评分函数是基于信息论准则，该类准则将学习问题看作一个数据压缩任务，学习目标是找到一个能以最短编码长度描述训练数据的模型，编码的长度包括描述模型自身所需的字节长度和使用该模型描述数据所需的字节长度，“最小描述长度”准则。

给定训练集D={x1，x2,⋯,xm}，贝叶斯网B=<G,Θ>在D上的评分函数可写为：s(B|D)=f(θ)|B|−LL(B|D)|B|是贝叶斯网的参数个数；f(θ)表示描述每个参数θ所需的字节数；LL(B|D)=∑i=1mlogPB(xi)=∑i=1m∏j=1nlogθxji|πji是贝叶斯网的对数似然，则上式函数第一项是计算编码贝叶斯网所需的字节数，第二项是计算B所对应的概率分布PB描述训练集所需的字节数。若f(θ)=1得到AIC评分函数；若f(θ)=12logm得到BIC评分函数；若f(θ)=0则退化到极大似然估计任务。

若贝叶斯网B=<G,Θ>的网络结构固定，则评分函数第一项为常数，最小化s(B|D)等价于参数Θ的极大似然估计，由公式可知参数θxj|πj能直接在训练数据上通过经验估计获得：θxj|πj=P^D(xj|πj)，其中P^D是D上的经验分布。因此，为了最小化评分函数，只需对网络结构进行搜索，而候选结构的最优参数可在训练集上得到。但从所有可能的网络结构空间搜索最优网络结构是一个NP难问题，有两种常用的策略能在有限时间求得近似解：第一种是贪心法；第二种是通过给网络结构施加约束来消减搜索空间。

3.3 推断

通过已知变量观测值来推测带查询变量的过程称为“推断”，已知变量观测值称为“证据”。最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，但这样的“精确推断”已被证明是NP难的；换言之，当网络节点多、连接稠密时，难以进行精确推断，需要借助“近似推断”，通过降低精度要求，在给定时间内求得近似解。在现实应用中，贝叶斯网的近似推断常用吉布斯采样(Gibbs sampling)来完成。

令Q={Q1,Q2,⋯,Qm} 表示待查询变量，E={E1,E2,⋯,En}为证据变量，已知其取值为e={e1,e2,⋯,en}。目标是计算后验概率P(Q=q|E=e)，其中q={q1,q2,⋯,qm} 是待查询变量的一组取值。吉布斯采样流程：先随机产生一个与证据E=e一致的样本q0作为初始点，然后每步从当前样本出发产生下一个样本。具体来说，在第t次采样中，算法先假设qt=qt−1，然后对非证据变量诸葛进行采样改变其值，采样概率根据贝叶斯网和其他变量的当前取值(即Z=z)计算获得。假定经过T次采样得到与q一致的样本共nq个，则可近似估算出后验概率P(Q=q|E=e)≃nqT。

实质上，吉布斯采样是在贝叶斯网所有变量的联合状态空间与证据E=e一致的子空间中进行“随机漫步”。每一步近依赖于前一步的状态，这是一个“马尔科夫链”。在一定条件下，无论从什么状态开始，马尔科夫链第t步的状态在t→∞必收敛于一个平稳分布。对于吉布斯采样来说，这个分布恰好就是P(Q|E=e)。在T很大时，吉布斯采样相当于根据P(Q|E=e)采样，从而可以近似估计后验概率。注意，由于马尔科夫链通常需要很长时间才能趋于平稳分布，所以吉布斯采样算法的收敛速度较慢。此外，若贝叶斯网存在锦缎概率“0”或“1”，则不能保证马尔科夫链存在平稳分布，此时吉布斯采样会给出错误的估计结果。

2. EM 期望最大化算法

EM算法是含有“隐变量”的概率模型参数的极大似然估计法。将观测数据表示为X ，未观测数据表示为Z ，则观测数据的似然函数为P(X|θ)=∑ZP(Z|θ)P(X|Z,θ)。EM迭代算法流程如下：

选择模型参数的初值θ(0)，开始迭代；
E步：记θ(t)为第t次迭代参数θ的估计值，在第t+1次迭代的E步，计算Q(θ,θ(t))=∑ZlogP(X,Z|θ)P(Z|X,θ(t))；
M步：求使Q(θ,θ(t))极大化的参数θ，确定第t+1次迭代的参数的估计值θ(t+1)=argmaxθQ(θ,θ(t))；
重复E步和M步，直到收敛。

上述过程中的Q函数是关于给定观测数据和当前参数下对未观测数据的条件概率的期望。**注意：**EM算法对初值敏感；给出停止迭代的条件，一般是较小的整数ε1,ε2，若满足∥θ(t+1)−θ(t)∥<ε1 或Q(θ(t+1),θ(t))−Q(θ(t),θ(t))<ε2则停止迭代。

2.1 高斯混合模型

高斯混合模型是指具有P(x|θ)=∑k=1Kαkϕ(x|θk)形式的概率分布模型，其中αk是系数：αk≥0,∑k=1Kαk=1；ϕ(x|θk)是高斯分布密度，θk=(μk,σ2k);ϕ(x|θk=12π√σkexp(−(x−μ)22σ2k)称为第k个分模型。

一般混合模型可以由任意概率分布密度代替高斯分布密度。

高斯混合模型参数估计的EM算法

假设观测数据x1,x2,⋯,xm 由高斯混合模型产生，我们由EM算法估计高斯混合模型的参数。

第一步：明确隐变量，写出完全数据的对数似然函数

观测数据xi是这样产生的：首先依概率αk选择第k个高斯分布分模型ϕ(x|θk)；然后依第k个分模型的概率分布ϕ(x|θk)生成观测数据xi。这时观测数据xi已知，但反映观测数据xi来自第k个分模型的数据是未知的，以隐变量γik表示，其定义如下：

γ i k = {1, 0, 第 j 个 观 测 来 自 第 k 个 分 模 型; 否 则 .

则完全数据的似然函数为：

P (x, γ | θ) = = = = \prod i = 1 m P (x i, γ i 1, γ i 2, \dots, γ i K | θ) \prod k = 1 K \prod i = 1 m [α k ϕ (x i | θ k)] γ i k \prod k = 1 K α n k k \prod i = 1 m [ϕ (x i | θ k)] γ i k \prod k = 1 K α n k k \prod i = 1 m [1 2 π - - \sqrt σ k exp (- (x i - μ k) 2 2 σ 2 k)] γ i k

式中，nk=∑i=1mγik,∑k=1Knk=m 。那么，完全数据的对数似然为：

log P (x, γ | θ) = \sum k = 1 K {n k log α k + \sum i = 1 m γ i k [log (1 2 π - - \sqrt) - log σ k - 1 2 σ 2 k (x i - μ k)]}

第二步：EM算法的E步：确定Q函数

Q (θ, θ (t))  = = =  E [log P (x, γ | θ) | x, θ (t)] E {\sum k = 1 K {n k log α k + \sum i = 1 m γ i k [log (1 2 π - - \sqrt) - log σ k - 1 2 σ 2 k (x i - μ k)]}}  \sum k = 1 K {{(E γ i k) log α k + \sum i = 1 m (E γ i k) [log (1 2 π - - \sqrt) - log σ k - 1 2 σ 2 k (x i - μ k)]}}

需要计算E(γik|x,θ)，记为γ^ik(当前模型参数下第i个观测数据来自第k个分模型的概率，称为分模型k对观测数据xi的响应度)：

γ^i k = = = = E (γ i k | x, θ) = P (γ i k = 1 | x, θ)  P (γ i k = 1, x i | θ) \sum K k = 1 P (γ i k = 1, x i | θ)  P (x i | γ i k = 1, θ) P (γ i k = 1 | θ) \sum K k = 1 P (x i | γ i k = 1, θ) P (γ i k = 1 | θ)  α k ϕ (x i | θ k) \sum K k = 1 α k ϕ (x i | θ k) 

将γ^ik=E(γik|x,θ)及nk=∑i=1mEγik代入Q函数得：

Q(θ,θ(t))=∑k=1K{nklogαk+∑i=1mγik^[log(12π−−√)−logσk−12σ2k(xi−μk)]}

第三步：确定EM算法的M步

计算新一轮迭代的模型参数：μ^k=∑i=1mγ^ikxi∑i=1mγ^ik,σ^2k=∑i=1mγ^ik(xi−μk)2∑i=1mγ^ik,α^k=nkm=∑i=1mγ^ikm。

2.2 EM算法的优缺点

优点

M步仅涉及完全数据极大似然，通产计算比较的简单
收敛是稳定的

缺点

当缺失数据大或者完全数据的对数似然估计比较复杂时，EM算法的收敛速度将很缓慢
EM算法本质上是非凸的，很容易陷入局部最优。
EM算法对初始值敏感

3. 最大熵模型

3.1 最大熵原理

学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。

假设离散随机变量X的概率分布是P(X)，则其熵是：H(P)=−∑xP(x)logP(x)，熵满足不等式：0≤H(P)≤log|X|式中|X|是X的取值个数，当且仅当X的分布式均匀分布时右边的等号成立。

最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。

3.2 最大熵模型的定义

给定训练数据集D={(x1,y1),(x2,y3),⋯,(xm,ym)}，可以确定联合分布P(X,Y) 的经验分布和边缘分布P(X)的经验分布，分别以P~(X,Y),P~(X) 表示。具体的，P~(X=x,Y=y)=v(X=x,Y=y)m,P~(X=x)=v(X=x)m ，其中v(⋅)表示出现的频数。用特征函数f(x,y)描述输入x和输出y之间的某一个事实（约束条件），是一个二值函数，当x和y满足某一事实时，值为1；否则值为0。

特征函数关于经验分布P~(X,Y)的期望值EP~(f)=∑x,yP~(x,y)f(x,y)；特征函数关于模型P(Y|X)与经验分布P~(X)的期望值EP(f)=∑x,yP~(x)P(y|x)f(x,y)，如果模型能够获取训练数据中的信息，那么就可以假设EP~(f)=EP(f)，我们将它作为模型学习的约束条件。有多少个特征函数对应多少个约束条件。

假定满足所有约束条件的模型集合为C={P∈P|EP~(fi)=EP(fi),i=1,2,⋯,k}，定义在条件概率分布P(Y|X)上的条件熵为H(P)=−∑x,yP~(x)P(y|x)logP(y|x)，则称模型集合中条件熵最大的模型为最大熵模型。

3.3 最大熵模型的学习

最大熵模型的学习等价于约束最优化问题：

max P \in C s . t . H (P) = - \sum x, y P ~ (x) P (y | x) log P (y | x)  E P (f k) = E P ~ (f k), k = 1, 2, \dots, K  \sum y P (y | x) = 1  

对应的最小化问题为：

min P \in C s . t . - H (P) = \sum x, y P ~ (x) P (y | x) log P (y | x)  E P (f k) - E P ~ (f k) = 0, k = 1, 2, \dots, K  \sum y P (y | x) = 1  

引入拉格朗日乘子β0,β1,⋯,βK，定义拉格朗日涵数L(P,β):

L (P, β) = = + - H (P) + β 0 (1 - \sum y P (y | x)) + \sum k = 1 K β k (E P ~ (f i) - E P (f i)) \sum x, y P ~ (x) P (y | x) log P (y | x) + β 0 (1 - \sum y P (y | x)) \sum k = 1 K β k (\sum x, y P ~ (x, y) f (x, y) - \sum x, y P ~ (x) P (y | x) f (x, y))

将其解记作：Pβ=argminP∈CL(P,β)=Pβ(y|x) 。具体地，求L(P,β)对P(y|x)的偏导数为0，

\partial L (P, β) \partial P (y | x) = = = \sum x, y P ~ (x) (log P (y | x) + 1) - \sum y β 0 - \sum x, y (P ~ (x) \sum k = 1 K β k f k (x, y)) \sum x, y P ~ (x) (log P (y | x) + 1 - β 0 - \sum k = 1 K β k f k (x, y)) 0

得：P(y|x)=exp(∑k=1Kβkfk(x,y)+β0−1)=exp(∑k=1Kβkfk(x,y))exp(1−β0),由∑yP(y|x)=1得Pβ(y|x)=1Zβ(x)exp(∑k=1Kβkfk(x,y)),其中Zβ(x)=∑yexp(∑k=1Kβkfk(x,y))。当选定合适的特征函数时，最大熵模型可以导出多项逻辑模型，这个很显然。但二者并不等价，最大熵可以选择其他特征函数。

记对偶函数为Ψ(β)=minP∈CL(P,β)=L(Pβ,β)，接下来最大化Ψ(β)得到其解β∗。则最大熵模型为：P∗=Pβ∗(y|x)。

可证明，对偶函数等价于条件概率分布P(Y|X)的对数似然函数LP~(Pβ)=∑x,yP~(x,y)logP(y|x)，则最大熵模型的学习中的对偶函数极大化等价于最大熵模型的极大似然估计。

k-近邻学习,朴素贝叶斯，期望最大化，最大熵模型算法介绍

相关推荐