首页 / PYTHON / Python机器学习（十六）KNN原理与代码实现

Python机器学习（十六）KNN原理与代码实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python机器学习（十六）KNN原理与代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含36105字，纯文字阅读大概需要52分钟。

内容图文

1. KNN原理

KNN（k-Nearest Neighbour）：K-近邻算法，主要思想可以归结为一个成语：物以类聚

1.1 工作原理

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k （k <= 20）个实例，这 k 个实例的多数属于某个类，

就把该输入实例分为这个类。

https://www.cnblogs.com/ybjourney/p/4702562.html给出的例子很形象，这里借用一下。

如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，

如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

技术分享图片

由此也说明了KNN算法的结果很大程度取决于K的选择。

1.2 欧氏距离公式

计算两个向量点xA和xB之间的距离

技术分享图片

1.3 分类决策规则（如多数表决）

技术分享图片

决定技术分享图片类别，为指示函数，即当时为 1，否则为0。

1.4 算法流程

对未知类别属性的数据集中的每个点依次执行以下操作：

1. 计算已知类别数据集中的点与当前点之间的距离；

2. 按照距离递增次序排序；

3. 选取与当前点距离最小的 k 个点；

4. 确定前 k 个点所在类别的出现频率；

5. 返回前 k 个点出现频率最高的类别作为当前点的预测分类；

2. 代码实现

python3.6

每个方法的作用，以及每行代码的作用，同样我都做了详细的注解。

希望大家最好自己能实现一下，特别是在运算时 list，array，matrix之间的关系以及运用场景，

只有在你自己实现时，才能理清这三者的作用以及关系。

2.1 输入数据

datingTestSet2.txt ：约会网站数据（三种类型：不喜欢的人，魅力一般的人，极具魅力的人）

输入数据集

2.2 KNN算法实现

myKNN.py

                      1
                    #
                     -*- coding: utf-8 -*-
                      2
                    """
                      3
                    Created on Mon Sep 17 15:58:58 2018

                      4
                    KNN(K-Nearest Neighbor) K-近邻算法

                      5
                    @author: weixw

                      6
                    """
                      7
                      8
                    import
                     numpy as np

                      9
                    import
                     operator

                     10
                    #
                    输入：行测试数据集，训练数据集，标签数据集，用于选择最近邻居的数目
                     11
                    #
                    功能：根据欧氏距离公式，找到与未知类别的测试数据距离最小的 k 个点，
                     12
                    #
                         以这 k 个点出现频率最高的类别座位测试数据的预测分类。
                     13
                    #
                         欧氏距离公式：测试数据与训练数据对应位置作差，平方和，然后开方
                     14
                    #
                    输出：测试数据预测分类结果
                     15
                    def
                     classify(testDataSet, trainingDataSet, labelList, k):

                     16
                    #
                    训练数据集行数
                     17     trainingDataSetSize = trainingDataSet.shape[0]
 18#np.tile(testDataSet, (trainingDataSetSize,1)沿X轴复制1倍（相当于没有复制），再沿Y轴复制trainingDataSetSize倍，维数：1000*3 19#欧氏距离公式实现  20#1 测试数据 - 训练数据 21     diffMat = np.mat(np.tile(testDataSet, (trainingDataSetSize, 1)) - trainingDataSet)
 22#2 差平方（需要将matrix转化为数组，否则报错） 23     sqDiffMat = diffMat.A**2
 24#3 按行求和 axis = 0(默认按列) axis = 1(按行) 25     sqDistances = sqDiffMat.sum(axis = 1)
 26#4 开方 27     distances = sqDistances**0.5
 28#agrsort():从小到大排序，返回欧氏距离最小值对应的索引列表 29     sortedDistIndicies = distances.argsort()
 30#预测分类计数 31     predictClassCount = {}
 32#多数表决方式，选择 k 个欧氏距离最小值  33for i in range(k):
 34#找到索引对应的标签值 35         voteLabel = labelList[sortedDistIndicies[i]]
 36#预测标签值字典，存储索引标签值预测次数 37         predictClassCount[voteLabel] = predictClassCount.get(voteLabel, 0) + 1
 38#对象按值逆向（由大到小）排序  39# sorted(iterable[, cmp[, key[, reverse]]]) 40# itemgetter(1) 取第一项结果 41     sortedPredictClassCount = sorted(predictClassCount.items(), key = operator.itemgetter(1), reverse = True)
 42return sortedPredictClassCount[0][0]
 43 44 45 46#输入：数据文件 47#功能：加载文件，文件最后一列是标签数据，分离特征数据集与标签数据集 48#     自动检测多少列特征数据并分离 49#输出：特征数据集矩阵，标签数据集矩阵 50def loadDataSet(fileName):
 51#特征数据列长度 52     numberFeat = len(open(fileName).readline().split(‘\t‘)) - 1
 53     dataSet = []; labelSet = []
 54     fr = open(fileName)
 55for line in fr.readlines():
 56         lineArr = []
 57#去除收尾空格，然后分割每一列 58         curLine = line.strip().split(‘\t‘)
 59#保存每一列特征数据 60for i in range(numberFeat):
 61            lineArr.append(float(curLine[i]))
 62        dataSet.append(lineArr)
 63         labelSet.append(float(curLine[-1]))
 64return np.mat(dataSet), labelSet
 65 66#输入：原始特征数据集 67#功能：数据归一化，使每类数据都在同一范围内 (0, 1) 变化 68#     归一化公式：newValue = (oldValue - min)/(max - min) 69#输出：归一化后特征数据集，范围数组大小（分母）,列最小值数组    70def autoNorm(dataMat):
 71#min(axis) 无参数：所有值中最小值；axis = 0：每列最小值；axis = 1：每行最小值 72#求出每列最小值 73     minValsMat = dataMat.min(0)
 74#求出每列最大值 75     maxValsMat = dataMat.max(0)
 76#计算差值（对应位置相减） 77     rangesMat = maxValsMat - minValsMat
 78#归一化特征数据集初始化，维数：1000*3 79     normDataMat = np.zeros(np.shape(dataMat))
 80#原始数据集行数目 81     m = dataMat.shape[0]
 82#归一化公式分子实现 83#np.tile(minVals, (m,1)沿X轴复制1倍（相当于没有复制），再沿Y轴复制m倍，维数：1000*3 84     normDataMat = dataMat - np.tile(minValsMat, (m, 1))
 85#归一化公式实现，求得归一化结果 86     normDataMat = normDataMat/np.tile(rangesMat, (m, 1))
 87return normDataMat, rangesMat, minValsMat
 88 89#输入：特征数据集矩阵，标签数据集列表，测试数据与训练数据比例，用于选择最近邻居的数目 90#功能：求出测试特征数据集预测分类结果 91# 1.解析文件 92# 2.通过ratio确定测试数据集 93# 3.归一化 94# 4.对每一行测试数据运用欧氏距离公式以及多数表决方式预测分类结果 95# 5.求出整个测试数据集的预测分类结果 96#输出：测试数据预测分类结果 97def dataClassify(dataMat, labelList, ratio, k):
 98 99#特征数据集归一化100     normDataMat, rangesMat, minValsMat = autoNorm(dataMat)
101#归一化特征数据集行数目102     m = normDataMat.shape[0]
103#测试数据集行数目（也就知道训练数据集行数）104     testDataNum = int(m*ratio)
105#预测分类错误计数106     errorCount = 0.0
107for i in range(testDataNum):
108#求出测试数据集每行预测分类109         classifierResult = classify(normDataMat[i, :], normDataMat[testDataNum:m, :], labelList[testDataNum:m], k)
110print ("the classifier result is: %d, the real answer is: %d"% (classifierResult, labelList[i]))
111#统计错误预测分类112if(classifierResult != labelList[i]):
113             errorCount += 1.0
114print ("the total error count is %d"% errorCount)
115print ("the total error rate is: %f"%(errorCount/float(testDataNum)))
116117118#绘制散点图119def drawScatter(filename):
120import matplotlib.pyplot as plt
121#加载文件，分离特征数据集和标签数据集122     dataMat, labelList = loadDataSet(filename)
123#矩阵转化为数组124     dataArr = dataMat.A
125#创建一副图画126    plt.figure()
127#保存标签类型相同的索引值（观察标签数据集，有3种不同类型）128     label_idx1 = []; label_idx2 = []; label_idx3 = []
129#遍历标签数组，索引，值130for index, value in enumerate(labelList):
131if(value == 1):
132            label_idx1.append(index)
133elif(value == 2):
134            label_idx2.append(index)
135else:
136            label_idx3.append(index)
137#scatter(x,y,s,maker,color,label)138#x,y必须是数组类型，s表示形状大小，maker:形状139     plt.scatter(dataArr[label_idx1, 1], dataArr[label_idx1, 2], marker = ‘x‘, color = ‘m‘, label = ‘no like‘, s = 30)
140     plt.scatter(dataArr[label_idx2, 1], dataArr[label_idx2, 2], marker = ‘+‘, color = ‘c‘, label = ‘like‘, s = 50)
141     plt.scatter(dataArr[label_idx3, 1], dataArr[label_idx3, 2], marker = ‘o‘, color = ‘r‘, label = ‘very like‘, s = 15)
142     plt.legend(loc = ‘upper right‘)
143144

KNN算法实现

2.3 测试代码

                     1
                    #
                     -*- coding: utf-8 -*-
                     2
                    """
                     3
                    Created on Tue Sep 18 14:07:14 2018

                     4
                    测试KNN算法

                     5
                    @author: weixw

                     6
                    """
                     7
                    import
                     myKNN as mk

                     8
                    #
                    前50%是测试数据，后50%作为训练数据
                     9 ratio = 0.5
10#选择邻居数目11#errCount:31 errRate:6.2%12 k = 4
13#errCount:30 errRate:6.0%14#k = 815#errCount:30 errRate:6.0%16#k = 1217#errCount:33 errRate:6.6%18#k = 1619#errCount:32 errRate:6.4%20#k = 2021222324 fileName = ‘datingTestSet2.txt‘25#绘制数据散点图26mk.drawScatter(fileName)
27#加载文件，分离特征数据集和标签数据集28 dataMat, labelList = mk.loadDataSet(fileName)
29#预测测试数据结果30 mk.dataClassify(dataMat, labelList, ratio, k)

测试代码

2.4 运行结果

输入数据的散点图：

技术分享图片

k = 4 ，ratio = 0.5（一半测试数据，一半训练数据）时分类结果：

技术分享图片

在 k为不同值时运行结果：

技术分享图片

可以看出，并不是 k越大，正确率越高，会产生过拟合。

3. 优缺点

优点：

1. 简单，易于理解，易于实现，无需训练；

2. 精度高，对异常值不敏感；

缺点：

计算复杂度高，空间复杂度高。

原文：https://www.cnblogs.com/huanghanyu/p/13154132.html

内容总结

以上是互联网集市为您收集整理的Python机器学习（十六）KNN原理与代码实现全部内容，希望文章能够帮你解决Python机器学习（十六）KNN原理与代码实现所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1272745.html

来源：【匿名】

首页 / PYTHON / Python机器学习（十六）KNN原理与代码实现

Python机器学习（十六）KNN原理与代码实现

内容导读

内容图文

1. KNN原理

1.1 工作原理

1.2 欧氏距离公式

1.3 分类决策规则（如多数表决）

1.4 算法流程

2. 代码实现

2.1 输入数据

2.2 KNN算法实现

2.3 测试代码

2.4 运行结果

3. 优缺点

优点：

缺点：

内容总结

内容备注

内容手机端

【Python机器学习（十六）KNN原理与代码实现】教程文章相关的互联网学习教程文章

Python机器学习（十六）KNN原理与代码实现【代码】【图】

机器学习-Python 01【代码】【图】

[Machine Learning]Python机器学习库【代码】

机器学习代码基础（1）--Python速成【代码】

Python相关机器学习

菜鸟入门_Python_机器学习（4）_PCA和MDA降维和聚类【代码】【图】

吴裕雄 python 机器学习——数据预处理字典学习模型【代码】【图】

NBC朴素贝叶斯分类器 ————机器学习实战 python代码【代码】

吴裕雄 python 机器学习——集成学习梯度提升决策树GradientBoostingClassifier分类模型【代码】【图】

可能是史上最全的机器学习和Python（包括数学）速查表【图】

机器学习经典算法详解及Python实现--CART分类决策树、回归树和模型树【图】

python学习之机器学习【图】

Python机器学习（三十四）Numpy 介绍

吴裕雄 python 机器学习-DMT（1）【代码】【图】

机器学习之路: python 回归树 DecisionTreeRegressor 预测波士顿房价【代码】

机器学习 - 相关标签

PYTHON - 技术教程分类

PYTHON - 最新教程

PYTHON - 最热教程