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

本文主要是介绍机器学习和数据挖掘（3）：线性模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

感知器模型

基本概念

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

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

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

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

a T y' i \geq t h r e s h o l d > 0, i \in [1, \dots, N]

$a^Ty_i^\prime \geq threshold > 0, i\in [1,\dots,N]$

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

感知器算法(PLA)

算法目的

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

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

h (x) = s i g n (\sum i = 1 n w i x i - t h r e s h o l d) = s i g n (\sum i = 1 n w i x i + (t h r e s h o l d) (+ 1)) = s i g n (\sum i = 1 n w i x i + w 0 x 0) = s i g n (\sum i = 1 n w i x i) = s i g n (W T X)

$\begin{align} h(x) & = sign(\sum_{i=1}^nw_ix_i-threshold) \\& = sign(\sum_{i=1}^nw_ix_i+(threshold)(+1)) \\ & = sign(\sum_{i=1}^nw_ix_i+w_0x_0) \\& = sign(\sum_{i=1}^nw_ix_i) \\ & = sign(W^TX) \end{align}$

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

h (x) = s i g n (w 0 + w 1 x 1 + w 2 x 2)

$h(x)=sign(w_0+w_1x_1+w_2x_2)$

基本思想

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

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

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

可行性分析

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

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

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

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

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

缺点

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

改进口袋算法(Pocket Algorithm)

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

import numpy as npdef pocket_pla(datas, limit):###############def _calc_false(vec):res = 0for data in datas:t = np.dot(vec, data[0])if np.sign(data[1]) != np.sign(t):res += 1return res###############w = np.random.rand(5)least_false = _calc_false(w)res = wfor 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 = tif t_false <= least_false:least_false = t_falseres = treturn res, least_false