唐小川，羅 亮

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

0 引言

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

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

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

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

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

1.1 兩水平完全析因設計

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

k← 1

while true do

析因設計的行的數(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ù)量k，避免了將數(shù)據(jù)集D與特征數(shù)量為1到k的所有析因設計進行比較，因此，該算法能快速地找出適合數(shù)據(jù)集D的最大析因設計。

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

…

③構造k階交互作用m2k。令m2k=mi1·mi2·…·mik。

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

(2)

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

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

(3)

在測試階段，為每一個實驗隨機產生兩個響應值，如表1右側兩列所示。

表1 二因子析因設計的設計矩陣和響應值

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

(4)

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

(5)

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

x2>x1>x1x2

(6)

1.3 計算復雜度分析

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

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

2 實驗與分析

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

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

Spambase數(shù)據(jù)集。該數(shù)據(jù)集由4 601條記錄和57個特征組成。圖1是Spambase數(shù)據(jù)集上的實驗結果。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個特征組成。在進行特征選擇之前，本文將PM2.5數(shù)據(jù)集的特征和目標變量離散化為二值變量。對于連續(xù)型變量，使用其平均值將其離散化為二值變量，將高于平均值的項標記為1，低于平均值的項標記為-1。對于一些離散型變量，使用一對多(one-vs-all)分解策略將其離散化為二值變量。對于時間特征，每年(year)被離散化為四個季度，每個月(month)被離散化為兩個半個月，每天(day)被離散化為兩個半天。對于風向特征“wind direction”，離散化為東北(North East, NE)、西北(North West, NW)、東南(South East, SE)和和靜風(Calm and Variable wind, CV)。對于目標變量，設定PM2.5的閾值為75，PM2.5大于75 μg/m3表示空氣受到污染，記為1，否則記為-1。因此，經過離散化以后，得到21個二值變量特征。

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

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

表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 結語

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

實驗結果表明，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ù)集的一個關鍵因素是風速與風向的交互作用，即東南方向的風速可能對北京PM2.5有重要影響。