2
$\begingroup$

I have a large dataset containing several objects. Each object has many attributes which is arranged in a time series. Is there a suggested method to find the top n "most interesting" attributes? The data contains many missing values so by "most interesting" I mean an attribute that has most of its values filled in as well as one that has some diversity in those values. For example, I'm not interested in the attributes that have all values filled in but have only 2 distinct values. Does this sound like an information theory problem? I'm not sure what I'm looking for here so any help would be appreciated. Thanks.

Edit/Clarification:
Thanks for the input so far.
By "missing values" I mean that right now they take on the value of "NaN"

"I'm not interested in the attributes that have all values filled in but have only 2 distinct values" - by this I mean, for example, if one attribute can take on any value between 0 and 255 but all the values are either 0 or 255 then I wish to ignore this attribute.

All the of the values were manually entered so I wouldn't consider it supervised/unsupervised.

$\endgroup$
3
  • $\begingroup$ "Unique" according to many dictionaries means occurring once only; in that sense, "distinct" is a much better word than "unique". $\endgroup$ – Nick Cox Jun 16 '15 at 16:40
  • $\begingroup$ @NickCox "Guessed?" I thought I nailed that with a sledgehammer...:) $\endgroup$ – Mike Hunter Jun 16 '15 at 17:02
  • $\begingroup$ Missing does turn out to mean "NaN". Thanks for the clarification. $\endgroup$ – Nick Cox Jun 16 '15 at 17:12
1
$\begingroup$

Good question! I like messy ones like this. May I ask for a clarification? When you write, "I'm not interested in the attributes that have all values filled in but have only 2 unique values..." can you elaborate a bit more about what this statement means? It's not clear to me.

I understand that you have many attributes with missing values. I'm assuming you don't have much stomach for imputing the missing values, a common statistical practice. Can you say whether or not this is a supervised vs unsupervised problem? In other words, do one, two or a few of these attributes qualify as "dependent variables" in the supervised, regression sense of the word?

To your point, this could be treated as an information-theoretic exercise but that's not the only approach. The thing that makes this messy are all of the missing values. Analysts invariable choose techniques that are in their theoretical and training "comfort zone." Information theorists trained in Kolmogorov Complexity will lean towards metrics such as entropy or MDL (minimum distance length), both of which are indicators of nonlinear, bivariate strength of association. There are many more: metrics based on reproducing kernel Hilbert spaces like distance correlations (Szekely), mutual information criterions (Reshefs), and so on.

I mention these as options for a couple of reasons: first, the standard multivariate statistical approaches to dimension reduction tend to be quite unforgiving wrt missing data. The default option for many of these techniques is "listwise deletion" which means that those units of observation with missing data get thrown out at the analysis. If you do have dependent variable(s), then the rankings based on the magnitude of the bivariate metrics mentioned above could be a good start towards attribute dimension reduction.

"Interestingness" is an information-theoretic metric developed, to the best of my knowledge, by Usama Fayyad in his 1996 book on data mining Advances in Knowledge Discovery and Data Mining. He had been asked to analyze data from scans of the observable sky done with the Hubble Telescope. First, he partitioned the "universe" into thousands of quadrants, calculated his "interestingness" metric for each quadrant, then ranked this metric from most to least. In the process, entirely new astronomical discoveries were uncovered. It's worth noting that Fayyad was also the first guy, back in the 80s when he was at the JPL, to train a machine to differentiate between a valley and a mountain, this time based on telemetric data from the Galileo space probe of Jupiter. This is "true" data mining at its best.

Since Fayyad's formulation, the metric has seen wider use and extensions. For instance, there's Huebner's 2009 paper DIVERSITY-BASED INTERESTINGNESS MEASURES FOR ASSOCIATION RULE MINING. I've seen other papers.

Even so, if you do have a PhD with deep training in 20th c multivariate statistical techniques, you are likely to choose one of the seemingly innumerable variable selection routines that are out there. One that a preponderance of statisticians like and prefer is Tibshirani's Lasso technique. It relies on L1 norms and has good properties in terms of regularizing the solution (not overfitting).

$\endgroup$
1
$\begingroup$

In this case, the regular discrete entropy of each variable might suffice for your purposes. If an attribute takes value i with probability $p_i$, then entropy is just $H(X) = -\sum_i p_i \log p_i$. If an attribute takes only a single value (all 0's), you get 0. If it takes just two values, then the maximum value will be 1 bit (using log base two). If it takes four values, the maximum possible value will be 2 bits. If it takes all possible values from 0 to 255 the maximum is 8 bits.

What will the "most interesting" variables look like for this measure? It will be the ones where each value is equally likely.

This is a "smooth" measure in the following sense. If you have an attribute that almost always takes just two values (0 and 255 in your example), but rarely takes other values, the score will still be near to one bit. In other words, rare events will not lead to "interestingness"/high entropy.

This measure can also be interpreted in terms of compression. What if you tried to compress this attribute, how many bits on average would be required? Well, if all possibilities are equally likely, 8 bits. If only two values ever occur, then only one bit is required.

$\endgroup$

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.