第8周

---

十四、K近邻法(KNN)

近朱者赤，近墨者黑。我们判断一个人的人品，只需要观察他来往最密切的几个人的人品好坏，这里就运用了KNN的思想。

K近邻是一种分类和回归的方法，现在只讨论分类问题中的K近邻。

K近邻原理简单直观：给定训练集，对于要分类的点，在训练集中找到与其最邻近的k个点，这k个点多数属于哪一类，这个要分类的点就属于哪类。

14.1 KNN模型三要素

距离度量、k值选择和分类决策规则。

• 距离度量：两个点之间的距离有多种度量方式，最常用的是欧式距离：

  $D(x,y)=\sqrt{(x_1-y_1{)}^2+(x_2-y_2{)}^2+...+(x_n-y_n{)}^2}=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$

  还有曼哈顿距离：

  $D(x,y)=|x_1-y_1|+|x_2-y_2|+...+|x_n-y_n|=\sum _{i=1}^n|x_i-y_i|$

  闵可夫斯基距离(Minkowski Distance):

  $D(x,y)=\sqrt[p]{(|x_1-y_1|{)}^p+(|x_2-y_2|{)}^p+...+(|x_n-y_n|{)}^p}=\sqrt[p]{\sum _{i=1}^n(|x_i-y_i|{)}^p}$

  当p为1即曼哈顿距离，当p为2即欧式距离。

• k值选择：选择较小的k值，只有与输入实例较近或相似的训练实例才会对预测结果起作用，意味着整体模型变得复杂，容易发生过拟合；
  选择较大的k值，这时候与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，意味着整体的模型变得简单。

  在应用中，k一般取一个比较小的值，通常采用交叉验证法来选最优的k值

• 分类决策规则：决策方式一般是多数表决，即少数服从多数。

14.2 构造kd树

如果计算输入实例（未知）和每个训练实例（已知）的距离，当训练集规模很大时，计算非常耗时是不可行的。如何对训练数据进行快速的k近邻搜索？

kd树是对数据进行二叉树结构存储以便加快检索。方法是依次选择用垂直于坐标轴的超平面将k维空间切分，形成k维矩形区域，切分点一般为特征值的中位数，kd树每个结点对应于一个矩形区域。举个例子

给定一个二维空间数据集{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}

先选择x轴，x坐标的中位数为6，但数据中没有这样的点，所以选择7，即过（7，2）做一条垂直x轴的切线分为两部分，接下来左边矩形选择y轴的中位数4，做一条垂直y轴的切线分为两部分，右边及其他以此类推。kd树如下图：

14.3 搜索kd树

​ 当生成KD树以后，就可以去预测测试集里面的样本目标点了。对于一个目标点，我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。

从上面的描述可以看出，KD树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。

用14.2建立的KD树，来看对点(2,4.5)找最近邻的过程。先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<(7,2)，(5,4)，(4,7)>，但 （4,7）与目标查找点的距离为3.202，而（5,4）与查找点之间的距离为3.041，所以（5,4）为查询点的最近点； 以（2，4.5）为圆心，以3.041为半径作圆，如下图所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找，也就是将（2,3）节点加入搜索路径中得<(7,2)，(2,3)>；于是接着搜索至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5；回溯查找至（5,4），直到最后回溯到根结点（7,2）的时候，以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图所示。至此，搜索路径回溯完，返回最近邻点（2,3），最近距离1.5。

对应的图如下：

十五、朴素贝叶斯

在所有的机器学习分类算法中，朴素贝叶斯和其他绝大多数的分类算法都不同。对于大多数的分类算法，比如决策树,KNN,逻辑回归，支持向量机等，他们都是判别方法，也就是直接学习出特征输出Y和特征X之间的关系，要么是决策函数$Y=f(X)$,要么是条件分布$P(Y|X)$。但是朴素贝叶斯却是生成方法，也就是直接找出特征输出Y和特征X的联合分布$P(X,Y)$,然后用$P(Y|X)=P(X,Y)/P(X)$得出。

贝叶斯学派的思想可以概括为先验概率+数据=后验概率。频率学派攻击贝叶斯学派的是先验概率，一般来说先验概率就是对于数据所在领域的历史经验，但是这个经验常常难以量化或者模型化，于是贝叶斯学派大胆的假设先验分布的模型，比如正态分布，beta分布等。这个假设一般没有特定的依据，因此一直被频率学派认为很荒谬。虽然难以从严密的数学逻辑里推出贝叶斯学派的逻辑，但是在很多实际应用中，贝叶斯理论很好用，比如垃圾邮件分类，文本分类。

朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法，因为对条件概率作了条件独立性这个较强的假设，所以称为“朴素”。

具体方法是对于给定的训练数据集，首先基于特征条件独立假设学习输入输出的联合概率分布，然后基于此模型，对给定的输入x，利用贝叶斯定理求出后验概率最大的输出y。

• 假设有m个样本，每个样本有n个特征，特征输出有K个类别，定义为$C_1,C_2,...,C_K$。

• 从样本可以学习先验分布$P(Y=C_k)(k=1,2,...K)$,就是类别$C_k$在训练集里面出现的频数；

• 接着学习到条件概率分布$P(X=x|Y=C_k)=P(X_1=x_1,X_2=x_2,...X_n=x_n|Y=C_k)$；

• 然后我们就可以用贝叶斯公式得到X和Y的联合分布P(X,Y)了。联合分布P(X,Y)定义为：

$$\begin{array}{rl}P(X,Y=C_k)& =P(Y=C_k)P(X=x|Y=C_k)\\ & =P(Y=C_k)P(X_1=x_1,X_2=x_2,...X_n=x_n|Y=C_k)\end{array}$$

但是$P(X_1=x_1,X_2=x_2,...X_n=x_n|Y=C_k)$很难求出,这是一个超级复杂的有n个维度的条件分布。朴素贝叶斯模型就是在这里做了一个大胆的假设，即X的n个维度之间相互独立，这样就可以得出:

$$P(X_1=x_1,X_2=x_2,...X_n=x_n|Y=C_k)=P(X_1=x_1|Y=C_k)P(X_2=x_2|Y=C_k)...P(X_n=x_n|Y=C_k)$$

从上式可以看出，这个很难的条件分布大大的简化了，但是这也可能带来预测的不准确性。你会说如果我的特征之间非常不独立怎么办？如果真是非常不独立的话，那就尽量不要使用朴素贝叶斯模型了，考虑使用其他的分类方法比较好。但是一般情况下，样本的特征之间独立这个条件的确是弱成立的，尤其是数据量非常大的时候。虽然我们牺牲了准确性，但是得到的好处是模型的条件分布的计算大大简化了，这就是贝叶斯模型的选择。

• $$P(Y_k|X)=\frac{P(X|Y_k)P(Y_k)}{\sum _{k}P(X|Y=Y_k)P(Y_k)}$$，最后计算出所有的K个条件概率$P(Y=C_k|X=X^{(test)})$,然后找出最大的条件概率对应的类别，这就是朴素贝叶斯的预测了。

注：

某些时候，可能某些类别在样本中没有出现，这样可能导致$P(X_j=X_j^{(train)}|Y=C_k)$为0，这样会影响后验的估计，为了解决这种情况引入：

$$P(X_j=X_j^{(train)}|Y=C_k)=\frac{m_{k{j}^{train}}+\lambda }{m_k+O_j\lambda }$$

其中$\lambda$ 为一个大于0的常数，常常取1称为拉普拉斯平滑。$O_j$为第j个特征的取值个数。