Ранжирование списка "количество — значимость" и задача о голосовании?
Здравствуйте Хабровчане.
Возникла интереснейшая проблема ранжирования результатов поиска.
Допустим есть абстрактная поисковая система по некоторым объектам, которая выдает результат в виде следующего списка соответствий «Количество совпадений — Средняя ошибка совпадений».
На практике возникают следующие ситуации: Ситуация 1:
Документ 1: 19-0,32
Документ 2: 1-0,59
Документ 3: 2-0,69 Для этого списка решение о найденном объекте принять легко — найден документ 1
А что делать в следующей ситуации: Ситуация 2:
Документ 1: 19-0,32
Документ 2: 18-0,30
Документ 3: 2-0,69
Тут сомнения между документами с номерами 1 и 2 — и в результат поиска можно с уверенностью выдать два документа.
или вот в такой: Ситуация 3:
Документ 1: 2-0,1
Документ 2: 18-0,30
Документ 3: 2-0,69
Тут сомнения так же между документами с номерами 1 и 2, но логичнее в поиск выдать документ 2 — так как совпадений больше. Но просто по количеству совпадений в тоже время нельзя ранжировать — так как может быть ситуация 4:
Ситуация 4:
Документ 1: 2-0,1
Документ 2: 18-0,30
Документ 3: 100-0,99
А средняя ошибка 0,99 при 100 совпадениях — это практически отсутствие этих самых совпадений.
Вопрос: Так как выдача алгоритма поиска может состоять из огромного по размеру списка — как его проранжировать и выдать пользователю? Наверное, следует соединить параметры: количество совпадений и точность в один параметр. Как это сделать — есть ли «best practices» на этот счет?
Количество ошибочных совпадений в документе равно произведению количества совпадений (N) на коэффициент ошибки (e): Ne = N*e
Тогда вероятность неверного выбора документа будет, кажется: (N-Ne)/N = Pe
Выбираем max Pe.
В любом случае нужно подобрать такую функцию, которая будет минимизировать вероятность неверного выбора документов. Эта задача решается в различных классификаторах.
Эту же задачу можно рассматривать как задачу построения классификатора, определяющего отношение документов к одному из двух классов — ошибочного и релевантного. Однако мало входных данных.
Возможно, что отношение количества совпадений к объему документа также имеет значение. (3 ошибки в слове GUI это не тоже самое, что 3 ошибки в слове representative). :)
«отношение количества совпадений к объему документа» — намекает также, что стоит покопать в сторону коэффициента Танимото, который зависит от мощности сравниваемых множеств. (Это может быть полезно, если рассматривать объем документа как мощность множества слов в него входящих).
Сложный
