一种基于改进网格搜索算法的SVM参数优化方法

摘要

本发明涉及数据挖掘技术领域，具体涉及支持向量机参数优化的一种基于改进网格搜索算法的SVM参数优化方法。本方法初始化分类器和粒子群算法的相关参数，选择对分类器性能影响较大的参数作为待优化参数，由粒子群算法获得全局最优参数或局部最优参数；求得的最优参数作为目标点，初始化网格搜索的空间范围参数和网格搜索过程中的搜索步长参数，以及其他变量；在选定的范围内进行网格搜索，采用k-cv交叉验证，重新获得该范围内的最优参数。本发明改进了传统的网格搜索算法，克服了在选取搜索区间时存在的盲目性以及经验性问题，改善了在数据量较大的情况下该方法存在的时间消耗大的问题，使时间消耗与分类性能达到一个相对平衡的状态。

权利要求

1.一种基于改进网格搜索算法的SVM参数优化方法，其特征在于，包括如下步骤：步骤1：初始化分类器和粒子群算法的相关参数，选择对分类器性能影响较大的参数作为待优化参数，由粒子群算法获得全局最优参数或局部最优参数；

步骤2：将步骤1中求得的最优参数作为目标点，初始化网格搜索的空间范围参数和网格搜索过程中的搜索步长参数，以及其他变量；

步骤3：在步骤2选定的范围内进行网格搜索，采用k-cv交叉验证，重新获得该范围内的最优参数；

步骤4：将重新获得的最优参数和原来的参数进行比较，若两次获得的参数不相等，将重新获得的最优参数作为目标点，将其搜索范围按照规则进行更新作为新的搜索空间:判断是否满足停止条件，若满足条件则结束寻优过程，输出最优参数组合，步骤5：若不满足最优条件，则继续将原来的最优参数作为目标点，在原来的搜索范围基础上按照规则重新扩大搜索范围，同时增大搜索步长，返回步骤3继续迭代寻优，直至满足最优条件。

2.根据权利要求1中所述的一种基于改进网格搜索算法的SVM参数优化方法，其特征在于，所述步骤1中待优化参数包括：高斯核函数g(g＝σ2)和惩罚因子C；所述步骤2中相关的参数包括：参数C的范围区间最小值指数dmin，参数C的范围区间最大值指数dmax，参数g的范围区间最小值指数fmin，参数g的范围区间最大值指数fmax，参数C的搜索步长Cstep，参数g的搜索步长gstep，系数变量M、N与常数L，其中参数的搜索范围存在如下关系：

3.根据权利要求1中所述的一种基于改进网格搜索算法的SVM参数优化方法，其特征在于，所述步骤4中，区间的变化与搜索步长变化的具体方法为：若新求得的最优参数C′best，g′best分别与上一次迭代过程中的参数Cbest，gbest相等，搜索区间的端点值相关参数更新公式及步长更新公式为：C′step＝N×Cstep，g′step＝M×gstep；

其中dmin、dmax是参数C的范围区间相关的指数参数，fmin与fmax是参数g的范围区间相关指数，常数Cstep和gstep是初始化时预设的步长，C′step与g′step是在步骤4中更新的阶段性步长参数，M与N是系统变量且遵循一定的变化规律；

若新求得的最优参数C′best，g′best分别与上一次迭代过程中的参数Cbest，gbest不相等，根据新获得的最优参数与上一次迭代过程中的最优参数的大小关系，搜索区间的端点值相关参数更新公式分别是：当C′best>Cbest时： dmax＝dmax+L；

当C′best

同理，

当g′best>gbest时： fmax＝fmax+L；

当g′best

其中，C′best，g′best是本次迭代过程中新求得的最优参数。

说明书

一种基于改进网格搜索算法的SVM参数优化方法

技术领域

[0001] 本发明涉及数据挖掘技术领域，具体涉及支持向量机参数优化的一种基于改进网格搜索算法的SVM参数优化方法。

背景技术

[0002] 近年来，随着互联网行业的发展，各行各业中积累了大量数字化数据，这些数据中包含着大量的有用信息，从这些海量数据中总结规律，提取出对人类有用的信息已成为数字化时代人们重要的研究内容。

[0003] 而数据分类作为数据挖掘中的一个重要任务或过程，是利用分类算法对已有的带有类别信息的数据进行学习或训练，探求其中的潜在规律，然后利用这种规律对新的未知数据进行类别分析或预测。

[0004] 支持向量机(Support Vector Machine,SVM)作为数据挖掘中应用最为广泛的的分类算法，能够很好地解决非线性、小样本、过学习、维数灾难等问题，它的主要思想是通过寻找不同类别之间的最优分类超平面将数据区分开来，且要满足分类间隔最大。但传统的支持向量机对内部参数的依赖性很强，其中的核参数g与惩罚参数C更是直接决定了支持向量机性能的优劣。所以优化向量机的参数成为了人们研究的重点问题。目前针对参数优化问题，已经提出了多种算法，包括利用网格搜索算法、粒子群算法(Particle swarm optimization,PSO)、遗传算法、蚁群算法等。这些方法在一定程度上提升了SVM的分类性能，但仍存在一定的缺陷。粒子群算法虽然收敛速度快且搜索能力强，但容易出现局部最优的问题；网格搜索算法虽然进行全局搜索保证得到全局最优参数，但搜索速度慢，性能低。因此，本发明提出了一种改进的网格搜索算法，将粒子群算法与网格搜索算法相结合，可以提升算法整体的搜索性能，以较快的速度在合适的时间消耗内找到满足分类准确性要求的最佳参数，使分类性能与时间消耗达到均衡和最佳状态。

[0005] 传统的网格搜索算法中，对于搜索区间的选取带有一定的经验性及盲目性。盲目将搜索区间选的过大，在数据量很大的情况下将以大量的时间消耗为代价，无法满足时间性能上的要求；而将区间选的过小，将造成无法寻得最优参数，无法满足分类准确性上的性能要求。而根据合适的区间选取搜索范围带有一定的经验性和针对性，无法满足大多数情况下网格寻优的区间范围选择。并且，大小范围不同的搜索区间对应的搜索步长大小也将影响最优参数的选择以及时间的消耗。

[0006] 处于对时间性能以及分类性能的双重考虑，本发明改进的网格搜索算法在搜索区间的选择上摆脱了经验性与盲目性的困扰。根据已有的粒子群算法，以其计算得到的局部最优或全局最优参数为搜索区间的中心点，根据一定的规则不断更新网格搜索的范围，从小区间到大区间逐步搜索，既克服了局部最优的缺点，也避免了全局大面积搜索带来的时间消耗，最终找到满足时间性能与分类性能的最佳参数组合。

发明内容

[0007] 本发明的目的在于提供一种基于改进网格搜索算法的SVM参数优化方法。

[0008] 本发明的目的是这样实现的：

[0009] 一种基于改进网格搜索算法的SVM参数优化方法，包括如下步骤：

[0010] 步骤1：初始化分类器和粒子群算法的相关参数，选择对分类器性能影响较大的参数作为待优化参数，由粒子群算法获得全局最优参数或局部最优参数；

[0011] 步骤2：将步骤1中求得的最优参数作为目标点，初始化网格搜索的空间范围参数和网格搜索过程中的搜索步长参数，以及其他变量；

[0012] 步骤3：在步骤2选定的范围内进行网格搜索，采用k-cv交叉验证，重新获得该范围内的最优参数；

[0013] 步骤4：将重新获得的最优参数和原来的参数进行比较，若两次获得的参数不相等，将重新获得的最优参数作为目标点，将其搜索范围按照规则进行更新作为新的搜索空间:判断是否满足停止条件，若满足条件则结束寻优过程，输出最优参数组合，[0014] 步骤5：若不满足最优条件，则继续将原来的最优参数作为目标点，在原来的搜索范围基础上按照规则重新扩大搜索范围，同时增大搜索步长，返回步骤3继续迭代寻优，直至满足最优条件。

[0015] 所述步骤1中待优化参数包括：高斯核函数g(g＝σ2)和惩罚因子C；所述步骤2中相关的参数包括：参数C的范围区间最小值指数dmin，参数C的范围区间最大值指数dmax，参数g的范围区间最小值指数fmin，参数g的范围区间最大值指数fmax，参数C的搜索步长Cstep，参数g的搜索步长gstep，系数变量M、N与常数L，其中参数的搜索范围存在如下关系：

[0016] 所述步骤4中，区间的变化与搜索步长变化的具体方法为：若新求得的最优参数C′best，g′best分别与上一次迭代过程中的参数Cbest，gbest相等，搜索区间的端点值相关参数更新公式及步长更新公式为：

[0017]

[0018]

[0019] C′step＝N×Cstep，g′step＝M×gstep；

[0020] 其中dmin、dmax是参数C的范围区间相关的指数参数，fmin与fmax是参数g的范围区间相关指数，常数Cstep和gstep是初始化时预设的步长，C′step与g′step是在步骤4中更新的阶段性步长参数，M与N是系统变量且遵循一定的变化规律；

[0021] 若新求得的最优参数C′best，g′best分别与上一次迭代过程中的参数Cbest，gbest不相等，根据新获得的最优参数与上一次迭代过程中的最优参数的大小关系，搜索区间的端点值相关参数更新公式分别是：

[0022] 当C′best>Cbest时： dmax＝dmax+L；

[0023] 当C′best

[0024] 同理，

[0025] 当g′best>gbest时： fmax＝fmax+L；

[0026] 当g′best

[0027] 其中，C′best，g′best是本次迭代过程中新求得的最优参数。

[0028] 本发明的有益效果在于：1.本发明改进了传统的网格搜索算法，克服了在选取搜索区间时存在的盲目性以及经验性问题，改善了在数据量较大的情况下该方法存在的时间消耗大的问题，使时间消耗与分类性能达到一个相对平衡的状态；2.优化之后的分类器可以有效提升分类器的综合性能和泛化能力。

附图说明

[0029] 图1是基于改进的网格搜索算法的SVM参数优化方法总流程图；

[0030] 图2是基于改进的网格搜索算法的SVM参数优化方法详细流程图。

具体实施方式

[0031] 下面结合附图对本发明做进一步描述。

[0032] 附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施一起用于解释本发明，并不构成对本发明的限制。

[0033] 本发明涉及数据挖掘技术领域，具体涉及支持向量机参数优化以及一种改进的网格搜索算法。

[0034] 本发明利用改进的网格搜索算法，并结合粒子群算法相关操作，可以自适应调整网格搜索的区间范围以及搜索步长，提升网格搜索算法的寻优效率。以下结合附图对本发明的具体实施说明如下。

[0035] 基于改进网格搜索算法的SVM参数优化的方法，包括如下几个步骤：

[0036] 步骤1：该方法首先将惩罚因子C和高斯核函数g作为待优化参数，通过粒子群算法，得到初始优化参数(Cpso,gpso)。其中，粒子群算法的标准算法形式如下所示：

[0037] vi＝w×vi+c1×rand()×(Pid(t)-xi)+c2×rand()×(Pgd(t)-xi)；

[0038] xi＝xi+vi。

[0039] 其中，w为惯性因子，c1与c2称为加速常数，一般取c1＝c2∈[0,4]，rand()表示[0,1]上的随机数。vi是粒子速度，xi表示粒子当前位置，Pid(t)代表第i个粒子在t轮迭代时个体最优位置的第d维度值，Pgd(t)代表第t轮时的种群最优位置的第d维值，其中，参数C、g作为粒子的相应维度值。

[0040] 粒子群算法通过以上两个公式，最终计算出局部最优参数组合或全局最优参数组合。因为无法保证参数的全局最优性，所以需要采用改进的网格搜索算法进行进一步计算。

[0041] 步骤2：对参数进行初始化，具体包括：以(Cpso,gpso)作为目标点，初始化常数L，Cstep以及gstep，初始化系统变量M＝1,N＝1，其他参数初始化如下所示：

[0042] 区间最优参数初始化：(Cbest,gbest)＝(Cpso,gpso)；

[0043] 搜索步长初始化：C′step＝Cstep，g′step＝gstep；

[0044] 搜索区间端点参数初始化：

[0045]

[0046]

[0047] 其中，搜索范围满足

[0048] 步骤3：采用k-cv交叉验证，根据步骤2中提供的区间范围进行网格搜索，搜索步长分别为C′step和g′step。最终通过计算获得本次迭代该区间内的最优参数(C′best,g′best)。

[0049] 步骤4：判断是否满足算法结束条件，若满足则输出最优参数组合,结束寻优；否则，转向步骤5；

[0050] 步骤5：分别比较C′best与Cbest，g′best与gbest的大小关系，根据他们的大小关系更新相关参数：

[0051] 若C′best>Cbest：

[0052] 系统变量更新：N＝0；

[0053] 范围区间端点参数更新： dmax＝dmax+L；

[0054] 搜索步长更新：C′step＝Cstep；

[0055] 最优参数目标值更新：Cbest＝C′best；

[0056] 若C′best＝Cbest：

[0057] 系统变量更新：N＝N+1；

[0058] 范围区间端点参数更新：

[0059] 搜索步长更新：C′step＝N×Cstep；

[0060] 若C′best

[0061] 系统变量更新：N＝0；

[0062] 范围区间端点参数更新：dmin＝dmin-L，

[0063] 搜索步长更新：C′step＝Cstep；

[0064] 最优参数目标值更新：Cbest＝C′best；

[0065] 同理，对于参数g：

[0066] 若g′best>gbest：

[0067] 系统变量更新：M＝0；

[0068] 范围区间端点参数更新： fmax＝fmax+L；

[0069] 搜索步长更新：g′step＝gstep；

[0070] 最优参数目标值更新：gbest＝g′best；

[0071] 若g′best＝gbest：

[0072] 系统变量更新：M＝M+1；

[0073] 范围区间端点参数更新：

[0074] 搜索步长更新：g′step＝M×gstep；

[0075] 若g′best

[0076] 系统变量更新：M＝0；

[0077] 范围区间端点参数更新：fmin＝fmin-L，

[0078] 搜索步长更新：g′step＝gstep；

[0079] 最优参数目标值更新：gbest＝g′best；

[0080] 其中，C′best与g′best是当前求得的最优参数，Cbest与gbest是上次迭代过程中获得的最优参数。当两次搜索得到的最优参数保持不变时，需要加大搜索空间；当参数发生变化时，以新获得的最优参数作为目标点重新确定搜索范围。需要注意的是，相关参数之间互有联系，更新的顺序需严格按照以上描述进行更新。

[0081] 步骤6：获得参数C，g的寻优区间的相关参数，回到步骤3进行迭代寻优。

[0082] 在步骤4中，对于算法终止条件的设置，通常需要根据实际需要选择。可以将实际的分类模型中的准确率作为终止条件，也可以根据实际需要，当获得的最优参数组合多次不再发生变化证明已达到全局最优，可以停止寻优。

[0083] 本发明提供了一种基于改进的网格搜索算法的SVM分类器参数优化方法，目的在于克服现有技术中存在的局部最优与大量的时间消耗问题，可以有效提升分类器的综合性能和泛化能力。

[0084] 本发明所提供的基于改进的网格搜索算法的SVM分类器参数优化方法，该方法包括以下步骤：

[0085] (1)初始化分类器和粒子群算法的相关参数，选择对分类器性能影响较大的参数作为待优化参数，由粒子群算法获得全局最优参数或局部最优参数；

[0086] (2)将步骤(1)中求得的最优参数作为目标点，初始化网格搜索的空间范围参数和网格搜索过程中的搜索步长参数，以及其他变量。

[0087] (3)在步骤(2)选定的范围内进行网格搜索，采用k-cv交叉验证，重新获得该范围内的最优参数；

[0088] (4)将重新获得的最优参数和原来的参数进行比较，若两次获得的参数不相等，将重新获得的最优参数作为目标点，将其搜索范围按照规则进行更新作为新的搜索空间，返回步骤(3)继续迭代寻优；否则，判断是否满足停止条件，若满足条件则结束寻优过程，输出最优参数组合，否则继续将原来的最优参数作为目标点，在原来的搜索范围基础上按照规则重新扩大搜索范围，同时增大搜索步长，返回步骤(3)继续迭代寻优。

[0089] 优选的，所述步骤(1)中待优化参数包括：

[0090] 高斯核函数g(g＝σ2)和惩罚因子C。

[0091] 优选的，所述步骤(2)中相关的参数包括：

[0092] 参数C的范围区间最小值指数dmin，参数C的范围区间最大值指数dmax，参数g的范围区间最小值指数fmin，参数g的范围区间最大值指数fmax，参数C的搜索步长Cstep，参数g的搜索步长gstep，系数变量M、N与常数L。其中参数的搜索范围存在如下关系：

[0093] 优选的，所述步骤(4)中，区间的变化与搜索步长变化的具体方法为：

[0094] 若新求得的最优参数C′best，g′best分别与上一次迭代过程中的参数Cbest，gbest相等，搜索区间的端点值相关参数更新公式及步长更新公式为：

[0095]

[0096]

[0097] C′step＝N×Cstep，g′step＝M×gstep；

[0098] 其中dmin、dmax是参数C的范围区间相关的指数参数，fmin与fmax是参数g的范围区间相关指数，常数Cstep和gstep是初始化时预设的步长，C′step与g′step是在步骤(4)中更新的阶段性步长参数，M与N是系统变量且遵循一定的变化规律。

[0099] 若新求得的最优参数C′best，g′best分别与上一次迭代过程中的参数Cbest，gbest不相等，根据新获得的最优参数与上一次迭代过程中的最优参数的大小关系，搜索区间的端点值相关参数更新公式分别是：

[0100] 当C′best>Cbest时： dmax＝dmax+L；

[0101] 当C′best

[0102] 同理，

[0103] 当g′best>gbest时： fmax＝fmax+L；

[0104] 当g′best

[0105] 其中，C′best，g′best是本次迭代过程中新求得的最优参数。