基于USPS和UCI数据集的近邻法分类

一、问题描述

       使用近邻算法进行分类问题的研究，并在USPS手写体数据集和UCI数据集上的iris和sonar数据上验证算法的有效性，并分别对近邻法中k近邻算法、最近邻算法和Fisher线性判别进行对比分析。

二、数据集说明

2.1 USPS手写体

       USPS，美国邮政署，是美国联邦政府的独立机构，其中的手写体是为了识别邮政单上的数字而构建的数据集，其中共有9298个手写数字图像，其中7291个用于训练，2007个用于测试。
       以下为数据展示：

       其中每个数据都是一个16*16=256的矩阵，以下为训练集第一个数据展示，其标签为“6”。

       将数据用matplotlib展示为图片格式：

       将数据转化为二值：

       以图片格式展示：

2.2 UCI数据集

       UCI数据库是加州大学欧文分校(University of CaliforniaIrvine)提出的用于机器学习的数据库，这个数据库目前共有488个数据集，其数目还在不断增加，UCI数据集是一个常用的标准测试数据集。
       每个数据文件（.data）包含以“属性-值”对形式描述的很多个体样本的记录。对应的.info文件包含的大量的文档资料。有些文件_generate_ databases；他们不包含*.data文件。作为数据集和领域知识的补充，在utilities目录里包含了一些在使用这一数据集时的有用资料。
       下表为Iris数据集部分数据展示：

三、近邻法原理分析

3.1 KNN算法简介

       K近邻算法是指给定一个未知标签的样本，在已有的训练样本集中，找到与该待分类的样本距离最邻近的k个训练样本，随后根据这k个训练样本的类别，通过一定的决策规则决定该未知样本的类别。具体流程如下：
       设训练样本集$D=(x_1,y_1),(x_2,y_2),\dots \dots ,(x_n,y_n)$，其中$x_i\in X\subseteq R^n$为样本的特征向量，$y_i$为样本标签，i=1,2,…,m,S为类别个数。对于待分类的未知样本x，求解所属的类y的步骤如下：
       （1）首先确定一种距离度量，计算未知样本与训练样本集中每个样本的距离，选出距离最小，即与x最近邻的k个点，这k个点集合记作$N_k(x)$。
       （2）在$N_k(x)$中，对每个样本的样本标签投票决定x的类别y，例如少数服从多数：
$$y=arg[ma{x}_j[\sum (x_i\in N_k(x)[I(y_i=c_j)]]],i=1,2,\dots ,m;j=1,2,\dots ,S$$
       当k=1时，k近邻又称为最近邻算法。显然的，对于输入的待分类样本x，其类别为在训练样本集与之距离最小的训练样本类别。
       K近邻法的模型有三个要素，分别是距离度量，k值大小和分类决策规则。

3.2 KNN算法模型

       K近邻法模型中，当给定训练样本集，且确定了距离度量，k值大小以及分类决策规则时，对于任意未知标签的样本，通过k近邻法模型，它的预测类别是唯一的。
       K近邻法模型根据上述要素进行建模，相当于把特征空间完备划分为一个个子空间，每个子空间都有唯一所属类别。在特征空间中，对于每个训练样本点x_i都有一个单元，即相比于其他训练样本，距离当前训练样本更近的所有点组成的区域。对落入一个单元的所有样本点，其类别都会与该单元所属类别一样。

3.3 距离度量

       两个样本的特征距离反映了彼此之间的相似程度。常见的距离度量有欧式距离、具有一般性的L_p距离和曼哈顿距离等。
       假设样本空间X属于n维实数向量空间$R^n$，则其$L_p$距离定义为：

       其中，p大于等于1。当p=2时，称为欧式距离：

       当p=1时，称为曼哈顿距离：

       当p=无穷大，他代表各个坐标距离中的最大值，即

3.4 KNN算法中K值的选择

       K值的选择对K近邻是及其重要的，如果K值较小，可通过在较小的近邻域中的训练样本进行预测，因为领域小，代表其中训练样本与未知样本的特征最为相似，而而其余的训练样本对于预测不起作用，所以预测的近似误差会减小。但随之而来的问题是，若近邻的训练样本点含有噪声，并且邻域较小，难以通过其余样本矫正分类结果，则预测的估计误差会增大。换句话说，k值越小，k近邻模型就越复杂，更容易产生拟合现象。
       如果k值较大，可通过在较大邻域中的训练样本进行预测。相比于k值较小，其优点是减少了预测的估计误差，缺点是增大了预测的近似误差。因为此时与未知样本较远的训练样本也参与预测，有可能产生错误预测。因此k值较大，k近邻模型会变得简单，将忽略大量的训练样本中的有用信息。
       在实际应用中，k值一般先取的较小值，然后使用交叉验证法选取最优的k值。

3.5 KNN算法分类决策规则

       K近邻算法中最后一步是利用分类决策规则对未知样本进行分类。其中最常见的分类决策规则是对数表决：已知未知样本的k个近邻训练样本，统计其中最多的类别作为未知样本的类别，即少数服从多数。

四、问题求解

五、结果分析

5.1 分析不同K值下的分类准确率

       USPS数据集

       Iris数据集

       Sonar数据集

5.2 分析不同的距离度量对分类准确率的影响

5.2.1 欧式距离

       两个n维向量之间的欧氏距离：

5.2.2 曼哈顿距离

       两个n维向量之间的曼哈顿距离：

5.2.3 切比雪夫距离

       两个n维向量之间的切比雪夫距离：

       另一种等价表达形式为：

5.2.4 不同距离度量对Iris数据集分类的影响

                                                                        欧式距离

                                                                      曼哈顿距离

                                                                    切比雪夫距离

5.3 针对USPS数据集的灰度图像分类

       USPS数据集原始数据为彩色图像，首先将其灰度化后，在用KNN算法进行分类，得到的准确率随K值的变化曲线如图所示：

       由图像可知，将图像灰度化之后，准确率明显下降，这是因为灰度化采用的是四舍五入的办法，如果某个像素点的数据小于0.5，则直接将其设置为0，这就导致，图片中的有效像素点就变得相当有限，所以准确率明显下降。

5.4 USPS数据集降维

       USPS原始数据集中的图片大小为1616，但是观察图片可以发现，在矩阵中，外边缘的大多数数据都是0，无法起到分类的作用，而且矩阵维度过高，导致运行速度很慢，所以考虑将外边缘的三行数据去掉，则数据变为99的矩阵。


       如上图所示，得到处理前后训练集的区别，由处理后的数据进行KNN分类，得到其准确率随k值变化的曲线如图：

       由图像可知，其准确率在0.85至0.9之间。

5.5 针对Sonar数据集对比Fisher线性判别和KNN算法

       由Fisher线性判别对Sonar数据集的分类可得，其分类准确率为75%，而KNN算法最终稳定在0.6左右。但是两种分类方法的原理和思想截然不同，不能只从分类准确率上来判别两种算法的优劣，下面分别讨论两种算法的异同。

       Fisher线性判别的主要思想是降维，而且针对的所有数据都是有标签的数据，只有在正确标注数据的情况下才可以运用在线性可分的问题中，使用条件比较局限。
       KNN算法，是根据数据本身，逐步自发的计算数据之间的距离来划分数据。

• 本文的pdf文件可在此下载：link

六、Python代码展示

6.1 USPS数据集

import h5py
import pandas as pd
import numpy as np
# 读取 USPS数据集
def pre_handle():
    with h5py.File( 'D:/usps.h5') as hf:
            train = hf.get('train')
            x_train = train.get('data')[:]
            y_train = train.get('target')[:]
            test = hf.get('test')
            x_test = test.get('data')[:]
            y_test = test.get('target')[:]
    train_data=pd.DataFrame(x_train)
    train_label=pd.DataFrame(y_train)
    test_data=pd.DataFrame(x_test)
    test_label=pd.DataFrame(y_test)
return train_data,train_label,test_data,test_label
train_data,train_label,test_data,test_label = pre_handle()
train_data = np.mat(train_data)
train_label = np.mat(train_label)
test_data = np.mat(test_data)
test_label = np.mat(test_label)
train_label = train_label.astype(int)
test_label = test_label.astype(int)
def knn_usps(train_data,train_label,test_data,test_label):
    accuracy = 0
    for i in range(2007):
        count = np.zeros(10)
        prediction = 0
        distance = np.zeros((7291,2))
        for t in range(7291):
            distance[t,1] = np.linalg.norm(test_data[i] - train_data[t])
            distance[t,0] = train_label[t]              # 储存标签和欧式距离
        order = distance[np.lexsort(distance.T)]    # 按最后一列排序
        for n in range(k):
            a = order[n,0]
            a = a.astype(int)
            count[a] += 1   
        prediction = count.argmax()                           # 取出现次数最多的为预测值
        if prediction == test_label[i]:
            accuracy += 1
    Accuracy = accuracy/2007
    print("USPS数据集的最近邻准确率为:",Accuracy)
return Accuracy
Res_usps = np.zeros(20)
for m in range(20):
    k = m+1
Res_usps[m] = knn_usps(train_data,train_label,test_data,test_label)
# 绘制 k与分类准确率的图像
import matplotlib.pyplot as plt
x = np.arange(1,21,1)
plt.xlabel('k')
plt.ylabel('Accuracy')
plt.ylim((0.5,1))      
plt.plot(x,Res_usps,'r')
plt.plot(x,Res_usps,'g*')
plt.grid()

6.2 Iris数据集

import pandas as pd
import numpy as np
iris = pd.read_csv('D:/iris.csv',header=None)
iris = np.array(iris)
def knn_iris(X):
    accuracy = 0
    for i in range(150):
        count1 = 0
        count2 = 0
        count3 = 0
        prediction = 0
        distance = np.zeros((149,2))
        test = X[i]
        train = np.delete(X,i,axis=0)
        test1 = test[:,0:4]
        train1 = train[:,0:4]
        for t in range(149):
            distance[t,1] = np.linalg.norm(test1 - train1[t])
            distance[t,0] = train[t,4]              # 储存标签和欧式距离
        order = distance[np.lexsort(distance.T)]    # 按最后一列排序
        for n in range(k):
            if order[n,0] == 1:
                count1 +=1
            if order[n,0] == 2:
                count2 +=1
            if order[n,0] == 3:
                count3 +=1
        if count1 >= count2 and count1 >= count3:
            prediction = 1
        if count2 >= count1 and count2 >= count3:
            prediction = 2
        if count3 >= count1 and count3 >= count2:
            prediction = 3                         # 取出现次数最多的为预测值
        if prediction == test[0,4]:
            accuracy += 1
    Accuracy = accuracy/150
    print(" k = %d时，Iris数据集的最近邻准确率为："%k,Accuracy)
return Accuracy
x_iris = iris[:,0:4]
x_iris = np.mat(x_iris)
a_iris = np.full((50,1),1)
b_iris = np.full((50,1),2)
c_iris = np.full((50,1),3)
Res_iris = np.zeros(50)
d_iris = np.append(a_iris,b_iris,axis=0)
d_iris = np.append(d_iris,c_iris,axis=0)
X_iris = np.append(x_iris,d_iris,axis=1)
for m in range(50):
    k = m + 1 
Res_iris[m] = knn_iris(X_iris)
# 绘制 k与分类准确率的图像
import matplotlib.pyplot as plt
x_iris = np.arange(1,51,1)
plt.xlabel('k')
plt.title('Iris')
plt.ylabel('Accuracy')
plt.ylim((0.8,1)) 
plt.plot(x_iris,Res_iris,'b')
plt.plot(x_iris,Res_iris,'r*')
plt.grid()

6.3 Sonar数据集

import pandas as pd
import numpy as np
sonar = pd.read_csv('D:/Sonar.csv',header=None)
sonar = np.array(sonar)
sonar.shape
def knn_sonar(X):
    accuracy = 0
    for i in range(208):
        count1 = 0
        count2 = 0
        prediction = 0
        distance = np.zeros((207,2))
        test = X[i]
        train = np.delete(X,i,axis=0)
        test1 = test[:,0:60]
        train1 = train[:,0:60]
        for t in range(207):
            distance[t,1] = np.linalg.norm(test1 - train1[t])
            distance[t,0] = train[t,60]              # 储存标签和欧式距离
        order = distance[np.lexsort(distance.T)]    # 按最后一列排序
        for n in range(k):
            if order[n,0] == 1:
                count1 +=1
            if order[n,0] == 2:
                count2 +=1
        if count1 >= count2:
            prediction = 1
        if count2 >= count1:
            prediction = 2                            
        if prediction == test[0,60]:
            accuracy += 1
    Accuracy = accuracy/208
    print("k = %d时，Sonar数据集的最近邻准确率为："%k,Accuracy)
return Accuracy
x_sonar = sonar[:,1:61]
x_sonar = np.mat(x_sonar)
a_sonar = np.full((97,1),1)
b_sonar = np.full((111,1),2)
Res_sonar = np.zeros(100)
c_sonar = np.append(a_sonar,b_sonar,axis=0)
X_sonar = np.append(x_sonar,c_sonar,axis=1)  
for m in range(100):
    k = m+1
Res_sonar[m] = knn_sonar(X_sonar)
# 绘制 k与分类准确率的图像
import matplotlib.pyplot as plt
x_sonar = np.arange(1,101,1)
plt.xlabel('k')
plt.ylabel('Accuracy')
plt.title('Sonar')
plt.ylim((0,1))      
plt.plot(x_sonar,Res_sonar,'r')
#plt.plot(x_sonar,Res_sonar,'g*')
plt.grid()