How to automatically group categorical explanatory variables in a linear regression model? I have a dataset with $10^3$ to $10^4$ observations, where each observation consists of a single (scalar) response variable $y$ and $N \approx 10^2$ explanatory variables $X_1, ..., X_n$. All the explanatory variables are categorical (say belonging to categories "A", "B", or "C"), so I represent each one of them with a two-level dummy encoding (i.e. category "A" is taken as the reference level, category "B" is represented by the vector $(1, 0)$ and "C" by $(0,1)$). My objective is to fit and assess different linear models to predict $y$ given $(X_{i})_{1 \leq i \leq N}$.
Looking at the samples in my dataset, I can clearly see some significant group effects. For example, I do not see a strong cross-correlation between $y$ and the independent explanatory variables $X_1$, $X_2$ and $X_3$. However, when $X_1$, $X_2$ and $X_3$ vary together, their variation (as a group) seems to be strongly correlated to the variations of $y$. In my opinion, this suggests that $X_1$, $X_2$ and $X_3$ could be grouped into a new variable $Z_1$, and the linear model could be built with respect to this new explanatory variable, instead of the original $X_i$'s.
Now, my question is how to build the new grouped variables $Z_k$ in an automatic fashion. Ideally, I would like each group of variables to be as large as possible, and I would like the final linear model to be as sparse as possible. I have already looked at a few possibilities, but they are not completely suitable for my problem, so any suggestion would be very welcome.
1. PCA
PCA applied as a dimensionality reduction method to the predictors $(X_i)_{1 \leq i \leq N}$ does not appear suitable for my problem for two reasons: (1) it does not include a response variable, and (2) it gives a linear combination of explanatory variables, whereas what I am looking for is a group of variables (roughly speaking a linear combination with binary coefficients).
2. Canonical Correlation Analysis
CCA (or Cross Decomposition in Scikit-Learn), does incorporate the response variable information, but similarly to PCA it builds a linear combination of explanatory variables, which is not what I am looking for.
3. Linear Discriminant Analysis Similarly to PCA and CCA, LDA produces a linear combination of explanatory variables, which is not exactly what I am looking for. In addition, to my understanding it is usually applied for classification.
4. Group Lasso Group Lasso seems to match many of my requirements: it does incorporate the response variable, it does build a linear regression model based on groups of explanatory variables. The problem is that these groups need to be built manually, or known a priori, which is precisely what I am trying to achieve. I could maybe even reformulate the question as "How to automatically build the groups of variables to be used in Group-Lasso?".
5. Multi-factor Dimensionality Reduction
MDR seems to be promising, as it is able to build groups of explanatory variables, while also incorporating the information of the response variable. However, this method does not seem as classical/well-known as the ones mentioned above, and it is not clear to me how the new grouped variable is built from the original explanatory variables (in particular how to set an appropriate threshold and so on...). Any clarification or explanation regarding this method would be very welcome.
I am aware that the question is rather broad, but I am not looking for a clear and definitive solution. Instead, any suggestion or direction would be greatly appreciated.
 A: I'm not sure if I understand correctly the reasons why you ruled out PCA, but a possible approach would be to use a dimension reduction technique on each group of variables, maybe including their interaction $Z$ if it makes sense. Then, use the dimensions of each group as features in your regression model.
As you mention categorical variables with more than two values, instead of PCA I'd suggest to use multiple correspondence analysis as a dimension reduction method, as it is designed specifically to work with categorical data.
Another approach would be to just model interactions, without using dimension reduction at all. However, modeling all possible interactions doesn't seem to be a good idea (I mention that, as you say in a comment "There are many other ways to define a $Z$, and that's what I am looking for"). Anyway, with all possible interactions, your dimensionality issue would still be there. Keeping only the interactions and omitting the main effects is probably not appropriate to solve this dimensionality problem.
Edit following your comment: including all possible interactions in your model and applying stepwise regression on it (in order to keep only the significant interactions) would lead to the same problems associated to stepwise regression.
Unfortunately, as you mention, dimension reduction (MCA, PCA) could make your model lose a good part of its predictive power. In your place, I'd simply try to model interactions based on domain knowledge -but I guess this is a problem to you as your initial question is about not having to model these interactions "by hand". Of possible interest regarding automated model selection: Algorithms for automatic model selection.
