k近邻算法的想法很简单，类似于多数表决，关键点是参与多数表决的人是离你最近的k个人。

给定一个实例，首先从训练集中找到离这个实例最近的k个实例，然后根据这k个实例中哪个标签出现次数最多决定该实例的标签。需要注意的点是：

度量距离有很多，这里介绍三种，即1范数，二范数和无穷大范数。假设两个实例的特征向量为：

1范数：

http://s14/mw690/62b0682agd4aa8faf156d&690
2范数：

http://s10/mw690/62b0682agd4aa9a68ba69&690
无穷大范数：

当然还有好多其他的距离度量方式，比如向量夹角等。关于范数的定义可以参见线性代数的书，会有详细的介绍。我觉得那个范数一致性倒是蛮重要的。

使用的距离不同，k近邻的结果也会不同的，即“由不同的距离度量所确定的最邻近点是不同的。”

k值得选择非常重要，不合适的k值结果可能会很不理想。

如果选择的比较小的话，相当于用较小邻域中的训练实例进行预测，学习的近似误差会减少，只有与输入实例较近的训练实例才会对预测结果起作用，缺点是学习的估计误差会增大，易受噪声影响，极端情况是k=1；

如果k值选取的比较大，相当于用较大邻域中德训练实例进行预测，学习的估计误差会减少，但是近似误差会增大，而且与输入实例较远的训练实例也会对预测起作用，是预测结果错误，k值的增大意味着整体模型变得简单。因为划分的区域少了，更容易进行预测结果。极端情况是k=n.

如果每次都计算每个训练实例和输入实例的距离显然是非常耗时间的，对于样本数量比较大的训练集这是不可行的。一般构造kd树(属于二叉树)来实现k近邻算法。提升速度，减少存储量。

kd树的构造是一个递归过程，其思想是对k维空间（假设数据集在这个k维空间中）进行划分，每次划分在一个维度中进行，取该维所有实例中位数为切分点，切分由通过切分点并与该维坐标轴垂直的超平面实现。

kd树的每个节点都是一个实例，相邻的节点，父节点与子节点之间是近邻的。给定一个目标点，搜索其最近邻，首先找到包含目标点的叶节点，然后从该叶节点出发，依次回退到父节点，不断查找与目标节点最邻近的节点，当确定不可能存在更近的节点时终止。这样搜索就被限制在空间的局部区域上，提高了搜索近邻的效率。

kd树更加详尽的中文介绍参见博文：http://www.cnblogs.com/eyeszjwang/articles/2429382.html

2.感知器模型

感知器是经典的线性分类模型，是神经网络和支持向量机的基础。

下面从统计学习三要素来分析感知器模型：

1.模型

感知器的模型是线性函数：http://s8/mw690/62b0682agd4b533139ee7&690

其中w是权值向量，b是偏置bias，线性方程wx+b=0是特征空间中的超平面，该超平面将特征空间划分成两个部分。

继续介绍之前先说明数据集的线性可分性，如果存在某个超平面S将数据集的正实例点和负实例点完全正确的划分到超平面两侧，则称数据集是线性可分的，否则数据集线性不可分。线性可分时，满足划分的超平面一般不只一个，因此有的算法会寻找最优超平面，比如SVM。线性不可分时，一般引入核函数，将输入空间投影到更高维的线性可分的特征空间中，这个容易理解，世界上没有两种完全相同的东西，我们总能通过各种标签来区分两个事物，除了引入核函数外，SVM还使用了软间隔，使算法可以容忍造成线性不可分的点，提高算法灵活度。

2.感知器的损失函数是每个实例点的函数间隔（注意和集合间隔的区别）之和：

http://s1/mw690/62b0682agd4b56bb9cac0&690
其中，M为误分类点的集合，该函数就是感知器的经验风险函数。

3.利用梯度下降求解经验风险函数最小化，对w和b求偏导可得损失函数的梯度：

因此，在学习时，对于一个误分类点，通过梯度对权值向量和偏置进行更新，更新时一般有一个系数称为学习率，它决定了按梯度下降的步长，学习率可以为实现指定的定值，也可以为一个和学习次数相关的减函数。

当训练集中没有误分类点或者学习次数大于阈值时，停止训练。

最终的权值向量和偏置就是所求的超平面的参数。

需要说明的地方：

a.权值向量和偏置在一开始需要进行初始化，初始化的值不同，训练所得的超平面也会不同。

b.不同的误分类点以及不同的输入顺序也会造成学习所得的超平面不同。

因此，在每次训练一个感知器的时候，结果并不是固定的，因此评价其性能一般需要多训练几次取结果的平均值。

还有一个重要的点是感知器算法的收敛性，即经过有限次的迭代可以得到一个将训练数据集完全正确划分的分离超平面及感知器模型。这里面涉及的公示很多，不再贴出来，有兴趣的话可以证明一下，还是有必要的。

下面的章节讨论朴素贝叶斯法和决策树法。

关于感知机的扩展会有一章介绍极速学习ELM神经网络。