A category-based probabilistic approach to feature selection

1.   Introduction

In high dimensional, large sample categorical data analysis, feature selection or dimension reduction is usually involved. Existing feature selection procedures either call upon the original variables or rely on linear models (or generalized linear models). Linear models are restrained by certain assumptions of multivariate distribution of data. Some categories in the original categorical explanatory variables may not be informative enough, redundant or even irrelevant with the response variable. Besides, a regular feature selection's statistical reliability may be jeopardized if it picks up variables with a large domains. So we propose a category-based probabilistic approach for feature selection.

One can refer to [10,8] for more introductions to various data types and algorithms in feature selection. The reliability was introduced by variance in [9,3] and by proportion of categories in [5]. The reliability measure used here was proposed in [6], denoted as $E(\mbox{Gini}(X|Y))$, which measures variable($X$)'s conditional concentration on variable $Y$. One straightforward reason for this measure is to believe that an explanatory variable is more statistically reliable when its domain is more concentrated with respect to the given response variable.

As in [6], we propose a category based feature selection method in this article to improve the statistical reliability and to increase the overall point-hit accuracy by merging or removing the less-informative or redundant categories in the categorical explanatory variables. Instead of doing as in [6], we first transform each original categorical explanatory variable into multiple dummy variables, then select the more informative ones by a stepwise forward feature selection approach, and then merge the unselected categories. The merging process in [6], on the other hand, is to find less informative categories within those pre-selected original explanatory variables and merge. Our proposed approach here can compare not only the categories within one explanatory variable one another, but also among the categories in other explanatory variables. Certain introductions and applications to dummy variable can be found in [1,2].

The rest of this article is organized as follows. Section 2 introduces the association measures and the reliability measures; Section 3 introduces the dummy variable approach, proves two theorems, and proposes the detailed feature selection steps; two experiments are conducted in Section 4; we briefly summarize results of this article in the last section.

2.   Data based association and explanatory reliability

Assume we are given a data set with one categorical explanatory variable $X$ with domain $\mbox{Domain}(X) = \{1, 2, \ldots, n_X\}$, and one response variable $Y$ with domain $\mbox{Domain}(Y) = \{1, 2, \ldots, n_Y\}$. We show our schemes with two Goodman-Kruskal association measures, the GK-lambda and the GK-tau. More details of these associations and the feature selection issues can be found in [8,4]. Please note that these measures can be extended to a categorical multivariate case since the multiple values of a multivariate set can be regarded as "one-dimensional" nominal values.

2.1.   Association measures: The GK-lambda and the GK-tau

The GK-lambda (denoted as $\lambda$ thereafter) is for modal (or optimal) prediction given as follows.

where

Please note that $p(\cdot)$ is the probability of an event. One can see that $\lambda$ is the relative decreasing rate of the error of predicting $Y$ with $X$ to that without $X$ when the modal prediction is applied; while the GK-tau (denoted as $\tau$ thereafter) is the counterpart for the proportional prediction as follows.

where

Both $\tau$ and $\lambda$ are used to measure the prediction errors: the first one aims to maximize the point-to-point accuracy and the second one maximize the point hit accuracy under the reasonable assumption that the predicted response variable and the actual response variable share the same distribution (in other words, both the training and predicted are identical in distributions). In practice, a feature selection needs to take care of both data-based association and statistical reliability of features selected. Sometimes, even the balance between model and proportional association has to be considered, cf. Huang and Pan [7].

2.2.   Reliability measure: $E(\mbox{Gini}(X|Y))$

Given a categorical data set with two variables $X$, $Y$ as above, Huang, Li and Pan [6] proposed the following statistical reliability measure of predicting $Y$ based on the information of $X$.

Notice that

and the smaller $E(\mbox{Gini}(X|Y))$, the more reliable the explanatory information. The size of $\mbox{Domain}(X, Y)$ determines the upper bound of $E(\mbox{Gini}(X|Y))$.

3.   Extraction of informative categories

3.1.   Dummy variables and two propositions

We transform $X$ into $n_X$ dummy variables, written as $X_1, X_2, \ldots, X_{n_X}$, where $X_i$ takes value $1$ if $X = i$; otherwise $X_i$ takes value $0$. The following proposition is to ensure that this transformation does not change the association of $Y$ with $X$ (when sample size is large enough).

Proposition 3.1.

Proof. Since $E_p(Y)$ is a constant for a given data set, we have $\tau(Y|X)\propto \omega^{Y|X}$, where

Thus we only need to prove that

Since

and

we have

So

that is,

It is of interest to introduce the following notion.

Definition 3.1. For a given categorical response variable $Y$ and an association measure $\beta^{Y|X}$, a categorical explanatory variable $X$ is referred to as reduced if merging of any two classes of $X$ does not strictly decreases $\beta$.

The next proposition tells that merging two categories in $X$ usually decreases (data-based) association.

Proposition 3.2. If two categories, $s, t$ in $X$ are merged into a new level, we have

where $X'$ is the merged new explanatory variable with only $n_X-1$ categories.

Proof. Notice that this proposition is equivalent to the following inequality.

Let

We have

where $m$ is the new category merged from $s$ and $t$, because

and

Multiplying $p(X = s)+p(X = t)$ to two sides of (1) and of(2), we have

Since $2b_sb_t\leq (b_s^2+b_t^2)$, we have

and the equality holds if and only if $b_s = b_t$.

In actual high dimensional data analysis projects, there are usually some categories in some explanatory variables that can be merged such that the association degree decrease is ignorable while the merge raises significantly selected features' statistical reliability. This is especially the case when the data set is high dimensional and many explanatory variables have many categories. Two experiments are conducted in the next section to support this supposition by showing that with similar reliability, merging categories can significantly increase the statistical reliability while not reducing association degree significantly.

3.2.   Feature selection process

A feature selection procedure usually follows a stepwise forward variable selection scheme, in which explanatory variables are selected one by one until certain pre-assigned threshold is hit. A reasonable threshold to stop the process is set by an acceptable association degree and statistical reliability. Specifically, for a given set of explanatory variables $X = \{X_1, X_2, \cdots, X_n\}$, and a response variable $Y$,

1. identify a subset of explanatory variables, denoted as $D_1$, that have the highest association degree among a set of unselected explanatory variables, denoted as $X \backslash D_0$, by

where $D_0$ is the set of previously selected explanatory variables;

2. select the one in $D_1$ with the highest reliability:

3. define the new set of selected variables as follows.

4. repeat the previous steps until the stopping criterion is met.

Thus the idea of this general feature selection process is to select a set of variables with the highest association degree and the reliability from the previous step, or with the association degree from the previous step and the highest statistical reliability. More detailed explanations and similar procedures can be found in [8].

3.3.   Our category-based forward selection process

The category based version of the previous procedure is to transform all the original (non-binary categorical) explanatory variables into dummy variables before the general steps. The unselected categories are then merged into a new category in each original variable as described below.

1. Transform each original variable $X_i$ into $n_i$ dummy variables. Then there are totally $M = \sum_{i = 1}^n n_i$ binary variables, denoted as $X_{11}, \cdots, X_{1, n_1}, \cdots$, $X_{n, n_n}$.

2. Follow the steps in Section (3.2) to select $m$ out of $M$ binary variables, where $m = \sum_{i = 1}^{n_t}n'_i$, $1 \leq n_t\leq n$ and $n'_i$ is the number of selected categories in $X_i$.

3. Merge the remaining $n_i-n'_i$ categories in $X_i$ into one new category and denote the new variable by $X'_i$. We then have the selected new variables as $X'_1, X'_2, \ldots, X'_{n_t}$.

3.4.   Complexity analysis

Notice that despite the genuine advantage of the category-based forward selection process, it has a higher time cost than the corresponding original variable based approach. It has to go through more loops to reach the same target given more features to be scanned. Generally, a complexity analysis needs to be related to a specifically designed and implemented algorithm. However, it is not this article's objective to discuss this subject in detail thus a brief discussion is carried out as follows.

Assume that the time cost for one variable set's association is a constant $C$, and that there are $N$ independent variables in the data set with $m$ categories in each variable on average. Further assuming that the original variable based process stops at $M_1$ variables and the category-based one stops at $M_2$ binary variables, we have the time cost of an original variable based feature selection method as $O(\frac{M_1(2 N - M_1+1)}{2})$ and that of a category-based one as $O(\frac{M_2(2 N m - M_2+1)}{2})$.

4.   Experiments

The experiment's purpose is to evaluate the association and the reliability differences between the category based and the original variable based feature selection processes. The first experiment uses the mushroom data set from UCI Machine Learning Repository[13]. It has $8,124$ observations with $22$ categorical variables. The second one uses the data set from a 1996 survey of family expenditure by Canada [12], shortened as FAMEX96. It has $10,417$ instances with more than $250$ continuous and categorical variables.

4.1.   Experiment on mushroom data

The mushroom's type is chosen as the response variable while the other 21 variables are the explanatory ones. We are going to compare the feature selection result by the original variables and that by the transformed dummy variables. Please note that $X_2$ in Table 1 is the set of selected original variables and $X'_2$ in Table 2 is the selected new variables with merged categories after the feature selection to the dummy transformation. We use $EG$ as a short for $E(\mbox{Gini}(X|Y))$.

As described in Table 1, there can only be four variables by the feature selection through the original variables with the final association which reaches the maximum (data-based) association degree as $1$ and the reliability ($EG(X|Y)$) is as poor as $0.9076$.

The category-based feature selection always gives rise to remarkably better reliability ($EG(X|Y)$) and higher associations ($\lambda$ or $\tau$).

It is also see from these two tables that we have in both experiments a higher association by the categories than that by the original variables given the same reliability threshold: for an almost equal reliability, say, $EG\approx 0.46$, the original variable based version gets a $\tau = 0.9429$ but the category version gets a $\tau = 0.9962$. The same story holds for $\lambda$.

4.2.   Experiment on FAMEX96 data

In this experiment, variable HouseholdType is chosen as the response variable and all other $24$ categorical variables are considered as the explanatory variables. Following the similar pattern as in the previous experiment, we have the feature selection results by the original variables in Table 3 and by the dummy variables (or categories) in Table 4.

One can see from these two tables that the category based approaches produces an association degree $\tau = 0.3242$ with a reliability measure of $0.5491$, while the original variable approach gives association degree $\tau = 0.3005$ with a significantly lower reliability as $EG = 0.8201$. When the association reaches $\tau = 0.3948$ in the original version, its reliability is as low as $0.9046$. But the category version can still have about $20\%$ better reliability as $0.7035$. Another perspective of this story is that the dummy method can give us more choices when we have to choose between the association and the reliability since the original method only gives three choices when the reliability reaches a unreliable $0.9833$ but the result from the category based approach offers us more options.

5.   Conclusion

By transforming the categorical explanatory variables into their dummy forms and applying feature selection procedure to the transformed variables, we can select the informative categories and merge the less informative or redundant categories in the explanatory variables in order to increase the association and raise the reliability. $E(\mbox{Gini}(X|Y))$ measures the statistical reliability. Experiments are conducted to show that both the association and the reliability are significantly better with the category-based feature selection than with original variables. Of course, the cost of category based approach is higher than the original variable based one. So in the situations that the dimension is not too high, the time cost (or computing complexity) of this category based approach is acceptable.