蓝皮书系列 之感知机

感知机作为最经典的学习算法，其基本原理就不再冗述。本片文章对蓝皮书P33~34页的对偶算法进行了实现。

Part i 算法详解

=================感知机对偶形式伪代码=====================
输入：线性可分数据集X，标签y，学习率η
输出：输出α，b；以及决策界面：

图片来源于《统计学习方法》

=======================================================
Step.1 α ← 0，b←0

Step.2 选取某个样本 图片来源于《统计学习方法》
Step.3 判断该样本是否为误分样本, 判断条件如下:
图片来源于《统计学习方法》

如果是，则对α，b按照以下规则更新：

图片来源于《统计学习方法》
Step.4 重复步骤2、3，直至没有误分类的样本
=======================================================

Part ii Python实现

• 定义一个perception()类，输入参数X,y和η
  并初始化内积矩阵Gram，拉格朗日系数 α以及偏置b

def __init__(self,x,y,yta=1.0):
        self.__x = x
        self.__y = y
        # 初始化gamm矩阵
        Gram = np.zeros([x.shape[0],x.shape[0]])
        for i in range(x.shape[0]):
            for j in range(x.shape[0]):
                Gram[i,j] = np.dot(x[i,:],x[j,:].T )
        self.__Gram = Gram
        # 初始化训练处置
        self.a = np.zeros([x.shape[0]])
        self.b = 0
        self.__yta = yta
        self.w = np.zeros([x.shape[1]])

• 在类中定义一个判断函数Condition(self,t)，用于判断某个样本是否为误分类样本。

def Condition(self,t):
        result = 0
        yi = self.__y[t]
        coni = np.sum( self.a * self.__y * self.__Gram[:,t]) + self.b
        if yi * coni <= 0:
            result = 1
        return result

• 接着就可以开始训练感知机了，定义训练函数def fit(self)

def fit(self):
        Num = self.__x.shape[0]
        Out = False
        # 训练
        while True:        
            for i in range(Num):
                if self.Condition(i):
                    self.a[i] += self.__yta
                    self.b += self.__yta * self.__y[i]
                    break
            else:
                Out = True
           
            if Out:
                break
        
        # 计算权重w
        for i in range(Num):
            self.w += self.a[i] * self.__x[i,:] * self.__y[i]

• 到此为止，一个感知器的训练程序基本上已经完成了，但是为了能够让感知机对新的数据进行测试，还得加入一个预测函数predict(self,x)

def predict(self,x):
        return np.sign( np.dot(x,self.w )+self.b )

• 当然了，为了能够清楚的观察到决策界面，所以又增加了一个可视化决策界面的函数。但是对于人类这种三维生物，只有低于三维的世界才有着绝对的上帝视角，所以咱的可视化函数也只对三维以下的数据集有效

def plot_decision_surface(self,x = None):
        if self.__x.shape[1] >2:
            return None
        else:
            import matplotlib.pyplot as plt 
            plt.figure()
            plt.scatter(self.__x[:,0],self.__x[:,1],c=self.__y,marker='p',s=200)
            # 计算超平面
            mgx = np.arange(-5,5,0.01)
            mgy = -self.b-self.w[0]*mgx
            mgy /= self.w[1]
            # 画出超平面
            plt.plot(mgx,mgy)      
            try:
                plt.scatter(x[:,0],x[:,1],c='r',marker='s',s = 50)
            except:
                x = None

Part iii 感知机实验运行结果

• 随机设置了一些坐标点和标签,正反例反别用 紫色和黄色区分

x = np.array([[-3,3],[4,3],[1,1],[2,5],[3,5],[1,2],[2,3]])
y = np.array([-1,1,-1,-1,1,-1,-1])

• 并且设置了两个预测样本，用红色表示

x_test = np.array([[0,0],[5,5]])

调用part ii 中的编写的感知机函数，进行预测

from Perception import perception
per = perception(x,y)
per.fit()
y_pred = per.predict( x_test )
per.plot_decision_surface(x_test)

最终实验结果：

感知机运行结果