一看就懂的 机器学习k-近邻算法（KNN）

基础知识：
1，机器学习想相关概念：

• 机器学习（Machine Learning，ML）：是人工智能的一个分支，是实现人工智能的一个途径，即以机器学习为手段解决人工智能中的问题。让一个计算机程序针对某一个特定任务，从经验中学习，并且越来越好。
• 深度学习（DeepLearning，DL）：是机器学习拉出的分支，是机器学习算法中的一种算法，一种实现机器学习的技术和学习方法。

2，机器学习和深度学习的应用：

• 机器学习的应用： 淘宝推送、电影猜你喜欢等推荐系统，数据挖掘，计算机视觉，自然语言处理，生物特征识别，搜索引擎，医学诊断，检测信用卡欺骗，语音识别与手写识别，战略游戏，机器人等。
• 深度学习的应用： AlphaGo，语音识别，图像识别，文字识 别，智能监控。

3，机器学习类型

• 监督学习：训练集包含特征x和目标y，且目标人为标注 。根据训练集学习出一个函数，当新的数据到来的时候，可以根据这个函数预测结果。
• 无监督学习：有训练集，有输入和输出。与监督学习相比，训练集没有人为标注，不告诉模型目标是什么。
• 半监督学习：介于监督学习和无监督学习之间
• 强化学习： 通过观察来学习做成某种动作，每个动作都会对环境有所影响，学习对象根据观察到的周围环境的反馈来作出判断。

K-近邻算法（KNN）是 机器学习中的有监督学习中聚类模型

1，概念原理：K-近邻算法（K-Nearest Neighbour algorithm, KNN），是数据挖掘技术中原理最简单的算法。给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最邻近的K个实例，如果这K个实例中的多数属于某个类别，那么新数据就属于这个类别。简单理解为：由那些离X最近的K个点来投票 决定X归为哪一类。

举个栗子：使用k-近邻算法分类一个电影是爱情片还是动作片

在这个表格中， 每个电影有两个特征，我们可以通过人眼判断出新电影属于什么类型，那如果是N个呢？这就需要k-近邻算法上场啦！
我们将表格画为散点图如下：

通过观察，从散点图中大致判断，新电影是爱情片。那KNN算法是如何判断的呢？ 没错，就是距离！
二维平面两点间距离公式：

N维空间两点间距离公式：

通过计算我们可以得到训练集中所有电影与未知电影的距离，如下表所示：

通过上表的计算结果，可以得出新电影到爱情片《后来的我们》距离最近，为29.1.如果仅仅根据这个结果，就判定新电影为爱情片，那这个算法就叫最近邻算法，而非k-近邻算法、
k-近邻算法步骤如下：


2，k-近邻算法的Python实现

 #构建数据集
import pandas as pd

filmdata = {
    '电影名称':['无问西东','后来的我们','前任3','红海行动','唐人街探案','战狼2'],
    '打斗镜头':[1,5,12,108,112,115],
    '接吻镜头':[101,89,97,5,9,8],
    '电影类型':['爱情片','爱情片','爱情片','动作片','动作片','动作片',]
}

film_data = pd.DataFrame(filmdata)
print(film_data)

#计算已知类别中数据点与当前点的距离
new_data = [24,67]
dist = list( (((film_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5 )
print(dist)

#对距离进行排序，然后选择距离最近的k个点
k = 4
dist_l = pd.DataFrame( { 'dist':dist, 'labels':(film_data.iloc[:6,3]) } )
dr = dist_l.sort_values(by='dist')[:k]
print(dr)

3，封装函数

import pandas as pd

filmdata = {
    '电影名称':['无问西东','后来的我们','前任3','红海行动','唐人街探案','战狼2'],
    '打斗镜头':[1,5,12,108,112,115],
    '接吻镜头':[101,89,97,5,9,8],
    '电影类型':['爱情片','爱情片','爱情片','动作片','动作片','动作片',]
}
film_data = pd.DataFrame(filmdata)
new_data = [24,67]

'''
函数功能：KNN分类器
参数说明：
    inX: 需要进行预测分类的数据集
    dataSet: 已知分类标签的数据集（训练集 ）
    k: 超参数，选择距离最小的k个点
返回：
     result: 预测分类结果
'''
def classify0(inX,dataSet,k):
    result = []
    dist = list((((dataSet.iloc[:, 1:3] - inX) ** 2).sum(1)) ** 0.5)
    dist_l = pd.DataFrame({'dist': dist, 'labels': (dataSet.iloc[:, 3])})
    dr = dist_l.sort_values(by='dist')[:k]
    re = dr.loc[:, 'labels'].value_counts()
    result.append(re.index[0])
    return result

inX = new_data
dataSet = film_data
k = 4

print(  classify0(inX,dataSet,k)  )

这就是我们使用k-近邻算法构建的一个分类器，可以看出，分类器给的答案还是比较符合我们的预期的。

那么问题来了：分类器给出的答案是否永远都正确？ 答案一定是否定的，分类器并不会得到100%正确的结果，我们可以使用很多方法来验证分类器的准确率。 此外，分类器的性能会受到很多因素的影响，比如 k的取值，就在很大程度上影响了分类器的预测结果，还有分类器的设置、原始数据集等等。 为了测试分类器的效果，我们可以把原始数据集分为两部分，一部分用来训练算法，称为训练集；另一部分用来测试算法的准确率，称为测试集。 我们不难发现，k-近邻算法没有进行数据的训练，直接使用未知的数据与已知的数据进行比较，得到结果，因此，k-近邻算法不具有显示的学习过程。

4，总结

优点：

• 简单好用，容易理解，精度高，理论成熟，既可以用来做分类，也可以用来做回归
• 可用于数值型数据和离散型数据
• 无数据输入假定
• 适合对稀有事件进行分类

缺点：

• 计算复杂性高；空间复杂性高
• 计算量太大，所以一般数值很大的时候不用这个；但是单个样本又不能太少，否则容易发生误分
• 样本不平衡问题（即有些类别的样本数量很多，而其他样本的数量很小）
• 可理解性比较差，无法给出数据的内在含义