一、k-最近邻
1、算法
积极学习方法（eager learner）：通过训练样本建立模型。
消极学习方法（lazy learner）：实例的学习，k-最近邻就属于这种。
k-最近邻算法：
令k是最近邻数目，D是训练样例集合
for z in 样例集合:
计算 z 和每个样例 (x,y) 的距离 d
选择离 z 前 k 个近距离的点，为集合 Dt
z的标记 y 为 Dt 中类较多的
k-最近邻采用多数表决的方法，该算法对 k 敏感：
\in D_{t}} I(v=y_{i}))
所以，需要降低 k 的影响，一种途径就是对距离的不同加权，如下，因为距离远的影响要弱一些，以距离平方的倒数为权值。
\in D_{t}}w_{i}\times I(v=y_{i}),w_{i}=\frac{1}{d(x',x_{i})^{2}})
2、最近邻分类器特征：
（1）实例的学习，不需要建模，但分类测试的开销很大。
（2）当k比较小的时候，对噪声非常敏感。
（3）可以生成任意决策边界。
二、贝叶斯分类器
1、贝叶斯公式
=\frac{P(X|Y_{j})P(Y_{j})}{P(X)}=\frac{P(X|Y_{j})P(Y_{j})}{\sum_{i=1}^{n}P(X|Y_{i})P(Y_{i})})
2、朴素贝叶斯
（1）条件独立性：
给定 Z，X 条件独立于 Y:
=P(X|Z))
则有：
=\frac{P(Z,Y,X)}{P(Z)}=\frac{P(Z,Y,X)}{P(Y,Z)}\frac{P(Y,Z)}{P(Z)}=P(X|Y,Z)P(Y|Z)=P(X|Z)P(Y|Z))
（2）朴素贝叶斯分类器：
=\frac{P(X|Y)P(Y)}{P(X)}=\frac{P(X_{1},...,X_{d})P(Y)}{P(X)}=\frac{P(Y)\prod_{i=1}^{d}P(X_{i}|Y)}{P(X)})
（3）连续属性的条件概率：
<1>把每个连续属性离散化，用相应的区间去替代原来的属性，但若某一个区间的样本数目过少，不容易做出可靠的估计。
<2>可以假设连续变量服从正态分布，Xi的概率等于：
=\frac{1}{\sqrt{2\pi}\sigma_{ij}}e{-\frac{(x_{i}-\mu_{ij}){2}}{2\sigma_{ij}}})
其中 mu 用样本均值估计， sigma 用样本方差估计。
（4）朴素贝叶斯举例：
拖欠贷款为 Y 变量。
5_01.png
测试记录X=（有房=否，婚姻状况=已婚，年收入=120K），求后验概率P（No|X）、P（Yes|X）。
总的 Y 可以知道，P（Yes）=0.3，P（No）=0.7。则：
P（X | No）=P（有房=否 | No）x P（婚姻状况=已婚 | No）x P（年收入=120K | No）=0.0024
P（X | Yes）= P（有房=否 | Yes）x P（婚姻状况=已婚 | Yes）x P（年收入=120K | Yes）=0
因为P（No|X）>P（Yes|X），所以该测试分类为No，不拖欠贷款。
上例中，P（婚姻状况=已婚 | Yes）=0，可能会出现极端现象，为了防止出现0，朴素贝叶斯没法正确分类，可以使用 m 估计（m-estimate）：
=\frac{n_{c}+mp}{n+m})
n 为 yi 的实例总数，nc 为 yi 中 xi 的实例数目，p 是用户指定，m 为等价样本大小的参数。上面的计算：P（婚姻状况=已婚 | Yes）=(0+3 x 1/3)/(3+3)=1/6，而不是0。
（4）朴素贝叶斯特征：
对于噪声点，朴素贝叶斯是健壮的。也可以处理属性值遗漏问题。
无关属性，朴素贝叶斯是健壮的。对于相关属性，可能会降低分类性能。
3、贝叶斯置信网络（Bayesian belief networks，BBN）
（1）模型表示：
两个主要成分：
一个有向无环图（DAG），表示变量之间的关系；
一个概率表，把各个结点和它的直接父节点关联起来。
性质1：条件独立
贝叶斯网络中的一个结点，如果它的父母结点已知，则它条件独立于它的所有非后代结点。
5_02.png
如图（b），给定C，A 条件独立于 B 和 D。
除了网络拓扑结构要求的条件独立外，每个结点还关联一个概率表。
（1）如果结点 X 没有父母结点，则表中只包含先验概率P(X);
（2）如果结点 X 只有一个父母结点 Y，则表中包含先验概率P(X | Y);
（3）如果结点 X 有多个父母结点{Y1，Y2...，Yk}，则表中只包含先验概率P(X|Y1，Y2...，Yk);
下图是一个贝叶斯置信网络。
5_03.png
（2）建立模型：
贝叶斯网络拓扑结构的生成算法：
设T=（X1，X2，...Xd）表示变量的全序
for j=1 to d do
令 XTj 表示 T 中第 j 个次序最高的变量
令A（XTj）={XT1，XT2，...XTj-1} 表示排在 XTj 前面的变量的集合
从A（XTj）中去掉对 Xj 没有影响的变量（使用先验知识）
在 XTj 和 A（XTj） 中的剩余变量之间画弧
考虑到图5_03，经过循环后，得到的如下概率：
P（D | E）化简为 P（D）
P（HD | E,D）不能化简
P（Hb | E,D,HD）化简为 P（Hb | D）
P（CP | E,D,HD,Hb）化简为 P（CP | HD,Hb）
P（BP | E,D,HD,Hb,CP）化简为 P（BP | HD）
上面的算法，保证了不会生成环。
不同的变量排序会产生不同的拓扑结构，理论上需要 d！种排序才能找到最优的，开销很大。代替方法是把变量分成原因变量和结果变量，从原因到结果画弧。
（3）使用BNN进行推理：
根据上面的贝叶斯置信网络图，有下面情况：
5_04.png
5_05.png
（4）BNN的特点：
构造网络比较费时，但网络结构一旦确定下来，添加新变量就变得容易。
很适合处理不完整数据，对有属性遗漏的可以通过概率或求积分来加以处理。
数据和先验知识结合起来，该方法对于模型的过拟合问题是非常鲁棒的。
网友评论