K Nearest Neighbor

摘要：而产生这种现象的唯一远远，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重的影响到计算结果。

简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

KNN可以说是最简单的分类算法之一，同时，它也是最常见的分类算法之一，注意KNN算法是有监督学习的分类算法，它看起来和另外一个机器学习算法Kmeans有点像（Kmeans是无监督学习算法）。

其工作原理是使用一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是KNN中K的出处，最后使用Majority-Voting（多数表决）选择k个最相似数据中次数出现最多的分类，作为新数据的分类。

K的取值：可以使用Cross Validation(交叉验证)来选取合适的值

我们该如何选择合适的k值呢？通过将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如6：4拆出训练数据和验证数据，从选取一个较小的k值开始，不断增加k的值，然后计算验证集合的方差，最终找到一个比较合适的k值。

距离度量 Metric / Distance Measure:距离度量一般都使用 Euclidean distance（欧氏距离）

二维空间两个点的欧式距离公式如下

分类决策 Deision rule：分类决策即Majority-Voting ，选取票数最多的标签，在回归中通常为k个最邻近点的标签的平均值

电影名称                    打斗镜头    接吻镜头     电影类型
Californla Man                3        104            爱情片
He`s Not Really into Dudes    2        100            爱情片
Beautiful Woman                1        81            爱情片
Kevin Longblade                101        10            动作片
Robo Slayer 3000            99        5            动作片
Ampedll                     98        2            动作片
？                            18        90            未知

首先我们通过 Python 的第三方库进行数据可视化处理

import matplotlib.pyplot as plt
import numpy as np 
import operator

# 已知分类的数据
x1=np.array([3,2,1])
y1=np.array([104,100,81])
x2=np.array([101,99,98])
y2=np.array([10,5,2])
scatter1 = plt.scatter(x1,y1,c="r")
scatter2 = plt.scatter(x2,y2,c="b")

# 求未知数据
x = np.array([18])
y = np.array([90])
scatter3 = plt.scatter(x,y,c="k")

#画图例
plt.legend(handles=[scatter1,scatter2,scatter3],labels=["labelA","labelB","X"],loc = "best" )

plt.show()

KNN近邻算法最核心的部分就是欧式距离的计算，通过计算得到距离最近的k个数的标签，统计出现次数最多的标签，将其赋值给新数据。下面这段代码就是KNN算法最基本的实例。通过传入数据来预测电影的标签是什么！

from numpy import *
import operator
# 电影分类
# 欧式距离求解返回前k个标签 然后汇总出现次数最多的标签
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    # 求inX与数据集中各个样本的欧氏距离
    diffMat = tile(inX, (dataSetSize,1)) - dataSet   # numpy中的tile函数将inX复制为重复的dataSize个行和重复的1列，功能相当于MATLAB中的repmat
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)  # 按照x轴相加
    distances = sqDistances**0.5
    # print(distances)
    sortedDistIndicies = distances.argsort()   # 从小到大排序后，返回索引
    # 这个返回索引是关键  只有理解了这个返回索引才能理解k-nn算法
    # print(sortedDistIndicies)
    # 字典，key存储第i小的标签值，value为标签的次数
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]  # 取第i个小的标签值
        # print(sortedDistIndicies[i])
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1  # 根据标签统计标签次数，如果没找到返回0。统计前k个候选者中标签出现的次数
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # operator.itemgetter(1) 按照第2个元素，即标签出现的次数对classCount从大到小排序
    # print(sortedClassCount)  # 测试结果 [("B", 2), ("A", 1)]
    return sortedClassCount[0][0]  # 返回最终的类别，即标签值key

# 传输数据
def createDataSet():
    group = array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ["A","A","A","B","B","B"]
    return group, labels

# 测试代码
group, labels = createDataSet()
ans = classify0([18,90], group, labels, 3)
print(ans)

>>> A

海伦使用约会网站寻求约会对象，经过一段实践之后，她发现曾交往过三类人：

不喜欢的人

魅力一般的人

极具魅力的人

她希望：

工作日与魅力一般的人约会

周末与极具魅力的人约会

不喜欢的人则直接排除掉

现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。

1. 收集数据：提供文本文件
2. 准本数据：使用Python解析文本文件
3. 分析数据：使用Matplotlib 画二维散点图
4. 训练算法：此步骤不适用与KNN算法，但是也很重要
5. 测试数据：使用海伦提供的部分数据作为测试样本
6. 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型

测试样本与非测试样本的区别在于：
测试样本是以及完成分类的数据，如果测试分类与实际类不同，则标记为一个错误

海伦把这些约会对象的数据存放在文本文件 datingTestSet2.txt 中，总共有1000行，海伦约会的对象主要包含以下3种特征：

每年获得的飞行常客里程数

玩视频游戏所耗费时间百分比

每周消费的冰激凌公升数

文本文件数据格式如下

40920    8.326976    0.953952    3
14488    7.153469    1.673904    2
26052    1.441871    0.805124    1
75136    13.147394    0.428964    1
38344    1.669788    0.134296    1

将文本记录转换为 NUmPy的解析程序

from numpy import zeros
def file2matrix(filename):
    """
    Desc：
        导入训练数据
    Parameters：
        filename：数据文件路径
    return：
        数据矩阵 returnMat 和对应的类别 classLabelVector
    """
    fr = open("datingTestSet2.txt")
    # 获得文件中的数据行的行数
    numberOfLines = len(fr.readlines())
    # 生成对应的空矩阵
    # 例如：zeros(2,3)就是生成一个 2*3 的矩阵，各个位置上全是0
    returnMat = zeros((numberOfLines , 3)) # prepare matrix to return
    classLabelVector = []
    fr = open("datingTestSet2.txt")
    index =0
    for line in fr.readlines():
        # str.strip([chars]) -- 返回已移除字符串头尾指定字符所生成的新字符串
        line = line.strip()
        # 以 	  切割字符串
        listFromLine = line.split("	")
        # 每列的属性数据
        returnMat[index , : ] = listFromLine[0:3]
        # 每列的类别数据，就是 label 标签数据
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
        # 返回数据矩阵 returnMat 和对应的类别 classLabelVector
    print(returnMat,classLabelVector)
    return returnMat,classLabelVector

if __name__=="__main__":
    file2matrix(1)

>>>
[[4.0920000e+04 8.3269760e+00 9.5395200e-01]
 [1.4488000e+04 7.1534690e+00 1.6739040e+00]
 [2.6052000e+04 1.4418710e+00 8.0512400e-01]
 ...
 [2.6575000e+04 1.0650102e+01 8.6662700e-01]
 [4.8111000e+04 9.1345280e+00 7.2804500e-01]
 [4.3757000e+04 7.8826010e+00 1.3324460e+00]] [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3, 2, 1, 2, 3, 2, 3, 2, 3, 2, 1, 3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 1, 2, 3, 3, 3, 1, 1, 1, 1, 2, 2, 1, 3, 2, 2, 2, 2, 3, 1, 2, 1, 2, 2, 2, 2, 2, 3, 2, 3, 1, 2, 3, 2, 2, 1, 3, 1, 1, 3, 3, 1, 2, 3, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 2, 1, 3, 3, 2, 1, 1, 3, 1, 2, 3, 3, 2, 3, 3, 1, 2, 3, 2, 1, 3, 1, 2, 1, 1, 2, 3, 2, 3, 2, 3, 2, 1, 3, 3, 3, 1, 3, 2, 2, 3, 1, 3, 3, 3, 1, 3, 1, 1, 3, 3, 2, 3, 3, 1, 2, 3, 2, 2, 3, 3, 3, 1, 2, 2, 1, 1, 3, 2, 3, 3, 1, 2, 1, 3, 1, 2, 3, 2, 3, 1, 1, 1, 3, 2, 3, 1, 3, 2, 1, 3, 2, 2, 3, 2, 3, 2, 1, 1, 3, 1, 3, 2, 2, 2, 3, 2, 2, 1, 2, 2, 3, 1, 3, 3, 2, 1, 1, 1, 2, 1, 3, 3, 3, 3, 2, 1, 1, 1, 2, 3, 2, 1, 3, 1, 3, 2, 2, 3, 1, 3, 1, 1, 2, 1, 2, 2, 1, 3, 1, 3, 2, 3, 1, 2, 3, 1, 1, 1, 1, 2, 3, 2, 2, 3, 1, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2, 3, 3, 3, 3, 1, 2, 3, 1, 1, 1, 3, 1, 3, 2, 2, 1, 3, 1, 3, 2, 2, 1, 2, 2, 3, 1, 3, 2, 1, 1, 3, 3, 2, 3, 3, 2, 3, 1, 3, 1, 3, 3, 1, 3, 2, 1, 3, 1, 3, 2, 1, 2, 2, 1, 3, 1, 1, 3, 3, 2, 2, 3, 1, 2, 3, 3, 2, 2, 1, 1, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3, 3, 3, 2, 3, 2, 1, 1, 1, 1, 1, 3, 2, 2, 1, 2, 1, 3, 2, 1, 3, 2, 1, 3, 1, 1, 3, 3, 3, 3, 2, 1, 1, 2, 1, 3, 3, 2, 1, 2, 3, 2, 1, 2, 2, 2, 1, 1, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 3, 1, 1, 2, 2, 1, 2, 2, 2, 3, 1, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 1, 3, 2, 3, 3, 2, 2, 1, 1, 1, 2, 1, 2, 2, 3, 3, 3, 1, 1, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 1, 2, 3, 2, 1, 1, 1, 1, 3, 3, 3, 3, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 2, 2, 2, 3, 2, 1, 3, 2, 3, 2, 3, 2, 1, 1, 2, 3, 1, 3, 3, 3, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 1, 3, 3, 2, 2, 2, 3, 1, 2, 1, 1, 3, 2, 3, 2, 3, 2, 3, 3, 2, 2, 1, 3, 1, 2, 1, 3, 1, 1, 1, 3, 1, 1, 3, 3, 2, 2, 1, 3, 1, 1, 3, 2, 3, 1, 1, 3, 1, 3, 3, 1, 2, 3, 1, 3, 1, 1, 2, 1, 3, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 3, 1, 3, 1, 1, 2, 2, 2, 3, 2, 2, 1, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 1, 3, 2, 3, 2, 1, 2, 1, 1, 1, 2, 3, 2, 2, 1, 2, 2, 1, 3, 1, 3, 3, 3, 2, 2, 3, 3, 1, 2, 2, 2, 3, 1, 2, 1, 3, 1, 2, 3, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 2, 2, 2, 3, 1, 3, 1, 2, 3, 2, 2, 3, 1, 2, 3, 2, 3, 1, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 3, 2, 1, 3, 3, 3, 1, 1, 3, 1, 2, 3, 3, 2, 2, 2, 1, 2, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 1, 3, 2, 1, 3, 3, 1, 2, 3, 2, 1, 3, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 1, 1, 2, 1, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 2, 2, 1, 2, 2, 1, 3, 1, 3, 1, 3, 3, 1, 1, 2, 3, 2, 2, 3, 1, 1, 1, 1, 3, 2, 2, 1, 3, 1, 2, 3, 1, 3, 1, 3, 1, 1, 3, 2, 3, 1, 1, 3, 3, 3, 3, 1, 3, 2, 2, 1, 1, 3, 3, 2, 2, 2, 1, 2, 1, 2, 1, 3, 2, 1, 2, 2, 3, 1, 2, 2, 2, 3, 2, 1, 2, 1, 2, 3, 3, 2, 3, 1, 1, 3, 3, 1, 2, 2, 2, 2, 2, 2, 1, 3, 3, 3, 3, 3, 1, 1, 3, 2, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 1, 2, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 1, 3, 3, 2, 3, 2, 3, 3, 2, 2, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 2, 3, 2, 2, 1, 3, 1, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 3, 1, 2, 1, 2, 3, 1, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 1, 3, 3, 3]

下面的代码里面有三分可视化的结果，但是我们可以在 Notebook中很明显的看到每年获取的飞行里程数和玩视频游戏所消耗的时间百分比所构成的坐标图非常的清晰的分成三个部分，这就为我们后续的计算距离分类奠定基础。

from numpy import zeros
import numpy as np
def file2matrix(filename):
    """
    Desc：
        导入训练数据
    Parameters：
        filename：数据文件路径
    return：
        数据矩阵 returnMat 和对应的类别 classLabelVector
    """
    fr = open("datingTestSet2.txt")
    # 获得文件中的数据行的行数
    numberOfLines = len(fr.readlines())
    # 生成对应的空矩阵
    # 例如：zeros(2,3)就是生成一个 2*3 的矩阵，各个位置上全是0
    returnMat = zeros((numberOfLines , 3)) # prepare matrix to return
    classLabelVector = []
    fr = open("datingTestSet2.txt")
    index =0
    for line in fr.readlines():
        # str.strip([chars]) -- 返回已移除字符串头尾指定字符所生成的新字符串
        line = line.strip()
        # 以 	  切割字符串
        listFromLine = line.split("	")
        # 每列的属性数据
        returnMat[index , : ] = listFromLine[0:3]
        # 每列的类别数据，就是 label 标签数据
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
        # 返回数据矩阵 returnMat 和对应的类别 classLabelVector
    # print(returnMat,classLabelVector)
    return returnMat,classLabelVector

# 因为 matplotlib 中不可显示中文，所以使用本机自带的字体进行替换
# 参考链接：https://www.cnblogs.com/pengsky2016/p/8126623.html
# 该链接是本书的该可视化部分的详细讲解 非常不错
from matplotlib.font_manager import FontProperties 
zhfont = FontProperties(fname="C:WindowsFontsmsyh.ttc",size=12)

if __name__=="__main__":
    datingDataMat,datingLabels  =  file2matrix(1)
#     print(datingDataMat)
#     print(datingLabels)

    import matplotlib
    import matplotlib.pyplot as plt
    fig = plt.figure()
    ax = fig.add_subplot(111)
    from numpy import *
    
    datingLabels = np.array(datingLabels)
#     每年获取的飞行里程数-玩视频游戏所消耗的事件百分比
#     datingDataMat[idx_1,0] 中的参数 0 和 1 以及 2 就是我们所选择的横坐标和纵坐标的选取值
#     我们可以根据这三个值的变动来变动我们的坐标轴的选取方法
    idx_1 = np.where(datingLabels==1)
    p1 = ax.scatter(datingDataMat[idx_1,0],datingDataMat[idx_1,1],marker = "*",color = "r",label="1",s=10)
    idx_2 = np.where(datingLabels==2)
    p2 = ax.scatter(datingDataMat[idx_2,0],datingDataMat[idx_2,1],marker = "o",color ="g",label="2",s=20)
    idx_3 = np.where(datingLabels==3)
    p3 = ax.scatter(datingDataMat[idx_3,0],datingDataMat[idx_3,1],marker = "+",color ="b",label="3",s=30)

    plt.xlabel(u"每年获取的飞行里程数", fontproperties=zhfont)
    plt.ylabel(u"玩视频游戏所消耗的事件百分比", fontproperties=zhfont)
    ax.legend((p1, p2, p3), (u"不喜欢", u"魅力一般", u"极具魅力"), loc=2, prop=zhfont)
    plt.show()


    
#     玩视频游戏所消耗的事件百分比-每周消耗的冰激凌公升数
#     datingLabels = np.array(datingLabels)
#     idx_1 = np.where(datingLabels==1)
#     p1 = ax.scatter(datingDataMat[idx_1,1],datingDataMat[idx_1,2],marker = "*",color = "r",label="1",s=10)
#     idx_2 = np.where(datingLabels==2)
#     p2 = ax.scatter(datingDataMat[idx_2,1],datingDataMat[idx_2,2],marker = "o",color ="g",label="2",s=20)
#     idx_3 = np.where(datingLabels==3)
#     p3 = ax.scatter(datingDataMat[idx_3,1],datingDataMat[idx_3,2],marker = "+",color ="b",label="3",s=30)
    
#     plt.xlabel(u"玩视频游戏所消耗的事件百分比", fontproperties=zhfont)
#     plt.ylabel(u"", fontproperties=zhfont)
#     ax.legend((p1, p2, p3), (u"不喜欢", u"魅力一般", u"极具魅力"), loc=2, prop=zhfont)
#     plt.show()
    
    
#     飞行常客里程数 - 每周消耗的冰激凌公升数
#     datingLabels = np.array(datingLabels)
#     idx_1 = np.where(datingLabels==1)
#     p1 = ax.scatter(datingDataMat[idx_1,0],datingDataMat[idx_1,2],marker = "*",color = "r",label="1",s=10)
#     idx_2 = np.where(datingLabels==2)
#     p2 = ax.scatter(datingDataMat[idx_2,0],datingDataMat[idx_2,2],marker = "o",color ="g",label="2",s=20)
#     idx_3 = np.where(datingLabels==3)
#     p3 = ax.scatter(datingDataMat[idx_3,0],datingDataMat[idx_3,2],marker = "+",color ="b",label="3",s=30)

#     plt.xlabel(u"每年获取的飞行里程数", fontproperties=zhfont)
#     plt.ylabel(u"玩视频游戏所消耗的事件百分比", fontproperties=zhfont)
#     ax.legend((p1, p2, p3), (u"不喜欢", u"魅力一般", u"极具魅力"), loc=2, prop=zhfont)
#     plt.show()
    

归一化数据是一个让权重变为统一的过程，比如你要买进10吨铁矿，用的人民币和美元肯定不同，那么这10吨铁矿的价值到底是多少，就需要一个统一的标准来衡量，全世界那么多国家，都要用自己国家的货币去买，到底该付多少就很迷茫。这时，规定用美元统一结算，各国按照本国货币对比美元的汇率，再加上10吨铁矿的美元价值，就可以算出自己应付多少本国货币。

序号     玩视频游戏所耗时间百分比    每年获得的飞行常客里程数    每周消耗的冰激凌公升数    样本分类
1        0.8                    400                        0.5                        1
2        12                    134000                    0.9                        3
3        0                    20000                    1.1                        2
4        67                    32000                    0.1                        2

表2-2给出了提取的四组数据，如果想要计算样本3和样本4之间的距离，可以使用下面的方法：
√((0−67)^2+(20 000 −32 000)^2+(1.1 −0.1)^2 )

我们很容易发现，上面方程中数字差值最大的数学对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响远远大于表2-

在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为0到1或-1到1之间。下面的公式可以将任意取值范围的特征值转换为0到1区间内的值：

newValue = (oldValue - min ) / (max - min)

其中 min 和 max 分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样子做。我们需要在文件中增加一个新的函数 autoNorm()，该函数可以自动将数字特征值转换为0到1的区间。
2中其他两个特征——玩视频游戏和每周消费冰激凌公升数——的影响。而产生这种现象的唯一远远，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重的影响到计算结果。

from numpy import zeros
import numpy as np
def file2matrix(filename):
    """
    Desc：
        导入训练数据
    Parameters：
        filename：数据文件路径
    return：
        数据矩阵 returnMat 和对应的类别 classLabelVector
    """
    fr = open("datingTestSet2.txt")
    # 获得文件中的数据行的行数
    numberOfLines = len(fr.readlines())
    # 生成对应的空矩阵
    # 例如：zeros(2,3)就是生成一个 2*3 的矩阵，各个位置上全是0
    returnMat = zeros((numberOfLines , 3)) # prepare matrix to return
    classLabelVector = []
    fr = open("datingTestSet2.txt")
    index =0
    for line in fr.readlines():
        # str.strip([chars]) -- 返回已移除字符串头尾指定字符所生成的新字符串
        line = line.strip()
        # 以 	  切割字符串
        listFromLine = line.split("	")
        # 每列的属性数据
        returnMat[index , : ] = listFromLine[0:3]
        # 每列的类别数据，就是 label 标签数据
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
        # 返回数据矩阵 returnMat 和对应的类别 classLabelVector
    # print(returnMat,classLabelVector)
    return returnMat,classLabelVector

def autoNorm(dataset):
    """
    Desc:
        归一化特征值，消除特征之间量级不同导致的影响
    parameter:
        dataset:数据集
    return :
        归一化后的数据集 normDataSet , ranges 和 minVals 即最小值与范围，并没有归一化公式
    归一化公式：
        Y=(X-Xmin)/(Xmax - Xmin)
        其中的 min 和 max 分别是数据集中的最小特征值和最大特征值，该函数可以自动将数字特征值转化为0到1的区间
    """
    # 计算每种属性的最大值、最小值、范围
    minVals = dataset.min(0)
    maxVals = dataset.max(0)
    ranges = maxVals - minVals
    # 极差
    normDataSet = zeros(shape(dataset))
    m = dataset.shape[0]
    #生成与最小值之差组成的矩阵
    # 因为特征值矩阵有1000 * 3 个值，而 minVals 和 range 的值都为1x3，
    # 为了解决这个问题，我们使用Numpy库中的tile()函数将变量内容复制成输入矩阵同样大小的矩阵，
    # 注意这是具体特征值相除，而不是矩阵除法，否则还需要使用函数linalg.solve(matA,matB)
    normDataSet = dataset - tile(minVals, (m,1))
    # 将最小值之差除以范围组成矩阵
    normDataSet = normDataSet / tile(ranges, (m,1))
    return normDataSet,range,minVals

if __name__=="__main__":
    datingDataMat,datingLabels  =  file2matrix(1)
    normMat,ranges,minVals = autoNorm(datingDataMat)
    print(normMat)
    print(range)
    print(minVals)

这个是核心内容，即计算各个标记点之间的距离并返回k个标记点内出现次数最多的标签。

对于每一个在数据集中的数据点：
    计算目标的数据点（需要分类的数据点） 与该数据点的距离
    将距离排序：从小到大
    选取k个最短距离
    选取这k个最多的分类类别
    返回该类别来作为目标数据点的预测值

整个训练算法和之前的电影分类的算法是一致的，该算法进化的部分即对数据进行了归一化处理，导致我们传入进去的数据也需要进行归一化处理。

# 训练算法
# 详解 k-nn训练算法 ：https://www.cnblogs.com/BaiYiShaoNian/p/4567446.html
def classify0(inX,dataSet,labels,k):
    """
    :param inX:  用于分类的输入向量
    :param dataSet: 训练样本集合
    :param labels: 标签向量
    :param k:  K-NN中的k
    """
    # shape 是array的属性 ，描述一个多维数组的维度
    dataSetSize = dataSet.shape[0]
    # 距离度量 度量公式为欧式距离
    """
    tile(inX,(dataSetSize,1)) : 把 inX 二维数组化，dataSetSize 表示生成数组后的行数
    1 表示列的倍数，整个这一行代表表示前一个二维数组矩阵的每一个元素减去后一个数组对应的元素值
    这样子就实现了矩阵之间的减法，简单方便
    """
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    # axis=1 表示矩阵中行之间数的求和 axis=0表示列之间数的求和
    distances = sqDistances ** 0.5

    # 将距离排序：从小到大
    # 关键是传回的是位置索引 而这个索引就可以得到在标签中所对应位置的标签
    sortedDistIndicies = distances.argsort()
    #选取前k个最短距离，选取这k个中最多的分类类别
    classCount = {}
#     print(labels)
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        # 这一行是python语法 看不懂基础问题
        # get()该方法是访问字典项的方法，即访问下标为 voteIlabel的项，如果没有这一项，那么初始值为0
        # 然后把这一项的值加1
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    import operator
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),reverse = True)
    return sortedClassCount[0][0]

该函数的代码是统计该KNN算法的实现效果，抽取一部分的数据作为数据集，进行测试然后统计测试错误的百分比

# 测试分类错误，错误分辨个数
def datingClassTest():
    hoRatio = 0.08      # 随机挖去 10% 的数据作为测试集
    datingDataMat,datingLabels = file2matrix("datingTestSet2.txt")       # 加载数据文件
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)  # 随机挖去的行数
    errorCount = 0.0
    for i in range(numTestVecs):
        # 前numTestVecs条作为测试集（一个一个测试），后面的数据作为训练样本，训练样本的标签，3个近邻
        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
    print("The number of errr is: %d" % int(errorCount))
    print("The total error rate is: %f" % (errorCount / float(numTestVecs)))
>>>The number of errr is: 2
>>>The total error rate is: 0.025000

直接在主函数中使用该函数调用数据预处理函数传入数据、调用归一化数据处理函数归一化数据、调用训练算法传入数据进行预测，最后输出算法判断后的结论。

# 实践算法
def validateTest():
    resultList = ["not at all", "in small doses", "in large doses"]
    percentTats = float(input("percentage of time spent playing video games ?"))
    ffMiles = float(input("frequent filer miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
#     print(str(inArr),str(minVals),str(ranges),normMat,datingLabels)
    # 为什么传入的值需要进行 如下操作呢 (inArry - minVals)/range
    # 因为我们之前传入的值都是进行过归一化的
    # 但是如果直接传入值会过大 所以我们在前面的归一化操作中将两个参数传过来就是为了这里使用
    # 但是这里传入的测试参数也是一个1x3的举证 所有 minVals 和 ranges 不需要进行 tile化
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print("You will probably like this person: ", resultList[classifierResult - 1])

    # 主函数
if __name__ == "__main__":
    # 实践算法
    validateTest()

>>>percentage of time spent playing video games ?10
>>>frequent filer miles earned per year?10000
>>>liters of ice cream consumed per year?0.5
>>>You will probably like this person:  in small doses

from numpy import zeros
import numpy as np
from numpy import *
import operator
# 数据预处理
def file2matrix(filename):
    """
    Desc：
        导入训练数据
    Parameters：
        filename：数据文件路径
    return：
        数据矩阵 returnMat 和对应的类别 classLabelVector
    """
    fr = open("datingTestSet2.txt")
    # 获得文件中的数据行的行数
    numberOfLines = len(fr.readlines())
    # 生成对应的空矩阵
    # 例如：zeros(2,3)就是生成一个 2*3 的矩阵，各个位置上全是0
    returnMat = zeros((numberOfLines, 3))  # prepare matrix to return
    classLabelVector = []
    fr = open("datingTestSet2.txt")
    index = 0
    for line in fr.readlines():
        # str.strip([chars]) -- 返回已移除字符串头尾指定字符所生成的新字符串
        line = line.strip()
        # 以 	  切割字符串
        listFromLine = line.split("	")
        # 每列的属性数据
        returnMat[index, :] = listFromLine[0:3]
        # 每列的类别数据，就是 label 标签数据
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
        # 返回数据矩阵 returnMat 和对应的类别 classLabelVector
    # print(returnMat,classLabelVector)
    return returnMat, classLabelVector


# 因为 matplotlib 中不可显示中文，所以使用本机自带的字体进行替换
# 参考链接：https://www.cnblogs.com/pengsky2016/p/8126623.html
# 该链接是本书的该可视化部分的详细讲解 非常不错
from matplotlib.font_manager import FontProperties
zhfont = FontProperties(fname="C:WindowsFontsmsyh.ttc", size=12)

# 归一化特征值
def autoNorm(dataset):
    """
    Desc:
        归一化特征值，消除特征之间量级不同导致的影响
    parameter:
        dataset:数据集
    return :
        归一化后的数据集 normDataSet , ranges 和 minVals 即最小值与范围，并没有归一化公式
    归一化公式：
        Y=(X-Xmin)/(Xmax - Xmin)
        其中的 min 和 max 分别是数据集中的最小特征值和最大特征值，该函数可以自动将数字特征值转化为0到1的区间
    """
    # 计算每种属性的最大值、最小值、范围
    minVals = dataset.min(0)
    maxVals = dataset.max(0)
    ranges = maxVals - minVals
    # 极差
    normDataSet = zeros(shape(dataset))
    m = dataset.shape[0]
    #生成与最小值之差组成的矩阵
    # 因为特征值矩阵有1000 * 3 个值，而 minVals 和 range 的值都为1x3，
    # 为了解决这个问题，我们使用Numpy库中的tile()函数将变量内容复制成输入矩阵同样大小的矩阵，
    # 注意这是具体特征值相除，而不是矩阵除法，否则还需要使用函数linalg.solve(matA,matB)
    normDataSet = dataset - tile(minVals, (m,1))
    # 将最小值之差除以范围组成矩阵
    normDataSet = normDataSet / tile(ranges, (m,1))
    return normDataSet,ranges,minVals

# 训练算法
# 详解 k-nn训练算法 ：https://www.cnblogs.com/BaiYiShaoNian/p/4567446.html
def classify0(inX,dataSet,labels,k):
    """
    :param inX:  用于分类的输入向量
    :param dataSet: 训练样本集合
    :param labels: 标签向量
    :param k:  K-NN中的k
    """
    # shape 是array的属性 ，描述一个多维数组的维度
    dataSetSize = dataSet.shape[0]
    # 距离度量 度量公式为欧式距离
    """
    tile(inX,(dataSetSize,1)) : 把 inX 二维数组化，dataSetSize 表示生成数组后的行数
    1 表示列的倍数，整个这一行代表表示前一个二维数组矩阵的每一个元素减去后一个数组对应的元素值
    这样子就实现了矩阵之间的减法，简单方便
    """
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    # axis=1 表示矩阵中行之间数的求和 axis=0表示列之间数的求和
    distances = sqDistances ** 0.5

    # 将距离排序：从小到大
    # 关键是传回的是位置索引 而这个索引就可以得到在标签中所对应位置的标签
    sortedDistIndicies = distances.argsort()
    #选取前k个最短距离，选取这k个中最多的分类类别
    classCount = {}
#     print(labels)
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        # 这一行是python语法 看不懂基础问题
        # get()该方法是访问字典项的方法，即访问下标为 voteIlabel的项，如果没有这一项，那么初始值为0
        # 然后把这一项的值加1
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    import operator
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1),reverse = True)
    return sortedClassCount[0][0]

# 测试分类错误，错误分辨个数
def datingClassTest():
    hoRatio = 0.08      # 随机挖去 10% 的数据作为测试集
    datingDataMat,datingLabels = file2matrix("datingTestSet2.txt")       # 加载数据文件
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)  # 随机挖去的行数
    errorCount = 0.0
    for i in range(numTestVecs):
        # 前numTestVecs条作为测试集（一个一个测试），后面的数据作为训练样本，训练样本的标签，3个近邻
        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
    print("The number of errr is: %d" % int(errorCount))
    print("The total error rate is: %f" % (errorCount / float(numTestVecs)))

# 实践算法
def validateTest():
    resultList = ["not at all", "in small doses", "in large doses"]
    percentTats = float(input("percentage of time spent playing video games ?"))
    ffMiles = float(input("frequent filer miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
#     print(str(inArr),str(minVals),str(ranges),normMat,datingLabels)
    # 为什么传入的值需要进行 如下操作呢 (inArry - minVals)/range
    # 因为我们之前传入的值都是进行过归一化的
    # 但是如果直接传入值会过大 所以我们在前面的归一化操作中将两个参数传过来就是为了这里使用
    # 但是这里传入的测试参数也是一个1x3的举证 所有 minVals 和 ranges 不需要进行 tile化
    classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
    print("You will probably like this person: ", resultList[classifierResult - 1])

    # 主函数
if __name__ == "__main__":
    # 实践算法
    validateTest()
    # 测试分类错误：判断程序的可行性
    print("这是输出判断算法优越性的结果：")
    datingClassTest()