Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Excuse the ignorance here. My background is not mathematics. This is an IT problem that may have a mathematical solution:

I have a large amount of sets of variables. The variables belong to a distinct set of data (for example, each variable may be the age of a person in years, in which case, my potential range has about 100 values). Each set has an unspecified number of data points (for the sake of making things easier to understand, lets assume that each set is the ages of people in a restaurant table):

  • set 1: {1, 100, 2, 3}
  • set 2: {3, 4, 45,1 ,2 ,34, 65, 33, 59, 32}
  • set 3: {40}
  • etc. etc.

I need to identify common subsets within the data. So ideally I would like to look at a few millions of sets and determine that in 20% of these sets you can find the subset (30, 45, 50) for example. Which would then suggest that if you see a 50 year old and a 45 year old, then there is a good chance that a 30 year old will join them - or something similar)

Can anyone provide a few pointers?

After going over some of the comments:

@dls thanks for the link. I think that I found something relevant in the apriori algorithm. There is also (for the IT lot) useful ruby code at github and R code.

I have also posted the same question at CrossValidated. The responses and comments have been very helpful so please have a look there too.

share|cite|improve this question
You may want to look into affinity analysis: Or ask the people at Cross Validated: – dls Aug 31 '13 at 16:00
@Dimitris Whenever you say 'group', you probably mean 'set'. In mathematics a 'group' is something completly different. – Git Gud Aug 31 '13 at 16:10
You should change subgroup to subset. A subgroup is something different. – MyUserIsThis Aug 31 '13 at 16:15
From the affinity analysis page on Wikipedia, you may also want to read about association rule learning: – dls Aug 31 '13 at 16:20
I don't know what a map/reduce approach is. As for NP-completeness, that's a bit of a long story. I'm sure the definition has been given on this site many times before. You might have a look at or at any textbook on the theory of computation, or at the book by Garey and Johnson, or just type "NP-complete" into a search engine and see what comes up. This is worth doing --- it's an important concept. – Gerry Myerson Sep 1 '13 at 7:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.