авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

На правах рукописи

ЛЕКСИН ВАСИЛИЙ АЛЕКСЕЕВИЧ ВЕРОЯТНОСТНЫЕ МОДЕЛИ В АНАЛИЗЕ КЛИЕНТСКИХ СРЕД 01.01.09 Дискретная математика и математическая кибернетика

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

Москва, 2011

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

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

Официальные оппоненты: доктор физико-математических наук Сенько Олег Валентинович кандидат технических наук Игнатов Дмитрий Игоревич

Ведущая организация: Учреждение Российской академии наук Научно-исследовательский институт системных исследований РАН

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

в на заседании диссертационного совета Д 002.017. в Учреждении Российской академии наук Вычислительный центр им. А. А. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

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

Автореферат разослан 2011 г.

Учёный секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор В. В. Рязанов

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

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

В работе исследуются методы вероятностного латентного семантического анализа (PLSA), основанные на байесовской вероятностной модели данных. Для идентификации парамет ров модели по выборке транзакций применяется итерационный EM -алгоритм, максимизирующий функционал правдоподобия.

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

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

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

Научная новизна. Впервые получены оценки скорости схо димости EM -алгоритма в PLSA, установлены условия супер линейной сходимости, выявлены основные параметры, воздей ствуя на которые можно улучшить сходимость EM -алгоритма.

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

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

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

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

.

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



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

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





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

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

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

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

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

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

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

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

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

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

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

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

ГЛАВА 1. Задачи и методология анализа кли ентских сред 1.1. Структура исходных данных. Пусть заданы множе ство U = {1,..., U } номеров клиентов (субъектов, пользовате лей) и множество R = {1,..., R} номеров объектов (ресурсов, товаров, предметов). Записи вида клиент u взаимодействовал с объектом r будем называть транзакциями. В зависимости от предметной области это могут быть покупки, визиты, просмот ры и т. д. Пусть каждая транзакция описывается элементом множества Y. Протоколом транзакций называется последова тельность записей D = {(ui, ri, yi ) : i = 1,..., ND } U R Y, где ND длина протокола.

Из протокола транзакций можно получить агрегирован ные данные в виде матрицы кросс-табуляции размера U R:

F = fur, fur = aggr (u, r, yi ) D, где aggr некоторая опе рация агрегирования. Например, fur число использований объекта r клиентом u. Конкретный вид операции агрегирова ния зависит от характера множества Y и прикладной задачи.

1.2. Прикладные задачи, потребности. Перечисляются основные постановки задач в анализе клиентских сред: выдать оценку объекта r для клиента u;

выдать клиенту u ранжирован ный список рекомендуемых объектов;

построить по объекту r ранжированный список схожих с ним объектов;

выявить тема тику интересов клиента u;

кластеризовать множество клиентов по интересам;

визуализировать кластерную структуру клиент ской среды. В результате их формализации возникают задачи прогнозирования незаполненных ячеек fur, оценивания функ ций сходства K(u, u ), K(r, r ), K(u, r) между клиентами и объ ектами, формирования сжатых описаний клиентов и объектов в терминах латентных интересов или тем, одновременной кла стеризации множеств клиентов и объектов.

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

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

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

ГЛАВА 3. Вероятностный латентный семанти ческий анализ В главе рассматривается метод вероятностного латентного семантического анализа (PLSA), его модификации и свойства.

Исследуются условия сходимости и предлагаются эвристиче ские методы улучшения EM -алгоритма для PLSA.

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

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

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

p(u, r) = pu ptu q(r|t) = (1) tT = qr qtr p(u|t) = (2) tT = pt q(r|t)p(u|t), (3) tT где ptu = p(t|u) вероятность интереса клиента u к теме t;

qtr = q(t|r) вероятность того, что объект r относится к те ме t;

pu = p(u) априорная вероятность клиента u;

qr = q(r) априорная вероятность объекта r;

pt = p(t) априорная веро ятность темы t.

Согласно формуле Байеса, апостериорные вероятности рас пределения клиентов и объектов по темам имеют вид p(u|t) = ptu pu /pt, q(r|t) = qtr qr /pt.

Вектор pu = (ptu : t T ) назовем профилем клиента u U, а вектор qr = (qtr : t T ) профилем объекта r R.

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

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

pu = S(u), qr = S(r), S(u) = fur, S(r) = fur, S = fur.

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

fur ln p(u, r) l= max (4) {ptu,qtr,pt } (u,r)UR при ограничениях неотрицательности ptu 0, qtr 0 и норми ptu = 1, qtr = 1, ptu pu = qtr qr = pt. Для ре ровки tT tT uU rR шения данной оптимизационной задачи используется EM -ал горитм. Скрытыми переменными в EM -алгоритме являются апостериорные вероятности того, что клиент u, выбирая объ ект r, интересовался темой t:

ptu qtr /pt h(t|u, r) =. (5) p u q r /p T Оптимизационная задача (4) решается аналитически, и её ре шение выражается через скрытые переменные:

ptu = fur h(t|u, r), S(u) rR qtr = fur h(t|u, r), (6) S(r) uU pt = fur h(t|u, r).

S (u,r)UR EM-алгоритм состоит из итерационного повторения двух ша гов: Е-шага (5) и M-шага (6). В качестве начального приближе ния задаются параметры ptu и qtr, параметры pt вычисляют ся из условий нормировки. Итерации продолжаются, пока не произойдёт стабилизация значений параметров и/или значений правдоподобия.

Отличие предложенного метода от классического, описан ного в работе Хофмана (2003), заключается в том, что здесь на каждом M -шаге непосредственно оцениваются компонен ты профилей ptu и qtr, а не апостериорные вероятности p(u|r) и q(r|t), через которые профили должны ещё вычисляться по формуле Байеса.

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

3.2. Оценка скорости сходимости EM -алгоритма. В дан ном разделе исследуются вопросы сходимости EM -алгоритма в методе PLSA.

Пусть pu и qr профили после выполнения M -шага. Для EM -алгоритма в PLSA доказаны следующие теоремы:

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

l pu pu = P u, u U, pu (7) l qr qr = Qr, r R, qr diag(p1u,..., pT u ) pu pT ;

Pu = где u S(u) diag(q1r,..., qT r ) qr qT.

Qr = r S(r) Теорема 2. Матрицы Pu и Qr положительно полуопределены для всех u U и r R.

Обозначим вектор всех параметров модели на k-ой итера ции через = [pT,..., pT, qT,..., qT ]T и рассмотрим блочно 1 U R диагональную матрицу P = diag{P1,..., PU, Q1,..., QR }. Тогда выражения (7) примут вид l =P, где значения вектора параметров на следующем шаге EM алгоритма.

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

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

Теорема 3. Пусть локальный максимум l(), при k, где k номер итерации;

в некоторой окрест 2 l() ности Гессиан H() = T существует и отрицательно определен. Тогда справедлива оценка lim rc, k где rc = E T I + P ( )H( ) 1 + 2 2m, M и m M минимальное и максимальное собственные значения положи тельно полуопределенной матрицы M = E T P ( )H( )E, E произвольный ортонормированный базис линейного под пространства = : ptu = 0, u U;

qtr = 0, r R;

= tT tT qr qtr, t T pu ptu = ;

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

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

Теорема 4. Пусть h(t|u, r) {0, 1} для всех t T, u U и r R в точке. Тогда rc = 0.

Для полученного теоретического результата можно прове сти следующую содержательную интерпретацию: если события (u, r) выбора объекта r клиентом u всегда обусловлены интере сом клиента u к одной и той же теме t T, то EM -алгоритм сходится с суперлинейной скоростью.

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

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

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

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

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

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

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

ГЛАВА 4. Эксперименты В данной главе описываются вычислительные эксперименты на модельных и на реальных данных. Для оценки работы алго ритма и оптимизации параметров вводятся специальные функ ционалы качества. На модельных данных функционал качества определяется как среднеквадратичное отклонение (СКО) ком понент профилей, полученных на выходе EM -алгоритма, от компонент модельных профилей, используемых для генерации протокола. На реальных данных функционал качества опреде ляется как число ошибок классификации частично размечен ной выборки объектов методом k ближайших соседей (kNN).

В экспериментах показывается, что предложенные эвристиче ские методы улучшают качество EM -алгоритма и повышают скорость сходимости.

В разделе 4.1 описываются используемые наборы данных.

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

В разделе 4.3 описаны эксперименты на реальных данных.

На данных поисковой машины Яндекс показывается, что симметризованный вероятностный латентный семантический анализ увеличивает скорость сходимости в 2 раза и улучша ет качество по kNN на 25%. Далее на данных поисковой ма шины строится полная и локальная карты сходства объектов.

На данных о действиях клиентов Интернет-магазина исследует ся метод задания начального приближения профилей клиентов и ресурсов по протоколу. В результате качество улучшилось в 3 раза и СКО от модельных профилей уменьшилось на 30% по сравнению со случайным начальным приближением.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ [1] Лексин В. А. Методы улучшения сходимости EM-алгорит ма в вероятностном латентном семантическом анализе // Математические методы распознавания образов: 15-я Все рос. конф. Тезисы докл. 2011. С. 262–265.

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

[3] Leksin V. A. Symmetrization and overtting in probabilistic latent semantic analysis // Pattern Recognition and Image Analysis. Vol. 19, no. 2009. Pp. 565–574.

[4] Leksin V. A., Vorontsov K. V. The overtting 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.

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

2007. С. 104–106.

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

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

Том 2. 2006. С. 276–277.

[8] Воронцов К. В., Рудаков К. В., Лексин В. А., Ефимов А. Н.

Выявление и визуализация метрических структур на мно жествах пользователей и ресурсов Интернет // Научно теоретический журнал Искусственный интеллект. №2.

2006. С. 285–288.

[9] Воронцов К. В., Рудаков К. В., Лексин В. А., Ефимов А. Н.

О метрических структурах на множествах пользователей и ресурсов Интернет // Интеллектуализация обработки информации: междунар. конф. Тезисы докл. 2006.

С. 46–48.

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

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

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

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



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.