Алгоритм Chung-Kwei: автоматическая классификация писем на основе выявления повторяющихся шаблонов

Алгоритм Teiresias

Алгоритм предназначен для поиска в массиве строк повторяющихся последовательностей (шаблонов). Был разработан группой биоинформатики исследовательского центра IBM для исследования цепочек ДНК. Подробное описание см. в работе [1], исследование сложности в [2].

Задан массив строк в алфавите A. Будем считать шаблоном (в терминах алгоритма Teiresias) последовательность следующего вида: A(A|.)*A. То есть шаблоном является строка, начинающаяся и кончающаяся символами из алфавита A, между которыми находится любая комбинация символов алфавита A и специального символа ‘.’ (точка). Шаблон является регулярным выражением, в котором специальный символ ‘.’ соответствует любому символу алфавита A. Тем самым шаблон P определяет язык G(P). К примеру, если задан шаблон BC.D.E, то его язык будет содержать, в частности, следующие строки: BCCDCE, BCEDCE, BCBDBEБ и т.п.

Для шаблона P каждая его подстрока, так же являющаяся шаблоном, называется внутренним шаблоном шаблона P. Шаблон P называется (L,W)-шаблоном, если каждый его внутренний шаблон длины W или более содержит как минимум L символов алфавита A. Понятно, что если шаблон P является (L,W)-шаблоном, то он также является и (L,W+1)-шаблоном.

Строка символов алфавита A называется подпадающей под шаблон P, если содержит в себе подстроку из языка G(P). Если задан набор строк S={s₁,s₂,…,s_n}, то для шаблона P можно определить следующее множество смещений:

L_s(P)={(i,j)| строка s_i содержит в себе строку языка G(P), начиная со смещения j}.

Шаблон P´ называется более характерным, чем P, если он может быть получен из P путем замещения одного или более специальных символов ‘.’ на символы алфавита A или через дописывания справа или/и слева строк, состоящих из специальных символов и символов алфавита A. Очевидно, что |L_s(P´)|≤|L_s(P)|. Шаблон P называется максимальным для множества S, если не существует более характерного шаблона P´, такого что
|L_s(P´)|=|L_s(P)|.

Алгоритм Teiresias позволяет по множеству строк S={s₁,s₂,…,s_n} в алфавите A и параметрам L, W, K найти все максимальные (L,W)-шаблоны, под которые подпадают как минимум в K различных строк множества S.

Подробное описание алгоритма Teiresias см. в [1, 2]. Попробовать алгоритм в действии можно на сайте группы биоинформатики исследовательского центра IBM: http://cbcsrv.watson.ibm.com/Tspd.html.

Алгоритм Chung-Kwei

Алгоритм Chung-Kwei основан на применении алгоритма Teiresias для поиска шаблонов в электронных сообщениях и разработан для спам-фильтра компании IBM SpamGuru. Алгоритм является целиком эвристическим, то есть не имеющим под собой точного обоснования.

Письма представляются в виде строк в алфавите ASCII. Авторы предполагают разделение писем на две части: техническая информация (заголовки) и тело письма, после чего предлагается использовать алгоритм раздельно для обеих частей. Тем не менее, в его описании [3] авторы используют только тело письма без технической информации.

Алгоритм выполняется в два этапа — построение базы шаблонов (обучение) и применение шаблонов для классификации письма.

Для построения базы шаблонов (словаря спама) используется исходный набор спама, для которого применяется алгоритм Teiresias с некоторыми заданными (L,W) и K=2. Понятно, что полученные шаблоны являются характеристиками документов и могут лежать в основе любого иного метода автоматической классификации, например, Байесовского классификатора.

Если кроме набора спама есть и набор нормальной почты, то шаблоны выделяются и из него. Их можно использовать для того, чтобы удалить из словаря спама лишние шаблоны и тем понизить вероятность ложных срабатываний.

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

Для каждого символа обрабатываемого письма заводится отдельный счетчик, изначально устанавливаемый в 0.

Каждое вхождение шаблона в письмо также соответствует вхождениям этого же шаблона в некоторые письма исходного набора. Для каждого такого вхождения по таблице соответствий символов начисляются очки в счетчики. Например, обрабатываемое письмо содержит подстроку ABCD, соответствующую найденному шаблону, и вхождение в базу содержит подстроку AbCD. Тогда каждому из четырех счетчиков, соответствующих символам этой строки в обрабатываемом письме, добавятся очки для пар символов (A,A), (B,b), (C,C) и (D,D) соответственно. Таблица соответствий символов заполняется изначально, исходя из прагматических соображений о степени «похожести» символов.

Если после завершения обработки шаблонов процентное количество ненулевых счетчиков (покрытие письма шаблонами) для обрабатываемого письма будет невелико (меньше заданного порога), то письмо считается «не спамом». В противном случае письмо считается «спамом».

Найденные спамерские письма могут автоматически добавляться в базу и использоваться для обучения алгоритма на лету.

Результаты классификации спама, указанные авторами в [3], есть 96% распознавания спама и 0,06% ложных срабатываний. Более подробное описание алгоритма Chung-Kwei и результатов его тестирования можно найти в [3].

Выводы

Предложенный в работе [3] алгоритм обладает достаточно узкой областью применения. Очевидно, что его использование у конечного получателя почты невозможно в силу того, что обучающая база спамерских сообщений должна быть большой и разнообразной (в [3] авторы использовали более 65 тысяч писем). Сложно ожидать, чтобы обычный конечный пользователь имел бы такое количество спама.

Кроме того, предполагается, что все письма, на которых производилось обучение, должны оставаться доступными при классификации почтовых сообщений (по ним рассчитывается покрытие шаблонами обрабатываемого письма). Если принять средний размер письма за 5КБ, то 65 тысяч писем потребуют более 300МБ на жестком диске. Таким образом, конечный пользователь для использования алгоритма Chung-Kwei в своем почтовом клиенте должен будет получить как минимум 300МБ архива спама и постоянно выкачивать обновления для него.

Таким образом, использование непосредственно описанного выше алгоритма Chung-Kwei на почтовых клиентах сильно затруднено.

Серверное же применение данного алгоритма, как и любого другого алгоритма, основанного на обучении, ограничено прежде всего отсутствием базы «не спама», которую очень сложно получить. И хотя авторы утверждают, что использование базы «не спама» для очистки словаря спамерских шаблонов необязательно, тем не менее они не приводят данных о ложных срабатываниях в случае отказа от этой операции. Можно предположить, что результат не будет очень хорошим. С другой стороны, может оказаться, что отсутствие вычистки по базе «не спама» приведет лишь к увеличению порогов количества совпавших шаблонов и покрытия письма, хотя это маловероятно и требует исследования на таких сложных категориях для классификации, как, например, приглашения на семинары.

Тем не менее, сама идея использования алгоритма Teiresias для выделения характерных признаков спама, которую авторы работы [3] хотели продемонстрировать при помощи алгоритма Chung-Kwei, очевидно, является удачной. Например, при помощи алгоритма Teiresias и при наличии достаточного количества спама для обработки становится возможным упростить труд лингвистов по выделению характеристических особенностей спама.

Ссылки

[1] I. Rigoutsos, A. Floratos. Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm. Bioinformatics, Vol .14, no. 1, 1998.
[2] A. Floratos, I. Rigoutsos. Research report: On the time complexity of the TEIRESIAS algorithm. IBM Research division, RC21161(94582)21APR98, 1998.
[3] I. Rigoutsos, T. Huynh. Chung-Kwei: a pattern-discovery-based system for the automatic identification of unsolicted e-mail messages (SPAM).