2.3 感知机学习算法（以达到策略）

2.3.1 原始形式：

给定一个训练数据集：

损失函数：

因为是误分类点所以yi(w·xi+b)必然<0，L(w,b)代表了误分类点的总距离
——>要使其极小化

采用随机梯度下降法：首先，任意选取一个超平面w0；然后，用梯度下降法不断地极小化目标函数（就是损失函数）；
注意： 用该在极小化过程中并非一次就让所有误分类点梯度下降，而是一次随机选取一个误分类点使其梯度下降！
随机选取一个误分类点(xi,yi)来对(w,b)进行更新：

参数更新不同方式：

其中η∈(0,1}]表示步长，这样可以使得L(w,b)越来越小，直到为0。批量的方法每次迭代需要用所有误分类点来更新，从而导致其速度慢；

算法：具有一定 随机性 ：x随机取可能会重复

image.png

选取初始w0,b0为0，得到了蓝色直线。对于感知机来说，w对应于超平面旋转程度，b对应于超平面位移量。我们要不断调整w,b使得将所有误分类点全正确分类(:з)∠)

算法实例：

由于可以采用不同的初值或者选取不同的误分类点，所以解也可以不同。所以竞赛做这种模型会比较容易好像XD

2.3.2 算法收敛性

解释：只有一个算法是收敛的才能说是有效的，就是要经过 有限次迭代 可以得到一个 将训练数据集完全正确划分 的分离超平面及感知机模型；
依赖性： 对于不同初值选择/迭代中不同误分类点选择顺序，可能会得到不同的分离超平面——>要增加约束条件来优化；
将权重向量以及输入向量都扩充一下：

上式两个向量内积结果就是wx+b

定理证明：

（1）说明每个点到超平面距离有一个下界；（2）说明误分类次数有上界。

若为误分类点则展开式的第二项必<0所以才有了下面的不等式

2.3.3 对偶性是

基本思想：将w,b表示为实例x和标记y的线性组合的形式（就是下面的α），通过求解其系数而球的w和b；

次数n越多表明该点难被分类，那么对最终结果影响就大

算法：（α=n*η）

将(3)细讲
算法实例：

注意： 对偶形式的算法也是收敛的，同时也可能存在多个解，那么就需要增加约束条件

三、K近邻法

直观理解：是一种基本分类与回归方法：
基本思想： 给定一个训练数据集，并且 实例标签已定，对新的输入实力，在训练数据集中找到与该实例最近的k个实例，这k个实例大多属于哪个类，那么该输入实例就属于那个类；

不同的k值会影响最终结果

三要素：k值、距离度量以及分类决策规则

3.1 k近邻算法：

误差率：

特殊情况：

贝叶斯误差率就是 最优决策 对应的误差

3.2 k近邻模型

3.2.1 模型：

当训练集、距离度量、k值以及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一确定。

定义：根据三要素将特征空间划为一些子空间，去v额定子空间里每个点所属的类；
单元(cell): 对于每个训练实例点xi，距离该点比其他点更近的所有点组成的一个域（都属于一个类），而xi的类yi则被作为其单元中所有点的类标记；

3.2.2 距离度量：

定义：特征空间中两个实例点的距离是他们俩的相似程度——>一般使用Lp距离：
当p=2时，其所代表就是欧氏距离（二维空间中两点间的直线距离）：

image.png
当p=1时，其所代表就是欧氏距离（直接向量相减）：
当p=∞时，其所代表就是欧氏距离（各个坐标距离的最大值）：
不同p的区别：
具体实例：

3.2.3 k值的选择

若k=N,那么无论输入实例是什么，都将简单地预测其属于在训练实例中最多的类。此时模型过于简单，完全忽略训练实例中地大量有用信息；
若k=1，那么就叫 最近邻算法，对于输入的实例点77x，他都将与x最临近点的类作为x的类。

3.2.4 分类决策规则

多数表决：

最小化误分类率就是最大化正确率I(yj=cj)

3.3 k近邻法的实现：kd树

主要考虑问题：如何对训练数据进行快速k近邻搜索，尤其是特征空间维数大以及训练数据集容量大时。用kd树结构存储有助于解决上述问题。

3.3.1 构造kd树

本质： 是二叉树，表述对k维空间的一个划分；
构造过程： 不断地用垂直于坐标轴地超平面将k维空间切分，构成一系列地k维超矩形区域。
kd树地每个节点对应于一个k维超矩形区域；
方法：

在选择根节点时可以通过计算每个特征的方差来进行选择（选最大的那个，因为其保留信息最多）；
中位数：当N为偶数时可以取中间两个数的平均值也可以选择其中一个；
注意：若当前节点划分维度为d，则d维度左（右）子树上所有点的坐标值小（大）于当前值。

划分实例：

即可得到kd树：

3.3.2 搜索kd树

其包含了两个部分：

算法：
例题讲解：

第一步，找到当前最近点，也就是包含输入实例的点（就是下图中在圈边的那个点）：

第二步，回溯，以实例点为圆心，到当前最近点距离为半径，看看圆是否与父节点划分的超平面有交集。如果有，那么就看看当前最近点的兄弟节点是否为更近的点。是的话就更新并进行二次回溯；

在新的圆中找不到其他点，那么将最近临近点更新为(2,3)