一种基于因果网络的支持向量回归特征选择算法

陈一明

摘 要 为了提高支持向量回归算法的学习能力，提出了一种基于因果网络的特征选择算法. 该方法假设目标变量和特征候选集之间符合一个因果网络模型，然后利用基于条件独立性测试的方法对目标变量的直接影响特征进行识别，从候选特征集之中获取与目标变量有着直接因果关系的特征子集.虚拟和真实数据集上的实验结果表明，该特征选择算法适用于支持向量回归算法，优于目前其他算法.

关键词 支持向量回归； 特征选择； 因果网络； 条件独立性测试

中图分类号 TP181 文献标识码 A 文章编号 1000-2537（2015）04-0090-06

Abstract In order to improve Support Vector Regression （SVR） learning ability， a novel feature selection method based on causal network is proposed. Firstly， the target variable and its candidate feature set are assumed to conform a causal network model. Subsequently， the causal feature can be detected by conditional independence test based method. Both virtual and real experimental results show that the proposed algorithm outperforms other methods when applied to SVR.

Key words support vector regression； feature selection； causal network； conditional independence test

对候选特征进行维数约简在支持向量回归（SVR）预测中占有重要地位，其学习能力很大程度上依赖特征集的选择.尽管实验表明[1]，支持向量机在先进行特征选择后往往比不进行特征选择的预测效果好，而且能很大程度上提高训练速度，但是要严格地确定特征集大小很困难.近十年来，虽然很多特征选择算法被提出[2-4]，但目前还没有一种能完全确定特征集的方法.

目前适用于SVR的特征选择算法大都基于最大依赖性准则 （Max-Dependence）[5]. 在特征选择中， 最大依赖性准则目的是寻找一个包含m个特征的集合S， 使得该集合与待预测变量y之间存在最大的依赖关系 （依赖关系一般使用互信息来评估），如式（1）所示.

实际操作中，由于候选特征往往是高维的，很难在高维上对公式（1）进行估算.鉴于此，一些学者提出了解决方法.例如MRMR算法[2]，利用最大相关性准则（Max-Relevance）和最小冗余性准则（Min-Redundance）来逼近公式（1）； MRMS算法[3]则利用最小冗余性准则（Min-Redundance）和最大显著性准则（Max-significant）对公式（1）进行概率性估算； MIGS算法[4]同样利用（条件）互信息对公式（1）的值进行估算.尽管使用这些特征选择方法后，SVR能够一定程度地提升学习精度和速度，但仍然无法完全确定真实的特征集.这些方法有一个共同的缺点，如图1所示.

其中，y为需要预测的目标变量，X={x1，x2，x3，x4，x5}为y的候选特征集，且满足图1所示因果网络模型[6].显然，{x2，x3，x4}为y的直接因果特征，即满足y=f（x2，x3，x4）， 所以y可以完全由{x2，x3，x4}确定.实际上，由于在这样的结构里，{x1，x5}对于y的依赖性往往要比{x2，x3，x4}大，现存的特征选择算法一般都会将{x1，x5}首先加入特征集队列里，在其后的交叉验证等方法里也很难将{x1，x5}移除.一方面，这样直接造成了特征集冗余；另一方面，根据每个特征选择算法的各自的机制，有可能会将{x2，x3，x4}其中的点移除.显然，这样都会影响SVR的预测准确率.

与现存的特征选择算法不同，因果网络是一种对可观测数据进行强有力推理的工具，可以方便地表示和分析确定性和概率性的事物.在因果推断的问题中，利用其可以有效地识别与待预测变量有着因果关系的特征. 基于此，提出了一种基于因果网络且适用SVR的特征选择算法. 该算法将传统的基于逼近最大依赖性准则的特征选择算法转移到因果网络的识别上来，直接对要进行预测的目标变量进行因果推断，找出其因果特征集，找到了一种可以确定特征集的方法.仿真数值实验和在应用真实数据集的实验结果表明，该算法应用在SVR模型上，预测的精确度要高于其他特征选择算法.

1 预备知识

1.1 因果网络

因果网络是表示变量间概率依赖关系的一个有向无环图（DAG），其可表示为一个三元组G=（X，E，P）. 其中，X={x1，x2，…，xn}表示该DAG中所有节点的集合.E={e（xi，xj）|xi，xj∈X}表示DAG中每两个节点间单向边的集合，其中e（xi，xj）表示xi，xj间存在依赖关系xi→xj.P={P（xi|paxi）|xi，paxi∈X}是条件概率的集合，其中P（xi|paxi）表示xi的父节点集paxi对xi的概率性影响.因果网络本质上就是联合概率分布P（x1，x2，…，xn）的一种图形化表示.

1.2 d-分离准则

d-分离是描述因果网络节点间关系的一个重要图准则. 设X， Y， Z是DAG中任意3个互不相交的节点的集合，称Z在图G中d-分离节点集X和Y，如果对任意的从X的节点到Y的一个节点的路P均被Z阻断，也就是路径P上存在一个节点xi满足下列其中一个条件：

（1）xi在P上存在碰撞箭头，即→xi←，且xi及其后代节点都不属于Z；

（2）xi在P上不存在碰撞箭头，即→xi→或←xi→，且xi∈Z.

根据d-分离准则的概率密度含义[6]，如果集合X和Y被集合Z d-分离，那么在给定Z情况下X和Y独立.相反地，如果集合X和Y没有被集合Z d-分离，那么给定Z后X，Y是相互依赖的.

2 因果推断与最大依赖性准则

信息理论[7]提供了一个直观的途径去估算变量间的依赖关系，其中互信息是一个关键的概念. 假设待预测变量y有着n个候选特征X={x1，x2，…，xn}，若其中唯一的m个特征组成的集合Sm满足最大依赖性准则maxSmX D（y，Sm），D=I（y；Sm），则选用Sm做特征向量进行SVR预测往往能达到最好的效果[3].而现时大部分的特征选择方法仅仅对最大依赖性进行逼近.由于采用的大都是启发式的搜索方法，如果非因果特征对于y的依赖性较大，很容易在算法的开始阶段就加入了特征集序列. 与传统特征选择算法不同，基于因果网络的因果推断方法可以直接找到满足最大依赖性的特征集.

定理1 如果待预测变量y唯一的m个特征组成的集合Sm满足最大依赖性准则maxSmX D（y，Sm），D=I（y；Sm）， 则Sm不包含y任何的非因果特征.

证 根据d-分离准则的联合概率密度含义[6]，y与任何非因果特征集X都可以被Sm （或Sm的一个子集） D分离，因而有I（y；X|Sm）=0.由于I（y；X|Sm）=I（y；X，Sm）-I（y；Sm），故I（y；X，Sm）=I（y；Sm），即能从X身上获得的关于y的信息，已全部被包含在Z内. 另一方面，由于y与其因果特征集Sm不被任何其他的特征d-分离，有I（y；Sm|X）≥0.事实上，只有当Sm， X之间满足信息无噪声传输且可逆映射关系时，等号才成立.因此，在实际应用上总有I（y；X）≤I（y；Sm）.即若要保持最大依赖性准则，Sm不能包含y的任何非因果特征，否则必存在冗余.

定理2 如果待预测变量y唯一的m个特征组成的集合Sm满足最大依赖性准则maxSmXD（y，Sm），D=I（y；Sm）， 则Sm包含y所有的因果特征.

证 假设x是不包含在Sm内的y的一个因果特征，根据d-分离准则的联合概率含义，y与其因果特征x不被任何其他的特征Sm d-分离，有I（y；x|Sm）>0.由于I（y；x|Sm）=I（y；x，Sm）-I（y；Sm），故I（y；x，Sm）>I（y；Sm），即能从x身上可以获取得到Sm中没有的关于y的信息. 显然这与最大依赖性准则的定义矛盾. 所以Sm包含y了所有的因果特征.

注 定理1和定理2说明了寻找待预测变量的因果特征和寻找满足最大相关性准则的特征集是等价的，因果特征集唯一地满足最大相关性准则，这也是因果推断算法能解决特征选择问题的一个重要理论依据.

3 算法的基本流程

如图2所示，因果推断算法的目的是找出预测变量y的直接因果特征.对于任意一个变量集X={x1，x2，…，xn}， y为待预测变量，用S（y）表示y的特征节点集.这里主要利用基于约束的方法[8-9]对带预测变量y的直接因果特征进行识别.相对于目前的特征选择算法，对因果特征直接进行识别，一定程度可以排除虽然满足最大依赖性准则却非直接关联的特征，同时也从理论上找到了一种可以确定特征个数的方法.原则上，任何因果推断算法均可使用，但不同算法往往有着不同的机制，从而可能会产生不同的结果，在一些情况某些算法可能反而不及基于互信息的特征选择方法下SVR的预测准确率高.如IGCI[10]，ANM[11-12]等算法无法应用于较高维数据.在这里，基于一种具有很好伸缩性、鲁棒性的BUSSM算法[13]的思想，并对其进行改良，使之适合应用于发现因果特征，具体如下.

算法开始时，先令y的特征节点集S（y）={}.

步骤1 应用独立性测试：测试X中y的每一个候选特征{x1，x2，…，xn}和y之间的独立性，若独立性Ind（y；xi）成立，表明xi没有携带任何关于y的信息，即xi不可能y的因果特征，将xi从X中移除.当候选特征较多，非因果基因的移除大大降低了算法的时间耗费，而且有助于提高算法的准确率.

步骤2 将任意的xi∈X加入到S（y），应用条件独立性测试：Ind（y；xi|U），U为S（y）＼xi的任意一个子集合，若条件独立Ind（y；xi|U）成立，表明xi携带的关于y的信息都被包含在U中了，即xi不可能为y的因果特征，则从S（y）中移除特征xi.

步骤3 重复步骤2，直到X中所有特征迭代完，最后得到特征集S（y）.

步骤4 由于特征集里元素按随机顺序加入，因而可能存在非因果特征保留在S（y）中，这时进行进一步的条件独立性测试：对于任意的xi∈S（y），U为S（y）＼xi的任意一个子集合，测试Ind（y；xi|U）.若y，xi被U d-分离，同样表明xi携带的关于y的信息都被包含在U中了，即xi不是y的因果特征，将xi从S（y）中移除.

步骤5 经过以上步骤，得到待预测变量y的特征集S（y），然后结合SVR中惩罚参数C， 核宽度g进行参数寻优，得到最优参数利用SVR模型对目标变量进行预测.

为了方便表述，记上述提出的算法为Causal Feature Selection （CFS），其具体实现方式如下：

CFS算法的时间复杂度分析：该算法的时间复杂度与所含因果特征的个数有关，与加入顺序也有关，下面进行具体分析.

1） 假设y有n个特征，其中仅有一个为因果特征，且为该因果特征被测试的第一个，则在步骤1中，变量数n*T独立性测试的时间复杂度，步骤2和3的时间复杂度因为都是条件集为单哥变量的独立性测试，时间复杂度都略大于O（T），所以最好的情况下，该算法的时间复杂度近似O（n*T）.

2） 假设y有n个特征，都为因果特征，此时节点测试顺序和算法时间复杂度无关，在步骤1中，容易得时间复杂度为O（T）.在步骤2中，S（y）变量数n与变量可能存在的子集个数形成的关系为：n个点的集合的子集个数是2n-1，故其算法复杂度为：O（2n*T），其中T为每次条件独立性测试的时间复杂度，不是恒值，仅为容易表示.步骤3中，由于每次条件集规模一样，同理得算法复杂度为：O（2n*n*T），故该算法的整体时间复杂度为：O（2n*n*T）.

实际上，这两种极端条件都很难出现，在一般情况下，不同对特征变量测试顺序导致的算法运行时间差距不大；另一方面，在正常情况下，算法复杂度也远远没达到O（2n*n*T）.

4 数值实验

数值实验在Matlab 2010b中完成，分别用虚拟网络数据和真实数据集对CFS进行评价.在虚拟网络的数据生成阶段，每个节点的数据由图3中节点的拓扑序列依照函数：y=w1f1（x1）+w2f2（x2）+ε生成.其中w1，w2为每个函数的权值，随机取值于0.3与0.7之间；f1（），f2（）是随机函数，等概率取于常见的几种初等函数{sin x，cos x，ex，x2，x3}；x1，x2为y的父节点，ε为高斯分布的添加噪声.而在真实数据集方面，采用广州某蓄冰供冷站对集运系统的供冷数据对提出的算法进行评估.在算法实现过程中，条件独立性测试使用基于核函数且适用于连续型数据的测试算法KCI-test[14]，阈值δ=0.05.

4.1 虚拟网络实验

首先，利用CFS算法对目标变量y进行特征选择，得到特征集F1={x2，x3，x4}.显然，从图3可以看出，F1满足y因果特征的条件：y=f（x2，x3，x4）.考虑到在这种因果网络结构下，现存的特征选择算法挑选出来的特征集几乎都会包含{x1，x5}.所以，在这部分实验中分别选取4种特征集F1={x2，x3，x4}，F2={x1，x5}，F3={x1，x2，x5}，F4={x1，x2，x3，x4，x5}对目标变量y进行预测.另一方面，考虑到实际上噪声对SVR预测的影响，实验分别以ε={0，0.01，0.02，0.05，0.1，0.2}6种不同程度的噪声进行实验，所有实验均进行1000次，取实验结果的平均值.

如图4所示，以特征集F1和F4进行预测的结果曲线几乎是重合的，但明显要比在F2和F3的情况下要好，其原因是F1和F4都包含了目标变量y的所有直接因果特征.但由于F4的维度明显比其余特征集高，其训练速度比其余久.在候选特征集规模很大的情况下，覆盖所有候选特征基因进行SVR预测往往很难操作.而F1仅仅覆盖了目标变量y的直接因果特征，由于y由其因果特征确定，所以在选用F1的情况下，其准确率不低于其他任何特征集. 同时，也可以看出不同特征对SVR的抗噪声能力不同，F1和F4对应的曲线相对于F2和F4在噪声增加时，预测的准确率下降速度慢.下面将利用真实数据对CFS算法进行进一步的验证.

4.2 真实数据实验

在本节实验中，采用广州某供冷站对集运系统从2011年4月14号到2013年11月11号的943天的供冷数据，针对提出的算法进行评估.其中前800天数据用作训练，后143天数据用作模型检验.在用SVR模型进行预测前，采用CFS算法对候选的16个特征集：{明天最高温度、明天最低温度、明天最高湿度、明天最低湿度、明天平均湿度、昨天最高温度、昨天最低温度、昨天最高湿度、昨天最低湿度、昨天平均湿度、昨天用冷量、两天最高温度差、两天最低温度差、两天最高湿度差、两天最低湿度差、两天平均湿度差}进行特征选择，最终得到特征集为第{1， 2， 5， 7， 11， 14} 6个特征.为了进行算法对比，利用常用的特征选择方法MIGS同样挑选前6个特征，按顺序为{11， 2， 7， 1， 6， 5}.可以看到CFS和MIGS挑选的结果仅有1个不同，这也一定程度显示了CFS的适用性，另外由于全部候选特征仅有16个，这里也全选特征进行对比实验.

由表1可以看出，在准确率上CFS仅微优于全选的结果，由偏差程度对比中也可以看到两者极为接近. 而MIGS所选的6个特征中，由于遗漏了对制冷量有着直接因果关系的特征，因而效果不如前两者的结果.真实实验的结果再一次表明，CFS算法适用于SVR特征选择，能准确地识别带预测变量的直接因果因素.而其他的特征选择算法都仅基于对最大依赖性准则逼近，这些算法在得到的特征序列中，非因果特一般排在了因果特征前面，导致了特征集过大或遗漏因果特征，从而影响了SVR的学习能力.

上述实验表明，CFS算法应用在SVR上有着优良的效果.事实上，虽然因果特征对待预测变量起着决定性作用，但这并等同于一定要包含因果特征的特征集适用于SVR时才能达到最高的准确率.在某些情况下，特征集不包含因果特征，也可能达到不逊于因果特征集的准确率.

CFS算法旨在从理论上将因果网络与特征选择结合起来，并为SVR提供一种可以完全确定特征集的途径.虽然CFS算法从理论上解决了一直无法找到准确特征集的问题，但由于现存的条件独立性测试算法相对于互信息计算对变量的样本量需求更高，在样本量不充分的情况下，应用在SVR上CFS也有可能不及传统的基于互信息的方法，这有待于条件独立性研究的发展.

5 结语

与传统的基于互信息的支持向量回归特征选择不同，本文采取了基于因果网络的特征选择方法，一方面利用条件独立性测试寻找带预测变量的直接关联特征，排除了虽然满足最大依赖性却非直接关联的特征；另一方面也从理论上找到了一种能确定特征个数的方法.文中采用虚拟网络数据和真实数据集进行实验，结果表明该算法应用在支持向量回归预测上优于其他特征选择算法.

参考文献：

[1] CAO L J， CHUA K S， CHONG W K， et al. A comparison of SA， KSA and ICA for dimensionality reduction in support vector machine[J]. Neurocomputing， 2003，55（1）：321-336.

[2] PENG H， LONG F， DING C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy[J]. Patt Anal Machine Intel， IEEE Trans， 2005，27（8）：1226-1238.

[3] MAJI P， GARAI P. On fuzzy-rough attribute selection： criteria of max-dependency， max-relevance， min-redundancy， and max-significance[J]. Appl Soft Comput， 2013，13（9）：3968-3980.

[4] CAI R， HAO Z， YANG X， et al. An efficient gene selection algorithm based on mutual information[J]. Neurocomputing， 2009，72（4）：991-999.

[5] MAJI P， PAUL S. Rough set based maximum relevance-maximum significance criterion and gene selection from microarray data[J]. Int J Approx Reason， 2011，52（3）：408-426.

[6] PEARL J. Causality： models， reasoning and inference[M]. Cambridge： The MIT press， 2000.

[7] COVER T M， THOMAS J A， Elements of Information Theory[M]. New Jersey： Wiley， 2005.

[8] SPIRTES， GLYMOUR C， SCHEINES R. Causation， prediction， and search[M]. Cambridge：The MIT Press， 2000.

[9] TSAMARDINOS I， BROWN L E， ALIFERIS C F. The max-min hill-climbing Bayesian network structure learning algorithm[J]. Machine Learning， 2006，65（1）：31-78.

[10] JANZING D， MOOIJ J， ZHANG K， et al. Information-geometric approach to inferring causal directions[J]. Artif Intell， 2012，56（10）：5168-5194.

[11] HOYER P O， JANZING D， MOOIJ J， et al. Nonlinear causal discovery with additive noise models[C]//Advances in Neural Information Processing Systems. Vancouver， Canada： MIT Press， 2009：689-696.

[12] PETERS J， JANZING D， SCHOLKOPF B. Causal inference on discrete data using additive noise models[J]. IEEE Trans Patt Anal Machine Intell， 2011，33（12）：2436-2450.

[13] CAI R， ZHANG Z， HAO Z. BASSUM： A Bayesian semi-supervised method for classification feature selection[J]. Patt Recog， 2011，44（4）：811-820.

[14] ZHANG K， PETERS J， JANZING D， et al. Kernel-based conditional independence test and application in causal discovery[EB/OL]. （2012-02-14） [2013-10-24]. http：//arxiv.org/ftp/arxiv/papers/1202/1202.3775.pdf.

（编辑 胡文杰）