logistic回归的目的是寻找一个非线性函数sigmoid的最佳拟合参数,从而来相对准确的预测分类结果。为了找出最佳的函数拟合参数,最常用的优化算法为梯度上升法,当然我们为了节省计算损耗,通常选择随机梯度上升法来迭代更新拟合参数。并且,随机梯度上升法是一种在线学习算法,它可以在新数据到来时完成参数的更新,而不需要重新读取整个数据集来进行批处理运算。
总的来说,logistic回归算法,其具有计算代价不高,易于理解和实现等优点;此外,logistic回归算法容易出现欠拟合,以及分类精度不太高的缺点。
我们知道,评判一个优化算法的优劣的可靠方法是看其是否收敛,也就是说参数的值是否达到稳定值。此外,当参数值接近稳定时,仍然可能会出现一些小的周期性的波动。这种情况发生的原因是样本集中存在一些不能正确分类的样本点(数据集并非线性可分),所以这些点在每次迭代时会引发系数的剧烈改变,造成周期性的波动。显然我们希望算法能够避免来回波动,从而收敛到某个值,并且收敛速度也要足够快。
改进:
1 alpha在每次迭代更新是都会调整,这会缓解数据波动或者高频运动。此外,alpha还有一个常数项,目的是为了保证在多次迭代后仍然对新数据具有一定的影响,如果要处理的问题是动态变化的,可以适当加大该常数项,从而确保新的值获得更大的回归系数。
2 第二个改进的地方是选择随机的样本对参数进行更新,由于增加了随机性,这就防止参数值发生周期性的波动。
===============================================================
五、支持向量机(SVM)1.概述 SVM有很多实现,但是本章只关注其中最流行的一种实现,即序列最小优化,在此之后,将介绍如何使用一种称为核函数(kernel)的方式将SVM扩展到更多数据集上。
支持向量机是一种二类分类算法,假设一个平面可以将所有的样本分为两类,位于正侧的样本为一类,值为+1,而位于负一侧的样本为另外一类,值为-1。虽然SVM本身是一个二类分类器,若要解决多类问题,需要修改SVM。
我们说分类,不仅仅是将不同的类别样本分隔开,还要以比较大的置信度来分隔这些样本,这样才能使绝大部分样本被分开。比如,我们想通过一个平面将两个类别的样本分开,如果这些样本是线性可分(或者近视线性可分),那么这样的平面有很多,但是如果我们加上要以最大的置信度来将这些样本分开,那么这样的平面只有一条。
- 1.几何间隔
几何间隔的概念,简单理解就是样本点到分隔平面的距离 2 间隔最大化
想要间隔最大化,我们必须找到距离分隔平面最近的点,并且使得距离平面最近的点尽可能的距离平面最远,这样,每一个样本就都能够以比较大的置信度被分隔开算法的分类预测能力也就越好
显然,SVM算法的关键所在,就是找到使得间隔最大化的分隔超平面(如果特征是高维度的情况,我们称这样的平面为超平面)。简言之:最大化支持向量到超平面距离优点:泛化错误率低,计算开销不大,结果易解释。
- 缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二类问题。
- 适用数据类型:数值型和标称型数据。
支持向量机推导
- 训练算法:SVM的大部分时间都源自训练,该过程主要实现两个参数的调优。
- 测试算法:十分简单的计算过程就可以实现。
- 使用算法:几乎所有分类问题都可以使用SVM,值得一提的是,S V M 本身是一个二类分类器,对多类问题应用SVM需要对代码做一些修改。
下面介绍线性支持向量机,近似线性支持向量机以及非线性支持向量机(核函数)
2.1 线性支持向量机 求解线性支持向量机的过程是凸二次规划问题,所谓凸二次规划问题,就是目标函数是凸的二次可微函数,约束函数为仿射函数满足
而我们说求解凸二次规划问题可以利用对偶算法–即引入拉格朗日算子,利用拉格朗日对偶性将原始问题的最优解问题转化为拉格朗日对偶问题,这样就将求<span class="MathJax" id="MathJax-Element-14-Frame" tabindex="0" data-mathml="w∗,b" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">w∗,bw∗,b的原始问题的极小问题转化为求
<span class="MathJax" id="MathJax-Element-15-Frame" tabindex="0" data-mathml="α∗" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">α∗α∗
[color=rgba(0, 0, 0, 0.75)]α>=0,∑i=1mαilable(i)=0(1)(1)α>=0,∑i=1mαilable(i)=0
的对偶问题的极大问题,即求出<span class="MathJax" id="MathJax-Element-17-Frame" tabindex="0" data-mathml="α∗" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 14px; text-align: left; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; color: rgba(0, 0, 0, 0.75); position: relative;">α∗α∗,在通过KKT条件求出对应的参数<span class="MathJax" id="MathJax-Element-18-Frame" tabindex="0" data-mathml="w∗,b" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; font-size: 14px; text-align: left; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; color: rgba(0, 0, 0, 0.75); position: relative;">w∗,bw∗,b,从而找到这样的间隔最大化超平面,进而利用该平面完成样本分类。目标函数如下:
[color=rgba(0, 0, 0, 0.75)]maxα[∑i=1mα−12∑i,j=1mlabel(i)label(j)αiαj<x(i),x(j)>](2)(2)maxα[∑i=1mα−12∑i,j=1mlabel(i)label(j)αiαj<x(i),x(j)>]
2.2 近似线性支持向量机
当数据集并不是严格线性可分时,即满足绝不部分样本点是线性可分,存在极少部分异常点;这里也就是说存在部分样本不能满足约束条件,此时我们可以引入松弛因子,这样这些样本点到超平面的函数距离加上松弛因子,就能保证被超平面分隔开来;当然,添加了松弛因子<span class="MathJax" id="MathJax-Element-20-Frame" tabindex="0" data-mathml="σ" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">σσ,我们也会添加对应的代价项,使得
[color=rgba(0, 0, 0, 0.75)]α$满足$0=<α<=C$和$∑i=1mαilable(i)=0(3)(3)α$满足$0=<α<=C$和$∑i=1mαilable(i)=0
2.3 非线性支持向量机
显然,当数据集不是线性可分的,即我们不能通过前面的线性模型来对数据集进行分类。此时,我们必须想办法将这些样本特征符合线性模型,才能通过线性模型对这些样本进行分类。这就要用到核函数,核函数的功能就是将低维的特征空间映射到高维的特征空间,而在高维的特征空间中,这些样本进过转化后,变成了线性可分的情况,这样,在高维空间中,我们就能够利用线性模型来解决数据集分类问题
如果想要透彻理解SVM建议还是要看看书和博客文章,篇幅有限,我这里的中心在于凸二次规划的优化算法——SMO(序列最小最优化算法)
SMO算法的工作原理是:每次循环中选择两个<span class="MathJax" id="MathJax-Element-22-Frame" tabindex="0" data-mathml="α" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">αα进行优化处理。一旦找到一对合适的<span class="MathJax" id="MathJax-Element-23-Frame" tabindex="0" data-mathml="α" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">αα,那么就增大其中一个而减少另外一个。这里的”合适”,意味着在选择<span class="MathJax" id="MathJax-Element-24-Frame" tabindex="0" data-mathml="α" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">αα对时必须满足一定的条件,条件之一是这两个<span class="MathJax" id="MathJax-Element-25-Frame" tabindex="0" data-mathml="α" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">αα不满足最优化问题的kkt条件,另外一个条件是这两个<span class="MathJax" id="MathJax-Element-26-Frame" tabindex="0" data-mathml="α" role="presentation" style="box-sizing: border-box; outline: 0px; display: inline; line-height: normal; text-align: left; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; word-break: break-all; position: relative;">αα还没有进行区间化处理,对于SMO算法编写,我们采用由简单到复杂的方法,层层递进,完成最终的SMO算法实现,最后通过实际的用例对SVM模型进行训练,并验证准确性。