机器学习和数据挖掘（3）：线性模型

￡神魔★判官ぃ 2022-06-12 01:37 312阅读 0赞

# 感知器模型 #

## 基本概念 ##

线性可分：在特征空间中可以用一个线性分界面正确无误地分开两类样本；采用增广样本向量，即存 在合适的增广权向量 a 使得：

![20130601125547513][]

则称样本是线性可分的。如下图中左图线性可分，右图不可分。

![20130601125913897][]

所有满足条件的权向量称为解向量。权值空间中所有解向量组成的区域称为解区。

通常对解区限制：引入阈值threshold，要求解向量满足：

aTy′i≥threshold>0,i∈\[1,…,N\]

使解更可靠（推广性更强），防止优化算法收敛到解区的边界。

## 感知器算法(PLA) ##

### 算法目的 ###

感知器算法由 Rosenblatt 提出，其主要功能是通过设计分类器来判别样本所属的类别；通过对训练样本集的学习，从而得到判别函数权值的解，产生线性可分的样本判别函数。该算法属于非参数算法，优点是不需要对各类样本的统计性质作任何假设，属于确定性方法。

![blog-perceptron-Ncell.png][]

感知器算法是非常好的二分类在线算法。该算法求取一个分离超平面，超平面由w∈R参数化并用来预测。对于一组数据（样本）X=\{ x1,x2,x3...,xn\}，其中每一个xi代表了一个属性值，那么这个属性值所代表的属性的重要程度可能是不同的。我们用一组权重的向量代表每个属性的重要程度W=\{ w1,w2,w3...,wn\}。这样对每一组数据，感知器算法通过计算y=(WTX)来得到一个得分，他可能代表了一些具体含义，比如某客户的信用额度。那么当score与某一临界值作比较时，当score大于临界值时，就是正值表示的含义是发信用卡，当score小于该临界值时，就是负值表示不发信用卡，这样分类器就产生了。那么，我们最终通过计算sign(y)来预测标签，得到样本的分类。

h(x)=sign(∑i=1nwixi−threshold)=sign(∑i=1nwixi\+(threshold)(\+1))=sign(∑i=1nwixi\+w0x0)=sign(∑i=1nwixi)=sign(WTX)

相应的，在二维空间中，h(x)变成了如下形式

h(x)=sign(w0\+w1x1\+w2x2)

### 基本思想 ###

以最简单的二分类问题为例，PLA算法的基本思想是，最开始的时候随便取得权重曲线Wn，这条曲线应用到已知的训练数据集中，算法仅在预测错误时修正权值w。如果正确的标签是y=1，那么权值修正为w\+x；如果y=−1，权值变为w−x，这时候我们去更新我们的曲线Wn\+1=Wn\+ynxn。

![578330-20161210102349772-1429279802.png][]![578330-20161210102701460-1381585066.png][]

根据上图，由于权向量w是分割线的法向量，无论发生错误的点是正值还是负值，经过修正后的分割线调整了方向从而向错误点靠拢，就是说他更接近那条完美的分割线。算法的具体描述是：

![SouthEast][]

from numpy import *
    
    def naive_pla(datas):
        w = datas[0][0]
        iteration = 0
        while True:
            iteration += 1
            false_data = 0
    
            for data in datas:
                t = dot(w, data[0])
                if sign(data[1]) != sign(t):
                    error = data[1]  
                    false_data += 1
                    w += error * data[0]
            print 'iter%d (%d / %d)' % (iteration, false_data, len(datas))
            if not false_data:
                break
        return w

### 可行性分析 ###

想让PLA算法可停止，必须能够找到至少一条直线将训练数据集D划分成正值和负值两个部分，即必须有无错的权向量存在。这样的D我们称它为“线性可分”的。D线性可分是PLA停止的必要条件，那么他是充分条件吗？即如果D线性可分，PLA一定会停止吗？证明如下：

![578330-20161210103551101-2011683489.png][]

通俗的说就是，如果D里面的数据能划分，就一定能找到那条（其实有无数条）划分线；此时，在D里面随便选一个点，它一定处在划分线的某一侧（不是直线上），并且这一侧所有其他点的计算符号都与它相同，所以这些点到直线的距离大于零（不等式（1）的意义）；根据这些条件得到不等式（2），它告诉我们权向量就像11点50的分针，近似目标向量就像同一时刻的时针，每一次修正，分针都离时针更近了！

但是上边的证明还不够完美，向量内积不仅反映了向量的角度还反映了其长度，两个向量就算夹角不变，只要长度变化，内积也可以增大！

不错，权向量的长度会怎么变化，推导如下

![578330-20161210103702241-1595137153.png][]

可以看到，修正之后权向量的长度，相较于修正之前的增加有一个上限，或者说它的长度增长是较慢的。这个上限由D中距离坐标原点最远的那个点决定。

### 缺点 ###

1.  PLA的算法是局限在线性可分的训练集上的，然而我们拿到一个训练集，并不知道其到底是不是线性可分，如果不是，PLA的算法程序将无限循环下去，这样做是不可行的。
2.  即使训练集是线性可分，我们也不知道PLA什么时候才能找到一个合适的解，如果要循环很多次才能找到，这对于实际使用是开销很大的。

### 改进 口袋算法(Pocket Algorithm) ###

对于那些有杂质的数据来说，要做到线性可分是非常困难的，因此我们采用的方法是找到一条直线，它是所有可能直线当中犯错误最少的？这是一个很难的问题，因为所含的直线太多了，你必须完整遍历一遍之后才能找到最优解，这是数学上的NP-hard问题。因此又提出了妥协的结果：口袋算法(Pocket Algorithm)。

![578330-20161210104105913-835177747.png][]

import numpy as np
    
    def pocket_pla(datas, limit):
        ###############
        def _calc_false(vec):
            res = 0
            for data in datas:
                t = np.dot(vec, data[0])
                if np.sign(data[1]) != np.sign(t):
                    res += 1
            return res
        ###############
        w = np.random.rand(5)
        least_false = _calc_false(w)
        res = w
    
        for i in xrange(limit):
            data = random.choice(datas)
            t = np.dot(w, data[0])
            if np.sign(data[1]) != np.sign(t):
                t = w + data[1] * data[0]
                t_false = _calc_false(t)
    
                w = t
    
                if t_false <= least_false:
                    least_false = t_false
                    res = t
        return res, least_false

同理，Pocket算法也有它自己的缺点:

1.  wt是随机的，可能算了很多次都没有找出一个更好的。
2.  假设数据一开始就是线性可分，那么这个算法找出来的未必是最好解，且时间花费也可能比较大。

[20130601125547513]: /images/20220612/44398ef6ceb341f7a2a85a20fed9cb6e.png
[20130601125913897]: /images/20220612/0bee98cf8f3c4fd2b9f1c1e791208056.png
[blog-perceptron-Ncell.png]: http://wizmann-tk-pic.u.qiniudn.com/blog-perceptron-Ncell.png
[578330-20161210102349772-1429279802.png]: http://images2015.cnblogs.com/blog/578330/201612/578330-20161210102349772-1429279802.png
[578330-20161210102701460-1381585066.png]: /images/20220612/7955c190db374b5c8145ee72f1130bb4.png
[SouthEast]: /images/20220612/82bab9174ee54098bc691f4f66aefbfb.png
[578330-20161210103551101-2011683489.png]: /images/20220612/252653f5854b44d6a43dec7e53056a42.png
[578330-20161210103702241-1595137153.png]: /images/20220612/61028456df9b456786325f2a6b0f51f2.png
[578330-20161210104105913-835177747.png]: /images/20220612/a775867af36545448b1d6d61b170dbc9.png