Adaptive Feature Selection based on the Most Informative Graph-based Featuresn閱讀筆記

02-03

轉載請註明出處：All Minable團隊的搬磚日常

論文鏈接：論文下載地址

論文原作者：Lixin Cui, Yuhang Jiao, Lu Bai, Luca Rossi, and Edwin R. Hancock

Abstract

這篇文章提出了一個對目標類標具有強大識別能力的自適應信息特徵選擇方法，能夠獲取信息量最大且冗餘度最小的特徵。該方法是基於圖特徵進行的，在特徵選擇過程中包含了對於圖中節點關係的特徵採樣。作者主要是通過穩定狀態隨機遊走的方式來探索圖結構，同時計算出遊走時訪問節點的概率分布。在文章中，作者還提出了一種新的信息理論標準來衡量對目標特徵和不同特徵組合的聯合相關性。最後，作者在實驗中以中國的P2P平台為實驗解釋了該方法的有效性。

Introduction

本部分中，作者主要介紹了現有的或者傳統的一些特徵選擇的方法，這些方法普遍有以下的不足：

1. 有些演算法需要提前確定選擇特徵的個數

2. 有些演算法使用貪心演算法進行挖掘，容易陷入局部最優

3. 大多數演算法把每個特徵看成是一個向量，而忽略了特徵樣本之間的關係，而這也將限制特徵間信息理論衡量的精確性

4. 還有部分的演算法不能自適應地決定最相關的特徵子集

基於現有演算法的上述不足，這篇文章提出了一個新的演算法，這個演算法可以在特徵選擇的過程中考慮特徵樣本之間的關係。文章的貢獻主要有以下幾點：

1. 將每個特徵向量 $mathbf{f_i}$ 都轉換成一個基於圖的特徵 $mathbf{G_i}$ ，其中 $mathbf{G_i}$ 是一個帶權完全圖，節點代表特徵樣本，邊代表特徵樣本間的關係。同時，作者使用穩定狀態隨機遊走(SSRW)來檢測每個圖的結構並計算遊走對節點訪問的概率分布

2. 提出新的資訊理論標準來衡量關於目標特徵的特徵對之間的相關關係，通過Jensen-Shannon divergence (JSD)

3. 應用新提出的資訊理論衡量標準，通過解決二次規劃問題自動找出具有最高信息量和最低冗餘性的特徵子集，同時，此方法適用於連續和離散目標變數。

Preliminary Concepts

1. The Steady State Random Walk (SSRW)

使用SSRW的好處有兩點：

1. SSRW可以用邊保存帶權信息

2. SSRW計算複雜度為 $O(|V|^2)$ ,V代表圖的節點集

對於圖G(V,E)，V是節點集，E是邊集，其中 $omega(u,v)$ 是節點u和v之間的邊權。

定義G的節點度矩陣： $D(v,v) = d(v) = sum_{u in V}{omega(v,u)}$

根據SSRW得到的每個節點的訪問概率為： $p(v) = frac{d(v)}{sum_{u in V}{d(u)}}$ ，這樣我們能得到概率分布 $P = {p(1),...,p(v),...,p(|V|)}$

根據概率分布，我們可以得到關於圖的熵： $H_S(G) = -sum_{v in V}{p(v)log{p(v)}}$

2. The Jensen-Shannon Divergence(JSD)

散度是用來度量兩種概率分布之間的不相似程度的，散度越大，說明兩種概率分布之間相差越遠。這裡使用JSD進行衡量:

$[I_D(P,Q) = H_S(frac{P+Q}{2})-frac{1}{2}H_S(P)-frac{1}{2}H_S(Q)]$

因為文章中作者也非常關心基於圖的特徵之間的相似性，也就是不同特徵概率分布之間的相似性，所以將上式改成:

$[I_S(P,Q) = exp{-I_D(P,Q)}]$

The Proposed Feature Selection Method

1. 將向量特徵轉化為基於圖的特徵

優勢：

1. 圖結構擁有拓撲結構，能比向量包含更多的信息

2. 圖結構能夠在特徵選擇過程中將特徵樣本之間的關係考慮進去，而向量是做不到的

對於數據集N有特徵 $X={mathbf{f_1,...,f_i,...f_N}} in R^{M times N}$ ，本步驟需要做的是將 $mathbf{f_i}$ 轉換成圖 $G_i(V_i,E_i)$ ，每個樣本對應圖的節點，樣本間存在邊，邊權計算如下：

$[omega(v_{ia},v_{ib}) = ||f_{ia}-f_{ib}||_2]$

對於目標特徵 $mathbf{Y}={y_1,...,y_a,...,y_b,...,y_M}^T$ 轉換得到的圖特徵稱為 $hat{G_i}(hat{V},hat{E})$

2. 特徵選擇的信息理論指標

對於不同特徵和目標特徵 $mathbf{Y}$ ，我們能找到任意兩個特徵對 ${mathbf{f_i},mathbf{f_j}}$ 之間的關係：

$[W_{i,j} = I_S(mathbf{G_i},mathbf{hat{G}}) times I_S(mathbf{G_j},mathbf{hat{G}}) times I_D(mathbf{G_i},mathbf{G_j})]$

上式可以這樣理解，如果 $W_{i,j}$ 的值比較大，就說明特徵i和特徵j和目標特徵Y的相似度都比較高，也就是i和j能較好的表現出目標特徵Y，同時，說明特徵i和特徵j的散度差異大，就說明i和j之間的冗餘信息少。

個人感覺，這個衡量指標的構建即能考慮單個特徵與目標特徵的關係，又能考慮特徵之間的信息冗餘關係，很有靈性。

3. 決定最具信息量的特徵集合

在第二部分中我們可以獲得特徵對之間的一個W矩陣，我們可以通過一個指示向量來構造目標函數：

$[max f(mathbf{a}) = frac{1}{2}mathbf{a^TWa}]$

其中， $mathbf{a} in R^N, mathbf{a} ge{0}, sum^N_{i=1}{a_i=1}$ , 當 $a_i$ 大於0時，說明特徵i屬於最具有信息的特徵集合，因此，大於0的值的個數可以決定選擇特徵數，所以具有自適應性。

上述目標函數，可以使用下式轉換成一個迭代演算法：

$[a_i(t+1) = a_i(t)frac{(mathbf{Wa}(t))_i}{mathbf{a}(t)^Tmathbf{Wa}(t)}]$

迭代之後，我們可以得到兩個集合， $mathbf{S_1}(a) = {mathbf{f_i}|a_i gt 0}$ 和 $mathbf{S_2}(a) = {mathbf{f_j}|a_j = 0}$ ，可以看出，集合S1中的特徵就是更加具有信息量且低冗餘的特徵。

4. 特徵排序

在某些情況下，我們可能需要對所有的特徵根據重要程度進行排序。對於本文的方法，其實要實現特徵排序也比較簡單。對於S1集合中的特徵，我們直接按照a值的大小對特徵進行排序。對於S2集合中a的0的特徵，我們可以通過計算下面公式來得到特徵j的rank值：

$[r_j = sum_{mathbf{f_i in S_1},a_i > 0}{W_{i,j}a_i}]$

其中，rank值越大的特徵在S2集合中的排名越靠前。這樣，我們就能將全部的特徵按照信息的貢獻進行一個排序。

註：實驗部分可直接查看論文。

個人理解：

本文的創新點在於將特徵的向量表達轉換成了圖表達方式，每個向量是一張圖，這樣得到的概率分布就包含了特徵樣本之間的關係，從而在後面的演算法中有個更多的信息。同時，不但考慮特徵與目標特徵的分布重合度，還考慮了減少特徵之間的信息冗餘，並通過使用指示向量 $mathbf{a}$ ，能夠實現特徵的自適應選擇。感覺這篇文章用了基礎的理論解決了很多現有演算法的問題，是一篇很值得一讀的文章。