444 工程科学学报，第42卷，第4期 em4+m,∑年≤∑，∑g≤∑，则 考平面，计算参考平面的法向量方向： d=+by=+1)b=-1y=-1) (2)在参考平面上布置均匀分布的参考点 称(m+,p-,b,,)为Pareto最优分类器.所有Pareto q,i=1,…,k 最优分类器构成了Pareto前沿分类器.由于所有 (3)遍历所有的k个参考点，求解最优化问题： Pareto最优分类器都是对分类间隔，正负经验误差 maxt,st.qi+tn=fx),t≥0，x∈X 之间的权衡，因此决策者可能会感兴趣.此外，由 并把q:+tn存储到集合R. 于具有最佳性能的分类器均在Pareto最优分类器 输出：代表性非支配点子集R 集合中，不需要考虑该集合之外的分类器 通过NBI方法可以求得一组MOLP的代表性 2.2多目标优化算法 非支配点.对于(T-SVM)问题，每个非支配点都对 本文采用法向边界交叉法(Normal boundary 应一个Pareto最优分类器.决策者可以在交叉验 intersection method,NBI)P来求解MOLP问题 证集上遍历所有的Pareto最优分类器，选择出性 (MOLP)min f(x)=(fi(x).f(x).....fp(x))T 能最优Pareto分类器作为最终的分类器 s.tr∈Rm:gr)=(g1x),g2(x),…,8p(x)T≤0 2.3分类器性能评估 其中，X={x∈R”:g(x)=(g1(x),g2(x),…,gp(x)T≤0} 对于一组Pareto最优分类器，决策者需要根据 代表决策变量可行域，假设其非空，则目标空间可 交叉验证集上的性能选择最终分类器.常用的衡 行域为Y={fx):xeX. 量分类器性能的评价指标有灵敏度(Sensitivity)、 对于MOLP问题，如果不存在x∈X使得 特异性(Specificity)和准确性(Accuracy).敏感性 fx)≤fe),则称∈X为MOLP问题的一个有效 表明少数群体的准确性，特异性表明多数群体的 解.有效解组成的集合表示为XE,称作决策空间中 准确性 的有效集合.相应地，=f)称作一个非支配点， 一般情况下，准确率通常被视为评估标准之 Yw={fx):xeXE称之为目标空间可行域中的非 一 但是，在数据集不平衡的情况下准确率不能完 支配点解集.NBI方法就是为了求得MOLP问题 全反映分类器的性能好坏.例如，对于正负样本比 中的非支配点集Yw的子集R.图3展示了NBI方法 率为1：9的数据集，即使判断所有少数类别的样 求解一个两个目标优化模型的示例.该方法首先 本都错误，准确率仍然可以达到90%.但是对于疾 计算一个参考平面，并在参考平面上放置均匀分 病诊断，正确分类少数类样本（患病）是很重要的. 布的参考点，然后沿着法线方向将参考点投影到 因此，本文使用灵敏度和特异性的几何平均值g Y的边界，最终得到多目标优化模型的代表性非支 means(g-means=Vsensitivity×specificity)来评估分 配点集合R.利用NBI解多个目标优化问题如算 类器性能 法1所示 3 实验结果 本文使用提出的基于1范数SVM的三个目标 分类方案对ADHD-200竞赛的五个数据集进行分 6 类测试.每个数据集都被随机分为三个数据集：训 练集、交叉验证集和测试集，划分比例为6：2：2， 即使用数据集的60%用于训练，20%用于模型交 叉验证选取最终分类器，剩余的20%用来测试衡 -2 6 8 量最终分类器的效果 下面以Peking-l数据集为例，给出分类器的选 图3NBI方法中获得的非支配点 Fig.3 Non-dominated points obtained using the NBI method 择过程.首先，用NBI方法来求解由训练集构成的 (T-SVM)问题，从而获得一组非支配点，共11个， 算法1NBI算法求解MOLP问题 如图4(a)所示，每个对应一个Pareto最优分类器， 输人：优化问题模型 图中三个坐标轴分别代表分类间隔|l,正样本 (1)求解三个目标模型中每个目标的最小值 经验误差之∑5，和与负样本经验误差之和∑-.进 =min((x):x∈X,k=1,2,3,假设最优解被表示 一步地，计算出11个分类器在训练集和交叉验证 为1,2,3，构造1,2,3三个点组成的凸包作为参 集上的准确率和g-means值，见表2.e T (w¯ ++w¯ −), ∑ {i|y i=+1} ξ i + ⩽ ∑ {i|y i=+1} ξ¯ i + , ∑ {i|y i=−1} ξ i − ⩽ ∑ {i|y i=−1} ξ¯ i − (w¯ +,w¯ −,b¯, ξ¯i + , ξ¯i − ) ，则 称 为 Pareto 最优分类器. 所有 Pareto 最优分类器构成了 Pareto 前沿分类器. 由于所有 Pareto 最优分类器都是对分类间隔，正负经验误差 之间的权衡，因此决策者可能会感兴趣. 此外，由 于具有最佳性能的分类器均在 Pareto 最优分类器 集合中，不需要考虑该集合之外的分类器. 2.2    多目标优化算法 本文采用法向边界交叉法 (Normal boundary intersection method, NBI)[21] 来求解 MOLP 问题. (MOLP)min f(x) = (f1(x), f2(x),··· , fp(x))T s.t.x ∈ R n : g(x) = (g1(x),g2(x),··· ,gp(x))T ⩽ 0 X = {x ∈ R n : g(x) = (g1(x),g2(x),··· ,gp(x))T ⩽ 0} Y = {f(x) : x ∈ X} 其中 ， 代表决策变量可行域，假设其非空，则目标空间可 行域为 . x ∈ X f(x) ⩽ f(xˆ) xˆ ∈ X XE yˆ = f(xˆ) YN = {f(x) : x ∈ XE} YN R R 对 于 MOLP 问 题 ， 如 果 不 存 在 使 得 ，则称 为 MOLP 问题的一个有效 解. 有效解组成的集合表示为 ，称作决策空间中 的有效集合. 相应地， 称作一个非支配点， 称之为目标空间可行域中的非 支配点解集. NBI 方法就是为了求得 MOLP 问题 中的非支配点集 的子集 . 图 3 展示了 NBI 方法 求解一个两个目标优化模型的示例. 该方法首先 计算一个参考平面，并在参考平面上放置均匀分 布的参考点，然后沿着法线方向将参考点投影到 Y 的边界，最终得到多目标优化模型的代表性非支 配点集合 . 利用 NBI 解多个目标优化问题如算 法 1 所示. 算法 1 NBI 算法求解 MOLP 问题 输入：优化问题模型 y I k = min{fk(x) : x ∈ X}, k = 1,2,3 y¯1, y¯2, y¯3 y¯1, y¯2, y¯3 （1）求解三个目标模型中每个目标的最小值 ，假设最优解被表示 为 ，构造 三个点组成的凸包作为参 考平面，计算参考平面的法向量方向 nˆ； qi ,i = 1,··· , k （ 2）在参考平面上布置均匀分布的参考点 ； （3）遍历所有的 k 个参考点，求解最优化问题： maxt,s.t.qi +tnˆ = f(x),t ⩾ 0, x ∈ X 并把 qi +tnˆ存储到集合 R. 输出：代表性非支配点子集 R 通过 NBI 方法可以求得一组 MOLP 的代表性 非支配点. 对于（T-SVM）问题，每个非支配点都对 应一个 Pareto 最优分类器. 决策者可以在交叉验 证集上遍历所有的 Pareto 最优分类器，选择出性 能最优 Pareto 分类器作为最终的分类器. 2.3    分类器性能评估 对于一组 Pareto 最优分类器，决策者需要根据 交叉验证集上的性能选择最终分类器. 常用的衡 量分类器性能的评价指标有灵敏度（Sensitivity）、 特异性（Specificity）和准确性（Accuracy）. 敏感性 表明少数群体的准确性，特异性表明多数群体的 准确性. g−means = √ sensitivity×specificity 一般情况下，准确率通常被视为评估标准之 一. 但是，在数据集不平衡的情况下准确率不能完 全反映分类器的性能好坏. 例如，对于正负样本比 率为 1∶9 的数据集，即使判断所有少数类别的样 本都错误，准确率仍然可以达到 90%. 但是对于疾 病诊断，正确分类少数类样本（患病）是很重要的. 因此，本文使用灵敏度和特异性的几何平均值 g￾means（ ）来评估分 类器性能. 3    实验结果 本文使用提出的基于 1 范数 SVM 的三个目标 分类方案对 ADHD-200 竞赛的五个数据集进行分 类测试. 每个数据集都被随机分为三个数据集：训 练集、交叉验证集和测试集，划分比例为 6∶2∶2， 即使用数据集的 60% 用于训练，20% 用于模型交 叉验证选取最终分类器，剩余的 20% 用来测试衡 量最终分类器的效果. ∥ w∥1 ∑ ξ+ ∑ ξ− 下面以 Peking-1 数据集为例，给出分类器的选 择过程. 首先，用 NBI 方法来求解由训练集构成的 （T-SVM）问题，从而获得一组非支配点，共 11 个， 如图 4（a）所示，每个对应一个 Pareto 最优分类器， 图中三个坐标轴分别代表分类间隔 ，正样本 经验误差之 和与负样本经验误差之和 . 进 一步地，计算出 11 个分类器在训练集和交叉验证 集上的准确率和 g-means 值，见表 2. y2 y−1 y 2 y1 Y − 8 6 4 4 6 8 2 −2 2 图 3 NBI 方法中获得的非支配点 Fig.3 Non-dominated points obtained using the NBI method · 444 · 工程科学学报，第 42 卷，第 4 期