K-近邻算法

1. 概念：K近邻算法采用测量不同特征值之间的距离方法进行一个分类
2. 优点：精确高、对异常值不敏感、无数据输入假定
3. 缺点：计算复杂度高、空间复杂度高
4. 适合数据范围：数值型和标称型
5. 原理：首先我们需要有一个数据样本集(我们也称作为数据训练集)，在这个训练集中的数据都是带有标签(与所属分类是一一对应的);然后将不带标签的数据与训练集中的数据的特征进行比较，使用算法提取出训练样本集中特征最相似的数据(我们往往选择训练集中的前K个，k<20)的分类标签；最后选择次数出现最好的分类标签作为这个新数据的标签。(如下图，画的不好将就一下呗)

K-近邻算法的一般流程

1. 收集数据：可以使用任何方法
2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式
3. 分析数据:可以使用任何方法
4. 训练算法:此步骤不是很适用于K近邻算法
5. 测试算法：计算错误率
6. 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理

伪代码

对未知类别属性的数据集中的每个点一次执行以下操作

1. 计算已知类别属性数据集中的点与当前点之间的距离

2. 按照距离递增次序排序

3. 选取与当前点距离最小的K个点

4. 确定前K个点所在类别的出现频率

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

代码案例

案例一

针对以上的kNN算法,我们在现实中去改进一下约会网站的配对效果

1. 收集数据：提供文本文件
2. 准备数据：使用Python解析文本文件
3. 分析数据：使用Matplotlib画二维扩散图
4. 训练算法：该步骤不适用于kNN算法
5. 测试算法：使用提供的部分数据作为测试样本（测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误）
6. 使用算法：产生简单的命令行程序，然后我们可以输入一些特征数据以判断对方是否为自己喜欢的类型

案例二

如何在人不太容易看懂的数据上使用分类器呢?
使用kNN算法的手写识别系统

1. 收集数据:提供文本文件
2. 准备数据：编写函数classify0,将图像格式转换为分类器使用的list格式
3. 分析数据：在python命令提示符中检查数据,确保它符合要求
4. 训练算法：此步骤不适用于kNN算法
5. 测试算法：编写函数使用提供的部分数据作为测试样本，测试样本与非测试样本的区别在于测试样本已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
6. 使用算法：从图像中取数字，并完成数字识别(美国的邮件分拣系统就是一个实际的类似系统)

下面给大家看看我的源码(如有错误请多多指出，大家一起进步)：

#!/usr/bin/env python3 # -*- coding: utf-8 -*-  ' a kNN module '  __author__ = 'OJ cheng'  from numpy import * #导入科学计算包 import operator # 导入运算发模块 from os import listdir  #------------------------------------华丽的分界线---------------------------------- #判断未知电影是动作片还是爱情片(根据电影中出现的接吻镜头次数和打斗镜头次数) def createDataSet(): 	group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])#NumPy中的方法,参数可以为(列表、元组或者数组) 	labels = ['A','A','B','B'] 	return group,labels   #该函数有四个参数：用于分类的输入向量inX；输入的训练样本集dataSet，标签向量labels，选择最近邻居的数目k #注意：标签向量的元素数目和矩阵dataSet的行数相同 """ 这个分类器中分别用到了NumPy库中的shape、tile、sum、argsort -shape：其实可以简单理解成显示NumPyArray的行/列(二维)、维/行/列(多维) 	x = array([[0,3],[2,1]]) 	print(x.shape) #结果为(2, 2) 二行而列 	x = zeros((2,3,4)) 	print(x.shape) #结果为(2,3,4) 二维三行两列  -sum:矩阵求和运算，其中axis指的是轴 	对于[[[ 0  1  2  3] 	  	  [ 4  5  6  7] 	      [ 8  9 10 11]] 	                       	 	  [[12 13 14 15] 	  	  [16 17 18 19] 	  	  [20 21 22 23]]  	  	] 	axis = 0 的时候，二维消失，第一维和第二维对应元素相加，结果为：  	 [ 	 	[ 		 	[12 14 16 18] 			[20 22 24 26] 		 	[28 30 32 34] 	 	] 	 ] 	axis = 1 的时候，行消失，第一维的三行元素累加，第二维同，结果为(为了表示形象)： 	 [ 	 	[ 	 		[12 15 18 21]  	 	]  	 	[ 	 		[48 51 54 57]  	 	] 	 ] 	axis = 2 的时候，列消失，第一维的三列元素累加，第二维同，结果为(为了表示形象)： 	[ 		[[  		  6  		  22       		  38 		]]  	    [[  	      54  	      70      	      86 	    ]] 	 ]  -tile:这是一个很神奇的函数，可以快速复制，tile(a,x) tile(a,(x,y)),tile(a,(x,y,z))等等 用法如下： 	a = [1 3] 	tile(a,1) 结果为：[1 3 1 3]  #这是一维数组，x=1说明将a复制一次，如果a=2就是复制两次啦 	tile(a,(2,3)) 结果为(形象表示)： 	[ 		[ 			[1 3 1 3 1 3]	 			[1 3 1 3 1 3]	#这是一个二维的1*2的矩阵，说明x=2控制行数，而y=3是控制a复制的次数啦 		] 	] 	tile(3,2,3) 结果为(形象表示)：将三维矩阵当成一个二维矩阵里面放了一个一维矩阵 	[ 		[[1 3 1 3] [1 3 1 3]] 						#这是一个三维的2*4矩阵，说明x=3控制的行数、y=2控制的是列数，而z=3表示a复制的次数 	    [[1 3 1 3] [1 3 1 3]] 	    [[1 3 1 3] [1 3 1 3]] 	] 	  -argsort：这个函数其实就是返回排序后的索引(默认从小到大)，比如： 	a = [4,3,5] #索引为：0,1,2 	a.argsort() #从小到大排序[3,4,5]对应的索引分别为：[1,0,2] 二维矩阵也是如此的  """  def classify(inX,dataSet,labels,k): 	dataSetSize = dataSet.shape[0] 	#利用欧拉公式去计算两点的距离 	diffMat = tile(inX,(dataSetSize,1)) - dataSet 	sqDiffMat = diffMat ** 2 #平方 	sqDistances = sqDiffMat.sum(axis=1) #列相加 	distances = sqDistances**0.5 #开根号 	#计算完所有点之间的距离后可以对数据进行从小到大的次序排序 	sortedDisIndicies = distances.argsort() 	#确定前k个距离最小元素所在的主要分类，其中k的值是一个正整数 	classCount = {} 	for i in range(k) : 		voteIlabel = labels[sortedDisIndicies[i]] 		classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 	#将classCount字典分解为元组列表，然后导入运算符模块的itemgetter方法，按照第二个元素的次序对元组进行排序 	#这个时候的元组排序是逆序(从大到小) 	#特别注意：python3.x后就不再支持dict的iteritems属性  所以执行sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)会报错 	sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) 	#返回发生频率最高的元素标签 	return sortedClassCount[0][0]  # group,labels = createDataSet() # print(classify([0,0],group,labels,3))  #------------------------------------------------华丽分界线------------------------------ #datingTestSet.txt中样本包括以下三种特征： 	#每年获得的飞行常客里程数 	#玩视频游戏所占时间百分比 	#每周消费的冰淇淋公升数 #第一步：将需要处理的数据格式改变为分类器可以接受的格式 def file2matrix(filename): 	fr = open(filename) 	#得到文件行数 	arrayOLines = fr.readlines()  	numberOfLines = len(arrayOLines) 	#创建返回的NumPy矩阵 	#以零填充的矩阵NumPy,将第三个纬度直接定为3 	returnMat = zeros((numberOfLines,3)) 	classLabelVector = [] 	index = 0 	#解析文件数据到列表 	for line in arrayOLines: 		#截取掉所有的回车字符 		line = line.strip() 		#使用\t分割成一个元素列表 		listFromLine = line.split('\t') 		#选择前三个元素储存到特征矩阵中 		returnMat[index,:] = listFromLine[0:3] 		#将最后一列元素储存到向量classLabelVector 		classLabelVector.append(int(listFromLine[-1])) 		index += 1 	return returnMat,classLabelVector  datingDataMat,datingLabels = file2matrix('E:\ML_Data\datingTestSet2.txt') # print(datingDataMat) #我们使用Matplotlib制作原始数据的散点图 #如果想使用reload在dos直接重新加载，python3.x后都得自己导入，from imp import reload # import matplotlib # import matplotlib.pyplot as plt # fig = plt.figure(1) # ax = fig.add_subplot(111) # #ax.scatter(datingDataMat[:,1],datingDataMat[:,2])#原始的方案没有颜色配置，无法去识别点属于哪个分类 # ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) # plt.show()  #第二步：准备数据，归一化数值 #我们认为训练集中的数据，它的三个特征应该是等同重要的，为了避免莫一个特征值明显大于其他两个特征值，我们需要归一化数值 #通常将取值范围处理为0~1或者-1~1：newValue = (oldValue - min)/(max-min) def  autoNorm(dataSet): 	#参数0时函数可以从列中选择最小值，不是当前行的最小值 	minVals = dataSet.min(0) 	maxVals = dataSet.max(0) 	ranges = maxVals - minVals 	normDataSet  = zeros(shape(dataSet)) 	#dataSet矩阵是1000*3个值，minVals和range的值都是1*3 	#使用NumPy中的tile()函数将变量内容复制成输入矩阵同样大小的矩阵 	m = dataSet.shape[0] 	normDataSet = dataSet - tile(minVals,(m,1)) 	#需要注意的是：这是特征值相除，对于某些数值处理软件包‘/’可能象征着矩阵除法 	#在NumPy中矩阵除法是函数：linalg.sovle(matA,matB) 	normDataSet = normDataSet / tile(ranges,(m,1)) 	return normDataSet,ranges,minVals  normMat,ranges,minVals = autoNorm(datingDataMat) # print(normMat)  #第三步：我们测试算法，采取传统的方式，10%的数据去测试分类器，检测分类器的准确率 #这是一个测试我们对约会网站改进的准确率 # def datingClassTest(): # 	hoRatio = 0.10 # 	datingDataMat,datingLabels = file2matrix('E:\ML_Data\datingTestSet2.txt') # 	normMat,ranges,minVals = autoNorm(datingDataMat) # 	m = normMat.shape[0] # 	numTestVecs = int(m*hoRatio) # 	errorCount = 0.0 # 	for i in range(numTestVecs): # 		classifierResult = classify(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],4) # 		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)))  # datingClassTest()#理论上k的值越大,准确率越高(但是往往太大后，准确率就降低)  #将以上算法进行组合，通过这个程序海伦可以在约会网站上找到某个人并输入他的信息，程序会预测他对对方喜欢的程度 #约会网站预测函数 def classifyPerson(): 	resultList = ['not at all ','in small doses','in large doses'] 	percentTats = float(input("percetage of time spent playing video games?")) 	ffMiles = float(input("frequent flier miles earned per year?")) 	iceCream = float(input("liters of ice cream consumed per year?"))  	datingDataMat,datingLabels = file2matrix("E:\ML_Data\datingTestSet2.txt") 	normMat,ranges,minVals = autoNorm(datingDataMat) 	inArr = array([ffMiles,percentTats,iceCream]) 	classifierResult = classify((inArr-minVals)/ranges,normMat,datingLabels,3) 	print("You will probably like this person :",resultList[classifierResult-1]) classifyPerson()  #--------------------------------------华丽分界线------------------------------------------------ #手写识别系统 #第一步：我们首先准备数据并且将图像转化为测试向量 #目录trainingDigits中包含大约2000个例子，每个数据大概有200个样本； #目录testDigits包含了大约900个测试数据 #我们将32*32的二进制图像矩阵转化为1*1024的向量，以便之前的分类器处理数字图像信息 # def img2vector(filename): # 	#创建1*1024的NumPy数组 # 	returnVect = zeros((1,1024)) # 	#打开文件 # 	fr = open(filename) # 	#循环读出文件的前32行 # 	for i in range(32): # 		lineStr = fr.readline() # 		#将每行的头32个字符值储存在NumPy数组中 # 		for j in range(32): # 			returnVect[0,32*i+j] = int(lineStr[j]) # 	return returnVect #在这里写成'\'这种，python在解析的时候一般会再加上一个\(也就是\\),但是遇到\0_13.txt中的\0这种特殊字符的时候不会自动加\ # testVector = img2vector('E:/ML_Data/testDigits/0_13.txt') # print(testVector[0,0:31])  #第二步：测试算法：使用kNN算法识别手写数字 #在这里我们首先导入os.listdir来列出给定目录的文件名 # def handwritingClasstest(): # 	hwLabels = [] # 	trainingFileList = listdir('E:/ML_Data/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.append(classNumStr) # 		trainingMat[i,:] = img2vector('E:/ML_Data/trainingDigits/%s' %fileNameStr) # 	testFileList = listdir('E:/ML_Data/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('E:/ML_Data/testDigits/%s' % fileNameStr) # 		classifierResult = classify(vectorUnderTest,trainingMat,hwLabels,4) # 		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)))  # handwritingClasstest() 

对应数据文件：

百度云链接：https://pan.baidu.com/s/1i4SI12P

相关书籍pdf ：https://github.com/apachecn/MachineLearning/tree/python-2.7/books

大家如果想要深入了解，请翻阅<机器学习实战>这一本书

或者直接访问开源https://github.com/apachecn/MachineLearning