06-SVM.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 一、SVM原理推导"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1、函数间隔(Function margin)与几何间隔(geometrical margin)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义超平面：$$w^{*} \\cdot x+b^{*}=0$$\n",
    "\n",
    "对点$(x_i,y_i)$:\n",
    "\n",
    "函数间隔(Function margin)：$$\\hat{\\gamma}_{i}=y_{i}\\left(w \\cdot x_{i}+b\\right)$$\n",
    "\n",
    "几何间隔(geometrical margin)：$$\\gamma_{i}=y_{i}\\left(\\frac{w \\cdot x_{i}+{b}}{\\|w\\|}\\right)$$\n",
    "\n",
    "两者关系：\n",
    "$$\n",
    "\\gamma=\\frac{\\hat{\\gamma}}{\\|w\\|}\n",
    "$$\n",
    "令超平面对于所有点$(x_i,y_i)$的函数间隔最小：\n",
    "$$\n",
    "\\hat{\\gamma}=\\min _{l=1, \\cdots, N} \\hat{\\gamma}_{i}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2、间隔最大化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "令几何间隔最大（间隔最小点的间隔最大）:\n",
    "$$\n",
    "\\max _{w, b} \\gamma\n",
    "$$\n",
    "约束条件：超平面关于每个训练样本的几何间隔至少是$\\gamma$\n",
    "$$\n",
    "s.t. \\quad y_{i}\\left(\\frac{w\\cdot x_{i}+b}{\\|w\\|}\\right) \\geqslant \\gamma, \\quad i=1,2, \\cdots, N\n",
    "$$\n",
    "根据几何间隔与函数间隔关系，可改写为：\n",
    "$$\n",
    "\\begin{array}{cc}{\\max _{w, b}} & {\\frac{\\hat{\\gamma}}{\\|w\\|}} \\\\ {\\text { s.t. }} & {y_{i}\\left(w \\cdot x_{i}+b\\right) \\geqslant \\hat{\\gamma}, \\quad i=1,2, \\cdots, N}\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "因为函数间隔$\\hat{\\gamma}$与$w、b$等比改变，所以对优化问题无影响，故令$\\hat{\\gamma}=1$：\n",
    "$$\n",
    "\\begin{array}{ll}{\\min _{w, b}} & {\\frac{1}{2}\\|w\\|^{2}} \\\\ {\\text { s.t. }} & {y_{i}\\left(w \\cdot x_{i}+b\\right)-1 \\geqslant 0, \\quad i=1,2, \\cdots, N}\\end{array}\n",
    "$$\n",
    "注:决定超平面划分的只有到超平面最近的几个点（即支持向量support vector）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3、Lagrange function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "补充：KKT条件：\n",
    "\n",
    "$\\min f(x)$\n",
    "\n",
    "$s.t. g_i(x) \\leqslant 0,  i=1,\\cdots,k$\n",
    "\n",
    "构造拉格朗日函数：$L（x,\\alpha）= f(x) + \\sum \\alpha_i \\cdot g_i(x)$\n",
    "\n",
    "（1） 拉格朗日函数对各参数求导=0\n",
    "\n",
    "（2） $\\alpha_i\\geqslant 0$\n",
    "\n",
    "（3） $\\alpha_i \\cdot g_i(x) = 0$\n",
    "\n",
    "（4） $g_i(x) \\leqslant 0$   （原始约束条件）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  引入拉格朗日乘子$\\alpha_i$后："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "$$\n",
    "L(w, b, \\alpha)=\\frac{1}{2}\\|w\\|^{2}-\\sum_{i=1}^{N} \\alpha_{i} y_{i}\\left(w \\cdot x_{i}+b\\right)+\\sum_{i=1}^{N} \\alpha_{i}\n",
    "$$\n",
    "即优化问题改为：\n",
    "$$\n",
    "\\min _{w, b}\\max _{a}  L(w, b, \\alpha)\n",
    "$$\n",
    "因为$\\min \\max f(x)\\geqslant \\max \\min f(x)$,所以等价于\n",
    "$$\n",
    "\\max _{a} \\min _{w, b} L(w, b, \\alpha)\n",
    "$$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### （1）求$\\min _{w, b} L(w, b, \\alpha)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分别对$w、b$求偏导并令其等于0：\n",
    "$$\n",
    "\\begin{array}{l}{\\nabla_{w} L(w, b, \\alpha)=w-\\sum_{i=1}^{N} \\alpha_{i} y_{i} x_{i}=0} \\\\ {\\nabla_{b} L(w, b, \\alpha)=\\sum_{i=1}^{N} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "得到：\n",
    "$$\n",
    "\\begin{array}{l}{w=\\sum_{i=1}^{N} \\alpha_{i} y_{i} x_{i}} \\\\ {\\sum_{i=1}^{N} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "将两项带回原式：\n",
    "$$\n",
    "\\begin{aligned} L(w, b, \\alpha) &=\\frac{1}{2} \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\alpha_{i} \\alpha_{j} y_{i} y_{j}\\left(x_{i} \\cdot x_{j}\\right)-\\sum_{i=1}^{N} \\alpha_{i} y_{i}\\left(\\left(\\sum_{j=1}^{N} \\alpha_{j} y_{j} x_{j}\\right) \\cdot x_{i}+b\\right)+\\sum_{i=1}^{N} \\alpha_{i} \\\\ &=-\\frac{1}{2} \\sum_{i=1}^{N} \\sum_{I=1}^{N} \\alpha_{i} \\alpha_{j} y_{i} y_{j}\\left(x_{i} \\cdot x_{j}\\right)+\\sum_{i=1}^{N} \\alpha_{i} \\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### （2）求 $\\min _{w, b} L(w, b, \\alpha)$对$\\alpha$极大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{l}\\max _\\alpha \\quad -\\frac{1}{2} \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\alpha_{i} \\alpha_{j} y_{i} y_{j}\\left(x_{i} \\cdot x_{j}\\right)+\\sum_{i=1}^{N} \\alpha_{i}\\\\ {\\text { s.t. }\\quad \\quad \\sum_{i=1}^{N} \\alpha_{l} y_{i}=0} \\\\ {\\alpha_{i} \\geqslant 0, \\quad i=1,2, \\cdots, N}\\end{array}\n",
    "$$\n",
    "改为极小问题：\n",
    "$$\n",
    "\\min _{\\alpha} \\frac{1}{2} \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\alpha_{i} \\alpha_{j} y_{i} y_{j}\\left(x_{i} \\cdot x_{j}\\right)-\\sum_{i=1}^{N} \\alpha_{i}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4、松弛变量 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "某些噪音不能满足函数间隔大于1的约束条件，因此引入松弛变量$\\xi_i \\geqslant 0$,约束条件变为：\n",
    "$$\n",
    "y_{i}\\left(w \\cdot x_{i}+b\\right) \\geqslant 1-\\xi_{i}\n",
    "$$\n",
    "$$\n",
    "\\xi_{i} \\geqslant 0, \\quad i=1,2, \\cdots, N\n",
    "$$\n",
    "目标函数变为，其中C为惩罚参数：\n",
    "$$\n",
    "\\frac{1}{2}\\|w\\|^{2}+C \\sum_{i=1}^{N} \\xi_{i}\n",
    "$$\n",
    "加入松弛变量后拉格朗日函数为：\n",
    "$$\n",
    "L(w, b, \\xi, \\alpha, \\mu) \\equiv \\frac{1}{2}\\|w\\|^{2}+C \\sum_{i=1}^{N} \\xi_{i}-\\sum_{i=1}^{N} \\alpha_{i}\\left(y_{i}\\left(w \\cdot x_{i}+b\\right)-1+\\xi_{i}\\right)-\\sum_{i=1}^{N} \\mu_{i} \\xi_{i}\n",
    "$$\n",
    "同上求对偶问题后，最终解为：（具体推导见书P110-111）\n",
    "$$\n",
    "\\min _{a} \\frac{1}{2} \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\alpha_{i} \\alpha_{j} y_{i} y_{j}\\left(x_{i} \\cdot x_{j}\\right)-\\sum_{i=1}^{N} \\alpha_{t}\n",
    "$$\n",
    "$$\n",
    "s.t. \\quad \\sum_{i=1}^{N} \\alpha_{i} y_{i}=0\n",
    "$$\n",
    "$$\n",
    "0 \\leqslant \\alpha_{i} \\leqslant C, \\quad i=1,2, \\cdots, N\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "之后求得满足约束并找到最优解的$\\alpha$即可，之后通过$w$的计算公式根据$\\alpha$求得，而$w$知道后将$w$带入$wx+b=0$也可求得$b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5、核函数 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1、将线性不可分的数据升维\n",
    "\n",
    "2、减少计算量\n",
    "我们看min后面这个式子，其中α和y都是标量，直接计算就可以，唯一让人难受的是xi与xj的点积，它是向量之间的点积，同时前面有求和项，也就是说在计算过程中是需要计算任意两个向量之间的点积的。这里就引申出一个问题，例如在Mnist数据集中，训练集有6万个样本，也就是6万个向量，现在计算机速度越来越快了，6万*6万个标量还行，算起来没多久，可是如果是向量呢？Mnist中每个向量由784维，也就是说单独的两个向量点积就需要784次运算，再加上6万个样本，其实速度是非常慢的。\n",
    "\n",
    "高斯核函数\n",
    "$$\n",
    "K(x, z)=\\exp \\left(-\\frac{\\|x-z\\|^{2}}{2 \\sigma^{2}}\\right) \\quad (式5.1)\n",
    "$$\n",
    "$$\n",
    "W(\\alpha)=\\frac{1}{2} \\sum_{i=1}^{N} \\sum_{j=1}^{N} \\alpha_{i} \\alpha_{j} y_{i} y_{i} K\\left(x, z\\right)-\\sum_{i=1}^{N} \\alpha_{i}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6、SMO "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "参考：http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html\n",
    "\n",
    "$\\alpha$是一个仍然存在的未知数，但其他好像我们目前都是可以得到的。那我们怎么求解这个问题的最优解呢？有一个定理是这样的：如果一个问题是最优解，那么它一定满足KKT条件，如果不满足，一定不是最优解，这是充分必要条件。所以这里引发出了一个思考，如果我们找到了最优解，那$\\alpha$的取值一定是满足KKT条件地。所以需要不断得去调整$\\alpha$的值，直到最后所有的$\\alpha$都满足$KKT$条件，这时候我一定得到了最优解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设选择2个变量$\\alpha_{1}、\\alpha_{2}$，其它变量$\\alpha_{(3,\\cdots,N)}$为固定值：\n",
    "$$\n",
    "\\min _{\\alpha_{1}, \\alpha_{2}} \\quad W\\left(\\alpha_{1}, \\alpha_{2}\\right)=\\frac{1}{2} K_{11} \\alpha_{1}^{2}+\\frac{1}{2} K_{22} \\alpha_{2}^{2}+y_{1} y_{2} K_{12} \\alpha_{1} \\alpha_{2}-\\left(\\alpha_{1}+\\alpha_{2}\\right)+y_{1} \\alpha_{1} \\sum_{i=3}^{N} y_{i} \\alpha_{i} K_{i 1}+y_{2} \\alpha_{2} \\sum_{i=3}^{N} y_{i} \\alpha_{i} K_{i 2}+constant\\quad(6.1)\n",
    "$$\n",
    "（已省略不含$\\alpha_{1}、\\alpha_{2}$的常数项）\n",
    "$$\n",
    "\\begin{array}{c}{\\text { s.t. } \\quad \\alpha_{1} y_{1}+\\alpha_{2} y_{2}=-\\sum_{i=3}^{N} y_{i} \\alpha_{i}=\\zeta} \\\\ {0 \\leqslant \\alpha_{i} \\leqslant C, \\quad i=1,2}\\end{array}\n",
    "$$\n",
    "由第一个约束项可得：$\\alpha_{1}=\\frac{\\xi-\\alpha_2 y_2}{y_1}$，用$\\alpha_2$表示$\\alpha_1$\n",
    "\n",
    "故$ W(\\alpha_{1}, \\alpha_{2})$可看做关于$\\alpha_2$的一元二次函数，通过对$W$进行求导等于0可以得到$\\alpha_2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Image of Yaktocat](http://images.cnblogs.com/cnblogs_com/jerrylead/201103/201103182043119717.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于$\\alpha_{1} y_{1}+\\alpha_{2} y_{2}=\\zeta$：\n",
    "\n",
    "当$y_1\\neq y_2$,即$y_1、y_2$分别为-1,1时：$\\alpha_1-\\alpha_2=k$\n",
    "\n",
    "当$y_1=y_2$,即$y_1、y_2$同为-1,1时：$\\alpha_1+\\alpha_2=k$\n",
    "\n",
    "如图所示：$\\alpha_1、\\alpha_2$既要在矩形方框内，也要在直线上，因此:\n",
    "$$\n",
    "L \\leqslant \\alpha_{2} \\leqslant H\n",
    "$$\n",
    "当$y_1\\neq y_2$,\n",
    "$$\n",
    "L=\\max \\left(0, \\alpha_{2}-\\alpha_{1}\\right) \\quad H=\\min \\left(C, C+\\alpha_{2}-\\alpha_{1}\\right)\n",
    "$$\n",
    "当$y_1=y_2$,\n",
    "$$\n",
    "L=\\max \\left(0, \\alpha_{2}+\\alpha_{1}-C\\right) \\quad H=\\min \\left(C, \\alpha_{2}+\\alpha_{1}\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### SMO变量的选择方法 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "前文已知：\n",
    "$$\n",
    "{w}=\\sum_{i=1}^{N} y_{i} \\alpha_{i} {x}_{i}, \\quad b={w} \\cdot {x}_{k}-y_{k}\n",
    "$$\n",
    "$$\n",
    "g(x)={w} \\cdot {x}-b\n",
    "$$\n",
    "所以：\n",
    "$$\n",
    "g(x)=\\sum_{j=1}^{N} y_{j} \\alpha_{j} K\\left({x}, {z}\\right)-b \\quad (6.6)\n",
    "$$\n",
    "$E_i$为预测值与真实值之差：\n",
    "$$\n",
    "E_{i}=g\\left(x_{i}\\right)-y_{i}=\\left(\\sum_{j=1}^{N} \\alpha_{j} y_{j} K\\left(x_{j}, x_{i}\\right)+b\\right)-y_{i}, \\quad i=1,2\n",
    "$$\n",
    "对于式（6.1）：\n",
    "$$\n",
    "\\min _{\\alpha_{1}, \\alpha_{2}} \\quad W\\left(\\alpha_{1}, \\alpha_{2}\\right)=\\frac{1}{2} K_{11} \\alpha_{1}^{2}+\\frac{1}{2} K_{22} \\alpha_{2}^{2}+y_{1} y_{2} K_{12} \\alpha_{1} \\alpha_{2}-\\left(\\alpha_{1}+\\alpha_{2}\\right)+y_{1} \\alpha_{1} \\sum_{i=3}^{N} y_{i} \\alpha_{i} K_{i 1}+y_{2} \\alpha_{2} \\sum_{i=3}^{N} y_{i} \\alpha_{i} K_{i 2}+constant\n",
    "$$\n",
    "引进记号：\n",
    "$$\n",
    "v_{i}=\\sum_{j=3}^{N} \\alpha_{j} y_{j} K\\left(x_{i}, x_{j}\\right)=g\\left(x_{i}\\right)-\\sum_{j=1}^{2} \\alpha_{j} y_{j} K\\left(x_{i}, x_{j}\\right)-b, \\quad i=1,2\n",
    "$$\n",
    "带入式（6.1）：\n",
    "$$\n",
    "\\begin{aligned} W\\left(\\alpha_{1}, \\alpha_{2}\\right)=& \\frac{1}{2} K_{11} \\alpha_{1}^{2}+\\frac{1}{2} K_{22} \\alpha_{2}^{2}+y_{1} y_{2} K_{12} \\alpha_{1} \\alpha_{2} -\\left(\\alpha_{1}+\\alpha_{2}\\right)+y_{1} v_{1} \\alpha_{1}+y_{2} v_{2} \\alpha_{2} \\end{aligned}\\quad(6.2)\n",
    "$$\n",
    "由$\\alpha_{1}=\\frac{\\xi-\\alpha_2 y_2}{y_1}，y_i^{2}=1$：\n",
    "$$\n",
    "\\alpha_{1}=\\left(\\xi-y_{2} \\alpha_{2}\\right) y_{1}\n",
    "$$\n",
    "带入式（6.2）：\n",
    "$$\n",
    "\\begin{aligned} W\\left(\\alpha_{2}\\right)=& \\frac{1}{2} K_{11}\\left(\\zeta-\\alpha_{2} y_{2}\\right)^{2}+\\frac{1}{2} K_{22} \\alpha_{2}^{2}+y_{2} K_{12}\\left(\\zeta-\\alpha_{2} y_{2}\\right) \\alpha_{2} -\\left(\\zeta-\\alpha_{2} y_{2}\\right) y_{1}-\\alpha_{2}+v_{1}\\left(5-\\alpha_{2} y_{2}\\right)+y_{2} v_{2} \\alpha_{2} \\end{aligned}\n",
    "$$\n",
    "对$\\alpha_2$求导=0：\n",
    "$$\n",
    "\\begin{aligned} \\frac{\\partial W}{\\partial \\alpha_{2}}= K_{11} \\alpha_{2}+K_{22} \\alpha_{2}-2 K_{12} \\alpha_{2}-K_{11}\\zeta y_2+K_{12} \\zeta y_{2}+y_{1} y_{2}-1-v_{1} y_{2}+y_{2} v_{2}=0 \\end{aligned}\n",
    "$$\n",
    "化简：\n",
    "$$\n",
    "\\left(K_{11}+K_{22}-2 K_{12}\\right) \\alpha_{2}=y_{2}\\left(y_{2}-y_{1}+\\zeta K_{11}-\\zeta K_{12}+v_{1}-v_{2}\\right)\n",
    "$$\n",
    "\n",
    "$$\n",
    "=y_{2}\\left[y_{2}-y_{1}+\\xi K_{11}-\\xi K_{12}+\\left(g\\left(x_{1}\\right)-\\sum_{j=1}^{2} y_{j} \\alpha_{j} K_{1 j}-b\\right)\\right.-\\left(g\\left(x_{2}\\right)-\\sum_{j=1}^{2} y_{j} \\alpha_{j} K_{2 j}-b\\right)]\n",
    "$$\n",
    "将$\\zeta=\\alpha_{1}^{\\text { old }} y_{1}+\\alpha_{2}^{\\text { old }} y_{2}$代入：\n",
    "$$\n",
    "\\begin{aligned}\\left(K_{11}+K_{22}-2 K_{12}\\right) \\alpha_{2}^{\\text { new, unclipped }} &=y_{2}\\left(\\left(K_{11}+K_{22}-2 K_{12}\\right) \\alpha_{2}^{\\text { old }} y_{2}+y_{2}-y_{1}+g\\left(x_{1}\\right)-g\\left(x_{2}\\right)\\right) \\\\ &=\\left(K_{11}+K_{22}-2 K_{12}\\right) \\alpha_{2}^{\\text { old }}+y_{2}\\left(E_{1}-E_{2}\\right) \\end{aligned}\n",
    "$$\n",
    "令$\\eta=K_{11}+K_{22}-2 K_{12}，即||K(x_1)-K(x_2)||^{2}$:\n",
    "$$\n",
    "\\alpha_{2}^{\\mathrm{new}, \\mathrm{unclipped}}=\\alpha_{2}^{\\mathrm{old}}+\\frac{y_{2}\\left(E_{1}-E_{2}\\right)}{\\eta}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用$\\alpha_2^{new, unclipped}$表示求导求出来的$\\alpha_2$，然而最后的$\\alpha_2^{new}$，要根据下面情况得到：\n",
    "$$\n",
    "\\alpha_{2}^{\\text { new }}=\\left\\{\\begin{array}{ll}{H} & {\\text { if } \\alpha_{2}^{\\text { new, unclipped }}>H} \\\\ {\\alpha_{2}^{\\text { new, unclipped}}} & {\\text { if } L \\leq \\alpha_{2}^{\\text { new, unclipped }} \\leq H} \\\\ {L} & {\\text { if } \\alpha_{2}^{n e w, u n c l i p p e d}<L}\\end{array}\\right.\n",
    "$$\n",
    "得到$\\alpha_2^{new}$后，可得出$\\alpha_1^{new}$\n",
    "$$\n",
    "\\alpha_{1}^{\\mathrm{new}}=\\alpha_{1}^{\\mathrm{old}}+y_{1} y_{2}\\left(\\alpha_{2}^{\\mathrm{old}}-\\alpha_{2}^{\\mathrm{new}}\\right)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 第一个变量的选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们选择违反KKT条件最严重的点。我们都知道最终的目的就是让所有的α都符合KKT条件，那么在找第一个的时候，我们倾向于最不符合KKT条件的，这样子步子能迈得大一点，从KKT条件上来看，也就是：\n",
    "$$\n",
    "\\begin{array}{l}{\\alpha_{i}=0 \\Leftrightarrow y_{i} g\\left(x_{i}\\right) \\geqslant 1} \\quad (6.3)\\\\ {0<\\alpha_{i}<C \\Leftrightarrow y_{i} g\\left(x_{i}\\right)=1} \\quad (6.4)\\\\ {\\alpha_{i}=C \\Leftrightarrow y_{i} g\\left(x_{i}\\right) \\leqslant 1\\quad (6.5)}\\end{array}\n",
    "$$\n",
    "其中：\n",
    "$$\n",
    "g(x)=\\sum_{j=1}^{N} y_{j} \\alpha_{j} K\\left({x}, {z}\\right)-b\n",
    "$$\n",
    "可以通过量化违反的程度来判断哪个违反的最严重，每次遍历样本找到违反最严重的。但在程序中并没有这么做，而是直接遍历，找到的第一个违反KKT的就作为第一个变量。这么做的理由主要是发现几乎所有$\\alpha$都违反，每次遍历找最违反感觉有点慢。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 第二个变量的选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第二个变量选择的过程为内循环，假设在外循环中已找到第一个变量$\\alpha_1$，现在要在内循环中找到第二个变量$\\alpha_2$:\n",
    "\n",
    "其宗旨就是在原先步子迈得比较大的情况下，再找一个步子迈得最大的$\\alpha$。它的量化方式是$|E_1-E_2|$，其中$E_i$的计算方式是：\n",
    "$$\n",
    "E_{1}=\\sum_{i=3}^{N} \\alpha_{i} y_{i} K_{i 1}+\\alpha_{1}^{\\text { old }} y_{1} K_{11}+\\alpha_{2}^{\\text { old }} y_{2} K_{21}+b^{\\text { old }}-y_{1}\n",
    "$$\n",
    "两个α都找到一个，进行优化，然后找下一对α，直到再也找不到不违反KKT的α了为止。α求得以后，w也就顺理成章能够得到了，之后再得到b，"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二、代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start read file\n",
      "start read file\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from minst import loadData\n",
    "\n",
    "trainData, trainLabel = loadData(fileName='D:/Jupyter/mnist_train.csv',label_bin=1)\n",
    "testData, testLabel   = loadData(fileName='D:/Jupyter/mnist_test.csv',label_bin=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算$g(x)=\\sum_{j=1}^{N} y_{j} \\alpha_{j} K\\left({x}, {z}\\right)-b $ 与判断KKT条件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "class SVM:\n",
    "    def isSatisfyKKT(self, i):\n",
    "        '''\n",
    "        查看第i个α是否满足KKT条件\n",
    "        :param i:α的下标\n",
    "        :return:\n",
    "            True：满足\n",
    "            False：不满足\n",
    "        '''\n",
    "        gxi = self.calc_gxi(i)\n",
    "        yi  = self.trainLabelMat[i]                                                     #判断依据参照“第1个变量的选择”(加入了松弛变量)\n",
    "\n",
    "\n",
    "        if (math.fabs(self.alpha[i]) < self.toler) and (yi * gxi >= 1):                 #依据6.3  math.fabs绝对值\n",
    "            return True\n",
    "      \n",
    "        elif (math.fabs(self.alpha[i] - self.C) < self.toler) and (yi * gxi <= 1):      #依据6.5\n",
    "            return True\n",
    "                                                                                         #依据6.4\n",
    "        elif (self.alpha[i] > -self.toler) and (self.alpha[i] < (self.C + self.toler)) and (math.fabs(yi * gxi - 1) < self.toler):  \n",
    "              \n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def calc_gxi(self, i):\n",
    "        '''\n",
    "        计算g(xi)\n",
    "        依据“7.101 两个变量二次规划的求解方法”式6.6\n",
    "        :param i:x的下标\n",
    "        :return: g(xi)的值\n",
    "        '''       \n",
    "        gxi = 0  #初始化g(xi)\n",
    "        #因为g(xi)是一个求和式+b的形式，普通做法应该是直接求出求和式中的每一项再相加即可\n",
    "        #但是读者应该有发现，在“7.2.3 支持向量”开头第一句话有说到“对应于α>0的样本点\n",
    "        #(xi, yi)的实例xi称为支持向量”。也就是说只有支持向量的α是大于0的，在求和式内的\n",
    "        #对应的αi*yi*K(xi, xj)不为0，非支持向量的αi*yi*K(xi, xj)必为0，也就不需要参与\n",
    "        #到计算中。也就是说，在g(xi)内部求和式的运算中，只需要计算α>0的部分，其余部分可\n",
    "        #忽略。因为支持向量的数量是比较少的，这样可以再很大程度上节约时间\n",
    "        #从另一角度看，抛掉支持向量的概念，如果α为0，αi*yi*K(xi, xj)本身也必为0，从数学\n",
    "        #角度上将也可以扔掉不算\n",
    "    \n",
    "        index = [i for i, alpha in enumerate(self.alpha) if alpha != 0]    #index获得非零α的下标，并做成列表形式方便后续遍历 \n",
    "        #enumerate()于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中\n",
    "        #i ：索引，alpha：元素\n",
    "        \n",
    "        for j in index:                                                     #遍历每一个非零α，i为非零α的下标      \n",
    "            gxi += self.alpha[j] * self.trainLabelMat[j] * self.k[j][i]     #计算g(xi)\n",
    "        gxi += self.b                                                       #求和结束后再单独加上偏置b\n",
    "\n",
    "        return gxi        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "计算$E_{i}=g\\left(x_{i}\\right)-y_{i}=\\left(\\sum_{j=1}^{N} \\alpha_{j} y_{j} K\\left(x_{j}, x_{i}\\right)+b\\right)-y_{i}, \\quad i=1,2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SVM:\n",
    "    def calcEi(self, i):\n",
    "        '''\n",
    "        计算Ei\n",
    "        根据“7.4.1 两个变量二次规划的求解方法”式7.105\n",
    "        :param i: E的下标\n",
    "        :return:\n",
    "        ''' \n",
    "        gxi = self.calc_gxi(i)                  #计算g(xi)   \n",
    "        return gxi - self.trainLabelMat[i]     #Ei = g(xi) - yi,直接将结果作为Ei返回"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SMO中选择第二个变量\n",
    "\n",
    "这一步是一个优化性的算法，实际上书上算法中初始时每一个Ei应当都为-yi（因为g(xi)由于初始α为0，必然为0），然后每次按照书中第二步去计算不同的E2来使得|E1-E2|最大，但是时间耗费太长了\n",
    "\n",
    "在Ei的初始化中，由于所有α为0，所以一开始是设置Ei初始值为-yi。这里修改为与α一致，初始状态所有Ei为0，在运行过程中再逐步更新。\n",
    "因此在挑选第二个变量时，只考虑更新过Ei的变量，但是存在问题\n",
    "\n",
    "1.当程序刚开始运行时，所有Ei都是0，那挑谁呢？\n",
    "\n",
    "当程序检测到并没有Ei为非0时，将会使用随机函数随机挑选一个\n",
    "\n",
    "2.怎么保证能和书中的方法保持一样的有效性呢？\n",
    "\n",
    "在挑选第一个变量时是有一个大循环的，它能保证遍历到每一个xi，并更新xi的值，在程序运行后期后其实绝大部分Ei都已经更新完毕了。下方优化算法只不过是在程序运行的前半程进行了时间的加速，在程序后期其实与未优化的情况无异"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SVM:\n",
    "    def getAlphaJ(self, E1, i):\n",
    "        '''\n",
    "        SMO中选择第二个变量\n",
    "        :param E1: 第一个变量的E1\n",
    "        :param i: 第一个变量α的下标\n",
    "        :return: E2，α2的下标\n",
    "        ''' \n",
    "        E2 = 0               #初始化E2  \n",
    "        maxE1_E2 = -1        #初始化|E1-E2|为-1\n",
    "        maxIndex = -1        #初始化第二个变量的下标\n",
    "        nozeroE = [i for i, Ei in enumerate(self.E) if Ei != 0]        #获得Ei非0的对应索引组成的列表，列表内容为非0Ei的下标i\n",
    "\n",
    "        for j in nozeroE:                                              #对每个非零Ei的下标i进行遍历\n",
    "            E2_tmp = self.calcEi(j)                                    #计算E2\n",
    "            if math.fabs(E1 - E2_tmp) > maxE1_E2:                      #如果|E1-E2|大于目前最大值\n",
    "                maxE1_E2 = math.fabs(E1 - E2_tmp)                      #更新最大值\n",
    "                E2 = E2_tmp                                            #更新最大值E2 \n",
    "                maxIndex = j                                           #更新最大值E2的索引j\n",
    "        if maxIndex == -1:                                     #如果列表中没有非0元素了（对应程序最开始运行时的情况）\n",
    "            maxIndex = i\n",
    "            while maxIndex == i:          \n",
    "                maxIndex = int(random.uniform(0, self.m))      #获得随机数，如果随机数与第一个变量的下标i一致则重新随机 \n",
    "            E2 = self.calcEi(maxIndex)                         #获得E2\n",
    "\n",
    "        return E2, maxIndex                                    #返回第二个变量的E2值以及其索引"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "class SVM:\n",
    "    def __init__(self, trainDataList, trainLabelList, sigma = 10, C = 200, toler = 0.001):\n",
    "        '''\n",
    "        SVM相关参数初始化\n",
    "        :param trainDataList:训练数据集\n",
    "        :param trainLabelList: 训练测试集\n",
    "        :param sigma: 高斯核中分母的σ\n",
    "        :param C:软间隔中的惩罚参数\n",
    "        :param toler:松弛变量\n",
    "        '''\n",
    "        self.trainDataMat = np.mat(trainDataList)       #训练数据集\n",
    "        self.trainLabelMat = np.mat(trainLabelList).T   #训练标签集，为了方便后续运算提前做了转置，变为列向量\n",
    "        self.m, self.n = np.shape(self.trainDataMat)    #m：训练集数量    n：样本特征数目\n",
    "        self.sigma = sigma                              #高斯核分母中的σ\n",
    "        self.C = C                                      #惩罚参数\n",
    "        self.toler = toler                              #松弛变量\n",
    "        self.k = self.calcKernel()                      #核函数（初始化时提前计算）\n",
    "        self.b = 0                                      #SVM中的偏置b\n",
    "        self.alpha = [0] * self.trainDataMat.shape[0]   # α 长度为训练集数目\n",
    "        self.E = [0 * self.trainLabelMat[i, 0] for i in range(self.trainLabelMat.shape[0])]     #SMO运算过程中的Ei\n",
    "        self.supportVecIndex = []\n",
    "        \n",
    "    def calcKernel(self):\n",
    "        '''\n",
    "        计算核函数\n",
    "        使用的是高斯核 \n",
    "        :return: 高斯核矩阵\n",
    "        '''        \n",
    "        k = [[0 for i in range(self.m)] for j in range(self.m)] #初始化高斯核结果矩阵 大小 = 训练集长度m * 训练集长度m #k[i][j] = Xi * Xj\n",
    "        \n",
    "        for i in range(self.m):                                 #大循环遍历式5.1中的x    \n",
    "            if i % 100 == 0:\n",
    "                print('construct the kernel:', i, self.m)            \n",
    "            X = self.trainDataMat[i, :]                          #得到式5.1中的X                        \n",
    "    \n",
    "            for j in range(i, self.m): \n",
    "            #小循环遍历Xj，Xj为式5.1中的Z # 由于 Xi * Xj 等于 Xj * Xi，一次计算得到的结果可以\n",
    "            # 同时放在k[i][j]和k[j][i]中，这样一个矩阵只需要计算上半部分即可,所以小循环直接从i开始\n",
    "                \n",
    "                Z = self.trainDataMat[j, :]                        #获得Z            \n",
    "                frac = (X - Z) * (X - Z).T                         #先计算||X - Z||^2                \n",
    "                result = np.exp(-1 * frac / (2 * self.sigma**2))   #分子除以分母后去指数，得到的即为高斯核结果                \n",
    "                k[i][j] = result                                   #将Xi*Xj的结果存放入k中(上半部分与下半部分相同)\n",
    "                k[j][i] = result        \n",
    "        return k       #返回高斯核矩阵\n",
    "\n",
    "    def isSatisfyKKT(self, i):\n",
    "        '''\n",
    "        查看第i个α是否满足KKT条件\n",
    "        :param i:α的下标\n",
    "        :return:\n",
    "            True：满足\n",
    "            False：不满足\n",
    "        '''\n",
    "        gxi = self.calc_gxi(i)\n",
    "        yi  = self.trainLabelMat[i]                                                     #判断依据参照“第1个变量的选择”(加入了松弛变量)\n",
    "\n",
    "\n",
    "        if (math.fabs(self.alpha[i]) < self.toler) and (yi * gxi >= 1):                 #依据6.3  math.fabs绝对值\n",
    "            return True\n",
    "      \n",
    "        elif (math.fabs(self.alpha[i] - self.C) < self.toler) and (yi * gxi <= 1):      #依据6.5\n",
    "            return True\n",
    "                                                                                         #依据6.4\n",
    "        elif (self.alpha[i] > -self.toler) and (self.alpha[i] < (self.C + self.toler)) and (math.fabs(yi * gxi - 1) < self.toler):  \n",
    "              \n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def calc_gxi(self, i):\n",
    "        '''\n",
    "        计算g(xi)\n",
    "        依据“7.101 两个变量二次规划的求解方法”式6.6\n",
    "        :param i:x的下标\n",
    "        :return: g(xi)的值\n",
    "        '''       \n",
    "        gxi = 0  #初始化g(xi)\n",
    "        #因为g(xi)是一个求和式+b的形式，普通做法应该是直接求出求和式中的每一项再相加即可\n",
    "        #但是读者应该有发现，在“7.2.3 支持向量”开头第一句话有说到“对应于α>0的样本点\n",
    "        #(xi, yi)的实例xi称为支持向量”。也就是说只有支持向量的α是大于0的，在求和式内的\n",
    "        #对应的αi*yi*K(xi, xj)不为0，非支持向量的αi*yi*K(xi, xj)必为0，也就不需要参与\n",
    "        #到计算中。也就是说，在g(xi)内部求和式的运算中，只需要计算α>0的部分，其余部分可\n",
    "        #忽略。因为支持向量的数量是比较少的，这样可以再很大程度上节约时间\n",
    "        #从另一角度看，抛掉支持向量的概念，如果α为0，αi*yi*K(xi, xj)本身也必为0，从数学\n",
    "        #角度上将也可以扔掉不算\n",
    "    \n",
    "        index = [i for i, alpha in enumerate(self.alpha) if alpha != 0]    #index获得非零α的下标，并做成列表形式方便后续遍历 \n",
    "        #enumerate()于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中\n",
    "        #i ：索引，alpha：元素\n",
    "        \n",
    "        for j in index:                                                     #遍历每一个非零α，i为非零α的下标      \n",
    "            gxi += self.alpha[j] * self.trainLabelMat[j] * self.k[j][i]     #计算g(xi)\n",
    "        gxi += self.b                                                       #求和结束后再单独加上偏置b\n",
    "\n",
    "        return gxi\n",
    "\n",
    "    def calcEi(self, i):\n",
    "        '''\n",
    "        计算Ei\n",
    "        根据“7.4.1 两个变量二次规划的求解方法”式7.105\n",
    "        :param i: E的下标\n",
    "        :return:\n",
    "        ''' \n",
    "        gxi = self.calc_gxi(i)                  #计算g(xi)   \n",
    "        return gxi - self.trainLabelMat[i]     #Ei = g(xi) - yi,直接将结果作为Ei返回\n",
    "\n",
    "    def getAlphaJ(self, E1, i):\n",
    "        '''\n",
    "        SMO中选择第二个变量\n",
    "        :param E1: 第一个变量的E1\n",
    "        :param i: 第一个变量α的下标\n",
    "        :return: E2，α2的下标\n",
    "        ''' \n",
    "        E2 = 0               #初始化E2  \n",
    "        maxE1_E2 = -1        #初始化|E1-E2|为-1\n",
    "        maxIndex = -1        #初始化第二个变量的下标\n",
    "        nozeroE = [i for i, Ei in enumerate(self.E) if Ei != 0]        #获得Ei非0的对应索引组成的列表，列表内容为非0Ei的下标i\n",
    "\n",
    "        for j in nozeroE:                                              #对每个非零Ei的下标i进行遍历\n",
    "            E2_tmp = self.calcEi(j)                                    #计算E2\n",
    "            if math.fabs(E1 - E2_tmp) > maxE1_E2:                      #如果|E1-E2|大于目前最大值\n",
    "                maxE1_E2 = math.fabs(E1 - E2_tmp)                      #更新最大值\n",
    "                E2 = E2_tmp                                            #更新最大值E2 \n",
    "                maxIndex = j                                           #更新最大值E2的索引j\n",
    "        if maxIndex == -1:                                     #如果列表中没有非0元素了（对应程序最开始运行时的情况）\n",
    "            maxIndex = i\n",
    "            while maxIndex == i:          \n",
    "                maxIndex = int(np.random.uniform(0, self.m))      #获得随机数，如果随机数与第一个变量的下标i一致则重新随机 \n",
    "            E2 = self.calcEi(maxIndex)                         #获得E2\n",
    "\n",
    "        return E2, maxIndex                                    #返回第二个变量的E2值以及其索引\n",
    "\n",
    "    def train(self, iter = 100):            #iterStep：迭代次数，超过设置次数还未收敛则强制停止     \n",
    "        iterStep = 0\n",
    "        parameterChanged = 1                #parameterChanged：单次迭代中有参数改变则增加1\n",
    "        #parameterChanged==0时表示上次迭代没有参数改变，如果遍历了一遍都没有参数改变，说明达到了收敛状态，可以停止了\n",
    "\n",
    "        while (iterStep < iter) and (parameterChanged > 0):         \n",
    "            print('iter:%d:%d'%( iterStep, iter))   #打印当前迭代轮数         \n",
    "            iterStep += 1                           #迭代步数加1\n",
    "         \n",
    "            parameterChanged = 0                     #新的一轮将参数改变标志位重新置0\n",
    "        \n",
    "            for i in range(self.m):                  #大循环遍历所有样本，用于找SMO中第一个变量            \n",
    "                if self.isSatisfyKKT(i) == False:    #查看第一个遍历是否满足KKT条件，如果不满足则作为SMO中第一个变量从而进行优化\n",
    "                                                     #如果下标为i的α不满足KKT条件，则进行优化\n",
    "                    #第一个变量α的下标i已经确定，接下来按照第二步选择变量2。由于变量2的选择中涉及到|E1 - E2|，因此先计算E1\n",
    "                    E1 = self.calcEi(i)\n",
    "                \n",
    "                    E2, j = self.getAlphaJ(E1, i)     #选择第2个变量  #参考“7.4.1两个变量二次规划的求解方法” P126 下半部分\n",
    "                                      \n",
    "                    y1 = self.trainLabelMat[i]        #获得两个变量的标签\n",
    "                    y2 = self.trainLabelMat[j]\n",
    "                 \n",
    "                    alphaOld_1 = self.alpha[i]        #复制α值作为old值\n",
    "                    alphaOld_2 = self.alpha[j]\n",
    "               \n",
    "                    if y1 != y2:                      #依据标签是否一致来生成不同的L和H\n",
    "                        L = max(0, alphaOld_2 - alphaOld_1)\n",
    "                        H = min(self.C, self.C + alphaOld_2 - alphaOld_1)\n",
    "                    else:\n",
    "                        L = max(0, alphaOld_2 + alphaOld_1 - self.C)\n",
    "                        H = min(self.C, alphaOld_2 + alphaOld_1)\n",
    "           \n",
    "                    if L == H:   continue                  #如果两者相等，说明该变量无法再优化，直接跳到下一次循环\n",
    "\n",
    "                    k11 = self.k[i][i]                     #计算α的新值                 \n",
    "                    k22 = self.k[j][j]                     #依据“7.4.1两个变量二次规划的求解方法”式7.106更新α2值\n",
    "                    k21 = self.k[j][i]                     #先获得几个k值，用来计算事7.106中的分母η\n",
    "                    k12 = self.k[i][j]\n",
    "            \n",
    "                    alphaNew_2 = alphaOld_2 + y2 * (E1 - E2) / (k11 + k22 - 2 * k12)        #依据式7.106更新α2，该α2还未经剪切\n",
    "              \n",
    "                    if alphaNew_2 < L: alphaNew_2 = L                                       #剪切α2\n",
    "                    elif alphaNew_2 > H: alphaNew_2 = H\n",
    "             \n",
    "                    alphaNew_1 = alphaOld_1 + y1 * y2 * (alphaOld_2 - alphaNew_2)           #更新α1，依据式7.109\n",
    "                    #依据“7.4.2 变量的选择方法”第三步式7.115和7.116计算b1和b2\n",
    "                    b1New = -1 * E1 - y1 * k11 * (alphaNew_1 - alphaOld_1) - y2 * k21 * (alphaNew_2 - alphaOld_2) + self.b\n",
    "                    b2New = -1 * E2 - y1 * k12 * (alphaNew_1 - alphaOld_1) - y2 * k22 * (alphaNew_2 - alphaOld_2) + self.b\n",
    "   \n",
    "                    if (alphaNew_1 > 0) and (alphaNew_1 < self.C):                        #依据α1和α2的值范围确定新b\n",
    "                        bNew = b1New\n",
    "                    elif (alphaNew_2 > 0) and (alphaNew_2 < self.C):\n",
    "                        bNew = b2New\n",
    "                    else:\n",
    "                        bNew = (b1New + b2New) / 2\n",
    "    \n",
    "                    self.alpha[i] = alphaNew_1                #将更新后的各类值写入，进行更新\n",
    "                    self.alpha[j] = alphaNew_2\n",
    "                    self.b = bNew\n",
    "                    self.E[i] = self.calcEi(i)\n",
    "                    self.E[j] = self.calcEi(j) \n",
    "                     \n",
    "                    if math.fabs(alphaNew_2 - alphaOld_2) >= 0.00001: #如果α2的改变量过于小，就认为该参数未改变，不增加parameterChanged值\n",
    "                        parameterChanged += 1                                               #反之则自增1\n",
    "                print(\"iter: %d i:%d, pairs changed %d\" % (iterStep, i, parameterChanged))  #打印迭代轮数，i值，该迭代轮数修改α数目\n",
    "\n",
    "        for i in range(self.m):                        #全部计算结束后，重新遍历一遍α，查找里面的支持向量\n",
    "            if self.alpha[i] > 0:                       #如果α>0，说明是支持向量\n",
    "                self.supportVecIndex.append(i)          #将支持向量的索引保存起来\n",
    "    \n",
    "    def calcSinglKernel(self, x1, x2):\n",
    "        '''\n",
    "        单独计算核函数\n",
    "        :param x1:向量1\n",
    "        :param x2: 向量2\n",
    "        :return: 核函数结果\n",
    "        '''\n",
    "        result = (x1 - x2) * (x1 - x2).T                        #按照“7.3.3 常用核函数”式7.90计算高斯核\n",
    "        result = np.exp(-1 * result / (2 * self.sigma ** 2))    #返回结果\n",
    "        return np.exp(result)\n",
    "    \n",
    "    def predict(self, x):\n",
    "        '''\n",
    "        对样本的标签进行预测\n",
    "        公式依据“7.3.4 非线性支持向量分类机”中的式7.94\n",
    "        :param x: 要预测的样本x\n",
    "        :return: 预测结果\n",
    "        '''\n",
    "        result = 0\n",
    "        for i in self.supportVecIndex:\n",
    "            #遍历所有支持向量，计算求和式\n",
    "            #如果是非支持向量，求和子式必为0，没有必须进行计算\n",
    "            #这也是为什么在SVM最后只有支持向量起作用\n",
    "  \n",
    "            tmp = self.calcSinglKernel(self.trainDataMat[i, :], np.mat(x))        #先单独将核函数计算出来    \n",
    "            result += self.alpha[i] * self.trainLabelMat[i] * tmp                 #对每一项子式进行求和，最终计算得到求和项的值\n",
    "        result += self.b            #求和项计算结束后加上偏置b\n",
    " \n",
    "        return np.sign(result)       #使用sign函数返回预测结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "construct the kernel: 0 1000\n",
      "construct the kernel: 100 1000\n",
      "construct the kernel: 200 1000\n",
      "construct the kernel: 300 1000\n",
      "construct the kernel: 400 1000\n",
      "construct the kernel: 500 1000\n",
      "construct the kernel: 600 1000\n",
      "construct the kernel: 700 1000\n",
      "construct the kernel: 800 1000\n",
      "construct the kernel: 900 1000\n"
     ]
    }
   ],
   "source": [
    "svm = SVM(trainData[:1000], trainLabel[:1000], 10, 200, 0.001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter:0:100\n",
      "iter: 1 i:16, pairs changed 1\n",
      "iter: 1 i:21, pairs changed 1\n",
      "iter: 1 i:22, pairs changed 2\n",
      "iter: 1 i:34, pairs changed 2\n",
      "iter: 1 i:35, pairs changed 3\n",
      "iter: 1 i:37, pairs changed 3\n",
      "iter: 1 i:38, pairs changed 4\n",
      "iter: 1 i:51, pairs changed 4\n",
      "iter: 1 i:52, pairs changed 5\n",
      "iter: 1 i:56, pairs changed 5\n",
      "iter: 1 i:57, pairs changed 6\n",
      "iter: 1 i:63, pairs changed 6\n",
      "iter: 1 i:64, pairs changed 7\n",
      "iter: 1 i:68, pairs changed 7\n",
      "iter: 1 i:69, pairs changed 7\n",
      "iter: 1 i:70, pairs changed 8\n",
      "iter: 1 i:71, pairs changed 9\n",
      "iter: 1 i:75, pairs changed 9\n",
      "iter: 1 i:76, pairs changed 10\n",
      "iter: 1 i:81, pairs changed 10\n",
      "iter: 1 i:82, pairs changed 11\n",
      "iter: 1 i:88, pairs changed 11\n",
      "iter: 1 i:89, pairs changed 12\n",
      "iter: 1 i:95, pairs changed 12\n",
      "iter: 1 i:96, pairs changed 13\n",
      "iter: 1 i:108, pairs changed 13\n",
      "iter: 1 i:109, pairs changed 14\n",
      "iter: 1 i:114, pairs changed 14\n",
      "iter: 1 i:115, pairs changed 15\n",
      "iter: 1 i:118, pairs changed 15\n",
      "iter: 1 i:119, pairs changed 15\n",
      "iter: 1 i:120, pairs changed 16\n",
      "iter: 1 i:121, pairs changed 16\n",
      "iter: 1 i:122, pairs changed 17\n",
      "iter: 1 i:123, pairs changed 18\n",
      "iter: 1 i:156, pairs changed 18\n",
      "iter: 1 i:157, pairs changed 19\n",
      "iter: 1 i:169, pairs changed 19\n",
      "iter: 1 i:170, pairs changed 20\n",
      "iter: 1 i:192, pairs changed 20\n",
      "iter: 1 i:193, pairs changed 21\n",
      "iter: 1 i:206, pairs changed 21\n",
      "iter: 1 i:207, pairs changed 22\n",
      "iter: 1 i:209, pairs changed 22\n",
      "iter: 1 i:210, pairs changed 22\n",
      "iter: 1 i:211, pairs changed 23\n",
      "iter: 1 i:212, pairs changed 24\n",
      "iter: 1 i:216, pairs changed 24\n",
      "iter: 1 i:217, pairs changed 25\n",
      "iter: 1 i:229, pairs changed 25\n",
      "iter: 1 i:230, pairs changed 26\n",
      "iter: 1 i:232, pairs changed 26\n",
      "iter: 1 i:233, pairs changed 27\n",
      "iter: 1 i:234, pairs changed 27\n",
      "iter: 1 i:246, pairs changed 27\n",
      "iter: 1 i:247, pairs changed 28\n",
      "iter: 1 i:249, pairs changed 28\n",
      "iter: 1 i:250, pairs changed 29\n",
      "iter: 1 i:260, pairs changed 29\n",
      "iter: 1 i:261, pairs changed 30\n",
      "iter: 1 i:283, pairs changed 30\n",
      "iter: 1 i:284, pairs changed 31\n",
      "iter: 1 i:293, pairs changed 31\n",
      "iter: 1 i:294, pairs changed 32\n",
      "iter: 1 i:296, pairs changed 32\n",
      "iter: 1 i:297, pairs changed 33\n",
      "iter: 1 i:303, pairs changed 33\n",
      "iter: 1 i:304, pairs changed 34\n",
      "iter: 1 i:320, pairs changed 34\n",
      "iter: 1 i:321, pairs changed 35\n",
      "iter: 1 i:326, pairs changed 35\n",
      "iter: 1 i:327, pairs changed 36\n",
      "iter: 1 i:359, pairs changed 36\n",
      "iter: 1 i:360, pairs changed 37\n",
      "iter: 1 i:399, pairs changed 37\n",
      "iter: 1 i:400, pairs changed 38\n",
      "iter: 1 i:427, pairs changed 38\n",
      "iter: 1 i:428, pairs changed 39\n",
      "iter: 1 i:429, pairs changed 39\n",
      "iter: 1 i:430, pairs changed 40\n",
      "iter: 1 i:435, pairs changed 40\n",
      "iter: 1 i:436, pairs changed 41\n",
      "iter: 1 i:440, pairs changed 41\n",
      "iter: 1 i:441, pairs changed 42\n",
      "iter: 1 i:451, pairs changed 42\n",
      "iter: 1 i:452, pairs changed 43\n",
      "iter: 1 i:453, pairs changed 43\n",
      "iter: 1 i:454, pairs changed 44\n",
      "iter: 1 i:458, pairs changed 44\n",
      "iter: 1 i:459, pairs changed 45\n",
      "iter: 1 i:462, pairs changed 45\n",
      "iter: 1 i:463, pairs changed 46\n",
      "iter: 1 i:464, pairs changed 46\n",
      "iter: 1 i:465, pairs changed 47\n",
      "iter: 1 i:473, pairs changed 47\n",
      "iter: 1 i:474, pairs changed 48\n",
      "iter: 1 i:489, pairs changed 48\n",
      "iter: 1 i:490, pairs changed 49\n",
      "iter: 1 i:519, pairs changed 49\n",
      "iter: 1 i:520, pairs changed 50\n",
      "iter: 1 i:524, pairs changed 50\n",
      "iter: 1 i:525, pairs changed 51\n",
      "iter: 1 i:526, pairs changed 51\n",
      "iter: 1 i:527, pairs changed 51\n",
      "iter: 1 i:528, pairs changed 52\n",
      "iter: 1 i:529, pairs changed 53\n",
      "iter: 1 i:542, pairs changed 53\n",
      "iter: 1 i:543, pairs changed 54\n",
      "iter: 1 i:577, pairs changed 54\n",
      "iter: 1 i:578, pairs changed 55\n",
      "iter: 1 i:582, pairs changed 55\n",
      "iter: 1 i:583, pairs changed 56\n",
      "iter: 1 i:596, pairs changed 56\n",
      "iter: 1 i:597, pairs changed 57\n",
      "iter: 1 i:603, pairs changed 57\n",
      "iter: 1 i:604, pairs changed 58\n",
      "iter: 1 i:612, pairs changed 58\n",
      "iter: 1 i:613, pairs changed 59\n",
      "iter: 1 i:633, pairs changed 59\n",
      "iter: 1 i:634, pairs changed 60\n",
      "iter: 1 i:639, pairs changed 60\n",
      "iter: 1 i:640, pairs changed 61\n",
      "iter: 1 i:656, pairs changed 61\n",
      "iter: 1 i:657, pairs changed 62\n",
      "iter: 1 i:662, pairs changed 62\n",
      "iter: 1 i:663, pairs changed 63\n",
      "iter: 1 i:666, pairs changed 63\n",
      "iter: 1 i:667, pairs changed 63\n",
      "iter: 1 i:668, pairs changed 63\n",
      "iter: 1 i:669, pairs changed 63\n",
      "iter: 1 i:670, pairs changed 64\n",
      "iter: 1 i:671, pairs changed 65\n",
      "iter: 1 i:672, pairs changed 66\n",
      "iter: 1 i:673, pairs changed 67\n",
      "iter: 1 i:689, pairs changed 67\n",
      "iter: 1 i:690, pairs changed 68\n",
      "iter: 1 i:702, pairs changed 68\n",
      "iter: 1 i:703, pairs changed 69\n",
      "iter: 1 i:709, pairs changed 69\n",
      "iter: 1 i:710, pairs changed 70\n",
      "iter: 1 i:712, pairs changed 70\n",
      "iter: 1 i:713, pairs changed 71\n",
      "iter: 1 i:733, pairs changed 71\n",
      "iter: 1 i:734, pairs changed 72\n",
      "iter: 1 i:743, pairs changed 72\n",
      "iter: 1 i:744, pairs changed 73\n",
      "iter: 1 i:745, pairs changed 73\n",
      "iter: 1 i:746, pairs changed 74\n",
      "iter: 1 i:776, pairs changed 74\n",
      "iter: 1 i:777, pairs changed 75\n",
      "iter: 1 i:781, pairs changed 75\n",
      "iter: 1 i:782, pairs changed 76\n",
      "iter: 1 i:787, pairs changed 76\n",
      "iter: 1 i:788, pairs changed 77\n",
      "iter: 1 i:790, pairs changed 77\n",
      "iter: 1 i:791, pairs changed 78\n",
      "iter: 1 i:818, pairs changed 78\n",
      "iter: 1 i:819, pairs changed 79\n",
      "iter: 1 i:825, pairs changed 79\n",
      "iter: 1 i:826, pairs changed 80\n",
      "iter: 1 i:849, pairs changed 80\n",
      "iter: 1 i:850, pairs changed 81\n",
      "iter: 1 i:859, pairs changed 81\n",
      "iter: 1 i:860, pairs changed 81\n",
      "iter: 1 i:861, pairs changed 82\n",
      "iter: 1 i:862, pairs changed 83\n",
      "iter: 1 i:869, pairs changed 83\n",
      "iter: 1 i:870, pairs changed 84\n",
      "iter: 1 i:872, pairs changed 84\n",
      "iter: 1 i:873, pairs changed 85\n",
      "iter: 1 i:889, pairs changed 85\n",
      "iter: 1 i:890, pairs changed 86\n",
      "iter: 1 i:903, pairs changed 86\n",
      "iter: 1 i:904, pairs changed 87\n",
      "iter: 1 i:927, pairs changed 87\n",
      "iter: 1 i:928, pairs changed 88\n",
      "iter: 1 i:943, pairs changed 88\n",
      "iter: 1 i:944, pairs changed 89\n",
      "iter: 1 i:949, pairs changed 89\n",
      "iter: 1 i:950, pairs changed 90\n",
      "iter: 1 i:952, pairs changed 90\n",
      "iter: 1 i:953, pairs changed 91\n",
      "iter: 1 i:957, pairs changed 91\n",
      "iter: 1 i:958, pairs changed 92\n",
      "iter: 1 i:965, pairs changed 92\n",
      "iter: 1 i:966, pairs changed 93\n",
      "iter: 1 i:979, pairs changed 93\n",
      "iter: 1 i:980, pairs changed 94\n",
      "iter: 1 i:984, pairs changed 94\n",
      "iter: 1 i:985, pairs changed 95\n",
      "iter: 1 i:997, pairs changed 95\n",
      "iter: 1 i:998, pairs changed 96\n",
      "iter:1:100\n",
      "iter: 2 i:1, pairs changed 0\n",
      "iter: 2 i:2, pairs changed 1\n",
      "iter: 2 i:21, pairs changed 1\n",
      "iter: 2 i:34, pairs changed 1\n",
      "iter: 2 i:37, pairs changed 1\n",
      "iter: 2 i:51, pairs changed 1\n",
      "iter: 2 i:56, pairs changed 1\n",
      "iter: 2 i:63, pairs changed 1\n",
      "iter: 2 i:68, pairs changed 1\n",
      "iter: 2 i:69, pairs changed 1\n",
      "iter: 2 i:75, pairs changed 1\n",
      "iter: 2 i:81, pairs changed 1\n",
      "iter: 2 i:88, pairs changed 1\n",
      "iter: 2 i:95, pairs changed 1\n",
      "iter: 2 i:108, pairs changed 1\n",
      "iter: 2 i:114, pairs changed 1\n",
      "iter: 2 i:118, pairs changed 1\n",
      "iter: 2 i:119, pairs changed 1\n",
      "iter: 2 i:121, pairs changed 1\n",
      "iter: 2 i:156, pairs changed 1\n",
      "iter: 2 i:169, pairs changed 1\n",
      "iter: 2 i:192, pairs changed 1\n",
      "iter: 2 i:206, pairs changed 1\n",
      "iter: 2 i:209, pairs changed 1\n",
      "iter: 2 i:210, pairs changed 1\n",
      "iter: 2 i:216, pairs changed 1\n",
      "iter: 2 i:229, pairs changed 1\n",
      "iter: 2 i:232, pairs changed 1\n",
      "iter: 2 i:234, pairs changed 1\n",
      "iter: 2 i:246, pairs changed 1\n",
      "iter: 2 i:249, pairs changed 1\n",
      "iter: 2 i:260, pairs changed 1\n",
      "iter: 2 i:283, pairs changed 1\n",
      "iter: 2 i:293, pairs changed 1\n",
      "iter: 2 i:296, pairs changed 1\n",
      "iter: 2 i:303, pairs changed 1\n",
      "iter: 2 i:320, pairs changed 1\n",
      "iter: 2 i:326, pairs changed 1\n",
      "iter: 2 i:359, pairs changed 1\n",
      "iter: 2 i:399, pairs changed 1\n",
      "iter: 2 i:427, pairs changed 1\n",
      "iter: 2 i:429, pairs changed 1\n",
      "iter: 2 i:435, pairs changed 1\n",
      "iter: 2 i:440, pairs changed 1\n",
      "iter: 2 i:451, pairs changed 1\n",
      "iter: 2 i:453, pairs changed 1\n",
      "iter: 2 i:458, pairs changed 1\n",
      "iter: 2 i:462, pairs changed 1\n",
      "iter: 2 i:464, pairs changed 1\n",
      "iter: 2 i:473, pairs changed 1\n",
      "iter: 2 i:489, pairs changed 1\n",
      "iter: 2 i:519, pairs changed 1\n",
      "iter: 2 i:524, pairs changed 1\n",
      "iter: 2 i:526, pairs changed 1\n",
      "iter: 2 i:527, pairs changed 1\n",
      "iter: 2 i:542, pairs changed 1\n",
      "iter: 2 i:577, pairs changed 1\n",
      "iter: 2 i:582, pairs changed 1\n",
      "iter: 2 i:596, pairs changed 1\n",
      "iter: 2 i:603, pairs changed 1\n",
      "iter: 2 i:612, pairs changed 1\n",
      "iter: 2 i:633, pairs changed 1\n",
      "iter: 2 i:639, pairs changed 1\n",
      "iter: 2 i:656, pairs changed 1\n",
      "iter: 2 i:662, pairs changed 1\n",
      "iter: 2 i:666, pairs changed 1\n",
      "iter: 2 i:667, pairs changed 1\n",
      "iter: 2 i:668, pairs changed 1\n",
      "iter: 2 i:669, pairs changed 1\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iter: 2 i:689, pairs changed 1\n",
      "iter: 2 i:702, pairs changed 1\n",
      "iter: 2 i:709, pairs changed 1\n",
      "iter: 2 i:712, pairs changed 1\n",
      "iter: 2 i:733, pairs changed 1\n",
      "iter: 2 i:743, pairs changed 1\n",
      "iter: 2 i:745, pairs changed 1\n",
      "iter: 2 i:776, pairs changed 1\n",
      "iter: 2 i:781, pairs changed 1\n",
      "iter: 2 i:787, pairs changed 1\n",
      "iter: 2 i:790, pairs changed 1\n",
      "iter: 2 i:818, pairs changed 1\n",
      "iter: 2 i:825, pairs changed 1\n",
      "iter: 2 i:849, pairs changed 1\n",
      "iter: 2 i:859, pairs changed 1\n",
      "iter: 2 i:860, pairs changed 1\n",
      "iter: 2 i:869, pairs changed 1\n",
      "iter: 2 i:872, pairs changed 1\n",
      "iter: 2 i:889, pairs changed 1\n",
      "iter: 2 i:903, pairs changed 1\n",
      "iter: 2 i:927, pairs changed 1\n",
      "iter: 2 i:943, pairs changed 1\n",
      "iter: 2 i:949, pairs changed 1\n",
      "iter: 2 i:952, pairs changed 1\n",
      "iter: 2 i:957, pairs changed 1\n",
      "iter: 2 i:965, pairs changed 1\n",
      "iter: 2 i:979, pairs changed 1\n",
      "iter: 2 i:984, pairs changed 1\n",
      "iter: 2 i:997, pairs changed 1\n",
      "iter:2:100\n",
      "iter: 3 i:1, pairs changed 0\n",
      "iter: 3 i:21, pairs changed 0\n",
      "iter: 3 i:34, pairs changed 0\n",
      "iter: 3 i:37, pairs changed 0\n",
      "iter: 3 i:51, pairs changed 0\n",
      "iter: 3 i:56, pairs changed 0\n",
      "iter: 3 i:63, pairs changed 0\n",
      "iter: 3 i:68, pairs changed 0\n",
      "iter: 3 i:69, pairs changed 0\n",
      "iter: 3 i:75, pairs changed 0\n",
      "iter: 3 i:81, pairs changed 0\n",
      "iter: 3 i:88, pairs changed 0\n",
      "iter: 3 i:95, pairs changed 0\n",
      "iter: 3 i:108, pairs changed 0\n",
      "iter: 3 i:114, pairs changed 0\n",
      "iter: 3 i:118, pairs changed 0\n",
      "iter: 3 i:119, pairs changed 0\n",
      "iter: 3 i:121, pairs changed 0\n",
      "iter: 3 i:156, pairs changed 0\n",
      "iter: 3 i:169, pairs changed 0\n",
      "iter: 3 i:192, pairs changed 0\n",
      "iter: 3 i:206, pairs changed 0\n",
      "iter: 3 i:209, pairs changed 0\n",
      "iter: 3 i:210, pairs changed 0\n",
      "iter: 3 i:216, pairs changed 0\n",
      "iter: 3 i:229, pairs changed 0\n",
      "iter: 3 i:232, pairs changed 0\n",
      "iter: 3 i:234, pairs changed 0\n",
      "iter: 3 i:246, pairs changed 0\n",
      "iter: 3 i:249, pairs changed 0\n",
      "iter: 3 i:260, pairs changed 0\n",
      "iter: 3 i:283, pairs changed 0\n",
      "iter: 3 i:293, pairs changed 0\n",
      "iter: 3 i:296, pairs changed 0\n",
      "iter: 3 i:303, pairs changed 0\n",
      "iter: 3 i:320, pairs changed 0\n",
      "iter: 3 i:326, pairs changed 0\n",
      "iter: 3 i:359, pairs changed 0\n",
      "iter: 3 i:399, pairs changed 0\n",
      "iter: 3 i:427, pairs changed 0\n",
      "iter: 3 i:429, pairs changed 0\n",
      "iter: 3 i:435, pairs changed 0\n",
      "iter: 3 i:440, pairs changed 0\n",
      "iter: 3 i:451, pairs changed 0\n",
      "iter: 3 i:453, pairs changed 0\n",
      "iter: 3 i:458, pairs changed 0\n",
      "iter: 3 i:462, pairs changed 0\n",
      "iter: 3 i:464, pairs changed 0\n",
      "iter: 3 i:473, pairs changed 0\n",
      "iter: 3 i:489, pairs changed 0\n",
      "iter: 3 i:519, pairs changed 0\n",
      "iter: 3 i:524, pairs changed 0\n",
      "iter: 3 i:526, pairs changed 0\n",
      "iter: 3 i:527, pairs changed 0\n",
      "iter: 3 i:542, pairs changed 0\n",
      "iter: 3 i:577, pairs changed 0\n",
      "iter: 3 i:582, pairs changed 0\n",
      "iter: 3 i:596, pairs changed 0\n",
      "iter: 3 i:603, pairs changed 0\n",
      "iter: 3 i:612, pairs changed 0\n",
      "iter: 3 i:633, pairs changed 0\n",
      "iter: 3 i:639, pairs changed 0\n",
      "iter: 3 i:656, pairs changed 0\n",
      "iter: 3 i:662, pairs changed 0\n",
      "iter: 3 i:666, pairs changed 0\n",
      "iter: 3 i:667, pairs changed 0\n",
      "iter: 3 i:668, pairs changed 0\n",
      "iter: 3 i:669, pairs changed 0\n",
      "iter: 3 i:689, pairs changed 0\n",
      "iter: 3 i:702, pairs changed 0\n",
      "iter: 3 i:709, pairs changed 0\n",
      "iter: 3 i:712, pairs changed 0\n",
      "iter: 3 i:733, pairs changed 0\n",
      "iter: 3 i:743, pairs changed 0\n",
      "iter: 3 i:745, pairs changed 0\n",
      "iter: 3 i:776, pairs changed 0\n",
      "iter: 3 i:781, pairs changed 0\n",
      "iter: 3 i:787, pairs changed 0\n",
      "iter: 3 i:790, pairs changed 0\n",
      "iter: 3 i:818, pairs changed 0\n",
      "iter: 3 i:825, pairs changed 0\n",
      "iter: 3 i:849, pairs changed 0\n",
      "iter: 3 i:859, pairs changed 0\n",
      "iter: 3 i:860, pairs changed 0\n",
      "iter: 3 i:869, pairs changed 0\n",
      "iter: 3 i:872, pairs changed 0\n",
      "iter: 3 i:889, pairs changed 0\n",
      "iter: 3 i:903, pairs changed 0\n",
      "iter: 3 i:927, pairs changed 0\n",
      "iter: 3 i:943, pairs changed 0\n",
      "iter: 3 i:949, pairs changed 0\n",
      "iter: 3 i:952, pairs changed 0\n",
      "iter: 3 i:957, pairs changed 0\n",
      "iter: 3 i:965, pairs changed 0\n",
      "iter: 3 i:979, pairs changed 0\n",
      "iter: 3 i:984, pairs changed 0\n",
      "iter: 3 i:997, pairs changed 0\n"
     ]
    }
   ],
   "source": [
    "svm.train()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9817\n"
     ]
    }
   ],
   "source": [
    "errorCnt = 0\n",
    "for i in range(len(testData[:200])):\n",
    "    if testLabel[i] != svm.predict(testData[i]):\n",
    "        errorCnt += 1\n",
    "accuracy = 1 - errorCnt / len(testData)\n",
    "print(accuracy)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "oldHeight": 208.4,
   "position": {
    "height": "230px",
    "left": "1166px",
    "right": "20px",
    "top": "120px",
    "width": "354px"
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "varInspector_section_display": "block",
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}