记录小润了解的各种机器学习算法的实现以及基础概念.zip

###github不支持Latex，公式显示不了，请查看[博文](http://blog.csdn.net/u012162613/article/details/48323777) ------- 朴素贝叶斯（Naive Bayes）是一种简单的分类算法，它的经典应用案例为人所熟知：文本分类（如垃圾邮件过滤）。很多教材都从这些案例出发，本文就不重复这些内容了，而把重点放在理论推导（其实很浅显，别被“理论”吓到），三种常用模型及其编码实现（Python）。 如果你对理论推导过程不感兴趣，可以直接逃到三种常用模型及编码实现部分，但我建议你还是看看理论基础部分。 另外，本文的所有代码都可以在[这里获取]() #1. 朴素贝叶斯的理论基础 >朴素贝叶斯算法是基于贝叶斯定理与特征条件独立假设的分类方法。 这里提到的**贝叶斯定理**、**特征条件独立假设**就是朴素贝叶斯的两个重要的理论基础。 ##1.1 贝叶斯定理 先看什么是**条件概率**。 P(A|B)表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。其基本求解公式为：$P(A|B)=\frac{P(AB)}{P(B)}$ 贝叶斯定理便是基于条件概率，通过P(A|B)来求P(B|A)： $P(B|A)=\frac{P(A|B)P(B)}{P(A)}$ 顺便提一下，上式中的分母P(A),可以根据全概率公式分解为： $P(A)=\sum_{i=1}^{n}P(B_{i})P(A|B_{i})$ ##1.2 特征条件独立假设 这一部分开始朴素贝叶斯的理论推导，从中你会深刻地理解什么是特征条件独立假设。 给定训练数据集（X,Y），其中每个样本x都包括n维特征，即$x=({x_{1},x_{2},x_{3},...,x_{n}})$，类标记集合含有k种类别，即$y=({y_{1},y_{2},...,y_{k}})$。 如果现在来了一个新样本x，我们要怎么判断它的类别？从概率的角度来看，这个问题就是给定x，它属于哪个类别的概率最大。那么问题就转化为求解$P(y_{1}|x),P(y_{2}|x),...,P(y_{k}|x)$中最大的那个，即求后验概率最大的输出：$argmax_{y_{k}} P(y_{k}|x)$ 那$P(y_{k}|x)$怎么求解？答案就是贝叶斯定理： $P(y_{k}|x)=\frac{P(x|y_{k})P(y_{k})}{P(x)}$ 根据全概率公式，可以进一步地分解上式中的分母： $P(y_{k}|x)=\frac{P(x|y_{k})P(y_{k})}{\sum_{k}P(x|y_{k})P(y_{k})}$ **【公式1】** >这里休息两分钟 先不管分母，分子中的$P(y_{k})$是先验概率，根据训练集就可以简单地计算出来。 而条件概率$P(x|y_{k})=P(x_{1},x_{2},...,x_{n}|y_{k})$，它的参数规模是指数数量级别的，假设第i维特征$x_{i}$可取值的个数有$S_{i}$个，类别取值个数为k个，那么参数个数为：$k\prod_{i=1}^{n}S_{i}$ 这显然不可行。**针对这个问题，朴素贝叶斯算法对条件概率分布作出了独立性的假设**，通俗地讲就是说假设各个维度的特征$x_{1},x_{2},...,x_{n}$互相独立，在这个假设的前提上，条件概率可以转化为： $P(x|y_{k})=P(x_{1},x_{2},...,x_{n}|y_{k})=\prod_{i=1}^{n}P(x_{i}|y_{k}) $ **【公式2】** 这样，参数规模就降到$\sum_{i=1}^{n}S_{i}k$ 以上就是针对条件概率所作出的特征条件独立性假设，至此，先验概率$P(y_{k})$和条件概率$P(x|y_{k})$的求解问题就都解决了，那么我们是不是可以求解我们所要的后验概率$P(y_{k}|x)$了？ >这里思考两分钟 答案是肯定的。我们继续上面关于$P(y_{k}|x)$的推导，将【公式2】代入【公式1】得到： $P(y_{k}|x)=\frac{P(y_{k})\prod_{i=1}^{n}P(x_{i}|y_{k})}{\sum_{k}P(y_{k})\prod_{i=1}^{n}P(x_{i}|y_{k})}$ 于是朴素贝叶斯分类器可表示为： $f(x)=argmax_{y_{k}} P(y_{k}|x)=argmax_{y_{k}} \frac{P(y_{k})\prod_{i=1}^{n}P(x_{i}|y_{k})}{\sum_{k}P(y_{k})\prod_{i=1}^{n}P(x_{i}|y_{k})}$ 因为对所有的$y_{k}$，上式中的分母的值都是一样的（为什么？注意到全加符号就容易理解了），所以可以忽略分母部分，朴素贝叶斯分类器最终表示为： $f(x)=argmax P(y_{k})\prod_{i=1}^{n}P(x_{i}|y_{k})$ 关于$P(y_{k})$，$P(x_{i}|y_{k})$的求解，有以下三种常见的模型. #2. 三种常见的模型及编程实现 ##2.1 多项式模型 当特征是离散的时候，使用多项式模型。多项式模型在计算先验概率$P(y_{k})$和条件概率$P(x_{i}|y_{k})$时，会做一些**平滑处理**，具体公式为： $P(y_{k})=\frac{N_{y_{k}}+\alpha}{N+k\alpha}$ >N是总的样本个数，k是总的类别个数，$N_{y_{k}}$是类别为$y_{k}$的样本个数，$\alpha$是平滑值。 $P(x_{i}|y_{k})=\frac{N_{y_{k},x_{i}}+\alpha}{N_{y_{k}}+n\alpha}$ >$N_{y_{k}}$是类别为$y_{k}$的样本个数，n是特征的维数，$N_{y_{k},x_{i}}$是类别为$y_{k}$的样本中，第i维特征的值是$x_{i}$的样本个数，$\alpha$是平滑值。 当$\alpha=1$时，称作Laplace平滑，当$0<\alpha<1$时，称作Lidstone平滑，$\alpha=0$时不做平滑。 如果不做平滑，当某一维特征的值$x_{i}$没在训练样本中出现过时，会导致$P(x_{i}|y_{k})=0$，从而导致后验概率为0。加上平滑就可以克服这个问题。 ### 2.1.1 举例 有如下训练数据，15个样本，2维特征$X^{1},X^{2}$，2种类别-1，1。给定测试样本$x=(2,S)^{T}$，判断其类别。  解答如下： 运用多项式模型，令$\alpha=1$ - 计算先验概率  - 计算各种条件概率  - 对于给定的$x=(2,S)^{T}$，计算：  由此可以判定y=-1。 ###2.1.2 编程实现（基于Python，Numpy） 从上面的实例可以看到，当给定训练集时，我们无非就是先计算出所有的先验概率和条件概率，然后把它们存起来（当成一个查找表）。当来一个测试样本时，我们就计算它所有可能的后验概率，最大的那个对应的就是测试样本的类别，而后验概率的计算无非就是在查找表里查找需要的值。 我的代码就是根据这个思想来写的。定义一个MultinomialNB类，它有两个主要的方法：fit(X,y)和predict(X)。fit方法其实就是训练，调用fit方法时，做的工作就是构建查找表。predict方法就是预测，调用predict方法时，做的工作就是求解所有后验概率并找出最大的那个。此外，类的构造函数\__init__()中，允许设定$\alpha$的值，以及设定先验概率的值。具体代码及如下： ``` """ Created on 2015/09/06 @author: wepon (http://2hwp.com) API Reference: http://scikit-learn.org/stable/modules/naive_bayes.html#naive-bayes """ import numpy as np class MultinomialNB(object): """ Naive Bayes classifier for multinomial models The multinomial Naive Bayes classifier is suitable for classification with discrete features Parameters ---------- alpha : float, optional (default=1.0) Setting alpha = 0 for no smoothing Setting 0 < alpha < 1 is called Lidstone smoothing Setting alpha = 1 is called Laplace smoothing fit_prior : boolean Whether to learn class prior probabilities or not. If false, a uniform prior will be used. class_prior : array-like, size (n_classes,) Prior probabilities of the classes. If specified the priors are not adjusted according to the data. Attributes ---------- fit(X,y): X and y are array-like, represent features and labels. call fit() method to train Naive Bayes classifier. predict(X): """ def __init__(self,alpha=1.0,fit_prior=True,class_prior=None): self.alpha = alpha self.fit_prior = fit_prior self.class_prior = cla