REALHW83 二分类逻辑回归

题目链接

题目描述

你需要基于用户的三个数值特征（年龄、月收入、浏览时长）训练一个二分类模型，判断其是否会购买某商品。每条训练数据包含三个特征与一个标签（0或1）。模型使用逻辑回归：以 Sigmoid 作为激活函数，损失为平均交叉熵，并加入 L2 正则。优化方式为批量梯度下降；达到最大迭代次数或相邻两次损失变化小于阈值即停止。随后对给定的测试样本输出预测标签与对应概率（四舍五入保留四位小数）。预测时，概率≥0.5 视为正类，否则为负类。

输入描述:

第1行：n max_iter alpha lam tol：训练样本条数, 最大迭代次数, 学习率, L2正则系数, 损失收敛阈值。
接下来 n 行：每行 a inc dur label 分别为年龄, 月收入, 浏览时长, 标签。
第 n+2 行：m (测试样本数)。
接下来 m 行：每行 a inc dur (仅特征，无标签)。

输出描述: 共 m 行。每行输出：pred prob，pred 为预测标签（0或1），prob 为对应正类概率，保留四位小数。

解题思路

本题要求我们从零开始实现一个带 L2 正则化的逻辑回归模型，并使用批量梯度下降进行训练。这是一个机器学习基础算法的模拟题，核心在于精确地实现各个数学模块。

1. 模型结构

逻辑回归模型由两部分组成：

线性组合: 对输入特征 $x = (x_1, x_2, x_3)$ 进行加权求和，并加上一个偏置项 $b$ ： $z = w_1x_1 + w_2x_2 + w_3x_3 + b = w^T x + b$
Sigmoid 激活函数: 将线性组合的结果 $z$ 映射到 (0, 1) 区间，作为预测为正类 (1) 的概率 $p$ ： $p = \sigma(z) = \frac{1}{1 + e^{-z}}$

2. 损失函数

我们使用平均交叉熵损失，并加入 L2 正则化项以防止模型过拟合。总损失函数 $J$ 定义为： $J(w, b) = -\frac{1}{n} \sum_{i=1}^{n} [y_i \log(p_i) + (1 - y_i) \log(1 - p_i)] + \frac{\lambda}{2} \|w\|^2_2$ 其中 $n$ 是训练样本数, $y_i$ 是第 $i$ 个样本的真实标签, $p_i$ 是模型对第 $i$ 个样本的预测概率, $\lambda$ 是正则化系数, $\|w\|^2_2 = w_1^2 + w_2^2 + w_3^2$ 是权重的 L2 范数平方。

3. 优化算法：批量梯度下降 (BGD)

BGD 的核心思想是在每次迭代时，使用全部训练样本来计算损失函数对参数的梯度，然后沿着梯度的反方向更新参数。

梯度计算:
- 对权重 $w_j$ 的偏导数: $\frac{\partial J}{\partial w_j} = \frac{1}{n} \sum_{i=1}^{n} (p_i - y_i)x_{ij} + \lambda w_j$
- 对偏置 $b$ 的偏导数: $\frac{\partial J}{\partial b} = \frac{1}{n} \sum_{i=1}^{n} (p_i - y_i)$
参数更新:
- $w_j := w_j - \alpha \frac{\partial J}{\partial w_j}$
- $b := b - \alpha \frac{\partial J}{\partial b}$ 其中 $\alpha$ 是学习率。

4. 算法流程

初始化: 将权重向量 $w$ 和偏置 $b$ 初始化为 0。
迭代训练:
- 循环进行 max_iter 次。
- 在每次循环中，遍历所有训练样本，累加梯度值。
- 根据上述公式计算完整的梯度，并更新 $w$ 和 $b$ 。
- 计算当前参数下的总损失 $J$ 。
- 检查是否满足停止条件：|当前损失 - 上次损失| < tol。如果满足，提前终止训练。
预测:
- 使用训练好的 $w$ 和 $b$ 。
- 对于每个测试样本，计算其预测概率 $p$ 。
- 根据 $p \ge 0.5$ 的规则判断预测标签。
- 格式化输出结果。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

double sigmoid(double z) {
    return 1.0 / (1.0 + exp(-z));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, max_iter;
    double alpha, lam, tol;
    cin >> n >> max_iter >> alpha >> lam >> tol;

    vector<vector<double>> X_train(n, vector<double>(3));
    vector<int> y_train(n);
    for (int i = 0; i < n; ++i) {
        cin >> X_train[i][0] >> X_train[i][1] >> X_train[i][2] >> y_train[i];
    }

    vector<double> w(3, 0.0);
    double b = 0.0;
    double prev_loss = 1e9;

    for (int iter = 0; iter < max_iter; ++iter) {
        vector<double> grad_w(3, 0.0);
        double grad_b = 0.0;
        double current_loss = 0.0;
        
        for (int i = 0; i < n; ++i) {
            double z = w[0] * X_train[i][0] + w[1] * X_train[i][1] + w[2] * X_train[i][2] + b;
            double p = sigmoid(z);
            double error = p - y_train[i];

            for (int j = 0; j < 3; ++j) {
                grad_w[j] += error * X_train[i][j];
            }
            grad_b += error;

            if (y_train[i] == 1) {
                current_loss -= log(p);
            } else {
                current_loss -= log(1 - p);
            }
        }

        current_loss /= n;
        double reg_term = 0.0;
        for (int j = 0; j < 3; ++j) {
            reg_term += w[j] * w[j];
        }
        current_loss += (lam / 2.0) * reg_term;

        if (abs(current_loss - prev_loss) < tol) {
            break;
        }
        prev_loss = current_loss;
        
        for (int j = 0; j < 3; ++j) {
            grad_w[j] = grad_w[j] / n + lam * w[j];
            w[j] -= alpha * grad_w[j];
        }
        grad_b /= n;
        b -= alpha * grad_b;
    }

    int m;
    cin >> m;
    cout << fixed << setprecision(4);
    for (int i = 0; i < m; ++i) {
        vector<double> x_test(3);
        cin >> x_test[0] >> x_test[1] >> x_test[2];
        double z = w[0] * x_test[0] + w[1] * x_test[1] + w[2] * x_test[2] + b;
        double prob = sigmoid(z);
        int pred = (prob >= 0.5) ? 1 : 0;
        cout << pred << " " << prob << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static double sigmoid(double z) {
        return 1.0 / (1.0 + Math.exp(-z));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int maxIter = sc.nextInt();
        double alpha = sc.nextDouble();
        double lam = sc.nextDouble();
        double tol = sc.nextDouble();

        double[][] xTrain = new double[n][3];
        int[] yTrain = new int[n];
        for (int i = 0; i < n; i++) {
            xTrain[i][0] = sc.nextDouble();
            xTrain[i][1] = sc.nextDouble();
            xTrain[i][2] = sc.nextDouble();
            yTrain[i] = sc.nextInt();
        }

        double[] w = {0.0, 0.0, 0.0};
        double b = 0.0;
        double prevLoss = Double.MAX_VALUE;

        for (int iter = 0; iter < maxIter; iter++) {
            double[] gradW = {0.0, 0.0, 0.0};
            double gradB = 0.0;
            double currentLoss = 0.0;

            for (int i = 0; i < n; i++) {
                double z = w[0] * xTrain[i][0] + w[1] * xTrain[i][1] + w[2] * xTrain[i][2] + b;
                double p = sigmoid(z);
                double error = p - yTrain[i];

                for (int j = 0; j < 3; j++) {
                    gradW[j] += error * xTrain[i][j];
                }
                gradB += error;

                if (yTrain[i] == 1) {
                    currentLoss -= Math.log(p);
                } else {
                    currentLoss -= Math.log(1 - p);
                }
            }
            
            currentLoss /= n;
            double regTerm = 0.0;
            for(int j = 0; j < 3; j++) {
                regTerm += w[j] * w[j];
            }
            currentLoss += (lam / 2.0) * regTerm;

            if (Math.abs(currentLoss - prevLoss) < tol) {
                break;
            }
            prevLoss = currentLoss;

            for (int j = 0; j < 3; j++) {
                gradW[j] = gradW[j] / n + lam * w[j];
                w[j] -= alpha * gradW[j];
            }
            gradB /= n;
            b -= alpha * gradB;
        }
        
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            double[] xTest = new double[3];
            xTest[0] = sc.nextDouble();
            xTest[1] = sc.nextDouble();
            xTest[2] = sc.nextDouble();
            
            double z = w[0] * xTest[0] + w[1] * xTest[1] + w[2] * xTest[2] + b;
            double prob = sigmoid(z);
            int pred = (prob >= 0.5) ? 1 : 0;
            System.out.printf("%d %.4f\n", pred, prob);
        }
    }
}

import math

def sigmoid(z):
    return 1.0 / (1.0 + math.exp(-z))

def solve():
    line1 = input().split()
    n = int(line1[0])
    max_iter = int(line1[1])
    alpha = float(line1[2])
    lam = float(line1[3])
    tol = float(line1[4])

    x_train = []
    y_train = []
    for _ in range(n):
        data = list(map(float, input().split()))
        x_train.append(data[:3])
        y_train.append(int(data[3]))

    w = [0.0, 0.0, 0.0]
    b = 0.0
    prev_loss = float('inf')

    for _ in range(max_iter):
        grad_w = [0.0, 0.0, 0.0]
        grad_b = 0.0
        current_loss = 0.0
        
        for i in range(n):
            z = sum(w[j] * x_train[i][j] for j in range(3)) + b
            p = sigmoid(z)
            error = p - y_train[i]

            for j in range(3):
                grad_w[j] += error * x_train[i][j]
            grad_b += error

            if y_train[i] == 1:
                current_loss -= math.log(p) if p > 0 else -1e9
            else:
                current_loss -= math.log(1 - p) if (1-p) > 0 else -1e9
        
        current_loss /= n
        reg_term = sum(wj * wj for wj in w)
        current_loss += (lam / 2.0) * reg_term
        
        if abs(current_loss - prev_loss) < tol:
            break
        prev_loss = current_loss

        for j in range(3):
            grad_w[j] = grad_w[j] / n + lam * w[j]
            w[j] -= alpha * grad_w[j]
        grad_b /= n
        b -= alpha * grad_b

    m = int(input())
    for _ in range(m):
        x_test = list(map(float, input().split()))
        z = sum(w[j] * x_test[j] for j in range(3)) + b
        prob = sigmoid(z)
        pred = 1 if prob >= 0.5 else 0
        print(f"{pred} {prob:.4f}")

solve()

算法及复杂度

算法: 机器学习, 逻辑回归, 批量梯度下降
时间复杂度: $O(\text{max\_iter} \cdot n \cdot f + m \cdot f)$
- $n$ : 训练样本数
- $m$ : 测试样本数
- $f$ : 特征数量 (本题中为 3)
- $\text{max\_iter}$ : 最大迭代次数
- 训练阶段：每次迭代都需要遍历所有 $n$ 个样本来计算梯度，每个样本涉及 $f$ 个特征的计算。
- 预测阶段：对 $m$ 个测试样本进行预测，每个样本涉及 $f$ 个特征。
空间复杂度: $O(n \cdot f + m \cdot f)$
- 主要用于存储训练集和测试集数据。模型的参数（ $w$ 和 $b$ ）只占用 $O(f)$ 的空间。

题解 | #二分类逻辑回归#