DATA MINING: РЕКОМЕНДАТЕЛЬНЫЕ СИСТЕМЫ Collaboration Filtering Максим Гончаров

Рекомендательные системы Подходы к формированию рекомендаций Задачи Подходы Сбор данных: Explicit/Implicit Content-based/Transaction-based Model-based/Memory-based User-based/Item-based Алгоритмы Ассоциативные правила Транзитивные ассоциативные сети Collaboration Filtering User-based Item-based Другие алгоритмы Big Data, Hadoop, Mahout etc 2

v v Рекомендательные системы: задачи и подходы

Задачи рекомендательных систем Рекомендательные системы (РС) применяются для предложения клиенту в реальном времени продуктов (фильмов, книг, одежды) или услуг, которые его с большой вероятностью заинтересуют. 4 Применения: Cross-Sale, Up-Sale электронная коммерция, он-лайн банкинг, розничная торговля, справочные центры, поиск фильмов, музыки, ПО, научных статей

Принцип рекомендательных систем Рекомендации предоставляются на основании уже совершенных покупок, посещений сайтов, а также приема обратной связи: выставленных рейтингов, заполненных анкет. 5 Примеры: Amazon.com (Item-based CF), Музыка на Yahoo!, Cinemax.com, Moviecritic, TV Recommender, Video Guide, CDnow.com и проч.

Критерии оценки качества РС Точность. Разделяем транзакции на обучающее и тестовое множество. Транзакции в обучающем множестве служат для оценки рейтингов товаров. Товары из каждой тестовой транзакции случайно разделяются на две группы: «известные» и «неизвестные». На основании рейтингов группы «известных» товаров строятся рейтинги для группы «неизвестных». Покрытие. Для какой части товаров РС может формировать прогнозы рейтнига или выдавать рекомендации? Скорость обучения. Степень новизны. Можно представить РС, дающую точные прогнозы с большим покрытием, но бесполезные. Например рекомендации по самым популярным товарам. 6

Как собирать данные? Используется явный или неявный сбор данных. При явном сборе от пользователя требуется заполнять анкеты для выявления предпочтений. При неявном сборе действия пользователя протоколируются для выявления предпочтений, и составления рейтингов происходит автоматически. Иногда оба подхода комбинируются: когда транзакционной истории пока нет – используются опросы. Затем начинают учитывать транзакции. 7

Как вычислять похожесть? Основной принцип: похожим пользователям рекомендуют похожие товары. Как определять похожесть? Content-based. Похожесть определяется на основании характеристик товаров и пользователей. Для товаров: сюжет, режиссер, киношкола; общее музыкальное направление, стиль; функциональное назначение, категория, ценовая группа. Для клиентов: демографические данные, предпочтения из заполненных анкет. Transaction-based. Товары считаются похожими, если часто входят вместе в одну транзакцию, а пользователи – если совершают схожие покупки. 8

Используется ли модель предметной области? Memory-based. Модели данных нет. Рекомендации формируются на основании вычисления некой меры похожести по всем накопленным данным. Этот подход проще, обладает высокой точностью, может использовать инкрементальный учет новых данных. Но ресурсоемок, не может предоставить описательный анализ существующих закономерностей, дать большее понимание имеющихся данных и объяснить прогноз. Model-based. Сначала формируется описательная модель предпочтений пользователей, товаров и взаимосвязи между ними, а затем формируются рекомендации на основании полученной модели. Преимущества: наличие модели, дающей большее понимание формируемых рекомендаций, а также то, что процесс формирования рекомендаций разбит на два этапа: ресурсоемкое обучение модели в отложенном режиме и достаточно простое вычисление рекомендаций на основе существующей модели в реальном времени. Недостатки: не поддерживают инкрементального обучения, меньшая точность прогноза. 9

Collaboration Filtering Collaboration Filtering – способ формирования рекомендаций: implicit (пользователи не опрашиваются), memory-based (без составления модели), transaction-based (на основе пользовательского поведения). User-based. Предложить товары, приобретаемые похожими пользователями: усреднить рейтинги товара, проставленные другими пользователями, с весами по степени похожести пользователей. Item-based. Предложить товары, похожие на уже приобретенные: усреднить рейтинги уже оцененных товаров с весами по степени похожести на неоцененный товар. 10

v v Рекомендательные системы: Алгоритмы

SQL Server Analysis Services Data Mining Microsoft Association Rules Правила вида «если A и B, то с вероятностью x также C», описывающие, например, совместно приобретаемые услуги. Поиск ассоциаций: Какие товары продаются совместно? Есть ли взаимосвязь между музыкальными и математическими способностями? 12

SQL Server Analysis Services Data Mining Microsoft Association Rules Алгоритм a-priori Алгоритм основан на итеративном вычислении частых наборов длиной i, т.е. наборов из i товаров, входящих более, чем в N чеков. Далее, наборы длиной i объединяются друг с другом для получения частых наборов длиной i+1. Как только все частые наборы найдены, они разбиваются на левую и правую часть для получения правил вхождения товаров из правой части набора при условии вхождения левой части. Оставляются только состоятельные правила (с большой вероятностью) и интересные (те, в которых левая часть сильно влияет на правую часть правила). 13

SQL Server Analysis Services Data Mining Microsoft Association Rules Параметры алгоритма a-priori Support – насколько часто корзина товаров встречается совместно в транзакциях. Confidence – насколько велика условная вероятность правой части правила при условии соблюдения левой части. Lift – насколько выполнение левой части правила увеличивает вероятность выполнения правой части. 14

SQL Server Analysis Services Data Mining Microsoft Association Rules 15

SQL Server Analysis Services Data Mining Microsoft Association Rules 16

SQL Server Analysis Services Data Mining Microsoft Association Rules 17

SQL Server Analysis Services Data Mining Microsoft Association Rules Ассоциативные правила более предназначены для описательного анализа, т.е. для определения какие товары продаются совместно, а не для формирования рекомендаций. Это связано с тем, что у алгоритма низкое покрытие: правила существуют только для небольшого набора товаров. Если у нас 1000 товаров и мы хотим для каждой пары товаров иметь возможность рекомендовать третий товар, то необходимо, чтобы транзакции, включающие все пары товаров + произвольный третий товар, были «частыми», т.е. встречались не менее 100 раз, получаем: минимум ~ записей. 18

SQL Server Analysis Services Data Mining Microsoft Association Rules DMX-запросы дают одинаковые результаты, т.к. не выявлены правила с участием левой части, поэтому рекомендуются наиболее популярные товары. SELECT FLATTENED ( SELECT [Movie], $NODEID FROM PredictAssociation([Movie Prediction Model].[Movies], 5, INCLUDE_NODE_ID) ) AS [Movie Prediction] FROM [Movie Prediction Model] NATURAL PREDICTION JOIN ( SELECT ( SELECT '28 Days' AS [Movie] ) AS [Movies] ) AS t 19

Microsoft Association Rules 20

Microsoft Association Rules 21

Microsoft Association Rules 22

Microsoft Association Rules 23

Microsoft Association Rules 24

SQL Server Analysis Services Data Mining Microsoft Association Rules Ассоциативные правила: идея ТоварыТранзакции А1 Б2 В3 Д4 Е5 Товары А и Б «сильно похожи», потому что вместе входят в транзакции 1 и 2. Товары Б и В «менее похожи», потому что вместе входят в транзакцию 2. 25

Транзитивные ассоциативные сети Расширение алгоритма ассоциативных правил. Мы считаем, что товары А и В также похоже, хотя они вместе не входят ни в одну транзакцию. А и В похожи потому что А ~ Б, Б ~ В. ТоварыТранзакции А1 Б2 В3 Д4 Е5 Другими словами: между товарами А и В существует путь длины 2. 26

Транзитивные ассоциативные сети Допустим, что пользователи c1 и c2 приобрели товар p1, а пользователи c2 и c3 приобрели товар p2. Стандартные алгоритмы совместной фильтрации свяжут пользователей c1 и c2, а также пользователей c2 и c3, но не свяжут c1 и c3. Для получения транзитивных связей между транзакциями используется граф, узлы которого состоят из двух частей – транзакции и товары, а дуги связывают транзакции с входящими в них товарами. 27

Транзитивные ассоциативные сети Для учета транзитивных связей между товарами мы рассматриваем все пути между ними с длиной не больше заданного числа M. Стандартные алгоритмы совместной фильтрации учитывают пути длиной 1. Интуитивно понятно, что чем больше число различных путей, соединяющих два узла, тем сильнее связь между ними. Также интуитивно понятно, что чем длинней путь, связывающий два узла, тем слабее связь между ними. Если A – матрица сопряженности (достижимости между товарами через одну транзакцию) между товарами, то A i – матрица достижимости за i шагов (через i транзакции). Если складывать число путей одной длины между товарами с весом

Транзитивные ассоциативные сети -- заполняем таблицу транзакций AS input.CoOccuranceTable; INSERT ( TransactionId, ItemId ) SELECT CustomerID, Movie FROM dbo.Movies -- запрос на похожие товары: SELECT * FROM [cooccurance].[getItemDistance](N'28 Days', ORDER BY similarity DESC -- запрос на прогноз SELECT * FROM N'28 Days,') t ORDER BY similarity DESC 29

Транзитивные ассоциативные сети 30

Транзитивные ассоциативные сети 31

v v Collaboration Filtering

User-based Collaboration Filtering Каждому пользователю ставится в соответствие вектор покупок, где каждому товару приписывается его рейтинг. В качестве меры близости между пользователями применяются метрики, основанные на углах между векторами покупок. Косинус угла между векторами покупок. Корреляция между векторами покупок. Рейтинг товара данного пользователя определяется как средний рейтинг этого товара, проставленный другими пользователями с учетом веса, определяемого мерой близости к данному пользователю. 33

User-based Collaboration Filtering Фильтрация по пользователям имеет высокую точность. Однако, недостатком всех вариантов приведенного алгоритма является его ресурсоемкость (требование к памяти) и сложность (количество вычислений, требуемое для получения рекомендаций). К тому же вычисление степени близости анализируемой транзакции ко всем остальным транзакциям может производиться только в реальном времени, так как данные о текущей транзакции становятся доступными только в момент выработки рекомендаций Вывод: фильтрация по пользователям может применяться только к относительно небольшим базам данных. 34

Item-based Collaboration Filtering Каждому товару ставится в соответствие вектор клиентов, где каждому клиенту приписывается рейтинг, который он выставил данному товару. В качестве меры близости между товарами применяются метрики, основанные на углах между векторами клиентов. Идея в фильтрации по товарам состоит в выставлении неизвестного рейтинга товару в анализируемой транзакции на основании взвешенных рейтингов других товаров, входящих в эту транзакцию. Т.е. мы считаем, что рейтинг товара будет близок к рейтингам похожих на него товаров из уже оцененных. 35

Item-based Collaboration Filtering В алгоритме фильтрации по товарам степень близости анализируемого товара ко всем остальным товарам может быть вычислена в отложенном режиме по расписанию, так как вектора рейтингов всех товаров доступны до момента формирования рекомендации. Мы можем разделить процесс выработки рекомендаций на отложенную стадию (вычисление степени близости товаров друг к другу) и стадию в реальном времени (вычисление рейтингов товаров). Таким образом, алгоритм фильтрации по товарам оказывается более эффективным с точки зрения времени формирования рекомендаций, чем алгоритм фильтрации по транзакциям благодаря возможности проведения отложенной предобработки данных. 36

v v Рекомендательные системы: Другие алгоритмы

Другие алгоритмы Компрессия и понижение размерности матрицы связи между клиентами и товарами при помощи SVD. Метод персональной диагностики. Мы рассматриваем анализируемую транзакцию как будто она была выбрана случайно с равномерным распределением из генеральной совокупности транзакций с добавлением белого шума. Т.е. помимо наблюдаемой случайной величины, соответствующей рейтингам товаров в анализируемой транзакции, у нас есть еще ненаблюдаемая случайная величина, которая описывает вариантом какой транзакции является «на самом деле». Классификация: Naïve Bayes. 38

Другие алгоритмы Гибкая смешанная модель (Flexible Mixture Model). Идея этого метода основывается заключается в следующем: Существует отдельный набор групп пользователей и отдельный набор групп товаров, вхождение в которые определяют значение рейтинга. Т.е. пользователи из группы i оценивают товары из группы j примерно одинаково. Пользователь или товар могут входить в несколько групп. Т.е. фильм может быть историческим, военным и психологическим одновременно. Аспектная модель (Aspect Model). Множество данных состоит из наблюдений, представляющих собой пары совместно встречающихся транзакций и товаров, интерпретируемые как «в i-ую транзакцию входит j-ый товар». С каждым наблюдением также связана ненаблюдаемая переменная класса, описывающая группы транзакций и товаров, «встречающихся» совместно. 39

v v Big Data, Hadoop, Mahout etc

Big Data 41 Traditional RDBMSMapReduce Data SizeGigabytes (Terabytes)Petabytes (Hexabytes) AccessInteractive and BatchBatch UpdatesRead / Write many timesWrite once, Read many times StructureStatic SchemaDynamic Schema IntegrityHigh (ACID)Low ScalingNonlinearLinear DBA Ratio1:401:3000 Reference: Tom Whites Hadoop: The Definitive Guide Large ComplexUnstructured

Mahout Apache Mahout - масштабируемая библиотека машинного обучения для Hadoop, предназначенная для обработки больших объемов данных. Collaborative Filtering User and Item based recommenders K-Means, Fuzzy K-Means clustering Mean Shift clustering Dirichlet process clustering Latent Dirichlet Allocation Singular value decomposition Parallel Frequent Pattern mining Complementary Naive Bayes classifier Random forest decision tree based classifier 42

Hadoop: ссылки Running Apache Mahout at Hadoop on Windows Azure: n/archive/2012/03/06/running-apache- mahout-at-hadoop-on-windows-azure- www-hadooponazure-com.aspx n/archive/2012/03/06/running-apache- mahout-at-hadoop-on-windows-azure- www-hadooponazure-com.aspx 43

Литература J. Herlocker, J. Konstan, L. Terveen, and J. Riedl.: Evaluating collaborative filtering recommender systems, ACM Translations on Information Systems, Vol. 22(1), Jun Wang, Arjen P. de Vries, Marcel J.T. Reinders, Unifying Userbased and Itembased Collaborative Filtering Approaches by Similarity Fusion. Justin Basilico, Thomas Hofmann Unifying Collaborative and Content-Based Filtering. Manolis G. Vozalis, Konstantinos G. Margaritis Applying SVD on Generalized Item-based Filtering. David M. Pennock, Eric Horvitz, Steve Lawrence and C. Lee Giles Collaborative Filtering by Personality Diagnosis: A Hybrid Memory- and Model-Based Approach. Prem Melville, Raymond J. Mooney, Ramadass Nagarajan Content-Boosted Collaborative Filtering for Improved Recommendations. Anne Yun-An Chen, Dennis McLeod Collaborative Filtering for Information Recommendation Systems. Luo Si, Rong Jin Flexible Mixture Model for Collaborative Filtering. Lyle H. Ungar, Dean P. Foster A Formal Statistical Approach to Collaborative Filtering. Rong Jin, Joyce Y. Chai, Luo Si An Automatic Weighting Scheme for Collaborative Filtering. Thomas Hofmann, Jan Puzieha Latent Class Models for Collaborative Filtering. Thomas George, Srujana Merugu A Scalable Collaborative Filtering Framework based on Co-clustering. A. Banerjee, I. Dhillon, J. Ghosh, S. Merugu, and D. Modha A generalized maximum entropy approach to Bregman co-clustering and matrix approximation. Gui-Rong Xue, Chenxi Lin, Qiang Yang, WenSi Xi, Hua-Jun Zeng, Yong Yu1, Zheng Chen Scalable Collaborative Filtering Using Cluster-based Smoothing. Zan Huang, Hsinchun Chen, Daniel Zeng Applying Associative Retrieval Techniques to Alleviate the Sparsity Problem in Collaborative Filtering. Kai Yu, Anton Schwaighofer, Volker Tresp, Wei-Ying Ma, HongJiang Zhang Collaborative Ensemble Learning: Combining Collaborative and Content-Based Information Filtering via Hierarchical Bayes. Dmitry Y. Pavlov, David M. Pennock A Maximum Entropy Approach To Collaborative Filtering in Dynamic, Sparse, High-Dimensional Domains. Michael Leben Applying Item-based and User-based collaborative filtering on the Netflix data. Benjamin Marlin Collaborative Filtering: A Machine Learning Perspective. А.А. Барсегян, М.С. Куприянов, И.И. Холод, М.Д. Тесс Анализ данных и процессов, СПб.: БХВ-Петербург,