回归算法

回归算法（精选7篇）

回归算法 篇1

摘要：本文基于张量CP (CANDECOMP/PARAFAC) 分解提出了秩优化的张量岭回归模型。通过模型中引入结构性稀疏项L (2, 1) -范数, 可以在模型参数训练过程中自动选择CP分解的秩, 得到准确的张量分解形式。为了验证本文算法的有效性, 在2个多媒体数据集上进行实验。实验结果表明本文的算法与对应的向量算法相比, 取得了更准确的分类结果。

关键词：张量,CP (CANDECOMP/PARAFAC) 分解,L (2, 1) -范数

1 引言

目前, 很多基于向量的分类方法被提出, 比如:K最近邻 (K-Nearest Neighbor, KNN) 分类算法, 岭回归 (Ridge Regression, RR) 分类算法等。由于这些基于向量的分类算法具有简单有效的归纳特性, 因此被广泛的用来处理多媒体分类的问题。但是这些方法需要按照一个指定的排列规则, 把张量多媒体数据或多媒体特征简单的排列成一个高维向量。这样做不仅会破坏多媒体的空间结构, 也会导致高维向量的产生。

如何构建有效的张量学习算法成为多媒体分类的重要研究内容。本文在CP分解后, 通过定义因子矩阵转置后的L (2, 1) - 范数, 得到因子矩阵的列稀疏结构, 由于因子矩阵的列数目与张量的秩是相等的, 通过删除因子矩阵中的稀疏列可以实现张量秩的自动选择。本文提出的算法是对向量岭回归的张量扩张, 因此称为秩优化的张量岭回归回归模型 (Rank optimization for Ten sor Ridge Regression, RoTRR) 。

2 秩选择的张量岭回归算法

每一个多媒体数据可以表示为一个N阶张量, 第i阶的维度为di。多媒体数据对应的分类标签为。因此M个多媒体数据可以表示成张量数据集。可对传统岭回归进行张量扩展得到:

其中为模型的张量权值参数, 为F范数作为正则化项防止过拟合, λ为正则化项系数。

对式 (1) 的张量参数w进行CP分解, 可以得到N个因子矩阵{Ui}Ni1。每一个因子矩阵的列数是相同的, 而且与初始假定的张量秩相等。由于初始的张量秩R是较大的, 因此CP分解后的结果包含大量的噪声或者冗余信息。首先定义一个组合因子矩阵U [U1;U2;...;UN]  [u1, u2, ..., uR]。 U的列数与张量的秩是相等的, 值得注意的是U的每一列对应的是一个秩-1 张量的所有因子向量, 如果某一列出现稀疏也就意味着这一列对应的秩-1 张量是冗余或者噪声信息, 应该删除掉, 反之, 应该保留。通过这种方式, 我们可以最终获得包含主要判别信息的秩-1 张量。最终剩下的秩-1张量数目, 即U的列数就是张量的秩。这样通过训练学习可以自动获得CP分解后张量的秩, 解决了张量秩不唯一的问题。Tan提出采用l1范数作为正则化项, 可以获得张量分解后的稀疏结构, 但是并不能在列方向上产生结构化的稀疏结果, 这样就不能自动的选择张量的秩。Han指出, 采用l2, 1范数可以在矩阵中产生行方向的稀疏。因此我们采用U转置的l2, 1范数作为正则化项, 可以达到秩选择的目的。综上所述, 我们可以得到:

因为式 (2) 中有N个参数需要进行训练估计, 式 (2) 对N个参数不是联合凸函数, 但是当固定其他参数, 式 (2) 对任意一个参数是凸函数, 所以我们采用交叉优化的方法对式 (2) 进行优化。

3 实验结果及分析

本文在两个2 阶图像数据集 (binary alpha digits (BAd) , USPS) 构造实验。实验中每一幅灰度图的大小被定义为12×12个像素。为了估计算法在少数训练数据的性能, 每一类随机选取1 一个图像作为训练数据, 其他图像作为测试数据。随机测试5 次, 以5 次的平均值作为最终结果。

实验的对比算法为:KNN算法, 岭回归 (RR) 算法。所有类的平均准确率 (Average accuracy) 作为评价法则评估算法的分类效果。算法RoTRR与RR参数调试范围为{106, 105, ..., 105, 106}, 每一个算法的最优的结果作为该算法的最终结果。算法KNN的参数k设置为10。

3.1 实验数据集

本文提出的算法RoTRR与其他算法在数据集BAd和USPS上的对比结果如表1 所示。黑色字体表示最优算法的结果。可以从表1 中看出:本文算法由于充分利用了图像张量的空间信息因此取得了更高的分类结果。另外本文的方法通过计算来自动选择张量秩, 解决了张量秩不唯一的问题, 能更准确的反映张量数据的组成结构。

3.2 参数分析

图1 所示为本文算法调整参数λ 和 β 的结果。在图1 中可以看出:算法RoTRR取得最优值时, 参数的取值分别是:BAd:λ=0.1, β=0.001, USPS:λ=0.0001, β=0.01。

4 结论

本文提出秩优化的张量岭回归算法, 解决了张量CP分解中秩不唯一的问题, 可以更有效地利用张量中的相关信息。在两个图像数据集上构造实验, 以所有类的平均准确率为衡量标准, 分析了本文算法的性能与相关参数。通过实验分析得出本文提出的算法可以取得更优的分类结果。

参考文献

[1]Shakhnarovich, G., Indyk, P., Darrell, T.Nearest-neighbor methods in learning and vision:theory and practice.Cambridge Massachusetts, MIT Press, 2006.

[2]Hoerl, A.E., Kennard, R.W., Ridge regression:biased estimation for nonorthogonal problems.Technometrics, 1970, 12 (1) , 55–67.

[4]X.Cai, F.Nie, H.Huang, and C.Ding.Multiclass l1, 2-normsupport vector machine//Proceedings of the International Conference on Data Mining, Vancouver, Canada, 2011:91–100.

[5]Tan, Xu and Zhang, Yin and Tang, Siliang and Shao, Jian and Wu, Fei and Zhuang, Yueting.Logistic tensor regression for classification.Intelligent Science and Intelligent Data Engineering.2012, 573--581.

[6]Han, Yahong and Yang, Yi and Zhou, Xiaofang.Coregularized ensemble for feature selection//Proceedings of the international joint conference on Artificial Intelligence, Beijing, China, 2013:1380--1386.

改进的回归型支持向量机学习算法 篇2

支持向量机 (SupportVectorMachine, 简为SVM) [1、2]是由AT&T贝尔实验室的Vapnik及其研究小组于1995年提出来的一种新的机器学习算法SVM的方法最早是针对模式识别问题提出的, 随着Vapnik对ε不敏感损失函数的引入, 已将其推广应用到非线性回归估计和曲线拟合中, 得到了用于曲线拟合的回归型支持向量机方法 (SupportVector MachineforRegression, 简为SVR) , 并且表现出很好的学习效果。用于回归估计的支持向量方法在非线性系统辨识、预测预报、建模与控制等领域都有潜在的广泛应用, 使得对其进行研究显得非常重要。

但是, 用于回归估计的标准SVR算法在求解大规模问题时存在学习速度过慢的问题。因此, 如何减少计算时间和存储空间成为用于回归估计的SVR学习算法的研究热点[3]。由于O.L.Mangasari等人提出的用于模式识别的SOR (Successive Over relaxation for Support Vector Machine) 算法[4]适合迭代求解并能用于解决大规模问题。因此, 现考虑将这一方法推广到回归估计问题中, 对用于回归估计的标准SVR算法的优化式加以改造, 得到了一种回归型支持向量的改进算法。这一新的算法具有能减少计算复杂性、提高学习速度和在一定程度上能提高回归估计的精确性等方面的优点。

1标准的回归型支持向量机 (SVR) 算法

先简要介绍一下用于回归估计的标准支持向量机学习算法。

假设给定了训练数据{ (xi, yi) , i=1, 2, …, l}, 其中xi∈Rd是第i个学习样本的输入值, 且为一d维列向量xi=[x${}_i^1$, x${}_i^2$, …x${}_i^d$]T, yi∈R为对应的目标值。先定义ε线性不敏感损失函数为

即如果目标值y和经过学习构造的回归估计函数的值f (x) 之间的差别小于ε, 则损失等于0。

支持向量机的基本思想是:将输入样本空间非线性变换到另一个特征空间, 在这个特征空间中构造回归估计函数, 而这种非线性变换是通过定义适当的核函数K (xi, xj) 来实现的。其中K (xi, xj) =ϕ (xi) ϕ (xj) , 回归函数为

f (x) =ωTϕ (x) +b (2)

我们的目标就是寻找ω, b对使在式 (1) 固定的条件下最小化置信范围。这样一来, 最优化问题为

当约束条件不可实现时, 可以引入松弛变量ξi, ξ*i;这样最优化问题就转化为

其对偶最优化问题为

$\{\begin{array}{l}\underset{\alpha ‚\alpha {}^{*}}{{\displaystyle \max }}[-\frac{1}{2}{\displaystyle \sum _{i=1}^l{\displaystyle \sum _{j=1}^l(}}\alpha {}_i-\alpha {}_i^{*})(\alpha {}_j-\alpha {}_j^{*}){\rm K}(x{}_i‚x{}_j)-\\ \epsilon {\displaystyle \sum _{i=1}^l(}\alpha {}_i+\alpha {}_i^{*})+{\displaystyle \sum _{i=1}^{l}y}{}_i(\alpha {}_i-\alpha {}_i^{*})]\\ \text{s}.\text{t}.{\displaystyle \sum _{i=1}^l(}\alpha {}_i-\alpha {}_i^{*})=0\\ 0\le \alpha {}_i\le C‚\\ 0\le \alpha {}_i^{*}\le C\end{array}(5)$

其中只有部分参数 (αi-α*i) 不为零, 它们就是问题中的支持向量 (SV) 。从而通过学习得到的回归估计函数为

f (x) =${\displaystyle \sum _{x{}_i\in \text{S}\text{V}}}$ (αi-α*i) K (xi, x) +b (6)

式 (6) 中

$b=\frac{1}{{\rm N}{}_{\text{Ν}\text{S}\text{V}}}${${\displaystyle \sum _{0<\alpha {}_i<C}}$[yi-${\displaystyle \sum _{x{}_i\in \text{S}\text{V}}}$ (αi-α*i) K (xj, xi) -ε]+${\displaystyle \sum _{0<\alpha {}_i<C}}$[yi-${\displaystyle \sum _{x{}_j\in \text{S}\text{V}}}$ (αj-α*j) K (xj, xi) +ε]}。

上式中NNSV为标准支持向量数量。

2改进的回归型支持向量机算法

将Mangasarian提出的用于分类的LSVM方法推广到回归估计问题中, 便可得到改进的用于回归估计的支持向量机 (LSVM-R) 。类似于文献[4]中LSVM的设计方法, 将式 (4) 改造成如下最优化问题

$\{\begin{array}{l}\underset{\omega }{{\displaystyle \min }}\frac{1}{2}\omega {}^{\text{Τ}}\omega +\frac{1}{2}b{}^2+\frac{C}{2}{\displaystyle \sum _{i=1}^l(}\xi {}_i^2+\xi {}_i^{*}{}^2)\\ \text{s}.\text{t}.y{}_i-\omega \text{ϕ}(x{}_i)-b\le \epsilon +\xi {}_i‚\\ \omega \text{ϕ}(x{}_i)+b-y{}_i\le \epsilon +\xi {}_i^{*}‚\\ i=1‚2‚\cdots ,l\end{array}(7)$

可以利用拉格朗日乘子法来求解这个约束最优化问题, 为此构造如下拉格朗日函数

$L{}_{{\rm P}}=\frac{1}{2}\parallel \omega \parallel {}^2+\frac{1}{2}b{}^2+\frac{C}{2}$${\displaystyle \sum _{i=1}^l}$ (ξ${}_i^2$+ξ*i2) -${\displaystyle \sum _{i=1}^l}$αi[ε+ξi-yi+ωϕ (xi) +b]-${\displaystyle \sum _{i=1}^l}$α*i[ε+ξ*i+yi-ωϕ (xi) -b] (8)

根据最优化理论, 将LP分别对求ω, b, ξi, ξ*i偏导数并令其为零得

将式 (9) 代入式 (8) , 得到对偶最优化问题

通过学习我们可以得到的回归估计函数为:

f (x) =${\displaystyle \sum _{x{}_i\in \text{S}\text{V}}}$ (αi-α*i) K (xi, x) +b (11)

根据最优化的充要条件 (KKT条件) 可知:

$\{\begin{array}{l}\alpha {}_i*[\epsilon +\xi {}_i-y{}_i+\omega \text{ϕ}(x{}_i)+b]=0\\ \alpha {}_i^{*}*[\epsilon +\xi {}_i^{*}+y{}_i-\omega \text{ϕ}(x{}_i)-b]=0\end{array}$

(12)

这样可以计算出估计函数中的参数b的值:

上式中NNSV为标准支持向量数量。

3结论

将标准的回归估计支持向量算法中的式 (4) 进行了改进, 最后得到了与标准的回归估计支持向量算法的对偶最优化问题式 (5) 相似的改进的对偶最优化问题式 (10) 。将式 (5) 和式 (10) 进行比较可以发现:一方面, 式 (10) 中变量没有上界约束;另一方面, 式 (10) 中没有等式约束条件, 从而简化了二次规划问题的求解过程。因此, 这样的改进有一定的优越性:不仅可以减少计算的复杂性, 提高学习的速度;同时在一定程度上能提高回归估计的精确性, 特别是用于解决大规模样本问题。

参考文献

[1]张学工.统计学习理论的本质.北京:清华大学出版社, 2000

[2]Vapnik V N.The nature of statistical learrning springer theory.New York:1995

[3]杜树心, 吴铁军.用于回归估计的支持向量机方法.系统仿真学报, 2003;15 (11) :1580—1585

回归算法 篇3

Vapnik等人提出的统计学习理论SLT(Statistical Learning Theory)[1]是一种针对小样本情况研究统计学习规律的理论,该理论的核心思想是通过引入结构风险最小化准则来控制学习机器的容量,从而刻画了过度拟合与泛化能力之间的关系。在这一理论基础上产生的支持向量机SVM(Support Vector Machines[2,3])学习方法近来受到广泛重视,该方法不但引入了结构风险的概念,还采用了核映射的思想,与传统方法相比,支持向量机所具有的优势体现在:即克服了传统方法的大样本要求,还有效地克服了维数灾难及局部极小问题,并在处理非线性问题时显示了其卓越的优越性。支持向量机以其出色的学习性能已经广泛用于解决分类与回归问题,随着其应用领域的不断扩大以及在应用中遇到的问题也反过来要求支持向量机本身不断完善和发展。支持向量机分类算法通过求两类样本之间的最大间隔来获得最优分离超平面,其几何意义相当直观,而回归算法的几何意义就不那么直观了。另外,有一些适用于分类问题的快速优化算法却不能用于回归算法中,因此,研究分类与回归之间的关系就显得很有意义。本文讨论了分类与回归算法之间的关系,利用回归样本集因变量的上下平移 将回归问题转化为分类问题,然后从理论上证明了分类与回归问题的等价性。

1 从回归到分类

文献[4]通过变量代换给出了支持向量机分类与回归之间的关系,并指出分类是一种特殊的回归。下面直接给出非线性情况下的分类与回归算法。这里采用一个非线性映射ϕ将数据映射到一个高维特征空间,然后在高维特征空间中进行线性分类与回归运算,其中涉及到的高维内积运算用一个核函数来代替,这也正是支持向量机在处理非线性问题时的巧妙所在。

给出训练样本集为:

(xi,yi) xi∈Rni=1,…,l

对于分类情况,yi∈{+1,-1},对于回归情况,yi∈R。

分类问题是解下面的二次规划:

$\min \frac{1}{2}$w2+C${\displaystyle \sum _{i=1}^l}$ξi (1)

约束为:

yi(〈w,ϕ(xi)〉+b)≥1-ξii=1,…,l (2)

ξ1≥0 i=1,…,l (3)

在回归问题求解中,设回归函数为:

f(x)=〈w,ϕ(x)〉+b (4)

回归问题归结为解下面的二次规划:

$\min \frac{1}{2}$w2+C${\displaystyle \sum _{i=1}^l}$(ξi+ξi*) (5)

约束为:

在支持向量回归中,y取连续的实值,而不是二元值。但实际上并没限制y取二元值。假设y∈{+1,-1},在训练样本集上进行回归操作,可以得到下面的定理。

定理1 设在规划参数C下分类问题(1)的最优解是(w,b),则存在一个a∈(0,1),对于∀ε∈[a,1)时,回归问题(5)在规划参数(1-ε)C下的最优解是(1-ε)(w,b)。

该定理的证明可以参考文献[4],这也表明分类问题完全可以通过回归方法来求解,分类是一种特殊的回归。

2 从分类到回归

文献[5]从另外一个角度给出了一种基于闭凸包收缩的最大边缘分类算法,其优化问题的几何意义清楚、明确,并且还将该分类算法应用于函数回归中[6],从而能很好地给出回归问题的几何意义。该方法首先通过样本集因变量的上下平移ε将回归问题转化为分类问题,然后求两类集合收缩闭凸包之间的最小距离,最后根据最小距离点求得的最大间隔分离超平面得出回归函数,从而建立了分类与回归之间的关系。下面应用前面的思想将支持向量机回归问题转化为分类问题,并从理论上证明这种转化的等价性。

标准的支持向量机回归算法引入两个参数ξ、ξ*来控制误差的大小,如优化模型(5)。文献[7]采用一个参数来控制误差,进而给出单参数约束下的支持向量回归算法。

在ε-不敏感损失函数下,采用一个参数来控制误差项,可得下面的优化问题:

$\min \frac{1}{2}$w2+C${\displaystyle \sum _{i=1}^l}$ξi (9)

约束为:

f(xi)-yi≤ξi+ε i=1,…,l (10)

ξi≥0 i=1,…,l (11)

则有下面的定理。

定理2 优化问题(9)与优化问题(5)的最优解是等价的。

该定理表明单参数约束下的回归模型与标准回归模型是等价的,下面建立单参数约束下的回归模型与分类之间的关系。将单参数回归模型的约束条件的绝对值符号去掉,优化问题为:

$\min \frac{1}{2}$w2+C${\displaystyle \sum _{i=1}^l}$ξi (12)

约束为:

yi-〈w,ϕ(xi)〉-b≤ε+ξii=1,…,l (13)

〈w,ϕ(xi)〉+b-yi≤ε+ξii=1,…,l (14)

ξi≥0 i=1,…,l (15)

为了建立回归与分类之间的关系,下面通过因变量的上下移动ε+1获得两个集合:

D+={(ϕ(xi),yi+ε+1),i=1,…,l}

D-={(ϕ(xi),yi-ε-1),i=1,…,l}

当ε充分大时,D+和D-显然是线性可分的。当然不必要保证完全线性可分,可以通过引入松弛变量ξ允许一定的误差存在。

对上面两个集合进行SVM分类,优化问题为:

$\min \frac{1}{2}$$\overline{w}$2+C${\displaystyle \sum _{i=1}^l}$ξi (16)

约束为:

$\langle \overline{w}‚z{}_i\rangle +\overline{b}-\xi {}_i\le -1z{}_i\in D{}^{+}$ (17)

$\langle \overline{w}‚z{}_i\rangle +\overline{b}+\xi {}_i\ge +1z{}_i\in D{}^{-}$ (18)

ξi≥0 i=1,…,l (19)

令$\overline{w}=(\overline{w}{}_1‚\overline{w}{}_2)$,按照超平面的函数表示习惯,不妨设$\overline{w}{}_2=-1$,则优化问题(16)成为:

$\min \frac{1}{2}$$\overline{w}{}_1$$+\frac{1}{2}+C$${\displaystyle \sum _{i=1}^l}$ξi (20)

约束为:

$\langle \overline{w}{}_1‚\text{ϕ}(x{}_i)\rangle -y{}_i-\epsilon -1+\overline{b}-\xi {}_i\le -1$ (21)

$\langle \overline{w}{}_1‚\text{ϕ}(x{}_i)\rangle -y{}_i+\epsilon +1+\overline{b}+\xi {}_i\ge +1$ (22)

ξi≥0 i=1,…,l (23)

经整理,优化(20)与优化(12)是等价的,这就证明了优化问题(16)和优化问题(12)是等价的。再由定理2知优化(12)与优化(5)是等价的。于是可得下面的定理。

定理3 将回归问题的训练样本的因变量上下平移ε+1得到两个集合D+和D-,则优化问题(16)和优化问题(5)是等价的。

该定理说明了回归问题可以通过分类方法来求解。

3 结 论

本文讨论了支持向量机分类与回归算法之间的关系,通过对回归样本的上下平移将回归问题转化成分类问题求解,并证明了支持向量机分类算法与回归算法之间的等价性,这将为快速分类算法与回归算法之间的融合提供一定的理论基础。

参考文献

[1]Vapnik VN.Statistical Learning Theory[M].NewYork,Wiley,1998.

[2]Burges C J C.A Tutorial on Support Vector Machines for Pattern Rec-ognition[J].Knowledge Discovery and Data Mining,1998,2(2):121-167.

[3]Smola A J,Scholkopf B.A tutorial on support vector regression[R].NeuroCOLT TR NC-TR-98-030.Royal Holloway College University ofLondon,UK,1998.

[4]Pontil M,Rifkin R,Evgeniou T.From Regression to Classification inSupport Vector Machines.http://www.dice.ucl.ac.be/Proceedings/esann/esannpdf/es1999-462.pdf.

[5]Bennett K,Bredensteiner E.Duality and Geometry in SVMClassifiers.In P Langley,eds.Proc.of Seventeenth Intl.Conf.on MachineLearning,Morgan Kaufmann,San Francisco,2000,57-64.

[6]Bi J,Bennett K P.Duality,Geometry and Support Vector Regression.http://citeseer.nj.nec.com/543126.html.

回归算法 篇4

目前有相关研究正在关注网络流量预测问题,并根据相关资料提出了诸多预测模型和相关算法。这些模型和算法包括:基于自回归滑动平均或自回归的预测模型[1]、基于自回归的综合滑动平均[2]或基于分形自回归的综合滑动平均预测模型[3]、基于神经网络预测模型[4]、结合小波变换和小波分析预测模型[5]及综合小波与神经网络预测模型[6]。

1 问题说明及模型定义

1.1 预测问题定义

为了解决网络流量的预测问题,通常将它写成随机过程:X=(xt:t=0,1,2⋯),数据包级网络流量有四种形式:数据包的到达时间;数据包的大小;相邻数据包的时间差;相同间隔内的到达数据包的数目。

问题描述的具体表达:给当前时间以及过去时间的值Xt=(xt-p+1,⋯,xt-1,xt),预测将来时间点值为xt+q,其中,p是预测数据长度,q是预测步长。

1.2 回归模型

xt+q预测值可用公式1确定:

其中预测值,E(|)为条件期望值,求解条件期望需先得知X=(xt:t=0,1,2…)的联合概率分布。因此,直接利用公式1进行流量预测很难,在实际情况下可转化成回归模型形式。

在文献[1]中提到,在xt=ξ2(t=1,2,⋯)的前提下,公式1描述的预测问题可描述成回归问题:给定出ξ2的任意一个子闭集M,找出M里面的某一个元素,使之间的均方误差最小。从而对xt+q的预测可以由公式2给定:

2 基于机器学习的流量预测算法

首先给出相关算法的流程,然后研究算法的各个细节。本文提出了利用三种算子:线性算子[2]、分段恒定算子[4]、前馈神经网络[3]。针对网络流量的自相似性,可提出使用主成分分析[5](Principal Component Analysis,PCA)作为算法的预处理的方法;对于分段恒定算子来说,提出相关权重的更新准则来利用各维特征之间的信息。本文将针对ADA-Boost方法的权重更新方法引起的过匹配(Overfitting)现象问题提出自适应的改进方法。

2.1 算法流程

基于经典Boosting算法得到基于机器学习的网络流量预测算法的流程如下:

1)建立训练集D=(X,Y),对D中的样本,输入为Xt=(xt-p+1,⋯,xt-1,xt)(Xt∈Rp);输出为Yt=xt+q(Yt∈R)。其中,t=1,2,…,N,N为D中的样本的总数。

2)针对训练集样本初始化权重:D1(t)=1/N;

3)重复下述迭代过程,直到满足停止规则为止。

a)针对样本权重分布D1,在D上训练弱回归算子;

b)得到弱回归算子:Rp→R;

c)利用弱回归算子评估数训练集D中样本t所属误差信息lt(t);

d)计算训练误差st;

e)选择系数αt以衡量弱回归算子ht;

f)更新D中的样本权重分布:Dt→Dt+1;

g)判断结束条件是否达到。

4)得到弱回归算子输出结果:{ht,t=1,2,⋯T}→H。

2.2 预处理过程

基于网络流量的突发性导致预测峰值的误差的情况,本文中提出采用主成分分析方法作为算法的预处理方法,相同长度的历史数据提供了更多关于历史数据的有效信息,有助于提高相关算法的性能;在主成分分析过程中执行解过程,有助于预测出的尖峰误差降低。

2.3 设计弱回归算子

1)线性算子

在这种情况下,弱回归算子可采用,其中,权重a根据如下方程获得:R∙a=r,其中,R是输入矩阵,r是输入输出形成的向量。

2)前馈神经网络

前馈神经网络描述非线性问题方面具有优势,本文设计采用三层前馈神经网络作为算子,其中,隐含层包括10个神经元、输出层包含1个神经元,层次之间采用sigmoid转移函数,隐含层跟输出层采用线性转移函数。

3)分段恒定算子

针对输入特征建立分段恒定算子:。

其中,xt-p+k是向量Xt=(xt-p+1,⋯,xt-1,xt)中的某一维的特征;bj(j=1,…,Num)是取值范围xt-p+k的等分点Num构成序列,aj可由xt-p+k在[bj,bj+1]区间的期望确定:aj=E(xt-p+k|bj≤xt-p+k≤bj+1),回归算子最终由预测误差的最小值确定。

2.4 更新相关权重分布

样本权重分布在ADA-Boost算法中,采用公式3更新:

其中,Zt保证Dt+1(t)的数据分布形式,Zt是规整化系数。文献[6]通过加入参数的方法来控制相关权重更新的速度。但是如何确定该参数,文献[6]没有给出具体思路。

为了处理上述文献[6]未解决的相关问题,在本文中提出本权重更新方法:

在公式3中,通过加入Rate参数,能够控制权重更新速度。由于Rate参数前后两轮的迭代过程中预测误差之比比较高;算法中迭代次数没有引入参数的位置均需设置。实验结果证明了该策略能够较好地解决过匹配现象。

在本文提出的改进权重更新方式中,需要为每维特征维护权重分布w(t),t=0,…,p。

令w(i),w(j)(i,j=0,…,p)分别表示特征维xt-i,xt-j的当前权重分布;令w’(i)、w’(j)分别表示特征维xt-i,xt-j更新后的权重分布;假设在前一轮迭代过程中,特征维xt-i被选中用于构造弱回归算子,那么对于权重分布w(i),仍然可按公式3或者公式4进行计算,然而,对于其他特征维xt-j所对应的权重分布,则应根据其与特征维xt-i的相关性确定。

一般情况下,xt-j和xt-i的相关性应该在相关和不相关关系之间,可得到权重更新公式:

在公式5中,αij∈[0,1]是衡量xt-j和xt-i相关性的参数,αij可根据xt-j和xt-i之间的Kullback-Leibler距离来确定(公式6),或者由序列Xt=(xt-p+1,⋯,xt-1,xt)的自相关函数(Autocorrelation Function,ACF)[9]确定(公式7)。在实验中采用后者来计算αij。

2.5 算法终止的准则

在理论上,为了避免εi逗留在0.5的左右,在新方法中,设置最大迭代次数为Tmax,算法终止规则由εi≥0.5或t≥Tmax给出。

2.6 组合弱回归算子输出

在回归模型中,通过中值方式输出时较稳定,本文采用中值方式作为弱回归算子组合输出方式。

3 实验结果及分析

3.1 实验设计

合成数据集和实际数据集是实验测试数据,合成数据集利用分形高斯噪声模型[7]模拟出长度为1000的网络流量,其中用于训练和测试数据分别为50%,预测步长为1,最大迭代步数设为20,用于预测数据长度的p取为7。

通过视频“Star War”获得实际数据集,将原始的视频流等量切分长度为1000的相关片段,然后,分别用方差—时间图法测试其自相似、用Surrogate方法测试其非线性,那么既会呈现自相似性、又表现出非线性性的流量片段用来评价算法。为了方便比较,把每一个片段输出都设定到[0,1]的范围内。

我们采用均方误差(MSE)、逆信噪比(ISNR)和最大误差(Max Error)评价算法性能。

3.2 实验结果和分析

基于ARMA模型的线性预测方法的结果见图1,横轴X表示网络流量自相似程度;纵轴表示预测结果ISNR。从图1可得Boosting算法比Lin算法[5]提高流量预测性能。

首先在回归模型下,采用FFNN作为算子的结果性能,在图2的结果中,圆圈线条是采用FFNN进行预测的曲线;剩余两条线是用Boosting进行预测的结果,虚线线条是采用经典的ADA-Boost权重更新方法,实线是采用自适应的更新权重方式,可得出结论,Boosting提高流量预测精度,算法性能因自适应更新权重机制而得到了提高。

图3给出了预测实例,其中横轴表示时间单位(秒),纵轴表示单位时间内到达的数据包数量;实线表示流量的实际值,虚线表示预测结果,图(a)是用Boosting进行预测的结果,图(b)是用前馈神经网络的预测结果。

从图5可见利用了关于历史数据的相关信息,使用主成分分析方法可以进一步提高了预测性能;大多数情况下的预测结果最大误差有明显降低。

图6以MSE作为评价依据,虚线条表示采用FFNN作为算子,并用PCA和FFNN作为预处理方法得到的结果;实线条表示采用分段恒定算子保留权重分布策略(BMR)。

图7给出基于Boosting的算法中,在回归模型下使用分段恒定算子,并为每一维特征保留权重分布策略(BMR)的实例。其中,X横轴代表时间(单位为秒),Y纵轴表示MSE;实线表示流量的实际值,虚线表示流量的预测结果。

4 结论

预测问题是监督学习问题,本文研究了基于机器学习方法的网络流量预测算法,本文重点研究回归学习模型。基于回归学习模型提出了基于的网络流量预测算法,并进行了比较模拟实验,相关结果表明该算法的效果优于传统相关算法。

参考文献

[1]Brockwell P,Davis R.Time series theory and methods.Springer-Verlag,New York,2nd edition,1991:40-55.

[2]陈静,李扬渊,何大可.FAPKC3的搜索攻击及非线性算子的新构造[J].计算机工程,2008,34(2):111-113.

[3]赵淑海,邱洪泽,马自谦.基于PPGA-MBP的神经网络优化及其应用[J].计算机工程与应用,2006,13:73-76.

[4]史迎春,王韬,周献中.基于语义的新闻视频检索研究[J].计算机工程,2004,30(16):155-157.

[5]艾玲梅,李营,马苗.基于EMD和PCA的P300分类算法[J].计算机工程,2010,36(5):182-187.

[6]Bone R,Assaad M,Crucianu M.Boosting recurrent neural networks for time series prediction[D].Proceedings of the Int Conf on ArtificialNeural Networks and Genetic Algorithms,2003:204-210.

[7]Gripenberg G,Norros I.On the prediction of fractional Brownian motion[J].Journal of Applied Probability,1996,33:400-410.

[8]Khotanzad A,Sadek N.Multi-scale high-speed network traffic prediction using combination of neural network.Proceedings of the Inter national Joint Conference on Neural Networks,2003,2:1071-1075.

回归算法 篇5

关键词：差分隐私,线性回归分析,敏感性,隐私预算

0 引言

线性回归分析是通过对给定数据集的属性值和预测值的统计整理和分析,找出已知属性和预测值的变化规律,用模型表示这种变化规律,并进行预测和分析。回归分析可应用于企业投资分析、医疗支出预测和机器学习等领域。图1为线性回归的一个实例,根据数据集中某台设备的温度和产量两个属性,找出这两者的线性关系模型,这样就能够利用设备的温度预测出该设备的产量。

图1线性回归模型实例

在实际应用中,直接发布回归模型参数容易泄露预测函数和数据集的数据信息。为了防止这种隐私泄露,隐私保护就变得非常重要。常用的隐私保护方法有k-anonymity[1]、l-diversity[2]、t-closeness[3]等,但是这些方法大部分都是基于某种背景知识。2006年Dwork[4]提出了差分隐私的理论体系,该模型不论攻击者具有多少背景知识,都能够通过添加噪声的方式,在较高程度上保护数据集隐私的同时尽可能减小数据的失真。文献[5]用差分隐私的方法实现了社会网络数据的发布。文献[6]基于差分隐私对一批线性计数查询提出了一个最优方案。文献[7]提出了一种发布差分隐私直方图的有效方法。文献[8]提出了一种基于遗传算法的多用途差分隐私模型。文献[9-11]总结了各种面向数据发布和分析的隐私保护方法,指出基于差分隐私的回归分析方法,并表明把差分隐私和回归分析进行结合和拓展也是一大研究热点。

应用差分隐私方法设计回归分析的算法中,文献[12]直接在输出结果上添加噪音,在一定程度上保护了隐私,但是所需噪声较大,影响预测精度; 文献[13,14]提出了一种逻辑回归分析方法,直接对n个扰动函数的均值添加噪声,添加噪音量有所减少,但该方法通用性不强。

文献[15]提出了一种函数机制FM( Functional Mechanism) ,通过对目标函数的系数统一添加噪声,得到添加噪声后的目标函数,再计算出最优的预测模型参数。该方法通用性强,适用于线性回归和逻辑回归等多种分析方法,但是算法的敏感性偏高,造成添加噪声偏大,使模型预测精度偏低。对于这个问题,本文提出一种针对线性回归分析的差分隐私算Diff-LR。通过对线性回归模型的目标函数进行分解,分配合理的隐私预算,再用拉普拉斯噪声分别对两个子函数的系数进行扰动,降低了整个算法的敏感性,减少了添加的拉普拉斯噪声,使线性回归模型预测更准确。

1 相关理论

1. 1 相关定义

定义1[4]( ε-差分隐私) 设有两个数据集D1和D2,D1和D2最多相差一个元组,给定一个随机隐私函数A,Range( A) 表示A可能输出结果O的取值范围( O∈Rang( A) ) ,如果A满足下列不等式,则称函数A满足 ε-差分隐私。

其中,ε表示隐私预算的代价,ε越小,数据保护程度越高。

定义2[16]对任意函数f:D→Rd,f的敏感性可定义为:

其中,D1,D2为给定的数据集,相差至多一条元组。

拉普拉斯机制的主要思想是通过添加拉普拉斯噪声来实现保护隐私的效果。

定理1[16]对于任一函数f:D→Rd,D为数据集,Δf表示其敏感性的大小,那么随机算法:

满足ε-差分隐私。其中,是相互独立的拉普拉斯变量,Δf与隐私预算ε是拉普拉斯变量的重要参数,所添加的拉普拉斯噪声量大小与函数敏感性成正比,与隐私预算成反比。

1.2差分隐私组合特性

差分隐私包含两个重要的组合性质[18],一是序列组合性,二是并行组合性。

性质1[17](序列组合性)给定一个数据集D,任一随机函数Ai满足εi-差分隐私,其中1≤i≤n,则函数Ai构成的组合函数对同一数据集D满足∑εi-差分隐私。

性质2[17](并行组合性)设任一随机函数Ai满足εi-差分隐私,其中1≤i≤n,对于互不相交的数据集Di,则函数Ai(Di)构成的组合函数满足(max(εi))-差分隐私。

1.3问题描述

设D为给定的训练集,包含了个元组,每个元组ti有d+1个属性值分别是:X1,X2,…,Xd和Y,表示为ti=(xi1,xi2,d…,xid,yi),其中。利用训练集建立一个预测函数p(xi)=xTiw*,w*是一个d维实数向量。预测函数通过输入某个元组的xi1,xi2,…,xid属性值使输出的预测值yi尽可能精确,线性回归模型的预测值与实际属性值的误差n n用一个目标函数表示,误差越小,预测精度越高。最优的线性模型参数w*可定义为:,即目标函数取最小值时,模型参数w*为最优值。本文针对这样的线性回归模型,设计出满足差分隐私的线性回归算法Diff-LR。

2 Diff-LR算法设计与分析

2. 1 Diff-LR算法设计

Diff-LR算法首先对线性回归模型的目标函数进行推导,把它简化成一个简单的二次多项式函数; 然后把目标函数分解成两个子函数,计算它们各自的敏感性; 对子函数合理分配隐私预算,再分别对两个子函数的系数添加拉普拉斯噪声,得到两个新的子函数,重新组合成一个添加噪声后的目标函数。当该目标函数取最小值时,得到最优的模型参数。

线性回归模型的目标函数可做出如下推导:

那么,很容易把目标函数看作w的二次函数,可简化为:

把目标函数拆分成子函数g(w)和t(w),令g(w)=aw2,t(w)=bw。Δ1表示g(w)的敏感性,Δ2表示t(w)的敏感性。在二次函数中,理想情况下目标函数的值为0,此时最优w的值为,与系数c无关。因此Diff-LR算法在求最优线性回归模型参数时可忽略系数c。设邻居数据集D、D'只相差一条元组,两个数据集最后一条元组不一样,分别为tn、tn',根据敏感性的定义可计算Δ1和Δ2:

对子函数g(w)、t(w)分配隐私预算ε1、ε2,根据拉普拉斯机制的特性可知,拉普拉斯噪音量的大小与函数的敏感性成正比,与隐私预算成反比。为了减少添加的噪声量,当敏感性较大时分配较大的隐私预算,敏感性较小时分配较小的隐私预算。根据计算的Δ1和Δ2的大小可知,敏感性在数据集属性维度d较大时,g(w)的敏感性比t(w)的敏感性更大。因此,分配隐私预算ε1、ε2时,使ε1≥ε2,即对于固定隐私预算ε,通过合理分配ε1、ε2,就可以减少噪音,使线性回归模型预测更准确。

Diff-LR算法如下:

如上述算法所述,第1-3行主要是把目标函数拆分成两个子函数g(w)和t(w),其中a、b分别表示两个子函数的系数,ε表示整个算法需要的隐私预算,ε1、ε2是分别分配给子函数g(w)、t(w)的预算;第4、5行主要是对两个子函数的系数分别添加噪声,表示系数a、b的矩阵形式,λ1、λ2分别表示添加拉普拉斯噪声后的子函数系数;第6、7行主要是求添加噪声后的目标函数表示对g(w)、t(w)添加噪声后的子函数;第8、9行表达的是当取最小值时,求取最优的模型参数,并返回的值。

2. 2 算法分析

基于下面定理的证明,验证算法Diff-LR的正确性。

定理2函数满足ε1-差分隐私

证明给定数据集D 、D' ,D 、D' 最多相差一条元组,假设D 、D' 只有最后一条元组不一样,分别为tn、tn',根据可得:

的计算满足ε1-差分隐私。同理可证,函数满足ε2-差分隐私。

定理3 Diff-LR算法满足ε-差分隐私

证明算法中第11行是,其中和分别满足ε1-差分隐私和ε2-差分隐私,且ε=ε1+ε2,根据性质1差分隐私的序列组合特性,可以推出满足差分隐私,即满足ε-差分隐私,证明了Diff-LR算法满足ε-差分隐私。

Diff-LR算法主要是对线性回归模型的目标函数拆分后的两个子函数分别计算敏感性,分配差异化的隐私预算以及对子函数的系数分别添加噪音,对于随机添加的噪音可能致使系数可能变成负数,造成不存在最优解问题,本文引用了文献[15]提出的正则化和谱修剪方法来避免这种情况。

3 实验设计与分析

文中的实验环境为Win 7,3. 6 GHz,2. 00 GB,Diff-LR算法是用Matlab语言实现。同FM算法一样,所用数据集US和Brazil都来自Integrated Public Use Microdata[18],分别包含370 000 和190 000条数据集,对数据集中的每个属性值进行预处理,使它们的取值范围在[- 1,1]。

本文通过选取数据集条数的80% 作为训练集,用来得到线性回归模型,剩下20% 为测试集,用来测试该模型的准确性。对实验结果采用的评判标准是均方误差errorRate ,定义如下:

其中,n表示测试集数据元组个数,xi和yi是数据集中已经给出的数据。每条元组的均方误差越小,线性回归模型预测越准确。

分别对数据集US和Brazil进行实验,针对不同数据集,不同的隐私预算 ε 值,Diff-LR算法和FM算法对实验结果产生影响如图2 和图3 所示。通过合理分配隐私预算参数 ε1、ε2,当隐私预算 ε 相同时,Diff-LR算法比FM算法均方误差更小,即Diff-LR算法添加噪声后的线性回归模型预测比FM算法更准确。随着 ε 逐渐增大,Diff-LR算法均方误差errorRate不断接近无噪音预测模型产生的误差,在保护隐私的同时极大降低了数据失真。不论对于较大数据集US还是较小数据集Brazil,Diff-LR算法都比FM算法的errorRate更小。同时,无论隐私预算怎么变化,无噪音模型的均方误差基本不变。

Diff-LR算法的均方误差比FM算法均方误差更小的原因有两点。1) Diff-LR算法对目标函数进行拆分,使得其中一个子函数的敏感性为4d ,另一个子函数的敏感性为2d2,而FM算法的敏感性为2( 2d + d2+ 1) 。根据拉普拉斯机制性质可知,拉普拉斯中噪音量的大小与敏感性成正比,算法的敏感性越大所需要的噪声越大。因为FM算法敏感性比Diff-LR算法敏感性更大,所以FM算法添加噪声产生的影响比Diff-LR算法更大,造成Diff-LR算法比FM算法均方误差更小,预测更准确。2) FM算法和Diff-LR算法均满足 ε -差分隐私,不同的是,FM算法是把隐私预算 ε 分配给整个目标函数,而Diff-LR算法通过分别给两个子函数分配不同的隐私预算 ε1、ε2,同时保证 ε =ε1+ ε2。Diff-LR算法为了减少添加的噪声量,给敏感性较大的函数分配较大的隐私预算,给敏感性较小的函数分配较小的隐私预算,即 ε1≥ ε2,添加的噪声更少,数据失真更小,预测精度更高。

4 结语

回归算法 篇6

关键词：线性解码器,回归模型,深度神经网络,图像分类

0 引言

随着互联网技术和多媒体技术的蓬勃发展,以及社交媒体的日益普及和流行,人们接触到的多媒体数据也呈现出直线增长的趋势。图像数据在多媒体数据海洋中占据了十分重要的位置,它也逐步成为人们信息交流、经验分享中的重要媒介。然而,在这些网络资源库中,大部分的图像数据是没有任何文本标注的,如果单纯依靠手工标注的方式对这些纷繁复杂的图像进行分类和管理,则存在费时费力、效率低的问题。于是,如何采用合理的计算机图像分析方法,进行高效的自动分类、管理及使用,一直是图像信息处理领域的研究热点[1,2,3,4,5]。

一图胜千言,图像的底层特征和高层语义之间存在着难以逾越的语义鸿沟[6]。为此,许多研究者提出了基于机器学习、统计分析的解决方法以缩小语义鸿沟,可成功应用于提高图像分类的准确率。例如:文献[7]采用误差反向传播算法BP,在底层特征的基础上运用机器学习的理论来得到图像的抽象表示。但是,这种方法容易陷入局部最小值,难以达到最优的学习效果,对复杂函数的表示能力有限,不能有效针对多重的分类问题进行泛化。针对这些问题,Hinton在2006年提出了第三代神经网络[8],即:深度学习方法。该方法可以通过学习一种深层非线性网络结构来实现复杂函数逼近,展现出较为强大的从大量样本集中学习数据集本质特征的能力[9]。例如:文献[10]采用卷积神经网络CNN获取图像的特征,并构成一幅特征映射图来对图像进行分类;但这种方法需要收集大量有标记的图像样本来训练,对训练集的要求比较高。考虑到标记样本有限的问题,Poultney等运用未标记样本集学习得到了图像的特征表达关系[11];Le等采用基于稀疏自编码的神经网络从图像中建立其高层次的特征检测器[12],采用无监督的反向传播方法,使目标值等于输入值,但该算法需要对输入进行限制或者缩放,使输入值在[0,1]的范围内。然而,目前关于数据范围的优化取值还属于开放性问题。

针对数据输入范围的限制和缩放问题,本文提出了基于线性解码器的深度神经网络方法,本文算法的流程如图1所示。先从原始的大图像中随机选择小块的图像区域,然后通过线性解码器学习到小图像的特征参数,并将其运用到对原始大图像的卷积和池化操作中,得到特征矩阵。在此基础上,进行Softmax回归分类和结果优化,与传统的基于向量模型的特征相似度度量模型相结合,提出了相应的自动分类机制。该网络包含输入层、隐藏层和输出层,并且无需对输入数据进行限制或缩放,简化了神经网络训练的复杂度,提高了数据预处理的效率。

1 基于线性解码的卷积特征分析

底层特征分析一直是影响图像语义理解和分类效率的关键因素。本节采用基于线性解码器的神经网络进行图像的特征学习,再利用学习到的参数在训练集及测试集中进行卷积特征分析,以及池化操作得到图像特征矩阵。

1.1 图像特征的线性解码算法分析

受深度学习中稀疏自编码方法[12,13]的启发,本文提出一种基于线性解码器的神经网络方法。神经网络方法是模拟人类神经网络中的特性,即人类大脑中的神经元细胞在接受刺激后会变的活跃,并在相互之间传递信息;通过设置网络中的每一层的节点个数,即:神经元个数,在神经网络的各个层次中传递图像特征数据,在达到收敛阈值或者最大迭代次数时,实现图像本质特征的智能学习。模拟过程如图1所示,Layer L1为输入层,接受到输入信息以后该层的神经元被激活,处理信息后传递至Layer L2层,即:隐藏层;隐藏层的神经元被激活并将处理之后的信息传递至Layer L3层,即:输出层;输出层神经元接受信息以后,输出该层处理后的结果。

假设集合X={x1,x2,x3,…,xi,…,xm}表示未标记的图像训练数据集,其中,xi表示输入的第i幅图像,m表示未标记的图像数据集样本的数量。向量Y={y1,y2,y3,…,yi,…,ym}表示输入为X时,图像集合所对应样本标记的期望输出值,其中,yi表示输入为第i幅图像时的期望输出值。本节在已有未标记的图像样本集X的基础上,生成一个假设模型hw,b(x),表示输入为x时的假设输出,其中,w为权值向量,b为偏置向量。特征学习的过程就是求解向量w和向量b。

首先,设基于线性解码器的神经网络中第l层中的第i个神经元的激活度可表示为ai(l),输入为xi时隐藏层神经元j的激活度为aj(2)(xi),则在训练集X={x1,x2,x3,…,xi,…,xm}上可以求得隐藏神经元j的平均激活度为:

为了使数据表示稀疏化,加入稀疏性参数ρ,满足限制条件。为了使隐藏神经元的平均激活度维持在一定范围内,实现对线性解码器的稀疏性控制,引入基于相对熵的惩罚因子,则整体的代价函数为:

其中,第一项为均方差项,第二项为防止过度拟合添加的权重衰减项。nl表示网络层数,λ为权重衰减参数,第三项为稀疏性控制的惩罚项,β为控制稀疏性惩罚因子的权重。

采用Sigmoid函数,作为神经元的激活函数,并定义第l层第i个神经元对最终误差产生的影响为残差记为σi(l),显然:

其中,zi(l+1)表示第l+1层中第i个神经元的输入值加权和。然后,求出J(w,b)的偏导数值并采用梯度下降法计算其最优化权值向量w和偏置向量b,待算法收敛或达到最大迭代次数时,求得向量w和b,即完成了特征学习过程。

1.2 基于部分联通网络的卷积特征分析

由于神经网络方法需要训练网络中神经元的权值向量w和偏置向量b,而向量w和b的个数则取决于图像分辨率的大小[8]。图像的分辨率越大,网络需要学习的向量个数越多。可见,图像分辨率的大小直接影响参数学习的复杂度。

为此,本节提出基于部分联通网络的卷积算法,即:将图像训练集中初始的图像样本全部切分成若干个小区域,构成区域子集,作为神经网络的输入层,也相当于在原有全联通网络基础上,使隐藏层神经元只连接输入层的一部分神经元。通过该算法得到数据集卷积后的特征矩阵,将该矩阵作为图像分类器的输入。

假设集合Ω={(z1,r1),(z2,r2),…,(zi,ri),…,(zt,rt)}表示有标记的图像训练集样本,其中t用来表示已标记的训练集样本个数,并假设标记样本集Ω中的图像属于k个不同的类别,zi表示训练集中的第i幅标记样本图像,ri表示该图像所属的类别编号。假设未标记的图像测试集用S={s1,s2,…,si,…,sn}表示,其中si表示测试集中的第i幅图像,n表示测试集样本个数。假设数据集Ω和S中图像的分辨率为a×a,从中随机选取一块分辨率为b×b的一个局部小块图像。将选取的所有局部小块图像数据集X={x1,x2,x3,…,xi,…,xm}作为线性解码器的输入,如图1中Pathes所示。

根据1.1节的特征学习算法计算出权值向量w和偏置向量b,设置卷积运算的步长为1,并利用从X={x1,x2,x3,…,xi,…,xm}中学习到的参数值对训练集Ω以及测试集S进行卷积运算。则在训练集Ω和测试集S上完成卷积后的特征矩阵分别为DConvoled_Train、DConvoled_Test,其维数大小均为为:

其中,k为隐藏层中的神经元个数。可见,矩阵DConvoled_Train和DConvoled_Test的维数非常高,不利于训练分类器,很容易出现过拟合的现象,影响图像分类效率。为此,本文采用计算图像各个区域上的特定特征的平均值方法对图像不同位置的特征进行聚合统计,即:池化操作。设定池化区域的大小为Dpooling,且池化操作必须作用于不重复的区域内,则可得到池化后的特征矩阵DPooled_Train和DPooled_Test。

2 基于卷积特征的回归预测

根据第1节中得到的训练集Ω与测试集S图像的特征矩阵DPooled_Train和DPooled_Test,采用改进的Softmax深度回归预测模型进行初步分类,并结合图像的视觉特征,学习得到测试集S中未标记样本si所属的语义类别。

2.1 回归函数定义和参数求解

将训练集图像的特征矩阵DPooled_Train作为该模型的训练样本,对于每一个输入的样本(zi,ri),该模型预测其每一种分类结果出现的概率值为p(ri=k|zi),假设函数定义如下:

其中,θ1,θ2,…,θk是该模型的训练参数。定义函数hθ(zi)求解的代价函数为:

其中1{ri=j}为指示性函数,当ri=j为真时,1{ri=j}=1,反之1{ri=j}=0。为了防止模型中参数的冗余,在代价函数J(θ)中加入权重衰减项:

进一步,求其偏导数为:

通过迭代得到J(θ)的最小值,求出参数θ1,θ2,…,θk,得到训练好的Softmax回归模型。然后运用该模型来对测试集S进行分类,通过式(5)计算出每一个样本在每一个类别中的概率值。

一般选择概率最大的类别为预测结果,然而,由于不可避免的参数误差、冗余及过拟合现象,单一地使用1.2节中学习到的特征与Softmax回归模型相结合,得到的分类结果会被上述因素影响。为了解决上述问题,该文采用多步分类的方法,即在Softmax回归模型计算出的预测概率中,由大到小排列,选择前个预测的类别作为初步的预测值,将对每一个样本si所属的类别候选集记为Ci:

其中,表示前k/2个预测的类别。

2.2 未标记测试样本的分类方法

在未标记的图像训练集X中,除了通过基于线性解码器的神经网络学习到的特征DPooled_feature,还可以提取图像的视觉特征。由于2.1节只是对测试集中的每个样本进行了初步预测,本节在预测标签集合Ci的基础上,在视觉特征空间中采用距离度量的算法确定最终的预测标签。

设从图像训练集和测试集中所提取的图像视觉特征的维数均为p,在包含m个有标记图像的训练集Ω上可得到视觉特征矩阵。同时在包含n个未标记图像的测试集Ε上得到视觉特征矩阵。设zi、sj分别表示矩阵A、B中的任意一个训练样本和一个测试样本的特征向量,它们之间的距离记为dij,选择欧式距离作为zi和sj的距离度量。

在2.1节中,已经完成了对图像的初步分类,因此,在计算样本间的距离时,只计算测试样本与预测类别Ci中包括的类别的距离。然后,取dij最小值所对应样本的类别作为最终的测试样本sj的预测结果,记为Li,完成图像的分类。整个算法流程如算法1所示。

3 实验结果与分析

3.1 数据集与特征提取

为了验证上述算法的性能,本文选取了两组图像数据集进行测试和验证。首先,从Web页面采集了10个语义类别的图像作为数据集,包括:鸟、马、小狗、海豚、大象、爆炸、飞机、摩托车、汽车、溪水。其中每个类别包含100幅图像,从中选取700幅图像作为训练集,其余300幅图像作为未标记的测试集。此外,还使用了公共图像数据集MSRA-MM[19]进行了实验验证,从MSRA-MM数据库中选取了6000幅图像作为训练集,其余3000幅作为测试集。图2显示了10个语义的Web图像数据的示例,其中每一列表示从一个语义类别中随机抽取的3幅图像样本。此外,实验提取的底层视觉特征包括256-d HSV颜色直方图、64-d LAB颜色聚合向量以及32-d Tamura方向度。

3.2 实验结果与分析

首先将Web数据集和MRSA-MM数据集中图像尺寸进行归一化,统一为96×96。同时,将用于1.1节中网络学习的小图像尺寸设定为8×8,且从每幅图像中提取100幅小图像,再从所有提取的小图像中随机选取100 000个样本作为线性解码器的输入。由于图像为彩色图,需要将三个通道的值同时作为输入层,则输入层的神经元个数为8×8×3,即192个;同样,输出层神经元个数也为192个,且设置隐藏层的神经元个数为400个,学习得到400个特征,如图3所示。图中每个小块图像表示所对应的隐藏层神经元学习到的特征值的可视化表示,可以观察到,很多小块都是类似图像的边缘部分,这有利于进行边缘检测来识别图像。同时,设置池化区域Dpooling的尺寸为19×19。

为了验证本文方法的有效性和优越性,选取隐藏神经元为400个的传统BP神经网络、Softmax分类、KNN分类算法,并使用精确率ACC(accuracy)作为评价指标。实验结果如表1所示。

从表1可以看出,在隐藏层神经元数目相同的情况下,采用Softmax分类方法的性能高于传统BP神经网络10.7个百分点。在确定分类方法后,为验证本文方法的有效性和优越性,实验分别采用下列三种距离度量方法,即:欧氏距离度量(Euclidean Distance)、马氏距离度量(Mahalanobis Distance)、夹角余弦(Cosine)距离度量,与本文的方法进行对比实验,并使用精确率ACC(accuracy)作为评价指标,实验结果如表2所示。

由表2可见,相对于使用单一的距离度量算法,与Softmax分类方法相结合后的性能有显著提高。同时,本文方法在三种组合算法中的性能最优,高于Softmax+Mahalanobis Distance、Softmax+Cosine28个百分点和17个百分点。

4 结语

回归算法 篇7

总体最小二乘[1]认为平差模型中观测向量和系数矩阵同时含有误差, 并对其进行改正。针对系数矩阵含有误差的平差问题, 在理论上总体最小二乘较最小二乘更为严密。总体最小二乘的经典解法是奇异值分解法 (SVD) , 但由于其计算复杂且不利于编程, 测量学者提出了一些基于平差模型的迭代解法[2~7], 并对其实际应用作了一些研究[8~10]。在测量数据处理中, 线性拟合是总体最小二乘一个最重要的应用, 但总体最小二乘的常规解法 (即奇异值分解法和迭代解法) 都无法顾及线性回归中系数矩阵的常数列而是对其进行了改正, 这对线性回归模型来讲是不合理的。文献[5]以直线必须通过数据点的中心, 才能使其偏差最小为约束条件, 推导了一种求解线性模型的总体最小二乘算法, 虽然该算法提高了线性回归的逼近精度, 但仍然存在偏差。文献[7]通过将数据中心化后再采用奇异值分解法对回归参数进行解算, 则分离了系数矩阵的常数列, 得到的参数估值合理可靠。但其缺陷是计算复杂难以编程实现。鉴于此, 本文在基于平差模型的基础上, 推导了一种求解线性回归参数的总体最小二乘算法, 该算法易于编程实现。算例分析表明其可靠、合理。

1 总体最小二乘常规解法

1.1 SVD解法

线性回归模型为[1,2,6]:

式中:Δ观测量y的真误差, ak为回归参数, 当同时考虑到自变量xk也含有误差, 此时系数矩阵A中的元素含有误差, 则式 (2) 变换为总体最小二乘的平差模型:

采用奇异值分解 (SVD) 法将式 (2) 变换为:

求得参数估值为[1,2,6]:

式 (4) 中, n为非固定列对应参数的个数, σ2n+1为增广矩阵[A L]的最小特征值。其单位权中误差计算公式为σ02=σ2n+1/ (m-n-1) , 其中m为观测个数, n+1为参数的个数。

SVD解是将系数矩阵中所有元素看成是含有误差的, 这对线性回归模型来讲是不合理的。而且SVD解法较为复杂, 不利于测量数据处理的编程实现。

1.2 常规迭代解法

总体最小二乘的迭代解法为[2]:

进行迭代解算时, 首先按最小二乘法计算参数的初值X (0) , 然后根据式 (5) 反复迭代直到‖X (i+1) -X (i) ‖<ε则停止计算输出参数值, 单位权中误差按σ0=V/ (m-n) 计算。迭代解法最大的优点是充分运用到测量平差模型, 其迭代格式简单易于编程。但常规的总体最小二乘迭代解法都是将系数矩阵所有元素看成是含误差的, 这对线性回归模型也是不合理的。

2 线性回归参数的总体最小二乘迭代解法

2.1 算法推导

根据前文所述, 有必要建立基于总体最小二乘的线性回归模型和解法, 线性回归数学模型为:

可将式 (6) 进行等价转换为:

表示为矩阵形式为:

设v=vec (EA) , vec表示向量拉直运算, vec (EA) 即将矩阵从左至右逐列拉直成一列向量。在不考虑权重时, 根据总体最小二乘原理, 相应的误差期望和方差为:

式 (9) 中, 为矩阵的克罗内克积, Im和In分别为m和n阶的单位矩阵, 相应的其平差准则为:

根据式 (8) 与式 (10) 构造拉格朗日目标函数:

式 (11) 中, k为 (n+1) ×1的拉格朗日乘数;, In+1为n+1阶的单位矩阵。根据拉格朗日函数求极值的必要条件, 将式 (11) 分别对v、x求导并令其等于0, 化简整理后可得:

由式 (12) 的第一式可得:

式 (13) 中, vec-1表示vec的逆运算, 即将矩阵重新构造为m× (n+1) 的矩阵。

将式 (12) 的第一式代入到式 (8) 中, 并顾及, 整理后可得:

根据式 (11) 第二式和式 (14) 则可得:

根据式 (15) 即可得到参数^x的表达式:

根据上述推导, 其参数解算步骤如下:

(1) 对回归参数附初值^x (0)

(2) 按式 (17) 计算k值和新的回归参数值

(3) 重复步骤 (2) , 直到‖x (i+1) -x (i) ‖<ε, 则停止迭代

按上述迭代方法即可求得式 (7) 的方程, 相应的线性回归方程的参数解:

2.2 单位权中误差评定

根据线性回归模型式 (7) , 当同时考虑自变量误差即采用总体最小二乘求取回归参数值时, 其单位权中误差的计算公式为:

根据上文的迭代解再结合式 (12) 可得:

则按本文的推导, 其单位权中误差计算公式为:

在计算线性回归单位权中误差时, 按常规的总体最小二乘解法算得的结果比按式 (19) 计算的结果要小, 这与实践是不不相符的。因为, 常规的总体最小二乘解法没有顾及线性回归模型中系数矩阵常数列。而本文推导的解法从理论上比常规总体最小二乘解法更严密, 究其原因, 是因为按常规总体最小二乘解法对线性回归模型的单位权中误差评定有误, 下面则具体进行讨论。

按常规总体最小二乘法将线性回归系数矩阵中的常数列也进行了改正并参与精度评定, 其改正后的模型可表示为:

其单位权中误差评定公式为:

从式 (22) 可以看出, 其将常数列的改正值看成是自变量的改正值, 这显然是不对的。从改正模型来看, 应该将常数列的改正值归入到因变量的改正值中, 则变量的改正值为:

按式 (24) 进行改正值修正后, 再按式 (19) 进行单位权中误差的评定。如此得到的结果才与线性回归模型相符。这也解释了前文提出的疑问, 同时也表明不能单一以单位权中误差来评定一种平差模型和算法的优劣。因为它们的单位权中误差评定方式不一定都相同。

3 算例分析

3.1 算例1

运用文献[6]例5~10的数据, 用三个点 (1, 2) 、 (2, 6) 、 (6, 1) 来拟合一元线性回归方程。运用本文的解法得到的参数估值为6、1。这与文献[5]中将数据中心化后再采用奇异值分解法得到的结果相同, 而按常规总体最小二乘的奇异值分解法和迭代解法得到的参数估值皆为6.74、0.99。这是因为总体最小二乘的常规解法将系数矩阵的常数列也进行了改正, 得到的结果有偏差。而本文的解法则将系数矩阵的常数列分离开不加改正, 计算得到的参数估值较之可靠。

3.2 算例2

为进一步验证本文方法对线性回归模型的统一性和可靠性, 运用MATLAB模拟一平面方程。设平面方程为:z=1.5+x+2y, 在x和y没有误差时求得z的值上加上均值为0, 方差为0.005的随机误差, 组成观测值。然后分别对x和y添加均值为0, 方差为0.03的随机误差, 组成新的观测值, 如表1所示。分别采用最小二乘法 (LS) 、常规总最小二乘法、本文解法解算线性回归方程的参数值, 并按文中所述的单位权中误差评定公式计算其单位权中误差, 结果如表2所示。

从表2中的参数估值结果不难看出, 采用本文的总体最小二乘解法解算的回归参数值与真值最为接近, 而常规的总体最小二乘解法由于将线性回归模型中的系数矩阵中的常数列也进行了改正导致其结果与真实值有偏差, 最小二乘法由于没有考虑到线性回归自变量的误差即系数矩阵元素的误差, 计算的结果与真值偏差最大。这也可以从其单位权中误差中得出, 本文的总体最小二乘解法所得单位权中误差最小, 常规总体最小二乘解法次之, 最小二乘法最小。需要指出的是, 如果按常规总体最小二乘的单位权中误差计算公式得到的单位权中误差为0.0227, 比本文方法得到的值要小, 这就会误以为按常规总体最小二乘解法解算线性回归参数得到的精度比本文要高。其实不然, 这是因为其针对线性回归模型的单位权中误差计算公式有误, 通过本文的纠正得出的值才符合其实际。这也可以通过参数的估值结果与真值的比较中看出。

4 结束语

本文给出了一种线性回归参数估计的总体最小二乘算法, 该算法即能同时考虑线性回归自变量的误差即平差模型系数矩阵元素的误差, 又能顾及线性回归中系数矩阵常数列即对常数项不加改正。这弥补了常规总体最小二乘解法针对线性回归模型解算的不足, 且对基于总体最小二乘的线性回归单位权中误差进行了探讨, 纠正了针对线性回归模型的常规总体最小二乘单位权中误差评定的偏颇。

摘要：根据线性回归模型的特点, 推导了一种解线性回归参数的总体最小二乘算法。并对其单位权中误差的评定进行了探讨, 通过理论推导表明按常规的总体最小二乘解法求得的线性回归单位权中误差与实际不符, 并对其进行了纠正。通过算例分析且与常规的总体最小二乘解法进行比较, 结果表明了算法的正确性和可靠性。

关键词：总体最小二乘,线性回归,平差模型,迭代解法,奇异值分解

参考文献

[1]GOLUB G H, VAN L C F.An Analysis of the Total Least Squares Problem[J].SIAM J Numer.Anal, 1980, 17:883~893.

[2]鲁铁定, 周世健.总体最小二乘的迭代解法[J].武汉大学学报 (信息科学版) , 2010, 35 (11) :1351~1354.

[3]孔建, 姚宜斌, 吴寒.整体最小二乘的迭代解法[J].武汉大学学报 (信息科学版) , 2010, 35 (6) :711~714.

[4]许超钤, 姚宜斌, 张豹等.基于整体最小二乘的参数估计新方法及精度评定[J].测绘通报, 2011, (10) :1~4.

[5]邱卫宁, 齐公玉, 田丰瑞.整体最小二乘求解线性模型的改进算法[J].武汉大学学报 (信息科学版) , 2010, 35 (6) 708~710.

[6]丁士俊, 姜卫平, 杨颜梅.整体最小二乘线性回归模型与算法[J].测绘通报, 2012, (12) :8~10.

[7]邱卫宁, 陶本藻, 姚宜斌等.测量数据处理理论与方法[M].武汉:武汉大学出版社, 2008.

[8]陈义, 陆珏, 郑波.总体最小二乘方法在空间后方交会中的应用[J].武汉大学学报 (信息科学版) , 2008, 33 (12) :1271~1274.

[9]陆珏, 陈义, 郑波.总体最小二乘方法在三维坐标转换中的应用[J].大地测量与地球动力学, 2008, 28 (5) :77~81.