KNN是模式识别中的经典算法，本次实验就MNIST数据集来做KNN算法的实验，并结合前一次的LDA降维对数据进行进一步处理。

实验报告图片版

pdf版本可以戳这：模式识别实验报告：KNN K近邻算法

关键代码

KNN原理报告里有写，不作重复赘述。
本实验使用的编程环境是Jupyter，完整的程序代码可以戳这下载。
【模式识别】实验二：KNN，python程序代码与实验过程
这里仅贴上核心代码

MNIST数据集的导入

在本专栏之前一篇博文专门分析过，这里只上代码：

mnist = fetch_openml("mnist_784")
X, y = mnist['data'], mnist['target'] # X:data，y:label

特征标准化

特征标准化的好处：1、提高精度。2、提高计算速度

from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split

scaler = StandardScaler()
X_standardized = scaler.fit_transform(X1)

数据筛选

shuffle_index = np.random.permutation(60000)  # 随机排列一个序列，返回一个排列的序列。
X1, y1 = X[shuffle_index[:10000]], y[shuffle_index[:10000]]

对KNN来说，数据筛选是很有必要的。MNIST总共7w条数据，全部都跑会跑到天荒地老~
因此本实验随机筛选了10000条数据。

KNN实现方式一：调用sklearn的KNeighborsClassifier

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import learning_curve
from sklearn import metrics

def knn(k):
    # 测试用，记录算法的时间
    # begin_t = t.time()
    #创建一个有5个邻居的KNN分类器对象
    knn = KNeighborsClassifier(n_neighbors=k, n_jobs=-1)

    #训练模型
    model = knn.fit(X_train, y_train)

    #预测数据
    predictions = model.predict(X_test)

    #测试准确率
    accuracy = metrics.accuracy_score(y_test, predictions)
#     print ("k=",k)
#     print ('accuracy：%.2f%%'%(100*accuracy))
    return 100*accuracy
    # print("Total time: {:.2f}s".format(t.time()-begin_t))

KNN实现方式二：手动实现

def knn(k):
    accuracy = 0
    m = X_train.shape[0] # m 标记预测值数量8000 ； n 标记测试集数量 2000
    n = X_test.shape[0]
    for i in range(n):
        count = np.zeros(10)
        prediction = 0
        distance = np.zeros((m,2))
        for t in range(m):
            distance[t,0] = y_train[t]              # 储存标签和欧式距离
            distance[t,1] = np.sqrt(sum(np.power(X_train[t] - X_test[i], 2)))  # 求欧式距离
        order = distance[np.lexsort(distance.T)]    # 按第二列(距离)排序
        for j in range(k):
            a = order[j,0]
            a = a.astype(int)
            count[a] += 1   
        prediction = count.argmax()                           # 取出现次数最多的为预测值
        if prediction == y_test[i]:
            accuracy += 1
    Accuracy = accuracy/n
    return 100*Accuracy  # 化成百分数形式

简要描述下算法思路：
1、逐次遍历测试集，对每个样本计算其和训练集的欧式距离。
2、将每个训练样本到该样本欧式距离排序，选取前K个训练样本。
3、统计这K个样本的标签，测试样本的标签即为这K个样本的最多的标签。

LDA降维

# 使用Fisher进行降维 
# 注：LDA最大降维数<分类数-1
# minsit为10分类，因此维度数可以取1-8
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis as LDA
def mylda(X, y, demension):
    lda = LDA(n_components=demension)
    lda.fit(X, y)
    result_x = lda.transform(X)
    return result_x

总结

KNN需要计算每一个样本到训练样本的距离，因此训练样本越多，程序运行越慢；
优势在于程序无需经过训练，可以直接将样本进行判别分类。

k-近邻算法（KNN）
简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
算法原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中数据对应的特征进行比较，然后算法提取样本集中特征值最相似数据（最近邻）的分类标签。一般来说，我们只选取样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后选择k个相似数据中出现次数最多的分类，作为新数据的分类。

采样方法
本组分别在食堂三层以及文实429教室进行数据采集。
食堂三层，以四根柱子将区域分成6块，采用6个AP在每个区域采集20条数据，共计120条数据。示意图及具体数据，如下所示。

AP1 AP2 AP3 AP4 AP5 AP6 区域
64 57 59 52 41 39 4
63 57 56 58 38 36 4
62 64 56 49 40 37 1
62 65 64 56 42 43 1
61 55 36 42 57 54 2
61 56 57 58 51 43 4
61 54 53 56 52 46 4
61 54 55 56 48 49 4
61 61 58 62 41 44 4
61 60 59 63 37 37 4
60 56 57 55 32 44 1
60 61 56 55 50 55 1
60 53 54 57 42 33 4
59 53 50 58 39 37 4
58 60 59 63 39 46 1
58 58 58 60 40 43 1
58 61 58 55 47 47 1
58 65 57 57 39 36 1
58 57 59 55 40 44 4
58 54 56 57 40 40 4
57 56 60 56 33 41 1
57 50 38 39 53 55 2
57 62 61 60 46 36 4
56 57 50 52 48 41 1
56 54 49 44 51 48 2
56 66 44 44 57 63 2
56 54 54 60 46 45 4
56 58 54 64 43 38 4
55 52 43 40 52 56 1
55 50 45 45 56 56 1
55 58 58 52 44 42 1
55 62 69 56 43 40 1
55 62 59 56 37 47 1
55 48 49 43 63 63 2
55 53 43 44 47 49 2
55 56 45 50 48 48 5
55 51 43 56 43 46 5
55 46 52 44 44 51 5
54 59 62 57 44 49 1
54 56 54 52 47 47 1
54 55 61 54 34 45 1
54 51 51 46 48 56 2
54 49 39 44 52 55 2
54 41 43 47 52 58 3
54 61 52 52 48 48 4
54 55 49 57 38 41 4
54 49 54 56 45 43 4
54 59 45 54 46 43 4
54 60 53 57 48 44 5
54 53 45 57 47 45 5
54 48 62 62 71 71 6
54 43 64 58 72 69 6
53 57 54 55 49 47 1
53 48 42 43 55 62 2
53 57 42 45 51 46 2
53 48 55 53 64 64 3
53 54 49 49 40 43 4
52 53 53 57 44 46 1
52 50 40 43 53 53 2
52 45 61 54 70 54 5
51 50 44 39 58 56 2
51 48 33 44 59 57 2
51 50 58 56 64 63 3
51 46 57 54 66 70 3
51 55 50 56 46 41 4
51 47 59 58 68 66 6
50 47 51 46 59 61 3
50 44 59 61 67 68 3
50 44 57 51 62 66 3
50 52 43 51 40 45 5
50 49 45 44 48 53 5
50 44 53 51 51 58 5
49 51 48 49 50 57 2
49 50 52 50 49 50 2
49 47 37 40 54 54 2
49 49 62 55 64 66 6
48 44 54 48 63 67 3
48 44 63 63 61 63 6
47 50 44 46 49 54 2
47 49 53 47 54 57 2
47 50 59 53 63 65 3
46 39 56 52 64 63 3
46 45 59 51 65 66 3
46 48 66 59 65 66 3
46 45 51 49 61 56 5
45 49 47 52 45 61 2
45 47 49 55 52 53 5
45 47 58 59 65 61 5
45 51 61 63 67 60 6
45 38 60 54 65 66 6
44 41 61 63 57 56 3
44 47 62 63 60 65 3
44 40 56 58 66 60 6
43 44 54 50 57 58 3
43 41 49 53 57 67 3
43 40 55 55 63 63 3
43 39 51 53 62 59 3
43 44 43 51 57 52 5
43 44 61 55 65 61 6
43 46 60 60 62 60 6
43 37 50 54 63 61 6
42 51 42 42 60 55 2
42 34 54 57 60 58 6
42 35 57 62 66 66 6
42 38 50 57 56 56 6
41 38 53 53 57 59 5
41 40 55 60 61 59 5
41 39 53 57 59 55 5
40 40 51 57 57 60 5
39 43 59 49 60 64 3
39 39 57 59 63 60 3
39 42 48 54 54 59 5
39 46 52 57 56 61 6
38 41 44 55 56 56 5
38 40 48 57 59 58 6
37 45 49 59 60 56 5
37 38 58 57 65 61 6
36 38 46 52 61 61 6
33 43 56 59 65 60 6
30 46 52 60 63 61 6

文实429教室数据采集，初期分成10个区域效果不好，最终将10区减少为5区，即每一列为一区，而不是原来的每一桌为一区，将错误率减少了20%，但由于选取的范围仍然差异较小，所以文实组实验错误率较高。选取5个AP，每个区域采集24条数据，共计120条数据。

AP1 AP2 AP3 AP4 AP5 区域
67 65 44 35 61 2
68 63 42 40 54 1
68 69 40 40 62 2
69 67 39 40 59 2
66 62 40 40 58 2
69 62 45 40 59 2
62 62 42 40 59 2
65 64 43 41 93 2
70 69 47 41 63 2
66 68 45 43 61 1
68 67 48 43 51 1
70 64 42 44 64 1
62 61 48 44 72 5
66 61 47 45 62 2
65 58 50 45 56 3
74 65 50 46 65 1
70 68 45 46 60 1
65 64 44 46 63 2
66 65 44 46 66 3
64 68 41 47 61 1
67 71 48 47 57 1
67 68 43 47 57 2
60 66 47 47 64 3
60 64 42 47 62 3
68 72 43 48 62 1
65 68 50 48 62 1
66 64 46 48 62 3
62 59 50 48 61 3
69 71 49 49 59 1
62 63 48 49 66 3
61 56 45 49 66 3
51 52 56 49 69 5
65 67 44 50 56 2
66 71 45 50 68 3
67 61 46 50 64 3
59 55 52 50 69 4
55 58 51 50 69 4
61 54 52 50 74 5
52 57 49 51 69 3
57 59 55 51 65 4
54 54 52 51 68 5
68 57 50 52 65 3
58 57 51 52 67 4
60 58 49 52 65 4
56 56 48 52 69 5
64 64 48 53 54 1
56 53 50 53 73 4
56 58 53 53 70 4
52 61 54 53 64 4
55 56 54 53 73 5
56 56 52 53 71 5
56 53 48 53 72 5
67 67 54 54 73 4
67 67 54 54 73 4
52 51 51 54 75 5
53 61 54 55 71 5
53 53 50 55 68 5
57 52 59 56 67 4
50 49 56 56 69 5
57 58 57 57 74 4
57 58 53 57 74 4
52 58 57 57 68 4
64 53 58 57 69 5
43 41 70 58 65 2
45 48 67 58 67 3
52 49 61 58 63 4
43 48 63 59 59 2
57 49 60 59 59 3
52 49 61 59 69 3
56 56 53 59 72 5
54 53 58 59 75 5
43 43 63 60 59 2
49 50 71 60 69 3
54 50 64 60 62 3
54 55 61 60 72 4
64 62 58 60 77 5
40 45 65 61 60 2
41 45 83 61 64 2
50 50 64 61 64 3
65 55 57 61 71 4
51 48 61 61 62 4
49 55 52 61 69 5
41 45 74 62 61 1
38 47 63 62 59 2
48 49 65 62 65 3
56 45 58 62 69 4
52 49 64 62 65 4
54 49 56 62 68 5
51 56 54 62 67 5
56 54 60 62 74 5
60 55 57 62 68 5
46 47 62 63 61 1
48 48 62 63 64 3
48 46 63 63 67 3
46 52 61 63 66 3
44 47 67 63 64 3
54 53 53 63 67 4
59 66 62 63 75 5
56 53 60 63 74 5
44 41 71 64 60 1
46 41 67 64 62 2
42 49 65 64 58 2
42 48 68 64 62 3
46 49 65 65 65 2
40 40 70 65 64 2
59 59 53 65 67 4
46 45 63 66 64 1
54 50 59 66 73 4
50 43 64 67 62 1
47 41 65 67 59 1
55 52 59 67 68 4
55 66 60 67 72 5
38 40 72 68 58 1
51 43 71 69 60 1
41 45 65 69 48 1
45 51 64 69 64 2
38 46 64 69 63 2
44 48 66 70 65 1
42 51 70 73 51 1
54 49 65 74 52 1

在训练算法的过程中，分别选取不同比例的数据作为训练集和测试集，同时在k取不同值时，最终结果亦不同。两个实验场所，共进行80次实验，实验条件如下所。

食堂组：共51组实验

文实429组：共39组实验

实验结果
食堂组最优结果如下，正确率79.2%。


文实429组最优结果如下，正确率58.4%，且有三组实验皆能取得最优成果。




实验分析
从结果上看食堂组的实验结果更加理想，经组内讨论分析，这可能与数据采集区域规则程度、大小等因素有关，食堂组划分的区域更加接近正方形，且区域面积更大，相对采集点密度降低，分布也更加均匀，从而最后的实验结果也更为理想。同时，由于对于编程的不熟悉，本次小组采用的编码程序可能存在考虑因素遗漏的情况，成为本次实验的局限之处。
未来实验的改进可以从代码优化以及数据科学采集两方面入手，从而使实验结果更加理想。最后附上本次实验的编码程序。

小组成员：伍秋晨、薛睿、许雪梅、杨涵月、赵鑫

机器学习——K-近邻算法

（一）K-近邻算法概述

（二）算法步骤

（三）使用Python导入数据

（四）K-近邻算法

（五）使用K-近邻算法识别手写数字

（六）总结

（一）K-近邻算法概述

        K-近邻法(K-nearest neighbor, K-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

（二）算法步骤

k-近邻算法步骤如下：

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

        使用K-近邻算法分类爱情片和动作片，图1-1显示了6部电影的打斗和接吻镜头数。我们可以使用KNN算法，对一部未看过的电影，确定它是爱情片还是动作片。

                图1-1    使用打斗和接吻镜头数分类电影

 我们需要知道这个电影存在多少打斗镜头和接吻镜头。如图1-2

图1-2

        我们可以从散点图大致推断，这个问号标记的电影可能属于爱情片，因为距离已知的那三个爱情片的圆点更近，可以使用距离度量。如图1-3所示

图1-3   两点距离公式

通过计算，我们得到图1-4所示结果

图1-4   已知电影与未知电影的距离

        现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman、California Man。K-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此判定未知电影是爱情片。这个判别过程就是k-近邻算法。

（三）使用Python导入数据

对于书上的案例，创建名为kNN.py的Python模块，导入以下数据：

from numpy import *
import operator
def createDataSet():
        group = array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
        labels = ['爱情片','爱情片','爱情片','动作片','动作片','动作片']
        return group,labels

运行结果：

图1-5

（四）K-近邻算法

根据两点距离公式，计算距离，并返回结果。

def classify0(inX, dataSet, labels, k):
    #numpy函数shape[0]返回dataSet的行数
    dataSetSize = dataSet.shape[0]
    #在列向量方向上重复inX共1次(横向)，行向量方向上重复inX共dataSetSize次(纵向)
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    #二维特征相减后平方
    sqDiffMat = diffMat**2
    #sum()所有元素相加，sum(0)列相加，sum(1)行相加
    sqDistances = sqDiffMat.sum(axis=1)
    #开方，计算出距离
    distances = sqDistances**0.5
    #返回distances中元素从小到大排序后的索引值
    sortedDistIndices = distances.argsort()
    #定一个记录类别次数的字典
    classCount = {}
    for i in range(k):
        #取出前k个元素的类别
        voteIlabel = labels[sortedDistIndices[i]]
        #dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
        #计算类别次数
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    #python3中用items()替换python2中的iteritems()
    #key=operator.itemgetter(1)根据字典的值进行排序
    #key=operator.itemgetter(0)根据字典的键进行排序
    #reverse降序排序字典
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    #返回次数最多的类别,即所要分类的类别
    return sortedClassCount[0][0]

运行结果：

图1-6

（五）使用K-近邻算法识别手写数字

        一般流程

1. 收集数据：提供文本文件。
2. 准备数据：编写函数classify0()，将图像格式转换为分类器使用的list格式。
3. 分析数据：在Python命令提示符中检查数据，确保它符合要求。
4. 训练算法：此步骤不适用于K-近邻算法。
5. 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
6. 使用算法：需要输入样本数据和结构化输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

        对于需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素x32像素。尽管采用本文格式存储图像不能有效地利用内存空间，但是为了方便理解，我们将图片转换为文本格式，数字的文本格式如图1-6

图1-6

#文本向量化 32x32 -> 1x1024
def img2vector(filename):
    returnVect = []
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect.append(int(lineStr[j]))
    return returnVect

以0_13.txt为例子，结果为：

 接着将数据导入到分类器中，检测分类器的执行效果。

def handwritingClassTest():
    #测试集的Labels
    hwLabels = []
    #返回trainingDigits目录下的文件名
    trainingFileList = listdir('trainingDigits')
    #返回文件夹下文件的个数
    m = len(trainingFileList)
    #初始化训练的Mat矩阵,测试集
    trainingMat = np.zeros((m, 1024))
    #从文件名中解析出训练集的类别
    for i in range(m):
        #获得文件的名字
        fileNameStr = trainingFileList[i]
        #获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        #将获得的类别添加到hwLabels中
        hwLabels.append(classNumber)
        #将每一个文件的1x1024数据存储到trainingMat矩阵中
        trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr))
    #返回testDigits目录下的文件列表
    testFileList = listdir('testDigits')
    #错误检测计数
    errorCount = 0.0
    #测试数据的数量
    mTest = len(testFileList)
    #从文件中解析出测试集的类别并进行分类测试
    for i in range(mTest):
        #获得文件的名字
        fileNameStr = testFileList[i]
        #获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        #获得测试集的1x1024向量,用于训练
        vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))
        #获得预测结果
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("分类返回结果为%d\t真实结果为%d" % (classifierResult, classNumber))
        if(classifierResult != classNumber):
            errorCount += 1.0
    print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount/mTest * 100))

结果为：

（六）总结

优点：

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

缺点：

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