本文主要整理了在阅读李航的《统计学习方法》中的学习笔记,阅读过程中参考了很多前人的总结和分析,收获良多。在此无法一一感谢,很多笔记都是拾人牙慧,如有侵权,请告知我将进行修改。
代码实现开源在我的 Github。
感知机
感知机算法是一种二分类算法。可以分为基本形式和对偶形式。
一、简介
在二维空间中,感知机模型试图寻找到一个直线区分开所有标签不同的元素。放到三维或者更高维的空间,感知机的模型就是尝试找到一个超平面,能够把所有的二元类别隔离开。当然,如果我们找不到这么一条直线的话怎么办?找不到的话那就意味着类别线性不可分,也就意味着感知机模型不适合你的数据的分类。
所以,使用感知机一个最大的前提,就是数据是线性可分的,这严重限制了感知机的使用场景。它的分类竞争对手在面对不可分的情况时,比如支持向量机可以通过核技巧来让数据在高维可分,神经网络可以通过优化激活函数、增加隐藏层和支持多输出,来让数据可分。
感知机适用于具有线性可分的数据集的二分类问题,可以说是很局限了。它本质上是一个分离超平面。在向量维数(特征数)过高时,选择对偶形式算法。在向量个数(样本数)过多时,应选择原始算法。
二、优缺点
优点:一种比较基础的方法,复杂度低。需要对于不同的数据集选取原始算法形式还是对偶算法形式。
缺点:只能处理能被二分类的问题,否则效果很差。当训练集线性不可分时,感知机学习算法不收敛,会发生震荡。
KNN算法
KNN算法是一种多分类算法,也可以用于回归
一、简介
KNN最邻近分类算法在分类决策时只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
KNN算法的关键:
- (1) 样本的所有特征都要做可比较的量化
若是样本特征中存在非数值的类型,必须采取手段将其量化为数值。例如样本特征中包含颜色,可通过将颜色转换为灰度值来实现距离计算。- (2) 样本特征要做归一化处理
样本有多个参数,每一个参数都有自己的定义域和取值范围,他们对距离计算的影响不一样,如取值较大的影响力会盖过取值较小的参数。所以样本参数必须做一些 scale 处理,最简单的方式就是所有特征的数值都采取归一化处置。 - (3) 需要一个距离函数以计算两个样本之间的距离
- (4) 确定K的值
**K值选的太大易引起欠拟合,太小容易过拟合,需交叉验证确定K值。**
- (2) 样本特征要做归一化处理
二、优缺点
KNN算法的优点:
简单,易于理解,易于实现,无需估计参数,无需训练;
适合对稀有事件进行分类;
特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。
KNN算法的缺点:
KNN算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算最近的邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。(可以才有kd树的加快搜索)
该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。
可理解性差,无法给出像决策树那样的规则
三、用于回归
KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比(组合函数)。
朴素贝叶斯算法
朴素贝叶斯算法是一种分类算法,生成学习算法
一、优点
朴素贝叶斯的主要优点有:
1)朴素贝叶斯模型发源于古典数学理论,有稳定的分类效率。
2)对小规模的数据表现很好,能个处理多分类任务,适合增量式训练,尤其是数据量超出内存时,我们可以一批批的去增量训练。
3)对缺失数据不太敏感,算法也比较简单,常用于文本分类。
二、缺点
朴素贝叶斯的主要缺点有:
1)理论上,朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为朴素贝叶斯模型给定输出类别的情况下,假设属性之间相互独立,这个假设在实际应用中往往是不成立的,在属性个数比较多或者属性之间相关性较大时,分类效果不好。而在属性相关性较小时,朴素贝叶斯性能最为良好。对于这一点,有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进。
2)需要知道先验概率,且先验概率很多时候取决于假设,假设的模型可以有很多种,因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。
3)由于我们是通过先验和数据来决定后验的概率从而决定分类,所以分类决策存在一定的错误率。
4)对输入数据的表达形式很敏感。
个人总结:贝叶斯算法还是要加强推导的练习,熟悉思路。
决策树
决策树一类基本的回归于分类问题。一般包括特征选择,决策树的生成,和决策树的剪枝。
决策树的生成对应了模型的局部选择,剪枝对应了模型的全局选择。
使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。
这部分内容《统计学习》里面介绍的不多,“西瓜书”更为详尽。
一、特征选择
一般就是就是基于信息论的,信息增益和信息增益率算法。其中ID3采用的是信息增益算法,C4.5算法是采用了启发式方法,首先候选划分属性中找出信息增益高于平均水平的属性(这样保证了大部分好的的特征),再从中选择增益率最高的(又保证了不会出现编号特征这种极端的情况)。
基本思路就是,每次进行决策时,希望决策后的集合的纯度最高,也就是新的集合的信息熵最小。
- 两种计算纯度方法的对比
- 信息增益准则其实是对可取值数目较多的属性有所偏好。因为可以获得最大的纯度,可能会分为最多的类。
- 信息增益比,相当于为原有的方法添加了损失项,会更趋向于选择少分类的项。(信息增益/特征A的熵)
另外CART算法采用的基尼系数衡量纯度。$Gini(p) = 1-\Sigma(p_k^2)$。 如果是回归树采用方差进行衡量。
二、剪枝
可以分为预剪枝和后剪枝
- 基于贪心思路的预剪枝的复杂度低,降低了训练时间。但是存在欠拟合的风险
- 后剪枝时首先从训练集中生成一棵完整的决策树,然后下而上的剪枝。这样复杂度高,但是欠拟合风险低且泛化能力强。
三、连续值和缺失值的处理。
- 连续值的处理
以上的属性值都是离散的,现实中通常会遇到连续的属性值。这个时候,连续属性离散化技术就可以用上啦,C4.5决策树算法采用的是最简单的策略二分法来对连续值进行处理。给西瓜属性考虑密度的属性,首先把不同样本的密度值按照从小到大排序,然后找到候选划分点,把每个候选划分点的信息增益算出来,取max的值作为密度的信息增益。第二次max就是找到最优划分属性了。
- 缺失值的处理
如果样本中有缺失值,那么会产生以下两个问题:
(1)如何在属性值缺失的情况下计算属性的信息增益,从而进行划分属性的选择?
(2)给定划分属性,如果样本在该属性值上是缺失的,如何对这个样本进行划分?
针对(1)的处理非常简单,假设17个样本在“色泽”属性上只有14个是有值的,另外3个是缺失的,那么就以这14个样本的属性值计算信息增益,然后把这个值乘以14/17,相当于乘上一个权重,当作这全部17个样本的信息增益。然后进行后续的属性划分。
针对(2)的处理也很简单,本来每个样本在结点中的权重都是1,当样本「8」在“纹理”上出现缺失值,那么在“纹理=清晰”、“纹理=模糊”、“纹理=稍糊”这三个分支中都会出现样本「8」,只是权重不再是1,而是7/15,5/15,3/15(这三个权重的来源是这三个分支中各个样本的比例,不包括这个样本「8」)
逻辑斯蒂回归
一、基础概念
LR回归的核心在于引入了新的平滑函数sigmoid函数,这种函数相比于感知机的符号函数sgn函数好处在于可以求导,可以求导意味着可以进行梯度下降。(在感知机中实际上是最小化 $y_i(w*x_i+b)$)
并且相对于感知机算法,只要$wx+b>0$就判定为1的策略。再sigmoid的函数帮助下,我们可以得到一个相对精确的概率。
我们需要假设数据符合这一分布,在得到了分布模型之后,我们可以通过最大似然估计的方法得到模型的相关参数。因为sigmoid是平滑可导的,我们可以对似然函数求导,进行梯度下降寻找参数的最优点。
需要注意得到的对数似然函数,N为样本数量。
对似然函数求导可以得到:
$\frac{\partial L(w)}{\partial w_i}={y_i}{x_i}-\frac{x_i\exp(wx_i)}{1 + \exp {w{x_i}})}$
对于LR的理解可以看为线性模型$w^Tx$的结果压缩到了[0, 1]的空间上,具有了概率意义。
二、对数几率(log odds)
定义对数几率为$logit(p) = \log(\frac{p}{1-p})$
最大熵原理
核心本质:系统中事件发生的概率满足一切已知约束条件,不对任何未知信息做假设,也就是对于未知的,当作等概率处理。
一、最大熵模型
我们希望得到的在满足了所有约束的前提下,其余时间的发生概率都是等概率的,也就是熵最大。我们可以从样本集中知道x的经验概率。因此我们希望得到一个模型$p(x|y)$能够做到$H(p)$ 最大。
二、最大熵模型的学习
从数据集中我们可以的一些关于x和y的经验分布知识,这里的特征函数$f_i$是一种存在关系。
可以认为如果(x, y)出现在训练集中,那么它就是1,因为一旦出现在训练集中,说明(x, y)对已经符合了某一样本的事实了。P上面的短横表示这个模型是基于训练集得出来的,只能被称为经验分布。
这个约束实际上要求我们训练出来的模型$p(y|x)$需要很接近$\bar{p}(y|x)$.
对于最优化问题我们采用引入拉格朗日乘子,定义为$L(P,w)$
注意这里可以对偶问题等价的条件是因为是凸函数。我们首先需要找到一个让$L(P,w)$最小的$P(y|x)$。因此我们对$L(P, w)$求导。
求导得到结果:
进一步变形整理
这一步其实没有实质性变化,只是化为了标准形式而已。
只需要带回去$L(w,p)$函数,在进一步对w求导就可以得到极值,但是这里出现了一个问题。将最优的p带回函数后,发现是无法对w求导解决的,因为是不可解析的。
三、最大化$L(w)$与最大似然估计是等价的
关于如何得到的对数似然函数可以参见,参考文献
四、最大熵模型的最优化算法
希望求解的是对偶函数的最大化条件,但是由于得不到显式的解析解,因此需要借助数值算法。好在目标函数是一个光滑的凸函数,因此可以采用多种方法求解,并且保证得到最优解。
这里采用IIS的方法:
核心在于求解
在代码层面实现:M可以看成学习速率,6.34式分子部分是给定数据集就确定的,分母部分每次更新完w之后需要重新计算
五、最大熵的优缺点
- 最大熵模型的优点有:
a) 最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型,作为经典的分类模型时准确率较高。
b) 可以灵活地设置约束条件,通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度
- 最大熵模型的缺点有:
a) 由于约束函数数量和样本数目有关系,导致迭代过程计算量巨大,实际应用比较难。