第2期 曹晋，等：一种新的基于支持向量数据描述的特征选择算法 ·217. 行讨论。 个方向上的分布就越广。若能量在第i个方向上较 令训练样本有n个，边界半径的平方如式(3) 小，则数据在该方向上必然非常紧凑。注意到作者 所示。用所有支持向量获得的R(x.)的平均值作 的目的是让尽可能多的目标数据包含在超球体内。 为衡量边界大小的准则函数，则该平均值J,定义为 紧凑的数据将形成一个小半径的超球体，这样的超 1,=∑ R2(x..) 球体可能不会包含大部分的数据。因此，紧凑分布 (4) 方向的特征应该被移除，同时分布较散的方向应该 式中：t是支持向量的个数。引入线性核函数后，准 保留。 则函数(4)可以表示为 因而，用a表示第i个特征的重要性。那么就 J,= 可以根据能量a来消除不重要特征。SVDD-RFE Σ化-ga足+宫含a4别 从特征集合中迭代消除特征，这个迭代过程分以下 3步完成。1)由目标数据训练SVDD,得到超球体的 (5) 中心：2)计算所有特征的a,i=1,2,…,D:3)从原 令J,(-P)为除特征P以外获得的球半径。 始特征集移除具有最小值所对应的特征。重复 则最坏的特征是具有最大J(-P)值所对应的特 这个迭代过程直到满足终止条件。具体算法在下面 征。移除特征P后，准则函数的有效性可用 的算法1中给出。 DJ,(P)=J,-J,(-P)来表示。最坏的特征是具有 注意算法1中的F是已选特征的索引集合，也 最小值的DJ(P)对应的特征。 意味着这些特征已保留下来。本算法旨在特征的选 1.2.2 SVDD-dual-objective-RFE 择和得到较少特征的数据集合。对于最后得到的数 令J:和J:(-P)分别为SVDD对偶规划中对 据集，任何分类器，都可以用来建立分类模型。 偶函数的值和移除特征P后对偶规划的值。J是式 算法1SVDD-RFE (1)中对偶规划具有相似的值，即： 输入：训练样本{c:}1,其中x:∈R,n是训 (6) 练样本的个数，D是样本维数，子空间维数用d表示； =1=1 输出：被选择特征的索引集合F。 J(-P)= 立a(-Px(-P)(-P),- 1)初始化被选特征的索引集合F= {1,2,…,D}并且令m=D。 三a(P)a(-Px(-D(Pm, 2)求解对偶规划(1)，得到超球体的中心a= (7) [a1a2…a]T∈R"。 用DJ(P)=J4-J(-P)作为衡量准则函数 3)计算所有方向的能量a,i=1,2,…,m。 来消除冗余特征，最坏的特征P·是在所有特征中， 4)找到具有最小能量的特征P=arg,mina。 i=,2,“则 具有最小J:(-P)值的那一个。即 5)令m=m-1,令被选特征索引集合F=F\P, P·=arg maxDJ(P) 并从训练样本集合中消除第P个特征，得到更新的 训练样本集合{x}-1,其中x:∈R。 2 基于支持向量数据描述的特征选择 6)若m=d,算法结束：否则转到2)。 算法 3 实验结果 本节提出了一种新的基于支持向量数据描述的 在DNA微阵列的基因表达数据集上进行实验， 特征选择算法，即SVDD-RFE。 要验证SVDD-RFE算法的正确性和有效性。实验 SVM特征选择是利用权向量w来进行特征消 数据集是Leukemia数据集。在Leukemia数据集 除。SVDD不存在权向量w,但具有超球体的中心 中，有2种不同种类的白血病，急性淋巴细胞性白血 a=[a1a2…a】T。|a:|的值表示目标样本 病(acute lymphoblastic leukemia,ALL)和急性骨髓 的第i个方向的平均幅值。则a:表示第i个方向的 性白血病(acute myeloid leukemia,AML)。 能量。第i个方向上的能量越大，则目标样本在第i 数据集被划分为2个子集：训练集和测试集。行讨论。 令训练样本有 ｎ 个，边界半径的平方如式（３） 所示。 用所有支持向量获得的 Ｒ ２ ｘｓｖ ( ) 的平均值作 为衡量边界大小的准则函数，则该平均值 Ｊｒ 定义为 Ｊｒ ＝ ∑ Ｒ ２ ｘｓｖ ( ) ｔ （４） 式中： ｔ 是支持向量的个数。 引入线性核函数后，准 则函数（４）可以表示为 Ｊｒ ＝ １ ｔ ∑ ｘ Ｔ ｓｖ ｘｓｖ － ２∑ ｎ ｉ ＝ １ αｉ ｘ Ｔ ｓｖ ｘｉ ＋ ∑ ｎ ｉ ＝ １ ∑ ｎ ｊ ＝ １ αｉαｊ ｘ Ｔ ( ｉ ｘｊ) （５） 令 Ｊｒ ( － Ｐ) 为除特征 Ｐ 以外获得的球半径。 则最坏的特征是具有最大 Ｊｒ ( － Ｐ) 值所对应的特 征。 移 除 特 征 Ｐ 后， 准 则 函 数 的 有 效 性 可 用 ＤＪｒ (Ｐ) ＝ Ｊｒ － Ｊｒ ( － Ｐ) 来表示。 最坏的特征是具有 最小值的 ＤＪｒ (Ｐ) 对应的特征。 １．２．２ ＳＶＤＤ⁃ｄｕａｌ⁃ｏｂｊｅｃｔｉｖｅ⁃ＲＦＥ 令 Ｊｄ 和 Ｊｄ ( － Ｐ) 分别为 ＳＶＤＤ 对偶规划中对 偶函数的值和移除特征 Ｐ 后对偶规划的值。 Ｊｄ 是式 （１）中对偶规划具有相似的值，即： Ｊｄ ＝ ∑ ｎ ｉ ＝ １ αｉ ｘ Ｔ ｉ ｘｉ － ∑ ｎ ｉ ＝ １ ∑ ｎ ｊ ＝ １ αｉαｊ ｘ Ｔ ｉ ｘｊ （６） Ｊｄ ( － Ｐ) ＝ ∑ ｎ ｉ ＝ １ α ( － Ｐ) ｉｘ ( － Ｐ) Ｔ ｉ ｘ ( － Ｐ) ｉ － ∑ ｎ ｉ ＝ １ ∑ ｎ ｊ ＝ １ α ( － Ｐ) ｉα ( － Ｐ) ｊｘ ( － Ｐ) Ｔ ｉ ｘ ( － Ｐ) ｊ （７） 用 ＤＪｄ (Ｐ) ＝ Ｊｄ － Ｊｄ ( － Ｐ) 作为衡量准则函数 来消除冗余特征，最坏的特征 Ｐ ∗ 是在所有特征中， 具有最小 Ｊｄ ( － Ｐ) 值的那一个。 即 Ｐ ∗ ＝ ａｒｇ ｍａｘ Ｐ ＤＪｄ (Ｐ) ２ 基于支持向量数据描述的特征选择 算法 本节提出了一种新的基于支持向量数据描述的 特征选择算法，即 ＳＶＤＤ⁃ＲＦＥ。 ＳＶＭ 特征选择是利用权向量 ｗ 来进行特征消 除。 ＳＶＤＤ 不存在权向量 ｗ ，但具有超球体的中心 ａ ＝ [ａ１ ａ２ … ａＤ ] Ｔ 。 ａｉ 的值表示目标样本 的第 ｉ 个方向的平均幅值。 则 ａ ２ ｉ 表示第 ｉ 个方向的 能量。 第 ｉ 个方向上的能量越大，则目标样本在第 ｉ 个方向上的分布就越广。 若能量在第 ｉ 个方向上较 小，则数据在该方向上必然非常紧凑。 注意到作者 的目的是让尽可能多的目标数据包含在超球体内。 紧凑的数据将形成一个小半径的超球体，这样的超 球体可能不会包含大部分的数据。 因此，紧凑分布 方向的特征应该被移除，同时分布较散的方向应该 保留。 因而，用 ａ ２ ｉ 表示第 ｉ 个特征的重要性。 那么就 可以根据能量 ａ ２ ｉ 来消除不重要特征。 ＳＶＤＤ⁃ＲＦＥ 从特征集合中迭代消除特征，这个迭代过程分以下 ３ 步完成。 １）由目标数据训练 ＳＶＤＤ，得到超球体的 中心；２）计算所有特征的 ａ ２ ｉ ，ｉ ＝ １，２，…，Ｄ ；３）从原 始特征集移除具有最小 ａ ２ ｉ 值所对应的特征。 重复 这个迭代过程直到满足终止条件。 具体算法在下面 的算法 １ 中给出。 注意算法 １ 中的 Ｆ 是已选特征的索引集合，也 意味着这些特征已保留下来。 本算法旨在特征的选 择和得到较少特征的数据集合。 对于最后得到的数 据集，任何分类器，都可以用来建立分类模型。 算法 １ ＳＶＤＤ⁃ＲＦＥ 输入： 训练样本 ｘｉ { } ｎ ｉ ＝ １ ，其中 ｘｉ ∈ Ｒ Ｄ ， ｎ 是训 练样本的个数， Ｄ 是样本维数，子空间维数用 ｄ 表示； 输出：被选择特征的索引集合 Ｆ 。 １） 初 始 化 被 选 特 征 的 索 引 集 合 Ｆ ＝ {１，２，…，Ｄ} 并且令 ｍ ＝ Ｄ 。 ２）求解对偶规划（１），得到超球体的中心 ａ ＝ [ａ１ ａ２ … ａｍ ] Ｔ ∈ Ｒ ｍ 。 ３）计算所有方向的能量 ａ ２ ｉ ， ｉ ＝ １，２，…，ｍ 。 ４）找到具有最小能量的特征 Ｐ ＝ ａｒｇ ｍｉｎ ｉ ＝ １，２，…，ｍ ａ ２ ｉ 。 ５）令 ｍ ＝ ｍ － １，令被选特征索引集合 Ｆ ＝ Ｆ ＼Ｐ， 并从训练样本集合中消除第 Ｐ 个特征，得到更新的 训练样本集合 ｘｉ { } ｎ ｉ ＝ １ ，其中 ｘｉ ∈ Ｒ ｍ 。 ６）若 ｍ ＝ ｄ ，算法结束；否则转到 ２）。 ３ 实验结果 在 ＤＮＡ 微阵列的基因表达数据集上进行实验， 要验证 ＳＶＤＤ⁃ＲＦＥ 算法的正确性和有效性。 实验 数据集是 Ｌｅｕｋｅｍｉａ 数据集。 在 Ｌｅｕｋｅｍｉａ 数据集 中，有 ２ 种不同种类的白血病，急性淋巴细胞性白血 病（ ａｃｕｔｅ ｌｙｍｐｈｏｂｌａｓｔｉｃ ｌｅｕｋｅｍｉａ，ＡＬＬ） 和急性骨髓 性白血病（ａｃｕｔｅ ｍｙｅｌｏｉｄ ｌｅｕｋｅｍｉａ，ＡＭＬ）。 数据集被划分为 ２ 个子集：训练集和测试集。 第 ２ 期 曹晋，等：一种新的基于支持向量数据描述的特征选择算法 ·２１７·