机器学习的敲门砖：kNN算法

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

作者 | Japson

来源 | 木东居士

前言

天下苦数学久矣！

对于很多想要入门机器学习的工程师来说，数学是通往AI道路上的第一支拦路虎。一些已经工作的同学不得不捡起早已还给老师的数学知识，勉强拿起《统计学习方法》、《西瓜书》等入门书籍钻研。或被一个个复杂的机公式劝退，或记下一堆公式定理之后却不知道和代码有什么关系，茫然不知所措。

其实对于工程师来说，最直接的入门方法就是coding。

本系列从最简单的机器学习算法“K-近邻算法”开始，通过代码走进机器学习的大门，搞定传统机器学习算法。

首先会介绍算法的基本原理，然后依据原理手动实现算法，最后使用sklearn中提供的机器学习库完成一些小demo。不用担心，相关的机器学习概念以及算法原理也会穿插其中，帮助你以“代码->原理->代码”这种迭代的方式完成学习。

需要：

掌握Python语言，能够使用Numpy、Pandas等工具库。

安装Anaconda

不要求对机器学习算法以及相关概念有很深刻的了解，因为在文章中会对首次出现的概念进行介绍。

子曰：“先行其言而后从之”。行动永远是引发改变的第一步，话不多说，先让我们码起来吧！

初探kNN算法

为什么选择kNN

为什么说KNN算法是机器学习的敲门砖？

首先KNN算法思想简单朴素，容易理解，几乎不需要任何数学知识。这一点使得KNN算法非常适合入门。

其次，KNN算法也很好用，理论成熟，简单粗暴，既可以用来做分类（天然支持多分类），也可以用来做回归。并且与朴素贝叶斯之类的算法相比，由于其对数据没有假设，因此准确度高，对异常点不敏感。

最后，kNN算法简单，但是可以解释机器学习算法过程中的很多细节问题，能够完整的刻画机器学习应用的流程。

当然KNN算法也有缺点，我们会在最后进行总结。

kNN思想简介

鲁迅曾经说过：“想要了解一个人，就去看看他的朋友”。因此，KNN算法是鲁迅发明的。

kNN(k-NearestNeighbor)，也就是k最近邻算法。顾名思义，所谓K最近邻，就是k个最近的邻居的意思。也就是在数据集中，认为每个样本可以用离他最距离近的k个邻居来代表。

贴出一张从百度百科上找的一张图，我们可以直观地感受到这朴素的思想：我们要判断Xu 是什么颜色的，找到与其距离最近的5个点，有4个是红色的，有1个是绿色的。因此我们认为Xu是属于红色的集合

因此我们说：

在一个给定的类别已知的训练样本集中，已知样本集中每一个数据与所属分类的对应关系（标签）。在输入不含有标签的新样本后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似的k个数据(最近邻)的分类标签。通过多数表决等方式进行预测。即选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

K近邻法不具有显式的学习过程，而是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

kNN算法流程

通过理解算法思想，可以将其简化为“找邻居+投票”。K近邻法使用的模型，实际上是特征空间的划分。模型由三个基本要素决定：

• 距离度量
• k值
• 分类决策规则
  

其中两个实例点之间的距离反映了相似程度。一般来说使用欧氏距离来计算。

梳理kNN算法流程如下：

• 计算测试对象到训练集中每个对象的距离
• 按照距离的远近排序
• 选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
• 统计这k个邻居的类别频率
• k个邻居里频率最高的类别，即为测试对象的类别
  

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Knn算法 机器学习 敲门砖 knn 学习的

0x02 算法实现

kNN算法自实现

打开Jupyter Notebook，创建Python3文件。

准备数据

首先我们准备一组数据：

1. import numpy as npimport matplotlib.pyplot as plt
   
2. # raw_data_x是特征，raw_data_y是标签，0为良性，1为恶性
   
3. raw_data_X = [[3.393533211, 2.331273381],
   
4. [3.110073483, 1.781539638],
   
5. [1.343853454, 3.368312451],
   
6. [3.582294121, 4.679917921],
   
7. [2.280362211, 2.866990212],
   
8. [7.423436752, 4.685324231],
   
9. [5.745231231, 3.532131321],
   
10. [9.172112222, 2.511113104],
    
11. [7.927841231, 3.421455345],
    
12. [7.939831414, 0.791631213]
    
13. ]
    
14. raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
    
15. # 设置训练组
    
16. X_train = np.array(raw_data_X)
    
17. y_train = np.array(raw_data_y)
    
18. # 将数据可视化
    
19. plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = 'Tumor Size')
    
20. plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='r', label = 'Time')
    
21. plt.xlabel('Tumor Size')
    
22. plt.ylabel('Time')
    
23. plt.axis([0,10,0,5])
    
24. plt.show()

复制代码

数据可视化后生成的图片如下图所示。其中横轴是肿块大小，纵轴是发现时间。每个病人的肿块大小和发病时间构成了二维平面特征中的一个点。对于每个点，我们通过label明确是恶性肿瘤（绿色）、良性肿瘤（红色）。

那么现在给出一个肿瘤患者的数据（样本点）x：[8.90933607318, 3.365731514]，是良性肿瘤还是恶性肿瘤

求距离

我们要做的是：求点x到数据集中每个点的距离，首先计算距离，使用欧氏距离

下面写代码：

1. from math import sqrt
   
2. distances = []
   
3. # 用来记录x到样本数据集中每个点的距离
   
4. for x_train in X_train:
   
5. d = sqrt(np.sum((x_train - x) ** 2))
   
6. distances.append(d)
   
7. # 使用列表生成器，一行就能搞定，对于X_train中的每一个元素x_train都进行前面的运算，把结果生成一个列表
   
8. distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
   
9. distances
   
10. 输出：
    
11. [5.611968000921151, 6.011747706769277,
    
12. 7.565483059418645, 5.486753308891268,
    
13. 6.647709180746875, 1.9872648870854204,
    
14. 3.168477291709152, 0.8941051007010301,
    
15. 0.9830754144862234, 2.7506238644678445]

复制代码

在求出距离列表之后，我们要找到最小的距离，需要进行一次排序操作。其实不是简单的排序，因为我们把只将距离排大小是没有意义的，我们要知道距离最小的k个点是在样本集中的位置。

这里我们使用函数：np.argsort(array) 对一个数组进行排序，返回的是相应的排序后结果的索引

1. nearest = np.argsort(distances)
   
2. nearest
   
3. 输出：array([7, 8, 5, 9, 6, 3, 0, 1, 4, 2])

复制代码

结果的含义是：距离最小的点在distances数组中的索引是7，第二小的点索引是8... 近到远是哪些点

选k值

然后我们选择k值，这里暂定为6，那就找出最近的6个点（top 6），并记录他们的标签值（y）

1. k = 6topK_y = [y_train[i] for i in nearest[:k]]
   
2. topK_y
   
3. 输出：[1, 1, 1, 1, 1, 0]

复制代码

决策规则

下面进入投票环节。找到与测试样本点最近的6个训练样本点的标签y是什么。可以查不同类别的点有多少个。

将数组中的元素和元素出现的频次进行统计

1. from collections import Counter
   
2. votes = Counter(topK_y)
   
3. votes
   
4. 输出：一个字典，原数组中值为0的个数为1，值为1的个数有为5Counter({0:1, 1:5})
   
5. # Counter.most_common(n) 找出票数最多的n个元素，返回的是一个列表，列表中的每个元素是一个元组，元组中第一个元素是对应的元素是谁，第二个元素是频次votes.most_common(1)
   
6. 输出：[(1,5)]
   
7. predict_y = votes.most_common(1)[0][0]
   
8. predict_y
   
9. 输出：1

复制代码

得到预测的y值是1

自实现完整工程代码

我们已经在jupyter notebook中写好了kNN算法，下面我们在外部进行封装。

相关代码可以在 https://github.com/japsonzbz/ML_Algorithms 中看到

1. import numpy as npimport math as sqrtfrom collections import Counterclass kNNClassifier:
   
2. def __init__(self, k):
   
3. """初始化分类器"""
   
4. assert k >= 1, "k must be valid"
   
5. self.k = k
   
6. self._X_train = None
   
7. self._y_train = None
   
8. def fit(self, X_train, y_train):
   
9. """根据训练数据集X_train和y_train训练kNN分类器"""
   
10. assert X_train.shape[0] == y_train.shape[0], \ "the size of X_train must be equal to the size of y_train"
    
11. assert self.k <= X_train.shape[0], \ "the size of X_train must be at least k"
    
12. self._X_train = X_train
    
13. self._y_train = y_train return self def predict(self,X_predict):
    
14. """给定待预测数据集X_predict，返回表示X_predict结果的向量"""
    
15. assert self._X_train is not None and self._y_train is not None, \ "must fit before predict!"
    
16. assert X_predict.shape[1] == self._X_train.shape[1], \ "the feature number of X_predict must be equal to X_train"
    
17. y_predict = [self._predict(x) for x in X_predict] return np.array(y_predict) def _predict(self, x):
    
18. distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in self._X_train]
    
19. nearest = np.argsort(distances)
    
20. topK_y = [self._y_train[i] for i in nearest]
    
21. votes = Counter(topK_y) return votes.most_common(1)[0][0] def __repr__(self):
    
22. return "kNN(k=%d)" % self.k
    
23. 
    
24. 当我们写完定义好自己的kNN代码之后，可以在jupyter notebook中使用魔法命令进行调用：
    
25. 
    
26. %run myAlgorithm/kNN.py
    
27. knn_clf = kNNClassifier(k=6)
    
28. knn_clf.fit(X_train, y_train)
    
29. X_predict = x.reshape(1,-1)
    
30. y_predict = knn_clf.predict(X_predict)
    
31. y_predict
    
32. 输出：array([1])

复制代码

现在我们就完成了一个sklearn风格的kNN算法，但是实际上，sklearn封装的算法比我们实现的要复杂得多。

sklearn中的kNN

代码

对于机器学习来说，其流程是：训练数据集 -> 机器学习算法 -fit-> 模型 输入样例 -> 模型 -predict-> 输出结果

我们之前说过，kNN算法没有模型，模型其实就是训练数据集，predict的过程就是求k近邻的过程。

我们使用sklearn中已经封装好的kNN库。你可以看到使用有多么简单。

1. from sklearn.neighbors import KNeighborsClassifier
   
2. # 创建kNN_classifier实例
   
3. kNN_classifier = KNeighborsClassifier(n_neighbors=6)
   
4. # kNN_classifier做一遍fit(拟合)的过程，没有返回值，模型就存储在kNN_classifier实例中
   
5. kNN_classifier.fit(X_train, y_train)
   
6. #
   
7. 
   
8. kNN进行预测predict，需要传入一个矩阵，而不能是一个数组。reshape()成一个二维数组，第一个参数是1表示只有一个数据，第二个参数-1，numpy自动决定第二维度有多少y_predict
   
9. = kNN_classifier.predict(x.reshape(1,-1))
   
10. y_predict
    
11. 输出：array([1])
    
12. 
    
13. 在kNN_classifier.fit(X_train, y_train)这行代码后其实会有一个输出：
    
14. 
    
15. KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
    
16. metric_params=None, n_jobs=1, n_neighbors=6, p=2,
    
17. weights='uniform')

复制代码

时光人 发表于 2019-12-6 11:46
0x02 算法实现kNN算法自实现打开Jupyter Notebook，创建Python3文件。[/backcolor ...

很精彩，谢谢楼主的分享~

        参数

1. class
   
2. sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,
   
3. weights=’uniform’, algorithm=’auto’, leaf_size=30, p=2, metric=’minkowski’,
   
4. metric_params=None, n_jobs=None, **kwargs)

复制代码

        我们研究一下参数：

•                 n_neighbors: int, 可选参数(默认为 5)。用于kneighbors查询的默认邻居的数量
•                 weights（权重）: str or callable(自定义类型), 可选参数(默认为 ‘uniform’)。用于预测的权重参数，可选参数如下：
•                 uniform : 统一的权重. 在每一个邻居区域里的点的权重都是一样的。
•                 distance : 权重点等于他们距离的倒数。
•                 使用此函数，更近的邻居对于所预测的点的影响更大。
•                 [callable] : 一个用户自定义的方法，此方法接收一个距离的数组，然后返回一个相同形状并且包含权重的数组。
•                 algorithm（算法）: {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, 可选参数（默认为 ‘auto’）。计算最近邻居用的算法：
•                 ball_tree 使用算法BallTree
•                 kd_tree 使用算法KDTree
•                 brute 使用暴力搜索
•                 auto 会基于传入fit方法的内容，选择最合适的算法。
•                 注意 : 如果传入fit方法的输入是稀疏的，将会重载参数设置，直接使用暴力搜索。
•                 leaf_size（叶子数量）: int, 可选参数(默认为 30)。传入BallTree或者KDTree算法的叶子数量。此参数会影响构建、查询BallTree或者KDTree的速度，以及存储BallTree或者KDTree所需要的内存大小。此可选参数根据是否是问题所需选择性使用。
•                 p: integer, 可选参数(默认为 2)。用于Minkowski metric（闵可夫斯基空间）的超参数。p = 1, 相当于使用曼哈顿距离，p = 2, 相当于使用欧几里得距离]，对于任何 p ，使用的是闵可夫斯基空间。
•                 metric（矩阵）: string or callable, 默认为 ‘minkowski’。用于树的距离矩阵。默认为闵可夫斯基空间，如果和p=2一块使用相当于使用标准欧几里得矩阵. 所有可用的矩阵列表请查询 DistanceMetric 的文档。
•                 metric_params（矩阵参数）: dict, 可选参数(默认为 None)。给矩阵方法使用的其他的关键词参数。
•                 n_jobs: int, 可选参数(默认为 1)。用于搜索邻居的，可并行运行的任务数量。如果为-1, 任务数量设置为CPU核的数量。不会影响fit
  

        方法

        对于KNeighborsClassifier的方法：

        方法名含义fit(X, y)使用X作为训练数据，y作为目标值（类似于标签）来拟合模型。get_params([deep])获取估值器的参数。neighbors([X, n_neighbors, return_distance])查找一个或几个点的K个邻居。kneighbors_graph([X, n_neighbors, mode])计算在X数组中每个点的k邻居的（权重）图。predict(X)给提供的数据预测对应的标签。predict_proba(X)返回测试数据X的概率估值。score(X, y[, sample_weight])返回给定测试数据和标签的平均准确值。set_params(**params)设置估值器的参数。

       

        0xFF 总结

        在本文中我们了解了第一个ML算法kNN，kNN凭借着自己朴素成熟的特点成为机器学习的敲门砖。

        然后我们学习了kNN算法的流程，并且在jupyter notebook上手动实现了代码，并且在外部也进行了封装。最后我们学习了sklearn中的kNN算法。

        虽然我们自己实现了一个机器学习算法，但是它的效果怎样样？预测准确率高不高？我们在机器学习过程中还有哪些需要注意的问题呢？

正在学，到时候有问题咨询楼主，感谢！