KNN近邻算法详解

2019-02-14 本文已影响12人 code_solve

前言

通过本文，你将了解并深刻理解什么是 KNN算法。
当然，阅读本文前，你最好会点python,这样阅读起来才会没有障碍噢

春节后的第一篇文章，在这里祝大家新的一年工作顺心！心想事成！新年又有新高度！

什么是 KNN近邻算法？

通常我们都知道这么一句话 “近朱者赤近墨者黑” ，KNN算法就是这句话的完美诠释了。

我们想要判断某个东西属于哪个分类，那么我们只需要找到最接近该东西的 K 个邻居，这些邻居中哪种分类占比最大，那么我们就认为该东西就属于这个分类！

KNN近邻算法实践

这里我们会使用到 sklearn 和 numpy 两个库，当然就算你不熟悉也没关系，这里主要就是为了直观的感受一下 KNN 算法。

导入数据

import numpy as np
import matplotlib 
import matplotlib.pyplot as plt
from sklearn import datasets

#这里我们采集的是 sklearn 包里面自带的 鸢尾花 的数据
digits = datasets.load_iris()

# 鸢尾花的种类 用 0，1，2 标识
y = digits.target

# 鸢尾花的 特征，为了可视化的需求，我们这里只取前两个特征
x = digits.data[:,:2]

# 在2d平面上画出鸢尾花的分布情况
#为了方便显示，我们这里只取标识为 0 和 1 两种鸢尾花的数据
plt.scatter(x[y==0,0],x[y==0,1],color='r')
plt.scatter(x[y==1,0],x[y==1,1],color='b')
plt.show()

鸢尾花分布图.png

拆分数据

# 将数据拆分为 测试数据 和 训练数据
from sklearn.model_selection import train_test_split
x_train,x_test,y_train,y_test = train_test_split(x,y,test_size=0.2)
# 显示如下图
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='r')
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='b')

# 测试数据我们用 黄色显示
plt.scatter(x_test[y_test==0,0],x_test[y_test==0,1],color='y')
plt.scatter(x_test[y_test==1,0],x_test[y_test==1,1],color='y')

plt.show()

测试数据和训练数据

预测和校准数据

from sklearn.neighbors import KNeighborsClassifier

# 使用 sklearn knn算法模型进行训练和预测
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(x_train,y_train)
y_predict = knn.predict(x_test)

# 真实数据分布情况
plt.scatter(x[y==0,0],x[y==0,1],color='r')
plt.scatter(x[y==1,0],x[y==1,1],color='b')
plt.show()

# 预测数据分布情况
plt.scatter(x_train[y_train==0,0],x_train[y_train==0,1],color='r')
plt.scatter(x_train[y_train==1,0],x_train[y_train==1,1],color='b')

plt.scatter(x_test[y_predict==0,0],x_test[y_predict==0,1],color='r')
plt.scatter(x_test[y_predict==1,0],x_test[y_predict==1,1],color='b')

plt.show()

真实鸢尾花分布图.png

测试鸢尾花分布图

从图中我们很明显的看到左下角的一个点预测错误，其余都正确，这里我们很直观的就可以感受到 KNN 算法的整个流程，其中最关键的还是在预测数据那块，那么接下来我们就来剖析下 KNN 的原理吧

KNN算法手写实现

思路
首先我们理一下，knn的几个关键因素：
① neighbors，我们该选取几个邻居作为目标分类的依据。
② 和邻居之间的距离怎么计算
1. neighbors 很简单，我们让调用者自己传入就好了
2. 和邻居之间的距离，我们采用简单的 欧拉距离 公式计算, 如下：
  $distance = \sqrt{ \sum_{i=1}^n (X_i^a-X_i^b)^2}$

当然，真正要写好 KNN算法肯定不是我们考虑的这么简单，但是主要思路是这样，所以我们根据这个思路先来把简单的 KNN 实现一下吧。

实现
有了上面的思路，我们直接来看代码吧！


from math import sqrt
from collections import Counter

class MyKNN:
    # 初始化
    def __init__(self,n_neighbors=5):
        self.n_neighbors = n_neighbors
        self.X = None
        self.Y = None

    def fit(self,x,y):
        """
        KNN 算是一个比较特殊的算法，其实它是没有一个训练过程的，
        这里简单的将训练数据保存起来就好了  
        """
        self.X = x
        self.Y = y
    
    def _predict(self,x):
        """
        预测单个样本的所属分类
        """
        # 欧拉距离的计算
        distances = [sqrt(np.sum((i-x)**2)) for i in self.X]
        # 排序
        sort_distances_index = np.argsort(distances)
        # 找出最近的 n_neighbors 个邻居
        neighbors_index = sort_distances_index[:self.n_neighbors]
        neighbors = self.Y[neighbors_index]
        # 返回最近邻居中分类占比最大的那个分类标识
        return Counter(neighbors).most_common(1)[0][0]
    
    def predict(self, X_predict):
        """
        预测多个样本的分类
        """
        # 通过单个样本分类直接 预测就 ok了
        y_predict = [self._predict(x) for x in X_predict]
        
        return np.array(y_predict)

上面这个代码应该是相当简单了，如果你有兴趣，可以把 KNN近邻算法实践 这一节的预测代码用我们手写的跑一遍，这里就不重复了，实现的效果大同小异，但是从上面的代码我们也可以看出来，咱们是采用遍历的方式来求所有距离的，如果你和 sklearn 中的算法做下对比，会发现我们写的运行效率，那真不是一个速度级的。

KNN 调参

实践了，手写了，不知道现在你对knn是不是有了一个比较深入的了解，嗯，只想说一句，不愧是最简单的算法之一，是真的很简单，完全没有什么高深的东西嘛。。。话虽如此，但是如果你觉得这样就可以用好knn那就有点太想当然了。

这里我们就引入了 KNN的调参，其实在机器学习过程中，调参那也是很大一部分的工作内容了。

超参数 K
这个k就是我们上面的选取的邻居的个数，选取数目的不一样，对于我们预测的结果肯定也是有差异的，那么下面我们来寻找一下最优的 K 把

首先我们得有一个评价标准，这里我们简单的就用正确率来评价这个 k 的好坏把，当然在实际工作中肯定不能是这么简单了.

def score(y_predict,y_true):
  """
  传入 预测的 y  和 真实的 y ，判断一下他们的正确率
  """
  return np.sum(y_predict == y_true)/len(y_true)

寻找最佳的 K 值

best_score = 0
best_k = 0

# 循环 10 以内的 k值进行预测，并且求出最佳的 k 值
for i in range(1,10):
    knn = MyKNN(n_neighbors=i)
    knn.fit(x_train,y_train)
    y_predict = knn.predict(x_test)

    s = score(y_predict,y_test)
  
    if(s>best_score):
        best_score = s
        best_k = i

print("best_score = ",best_score)
print("best_k = ",best_k)

和距离有关的超参数
1. 权重
  什么是权重呢？举个简单的栗子，我有三个朋ABC,其中A喜欢吃苹果，BC喜欢吃梨，我和A的关系非常好，和BC只是普通朋友，那么我是喜欢吃苹果还是梨呢？如果不考虑权重，我肯定是喜欢吃梨，因为我的三个朋友有两个喜欢吃梨，但是如果考虑权重的话，就不一定了，鉴于我和A的关系非常好，那么我喜欢吃苹果的概率可能更大。
  
  通过上面的栗子，我们应该知道，关于距离的远近对于预测的结果应该是可以考虑不同权重的，距离越近，那么权重越高，我们上面写的算法那肯定是没有考虑，不管远近权重都是1。但是在 sklearn 中你是可以找到 weight 这个超参数的
2. 距离的计算方式
  上面我们采用的是欧拉距离作为距离的计算方式，实际上，在 sklearn 中，采用的是另外一种方式，叫做明可夫斯基距离，公式如下：
  $distance = ( \sum_{i=1}^n |X_i^a-X_i^b|^p)^\frac{1}{p}$
  
  其实仔细观察我们会发现，当 P = 1/2 就是我们用到的 欧拉距离 了，所以这里我们又得到一个可以调节的超参数 P，在sklearn 中你是可以找到 P 这个超参数的
  
  当然还有很多距离的计算方式，比如：余弦相似度，皮尔森相似度等

这一小节我们主要介绍了另外两个超参数，我们其实可以想一下，当有多个超参数需要调节，我们还采用上面的那个循环遍历一个个去试的话，可能就会有大问题，因为存在的可能性太多了，会导致寻找非常困难，所以这里我们需要另外一个叫做 网格搜索 的方式来寻找，这里就不介绍了，感兴趣的可以自行搜索一下噢。

KNN是否可以用于回归算法？

前面我们说了，KNN算法是一个分类算法，但事实上其同样可以用来处理回归问题，思路也很简单，找到相应的邻居，然后根据邻居的打分来求自己的打分，将分类问题就转换成了回归问题了。

最后，我们在总结下 KNN 的优缺点

优点
简单，并且效果还不错
天然适合多分类问题
缺点
效率低，样本越多，维度越多，其执行时间复杂度呈线性增长
高度数据相关性
结果不具有可解释性

KNN近邻算法详解

前言

什么是 KNN近邻算法？

KNN近邻算法实践

KNN算法手写实现

KNN 调参

KNN是否可以用于回归算法？

最后，我们在总结下 KNN 的优缺点

猜你喜欢

热点阅读

KNN近邻算法 详解

前言

什么是 KNN近邻算法？

KNN近邻算法 实践

KNN算法 手写实现

KNN 调参

KNN是否可以用于回归算法？

最后，我们在总结下 KNN 的优缺点

猜你喜欢

热点阅读

KNN近邻算法详解

KNN近邻算法实践

KNN算法手写实现