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

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

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

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

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

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

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

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

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

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

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

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

Публикации

• D.I.Ignatov, S.O. Kuznetsov. Concept-based Recommendations for Internet Advertisement// In proceedings of The Sixth International Conference Concept Lattices and Their Applications (CLA’08), Olomouc, Czech Republic, 2008 ([1])

• Игнатов Д. И., Кузнецов С.О Методы разработки данных (Data Mining) для рекомендательной системы Интернет-рекламы // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием (КИИ-2008, 28 сентября — 3 октября 2008 г., г. Дубна, Россия): Труды конференции. Т.2. — М.: Ленанд, 2008. — 392 с.