陳一明

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

對候選特征進行維數(shù)約簡在支持向量回歸(SVR)預(yù)測中占有重要地位，其學(xué)習(xí)能力很大程度上依賴特征集的選擇.盡管實驗表明［1］，支持向量機在先進行特征選擇后往往比不進行特征選擇的預(yù)測效果好，而且能很大程度上提高訓(xùn)練速度，但是要嚴(yán)格地確定特征集大小很困難.近十年來，雖然很多特征選擇算法被提出［2-4］，但目前還沒有一種能完全確定特征集的方法.

目前適用于SVR 的特征選擇算法大都基于最大依賴性準(zhǔn)則(Max-Dependence)［5］.在特征選擇中，最大依賴性準(zhǔn)則目的是尋找一個包含m 個特征的集合S，使得該集合與待預(yù)測變量y 之間存在最大的依賴關(guān)系(依賴關(guān)系一般使用互信息來評估)，如式(1)所示.

實際操作中，由于候選特征往往是高維的，很難在高維上對公式(1)進行估算.鑒于此，一些學(xué)者提出了解決方法.例如MRMR 算法［2］，利用最大相關(guān)性準(zhǔn)則(Max-Relevance)和最小冗余性準(zhǔn)則(Min-Redundance)來逼近公式(1);MRMS 算法［3］則利用最小冗余性準(zhǔn)則(Min-Redundance)和最大顯著性準(zhǔn)則(Max-significant)對公式(1)進行概率性估算;MIGS 算法［4］同樣利用(條件)互信息對公式(1)的值進行估算.盡管使用這些特征選擇方法后，SVR 能夠一定程度地提升學(xué)習(xí)精度和速度，但仍然無法完全確定真實的特征集.這些方法有一個共同的缺點，如圖1所示.

圖1 因果網(wǎng)絡(luò)模型Fig.1 Causal network model

其中，y 為需要預(yù)測的目標(biāo)變量，X={x1，x2，x3，x4，x5}為y 的候選特征集，且滿足圖1所示因果網(wǎng)絡(luò)模型［6］.顯然，{x2，x3，x4}為y 的直接因果特征，即滿足y=f(x2，x3，x4)，所以y 可以完全由{x2，x3，x4}確定.實際上，由于在這樣的結(jié)構(gòu)里，{x1，x5}對于y 的依賴性往往要比{x2，x3，x4}大，現(xiàn)存的特征選擇算法一般都會將{x1，x5}首先加入特征集隊列里，在其后的交叉驗證等方法里也很難將{x1，x5}移除.一方面，這樣直接造成了特征集冗余;另一方面，根據(jù)每個特征選擇算法的各自的機制，有可能會將{x2，x3，x4}其中的點移除.顯然，這樣都會影響SVR 的預(yù)測準(zhǔn)確率.

與現(xiàn)存的特征選擇算法不同，因果網(wǎng)絡(luò)是一種對可觀測數(shù)據(jù)進行強有力推理的工具，可以方便地表示和分析確定性和概率性的事物.在因果推斷的問題中，利用其可以有效地識別與待預(yù)測變量有著因果關(guān)系的特征.基于此，提出了一種基于因果網(wǎng)絡(luò)且適用SVR 的特征選擇算法.該算法將傳統(tǒng)的基于逼近最大依賴性準(zhǔn)則的特征選擇算法轉(zhuǎn)移到因果網(wǎng)絡(luò)的識別上來，直接對要進行預(yù)測的目標(biāo)變量進行因果推斷，找出其因果特征集，找到了一種可以確定特征集的方法.仿真數(shù)值實驗和在應(yīng)用真實數(shù)據(jù)集的實驗結(jié)果表明，該算法應(yīng)用在SVR 模型上，預(yù)測的精確度要高于其他特征選擇算法.

1 預(yù)備知識

1.1 因果網(wǎng)絡(luò)

因果網(wǎng)絡(luò)是表示變量間概率依賴關(guān)系的一個有向無環(huán)圖(DAG)，其可表示為一個三元組G=(X，E，P).其中，X={x1，x2，…，xn}表示該DAG 中所有節(jié)點的集合.E={e(xi，xj)|xi，xj∈X}表示DAG 中每兩個節(jié)點間單向邊的集合，其中e(xi，xj)表示xi，xj間存在依賴關(guān)系xi→xj.P={P(xi|paxi)|xi，paxi∈X}是條件概率的集合，其中P(xi|paxi)表示xi的父節(jié)點集paxi對xi的概率性影響.因果網(wǎng)絡(luò)本質(zhì)上就是聯(lián)合概率分布P(x1，x2，…，xn)的一種圖形化表示.

1.2 d-分離準(zhǔn)則

d-分離是描述因果網(wǎng)絡(luò)節(jié)點間關(guān)系的一個重要圖準(zhǔn)則.設(shè)X，Y，Z 是DAG 中任意3 個互不相交的節(jié)點的集合，稱Z 在圖G 中d-分離節(jié)點集X 和Y，如果對任意的從X 的節(jié)點到Y(jié) 的一個節(jié)點的路P 均被Z 阻斷，也就是路徑P 上存在一個節(jié)點xi滿足下列其中一個條件:

(1)xi在P 上存在碰撞箭頭，即→xi←，且xi及其后代節(jié)點都不屬于Z;

(2)xi在P 上不存在碰撞箭頭，即→xi→或←xi→，且xi∈Z.

根據(jù)d-分離準(zhǔn)則的概率密度含義［6］，如果集合X 和Y 被集合Z d-分離，那么在給定Z 情況下X 和Y 獨立.相反地，如果集合X 和Y 沒有被集合Z d-分離，那么給定Z 后X，Y 是相互依賴的.

2 因果推斷與最大依賴性準(zhǔn)則

信息理論［7］提供了一個直觀的途徑去估算變量間的依賴關(guān)系，其中互信息是一個關(guān)鍵的概念.假設(shè)待預(yù)測變量y 有著n 個候選特征X={x1，x2，…，xn}，若其中唯一的m 個特征組成的集合Sm滿足最大依賴性準(zhǔn)則，則選用Sm做特征向量進行SVR 預(yù)測往往能達到最好的效果［3］.而現(xiàn)時大部分的特征選擇方法僅僅對最大依賴性進行逼近.由于采用的大都是啟發(fā)式的搜索方法，如果非因果特征對于y 的依賴性較大，很容易在算法的開始階段就加入了特征集序列.與傳統(tǒng)特征選擇算法不同，基于因果網(wǎng)絡(luò)的因果推斷方法可以直接找到滿足最大依賴性的特征集.

定理1如果待預(yù)測變量y 唯一的m 個特征組成的集合Sm滿足最大依賴性準(zhǔn)則Sm)，則Sm不包含y 任何的非因果特征.

證根據(jù)d-分離準(zhǔn)則的聯(lián)合概率密度含義［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 身上獲得的關(guān)于y 的信息，已全部被包含在Z 內(nèi).另一方面，由于y 與其因果特征集Sm不被任何其他的特征d-分離，有I(y;Sm|X)≥0.事實上，只有當(dāng)Sm，X 之間滿足信息無噪聲傳輸且可逆映射關(guān)系時，等號才成立.因此，在實際應(yīng)用上總有I(y;X)≤I(y;Sm).即若要保持最大依賴性準(zhǔn)則，Sm不能包含y 的任何非因果特征，否則必存在冗余.

定理2如果待預(yù)測變量y 唯一的m 個特征組成的集合Sm滿足最大依賴性準(zhǔn)則Sm)，則Sm包含y 所有的因果特征.

證假設(shè)x 是不包含在Sm內(nèi)的y 的一個因果特征，根據(jù)d-分離準(zhǔn)則的聯(lián)合概率含義，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中沒有的關(guān)于y 的信息.顯然這與最大依賴性準(zhǔn)則的定義矛盾.所以Sm包含y 了所有的因果特征.

注定理1 和定理2 說明了尋找待預(yù)測變量的因果特征和尋找滿足最大相關(guān)性準(zhǔn)則的特征集是等價的，因果特征集唯一地滿足最大相關(guān)性準(zhǔn)則，這也是因果推斷算法能解決特征選擇問題的一個重要理論依據(jù).

3 算法的基本流程

如圖2所示，因果推斷算法的目的是找出預(yù)測變量y 的直接因果特征.對于任意一個變量集X={x1，x2，…，xn}，y 為待預(yù)測變量，用S(y)表示y 的特征節(jié)點集.這里主要利用基于約束的方法［8-9］對帶預(yù)測變量y的直接因果特征進行識別.相對于目前的特征選擇算法，對因果特征直接進行識別，一定程度可以排除雖然滿足最大依賴性準(zhǔn)則卻非直接關(guān)聯(lián)的特征，同時也從理論上找到了一種可以確定特征個數(shù)的方法.原則上，任何因果推斷算法均可使用，但不同算法往往有著不同的機制，從而可能會產(chǎn)生不同的結(jié)果，在一些情況某些算法可能反而不及基于互信息的特征選擇方法下SVR 的預(yù)測準(zhǔn)確率高.如IGCI［10］，ANM［11-12］等算法無法應(yīng)用于較高維數(shù)據(jù).在這里，基于一種具有很好伸縮性、魯棒性的BUSSM 算法［13］的思想，并對其進行改良，使之適合應(yīng)用于發(fā)現(xiàn)因果特征，具體如下.

算法開始時，先令y 的特征節(jié)點集S(y)={}.

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

步驟1應(yīng)用獨立性測試:測試X 中y 的每一個候選特征{x1，x2，…，xn}和y 之間的獨立性，若獨立性Ind(y;xi)成立，表明xi沒有攜帶任何關(guān)于y 的信息，即xi不可能y 的因果特征，將xi從X 中移除.當(dāng)候選特征較多，非因果基因的移除大大降低了算法的時間耗費，而且有助于提高算法的準(zhǔn)確率.

步驟2將任意的xi∈X 加入到S(y)，應(yīng)用條件獨立性測試:Ind(y;xi|U)，U 為S(y)xi的任意一個子集合，若條件獨立Ind(y;xi|U)成立，表明xi攜帶的關(guān)于y 的信息都被包含在U 中了，即xi不可能為y 的因果特征，則從S(y)中移除特征xi.

步驟3重復(fù)步驟2，直到X 中所有特征迭代完，最后得到特征集S(y).

步驟4由于特征集里元素按隨機順序加入，因而可能存在非因果特征保留在S(y)中，這時進行進一步的條件獨立性測試:對于任意的xi∈S(y)，U 為S(y)xi的任意一個子集合，測試Ind(y;xi|U).若y，xi被U d-分離，同樣表明xi攜帶的關(guān)于y 的信息都被包含在U 中了，即xi不是y 的因果特征，將xi從S(y)中移除.

步驟5經(jīng)過以上步驟，得到待預(yù)測變量y 的特征集S(y)，然后結(jié)合SVR 中懲罰參數(shù)C，核寬度g 進行參數(shù)尋優(yōu)，得到最優(yōu)參數(shù)利用SVR 模型對目標(biāo)變量進行預(yù)測.

為了方便表述，記上述提出的算法為Causal Feature Selection(CFS)，其具體實現(xiàn)方式如下:

CFS 算法的時間復(fù)雜度分析:該算法的時間復(fù)雜度與所含因果特征的個數(shù)有關(guān)，與加入順序也有關(guān)，下面進行具體分析.

1)假設(shè)y 有n 個特征，其中僅有一個為因果特征，且為該因果特征被測試的第一個，則在步驟1 中，變量數(shù)n*T 獨立性測試的時間復(fù)雜度，步驟2 和3 的時間復(fù)雜度因為都是條件集為單哥變量的獨立性測試，時間復(fù)雜度都略大于O(T)，所以最好的情況下，該算法的時間復(fù)雜度近似O(n*T).

2)假設(shè)y 有n 個特征，都為因果特征，此時節(jié)點測試順序和算法時間復(fù)雜度無關(guān)，在步驟1 中，容易得時間復(fù)雜度為O(T).在步驟2 中，S(y)變量數(shù)n 與變量可能存在的子集個數(shù)形成的關(guān)系為:n 個點的集合的子集個數(shù)是2n－1，故其算法復(fù)雜度為:O(2n*T)，其中T 為每次條件獨立性測試的時間復(fù)雜度，不是恒值，僅為容易表示.步驟3 中，由于每次條件集規(guī)模一樣，同理得算法復(fù)雜度為:O(2n*n*T)，故該算法的整體時間復(fù)雜度為:O(2n*n*T).

實際上，這兩種極端條件都很難出現(xiàn)，在一般情況下，不同對特征變量測試順序?qū)е碌乃惴ㄟ\行時間差距不大;另一方面，在正常情況下，算法復(fù)雜度也遠(yuǎn)遠(yuǎn)沒達到O(2n*n*T).

4 數(shù)值實驗

數(shù)值實驗在Matlab 2010b 中完成，分別用虛擬網(wǎng)絡(luò)數(shù)據(jù)和真實數(shù)據(jù)集對CFS進行評價.在虛擬網(wǎng)絡(luò)的數(shù)據(jù)生成階段，每個節(jié)點的數(shù)據(jù)由圖3 中節(jié)點的拓?fù)湫蛄幸勒蘸瘮?shù):y=w1*f1(x1)+w2*f2(x2)+ε 生成.其中w1，w2為每個函數(shù)的權(quán)值，隨機取值于0.3 與0.7 之間;f1(*)，f2(*)是隨機函數(shù)，等概率取于常見的幾種初等函數(shù){sin x，cos x，ex，x2，x3};x1，x2為y 的父節(jié)點，ε 為高斯分布的添加噪聲.而在真實數(shù)據(jù)集方面，采用廣州某蓄冰供冷站對集運系統(tǒng)的供冷數(shù)據(jù)對提出的算法進行評估.在算法實現(xiàn)過程中，條件獨立性測試使用基于核函數(shù)且適用于連續(xù)型數(shù)據(jù)的測試算法KCI-test［14］，閾值δ=0.05.

圖3 虛擬網(wǎng)絡(luò)數(shù)據(jù)Fig.3 Virtual network dataset

4.1 虛擬網(wǎng)絡(luò)實驗

首先，利用CFS 算法對目標(biāo)變量y 進行特征選擇，得到特征集F1={x2，x3，x4}.顯然，從圖3 可以看出，F(xiàn)1滿足y 因果特征的條件:y=f(x2，x3，x4).考慮到在這種因果網(wǎng)絡(luò)結(jié)構(gòu)下，現(xiàn)存的特征選擇算法挑選出來的特征集幾乎都會包含{x1，x5}.所以，在這部分實驗中分別選取4 種特征集F1={x2，x3，x4}，F(xiàn)2={x1，x5}，F(xiàn)3={x1，x2，x5}，F(xiàn)4={x1，x2，x3，x4，x5}對目標(biāo)變量y 進行預(yù)測.另一方面，考慮到實際上噪聲對SVR 預(yù)測的影響，實驗分別以ε={0，0.01，0.02，0.05，0.1，0.2}6 種不同程度的噪聲進行實驗，所有實驗均進行1000次，取實驗結(jié)果的平均值.

如圖4所示，以特征集F1和F4進行預(yù)測的結(jié)果曲線幾乎是重合的，但明顯要比在F2和F3的情況下要好，其原因是F1和F4都包含了目標(biāo)變量y 的所有直接因果特征.但由于F4的維度明顯比其余特征集高，其訓(xùn)練速度比其余久.在候選特征集規(guī)模很大的情況下，覆蓋所有候選特征基因進行SVR 預(yù)測往往很難操作.而F1僅僅覆蓋了目標(biāo)變量y 的直接因果特征，由于y 由其因果特征確定，所以在選用F1的情況下，其準(zhǔn)確率不低于其他任何特征集.同時，也可以看出不同特征對SVR 的抗噪聲能力不同，F(xiàn)1和F4對應(yīng)的曲線相對于F2和F4在噪聲增加時，預(yù)測的準(zhǔn)確率下降速度慢.下面將利用真實數(shù)據(jù)對CFS 算法進行進一步的驗證.

圖4 在4 種特征集下SVR 算法的預(yù)測結(jié)果Fig.4 The results of SVR with 4 different feature sets

4.2 真實數(shù)據(jù)實驗

表1 真實數(shù)據(jù)集下的實驗結(jié)果Tab.1 The results of real world dataset

在本節(jié)實驗中，采用廣州某供冷站對集運系統(tǒng)從2011年4月14 號到2013年11月11 號的943 天的供冷數(shù)據(jù)，針對提出的算法進行評估.其中前800 天數(shù)據(jù)用作訓(xùn)練，后143 天數(shù)據(jù)用作模型檢驗.在用SVR 模型進行預(yù)測前，采用CFS 算法對候選的16 個特征集:{明天最高溫度、明天最低溫度、明天最高濕度、明天最低濕度、明天平均濕度、昨天最高溫度、昨天最低溫度、昨天最高濕度、昨天最低濕度、昨天平均濕度、昨天用冷量、兩天最高溫度差、兩天最低溫度差、兩天最高濕度差、兩天最低濕度差、兩天平均濕度差}進行特征選擇，最終得到特征集為第{1，2，5，7，11，14}6 個特征.為了進行算法對比，利用常用的特征選擇方法MIGS同樣挑選前6 個特征，按順序為{11，2，7，1，6，5}.可以看到CFS 和MIGS 挑選的結(jié)果僅有1 個不同，這也一定程度顯示了CFS 的適用性，另外由于全部候選特征僅有16 個，這里也全選特征進行對比實驗.

由表1 可以看出，在準(zhǔn)確率上CFS 僅微優(yōu)于全選的結(jié)果，由偏差程度對比中也可以看到兩者極為接近.而MIGS 所選的6 個特征中，由于遺漏了對制冷量有著直接因果關(guān)系的特征，因而效果不如前兩者的結(jié)果.真實實驗的結(jié)果再一次表明，CFS 算法適用于SVR 特征選擇，能準(zhǔn)確地識別帶預(yù)測變量的直接因果因素.而其他的特征選擇算法都僅基于對最大依賴性準(zhǔn)則逼近，這些算法在得到的特征序列中，非因果特一般排在了因果特征前面，導(dǎo)致了特征集過大或遺漏因果特征，從而影響了SVR 的學(xué)習(xí)能力.

上述實驗表明，CFS 算法應(yīng)用在SVR 上有著優(yōu)良的效果.事實上，雖然因果特征對待預(yù)測變量起著決定性作用，但這并等同于一定要包含因果特征的特征集適用于SVR 時才能達到最高的準(zhǔn)確率.在某些情況下，特征集不包含因果特征，也可能達到不遜于因果特征集的準(zhǔn)確率.

CFS 算法旨在從理論上將因果網(wǎng)絡(luò)與特征選擇結(jié)合起來，并為SVR 提供一種可以完全確定特征集的途徑.雖然CFS 算法從理論上解決了一直無法找到準(zhǔn)確特征集的問題，但由于現(xiàn)存的條件獨立性測試算法相對于互信息計算對變量的樣本量需求更高，在樣本量不充分的情況下，應(yīng)用在SVR 上CFS 也有可能不及傳統(tǒng)的基于互信息的方法，這有待于條件獨立性研究的發(fā)展.

5 結(jié)語

與傳統(tǒng)的基于互信息的支持向量回歸特征選擇不同，本文采取了基于因果網(wǎng)絡(luò)的特征選擇方法，一方面利用條件獨立性測試尋找?guī)ьA(yù)測變量的直接關(guān)聯(lián)特征，排除了雖然滿足最大依賴性卻非直接關(guān)聯(lián)的特征;另一方面也從理論上找到了一種能確定特征個數(shù)的方法.文中采用虛擬網(wǎng)絡(luò)數(shù)據(jù)和真實數(shù)據(jù)集進行實驗，結(jié)果表明該算法應(yīng)用在支持向量回歸預(yù)測上優(yōu)于其他特征選擇算法.

［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.