I have a large relation in which each tuple has an integer value corresponding to each column. Now I need to display these tuples in an order according the user specified priorities of each column(which obviously change according to the user). Miniature example: Consider this relation:
A user enters priorities as 8,9,5 and 4 for A,B,C and D respectively, I need to determine the order of the tuples matching best to user priorities. What I have thought of till now is applying filters in the sorted order of the provided user priorities and then displaying the results. I need help for a more accurate algorithm.
Best How To :
Might the answer be as simple as...? Obviously, this is not the answer, yet I am still in the dark, what the correct result might be...
Basically the question comes down to "Which metric is to the best taste of the user?".
While offering 2 metrics myself, anyone who has ideas can shorten their answers by giving a metric function. You can experiment with the code below for example at http://www.tryfsharp.org/Create
The first (
metric1 uses the scalar product). While the second value is small, the first value with nearly as high a priority gets (6,2,3,8) up in the rankings.
The second (
metric2) attempts to be value agnostic, using some ranking method (ranking as in robust estimators, baysean, ...) where a match in the position of the sorted tuple values relative to the positions in the sorted priority tuple is rewarded with a number which is 2^(priority position). This means, that a match in the rank for the highest priority can never be beaten by a lower priority position match. You still follow, right? :)
To clarify metric2 a bit more (and I am sure it can be improved - where are those google guys when you need them?!):
[3; 2; 4; 1] [2; 1; 3; 4] ([1; 5; 9; 2] [8; 9; 5; 4])
[4; 1; 3; 2] [2; 1; 3; 4] ([6; 2; 3; 8] [8; 9; 5; 4])
[4; 3; 2; 1] [2; 1; 3; 4] ([4; 4; 4; 4] [8; 9; 5; 4])
Here you see intermediate values for metric2 for all 3 4-tuples in the table. Rightmost you see the priority value tuple. Second from right, the input value tuple. The first two lists show the sorting indices (in descending order) for both the table tuple and the priority tuple.
Now... a good match would have the same sorting order as the priority tuple. (This metrics theory). So if the biggest value in the table tuple would be located where the highest priority in the priority tuple is located, this would be good. And for high priority positions in the priority tuple this is even better. If the second highest value in the table tuple is at the position of the second highest priority value in the priority tuple, this is also nice - but not as important as the first value on the highest priority...
To avoid that the ordering of the least "significant" values in the tuple according to the priority tuple win over the more "significant" ones, I added a priority specific value to the metrics.
If the first priority is matched, it gets the metric value 2^4 = 16. If the second matches it is 8, then 4,2,1. So even if the first match failed and all the others are matched, a tuple cannot beat a tuple where the first one is in the right spot.
For the researchers convenience, I added an empty
metric3 which can be used for finding better alternatives.
let ua,ub,uc,ud = (8,9,5,4)
let table = [ 1,5,9,2; 6,2,3,8; 4,4,4,4 ]
let metric1 (a,b,c,d) = a*ua + b * ub + c * uc + d * ud
let metric2 (a,b,c,d) =
let indices = [1;2;3;4]
let values = [a;b;c;d]
let indByValue =
List.zip indices values
|> List.sortBy (fun (i,v) -> v)
|> List.map (fun (i,v) -> i)
let prioIndByValue =
List.zip indices [ua;ub;uc;ud]
|> List.sortBy (fun (i,p) -> p)
|> List.map (fun (i,p) -> i)
//printfn "%A %A (%A %A)" indByValue prioIndByValue values [ua;ub;uc;ud]
let r,_ =
List.zip indByValue prioIndByValue
|> List.fold (fun (cnt,w) (x,y)-> if x = y then (cnt + (1 <<< w),w-1) else (cnt,w-1) ) (0,4)
let metric3 (a,b,c,d) =
// TODO: Write your favourite metric here ;)
let best1 = List.maxBy metric1 table
let sorted1 = List.sortBy metric1 table
let best2 = List.maxBy metric2 table
let sorted2 = List.sortBy metric2 table
let best3 = List.maxBy metric3 table
let sorted3 = List.sortBy metric3 table
//table |> List.iter (fun r -> printfn "%A" (metric2 r))