Алгоритм вероятности: поиск вероятного правильного элемента в списке (например, Джон, Джон, Джон)

Question

Возьмем, к примеру, список (L):
Джон, Джон, Джон, Джон, Джон, Джон

Мы должны предположить, что один пункт должен быть правильным (например, Джон в данном случае), и дать вероятность, что он правильный. Первая (и хорошая!) Попытка: MostFrequentItem (L) .Count / L.Count (например, 4/5 или 80% вероятности )

Но рассмотрим случаи:
Джон, Джон, Джон, Джонни
Джон, Джон, Джон, Джон

Я хочу рассмотреть вероятность того, что правильный предмет, будь то Джон, выше в первом списке! Я знаю, что должен посчитать SecondMostFrequent Item и сравнить их.

Есть идеи? Это действительно разрушает мой мозг!
Спасибо, Andrew

Answer 1

Как чрезвычайно простое решение, по сравнению с более правильными, но сложными решениями, описанными выше, вы можете взять подсчеты для каждого варианта, возвести их в квадрат и использовать их для вычисления весов. Итак:

[John, John, Jon, Jonny]

даст Джону вес 4, а двум другим - 1, при вероятности 66% Джон прав.

[John, John, Jon, Jon]

даст весам 4 для Джона и Джона, поэтому вероятность Джона составляет всего 50%.

Answer 2

Может быть Редактировать расстояние ? Просто направление к решению, хотя ...

Answer 3

Прежде всего, я подозреваю, что вы используете термины непоследовательно. Это поможет, если вы будете использовать технические термины, такие как «вероятность» и «вероятность», со строгой корректностью.

вероятность вещи позволяет нам рассуждать от параметра до результата . Например, предположим, что у нас есть нечестная монета, которая с вероятностью 60% выпадет в голову. 60% - это параметр. Исходя из этого, мы можем предположить, что вероятность получить две головы подряд составляет 60% * 60% = 36%.

вероятность вещи позволяет нам рассуждать от исхода до параметра . То есть мы подбрасываем пару одинаковых монет тысячу раз и обнаруживаем, что мы получаем две головы в 36% случаев. Мы можем вычислить «вероятность вероятности появления голов составляет 60% с учетом того, что 36% пар были двумя головами».

Теперь возникает разумный вопрос: «Насколько мы можем быть уверены, что мы получили правильный параметр с учетом результата?» Если вы переворачиваете пары монет миллион раз и получаете двойные головы на 36%, кажется правдоподобным, что мы можем быть очень уверены, что параметр для одной монеты составляет 60%. Вероятность высока. Если мы перевернем пары монет три раза и получим двойные головы в 33% случаев, у нас будет очень мало уверенности в том, что параметр для одной монеты, получающей головы, близок к 60%. Это может быть 50% или 40%, и нам просто везет раз в три. Вероятность низкая.

Все это преамбула к простой просьбе прояснить вопрос. У вас есть результат: куча результатов. Вы хотите сделать оценку параметров, которые дали такой результат? Вы хотите получить доверительный интервал для этой оценки? Что именно вы собираетесь здесь?

Answer 4

Я думаю, вам понадобится какая-то система подсчета очков.

Недостаточно просто указать разные токены:

[John, Johen, Jon, Jhon, Johnn]

С вашим алгоритмом здесь нет явного победителя, в то время как наиболее вероятное имя - «Джон», остальные - всего 1 на расстоянии Дамерау-Левенштейна .

Итак, я бы сделал двухэтапный процесс:

1. Подсчитайте вхождения каждого слова
2. Для каждого слова добавьте «бонус» для каждого слова, обратно пропорционального их расстоянию

Для бонуса я бы предложил следующую формулу:

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

Обратите внимание, что вы не должны применять это сначала для (John, Johen), а затем для (Johen, John).

Пример: * * тысяча двадцать-пять

# 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

Я не уверен, что это идеально, и я понятия не имею, как преобразовать это в некоторый процент ... но я думаю, что это дает довольно точное представление (наиболее вероятное). Возможно, бонус должен быть уменьшен (какой фактор?), Но проверьте этот вырожденный случай:

[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

Как вы можете видеть, он не может быть напрямую конвертирован в какой-то процент: процент правильного результата в 99,8%: «Джон» кажется низким здесь!

Примечание: Эффективно реализовать расстояние сложно, спасибо Peter Norvig за его решение Python!

Answer 5

Только что у меня в голове, что если вы сравните% случаев с%, если все предметы имели одинаковое количество вхождений

В вашем примере выше
Джон, Джон, Джон, Джонни
50% Джон
25% Джон
25% Джонни
33,3% нормально? (Я придумываю слово, потому что не знаю, как это назвать. 3 предмета: 100% / 3)
Оценка Джона = 50% - 33,3% = 16,7%

Джон, Джон, Джон, Джон
50% Джон
50% Джон
50% Нормальный (2 предмета, 100% / 2)
Оценка Джона = 50% - 50% = 0%

Если бы у вас было [Джон, Джон, Джон, Джон, Джон], тогда оценка Джона была бы 60% -50% = 10%, что ниже, чем в первом случае, но выше, чем во втором (надеюсь, это желаемый результат, в противном случае вам нужно будет уточнить, какими должны быть желаемые результаты)

В вашем первом случае [Джон, Джон, Джон, Джон, Джон] вы получите 80% -50% = 30%
Для [Джон, Джон, Джон, Джон, Джон, Джонни] вы получите 66,6% -33,3% = 33,3%
Это может или не может быть то, что вы хотите.

Если вышеупомянутое может повлиять на большее, то если бы у вас был Джон * 97 + Джон + Джонни + Джонни, это дало бы вам 97% -25% = 72%, но Джон * 99 + Джон дал бы вам только оценку 99-50% = 49%

Вам нужно выяснить, как вы хотите справиться с вырожденным случаем, когда все они одинаковы, иначе вы получите 0% за то, что, вероятно, не то, что вы хотите.

РЕДАКТИРОВАТЬ (хорошо, я сделал много правок, но это не просто примеры: p)
Чтобы нормализовать результаты, возьмите оценку, рассчитанную выше, делите на предел максимально возможной оценки, учитывая количество различных значений. (Хорошо, это звучит намного сложнее, чем нужно, пример времени)

Пример:
[Джон, Джон, Джон, Джонни] 50% - 33,3% = 16,7%. Это предыдущая оценка, но с 3 пунктами верхний предел вашей оценки будет 100% -33,3% = 66,6%, поэтому, если мы примем это во внимание, мы получим 16,7 / 66,6 = 25%

[Джон, Джон, Джон, Джон] дает (50-50) / 50 = 0%
[Джон, Джон, Джон, Джон, Джон] дает (60-50) / 50 = 20%
[Джон, Джон, Джон, Джон, Джон] дает (80-50) / 50 = 60%
[Джон, Джон, Джон, Джон, Джон, Джонни] дает (66,6-33,3) / (66,6) = 50%
[Джон * 97, Джон, Джонни, Джонни] дает (97-25) / 75 = 96%
[Джон * 99, Джон] дает (99-50) / 50 = 98%

Answer 6

Я не уверен, почему вам нужно рассчитать второй по частоте элемент.В последнем примере не могли бы вы просто посмотреть (количество подходящих записей) / (общее количество записей) и сказать, что это правильно с вероятностью 4/8?Разве это не достаточный показатель?Тогда вы бы также сказали, что у Джона вероятность 3/8 правильности, а у Джонни 1/8?

Почему этого недостаточно для ваших целей?