统计学习方法-感知机、k近邻

--------来自李航 《统计学习方法》

第二章 感知机

1.感知机： 二类分类、线性分类模型、判别模型、输出取+1、-1

		 f(x)=sign(w•x+b）

​ （其实就是求出使损失函数最小的w和b）

2.损失函数：误分类点到超平面的总距离

3.采用的最优化算法是：随机梯度下降法。

​ 一次选取一个误分类点使其梯度下降，极小化损失函数；

4.（1）感知机学习算法由于采用不同的初值或不同的误分类点选择顺序，解可以不同；若要得到唯一解，需要对分离超平面增加约束。

（2）误分类次数k是有上界的，即当训练集线性可分时，感知机学习算法原始形式的迭代是收敛的。

第三章 K近邻法

1.k近邻法的特殊情况：k=1，最近邻算法；

2.k近邻法三要素：

（1）k值的选择：k小模型复杂，容易过拟合；k大模型简单

​ k值一般取一个较小的数值，通常用交叉验证法选择最优的k值

（2）距离度量：最常用欧式距离；

​ L1(曼哈顿距离)、L2(欧式距离)、L∞(是各个坐标距离的最大值)

​ 由不同的距离度量所确定的最近邻点不同

（3）分类决策规则 ：往往是多数表决，等价于经验风险最小化；

3.线性扫描，即挨个计算输入实例与每个点间的距离，训练集很大时不可行；

​ 如何对训练数据进行快速k近邻搜索：kd树（二叉树，对实例点进行存储以便搜索）

算法： 构造平衡kd树；

​ 用kd树的最近邻搜索； （kd树搜索平均计算复杂度：O(logN)）