Feature Selection for Supervised Learning and Compression

Figures & data

Table

Algorithm 1 Forward greedy search
1: procedure ForwardGreedy $X,y,k$ 2:  $S\leftarrow \mathrm{\varnothing }$ 3:  while $|S|<k$ do 4:   $s\leftarrow \underset{s\in X\mathrm{\setminus }S}{argmax}\mathcal{P}(S\cup \{s\},y)-\mathcal{P}(S,y)$ 5:   $S\leftarrow S\cup \{s\}$ 6:  return $S$

Table

Algorithm 2 Lazy forward greedy search

1: procedure LazyForwardGreedy $X,y,k$ 2:  $S\leftarrow \mathrm{\varnothing }$ 3:  for $x\in X$ do ${\mathrm{\Delta }}_x\leftarrow \mathrm{\infty }$ 4:  while $|S|<k$ do 5:   for $x\in X$ do $C_x\leftarrow \mathbf{f}\mathbf{a}\mathbf{l}\mathbf{s}\mathbf{e}$ 6:   loop 7:    $s\leftarrow \underset{s\in X\mathrm{\setminus }S}{argmax}{\mathrm{\Delta }}_s$8:  if $C_s$ then 9:     break 10:    else 11:     ${\mathrm{\Delta }}_s\leftarrow \mathcal{P}(S\cup \{s\},y)-\mathcal{P}(S,y)$ 12:     $C_s=\mathbf{t}\mathbf{r}\mathbf{u}\mathbf{e}$ 13:   $S\leftarrow S\cup \{s\}$ 14:  return $S$

Table 1. The quantities of entropy that are maximized in each of the entropy based criterions.

	$H(y)$	$H(s_k)$	$H(y|s_k)$	$|S{|}^{-1}\sum _{x\in S}H(s_k|x)$
$\mathrm{M}\mathrm{R}$	$1$	$0$	$-1$	$0$
$\mathrm{M}\mathrm{R}+\mathrm{C}$	$1$	$-\omega$	$-1$	$0$
$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}$	$1$	$0$	$-1$	$1$
$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$	$1$	$-\omega$	$-1$	$1$

Figure 1. Entropy Venn diagrams.

Figure 2. Demonstration of (a) $\mathrm{M}\mathrm{R}$ vs $\mathrm{M}\mathrm{R}+\mathrm{C}$ and (b) $\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}$ vs $\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$.

Table 2. Feature selection performance measures investigated in the evaluation.

Selection method	Performance measure	Equation	Tasks
$\mathrm{M}\mathrm{R}+\mathrm{C}$	${\mathcal{P}}_{\mathrm{M}\mathrm{R}+\mathrm{C}}$	12	FC, PoI
$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$	${\mathcal{P}}_{\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}}$	19	FC, PoI
$\mathrm{G}\mathrm{O}\mathrm{F}\mathrm{r}+\mathrm{C}$	${\mathcal{P}}_{{\mathcal{M}}_{\mathrm{L}\mathrm{R}\mathrm{r}},{\mathcal{G}}_{R^2+\mathrm{C}}}$	30	FC
$\mathrm{G}\mathrm{O}\mathrm{F}\mathrm{c}+\mathrm{C}$	${\mathcal{P}}_{{\mathcal{M}}_{\mathrm{L}\mathrm{C}\mathrm{c}},{\mathcal{G}}_{\mathrm{A}\mathrm{U}\mathrm{C}+\mathrm{C}}}$	31	PoI
$\mathrm{W}\mathrm{L}\mathrm{R}\mathrm{r}+\mathrm{C}$	${\mathcal{P}}_{{\mathcal{M}}_{\mathrm{L}\mathrm{R}\mathrm{r}},{\mathcal{P}}_{R^2+\mathrm{C}}}$	38	FC
$\mathrm{W}\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{r}+\mathrm{C}$	${\mathcal{P}}_{{\mathcal{M}}_{\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{r}},{\mathcal{P}}_{R^2+\mathrm{C}}}$	39	FC
$\mathrm{W}\mathrm{L}\mathrm{C}\mathrm{c}+\mathrm{C}$	${\mathcal{P}}_{{\mathcal{M}}_{\mathrm{L}\mathrm{C}\mathrm{c}},{\mathcal{P}}_{\mathrm{A}\mathrm{U}\mathrm{C}+\mathrm{C}}}$	40	PoI
$\mathrm{W}\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{c}+\mathrm{C}$	${\mathcal{P}}_{{\mathcal{M}}_{\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{c}},{\mathcal{P}}_{\mathrm{A}\mathrm{U}\mathrm{C}+\mathrm{C}}}$	41	PoI

Figure 3. $R^2$ performances for the FC task.

Figure 4. $\mathrm{A}\mathrm{U}\mathrm{C}$ performances for the PoI task.

Figure 5. DEFLATE bytes performances for the FC task.

Figure 6. DEFLATE bytes performances for the PoI task.

Figure 7. DWT bytes performances for the FC task.

Figure 8. DWT bytes performances for the PoI task.

Table 3. Best performances (by $R^2$) in the FC task selecting up to 15 features using (a) forward greedy and (b) lazy forward greedy search.

(a)
	$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$				$\mathrm{G}\mathrm{O}\mathrm{F}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{L}\mathrm{R}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{r}+\mathrm{C}$
${\omega }_{com}$	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB
0.000	15	0.739	0.070	134.3	6	0.749	0.062	87.8	6	0.709	0.082	82.1	14	0.772	0.059	87.5
0.200	14	0.738	0.071	120.2	6	0.706	0.063	38.3	1	0.436	0.166	15.4	12	0.742	0.063	48.7
0.400	12	0.711	0.073	98.4	6	0.732	0.062	30.2	1	0.436	0.166	15.4	4	0.714	0.068	29.4
0.600	15	0.734	0.069	114.7	6	0.706	0.063	26.4	1	0.436	0.166	15.4	4	0.717	0.065	27.0
0.800	13	0.616	0.080	99.1	7	0.651	0.068	27.3	1	0.436	0.166	15.4	7	0.713	0.066	27.6
1.000	15	0.571	0.084	101.7	10	0.548	0.082	32.1	1	0.436	0.166	15.4	7	0.710	0.067	27.7
(b)
	$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$				$\mathrm{G}\mathrm{O}\mathrm{F}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{L}\mathrm{R}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{r}+\mathrm{C}$
${\omega }_{com}$	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB	#	$R^2$	$\mathrm{M}\mathrm{A}\mathrm{E}$	KB
0.000	3	0.304	0.165	42.3	6	0.754	0.076	85.0	4	0.692	0.075	66.3	11	0.769	0.054	91.7
0.200	13	0.270	0.165	46.9	7	0.733	0.070	36.3	5	0.660	0.076	34.8	2	0.692	0.074	34.0
0.400	8	0.234	0.166	43.9	5	0.719	0.068	26.7	5	0.610	0.088	28.4	5	0.680	0.072	43.4
0.600	4	0.279	0.169	39.9	7	0.663	0.073	29.5	8	0.620	0.083	31.6	5	0.664	0.076	30.6
0.800	5	0.284	0.173	39.9	6	0.644	0.083	25.9	7	0.544	0.094	29.0	13	0.704	0.072	45.5
1.000	4	0.287	0.175	38.0	8	0.622	0.090	29.1	7	0.518	0.099	27.6	13	0.712	0.071	45.6

Table 4. Best performances (by $\mathrm{A}\mathrm{U}\mathrm{C}$) in the PoI task selecting up to 15 features using (a) forward greedy and (b) lazy forward greedy search.

(a)
	$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$				$\mathrm{G}\mathrm{O}\mathrm{F}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{L}\mathrm{R}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{r}+\mathrm{C}$
${\omega }_{com}$	#	AUC	F 1	KB	#	AUC	F 1	KB	#	AUC	F 1	KB	#	AUC	F 1	KB
0.000	15	0.874	0.761	25.1	1	0.926	0.588	9.5	1	0.884	0.573	10.4	1	0.961	0.684	12.4
0.200	15	0.888	0.787	12.7	13	0.952	0.828	4.6	1	0.937	0.772	1.2	3	0.925	0.676	2.3
0.400	15	0.916	0.806	8.4	1	0.946	0.722	1.2	1	0.937	0.770	1.2	1	0.947	0.777	1.2
0.600	13	0.928	0.752	5.7	1	0.946	0.720	1.2	1	0.937	0.770	1.2	1	0.947	0.777	1.2
0.800	15	0.911	0.749	5.9	1	0.946	0.720	1.2	1	0.937	0.770	1.2	1	0.947	0.777	1.2
1.000	9	0.874	0.640	4.0	1	0.946	0.720	1.2	1	0.937	0.770	1.2	2	0.930	0.640	1.5
(b)
	$\mathrm{M}\mathrm{R}\mathrm{M}\mathrm{R}+\mathrm{C}$				$\mathrm{G}\mathrm{O}\mathrm{F}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{L}\mathrm{R}\mathrm{r}+\mathrm{C}$				$\mathrm{W}\mathrm{S}\mathrm{V}\mathrm{M}\mathrm{r}+\mathrm{C}$
${\omega }_{com}$	#	AUC	F 1	KB	#	AUC	F 1	KB	#	AUC	F 1	KB	#	AUC	F 1	KB
0.000	12	0.784	0.518	23.5	1	0.948	0.606	11.9	1	0.902	0.569	12.3	2	0.952	0.662	11.9
0.200	3	0.636	0.295	6.5	1	0.948	0.783	1.1	1	0.939	0.770	1.2	15	0.887	0.521	6.3
0.400	9	0.714	0.372	3.7	1	0.948	0.783	1.1	1	0.939	0.770	1.2	5	0.862	0.560	2.3
0.600	14	0.713	0.457	3.9	1	0.946	0.783	1.1	1	0.943	0.767	1.2	1	0.848	0.671	1.2
0.800	3	0.806	0.333	1.9	1	0.946	0.783	1.1	1	0.943	0.767	1.2	1	0.848	0.671	1.2
1.000	3	0.806	0.332	1.9	1	0.946	0.783	1.1	1	0.943	0.767	1.2	12	0.854	0.632	3.1

Figure 9. Number of feature set evaluations for the FC task.

Figure 10. Number of feature set evaluations for the PoI task.