2

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.

Community
  • 1
Dimitris
  • 121
  • 3
  • You may want to look into affinity analysis: http://en.wikipedia.org/wiki/Affinity_analysis

    Or ask the people at Cross Validated: http://stats.stackexchange.com

     – 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
  • 1
    From the affinity analysis page on Wikipedia, you may also want to read about association rule learning: http://en.wikipedia.org/wiki/Association_rule_learning – dls Aug 31 '13 at 16:20
  • Identifying common subsets among a million sets? I bet there's no computationally feasible way to do that --- it smells like an NP-complete problem to me. – Gerry Myerson Sep 01 '13 at 07:07
  • @Gerry Myerson can you provide some more information about what an NP-complete problem is? Also, can this be broken down via a map / reduce approach? – Dimitris Sep 01 '13 at 07:28
  • 1
    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 http://math.stackexchange.com/tags/np-complete/ 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 01 '13 at 07:34
  • map / reduce is a programming approach to solving computationally expensive problems. An algorithm that can be implemented this way (in this case the APriori algorithm) can be processed by a map reduce service (like Amazon's). Have a look at http://en.wikipedia.org/wiki/MapReduce . – Dimitris Sep 01 '13 at 08:14

0 Answers0