朴素贝叶斯

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单.

理论上，NBC模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

$$p\left(c_{i} \mid w\right)=\frac{p\left(w \mid c_{i}\right) p\left(c_{i}\right)}{p(w)}$$

SVM

支持向量机(supportvector machine ,SVM)是一种二类分类模型.它的基本模型是定义在特征空间上的能够正确划分训练数据集并且几何间隔最大的线性分类器。支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题，支持向量机的学习算法是求解凸二次规划的最优化算法。

 核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积，满足正定条件。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机，这样的方法称为核技巧，核方法是比支持向量机更为一般的机器学习方法。

一般选择线性核和高斯核，也就是Linear核与RBF核。

Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了.
RBF核：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。

如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM。 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel。

LR和SVM有什么区别

相同点：

  • 监督学习，分类，线性，判别模型，应用广泛

不同点：   

  • 损失函数：SVM hingeloss; LR对数损失说明分类的不同假设前提，SVM基于几何间隔最大化，LR基于概率理论

  • SVM只考虑局部的边界线附近的点（支持向量），LR考虑全局，即线性SVM不直接依赖于数据分布，分类平面不受一类点影响；LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要先对数据做balancing

  • SVM支持核函数，可处理线性非线性问题;   LR模型简单，训练速度快，适合处理线性问题 ，原因是SVM只用个别点参与核运算，而LR需要全部点进行核运算，计算复杂度太高，很少运用。

  • SVM依赖数据表达距离，需要normalization，LR不需要

  • SVM的损失函数自带正则，故SVM为结构风险最小化算法，而LR必须在损失函数外加正则项

  • LR输出具有概率意义，而SVM没有，直接为1或-1

决策树

决策树算法，无论是哪种，其目的都是为了让模型的不确定性降低的越快越好，基于其评价指标的不同，主要是ID3算法，C4.5算法和CART算法，其中ID3算法的评价指标是信息增益，C4.5算法的评价指标是信息增益率，CART算法的评价指标是基尼系数。

信息增益和信息增益率

对同一个随机变量，当他的概率分布为均匀分布时，不确定性最大，熵也最大。对有相同概率分布的不同的随机变量，取值越多的随机变量熵越大。其次，要理解条件熵的概念。正如熵是对随机变量不确定性的度量一样，条件熵是指，有相关的两个随机变量X和Y，在已知随机变量X的条件下，随机变量Y的不确定性。当熵和条件熵中概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别为经验熵与经验条件熵。
所谓信息增益，也叫互信息，就是指集合D的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D∣A)$ 之差。ID3算法在每一次对决策树进行分叉选取最优特征时，会选取信息增益最高的特征来作为分裂特征。

信息增益准则的问题？

ID3算法存在的问题: 信息增益准则对那些特征的取值比较多的特征有所偏好，也就是说，采用信息增益作为判定方法，会倾向于去选择特征取值比较多的特征作为最优特征。那么，选择取值多的特征为甚就不好呢？参考这篇博文。 采用信息增益率的算法C4.5为什么可以解决ID3算法中存在的问题呢？ 信息增益率的公式如下：

$$g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}$$ 其中 $$H_A(D)=-\sum_{i=1}^n \frac{\left|D_i\right|}{|D|} \log _2 \frac{\left|D_i\right|}{|D|}$$

$n$ 是特征 $A$ 取值的个数。$H_{A}(D)$ 表示的就是特征 $A$ 的纯度，如果 $A$ 只含有少量的取值的话，那么 $A$ 的纯度就比较高，$H_{A}(D)$就比较小；相反，如果 $A$ 取值越多的话，那么 $A$ 的纯度就越低，$H_{A}(D)$ 就比较大。这样就可以解决ID3算法中存在的问题了。

决策树出现过拟合的原因及其解决办法

  • 原因

    • 在决策树构建的过程中，对决策树的生长没有进行合理的限制- （剪枝）；
    • 样本中有一些噪声数据，没有对噪声数据进行有效的剔除；
    • 在构建决策树过程中使用了较多的输出变量，变量较多也容易产生过拟合（该原因待解释）。

  • 解决办法

    • 选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，我们一般采用后剪枝的方法；
    • 利用 K−folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用 K−1 份作为训练样本数据集，另外一份作为测试集；
    • 减少特征，计算每一个特征和响应变量的相关性，常见得为皮尔逊相关系数，将相关性较小的变量剔除（待解释！！！）；当然还有一些其他的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等（决策的正则化，例如，L1和L2正则，具体是对谁的正则呢？怎样正则的呢？）。面试官顺便会问L1和L2，一定要搞明白