KNN学习记录1

1.KNN算法介绍 ——（物以类聚）

KNN的主要目的就是寻找未知分类的数据，离他最近的K个已知数据，然后来看它应该是属于哪一类的。

KNN主要思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。在KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。以下有一个图非常好理解KNN，也是学习KNN中一个最经典的图形。

knn.png

如图所示，我们最终的目的就是要确定图片上绿点属于哪一类（红色三角还是蓝色矩形），所以要做的就是选出距离目标点距离最近的K个点，看这K个点的大多数类型(颜色)是什么类型（颜色）。

显然的，当我们取K=3的时候，我们可以看出距离最近的三个点，分别是红色三角、红色三角、蓝色矩形，因此此时我们认为目标点（绿点）属于红色三角那一类；
同理当我们取K=5的时候，显然的我们可以认为目标点（绿点）属于蓝色矩形那一类。

1.1 算法原理：

计算距离
升序排列
取前k个最近的
加权平均 --- 近的权重大

1.2 K的选取：（核心）

k太大：导致分类模糊
k太小：受个例影响大

1.3 如何现在k：

经验
均方根误差

2. 以下介绍一个最简单的KNN算法过程

最主要的原理有：

计算目标数据与各个训练数据之间的距离；
按照距离的大小进行排序；
选取出距离最小的K个点；
确定前K个点所在类别的出现频率；
返回前K个点中出现频率最高的类别作为测试数据的预测分类

2.1 初步介绍，引入例子

import numpy as np
import pandas as pd 
import matplotlib.pyplot as plt

下面随意构造一些点，人为分为两大类，具体数据如下所示：

x_data = [[3.3, 2.9],
              [3.1, 1.],
              [1.9, 3.3],
              [3.5, 3.5],
              [2.3, 2.6],
              [7.6, 4.8],
              [5, 3.4],
              [9.8, 2.7],
              [7.8, 3.8],
              [7.6, 0.3],
              [7, 2]]
y_data= [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
# 划分数据集
x_train = np.array(x_data)
y_train = np.array(y_data)

# 看看数据的具体情况

# x_train中，标记点为0的点(0表示x1,1,表示x2)
plt.figure(dpi = 150)
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='red') 
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='cyan')
plt.savefig('class.png')
plt.show()

结果如图所示,显然有两类数据。

class.png

现在判断一个新的点(5, 2.8)是属于哪一类的，如图所示

x = np.array([5, 2.8])
plt.figure(dpi = 150)
plt.scatter(x=x_train[y_train==0,0],y = x_train[y_train==0,1],color = 'red')
plt.scatter(x =x_train[y_train ==1,0],y = x_train[y_train ==1,1],color = 'cyan')
plt.scatter(x = x[0],y = x[1],color = 'black')
plt.show()

class_belong.png

现在我们更具图形很难判断这个点是属于哪一类,所以下一步我们计算距离，在这里距离有多种距离。

2.2. 距离的计算

我们认为在空间中两个点的距离是两个实例点相似程度的反应。KNN模型的特征空间一般是 $n$ 维实数向量空间 $R^n$ ,使用的距离是欧式距离，但也可以是其他距离，如更一般的 $L_p$ 距离或Minkowshi距离

一般的我们采用欧氏距离，即最常见的：
$L_{2}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{2}\right)^{\frac{1}{2}}$
现在开始计算距离：

distance = []
for X in x_train:
    d = np.sqrt(np.sum((X-x)**2))
    distance.append(d)
print("黑点距离各个点的距离为:\n",distance)

距离.jpg

#或者为
distance = [np.sqrt(np.sum((X-x)**2)) for X in x_train]
print(distance)

下面我们来查找距离索引，利用numpy中的一个argsort函数：

sortdist = np.argsort(distance)
print(sortdist)

dist_result.png

根据结果我们可以知道，距离黑的最近的是第7个点，其次是第4个点.....

对k取1和取3分别进行投票表决

from collections import  Counter
K = [1, 3]
result = []
for k_ in K:
    top_k = [y_train[i] for i in sortdist[:k_]]
    vetos = Counter(top_k)
    a = vetos.most_common()
    result.append(a)
print(result)

投票结果.jpg

所以我们可以知道，当k取1的时候，它属于labels为1的类，当k取3的时候，它属于labels为0的类。所以k的取值非常重要，今天的记录到此，下次记录使用sklearn学习调参，确定K以及其他参数。