一种基于梯度下降法的多视图GEPSVM网页分类算法

摘要

本发明提出了一种基于梯度下降法的多视图GEPSVM网页分类算法,包括MvGDSVM网页分类模型参数训练步骤和网页数据分类步骤；MvGDSVM网页分类模型参数训练步骤包括：步骤A：输入网页训练样本数据；步骤B：对网页训练样本数据进行预处理；步骤C：训练MvGDSVM网页分类模型参数；网页数据分类步骤包括：步骤a：输入待测网页样本数据；步骤b：对待测网页样本数据进行标准化预处理；步骤c：通过MvGDSVM网页分类模型对待测网页样本数据进行分类。本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法，通过引入一个多视图协同规范化项来最大化不同视图间分类的一致性，从而有效地结合了两个单视图的提高性的广义特征值最接近支持向量机，最后利用共轭梯度下降法来求解生成的优化问题。

说明书

技术领域

本发明涉及网页分类技术领域，尤其涉及一种基于梯度下降法的多视图GEPSVM网页分类算法(简称MvGDSVM网页分类算法)。

背景技术

近年来，随着互联网的普及，网络信息呈指数级增长，它已经成为人们获取信息的重要手段。面对海量而又内容复杂的网络信息，很多时候无法准确定位自己想要的信息，而通过网页的分类，可以从海量的网络信息中迅速、准确的获取用户感兴趣的信息。

目前，现有的广义特征值最接近支持向量机(Generalized eigenvalue proximalsupport vector machine，GEPSVM)以及提高性的广义特征值最接近支持向量机(Improvedgeneralized eigenvalue proximal support vector machine，IGEPSVM)都是简单有效的分类方法。

1.广义特征值最接近支持向量机

a)线性的GEPSVM

广义特征值最接近支持向量机是监督学习中一种简单且有效的二分类方法，利用两个超平面来对数据点进行分类。其中每一个超平面离两类数据的其中一类尽量近，离另外一类尽量远。广义特征值最接近支持向量机通过解一对广义特征值问题来获得这两个非平行的超平面。

假设在实空间R^d中，有n个标签为y_i(i＝1,2,...,n)∈{+1,-1}的样本点。其中，矩阵表示属于+1类的样本在第一个视图上的特征，矩阵表示属于-1类的样本在第二个视图上的特征(n₁+n₂＝n)。

在实空间R^d中定义两个超平面：

GEPSVM在最接近超平面上摒弃了标准的SVM中两个超平面平行的条件，而要求：第一个超平面离类+1的样本点尽可能近，离类-1的样本点尽可能远；第二个超平面离类-1的样本点尽可能近，离类+1的样本点尽可能远。GEPSVM的决策目标产生了如下一对优化问题：

$>\underset{(w_1,{\gamma }_1)\ne 0}{min}\frac{\left|\right|{\mathrm{Aw}}_1+{\mathrm{e\gamma }}_1|{|}^2/|\left|\left(\begin{array}{c}{w}_1\\ {\gamma }_1\end{array}\right)\right|{|}^2}{\left|\right|{\mathrm{Bw}}_1+{\mathrm{e\gamma }}_1|{|}^2/|\left|\left(\begin{array}{c}{w}_1\\ {\gamma }_1\end{array}\right)\right|{|}^2}---\left(2\right)$>

和

$>\underset{(w_2,{\gamma }_2)\ne 0}{min}\frac{\left|\right|{\mathrm{Bw}}_2+{\mathrm{e\gamma }}_2|{|}^2/|\left|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)\right|{|}^2}{\left|\right|{\mathrm{Aw}}_2+{\mathrm{e\gamma }}_2|{|}^2/|\left|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)\right|{|}^2},---\left(3\right)$>

其中||.||表示2-范数。以上的两个优化问题可以被简化成：

$>\underset{(w_1,{\gamma }_1)\ne 0}{min}\frac{\left|\right|{\mathrm{Aw}}_1+{\mathrm{e\gamma }}_1|{|}^2}{\left|\right|{\mathrm{Bw}}_1+{\mathrm{e\gamma }}_1|{|}^2}---\left(4\right)$>

和

$>\underset{(w_2,{\gamma }_2)\ne 0}{min}\frac{\left|\right|{\mathrm{Bw}}_2+{\mathrm{e\gamma }}_2|{|}^2}{\left|\right|{\mathrm{Aw}}_2+{\mathrm{e\gamma }}_2|{|}^2}.---\left(5\right)$>

引入一个Tikhonov规范化项，(4)和(5)可以被规范化成：

$>\underset{(w_1,{\gamma }_1)\ne 0}{min}\frac{\left|\right|{\mathrm{Aw}}_1+{\mathrm{e\gamma }}_1|{|}^2+ϵ|\left|\left(\begin{array}{c}{w}_1\\ {\gamma }_1\end{array}\right)\right|{|}^2}{\left|\right|{\mathrm{Bw}}_1+{\mathrm{e\gamma }}_1|{|}^2}---\left(6\right)$>

和

$>\underset{(w_2,{\gamma }_2)\ne 0}{min}\frac{\left|\right|{\mathrm{Bw}}_2+{\mathrm{e\gamma }}_2|{|}^2+ϵ|\left|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)\right|{|}^2}{\left|\right|{\mathrm{Aw}}_2+{\mathrm{e\gamma }}_2|{|}^2},---\left(7\right)$>

其中ε是个非负的权重系数。

做出如下定义：

其中G和H是两个在R^(d+1)×(d+1)上的对称矩阵，z₁和z₂是两个在R^d+1的超平面参数。那么优化问题(6)和(7)可以简写成：

和

上面的优化问题(9)和(10)是完全瑞利商的，所以它们的全局最优解可以通过求解以下相关的广义特征值问题得到

(G+εI)z₁＝λHz₁,z₁≠0>

和

(H+εI)z₂＝λGz₂,z₂≠0.>

第一个和第二个最优接近超平面分别是广义特征值问题(11)和(12)对于最小特征值相对应的特征向量。

显然，对于一个测试样本x，线性的GEPSVM的预测函数是

其中|.|是个绝对值函数，表示x到第一个分类超平面的垂直距离，表示x到第二个分类超平面的垂直距离。这个预测函数表明如果样本x离第一个分类超平面比较近，它就被分到类+1，否则它被分到类-1。

b)核方法的GEPSVM

线性的GEPSVM可以通过核方法来泛化到非线性的情况。考虑一下两个核生成的超平面代替平面(1)：

其中K是个核函数。在本文中，主要考虑常用的高斯核(Gaussiankernel)，它的第ij(i＝1,2,...,n₁,j＝1,2,...,n)个元素如下给出：

其中μ是个高斯核参数。注意到其实平面(1)是一个(14)的特殊情况：假设使用一个线性核然后让

后面训练得到两个超平面的过程与线性的GEPSVM的训练过程形式相同。

对于一个测试样本x，核的GEPSVM的预测函数是

其中表示x到第一个基于核的分类超平面的距离，表示x到第二个基于核的分类超平面的距离。这个预测函数表明如果样本x离第一个分类超平面比较近，它就被分到类+1，否则它被分到类-1。

2.提高性的广义特征值最接近支持向量机

a)线性的IGEPSVM

GEPSVM的决策目标产生了如下一对优化问题：

$>\underset{(w_1,{\gamma }_1)\ne 0}{min}\frac{\left|\right|{\mathrm{Aw}}_1+{\mathrm{e\gamma }}_1|{|}^2/|\left|\left(\begin{array}{c}{w}_1\\ {\gamma }_1\end{array}\right)\right|{|}^2}{\left|\right|{\mathrm{Bw}}_1+{\mathrm{e\gamma }}_1|{|}^2/|\left|\left(\begin{array}{c}{w}_1\\ {\gamma }_1\end{array}\right)\right|{|}^2}---\left(17\right)$>

和

$>\underset{(w_2,{\gamma }_2)\ne 0}{min}\frac{\left|\right|{\mathrm{Bw}}_2+{\mathrm{e\gamma }}_2|{|}^2/|\left|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)\right|{|}^2}{\left|\right|{\mathrm{Aw}}_2+{\mathrm{e\gamma }}_2|{|}^2/|\left|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)\right|{|}^2},---\left(18\right)$>

其中||.||表示2-范数。

GEPSVM在广义特征值分解时会产生奇异值问题，为了克服这个缺陷，IGEPSVM使用减来代替GEPSVM中的除来衡量两类样本到分类超平面之间的距离差。那么优化问题(17)和(18)可以被转化成：

$>\underset{(w_1,{\gamma }_1)\ne 0}{min}\frac{\left|\right|{\mathrm{Aw}}_1+{\mathrm{e\gamma }}_1|{|}^2}{\left|\right|\left(\begin{array}{c}{w}_1\\ {\gamma }_0\end{array}\right)|{|}^2}-v\frac{\left|\right|{\mathrm{Bw}}_1+{\mathrm{e\gamma }}_1|{|}^2}{\left|\right|\left(\begin{array}{c}{w}_1\\ {\gamma }_1\end{array}\right)|{|}^2},---\left(19\right)$>

和

$>\underset{(w_2,{\gamma }_2)\ne 0}{min}\frac{\left|\right|{\mathrm{Bw}}_2+{\mathrm{e\gamma }}_2|{|}^2}{\left|\right|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)|{|}^2}-v\frac{\left|\right|{\mathrm{Aw}}_2+{\mathrm{e\gamma }}_2|{|}^2}{\left|\right|\left(\begin{array}{c}{w}_2\\ {\gamma }_2\end{array}\right)|{|}^2},---\left(20\right)$>

其中ν是个权重系数。为了消去超平面变量(w_i,γ_i)(i＝1,2)的范数，引入一个Tikhonov规范化项。然后通过如下的定义：

然后优化问题(19)和(20)可以被规范化成：

和

以上的两个优化问题是完全瑞利商的。式(21)的拉格朗日函数可以写成：

其中λ₁和λ₂是拉格朗日乘子。令式(23)关于变量(z₁,α₁)求偏导后的值为零，得到以下等式

2(G+εI-νH)z₁-2λ₁z＝0.

所以优化问题(21)的全局最优解可以通过求解下面的特征值问题求得

(G+εI-νH)z₁＝λ₁z₁.(24)

相似的，优化问题(22)的全局最优解可以通过下面的特征值问题求得

(H+εI-νG)z₂＝λ₁z₂.(25)

第一个和第二个最优接近超平面分别是特征值问题(24)和(25)对于最小特征值对应的特征向量。

显然，对于一个测试样本x，线性的IGEPSVM的预测函数是

b)核的IGEPSVM

线性的IGEPSVM可以通过核方法来泛化到非线性的情况。考虑一下两个核生成的超平面代替平面(1)：

其中K是之前提到的核函数。

后面的训练过程与线性的IGEPSVM的训练过程形式相同。而核的IGEPSVM的预测准则和核的GEPSVM相同。

但目前，现有的不管是广义特征值最接近支持向量机，还是提高性的广义特征值最接近支持向量在网页分类的应用都不是很广泛。因为这两个算法都是单视图的分类算法，有着一定的局限性。它们都不能充分利用网页的多个视图上的特征信息，在网页上的分类精度还有提高的空间。

发明内容

本发明提出一种多视图GEPSVM算法用于网页分类，能够充分利用网页的多个视图信息，来提高分类性能。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，包括MvGDSVM网页分类模型参数训练步骤和网页数据分类步骤；

所述MvGDSVM网页分类模型参数训练步骤包括：

步骤A：输入网页训练样本数据；

步骤B：对所述网页训练样本数据进行预处理；

步骤C：训练MvGDSVM网页分类模型参数；

所述网页数据分类步骤包括：

步骤a：输入待测网页样本数据；

步骤b：对所述待测网页样本数据进行标准化预处理；

步骤c：通过MvGDSVM网页分类模型对所述待测网页样本数据进行分类。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述步骤B中的预处理包括：

步骤B1：确定所述网页训练样本数据每个视图上的特征向量；

步骤B2：对所有所述网页训练样本数据的每个视图上的特征向量分别作标准化处理。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述步骤C中，通过多视图协同规范化项来最大化不同视图间分类的一致性。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述步骤C包括：

步骤C1：在每个视图上最大化两类样本与超平面之间的距离差，同时最小化在同一个网页训练样本上两个假设函数作用在不同视图上的结果；

步骤C2：使用共轭梯度下降法优化目标函数，给出目标函数的梯度。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述步骤C进一步包括：

步骤C3：利用MvGDSVM求得分类超平面参数；

步骤C4：分别计算每个视图上网页训练样本到两个超平面的垂直距离，得到决策函数的预测结果。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述步骤b中标准化预处理包括：

步骤b1：确定待测网页样本数据每个视图上的特征向量；

步骤b2：对所有待测网页网页数据的每个视图上的特征向量分别作标准化处理。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述步骤c中对所述待测网页数据进行分类包括：

步骤c1：利用训练样本数据得到的MvGDSVM分类模型的最佳参数，分别计算每个视图上样本到两个超平面的垂直距离；

步骤c2：利用训练时得到的最佳预测函数来对待测网页样本数据进行分类。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，线性的MvGDSVM中，每个视图上网页样本到两个超平面的垂直距离如下式：

其中，view 1和view 2分别表示第一个视图和第二个视图；dist11表示网页样本数据在第一个视图上到第一个超平面的垂直距离，dist12表示网页样本数据在第一个视图上到第二个超平面的垂直距离；dist21表示网页样本数据在第二个视图上到第一个超平面的垂直距离，dist22表示网页样本数据在第二个视图上到第二个超平面的垂直距离；x₁表示网页样本数据第一个视图上的特征向量，x₂表示网页样本数据第二个视图上的特征向量；第一个视图的第一个超平面参数表示为(w₁,γ₁)，第二个超平面参数表示为(u₁,ζ₁)；第二个视图的第一个超平面参数表示为(w₂,γ₂)，第二个超平面参数表示为(u₂,ζ₂)。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，核的MvGDSVM中，每个视图上网页样本到两个超平面的距离如下式：

其中，矩阵表示第一类网页样本数据在第一个视图上的特征；矩阵表示第一类网页样本数据在第二个视图上的特征；矩阵表示第二类网页样本数据在第一个视图上的特征；矩阵表示第二类网页样本数据在第二个视图上的特征；K为核函数。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法中，所述决策函数的预测结果如下式：

$>\widehat{y_1}=sign(dist12-dist11),$>

$>\widehat{y_2}=sign(dist22-dist21),$>

$>\hat{y}=sign(dist12+dist22-dist11-dist21);$>

其中，为第一个视图上的决策函数的预测结果；是第二个视图上的决策函数的预测结果；是结合两个视图的决策函数的预测结果。

本发明提出的基于梯度下降法的多视图GEPSVM网页分类算法，通过引入一个多视图协同规范化项来最大化不同视图间分类的一致性，从而有效地结合了两个单视图的提高性的广义特征值最接近支持向量机(IGEPSVM)。最后利用共轭梯度下降法来求解生成的优化问题。

附图说明

图1为本发明基于梯度下降法的多视图GEPSVM网页分类算法的流程框架图。

具体实施方式

结合以下具体实施例和附图，对发明作进一步的详细说明。实施本发明的过程、条件、实验方法等，除以下专门提及的内容之外，均为本领域的普遍知识和公知常识，本发明没有特别限制内容。

本发明提出了一种基于梯度下降法的多视图GEPSVM网页分类算法，包括MvGDSVM网页分类模型参数训练步骤和网页数据分类步骤。

本发明中，MvGDSVM网页分类模型参数训练步骤包括：

步骤A：输入网页训练样本数据；

步骤B：对所述网页训练样本数据进行预处理；

步骤C：训练MvGDSVM网页分类模型参数；

本发明中，所述网页数据分类步骤包括：

步骤a：输入待测网页样本数据；

步骤b：对所述待测网页样本数据进行标准化预处理；

步骤c：通过MvGDSVM网页分类模型对所述待测网页样本数据进行分类。

本发明提出的MvGDSVM网页分类算法，分为线性和非线性的两种情况：1.线性的MvGDSVM

考虑一个网页数据的二分类问题，给定n个标签为y_i(i＝1,2,...,n)∈{+1,-1}的网页样本点。对网页训练样本数据预处理后，得到所有网页训练样本的在每个视图上的特征向量。其中矩阵表示属于类+1的样本点在第一个视图上的特征，矩阵表示属于类+1的样本点在第二个视图上的特征。矩阵表示属于类-1的样本点在第一个视图上的特征，矩阵表示属于类-1的样本点在第二个视图上的特征。显然，n₁+n₂＝n。

对于每个视图，分别给出如下两个超平面的定义：

其中x₁(x₂)表示x的第一个(第二个)视图的特征。

本发明给出如下定义：

其中，G₁和H₁是在上的对称矩阵，G₂和H₂是在上的对称矩阵。z₁和p₁是两个在的超平面参数，z₂和p₂是两个在上的超平面参数。

为了结合两个视图的特征，引入如下的多视图协同规范化项：

$>\left|\right|M_{A_1}{z}_1-M_{A_2}{z}_2|{|}^2.$>

通过结合两个单视图的IGEPSVM，本发明给出MvGDSVM的第一个优化问题：

其中ν，δ是非负的权重参数。

上面的优化问题的目标函数可以被理解成：在每个视图上最大化两类样本与超平面之间的距离差，与此同时最小化在同一个训练样本上两个函数和作用在不同视图上的结果。

上面的优化问题(28)可以被简化成：

本发明中，使用共轭梯度下降法去优化目标函数F₁(z₁,z₂)，然后分别给出目标函数关于z₁和z₂的梯度

对于一个非凸函数，梯度下降法求得的是局部最优解。所以它不能确保得到优化问题(29)的最优解。为了较好的分类超平面，选择三组不同z₁,z₂的初始值来对优化问题(29)进行梯度下降：

1.z₁和z₂分别通过单视图的IGEPSVM求得。

2.z₁和z₂分别是对应维度的单位列向量。

3.z₁和z₂分别是对应维度的列向量，它们的每个元素都是在[-1，1]之间取值的随机数。

第一组初始值作为基本参照，它能够确保采用的初始化策略对目标函数(29)进行梯度下降后求得的局部最优解肯定优于z₁和z₂分别是两个单视图的IGEPSVM的最优分类平面的参数的情况。它表明在理论上本发明提出的多视图方法与对应的单视图方法相比是更加有效的。

相同地，通过引入另外一个多视图协同规范化项

$>\left|\right|M_{B_1}{p}_1-M_{B_2}{p}_2|{|}^2,$>

本发明给出MvGDSVM的第二个优化问题：

它可以被简化成：

本发明用共轭梯度下降法并采用上面的初始化策略去优化目标函数F₂(p₁,p₂)，然后分别给出目标函数式(31)关于p₁和p₂的梯度

现在利用线性的MvGDSVM求得需要的分类超平面参数：第一个视图的第一个超平面参数(w₁,γ₁)和第二个超平面参数(u₁,ζ₁)，以及第二个视图的第一个超平面参数(w₂,γ₂)和第二个超平面参数(u₂,ζ₂)。对于一个网页待测样本x，首先对其每个视图上的特征向量分别作标准化处理，然后分别计算每个视图上x到两个超平面的垂直距离：

然后本发明给出三种不同的决策函数：

$>\begin{array}{c}\widehat{y_1}=sign\left(dist12-dist11\right),\\ \widehat{y_2}=sign\left(dist22-dist21\right),\\ \hat{y}=sign\left(dist12+dist22-dist11-dist21\right),\end{array}---\left(33\right)$>

其中和分别是第一个视图上和第二个视图上的决策函数的预测结果，是结合两个视图的决策函数的预测结果。

2.核的MvGDSVM

对于非线性的情况，引入核生成的超平面。对于每一个视图上的两个超平面，做出如下定义：

其中K是上文中提及的核函数.

首先给出如下定义：

其中G₁，H₁，G₂和H₂是在R^(n+1)×(n+1)上的对称矩阵，z₁，p₁，z₂，p₂是在Rⁿ⁺¹上的超平面参数。

在核的MvGDSVM中，为了结合两个视图的特征，引入如下的多视图协同规范化项

$>\left|\right|M_{A_1}{z}_1-M_{A_2}{z}_2|{|}^2.$>

然后通过结合两个单视图的IGEPSVM，本发明给出核的MvGDSVM的第一个优化问题：

其中ν是个非负的权重参数。上面的优化问题(34)可以被简化成

同样地，利用共轭梯度下降法并采用上面的初始化策略去优化目标函数F₁(z₁,z₂)，然后分别给出目标函数式(35)关于z₁和z₂的梯度：

相同地，通过引入另外一个多视图协同规范化项：

$>\left|\right|M_{B_1}{p}_1-M_{B_2}{p}_2|{|}^2,$>

本发明给出核的MvGDSVM的第二个优化问题

它可以被简化成：

用共轭梯度下降法并采用上面的初始化策略去优化目标函数F₂(p₁,p₂)，然后分别给出目标函数式(37)关于p₁和p₂的梯度

对于核的MvGDSVM来说，决策函数和在线性的MvGDSVM中的式(33)是完全相同，但是对点到超平面的距离的定义是不同于式(32)的.对于一个网页待测样本x，首先对其每个视图上的特征向量分别作标准化处理，然后分别计算每个视图上x到两个超平面的距离：

通过在一个真实的网页数据集上的例子来说明本发明的具体实施方法和验证本发明算法的效果。网页分类数据集是从Cornell University，University of Washington，University of Wisconsin，and University of Texas这四所美国大学计算机系网站上收集而来的拥有两个视图的网页构成的，其中一个视图是网页本身的单词特性，另一个视图是指向此网页的超链接上的单词特性。这两个视图的维度分别是500和87。这个数据集一共有1051个样本，其中有关课程的网页230个，无关课程的网页821个。随机选择了500个样本来验证本发明MvGDSVM算法的分类性能。

对于这500个网页样本，首先把它们划分成训练样本数据和测试样本数据。通过在训练样本数据上利用网格搜索的5-fold交叉验证得到的平均验证准确率，选取出最佳的模型参数。对于MvGDSVM方法，除了复合决策函数，也考虑来自各个视图的决策函数，其中最大验证准确率的决策函数将被采用的，见式(33)。当最佳的模型参数和决策函数都选择好后，将会评估所有的方法在测试集上的性能。上面的过程随机重复5次，然后通过平均正确率和对应的标准差来展示所有方法的分类性能。下图是MvGDSVM以及对比算法的平均分类准确率和标准差。其中IGEPSVM1，IGEPSVM2和IGEPSVM3是单视图的IGEPSVM算法，前两者分别作用在第一个视图和第二个视图的特征向量上。而IGEPSVM3把两个视图的特征向量连接起来作为一个视图。从图中可以看出本发明的MvGDSVM算法与对应的单视图方法相比，有很好的性能提高。与另外一个经典的多视图学习方法SVM-2K相比，本发明的算法不管在准确率和稳定性上都表现得较好。这说明本发明的多视图学习算法MvGDSVM在网页分类上是完全有效的。

算法IGEPSVM1IGEPSVM2IGEPSVM3MvGDSVMSVM-2K准确率(％)78.4(5.81)88.6(3.13)78.6(5.59)89.80(3.49)89.20(4.66)

本发明的保护内容不局限于以上实施例。在不背离发明构思的精神和范围下，本领域技术人员能够想到的变化和优点都被包括在本发明中，并且以所附的权利要求书为保护范围。