Python — 特徵選擇之CFS (Correlation-based Feature Selection)

基於相關性的特徵選擇 (Correlation-based Feature Selection ,CFS)，是機器學習特徵選擇中，Filter 的一個方法，通常會搭配最佳搜尋演算法 (Best First Search ,BFS) 一起實現。

Photo by Jerry Zhang on Unsplash

筆者最近在研究不同類型的變量對應到特徵選擇之方法，在閱讀大量 paper 後，偶然發現 CFS 結合 BFS 的方法，心想也沒多難就將此其實現了出來。雖然最後又找到效率更高的方法，不過為了不浪費當初找一大堆資料的努力，還是決定寫成文章，希望能幫助到更多的人。

本篇文章關於 CFS 的部分，引用自 “Correlation-based Feature Selection for Discrete and Numeric Class Machine Learning” 和 “An analysis on new hybrid parameter selection model performance over big data set” 兩篇 paper，已有將連結附在最底下，關於內容如有不對的地方，歡迎指正！

以下正文開始～

What’s Feature Selection?

於機器學習的流程中，特徵選擇(Feature Selection) 是接在特徵工程 (Feature Engineering) 之後的，特徵工程除了資料清洗(Data Cleansing) 和資料預處理(Data Preprocessing) 外，也包含建立新的特徵。

而特徵選擇的主要目的為從整理過資料集全部的特徵中，尋找最優的特徵子集(Optimal Feature Subset)，進而避免模型訓練時因不相關或冗餘特徵太多，造成維度詛咒(Curse of Dimensionality) 或是過度擬合(Overfitting) 的情況，可知特徵選擇和模型訓練成功與否有非常大的關係。

除了特徵選擇之外，另一種提高模型精確度的方法為降低維度(Dimension Reduction) 的操作，其最常見的方法為 PCA 降維；需注意的是特徵選擇和降維並不相同，雖然意義上都是減少原始特徵集，但降維會使資料喪失可解釋性，而特徵選擇不會改變特徵的內容。

特徵選擇方法

基本的特徵選擇方法分有三大面向，分別為過濾法(Filter)、包裝法(Wrapper) 和嵌入法(Embedded)。

• 過濾法：依據資料的發散性和特徵與目標變量的相關性對各個特徵進行評分，其評分方式如卡方檢定、Pearson 相關係數、F 檢定等等，並設定門檻值或是預選取特徵之個數來決定最佳特徵集合。Filter 的缺點是只能應用於離散變量的特徵選擇問題中。
• 包裝法：為特徵選擇和演算法訓練同時進行的方法，通常以一目標函式作為標準來選取特徵，而不是直接設定一評估指標。典型的目標函式為遞迴特徵消除法(Recursive feature elimination ,RFE)，常用模型有 Decision Tree、SVM、KNN。此方法和其他兩者差異為，Filter 和 Embedded 是一次訓練便可解決全部問題，但 Wrapper 需使用特徵子集合多次訓練，故運行時間是最長、資源利用最多的。
• 嵌入法：同時考量特徵之間的關係與預期將要使用的模型，建模的同時也在做特徵選擇。其類似於 Filter，但是是通過訓練來決定特徵的優劣。

Correlation-based Feature Selection

CFS 的理念是採用啟發式的方式找尋最優的特徵子集(Optimal Feature Subset)，其假設必須為：子及內個別特徵與目標變量高度相關，但是特徵彼此不相關。

CFS 的評價函數公式， Merit 如下：

其中：

• rcf ：feature-feature 的平均 correlation。
• rff ：class-feature 的平均 correlation。

注意：這裡的rcf跟rff指的是全部rcf的平均跟全部rff的平均，但因打不出來平均符號，故請讀者們自己想像一下。

不同特徵變量下衡量相關性的方法

不同特徵變量下，欲計算 feature-feature 的 correlation 均會使用到不同的相關性計算方法。

• features 均為離散變量(Discrete Variables)，使用對稱不確定性(Symmetrical Uncertainty) 作為 feature 間相關性的衡量標準，其公式為：

• features 均為連續變量(Continuous Variables)，使用 Standard Linear (Pearson’s) Correlation 作為 feature 間相關性的衡量標準，其公式為：

補：scikit-learn其實有CFS相關的套件，但其是基於Symmetrical Uncertainty進行設計的，換言之只能針對離散型的變量進行使用而已。

Best First Search

要了解最佳搜索演算法(Best First Search) 就必須先瞭解前向選擇法(Forward Selection) 跟後向選擇法(Backward Selection)。

• Forward Selection：始於一無特徵的集合，然後貪心地增加特徵，直到沒有合適的特徵加入為止。
• Backward Selection：始於一有全部特徵的集合，然後每次去除一個特徵，直到評價值不再降低為止。

BFS 和 FS、BS 兩種搜索法差不多，可開始於空集合，亦可開始於全集合。

CFS + BFS 之步驟說明

(1) 計算 feature-feature 的 correlation。

(2) 計算 class-feature 的 correlation。

(3) 計算各個單一 feature 的 Merit 值。

(4) 產生一預計成為 Optimal Feature Subset 的空集合 S，優先選擇 Merit 值最大的特徵加入 S。

(5) 以當前的 S 為主，依序加入下一個 Merit 最大的 feature 進入 S，並計算所有 S 的 Merit，且保留最大的那個，結果即是當前最佳 S。

(6) 重複步驟 (5) ，直到找出 Optimal Feature Subset。

Python 實作開始

本次實作之資料採用 UCI 的 Algerian Forest Fires Dataset，其資料是由 Algerian 的兩個地區組成的，分別為 Algerian 東北部的 Bejaia 和西北部的 Sidi-Bel Abbes，那本次實作只會演示 Bejaia 的部分。

Read Data

讀取 Algerian Forest Fires Dataset 資料集中的 Bejaia。

Data Preprocessing

首先進行 data preprocessing，資料中 day-month-year 其實是將原日期紀錄分開而已，而 Classes 是為一 binary 變量，由 0,1 組成。

(1) 將特徵 year 去除，因整筆資料其均發生於 2012 年，判斷上是為冗餘特徵；

(2) 將特徵 day 和特徵 month 合併，兩者特徵原都為離散變量，而整體數據以連續變量為主，故將兩筆合併成為一新特徵 days，變成連續變量，方便之後計算 correlaiton，days 內的特徵從原本 [1, 30] 和 [6,7,8,9] 的區間變成 [1, 365]。其轉換原理如下：

ex:
   month   day                            days
01   6      1      ---> 31*3 + 30*2 + 1  = 154 
02   7      15     ---> 31*3 + 30*3 + 15 = 198

(3) 將 Classes 內的資料轉換為數值型態，從原本的 [ “not fire”, “fire” ] 轉為 binary 的 (0,1) 型態。

• 以下為資料轉換後的結果：

計算 feature-feature & clss-feature 的 correlation

由上一步整理後的資料可知，features 均為連續變量，故 feature-feature 的 correlation 可以使用 Standard Linear (Pearson’s) Correlation 計算；而 class-feature 則為二元變量對連續變量，可採用 Point-biserial Correlation Coefficient 計算 correlation。

其衡量的 correlation 介於 -1~1 之間，換算成絕對值來看，落在 0.5~1.0 即代表有很強的相關性。

• feature-feature correlation matrix：

該矩陣其實是以上下對稱的，其也方便接下來的步驟以搜索 index 找 correlation，故就不刪除重複值。

• class-feature correlation：

將 class-feature correlation 的計算結果附在 feature-feature matrix 最右邊。

設置一 function 用來計算 Merit

根據 Merit 公式的定義，需要全部特徵之 rcf mean 和 rff mean 平均來計算，以下 function 的設計概念為：

• rcf mean：找出上步驟 matrix 中 Rcf 欄位對應到的 correlation 值，再將其加總求平均。
• rff mean：一樣為找出 matrix 中對應到兩兩特徵的 correlation 值，加總求平均；但設計上會先求出欲帶入 feature subset 的全部可能組合，再將組合內的位置依序帶入 matrix 中，找到對應的 correlation。

進入 BFS 選擇環節

優先將 Merit 值最大的特徵存入空集合 S，於代碼中將其命名為 OFS (Optimal Feature Subset)。透過 class-feature correlation 表，可知當前最佳的 feature 為 “ISI”，優先將其存入。

OFS = ['ISI']

其後針對 OFS 依序存入各個特徵，並列出其所有可能加入當前 OFS 的組合。打 code 時記得刪除重複項，以免出現 [ ‘ISI’, ’ISI’ ] 的組合。

All possible subsets:
[['ISI', 'Temperature'], ['ISI', 'RH'], ['ISI', 'Ws'], ['ISI', 'Rain '], ['ISI', 'FFMC'], ['ISI', 'DMC'], ['ISI', 'DC'], ['ISI', 'BUI'], ['ISI', 'FWI'], ['ISI', 'days']]

其後依序算出個組合的 Merit 值，將組合內 Merit 值最大的 subset 叫出，和當前 OFS 的 Merit 比較，欲比較之新舊 subsets 各別如下：

1. ['ISI', 'FFMC'] merit:  0.8326225563999243
2. ['ISI']         merit:  0.8317963438470507

經過比較，可知道 [ ‘ISI’, ‘FFMC’ ] 的 Merit 較佳，故取代當前的 subset。之後就重複這部分的步驟直到輸出最佳結果為止。

在此可能會出現一問題為，當前若無特徵繼續加入 OFS，該如何設置才可讓程式 Early Stop？

筆者使用之方法為，初始設置一變數負責記錄 OFS 的長度，於 loop 前後各紀錄一次，若兩次長度相同，代表該次迴圈並無任何新特徵加入，以此原因便可直接讓程式 Early Stop。

輪完全部的特徵後，輸出最佳特徵子集及歷代特徵長度個數紀錄如下：

透過上圖結果可知道，此次資料，Algerian Forest Fires Dataset，對於是否有發生火災，最相關的變數分別為：[ ‘ISI’, ‘FFMC’, ‘FWI’ ]。

窮舉法找出 Optimal Feature Subset

其實可以用窮舉法(Method of Exhaustion) 這種暴力解來處理這種特徵很少的資料集，方法大致上為求出這 11 個 features 所有可能出現的 feature subsets，從 1 個 feature 到 11 個 features 的 subset 都要求出。

其後再算出各自的 Merit，並輸出 Merit 最大的那組即可。程式碼如下：

輸入變數為總 features 和 class-feature 列表，而輸出結果亦為 [ ‘ISI’, ‘FFMC’, ‘FWI’ ]。

OFS 結果分析

關於 OFS 的最後數量，可能有讀者會認為怎麼這麼少，原本明明有多達 11 個特徵，篩到最後卻剩下 3 個，其實這是正常的情況。以下引述 paper “An analysis on new hybrid parameter selection model performance over big data set” 內的結果，其中也是以 CFS 結合 BFS，並從特徵集非常大的資料中找出其 OFS，

上圖中，SSRS 指得是 Rough Set 和 Soft Set 的選擇方法，忽略其不看，只看 BM1 中 CFSBF 的特徵選擇結果的話，可看出六種不同的資料集，原始特徵(Attributes) 從 11 ~ 10001 都有，經過 CFSBF 的篩選後，減少至 5~76，由此可知，對於一原始特徵在經過 feature selection 前，都包含大量冗餘特徵。

完整代碼分享

結語

Feature Selection 的方法其實有非常多種，網上也有其他套件是可直接求出 Optimal Feature Subset，而筆者只是針對其中一個方法詳細進行介紹而已。本文結尾處並不包含驗證其準確性的方式，將來若是有時間，會補上的。

References

1. Hall, M. A. (2000). Correlation-based feature selection of discrete and numeric class machine learning.
2. Mohand, M. & Selamat, A. & Krejcar, O. & Fujita, H. & Wu, T. (2020). An analysis on new hybrid parameter selection model performance over big data set.