k近邻法（k-nearest neighbor, k-NN）

参考：机器学习实战教程（一）：K-近邻（KNN）算法（史诗级干货长文） (cuijiahua.com)

​ 《机器学习实战》

​ 《统计学习方法》

核心思想介绍

1. 算法简介

给定一个训练数据集，对新的输入实例，在训练数据集中找到于该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

模型主要由三个要素来决定：

距离度量、k值得选择和分类决策规则

2. 数理讲解

1）距离度量

主要引入较为普遍的欧式距离（二维情况下两点间距离）：p>=1，即p=2时，

2）k值的选取会对该算法产生重大影响

3）分类决策规则

可以使误分类率最小，即经验风险最小。

3. 算法代码主体部分

代码实现如下，具体思路是输入一个实例，并将这个实例按照训练数据集实例个数，复制自身拓展为多维矩阵，分别与每一个训练数据集实例相减计算距离，将距离排序，筛选出最近的k个实例，了解k个实例中哪个类别的实例数量最多，那么就将这个类别判定给最新的这个实例。

import numpy as np

###2-1 k-近邻算法###
#inX是用于分类的输入向量，dataSet是训练集，labels是训练集对应的标签，k是最近邻实例的数量
def classify0(inX, dataSet, labels, k):
	#numpy的shape是查看矩阵或者数组的维数，shape[0]为读取数组第一维度的长度
	dataSetSize = dataSet.shape[0]
	#inX在列向量方向上重复共1次（横向），行向量方向上重复dataSetSize次（纵向），并与训练集矩阵相减
	diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
	#求平方
	sqDiffMat = diffMat**2
	#sum()所有元素相加，sum(0)列相加，sum(1)行相加
	sqDistances = sqDiffMat.sum(axis=1)
	#开方，计算出距离
	distances = sqDistances**0.5
	#distances中元素从小到大排序后的索引值
	sortedDistIndicies = distances.argsort()
	#定一个记录类别次数的字典
	classCount = {}
	for i in range(k):
		#取出前k个元素的类别
		voteIlabel = labels[sortedDistIndicies[i]]
		#dict.get(key,default=None)，字典的get()方法，返回指定键的值，如果值不在字典中返回默认值。
		#计算类别次数
		classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
	#python3中用items()替换python2中的iteritems()，以列表方式返回字典中的键值对。
	#key=operator.itemgetter(1)按照字典的值进行排序
	#key=operator.itemgetter(0)根据字典的键进行排序
	#reverse降序排序字典
	sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
	#返回次数最多的类别，即索要分类的类别
	return sortedClassCount[0][0]

应用案例一：使用k-近邻算法改进约会网站的配对效果

1. 背景和所涉函数&框架

背景：海伦一直使用在线约会网站寻找约会对象，她根据经验将约会对象分为三类（不喜欢的人、魅力一般的人、极具魅力的人），她搜集了一些约会对象的数据（有3个特征，分别是每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数），希望能采用kNN算法帮助她对未来的约会对象进行归类。

函数清单：

• classify0(inX, dataSet, labels, k)

​ inX是用于分类的输入向量，dataSet是训练集，labels是训练集对应的标签，k是最近邻实例的数量

​ k-近邻算法，计算距离并预测新实例所属类别

​ 输出结果：sortedClassCount，是所属类别

• file2matrix(filename)

  filename是数据文件

  数据整理，把数据整理为两个矩阵，一个是特征矩阵，一个是分类矩阵，并为分类矩阵打好数字标签

  输出结果：datingDataMat 特征矩阵, datingLabels分类矩阵

• showdatas(datingDataMat, datingLabels)

​ 制作散点图

• autoNorm(dataSet)

  dataSet是特征矩阵

  按照归一化的公式来对原始特征矩阵进行处理

  输出结果：normDataSet新的特征矩阵, ranges最大最小值之间差, minVals最小值

2. 具体操作

（1）数据处理

测试数据描述：如下图，一共有1000个可选约会对象实例，前三列为特征向量（浮点数），最后一列为分类标签（字符）。

代码实现如下，主要思想是将文件内的数据按照行来打散成为字符串列表，按照每个实例（每行），将其前三列数值填充进形成好的零矩阵中，并将将最后一列标签值赋予数值，遍历所有实例，完成填充和赋值。

# -*- coding: UTF-8 -
import numpy as np

"""
函数说明：将数据转化为可用于分析的数据

Parameter:
    filename - 文件名
Returns：
    returnMat - 特征矩阵
    classLabelVector - 分类Label向量

Modify:
    2022-07-05
"""

def file2matrix(filename):
	fr = open(filename)
	# readlines()读取所有行，然后把它们作为一个字符串列表返回
	arrayOLines = fr.readlines()
	# 记录有多少个实例（行数）
	numberOlines = len(arrayOLines)
	# 返回一个numberOgLines*3且都为0的数组
	returnMat = np.zeros((numberOlines, 3))
	# 设置分类标签向量和实例（行）的索引值
	classLabelVector = []
	index = 0
	for line in arrayOLines:
		# s.strip(rm)，当rm空时,默认删除空白符(包括'\n','\r','\t',' ')
		line = line.strip()
		# 将字符串根据'\t'分隔符进行切片
		listFromLine = line.split('\t')
		# 将数据前三列提取出来,存放到returnMat的NumPy矩阵(原本都是零矩阵）中,也就是特征矩阵
		returnMat[index, :] = listFromLine[0:3]
		# 根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力
		if listFromLine[-1] == 'didntLike':
			classLabelVector.append(1)
		elif listFromLine[-1] == 'smallDoses':
			classLabelVector.append(2)
		elif listFromLine[-1] == 'largeDoses':
			classLabelVector.append(3)
		# 等于index = index + 1
		index += 1
	#检查标签是否全部都被赋值了
	print(len(classLabelVector))
	return returnMat, classLabelVector



if __name__ == '__main__':
	filename = 'D:\技能训练材料\数据分析、数据挖掘\实践项目\kNN\datingTestSet.txt'
	# 打开并处理数据
	datingDataMat, datingLabels = file2matrix(filename)

结果如下：1000个都已经赋值

（2）分析数据：使用Matplotlib创建散点图

通过描述性统计，采用不同特征组合，看下数据是否根据类别不同有所区分。

# -*- coding: UTF-8 -
import matplotlib.lines as mlines
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.font_manager import FontProperties
#从kNN_dataset.py中引入file2matrix这个自定义函数（前面是地址，因人而异）
from 机器学习实践.kNN.kNN_dataset import file2matrix

"""""
函数说明: 描述性统计-数据可视化-散点图

Parameters:
    datingDataMat - 特征矩阵
    datingLabels - 分类Label
Returns:
    无
Modify:
    2022-07-5
"""
def showdatas(datingDataMat, datingLabels):
	#设置汉字格式
	font = FontProperties(fname=r"c:\windows\fonts\simkai.ttf",size=14)
	#将fig画布分隔成1行1列，不共享x轴和y轴，fig画布的大小为(13,8)
	#当nrow=2, nclos=2时，代表fig画布被分为四个区域，axs[0][0]标识第一行第一个区域
	fig,axs = plt.subplots(nrows=2, ncols=2, sharex=False, sharey=False, figsize=(13,8))
	number0fLabels = len(datingLabels)
	LabelsColors = []
	for i in datingLabels:
		if i == 1:
			LabelsColors.append('black')
		if i == 2:
			LabelsColors.append('orange')
		if i == 3:
			LabelsColors.append('red')
	#画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第二列(玩游戏)数据画散点数据,散点大小为15,透明度为0.5
	axs[0][0].scatter(x=datingDataMat[:,0], y=datingDataMat[:,1],color=LabelsColors, s=15, alpha=.5)
    #设置标题，x轴label，y轴label
	axs0_title_text = axs[0][0].set_title(u'每年获得的飞行常客里程数与玩视频游戏所消耗时间占比', fontproperties=font)
	axs0_xlabel_text = axs[0][0].set_xlabel(u'每年获得的飞行常客里程数', fontproperties=font)
	axs0_ylabel_text = axs[0][0].set_ylabel(u'玩视频游戏所消耗时间占', fontproperties=font)
	plt.setp(axs0_title_text, size=9, weight='bold', color='red')
	plt.setp(axs0_xlabel_text, size=7, weight='bold', color='black')
	plt.setp(axs0_ylabel_text, size=7, weight='bold', color='black')

	# 画出散点图,以datingDataMat矩阵的第一(飞行常客例程)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
	axs[0][1].scatter(x=datingDataMat[:, 0], y=datingDataMat[:, 2], color=LabelsColors, s=15, alpha=.5)
	# 设置标题,x轴label,y轴label
	axs1_title_text = axs[0][1].set_title(u'每年获得的飞行常客里程数与每周消费的冰激淋公升数', fontproperties=font)
	axs1_xlabel_text = axs[0][1].set_xlabel(u'每年获得的飞行常客里程数', fontproperties=font)
	axs1_ylabel_text = axs[0][1].set_ylabel(u'每周消费的冰激淋公升数', fontproperties=font)
	plt.setp(axs1_title_text, size=9, weight='bold', color='red')
	plt.setp(axs1_xlabel_text, size=7, weight='bold', color='black')
	plt.setp(axs1_ylabel_text, size=7, weight='bold', color='black')

	# 画出散点图,以datingDataMat矩阵的第二(玩游戏)、第三列(冰激凌)数据画散点数据,散点大小为15,透明度为0.5
	axs[1][0].scatter(x=datingDataMat[:, 1], y=datingDataMat[:, 2], color=LabelsColors, s=15, alpha=.5)
	# 设置标题,x轴label,y轴label
	axs2_title_text = axs[1][0].set_title(u'玩视频游戏所消耗时间占比与每周消费的冰激淋公升数', fontproperties=font)
	axs2_xlabel_text = axs[1][0].set_xlabel(u'玩视频游戏所消耗时间占比', fontproperties=font)
	axs2_ylabel_text = axs[1][0].set_ylabel(u'每周消费的冰激淋公升数', fontproperties=font)
	plt.setp(axs2_title_text, size=9, weight='bold', color='red')
	plt.setp(axs2_xlabel_text, size=7, weight='bold', color='black')
	plt.setp(axs2_ylabel_text, size=7, weight='bold', color='black')

	# 设置图例
	didntLike = mlines.Line2D([], [], color='black', marker='.',
	                          markersize=6, label='didntLike')
	smallDoses = mlines.Line2D([], [], color='orange', marker='.',
	                           markersize=6, label='smallDoses')
	largeDoses = mlines.Line2D([], [], color='red', marker='.',
	                           markersize=6, label='largeDoses')
	# 添加图例
	axs[0][0].legend(handles=[didntLike, smallDoses, largeDoses])
	axs[0][1].legend(handles=[didntLike, smallDoses, largeDoses])
	axs[1][0].legend(handles=[didntLike, smallDoses, largeDoses])
	# 显示图片
	plt.show()

if __name__ == '__main__':
	#打开的文件名
	filename = "D:\技能训练材料\数据分析、数据挖掘\实践项目\kNN\datingTestSet.txt"
	#打开并处理数据
	datingDataMat, datingLabels = file2matrix(filename)
	showdatas(datingDataMat, datingLabels)

结果如下：可以看到采用第一和第二种特征搭配，能够将三个群体较有效地区隔开来。

（3）准备数据：归一化

根据下表可以看到，特征”每年获得的飞行常客里程数“整体数值远高出另外两种特征，因此在计算两个实例间的距离时，该特征的影响会被放大，因此需要将数值归一化，即将取值范围处理为0到1或者-1到1之间（三个特征值都同时被处理归一）。

具体归一化公式如下:

代码实现如下，主要思想是分别计算最大最小值，以及最大最小值之间的差，并在与原始值计算时将这些数值转化为矩阵模式来计算，按照如上的归一化公式计算得到最终新的特征矩阵：

# -*- coding: UTF-8 -
from 机器学习实践.kNN.kNN_dataset import file2matrix
import numpy as np


########特征数据归一化##########
"""
函数说明：对数据进行归一化

Parameters:
    dataSet - 特征矩阵
Returns:
    nomrDataSet - 归一化后的特征矩阵
    ranges - 数据范围
    minVals - 数据最小值

Modify:
    2022-07-06
"""


def autoNorm(dataSet):
	# 获得数据的最大最小值
	minVals = dataSet.min(0)
	maxVals = dataSet.max(0)
	ranges = maxVals - minVals
	# 获得dataSet的矩阵行列数，并据此形成零矩阵
	normDataSet = np.zeros(np.shape(dataSet))
	# 返回dataSet的行数
	m = dataSet.shape[0]
	# miVals在列向量上重复1次，在行向量上重复m次，计算原始数据和最小值之间的差
	normDataSet = dataSet - np.tile(minVals, (m, 1))
	# 归一化计算
	normDataSet = normDataSet / np.tile(ranges, (m, 1))
	return normDataSet, ranges, minVals

if __name__ == '__main__':
	filename = 'D:\技能训练材料\数据分析、数据挖掘\实践项目\kNN\datingTestSet.txt'
	datingDataMat, datingLabels = file2matrix(filename)
	normDataSet, ranges, minVals = autoNorm(datingDataMat)
	print("这是归一化矩阵\n",normDataSet)
	print("这是范围\n",ranges)
	print("这是最小值\n",minVals)

结果如下：

（4）测试算法

采用错误率来测试算法是否准确，对于分类器来说，错误率就是分类器给出错误结果的次数除以测试数据的总数，完美分类器的错误率为0，而错误率为1.0的分类器不会给出任何正确的分类结果。

代码实现如下：

# -*- coding: UTF-8 -
#########测试数据##########
from 机器学习实践.kNN.kNN_norm import autoNorm
from 机器学习实践.kNN.kNN_dataset import file2matrix
from 机器学习实践.kNN.kNN import classify0

"""
函数说明：计算该算法的错误率，涉及到拆分数据集为测试和训练数据集，到预测并计算

Parameters:
    无
Returns:
    无

Modify:
    2022-07-06
"""


def datingClassTest():
	# 取所有数据的10%作为测试数据，剩下90%为训练数据
	hoRatio = 0.10
	# 将返回的特征矩阵和分类向量分别存储进datingDataMat和datingLabels中
	datingDataMat, datingLabels = file2matrix(filename)
	# 数据归一化
	normMat, ranges, minVals = autoNorm(datingDataMat)
	# 获得normMat的行数
	m = normMat.shape[0]
	# 百分之十的测试数据个数
	numTestVecs = int(m * hoRatio)
	# 分类错误计数
	errorCount = 0.0
	for i in range(numTestVecs):
		# 前numTestVecs个数据作为测试集，后m-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
	error_rate = errorCount / float(numTestVecs)
	print("the total error rate is: %f" % (error_rate* 100))

if __name__ == '__main__':
	filename = 'D:\技能训练材料\数据分析、数据挖掘\实践项目\kNN\datingTestSet.txt'
	datingClassTest()

结果如下：可以看到本次结果有5%的可能性被分错

（5）使用算法

# -*- coding: UTF-8 -
###########使用算法#################
from 机器学习实践.kNN.kNN_norm import autoNorm
from 机器学习实践.kNN.kNN_dataset import file2matrix
from 机器学习实践.kNN.kNN import classify0
import numpy as np

"""
函数说明:通过输入一个人的三维特征,进行分类输出

Parameters:
    无
Returns:
    无

Modify:
    2022-07-06
"""

def classifyPerson():
	resultList = ['不喜欢', '有点喜欢', '非常喜欢']
	#Python3里面把raw-input和input整合在一起，默认接收str类型
	percentTats = float(input("玩视频游戏所耗时间百分比:"))
	ffMiles = float(input("每年获得的飞机常客里程数:"))
	iceCream = float(input("每周消费的冰淇淋公升数:"))
	datitingDataMat, datingLabels = file2matrix(filename)
	normMat, ranges, minVals = autoNorm(datitingDataMat)
    #生成NumPy数组,测试集
	inArr = np.array([ffMiles, percentTats, iceCream])
    #返回分类结果
	classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
	print("你可能%s这个人" % (resultList[classifierResult - 1]))

if __name__ == '__main__':
	filename = 'D:\技能训练材料\数据分析、数据挖掘\实践项目\kNN\datingTestSet.txt'
	classifyPerson()

结果如下：输入三个特征维度值，预测结果如下，且可能有5%的概率是预测错误的。

应用案例二：手写识别系统

数据展示：第一个图片是文件夹打开后，将图像转化为.txt格式的二进制文件，文件名首位是该文件所代表的数值。

如下是文件打开后，是二进制图像

代码实现如下，基本思路和应用案例一一致，只是需要将每个图像转化为有1024个特征的向量：

import os
from os import listdir
import numpy as np
import operator
from 机器学习实践.kNN.kNN import classify0

##数据处理###
"""
函数说明：将32X32的二进制图像转化为1X1024向量

Parameters:
	filename - 文件名
Returns:
	returnVect - 返回的二进制图像的1X1024向量
	
Modify:
    2022-07-06
"""

def img2vector(filename):
	#创建一个1X1024的零向量
	returnVect = np.zeros((1,1024))
	fr = open(filename)
	for i in range(32):
		# readline()用于从文件每次读取一行，包括"\n"字符，该方法返回一个字符串对象
		lineStr = fr.readline()
		#i不变，列开始循环，每一次循环都将其中一行的数字填充到returnVect，列循环结束后，开启下一行。
		for j in range(32):
			returnVect[0, 3*i+j] = int(lineStr[j])
	return returnVect

##测试算法##
"""
函数说明：将32X32的二进制图像转化为1X1024向量

Parameters:
	filename - 文件名
Returns:
	returnVect - 返回的二进制图像的1X1024向量

Modify:
    2022-07-06
"""
def handwritingClassTest():
	hwLabels = []
	#打开训练数据文件，输出所有文件和文件夹
	trainingFileList = os.listdir(filename1)
	print(trainingFileList)
	#输出trainingFileList的元素数量
	m = len(trainingFileList)
	#形成一个m*1024的零矩阵
	trainingMat = np.zeros((m,1024))
	#以下的矩阵最终得到m*1024的实例矩阵
	for i in range(m):
		#将trainingFileList对应i位的元素给到fileNameStr，也就是文件名
		fileNameStr = trainingFileList[i]
		#按照"."来进行分割，并取出第0位的元素,也就是文件名”0_0.txt"前面的内容
		fileStr = (fileNameStr.split('.'))[0]
		#取出文件名”0_0.txt"的首位0
		classNumStr = int(fileStr.split('_')[0])
		#在hwLabels里面添加classNumStr
		hwLabels.append(classNumStr)
		#对trainingMat的每一行插入trainingDigits文件夹下的各个文件
		trainingMat[i,:] = img2vector('%s\%s' % (filename1,fileNameStr))
	#打开测试数据文件，输出所有文件和文件夹
	testFileList = listdir(filename2)
	#设置错误率
	errorCount = 0.0
	#输出testFileList的元素数量
	mTest = len(testFileList)
	#以下内容逻辑和上面一样，不再赘述
	for i in range(mTest):
		fileNameStr = testFileList[i]
		fileStr = (fileNameStr.split('.'))[0]
		classNumStr = int(fileStr.split('_')[0])
		vectorUnderTest = img2vector('%s/%s' % (filename2,fileNameStr))
		#使用之前定义过的classify0来对该测试数据分类
		classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 13)
		print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult,classNumStr))
		if (classifierResult != classNumStr): errorCount +=1.0
	print("\nthe total numbber of errors is: %d" % errorCount)
	print("\nthe total error rate is: %f" % (errorCount/float(mTest)))

if __name__ == '__main__':
	filename1 = r'D:\技能训练材料\数据分析、数据挖掘\软件\python\机器学习实战\机器学习实战（源代码）\Ch02\digits\trainingDigits'
	filename2 = r'D:\技能训练材料\数据分析、数据挖掘\软件\python\机器学习实战\机器学习实战（源代码）\Ch02\digits\testDigits'
	handwritingClassTest()

结果如下：可看到该模型测试后误差比较高，可以通过改变k值改变误差，但效果不太好，可能和模型或者数据相关。

其他：关于hexo就本地图片无法显示的问题Hexo上markdown图片路径与Typora保持一致 | He’s Blog (algorithmofdish.tech)

关于hexo公式显示的问题如何在hexo显示图片与公式 | Keep (liaokai.com.cn)