Probability Algorithm: Finding the likely correct item in the list (e.g. John, John, John)
Take for example list (L):
John, John, John, John
We have to assume that one element has to be correct (like John in this case) and give the probability that it is correct. First try (and good!): MostFrequentItem (L) .Count / L.Count (e.g. 4/5 or 80% chance )
But consider the cases:
John, John, John, Johnny
John, John, John, John
I want to consider the likelihood that the correct item will become John higher on the first list! I know that I have to read the SecondMostFrequent Items and compare them.
Any ideas? This is really destroying my brain!
Thanks Andrew
a source to share
As an extremely simple solution, compared to the more correct but complex solutions above, you can take the count of each variation, count the number, and use them to calculate the weights. So:
[John, John, Jon, Jonny]
would give John a weight of 4 and the other two give a weight of 1, for a 66% chance that John is right.
[John, John, Jon, Jon]
would give 4 weights to both John and John, so the probability of John is only 50%.
a source to share
Off the top of my head, what if you compare% occurrences versus% if all elements had equal number of occurrences
In your example above
John, John, John, Johnny
50% John
25% John
25% Johnny
33.3% Normal? (I'm forming a word because I don't know what to call it. 3 items: 100% / 3)
John score = 50% - 33.3% = 16.7%
John, John, John, John
50% John
50% John
50% Normal (2 pcs, 100% / 2)
John score = 50% - 50% = 0%
If you had [John, John, John, John, John], then John's score would be 60% -50% = 10%, which is lower than the first, but higher than the second (hopefully the desired result, otherwise you need will clarify what the desired results should be)
In your first case [John, John, John, John, Jon] you will get 80% -50% = 30%
For [John, John, John, John, Jon, Jonny] you will get 66.6% -33.3% = 33.3%
This is may or may not be what you want.
In case the above might make a bigger difference, if you have John * 97 + John + Johnny + Johnny it will give you 97% -25% = 72%, but John * 99 + John will only give you 99-50% = 49%
You need to figure out how you want to handle the degenerate case when they are all the same, otherwise you will get a 0% score for what is probably not what you want.
EDIT (ok, I made a lot of changes, but these are not just examples: p)
To normalize the results, take the score calculated above, divide by the maximum possible score given the number of different values. (Okay, this sounds a lot harder than it takes, like time)
Example:
[John, John, John, Johnny] 50% - 33.3% = 16.7%. If the previous score, but with 3 points, the upper limit of your score would be 100% -33.3% = 66.6%, so when we factor that in we would have 16.7 / 66.6 = 25%
[John, John, John, John] gives (50-50) / 50 = 0%
[John, John, John, John, John] gives (60-50) / 50 = 20%
[John, John, John, John , John] give (80-50) / 50 = 60%
[John, John, John, John, John, Johnny) give (66.6-33.3) / (66.6) = 50%
[John * 97, John, Johnny, Johnny ] gives (97-25) / 75 = 96%
[John * 99, John] gives (99-50) / 50 = 98%
a source to share
I think you need some kind of scoring system.
Single identification of different tokens is insufficient:
[John, Johen, Jon, Jhon, Johnn]
With your algorithm, there is no clear winner here, while the most likely name is "John", the others are just 1 in the Damerau-Levenshtein distance.
So, I would do a two step process:
- Count the occurrences of each word
- For each word, add a "bonus" for each other word, inversely proportional to their distance
For a bonus, I would suggest the following formula:
lhs = 'John'
rhs = 'Johen'
d = distance(lhs,rhs)
D = max( len(lhs), len(rhs) ) # Maximum distance possible
tmp = score[lhs]
score[lhs] += (1-d/D)*score[rhs]
score[rhs] += (1-d/D)*tmp
Note that you do not have to apply this first for (John, Johen)
and then for (Johen, John)
.
Example:
# 1. The occurences
John => 1
Johen => 1
Jon => 1
Jhon => 1
Johnn => 1
# 2. After executing it for John
John => 4.1 = 1 + 0.80 + 0.75 + 0.75 + 0.80
Johen => 1.8 = (1) + 0.80
Jon => 1.75 = (1) + 0.75
Jhon => 1.75 = (1) + 0.75
Johnn => 1.8 = (1) + 0.80
# 3. After executing it for Johen (not recounting John :p)
John => 4.1 = (1 + 0.80 + 0.75 + 0.75 + 0.80)
Johen => 3.8 = (1 + 0.80) + 0.60 + 0.60 + 0.80
Jon => 2.35 = (1 + 0.75) + 0.60
Jhon => 2.35 = (1 + 0.75) + 0.60
Johnn => 2.6 = (1 + 0.80) + 0.80
# 4. After executing it for Jon (not recounting John and Johen)
John => 4.1 = (1 + 0.80 + 0.75 + 0.75 + 0.80)
Johen => 3.8 = (1 + 0.80 + 0.60 + 0.60 + 0.80)
Jon => 3.7 = (1 + 0.75 + 0.60) + 0.75 + 0.60
Jhon => 3.1 = (1 + 0.75 + 0.60) + 0.75
Johnn => 3.2 = (1 + 0.80 + 0.80) + 0.60
# 5. After executing it for Jhon(not recounting John, Johen and Jon)
John => 4.1 = (1 + 0.80 + 0.75 + 0.75 + 0.80)
Johen => 3.8 = (1 + 0.80 + 0.60 + 0.60 + 0.80)
Jon => 3.7 = (1 + 0.75 + 0.60 + 0.75 + 0.60)
Jhon => 3.7 = (1 + 0.75 + 0.60 + 0.75) + 0.60
Johnn => 3.8 = (1 + 0.80 + 0.80 + 0.60) + 0.60
I'm not sure if this is perfect, and I don't know how to turn this into a percentage ... but I think it gives a pretty accurate idea (most likely). Perhaps the bonus should be reduced (what factor?) But check this degenerate case:
[John*99, Jon]
# 1. Occurences
John => 99
Jon => 1
# 2. Applying bonus for John
John => 99.8 = (99) + 0.80
Jon => 80.2 = (1) + 0.80*99
As you can see, it cannot be directly converted to any percentages: 99.8% of the correct result being “John” seems low here!
Note. Using distance efficiently is difficult, reliable by Peter Norvig for a Python solution!
a source to share
First, I suspect you are using terms inconsistently. It helps if you use technical terms such as "probability" and "probability" with strict correctness.
The likelihood of a thing allows us to reason from parameter to result. For example, suppose we have an unfair coin that is 60% more likely to come to mind. The parameter is 60%. From this we can assume that the probability of getting two heads in a row is 60% * 60% = 36%.
The likelihood of a thing allows us to reason from result to parameter. That is, we flip a pair of identical coins a thousand times and find that we get two heads 36% of the time. We can calculate "the probability of a headshot is 60%, given that 36% of couples were two heads."
Now a reasonable question: "How sure can we be that we have derived the correct parameter, given the result?" If you flip pairs of coins a million times and get 36% of double heads, it seems plausible that we can be very confident that the parameter for one coin is 60%. The probability is high. If we flip pairs of coins three times and get double heads 33% of the time, we have very little confidence that the parameter for getting one coin head is close to 60%. It could be 50% or 40%, and we just got lucky once every three. The probability is low.
All this is a preamble to the simple asking you to clarify the issue. You have a result: a bunch of results. Do you want to evaluate the parameters that gave this result? Do you want to get a confidence interval for this estimate? What exactly are you going to here?
a source to share
I'm not sure why you need to calculate the second most used item. In the last example, couldn't you just look at (number of records matched) / (total records) and say that this is correct with a 4/8 probability? Isn't that a sufficient metric? Would you also say that John has a 3/8 chance of being correct and Johnny has a 1/8 chance?
Why is this not enough for your purposes?
a source to share