Рекомендательные системы позволяют на основании выставленных пользователями оценок объектам прогнозировать значения оценок и осуществлять автоматический выбор объектов, которые могут заинтересовать пользователя. В последнее время разработано большое количество различных рекомендательных систем, однако формальной постановки задач, решаемых такими системами, нет. В работе рассмотрены три задачи, которые могут быть решены методами коллаборативной фильтрации и показано, как постановка задач зависит от спектра шкалы оценок и понятия близости оценок, выставленных разными пользователями.
Чем больше совпадений между оценками двух пользователей рекомендательной системы, тем больше вероятность того, что и остальные оценки у этих пользователей совпадают. Можно выбрать операцию усреднения, позволяющую по оценкам объекта, сделанным множеством пользователей, восстановить оценку этого же объекта для Труды 14-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» — RCDL-2012, Переславль-Залесский, Россия, 15-18 октября 2012 г.
Поскольку объекты оцениваются в порядковой шкале, вид операции усреднения зависит от спектра шкалы, а также от способа определения совпадений оценок пользователей. Действительно, совпадения оценок могут быть рассчитаны по значению оценки, попаданию в определенные семантические страты, совпадению порядков, построенных по множеству оценок и пр. Таким образом, использование одних и тех же предположений не приводит к однозначности поставленной задачи. А значит, рекомендации, полученные решением различных задач, не могут быть оценены одними и теми же показателями эффективности. Более того, в рамках некоторого показателя эффективности результаты работы различных рекомендательных систем могут оказаться несравнимыми. Среди разработчиков рекомендательных систем существует понимание этого факта, поэтому для измерения эффективности работы рекомендательных систем введен [2] ряд различных показателей (Табл. 1). Аббревиатуры показателей эффективности будут расшифрованы ниже. Такое разнообразие показателей показывает общее состояние разработок в этой области, когда на основе немногочисленных признанных достижений работают параллельно много независимых групп, создающих свою терминологию, методы верификации и проверки полученных результатов.
Цель работы – дать формальную постановку для задач, решаемых с использованием коллаборативного подхода, рассмотреть возможные критерии, экстремум которых соответствует максимальной эффективности рекомендательных систем, исследовать возможности решения многокритериальных задач в этой области.
Работа проводилась при финансовой поддержке Министерства образования и науки Российской Федерации. 2 Формальные постановки задач
Пусть задана шкала оценок. Если спектр оценок содержит достаточно много возможных значений (учитывая, что оценка всегда дискретна), то невозможно выделить семантически каждую оценку. precision positive prediction value recall (recall rate), rtu positive rate, sensitivity, hitrate coverage negative prediction value specificity accuracy F-measure (F score) false discovery rate false positive rare fall-out точность (точность, усредненная по пользователям системы имеет обозначение map.) полнота точность отрицательного прогноза специфичность аккуратность F мера (мера Ван Ризбергена) Поэтому оценки объединяются в семантические страты. По результатам оценок можно построить отношение порядка на множестве оцененных объектов. Таким образом, есть три возможности указать на совпадение оценок двух пользователей: по совпадению или незначительной разности значений оценки, по совпадению страт, в которые попадают эти оценки, по совпадению упорядоченных множеств объектов. В соответствии с каждой из этих возможностей, можно выделить три задачи рекомендательной системы. 2.1 Задача прогноза оценки объекта пользователем
Обозначим: ri – результат работы рекомендательной системы: оценка в принятой шкале, сгенерированная системой в ходе i-го обращения к ней (вне зависимости от пользователя и объекта). n – число обращений к системе (объем выборки). vi – соответствующая i-ому обращению к системе собственная оценка пользователя, данная им объекту; vi не известна алгоритму и может быть использована в ходе испытаний за счет выделения контрольного множества оценок.
Предполагается, что величины vi не зависят от ri, они постоянны во времени (эти предположения могут быть сняты при уточнении модели пользователя).
<1> Задачей рекомендательной системы является расчет значений ri, максимально близких к 1 - -error =-error +acc; acc = rcl + (1-)spc α-error величинам vi, при заданном множестве пар (пользователь, объект), доля которых известны vi.
Для любого фиксированного n результат работы рекомендательной системы: вектор R=(r1, r2, …, rn) представляет собой точку в пространстве Mn, где M – множество (спектр) оценок, допустимых в используемой шкале. Этому же пространству принадлежит точка V=(v1, v2, … , vn). Формальная постановка задачи <1> n где d – метрика, выбранная на пространстве М . Если на пространстве Мn выбрана норма ||V||, например, из класса lp, то соответствующее этой норме расстояние (1) (2) может служить критерием эффективности для задачи (1). Нормируем расстояние d(R,V), чтобы результат не зависел от объема выборки n, получим:
Отметим, что в такой постановке не имеет значения знак разности между vi и ri , а также величина оценки. Выбор параметра p осуществляется из соображений значимости больших отклонений по сравнению с малыми. 2.2 Задача определения страты, в которую попадает оценка
Разделим принятую в данной рекомендательной системе шкалу на две страты: P – положительные оценки и N – отрицательные оценки.
<2> Тогда работа рекомендательной системы представляет собой проверку гипотезы H0:viP.
Так же, как и для любого процесса проверки гипотезы, результат работы можно свести (табл. 2) Таблица 2 Возможные результаты прогноза riP riN viP положительный прогноз верен ошибка 2 рода ( - ошибка) viN ошибка 1 рода ( - ошибка) отрицательный прогноз верен Обозначим: tp – число опытов, в которых положительный прогноз оказался верен, tn – число опытов в которых отрицательный прогноз оказался верен, fp – число опытов, в которых положительный прогноз оказался ошибочным (число опытов в котороых наблюдалась ошибка первого рода), fn – число опытов, в которых отрицательный прогноз оказался ошибочным (число опытов, в которых наблюдалась ошибка второго рода).
Сравнивая величины tp, tn, fp, fn (tp+tn+fp+fn=n), можно получить различные критерии для формализации задачи <2> (табл. 3).
Отметим, что эти критерии могут быть противоречивыми: уменьшение уровня значимости (α-error) возможно только за счет снижения мощности критерия проверки гипотезы (1 – -error). Если в качестве критериев деятельности рекомендательной системы выбраны несколько таких противоречивых критериев, то настройки системы могут обеспечить увеличение эффективности по одному из критериев только за счет ухудшения эффективности по другому, таким образом составляя множество Парето. Такое множество для рекомендательных систем строится, как правило либо для показателей prc(rcl), либо для rcl(fpr).
Для свертки критериев могут использоваться различные функции двух или более критериев, такие, как взвешенные суммы, усредненные оценки типа fall-out или, например, коэффициент корреляции Мэтью: precision positive prediction value точность1 recall (recall rate), rtu positive rate, sensitivity, hitrate coverage полнота negative prediction value точность отрицательного прогноза specificity специфичность Accuracy аккуратность
F мера (мера Ван Ризбергена) false discovery rate false positive rare fall-out 1 - -error =-error +acc acc = rcl + (1-)spc error αСуществует отличие между задачами <1> и <2>. Оно заключается в том, что в первой задаче пространство оценок считается однородным, тогда как во второй оно разграничено стратами. При проверке гипотез две оценки, расположенные по обе стороны от границы страт сколь угодно близко друг к другу, оказываются значительно «дальше», чем оценки разность которых больше, находящиеся в одной страте.
Использование рассмотренных критериев возможно и при числе страт, большем двух. В этом случае следует выделить проверяемую гипотезу о попадании прогнозной оценки в заданную страту. С другой стороны, при количестве страт, большем двух, можно преобразовать шкалу оценок так, чтобы каждой страте соответствовала одна оценка. Тогда можно формализовать задачу рекомендации объекта в виде задачи <1>. 2.3 Задача выбора последовательности лучших объектов
Оценки всегда формируют линейно упорядоченное множество: для любых i, j выполняется либо 1 Точность, усредненная по пользователям системы имеет обозначение map. ri rj либо rj ri. Аналогичное утверждение верно и для множества оценок vi. Корреляция Пирсона При расчете корреляции Пирсона используются центральные моменты, представляющие средние значения (по множеству опытов) разностей величин и их средних значений.
Косинус угла между векторами R и V: Выражение для cos аналогично корреляции r, только для вычисления косинуса используются не центральные, а начальные моменты. (3) соответствия термину normalized discounted cumulative gain) — ndcg, — рассчитываемый, как отношение Литература
Development of internet services leads to investigation of forecast algorithms. One of them is collaboration filtering. It allows a user to find objects to be the most interesting for him/her. Unfortunately, there is no formal statement of problems solved by the collaboration filtering algorithms. Three problems are considered in the paper, differences between the statements are discussed. It is shown that a spectrum of the valuation scale and definition of notion of proximity of valuations provided by different users determine the type of problem to solve.