题解 | #二分类的意图判定#

题目链接

二分类的意图判定

题目描述

本题要求从零开始实现一个逻辑回归模型，用于二分类任务。输入是仅由大写字母 'A' 到 'G' 组成的字符串，输出是标签 0 或 1。

模型细节:

特征工程: 输入字符串需要被转换为 7 维的 One-Hot 编码向量。向量的维度顺序固定为 A, B, C, D, E, F, G。如果字符串中出现过某个字母，则该维度为 1，否则为 0。
模型结构: 单层逻辑回归。
- 权重 $w$ (7 维向量) 和偏置 $b$ (标量) 初始值均为 0。
- 激活函数为 Sigmoid: $p = \frac{1}{1 + e^{-z}}$ ，其中 $z = w \cdot x + b$ 。
训练过程:
- 损失函数: 二分类交叉熵。
- 优化器: 梯度下降。
- 学习率: 0.1。
- 训练轮数 (Epochs): 20。
- 批量大小 (Batch Size): 1 (即随机梯度下降 SGD)。
预测:
- 使用训练好的 $w$ 和 $b$ 进行计算。
- 预测概率 $p > 0.5$ 则判定为类别 1，否则为 0。

解题思路

这是一个标准的机器学习入门任务，需要我们手动实现整个流程，不能使用现成的库如 scikit-learn。

特征提取函数 (string_to_features)
- 创建一个函数，输入一个字符串，输出一个 7 维的 double 或 float 数组。
- 函数内部初始化一个全为 0 的 7 维数组 features。
- 遍历字符串中的每个字符，根据字符 ('A' 到 'G') 计算出它对应的索引 (0 到 6)，并将 features 数组中该索引位置的值设为 1。例如，'A' 对应索引 0，'B' 对应 1，以此类推。
Sigmoid 函数
- 实现 Sigmoid 函数 $\sigma(z) = \frac{1}{1 + e^{-z}}$ 。这个函数会将任意实数映射到 (0, 1) 区间，代表概率。
训练阶段
- 初始化一个 7 维的权重数组 $w$ 和一个偏置 $b$ ，全部设为 0。
- 进行 20 轮 (epoch) 的迭代。
- 在每一轮迭代中，遍历所有的 $N$ 个训练样本。对于每个样本 (字符串 s, 标签 y)：
  - 特征转换: 调用 string_to_features 将 s 转换为特征向量 $x$ 。
  - 前向传播:
    - 计算线性组合 $z = \sum_{i=0}^{6} w_i \cdot x_i + b$ 。
    - 通过 Sigmoid 函数计算预测概率 $p = \sigma(z)$ 。
  - 梯度计算: 对于二分类交叉熵损失，梯度有一个简洁的形式： $grad_z = p - y$ 。
  - 参数更新: 根据梯度下降法更新权重和偏置。
    - 对每个权重 $w_i$ ： $w_i = w_i - \text{learning_rate} \cdot grad_z \cdot x_i$ 。
    - 对偏置 $b$ ： $b = b - \text{learning_rate} \cdot grad_z$ 。
预测阶段
- 遍历 $M$ 个测试样本。对于每个测试字符串 s_test:
  - 将其转换为特征向量 $x_{test}$ 。
  - 使用训练好的 $w$ 和 $b$ 计算 $z_{test} = w \cdot x_{test} + b$ 。
  - 计算预测概率 $p_{test} = \sigma(z_{test})$ 。
  - 根据阈值 0.5 判断最终类别：如果 $p_{test} > 0.5$ ，输出 1；否则输出 0。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>

using namespace std;

// 特征提取函数
vector<double> string_to_features(const string& s) {
    vector<double> features(7, 0.0);
    for (char c : s) {
        if (c >= 'A' && c <= 'G') {
            features[c - 'A'] = 1.0;
        }
    }
    return features;
}

// Sigmoid 激活函数
double sigmoid(double z) {
    return 1.0 / (1.0 + exp(-z));
}

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

    int n, m;
    cin >> n >> m;

    vector<pair<string, int>> train_data(n);
    for (int i = 0; i < n; ++i) {
        cin >> train_data[i].first >> train_data[i].second;
    }

    vector<string> test_data(m);
    for (int i = 0; i < m; ++i) {
        cin >> test_data[i];
    }

    // 初始化模型参数
    vector<double> w(7, 0.0);
    double b = 0.0;
    double learning_rate = 0.1;
    int epochs = 20;

    // 训练模型
    for (int epoch = 0; epoch < epochs; ++epoch) {
        for (const auto& sample : train_data) {
            vector<double> x = string_to_features(sample.first);
            int y = sample.second;

            double z = 0.0;
            for(int i = 0; i < 7; ++i) {
                z += w[i] * x[i];
            }
            z += b;

            double p = sigmoid(z);
            double grad_z = p - y;

            for (int i = 0; i < 7; ++i) {
                w[i] -= learning_rate * grad_z * x[i];
            }
            b -= learning_rate * grad_z;
        }
    }

    // 预测
    for (const auto& s : test_data) {
        vector<double> x_test = string_to_features(s);
        double z_test = 0.0;
        for(int i = 0; i < 7; ++i) {
            z_test += w[i] * x_test[i];
        }
        z_test += b;

        double p_test = sigmoid(z_test);
        cout << (p_test > 0.5 ? 1 : 0) << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.lang.Math;

public class Main {

    // 特征提取函数
    private static double[] stringToFeatures(String s) {
        double[] features = new double[7];
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'G') {
                features[c - 'A'] = 1.0;
            }
        }
        return features;
    }

    // Sigmoid 激活函数
    private 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 m = sc.nextInt();

        List<String> trainStrings = new ArrayList<>();
        List<Integer> trainLabels = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            trainStrings.add(sc.next());
            trainLabels.add(sc.nextInt());
        }

        List<String> testStrings = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            testStrings.add(sc.next());
        }

        // 初始化模型参数
        double[] w = new double[7]; // 默认初始化为 0.0
        double b = 0.0;
        double learningRate = 0.1;
        int epochs = 20;

        // 训练模型
        for (int epoch = 0; epoch < epochs; epoch++) {
            for (int i = 0; i < n; i++) {
                double[] x = stringToFeatures(trainStrings.get(i));
                int y = trainLabels.get(i);

                double z = 0.0;
                for (int j = 0; j < 7; j++) {
                    z += w[j] * x[j];
                }
                z += b;

                double p = sigmoid(z);
                double gradZ = p - y;

                for (int j = 0; j < 7; j++) {
                    w[j] -= learningRate * gradZ * x[j];
                }
                b -= learningRate * gradZ;
            }
        }

        // 预测
        for (String s : testStrings) {
            double[] xTest = stringToFeatures(s);
            double zTest = 0.0;
            for (int i = 0; i < 7; i++) {
                zTest += w[i] * xTest[i];
            }
            zTest += b;

            double pTest = sigmoid(zTest);
            System.out.println(pTest > 0.5 ? 1 : 0);
        }
    }
}

import math

# 特征提取函数
def string_to_features(s):
    features = [0.0] * 7
    for char in s:
        if 'A' <= char <= 'G':
            features[ord(char) - ord('A')] = 1.0
    return features

# Sigmoid 激活函数
def sigmoid(z):
    return 1.0 / (1.0 + math.exp(-z))

def main():
    n, m = map(int, input().split())
    
    train_data = []
    for _ in range(n):
        line = input().split()
        train_data.append((line[0], int(line[1])))
        
    test_data = [input() for _ in range(m)]

    # 初始化模型参数
    w = [0.0] * 7
    b = 0.0
    learning_rate = 0.1
    epochs = 20

    # 训练模型
    for _ in range(epochs):
        for s, y in train_data:
            x = string_to_features(s)
            
            z = sum(wi * xi for wi, xi in zip(w, x)) + b
            p = sigmoid(z)
            
            grad_z = p - y
            
            w = [wi - learning_rate * grad_z * xi for wi, xi in zip(w, x)]
            b -= learning_rate * grad_z

    # 预测
    for s_test in test_data:
        x_test = string_to_features(s_test)
        z_test = sum(wi * xi for wi, xi in zip(w, x_test)) + b
        p_test = sigmoid(z_test)
        print(1 if p_test > 0.5 else 0)

if __name__ == "__main__":
    main()

算法及复杂度

算法：机器学习、逻辑回归、梯度下降
时间复杂度： $O(E \cdot N \cdot D + M \cdot D)$ ，其中 $E$ 是训练轮数 (20)， $N$ 是训练样本数， $M$ 是测试样本数， $D$ 是特征维度 (7)。由于 $E$ 和 $D$ 都是常数，复杂度可简化为 $\mathcal{O}(N + M)$ 。
空间复杂度： $O(N \cdot D + M \cdot |S_{max}|)$ ，其中 $|S_{max}|$ 是最长字符串的长度。主要用于存储训练和测试数据。由于 $D$ 是常数，复杂度可简化为 $\mathcal{O}(N + M \cdot |S_{max}|)$ 。