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

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

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

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

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

\begin{enumerate}

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

\end{enumerate}

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

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

Пусть $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)$. Построим формальный контекст $\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$. Тогда такому метаправилу контекста $\K_{TS}$ соответствует $t \xrightarrow[]{FT} s_i^{I_{TS}}$ --- ассоциативное правило контекста $\K_{FT}$. Если величина поддержки и достоверности такого правила в контексте $\K_{FT}$ превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту $\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-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль.