I'm having trouble researching this, or even writing this question, because I'm not sure what this is called and I'm not familiar with a lot of the terminology. The best I can do is an example.

Let's say my data set consists of the tags on every question on Stack Overflow. So I have:

  • 14,000,000 samples.
  • Each sample consists of up to 5 unique items, there are 50,000 possible items.

I'm looking for an analysis technique I can use to find the correlation of the presence of items in a group (tags on questions in this example), so that at the end I can make statements such as:

  • Tag A hardly ever appears with tag B.
  • When tag C is present, tag D is almost always also present, but not the other way around.
  • Tags E and F virtually always appear together.
  • Tags X and Y appear completely independent of eachother.
  • Etc.

And it would be really great if I could also make statements involving more than 2 items at a time, if such an algorithm exists, e.g.:

  • Tags G, H, and I almost always appear together.
  • When tag J and K are present, L is almost never present.
  • When tag M is present, tags N, O, and P are also almost always present.
  • Etc.

I do not need to predict the structure of data outside my sample set. My sample set represents the entire population, I only need to analyze it. Not sure if this is important.

Another maybe important point is, for the statements above, I need to be able to discover facts like that. That is, I wouldn't be asking "How likely is L to be present when J and K are present" up front, because I don't suspect any relation between J, K, L, or any other tags ahead of time. If that makes sense.

I'm not really sure what to look for, I just need a kick in the right direction.

I keep finding things about covariance matrices, although I don't fully understand how to apply that yet. In particular I guess I could represent each sample as a 50,000-dimensional vector with a $1$ for each item that was present and $0$ otherwise, although I'm not sure how a finite set of values fits in here. I guess in that case I'd get some sort of 50,000x50,000 matrix out.

The other thing is I'm not sure how to do this "efficiently" (not lightning fast, but this can't take an entire day and does have to fit in a reasonable amount of memory) for tens of millions of samples and tens of thousands of dimensions.

What technique(s) can I use for this and, are there any algorithms I can look into to do it efficiently for large inputs?

I hope this is clear. Like I said, I'm all ready to go do the rest of the research here, I just need a few starting hints. (Also, while I'm not entirely familiar with a lot of the terminology and concepts, I'm not entirely unfamiliar either, so answers do not need to be at ELI5 level. I can figure it out but I need a starting point.)

  • $\begingroup$ Not entirely sure what tags to use. $\endgroup$ – Jason C May 25 '17 at 22:31
  • $\begingroup$ Hmm, arxiv.org/pdf/1410.7404.pdf looks potentially promising, at a glance, I'm reading up on it now and trying to understand it. Not sure... $\endgroup$ – Jason C May 25 '17 at 23:24

Some thoughts: First, you should have a look at tagoverflow (somebody have already thought about the problem). They probably used some form of multidimensional scaling (MDS) (tag ). But you seem to have some other ideas, specifically, you ask about relationships among three tags at a time, and covariance cannot answer that kind of questions.

Another obvious idea is some form of clustering, but among with MDS that searches for global solutions, and you ask for "discovering facts about relationships among tags", for example inclusion (or near inclusion) and others. Going out on a tangent, maybe you should look into market basket analysis or formal concept analysis.


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.