Hi Everyone,

New to the forum, glad to be here. Have this question that I could use some help with.

Let's say we have a list of lists of objects, which are selected from a predetermined set (we can also look at each list of objects as a transaction, like they have in the Apriori algorithm). Each object can only appear in each list once.

What needs to be done, is to create a coefficient which describes the compatibility of each variable in the predetermined set to each list of objects. This should be done by the frequency of this object in other lists containing objects similar to the ones on the list for which the coefficient is made for.

The output result for each coefficient should be a value between 0 and 1, with 1 meaning the object should definitely be part of the list (or already in it) and 0 means there was no indication of compatibility.

This simple example might help explain the problem:
Let's say we have the following lists:
1: {1, 2, 3, 4}
2: {1, 2}
3: {1, 2, 3}
4: {1}

And we want to know how likely is it that 1, 2, 3 or 4 will be in list #4; 1 would be the highest (1), since it's in the list; 2 would be second-highest since it's in all other lists containing 1; 3 would be the next since it's only in list #1 and list #3 and 4 would be the last since it's only in list #1.

The algorithm should probably also take a lot into account (like - what if another list has only part of the list for which the coefficient is made, etc.).

Read about the Apriori algorithm, but I don't think I can use it - as it answers a different question. Since this seems like a rather general problem, I bet there is somewhere a good solution for it I can utilise - but I could use some direction.

Thanks in advanced.

Hi,

Welcome to the forum.

One possibility would be to use association rules.

If we consider the first three transactions:

1: {1, 2, 3, 4}
2: {1, 2}
3: {1, 2, 3}

You would have the following association rules:

1 -> 2 with a support (frequency) of 3 transactions and a confidence of 100 % because in every sequence where 1 appears, 2 also appears.
1 --> 3 with a support of 2 transactions and a confidence of 66 % because 1 appears with 3 in two cases out of 3 transactions where 1 appears.
1 --> 4 with a support of 1 transaction and a confidence of 33 % because 1 appears with 4 in 1 transactions out of 3 transactions where 1 appears.
...
and many others...

So if you have a new transaction:

4: {1}

You could use the association rule to evaluate wich item is more likely between 2, 3 and 4 by looking at the confidence of the rules.

This would work.

Moreover, instead of using the confidence, you could use a measure called lift which may perform better to evaluate associations between items.


Another solution if you don't want to use association rules is to scan the database and count which items appears with 1 and then choose the one that appears the most often. In this case you don't need to use association rule.

Best,

Philippe



Edited 1 time(s). Last edit at 03/11/2014 06:30AM by webmasterphilfv.

Hi Philippe,

Thanks for the quick answer, however - I still have a little trouble with something.

Probably the example I gave wasn't the best one; let's say that the new group was {1, 5} - using Apriori there will not be confidence for any of the other values (2, 3, 4) since 5 is introduced in the new group (which could happen all the time in my dataset). However, even in this scenario I will still want to have a certain level of confidence because the 1 is still present. Is there an algorithm or a measurement that will give me that?

Thanks again

If in the new group you have {1 5} and there is no rule {1 5} --> ... then you could just check if there are rules by removing one or more item from {1, 5}.

For example, if the new group is {1, 5}, then you could first check if there is a rule with {1 5} in the left part.

If there is none, then you could try removing 1 and 5. So you would check for rules like this {1} --> ... or a rule {5} --> ....

Then your program would find that there are some rules 1--> 3 and 1 --> 2 .

This is just some idea. You could certainly make it more complicated then this.

Best,

Thanks again my friend.

An expert I've consulted with offered me to check into collaborative filtering. The problem with that approach is that it would provide items which would be recommended to add to the new group (which might be enough), but won't provide to coefficients to quantify the relevance of each item. What is your take on that?

From what I know about collaborative filtering, you have some users and some objects. Then the users have to provide ratings for the objects so that the system can recommend objects. Recommendation for a user are based on users who have rated other objects similarly.

If you have this kind of information about ratings, etc. then it may be applicable.

You could always set the rating to 0 and 1 only to apply CF. But then maybe it is not necessary to use CF at all.

I'm not an expert on CF, though.



Edited 3 time(s). Last edit at 03/12/2014 05:27AM by webmasterphilfv.