文章目录
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∥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
.
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,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)
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 个特征，作为最优的特征子集。
算法伪代码：
其中，矩阵
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。
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∈DargminNRPS(I∪{r})
算法伪代码如下所示：
4. DOI
http://www.doi.org/10.1109/JAS.2017.7510781