企业建站域名,网站开发专业感想,360企业网站认证,四川招标采购网一、 硬间隔-SMO算法推导 明天再说#xff0c;啊。。。。感觉天空明朗了很多#xff0c;即使现在已经很晚了 还是要打开柯南#xff0c;看看电视#xff0c;等待天气预报所说的台风天吧#xff01; 一时之间#xff0c;忽然失去了用markdown语法写下推导过程的勇气。。。…一、 硬间隔-SMO算法推导 明天再说啊。。。。感觉天空明朗了很多即使现在已经很晚了 还是要打开柯南看看电视等待天气预报所说的台风天吧 一时之间忽然失去了用markdown语法写下推导过程的勇气。。。以上只是自己在线性可分的情况下推导的smo算法但实际书本上给出的smo算法是增加了软间隔后的smo算法 以上只是理解版本的推导但实际要用在程序上理解绝不能这么不严谨 是的我现在终于理解为什么为什么为什么课本要列出那么多奇奇怪怪的符号 那都是非常简便的表达方式 看了自己手动推的乱七八糟SMO再看看人家推导的SMO保姆级教学 我终于发现自己推导的漏洞百出 哭了哭着重新在草稿纸继续推导吧~ 最后拉格朗日对偶问题是要求解 M A X λ L ( λ ) ∑ λ i − ∑ i 1 n ∑ j 1 n λ i λ j x i x j y i y j 2 MAX_λL(λ)∑λ_i-\frac{∑_{i1}^n∑_{j1}^nλ_iλ_jx_ix_jy_iy_j}{2} MAXλL(λ)∑λi−2∑i1n∑j1nλiλjxixjyiyj 即通过调整λ值求解L函数极大值
而 M a x : L Max: L Max:L可以转化为求 M i n : − L Min:- L Min:−L即求解 M i n λ L ( λ ) ∑ i 1 n ∑ j 1 n λ i λ j x i x j y i y j 2 − ∑ λ i Min_λL(λ)\frac{∑_{i1}^n∑_{j1}^nλ_iλ_jx_ix_jy_iy_j}{2}-∑λ_i MinλL(λ)2∑i1n∑j1nλiλjxixjyiyj−∑λi
接下来采用SMO算法求解 M i n : L Min: L Min:L ①使最终数据符合KKT条件 λ g ( w , b ) ≤ 0 , 且要保证 λ ≥ 0 因此 K K T 条件的判断具体分为以下两种 λg(w,b)≤0,且要保证λ≥0因此KKT条件的判断具体分为以下两种 λg(w,b)≤0,且要保证λ≥0因此KKT条件的判断具体分为以下两种 λ i 0 时 g ( w , b ) 0 即 1 − y i ∗ ( W x i b ) 0 λ_i0时g(w,b)0即1-y_i*(Wx_ib)0 λi0时g(w,b)0即1−yi∗(Wxib)0 λ i 0 时 g ( w , b ) ≤ 0 即 1 − y i ∗ ( W x i b ) ≤ 0 λ_i 0时g(w,b)≤0即1-y_i*(Wx_ib)≤0 λi0时g(w,b)≤0即1−yi∗(Wxib)≤0
②λ要始终满足 Σ λ i y i 0 Σλ_iyi0 Σλiyi0
SMO算法思想:迭代贪心
由于每条数据都对应一个λ值即 x i , y i , λ i x_i,y_i,λ_i xi,yi,λi因此假设有n条数据就有n个λ直接求导非常困难
SMO算法提出每次迭代2个λ确保这2个λ都在自己能力范围内都尽可能使L(λ)函数值达到最优且始终保持 Σ λ i y i 0 Σλ_iyi0 Σλiyi0 这就像是贪心算法局部最优最终全局最优 简单点每个人都拼尽全力让社会更美好那么社会才会达到最美好 每道题都拿最高分你就是rolling king or rolling queen SMO思想甚至还有先富带后富的先进理念我无法同时让λ达到状态但我可以每次2个既可以保证 Σ λ i y i 0 Σλ_iyi0 Σλiyi0还可以逐次使L达到最优 1. 算法步骤总览
明确SMO的迭代贪心的思想后就可以简化为以下几个步骤
①未知参数赋初值 ②选择2个迭代λ用λ_1,λ_2分别代表选中的2个λ ③求解迭代后的λ并判断是否满足λ≥0条件 ④计算当前的 W n e w , b n e w W_{new},b_{new} Wnew,bnew ⑤若全部满足KKT条件或达到迭代次数则停止SMO算法 看似简单的步骤实则难于上青天 ①未知参数赋初值
λλ_i全赋值为0这样即可保证 Σ λ i y i 0 Σλ_iyi0 Σλiyi0W W ∑ λ i x i ∗ y i 因此 W 也全为 0 W∑λ_ix_i*y_i因此W也全为0 W∑λixi∗yi因此W也全为0bb没有条件限制要求可以直接赋值为0 【需要注意λ的个数为n表示n条数据就有n个λW的个数为影响因素的个数即有m种x就有m个W】 例如性别、年龄、收入这三个影响因素x决定幸福感y那么W就有3个 ②选择2个迭代λ用λ_1,λ_2分别代表选中的2个λ
λ1的选择方式选择最偏离KKT条件的λ
如何判断偏离KKT条件的程度 λ g ( w , b ) ≤ 0 , 且要保证 λ ≥ 0 因此 K K T 条件的判断具体分为以下两种 λg(w,b)≤0,且要保证λ≥0因此KKT条件的判断具体分为以下两种 λg(w,b)≤0,且要保证λ≥0因此KKT条件的判断具体分为以下两种 λ i 0 时 g ( w , b ) 0 即 1 − y i ∗ ( W x i b ) 0 λ_i0时g(w,b)0即1-y_i*(Wx_ib)0 λi0时g(w,b)0即1−yi∗(Wxib)0 λ i 0 时 g ( w , b ) ≤ 0 即 1 − y i ∗ ( W x i b ) ≤ 0 λ_i 0时g(w,b)≤0即1-y_i*(Wx_ib)≤0 λi0时g(w,b)≤0即1−yi∗(Wxib)≤0 首先是违反KKT条件其次违反程度通过g(w,b)值来衡量即选择max:g(w,b)下的 λ i λ_i λi 但建议还是将违反KKT条件的程度降序排列得到一个违反KKT条件的g(w,b)降序列表 这样如果g(w,b)的最大值对应的λ1不满足迭代条件时还可以退而求其次选g(w,b)第二大对应的λ1 【判断1】若选不到λ1说明所有λ都满足KKT条件可停止SMO算法 λ2的选择方式选择能使λ2改变最大的λ 公式推导出的 λ 2 n e w λ 2 o l d y i ∗ ( E 1 − E 2 ) K 11 K 22 − 2 K 12 λ2_{new}λ2_{old}\frac{y_i*(E1-E2)}{K11K22-2K12} λ2newλ2oldK11K22−2K12yi∗(E1−E2) 当 ∣ E 1 − E 2 ∣ 大 |E1-E2|大 ∣E1−E2∣大说明这两条对应的数据差距比较大【后续再公式推导】【判断1】若当前|E1-E2|最大的λ2不满足条件要求则重选λ即退而求其次选|E1-E2|第二大对应的λ2【判断2】若选不到λ2则重新选λ1再选λ2 重选λ1是指选下一个偏离KKT条件的λ而不是最偏离了【降序选择λ1】 λ 2 n e w λ2_{new} λ2new的公式推导
求解 M i n λ L ( λ ) ∑ i 1 n ∑ j 1 n λ i λ j x i x j y i y j 2 − ∑ λ i Min_λL(λ)\frac{∑_{i1}^n∑_{j1}^nλ_iλ_jx_ix_jy_iy_j}{2}-∑λ_i MinλL(λ)2∑i1n∑j1nλiλjxixjyiyj−∑λi已知所有λ均有初值
那么单独挑出λ1、λ2作为未知量来求L极值并迭代则需将其余的λ3…λn都当作常数
未知量λ1、λ2常数λ3…λn实际λ1、λ2本身是有旧值的但我们要求解的是它们的新值因此当作未知量来求导
step1: 因此先分离出L(λ)里含λ1和λ2的项再进行求导
第一部分 1 2 ∑ i 1 n ∑ j 1 n λ i λ j x i x j y i y j \frac{1}{2}∑_{i1}^n∑_{j1}^nλ_iλ_jx_ix_jy_iy_j 21∑i1n∑j1nλiλjxixjyiyj 1 2 [ λ 1 2 y 1 2 x 1 . x 1 λ 2 2 y 2 2 x 2 . x 2 2 λ 1 λ 1 y 1 y 2 x 1 . x 2 2 ( λ 1 y 1 x 1 λ 2 y 2 x 2 ) ∑ i 3 n λ i y i x i ∑ i 3 n ∑ j 3 n λ i λ j x i x j y i y j ] \frac{1}{2}[ λ_1^2y_1^2x_1.x_1λ_2^2y_2^2x_2.x_22λ_1λ_1y_1y_2x_1.x_22(λ_1y_1x_1λ_2y_2x_2)∑^n_{i3}λ_iy_ix_i∑_{i3}^n∑_{j3}^nλ_iλ_jx_ix_jy_iy_j] 21[λ12y12x1.x1λ22y22x2.x22λ1λ1y1y2x1.x22(λ1y1x1λ2y2x2)∑i3nλiyixi∑i3n∑j3nλiλjxixjyiyj]
注 x 1. x 1 x1.x1 x1.x1中间的点表示点积因为 x i x_i xi本身是向量向量相乘即为点积运算
第二部分 ∑ λ i λ 1 λ 2 ∑ i 3 n λ i ∑λ_iλ_1λ_2∑^n_{i3}λ_i ∑λiλ1λ2∑i3nλi
step2: 后续求导常数无用则删: 将第一、二部分常数删去后再拼接成只含迭代变量的Q(λ1λ2函数 Q 1 2 [ λ 1 2 y 1 2 x 1 . x 1 λ 2 2 y 2 2 x 2 . x 2 2 λ 1 λ 1 y 1 y 2 x 1 . x 2 2 ( λ 1 y 1 x 1 λ 2 y 2 x 2 ) ∑ i 3 n λ i y i x i ] λ 1 λ 2 Q \frac{1}{2}[ λ_1^2y_1^2x_1.x_1λ_2^2y_2^2x_2.x_22λ_1λ_1y_1y_2x_1.x_22(λ_1y_1x_1λ_2y_2x_2)∑^n_{i3}λ_iy_ix_i]λ_1λ_2 Q21[λ12y12x1.x1λ22y22x2.x22λ1λ1y1y2x1.x22(λ1y1x1λ2y2x2)∑i3nλiyixi]λ1λ2
step3: 将Q函数变为只含一个未知λ再求导
由 Σ λ i y i 0 Σλ_iyi0 Σλiyi0可得 λ 1 y 1 λ 2 y 2 − ∑ i 3 n λ i − λ 1 o l d y 1 − λ 2 o l d y 2 λ_1y_1λ_2y_2-∑^n_{i3}λ_i-λ_{1old}y_1-λ_{2old}y_2 λ1y1λ2y2−∑i3nλi−λ1oldy1−λ2oldy2
这里的λ1、λ2表示未知量 λ 1 o l d , λ 2 o l d λ_{1old},λ_{2old} λ1old,λ2old则表示它们的旧值 ∑ i 3 n λ i λ 1 o l d y 1 λ 2 o l d y 2 可视为常数 A 方便简化计算 ∑^n_{i3}λ_iλ_{1old}y_1λ_{2old}y_2可视为常数 A方便简化计算 ∑i3nλiλ1oldy1λ2oldy2可视为常数A方便简化计算
给 λ 1 y 1 λ 2 y 2 − A λ_1y_1λ_2y_2-A λ1y1λ2y2−A两边乘以y1并移项可得:λ1 -λ2y1y2-Ay1
将 λ 1 − λ 2 y 1 y 2 − A y 1 代入 Q 函数 λ1 -λ2y1y2-Ay1代入Q函数 λ1−λ2y1y2−Ay1代入Q函数即可得到只含未知量λ2的Q函数并对λ2求导后整理可得 Q λ 2 ′ h a h a h a h h a h a h a h h a h a h 放弃 m a r k d o w n 语法写推导太长辣救命 Q_{λ2} hahahahhahahahhahah放弃markdown语法写推导太长辣救命 Qλ2′hahahahhahahahhahah放弃markdown语法写推导太长辣救命
然后再将 A ∑ i 3 n λ i A∑^n_{i3}λ_i A∑i3nλi代入 Q λ 2 ′ Q_{λ2} Qλ2′并令 W x i b − y i E i 表示预测值与真实值的差距 Wx_ib-y_i E_i表示预测值与真实值的差距 Wxib−yiEi表示预测值与真实值的差距
则令 Q λ 2 ′ 0 Q_{λ2} 0 Qλ2′0最终整理出 λ 2 λ 2 o l d y 2 ∗ ( E 1 − E 2 ) x 1. x 1 x 2. x 2 − 2 x 1. x 2 λ2 λ_{2old}\frac{y2*(E1-E2)}{x1.x1x2.x2-2x1.x2} λ2λ2oldx1.x1x2.x2−2x1.x2y2∗(E1−E2)
③求解迭代后的λ并判断是否满足迭代条件
λ的条件要满足λ≥0即求解出的λ1、λ2都要满足≥0的条件
通过上一步可得到 λ 2 λ 2 o l d y 2 ∗ ( E 1 − E 2 ) x 1. x 1 x 2. x 2 − 2 x 1. x 2 λ2 λ_{2old}\frac{y2*(E1-E2)}{x1.x1x2.x2-2x1.x2} λ2λ2oldx1.x1x2.x2−2x1.x2y2∗(E1−E2)
因此可先判断λ2≥0
如果λ2≥0即继续往下如果λ2不满足条件则返回重选λ2
接着判断λ1由 λ 1 − λ 2 y 1 y 2 − A y 1 ≥ 0 λ_1 -λ_2y_1y_2-Ay_1≥0 λ1−λ2y1y2−Ay1≥0可得
当y1y2 1时 λ 2 ≤ − A y 1 λ2≤-Ay_1 λ2≤−Ay1当y1y2 -1时 λ 2 ≥ A y 1 λ2≥Ay_1 λ2≥Ay1如果满足任意一个条件则继续往下如果以上两个条件都不满足则返回重选λ2
④计算当前的 W n e w , b n e w W_{new},b_{new} Wnew,bnew
计算出满足λ≥0的λ1和λ2后可代入求解最新的 W n e w W_{new} Wnew W o l d λ 1 o l d y 1 x 1 λ 2 o l d y 2 x 2 ∑ i 3 n λ i y i x i W_{old} λ_{1old}y_1x_1λ_{2old}y_2x_2∑^n_{i3}λ_iy_ix_i Woldλ1oldy1x1λ2oldy2x2∑i3nλiyixi W n e w λ 1 y 1 x 1 λ 2 y 2 x 2 ∑ i 3 n λ i y i x i W_{new} λ_{1}y_1x_1λ_{2}y_2x_2∑^n_{i3}λ_iy_ix_i Wnewλ1y1x1λ2y2x2∑i3nλiyixi
则 W n e w W o l d ( λ 1 − λ 1 o l d ) y 1 x 1 ( λ 2 − λ 2 o l d ) y 2 x 2 W_{new} W_{old}(λ_{1}-λ_{1old})y_1x_1(λ_{2}-λ_{2old})y_2x_2 WnewWold(λ1−λ1old)y1x1(λ2−λ2old)y2x2
可见每次W的更新都只与选择的两个λ有关 b n e w b_{new} bnew表示两条边界上的b1和b2的中间值
怎么判断是不是边界呢
其实也就是当λ0的时候因此λ0则g(w,b)0这在之前的拉格朗日乘数法中已证明为支持向量即边界
因此则当λ1、λ2均大于0时根据 g ( w , b ) 1 − y i ( W n e w x i b ) 0 g(w,b) 1-y_i(W_{new}x_ib) 0 g(w,b)1−yi(Wnewxib)0
求出 b 1 n e w y 1 − W n e w x 1 b_{1new} y_1-W_{new}x_1 b1newy1−Wnewx1 b 2 n e w y 2 − W n e w x 2 b_{2new} y_2-W_{new}x_2 b2newy2−Wnewx2
则 b n e w b 1 n e w b 2 n e w 2 b_{new} \frac{b_{1new}b_{2new}}{2} bnew2b1newb2new
⑤若全部满足KKT条件或达到迭代次数则停止SMO算法 硬间隔情况下的推导比较简单但实践起来困难重重并且有些是想不通的 1、 选出违反KKT条件最严重的λ1再选出|E1-E2|值最大的λ2但计算出的 λ 1 n e w 、 λ 2 n e w λ1_{new}、λ2_{new} λ1new、λ2new并不满足λ≥0的条件因此需要重新选λ但要怎么重新选呢 先重新选λ2将所有λ的|E1-E2|进行降序排列再依次选择对应的λ2直到 λ 1 n e w 、 λ 2 n e w λ1_{new}、λ2_{new} λ1new、λ2new都满足λ≥0如果所有的|E1-E2|0的λ都选择了个遍却依然无法满足λ≥0则说明当前的λ1暂时选不出合适的λ2 则可以重新选择λ1重新选择的是违反KKT条件程度第二的λ 如果选到了合适的λ2则在完成λ1、λ2的迭代后返回重新选λ1、λ2开始新一轮的迭代。 但在实践过程中即使数据是线性可分的可一旦数据量很多的时候就很难收敛了并且经常在几个数据里来回震荡无法完全满足KKT条件的同时还能满足迭代后的λ≥0
于是为了解决这个问题采取了限定迭代次数的方法 并且测试时自己设计了线性关系哎。。。总之就是 如果只有一个影响因素x并且成线性关系时数据量少的情况下测试10条是可以完全准确分类的。。。。 但是训练的过程。。。真的好慢好慢好慢啊。。。。只要我多加一个新的线性影响因素还是10条数据。。。。。就会慢的要死并且还很难收敛到所有λ都满足KKT条件只有到10000次迭代次数自动停止后才结束训练不过好在10条数据内2个影响因素都还是100%的分类准确率 我甚至不敢测试多几条数据。。。。但还是英勇的选择了100条数据进行训练… 果然还是无法完全收敛满足KKT条件超过迭代次数后停下来的 最终准确率还是降低了…差不多就得了…实际它都没迭代完。。。但数据量实在太大了 import numpy as np
import pandas as pd
import random
import matplotlib.pyplot as plt
import time
# 获取所需数据
datas pd.read_excel(./datas6.xlsx)
important_features [推荐分值,专业度,推荐类型]
# datas pd.read_excel(./datas5.xlsx)
# important_features [推荐分值,推荐类型]datas_1 datas[important_features].head(100)
Y datas_1[推荐类型]
X datas_1.drop(推荐类型,axis1)
X_features X.columns
Y_features 推荐类型
rows,columns datas_1.shapeYY.where(Y!高推荐,other1) # 高推荐设置为1
YY.where(Y!低推荐,other-1) # 低推荐设置为-1class SMO():def __init__(self,X,Y):self.X Xself.Y Yself.m X.shape[1]self.n Y.shape[0]self.lamb np.zeros(self.n)self.b 0self.W0 np.zeros(self.m)self.times 10000self.Finish Falseself.break_kkt {}self.break_kkt_list []self.E Nonedef count_break_KKT(self):del self.break_kktself.break_kkt {}self.g 1-self.Y*((self.W0*self.X).sum(axis1)self.b)# time.sleep(3)for index,g_value in self.g.items():a self.lamb[index]if a 0:raise Exception(flamb1_new为{lamb1_new},还是小于0)elif a 0 and g_value0:self.break_kkt[index] abs(g_value)elif a 0 and g_value!0:self.break_kkt[index] abs(g_value)def run(self):select_lamb1 Falsewhile not self.Finish and self.times0:if len(self.break_kkt_list) 0:self.count_break_KKT()self.break_kkt_list sorted(self.break_kkt.items(), keylambda d: d[1], reverseTrue)if len(self.break_kkt_list) 0:print(已全部满足KKT)break# print(f当前违反KKT条件的{self.break_kkt_list})# time.sleep(3)index1 self.break_kkt_list.pop(0)[0]x1 self.X.iloc[index1]y1 self.Y[index1]lamb1_old self.lamb[index1]self.E (self.W0 * self.X).sum(axis1) self.b - self.Ye1 self.E[index1]self.E1E2_all e1-self.Eself.E1E2_abs (e1-self.E).abs()self.E1E2_sort sorted(self.E1E2_abs.items(), keylambda d: d[1], reverseTrue)# print(f当前的E1E2排序{self.E1E2_sort})# time.sleep(3)self.times - 1for j in self.E1E2_sort:index2 j[0]x2 self.X.iloc[index2]y2 self.Y[index2]lamb2_old self.lamb[index2]e1_e2 self.E1E2_all[index2]# print(f选中的第{index1}和第{index2}的E差值为{e1_e2},参数{self.lamb[index1], self.lamb[index2]})# time.sleep(3)if e1_e2 0:# print(f由于两者的E差值为0因此不进行迭代)select_lamb1 Truebreaktemp sum(x1*x1x2*x2-2*x1*x2)A -lamb1_old*y1-lamb2_old*y2if temp0:# print(当前的index1和index2的X值一致可以直接将index2的lamb2_new等同于lamb1_new)# time.sleep(3)continuelamb2_new lamb2_old e1_e2*y2/tempif lamb2_new0:continueelif y1*y2 1:if lamb2_new -A*y1:continueelif y1*y2 -1:if lamb2_new A*y1:continuelamb1_new -lamb2_new*y1*y2-A*y1time.sleep(3)self.W0 self.W0(lamb1_new-lamb1_old)*y1*x1(lamb2_new-lamb2_old)*y2*x2self.W0 np.array(self.W0)b1_new y1-sum(self.W0*x1)b2_new y2-sum(self.W0*x2)self.b np.array((b1_newb2_new)/2)self.lamb[index1]lamb1_newself.lamb[index2]lamb2_newprint(f新的lamb:{self.lamb},\nW0为{self.W0},b为{self.b})select_lamb1 Truebreakelse:print(f可选的E2中{self.E1E2_sort}没有满足条件的lamb2)if select_lamb1:select_lamb1 Falseself.count_break_KKT()self.break_kkt_list sorted(self.break_kkt.items(), keylambda d: d[1], reverseTrue)if len(self.break_kkt_list)0:self.Finish Trueprint(已全部服从KKT条件)sum_lamb_y sum(self.lamb*self.Y)print(f汇总后的值是否为零{sum_lamb_y})print(self.lamb)breaklambs sorted([(index1,value1) for index1,value1 in enumerate(self.lamb)],keylambda x:x[1],reverseTrue)index1 lambs.pop(0)[0]for index2,value2 in enumerate(lambs):if self.Y[index1]!self.Y[index2] and value2!0:print()x1 self.X.iloc[index1]x2 self.X.iloc[index2]print(self.W0*x1)print((self.W0*x1).sum(axis0))b1_new np.array(self.Y[index1]-(self.W0*x1).sum(axis0))b2_new np.array(self.Y[index2]-(self.W0*x2).sum(axis0))b_new (b1_newb2_new)/2self.b b_newprint()breakprint(b1_new,b2_new)self.W0 np.array([self.W0])print(_________________________)print(self.W0)print(self.X)print(self.b)print(_________________________)z (self.W0*self.X).sum(axis1)self.bself.Y_pre []原本计划是要大于支持向量边界时也就是大于1才能分类为1小于-1才能分类为-1但实际还是有些点位于-1,1之间导致无法完全实现点全在两侧边界分类的效果因此直接用中间的分类函数进行分for i in z:if i0:self.Y_pre.append(1)elif i0:self.Y_pre.append(-1)print(f分类准确率为{round(sum(self.Y_preself.Y)/self.Y.shape[0]*100,2)}%)test SMO(X,Y)
test.run()二、 软间隔-对偶问题及smo算法推导
之前要求的对偶问题 M A X λ L ( λ ) ∑ λ i − ∑ i 1 n ∑ j 1 n λ i λ j x i x j y i y j 2 MAX_λL(λ)∑λ_i-\frac{∑_{i1}^n∑_{j1}^nλ_iλ_jx_ix_jy_iy_j}{2} MAXλL(λ)∑λi−2∑i1n∑j1nλiλjxixjyiyj
是基于线性可分的情况下【即硬间隔】一旦数据并不是严格线性可分的情况下SVM就会失效 我猜测极有可能无法应用SMO算法计算出正确的λ
因此每条数据都引入一个松弛变量的 ξ i ξ_i ξi
然后每条数据的约束条件就变为 y i ( W x i b ) ≥ 1 − ξ i y_i(Wx_ib)≥1-ξ_i yi(Wxib)≥1−ξi且ξ≥0
但引入松弛变量就要在目标函数上增加惩罚项
原目标函数 m i n : f w 2 2 min:f\frac{w^2}{2} min:f2w2
增加惩罚项后为 m i n : f w 2 2 C ∑ ξ i min:f\frac{w^2}{2}C∑ξ_i min:f2w2C∑ξi
这里的C是我们自己设置的惩罚项权重常数 其实我也很困惑这个惩罚项到底对于目标函数的实现有什么作用呢 按我的初步想法是将惩罚项放入原函数中 w 2 2 C ∑ ξ i \frac{w^2}{2}C∑ξ_i 2w2C∑ξi 表示,要让 w 2 2 和 C ∑ ξ i \frac{w^2}{2}和C∑ξ_i 2w2和C∑ξi在相互影响相互制约的情况下尽可能使f(x)达到极小值
那么 m i n : f w 2 2 C ∑ ξ i min:f\frac{w^2}{2}C∑ξ_i min:f2w2C∑ξi中如果C比较大那么松弛变量对目标函数f的影响就会比较大因此会在训练过程中偏向于让ξ达到最小而w就没那么重要了
反之如果C比较小则松弛变量ξ对目标函数f的影响就比较小因此训练过程中会倾向于让w达到最小松弛变量反而就相对没那么重要。
通常在sklearn中这个C默认取值为1但训练出来的结果未必令人满意的因此要看情况设置C【这部分回头再说】
现在的求解目标为
目标函数为 m i n : f w 2 2 C ∑ ξ i min:f\frac{w^2}{2}C∑ξ_i min:f2w2C∑ξi约束条件为 g ( w , b , ξ ) 1 − ξ i − y i ( W x i b ) ≤ 0 g(w,b,ξ) 1-ξ_i-y_i(Wx_ib)≤0 g(w,b,ξ)1−ξi−yi(Wxib)≤0 这是约束条件1 ξ ≥ 0 ξ≥0 ξ≥0这是约束条件2转为 − ξ ≤ 0 -ξ≤0 −ξ≤0
根据拉格朗日乘数法建立函数L 第一个约束条件用λ表示对应的拉格朗日乘子 第二个约束条件用β表示对应的拉格朗日乘子 m i n L ( w , b , ξ , λ , β ) w 2 2 C Σ ξ i Σ λ i [ 1 − ξ i − y i ( W x i b ) ] − Σ β i ξ i min L(w,b,ξ,λ,β)\frac{w^2}{2}CΣξ_iΣλ_i[1-ξ_i-y_i(Wx_ib)]-Σβ_iξ_i minL(w,b,ξ,λ,β)2w2CΣξiΣλi[1−ξi−yi(Wxib)]−Σβiξi
KKT条件是 λ i [ 1 − ξ i − y i ( W x i b ) ] 0 λ_i[1-ξ_i-y_i(Wx_ib)]0 λi[1−ξi−yi(Wxib)]0 λ i 0 时 1 − ξ i − y i ( W x i b ) 0 λ_i0时 1-ξ_i-y_i(Wx_ib)0 λi0时1−ξi−yi(Wxib)0 λ i 0 时 1 − ξ i − y i ( W x i b ) ≤ 0 λ_i0时 1-ξ_i-y_i(Wx_ib)≤0 λi0时1−ξi−yi(Wxib)≤0 β i ξ i 0 β_iξ_i0 βiξi0 β i 0 时 ξ i 0 β_i0时ξ_i0 βi0时ξi0 β i 0 时 ξ i ≥ 0 β_i0时ξ_i≥0 βi0时ξi≥0
将拉格朗日函数变为对偶问题 m i n L ( w , b , ξ , λ , β ) w 2 2 C Σ ξ i Σ λ i [ 1 − ξ i − y i ( W x i b ) ] − Σ β i ξ i min L(w,b,ξ,λ,β)\frac{w^2}{2}CΣξ_iΣλ_i[1-ξ_i-y_i(Wx_ib)]-Σβ_iξ_i minL(w,b,ξ,λ,β)2w2CΣξiΣλi[1−ξi−yi(Wxib)]−Σβiξi
由于求极值过程中是要先w,b,ξ求其极小值因此可以同之前硬间隔那样推导出对偶函数为 M a x λ , β M i n w , b , ξ L ( w , b , ξ , λ , β ) w 2 2 C Σ ξ i Σ λ i [ 1 − ξ i − y i ( W x i b ) ] − Σ β i ξ i Max_{λ,β}Min_{w,b,ξ} L(w,b,ξ,λ,β)\frac{w^2}{2}CΣξ_iΣλ_i[1-ξ_i-y_i(Wx_ib)]-Σβ_iξ_i Maxλ,βMinw,b,ξL(w,b,ξ,λ,β)2w2CΣξiΣλi[1−ξi−yi(Wxib)]−Σβiξi
先对w,b,以及每一个ξ_i分别求偏导得到以下三个条件 w Σ λ i x i y i w Σλ_ix_iy_i wΣλixiyi ———① Σ λ i y i 0 Σλ_iy_i0 Σλiyi0 ———② C − λ i − β i 0 C-λ_i-β_i 0 C−λi−βi0 ———③
将 C − Σ λ i − Σ β i 0 C-Σλ_i-Σβ_i 0 C−Σλi−Σβi0转为 Σ β i C − Σ λ i Σβ_i C-Σλ_i ΣβiC−Σλi并结合①代入对偶函数整理得到 M a x ( λ ) Σ λ i − 1 2 Σ Σ λ i λ j y i y j x i x j Max(λ) Σλ_i-\frac{1}{2}ΣΣλ_iλ_jy_iy_jx_ix_j Max(λ)Σλi−21ΣΣλiλjyiyjxixj这会发现与之前硬间隔的对偶函数是一样的
松弛变量ξ及对应的拉格朗日乘子β对目标求解并无直接影响。
但KKT条件是对SMO迭代时有条件上的额外限制
KKT条件是 λ i [ 1 − ξ i − y i ( W x i b ) ] 0 λ_i[1-ξ_i-y_i(Wx_ib)]0 λi[1−ξi−yi(Wxib)]0 λ i 0 时 1 − ξ i − y i ( W x i b ) 0 λ_i0时 1-ξ_i-y_i(Wx_ib)0 λi0时1−ξi−yi(Wxib)0 λ i 0 时 1 − ξ i − y i ( W x i b ) ≤ 0 λ_i0时 1-ξ_i-y_i(Wx_ib)≤0 λi0时1−ξi−yi(Wxib)≤0总之 λ i ≥ 0 λ_i≥0 λi≥0————① β i ξ i 0 β_iξ_i0 βiξi0 β i C − λ i 0 时 ξ i 0 β_iC-λ_i0时ξ_i0 βiC−λi0时ξi0 β i C − λ i 0 时 ξ i ≥ 0 β_iC-λ_i0时ξ_i≥0 βiC−λi0时ξi≥0总之 β i C − λ i ≥ 0 β_iC-λ_i≥0 βiC−λi≥0——————② 由①②综合得 C ≥ λ i ≥ 0 C≥λ_i≥0 C≥λi≥0
对偶补充条件是: w Σ λ i x i y i w Σλ_ix_iy_i wΣλixiyi Σ λ i y i 0 Σλ_iy_i0 Σλiyi0 C − λ i − β i 0 C-λ_i-β_i 0 C−λi−βi0
在SMO迭代时的5个步骤里,在第①③④⑤上都有各自对应的调整
①未知参数赋初值C、λ、w、b
C: 可先设置为1λλ_i全赋值为0这样即可保证 Σ λ i y i 0 Σλ_iyi0 Σλiyi0ξ ξ i 由 C − λ i 得到 ξ_i由C-λ_i得到 ξi由C−λi得到W W ∑ λ i x i ∗ y i 因此 W 也全为 0 W∑λ_ix_i*y_i因此W也全为0 W∑λixi∗yi因此W也全为0bb没有条件限制要求可以直接赋值为0
②选择2个迭代λ用λ_1,λ_2分别代表选中的2个λ λ1的选择方式选择最偏离KKT条件的λ 首先是违反KKT条件 λ i [ 1 − ξ i − y i ( W x i b ) ] 0 λ_i[1-ξ_i-y_i(Wx_ib)]0 λi[1−ξi−yi(Wxib)]0 λ i 0 时 1 − ξ i − y i ( W x i b ) 0 λ_i0时 1-ξ_i-y_i(Wx_ib)0 λi0时1−ξi−yi(Wxib)0 λ i 0 时 1 − ξ i − y i ( W x i b ) ≤ 0 λ_i0时 1-ξ_i-y_i(Wx_ib)≤0 λi0时1−ξi−yi(Wxib)≤0 其次违反程度通过 m a x : 1 − ξ − y ( w x b ) max:1-ξ-y(wxb) max:1−ξ−y(wxb)值来衡量即选择 m a x : 1 − ξ − y ( w x b ) max:1-ξ-y(wxb) max:1−ξ−y(wxb)下的 λ i λ_i λi 但建议还是将违反KKT条件的程度降序排列得到一个违反KKT条件的 1 − ξ − y ( w x b ) 1-ξ-y(wxb) 1−ξ−y(wxb)降序列表 这样如果 1 − ξ − y ( w x b ) 1-ξ-y(wxb) 1−ξ−y(wxb)的最大值对应的λ1不满足迭代条件时还可以退而求其次选 1 − ξ − y ( w x b ) 1-ξ-y(wxb) 1−ξ−y(wxb)第二大对应的λ1 【判断1】若选不到λ1说明所有λ都满足KKT条件可停止SMO算法 λ2的选择方式选择能使λ2改变最大的λ 公式推导出的 λ 2 n e w λ 2 o l d y i ∗ ( E 1 − E 2 ) K 11 K 22 − 2 K 12 λ2_{new}λ2_{old}\frac{y_i*(E1-E2)}{K11K22-2K12} λ2newλ2oldK11K22−2K12yi∗(E1−E2) 当 ∣ E 1 − E 2 ∣ 大 |E1-E2|大 ∣E1−E2∣大说明这两条对应的数据差距比较大【后续再公式推导】【判断1】若当前|E1-E2|最大的λ2不满足条件要求则重选λ即退而求其次选|E1-E2|第二大对应的λ2【判断2】若选不到λ2则重新选λ1再选λ2 重选λ1是指选下一个偏离KKT条件的λ而不是最偏离了【降序选择λ1】
最终整理出 λ 2 λ 2 o l d y 2 ∗ ( E 1 − E 2 ) x 1. x 1 x 2. x 2 − 2 x 1. x 2 λ2 λ_{2old}\frac{y2*(E1-E2)}{x1.x1x2.x2-2x1.x2} λ2λ2oldx1.x1x2.x2−2x1.x2y2∗(E1−E2)
③求解迭代后的λ并判断是否满足迭代条件
条件1λ≥0即求解出的λ1、λ2都要满足 C ≥ λ ≥ 0 C≥λ≥0 C≥λ≥0的条件
通过上一步可得到 λ 2 λ 2 o l d y 2 ∗ ( E 1 − E 2 ) x 1. x 1 x 2. x 2 − 2 x 1. x 2 λ2 λ_{2old}\frac{y2*(E1-E2)}{x1.x1x2.x2-2x1.x2} λ2λ2oldx1.x1x2.x2−2x1.x2y2∗(E1−E2)
因此可先判断 0 ≤ λ 2 ≤ C 0≤λ2≤C 0≤λ2≤C ————①
接着判断λ1由 C ≥ λ 1 − λ 2 y 1 y 2 − A y 1 ≥ 0 C≥λ_1 -λ_2y_1y_2-Ay_1≥0 C≥λ1−λ2y1y2−Ay1≥0可得 当 y 1 y 2 1 时 C ≥ − λ 2 − A y 1 ≥ 0 当y1y2 1时C≥ -λ_2-Ay_1≥0 当y1y21时C≥−λ2−Ay1≥0 C A y 1 ≤ λ 2 ≤ − A y 1 CAy_1≤λ_2≤-Ay_1 CAy1≤λ2≤−Ay1 结合上式①得λ2最终的取值范围 m a x ( 0 , C A y 1 ) ≤ λ 2 ≤ m i n ( C , − A y 1 ) max(0,CAy_1)≤λ_2≤min(C,-Ay_1) max(0,CAy1)≤λ2≤min(C,−Ay1)简化为 L ≤ λ 2 ≤ H L≤λ_2≤H L≤λ2≤H 当 y 1 y 2 − 1 时 C A y 1 ≥ λ 2 ≥ A y 1 当y1y2 -1时CAy_1≥λ2≥Ay_1 当y1y2−1时CAy1≥λ2≥Ay1 ——————② 结合上式①得λ2最终的取值范围 m a x ( 0 , A y 1 ) ≤ λ 2 ≤ m i n ( C , C A y 1 ) max(0,Ay_1)≤λ_2≤min(C,CAy_1) max(0,Ay1)≤λ2≤min(C,CAy1)简化为 L ≤ λ 2 ≤ H L≤λ_2≤H L≤λ2≤H 如果满足 L ≤ λ 2 ≤ H L≤λ_2≤H L≤λ2≤H则继续往下如果不满足条件则直接剪枝后再继续往下 当λ2H时使λ2H当λ2L时使λ2L
④计算当前的 W n e w , b n e w W_{new},b_{new} Wnew,bnew
计算出满足λ≥0的λ1和λ2后可代入求解最新的 W n e w W_{new} Wnew W o l d λ 1 o l d y 1 x 1 λ 2 o l d y 2 x 2 ∑ i 3 n λ i y i x i W_{old} λ_{1old}y_1x_1λ_{2old}y_2x_2∑^n_{i3}λ_iy_ix_i Woldλ1oldy1x1λ2oldy2x2∑i3nλiyixi W n e w λ 1 y 1 x 1 λ 2 y 2 x 2 ∑ i 3 n λ i y i x i W_{new} λ_{1}y_1x_1λ_{2}y_2x_2∑^n_{i3}λ_iy_ix_i Wnewλ1y1x1λ2y2x2∑i3nλiyixi
则 W n e w W o l d ( λ 1 − λ 1 o l d ) y 1 x 1 ( λ 2 − λ 2 o l d ) y 2 x 2 W_{new} W_{old}(λ_{1}-λ_{1old})y_1x_1(λ_{2}-λ_{2old})y_2x_2 WnewWold(λ1−λ1old)y1x1(λ2−λ2old)y2x2
可见每次W的更新都只与选择的两个λ有关 b n e w b_{new} bnew表示两条边界上的b1和b2的中间值
怎么判断是不是边界呢
其实也就是当λ0的时候因此λ0则g(w,b)0这在之前的拉格朗日乘数法中已证明为支持向量即边界
因此则当λ1、λ2均大于0且小于C时根据 g ( w , b ) 1 − ξ i − y i ( W n e w x i b ) 0 g(w,b) 1-ξ_i-y_i(W_{new}x_ib) 0 g(w,b)1−ξi−yi(Wnewxib)0
要求松弛变量 ξ i ξ_i ξi同时为0则 β i 0 β_i0 βi0,即 C − λ i 0 C-λ_i0 C−λi0
综合得 当 0λC时该数据为支持向量上的边界点则可以求出b
求出 b 1 n e w y 1 − W n e w x 1 b_{1new} y_1-W_{new}x_1 b1newy1−Wnewx1 b 2 n e w y 2 − W n e w x 2 b_{2new} y_2-W_{new}x_2 b2newy2−Wnewx2
则 b n e w b 1 n e w b 2 n e w 2 b_{new} \frac{b_{1new}b_{2new}}{2} bnew2b1newb2new
⑤若全部满足KKT条件或达到迭代次数则停止SMO算法
增加软间隔后的分类速度其实很快而且准确率相对高一点点儿
代码改动量不大主要只需要改动的是计算出新的λ时要进行判断和剪枝
import numpy as np
import pandas as pd
import random
import matplotlib.pyplot as plt
import time
# 获取所需数据
datas pd.read_excel(./datas6.xlsx)
important_features [推荐分值,专业度,推荐类型]
# datas pd.read_excel(./datas5.xlsx)
# important_features [推荐分值,推荐类型]datas_1 datas[important_features].head(100)
Y datas_1[推荐类型]
X datas_1.drop(推荐类型,axis1)
X_features X.columns
Y_features 推荐类型
rows,columns datas_1.shapeYY.where(Y!高推荐,other1) # 高推荐设置为1
YY.where(Y!低推荐,other-1) # 低推荐设置为-1class SMO():def __init__(self,X,Y):self.X Xself.Y Yself.C 1self.m X.shape[1]self.n Y.shape[0]self.lamb np.zeros(self.n)self.β self.C-self.lambself.b 0self.W0 np.zeros(self.m)self.times 5self.Finish Falseself.break_kkt {}self.break_kkt_list []self.E Nonedef count_break_KKT(self):del self.break_kktself.break_kkt {}self.g 1-self.Y*((self.W0*self.X).sum(axis1)self.b)# time.sleep(3)for index,g_value in self.g.items():a self.lamb[index]if a 0:raise Exception(flamb1_new为{self.lamb1_new},还是小于0)elif a 0 and g_value0:self.break_kkt[index] abs(g_value)elif a 0 and g_value!0:self.break_kkt[index] abs(g_value)def run(self):select_lamb1 Falsewhile not self.Finish and self.times0:if len(self.break_kkt_list) 0:self.count_break_KKT()self.break_kkt_list sorted(self.break_kkt.items(), keylambda d: d[1], reverseTrue)if len(self.break_kkt_list) 0:print(已全部满足KKT)break# print(f当前违反KKT条件的{self.break_kkt_list})# time.sleep(3)index1 self.break_kkt_list.pop(0)[0]x1 self.X.iloc[index1]y1 self.Y[index1]lamb1_old self.lamb[index1]self.E (self.W0 * self.X).sum(axis1) self.b - self.Ye1 self.E[index1]self.E1E2_all e1-self.Eself.E1E2_abs (e1-self.E).abs()self.E1E2_sort sorted(self.E1E2_abs.items(), keylambda d: d[1], reverseTrue)# print(f当前的E1E2排序{self.E1E2_sort})# time.sleep(3)self.times - 1for j in self.E1E2_sort:index2 j[0]x2 self.X.iloc[index2]y2 self.Y[index2]lamb2_old self.lamb[index2]e1_e2 self.E1E2_all[index2]# print(f选中的第{index1}和第{index2}的E差值为{e1_e2},参数{self.lamb[index1], self.lamb[index2]})# time.sleep(3)if e1_e2 0:# print(f由于两者的E差值为0因此不进行迭代)select_lamb1 Truebreaktemp sum(x1*x1x2*x2-2*x1*x2)A -lamb1_old*y1-lamb2_old*y2if temp0:continuelamb2_new lamb2_old e1_e2*y2/tempif y1*y2 1:L max(0,-self.C-A*y1,)H min(self.C,-A*y1)if lamb2_newL:lamb2_new Lelif lamb2_newH:lamb2_new Helif lamb2_newH and lamb2_newL:passelse:print(怎么H还比L小呢)self.Finish Truebreakelif y1*y2 -1:L max(0,A*y1)H min(self.C,self.CA*y1)if lamb2_newL:lamb2_new Lelif lamb2_newH:lamb2_new Helif lamb2_newH and lamb2_newL:passelse:print(怎么H还比L小呢)self.Finish Truebreaklamb1_new -lamb2_new*y1*y2-A*y1time.sleep(3)self.W0 self.W0(lamb1_new-lamb1_old)*y1*x1(lamb2_new-lamb2_old)*y2*x2self.W0 np.array(self.W0)if 0lamb1_new and lamb1_newself.C:b1_new y1-sum(self.W0*x1)if 0 lamb2_new and lamb2_new self.C:b2_new y2-sum(self.W0*x2)self.b np.array((b1_newb2_new)/2)self.lamb[index1]lamb1_newself.lamb[index2]lamb2_newself.β[index1]self.C-lamb1_newself.β[index2]self.C-lamb2_newprint(f新的lamb:{self.lamb},\nW0为{self.W0},b为{self.b})select_lamb1 Truebreakelse:print(f可选的E2中{self.E1E2_sort}没有满足条件的lamb2)if select_lamb1:select_lamb1 Falseself.count_break_KKT()self.break_kkt_list sorted(self.break_kkt.items(), keylambda d: d[1], reverseTrue)if len(self.break_kkt_list)0:self.Finish Trueprint(已全部服从KKT条件)sum_lamb_y sum(self.lamb*self.Y)print(f汇总后的值是否为零{sum_lamb_y})print(self.lamb)breaklambs sorted([(index1,value1) for index1,value1 in enumerate(self.lamb)],keylambda x:x[1],reverseTrue)index1 lambs.pop(0)[0]for index2,value2 in enumerate(lambs):if self.Y[index1]!self.Y[index2] and value2!0:print()x1 self.X.iloc[index1]x2 self.X.iloc[index2]print(self.W0*x1)print((self.W0*x1).sum(axis0))b1_new np.array(self.Y[index1]-(self.W0*x1).sum(axis0))b2_new np.array(self.Y[index2]-(self.W0*x2).sum(axis0))b_new (b1_newb2_new)/2self.b b_newprint()breakprint(b1_new,b2_new)self.W0 np.array([self.W0])print(_________________________)print(self.W0)print(self.X)print(self.b)print(_________________________)z (self.W0*self.X).sum(axis1)self.bself.Y_pre []for i in z:if i0:self.Y_pre.append(1)elif i0:self.Y_pre.append(-1)else:print(居然还有点位于支持向量中间的点big problem)print(f分类准确率为{round(sum(self.Y_preself.Y)/self.Y.shape[0]*100,2)}%)print(_________________________)z (self.W0*self.X).sum(axis1)self.b# z1 (self.W0 * self.X).sum(axis1) b1_new# z2 (self.W0 * self.X).sum(axis1) b2_newmap_color {-1: r, 1: g}color list(map(lambda x: map_color[x], self.Y))plt.scatter(np.array(z), np.array(self.Y),ccolor)plt.show()test SMO(X,Y)
test.run()
