唐小川，羅 亮

(電子科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，成都 611731)

0 引言

隨著大數(shù)據(jù)時代的到來，許多數(shù)據(jù)集具有大量特征和數(shù)據(jù)記錄[1]，比如社交網(wǎng)絡(luò)數(shù)據(jù)和自然語言處理數(shù)據(jù)。文獻(xiàn)[2]指出，這種特征數(shù)量多、數(shù)據(jù)量大的數(shù)據(jù)集為大數(shù)據(jù)分析帶來了巨大的挑戰(zhàn)。對于這類數(shù)據(jù)，傳統(tǒng)的因果關(guān)系分析可能變得十分困難，復(fù)雜度更低的相關(guān)關(guān)系分析[3]迎來了新的機(jī)遇。變量之間的相關(guān)關(guān)系是指目標(biāo)變量與特征之間的關(guān)聯(lián)性，文獻(xiàn)[4]對大數(shù)據(jù)相關(guān)關(guān)系分析方法進(jìn)行了綜述。文獻(xiàn)[5]指出，對于一些大數(shù)據(jù)分析問題，相關(guān)關(guān)系的結(jié)果就足以解決問題。在機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域，特征選擇方法廣泛應(yīng)用于挖掘與目標(biāo)變量相關(guān)的重要特征。

特征選擇算法通?？煞譃槿怺6]：嵌入式(Embedding)、封裝式(Wrapper)和過濾式(Filter)。嵌入式方法將特征選擇作為分類器的一個組成部分。封裝式方法枚舉所有特征子集，并計算其分類效果。過濾式方法通過定義一個評分標(biāo)準(zhǔn)對特征進(jìn)行打分排序，最終選擇得分高的特征，文獻(xiàn)[6]提出了一個過濾式特征選擇算法的框架。相比嵌入式和封裝式方法，過濾式方法的效率更高并且獨立于具體的分類器，因此，本文研究使用過濾式特征選擇方法挖掘大數(shù)據(jù)相關(guān)關(guān)系。

文獻(xiàn)[7]將過濾式特征選擇方法分為單變量算法和多變量算法。單變量方法的效率高但是忽略特征之間的依賴性，比如信息增益(Information Gain, IG)[8]。多變量算法使用特征之間的依賴性提升了特征選擇的效果，比如：文獻(xiàn)[9]提出的互信息最大化算法考慮了相關(guān)性；文獻(xiàn)[10]提出的一種改進(jìn)的最大相關(guān)最小冗余算法考慮了條件冗余性；文獻(xiàn)[11]提出的一種兩階段特征選擇算法考慮了特征之間的交互作用，但是，多變量方法的復(fù)雜度較高，難以直接應(yīng)用于大數(shù)據(jù)分析。

本文的主要內(nèi)容如下：提出一種快速的多變量過濾式特征選擇算法FFD(Full Factorial Design)，用于挖掘大數(shù)據(jù)中與目標(biāo)變量關(guān)聯(lián)性強(qiáng)的特征和交互作用。FFD將析因設(shè)計的因子效應(yīng)作為一種新的相關(guān)關(guān)系度量標(biāo)準(zhǔn)，用于度量特征和交互作用與目標(biāo)變量的相關(guān)性，從而能對特征和交互作用進(jìn)行統(tǒng)一排序，通過交互作用提升多變量過濾式特征選擇算法的性能。FFD使用一種分治算法快速地從輸入數(shù)據(jù)集中獲取析因設(shè)計的結(jié)果，從而提高計算因子效應(yīng)的速度。

1 一種大數(shù)據(jù)特征和交互作用選擇方法

1.1 兩水平完全析因設(shè)計

兩水平完全析因設(shè)計FFD廣泛應(yīng)用于統(tǒng)計學(xué)實驗設(shè)計(Design of Experiments, DOE)，實驗設(shè)計研究如何制定實驗計劃和分析實驗結(jié)果[12]。傳統(tǒng)的實驗設(shè)計方法是一種模型驅(qū)動的方法，主要包括三個階段：設(shè)計、測試和分析。在設(shè)計階段，制定最有效的實驗計劃；在測試階段，按照實驗計劃做實驗；在分析階段，使用統(tǒng)計學(xué)工具分析實驗結(jié)果。

1.2 基于析因設(shè)計的特征和交互作用選擇

文獻(xiàn)[11]提出一種基于析因設(shè)計的特征選擇算法。本文提出一個快速的搜索適合輸入數(shù)據(jù)集的最優(yōu)析因設(shè)計的算法，使得析因設(shè)計能夠應(yīng)用于大數(shù)據(jù)的特征和交互作用選擇。式(1)是析因設(shè)計的統(tǒng)計模型。該模型是一個包含交互作用項的一般線性模型(General Linear Model, GLM)。

f(x1,x2,…,xp)=β1x1+β2x2+β3x3+…+β12x1x2+β13x1x3+…+β123x1x2x3+…+ε

(1)

其中:x1,x2,x3,…表示特征；x1x2,x1x3,x1x2x3,…表示交互作用；ε表示隨機(jī)誤差。特征和交互作用常被稱為因子。

式(1)中的系數(shù)β表示因子與目標(biāo)變量之間的關(guān)聯(lián)性，常被稱為因子效應(yīng)。對于給定的特征，如果該特征的因子效應(yīng)的絕對值大于其他因子，那么該特征與目標(biāo)變量之間的相關(guān)關(guān)系最強(qiáng)。因此，本文使用因子效應(yīng)作為特征與目標(biāo)變量之間關(guān)聯(lián)性的度量標(biāo)準(zhǔn)。

本文提出一種快速計算因子效應(yīng)的方法，該方法是一種數(shù)據(jù)驅(qū)動的方法，克服了由模型驅(qū)動的析因設(shè)計方法需要手動執(zhí)行實驗的局限性。該方法也說明了為輸入數(shù)據(jù)集搜索最優(yōu)析因設(shè)計的過程，具體如下：

1)用特征排序方法對X中的所有特征進(jìn)行排序，比如對稱不確定性[13]和最大互信息[9]。

2)將X中的所有特征都轉(zhuǎn)化為二值變量，比如：對于連續(xù)性特征，使用該特征的均值將其劃分為高(+1)和低(-1)兩個水平。這個過程常被稱為二值化。

3)計算最大的兩水平析因設(shè)計，使得數(shù)據(jù)集D能夠為其提供足夠的數(shù)據(jù)。由于析因設(shè)計與因子數(shù)量一一對應(yīng)，本文提出一個搜索最大析因設(shè)計對應(yīng)的最大因子數(shù)量的算法：

輸入：數(shù)據(jù)集D，其中的特征已經(jīng)排序和二值化。

輸出：最大因子數(shù)量k。

index[0]←{1,2,…,n}

k← 1

while true do

析因設(shè)計的行的數(shù)量nrun← 2k

k←k+1

//將index[i]劃分為兩部分：

temp_index[2i] ← 找出所有的s0∈index[i]，

滿足D[s0][k]==-1

temp_index[2i+1]← 找出所有的s1∈index[i]，

滿足D[s1][k]==1

end for

iftemp_index中有元素為空 then

break

else

index←temp_index

end if

end while

該算法使用分治法搜索最大析因設(shè)計對應(yīng)的特征數(shù)量k，避免了將數(shù)據(jù)集D與特征數(shù)量為1到k的所有析因設(shè)計進(jìn)行比較，因此，該算法能快速地找出適合數(shù)據(jù)集D的最大析因設(shè)計。

①生成單個特征mi,i∈{1,2,…,k}。mi的值開始于-1，然后切換為1，…，依此類推，每隔N/2i個元素切換一次正負(fù)號。

…

③構(gòu)造k階交互作用m2k。令m2k=mi1·mi2·…·mik。

因此，可以通過式(2)計算因子效應(yīng)，其中wi(i∈{1,2,…,k})是mi的權(quán)重系數(shù)，表示單個特征的因子效應(yīng)；wj(j∈{k+1,k+2,…,N})是mj的權(quán)重，表示交互作用的因子效應(yīng)，從而可以通過因子效應(yīng)對特征和交互作用進(jìn)行統(tǒng)一排序。

(2)

下面舉例說明如何使用FFD分析兩個因子x1、x2和交互作用x1x2。

在設(shè)計階段，生成一個設(shè)計矩陣，如表1的左側(cè)3列所示，得到設(shè)計矩陣M如下：

(3)

在測試階段，為每一個實驗隨機(jī)產(chǎn)生兩個響應(yīng)值，如表1右側(cè)兩列所示。

表1 二因子析因設(shè)計的設(shè)計矩陣和響應(yīng)值

在分析階段，計算各個特征和交互作用的因子效應(yīng)。由表1右側(cè)2列的每一行分別求平均值可得平均響應(yīng)值為：

(4)

因此，根據(jù)式(2)可得因子效應(yīng)為：

(5)

從而x1，x2和x1x2的因子效應(yīng)分別為-0.271 1，0.355 2和0.106 3。按因子效應(yīng)絕對值的大小可將特征和交互作用排序為：

x2>x1>x1x2

(6)

1.3 計算復(fù)雜度分析

輸入數(shù)據(jù)D∈Rn×p由n條記錄和p個特征組成，適合數(shù)據(jù)集D的最大的兩水平析因設(shè)計由k個因子組成，k的上界為O(lbn)。

搜索最大析因設(shè)計的復(fù)雜度為O(2nk)，即O(2nlbn)。

2 實驗與分析

本文通過實驗對比了FFD與其他特征選擇方法。實驗采用3個UCI(University of California Irvine Machine Learning Repository)數(shù)據(jù)集，包括細(xì)顆粒物數(shù)據(jù)集(Beijing Particulate Matter 2.5，PM2.5)、垃圾郵件數(shù)據(jù)集(Spambase)和文本分類數(shù)據(jù)集(Baseball vs. Hockey, BASEHOCK)。由于本文提供的方法已經(jīng)顯式地考慮了交互作用，所以通過線性回歸的分類錯誤率對比不同的特征選擇方法。本文對比了3個著名的過濾式特征選擇算法：聯(lián)合互信息最大化(Joint Mutual Information Maximisation, JMIM)算法[14]使用聯(lián)合互信息度量兩個特征和一個目標(biāo)變量三者之間的交互作用；ReliefF[15]是一種基于相似度的特征選擇算法，利用了特征之間的條件依賴性；互信息最大化(Mutual Information Maximisation, MIM)算法[9]考慮了單個特征與目標(biāo)變量之間的相關(guān)關(guān)系。

本文的實驗配置[16]如下。首先，使用十折交叉驗證將數(shù)據(jù)隨機(jī)劃分為訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)。然后對數(shù)據(jù)進(jìn)行二值化。其次，用特征選擇方法選擇k={2,4,…,50}個特征或交互作用，并更新數(shù)據(jù)集。交互作用的值可由向量的對應(yīng)分量的乘積得到，可視為一個新特征。再次，用訓(xùn)練數(shù)據(jù)訓(xùn)練線性回歸模型，然后用得到的模型在測試數(shù)據(jù)上得到分類錯誤率。最后，計算十折交叉驗證的平均分類錯誤率。

Spambase數(shù)據(jù)集。該數(shù)據(jù)集由4 601條記錄和57個特征組成。圖1是Spambase數(shù)據(jù)集上的實驗結(jié)果。FFD的錯誤率一直低于其他對比方法。FFD的最低錯誤率是9.06%，其他方法的最低錯誤率是11.89%，F(xiàn)FD將錯誤率降低了2.83個百分點。一個可能的原因是FFD選擇的交互作用具備單個特征所不具備的信息，比如二階交互作用x7x53。

圖1 Spambase數(shù)據(jù)集上的分類錯誤率隨特征數(shù)量的變化

PM2.5數(shù)據(jù)集。該數(shù)據(jù)集記錄了北京市在2010至2014年間的PM2.5數(shù)據(jù)，由43 824條記錄和13個特征組成。在進(jìn)行特征選擇之前，本文將PM2.5數(shù)據(jù)集的特征和目標(biāo)變量離散化為二值變量。對于連續(xù)型變量，使用其平均值將其離散化為二值變量，將高于平均值的項標(biāo)記為1，低于平均值的項標(biāo)記為-1。對于一些離散型變量，使用一對多(one-vs-all)分解策略將其離散化為二值變量。對于時間特征，每年(year)被離散化為四個季度，每個月(month)被離散化為兩個半個月，每天(day)被離散化為兩個半天。對于風(fēng)向特征“wind direction”，離散化為東北(North East, NE)、西北(North West, NW)、東南(South East, SE)和和靜風(fēng)(Calm and Variable wind, CV)。對于目標(biāo)變量，設(shè)定PM2.5的閾值為75，PM2.5大于75 μg/m3表示空氣受到污染，記為1，否則記為-1。因此，經(jīng)過離散化以后，得到21個二值變量特征。

圖2是PM2.5數(shù)據(jù)集上的實驗結(jié)果?？梢钥吹?，隨著已選特征和交互作用數(shù)量的增加，F(xiàn)FD的錯誤率逐漸降低，當(dāng)特征和交互作用大于12時，F(xiàn)FD的錯誤率持續(xù)低于其他對比方法。FFD的最低錯誤率為32.72%，低于其他對比方法的最低錯誤率(33.61%)。一個可能的原因是FFD選擇的交互作用具有其他特征所不具備的關(guān)鍵信息，比如：交互作用x6x8(風(fēng)速和東南風(fēng)之間的交互作用)的重要性排第三，可能對北京PM2.5有顯著的影響。

BASEHOCK數(shù)據(jù)集。該數(shù)據(jù)集由1 993條記錄和4 862個特征組成。圖3是BASEHOCK數(shù)據(jù)集上的實驗結(jié)果。FFD的錯誤率一直低于對比方法，F(xiàn)FD將最低錯誤率降低了5.07個百分點。一個可能的原因是FFD選擇的交互作用(比如二階交互作用x2965x3302)具備其他方法所忽略的關(guān)鍵信息。

表2對比了FFD與其他算法的分類錯誤率。FFD分別將MIM、JMIM和ReliefF的平均錯誤率降低了2.95、3.33和6.62個百分點。FFD在Spambase、PM2.5和BASAHOCK數(shù)據(jù)集上的最低錯誤率都低于對比方法。

圖2 PM2.5數(shù)據(jù)集上的分類錯誤率隨特征數(shù)量的變化

圖3 BASEHOCK數(shù)據(jù)集上的分類錯誤率隨特征數(shù)量的變化

Tab. 2 Comparison of lowest classification error rate for each feature selection algorithm %

3 結(jié)語

本文提出了一種新的過濾式特征選擇方法FFD用于大數(shù)據(jù)相關(guān)關(guān)系分析。FFD使用析因設(shè)計的因子效應(yīng)作為特征與目標(biāo)變量之間的關(guān)聯(lián)性的度量標(biāo)準(zhǔn)。提出一種為輸入數(shù)據(jù)集快速搜索最佳析因設(shè)計的分治算法，理論分析表明，這個分治算法的復(fù)雜度為O(lb2n)，有效降低了計算因子效應(yīng)的復(fù)雜度。為了對特征和交互作用進(jìn)行統(tǒng)一排序，F(xiàn)FD將因子效應(yīng)作為排序標(biāo)準(zhǔn)。

實驗結(jié)果表明，F(xiàn)FD在數(shù)據(jù)集BASEHOCK、Spambase和PM2.5數(shù)據(jù)集上的最低錯誤率分別比其他對比方法低5.07、2.83和0.89個百分點，也就是將實驗中的所有數(shù)據(jù)集的最低錯誤率降低了2.93個百分點。FFD成功地發(fā)現(xiàn)了影響PM2.5數(shù)據(jù)集的一個關(guān)鍵因素是風(fēng)速與風(fēng)向的交互作用，即東南方向的風(fēng)速可能對北京PM2.5有重要影響。