Формирование бикластеров и рекомендаций для рекомендательной системы Интернет-рекламы

Материал из MachineLearning.

Перейти к: навигация, поиск

Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ и ``Бегун. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма F приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила F и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.

Исходный массив данных описывается формальным контекстом \mathbb{K}_{FT}=(F,T,I_{FT}), F (от firms) --- множество компаний-рекламодателей, а T (от term) --- множество рекламных словосочетаний, I --- отношение инцидентности, показывающее, что фирма f \in F купила словосочетание t \in T тогда и только тогда, когда fIt.

Для решения задачи последовательно применялись следующие подходы:

  • отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;
  • поиск ассоциативных правил для построения рекомендаций;
  • построение ассоциативных метаправил с помощью морфологического анализа;
  • построение ассоциативных метаправил с помощью онтологий (тематического каталога).


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

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

Пусть t - некое рекламное словосочетание. Представим его в виде множества слов его образующих t=\{w_1, w_2, \ldots, w_n\}. Основу слова w_i обозначим через s_i=stem(w_i), тогда множество основ словосочетания t обозначим через Stem(t)=\bigcup\limits_i stem(w_i). Построим формальный контекст \mathbb{K}_{TS}=(T, S, I_{TS}), где T --- множество всех словосочетаний, а S --- множество основ всех словосочетаний из T, т.е. S=\bigcup\limits_i Stem(t_i). Тогда tIs будет означать, что во множество основ словосочетания t входит основа s.

Построим по такому контексту правила вида t \rightarrow s_i^{I_{TS}} для всех t \in T. Тогда такому метаправилу контекста \mathbb{K}_{TS} соответствует t \xrightarrow[]{FT} s_i^{I_{TS}} --- ассоциативное правило контекста \mathbb{K}_{FT}. Если величина поддержки и достоверности такого правила в контексте \mathbb{K}_{FT} превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту \mathbb{K}_{FT}, не столь интересными (их можно вывести из описания признаков).

В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида t \xrightarrow[]{FT} \bigcup\limits_i s_i^{I_{TS}}, т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида t \xrightarrow[]{FT} (\bigcup\limits_i s_i)^{I_{TS}}, т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack --- игровой бизнес и ``black coat --- одежда. Такое объединение произошло благодаря наличию общего слова ``black. А второй тип правил относится к более редким зависимостям, например, \{black~ jack\} \rightarrow \{black~jack~game~online\}. Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида t_1 \xrightarrow[]{FT} t_2, такие что t_2^{I_{TS}} \subseteq t_1^{I_{TS}}. Такие правила имеют простую интерпретацию, из словосочетания t_2 следует словосочетание множество основ которого вкладывается в множество основ t_1, например, \{ink \ jet\}\rightarrow\{ink\}, supp=14, а conf= 0,7.

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

machine 01:28, 5 ноября 2010 (MSK)