How can I do classification with categorical data which is not fixed?

Question

I have a classification problem with both categorical and numerical data. The problem I'm facing is that my categorical data is not fixed, that means that the new candidate whose label I want to predict may have a new category which was not observed beforehand.

For example, if my categorical data was sex, the only possible labels would be female, male and other, no matter what. However, my categorical variable is city so it could happen that the person I am trying to predict has a new city that my classifier has never seen.

I am wondering if there is a way to do the classification in these terms or if I should do the training again considering this new categorical data.

Answer 1

It is very good question; in fact this problem has been around for a while and I have not yet found the perfect solution. Yet more than happy to share my experience:

• Avoid one-hot-encode as much as possible (contrary to what was suggested above). The reasoning is that it won't work. A model with one-hot-encode features only works when all those sublevels had been existed in the training data. The model won't be able to do prediction, unless somehow it is manually tweaked. If you search you will find many people ran into this issue when splitting their data into train/test, and faced the issue of some sublevels of a particular feature were not present in the training split and subsequently failed to do prediction on the test. Said aside, if you have very high cardinal features (maybe like your city with let's say 200 city names), this will increase the dimensionality of your data unnecessarily! If for some reasons you may need to do one-hot-encoding, just keep these in mind.

• Use Other Encoding Methods. Maybe try learning more about other methods that are robust to this issue, at least for the time being like target-based coding, hashing (see some references below). If you are with Python there is a nice package offer mant encoding options. You may be surprised to see that other simple methods often works just fine.

• Retrain your model. Theoretically when learning your train/set should have had the same distribution (mostly this is thought of as target distribution, but can be true about variables as well). Now with new items comes into play, your test (unseen) data distribution has changed. Then it is best to retrain the model again so that those new cities will be accounted for.

• Put Newly Added Subcategories (and least frequent ones) to Others. While earlier point is true theoretically, it is very likely that the test distribution (of that particular category) won't change that drastically in most of the cases e.g. very few items goes top of the categories in the training set. Perhaps like in your case, you may have 100 cities in the city feature, and just very few new ones comes over time. What I would consider would be looking at the let's X-quantile of that particular category, and put the least frequent ones into Others subcategory. Assuming your newly added data point is only little, it will very much goes into the Others group. You will certainly lose a level of granularity by doing this one, but once again the point of learning is that not only your model learn the training data, but most importantly to be able to generalize very well on unseen data and if those new added categories are very data points, grouping them altogether into the Others group won't hurt.

• Other Recent Not-Yet Mature Solutions like Cat2Vec (borrowed from Word2Vec from NLP) or Similarity Encoding. These are very recent, check the paper for the former and its github and an example (based on Word2Vec) in Kaggle, and this paper for the latter and its implementation. The idea of the former is to convert categories to vectors. As much as I have to say it really make sense to work, but I have no experience using it. The latter, so-called dirty_cat, looks quite promising and easy to use. Whether it is robust to having unseen cardinal category in your test data is not clear to me!

P.S.: I would like to add that the idea of city to a geographical location given in the first comment is really nice and it is actually not complicated as they are many Python API e.g. by Google or HERE that allows you to do that. But it is noted that this is just a way to engineer new features and certainly not to be replaced by the city feature itself.

Interesting references to check first, second, third, fourth (no particular order!)

All above-mentioned points are practical solutions rather concretely theoretically correct, and surely subject to further discussions. And I am more than happy to learn more.

Answer 2

The simplest thing to do (which is usually a good place to start) is just one-hot-encode your cities where every city becomes a single feature and has values of either 1 (the person is from that city) or 0 (not from that city). If a new city appears in a test set that isn't present in the training set that person will just have 0's for all the cities in the training set. This might seem weird but, if that city isn't in the training set, then there should be no weight placed a person being from that city.

The next step would be something along the lines of what Mohammad Athar suggested and get some idea of geographic proximity to other cities in your training set. That is going to be much more complicated so I will let someone else comment on it.

Answer 3

You should checkout Vowpal Wabbit, which handles very nicely new features using a hashing trick and adaptive learning rates.

Not only will it not crash when new features appear (at train or test time), it will also start updating its weights on it. On top of that its wicked fast. It only implements variants of the linear model though, so you are restricted on that side. A very powerful tool to know about