相關文章
特征選擇
LVW（Las Vegas Wrapper）特征選擇算法簡單介紹

Relief（Relevant Features） 是著名的過濾式特征選擇方法，Relief 為一系列算法，它包括最早提出的 Relief 以及后來拓展的 Relief-F 和 RRelief-F ，其中最早提出的 Relief 針對的是二分類問題，RRelief-F 算法可以解決多分類問題，RRelief-F 算法針對的是目標屬性為連續值的回歸問題。

1 原始的 Relief 算法

最早提出的 Relief 算法主要針對二分類問題，該方法設計了一個“相關統計量”來度量特征的重要性，該統計量是一個向量，向量的每個分量是對其中一個初始特征的評價值，特征子集的重要性就是子集中每個特征所對應的相關統計量之和，因此可以看出，這個“相關統計量”也可以視為是每個特征的“權值”。可以指定一個閾值 $\tau$，只需選擇比 $\tau$ 大的相關統計量對應的特征值，也可以指定想要選擇的特征個數 $k$，然后選擇相關統計量分量最大的 $k$ 個特征。

有了 Relief 的基本思想，那么現在的問題就轉換成如何得到一種有效的權值或者相關統計量類對特征進行度量，Relief 借用了 “假設間隔”（hypothesis margin） 的思想，我們知道在分類問題中，常常會采用決策面的思想來進行分類，“假設間隔”就是指在保持樣本分類不變的情況下，決策面能夠移動的最大距離，可以表示為：

$$\theta =\frac{1}{2}(\Vert x?M(x)\Vert ?\Vert x?H(x)\Vert )\text{\hspace{1em}(1)}$$

其中，$M(x)$、$H(x)$ 指的是與 $x$ 同類的和與 $x$ 非同類的最近鄰點。

我們知道，當一個屬性對分類有利時，則該同類樣本在該屬性上的距離較近，而異類樣本在該屬性上的距離較遠，因此，若將假設間隔推廣到對屬性的評價中，則對應于公式（1）圓括號中的第一項越小，第二項越大，則該屬性對分類越有利。“假設間隔”能對各維度上的特征的分類能力進行評價，從而就可以近似地估計出對分類最有用的特征子集，Relief 正是利用了這個特性。
　　
假設訓練集 $D$ 為 $(x_1,y_1),(x_2,y_2),?,(x_m,y_m)$，對每個樣本 $x_i$，計算與 $x_i$ 同類別的最近鄰 $x_{i,nh}$，稱為是 “猜中近鄰”（near-heat），然后計算與 $x_i$ 非同類別的最近鄰 $x_{i,nm}$，稱為是 “猜錯近鄰”（near-miss），則屬性 $j$ 對應的相關統計量為：

$${\delta }^j=\sum _i?diff(x_i^j,x_{i,nh}^j{)}^2+diff(x_i^j,x_{i,nm}^j{)}^2\text{\hspace{1em}(2)}$$

其中，$x_a^j$ 代表樣本 $x_a$ 在屬性 $j$ 上的取值，$diff(x_a^j,x_b^j)$ 的計算取決于屬性 $j$ 的類型：

（1）對離散型屬性：

$$diff(x_a^j,x_b^j)=\{\begin{array}{ll}0,& x_a^j=x_b^j\\ 1,& otherwise\end{array}$$

（2）對連續型屬性：

$$diff(x_a^j,x_b^j)=|x_a^j?x_b^j|$$

注：$x_a^j$，$x_b^j$已經規范化到 $[0,1]$ 區間。
　　
從公式（2）中可以看出，若 $x_i$ 與其猜中近鄰 $x_{i,nh}$ 在屬性 $j$ 上的距離小于 $x_i$ 與其非同類別的最近鄰 $x_{i,nm}$ 的距離，則說明屬性 $j$ 對區分同類與異類樣本是有利的，反之則不利，因此公式（2）的值越大則說明該屬性的分類能力越強。

公式（2）得到的是單個樣本對每個屬性的評價值，將所有樣本對同一個屬性的評價值進行平均就得到了該屬性的相關統計分量，分量值越大，分類能力就越強。

2 Relief-F

Relief 算法只能直接處理兩分類的特征選擇，改進的 Relief-F 算法能夠處理多分類問題，它將多分類視為是一類對多類直接加以解決。其方法是尋找當前樣本的各類最近鄰點并綜合加以計算。

假設數據集為 $D$，該數據集一共包含 $|y|$ 個類別，對示例 $x_i$，若它屬于第 $k$ 類（$k\in \{1,2,?,|y|\}$），則 Relef-F 算法先在第 $k$ 類的樣本中尋找 $x_i$ 的最近鄰 $x_{i,nh}$，作為樣本 $x_i$ 的猜中近鄰，然后在第 $k$ 類之外的每個類別的樣本中尋找 $x_i$ 的最近鄰 $x_{i,l,nm}$（$l=1,2,?,|y|;l=k$），作為樣本 $x_i$ 的猜錯近鄰，則相關統計量對應于屬性 $j$ 的分量為：
$${\delta }^j=\sum _i?diff(x_i^j,x_{i,nh}^j{)}^2+\sum _{l=k}(p_l\times diff(x_i^j,x_{i,l,nm}^j{)}^2)$$

其中，$p_l$ 為第 $l$ 類樣本在數據集 $D$ 中所占的比例。

【參考文獻】
《機器學習》周志華著.–北京：清華大學出版社

總結

以上是生活随笔為你收集整理的Relief 特征选择算法简单介绍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。