本科课程数据挖掘与统计决策的复习。

目录

• 绪论和python
• 回归模型
• 聚类模型
• 关联规则
• 决策树
• 支持向量机
• 贝叶斯网络
• 神经网络
• EM算法
• 奇异值分解

绪论和python

数据科学的基本概念和建模流程。

基本概念

1. 大数据特征：数据量大（Volume），数据种类多（Variety），价值密度低（Veracity），速度快时效高（Velocity）。
2. 数据建模的两种思路。
   • 统计模型：假设数据的产生过程已知，通过模型去理解整个过程。有很好的可解释性，有很多分析稳定性的数学工具，实际中的预测效果并不好。
   • 算法模型：也即机器学习。假设数据的产生过程是复杂未知的，建模的目的是尽可能地从结构上“模仿”数据的产生过程，达到好的预测效果。模型的可解释性差，稳定性分析工具少。

建模流程

获取数据$\rightarrow$数据分析可视化$\rightarrow$数据准备$\rightarrow$建立模型$\rightarrow$结果评估。

1. 可视化：箱线图，散点图，散点图矩阵，平行坐标图（高维数据）。
2. 数据预处理：特征提取，数据缺失，数据不平衡，异常数据。
3. 结果评估
   • 错误率：错分样本的占比。
   • 误差：样本真实输出和预测输出之间的差异。（训练误差，测试误差，泛化误差）
   • 过拟合：将训练样本本身的特点 当做所有样本的一般性质，导致泛化性能下降。（优化目标加正则项，early stop)
   • 正则本质上是对参数多了个约束条件，限制了模型的复杂度，提升模型泛化能力。
   • 欠拟合：对训练样本的一般性质尚未学好
   • 交叉验证法（将数据集分层采样划分为k个大小相似的互斥子集，每次用k -1个子集的并集作为训练集，余下的子集作为测试集，最终返回k个测试结果的均值）
   • 留出法（直接将数据集划分为两个互斥集合）等是常用的划分训练、测试集的方法。

回归模型

回归模型的基本概念

回归分析是基于观测数据建立变量间适当的依赖关系，以分析数据内在规律，并可用于预报、控制等问题，是应用极其广泛的数据分析方法之一。

回归分析考虑建立可观测的因素变量$(𝑥_1,𝑥_2,\dots,𝑥_𝑝)$与变量 $y$ (因变量)之间的确定性或不确定性关系，即：
$$Y = f(𝑥_1,𝑥_2,\dots,𝑥_𝑝) + \epsilon, \varepsilon \sim N\left(0, \sigma^{2}\right)$$

线性回归

通常用最小二乘法求解析解。

• 满秩时：$\hat y = X \hat{\beta} = X(X^TX)^{-1}X^Ty$
• 欠定方程：通常采取的是引入正则（L1)。

统计检验

1. 相关系数检验(单个变量)：
   $r=\frac{\operatorname{Cov}(X, Y)}{\sqrt{D X \cdot D Y}}$，$\hat{r} > r_{1-\frac{\alpha}{2}}(n-2)$。
2. F检验（线性回归方程整体的显著性检验）：$H_0:\beta_1 = \dots = \beta_p = 0$
   $$\sum_{i=1}^{n}\left(y_{i}-\bar{y}\right)^{2}=\sum_{i=1}^{n}\left(y_{i}-\hat{y}{i}\right)^{2}+\sum{i=1}^{n}\left(\hat{y}{i}-\bar{y}\right)^{2}$$
   或者记为$S_T^2 = S_E^2 + S_R^2$，$S_E^2$残差平方和（模型不可解释的误差，越小越好），$S_R^2$回归平方和，回归模型可解释的部分。
   $$ F = \frac{S_R^2 / P}{S_E^2/(n-p-1)} \sim F{\alpha}(p,n-p-1)$$
3. t检验（单个系数是否为0）：$T_{i}=\frac{\hat{\beta}{i}}{\sqrt{c{i i}} \hat{\sigma}} \sim t(n-p-1)$
4. 拟合优度检验：$R^2 = \frac{S_R^2}{S_T^2}$

逻辑回归

假设发生比的对数为线性模型,发生比$\Omega$，表示该事件发生和不发生的比率
$$\ln \Omega=\ln \frac{P\left(y_{i}=1\right)}{1-P\left(y_{i}=1\right)}=\beta_{0}+x_{i, 1} \beta_{1}+x_{i, 2} \beta_{2}+\cdots+x_{i, p} \beta_{p}+=X_{i}^{T} \boldsymbol{\beta}$$
由于Logistic回归是非线性模型，极大似然估计法是最常用的模型参数估计方法。
$$\hat{P}\left(y_{i}=1\right)=\frac{1}{1+e^{-X_{i}^{T} \widehat{\beta}}}=\frac{e^{X_{i}^{T} \widehat{\beta}}}{1+e^{X_{i}^{T} \hat{\beta}}}$$

• 多分类，sorfmax

统计检验

1. 回归系数的显著性检验(Wald检验统计量)：$H_0:\beta_1 =0$
   $$ wald = (\frac{\beta_1}{S_{\beta_1}})^2$$
   $\beta_1$是回归系数, $S_{\beta_1}$是回归系数标准误差。Wald检验统计量服从$\chi^{2}(1)$分布。

聚类模型

聚类分析的基本概念

聚类目标：将数据集中的样本划分为若干个通常不相交的子集（“簇”，cluster）。聚类结果的“簇内相似度”（intra-cluster similarity）高，且“簇间相似度”（inter-cluster similarity）低，这样的聚类效果较好。

无量纲化

1. 标准差标准化：将数据转化为均值为0，方差为1的分布。
   $$x_{i j}^{\prime}=\frac{x_{i j}-\overline{x_{j}}}{s_{j}}$$
2. 极差标准化：将数据转化为[0,1]的分布。
   $$x_{i j}^{\prime}=\frac{x_{i j}-\min {1 \leq i \leq n}\left(x{i j}\right)}{R_{j}}$$

常见距离

1. 绝对值距离（1范数）
2. 欧式距离（2范数)
3. 切比雪夫(无穷范)$d_{i j}(\infty)=\max {1 \leq k \leq m}\left|x{i k}-x_{j k}\right|$
4. 闵可夫斯基距离（p范数）
5. 基于距离的类-类间距离
   • 最短距离
   • 最长距离
   • 平均距离

性能度量

聚类性能度量大致分为两类：一类是将聚类结果与某个“参考模型”进行比较，称为外部指标；另一类是直接考虑聚类结果而不利用任何参考模型，称为内部指标。

外部指标

给出簇划分C和C，$\lambda和\lambda$代表对应的簇标记向量。
$$a=|S S|, S S=\left{\left(x_{i}, x_{j}\right) \mid \lambda_{i}=\lambda_{j}, \lambda_{i}^{}=\lambda_{j}^{}, i<j\right}$$
$$b=|S D|, S D=\left{\left(x_{i}, x_{j}\right) \mid \lambda_{i}=\lambda_{j}, \lambda_{i}^{} \neq \lambda_{j}^{}, i<j\right}$$
$$c=|D S|, D S=\left{\left(x_{i}, x_{j}\right) \mid \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{}=\lambda_{j}^{}, i<j\right}$$
$$d=|D D|, D D=\left{\left(x_{i}, x_{j}\right) \mid \lambda_{i} \neq \lambda_{j}, \lambda_{i}^{} \neq \lambda_{j}^{}, i<j\right}$$

1. Jaccard系数
   $$ JC = \frac{a}{a+b+c}$$
2. FM指数
   $$ FMI = \sqrt{\frac{a}{a+b} \times \frac{a}{a+c}}$$
3. Rand指数
   $$RI = \frac{2(a+d)}{n(n-1)}$$

三个指标的值都在[0,1]，越大越好。

内部指标

1. 蔟内样本间的平均距离
   $$\operatorname{avg}\left(C_{i}\right)=\frac{2}{\left|C_{i}\right|\left(\left|C_{i}\right|-1\right)} \sum_{1 \leq i<j \leq\left|C_{i}\right|} \operatorname{dist}\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)$$
2. 蔟内样本最远（最近）距离。
3. 簇间中心点间距离
4. DB指数
   $$\mathrm{DBI}=\frac{1}{k} \sum_{i=1}^{k} \max {j \neq i}\left(\frac{\operatorname{avg}\left(C{i}\right)+\operatorname{avg}\left(C_{j}\right)}{d_{\operatorname{cen}}\left(\boldsymbol{u}{i}, \boldsymbol{u}{j}\right)}\right)$$
5. Dunn指数
   $$\mathrm{DI}=\min {1 \leq i \leq k}\left{\min _{j \neq i}\left(\frac{d{\min }\left(C_{i}, C_{j}\right)}{\max {1 \leq l \leq k} \operatorname{diam}\left(C{l}\right)}\right)\right}$$

DBI的值越小越好，而DI则相反，值越大越好。

K-means

给定数据集${x_l}{l=1}^n$，要将其划分为$𝑘$个簇，$𝑘$个簇中心记为$𝒄_𝑖$,希望数据到它所属类中心的距离越小越好,损失函数如下：
$$J=\min _{\left{c{i}, i=1,2, \ldots, k\right}} \sum_{i=1}^{k} \sum_{x \in c_{i}}\left|x-c_{i}\right|_{2}^{2}$$
是NP难问题。因此，K-means聚类算法采用贪心策略，通过迭代优化来近似求解式

算法假设

1. 用欧式距离来衡量数据间的相似程度，因此它要求数据在各个维度上是匀质的。
2. 损失函数中，不同类别的权重是一样的，即模型假设不同类别的内部方差是大致相等的。
3. 主要发现圆形或者球形簇，不能识别非球形的簇。

求解过程

1. 给出类数K，随机选取K个样本作为聚类中心。
2. 将样本按最小欧式距离归入聚类块。
3. 调整聚类中心，取蔟内平均。
4. 直到聚类中心不再变化，体制迭代。

缺点

1. K-means算法的第一步是随机产生初始的聚类中心，因此对同一批数据，多次使用K-means算法进行聚类，可能会得到不同的聚类结果，即K-means的预测结果并不稳定。算法收敛到了局部极值点而非全局最值点。算法在达到收敛之前就停止迭代了。反复多次训练模型，从中选择效果最好的。
2. 𝑘值选取问题，必须事先给出𝑘值，并且对𝑘值的选取不同会导致结果不同。
3. 对噪声和孤立点敏感（对所有数据进行聚类，不识别噪声点和孤立点）。
4. 只适用于凸域。

优点

1. 对于大数据的处理较为高效（时间复杂度为𝑂(𝐼𝑘𝑛𝑚) ，𝐼迭代次数，𝑘为聚类簇数，𝑛为数据个数，𝑚为数据维数），并且当数据较为密集时，聚类的结果较好。

调参

𝑘值表示聚类模型的复杂度，模型越复杂，对训练数据的预测效果越好，但也越容易引发过拟合问题。需要在聚类个数𝑘和预测误差平方和𝐽之间做出妥协。

1. 手肘法：假设当聚类个数小于真实的类别个数时，聚类结果的误差平方和会下降得很快，但当聚类个数超过真实值时，误差平方和虽然会下降，但下降速度会明显减缓。
2. 轮廓法：轮廓系数法的思路是计算聚类中心能在多大程度上代表这个类别里的所有数据。 假设对于一个聚类结果, 𝑎表示样本i到蔟内其他数据距离均值,而𝑏 表示数据 𝑖 到最近簇数据的平均距离,则定义如下的轮廓系数𝑠 :
   $$s_{i}=\frac{b-a}{\max (a, b)}, s_{i} \in[-1,1]$$
   $𝑠_𝑖=1$,表示聚类的结果达到了最完美的状态;而$𝑠_𝑖=−1$表示聚类结果是最糟糕的状态,说明样本𝑖更应该分类到另外的簇;如果轮廓系数$𝑠_𝑖\sim0$，则说明样本𝑖在两个簇的边界上。而且容易证明, 𝑠的取值与聚类个数没有直接的单调相关关系。所有样本的轮廓系数$𝑠_𝑖$的均值称为聚类结果的轮廓系数，是该聚类是否合理、有效的度量。

密度聚类

DBSCAN算法：基于一组“邻域”参数(𝜀,𝑀𝑖𝑛𝑝𝑡𝑠)来刻画样本分布的紧密程度。

定义

1. 密度：对样本$𝒙_𝑗∈𝑫$， 以𝜀为半径的圆区域内包含的点数目作为该点的密度。
2. 核心点：若空间某点的密度大于给定阈值𝑀𝑖𝑛𝑃𝑡𝑠，则该点称为核心点。
3. 直接密度可达（密度直达）：点𝒙_𝑗由点𝒙_𝑖直接密度可达，若其满足：
   • $\boldsymbol{x}{j} \in N{\varepsilon}\left(\boldsymbol{x}_{i}\right)$
   • $\left|N_{\varepsilon}\left(\boldsymbol{x}{i}\right)\right| \geq \operatorname{MinPts}\left(\boldsymbol{x}{i} \text { 是一个核心点 }\right)$
4. 密度可达：对$𝒙𝑖$与$𝒙_𝑗$，若存在样本序列$𝑝_1,𝑝_2,.., 𝑝_𝑛$，其中$𝑝_1= 𝒙_𝑖， 𝑝_𝑛= 𝒙_𝑗$，且$𝑝{𝑖+1}$由$𝑝_𝑖$密度直达，则称点$𝒙_𝑗$由点$𝒙_𝑖$密度可达。
5. 密度相连：对$𝒙_𝑖与𝒙_𝑗$，若存在样本$𝒙_𝑘$使得两样本均由$𝒙_𝑘$密度可达，则称该两样本密度相连。

通过密度可达关系导出簇。
若$x$为核心对象，由$x$密度可达的所有样本组成的集合记为$𝑋={𝑥^′∈𝐷 | 𝑥^′ 由𝑥密度可达}$，则𝑋为满足连接性与最大性的簇。

优点

1. 无需输入类别数𝑘，可适用于任意形状的聚类簇。
2. 对噪声、异常点不敏感，能够识别出噪声点，不依赖于初始类中心的选取。

缺点

1. 样本集密度不均、聚类间距差较大时，聚类结果较差。
2. 样本集较大时，收敛时间较长。
3. 对于参数𝜀和𝑀𝑖𝑛𝑃𝑡𝑠,调参难度较大，不同参数组合对聚类结果影响较大。
4. 对于高维数据，点之间极为稀疏，密度很难定义。

层次聚类

系统聚类（自底向上）

系统聚类法又常被称为谱系聚类法或分层聚类法。
在聚类之前，先将每一个样本或变量都各自看成一类，计算样本之间距离，并以样本之间距离定义类之间的距离。先选择距离最近的一对合并成一个新类，计算新类与其他类之间的距离，再将距离最近的两类合并，如此持续做下去，这样就每次减少一类，直至所有的样本或变量都归为一大类为止，最后可以根据聚类的结果画出一张聚类的树形图，可以直观的反映整个聚类过程。

算法步骤

1. 规定距离（最长，最短），各样本自成一类。
2. 计算距离矩阵最小值，对应的两类合并成新类。
3. 计算新类和其他类的距离。
4. 迭代，直到全部样本聚成一个类，停止。

DIANA算法（自顶向下）

DIANA算法属于分裂的层次聚类，采用一种自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一个簇，或者达到某个终结点，或者两个最近簇之间的距离超过了某个阈值。

概念

簇的直径：簇中任意两个样本点间的最大距离。
一个点的平均相异度：簇中，该点与簇内其他点的距离的平均值。

算法步骤

输入终止条件簇数目K

1. 将所有的样本当成一个初始簇，计算簇的直径。
2. 选出直径最大的簇$𝐶{𝑗^∗}$，在簇$𝐶{𝑗^∗}$中，找到与其他点平均相异度最大的点$𝑃$放入临时的簇$𝐶′$中，剩余的点依旧放在$𝐶_{𝑗^∗}$中。
3. 对于$𝐶{𝑗^∗}$中的其他点，找出到$𝐶′$中最近的点的距离小于到$𝐶{𝑗^∗}$中最近点的距离的点，将该点加入到$𝐶′$中。
4. 不断重复（3）直至$𝐶_{𝑗^∗}$中没有点能分配到$𝐶′$中，转到（5）.
5. 将$𝐶_{𝑗^∗}$和$𝐶′$作为两个单独的簇与其他簇一起组成新的簇的集合，迭代。

优点

1. 适用于任意形状和任意属性的数据集，不需要预先设定聚类数，可以发现类的层次关系。

缺点

1. 计算复杂度太高，$𝑂(𝑛^3)$，一步错步步错。

谱聚类

内容考完试补上。

优点

1. 谱聚类算法使用了降维的技术，所以更加适用于高维数据的聚类。
2. 谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法（比如K-Means）很难做到。
3. 谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解。

缺点

1. 谱聚类对相似度图的改变和聚类参数的选择非常的敏感。
2. 谱聚类适用于均衡分类问题，即各簇之间点的个数相差不大，对于簇之间点个数相差悬殊的聚类问题，谱聚类则不适用。

关联规则

关联分析由R. Agrawal于1993年提出，是知识发现研究的重要内容，侧重于确定数据中不同领域之间的联系，找出满足给定支持度和置信度阈值的多个域之间的依赖关系 。

关联规则（Association Rules）是无监督的机器学习方法，用于知识发现，而非预测。

基本概念

1. 项目集：设$𝐼={𝐼_1,𝐼_2,…,𝐼_𝑚}$是$𝑚$个不同项目的集合，称为项目集，也简称为项集。
   • 极大项目集: 一个项目集不是任何其它项目集的子集。
2. 事务：项目集$𝐼$的一个子集，即$𝑡𝑖={𝐼{𝑖1},𝐼{𝑖2},\dots,𝐼{𝑖𝑝}} \subset 𝐼$。
   • 事务数据库𝐷 ：事务的集合$𝐷={𝑡_1,𝑡_2,\dots,𝑡_𝑛}$
3. 项目集𝑋的支持度
   $$sup(X) = \frac{X出现次数}{事务总数|D|}$$
   • 若$𝑋\subset𝑌，则sup(𝑋)\geq sup⁡(𝑌)$
4. 最小支持度：发现关联规则要求项目集必须满足的最小支持阈值，记为 min_sup。
   • 支持度大于或等于用户指定的最小支持度的项目集。反之称为弱项集（Small Item Set）。
5. 项目集的置信度
   $$\begin{aligned} \operatorname{conf}(Y \mid X) &=\frac{X \cap Y \text { 出现次数 }}{X \text { 出现次数 }}=\frac{X \cap Y \text { 出现次数/事务总数 }|D|}{X \text { 出现次数/事务总数 }|D|} \ &=\frac{\sup (X \cap Y)}{\sup (X)} \end{aligned}$$
6. 关联规则的支持度:项目集$𝑋\cap Y$的支持度称为关联规则$𝑋\rightarrow𝑌$的支持度

Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。该算法利用由少到多，从简单到复杂的循序渐进方式，搜索数据库的项目相关关系，并利用概率的表示形成关联规则。Apriori算法的实现是基于关联分析的一种逆单调特性，这种特性也被称作Apriori属性。

• Apriori属性：在给定的事务数据库D中，任意频繁项集的子集都是频繁项目集；任意弱项目集的超集都是弱项目集。

算法步骤

1. 设定最小支持度及最小置信度。
2. 首先扫描数据库产生候选项目集，若候选项目集的支持度大于或等于最小支持度，则该候选项集合为频繁项目集。
3. 由数据库读入所有的事务数据，得到候选1_项目集合及相应的支持度数据，通过将每个1_项目集的支持度与最小支持度比较，得出频繁1_项目集合，然后将这些频繁1_项目集两两进行连接，产生候选2_项目集合。
4. 然后再次扫描数据库得到候选2_项目集合的支持度，将2_项目集的支持度与最小支持度比较，确定频繁2_项目集。类似地，利用这些频繁2_项目集产生候选3_项目集和确定频繁3_项目集，依此类推。
5. 反复扫描数据库、与最小支持度比较，产生更高项的频繁项集合，再结合产生下一级候选项集，直到不再结合产生出新的候选项集为止。

缺点

1. 由频繁项集进行自连接生成的候选频繁项集数量巨大。在验证候选频繁项集的时候需要对整个数据库进行扫描，非常耗时。
2. 由于Apriori算法需要反复对数据库进行扫描，当存在长度较大的频繁集时会增加扫描数据库次数，而当数据库容量非常大时，又会增加每次扫描数据库的时间。

基于Apriori算法的改进算法

1. 哈希方法：减少生成候选k_项目集。例如，在生成候选2_项目集时，直接对数据库进行扫描，将事务数据库中可能出现的候选2_项目集通过hash函数放入hash桶中并修改相应的桶的计数器。在读取完全部的事务数据后，可根据最小支持度检查每个hash桶的计数器，排除一部分未能达到最小支持度的候选频繁项目集，同时不会生成支持度为0的候选集。缺点：占用内存。
2. 减少事务数据的方法：基于假设：如果如果一个事务数据不能支持任一个频繁k_ 项集，那么它也必不能支持任一个频繁k+1 _项集。该方法在为确定频繁k _项集进行数据库扫描的同时，标识每一条数据是否能支持最少一个频繁k _ 项集，在数据库扫描结束后，将不能支持最少一个频繁k _ 项集的事务数据在数据库中进行删除。从而减少了算法下一次扫描数据库所需要的时间。
3. 划分方法：将一个大的事务数据库划分为若干个规模较小的事务数据库，然后在各个小事务数据库中挖掘极大频繁集。每个小事务数据库中找到的极大频繁集可称作局部极大频繁，而对于数据库D的极大频繁集相应称作全局极大频繁。由于全局极大频繁集必然在最少一个小事务数据库中是极大频繁集，因此，第二步是将全部的局部极大频繁集汇总起来形成候选全局极大频繁集，然后再一次扫描大数据集D计算每个候选全局极大频繁集的支持度，最后和全局最小支持度 进行比较，即可得到全局极大频繁集。
4. 抽样方法：抽样方法实际上是牺牲精度换取速度的方法。该方法首先从事务数据库中随机抽取一定数量的样本作为一个样本数据库S，算法将在样本数据库S中挖掘极大频繁集。所找到的极大频繁集则作为整个数据库的候选频繁集，通过一次扫描数据库，计算候选极大频繁集的支持度，即可确定整个数据库的极大频繁集。整个算法只对数据库进行一次扫描，因此在效率上会有显著的提高。然而，不可避免的风险是存在遗漏极大频繁集的可能性。一种可取的方法是适当地降低最小支持度来获得更多的候选极大频繁集，也可以通过多次抽样汇总候选极大频繁集的方法，或者采用其它的机制来检验是否存在遗漏的可能。这种方法主要用在对效率有很高要求和需要经常运算的情况。

FP-growth算法

频繁模式增长（Frequent Pattern Growth，简称为FP-Growth）。FP-Growth算法用频繁树（FP-Tree）的存储结构存储事务数据，FP-Growth是在频繁树上能够在不生成候选频繁集的情形下直接搜索全部的频繁集的一种算法。

• 频繁树是一种针对事务数据的树型存储结构，对事务数据库具有较高的压缩比。该树型结构具有一个根结点，每一条事务数据中的所有项目都按照一定的顺序存储在频繁树的结点当中，每个结点都有一个项目标号指向事务数据库的一个项目，还有一个计时器用于存储该项目出现的次数。

算法步骤

1. 从优先度最低的项目开始，读取包含该项目的全部事务数据，并构建关于该项目的条件频繁树。
2. 对于条件频繁树，根据最小支持度，进行剪枝，删除小于最小支持度的节点。
3. 对经过剪枝后的条件频繁树提取频繁集，得到所有包含该项目的频繁集。
4. 按照优先度的逆序，选择下一个项目，重复（1）-（3）的做法，找到全部包含该项目的频繁集。
5. 直到找到全部包含优秀度最高的项目的频繁集，则算法结束。

优点

1. FP-Growth算法最大的特点是无需生成候选频繁集而直接找出全部的频繁集，比Apriori一类的关联规则挖掘方法有着极大的速度优势。

决策树

决策树是一种基本的分类与回归方法.决策树模型呈树形结构。

概述

1. 决策树学习包括3个步骤：特征选择，决策树的生成和决策树的修剪。
2. 决策树学习算法以一组样本数据集为基础的一种归纳学习算法，着眼于一组无次序、无规则的样本数据中推理出决策树表示形式的分类规则。
3. 决策树可以看成一个if-then规则的集合。
4. 决策树的路径或其对应的规则结合具有一个重要的性质：互斥并且完备，每一个样本都被一条路径或规则所覆盖，而且只被一条路径或规则所覆盖。
5. 决策树学习的目的是为了产生一棵泛化能力强，即处理未见样本能力强的决策树，基本流程是遵循简单且直观的“分而治之”策略。

CLS算法

CLS算法思想：从空决策树出发，根据样本数据不断增加新分支结点，直到产生的决策树能够正确地将样本数据集分类为止。

算法步骤

1. 决策树𝑇的初始状态只含有一个树根(𝑋,𝑄),其中𝑋是全体样本数据的集合，𝑄是全体测试属性的集合。
2. 如果𝑇中所有叶结点$(𝑋^′,𝑄^′)$都有如下状态：或者𝑋^′中的样本数据都是属于同一个类，或者$𝑄^′$为空，则停止执行,学习的结果为𝑇。
3. 否则，选取一个不具有（2）所描述状态的叶结点$(𝑋^′,𝑄^′)$。
4. 对于$𝑄^′$,按照一定规则选取属性$𝑏\in𝑄^′$，设$𝑋^′$被𝑏的不同取值分为𝑚个不相交的子集$𝑋_𝑖^′,(1≤𝑖≤𝑚)$，从$(𝑋^′,𝑄^′)$伸出𝑚个分支，每个分支代表属性𝑏的一个不同取值，从而形成𝑚个新的叶结点$(𝑋_𝑖^′,𝑄^′−{𝑏})$,1≤𝑖≤𝑚。

决策树的生成过程是一个递归过程，有两种情形会导致递归返回：

• 当前结点包含的样本全属于同一个类别，无需划分。
• 当前属性集为空，无法划分。把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。
• CLS算法没有给出具体的选取测试属性的规则和标准。（不同的标准和规则演变成不同的算法，但万变不离其宗。

信息熵

1. 自信息量：接收者在收到信息符号$𝑎_𝑖$之前，对信源$𝑋$发出$𝑎_𝑖$的不确定性.定义为信息符号$𝑎_𝑖$的自信息量
   $$𝐼(𝑎_𝑖 )=−𝑙𝑜𝑔_2 𝑝(𝑎_𝑖)$$
   其中$𝑎_𝑖$是信源$𝑋$取值为$𝑎_𝑖$的概率.自信息量反映了接收$𝒂_𝒊$的不确定性，自信息量越大，不确定性越大.

2. 信息熵：自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源$𝑋$整体的不确定性，是各个自信息量的期望。
   $$ H(X) = -\sum_{i=1}^np(a_i)\times \log_2p(a_i)$$
   度量样本集合纯度最常用的一种指标，信息熵越低，纯度越高。

3. 条件熵：如果信源$𝑋$与信息$𝑌$不是相互独立的，接收者收到信息$𝑌$，那么用条件熵$𝐻(𝑋|𝑌)$来度量接收者在收到随机变量$𝑌$之后，对随机变量$𝑋$仍然存在的不确定性。$𝑋$对应信源符号$𝑎𝑖$，$Y$对应信宿符号$𝑏_𝑗$ ,$𝑝(𝑎_𝑖 |𝑏_𝑗)$为当$𝑌$为 $𝑏_𝑗$时$X$为$𝑎_𝑖$的条件概率，则有:
   $$H(X \mid Y)=\sum{j=1}^{S} p\left(b_{j}\right) H\left(X \mid b_{j}\right)=-\sum_{j=1}^{S} \sum_{i=1}^{n} p\left(a_{i}, b_{j}\right) \log {2} p\left(a{i} \mid b_{j}\right)$$
   $𝐻(𝑋│𝑎)$表示在特征$𝑎$给定的条件下对数据集$X$进行分类的不确定性。

4. 平均互信息量：用来表示信号𝑌所能提供的关于𝑋的信息量的大小
   $$I(X;Y) = H(X) - H(X|Y)$$
   决策树中的信息增益$𝐼(𝑋;𝑎)$表示由于特征$𝑎$而使得对数据集$𝑋$的分类的不确定性减少的程度（从特征$𝑎$中获得的关于数据集$𝑋$的信息量的大小）.该值越大，表示$H(X|a)$越小，这个特征分类后数据纯度高，代表该特征具有越大的分类能力。

5. 基尼系数

   假设有$𝑘$个类，样本点属于第$𝑘$类的概率为$𝑝𝑘$，则概率分布的基尼指数定义为：
   $$\operatorname{Gini}(p)=\sum{k=1}^{C} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{C} p_{k}^{2}$$
   $𝐺𝑖𝑛𝑖(𝑋)$反映了从数据集𝑋中随机地抽取两个样本，其类别标记不一致的概率.因此，$𝐺𝑖𝑛𝑖(𝑋)$越小，则数据集$𝑋$的纯度越高.

ID3算法

基于CLS算法，ID3算法根据信息增益准则选取测试属性（分裂属性）：对训练数据集（或子集）$𝑋$，计算每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征.

设样本数据集为$𝑋$ ，目的是要把它们分为$C$类.设𝑋中的样本个数$|𝑋|$ ，属于第$𝑖$类的样本数据个数是$𝑐𝑖$ ，则一个样本数据属于第𝑖类的概率$𝑃(𝐶_𝑖)\approx \frac{𝑐_𝑖}{|𝑋|}$。此时决策树对划分$𝐶$的不确定程度（即信息熵）为
$$H(X, C) = H(X) = -\sum{i=1}^{c}p(C_i) \times log_2p(C_i)$$
设属性$𝑎$有$𝑚$个不同的取值${𝑎1,𝑎_2,…,𝑎_𝑚 }$. 若选择属性$𝑎$进行测试，则条件熵为
$$\begin{aligned} H(X \mid a)&=-\sum{i=1}^{C} \sum_{j=1}^{m} p\left(C_{i}, a=a_{j}\right) \log {2} p\left(C{i} \mid a=a_{j}\right)
\&=-\sum_{j=1}^{m} p\left(a=a_{j}\right) \sum_{i=1}^{C} p\left(C_{i} \mid a=a_{j}\right) \log {2} p\left(C{i} \mid a=a_{j}\right) \end{aligned}$$
用的是对$p\left(C_{i}, a=a_{j}\right)$用条件概率公式展开了。

属性𝑎对分类提供的信息量为
$$I(X;a) = H(X) - H(X|a)$$
其中$𝐼(𝑋,𝑎)$表示选择了属性$𝑎$作为分类属性之后信息熵的下降的程度，亦即不确定性下降的程度，所以应该选择使得$𝑰(X,a)$最大的属性作为分类属性，这样得到的决策树的确定性最大。

算法步骤

1. 若$𝑋$中所有样本属于同一类$𝐶_𝑘$，则决策树$$为单结点树，将类$𝐶_𝑘$作为该结点的类标记，返回$𝑇$.
2. 若特征集$𝐴=∅$，则$T$为单结点树，将$𝑋$中样本数最大的类$𝐶_𝑘$作为该结点的类标记，返回$𝑇$.
3. 否则，计算$𝐴$中各特征对𝑋的信息增益，选择信息增益最大的特征$𝑎$.
4. 如果$𝑎$的信息增益小于阈值$𝜀$，则置$𝑇$为单结点树，将$𝑋$中样本数最大的类$𝐶_𝑘$作为该结点的类标记，返回𝑇.
5. 否则，对$𝑎$的每一可能值$𝑎_𝑖$，依$𝑎=𝑎_𝑖$将$𝑋$分割为若干个非空子集$𝑋_𝑖$,将$𝑋_𝑖$中样本数最大的类$𝐶_𝑘$作为该结点的类标记，构建子结点，由结点及其子结点构成树$𝑇$，返回$𝑇$.
6. 对第$𝑖$个子结点，以$𝑋_𝑖$为训练集，以$𝐴−𝑎$为特征集，递归地调用（1）-（5）步，得到子树$𝑇_𝑖$ ，返回$𝑇_𝑖$.

缺点

1. 信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。泛化能力弱。

C4.5算法

著名的C4.5决策树算法是ID3的改进，采用信息增益率（gain ratio）来选择最优划分属性，增加了对连续属性、属性值空缺情况的处理，对树剪枝也有了较成熟的方法。

信息增益率定义为平均互信息与获取𝑎信息所付出代价的比值：
$$ E(X,a) = \frac{I(X, a)}{H(X,a)}$$
其中$H(X, a)=-\sum_{i=1}^{m} p\left(a_{i}\right) \log {2} p\left(a{i}\right)$

信息增益率是单位代价所取得的信息量，是一种相对的信息量不确定性度量.C4.5算法以信息增益率作为测试属性的选择标准，选择𝐸(𝑋,𝑎)最大的属性𝑎作为测试属性。（本质上是多了结构方面的参考，$H(X,a)$是对属性a划分的结构的衡量）。

算法步骤与ID3类似。

与ID3算法比，C4.5算法改进地方

1. C4.5算法不仅可以处理离散属性，而且可以处理连续属性——连续属性离散化，如二分法。（对所有点计算信息增益率，选择最佳划分是的信息增益率最大的点作为划分）
   • 注意：根据连续特征分支时，各分支下的子数据集必须依旧包含该特征。因为该连续特征在接下来的树分支过程中可能依旧起着决定性作用。
2. 增加对缺失值的处理。
   • 计算信息增益率时，每个样本赋予权重。
   • 对划分属性缺失的数据，将x同时划入所有子节点，同时样本权值和属性值在对应的子节点中调整为 $\hat r_v \omega_x$，(直观来看，相当于让同一个样本以不同概率划入不同的子结点中去)。
3. 增加了剪枝算法。在C4.5中，有两种基本的剪枝策略：
   • 子树替代法剪枝是指用叶结点替代子树.仅当替代后的误差率与原始树的误差率接近时才替代.子树替代是从树的底部向树根方向进行的.
   • 子树上升法剪枝是指用一棵子树中最常用的子树来代替这棵子树.子树从当前位置上升到树中较高的结点处.对于这种替代也需要确定误差率的增加量。

CART算法

分类与回归树（classification and regression tree， CART）模型由Breiman等人在1984年提出，是一种产生二叉决策树、应用广泛的决策树学习方法.

CART算法产生二叉决策树，即每个树结点只产生两个分支. CART算法也是采用平均互信息确定测试属性. 对于取定的测试属性$𝑎$，若含有多属性值时，“最佳”分裂属性值$𝑎0$需满足条件：
$$\Phi(a_0|a) = \max_i \phi(a_i|a)$$
$$\Phi\left(a{i} \mid a\right)=2 P_{L} P_{R} \sum_{j=1}^{C}\left|P\left(C_{j} \mid t_{l}\right)-P\left(C_{j} \mid t_{R}\right)\right|$$
其中$P_L = \frac{左子树的样本数}{样本总数}$,$P(C_i|t_L) = \frac{左子树属于C_i类的样本数}{t节点样本数}$

$Φ(𝑎_𝑖 |𝑎)$主要度量在结点$𝑎$的$𝑎_𝑖$属性值引出两分支时，两分支出现的可能性以及两分支每个分类结果出现的可能性差异大小。当$\Phi(𝒂_𝒊 |𝒂)$较大时，表示两分支分类结果出现的可能性差异大，即分类不均匀，特别地当一分支完全含有同一类别结果的样本而另一分支不含有时，差异最大，这种情况越早出现，表示利用越少结点，可以越快获得分类结果。

CART算法用基尼指数选择最优特征，同时决定该特征的最优二值分裂点.
设样本集$𝑋$根据属性$𝑎$与可能取值$𝑡$的大小关系被分割为$𝑋^1$和$𝑋^2$两部分，则在属性$𝑎$的条件下，数据集𝑋的基尼指数定义为
$$\operatorname{Gini}(X, a)=\frac{\left|X^{1}\right|}{|X|} \operatorname{Gini}\left(X^{1}\right)+\frac{\left|X^{2}\right|}{|X|} \operatorname{Gini}\left(X^{2}\right)$$
其中：$\operatorname{Gini}(X_1)=1-\sum_{k=1}^{C}\left(\frac{\left|X_{k}\right|}{|X_1|}\right)^{2}$,$C$是类别数。

决策树剪枝

在决策树学习中将已生成的树进行简化的过程称为剪枝（prunning）.具体地，剪枝从已生成的树上剪掉一些子树或叶节点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型.在保证具有一定的分类正确率条件下，越简化越好.主要包括预剪枝（prepruning）和后剪枝（postprunning）.

预剪枝

预剪枝就是预先指定某一相关阈值，决策树模型有关参数在达到该阈值后停止树的生长.预剪枝方法不必生成整棵决策树，且算法相对简单，效率很高，适合解决大规模问题，但预先指定的相关阈值不易确定.一般地，多以样本集应达到的分类正确率作为阈值进行预剪枝控制，此时树型的复杂度可以通过随阈值变化而确定.

后剪枝

后剪枝就是对已生成的完整决策树以一定的标准进行剪枝，使决策树能简化并具有一定的分类正确率.
决策树后剪枝算法，就是针对未经剪枝的决策树𝑇，应用算法将𝑇的某一个或几个子树删除，得到决策树为𝑇^′ ，对多种不同剪枝结果𝑇_𝑗^′ 进行评价，找出最好的剪枝形式.其中，剪枝过程删除的子树将用叶结点代替，这个叶结点所属的类用这棵子树中大多数训练实例所属的类来代替.

后剪枝步骤

设$𝑇0$ 为原始树(未经任何剪枝和修改)，$𝑇{i+1}$是由$𝑇_𝑖$中一个或多个的子树被叶结点所代替得到的剪枝树.

1. 用$a = \frac{M}{N(L(S) - 1)}$来衡量剪枝结果。$M$是剪枝数分类错误增加数，$N$是总样本数，$L(S)$是剪枝树被去掉的叶节点数目。错误率越小越好。

决策树的特点总结

1. 决策树归纳是一种构建分类模型的非参数方法。不要求任何先验假设，不假定类和其他属性服从一定的概率分布。
2. 找到最佳的决策树是NP完全问题。许多决策树算法都采取启发式的方法指导对假设空间的搜索。例如，Hunt算法就采用了一种贪心的、自顶向下的递归划分策略建立决策树。
3. 已开发的构建决策树技术不需要昂贵的计算代价，在训练集非常大时也可以快速建立模型。此外，决策树一旦建立，样本分类非常快，最坏情况下的时间复杂度是O(w)，其中w是树的最大深度。
4. 决策树相对容易解释，特别是小型的决策树，在很多简单的数据集上，决策树的准确率也可以与其他分类算法相媲美。
5. 决策树是学习离散值函数的典型代表。
6. 冗余属性不会对决策树的准确率造成不利的影响。一个属性如果在数据中它与另一个属性是强相关的，那么它是冗余的。在两个冗余的属性中，如果已经选择其中一个作为用于划分的属性，则另一个将被忽略。然而，如果数据集中含有很多不相关的属性（即对分类任务没有用的属性），则某些不相关属性可能在树的构造过程中偶然被选中，导致决策树过于庞大。通过在预处理阶段删除不相关属性，特征选择技术能够提高决策树的准确率。
7. 子树可能在决策树中重复多次，这使得决策树过于复杂，并且可能更难解释。当决策树的每个内部结点都依赖单个属性测试条件时，就会出现这种情形。由于大多数的决策树算法都采用分治划分策略，因此在属性空间的不同部分可以使用相同的测试条件，从而导致子树重复问题。

支持向量机

概述

支持向量机（Support Vector Machine, 简记为SVM）是90年代中期 Cortes 和 Vapnik 基于统计学习理论的VC维理论和结构风险最小原理发展起来的一种机器学习方法.

SVM在很大程度上克服了传统机器学习中维数灾难、局部最小化以及过学习等难以克服的困难，在模式识别、回归预测、函数拟合等学习问题中均有广泛应用。

SVM是针对二分类问题提出的. SVM通过最大化两类样本之间距离，即最大化分类间隔以获得对测试集较小的测试误差，利用软间隔以解决近似线性可分问题，通过引入核函数使线性不可分变为高维空间的线性可分问题.

SVM有严格的理论基础，在解决小样本、非线性及高维模式识别问题中表现出特有的优势.

1. 利用大间隔（Margin）的思想实现Vapnik的结构风险最小化原则（Structural Risk Minimization，简记为SRM），在最小化训练错误的同时尽量提高学习机的泛化能力
2. 利用核函数实现线性算法的非线性化
3. 稀疏性，即少量样本（支撑向量）的系数不为零，就推广性而言，较少的支撑向量数在统计意义上对应于好的推广能力；从计算角度看，支撑向量减少了核形式的判别式的计算量
4. 可以方便的由二分类问题拓展到多分类问题，并且可以实现分类和回归算法的结合，方便于编程.

线性SVM

在样本空间中寻找一个超平面, 将不同类别的样本分开。
$$ \omega \cdot x + b = 0$$

• $\omega$ 法向量，决定超平面的方向。
• $b$位移项，决定超平面与院电的距离。
  点$x$到超平面的距离为$\frac{|\omega \cdot x + b|}{||\omega||}$，边界$\omega \cdot x + b = 1$，所以优化目标，就是$||\omega||$

最大间隔：寻找参数$\omega$和$b$使得$\gamma$最大
$$\min {\boldsymbol{\omega}, b} \frac{1}{2}|\boldsymbol{\omega}|^{2}$$
$$s.t. \quad y{i}\left(\boldsymbol{\omega} \cdot \mathbf{x}_{i}+b\right) \geq 1, i=1, \cdots, m$$
这是一个凸二次规划(convex quadratic programming)问题,若训练数据集线性可分，则可将训练数据集中的样本点正确分开的最大间隔超平面存在且唯一.

为了消除维数的影响，提高计算速度，同时为了推广到非线性分类问题，通常求解其对偶问题.下面使用拉格朗日乘子法得到上式的对偶问题.

对应的拉格朗日函数
$$L(\omega, b ; \alpha)=\frac{1}{2}|\omega|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\omega \cdot x_{i}+b\right)\right)$$
对$\omega$和$b$求极小
$$\omega=\sum_{i=1}^{m} \alpha_{i} y_{i} \mathbf{x}{i} \quad \sum{i=1}^{m} \alpha_{i} y_{i}=0$$
得
$$\min {\boldsymbol{\omega}, b} \boldsymbol{L}(\boldsymbol{\omega}, b ; \boldsymbol{\alpha})=-\frac{1}{2} \sum{i=1}^{m} \sum_{j=1}^{m} y_{i} y_{j} \alpha_{i} \alpha_{j}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right)+\sum_{j=1}^{m} \alpha_{j}$$
对$\min {\boldsymbol{\omega}, b} \boldsymbol{L}(\boldsymbol{\omega}, b ; \boldsymbol{\alpha})$中的$\alpha$求极大，可得原问题的对偶问题。
$$\max _{\alpha}-\frac{1}{2} \sum{i=1}^{m} \sum_{j=1}^{m} y_{i} y_{j} \alpha_{i} \alpha_{j}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right)+\sum_{j=1}^{m} \alpha_{j}$$
$$s.t. \sum_{i=1}^{m} \alpha_{i} y_{i}=0$$
$$\alpha_{i} \geq 0, \quad i=1, \cdots, m$$
要满足Karush-Kuhn-Tucker(KKT)条件:
$$\nabla_{\omega} L(\omega, b ; \alpha)=0$$
$$\nabla_{b} L(\omega, b ; \alpha)=0$$
$$\alpha_{i} \cdot c_{i}(\omega, b)=0, \quad i=1, \cdots, m$$
$$c_{i}(\boldsymbol{\omega}, b) \leq 0 \quad (原问题的不等式约束)$$
$$\alpha_{i} \geq 0$$
最终化为一个二次规划问题。
$$\max {\boldsymbol{\alpha}}-\frac{1}{2} \sum{i=1}^{m} \sum_{j=1}^{m} y_{i} y_{j} \alpha_{i} \alpha_{j}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right)+\sum_{j=1}^{m} \alpha_{j}$$
$$s.t. \quad \sum_{i=1}^{m} \alpha_{i} y_{i}=0$$
$$\alpha_{i} \geq 0, \quad i=1, \cdots, m$$
$$-\sum_{i=1}^{m} \alpha_{i} y_{i}=0$$
$$y_{i}\left(\omega \cdot \mathbf{x}{i}+b\right)-1 \geq 0, \quad i=1, \cdots, m$$
$$\alpha{i}\left(y_{i}\left(\omega \cdot \mathbf{x}_{i}+b\right)-1\right)=0, \quad i=1, \cdots, m$$

• 二次规划问题规模正比于训练样本数。
• 每一个$\alpha_i$与一个训练样本对应.
• 若$\alpha_i \neq 0$,则$𝑥_𝑖$就称为支持向量
• 若$\alpha^∗=(\alpha_1^∗,\dots,\alpha_𝑚^∗)$为对偶问题的最优解，则法向量只由支持向量组成.
• $\omega^∗$只由支持向量组成,而且分布在超平面$(𝛚⋅𝐱)+𝑏=±1$上.
• $b$的求解：$b^{}=y_{i}-\sum_{\mathbf{x}{j} \in S V{S}} y_{j} \alpha_{j}^{}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right), \forall i \in\left{i \mid \alpha_{i}^{*}>0\right}$

软间隔线性SVM

实际问题中训练样本往往不是严格线性可分的，两超平面之间的区域也存在少量样本.

解决方法：允许支持向量机在一些样本上出错——软间隔

基本想法：最大化间隔的同时, 让不满足约束的样本应尽可能少。

• hinge损失函数：0/1损失函数的上界，连续，凸。
  $$hinge(z) = \max (0, 1-z)$$

加入对错误分类项的惩罚，问题转变成：
$$\min {\boldsymbol{\omega}, b} \frac{1}{2}|\boldsymbol{\omega}|^{2}+C \cdot \sum{i=1}^{m} \max \left(0,1-y_{i}\left(\boldsymbol{\omega} \cdot \mathbf{x}{i}+b\right)\right)$$
引入松弛变量$\xi{i}$
$$\min {\mathbf{\omega}, b} \frac{1}{2}|\boldsymbol{\omega}|^{2}+C \cdot \sum{i=1}^{m} \xi_{i}$$
$$s.t. \quad y_{i}\left(\left(\boldsymbol{\omega} \cdot \mathbf{x}{i}\right)+b\right) \geq 1-\xi{i}, \quad i=1, \cdots, m$$
$$\quad \xi_{i} \geq 0, \quad i=1,2, \cdots, m$$

软间隔线性SVM的求解

也是用拉格朗日乘子法求对偶。
$$L(\mathbf{w}, b, \xi ; \mathbf{\alpha}, \boldsymbol{\beta})=\frac{1}{2}|\boldsymbol{\omega}|^{2}+C \sum_{i=1}^{m} \xi_{i}+\sum_{i=1}^{m} \alpha_{i}\left(1-\xi_{i}-y_{i}\left(\boldsymbol{\omega} \cdot \mathbf{x}{i}+b\right)\right)-\sum{i=1}^{m} \beta_{i} \xi_{i}$$
令$L(\mathbf{w}, b, \xi ; \mathbf{\alpha}, \boldsymbol{\beta})$对$\omega, b, \xi$的偏导为0。
$$\omega=\sum_{i=1}^{m} \alpha_{i} y_{i} \mathbf{x}{i}$$
$$\sum{i=1}^{m} \alpha_{i} y_{i}=0$$
$$C-\alpha_{i}-\beta_{i}=0, i=1,2, \cdots, m$$
把三个式子代回原式：
$$\min {\boldsymbol{\omega}, b, \xi} \boldsymbol{L}(\boldsymbol{\omega}, b, \xi ; \boldsymbol{\alpha}, \beta)=-\frac{1}{2} \sum{i=1}^{m} \sum_{j=1}^{m} y_{i} y_{j} \alpha_{i} \alpha_{j}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right)+\sum_{j=1}^{m} \alpha_{j}$$
对$\alpha$求极大，则是对偶问题：
$$\max {\alpha} \sum{j=1}^{m} \alpha_{j}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} y_{i} y_{j} \alpha_{i} \alpha_{j}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right)$$
$$s.t. \sum_{i=1}^{m} \alpha_{i} y_{i}=0$$
$$\alpha_{i} \geq 0, \quad i=1, \cdots, m$$
$$C-\alpha_{i}-\beta_{i}=0, \quad i=1, \cdots, m$$
$$\beta_{i} \geq 0, i=1,2, \cdots, m$$
最后三条约束可以合并成：
$$0 \leq \alpha_i \leq C, i=1,2, \cdots, m$$
还需要满足KKT条件。
$$\left{\begin{array}{c}\alpha_{i} \geq 0, \beta_{i} \geq 0 \ y_{i}\left(\omega \cdot \mathbf{x}{i}+b\right) \geq 1-\xi{i} \ \alpha_{i}\left(y_{i}\left(\omega \cdot \mathbf{x}{i}+b\right)-1+\xi{i}\right)=0 \ \xi_{i} \geq 0 \ \beta_{i} \xi_{i}=0, i=1,2, \cdots, m\end{array}\right.$$

• 对应$\alpha_i>0$的样本点称为支持向量
• 软间隔的支持向量或者在间隔边界上，或者在间隔边界与分类超平面之间，或者在分类超平面误分一侧.
• 如果$0<\alpha_i<𝐶$，那么$\beta_i=𝐶−\alpha_i>0$,从而$\xi_i=0$,对应的支持向量恰好落在间隔边界上.
• 如果$\alpha_i=𝐶$，则有$\beta_i=0$
  1. 若$0<\xi_i<1$，则支持向量在间隔边界与分类超平面之间.
  2. 若$\xi_i=1$，则支持向量在分类超平面上.
  3. 若$\xi_i>1$，则支持向量位于分类超平面误分一侧.

最优解：
$$\left{\begin{array}{l}\boldsymbol{\omega}^{}=\sum_{\mathbf{x}{i} \in S V{s}} \alpha_{i}^{} y_{i} \mathbf{x}{i} \ b^{*}=y{j}-\sum_{\mathbf{x}{i} \in S V{S}} y_{i} \alpha_{i}^{}\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right), \forall j \in\left{j \mid 0<\alpha_{j}^{}<C\right}\end{array}\right.$$

非线性SVM

当数据非线性可分时，即能正确划分训练集的超平面已经不存在了，只能通过超曲面𝐺(𝑋)进行划分.当我们通过非线性映射函数Φ把训练集从输入空间映射到特征空间，样本点在特征空间的映像表现出线性可分的趋势。

• 如果原始空间是有限维，那么一定存在一个高维特征空间使样本线性可分。

核函数

设$X$是输入空间（欧式空间），$𝐻$是特征空间（希尔伯特空间）,$\Phi : X \rightarrow H$,核函数$K(x,z)$满足：
$$ K(x,z)=\Phi(x) \cdot \Phi(z)$$
避免了直接显示的定义$\Phi$

• 对给定的核$𝐾(𝑥,𝑧)$，特征空间$𝐻$和映射函数$\Phi$的取法并不唯一.
• K的核矩阵要求半正定。任何一个核函数都隐式地定义了一个称为再生核希尔伯特空间的特征空间.

常用核函数

1. 线性核：$K(x,y) = x^Ty$
2. 多项式核:$k(X,y) = (x^Ty)^d \quad d\geq1$
3. 高斯核: $k(x,y) = exp(-\frac{||x-y||^2}{2\sigma^2}) \quad \sigma > 0$为高斯核的带宽（带宽越大，越平滑，bias增大，variance减少）。
4. 拉普拉斯核：$k(x,y) = exp(-\frac{||x-y||}{\sigma}) \quad \sigma > 0$
5. sigmoid核：$k(x,y) = \tanh(\beta x^Ty+\theta),\quad \beta>0, \theta < 0$

非线性硬间隔SVM求解

假设样本在特征空间是线性可分的，则存在超平面
$$ f(x) = \omega \cdot \phi(x)+b = 0$$
类似可得特征空间硬间隔SVM模型：
$$\min {\boldsymbol{\omega}, b} \frac{1}{2}|\boldsymbol{\omega}|^{2}$$
$$s.t. \quad y{i}\left(\boldsymbol{\omega} \cdot \mathbf{\phi(x)}{i}+b\right) \geq 1, i=1, \cdots, m$$
其对偶问题为：
$$\max _{\alpha}-\frac{1}{2} \sum{i=1}^{m} \sum_{j=1}^{m} y_{i} y_{j} \alpha_{i} \alpha_{j}K\left(\mathbf{x}{i} \cdot \mathbf{x}{j}\right)+\sum_{j=1}^{m} \alpha_{j}$$
$$s.t. \sum_{i=1}^{m} \alpha_{i} y_{i}=0$$
$$\alpha_{i} \geq 0, \quad i=1, \cdots, m$$
最优解
$$\left{\begin{array}{l}\boldsymbol{\omega}^{}=\sum_{i=1}^{m} \alpha_{i}^{} y_{i} \phi\left(\mathbf{x}{i}\right) \ b^{*}=y{j}-\sum_{i=1}^{m} y_{i} \alpha_{i}^{} K\left(\mathbf{x}{i}, \mathbf{x}{j}\right), \forall j \in\left{j \mid \alpha_{j}^{}>0\right}\end{array}\right.$$

非线性硬间隔SVM求解

类似，将线性核换成核函数即可。\

svm与逻辑回归

• hinge损失换成对数损失，则于逻辑回归模型接近。
• 逻辑回归
  $$\min_\beta \frac{1}{2} ||\beta||^2 + \sum_i [-y(\beta \cdot x_i)+ln(1+e^{\beta x_i})]$$
• 逻辑回归通过输出预测概率后根据阈值进行判断类别，SVM则直接输出分割超平面，然后使用0/1函数对样本进行分类，不能直接输出概率值。
• 逻辑回归可以使用多阈值然后进行多分类，SVM则需要进行推广
• SVM的解只依赖支持向量，依赖的训练样本数较小，解具有稀疏性，而对数损失函数是光滑的单调递减函数，不能导出类似支持向量的概念，因此逻辑回归的解依赖于更多的训练样本，其预测开销更大

支持向量回归

特点: 允许模型输出和实际输出间存在$2\epsilon$的偏差,落入中间$2\epsilon$间隔带的样本不计算损失, 从而使得模型获得稀疏性.

损失函数
$$\ell_{\epsilon}(z)=\left{\begin{array}{ll}0 & \text { if }|z| \leq \epsilon \ |z|-\epsilon & \text { otherwise }\end{array}\right.$$

原始问题(允许误差$\epsilon$）：
$$\begin{aligned} \min {\boldsymbol{w}, b, \xi{i}, \hat{\xi}{i}} & \frac{1}{2}|\boldsymbol{w}|^{2}+C \sum{i=1}^{m}\left(\xi_{i}+\hat{\xi}{i}\right) \ \text { s.t. } & y{i}-\boldsymbol{w}^{\top} \phi\left(\boldsymbol{x}{i}\right)-b \leq \epsilon+\xi{i} \ & y_{i}-\boldsymbol{w}^{\top} \phi\left(\boldsymbol{x}{i}\right)-b \geq-\epsilon-\hat{\xi}{i} \ & \xi_{i} \geq 0, \hat{\xi}{i} \geq 0, i=1,2, \ldots, m \end{aligned}$$
对偶问题：
$$\begin{array}{ll}\min _{\boldsymbol{\alpha}, \hat{\alpha}} & \frac{1}{2} \sum{i=1}^{m} \sum_{j=1}^{m}\left(\alpha_{i}-\hat{\alpha}{i}\right)\left(\alpha{j}-\hat{\alpha}{j}\right) \kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)+\sum{i=1}^{m}\left(\alpha_{i}\left(\epsilon-y_{i}\right)+\hat{\alpha}{i}\left(\epsilon+y{i}\right)\right) \ \text { s.t. } & \sum_{i=1}^{m}\left(\alpha_{i}-\hat{\alpha}{i}\right)=0 \ & 0 \leq \alpha{i} \leq C, 0 \leq \hat{\alpha}{i} \leq C\end{array}$$
预测
$$f(\boldsymbol{x})=\boldsymbol{w}^{\top} \phi(\boldsymbol{x})+b=\sum{i=1}^{m}\left(\hat{\alpha}{i}-\alpha{i}\right) y_{i} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}\right)+b$$

多分类问题

转化为二分类问题，常见的有一对其余策略和一对一策略

一对其余策略

把每个类与其余类建立二分类器。

缺点

1. 存在不可分区域，改进：用$i^* = max_{i\in{1,\dots,c}}g_i(x)$

一对一策略

一对一策略共需要构造$𝑐(𝑐−1)/2$个二分类最优超平面。然后采用投票法。

SVM对偶问题的求解

SMO算法

SMO算法是一种启发式算法，基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就找到了.因为KKT条件是该最优化问题的充分必要条件.否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题.这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小.重要的是，这时子问题可以通过解析法求解,大大提高算法的计算速度.

子问题有两个变量，仅优化两个参数的过程能做到非常高效. 如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的.

如何选取一对变量

1. $\alpha_i$ 和$\alpha_j$有一个不满足KKT条件时，目标函数就会在迭代后减少. KKT条件违反的程度越大，则变量更新后可能导致的目标函数值减幅越大. 于是，SMO算法先选取违背KKT条件程度最大的变量.
2. 第二个变量应该选一个使目标函数值减少最快的变量——复杂度过高，启发式：使选取的两变量所对应样本之间的间隔最大.这样的两个变量有很大的差别，对它们进行更新会带给目标函数更大的变化.

贝叶斯网络

建模的出发点不是为了对未知数据作预测，而是为了弄清楚并模拟数据产生的原理和机制。

• 判别式模型（discriminative models）（直接模型）：模型的出发点是直接考察自变量到被预测量的关系：给定 𝑥，通过直接建模𝒑(𝑦|𝒙), 来预测𝑦
  逻辑回归，决策树，支持向量机，BP神经网络
• 生成式模型（generative models）（间接模型）：关心数据{𝑥,𝑦}是如何产生的。建模对象是𝒑(𝑦)和𝒑(𝒙|𝑦)。最终通过$p(y \mid x)=\frac{p(y) p(\boldsymbol{x} \mid y)}{p(\boldsymbol{x})} \propto p(y) p(\boldsymbol{x} \mid y)$实现对y的预测。

生成式模型是间接建模，建模理念非常诱人：它不但能根据特征预测结果，还能“理解”数据是如何产生的，并以此为基础“创造”数据，这才是真正意义上的人工智能

概述

1. 贝叶斯网络是用来表示变量之间连接关系概率的图形模式，它提供了一种自然的表示因果信息的方法，用来发现数据间潜在关系。
2. 贝叶斯网络建立在贝叶斯理论之上，具有稳固的数学理论基础。它刻画了信任度与证据的一致性以及信任度随证据而变化的增量学习特性，以概率测度的权重来描述数据间的相关性。
3. 贝叶斯方法以其独特的不确定性知识表示形式、丰富的概率表达能力、综合先验知识的增量学习特性成为当前数据挖掘众多方法中最为引人注目的焦点之一。
4. 贝叶斯分析方法的特点是用概率去表示所有形式的不确定性，学习或其它形式的推理都用概率规则来实现。
5. 贝叶斯学习的结果表示为随机变量的概率分布，它可以理解为我们对不同可能性的信任程度。
6. 贝叶斯定理将事件的先验概率与后验概率联系起来。
7. 先验概率是指根据历史的资料或主观判断所确定的各事件发生的概率，该类概率没能经过实验证实，属于检验前的概率，所以称之为先验概率。先验概率一般分为两类：一是客观先验概率，是指利用过去的历史资料计算得到的概率；二是主观先验概率，是指在无历史资料或历史资料不全的时候，只能凭借人们的主观经验来判断取得的概率。
8. 后验概率：一般是指利用贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率进行修正后得到的更符合实际的概率

原理

假设随机向量𝒙,𝜃的联合分布密度是𝑝(𝒙,𝜃)，它们的边际密度分布为𝑝(𝒙)、𝑝(𝜃)。一般情况下设𝒙是观测向量，𝜃是未知参数向量，通过观测向量获得未知参数向量的估计，贝叶斯定理记作：
$$p(\theta \mid \boldsymbol{x})=\frac{p(\theta) p(\boldsymbol{x} \mid \theta)}{p(\boldsymbol{x})}=\frac{p(\theta) p(\boldsymbol{x} \mid \theta)}{\int p(\theta) p(\boldsymbol{x} \mid \theta) d \theta}$$

贝叶斯方法对未知参数向量估计的一般过程

1. 将未知参数看成随机向量
2. 根据以往对参数𝜃的知识，确定先验分布𝑝(𝜃)，若先验未知，则采用均匀分布（贝叶斯假设）。
3. 计算后验分布密度，做出对未知参数的推断

贝叶斯网络的知识推理模式

1. 因果推理 由原因推知结论又可称为至顶向下的推理（Causal or Top-Down Inference），目的是由原因推导出结果。已知一定的原因（事实），使用贝叶斯网络的推理计算，求出在该原因的情况下结果发生的概率
2. 诊断推理 由结论推知原因又可称为至底向上的推理（Diagnostic or Bottom-Up Inference），目的是在已知结果时，找出产生该结果的原因。已知发生了某些结果，根据贝叶斯网络的推理计算，得到造成该结果发生的原因和发生的概率。
3. 支持推理 支持推理可以提供解释以支持所发生的现象（Explaining Away），目的是对原因之间的相互影响进行分析。

贝叶斯网络定义

1. 𝐵=<𝐺,𝛩>表示一贝叶斯网络，其中𝐺是一个有向无环图，其顶点对应于有限集𝑋中的随机变量$𝑋_1,𝑋_2,⋯,𝑋_𝑛，$其弧代表一个函数依赖关系。
2. 如果有一条弧从$𝑋_𝑖$到$𝑋_𝑗$，则$𝑋_𝑖$是$𝑋_𝑗$的双亲或直接前驱，$𝑋_𝑗$是$𝑋_𝑖$的后继。变量$𝑋_𝑗$所有双亲变量用集合$𝑃𝑎(𝑋_𝑗)$表示，并用$𝑝𝑎(𝑋_𝑗)$表示$𝑃𝑎(𝑋_𝑗)$的一个取值。
3. 一旦给定其双亲，每个变量独立于该节点的非后继
4. 𝛩表示用于量化网络的一组参数，通常是条件概率。

贝叶斯网络建立的主要步骤

1. 贝叶斯网络建立主要划分为两个相继环节：结构学习与参数学习
2. 结构学习是利用一定的方法建立贝叶斯网络结构的过程，该过程决定了各个变量之间的关系，是贝叶斯网络分类算法的最重要的步骤。
3. 参数学习是量化网络的过程，它在网络结构已知的情况下计算各节点𝑋_𝑖的条件概率。

贝叶斯网络的结构学习

贝叶斯网络结构学习算法主要分析节点依赖关系与节点连接关系。

基于评分——搜索的贝叶斯网络结构学习

1. 将学习问题看作为数据集寻找最合适的结构，这类算法从没有边的图形开始，利用搜索方法将边加入到图形中。利用测试方法（如贝叶斯评分、基于熵的评分、最小描述长度等）检验是否新的结构优于旧的结构。
2. 当变量数较大时，贝叶斯网络结构空间相当大，这会使得搜索用时较长且结果较差。

基于信息论的贝叶斯网络结构学习

学习贝叶斯网络的算法主要根据变量之间的依赖性建立贝叶斯网络结构。
对应变量的网络节点为$𝑋𝑖$和$𝑋_𝑗$，互信息为：
$$I\left(X{i}, X_{j}\right)=\sum_{X_{i}, X_{j}} P\left(X_{i}, X_{j}\right) \log {2} \frac{P\left(X{i}, X_{j}\right)}{P\left(X_{i}\right) P\left(X_{j}\right)}$$

贝叶斯网络的参数学习

1. 贝叶斯网络的参数学习实质上是在已知网络结构的条件下，通过样本学习获取每个节点的概率分布表。
2. 初始的贝叶斯网络的概率分布表一般由专家根据先验知识指定，称为网络的先验参数。这样的先验参数可能导致学习结果与观测数据产生较大的偏差。
3. 针对完整数据与不完整数据，贝叶斯网络的参数学习也分为两种不同情况。
4. 先验分布的选取原则：共轭分布，杰弗莱原则，最大熵原则等。

基于完整数据的贝叶斯网络参数学习

1. 对完备数据集D进行条件概率学习的目标是找到能以概率形式𝑃(𝑥|𝜃)概括样本D的参数𝜃。
2. 参数学习一般要首先指定一定的概率分布族，然后利用一定的策略估计这些分布的参数。
3. 通常有两种学习方法：最大似然估计(MLE)方法和贝叶斯方法。这两种方法都是以下面的独立同分布假设为前提的
   • 参数全局独立性：给定网络结构𝐵，有$P\left(\theta_{s} \mid B\right)=\prod_{i=1}^{n} P\left(\theta_{i} \mid B\right)$
   • 参数局部独立性：给定网络结构𝐵，有$P\left(\theta_{i} \mid B\right)=\prod_{j=1}^{q_i} P\left(\theta_{ij} \mid B\right)$
4. 贝叶斯算法
   网络参数是概率$𝜃=(𝜃1,𝜃_2,⋯,𝜃_𝑁)$，其中$𝜃_𝑗>0$，$\sum{j=1}^N \theta_j = 1$

基于不完整数据的贝叶斯网络参数学习

Gibbs抽样算法

1. Gibbs抽样算法是一种随机方法，能近似得出变量的初始概率分布。它把含有不完全数据样本的每一缺项当做待估参数，通过对未知参数后验分布的一系列随机抽样过程，计算参数的后验均值的经验估计。
2. 算法定义为：按照候选假设集合H上的后验概率分布，从H中随机选择假设h，用h来预言下一个实例的分类。
3. 算法分为三个步骤：首先，随机地对所有未观测变量的状态进行初始化，由此可以得出一个完整的数据集；然后，基于这个完整的数据集，对条件概率表CPT进行更新；第三，基于更新的CPT参数，用Gibbs抽样算法对所有丢失的数据进行抽样，又得到一个完整的数据集。直到CPT达到稳定时，完成学习过程。

   EM算法

4. EM 算法可用于变量的值从来没有被直接观察到的情形，只要这些变量所遵循的概率分布的一般形式已知即可。
5. 两个步骤：期望(Expectation Step)和最大化(Maximization Step)。
6. E步：用现有参数来估计未观察参数；M步：利用估计参数进行参数的ML/MAP估计，将估计值赋给参数。重复EM步骤，直到收敛到局部最优解。

朴素贝叶斯

贝叶斯决策论

在分类问题情况下，在所有相关概率都已知的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。

假设有N种可能的类别标记，即$y={c_1,\dots,c_N}$, $\lambda_{ij}$将一个真实标记为$c_j$的样本误分类为$c_i$所产生的损失。基于后验概率$P(c_i|x)$ 可获得将样本$x$分类为$c_i$所产生的期望损失（expected loss），即在样本上的“条件风险”（conditional risk）
$$R\left(c_{i} \mid \mathbf{x}\right)=\sum_{j=1}^{N} \lambda_{i j} P\left(c_{j} \mid \mathbf{x}\right)$$

贝叶斯判定准则

为最小化总体风险，只需在每个样本上选择那个能使条件风险$R(c|x)$最小的类别标记，即
$$h^{}(x)=\underset{c \in y}{\operatorname{argmin}} R(c \mid x)$$
此时，被称为贝叶斯最优分类器(Bayes optimal classifier)，与之对应的总体风险 $h^{}(x)$称为贝叶斯风险 (Bayes risk)。$1-h^{*}(x)$反映了分类起所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限。

当误判损失$\lambda_{ij}$为：
$$\lambda_{i, j}\left{\begin{array}{l}0, \quad \text { if } i=j \ 1, \quad \text { otherwise }\end{array}\right.$$
则贝叶斯最优分类器为
$$h^{*}(x)=\underset{c \in y}{\operatorname{argmax}} P(c \mid x)$$

目标变为估计后验概率$P(c|x)$
$$P(c|x) = \frac{P(c)P(x|c)}{P(x)}$$

朴素贝叶斯网络

1. 根据变量关系要求的条件不同，贝叶斯网络建立一般分为有约束贝叶斯网络和无约束贝叶斯网络。
2. 有约束贝叶斯网络要求变量对应的节点是相互独立或有少量的节点是不独立的。
3. 无约束贝叶斯网络是允许变量节点是不独立的
4. 朴素贝叶斯网络是典型的有约束贝叶斯网络。
5. 结构简单——只有两层结构
6. 推理复杂性与网络节点个数呈线性关系
7. 朴素贝叶斯法实现简单，学习与预测的效率很高，是一种常用的方法。
8. 朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。
9. 朴素贝叶斯分类器的假设：即给定类变量(网络中的根节点)的状态，每个属性变量（网络中每个叶节点）与其余的属性变量是独立的。
10. 对于给定的训练数据集，首先基于特征条件独立假设学习输入/输出的联合概率分布；然后基于此模型，对给定的输入𝒙 ，利用贝叶斯定理求出后验概率最大的输出𝑦 。

网络原理

设输入空间$\chi \subseteq R^n$，输出空间为类标记集合$\Gamma={𝐶_1,…,𝐶_𝑚}$。输入为特征向量$𝒙\in\chi$，输出为类标记$𝑦\in\Gamma$。 $𝑋$是定义在输入空间$\chi$的随机向量，$𝑌$是定义在输出空间$\Gamma$上的随机变量。 $𝑃(𝑋,𝑌)$$X$和$𝑌$的联合概率分布。

训练数据集$T={(𝒙_1,𝑦_1),(𝒙_𝟐,𝑦_2 ),⋯,(𝒙_𝑡,𝑦_𝑡)}$由$𝑃(𝑋,𝑌)$独立同分布产生。

朴素贝叶斯法通过训练数据集学习联合概率分布$𝑃(𝑋,𝑌)$。
包括

• 先验概率分布：$P(Y=C_k)$
• 条件概率分布(这会产生指数阶参数，所以需要独立性假设）：$P\left(X=\boldsymbol{x} \mid Y=C_{k}\right)=P\left(A_{1}=x_{1}, \ldots, A_{n}=x_{n} \mid Y=C_{k}\right)$

朴素贝叶斯法对条件概率分布作了条件独立性的假设：
$$\begin{aligned} P\left(X=\boldsymbol{x} \mid Y=C_{k}\right) &=P\left(A_{1}=x_{1}, \ldots, A_{n}=x_{n} \mid Y=C_{k}\right) \ &=\prod_{j=1}^{n} P\left(A_{j}=x_{j} \mid Y=C_{k}\right) \end{aligned}$$
说用于分类的特征在类确定的条件下都是条件独立的——简单，但会牺牲一定的分类精度

给定一个未知的数据样本$𝒙=(𝑥_1,𝑥_2,⋯,𝑥_𝑛 )$，朴素贝叶斯分类法将预测$𝒙$属于具有最高后验概率的类。

使用极大似然进行参数估计

$$P\left(C_{i} * \mid x\right) \propto \max {1 \leq i \leq m} P\left(C{i}\right) \prod_{j=1}^{n} P\left(x_{j} \mid C_{i}\right)$$

• $P(C_i) = t_i / t$

参数估计修正，拉普拉斯平滑

• $P(C_i) = (t_i + 1) / (t + T)$
• 拉普拉斯修正避免了因训练样本不充分而导致概率估值为零的问题，并且在训练集变大时，修正过程引入的先验的影响也会逐渐变得可忽略，使得估计值趋于实际概率值。

朴素贝叶斯学习步骤

1. 先计算先验概率以及条件概率
2. 对于给定的测试样本，计算似然函数
3. 确定测试样本的类别

朴素贝叶斯优点

网络结构非常简单，建立网络时间少，参数学习与分类过程简便。

朴素贝叶斯缺点

由于类条件独立假设割断了属性间的联系，使得其网络结构不合理，导致了朴素贝叶斯网络分类器的分类精度相对较低。

神经网络

概述

1. 常用非线性激活函数
   • sigmoid
   • tanh
   • relu
2. 常见的神经网络结构
   • 层次型
   • 互联型（图形）

单层感知机

1. 损失函数：
   $f(x)=\left{\begin{array}{ll}1, & x \geq 0 \ 0, & x<0\end{array}\right.$
2. 收敛性：对于线性可分数据集，单层感知机的学习过程是收敛的；否则感知机的学习过程将会发生震荡.（异或处理不了）
3. 事实上, 与、或、非问题是线性可分的, 因此感知机学习过程能够求得适当的权值向量. 而异或问题不是线性可分的, 感知机学习不能求得合适解。

多层感知机

输出层与输入层之间的一层神经元, 被称之为隐层或隐含层（非线性）, 隐含层和输出层神经元都是具有激活函数的功能神经元

多层前馈神经网络

1. 定义：每层神经元与下一层神经元全互联, 神经元之间不存在同层连接也不存在跨层连接
2. 前馈：输入层接受外界输入, 隐含层与输出层神经元对信号进行加工, 最终结果由输出层神经元输出
3. 学习：根据训练数据来调整神经元之间的“连接权”以及每个功能神经元的“阈值”
4. 网络中每个神经元（除了输入层）包含了一个可微的非线性激活函数；
5. 隐藏层的使用使得学习过程变得更困难。目前训练多层感知机的一个流行方法是反向传播（error backpropagation，BP）算法。
6. BP算法是迄今最成功的的神经网络学习算法。现实任务中使用神经网络时，大多是在使用BP算法进行训练。BP算法不仅可用于多层前馈神经网络，还可用于其他类型的网络，如递归神经网络。但BP网络一般指的用BP算法训练多层前馈神经网络。
7. BP神经网络，是一种多层前馈型、按梯度算法使期望输出与实际输出的误差沿反向传播修正各连接权的神经网络模型。
8. BP神经网络按有监督的方式进行学习，给定学习样本，利用误差反向传播不断修正网络参数，网络对输入模式响应的正确率不断提高。

BP训练原理

一个三层MLP，$n \times l \times q$

给定样本
$$\left{\left(x_{1}^{(k)}, x_{2}^{(k)}, \ldots x_{n}^{(k)}, y_{1}^{(k)}, y_{2}^{(k)}, \ldots y_{q}^{(k)}\right) \mid k=1,2, \ldots m\right}$$
隐藏层第$i$个神经元输入$\alpha_i = \sum_{j=1}^nw_{ij}x_j$输出$b_i$，激活函数选sigmoid
$$b_{i}=f\left(\sum_{j=1}^{n} w_{i j} x_{j}-\theta_{i}\right)=f\left(\alpha_{i}-\theta_{i}\right), i=1,2, \cdots, l$$
输出层第h个神经元收到的输入$\beta_k = \sum_{i=1}^lv_{hi}b_i$输出为
$$O_{h}=f\left(\sum_{i=1}^{l} v_{h i} b_{i}-r_{h}\right)=f\left(\beta_{h}-r_{h}\right), h=1,2, \cdots, q$$
第k个样本的误差计算公式
$$E_{k}=\frac{1}{2} \sum_{j=1}^{q}\left(y_{j}^{(k)}-O_{j}^{(k)}\right)^{2}$$
通过梯度下降，更新$v$
$$\Delta v_{h i}=-\alpha \frac{\partial E_{k}}{\partial v_{h i}}=-\alpha\left(\frac{\partial E_{k}}{\partial O_{h}^{(k)}} \frac{\partial O_{h}^{(k)}}{\partial \beta_{h}} \frac{\partial \beta_{h}}{\partial v_{h i}}\right)=\alpha h_{h} b_{i}$$
其中
$$\frac{\partial E_{k}}{\partial O_{h}^{(k)}}=-\left(y_{h}^{(k)}-O_{h}^{(k)}\right) \quad \frac{\partial \beta_{h}}{\partial v_{h i}}=b_{i} \quad h_{h}=-\frac{\partial E_{k}}{\partial O_{h}^{(k)}} \frac{\partial O_{h}^{(k)}}{\partial \beta_{h}}=\left(y_{h}^{(k)}-O_{h}^{(k)}\right) O_{h}^{(k)}\left(1-O_{h}^{(k)}\right)$$
$$\frac{\partial O_{h}^{(k)}}{\partial \beta_{h}}=f^{\prime}\left(\beta_{h}-r_{h}\right)=f\left(\beta_{h}-r_{h}\right)\left(1-f\left(\beta_{h}-r_{h}\right)\right)=O_{h}^{(k)}\left(1-O_{h}^{(k)}\right)$$
更新$w$
$$\Delta w_{i j}=-\beta \frac{\partial E_{k}}{\partial w_{i j}}=-\beta\left(\frac{\partial E_{k}}{\partial b_{i}} \frac{\partial b_{i}}{\partial \alpha_{i}} \frac{\partial \alpha_{i}}{\partial w_{i j}}\right)=\beta e_{i} x_{j}$$
其中
$$\frac{\partial E_{k}}{\partial b_{i}}=\sum_{h=1}^{q} \frac{\partial E_{k}}{\partial \beta_{h}} \frac{\partial \beta_{h}}{\partial b_{i}}=-\sum_{h=1}^{q}\left(y_{h}^{(k)}-O_{h}^{(k)}\right) O_{h}^{(k)}\left(1-O_{h}^{(k)}\right) v_{h i}=-\sum_{h=1}^{q} h_{h} v_{h i}$$
$$\frac{\partial b_{i}}{\partial \alpha_{i}}=f^{\prime}\left(\alpha_{i}-\theta_{i}\right)=f\left(\alpha_{i}-\theta_{i}\right)\left(1-f\left(\alpha_{i}-\theta_{i}\right)\right)=b_{i}\left(1-b_{i}\right)$$
$$\frac{\partial \alpha_{i}}{\partial w_{i j}}=x_{j} \quad e_{i}=\sum_{h=1}^{q} h_{h} v_{h i} b_{i}\left(1-b_{i}\right)$$
类似可得$\Delta r_h, \Delta \theta_i$
$$ \Delta r_h = -\alpha h_h, \quad \Delta \theta_i = -\beta e_i$$

多层前馈网络局限

1. 神经网络由于强大的表示能力, 经常遭遇过拟合. 表现为：训练误差持续降低, 但测试误差却可能上升
2. 早停：在训练过程中, 若训练误差降低, 但验证误差升高, 则停止训练
3. 正则化：在误差目标函数中增加一项描述网络复杂程度的部分, 例如连接权值与阈值的平方和.

BP神经网络的优点

1. 非线性映射能力：两层的前馈神经网络就能够以任意精度逼近任何非线性连续函数，即BP神经网络具有较强的非线性映射能力.
2. 自学习和自适应能力：BP神经网络在训练时，能够通过学习自动提取、输出数据间的“合理规则”，并自适应的将学习内容记忆于网络的权重中.即BP神经网络具有高度自学习和自适应的能力.
3. 泛化能力： BP神经网络具有将学习成果应用于新知识的能力.
4. 容错能力：BP神经网络在其局部的或者部分的神经元受到破坏后还是可以正常工作的，具有一定的容错能力.

BP神经网络的缺点

1. 局部极小化问题：BP神经网络的权重 是通过沿局部改善的方向逐渐进行调整的，这样会使算法陷入局部极值。加上BP神经网络对初始网络权重非常敏感，以不同的权重初始化网络，往往会收敛于不同的局部极小。
2. 收敛速度慢：BP神经网络采用梯度下降法寻优，当优化的目标函数非常复杂、或者神经元输出接近0或1的情况下，BP算法非常低效。
3. 网络结构选择不一：BP神经网络结构的选择至今尚无一种统一而完整的理论指导，一般只能由经验选定。而网络的结构直接影响网络的逼近能力及泛化能力。

CNN

CNN其本质是一个多层感知机，成功的原因在于其采用了局部感知和共享权重的网络结构方式：

• 一方面减少了权值的数量使得网络易于优化
• 另一方面降低了模型的复杂度，也就是减小了过拟合的风险
  平均池化和最大池化的优势区别
• 平均池化能够提取出图像局部特征区域的整体特征，提炼局部特征区域的背景；
• 最大池化则可以提取出图像的边缘纹路，放大不同特征区域的内容差异，但可能会引起图像的过度失真。

RNN

1. 时间递归神经网络，又名循环神经网络（Recurrent Neural Network，简记为RNN）被设计用于处理序列数据，因而广泛地应用于语音识别，文本翻译，视频描述等问题
2. RNN网络结构中当前时刻的输出不仅和当前的输入有关，还与过去时刻的输入有关，因此可以将RNN网络看作是具有记忆能力的网络结构

EM算法

EM算法是一种迭代算法，1977年由Dempster等人总结提出，用于含有隐变量（hidden variable）的概率模型参数的极大似然估计，或极大后验概率估计。

EM算法的迭代由两步组成：

• E步：求期望（expectation）
• M步：求极大（maximization）

EM算法是通过不断求解下界的极大化逼近求解对数似然函数极大化的

步骤

1. 选择参数的初值$\theta^0$,开始迭代,EM算法对初始值敏感。
2. E步，计算$\theta$的最大化期望
   $$Q(\theta, \theta^i) = E_z[logP(Y,Z|\theta)|Y,\theta^i]=\sum_zlogP(Y,Z|\theta)P(Z|Y,\theta^i)$$
3. M步，求最大化期望的估计值$\theta^{i+1}$
   $$\theta^{i+1} = \argmax_{\theta} Q(\theta, \theta^i)$$

EM算法收敛性

1. $P(Y|\theta^i)$单调递增
2. 如果$P(Y|\theta)$有上界，则$L(\theta^i) =logP(Y|\theta^i)收敛到某一值L*$
3. 在函数$Q(Θ, Θ’)$与$L(Θ)$满足一定条件下，由EM算法得到的参数估计序列$Θ^i$的收敛值$Θ*$是$L(Θ)$的稳定点。

EM解决高斯混合模型

奇异值分解

奇异值分解（singular value decomposition，SVD）是一种矩阵因子分解方法，在统计学习中被广泛使用。
奇异值分解可以看作是矩阵数据压缩的一种方法，即用因子分解的方式近似地表示原始矩阵，这种近似是在平方损失意义下的最优近似。

将一个非零的$m\times n$实矩阵$A$分解成：
$$A=U \Sigma V^{\mathrm{T}}$$
其中$U$是m阶正交矩阵，$V$是n阶正交矩阵，$\Sigma$是由降序排列的飞赴对角矩阵。

具体步骤

1. $A^TA$是n阶实对称矩阵。存在一个n阶正交实矩阵$V$使得$A^TA$对角化。$V^{T}\left(A^{T} A\right) V=\Lambda$

   令$(\lambda_1, \dots, \lambda_r,0,\dots,0)$是$A^TA$的特征值，对应的特征向量$V_{1}=\left[\begin{array}{llllll}\nu_{1} & \nu_{2} & \cdots & \nu_{r}\end{array}\right], \quad V_{2}=\left[\begin{array}{llllll}\nu_{r+1} & \nu_{r+2} & \cdots & \nu_{n}\end{array}\right]$,$V_2$的列向量是$N(A)$的一组标准正交基，$AV_2 = 0$。

2. 就有对角矩阵$\Sigma$
   $$\Sigma=\left[\begin{array}{cc}\Sigma_{1} & 0 \ 0 & 0\end{array}\right]$$

3. 确定$U$
   $$u_{j}=\frac{1}{\sigma_{j}} A v_{j}, \quad j=1,2, \cdots, r$$
   $$U_{1}=\left[\begin{array}{llll}u_{1} & u_{2} & \cdots & u_{r}\end{array}\right]$$
   则有$AV_1 = U_1\Sigma_1$，令$U_{2}=\left[\begin{array}{llll}u_{r+1} & \cdots & u_{n}\end{array}\right]$为$N(A^T)$的一组标准正交基。则$U = [u1,u2]$是m阶正交矩阵。

紧奇异值分解

$$A=U_r \Sigma_r V_r^{\mathrm{T}}$$
$U,V$取前r列，$\Sigma$取前r个对角元素。

截断奇异值分解

在矩阵的奇异值分解中，只取最大的k个奇异值（k<r，r为矩阵的秩）对应的部分，就得到矩阵的截断奇异值分解。

PCA