{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**k-近邻**（k-Nearest Neighbor, 简称 kNN）是一种常见的监督学习算法，它是 Cover T 和 Hart P 在 1967 年提出的一种既可以用于分类，也可以用于回归的学习方法。它的工作原理非常简单：用一句古话来说就是，“近朱者赤，近墨者黑”，给定测试样本，基于某种距离度量找出训练集中与其最靠近的 k 个训练样本，这 k 个距离最近的样本就是 k-Nearest Neighbor。如果是在分类任务中，我们把这 k 个样本中出现最多的类别作为预测结果；如果是在回归任务中，我们把这 k 个样本的平均值作为预测结果。一般情况下，用 kNN 处理回归问题比较少见，我们这一节使用 kNN 解决分类问题。\n",
    "\n",
    "![](../images/knn.png)\n",
    "\n",
    "如上图所示，这是一个简单的分类任务，有两类不同的样本数据，分别用蓝色正方形和红色三角形表示，而图正中间的那个绿色的圆点则是待分类的数据。使用 kNN 来解决这个问题的基本思路是，从样本数据中找出距离绿色圆点最近的 k 个数据，然后看这 k 个数据中哪个类别出现的最多。可以看出，当 k = 3 时，有 2 个红色三角形和 1 个蓝色正方形，可以判定绿色圆点和红色三角形一类；但是当 k = 5 时，有 2 个红色三角形和 3 个蓝色正方形，可以判定绿色圆点和蓝色正方形一类。所以，在 kNN 算法中 k 值的选择很重要。\n",
    "\n",
    "在李航的《统计学习方法》中，将 **k值的选择**、**距离度量** 和 **分类决策规则** 作为 kNN 算法的三个基本要素：\n",
    "\n",
    "1. 首先是参数 k，它是一个超参数，它的取值对分类结果有着显著的影响，所以一般会通过交叉验证法，选择不同的 k 值进行计算，最后取一个分类结果最好的 k 值；\n",
    "2. 其次是距离度量的方法，最常用的是欧氏距离，除此之外，还有切比雪夫距离、马氏距离、巴氏距离等，要根据实际求解的问题来选择；\n",
    "3. 最后是分类决策规则，通常使用多数表决规则（majority voting rule），即将 k 个最近的样本中出现最多的类别作为预测结果。\n",
    "\n",
    "要注意的是，kNN 算法没有显式的训练过程，它的训练开销为零，这种学习算法又被称为 **懒惰学习**（lazy learning），相反的，那些有训练过程的算法被称为 **急切学习**（eager learning）。\n",
    "\n",
    "### kNN 优缺点\n",
    "\n",
    "* 优点\n",
    "  * 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；\n",
    "  * 可用于数值型数据和离散型数据；\n",
    "  * 训练时间复杂度为O(n)；无数据输入假定；\n",
    "  * 对异常值不敏感；\n",
    "* 缺点\n",
    "  * 计算复杂性高；空间复杂性高；\n",
    "  * 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；\n",
    "  * 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分；\n",
    "  * 最大的缺点是无法给出数据的内在含义；"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}