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

Лексин, Василий Алексеевич

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

Лексин, Василий Алексеевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Вероятностные модели в анализе клиентских сред»

Автореферат диссертации на тему "Вероятностные модели в анализе клиентских сред"

005004973

ЛЕКСИН ВАСИЛИЙ АЛЕКСЕЕВИЧ

ВЕРОЯТНОСТНЫЕ МОДЕЛИ В АНАЛИЗЕ КЛИЕНТСКИХ СРЕД

01.01.09 — Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

- 8 ЛЕК 2011

Москва, 2011

005004973

Работа выполнена на кафедре интеллектуальных систем Московского физико-технического института (государственного университета)

Научный руководитель: доктор физико-математических наук

Воронцов Константин Вячеславович

Официальные оппоненты: доктор физико-математических наук

Сенько Олег Валентинович

кандидат технических наук Игнатов Дмитрий Игоревич

Ведущая организация: Учреждение Российской академии наук

Научно-исследовательский институт системных исследований РАН

Защита диссертации состоится « » 2011 г.

в 4!?'-СО на заседании диссертационного совета Д002.017.02 в Учреждении Российской академии наук Вычислительный центр им.А.А.Дородницына РАН по адресу: 119333, г.Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан « » 2011 г.

Учёный секретарь диссертационного совета

Д 002.017.02, д.ф.-м.н., профессор ,^^ В.В.Рязанов

Общая характеристика работы

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

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

Хотя данный подход активно применяется уже более 10 лет,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Краткое содержание работы по главам ВВЕДЕНИЕ

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

ГЛАВА 1. Задачи и методология анализа клиентских сред

1.1. Структура исходных данных. Пусть заданы множество Ы = {1,... ,11} номеров клиентов (субъектов, пользователей) и множество 7Z — {1,..., Д} номеров объектов (ресурсов, товаров, предметов). Записи вида «клиент и взаимодействовал с объектом г» будем называть транзакциями. В зависимости от

предметной области это могут быть покупки, визиты, просмотры и т.д. Пусть каждая транзакция описывается элементом множества У. Протоколом транзакций называется последовательность записей V — {(щ, г¿, yi) : г = 1,..., ND} ÇU х 71 х У, где Nd — длина протокола.

Из протокола транзакций можно получить агрегированные данные в виде матрицы кросс-табуляции размера U х R: F = Ц/ш-Ц, fur = aggr{(u,r,y<) G £>}, где aggr — некоторая операция агрегирования. Например, fur — число использований объекта г клиентом и. Конкретный вид операции агрегирования зависит от характера множества У и прикладной задачи.

1.2. Прикладные задачи, потребности. Перечисляются основные постановки задач в анализе клиентских сред: выдать оценку объекта г для клиента и; выдать клиенту и ранжированный список рекомендуемых объектов; построить по объекту г ранжированный список схожих с ним объектов; выявить тематику интересов клиента и; кластеризовать множество клиентов по интересам; визуализировать кластерную структуру клиентской среды. В результате их формализации возникают задачи прогнозирования незаполненных ячеек fur, оценивания функций сходства К(и,и'), К (г, г'), К(и,г) между клиентами и объектами, формирования сжатых описаний клиентов и объектов в терминах латентных интересов или тем, одновременной кластеризации множеств клиентов и объектов.

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

1.3. Методология анализа клиентских сред. В данном разделе рассматриваются отдельные методы анализа данных и способы их совместного применения, в совокупности образующие методологию анализа клиентских сред. Описываются входные и выходные данные для каждого из методов.

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

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

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

В главе рассматривается метод вероятностного латентного семантического анализа (РЬБА), его модификации и свойства. Исследуются условия сходимости и предлагаются эвристиче-

ские методы улучшения ¿?М-алгоритма для PLSA.

3.1. Восстановление скрытых профилей клиентов и объектов. В разделе описываются две модификации стандартного вероятностного латентного семантического анализа.

Пусть Т = {1,...,Г} — множество номеров тем объектов (интересов клиентов), Т — число тем. Предполагается, что Т «С R и Т < U.

Рассмотрим вероятностное пространство на U х И с функцией распределения р(и,г). В основе PLSA лежит вероятностная модель, которая может быть представлена в трех эквивалентных видах согласно формуле полной вероятности:

p{u,r) =^puptuq(r\t)= (1)

t€T

= ^2qrQtrP{u\t) = (2)

ter

= $><l(r\t)p(u\t), (3)

ter

где ptu = p(t\u) — вероятность интереса клиента и к теме t; Qtr — Çt(t\r) — вероятность того, что объект г относится к теме i; ри = р(и) — априорная вероятность клиента и; qr = q(r) — априорная вероятность объекта г; pt = p(t) — априорная вероятность темы t.

Согласно формуле Байеса, апостериорные вероятности распределения клиентов и объектов по темам имеют вид

p(u\t) = PtuPu/Pt, q{r\t) = qtrqr/Pt-

Вектор pu = (ptu : t G T) назовем профилем клиента и EU, а вектор qr = (qtr ■ t G T) — профилем объекта r ETI.

Задача вероятностного латентного семантического анализа—оценить по транзакционным данным V или по матрице кросс-табуляции F профили клиентов и объектов, используя вероятностную модель (1)-(3).

Априорные вероятности легко оценить по выборке данных:

Pu = 9г — S (и) = Е fur, S (г) = Е fur> 5 = E E fur-

reiz иШ ген и&л

Для нахождения неизвестных параметров ptu, qtr и pt воспользуемся принципом максимума взвешенного правдоподобия:

1= J2 /Mrlnp(u,r)-> max (4)

(u,r)£Ux1l

при ограничениях неотрицательности píu ^ 0, qtr ^ 0 и нормировки X) Ptu = 1, Е Qtr = 1, Е PtuPu = Е QtrQr = Pt- Для ре-

íeT ter uew ге7г

шения данной оптимизационной задачи используется ЕМ-гл-

горитм. Скрытыми переменными в ЕМ-алгоритме являются апостериорные вероятности того, что клиент и, выбирая объект г, интересовался темой t:

, /.. X PtuQtr/Pt

ЩМ= EWPr- (5)

тет

Оптимизационная задача (4) решается аналитически, и её решение выражается через скрытые переменные:

Ptu = -07-т У! /ur^(í|u, г),

4 ' reтг.

Qtr = дТт XI г), (g)

u&A

1 -

Pi =

(■и,г)еихтг

ЕМ-алгоритм состоит из итерационного повторения двух шагов: Е-шага (5) и М-шага (6). В качестве начального приближения задаются параметры ры и параметры р4 вычисляются из условий нормировки. Итерации продолжаются, пока не произойдёт стабилизация значений параметров и/или значений правдоподобия.

Отличие предложенного метода от классического, описанного в работе Хофмана (2003), заключается в том, что здесь на каждом М-шаге непосредственно оцениваются компоненты профилей р^ и а не апостериорные вероятности р(и\г) и д(г|£), через которые профили должны ещё вычисляться по формуле Байеса.

Далее в работе предлагается симметризованный метод, основанный на вероятностных моделях (1) и (2) и представляющий собой двухступенчатый итерационный процесс, в котором профили рщ и <74г оцениваются поочередно, используя ЕМ-алгоритм, подобный описанному выше. При оценке профилей р¿и профили считаются фиксированными, затем, наоборот, фиксируются значения ры и производится оценка профилей дгг. Это позволяет задавать начальные приближения только для профилей клиентов, либо только для профилей объектов.

3.2. Оценка скорости сходимости ЕМ-алгоритма. В данном разделе исследуются вопросы сходимости ЕМ-алгоритма в методе РЬБА.

Пусть Рц и — профили после выполнения М-шага. Для ЕМ-алгоритма в РЬЭА доказаны следующие теоремы:

Теорема 1. На каждой итерации справедливы равенства: dl

Ри - Ри = Рид-, и £ U,

ОРи

А ÖI

qr-qr = Qr —, re П, dqr

где Ри=зЩ (diag(pi„,..., рт) ~ р«рЭ ;

Qr = W) (tiagiqir, • • •, Чтг) ~ qrQr) •

Теорема 2. Матрицы Ри и Qr положительно полуопределены для всех и EU и г £ 71.

Обозначим вектор всех параметров модели на к-ой итерации через в = [pj,..., pjj, q{,..., q^]T и рассмотрим блочно-диагональную матрицу Р = diag{Pi,..., Рц, Qi,..., Qr}. Тогда выражения (7) примут вид

где в' — значения вектора параметров на следующем шаге ЕМ-алгоритма.

Из утверждения теоремы 2 следует, что матрица Р положительно полуопределена, что имеет следующую геометрическую интерпретацию: разность векторов 0' — в на каждом шаге .EM-алгоритма имеет неотрицательную проекцию на градиент правдоподобия. Это показывает тесную связь ЕМ-алгоритма с градиентным методом, когда на каждом шаге движение идет в направлении градиента с некоторым выбранным шагом. Известно, что для градиентного метода гарантирована сходимость к локальному максимуму правдоподобия.

В следующей теореме утверждается, что Е'М-алгоритм имеет асимптотически линейную скорость сходимости.

Теорема 3. Пусть в* — локальный максимум 1(в), в —» в* при к —► оо, где к — номер итерации; в некоторой окрестности в* Гессиан Н(в) = существует и отрицательно определен. Тогда справедлива оценка

где гс = ||£Т(/ + Р(Г)#(Г))|| ^ у/1 + Х2М - 2Хт, Хм и Хт -минимальное и максимальное собственные значения положительно полуопределенной матрицы M = —ЕТР{в*)Н{0*)Е, Е — произвольный ортонормированный базис линейного подпространства

в = U = 9' - в : J^Ptu = o,ueU-,^2qtr = o,ren-,

^ ter teT

u6U rëR

Скорость сходимости критически зависит от степени обусловленности матрицы РН. Если матрица обусловлена плохо, то сходимость алгоритма не гарантируется.

В следующей теореме утверждается, что если все векторы (h(t\u,r): t G Т), для которых fur ф 0, содержат строго по одному ненулевому элементу, то алгоритм имеет суперлинейную скорость сходимости.

Теорема 4. Пусть h(t\u,г) Е {0,1} для всех t £ Т, и еИ и г е 71 в точке в*. Тогда гс = 0.

Для полученного теоретического результата можно провести следующую содержательную интерпретацию: если события

(и, г) выбора объекта г клиентом и всегда обусловлены интересом клиента и к одной и той же теме t G Т, то ЕМ-алгоритм сходится с суперлинейной скоростью.

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

В разделе рассматриваются два эвристических метода улучшения сходимости ЕМ-алгоритма.

1. Метод задания начального приближения профилей по протоколу транзакций, состоящий из следующих шагов.

• Выделяется небольшая подвыборка объектов (метод сем-плирования). Подвыборка может быть либо случайной, либо включать объекты, для которых априори известно, что они относятся к разным темам.

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

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

2. Метод увеличения разреженности профилей и векторов скрытых вероятностей путем обнуления близких к нулю компонент. На каждой ЕМ-итерации отбрасываются (обнуляются) близкие к нулю скрытые переменные h(t\u, г) и компоненты профилей по заданным порогам. Данный подход позволяет существенно сократить объем хранимых в памяти данных.

ГЛАВА 4. Эксперименты

В данной главе описываются вычислительные эксперименты на модельных и на реальных данных. Для оценки работы алгоритма и оптимизации параметров вводятся специальные функционалы качества. На модельных данных функционал качества определяется как среднеквадратичное отклонение (СКО) компонент профилей, полученных на выходе £7М-алгоритма, от компонент модельных профилей, используемых для генерации протокола. На реальных данных функционал качества определяется как число ошибок классификации частично размеченной выборки объектов методом к ближайших соседей (кЫГ\Г). В экспериментах показывается, что предложенные эвристические методы улучшают качество ЕМ-алгоритма и повышают скорость сходимости.

В разделе 4.1 описываются используемые наборы данных. В разделе 4.2 исследуются свойства и способы улучшения сходимости £7М-алгоритма на модельных данных. Для исследования влияния начального приближения профилей на результат ЕМ-алгоритма берется идеальное начальное приближение (модельные профили), с наложенным на него аддитивным шумом заданной амплитуды а. Выяснилось, что скорость и качество сходимости Е'М-алгоритма критически зависят от данного параметра. Для проверки условия суперлинейной сходимости был проведен эксперимент, в котором удалось выяснить, что алгоритм сходится за 4 шага при выполнении условия теоремы и фиксированных параметрах моделирования протокола. Задание начального приближения профилей по протоколу увеличивает скорость сходимости в 3 раза и уменьшает СКО от модельных профилей на 40%. Метод обнуления малых компонент

скрытых переменных и профилей увеличивает скорость сходимости в 2 раза и улучшает качество на 15%.

В разделе 4.3 описаны эксперименты на реальных данных. На данных поисковой машины «Яндекс» показывается, что симметризованный вероятностный латентный семантический анализ увеличивает скорость сходимости в 2 раза и улучшает качество по на 25%. Далее на данных поисковой машины строится полная и локальная карты сходства объектов. На данных о действиях клиентов Интернет-магазина исследуется метод задания начального приближения профилей клиентов и ресурсов по протоколу. В результате качество улучшилось в 3 раза и СКО от модельных профилей уменьшилось на 30% по сравнению со случайным начальным приближением.

В заключении приведены основные результаты работы.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Лексин В. А. Методы улучшения сходимости ЕМ-алгорит-ма в вероятностном латентном семантическом анализе // Математические методы распознавания образов: 15-я Все-рос. конф. Тезисы докл.— 2011. — С. 262-265.

[2] Лексин В. А. Исследование свойств сходимости ЕМ-алгоритма в вероятностном латентном семантическом анализе // ЖВМиМФ. №3 — 2012 (статья принята к публикации).

[3] Лексин В. А. Критерии ветвления в иерархическом вероятностном латентном семантическом анализе // Труды 52-й научной конференции МФТИ, Т. 7, ч. 2. — 2009. - С. 76-79.

[4] Leksin V. A. Symmetrization and overfitting in probabilistic latent semantic analysis // Pattern Recognition and Image Analysis. — Vol. 19, no. 4 — 2009. — Pp. 565-574.

[5] Leksin V. A., Vorontsov К. V. 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.

[6] Лексин В. А. Оценивание сходства пользователей и ресурсов путем выявления скрытых тематических профилей // Труды 50-й научной конф. МФТИ. Часть VII. Том 2. — 2007. - С. 104-106.

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

[8] Лексин В. А., Воронцов К. В. Персонализация контента на основе оценок сходства пользователей и ресурсов сети интернет // Труды 49-й научной конф. МФТИ. Часть VII. Том 2.-2006. - С. 276-277.

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

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

В работах с соавторами лично соискателем сделано следующее:

• разработаны и реализованы алгоритмы обработки логов поисковой машины «Яндекс» [9, 10];

• проведены эксперименты по оцениванию метрики на множестве объектов по точному тесту Фишера [8, 9];

• разработаны методы оценивания качества метрик, проведены эксперименты по восстановлению скрытых профилей и построению карт сходства объектов [7, 5].

Усл.п.л. - 1.0 Заказ №06750 Тираж: ЮОэкз.

Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Лексин, Василий Алексеевич

Введение

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М-алгоритма применяются методы минимизации функций с ограничениями типа равенств. Для оценки сходимости ЕМ-алгоритма используются свойства линейных пространств и операторных норм. При разработке эвристических методов улучшения сходимости применяются методы математической статистики и комбинаторного анализа.

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

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

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

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

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

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

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

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.