首页 ›存档› 技术 › 查看内容

Python机器学习算法入门之简单感知器学习算法

2018-3-30 13:00 |来自: 互联网 287 0

摘要: ZZR，Python中文社区专栏作者，OpenStack工程师，曾经的NLP研究者。主要兴趣方向：OpenStack、Python爬虫、Python数据分析。 Blog：http://skydream.me/ CSDN：http://blog.csdn.net/titan0427/article/details/5036 ...

ZZR，Python中文社区专栏作者，OpenStack工程师，曾经的NLP研究者。主要兴趣方向：OpenStack、Python爬虫、Python数据分析。

Blog：http://skydream.me/

CSDN：http://blog.csdn.net/titan0427/article/details/50365480

问题背景

考虑一个问题：现在我们有一些过往核发信用卡的资料，包括用户个人信息和审核结果。根据这些资料，我们希望预测能不能给下一个用户发信用卡。用户基本信息如下：

这些基本信息组成了一个向量。不同的信息有不同的权重，设权重向量。我们希望构造一个函数来给用户的信用打分，并且，如果信用分超过了某个阈值，我们就认为这个客户是可靠的，可以给他发信用卡：

能发：
不能：

通过阶跃函数，进一步将这个过程函数化：

所以，当，通过；当，拒绝；当，忽略。

其中：

整理该方程如下：

具体到二维空间

简化上面的问题，假设用户只有两个属性，就可以用二维空间的一个点来表示一个用户。如下所示，蓝圈表示通过，红叉表示拒绝。注意到直线的两边，一边大于0，一边小于0，也就是一边都是蓝圈，一边都是红叉。所以现在的目标就是，找到一条直线，可以将已知的蓝圈和红叉完美区分开。

基础知识回顾

简单回顾一下线性代数的知识。一条直线可以由一个点和法向量唯一确定。其点法式方程为：。相应地，其方向向量为：

感知机学习算法

简单感知机算法（Perceptron Learning Algorithm，PLA）的思路很简单，首先随便找一条直线，然后遍历每一个已知点，如果正确，则跳过；如果错误，则利用这个点的信息对直线进行修正。修正的思路如上图所示：是直线的法向量。是错误点的方向向量，是真实值。具体情况可分为如下两种情况：

情况一：

为了将这个出错的点包括进紫色区域，应该靠近方向。因此，。

情况二：

为了将这个出错的点排除出紫色区域，应该远离方向。因此，

。

综上，得到修正函数：

证明：PLA校正的正确性

那么为什么感知机算法可以逐步接近正确呢？

已知

两边同时乘上和，得：

因为，所以：

注意到恰好就是我们给出的当前用户的分数。当，也就是我们打分打低了，修正后分数上升；当，也就是我们打分打高了，修正后分数下降。这个结论说明，对于这组错误数据，经过修正以后，我们打出的分数更靠近正确结果了。

证明：PLA终止的充分条件

从算法的规则上可以看出，PLA终止的必要条件是数据集中确定存在一条直线，可以将蓝圈和红叉分开，也就是线性可分：

现在证明，线性可分是PLA终止的充分条件。

（1）设表示第t次更新时的点，一共更新了n次。若线性可分，则必然存在一条完美的直线，使得对，有。也就是：

（为向量内积，也就是）又由的更新规则得：

因此：

综上，得到：

初始时，所以：

（2）因为每次遇到错误的数据才会更新，也就是。其中是第t次更新时的权重值。因此：

类似于（1），得到：

（3）综上，得：

是一个常数，因此，随着t的增大，也逐步增大，也就是向量和的夹角逐渐减小，逐渐接近。
又因为：，所以。因此，PLA算法必然收敛。

Linear Pocket Algorithm

上述PLA算法的前提是数据集线性可分。但是很明显，在分类之前我们不可能知道我们手里的数据是不是线性可分的。更何况，数据集可能有噪声（noise），这些噪声是之前的经验中错误的分类结果，这些噪声将导致PLA无法收敛。因此，我们的目标就从找到一条完美划分数据集的，变成了找到一条最接近完美，使得错误的点最少。这个转变使得我们可以理非线性可分的数据集 ：

但是很遗憾的是，寻找是一个NP-hard问题。

因此问题又从“寻找最接近完美的变成了“寻找尽可能完美的。Pocket Algorithm是PLA的变形，用于处理此类问题。算法如下：

与简单PLA不同的是：