Как обеспечить наиболее релевантные результаты с помощью взвешенной сортировки по нескольким факторам

Мне нужно предоставить взвешенную сортировку по 2+ факторам, упорядоченную по «релевантности». Однако факторы не полностью изолированы, поскольку я хочу, чтобы один или несколько факторов влияли на «срочность» (вес) других.

Пример: за добавленный контент (статьи) можно проголосовать за или против и, таким образом, получить рейтинг; у них есть дата публикации, и они также помечены категориями. Пользователи пишут статьи и могут голосовать, а также могут иметь или не иметь какой-либо рейтинг (эксперт и т. д.). Вероятно, похоже на StackOverflow, верно?

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

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

Мой вопрос: каков наилучший алгоритм для сортировки по нескольким факторам? Это может быть дубликат этот вопрос, но меня интересует общий алгоритм для любого количества факторов (более разумное ожидание - 2-4 фактора), предпочтительно "полностью автоматическая функция, которую мне не нужно настраивать или требовать ввода пользователем, и я не могу анализировать линейную алгебру и дурацкие собственные векторы.


Возможности, которые я нашел до сих пор:

Примечание. S — это "оценка сортировки"

  1. "Линейно взвешенный" – используйте функцию, например: S = (w1 * F1) + (w2 * F2) + (w3 * F3), где wx – произвольно присвоенные веса, а _4  – значения факторов. Вы также хотели бы нормализовать F (т.е. Fx_n = Fx / Fmax). Я думаю, что это как Поиск Lucene работает.
  2. "Взвешенные по основанию N" – это больше похоже на группировку, чем на взвешивание, это просто линейное взвешивание, при котором веса увеличиваются кратно десятичной системе (принцип аналогичен специфичность селектора CSS), так что более важно факторы значительно выше: S = 1000 * F1 + 100 * F2 + 10 * F3 ....
  3. Оценочная истинная ценность (ETV) — это, очевидно, то, что Google Analytics представила в своих отчетах, где значение одного фактора влияет (веса) на другой фактор, следствием чего является сортировка по более "статистически значимым" ценности. Ссылка объясняет это довольно хорошо, так что вот просто уравнение: S = (F2 / F2_max * F1) + ((1 - (F2 / F2_max)) * F1_avg), где F1 — «более важный» фактор («показатель отказов» в статье), а F2 — фактор «изменяющий значимость» («посещения» в статье). ).
  4. Байесовская оценка — очень похоже на ETV, так IMDb рассчитывает свой рейтинг. См. это сообщение StackOverflow для объяснения; уравнение: S = (F2 / (F2+F2_lim)) * F1 + (F2_lim / (F2+F2_lim)) × F1_avg, где Fx такие же, как #3, а F2_lim — это минимальный пороговый предел для фактора «значительности» (т. е. любое значение меньше X не должно учитываться).

Варианты № 3 или № 4 выглядят многообещающе, поскольку вам не нужно выбирать произвольную схему взвешивания, как в вариантах № 1 и № 2, но проблема заключается в том, как сделать это для более чем двух факторов?

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


person drzaus    schedule 06.01.2012    source источник
comment
Просто для ясности, какой фактор вы бы изменили веса каких других факторов в вашем примере? Является ли один из них намного более важным, чем другие, или вы просто хотите избежать ручной установки весов?   -  person gankoji    schedule 29.12.2014
comment
@gankoji, честно говоря, не помню (2+ года назад); Вероятно, я просто хотел избежать установки весов вручную, поскольку каждый раз, когда мы меняем свое мнение о важности, нам придется развертывать код, а также в первую очередь выбирать правильные веса.   -  person drzaus    schedule 29.12.2014
comment
Извините, я понял, что это был пост двухлетней давности после комментария. Я собирался предложить вам использовать то, что на жаргоне оптимизации называется «компромиссным решением». По сути, вы выбираете абсолютную идеальную «точку» в своем пространстве решений (афиша с самым высоким рейтингом, самая новая дата и т. д.), а затем ваша оценка будет обратным евклидову расстоянию от этой точки. то есть S = 1/(sqrt((rank - rank_ideal)^2 + (age - age_ideal)^2 ... (xn - xn_ideal)^2); В любом случае, надеюсь, вы поняли это.   -  person gankoji    schedule 30.12.2014
comment
@gankoji не беспокойтесь; вы должны опубликовать это предложение в качестве ответа, чтобы его было легче найти   -  person drzaus    schedule 30.12.2014
comment
Для линейно-взвешенного алгоритма веса должны в сумме равняться 1? Что произойдет, если у меня будет что-то вроде S = (f1 * .80) + (f2 * .80)?   -  person 425nesp    schedule 24.03.2019
comment
@ 425nesp Интернет взрывается, и вы получаете что-то вроде редизайна SO для первоапрельских шуток (комментарии Comic Sans !!!) ... но, скорее всего, это просто произвольно завысит ваше окончательное значение, что может не иметь значения, если это просто для сортировки.   -  person drzaus    schedule 01.04.2019


Ответы (3)


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

По сути, вы рассматриваете каждый свой критерий как координату (после нормализации, конечно). Основываясь на своем суждении, вы выбираете абсолютную оптимальную точку, т.е. в этом случае автор с самым высоким рейтингом, самая новая статья и т. д. После того, как вы выберете оптимальное решение, каждое другое «решение» оценивается на основе его удаленности от этого оптимального. Примерная формула будет обратной евклидову расстоянию для оценки каждой статьи: S = 1/(sqrt((rank - rank_ideal)^2 + (age - age_ideal)^2 + ... + (xn - xn_ideal)^2 )).

Это рассматривает все критерии как равные, так что имейте это в виду.

person gankoji    schedule 30.12.2014
comment
не будет ли это делением на ноль, если попадется точно такое же совпадение? - person Gokigooooks; 07.11.2017
comment
Да, если у вас неуникальный набор, возможно деление на ноль. Это тривиально обрабатывается в коде (сначала вычислить делитель, проверить на малость, при необходимости выбросить ошибку). Тем не менее, в этом случае использования неуникальность а) не упоминалась как ограничение и б) кажется маловероятной, учитывая тип набора данных и количество измерений. - person gankoji; 07.12.2017
comment
Извините за беспокойство, сэр, но у меня есть еще один вопрос! что, если значения каждого критерия имеют очень большую разницу, например, критерий № 1 находится в диапазоне от 1 до 30, а критерий № 2 — в диапазоне 1000+? Критерий № 2 будет сильно нагружен, верно? как я могу это нормализовать? - person Gokigooooks; 07.12.2017
comment
Разделите каждый критерий/измерение на максимально возможное для этого критерия. Это нормализует каждый критерий до 1. - person gankoji; 14.12.2017

Рассмотрим цепочку весов. Например. у вас есть 3 фактора: X, Y и Z. Вы можете рассчитать ETVyz как W = (Z/Zmax * Y) + (1 - Z/Zmax) * Yavg для каждой записи, а затем рассчитать ETVxw как S = (W/Wmax * X) + (1 - W/Wmax) * Xavg. Вы можете связать больше факторов аналогичным образом.

person well-wisher    schedule 20.03.2012
comment
но вы не можете нормализовать W (W против Wmax) в функции для ETVxw, потому что это уже результат внутренних нормализованных факторов - person drzaus; 19.04.2012

Решение, кратко указанное @gankoji, представляет собой упрощение метода TOPSIS.

В TOPSIS компромиссное решение можно рассматривать как выбор решения с кратчайшим евклидовым расстоянием от идеального решения и самым дальним евклидовым расстоянием от отрицательного идеального решения.

Этот класс проблем подпадает под термин MCDM — принятие решений по множеству критериев.

Пакеты Python scikit-criteria и mcdm предоставляют реализации наиболее популярных методов. Документы пакета ссылаются на соответствующие документы по алгоритму.

person dre-hh    schedule 01.09.2020