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?

  • $\begingroup$ 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? $\endgroup$
    – Danica
    Dec 9, 2015 at 17:52
  • $\begingroup$ 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. $\endgroup$
    – seanv507
    Dec 9, 2015 at 19:38
  • $\begingroup$ @seanv507 thank you very much. I found OneHotEncoder from scikit, which has an option sparse. Is there something similar for R? $\endgroup$
    – vladkkkkk
    Dec 10, 2015 at 9:51
  • 2
    $\begingroup$ 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 $\endgroup$
    – seanv507
    Dec 10, 2015 at 10:14

1 Answer 1

  1. Sparse data structures conserve RAM.
  2. Algorithms which respect sparsity will have speedup essentially proportional to the amount of sparsity.
  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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.