关键词:
第2章 k-近邻算法
KNN 概述
k-近邻(kNN, k-NearestNeighbor)算法主要是用来进行分类的.
KNN 场景
电影可以按照题材分类,那么如何区分 动作片
和 爱情片
呢?
- 动作片:打斗次数更多
- 爱情片:亲吻次数更多
基于电影中的亲吻、打斗出现的次数,使用 k-近邻算法构造程序,就可以自动划分电影的题材类型。
现在根据上面我们得到的样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到 k 个距离最近的电影。
假定 k=3,则三个最靠近的电影依次是, He‘s Not Really into Dudes 、 Beautiful Woman 和 California Man。
knn 算法按照距离最近的三部电影的类型,决定未知电影的类型,而这三部电影全是爱情片,因此我们判定未知电影是爱情片。
KNN 原理
KNN 工作原理
- 假设有一个带有标签的样本数据集(训练样本集),其中包含每条数据与所属分类的对应关系。
- 输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较。
- 计算新数据与样本数据集中每条数据的距离。
- 对求得的所有距离进行排序(从小到大,越小表示越相似)。
- 取前 k (k 一般小于等于 20 )个样本数据对应的分类标签。
- 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 开发流程
收集数据:任何方法
准备数据:距离计算所需要的数值,最好是结构化的数据格式
分析数据:任何方法
训练算法:此步骤不适用于 k-近邻算法
测试算法:计算错误率
使用算法:输入样本数据和结构化的输出结果,然后运行 k-近邻算法判断输入数据分类属于哪个分类,最后对计算出的分类执行后续处理
KNN 算法特点
优点:精度高、对异常值不敏感、无数据输入假定
缺点:计算复杂度高、空间复杂度高
适用数据范围:数值型和标称型
KNN 项目案例
项目案例1: 优化约会网站的配对效果
项目概述
海伦使用约会网站寻找约会对象。经过一段时间之后,她发现曾交往过三种类型的人:
- 不喜欢的人
- 魅力一般的人
- 极具魅力的人
她希望:
- 工作日与魅力一般的人约会
- 周末与极具魅力的人约会
- 不喜欢的人则直接排除掉
现在她收集到了一些约会网站未曾记录的数据信息,这更有助于匹配对象的归类。
开发流程
收集数据:提供文本文件
准备数据:使用 Python 解析文本文件
分析数据:使用 Matplotlib 画二维散点图
训练算法:此步骤不适用于 k-近邻算法
测试算法:使用海伦提供的部分数据作为测试样本。
测试样本和非测试样本的区别在于:
测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。
使用算法:产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。
收集数据:提供文本文件
海伦把这些约会对象的数据存放在文本文件 datingTestSet2.txt 中,总共有 1000 行。海伦约会的对象主要包含以下 3 种特征:
- 每年获得的飞行常客里程数
- 玩视频游戏所耗时间百分比
- 每周消费的冰淇淋公升数
文本文件数据格式如下:
40920 8.326976 0.953952 3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
准备数据:使用 Python 解析文本文件
将文本记录转换为 NumPy 的解析程序
def file2matrix(filename):
"""
Desc:
导入训练数据
parameters:
filename: 数据文件路径
return:
数据矩阵 returnMat 和对应的类别 classLabelVector
"""
fr = open(filename)
# 获得文件中的数据行的行数
numberOfLines = len(fr.readlines())
# 生成对应的空矩阵
# 例如:zeros(2,3)就是生成一个 2*3的矩阵,各个位置上全是 0
returnMat = zeros((numberOfLines, 3)) # prepare matrix to return
classLabelVector = [] # prepare labels return
fr = open(filename)
index = 0
for line in fr.readlines():
# str.strip([chars]) --返回移除字符串头尾指定的字符生成的新字符串
line = line.strip()
# 以 ‘ ‘ 切割字符串
listFromLine = line.split(‘ ‘)
# 每列的属性数据
returnMat[index, :] = listFromLine[0:3]
# 每列的类别数据,就是 label 标签数据
classLabelVector.append(int(listFromLine[-1]))
index += 1
# 返回数据矩阵returnMat和对应的类别classLabelVector
return returnMat, classLabelVector
分析数据:使用 Matplotlib 画二维散点图
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels))
plt.show()
下图中采用矩阵的第一和第三列属性得到很好的展示效果,清晰地标识了三个不同的样本分类区域,具有不同爱好的人其类别区域也不同。
- 归一化数据 (归一化是一个让权重变为统一的过程,更多细节请参考: https://www.zhihu.com/question/19951858)
序号 | 玩视频游戏所耗时间百分比 | 每年获得的飞行常客里程数 | 每周消费的冰淇淋公升数 | 样本分类 |
---|---|---|---|---|
1 | 0.8 | 400 | 0.5 | 1 |
2 | 12 | 134 000 | 0.9 | 3 |
3 | 0 | 20 000 | 1.1 | 2 |
4 | 67 | 32 000 | 0.1 | 2 |
样本3和样本4的距离: $$sqrt{(0-67)^2 + (20000-32000)^2 + (1.1-0.1)^2 }$$
归一化特征值,消除特征之间量级不同导致的影响
def autoNorm(dataSet):
"""
Desc:
归一化特征值,消除特征之间量级不同导致的影响
parameter:
dataSet: 数据集
return:
归一化后的数据集 normDataSet. ranges和minVals即最小值与范围,并没有用到
归一化公式:
Y = (X-Xmin)/(Xmax-Xmin)
其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
"""
# 计算每种属性的最大值、最小值、范围
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
# 极差
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
# 生成与最小值之差组成的矩阵
normDataSet = dataSet - tile(minVals, (m, 1))
# 将最小值之差除以范围组成矩阵
normDataSet = normDataSet / tile(ranges, (m, 1)) # element wise divide
return normDataSet, ranges, minVals
训练算法:此步骤不适用于 k-近邻算法
因为测试数据每一次都要与全量的训练数据进行比较,所以这个过程是没有必要的。
测试算法:使用海伦提供的部分数据作为测试样本。如果预测分类与实际类别不同,则标记为一个错误。
kNN 分类器针对约会网站的测试代码
def datingClassTest():
"""
Desc:
对约会网站的测试方法
parameters:
none
return:
错误数
"""
# 设置测试数据的的一个比例(训练数据集比例=1-hoRatio)
hoRatio = 0.1 # 测试范围,一部分测试一部分作为样本
# 从文件中加载数据
datingDataMat, datingLabels = file2matrix(‘input/2.KNN/datingTestSet2.txt‘) # load data setfrom file
# 归一化数据
normMat, ranges, minVals = autoNorm(datingDataMat)
# m 表示数据的行数,即矩阵的第一维
m = normMat.shape[0]
# 设置测试的样本数量, numTestVecs:m表示训练样本的数量
numTestVecs = int(m * hoRatio)
print ‘numTestVecs=‘, numTestVecs
errorCount = 0.0
for i in range(numTestVecs):
# 对数据测试
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if (classifierResult != datingLabels[i]): errorCount += 1.0
print "the total error rate is: %f" % (errorCount / float(numTestVecs))
print errorCount
使用算法:产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。
约会网站预测函数
def clasdifyPerson():
resultList = [‘not at all‘, ‘in small doses‘, ‘in large doses‘]
percentTats = float(raw_input("percentage of time spent playing video games ?"))
ffMiles = float(raw_input("frequent filer miles earned per year?"))
iceCream = float(raw_input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix(‘datingTestSet2.txt‘)
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([ffMils, percentTats, iceCream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels, 3)
print "You will probably like this person: ", resultList[classifierResult - 1]
实际运行效果如下:
>>> kNN.classifyPerson()
percentage of time spent playing video games?10
frequent flier miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person: in small doses
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/2.KNN/kNN.py
项目案例2: 手写数字识别系统
项目概述
构造一个能识别数字 0 到 9 的基于 KNN 分类器的手写数字识别系统。
需要识别的数字是存储在文本文件中的具有相同的色彩和大小:宽高是 32 像素 * 32 像素的黑白图像。
开发流程
收集数据:提供文本文件。
准备数据:编写函数 img2vector(), 将图像格式转换为分类器使用的向量格式
分析数据:在 Python 命令提示符中检查数据,确保它符合要求
训练算法:此步骤不适用于 KNN
测试算法:编写函数使用提供的部分数据集作为测试样本,测试样本与非测试样本的
区别在于测试样本是已经完成分类的数据,如果预测分类与实际类别不同,
则标记为一个错误
使用算法:本例没有完成此步骤,若你感兴趣可以构建完整的应用程序,从图像中提取
数字,并完成数字识别,美国的邮件分拣系统就是一个实际运行的类似系统
收集数据: 提供文本文件
目录 trainingDigits 中包含了大约 2000 个例子,每个例子内容如下图所示,每个数字大约有 200 个样本;目录 testDigits 中包含了大约 900 个测试数据。
准备数据: 编写函数 img2vector(), 将图像文本数据转换为分类器使用的向量
将图像文本数据转换为向量
def img2vector(filename):
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readLine()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
分析数据:在 Python 命令提示符中检查数据,确保它符合要求
在 Python 命令行中输入下列命令测试 img2vector 函数,然后与文本编辑器打开的文件进行比较:
>>> testVector = kNN.img2vector(‘testDigits/0_13.txt‘)
>>> testVector[0,0:31]
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])
>>> testVector[0,31:63]
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])
训练算法:此步骤不适用于 KNN
因为测试数据每一次都要与全量的训练数据进行比较,所以这个过程是没有必要的。
测试算法:编写函数使用提供的部分数据集作为测试样本,如果预测分类与实际类别不同,则标记为一个错误
def handwritingClassTest():
# 1. 导入训练数据
hwLabels = []
trainingFileList = listdir(‘input/2.KNN/trainingDigits‘) # load the training set
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
# hwLabels存储0~9对应的index位置, trainingMat存放的每个位置对应的图片向量
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split(‘.‘)[0] # take off .txt
classNumStr = int(fileStr.split(‘_‘)[0])
hwLabels.append(classNumStr)
# 将 32*32的矩阵->1*1024的矩阵
trainingMat[i, :] = img2vector(‘input/2.KNN/trainingDigits/%s‘ % fileNameStr)
# 2. 导入测试数据
testFileList = listdir(‘input/2.KNN/testDigits‘) # iterate through the test set
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split(‘.‘)[0] # take off .txt
classNumStr = int(fileStr.split(‘_‘)[0])
vectorUnderTest = img2vector(‘input/2.KNN/testDigits/%s‘ % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr)
if (classifierResult != classNumStr): errorCount += 1.0
print "
the total number of errors is: %d" % errorCount
print "
the total error rate is: %f" % (errorCount / float(mTest))
使用算法:本例没有完成此步骤,若你感兴趣可以构建完整的应用程序,从图像中提取数字,并完成数字识别,美国的邮件分拣系统就是一个实际运行的类似系统
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/2.KNN/kNN.py
- 作者:羊三 小瑶
- GitHub地址: https://github.com/apachecn/MachineLearning
- 版权声明:欢迎转载学习 => 请标注信息来源于 ApacheCN
《机器学习实战》之k-近邻算法
看了这本书的第一个算法—k-近邻算法,这个算法总体构造思想是比较简单的,在ACM当中的话就对应了kd树这种结构。首先需要给定训练集,然后给出测试数据,求出训练集中与测试数据最相近的k个数据,根据这k个数据的属... 查看详情
《机器学习实战》之k-近邻算法(手写识别系统)
这个玩意和改进约会网站的那个差不多,它是提前把所有数字转换成了32*32像素大小的黑白图,然后转换成字符图(用0,1表示),将所有1024个像素点用一维矩阵保存下来,这样就可以通过knn计算欧几里得距离来得到最接近的答案... 查看详情
机器学习实战——k-近邻算法(代码片段)
...去看看KNN了,然后我给你安排一个工作!我:好嘞!就是第二章吗?老板:对!去吧!可恶的老板又给我安排任务了!《机器学习实战》这本书中的第二章为我们介绍了K-近邻算法,这是本书中第一个机器学习算法,它非常有效... 查看详情
机器学习实战-第二章-k-近邻算法
时间:2021.11.02下午14:22开始记将文件转换为矩阵格式的代码:#deffile2Matrix(filename):# fr=open(filename)# arrayOLines=fr.readlines()# numberOLines=len(arrayOLines)# returnMat=zeros((numberOLines,3))# classLabel... 查看详情
机器学习实战之k近邻算法
k近邻算法概述简单地说,K近邻算法采用测量不同特征值之间的距离方法进行分类。优点:精度高、对异常值不敏感、无数据输入假定。缺点:计算复杂度高、空间复杂度高。适用数据范围:数值型和标称型。它的工作原理是:存在一... 查看详情
361机器学习常见算法
K-近邻算法(KNearestNeighbors)参考:机器学习实战教程(一):K-近邻算法(史诗级干货长文)决策树算法(DecisionTree)参考:机器学习实战教程(二):决策树基础篇之让我们从相亲说起参考:机器学习实战教程(三):决策树... 查看详情
《机器学习实战》-k近邻算法(代码片段)
目录K-近邻算法k-近邻算法概述解析和导入数据使用Python导入数据实施kNN分类算法测试分类器使用k-近邻算法改进约会网站的配对效果收集数据准备数据:使用Python解析文本文件分析数据:使用Matplotlib画二维散点图准备数据:归... 查看详情
机器学习实战k-近邻算法
...tp://www.cnblogs.com/lighten/p/7593656.html 1.原理 本章介绍机器学习实战的第一个算法——k近邻算法(k NearestNeighbor),也称为kNN。说到机器学习,一般都认为是很复杂,很高深的内容,但实际上其学习门栏并不算高,具备基... 查看详情
《机器学习实战》之k-近邻算法(改进约会网站的配对效果)
示例背景:我的朋友海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选,但她并不是喜欢每一个人。经过一番总结,她发现曾交往过三种类型的人:(1)不喜欢的人;(2)魅力一般的人;(3... 查看详情
machinelearninginaction机器学习——第二章k-近邻算法代码详解(代码片段)
一、近邻算法的定义与作用也就是意义k-近邻算法,近邻算法近邻算法顾名思义,找到最近的点然后进行归纳,距离哪些点最近这个点就属于那个类。这和线性回归算法有异曲同工之妙,但是我感觉还是一元线性... 查看详情
机器学习实战☛k-近邻算法(k-nearestneighbor,knn)(代码片段)
机器学习实战☛k-近邻算法(K-NearestNeighbor,KNN)文章目录机器学习实战☛k-近邻算法(K-NearestNeighbor,KNN)k-近邻算法概述原理简介k-近邻算法一般流程伪代码与实现示例:使用kNN改进约会网站的配对效... 查看详情
《机器学习实战》学习笔记——k近邻算法
1.numpy中一些函数的用法学习shape()用法:shape :tupleofintsTheelementsoftheshapetuplegivethelengthsofthecorrespondingarraydimensions.。 shape返回一个元组,依次为各维度的长度。shape[0]:第一维长度,shape[1]:第二维长度。 tile()用法:numpy.tile 查看详情
机器学习实战笔记--k近邻算法
1#encoding:utf-82fromnumpyimport*3importoperator4importmatplotlib5importmatplotlib.pyplotasplt67fromosimportlistdir89defmakePhoto(returnMat,classLabelVector):#创建散点图10fig=plt.figure()11ax=fig.add_subpl 查看详情
《机器学习实战》读书笔记2:k-近邻(knn)算法
声明:文章是读书笔记,所以必然有大部分内容出自《机器学习实战》。外加个人的理解,另外修改了部分代码,并添加了注释1、什么是K-近邻算法?简单地说,k-近邻算法采用测量不同特征值之间距离的方法进行分类。不恰当... 查看详情
机器学习实战精读--------k-近邻算法
对机器学习实战的课本和代码进行精读,帮助自己进步。#coding:utf-8from numpy import *import operator #运算符模块from os import listdir #os.listdir() 方法用于返回指定的文件夹包含的文件或文件夹的名字... 查看详情
机器学习实战k-近邻算法实施knn分类算法
2.预测数据分类时,出现‘dict’objecthasnoattribute‘iteritems‘如: 最常见的解决办法是更改环境变量顺序如 注意:哪个版本在上面,cmd中的python版本即是谁。如又如: 然后预测数据所在分类即可实现: 查看详情
机器学习实战task1(knn)k近邻算法的应用(代码片段)
...算法的简介k-近邻算法是属于一个非常有效且易于掌握的机器学习算法,简单的说就是采用测量不同特征值之间距离的方法对数据进行分类的一个算法。(2)k近邻算法的工作原理给定一个样本的集合,这里称为训... 查看详情
机器学习实战ch02:k-近邻算法
k-近邻算法算是一个非常暴力也非常好理解的算法(抽象来讲,就是和谁长得像就分为哪一类如何划分长得像还是不像的尺度?把特征值当做坐标,把个体当做线性空间中的离散点,取k个离目标最近的训练集点,进行labelvote,少... 查看详情