机器学习相关算法总结

集成学习

集成学习通过训练多个分类器，然后将其组合起来，从而达到更好的预测性能，提高分类器的泛化能力。

Baggging 和Boosting都是模型融合的方法，可以将弱分类器融合之后形成一个强分类器，而且融合之后的效果会比最好的弱分类器更好。

目前集成学习主要有三个主要框架：bagging，boosting，stacking。

偏差：训练到的模型与真实标签之间的区别。

方差：每次学习的模型之间差别有多大。

偏差指的是算法的期望预测与真实值之间的偏差程度，反映了模型本身的拟合能力；

方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。

bagging套袋法

bagging是并行集成学习方法的最著名代表，其算法过程如下：

• 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）

• 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

• 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

  

boosting提升法

大多数的提升方法都是改变训练数据的概率分布（训练数据中的各个数据点的权值分布），调用弱学习算法得到一个弱分类器，再改变训练数据的概率分布，再调用弱学习算法得到一个弱分类器，如此反复，得到一系列弱分类器。两个问题？

1. 是在每一轮如何改变训练数据的概率分布。
2. 是如何将多个弱分类器组合成一个强分类器。

关于第一个问题，AdaBoosting方式每次使用的是全部的样本，每轮训练改变样本的权重。下一轮训练的目标是找到一个函数f 来拟合上一轮的残差。当残差足够小或者达到设置的最大迭代次数则停止。

至于第二个问题，采取加权多数表决的方法。Boosting会减小在上一轮训练正确的样本的权重，增大错误样本的权重。（对的残差小，错的残差大）梯度提升的Boosting方式是使用代价函数对上一轮训练出的模型函数f的偏导来拟合残差。

bagging和boosting区别

Bagging是减少方差variance，而Boosting是减少偏差bias

（1）样本选择上：

• Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

• Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

（2）样例权重：

• Bagging：使用均匀取样，每个样例的权重相等。

• Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

（3）预测函数：

• Bagging：所有预测函数的权重相等。

• Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

（4）并行计算：

• Bagging：各个预测函数可以并行生成。

• Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

stacking模型融合

stacking 就是当用初始训练数据学习出若干个基学习器后，将这几个学习器的预测结果作为新的训练集，来学习一个新的学习器。

Bagging是减少方差variance和偏差bias。Stacking既减少方差又减少偏差。

Bagging是尽可能的提高模型的随机性，使得模型之间没有强相关性，以此降低融合的方差。

Boosting是不断递进的优化每个分类器，逐步减少偏差，各分类器直接具有强相关性，因此不会降低方差。

决策树

什么是决策树呢？决策树是一种监督学习方法，既可以用来处理分类问题也可以处理回归问题。

决策树是一个有监督分类模型，本质是选择一个最大信息增益的特征值进行输的分割，直到达到结束条件或叶子节点纯度达到阈值。

ID3算法（信息增益）

• 思想：ID3使用信息增益作为特征选择的度量，使用自顶向下的贪心算法遍历决策树空间。

  • （1）计算数据集合的信息熵，以及各个特征的条件熵，最后计算信息增益，选择信息增益最大的作为本次划分的节点
  • （2）删除上一步使用的特征。更新各个分支的数据集和特征集。
  • （3）重复（1）（2）步，直到子集包含单一特征，则为分支叶节点。

• 信息熵：是度量样本集合纯度最常用的一种指标，假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k = 1, 2, …, c)$ ，则 $D$ 的信息熵定义为：

  $$Ent(D)= -\sum_{k=1}^{c}p_klog_2 p_k$$

  $Ent(D)$ 的值越小，则 $D$ 的纯度越高。注意因为 $p_k \le 1$ ，因此 $Ent(D)$ 也是一个大于等于０小于１的值。$p_i = \frac{|C_k|}{|D|}$, 其中Ck表示集合 D 中属于第 k 类样本的样本子集。

  信息熵：

  $$H(D)= -\sum_{k=1}^{c}\frac{|C_k|}{|D|}log_2 \frac{|C_k|}{|D|}$$

  针对某个特征A，对于数据集D的条件熵：也就是考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $\frac{|D^i|}{|D|}$

  $$H(D|A) =\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i) = -\sum_{i=1}^{n}\frac{|D_i|}{|D|}(\sum_{k=1}^{c}\frac{|C_{ik}|}{|D_i|}log_2 \frac{|C_{ik}|}{|D_i|})$$

  信息增益== 信息熵-条件熵：

  $$Gain(D,a) = H(D) - H(D|A)$$

  信息增益越大越好，因为其代表着选择该属性进行划分所带来的纯度提升，因此全部计算当前样本集合 $D$ 中存在不同取值的那些属性的信息增益后，取信息增益最大的那个所对应的属性作为划分属性即可。

• 优缺点

  • ID3算法没有进行决策树剪枝，容易发生过拟合
  • ID3算法没有给出处理连续数据的方法，只能处理离散特征
  • ID3算法不能处理带有缺失值的数据集,需对数据集中的缺失值进行预处理
  • 信息增益准则对可取值数目较多的特征有所偏好 (信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)

C4.5算法（信息增益率）

C4.5主要是克服ID3使用信息增益进行特征划分对取值数据较多特征有偏好的缺点。使用信息增益率进行特征划分。

• 对ID3算法的改进：

  • 引入剪枝策略，使用悲观剪枝策略进行后剪枝。

  • 使用信息增益率代替信息增益，作为特征划分标准

  • 连续特征离散化

  • • 需要处理的样本或样本子集按照连续变量的大小从小到大进行排序
    • 假设该属性对应的不同的属性值一共有N个,那么总共有N−1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成两类

  • 缺失值处理

  • • 对于具有缺失值的特征，用没有缺失的样本子集所占比重来折算信息增益率，选择划分特征
    • 选定该划分特征，对于缺失该特征值的样本，将样本以不同的概率划分到不同子节点

• 信息增益率，信息增益率表示如下：

  $$Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$$ $$IV(a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}$$

  $IV(a) $称为属性 a 的“固有值”。属性 a 的可能取值数目越多，则 $IV(a)$ 的值通常会越大，信息增益率对可取值较少的特征有所偏好（分母越小，整体越大）因此一定程度上抵消了信息增益对可取值数目多的属性的偏好。但是C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

• 决策树剪枝：

  • 决策树剪枝是为了防止过拟合
  • C4.5采用的是后剪枝策略进行剪枝：在决策树构造完成后，自底向上对非叶节点进行评估，如果将其换成叶节点能提升泛化性能，则将该子树换成叶节点。后剪枝决策树欠拟合风险很小，泛化性能往往优于预剪枝决策树。但训练时间会大很多。

• C4.5的优缺点

  • C4.5只能用于分类
  • C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。
  • 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，算法低效。
  • 对于连续值属性来说，可取值数目不再有限，因此可以采用离散化技术（如二分法）进行处理。将属性值从小到大排序，然后选择中间值作为分割点，数值比它小的点被划分到左子树，数值不小于它的点被分到右子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。

CART算法（基尼系数）

相比ID3和C4.5算法，CART算法使用二叉树简化决策树规模，提高生成决策树效率。

• CART树在C4.5基础上改进

  • CART使用二叉树来代替C4.5的多叉树，提高了生成决策树效率
  • C4.5只能用于分类，CART树可用于分类和回归
  • CART 使用基尼（Gini）系数作为变量的不纯度量，减少了大量的对数运算
  • CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中
  • CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法
  • ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征

• CART是一棵二叉树，采用二元切分法，每次把数据分成两份，分别进入左子树、右子树。并且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子节点多一。相比于ID3和C4.5，CART的应用要多一些，既可以用于分类也可以用于回归。CART分类时，选择基尼指数（Gini）为最好的分类特征，gini描述的是纯度，与信息熵含义类似，CART中每次迭代都会降低基尼系数。基尼值：

  $$Gini(D) = \sum_{k=1}^{c} \sum_{k^, \not =k}p_kp_{k^,} = 1- \sum_{k=1}^{c}p_k^2 = 1-\sum_{k=1}^{c}(\frac{D^k}{D})^2$$

  直观来看，$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此$Gini(D)$ 越小，则数据集 $D$ 的纯度越高。

  对于样本D，个数为|D|，根据特征A的某个值a，把D分成|D1|和|D2|，则在特征A的条件下，样本D的基尼系数表达式为：

  $$Gini\_index(D,A) = \frac{|D^1|}{|D|}Gini(D^1)+ \frac{|D^2|}{|D|}Gini(D^2)$$

  于是，我们在候选属性集合A中，选择那个使得划分后基尼系数最小的属性作为最优划分属性即可。

• 缺失值处理

  CART 算法使用一种惩罚机制来抑制提升值，从而反映缺失值的影响。为树的每个节点都找到代理分裂器，当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。

• 决策分类树

  CART作为分类树时，特征属性可以是连续类型也可以是离散类型，但观察属性(即标签属性或者分类属性)必须是离散类型。

  先说分类树，ID3、C4.5在每一次分支时，是穷举每一个特征属性的每一个阈值，找到使得按照特征值<=阈值，和特征值>阈值分成的两个分支的熵最大的特征和阈值。按照该标准分支得到两个新节点，用同样的方法进行分支，直到所有人被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中性别不唯一，则以多数人的性别作为该叶子节点的性别。

• 决策回归树

  回归树总体流程也是类似，不过在每个节点(不一定是叶子节点)都会得到预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分支时穷举每个特征的每个阈值，找最好的分割点，但衡量的标准变成了最小化均方误差，即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方误差越大，通过最小化均方误差找最靠谱的分支依据。分支直到每个叶子节点上的人的年龄都唯一(这太难了)，或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄作为该叶子节点的预测年龄。

  对于决策树建立后做预测的方式，CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

• 剪枝策略：采用一种“基于代价复杂度的剪枝”方法进行后剪枝

对比总结

• Bagging+决策树=随机森林
• Boosting+决策树=GBDT

随机森林（Bagging）

随机森林本质上就是构建很多弱决策树，然后整合成森林，来确定最终的预估结果。Bagging+决策树=随机森林

随机森林的主要特点可以总结为如下2点：数据随机性选取，待选特征的随机选取。主要是为了消除过拟合问题。随机森林使用CART树作为弱学习器，生成树的过程中不进行剪枝，确定最终结果时，分类使用投票机制，回归问题使用平方误差最小化。

随机森林根据下面步骤来构建：

1. M来表示训练样本的个数，N表示特征数目
2. 输入特征数目n，用于确定决策树一个节点的决策结果；其中n应远小于N
3. M个训练样本中，有放回抽样的方式，取样k次，形成训练集，并用未抽到样本做预测，评估误差
4. 随机选择n个特征，每棵决策树上每个节点的决策基于这些特征确定。根据这n个特征，计算其最佳的分裂方式
5. 最后根据每棵树，以多胜少方式决定分类

优点：

• 很容易查看模型的输入特征的相对重要性
• 可以处理高维数据
• 超参数的数量不多，而且它们所代表的含义直观易懂
• 随机森林有足够多的树，分类器就不会产生过度拟合模型

缺点：

• 使用大量的树会使算法变得很慢，无法做到实时预测
• 对于回归问题，精准度不够
• 抗噪声干扰能力弱，无法自动处理异常样本
• 模型越深越容易过拟合

Boosting算法代表

AdaBoost算法

• 特点
  • 不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起到不同的作用
  • 利用基本分类器的线性组合构建最终的分类器

假定给定一个二分类分类的训练数据：

$$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$

其中每个样本点由实例与标记组成。实例 $x_i \in \chi \subseteq R^n$ ，标记 $y_i \in \Upsilon = \{-1,1\}$ ，$\chi$ 是实例空间，$\Upsilon$ 是标记集合。Adaboost 利用以下算法，从训练数据中学习一系列弱分类器，并将这些弱分类器线性组合成为一个强分类器。

（1）初始化训练数据的权值分布：

$$D_1 = (w_{11},...,w_{1i},...,w_{1N}),\quad w_{1i}=\frac{1}{N},\quad i=1,2,...,N$$

假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同。这一假设保证第１步能够在原始数据上学习基本分类器 $G_1(x)$ 。

（2）一共需要学习 M 个基本分类器，则在每一轮 $m = 1,2,…,M$ 顺次地执行下列操作：

• a.使用当前分布 $D_m$ 加权的训练数据集，得到基本分类器：

$$G_m(x):\chi\rightarrow \{-1,+1\}$$

• b.计算 $G_m(x)$ 在训练数据集上的分类误差率：

$$e_m = \sum_{i=1}^{N}P(G_m(x_i)\not = y_i) = \sum_{G_{mi}\not = y_i}w_{mi}$$

$w_{mi}$ 表示第 m 轮中第 i 个实例的权值，$\sum_{i=1}^{N}w_{mi} = 1$ 。这表明， $G_{m}(x)$ 在加权的训练数据集上的分类误差率是被 $G_{m}(x)$ 误分类的样本的权值之和。

• c.计算 $G_{m}(x)$ 的系数：

  $$\alpha_m = \frac{1}{2}ln \frac{1-e_m}{e_m}$$

  $\alpha_m$ 表示 $G_{m}(x)$ 在最终分类器中的重要性。根据式子可知，$e_m \le \frac{1}{2}$ 时，$\alpha_m \ge 0$ ，并且 $\alpha_m$ 随着 $e_m$ 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。这里注意所有 $\alpha_m$ 加起来的和并不等于 1 。 （注意 $e_m$ 是有可能比 $\frac{1}{2}$ 大的，也就是说 $\alpha_m$ 有可能小于 0，《统计学习方法》没有讨论这种情况的处理方法，但在西瓜书中的处理方法是抛弃该分类器，且终止学习过程，哪怕学习到的分类器个数远远没有达到预设的 M）

• e.更新训练数据集的权值分布：

$$D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})$$ $$w_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), \quad i=1,2,...,N$$ $$其中 Z_m是规范因子，Z_m = \sum_{i=1}^{N}w_{mi}exp(-\alpha_my_iG_m(x_i))$$

​ $w_{m+1,i}$ 也可以写成分段函数的形式：

$$w_{m+1,i}= \begin {cases} \frac{w_{mi}}{Z_m}e^{-\alpha_m}, & G_m(x_i) = y_i \\ \frac{w_{mi}}{Z_m}e^{\alpha_m}, & G_m(x_i) \not = y_i \end {cases}$$

​ 也就是说被基本分类器 $G_m(x)$ 误分类样本的权值得以增大，而被正确分类的样本的权值却变小。两者相比可知误分类样本的权值被 放 大 $e^{2\alpha_m} = \frac{1-e_m}{e_m}$ 倍。因此，误分类样本在下一轮学习中起更大的作用。

（3）经过以上过程后可以得到 M 个基本分类器，构建基本分类器的线性组合：

$$f(x) = \sum_{m=1}^{M}\alpha_m G_m(x)$$

​ 通过线性组合得到最终的分类器：

$$G(x) = sign(f(x)) = sign(\sum_{m=1}^{M}\alpha_m G_m(x))$$

​ 线性组合 $f(x)$ 实现 M 个基本分类器的加权表决，$f(x)$ 的符号决定了实例 $x$ 的类，$f(x)$ 的绝对值表示分类的确信度。

GBDT算法

GBDT（Gradient Boosting Decision Tree）梯度迭代树，是Boosting算法的一种。

GBDT使用的弱学习器必须是CART，且必须是回归树。GBDT用来做回归预测，当然，通过设置阈值也能用于分类任务。在模型训练时，模型预测样本损失尽可能小。

GBDT直观理解：模型的每一轮预测和真实值有gap，这个gap称为残差。下一轮对残差进行预测，最后将所有预测结果相加，就可以得到最终结果。也就是说，模型的结果是一组回归分类树组合：T1，T2，…，Tk，其中Tj学习的是之前j-1课树预测结果的残差。这种思想就像准备考试前的复习，先做一遍习题册，然后把做错的题目挑出来，再做一次，然后把做错的题目挑出来在做一次，经过反复多轮训练，取得最好的成绩。

GBDT学习的是残差，而本质是在学习负梯度信息，由于一般回归使用平方损失（L2 loss），他的导数就是残差，所以GBDT学的是残差。

GBDT和AdaBoost的模型的表示形式都可以：

$$f(x) = \sum_{m=1}^M \alpha_m G_m(x)$$

只是 AdaBoost 在训练完一个 $G_m(x)$ 后会重新赋值样本的权重：分类错误的样本的权重会增大而分类正确的样本的权重则会减小。这样在训练时 $G_{m+1}(x)$ 会侧重对错误样本的训练，以达到模型性能的提升，

但是AdaBoost模型每个基分类器的损失函数优化目标是相同的且独立的，都是最优化当前样本（样本权重）的指数损失。

GBDT是一个加性模型，但其是通过不断迭代拟合样本真实值与当前分类器预测的残差来逼近真实值的。可以形象地理解如下：

按照这个思路，第 m 个基分类器的预测结果为：

$$f_m(x) = f_{m-1}(x)+\alpha_mG_m(x)$$

而 $G_m(x)$ 的优化目标就是最小化当前预测结果 $f_{m-1}(x_i)+\alpha G(x_i)$ 与真实值 $y_i$ 之间的差距。

$$(\alpha_m,G_m(x)) = arg min_{\alpha,G}\sum_{i=1}^{N}L(y_i,\quad f_{m-1}(x_i)+\alpha G(x_i))$$

GBDT树的学习过程为：计算伪残差-> 生成基学习器 -> 目标函数优化 -> 更新模型

其思想类似于数值优化中梯度下降求参方法，参数沿着梯度的负方向以小步长前进，最终逐步逼近参数的局部最优解。在GB中模型每次拟合残差，逐步逼近最终结果。

如上所述，我们每个 stage 的优化目标是：（一阶泰勒）

$$G_m(x) = arg min_{G}\sum_{i=1}^{N}L(y_i,\quad f_{m-1}(x_i)+\alpha_m G_{m}(x_i))$$ $$这一块太乱，回来再重新总结一遍。经过一阶泰勒展开得到：$$ $$arg min_{G}\sum_{i=1}^{N}L(y_i,\alpha_m G_{m-1}(x_i))+f_{m-1}(x_i)+\frac{\partial L(y_i,f_m(x_i))}{\partial f_m(x_i)}\\$$

该函数比较难求解，类似于梯度下降方法，给定 $f_{m-1}(x_i)$ 的一个近似解，$\alpha_mG_m(x)$ 可以看作是 $f_{m-1}(x_i)$ 逼近 $f_m(x_i)$ 的步长和方向。所以：

$$f_m(x)= f_{m-1}(x)-\alpha_m [\frac{\partial L(y_i,f_m(x_i))}{\partial f_m(x_i)}]_{f_m(x_i)=f_{m-1}(x_i)}$$ $$\alpha_m = arg min_{\alpha}\sum_{i=1}^{N}L(y_i,f_{m-1}(x)-\alpha_m [\frac{\partial L(y_i,f_m(x_i))}{\partial f_m(x_i)}]_{f_m(x_i)=f_{m-1}(x_i)} )$$

上面的损失函数 L 可以根据问题的不同使用不同的损失函数，而且还可以加上模型复杂度的正则项等等来尽量避免过拟合。

GBDT缺点：基于残差的gbdt在解决回归问题上不算好的选择，对异常值过于敏感；不适合高纬稀疏特征；不好并行计算。

XGBoost算法

XGBoost和GBDT都是属于Grandient Boosting，本质思想与GBDT一致，构建多个基学习器使用加法模型，学习前面基学习器的结果与真实值的偏差，通过多个学习器的学习，不断降低模型值和实际值的差。XGBoost 可以认为是 GBDT 的一个实现，但是XGBoost相比GBDT做了如下的改进：

• GBDT将目标函数泰勒展开到一阶，而xgboost将目标函数泰勒展开到二阶，XGBoost保留更多有关目标函数的信息。
• GBDT是给新的基模型寻找新的拟合标签（前面加法模型的负梯度），而XGBoost是给新的基模型寻找新的目标函数（目标函数关于新的基模型的二阶泰勒展开）。
• XGBoost加入了和叶子权重的L2正则化，有利于模型获得更低的方差。
• XGBoost增加了自动处理缺失值特征的策略，通过把带缺失值的样本划分到左子树或右子树，比较两种方案下目标函数的优劣，从而自动对有缺失值的样本进行划分，无需对缺失值特征进行填充预处理。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。
• 支持并发，xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。节点分裂时，计算特征增益是多线程并行的。
• 基分类器：传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。
• 子采样：传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样。

最终分类器可以用这个公式表示：

$$f(x) = \sum_{m=1}^M G_m(x)$$

优化的目标：

$$Obj = \sum_{i=1}^N L(y_i,f(x_i))+\sum_{m = 1}^{M}\Omega(G_m(x))$$

其中 $N$ 为样本数量，$y_i$ 表示样本真实值，$f(x)$ 是模型输出，所以前半部分代表模型的损失函数。$M$ 表示树的个数，$G_m(x)$ 表示第 $m$ 棵树，$\Omega$ 是模型复杂度函数，是一个正则项。模型越复杂，越容易出现过拟合，所以采用这样的目标函数，为了使得最终的模型既有很好的准确度也有不错的泛化能力。

追加法训练：

核心的思想是，已经训练好的树 $T1…T_{t-1}$ 不再调整。根据目标函数最小原则，新增树 $T_t$ ，表示如下：

$$f_0(x) = 0 \quad 算法初始化$$ $$f_1(x) = G_1(x) = f_0(x)+G_1(x)\quad 训练第１棵树 G_1(x)$$ $$f_2(x) = G_1(x)+G_2(x) = f_1(x)+G_2(x) \quad 训练第２棵树 G_2(x)$$ $$f_t(x) = \sum_{m = 1}^{t} f_m(x) = f_{t-1}(x)+G_t(x) \quad 训练第t棵树，前面t-1棵不再调整$$

假设此时对第 t 棵树训练，则目标函数表示为：

$$Obj^{(t)} = \sum_{i=1}^N L(y_i,f_t(x_i))+\sum_{m = 1}^{t}\Omega(G_m(x)) \\ =\sum_{i=1}^{N}L(y_i, f_{t-1}(x_i)+ G_t(x_i)+\Omega(G_t(x))+constant$$

其中 constant 常数代表 $\sum_{m=1}^{t-1}\Omega(G_m(x))$ ，因为前面 t-1 棵树结构不再变化，所以他们的复杂度为常数。

回顾高等数学中的泰勒展开，它使用一个函数的高阶导数，用多项式的形式逼近原始函数。当展开到二阶导数的时候公式如下：

利用泰勒展开公式和上面推导的 $Obj^{(t)}$ ， $Obj^{(t)}$ 式中，$f_{t-1}(x)$ 对应泰勒公式中的 $x$，而 $G_t(x)$ 是一棵待增加的新树，对应泰勒公式中的 $\Delta x$ ，$L(y_i,f_{t-1}(x))$ 对应泰勒公式中的 $f(x)$ ，而 $L(y_i, f_{t-1}(x_i)+ G_t(x_i)$ 对应泰勒公式中的 $f(x+\Delta x)$ ，则对 $L(y_i, f_{t-1}(x_i)+ G_t(x_i)$ 做二阶泰勒展开，得：

$$Obj^{(t)} =\sum_{i=1}^{N}[L(y_i, f_{t-1}(x_i))+ g_iG_t(x_i)+\frac{1}{2}h_iG_t^2(x_i)]+\Omega(G_t(x))+constant$$

其中：

$$g_i = \frac{\partial L(y_i, f_{t-1}(x_i))}{\partial f_{t-1}(x_i)} \quad 一阶导数 \\ h_i = \frac{\partial L(y_i, f_{t-1}(x_i))}{\partial^2 f_{t-1}(x_i)} \quad 二阶导数$$

因为我们求解的目标是使得 $Obj^{(t)}$ 最小的 $G_t(x)$ 。当前面 $t-1$ 棵树都已经确定时， $\sum_{i=1}^{N}[L(y_i, f_{t-1}(x_i))$ 是一个常量，可以省略，constant 常量也可以省略，因此简化得到新的目标函数：

$$Obj^{(t)} =\sum_{i=1}^{N}[ g_iG_t(x_i)+\frac{1}{2}h_iG_t^2(x_i)]+\Omega(G_t(x))$$

从XGBoost原理部分可以看出，XGBoost的实现中，采用了二阶泰勒展开公式展开来近似损失函数，同时在求解树的过程中，使用了贪心算法，并使用枚举特征，样本按照特征排序后，采用线性扫描找到最优分裂点。这种实现方法，是对GDBT思想的逼近，但是在工程上确非常有效。

对比总结

K-means聚类算法

K-means算法

• 算法简介：

  • k-means是一种聚类算法，聚类就是指在不知道任何样本的标签情况下，通过数据之间的内在关系将样本分成若干个类别，使得相同类别样本之间的相似度搞，不同类别之间的样本相似度低。因此，k-mean算法是属于非监督学习的范畴。

  • k是指k个簇（cluster），means是指每个簇内的样本均值，也就是聚类中心

  • 基本思想：通过迭代的方式寻找 k 个簇的划分方案，使得聚类结果对应的代价函数最小。代价函数可以定义为各个样本距离它所属的簇的中心点的误差平方和：

    $$J(c,\mu)=\sum_{i=1}^{N} ||x_{i} - \mu _{c_{i}}||^{2} \\ 其中，x_{i}代表第i个样本，c_{i}是x_{i}所属的簇，\mu_{c_{i}}代表簇对应的中心点（即均值），N是样本总数.$$

• 算法流程：

  k-means算法采用了贪心策略，通过多次迭代来近似求解上面的代价函数，具体算法流程如下：

  • （1）随机选取 k 个点作为初始聚类（簇）中心，记为 $\mu_{1}^{(0)},\mu_{2}^{(0)},…,\mu_{k}^{(0)}$。

  • （2）计算每个样本 $x_{i}$ 到各个簇中心的距离（欧式距离，余弦相似度），将其分配到与它距离最近的簇。

    $$c_{i}^{(t)} \leftarrow \underset{k'}{argmin} ||x_{i}-\mu _{k'}^{(t)}||^{2} \\ 其中,t为当前迭代步数，k'为第k'个簇（类别）(k'=1,2,..,k)$$

  • （3）对于每个簇，利用该簇中的样本重新计算该簇的中心（即均值向量）：

    $$\mu_{k}^{(t+1)} \leftarrow \underset{\mu}{argmin} \sum_{i:c_{i}^{(t)}=k'} ||x_{i}-\mu||^{2}$$

  • （4）重复迭代上面2-3步骤 T 次，若聚类结果保持不变，则结束。

• k-means算法的优点

  • 算法简单易实现。
  • 对于大数据集，这种算法相对可伸缩且是高效的，计算复杂度为 $O(TNk)$ 接近于线性（其中T是迭代次数、N是样本总数、k为聚类簇数）。
  • 虽然以局部最优结束，但一般情况下达到的局部最优已经可以满足聚类的需求。

• k-means算法的缺点

  • 需要人工预先确定初始K值，该值与实际的类别数可能不吻合。
  • K均值只能收敛到局部最优。因为求解这个代价函数是个NP问题，采用的是贪心策略，所以只能通过多次迭代收敛到局部最优，而不是全局最优。
  • K均值的效果受初始值和离群点的影响大。因为 k 均值本质上是基于距离度量来划分的，均值和方差大的维度将对数据的聚类结果产生决定性的影响，因此需要进行归一化处理；此外，离群点或噪声对均值会产生影响，导致中心偏移，因此需要进行预处理。
  • 对于数据簇分布差别较大的情况聚类效果很差。例如一个类别的样本数是另一类的100倍。
  • 样本只能被划分到一个单一的类别中。
  • 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。
  • 对异常值敏感。

K-means++算法

由于 k-means 算法中，初始K值是人为地凭借经验来设置的，聚类的结果可能不符合实际的情况。因此，K值的设置对算法的效果影响其实是很大的，那么，如何设置这个K值才能取得更好的效果呢？

k-means++的主要思想：

• 首先随机选取1个初始聚类中心（n=1）。
• 假设已经选取了n个初始聚类中心（0<n<k），那么在选择第n+1个聚类中心时，距离当前已有的n个聚类中心越远的点越有可能被选取为第n+1个聚类中心。
• 按照 k-means 算法去优化。
• 可以这样理解上面的思想：聚类中心自然是越互相远离越好，即不同的类别尽可能地分开。
• 缺点：难以并行化。

k-means++算法虽然可以更好地初始k个聚类中心，但还是不能解决一个问题，k 值应该取多少才算合理？

如何选取K值？

如何才能合理地选取k值是k-means算法最大的问题之一，一般可以采取手肘法和Gap Statistic方法。

手肘法

k值的选择一般基于经验或者多次实验来确定，手肘法便是如此，其主要思想是：通过多次实验分别选取不同的k值，将不同k值的聚类结果对应的最小代价画成折线图，将曲线趋于平稳前的拐点作为最佳k值。如下图所示：

上图中，k取值在1~3时，曲线急速下降；当k>3时，曲线趋于平稳。因此，在k=3处被视为拐点，所以手肘法认为最佳的k值就是3。

Gap Statistic

Gap Statistics 定义为：

$$Gap(k)=E(logD_{k})-logD_{k} \\ 其中，D_{k}是第k簇聚类对应的损失值，E(logD_{k})是logD_{k}的期望。$$

对于上式的 $E(logD_{k})$，一般通过蒙特卡洛模拟产生。具体操作是：在样本所在的区域内，按照均匀分布随机产生和原样本数目一样的随机样本，计算这些随机样本的均值，得到一个 $D_{k}$，重复多次即可计算出 $E(logD_{k})$ 的近似值。

$Gap(k)$ 可以看做是随机样本的损失与实际样本的损失之差，假设实际样本最佳的簇类数目为 k，那么实际样本的损失应该相对较小，随机样本的损失与实际样本的损失的差值相应地达到最大，即最大的 $Gap(k)$ 值应该对应最佳的k值。

因此，我们只需要用不同的k值进行多次实验，找出使得$Gap(k)$最大的k即可。

到现在为止我们可以发现，上面的算法中，k值都是通过人为地凭借经验或者多次实验事先确定下来了的，但是当我们遇到高维度、海量的数据集时，可能就很难估计出准确的k值。那么，有没有办法可以帮助我们自动地确定k值呢？有的，下面来看看另一个算法。

ISODATA 算法

ISODATA 的全称是迭代自组织数据分析法。它解决了 K 的值需要预先人为的确定这一缺点。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出 K 的大小。ISODATA 就是针对这个问题进行了改进。

主要思想：

• 当某个类别样本数目过多、分散程度较大时，将该类别分为两个子类别。（分裂操作，即增加聚类中心数）
• 当属于某个类别的样本数目过少时，把该类别去除掉。（合并操作，即减少聚类中心数）

算法优点：可以自动寻找合适的k值。

算法缺点： 除了要设置一个参考聚类数量 $k_{0}$ 外，还需要指定额外的3个阈值，来约束上述的分裂和合并操作。具体如下：

1. 预期的聚类数目 $k_{0}$ 作为参考值，最终的结果在 $k_{0}$ 的一半到两倍之间。
2. 每个类的最少样本数目 $N_{min}$，若分裂后样本数目会少于该值，则该簇不会分裂。
3. 最大方差 $Sigma$，用于控制某个簇的样本分散程度，操作该值且满足条件2，则分裂成两个簇。
4. 两个簇最小距离 $D_{min}$，若两个簇距离小于该值，则合并成一个簇。

K-means和 KNN 算法的区别

KNN：KNN的全称是K Nearest Neighbors，意思是K个最近的邻居。K个最近邻居，K的取值肯定是至关重要的。那么最近的邻居又是怎么回事呢？其实啊，KNN的原理就是当预测一个新的值x的时候，根据它距离最近的K个点是什么类别来判断x属于哪个类别。注意KNN算法是有监督学习中的分类算法。

• 1、距离的计算：欧式距离；曼哈顿距离；闵可夫斯基距离。

• 2、K值的选取：通过交叉验证（将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如6：4拆分出部分训练数据和验证数据），从选取一个较小的K值开始，不断增加K的值，然后计算验证集合的方差，最终找到一个比较合适的K值。

  当你增大k的时候，一般错误率会先降低，因为有周围更多的样本可以借鉴了，分类效果会变好。但注意，当K值继续增大的时候，错误率会更高。这也很好理解，比如说你一共就35个样本，当你K增大到30的时候，KNN基本上就没意义了。

  选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合。
  　　
  选择较大的k值，就相当于用较大邻域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

  选择K点的时候可以选择一个较大的临界K点，当它继续增大或减小的时候，错误率都会上升。

• 3、算法流程：

  （1）计算测试数据与各个训练数据之间的距离；

  （2）按照距离的递增关系进行排序；

  （3）选取距离最小的K个点；

  （4）确定前K个点所在类别的出现频率；

  （5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

• KNN的特点：非参，惰性

  • 非参：非参的意思并不是说这个算法不需要参数，而是意味着这个模型不会对数据做出任何的假设，与之相对的是线性回归（我们总会假设线性回归是一条直线）。也就是说KNN建立的模型结构是根据数据来决定的。
  • 惰性：KNN算法不需要大量的训练过程得到一个算法模型，他没有明确的训练数据的过程，或者说这个过程很快。

• 优点：简单易用；模型训练时间快；预测效果好；对异常值不敏感

• 缺点：对内存要求较高，因为该算法存储了所有训练数据；预测阶段可能很慢；对不相关的功能和数据规模敏感

k-means和KNN的不同点：

• KNN为分类，K-means为聚类；
• KNN为监督学习，K-means为无监督学习；
• KNN的输入样本为带label的，K-means的输入样本不带label；
• KNN没有训练过程，K-means有训练过程；
• K的含义不同：
  • KNN：直接把待分类点周边最近的k个点计数，数量多的那类定为待分类点的类别。无训练的过程。
  • K-means：先定好k个类别，然后随机确定k个坐标（聚类中心），各点离哪个坐标近就算做哪类，然后不停算平均值求出中心，直到稳定，聚类完成。有训练的过程。

相同点：都是计算最近邻，一般都用欧氏距离。

K-means和GMM算法的区别

高斯混合模型（GMM），GMM是指具有如下形式的概率分布模型

$$P(x|\theta)=\sum_{k=1}^{K} \alpha_{k} \phi (x|\theta_{k})\\$$ $$其中，\alpha_{k}是高斯混合系数，\alpha_{k} \geq 0 \ 且\sum_{k=1}^{K}\alpha_{k}=1;$$ $$\theta_{k}=(\mu_{k},\sigma_{k}^{2});$$ $$\phi (x|\theta_{k})是第k个高斯分布模型的概率密度函数，具体形式如下：$$ $$\phi (x|\theta_{k})=\frac{1}{\sqrt {2\pi} \sigma_{k}} exp\left ( -\frac{(y-\mu_{k})^{2}}{2\sigma_{k}^{2}} \right )$$ $$其中，u_k是均值，\sigma_{k}^2是方差$$

$\phi (x|\theta_{k})$的值代表：x由参数$\theta_{k}$下的高斯模型生成的概率。据此可以==判断x属于第k个高斯模型生成的概率。==

GMM聚类：高斯混合模型（GMM）聚类的思想和 k-means 其实有点相似，都是通过迭代的方式将样本分配到某个簇类中，然后更新簇类的信息，不同的是GMM是基于概率模型来实现的，而 k-means 是非概率模型，采用欧氏距离的度量方式来分配样本。

GMM聚类主要思想和流程：

​ 每个GMM由K个混合成分组成，每个混合成分都是一个高斯分布，$\alpha_{k}$ 为相应的混合系数。GMM模型假设所有的样本都根据高斯混合分 布生成，那么每个高斯分布其实就代表了一个簇类。具体流程如下：

​ （1）先初始化高斯混合模型的参数 $\{(\alpha_{k},\mu_{k},\sigma_{k}^{2})\ | \ 1\leq k \leq K \ \}$ ，训练一个GMM模型需要估计这些参数，如何估计后面会介绍。

​ （2）对每个样本，固定各个高斯分布，计算样本在各个高斯分布上的概率（即该样本是由某个高斯分布生成而来的概率）。

​ （3）然后固定样本的生成概率，更新参数以获得更好的高斯混合分布。

​ （4）迭代至指定条件结束。

EM算法估计GMM参数

上面提到，要训练一个GMM模型，就需要估计每个高斯分布的参数 $\{(\alpha_{k},\mu_{k},\sigma_{k}^{2})\ | \ 1\leq k \leq K \ \}$，才能知道每个样本是由哪个高斯混合成分生成的，也就是说，数据集的所有样本是可观测数据， $\{(\alpha_{k},\mu_{k},\sigma_{k}^{2})\ | \ 1\leq k \leq K \ \}$ 这些是待观测数据(隐变量)，而估计待观测数据常用的算法就是EM算法。

EM（Expectation-Maximization）算法是常用的估计参数隐变量的礼器，它是一种迭代的方法，其主要的思想就是：若参数$\theta$ 已知，则可以根据训练数据推断出最优隐变量Z的值（E步），若Z的值已知，则可方便的对参数$\theta$ 做最大似然估计（M步）。

EM算法估计高斯混合模型的参数的步骤：

• （1）给定数据集$D=\{x_{1},x_{2},…,x_{m} \}$，初始化高斯混合分布的模型参数 $\{(\alpha_{k},\mu_{k},\sigma_{k}^{2})\ | \ 1\leq k \leq K \ \}$。

• （2）E步：遍历每个样本，对每个样本 $x_{i}$，计算其属于第k个高斯分布的概率：

  $$\gamma_{ik}=\frac{\alpha_{k}\phi(x_{i}|\theta_{k})}{\sum_{k=1}^{K}\alpha_{k}\phi(x_{i}|\theta_{k})} \ ,\quad 其中，\theta_{k}=(\mu_{k},\sigma_{k}^{2})$$

• （3）M步：更新各个高斯分布的参数为$\{(\hat{\alpha}_{k},\hat{\mu}_{k},\hat{\sigma}_{k}^{2})\ | \ 1\leq k \leq K \ \}$ :

$$\hat{\alpha}_{k}=\frac{\sum_{i=1}^{m} \gamma_{ik}}{m} --- m个样本在该类的平均概率$$ $$\hat{\mu}_{k}=\frac{\sum_{i=1}^{m} \gamma_{ik} x_{i}}{\sum_{i=1}^{m} \gamma_{ik}} --- m个样本特征值的加权平均$$ $$\hat{\sigma}_{k}^{2}=\frac{\sum_{i=1}^{m} \gamma_{ik} (x_{i}-\mu_{k})^{2}}{\sum_{i=1}^{m} \gamma_{ik}} --- m个样本的方差加权平均$$

• （4）重复2-3步，直至收敛。

  注意，EM算法通过迭代的方式估计GMM模型的参数，得到的是局部最优解而不是全局最优。

在迭代收敛后，遍历所有的样本，对于每个样本 $x_{i}$，计算它在各个高斯分布中的概率，将样本划分到概率最大的高斯分布中（每个高斯分布都相当于是一个簇类，因此可以理解为是将每个样本划分到相应的类别中，不过实际上是给出属于每个类别的概率而非属于某个类别）。

k-means和GMM的区别：

• k-means算法是非概率模型，而GMM是概率模型

  k-means算法基于欧氏距离的度量方式将样本划分到与它距离最小的类，而GMM则是计算各个高斯分布生成样本的概率，将样本划分到取得最大概率的高斯分布中

• 两者计算的参数不一样

  k-means计算的是簇类的均值，GMM计算的是高斯分布的参数（均值，方差和高斯混合系数）

• k-means是硬聚类，要么属于这一类要么属于那一类；而GMM算法是软聚类，给出的是属于某些类别的概率。

• GMM每一步迭代的计算量比k-means要大。

k-means和GMM的区别：

• 都是聚类算法
• 都需要指定K值，且都受初始值的影响。k-means初始化k个聚类中心，GMM初始化k个高斯分布。
• 都是通过迭代的方式求解，而且都是局部最优解。k-means的求解过程其实也可以用EM算法的E步和M步来理解。

支持向量机（SVM）

概要

支持向量机（support vector machine）SVM：就是有监督学习的二分类分类模型，他的基本模型是定义在特征空间上的间隔最大的线性分类器，SVM的学习策略就是间隔最大化。

支持向量机（英语：support vector machine，常简称为SVM，又名支持向量网络）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

直观理解

图中有分别属于两类的一些二维数据点和三条直线。如果三条直线分别代表三个分类器的话，请问哪一个分类器比较好？

我们凭直观感受应该觉得答案是H3。首先H1不能把类别分开，这个分类器肯定是不行的；H2可以，但分割线与最近的数据点只有很小的间隔，如果测试数据有一些噪声的话可能就会被H2错误分类(即对噪声敏感、泛化能力弱)。H3以较大间隔将它们分开，这样就能容忍测试数据的一些噪声而正确分类，是一个泛化能力不错的分类器。

对于支持向量机来说，数据点若是p维向量，我们用p−1维的超平面来分开这些点。但是可能有许多超平面可以把数据分类。最佳超平面的一个合理选择就是以最大间隔把两个类分开的超平面。因此，SVM选择能够使离超平面最近的数据点到超平面距离最大的超平面。

以上介绍的SVM只能解决线性可分的问题，为了解决更加复杂的问题，支持向量机学习方法有一些由简至繁的模型:

• 线性可分SVM

  当训练数据线性可分时，通过硬间隔(hard margin，什么是硬、软间隔下面会讲)最大化可以学习得到一个线性分类器，即硬间隔SVM，如上图的的H3。

• 线性SVM

  当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM。

• 非线性SVM

  当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM。

线性可分SVM-硬间隔

如下形式的线性可分的训练数据集

$$(X_1,y_1), (X_2,y_2),....(X_i,y_i)$$

其中 $X_i \in R^d$ 是一个含有d个元素的列向量，$y_i$ 是标量，$y_i \in \{ -1, 1\}$，$y_i=1$ 时表示$X_i$属于正类别，反之亦然。

注：$X$, $X_i$, $W$ 等都是（列）向量

感知机的目标: 找到一个超平面使其能正确地将每个样本正确分类。感知机使用误分类最小的方法求得超平面，不过此时解有无穷多个 (例如图1.1的H2和H3以及它俩的任意线性组合)。而线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。

假设超平面$(W,b)$ 能够将训练样本正确分类，对于$(X_i,y_i)$ ,若 $y_i=+1$，则有 $X_{i}^{T} W+b \geq0$, ,若 $y_i=-1$，则有 $X_{i}^{T} W+b \leq 0$， 令：

$$X_{i}^{T} W+b \geq+1, y_{i}=+1$$ $$X_{i}^{T} W+b \leq-1, y_{i}=-1 \tag{2.2.1}$$

超平面与间隔

一个超平面由法向量 $W$ 和截距 $b$ 决定，其方程如下，

$$X^TW+b=0 \tag{2.2.2}$$

其中法向量决定了超平面的方向，截距决定了超平面与远点的距离。我们规定法向量指向的一侧为正类,另一侧为负类。下图画出了三个平行的超平面，法方向取左上方向。

$X$ 和 $W$ 都是列向量，$X^TW$ 会得到二者的点积是一个标量

为了找到最大间隔超平面，我们可以先选择分离两类数据的两个平行超平面，使得它们之间的距离尽可能大。**在这两个超平面范围内的区域称为“间隔(margin)”，最大间隔超平面是位于它们正中间的超平面。这个过程如上图所示。

间隔最大化

将高数里面求两条平行直接的距离公式推广到高维中可以求得上图中的间隔(margin)的 为

$$margin = \rho = \frac{2}{||W||} \tag{2.2.3}$$

目标为 $\rho$ 最大，等价于 $\rho^2$ 最大

$$\max _{W, b} \rho \Longleftrightarrow \max _{W, b} \rho^{2} \Longleftrightarrow \min _{W, b} \frac{1}{2}\|W\|^{2} \tag{2.2.4}$$

同时别忘记了约束条件：

$$X_{i}^{T} W+b \geq+1, y_{i}=+1$$ $$X_{i}^{T} W+b \leq-1, y_{i}=-1 \tag{2.2.5}$$

总结一下，间隔最大化问题的数学表达就是：

$$\begin{array}{l} \min _{W, b} J(W)=\min _{W, b} \frac{1}{2}\|W\|^{2} \end{array}$$ $$\text { s.t. } \quad y_{i}\left(X_{i}^{T} W+b\right) \geq 1, i=1,2, \ldots n . \tag{2.2.6}$$

这就是支持向量机的基本型，下面就是求解过程。

支持向量

在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的数据点称为支持向量(support vector)，支持向量是使 式（2.5）中的约束条件取等的点，即满足：

$$y_i((X_i^TW = b) =1$$

的点，也就是在直线 $X_{i}^{T} W+b= +1$ 或者 $X_{i}^{T} W+b= -1$ 的点，如下图所示：

在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用 (具体推导见后面)。如果移动非支持向量，甚至删除非支持向量都不会对最优超平面产生任何影响。也即支持向量对模型起着决定性的作用，这也是“支持向量机”名称的由来。

对偶问题

如何求解？

$$\begin{array}{l} \min _{W, b} J(W)=\min _{W, b} \frac{1}{2}\|W\|^{2} \end{array}$$ $$\text { s.t. } \quad y_{i}\left(X_{i}^{T} W+b\right) \geq 1, i=1,2, \ldots n . \tag{2.4.1}$$

该公式本身是一个凸二次规划问题，虽然可以直接用现成的优化计算包求解，但是不够高效。定义该公式所述问题为原始问题，我们可以拉格朗日乘子法构造拉格朗日函数再通过求解其对偶问题得到原始问题的最优解，转换为对偶问题来求解的原因是：

• 对偶问题更易求解，由下文知对偶问题只需优化一个变量 $\alpha$ 且约束条件更简单，更加高效；
• 能更加自然地引入核函数，进而推广到非线性问题。

首先需要构建拉格朗日函数，为此引进拉格朗日乘子 $\alpha_i \geq 0, i=1,2,..,n $，则该问题的拉格朗日函数为：

$$L(W, b, \alpha)=\frac{1}{2}\|W\|^{2} + \sum_{i=1}^{n} \alpha_{i}\left[ 1- y_{i}\left(X_{i}^{T} W+b\right)\right] \tag{2.4.2}$$

因此，给定$(W,b)$ ，若不满足式(2.4.1) 的约束条件，那么：

$$\max _{\alpha} L(W, b, \alpha)=+\infty \tag{2.4.3}$$

否则，若满足式(2.4.1) 的约束条件，那么：

$$\max _{\alpha} L(W, b, \alpha)=J(W)=\frac{1}{2}\|W\|^{2} \tag{2.4.4}$$

结合式(2.4.3) 和式(2.4.4)，优化问题为：

$$\min _{W，b}\max _{\alpha} L(W, b, \alpha) \tag{2.4.5}$$

这与支持向量机的基本型式(2.4.1) 所述问题是完全等价的。

根据拉格朗日对偶性，式(2.4.1)所述的原始问题的对偶问题是：

$$\max _{\alpha}\min _{W，b} L(W, b, \alpha) \tag{2.4.6}$$

为了求得对偶问题的解，需要先求得 $L(W, b, \alpha)$ 对 $W$ 和 $b$ 的极小再求对α的极大。

(1) 求 $\min _{W，b} L(W, b, \alpha)$ ：求拉格朗日函数对 $W$ 和 $b$ 的偏导。并且偏导等于0，有

$$\nabla_{W} L(W, b, \alpha)=W-\sum_{i=1}^{n} \alpha_{i} y_{i} X_{i}=0 \Longrightarrow W=\sum_{i=1}^{n} \alpha_{i} y_{i} X_{i} \tag{2.4.7}$$ $$\\ \nabla_{b} L(W, b, \alpha)=-\sum_{i=1}^{n} \alpha_{i} y_{i}=0 \Longrightarrow \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \tag{2.4.8}$$

将上面两个式代入 $L(W, b, \alpha)$, 可将其中的 $W$ 和 $b$ 消去，，

$$\begin{array}{l} L(\mathbf{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\mathbf{w}\|^{2}-\sum_{i=1}^{n} \alpha_{i}\left[y_{i}\left(\mathbf{x}_{i}^{T} \mathbf{w}+b\right)-1\right] \\ =\frac{1}{2} \sum_{i=1}^{n} \alpha_{i} y_{i} \mathbf{x}_{i}^{T} \sum_{j=1}^{n} \alpha_{j} y_{j} \mathbf{x}_{j}-\sum_{i=1}^{n} \alpha_{i} y_{i} \mathbf{x}_{i}^{T} \sum_{j=1}^{n} \alpha_{j} y_{j} \mathbf{x}_{j}-b \sum_{i=1}^{n} \alpha_{i} y_{i}+\sum_{i=1}^{n} \alpha_{i} \\ =\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \alpha_{i} y_{i} \mathbf{x}_{i}^{T} \sum_{j=1}^{n} \alpha_{j} y_{j} \mathbf{x}_{j}=\sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} y_{i} y_{j} \alpha_{j} \alpha_{j} \mathbf{x}_{j}^{T} \mathbf{x}_{i} \end{array} \tag{2.4.9}$$

所以：

$$\min _{W，b} L(W, b, \alpha) = \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} \mathbf{x}_{j}^{T} \mathbf{x}_{i} \tag{2.4.10}$$

（2）对 $\min _{W，b} L(W, b, \alpha)$ 对 $\alpha$ 的极大：就得到原始问题的对偶问题的最优化。

$$\max _{\alpha}\min _{W，b} L(W, b, \alpha) = \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{i=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} \mathbf{x}_{j}^{T} \mathbf{x}_{i}$$ $$s.t. \quad \sum_{i=1}^{n} \alpha_{i} y_{i}=0,$$ $$\quad \alpha_i \geq 0, i=1,2,..,n \tag{2.4.11}$$

（3）如何求解优化问题式 (4.11) 的最优解 $\hat{\alpha}$ ，这是一个二次规划问题，，有现成的通用算法求解。

事实上通用的求解二次规划问题的算法的复杂度正比于训练数据样本数，所以在实际应用中需要寻求更加高效的算法，例如序列最小优化(Sequential Minimal Optimiation, SMO)算法。

（4）假设，我们求得了式 (2.4.11) 的最优解 $\hat{\alpha}$ ，则可以根据式(2.4.7) 求得最优 $\hat{W}$,

$$\hat{W} = \sum_{i=1}^{n} \hat{\alpha_{i}} y_{i} X_{i} \tag{2.4.12}$$

因为至少存在一个 $\hat{\alpha_j} > 0$，若不存在$(\alpha_i=0)$,则 $\hat{W} = 0$,得到 $margin = \frac{2}{||W||} = +\infty$,（显然不行）。再根据原始问题式(4.1)中是有不等式越苏的，因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件，即要求：

$$\left\{\begin{array}{l} \text { 乘子非负: } \alpha_{i} \geq 0(i=1,2, \ldots n . \text { 下同 }) \\ \text { 约束条件: } y_{i}\left(X_{i}^{T} W+b\right)-1 \geq 0 \\ \text { 互补条件 }: \alpha_{i}\left(y_{i}\left(X_{i}^{T} W+b\right)-1\right)=0 \end{array}\right. \tag{2.4.13}$$

所以至少存在一个j，使得 $y_i(X_{i}^{T} \hat{W}+\hat{b}) - 1=0$，即可以求得最优的 $\hat{b}$:

$$\hat{b}=\frac{1}{y_{j}}-X_{j}^{T} \hat{W} = y_{j}-X_{j}^{T} \hat{W} = y_{j}-\sum_{i=1}^{n} \hat{\alpha}_{i} y_{i} X_{j}^{T} X_{i} \tag{2.4.14}$$

（5）至此，我们求得了整个线性可分SVM的解，求得的分离超平面为：

$$\sum_{i=1}^{n} \hat{\alpha_{i}} y_{i} X^T X_{i} + \hat{b} = 0 \tag{2.4.15}$$

支持向量和非支持向量：最优超平面只与支持向量有关而与非支持向量无关。

再来分析KKT条件里的互补条件，对于任意样本 $(X_i, y_i)$ ，总会有 $\alpha_i=0$ 或者 $y_if(X_i) = y_i(X_i^T\hat{W} + b) = 1$。则有若 $\alpha_i=0$ ，此样本点不是支持向量，对模型没有任何作用；若 $\alpha_i>0$ ，此样本点位于最大间隔边界上，是一个支持向量，如下图所示。

则分类的决策函数为

$$f(X) = sign(\sum_{i=1}^{n} \hat{\alpha_{i}} y_{i} X^T X_{i} + \hat{b}) \tag{2.4.16}$$

线性SVM-软间隔

在前面的讨论中，我们一直假定训练数据是严格线性可分的，即存在一个超平面能完全将两类数据分开。但是现实任务这个假设往往不成立，例如下图所示的数据。

软间隔最大化

解决该问题的一个办法是允许SVM在少量样本上出错，即将之前的硬间隔最大化条件放宽一点，为此引入“软间隔(soft margin)”的概念。即允许少量样本不满足约束：

$$y_i((X_i^TW = b) \geq 1 \tag{3.1.1}$$

为了使不满足上述条件的样本点尽可能少，我们需要在优化的目标函数(2.2.4)里面新增一个对这些点的惩罚项。最常用的是hinge损失:

$$l_{hinge}(z) = max(0, 1-z) \tag{3.1.2}$$

即若样本点满足约束条件损失就是0, 否则损失就是 $1-z$, 则优化目标(2.2.4)变成:

$$\min _{W, b} \frac{1}{2}\|W\|^{2} + C \sum_{i=1}^{n}max(0, 1-y_i(X^TW+b)) \tag{3.1.3}$$

其中 $C>0$ 称为惩罚参数，C越小时对误分类惩罚越小，越大时对误分类惩罚越大，当C取正无穷时就变成了硬间隔优化。实际应用时我们要合理选取C，C越小越容易欠拟合，C越大越容易过拟合。

如果我们引入 松弛变量 $\xi_{i} \geq 0$，那种优化目标可以重写为：

$$\min _{W, b} \frac{1}{2}\|W\|^{2} + C \sum_{i=1}^{n} \xi_{i}$$ $$\text { s.t. } \quad y_{i}\left(X_{i}^{T} W+b\right) \ge 1-\xi_{i}$$ $$\xi_{i} \ge 0 ,i=1,2,...n. \tag{3.1.4}$$

上式所述问题即软间隔支持向量机。

对偶问题

式(3.1.4)表示的软间隔支持向量机依然是一个凸二次规划问题，和硬间隔支持向量机类似，我们可以通过拉格朗日乘子法将其转换为对偶问题进行求解。 式(3.1.4)对应的拉格朗日函数为：

$$L(W, b, \xi, \alpha, \beta)=\frac{1}{2}\|W\|^{2}+C \sum_{i=1}^{n} \xi_{i}-\sum_{i=1}^{n} \alpha_{i}\left[y_{i}\left(X_{i}^{T} W+b\right)-1+\xi_{i}\right]-\sum_{i=1}^{n} \beta_{i} \xi_{i} \tag{3.2.1}$$

类似上面，为了求得对偶问题的解，我们需要先求得 $L(W, b, \xi, \alpha, \beta)$ 对 $( W,b, \xi)$ 的极小再求对 $(\alpha, \beta )$ 的极大。

（1）求 $\min _{W，b， \xi} L(W, b, \xi, \alpha, \beta)$：将 $ L(W, b, \xi, \alpha, \beta) $ 分别对 $( W,b, \xi)$ 求偏导，并且偏导为0，得到：

$$W=\sum_{i=1}^{n} \alpha_{i} y_{i} X_{i}$$ $$\sum_{i=1}^{n} \alpha_{i} y_{i}=0$$ $$C = \alpha_i + \beta_i \tag{3.2.2}$$

将上面两个式代入 $L(W, b, \xi, \alpha, \beta)$, 可将其中的 $W$ 和 $b$ 和 $\beta$ 消去，

$$\min _{W，b, \xi} L(W, b, \xi, \alpha, \beta) = \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} \mathbf{x}_{j}^{T} \mathbf{x}_{i} \tag{3.2.3}$$

（2）对 $\min _{W，b, \xi} L(W, b, \alpha, \beta)$ 对 $\alpha$ 的极大：就得到原始问题的对偶问题的最优化。

$$\max _{\alpha}\min _{W，b, \xi} L(W, b, \alpha, \beta) = \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{n} \sum_{i=1}^{n} y_{i} y_{j} \alpha_{i} \alpha_{j} \mathbf{x}_{j}^{T} \mathbf{x}_{i}$$ $$s.t. \quad \sum_{i=1}^{n} \alpha_{i} y_{i}=0,$$ $$\quad 0 \leq \alpha_i \leq C, i=1,2,..,n \tag{3.2.4}$$

（3）类似上面，可以利用现成的通用算法，例如SMO算法 ，求式(3.2.4)。

（4）KTT条件：

$$\left\{\begin{array}{l} \text { 乘子非负: } \alpha_{i} \geq 0, \beta_{i} \geq 0(i=1,2, \ldots n . \text { 下同 }) \\ \text { 约束条件: } y_{i}\left(X_{i}^{T} W+b\right)-1 \geq \xi_i \\ \text { 互补条件 }: \alpha_{i}\left[y_{i}\left(X_{i}^{T} W+b\right)-1 + \xi_i\right]=0, \beta_i\xi_i=0 \end{array}\right. \tag{3.2.5}$$

对于任意样本 $(X_i,y_i)$，若 $\alpha_i=0$，此样本点不是支持向量，该样本对模型没有任何的作用；若 $\alpha_i>0$，此样本是一个支持向量。

因此，最优超平面只与支持向量有关而与非支持向量无关。

惩罚参数C

对于不同惩罚参数C，SVM结果如下图所示

再来看看我们的原始目标函数:

$$\min _{W, b} \frac{1}{2}\|W\|^{2} + C \sum_{i=1}^{n} \xi_{i} \tag{3.2.6}$$

对于更加一般化的问题，可将上述式子抽象成：

$$\min _{f} \Omega(f)+C \sum_{i=1}^{n} l\left(f\left(x_{i}\right), y_{i}\right) \tag{3.2.7}$$

前一项可以理解为“结构风险(structural risk)”，用来描述所求模型的某些性质(SVM就是要求间隔最大)；第二项称为“经验风险(empirical risk)”，用来描述模型与训练数据的契合程度(即误差)。而参数C就是用于对二者的折中,即我们一方面要求模型要满足某种性质另一方面又想使模型与训练数据很契合。

从正则化角度来讲，Ω(f)称为正则化项，C称为惩罚参数，C越大即对误分类的惩罚越大(要求模型对训练模型更契合)，这可能会存在过拟合；C越小即相对更加看重正则化项，此时可能存在欠拟合。

非线性SVM-核技巧

前面介绍的都是线性问题，但是我们经常会遇到非线性的问题(例如异或问题)，此时就需要用到核技巧(kernel trick)将线性支持向量机推广到非线性支持向量机。需要注意的是，不仅仅是SVM，很多线性模型都可以用核技巧推广到非线性模型，例如核线性判别分析(KLDA)。

为了使不满足上述条件的样本点尽可能少，我们需要在优化的目标函数(2.2.2)里面新增一个对这些点的惩罚项。最常用的是hinge损失:

核函数

核技巧的基本思路分为两步:

• 使用一个变换将原空间的数据映射到新空间(例如更高维甚至无穷维的空间)；
• 然后在新空间里用线性方法从训练数据中学习得到模型。

和函数的定义：

设X是输入空间(欧式空间$R^n$的子集或离散集合)，又设H是特征空间(希尔伯特空间)，如果存在一个X到H的映射 ϕ(x):X→H 使得对所有 x,z∈X，函数 K(x,z) 满足条 件K(x,z)=ϕ(x)⋅ϕ(z) 则称 K(x,z) 为核函数，ϕ(x)为映射函数，式中 ϕ(x)⋅ϕ(z) 为 ϕ(x)和ϕ(z) 的內积。

通常，直接计算 K(x,z) 比较容易而通过 ϕ(x)和ϕ(z) 计算 K(x,z) 并不容易。而幸运的是，在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都只涉及到输入样本与样本之间的內积，因此我们不需要显式地定义映射 ϕ(x) 是什么，而只需事先定义核函数 K(x,z) 即可。也就是说，在核函数 K(x,z) 给定的情况下，可以利用解线性问题的方法求解非线性问题的支持向量机，此过程是隐式地在特征空间中进行的。

正定核

由上面的介绍可知，我们只需要定义核函数就可以了。但是如何不通过映射 ϕ(x) 判断给定的一个函数 K(x,z) 是不是核函数呢？或者说，K(x,z) 需要满足什么条件才是一个核函数？

通常所说的核函数就是正定核函数。常用的核函数：

• 多项式核函数：

  $$K(x, z) = (x \cdot z + 1)^p$$

• 高斯核函数：

  $$K(x, z) = exp(-\frac{||x-z||^2}{2 \sigma})$$

非线性支持向量机

利用核技巧可以很简单地把线性支持向量机扩展到非线性支持向量机，只需将线性支持向量机中的內积换成核函数即可。下面简述非线性支持向量机学习算法。

• 首先选取适当的核函数 $K(x,z)$ 和适当的参数 $C$，构造最优化问题：

  $$\max _{\alpha}\min _{W，b} L(W, b, \alpha) = \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} y_{i} y_{j} \alpha_{j} \alpha_{j} K(X_i,K_j)$$ $$s.t. \quad \sum_{i=1}^{n} \alpha_{i} y_{i}=0,$$ $$\quad 0 \leq \alpha_i \leq C, i=1,2,..,n$$

• 构造决策函数： $$f(X) = sign(\sum_{i=1}^{n} \hat{\alpha_{i}} y_{i} K(X_i,K_j) + \hat{b})$$

总结

• 简单介绍SVM？

  支持向量机SVM是一种二类分类模型。它的基本模型是定义在特征空间中的间隔最大的线性分类器。学习的目标就是在特征空间内找到一个分离超平面，能够将实例分到不同的类。

  从分类平面，到求两类间的最大间隔，到转化为求间隔分之一，等优化问题，然后就是优化问题的解决办法，首先是用拉格拉日乘子把约束优化转化为无约束优化，对各个变量求导令其为零，得到的式子带入拉格朗日式子从而转化为对偶问题，最后再利用SMO（序列最小优化）来解决这个对偶问题。

  • 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
  • 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
  • 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

• 什么是支持向量？

  在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。

• SVM为什么采用间隔最大化？

  当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。可以借此机会阐述一下几何间隔以及函数间隔的关系

• 为什么要将求解问题SVM的原始问题转换为其对偶问题？

  • 对偶问题往往更易求解，当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。

  • 可以自然引入核函数，进而推广到非线性分类问题。

  • 求解更高效，改变了问题的复杂度，由求特征向量w转化为求比例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。因为只用求解alpha系数，而alpha系数只有支持向量才非0，其他全部为0。

• 为什么SVM要引入核函数？

  当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。而引入这样的映射后，所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。核函数的定义：K(x,y)=<ϕ(x),ϕ(y)>，即在特征空间的内积等于它们在原始样本空间中通过核函数 K 计算的结果。一方面数据变成了高维空间中线性可分的数据，另一方面不需要求解具体的映射函数，只需要给定具体的核函数即可，这样使得求解的难度大大降低。

• 为什么SVM对数据确实敏感？

  缺失数据是指缺失某些特征数据，向量数据不完整。SVM没有处理缺失值的策略（决策树有）。而SVM希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

支持向量机的优点:

1. 由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
2. 不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
3. 拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维数灾难”。
4. 理论基础比较完善(例如神经网络就更像一个黑盒子)。
5. SVM无需依赖所有样本， 只依赖支持向量

支持向量机的缺点是:

1. 二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
2. 只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)
3. SVM对缺失值敏感
4. 如果特征维度远大于样本个数，SVM变现一般
5. SNM在样本巨大且使用核函数时计算量很大。

降维算法

降维就是用低纬度的向量来表示原始高纬度的特征。

降维的作用：增大样本密度，可以缓解维数灾难；减少计算开销；去噪

PCA算法

PCA算法，就是主成分分析法（Components Analysis，PCA），旨在找到数据中的主成分，并利用这些主成分来表征原始数据。简单的来说就是将n维的特征映射到k维上（k<n）,这k维的正交特征，这就是主成分。

是一个非监督的机器学习算法，是一种用于探索高维数据结构的技术，主要用于对数据的降维，通过降维可以发现更便于人理解的特征，加快对样本有价值信息的处理速度，此外还可以应用于可视化（降到二维）和去噪。

PCA降维准则：

• 最大可分性：样本点在这个超平面（直线的高维推广）的投影尽可能地分开（最大化方差）
• 最近重构性：样本点到这个超平面地距离都足够近（最小化平方误差）

PCA之最大可分性（最大方差）

用方差来定义样本的间距，方差越大表示样本分布越稀疏，方差越小表示样本分布越密集。

PCA的优化目标，就是最大化投影方差。换种说法就是，让数据在某个超平面（主轴）上投影的方差最大。

最大化方差公式推导：

• （1）给定一组样本点$\{v_{1},v_{2},…,v_{n}\}$，首先将其中心化后表示为$\{x_{1},x_{2},…,x_{n}\}=\{v_{1}-\mu,v_{2}-\mu,…,v_{n}-\mu\}$，其中，$\mu=\frac{1}{n}\sum_{i=1}^{n}v_{i}$。去均值后，样本x每个特征维度上的均值都是0。

• （2）因为一个向量$x_{i}$在$\omega$（单位方向向量）上的投影可以表示为两者的内积$=x_{i}^{T}\omega$，而PCA的目标就是找到一个投影方向$\omega$，使得所有的数据$\{x_{1},x_{2},…,x_{n}\}$在$\omega$上的投影方差尽可能地大，因此：

• （3）投影后的方差可以表示为：

  $$D(x)=\frac{1}{n}\sum_{i=1}^{n}(x_{i}^{T}\omega)^2 \\=\frac{1}{n}\sum_{i=1}^{n}(x_{i}^{T}\omega)^{T}(x_{i}^{T}\omega) \\=\frac{1}{n}\sum_{i=1}^{n}\omega^{T}x_{i}x_{i}^{T}\omega =\omega^{T}\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{T}\right)\omega$$

• （4）然后可以发现，上面大括号内的$\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{T}$就是原始样本的协方差矩阵，令其等于$\Sigma$。

  补充理解：协方差公式形式：

  $$Cov(x,y)=\frac{1}{n-1}\sum_{i=1}^{n}(x_{i}-\mu_x)(y_{i}-\mu_{y})$$

  在均值 $\mu=0$ 时，（当n足够大时，n-1可以约等于n），于是有：

  $$Cov(x,y)=\frac{1}{n}\sum_{i=1}^{n}x_{i}y_{i}$$

  对于步骤③中 $x_{i}$，是原始样本 $v_{i}$ 中心化后的，因此可以说 $\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{T}$ 就是原始样本的协方差矩阵。

• （5）因此，上面的最大化方差D(x)的优化问题可以转化为

$$\begin{cases}max\{\omega^{T}\Sigma\omega\},\\s.t. \ \ \omega^{T}\omega=1.\end{cases}\\ 其中，\omega是单位向量，因此有\ \omega^{T}\omega=1.$$

• （6）对于上面的优化目标，可以构造拉格朗日函数来解决：

  $$L(\omega)=\omega^{T}\Sigma\omega+\lambda(1-\omega^{T}\omega)\\ 对\ \omega\ 求导并令其等于0，可得\ \Sigma\omega=\lambda\omega$$

  补充一点矩阵微分的知识，有助于理解上式的求导过程：（非常有用的公式！！！可以记住！）

  $$①\ \frac{\partial x^{T}a}{\partial x}=\frac{\partial a^{T}x}{\partial x}=a\ \ \ \ \\②\ \frac{\partial x^{T}Ax}{\partial x}=(A+A^{T})x$$

  因此，对拉格朗日函数的求导便很容易理解了：

  $$\frac{\partial L(\omega)}{\partial\omega}=(\Sigma+\Sigma^{T})\omega-\lambda(I+I^{T})\omega\\ 其中 I为单位矩阵$$

  还记得$\Sigma$是什么吗？由上面定义可知，$\Sigma=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{T}$，很显然，$\Sigma$的转置$\Sigma^{T}$=$\Sigma$，因此上面可化简为：

  $$\frac{\partial L(\omega)}{\partial\omega}=2\Sigma\omega-2\lambda\omega\\ 令其等于0，便可得\ \Sigma\omega=\lambda\omega$$

• （7）由此，最终可以得到最大方差： $$D(x)=\omega^{T}\Sigma\omega=\lambda\omega^{T}\omega=\lambda$$ 至此，公式推导已经完成，现在我们不难看出，x 投影后的方差就是协方差矩阵的特征值，理解了这一点一切就很清晰了。因此，我们要找到最大的方差，也就是相当于要求协方差矩阵的最大特征值，而最佳投影方向就是最大特征值所对应的特征向量。

PCA的求解过程总结

• （1）对原始样本进行中心化处理，即零均值化，即每一位特征减去各自的平均值。

• （2）求出样本的协方差矩阵 $\Sigma=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{T}$

• （3）求解协方差矩阵的特征值和特征向量

• （4）将特征值由大到小排列，取出前 k 个特征值对应的特征向量

• （5）将 n 维样本映射到 k 维，实现降维处理。

  $$x_{i}^{'}=\begin{bmatrix}\omega_{1}^{T}x_{i}\\\omega_{2}^{T}x_{i}\\\vdots \\\omega_{k}^{T}x_{i} \end{bmatrix}\\ 新的x_{i}^{'}的第k维就是x_{i}在第k个主成分\omega_{k}方向上的投影.$$

PCA之最近重构性（最小平方误差）

超平面是直线在高维空间的推广，因此，最大化方差就是寻找一个超平面使得样本点在超平面上的投影方差最大，而最小平方误差就是寻找一个超平面使得样本点到这个超平面的距离平方和最小，也就是最近重构性。

PCA的优缺点和应用场景

优点：

• 它是无监督学习算法，完全无参数限制。

• 降维，减小计算开销

• 使得数据集更易使用；

• 去除噪声

• 使得结果容易理解

缺点：

• 如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高；
• 特征值分解有一些局限性，比如变换的矩阵必须是方阵

应用场景：

• 高维数据集的探索与可视化。
• 数据压缩。
• 数据预处理。
• 图象、语音、通信的分析处理。
• 降维(最主要)，去除数据冗余与噪声。

LDA算法

LDA算法，就是线性判别分析（Linear Discriminant Analysis，LDA）。

LDA是一种线性的、有监督的降维方法，即每个样本都有对应的类别标签（这点和PCA不同）。

主要思想：给定训练样本集，设法将样本投影到一条直线上，使得同类的样本的投影尽可能的接近、异类样本的投影尽可能地远离（即最小化类内距离和最大化类间距离）。

● 为什么要将最大化类间距离和最小化类内距离同时作为优化目标呢？

先看上面第二张图的左图（a），对于两个类别，只采用了最大化类间距离，其结果中两类样本会有少许重叠；而对于右图（b），同时最大化类间距离和最小化类内距离，可见分类效果更好，同类样本的投影分布更加集中了。当然，对于二维的数据，可以采用将样本投影到直线上的方式，对于高维的数据，则是投影到一个低维的超平面上，这应该很好理解。

优化目标：LDA算法的思想就是最大化类间距离和最小化类内距离，其优化目标就很直观了，那怎么用数学方式来表示呢？要解决这个问题，就得先看看怎么描述类间距离和类内距离？推理略

LDA算法求解流程

• （1）计算每类样本的均值向量 $\mu_{i}$。

• （2）计算类间散度矩阵 $S_{\omega}$ 和类内散度矩阵 $S_{b}$ 。

• （3）求矩阵 $S_{\omega}^{-1}S_{b}$ 的特征值即对应的特征向量，从大到小排序。

• （4）将特征值由大到小排列，取出前 k 个特征值对应的特征向量。

• （5）将 n 维样本映射到 k 维，实现降维处理。

  $$x_{i}^{'}=\begin{bmatrix}\omega_{1}^{T}x_{i}\\\omega_{2}^{T}x_{i}\\\vdots \\\omega_{k}^{T}x_{i} \end{bmatrix}\\$$

LDA算法总结

• LDA是线性的、有监督的降维方法，其优点是善于对有类别信息的数据进行降维处理（与PCA的不同）。
• LDA因为是线性模型，对噪声的鲁棒性较好，但由于模型简单，对数据特征的表达能力不足。
• LDA对数据的分布做了一些很强的假设，比如每个类别都是高斯分布、各个类别的协方差相等，实际中这些假设很难完全满足。

PCA和LDA的区别

异同点

相同点：

• ① 均是降维方法
• ② 降维时均使用了矩阵特征分解的思想
• ③ 两者都假设数据符合高斯分布

不同点：

• ① PCA是无监督的降维方法，而LDA是有监督的降维方法
• ② LDA除了可以降维，还可以用于分类
• ③ LDA降维最多降到类别数 k-1的维数（k是样本类别的个数），而PCA没有这个限制。
• ④ LDA选择的是分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向

● 关于第4点，可以这样理解：

LDA在降维过程中最小化类内距离，即同类样本的方差尽可能小，同时最大化类间距离，即异类样本尽可能分离，这本身是也为分类任务服务的；而PCA是无监督的降维方法，其假设方差越大，信息量越多，因此会选择样本点投影具有最大方差的方向。

优缺点

LDA优点：

• ① 降维过程中可以使用类别的先验知识（有监督的），而PCA是无监督的
• ② 在样本分类信息依赖均值而不是方差的时候，LDA算法优于PCA算法

LDA缺点：

• ① LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。
• ② LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好。
• ③ LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。
• ④ LDA可能过度拟合数据。

PCA优点：

• ①它是无监督学习算法，完全无参数限制。
• ② 在样本分类信息依赖方差而不是均值的时候，PCA算法优于LDA算法

PCA缺点：

• ①特征值分解有一些局限性，比如变换的矩阵必须是方阵
• ②如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高

关键点检测

SIFT算法（(Scale Invariant Feature Transform）：度不变特征转换匹配算法。

• 创建比例空间：确保要素与比例无关
• 关键点本地化：确定合适的特征或关键点
• 方向分配：确保关键点是角度不变
• 关键点描述符：为每个关键点分配独一的指纹