{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "\n# Explicit feature map approximation for RBF kernels\n\nAn example illustrating the approximation of the feature map\nof an RBF kernel.\n\n.. currentmodule:: sklearn.kernel_approximation\n\nIt shows how to use :class:`RBFSampler` and :class:`Nystroem` to\napproximate the feature map of an RBF kernel for classification with an SVM on\nthe digits dataset. Results using a linear SVM in the original space, a linear\nSVM using the approximate mappings and using a kernelized SVM are compared.\nTimings and accuracy for varying amounts of Monte Carlo samplings (in the case\nof :class:`RBFSampler`, which uses random Fourier features) and different sized\nsubsets of the training set (for :class:`Nystroem`) for the approximate mapping\nare shown.\n\nPlease note that the dataset here is not large enough to show the benefits\nof kernel approximation, as the exact SVM is still reasonably fast.\n\nSampling more dimensions clearly leads to better classification results, but\ncomes at a greater cost. This means there is a tradeoff between runtime and\naccuracy, given by the parameter n_components. Note that solving the Linear\nSVM and also the approximate kernel SVM could be greatly accelerated by using\nstochastic gradient descent via :class:`~sklearn.linear_model.SGDClassifier`.\nThis is not easily possible for the case of the kernelized SVM.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Python package and dataset imports, load dataset\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# Authors: The scikit-learn developers\n# SPDX-License-Identifier: BSD-3-Clause\n\n# Standard scientific Python imports\nfrom time import time\n\nimport matplotlib.pyplot as plt\nimport numpy as np\n\n# Import datasets, classifiers and performance metrics\nfrom sklearn import datasets, pipeline, svm\nfrom sklearn.decomposition import PCA\nfrom sklearn.kernel_approximation import Nystroem, RBFSampler\n\n# The digits dataset\ndigits = datasets.load_digits(n_class=9)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Timing and accuracy plots\nTo apply an classifier on this data, we need to flatten the image, to\nturn the data in a (samples, feature) matrix:\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "n_samples = len(digits.data)\ndata = digits.data / 16.0\ndata -= data.mean(axis=0)\n\n# We learn the digits on the first half of the digits\ndata_train, targets_train = (data[: n_samples // 2], digits.target[: n_samples // 2])\n\n\n# Now predict the value of the digit on the second half:\ndata_test, targets_test = (data[n_samples // 2 :], digits.target[n_samples // 2 :])\n# data_test = scaler.transform(data_test)\n\n# Create a classifier: a support vector classifier\nkernel_svm = svm.SVC(gamma=0.2)\nlinear_svm = svm.LinearSVC(random_state=42)\n\n# create pipeline from kernel approximation\n# and linear svm\nfeature_map_fourier = RBFSampler(gamma=0.2, random_state=1)\nfeature_map_nystroem = Nystroem(gamma=0.2, random_state=1)\nfourier_approx_svm = pipeline.Pipeline(\n    [\n        (\"feature_map\", feature_map_fourier),\n        (\"svm\", svm.LinearSVC(random_state=42)),\n    ]\n)\n\nnystroem_approx_svm = pipeline.Pipeline(\n    [\n        (\"feature_map\", feature_map_nystroem),\n        (\"svm\", svm.LinearSVC(random_state=42)),\n    ]\n)\n\n# fit and predict using linear and kernel svm:\n\nkernel_svm_time = time()\nkernel_svm.fit(data_train, targets_train)\nkernel_svm_score = kernel_svm.score(data_test, targets_test)\nkernel_svm_time = time() - kernel_svm_time\n\nlinear_svm_time = time()\nlinear_svm.fit(data_train, targets_train)\nlinear_svm_score = linear_svm.score(data_test, targets_test)\nlinear_svm_time = time() - linear_svm_time\n\nsample_sizes = 30 * np.arange(1, 10)\nfourier_scores = []\nnystroem_scores = []\nfourier_times = []\nnystroem_times = []\n\nfor D in sample_sizes:\n    fourier_approx_svm.set_params(feature_map__n_components=D)\n    nystroem_approx_svm.set_params(feature_map__n_components=D)\n    start = time()\n    nystroem_approx_svm.fit(data_train, targets_train)\n    nystroem_times.append(time() - start)\n\n    start = time()\n    fourier_approx_svm.fit(data_train, targets_train)\n    fourier_times.append(time() - start)\n\n    fourier_score = fourier_approx_svm.score(data_test, targets_test)\n    nystroem_score = nystroem_approx_svm.score(data_test, targets_test)\n    nystroem_scores.append(nystroem_score)\n    fourier_scores.append(fourier_score)\n\n# plot the results:\nplt.figure(figsize=(16, 4))\naccuracy = plt.subplot(121)\n# second y axis for timings\ntimescale = plt.subplot(122)\n\naccuracy.plot(sample_sizes, nystroem_scores, label=\"Nystroem approx. kernel\")\ntimescale.plot(sample_sizes, nystroem_times, \"--\", label=\"Nystroem approx. kernel\")\n\naccuracy.plot(sample_sizes, fourier_scores, label=\"Fourier approx. kernel\")\ntimescale.plot(sample_sizes, fourier_times, \"--\", label=\"Fourier approx. kernel\")\n\n# horizontal lines for exact rbf and linear kernels:\naccuracy.plot(\n    [sample_sizes[0], sample_sizes[-1]],\n    [linear_svm_score, linear_svm_score],\n    label=\"linear svm\",\n)\ntimescale.plot(\n    [sample_sizes[0], sample_sizes[-1]],\n    [linear_svm_time, linear_svm_time],\n    \"--\",\n    label=\"linear svm\",\n)\n\naccuracy.plot(\n    [sample_sizes[0], sample_sizes[-1]],\n    [kernel_svm_score, kernel_svm_score],\n    label=\"rbf svm\",\n)\ntimescale.plot(\n    [sample_sizes[0], sample_sizes[-1]],\n    [kernel_svm_time, kernel_svm_time],\n    \"--\",\n    label=\"rbf svm\",\n)\n\n# vertical line for dataset dimensionality = 64\naccuracy.plot([64, 64], [0.7, 1], label=\"n_features\")\n\n# legends and labels\naccuracy.set_title(\"Classification accuracy\")\ntimescale.set_title(\"Training times\")\naccuracy.set_xlim(sample_sizes[0], sample_sizes[-1])\naccuracy.set_xticks(())\naccuracy.set_ylim(np.min(fourier_scores), 1)\ntimescale.set_xlabel(\"Sampling steps = transformed feature dimension\")\naccuracy.set_ylabel(\"Classification accuracy\")\ntimescale.set_ylabel(\"Training time in seconds\")\naccuracy.legend(loc=\"best\")\ntimescale.legend(loc=\"best\")\nplt.tight_layout()\nplt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Decision Surfaces of RBF Kernel SVM and Linear SVM\nThe second plot visualized the decision surfaces of the RBF kernel SVM and\nthe linear SVM with approximate kernel maps.\nThe plot shows decision surfaces of the classifiers projected onto\nthe first two principal components of the data. This visualization should\nbe taken with a grain of salt since it is just an interesting slice through\nthe decision surface in 64 dimensions. In particular note that\na datapoint (represented as a dot) does not necessarily be classified\ninto the region it is lying in, since it will not lie on the plane\nthat the first two principal components span.\nThe usage of :class:`RBFSampler` and :class:`Nystroem` is described in detail\nin `kernel_approximation`.\n\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "# visualize the decision surface, projected down to the first\n# two principal components of the dataset\npca = PCA(n_components=8, random_state=42).fit(data_train)\n\nX = pca.transform(data_train)\n\n# Generate grid along first two principal components\nmultiples = np.arange(-2, 2, 0.1)\n# steps along first component\nfirst = multiples[:, np.newaxis] * pca.components_[0, :]\n# steps along second component\nsecond = multiples[:, np.newaxis] * pca.components_[1, :]\n# combine\ngrid = first[np.newaxis, :, :] + second[:, np.newaxis, :]\nflat_grid = grid.reshape(-1, data.shape[1])\n\n# title for the plots\ntitles = [\n    \"SVC with rbf kernel\",\n    \"SVC (linear kernel)\\n with Fourier rbf feature map\\nn_components=100\",\n    \"SVC (linear kernel)\\n with Nystroem rbf feature map\\nn_components=100\",\n]\n\nplt.figure(figsize=(18, 7.5))\nplt.rcParams.update({\"font.size\": 14})\n# predict and plot\nfor i, clf in enumerate((kernel_svm, nystroem_approx_svm, fourier_approx_svm)):\n    # Plot the decision boundary. For that, we will assign a color to each\n    # point in the mesh [x_min, x_max]x[y_min, y_max].\n    plt.subplot(1, 3, i + 1)\n    Z = clf.predict(flat_grid)\n\n    # Put the result into a color plot\n    Z = Z.reshape(grid.shape[:-1])\n    levels = np.arange(10)\n    lv_eps = 0.01  # Adjust a mapping from calculated contour levels to color.\n    plt.contourf(\n        multiples,\n        multiples,\n        Z,\n        levels=levels - lv_eps,\n        cmap=plt.cm.tab10,\n        vmin=0,\n        vmax=10,\n        alpha=0.7,\n    )\n    plt.axis(\"off\")\n\n    # Plot also the training points\n    plt.scatter(\n        X[:, 0],\n        X[:, 1],\n        c=targets_train,\n        cmap=plt.cm.tab10,\n        edgecolors=(0, 0, 0),\n        vmin=0,\n        vmax=10,\n    )\n\n    plt.title(titles[i])\nplt.tight_layout()\nplt.show()"
      ]
    }
  ],
  "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.9.21"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}