KNN算法填坑

python基础

浏览数:78

2020-5-31


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 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 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

 

 

 

喜欢可以多多收藏哦~转载请标注原文地址呦~

 

作者:Uncle_OJ