k-近邻算法(KNN)详解及python实现和应用

简介: k-近邻算法(KNN)详解及python实现和应用

一、KNN算法概述


工作原理:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都纯在标签,就每一个样本都有一个标签与之对应。输入没带标签的新数据之后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签,然后给新数据该标签。我们只选择样本数据集中前k个最相似的数据,最后选择k个最相似数据中出现次数最多的分类,作为新数据的分类。


光看文字理解显然不够深刻,来看看图片。


2020100419505293.png

假定新加入了一个绿正方形,现在我们要判定它是属于三角形还是属于圆形。首先根据先看距离正方形最近的图形有哪些,根据它们离正方形的距离进行排序,再根据确定的k值进行划分,选出离目标最近的k个图形,然后判定在k个里面哪个图形占多数,占多数的则把该目标归为哪一类。


这样应该很好理解,也说明了KNN算法的结果很大程度取决于K的选择,其中K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。


二、距离度量


因为在各种不同的环境下采用knn算法,度量变量距离也有许多种不同的算法。免了对象之间的匹配问题。在KNN算法中一般采用的是欧氏距离或曼哈顿距离:


欧氏距离(二维):

20201004200432434.png

曼哈顿距离(二维):

20201004200511957.png


三、实现算法


首先算法一般流程

.收集数据->处理数据(标准化)->分析数据->训练算法->测试算法->使用算法


20201015190711128.jpg



先创建数据导入块

import numpy as np
import operator
from matplotlib import pyplot as plt
#创建数据集
def createrDataSet():
    group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

20201004220710821.png


类似这种效果,如何开始写入knn算法


20201015191020143.jpg

from numpy import *
import operator
#创建数据集
def createrDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels
ture = 1
#inX:输入向量; dataSet:训练样本集; labels:标签向量 k=最近邻居个数; 其中标签元素数目和矩阵dataSet的行数相同。
def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0] #行数
    #计算欧式距离
    diffMat = tile(inX,(dataSetSize,1))-dataSet #扩展dataSet行,分别相减,形成(x1-x2)矩阵
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()#从小到大排序,获得索引值(下标)
    #选择距离最小的k个点
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    #排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=ture)
    return sortedClassCount[0][0]

具体实现过程已经在代码中标识出来了。

我们可以通过简单的测试。

import KNN
from numpy import *
dataSet,labels = KNN.createrDataSet()
inX = array([0,0.3])
k = 3
output = KNN.classify0(inX,dataSet,labels,k)
print("测试数据为:",inX,"分类结果为:",output)

20201004221203785.png

PS.按照机器学习实战的那本来敲代码的话可能会遇到'dict' object has no attribute 'iteritems'。

原因:iteritems是为python2环境中dict的函数。在python3报错,将iteritems改为items即可。


四、实战练习


练习当然是我们的海伦约会实例,也是最常见拿来练手的例子了。


海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选,但她并不是喜欢每一个人。经过一番总结,她发现自己交往过的人可以进行如下分类:


不喜欢的人

魅力一般的人

极具魅力的人

首先准备数据,海伦收集的样本数据主要包含以下3种特征:


每年获得的飞行常客里程数

玩视频游戏所消耗时间百分比

每周消费的冰淇淋公升数


1.转换数据


将文本记录转换为Numpy解析程序

#处理数据格式
#输入文件名字符串,输出为训练样本矩阵和类标签
def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()#得到文件行数
    numberOfLines = len(arrayOLines)
    returnMat = zeros((numberOfLines,3))#得到与之对应行数,3列的0填充矩阵
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()#截取所有回车字符
        listFromLine = line.split('\t')#按tap格式分割
        returnMat[index,:] = listFromLine[0:3]#从头开始填充
        classLabelVector.append((listFromLine[-1]))#将标签保留
        index += 1
# datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
# print(datingDateMat,datingLabels)
from collections import Counter
##将列表的最后一列由字符串转化为数字,便于以后的计算
    dictClassLabel = Counter(classLabelVector)
    classLabel = []
    kind = list(dictClassLabel)
    for item in classLabelVector:
        if item == kind[0]:
            item = 1
        elif item == kind[1]:
            item = 2
        else:
            item = 3
        classLabel.append(item)
    return returnMat,classLabel#####将文本中的数据导入到列表


我们可以看到数据

20201005201650370.png

2.分析数据


我们可以使用Matplotlib创建散点图

import matplotlib
import matplotlib.pyplot as plt
#绘制散点图
fig = plt.figure()
ax = fig.add_subplot(111)#分割为1行1列第1块
ax.scatter(datingDataMat[:,1], datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()


这里对比一下‘玩视频游戏所消耗时间百分比’和‘每周消费的冰淇淋公升数’

很明显

image.png

image.png


数据还没有处理好看不出什么效果。


3.数据归一化


因为根据knn采用的为欧式距离,在数据属性权重相同的情况下,数字差值最大的属性对计算结果影响最大,所以我们必须使用数据归一化避免相比差值过大严重影响计算结果。


那么接下来我们进行数据归一化,考虑到使用Min-Max标准可能如果max和min不稳定,很容易使得归一化结果不稳定,使得后续使用效果也不稳定。所以我们采用Z-score标准化。数据预处理归一化详细解释


from sklearn.preprocessing import StandardScaler
def autoNorm(dataSet):
    sc = StandardScaler()
    normDataSet =sc.fit_transform(datingDataMat)
    mean = sc.mean_
    std = sqrt(sc.var_)
    return normDataSet,mean,std

很明显归一化的数据很易于分析:

20201005204050108.png


4.测试算法


接下来开始评估我们算法的可靠性,通常我们只提供已有数据的90%作为训练样本训练分类器,而使用其余的10%数据去测试分类器。一开始想使用线性回归的

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y,
                                                    test_size=0.1,
                                                    random_state=0)

发现只能二值计算,有点尴尬,不知道大家有什么好的方法来划分数据集,安装书上的方法属实是最原始的划分方法。

def datingClassTest():
    #将返回的特征矩阵和分类向量分别存储到datingDataMat和datingLabels中
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    #取所有数据的百分之十
    hoRatio = 0.10
    #数据归一化,返回归一化后的矩阵,数据范围,数据最小值
    normMat= autoNorm(datingDataMat)
    #获得normMat的行数
    m = normMat.shape[0]
    #百分之十的测试数据的个数
    numTestVecs = int(m * hoRatio)
    #分类错误计数
    errorCount = 0.0
    for i in range(numTestVecs):
        #前numTestVecs个数据作为测试集,后m-numTestVecs个数据作为训练集
        classifierResult = KNN.classify0(normMat[i,:], normMat[numTestVecs:m,:],
            datingLabels[numTestVecs:m], 4)
        print("分类结果:%s\t真实类别:%d" % (classifierResult, datingLabels[i]))
        if classifierResult != datingLabels[i]:
            errorCount += 1.0
    print("错误率:%f%%" % (errorCount / float(numTestVecs) * 100))

20201005205523273.png


这是没简化标签时候截的图,后面优化了一下便于计算

20201005205637187.png


5.使用算法


经过测试我们的knn算法还算不错,现在我们可以编写一个窗口来使用这个分类器了:

def classifyPerson():
    #输出结果
    resultList = ['讨厌','有些喜欢','非常喜欢']
    #三维特征用户输入
    precentTats = float(input("玩视频游戏所耗时间百分比:"))
    ffMiles = float(input("每年获得的飞行常客里程数:"))
    iceCream = float(input("每周消费的冰激淋公升数:"))
    #打开的文件名
    filename = "datingTestSet2.txt"
    #打开并处理数据
    datingDataMat, datingLabels = file2matrix(filename)
    #训练集归一化
    normMat, mean, std = autoNorm(datingDataMat)
    #生成NumPy数组,测试集
    inArr = array([ffMiles, precentTats, iceCream])
    #测试集归一化
    norminArr = (inArr - mean) / std
    #返回分类结果
    classifierResult =KNN.classify0(norminArr, normMat, datingLabels, 3)
    #打印结果
    print("你可能%s这个人" % (resultList[classifierResult-1]))
classifyPerson()

附上我理想女友的数据

20201005211253267.png


确实有点喜欢哈哈哈

20201015202712493.png


总结


具体算法应该很好理解,要使用起来也不难,很好掌握的一个算法,就是在不同的环境下要考虑该如何改进再使用。下一篇开始学习决策树了。

目录
打赏
0
0
0
0
33
分享
相关文章
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
眼疾识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了4种常见的眼疾图像数据集(白内障、糖尿病性视网膜病变、青光眼和正常眼睛) 再使用通过搭建的算法模型对数据集进行训练得到一个识别精度较高的模型,然后保存为为本地h5格式文件。最后使用Django框架搭建了一个Web网页平台可视化操作界面,实现用户上传一张眼疾图片识别其名称。
76 4
基于Python深度学习的眼疾识别系统实现~人工智能+卷积网络算法
猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
宠物识别系统使用Python和TensorFlow搭建卷积神经网络,基于37种常见猫狗数据集训练高精度模型,并保存为h5格式。通过Django框架搭建Web平台,用户上传宠物图片即可识别其名称,提供便捷的宠物识别服务。
290 55
Python图像处理实用指南:PIL库的多样化应用
本文介绍Python中PIL库在图像处理中的多样化应用,涵盖裁剪、调整大小、旋转、模糊、锐化、亮度和对比度调整、翻转、压缩及添加滤镜等操作。通过具体代码示例,展示如何轻松实现这些功能,帮助读者掌握高效图像处理技术,适用于图片美化、数据分析及机器学习等领域。
49 20
Python编程入门:从零基础到实战应用
本文是一篇面向初学者的Python编程教程,旨在帮助读者从零开始学习Python编程语言。文章首先介绍了Python的基本概念和特点,然后通过一个简单的例子展示了如何编写Python代码。接下来,文章详细介绍了Python的数据类型、变量、运算符、控制结构、函数等基本语法知识。最后,文章通过一个实战项目——制作一个简单的计算器程序,帮助读者巩固所学知识并提高编程技能。
局域网屏幕监控系统中的Python数据结构与算法实现
局域网屏幕监控系统用于实时捕获和监控局域网内多台设备的屏幕内容。本文介绍了一种基于Python双端队列(Deque)实现的滑动窗口数据缓存机制,以处理连续的屏幕帧数据流。通过固定长度的窗口,高效增删数据,确保低延迟显示和存储。该算法适用于数据压缩、异常检测等场景,保证系统在高负载下稳定运行。 本文转载自:https://www.vipshare.com
122 66
高精度保形滤波器Savitzky-Golay的数学原理、Python实现与工程应用
Savitzky-Golay滤波器是一种基于局部多项式回归的数字滤波器,广泛应用于信号处理领域。它通过线性最小二乘法拟合低阶多项式到滑动窗口中的数据点,在降噪的同时保持信号的关键特征,如峰值和谷值。本文介绍了该滤波器的原理、实现及应用,展示了其在Python中的具体实现,并分析了不同参数对滤波效果的影响。适合需要保持信号特征的应用场景。
104 11
高精度保形滤波器Savitzky-Golay的数学原理、Python实现与工程应用
Python 在企业级应用中的两大硬伤
关系数据库和SQL在企业级应用中面临诸多挑战,如复杂SQL难以移植、数据库负担重、应用间强耦合等。Python虽是替代选择,但在大数据运算和版本管理方面存在不足。SPL(esProc Structured Programming Language)作为开源语言,专门针对结构化数据计算,解决了Python的这些硬伤。它提供高效的大数据运算能力、并行处理、高性能文件存储格式(如btx、ctx),以及一致的版本管理,确保企业级应用的稳定性和高性能。此外,SPL与Java无缝集成,适合现代J2EE体系应用,简化开发并提升性能。
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
宠物识别系统,本系统使用Python作为主要开发语言,基于TensorFlow搭建卷积神经网络算法,并收集了37种常见的猫狗宠物种类数据集【'阿比西尼亚猫(Abyssinian)', '孟加拉猫(Bengal)', '暹罗猫(Birman)', '孟买猫(Bombay)', '英国短毛猫(British Shorthair)', '埃及猫(Egyptian Mau)', '缅因猫(Maine Coon)', '波斯猫(Persian)', '布偶猫(Ragdoll)', '俄罗斯蓝猫(Russian Blue)', '暹罗猫(Siamese)', '斯芬克斯猫(Sphynx)', '美国斗牛犬
193 29
【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
探秘Win11共享文件夹之Python网络通信算法实现
本文探讨了Win11共享文件夹背后的网络通信算法,重点介绍基于TCP的文件传输机制,并提供Python代码示例。Win11共享文件夹利用SMB协议实现局域网内的文件共享,通过TCP协议确保文件传输的完整性和可靠性。服务器端监听客户端连接请求,接收文件请求并分块发送文件内容;客户端则连接服务器、接收数据并保存为本地文件。文中通过Python代码详细展示了这一过程,帮助读者理解并优化文件共享系统。
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
50 5