K-近邻算法
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高
适用数据范围：数值型和标称型
解释：
标称型：标称型目标变量的结果只在有限目标集中取值，比如真与假(标称型目标变量主要用于分类)
数值型（连续型）：数值型目标变量则可以从无限的数值集合中取值
工作原理
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。
K-近邻算法的一般流程
- 收集数据：可以使用任何方法
- 准备数据：距离计算所需要的数值，最好是结构化的数据格式
- 分析数据：可以使用任何方法
- 训练算法：此步骤不适用于k-近邻算法
- 测试算法：计算错误
- 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理
1、准备：使用Python导入数据
2、实施KNN分类算法
k-近邻算法将每组数据划分到某个类中，主要操作如下：
（1）计算已知类别数据集中的点与当前点之间的距离
（2）按照距离递增次序排序
（3）选取与当前点距离最小的k个点
（4）确定k个点所在类别出现的频率
（5）返回前k个点出现的频率最高的类别作为当前的预测分类
3、如何测试分类器
我们可以使用已知答案的数据，检验分类器给出的结构是否符合预期。
错误率是分析器给出错误的结果的次数除以测试执行的总数。
完美的分类器的错误率为0，最差的分类器的错误率是1.0
4、KNN示例代码：
from numpy import *
import operator
import numpy
def createDataSet():
group = numpy.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
def classify0(inx, dataSet, labels, k):
dataSetsize = dataSet.shape[0]
# 获得dataSet的数据大小
diffMat = tile(inx, (dataSetsize, 1)) - dataSet
# tile函数是一种扩展矩阵函数，对于给定的值进行加行或加列
sqDiffMat = diffMat**2
# 计算所有的矩阵元素的平方
sqDistances = sqDiffMat.sum(axis=1)
# axis=1将一个矩阵的每一行向量相加，axis＝0表示按列相加
distances = sqDistances ** 0.5
# 将矩阵上的每一个元素都开根号
sortedDistIndices = distances.argsort()
# argsort函数返回的是数组值从小到大的索引值，本数据为[2 3 1 0]即表示最小的是下表为2的数据，最大的为小标为0的数据
# 以上6行是用来计算距离的
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndices[i]]
# 获取当前的标签
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
print(classCount[voteIlabel], classCount)
# get(voteilabel,0)：原型为get(key,默认值)，作用是获取key对应的值，如果不存在key,则新增key,值为默认值
sortedClassCount = sorted(
classCount.items(), key=operator.itemgetter(1), reverse=True)
# sorted(对象，排序值，reverse=True/False)，reverse默认值为False，表示正序，reverse=True表示倒序。
# 按照每个key的值对每对keyvalue进行降序排序，operator.itemgetter(1)：得到item中的第二个位置的值
return sortedClassCount[0][0]
group, labels = createDataSet()
print(group, "\n", labels)
test = classify0([0, 0], group, labels, 3)
print(test)
提示： 可以在不懂得地方打印出来结果看看，每一个变量是怎么样的
示例：使用K-近邻算法改进约会网站的配对效果
使用K-近邻算法的具体流程
- 收集数据：提供文本文件
- 准备数据：使用Python解析文本文件
- 分析数据：使用Matplotlib画二维扩展图
- 训练算法：此步骤不适用于k-近邻算法
- 测试算法：使用提供的部分数据作为测试样本
测试样本与非测式样本的区别在于：测试样本是已经完成分类的数据，如果测试分类与实际类别不同，则标记为一个错误 - 使用算法：产生简单的命令行数据，然后输入一些特征数据以判断是否为想要的结果
1、准备数据：从文本文件中解析数据
在将特征数据输入到分类器之前，必须将数据的格式转变为分类器可以接受的格式。
2、分析数据：使用Matplotlib创建散点图
可以使用不同的颜色或标记来区分不同的样本，以便更好的理解数据信息。可以多试几组相关的信息，来形成不同样本分类分区。
3、准备数据：归一化数值
在处理不同范围的特征值时，我们常采用的方法是将数值归一化，如将取值范围处理为0到1或者是-1到1之间。具体公式如下，特征值转化到0-1之间：
4、测试算法：作为完整程序验证分类器
机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供90%的数据作为训练样本分类器，而使用其余的10%数据去测试分类器，检测分类器的正确性。
提示： 10%的数据是随机选择的
5、使用算法：构建完整可用的系统
就是将复杂的数据展示给用户可以容易理解的形式展示出来。
6、约会网站的配对的示例代码
import operator
from os import error
import numpy as np
import matplotlib.pyplot as plt
from numpy.core.defchararray import array
from numpy import *
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
# matplotlib画图中中文显示会有问题，需要这两行设置默认字体
# k-近邻算法
def classify0(inx, dataSet, labels, k):
dataSetsize = dataSet.shape[0]
# 获得dataSet的数据大小
diffMat = tile(inx, (dataSetsize, 1)) - dataSet
# tile函数是一种扩展矩阵函数，对于给定的值进行加行或加列
sqDiffMat = diffMat**2
# 计算所有的矩阵元素的平方
sqDistances = sqDiffMat.sum(axis=1)
# axis=1将一个矩阵的每一行向量相加，axis＝0表示按列相加
distances = sqDistances ** 0.5
# 将矩阵上的每一个元素都开根号
sortedDistIndices = distances.argsort()
# argsort函数返回的是数组值从小到大的索引值，本数据为[2 3 1 0]即表示最小的是下表为2的数据，最大的为小标为0的数据
# 以上6行是用来计算距离的
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndices[i]]
# 获取当前的标签
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# get(voteilabel,0)：原型为get(key,默认值)，作用是获取key对应的值，如果不存在key,则新增key,值为默认值
sortedClassCount = sorted(
classCount.items(), key=operator.itemgetter(1), reverse=True)
# sorted(对象，排序值，reverse=True/False)，reverse默认值为False，表示正序，reverse=True表示倒序。
# 按照每个key的值对每对keyvalue进行降序排序，operator.itemgetter(1)：得到item中的第二个位置的值
return sortedClassCount[0][0]
# 返回频率发生最高的结果
# 导入数据的函数
def file2matrix(filename):
fr = open(filename)
# 打开并读取文件内容
arrayOLines = fr.readlines()
# 按照每一行来读取，并且返回一个数组，一行是一个元素
numberOfLines = len(arrayOLines)
# 获取文件中有多少行数据
returnMat = np.zeros((numberOfLines, 3))
# 创造一个同文件数据一样多的行数据，列为3，zeros创造全0的矩阵
classLabelVector = []
index = 0
for line in arrayOLines:
line = line.strip()
# 将文件中每一行，首尾的空格删去，此时会将转义字符变成真正的符号
listFromLine = line.split('\t')
# 将数据用‘\t’来分割，并结果以数组的形式返回
returnMat[index, :] = listFromLine[0:3]
# 将文本中的前三列数据复制到returnMat中
classLabelVector.append(int(listFromLine[-1]))
# 将文本中的最后一列数据追加到classLabelVector中
index += 1
return returnMat, classLabelVector
# 归一化数据处理
def autoNorm(dataSet):
minVals = dataSet.min(0)
# min(0)表示每一列中，数值最小的那一个
maxVals = dataSet.max(0)
# max(0)表示每一行中，数值最小的那一个
ranges = maxVals-minVals
normDataSet = np.zeros(shape(dataSet))
# 创建dataSet一样行和列的0元素矩阵
m = dataSet.shape[0]
# 获得传来数据的行数
normDataSet = dataSet-tile(minVals, (m, 1))
# tile函数是一种扩展矩阵函数，对于给定的值进行加行或加列，相当于是将minVals值按行扩展了m倍
# 传来的数据每一个都减去了本列中的最小值
normDataSet = normDataSet/tile(ranges, (m, 1))
# 特征值相除，以上两行公式为：newValue = (lodValue - min) / (max - min)
return normDataSet, ranges, minVals
# 分类器的测试
def datingClassTest():
hoRatio = 0.10
# 测试数据占总数据的百分比
datingDataMat, datingLables = file2matrix('datingTestSet.txt')
# 导入数据
norMat, ranges, minVals = autoNorm(datingDataMat)
# 归一化数据处理，norMat是计算newValue = (lodValue - min) / (max - min)，使数据特征值在0-1之间
m = norMat.shape[0]
# norMat是数据特征值，m是获得数据的行数
numTestVecs = int(m*hoRatio)
# 测试数据的行数
errorCount = 0.0
# 记录错误数据数量
for i in range(numTestVecs):
classifierResult = classify0(
norMat[i, :], norMat[numTestVecs:m, :], datingLables[numTestVecs:m], 3)
# classify0为kNN分类器，normMat为用于分类的输入向量，normMat为输入的训练样本集（剩余的90%）
# datingLabels为训练标签，3表示用于选择最近邻居的数目
print("The classifier came back with: %d, the real answer is: %d" %
(classifierResult, datingLables[i]))
if (classifierResult != datingLables[i]):
errorCount += 1.0
# 若预测结果与实际的数据标签不符，则证明是错误的，错误计算器加一
print("The total error rate is: %f" % (errorCount/float(numTestVecs)))
def classifyPerson():
resultList = ['Not at all', 'in small doses', 'in large']
# 定义显示结果的列表
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 consumed per year?"))
# 输入的三个数据
datingDataMat, datingLables = file2matrix('datingTestSet.txt')
# 导入数据大量数据一部分训练一部分测试
norMat, ranges, minVals = autoNorm(datingDataMat)
# 对数据进行归一化
inArr = np.array([ffMiles, percentTats, iceCream])
# 将用户输入的整合成三元组
classifierResult = classify0(
(inArr-minVals)/ranges, norMat, datingLables, 3)
# 使用KNN算法
print("You will probaby like this person:",
resultList[classifierResult-1])
classifyPerson()
datingDataMat, datingLables = file2matrix('datingTestSet.txt')
norMat, ranges, minVals = autoNorm(datingDataMat)
# 画图（start）
fig = plt.figure()
# 新建figure对象
ax = fig.add_subplot(111)
# 新建子图1，子图格式1行1列第一个图
# ax.scatter(datingDataMat[:,1],datingDataMat[:,2])
# 没有大小和颜色上的区分
ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1],
15.0*np.array(datingLables), 15.0*np.array(datingLables))
# scatter前两个参数(x,y)设置点的位置，第三个参数设置点的大小，第四个点设置点的颜色
# 具体scatter参考https://blog.csdn.net/weixin_33851177/article/details/85967765
plt.xlabel('每年获取的飞行常客里的程数')
plt.ylabel('玩视频游戏所耗时间的百分比')
plt.show()
# 画图（end）
示例：手写识别系统
提示： 此示例只能识别0-9
使用K-近邻算法的具体流程
- 收集数据：提供文本文件
- 准备数据：编写函数img2vector()，将图像格式转化为分类器使用的向量格式
- 分析数据：检查数据，确保它符合要求
- 训练算法：此步骤不适用于k-近邻算法
- 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本得区别在于测试样本是已经完成了分类的数据，若预测分类与实际类别不同，则标记为一个错误
- 使用算法：本里没有完成此步骤
1、准备数据：将图像转化为测试向量
为了使用前面例子中的分类器，必须将图像格式化处理为一个向量。将32 * 32的二进制矩阵转化为 1 * 1024的向量，这样就可以使用前面的分类器处理数字图像信息了。
2、测试数据：使用K-近邻算法识别手写数字
上面已经将数据处理成分类器可以识别的格式了，我们再将数据输入到分类器中，检测分类的执行效果。
3、识别手写数字的示例代码
import numpy as np
import operator
import os
from numpy.lib.shape_base import tile
def classify0(inx, dataSet, labels, k):
dataSetsize = dataSet.shape[0]
# 获得dataSet的数据大小
diffMat = tile(inx, (dataSetsize, 1)) - dataSet
# tile函数是一种扩展矩阵函数，对于给定的值进行加行或加列
sqDiffMat = diffMat**2
# 计算所有的矩阵元素的平方
sqDistances = sqDiffMat.sum(axis=1)
# axis=1将一个矩阵的每一行向量相加，axis＝0表示按列相加
distances = sqDistances ** 0.5
# 将矩阵上的每一个元素都开根号
sortedDistIndices = distances.argsort()
# argsort函数返回的是数组值从小到大的索引值，本数据为[2 3 1 0]即表示最小的是下表为2的数据，最大的为小标为0的数据
# 以上6行是用来计算距离的
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndices[i]]
# 获取当前的标签
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# get(voteilabel,0)：原型为get(key,默认值)，作用是获取key对应的值，如果不存在key,则新增key,值为默认值
sortedClassCount = sorted(
classCount.items(), key=operator.itemgetter(1), reverse=True)
# sorted(对象，排序值，reverse=True/False)，reverse默认值为False，表示正序，reverse=True表示倒序。
# 按照每个key的值对每对keyvalue进行降序排序，operator.itemgetter(1)：得到item中的第二个位置的值
return sortedClassCount[0][0]
# 将32*32的二进制矩阵转换成1*1024的向量
def img2vector(filename):
resultVect = np.zeros((1, 1024))
# 创建一个1*1024的矩阵
fr = open(filename)
for i in range(32):
linesStr = fr.readline()
for j in range(32):
resultVect[0, 32*i+j] = int(linesStr[j])
# 将32*32的矩阵变化为1*1024的矩阵，方便后期信息的处理
return resultVect
# 手写数字识别的测试代码
def handWritingClassTest():
hwLabels = []
trainingFileList = os.listdir('trainingDigits')
# 获取目录内容，形成一个list
m = len(trainingFileList)
# 获取目录中文件的个数
trainingMat = np.zeros((m, 1024))
# 为目录中每一个文件都创建一个1*1024的矩阵
for i in range(m):
fileNameStr = trainingFileList[i]
# 获取文件夹中每一个文件名称
fileStr = fileNameStr.split('.')[0]
# 获取文件的名称，不要其后缀名
classNumStr = int(fileStr.split('_')[0])
# 获取“-”之前的数字，表示被测试出来的数字，即0-9
hwLabels.append(classNumStr)
# 追加到hwLabels列表中，即此时hwLabels只有0-9
trainingMat[i, :] = img2vector(".\\trainingDigits\\%s" % fileNameStr)
# 文件中的每一个文件二进制数据都存放到trainingMat数组中，为以后训练数据使用
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)
# 获取每一个测试数据的1*1024矩阵值
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
# 利用KNN算法来计算与那一个数值相接近
print("The classifier came back with: %d, the real answer is: %d" %
(classifierResult, classNumStr))
if (classifierResult != classNumStr):
errorCount += 1.0
# 若预测结果与实际的数据标签不符，则证明是预测错误的，错误计算器加一
print("\nThe totle number of error is: %d" % errorCount)
print("\nThe totle error rate is: %f" % (errorCount/float(mTest)))
handWritingClassTest()
注意： 改变变量K值、修改函数handWritingClassTest随机训练样本、改变训练样本数目，都会对K-近邻算法的错误产生影响。<u>实际使用这个算法时执行的效率并不高</u>
小结
K-近邻算法是分类数据最简单有效的算法。k-近邻是基于实例的学习，使用算法时必须有接近的训练样本数据。k-近邻算法必须保存全部的数据集，若训练数据集很大，必须使用大量的存储空间；此外由于必须对数据集中的每个数据集中的每个数据计算距离值，实际使用时间可能非常耗时。
k-近邻算法另一个缺点是它无法给出任何数据的基础结构信息，因此也无法得出平均实例样本和典型实例样本具有什么特征。
