DanielLaah

手撸机器学习算法系列(一) - 感知机


本篇介绍如何使用Python+Numpy实现一个基本的感知机模型, 并在sklearn的iris数据集上测试. 感知机的理论部分可参见《统计学习方法》笔记 (三) - 感知机.
代码: Github


感知机对应于特征空间中将实例划分为正负两类的分离超平面, 想要实现一个感知机模型, 就要知道如何求得这个超平面. 由《统计学习方法》笔记 (三) - 感知机我们知道, 感知机的损失函数定义为:
$$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_0 +b)$$
并且它使用随机梯度下降(Stochastic Gradient Descent)算法不断极小化损失函数. 这里我们将$w, b$合在一起定义为weight方便代码实现.

1
2
3
4
5
6
import random
import numpy as np
from sklearn.metrics import accuracy_score
class Perceptron(object):
def __init__(self):
self.weight = None

接下来我们就要实现随机梯度下降算法, 将其定义为fit函数. 因为我们将$w, b$合并了, 所以对于样本$X$ 我们需要将其加上偏置项. 在随机梯度下降算法开始之前, 需要将权重weight初始化, 这里就直接初始化为0.

1
2
3
4
5
6
def fit(self, X, y, alpha=0.001, max_iter=1000):
X, y = np.array(X), np.array(y)
sample_nums = X.shape[0]
X = np.column_stack((np.ones(sample_nums), X))
feature_nums = X.shape[1]
self.weight = np.zeros((feature_nums, 1))

感知机是误分类点驱动的, 每次随机梯度下降迭代的时候, 需要随机选取一个误分类点来优化, 所以我们需要记录误分类样本的index. 然后随机选取一个误分类样本计算梯度, 更新weight. 这里注意在更新weight的时候, 需要乘以一个学习率$\alpha$. 这样不断迭代, 就可以找到我们所需要的weight. 这里需要注意的是, 感知机只能处理线性可分问题, 当线性不可分时, 优化算法无法收敛(震荡), 所以这里设置了一个max_iter来限制最大迭代次数.

1
2
3
4
5
6
7
8
9
idx = np.array([i for i in range(sample_nums)])
mis_idx = idx[(np.dot(X, self.weight).reshape(sample_nums,) * y) <= 0]
iteration = 0
while(len(mis_idx) > 0 and iteration < max_iter):
rand_mis_idx = random.choice(mis_idx)
self.weight += (alpha * y[rand_mis_idx] * X[rand_mis_idx]).reshape(feature_nums, 1)
mis_idx = idx[(np.dot(X, self.weight).reshape(sample_nums,) * y) <= 0]
iteration += 1
return self

在得到最优weight之后, 实现predictscore方法就很简单了. 权重与样本的内积大于0时, 预测该样本为正样本; 权重与样本的内积小于0时, 预测该样本为负样本;

1
2
3
4
5
6
7
8
9
10
11
12
def predict(self, X):
X = np.array(X)
if X.ndim == 1:
X = np.concatenate([np.ones(1), X])
return 1 if X.dot(self.weight)[0] >= 0 else 0
sample_nums = X.shape[0]
X = np.column_stack((np.ones(sample_nums), X))
return np.apply_along_axis(lambda x: 1 if x >= 0 else -1, 1, np.dot(X, self.weight))

def score(self, X, y):
y_predict = self.predict(X)
return accuracy_score(y_predict, y)

下面使用sklearn中的iris数据集来测试一下, 一下为测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from sklearn import datasets
from sklearn.model_selection import train_test_split
from perceptron import Perceptron

if __name__ == '__main__':
iris = datasets.load_iris()
X = iris.data
y = iris.target
# 该数据集一共有3类, 我们只用y=0和y=1这两个类, 并且将标签y=0改为y=-1
X = X[y < 2]
y = y[y < 2]
y[y == 0] = -1
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=8827)
clf = Perceptron().fit(X, y)
print('准确率: {}%'.format(clf.score(X_test, y_test) * 100))

输出结果如下:

这里我们就完整地实现了感知机模型, 以上代码可在这里下载:Github