isn't it an application of association rule mining. http://en.wikipedia.org/wiki/Association_rule just that ARM will mostly result multiple solution depending on your data. Its up to you to decide a strategy for breaking ties.
On Aug 15, 1:19 am, Geoffrey Summerhayes <[EMAIL PROTECTED]> wrote: > On Aug 14, 4:25 am, sfl <[EMAIL PROTECTED]> wrote: > > > Hi, > > > Let's suppose we search into a table for N parameters, starting from a > > maximized key. > > If we do not find anything we start to generalize the key by take off > > one parameter. > > We do this until we find something. > > Stop. This is a poor specification, give this to 5 different > programmers and expect 5 programs that give different > results. > > > > > Let's try with an example, 3 parameters: > > > Database table > > MyTable > > code | state | color | size > > > rule1 california blue large > > rule2 california yellow medium > > rule3 california yellow - > > rule4 california - small > > rule5 - - small > > rule6 - yellow medium > > > Now suppose our key K is composed from K(california, red, small) > > We have to find the rule by search into MyTable. > > > step1: search MyTable for (california,red,small) > > we do not find anything > > > step2: search MyTable for K(california,red, null) ( we have reduced > > the key). > > Why? If you get an answer set that matches [california,red] you > end up ignoring the answers to [california,small] and [small,red] > both of which match using the same number of criteria but return > a different set of rules. What makes the [california,red] answer set > deserve special treatment? > > > > > we do not find anything > > > step3: use the K(null,red,small), we do not find anything again, step > > over > > > step4: use the K(california, null, small) we finally find rule4, stop! > > > We got to the end, but let's now suppose this row in our table: > > > rule7 - red small > > > step3 would find the rule7 and step4 would find rule4, which is right? > > If parameters has no weight, the algorithm returns 2 solution. > > > So, suppose I give a grid of combination, ordered. > > > ord state color size > > 1 x x x > > 2 x x - > > 3 x - x > > 4 - x x > > 5 - x - > > 6 x - - > > 7 - - x > > 8 - - - > > > I search for K(x,x,x), then K(x,x,null) etc until I find a rule. > > Complexity is O(2^n) where n= number of parameters > > #(state,color,size)=3 > > If it was O(2^n) then adding 500 rules to that database > wouldn't change anything, right? > > > So, to keep it short, how would you solve this problem? > > Probably by going through the rules in one pass, keeping > the best matching set. > > > Which is the class of this problem? n,p,np,np-c,etc... > > If n is the total number of elements considered, that is > the number of rules multiplied by the number of parameters, > it's linear. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
