python实现KNN算法（公式推导+源代码）
今天这篇⽂章要介绍的是KNN（k近邻算法），这是⼀种简单的分类算法，它的思想是通过测量不同特征值之间的距离进⾏分类的。
这样说你可能不太懂，那下⾯我们就通过⼀个简单的例⼦来形象的概述下。
以下⾯这张图为例，我们在这张图上可以看到有三种不同类别的形状（正⽅形、圆形、三⾓形），其中他们的分布也是⽐较不集中的。
假设我们在内圆⾥⾯要判断某个东西是属于哪⼀类别的话，我们该怎么做呢 ？
⽅法很简单，就是在内圆⾥⾯选择K个数据离我（图中 ？表⽰）最近的⼏个点，然后根据少数服从多数的原则，将多数的类别作为我预测的类别。
⽐如我们取k=4，那么三⾓形有2个，正⽅形1个，圆1个，他们的占⽐分别为 1/2、1/4、1/4
所以我们将三⾓形作为我们这个输⼊数据（相当于 ？）的预测类别。
⾄此，我相信你⼤概明⽩了KNN的意思。
我们在KNN中，使⽤最多的就是欧式距离来计算各个点之间的距离，如下所⽰：
好了，了解上⾯的基本知识之后，接下来就是我们来阐述下KNN算法：
1.计算测试数据与训练数据之间的距离
2.按照距离的从⼩到⼤的关系进⾏排序
3.选取距离最⼩的k个点
4.统计前k个点所在类别的出现频率
5.返回前k个点中 出现频率最⾼的类别作为测试数据的预测分类。
下⾯我们通过⽹上⼀个实战案例：优化约会⽹站的配对效果，为例通过⾃⼰的理解以及代码的部分改动来深⼊了解KNN算法。
1.准备数据集
点击这⾥下载：
⼤致的格式如上所⽰，有三个特征值以及⼀种标签类。
其中第⼀列代表的是：每年获得的飞⾏常客⾥程数
第⼆列代表的是：玩视频游戏所耗时间百分⽐
第三列代表的是：每周消费的冰淇淋公升数
第四列代表的是：1-不喜欢、2-有点喜欢、3-⾮常喜欢
通过输⼊前三个特征来预测约会的对象是否符合⾃⼰的⼝味。
2.⾸先读取⽂件数据
def loadData(filename):
"""
:param filename: ⽂件路径名
:return: dataMat：数据集      lableMat：标签集
"""
# 读取⽂件
fr = open(filename)
# 读取⽂件内容
getFile = fr.readlines()
# 获取⽂件⾏数
lines = len(getFile)
# 定义存放标签的列表
lableMat = []
# 定义⼀个空矩阵，存放特征值的列表
emptyMat = np.zeros((lines,3))
# 初始化索引
index = 0
# 通过迭代读取数据
for line in getFile:
# 将每⼀⾏的数据的空格或者换⾏符去掉
lineArr = line.strip().split()
# 逐⾏读取前三列数据
# dataMat.append(lineArr[:3]) # 这⾥不使⽤这个⽅法的⽬的是⽣成的是列表，后续我们需要使⽤的是矩阵，所以⽤下⾯那个⽅法，避免后续不必要的⿇烦        emptyMat[index,:] = lineArr[:3]
# 读取每⼀⾏的标签值(lineArr[-1]代表的是每⼀⾏最后⼀个元素)
lableMat.append(int(lineArr[-1]))  # 为什么要转为int，因为我们的linArr[-1]是str类型，这⾥不类型转换后续操作
# 索引值⾃增
index += 1
return emptyMat,lableMat
3.我们图形化显⽰每年获得的飞⾏常客⾥程数与玩视频游戏所消耗时间占⽐
这是运⾏结果，代码如下所⽰：
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.lines as mlines
from matplotlib.font_manager import FontProperties
def loadData(filename):
"""
python怎么读取文件中的数据
"""
:param filename: ⽂件路径名
:return: dataMat：数据集      lableMat：标签集
"""
# 读取⽂件
fr = open(filename)
# 读取⽂件内容
getFile = fr.readlines()
# 获取⽂件⾏数
lines = len(getFile)
# 定义存放标签的列表
lableMat = []
# 定义⼀个空矩阵，存放特征值的列表
emptyMat = np.zeros((lines,3))
# 初始化索引
index = 0
# 通过迭代读取数据
for line in getFile:
# 将每⼀⾏的数据的空格或者换⾏符去掉
lineArr = line.strip().split()
# 逐⾏读取前三列数据
#dataMat.append(lineArr[:3])
emptyMat[index,:] = lineArr[:3]
# 读取每⼀⾏的标签值(lineArr[-1]代表的是每⼀⾏最后⼀个元素)
lableMat.append(int(lineArr[-1]))  # 为什么要转会出问题为int，因为我们的linArr[-1]是str类型，这⾥不类型转换后续操作        # 索引值⾃增
index += 1
return emptyMat,lableMat
def show(dataMat,lableMat):
"""
:param dataMat:
:param lableMat:
"""
# 设置汉字格式
font = FontProperties(fname=r"D:\f", size=9)
# 设置颜⾊列表
LabelColros = []
# 给不同的标签添加上不同的颜⾊
for i in lableMat:
if i == 1:
LabelColros.append('black')
if i == 2:
LabelColros.append('orange')
if i == 3:
LabelColros.append('red')
# 画出散点图，以datas矩阵的第⼀(飞⾏常客例程)、第⼆列(玩游戏)数据画散点数据，散点⼤⼩为15，透明度为0.5
plt.scatter(dataMat[:,0].tolist(),dataMat[:,1].tolist(), color=LabelColros,s=15, alpha=.5)
# 设置标题
plt.title('每年获得的飞⾏常客⾥程数与玩视频游戏所消耗时间占⽐', FontProperties=font,color='r',size=10)
# 设置x轴
plt.xlabel('每年获得的飞⾏常客⾥程数', FontProperties=font,color='blue')
# 设置y轴
plt.ylabel('玩视频游戏所消耗时间占', FontProperties=font,color='orange')
# 设置图例
didntLike = mlines.Line2D([], [], color='black', marker='.',
markersize=6, label='didntLike')
smallDoses = mlines.Line2D([], [], color='orange', marker='.',
markersize=6, label='smallDoses')
largeDoses = mlines.Line2D([], [], color='red', marker='.',
markersize=6, label='largeDoses')
# 添加图例
# 添加图例
plt.legend(handles=[didntLike, smallDoses, largeDoses])
# 显⽰
plt.show()
if __name__ == '__main__':
filepath = ""
data,label = loadData(filepath)
show(data,label)
4.接下来我们需要对我们的数据进⾏归⼀化处理（）
这⾥我谈下我个⼈的观点为什么要对数据进⾏归⼀化，因为我们可以看到我们的数据集第⼀列和其他2列数值之间的差值是挺⼤的，这就会导致我们在计算距离的时候会有很⼤的误差，这种误差就导致我们的分类效果不佳，所以我们为了统⼀数据进⾏归⼀化，让数据处在区间（0,1）中。
这⾥我们采⽤的是最值归⼀化，通过这种⽅法可以使数据取值在（0,1）之间，公式为：
其中x表⽰的是原始数据，min表⽰的是每⼀列最⼩值，max表⽰的是每⼀列最⼤值。
def dataNorm(dataSet):
"""
:param dataSet:
:return: diffs：最⼤最⼩之间的差值    normData：归⼀化的数据集
"""
# 获取数据集中每⼀列的最⼤值
maxValue = dataSet.max(0)
# print(maxValue)
# 获取数据集中每⼀列的最⼩值
minValue = dataSet.min(0)
# print(minValue)
# 最⼤值与最⼩值之间的差值
diffs = maxValue - minValue
# 获取dataSet⾏数
num = dataSet.shape[0]  # num = 1000
# 定义⼀个和DataSet⼀样⼤⼩的矩阵
normData = np.zeros(dataSet.shape)
# 数据归⼀化（使数据属于(0,1)之间）
for i in range(num):
# 采⽤的是最值归⼀化：x = (x - min) / (max - min)
normData[i,: ] = (dataSet[i,:] - minValue) / diffs
return diffs,normData,minValue
5.分别测试下数据归⼀化和没有归⼀化的误差
5.1 未对数据归⼀化
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.lines as mlines
from matplotlib.font_manager import FontProperties
def loadData(filename):
"""
:param filename: ⽂件路径名
:return: dataMat：数据集      lableMat：标签集
"""

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。