k-近邻算法概述
k-近邻算法就是采用测量不同的特征值之间的距离进行分类
它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所分类类别的对应关系。输入没有标签的新数据后，将新数据的每个特征最相似数据（最邻近）的分类标签。一般来说，我们只选择样本数据集中的前k个最相似的数据，这就是k-近邻算法中的k的出处，通常k<=20(整数)。最后我们选择k个最相似数据中出现次数最多的分类，最为新数据的分类。
优缺点
优点：精度高、对异常不敏感、无数据就输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型
k-近邻算法的一般流程
（1）、收集数据：可以使用任何方法
（2）、准备数据：距离计算所需要的数据，最好是结构化的数据格式
（3）、分析数据：可以使用任何方法
（4）、测试算法：计算错误率
（5）、使用算法：首先输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个类，最后应用对计算 出的分类执行后续的处理
电影分类的例子
使用k-近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头。假如有一部看过的电影，如何确定它是爱情片还是动作片？我们可以使用KNN来 解决这个问题。
<caption>每部电影的打斗镜头、接吻镜头以及电影评估类型</caption>
| 电影名称 | 打斗镜头 | 接吻镜头 | 电影类型 |
|---|---|---|---|
| Colifornia Man | 3 | 104 | 爱情片 |
| He’s Not Really into Dudes | 2 | 100 | 爱情片 |
| Beautiful Woman | 1 | 81 | 爱情片 |
| Kevin Longblade | 101 | 10 | 动作片 |
| Robo Slayer 3000 | 99 | 5 | 动作片 |
| Amped II | 98 | 2 | 动作片 |
| ？ | 18 | 90 | 未知 |
即使不知道未知电影的类型，我们也可以通过某种方法计算出来。首先计算出未知电影与样本集中其他电影的距离。
现在我们得到了样本中所有与未知电影的距离，按照递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是 He’s Not Really into Dudes 、Beautiful Woman 、 Colifornia Man。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型。而这三部电影全是爱情片，因此我们判定未知电影属于爱情片。
假设这里有五组数据，五个对应的标签以及一组未知标签的数据如下，我们要来预测未知标签的数据属于哪一类
已知数据：
A 1.0,1.1
A 1.0,1.0
B 0.0,0.0
B 0.0,0.1
B 0.0,0.1
未知数据
1.0,1.0
代码实现
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
'''
@Time : 2018/8/13 16:15
@Author :
@Site :
@File : KNN.py
@Software: PyCharm
'''
from numpy import *
import operator
def createDataSet():
"""
准备数据集
A 1.0,1.1
A 1.0,1.0
B 0.0,0.0
B 0.0,0.1
B 0.0,0.1
:return: group,labels
"""
group = array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1], [0.0, 0.1]])
labels = ['A', 'A', 'B', 'B', 'B']
return group, labels
def classify(inX, dataSet, labels, k):
"""
K-近邻算法
:param inX:用于分类的输入向量
:param dataSet: 输入的训练样本
:param labels: 向量的标签
:param k:用于选择最近邻居的数目
:return:
"""
dataSetSize = dataSet.shape[0] #获取训练样本的个数
diffMat = tile(inX,(dataSetSize, 1)) - dataSet #tile(A,n) 将A重复n次构成一个新的数组
sqDiffMat = diffMat**2 #将两向量之间的差值分别平方
sqDistance = sqDiffMat.sum(axis=1) #axis=1表述行，axis=0表述列
distances = sqDistance**0.5 #开方算出欧氏距离
sortedDistancesIndex = distances.argsort() #将距离从小到大排序并将其下表存入sortedDistanceIndex
classCount = {}
for i in range(k):
voteLabel = labels[sortedDistancesIndex[i]]
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 #统计各个标签出现的次数
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
#----------------测试------------------
group, labels = createDataSet()
print(classify([1,1], group, labels, 3))
"""
结果输出:A
"""
image.gif
网友评论