Модель рекомендательной системы на нечетких множествах как эффективное расширение коллаборативной модели

-

Рекомендательные системы (далее РС) [ 1 ] – одна из развивающихся областей Computer Science, начавшая свое существование с конца прошлого столетия [ 2 ]. РС являются инструментом, который облегчает пользователю задачу поиска нужной информации путем предоставления рекомендации по использованию соответствующей информации или за счет определения степени близости конкретной информации интересам пользователя.

РС работают со следующими данными: исходными Труды XIX Международной конференции «Аналитика и управление данными в областях с интенсивным использованием данных» (DAMDID/ RCDL’2017), Москва, Россия, 10–13 октября 2017 года • : × → [ 0,1 ] – функция оценки близости и объектов; значение ( , ) показывает, насколько объекты и ⁡близки; как правило, оценки близости задаются самими пользователями за время работы с РС; будем считать, что чем меньше значение оценки, тем объекты ближе; будем говорить, что между пользователем и объектом выполняется отношение близости⁡ℛ, если ( , )≤ 0 ∈ (0); будем называть такие объекты близкими. называется активным и обозначается символом ):

Задача прогнозирования: спрогнозировать роли информации прошедшего времени, тестовое – в неизвестное ⁡⁡будем функции значение ( , )=⊥⁡(символом ⊥ обозначать неизвестное значение) путем алгоритмического вычисления значения прогнозной ( , ): × → [ 0,1 ], где⁡ − ⁡прогнозируемый объект; при этом требуется, чтобы прогноз был составлен точно, то есть | ( , )− ( , )| ≤ 0; 2. Задача – формирование подмножества объектов = { : ( ℛ )∧ ( , )=⊥} ∧ | | = . ℛ функции: в силу отношения прогнозной Так как неизвестно, выполняется ли отношение ℛ того, что ( , )=⊥, то определяется по выполнение

значению ℛ ⇔ ( , )≤ 0. Решение названных задач производится РС за счет анализа информации о ( , )∈ 0, будем обозначать такие объекты 0. Если ( , )∈ ⊥, будем обозначать такие объекты ⊥. 2 Коллаборативные модели

Рассмотрим коллаборативную фильтрацию [ 3-7 ], которая является одним из наиболее изученных [ 3 ], популярных [ 4 ] и успешных [ 5 ] правил вычисления следующий вид: роли информации будущего времени.

Правило Π

основано на утверждении, которое гласит, что если в прошлом пользователи были близки по предпочтениям, то и в будущем они будут близки по предпочтениям. Во введенной данное утверждение примет ℛ ⁡выполняется⁡на⁡ 0 ⇒ ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ ℛ ⁡выполняется⁡на⁡ ⊥, (2) ℛ – отношение близости пользователей. объекты, а значениями весов – значения ( , )∈ 0, которые были выставлены самими пользователями и характеризуют предпочтения пользователей. Для определения близости по предпочтениям используются так называемые меры близости ℛ между : × → [ 0,1 ]: (1 − ( , ))≤ 0 ⇔ ℛ . Пользователи, между которыми выполняется отношение близости, называются соседями. Правило Π СОК задается формулой ∈ , ( ℛ )⇒ | ( , )− ( , )| ≤ 0⁡,⁡⁡(3) ( , )= ({ ( , )}). Правило Π СОК говорит о том, что если пользователи являются соседями для пользователя , коррелируют, ( , ) можно то

оценки ( , ),⁡⁡⁡ ( , ) поэтому неизвестное

значение функционально определить по значениям { ( , )}, то есть прогнозная функция является функцией от значений оценок близости соседей.

Правило Π ООК основано на утверждении: если пользователю нравится объект , который близок по характеристикам к объекту , то пользователю понравится объект . Во введенной терминологии данное утверждение примет вид

( ℛ )∧ ( ℛ )⇒ ℛ ⁡,⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(4) ℛ

– отношение близости объектов. Отношение близости ℛ между объектами устанавливается РС на основании значений

мер близости: 1 − ( , )≤ 0 ⇔ ℛ , : × → [ 0,1 ] – мера близости объектов. Объекты, между которыми выполняется отношение близости, называются соседями.

При решения задачи в ООК используется информация только о тех объектах, для которых известно, что ( ℛ 0), ( ℛ ⊥), поэтому будем считать, что = { ( , ): ℛ } для задачи . Правило Π ООК задается формулой

( ℛ 0)⇒ ( ( , )= 0)⇒ ℛ .⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡(5) Значения ( , ) задаются равными нулю, потому исходного множества. что тогда объекты

будут близки активному пользователю при любом пороговом значении 0.

Правило вывода ООК говорит о том, что если так как ℛ 0 по принятому для задачи существует объект , являющийся соседом объекта 0, то, следуя эвристическому утверждению, ℛ , виду 3 Проблемы применения коллаборативных моделей 3.1 Выполнение эвристических утверждений Будем говорить, что РС эффективна, если ее правила 3.2 Достаточные условия качественного решения множество пользователей или Назовем это условие условием 1. ∀ 1, 2 ∈ : ( 1ℛ )∧ ( 2ℛ )⇒ 1ℛ 2. Достаточным условием, при котором , является транзитивность отношения близости на объединении обучающего, тестового и результирующего множеств: ( ℛ )∧ ( ℛ )⇒ ( ℛ ), , , ∈ 0 ⋃⁡ ⋃⁡ ⊥, ⊥ = { ⊥, 0 = { 0}. Назовем его условием 2.

Выполнение достаточных условий зависит от того, какое значение выбрано в качестве порогового значения 0, и функции, использующейся в качестве меры близости. К примеру, если = cosи 0 = 0,49, то транзитивность не гарантируется; коэффициент корреляции Пирсона [ 6 ], являющийся традиционной мерой близости СОК, не обладает свойством транзитивности [ 9 ].

Если эвристические утверждения выполняются, то правила качественного вывода Π гарантируют

получение решения, если выполняются достаточные условия, что зависит от разработчиков системы.

Проблемы, описанные в разделах 2.1 и 2.2, подтверждены на практике и продемонстрированы ниже в Разделе 4, в Таблицах 1 и 2. 3.3 Масштабируемость

Стандартные алгоритмы решений КРС обладают следующими асимптотическими сложностями [ 10 ]: (| |2) для задачи , (| |) для задачи прогнозирования.

Учитывая огромную мощность множеств , , такие асимптотические сложности приводят к проблеме масштабируемости КРС [ 10 ]. 4 Нечеткая контентная модель 4.1 Описание В нечеткой контентной модели будем представлять контент в виде нечеткое подмножества множества характеристик [ 11 ]: {( | ( , c))}, где – характеристика пользователя или объекта, расстояние

Хэмминга, метрическими свойствами. характеристическая функция принадлежности. Для СОК и ООК контент пользователя представляется в виде нечеткого

множества вида {( |1 − ⁡ ( , ))}. Между пользователями и объектам введем расстояния и соответственно как обобщенное которое обладает При представлении контентов в виде нечетких множеств определим нечеткое отображение Ψ: → объектов, ∈ ⁡– – , характеристическая следующей формулой: и расстояние между пользователем и объектом ∈ Ψ( )= max⁡min{ ( , ); ( , )},⁡⁡⁡⁡⁡⁡⁡⁡(6) функция которого задана ( , )= (Ψ( ), ). (7) т. д. Будем говорить, что оценка сходства задана Нечеткое правило вычисления Πf заключается в задании оценки сходства δc, нечеткого отображения Ψ (6) и вычислении расстояния между пользователем и объектом, определенного формулой (7):

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡Π = { , (6), (7)}.

Нечеткая контентная модель – это модель, которая задается следующей тройкой: | ( , )− ( , )| ≤ 0 Покажем, что выполняется в случае с КРС. Напомним, что оно ( ; ; Π⁡ ∈ ⁡ {Π , ΠСОК, ΠООК}). 4.2 условие при составлении кластера соседей – = достаточное { : ( , )≤ 0/2}.

условие. верно, что ( ℛ )∧ ( ℛ ).

заключается в выполнении свойства транзитивности отношения близости ℛ

на кластере соседей: ∀ , ∈ дополнительному

условию Так как функция ρ

u обладает метрическими свойствами, то ρu(u, v)≤ ρu(ua, u)+ ρu(ua, v). По ρu(ua, u)≤ ε0/2, ρu(ua, v)≤ ε0/2, поэтому ρu(u, v)≤ ε0 ⇒ uℛuv.

Утверждение 2: нечеткая контентная модель (11) является эффективным расширением качества, так как выполняется условие 2 при 0 = 0. Покажем, что выполняется условие 2. Напомним, что оно заключается в выполнении функция обладает метрическими свойствами, то условию ( 0, )= 0, так как выполняется 0ℛ ⊥, то ( 0, ⊥)≤ 0.

Поэтому ( , ⊥)≤ 0, то есть на по (9) (10) (11) выполняется отношение ℛ ⊥.

Таким образом, правила вывода ΠСОК, ΠООК в представлении контентов в виде нечетких подмножеств и при использовании метрических расстояний обладают большей эффективностью по критерию качества решения, так как выполняются достаточные условия 1 и 2, и поэтому контентная нечеткая модель является эффективным расширением по критерию качества. Данный вывод подтверждается практическими результатами (см. таблицы 1 и 2). решения задач 4.3 Применение нечеткого правила вывода для (| |). ( ).

Определим

решения в нечеткой контентной модели при использовании Π .

Задача

может быть решена при помощи линейного поиска объектов, таких, что ( , )⁡ ≤ 0. Асимптотическая сложность такого алгоритма равна Для решения задачи прогнозирования нужно всего лишь рассчитать значение ( , ), поэтому асимптотическая сложность такого решения равна Если оценка сходства задана аккуратно, то решения

задач эффективны по контентной критерию нечеткой

модели качества, что будет продемонстрировано на разделе 4. Точность задания зависит только от разработчиков, но не от свойств исходных данных или дополнительных условий, как Асимптотические сложности алгоритмов решений при использовании правила вывода Π порядок меньше по сравнению со сложностями КРС, поэтому представленная модель более эффективна по критерию масштабируемости, чем КРС. Каждый раз, когда производится вычисление с, производятся отображение⁡⁡Ψ и расчет . Сложности вычислений отображения Ψ и зависят от мощности контента (которое, как правило, значительно меньше мощности множеств пользователей и объектов) и от того, как была задана разработчиками, поэтому эти сложности не учтены в расчетах, представленных на ниже.

Приведенные значения асимптотических сложностей показывают, что контентная нечеткая модель является эффективным расширением КРС по критерию масштабируемости. 5 Практические результаты

Для получения практических результатов было разработано программное обеспечение, которое реализует ООК, СОК и нечеткую контентную РС. С помощью ООК решалась задача , с помощью Пороговое значение 0 было принято равным 0,1.

Чтобы применить Π , была задана функция⁡ ⁡⁡на основании эвристического предположения о том, что между оценкой пользователя и жанрами объектов существует корреляция: ( , )= (| | − | |)/| u|. Если ( , )< ⁡0, то ⁡

( , )= 0,0001; = { : ( ( , )≤ ⁡ 0)⁡ ∧ ( , )⁡ ≠ 0}, = { : ( ( , )> ⁡ 0)⁡∧ ( , )⁡ ≠ 0},

u = { : ( ( , )≠⁡⊥)}. некоторых – нет.

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

Поэтому для некоторых пользователей функция задана аккуратно, а для Стандартно при проведении тестирования данные о пользователе случайно разбивались в следующем отношении: 80% – обучающее множество, 20% – тестовое. Обозначим такое разбиение разбиения цифрой 1.

Помимо стандартного использовались и другие специально сформированные разбиения 2 и 3. Разбиение 2 составлено так, что обучающее множество состоит из таких объектов ,⁡ для которых выолняется отношение ℛ , тестовое множество состоит из таких объектов , для которых отношение ⁡ℛ ⁡ не выполняется. Такое разбиение создано для того, чтобы подтвердить или опровергнуть влияние свойства неоднородности данных на эффективность по критерию качества. Разбиение 3 составлено так же, как и стандартное разбиение, но в нем участвуют только те пользователи, для которых функция задана аккуратно.

Эффективность

решений задач по критерию качества определяется усредненными по числу тестов (равному 1000 для каждой задачи, разбиению и модели) значениями функций. Эффективность по NDCG. В результате тестирования среднее значение этих функций мало отличалось, поэтому в Таблице 1 приведены RMSE, меньшее значение которых говорит о более эффективном решении.

Таблица 1 Разбиение P Модель/Правило вычисления ООК/⁡ΠООК ООК/⁡ΠООК Нечеткая /⁡ΠООК Нечеткая /⁡ΠООК Нечеткая контентная/⁡Π Нечеткая контентная/⁡Π Нечеткая контентная/⁡Π контентная 1 контентная 2 1 2 1 2 3 Результаты 3 и 4 эффективнее результатов 1 и 2, что подтверждает вывод о том, что нечеткая контентная модель является эффективным расширением, так как в ней выполняются достаточные условия 1 и 2. Эти же результаты подтверждают выводы о влиянии меры сходства на эффективность ООК и СОК по критерию качества.

Результаты 7 эффективнее результатов 3–6, так как для разбиения 7 функция задана аккуратно. Результаты 7 эффективнее результатов 5 и 6, так как для 5 и 6 в общем случае ⁡не⁡задана⁡аккуратно, и поэтому же 5 и 6 не эффективнее 3 и 4. Результаты 5 эффективнее 6, так как функция задавалась на основании данных обучающего множества, поэтому свойство неоднородности влияет на аккуратность функции так же, как и на эффективность КРС по критерию качества. Использование Π может быть неэффективным, если о пользователях известна только та информация, которая принадлежит исходному множество . В такой ситуации эффективнее использовать нечеткую модель ΠООК или ΠСОК. Для задания функции можно использовать информацию, которая никак не зависит от мощности и свойств исходных данных, и тогда решения задач в нечеткой контентной модели не будут зависеть от свойств исходных данных. Такой информацией может выступать, к примеру, контекстная информация [ 13 ]. 6 Заключение

Нечеткая контентная модель РС, представленная в настоящей работе, является эффективным расширением КРС по критериям качества решений и масштабируемости. Литература

References

[1] Resnick , P. , Varian , H.R. : Recommender systems . Communications of the ACM , 40 ( 2 ), pp. 56 - 58 ( 1997 )

[2] Goldberg , D. , Nichols , D. , Oki , B.M. , Terry , D. : Using collaborative filtering to weave an information tapestry . Communications of the ACM , 35 ( 12 ), pp. 61 - 70 ( 1992 )

[3] Asanov , D. : Algorithms and Methods in Recommender Systems . Berlin Institute of Technology. https://www.snet.tuberlin.de/fileadmin/ fg220/courses/SS11/snetproject/ recommender-systems_asanov.pdf

[4] Yao , W. , Xudong , L. , Min , X. , Ester , M. , Qing , Y. : CCCF: Improving Collaborative Filtering via Scalable User-Item Co-Clustering . WSDM '16 Proc. of the Ninth ACM Int. Conf. on Web Search and Data Mining , pp. 73 - 82 ( 2016 )

[5] Hu , R. , Pu , P. : Using personality information in collaborative filtering for new users . Recommender Systems and the Social Web , pp. 17 - 24 ( 2010 )

[6] Su , X. , Khoshgoftaar , T. : A survey of collaborative filtering based social recommender systems . Computer Communications , 41 , pp. 1 - 10 ( 2014 )

[7] Wang Jun : Unifying user-based and item-based collaborative filtering approaches by similarity fusion . SIGIR'06 Proc. of the 29th Annual International ACM , pp. 501 - 508 ( 2006 )

[9] Castro Sotos , A. , Vanhoof , S. , Van den Noortgate, W., Onghena , P.: The non-transitivity of Pearson's correlation coefficient: an educational perspective . Proc. of the 56th Session of the ISI , 62 , pp. 4609 - 4613 ( 2007 )

[10] Linden , G. , Smith , B. , York, J.: Amazon.com Recommendations Item-to-Item Collaborative Filtering . Internet Computing, IEEE, 7 , pp. 76 - 80 ( 2003 )

[11] Амелькин , С.А. , Понизовкин , Д.П.: Математическая модель задачи topN для контентных рекомендательных систем . Изв. МГТУ МАМИ , 2 , cс. 26 - 31 ( 2013 )

[12] Deshpande , M. , Karypis , G.: Item-Based Top-N Recommendation Algorithms . ACM Transactions on Information Systems , 22 ( 1 ), pp. 143 - 177 ( 2004 )

[13] Adomavicius , G. , Tuzhilin , A. : Context-aware recommender systems . Conference: Proc. of the 2008 ACM Conference on Recommender Systems, RecSys 2008 , Lausanne, Switzerland, October 23- 25 , 2008 . doi: 10 .1007/978-1- 4899 -7637- 6 _ 6