比尔云BierYun--阿里云最新优惠活动
阿里云优惠码丨阿里云代金券

机器学习实战(kNN)

机器学习实战(kNN)http://www.bieryun.com/2427.html

概述

k-近邻算法采用测量不同特征值之间的距离方法进行分类。

[html] view plain copy

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

工作原理

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

[python] view plain copy

  1. ”’
  2. kNN算法核心分类函数
  3. 这里距离使用的是欧式距离sqrt((a1-b1)**2 + (a2-b2)**2 + … + (an-bn)**2)
  4. 参数:
  5. inX:用于分类的输入向量
  6. dataSet:训练集样本
  7. labels:标签向量
  8. k:选择最近邻居的数目
  9. ”’
  10. def classify0(inX,dataSet,labels,k):
  11.     dataSetSize = np.size(dataSet,axis=0)               #数据集样本数目
  12.     diffMat = np.tile(inX,(dataSetSize,1)) – dataSet    #tile函数构建dataSet同样规格的矩阵,输入向量的各个特征减去训练集中对应特征
  13.     sqDiffMat = diffMat**2                              #计算输入向量与训练集中各个样本的距离
  14.     sqDistances = np.sum(sqDiffMat,axis=1)              #把每一列的矩阵相加
  15.     sortedIndicies = np.argsort(sqDistances)            #按照距离升序,新矩阵显示的是在之前矩阵的距离
  16.     classCount = {}                                     #存储k个最近邻居的标签及数目
  17.     for i in range(k):                                  #找到k个最近邻居并存储
  18.         voteILabel = labels[sortedIndicies[i]]
  19.         classCount[voteILabel] = classCount.get(voteILabel,0) + 1
  20.     sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)   #对value降序排序,返回一个数组
  21.     return sortedClassCount[0][0]      #预测的分类

使用k-近邻算法改进约会网站的配对效果

[python] view plain copy

  1. import numpy as np
  2. import operator
  3. import matplotlib
  4. import  matplotlib.pyplot as plt
  5. ”’
  6. 将文本记录转换为numpy矩阵
  7. 参数:
  8. filename:文件路径
  9. ”’
  10. def file2matrix(filename):
  11.     fr = open(filename)     #打开文件
  12.     arrayOLines = fr.readlines()        #读取文件
  13.     numberOfLines = len(arrayOLines)    #获取文件行数
  14.     returnMat = np.zeros((numberOfLines,3))     #构造行数=文本行数,列数=特征数的numpy零矩阵
  15.     classLabelVector = []       #存储文本中每个样本对应分类标签
  16.     index = 0                   #索引,用于调到下一行进行赋值
  17.     for line in arrayOLines:
  18.         line = line.strip()     #截取所有回车字符
  19.         listFromLine = line.split(‘\t’)     #使用tab字符’\t’将上一步得到的整行数据分割成一个元素列表
  20.         returnMat[index,:] = listFromLine[0:3]      #选取前三个字符将他们存储到特征矩阵中
  21.         classLabelVector.append(int(listFromLine[-1]))      #将文本中的最后一列(列表标签)单独存储到一个列表中
  22.         index += 1
  23.     return returnMat,classLabelVector       #返回一个特征矩阵和标签列表
  24. ”’
  25. 归一化特征值
  26. dataSet:训练集样本(特征矩阵)
  27. newValue = (oldValue – min)/(maxValue – minValue)
  28. ”’
  29. def autoNorm(dataSet):
  30.     minVals = np.min(dataSet,axis=0)        #每一列的最小值
  31.     maxVals = np.max(dataSet,axis=0)        #每一列的最大值
  32.     ranges = maxVals – minVals              #每一列的取值范围
  33.     normDataSet = np.zeros(np.shape(dataSet))       #构造一个新的dataSet大小的numpy零矩阵
  34.     m = np.size(dataSet,axis=0)             #取dataSet行数
  35.     normDataSet = dataSet – np.tile(minVals,(m,1))      #按照公式进行归一化
  36.     normDataSet = normDataSet/np.tile(ranges,(m,1))
  37.     return normDataSet,ranges,minVals       #归一化后的特征矩阵,取值范围,训练集每一列的最小值”’
  38. 分类器针对约会网站的测试函数
  39. 取训练集的前10%样本作为测试集
  40. def datingClassTest():
  41.     hoRatio = 0.10
  42.     datingDataMat,datingLabels = file2matrix(‘datingTestSet2.txt’)
  43.     normMat,ranges,minVals = autoNorm(datingDataMat)
  44.     m = np.size(normMat,axis=0)
  45.     numTestVecs = int(hoRatio*m)
  46.     errorCount = 0.0
  47.     for i in range(numTestVecs):
  48.         classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 3)
  49.         print(“The classifier came back with:%d,the real answer is:%d” % (classifierResult,datingLabels[i]))
  50.         if classifierResult != datingLabels[i]:
  51.             errorCount += 1.0
  52.     print(“the total error rate is:%f” % (errorCount/float(numTestVecs)))
  53. ”’
  54. 约会网站预测函数
  55. ”’
  56. def classifyPerson():
  57.     resultList = [“not at all”,“in small does”,“in large does”]
  58.     percentTats = float(input(“percentage of time spent playing video games?”))
  59.     ffMiles = float(input(“frequent flier miles earned per year?”))
  60.     iceCream = float(input(“liters of ice cream consumes per year?”))
  61.     datingDataMat,datingLabels = file2matrix(“datingTestSet2.txt”)
  62.     normMat,ranges,minVals = autoNorm(datingDataMat)
  63.     inArr = np.array([ffMiles,percentTats,iceCream])
  64.     classifierResult = classify0(((inArr-minVals)/ranges),datingDataMat,datingLabels,3)
  65.     print(“You will probably like this person:”,resultList[classifierResult – 1])

结果(部分)

[python] view plain copy

  1. The classifier came back with:3,the real answer is:3
  2. The classifier came back with:2,the real answer is:2
  3. The classifier came back with:1,the real answer is:1
  4. The classifier came back with:1,the real answer is:1
  5. The classifier came back with:1,the real answer is:1
  6. The classifier came back with:1,the real answer is:1
  7. The classifier came back with:3,the real answer is:3
  8. The classifier came back with:1,the real answer is:1
  9. The classifier came back with:3,the real answer is:3
  10. The classifier came back with:3,the real answer is:3
  11. The classifier came back with:2,the real answer is:2
  12. The classifier came back with:1,the real answer is:1
  13. The classifier came back with:3,the real answer is:1
  14. the total error rate is:0.050000
  15. percentage of time spent playing video games?10
  16. frequent flier miles earned per year?10000
  17. liters of ice cream consumes per year?0.5
  18. You will probably like this person: in small does

手写数字识别

[python] view plain copy

  1. import numpy as np
  2. import os
  3. import operator
  4. ”’
  5. 将32*32的黑白图像转换成1*1024的向量
  6. 参数:
  7. filename:文件路径
  8. ”’
  9. def img2vector(filename):
  10.     returnVect = np.zeros((1,1024))     #构造1*1024的numpy零矩阵
  11.     fr = open(filename)                 #打开文件
  12.     for i in range(32):                 #循环读取每一个像素点(字符),转换为1*1024的向量
  13.         lineStr = fr.readline()
  14.         for j in range(32):
  15.             returnVect[0,32*i+j] = int(lineStr[j])
  16.     return returnVect
  17. ”’
  18. 手写数字识别系统的测试函数
  19. 每一个样本为单个文件,统一存在训练集文件夹下
  20. ”’
  21. def handwritingClassTest():
  22.     hwLabels = []           #存储手写数字分类标签的列表
  23.     trainingFileList = os.listdir(‘trainingDigits’)     #进入训练集目录
  24.     m = len(trainingFileList)       #统计训练样本数目
  25.     trainingMat = np.zeros((m,1024))        #构造m*1024numpy零矩阵,为了将所有训练样本转换成二维矩阵进行计算
  26.     for i in range(m):      #将所有训练样本转换成m*1024的numpy矩阵
  27.         fileNameStr = trainingFileList[i]       #样本名称
  28.         fileStr = fileNameStr.split(‘.’)[0]     #获取样本对应类别标签
  29.         classNumStr = int(fileStr.split(‘_’)[0])
  30.         hwLabels.append(classNumStr)
  31.         trainingMat[i, :] = img2vector(‘trainingDigits/’ + fileNameStr)     #将32*32的黑白图像转换成1*1024的向量
  32.     testFileList =  os.listdir(‘testDigits’)        #进入训练集文件夹,得到所有测试样本列表
  33.     errorCount = 0.0        #预测错误个数
  34.     mTest = len(testFileList)       #测试样本个数
  35.     for i in range(mTest):      #每个测试集样本进行预测
  36.         fileNameStr = testFileList[i]       #测试样本名称
  37.         fileStr = fileNameStr.split(‘.’)[0]     #获取测试样本真正的类别标签
  38.         classNumStr = int(fileStr.split(‘_’)[0])
  39.         vectorUnderTest = img2vector(‘testDigits/%s’ % fileNameStr)     #将32*32的黑白图像转换成1*1024的向量
  40.         prediction = classify0(vectorUnderTest,trainingMat,hwLabels,3)      #预测手写数字
  41.         print(“the classifier came back with: %d,the real answer is:%d” % (prediction,classNumStr))
  42.         if classNumStr != prediction:
  43.             errorCount += 1
  44.     print(“\nthe total number of errors is:%d” % errorCount)        #预测错误次数
  45.     print(“\nthe total error rate is:%f” % (errorCount/float(mTest)))       #预测错误率

结果(部分)

[python] view plain copy

  1. the classifier came back with: 9,the real answer is:9
  2. the classifier came back with: 9,the real answer is:9
  3. the classifier came back with: 9,the real answer is:9
  4. the classifier came back with: 9,the real answer is:9
  5. the classifier came back with: 9,the real answer is:9
  6. the classifier came back with: 9,the real answer is:9
  7. the total number of errors is:10
  8. the total error rate is:0.010571

实际使用这个算法时,时间复杂度和空间复杂度相当高, 因此执行效率并不高。此外还需要为向量准备2MB的存储空间。为了解决存储空间和计算时间的开销,可以引入k决策树,可以节省大量的计算开销。

小结

knn是分类数据最简单有效的算法。knn是基于实例的学习,使用算法时必须有接近实际数据的训练样本数据。knn必须保存全部数据集,如果训练数据集很大,则须使用大量存储空间。此外,由于必须对数据集中的每个数据计算距离值,实际使用时可能非常耗时。

knn另一个缺陷是无法给出任何数据的基础结构信息,因此也无法知晓平均实例样本和典型实例样本具有什么特征。knn

未经允许不得转载:比尔云 » 机器学习实战(kNN)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

强烈推荐

高性能SSD云服务器ECS抗攻击,高可用云数据库RDS