10-2 Feature Selection Methods (Sxk)

[english][all]
(請注意：中文版本並未隨英文版本同步更新！)
「特徵選取」（feature selection）的目標是要從原有的特徵中挑選出最佳的部分特徵，使其辨識率能夠達到最高值。這些鑑別能力較好的特徵，不但能夠簡化分類器的計算，而且也可以幫助我們瞭解此分類問題的因果關係。

The recognition rate is improved.
Less computing power is needed for constructing the classifier.
The selected features can help us understand the causal relationship between features and classes.

我們也可以使用數學的方式來說明特徵選取。假設我們有一組特徵 $V=\{v_1, v_2, \dots, v_d\}$，我們希望透過某種分類器來得到辨識率 J（˙），此辨識率是所選取特徵的函數；而特徵選取的目標，就是要從 V 中找出一組鑑別能力最佳的的子集合 S，使得 $J(S) \geq J(T)$，其中 T 是任何由 W 所形成的子集合。
一般來說，要選出一組鑑別能力最好的子集合，並沒有什麼好方法，除了簡單的 heuristics 外，就是暴力法，但是暴力法的計算量很大，除非資料量不大，否則我們很難使用暴力法。因此最常用到的是近似最佳法（或稱為 heuristic methods），其中 1971 年由 Whitney 所提出的 Sequential forward selection（簡稱 SFS）是最常被用到的近似最佳法，步驟如下：

使用最近鄰居法則（KNNC）和「一次挑一個」（leave-one-out, LOO）辨識率預估法。
第一個挑選的特徵必定是辨識率最高的特徵。
下一個挑選的特徵必定是和原本已選取的特徵合併後，辨識率最高的一個。
重複步驟 3，直至挑選出全部的特徵。

我們可以使用上述方法來對 IRIS 資料進行特徵選取。IRIS 資料共有 150 筆，共分成三類，每一筆資料具有四個特徵，使用 inputSelectSequential.m 來進行 SFS，結果請見下列範例：
Example 1: feaSelBySfs4iris01.m

從上圖可以看出，SFS 選的特徵分別是 {1}, {2}, {3}, {4}, {3,1}, {3,2}, {3,4}, {3,4,1}, {3,4,2}, {3,4,1,2}，但最後卻發覺只要使用 {3}，辨識率就可以達到 94.7%，然而這並分是最佳辨識率，因為 SFS 本來就是一個 heuristic 的方法，計算速度很快，但是並不保證可以找出最好的特徵。
如果我們改用暴力法，將所有可能的特徵組合全部算一遍，在速度上會比較慢，但由於 IRIS 資料的個數並不大，特徵也只有四個，因此我們可以直接使用 inputSelectExhaustive.m 來進行窮舉式的特徵選取，如下：
Example 2: feaSelByEs4iris01.m

由於 IRIS 資料量及特徵維度都不大，因此暴力法只需要計算 15（= 2⁴ - 1）個分類器，所得到的最佳辨識率是 96%，所選到的特徵是 {2,4}。
In the above two examples, the optimum recognition rate occurs when all features are selected. However, this is not the general case since sometimes we only need to use a subset of features to outperform the use of all features. The following example demonstrates that we only need 3 features to achieve the maximum recognition rate when the number of allowable features is 6.
Example 3: feaSelBySfs4wine01.m

Moreover, we can observe that whenever feature 13 is selected, the recognition rate will drop. This observation reminds us that the range of feature 13 might be very different from those of other features. Indeed, this is already confirmed by the example shown in the previous section. As a result, we need to normalize the features before conducting feature selection, as shown in the next example.
Example 4: feaSelBySfs4wine02.m

The only difference between this example and the previous one is that the features are normalized, which enhances the recognition rate from 93.8% to 97.8%. This demonstrates the importance of input (feature) normalization.
Hint
In fact, by using exhaustive search on all features, we can achieve a recognition rate of 99.4% based on the selected features {1, 3, 4, 9, 10, 11, 12, 13}, after conducting 8191 LOO tests.

However, it should be noted that input (feature) normalization does not guarantee improvement. As a result, it is always a good practice to try both the original and the normalized datasets for a given choice of classifier.
Some of the commonly used methods for feature selection, including sequential forward selection and exhaustive search, are listed here according to their computational complexity:

One-pass ranking
Sequential forward selection
Generalized sequential forward selection
Sequential backward selection
Generalized sequential backward selection
"Add m, remove n" selection
Generalized "add m, remove n" selection
Exhaustive search
Reference:

A. Whitney, "A direct method of nonparametric measurement selection", IEEE Transactions on Computers, vol. 20, pp.1100-1103, 1971.

Data Clustering and Pattern Recognition (資料分群與樣式辨認)