Group feature screening based on Gini impurity for ultrahigh-dimensional multi-classification

1.   Introduction

Ultrahigh-dimensional data are commonly available for a wide range of scientific research and applications. Feature screening plays an essential role in ultrahigh-dimensional data, where Fan and Lv ^[5] first proposed sure independence screening (SIS) in their seminal paper. For linear regressions, they showed that the approach based on Pearson correlation learning possesses a screening property. That is, even if the number of predictors $P$ can grow much faster than the number of observations n with $\log{P} = O(n^\alpha)$ for some $\alpha\in(0, \frac{1}{2})$, all relevant predictors can be selected with a probability tending to one ^[6].

To address ultrahigh-dimensional feature screening in the classification problem, Mai and Zou ^[11] applied a Kolmogorov filter to ultrahigh-dimensional binary classification. Cui et al. ^[4] proposed a screening procedure using empirical conditional distribution functions. The proposed screening methods assume that the types of data are continuous. Assume that the types of data are continuous. For categorical covariates, Huang et al. ^[8] constructed a model-free discrete feature screening method based on Pearson Chi-square statistics and showed its screening property fulfilling Fan et al. ^[6] when all covariates were binary. Ni and Fang ^[12] proposed a model-free feature screening procedure based on information entropy theory for multi-class classification. Ni et al. ^[13] further proposed a feature screening procedure based on weighting the Adjusted Pearson Chi-square for multi-class classification. Sheng and Wang ^[17] proposed a new model-free feature screening method based on the classification accuracy of marginal classifiers for ultrahigh-dimensional classification. However, some covariates existed in the groups, especially discrete and categorical covariates that showed microarrays, genomics, brain images and quantitative measurements. A fair number of grouped variable selection methods arise from individual variable selection and yield a sparse solution at the group level, or even at the within-group level. Refer to group LASSO ^[22], group SCAD ^[21], group MCP ^[2], group hierarchical LASSO ^[23], group bridge ^[9] and group exponential LASSO ^[1]. When the regularization parameter is set for non-sparse estimation, some grouped variable selection algorithms may fail to converge, causing non-identifiability problems and near-singularity problems. Even if the algorithm converges in the setting of a large group and small sample $n$, the estimated coefficients are not likely to be globally optimal solutions. Therefore, to reduce the number of groups before selecting important groups and variables within these groups, there is a need for new screening methods. For ultrahigh-dimensional data with grouping structures, Niu et al. ^[15] applied working independence in linear models to propose a group-screening approach. Song and Xie ^[18] further used F-test statistics to construct a group screening approach that improved marginal methods by reducing the burden of multiple testing and aggregating individual effects. With regard to ultrahigh-dimensional group data in the linear model, Qiu and Ahn ^[16] proposed group sure independence screening (gSIS), group high dimensional ordinary least-squares projector (gHOLP) and group wise adjusted R-squares screening (gAR2). He and Deng ^[7] applied joint information entropy to screen for important grouped covariates.

In this study, we propose a model-free group feature screening method for ultrahigh-dimensional multi-classification of categorical. Our proposed group screening method is based on the Gini impurity to evaluate the predictive power of grouped covariates. The Gini impurity is a non-purity attribute splitting index, which was proposed by Breiman et al. ^[3] and has been widely used in decision tree algorithms, such as CART and SPRINT. Regarding categorical covariate screening, we can apply the index of purity gain, which is the same as the information gain ^[12]. As in Ni and Fang ^[12], continuous covariates can be sliced using standard normal quantiles. The proposed grouped feature screening procedure is based on the purity gain, which is referred to as GP-SIS. Theoretically, the GP-SIS is rigorously proven to enjoy Fan and Lv ^[5] proposed a sure screening property that ensures that all important features can be obtained. Practically, as shown by the simulation results, compared with the existing group feature screening method and single covariate feature screening, GP-SIS has a better performance.

The remainder of this paper is organized as follows. Section 2 describes the proposed GP-SIS method in detail. In Section 3, the screening property is established. In Section 4, numerical simulations and an example of real data analysis are presented to assess the performance of the proposed method. Some concluding remarks are given in Section 5, and all proofs are provided in the Appendix.

2.   Group feature screening procedure

We first introduce the Gini impurity and purity gain and then propose a screening procedure based on purity gain.

2.1.   Gini index and purity gain

Each grouped covariate can be regarded as a whole. Suppose that $Y$ is a categorical response, and covariate matrix $X$ is a multivariate covariate matrix of $n \times P$ dimension with $G$ grouped covariates, which can be represented in Table 1.

Here, $X_g = (X_{g1}, X_{g2}, \cdots, X_{gp_g})$ represents the $g$-th group covariate, $p_g$ represents the dimension of the covariates in the $g$-th group covariates, and $P = \sum_{g = 1}^{G}p_g$. To introduce the Gini impurity and purity gain, assume that all the covariate components of the covariate matrix $X$ are classified with $J$ categorizes $\{1, \cdots, J\}$. The values of any element in $X_g \in \{1, \cdots, J\}$, $J^{p_g}$ combinations were formed. $J_g$ represents the last combinations between covariate categories in the $g$-th group covariate matrix, $J_g = (j_{p_g}, j_{p_g}, \cdots, j_{p_g})$. Here, ${\boldsymbol j}_g = (j_1, \cdots, j_{p_g})$ represents the indicator variable in the combination between covariate categories in the g-th group covariate matrix, and $j_1$ represents the first covariate category combination.

Let $p_r = P(Y = r)$ represent the probability function of a response variable, $w_{{\boldsymbol j}_g} = w_{(j_1, \cdots, j_{p_g})} = P(X_{g1} = j_1, \cdots, X_{gp_g} = j_{p_g})$ represent the probability function of group covariate, and $p_{{\boldsymbol j}_gr} = p_{(j_1, \cdots, j_{p_g})r} = P(Y = r \vert X_{g1} = j_1, \cdots, X_{gp_g} = j_{p_g})$ represent the probability function of response variables under the condition of group covariates, where $g \in \{1, \cdots, G\}, (j_1, \cdots, j_{p_g}) \in \{(1, 1, \cdots, 1), (2, 1, \cdots, 1) \cdots, (J, J, \cdots, J)\}, r \in \{1, \cdots, R\}$. The marginal Gini impurity of $Y$ is defined as

Conditional Gini impurity is defined as

Similar to the information gain, the purity gain is defined as

In Eq (2.1), $Gini(Y)$ is non-negative and acquires its maximum $1-\frac{1}{R}$ if and only if $p_1 = \cdots = p_R = \frac{1}{R}$ by Jensen's inequality. The $Gini(Y \vert X_g)$ in Eq (2.2) is the conditional Gini impurity of $Y$ given $X_{g1} = j_1, \cdots, X_{gp_g} = j_{p_g}$. Further support can be provided by the following proposition.

Proposition 2.1. When $X_g$ is a categorical covariable, we obtain $GP(Y \vert X_g)\geq0$, and $X_g$ and $Y$ are independent if and only if $GP(Y \vert X_g) = 0$.

For continuous $X_g$, the conditional Gini impurity cannot be directly calculated, and the purity gain by slicing $X$ into several categories. For a fixed integer $J\geq2$, let $q_{(j)}$ be the $j/J$-th percentile of $X$, $j = 1, \cdots, J-1$, $q_{(0)} = -\infty$ and $q_{(J)} = +\infty$. Replacing $w_{{\boldsymbol j}_g}$ and $p_{{\boldsymbol j}_gr}$ in Eq (2.3), respectively, by

We define conditional Gini impurity based on continuous covariates:

Proposition 2.2. When $X_g$ is a continuous covariable, we obtain ${GP}_J(Y \vert X_g)\geq0$, and $X_g$ and $Y$ are independent if and only if ${GP}_J(Y \vert X_g) = 0$.

2.2.   Grouped feature screening procedure based on purity gain

First, we select a medium-scale simplified model that can almost fully contain $D$, where $D =$\{$g:F(Y \vert x)$ functionally depends on $X_g$ for some $Y = r$\}, using an adjusted purity gain index for each pair $(Y, X_g)$ as follows:

Here, $p_r = P(Y = r)$, $w_{{\boldsymbol j}_g} = w_{(j_1, \cdots, j_{p_g})} = P(X_{g1} = j_1, \cdots, X_{gp_g} = j_{p_g})$ when $X_g$ is a categorical group, $N_g$ represents the number of group categories of $X_g$, and $p_{{\boldsymbol j}_gr} = p_{(j_1, \cdots, j_{p_g})r} = P(Y = r \vert X_{g1} = j_1, \cdots, X_{gp_g} = j_{p_g})$.

When $X_g$ is defined as continuous group covariates, $p_{{{\boldsymbol j}_g}r} = P(Y = r \vert X_{g1}\in(q_{g1, (j-1)}, q_{g1, {(j)}}], \cdots, X_{gp_g}\in(q_{gp_g, (j-1)}, q_{gp_g, (j)}])$, where $q_{g1, j}$ represents $j/J$ percentile of $X_{g1} \cdot J_g = J^{P_g}$, and $J$ represents the number of slices applied to $X_g$. In this case, $N_g = J^{P_g}$.

There may be more categories of group covariates associated with larger purity gain in the original definition of Eq (2.3), regardless of whether the group covariates are important, especially when the number of categories involved in each group covariate is different. Therefore, Ni and Fang ^[12] used $\log J_k$ to construct an information gain ratio to solve this problem, where each category of $X_k$ is the same. Similarly, when each category of $X_g$ is the same, for Eq (2.8), we apply the $\log{N_g}$ to build an adjusted purity gain index to address the problem, which is also applied to continuous $X_g$. However, when each category of $X_g$ is different, $1-\sum_{{\boldsymbol j}_g = c(1, 1, \cdots, 1)}^{J_g}w_{{\boldsymbol j}_g}^2$ is defined as an adjustment factor, motivated by the split of $X_g$ into several categories via the Decision Tree algorithm.

For group sample data $\{x_{i, g1}, \cdots, x_{i, gp_g}, y\}$, $i = 1, \cdots, n$, $e_g$ can be easily estimated by

When $X_g$ is categorical,

When $X_g$ is continuous,

Here, $q_{g1, j}$ is the $j/J$th sample normal percentile of $\{x_{1, g1}, \cdots, x_{n, g1}\}$. In either case, ${\hat{p}}_r = \frac{1}{n}\sum_{i = 1}^{n}I\{y_i = r\}$.

We suggest selecting a sub-model $\hat{D} = \{g:{\hat{e}}_g\geq c n^{-\tau}, 1\le g\le G\}$, where both $c$ and $\tau$ are predetermined thresholds established via condition (C2) in Section 3. In practice, we can choose a model $\hat{D}$ = $\{$ $g:{\hat{e}}_g$ is among the top of $d$ largest of all $\}$, where $d = [n/\log{n}]$.

3.   Group feature screening property

In this section, we establish the screening properties of the GP-SIS. Based on the sure independent screening theories proposed by Ni and Fang ^[12] and He and Deng ^[7], the following conditions are assumed:

Condition 1 (C1). There exist two positive constants $c_1$ and $c_2$ such that $c_1/R\le p_r\le c_2/R$, $c_1+c_2\le R$, $c_1/R\le p_{{\boldsymbol j}_gr}\le c_2/R$ and $c_1/N_g\le w_{{\boldsymbol j}_g}\le c_2/N_g$ for every $1\le g\le G$, $1\le r\le R$ and ${\boldsymbol j}_g \in \{(1, 1, \cdots, 1), (2, 1, \cdots, 1), \cdots, (J, J, \cdots, J)\}$.

Condition 2 (C2). There exists a positive constant $c > 0$, and $0\le\tau < 1/2$ such that $\min_{g\epsilon D}{e_g\geq2cn^{-\tau}}$.

Condition 3 (C3). $R = O(n^\varepsilon)$, $J = \max_{1\le g\le G}{N_g = O(n^\kappa)}$, where $\varepsilon\geq0$, $\kappa \geq 0$ and $2\tau+2\varepsilon+2\kappa < 1$.

Condition 4 (C4). There exists a positive constant $c_3$, such that $0 < f_g(x \vert Y = r) < c_3$ for any $1\le r\le R$, and $x$ is in the domain of $X_g$, where $f_g(x \vert Y = r)$ is the Lebesgue density function of $X_g$ conditional on $Y = r$.

Condition 5 (C5). There exists a positive constant $c_4$, and $0\le\rho < 1/2$ such that $f_g(x)\geq c_4n^{-\rho}$ for any $1\le g \le G$ and $x$ in the domain of $X_g$, where $f_g(x)$ is the Lebesgue density function of $X_g$. Furthermore, $f_g(x)$ was continuous in the domain of $X_g$.

Condition 6 (C6). $R = O(n^\varepsilon)$, $J = \max_{1\le g\le G}{N_g = O\left(n^k\right)},$ where $2\tau+2\varepsilon+2\kappa+2\rho < 1$ and $\varepsilon\geq0, \kappa\geq0$.

Condition 7 (C7). $\lim{\inf_{p\rightarrow \infty}\{\min_{g\epsilon D}{e_g-\max_{g\epsilon I}{e_g}}\}\geq\delta}$, where $\delta > 0$ is a constant.

Condition (C1) guarantees that the proportion of each class of variables cannot be either extremely small or extremely large. A similar assumption was made for conditions (C1) in Huang et al. ^[8] and Cui et al. ^[4]. According to Fan and Lv ^[5] and Cui et al. ^[4], Condition (C2) allows the minimum true signal to disappear to zero in the order of $n^{-\tau}$ as the sample size goes to infinity. According to Ni and Fang ^[12] and He and Deng ^[7], Condition (C3) provides for the covariates to diverge with a certain order and number of classes for the response, and Condition (C6) slightly modifies Condition (C3). To ensure that the sample percentiles are close to the true percentiles, Condition (C4) rules out the extreme case in which some $X_g$ places a heavy mass in a small range. Condition (C5) requires $n^{-\rho}$ as the lower bound of the density. Cui et al. ^[4] and Zhu et al. ^[24] proposed the ranking consistency property; assuming the inactive covariate subset $I = \{1, \cdots, P\} \backslash D$, then Condition (C7) is established; a similar assumption was also made by Ni and Fang ^[12] and He and Deng ^[7].

Theorem 3.1 (Sure screening property). Under conditions (C1) to (C3), if all the covariates are categorical, we obtain:

where $b$ denotes a positive constant. If $\log{p} = O\left(n^\alpha\right)$ and $\alpha < 1-(2\tau+2\varepsilon+2\kappa)$, GP-SIS exhibits a sure screening property.

Theorem 3.2 (Sure screening property). Under conditions (C4)–(C6), when the covariates comprise continuous and categorical variables, we obtain

where $b$ denotes a positive constant. If $\log{p} = O(n^\alpha)$ and $\alpha < 1-(2\tau+2\varepsilon+2\kappa+2\rho)$, GP-SIS exhibits a sure screening property.

Theorem 3.3 (Ranking consistency property). Under conditions (C1), (C4), (C5) and (C7), if $\log{\frac{RN_g}{\log{n}} = O(1)}$ and $\frac{\max{\{\log{p}, \log{n}\}}R^4{N_g}^4}{n^{1-2\rho}} = O(1)$, then $\lim {\inf_{n\rightarrow \infty}\{{min}_{g\epsilon G}{{\hat{e}}_g-{max}_{g\epsilon I}{{\hat{e}}_g}}\}} > 0, a.s$.

Theorem 3.3 testifies that the proposed screening index can effectively separate active and inactive covariates at the sample level.

4.   Numerical studies

4.1.   Simulation results

In this subsection, we conduct four simulation studies to demonstrate the finite sample performance of the group screen methods described in Section 2. We compared GP-SIS with IG-SIS ^[12] and GIG-SIS ^[7] in terms of performance using the following evaluation criteria: we ranked the features inside each replication in accordance with each screening criterion and noted the minimum model size (MMS) required to accommodate all of the active features. The $5, 25, 50, 75$, and $95\%$ quantiles of the MMS over 100 replications were used to determine the screening performance. Following Shao and Zhang ^[20], we denote this as CPa. CPa close to 1 is evidence of sure screening for a procedure. We also consider predictor-specific inclusion proportions, which are denoted as $CP1$, $CP2$, and $CP3$, respectively. These represent the coverage probability, which is a given model size of $[n/logn]$, $2[n/logn]$, and $3[n/logn]$, including the indicators of all active covariates. This allows us to further investigate the active predictors that are easier to predict.

Model 1: categorical covariates and binary response

First, we consider the response variables of different categories. According to Ni and Fang ^[12] and He and Deng ^[7], we assume a model in which the response $y_i$ is binary, where $R = 2$, and all covariates are categorical. We consider two distributions for $y_i$:

(1) Balanced, $p_r = P(y_i = r) = 1/2$;

(2) Unbalanced, $p_r = 2[1+\frac{R-r}{R-1}]/3R$ with $\max_{1\le r\le R}p_r = 2\min_{1\le r\le R}p_r$.

The true model was defined as $D = \{1, \cdots, 9\}$ with $d_0 = 9$, and the group size was $d_{0G} = 3$. Under the condition of $y_i$, the latent variable is generated as $z_i = (z_{i, 1}, \cdots, z_{i, P})$, where $z_{i, k}\; N(u_{rk}, 1)$, $1\le k\le P$. Subsequently, we construct the active covariates:

(1) If $k > d_0$, then $u_{rk} = 0$;

(2) If $k\le d_0$ and $r = 1$, then $u_{rk} = -0.5$;

(3) If $k\le d_0$ and $r = 2$, then $u_{rk} = 0.5$.

Next, we apply the quantile of the standard normal distribution to generate the covariates. The specific approach is as follows.

(1) When $k$ is an odd number, that is, $x_{i, k} = I(z_{i, k} > z_{(\frac{j}{2})})+1$;

(2) When $k$ is an even number, that is, $x_{i, k} = I(z_{i, k} > z_{(\frac{j}{5})})+1$;

where $\alpha$th percentile of the standard normal distribution is $z_{(\alpha)}$.

Thus, among all $P$ covariates, the covariates of the two categories and five categories accounted for half. In this model, we considered $P = 1500$ and $n = 80,100,120$.

Table 2 shows the evaluation criteria over $100$ simulations for Model 1. The results argue that the proposed GP-SIS works well. When the sample size $n$ increases, GP-SIS is close to $d_{0G} = 3$ in MMS, and both increase to $1$ in coverage probability. MMS in an unbalanced response is better than in a balanced response in performance via comparing the responses of different structures. Moreover, GP-SIS is more robust than the other two methods in performance because the fluctuation range in MMS is small.

Model 2: categorical covariates and multi-class response

We consider more covariate classifications, and the response $y_i$ is multi-class, where $R = 10$. We consider $y_i$ of the two distributions:

(1) Balanced, $p_r = P(y_i = r) = 1/R$;

(2) Unbalanced, $p_r = 2[1+\frac{R-r}{R-1}]/3R$ with $\max_{1\le r\le R}{p_r = 2\min_{1\le r\le R}{p_r}}$.

The true model was defined as $D = \{1, \cdots, 9\}$ with $d_0 = 9$, and the group size was $d_{0G} = 3$. Condition on $y_i$, the latent variable is generated as $z_i = (z_{i, 1}, \cdots, z_{i, P})$, for covariates $X_k, x_{i, k} = f_k(\varepsilon_{i, k}+\mu_{i, k})$, where $\varepsilon_{i, k} \sim t(4)$ and $f_k(\cdot)$ represents a quantile function of standard normal distribution. We then construct the active covariates by defining $u_{i, k}$:

(1) If $k > d_0$, then $u_{rk} = 0$;

(2) If $\le d_0$, then $u_{rk} = 1.5\times(-0.9)^r$.

Next, we apply the $f_k(\cdot)$ to generate covariates and consider $P = 2000, n = 100,150,200$ in this model. The specific approach is as follows:

(1) For $k\le400$, $f_k(\varepsilon_{i, k}+\mu_{i.k}) = I(z_{i, k} > z_{(\frac{j}{2})})+1$;

(2) For $401\le k\le800$, $f_k(\varepsilon_{i, k}+\mu_{i.k}) = I(z_{i, k} > z_{(\frac{j}{4})})+1$;

(3) For $801\le k\le1200$, $f_k(\varepsilon_{i, k}+\mu_{i.k}) = I(z_{i, k} > z_{(\frac{j}{6})})+1$;

(4) For $1201\le k\le1600$, $f_k(\varepsilon_{i, k}+\mu_{i.k}) = I(z_{i, k} > z_{(\frac{j}{8})})+1$;

(5) For $1601\le k$, $f_k(\varepsilon_{i, k}+\mu_{i.k}) = I(z_{i, k} > z_{(\frac{j}{10})})+1$.

Thus, among all the $P$ covariates, the covariates of two, four, six, eight, and ten categories accounted for one-fifth each.

Table 3 shows the evaluation criteria over $100$ simulations for Model 2. Two methods in performance under Model 1 are worse than Model 2. When the model is more intricate, GP-SIS in performance is better than IG-SIS. Particularly, GP-SIS and GIG-SIS have a slightly small MMS under a small sample size $n$. When the sample size $n$ increases, GP-SIS is close to $d_{0G} = 3$ in MMS, and both increase to $1$ in coverage probability. MMS in an unbalanced response is better than in a balanced response in performance via comparing the responses of different structures. Furthermore, GP-SIS is more robust in performance because the fluctuation range in MMS is small.

Model 3: continuous and categorical covariates

Finally, among the covariates that are both continuous and categorical, we assume a more complex example, where response $y_i$ is multi-class with $R = 4$. We consider $y_i$ of the two distributions:

(1) Balanced, $p_r = P(y_i = r) = 1/R$;

(2) Unbalanced, $p_r = 2[1+\frac{R-r}{R-1}]/3R$ with $\max_{1\le r\le R}{p_r} = 2\min_{1\le r\le R}{p_r}$.

In this model, we consider $P = 3000, n = 180,220,260$. The true model is defined at $D = \{1, 2, 3,751,752,753, 1501, 1502,$ $1503, 1504, 1505, 1506\}$ with $d_0 = 12$, and the group size is $4$. Under condition $y_i$, the latent variable is generated as $z_i = (z_{i, 1}, \cdots, z_{i, p})$. For covariates $X_k, z_{i, k}\; N(\mu_i, 1), 1\le k\le P$, where $u_i = (u_{i1}, \ldots, u_{ip})^T$ with $u_{ik} = (-1)^r\theta_{rk}$ when $y_i = r$ and $k\in D$. According to He and Deng ^[7] and Ni and Fang ^[12], $\theta_{rk}$ is listed in Table 4. $u_{ik} = 0$ when $k\notin D$. To generate $X_k$:

For $k \le 750$, $x_{ik} = j, if z_{ik}\in(z_{(j-1)/4}, z_{j/4}]$;

For $750 < k \le 1500$, $x_{ik} = j, if z_{ik}\in(z_{(j-1)/10}, z_{j/10}]$;

For $1501 \le k$, $x_{ik} = z_{ik}$.

Thus, among all the $P$ covariates, the covariates of four categories and ten categories accounted for one- fifth, and the other covariates were continuous. Similarly, there are three in four categories and ten in ten categories, and the active covariates are continuous, accounting for half. For continuous covariates, we applied different slices, $J = 4, 8, 10$. The corresponding approaches were defined as GP-SIS-4, IG-SIS-4, GP-SIS-8, IG-SIS-8, GP-SIS-10 and IG-SIS-10. When the numbers of covariates are grouped, He and Deng ^[7] proposed a grouped feature screening algorithm by using the joint information entropy to screen some important grouped covariates. We denote these as GIG-SIS-4, GIG-SIS-8 and GIG-SIS-10.

Tables 5 and 6 present the simulation results with over $100$ simulations for the balanced and unbalanced cases, respectively. When the sample size $n$ increases, GP-SIS is close to $d_{0G} = 3$ in MMS, and both increase to $1$ in coverage probability. The coverage probability of GP-SIS is close to that of GIG-SIS in the five indexes. Therefore, it was proved that GP-SIS has the characteristics of group feature screening. MMS in an unbalanced response is better than in a balanced response in terms of performance by comparing the responses of different structures.

Furthermore, GP-SIS and GIG-SIS are robust in performance, because the fluctuation range in the MMS is small for the two types of responses. When different slices are applied in continuous covariates, GP-SIS and GIG-SIS are better in terms of the five indices of coverage probability and MMS in performance by comparing the responses of different structures. Therefore, three methods are independent of the number of slices in performance.

Model 4. Computational time complexity analysis

Similar to Model 1. However, for the distribution of $y_i$, we consider balanced data, that is, $P(y_i = r) = 1/2$. The true model was defined as $D = \{1, \ldots, 9\}$, with $d_0 = 9$ and $d_0G = 3$, and the group size was $3$. The active and irrelevant covariates were generated in the same way as in Model 1. Similarly, half of the p-dimensional covariates are two-category, while the other half are five-category covariates. Model 4 controls for a constant sample size of $150$ and considers a dimensional vector of covariates ranging from $1500$ to $10500$, with an equal series of 1000 equal differences. The running times of the five methods were recorded for each experiment, and the median running time in 100 replicate experiments was recorded as the running time index of the five methods. The trends of the five methods will be compared as the dimension of covariates increases to compare the computational complexities of the methods.

The median run times in Table 7 show a linear trend for the three methods as the sample size varies linearly. It can be observed that the running time of GP-SIS is not much different from that of GIG-SIS. In ultrahigh-dimensional feature screening, both GP-SIS and GIG-SIS are robust, but the computational time of GP-SIS is shorter than that of GIG-SIS. For grouped variable feature screening, our method was superior to GIG-SIS.

4.2.   Real data

In this subsection, we analyze a real data-set from the feature selection database at Arizona State University (http://featureselection.asu.edu/). The lung biological data included $203$ samples and $3312$ features, which were unbalanced owing the response variable. Every class is $139, 17, 21, 20$, and $6$, and the covariates are not only continuous but also have group correlations. We randomly divided the data into two parts, where $90\%$ of the data represented training data and $10\%$ of the data represented the test data. The sample sizes of training data and test data respectively are $n = 182$ and $n = 21$. The dimensions of both the training data and test data were $P = 3312$.

We utilized a ten-fold cross-validation method to assess the performances of various classification algorithms to eliminate the model accuracy issues caused by various training data. Active covariates were chosen by GP-SIS-10, IG-SIS-10 and GIG-SIS-10 based on the training data. We classified them using a variety of techniques, including Support Vector Machine ^[19], Random Forest (RF), and Decision Tree (DT) ^[10], using the active covariates chosen based on GP-SIS, IG-SIS and GIG-SIS. G-mean and F-measure are the evaluation indices employed. The performance of feature screening for unbalanced high-dimensional data improves with higher G-means and F-measures ^[7]. Table 8 shows the G-mean and F-measure for the training data and test data using the three classification techniques GP-SIS-10, IG-SIS-10 and GIG-SIS-10. Among all classification methods, GP-SIS exhibited the best performance, where F-measure of GP-SIS is closer to $1$ than those of the other two methods. However, the F-measure (test) of some response's class is a little small, which is close to $0$ in all classification methods. In other words, the proposed GP-SIS method performed better.

5.   Conclusions

In the data, there were continuous and categorical grouping covariates, and the response was categorical, which is common in practice, but the applicable screening methods are limited. We propose a GP-SIS procedure based on the Gini impurity to effectively screen grouping covariates. GP-SIS has a sure screening property and ranking consistency property, theoretically, and is model-free. When the numbers of categories of all grouping covariates are the same and different, GP-SIS is quite similar to GIG-SIS in performance, which can be shown in the simulation. Practically, as shown by the simulation results, compared with the existing group feature screening method and single covariate feature screening, GP-SIS has a better performance.

Group feature screening reports difficulties based on missing data. In the future, based on the classification model, we intend to propose a new group feature screening method for either the missing variable or response variable.

Acknowledgments

The work was supported by National Natural Science Foundation of China [grant number 71963008]. The authors are grateful to the editor and anonymous referee for their constructive comments that led to significant improvements in the paper.

Conflict of interest

All authors declare no conflicts of interest in this paper.

Availability of data

The lung biological data that support the findings of this study are available from the feature selection database of Arizona State University (http://featureselection.asu.edu/).

Appendix

Proof of Proposition 2.1. To prove Proposition 2.1, we need to define $f(x) = x^2$, proved to be close Ni and Fang ^[12]. By Jensen's inequality,

and then

The above equation holds if and only if $p_{(j_1, \cdots, j_{p_g})r} = p_{(j_1, \cdots, j_{p_g})'r}$, for any $1\ \le r\ \le R$, $1\le i\le p_g$ and $1\le j_{p_g}\le j'_{p_g} \le J$. That is, $X_g$ and $Y$ are independent.

Proof of Proposition 2.2. From the same proof as Proposition 2.1, we can get that $GP_J(Y \vert X_g) \geq 0$ holds if and only if $p_{(j_1, \cdots, j_{p_g})r} = p_{(j_1, \cdots, j_{p_g})'r}$. So, when $X_g$ and $Y$ are independent, $GP_J(Y \vert X_g) = 0$.

By $\sum_{j = 1}^J P(X_{g1}\in(q_{g1, (j-1)}, q_{g1, {(j)}}], \cdots, X_{gp_g}\in(q_{gp_g, (j-1)}, q_{gp_g, (j)}]) = 1$, we have $P(X_{g1}\in(q_{g1, (j-1)}, q_{g1, {(j)}}], \cdots, X_{gp_g}\in(q_{gp_g, (j-1)}, q_{gp_g, (j)}]) = (1/J)^{p_g}$ and $P(X_{g1} \leq q_{g1, j}, \cdots, X_{gp_g} \leq q_{gp_g, j} \vert Y = r) = (j/J)^{p_g}$ if covariates have a similar distribution.

Lemma 1 (Bernstein inequality). If $Z_1, \cdots, Z_n$ is an independent random variable with a mean value of 0, and bounded supporter is $[-M, M]$, then we have the inequality: $P(\vert \sum_{i = 1}^{n}Z_i \vert > t)\le 2exp\{-\frac{t^2}{2(v+\frac{Mt}{3})}\}$ where $v \geq Var(\sum_{i = 1}^{n}Z_i)$.

Lemma 2. For discrete group covariates $X_g$ and discrete response $Y$, we have the following three inequalities:

(a)$P(\vert {\hat{p}}_r-p_r \vert > t)\le 2\exp{\{-\frac{6nt^2}{3+4t}\}}$;

(b)$P(\vert {\hat{w}}_{{\boldsymbol j}_g}-w_{{\boldsymbol j}_g} \vert > t)\le 2\exp\{-\frac{6nt^2}{3+4t}\}$;

(c)$P(\vert {\hat{p}}_{{\boldsymbol j}_gr}-p_{{\boldsymbol j}_gr} \vert > t)\le 2\exp\{-\frac{6nt^2}{3+4t}\}$.

Proof of Lemma 2. Three inequalities are similar in the proofs, where inequality (a) and inequality (b), respectively, have been given at Ni ^[14] and He and Deng ^[7]. The following is the proof of inequality (c).

The expectation of ${\hat{p}}_{{\boldsymbol j}_gr}$ is

Let $Z_i = I\{y_i = r \vert X_{ig1} = j_1, \cdots, X_{igp_g} = j_{p_g}\}-p_{{\boldsymbol j}_gr}$, $Var(\sum_{i = 1}^{n}Z_i) = nVar(Z_i) = np_{{\boldsymbol j}_gr}(1-p_{{\boldsymbol j}_gr})\le\frac{n}{4}$ be known, and then

According to the Bernstein inequality, the formula is held.

Lemma 3. With regard to discrete group covariates $X_g$ and discrete response $Y$, for any $0 < \varepsilon < 1$, under condition (C1), we have $P(\vert {\hat{e}}_g-e_g \vert > 2 \varepsilon) \le O(RJ^3)\exp\{-c_5\frac{n \varepsilon^2}{R^2 J^6}\}$, where $c_5$ represents a positive constant.

Proof of Lemma 3. By $e_g$ and ${\hat{e}}_g$ in Section 2.2, we have

Since $\log{J} \geq \log2 \geq0.5$, we have

For $I_1$, we have

For $I_2$, we have

For $I_3$, we have

For $I_{31}$ and $I_{32}$, we have

In a word, we have the inequality

where $c_5$ represents a positive constant.

Proof of Theorem 3.1. By Conditions (C1) to (C3) and Lemma 3, we can get

where $b$ is a positive constant.

Lemma 4 (Lemma A.5 ^[7]). Under (C1), (C4) and (C5), mfor any $0 < \varepsilon < 1$, so for continuous $X_g$, we have $P(\vert {\hat{e}}_g-e_g \vert > 2 \varepsilon) \le O(RN_g)\exp\{-c_6\frac{n^{1-2p}\varepsilon^2}{R^4N_g^4}\}$, there exists a positive constant $c_6$.

Proof of Theorem 3.2. According to Lemma 4, the proof of Theorem 3.2 is the same as Theorem 3.1 and hence is omitted.

Proof of Theorem 3.3. According to Lemma 3 and 4 and under Conditions (C1), (C4), (C5) and (C7), we get

where $c_7 = \min\{c_5, c_6\}(\frac{\delta^2}{4})$. Since $\frac{\log(RN_g)}{\log{n}} = O(1)$, there exists a positive constant $c_8$ such that $\log(RN_g) \le c_8 \log{n}$. Also, $\frac{\max{\{\log{p}, \log{n}\}}R^4{N_g}^4}{n^{1-2\rho}} = O(1)$ implies that $\log{p} \le \frac{1}{2}c_7\frac{n^{1-2\rho}}{R^4N_g^4}$ and $\frac{1}{2}c_7\frac{n^{1-2\rho}}{R^4N_g^4} \geq (c_8+2)\log{n}$ for large $n$. Next, there exists a constant $n_0$, and we can get $\sum_{n = n_0}^{\infty}\exp\{\log{RN_g}+\log{p}-c_7\frac{n^{1-2\rho}}{R^4N_g^4}\}\le$$\sum_{n = n_0}^{\infty}\exp\{c_8\log{n}-\frac{1}{2}c_7\frac{n^{1-2\rho}}{R^4N_g^4}\}\le$$\sum_{n = n_0}^{\infty}\exp\{c_8\log{n}-\left(c_8+2\right)\log{n}\} = \sum_{n = n_0}^{\infty}n^{-2} < \infty$. According to Ni and Fang ^[12] and by the Borel Cantelli Lemma, we can get $\lim{{inf}_{n\rightarrow \infty}\{{min}_{g\epsilon G}{{\hat{e}}_g-{max}_{g\epsilon I}{{\hat{e}}_g}}\}}\geq\frac{\delta}{2} > 0, a.s$.