Формирование бикластеров и рекомендаций для рекомендательной системы Интернет-рекламы
Материал из MachineLearning.
Строка 1: | Строка 1: | ||
Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ'' и ``Бегун''. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма <tex>F</tex> приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила <tex>F</tex> и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи. | Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ'' и ``Бегун''. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма <tex>F</tex> приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила <tex>F</tex> и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи. | ||
- | Исходный массив данных описывается формальным контекстом <tex>\ | + | Исходный массив данных описывается формальным контекстом <tex>\mathbb{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>\ | + | Пусть <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>\mathbb{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>\ | + | Построим по такому контексту правила вида <tex>t \rightarrow s_i^{I_{TS}}</tex> для всех <tex>t \in T</tex>. Тогда такому метаправилу контекста <tex>\mathbb{K}_{TS}</tex> соответствует <tex>t \xrightarrow[]{FT} s_i^{I_{TS}}</tex> --- ассоциативное правило контекста <tex>\mathbb{K}_{FT}</tex>. Если величина поддержки и достоверности такого правила в контексте <tex>\mathbb{K}_{FT}</tex> превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту <tex>\mathbb{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:25, 4 ноября 2010
Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ и ``Бегун. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.
Исходный массив данных описывается формальным контекстом , (от firms) --- множество компаний-рекламодателей, а (от term) --- множество рекламных словосочетаний, --- отношение инцидентности, показывающее, что фирма купила словосочетание тогда и только тогда, когда .
Для решения задачи последовательно применялись следующие подходы:
- отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;
- поиск ассоциативных правил для построения рекомендаций;
- построение ассоциативных метаправил с помощью морфологического анализа;
- построение ассоциативных метаправил с помощью онтологий (тематического каталога).
Краткое описание модели формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа приведено ниже. Рассмотрим в качестве дополнительного знания имеющееся признаковое пространство, а именно тот факт, что каждый признак является словом или словосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленные экспертами, но ввиду большого количества рекламных слов (несколько тысяч) наполнение каталога ``вручную является сложной задачей.
Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга.
Пусть - некое рекламное словосочетание. Представим его в виде множества слов его образующих . Основу слова обозначим через , тогда множество основ словосочетания обозначим через . Построим формальный контекст , где --- множество всех словосочетаний, а --- множество основ всех словосочетаний из , т.е. . Тогда будет означать, что во множество основ словосочетания входит основа .
Построим по такому контексту правила вида для всех . Тогда такому метаправилу контекста соответствует --- ассоциативное правило контекста . Если величина поддержки и достоверности такого правила в контексте превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту , не столь интересными (их можно вывести из описания признаков).
В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида , т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида , т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack --- игровой бизнес и ``black coat --- одежда. Такое объединение произошло благодаря наличию общего слова ``black. А второй тип правил относится к более редким зависимостям, например, . Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида , такие что . Такие правила имеют простую интерпретацию, из словосочетания следует словосочетание множество основ которого вкладывается в множество основ , например, , , а .
Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль.