多重屬性過濾深度特征合成算法

王立可，崔小莉，張力戈

1.中國科學院 成都計算機應用研究所，成都610041

2.中國科學院大學，北京100049

3.四川虹信軟件股份有限公司，成都610041

1 引言

近年來，隨著人工智能和大數據等技術的快速發展，可以從大量數據中獲取有價值的信息，利用機器學習等方法可以得到預測模型，且模型構造越來越多地從人工設計階段轉向自動化構造階段，旨在通過尋找適用數據集的最優模型來簡化模型選擇和機器學習調優過程，幾乎不需要任何人工干預[1-2]。然而，特征工程作為機器學習流程中最有價值的一個方面，幾乎完全是人工的，往往需要數據科學家人工地找出最佳的特征組合，在效果及效率上有很大的局限性[3]。

對于不存在實體關聯的結構化數據進行自動特征生成，Cheng等人提出了一種基于知識庫表達圖的自動特征特征向量構造方法，可以在有標記的稀疏數據上進行特征構造[4]；Fawcett等人提出了基于歸納與反饋的特征生成理論，在特定的系統上可以取得較好的效果[5]；Leather等人提出的基于優化編譯的機器學習自動特征算法，能自動找出最能提高機器學習質量的特征，通過從編譯器的內部表示中自動派生出特征語法，使用特定的方法搜索一個特征空間，自動從編譯器的內部表示形式派生出特征語法，得到了顯著優于以前由編譯器專家手動生成的特性[6]；Katz等人提出了ExploreKit特征生成框架，通過結合原始特性中的信息生成大量候選特性，并使用基于機器學習的特征選擇方法來預測新候選特征的有用性[7]。

然而對于結構化的關系型數據，通常表示為一組具有關系鏈接的表，且數據蘊含了人類與復雜系統交互的大量信息，對這種類型的數據建模與特征構造，其過程需要不斷迭代，需要人類的直覺驅動，并且具有挑戰性。深度特征合成（Deep Feature Synthesis，DFS）算法通過引入特征基元等概念，自動為關系數據集生成特征。該算法遵循數據中基本屬性的關系鏈路，然后沿該路徑依次地應用數學函數以創建最終特征。通過順序堆疊計算，每個新特征定義會具有一定深度d。在應用中，每一個關系實體中都存在大量的屬性，深度特征合成算法對實體的屬性進行特征合成之后會產生大量的特征，其中包含部分冗余特征，這些冗余特征難以通過簡單的數據降維方法進行篩選，因為在合成的特征過程中，不重要屬性與重要的屬性融合，產生了迷惑性的特征。

本文提出一種多重屬性過濾的DFS算法，映射連接實體與標記，并基于JSKL散度和Hellinger距離度量實體中屬性的重要程度，多重過濾屬性，拒絕實體中重要程度低的屬性參與深度特征合成算法，實驗結果表明本文方法能夠減少迷惑性特征的產生，降低特征冗余度，生成的特征集合能夠降低后續模型構造的難度，提升模型最終預測準確率。

2 相關工作

2.1 深度特征合成算法

深度特征合成算法的輸入是一組有關系鏈接的實體以及與之關聯的表。表中的每個實體實例都有一個唯一的標識符。實體之間可以通過使用相關實體的唯一標識符來引用相關實體的實例。E1,2,…,K表示給出的實體，其中每個實體具有J個特征。表示第k個實體的第i個實例特征j的值。生成的特征有三種類型，分別是efeat、dfeat、rfeat，在生成dfeat和rfeat類型的特征時是通過聯合分析兩個相關實體El與Ek得出的，這兩個實體存在以下兩種關系之一：

（1）前向關系：存在于實體El的實例m和Ek中另一實體i的單個屬性之間的關系。

（2）后向關系：從EK中的實例i到El中與k具有前向關系的所有實例m={1,2,…,M}的關系。

三種類型的特征計算方式分別為：

（1）efeat：通過計算每個屬性值來獲得特征，這些特征可以通過對xi,j′逐元應用計算函數。這種計算可表示為：

（2）dfeat：應用于關系表中的前向關系。相關實體i∈Ek中的特征被直接轉移為m∈Ek的特征。

算法為給定實體合成的特征數量z由下式給出：

其中，i為遞歸的次數，n與m為前向關系和后向關系的個數，r為rfeat函數的個數，e為efeat函數個數。

2.2 相對熵

相對熵又稱KL散度，相對熵是交叉熵與信息熵的差值，是一種用于描述兩個概率分布差異的方法，可以更實際地反映出事件的概率分布變化，精確地表現細小的差異[8]。設P(x)、Q(x)是隨機變量X上的兩個概率分布，則相對熵表示為：

在離散隨機變量的情形下，相對熵的計算公式為：

在連續隨機變量的情形下，相對熵的計算公式為：

盡管KL散度從直觀上是個度量或距離函數，但它并不是一個真正的度量或者距離，因為它不具有對稱性，即：D(p||q)≠D(q||p)

2.3 Hellinger距離

在概率論和統計理論中，Hellinger距離被用來度量兩個概率分布的相似度。它是f散度的一種。為了從度量理論的角度定義Hellinger距離，假設P和Q是兩個概率測度，并且它們對于第三個概率測度λ來說是絕對連續的，則P和Q的Hellinger距離的平方定義如下：

把上述概率密度函數分別表示為f和g，那么可以用以下的積分形式表示Hellinger距離：

上述等式可以通過展開平方項得到，注意到任何概率密度函數在其定義域上的積分為1。根據柯西-施瓦茨不等式（Cauchy-Schwarz inequality），Hellinger距離滿足0≤H(P,Q)≤1。

對于兩個離散概率分布P=(p1,p2,…,pn)和Q=(q1,q2,…,qn)，它們的Hellinger距離可以定義為：

3 基于KL散度與Hellinger距離散度的多重屬性過濾深度特征合成算法

對一組相關聯的實體，每個實體EK具有1,2,…,J屬性是第k實體的第i實例的屬性j的值。Tag1,2,…,t表示標記值，共有T組標記。若Tag為連續值，先將實體與Tag標記值映射連接，記為Tag→E，且連接時有三種情況：

（1）實體EK直接可以與標記連接映射，即標記位的鍵包含在實體中的屬性中。該類型實體與標記連接后會增加一個Tag標記位。

（2）實體EK不能直接與標記連接映射，但是可以先與其他實體連接后再與標記連接，連接后的實體會增加等同于連接深度大小數量的屬性和一個Tag標記。

（3）實體不能與標記位連接，不做連接，實體結構不改變。

離散屬性j類別數量超過分箱閾值，則對屬性j的值分箱，具體如下：

（1）計算屬性j中的離散值的各個種類概率分布P(p1,p2,…,pk)。

（2）從前到后依次比較概率值pi與1/α的大小，若pi小于1/α，則與后一個概率值pi+1相加再比較，直到結果大于1/α，相加的種類組成一個箱，重復此過程，直到所有的概率值都處理完畢。

（3）分箱后的屬性j計算概率分布P(p1,p2,…,pn)。

分別統計屬性j中離散值各個種類的概率分布Tag1(p1,p2,…,pn),Tag2(p1,p2,…,pn),…,Tagn(p1,p2,…,pn),為處理數據稀疏的情況，概率分布中所有概率值都加上了一個eps值，eps值為默認的最小浮點數精度。對屬性分組后的T組Tag分別計算每組之間距離度量，在使用相對熵度量分布的距時，因為KL散度的不對稱性，所以使用它的改進版本JSKL散度，計算公式為：

可以看出JSKL散度是對稱的，可以用于衡量兩種不同分布之間的差異。假設共有T組Tag，在計算距離度量時，分別計算每一個標記t與非標記t的距離度量，將所有值累加后除以T得到該屬性的距離度量值，因此本文中的JSKL散度值度量值計算公式為：

Hellinger距離度量值計算公式為：

由上述計算得到的度量值集合對實體中大量屬性做重要程度評價，留下重要的屬性值參與深度特征合成算法，JSKL散度值和Hellinger距離體現了該屬性對決策類分布的區分能力，值越大，說明使用該屬性值參與特征合成的結果更重要。在做評價時采用JSKL散度Hellinger結合使用的方法，即同時使用JSKL散度值度量和Hellinger距離度量分布之間的距離，通過調整舍棄因子β確定過濾掉的屬性，舍棄方式是在度量值中找到最大值除以舍棄因子得到比較值，其他屬性的度量值分別與比較值比較，先標記出小于比較值的屬性，這一條件記為(Hmax/Hd＞β,d)。并且舍棄掉在JSKL散度度量和Hellinger距離度量上同時滿足標記條件的屬性。算法主框架描述如下：

輸入：一組實體E1,2,…,K，分箱閾值α，舍棄因子β。

輸出：由互連的實體合成的特征集合F。

1.初始化參數D,C。

2.通過實體間的連接操作Tag→E連接把Tag映射到的實體中去。

3.遍歷E內的實體k執行步驟4～11。

4.將k中屬性分為離散屬性集合D和連續屬性集合C。

5.以頻率1/α對D內的數據等頻分箱，對C內特征的值進行等距分箱，分箱為α等份。

6.計算D內的每個屬性d的概率分布：Tagt+(p1,p2,…,pn),Tagt-(p1,p2,…,pn)，計算C內的每個特征j的概率分布：Tagt+(x1,x2,…,xn)，Tagt-(x1,x2,…,xn)。

7.分別計算屬性d的Tagt+與Tagt-的Hellinger距離均值構成集合Hd,分別計算屬性c的Tagt+與Tagt-的Hellinger距離均值Hc。

8.標記出符合篩選條件的屬性并計算出篩選比例ε，集合D中的條件為(Hmax/Hd＞β,d)，集合C中的條件為(Hmax/Hd＞β,c)。

9.分別計算屬性d的Tagt+與Tagt-的JSKL散度距離度量均值并按照比例ε篩選出距離較大的特集合組成集合Jd，同理按照比例ε篩選出屬性c距離較大的特集合組成集合Jc。

10.合并集合Hd,Jd組成特征集合D=Hd?Jd，同理組成特征集合C=Hc?Jc。

11.將選擇后的實體K的連續特征與離散特征合并Ek=D?C。

12.將新組成的實體集合進行深度特征合成DFS(E1,2,…,K)。

由以上可知本文改進的深度特征合成算法可以通過調整β值來控制參與合成特征的屬性數量，β值越大，參與合成的屬性越多，最終合成的特征數量越多；β值越小，參與合成的屬性越少，最終合成的特征數量越少。對實體進行融合之前篩選特征，舍棄非重要的特征，以免在特征融合的過程中融合成為難以選擇的特征，以達到合成更好的特征的效果。

4 實驗結果與分析

為了驗證本文提出的算法的有效性，本文進行了一系列的實驗，實驗環境如下：Intel?-CoreTMi7-8750U2.20GHz處理器，16 GB運行內存，64位Windows10操作系統，深度特征合成算法使用Python第三方開源包featuretools。

本文采用幾種使用頻率高的分類器模型，具體如下所示：

（1）支持向量機（Support Vector Machine，SVM），指通過升維把低維樣本向高維空間做映射，使原本在低維樣本空間中非線性可分的問題轉化為在特征空間中線性可分的問題，尋找一個超平面來對樣本進行分割。算法的核函數參數均采用默認值[10]。

（2）分類與回歸樹（classification and regression tree，C4.5）算法通過對特征屬性的分類對樣本進行分類的樹形結構。終將具有p維特征的n個樣本分到c個類別中去[11]。

（3）深度神經網絡（Deep Neural Networks，DNN）通過模擬人類大腦的計算單元神經元而產生的一類算法。相當于一個多層感知機，組合輸入的操作是一種非線性函數，只有輸入達到某個閾值的時候，神經元才會生成輸出。并且在輸入值的加權和的基礎上應用了非線性函數。本文實驗構建了一個擁有三層隱藏層的DNN網絡，且迭代次數均達到飽和[12-13]。

本文選擇的實驗數據集均來自國內外競賽或開源的數據集，且均有實際應用場景，分別是：

（1）ACM的SIGKDD組織的2014年度競賽KDDCUP數據集。

（2）DataCastle 2018年甜橙金融杯大數據大賽數據。

（3）數據堂開源國內某B2C電子商務網站真實數據。

本文分別使用改進后的HJDFS算法和原算法進行實驗，且為使實驗結果更有說服性，在使用機器學習模型對算法得到的特征集合訓練時，采用5折交叉驗證實驗對數據集進行測試和評價，并且將原樣本數據順序隨機打亂后得到新的樣本數據后進行實驗。

圖1給出了本文提出的HJDFS算法和原算法DFS在三個數據集上合成特征時耗費時間對比圖，改進的算法對原實體集合做多重屬性過濾，使更少的屬性參與特征合成，時間耗費大幅度減少。改進的HJDFS算法的時間耗費相較于DFS在三個數據集上均有明顯減少，減少比例分別為23.7%、24.4%和40.3%。HJDFS算法不僅在合成特征時具有時間優勢，在對合成的特征使用機器學習算法訓練時，也有明顯優勢。表1給出了算法HJDFS與DFS合成特征及模型訓練時間（min）對比，改進的算法在不同的機器學習模型上均有明顯效率提升，其中在SVM分類器模型上，平均訓練時間減少31.41%，在C4.5分類器模型上，平均訓練時間減少21.87%，在DNN3分類器模型上，平均訓練時間減少21.53%。時間性能的提升可以加快算法反饋效率，成倍增加模型調優的效率，改進的算法在實際應用中具有極高的使用價值。

圖1 DFS和HJDFS在不同數據集上合成特征耗費時間

改進的算法不僅在時間上有優勢，也提升了合成特征的質量及預測準確率。圖2～圖4給出了三個數據集使用HJDFS合成特征集合時β值在不同分類器上的準確率變化，不難看出在不同的數據集上均有一個共同點，隨著β值變大，在分類器上的準確率不斷提高，在準確率達到一定瓶頸后再增大β值，準確率有略微下降，在SVM分類器和DNN3分類器上更明顯。這是因為在實體集中對實體屬性的過濾要求越來越嚴格，最終合成的特征集合中的特征數量越來越多，生成的冗余特征也越來越多，所以本文選取了合適的β值進行實驗，β取無窮大時，即等同于直接使用DFS算法，不對原實體集合的屬性過濾。這說明選取合適的β值使用HJDFS合成特征可以降低合成特征的冗余度，提升預測的準確率，從另一方面來看，由于冗余屬性的減少可以使算法的時間減少。

表1 算法HJDFS與DFS合成特征及模型訓練時間對比 min

圖2 數據集1的β值在不同分類器上的準確率

圖3 數據集2的β值在不同分類器上的準確率

圖4 數據集3的β值在不同分類器上的準確率

表2～表4給出了所選擇3個數據集上不同分類器（SVM、C4.5和DNN3）采用5折交叉驗證法所獲得的分類準確率和特征數。其中DFS是深度特征合成算法生成的特征集合，HJDFS是使用本文提出的改進算法生成的特征集合，同時為了比較算法在相同特征數量上的優劣，在對生成后的特征集合進行了數據清洗和規范后，使用截斷的SVD分解[14-16]對從DFS和HJDFS生成的特集合選擇了相同數量特征，組成了特征集合DFS-SVD和HJDFS-SVD。且根據表2～表4所示的實驗結果，改進的算法HJDFS在三個數據集上所生成特征數量比算法DFS要分別少24.3%、38.9%，和39.3%。算法HJDFS在三種不同分類器上的平均準確率提升分別為0.826%、0.227%和0.275%，在三個數據集上使用SVM分類器的準確率提升為0.771%、0.439%和1.267%，在DNN3分類器上的準確率提升分別為0.546%、0.923%和0.358%，在C4.5分類器上也均有提升。在對DFS和HJDFS使用截斷的SVD分解取得的相同數量的特征集合上，算法HJDFS的準確率提升更加明顯，HJDFS-SVD相較于DFS-SVD在三種不同分類器上的平均準確率提升分別為1.221%、0.674%和0.683%，在三種不同的分類器上均有不同程度的提升，這是因為在DFS算法合成特征的過程中，實體內不重要的屬性與重要的屬性融合，使得合成的特征在普通特征選擇算法上難以區分，從而在對特征集合進行特征提取之后，準確率反而下降。

表2 基于SVM分類器上各特征合成方法的比較

表3 基于C4.5分類器上各特征合成方法的比較

表4 基于DNN3分類器上各特征合成方法的比較

綜上可知，本文提出的HJDFS算法在對特征進行融合之前多重過濾了實體中的部分屬性，降低了合成后特征集合的冗余度，不僅減少了算法合成特征所需要的時間，也減少了算法合成特征集合需要的時間與模型訓練時間，從而加快算法反饋效率，成倍增加模型調優的效率。實驗結果同時表明，改進的算法減少了重要屬性與不重要屬性融合生成迷惑性特征的數量，減小了后續特征處理與數據降維的難度，從而提高了在最終分類器模型上的預測準確率。

5 結束語

自動化特征工程是一項潛力無窮的技術，只有實現了特征自動化，人工智能才可以稱得上是真正的智能，結構化的關系型數據特征構造更是其中一項具有挑戰性的工作。本文使用衡量屬性重要度和多重屬性過濾的方法改進了深度特征融合算法，并對改進算法進行了實驗驗證，實驗結果表明改進算法可以有效過濾實體中冗余屬性，生成更優的特征。如今的海量數據中存在很多文本數據，想要相對這部分數據實現特征融合，需用到自然語言處理相關的知識，在接下來的工作中，將針這些問題進一步展開工作，將該算法推向更廣闊的應用場景。