1
$\begingroup$

This has been originally asked at math.stackexchange where it was suggested that I try Cross Validated.

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, 2 ,1 ,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?


Some more information which should make this easier to understand:

Again, thanks to @whuber for the guidance.

  1. The values are not numbers. I think that the best description I can provide is something like product names. Therefore there is no error in their measurement and there is a finite number of them which is known beforehand.
  2. There is a possibility to associate the values to each other, i.e. 'A' may be closely related to 'B' where as 'A' may be completely unrelated to 'C'. In any case, I may not be able to quantify the relationship, so for now I have to assume that there is no connection between the values.
$\endgroup$
  • $\begingroup$ Let's first establish the sense in which you mean "subset": after all, the value 2 has been repeated in your 'set 2' and that is unusual--it suggests you might be looking for tuples or sequences rather than subsets. Your notation "(...)" also is not a standard set-descriptor notation. Could you clarify your meaning? A small worked example could help convey your intentions. $\endgroup$ – whuber Aug 31 '13 at 16:42
  • $\begingroup$ @whuber I have cleaned this up. Thanks for the feedback. These are not tuples, so I have removed the duplicate values $\endgroup$ – Dimitris Aug 31 '13 at 16:50
  • 1
    $\begingroup$ Thanks. It can be useful to know more about the data. In particular, (a) are the values actually ages? If not, what are they? Are there are limited number of possible values? (b) Are the values measured without error? If not, what kinds of error or variation is possible? (c) Is there some sense of values that are "close" to one another, so that for instance if there are many occurrences of {30,45,50} and many of {31,45,50} you might want to make note of this, or would these two subsets be as different from each other as they are from {2,4,91}, say? $\endgroup$ – whuber Aug 31 '13 at 16:56
  • 1
    $\begingroup$ From your description and example it sounds like you might be looking for something like Association rule learning. Does this seem right? $\endgroup$ – alto Aug 31 '13 at 17:29
2
$\begingroup$

What you describe is frequent itemsets problem, which is finding subsets of items that appear in many of the given sets. Since the problem is NP-hard (that is, no known polynomial time algorithm for solving it) there are a variety of heuristic approaches. One of the well-known such algorithms is called APriori. I suggest you to have a look at it.

$\endgroup$
  • 1
    $\begingroup$ I have had a look at the APriori algorithm and I think that this is very close to what I am after. If you happen to know more about it, then please provide some extra information. I am also interested in the technical implementation of the solution, so if for example you have used R then again it would be useful to hear your experience. Thanks for your input @Tevfik Aytekin $\endgroup$ – Dimitris Aug 31 '13 at 21:13
  • 1
    $\begingroup$ The arules package offers such an implementation. There's also a JSS paper which provides more details. $\endgroup$ – chl Aug 31 '13 at 21:29
  • 1
    $\begingroup$ Hi Dimitris, APriori is a very classic algorithm and there are many good tutorials around the web (or in data mining textbooks) you can easily find. I just wanted to point out that your problem is a very well studied problem in data mining and there are numerous ways for attacking it. You can check the book link $\endgroup$ – Sanyo Mn Aug 31 '13 at 21:32

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.