基于析因設(shè)計(jì)的大數(shù)據(jù)相關(guān)關(guān)系挖掘算法

唐小川，羅 亮

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

0 引言

隨著大數(shù)據(jù)時(shí)代的到來，許多數(shù)據(jù)集具有大量特征和數(shù)據(jù)記錄[1]，比如社交網(wǎng)絡(luò)數(shù)據(jù)和自然語言處理數(shù)據(jù)。文獻(xiàn)[2]指出，這種特征數(shù)量多、數(shù)據(jù)量大的數(shù)據(jù)集為大數(shù)據(jù)分析帶來了巨大的挑戰(zhàn)。對(duì)于這類數(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]對(duì)大數(shù)據(jù)相關(guān)關(guān)系分析方法進(jìn)行了綜述。文獻(xiàn)[5]指出，對(duì)于一些大數(shù)據(jù)分析問題，相關(guān)關(guān)系的結(jié)果就足以解決問題。在機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘領(lǐng)域，特征選擇方法廣泛應(yīng)用于挖掘與目標(biāo)變量相關(guān)的重要特征。

特征選擇算法通?？煞譃槿怺6]：嵌入式(Embedding)、封裝式(Wrapper)和過濾式(Filter)。嵌入式方法將特征選擇作為分類器的一個(gè)組成部分。封裝式方法枚舉所有特征子集，并計(jì)算其分類效果。過濾式方法通過定義一個(gè)評(píng)分標(biāo)準(zhǔn)對(duì)特征進(jìn)行打分排序，最終選擇得分高的特征，文獻(xiàn)[6]提出了一個(gè)過濾式特征選擇算法的框架。相比嵌入式和封裝式方法，過濾式方法的效率更高并且獨(dú)立于具體的分類器，因此，本文研究使用過濾式特征選擇方法挖掘大數(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è)計(jì)的因子效應(yīng)作為一種新的相關(guān)關(guān)系度量標(biāo)準(zhǔn)，用于度量特征和交互作用與目標(biāo)變量的相關(guān)性，從而能對(duì)特征和交互作用進(jìn)行統(tǒng)一排序，通過交互作用提升多變量過濾式特征選擇算法的性能。FFD使用一種分治算法快速地從輸入數(shù)據(jù)集中獲取析因設(shè)計(jì)的結(jié)果，從而提高計(jì)算因子效應(yīng)的速度。

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

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

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

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

文獻(xiàn)[11]提出一種基于析因設(shè)計(jì)的特征選擇算法。本文提出一個(gè)快速的搜索適合輸入數(shù)據(jù)集的最優(yōu)析因設(shè)計(jì)的算法，使得析因設(shè)計(jì)能夠應(yīng)用于大數(shù)據(jù)的特征和交互作用選擇。式(1)是析因設(shè)計(jì)的統(tǒng)計(jì)模型。該模型是一個(gè)包含交互作用項(xià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)。對(duì)于給定的特征，如果該特征的因子效應(yīng)的絕對(duì)值大于其他因子，那么該特征與目標(biāo)變量之間的相關(guān)關(guān)系最強(qiáng)。因此，本文使用因子效應(yīng)作為特征與目標(biāo)變量之間關(guān)聯(lián)性的度量標(biāo)準(zhǔn)。

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

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

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

3)計(jì)算最大的兩水平析因設(shè)計(jì)，使得數(shù)據(jù)集D能夠?yàn)槠涮峁┳銐虻臄?shù)據(jù)。由于析因設(shè)計(jì)與因子數(shù)量一一對(duì)應(yīng)，本文提出一個(gè)搜索最大析因設(shè)計(jì)對(duì)應(yīng)的最大因子數(shù)量的算法：

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

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

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

k← 1

while true do

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

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

…

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

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

(2)

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

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

(3)

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

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

在分析階段，計(jì)算各個(gè)特征和交互作用的因子效應(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)絕對(duì)值的大小可將特征和交互作用排序?yàn)椋?/p>

x2>x1>x1x2

(6)

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

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

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

2 實(shí)驗(yàn)與分析

本文通過實(shí)驗(yàn)對(duì)比了FFD與其他特征選擇方法。實(shí)驗(yàn)采用3個(gè)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)顯式地考慮了交互作用，所以通過線性回歸的分類錯(cuò)誤率對(duì)比不同的特征選擇方法。本文對(duì)比了3個(gè)著名的過濾式特征選擇算法：聯(lián)合互信息最大化(Joint Mutual Information Maximisation, JMIM)算法[14]使用聯(lián)合互信息度量?jī)蓚€(gè)特征和一個(gè)目標(biāo)變量三者之間的交互作用；ReliefF[15]是一種基于相似度的特征選擇算法，利用了特征之間的條件依賴性；互信息最大化(Mutual Information Maximisation, MIM)算法[9]考慮了單個(gè)特征與目標(biāo)變量之間的相關(guān)關(guān)系。

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

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

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

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

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

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

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

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

圖3 BASEHOCK數(shù)據(jù)集上的分類錯(cuò)誤率隨特征數(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è)計(jì)的因子效應(yīng)作為特征與目標(biāo)變量之間的關(guān)聯(lián)性的度量標(biāo)準(zhǔn)。提出一種為輸入數(shù)據(jù)集快速搜索最佳析因設(shè)計(jì)的分治算法，理論分析表明，這個(gè)分治算法的復(fù)雜度為O(lb2n)，有效降低了計(jì)算因子效應(yīng)的復(fù)雜度。為了對(duì)特征和交互作用進(jìn)行統(tǒng)一排序，F(xiàn)FD將因子效應(yīng)作為排序標(biāo)準(zhǔn)。

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