Какой алгоритм применить, что бы передавать что одно лучше другого и в итоге получить таблицу?
Мне нужно вывести таблицу упорядоченную от лучших к худшим.
Нужно передавать в алгоритм, что одно лучше другого, а он в свою очередь должен сортировать эту таблицу соответствующим образом.
Вся загвоздка в том, что один может передать, что А лучше Б, а другой наоборот. И это нужно учитывать.
Плюс каких то сравнений может быть много
(например А сравнивали и с Б и с В и с Г),
а каких то мало
(например Г сравнили только с А).
Нам нужно себъективные мнения привести к объективному среднему числу.
Есть куча объектов которые сравнивают между собой, есть куча голосующих, которые выбирают что из двух нравится больше.. и из этого нужно собрать таблицу.
Просто кол-во проголосовавших не подходит, т.к. за А может быть только 1 голос но он говорит о том, что А лучше всех остальных.
Перепробовал уже много всего разного.
Никак не могу найти оптимальный подход.
То есть дана таблица попарных различий, запись в которой указывает, что первый объект должен располагаться выше второго. Требуется построить общую таблицу, в которой все объекты будут расположены в таком порядке, чтобы правила, заданные в исходной таблице не нарушались.
"Вся загвоздка в том, что один может передать, что А лучше Б, а другой наоборот. И это нужно учитывать."
Ну и как учитывать? Формулу-то приведите.
А если противоречий нет, то это я бы назвал линейным списком. Вводим уровни иерархии. Только будет неоднозначность. Например, А лучше Б, Б лучше В. Тогда А на первом уровне, Б на втором, В на третьем. Добавляем: А лучше Д. Получается, что Д может оказаться и на втором, и на третьем уровне.
Александр Скуснов: "Получается, что Д может оказаться и на втором, и на третьем уровне." --именно так. Формулы нет. Именно поэтому я и задал вопрос. Что бы попробовать все таки отыскать оптимальное решение.
Mizhgunich: Формулу я предлагал для первого варианта: А>Б и Б>A.
То, что Д может оказаться на разных уровнях это просто неоднозначность.
(да, список называется просто связным, а не линейным). В теории графов есть способ упорядочивания (естественно, если нет противоречий).
Теорема о невозможности доказывает, что полностью справедливую систему построить невозможно. Нужно, учитывая предметную область, рассмотреть различные варианты обобщения коллективных оценок и выбрать наиболее удобную или подходящую.
Неплохая статья на хабре с некоторыми способами ранжирования.
Вам нужно вот это "одно лучше" выразить в числовом эквивалиенте, причем абсолютном, а не относительно других.
Например, не "машина А быстрее машины Б", а "у машины А максимальная скорость 100, а у машины Б максимальная скорость - 300".
Если критериев сравнения несколько - давать средневзвешенную оценку.
Например, если у машины параметры скорость и маневренность, а вам нужно дать общую оценку, то нужно четко определить, какой вклад в общую оценку делает каждый параметр (математически, формулой. Например - веса), выносить на основе формулы общую оценку и уже сортировать по ней.
GavriKos: ну это если не выявится, что аудитория чаще отдаёт предпочтение такому-то параметру (другое дело - и работать это будет только на схожей аудитории) :-)
Александр Пожарский аа, типо намутить обучающуюся систему, которая исходя из какого то голосования (допустим) будет подкручивать эти коэффициенты? Ну ИМХО это немного другая задача все равно - как намутить коэффициенты, а не как отсортировать )
Александр Пожарский "Нужно передавать в алгоритм, что одно лучше другого, а он в свою очередь должен сортировать эту таблицу соответствующим образом." - я это воспринял как "у нас уже есть инфа о том что А лучше Б, как это применить ко все выборке". А теги - от лукавого. Но может вы и правы, сложно сказать.
"Нужно передавать в алгоритм, что одно лучше другого."
А не передавать ли какой-то чёткий параметр? Или такого нет (ну или задача как раз -выделить его)?
"Вся загвоздка в том, что один может передать, что А лучше Б, а другой наоборот"
Разделить оценки по категориям (читай "лучше в связи с тем-то") или же (если есть явный перевес) - отбросить одну из сторон, нет?
з.ы. кстати, если явно перевеса нет - возможно, удастся разбить юзеров на N кластеров по их голосованиям, обучить N оценивающих сеток и после - классифицировать юзера и давать ему вывод соответсвующей сети. Но тут я уже не подскажу какой-либо конкретики.
Mizhgunich: вообще говоря - а какие у нас входные параметры? Как я понимаю - кучка числовых (или сводимых к ним) и результаты голосования для каждого пользователя, верно?
Александр Пожарский: есть куча объектов которые сравнивают, есть куча голосующих, которые выбирают что из двух нравится больше.. и из этого нужно собрать таблицу.
Просто кол-во проголосовавших не подходит, т.к. за А может быть только 1 голос но он говорит о том, что А лучше всех остальных.
Mizhgunich: "за А может быть только 1 голос но он говорит о том, что А лучше всех остальных." - можно разъяснить механизм? Не было других голосований с A? Или, возможно - голос отдан юзером с большим весом? Или я что-то упустил?
Mizhgunich: Вообще - по единственному голосу, думаю, не получится сделать вывод (не известны критерии оценки, примененные конкретным пользователем и аудиторий). Разве что мы выведем критерии оценки предварительно и проверим этот голос (например - мы выяснили, что аудитория отдает предпочтение параметру A, если B находится в определенных пределах. И если B лучше C, а A оказалось лучше B (по выведенному критерию) - вероятно A лучше C). Не?
Александр Пожарский: ну вот примерно так у меня сейчас идет сортировка. Строится граф и потом считается.. только граф непозволяет выбрать А лучше Б и Б лучше А одновременно. А такое может быть, учитывая, что будут разные пользователи.
Mizhgunich: Тогда, думаю - как я уже писал выше - нужно кластеризовать пользователей и построить для каждого кластера свою систему оценки (в принципе - код будет один, только обучение на разных данных). Ну а после - классифицировать новых пользователей и давать им оценки от системы, рассчитанной на определенный кластер.
Александр Пожарский: не вариант, т.к. нужно строить таблицу и для пользователей, которые еще не голосовали. И делить вцелом не вариант, т.к. сегодня пользователь проголосовал так, а завтра может иначе. Все это субъективно.
Mizhgunich: Так ведь голосование явно будет зависеть от вкусов пользователя - а пока он не принял участие в чём-либо - мы не сможем их определить, не? Но сможем отнести в какой-либо дефолтный кластер, если такой обнаружится.
Mizhgunich: "сегодня пользователь проголосовал так, а завтра может иначе" - клонишь к тому, что голосования не лишены погрешности? Вроде такое вполне реально учесть.
Если же ты о том, что мы не учтём некий критерий или же вкусы юзера изменятся - не думаю, что в общем случае мы можем заранее это предсказать - только среагировать на такое изменение.
Александр Пожарский: несовсем. Есть критерии по которым выбирается лучший, но анализировать это машиной не представляется возможным, необходимо именно человеческое участие. Причем определить в числовом значении эти критерии так же невозможно. Можно только это тут лучше а это тут лучше.
Средний
Простой