基于Python进行模式识别（K 近邻法）【100012071】

# 模式识别 K 近邻法 ## 一、最近邻、k 近邻算法介绍 ### 1.1 介绍 以每个训练样本为一个子类，不同类的两个样本之间用最小距离作为分类准则。显然这时就没有必要事先用所有两两样本间的分类面构造出分段线性分类面，而是可以在拿到一个待分类的样本后，通过判断它到两类样本的距直来进行决策。这就是最近邻法。 最近邻法就是源于这样一种直观的想法：对于一个新样本，把它逐一与已知样本比较，找出距离新样本最近的已知样本，该样本的类别作为新样本的类别。 在很多情况下，把决策建立在一个最近的样本上有一定风险，当数据分布复杂或数据中噪声严重时尤其如此。一种很自然的改进就是引人投票机制选择前若干个离新样本最近的已知样本，用它们的类别投票来决定新样本的类别，这种方法称作 k-近邻法，因为人们习惯上把参加投票的近邻样本的个数记作 k。显然，最近邻法可以看作是 k 近邻法的特例。 ### 1.2 近邻法的形式化表示 （1）最近邻 已知样本集，其中，是样本i的特征向量，是它对应的类别，设c个类，即。定义两个样本简得距离量度，比如可以采用欧氏距离。对未知样本，求中与之距离最近的样本，设为（对应的类别为)，即：  将决策为类。 如果写成判别函数的形式，类的判别函数可以写作：  决策规则为各类的判别函数比较大小，即：  错误率：最坏不会超过两倍的贝叶斯错误率，而最好则有可能接近或达到贝叶斯错误率。 注：根据实际问题，可以采用不同的距离度量。 （2）k 近邻 设有N个已知样本分属于c个类，，考察新样本在这些样本中的前个近邻，设有个属于类，则类的判别函数就是：  决策规则是：  错误率：当 k 趋于无穷大时，k 近邻法就达到了贝叶斯错误率。 注：在两分类问题中，通常需要选择 k 为奇数，以避免出现两类的票相等的情况 ## 二、实验数据集介绍 ### 2.1 Iris 数据集介绍  ### 2.2 Sonar 数据集介绍  ## 三、实验设置 对两类数据集，均分别采用最近邻、k 近邻两种方法进行分类，计算准确率，最后将 k 值、测试比例进行变换，观察分类结果。 两类数据集处理方法具有相似性，因此实验设置基本一致，具体如下： 1、读取数据信息。首先从数据集文件（iris.data、sonar.all-data）中读取数据，将读取到的数据按照一定比例（例如：1/5 的数据用于测试，4/5 的数据用于训练）随机存放到训练集和测试集中，再将训练集中数据按标签分类（Iris 分三类、sonar 分两类）。 2、求解样本间距离。依次遍历测试集中的元素，将测试数据分别与训练集中的每一组数据求解欧氏距离（还可更换其他距离），将所有距离数据保存。 3、寻找最小距离/分类别投票，求分类结果。 （1）最近邻法：直接遍历即可求出最小距离，该最小距离对应的样本标签即为分类结果。 （2）k 近邻法：将训练集数据的标签和对应距离依据距离进行排序（递增），取前 k 项数据，统计出现次数最多的标签数，该标签即为分类结果。 4、 统计所有测试数据分类的正确、错误数量，计算准确率。 5、重复 1-4 步 20 次，计算平均准确率，绘图显示。 6、更改 k 值，观察准确率变化。 ## 四、实验结果展示与分析 ### 4.1 Iris 数据集分类结果分析  1、首先使用最近邻法将 Iris 测试集进行分类，默认使用 1/5 的数据用于测试，4/5 的数据用于训练，重复 20 次后，分类精确度如下： 上述结果可以看出：20次最近邻法iris数据集分类平均准确率96.3%，由于测试样本较少，还出现了几次准确率为1的情况。  2、使用 k 近邻法将 Iris 数据集分类，设置 k=5，其余设置与上述一致，分类结果如下：  上述结果可以看出：使用 k 近邻法（k=5)的分类结果与最近邻法相比，精准度略有提高，但相差不多。平均准确率为 96.5%。 3、随后改变 k 的值（1-20，对应图中 0-19）进行测试，分类结果如下： 上述结果可以看出：k 取值在 12 之前准确率均在较高水平，由于�