lbbsvm

lbbsvm 是一个使用 C++ 实现的轻量级 SVM 支持向量机项目，并通过 pybind11 提供 Python 接口。

这个分支主要实现了二分类 SVM 和一对一多分类 SVM，支持 linear kernel、RBF kernel 和 sparse-list linear kernel。相比普通的简单实现，代码中加入了 kernel cache、AVX2 点积加速、OpenMP 并行计算，以及适合 one-vs-one 训练过程的缓存复用逻辑。

主要特点

• C++ 实现 SVM 训练和预测

• 通过 pybind11 提供 Python 接口

• 支持二分类模型 SVC

• 支持一对一多分类模型 OneVsOneSVC

• 支持三种 kernel：

  • linear
  • rbf
  • listlinear

• 使用 AVX2 加速 dense vector dot product

• 使用 OpenMP 对部分大规模循环进行并行化

• 使用 LRU cache 缓存 kernel row

• 在 LRUCache 内部直接维护 LRU 双向链表

• 支持 reset 和 sub_reset，便于 one-vs-one 多分类训练时复用部分缓存

项目结构

lbbsvm/
├── include/
│   ├── common.h
│   ├── lrucache.h
│   ├── model.h
│   ├── qmatrix.h
│   └── solver.h
├── src/
│   ├── lrucache.cpp
│   ├── model.cpp
│   ├── qmatrix.cpp
│   └── solver.cpp
├── src_python/
│   └── bind.cpp
├── setup.py
└── README.md

安装

git clone https://github.com/luboyang-a/lbbsvm.git
cd lbbsvm
git checkout master

安装依赖：

python -m pip install --upgrade pip setuptools wheel
python -m pip install numpy pybind11

编译并安装：

python -m pip install .

安装完成后可以导入：

import lbbsvm

快速使用

二分类

SVC 用于二分类任务，标签应使用 -1 和 1。

import numpy as np
import lbbsvm

X = np.array([
    [0.0, 0.0],
    [0.2, 0.1],
    [1.0, 1.0],
    [1.2, 1.1],
], dtype=np.float64)

y = np.array([-1, -1, 1, 1], dtype=np.int32)

clf = lbbsvm.SVC(
    X=X,
    y=y,
    dim=X.shape[1],
    C=1.0,
    eps=1e-3,
    kernel="linear",
    sigma=1.0
)

clf.fit(max_iter=50000)

pred = clf.predict(X)
print(pred)

多分类

OneVsOneSVC 用于多分类任务，标签应是从 0 开始的连续整数。

import numpy as np
import lbbsvm

X = np.array([
    [0.0, 0.0],
    [0.1, 0.2],
    [1.0, 1.0],
    [1.1, 1.2],
    [3.0, 3.0],
    [3.2, 3.1],
], dtype=np.float64)

y = np.array([0, 0, 1, 1, 2, 2], dtype=np.int32)

clf = lbbsvm.OneVsOneSVC(
    X=X,
    y=y,
    dim=X.shape[1],
    C=1.0,
    eps=1e-3,
    kernel="rbf",
    sigma=1.0
)

clf.fit(max_iter=50000)

pred = clf.predict(X)
print(pred)

Kernel 说明

linear

线性核：

K(x, y) = x · y

rbf

RBF 核：

K(x, y) = exp(-||x - y||² / (2 * sigma²))

listlinear

listlinear 会把输入向量转换成 sparse-list 形式，只遍历非零特征进行线性核计算。

当数据中有大量接近 0 的特征时，listlinear 可以减少部分无效计算。

数据格式要求

建议传入连续内存的 NumPy 数组：

X = np.ascontiguousarray(X, dtype=np.float64)
y = np.ascontiguousarray(y, dtype=np.int32)

二分类时：

y ∈ {-1, 1}

多分类时：

y ∈ {0, 1, 2, ..., num_classes - 1}

实现说明

代码主要由以下部分组成：

• QMatrix：kernel 计算抽象接口
• VectorLinear：dense linear kernel
• VectorRbf：dense RBF kernel
• ListLinear：sparse-list linear kernel
• LRUCache：kernel row 缓存
• Solver：SMO 风格的优化求解器
• SVC：二分类 SVM
• OneVsOneSVC：一对一多分类 SVM

这个分支的 LRUCache 把 LRU 节点结构直接放在类内部，通过 lru_head、lru_free、Map 和 pool 管理缓存行。 在 one-vs-one 多分类训练中，reset 和 sub_reset 可以配合类别子集训练，减少完全重建缓存的开销。

编译说明

默认编译会启用 C++14、AVX2、FMA 和 OpenMP。

Linux 下主要使用：

-O3
-std=c++14
-fPIC
-march=native
-mavx2
-mfma
-fopenmp

Windows 下主要使用：

/O2
/std:c++14
/arch:AVX2
/openmp

如果机器不支持 AVX2，需要修改 setup.py 中的编译参数。