感知机算法

感知机其实就是逻辑回归的轻量版，就是找出一个简单的分类超平面，从而将正负样本分割出来

算法简介

对于样本集合,如下

x = [[3,3], [4,3], [1,1]...]
y = [1,1,-1...]

我们期望找到一个函数，确定其中的w和b

f(x) = sign(w*x + b)

sign()函数是一个判别函数，代表如果wx+b>0的话f(x) = 1,如果wx+b < 0的话f(x) = -1,这样我们就能很好的拟合和预测对于一个x[i]是属于1还是-1样本的了

首先我们需要定义分类错误的情况和损失函数，也就是一个我们可以优化的损失函数，从而优化我们的回归方程

很明显一个定义损失函数的方式是对于某一对(w,b)，使用f(x)分类错误的点的个数；或者也可以计算误分类点到超平面的距离

对于点到平面的计算公式如下：

|w*x+b|/||w||

对于某一个点来说，我们可以很容易得到，误分类点的计算如下：

-y(w*x+b) > 0

1. 对于正样本来说，y = 1,如果分类错误的话，wx + b < 0，所以 -y(wx+b) > 0
2. 对于负样本来说，y = -1,如果分类错误的话，wx + b > 0，所以 -y(wx+b) > 0

所以我们的损失函数可以为

∑-y(w*x+b)

接下来就可以使用梯度下降的方式来不断的更新w和b的值，从而得到最小的损失函数，根据多元函数的求导公式可得：

δf/δw = -Σy*x
δf/δb = -Σy

其中-Σy*x,为所有分类错误的点的标签和特征的乘积和

所以我们的梯度变化为：

w = w + (-Σy*x)*η
b = b + (-Σy)*η

其中η为变化的步长

简单的算法实现

#!/usr/bin/python
# -*- coding: utf-8 -*-
# 单层感知机

import numpy as np
import matplotlib.pyplot as plt
# %matplotlib inline

# 绘制正负样本点
def draw_dot(x,y):
    for i in range(len(y)):
        if y[i] == 1:
            # 正样本点画为红色
            plt.scatter(x[i][0], x[i][1], color="red")
        else:
            # 负样本点画黑色
            plt.scatter(x[i][0], x[i][1], color="black")

# 绘制分类直线
def draw_line(w, b):
    line_x = [0,10]
    line_y = -(b + w[0] * line_x)/w[1]  # 因为 w1 * x[1] + w2 * x2 + b = 0,取y = x2，可得y=-(b + w1 * x1)/w1

    plt.plot(line_x, line_y)

# 随机取一些样本
x = np.array([[3,3], [4,3], [1,1]])
y = np.array([1,1,-1])

# 画一下样本点
draw_dot(x, y)
# plt.show()
w = [0,0] # 初始化一下每个特征的权重
b = 0 # 初始化截距
lr = 1 # 梯度下降的步长

for j in range(100): # 遍历个100次吧
    wrong_nums = 0 # 分类错误的点的个数
    for i in range(len(y)):
        if y[i] != np.sign(np.dot(w, x[i]) + b): # numpy.sign就是如果参数大于0返回1,如果参数小于0返回-1
            wrong_nums += 1
            w = w + lr * y[i] * x[i] # 梯度下降的学习算法计算出来的w,由 w*x+b=0
            b = b + lr * y[i]
    if wrong_nums == 0:
        break

draw_line(w,b) # 划线
plt.show() # 显示图像

image.png