Формирование бикластеров и рекомендаций для рекомендательной системы Интернет-рекламы
Материал из MachineLearning.
| Строка 1: | Строка 1: | ||
| - | + | Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ'' и ``Бегун''. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма <tex>F</tex> приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила <tex>F</tex> и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи. | |
| - | Исходный массив данных описывается формальным контекстом <tex>\K_{FT}=(F,T,I_{FT})<tex>, <tex>F<tex> (от firms) --- множество компаний-рекламодателей, а <tex>T<tex> (от term) --- множество рекламных словосочетаний, <tex>I<tex> --- отношение инцидентности, показывающее, что фирма <tex>f \in F<tex> купила словосочетание <tex>t \in T<tex> тогда и только тогда, когда <tex>fIt<tex>. | + | Исходный массив данных описывается формальным контекстом <tex>\K_{FT}=(F,T,I_{FT})</tex>, <tex>F</tex> (от firms) --- множество компаний-рекламодателей, а <tex>T</tex> (от term) --- множество рекламных словосочетаний, <tex>I</tex> --- отношение инцидентности, показывающее, что фирма <tex>f \in F</tex> купила словосочетание <tex>t \in T</tex> тогда и только тогда, когда <tex>fIt</tex>. |
Для решения задачи последовательно применялись следующие подходы: | Для решения задачи последовательно применялись следующие подходы: | ||
| Строка 15: | Строка 15: | ||
Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга. | Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга. | ||
| - | Пусть <tex>t<tex> - некое рекламное словосочетание. Представим его в виде множества слов его образующих <tex>t=\{w_1, w_2, \ldots, w_n\}<tex>. Основу слова <tex>w_i<tex> обозначим через <tex>s_i=stem(w_i)<tex>, тогда множество основ словосочетания <tex>t<tex> обозначим через <tex>Stem(t)=\bigcup\limits_i stem(w_i)<tex>. Построим формальный контекст <tex>\K_{TS}=(T, S, I_{TS})<tex>, где <tex>T<tex> --- множество всех словосочетаний, а <tex>S<tex> --- множество основ всех словосочетаний из <tex>T<tex>, т.е. <tex>S=\bigcup\limits_i Stem(t_i)<tex>. Тогда <tex>tIs<tex> будет означать, что во множество основ словосочетания <tex>t<tex> входит основа <tex>s<tex>. | + | Пусть <tex>t</tex> - некое рекламное словосочетание. Представим его в виде множества слов его образующих <tex>t=\{w_1, w_2, \ldots, w_n\}</tex>. Основу слова <tex>w_i</tex> обозначим через <tex>s_i=stem(w_i)</tex>, тогда множество основ словосочетания <tex>t</tex> обозначим через <tex>Stem(t)=\bigcup\limits_i stem(w_i)</tex>. Построим формальный контекст <tex>\K_{TS}=(T, S, I_{TS})</tex>, где <tex>T</tex> --- множество всех словосочетаний, а <tex>S</tex> --- множество основ всех словосочетаний из <tex>T</tex>, т.е. <tex>S=\bigcup\limits_i Stem(t_i)</tex>. Тогда <tex>tIs</tex> будет означать, что во множество основ словосочетания <tex>t</tex> входит основа <tex>s</tex>. |
| - | Построим по такому контексту правила вида <tex>t \rightarrow s_i^{I_{TS}}<tex> для всех <tex>t \in T<tex>. Тогда такому метаправилу контекста <tex>\K_{TS}<tex> соответствует <tex>t \xrightarrow[]{FT} s_i^{I_{TS}}<tex> --- ассоциативное правило контекста <tex>\K_{FT}<tex>. Если величина поддержки и достоверности такого правила в контексте <tex>\K_{FT}<tex> превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту <tex>\K_{FT}<tex>, не столь интересными (их можно вывести из описания признаков). | + | Построим по такому контексту правила вида <tex>t \rightarrow s_i^{I_{TS}}</tex> для всех <tex>t \in T</tex>. Тогда такому метаправилу контекста <tex>\K_{TS}</tex> соответствует <tex>t \xrightarrow[]{FT} s_i^{I_{TS}}</tex> --- ассоциативное правило контекста <tex>\K_{FT}</tex>. Если величина поддержки и достоверности такого правила в контексте <tex>\K_{FT}</tex> превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту <tex>\K_{FT}</tex>, не столь интересными (их можно вывести из описания признаков). |
| - | В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида <tex>t \xrightarrow[]{FT} \bigcup\limits_i s_i^{I_{TS}}<tex>, т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида <tex>t \xrightarrow[]{FT} (\bigcup\limits_i s_i)^{I_{TS}}<tex>, т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack'' --- игровой бизнес и ``black coat'' --- одежда. Такое объединение произошло благодаря наличию общего слова ``black''. А второй тип правил относится к более редким зависимостям, например, <tex>\{black~ jack\} \rightarrow \{black~jack~game~online\}<tex>. Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида <tex>t_1 \xrightarrow[]{FT} t_2<tex>, такие что <tex>t_2^{I_{TS}} \subseteq t_1^{I_{TS}}<tex>. Такие правила имеют простую интерпретацию, из словосочетания <tex>t_2<tex> следует словосочетание множество основ которого вкладывается в множество основ <tex>t_1<tex>, например, <tex>\{ink \ jet\}\rightarrow\{ink\}<tex>, <tex>supp=14<tex>, а <tex>conf= 0,7<tex>. | + | В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида <tex>t \xrightarrow[]{FT} \bigcup\limits_i s_i^{I_{TS}}</tex>, т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида <tex>t \xrightarrow[]{FT} (\bigcup\limits_i s_i)^{I_{TS}}</tex>, т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack'' --- игровой бизнес и ``black coat'' --- одежда. Такое объединение произошло благодаря наличию общего слова ``black''. А второй тип правил относится к более редким зависимостям, например, <tex>\{black~ jack\} \rightarrow \{black~jack~game~online\}</tex>. Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида <tex>t_1 \xrightarrow[]{FT} t_2</tex>, такие что <tex>t_2^{I_{TS}} \subseteq t_1^{I_{TS}}</tex>. Такие правила имеют простую интерпретацию, из словосочетания <tex>t_2</tex> следует словосочетание множество основ которого вкладывается в множество основ <tex>t_1</tex>, например, <tex>\{ink \ jet\}\rightarrow\{ink\}</tex>, <tex>supp=14</tex>, а <tex>conf= 0,7</tex>. |
Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль. | Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль. | ||
Версия 22:24, 4 ноября 2010
Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ и ``Бегун. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила
и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.
Исходный массив данных описывается формальным контекстом ,
(от firms) --- множество компаний-рекламодателей, а
(от term) --- множество рекламных словосочетаний,
--- отношение инцидентности, показывающее, что фирма
купила словосочетание
тогда и только тогда, когда
.
Для решения задачи последовательно применялись следующие подходы:
- отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;
- поиск ассоциативных правил для построения рекомендаций;
- построение ассоциативных метаправил с помощью морфологического анализа;
- построение ассоциативных метаправил с помощью онтологий (тематического каталога).
Краткое описание модели формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа приведено ниже. Рассмотрим в качестве дополнительного знания имеющееся признаковое пространство, а именно тот факт, что каждый признак является словом или словосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленные экспертами, но ввиду большого количества рекламных слов (несколько тысяч) наполнение каталога ``вручную является сложной задачей.
Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга.
Пусть - некое рекламное словосочетание. Представим его в виде множества слов его образующих
. Основу слова
обозначим через
, тогда множество основ словосочетания
обозначим через
. Построим формальный контекст
, где
--- множество всех словосочетаний, а
--- множество основ всех словосочетаний из
, т.е.
. Тогда
будет означать, что во множество основ словосочетания
входит основа
.
Построим по такому контексту правила вида для всех
. Тогда такому метаправилу контекста
соответствует
--- ассоциативное правило контекста
. Если величина поддержки и достоверности такого правила в контексте
превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту
, не столь интересными (их можно вывести из описания признаков).
В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида , т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида
, т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack --- игровой бизнес и ``black coat --- одежда. Такое объединение произошло благодаря наличию общего слова ``black. А второй тип правил относится к более редким зависимостям, например,
. Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида
, такие что
. Такие правила имеют простую интерпретацию, из словосочетания
следует словосочетание множество основ которого вкладывается в множество основ
, например,
,
, а
.
Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль.
