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

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

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

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

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

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

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

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

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

Построим по такому контексту правила вида для всех . Тогда такому метаправилу контекста соответствует --- ассоциативное правило контекста . Если величина поддержки и достоверности такого правила в контексте превышают некоторые пороговые значения, то можно считать ассоциативные правила, построенные по контексту , не столь интересными (их можно вывести из описания признаков).

В качестве более крупных метаправил предлагаются следующие две возможности. Во-первых, можно искать правила вида , т.е. правила, в правую часть которых входят все термы, имеющие хотя бы одно однокоренное слово с исходным термом. Во-вторых, правила вида , т.е. правила, термы в правой части которых содержат в своем составе те же основы, что и исходный. Довольно очевидно, что первый тип правил может привести к объединению различных словосочетаний, например ``black jack --- игровой бизнес и ``black coat --- одежда. Такое объединение произошло благодаря наличию общего слова ``black. А второй тип правил относится к более редким зависимостям, например, . Поэтому меры поддержки и достоверности при построении простых метаправил должны служить их мерой пригодности для дальнейшего использования. Предложено также использовать метаправила вида , такие что . Такие правила имеют простую интерпретацию, из словосочетания следует словосочетание множество основ которого вкладывается в множество основ , например, , , а .

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