Chapter 2 Perceptron算法

1.感知机学习算法

1.1 概述

​ 感知机模型是一个二分类的的线性模型,其输入为实例的特征向量,输出为实例的类别,取-1和+1二值。感知机对应输入空间(特征空间)中将实例划分为正负两类的分离超平面,属于判别模型。感知机模型如下(其中w和x为感知机模型参数):
f(x)=sign(wx+b)sign(x)={+1,x01,x&lt;0 \begin{array}{l}{f(x)=\operatorname{sign}(w \cdot x+b)} \\ {\operatorname{sign}(x)=\left\{\begin{array}{ll}{+1,} &amp; {x \geqslant 0} \\ {-1,} &amp; {x&lt;0}\end{array}\right.}\end{array} f(x)=sign(w⋅x+b)sign(x)={+1,−1,​x⩾0x<0​​
​ 感知机学习的策略是极小化损失函数,损失函数的得出是根据数据点中误分类的点到分离超平面的的距离,损失函数如下(其中M表示误分类点的个数):
minw,bL(w,b)=xiMyi(wxi+b) \min _{w, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right) w,bmin​L(w,b)=−xi​∈M∑​yi​(w⋅xi​+b)
​ 显然,这个损失函数的值是非负的,并且,当数据点中没有误分类的点时,这时的损失函数的值为0。感知机学习算法是误分类驱动的,具体采用随机梯度下降法,在实际极小化的过程中,不是将所有的误分类点进行梯度下降,而是一次选取一个误分类点使其梯度下降。梯度参数更新如下:
w=w+ηyixib=b+ηyi \begin{array}{l}{w=w+\eta y_{i} x_{i}} \\ {b=b+\eta y_{i}}\end{array} w=w+ηyi​xi​b=b+ηyi​​
​ 这样通过更新损失函数的参数w和b,使得损失函数的值不断减少的0,最终得到相应的w和b参数值,进而得到分类超平面的wxi+b=0w \cdot x_{i}+b=0w⋅xi​+b=0。

1.2 感知机学习算法的原始形式

输入:T={(x1,y1),(x2,y2),,(xN,yN)}T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}T={(x1​,y1​),(x2​,y2​),…,(xN​,yN​)}
xiX=Rn,yiY={1,+1},i=1,2,,N;0&lt;η1x_{i} \in \mathcal{X}=\mathbf{R}^{n}, y_{i} \in \mathcal{Y}=\{-1,+1\}, i=1,2, \ldots, N ; 0&lt;\eta \leqslant 1xi​∈X=Rn,yi​∈Y={−1,+1},i=1,2,…,N;0<η⩽1

输出:w,b;f(x)=sign(wx+b)w,b;f(x)=sign(w\cdot x+b)w,b;f(x)=sign(w⋅x+b)

  1. 选取初值w0,b0w_0,b_0w0​,b0​

  2. 训练集中选取数据(xi,yi)(x_i,y_i)(xi​,yi​)

  3. 如果yi(wxi+b)0y_i(w\cdot x_i+b)\leqslant 0yi​(w⋅xi​+b)⩽0

ww+ηyixibb+ηy \begin{array}{c}{w \leftarrow w+\eta y_{i} x_{i}} \\ {b \leftarrow b+\eta y}\end{array} w←w+ηyi​xi​b←b+ηy​

  1. 转至(2),直至训练集中没有误分类点

** 算法的直观解释:**当一个实例点被误分类,即位于分离超平面的错误的一侧时,则调整w, b的值,使得分离超平面的向该误分类点的一侧移动,以减少该分类点与超平面的距离,直到超平面越过该分类点的使其正确被分类。

代码实现:

#1.数据预处理
data = np.array(df.iloc[:100, [0, 1, -1]])
print(data.shape)
X, y = data[:,:-1], data[:,-1]#取出数据和标签
y = np.array([1 if i == 1 else -1 for i in y])#剔除零元素为-1

#2.感知机算法
class Model:
    
    def __init__(self):
        self.w = np.ones(len(data[0])-1, dtype=np.float32)
        self.b = 0
        self.l_rate = 0.1
    
    #构建函数
    def sign(self, x, w, b):
        y = np.dot(x, w) + b
        return y
    
    #随机梯度下降算法的构建
    def fit(self, X_train, y_train):
        is_wrong = False
        while not is_wrong:
            wrong_count = 0 #误分类点个数
            for d in range(len(X_train)):#遍历整个数据点
                X = X_train[d]
                y = y_train[d]
                #判断是否为误分类点
                if y * self.sign(X, self.w, self.b) <= 0:
                    #梯度下降法更新数据
                    self.w = self.w + self.l_rate*np.dot(y, X)
                    self.b = self.b + self.l_rate*y
                    wrong_count += 1
                    
            if wrong_count == 0: #数据能够正确的分类,没有误分类的点
                    is_wrong = True
        print(wrong_count)
        return 'Perceptron Model!'
            
            
    def score(self):
        pass
        
#3.数据处理
perceptron = Model()
perceptron.fit(X, y)
x_points = np.linspace(4, 7,10)
y_ = -(perceptron.w[0]*x_points + perceptron.b)/perceptron.w[1]
#绘画分类线段
plt.plot(x_points, y_)
plt.plot(data[:50, 0], data[:50, 1], 'bo', color='blue', label='0')
plt.plot(data[50:100, 0], data[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

结果:

Chapter 2 Perceptron算法

1.3 感知机学习算法的对偶形式

**对偶形式的基本想法:**将w和b表示为实例xix_ixi​和标记yiy_iyi​的线性组合的形式,通过求解其系数而求得w和b

算法描述如下:

输入:
T={(x1,y1),(x2,y2),,(xN,yN)}xiX=Rn,yiY={1,+1},i=1,2,,N;o&lt;η1 \begin{array}{l}{T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}} \\ {x_{i} \in \mathcal{X}=\mathbf{R}^{n}, \mathbf{y}_{\mathbf{i}} \in \mathcal{Y}=\{-\mathbf{1},+\mathbf{1}\}, i=\mathbf{1}, 2, \ldots, \mathcal{N} ; \mathbf{o}&lt;\eta \leqslant \mathbf{1}}\end{array} T={(x1​,y1​),(x2​,y2​),…,(xN​,yN​)}xi​∈X=Rn,yi​∈Y={−1,+1},i=1,2,…,N;o<η⩽1​

输出
α,b;f(x)=sign(j=1Nαjyjxjx+b)α=(α1,α2,&ThinSpace;,αN)T \begin{aligned} \alpha, b ; f(x) &amp;=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b\right) \\ \alpha &amp;=\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{N}\right)^{T} \end{aligned} α,b;f(x)α​=sign(j=1∑N​αj​yj​xj​⋅x+b)=(α1​,α2​,⋯,αN​)T​

  1. α0,b0\alpha \leftarrow 0,b\leftarrow 0α←0,b←0
  2. 训练集中选取数据(xi,yi)(x_i,y_i)(xi​,yi​)
  3. 如果yi(j=1Nαjyjxjx+b)0y_i\left(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b\right) \leqslant 0yi​(∑j=1N​αj​yj​xj​⋅x+b)⩽0

αiαi+ηbb+ηyi \begin{array}{l}{\alpha_{i} \leftarrow \alpha_{i}+\eta} \\ {b \leftarrow b+\eta y_{i}}\end{array} αi​←αi​+ηb←b+ηyi​​

  1. 转至(2),直至训练集中没有误分类点

**Notice:**如何实例点更新的次数越多,意味着它距离分离超平面越近,也就是越南正确分类。换句话说,这样的实例对学习结果影响很大。

2.感知机总结

​ 感知机作为二分类的判别模型,当数据集线性可分时,感知机学习算法是收敛的,除此之外,感知机学习算法存在无穷多个解,其解由于不同的初值或不同的迭代顺序而可能有所不同。

上一篇:多层感知器,可视化Python中的决策边界(2D)


下一篇:python – 感知器学习算法需要大量的迭代才能收敛?