请选择 进入手机版 | 继续访问电脑版

石家庄老站长

点击联系客服
客服QQ: 客服微信:
 找回密码
 立即注册
查看: 12|回复: 1

[机器学习实战task1] (KNN) k近邻算法的应用

[复制链接]

1

主题

1

帖子

-7

积分

限制会员

积分
-7
发表于 2021-9-21 14:30:59 | 显示全部楼层 |阅读模式
1 背景

1.1 k近邻算法的概述

(1)k最近折叠算法简介

K近邻算法是一种非常有效、容易理解的机器学习算法,简单地说,是一种用测量不同特征值之间距离的方法对数据进行分类的算法。

(2)k近邻算法的工作原理

给定样品的集合,其中称为训练集,样品中的每个数据都包含标签。对于没有标签的新输入数据,计算此新数据和每个样本之间的距离,选择前K个,通常是K小于20。使用K个剧中最近一次出现在数据标签上的标签作为新添加的数据标签。

(3)k近邻算法的实例

统计了目前与6部电影接吻搏斗的场面数量。假设有没有看过的电影,如何确认是爱情片还是动作片?

电影名称打架镜头接吻镜头电影类型California  Man3104爱情片He's  Not  Really  into  Dudes2100爱情片Beautiful  Woman181爱情片Kevin  Longblade10110动作片Robo  Slayer  3000995动作片amped  ii  95 1890

以加利福尼亚城域网为例
>>>((3-18)**2+(104-90)**2)**(1/2)
20.518284528683193
电影名称与未知i电影之间的距离
California Man20.5
He‘s Not Really into Dudes18.7
Beautiful Woman19.2
Kevin Longblade115.3
Robo Slayer 3000117.4
Amped II118.9

因此我们可以找到样本中前k个距离最近的电影,假设k=3,前三部电影均为爱情片,因此我们判定未知电影属于爱情片。

1.2 用python代码实现k近邻算法
(1)计算已知类别数据集中的每个点与当前点之间的距离

(2)按照距离递增次序排序

(3)选取与当前点距离最小的k个点

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

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

import numpy as np
import operator
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}         
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
(6)案例

>>>group = np.array([[1, 1.1],
...                 [1, 1],
...                 [0, 0],
...                 [0, 0.1]])
>>>labels = ['A', 'A', 'B', 'B']
>>>classify0([0,0], group, labels, 3)
'B'

1.3 如何测试分类器
正常来说为了测试分类器给出来的分类效果,我们通常采用计算分类器的错误率对分类器的效果进行评判。也就是采用分类出错的次数除以分类的总次数。完美的分类器的错误率为0,而最差的分类器的错误率则为1。

2 使用kNN算法改进约会网站的匹配效果
2.1 案例介绍
朋友海伦在使用约会软件寻找约会对象的时候,尽管网站会推荐不同的人选,但并不是每一个人她都喜欢,具体可以分为以下三类:不喜欢的人,魅力一般的人,极具魅力的人。尽管发现了以上的规律,但是海伦依旧无法将网站推荐的人归到恰当的类别,因此海伦希望我们的分类软件能更好的帮助她将匹配到的对象分配到确切的分类中。

2.2 数据的准备
以下提供两种下载数据集的渠道:

《机器学习实战官方下载python2版本代码》

《202xxx的github下载python3版本代码》

数据存放在datingTestSet2.txt中,每个样本占一行,共1000行数据,主要包括了以下三个特征:

每年获得的飞行常客里程数,玩视频游戏所耗时间百分比,每周消费冰淇淋公升数

在数据输入到分类器之前,需要把数据转换成分类器可以识别的样式

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = np.zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector
使用file2matix读取到的特征数据(datingDataMat)如下

array([[4.0920000e+04, 8.3269760e+00, 9.5395200e-01],
        [1.4488000e+04, 7.1534690e+00, 1.6739040e+00],
        [2.6052000e+04, 1.4418710e+00, 8.0512400e-01],
        ...,
        [2.6575000e+04, 1.0650102e+01, 8.6662700e-01],
        [4.8111000e+04, 9.1345280e+00, 7.2804500e-01],
        [4.3757000e+04, 7.8826010e+00, 1.3324460e+00]]
标签数据(datingLabels)如下

[3,2,1,1,1,1,3,3,...,3,3,3]
2.3 数据分析:使用Matplotlib创建散点图
(1)玩视频游戏所耗时间百分比与每周消费冰淇淋公升数之间的相关关系图

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))
plt.show()
其中,y轴为每周消费冰淇淋公升数,x轴为玩视频游戏所耗时间百分比

紫色为不喜欢,绿色为魅力一般,黄色为极具魅力



(2)飞行常客里程数与玩视频游戏所耗时间百分比之间的相关关系图

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))
plt.show()
其中,y轴为玩视频游戏所耗时间百分比,x轴为飞行常客里程数

紫色为不喜欢,绿色为魅力一般,黄色为极具魅力



(3)飞行常客里程数与每周消费冰淇淋公升数之间的相关关系图

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0], datingDataMat[:,2], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))
plt.show()
其中,y轴为每周消费冰淇淋公升数,x轴为飞行常客里程数

紫色为不喜欢,绿色为魅力一般,黄色为极具魅力



2.4 数据准备:归一化数值
由于通过欧式距离计算样本之间的距离时,对于飞行常客里程数来说,数量值巨大,会对结果影响的权重也会较大,而且远远大于其他两个特征,但是作为三个等权重之一,飞行常客里程数并不应该如此严重影响结果,例子如下

((0-67)**2+(20000-32000)**2+(1.1-0.1)**2)**1/2
玩视频游戏所耗时间百分比飞行常客里程数每周消费冰淇淋公升数样本分类
10.84000.51
2121340000.93
30200001.12
467320000.12

通常我们在处理不同取值范围的特征时,常常采用归一化进行处理,将特征值映射到0-1或者-1到1之间,通过对(列中所有值-列中最小值)/(列中最大值-列中最小值)进行归一化特征

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m,1))
    normDataSet = normDataSet/np.tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals
2.5 测试算法:作为完整程序验证分类器
评估正确率是机器学习算法中非常重要的一个步骤,通常我们会只使用训练样本的90%用来训练分类器,剩下的10%用于测试分类器的正确率。为了不影响数据的随机性,我们需要随机选择10%数据。

(1)使用file2matrix函数导入数据样本

(2)使用autoNorm对数据进行归一化处理

(3)使用classify0对90%的数据进行训练,对10%的数据进行测试

(4)输出测试集中的错误率

def datingClassTest():
    hoRatio = 0.50      #hold out 10%
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    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))
        if (classifierResult != datingLabels): errorCount += 1.0
    print ("the total error rate is: %f" % (errorCount/float(numTestVecs)))
    print (errorCount)
最后得到分类器处理的约会数据集的错误率为2.4%,这是一个相当不错的结果,同样我们可以改变hoRatio的值,和k的值,检测错误率是否随着变量的变化而增加

2.5 使用算法:构建完整可用的系统
通过上面的学习,我们尝试给海伦开发一套程序,通过在约会网站找到某个人的信息,输入到程序中,程序会给出海伦对对方的喜欢程度的预测值:不喜欢,魅力一般,极具魅力

import numpy as np
import operator
def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = np.zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m,1))
    normDataSet = normDataSet/np.tile(ranges, (m,1))   #element wise divide
    return normDataSet, ranges, minVals
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()     
    classCount={}         
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
def classifyPerson():
    resultList = ["not at all", "in small doses", "in large doses"]
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("ferquent fiter miles earned per year?"))
    iceCream = float(input("liters of ice ice crean consumed per year?"))
    datingDataMat,datingLabels = file2matrix('knn/datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([percentTats, ffMiles, iceCream])
    classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels,3)
    print ("You will probably like this person:", resultList[classifierResult-1])
if __name__ == "__main__":
    classifyPerson()#10    10000    0.5
输入测试数据:

percentage of time spent playing video games?10
ferquent fiter miles earned per year?10000
liters of ice ice crean consumed per year?0.5
You will probably like this person: not at all
3 使用kNN算法制作手写识别系统
3.1 案例介绍
以下案例以数字0-9的分类为例,简述如何采用k近邻算法对手写数字进行识别。



通常手写输入的数字都是图片格式,我们需要将图片转换成knn算法可以识别的结构化数据,简单来说就是读取图片中的像素点,像素点值通常在0-255之间,0为黑色,255为白色,因此可以将值大于250的像素点标记为1,其余标记为0,手写数字1可以用以下数据集表示:

1111111111
1111000111
1111000111
1111001111
1111001111
1111001111
1111001111
1111001111
1110000111
1111111111

3.2 数据准备:将图像转换为测试向量
以下提供两种下载数据集的渠道:

《机器学习实战官方下载python2版本代码》

《202xxx的github下载python3版本代码》

数据集存放在digits.zip中,其中用1代表手写的区域,用0代表空白区域





(大佬们,中秋快乐!!!)

通过img2vector函数对数据进行读取,并且返回数组

def img2vector(filename):
    returnVect = np.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
3.3 测试算法,使用kNN识别手写数字
(1)使用listdir读取trainingDigits目录下所有文件作为训练数据

(2)使用listdir读取testDigits目录下所有文件作为测试数据

(3)将训练数据与测试数据喂入knn算法中

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')           #load the training set
    m = len(trainingFileList)
    trainingMat = np.zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('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 ("\nthe total number of errors is: %d" % errorCount)
    print ("\nthe total error rate is: %f" % (errorCount/float(mTest)))
输出训练结果,错误率为1.1628%,通过改变k值与训练样本都会使得错误率发生变化。

the classifier came back with: 7, the real answer is: 7
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 7, the real answer is: 7
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 5, the real answer is: 5
the classifier came back with: 4, the real answer is: 4
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 3, the real answer is: 3
the total number of errors is: 11
the total error rate is: 0.011628
4 总结
4.1 k-近邻算法的优缺点
(1)优点:精度高,对异常值不敏感,无数据输入假定

(2)缺点:计算复杂度高,空间复杂度高

适用数据范围:数值型和标称型

4.2 k-近邻算法的一般流程
(1)收集数据:可以使用任何方法

(2)准备数据:距离计算所需的数值,最好是结构化的数据格式

(3)分析数据L:可以使用任何方法

(4)训练算法:此步骤不适合与k近邻算法

(5)测试算法:计算错误率

(6)使用算法:首先需要输入样本数据和结构化的输出结果,然后运行k-近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。

4.3 k-近邻算法使用需要注意的问题
(1)数据特征之间量纲不统一时,需要对数据进行归一化处理,否则会出现大数吃小数的问题

(2)数据之间的距离计算通常采用欧式距离

(3)kNN算法中K值的选取会对结果产生较大的影响,一般k值要小于训练样本数据的平方根

(4)通常采用交叉验证法来选择最优的K值

5 Reference
《机器学习实战》
回复

使用道具 举报

0

主题

646

帖子

-629

积分

限制会员

积分
-629
发表于 2021-9-21 19:47:41 | 显示全部楼层
不错不错,很好哦
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|无图版|手机版|小黑屋|石家庄@IT精英团

GMT+8, 2021-10-18 00:27 , Processed in 0.187200 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2021 Comsenz Inc.

快速回复 返回顶部 返回列表