АЛГОРИТМ ОПРЕДЕЛЕНИЯ СПАМНОСТИ ДОКУМЕНТОВ НА ОСНОВЕ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ
А.Г. Коробейников, С.Ю. Блинов, А.В. Лейман, Г.Л. Маркина, И.М. Кутузов
7 МЕТОДЫ И СИСТЕМЫ ЗАЩИТЫ ИНФОРМАЦИИ
УДК 004.912
АЛГОРИТМ ОПРЕДЕЛЕНИЯ СПАМНОСТИ ДОКУМЕНТОВ НА ОСНОВЕ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ
А.Г. Коробейников, С.Ю. Блинов, А.В. Лейман, Г.Л. Маркина, И.М. Кутузов
Предложен алгоритм определения спамности почтовых документов на базе метода опорных векторов. Модификация метода заключается в построении разделяющей гиперплоскости на основе фейеровских отображений, что позволяет работать с нестационарными данными, характерными для задач классификации документов. Ключевые слова: классификация информации, спам, задачи сильной отделимости, гильбертово пространство.
Введение
Информационные технологии породили все увеличивающийся поток разнородной информации. Основной задачей поисковых систем (поисковых машин) является предоставление качественных результатов, т.е. наиболее важных релевантных страниц. Для этого необходимо решать задачу классификации. В связи с этим теория, методы и алгоритмы классификации информации являются бурно развивающимся научным направлением.
Одной из важнейших проблем, встающей практически перед каждым пользователем Интернет, является борьба со спамом, т.е. задача фильтрации (классификации) поступающей информации. В настоящее время разработан ряд технологий построения фильтров – сервисов для отсеивания нежелательной информации. Эти технологии можно разделить на настраиваемые вручную и автоматизированные. Настраиваемые вручную фильтры основываются на списках доступа: пользователь непосредственно выбирает либо нежелательные адреса (при политике пропуска по «черному списку»), либо разрешенные адреса (при политике пропуска по «белому списку»). Однако ручные способы фильтрации нежелательных сообщений малоэффективны и требуют постоянного обновления списков доступа, создавая дополнительную нагрузку на пользователя. Кроме того, ручная категоризация неприменима, если необходимо классифицировать большой объем информации за ограниченное время.
Применение автоматизированных технологий фильтрации основано на использовании методов распознавания образов, искусственного интеллекта, математической статистики и т.д. [1, 2].
Одним из самых популярных на сегодняшний день является фильтр, основанный на байесовском подходе (наивный байесовский классификатор), в котором предполагается, что различные термы сообщения независимы друг от друга. Но для повышения эффективности таких фильтров необходимо учитывать семантические связи между термами, что требует привлечения методов семантического анализа, тем самым существенно повышая нагрузку на систему и увеличивая время работы самого фильтра при незначительном повышении эффективности фильтрации.
Таким образом, существует потребность в разработке новых методов и алгоритмов классификации информации для решения задачи фильтрации нежелательных сообщений, что делает актуальной тему настоящей работы. В работе предложен алгоритм построения классификатора, базирующийся на построении разделяющей гиперплоскости в гильбертовом пространстве на основе фейеровского отображения [3, 4].
Постановка задачи классификации
Формально постановка задачи классификации выглядит следующим образом. Пусть дано конечное множество категорий (классов) C = {c1, c2, …c|C|} и конечное множество документов D = {d1, d2, …d|D|}. Целевая функция (функционал, классификатор) Ф : DC {–1, 1}, определяющая для каждой пары соответствие их друг другу, неизвестна. Требуется найти классификатор Ф′, т.е. функцию, максимально близкую к функции Ф [4]. Если пересечение двух категорий пусто, то имеет место бинарная классификация, которая часто используется в фильтрации спама. Если имеются образцы из каждой категории (объекты) и заранее известно, к какой категории они принадлежат, то такие задачи называются обучением с учителем, а известные данные – обучающей выборкой. В предлагаемом методе используется именно этот подход. Машинное обучение предполагает наличие обучающей и контрольной выборки. Дана начальная
коллекция документов = {d1, d2, …d||} D, где значения целевой функции Ф известны для (di, cj) C. Эта коллекция разбивается на два непересекающихся множества: = 12 и 12 = (1 – спам, 2 – не спам). Формирование этих подмножеств может происходить вручную, т.е. эксперты после работы с множеством документов мощности || выносят решение: если документ di является спамом, то он принадлежит множеству di 1; наоборот, если документ не спам, то di 2.
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
123
АЛГОРИТМ ОПРЕДЕЛЕНИЯ СПАМНОСТИ ДОКУМЕНТОВ …
Обозначим обучающее множество Q = {(di,yi)}, где di , yi C. Классификатор Ф обучается индуктивно на основе выявленных характеристик документов [5].
Анализ метода построения классификатора
Построение классификатора будем проводить на основе метода опорных векторов (SVM – support vector machines) [6]. SVM – это набор схожих алгоритмов на основе обучения с учителем, применяющийся для анализа данных и распознавания образов в задачах классификации и регрессионном анализе. SVM является линейным классификатором. На основе обучающей выборки алгоритм помогает предсказать, в какую категорию из двух заранее заданных попадает элемент, подлежащий классификации.
Особым свойством SVM является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора. По этой причине этот метод также известен как метод классификатора с максимальным зазором. SVM считается очень перспективным для решения задач классификации (кластеризации) с использованием методов теории искусственного интеллекта.
Основная идея, используемая в SVM, – построение гиперплоскости или набора гиперплоскостей в пространстве более высокой размерности и максимизация расстояния между построенной гиперплоскостью и классами обучающей выборки. Но в настоящее время еще не разработаны общие методы построения таких гиперплоскостей (спрямляющих пространств или ядер классификатора), наиболее подходящих для конкретной задачи. Построение адекватного ядра является искусством и, как правило, опирается на априорные знания о предметной области. На практике «вполне разумные» ядра классификатора, выведенные из содержательных соображений, далеко не всегда оказываются положительно определенными, что, естественно, не может не сказаться на качестве решения. Именно построению такой гиперплоскости посвящена настоящая работа.
Разработка алгоритма решения задачи защиты от спама на базе SVM
В задаче классификации информации для задачи защиты от спама необходимо определять, являет-
ся данный документ спамом или нет. В предлагаемом подходе для решения этой задачи вводится систе-
ма метрик. Пользователь разделяет свои письма и отмечает те, которые считает спамом, т.е. строит обу-
чающее множество Q. На основании этой информации строятся выпуклые оболочки в виде систем ли-
нейных неравенств. Первая система задает множество точек-документов, определяемых как спам, вторая
система – множество точек-документов, определяемых как не спам. Построив слой наибольшей толщи-
ны, разделяющий два многогранника, можно разработать процедуру, позволяющую автоматически раз-
делять (классифицировать) документы на «хорошие» и «плохие». Получив новый документ и прочитав
его характеристики, получаем точку в рассматриваемом пространстве. Если данная точка попадает в
«плохое» полупространство, делается предположение, что это спам; если в «хорошее» – не спам; если
точка попадает внутрь слоя, письмо доставляется пользователю с пометкой «возможно, спам».
Для решения задачи сильной отделимости обычно применяют итерационный процесс, исполь-
зующий операцию проектирования. Однако на практике применение этого метода существенно ограни-
чено тем фактом, что далеко не всегда удается построить конструктивную формулу для вычисления про-
екции точки на выпуклое множество. В связи с этим целесообразно произвести замену операции проек-
тирования последовательностью фейеровских отображений [7].
Кроме того, алгоритмы разделения многогранников на основе фейеровских отображений обладают
тем преимуществом по сравнению с проективными и другими известными методами, что они примени-
мы к нестационарным задачам, т.е. к задачам, в которых исходные данные могут меняться в процессе
решения задачи. Такой нестационарной задачей является, например, задача о спам-фильтре.
Рассмотрим алгоритмы для решения задачи сильной отделимости.
Пусть даны два выпуклых непересекающихся многогранника M Rn и N Rn, заданные система-
ми линейных неравенств
M = {x| Ax b} ; N = {x| Bx d} .
(1)
Задача сильной отделимости заключается в нахождении слоя наибольшей толщины, разделяющего
M и N. Эта задача эквивалентна задаче отыскания расстояния между M и N в смысле метрики:
(M,N) = min{|| x – y || x M, y N}.
(2)
Если x1 M и y1 N являются arg-точками задачи (2), т.е. (M,N) = ||x1 – y1||, то слоем наибольшей толщины, разделяющим множества M и N, является
P = {x| x P1 P2}, где < , > – скалярное произведение двух векторов; P1 и P2 – полупространства, задаваемые линейными неравенствами
< x – x1, x1 – y1 > 0 и < y – y1, x1 – y1 > 0. Следовательно, задачу сильной отделимости можно сформулировать так:
{ x1, y1} = аrg min{||x – y|| x M, y N}.
(3)
Задачу (3) можно решить при помощи известного алгоритма последовательного проектирования.
124
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
А.Г. Коробейников, С.Ю. Блинов, А.В. Лейман, Г.Л. Маркина, И.М. Кутузов
Алгоритм решения задачи сильной отделимости (). Даны два выпуклых непересекающихся многогранника M Rn и N Rn, заданные системами линейных неравенств (1). Обозначим отображение
(проектирование) точки на M через M, а на N – M. Зададим произвольное начальное приближение w0 Rn. Выберем фиксированное положительное вещественное число . Тогда алгоритм решения задачи сильной отделимости будет состоять из следующих шагов.
Шаг 0. k := 0.
Шаг 1. xk+1 := M (wk). Шаг 2. yk+1 := N (wk). Шаг 3. wk+1 := (xk+1 + yk+1)/2. Шаг 4. k := k + 1.
Шаг 5. Если min{||xk+1– xk||, ||yk+1– yk||} , то перейти к шагу 1. Шаг 6. Конец. Если множества M и N достаточно просты в смысле реализации операции проектирования точек
на них, то представленный алгоритм может быть использован на практике. Но если M и N – произ-
вольные многогранники, то не может быть признан эффективным, так как неизвестен универсальный конструктивный метод построения проекции точки на многогранник. В этом случае решить задачу можно, если вместо операции проектирования использовать фейеровские отображения.
Дадим определение фейеровского отображения. Пусть : Rn → Rn. Отображение называется
М-фейеровским, если выполняются следующие два условия:
y y , y M; x y x y , x M, y M.
Класс M-фейеровских отображений обозначим через FM.
Под фейеровским процессом, порождаемым однозначным M-фейеровским отображением FM
при произвольном начальном приближении x0 Rn, будем понимать последовательность
k x0
.
k 0
Известно [8], что в случае, когда однозначное М-фейеровское отображение является непрерыв-
ным, фейеровский процесс сходится к точке, принадлежащей множеству
М:
k x0
x M.
k 0
Это означает, что для любого вещественного > 0 существует целое положительное число K, та-
кое, что для всех k > K имеем xk x .
Спроектируем М-фейеровское отображение, согласно [8]. Представим систему линейных нера-
венств, задающих многогранник M, в виде
M = {x| Ax b : lj(x) = < aj, x > – b 0, j = 1,…m},
где 0 для любого j. Зададим
l plus j
x
следующим образом:
l
plus j
x
max
lj x,0
, j 1,...m .
Тогда отображение вида
x
m
x
j 1
aj
2
j
l plus j aj
x
2
будет М-фейеровским для любой системы положительных коэффициентов {aj >0}, j = 1, …, m, таких, что
m
a j 1 , и коэффициентов релаксации 0
7 МЕТОДЫ И СИСТЕМЫ ЗАЩИТЫ ИНФОРМАЦИИ
УДК 004.912
АЛГОРИТМ ОПРЕДЕЛЕНИЯ СПАМНОСТИ ДОКУМЕНТОВ НА ОСНОВЕ ФЕЙЕРОВСКИХ ОТОБРАЖЕНИЙ
А.Г. Коробейников, С.Ю. Блинов, А.В. Лейман, Г.Л. Маркина, И.М. Кутузов
Предложен алгоритм определения спамности почтовых документов на базе метода опорных векторов. Модификация метода заключается в построении разделяющей гиперплоскости на основе фейеровских отображений, что позволяет работать с нестационарными данными, характерными для задач классификации документов. Ключевые слова: классификация информации, спам, задачи сильной отделимости, гильбертово пространство.
Введение
Информационные технологии породили все увеличивающийся поток разнородной информации. Основной задачей поисковых систем (поисковых машин) является предоставление качественных результатов, т.е. наиболее важных релевантных страниц. Для этого необходимо решать задачу классификации. В связи с этим теория, методы и алгоритмы классификации информации являются бурно развивающимся научным направлением.
Одной из важнейших проблем, встающей практически перед каждым пользователем Интернет, является борьба со спамом, т.е. задача фильтрации (классификации) поступающей информации. В настоящее время разработан ряд технологий построения фильтров – сервисов для отсеивания нежелательной информации. Эти технологии можно разделить на настраиваемые вручную и автоматизированные. Настраиваемые вручную фильтры основываются на списках доступа: пользователь непосредственно выбирает либо нежелательные адреса (при политике пропуска по «черному списку»), либо разрешенные адреса (при политике пропуска по «белому списку»). Однако ручные способы фильтрации нежелательных сообщений малоэффективны и требуют постоянного обновления списков доступа, создавая дополнительную нагрузку на пользователя. Кроме того, ручная категоризация неприменима, если необходимо классифицировать большой объем информации за ограниченное время.
Применение автоматизированных технологий фильтрации основано на использовании методов распознавания образов, искусственного интеллекта, математической статистики и т.д. [1, 2].
Одним из самых популярных на сегодняшний день является фильтр, основанный на байесовском подходе (наивный байесовский классификатор), в котором предполагается, что различные термы сообщения независимы друг от друга. Но для повышения эффективности таких фильтров необходимо учитывать семантические связи между термами, что требует привлечения методов семантического анализа, тем самым существенно повышая нагрузку на систему и увеличивая время работы самого фильтра при незначительном повышении эффективности фильтрации.
Таким образом, существует потребность в разработке новых методов и алгоритмов классификации информации для решения задачи фильтрации нежелательных сообщений, что делает актуальной тему настоящей работы. В работе предложен алгоритм построения классификатора, базирующийся на построении разделяющей гиперплоскости в гильбертовом пространстве на основе фейеровского отображения [3, 4].
Постановка задачи классификации
Формально постановка задачи классификации выглядит следующим образом. Пусть дано конечное множество категорий (классов) C = {c1, c2, …c|C|} и конечное множество документов D = {d1, d2, …d|D|}. Целевая функция (функционал, классификатор) Ф : DC {–1, 1}, определяющая для каждой пары соответствие их друг другу, неизвестна. Требуется найти классификатор Ф′, т.е. функцию, максимально близкую к функции Ф [4]. Если пересечение двух категорий пусто, то имеет место бинарная классификация, которая часто используется в фильтрации спама. Если имеются образцы из каждой категории (объекты) и заранее известно, к какой категории они принадлежат, то такие задачи называются обучением с учителем, а известные данные – обучающей выборкой. В предлагаемом методе используется именно этот подход. Машинное обучение предполагает наличие обучающей и контрольной выборки. Дана начальная
коллекция документов = {d1, d2, …d||} D, где значения целевой функции Ф известны для (di, cj) C. Эта коллекция разбивается на два непересекающихся множества: = 12 и 12 = (1 – спам, 2 – не спам). Формирование этих подмножеств может происходить вручную, т.е. эксперты после работы с множеством документов мощности || выносят решение: если документ di является спамом, то он принадлежит множеству di 1; наоборот, если документ не спам, то di 2.
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
123
АЛГОРИТМ ОПРЕДЕЛЕНИЯ СПАМНОСТИ ДОКУМЕНТОВ …
Обозначим обучающее множество Q = {(di,yi)}, где di , yi C. Классификатор Ф обучается индуктивно на основе выявленных характеристик документов [5].
Анализ метода построения классификатора
Построение классификатора будем проводить на основе метода опорных векторов (SVM – support vector machines) [6]. SVM – это набор схожих алгоритмов на основе обучения с учителем, применяющийся для анализа данных и распознавания образов в задачах классификации и регрессионном анализе. SVM является линейным классификатором. На основе обучающей выборки алгоритм помогает предсказать, в какую категорию из двух заранее заданных попадает элемент, подлежащий классификации.
Особым свойством SVM является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора. По этой причине этот метод также известен как метод классификатора с максимальным зазором. SVM считается очень перспективным для решения задач классификации (кластеризации) с использованием методов теории искусственного интеллекта.
Основная идея, используемая в SVM, – построение гиперплоскости или набора гиперплоскостей в пространстве более высокой размерности и максимизация расстояния между построенной гиперплоскостью и классами обучающей выборки. Но в настоящее время еще не разработаны общие методы построения таких гиперплоскостей (спрямляющих пространств или ядер классификатора), наиболее подходящих для конкретной задачи. Построение адекватного ядра является искусством и, как правило, опирается на априорные знания о предметной области. На практике «вполне разумные» ядра классификатора, выведенные из содержательных соображений, далеко не всегда оказываются положительно определенными, что, естественно, не может не сказаться на качестве решения. Именно построению такой гиперплоскости посвящена настоящая работа.
Разработка алгоритма решения задачи защиты от спама на базе SVM
В задаче классификации информации для задачи защиты от спама необходимо определять, являет-
ся данный документ спамом или нет. В предлагаемом подходе для решения этой задачи вводится систе-
ма метрик. Пользователь разделяет свои письма и отмечает те, которые считает спамом, т.е. строит обу-
чающее множество Q. На основании этой информации строятся выпуклые оболочки в виде систем ли-
нейных неравенств. Первая система задает множество точек-документов, определяемых как спам, вторая
система – множество точек-документов, определяемых как не спам. Построив слой наибольшей толщи-
ны, разделяющий два многогранника, можно разработать процедуру, позволяющую автоматически раз-
делять (классифицировать) документы на «хорошие» и «плохие». Получив новый документ и прочитав
его характеристики, получаем точку в рассматриваемом пространстве. Если данная точка попадает в
«плохое» полупространство, делается предположение, что это спам; если в «хорошее» – не спам; если
точка попадает внутрь слоя, письмо доставляется пользователю с пометкой «возможно, спам».
Для решения задачи сильной отделимости обычно применяют итерационный процесс, исполь-
зующий операцию проектирования. Однако на практике применение этого метода существенно ограни-
чено тем фактом, что далеко не всегда удается построить конструктивную формулу для вычисления про-
екции точки на выпуклое множество. В связи с этим целесообразно произвести замену операции проек-
тирования последовательностью фейеровских отображений [7].
Кроме того, алгоритмы разделения многогранников на основе фейеровских отображений обладают
тем преимуществом по сравнению с проективными и другими известными методами, что они примени-
мы к нестационарным задачам, т.е. к задачам, в которых исходные данные могут меняться в процессе
решения задачи. Такой нестационарной задачей является, например, задача о спам-фильтре.
Рассмотрим алгоритмы для решения задачи сильной отделимости.
Пусть даны два выпуклых непересекающихся многогранника M Rn и N Rn, заданные система-
ми линейных неравенств
M = {x| Ax b} ; N = {x| Bx d} .
(1)
Задача сильной отделимости заключается в нахождении слоя наибольшей толщины, разделяющего
M и N. Эта задача эквивалентна задаче отыскания расстояния между M и N в смысле метрики:
(M,N) = min{|| x – y || x M, y N}.
(2)
Если x1 M и y1 N являются arg-точками задачи (2), т.е. (M,N) = ||x1 – y1||, то слоем наибольшей толщины, разделяющим множества M и N, является
P = {x| x P1 P2}, где < , > – скалярное произведение двух векторов; P1 и P2 – полупространства, задаваемые линейными неравенствами
< x – x1, x1 – y1 > 0 и < y – y1, x1 – y1 > 0. Следовательно, задачу сильной отделимости можно сформулировать так:
{ x1, y1} = аrg min{||x – y|| x M, y N}.
(3)
Задачу (3) можно решить при помощи известного алгоритма последовательного проектирования.
124
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 6 (82)
А.Г. Коробейников, С.Ю. Блинов, А.В. Лейман, Г.Л. Маркина, И.М. Кутузов
Алгоритм решения задачи сильной отделимости (). Даны два выпуклых непересекающихся многогранника M Rn и N Rn, заданные системами линейных неравенств (1). Обозначим отображение
(проектирование) точки на M через M, а на N – M. Зададим произвольное начальное приближение w0 Rn. Выберем фиксированное положительное вещественное число . Тогда алгоритм решения задачи сильной отделимости будет состоять из следующих шагов.
Шаг 0. k := 0.
Шаг 1. xk+1 := M (wk). Шаг 2. yk+1 := N (wk). Шаг 3. wk+1 := (xk+1 + yk+1)/2. Шаг 4. k := k + 1.
Шаг 5. Если min{||xk+1– xk||, ||yk+1– yk||} , то перейти к шагу 1. Шаг 6. Конец. Если множества M и N достаточно просты в смысле реализации операции проектирования точек
на них, то представленный алгоритм может быть использован на практике. Но если M и N – произ-
вольные многогранники, то не может быть признан эффективным, так как неизвестен универсальный конструктивный метод построения проекции точки на многогранник. В этом случае решить задачу можно, если вместо операции проектирования использовать фейеровские отображения.
Дадим определение фейеровского отображения. Пусть : Rn → Rn. Отображение называется
М-фейеровским, если выполняются следующие два условия:
y y , y M; x y x y , x M, y M.
Класс M-фейеровских отображений обозначим через FM.
Под фейеровским процессом, порождаемым однозначным M-фейеровским отображением FM
при произвольном начальном приближении x0 Rn, будем понимать последовательность
k x0
.
k 0
Известно [8], что в случае, когда однозначное М-фейеровское отображение является непрерыв-
ным, фейеровский процесс сходится к точке, принадлежащей множеству
М:
k x0
x M.
k 0
Это означает, что для любого вещественного > 0 существует целое положительное число K, та-
кое, что для всех k > K имеем xk x .
Спроектируем М-фейеровское отображение, согласно [8]. Представим систему линейных нера-
венств, задающих многогранник M, в виде
M = {x| Ax b : lj(x) = < aj, x > – b 0, j = 1,…m},
где 0 для любого j. Зададим
l plus j
x
следующим образом:
l
plus j
x
max
lj x,0
, j 1,...m .
Тогда отображение вида
x
m
x
j 1
aj
2
j
l plus j aj
x
2
будет М-фейеровским для любой системы положительных коэффициентов {aj >0}, j = 1, …, m, таких, что
m
a j 1 , и коэффициентов релаксации 0