ранжирование на основе предпочтений пользователя

Я пытаюсь придумать алгоритм для следующей задачи.

Имеется набор из N объектов с M различными вариациями каждого объекта. Цель состоит в том, чтобы найти лучший вариант для каждого объекта на основе отзывов разных пользователей.

В конце пользователи будут помещены в категорию, чтобы определить, какая категория предпочитает какой вариант.

Требуется, чтобы не более двух вариантов объекта располагались рядом.

Проблема в том, что если M велико, количество возможных комбинаций становится слишком большим, и пользователь может потерять интерес и потенциально исказить результаты.

Алгоритм/оценку Elo можно использовать, как только я узнаю порядок выбора от пользователя, как описано в этом посте Алгоритм ранжирования на основе сравнения

Вопрос:

Существует ли алгоритм, который может уменьшить количество возможных комбинаций, представленных пользователю, и при этом получить правильный порядок?

пример: 7 различных видов фруктов. Каждый фрукт доступен в 5 различных формах. Пользователи дают свой рейтинг от 1 до 5 для каждого фрукта в зависимости от размера, который они предпочитают. Это означает, что для каждого фрукта пользователь может выбрать не более 10 комбинаций (поскольку размеры разные, нет смысла представлять как {1,1}). Как бы я уменьшил "10 комбинаций"?


person Varun Dave    schedule 14.09.2012    source источник


Ответы (1)


Если предпочтения пользователя всегда согласуются с общим порядком, и вы можете изменить сравнения, чтобы учесть результаты сделанных до сих пор сравнений, вам просто нужен эффективный алгоритм сортировки. Для 5 элементов кажется, что вам нужно минимум 7 сравнений - см. Сортировка 5 элементов с минимальным сравнением элементов. Вы также можете посмотреть на http://en.wikipedia.org/wiki/Sorting_network.

В общем, когда вы пытаетесь разработать какой-то план эксперимента, вы часто обнаружите, что случайные сравнения, хотя и не оптимальные, не слишком далеки от наилучшего возможного ответа.

person mcdowella    schedule 14.09.2012
comment
Я не совсем понимаю, что вы подразумеваете под полным порядком. Объясните пожалуйста? - person Varun Dave; 14.09.2012
comment
Если пользователь предпочитает A вместо B, B вместо C и C перед A, то умный алгоритм сортировки может сделать неправильный вывод из первых двух предпочтений, что пользователь предпочитает A вместо C. Это звучит странно, но может произойти по множеству причин. - для забавного см. en.wikipedia.org/wiki/Nontransitive_dice. - person mcdowella; 14.09.2012