[关闭]
@tianxingjian 2020-11-21T23:30:46.000000Z 字数 12241 阅读 2351

机器学习

《Machine Learning in Action》—— 剖析支持向量机,优化SMO

薄雾浓云愁永昼,瑞脑销金兽。

愁的很,上次不是更新了一篇关于支持向量机的文章嘛,《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM。虽然效果还算不错,数据集基本都能够分类正确,模型训练效率的话也还说的过去,但这是基于我们训练样本数据集比较少、迭代次数比较少的前提下。

假如说我们数据集比较大,而且还需要迭代不少次数的话,上一篇文章中使用到的SMO算法的效率可就不敢恭维了,训练的速度可堪比龟龟。月黑风高夜,杀人放火天。不对不对,月黑风高夜,疯狂肝文时。既然一般的SMO算法的效率低下,那怎么说也得进一步优化才行呐。

就在前几天还听见收音机上说,国内外有许多如雷贯耳的大佬都在不断研究新算法来进一步提高SMO算法的训练效率。闻此一言,Taoye心中大喜:"如果我能蹦跶出一个新的优化算法,哥哥我声名远扬的大好机会就来了啊,雄霸天下的抱负就指日可待了啊!哈哈哈哈!!!"想法虽好,可是该怎么优化呢?在这薄雾浓云、月黑风高之夜,Taoye的思绪漫天飞,愁的很。

有心栽花花不开,无心插柳柳成荫。

明明已经知道SMO算法待优化的地方太多了,可是就是不知如何下手,想了老半天,脑阔疼的厉害。此刻实验室空无一人,Taoye转着座椅,双目望向窗外,皎洁的月光总是给人无限遐想。

罢了罢了,与其木讷在这有心栽花花不开,倒不如出去转悠转悠,说不定能捕获个意想不到的收获,给我来了无心插柳柳成荫呢?说走咱就走哇(调调有点不对劲~~),关上空调,披件外套,锁上室门,双手插袋朝外走去。

或许是空调吹太久了,亦或实验室呆太久了,出来的瞬间一股神清气爽的感觉涌上心头,五音不全的我此时还真想高歌一曲。顷之,微凉,好在出门前披了件外套。活动活动筋骨,朝湖边走去。走着走着,不知不觉来到了步行桥,风平浪静的湖面,没有一丝波纹荡起。左转,低头看着湖面中胡子拉碴且憔悴的自己,此时我的眼角又再一次。。。┭┮﹏┭┮ 。。抬头看着湖边零星几对小情侣,或有说有笑、或呢喃窃语、或打情骂俏,滋滋滋,有点儿意思,只有我只身一人还在想着如何优化SMO算法。

等会儿。。。小情侣???优化SMO???

我记得在前面那篇文章中写到的SMO算法的核心思想里,正是不断迭代成双成对的,只不过那个时候的这对“小情侣”是随意配对,所以导致的排列组合的可能性太多,从而拉低了整个模型训练的效率。假如说,我那个时候选取这对“小情侣”的时候并不是无意的,而是有意识、有条件的去选取,不就可以避开大量没必要的可能性计算么,这样一来不就可以大大提高模型的训练效率了么???

握了一棵草,乖乖,我真是个天才,这都被我想到了???心头灵光一闪,犹如饥渴春笋听到的第一声惊雷,屁颠屁颠的朝实验室跑去,而一对对小情侣异样且诧异的眼神朝我看来。。。

上述内容部分虚构,仅做引出下文之用。

在这之前,我们先静下心来分析一下上篇文章中SMO的核心算法:

上图是我们在讲解手撕线性SVM中所写到的linear_smo方法,详细请看:《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM。其中Taoye圈出了三个代码块来给大家介绍下:

第一个代码块,我们可以发现代码行为for i in range(m):,想必大家都知道这是一个循环语句,在这个方法中它具体表达的意思是根据样本数量一次选取索引,然后通过这个索引来确定的选择,所以它最终会把所有的样本都“走一遍”。

第二个代码块,是根据的值重新在中选取一个不与相同的,然后根据这个来修改对应的

第三个就是我们大量的矩阵、向量进行计算的代码块了,我们可以发现,无论前两个的选取是怎样的,第三个代码块都会去执行、计算,然而有些计算完全是没必要的,这样就大大拉跨了整个SMO算法的效率,这可不是我们想要的。

综上,我们需要在的选取上做点文章,使其在一定的跳过第三个代码块的计算。

在上一篇文章中,我们也有提到,大多数样本对于决策面的确定都是无用的,只有少数部分的样本点才能确定具体的决策面。而与样本之间满足如下关系:

对于第一个的选取,初始化的向量为0,所以第一次迭代是对所有的样本点进行。待第一次迭代完成之后,此时的向量已经更新完成了,在之后的迭代过程中,我们就不需要对所有的样本进行遍历了,而是选取在区间的值即可,因为其他的值对于最终决策面的确定没有什么影响。

对于第一个的选取,核心代码思想如下所示,也就是我们的外层循环。其中data_struct是一个数据结构,其内部保存了一些公有地的属性,这个我们后面会讲:

  1. """
  2. Author:Taoye
  3. 微信公众号:玩世不恭的Coder
  4. Explain:外层循环,选取第一个合适alpha
  5. Parameters:
  6. x_data: 样本属性特征矩阵
  7. y_label: 属性特征对应的标签
  8. C:惩罚参数
  9. toler:容错率
  10. max_iter:迭代次数
  11. Return:
  12. b: 决策面的参数b
  13. alphas:获取决策面参数w所需要的alphas
  14. """
  15. def outer_smo(self, data_struct, x_data, y_label, C, toler, max_iter):
  16. iter_num, ergodic_flag, alpha_optimization_num = 0, True, 0
  17. while (iter_num < max_iter) and ((alpha_optimization_num > 0) or (ergodic_flag)):
  18. alpha_optimization_num = 0
  19. if ergodic_flag:
  20. for i in range(data_struct.m):
  21. alpha_optimization_num += self.inner_smo(i, data_struct)
  22. print("遍历所有样本数据:第%d次迭代,样本为:%d,alpha优化的次数:%d" % (iter_num, i, alpha_optimization_num))
  23. iter_num += 1
  24. else:
  25. no_zero_index = np.nonzero((data_struct.alphas.A > 0) * (data_struct.alphas.A < C))[0]
  26. for i in no_zero_index:
  27. alpha_optimization_num += self.inner_smo(i, data_struct)
  28. print("非边界遍历样本数据:第%d次迭代,样本为:%d,alpha优化的次数:%d" % (iter_num, i, alpha_optimization_num))
  29. iter_num += 1
  30. if ergodic_flag: ergodic_flag = False
  31. elif alpha_optimization_num == 0: ergodic_flag = True
  32. print("迭代次数:%d" % iter_num)
  33. return data_struct.b, data_struct.alphas

对于第二个,我们不妨先分析一下前篇文章中SMO算法最终优化之后的

我们可以发现主要是靠更新迭代来进行优化,而是已知的,我们没有选择的权利,但是这一部分的值我们是可控的,也就是说我们要选择合适的来使得后一部分的值尽可能的大,从而达到快速修改向量的目的,才能更快速的实现训练饱和。

简单来说就是的变化依赖于,当该绝对值越大,的变化也就越大。也就是说,为正的时候,我们的要选择尽可能小的为负的时候,我们要选择尽可能大的。根据这个思想我们就能让这对“小情侣”完美的配对了,美滋滋~~

对于第一个的选取,核心代码思想如下所示,也就是我们的内层循环的所需要选取内容:

  1. def select_appropriate_j(self, i, data_struct, E_i):
  2. max_k, max_delta_E, E_j = -1, 0, 0
  3. data_struct.E_cache[i] = [1, E_i]
  4. valid_E_cache_list = np.nonzero(data_struct.E_cache[:, 0].A)[0]
  5. if (len(valid_E_cache_list) > 1):
  6. for k in valid_E_cache_list:
  7. if k == i: continue
  8. E_k = self.calc_E(data_struct.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, k)
  9. delta_E = abs(E_i - E_k)
  10. if (delta_E > max_delta_E): max_k, max_delta_E, E_j = k, delta_E, E_k
  11. return max_k, E_j
  12. else:
  13. j = self.random_select_alpha_j(i, data_struct.m)
  14. E_j = self.calc_E(data_struct.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, j)
  15. return j, E_j

为了方便我们使用有关数据集和模型的一些公共资源,以及方便对它们进行操作,我们需要单独封装一个数据结构(当然了,不封装也没什么问题),该数据结构有关属性解释如下:

  1. x_data:etablish_data随机生成数据集中的属性矩阵
  2. y_label:etablish_data随机生成数据集中的标签
  3. C:惩罚参数
  4. toler:容错率
  5. m:数据样本数
  6. alphas:SMO算法所需要训练的向量
  7. b:SMO算法所需要训练的参数
  8. E_cache:用于保存误差,第一列为有效标志位,第二列为样本索引对应的误差E

此外,为了提高代码的扩展性和灵活性,还单独抽离了一个方法update_E_k,主要用于更新data_struct对象中的E_cache属性:

  1. def update_E_k(self, data_struct, k):
  2. E_k = self.calc_E(data_struct.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, k) #计算Ek
  3. data_struct.E_cache[k] = [1,E_k]

完整代码:

  1. import numpy as np
  2. import pylab as pl
  3. from matplotlib import pyplot as plt
  4. class DataStruct:
  5. def __init__(self, x_data, y_label, C, toler):
  6. self.x_data = x_data
  7. self.y_label = y_label
  8. self.C = C
  9. self.toler = toler
  10. self.m = x_data.shape[0]
  11. self.alphas = np.mat(np.zeros((self.m, 1)))
  12. self.b = 0
  13. self.E_cache = np.mat(np.zeros((self.m, 2)))
  14. class OptimizeLinearSVM:
  15. def __init__(self):
  16. pass
  17. """
  18. Author: Taoye
  19. 微信公众号: 玩世不恭的Coder
  20. Explain: 用于生成训练数据集
  21. Parameters:
  22. data_number: 样本数据数目
  23. Return:
  24. x_data: 数据样本的属性矩阵
  25. y_label: 样本属性所对应的标签
  26. """
  27. def etablish_data(self, data_number):
  28. np.random.seed(38)
  29. x_data = np.concatenate((np.add(np.random.randn(data_number, 2), [3, 3]),
  30. np.subtract(np.random.randn(data_number, 2), [3, 3])),
  31. axis = 0) # random随机生成数据,+ -3达到不同类别数据分隔的目的
  32. temp_data = np.zeros([data_number])
  33. temp_data.fill(-1)
  34. y_label = np.concatenate((temp_data, np.ones([data_number])), axis = 0)
  35. return x_data, y_label
  36. """
  37. Author: Taoye
  38. 微信公众号: 玩世不恭的Coder
  39. Explain: 随机选取alpha_j
  40. Parameters:
  41. alpha_i_index: 第一个alpha的索引
  42. alpha_number: alpha总数目
  43. Return:
  44. alpha_j_index: 第二个alpha的索引
  45. """
  46. def random_select_alpha_j(self, alpha_i_index, alpha_number):
  47. alpha_j_index = alpha_i_index
  48. while alpha_j_index == alpha_i_index:
  49. alpha_j_index = np.random.randint(0, alpha_number)
  50. return alpha_j_index
  51. """
  52. Author: Taoye
  53. 微信公众号: 玩世不恭的Coder
  54. Explain: 使得alpha_j在[L, R]区间之内
  55. Parameters:
  56. alpha_j: 原始alpha_j
  57. L: 左边界值
  58. R: 右边界值
  59. Return:
  60. L,R,alpha_j: 修改之后的alpha_j
  61. """
  62. def modify_alpha(self, alpha_j, L, R):
  63. if alpha_j < L: return L
  64. if alpha_j > R: return R
  65. return alpha_j
  66. """
  67. Author: Taoye
  68. 微信公众号: 玩世不恭的Coder
  69. Explain: 计算误差并返回
  70. """
  71. def calc_E(self, alphas, y_label, x_data, b, i):
  72. f_x_i = float(np.dot(np.multiply(alphas, y_label).T, x_data * x_data[i, :].T)) + b
  73. return f_x_i - float(y_label[i])
  74. """
  75. Author: Taoye
  76. 微信公众号: 玩世不恭的Coder
  77. Explain: 计算eta并返回
  78. """
  79. def calc_eta(self, x_data, i, j):
  80. eta = 2.0 * x_data[i, :] * x_data[j, :].T \
  81. - x_data[i, :] * x_data[i, :].T \
  82. - x_data[j, :] * x_data[j,:].T
  83. return eta
  84. """
  85. Author: Taoye
  86. 微信公众号: 玩世不恭的Coder
  87. Explain: 计算b1, b2并返回
  88. """
  89. def calc_b(self, b, x_data, y_label, alphas, alpha_i_old, alpha_j_old, E_i, E_j, i, j):
  90. b1 = b - E_i \
  91. - y_label[i] * (alphas[i] - alpha_i_old) * x_data[i, :] * x_data[i, :].T \
  92. - y_label[j] * (alphas[j] - alpha_j_old) * x_data[i, :] * x_data[j, :].T
  93. b2 = b - E_j \
  94. - y_label[i] * (alphas[i] - alpha_i_old) * x_data[i, :] * x_data[j, :].T \
  95. - y_label[j] * (alphas[j] - alpha_j_old) * x_data[j, :] * x_data[j, :].T
  96. return b1, b2
  97. def select_appropriate_j(self, i, data_struct, E_i):
  98. max_k, max_delta_E, E_j = -1, 0, 0
  99. data_struct.E_cache[i] = [1, E_i]
  100. valid_E_cache_list = np.nonzero(data_struct.E_cache[:, 0].A)[0]
  101. if (len(valid_E_cache_list) > 1):
  102. for k in valid_E_cache_list:
  103. if k == i: continue
  104. E_k = self.calc_E(data_struct.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, k)
  105. delta_E = abs(E_i - E_k)
  106. if (delta_E > max_delta_E): max_k, max_delta_E, E_j = k, delta_E, E_k
  107. return max_k, E_j
  108. else:
  109. j = self.random_select_alpha_j(i, data_struct.m)
  110. E_j = self.calc_E(data_struct.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, j)
  111. return j, E_j
  112. def update_E_k(self, data_struct, k):
  113. E_k = self.calc_E(data_struct.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, k) #计算Ek
  114. data_struct.E_cache[k] = [1,E_k]
  115. """
  116. Author: Taoye
  117. 微信公众号: 玩世不恭的Coder
  118. Explain: smo内层
  119. """
  120. def inner_smo(self, i, data_strcut):
  121. E_i = self.calc_E(data_strcut.alphas, data_struct.y_label, data_struct.x_data, data_struct.b, i) # 调用calc_E方法计算样本i的误差
  122. if ((data_struct.y_label[i] * E_i < -data_struct.toler) and (data_struct.alphas[i] < data_struct.C)) or ((data_struct.y_label[i] * E_i > data_struct.toler) and (data_struct.alphas[i] > 0)):
  123. j, E_j = self.select_appropriate_j(i, data_strcut, E_i) # 选取一个恰当的j
  124. alpha_i_old, alpha_j_old = data_struct.alphas[i].copy(), data_struct.alphas[j].copy()
  125. if (data_struct.y_label[i] != data_struct.y_label[j]): # 确保alphas在[L, R]区间内
  126. L, R = max(0, data_struct.alphas[j] - data_struct.alphas[i]), min(data_struct.C, data_struct.C + data_struct.alphas[j] - data_struct.alphas[i])
  127. else:
  128. L, R = max(0, data_struct.alphas[j] + data_struct.alphas[i] - data_struct.C), min(data_struct.C, data_struct.alphas[j] + data_struct.alphas[i])
  129. if L == R: print("L==R"); return 0 # L==R时选取下一个样本
  130. eta = self.calc_eta(data_struct.x_data, i, j) # 计算eta值
  131. if eta >= 0: print("eta>=0"); return 0
  132. data_struct.alphas[j] -= data_struct.y_label[j] * (E_i - E_j) / eta
  133. data_struct.alphas[j] = self.modify_alpha(data_struct.alphas[j], L, R) # 修改alpha[j]
  134. self.update_E_k(data_strcut, j)
  135. if (abs(data_strcut.alphas[j] - alpha_j_old) < 0.000001): print("alpha_j修改太小了"); return 0
  136. data_struct.alphas[i] += data_strcut.y_label[j] * data_strcut.y_label[i] * (alpha_j_old - data_strcut.alphas[j])
  137. self.update_E_k(data_strcut, i)
  138. b1, b2= self.calc_b(data_struct.b, data_struct.x_data, data_struct.y_label, data_struct.alphas, alpha_i_old, alpha_j_old, E_i, E_j, i, j) # 计算b值
  139. if (0 < data_struct.alphas[i]) and (data_struct.C > data_struct.alphas[i]): data_struct.b = b1
  140. elif (0 < data_struct.alphas[j]) and (data_struct.C > data_struct.alphas[j]): data_struct.b = b2
  141. else: data_struct.b = (b1 + b2)/2.0
  142. return 1
  143. else: return 0
  144. """
  145. Author:Taoye
  146. 微信公众号:玩世不恭的Coder
  147. Explain:外层循环,选取第一个合适alpha
  148. Parameters:
  149. x_data: 样本属性特征矩阵
  150. y_label: 属性特征对应的标签
  151. C:惩罚参数
  152. toler:容错率
  153. max_iter:迭代次数
  154. Return:
  155. b: 决策面的参数b
  156. alphas:获取决策面参数w所需要的alphas
  157. """
  158. def outer_smo(self, data_struct, x_data, y_label, C, toler, max_iter):
  159. iter_num, ergodic_flag, alpha_optimization_num = 0, True, 0
  160. while (iter_num < max_iter) and ((alpha_optimization_num > 0) or (ergodic_flag)):
  161. alpha_optimization_num = 0
  162. if ergodic_flag:
  163. for i in range(data_struct.m):
  164. alpha_optimization_num += self.inner_smo(i, data_struct)
  165. print("遍历所有样本数据:第%d次迭代,样本为:%d,alpha优化的次数:%d" % (iter_num, i, alpha_optimization_num))
  166. iter_num += 1
  167. else:
  168. no_zero_index = np.nonzero((data_struct.alphas.A > 0) * (data_struct.alphas.A < C))[0]
  169. for i in no_zero_index:
  170. alpha_optimization_num += self.inner_smo(i, data_struct)
  171. print("非边界遍历样本数据:第%d次迭代,样本为:%d,alpha优化的次数:%d" % (iter_num, i, alpha_optimization_num))
  172. iter_num += 1
  173. if ergodic_flag: ergodic_flag = False
  174. elif alpha_optimization_num == 0: ergodic_flag = True
  175. print("迭代次数:%d" % iter_num)
  176. return data_struct.b, data_struct.alphas
  177. """
  178. Author: Taoye
  179. 微信公众号: 玩世不恭的Coder
  180. Explain: 根据公式计算出w权值向量
  181. Parameters:
  182. x_data: 样本属性特征矩阵
  183. y_label: 属性特征对应的标签
  184. alphas:linear_smo方法所返回的alphas向量
  185. Return:
  186. w: 决策面的参数w
  187. """
  188. def calc_w(self, x_data, y_label, alphas):
  189. x_data, y_label, alphas = np.array(x_data), np.array(y_label), np.array(alphas)
  190. return np.dot((np.tile(y_label.reshape(1, -1).T, (1, 2)) * x_data).T, alphas).tolist()
  191. """
  192. Author: Taoye
  193. 微信公众号: 玩世不恭的Coder
  194. Explain: 绘制出分类结果
  195. Parameters:
  196. x_data: 样本属性特征矩阵
  197. y_label: 属性特征对应的标签
  198. w:决策面的w参数
  199. b:决策面的参数b
  200. """
  201. def plot_result(self, x_data, y_label, w, b):
  202. data_number, _ = x_data.shape; middle = int(data_number / 2)
  203. plt.scatter(x_data[:, 0], x_data[:, 1], c = y_label, cmap = pl.cm.Paired)
  204. x1, x2 = np.max(x_data), np.min(x_data)
  205. w1, w2 = w[0][0], w[1][0]
  206. y1, y2 = (-b - w1 * x1) / w2, (-b - w1 * x2) / w2
  207. plt.plot([float(x1), float(x2)], [float(y1), float(y2)]) # 绘制决策面
  208. for index, alpha in enumerate(alphas):
  209. if alpha > 0:
  210. b_temp = - w1 * x_data[index][0] - w2 * x_data[index][1]
  211. y1_temp, y2_temp = (-b_temp - w1 * x1) / w2, (-b_temp - w1 * x2) / w2
  212. plt.plot([float(x1), float(x2)], [float(y1_temp), float(y2_temp)], "k--") # 绘制支持向量
  213. plt.scatter(x_data[index][0], x_data[index][1], s=150, c='none', alpha=0.7, linewidth=2, edgecolor='red') # 圈出支持向量
  214. plt.show()
  215. if __name__ == '__main__':
  216. optimize_linear_svm = OptimizeLinearSVM()
  217. x_data, y_label = optimize_linear_svm.etablish_data(50)
  218. data_struct = DataStruct(np.mat(x_data), np.mat(y_label).T, 0.8, 0.00001)
  219. b, alphas = optimize_linear_svm.outer_smo(data_struct, x_data, y_label, data_struct.C, data_struct.toler, 10)
  220. w = optimize_linear_svm.calc_w(x_data, y_label, alphas)
  221. optimize_linear_svm.plot_result(x_data, y_label, w, b)

优化后的分类结果:

这期的内容没那么多,主要是优化了一下上期内容中的SMO算法,从而在一定程度上提高模型的训练效率,由于是手动实现该线性SVM算法,所以模型可能达不到那些框架内置的性能,有兴趣的读者可自行慢慢优化。

关于线性SVM应该就暂时写到这里了,后期的话应该会更新非线性相关的内容。

我是Taoye,爱专研,爱分享,热衷于各种技术,学习之余喜欢下象棋、听音乐、聊动漫,希望借此一亩三分地记录自己的成长过程以及生活点滴,也希望能结实更多志同道合的圈内朋友,更多内容欢迎来访微信公主号:玩世不恭的Coder

参考资料:

[1] 《机器学习实战》:Peter Harrington 人民邮电出版社
[2] 《统计学习方法》:李航 第二版 清华大学出版社

推荐阅读

《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM
print( "Hello,NumPy!" )
干啥啥不行,吃饭第一名
Taoye渗透到一家黑平台总部,背后的真相细思极恐
《大话数据库》-SQL语句执行时,底层究竟做了什么小动作?
那些年,我们玩过的Git,真香
基于Ubuntu+Python+Tensorflow+Jupyter notebook搭建深度学习环境
网络爬虫之页面花式解析
手握手带你了解Docker容器技术
一文详解Hexo+Github小白建站
​打开ElasticSearch、kibana、logstash的正确方式

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注