第四章:支持向量机
在超平面的表达式$f(x) = w^Tx + b = 0$中：
-
$x$: 是数据点在特征空间中的向量表示。例如，如果每个数据点有两个特征（如长和宽），那么$x$就是一个二元素向量，包含了数据点的长和宽。
-
$w$: 是权重向量，和$x$有相同的维数。权重向量决定了最优超平面的方向。几何意义上，可以理解为超平面的法线向量。
-
$b$: 是偏置项，影响最优超平面的位置（即与原点的距离）。
在二维空间中，超平面就是一条直线，而在三维空间中，超平面就是一个平面，以此类推。
权重向量$w$的方向正交于超平面。也就是说，任意在超平面上的两点$x_1$和$x_2$，都满足方向向量$(x_2-x_1)$与$w$的点积为零，即$|(x_2-x_1)w|=0$。
权重向量$w$的模长（即欧几里得长度）与超平面的间隔成反比。模长越小，间隔越大。因此优化$w$的目标就是让其模长尽量小，从而使间隔尽量大。
间隔
函数间隔和几何间隔都是在超平面（决策边界）划分数据集时定义出的两个重要概念：
-
函数间隔（Functional Margin）: 对于给定的训练数据集$\mathrm{T}$和超平面$(w, b)$，定义超平面$(w, b)$关于样本点$(x_i, y_i)$的函数间隔为$y_i(w^T x_i + b)$。规定如果样本点被正确分类，那么函数间隔需为正。这对应了数据点到超平面的“原始距离”。
-
几何间隔（Geometrical Margin）: 对于给定的训练数据集$\mathrm{T}$和超平面$(w, b)$，定义超平面$(w, b)$关于样本点$(x_i, y_i)$的几何间隔为$y_i(w^T x_i + b)/||w||$。也就是在函数间隔的基础上，采用单位化权重向量来消除权重向量长度的影响，从而得到的数据点到超平面的真实距离。
在最优化问题中，SVM主要的目标是寻求得到最大的几何间隔，从而最小化模型的泛化误差，提高模型的分类性能。
而偏置项$b$决定了超平面距离原点的远近。比如在二维空间中，假设超平面是一条直线，那么$b$就是直线在y轴上的截距。增大$b$的绝对值会使直线沿着与$w$方向正交的方向移动，但并不会改变直线的方向。
如何优化w?
什么是支持向量
在支持向量机(SVM)的标准形式中，所有的数据点都会形成一些约束条件，但在实践中，大部分的数据点对最终的最优解影响不大。那些真正影响到SVM的最优解（即最优超平面）的数据点是那些离分割超平面最近的点，也就是被称为"支持向量"的数据点。换言之，最优解依赖于那些位于或者在最优超平面附近的点，它们被称为"支持向量"。这是因为这些点满足 $y_i(w^T x_i+b) -1 = 0$ 或者 $y_i (w^T x_i+b) +1 = 0$ ，是损失函数（即上述的拉格朗日函数）的活跃约束，同时也是我们判定间隔边界的点。所以，SVM只关心那些离超平面近的点，即支持向量，而对其他的点则不敏感。
拉格朗日方法
选取最优化平面问题作为例子，我们知道，这是支持向量机(SVM)的基本思想。要找到一个最优的超平面，使得所有样本到该平面的间隔最大。用拉格朗日乘数法的语言来描述，就是我们希望求解以下原始问题：
最小化目标函数
$$\frac{1}{2} ||w||^2$$
约束条件
$$y_i (w^T x_i + b) - 1 \geq 0, \text{ } \forall i$$
其中，$w$维度的向量，是我们要找的超平面的法向量；$x_i$是样本的特征向量；$y_i$是样本的类别标签，取值为-1或+1；and $b$是超平面的截距。
由上述原问题，我们可以构建出以下拉格朗日函数：“
$$L(w, b, \alpha) = \frac{1}{2} ||w||^2 - \sum_{i=1}^{m} \alpha {i} [y{i}(w^T x_i + b) - 1]$$
其中，$\alpha _{i}$就是拉格朗日乘数，M为样本数。
通过对w和b求导，令其等于零，得到w和b的表达式，将这个表达式带入到拉格朗日函数中，我们可以得到对偶问题。
对偶问题的优化目标就变为，求以下函数最大值：
$$\max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m y_i y_j \alpha_i \alpha_j <x_i,x_j>$$
约束条件为：
$$\sum_{i=1}^m \alpha_i y_i = 0 \quad \text{ and } \quad \alpha_i \geq 0 , i=1,2,3,…,m$$
之所以要构建对偶问题，是因为它一般情况下要比原问题更容易求解，并且能自然地引入核函数，处理逻辑非线性可分的情况。在求解了对偶问题之后，我们能通过拉格朗日乘数法得到w、b参数，然后得到分类平面。
考虑到软分类优化
非线性支持向量机
使用一个变换，将原空间数据映射到新空间
决策树
下面是ID3算法的基本步骤：
-
计算信息增益：对于数据集中的每个特征，计算使用该特征来划分数据集的信息增益。
-
选择最佳特征：选择具有最高信息增益的特征。
-
分裂数据集：使用选定的特征，根据该特征的所有可能值来分裂数据集。
-
递归构建子树：对于分裂后的每个子数据集，重复步骤1-3，直到满足停止条件（如，数据集中的所有实例都属于同一类别，或达到预定的树的深度）。
-
生成决策树：一旦达到停止条件，每个子数据集都将被分配一个类标签，这个类标签通常是该子数据集中最常见的类。
C4.5
-
信息增益比:相比于ID3,增加了增益比,在选择最佳特征时在考虑n个最高信息增益的特征时额外考虑信息增益比(倾向于使分类不平均)
-
后剪枝:生成决策树后为防止过拟合,进行后剪枝:将所有的子孙叶节点合并到自己,自己成为新的叶节点