论文阅读报告：Feature Selection for Multi-label Classification Using Neighborhood Preservation，Zhiling Cai

悠悠 2021-09-25 01:02 211阅读 0赞

### 文章目录 ###

*  1. 论文出处
 *  2. 流程（示意图）
 *  3. 预备知识
 *   *  3.1 相似性保持特征选择（Similarity Preserving Feature Selection）
     *  3.2 多标签
 *  4. 论文内容
 *   *  4.1 NRPS
     *  4.2 FNRPS
     *  4.3 GNRPS
 *  5. DOI

# 1. 论文出处 #

*  **Feature Selection for Multi-label Classification Using Neighborhood Preservation**
 *  Zhiling Cai and William Zhu
 *  IEEE/CAA JOURNAL OF AUTOMATICA SINICA
 *  Volumn 5
 *  Number 1
 *  2018

# 2. 流程（示意图） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]  
四步：

*  构建两个样本相似性矩阵，一个是特征子空间下的样本相似性矩阵，另外一个是标签空间下的样本相似性矩阵；
 *  构建关于  F I F^I FI 和  L L L 的表达式；
 *  特征评价准则 NRPS；
 *  设计两种特征选择算法，分别是 FNRPS 和 GNRPS。

# 3. 预备知识 #

## 3.1 相似性保持特征选择（Similarity Preserving Feature Selection） ##

S C ( f ) = f ^ T K f ^ SC(f)=\\hat\{f\}^TK \\hat\{f\} SC(f)=f^TKf^  
其中， K ^ \\hat\{K\} K^ 是相似度矩阵， f ^ \\hat\{f\} f^ 是归一化后的特征（属性）向量。

单标签中， K K K 定义为  
 min ⁡ X ^ ∥ K ′ − K ∥ F 2 s.t.  K ′ = X ^ T X ^ \\begin\{aligned\} &\\min\_\{\\hat\{X\}\} \\lVert K'-K \\rVert^2\_F \\\\ &\\text\{s.t. \} K' = \\hat\{X\}^T\\hat\{X\} \\end\{aligned\} X^min∥K′−K∥F2s.t. K′=X^TX^  
其中， X ^ \\hat\{X\} X^ 是从所有特征中选择出来的  k k k 个特征， ∥ ⋅ ∥ F \\lVert \\cdot \\rVert\_F ∥⋅∥F 是 Frobenius norm。

Frobenius norm 定义为  
 ∥ M ∥ F = ∑ i = 1 n ∑ j = 1 m M i j 2 . \\lVert M \\rVert\_F = \\sqrt\{\\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{m\} M\_\{ij\}^2\}. ∥M∥F=i=1∑nj=1∑mMij2.

## 3.2 多标签 ##

记 –

*   d d d 维的特征空间为  X = R d \\mathcal\{X\}=\\mathbb\{R\}^d X=Rd；
 *  标签集合  C = \{ c 1 , … , c m \} C=\\\{c\_1, \\dots, c\_m\\\} C=\{ c1,…,cm\}；
 *  多标签训练集  D = \{ ( x i , Y i ) ∣ 1 ≤ i ≤ n \} D=\\\{(x\_i, Y\_i)\\mid 1\\leq i \\leq n\\\} D=\{ (xi,Yi)∣1≤i≤n\}；
 *   x i ∈ X x\_i \\in \\mathcal\{X\} xi∈X 是一个  d d d 维的特征向量  \[ x i 1 , … , x i d \] \[x\_\{i1\},\\dots,x\_\{id\}\] \[xi1,…,xid\]；
 *   Y i ∈ C Y\_i \\in C Yi∈C 是和  x i x\_i xi 关联的标签集合；
 *   Y i Y\_i Yi 是一个  m m m 维的二值向量  y i = \[ y i 1 , … , y i m \] y\_i = \[y\_\{i1\},\\dots,y\_\{im\}\] yi=\[yi1,…,yim\] ，其中  
     y i j = \{ 1 , 如果  Y i  拥有标签  c j ; 0 , 否则 . y\_\{ij\} = \\begin\{cases\} 1, & \\text\{如果 \} Y\_i \\text\{ 拥有标签 \} c\_j;\\\\ 0, & \\text\{否则\}. \\end\{cases\} yij=\{ 1,0,如果 Yi 拥有标签 cj;否则.

# 4. 论文内容 #

特征选择问题是选择一个特征子集以近似地表示所有特征。

设  I ⊆ \{ 1 , … , m \} I\\subseteq \\\{1,\\dots,m\\\} I⊆\{ 1,…,m\} 是选择出来特征的下标集合。

特征选择后，一个实例  x ∈ R d x\\in \\mathcal\{R\}^d x∈Rd 可以近似地表示为  x I ∈ R ∣ I ∣ x^I \\in \\mathbb\{R\}^\{\\lvert I \\rvert\} xI∈R∣I∣，其中  x I x^I xI 是  x x x 的一个子向量。

通过训练集  D D D 和下标集合  I I I，构建两个样本相似性矩阵，其中一个基于特征子空间，另外一个基于标签空间。

*  对于  \{ x 1 I , … , x n I \} \\\{x^I\_1, \\dots, x^I\_n\\\} \{ x1I,…,xnI\}，定义  F I = \[ F i j I \] n × n , F i j I = ⟨ x i I , x j I ⟩ F^I=\\left\[F^I\_\{ij\}\\right\]\_\{n\\times n\}, F^I\_\{ij\}=\\langle x^I\_i, x^I\_j \\rangle FI=\[FijI\]n×n,FijI=⟨xiI,xjI⟩ 是基于特征子空间的样本相似性矩阵。
 *  对于  \{ y 1 , … , y n \} \\\{y\_1,\\dots,y\_n\\\} \{ y1,…,yn\}，定义  L = \[ L i j \] n × n , L i j = ⟨ y i , y j ⟩ L=\\left\[L\_\{ij\} \\right\]\_\{n\\times n\}, L\_\{ij\} = \\langle y\_i, y\_j \\rangle L=\[Lij\]n×n,Lij=⟨yi,yj⟩ 是基于标签控件的样本相似性矩阵。

如果两个样本之间包含越多的相同标签，则它们应该越相似。  
因此，定义相似保持（Similarity Preservation）如下：  
 min ⁡ I ∥ F I − L ∥ F 2 . \\min\_\{I\} \\lVert F^I - L \\rVert\_F^2. Imin∥FI−L∥F2.  
上式假设，特征子空间标签子空间中，样本之间的相似性近似相等。

然而，上式没考虑到的是，这两种相似性很可能有不同的范围（different scales）。

因此，对上式进行改进。

**思想：**

*  样本相似性矩阵中，两个样本之间的相似性越高，则样本越相近；
 *  样本相似性可以转换成样本邻居关系来表达；

领域保持（Neighborhood Preservation）定义如下：  
 min ⁡ I , a , b 1 2 ∥ a F I + b 1 − L ∥ F 2 \\min\_\{I,a,b\} \\frac\{1\}\{2\} \\lVert aF^I + b\\bm\{1\}-L\\rVert\_F^2 I,a,bmin21∥aFI\+b1−L∥F2  
其中， a a a 和  b b b 是两个待解决的变量， 1 ∈ R n × n \\bm\{1\}\\in \\mathbb\{R\}^\{n\\times n\} 1∈Rn×n 是全 1 矩阵。

为了得到特征评价准则，假设  I I I 是已知的，求解  
 arg min ⁡ a , b 1 2 ∥ a F I + b 1 − L ∥ F 2 = arg min ⁡ a , b 1 2 tr \[ ( a F I + b 1 − L ) T ( a F I + b 1 − L ) \] = arg min ⁡ a , b 1 2 tr ( a 2 F I F I + 2 a b F I 1 + b 2 1 2 − 2 a F I L − 2 b 1 L + L 2 ) . \\begin\{aligned\} \\argmin\_\{a,b\} & \\frac\{1\}\{2\} \\lVert aF^I + b\\bm\{1\} - L \\rVert\_F^2 \\\\ &= \\argmin\_\{a,b\} \\frac\{1\}\{2\} \\text\{tr\} \\left\[\\left(aF^I + b\\bm\{1\} - L\\right)^T \\left( aF^I + b \\bm\{1\} - L\\right)\\right\] \\\\ &= \\argmin\_\{a,b\} \\frac\{1\}\{2\}\\text\{tr\}\\left(a^2F^IF^I + 2abF^I\\bm\{1\} + b^2\\bm\{1\}^2 - 2aF^IL-2b\\bm\{1\}L + L^2 \\right). \\end\{aligned\} a,bargmin21∥aFI\+b1−L∥F2=a,bargmin21tr\[(aFI\+b1−L)T(aFI\+b1−L)\]=a,bargmin21tr(a2FIFI\+2abFI1\+b212−2aFIL−2b1L\+L2).  
令  O = 1 2 ∥ a F I + b 1 − L ∥ F 2 \\mathbb\{O\} =\\frac\{1\}\{2\}\\lVert aF^I + b\\bm\{1\} - L\\rVert\_F^2 O=21∥aFI\+b1−L∥F2，

通过将其对于  a a a 的偏导数置为 0，得到  
 d O d a = a tr ( F I F I ) + b tr ( F I 1 ) − tr ( F I L ) = 0. \\frac\{d\\mathbb\{O\}\}\{da\} = a\\text\{tr\}\\left(F^IF^I\\right) + b\\text\{tr\}\\left(F^I\\bm\{1\}\\right) -\\text\{tr\}\\left(F^IL\\right) = 0. dadO=atr(FIFI)\+btr(FI1)−tr(FIL)=0.

通过将其对于  b b b 的偏导数置为 0，得到  
 d O d b = a tr ( F I 1 ) + b tr ( 1 2 ) − tr ( 1 L ) = 0. \\frac\{d\\mathbb\{O\}\}\{db\} = a\\text\{tr\}\\left( F^I\\bm\{1\}\\right) + b \\text\{tr\} \\left(\\bm\{1\}^2 \\right) - \\text\{tr\}\\left(\\bm\{1\} L\\right) = 0. dbdO=atr(FI1)\+btr(12)−tr(1L)=0.

由上面两个偏导数得到  
 ( tr ( F I F I ) tr ( F I 1 ) tr ( F I 1 ) tr ( 1 2 ) ) ( a b ) = ( tr ( F I L ) tr ( L 1 ) ) \\begin\{pmatrix\} \\text\{tr\}\\left(F^IF^I\\right) \\quad \\text\{tr\}\\left(F^I\\bm\{1\}\\right) \\\\ \\text\{tr\}\\left(F^I \\bm\{1\} \\right) \\quad \\text\{tr\}\\left( \\bm\{1\}^2\\right) \\end\{pmatrix\} \\begin\{pmatrix\} a \\\\ b \\\\ \\end\{pmatrix\} = \\begin\{pmatrix\} \\text\{tr\} \\left(F^IL \\right) \\\\ \\text\{tr\} \\left(L\\bm\{1\} \\right) \\\\ \\end\{pmatrix\} (tr(FIFI)tr(FI1)tr(FI1)tr(12))(ab)=(tr(FIL)tr(L1))

为了解决上式的问题，需要额外的信息。

**引理 1：柯西不等式**  
设  α 1 , … , α n , β 1 , … , β n ∈ R \\alpha\_1, \\dots, \\alpha\_n, \\beta\_1, \\dots, \\beta\_n \\in \\mathbb\{R\} α1,…,αn,β1,…,βn∈R，有  
 \[ ∑ i = 1 n α i β i \] 2 ≤ ∑ i = 1 n α i 2 ∑ i = 1 n β i 2 \\left\[\\sum\_\{i=1\}^\{n\} \\alpha\_i\\beta\_i\\right\]^2 \\leq \\sum\_\{i=1\}^\{n\}\\alpha\_i^2\\sum\_\{i=1\}^\{n\}\\beta\_i^2 \[i=1∑nαiβi\]2≤i=1∑nαi2i=1∑nβi2  
当且仅当  β i = 0 \\beta\_i=0 βi=0 或者  α i = c β i ( i = 1 , … , n  且  c ∈ R ) \\alpha\_i=c\\beta\_i(i=1,\\dots,n \\text\{ 且 \} c\\in \\mathbb\{R\}) αi=cβi(i=1,…,n 且 c∈R)时，取等号。

**推论 1**  
如果  A A A 和  B B B 都是对称矩阵，则有  
 \[ tr ( A B ) \] 2 ≤ tr ( A 2 ) tr ( B 2 ) \\left\[\\text\{tr\}(AB)\\right\]^2 \\leq \\text\{tr\}(A^2) \\text\{tr\}(B^2) \[tr(AB)\]2≤tr(A2)tr(B2)  
其中，当  B = 0 B=\\bm\{0\} B=0 或者  A = c B ( c ∈ R ) A=cB(c\\in \\mathbb\{R\}) A=cB(c∈R) 时，取等号。

在实际应用中，样本之间的相似性不可能都相同。

也就是， F I ≠ c 1 ( c ∈ R ) F^I \\neq c\\bm\{1\}(c \\in \\mathbb\{R\}) FI=c1(c∈R)，得到

( tr ( F I 1 ) ) 2 ≤ tr ( F I F I ) tr ( 1 2 ) . \\left(\\text\{tr\}\\left(F^I\\bm\{1\}\\right) \\right)^2 \\leq \\text\{tr\}\\left( F^IF^I\\right)\\text\{tr\}\\left(\\bm\{1\}^2\\right). (tr(FI1))2≤tr(FIFI)tr(12).

因此，有  
 ∣ tr ( F I F I ) tr ( F I 1 ) tr ( F I 1 ) tr ( 1 2 ) ∣ ≠ 0. \\left \\lvert \\begin\{matrix\} \\text\{tr\}\\left(F^IF^I \\right) \\quad \\text\{tr\}\\left(F^I\\bm\{1\} \\right) \\\\ \\text\{tr\}\\left( F^I \\bm\{1\}\\right) \\quad \\text\{tr\} \\left( \\bm\{1\}^2\\right) \\end\{matrix\} \\right \\rvert \\neq 0. ∣∣∣∣tr(FIFI)tr(FI1)tr(FI1)tr(12)∣∣∣∣=0.

基于以上的结论，可以得到  a a a、 b b b 的唯一解：  
 a = tr ( F I L ) tr ( 11 ) − tr ( F I 1 ) tr ( L 1 ) tr ( F I F I ) tr ( 11 ) − tr ( F I 1 ) tr ( F I 1 ) a = \\frac\{\\text\{tr\} \\left(F^IL\\right) \\text\{tr\} (\\bm\{11\}) - \\text\{tr\} \\left(F^I\\bm\{1\}\\right)\\text\{tr\}\\left(L\\bm\{1\}\\right)\}\{\\text\{tr\}\\left(F^IF^I\\right) \\text\{tr\}(\\bm\{11\}) - \\text\{tr\}\\left(F^I \\bm\{1\} \\right) \\text\{tr\} \\left( F^I \\bm\{1\} \\right)\} a=tr(FIFI)tr(11)−tr(FI1)tr(FI1)tr(FIL)tr(11)−tr(FI1)tr(L1)

b = tr ( F I F I ) tr ( L 1 ) − tr ( F I 1 ) tr ( F I L ) tr ( F I F I ) tr ( 11 ) − tr ( F I 1 ) tr ( F I 1 ) b = \\frac\{\\text\{tr\} \\left(F^IF^I\\right) \\text\{tr\} (L\\bm\{1\}) - \\text\{tr\} \\left(F^I\\bm\{1\}\\right)\\text\{tr\}\\left(F^IL\\right)\}\{\\text\{tr\}\\left(F^IF^I\\right) \\text\{tr\}(\\bm\{11\}) - \\text\{tr\}\\left(F^I \\bm\{1\} \\right) \\text\{tr\} \\left( F^I \\bm\{1\} \\right)\} b=tr(FIFI)tr(11)−tr(FI1)tr(FI1)tr(FIFI)tr(L1)−tr(FI1)tr(FIL)

## 4.1 NRPS ##

**Neighborhood relationship preserving score(NRPS)**

对于每个下标集合  I I I，计算 NRPS  
 N R P S ( I ) = ∥ a F I + b 1 − L ∥ F 2 NRPS(I) = \\lVert aF^I + b\\bm\{1\} - L \\rVert\_F^2 NRPS(I)=∥aFI\+b1−L∥F2  
**值越小，代表特征子集越重要。**

## 4.2 FNRPS ##

**Feature Ranking Method for Multi-label Feature Selection(FNRPS)**

记  S C ( r ) SC(r) SC(r) 是第  r r r 个特征的领域保持分数（ r = 1 , … , d r=1,\\dots,d r=1,…,d， d d d 是特征的数目）。

令  
 S C ( r ) = N R P S ( \{ r \} ) , SC(r) = NRPS(\\\{r\\\}), SC(r)=NRPS(\{ r\}),  
然后选择分数最小的  k k k 个特征，作为最优的特征子集。

算法伪代码：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 1]  
其中，矩阵  P , Q ∈ R d P, Q \\in \\mathbb\{R\}^d P,Q∈Rd， tr ( P Q ) = ∑ i = 1 n ∑ j = 1 n p i j q j i \\text\{tr\}(PQ)=\\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{n\} p\_\{ij\} q\_\{ji\} tr(PQ)=∑i=1n∑j=1npijqji。

## 4.3 GNRPS ##

**Greedy Method for Multi-label Feature Selection(GNRPS)**

采用传统的前向搜索策略，贪婪地选择特征。

首先，初始化  I = ∅ I=\\emptyset I=∅， D D D 中特征的下标集合为  \{ 1 , … , d \} \\\{1,\\dots,d\\\} \{ 1,…,d\}。

基于以下式子，从  D D D 中逐个添加特征到  I I I 中：  
 arg min ⁡ r ∈ D N R P S ( I ∪ \{ r \} ) \\argmin\_\{r \\in D\} NRPS(I \\cup \\\{r\\\}) r∈DargminNRPS(I∪\{ r\})

算法伪代码如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 3]

# 5. DOI #

http://www.doi.org/10.1109/JAS.2017.7510781

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]: /images/20210923/abbce18138b0408da08ea61012e5542f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 1]: /images/20210923/0a7d6a7a84024d0ea0185d6db3fb4735.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 2]: /images/20210923/c34406bfb9bc4d7c8d944f0686e7189b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 3]: /images/20210923/afa2568c89394a4c8d927b0151e22048.png