机器学习实战（kNN）
概述
k-近邻算法采用测量不同特征值之间的距离方法进行分类。
- 优点：精度高、对异常值不敏感、无数据输入假定
- 缺点：计算复杂度高、空间复杂度高
- 适用数据范围：数值型和标称型
工作原理
存在一个一个数据集合，也称训练数据集，并且每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，选择前k（通常k是不大于20的整数）个最相似（最邻近）的数据。在这些数据中取出现次数最多的分类。
- '''''
- kNN算法核心分类函数
- 这里距离使用的是欧式距离sqrt((a1-b1)**2 + (a2-b2)**2 + ... + (an-bn)**2)
- 参数：
- inX：用于分类的输入向量
- dataSet：训练集样本
- labels：标签向量
- k：选择最近邻居的数目
- '''
- def classify0(inX,dataSet,labels,k):
- dataSetSize = np.size(dataSet,axis=0) #数据集样本数目
- diffMat = np.tile(inX,(dataSetSize,1)) - dataSet #tile函数构建dataSet同样规格的矩阵，输入向量的各个特征减去训练集中对应特征
- sqDiffMat = diffMat**2 #计算输入向量与训练集中各个样本的距离
- sqDistances = np.sum(sqDiffMat,axis=1) #把每一列的矩阵相加
- sortedIndicies = np.argsort(sqDistances) #按照距离升序，新矩阵显示的是在之前矩阵的距离
- classCount = {} #存储k个最近邻居的标签及数目
- for i in range(k): #找到k个最近邻居并存储
- voteILabel = labels[sortedIndicies[i]]
- classCount[voteILabel] = classCount.get(voteILabel,0) + 1
- sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #对value降序排序，返回一个数组
- return sortedClassCount[0][0] #预测的分类
使用k-近邻算法改进约会网站的配对效果
- import numpy as np
- import operator
- import matplotlib
- import matplotlib.pyplot as plt
- '''''
- 将文本记录转换为numpy矩阵
- 参数：
- filename：文件路径
- '''
- def file2matrix(filename):
- fr = open(filename) #打开文件
- arrayOLines = fr.readlines() #读取文件
- numberOfLines = len(arrayOLines) #获取文件行数
- returnMat = np.zeros((numberOfLines,3)) #构造行数=文本行数，列数=特征数的numpy零矩阵
- classLabelVector = [] #存储文本中每个样本对应分类标签
- index = 0 #索引，用于调到下一行进行赋值
- for line in arrayOLines:
- line = line.strip() #截取所有回车字符
- listFromLine = line.split('\t') #使用tab字符'\t'将上一步得到的整行数据分割成一个元素列表
- returnMat[index,:] = listFromLine[0:3] #选取前三个字符将他们存储到特征矩阵中
- classLabelVector.append(int(listFromLine[-1])) #将文本中的最后一列(列表标签)单独存储到一个列表中
- index += 1
- return returnMat,classLabelVector #返回一个特征矩阵和标签列表
- '''''
- 归一化特征值
- dataSet：训练集样本(特征矩阵)
- newValue = (oldValue - min)/(maxValue - minValue)
- '''
- def autoNorm(dataSet):
- minVals = np.min(dataSet,axis=0) #每一列的最小值
- maxVals = np.max(dataSet,axis=0) #每一列的最大值
- ranges = maxVals - minVals #每一列的取值范围
- normDataSet = np.zeros(np.shape(dataSet)) #构造一个新的dataSet大小的numpy零矩阵
- m = np.size(dataSet,axis=0) #取dataSet行数
- normDataSet = dataSet - np.tile(minVals,(m,1)) #按照公式进行归一化
- normDataSet = normDataSet/np.tile(ranges,(m,1))
- return normDataSet,ranges,minVals #归一化后的特征矩阵，取值范围，训练集每一列的最小值'''
- 分类器针对约会网站的测试函数
- 取训练集的前10%样本作为测试集
- '''
- def datingClassTest():
- hoRatio = 0.10
- datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
- normMat,ranges,minVals = autoNorm(datingDataMat)
- m = np.size(normMat,axis=0)
- numTestVecs = int(hoRatio*m)
- 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)))
- '''''
- 约会网站预测函数
- '''
- def classifyPerson():
- resultList = ["not at all","in small does","in large does"]
- percentTats = float(input("percentage of time spent playing video games?"))
- ffMiles = float(input("frequent flier miles earned per year?"))
- iceCream = float(input("liters of ice cream consumes per year?"))
- datingDataMat,datingLabels = file2matrix("datingTestSet2.txt")
- normMat,ranges,minVals = autoNorm(datingDataMat)
- inArr = np.array([ffMiles,percentTats,iceCream])
- classifierResult = classify0(((inArr-minVals)/ranges),datingDataMat,datingLabels,3)
- print("You will probably like this person:",resultList[classifierResult - 1])
结果(部分)
- The classifier came back with:3,the real answer is:3
- The classifier came back with:2,the real answer is:2
- The classifier came back with:1,the real answer is:1
- The classifier came back with:1,the real answer is:1
- The classifier came back with:1,the real answer is:1
- The classifier came back with:1,the real answer is:1
- The classifier came back with:3,the real answer is:3
- The classifier came back with:1,the real answer is:1
- The classifier came back with:3,the real answer is:3
- The classifier came back with:3,the real answer is:3
- The classifier came back with:2,the real answer is:2
- The classifier came back with:1,the real answer is:1
- The classifier came back with:3,the real answer is:1
- the total error rate is:0.050000
- percentage of time spent playing video games?10
- frequent flier miles earned per year?10000
- liters of ice cream consumes per year?0.5
- You will probably like this person: in small does
手写数字识别
- import numpy as np
- import os
- import operator
- '''''
- 将32*32的黑白图像转换成1*1024的向量
- 参数：
- filename：文件路径
- '''
- def img2vector(filename):
- returnVect = np.zeros((1,1024)) #构造1*1024的numpy零矩阵
- fr = open(filename) #打开文件
- for i in range(32): #循环读取每一个像素点(字符)，转换为1*1024的向量
- lineStr = fr.readline()
- for j in range(32):
- returnVect[0,32*i+j] = int(lineStr[j])
- return returnVect
- '''''
- 手写数字识别系统的测试函数
- 每一个样本为单个文件，统一存在训练集文件夹下
- '''
- def handwritingClassTest():
- hwLabels = [] #存储手写数字分类标签的列表
- trainingFileList = os.listdir('trainingDigits') #进入训练集目录
- m = len(trainingFileList) #统计训练样本数目
- trainingMat = np.zeros((m,1024)) #构造m*1024numpy零矩阵，为了将所有训练样本转换成二维矩阵进行计算
- for i in range(m): #将所有训练样本转换成m*1024的numpy矩阵
- fileNameStr = trainingFileList[i] #样本名称
- fileStr = fileNameStr.split('.')[0] #获取样本对应类别标签
- classNumStr = int(fileStr.split('_')[0])
- hwLabels.append(classNumStr)
- trainingMat[i, :] = img2vector('trainingDigits/' + fileNameStr) #将32*32的黑白图像转换成1*1024的向量
- testFileList = os.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) #将32*32的黑白图像转换成1*1024的向量
- prediction = classify0(vectorUnderTest,trainingMat,hwLabels,3) #预测手写数字
- print("the classifier came back with: %d,the real answer is:%d" % (prediction,classNumStr))
- if classNumStr != prediction:
- errorCount += 1
- print("\nthe total number of errors is:%d" % errorCount) #预测错误次数
- print("\nthe total error rate is:%f" % (errorCount/float(mTest))) #预测错误率
结果(部分)
- the classifier came back with: 9,the real answer is:9
- the classifier came back with: 9,the real answer is:9
- the classifier came back with: 9,the real answer is:9
- the classifier came back with: 9,the real answer is:9
- 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:10
- the total error rate is:0.010571
实际使用这个算法时，时间复杂度和空间复杂度相当高， 因此执行效率并不高。此外还需要为向量准备2MB的存储空间。为了解决存储空间和计算时间的开销，可以引入k决策树，可以节省大量的计算开销。
小结
knn是分类数据最简单有效的算法。knn是基于实例的学习，使用算法时必须有接近实际数据的训练样本数据。knn必须保存全部数据集，如果训练数据集很大，则须使用大量存储空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时。
knn另一个缺陷是无法给出任何数据的基础结构信息，因此也无法知晓平均实例样本和典型实例样本具有什么特征。knn
