У меня есть список друзей. Затем я получаю несколько списков одних и тех же друзей, но с другим рейтингом. Есть ли алгоритм проверки, какой список наиболее близок к исходному ранжированию?алгоритм ранговой корреляции
Благодаря
Это, вероятно, зависит от того, что ваша мера «расстояния» между двумя ранжировании является.
Например, если мы определим
dist(R1, R2) = Sum abs(position of i in R1 - position of i in R2), over all i
, то вы можете сохранить позиции каждой i в первом рейтинге в массиве
т.е.
pos[Peter] = 3
средства что Peter появляется в качестве третьего друга в вашем рейтинг.
Ближайший рейтинг можно найти в линейном времени, вычислив сумму, указанную выше, используя pos.
Это хорошее решение. Однако это не говорит мне о важности расстояния. Скажем, у меня есть рейтинговый список с 200 друзьями, которые отключены на 1 место, а с другой стороны, у меня есть рейтинговый список, в котором рейтинг одного друга отключен на 200 мест. Расстояние будет таким же. Тем не менее, второй рейтинг-список намного больше, чем первый рейтинговый список. – Mike
Вы можете оштрафовать большие расхождения, взяв квадрат или куб различий в позиции. – abeln
Думаю, я могу. благодаря – Mike
Я думаю, вы должны сравнить расстояния ранга между ними, но с использованием весов. Например, если пользователь занял 1-е место на 10-м месте, это большая разница, но если пользователь занял 101-е место на 110-м месте, это не большое изменение. Таким образом, вы должны ставить более высокие коэффициенты на различия пользователей с более высоким рейтингом.
Я думаю, вы могли бы сделать это с помощью алгоритма [инверсии массива] (http://stackoverflow.com/questions/337664/counting-inversions-in-an-array), который работает в O (n log n). В основном, вы берете свой первоначальный рейтинг и назначаете каждому элементу идентификатор в порядке возрастания, а затем выполняете поиск в «разных рейтингах» для каждого из ваших n элементов, чтобы назначать им соответствующие идентификаторы из первоначального рейтинга (вы должны иметь возможность чтобы сделать это эффективно), а затем примените описанный выше алгоритм к идентификаторам, присвоенным «другому ранжированию». –