第３９卷第３期 ２０１２年６月 应 用 科 技 、，０ｌＩ３９．ＮＯ－３ Ｊｕｎ．２０１２ Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００９・６７１Ｘ．２０１ １ １２０１６ 基于改进的网格搜索法的ＳＶＭ参数优化 王健峰，张磊，陈国兴，何学文 哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨１５０００１ 摘要：比较了现今应用比较广泛的３种支持向量机（ＳＶＭ）参数优化方法．具体分析了网格法、遗传算法和粒子群算 法在ＳＶＭ参数优化方面的性能以及优缺点，提出了一种改进的网格法．先在较大范围内进行搜索，在得到的优化结果 附近区域再进行精确搜索．实验表明改进的网格搜索法耗时短，更适用于有时问要求的说话人识别应用中． 关键词：支持向量机；参数优化；网格搜索；遗传算法；粒子群算法；说话人识别 中图分类号：ＴＰ２７３ 文献标志码：Ａ 文章编号：１００９—６７１Ｘ（２０１２）０３—００２８．０４ Ａ ｐａｒａｍｅｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ａｎ ＳＶＭ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｇｒｉｄ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ＷＡＮＧ Ｊｉａｎｆｅｎｇ，ＺＨＡＮＧ Ｌｅｉ，ＣＨＥＮ Ｇｕｏｘｉｎｇ，ＨＥ Ｘｕｅｗｅｎ Ｃｏｌｌｅｇｅ ｏｆＩｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ １５０００１，Ｃｈｉｎａ Ａｂｓｔｒａｃｔ：Ｔｈｒｅｅ ｋｉｎｄｓ ｏｆ ＳＶＭ ｐａｒａｍｅｔｅｒｓ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄｓ ｗｅｒｅ ｃｏｍｐａｒｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅｓ ａｎｄ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｇｒｉｄ ｓｅａｒｃｈ，ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｒｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎ ＳＶＭ ｐａｒａｍｅｔｅｒｓ ｏｐｔｉｍｉｚａｔｉｏｎ ｗｅｒｅ ａｎａｌｙｚｅｄ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ ａｎ ｉｍｐｒｏｖｅｄ鲥ｄ ｓｅａｒｃｈ ｍｅｔｈｏｄ ｗａｓ ｐｒｏｐｏｓｅｄ．Ｆｉｒｓｔｌｙ，ｗｅ ｓｅａｒｃｈｅｄ ａ ｓｅｔ ｏｆｐａｒａｍｅｔｅｒｓ ｉｎ ａ ｌａｒｇｅ ｓｐａｃｅ ａｎｄ ｔｈｅｎ ｓｅａｒｃｈｅｄ ａｃｃｕｒａｔｅｌｙ ａｒｏｕｎｄ ｔｈｅ ｐａｒａｍｅｔｅｒｓ ｗｅ ｈａｄ ｆｏｕｎｄ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ｍｅｔｈｏｄ ｕｅｓｅｓ ｌｅｓｓ ｔｉｍｅ ａｎｄ ｉｓ ｓｕｉｔａｂｌｅ ｆｏｒ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ｓｐｅａｋｅｒ ｒｅｃｏｇｎｉｔｉｏｎ ｌｉｍｉｔｅｄ ｂｙ ｔｉｍｅ． ‘ Ｋｅｙｗｏｒｄｓ：ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ；ｐａｒａｍｅｔｅｒｓ ｏｐｔｉｍｉｚａｔｉｏｎ；ｇｒｉｄ ｓｅａｒｃｈ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ； ｓｐｅａｋｅｒ ｒｅｃｏｇｎｉｔｉｏｎ ＳＶＭ是一种基于统计学习理论基础上的机器学 习方法，具有很好的泛化能力【１ Ｊ，在说话人识别等模 将待搜索参数在一定的空间范围中划分成网格，通过 遍历网格中所有的点来寻找最优参数．这种方法在寻 优区间足够大且步距足够小的情况下可以找出全局最 式识别领域得到了广泛的引用．与其他重视经验风险 最小化的算法相比，ＳＶＭ能够得到更好的泛化精度， 在小样本、非线性模式识别中具有一定的优势．实践 证明，核函数的参数以及惩罚系数对ＳＶＭ的性能有 优解．由于网格内多数参数组对应的分类准确率都非 常低，只在一个比较小的区间内的参数组所对应的分 类准确率很高，所以遍历网格内所有参数组会相当浪 费时间．ＧＡ算法和ＰＳＯ算法属于启发式算法，它们不 必遍历区间内所有的参数组也能找到全局最优解，但 这２种算法操作往往比较复杂，且容易陷入局部最优． 针对网格搜索法搜索时间长的问题提出一种改进 的网格搜索法，先采用大步距大范围粗搜，初步确定 一着很大的影响【２］．而对于一些对实时眭要求较高的系 统，如说话人识别系统而言，快速的选择合适的ＳＶＭ 参数，减少训练和识ＮＨ，－ｔ间有着很重要的实际意义． 关于ＳＶＭ参数的优化选取，国际上并没有公认 统一的最好的方法，目前较为常用的ＳＶＭ参数寻优 的方法有：实验法、网格搜索（ｇｒｉｄ ｓｅａｒｃｈ）法【ｊＪ、遗 个最优参数区间，之后在此区间内进行小步距精搜， 传算法（ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ＧＡ）寻优法 、粒子群算 法（ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）寻优法Ｌ５ 等．实 验法是指通过大量的实验比较来确定参数，这种方法 十分浪费时间，且不易寻得最优参数．网格搜索法是 收稿日期：２０１１－１２—０８． 作者简介：王健峰（１９８７一），男，硕士研究生，主要研究方向：语音信 号处理、自然语言处理，Ｅ—ｍａｉｌ：ｊｉａｎｆｅｎｇＯ７０４＠１６３．ｃｏｒｎ． 大幅度地减少了参数寻优时间， 使基于ＳＶＭ的说话 人识别系统更好地满足实时性的要求． １ 支持向量机 ｓｖＭ［ ｌ的基本思想是通过非线性变化把原数据 空间变化到某一高维的特征空间，然后在这个新空间 第３期 王健峰，等：基于改进的网格搜索法的ＳＶＭ参数优化 中求取最优线性分类面，使得该超平面将２类样本正 的折中．若Ｃ过大，就会引起过学习，影响分类器的 泛化能力． 确无误地分开且使分类间隔最大．这种非线性变化通 过定义适当的内积函数加以实现．ＳＶＭ的特点在于根 据有限的样本信息在模型的复杂性（即对特定训练样 本的学习精度）和学习能力（即无错误地识别任意样 本的能力）之间寻求最佳折中，以获得最好的推广能 力． 如果一个问题在其定义的空间中不是线性可分 的，可以考虑通过引入核函数Ｋ（ ，Ｘ），把问题转换 到一个新的空间中，相应的判别函数为 厂ｌ（ ）＝ｓｇｎ（∑口 Ｙ Ｋ（ｘｉ， ）＋６） ｉ＝１ （６） ］，文 对于给定的线性可分数据集｛Ｘｉ，Ｙｉ｝，ｉ＝１，…，Ⅳ， Ｙｉ∈｛一１，＋ｌ｝，Ｘｉ∈Ｒｄ，ｄ维空间中的线性判别函数 径向基核函数是目前应用最广泛的核函 中采用的就是这一核函数，其形式如下： ｇ（ ）＝Ｍ，． ＋ｂ，则可用超平面 ¨，．Ｘ＋ｂ＝０ （１） 进行分离．式中ｗ为权向量，ｂ为分类阈值．而要求分 类线对所有样本正确分类，就是要求它满足： Ｙｉ（ ・五＋６）一１≥０，ｉ＝１，２，…，，ｚ． （２） 满足上述条件且使得分类间隔最大的超平面就是最优 分类面，如图１所示． （ｗ－ｘ） ６ 一１ 最大分类间隔 （ｗ‘ ）＋６＝１ 支持向量 最优分 支持向量 图１最优分类面 经过整理，最优分类面问题可以表示成如下的约 束优化问题，即在式（２）的约束下，求函数 （ ）＝ ｌ ｌｌ』 ＝去（ ・ ） （３） 的最小值．最终可以得出最优分类函数是： 厂（ ）＝ｓｇｎ（（ｗ・ ）＋６）＝ ＿ｖ ｓｇｎ（￣－＂ ｆＹｆ（ ・ ）＋６）． （４） ｉ＝１ 式中：ａ 是二次规划优化问题所求解的拉格朗日因 子，ＪⅣ为支持向量数． 对于线性不可分情况，可以通过在约束条件中引 入松弛变量，在目标函数中加入惩罚函数来解决这一 问题．这时广义最优分类面问题可以进一步演化为求 取下列函数的极小值： （Ｍ，， ）：去（ ・ ）＋ｃ（Ｚ ）． （５） 厶 ｉ＝ｌ 式中：ｃ为常数，它实际上起控制对错分样本惩罚的 程度的作用，实现错分样本的比例与算法复杂度之问 （一， ）＝ｅｘｐ（一ｇＩｌＸｉ一 ｌＩ２］Ｉ，ｇ＞０ （７） 式中：参数ｇ是核函数中的重要参数，影响着ＳＶＭ 分类算法的复杂程度． 综上所述，惩罚参数ｃ和核函数参数ｇ是影响 ＳＶＭ分类器性能的关键参数，所以文中以（Ｇｇ）作 为寻优变量． ２改进的网格搜索寻优方法 ２．１交叉验证 交叉验证（ｃｒｏｓｓ ｖａｌｉｄａｔｉｏｎ，ＣＶ）是用来验证分类 器Ｉ生能的一种统计方法，基本思想是把在某种意义下 将原始数据进行分组，一部分作为训练集，另一部分 作为验证集．首先用训练集对分类器进行训练，再利 用验证集来测试训练得到的模型，以此作为评价分类 器的性能指标．通常人们都采用Ｋ－ｆｏｌｄ ＣＶ，将原始数 据分成 组（一般是均分），将每个子集数据分别做 一次验证集，其余的 ｌ组子集数据作为训练集，这 样会得到 个模型，用这 个模型最终的验证集的分 类准确率的平均数作为此Ｋ－ＣＶ下分类器的性能指标． 一般大于等于２，实际操作时一般从３开始取．只有 在原始数据集合数据量小的时候才会尝试取２．Ｋ－ＣＶ 可以有效地避免过学习以及欠学习状态的发生，最后 得到的结果也比较具有说服性． ２－２改进的网格搜索法 网格搜索法Ｌ１ ＵＪ的基本原理是让Ｃ和ｇ在一定的范 围划分网格并遍历网格内所有点进行取值，对于取定 的Ｃ和ｇ利用Ｋ－ＣＶ方法得到在此组Ｃ和ｇ下训练集 验证分类准确率，最终取使得训练集验证分类准确率 最高的那组Ｃ和ｇ作为最佳的参数．这里给出参数寻 优结果如图２所示，其中Ｃ的范围设置为［２－１￣，２ ｇ 的范围设置为［２。 ，２ ］，步距为０．１． 从图２中可以发现，参数Ｃ和ｇ在一定区间上对 应的分类准确率很高，但在多数范围内的分类准确率 却很低，因此若能先定位出比较好的参数寻优区间， 应 用 科 技 第３９卷 再进行精确搜索，就能够减少不必要的计算，节省大 换成ＬＩＢＳＶＭ要求的输人格式．采用改进的网格搜索 量的时间． ＪＯＯ ９Ｏ ８０ 器７０ 延６Ｏ ５Ｏ ４０ ３０ （） 图２ ＳＶＣ参数选择结果 针对以上问题，提出一种改进的网格搜索法．首 先，在较大范围内采用大步距进行粗搜，选择使分类 准确率最高的一组Ｃ和ｇ．若参数选择过程中有多组 的ｃ和ｇ对应于最高的验证分类准确率，则选取能够 达到最高验证分类准确率中参数Ｃ最小的那组Ｃ和譬 做为最佳的参数；如果对应最小的ｃ有多组．ｇ，就选 取搜索到的第一组Ｃ和譬做为最佳的参数．这样做是 因为过高的ｃ会导致过学习状态发生，即训练集分类 准确率很高而测试集分类准确率很低ｆ分类器的泛化 能力降低），在能够达到最高验证分类准确率中的所有 的成对的Ｃ和２中认为较小的惩罚参数Ｃ是更佳的选 择对象．在寻得了局部最优参数之后，再在这组参数 附近选择一个小区间，采用传统方法中的小步距进行 二次精搜，找到最终的最优参数．如果参数区间选择 合理，那么改进的网格搜索法能够搜索出全局最优的 参数，但由于这个区间的选择含有比较多的经验成分， 所以通常情况下只能得到局部最优的参数．因此，这 种改进的网格搜索法相当于牺牲了分类准确度，来减 少大量的搜索时问． ３实验结果及分析 实验采用的数据是从４名说话人的语音数据中提 取的４组１３维Ｍｅｌ频率倒谱系数（ｍｅｌ ｆｒｅｑｕｅｎｃｙ ｃｅｐｓｔｒａｌ ｃｏｅｆｉｆｃｉｅｎｔｓ，ＭＦＣＣ），其中第１组含有１４１个 样本，第２组含有２０６个样本，第３组含有１６９个样 本，第４组含有１３２个样本，每个样本包含１３个特征 分量．实验平台为ＭＡＴＬＡＢ Ｒ２０１０ｂ，采用台湾大学 林智仁（Ｃｈｉｈ—Ｊｅｎ Ｌｉｎ）博士等 ｌＪ开发设计的ＬＩＢＳＶＭ 工具包进行测试． 实验中首先将样本数据分为（１，２，３，４）４类，并转 法进行参数寻优的实验过程如下： １）设定网格搜索的变量（Ｃ，ｇ）的范围以及搜 索步距．其中Ｃ的初始范围设置为［２－１￣，２ １，ｇ的初始 范围设置为［２－１￣，２ １，由于传统方法中步距一般设为 ０．１，所以改进方法中初始步距选为１００倍的步距，设 为１０． ２屎用Ｋ－ＣＶ方法对训练集进行测试，其中Ｋ＝３， 并得到使分类准确率最高的局部最优参数Ｃ＝Ｉ和 ｇ＝０．０００ ９７． 根据得到的局部最优参数，在其附近选择不同的 区间进行二次寻优，步距与传统方法一样设为０．１，比 较不同的搜索区间对分类准确率的影响，结果记录于 表１． 表１ 不同搜索区间内参数寻优的结果比较 从表１中可以看出，如果二次寻优的参数区间选 择过窄，则可能出现局部最优，对应的分类准确率会 低一些，而参数区问选择过宽，寻优时间又会过长．为 了在两者间进行折中，提出的改进的网格搜索法采用 第２组的参数区间． 为了便于分析，分别采用传统网格搜索法、改进 的网格搜索法、ＧＡ以及ＰＳＯ进行参数寻优，比较各 自性能．实验从４名说话人数据中随机抽取２名训练 一个分类器进行寻优测试，一共做６组．其中ＧＡ参 数寻优法和ＰＳＯ参数寻优法属于启发式算法，它们对 同一组数据进行多次寻优结果可能不同，所以针对这 ２种算法对每组数据做５次实验，取平均值．比较结果 见表２． 从表２中不难看出，传统的网格搜索法耗时最长， ＧＡ算法虽然有时能够得到最高的分类准确率；但容 易过早收敛，出现局部最优，搜索效果不稳定．ＰＳＯ 算法搜索能力比ＧＡ算法稳定，但耗时也比较长．而 文中提出的改进的网格搜索法虽然分类准确率稍低于 其他算法，但其寻优时间远低于其他算法． 第３期 王健峰，等：基于改进的网格搜索法的ＳＶＭ参数优化 表２不同方法进行参数寻优的结果比较 ・３１・ ４ 结束语 支持向量机的参数选择是一项很有意义的研究课 ［５］ＥＢＥＲＨＡＲＴ Ｒ，ＫＥＮＮＥＹ Ｊ．Ａ ｎｅｗ ｏｐｔｉｍｉｚｅｒ ｕｓｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｔｈｅｏｒｙ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ｓｉｘｔｈ Ｉｎｔｅｍａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍｉｃｒｏ Ｍａｃｈｉｎｅ ａｎｄ Ｈｕｍａｎ Ｓｃｉｅｎｃｅ．Ｐｉｓｃａｔａｗａｙ，ＵＳＡ， １９９５：３９—４３． 题，本文针对传统方法寻优时间过长的问题提出了改 进的网格搜索寻优法，经实验证明具有良好的效果， 牺牲了一点分类准确率，但大幅度的减少了寻优时间， 能够满足说话人识别系统对时间的要求． ［６］ＳＵ Ｃ Ｌ ＹＡＮＧ Ｃ Ｈ．Ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｆｏｒ ｔｈｅ ＳＶＭ：ａｎ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｈｙｐｅｒｔｅｎｓｉｏｎ ｄｉａｇｎｏｓｉｓ［Ｊ］．Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎ，２００８，３４（１）：７５４—７６３． 参考文献： ［１】ＶＡＰＮＩＫ Ｖ，ＬＥＶＩＮ Ｅ，ＣＵＮ Ｙ Ｌ．Ｍｅａｓｕｒｉｎｇ ｔｈｅ ［７］张学工．关于统计学习理论与支持向量机［Ｊ］．自动化学报， ２０００，２６（１）：３４—３９． ［８］ＫＥＥＲＴＨＩ Ｓ Ｓ，ＬＩＮ Ｃ Ｊ．Ａｓｙｍｐｔｏｔｉｃ ｂｅｈａｖｉｏｒｓ ｏｆ ｓｕｐｐｏｒｔ ＶＣ—ｄｉｍｅｎｓｉｏｎ ｏｆ ｌｅａｒｎｉｎｇ ｍａｃｈｉｎｅｓ［Ｊ］．Ｎｅｕｒａｌ Ｃｏｍｐｕｔａｔｉｏｎ， １９９４，６（５）：８５１－８７６． ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ｗｉｔｈ Ｇａｕｓｓｉａｎ ｋｅｍｅｌ［Ｊ］．Ｎｅｕｒａｌ Ｃｏｍｐｕｔａｔｉｏｎ， ［２】ＣＨＡＰＥＬＬＥ Ｏ，ＶＡＰＮＩＫ ｍｕｌｔｉｐｌｅ ｐａｒａｍｅｔｅｒｓ ＢＯＵＳＱＵＥＴ Ｏ．Ｃｈｏｏｓｉｎｇ ２００３，１５（７）：１６６７—１６８９． ［９】ＳＭＯＬＡ Ａ Ｊ，ＳＣＨＯＬＫＯＰＦ Ｂ，ＭＵＬＬＥＲ Ｋ Ｒ．Ｔｈｅ ｃｏｎｎｅｃｔｉｏｎ ｂｅｔｗｅｅｎ ｒｅｇｕｌａｒｉｚａｔｉｏｎ ｏｐｅｒａｔｏｒｓ ａｎｄ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｋｅｍｅｌｓ［Ｊ］． Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ，１９９８，ｌ１（４）：６３７—６４９． ｆｏｒ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ［Ｊ］． Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ，２００２，４６（１／３）：１３ １－１５９． ［３］Ｌ１Ｕ Ｘｉａｎｇｌｏｕ，ＪＩＡ Ｄｏｎｇｘｕ，ＬＩ Ｈｕｉ．Ｒｅｓｅａｒｃｈ ｏｎ Ｋｅｒｎｅｌ ｐａｒａｍｅｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｉｎ ｓｐｅａｋｅｒ ｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．Ｓｃｉｅｎｃｅ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０， １０ｆ７）：１６６９—１６７３． ［１０】王兴玲，李占斌．基于网格搜索的支持向量机核函数参数 的确定［Ｊ】．中国海洋大学学报，２００５，３５（５）：８５９—８６２． ［１１］ＣＨＡＮＧＣＣ，ＬＩＮＣ Ｊ．ＬＩＢＳＶＩＶＩ：ａｌｉｂｒａｒｙｆｏｒ ｓｕｐｐｏｒｔｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ［ＤＢ／ＯＬ］．［２０１ １－１０・０７］．ｈｔｔｐ：ｌｌｗｗｗ．ｃｓｉｅ．ｎｔｕ．ｅｄｕ． ［４】ＣＨＥＮ Ｐ ｗ ＷＡＮＧ Ｊ ＬＥＥ Ｈ．Ｍｏｄｅｌ ｓｅｌｅｃｔｉｏｎ ｏｆ ＳＶＭｓ ｕｓｉｎｇ ＧＡ ａｐｐｒｏａｃｈ［Ｃ］／／Ｐｒｏｃ ｏｆ ２００４ ＩＥＥＥ Ｉｎｔ Ｊｏｉｎｔ Ｃｏｎｆ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．Ｐｉｓｃａｔａｗａｙ，ＵＳＡ，２００４：２０３５—２０４０． ｗ／ｔ－ｃｊｌｉｎ／ｌｉｂｓｖｍ／．
