一、K近邻算法概念
K近邻（k-Nearest Neighbor，简称kNN）学习是一种或常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本的实质输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或者加权投票，距离越近的样本权重越大。
k近邻没有显式的训练过程。事实上，它是“懒惰学习”的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，成为“急切学习”。
图1、为k近邻分类器示意图
图1中有红色三角和蓝色方法两种类别，我们现在需要判断绿色圆点榆树哪种类别
当k=3时，绿色圆点属于红色三角这种类别；
当k=5时，绿色圆点属于蓝色方块这种类别。
下面给出两个距离公式
第一个是欧几里得距离（也就是我们经常用到的）公式：
扩展到n维空间：
第二个是曼哈顿距离公式：
扩展到n维空间：
步骤：
（1）计算已知类别数据集中的点与当前点之间的距离；
（2）按照距离递增次序排序；
（3）选取与当前点距离最小的k个点；
（4）确定前k个点所在类别的出现频率；
（5）返回前k个点，出现频率最高的类别作为当前点的预测类别。
算法功能：分类（核心）、回归
算法类型：有监督学习，懒惰学习，距离模型
数据输入：包含数据标签y，且特征空间中至少至少包含k个训练样本（k>=1）特征空间 中各个特征的量纲需统一，若不统一则需要进行归一化处理自定义的超参数k（k>=1）
模型输出：在KNN分类中，输出是标签中的某个类别
在KNN回归中，输出是对象的属性值，该值是距离输入的数据最近的K个训练 样本标签的平均值。
二、python代码的实现
1、电影的预测
import pandas as pd
"""
函数功能：KNN分类器
参数说明：
intX：需要预测的数据集
dataSet：已知分类标签的数据集（训练集）
k：k-近邻算法参数，选择距离最小的k个点
返回：
result：分类结果
"""
rowdata = {'电影名称':['无问西东', '后来的我们','前任3', '红海行动', '唐人街探案','战狼2'],
'打斗镜头':[1,5,12, 108,112,115],
'接吻镜头':[101,89,97,5,9,8],
'电影类型':['爱情片','爱情片','爱情片','动作片','动作片','动作片']}
movie_data = pd.DataFrame(rowdata)
new_data = [24, 67]
def classify0(intX,dataSet,k):
result = []
dist = list((((dataSet.iloc[:6, 0:2]-intX)**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
intX = new_data
dataSet = movie_data
k = 4
print(classify0(intX, dataSet, k))
2、K近邻算法之约会网站配对效果判定
海伦-直使用在线约会网站寻找适合自己的约会对象,尽管约会网站会推荐不同的人选，但她并不是每一个都喜欢，经过一番总结，她发现曾经交往的对象可以分为三类:
●不喜欢的人
●魅力一般的人
●极具魅力得人
海伦收集约会数据已经有了-段时间，她把这些数据存放在文本文件datingTestSet.txt中，其中各字段分别为:
1.每年飞行常客里程
2.玩游戏视频所占时间比
3.每周消费冰淇淋公升数
import pandas as pd
import matplotlib as mpl
import matplotlib.pyplot as plt
#
daTingTest = pd.read_table('datingTestSet.txt', header=None)
"""
数据集表示
不喜欢的人
魅力一般的人
极具魅力的人
1.每年飞行常客里程
2.玩游戏视频所占时间比
3.每周消费冰淇淋公升数
daTingTest.head()查看前五行数据
daTingTest.shape查看多少行多少列(1000, 4)
daTingTest.info()
RangeIndex: 1000 entries, 0 to 999
Data columns (total 4 columns):
0 1000 non-null int64
1 1000 non-null float64
2 1000 non-null float64
3 1000 non-null object
dtypes: float64(2), int64(1), object(1)
memory usage: 31.3+ KB
None
"""
#把不同标签用颜色区分
Color = []
for i in range(daTingTest.shape[0]):
m = daTingTest.iloc[i, -1]
if m == 'didntLike':
Color.append('black')
if m == 'smallDoses':
Color.append('orange')
if m == 'largeDoses':
Color.append('red')
# 绘制两两特征之间的散点图
plt.rcParams['font.sans-serif'] = ['Simhei'] #图中字体设置为黑体
pl=plt.figure(figsize=(12,8))
fig1 = pl.add_subplot(221)
plt.scatter(daTingTest.iloc[:, 1], daTingTest.iloc[:, 2], marker='.', c=Color)
plt.xlabel('玩游戏视频所占时间比')
plt.ylabel('每周消费冰淇淋公升数')
fig2 = pl.add_subplot(222)
plt.scatter(daTingTest.iloc[:, 0], daTingTest.iloc[:, 1], marker='.', c=Color)
plt.xlabel('每年飞行常客里程')
plt.ylabel('玩游戏视频所占时间比')
fig3 = pl.add_subplot(223)
plt.scatter(daTingTest.iloc[:, 0], daTingTest.iloc[:, 2], marker='.', c=Color)
plt.xlabel('每年飞行常客里程')
plt.ylabel('每周消费冰淇淋公升数')
plt.show()
#数据归一化
"""
函数功能：归一化
参数说明：
dataSet：原始数据集
返回：0-1标准化之后的数据集
"""
def minmax(dataSet):
minof = dataSet.min()
maxof = dataSet.max()
normSet = (dataSet - minof)/(maxof - minof)
return normSet
daTingT = pd.concat([minmax(daTingTest.iloc[:, :3]), daTingTest.iloc[:, 3]], axis=1)
#q切分训练集和测试集
"""
函数功能：切分训练集和测试集
参数说明：
dataSet：原始数据集
rate：训练集所占比例
返回：切分好的训练集和测试集
"""
def randSplit(dataSet,rate=0.9):
n = dataSet.shape[0]
m = int(n*rate)
train = dataSet.iloc[:m, :]
test = dataSet.iloc[m:, :]
test.index = range(test.shape[0])
return train, test
train, test = randSplit(daTingT)
#定义分类器的函数
def datingClass(train,test,k):
n = train.shape[1]-1
m = test.shape[0]
result = []
for i in range(m):
dist = list((((train.iloc[:, :n]-test.iloc[i, :n])**2).sum(1))**0.5)
dist_l = pd.DataFrame({'dist': dist, 'labels': (train.iloc[:, n])})
dr = dist_l.sort_values(by='dist')[: k]
re = dr.loc[:, 'labels'].value_counts()
result.append(re.index[0])
result = pd.Series(result)
test['predict'] = result
acc = (test.iloc[:, -1]== test.iloc[:, -2]).mean()
print('模型预测准确率为%.2f' % acc)
return test
print(datingClass(train,test,5))
结果
模型预测准确率为0.95
0 1 2 3 predict
0 0.513766 0.170320 0.262181 didntLike didntLike
1 0.089599 0.154426 0.785277 smallDoses smallDoses
2 0.611167 0.172689 0.915245 didntLike didntLike
3 0.012578 0.000000 0.195477 smallDoses smallDoses
4 0.110241 0.187926 0.287082 smallDoses smallDoses
5 0.812113 0.705201 0.681085 didntLike didntLike
6 0.729712 0.490545 0.960202 didntLike didntLike
7 0.130301 0.133239 0.926158 smallDoses smallDoses
8 0.557755 0.722409 0.780811 largeDoses largeDoses
9 0.437051 0.247835 0.131156 largeDoses didntLike
10 0.722174 0.184918 0.074908 didntLike didntLike
11 0.719578 0.167690 0.016377 didntLike didntLike
12 0.690193 0.526749 0.251657 didntLike didntLike
13 0.403745 0.182242 0.386039 didntLike didntLike
14 0.401751 0.528543 0.222839 largeDoses largeDoses
15 0.425931 0.421948 0.590885 largeDoses largeDoses
16 0.294479 0.534140 0.871767 largeDoses largeDoses
17 0.506678 0.550039 0.248375 largeDoses largeDoses
18 0.139811 0.372772 0.086617 largeDoses smallDoses
19 0.386555 0.485440 0.807905 largeDoses largeDoses
20 0.748370 0.508872 0.408589 didntLike didntLike
21 0.342511 0.461926 0.897321 largeDoses largeDoses
22 0.380770 0.515810 0.774052 largeDoses largeDoses
23 0.146900 0.134351 0.129138 smallDoses smallDoses
24 0.332683 0.469709 0.818801 largeDoses largeDoses
25 0.117329 0.067943 0.399234 smallDoses smallDoses
26 0.266585 0.531719 0.476847 largeDoses largeDoses
27 0.498691 0.640661 0.389745 largeDoses largeDoses
28 0.067687 0.057949 0.493195 smallDoses smallDoses
29 0.116562 0.074976 0.765075 smallDoses smallDoses
.. ... ... ... ... ...
70 0.588465 0.580790 0.819148 largeDoses largeDoses
71 0.705258 0.437379 0.515681 didntLike didntLike
72 0.101772 0.462088 0.808077 smallDoses smallDoses
73 0.664085 0.173051 0.169156 didntLike didntLike
74 0.200914 0.250428 0.739211 smallDoses smallDoses
75 0.250293 0.703453 0.886825 largeDoses largeDoses
76 0.818161 0.690544 0.714136 didntLike didntLike
77 0.374076 0.650571 0.214290 largeDoses largeDoses
78 0.155062 0.150176 0.249725 smallDoses smallDoses
79 0.102188 0.000000 0.070700 smallDoses smallDoses
80 0.208068 0.021738 0.609152 smallDoses smallDoses
81 0.100720 0.024394 0.008994 smallDoses smallDoses
82 0.025035 0.184718 0.363083 smallDoses smallDoses
83 0.104007 0.321426 0.331622 smallDoses smallDoses
84 0.025977 0.205043 0.006732 smallDoses smallDoses
85 0.152981 0.000000 0.847443 smallDoses smallDoses
86 0.025188 0.178477 0.411431 smallDoses smallDoses
87 0.057651 0.095729 0.813893 smallDoses smallDoses
88 0.051045 0.119632 0.108045 smallDoses smallDoses
89 0.192631 0.305083 0.516670 smallDoses smallDoses
90 0.304033 0.408557 0.075279 largeDoses largeDoses
91 0.108115 0.128827 0.254764 smallDoses smallDoses
92 0.200859 0.188880 0.196029 smallDoses smallDoses
93 0.041414 0.471152 0.193598 smallDoses smallDoses
94 0.199292 0.098902 0.253058 smallDoses smallDoses
95 0.122106 0.163037 0.372224 smallDoses smallDoses
96 0.754287 0.476818 0.394621 didntLike didntLike
97 0.291159 0.509103 0.510795 largeDoses largeDoses
98 0.527111 0.436655 0.429005 largeDoses largeDoses
99 0.479408 0.376809 0.785718 largeDoses largeDoses
[100 rows x 5 columns]
