基于析因設計的大數據相關關系挖掘算法

唐小川，羅 亮

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

0 引言

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

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

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

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

1 一種大數據特征和交互作用選擇方法

1.1 兩水平完全析因設計

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

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

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

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

(1)

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

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

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

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

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

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

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

輸出：最大因子數量k。

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

k← 1

while true do

析因設計的行的數量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

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

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

…

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

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

(2)

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

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

(3)

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

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

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

(4)

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

(5)

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

x2>x1>x1x2

(6)

1.3 計算復雜度分析

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

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

2 實驗與分析

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

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

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

圖1 Spambase數據集上的分類錯誤率隨特征數量的變化

PM2.5數據集。該數據集記錄了北京市在2010至2014年間的PM2.5數據，由43 824條記錄和13個特征組成。在進行特征選擇之前，本文將PM2.5數據集的特征和目標變量離散化為二值變量。對于連續型變量，使用其平均值將其離散化為二值變量，將高于平均值的項標記為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數據集上的實驗結果。可以看到，隨著已選特征和交互作用數量的增加，FFD的錯誤率逐漸降低，當特征和交互作用大于12時，FFD的錯誤率持續低于其他對比方法。FFD的最低錯誤率為32.72%，低于其他對比方法的最低錯誤率(33.61%)。一個可能的原因是FFD選擇的交互作用具有其他特征所不具備的關鍵信息，比如：交互作用x6x8(風速和東南風之間的交互作用)的重要性排第三，可能對北京PM2.5有顯著的影響。

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

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

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

圖3 BASEHOCK數據集上的分類錯誤率隨特征數量的變化

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

3 結語

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

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