K近邻分类器（KNN）（4-2）

K近邻分类器（K-Nearest Neighbor，简称KNN）是一种基本的机器学习分类算法。它的工作原理是：在特征空间中，如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别。

具体来说，KNN算法首先计算待分类样本与其他所有样本的距离，然后按照距离的递增关系进行排序，选取距离最小的K个样本，最后根据这K个样本的类别通过多数投票等方式进行预测。当K=1时，KNN算法又称为最近邻算法。

KNN算法的优点包括：

思想简单，易于理解和实现。
对数据分布没有假设，完全基于距离度量进行分类。
适用范围广，可以用于多分类问题。
然而，KNN算法也存在一些缺点：

对距离度量函数和K值的选择敏感，不同的距离度量函数和K值可能会产生不同的分类结果。
计算量大，需要计算待分类样本与所有训练样本的距离。
内存需求大，需要存储所有的训练样本。
可解释性不强，无法给出决策边界等直观的解释。
KNN算法的应用场景非常广泛，包括但不限于：

垃圾邮件识别：可以将邮件分为“垃圾邮件”或“正常邮件”两类。
图像内容识别：由于图像的内容种类可能很多，因此这是一个多类分类问题。
文本情感分析：既可以作为二分类问题（褒贬两种情感），也可以作为多类分类问题（如十分消极、消极、积极、十分积极等）。

 一、问题引入

海伦一直使用在线约会网站寻找适合自己的约会对象。她曾交往过三种类型的人：

-  喜欢的人

- 一般喜欢的人

- 非常喜欢的人

这些人包含以下三种特征

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

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

3. 每周消费的冰淇淋公升数

该网站现在需要尽可能向海伦推荐她喜欢的人，需要我们设计一个分类器，根据用户的以上三种特征，识别出是否该向海伦推荐。

二、需求概要分析

根据问题，我们可知，样本特征个数为3，样本标签为三类。现需要实现将一个待分类样本的三个特征值输入程序后，能够识别该样本的类别，并且将该类别输出。

三、程序结构设计说明

根据问题，可以知道程序大致流程如下。


其输入数据应包含三个值，输出应为喜欢，一般，不喜欢，三个中的一个。

四、K近邻算法的一般流程

1. **数据准备：**这包括收集、清洗和预处理数据。**预处理可能包括归一化或标准化特征**，以确保所有特征在计算距离时具有相等的权重。


我们很容易发现，当计算样本之间的距离时数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远大于上表中其他两个特征-玩视频游戏所耗时间占比和每周消费冰淇淋公斤数的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

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

$$v_{new}=(v_{old}-v_{min})(v_{max}-v_{min})$$

2. **选择距离度量方法**：确定用于比较样本之间相似性的度量方法，常见的如欧几里得距离、曼哈顿距离等

3. **确定K值：选择一个K值**，即在分类或回归时应考虑的邻居数量。这是一个超参数，可以通过交叉验证等方法来选择最优的K值。

4. **找到K个最近邻居**：对于每一个需要预测的未标记的样本：

- 计算该样本与训练集中所有样本的距离。

- 根据距离对它们进行排序。

- 选择距离最近的K个样本

5. **预测**：

   - 对于**分类任务**：查看K个最近邻居中最常见的类别，作为预测结果。例如，如果K=3，并且三个最近邻居的类别是[1, 2, 1]，那么预测结果就是类别1。

   - 对于**回归任务**：预测结果可以是K个最近邻居的平均值或加权平均值。

6. **评估：**使用适当的评价指标（如准确率、均方误差等）评估模型的性能。

7. **优化：**基于性能评估结果，可能需要返回并调整某些参数，如K值、距离度量方法等，以获得更好的性能。

五、算法实现

创建一个kNN.py文件，将如下代码加入到kNN.py中，之后的相关代码也是加入到这个文件中完成实验。

def classify0(inx,dataset,labels,k): #inx为用于分类的输入量，dataset为训练样本集，labels为标签向量，k表示用于选择最近邻邻居的数目
    datasetsize=dataset.shape[0]  #shape 是 NumPy 数组的属性，用于获取数组的形状，对于二维数组，返回一个元组 (行数, 列数)，因此 dataset.shape[0] 返回数据集的行数，即样本数量。
    diffmat=tile(inx,(datasetsize,1))-dataset #这里将输入数据 inx 重复拼接 datasetsize 行，1 列，以便与数据集进行逐元素相减。得到了输入数据与数据集中每个样本的差值矩阵。
    sqdiffmat=diffmat**2  #对差值矩阵中的每个元素进行平方操作，得到平方差值矩阵。
    sqdistances=sqdiffmat.sum(axis=1)  #计算平方欧式距离，即将平方差值矩阵的每一行元素相加，得到每个样本与输入数据的平方欧式距离。指定了沿着每行（axis=1 表示行）的方向进行求和，得到每行元素的总和。这里的每行对应于数据集中的一个样本，因此结果是一个包含了每个样本与输入数据 inx 之间平方欧式距离的数组 sqdistances。
    distances=sqdistances**0.5 #对平方欧式距离进行开方，得到每个样本与输入数据的欧式距离。
    sorteddistindicies=distances.argsort() #对欧式距离进行排序，并返回排序后的索引，索引值表示距离最近的样本在原始数据集中的位置。
    classcount={} #初始化一个空字典，用于统计每个类别的票数。
    for i in range(k):
        voteilabel=labels[sorteddistindicies[i]] #从 labels 列表中获取距离最近的前 k 个样本的标签，并将其存储在 voteilabel 变量中。
        classcount[voteilabel]=classcount.get(voteilabel,0)+1  #统计每个标签的出现次数。如果标签 voteilabel 已经在字典 classcount 中，就将其对应的计数值加一；如果不在，就添加一个新的键值对，值初始化为 0，并加一。
    sortedclasscount=sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)  #对字典 classcount 中的项按照值（票数）从大到小排序，operator.itemgetter(1) 表示按照值进行排序，reverse=True 表示降序排序。
    return sortedclasscount[0][0] #返回票数最多的类别，即距离最近的 k 个样本中所属类别最多的类别作为分类结果。

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

使用k-近邻算法改进约会网站的配对效果

流程：

（1）收集数据：提供文本文件。

（2）准备数据：使用Python解析文本文件。

（3）分析数据：使用Matplotlib画二维扩散图。

（4）训练算法：此步骤不适用于k-近邻算法。

（5）测试算法：使用海伦提供的部分数据作为测试样本。

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

（6）使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己           喜欢的类型。

准备数据：从文本文件中解析数据

在文本文件datingTestSet2.txt中存放了海伦收集的约会数据，包含三种特征：每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数。

文件中每个样本数据占据一行，前三个属性为特征，末尾数字表示喜欢程度，共1000行。

在我们的kNN.py中加入函数file2matrix对datingTestSet文件进行数据解析,代码如下：

问题与解决：（1）运行过程中会报错，文件无法打开。 解决：datingTestSet2.txt文件要与当前的kNN.py在一个包中filename才能按书上的直接输入相对路径。否则要输入文件的完整路径。

通过这段代码我们可以获取到海伦提供数据对应的特征矩阵和每个样本对应标签构成的列表

接着打开Python命令行环境进行验证，在Python命令行环境中输入下面命令：

我们将得到文件分析后返回的特征值矩阵：

再输入： datinglabels

 我们可以得到每个样本对应的标签：

至此，数据解析工作完成。

问题与解决：

（1）代码运行过程中会报错，文件无法打开。

解决：datingTestSet2.txt文件要与当前的kNN.py在一个包中filename才能按书上的直接输入相对路径。否则要输入文件的完整路径。

（2） 打开Python命令行环境有问题。 

解决：Linux/Max OS终端内可以直接输入python，在Windows命令提示符下需要输入自己python所存放的地址路径例如（C:\Python2.6\python.exe),若不知道自己python所存放路径可以通过输入‘where python’进行查看。若不能使用也可以打开一个新的py文件import kNN进行相应操作如：

分析数据：使用Matplotlib创建散点图

使用Matplotlib制作原始数据的散点图，这里以每年获取得的飞行常客里程数和玩视频游戏所耗时间百分比两个特征值为例提供实现代码：

import kNN
import numpy
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']  #确保在图中显示中文时不会出现乱码
datingdatamat,datingglabels=kNN.file2matrix('C:\\Users\\86180\\Desktop\\MLiA_SourceCode\\machinelearninginaction\\Ch02\\datingTestSet2.txt')
n = 1000 #样本总数
x1 = []; y1 = []  #存放不喜欢数据点对应的横纵坐标
x2 = []; y2 = []  #存放魅力一般数据点对应的横纵坐标
x3 = []; y3 = []  #存放极具魅力数据的对应的横纵坐标
 
for i in range(n):  #循环判断每个样本属于哪个类型并存放入相应的横纵坐标
    if(datingglabels[i]==1):  #表示不喜欢的标签类
        x1.append(datingdatamat[i,0])  #在特征矩阵中找到改标签类对应的‘每年获得的飞行常客里程数’对应的特征值放入该类对应的横轴坐标数组中
        y1.append(datingdatamat[i,1])  #在特征矩阵中找到改标签类对应的‘玩视频游戏所耗时间百分比’对应的特征值放入该类对应的横轴坐标数组中
 
    elif(datingglabels[i]==2):  #表示魅力一般的标签类
        x2.append(datingdatamat[i,0])
        y2.append(datingdatamat[i,1])
    elif(datingglabels[i]==3):  #表示极具魅力的标签类
        x3.append(datingdatamat[i,0])
        y3.append(datingdatamat[i,1])
 
fig = plt.figure()  #创建一个新的图形
ax = fig.add_subplot(111)  #添加一个子图，参数(111)表示1行1列的子图中的第一个位置
type1 = ax.scatter(x1, y1, s=20, c='red')   #绘制类别1的数据点，颜色为红色，标记大小为20
type2 = ax.scatter(x2, y2, s=30, c='green')  #绘制类别2的数据点，颜色为绿色，标记大小为30
type3 = ax.scatter(x3, y3, s=50, c='blue')  #绘制类别3的数据点，颜色为蓝色，标记大小为50
ax.legend([type1, type2, type3], ["不喜欢", "魅力一般", "极具魅力"])  #添加图例，将每个类别的散点标记与其对应的类别名称关联起来
plt.xlabel('每年获取得的飞行常客里程数')  #添加x轴标签
plt.ylabel('玩视频游戏所耗时间百分比')  #添加y轴标签
plt.show()  #显示绘制的图形

这里的图用每年获取得的飞行常客里程数作为横坐标，玩视频游戏所耗时间百分比作为纵坐标，其他相关代码解释如代码中的注释所示。

运行之后我们可以得到这两个特征值对应的相关散点图：

同理我们也可以得到另外两幅散点图，（每年获得的飞行常客里程数，每周消费的冰淇淋公升数）和（玩视频游戏所耗时间百分比，每周消费的冰淇淋公升数） 图例如下：

结论：通过Matplotlib创建散点图我们可以直观的观察到不同数据样本点标签类与数据特征值的关联，过观察散点图的分布，可以发现数据是否存在明显的聚类趋势。不同的类别是否在特征空间中形成了不同的聚类区域，或者它们是否有重叠部分。每个散点图显示两个特征之间的关系，以便更好地理解它们之间的线性或非线性关系。在分类问题中，散点图可以帮助我们直观地理解分类器的决策边界。我们可以将不同类别的数据点绘制在同一张图中，并在图中绘制分类器的决策边界，以便观察分类器对不同类别的区分能力。例如，极具魅力的数据点聚集分布在每年获得的飞行常客里程数范围2000~4000、玩视频游戏所耗时间百分比范围8~13等。

问题与解决：

（1）Python命令行环境中无法使用‘fig = plt.figure()’

解决：重新打卡了一个.py文件，在.py文件中输入相同代码能够正常运行

（2）修改图像的x、y轴标签时出现乱码。 

解决：网络上查询了相关资料信息，发现在开头加上plt.rcParams['font.sans-serif'] = ['SimHei']这段代码后可以确保在图中显示中文时不会出现乱码。

2.3  准备数据：归一化数值
1. 原因：我们很容易发现，在计算各个样本点之间的距离时，数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对应计算结果的影响将远远大于其他两个特征的影响。但这三种特征是同等重要的，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果。

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

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

其中min和max分别是数据集中的最小特征值和最大特征值。

3.代码实现：

def autoNorm(dataset):
    minvals=dataset.min(0) #这一行计算了数据集 dataset 每一列的最小值。min 函数中的参数 0 表示沿着第一个轴（列）计算最小值。
    maxvals=dataset.max(0) #这行计算了数据集 dataset 每一列的最大值
    ranges=maxvals-minvals #这一行计算了每个特征（列）的取值范围，通过将每列的最大值减去最小值得到。  前三句返回的结果都是NumPy数组类型
    normdataset=zeros(shape(dataset))  #这行初始化了一个数组 normdataset，其形状与输入的 dataset 相同，用零填充。这个数组将用来存储归一化后的值。
    m=dataset.shape[0]  #这行获取了 dataset 数组的行数，并将其赋值给变量 m
    normdataset=dataset-tile(minvals,(m,1))  #从 dataset 数组的每个元素中减去对应的最小值 minvals。tile 函数用于创建与 dataset 相同形状的矩阵，其中每行都与 minvals 相同。
    normdataset=normdataset/tile(ranges,(m,1))  #这行将 normdataset 中的每个元素除以对应特征的范围（由 ranges 指定）。同样，tile 函数用于创建与 dataset 相同形状的矩阵，其中每行都与 ranges 相同。
    return normdataset,ranges,minvals  #返回归一化后的数据集 (normdataset)、每个特征的范围 (ranges)，以及每个特征的最小值 (minvals)

相关理解如代码注释中所示。

4.效果演示：

在python命令提示符中输入：

可以得到normmat即归一化后的特征值数据集：

再向命令提示符中分别输入ranges、minvals就可以得到每个特征的范围 (ranges)，以及每个特征的最小值 (minvals)：

5. 结论：数据归一化是将数据按比例缩放，使其落入特定的范围内

优点：

消除量级影响：使得不同特征具有相同的量级，避免因特征量级差异导致的模型参数难以确定或模型表现不佳的问题。

提高模型稳定性：归一化可以减少特征值的波动范围，使得模型对数据中的噪声和异常值的影响减弱，提高了模型的稳定性。

缺点：

信息损失：对数据进行归一化可能会导致一定程度的信息损失，因为归一化后，原始数据的分布和变异性可能发生变化，丢失了部分数据的原始含义。

对异常值敏感：某些归一化方法对异常值敏感，如最小-最大缩放，如果数据中存在异常值，可能会导致归一化后的结果不准确。

 但在这次机器学习的约会网站改进的实验中，归一化处理帮助我们削弱每年获取的飞行常客里程数对于计算结果的过大影响，使得三个特征值是等权重影响。虽然增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。

2.4  测试算法：作为完整程序验证分类器
1.制作分类器：

机器学习算法一个重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为戌年样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。

代码里我们定义一个计数器变量，每次分类器错误地分类数据，计数器就加1，程序执行完成之后计数器的结果除以数据点总数即是错误率，来检测分类器的性能。

代码实现：

def datingclasstest():
    horatio=0.10 #设置测试数据集的比例，这里设置为 10%
    datingdatamat,datinglabels=file2matrix('C:\\Users\\86180\\Desktop\\MLiA_SourceCode\\machinelearninginaction\\Ch02\\datingTestSet2.txt') #调用 file2matrix 函数读取数据集，并将特征矩阵和标签分别赋值给 datingdatamat 和 datinglabels。
    normat,ranges,minvals=autoNorm(datingdatamat) #对数据集进行归一化处理，并返回归一化后的数据集、范围和最小值。
    m=normat.shape[0] #获取归一化后的数据集的行数
    numtestvecs=int(m*horatio) #计算测试向量的数量，即测试数据集的样本数
    errorcount=0.0 #初始化错误分类计数器。
    for i in range(numtestvecs): #遍历测试数据集。
        classifierresult=classify0(normat[i,:] ,normat[numtestvecs:m,:],datinglabels[numtestvecs:m],3)  #调用 classify0 函数对测试数据进行分类，并返回分类结果。normat[i,:]是测试数据点，normat[numtestvecs:m,:]剩余百分之九十的归一化后数据特征集，datinglabels[numtestvecs:m]是剩余百分之九十的标签，3是3NN.
        print("the classifier came back with: %d, the real answer is : %d" % (classifierresult, datinglabels[i]))
        if(classifierresult!=datinglabels[i]):errorcount+=1.0  #如果分类结果与真实标签不一致，则错误分类计数器加一。
    print("the total error rate is: %f"%(errorcount/float(numtestvecs)))  #错误分类数量与总测试样本数之比作为错误率