Строительные исследования
страница - 0
Алгоритм автоматического создания фильтров для сортировки входящей почты
Свердлов М.И.( Mike@globalinfactory.com), Андриенко П.В.
Санкт-Петербургский Государственный университет аэрокосмического приборостроения
Автоматизация обработки потока электронной корреспонденции рекламной компании является важным элементом технологии Friendly Advertising (Дружественная реклама). Такая автоматизация устраняет узкое место в применении самой технологии Friendly Advertising, а именно позволяет эффективно обрабатывать большие потоки ответной реакции потребителей - их писем. Как правило, при этом к большому количеству получателей приходит одно и то же рекламное сообщение и некоторые из получателей на него отвечают отправителю. Таким образом, ставится задача обработки ответных сообщений от получателей рекламы.
В настоящее время распространен подход, когда входящие ответные сообщения просто не обрабатываются, или обрабатываются простейшими фильтрами в целях удаления адресов людей, не желающих получать рекламу (общепринятая форма запроса на удаление из списка рассылки: «REMOVE» в поле Тема письма). Тем не менее, обработка хотя бы первичных откликов от получателей позволяет существенно повысить эффективность такой рекламы, а также позволяет снизить возможное раздражение получателей рекламы. Причиной, которая приводит к отказу от обработки откликов, является отсутствие эффективного алгоритма автоматизированной обработки. Обработка же вручную, как правило, экономически нерентабельна.
Однако, практика авторов работы в данной сфере и известный авторам опыт коллег показывает, что на любую рекламную кампанию, включающую рассылку сообщения с одинаковым текстом, возможно ограниченное количество категорий откликов, часто до 10. Лишь незначительный процент от общего количества откликов невозможно классифицировать в эти категории. Каждая категория может отличаться типом реакции системы или оператора. Например, такой реакцией может стать отправка стандартного ответа, передача на дальнейшую обработку менеджеру по продажам, простановка в систему планирования для дальнейших контактов, внесение в особый список и т. д.
Задача автоматического распознавания категорий входящих откликов решается применением фильтров по ключевым фразам, возможность создания которых присутствует сегодня практически в каждой программе-клиенте электронной почты. Однако, в связи с этим возникает проблема создания фильтров, способных распознавать категорию сообщения. Цели, которые ставятся при создании фильтров, следующие. Во-первых, с помощью созданных фильтров должен распознаваться достаточно высокий процент сообщений, во-вторых, погрешность распознавания не должна превышать допустимую, в соответствии с целями обработки сообщений.
Фильтры могут создаваться вручную, однако в связи с этим возникает следующий комплекс проблем: относительно невысокий процент распознавания и относительно высокая погрешность, либо значительное время на создание и тестирование фильтров. Фильтры необходимо протестировать на значительной выборке сообщений (как правило, 1000 и более).
В данной статье предлагается алгоритм автоматизированного создания фильтров. Заметим, что данный алгоритм работает для английского языка. Реализация его для других
языков с иной структурой может представлять сложность, иметь худшие результаты, либо требовать доработки алгоритма.
Рассмотрим вначале простую модель создания фильтров по выборке значительного размера. Оператор определяет категории, вручную сортирует достаточно большое число сообщений (например, 2000) по категориям, после чего передает выборку в таком виде программе.
Принцип работы алгоритма заключается в сравнении частоты появления той или иной ключевой фразы в каждой категории. Если в одной категории фраза встречается значительно чаще, чем в другой, при этом не менее какого-то количества раз, то можно считать, что оно является ключевой фразой.
Поясним подробнее. Укрупненно, порядок выделения ключевых фраз таков:
1)создание списка всех слов во всех сообщениях каждой категории;
2)определение индекса присутствия для всех выражений (упрощенно - частота появления слова в категории);
3)выявление и пометка кандидатов в ключевые выражения - выражений, для которых индекс встречаемости выше заданного;
4)для всех таких кандидатов: добавление в список выражений с размерностью на одно слово больше, слово берется из сообщения справа от того, на которое оканчивается текущее выражение, и присоединяется к кандидату;
5)повторение шагов 2-4 для всех новых появившихся выражений, пока не перестанут появляться новые кандидаты в ключевые выражения на шаге 3.
Цель части алгоритма выше - выделить все возможные выражения из любого количества слов, которые повторяются в категории не менее заданного числа раз, то есть проявляют собой некоторую повторяемость, и следовательно, могут являться кандидатами в ключевые выражения.
6)сравнение частоты встречаемости кандидатов в ключевые выражения вне и внутри категории: если их частное не больше определённого значения, то выражение считается ключевым.
Таким образом, алгоритм определения выражения как ключевого базируется на двух критериях: достаточная повторяемость в распознаваемой категории и достаточно большое различие в частоте появления внутри и вне распознаваемой категории. Позволим себе небольшое отступление: небезынтересно, эти принципы определения критериев распознавания категорий объектов, по-видимому, соответствуют двум принципам естественной эволюции - размножению и селекции.
Итак, результатом работы алгоритма является набор ключевых выражений, каждое из которых способно с обозначенной погрешностью распознать принадлежность или непринадлежность нового сообщения к какой-либо категории.
Рассмотрим подробнее каждый из пунктов алгоритма.
1.Получив выборку сообщений, разбитую на категории, программа создает список всех слов, встречающихся в каждом сообщении в каждой категории. Слово -последовательность символов, разделенная пробелами, и рядом других знаков («!?;:%()+» и т.д.). В списке для каждого слова также указывается адрес сообщения в базе, в котором встречается слово, и позиция внутри сообщения. Эти параметры понадобятся для быстрого доступа к данному слову в сообщении при дальнейшем создании выражений, состоящих из 2, 3 и большего количества слов.
2.Далее программа сортирует этот индекс слов по алфавиту и подсчитывает для каждого слова индекс встречаемости. Сортировка позволит более быстро подсчитать индекс
встречаемости. Индекс встречаемости - это параметр, являющийся чем-то средним между количеством сообщений, в которых встречается данное слово, и количеством всех вхождений данного слова в категорию. Ценность многократного появления слова в 1 сообщении ниже, чем появления слова во многих сообщениях по 1 разу. Чтобы учесть этот принцип снижающейся предельной полезности (в целях распознавания категории) каждого нового повтора слова и вводится индекс встречаемости слова.
На основании индекса встречаемости далее будет производиться отбраковка кандидатов в ключевые фразы из всего списка фраз.
Индекс встречаемости можно высчитать следующим образом. Все выделенные слова, содержащиеся во всех сообщениях категории, проходят по порядку. Если в одном сообщении какое-либо слово встречается 1 раз, то к индексу его встречаемости в выборке добавляется единица. Если 2 повтора слова, то к индексу встречаемости прибавляется 1+1/k (например, 1+1/3), если 3 повтора, то 1+1/k+1/(2k) (в примере - 1+1/3+1/6), если 4, то 1+1/k+1/(2k)+1/(3k) (т.е. 1+1/3+1/6+1/9) и т.д. Общая формула очередного добавляемого слагаемого: 1/((N-1)k), где N - номер очередного повтора слова в данном сообщении, k -коэффициент значимости повторений, который может принимать значения от 1 и выше. Увеличение индекса встречаемости для данного сообщения можно высчитать и проще, по известной формуле суммы конечной убывающей геометрической прогрессии, где аргументом будет количество вхождений фразы в сообщение.
Поясним на примерах, как действует индекс встречаемости. Если слово в сообщении встречается 1 раз, то к индексу добавляется единица. Если 10 раз, то не 10 единиц, а лишь 2 или 3 единицы, в зависимости от выставленного коэффициента k. Таким образом, если человек ответил сообщением, где 100 раз повторяется одно и то же слово REMOVE, то значимость этого слова с точки зрения распознавания категории окажется лишь, скажем, в 3,5 раза выше, чем, если бы человек сказал REMOVE в своем сообщении всего 1 раз. Индекс встречаемости слова в категории, встречающегося 10 раз в 1 сообщении из категории - лишь 3, в то время как по 1 разу в 10 сообщениях - 10.
На взгляд авторов, целесообразно устанавливать k консервативно: таким образом, чтобы при больших значениях повторов в сообщении, индекс встречаемости оказывался близким к 2. k может равняться 5,2, тогда, при 100 повторах прирост индекса встречаемости, примерно равен 2, а при неограниченно большом числе повторов - не уходит далеко от 2,5.
Заметим, что выбор формулы для расчета коэффициента встречаемости не является чем-то, безусловно детерминированным, может быть выбрана и другая функция. Однако выбранная функция, по мнению авторов, неплохо реализует требуемое от нее поведение.
Итак, ко всем словам, выделенным из всех сообщений в каждой категории, рассчитан индекс встречаемости, демонстрирующий, насколько часто в данной категории появляется данное слово.
3.Далее определяются и маркируются те выражения, которые являются кандидатами в ключевые выражения. Признаком является индекс встречаемости не ниже порогового значения A. «A» может принимать значения от 1 и более. Лишь в особых случаях использования алгоритма может иметь смысл устанавливать значение А=1 (то есть появление выражения в выборке как такового хотя бы 1 раз). Обычно достаточно надежным признаком повторяемости, а значит, неслучайности выражения, может являться значение А, равное 3 или 4.
4.Следующим шагом, для кандидатов в ключевые выражения необходимо построить и добавить в список выражения с числом слов, на единицу большим. Для этого программа проходит по списку кандидатов в ключевые выражения, обращается по указанной в них ссылке на сообщение и позицию в нем, и берет следующее за текущим выражением слово. Это слово присоединяется справа к текущему выражению, после чего выражение добавляется в список.
содержание:
[стр.Введение] [стр.1] [стр.2]