Method to test compatibility between variable values

Question

I have a problem with my current research that I have come across repeatedly over my research career in various different fields. It goes like this.

You are trying to characterise instances of some particular category that you study. This can be trees, buildings, chemical substances or English sentences. You determine a few discrete variables that you want to measure for each particular instance. For example, if we are talking about buildings, you may decide to focus on the main construction material (stone, wood, brick, etc.), use (residence, office space, public institution, etc.), construction decade (1940s, 1950s, 1960s, etc.), height bracket (under 5 m, between 5 and 100 m, between 100 and 300 m, over 300 m), plus others. Each individual instance that you observe (each building in our example) can be characterised by giving it a value for each variable. For example, building A may be made of wood, used for residence, constructed in the 1960s, and having a height in the 5-100 m bracket.

In real-world situations, you may have many variables (ten or twenty is not uncommon), and each variable may be able to take multiple values (many take 5-10 values; some may take up to 40 or 50). This creates a "solution space" of as many dimensions as variables, and as many individual points as distinct combinations of values. In my current research, I am working with 6 variables, some of which may take up to 12 different values, adding up to a solution space having over 15.000 points.

Now, I want to verify if every possible combination of values is possible. In other words, I want to check if there might be instances of the things I'm studying at every point in the solution space. In the example above, there aren't any buildings constructed in the 1880s and having a height of over 300 m. I have a suspicion that many areas in the solution space are similarly "impossible" areas, in the sense that there are combinations of values that are incompatible amongst each other and can't be found in the real world.

Of course, I can create a multi-dimensional matrix with thousands of cells, and start evaluating the possibility of finding an instance for each one. But this would take ages and is difficult to visualise and process without making mistakes. So, my question is, is there any particular technique to tackle a problem like this?

Answer 1

I'm just spitballing here, and I'm assuming the data is discrete (which would require a preliminary, perhaps arbitrary, chopping of continuous data into intervals). Let $O$ be the set of all observations. My first step would be to sort the variables into ascending size of their domains (breaking ties whimsically). Now partion $O$ into the disjoint union $O_1 \cup \dots \cup O_n$ where $1,\dots,n$ indexes the domain of the first variable. If $O_i=\emptyset$ for any $i$, then obviously any point in solution space using the $i$-th value of the first variable is impossible.

Now partition each nonempty $O_i$ into a disjoint union $O_{i1}\cup\dots\cup O_{im}$ where $1,\dots,m$ indexes the domain of the second variable. Again, any empty set signals a combination of values for the first two variables that never occurs. Repeat until you have gone through all variables. At that point, the list of empty sets translates to a list of unobserved ("impossible"?) combinations.

The initial sort is not necessary conceptually. I'm just hoping that it will allow early "pruning" of the unions and help keep down the number of sets. The number of sets will grow, although the sum of their cardinalities will remain constant.

What you end up with is a list of unobserved combinations. If you need some sort of compact characterization (e.g., you don't encounter trees with heights in categories 3 through 6 that have seed pods of types 2 or 3 in climates 1 through 5), you might want to look at something like clustering or perhaps some sort of decision tree/decision forest model (no pun intended) to aggregate the unobserved combinations.