前言：
参考了一位NLP学长的博客，受益颇多，跟着学长学习李航老师的《统计学习方法》，希望整理一些重点，便于翻阅，日积月累，为三年后的面试打下基础！
代码来自：
https://www.pkudodo.com

（一）感知机

定义：

感知机是二分类的线性模型,属于判别模型.感知机学习旨在求出将训练数据进行线性划分的分离超平面.是神经网络和支持向量机的基础。

个人理解：结合看过的《深度学习入门基于python的理论与实现》，感知机说白了就是接受一些信号，输出信号的模型（就像理工科电工科中讲到的逻辑电路一个道理），多个输入信号都有各自固有的权重，这些权重发挥着控制各个信号的重要性的作用，也就是说，权重越大，对应该权重的信号的重要性就越高。


那么，有同学就疑问了，为什么是线性呢，非线性不能吗，这里可以看看两张图：

用一条直线是可以将图1正常分割开，而无法将第二张图分割，第一张图在编程实现时用到的是简单的逻辑电路（与门、与非门、或门），但是第二张图这种异或门只能通过多层感知机，也就是神经网络才能够实现。

感知机的几何解释:
模型公式:$f(x)=sign(w\cdot x+b)$
$w$叫作权值向量,$b$叫做偏置,$sign$是符号函数.
$w\cdot x+b$对应于特征空间中的一个分离超平面$S$,其中$w$是$S$的法向量,$b$是$S$的截距.$S$将特征空间划分为两个部分,位于两个部分的点分别被分为正负两类.

策略:
假设训练数据集是线性可分的,感知机的损失函数是误分类点到超平面$S$的总距离。因为误分类点到超平面S的距离是$\frac{1}{||w||}|w\cdot{x_0}+b|$.且对于误分类的数据来说,总有:$-y_i(w\cdot{x_i}+b)>0$成立,因此不考虑$\frac{1}{||w||}$,就得到感知机的损失函数:
$L(w,b)=-\sum_{x_i\in{M}} y_i(w\cdot{x_i}+b)$,其中$M$是误分类点的集合.感知机学习的策略就是选取使损失函数最小的模型参数.

算法:感知机的最优化方法采用随机梯度下降法.首先任意选取一个超平面$w_0$,$b_0$,然后不断地极小化目标函数.在极小化过程中一次随机选取一个误分类点更新$w,b$,直到损失函数为0:
$$w\longleftarrow w+\eta y_ix_i$$
$$b\longleftarrow b+\eta y_i$$
其中$η$表示步长.该算法的直观解释是:当一个点被误分类,就调整$w,b$使分离超平面向该误分类点接近.感知机的解可以不同.

对偶形式: 假设原始形式中的$w_0$和$b_0$均为0,设逐步修改$w$和$b$共$n$次,令$a=nη$,最后学习到的$w,b$可以表示为$w=\sum_{i=1}^{N}\alpha y_i x_i,$.那么对偶算法就变为设初始a和b均为0,每次选取数据更新a和b直至没有误分类点为止.对偶形式的意义在于可以将训练集中实例间的内积计算出来,存在Gram矩阵中,可以大大加快训练速度

代码：

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#coding=utf-8
#Author:Dodo
#Date:2018-11-15
#Email:lvtengchao@pku.edu.cn
'''
数据集：Mnist
训练集数量：60000
测试集数量：10000
------------------------------
运行结果：
正确率：81.72%（二分类）
运行时长：78.6s
'''
import numpy as np
import time
def loadData(fileName):
    '''
    加载Mnist数据集
    :param fileName:要加载的数据集路径
    :return: list形式的数据集及标记
    '''
    print('start to read data')
    # 存放数据及标记的list
    dataArr = []; labelArr = []
    # 打开文件
    fr = open(fileName, 'r')
    # 将文件按行读取
    for line in fr.readlines():
        # 对每一行数据按切割福','进行切割，返回字段列表
        curLine = line.strip().split(',')
        # Mnsit有0-9是个标记，由于是二分类任务，所以将>=5的作为1，<5为-1
        if int(curLine[0]) >= 5:
            labelArr.append(1)
        else:
            labelArr.append(-1)
        #存放标记
        #[int(num) for num in curLine[1:]] -> 遍历每一行中除了以第一哥元素（标记）外将所有元素转换成int类型
        #[int(num)/255 for num in curLine[1:]] -> 将所有数据除255归一化(非必须步骤，可以不归一化)
        dataArr.append([int(num)/255 for num in curLine[1:]])
    #返回data和label
    return dataArr, labelArr
def perceptron(dataArr, labelArr, iter=50):
    '''
    感知器训练过程
    :param dataArr:训练集的数据 (list)
    :param labelArr: 训练集的标签(list)
    :param iter: 迭代次数，默认50
    :return: 训练好的w和b
    '''
    print('start to trans')
    #将数据转换成矩阵形式（在机器学习中因为通常都是向量的运算，转换成矩阵形式方便运算）
    #转换后的数据中每一个样本的向量都是横向的
    dataMat = np.mat(dataArr)
    #将标签转换成矩阵，之后转置(.T为转置)。
    #转置是因为在运算中需要单独取label中的某一个元素，如果是1xN的矩阵的话，无法用label[i]的方式读取
    #对于只有1xN的label可以不转换成矩阵，直接label[i]即可，这里转换是为了格式上的统一
    labelMat = np.mat(labelArr).T
    #获取数据矩阵的大小，为m*n
    m, n = np.shape(dataMat)
    #创建初始权重w，初始值全为0。
    #np.shape(dataMat)的返回值为m，n -> np.shape(dataMat)[1])的值即为n，与
    #样本长度保持一致
    w = np.zeros((1, np.shape(dataMat)[1]))# 初始化权重w为1*N的0矩阵
    #初始化偏置b为0
    b = 0
    #初始化步长，也就是梯度下降过程中的n，控制梯度下降速率
    h = 0.0001

    #进行iter次迭代计算
    for k in range(iter):
        #对于每一个样本进行梯度下降
        #李航书中在2.3.1开头部分使用的梯度下降，是全部样本都算一遍以后，统一
        #进行一次梯度下降
        #在2.3.1的后半部分可以看到（例如公式2.6 2.7），求和符号没有了，此时用
        #的是随机梯度下降，即计算一个样本就针对该样本进行一次梯度下降。
        #两者的差异各有千秋，但较为常用的是随机梯度下降。
        for i in range(m):
            #获取当前样本的向量
            xi = dataMat[i]
            #获取当前样本所对应的标签
            yi = labelMat[i]
            #判断是否是误分类样本
            #误分类样本特征为： -yi(w*xi+b)>=0，详细可参考书中2.2.2小节
            #在书的公式中写的是>0，实际上如果=0，说明改点在超平面上，也是不正确的
            if -1 * yi * (w * xi.T + b) >= 0:
                #对于误分类样本，进行梯度下降，更新w和b
                w = w + h *  yi * xi
                b = b + h * yi
        #打印训练进度
        print('Round %d:%d training' % (k, iter))

    #返回训练完的w、b
    return w, b
def test(dataArr, labelArr, w, b):
    '''
    测试准确率
    :param dataArr:测试集
    :param labelArr: 测试集标签
    :param w: 训练获得的权重w
    :param b: 训练获得的偏置b
    :return: 正确率
    '''
    print('start to test')
    #将数据集转换为矩阵形式方便运算
    dataMat = np.mat(dataArr)
    #将label转换为矩阵并转置，详细信息参考上文perceptron中
    #对于这部分的解说
    labelMat = np.mat(labelArr).T

    #获取测试数据集矩阵的大小
    m, n = np.shape(dataMat)
    #错误样本数计数
    errorCnt = 0
    #遍历所有测试样本
    for i in range(m):
        #获得单个样本向量
        xi = dataMat[i]
        #获得该样本标记
        yi = labelMat[i]
        #获得运算结果
        result = -1 * yi * (w * xi.T + b)
        #如果-yi(w*xi+b)>=0，说明该样本被误分类，错误样本数加一
        if result >= 0: errorCnt += 1
    #正确率 = 1 - （样本分类错误数 / 样本总数）
    accruRate = 1 - (errorCnt / m)
    #返回正确率
    return accruRate
if __name__ == '__main__':
    #获取当前时间
    #在文末同样获取当前时间，两时间差即为程序运行时间
    start = time.time()

    #获取训练集及标签
    trainData, trainLabel = loadData('./mnist_train.csv')
    #获取测试集及标签
    testData, testLabel = loadData('./mnist_test.csv')

    #训练获得权重
    w, b = perceptron(trainData, trainLabel, iter = 30)
    #进行测试，获得正确率
    accruRate = test(testData, testLabel, w, b)

    #获取当前时间，作为结束时间
    end = time.time()
    #显示正确率
    print('accuracy rate is:', accruRate)
    #显示用时时长
    print('time span:', end - start)

（二）K-邻近

定义：

$k$近邻法根据其$k$个最邻的训练实例的类别,通过多数表决等方式进行预测.

什么是多数表决？我们为了对样本$x$进行归类，通过它周围最近的$k$个点来“投票”，这$k$个点大多数是哪个类型的，则定样本$x$为这个类型，故称为多数表决

模型说明:
(1)训练集（样本$x$以及样本$x$对应的label:$y$）
(2)距离度量(欧氏距离or曼哈顿距离) 特征空间中两个实例点的距离是相似程度的反映,k近邻算法一般使用欧氏距离,也可以使用曼哈顿距离.
欧式距离：
曼哈顿距离：
(3)k值 k值较小时,整体模型变得复杂,容易发生过拟合;k值较大时,整体模型变得简单.在应用中k一般取较小的值,通过交叉验证法选取最优的k.

但是K邻近算法也有其局限性：

  1. 在预测样本类别时，待预测样本需要与训练集中所有样本计算距离，当训练集数量过高时（例如Mnsit训练集有60000个样本），每预测一个样本都要计算60000个距离，计算代价过高，尤其当测试集数目也较大时（Mnist测试集有10000个）。

  2. K近邻在高维情况下时（高维在机器学习中并不少见），待预测样本需要与依次与所有样本求距离。向量维度过高时使得欧式距离的计算变得不太迅速了。本文在60000训练集的情况下，将10000个测试集缩减为200个，整个过程仍然需要308秒（曼哈顿距离为246秒，但准确度大幅下降）。

  3. 使用欧氏距离还是曼哈顿距离，性能上的差别相对来说不是很大，说明欧式距离并不是制约计算速度的主要方式。最主要的是训练集的大小，每次预测都需要与60000个样本进行比对，同时选出距离最近的$k$项


代码：

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#coding=utf-8
#Author:Dodo
#Date:2018-11-16
#Email:lvtengchao@pku.edu.cn

'''
数据集：Mnist
训练集数量：60000
测试集数量：10000（实际使用：200）
------------------------------
运行结果：（邻近k数量：25）
向量距离使用算法——欧式距离
    正确率：97%
    运行时长：308s
向量距离使用算法——曼哈顿距离
    正确率：14%
    运行时长：246s
'''

import numpy as np
import time

def loadData(fileName):
    '''
    加载文件
    :param fileName:要加载的文件路径
    :return: 数据集和标签集
    '''
    print('start read file')
    #存放数据及标记
    dataArr = []; labelArr = []
    #读取文件
    fr = open(fileName)
    #遍历文件中的每一行
    for line in fr.readlines():
        #获取当前行，并按“，”切割成字段放入列表中
        #strip：去掉每行字符串首尾指定的字符（默认空格或换行符）
        #split：按照指定的字符将字符串切割成每个字段，返回列表形式
        curLine = line.strip().split(',')
        #将每行中除标记外的数据放入数据集中（curLine[0]为标记信息）
        #在放入的同时将原先字符串形式的数据转换为整型
        dataArr.append([int(num) for num in curLine[1:]])
        #将标记信息放入标记集中
        #放入的同时将标记转换为整型
        labelArr.append(int(curLine[0]))
    #返回数据集和标记
    return dataArr, labelArr

def calcDist(x1, x2):
    '''
    计算两个样本点向量之间的距离
    使用的是欧氏距离，即 样本点每个元素相减的平方  再求和  再开方
    欧式举例公式这里不方便写，可以百度或谷歌欧式距离（也称欧几里得距离）
    :param x1:向量1
    :param x2:向量2
    :return:向量之间的欧式距离
    '''
    return np.sqrt(np.sum(np.square(x1 - x2)))

    #马哈顿距离计算公式
    # return np.sum(x1 - x2)




def getClosest(trainDataMat, trainLabelMat, x, topK):
    '''
    预测样本x的标记。
    获取方式通过找到与样本x最近的topK个点，并查看它们的标签。
    查找里面占某类标签最多的那类标签
    （书中3.1 3.2节）
    :param trainDataMat:训练集数据集
    :param trainLabelMat:训练集标签集
    :param x:要预测的样本x
    :param topK:选择参考最邻近样本的数目（样本数目的选择关系到正确率，详看3.2.3 K值的选择）
    :return:预测的标记
    '''
    #建立一个存放向量x与每个训练集中样本距离的列表
    #列表的长度为训练集的长度，distList[i]表示x与训练集中第
    ## i个样本的距离
    distList = [0] * len(trainLabelMat)
    #遍历训练集中所有的样本点，计算与x的距离
    for i in range(len(trainDataMat)):
        #获取训练集中当前样本的向量
        x1 = trainDataMat[i]
        #计算向量x与训练集样本x的距离
        curDist = calcDist(x1, x)
        #将距离放入对应的列表位置中
        distList[i] = curDist

    #对距离列表进行排序
    #argsort：函数将数组的值从小到大排序后，并按照其相对应的索引值输出
    #例如：
    #   >>> x = np.array([3, 1, 2])
    #   >>> np.argsort(x)
    #   array([1, 2, 0])
    #返回的是列表中从小到大的元素索引值，对于我们这种需要查找最小距离的情况来说很合适
    #array返回的是整个索引值列表，我们通过[:topK]取列表中前topL个放入list中。
    #----------------优化点-------------------
    #由于我们只取topK小的元素索引值，所以其实不需要对整个列表进行排序，而argsort是对整个
    #列表进行排序的，存在时间上的浪费。字典有现成的方法可以只排序top大或top小，可以自行查阅
    #对代码进行稍稍修改即可
    #这里没有对其进行优化主要原因是KNN的时间耗费大头在计算向量与向量之间的距离上，由于向量高维
    #所以计算时间需要很长，所以如果要提升时间，在这里优化的意义不大。（当然不是说就可以不优化了，
    #主要是我太懒了）
    topKList = np.argsort(np.array(distList))[:topK]        #升序排序
    #建立一个长度时的列表，用于选择数量最多的标记
    #3.2.4提到了分类决策使用的是投票表决，topK个标记每人有一票，在数组中每个标记代表的位置中投入
    #自己对应的地方，随后进行唱票选择最高票的标记
    labelList = [0] * 10
    #对topK个索引进行遍历
    for index in topKList:
        #trainLabelMat[index]：在训练集标签中寻找topK元素索引对应的标记
        #int(trainLabelMat[index])：将标记转换为int（实际上已经是int了，但是不int的话，报错）
        #labelList[int(trainLabelMat[index])]：找到标记在labelList中对应的位置
        #最后加1，表示投了一票
        labelList[int(trainLabelMat[index])] += 1
    #max(labelList)：找到选票箱中票数最多的票数值
    #labelList.index(max(labelList))：再根据最大值在列表中找到该值对应的索引，等同于预测的标记
    return labelList.index(max(labelList))


def test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, topK):
    '''
    测试正确率
    :param trainDataArr:训练集数据集
    :param trainLabelArr: 训练集标记
    :param testDataArr: 测试集数据集
    :param testLabelArr: 测试集标记
    :param topK: 选择多少个邻近点参考
    :return: 正确率
    '''
    print('start test')
    #将所有列表转换为矩阵形式，方便运算
    trainDataMat = np.mat(trainDataArr); trainLabelMat = np.mat(trainLabelArr).T
    testDataMat = np.mat(testDataArr); testLabelMat = np.mat(testLabelArr).T

    #错误值技术
    errorCnt = 0
    #遍历测试集，对每个测试集样本进行测试
    #由于计算向量与向量之间的时间耗费太大，测试集有6000个样本，所以这里人为改成了
    #测试200个样本点，如果要全跑，将行注释取消，再下一行for注释即可，同时下面的print
    #和return也要相应的更换注释行
    # for i in range(len(testDataMat)):
    for i in range(200):
        # print('test %d:%d'%(i, len(trainDataArr)))
        print('test %d:%d' % (i, 200))
        #读取测试集当前测试样本的向量
        x = testDataMat[i]
        #获取预测的标记
        y = getClosest(trainDataMat, trainLabelMat, x, topK)
        #如果预测标记与实际标记不符，错误值计数加1
        if y != testLabelMat[i]: errorCnt += 1

    #返回正确率
    # return 1 - (errorCnt / len(testDataMat))
    return 1 - (errorCnt / 200)



if __name__ == "__main__":
    start = time.time()

    #获取训练集
    trainDataArr, trainLabelArr = loadData('./mnist_train.csv')
    #获取测试集
    testDataArr, testLabelArr = loadData('./mnist_test.csv')
    #计算测试集正确率
    accur = test(trainDataArr, trainLabelArr, testDataArr, testLabelArr, 25)
    #打印正确率
    print('accur is:%d'%(accur * 100), '%')

    end = time.time()
    #显示花费时间
print('time span:', end - start)