求解大规模矛盾方程组的最小二乘支持向量机算法

doi:10.3785/j.issn.1008-9497.2022.04.007

求解大规模矛盾方程组的最小二乘支持向量机算法

郑素佩^,^,, 闫佳^,^,, 宋学力, 陈荧

长安大学理学院，陕西西安 710064

A least square support vector machine algorithm for solving huge contradictory equations

ZHENG Supei^,^,, YAN Jia^,^,, SONG Xueli, CHEN Ying

School of Science，Chang'an University，Xi'an 710064，China

通讯作者: ORCID：https：//orcid.org/0000-0002-6814-0419，E-mail：yj_yan_jia@163.com.

收稿日期: 2021-07-29

基金资助:

国家自然科学基金资助项目. 11971075
陕西省自然科学基金青年项目. 2020JQ-338. 2020JQ-342

Received: 2021-07-29

作者简介 About authors

郑素佩（1978—），ORCID：https：//orcid.org/0000-0003-2502-6998，女，博士，副教授，主要从事微分方程数值解法研究，E-mail：zsp2008@chd.edu.cn. , E-mail：zsp2008@chd.edu.cn

摘要

房价预测、共享单车出租数量预测、空气污染情况预测等常涉及矛盾方程组求解，对其数值求解方法研究具有重要的理论意义与应用价值。当矛盾方程组规模过大时，用传统的最小二乘法求解，不仅计算量大，而且由于误差积累使最终结果的准确性不高。鉴于此，采用机器学习中的最小二乘支持向量机（least squares support vector machine，LS-SVM）算法求解大规模矛盾方程组，并分别针对线性、非线性、单变量、多变量矛盾方程组进行了数值求解。数值结果表明，数据类型和数据量的变化对结果的影响不大，因此只要选取适当的参数就可建立合适的模型，得到高精度的预测结果。

关键词： 大规模矛盾方程组 ; 机器学习 ; LS-SVM ; 最小二乘法

Abstract

Contradictory equations often appear in the predictions of housing price, the number of shared bike rentals, air pollution and other problems. It is of important theoretical significance and practical application value to conduct research on the related numerical method. When the number of contradictory equations is huge, it is too difficult to use the traditional least square method to solve the problem due to the accumulation of errors. In view of this, this paper adopts the least square support vector machine (LS-SVM) algorithm, which is suitable for machine learning of big data process, to solve the huge contradictory equations, and applies the algorithm to problems with practical application background. Experimental results show that the linear, nonlinear, univariate and multivariable contradictory equations can be solved numerically, the change of data type and data volume does not affect the results much, and the appropriate model can be built to obtain high accuracy results as long as the appropriate parameters are selected.

Keywords： huge contradictory equations ; machine learning ; LS-SVM ; least square method

PDF (2943KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

郑素佩, 闫佳, 宋学力, 陈荧. 求解大规模矛盾方程组的最小二乘支持向量机算法. 浙江大学学报(理学版)[J], 2022, 49(4): 435-442 doi:10.3785/j.issn.1008-9497.2022.04.007

ZHENG Supei, YAN Jia, SONG Xueli, CHEN Ying. A least square support vector machine algorithm for solving huge contradictory equations. Journal of Zhejiang University(Science Edition)[J], 2022, 49(4): 435-442 doi:10.3785/j.issn.1008-9497.2022.04.007

0　引言

在求解范围内无解（解为空集）的方程组称为该范围内的矛盾方程组。矛盾方程组在实际生活中应用广泛，通常采用最小二乘法求解，其基本思想是寻找一组解 $\tilde{x}$ ，使得方程组两端的偏差向量的2-范数平方最小。近年来，基于最小二乘法的新算法不断涌现，如JIANG^［1］系统阐述了最小二乘有限元法；李玉良等^［2］依据圣维南原理，提出了基于最小二乘法的复杂局部边界结构载荷误差消减算法。

随着信息技术的发展，实际遇到的矛盾方程组规模都较大。当方程组规模过大时，用传统的最小二乘法求解，计算、存储均较复杂，且误差较大，需要寻找更好的算法。例如，将最小二乘与随机算法相结合^［3］，运用机器学习改进最小二乘法的计算精度^［4］等。

机器学习是一门多领域交叉学科，以计算机为工具模拟人类的学习方式，适用于大规模数据处理，可很好地解决非线性问题。其中支持向量机（support vector machine，SVM）^［5-6］因具有出色的泛化能力和较强的样本适应能力应用广泛。SUYKENS等^［7］从机器学习的损失函数入手提出的最小二乘支持向量机（least squares support vector machine，LS-SVM）算法，求解精度大幅提高，并不断被用于解决实际问题。例如徐锋等^［8］提出了基于LS-SVM积分型辨识样本结构的船舶操纵运动的在线建模。SHARMA等^［9］为提高工程造价预测的准确性，提出了基于LS-SVM的工程造价预测模型，该模型预测精度高，结果稳定，相对误差在7%内。赵庆志等^［10］应用LS-SVM实现了对未来降雨的预测，可准确预测99%的降雨事件。鲜有报道涉及基于LS-SVM算法求解具有实际背景的大规模矛盾方程组的研究。鉴于此，本文采用LS-SVM算法对大规模矛盾方程组进行数值求解，给出求解过程，将其应用于若干具体算例，并对结果进行分析和比较。

1　矛盾方程组的最小二乘解

对于方程组：

\{\begin{array}{l} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = y_{1} ， \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = y_{2} ， \\ \dots \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} = y_{m} ， \end{array}

（1）

其中， $m ≫ n$ 。其矩阵形式为

[\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a {}_{m 2} & \dots & a_{m n} \end{matrix}] [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}] = [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}] ，

（2）

令 $A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a {}_{m 2} & \dots & a_{m n} \end{matrix}]$ ， $x = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}]$ ， $y = [\begin{matrix} y_{1} \\ y_{2} \\ ⋮ \\ y_{m} \end{matrix}]$ ， $a_{i j} = a_{i j} (x)$ ，则式（2）可简写为 $A x = y$ 。

通常，若没有任何一组解使得式（1）准确成立，则称该方程组为矛盾方程组。希望可以找到一组数 $\tilde{x} = (x_{1}, x_{2}, \dots, x_{n})^{T}$ ，使方程组两端的偏差向量 $(δ_{1}, δ_{2}, \dots, δ_{m})^{T}$ $(δ_{i} = \sum_{j = 1}^{m} a_{i j} x_{j} - y_{i})$ 的2-范数平方最小。这种以偏差平方和最小为求解标准的方法，称为最小二乘法^［11-12］。

具体地，令

$Q (x_{1}, x_{2}, \dots, x_{n}) = \sum_{i = 1}^{m} δ_{i}^{2} = {\sum_{i = 1}^{m} (\sum_{j = 1}^{n} a_{i j} x_{j} - y_{i})}^{2}$ ，一般采用多元函数求极值的方法得到对应的法方程组（正规方程组），王萼芳等^［13］基于内积理论对法方程组解的存在性问题进行了讨论。令

\begin{array}{l} \frac{\partial Q}{\partial x_{k}} = \sum_{i = 1}^{m} (\sum_{k = 1}^{n} a_{i k} x_{k} - y_{i}) a_{i j} = \\ 2 (a_{1 k}, a_{2 k}, \dots, a_{m k}) (A x - y) = \\ 2 A^{T} (A x - y) = 0 ， k = 1,2, \dots, n, \end{array}

（3）

找到极值点，则有 $A^{T} A x = A^{T} y$ 。如果矩阵 $A$ 为列满秩矩阵，则法方程组的解存在且唯一。

2　机器学习法求解矛盾方程组

将最小二乘法运用于SVM，在优化问题的目标函数中使用2-范数，用等式约束条件代替SVM标准算法中的不等式约束条件，得到LS-SVM^［7］。SVM与LS-SVM的区别主要表现在：

（1）优化问题的构造不同，SVM采用的目标函数为误差因子的一次项，约束条件为不等式约束；LS-SVM具有最小二乘的性质，采用的目标函数为平方项，约束条件为等式约束。

（2）在求解二次规划（quadratic programming，QP）问题时，SVM的变量维数与训练样本的个数相同，求解过程中矩阵元素的个数是训练样本个数的平方，当数据规模较大时，SVM的求解规模也随之增大；LS-SVM则通过求解线性方程组得到最终的决策函数，在一定程度上求解难度较SVM大大降低，求解速度更快，适用于求解大规模问题。

（3）SVM可通过求解QP问题获得理论上的全局最优解，因为大部分的Lagrange乘子为零，最终的决策函数只能依赖于少量数据，即支持向量，从而体现了SVM中解的稀疏性特点。LS-SVM采用误差平方项以及等式约束条件来优化问题，将SVM中的QP问题转化为求解线性方程组，使得Lagrange乘子与误差项相关，其最终决策函数与所有样本相关。

因此，LS-SVM在计算时间、计算复杂度和精确度上均优于SVM。鉴于此，本文运用LS-SVM求解大规模矛盾方程组。

2.1　LS-SVM

令数据集 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{m}, y_{m})}$ ， $x_{i} \in R^{n}$ 为样本解向量， $y_{i} \in R$ 为方程组右端项，其中 $i = 1,2, \dots, m$ 。可将式（2）的最小二乘求解问题转化为关于数据集 $D$ 的优化问题，目标函数为

\underset{ω, ε}{m i n} J (ω, ε) = \frac{1}{2} | | ω | |^{2} + \frac{1}{2} γ \sum_{i = 1}^{m} ε_{i}^{2}

，（4）

其中， $ω, ε$ 为参数， $γ$ 为正则化参数， $ε_{i} = f (x_{i}) - y_{i}, i = 1,2, \dots, m$ 。假设采用Lagrange乘子法将优化问题转化为对单一参数 $α$ 的求极值问题，

\begin{array}{l} L （ ω, b, ε; α ） = J （ ω, ε ） - \\ \sum_{i = 1}^{m} α_{i} {ω^{T} x_{i} + b + ε_{i} - y_{i}} ， \end{array}

（5）

寻找极值点（令偏导为零）：

\{\begin{array}{l} \frac{\partial L}{\partial ω} = 0 \to ω = \sum_{i = 1}^{m} α_{i} x_{i} ， \\ \frac{\partial L}{\partial b} = 0 \to \sum_{i = 1}^{m} α_{i} = 0 ， \\ \frac{\partial L}{\partial ε_{i}} = 0 \to α_{i} = γ ε_{i} ， \\ \frac{\partial L}{\partial α_{i}} = 0 \to ω^{T} \tilde{x} + b + ε_{i} - y_{i} = 0, \end{array}

（6）

其中， $i = 1,2 ， \dots, m 。$ 记为线性方程组：

[\begin{matrix} 0 & 1_{v}^{T} \\ 1_{v} & x_{i}^{T} \tilde{x} + I / γ \end{matrix}] [\begin{matrix} b \\ α \end{matrix}] = [\begin{matrix} 0 \\ y \end{matrix}]

，（7）

其中，b为参数。求解式（6）可得LS-SVM线性回归函数：

f (x) = \sum_{i = 1}^{m} α_{i} x_{i}^{T} \tilde{x} + b

。（8）

针对非线性问题，可引入核函数，用核函数代替线性方程组中的线性项，将原线性算法“非线性化”，即非线性回归。若 $φ (\tilde{x})$ 表示将 $\tilde{x}$ 映射后的特征向量，则最终的LS-SVM非线性回归函数为

f (\tilde{x}) = \sum_{i = 1}^{m} α_{i} K （ \tilde{x}, x_{i} ） + b ，

（9）

其中，核函数的表达式为

K （ \tilde{x}, x_{i} ） = φ （ x_{i} ）^{T} φ （ \tilde{x} ）, i = 1,2 ， \dots, m

。（10）

常用的核函数主要有线性核函数、多项式核函数、高斯核函数等^［14］，本文采用目前较常用的高斯核函数^［15］。高斯核函数是一种径向基函数（radial basis function，RBF），是沿径向对称的标量函数，定义为空间中任一点 $x$ 与某一中心 $x_{c}$ 之间欧氏距离的单调函数，其作用往往是局部的，即当 $x$ 远离 $x_{c}$ 时函数值很小。高斯核函数的表达式为

K (x, x_{c}) = e x p^{- | | x - x_{c} | |_{2}^{2} / 2 σ^{2}}

，（11）

其中， $K$ 为核， $x_{c}$ 为核函数中心， $σ$ 为函数的宽度参数，用以控制函数的径向作用范围。高斯核函数的正则化项^［16］为

| | P f | |^{2} = \int \sum_{n} \frac{σ^{2 n}}{n! 2^{n}} [O^{n} f {(x)]}^{2} d x

，（12）

其中， $O^{2 n} = Δ^{n}$ ， $O^{2 n + 1} = \nabla Δ^{n}$ ， $Δ$ 为拉普拉斯算子， $\nabla$ 为梯度算子。

由于式（12）中函数 $f$ 的所有阶导数均增加了惩罚因子，所以对SVM采用RBF可获得一个非常平滑的估计。同时由于 $K$ 的范围为 $(0, 1)$ ，因此计算过程相对简单。

2.2　算法步骤

第1步　将矛盾方程组求解问题转化为凸优化问题，建立优化目标函数；

第2步　构建Lagrange函数，利用Lagrange乘子法将优化问题转化为对单一参数 $α$ 的求极值问题；

第3步　将求极值问题转化为求线性方程组；

第4步　将解代入原始模型即为训练所得线性模型；用 $φ （ x ）$ 表示将 $x$ 映射后的特征向量，得到相应的最终LS-SVM非线性回归函数；

第5步　将数据代入模型，得到实验结果，即最终预测值。

3　数值算例

实际问题包括单变量问题和多变量问题，数据一般分为线性和非线性两大类，运用LS-SVM进行算例分析，数据量为1 000~7 000，以验证算法性能。算例1~算例3中数据是通过随机取样方法产生10^-3~10^-2的振幅，将原函数值加上或减去该振幅得到的。算例4~算例8中数据集均来自加州大学欧文分校机器学习数据库（UCI Machine Learning Repository，http：//archive.ics.uci.edu/ml/index.pdf）。

为便于对比，所有数值算例结果均显示部分数据，且分为上、下两图，上图为训练集预测结果，下图为测试集预测结果，图中纵坐标Y_t 表示最终预测值。训练集主要用于训练模型，测试集主要用于测试模型的优劣。

3.1　单变量线性矛盾方程组求解

算例1　函数 $y = \frac{x}{5} - 600$ 上下扰动所得数据为 $y^{*}$ 。

该算例属于一元线性问题，共5 000组数据，随机选取3 500组为训练集，剩余1 500组为测试集，进行两组实验，实验1和实验2的测试集分别为 $(x_{i}, y_{i}^{*}),$ $(x_{i}, x_{i} / 5 - 600)$ ， $i = 1,2, \dots, 1 500$ 。如图1所示，在实验1中， $R^{2}$ 达0.962，在实验2中， $R^{2}$ 达0.999，拟合效果非常好。结果表明，在大数据量的情况下，拟合度依然较高。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 算例1数值结果

实验1的核函数参数为 $γ = 17, σ = 2$ ；实验2的核函数参数为 $γ$ =40， $σ$ =2。

Fig.1 Numerical results of example 1

Parameters in the kernel function of experiment 1 are $γ = 17, σ = 2$ ；

parameters in the kernel function of experiment 2 are $γ$ =40， $σ$ =2.

3.2　多变量线性矛盾方程组求解

算例2　函数 $y = 3 | x_{1} | - 2 | x_{2} | + 3 x_{3}$ 上下扰动所得数据为 $y^{*}$ 。

该算例属于三元线性问题，共5 000组数据，随机选取4 000组为训练集，剩余1 000组为测试集。如图2所示，两次实验的 $R^{2}$ 均为0.990以上，拟合效果非常好。结果表明，大数据量并不影响多元线性问题的拟合效果，可以很好地对原函数进行近似。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 算例2数值结果

实验1和实验2的核函数参数均为 $γ = 20, σ = 2$ 。

Fig.2 Numerical results of example 2

Parameters in kernel function of experiment 1 and experiment 2 are $γ$ =20， $σ$ =2.

3.3　单变量非线性矛盾方程组求解

算例3　函数 $y = 10 s i n (x)$ 上下扰动后所得数据为 $y^{*}$ 。

该算例属于一元三角函数拟合问题，共6 000组数据，随机选取4 500组为训练集，剩余1 500组为测试集，满足LS-SVM对训练集和测试集的要求。实验1的测试集真实值为 y^*，实验2的测试集真实值为 $y$ ，预测结果如图3所示。可知，实验1的 $R^{2} = 0.837$ ，表明三角函数具有较好的拟合效果。实验2的 $R^{2} = 0.845$ ，表明 $y$ 具有较好的拟合效果。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 算例3数值结果

实验1的核函数参数为 $γ = 10, σ = 1.47 \times 10^{- 7}$ ；实验2的核函数参数为 $γ = 10, σ = 1 \times 10^{- 7}$

Fig.3 Numerical results of example 3

Parameters in the kernel function of experiment 1 are $γ = 10, σ = 1.47 \times 10^{- 7}$ ；

parameters in the kernel function of experiment 2 are $γ = 10, σ = 1 \times 10^{- 7}$ .

3.4　多变量非线性矛盾方程组求解

算例4　Airfoil_self_noise数据集预测。

该数据集来自美国航空航天局（NASA）在消声风洞中进行的二维和三维翼型叶片剖面的一系列空气动力学和声学试验。其中，机翼的跨度、观察者的位置不变。共1 503组数据，5个属性值，随机选取1 150组为训练集，其余353组为测试集。预测结果如图4所示，经过多次实验，最佳 $R^{2} = 0.889$ ，拟合效果较好，本算例数据量较小，实验结果较好，可以采用该模型进行数据预测。

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 算例4数值结果

核函数参数为 $γ = 150, σ = 0.1$ 。

Fig. 4 Numerical results of example 4

Parameters in the kernel function are $γ = 150, σ = 0.1$ .

算例5　gt_2011数据集预测。

该数据集包含由11个传感器测量的36 733个实例，是土耳其西北部地区燃气轮机1 h内的数据汇总（平均值或总和），目的是研究烟气排放，即一氧化碳和氮氧化物。本实验仅选取2011年的数据，共7 411组，输出值为一氧化碳排放量。随机选取6 000组为训练集，其余1 411组为测试集。预测结果如图5所示， $R^{2} = 0.909$ ，拟合效果较好，可以根据此模型预测气体排放量。该算例的数据量较算例4大幅增加，有7 000多组数据，但预测结果并未变差。

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 算例5数值结果

核函数参数为 $γ = 1 800, σ = 30$ 。

Fig.5 Numerical results of example 5

Parameters in the kernel function are $γ = 1 800, σ = 30$ .

算例6　parkinsons_updrs数据集预测

该数据集为由Athanasios Tsanas创建、Max Little与美国10个医疗中心、英特尔公司合作开发的远程监控设备所记录的语音信号。最初使用一系列线性和非线性回归方法预测临床医生在UPDRS量表上的帕金森病症状评分。共5 875组数据，26个属性值，随机选取4 000组作为训练集，其余1 875组作为测试集。预测结果如图6所示， $R^{2} = 0.983$ ，非常接近于1，实验结果表明，属性值的增多并不会改变拟合效果。

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 算例6数值结果

核函数参数为 $γ = 1 500, σ = 13$ 。

Fig. 6 Numerical results of example 6

Parameters in the kernel function are $γ = 1 500, σ = 13$ .

算例7　SeoulBikeData数据集预测

目前，许多城市引入了共享单车，以提高出行的便捷性。能在合适的时间租到自行车，可减少公众的等待时间。此问题的关键是预测每小时所需的共享单车数。

数据集包含天气（温度、湿度、风速、能见度、露点、太阳辐射、降雪量、降雨量）、每小时共享单车租用数和日期等信息。共8 700组数据，包含14个属性值。随机选取6 000组作为训练集，其余2 700组作为测试集。预测结果如图7所示， $R^{2} = 0.860$ ，拟合效果较好。结果表明，大规模数据具有较好拟合效果。

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 算例7数值结果

核函数参数为 $γ = 200, σ = 25$ 。

Fig. 7 Numerical results of example 7

Parameters in the kernel function are $γ = 200, σ = 25$ .

算例8　kc_train数据集预测

数据集主要包括2014年5月至2015年5月美国King County的房屋销售价格以及房屋的基本信息。数据分为训练数据和测试数据两部分，分别保存在kc_train.csv和kc_test.csv两个文件中。其中训练数据主要包括10 000条记录，14个字段，随机选取8 000条作为训练集，其余2 000条作为测试集。预测结果如图8所示， $R^{2} = 0.790$ ，非常接近0.8，拟合效果良好，可用于预测房价，结果再次表明，当数据量达到10 000时拟合效果仍良好。

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8 算例8数值结果

核函数参数为 $γ = 190, σ = 20$ 。

Fig. 8 Numerical results of example 8

Parameters in the kernel function are $γ = 190, σ = 20$ .

4　结论

研究了如何用LS-SVM求解大规模矛盾方程组，并将其用于预测实际问题。在实验过程中不断修正参数值，使得训练模型更符合实际情况。通过对线性单变量和多变量问题、非线性单变量和多变量问题的研究，得到以下结论：

（1）数据类型，如线性与非线性、一元与多元并不影响数据的拟合度，对于不同类型的数据，只要找到适当的参数值，就可以得到具有良好效果的拟合模型，进行数据预测。

（2）从预测结果看，数据量的增多并不影响数据的拟合效果。

http://dx.doi.org/10.3785/j.issn.1008-9497.2022.04.007

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

JIANG

B N

. The Least-Squares Finite Element Method［M］. Berlin/Heidelberg：Springer-Verlag Press， 1998. doi:10.1007/978-3-662-03740-9_8