王立可,崔小莉,張力戈
1.中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所,成都610041
2.中國(guó)科學(xué)院大學(xué),北京100049
3.四川虹信軟件股份有限公司,成都610041
近年來,隨著人工智能和大數(shù)據(jù)等技術(shù)的快速發(fā)展,可以從大量數(shù)據(jù)中獲取有價(jià)值的信息,利用機(jī)器學(xué)習(xí)等方法可以得到預(yù)測(cè)模型,且模型構(gòu)造越來越多地從人工設(shè)計(jì)階段轉(zhuǎn)向自動(dòng)化構(gòu)造階段,旨在通過尋找適用數(shù)據(jù)集的最優(yōu)模型來簡(jiǎn)化模型選擇和機(jī)器學(xué)習(xí)調(diào)優(yōu)過程,幾乎不需要任何人工干預(yù)[1-2]。然而,特征工程作為機(jī)器學(xué)習(xí)流程中最有價(jià)值的一個(gè)方面,幾乎完全是人工的,往往需要數(shù)據(jù)科學(xué)家人工地找出最佳的特征組合,在效果及效率上有很大的局限性[3]。
對(duì)于不存在實(shí)體關(guān)聯(lián)的結(jié)構(gòu)化數(shù)據(jù)進(jìn)行自動(dòng)特征生成,Cheng等人提出了一種基于知識(shí)庫表達(dá)圖的自動(dòng)特征特征向量構(gòu)造方法,可以在有標(biāo)記的稀疏數(shù)據(jù)上進(jìn)行特征構(gòu)造[4];Fawcett等人提出了基于歸納與反饋的特征生成理論,在特定的系統(tǒng)上可以取得較好的效果[5];Leather等人提出的基于優(yōu)化編譯的機(jī)器學(xué)習(xí)自動(dòng)特征算法,能自動(dòng)找出最能提高機(jī)器學(xué)習(xí)質(zhì)量的特征,通過從編譯器的內(nèi)部表示中自動(dòng)派生出特征語法,使用特定的方法搜索一個(gè)特征空間,自動(dòng)從編譯器的內(nèi)部表示形式派生出特征語法,得到了顯著優(yōu)于以前由編譯器專家手動(dòng)生成的特性[6];Katz等人提出了ExploreKit特征生成框架,通過結(jié)合原始特性中的信息生成大量候選特性,并使用基于機(jī)器學(xué)習(xí)的特征選擇方法來預(yù)測(cè)新候選特征的有用性[7]。
然而對(duì)于結(jié)構(gòu)化的關(guān)系型數(shù)據(jù),通常表示為一組具有關(guān)系鏈接的表,且數(shù)據(jù)蘊(yùn)含了人類與復(fù)雜系統(tǒng)交互的大量信息,對(duì)這種類型的數(shù)據(jù)建模與特征構(gòu)造,其過程需要不斷迭代,需要人類的直覺驅(qū)動(dòng),并且具有挑戰(zhàn)性。深度特征合成(Deep Feature Synthesis,DFS)算法通過引入特征基元等概念,自動(dòng)為關(guān)系數(shù)據(jù)集生成特征。該算法遵循數(shù)據(jù)中基本屬性的關(guān)系鏈路,然后沿該路徑依次地應(yīng)用數(shù)學(xué)函數(shù)以創(chuàng)建最終特征。通過順序堆疊計(jì)算,每個(gè)新特征定義會(huì)具有一定深度d。在應(yīng)用中,每一個(gè)關(guān)系實(shí)體中都存在大量的屬性,深度特征合成算法對(duì)實(shí)體的屬性進(jìn)行特征合成之后會(huì)產(chǎn)生大量的特征,其中包含部分冗余特征,這些冗余特征難以通過簡(jiǎn)單的數(shù)據(jù)降維方法進(jìn)行篩選,因?yàn)樵诤铣傻奶卣鬟^程中,不重要屬性與重要的屬性融合,產(chǎn)生了迷惑性的特征。
本文提出一種多重屬性過濾的DFS算法,映射連接實(shí)體與標(biāo)記,并基于JSKL散度和Hellinger距離度量實(shí)體中屬性的重要程度,多重過濾屬性,拒絕實(shí)體中重要程度低的屬性參與深度特征合成算法,實(shí)驗(yàn)結(jié)果表明本文方法能夠減少迷惑性特征的產(chǎn)生,降低特征冗余度,生成的特征集合能夠降低后續(xù)模型構(gòu)造的難度,提升模型最終預(yù)測(cè)準(zhǔn)確率。
深度特征合成算法的輸入是一組有關(guān)系鏈接的實(shí)體以及與之關(guān)聯(lián)的表。表中的每個(gè)實(shí)體實(shí)例都有一個(gè)唯一的標(biāo)識(shí)符。實(shí)體之間可以通過使用相關(guān)實(shí)體的唯一標(biāo)識(shí)符來引用相關(guān)實(shí)體的實(shí)例。E1,2,…,K表示給出的實(shí)體,其中每個(gè)實(shí)體具有J個(gè)特征。表示第k個(gè)實(shí)體的第i個(gè)實(shí)例特征j的值。生成的特征有三種類型,分別是efeat、dfeat、rfeat,在生成dfeat和rfeat類型的特征時(shí)是通過聯(lián)合分析兩個(gè)相關(guān)實(shí)體El與Ek得出的,這兩個(gè)實(shí)體存在以下兩種關(guān)系之一:
(1)前向關(guān)系:存在于實(shí)體El的實(shí)例m和Ek中另一實(shí)體i的單個(gè)屬性之間的關(guān)系。
(2)后向關(guān)系:從EK中的實(shí)例i到El中與k具有前向關(guān)系的所有實(shí)例m={1,2,…,M}的關(guān)系。
三種類型的特征計(jì)算方式分別為:
(1)efeat:通過計(jì)算每個(gè)屬性值來獲得特征,這些特征可以通過對(duì)xi,j′逐元應(yīng)用計(jì)算函數(shù)。這種計(jì)算可表示為:
(2)dfeat:應(yīng)用于關(guān)系表中的前向關(guān)系。相關(guān)實(shí)體i∈Ek中的特征被直接轉(zhuǎn)移為m∈Ek的特征。
算法為給定實(shí)體合成的特征數(shù)量z由下式給出:
其中,i為遞歸的次數(shù),n與m為前向關(guān)系和后向關(guān)系的個(gè)數(shù),r為rfeat函數(shù)的個(gè)數(shù),e為efeat函數(shù)個(gè)數(shù)。
相對(duì)熵又稱KL散度,相對(duì)熵是交叉熵與信息熵的差值,是一種用于描述兩個(gè)概率分布差異的方法,可以更實(shí)際地反映出事件的概率分布變化,精確地表現(xiàn)細(xì)小的差異[8]。設(shè)P(x)、Q(x)是隨機(jī)變量X上的兩個(gè)概率分布,則相對(duì)熵表示為:
在離散隨機(jī)變量的情形下,相對(duì)熵的計(jì)算公式為:
在連續(xù)隨機(jī)變量的情形下,相對(duì)熵的計(jì)算公式為:
盡管KL散度從直觀上是個(gè)度量或距離函數(shù),但它并不是一個(gè)真正的度量或者距離,因?yàn)樗痪哂袑?duì)稱性,即:D(p||q)≠D(q||p)
在概率論和統(tǒng)計(jì)理論中,Hellinger距離被用來度量?jī)蓚€(gè)概率分布的相似度。它是f散度的一種。為了從度量理論的角度定義Hellinger距離,假設(shè)P和Q是兩個(gè)概率測(cè)度,并且它們對(duì)于第三個(gè)概率測(cè)度λ來說是絕對(duì)連續(xù)的,則P和Q的Hellinger距離的平方定義如下:
把上述概率密度函數(shù)分別表示為f和g,那么可以用以下的積分形式表示Hellinger距離:
上述等式可以通過展開平方項(xiàng)得到,注意到任何概率密度函數(shù)在其定義域上的積分為1。根據(jù)柯西-施瓦茨不等式(Cauchy-Schwarz inequality),Hellinger距離滿足0≤H(P,Q)≤1。
對(duì)于兩個(gè)離散概率分布P=(p1,p2,…,pn)和Q=(q1,q2,…,qn),它們的Hellinger距離可以定義為:
對(duì)一組相關(guān)聯(lián)的實(shí)體,每個(gè)實(shí)體EK具有1,2,…,J屬性是第k實(shí)體的第i實(shí)例的屬性j的值。Tag1,2,…,t表示標(biāo)記值,共有T組標(biāo)記。若Tag為連續(xù)值,先將實(shí)體與Tag標(biāo)記值映射連接,記為Tag→E,且連接時(shí)有三種情況:
(1)實(shí)體EK直接可以與標(biāo)記連接映射,即標(biāo)記位的鍵包含在實(shí)體中的屬性中。該類型實(shí)體與標(biāo)記連接后會(huì)增加一個(gè)Tag標(biāo)記位。
(2)實(shí)體EK不能直接與標(biāo)記連接映射,但是可以先與其他實(shí)體連接后再與標(biāo)記連接,連接后的實(shí)體會(huì)增加等同于連接深度大小數(shù)量的屬性和一個(gè)Tag標(biāo)記。
(3)實(shí)體不能與標(biāo)記位連接,不做連接,實(shí)體結(jié)構(gòu)不改變。
離散屬性j類別數(shù)量超過分箱閾值,則對(duì)屬性j的值分箱,具體如下:
(1)計(jì)算屬性j中的離散值的各個(gè)種類概率分布P(p1,p2,…,pk)。
(2)從前到后依次比較概率值pi與1/α的大小,若pi小于1/α,則與后一個(gè)概率值pi+1相加再比較,直到結(jié)果大于1/α,相加的種類組成一個(gè)箱,重復(fù)此過程,直到所有的概率值都處理完畢。
(3)分箱后的屬性j計(jì)算概率分布P(p1,p2,…,pn)。
分別統(tǒng)計(jì)屬性j中離散值各個(gè)種類的概率分布Tag1(p1,p2,…,pn),Tag2(p1,p2,…,pn),…,Tagn(p1,p2,…,pn),為處理數(shù)據(jù)稀疏的情況,概率分布中所有概率值都加上了一個(gè)eps值,eps值為默認(rèn)的最小浮點(diǎn)數(shù)精度。對(duì)屬性分組后的T組Tag分別計(jì)算每組之間距離度量,在使用相對(duì)熵度量分布的距時(shí),因?yàn)镵L散度的不對(duì)稱性,所以使用它的改進(jìn)版本JSKL散度,計(jì)算公式為:
可以看出JSKL散度是對(duì)稱的,可以用于衡量?jī)煞N不同分布之間的差異。假設(shè)共有T組Tag,在計(jì)算距離度量時(shí),分別計(jì)算每一個(gè)標(biāo)記t與非標(biāo)記t的距離度量,將所有值累加后除以T得到該屬性的距離度量值,因此本文中的JSKL散度值度量值計(jì)算公式為:
Hellinger距離度量值計(jì)算公式為:
由上述計(jì)算得到的度量值集合對(duì)實(shí)體中大量屬性做重要程度評(píng)價(jià),留下重要的屬性值參與深度特征合成算法,JSKL散度值和Hellinger距離體現(xiàn)了該屬性對(duì)決策類分布的區(qū)分能力,值越大,說明使用該屬性值參與特征合成的結(jié)果更重要。在做評(píng)價(jià)時(shí)采用JSKL散度Hellinger結(jié)合使用的方法,即同時(shí)使用JSKL散度值度量和Hellinger距離度量分布之間的距離,通過調(diào)整舍棄因子β確定過濾掉的屬性,舍棄方式是在度量值中找到最大值除以舍棄因子得到比較值,其他屬性的度量值分別與比較值比較,先標(biāo)記出小于比較值的屬性,這一條件記為(Hmax/Hd>β,d)。并且舍棄掉在JSKL散度度量和Hellinger距離度量上同時(shí)滿足標(biāo)記條件的屬性。算法主框架描述如下:
輸入:一組實(shí)體E1,2,…,K,分箱閾值α,舍棄因子β。
輸出:由互連的實(shí)體合成的特征集合F。
1.初始化參數(shù)D,C。
2.通過實(shí)體間的連接操作Tag→E連接把Tag映射到的實(shí)體中去。
3.遍歷E內(nèi)的實(shí)體k執(zhí)行步驟4~11。
4.將k中屬性分為離散屬性集合D和連續(xù)屬性集合C。
5.以頻率1/α對(duì)D內(nèi)的數(shù)據(jù)等頻分箱,對(duì)C內(nèi)特征的值進(jìn)行等距分箱,分箱為α等份。
6.計(jì)算D內(nèi)的每個(gè)屬性d的概率分布:Tagt+(p1,p2,…,pn),Tagt-(p1,p2,…,pn),計(jì)算C內(nèi)的每個(gè)特征j的概率分布:Tagt+(x1,x2,…,xn),Tagt-(x1,x2,…,xn)。
7.分別計(jì)算屬性d的Tagt+與Tagt-的Hellinger距離均值構(gòu)成集合Hd,分別計(jì)算屬性c的Tagt+與Tagt-的Hellinger距離均值Hc。
8.標(biāo)記出符合篩選條件的屬性并計(jì)算出篩選比例ε,集合D中的條件為(Hmax/Hd>β,d),集合C中的條件為(Hmax/Hd>β,c)。
9.分別計(jì)算屬性d的Tagt+與Tagt-的JSKL散度距離度量均值并按照比例ε篩選出距離較大的特集合組成集合Jd,同理按照比例ε篩選出屬性c距離較大的特集合組成集合Jc。
10.合并集合Hd,Jd組成特征集合D=Hd?Jd,同理組成特征集合C=Hc?Jc。
11.將選擇后的實(shí)體K的連續(xù)特征與離散特征合并Ek=D?C。
12.將新組成的實(shí)體集合進(jìn)行深度特征合成DFS(E1,2,…,K)。
由以上可知本文改進(jìn)的深度特征合成算法可以通過調(diào)整β值來控制參與合成特征的屬性數(shù)量,β值越大,參與合成的屬性越多,最終合成的特征數(shù)量越多;β值越小,參與合成的屬性越少,最終合成的特征數(shù)量越少。對(duì)實(shí)體進(jìn)行融合之前篩選特征,舍棄非重要的特征,以免在特征融合的過程中融合成為難以選擇的特征,以達(dá)到合成更好的特征的效果。
為了驗(yàn)證本文提出的算法的有效性,本文進(jìn)行了一系列的實(shí)驗(yàn),實(shí)驗(yàn)環(huán)境如下:Intel?-CoreTMi7-8750U2.20GHz處理器,16 GB運(yùn)行內(nèi)存,64位Windows10操作系統(tǒng),深度特征合成算法使用Python第三方開源包featuretools。
本文采用幾種使用頻率高的分類器模型,具體如下所示:
(1)支持向量機(jī)(Support Vector Machine,SVM),指通過升維把低維樣本向高維空間做映射,使原本在低維樣本空間中非線性可分的問題轉(zhuǎn)化為在特征空間中線性可分的問題,尋找一個(gè)超平面來對(duì)樣本進(jìn)行分割。算法的核函數(shù)參數(shù)均采用默認(rèn)值[10]。
(2)分類與回歸樹(classification and regression tree,C4.5)算法通過對(duì)特征屬性的分類對(duì)樣本進(jìn)行分類的樹形結(jié)構(gòu)。終將具有p維特征的n個(gè)樣本分到c個(gè)類別中去[11]。
(3)深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Networks,DNN)通過模擬人類大腦的計(jì)算單元神經(jīng)元而產(chǎn)生的一類算法。相當(dāng)于一個(gè)多層感知機(jī),組合輸入的操作是一種非線性函數(shù),只有輸入達(dá)到某個(gè)閾值的時(shí)候,神經(jīng)元才會(huì)生成輸出。并且在輸入值的加權(quán)和的基礎(chǔ)上應(yīng)用了非線性函數(shù)。本文實(shí)驗(yàn)構(gòu)建了一個(gè)擁有三層隱藏層的DNN網(wǎng)絡(luò),且迭代次數(shù)均達(dá)到飽和[12-13]。
本文選擇的實(shí)驗(yàn)數(shù)據(jù)集均來自國(guó)內(nèi)外競(jìng)賽或開源的數(shù)據(jù)集,且均有實(shí)際應(yīng)用場(chǎng)景,分別是:
(1)ACM的SIGKDD組織的2014年度競(jìng)賽KDDCUP數(shù)據(jù)集。
(2)DataCastle 2018年甜橙金融杯大數(shù)據(jù)大賽數(shù)據(jù)。
(3)數(shù)據(jù)堂開源國(guó)內(nèi)某B2C電子商務(wù)網(wǎng)站真實(shí)數(shù)據(jù)。
本文分別使用改進(jìn)后的HJDFS算法和原算法進(jìn)行實(shí)驗(yàn),且為使實(shí)驗(yàn)結(jié)果更有說服性,在使用機(jī)器學(xué)習(xí)模型對(duì)算法得到的特征集合訓(xùn)練時(shí),采用5折交叉驗(yàn)證實(shí)驗(yàn)對(duì)數(shù)據(jù)集進(jìn)行測(cè)試和評(píng)價(jià),并且將原樣本數(shù)據(jù)順序隨機(jī)打亂后得到新的樣本數(shù)據(jù)后進(jìn)行實(shí)驗(yàn)。
圖1給出了本文提出的HJDFS算法和原算法DFS在三個(gè)數(shù)據(jù)集上合成特征時(shí)耗費(fèi)時(shí)間對(duì)比圖,改進(jìn)的算法對(duì)原實(shí)體集合做多重屬性過濾,使更少的屬性參與特征合成,時(shí)間耗費(fèi)大幅度減少。改進(jìn)的HJDFS算法的時(shí)間耗費(fèi)相較于DFS在三個(gè)數(shù)據(jù)集上均有明顯減少,減少比例分別為23.7%、24.4%和40.3%。HJDFS算法不僅在合成特征時(shí)具有時(shí)間優(yōu)勢(shì),在對(duì)合成的特征使用機(jī)器學(xué)習(xí)算法訓(xùn)練時(shí),也有明顯優(yōu)勢(shì)。表1給出了算法HJDFS與DFS合成特征及模型訓(xùn)練時(shí)間(min)對(duì)比,改進(jìn)的算法在不同的機(jī)器學(xué)習(xí)模型上均有明顯效率提升,其中在SVM分類器模型上,平均訓(xùn)練時(shí)間減少31.41%,在C4.5分類器模型上,平均訓(xùn)練時(shí)間減少21.87%,在DNN3分類器模型上,平均訓(xùn)練時(shí)間減少21.53%。時(shí)間性能的提升可以加快算法反饋效率,成倍增加模型調(diào)優(yōu)的效率,改進(jìn)的算法在實(shí)際應(yīng)用中具有極高的使用價(jià)值。
圖1 DFS和HJDFS在不同數(shù)據(jù)集上合成特征耗費(fèi)時(shí)間
改進(jìn)的算法不僅在時(shí)間上有優(yōu)勢(shì),也提升了合成特征的質(zhì)量及預(yù)測(cè)準(zhǔn)確率。圖2~圖4給出了三個(gè)數(shù)據(jù)集使用HJDFS合成特征集合時(shí)β值在不同分類器上的準(zhǔn)確率變化,不難看出在不同的數(shù)據(jù)集上均有一個(gè)共同點(diǎn),隨著β值變大,在分類器上的準(zhǔn)確率不斷提高,在準(zhǔn)確率達(dá)到一定瓶頸后再增大β值,準(zhǔn)確率有略微下降,在SVM分類器和DNN3分類器上更明顯。這是因?yàn)樵趯?shí)體集中對(duì)實(shí)體屬性的過濾要求越來越嚴(yán)格,最終合成的特征集合中的特征數(shù)量越來越多,生成的冗余特征也越來越多,所以本文選取了合適的β值進(jìn)行實(shí)驗(yàn),β取無窮大時(shí),即等同于直接使用DFS算法,不對(duì)原實(shí)體集合的屬性過濾。這說明選取合適的β值使用HJDFS合成特征可以降低合成特征的冗余度,提升預(yù)測(cè)的準(zhǔn)確率,從另一方面來看,由于冗余屬性的減少可以使算法的時(shí)間減少。
表1 算法HJDFS與DFS合成特征及模型訓(xùn)練時(shí)間對(duì)比 min
圖2 數(shù)據(jù)集1的β值在不同分類器上的準(zhǔn)確率
圖3 數(shù)據(jù)集2的β值在不同分類器上的準(zhǔn)確率
圖4 數(shù)據(jù)集3的β值在不同分類器上的準(zhǔn)確率
表2~表4給出了所選擇3個(gè)數(shù)據(jù)集上不同分類器(SVM、C4.5和DNN3)采用5折交叉驗(yàn)證法所獲得的分類準(zhǔn)確率和特征數(shù)。其中DFS是深度特征合成算法生成的特征集合,HJDFS是使用本文提出的改進(jìn)算法生成的特征集合,同時(shí)為了比較算法在相同特征數(shù)量上的優(yōu)劣,在對(duì)生成后的特征集合進(jìn)行了數(shù)據(jù)清洗和規(guī)范后,使用截?cái)嗟腟VD分解[14-16]對(duì)從DFS和HJDFS生成的特集合選擇了相同數(shù)量特征,組成了特征集合DFS-SVD和HJDFS-SVD。且根據(jù)表2~表4所示的實(shí)驗(yàn)結(jié)果,改進(jìn)的算法HJDFS在三個(gè)數(shù)據(jù)集上所生成特征數(shù)量比算法DFS要分別少24.3%、38.9%,和39.3%。算法HJDFS在三種不同分類器上的平均準(zhǔn)確率提升分別為0.826%、0.227%和0.275%,在三個(gè)數(shù)據(jù)集上使用SVM分類器的準(zhǔn)確率提升為0.771%、0.439%和1.267%,在DNN3分類器上的準(zhǔn)確率提升分別為0.546%、0.923%和0.358%,在C4.5分類器上也均有提升。在對(duì)DFS和HJDFS使用截?cái)嗟腟VD分解取得的相同數(shù)量的特征集合上,算法HJDFS的準(zhǔn)確率提升更加明顯,HJDFS-SVD相較于DFS-SVD在三種不同分類器上的平均準(zhǔn)確率提升分別為1.221%、0.674%和0.683%,在三種不同的分類器上均有不同程度的提升,這是因?yàn)樵贒FS算法合成特征的過程中,實(shí)體內(nèi)不重要的屬性與重要的屬性融合,使得合成的特征在普通特征選擇算法上難以區(qū)分,從而在對(duì)特征集合進(jìn)行特征提取之后,準(zhǔn)確率反而下降。
表2 基于SVM分類器上各特征合成方法的比較
表3 基于C4.5分類器上各特征合成方法的比較
表4 基于DNN3分類器上各特征合成方法的比較
綜上可知,本文提出的HJDFS算法在對(duì)特征進(jìn)行融合之前多重過濾了實(shí)體中的部分屬性,降低了合成后特征集合的冗余度,不僅減少了算法合成特征所需要的時(shí)間,也減少了算法合成特征集合需要的時(shí)間與模型訓(xùn)練時(shí)間,從而加快算法反饋效率,成倍增加模型調(diào)優(yōu)的效率。實(shí)驗(yàn)結(jié)果同時(shí)表明,改進(jìn)的算法減少了重要屬性與不重要屬性融合生成迷惑性特征的數(shù)量,減小了后續(xù)特征處理與數(shù)據(jù)降維的難度,從而提高了在最終分類器模型上的預(yù)測(cè)準(zhǔn)確率。
自動(dòng)化特征工程是一項(xiàng)潛力無窮的技術(shù),只有實(shí)現(xiàn)了特征自動(dòng)化,人工智能才可以稱得上是真正的智能,結(jié)構(gòu)化的關(guān)系型數(shù)據(jù)特征構(gòu)造更是其中一項(xiàng)具有挑戰(zhàn)性的工作。本文使用衡量屬性重要度和多重屬性過濾的方法改進(jìn)了深度特征融合算法,并對(duì)改進(jìn)算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證,實(shí)驗(yàn)結(jié)果表明改進(jìn)算法可以有效過濾實(shí)體中冗余屬性,生成更優(yōu)的特征。如今的海量數(shù)據(jù)中存在很多文本數(shù)據(jù),想要相對(duì)這部分?jǐn)?shù)據(jù)實(shí)現(xiàn)特征融合,需用到自然語言處理相關(guān)的知識(shí),在接下來的工作中,將針這些問題進(jìn)一步展開工作,將該算法推向更廣闊的應(yīng)用場(chǎng)景。