KNN（原理及代码实现）

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)