练习：感知机算法

发表于 2018-08-04 分类于机器学习 Waline： 0 阅读次数： 298

感知机算法是 <统计学习方法> 这本书讲的第一个机器学习算法，据说是最简单的机器学习算法。这里参考书中的例子，使用程序实现该算法，以便加深理解。

感知机学习算法是误分类驱动的，可采用随机梯度下降法求解。

原始形式

算法介绍

具体来讲，先任意选择一个超平面 (参数为向量 $w_{0}$ 和实数 $b_{0}$ )，然后用梯度下降法不断极小化目标函数

$\begin{matrix} (1) & min_{w, b} L (w, b) = - \sum_{x_{i} \in M} y_{i} (w \cdot x_{i} + b) \end{matrix}$

该目标函数的梯度为

$\begin{aligned} (2) & ▽_{w} L (w, b) & = \frac{\partial (min_{w, b} L (w, b))}{\partial w} = - \sum_{x_{i} \in M} y_{i} x_{i} \\ (3) & ▽_{b} L (w, b) & = \frac{\partial (min_{w, b} L (w, b))}{\partial b} = - \sum_{x_{i} \in M} y_{i} \end{aligned}$

沿梯度的相反方向移动可使梯度减小，这就是梯度下降的含义。所谓随机梯度下降，就是每次随机选择一个误分类点使变量的梯度下降，与此相对的是批梯度下降法。

随机梯度下降的更新规则如下

$\begin{aligned} (4) & w & \leftarrow w + η y_{i} x_{i} \\ (5) & b & \leftarrow b + η y_{i} \end{aligned}$

算法分析

原始形式的训练过程如下

选取初始参数值 $w_{0}, b_{0}$
在训练集中选取样本数据 $(x_{i}, y_{i})$
如果 $y_{i} (w \cdot x_{i} + b) \leq 0$ 则更新参数值
$\begin{aligned} (6) & w & \leftarrow w + η y_{i} x_{i} \\ (7) & b & \leftarrow b + η y_{i} \end{aligned}$
转到第 2 步继续，直到训练集中没有误分类点

由训练过程可知，该算法的核心包括两部分

误分类点的判定
参数值的更新

下面通过 java 程序实现该算法

算法实现

问题：训练集包含正样本 $x_{1} = (3, 3)^{T}$ ， $x_{2} = (4, 3)^{T}$ ，负样本 $x_{3} = (1, 1)^{T}$ ，求解感知机模型 $f (x) = s i g n (w \cdot x + b)$

样本定义

这里仅用于演示算法，故暂不考虑扩展性。

/**
 * 训练样本
 *
 * @author gorden5566
 * @date 2018/8/4
 */
public class Example {
    /**
     * 样本点名字
     */
    private String name;

    /**
     * 输入(为便于理解，使用两个变量表示输入向量)
     */
    private double x1;
    private double x2;

    /**
     * 输出(又叫做标记，1表示正样本，-1表示负样本)
     */
    private double y;

    public Example(String name, double x1, double x2, double y) {
        this.name = name;
        this.x1 = x1;
        this.x2 = x2;
        this.y = y;
    }

    public double getX1() {
        return x1;
    }

    public double getX2() {
        return x2;
    }

    public double getY() {
        return y;
    }

    @Override
    public String toString() {
        return "Example{" +
            "name='" + name + '\'' +
            ", x1=" + x1 +
            ", x2=" + x2 +
            ", y=" + y +
            '}';
    }
}

参数 w 和 b

同样，定义参数 w 和 b 的数据结构

/**
 * 感知机参数
 *
 * @author gorden5566
 * @date 2018/8/4
 */
public class Parameter {
    /**
     * 参数w
     */
    private double w1;
    private double w2;

    /**
     * 参数b
     */
    private double b;

    public Parameter(double w1, double w2, double b) {
        this.w1 = w1;
        this.w2 = w2;
        this.b = b;
    }

    public double getW1() {
        return w1;
    }

    public void setW1(double w1) {
        this.w1 = w1;
    }

    public double getW2() {
        return w2;
    }

    public void setW2(double w2) {
        this.w2 = w2;
    }

    public double getB() {
        return b;
    }

    public void setB(double b) {
        this.b = b;
    }

    @Override
    public String toString() {
        return "Parameter{" +
            "w1=" + w1 +
            ", w2=" + w2 +
            ", b=" + b +
            '}';
    }
}

误分类点判定

其实就是计算样本点到分离超平面的函数间隔 $y_{i} (w \cdot x_{i} + b)$ ，若间隔小于 0 则认为是误分类，函数间隔的计算代码如下

/**
 * 计算距离(其实就是SVM的函数间隔)
 *
 * 公式：y(wx+b)
 *
 * distance <= 0, 则分类结果错误
 * distance > 0, 则分类结果正确
 *
 * @param example
 * @param parameter
 * @return
 */
private static double calcDistance(Example example, Parameter parameter) {
    // 计算wx(向量内积)
    double wx = parameter.getW1() * example.getX1() + parameter.getW2() * example.getX2();
    double distance = example.getY() * (wx + parameter.getB());
    return distance;
}

参数的更新

如果当前选择的样本点是误分类点，则使用该样本更新参数值

/**
 * 更新参数
 *
 * @param example
 * @param parameter
 * @param eta
 */
private static void updateParameters(Example example, Parameter parameter, double eta) {
    // wi = wi + eta * y * xi
    double w1 = parameter.getW1() + eta * example.getY() * example.getX1();
    double w2 = parameter.getW2() + eta * example.getY() * example.getX2();
    parameter.setW1(w1);
    parameter.setW2(w2);

    // b = b + eta * y
    parameter.setB(parameter.getB() + eta * example.getY());
}

训练

有了以上这些，我们就可以实现感知机算法了。实现的思路是：

设置误分类标记为 False (表示这一次循环开始啦)，对样本集进行遍历，检查样本是否误分类。
如果误分类则更新参数值，同时误分类标记置为 True (表示存在误分类情况)。
检查误分类标记，如果为 False 则结束

重复上述动作，直到退出循环。具体代码如下

for (int i = 0; i < 100; i++) {
    // 是否有误分类
    boolean hasMisClassification = false;
    for (Example example : trainingSet) {
        // 误分类时更新参数
        if (calcDistance(example, parameter) <= 0) {
            hasMisClassification = true;
            updateParameters(example, parameter, eta);
        }
    }

    // 全部分类正确，退出循环
    if (!hasMisClassification) {
        break;
    }
}

对样本集进行训练，训练结果如下

第1次更新：Example{name='x1', x1=3.0, x2=3.0, y=1.0}, Parameter{w1=0.0, w2=0.0, b=0.0}
第1次更新后：Parameter{w1=3.0, w2=3.0, b=1.0}
第2次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, Parameter{w1=3.0, w2=3.0, b=1.0}
第2次更新后：Parameter{w1=2.0, w2=2.0, b=0.0}
第3次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, Parameter{w1=2.0, w2=2.0, b=0.0}
第3次更新后：Parameter{w1=1.0, w2=1.0, b=-1.0}
第4次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, Parameter{w1=1.0, w2=1.0, b=-1.0}
第4次更新后：Parameter{w1=0.0, w2=0.0, b=-2.0}
第5次更新：Example{name='x1', x1=3.0, x2=3.0, y=1.0}, Parameter{w1=0.0, w2=0.0, b=-2.0}
第5次更新后：Parameter{w1=3.0, w2=3.0, b=-1.0}
第6次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, Parameter{w1=3.0, w2=3.0, b=-1.0}
第6次更新后：Parameter{w1=2.0, w2=2.0, b=-2.0}
第7次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, Parameter{w1=2.0, w2=2.0, b=-2.0}
第7次更新后：Parameter{w1=1.0, w2=1.0, b=-3.0}
训练结果：Parameter{w1=1.0, w2=1.0, b=-3.0}

可以看到每一次更新参数时使用的样本，以及更新后的结果。最终的参数结果为

$\begin{matrix} (8) & w_{1} = 1, w_{2} = 1, b = - 3 \end{matrix}$

分离超平面为

$\begin{matrix} (9) & x^{(1)} + x^{(2)} - 3 = 0 \end{matrix}$

感知机模型为

$\begin{matrix} (10) & f (x) = s i g n (x^{(1)} + x^{(2)} - 3) \end{matrix}$

完整代码

/**
 * 感知机算法原始形式demo
 *
 * 正样本(3,3)和(4,3)
 * 负样本(1,1)
 *
 * @author gorden5566
 * @date 2018/8/4
 */
public class Perceptron {
    public static void main(String[] args) {
        // 训练样本初始化
        List<Example> trainingSet = getTrainingSet();

        // 参数初始化
        Parameter parameter = new Parameter(0, 0, 0);

        // 学习率
        double eta = 1;

        int times = 0;
        for (int i = 0; i < 100; i++) {
            // 是否有误分类
            boolean hasMisClassification = false;
            for (Example example : trainingSet) {
                // 误分类时更新参数
                if (calcDistance(example, parameter) <= 0) {
                    times++;
                    hasMisClassification = true;
                    // 输出样本和参数
                    System.out.println("第" + times + "次更新：" + example + ", " + parameter);
                    updateParameters(example, parameter, eta);
                    System.out.println("第" + times + "次更新后：" + parameter);
                }
            }

            // 全部分类正确，退出循环
            if (!hasMisClassification) {
                break;
            }
        }

        System.out.println("训练结果：" + parameter);
    }

    /**
     * 计算距离(其实就是SVM的函数间隔)
     *
     * 公式：y(wx+b)
     *
     * distance <= 0, 则分类结果错误
     * distance > 0, 则分类结果正确
     *
     * @param example
     * @param parameter
     * @return
     */
    private static double calcDistance(Example example, Parameter parameter) {
        // 计算wx(向量内积)
        double wx = parameter.getW1() * example.getX1() + parameter.getW2() * example.getX2();
        double distance = example.getY() * (wx + parameter.getB());
        return distance;
    }

    /**
     * 更新参数
     *
     * @param example
     * @param parameter
     * @param eta
     */
    private static void updateParameters(Example example, Parameter parameter, double eta) {
        // wi = wi + eta * y * xi
        double w1 = parameter.getW1() + eta * example.getY() * example.getX1();
        double w2 = parameter.getW2() + eta * example.getY() * example.getX2();
        parameter.setW1(w1);
        parameter.setW2(w2);

        // b = b + eta * y
        parameter.setB(parameter.getB() + eta * example.getY());
    }

    /**
     * 获取训练样本
     *
     * @return
     */
    private static List<Example> getTrainingSet() {
        List<Example> trainingSet = new ArrayList<>();
        Example example1 = new Example("x1",3, 3, 1);
        Example example2 = new Example("x2",4, 3, 1);
        Example example3 = new Example("x3",1, 1, -1);
        trainingSet.add(example1);
        trainingSet.add(example2);
        trainingSet.add(example3);

        return trainingSet;
    }
}

对偶形式

感知机学习算法的对偶形式基本思想是，将 w 和 b 表示为实例 $x_{i}$ 和标记 $y_{i}$ 的线性组合的形式，先求解组合的系数然后可得到 w 和 b。

算法介绍

仍按照原始形式对参数 w 和 b 进行更新

$\begin{aligned} (11) & w & \leftarrow w + η y_{i} x_{i} \\ (12) & b & \leftarrow b + η y_{i} \end{aligned}$

假设更新了 n 次。对于样本 $(x_{i}, y_{i})$ ，w 的增量可表示为 $α_{i} y_{i} x_{i}$ ，b 的增量可表示为 $α_{i} y_{i}$ ，其中 $α_{i} = n_{i} η$ ( $n_{i}$ 表示这 n 次修改中，样本 i 误分类导致的修改有 $n_{i}$ 次)。则 w 和 b 可通过如下转换公式得到

$\begin{aligned} (13) & w & = \sum_{i = 1}^{m} α_{i} y_{i} x_{i} \\ (14) & b & = \sum_{i = 1}^{m} α_{i} y_{i} \end{aligned}$

其中 $α_{i} \geq 0$ ，维数和样本容量相等。当 $η = 1$ 时， $α_{i}$ 表示第 i 个样本点由于误分类导致的更新次数。

可以想象，样本点距离分离超平面越近，则每次更新越有可能导致该样本点被误分类，从而使其更新的次数增多。也就是说样本点距离分离超平面越近，它对学习的结果影响越大 (这种样本点更有可能是 SVM 中的支持向量)

算法核心如下

误分类点判断

$\begin{matrix} (15) & y_{i} (\sum_{j = 1}^{n} α_{j} y_{j} x_{j} \cdot x_{i} + b) \leq 0 \end{matrix}$

其中 $x_{j} \cdot x_{i}$ 的值提前计算好，存储到 Gram 矩阵中，每次计算时直接查询获取

更新规则

$\begin{aligned} (16) & α_{i} & \leftarrow α_{i} + η \\ (17) & b & \leftarrow b + η y_{i} \end{aligned}$

b 的更新规则不变。w 的更新规则变成 $α$ 的更新规则，向量 $α$ 记录了 $η$ 应用于每个样本的次数，然后等到训练介绍再统一计算更新结果，得到 w

算法实现

参数定义

首先要修改参数定义，将 w 改为 $α$

/**
 * @author gorden5566
 * @date 2018/8/5
 */
public class ParameterDual {
    /**
     * 参数alpha，大小等于样本容量
     */
    private double[] alpha;

    /**
     * 参数b
     */
    private double b;

    /**
     * 构造函数
     *
     * @param m 样本容量
     * @param b
     */
    public ParameterDual(int m, double b) {
        this.alpha = new double[m];
        this.b = b;
    }


    public double[] getAlpha() {
        return alpha;
    }

    public double getB() {
        return b;
    }

    public void setB(double b) {
        this.b = b;
    }

    @Override
    public String toString() {
        return "ParameterDual{" +
            "alpha=" + Arrays.toString(alpha) +
            ", b=" + b +
            '}';
    }
}

Gram 矩阵计算

本例中的 Gram 矩阵如下 (比如第一行第二列表示 $x_{2}$ 和 $x_{1}$ 的内积为 21.0)

$\begin{matrix} (18) & (\begin{matrix} 18.0 & 21.0 & 6.0 \\ 21.0 & 25.0 & 7.0 \\ 6.0 & 7.0 & 2.0 \end{matrix}) \end{matrix}$

代码如下

/**
 * 计算gram矩阵
 *
 * @param trainingSet
 * @return
 */
private static double[][] calcGram(List<Example> trainingSet) {
    int m = trainingSet.size();
    double[][] gram = new double[m][m];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            Example xi = trainingSet.get(i);
            Example xj = trainingSet.get(j);
            // 内积
            gram[i][j] = xi.getX1() * xj.getX1() + xi.getX2() * xj.getX2();
        }
    }

    return gram;
}

误分类判断

若 $y_{i} (\sum_{j = 1}^{n} α_{j} y_{j} x_{j} x_{i} + b) \leq 0$ 则表示该样本点误分类

/**
 * 计算对偶形式的误分类数据
 *
 * 公式：y_i (\sum_{j=1}^{n} \alpha_j y_j x_j x_i + b)
 *
 * @param trainingSet
 * @param parameter
 * @param i 表示当前处理的是第几个样本
 * @param gram
 * @return
 */
private static double calcDistance(List<Example> trainingSet, ParameterDual parameter, int i, double[][] gram) {
    //
    double sum = 0;
    for (int j = 0; j < trainingSet.size(); j++) {
        Example examplej = trainingSet.get(j);

        // 第j个样本的标记
        double yj = examplej.getY();

        double alphaj = parameter.getAlpha()[j];

        // \alpha_j y_j x_j x_i 其中 x_j x_i 直接从 gram 矩阵中获取
        sum += alphaj * yj * gram[j][i];
    }

    // 代入公式
    double result =  trainingSet.get(i).getY() * (sum + parameter.getB());

    return result;
}

参数更新

更新规则如下

$\begin{aligned} (19) & α_{i} & = α_{i} + η \\ (20) & b & = b + η * y_{i} \end{aligned}$

/**
 * 更新参数
 *
 * @param example
 * @param parameter
 * @param i
 * @param eta
 */
private static void updateParameters(Example example, ParameterDual parameter, int i, double eta) {
    double[] alpha = parameter.getAlpha();
    double b = parameter.getB();

    // \alpha_i = \alpha_i + \eta
    alpha[i] = alpha[i] + eta;

    // b = b + \eta * y+i
    parameter.setB(b + eta * example.getY());
}

训练

训练过程和之前类似，区别是这里需要用到下标 i

for (int count = 0; count < 100; count++) {
    // 是否有误分类
    boolean hasMisClassification = false;
    for (int i = 0; i < m; i++) {
        Example example = trainingSet.get(i);
        // 误分类时更新参数
        if (calcDistance(trainingSet, parameter, i, gram) <= 0) {
            times++;
            hasMisClassification = true;
            updateParameters(example, parameter, i, eta);
        }
    }

    // 全部分类正确，退出循环
    if (!hasMisClassification) {
        break;
    }
}

参数转换

使用对偶形式训练出结果后，还需要转换成 w 和 b

/**
 * 转换为原始参数
 *
 * @param parameterDual
 * @param trainingSet
 * @return
 */
private static Parameter convertToOriginParameter(ParameterDual parameterDual, List<Example> trainingSet) {
    double w1 = 0;
    double w2 = 0;
    double[] alpha = parameterDual.getAlpha();
    for (int i = 0; i < alpha.length; i++) {
        Example example = trainingSet.get(i);

        // w = \sum_{i=1}^{m} \alpha_i y_i x_i  其中 w 和 x_i 均为向量
        w1 += alpha[i] * example.getX1() * example.getY();
        w2 += alpha[i] * example.getX2() * example.getY();

        // b = \sum_{i=1}^{m} \alpha_i y_i 因为已经计算出，可直接使用
    }

    Parameter originParameter = new Parameter(w1, w2, parameterDual.getB());
    return originParameter;
}

训练结果

第1次更新：Example{name='x1', x1=3.0, x2=3.0, y=1.0}, ParameterDual{alpha=[0.0, 0.0, 0.0], b=0.0}
第1次更新后：ParameterDual{alpha=[1.0, 0.0, 0.0], b=1.0}
第2次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, ParameterDual{alpha=[1.0, 0.0, 0.0], b=1.0}
第2次更新后：ParameterDual{alpha=[1.0, 0.0, 1.0], b=0.0}
第3次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, ParameterDual{alpha=[1.0, 0.0, 1.0], b=0.0}
第3次更新后：ParameterDual{alpha=[1.0, 0.0, 2.0], b=-1.0}
第4次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, ParameterDual{alpha=[1.0, 0.0, 2.0], b=-1.0}
第4次更新后：ParameterDual{alpha=[1.0, 0.0, 3.0], b=-2.0}
第5次更新：Example{name='x1', x1=3.0, x2=3.0, y=1.0}, ParameterDual{alpha=[1.0, 0.0, 3.0], b=-2.0}
第5次更新后：ParameterDual{alpha=[2.0, 0.0, 3.0], b=-1.0}
第6次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, ParameterDual{alpha=[2.0, 0.0, 3.0], b=-1.0}
第6次更新后：ParameterDual{alpha=[2.0, 0.0, 4.0], b=-2.0}
第7次更新：Example{name='x3', x1=1.0, x2=1.0, y=-1.0}, ParameterDual{alpha=[2.0, 0.0, 4.0], b=-2.0}
第7次更新后：ParameterDual{alpha=[2.0, 0.0, 5.0], b=-3.0}
训练结果：ParameterDual{alpha=[2.0, 0.0, 5.0], b=-3.0}
对应原始参数：Parameter{w1=1.0, w2=1.0, b=-3.0}

可以看出，该训练步骤和原始形式相对应

完整代码

/**
 * @author gorden5566
 * @date 2018/8/5
 */
public class PerceptronDual {

    public static void main(String[] args) {
        // 训练样本初始化
        List<Example> trainingSet = getTrainingSet();

        // 样本大小
        int m = trainingSet.size();

        // 参数初始化
        ParameterDual parameter = new ParameterDual(m, 0);

        // 学习率
        double eta = 1;

        // 计算gram矩阵
        double[][] gram = calcGram(trainingSet);
        printGram(gram);

        int times = 0;
        for (int count = 0; count < 100; count++) {
            // 是否有误分类
            boolean hasMisClassification = false;
            for (int i = 0; i < m; i++) {
                Example example = trainingSet.get(i);

                // 误分类时更新参数
                if (calcDistance(trainingSet, parameter, i, gram) <= 0) {
                    times++;
                    hasMisClassification = true;
                    // 输出样本和参数
                    System.out.println("第" + times + "次更新：" + example + ", " + parameter);
                    updateParameters(example, parameter, i, eta);
                    System.out.println("第" + times + "次更新后：" + parameter);
                }
            }

            // 全部分类正确，退出循环
            if (!hasMisClassification) {
                break;
            }
        }

        System.out.println("训练结果：" + parameter);

        Parameter originParameter = convertToOriginParameter(parameter, trainingSet);
        System.out.println("对应原始参数：" + originParameter);

    }

    /**
     * 转换为原始参数
     *
     * @param parameterDual
     * @param trainingSet
     * @return
     */
    private static Parameter convertToOriginParameter(ParameterDual parameterDual, List<Example> trainingSet) {
        double w1 = 0;
        double w2 = 0;
        double[] alpha = parameterDual.getAlpha();
        for (int i = 0; i < alpha.length; i++) {
            Example example = trainingSet.get(i);

            // w = \sum_{i=1}^{m} \alpha_i y_i x_i  其中 w 和 x_i 均为向量
            w1 += alpha[i] * example.getX1() * example.getY();
            w2 += alpha[i] * example.getX2() * example.getY();

            // b = \sum_{i=1}^{m} \alpha_i y_i 因为已经计算出，可直接使用
        }

        Parameter originParameter = new Parameter(w1, w2, parameterDual.getB());
        return originParameter;
    }

    /**
     * 计算对偶形式的误分类数据
     *
     * 公式：y_i (\sum_{j=1}^{n} \alpha_j y_j x_j x_i + b)
     *
     * @param trainingSet
     * @param parameter
     * @param i 表示当前处理的是第几个样本
     * @param gram
     * @return
     */
    private static double calcDistance(List<Example> trainingSet, ParameterDual parameter, int i, double[][] gram) {
        //
        double sum = 0;
        for (int j = 0; j < trainingSet.size(); j++) {
            Example examplej = trainingSet.get(j);

            // 第j个样本的标记
            double yj = examplej.getY();

            double alphaj = parameter.getAlpha()[j];

            // \alpha_j y_j x_j x_i 其中 x_j x_i 直接从 gram 矩阵中获取
            sum += alphaj * yj * gram[j][i];
        }

        //
        double result =  trainingSet.get(i).getY() * (sum + parameter.getB());

        return result;
    }

    /**
     * 更新参数
     *
     * @param example
     * @param parameter
     * @param i
     * @param eta
     */
    private static void updateParameters(Example example, ParameterDual parameter, int i, double eta) {
        double[] alpha = parameter.getAlpha();
        double b = parameter.getB();

        // \alpha_i = \alpha_i + \eta
        alpha[i] = alpha[i] + eta;

        // b = b + \eta * y_i
        parameter.setB(b + eta * example.getY());
    }

    /**
     * 打印gram矩阵
     *
     * @param gram
     */
    private static void printGram(double[][] gram) {
        System.out.println("gram matrix: ");
        for (int i = 0; i < gram.length; i++) {
            for (int j = 0; j < gram[0].length; j++) {
                System.out.print(gram[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 计算gram矩阵
     *
     * @param trainingSet
     * @return
     */
    private static double[][] calcGram(List<Example> trainingSet) {
        int m = trainingSet.size();
        double[][] gram = new double[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                Example xi = trainingSet.get(i);
                Example xj = trainingSet.get(j);
                // 内积
                gram[i][j] = xi.getX1() * xj.getX1() + xi.getX2() * xj.getX2();
            }
        }

        return gram;
    }

    /**
     * 获取训练样本
     *
     * @return
     */
    private static List<Example> getTrainingSet() {
        List<Example> trainingSet = new ArrayList<>();
        Example example1 = new Example("x1",3, 3, 1);
        Example example2 = new Example("x2",4, 3, 1);
        Example example3 = new Example("x3",1, 1, -1);
        trainingSet.add(example1);
        trainingSet.add(example2);
        trainingSet.add(example3);

        return trainingSet;
    }
}

说明

以上代码可到 https://github.com/gorden5566/machine-learning 下载

参考

李航。统计学习方法
http://www.hankcs.com/ml/the-perceptron.html

原始形式

算法介绍

算法分析

算法实现

样本定义

参数 w 和 b

误分类点判定

参数的更新

训练

完整代码

对偶形式

算法介绍

算法核心如下

算法实现

参数定义

Gram 矩阵计算

误分类判断

参数更新

训练

参数转换

训练结果

完整代码

说明

参考

预览: