What is the best way to prove / show that a dataset has all combinations of nominal values for a known group of features? For example, if attributes A and B can take on values from the set {low, med, high}, then the following dataset has all their combinations:

A      B
low    low
low    med
low    high
med    low
med    med
med    high
high   low
high   med
high   high

EDIT: I mean to show mathematically that this is the case.

  • $\begingroup$ how to define "prove/show", are you trying to ask an algorithm to search the data set that contains certain pattern? $\endgroup$ – Haitao Du Jul 21 '16 at 17:47
  • $\begingroup$ Fair enough. I was asked to perform association rule mining on such a dataset, which of course will not provide any reasonable results. I can tell that all combinations exist exactly once by looking at the data, and want to justify that mining association rules on such dataset makes no sense, but I can't find a way to formally show that the dataset has this structure. $\endgroup$ – Diogo Franco Jul 21 '16 at 17:54
  • $\begingroup$ How large is the data set? $\endgroup$ – Matthew Drury Jul 21 '16 at 17:55
  • $\begingroup$ A few thousand lines and 6 attributes. $\endgroup$ – Diogo Franco Jul 21 '16 at 18:05
  • 1
    $\begingroup$ Just tally the features. $\endgroup$ – whuber Jul 21 '16 at 18:46

You're wanting to show that given features $X_1,\ldots,X_k$, you have the Cartesian product $X_1\otimes \cdots \otimes X_k$.

What I would do is see how many levels $n_1$ of $X_1$ there are, how many levels of $n_2$ of $X_2$ there are, and so on. Then the cardinality of $X_1\otimes \cdots \otimes X_k$ should be $\prod_{i=1}^kn_i$. (For a proof of this, see Theorem 1.2.14 in Statistical Inference by Casella and Berger.) Then see if the number of rows in your data set is equal to $\prod_{i=1}^kn_i$. This method assumes that there are no duplicates in your data set.

If you are concerned about duplicates (i.e. you might have two observations in your data set with the exact same levels for all factors), then you will need to dedupe your data first to remove these duplicate observations.

| cite | improve this answer | |
  • $\begingroup$ Oh, thank you, I see. I can show that the number of rows is exactly the number that it should be if the dataset is indeed the cartesian product, by multiplying the cardinality of each feature. I had thought of this before posting, but concluded wrongly that it wasn't enough, because datasets can have that number of rows and not be the cartesian product. But of course, all of those must have duplicate records! $\endgroup$ – Diogo Franco Jul 21 '16 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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