【机器学习】分类算法-KNN算法实现

一、前言

   最近，在学习机器学习相关的内容，就想着能不能跑一些机器学习的Demo,这样更方便后期的学习，于是在B站上，找了一个Up主【abilityjh】的视频，跟着学，跟着敲代码，自己在博客上将学的东西，以博客、大白话的形式记录，方便后期的回顾，也希望可以帮助到大家！

二、什么是KNN算法

   KNN算法也叫做K-临近算法，也就是说对于一个未知的样本，我们可以从已知的样本中，在一定范围内确定K个数，在K个数中，哪一类的类型个数多，我们就将未知样本归于哪一类，从而确定它的类型。

如图所示在这个圆圈范围内，有4个三角形，两个正方形，那么对于未知样本的红色圆形就最终判定为三角形。

三、KNN算法实现

（1）案例介绍

如上图所示，我们以B站Up主给的情况做一个案例，训练集是通过“接吻次数”、‘打斗次数’来确定电影类型，我们这个案例需要事先更具训练集来判断出测试集的电影类型。

（2）实现步骤

导入必须得数据库

import numpy as np
import matplotlib.pyplot as plt

①我们要建立训练和测试数据集

我们将接吻kiss和打斗fight分别一 一对应，用filmType代表不同的电影类型（1为爱情电影，2为动作电影），然后将数据转化为矩阵

# Python 的元组与列表类似，不同之处在于元组的元素不能修改。元组使用小括号，列表使用方括号
# (1)建立数据集
fight = (3, 2, 1, 101, 99, 98)
kiss = (104, 100, 81, 10, 5, 2)
filmType = (1, 1, 1, 2, 2, 2)
plt.scatter(fight, kiss, c=filmType)
x = np.array([fight, kiss])
x = x.T
y = np.array(filmType)
plt.show()
print(x)
print(y)

效果：

②计算距离并排序

计算未知点到每个点的距离

xx = np.array([18, 90])
# numpy求和sum(x)函数,x==0按照列求和，x=1按照行求和
dist = (((x - xx) ** 2).sum(1)) ** 0.5
# 按照索引值排序的
sortdDist = dist.argsort()

③选取最近的K个点，来做选择

从上面的操作中，我们已经能够拿到，未知点到每个测试点的由近到远的距离对应的下标，此时我们采用一个classCount{}字典来统计，临近的K个点中，不同类型出现的次数。

k = 4
classCount = {}
for i in range(k):
    # 根据索引值去映射
    voteLabel = y[sortdDist[i]]
    classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
print('class: count', classCount)

这段代码稍微有点绕，解释一下：我们选取临近的K个点，创建了一个字典classCount{},我们遍历循环从0开始，我们从上面的代码知道，sortdDist[0]=1，y[1]=1,所以classCount[voteLabel] = classCount.get(voteLabel, 0) + 1就是在classCount[1]=0的基础上＋1，则classCount[1]=1，这是第一次循环；我们不妨在分析一次i=1时的循环：sortdDist[1]=2，y[2]=1,所以classCount[voteLabel] = classCount.get(voteLabel, 0) + 1就是在classCount[1]=1的基础上＋1，则classCount[1]=2;其他的以此类推即可！最终的话classCount={1:3,2:1}

运行效果：

④根据多数表决，输出结果

其实，就是将我们classCount中的value做比较（比大小），得出value值最大的，对应的key,则对应key的类型就是未知点对应类型。

maxType = 0
maxCount = -1
for key, value in classCount.items():
    if value > maxCount:
        maxType = key
        maxCount = value
print('output: ', maxType)

效果：

如图所示，我们就可以根据训练集和规定的K个参数，得到我们未知的点的类型为1即爱情类电影。

四、总结

   虽然这只是一个简单的案例，但是却可以帮助我们理解KNN算法的基本原理，以后面可以再出一篇通过读取文本数据（数据量较多），通过KNN算法来实现未知变量的分类和识别。