<commit_before>{
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Support Vector Data Description\n",
      "===================================\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The problem of *data description* or one-class classification is to make a description of a training set of objects and to detect which (new) objects resemble this training set. \n",
      "\n",
      "This has been greatly used in outlier detection, i.e. the detection of uncharacteristic objects from a data set. Furthermore, another possible application of data description is in a classification problem where one of the classes is sampled very well, while the other class is severely undersampled. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here, the method proposed by <NAME> Duin in 2004. called *Support Vector Data Description* has been implemented. This method obtains a spherically shaped boundary around the complete target set. To minimize the chance of accepting outliers, the volume of this description is minimized. \n",
      "\n",
      "The error function to be minimized is defined as:\n",
      "\n",
      "$$F(R, \\mathbf{a}) = R^2$$\n",
      "\n",
      "with the constraint:\n",
      "\n",
      "$$\\|\\Phi(\\mathbf{x}_i)-\\mathbf{a}\\|^2 \\le R^2, \\hspace{3mm}\\forall i,$$\n",
      "\n",
      "where $\\Phi$ defines an implicit mapping of the data into an another (possibly highdimensional) feature space.\n",
      "\n",
      "To allow the possibility of outliers in the training set, the distance from $\\Phi(\\mathbf{x}_i)$ to the center $\\mathbf{a}$ should not be strictly smaller than $R^2$, but larger distances should be penalized. Therefore, the slack variables $\\xi_i \\ge 0$ are introduced, so the minimization problem becomes:\n",
      "\n",
      "$$F(R, \\mathbf{a}) = R^2 + C\\sum_i{\\xi_i}$$\n",
      "with the constraint which ensures that almost all objectives are within the sphere:\n",
      "\n",
      "$$\\|\\Phi(\\mathbf{x}_i)-\\mathbf{a}\\|^2 \\le R^2 + \\xi_i, \\hspace{3mm} \\xi_i \\ge 0 \\hspace{3mm} \\forall i.$$\n",
      "\n",
      "\n",
      "This optimization problem can be solved using the Lagrange multipliers, so the following expression is obtained:\n",
      "\n",
      "<!--$$L(R,\\mathbf{a}, \\alpha_i, \\gamma_i, \\xi_i) = R^2 + C\\sum_i{\\xi_i} - \\sum_i{\\alpha_i(R^2 + \\xi_i - ({\\|\\mathbf{x}_i\\|}^2 - 2\\mathbf{a}\\mathbf{x}_i + {\\|\\mathbf{a}\\|}^2))} - \\sum_i{\\gamma_i\\xi_i},$$\n",
      "\n",
      "where $L$ should be minimized with respect to $R, \\mathbf{a}, \\xi_i$ and maximized with respect to the Lagrange multipliers $\\alpha_i \\ge 0$ and $\\gamma_i \\ge 0$. -->\n",
      "\n",
      "<!--After setting the partial derivatives to zero and resubstituting the obtained equations into $L$,--> \n",
      "\n",
      "$$L = \\sum_i{\\alpha_i(\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_i))} -  \\sum_i\\sum_j{\\alpha_i \\alpha_j(\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_j))}$$\n",
      "\n",
      "subject to the constraints:\n",
      "\n",
      "$$\\sum_i{\\alpha_i} = 1,$$\n",
      "\n",
      "$$\\mathbf{a} = \\sum_i{\\alpha_i\\Phi(\\mathbf{x}_i)},$$\n",
      "\n",
      "$$0 \\le \\alpha_i \\le C.$$\n",
      "\n",
      "Only objects $\\Phi(\\mathbf{x}_i)$ with $\\alpha_i \\gt 0$ are needed in the data description and these objects are called the *support vectors* (SVs) of the description.\n",
      "\n",
      "The above used inner products $(\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_j))$ can be replaced by a *kernel* function $K(\\mathbf{x}_i, \\mathbf{x}_j) = (\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_j))$ to obtain more flexible methods, so the optimization problem above becomes:\n",
      "\n",
      "$$L = \\sum_i{\\alpha_iK(\\mathbf{x}_i, \\mathbf{x}_i)} -  \\sum_i\\sum_j{\\alpha_i \\alpha_jK(\\mathbf{x}_i, \\mathbf{x}_j)}.$$\n"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      "import numpy as np\n",
      "import matplotlib.pyplot as plt\n",
      "from tilitools.svdd_dual_qp import SvddDualQP\n",
      "from tilitools.svdd_primal_sgd import SvddPrimalSGD"
     ],
     "language": "python",
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      "# generate raw training data\n",
      "Dtrain = np.random.randn(2, 1000)\n",
      "Dtrain /= np.max(np.abs(Dtrain))"
     ],
     "language": "python",
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [
      {
       "ename": "NameError",
       "evalue": "name 'nu' is not defined",
       "output_type": "pyerr",
       "traceback": [
        "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
        "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
        "\u001b[0;32m<ipython-input-4-faccfa410c56>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# train dual svdd\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0msvdd\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mSvddDualQP\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'linear'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0.1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mnu\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0msvdd\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mDtrain\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;31m# train primal svdd\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
        "\u001b[0;31mNameError\u001b[0m: name 'nu' is not defined"
       ]
      }
     ],
     "input": [
      "# train dual svdd\n",
      "svdd = SvddDualQP('linear', 0.1, nu)\n",
      "svdd.fit(Dtrain)\n",
      "\n",
      "# train primal svdd\n",
      "psvdd = SvddPrimalSGD(nu)\n",
      "psvdd.fit(Dtrain, max_iter=1000, prec=1e-4)\n",
      "\n",
      "# print solutions\n",
      "print('\\n  dual-svdd: obj={0}  T={1}.'.format(svdd.pobj, svdd.radius2))\n",
      "print('primal-svdd: obj={0}  T={1}.\\n'.format(psvdd.pobj, psvdd.radius2))"
     ],
     "language": "python",
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      "# generate test data grid\n",
      "delta = 0.1\n",
      "x = np.arange(-2.0-delta, 2.0+delta, delta)\n",
      "y = np.arange(-2.0-delta, 2.0+delta, delta)\n",
      "X, Y = np.meshgrid(x, y)\n",
      "(sx, sy) = X.shape\n",
      "Xf = np.reshape(X,(1, sx*sy))\n",
      "Yf = np.reshape(Y,(1, sx*sy))\n",
      "Dtest = np.append(Xf, Yf, axis=0)\n",
      "if Dtrain.shape[0] > 2:\n",
      "    Dtest = np.append(Dtest, np.random.randn(Dtrain.shape[0]-2, sx*sy), axis=0)\n",
      "print(Dtest.shape)\n",
      "\n",
      "res = svdd.predict(Dtest)\n",
      "pres = psvdd.predict(Dtest)\n",
      "\n",
      "# nice visualization\n",
      "plt.figure(1)\n",
      "plt.subplot(1, 2, 1)\n",
      "plt.title('Dual QP SVDD')\n",
      "Z = np.reshape(res,(sx, sy))\n",
      "plt.contourf(X, Y, Z)\n",
      "plt.contour(X, Y, Z, [0.0], linewidths=3.0, colors='k')\n",
      "plt.scatter(Dtrain[0, svdd.get_support_inds()], Dtrain[1, svdd.get_support_inds()], 40, c='k')\n",
      "plt.scatter(Dtrain[0, :], Dtrain[1, :],10)\n",
      "plt.xlim((-2., 2.))\n",
      "plt.ylim((-2., 2.))\n",
      "plt.yticks(range(-2, 2), [])\n",
      "plt.xticks(range(-2, 2), [])\n",
      "\n",
      "plt.subplot(1, 2, 2)\n",
      "plt.title('Primal Subgradient SVDD')\n",
      "Z = np.reshape(pres,(sx, sy))\n",
      "plt.contourf(X, Y, Z)\n",
      "plt.contour(X, Y, Z, [0.0], linewidths=3.0, colors='k')\n",
      "plt.scatter(Dtrain[0, :], Dtrain[1, :], 10)\n",
      "plt.xlim((-2., 2.))\n",
      "plt.ylim((-2., 2.))\n",
      "plt.yticks(range(-2, 2), [])\n",
      "plt.xticks(range(-2, 2), [])\n",
      "\n",
      "plt.show()"
     ],
     "language": "python"
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},<commit_msg>@feat new svdd minimal example notebook<commit_after>{
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Support Vector Data Description\n",
      "===================================\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The problem of *data description* or one-class classification is to make a description of a training set of objects and to detect which (new) objects resemble this training set. \n",
      "\n",
      "This has been greatly used in outlier detection, i.e. the detection of uncharacteristic objects from a data set. Furthermore, another possible application of data description is in a classification problem where one of the classes is sampled very well, while the other class is severely undersampled. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here, the method proposed by Tax and Duin in 2004. called *Support Vector Data Description* has been implemented. This method obtains a spherically shaped boundary around the complete target set. To minimize the chance of accepting outliers, the volume of this description is minimized. \n",
      "\n",
      "The error function to be minimized is defined as:\n",
      "\n",
      "$$F(R, \\mathbf{a}) = R^2$$\n",
      "\n",
      "with the constraint:\n",
      "\n",
      "$$\\|\\Phi(\\mathbf{x}_i)-\\mathbf{a}\\|^2 \\le R^2, \\hspace{3mm}\\forall i,$$\n",
      "\n",
      "where $\\Phi$ defines an implicit mapping of the data into an another (possibly highdimensional) feature space.\n",
      "\n",
      "To allow the possibility of outliers in the training set, the distance from $\\Phi(\\mathbf{x}_i)$ to the center $\\mathbf{a}$ should not be strictly smaller than $R^2$, but larger distances should be penalized. Therefore, the slack variables $\\xi_i \\ge 0$ are introduced, so the minimization problem becomes:\n",
      "\n",
      "$$F(R, \\mathbf{a}) = R^2 + C\\sum_i{\\xi_i}$$\n",
      "with the constraint which ensures that almost all objectives are within the sphere:\n",
      "\n",
      "$$\\|\\Phi(\\mathbf{x}_i)-\\mathbf{a}\\|^2 \\le R^2 + \\xi_i, \\hspace{3mm} \\xi_i \\ge 0 \\hspace{3mm} \\forall i.$$\n",
      "\n",
      "\n",
      "This optimization problem can be solved using the Lagrange multipliers, so the following expression is obtained:\n",
      "\n",
      "<!--$$L(R,\\mathbf{a}, \\alpha_i, \\gamma_i, \\xi_i) = R^2 + C\\sum_i{\\xi_i} - \\sum_i{\\alpha_i(R^2 + \\xi_i - ({\\|\\mathbf{x}_i\\|}^2 - 2\\mathbf{a}\\mathbf{x}_i + {\\|\\mathbf{a}\\|}^2))} - \\sum_i{\\gamma_i\\xi_i},$$\n",
      "\n",
      "where $L$ should be minimized with respect to $R, \\mathbf{a}, \\xi_i$ and maximized with respect to the Lagrange multipliers $\\alpha_i \\ge 0$ and $\\gamma_i \\ge 0$. -->\n",
      "\n",
      "<!--After setting the partial derivatives to zero and resubstituting the obtained equations into $L$,--> \n",
      "\n",
      "$$L = \\sum_i{\\alpha_i(\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_i))} -  \\sum_i\\sum_j{\\alpha_i \\alpha_j(\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_j))}$$\n",
      "\n",
      "subject to the constraints:\n",
      "\n",
      "$$\\sum_i{\\alpha_i} = 1,$$\n",
      "\n",
      "$$\\mathbf{a} = \\sum_i{\\alpha_i\\Phi(\\mathbf{x}_i)},$$\n",
      "\n",
      "$$0 \\le \\alpha_i \\le C.$$\n",
      "\n",
      "Only objects $\\Phi(\\mathbf{x}_i)$ with $\\alpha_i \\gt 0$ are needed in the data description and these objects are called the *support vectors* (SVs) of the description.\n",
      "\n",
      "The above used inner products $(\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_j))$ can be replaced by a *kernel* function $K(\\mathbf{x}_i, \\mathbf{x}_j) = (\\Phi(\\mathbf{x}_i)\\cdot\\Phi(\\mathbf{x}_j))$ to obtain more flexible methods, so the optimization problem above becomes:\n",
      "\n",
      "$$L = \\sum_i{\\alpha_iK(\\mathbf{x}_i, \\mathbf{x}_i)} -  \\sum_i\\sum_j{\\alpha_i \\alpha_jK(\\mathbf{x}_i, \\mathbf{x}_j)}.$$\n"
     ]
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      "%matplotlib inline\n",
      "\n",
      "import numpy as np\n",
      "import matplotlib.pyplot as plt\n",
      "\n",
      "from tilitools.svdd_dual_qp import SvddDualQP\n",
      "from tilitools.svdd_primal_sgd import SvddPrimalSGD"
     ],
     "language": "python",
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      "# generate raw training data\n",
      "Dtrain = np.random.randn(2, 1000)\n",
      "Dtrain /= np.max(np.abs(Dtrain))"
     ],
     "language": "python",
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Creating new dual QP SVDD (linear) with nu=0.15.\nCalculating linear kernel with size 1000x1000.\n     pcost       dcost       gap    pres   dres\n 0: -1.3158e+01 -1.0320e+01  5e+03  7e+01  3e-15\n 1: -3.3426e-01 -1.0255e+01  5e+01  7e-01  3e-15\n 2: -2.0973e-01 -5.9640e+00  6e+00  1e-15  2e-15\n 3: -2.5500e-01 -1.4003e+00  1e+00  9e-16  2e-15\n 4: -3.4401e-01 -7.9795e-01  5e-01  1e-16  1e-15\n 5: -4.1149e-01 -5.3820e-01  1e-01  7e-16  9e-16\n 6: -4.3320e-01 -4.8796e-01  5e-02  3e-16  8e-16\n 7: -4.4098e-01 -4.7008e-01  3e-02  8e-16  7e-16\n 8: -4.4582e-01 -4.5990e-01  1e-02  4e-16  7e-16\n 9: -4.4804e-01 -4.5552e-01  7e-03  2e-16  7e-16\n10: -4.4993e-01 -4.5212e-01  2e-03  3e-16  8e-16\n11: -4.5074e-01 -4.5099e-01  3e-04  9e-16  9e-16\n12: -4.5084e-01 -4.5086e-01  1e-05  4e-17  9e-16\n13: -4.5085e-01 -4.5085e-01  1e-07  2e-15  9e-16\nOptimal solution found.\nCalculating linear kernel with size 151x151.\nCalculating diagonal of a linear kernel with size 151x151.\nCreating new primal SVDD with nu=0.15.\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stderr",
       "text": [
        "/Users/nicococo/anaconda/lib/python2.7/site-packages/numba/dataflow.py:297: RuntimeWarning: Python2 style print partially supported.  Please use Python3 style print.\n  \"Python3 style print.\", RuntimeWarning)\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Iter=17: obj=0.45103851623  T=0.286316083519\n\n\n  dual-svdd: obj=0.450850643814  T=0.279488059588.\nprimal-svdd: obj=0.45103851623  T=0.286316083519.\n\n"
       ]
      }
     ],
     "input": [
      "nu = 0.15  # outlier fraction\n",
      "\n",
      "# train dual svdd\n",
      "svdd = SvddDualQP('linear', 0.1, nu)\n",
      "svdd.fit(Dtrain)\n",
      "\n",
      "# train primal svdd\n",
      "psvdd = SvddPrimalSGD(nu)\n",
      "psvdd.fit(Dtrain, max_iter=1000, prec=1e-4)\n",
      "\n",
      "# print solutions\n",
      "print('\\n  dual-svdd: obj={0}  T={1}.'.format(svdd.pobj, svdd.radius2))\n",
      "print('primal-svdd: obj={0}  T={1}.\\n'.format(psvdd.pobj, psvdd.radius2))"
     ],
     "language": "python",
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      "# generate test data grid\n",
      "delta = 0.1\n",
      "x = np.arange(-2.0-delta, 2.0+delta, delta)\n",
      "y = np.arange(-2.0-delta, 2.0+delta, delta)\n",
      "X, Y = np.meshgrid(x, y)\n",
      "(sx, sy) = X.shape\n",
      "Xf = np.reshape(X,(1, sx*sy))\n",
      "Yf = np.reshape(Y,(1, sx*sy))\n",
      "Dtest = np.append(Xf, Yf, axis=0)\n",
      "if Dtrain.shape[0] > 2:\n",
      "    Dtest = np.append(Dtest, np.random.randn(Dtrain.shape[0]-2, sx*sy), axis=0)\n",
      "print(Dtest.shape)\n",
      "\n",
      "res = svdd.predict(Dtest)\n",
      "pres = psvdd.predict(Dtest)\n",
      "\n",
      "# nice visualization\n",
      "plt.figure(1)\n",
      "plt.subplot(1, 2, 1)\n",
      "plt.title('Dual QP SVDD')\n",
      "Z = np.reshape(res,(sx, sy))\n",
      "plt.contourf(X, Y, Z)\n",
      "plt.contour(X, Y, Z, [0.0], linewidths=3.0, colors='k')\n",
      "plt.scatter(Dtrain[0, svdd.get_support_inds()], Dtrain[1, svdd.get_support_inds()], 40, c='k')\n",
      "plt.scatter(Dtrain[0, :], Dtrain[1, :],10)\n",
      "plt.xlim((-2., 2.))\n",
      "plt.ylim((-2., 2.))\n",
      "plt.yticks(range(-2, 2), [])\n",
      "plt.xticks(range(-2, 2), [])\n",
      "\n",
      "plt.subplot(1, 2, 2)\n",
      "plt.title('Primal Subgradient SVDD')\n",
      "Z = np.reshape(pres,(sx, sy))\n",
      "plt.contourf(X, Y, Z)\n",
      "plt.contour(X, Y, Z, [0.0], linewidths=3.0, colors='k')\n",
      "plt.scatter(Dtrain[0, :], Dtrain[1, :], 10)\n",
      "plt.xlim((-2., 2.))\n",
      "plt.ylim((-2., 2.))\n",
      "plt.yticks(range(-2, 2), [])\n",
      "plt.xticks(range(-2, 2), [])\n",
      "\n",
      "plt.show()"
     ],
     "language": "python",
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
     "outputs": [],
     "input": [
      ""
     ],
     "language": "python"
    },
    {
     "cell_type": "code",
     "execution_count": null,
     "metadata": {},
{'fraction_non_alphanumeric': 0.22068811936309987, 'fraction_numerical': 0.058902126711947445, 'mean_word_length': 2.3860508953817154, 'pattern_counts': {'":': 102, '<': 10, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1769500', 'n_tokens_mistral': 7702, 'n_tokens_neox': 7064, 'n_words': 1504}