Вероятностные модели в анализе клиентских сред тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Лексин, Василий Алексеевич

• Лексин, Василий Алексеевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Лексин, Василий Алексеевич

Введение

1 Задачи и методология анализа клиентских сред

1.1 Структура исходных данных.

1.2 Прикладные задачи, потребности.

1.3 Методология анализа клиентских сред.

2 Обзор методов коллаборативной фильтрации

2.1 Корреляционные алгоритмы

2.2 Модельные алгоритмы.

2.2.1 Латентный семантический анализ.

2.2.2 Вероятностный латентный семантический анализ

2.2.3 Иерархический вероятностный латентный семантический анализ.

2.3 Методы задания начального приближения профилей

3 Вероятностный латентный семантический анализ

3.1 Восстановление скрытых профилей клиентов и объектов

3.1.1 Вероятностная модель порождения данных

3.1.2 Модификация стандартного подхода.

3.1.3 Симметризованный подход.

3.1.4 Сравнение подходов.

3.2 Оценка скорости сходимости ЕМ-алгоритма.

3.2.1 Оценка асимптотической скорости сходимости

3.2.2 Условие суперлинейной сходимости

3.3 Методы улучшения сходимости ЕМ-алгоритма

3.3.1 Задание начального приближения профилей

3.3.2 Метод сглаженной корреляции.

3.3.3 Начальное приближение профилей по представительным объектам.

3.3.4 Обнуление малых компонент скрытых переменных и профилей

4 Эксперименты

4.1 Описание наборов данных.

4.1.1 Моделирование данных.

4.1.2 Данные поисковой машины.

4.1.3 Данные интернет-магазина.

4.2 Функционалы качества

4.2.1 Сравнение профилей.

4.2.2 Функционал качества на модельных данных

4.2.3 Функционалы качества на реальных данных

4.3 Описание экспериментов.

4.3.1 Сравнение различных алгоритмов АКС

4.3.2 Начальное приближение.

4.3.3 Методика обнуления малых компонент скрытых переменных.

4.3.4 Карта сходства всех объектов.

4.3.5 Локальная карта сходства объектов.

4.3.6 Интерпретации и выводы.

Введение диссертации (часть автореферата) на тему «Вероятностные модели в анализе клиентских сред»

Актуальность темы исследования. В работе вводится понятие клиентской среды, позволяющее с единых позиций подходить к анализу транзакционных данных, возникающих в различных прикладных областях. Клиентская среда описывается тремя множествами: множеством субъектов (клиентов, пользователей), множеством объектов (ресурсов, услуг, товаров, документов и т.д.) и множеством транзакций. В типичном случае транзакция представляет собой запись о взаимодействии некоторого субъекта с некоторым объектом. В качестве приложений можно рассматривать клиентские среды интернет-магазинов, поисковых машин, электронных библиотек, социальных сетей, торговых сетей, операторов связи, и т.д. Целью анализа клиентских сред (АКС) является построение информационных сервисов для выявления предпочтений клиентов, формирования персональных рекомендаций, поиска релевантных объектов или субъектов, выявления и визуализации скрытых закономерностей.

В работе исследуются методы вероятностного латентного семантического анализа (РЬБА), основанные на байесовской вероятностной модели данных. Для идентификации параметров модели по выборке транзакций применяется итерационный #М-алгоритм, максимизирующий функционал правдоподобия. Методы РЬБА позволяют получать сжатые семантические описания для каждого объекта и каждого субъекта в виде вектора вероятностей тем, называемого в работе профилем соответствующего объекта или субъекта.

Хотя данный подход активно применяется уже более 10 лет, оценки скорости сходимости ЕМ-алгоритма именно для РЬБА до сих пор не были получены. Кроме того, оставались открытыми вопросы формирования начальных приближений и влияния разреженности профилей на качество решения и скорость сходимости Е'М-алгоритма. Получение ответов на эти вопросы является актуальной задачей.

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

Научная новизна. Впервые получены оценки скорости сходимости £7М-алгоритма в РЬБА, установлены условия суперлинейной сходимости, выявлены основные параметры, воздействуя на которые можно улучшить сходимость .Е'М-алгоритма. Разработаны новые эвристические методы, позволяющие улучшить качество восстановления профилей и скорость сходимости итерационного ЕМ-алгоритма. Предложена симметризованная модель РЬБА и метод оценивания её параметров на основе нового двухступенчатого Е'М-алгоритма. Предложен способ формирования начальных приближений для .БМ-алгоритма на основе быстрой кластеризации исходных данных, в то время как в литературе обычно предлагается брать случайные начальные приближения. Предложена методика поддержания разреженности тематических профилей в ходе итераций. Описана общая методология анализа клиентских сред, включающая операции предварительной обработки данных, предварительной кластеризации, восстановления профилей, вычисления функций сходства между объектами и субъектами, формирование рекомендаций, их ранжирование и визуализацию в виде карт сходства.

Методы исследований. Для построения байесовской вероятностной модели взаимодействия клиентов и объектов и оценки параметров модели с помощью принципа максимизации взвешенного правдоподобия (МВП) применяются методы теории вероятности и математической статистики. При выводе формул £7М-алгоритма применяются методы минимизации функций с ограничениями типа равенств. Для оценки сходимости ЕМ-алгоритма используются свойства линейных пространств и операторных норм. При разработке эвристических методов улучшения сходимости применяются методы математической статистики и комбинаторного анализа.

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

Результаты, выносимые на защиту.

1. Симметризованная модель вероятностного латентного семантического анализа и метод оценивания её параметров на основе двухступенчатого ЕМ-алгоритма.

2. Асимптотическая оценка скорости сходимости .ЕМ-алгоритма и условия его суперлинейной сходимости.

3. Способы улучшения сходимости Е'М-алгоритма и повышения качества восстановления профилей.

Практическая и теоретическая ценность. Вопрос о сходимости итерационных методов оценивания параметров моделей по выборкам данных является одной из ключевых проблем в математической теории распознавания и классификации. Настоящая работа даёт решение данной проблемы для задач восстановления тематических профилей, которые можно рассматривать как специальный класс задач кластеризации.

Предлагаемые методы улучшения сходимости Е'М-алгоритма и повышения качества восстановления профилей (формирование начального приближения, поддержание разреженности профилей, оптимизация параметров на модельных данных, учет априорной информации и т.д.) направлены на непосредственное практическое применение. В работе приводятся результаты экспериментов на реальных данных, демонстрирующие практическую применимость предложенных методов.

Аппробация работы. Результаты работы неоднократно докладывались на научных семинарах отдела Интеллектуальных систем ВЦ РАН и на конференциях:

• международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» РОАИ-9, Нижний Новгород, 2008 г. [29];

• 50-я научная конференция МФТИ, 2007 г. [4];

• всероссийская конференция «Математические методы распознавания образов» ММРО-13, 2007 г. [5];

• 49-я научная конференция МФТИ, 2006 г. [3];

• международная конференция «Интеллектуализация обработки информации» ИОИ-б, 2006 г. [6, 2];

• всероссийская конференция «Математические методы распознавания образов» ММРО-12, 2005 г.

Публикации. По теме диссертации опубликовано 9 работ, в том числе в изданиях из списка, рекомендованного ВАК РФ — одна [28], 7 в трудах конференций. Еще одна статья принята к публикации в рецензируемом журнале.

Структура и объем диссертационной работы. Диссертация изложена на 95 страницах машинописного текста и состоит из введения, 4 глав, заключения и списка литературы. Список литературы состоит из 41 наименования.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Лексин, Василий Алексеевич

Заключение

В работе предложена методология анализа клиентских сред, основанная на вероятностном латентном семантическом анализе (РЬБА). Введена байесовская вероятностная модель данных об использовании объектов клиентами, позволяющая выявлять скрытые тематические профили клиентов и объектов на основе принципа максимума правдоподобия и .ЕМ-алгоритма.

Предложен симметризованный 2?М-алгоритм, позволяющий, не выходя за рамки той же модели вероятностного латентного семантического анализа, повысить скорость сходимости и качество восстановления скрытых тематических профилей клиентов и объектов.

В данной работе впервые получены оценки скорости сходимости ЕМ-алгоритма, лежащего в основе метода РЬБА, и найдено условие его суперлинейной сходимости. На основе полученных теоретических результатов предложен ряд эвристик, повышающих скорость сходимость ЕМ-алгоритма и качество восстановления профилей по сравнению со стандартными вариантами ЕМ-алгоритма.

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

Перспективными направлениями дальнейших исследований представляются следующие: разработка различных модификаций вероятностной модели, разработка методов оптимизации числа латентных тем и степени разреженности профилей для иерархических профилей, в частности, путем выработки критериев расщепления тем в профилях и разработки инкрементных методов оценивания профилей клиентов и объектов.

Список литературы диссертационного исследования кандидат физико-математических наук Лексин, Василий Алексеевич, 2011 год

1. Воронцов К. В. Предварительная обработка данных для решения специального класса задач распознавания // ЖВМ и МФ. - 1995. - Т. 35, № 10. - С. 1565-1575.

2. Выявление и визуализация метрических структур на множествах пользователей и ресурсов Интернет / К. В. Воронцов, К. В. Рудаков, В. А. Лексин, А. Н. Ефимов // Искусственный Интеллект. 2006. - С. 285-288.

3. Лексин В. А. Персонализация контента на основе оценок сходства пользователей и ресурсов сети интернет // Труды 49-й научной конференции МФТИ. Т. УН-2. - 2006. - С. 276-277.

4. Лексин В. А. Оценивание сходства пользователей и ресурсов путем выявления скрытых тематических профилей // Труды 50-й научной конференции МФТИ. Т. УН-2. - 2007. - С. 104106.

5. Лексин В. А., Воронцов К. В. Анализ клиентских сред: выявление скрытых профилей и оценивание сходства клиентов и ресурсов // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. С. 488-491.

6. О метрических структурах на множествах пользователей и ресурсов интернет / К. В. Воронцов, К. В. Рудаков, В. А. Лексин, А. Н. Ефимов // Интеллектуализация обработки информации: Тезисы докл. Симферополь. — 2006. — С. 46-48.

7. Adomavicius G., Tuzhilin A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions // IEEE Transactions on Knowledge and Data Engineering. — 2005. — Vol. 17, no. 6.

8. Application of dimensionality reduction in recommender system a case study / Badrul M. Sarwar, George Karypis, Joseph A. Konstan, John T. Riedl //IN ACM WEBKDD WORKSHOP. - 2000.

9. Billsus Daniel, Pazzani Michael J. Learning collaborative information filters 11 Proc. 15th International Conf. on Machine Learning. — Morgan Kaufmann, San Francisco, CA, 1998. — Pp. 46-54.

10. Brand Matthew. Fast online svd revisions for lightweight recommender systems // SIAM International Conference on Data Mining. 2003.

11. Canny John. Collaborative filtering with privacy via factor analysis //In Proceedings of the 25th annual international ACM

12. SIGIR conference on Research and development in information retrieval. ACM Press, 2002. - Pp. 238-245.

13. Dempster A. P., Laird N. M., Rubin D. B. Maximum likelihood from incomplete data via the EM algorithm // J. of the Royal Statistical Society, Series B. — 1977. — no. 34. — Pp. 1-38.

14. Goldberg Ken, Roeder Theresa, Gupta Dhruv, Perkins Chris. Eigentaste: A constant time collaborative filtering algorithm. — 2000.

15. Fayyad Usama M., Reina Cory A., Bradley Paul S. Initialization of iterative refinement clustering algorithms // Knowledge Discovery and Data Mining. AAAI Press, 1998. - Pp. 194-198.

16. Generative models for cold-start recommendations / Andrew I. Schein, Alexandrin Popescul, Lyle H. Ungar,

17. David M. Pennock // the SIGIR'Ol Workshop on Recommender Systems. 2001.

18. George Thomas. A scalable collaborative filtering framework based on co-clustering // Fifth IEEE International Conference on Data Mining. 2005. - Pp. 625-628.

19. Grcar M. User profiling: Collaborative filtering // SIKDD 2004 at multiconference IS 12-15 Oct 2004, Ljubljana, Slovenia. — 2004.

20. GroupLens: An open architecture for collaborative filtering of netnews / P. Resnick, N. Iacovou, M. Suchak et al. // Proceedings of ACM 1994 Conference on Computer Supported Cooperative Work. Chapel Hill, North Carolina: ACM, 1994. - Pp. 175-186.

21. Gunawardana Asela, Byrne William. Convergence theorems for generalized alternating minimization procedures // J. Mach. Learn. Res. 2005. - Vol. 6. - Pp. 2049-2073.

22. Hofmann Thomas. Latent semantic models for collaborative filtering // ACM Transactions on Information Systems. — 2004.— Vol. 22, no. l.-Pp. 89-115.

23. Hofmann Thomas, Puzicha Jan. Latent class models for collaborative filtering // International Joint Conference in Artificial Intelligence. 1999.

24. Indexing by latent semantic analysis / Scott Deerwester, Susan T. Dumais, George W. Furnas et al. // Journal of the

25. American Society for Information Science. — 1990. — Vol. 41. — Pp. 391-407.

26. Item-based collaborative filtering recommendation algorithms / Badrul Sarwar, George Karypis, Joseph Konstan, John Reidl // Proceedings of the 10th international conference on World Wide Web. WWW '01. - New York, NY, USA: ACM, 2001. - Pp. 285295.

27. Jin R, Si Luo, Zhai Chengxiang. A study of mixture models for collaborative filtering // Information Retrieval. — 2006. — Vol. 9, no. 3. Pp. 357-382.

28. Leksin V. A. Symmetrization and overfitting in probabilistic latent semantic analysis // Pattern Recognition and Image Analysis. — 2009. Vol. Volume 19, Number 4 / Декабрь 2009 г. - Pp. 565574.

29. Leksin V. A., Vorontsov К. К The overfitting in probabilistic latent semantic models // Pattern Recognition and Image Analysis: new information technologies (PRIA-9).— Vol. 1.— Nizhni Novgorod, Russian Federation, 2008. Pp. 393-396.

30. Marlin B. Collaborative filtering: A machine learning perspective: Ph.D. thesis / Master's thesis, University of Toronto. — 2004.

31. Marlin Benjamin, Zemel Richard S. The multiple multiplicative factor model for collaborative filtering // Proceedings of the 21-th International Conference on Machine Learning; Banff, Alberta, Canada. ACM, 2004. - Pp. 73-80.

32. Michael Daniel Billsus. Learning collaborative information filters. 1998.

33. Pavlov Dmitry Y., Pennock David M. A maximum entropy approach to collaborative filtering in dynamic, sparse, high-dimensional domains //In Proceedings of Neural Information Processing Systems. MIT Press, 2002. - Pp. 1441-1448.

34. Scalable collaborative filtering using cluster-based smoothing / Gui rong Xue, Chenxi Lin, Qiang Yang et al. //In Proc. of SIGIR. 2005. - Pp. 114-121.

35. Si Luo, Jin Rong. Flexible mixture model for collaborative filtering // Proceedings of ICML'03.- AAAI Press, 2003.-Pp. 704-711.

36. Srebro Nathan, Rennie Jason D. M., Jaakkola Tommi S. Maximum-margin matrix factorization // Advances in Neural Information Processing Systems 17. — MIT Press, 2005. — Pp. 1329-1336.

37. Two-way latent grouping model for user preference prediction / Eerika Savia, Kai Puolama"ki, Janne Sinkkonen, Samuel Kaski // In Proceedings of the UAI'05. AU AI Press, 2005. - Pp. 518-525.

38. Ungar L., Foster D. Clustering methods for collaborative filtering // Proceedings of the Workshop on Recommendation Systems. — AAAI Press, Menlo Park California, 1998.

39. Vinokourov Alexei, Girolami Mark. A probabilistic framework for the hierarchic organisation and classification of document collections. 2002.