Вероятностные модели в анализе клиентских сред

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Содержание

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? М-алгоритм, позволяющий, не выходя за рамки той же модели вероятностного латентного семантического анализа, повысить скорость сходимости и качество восстановления скрытых тематических профилей клиентов и объектов.

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

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

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

Показать весь текст

Список литературы

Воронцов К. В. Предварительная обработка данных для решения специального класса задач распознавания // ЖВМ и МФ. — 1995. — Т. 35, № 10. — С. 1565−1575.
Выявление и визуализация метрических структур на множествах пользователей и ресурсов Интернет / К. В. Воронцов, К. В. Рудаков, В. А. Лексин, А. Н. Ефимов // Искусственный Интеллект. 2006. — С. 285−288.
Лексин В. А. Персонализация контента на основе оценок сходства пользователей и ресурсов сети интернет // Труды 49-й научной конференции МФТИ. Т. УН-2. — 2006. — С. 276−277.
Лексин В. А. Оценивание сходства пользователей и ресурсов путем выявления скрытых тематических профилей // Труды 50-й научной конференции МФТИ. Т. УН-2. — 2007. — С. 104 106.
Лексин В. А., Воронцов К. В. Анализ клиентских сред: выявление скрытых профилей и оценивание сходства клиентов и ресурсов // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. С. 488−491.
О метрических структурах на множествах пользователей и ресурсов интернет / К. В. Воронцов, К. В. Рудаков, В. А. Лексин, А. Н. Ефимов // Интеллектуализация обработки информации: Тезисы докл. Симферополь. — 2006. — С. 46−48.
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.
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.
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.
Brand Matthew. Fast online svd revisions for lightweight recommender systems // SIAM International Conference on Data Mining. 2003.
Canny John. Collaborative filtering with privacy via factor analysis //In Proceedings of the 25th annual international ACM
SIGIR conference on Research and development in information retrieval. ACM Press, 2002. — Pp. 238−245.
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.
Goldberg Ken, Roeder Theresa, Gupta Dhruv, Perkins Chris. Eigentaste: A constant time collaborative filtering algorithm. — 2000.
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.
Generative models for cold-start recommendations / Andrew I. Schein, Alexandrin Popescul, Lyle H. Ungar,
David M. Pennock // the SIGIR’Ol Workshop on Recommender Systems. 2001.
George Thomas. A scalable collaborative filtering framework based on co-clustering // Fifth IEEE International Conference on Data Mining. 2005. — Pp. 625−628.
Grcar M. User profiling: Collaborative filtering // SIKDD 2004 at multiconference IS 12−15 Oct 2004, Ljubljana, Slovenia. — 2004.
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.
Gunawardana Asela, Byrne William. Convergence theorems for generalized alternating minimization procedures // J. Mach. Learn. Res. 2005. — Vol. 6. — Pp. 2049−2073.
Hofmann Thomas. Latent semantic models for collaborative filtering // ACM Transactions on Information Systems. — 2004.— Vol. 22, no. l.-Pp. 89−115.
Hofmann Thomas, Puzicha Jan. Latent class models for collaborative filtering // International Joint Conference in Artificial Intelligence. 1999.
Indexing by latent semantic analysis / Scott Deerwester, Susan T. Dumais, George W. Furnas et al. // Journal of the
American Society for Information Science. — 1990. — Vol. 41. — Pp. 391−407.
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. 285 295.
Jin R, Si Luo, Zhai Chengxiang. A study of mixture models for collaborative filtering // Information Retrieval. — 2006. — Vol. 9, no. 3. Pp. 357−382.
Leksin V. A. Symmetrization and overfitting in probabilistic latent semantic analysis // Pattern Recognition and Image Analysis. — 2009. Vol. Volume 19, Number 4 / Декабрь 2009 г. — Pp. 565 574.
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.
Marlin B. Collaborative filtering: A machine learning perspective: Ph.D. thesis / Master’s thesis, University of Toronto. — 2004.
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.
Michael Daniel Billsus. Learning collaborative information filters. 1998.
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.
Scalable collaborative filtering using cluster-based smoothing / Gui rong Xue, Chenxi Lin, Qiang Yang et al. //In Proc. of SIGIR. 2005. — Pp. 114−121.
Si Luo, Jin Rong. Flexible mixture model for collaborative filtering // Proceedings of ICML'03.- AAAI Press, 2003.-Pp. 704−711.
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.
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.
Ungar L., Foster D. Clustering methods for collaborative filtering // Proceedings of the Workshop on Recommendation Systems. — AAAI Press, Menlo Park California, 1998.
Vinokourov Alexei, Girolami Mark. A probabilistic framework for the hierarchic organisation and classification of document collections. 2002.

Заполнить форму текущей работой