基于強化學習的特征工程算法研究*

謝 斌 ，林珊玲 ，林志賢 ，郭太良

（1.福州大學 物理與信息工程學院，福建 福州 350116；2.中國福建光電信息科學與技術創新實驗室，福建 福州 350116；3.福州大學 先進制造學院，福建 泉州 362200）

0 引言

機器學習廣泛應用于人們的日常生活中，其中預測分析廣泛應用于多個領域的決策，包括欺詐檢測[1-2]、在線廣告[3-4]、風險管理、市場營銷等。預測模型是采用監督學習算法來進行預測，通過歷史數據進行訓練分類或者回歸模型來預測未知的結果，以起到決策的作用。數據的表示方法對于模型的準確度十分重要，原始的數據空間往往難以表達數據。因此，在模型構建之前對數據進行適當的處理及轉換是必不可少的。

特征工程的主要目的就是改變預測建模的特征以更好地適應算法的訓練，通過生成那些判別性高的特征來提高模型訓練的準確度。在現實中，特征工程是由數據科學家手動和根據領域知識來進行的，這一過程往往是十分繁瑣且耗時的[5]，而且很容易產生錯誤和偏差。

本文提出一種基于強化學習（RL）的方法進行特征工程，通過強化學習的相關方法從原始的數據中學習有效的策略。探索有效策略的過程無需人為的操作，通過算法自動學習得到。

1 相關工作

現有的特征工程的方法分為兩種，一種使用數值變換方法進行特征工程。數據科學機（DSM）[6]提出和開發了深度特征綜合算法，自動地為那些有關系的數據集生成特征；ExploreKit[7]通過原始特征中的信息來組合生成大量的候選特征，并提出了一種新穎的基于機器學習的特征選擇方法；NARGESIAN U[8]提出訓練一組神經網絡，來預測對分類性能產生積極影響的轉換。KHURANA U[9]通過對過去的示例進行強化學習，得出一種高效的探索策略；Cognit[10]系統以分層且非窮舉的方式探索各種特征構造選擇，通過貪婪的探索策略最大化模型的準確性；AutoCross[11]是用在表數據上的數據特征組合的方法，利用集束搜索策略構建有效的特征組合。

另一種是通過深度學習的方法來學習有用的特征。深度學習的方法在視頻、圖像以及語音等數據上取得巨大的成功，但是深度學習的方法往往需要大量的數據以避免過擬合，且其學習到的特征往往不可解釋。

2 強化學習進行特征工程

本文的第一個貢獻是將特征工程作為一個馬爾可夫決策過程（MDP），令D0代表原始的特征空間，則狀態空間S 就是經過一系列數字變換后形成的特征空間的集合。動作空間A 是一系列的數值變換方法（如sin、cos、log 等）的集合。當前特征空間D 經過特征變換a 后，新的特征空間D*=a（D），a∈A。

特征工程的主要目的是對原始數據進行一系列處理以獲得最高的精度，所以MDP 過程中最終狀態的獎勵就是最終的特征空間與原始的特征空間的精度的差值，用Acc（D）來表示，令Π*作為在每一個狀態選擇動作的MDP 策略，DΠ代表從原始特征空間跟隨Π*策略生成最終的特征空間。因此，Π*的作用就是使得Acc（DΠ）最大化，即在最終的狀態空間獲得最大的精度。

根據Bellman 的最優性原理[12]，將最優值函數V*定義為：

所以最佳的策略Π*（D）可以定義為：

雖然上述的Π*可以得到最優的特征空間，但是狀態空間S 的數量是指數級別的，處理起來將會十分困難。因此，本文第二個貢獻是在上限置信區間算法（UCT）[13]的基礎上提出一個近似的方法，使其可以用于進行二分類數值數據的特征工程，進而獲得最優策略的近似值。

3 上限置信區間算法（UCT）

UCT 是一種蒙特卡洛樹搜索算法，可以權衡勘探與利用，以探索最有希望的區域。算法分為4 個步驟：

（1）選擇：從根節點開始，使用樹策略即UCB 公式來挑選一個子節點，直到挑選到葉子節點。

（2）擴展：對選定的葉子節點，將葉子節點采取非試探性的動作可以達到的節點加入該葉子節點的子節點中。

（3）模擬：從當前選擇的節點，根據預演策略來進行動作的選擇直到模擬結束，得到的是一次蒙特卡洛實驗并獲得獎勵值。

（4）回溯：用模擬過程得到的獎勵值來更新當前節點及其所有的父親節點的狀態。

樹策略（UCB）[14]公式為：

其中，TF是節點F 的訪問次數，A 是可供選擇的動作空間，uF，a表示節點F 選擇動作a 時獲得的平均獎勵，tF，a表示節點F 選擇動作a 的次數。參數Ce可用來控制勘探強度。

4 基于UCT 的特征工程

本文將特征工程視作蒙特卡洛樹搜索過程，圖1 為整體的結構示意圖，圖中只畫出了3 層的結構圖，動作空間為log、cos、sqrt。圖中橢圓代表一個節點，每一個節點代表著不同版本的數據。節點與節點之間的連線代表選擇的動作，狀態空間就是這些節點的集合。其中D0是原始的特征空間也就是根節點，從根節點出發，每進行一次特征變換就會得到一個子節點。這樣隨著層數的不斷增加，探索空間也呈現爆炸性增長。因此，遍歷所有的節點是非常昂貴且不現實的，因此本文在UCT 的基礎上提出求解最佳策略的方法，以此來權衡探索與利用。

圖1 整體結構示意圖

本文在UCT 基礎上提出一種近似方法，使其可以適用于特征工程。在UCT 中是根據平均收益來選擇子節點。這在解決特征工程的問題并不是很適用，平均收益高的節點可以說明當前特征空間的特征是相對較好的，可能對于某些特征只有經過特定的變換才能獲得較好的精度，但是在探索的過程中由于進行其他一些降低精度的變換，拉低了這個節點的獎勵值，從而導致最終沒有選擇這個節點。因此，本文提出方法中節點中不僅維護了平均獎勵、訪問的次數，還維護了模擬過程中得到的最大的收益。在選擇子節點時，根據子節點的最大收益值來進行選擇。本文設定的實驗結束的條件是達到最大的層數或者選擇了停止動作。在達到最大的層數之前可能就已經獲得了最佳的結果，停止動作的設立是為了避免這種情況發生。

接下來的部分是對本文在UCT 算法基礎上提出的近似方法的介紹以及獎勵函數、特征變換、模擬策略的描述。

4.1 獎勵函數的設定

蒙特卡洛搜索要求每次迭代都要計算獎勵值。獎勵函數的主要目的就是判斷變換的有效性，因此將最終的特征空間與原始特征空間的精度的差值作為獎勵。設Ac 為特征空間的精度，本文計算的精度為FScore。D 為最終的特征空間，D0為原始的特征空間，則獎勵R 可以表示為：

4.2 特征變換的設定（transform）

在進行特征變換時，設A 為動作空間，a∈A 為當前選擇的動作，Di為當前的特征空間，則新的特征空間D*可以表示為：

特征變換都是對適合于當前選擇的動作的特征進行變換。

在每次特征變換后通過特征篩選將特征的數量與原始特征空間保持一致，這樣既可以使用判別性高的特征來創建高階特征，又可以有效避免特征爆炸的問題。

4.3 模擬策略（evaluate）

本文設定的模擬策略為貪婪的策略，設A 為動作空間，D*為當前的特征空間。模擬策略Π*可以表示為：

在UCT 算法中模擬過程的節點往往是不會保存下來的，但是本文最終是根據子節點的最大收益來選擇子節點。為了確保可以找到模擬過程中獲得最大收益的路徑，因此將模擬過程達到的節點全都保存下來。由于本文設定的是貪婪的模擬策略，需要昂貴計算代價，因此將模擬過程的節點保存下來在一定程度上會加快整體的計算速度。

（1）算法1 選擇動作（get_act）

（2）算法2 本文近似算法

4.4 方法概述

算法1 展示了在每一層選擇子節點的算法。通過UCB 公式來權衡探索與利用，以此來搜索最有希望的區域，同時在這過程中保存獲得最大收益。最終通過最大的收益來選擇子節點。這里判斷循環結束的條件就是連續超過10 次選擇相同的子節點或者達到最大的迭代次數。算法2 展示了本文提出的近似算法。在每一層通過算法1 來選擇子節點，直到到達最終層或者挑選到停止動作。

5 實驗和結果

本實驗在5 個公開數據集上進行，驗證本文提出方法的有效性。表1 列出了本文使用的5 個二分類數據集的名稱、來源、記錄數和特征的數量。

表1 本文使用5 個公開數據集的來源、記錄數以及特征數量

所有的實驗結果都是在5 折交叉驗證下得到的，本文使用的模型是隨機森林，模型的參數全部都是默認的參數。對于所有的數據集ce全部設為1.0。蒙特卡洛搜索樹的最大層數設置為10 層，動作空間有：對數、開三次方、平方、開平方、標準化、歸一化、S 函數、正弦、余弦、雙曲函數、分桶、相加、相乘、停止14 種變換方法。在這些變換方法中相加和相乘的操作是對特征空間中的兩兩特征進行相加與相乘,停止操作就是不進行任何操作，返回原來的特征空間。

在實驗中，比較了5 個方面的精度：（1）原始數據集；（2）本文的方法；（3）將所有特征變換方法都用在原始的特征空間后進行特征篩選；（4） 隨機選擇動作進行特征變換，重復進行10 次；（5）選擇使當前特征空間獲得最高精度的特征變換，重復進行10 次。比較結果如表2 所示。

表2 各個數據集在五個方面的精度（FScore）比較

本文還與其他兩篇有限元變換的特征工程文獻[9-10]進行比較。這兩篇文獻和本文類似，都是使用數值變換來進行特征工程。文獻[9]通過線性逼近的Q_learning[15]來從過去的示例來學習策略，而文獻[10]則是使用制定好的策略。本文通過UCT 框架探索最佳的策略。本文使用FScore 提升量來進行比較，表3 中精度提升量以文獻[9]為基準。

表3 本文方法與文獻[9]、[10]FScore 提升量的比較

從表2 可以看出，本文提出的方法在5 個數據集原本的FScore 上平均提高了9.032%，在與其他變換方式進行比較時也是最好的。從表3 可以看出，本文提出的方法在除了German Credit 的數據集外，提升的精度是最高的。圖2 展示了5 個數據集的FScore 與變換次數之間的關系，圖中有些數據集變換不足10 次的原因是選擇停止動作導致實驗提前結束。對于搜索到最大層數的數據集的曲線走向整體上是朝上的，即使中間有較大的起伏，但是在最終層總能獲得最高的精度。隨著最大層數的加深，精度可能會進一步提升。最終層的特征的數量與原始特征空間的特征數量保持一致，在相同的特征數量下精度卻得到了大幅度提升，說明本文提出的方法可以得到判別性高的特征，提高模型的學習能力，又能避免特征爆炸的問題，達到特征工程的目的。

圖2 精度（FScore）與變換次數之間的關系

6 結論

本文中提出以一個新穎的思路將特征工程視作馬爾可夫決策過程（MDP），在UCT 基礎上提出一種特征工程的最佳策略的求解方法。本文提出的方法可以自動找到那些具有高判別性的特征，同時又避免了特征爆炸的問題，在5 個數據集上均取得了較好的效果。本文提出的方法目前只實現了二分類的數值數據的特征工程，還未支持多分類以及回歸數據。由于采用的是貪婪模擬策略，所需要的計算代價比較昂貴，也有可能陷入局部最優的情況。未來可以通過深度蒙特卡洛的方法作為特征工程求解的方法，將深度學習的方法與蒙特卡洛的方法相結合來實現特征工程。