《统计学习方法》-03k邻近和朴素贝叶斯

# k近邻和朴素贝叶斯

## k近邻

k近邻很简单……

k近邻是一个不需要训练的算法，但是想要实现还是需要一些算法来优化的。

通过给定的距离度量，在训练集$T$中找到与$x$最邻近的$k$个点，$k$的值需要设定，，然后根据某一种分类决策规则，决定$x$的种类$y$，比如根据多数表决：
$$
y=\arg \max_{c_j} \sum_{x_i \in N_k(x)}I(y_i=c_j),\ \ \ \ i=1,2,...,K
$$
其中，$I$为指示函数。

### 距离度量

根据线性代数中对范数的定义，我们有：
$$
L_p(x_i,x_j)=\Large{\big(\sum_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^p\big)^{\frac{1}{p}}}
$$
当$p=2$时为欧式距离。

### k值的选择

选择较小的k，可以比较精确地划分实例的类别，但是也会很容易受到噪声的影响，而选择较大的k，学习的近似误差会增大。一般在应用中，会采用交叉验证法来选择合适的k值。



## 朴素贝叶斯

朴素贝叶斯法是典型的生成学习方法，由训练数据生成联合概率分布$P(Y,X)$，将测试数据计算得到的最大的概率的那一类，当作分类预测的结果，朴素贝叶斯的目标是分类。

### 联合概率分布

联合概率分布可以由先验概率和条件概率来得到：
$$
P(X,Y)=P(Y)P(X|Y)
$$
也就是说，只要知道了先验概率分布$P(Y)$和条件概率分布$P(X|Y)$，就可以算出联合概率分布，而先验概率分布和条件概率分布可以由极大似然估计或者贝叶斯估计得出。

### 极大似然估计

极大似然估计就是通过事件发生的频率来估计事件发生的概率：
$$
\Large{{P(Y=c_k)=\frac{\sum_{i=1}^{N} I(y_i=c_k)}{N}}}\\
\Large{P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^{N} I(x_i^{(j)}=a_{jl},y_i=C_k)}{\sum_{i=1}^N I(y_i=c_k)}}
$$

### 贝叶斯估计

由极大似然估计得到的概率，如果概率值为零的话，会影响到后验概率的计算（分母不能为零）

那么，在随机变量各个取值的频数上赋予一个正数$\lambda>0$，就可以避免这个问题：
$$
\Large{{P(Y=c_k)=\frac{\sum_{i=1}^{N} I(y_i=c_k)+\lambda}{N+K\lambda}}}\\
\Large{P(X^{(j)}=a_{jl}|Y=c_k)=\frac{\sum_{i=1}^{N} I(x_i^{(j)}=a_{jl},y_i=C_k)}{\sum_{i=1}^N I(y_i=c_k)}}
$$

 在这里，$\lambda=0$时为极大似然估计，$\lambda=1$时是拉普拉斯平滑，其中的一些参数是，$l=1,2,...,S_j$，$k=1,2,...,K$

### 朴素贝叶斯法

有了计算各个概率的方法之后，我们就可以去计算每一个$P(Y=c_k|X=x)$，然后取值最大的那个概率对应的$Y$作为预测的结果。

在学习的时候，我们需要模型去学习一个机制，使得$P(Y=c_k|X=x)$能够最大，这就确保了，当系统接收到一个输入样本$X=x$的时候，系统最可能给出正确的分类答案，即$Y=c_k$。

有极大似然估计或者贝叶斯估计，我们可以计算出$P(X=x|Y=c_k)$和$P(Y=c_k)$，那么我们怎么才能得到$P(Y=c_k|X=x)$呢？

由贝叶斯公式（或者贝叶斯定理），我们有：
$$
\Large{P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x|Y=c_k)P(Y=c_k)}}
$$
而我们知道，任何一个输入的样本都可以被表示为一个n维向量，那么条件概率分布：
$$
P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k),\ \ \ k=1,2,...,K
$$
而在朴素贝叶斯法中，对条件概率分布做了__条件独立性__的假设，那么就有：
$$
\begin{align}
\large{P(X=x|Y=c_k)=P(X^{(1)}=}&\large{x^{(1)},...,X^{(n)}=x^{(n)}|Y=c_k)}\\
\large{=}&\large{\prod_{j=1}^nP(X^{(i)}=x^{(i)}|Y=c_k)}
\end{align}
$$
于是乎：
$$
\Large{P(Y=c_k|X=x)=\frac{P(Y=c_k)\prod _jP(X^{(j)}=x^{(j)}|Y=c_k)}{\sum_kP(Y=c_k\prod_jP(X^{(j)}=x^{(j)}|Y=c_k)}}
$$
省去不会变化的分母，朴素贝叶斯分类器可以表示为：
$$
\Large{y=\arg \max_{c_k}P(Y=c_k)\prod _jP(X^{(j)}=x^{(j)}|Y=c_k)}
$$
也就是说，找到一个$y=c_k$，使得上式最大化即可，这个$y$就是分类器预测的结果。