Материал из MachineLearning.
Одна из разновидностей электронной коммерции --- контекстная Интернет-реклама. Сейчас на рынке таких услуг крупными игроками являются поисковые системы, немалую часть прибыли которых составляет так называемая поисковая реклама. Для России репрезентативными примерами служат рекламные Интернет-сервисы ``Яндекс.Директ и ``Бегун. Пользователю предлагается релевантная (с точки зрения поисковой системы) его поисковому запросу реклама. В отличие от задачи предоставления пользователю наиболее интересной ему поисковой рекламы, наша задача --- выявление рекламных слов, которые могут быть интересны рекламодателю. Предположим, что некая фирма ![F<tex> приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила <tex>F<tex> и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.
</p><p>Исходный массив данных описывается формальным контекстом <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>.
</p><p>Для решения задачи последовательно применялись следующие подходы:
</p>
<ul><li> отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;
</li><li> поиск ассоциативных правил для построения рекомендаций;
</li><li> построение ассоциативных метаправил с помощью морфологического анализа;
</li><li> построение ассоциативных метаправил с помощью онтологий (тематического каталога).
</li></ul>
<p><br />
Краткое описание модели формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа приведено ниже. Рассмотрим в качестве дополнительного знания имеющееся признаковое пространство, а именно тот факт, что каждый признак является словом или словосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленные экспертами, но ввиду большого количества рекламных слов (несколько тысяч) наполнение каталога ``вручную'' является сложной задачей.
</p><p>Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга.
</p><p>Пусть <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>.
</p><p>Построим по такому контексту правила вида <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>, не столь интересными (их можно вывести из описания признаков).
</p><p>В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида <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>.
</p><p>Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль.](../mimetex/?F<tex> приобрела ряд рекламных слов, которые описывают предоставляемые услуги. Как правило, на рынке уже существуют компании-конкуренты, поэтому вполне разумно было бы выяснить, какие рекламные слова приобрели они. Далее можно сравнить эти множества слов с теми, что купила <tex>F<tex> и, исходя из частоты таких покупок, отобрать наиболее для нее интересные из неприобретенных. Такой механизм стимулирует продажи рекламы и позволяет устраивать своеобразный аукцион по определению цены того или иного рекламного словосочетания. Решение подобной задачи методами спектральной кластеризации описано в работах Жукова~Л.Е. Цель наших экспериментов не только расширить список методов бикластеризации пригодных для решения этой задачи, но и улучшить качество предложенных рекомендаций. Ниже приведено описание математической модели задачи.
</pre>
<p>Исходный массив данных описывается формальным контекстом <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>.
</p><p>Для решения задачи последовательно применялись следующие подходы:
</p>
<ul><li> отбор по размеру объема и содержания понятий и объектно-признаковую бикластеризацию для выявления крупных рынков средствами АФП;
</li><li> поиск ассоциативных правил для построения рекомендаций;
</li><li> построение ассоциативных метаправил с помощью морфологического анализа;
</li><li> построение ассоциативных метаправил с помощью онтологий (тематического каталога).
</li></ul>
<p><br />
Краткое описание модели формирования рекомендаций на основе ассоциативных метаправил с помощью морфологического анализа приведено ниже. Рассмотрим в качестве дополнительного знания имеющееся признаковое пространство, а именно тот факт, что каждый признак является словом или словосочетанием. Вполне очевидно, что синонимичные словосочетания принадлежат к одному сегменту рынка. Конечно, в штате компаний, занимающихся контекстной рекламой, существуют тематические каталоги, составленные экспертами, но ввиду большого количества рекламных слов (несколько тысяч) наполнение каталога ``вручную'' является сложной задачей.
</p><p>Для построения тематического каталога рекламных словосочетаний могут потребоваться словари синонимов, а учитывая тот факт, что такие словосочетания не всегда слова или сочетания двух слов, такие словари редки. Поэтому в качестве первого приближения для решения такой задачи можно использовать стемминг, или выделение основы слова. Опишем последовательность действий при извлечении знаний с помощью стемминга.
</p><p>Пусть <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>.
</p><p>Построим по такому контексту правила вида <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>, не столь интересными (их можно вывести из описания признаков).
</p><p>В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида <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>.
</p><p>Для указанных выше задач автором предложены методики оценки качества поиска, основанные на мерах качества, применяемых в информационном поиске (точность, полнота, F-мера), разработке данных (поддержка) в сочетании с техниками оценки качества из машинного обучения, такими как скользящий контроль.)
