Feature selection in high dimension

Suppose I have a (labeled) date, where features have many categories. For example, one can take kaggle's Wallmart dataset https://www.kaggle.com/c/walmart-recruiting-trip-type-classification/data. Usually I make one-hot-encoding and then PCA in order to reduce space dimensionality. However, when number of categories is too high, this seems infeasible. Can anyone suggest please how to deal with such data?

To be more precise, suppose we are given a labeled (0/1) dataset of ~250k observations with 5-10 categorical features each of which has ~10k categories. If I use one hot encoding for all features, the design matrix will have ~2.5 billions of entries, which cannot be allocated in RAM. Although, I can use sparse representation, I do not know whether it is possible to process it in such form.

For example, for kNN approach I can provide a simple metric $d(x,y)=\sum \{x \neq y\}$, which solves the issue. However, how can I apply logistic regression, svm or some other approach here?

• This completely depends on what type of learning model you're using. Which ones do you care about? Also, by "this seems infeasible" are you worried about computation, needing too many dimensions to accurately represent the original space, something else? – djs Dec 9 '15 at 17:52
• most machine learning implementations use sparse representations (think bag of words applications) so eg scikit-learn in python has svm and logistic regression with sparse representations. – seanv507 Dec 9 '15 at 19:38
• @seanv507 thank you very much. I found OneHotEncoder from scikit, which has an option sparse. Is there something similar for R? – nmerci Dec 10 '15 at 9:51
• basically no... you would be better off using scikitlearn. statisticians frown on using such high cardinality categories - they would suggest reencoding in terms of relevant features (eg age/gender etc) rather than the phonebook listing approach of BOW. I know you can use glmnet, but you will have to generate the sparse matrix yourself. see r-bloggers.com/genetic-data-large-matrices-and-glmnet – seanv507 Dec 10 '15 at 10:14

3. Using PCA to rank-reduce a sparse data set is as simple as writing a routine to do power iteration and Gram-Schmidt (because you only want the $k$ basis vectors corresponding to the largest $k$ eigenvalues, not all of them, you need only do computations to estimate $k$ orthogonal vectors).