统计学习方法 笔记一
概论
-
统计学习方法三要素：模型、策略、算法
-
精确率、召回率、准确率、F1-score
- 精确率：$P=\frac{TP}{TP+FP}$
- 召回率：$R=\frac{TP}{TP+FN}$
- 准确率：$\frac{TP+TN}{TP+TN+FP+FN}$
- F1-score：$2*\frac{PR}{P+R}=\frac{2TP}{2*TP+FN+FP}$
感知机
解决二分类问题，前提是数据集线性可分
例：平面点集划分
损失函数：$L(w,b)=-\frac{1}{\Vert w \Vert}\sum_{x_i\in M}y_i(w\cdot x_i+b)$ ，$M$是误分类点的集合
可不考虑$\frac{1}{\Vert w \Vert}$，即$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)$，当没有误分类点时损失函数为0
因为感知机为误分类驱动的模型，只需计算误分类的样本数即可，而不必计算实际的“距离”。至于为什么不直接统计错误分类的数目作为损失函数，是因为但从错误分类的数目不能对参数w进行优化，所以通过距离来进行w的“绑定”
算法使用随机梯度下降
k近邻
分类与回归
k值的选择, 距离度量及分类决策规则是kNN的三个基本要素
k值的选择通常用交叉验证的方式选取，距离度量一般为二范数即欧氏距离，决策规则通常为多数表决的方式
K近邻算法是没有显示的模型的，意思是说不像感知机那样，通过训练数据训练好模型后就不需要训练数据了，直接将预测数据输入模型即可得出结果。而是每一次的预测都需要原始数据的参与
朴素贝叶斯
用于多分类,朴素贝叶斯法实际上学习到生成数据的机制, 所以属于生成模型
例：辨别垃圾邮件
其通过训练先验概率分布$P(Y=c_k)$和条件概率分布$P(X=x \mid Y=c_k)$来得到后验$P(Y \mid X)=\frac{P(X,Y)}{P(X)}=\frac{P(X \mid Y)P(Y)}{P(X)}$，当输入测试样本$X$，取后验概率最大的为输出结果
朴素 是因为对条件概率分布做了条件独立的假设，即用于分类的特征在类别确定的条件下都是条件独立的，即
$P(X=x \mid Y=c_k)=P(X^{(1)}, \dots,X^{(n)} \vert Y=c_k)=\prod^n_{j=1}P(X^{(j)}=x^{(j)} \mid Y=c_k)$
则$P(Y=c_k \mid X=x)=\frac{P(X,Y)}{P(X=x)}=\frac{P(X=x \mid Y=c_k)P(Y=c_k)}{P(X=x)}=\frac{\prod^n_{j=1}P(X^{(j)}=x^{(j)} \mid Y=c_k)P(Y=c_k)}{P(X=x)}$
模型输出：
$f(x)=\mathop{argmax}\limits_{c_k}P(Y=c_k \mid X=x)=\mathop{argmax}\limits_{c_k}\prod^n_{j=1}P(X^{(j)}=x^{(j)} \mid Y=c_k)P(Y=c_k)$
损失函数:0-1损失函数 $$ L(Y,f(x))=\left{ \begin{aligned} 0,Y=f(x) \ 1,Y\not ={f(x)} \end{aligned} \right. $$
优化目标：期望风险最小化： $\min\mathbb{E}L(Y,f(x))=\min\sum\limits_x L(Y,f(x))P(X,Y)=\min\sum\limits_x L(Y,f(x))P(Y \vert X)P(X)$
相当于：$\min\sum\limits_x L(Y,f(x))P(Y \mid X)=\min\sum\limits_{c_k} L(Y=c_k,f(x))P(Y=c_k \mid X)$
最后可得到后验概率最大化准则：$f(x)=\arg\max\limits_{c_k}P(c_k \mid X=x)$ ，详细见p80
为什么用期望风险：期望风险是比经验风险度量模型好坏的更优指标，只不过一般的模型对于求解$P(X)$??比较难求，而朴素贝叶斯在之前的训练过程中就已经求出先验概率的，所以可以求期望风险
对先验概率$P(Y)$和$P(X \mid Y)$的估计可用极大似然估计，但可能出现为0的特殊情况，则使用贝叶斯估计
决策树
分类和回归方法，主要的三个步骤：特征选择，决策树生成，决策树修剪
根据选取特征的侧重不同，主要有三种构造算法：
1. 信息增益 ID3
Iterative Dichotomiser 3 迭代二分法3代
熵：事物的混乱程度，熵越大越混乱
信息熵：描述事物信息量的多少，熵越大，信息量越大，信息越“混乱”，即当可能的取值等概率分布时，熵最大。在决策树中，熵越小表示信息越“确定”，即熵越小的特征更有代表性 $H(X)=-\sum_{i=1}^{n}p(x_{i})logp(x_{i})$
信息增益：当前节点的信息熵减去子节点的(加权)信息熵。若信息增益大，即子节点的(加权)信息熵小，则可以得出此特征具有良好的分类能力，因为信息熵小的节点具有更“确定”的信息，即具有大致相同的分类。
$Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{\vert D^v \vert}{\vert D \vert}*Ent(D^v)$，$D$为父亲节点，$D^v$为孩子节点，$a$为当前选择的特征
决策树的生成：用每个特征轮流作用于当前节点，每次作用都会产生多个子节点，求出节点对每个子节点的信息增益，把取得信息增益最大的特征作为当前的分类特征；对于上一步刚生成的子节点再用剩余特征分别作用求解即可，直到特征用完或成功分类(即节点中全部为一种类别，则无再分需要)或达到预设的信息增益阈值
在构建的过程中将节点中样本数最多的类别作为当前节点的标记
2. 信息增益率 C4.5
$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
$IV(a)=-\sum_{v=1}^V\frac{\vert D^v \vert}{\vert D \vert}*log_2\frac{\vert D^v \vert}{\vert D \vert}$
在信息增益的基础上加了权重$IV(a)$，其为特征a对节点分类后产生的子节点之间的信息熵，代表了子节点之间的分类差别，$IV(a)$越小，子节点之间的区别越大，即分类效果越好，体现在$Gain_ratio$上就是值变大，也即特征的类数越少越好，类之间的差异越大越好
在求解过程中可以不必对每个特征都求其增益率，可以先对每个特征应用ID3算法求出信息增益，然后选出前topK来进一步计算其增益率，最后选取增益率最大的特征作为当前节点特征即可，其余步骤与ID3类似
3. 基尼系数 CART
不同于前两种算法，CART生成的树为二叉树
CART(Classification And Regression Tree)，即分类回归树算法
Gini系数原生表示的是社会收入水平的差距，越大代表收入越不平衡。这里的Gini系数是一种与信息熵类似的做特征选择的方式，可以用来数据的纯度,系数越大表示数据的纯度越低。计算方法不同，但具有相似的含义
$Gini(D)=\sum_{i=1}^{n}p_i(1-p_i)=1-\sum_{i=1}^{n}p_i^2$，D表示数据集全体样本，pi表示每种类别出现的概率，值越小，越代表属于同一类别
注意：在CART算法中n=2，因其为二叉树，所以只能选取每个特征下K种取值中最好的作为当前特征的属性，然后用该属性的满足和不满足两种选择来计算当前特征的优劣，然后同样方式计算其他特征优劣，再从当前节点的所有特征中选取最优的
所以可看出与以上两种方法不同的是，CART只选取特征的一种属性，而不是全部选取
$Gini_index(D,a)=\sum_{v=1}^{V}\frac{\vert D^v \vert}{\vert D \vert}*Gini(D^v)$
选取基尼指数最小的特征作为当前的节点的分类特征
注意：为什么这里不像ID3那样用增益(比如这里可能是基尼增益)作为选择的指标，是因为在前两个算法中，对特征的每个属性都要做选择判断，所以生成的树有极大可能会过拟合，因此在生成的过程中就要设置一个阈值(即前后信息熵的差值)来进行预剪枝，这个阈值就是增益的大小；而CART在生成的过程中只选取一个属性进行是否判断，自动将此特征的其他属性剪去了，所以就没必要再进行剪枝了，也就没必要用增益了
过拟合
方法：预剪枝、后剪枝
预剪枝： 在树生成的过程中进行剪枝
在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点 参考
后剪枝： 在树生成后进行剪枝
用训练集构建好一颗决策树后，利用测试集进行的操作。自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点 参考
衡量剪枝与否的标准：最小化决策树的损失函数
$C_{\alpha}(T)=\sum_{t=1}^{ \vert T \vert} N_{t} H_{t}(T)+\alpha \vert T \vert$，$\vert T \vert$ 表示叶节点的个数，即模型复杂度，相当于正则来防止过拟合；$t$为叶节点
$H_{t}(T)=-\sum_{k} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}}$
$C(T)=\sum_{t=1}^{ \vert T \vert } N_{t} H_{t}(T)=-\sum_{t=1}^{ \vert T \vert } \sum_{k=1}^{K} N_{t k} \log \frac{N_{t k}}{N_{t}}$
$C_{\alpha}(T)=C(T)+\alpha \vert T \vert$
对比： 后剪枝决策树通常比预剪枝决策树保留了更多的分支； 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树； 后剪枝决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多
对连续值的处理
参考链接
因为连续特征的可取值数目不再有限，因此不能像前面处理离散特征枚举离散特征取值来对结点进行划分。因此需要连续特征离散化，常用的离散化策略是二分法，这个技术也是C4.5中采用的策略
方式：将连续值按小到大进行排序。如[1,2,3,4,5]，分别选取前n-1个数据作为划分点，如选取2时划分的特征为n<=2，划分的子节点为[1,2]和[3,4,5]，所以就转化成了二分类问题
与离散特征不同，若当前结点划分特征为连续特征，该特征还可作为其后代结点的划分特征。“n<=2”这个特征在根节点用了一次，后代结点也用了一次，只是两次划分点取值不同，后一次的可能为“n>=4”。注意的是，使用特征的次数是指从当前节点到根节点的路径上的特征，若为离散特征，在这条路径上每个特征只能出现一次，但可在多条路径上出现多次，而连续特征在一条路径上可出现多次