论文阅读报告：Laplacian Score for Feature Selection，Xiaofei He、Deng Cai and Partha Niyogi（2005）

妖狐艹你老母 2021-09-23 05:04 218阅读 0赞

### 文章目录 ###

*  0. LS
 *  1. 拉普拉斯分数
 *  2. 算法
 *   *  2.1. 构建连通图
     *  2.2. 权重矩阵
     *  2.3. 图拉普拉斯
     *  2.4. 拉普拉斯分数
 *  3. 目标函数
 *  4. 证明
 *  5. 出处

# 0. LS #

Laplacian Score（LS），中文名称 拉普拉斯分数。

# 1. 拉普拉斯分数 #

Laplacian Score 是一个对一个训练集样本的特征进行打分的算法。通过这个算法可以给每一个特征打出一个分数，最后再取分数最低的  k k k 个特征作为最后选择的特征子集，是标准的 Filter 式方法。

# 2. 算法 #

整个 Laplacian Score 分成 4 个步骤，分别对应于下面的 4 个小节。

令  L r L\_r Lr 表示第  r r r 个特征的 Laplacian Score。  
令  f r i f\_\{ri\} fri 表示第  r r r 个特征的第  i i i 个样本（ i = 1 , … , m i=1,\\dots,m i=1,…,m）。

## 2.1. 构建连通图 ##

构建一个  m m m 个节点的最近邻图  G G G。第  i i i 个节点对应于  x i \\mathbf\{x\}\_i xi。如果  x i \\mathbf\{x\}\_i xi 和  x j \\mathbf\{x\}\_j xj 是接近的，比如  x i \\mathbf\{x\}\_i xi 在  x j \\mathbf\{x\}\_j xj 的  k k k 个最近邻中，或者  x j \\mathbf\{x\}\_j xj 在  x i \\mathbf\{x\}\_i xi 的  k k k 个最近邻中，则在节点  i i i 和  j j j 之间放一条边。当标签信息已知时，两个相同标签的节点可以放一条边。

用公式表示：  
对于**无监督学习（Unsupervised Learning）** –  
 G m × m : ( G i j ) = \{ 1 , if  x i  close to  x j ; 0 , otherwise . G\_\{m \\times m\} : (G\_\{ij\}) = \\begin\{cases\} 1, & \\text\{if \} \\mathbf\{x\}\_i \\text\{ close to \} \\mathbf\{x\}\_j; \\\\ 0, & \\text\{otherwise\}. \\end\{cases\} Gm×m:(Gij)=\{ 1,0,if xi close to xj;otherwise.

对于**监督学习（Supervised Learning）** –  
 G m × m : ( G i j ) = \{ 1 , if  l r = l j ; 0 , otherwise . G\_\{m \\times m\} : (G\_\{ij\}) = \\begin\{cases\} 1, & \\text\{if \} l\_r = l\_j; \\\\ 0, & \\text\{otherwise\}. \\end\{cases\} Gm×m:(Gij)=\{ 1,0,if lr=lj;otherwise.

## 2.2. 权重矩阵 ##

如果节点  i i i 和  j j j 是连接的，则置  S i j = e − ∥ x i − x j ∥ 2 t S\_\{ij\}=e^\{-\\frac\{\\lVert \\mathbf\{x\}\_i - \\mathbf\{x\}\_j \\rVert^2\}\{t\}\} Sij=e−t∥xi−xj∥2，其中  t t t 是一个合适的常数。否则的话，置  S i j = 0 S\_\{ij\}=0 Sij=0。图的权重矩阵  S S S 对数据空间的局部结构进行建模。

用公式表示：  
 S m × m : ( S i j ) = \{ e − ∥ x i − x j ∥ 2 t , if  G i j = 1 ; 0 , otherwise . S\_\{m \\times m\} : (S\_\{ij\}) = \\begin\{cases\} e^\{-\\frac\{\\lVert \\mathbf\{x\}\_i - \\mathbf\{x\}\_j \\rVert^2\}\{t\}\}, \\text\{if \} G\_\{ij\} = 1; \\\\ 0, \\text\{otherwise\}. \\end\{cases\} Sm×m:(Sij)=\{ e−t∥xi−xj∥2,if Gij=1;0,otherwise.

## 2.3. 图拉普拉斯 ##

对于第  r r r 个特征，定义

f r = \[ f r 1 , f r 2 , … , f r m \] T \\mathbf\{f\}\_r=\[f\_\{r1\}, f\_\{r2\}, \\dots, f\_\{rm\}\]^T fr=\[fr1,fr2,…,frm\]T,  D = d i a g ( S 1 ) D=diag(S\\mathbf\{1\}) D=diag(S1),  1 = \[ 1 , … , 1 \] T \\mathbf\{1\}=\[1,\\dots,1\]^T 1=\[1,…,1\]T, L = D − S L=D-S L=D−S

其中，矩阵  L L L 通常被称为图拉普拉斯。  
令  
 f ~ r = f r − f r T D 1 1 T D 1 1 \\tilde\{\\mathbf\{f\}\}\_\{r\}=\\mathbf\{f\}\_\{r\}-\\frac\{\\mathbf\{f\}\_\{r\}^\{T\} D \\mathbf\{1\}\}\{\\mathbf\{1\}^\{T\} D \\mathbf\{1\}\} \\mathbf\{1\} f~r=fr−1TD1frTD11

## 2.4. 拉普拉斯分数 ##

第  r r r 个特征的拉普拉斯分数如下：  
 L r = f ~ r T L f ~ r f ~ r T D f ~ r L\_\{r\}=\\frac\{\\tilde\{\\mathbf\{f\}\}\_\{r\}^\{T\} L \\tilde\{\\mathbf\{f\}\}\_\{r\}\} \{\\tilde\{\\mathbf\{f\}\}\_\{r\}^\{T\} D \\tilde\{\\mathbf\{f\}\}\_\{r\}\} Lr=f~rTDf~rf~rTLf~r

# 3. 目标函数 #

回想一下，在给定数据集的情况下，我们构建了一个加权图  G G G，它的边将临近的点彼此连接。 S i j S\_\{ij\} Sij 评估第  i i i 个节点和第  j j j 个节点之间的相似性。特征的重要性可以视为其尊重图结构的程度。具体地讲，一个“好”的特征应该是当且仅当这两个数据点之间存在边时，两个数据点彼此接近的功能。选择良好特征的合理标准是最小化以下目标函数：  
 L r = ∑ i j ( f r i − f r j ) 2 S i j V a r ( f r ) L\_\{r\}=\\frac\{\\sum\_\{ij\}\\left(f\_\{r i\}-f\_\{r j\}\\right)^2 S\_\{i j\}\}\{ Var\\left(\\mathbf\{f\}\_\{r\}\\right)\} Lr=Var(fr)∑ij(fri−frj)2Sij

min ⁡ L r \\min L\_r minLr

因此，特征的拉普拉斯分数，越小越好。

# 4. 证明 #

未完待续……

# 5. 出处 #

1.  NIPS’05: Proceedings of the 18th International Conference on Neural Information Processing SystemsDecember 2005 Pages 507–514