Chapter 13 - Prototype Methods and Nearest Neighbors.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 13 - Prototype Methods and Nearest Neighbors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.1 - Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Prototype methods are simple and essentially model-free methods for classification and pattern recognition. \n",
    "* Because they are highly unstructured, they typically are not useful for understanding the nature of the relationship between the features and class outcome. \n",
    "* However, as black box prediction engines, they can be very effective, and are often among the best performers in real data problems. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.2 - Prototype Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Each prototype has an associated class label, and classification of a query point x is made to the class of the closest prototype. \n",
    "* “Closest” is usually defined by Euclidean distance in the feature space, after each feature has been standardized to have overall mean 0 and variance 1 in the training sample.\n",
    "* The main challenge is to figure out how many prototypes to use and where to put them. \n",
    "* Methods differ according to the number and way in which prototypes are selected.\n",
    "\n",
    "**K-Means**\n",
    "* K-means clustering is a method for finding clusters and cluster centers in a set of unlabeled data. One chooses the desired number of cluster centers, say R, and the K-means procedure iteratively moves the centers to minimize the total within cluster variance.\n",
    "\n",
    "Algorithm\n",
    "* For each center we identify the subset of training points (its cluster) that is closer to it than any other center.\n",
    "* The means of each feature for the data points in each cluster are computed, and this mean vector becomes the new center for that cluster.\n",
    "* Apply K-means clustering to the training data in each class separately, using R prototypes per class.\n",
    "* Assign a class label to each of the K × R prototypes\n",
    "* Classify a new feature x to the class of the closest prototype.\n",
    "\n",
    "**Learning Vector Quantization (LVQ)**\n",
    "* Similar to K-Means but the other classes get a say in the positioning of a class prototype.\n",
    "* The idea is that the training points attract prototypes of the correct class, and repel other prototypes. When the iterations settle down, prototypes should be close to the training points in their class.\n",
    "\n",
    "**Gaussian Mixtures**\n",
    "* Gaussian mixture models can be thought of as a soft prototype method.\n",
    "* Each cluster is described in terms of a Gaussian density, which has a centroid (as in K-means), and a covariance matrix. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.3 - k-Nearest-Neighbor Classifiers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* These classifiers are memory-based, and require no model to be fit. \n",
    "* Given a query point $x_0$, we find the k training points $x(r),r = 1,...,k$ closest in distance to $x_0$, and then classify using majority vote among the k neighbors.\n",
    "* Typically we first standardize each of the features to have mean zero and variance 1, since it is possible that they are measured in different units. \n",
    "* KNN is often successful where each class has many possible prototypes, and the decision boundary is very irregular. (e.g. classifying handwriting digits).\n",
    "* Often we want our training data to be \"invariant\". For example, in digit classification we have data that is often rotated slightly due to handwriting differences.  \n",
    "* A simple way to achieve this invariance would be to add into the training set a number of rotated versions of each training image. This idea is called “hints” and works well when the space of invariances is small.\n",
    "* Other possible invariances are translation (two directions), scaling (two directions), sheer, and character thickness.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              precision    recall  f1-score   support\n",
      "\n",
      "      setosa       1.00      1.00      1.00        12\n",
      "  versicolor       0.87      1.00      0.93        13\n",
      "   virginica       1.00      0.85      0.92        13\n",
      "\n",
      "    accuracy                           0.95        38\n",
      "   macro avg       0.96      0.95      0.95        38\n",
      "weighted avg       0.95      0.95      0.95        38\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "from sklearn import datasets\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import classification_report\n",
    "\n",
    "clf = KNeighborsClassifier(n_neighbors=3)\n",
    "iris = datasets.load_iris()\n",
    "X, y = iris.data, iris.target\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y)\n",
    "clf.fit(X, y)\n",
    "\n",
    "print(\n",
    "    classification_report(y_test, clf.predict(X_test), target_names=iris.target_names)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.4 - Adaptive Nearest-Neighbor Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* When nearest-neighbor classification is carried out in a high-dimensional feature space, the nearest neighbors of a point can be very far away, causing bias and degrading the performance of the rule.\n",
    "* This calls for adapting the metric used in nearest-neighbor classification, so that the resulting neighborhoods stretch out in directions for which the class probabilities don’t change much.\n",
    "* At each query point, a neighborhood of points is formed, and the class distribution among the points is used to decide how to deform the neighborhood -- that is, to adapt the metric. The adapted metric is then used in a nearest-neighbor rule at the query point. Thus at each query point a potentially different metric is used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 13.5 - Computational Considerations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* One drawback of nearest-neighbor rules in general is the computational load, both in finding the neighbors and storing the entire training set. \n",
    "* With $N$ observations and $p$ predictors, nearest-neighbor classification requires $Np$ operations to find the neighbors per query point."
   ]
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}