SVM 与决策树

# SVM

SVM 是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使其有别于感知机，SVM 还包括核技巧，使它成为实质上的非线性分类器。

SVM 的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的最优化问题。其基本思想是求解能够正确划分训练数据集且几何间隔最大的分离超平面。

（间隔对偶核技巧） 带约束的原问题 -> 不带约束的原问题（引入拉格朗日） -> 对偶问题（凸二次规划问题，约束是线性的、目标函数是二次的->强对偶问题）-> 无约束优化求导为零解最优解

原、对偶问题是强对偶关系 <=> 满足 KKT 条件，KKT 条件为

$\left\{ \begin{aligned} \frac{\partial \mathcal{L}}{\partial \mathbb{w}} = 0, \frac{\partial \mathcal{L}}{\partial b} = 0, \frac{\partial \mathcal{L}}{\partial \lambda} = 0\\ {\lambda}_{i}(1-y_{i}(\mathbb{w}^Tx_i + b)) = 0\\ {\lambda}_{i} \ge 0\\ 1-y_{i}(\mathbb{w}^Tx_i + b) \le 0 \end{aligned} \right.$

于是根据 KKT 条件求出参数即可。

手推 SVM 三步走：

• 几何解释 -> 数学解释
• 带约束优化 -> 无约束优化
• 对偶问题 -> KKT 条件

下面根据这三个步骤给出一个手推 SVM 的过程。

从几何解释到数学解释

第二步和第三步合并在一起

通常情况下，数据中会存在一些 Outlier，这些点可能使得数据变得不可分，同时会破坏函数间隔大于等于 1 的条件，软间隔的引入就是为了解决这个问题。

# 决策树

信息增益存在偏向于选择取值较多的特征的问题，可用信息增益比来修正。分别对应 ID3 算法和 C4.5 算法。

决策树的生成学习仅考虑对训练数据的拟合程度，不考虑模型的复杂成都，容易过拟合，而剪枝学习同时考虑两者。

CART 树是二叉树，由特征选择、树的生成、树的剪枝组成，可用于回归和分类。基尼系数作为特征选择指标。基尼系数越小，分类结果越好。CART 剪枝形成一个序列，相当于超参数的选择过程。

基尼系数和熵之半的曲线很接近，都可以近似的代表分类误差率。

对于连续值的处理：用区间划分对其进行离散化，选择信息熵最小的划分，因为希望划分之后的数据更纯净。