一種基于因果網絡的支持向量回歸特征選擇算法

陳一明

(廣東石油化工學院實驗教學部，中國茂名 525000)

對候選特征進行維數約簡在支持向量回歸(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所示.

圖1 因果網絡模型Fig.1 Causal network model

其中，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滿足最大依賴性準則，則選用Sm做特征向量進行SVR 預測往往能達到最好的效果［3］.而現時大部分的特征選擇方法僅僅對最大依賴性進行逼近.由于采用的大都是啟發式的搜索方法，如果非因果特征對于y 的依賴性較大，很容易在算法的開始階段就加入了特征集序列.與傳統特征選擇算法不同，基于因果網絡的因果推斷方法可以直接找到滿足最大依賴性的特征集.

定理1如果待預測變量y 唯一的m 個特征組成的集合Sm滿足最大依賴性準則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滿足最大依賴性準則Sm)，則Sm包含y 所有的因果特征.

證假設x 是不包含在Sm內的y 的一個因果特征，根據d-分離準則的聯合概率含義，y 與其因果特征x不被任何其他的特征Smd-分離，有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)={}.

圖2 算法的基本框架Fig.2 Algorithm framework

步驟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=w1*f1(x1)+w2*f2(x2)+ε 生成.其中w1，w2為每個函數的權值，隨機取值于0.3 與0.7 之間;f1(*)，f2(*)是隨機函數，等概率取于常見的幾種初等函數{sin x，cos x，ex，x2，x3};x1，x2為y 的父節點，ε 為高斯分布的添加噪聲.而在真實數據集方面，采用廣州某蓄冰供冷站對集運系統的供冷數據對提出的算法進行評估.在算法實現過程中，條件獨立性測試使用基于核函數且適用于連續型數據的測試算法KCI-test［14］，閾值δ=0.05.

圖3 虛擬網絡數據Fig.3 Virtual network dataset

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 在4 種特征集下SVR 算法的預測結果Fig.4 The results of SVR with 4 different feature sets

4.2 真實數據實驗

表1 真實數據集下的實驗結果Tab.1 The results of real world dataset

在本節實驗中，采用廣州某供冷站對集運系統從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 maxsignificance［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.