Формирование бикластеров и рекомендаций для рекомендательной системы Интернет-рекламы
Материал из MachineLearning.
Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ и ``Бегун. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила
и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.
Исходный массив данных описывается формальным контекстом ,
(от firms) --- множество компаний-рекламодателей, а
(от term) --- множество рекламных словосочетаний,
--- отношение инцидентности, показывающее, что фирма
купила словосочетание
тогда и только тогда, когда
.
Для решения задачи последовательно применялись следующие подходы:
- отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;
- поиск ассоциативных правил для построения рекомендаций;
- построение ассоциативных метаправил с помощью морфологического анализа;
- построение ассоциативных метаправил с помощью онтологий (тематического каталога).
Краткое описание модели формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа приведено ниже. Рассмотрим в качестве дополнительного знания имеющееся признаковое пространство, а именно тот факт, что каждый признак является словом или словосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленные экспертами, но ввиду большого количества рекламных слов (несколько тысяч) наполнение каталога ``вручную является сложной задачей.
Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга.
Пусть - некое рекламное словосочетание. Представим его в виде множества слов его образующих
. Основу слова
обозначим через
, тогда множество основ словосочетания
обозначим через
. Построим формальный контекст
, где
--- множество всех словосочетаний, а
--- множество основ всех словосочетаний из
, т.е.
. Тогда
будет означать, что во множество основ словосочетания
входит основа
.
Построим по такому контексту правила вида для всех
. Тогда такому метаправилу контекста
соответствует
--- ассоциативное правило контекста
. Если величина поддержки и достоверности такого правила в контексте
превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту
, не столь интересными (их можно вывести из описания признаков).
В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида , т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида
, т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack --- игровой бизнес и ``black coat --- одежда. Такое объединение произошло благодаря наличию общего слова ``black. А второй тип правил относится к более редким зависимостям, например,
. Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида
, такие что
. Такие правила имеют простую интерпретацию, из словосочетания
следует словосочетание множество основ которого вкладывается в множество основ
, например,
,
, а
.
Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль.
machine 01:28, 5 ноября 2010 (MSK)