k-近邻算法

k-近邻算法(kNN)工作原理:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,通常k是不大于20的整数。最后,选择k个最相似数据中数据出现次数最多的分类,作为新数据的分类。

优点:精度高、对异常值不敏感、无数据输入假定。
缺点:计算复杂度高、空间复杂度高。
适用数据范围:数值型和标称型

一般流程:收集数据、准备数据、分析数据、训练算法(不适用于kNN)、测试算法、使用算法。

1.1准备:使用Python导入数据

#coding=utf-8
from numpy import * #科学计算包
import operator   #运算符模块

import matplotlib
import matplotlib.pyplot as plt
from os import listdir #列出给定目录的文件名

# 创建数据集,并返回数据集和分类标签
def createDataSet():
      group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
      labels = ['A','A','B','B']
      return group,labels

结果

>>> import kNN
>>> group,labels=kNN.createDataSet()
>>> group
array([[1. , 1.1],
       [1. , 1. ],
       [0. , 0. ],
       [0. , 0.1]])
>>> labels
['A', 'A', 'B', 'B']

1.2 实施kNN分类算法

#对新数据进行分类
#inX是用于分类的输入向量,datasSet是输入的训练样本集,labels是标签向量, k表示用于选择最近邻居的数目
def classify0(inX,dataSet,labels,k):
      #查看矩阵或者数组的维数 c.shape[0] 为第一维的长度,
      #c.shape[1] 为第二维的长度,此处为4     
      dataSetSize = dataSet.shape[0]
      #(dataSetSize, 1)使数组重复完是四行一样的  而不是在1行中
      #要分类的新数据与原始数据做差
      #numpy.tile(A,reps) tile共有2个参数,A指待输入数组,reps则决定A重复的次数,整个函数用于重复数组A来构建新的数组。
      diffMat= tile(inX,(dataSetSize,1))-dataSet
      #求差的平方
      sqDiffMat = diffMat**2
      #求差的平方和
      sqDistance = sqDiffMat.sum(axis = 1)
      #求标准差
      distances = sqDistance**0.5
      #argsort是排序,将元素按照由小到大的顺序返回下标
      sortedDistIndicies = distances.argsort()
       #dict字典数据类型,字典是python中唯一内建的映射类型,定义元字典
      classCount = {}
      #遍历前k个元素
      for i in range(k):
            #获得前k个元素的标签
            voteIlabel =labels[sortedDistIndicies[i]]
            #计算前k个数据标签出现的次数
            #get是取字典里的元素,如果之前这个voteIlabel是有的,
            #那么就返回字典里这个voteIlabel里的值,如果没有就返回0(后面写的),
            #这行代码的意思就是算离目标点距离最近的k个点的类别,这个点是哪个类别哪个类别就加1
            classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
            #将classCount字典分解为元组列表,然后使用程序第三行导入运算符模块的itemgetter方法,
            #按照第二个元素的次序对元组进行排序,逆序从大到小
            sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
            #返回出现次数最多的标签
            return sortedClassCount[0][0]

结果

>>> kNN.classify0([0,0],group,labels,3)
'B'

2、使用k-近邻算法改进约会网站的配对效果
2.1准备数据:从文本文件中解析数据
将文本记录装换成NumPy的解析程序

#读取文本文件中的数据
def file2matrix(filename):
      #打开文件
      fr=open(filename)
      #计算文本文件的行数
      #arrayOLines=fr.readlines()
      numberOfLines=len(fr.readlines())
      #创建返回的数据矩阵
      returnMat=zeros((numberOfLines,3))
      #创建类标签
      classLabelVector=[]
      #打开文件
      fr=open(filename)
      #定义索引
      index=0
      #读取文件的每一行并处理
      for line in fr.readlines():
            #去除行的尾部的换行符
            line=line.strip()
            #将一行数据按空进行分割
            listFromLine=line.split('\t')
            #0:3列为数据集的数据
            returnMat[index,:]=listFromLine[0:3]
            #最后一列为数据的分类标签
            classLabelVector.append(int(listFromLine[-1]))
            #索引加1
            index += 1
            #返回数据集和对应的类标签
      return returnMat,classLabelVector

结果

>>> reload(kNN)
>>> datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')
>>> 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[0:20]
[3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3]

2.2、分析数据:使用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))
<matplotlib.collections.PathCollection object at 0x000000000C131240>
>>> plt.show()

结果
k-近邻算法
2.3准备数据:归一化数值
归一化特征值

#归一化函数
def autoNorm(dataSet):
      #求数据矩阵每一列的最小值
      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))
      #返回归一化后的数据,最大最小值差值,最小值
      return normDataSet,ranges,minVals

结果

>>> import kNN
>>> reload(kNN)
>>> normMat,ranges,minVals=kNN.autoNorm(datingDataMat)
>>> datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt')
>>> normMat,ranges,minVals=kNN.autoNorm(datingDataMat)
>>> normMat
array([[0.44832535, 0.39805139, 0.56233353],
       [0.15873259, 0.34195467, 0.98724416],
       [0.28542943, 0.06892523, 0.47449629],
       ...,
       [0.29115949, 0.50910294, 0.51079493],
       [0.52711097, 0.43665451, 0.4290048 ],
       [0.47940793, 0.3768091 , 0.78571804]])
>>> ranges
array([9.1273000e+04, 2.0919349e+01, 1.6943610e+00])
>>> minVals
array([0.      , 0.      , 0.001156])

2.4测试算法:作为完整程序验证分类器
分类器针对约会网站的测试代码

#分类器测试函数
def datingClassTest():
      #测试集所占的比例
      hoRatio=0.10
      #从文件中读取数据
      datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
      #对数据进行归一化处理
      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],2)
            #输出分类结果和实际的类别
            print "the classifer came back with: %d,the real answer is: %d" %(classifierResult,datingLabels[i])
            #如果分类结果和实际结果不一致
            if(classifierResult != datingLabels[i]):
                  #误判数目加1
                  errorCount +=1.0
      #输出错误率
      print "the total error rate is: %f" %(errorCount/float(numTestVecs))

结果

>>> kNN.datingClassTest()
the classifer came back with: 3,the real answer is: 3
the classifer came back with: 2,the real answer is: 2
the classifer came back with: 1,the real answer is: 1
the classifer came back with: 1,the real answer is: 1
the classifer came back with: 1,the real answer is: 1
the classifer came back with: 1,the real answer is: 1
the classifer came back with: 3,the real answer is: 3
the classifer came back with: 3,the real answer is: 3
the total error rate is: 0.080000

2.5使用算法构建完整系统
约会网站预测函数

#对人分类
def classiyPerson():
      #定义分类结果的类别
      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 flier 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([percentTats,percentTats,iceCream])
      #对输入数据进行分类
      classifierResult = classify0(inArr,datingDataMat,datingLabels,3)
      #输入预测的分类类别
      print "You will probably like this person:",resultList[classifierResult - 1]

结果:

>>> kNN.classiyPerson()
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

3、手写识别系统
3.1、准备数据:将图像转换成测试向量

#将单个手写字符文件变成向量
def img2vector(filename):
      #定义要返回的向量
      returnVect = zeros((1,1024))
      #打开文件
      fr = open(filename)
      #遍历文件中的每一行和每一列
      for i in range(32):
            #读取一行
            lineStr = fr.readline()
            # 对读取数据赋值到returnVect中
            for j in range(32):
                  returnVect[0,32*i+j]=int(lineStr[j])
      #返回向量
      return returnVect

结果

>>> 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.])

3.2、测试算法:使用k-近邻算法识别手写数字
手写数字识别系统的测试代码

#手写字符识别测试
def handwritingClassTest():
      # 定义手写字符标签(类别)
      hwLabels = []
      # 列出目录下所有的文件
      trainingFileList = listdir('trainingDigits')
      # 计算文件的数目
      m = len(trainingFileList)
      # 定义手写字符数据矩阵
      trainingMat = zeros((m,1024))
      # 依次读取每个文件
      for i in range(m):
            # 定义文件名
            fileNameStr = trainingFileList[i]
            # 对文件名进行分割
            fileStr = fileNameStr.split('.')[0]
            # 获得文件名中的类标签
            classNumStr = int(fileStr.split('_')[0])
            # 把类标签放到hwLabels中
            hwLabels.append(classNumStr)
            # 把文件变成向量并赋值到trainingMat中
            trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
            # 列出测试目录下的所有文件
            testFileList = listdir('testDigits')
            # 定义错误率
            errorCount = 0.0
            # 定义测试文件数目
            mTest = len(testFileList)
      # 遍历测试
      for i in range(mTest):
            # 定义测试文件名
            fileNameStr = testFileList[i]
            # 对测试文件名进行分割
            fileStr = fileNameStr.split('.')[0]
            # 获得测试文件的类标签
            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 "\nthr total error rate is:%f" % (errorCount/float(mTest))  

结果

>>> kNN.handwritingClassTest()
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:0,the real answer is 0
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:0,the real answer is 0
the classifier came back with:0,the real answer is 0
the classifier came back with:9,the real answer is 9
the classifier came back with:9,the real answer is 9

the total number of errors is:13

thr total error rate is:0.013742

小结
k-近邻算法是分类数据最简单有效的算法,是基于实例的学习,使用算法时我们必须有接近实际数据的训练样本数据,必须保存全部数据集。缺陷是无法给出任何数据的基础结构信息,无法知晓平均实例样本和典型实例样本具有什么特征。

友情提示
Pythond代码的缩进很重要,当觉得自己代码没有错误时,可以查看一下,缩进是否有错误。

机器学习实战第二章代码详解

;