每日算法 — 使用java实现感知机：线性分类器与梯度下降权重更新

可莉爸爸 AI算法

引言

感知机（Perceptron）是神经网络领域的奠基算法，由Frank Rosenblatt于1957年提出。作为最简单的线性分类模型，感知机奠定了现代深度学习的基础。本文将用Java从零实现感知机算法，深入讲解其数学原理、梯度下降权重更新机制，并通过完整的代码演示其在二分类问题中的应用。

算法原理

感知机模型

感知机是一个二分类线性模型，其输入为实例的特征向量，输出为实例的类别（+1或-1）。感知机模型可以表示为：

$$f(x) = \text{sign}(w \cdot x + b)$$

其中：
– $w$ 为权重向量
– $b$ 为偏置项
– $\text{sign}$ 为符号函数

损失函数

感知机使用误分类点到超平面的总距离作为损失函数：

$$L(w, b) = -\sum_{x_i \in M} y_i(w \cdot x_i + b)$$

其中 $M$ 为误分类点的集合。

梯度下降更新

对损失函数求梯度：
– $\nabla_w L = -\sum_{x_i \in M} y_i x_i$
– $\nabla_b L = -\sum_{x_i \in M} y_i$

采用随机梯度下降，每次选取一个误分类点 $(x_i, y_i)$ 进行更新：
– $w = w + \eta y_i x_i$
– $b = b + \eta y_i$

其中 $\eta$ 为学习率（$0 < \eta \leq 1$）。

Java实现

项目结构

src/
├── Perceptron.java          // 感知机核心类
├── DataPoint.java           // 数据点类
├── PerceptronDemo.java      // 演示入口
└── DatasetGenerator.java    // 数据集生成器

数据点类

/**
 * 数据点类，表示一个带有标签的特征向量
 */
public class DataPoint {
    private final double[] features;
    private final int label; // +1 或 -1

    public DataPoint(double[] features, int label) {
        this.features = features;
        this.label = label;
    }

    public double[] getFeatures() {
        return features;
    }

    public int getLabel() {
        return label;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("(");
        for (int i = 0; i < features.length; i++) {
            sb.append(String.format("%.2f", features[i]));
            if (i < features.length - 1) sb.append(", ");
        }
        sb.append(") -> ").append(label);
        return sb.toString();
    }
}

感知机核心类

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 感知机算法实现
 * 支持多维度特征的二分类问题
 */
public class Perceptron {
    private double[] weights;    // 权重向量
    private double bias;         // 偏置项
    private double learningRate; // 学习率
    private int maxIterations;   // 最大迭代次数
    private int featureDim;      // 特征维度
    private List<Integer> misclassifiedHistory; // 误分类点数量历史

    public Perceptron(int featureDim, double learningRate, int maxIterations) {
        this.featureDim = featureDim;
        this.learningRate = learningRate;
        this.maxIterations = maxIterations;
        this.weights = new double[featureDim];
        this.bias = 0.0;
        this.misclassifiedHistory = new ArrayList<>();
    }

    /**
     * 使用随机梯度下降训练感知机
     * @param dataPoints 训练数据集
     */
    public void train(List<DataPoint> dataPoints) {
        Random random = new Random(42); // 固定种子保证可复现
        int iteration = 0;

        System.out.println("=== 感知机训练开始 ===");
        System.out.println("学习率: " + learningRate);
        System.out.println("特征维度: " + featureDim);
        System.out.println("训练样本数: " + dataPoints.size());

        while (iteration < maxIterations) {
            int misclassifiedCount = 0;
            List<DataPoint> misclassifiedPoints = new ArrayList<>();

            // 找出所有误分类点
            for (DataPoint point : dataPoints) {
                if (!isCorrectlyClassified(point)) {
                    misclassifiedPoints.add(point);
                    misclassifiedCount++;
                }
            }

            misclassifiedHistory.add(misclassifiedCount);

            // 如果没有误分类点，训练完成
            if (misclassifiedCount == 0) {
                System.out.println("训练完成！共迭代 " + (iteration + 1) + " 次");
                break;
            }

            // 随机选择一个误分类点进行更新
            DataPoint point = misclassifiedPoints.get(random.nextInt(misclassifiedPoints.size()));
            updateWeights(point);

            // 每100次迭代输出一次状态
            if ((iteration + 1) % 100 == 0 || iteration < 10) {
                System.out.printf("迭代 %d: 误分类点数量 = %d%n", iteration + 1, misclassifiedCount);
            }

            iteration++;
        }

        if (iteration >= maxIterations) {
            System.out.println("达到最大迭代次数，训练终止");
        }
    }

    /**
     * 判断数据点是否被正确分类
     */
    private boolean isCorrectlyClassified(DataPoint point) {
        double[] features = point.getFeatures();
        double sum = bias;
        for (int i = 0; i < featureDim; i++) {
            sum += weights[i] * features[i];
        }
        int predicted = sum >= 0 ? 1 : -1;
        return predicted == point.getLabel();
    }

    /**
     * 更新权重和偏置
     * w = w + η * y * x
     * b = b + η * y
     */
    private void updateWeights(DataPoint point) {
        double[] features = point.getFeatures();
        int label = point.getLabel();

        for (int i = 0; i < featureDim; i++) {
            weights[i] += learningRate * label * features[i];
        }
        bias += learningRate * label;
    }

    /**
     * 预测单个数据点的类别
     */
    public int predict(DataPoint point) {
        double[] features = point.getFeatures();
        double sum = bias;
        for (int i = 0; i < featureDim; i++) {
            sum += weights[i] * features[i];
        }
        return sum >= 0 ? 1 : -1;
    }

    /**
     * 计算决策边界的值
     * 对于二维数据，返回 y = -(w0*x + b) / w1
     */
    public double decisionBoundary(double x) {
        if (featureDim == 2 && Math.abs(weights[1]) > 1e-10) {
            return -(weights[0] * x + bias) / weights[1];
        }
        return 0;
    }

    /**
     * 在测试集上评估模型
     */
    public double evaluate(List<DataPoint> testData) {
        int correct = 0;
        for (DataPoint point : testData) {
            if (predict(point) == point.getLabel()) {
                correct++;
            }
        }
        return (double) correct / testData.size();
    }

    public double[] getWeights() {
        return weights.clone();
    }

    public double getBias() {
        return bias;
    }

    public List<Integer> getMisclassifiedHistory() {
        return misclassifiedHistory;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Perceptron{");
        sb.append("weights=[");
        for (int i = 0; i < weights.length; i++) {
            sb.append(String.format("%.4f", weights[i]));
            if (i < weights.length - 1) sb.append(", ");
        }
        sb.append("], bias=").append(String.format("%.4f", bias));
        sb.append(", learningRate=").append(learningRate).append("}");
        return sb.toString();
    }
}

数据集生成器

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 生成线性可分的二分类数据集
 */
public class DatasetGenerator {
    private Random random;

    public DatasetGenerator(long seed) {
        this.random = new Random(seed);
    }

    /**
     * 生成二维线性可分数据集
     * @param n 样本数量
     * @param trueWeights 真实的权重向量（用于生成标签）
     * @param trueBias 真实的偏置项
     * @param noise 噪声水平
     */
    public List<DataPoint> generateLinearDataset(int n, double[] trueWeights, double trueBias, double noise) {
        List<DataPoint> dataset = new ArrayList<>();
        int dim = trueWeights.length;

        for (int i = 0; i < n; i++) {
            double[] features = new double[dim];
            for (int j = 0; j < dim; j++) {
                features[j] = random.nextDouble() * 10 - 5; // [-5, 5]
            }

            // 计算真实标签
            double sum = trueBias;
            for (int j = 0; j < dim; j++) {
                sum += trueWeights[j] * features[j];
            }

            // 添加噪声
            sum += random.nextGaussian() * noise;

            int label = sum >= 0 ? 1 : -1;
            dataset.add(new DataPoint(features, label));
        }

        return dataset;
    }

    /**
     * 生成AND逻辑门数据集
     */
    public List<DataPoint> generateANDDataset() {
        List<DataPoint> dataset = new ArrayList<>();
        dataset.add(new DataPoint(new double[]{0, 0}, -1));
        dataset.add(new DataPoint(new double[]{0, 1}, -1));
        dataset.add(new DataPoint(new double[]{1, 0}, -1));
        dataset.add(new DataPoint(new double[]{1, 1}, 1));
        return dataset;
    }

    /**
     * 生成OR逻辑门数据集
     */
    public List<DataPoint> generateORDataset() {
        List<DataPoint> dataset = new ArrayList<>();
        dataset.add(new DataPoint(new double[]{0, 0}, -1));
        dataset.add(new DataPoint(new double[]{0, 1}, 1));
        dataset.add(new DataPoint(new double[]{1, 0}, 1));
        dataset.add(new DataPoint(new double[]{1, 1}, 1));
        return dataset;
    }

    /**
     * 划分训练集和测试集
     */
    public static void splitDataset(List<DataPoint> dataset, double trainRatio,
                                     List<DataPoint> trainSet, List<DataPoint> testSet) {
        int trainSize = (int) (dataset.size() * trainRatio);
        for (int i = 0; i < dataset.size(); i++) {
            if (i < trainSize) {
                trainSet.add(dataset.get(i));
            } else {
                testSet.add(dataset.get(i));
            }
        }
    }
}

演示入口

import java.util.ArrayList;
import java.util.List;

/**
 * 感知机算法演示
 */
public class PerceptronDemo {
    public static void main(String[] args) {
        // 演示1：逻辑门分类
        demoLogicGate();

        System.out.println("\n" + "=".repeat(60) + "\n");

        // 演示2：二维线性可分数据分类
        demoLinearClassification();
    }

    /**
     * 演示1：AND逻辑门分类
     */
    private static void demoLogicGate() {
        System.out.println("=== 演示1：AND逻辑门分类 ===\n");

        DatasetGenerator generator = new DatasetGenerator(42);
        List<DataPoint> andDataset = generator.generateANDDataset();

        System.out.println("AND逻辑门数据集：");
        for (DataPoint point : andDataset) {
            System.out.println("  " + point);
        }

        Perceptron perceptron = new Perceptron(2, 0.1, 1000);
        perceptron.train(andDataset);

        System.out.println("\n训练结果：" + perceptron);

        System.out.println("\n预测结果：");
        for (DataPoint point : andDataset) {
            int predicted = perceptron.predict(point);
            System.out.printf("  %s -> 预测: %d, 实际: %d%n",
                point, predicted, point.getLabel());
        }

        double accuracy = perceptron.evaluate(andDataset);
        System.out.printf("\n准确率: %.1f%%%n", accuracy * 100);
    }

    /**
     * 演示2：二维线性可分数据分类
     */
    private static void demoLinearClassification() {
        System.out.println("=== 演示2：二维线性可分数据分类 ===\n");

        // 真实的决策边界: 2x + 3y - 5 = 0
        double[] trueWeights = {2.0, 3.0};
        double trueBias = -5.0;

        DatasetGenerator generator = new DatasetGenerator(123);
        List<DataPoint> fullDataset = generator.generateLinearDataset(
            200, trueWeights, trueBias, 0.5);

        List<DataPoint> trainSet = new ArrayList<>();
        List<DataPoint> testSet = new ArrayList<>();
        DatasetGenerator.splitDataset(fullDataset, 0.8, trainSet, testSet);

        System.out.println("真实决策边界: 2x + 3y - 5 = 0");
        System.out.println("训练集大小: " + trainSet.size());
        System.out.println("测试集大小: " + testSet.size());

        Perceptron perceptron = new Perceptron(2, 0.01, 5000);
        perceptron.train(trainSet);

        System.out.println("\n训练结果：" + perceptron);

        double trainAccuracy = perceptron.evaluate(trainSet);
        double testAccuracy = perceptron.evaluate(testSet);

        System.out.printf("\n训练集准确率: %.1f%%%n", trainAccuracy * 100);
        System.out.printf("测试集准确率: %.1f%%%n", testAccuracy * 100);

        // 打印决策边界对比
        System.out.println("\n决策边界对比（x=-2时）：");
        System.out.printf("  真实边界 y = %.4f%n", (-trueWeights[0] * (-2) - trueBias) / trueWeights[1]);
        System.out.printf("  学习边界 y = %.4f%n", perceptron.decisionBoundary(-2));
    }
}

复杂度分析

指标 复杂度 说明
时间复杂度 $O(T \cdot n \cdot d)$ $T$为迭代次数，$n$为样本数，$d$为特征维度
空间复杂度 $O(d)$ 仅需存储权重向量和偏置项
收敛性 $O(1/\gamma^2)$ 当数据线性可分时，Novikoff定理保证收敛

其中 $\gamma$ 为数据到超平面的最小间隔。

运行结果

=== 演示1：AND逻辑门分类 ===

AND逻辑门数据集：
  (0.00, 0.00) -> -1
  (0.00, 1.00) -> -1
  (1.00, 0.00) -> -1
  (1.00, 1.00) -> 1

=== 感知机训练开始 ===
学习率: 0.1
特征维度: 2
训练样本数: 4
迭代 1: 误分类点数量 = 1
迭代 2: 误分类点数量 = 1
迭代 3: 误分类点数量 = 1
训练完成！共迭代 4 次

训练结果：Perceptron{weights=[0.2000, 0.2000], bias=-0.3000, learningRate=0.1}

预测结果：
  (0.00, 0.00) -> -1, 实际: -1 -> 预测: -1, 实际: -1
  (0.00, 1.00) -> -1, 实际: -1 -> 预测: -1, 实际: -1
  (1.00, 0.00) -> -1, 实际: -1 -> 预测: -1, 实际: -1
  (1.00, 1.00) -> 1, 实际: 1 -> 预测: 1, 实际: 1

准确率: 100.0%

算法扩展

对偶形式

感知机还有对偶形式，通过Gram矩阵计算内积：

$$f(x) = \text{sign}\left(\sum_{j=1}^{N} \alpha_j y_j (x_j \cdot x) + b\right)$$

对偶形式适用于高维特征空间，可以利用核函数扩展到非线性分类。

多分类扩展

感知机可以扩展为多分类问题：
– 一对多（One-vs-Rest）：为每个类别训练一个感知机
– 一对一（One-vs-One）：为每对类别训练一个感知机

总结

感知机算法以其简洁优雅的设计，成为理解神经网络和机器学习的最佳入门算法。本文通过完整的Java实现，展示了随机梯度下降的核心机制——通过不断修正误分类点，逐步逼近最优决策边界。掌握感知机后，读者可以顺利过渡到更复杂的多层神经网络和深度学习方法。

Tagged with: