1.掌握k近邻算法的原理。
定义：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
也就是-“物以类聚”
2.理解k近邻算法三要素。
三要素分别为：k值的选择、距离度量、决策规则
近似误差：对现有训练集的训练误差，关注训练集，如果近似误差过小可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
估计误差：可以理解为对测试集的测试误差，关注测试集，估计误差小说明对未知数据的预测能力好，模型本身最接近最佳模型。
k值的选择
k值小->较小的邻域内->近似误差减小（训练集）->估计误差增大（测试集，噪声影响造成估计误差增大）->整体模型更加复杂->过拟合
k值大->较大的邻域内->估计误差减小->不相关的预测实例也造成影响->整体模型变得简单
应用中：k一般取用一个较小的值，采用交叉验证选取最优的k值。
距离度量
欧氏距离（两点之间的直线）
图片.png
曼哈顿距离（街区距离）
图片.png
切比雪夫距离（棋盘距离）
图片.png
决策规则
多数表决，对应于经验风险化最小，例如选取k=10，经预测后将相同的结果进行分类，其中最大的就是要预测结果所在的分类。
3.掌握k近邻算法在分类问题上的求解过程。
1）计算已知类别数据集中的点与当前点之间的距离（一般采用欧氏距离）
2）按距离递增次序排序（采用距离由小到大进行排序，按照下标，后代码中有）
3）选取与当前点距离最小的k个点
4）统计前k个点所在的类别出现的频率
5）返回前k个点出现频率最高的类别作为当前点的预测分类
4.掌握k近邻的代码实现
数据集的描述：手写数字识别，第一列为标签，即是什么数字，剩下的255列是特征描述
import numpy as np
import time
from tqdm import tqdm
def loadData(fileName):
"""
加载文件
:param fileName:要加载的文件路径
:return: 数据集和标签集
"""
print("start to read!")
dataArr = []
labelArr = []
#读取文件
#遍历文件中的每一行
fr = open(fileName)
for line in tqdm(fr.readlines()):
#按照‘，’切割成字段放入列表，
#strip去掉每行字符串首位指定的字符（空格或换行）
curLine = line.strip().split(',')
#标记和数据分开存放
dataArr.append([int(num) for num in curLine[1:]])
labelArr.append(int(curLine[0]))
return dataArr,labelArr
def calcDist(x1,x2):
"""
计算两个样本点之间的向量之间的距离
:param x1: 向量1
:param x2: 向量2
:return: 两个样本点之间的距离
"""
#欧氏距离
return np.sqrt(np.sum(np.square(x1-x2)))
#曼哈顿距离
#return np.sum(x1-x2)
def getClosest(trainDataMat,trainlabelMat,x,topk):
"""
预测样本x的标记
获取方式通过找到与样本x最近的topK个点，并查看它们的标签。
查找里面占某类标签最多的那类标签
:param trainDataMat:训练数据集
:param trainlabelMat:训练标签集
:param x:要预测的样本x
:param topk:最邻近的样本点
:return:预测的标记
"""
#建立一个存放向量x与最近的topk个点，并查看他们的标签
#列表长度为训练集的长度，distlist[i]表示与训练集中第i个
distList = [0] * len(trainDataMat)
#遍历训练集中所有的样本点，计算与x的距离
for i in range(len(trainDataMat)):
x1 = trainDataMat[i]
curDist = calcDist(x1,x)
distList[i] = curDist
#此处做了优化，将要进行比较的topk个点已经按照下标排序好了，节约了时间复杂度
topKlist = np.argsort(np.array(distList))[:topk]
labelList = [0] * 10
for index in topKlist:
#trainLabelMat[index],在训练集中找到topk元素索引对应的标记
#int(trainLabelMat[index]):将标记转化为int
labelList[int(trainlabelMat[index])] += 1
# max(labelList)：找到选票箱中票数最多的票数值
# labelList.index(max(labelList))：
# 再根据最大值在列表中找到该值对应的索引，等同于预测的标记
print(labelList.index(max(labelList)))
return labelList.index(max(labelList))
def model_test(trainDataArr,trainLabelArr,testDataArr,testLabelArr,topk):
"""
测试正确率
:param trainDataArr: 训练数据及
:param trainLabelAr: 训练标签集
:param testDataArr: 测试数据集
:param testLabelArr: 测试标签集
:param topk: 邻居数
:return: 正确率
"""
print("start test!")
#将所有列表转化成矩阵形式，方便运算
trainDataMat = np.mat(trainDataArr)
trainLabelMat = np.mat(trainLabelArr).T
testDataMat = np.mat(testDataArr)
testLabelMat = np.mat(testLabelArr).T
errorCnt = 0
for i in range(200):
print('test %d:%d'%(i,200))
#读取当前测试集样本的向量
x = testDataMat[i]
y = getClosest(trainDataMat,trainLabelMat,x,topk)
if y!= testLabelMat[i] : errorCnt += 1
return 1 - (errorCnt / 200)
if __name__ == '__main__':
start = time.time()
trainDataArr = [5,9,4,2,8,7]
trainDataMat = np.array(trainDataArr)
trainLabelArr = [4,6,7,3,1,2]
trainLabelMat = np.array(trainLabelArr)
#accur = model_test(trainDataArr,trainLabelArr,testDataArr,testLabelArr,25)
#print('accur is :%d'%(accur * 100),'%')
getClosest(trainDataMat,trainLabelMat,5,topk=1)
end = time.time()
print('time span:',end-start)
网友评论