multiclass support vector machine.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiclass Support Vector Machine\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "This notebook focuses on multiclass SVM with different methods including OVR (One-Versus-Rest), OVO (One-Versus-One), DAG (Directed Acyclic Graph). \n",
    "\n",
    "Reference to Binary SVM\n",
    "\n",
    "https://github.com/je-suis-tm/machine-learning/blob/master/binary%20support%20vector%20machine.ipynb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import cvxopt.solvers\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import copy\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.decomposition import PCA\n",
    "from sklearn.svm import SVC\n",
    "import os\n",
    "os.chdir('d:/python/data')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#plz refer to binary svm for this function\n",
    "def binary_svm(x_train,y_train,kernel='linear',poly_constant=0.0,poly_power=1,gamma=5):\n",
    "\n",
    "    y_product=np.outer(y_train,y_train)\n",
    "    \n",
    "    if kernel=='linear':\n",
    "        x_product=np.outer(x_train,x_train)\n",
    "    elif kernel=='polynomial':\n",
    "        arr=np.outer(x_train,x_train)\n",
    "        x_product=np.apply_along_axis(lambda x:(x+poly_constant)**poly_power,0,arr.ravel()).reshape(arr.shape)\n",
    "    else:\n",
    "        arr=np.mat([i-j for j in x_train for i in x_train]).reshape(len(x_train),len(x_train))\n",
    "        x_product=np.apply_along_axis(lambda x:np.exp(-1*gamma*(np.linalg.norm(x))**2),0,arr.ravel()).reshape(arr.shape)\n",
    "    \n",
    "    P=cvxopt.matrix(x_product*y_product)\n",
    "    q=cvxopt.matrix(-1*np.ones(len(x_train)))\n",
    "    G=cvxopt.matrix(np.diag(-1 * np.ones(len(x_train))))\n",
    "    h=cvxopt.matrix(np.zeros(len(x_train)))\n",
    "    A=cvxopt.matrix(y_train,(1,len(x_train)))\n",
    "    b=cvxopt.matrix(0.0)\n",
    "\n",
    "    solution=cvxopt.solvers.qp(P, q, G, h, A, b)\n",
    "    alpha=pd.Series(solution['x'])\n",
    "    w=np.sum(alpha*y_train*x_train)\n",
    "\n",
    "    b=-(min(x_train[y_train==1.0]*w)+max(x_train[y_train==-1.0]*w))/2\n",
    "\n",
    "    return w,b    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#first, one vs one multiclass svm\n",
    "#given n classes, we do n*(n-1)/2 times binary classification as one vs one\n",
    "#we would obtain w and b for each binary classification\n",
    "#when we make a prediction, we use each w and b to get the classification\n",
    "#now that we have a classification list of n*(n-1)/2\n",
    "#we just select the value with the most frequency in the list\n",
    "#that would be our prediction, voila!\n",
    "def get_accuracy_ovo(train,test,**kwargs):\n",
    "    \n",
    "    #calculate w and b for each binary classification\n",
    "    multiclass=train['y'].drop_duplicates().tolist()\n",
    "    multiclass_params={}\n",
    "    for i in range(len(multiclass)):\n",
    "        for j in range(i+1,len(multiclass)):\n",
    "            data=copy.deepcopy(train)\n",
    "            arr=np.select([data['y']==multiclass[i],data['y']==multiclass[j]], \\\n",
    "                            [-1.0,1.0],default=0.0)\n",
    "            data['y']=arr\n",
    "            data=data[data['y']!=0.0]\n",
    "            multiclass_params['{},{}'.format(multiclass[i], \\\n",
    "                                             multiclass[j])]=binary_svm(data['x'], \\\n",
    "                                                                        data['y'], \\\n",
    "                                                                        **kwargs)\n",
    "            \n",
    "    result=[]\n",
    "    \n",
    "    #store all the predictions in one list\n",
    "    #and select the value with the most frequency in this list\n",
    "    predict=[]\n",
    "    for i in train['x']:\n",
    "        arr=[]\n",
    "        for j in multiclass_params:\n",
    "            w=multiclass_params[j][0]\n",
    "            b=multiclass_params[j][1]\n",
    "            value=np.sign(np.multiply(w,i)+b)\n",
    "            arr.append(j.split(',')[0] if value==-1.0 else j.split(',')[1])\n",
    "        \n",
    "        predict.append(max(set(arr), key=arr.count))\n",
    "        \n",
    "    predict=pd.Series(predict).apply(int)\n",
    "    result.append('train accuracy: %.2f'%(\n",
    "        len(predict[predict==train['y']])/len(predict)*100)+'%')\n",
    "    \n",
    "    \n",
    "    #kinda the same as training sample prediction\n",
    "    predict=[]\n",
    "    for i in test['x']:\n",
    "        arr=[]\n",
    "        for j in multiclass_params:\n",
    "            w=multiclass_params[j][0]\n",
    "            b=multiclass_params[j][1]\n",
    "            value=np.sign(np.multiply(w,i)+b)\n",
    "            arr.append(j.split(',')[0] if value==-1 else j.split(',')[1])\n",
    "            \n",
    "        predict.append(max(set(arr), key=arr.count))\n",
    "\n",
    "    predict=pd.Series(predict).apply(int)\n",
    "    \n",
    "    result.append('test accuracy: %.2f'%(\n",
    "        len(predict[predict==test['y']])/len(predict)*100)+'%')\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#alternatively, one vs rest multiclass svm\n",
    "#given n classes, we do n times binary classification as one vs rest\n",
    "#we would obtain w and b for each binary classification\n",
    "#when we make a prediction, we use each w and b to get the decision function value\n",
    "#we select the classifier with the maximum decision function value\n",
    "#that classifier would return +1.0 and we would take it as the result\n",
    "def get_accuracy_ovr(train,test,**kwargs):\n",
    "    \n",
    "    multiclass=train['y'].drop_duplicates()\n",
    "    multiclass_params={}\n",
    "    \n",
    "    #calculate w and b for each binary classification\n",
    "    for i in multiclass:\n",
    "        data=copy.deepcopy(train)\n",
    "        data['y']=np.where(data['y']==i,1.0,-1.0)\n",
    "        multiclass_params[i]=binary_svm(data['x'],data['y'],**kwargs)\n",
    "\n",
    "    result=[]\n",
    "        \n",
    "    #store all the decision function values in one list\n",
    "    #and select the classifier which gives the largest value\n",
    "    predict=[]\n",
    "    for i in train['x']:\n",
    "        max_value=float('-inf')\n",
    "        idx=0\n",
    "        for j in multiclass_params:\n",
    "            w=multiclass_params[j][0]\n",
    "            b=multiclass_params[j][1]\n",
    "            value=np.multiply(w,i)+b\n",
    "            if value>max_value:\n",
    "                max_value=value\n",
    "                idx=j\n",
    "    \n",
    "        predict.append(idx)\n",
    "    \n",
    "    predict=pd.Series(predict).apply(int)\n",
    "    result.append('train accuracy: %.2f'%(\n",
    "        len(predict[predict==train['y']])/len(predict)*100)+'%')\n",
    "    \n",
    "    #kinda the same as training sample prediction\n",
    "    predict=[]\n",
    "    for i in test['x']:\n",
    "        max_value=float('-inf')\n",
    "        idx=0\n",
    "        for j in multiclass_params:\n",
    "            w=multiclass_params[j][0]\n",
    "            b=multiclass_params[j][1]\n",
    "            value=np.multiply(w,i)+b\n",
    "            if value>max_value:\n",
    "                max_value=value\n",
    "                idx=j\n",
    "    \n",
    "        predict.append(idx)\n",
    "\n",
    "    predict=pd.Series(predict).apply(int)\n",
    "    result.append('test accuracy: %.2f'%(\n",
    "        len(predict[predict==test['y']])/len(predict)*100)+'%')\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#dagsvm is not supported in sklearn\n",
    "#it is an optimization for multiclass ovo\n",
    "#it uses graph theory to avoid n*(n-1)/2 binary classification\n",
    "#it only takes n-1 binary classification\n",
    "def get_accuracy_dag(train,test,**kwargs):\n",
    "    \n",
    "    #the same as ovo\n",
    "    #except one more line to build a graph structure\n",
    "    #we denote the class as the node\n",
    "    #the edge as binary svm between two classes\n",
    "    #the weight as parameters w and b\n",
    "    multiclass=train['y'].drop_duplicates().tolist()\n",
    "    graph=nx.DiGraph()\n",
    "    for i in range(len(multiclass)):\n",
    "        for j in range(i+1,len(multiclass)):\n",
    "                \n",
    "            data=copy.deepcopy(train)\n",
    "            arr=np.select([data['y']==multiclass[i],data['y']==multiclass[j]], \\\n",
    "                            [-1.0,1.0],default=0.0)\n",
    "            data['y']=arr\n",
    "            data=data[data['y']!=0.0]\n",
    "            graph.add_edge(multiclass[i],multiclass[j],weight=binary_svm(data['x'], \\\n",
    "                                                                        data['y'], \\\n",
    "                                                                        **kwargs))\n",
    "   \n",
    "    result=[]\n",
    "    \n",
    "    #use directed acyclic graph to boost the speed of ovo\n",
    "    #for ovo, the time complexity is n*(n-1)/2\n",
    "    #where n is the dimension of classes\n",
    "    #for dag, the time complexity is only n-1\n",
    "    #in dag, once we have checked two classes and got the result\n",
    "    #we would remove the negative result from the graph structure\n",
    "    #and move on to the comparison with the next class \n",
    "    #until we only have one class left in dag\n",
    "    #which would become the final result\n",
    "    #as a tradeoff for time complexity\n",
    "    #the result isnt as accurate as ovo\n",
    "    predict=[]\n",
    "    for i in train['x']:\n",
    "        g=copy.deepcopy(graph)\n",
    "        \n",
    "        while len(g.nodes)>1:\n",
    "            \n",
    "            #beware, graph.nodes aint a list type\n",
    "            node0=list(g.nodes)[0]\n",
    "            node1=list(g.nodes)[1]\n",
    "            \n",
    "            #since the graph structure is directed\n",
    "            #the opposite direction between nodes do not exist\n",
    "            #we would not get the parameters w and b\n",
    "            #thats why we need to put a try to avoid keyerror\n",
    "            #if we make this graph structure undirected\n",
    "            #it would be impossible to identify which class is -1.0\n",
    "            try:\n",
    "                w=g[node0][node1]['weight'][0]\n",
    "                b=g[node0][node1]['weight'][1]\n",
    "                value=np.sign(np.multiply(w,i)+b)\n",
    "                g.remove_node(node1 if value==-1 else node0)\n",
    "            except KeyError:\n",
    "                w=g[node1][node0]['weight'][0]\n",
    "                b=g[node1][node0]['weight'][1]\n",
    "                value=np.sign(np.multiply(w,i)+b)\n",
    "                g.remove_node(node0 if value==-1 else node1)\n",
    "        \n",
    "        predict+=list(g.nodes)\n",
    "        \n",
    "    predict=pd.Series(predict).apply(int)\n",
    "    result.append('train accuracy: %.2f'%(\n",
    "        len(predict[predict==train['y']])/len(predict)*100)+'%')\n",
    "    \n",
    "    \n",
    "    #the same as training samples\n",
    "    predict=[]\n",
    "    for i in test['x']:\n",
    "        g=copy.deepcopy(graph)\n",
    "        \n",
    "        while len(g.nodes)>1:\n",
    "            \n",
    "            node0=list(g.nodes)[0]\n",
    "            node1=list(g.nodes)[1]\n",
    "            \n",
    "            try:\n",
    "                w=g[node0][node1]['weight'][0]\n",
    "                b=g[node0][node1]['weight'][1]\n",
    "                value=np.sign(np.multiply(w,i)+b)\n",
    "                g.remove_node(node1 if value==-1 else node0)\n",
    "            except KeyError:\n",
    "                w=g[node1][node0]['weight'][0]\n",
    "                b=g[node1][node0]['weight'][1]\n",
    "                value=np.sign(np.multiply(w,i)+b)\n",
    "                g.remove_node(node0 if value==-1 else node1)\n",
    "        \n",
    "        predict+=list(g.nodes)\n",
    "        \n",
    "    predict=pd.Series(predict).apply(int)\n",
    "    result.append('test accuracy: %.2f'%(\n",
    "        len(predict[predict==test['y']])/len(predict)*100)+'%')\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#using official sklearn package with the same parameters\n",
    "def skl_multiclass_svm(x_train,x_test,y_train,y_test,**kwargs):\n",
    "    \n",
    "    m=SVC(**kwargs).fit(np.array(x_train).reshape(-1, 1), \\\n",
    "                        np.array(y_train).ravel())\n",
    "    \n",
    "    train=m.score(np.array(x_train).reshape(-1, 1), \\\n",
    "                  np.array(y_train).ravel())*100\n",
    "    test=m.score(np.array(x_test).reshape(-1, 1), \\\n",
    "                 np.array(y_test).ravel())*100\n",
    "    \n",
    "    print('\\ntrain accuracy: %s'%(train)+'%')\n",
    "    print('\\ntest accuracy: %s'%(test)+'%')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ETL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "df=pd.read_csv('iris.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "df['y']=np.select([df['type']=='Iris-setosa', \\\n",
    "                   df['type']=='Iris-versicolor', \\\n",
    "                   df['type']=='Iris-virginica'],[1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for simplicity, let us reduce the dimension of x to 1\n",
    "#reference to pca\n",
    "# https://github.com/je-suis-tm/machine-learning/blob/master/principal%20component%20analysis.ipynb\n",
    "high_dims=pd.concat([df[i] for i in df.columns if 'length' in i or 'width' in i],axis=1)\n",
    "x=PCA(n_components=1).fit_transform(high_dims)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "x=pd.Series([x[i].item() for i in range(len(x))])\n",
    "y=df['y']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#train test split\n",
    "x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#crucial!!!!\n",
    "#or we would get errors in the next step\n",
    "x_test.reset_index(inplace=True,drop=True)\n",
    "y_test.reset_index(inplace=True,drop=True)\n",
    "x_train.reset_index(inplace=True,drop=True)\n",
    "y_train.reset_index(inplace=True,drop=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "train=pd.DataFrame({'x':x_train,'y':y_train})\n",
    "test=pd.DataFrame({'x':x_test,'y':y_test})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -9.6089e+01 -2.2204e+02  1e+02  2e-15  2e+00\n",
      " 1: -2.0969e+02 -2.1293e+02  3e+00  2e-14  1e+00\n",
      " 2: -1.3831e+04 -1.3834e+04  2e+00  2e-13  1e+00\n",
      " 3: -8.3446e+07 -8.3446e+07  1e+02  7e-09  1e+00\n",
      " 4: -5.0973e+10 -5.0973e+10  8e+04  2e-06  1e+00\n",
      "Terminated (singular KKT matrix).\n",
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -1.7104e+01 -3.4514e+01  4e+02  2e+01  2e+00\n",
      " 1: -2.0842e+01 -1.6714e+01  2e+02  8e+00  7e-01\n",
      " 2: -2.0117e+01 -1.0351e+01  1e+02  4e+00  4e-01\n",
      " 3: -2.2540e+00 -1.9307e+00  8e+00  3e-01  3e-02\n",
      " 4: -6.3726e-01 -1.3288e+00  7e-01  9e-16  2e-15\n",
      " 5: -1.1219e+00 -1.2159e+00  9e-02  3e-16  2e-15\n",
      " 6: -1.1852e+00 -1.1959e+00  1e-02  5e-16  2e-15\n",
      " 7: -1.1955e+00 -1.1956e+00  2e-04  2e-16  2e-15\n",
      " 8: -1.1956e+00 -1.1956e+00  2e-06  1e-15  2e-15\n",
      " 9: -1.1956e+00 -1.1956e+00  2e-08  8e-16  2e-15\n",
      "Optimal solution found.\n",
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -4.5089e+01 -1.0384e+02  3e+02  1e+01  2e+00\n",
      " 1: -9.9358e+01 -1.6258e+02  3e+02  1e+01  2e+00\n",
      " 2: -4.6021e+02 -6.7784e+02  3e+02  9e+00  1e+00\n",
      " 3: -1.7190e+03 -1.9767e+03  3e+02  7e+00  1e+00\n",
      " 4: -5.0004e+03 -5.5654e+03  6e+02  7e+00  1e+00\n",
      " 5: -9.9879e+03 -1.1002e+04  1e+03  7e+00  1e+00\n",
      " 6: -4.4054e+04 -4.7116e+04  3e+03  7e+00  1e+00\n",
      " 7: -1.8081e+05 -1.9084e+05  1e+04  7e+00  1e+00\n",
      " 8: -1.0598e+06 -1.1035e+06  4e+04  7e+00  1e+00\n",
      " 9: -1.4617e+07 -1.4914e+07  3e+05  7e+00  1e+00\n",
      "10: -6.4716e+08 -6.4898e+08  2e+06  6e+00  1e+00\n",
      "11: -2.0997e+11 -2.1002e+11  6e+07  6e+00  1e+00\n",
      "12: -2.1014e+11 -2.1019e+11  6e+07  6e+00  1e+00\n",
      "13: -2.1018e+11 -2.1024e+11  6e+07  6e+00  1e+00\n",
      "14: -2.3075e+11 -2.3081e+11  6e+07  6e+00  1e+00\n",
      "15: -3.9665e+11 -3.9676e+11  1e+08  6e+00  1e+00\n",
      "16: -8.6111e+11 -8.6132e+11  2e+08  6e+00  1e+00\n",
      "17: -2.1401e+12 -2.1406e+12  4e+08  6e+00  1e+00\n",
      "Terminated (singular KKT matrix).\n"
     ]
    }
   ],
   "source": [
    "ovr=get_accuracy_ovr(train,test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -6.1869e+00 -1.2269e+01  2e+02  1e+01  2e+00\n",
      " 1: -7.9032e+00 -5.8295e+00  6e+01  4e+00  5e-01\n",
      " 2: -5.5158e-01 -2.0978e+00  1e+01  4e-01  6e-02\n",
      " 3: -4.5189e-01 -1.3564e+00  9e-01  4e-16  8e-16\n",
      " 4: -1.0793e+00 -1.2008e+00  1e-01  2e-16  1e-15\n",
      " 5: -1.1741e+00 -1.1977e+00  2e-02  7e-16  1e-15\n",
      " 6: -1.1954e+00 -1.1957e+00  2e-04  4e-16  1e-15\n",
      " 7: -1.1956e+00 -1.1956e+00  2e-06  5e-16  1e-15\n",
      " 8: -1.1956e+00 -1.1956e+00  2e-08  1e-15  1e-15\n",
      "Optimal solution found.\n",
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -2.7304e+01 -7.4656e+01  3e+02  1e+01  3e+00\n",
      " 1: -8.4162e+01 -1.7339e+02  3e+02  1e+01  2e+00\n",
      " 2: -5.3939e+02 -6.7259e+02  1e+02  7e+00  1e+00\n",
      " 3: -1.3672e+03 -1.6072e+03  2e+02  6e+00  1e+00\n",
      " 4: -2.2173e+03 -2.5712e+03  4e+02  6e+00  1e+00\n",
      " 5: -4.1833e+03 -4.7694e+03  6e+02  6e+00  1e+00\n",
      " 6: -4.3857e+03 -4.9965e+03  6e+02  6e+00  1e+00\n",
      " 7: -2.3723e+04 -2.5237e+04  2e+03  6e+00  1e+00\n",
      " 8: -2.6862e+05 -2.7513e+05  7e+03  6e+00  1e+00\n",
      " 9: -1.0079e+07 -1.0113e+07  3e+04  6e+00  1e+00\n",
      "10: -2.9628e+09 -2.9631e+09  4e+05  6e+00  1e+00\n",
      "11: -4.1995e+11 -4.2000e+11  5e+07  6e+00  1e+00\n",
      "12: -8.5930e+11 -8.5939e+11  1e+08  6e+00  1e+00\n",
      "13: -1.2885e+12 -1.2886e+12  1e+08  6e+00  1e+00\n",
      "Terminated (singular KKT matrix).\n",
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -2.8064e+00 -4.9847e+00  2e+02  1e+01  2e+00\n",
      " 1: -1.6052e+00 -9.7543e-01  2e+01  1e+00  2e-01\n",
      " 2: -1.4529e-03 -6.4303e-01  6e-01  8e-16  2e-15\n",
      " 3: -1.8891e-01 -2.7546e-01  9e-02  8e-17  6e-16\n",
      " 4: -2.2080e-01 -2.9386e-01  7e-02  4e-17  5e-16\n",
      " 5: -2.6577e-01 -2.7043e-01  5e-03  1e-16  5e-16\n",
      " 6: -2.7006e-01 -2.7013e-01  7e-05  6e-17  7e-16\n",
      " 7: -2.7012e-01 -2.7012e-01  7e-07  1e-16  6e-16\n",
      " 8: -2.7012e-01 -2.7012e-01  7e-09  6e-17  4e-16\n",
      "Optimal solution found.\n"
     ]
    }
   ],
   "source": [
    "ovo=get_accuracy_ovo(train,test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -6.1869e+00 -1.2269e+01  2e+02  1e+01  2e+00\n",
      " 1: -7.9032e+00 -5.8295e+00  6e+01  4e+00  5e-01\n",
      " 2: -5.5158e-01 -2.0978e+00  1e+01  4e-01  6e-02\n",
      " 3: -4.5189e-01 -1.3564e+00  9e-01  4e-16  8e-16\n",
      " 4: -1.0793e+00 -1.2008e+00  1e-01  2e-16  1e-15\n",
      " 5: -1.1741e+00 -1.1977e+00  2e-02  7e-16  1e-15\n",
      " 6: -1.1954e+00 -1.1957e+00  2e-04  4e-16  1e-15\n",
      " 7: -1.1956e+00 -1.1956e+00  2e-06  5e-16  1e-15\n",
      " 8: -1.1956e+00 -1.1956e+00  2e-08  1e-15  1e-15\n",
      "Optimal solution found.\n",
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -2.7304e+01 -7.4656e+01  3e+02  1e+01  3e+00\n",
      " 1: -8.4162e+01 -1.7339e+02  3e+02  1e+01  2e+00\n",
      " 2: -5.3939e+02 -6.7259e+02  1e+02  7e+00  1e+00\n",
      " 3: -1.3672e+03 -1.6072e+03  2e+02  6e+00  1e+00\n",
      " 4: -2.2173e+03 -2.5712e+03  4e+02  6e+00  1e+00\n",
      " 5: -4.1833e+03 -4.7694e+03  6e+02  6e+00  1e+00\n",
      " 6: -4.3857e+03 -4.9965e+03  6e+02  6e+00  1e+00\n",
      " 7: -2.3723e+04 -2.5237e+04  2e+03  6e+00  1e+00\n",
      " 8: -2.6862e+05 -2.7513e+05  7e+03  6e+00  1e+00\n",
      " 9: -1.0079e+07 -1.0113e+07  3e+04  6e+00  1e+00\n",
      "10: -2.9628e+09 -2.9631e+09  4e+05  6e+00  1e+00\n",
      "11: -4.1995e+11 -4.2000e+11  5e+07  6e+00  1e+00\n",
      "12: -8.5930e+11 -8.5939e+11  1e+08  6e+00  1e+00\n",
      "13: -1.2885e+12 -1.2886e+12  1e+08  6e+00  1e+00\n",
      "Terminated (singular KKT matrix).\n",
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -2.8064e+00 -4.9847e+00  2e+02  1e+01  2e+00\n",
      " 1: -1.6052e+00 -9.7543e-01  2e+01  1e+00  2e-01\n",
      " 2: -1.4529e-03 -6.4303e-01  6e-01  8e-16  2e-15\n",
      " 3: -1.8891e-01 -2.7546e-01  9e-02  8e-17  6e-16\n",
      " 4: -2.2080e-01 -2.9386e-01  7e-02  4e-17  5e-16\n",
      " 5: -2.6577e-01 -2.7043e-01  5e-03  1e-16  5e-16\n",
      " 6: -2.7006e-01 -2.7013e-01  7e-05  6e-17  7e-16\n",
      " 7: -2.7012e-01 -2.7012e-01  7e-07  1e-16  6e-16\n",
      " 8: -2.7012e-01 -2.7012e-01  7e-09  6e-17  4e-16\n",
      "Optimal solution found.\n"
     ]
    }
   ],
   "source": [
    "dag=get_accuracy_dag(train,test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one vs rest self implementation\n",
      "\n",
      " train accuracy: 89.52%\n",
      "\n",
      " test accuracy: 97.78%\n"
     ]
    }
   ],
   "source": [
    "print('one vs rest self implementation')\n",
    "for i in ovr:\n",
    "    print('\\n',i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one vs one self implementation\n",
      "\n",
      " train accuracy: 89.52%\n",
      "\n",
      " test accuracy: 97.78%\n"
     ]
    }
   ],
   "source": [
    "#normally ovo should work better than ovr \n",
    "#as time complexity of ovo is higher\n",
    "#n*(n-1)/2>n\n",
    "print('one vs one self implementation')\n",
    "for i in ovo:\n",
    "    print('\\n',i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dag self implementation\n",
      "\n",
      " train accuracy: 89.52%\n",
      "\n",
      " test accuracy: 97.78%\n"
     ]
    }
   ],
   "source": [
    "print('dag self implementation')\n",
    "for i in dag:\n",
    "    print('\\n',i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one vs rest sklearn\n",
      "\n",
      "train accuracy: 92.38095238095238%\n",
      "\n",
      "test accuracy: 88.88888888888889%\n"
     ]
    }
   ],
   "source": [
    "print('one vs rest sklearn')\n",
    "skl_multiclass_svm(x_train,x_test,y_train,y_test,kernel='linear',decision_function_shape='ovr')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one vs one sklearn\n",
      "\n",
      "train accuracy: 92.38095238095238%\n",
      "\n",
      "test accuracy: 88.88888888888889%\n"
     ]
    }
   ],
   "source": [
    "print('one vs one sklearn')\n",
    "skl_multiclass_svm(x_train,x_test,y_train,y_test,kernel='linear',decision_function_shape='ovo')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}