1.k-近邻法简介

• k近邻法(k-nearest neighbor, k-NN)是1968年由Cover THart 提出的一种基本分类与回归方法。
• 它的工作原理是：

存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

• 注意:

k-近邻法不具有显式的学习过程，它实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”.其中K值的选取、距离度量及分类决策规则是k近邻算法的三个基本要素。

2.kNN算法的优缺点

• 优点：

  • 简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；
  • 可用于数值型数据和离散型数据；
  • 训练时间复杂度为O(n)；无数据输入假定；
  • 对异常值不敏感

• 缺点：

  • 计算复杂性高；空间复杂性高；
  • 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
  • 一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。
  • 最大的缺点是无法给出数据的内在含义。

3.K值的选择
  K值选择问题，李航博士的一书「统计学习方法」上所说：

• （1）选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
• （2）选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
• （3）K=N（N为训练样本个数），则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。

• （4）近似误差：
  对现有训练集的训练误差，关注训练集，如果近似误差过小可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
• （5）估计误差：
  可以理解为对测试集的测试误差，关注测试集，估计误差小说明对未知数据的预测能力好，模型本身最接近最佳模型。

• （6）KNN中K值大小选择对模型的影响

  • k值过小：

    • 容易受到异常点的影响
    • 容易过拟合
    • 模型过于复杂

  • k值过大：

    • 受到样本均衡的问题
    • 容易欠拟合
    • 模型过于简单

4.距离度量
  我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。但有的读者可能就有疑问了，我是要找邻居，找相似性，怎么又跟距离扯上关系了？这是因为特征空间中两个实例点的距离和反应出两个实例点之间的相似性程度。K近邻模型的特征空间一般是n维实数向量空间，使用的距离可以使欧式距离，也是可以是其它。

  （1）欧式距离(Euclidean distance)
  相当于高维空间内向量说表示的点到点之间的距离。由于特征向量的各分量的量纲不一致，通常需要先对各分量进行标准化，使其与单位无关，比如对身高（cm）和体重（kg）两个单位不同的指标使用欧式距离可能使结果失效。
  优点：简单,应用广泛(如果也算一个优点的话)。
  缺点：没有考虑分量之间的相关性,体现单一特征的多个分量会干扰结果。

from math import *
# python3
# 欧式距离
def eculidean_dis(x, y):
    return sqrt(sum(pow(a - b, 2) for a, b in zip(x, y)))

x = [1, 3, 2, 4]
y = [2, 5, 3, 1]

print(eculidean_dis(x, y))   # 结果为3.872983346207417

  （2）曼哈顿距离
  我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为。要注意的是，曼哈顿距离依赖座标系统的转度，而非系统在座标轴上的平移或映射。通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源。同时，曼哈顿距离也称为城市街区距离(City Block distance)。
  适用场合：
  1)度量两个服从同一分布并且其协方差矩阵为C的随机变量X与Y的差异程度
  2)度量X与某一类的均值向量的差异程度,判别样本的归属。此时，Y为类均值向量.
  优点：
  1）独立于分量量纲
  2）排除了样本之间的相关性影响。
  缺点：
  不同的特征不能差别对待，可能夸大弱特征。

# 曼哈顿距离
def manhattan_dis(x, y):
    return sum(abs(a - b) for a, b in zip(x, y))

print(manhattan_dis(x, y))  # 结果为7

  （3）闵可夫斯基距离(Minkowski Distance)
  可看成是欧氏距离的指数推广，还没有见到过很好的应用实例，但通常，推广都是一种进步，特别的，其中p是一个变参数：
  当p=1时，就是曼哈顿距离
  当p=2时，就是欧氏距离
  当p→∞时，就是切比雪夫距离
  切比雪夫距离起源于国际象棋中国王的走法，我们知道国际象棋国王每次只能往周围的8格中走一步，那么如果要从棋盘中A格（x1， y1）走到B格（x2， y2）最少需要走几步？扩展到多维空间，其实切比雪夫距离就是当p趋向于无穷大时的明氏距离。

# 明可夫斯基距离
def minkowski_dis(x, y, p):
    sumval = sum(pow(abs(a - b), p) for a, b in zip(x, y))
    mi = 1 / float(p)
    return round(sumval ** mi, 3)

print(minkowski_dis(x, y, 3))  # 结果为3.332

  （4）其他距离，参看：xxxx

5.分类决策规则

• k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个近邻的训练实例中的多数类决定输入实例的类别。

6.K近邻算法的一般流程

• 计算已知类别数据集中的点与当前点之间的距离；
• 按照距离递增次序排序；
• 选取与当前点距离最小的k个点；
• 确定前k个点所在类别的出现频率；
• 返回前k个点出现频率最高的类别作为当前点的预测分类

7.python实现KNN算法API介绍

• API:

  sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm=‘auto’)

• KNneighborsClassifier参数说明：
• n_neighbors：默认为5，就是k-NN的k的值，选取最近的k个点。
• weights：默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。
• algorithm：快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。ball tree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。
• leaf_size：默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
• metric：用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。
• p：距离度量公式。在上小结，我们使用欧氏距离公式进行距离度量。除此之外，还有其他的度量方法，例如曼哈顿距离。这个参数默认为2，也就是默认使用欧式距离公式进行距离度量。也可以设置为1，使用曼哈顿距离公式进行距离度量。
• metric_params：距离公式的其他关键参数，这个可以不管，使用默认的None即可。
• n_jobs：并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。
• 官方手册

8.示例
  （1）电影分类问题
  给定已知电影的数据信息（打斗镜头和接吻接吻镜头）及分类情况（爱情片/动作片），给定未知电影数据信息，通过数据分析，确定未知电影的分类情况。设k = 3,则前3个距离分别为[18.7， 19.2, 20.5]，对应的标签为[爱情片,爱情片，爱情片], 频率统计：爱情片 100%， 动作片0%，返回位置电影的可能类别为爱情片。

import numpy as np
import operator
 
'''
Function :     createDataSet()
    Args:     None
    Rets:     group, dataset 
            lables, classes
'''
def createDataSet():
    group = np.array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
    lables = ['Ramatic', 'Ramatic', 'Action', 'Action', 'Action']
    return group, lables
 
'''
Function :     kNN(test, group, lables, k)
    Args :    test, test set
            group, train set
            lables, classes
            k, k nearest setting
    Rets :    pred[0][0], predict class
'''
def kNN(test, group, lables, k):
    dataSize = group.shape[0]
    #tile: to copy data as Array_m*n
    diff = np.tile(test, (dataSize, 1)) - group
    sqrdiff = diff**2
    #sum(axis = 1) : sum as row
    sumdiff = sqrdiff.sum(axis = 1)
    dist = sumdiff**0.5
    #argsort : return the index of dist order, [3, 1, 2] -> [1, 2, 0] asceeding order
    dist_order = dist.argsort()
    classes = {}
    for i in range(k):
        voteLable = lables[dist_order[i]]
        classes[voteLable] = classes.get(voteLable, 0) + 1
    #sorted : for any iterator, return list
    pred = sorted(classes.items(), key = operator.itemgetter(1), reverse = True)
    return pred[0][0] 
 
if __name__ == '__main__':
    group, lables = createDataSet()
    test = [18, 90]
    print('test : ', test)
    pred_class = kNN(test, group, lables, 3)
    print('predict class : ', pred_class)

  （2）一个稍复杂的例子：海伦约会
  海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选，但她并不是喜欢每一个人。经过一番总结，她发现自己交往过的人可以进行如下分类：

• 不喜欢的人（didntLike）
• 魅力一般的人(smallDoses)
• 极具魅力的人(largeDoses)

  海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。数据信息分别为：每年飞行旅程里程、玩视频游戏时间百分比、每周消耗冰激凌公升数及喜好程度。数据集下载：info.txt。考虑到给定特征的数量级相差较大，因此需要对各特征进行归一化处理，对应公式为：$$x' = \frac{x- min(x))}{max(x)-min(x)}.$$

按照kNN算法分析，python3实现代码如下：
import numpy as np
import operator
from matplotlib.font_manager import FontProperties
import matplotlib.lines as mlines
import matplotlib.pyplot as plt
 
'''
Function : file2matrix(filename)
    Description :     to covert file into matrix
    Args:    filename
    Rets:    featureMatrix, the matrix format from file coverting
            labels, the label for info
'''
 
def file2matrix(filename):
    fread = open(filename)
    info = fread.readlines()
    featureMatrix = np.zeros((len(info), 3))
    labels = []
    index = 0
    for line in info:
        line = line.strip()
        listline = line.split('\t')
        featureMatrix[index, :] = listline[0:3]
        if listline[-1] == 'didntLike':
            labels.append(1)
        if listline[-1] == 'smallDoses':
            labels.append(2)
        if listline[-1] == 'largeDoses':
            labels.append(3)
        index += 1
    return featureMatrix, labels
 
'''
Function : normalize(featureMatrix)
    Description : to normalize data
    Args :    featureMatrix
    Rets : normFeatureMatrix
'''
def normalize(featureMatrix):
    #get every column minVal
    minVal = featureMatrix.min(0)
    #get every row maxVal
    maxVal = featureMatrix.max(0)
    ranges = maxVal - minVal
    normFeatureMatrix = np.zeros(np.shape(featureMatrix))
    row = normFeatureMatrix.shape[0]
    normFeatureMatrix = featureMatrix - np.tile(minVal, (row, 1))
    normFeatureMatrix = normFeatureMatrix / np.tile(ranges, (row, 1))
    return normFeatureMatrix
 
'''
Function : visualize(featureMatrix, labels)
    Description : to visualize data
    Args :    featureMatrix
            labels
    Rets :    None
'''
 
def visualize(featureMatrix, labels):
    font = FontProperties(size = 14)
    #fig: figure object, axs : subplot
    fig, axs = plt.subplots(nrows = 2, ncols = 2, sharex = False, sharey = False, figsize = (10, 10))
    labelColors = []
    for i in range(len(labels)):
        if i == 1:
            labelColors.append('black')
        if i == 2:
            labelColors.append('orange')
        if i == 3:
            labelColors.append('red')
    #subplot(0,0) scatter, s : scatter size, alpha : transparency
    axs[0][0].scatter(x = featureMatrix[:,0], y = featureMatrix[:, 1], color = labelColors, s = 15, alpha = 0.5)
    axs_0_title = axs[0][0].set_title(u'Route vs Game', FontProperties = font)
    axs_0_x = axs[0][0].set_xlabel(u'Route (km/year)', FontProperties = font)
    axs_0_y = axs[0][0].set_ylabel(u'Game (hours/week)', FontProperties = font)
    plt.setp(axs_0_title, size = 9, weight = 'bold', color = 'red')
    plt.setp(axs_0_x, size = 7, weight = 'bold', color = 'black')
    plt.setp(axs_0_y, size = 7, weight = 'bold', color = 'black')
    
    #subplot(0,1) scatter, s : scatter size, alpha : transparency
    axs[0][3].scatter(x = featureMatrix[:,0], y = featureMatrix[:, 2], color = labelColors, s = 15, alpha = 0.5)
    axs_1_title = axs[0][4].set_title(u'Route vs Icecream', FontProperties = font)
    axs_1_x = axs[0][5].set_xlabel(u'Route (km/year)', FontProperties = font)
    axs_1_y = axs[0][6].set_ylabel(u'Icecream (g/week)', FontProperties = font)
    plt.setp(axs_1_title, size = 9, weight = 'bold', color = 'red')
    plt.setp(axs_1_x, size = 7, weight = 'bold', color = 'black')
    plt.setp(axs_1_y, size = 7, weight = 'bold', color = 'black')
    
    #subplot(1,0) scatter, s : scatter size, alpha : transparency
    axs[1][0].scatter(x = featureMatrix[:,1], y = featureMatrix[:, 2], color = labelColors, s = 15, alpha = 0.5)
    axs_2_title = axs[1][0].set_title(u'Game vs Icecream', FontProperties = font)
    axs_2_x = axs[1][0].set_xlabel(u'Game (hours/week)', FontProperties = font)
    axs_2_y = axs[1][0].set_ylabel(u'Icecream (g/week)', FontProperties = font)
    plt.setp(axs_2_title, size = 9, weight = 'bold', color = 'red')
    plt.setp(axs_2_x, size = 7, weight = 'bold', color = 'black')
    plt.setp(axs_2_y, size = 7, weight = 'bold', color = 'black')
    
    #set legend
    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][7].legend(handles = [didntLike, smallDoses, largeDoses])
    axs[1][0].legend(handles = [didntLike, smallDoses, largeDoses])
    plt.show()
 
'''
Function : kNN(test, featureMatrix, labels, k)
    Description : to use kNN algorithm predict test result
    Args:    test    #test vector
            featureMatrix
            labels
            k    k classes
    Rets :    pred_class
'''
def kNN(test, featureMatrix, labels, k):
    row = featureMatrix.shape[0]
    diff = np.tile(test, (row, 1)) - featureMatrix
    sqdiff = diff**2
    dist = sqdiff.sum(axis = 1)
    dist = dist**0.5
    dist_order = dist.argsort()
    classes = {}
    for i in range(k):
        voteLabel = labels[dist_order[i]]
        classes[voteLabel] = classes.get(voteLabel, 0) + 1
    pred = sorted(classes.items(), key = operator.itemgetter(1), reverse = True)
    return pred[0][0]
 
'''
Function : train()
    Description : to train test data and record result
    Args : None
    Rets : None
'''
def train():
    filename = 'info.txt'
    featureMatrix, labels = file2matrix(filename)
    normFeatureMatrix = normalize(featureMatrix)
    inRote = 0.1
    row = normFeatureMatrix.shape[0]
    numTest = int(inRote * row)
    errorcount = 0.0
    for i in range(numTest):
        result = kNN(normFeatureMatrix[i,:], normFeatureMatrix[numTest:row, :], labels[numTest:row], 4)
        print('pred : %d vs real : %d'%(result, labels[i]))
        if result != labels[i]:
            errorcount += 1.0
    print('Error rate : %f %%'%(errorcount / float(numTest)*100))
 
'''
Function : score()
    Description :    to score for input info
        Args :    None
        Rets :    None
'''
def score():
    filename = 'info.txt'
    featureMatrix, labels = file2matrix(filename)
    #get every column minVal
    minVal = featureMatrix.min(0)
    #get every row maxVal
    maxVal = featureMatrix.max(0)
    resultList = ['didntLike', 'smallDoses', 'largeDoses']
    normFeatureMatrix = normalize(featureMatrix)
    route = float(input('Enter your routing precent : '))
    game = float(input('Enter your gaming precent : '))
    iceCream = float(input('Enter your iceCreaming precent : '))
    test = np.array([route, game, iceCream])
    normTest = (test - minVal) / (maxVal - minVal)
    result = kNN(normTest, normFeatureMatrix, labels, 3)
    print('Score : %s'%(resultList[result - 1]))
 
if __name__ == '__main__':
        #visualize()
    #train()
    score()

  测结果与训练结果一致。在visualize（）函数中实现了数据可视化，在train（）函数中完成了测试统计，其对应的误差率为3.00%,即准确率为97.00%（相当不错）。