第2章-感知器.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第2章 感知器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Perceptron"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 感知器模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__定义__：假设输入空间(特征空间)是$\\mathcal{X} \\subseteq \\mathbf{R}^n$，输出空间是$\\mathcal{Y}=\\{+1,-1\\}$。输入$\\mathbf{x} \\in \\mathcal{X}$表示实例的特征向量，对应于输入空间(特征空间)的点；输出$y \\in \\mathcal{Y}$表示实例的类别。由输入空间到输出空间的如下函数：\n",
    "\n",
    "$$f(\\mathbf{x})=sign(\\mathbf{w}·\\mathbf{x}+b)$$\n",
    "\n",
    "称为__感知器(Perceptron)__。\n",
    "\n",
    "其中，$\\mathbf{w}$和$b$是感知器参数，$\\mathbf{w} \\in \\mathbf{R}^n$叫做权值，$b \\in \\mathbf{R}$叫做偏置。\n",
    "\n",
    "感知器是一种__线性分类模型__。假设空间是定义在特征空间中的所有__线性分类模型__，即$\\{f\\ |\\ f(\\mathbf{x})=\\mathbf{w}·\\mathbf{x}+b\\}$\n",
    "\n",
    "感知器的__几何解释__：一个感知器模型，对应$\\mathbf{R}^n$中的一个超平面$S: \\mathbf{w}·\\mathbf{x}+b=0$，$\\mathbf{w}$是超平面的法向量，$b$是超平面的截距。该超平面将输入空间划分为两大部分，两个部分的点分别为分为正类和负类。因此，超平面$S$又被称为__分离超平面__($\\mathbf{w}$的方向指向正类，反方向为负类)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当然，我们可以将偏置项$b$并入权重$\\mathbf{w}$中，作为$w^{(0)}$，这样做的同时需要在$\\mathbf{x}$中添加“第0维”，即$x^{(0)}=1$。这样，我们可以将感知器写成：\n",
    "\n",
    "$$f(\\mathbf{x}) = sign(\\mathbf{w}·\\mathbf{x})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 感知器学习策略"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 数据集的线性可分性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__数据集的线性可分(Linear Separable)__：存在某个超平面$S$能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称该数据集是线性可分的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 学习策略"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "首先选择__损失函数__：\n",
    "\n",
    "* 使用__误分类点的总数__？但这样的损失函数不是$\\mathbf{w}$的连续可导函数，不易最优化，舍弃；\n",
    "* 使用__误分类点到超平面$S$的总距离__！例如，点$\\mathbf{x_0}$到超平面$S$的距离为：($\\mathbf{w^-}$表示原权重向量)\n",
    "\n",
    "$$\\frac{1}{\\|\\mathbf{w^-}\\|}|\\mathbf{w}·\\mathbf{x_0}|$$\n",
    "\n",
    "对于误分类点$(\\mathbf{x_i},y_i)$，有：\n",
    "\n",
    "$$-y_i\\mathbf{w}\\mathbf{x_i} > 0$$\n",
    "\n",
    "那么，误分类点$(\\mathbf{x_i},y_i)$到超平面$S$的距离为：\n",
    "\n",
    "$$-\\frac{1}{\\|\\mathbf{w^-}\\|}y_i \\mathbf{w}\\mathbf{x_i}$$\n",
    "\n",
    "假设误分类点的集合为$M$，那么所有误分类点到超平面的总距离为：\n",
    "\n",
    "$$-\\frac{1}{\\|\\mathbf{w^-}\\|} \\sum_{x_i \\in M} y_i \\mathbf{w}\\mathbf{x_i}$$\n",
    "\n",
    "【这里需要再阐明！】不考虑$\\frac{1}{\\|\\mathbf{w}^-\\|}$，得到感知器的经验损失为：\n",
    "\n",
    "$$L(\\mathbf{w}) = -\\sum_{x_i \\in M} y_i \\mathbf{w}\\mathbf{x_i}$$\n",
    "\n",
    "所以，最优化问题为：\n",
    "\n",
    "$$\\underset{\\mathbf{w}}{min}\\ L(\\mathbf{w}) = -\\sum_{x_i \\in M} y_i \\mathbf{w}\\mathbf{x_i}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3 感知器学习算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 原始形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用__随机梯度下降__求解上述最优化问题。\n",
    "\n",
    "假设误分类点集合$M$固定，则有：\n",
    "\n",
    "$$\\nabla_{\\mathbf{w}}L = -\\sum_{x_i \\in M} y_i\\mathbf{x_i}$$\n",
    "\n",
    "因此，使用随机梯度下降，每次随机选取一个误分类点$(\\mathbf{x_i},y_i)$进行更新：\n",
    "\n",
    "$$\\mathbf{w}_{t+1} = \\mathbf{w}_t + \\eta y_i\\mathbf{x_i}$$\n",
    "\n",
    "直到训练集中没有误分类的点。\n",
    "\n",
    "直观解释：当一个实例被误分，则调整$\\mathbf{w}$，使得超平面向该误分点一侧移动，以减少该点到超平面的距离，直至越过该误分点，使其被正确分类。\n",
    "\n",
    "注意，不同的初值$\\mathbf{w_0}$或过程中选择不同的误分类点，最后得到的超平面可能不同——因为线性可分数据本来就存在不止一个满足条件的超平面。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 收敛性证明"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于线性可分的数据集，感知器学习算法的原始形式能够__收敛__——经过__有限次迭代__得到一个将训练数据完全正确划分的分离超平面。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Novikoff定理__：设训练数据集$T=\\{(\\mathbf{x_1},y_1),(\\mathbf{x_2},y_2),\\cdots,(\\mathbf{x_N},y_N)\\}$是线性可分的，其中$\\mathbf{x_i} \\in \\mathcal{X}=\\mathbf{R}^n$，$y_i \\in \\mathcal{Y}=\\{-1,+1\\}$，$i=1,2,\\cdots,N$，则：\n",
    "\n",
    "1. 存在满足条件$\\|\\mathbf{w_{opt}}\\|=1$的超平面$\\mathbf{w_{opt}}\\mathbf{x}=0$将训练集完全正确分开；且存在$\\gamma>0$，对所有$i=1,2,\\cdots,N$：\n",
    "\n",
    "$$y_i\\mathbf{w_{opt}}\\mathbf{x_i} \\geq \\gamma$$\n",
    "\n",
    "2. 令$R=\\underset{1\\leq i\\leq N}{max}\\|\\mathbf{x_i}\\|$，则感知器算法在训练数据集上的误分类次数k满足不等式：\n",
    "\n",
    "$$k\\leq \\Big(\\frac{R}{\\gamma}\\Big)^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__证明__：\n",
    "\n",
    "1)\n",
    "\n",
    "因为训练集线性可分，由线性可分的定义可知，一定存在某个分离超平面能将训练集完全正确分开，不妨将该超平面记做$\\mathbf{w_{opt}}·\\mathbf{x}=0$，并令$\\|\\mathbf{w_{opt}}\\|=1$，因为放缩$\\mathbf{w}$并不改变平面。\n",
    "\n",
    "因为该超平面可以将训练集中的所有点完全正确分开，所以对所有$i=1,2,\\cdots,N$：\n",
    "\n",
    "$$y_i\\mathbf{w_{opt}}\\mathbf{x_i} \\geq 0$$\n",
    "\n",
    "所以存在\n",
    "\n",
    "$$\\gamma = \\underset{i}{min}\\{y_i\\mathbf{w_{opt}}\\mathbf{x_i}\\}$$\n",
    "\n",
    "使\n",
    "\n",
    "$$y_i\\mathbf{w_{opt}}\\mathbf{x_i} \\geq \\gamma$$\n",
    "\n",
    "2)\n",
    "\n",
    "假设感知器从$\\mathbf{w_{0}}=\\mathbf{0}$开始更新，第k次更新为$\\mathbf{w_{k}}=\\mathbf{w_{k-1}}+\\eta y_{n(k-1)}\\mathbf{x_{n(k-1)}}$，有：\n",
    "\n",
    "$$\\mathbf{w_{opt}}\\mathbf{w_k}=\\mathbf{w_{opt}}\\mathbf{w_{k-1}}+\\eta y_{n(k-1)}\\mathbf{w_{opt}}\\mathbf{x_{n(k-1)}} \\geq \\mathbf{w_{opt}}\\mathbf{w_{k-1}}+\\eta\\gamma$$\n",
    "\n",
    "递推得：\n",
    "\n",
    "$$\\mathbf{w_{opt}}\\mathbf{w_k} \\geq \\mathbf{w_{opt}}\\mathbf{w_{k-1}}+\\eta\\gamma \\geq \\mathbf{w_{opt}}\\mathbf{w_{k-2}}+2\\eta\\gamma \\geq \\cdots \\geq k\\eta\\gamma$$\n",
    "\n",
    "即(__式一__)：\n",
    "\n",
    "$$\\mathbf{w_{opt}}\\mathbf{w_k} \\geq k\\eta\\gamma$$\n",
    "\n",
    "对于$\\mathbf{w_k}$，有：\n",
    "\n",
    "$$\\|\\mathbf{w_k}\\|^2 = \\|\\mathbf{w_{k-1}}\\|^2+2\\eta y_{n(k-1)}\\mathbf{w_{k-1}}\\mathbf{x_{n(k-1)}}+\\eta^2\\|\\mathbf{x_{n(k-1)}}\\|^2 \\leq \\|\\mathbf{w_{k-1}}\\|^2 + \\eta^2\\|\\mathbf{x_{n(k-1)}}\\|^2$$\n",
    "\n",
    "由题目关于$R$的定义可知：\n",
    "\n",
    "$$\\|\\mathbf{w_k}\\|^2 \\leq \\|\\mathbf{w_{k-1}}\\|^2 + \\eta^2\\|\\mathbf{x_{n(k-1)}}\\|^2 \\leq \\|\\mathbf{w_{k-1}}\\|^2 + \\eta^2R^2$$\n",
    "\n",
    "同样递推可得(__式二__)：\n",
    "\n",
    "$$\\|\\mathbf{w_k}\\|^2 \\leq k\\eta^2R^2$$\n",
    "\n",
    "最后，由式一、式二、以及权重向量模为1得：\n",
    "\n",
    "$$k\\eta\\gamma \\leq \\mathbf{w_{opt}}\\mathbf{w_k} \\leq \\|\\mathbf{w_{opt}}\\|\\|\\mathbf{w_k}\\| \\leq \\|\\mathbf{w_k}\\| \\leq \\sqrt{k}\\eta R$$\n",
    "\n",
    "故有：\n",
    "\n",
    "$$k\\leq \\Big(\\frac{R}{\\gamma}\\Big)^2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上述定理证明，当训练集线性可分时，迭代次数k是有上界的，即可以经过有限次搜索找到将训练集完全正确分开的分离超平面。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三. 对偶形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dual的思路：将$\\mathbf{w}$表示为$y_i\\mathbf{x_i}$的线性组合，然后求解系数，即：\n",
    "\n",
    "$$\\mathbf{w} = \\sum_{i=1}^{N}\\alpha_iy_i\\mathbf{x_i}$$\n",
    "\n",
    "其中，\n",
    "\n",
    "$$\\alpha_i \\geq 0,\\ i=1,2,\\cdots,N$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why?若将$\\mathbf{w}$的初始值设为$\\mathbf{0}$，假设在更新的$n$次里，第$i$个样本点被更新了$n_i$次，则$y_i\\mathbf{x_i}$前的系数是$n_i\\eta$，即$\\alpha_i = n_i\\eta$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__感知器学习算法的对偶形式__：\n",
    "\n",
    "* __输入__：线性可分的数据集$T$，学习率$\\eta$；\n",
    "* __输出__：$\\mathbf{\\alpha} = (\\alpha_1, \\alpha_2, \\cdots, \\alpha_N)^T$；感知器模型$f(\\mathbf{x})=sign\\Big(\\sum_{j=1}^N\\alpha_jy_j\\mathbf{x_j}·\\mathbf{x}\\Big)$\n",
    "* __算法__：\n",
    "    1. $\\mathbf{\\alpha} = \\mathbf{0}$\n",
    "    2. 在训练集中选取数据$(\\mathbf{x_i},y_i)$\n",
    "    3. 若$y_i\\Big(\\sum_{j=1}^N\\alpha_jy_j\\mathbf{x_j}·\\mathbf{x_i}\\Big) \\leq 0$，执行更新$\\alpha_i = \\alpha_i+\\eta$；\n",
    "    4. 转至2直到没有误分类的数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对偶形式中，训练实例仅以内积的形式出现。为了方便，可以预先将训练集实例间的内积计算出来并以矩阵的形式存储起来，这个矩阵就是所谓的Gram矩阵(Gram Matrix)：\n",
    "\n",
    "$$G=[x_i·x_j]_{N×N}$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4 感知器的Python实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 边际可视化\n",
    "from matplotlib.colors import ListedColormap\n",
    "\n",
    "# classification <= 5\n",
    "def plot_decision_regions(X, y, classifier=None, scaler = None, resolution=0.02, need_samples=1):\n",
    "    # setup marker generator and color map\n",
    "    markers = ('s','x','o','^','v')\n",
    "    colors = ('red','blue','lightgreen','gray','cyan')\n",
    "    cmap = ListedColormap(colors[:len(np.unique(y))])\n",
    "    \n",
    "    # In this way, we can just draw a scatter pic\n",
    "    if classifier:\n",
    "        # plot the decision surface\n",
    "        x1_min, x1_max = X[:,0].min()-1, X[:,0].max()+1\n",
    "        x2_min, x2_max = X[:,1].min()-1, X[:,1].max()+1\n",
    "        xx1,xx2 = np.meshgrid(np.arange(x1_min,x1_max,resolution),\n",
    "                              np.arange(x2_min,x2_max,resolution))\n",
    "        temp = np.array([xx1.ravel(),xx2.ravel()]).T\n",
    "        if scaler:\n",
    "            temp = scaler.transform(temp)\n",
    "        Z = classifier.predict(temp)\n",
    "        Z = Z.reshape(xx1.shape)\n",
    "        plt.contourf(xx1, xx2, Z, alpha=0.3, cmap=cmap)\n",
    "        plt.xlim(xx1.min(), xx1.max())\n",
    "        plt.ylim(xx2.min(), xx2.max())\n",
    "    \n",
    "    if need_samples:\n",
    "        # plot class samples\n",
    "        for idx,cl in enumerate(np.unique(y)):\n",
    "            plt.scatter(x=X[y==cl,0],\n",
    "                        y=X[y==cl,1],\n",
    "                        alpha=0.8,\n",
    "                        c=colors[idx],\n",
    "                        marker=markers[idx],\n",
    "                        label=cl,\n",
    "                        edgecolor='black')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 272,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEKCAYAAAARnO4WAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGlZJREFUeJzt3XuQJWd53/Hfb+cSPFiCFLu+gNgZm9hyiYsl7VoCRLhICpZBEU6EC6hxKDCujVcJhiJUKngrcYxrTAI2hU2MyICwwTOGgJBsWUFcbMDmYsC7C7ojxca7a1lOtMZ4JVhbYnef/NF92JnZMzP9njlvn+7T309V15nTp6fP0927z559nvO+7YgQAGD8bRt1AACAepDwAaAjSPgA0BEkfADoCBI+AHQECR8AOoKEDwAdQcIHgI4g4QNAR0yOOoCVtm/fHnNzc6MOAwBa48CBA38bETuqbNuohD83N6f9+/ePOgwAaA3bh6tuS0kHADqChA8AHUHCB4COIOEDQEeQ8AGgI0j4ANARJHygpZaXpbk5adu24nF5edQRoeka9T18ANUsL0t79kjHjxfPDx8unkvS/Pzo4kKz8QkfaKF9+04n+57jx4v1wHpI+EALHTmSth6QMpd0bB+S9JCkk5JORMTunO8HdMXOnUUZp996YD11fMJ/XkScT7IHhmdhQZqZWb1uZqZYj411udlNSQdoofl5aXFRmp2V7OJxcZGG7WZ6ze7Dh6WI083uriR9R0S+ndt/KekbkkLS/4yIxY223717dzBbJoBc5ub6l8JmZ6VDh+qOZjhsH6haQcn9tcxLIuJ+298j6RO2vxoRf7JyA9t7JO2RpJ0UIAFk1PVmd9aSTkTcXz4+IOlGSRf12WYxInZHxO4dOyrN4Q+gIdpWD1/vM+UwPmu24VxkS/i2H237rN7Pkp4v6Y5c7wegXm2sh+dqdrflXGSr4dv+QRWf6qWidPS7EbHhaaWGD7RHW+vhy8vFALUjR4pP9gsLW292j/JcpNTwszZtU5HwgfbYtq34NLuWLZ06VX88ozTKc5GS8PlaJoCB5KyHt01bzgUJH2iQNjT+erow+Kvq9WjNuYiIxiy7du0KoKuWliJmZiKK4kCxzMwU65tqaSlidjbCLh6bHGuq1OsxqnMhaX9UzLHU8IGGaGsTdFy15XpQwwdaqOuDgppmHK8HCR9oiLY0/rpiHK8HCR9oiJyNv2uukSYni68JTk4Wz4ehTU3mniY0Ykd23qoW++tYaNqi63I0/vbuXd147C1792491jY2mUfdiB32eRNNWwA9k5PSyZNnrp+YkE6cGHy/bWlqrtSEmIcdA01bAN/RL9lvtL6qNjY1mxDzKGMg4QNjbmIibX1VbWxqNiHmUcZAwgfG3J49aeuryj26NKWx2YRGbFUjjaFqsb+OhaYtMHxLSxGTk6ubhJOTw2tA5hhdmtLYbEIjNtUwYxBNWwA9TWhUpkqJuY3HN0w0bQF8RxMalalSYm7j8Y0KCR8Yc01oVKZKibmNxzcqJHy0Sq4RijkahLlVHT2b2iRswjlOibkJjdjWqFrsr2OhaYuN5BrZmbNBmEvq6NmqTcImnOPUmFO3HTeiaYtxlKs518YGYdtGzzblvI0j7mmLsZTrvqEp+23KfVzt9V/byl/pJpxjpOFbOhhLqc25qjXjNjYImzJ6Nsc5HkQbezAjUbX2U8dCDR8byVVr70INv6o2nremxDEqSqjhjzzJr1xI+NhM1ebc7Gz/hDg7u7X9pm6b0969ERMTxXFNTGw92fc04RynSIkjNeY2SEn41PAxlqgZ59eUc9zGHswwUcNH5zWl1j7OmnKO29iDGRUSPsYSg3EGl2vmyVzNUgZpJaha+6ljoYaPYWpKrb1Ncs08mbtZ2sYezLCIGj6AQTDwqn2o4QMYSK6ZJ5nRshlI+AC+I1dTs+vN0qYg4QNKayhWnaUydxw55Gpqdr5Z2hRVi/11LDRtMQopDcVcI1xT48gp520Lx6lZ2hSiaQtUl9JQzDVLZWocQA9NWyBBSkOxX7LfaH2uOIBBkPDReSkNxVyzVKbGAQyChI/OW1iQpqdXr5ue7t9Q3LOn/z7WW5/rtn7AIEj4gM6cUGu91tYllxR1/JUmJ4v1ay0vF/8QHD5c7O/w4eL5ekl/fl5aXCxq9nbxuLhYrAeGgaYtOi/XLQ5pwqIONG2BBCnN0lzbAnXInvBtT9j+su2bc78XMIhc0+vShEXT1PEJ/zWS7q7hfYBVqo6IzTW97sKCNDW1et3U1PCasNzHFcmqjtAaZJF0jqQ/knSppJs3256RthiW1BGxOabXXVqKmJ5e/f7T09zHFcOlpoy0tX29pDdJOkvS6yPiyo22p2mLYck5IraqnE1bmsfoaUTT1vaVkh6IiAObbLfH9n7b+48ePZorHHRMzhGxVeVs2tI8xiBy1vAvkXSV7UOSPiDpUttLazeKiMWI2B0Ru3fs2JExHNSlCfXi1BGxOWLO2bSleYxBZEv4EfGGiDgnIuYkvVTSJyPip3O9H5ohdbBRLikjYnPF/IIXpK1PwX1cMZCqxf6tLJKeK5q2nTA7279ZOjtbfyx790ZMTBTvPzGxfsM2V8y5z0WX7+OK09SUpm0qmrbtt21b/2kJbOnUqfrjqSJXzG08F2ifRjRt0U1trBdzWz90BQkfQ9WkenHVRiy39UNnVK391LFQwx8PTagXpw424rZ+aCtRw0fXMdgIXUENH53HYCPgTCR8jCUapsCZSPgYS7lnqgTaiISPsWVv/BzoGhI+xtK+fdIjj6xe98gjxXqgq0j4GEs0bYEzkfAxlmjaAmci4WMspY5ybcKUzkBuk5ttYPufSLpa0tzK7SPijfnCArZmfr543LevKOPs3Fkk+976lXrTIx8/XjzvTY+8cj/AONh0pK3tj0o6JumApO/cLygifm3YwTDSFqPAqFy0WcpI200/4Us6JyKu2GJMQGPR4EVXVKnhf972U7NHAowIDV50xboJ3/bttm+T9CxJB23fY/u2FevRcjQqCzR40RUblXSurC0K1I5G5Wk0eNEVVZq2vxMR/2azdcNA07Y+NCoHw3lD0wx7euQnr9n5hKRdgwSG5qBRORjOG9psoxr+G2w/JOlpth8sl4ckPSDp92uLEFnQqBwM5w1ttm7Cj4g3RcRZkt4SEWeXy1kR8biIeEONMSID7rc6GM4b2qxKSedDti9cszzJdpXv8KOh5uelxcWi9mwXj4uLNB43w3lDm1Vp2n5B0oWSbpNkSU+VdKukx0n6uYj4+LCCoWkLAGmG3bQ9JOmCiNgdEbsknS/pDkmXS3rzwFECAGpVJeH/SETc2XsSEXep+Afga/nCwqBSBgUxgAjolip1+HtsXyvpA+Xzl0i6t5xF89vZIkOylEFBDCACuqdKDf+7JF2jYooFS/qspHdI+kdJMxHxzWEFQw1/a1IGBTGACBgPKTX8TRN+nUj4W7Ntm9TvctrSqVODbwuguYbatLV9ie1P2L7X9td6y9bDxLClDApiABHQPVWattdJequKks6PrVjQMCmDghhABHRPlYR/LCJuiYgHIuLrvSV7ZEiWMiiIAURA91Rp2v43SROSbpD0cG99RBwcdjDU8AEgzbBvcXhx+bhyhyHp0tTAAACjs2nCj4jn1REIACCvKt/S+V7b19m+pXx+nu1X5Q8NADBMVZq2vy3pY5IeXz6/V9JrcwUEAMijSsLfHhEflHRKkiLihKSTWaMCAAxdlYT/LduPU9Gole2nSzqWNSoAwNBVSfivk3STpCfZ/pyk90l69Wa/ZPtRtr9k+1bbd9r+pS3GihFiZk2g/ap8S+eg7edIOlfF5Gn3RESVWTIflnRpRHzT9pSkz9q+JSK+sLWQUTdm1gTGw7oJ3/a/XuelH7atiLhhox1HMaKrN5PmVLk0Z6Y2VLZv3+lk33P8eLGehA+0x0af8P/lBq+FipG3G7I9IemApH8m6Tcj4ot9ttkjaY8k7WTmrkY6ciRtPYBmWjfhR8Qrt7rziDgp6Xzbj5V0o+2nRMQda7ZZlLQoFVMrbPU9MXw7d/afO59/n4F2qdK03bKI+HtJn5Z0RR3vh+FiZk1gPGRL+LZ3lJ/se3fNulzSV3O9H/JhZk1gPFSZPG1Q3y/pvWUdf5ukD0bEzRnfDxnNz5PggbYb5Fs6klTlWzq3SbpgwLgAAEOW9Vs6AIDmyPotHQBAc1Sq4dt+oaQnS3pUb11EvDFXUACA4asyH/47Jb1Exfw5lvRTkmYzxwUAGLIqX8t8ZkS8XNI3IuKXJD1D0hPzhgUAGLYqCf8fysfjth8v6duSfiBfSACAHKrU8G8uB1C9RdJBFd/QeXfWqAAAQ1cl4b85Ih6W9GHbN6to3P5j3rAAAMNWpaTzp70fIuLhiDi2ch0AoB02Gmn7fZKeIOm7bF+g4hs6knS2pJn1fg8A0EwblXR+XNIrJJ0j6a0r1j8o6RcyxgQAyGCjkbbvVTH52dUR8eEaYwIAZFClhv8529fZvkWSbJ9n+1WZ4wIADFmVhP9bkj4m6fHl83slvTZbRACALKok/O0R8UFJpyQpIk5IOpk1KgDA0FVJ+N+y/TgVA65k++mSjmWNCgAwdFUGXr1O0k2SnmT7c5J2SHpx1qgAAEO3acKPiIO2nyPpXBXfxb8nIr6dPTIAwFBtmvBtP0rSNZKepaKs8xnb74wIplcAgBapUtJ5n6SHJL29fP4ySb+jYl58AEBLVEn450bEj654/inbt+YKCACQR5Vv6Xy5/GaOJMn2xZI+ly8kAEAOVT7hXyzp5baPlM93Srrb9u2SIiKeli06AMDQVEn4V2SPAgCQXZWvZR6uIxAAQF5VavgAgDFAwgeAjiDhA0BHkPABoCNI+ADQESR8AOgIEj4AdAQJHwA6goQPAB1BwgeAjiDhA0BHkPABoCNI+ADQESR8AOiIbAnf9hNtf8r23bbvtP2aXO8FANhclRugDOqEpP8QEQdtnyXpgO1PRMRdGd8TALCObJ/wI+JvIuJg+fNDku6W9IRc7wcA2FgtNXzbc5IukPTFPq/tsb3f9v6jR4/WEQ4AdFL2hG/7uyV9WNJrI+LBta9HxGJE7I6I3Tt27MgdDgB0VtaEb3tKRbJfjogbcr7XWFtelubmpG3bisfl5W7GAGBLsjVtbVvSdZLujoi35nqfsbe8LO3ZIx0/Xjw/fLh4Lknz892JAcCWOSLy7Nh+lqTPSLpd0qly9S9ExEfW+53du3fH/v37s8TTWnNzRYJda3ZWOnSoOzEA6Mv2gYjYXWXbbJ/wI+Kzkpxr/51x5Eja+nGNAcCWMdK26XbuTFs/rjEA2DISftMtLEgzM6vXzcwU67sUA4AtI+E33fy8tLhY1Mvt4nFxsd5maRNiALBl2Zq2g6BpCwBpUpq2fMIHgI4g4QNAR5DwUU1TRtpec400OVn0EiYni+d1a8q5ABLlnB4Z46IpI22vuUa69trTz0+ePP38He+oJ4amnAtgADRtsbmmjLSdnCyS/FoTE9KJE/XE0JRzAZRo2mK4mjLStl+y32h9Dk05F8AASPjYXFNG2k5MpK3PoSnnAhgACX8UUpt+uRqVl19e7LO3XH55/+0WFqSpqdXrpqbqH2nbq5VXXZ8Do47RZhHRmGXXrl0x9paWImZmIqTTy8xMsb6fvXtXb9tb9u7dWhyXXdZ/v5dd1j/m6enV201Prx9zTnv3RkxMFDFMTGz9PAxiaSlidjbCLh5HcR6AkqT9UTHH0rStW2rTL1ej0htMZLr2zwSNSqCxaNo2WWrTj0YlgCEh4Q9L1bp8atMvtVFZtS6fIjXm1J5DSk+DgVfA4KrWfupYWlvDT6nL56zhp9Tlzzuv/7bnnbe1bVN7DinnI1c/I0Xq9QMyU0INf+RJfuXS2oQ/O9s/Ec3O9t8+telXtVHZL4bespWYU/bbi3PtMjHRP+aUOFL3nUPqtQYyS0n4NG2HYdu2MxudUlF2OHXqzPW5pDRiU2JO2W/KtjnjyKUp1xoo0bStWxsH4+SKObXnkBIHA6+ALelews/RcFtYKPa30rZtwxuMU7VRedll1dcvLJyZKCcm+secst/UwVEpA5lS953rWjPwCm1VtfZTx5K9hp+r4ZazmZiy76Wl/ttutQGaGsPaWvvExMbnOKWnUbWfkbO5ysArNIio4a8j1wCinLM4puw75fhS9psrhpyaEgeQWUoNv1sJP1fDLWczsW2N2KY0NZsSB5AZTdv1NKVRmWvfuRqguWLIqSlxAA3SrYSf2lyt2vTL2UxM2XeuBmiuGAZR9dw1ZYZPoEmqFvvrWLI3bVObj6kjYnM1E1NmiKzaUExtruaIIVXqiOamzPAJZCSatutoQvOxKc3EpsSRIiXmNh4fMACatutpQvOxKc3EpsSRIiXmNh4fMACatutpQvOxKc3EpsSRIiXmNh4fkFm3En4Tmo9NGam5sCBNT69eNz3d7KZmyrlrynlmKmU0SdVifx1LLbNlNqX5OOqRmktLEVNTq5uaU1PNb2qmnLtRn2emUkYNRNMWm6KpmR/nGDWgho/NcdvC/DjHaJjxSPjUSdPR1MyPc4yGaX/CX14umq6HDxdV0sOHi+ck/Y01pak5zjjHaJj2J/x9+6Tjx1evO368WI/1zc9Li4tFPdkuHhcXi/UYDs4xGqb9TVsG2ADosG41bamTAkAl2RK+7ffYfsD2HbneQ1Jz6qQ0jgE0XM5P+L8t6YqM+y80oU5K4xhAC2St4duek3RzRDylyvatHXjFABsAI9KqGr7tPbb3295/9OjRUYczGAbYAGiBkSf8iFiMiN0RsXvHjh2jDmcwNI4BtMDIE/5YaErjGAA2QMIfhiY0jgFgE5O5dmz7/ZKeK2m77fsk/WJEXJfr/UZufp4ED6DRsiX8iHhZrn0DANJR0gGAjiDhA0BHkPABoCNI+ADQESR8AOiIRs2Hb/uopD6T0ozcdkl/O+ogMuL42o3ja69hHNtsRFSapqBRCb+pbO+vOjlRG3F87cbxtVfdx0ZJBwA6goQPAB1Bwq9mcdQBZMbxtRvH1161Hhs1fADoCD7hA0BHkPDXsD1h+8u2b+7z2itsH7X9lXL52VHEOCjbh2zfXsZ+xr0kXfgN239u+zbbF44izkFVOL7n2j624vr9l1HEOSjbj7V9ve2v2r7b9jPWvN7a61fh2Fp77WyfuyLur9h+0PZr12xTy7XLNltmi71G0t2Szl7n9f8VEf++xniG7XkRsd73fn9C0g+Vy8WSri0f22Sj45Okz0TElbVFM1y/LumjEfFi29OS1tx1p9XXb7Njk1p67SLiHknnS8UHSkl/LenGNZvVcu34hL+C7XMkvVDSu0cdy4i8SNL7ovAFSY+1/f2jDgqS7bMlPVvSdZIUEY9ExN+v2ayV16/isY2LyyT9RUSsHWBay7Uj4a/2Nkn/UdKpDba5uvwv1/W2n1hTXMMSkj5u+4DtPX1ef4Kkv1rx/L5yXVtsdnyS9Azbt9q+xfaT6wxui35Q0lFJv1WWHN9t+9Frtmnr9atybFJ7r91KL5X0/j7ra7l2JPyS7SslPRARBzbY7A8kzUXE0yT9oaT31hLc8FwSEReq+O/jv7P97DWvu8/vtOlrXJsd30EVw9B/VNLbJf1e3QFuwaSkCyVdGxEXSPqWpP+0Zpu2Xr8qx9bmaydJKktVV0n6UL+X+6wb+rUj4Z92iaSrbB+S9AFJl9peWrlBRHw9Ih4un75L0q56Q9yaiLi/fHxARQ3xojWb3Cdp5f9azpF0fz3Rbd1mxxcRD0bEN8ufPyJpyvb22gMdzH2S7ouIL5bPr1eRJNdu08brt+mxtfza9fyEpIMR8f/6vFbLtSPhlyLiDRFxTkTMqfhv1ycj4qdXbrOmpnaViuZuK9h+tO2zej9Ler6kO9ZsdpOkl5ffGHi6pGMR8Tc1hzqQKsdn+/tsu/z5IhV//r9ed6yDiIj/K+mvbJ9brrpM0l1rNmvl9atybG2+diu8TP3LOVJN145v6WzC9hsl7Y+ImyT9vO2rJJ2Q9HeSXjHK2BJ9r6Qby78zk5J+NyI+avvnJCki3inpI5JeIOnPJR2X9MoRxTqIKsf3Ykl7bZ+Q9A+SXhrtGnn4aknLZWnga5JeOUbXb7Nja/W1sz0j6V9I+rcr1tV+7RhpCwAdQUkHADqChA8AHUHCB4COIOEDQEeQ8AGgI0j4QKmckbHfLKl91w/h/X7S9nkrnn/a9ljeuxXNQMIHRucnJZ236VbAkJDw0RrlaNr/XU6gdYftl5Trd9n+43LStI/1RkSXn5jfZvvz5fYXlesvKtd9uXw8d6P37RPDe2z/Wfn7LyrXv8L2DbY/avv/2H7zit95le17y3jeZft/2H6mitHab3ExR/qTys1/yvaXyu3/+ZBOHSCJkbZolysk3R8RL5Qk24+xPaViMq0XRcTR8h+BBUk/U/7OoyPimeVEau+R9BRJX5X07Ig4YftySb8i6eqKMexTMe3Gz9h+rKQv2f7D8rXzJV0g6WFJ99h+u6STkv6zirlhHpL0SUm3RsTnbd8k6eaIuL48HkmajIiLbL9A0i9KunyQEwX0Q8JHm9wu6Vdt/3cVifIztp+iIol/okyYE5JWzkHyfkmKiD+xfXaZpM+S9F7bP6RiRsKphBier2KSvdeXzx8laWf58x9FxDFJsn2XpFlJ2yX9cUT8Xbn+Q5J+eIP931A+HpA0lxAXsCkSPlojIu61vUvFnCNvsv1xFbNi3hkRz1jv1/o8/2VJn4qIf2V7TtKnE8KwpKvLuxidXmlfrOKTfc9JFX+/+k17u5HePnq/DwwNNXy0hu3HSzoeEUuSflVFmeQeSTtc3gPV9pRX3xyjV+d/looZCI9JeoyK28xJ6RPgfUzSq1fM3HjBJtt/SdJzbP9T25NaXTp6SMX/NoBa8AkCbfJUFU3OU5K+LWlvRDxi+8WSfsP2Y1T8mX6bpDvL3/mG7c+ruEdxr67/ZhUlndepqKmn+OVy/7eVSf+QpHXvsxoRf237VyR9UcX85ndJOla+/AFJ77L98ypmgwSyYrZMjC3bn5b0+ojYP+I4vjsivll+wr9R0nsiYu1NrIHsKOkA+f1X219RcUOWv1QLb8+H8cAnfADoCD7hA0BHkPABoCNI+ADQESR8AOgIEj4AdAQJHwA64v8DRfTIz2wNwa4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "\n",
    "iris = load_iris()\n",
    "data = iris.data\n",
    "target = iris.target\n",
    "# setosa是-1, versicolor是1\n",
    "# x1是sepal length, x2是petal length\n",
    "X = data[target!=2][:,[0,2]]\n",
    "y = target[target!=2]\n",
    "y = np.where(y==0,-1,1)\n",
    "# 作图\n",
    "plt.xlabel(\"sepal length\")\n",
    "plt.ylabel(\"petal length\")\n",
    "plt.scatter(X[y==-1,0],X[y==-1,1],color='r')\n",
    "plt.scatter(X[y==1,0],X[y==1,1],color='b');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. primal形式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Perceptron:\n",
    "    \"\"\"Perceptron classifier.\n",
    "    Parameters\n",
    "    --------------\n",
    "    eta : float\n",
    "        Learning rate\n",
    "    random_state : int\n",
    "        random seed\n",
    "        \n",
    "    Attributes\n",
    "    --------------\n",
    "    w_ : 1d-array\n",
    "        Weights\n",
    "    errors_ : list\n",
    "        Number of updates in each epoch\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, eta=0.01, random_state=1):\n",
    "        self.eta = eta\n",
    "        self.random_state = random_state\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        \"\"\"Fitting training data.\n",
    "        Parameters\n",
    "        --------------\n",
    "        X : nd-array, shape = [n_samples, n_features]\n",
    "            Training vectors\n",
    "        y : 1d-array, shape = [n_samples,]\n",
    "            Target values\n",
    "        \n",
    "        Return\n",
    "        --------------\n",
    "        self : object\n",
    "        \"\"\" \n",
    "        n_samples = X.shape[0]        # n_samples\n",
    "        n_features = X.shape[1]       # n_features\n",
    "        # Initialization\n",
    "        self.w_ = np.zeros(n_features+1)\n",
    "        self.errors = []\n",
    "        rgen = np.random.RandomState(self.random_state)\n",
    "        index = rgen.permutation(range(n_samples))         # Random index of samples\n",
    "        updates = 0                                        # Total updates\n",
    "        # Add 0-dimension\n",
    "        X_add = np.hstack([np.ones((n_samples,1)), X])\n",
    "        # Start\n",
    "        while True:\n",
    "            errors = 0\n",
    "            for xi,target in zip(X_add[index],y[index]):\n",
    "                y_hat = np.sign(np.dot(xi,self.w_))\n",
    "                y_hat = -1 if y_hat==0 else y_hat\n",
    "                if y_hat != target:\n",
    "                    errors += 1\n",
    "                    self.w_ += eta * target * xi\n",
    "            self.errors.append(errors)\n",
    "            if errors == 0:\n",
    "                break\n",
    "            updates += errors\n",
    "        return self\n",
    "    \n",
    "    def predict(self, X):\n",
    "        scores = np.dot(X,self.w_[1:])+self.w_[0]\n",
    "        return np.where(scores > 0, 1, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 288,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGzRJREFUeJzt3X+MXPV57/HPs2YNa2MvjrN2bJxckl4TlTgBogWJgiOXtBgrwW6aRi0SVyKN4qubH6JKrkgT/qgqQtOuYlTaorQObrjtEkoCNaH5YRMVubHV3GxMQwkxARFC5Y0hrN2AAVO88T7948zxzszOnDlz5pyZ8515vyS0e87MnPM9a/Ts2ec8z/dr7i4AQDiGej0AAEB7CNwAEBgCNwAEhsANAIEhcANAYAjcABAYAjcABIbADQCBIXADQGDOSPMmMztH0h2SNkhySb/v7t9t9v7ly1/vq1efl8sAAWAQPPXUw0fdfSzNe1MFbkm3Sdrj7r9jZoslLUl68+rV5+nWWw+mPDQAYOtW+4+0720ZuM1suaR3Sbpektz9pKSTWQcHAOhMmhz3WyTNSPqSmf3AzO4ws6X1bzKz7WZ20MwOvvjiTO4DBQBE0gTuMyS9U9IX3P1iSa9I+sP6N7n7Tncfd/fx0dFUaRoAQAZpctzTkqbd/XuV7XvVIHADQLcNDc1q5cppDQ//V6+Hktrs7Fk6dmyd5uaGMx+jZeB29+fM7LCZvdXdn5D0bkmHMp8RAHKycuW01qxZpuXLz5OZ9Xo4Lbm7jh8/JmlaMzNvznyctFUlH5d0V6Wi5GlJH8x8RgDIyfDwfwUTtCXJzLR8+UodPdrZc8BUgdvdH5E03tGZAKAAoQTtWB7jpXMSAAJD4AaAnDz55I911VWXafXqM/WXf/n5ws6TNscNAGhhxYrX6U//9C/0jW/cX+h5CNwABsK2Ky/RSzPPL9i/bGyVvvbQ93M5x9jYKo2NrdKDD34jl+M1Q+AGMBBemnleU69f2Bx4aYNgXnbkuAEgMARuAOjAF794uzZuvEgbN16kZ5890pVzkioBgA58+MMf1Yc//NGunpPADQA5+fnPn9OVV47rpZeOy2xIf/3Xf67vfveQli9fnut5CNwABsKysVUNH0QuG1uV2zlWr36DfvSj6dyO1wyBG8BAyKvkrwx4OAkAgSFwA0BgCNwAEBgCNwAEhsANAIEhcANAhz72sd/X+vWrdNllG7pyPgI3gIHhnryd1bXXXq97792Tz8FSIHADGAh33indfvt8sHaPtu+8s/NjX375u7Rixes6P1BKBG4Afc9devll6b775oP37bdH2y+/nN+dd7fQOQmg75lJH63MA3XffdF/kvT+90f7A1tvmDtuAIOhOnjHQgzaEoEbyFVRD7/QuTg9Uq065x0SAjeQkz17pPvvr334df/90X70VnVO+/3vlx56KPpanfPuxIc+dK2uuuoyPfXUE3rb29bp7/9+Vz4Db4IcN5ADd+nVV6X9+6Pt3/qtKGjv3y9t3Bi9HuKf5P3CTDr77Nqcdpw2Ofvszv9tdu26u/NBtoHADeTALArWUhSs4wC+cWO0n6Dde9dfX/sLNA7eIf7bpEqVmNkzZvZDM3vEzA4WPSggRNXBOxZq0O7XXH39v0WI/zZSeznuX3f3i9x9vLDRAAGLc9rVqnPeoQgtV++B/YDzGC8PJ4EcxMEtzmnv2BF93b8/rOBdnauPxx1f16uvlu86ZmfP0vHjx4IJ3u6u48ePaXb2rI6OkzbH7ZIeNDOX9DfuvrOjswJ9xkwaGanNacdpk5GRcP4kDy1Xf+zYOknTOnp0ptdDSW129qzKuLNLG7gvd/cjZrZK0rfN7Mfu/p3qN5jZdknbJWls7E0dDQoI0dVXL3z4lUewq69IKbpCJR53HLSl9NfR7bHOzQ1rZubNxZ2gpFKlStz9SOXr85J2S7q0wXt2uvu4u4+Pjo7lO0ogEHk//OpFvjlrrj603HjIWgZuM1tqZsvi7yVdJemxogcGDLpe5Juz5upDy42HLk2qZLWk3RbdOpwh6cvuzu9QDKxupQN6kW9Ok6tvdv0h5cZD1zJwu/vTki7swliA0tuzJ7qDjINRfGc5MhLluPPWSb45q6Rcfavr7/ZYBxXlgEBKvUxdVOtGeWGjXH2r65+b64869hDQ8g6k1O10QH2+uXr+E6n7d7NJ179tm/S1r5VnrP2OO26gDZ20tc/NJW83OlejfPPGjcXXhjdreW92/UNDrcfar230vUDgBtqQNXWxY4d0yy3zwXpuLtresSPdOZO285ZU1pd0/XGOuz43fvXVlArmjcANpJS1VG5uTjpxQnr00fngfcst0faJE83vvOOc8oEDtTnlAweKzakn5bF3706+/iy5ce6820eOG0gpa1v70JB0003SZz8bBevf/d1o/9vfHu0fanL71GlOvVXZYpayvr17279+SgXzxx030IakdECSBx+UNmyoTRVs2BDtT5I1p94qNZH0etI5s15/P015WwYEbqBN7ba1u0cpka98RTp1Kto+dSraPnEiOVWQJaeepmyvk7K+LG39/TLlbVmQKgEK5i499pj02mvSmWdKa9ZIzz4bbT/2WPM7z6zlgGlSE90s6ytbWWM/IHCj9LK2mCd9rqi29bm52px1vL10qXTxxdIvfhGdZ80aacWKaP/QUPPxZG0/b9VxmfR63tPT9suUt2VC4EapZW0xT/qcVEzb+o4dUeojfuAYV48sWSJ94hNRRcaBA9F7zaIc9/ve1/oas7Sfb97cODVR/95GrxcxPW1RU94OKnLcKK2sZWStPnfiRP6laUklf6+8Mh+0q8vo4jK/VuNpt8TuxInkssU4h91uWV+nijjmoOKOG6WVJlebpaQtPnaepWlxyV8crOOSv3e8I9r/4IPNUwWbNyePJ++yvbjL8Yoral93b52CQTlwx41SSyojy1rSVlRpWhy8q8Vpk6QyuiKuMU3ZXrM7YLocy4/AjVJrlovtpKStqNK0OD1SrbrNvVmgLOIaW52v26kk5ItUCUqrVRnZtm3R13ZL2tzn8815laZV57Tj9Ei8fcstzTski7rGpOvoRSoJ+eKOG6XVana8oaFsM9UtWZL/jHtDQ9Fx46Adp03e8Y5of1Jbe6N88xVXpLvGZp9rdR29SCUhP9xxo9SSysg6KWkrojTtk5+sreOOg3ezoF2t3TRK9Z1x0nGaaXXcpFJC9B6BG6XXrByu3W686u2iStPqg3SroF2db5Zqr2PjxtoywmYpn0afS6oCafWzKyKVhHwRuBGkfunG66Ssr1UZYdI5k3529ccJ8efa78wLeEy8fv2433rrwdyPC9TL2tberDW903Nm5R6lWmI7dqS7jqTPpTlnlp8dirF1qz3s7uNp3svDSQQtSy1yJ6vRFFHj3Ko8sd38d9p7sV6kkpAPAjf6TlKd8iuvZFuNptVxs9Y41+eb066qk/Vz6A/kuNF3WuWN3/e+5NVoWs241+y4We5Ks+bq+yXHj2wI3OhLe/fOd0nGVSju0X4pmpnv0UfnX6tejSZppr44QDabLjWLrDPnMePe4CJVgr4TrzjzT/8kvfBCtP3CC9F2nCppthpNq3bvotrls+aUyUUPJu640ZeSAljSajQ33dS8xE5iJReUQ+o7bjNbZGY/MLOvFzkgoB31DxPn5ubzv1u3SuecE22fc060vXTp/Go0a9ZEr61ZE20vXSotWjQ/P0hs27b5HHdSK32cWqlWvZ30GtCOdu64b5D0uKTlBY0FaEuaFWeq87/uUdPK5s3Jq9F8//u1ufFbbpEuuSTKKWddkUYqZtUdDKZUd9xmtk7SeyTdUexwgHSyrjize3cUMJu9NjUVHeN1r5M+//no66OPRsE8aXrWVivS5F1GiMGWqnPSzO6V9DlJyyT9X3d/b9L76ZxEvSI68aqDdax6xZksd7/uUZCOF/V1jxb1veQSacuW1tdYnfOWGufH618jLw4p585JM3uvpOfd/eEW79tuZgfN7OCLL86kHCoGQVErqiStOBOfp1q83Wo1mg0baj+3YUO64MpUqeiWNKmSyyVtNbNnJP2DpCvNbLL+Te6+093H3X18dHQs52EiVEV0G8aarThz6lR07Hgx3vicBw60XoC3WRnhiROtx5pUKlhUGSEGU8uHk+7+aUmfliQz26QoVXJdweNCnyii21BKXnHmT/5E+sxnsp0zqVMxSdJUqfEvCsoIkRcacFC4ItIE8Yoz1a3qN90UbS9ZEpX1tXvOpDLCVm3kSaWCS5a0LiME2tFWA46775O0r5CRoG8lrbbSSdB629uiFEZ1rnrDhihQZj1nXCrYqIywlV6suoPBxB03ClXULHZx7rxZHnv37uwz7jUqFUw7VqZKRTfQ8o5CFTWLXXwc99o8drx4btLKMcy4h9ARuFG4omax27t3PpVR/XXvXmbcQ38jVYKuyDtNEKdKHnigtnTvgQeSS/56MVYgbwRuBCspVw30MwI3gmQWVY9cc01t6d4110T7W83UB4SMwI1gbd48304uzX+/eXNxbfZAGfBwEkFK6lSMX4+nba1+bePGfCa4AnqJwI0gtSrdi+/G82yzB8qCwI22FDE9a1atSveSFvUt03UA7SLHjdTKmDduVrqXNBtfGa8DaAeBG6kUOT1r3pLa7HfvDuc6gGZIlSCVoqZnLUKa/LdU/usAmiFwI7U4ADbLG5dJJ/lvoOxIlSC10FZxyZL/BkLAHTdSaVU3Hcoda79cB8I28alj0kvH53e8+GJbnydwY4FmpXIjI/PTplZPqxrSlKdM3YpemJqS9n3hkHTy5Ol9+7d8bv4N558v+2z64xG4UWPPnqi6Ig5q8R3qyEj0ej/MnMfUrSjKxISkY8ek539eE6QladPoI7r5Syur9mRfupfAjdOqS/6k2jTCFVfMdyLWvxZiG3k//AJCb01OSke+9ciC/fsv/Li0UtKNN9a9snLBe7MicOO0ViV/McroMEgmJ+e/P/LDY9L04dPbN667W9f82RV1n6gP2PkjcKNGq5I/yugwCCY+8tPom8pDw02j0Z31+ZJuvuEn0qWXVt5ZH7S7g8CNGkmro8ffN3qN4I1QTXzkpwuqOjaNPqKbf+1b0cZ116k2zZFfyiMrAjdOSyqVi3PYlNEhRFNT0r59VTv+fT43vXbxUd1zw79U3UVLUXDO/vCwaARunNaqVE6ijA7hmJhQTYDeNPqIbj5vV7RxoeoeHlYH7fIjcKNGq1I5yuhQNpOT0pEjqgnSsf1bPldJdUiVUo9uDq0wBG4skFQqRxkdeqlRx+HaxUe1aWRaN1+4q0EJXnnTHZ0gcAMorakpad9ttXfS9R2HUW66f+6m02gZuM3sLEnfkXRm5f33uvsfFT0whIdVZZDVxETlm8cPLeg4XFgr3Z930e1Ic8f9mqQr3f1lMxuWdMDMvuXu/7/gsSEgSa3yV1/d69GhTCYnpSP/3CRA/+q/Nkh39KZWusxaBm53d0kvVzaHK/8xASZOS2qVD7EdHvlov+PwChGk00mV4zazRZIelvQ/Jd3u7t8rdFQISkir46BYZe847BepAre7n5J0kZmdI2m3mW1w98eq32Nm2yVtl6SxsTflPlCUW0ir4yAfIXYc9ou2qkrc/QUz2yfpakmP1b22U9JOSVq/fpxUyoBJapUneIerZcfhXa/WfaLcHYf9Ik1VyZik2UrQHpH0G5L+rPCRIRisKtNfJj5VO5/0jevuPv3aNRc2eniIbktzx71G0v+r5LmHJH3F3b9e7LAQElaVCVPNw8N/brA6y+mOw+p8NLnpMkhTVfKopIu7MBYEjFVlym9yUjryr/MPD9cuPqrzR6YlSeePKLfVWVA8OieRG9rhy6NRx6FUWZ1l7dq6+TsQGgI3ELDTHYdStNZhCVZnQfEI3EBgJj7y06jjqdHDwy3PNMlNo58QuIESmpqSnnyykpOuq5Veu/io7vk//9KkmYVgPQgI3ECPTU1J++786fyOqq7DhR2HsbAm/ke+CNxADzRcnSXuOJTqug55gIhaBG6gQKcfHqZanYUSPKRD4AZycrrjMHbypNYuPqrrVn27ScchgRrZELiBNsUPDqUmHYfnnx9t1Dw85KEh8kPgBlo43XFYKcGj4xC9RuAGqkxOSke+Rcchyo3AjYFExyFCRuDGwJj44KHoGzoOETgCN/rK1FT0dd+dTVZnuf4n0call4qOQ4SKwI1gJXUcblKjjsOVIjeNfkDgRlDoOAQI3CgpOg6B5gjc6Dk6DoH2ELjRNfGDQ2nh6iz7b7hvfoOOQyARgRuFmZiQ9Extx2HsxnXfrquVZppSIC0CN3KRvuMwxp00kBWBG22h4xDoPQI3WkrsOLxhcZMltAAUhcANSZ10HALoNgL3AJv41LHom0q6Y+3io9o0Mq2b76pvXKHjECgTAveAmPhUbT46tn/L56S3i+lKgYAQuPtMzcPDxxuszrKguoNmFiA0LQO3mb1R0t9JeoOkOUk73f22ogeGdCYnK8tnSTUdh5KkVaqr8iBIA/0gzR33LyV90t3/zcyWSXrYzL7t7ocKHhuqnH54eFuTWulNm6juAAZEy8Dt7s9Kerby/Utm9rikcyURuAsyMaGoRjpW9fBwYcehRK00MFjaynGb2XmSLpb0vQavbZe0XZLGxt6Uw9AGy8RHasvw9l/48eibtWvrHh5yNw0MutSB28zOlnSfpD9w9+P1r7v7Tkk7JWn9+nHPbYR9ZHJSOnJE0fwddbXSaxcf1T13vVq1p7i76Cs/8Qkdrzu/JC0fHdVDt95ammMCaCxV4DazYUVB+y53/8dih9QfpqakfV+oyiZVdx0uk665fnHd6izdc/zFF3VwdHTB/vEGgbeXxwTQWJqqEpO0S9Lj7s6tU52aqUr3aeHqLHHHoUTXIYBcpLnjvlzS/5L0QzOLo9Jn3P2bxQ2r3Bp1HErSWkn3bPliXTMLDS0A8pWmquSAJOvCWEqpUcfh2sVHdc+v/rH09kbTlVIrDaBYdE5WtN9xSAkegN4Y2MA9yB2Hy0dHGz40XN7g4WIvjwmgsb4P3FNT0pNPJqzOMoAdhyGV5537gQ9Is7MLXxge1s+++tVMx6R0EaHrq8BNx2HvFFYOODurnw0PL9h9bqNgnhKliwhd8IF74oN1+ei441Cqe3g4GHfTAPpfEIE7qeNw0+gjuvlL1SV33EUD6G+lC9ztdxxSJ91IUh73icOHM+WNV27bpmFfOJvBrJmGFy3S+C9+seC16faGDSCFngVuOg6LlZjHzZg3HnbXc7awpP8N7lo0N6eDOeeiATTW1cBNx2H/Ghoa0qFTpxru78jwcOPg3+CXRFqULiJ0hQXuxI7DlZJurM9F91etdDckpUOySkyHSJpr8JoknfzlL9Xo3vqkWpf0FXEdQD8rJHA/9/QJvWHpYe2/4b4GM+Dx8DAvRZS1JaVDJKnZ/bNJurDJ/lapmSLSOkkoB0ToCgncb33LrPbfelhSb6YtBYB+VrqqEuQjKY/77PHjzfPGr73W9JivKVoxutF+kzTe4LWTkkbSDRlASgTuHuuk/frpmRmdOzOzYP+rkv5z166mnzv3Ax9IPG6zPPaQpNUN9k9LGlaD9ewULU56am5Ohxr8Qlj4KLM9tK5jUBG4e6yTfOtiST9LyEc31SJv3CyPPSzp3xPOtyjhlBc0+JxajbMFctUYVATuwL3aYfCrl5QOOVPSoSbnS/rckKQLG1WqVL5mTutkRDkgQkfg7rGkdEerVMCioSGNNAhgi2ZnM5fY/crYWNO72OkG44wtGRpqehe/ZuXKxDvjpLRG0nUceuaZTN2apFEQOgJ3jyWlOzpJBRSVRigi5ZEk6Tro1sSg6rCtDQDQbdxxl0DmPHXWdvCEzyXlf2dnZprmqhdlPGYnCmuzB0qOwN1jSXnqVpJm8hv/0IcyfS7JG3/7t3V3g/2bJR3OeMxOrF6xQhc0CP6rO0gHUWKIEBC4kdrc3JwuaPBLZq6PcsqUGCIEBO5eKyjFUER64tTQkMYbpCZOFZiaaHUdlPVhEBG4uyDpz++saYtWivizft2KFV2/GyU9ASxE4O4C/vwGkCcevwNAYFrecZvZ30p6r6Tn3X1D8UNCWQ1Cq/ggXCPClyZVcqekv5L0d8UOBe3qdunaIOSbB+EaEb6Wgdvdv2Nm5xU/FLSL3DkwmHg42QX8+Q0gT7kFbjPbLmm7JL1pbCyvw/YF/vwGkKfcqkrcfae7j7v7+Bh3kgBQGMoBASAwacoB75a0SdLrzWxa0h+5e/MFDdE15M6BwZSmquTabgwE7SN3DgwmUiUAEBgCNwAEhsANAIEhcANAYAjcABAYAjcABIbADQCBIXADQGAI3AAQGAI3AASGwA0AgSFwA0BgCNwAEBgCNwAEhsANAIEhcANAYAjcABAYAjcABIbADQCBIXADQGAI3AAQGAI3AASGwA0AgSFwA0BgCNwAEBgCNwAEhsANAIFJFbjN7Goze8LMnjKzPyx6UACA5loGbjNbJOl2SVskXSDpWjO7oOiBAQAaS3PHfamkp9z9aXc/KekfJG0rdlgAgGbSBO5zJR2u2p6u7AMA9MAZKd5jDfb5gjeZbZe0vbL5sm3d+kQnAyuJ10s62utBlBQ/m2T8fJrjZ9PY/0j7xjSBe1rSG6u210k6Uv8md98paWfaE4fAzA66+3ivx1FG/GyS8fNpjp9N59KkSr4vab2ZvdnMFkv6PUkPFDssAEAzLe+43f2XZvYxSXslLZL0t+7+o8JHBgBoKE2qRO7+TUnfLHgsZdRXqZ+c8bNJxs+nOX42HTL3Bc8ZAQAlRss7AASGwN2EmS0ysx+Y2dd7PZayMbNnzOyHZvaImR3s9XjKxMzOMbN7zezHZva4mV3W6zGVhZm9tfL/TPzfcTP7g16PK0SpctwD6gZJj0ta3uuBlNSvuzu1uAvdJmmPu/9OpQprSa8HVBbu/oSki6TTU2n8TNLung4qUNxxN2Bm6yS9R9IdvR4LwmFmyyW9S9IuSXL3k+7+Qm9HVVrvlvQTd/+PXg8kRATuxv5c0o2S5no9kJJySQ+a2cOVjllE3iJpRtKXKmm2O8xsaa8HVVK/J+nuXg8iVATuOmb2XknPu/vDvR5LiV3u7u9UNGPkR83sXb0eUEmcIemdkr7g7hdLekUS0yDXqaSQtkr6aq/HEioC90KXS9pqZs8omgnxSjOb7O2QysXdj1S+Pq8oR3lpb0dUGtOSpt39e5XtexUFctTaIunf3P3nvR5IqAjcddz90+6+zt3PU/Tn3EPufl2Ph1UaZrbUzJbF30u6StJjvR1VObj7c5IOm9lbK7veLelQD4dUVteKNElHqCpBu1ZL2m1mUvT/z5fdfU9vh1QqH5d0VyUd8LSkD/Z4PKViZksk/aak/93rsYSMzkkACAypEgAIDIEbAAJD4AaAwBC4ASAwBG4ACAyBGwACQ+AGgMAQuAEgMP8NicRb74pAt94AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 测试\n",
    "ppn = Perceptron(eta=0.1, random_state=0)\n",
    "ppn.fit(X,y)\n",
    "plot_decision_regions(X,y,classifier=ppn)\n",
    "plt.legend();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. dual形式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DualPerceptron:\n",
    "    \"\"\"Perceptron classifier-Dual.\n",
    "    Parameters\n",
    "    --------------\n",
    "    eta : float\n",
    "        Learning rate\n",
    "    random_state : int\n",
    "        random seed\n",
    "        \n",
    "    Attributes\n",
    "    --------------\n",
    "    alpha_ : 1d-array\n",
    "        Weights for each sample\n",
    "    errors_ : list\n",
    "        Number of updates in each epoch\n",
    "    X_add_ : nd-array, shape = [n_samples, n_features+1]\n",
    "        Training vectors added 0-dimension for prediction\n",
    "    y_ : 1d-array, shape = [n_samples,]\n",
    "        Target values for prediction\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, eta=0.01, random_state=1):\n",
    "        self.eta = eta\n",
    "        self.random_state = random_state\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        \"\"\"Fitting training data.\n",
    "        Parameters\n",
    "        --------------\n",
    "        X : nd-array, shape = [n_samples, n_features]\n",
    "            Training vectors\n",
    "        y : 1d-array, shape = [n_samples,]\n",
    "            Target values\n",
    "        \n",
    "        Return\n",
    "        --------------\n",
    "        self : object\n",
    "        \"\"\" \n",
    "        n_samples = X.shape[0]        # n_samples\n",
    "        n_features = X.shape[1]       # n_features\n",
    "        # Add 0-dimension\n",
    "        X_add = np.hstack([np.ones((n_samples,1)), X])\n",
    "        # Initialization\n",
    "        self.X_add_ = X_add\n",
    "        self.y_ = y\n",
    "        self.alpha_ = np.zeros(n_samples)\n",
    "        self.errors = []\n",
    "        rgen = np.random.RandomState(self.random_state)\n",
    "        index = rgen.permutation(range(n_samples))         # Random index of samples\n",
    "        updates = 0                                        # Total updates\n",
    "        # Gram Matrix\n",
    "        gram = X_add.dot(X_add.T)\n",
    "        # Start\n",
    "        while True:\n",
    "            errors = 0\n",
    "            for i in index:\n",
    "                y_hat = np.sign((self.alpha_*y).dot(gram[:,i]))\n",
    "                y_hat = -1 if y_hat==0 else y_hat\n",
    "                if y_hat != y[i]:\n",
    "                    errors += 1\n",
    "                    self.alpha_[i] += eta\n",
    "            self.errors.append(errors)\n",
    "            if errors == 0:\n",
    "                break\n",
    "            updates += errors\n",
    "        return self\n",
    "    \n",
    "    def predict(self, X):\n",
    "        X = np.array(X)\n",
    "        if len(X.shape) == 1:\n",
    "            X_add = np.hstack([1,X])\n",
    "        else:\n",
    "            X_add = np.hstack([np.ones((X.shape[0],1)),X])\n",
    "        scores = ((self.alpha_*self.y_).T).dot(self.X_add_.dot(X_add.T))\n",
    "        return np.where(scores > 0, 1, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAW4AAAD8CAYAAABXe05zAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAGz1JREFUeJzt3X+MXPV57/HPs2YNa2MvjrN2bJxckl4TlTgBogWJgiOXtBgrwW6aRi0SVyKN4qubH6JKrkgT/qgqQtOuYlTaorQObrjtEkoCNaH5YRMVubHV3GxMQwkxARFC5Y0hrN2AAVO88T7948zxzszOnDlz5pyZ8515vyS0e87MnPM9a/Tsd5/zPOdr7i4AQDiGej0AAEB7CNwAEBgCNwAEhsANAIEhcANAYAjcABAYAjcABIbADQCBIXADQGDOSPMmMztH0h2SNkhySb/v7t9t9v7ly1/vq1efl8sAAWAQPPXUw0fdfSzNe1MFbkm3Sdrj7r9jZoslLUl68+rV5+nWWw+mPDQAYOtW+4+0720ZuM1suaR3Sbpektz9pKSTWQcHAOhMmhz3WyTNSPqSmf3AzO4ws6X1bzKz7WZ20MwOvvjiTO4DBQBE0gTuMyS9U9IX3P1iSa9I+sP6N7n7Tncfd/fx0dFUaRoAQAZpctzTkqbd/XuV7XvVIHADQLcNDc1q5cppDQ//V6+Hktrs7Fk6dmyd5uaGMx+jZeB29+fM7LCZvdXdn5D0bkmHMp8RAHKycuW01qxZpuXLz5OZ9Xo4Lbm7jh8/JmlaMzNvznyctFUlH5d0V6Wi5GlJH8x8RgDIyfDwfwUTtCXJzLR8+UodPdrZfcBUgdvdH5E03tGZAKAAoQTtWB7jpXMSAAJD4AaAnDz55I911VWXafXqM/WXf/n5ws6TNscNAGhhxYrX6U//9C/0jW/cX+h5CNwABsK2Ky/RSzPPL9i/bGyVvvbQ93M5x9jYKo2NrdKDD34jl+M1Q+AGMBBemnleU69f2Bx4aYNgXnbkuAEgMARuAOjAF794uzZuvEgbN16kZ5890pVzkioBgA58+MMf1Yc//NGunpPADQA5+fnPn9OVV47rpZeOy2xIf/3Xf67vfveQli9fnut5CNwABsKysVUNb0QuG1uV2zlWr36DfvSj6dyO1wyBG8BAyKvkrwy4OQkAgSFwA0BgCNwAEBgCNwAEhsANAIEhcANAhz72sd/X+vWrdNllG7pyPgI3gIHhnryd1bXXXq97792Tz8FSIHADGAh33indfvt8sHaPtu+8s/NjX375u7Rixes6P1BKBG4Afc9devll6b775oP37bdH2y+/nN/Mu1vonATQ98ykj1aeA3XffdF/kvT+90f7A1tvmBk3gMFQHbxjIQZticAN5Kqom1/oXJweqVad8w4JgRvIyZ490v331978uv/+aD96qzqn/f73Sw89FH2tznl34kMfulZXXXWZnnrqCb3tbev093+/K5+BN0GOG8iBu/Tqq9L+/dH2b/1WFLT375c2boxeD/FP8n5hJp19dm1OO06bnH125/82u3bd3fkg20DgBnJgFgVrKQrWcQDfuDHaT9Duveuvr/0FGgfvEP9tUqVKzOwZM/uhmT1iZgeLHhQQourgHQs1aPdrrr7+3yLEfxupvRz3r7v7Re4+XthogIDFOe1q1TnvUISWq/fAfsB5jJebk0AO4uAW57R37Ii+7t8fVvCuztXH446v69VXy3cds7Nn6fjxY8EEb3fX8ePHNDt7VkfHSZvjdkkPmplL+ht339nRWYE+YyaNjNTmtOO0ychIOH+Sh5arP3ZsnaRpHT060+uhpDY7e1Zl3NmlDdyXu/sRM1sl6dtm9mN3/071G8xsu6TtkjQ29qaOBgWE6OqrF978yiPY1VekFF2hEo87DtpS+uvo9ljn5oY1M/Pm4k5QUqlSJe5+pPL1eUm7JV3a4D073X3c3cdHR8fyHSUQiLxvfvUi35w1Vx9abjxkLQO3mS01s2Xx95KukvRY0QMDBl0v8s1Zc/Wh5cZDlyZVslrSboumDmdI+rK78zsUA6tb6YBe5JvT5OqbXX9IufHQtQzc7v60pAu7MBag9PbsiWaQcTCKZ5YjI1GOO2+d5JuzSsrVt7r+bo91UFEOCKTUy9RFtW6UFzbK1be6/rm5/qhjDwEt70BK3U4H1Oebq59/InV/Npt0/du2SV/7WnnG2u+YcQNt6KStfW4uebvRuRrlmzduLL42vFnLe7PrHxpqPdZ+baPvBQI30IasqYsdO6RbbpkP1nNz0faOHenOmbSdt6SyvqTrj3Pc9bnxq6+mVDBvBG4gpaylcnNz0okT0qOPzgfvW26Jtk+caD7zjnPKBw7U5pQPHCg2p56Ux969O/n6s+TGmXm3jxw3kFLWtvahIemmm6TPfjYK1r/7u9H+t7892j/UZPrUaU69VdlilrK+vXvbv35KBfPHjBtoQ1I6IMmDD0obNtSmCjZsiPYnyZpTb5WaSHo96ZxZr7+fHnlbBgRuoE3ttrW7RymRr3xFOnUq2j51Kto+cSI5VZAlp56mbK+Tsr4sbf398sjbsiBVAhTMXXrsMem116Qzz5TWrJGefTbafuyx5jPPrOWAaVIT3SzrK1tZYz8gcKP0sraYJ32uqLb1ubnanHW8vXSpdPHF0i9+EZ1nzRppxYpo/9BQ8/FkbT9v1XGZ9Hrej6ftl0felgmBG6WWtcU86XNSMW3rO3ZEqY/4hmNcPbJkifSJT0QVGQcORO81i3Lc73tf62vM0n6+eXPj1ET9exu9XsTjaYt65O2gIseN0spaRtbqcydO5F+allTy98or80G7uowuLvNrNZ52S+xOnEguW4xz2O2W9XWqiGMOKmbcKK00udosJW3xsfMsTYtL/uJgHZf8veMd0f4HH2yeKti8OXk8eZftxV2OV1xR+7p76xQMyoEZN0otqYwsa0lbUaVpcfCuFqdNksroirjGNGV7zWbAdDmWH4EbpdYsF9tJSVtRpWlxeqRadZt7s0BZxDW2Ol+3U0nIF6kSlFarMrJt26Kv7Za0uc/nm/MqTavOacfpkXj7lluad0gWdY1J19GLVBLyxYwbpdXq6XhDQ9meVLdkSf5P3Bsaio4bB+04bfKOd0T7k9raG+Wbr7gi3TU2+1yr6+hFKgn5YcaNUksqI+ukpK2I0rRPfrK2jjsO3s2CdrV20yjVM+Ok4zTT6rhJpYToPQI3Sq9ZOVy73XjV20WVptUH6VZBuzrfLNVex8aNtWWEzVI+jT6XVAXS6mdXRCoJ+SJwI0j90o3XSVlfqzLCpHMm/ezqjxPiz7XfmRdwm3j9+nG/9daDuR8XqJe1rb1Za3qn58zKPUq1xHbsSHcdSZ9Lc84sPzsUY+tWe9jdx9O8l5uTCFqWWuROVqMposa5VXliu/nvtHOxXqSSkA8CN/pOUp3yK69kW42m1XGz1jjX55vTrqqT9XPoD+S40Xda5Y3f977k1WhaPXGv2XGzzEqz5ur7JcePbAjc6Et79853ScZVKO7Rfil6Mt+jj86/Vr0aTdKT+uIA2exxqVlkfXIeT9wbXKRK0HfiFWf+6Z+kF16Itl94IdqOUyXNVqNp1e5dVLt81pwyuejBxIwbfSkpgCWtRnPTTc1L7CRWckE5pJ5xm9kiM/uBmX29yAEB7ai/mTg3N5//3bpVOuecaPucc6LtpUvnV6NZsyZ6bc2aaHvpUmnRovnng8S2bZvPcSe10seplWrV20mvAe1oZ8Z9g6THJS0vaCxAW9KsOFOd/3WPmlY2b05ejeb736/Njd9yi3TJJVFOOeuKNFIxq+5gMKWacZvZOknvkXRHscMB0sm64szu3VHAbPba1FR0jNe9Tvr856Ovjz4aBfOkx7O2WpEm7zJCDLZUnZNmdq+kz0laJun/uvt7k95P5yTqFdGJVx2sY9UrzmSZ/bpHQTpe1Nc9WtT3kkukLVtaX2N1zltqnB+vf428OKScOyfN7L2Snnf3h1u8b7uZHTSzgy++OJNyqBgERa2okrTiTHyeavF2q9VoNmyo/dyGDemCK49KRbekSZVcLmmrmT0j6R8kXWlmk/Vvcved7j7u7uOjo2M5DxOhKqLbMNZsxZlTp6Jjx4vxxuc8cKD1ArzNyghPnGg91qRSwaLKCDGYWt6cdPdPS/q0JJnZJkWpkusKHhf6RBHdhlLyijN/8ifSZz6T7ZxJnYpJkh6VGv+ioIwQeaEBB4UrIk0QrzhT3ap+003R9pIlUVlfu+dMKiNs1UaeVCq4ZEnrMkKgHW014Lj7Pkn7ChkJ+lbSaiudBK23vS1KYVTnqjdsiAJl1nPGpYKNyghb6cWqOxhMzLhRqKKeYhfnzpvlsXfvzv7EvUalgmnHyqNS0Q20vKNQRT3FLj6Oe20eO148N2nlGJ64h9ARuFG4op5it3fvfCqj+uvevTxxD/2NVAm6Iu80QZwqeeCB2tK9Bx5ILvnrxViBvBG4EaykXDXQzwjcCJJZVD1yzTW1pXvXXBPtb/WkPiBkBG4Ea/Pm+XZyaf77zZuLa7MHyoCbkwhSUqdi/Hr82Nbq1zZuzOcBV0AvEbgRpFale/FsPM82e6AsCNxoSxGPZ82qVele0qK+ZboOoF3kuJFaGfPGzUr3kp7GV8brANpB4EYqRT6eNW9Jbfa7d4dzHUAzpEqQSlGPZy1Cmvy3VP7rAJohcCO1OAA2yxuXSSf5b6DsSJUgtdBWccmS/wZCwIwbqbSqmw5lxtov14GwTXzqmPTS8fkdL77Y1ucJ3FigWancyMj8Y1OrH6sa0iNPeXQremFqStr3hUPSyZOn9+3f8rn5N5x/vuyz6Y9H4EaNPXui6oo4qMUz1JGR6PV+eHIej25FUSYmJB07Jj3/85ogLUmbRh/RzV9aWbUn+9K9BG6cVl3yJ9WmEa64Yr4Tsf61ENvI++EXEHprclI68q1HFuzff+HHpZWSbryx7pWVC96bFYEbp7Uq+YtRRodBMjk5//2RHx6Tpg+f3r5x3d265s+uqPtEfcDOH4EbNVqV/FFGh0Ew8ZGfRt9UbhpuGo1m1udLuvmGn0iXXlp5Z33Q7g4CN2okrY4ef9/oNYI3QjXxkZ8uqOrYNPqIbv61b0Ub112n2jRHfimPrAjcOC2pVC7OYVNGhxBNTUn79lXt+Pf53PTaxUd1zw3/UjWLlqLgnP3mYdEI3DitVamcRBkdwjExoZoAvWn0Ed183q5o40LV3TysDtrlR+BGjValcpTRoWwmJ6UjR1QTpGP7t3yukuqQKqUe3RxaYQjcWCCpVI4yOvRSo47DtYuPatPItG6+cFeDErzypjs6QeAGUFpTU9K+22pn0vUdh1Fuun9m02m0DNxmdpak70g6s/L+e939j4oeGMLDqjLIamKi8s3jhxZ0HC6sle7PWXQ70sy4X5N0pbu/bGbDkg6Y2bfc/f8XPDYEJKlV/uqrez06lMnkpHTkn5sE6F/91wbpjt7USpdZy8Dt7i7p5crmcOU/HoCJ05Ja5UNsh0c+2u84vEIE6XRS5bjNbJGkhyX9T0m3u/v3Ch0VghLS6jgoVtk7DvtFqsDt7qckXWRm50jabWYb3P2x6veY2XZJ2yVpbOxNuQ8U5RbS6jjIR4gdh/2iraoSd3/BzPZJulrSY3Wv7ZS0U5LWrx8nlTJgklrlCd7hO33zsL7j8K5X695Z7o7DfpGmqmRM0mwlaI9I+g1Jf1b4yBAMVpXpLxOfavw86RvX3a1rLmx08xDdlmbGvUbS/6vkuYckfcXdv17ssBASVpUJU83Nw39usDrLdfUzZ24elkWaqpJHJV3chbEgYKwqU36Tk9KRf52/ebh28VGdPzItSTp/RLmtzoLi0TmJ3NAOXx6NOg6lyuosa9fWPb8DoSFwAwE7fdNQitY6LMHqLCgegRsIzMRHfhp1PFVy0jeuu/v0a9dseaZqNk0+ul8RuIESmpqSnnyykpOuq5Veu/io7vk//9KkmYVgPQgI3ECPTU1J++786fyOqq7DhR2HsbAe/I98EbiBHmi4OkvccSjVdR1yAxG1CNxAgRp1HMYWrs5CCR7SIXADOTndcRg7eVJrFx/Vdau+3aTjkECNbAjcQJviG4dSk47D88+PNmpuHnLTEPkhcAMtnO44rJTg0XGIXiNwA1UmJ6Uj36LjEOVG4MZAouMQISNwY2BMfPBQ9A0dhwgcgRt9ZWoq+rrvziars1z/k2jj0ktFxyFCReBGsJI6DjepUcfhSpGbRj8gcCModBwCBG6UFB2HQHMEbvQcHYdAewjc6Jr4xqG0cHWW/TfcN79BxyGQiMCNwkxMSHqmtuMwduO6b9fVSvOYUiAtAjdykb7jMMZMGsiKwI220HEI9B6BGy0ldhzesLjJEloAikLghqROOg4BdBuBe4BNfOpY9E0l3bF28VFtGpnWzXfVN67QcQiUCYF7QEx8qjYfHdu/5XPS28XjSoGAELj7TM3Nw8cbrM6yoLqDZhYgNC0Dt5m9UdLfSXqDpDlJO939tqIHhnQmJyvLZ0k1HYeSpFWqq/IgSAP9IM2M+5eSPunu/2ZmyyQ9bGbfdvdDBY8NVU7fPLytSa30pk1UdwADomXgdvdnJT1b+f4lM3tc0rmSCNwFmZhQVCMdq7p5uLDjUKJWGhgsbeW4zew8SRdL+l6D17ZL2i5JY2NvymFog2XiI7VlePsv/Hj0zdq1dTcPmU0Dgy514DazsyXdJ+kP3P14/evuvlPSTklav37ccxthH5mclI4cUfT8jrpa6bWLj+qeu16t2lPcLPrKT3xCx+vOL0nLR0f10K23luaYABpLFbjNbFhR0L7L3f+x2CH1h6kpad8XqrJJ1V2Hy6Rrrl9ctzpL9xx/8UUdHB1dsH+8QeDt5TEBNJamqsQk7ZL0uLszdapT86jSfVq4OkvccSjRdQggF2lm3JdL+l+SfmhmcVT6jLt/s7hhlVujjkNJWivpni1frGtmoaEFQL7SVJUckGRdGEspNeo4XLv4qO751T+W3t7ocaXUSgMoFp2TFe13HFKCB6A3BjZwD3LH4fLR0YY3DZc3uLnYy2MCaKzvA/fUlPTkkwmrswxgx2FI5XnnfuAD0uzswheGh/Wzr3410zEpXUTo+ipw03HYO4WVA87O6mfDwwt2n9somKdE6SJCF3zgnvhgXT467jiU6m4eDsZsGkD/CyJwJ3Ucbhp9RDd/qbrkjlk0gP5WusDdfschddKNJOVxnzh8OFPeeOW2bRr2hU8zmDXT8KJFGv/FLxa8Nt3esAGk0LPATcdhsRLzuBnzxsPues4WlvS/wV2L5uZ0MOdcNIDGuhq46TjsX0NDQzp06lTD/R0ZHm4c/Bv8kkiL0kWErrDAndhxuFLSjfW56P6qle6GpHRIVonpEElzDV6TpJO//KUaza1PqnVJXxHXAfSzQgL3c0+f0BuWHtb+G+5r8AQ8bh7mpYiytqR0iCQ1mz+bpAub7G+VmikirZOEckCErpDA/da3zGr/rYcl9eaxpQDQz0pXVYJ8JOVxnz1+vHne+LXXmh7zNUUrRjfab5LGG7x2UtJIuiEDSInA3WOdtF8/PTOjc2dmFux/VdJ/7trV9HPnfuADicdtlscekrS6wf5pScNqsJ6dosVJT83N6VCDXwgLb2W2h9Z1DCoCd491km9dLOlnCfnoplrkjZvlsYcl/XvC+RYlnPKCBp9Tq3G2QK4ag4rAHbhXOwx+9ZLSIWdKOtTkfEmfG5J0YaNKlcrXzGmdjCgHROgI3D2WlO5olQpYNDSkkQYBbNHsbOYSu18ZG2s6i51uMM7YkqGhprP4NStXJs6Mk9IaSddx6JlnMnVrkkZB6AjcPZaU7ugkFVBUGqGIlEeSpOugWxODqsO2NgBAtzHjLoHMeeqs7eAJn0vK/87OzDTNVS/KeMxOFNZmD5QcgbvHkvLUrSQ9yW/8Qx/K9Lkkb/zt39bdDfZvlnQ44zE7sXrFCl3QIPiv7iAdRIkhQkDgRmpzc3O6oMEvmbk+yilTYogQELh7raAUQxHpiVNDQxpvkJo4VWBqotV1UNaHQUTg7oKkP7+zpi1aKeLP+nUrVnR9Nkp6AliIwN0F/PkNIE/cfgeAwLSccZvZ30p6r6Tn3X1D8UNCWQ1Cq/ggXCPClyZVcqekv5L0d8UOBe3qdunaIOSbB+EaEb6Wgdvdv2Nm5xU/FLSL3DkwmLg52QX8+Q0gT7kFbjPbLmm7JL1pbCyvw/YF/vwGkKfcqkrcfae7j7v7+BgzSQAoDOWAABCYNOWAd0vaJOn1ZjYt6Y/cvfmChugacufAYEpTVXJtNwaC9pE7BwYTqRIACAyBGwACQ+AGgMAQuAEgMARuAAgMgRsAAkPgBoDAELgBIDAEbgAIDIEbAAJD4AaAwBC4ASAwBG4ACAyBGwACQ+AGgMAQuAEgMARuAAgMgRsAAkPgBoDAELgBIDAEbgAIDIEbAAJD4AaAwBC4ASAwBG4ACAyBGwACQ+AGgMCkCtxmdrWZPWFmT5nZHxY9KABAcy0Dt5ktknS7pC2SLpB0rZldUPTAAACNpZlxXyrpKXd/2t1PSvoHSduKHRYAoJk0gftcSYertqcr+wAAPXBGivdYg32+4E1m2yVtr2y+bFu3PtHJwEri9ZKO9noQJcXPJhk/n+b42TT2P9K+MU3gnpb0xqrtdZKO1L/J3XdK2pn2xCEws4PuPt7rcZQRP5tk/Hya42fTuTSpku9LWm9mbzazxZJ+T9IDxQ4LANBMyxm3u//SzD4maa+kRZL+1t1/VPjIAAANpUmVyN2/KembBY+ljPoq9ZMzfjbJ+Pk0x8+mQ+a+4D4jAKDEaHkHgMAQuJsws0Vm9gMz+3qvx1I2ZvaMmf3QzB4xs4O9Hk+ZmNk5Znavmf3YzB43s8t6PaayMLO3Vv6fif87bmZ/0OtxhShVjntA3SDpcUnLez2Qkvp1d6cWd6HbJO1x99+pVGEt6fWAysLdn5B0kXT6URo/k7S7p4MKFDPuBsxsnaT3SLqj12NBOMxsuaR3SdolSe5+0t1f6O2oSuvdkn7i7v/R64GEiMDd2J9LulHSXK8HUlIu6UEze7jSMYvIWyTNSPpSJc12h5kt7fWgSur3JN3d60GEisBdx8zeK+l5d3+412Mpscvd/Z2Knhj5UTN7V68HVBJnSHqnpC+4+8WSXpHEY5DrVFJIWyV9tddjCRWBe6HLJW01s2cUPQnxSjOb7O2QysXdj1S+Pq8oR3lpb0dUGtOSpt39e5XtexUFctTaIunf3P3nvR5IqAjcddz90+6+zt3PU/Tn3EPufl2Ph1UaZrbUzJbF30u6StJjvR1VObj7c5IOm9lbK7veLelQD4dUVteKNElHqCpBu1ZL2m1mUvT/z5fdfU9vh1QqH5d0VyUd8LSkD/Z4PKViZksk/aak/93rsYSMzkkACAypEgAIDIEbAAJD4AaAwBC4ASAwBG4ACAyBGwACQ+AGgMAQuAEgMP8Ng8RZ7wnrku0AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# 测试\n",
    "ppn_dual = DualPerceptron(eta=0.1, random_state=0)\n",
    "ppn_dual.fit(X,y)\n",
    "plot_decision_regions(X,y,classifier=ppn_dual)\n",
    "plt.legend();"
   ]
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}