# How can I quantify unordered categorical data with infinite possible outcomes?

I'm trying to model a very simple supervised machine learning model. Let's say that it's a logistic classification problem.

I must take into account some qualitative variables (categories) with a very, very large number of different possible outcomes, and I don't know how to express them.

For instance, let's say they can be geographical locations (strictly speaking, they're not infinite, but close to), or different moments in a year with a precision of an hour (so there are 24*365 possible outcomes), or even the color of a pixel expressed with an RGB code (16 million outcomes). You get it.

This is unordered data, so I can't say that that particular location is 1, that other one is 2, etc. Otherwise, my weights would treat the outcome with a higher label number as more important on the dependent variable than the other ones.

The only way I know to model such a scenario is using binary variables: but that would mean to have an infinite number of possible inputs. Not only: it's very redundant, because if one of these variables is 1, all the other ones must be 0 (one-hot combinations).

There must be a way to express quantitatively and unorderly a category variable with a close-to-infinite number of possible outcomes.

I'm quite certain that I'm missing something very basilar; unfortunately, my academic background is somewhat fragmented...

• All three of your examples are not like nominal categories -- the first is spatial (2-D), second is ordered in time, and the third can be treated as 3-D spatial. You shouldn't ignore such structure. For example, in each case you'd expect that measurements of something on a pair of very nearby locations/times might tend to be more alike than far apart locations/times. You should generally avoid throwing out information like that – Glen_b Jul 11 '16 at 0:51

Your data is finite, correct? So, let's not assume infinity. Rather, given different information, assume that some categories or levels will be new relative to the original or previous data. That said, if we can label the data challenge you've described as "massively categorical," then some solutions do suggest themselves. You don't mention it but one of the biggest challenges to this type of analysis has been that with so many possible categorical values or levels, software doesn't exist (on the planet) able to fit all of that information into memory at one time. This is the historic problem with traditional, frequentist, statistical models and solutions -- inversion of a massive cross-products matrix.

The first approach to modeling massively categorical data is hierarchical and Bayesian and introduced in a Marketing Science paper about 15 years ago by Steenburgh and Ainslie. When this paper was written, there was little understanding about possible workarounds to the memory limitations mentioned above. Titled Massively Categorical Variables: Revealing the Information in Zip Codes, an ungated copy can be found here ... http://www.people.hbs.edu/tsteenburgh/articles/Steenburgh_Ainslie_and_Engebretson_(winter_2003).pdf
Their approach isn't exploratory, i.e., it presumes a pre-existing model, is quite computationally expensive and, with truly massive data (e.g., the 16 million pixels you described), is likely never to converge even on a parallel platform.

A second approach is also Bayesian. David Dunson, at Duke, is probably the leading exponent of tensor approaches to modeling massive contingency tables, among other things. His papers with their attendant descriptions are much better introductions than anything I have to offer or can say. Here's one such paper as well as a link to his Google Scholar page. He's very active and prolific. https://scholar.google.com/citations?user=PxPxCv8AAAAJ&hl=en&oi=ao https://arxiv.org/pdf/1306.1598.pdf

A third workaround is rooted in iterative machine-learning algorithms, is exploratory and neither presumes nor requires a pre-existing model. Variously titled, e.g., "divide and conquer" (D&C) or "bags of little jacknifes" (BLJs) algorithms, these methods, to a large degree, can be viewed as extensions of Breiman's random forest approach to CART. Breiman did his work in the late 90s on a single CPU when "big data" meant a few gigs, several thousand features and several thousand bootstrapped trees evaluated as an ensemble. Today's extensions are several: first, "massive" typically means terabytes of data containing millions, tens of millions or even hundreds of millions of features evaluated on a massively parallel, multi-core platform. Next, where Breiman wrote only about trees, any multivariate engine can and is being substituted. Finally, with this kind of computational power, millions of mini-models can be run and evaluated in a few hours. Given that, you could plug in one of the GLMs and obtain an ensemble answer to your massively categorical features. Here is an introductory, ungated copy of one review of these algorithms ... http://www.math.chalmers.se/Stat/Grundutb/GU/MSA220/S16/ReviewBigDataR.pdf

I'm trying very hard to be agnostic here and avoid the "wars of religion" between Frequentists and Bayesians. Regardless, until these ML workarounds were developed, frequentists were pretty much screwed when it came to modeling truly massive data. With these workarounds, any arbitrage Bayesians enjoyed in handling massively categorical information has been eliminated.

I wouldn't treat any of your examples (time with 1-hour resolution, geographic location, or RGB color) as categorical. To do so would be to throw away what we know about how the values are related to each other: for example, noon on January 1st is closer to 1:00 PM on January 1st than it is to noon on January 2nd. So do treat them quantitatively, but rather than labeling the values arbitrarily, use a system of coordinates that make sense for the data type. Locations can be represented as latitude and longitude, time can be represented as the number of hours since the beginning of the year, and color can be represented as red, green, and blue components, each 0 to 255. There are many options as to how to coordinatize a given datatype; how you should choose depends on the data you have and the problem you want to solve. You can find detailed treatments of how to represent time and space in books on time series and spatial data analysis, respectively.

• Treating time as a continuous variable is definitely a possibility. This treatment would introduce a simple linear and deterministic trend function. Regarding color, I suppose it could be treated continuously as a spectral dimension. However, I don't agree that treating lat-long as a continuous feature makes sense in a raw form. Transforming it into a networked distance function is a possibility as long as there were origins or base locations against which such a function could be calibrated. – DJohnson Jul 11 '16 at 0:24