Chapter3-KNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第3章 k近邻法描述\n",
    "K近邻算法本身是个很简单的算法，某些时候甚至不能称之为机器学习算法，因为它没有“学习”的过程，仅仅通过判定和要预测的$x$相近的点都呈现的表征来确定$x$的对应类标$y$就可以了，但是《统计学习方法》这本书使用了KD-tree的方法来寻找最近邻，其主要目的是在数据量比较大的时候能够优化查找效率，从原理来讲，树结构的查找的时间复杂度$O\\left( logN \\right)$比线性查找的复杂度$O\\left( N \\right)$低，因此效率比较高。\n",
    "## 3.1k近邻算法(KNN)\n",
    ">输入:训练数据集\n",
    "    $$ T = \\{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \\}$$\n",
    "    其中, $x_i \\in \\mathcal{X} \\subseteq R^n$为实例的特征向量,$y_i \\in \\mathcal{Y} =\\{ c_1,c_2,...,c_K\\}$为实例的类别, $i = 1,2,...N$; 实例特征向量$x$.  \n",
    "输出:实例$x$所属类别$y$\n",
    "* 根据距离度量,在训练集$T$中找到与$x$最近邻的$k$个点,涵盖这$k$个点的邻域记作$N_k(x)$\n",
    "* 在$N_k(x)$中根据分类决策规则(如多数表决)决定$x$的类别$y$\n",
    "$$ y = \\arg\\underset{c_j}{\\max} \\sum_{x_i \\in N_k(x)} I(y_i = c_j),i=1,2,...,N;j=1,2,...,k$$\n",
    "上式中,$I$为指示函数,当$y_i = c_j$的时候,$I$为1,否则置0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## 3.2距离度量方法以及定义\n",
    ">* $L_p$ distance: $L_p$距离\n",
    "$$L_p(x_i,x_j) = (\\sum^n_{l=1} {\\left| x^{(l)}_i - x^{(l)}_j \\right|}^p)^\\frac{1}{p}$$\n",
    "* Euclidean distance: 欧式距离\n",
    "$$L_2(x_i,x_j) = (\\sum^n_{l=1} {\\left| x^{(l)}_i - x^{(l)}_j \\right|}^2)^\\frac{1}{2}$$\n",
    "* Manhattan distance: 曼哈顿距离\n",
    "$$L_1(x_i,x_j) = \\sum^n_{l=1} {\\left| x^{(l)}_i - x^{(l)}_j \\right|}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calDis(x_1,x_2,dis_type = None):\n",
    "    \"\"\"\n",
    "    距离度量公式,包含2种,分别记为'E','M',E为欧式距离,M是曼哈顿距离\n",
    "    x_1,x_2为两个向量S\n",
    "    \"\"\"\n",
    "    distance = 0\n",
    "    if (dis_type == None)|(dis_type == 'E'):\n",
    "        distance = math.sqrt(sum((x_1-x_2)**2))\n",
    "    elif (dis_type == 'M'):\n",
    "        distance = sum(abs(x_1-x_2))\n",
    "    else:\n",
    "        print('WARNING: 函数calDis(self,x_1,x_2,dis_type)没有dis_type='+ str(dis_type) +' 这种距离度量方法,请重新定义dis_type=E或者M')\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">测试距离计算"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "欧式距离为: 1.4142135623730951\n",
      "曼哈顿距离为: 2\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "a = np.array([1,2])\n",
    "b = np.array([2,1])\n",
    "print('欧式距离为:' ,calDis(a,b,'E'))\n",
    "print('曼哈顿距离为:' , calDis(a,b,'M'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## 3.3 常规遍历算法，并设计自己的KNN算法框架\n",
    ">这里使用遍历计算的方法直接及计算距离并找到最近的k个元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array([[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]])\n",
    "data_label = np.array([1,1,0,1,0,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">这里首先定义训练部分“train”，但是实质不是训练过程，这里用来保存模型的参数，即x，y，k，distance_type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class myKNN():\n",
    "    def train(self, x, y, k = None, dis_type = None):\n",
    "        model = []\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        if k == None:\n",
    "            self.k = 1\n",
    "        else:\n",
    "            self.k = k\n",
    "        if dis_type == None:\n",
    "            self.dis_type = 'E'\n",
    "        else:\n",
    "            self.dis_type = dis_type\n",
    "        model.append(self.x)\n",
    "        model.append(self.y)\n",
    "        model.append(self.k)\n",
    "        model.append(self.dis_type)\n",
    "        return model\n",
    "    \n",
    "    def predict(self,x,model,dis_type = None):\n",
    "        if x.ndim == 1:             # 如果是一个样本\n",
    "            x = x.reshape(1,len(x)) # 转化为1×n的张量样本\n",
    "        predicted_y = []            # 用于保存预测类别\n",
    "        for i in range(len(x)):     # 预测x的每个元素\n",
    "            distance = []           # 保存x[j]与原有数据所有样本之间的距离\n",
    "            for j in range(len(model[0])): # 计算x[j]与原有数据所有样本之间的距离\n",
    "                distance.append(calDis(model[0][j],x[i],model[3]))\n",
    "            predicted_y_distance = np.column_stack((model[1],distance)) # 合并得到（y,distance）两列数据\n",
    "            # 排序，以下步骤实现argmax的那个步骤\n",
    "            sorted_y_distance = predicted_y_distance[\n",
    "                predicted_y_distance.argsort(0)[:,1]] # 对得到的（y,distance）按照第二列排序\n",
    "            knn_data = sorted_y_distance[:model[2]]\n",
    "            nearestky_list = knn_data[:,0].tolist()\n",
    "            count = {c:nearestky_list.count(c) for c in set(nearestky_list)}\n",
    "            y = sorted(count.keys())[0]\n",
    "            predicted_y.append(y)\n",
    "        return predicted_y\n",
    "    \n",
    "    def accuracy(self,precited_y,real_y):\n",
    "        self.y = precited_y\n",
    "        self.realy = real_y\n",
    "        return 1-sum(np.sign(np.abs(self.y-self.realy)))/len(self.y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "使用曼哈顿距离得到的正确率： 1.0\n",
      "使用欧式距离得到的正确率： 1.0\n"
     ]
    }
   ],
   "source": [
    "mk = myKNN()\n",
    "\n",
    "model1 = mk.train(data,data_label,k=3,dis_type='M') # 曼哈顿距离，k=3\n",
    "predicted_y = mk.predict(data,model1)\n",
    "print('使用曼哈顿距离得到的正确率：',mk.accuracy(predicted_y,data_label))\n",
    "\n",
    "model2 = mk.train(data,data_label) # 欧式距离，k为默认值k=1\n",
    "predicted_y = mk.predict(data,model2)\n",
    "print('使用欧式距离得到的正确率：',mk.accuracy(predicted_y,data_label))"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}