四、Ｍａ ｔｌａ ｂ 程序实现一对一方式 Ｍ－ Ｓ ＶＭ 本文使用的 Ｍａｔｌａｂ 版本为 ７．１， 为方便起见， 所要分类 的类别为三类， 输入向量的维数为四维。类 １ 训练样本数 取 ５０， 类 ２ 训 练 样 本 数 取 ５０， 类 ３ 训 练 样 本 数 取 ５０， 待 预 测样本为 １０００。利用三个二分类 ＳＶＭ 模型构造一个三分 类 ＳＶＭ 模型。 （ 一） 二分类情况 Ｍａｔｌａｂ７．１ 中 提 供 了 关 于 二 分 类 支 持 向 量 机 的 函 数 ｓｖｍｔｒａｉｎ（ ｔｒａｉｎ， ｇｒｏｕｐ） 和 ｓｖｍｃｌａｓｓｉｆｙ（ ＳＶＭＳｔｒｕｃｔ， ｔｅｓｔ） ， 其 中 ｔｒａｉｎ 为 训 练 样 本 集 ， ｇｒｏｕｐ 为 ｔｒａｉｎ 中 各 样 本 所 属 的 类 别 ， ｓｖｍｔａｉｎ 用于训 练 支 持 向 量 机 模 型 ， ｓｖｍｃｌａｓｓｉｆｙ 用 于 对 未 知 类 别 数 据 ｔｅｓｔ 进 行 预 测 ， ＳＶＭＳｔｒｕｃｔ 为 训 练 好 的 支 持 向 量 机模型。数据类型格式如图 ２ 所示， 输入 向 量 格 式 为 ｘｉ＝ ｛ａｉ， ｂｉ， ｃｉ， ｄｉ ｝；
ＭＡＴＬＡＢ 是 ＭａｔｈＷｏｒｋｓ 公司于 １９８２ 年推 出 的 一 套 高 性 能 的 数 值 计 算 和 可 视 化 软 件 。它 集 数 值 分 析 、矩 阵 运 算 、
ｌ
. ! ! ｗ， ｂ， ｃ " ＝ １ ２
２
‖ｗ‖ －
ａｉ !ｙｉ & ＜ｗ·ｘ＞＋ｂ
ｉ＝１

/ － １
"， 但由于计
信 号 处 理 和 图 形 显 示 于 一 体 ， 构 成 了 一 个 方 便 、界 面 友 好 算 的 复 杂 性 ， 一 般 不 直 接 求 解 ， 而 是 依 据 拉 格 朗 日 对 偶 理
ＳＶＭ 可以解决二分类和多分类的问题， 可以考虑使用 Ｍａｔｌａｂ 来实现 ＳＶＭ 的分类功能。ＳＶＭ 的训练以及决策时 需要运算大量的数据， 然而 Ｍａｔｌａｂ 在处理大量数据时， 如 果程序的算法不恰当， 程序执行效率是很低的， 运行时间 较长。事实上， 在 Ｍａｔｌａｂ 程序中尽量避免使用循环语句， 而 改用对矩阵的处理， 将会大大提高运算速度。本文就 ＳＶＭ 在一对一投票法解决多分类问题时 ， ［３］ 遇到的大量数据计 算， 给出了 Ｍａｔｌａｂ 矩阵运算方式的算法。
三、一对一方式的 Ｍ－ Ｓ ＶＭ ＳＶＭ 的方法是针对二分类问题提出的。对于多分类问 题 ， 目 前 的 多 分 类 支 持 向 量 机（ Ｍ－ ＳＶＭ） 主 要 有 俩 方 面 的 方 法［４］： 一是直接求解一个含多类问题的优化问题， 通过适当 的修改求解原始最优化问题， 使它能同时一次性计算出所 有多分类的预测函数， 一次性的进行多类分类。该方法花 费的时间较长， 计算量较大， 求解过程复杂， 没有很广泛的 被应用； 另一个是基于二分类问题算法的， 构造或组建多个二 分类器来实现多分类问题。该方法简单实用， 其中包括一 对多和一对一以及决策树等方式。 一对一分类是在 Ｎ 类训练样本中构造所有可能的两 类分类器， 每个分类器仅仅在 Ｎ 类中的两类训练样本上训 练， 结果共构造 Ｎ（ Ｎ－ １） ／２ 个分类器。测试样本经过各个分 类器进行分类， 对所有组合类进行投票， 得票最多的类为 测试样本所属的类。
)
ｌ
ｌｌ
. .. +
++ｍａｘｍｉｓｅ
+ +
ａｋ －
ｋ＝１
１ ２
ａｉ ａｊ ｙｉ ｙｊ ＜ｘｉ·ｘｊ ＞
ｉ＝１ ｊ＝１
*
+
ｌ
+
. ++ｓｕｂｊｅｃｔ ｔｏ
+
ａｉ ｙｉ ＝０， ａｉ (０， ｉ＝１， …， ｌ
,
ｉ＝１
求 解 得 到 的 最 优 解 为 ａ＊ ＝（ ａ１ ＊ ， … ， ａｌ ＊ ） Ｔ 这 样 ， 计 算 得
ｒｅｓｕｌｔ＝ｃ１＋ｃ２·５＋ｃ３·１０＋ｃ４·１６； ｒｅｓｕｌｔ 就 是 待 预 测 数 据 ｔｅｓｔ 经 过 三 分 类 后 的 结 果 ， 分 别用 １、５、１０、１６ 标出。
性软间隔分类。常用的核函数包括多项式核， 径向基核， 以
现给出两类训练样本集的分类问题
及 Ｓｉｇｍｏｉｄ 核 等 ， 对 于 非 线 性 分 类 ， ＳＶＭ 运 算 只 考 虑 特 征
Ｄ＝ #!ｘ１ ， ｙ１ "， …， !ｘ１ ， ｙ１ "$， ｘ∈Ｒｎ ， ｙ∈ # － １， １ $
该 问 题 的 分 类 就 是 寻 找 最 优 超 平 面（ ｗ， ｘ） ＋ｂ＝０， 使 得
山西煤炭管理 １４６
干部学院学报
２００８．１
图 ２ 支持向量机数据格式
图 ３ 各二分类器训练数据格式
利用以上训练数据分别训练 ＳＶＭ， 可得到三个二分类 器模型， 代码如下：
ＳＶＭＳｔｒｕｃｔ１２＝ｓｖｍｔｒａｉｎ（ ｔｒａｉｎ１２， ｇｒｏｕｐ１２） ； ＳＶＭＳｔｒｕｃｔ２３＝ｓｖｍｔｒａｉｎ（ ｔｒａｉｎ２３， ｇｒｏｕｐ２３） ； ＳＶＭＳｔｒｕｃｔ１３＝ｓｖｍｔｒａｉｎ（ ｔｒａｉｎ１３， ｇｒｏｕｐ１３） ； 接下来就可以用以上三个模型去预测待分类的数据 ｔｅｓｔ， ｔｅｓｔ 的数据格式也和训练数据的类型格 式 一 样 ， 所 不 同的是 ｔｅｓｔ 数据是未知类别的。代码如下： ｃｌａｓｓ１２ ＝ ｓｖｍｃｌａｓｓｉｆｙ（ ＳＶＭＳｔｒｕｃｔ１２， ｔｅｓｔ） ｃｌａｓｓ２３＝ｓｖｍｃｌａｓｓｉｆｙ（ ＳＶＭＳｔｒｕｃｔ２３， ｔｅｓｔ） ｃｌａｓｓ１３＝ｓｖｍｃｌａｓｓｉｆｙ（ ＳＶＭＳｔｒｕｃｔ１３， ｔｅｓｔ） 接下来该解决投票问题了。ｔｅｓｔ 中各输入向量 Ｘｉ 的最 终归属类别取决于 ｃｌａｓｓ１２、ｃｌａｓｓ２３、ｃｌａｓｓ１３ 的分类情况， 对 于某个输入向量 Ｘｉ 的最终归属类别应该是经过 三 个 模 型 预测后， 被预测为类别最多的那个类别。对本文中的三分 类情况， ｔｅｓｔ 中某个 Ｘｉ 经过三个模型预测后， 所属类别情 况只可能是图 ４ 所示的情况。
ｌ
. 标函数改为 求 " ! ｗ， ! " ＝ １ ２
２
‖ｗ‖ ＋Ｃ !ｉ 最 小 ， 就 可 以 解
ｉ＝１
决样本点线性不可分的情况了。其中， Ｃ 为惩罚参数。其求
解方式和线性可分情况几乎完全相同， 只是约束条件变为
二、Ｓ ＶＭ 基本原理
０1ａｉ 1Ｃ， 最优预测函数的形式与式（ ２） 一样。由于对偶形
支 持 向 量 机 ＳＶＭ （ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅ） 是 ＡＴ＆ＴＢｅｌｌ 实验室的 Ｖ．Ｖａｐｎｉｋ 提出的针对分类和回归问题 的统计学习理论。［２］由于 ＳＶＭ 方法具有许多引人注目的优 点和有前途的实验性能， 越来越受重视。该技术已成为机 器学习研究领域中的热点， 并取得很理想的效果， 如人脸 识 别 、手 写 体 数 字 识 别 和 网 页 分 类 等 。
干部学院学报
２００８．１
线性 ＳＶＭ 核形式的最优判别函数为
ｌ
! ｆ（ ｘ） ＝ｓｇｎ（ ａｉ ＊ Ｋ（ ｘ·ｘｉ） ＋ｂ＊ ） ｉ＝１
在具体的实现上， 只要将所要训练 ＳＶＭ 的 数 据 按 一 定的格式组成输入向量， 对 ＳＶＭ 进行训练就可 求 得 一 组 参数， 得到一个支持向量机模型， 用得到的 ＳＶＭ 模 型 去 预 测未知类别的数据（ 数据格式同训练数据格式） ， 就可得到 分类结果。
的用户环境。Ｍａｔｌａｂ 语言是一种以矩阵和阵列为基本编程 论， 求解以下对偶问题式：
单元， 拥有完整的控制语句、数据结构、函数编写与调用格 式和输入输出功能的编程语言， 相对于其他编程语言来 说 ， 在 矩 阵 运 算 、数 据 处 理 和 图 形 显 示 功 能 方 面 Ｍａｔｌａｂ 更 具优势， ［１］对于复杂算法可用简洁的脚本式语句编写程序 ， 方便快捷。
ｌ
. 到 ｗ＊ ＝ ａｉ ｘｉ ｙｉ ； ｂ＊ ＝－ ｉ＝１
１ ２
＜ｗ＊ ， ｘｒ ＋ｘｓ ＞；
其中 ｘｒ ， ｘｓ 是俩类中
任意的支持 向 量 （ ＳＶ）（ 依 据 Ｋａｒｕｓｈ－ Ｋｕｈｎ－ Ｔｕｃｋｅｒ 互 补 条
件， 少量最靠近超平面样本点的 ａｉ 值不为零的点， 称为支
持向量） ， 最终预测函数为：
基于 ＭＡＴＬＡＢ 的一对一 Ｍ－ Ｓ ＶＭ 算 法实现
窦智宙， 孟昭进
（ 内蒙古师范大学计算机与信息工程学院， 内蒙古 呼和浩 特 ０１００２２）
训练样本集完全正确分开， 同时满足距离超平面最近的两 类点间隔最大（ 如图 １ 所示） 。
摘要： 简述了多分类支持向量机（ Ｍｕｌｔｉ－ ｃｌａｓｓ Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ
Ｍａｃｈｉｎｅ ， Ｍ－ ＳＶＭ） 的 原 理 及 算 法 。 在 此 基 础 上 ， 利 用
ＭＡＴＬＡＢ 实现了一对一多分类支持向量机的多分类算法，
图 １ 最优分类面示意图
利 用 ＭＡＴＬＡＢ 的 矩 阵 处 理 方 式 解 决 了 算 法 中 投 票 机 制 。 该算 法 避 免 了 ＭＡＴＬＡＢ 中 循 环 语 句 的 使 用 ， 提 高 了 算 法 效率， 缩短了运行时间。 关键词： ＭＡＴＬＡＢ； 多分类支持向量机； 一对一 中 图 分 类 号 ： ＴＰ ３１９ 文 献 标 识 码 ： Ａ 文 章 编 号 ： １００８－ ８８８１（ ２００８） ０１－ ０１４５－ ０３
ｌ
. ｆ（ ｘ） ＝ｓｇｎ（ ａｉ ＊ ｙ（ｉ ｘ·ｘｉ） ＋ｂ＊ ）
（ ２）
ｉ＝１
（ 二） 线性不可分 ＳＶＭ
对 于 分 类 问 题 线 性 不 可 分 的 情 况 ， 只 要 在（ １） 式 中 引
入 松 驰 项 !ｉ (０， 成 为 ｙｉ &＜ｗ， ｘｉ ＞＋ｂ /(１－ !， ｉ＝１， … ， ｌ 将 目