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

文章目录

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. 预备知识

2.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∥F2​s.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∑n​j=1∑m​Mij2​ ​.

2.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​;否则.​

3. 论文内容

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

设 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,bmin​21​∥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,bargmin​​21​∥aFI+b1−L∥F2​=a,bargmin​21​tr[(aFI+b1−L)T(aFI+b1−L)]=a,bargmin​21​tr(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​αi2​i=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)​

3.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​
值越小,代表特征子集越重要。

3.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 个特征,作为最优的特征子集。

算法伪代码:论文阅读报告:Feature Selection for Multi-label Classification Using Neighborhood Preservation,Zhiling Cai
其中,矩阵 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=1n​pij​qji​。

3.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∈Dargmin​NRPS(I∪{r})

算法伪代码如下所示:
论文阅读报告:Feature Selection for Multi-label Classification Using Neighborhood Preservation,Zhiling Cai
论文阅读报告:Feature Selection for Multi-label Classification Using Neighborhood Preservation,Zhiling Cai

4. DOI

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

上一篇:【已解决】el-table分页回显与多选删除功能冲突(reserve-selection)


下一篇:机器学习之特征选择(Feature Selection)