автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Методы и алгоритмы классификации информации для защиты от спазма

/

На правах, рукописи

/

Блинов Станислав Юрьевич

Методы и алгоритмы классификации информации для защиты от спама

Специальность: 05.13.19. Методы и системы защиты информации, информационная безопасность

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург ! 005531978 2013 г. ______

005531978

Работа выполнена на кафедре "Проектирования и безопасности компьютерных систем" в НИУ ИТМО

Научный руководитель:

Коробейников Анатолий Григорьевич доктор технических наук, профессор

Официальные оппоненты:

Нырков Анатолий Павлович доктор технических наук, профессор, ГУМРФ имени адмирала С.О. Макарова, заведующий кафедрой Комплексного обеспечения информационной

безопасности

Карманов Андрей Геннадиевич Кандидат технических наук, доцент, кафедра Геоинформационных технологий НИУ ИТМО

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Поволжский государственный технологический университет»

Защита состоится "29" мая 2013 г. в 15-50 часов на заседании диссертационного Совета Д.212.227.05 в НИУ ИТМО по адресу: 197101, Санкт-Петербург, Кронверский пр., 49.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО

Автореферат разослан "29" апреля 2013 г.

Ученый секретарь диссертационного совета Д.212.227.05,

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы.

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

Классификация информации в сетях, и в частности в сети Интернет, позволяет решать различные задачи, например: документооборот, автоматическое аннотирование и реферирование, машинный перевод, составление интернет-каталогов, ограничение области поиска в поисковых системах, определение кодировки и языка текста, классификация новостей и т.д.

В России большими темпами активно развиваются классификационные системы и специализированные системы полнотекстового анализа, позволяющие производить автоматическую классификацию и реферирование текстов, например, "Следопыт", "ТекстАналист" и другие.

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

Кроме того, в связи с бурным ростом объема информации в сети Интернет поисковые машины стали основным средством для эффективного доступа к ней. Задача поисковой машины - на каждый поисковый запрос выдавать ранжированный набор страниц, наиболее соответствующих запросу. Мера соответствия страницы запросу, называемая релевантностью, вычисляется на основе характеристик страниц и запросов. Некоторые владельцы сайтов пытаются повлиять на работу поисковых машин, чтобы повысить релевантность страниц. Это явление получило название поискового спама.

В настоящее время существуют технологии создания фильтров-сервисов отсекания навязываемой информации. Их принято разделять на два класса: настраиваемые вручную и автоматизированные. Технологии из первого класса применяют списки доступа и настраиваются пользователем, выбирающему или запрещенные, при политике «черного списка», или разрешенные, при политике «белого списка», адреса. Но такие разделения навязываемой информации неэффективны так как необходимо частое обновление списков доступа.

Кроме того, ручная категоризация неприменима, если необходимо классифицировать большой объем информации за ограниченное время.

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

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

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

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

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

Все вышесказанное определило цели и задачи диссертационного исследования.

Целью диссертационной работы является повышение эффективности фильтрации информации в сети Интернет с использованием разработанных методов и алгоритмов.

Для достижения поставленной цели в диссертационном исследовании были сформулированы и решены следующие задачи:

• Разработка и анализ алгоритмов детектирования текстового спама на базе машинного обучения.

• Исследование моделей массово создаваемых неестественных текстов.

• Разработка и реализация метода построения разделяющей гиперплоскости в гильбертовом пространстве на основе фейеровского отображения для решения задачи сильной отделимости.

• Разработка системы классификации информации в Интернете, удовлетворяющей следующим условиям:

- точность и полнота обнаружения спам-документов;

- применимость к различным естественным языкам.

Объектом исследования методы и модели классификации информации в Интернете.

Методы исследования. Решение вышеперечисленных задач происходит с применением методов теории защиты информации, системного и структурного анализа, функционального анализа и методов математического моделирования.

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

Положения, выносимые на защиту:

1. Математические модели построения обучающей выборки.

2. Метод построения разделяющей гиперплоскости обучающей выборки на базе фейеровского отображения;

3. Алгоритм классификации документов.

Практическая значимость заключается в том, что

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

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

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

Апробация работы. Основные положения диссертационного исследования докладывались и обсуждались на международных конгрессах и конференциях различного уровня: Всероссийская научно-практическая конференции с международным участием. Йошкар-Ола: Марийский государственный технический университет, 2012; 1-ый Международный симпозиум "Гибридные и синергетические интеллектуальные системы: теория и практика". Россия, Калининград, БФУ им. И.Канта, 2012; Международный конгресс по интеллектуальным системам и информационным технологиям AIS-IT'12. Россия, Дивноморское (Геленджик), 2012.

Результаты исследований реализованы в СПб НИУ ИТМО и используются в учебном процессе при проведении занятий по дисциплинам: «Защита информации», «Информационная безопасность», «Информационная безопасность и защита информации», ООО «ДорСтройИнжиниринг», ООО «Тонар».

Публикации. По тематике диссертации опубликовано девять работ, в том числе три работы входят в список . рекомендованный ВАК для защиты кандидатских диссертаций.

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы.

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, изложенных на 98 листах машинописного текста, содержит 14 рисунков и 11 таблиц. Список литературы включает 62 наименования.

Основное содержание работы Во введении обоснована актуальность темы исследования, сформулированы цель работы, основные научные положения, выносимые на защиту, отмечена научная новизна и практическая ценность работы, кратко изложено основное содержание работы.

В первой главе проанализированы тенденции и закономерности развития систем классификации информации, дана формальная постановка задачи классификации, рассмотрены основные методы классификации.

В настоящее время, по различным оценкам, объем информации увеличивается экспоненциально. Поэтому одной актуальнейших научных задач является систематизация (классификация) информации, в т. ч. в Интернете.

Классификация (категоризация, рубрикация) документов (text categorization, text classification, topic spotting) - является одной из задач информационного поиска, результат который заключается в занесении документа в одну из категорий на основании содержания документа (Рис.1).

Рис.1. Обобщенная схема задачи классификации

Классификация может осуществляться вручную, на основе правил или автоматически. Примером ручной классификации может служить библиотека, где книгам вручную присваиваются тематические рубрики. Ручная категоризация неприменима, если

необходимо классифицировать большой объем документов за ограниченное время.

Классификация на основе правил широко применялась до начала 1990-х гг. В соответствии с правилами, написанными экспертами, документ относился к той или иной категории. Часто правила имели форму регулярных выражений. Таким образом, от эксперта требовалось не только знание предметной области, но и навыки написания правил. Этот подход в некоторых случаях превосходит по точности другие методы, однако для поддержания базы правил в актуальном состоянии необходима постоянная работа эксперта, поэтому в 90-х гг. правила сменились машинным обучением, которое базируется на методах распознавания образов, искусственного интеллекта, математической статистики и т.д.

Автоматической классификации предшествует этап индексирования документов. Индексация - это процесс приведения документа к единому формату. Индексирование включает в себя построение модели документа и уменьшение размерности. Наиболее распространенными моделями документов являются варианты моделей множества слов (Ьад-оГ-\vords), а именно бинарная модель и модель с весами терминов. Бинарная модель учитывает только наличие или отсутствие слова в документе, во взвешенной же модели каждому термину ставится в соответствие его вес.

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

Основными методами классификации информации в настоящее время являются: иерархический метод классификации; фасетный метод классификации; дескрипторный метод классификации; метод "ближайшего соседа" или системы рассуждений на базе аналогичных случаев; многомерная классификация.

Далее было рассмотрено понятие спама и его основные виды. Проанализированы его основные характеристики. Рассмотрены основные методы борьбы со спамом.

Во второй главе рассмотрена математическая постановка задачи классификации, обзор основных алгоритмов классификации и основные положения метода опорных векторов.

Формально постановка задачи классификации выглядит следующим образом. Пусть дано конечное множество категорий (классов) С= {сь ci, ...Cjq} и конечное множество документов D = {d\, d2, Целевая функция (функционал, классификатор)

Ф:DxC —> {-1, 1}, определяющая для каждой пары <документ, категория> соответствие их друг другу, не известна. Требуется найти классификатор Ф', т.е. функцию, максимально близкую к функции Ф. Если пересечение двух категорий пусто, то классификация бинарная, которая часто используется в фильтрации спама.

Если имеются образцы из каждой категории (объекты), про которые заранее известно, к какой категории они принадлежат, то такие задачи называются обучением с учителем, а известные данные называют обучающей выборкой.

Машинное обучение предполагает наличие обучающей и контрольной выборки, т.е. дана начальная коллекция документов £2 = {d\, d2, ...dm}aD, где значения целевой функции Ф известны для V (dh с/)е Q хС. Эта коллекция £2 разбивается на два непересекающихся множества. Классификатор Ф обучается индуктивно на основе выявленных характеристик документов.

Простейшим классификатором является метод ближнего соседа (Nearest Neighbor Classifier). Объект присваивают классу, являющимся наиболее распространенным среди соседей данного объекта. Соседи выбираются из множества объектов, классы которых уже известны.

Метод максимальной энтропии (Maximum Entropy) предусматривает распределение, наиболее близкое к равномерному. На основе обучающей выборки формируется множество ограничений модели. Ограничения представляются как ожидаемые значения признаков.

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

по расстоянию. Метод Роччио не применим для текстов на разных языках.

Деревья решений представляют собой следующий алгоритм: 1) выбирается термин; 2) документы, содержащие этот термин, кладутся слева, не содержащие - справа; 3) выбирается новый термин и все повторяется.

Термины выбираются исходя из коэффициента полезности . Линейный online классификатор рассчитывается по формуле:

CSV,(d)=dcl=YJcydl j

или, после нормализации получаем косинус между векторами:

Обучение можно проводить за пределами обучающей выборки при наличии обратной связи.

Метод регрессии. В отличие от других методов, обучение происходит сразу на всей коллекции.

Метод опорных векторов (SVM - support vector machines) -это набор схожих алгоритмов на основе обучения с учителем, применяющийся для анализа данных и распознавания образов в задачах классификации и регрессионном анализе. SVM является линейным классификатором. На основе обучающей выборки алгоритм помогает предсказать, в какую из двух заранее заданных категорий попадает элемент, подлежащий классификации.

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

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

Разработка поискового спама связана с генерацией текстов для автоматического заполнения спам-сайтов. В настоящее время применяют следующие подходы при создании текстов для спам-сайтов:

• Написание текста вручную;

• Копирование текста из различных источников;

• Автоматическая генерация текстов;

• Автоматическая модификация существующих текстов.

Написание текста вручную есть трудоемкий и дорогостоящий процесс. Из-за этого его крайне редко используют для массового порождения текстов.

Копирование текста из различных источников - очень распространенный прием. Но надо сказать, что сейчас имеются эффективные методы детектирования скопированной текстовой информации, например, на базе шинглирования.

Таким образом, в настоящее время наиболее эффективными являются методы, позволяющие автоматически генерировать уникальную текстовую информацию

В настоящее время достаточно широко применяются генераторы текста на основе цепей Маркова. Сгенерированные ими тексты имеют свойства, которые сделали этот метод популярным для создания поискового спама. Во-первых, в сгенерированном тексте имеется такая же лексика, что и в начальном тексте. Поэтому в качестве образцов используются существующие тексты, высоко ранжируемые поисковыми машинами. Например, берутся образцы текста из сниппетов поисковых машин, и получают на выходе текст, оптимизированный под конкретный запрос. Во-вторых, сгенерированный текст с большой вероятностью является оригинальным. Это обстоятельство делает трудным детектирование этих текстов методом сравнения с дубликатами.

Кратко рассмотрим основные известные методы обнаружения поискового спама.

Для начала заметим, что в настоящее время не разработана строго обоснованная теория, описывающая законы порождения связных осмысленных текстов.

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

Существуют несколько методов решения этой задачи. Рассмотрим кратко некоторые из них.

Методы анализа лингвистических характеристик для обнаружения поискового спама базируются на использовании специального словаря на основе признаков. Применение словаря означает, что генераторы текстов могут "обманывать" данные методы.

Существуют методы анализа содержимого документов для обнаружения поискового спама, которые определяют коммерческую составляющую таких текстов, вычисляя некоторую статистику атрибутов. Эти атрибуты в основном базируются исследовании логов систем контекстной рекламы или логов поисковых запросов. Применение характеристик, которые мало используются словарем, позволяет некоторым генераторам "обманывать" данные методы.

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

Разработаны методы обнаружения спама, в которых анализируются стилистические особенности НТМЬ-кода в страницах. Причем текстовая информация совсем не анализируется.

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

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

Отметим, что задача определения дубликатов текста - это смежная задача детектирования текстов, сгенерированных цепями Маркова. Это следует из того факта, что при увеличении длины цепи, генератор повторяет все большие фрагменты текста-образца.

Детектирование спама, полученного с помощью генераторов текста на основе цепей Маркова, базируется на методах определения жанра и авторства.

В четвертой главе был разработан и проанализирован классификатор спама текстов на основе метода БУМ. Предложена модификация построения разделяющей гиперплоскости с использованием фейеровских отображений.

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

Для решения задачи сильной отделимости обычно применяют итерационный процесс, использующий оператор проектирования. Но реально использование такого метода сильно ограничено из-за того, что часто не получается получить конструктивный оператор, вычисляющий проекцию точки на выпуклое множество. Из-за этого производят замену оператора проектирования последовательностью фейеровских отображений [57]. Кроме того, алгоритмы разделения многогранников на основе оператора проектирования неустойчивы в задачах, где входные данные меняются в процессе решения. А вот алгоритмы на базе фейеровских отображений устойчивы к нестационарным

данным. Так вот, нестационарной задачей является задача о спам-фильтре.

Рассмотрим алгоритмы решения задачи сильной отделимости.

Пусть даны два выпуклых непересекающихся многогранника Mcä"hNc R", заданные системами линейных неравенств:

Ш={х\Ах<Ь}^0\ N={x[Äc<J}^0. (1)

Задача сильной отделимости заключается в нахождения слоя наибольшей толщины, разделяющего М и N. Эта задача равносильна задаче поиска минимального расстояния между М и N в метрике:

p(N,M)=min{||x->>|||xeM,jeN}. (2)

Если Х|<=М и >'ieN есть arg - точки(2) (p(N,M) =||х,-_у,[|), то тогда слоем наибольшей толщины, разделяющий N и М будет: Р= {х|хе Р[ПР2}, ?! и Р2 - полупространства, задаваемые линейными неравенствами:

<x-xbxi-vi >< 0, <y-yi,xi-ух > > О, где < , > - скалярное произведение двух векторов.

Следовательно, задачу сильной отделимости можно сформулировать так:

{xliy]}=Argmin{|!x-.y|| |xeMj;eN}. (3)

Задачу (3) можно решить при помощи известного алгоритма последовательного проектирования.

Алгоритм решения задачи сильной отделимости (91).

Даны два выпуклых непересекающихся многогранника М с if" и N с R", заданные системами линейных неравенств (1).

Обозначим отображение (проектирование) точки на М через 71м» а на N - Лц. Зададим произвольное начальное приближение wo е R". Выберем фиксированное положительное вещественное число е. Тогда алгоритм решения задачи сильной отделимости будет состоять из следующих шести шагов. Шаг 0. к :=0. . Шаг 1. xk+i := 7СМ (щ)-Шаг 2. yk+l := nN (wk). Шаг 3. Wyt+i := (хы +ук+))!2. Шаг 4. к :=к + 1.

Шаг 5. Если гшп{Цлг^+х— Цу*+1-;Ы1} ^ е, то перейти к Шаг 1. Шаг 6. Конец.

Если множества N и М достаточно просты в смысле реализации оператора проектирования точек на них, то алгоритм 91 можно применить на практике. Однако, в случае, когда N и М - произвольные многогранники, то 91 нельзя использовать ввиду того, что не известно универсального метода построения проекции точки на многогранник. Решить эту задачу можно, если заменить оператор проектирования на последовательность фейеровских отображений.

Дадим определение М-фейеровского отображения.

Пусть ф : Я" -> В". Отображение ср называется М-фейеровским, если выполняются следующие два условия:

Ф (У)=У, VУ* м; НФ С*ЫI < \\*-У\\> у

Класс М-фейеровских отображений обозначим через Рм.

Последовательность однозначных М-фейеровских отображений {р* (хо )}П,, при любом начальном значении х0 е Я", будем называть фейеровским процессом.

Известно, что когда однозначное М-фейеровское отображение ф непрерывно, то фейеровский процесс стремится к точке, которая принадлежит М:

М: М.

Это означает, что для любого вещественного е > О существует целое положительное число К, такое, что для всех к > К имеем К -4<е.

Спроектируем М-фейеровское отображение, представив систему линейных неравенств, задающих многогранник М в виде:

М = {х\ Ах < Ь : 7/х) = <а^> - Ь < 0,/= 1,.. .т}, где < а]ух > для любогоЗададим (*) следующим образом:

/;*" (*)= шах {/,(*),оЪ' = 1 ,-т .

Тогда отображение вида:

будет М-фейеровским для любой системы положительных коэффициентов {а; >0}, ] = 1 ,...т, таких, что X"¡ =1 и коэффициентов релаксации 0</,<2.

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

Если дано однозначное непрерывное отображение ср е Рм, то тогда под ф - проектированием (псевдопроектированием) точки хеП" на множество М будет пониматься отображение < ,

которое задается Точку ж1< М называют

псевдопроекцией точки х на множество М.

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

Алгоритм А. Зададим произвольное начальное приближение м^еЛ". Выберем фиксированное положительное вещественное число е. Тогда алгоритм решения задачи сильной отделимости с использованием фейеровских отображений будет состоять из следующих шести шагов.

Шаг 0. к :=0.

Шаг 1. := "I ).

Шаг 2. ук+\ := КМ.

Шаг 3. м>к+\ \=(хкп +у^{)12.

Шаг 4. к :=к+ 1.

Шаг 5. Если || > 8, то перейти к Шаг 1.

Шаг 6. Конец.

Основной вопрос при обосновании применимости алгоритма А к задаче классификации информации заключается в доказательстве сходимости этого алгоритма к требуемому решению.

Обычно, для обоснования сходимости алгоритма А необходимо более сильное свойство, чем просто фейеровость отображения ф, а именно локально - сильное фейеровское отображение. В этом случае сходимость алгоритма строго доказана.

Понятно, что самыми ресурсоемкими шагами в алгоритме А - это Шаг 1 и Шаг 2. В этих шагах выполняется последователь-

ный фейеровский процесс. Результатом является псевдопроекция точки на многогранник. Многогранник, задаваемый системой линейных неравенств, всегда является выпуклым замкнутым множеством, то есть всегда существует решение.

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

Будем производить действия по следующему алгоритму:

1. Берем обучающее множество Q и считываем его термы. Получаем множество термов:

T={tl>t2,...tp},p=l,...\7}.

2. Проводим лексикографическое упорядочивание множества, то есть преобразуем Т в ТЫия т. е. Т —> Tbase, l^barel—| T\i Lbase

\Tbase\-

3. На базе обучающего множества Q формируется частотный словарь слов (термов) Datatable, в котором каждому t,G Tbase, i=l,...,\Lbase\ соответствуют числа: vu - частота встречаемости в Д и v2l- - частота встречаемости в ü2, Datatable={;bVn, V\2, ^2,V21,V22,... tr,Vr\,Vr2), r-Lbase•

4. Берем последовательно все документы d^£2\, r=l, ... \¿2\\.

5. Считываем все термы из документа d¡: TT={tt\,...,ít¡c}, k= \d¡\.

6. Проводим лексикографическое упорядочивание множества ТТ, то есть преобразуем ГГв ТГЫие т. е. ТТ-* TTbasc, \TTbase\<\TI\,

Ibase '^'^¡41 к с- \ •

7. На базе множеств Tbase, TTbase, частотного словаря и вектора

ПрИЗНаКОВ формируем вектор: ^,= {Vn,Vi2,V2i,V22,...;

где p-Lhase, И Vy—0, если tt¡G 1I Y~) Tbase—0. Обозначим множество векторов x¡ через X — {х,}, i= 1, ... \Q\\. Получили множество, соответствующих спаму.

8. Повторяем шаги 4-7, но только для множества i22. Обозначим полученное множество через Y. Получили множество, соответствующее не спаму.

9. Строим по алгоритму Á разделяющую гиперплоскость между X и Y. Получили нормальный вектор к гиперплоскости w и параметр Ъ (порог классификации).

10. Строим классифицирующую функцию Ф'.

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

1. Берем документ (¡¡е.В\£2, г'=1,...

2; Считываем все термы из документа й?,-: ТТ-{П\,...,ик}, к=\сЦ.

3. Проводим лексикографическое упорядочивание множества ТТ, то есть преобразуем 7Тв ТТьюе ТТ->ТТ1ше, \ТГЬте\<\ТТ\, 1Ьа5е = \TTbase\-

4. Определяем множество признаков для данного документа. Если данный признак не определен, то присваиваем лт, = 0.

5. На базе множеств Т1)те, ТТьа$е, частотного словаря и множества признаков формируем вектор х ={4 иУп^гиЪ!,- ■ ^ь \р2, SVu. ■ где р =ЬЬше, \',у=0, если ТТп ТЬа5е= 0.

6. Определяется спайность документа с1, при помощи классификатора: Ф'(х) = б1{*п(<и>, х > + Ь).

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

В собственной коллекции оказались ссылки с 25 сайтов, помещающих спам-ссылки (данные о месте помещения платных ссылок предоставляются владельцем сайта). Количество страниц на любом их сайтах - от 90 до 1000. Количество помеченных (в автоматическом режиме) ссылок: 22500 спам и 7500 не спам ссылок.

Во всех коллекциях произведено выделение ссылок с метками "спам" и не "спам".

Для проверки метода был использован обучающий набор, состоящий из 172 спам-документов и 170 документов не спам. Такие числа были взяты специально для равномерного распределения. В результате был сформирован словарь, содержащий 14386 различных слов.

Эксперименты проводились три раза по неделе каждый на реальном почтовом ящике, созданном более 4 лет назад и который сейчас активно не эксплуатируется.

Результаты работы фильтра на основе разработанного метода представлены на Рис. 2. На этом рисунке представлены все поступившие документы, спам-документы и легитимные документы. Оси X - день, а ось У - число документов.

Спам был пропущен в 1, 2 и 5 день - по 1 документу. Процент пропущенного спама составил 4.83 %(3) от полного числа документов (62).

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

-Ок}ильтровано слана

-Пропущено спама

-Принято за спам легит имньк документов

Результаты (»йоты фиьтра на огнове разработанного мэтода за период с 1 го 7 очтября 2012 г.

Рис. 2. Результаты работы фильтра на основе разработанного

метода

Заключение

В заключении приведены основные результаты диссертационной работы:

1. Определены основные тенденции и закономерности развития систем классификации информации. Показано, что разработка систем классификации информации, используя различные подходы, является актуальной задачей.

2. Проведен анализ на предмет использования различных подходов при разработке систем классификации спама.

3. Проведен анализ математических моделей массово порождаемых неестественных текстов.

4. Разработан и реализован метода построения разделяющей гиперплоскости в гильбертовом пространстве на основе фейеровского отображения для решения задачи сильной отделимости.

5. Разработаны математические модели построения обучающей выборки.

6. Реализован спам-фильтр на основе разработанного метода. Испытания на реальном почтовом ящике показали, что разработанная система допускает ошибку первого рода (ложное срабатывание) не больше 1.86 % и допускает ошибку второго рода (пропуск события) не больше 4.83 %.

Дальнейшее направление исследований. Разработанный алгоритм определения спамности документа, или классификации, конечно же имеет свои недостатки. Это видно из анализа проведенных экспериментов. Но попытка построить для решения задачи классификации один алгоритм, удовлетворяющих всех, заранее обречена на провал. Поэтому есть идея, в основе которой лежит композиционное объединение нескольких алгоритмов. В этом случае возможна компенсация погрешности разных алгоритмов. Но сразу возникает много проблем, строя такие композиции. Например, при каких условиях качество композиции окажется выше, чем у отдельных базовых алгоритмов? Как настроить базовые алгоритмы, считая, что они будут функционировать в составе композиции? Можно ли использовать для их настройки стандартные методы обучения? Какое минимальное число базовых алгоритмов? Формально, эти вопросы можно записать следующим образом. Пусть имеется задача обучения по прецедентам {Х,Уу У1}, где X - множество объектов; У - множество ответов; у* :Х—* У— отображение (неизвестная целевая зависимость); X1 = {х{, ..., х/) - обучающая выборка; У1 =(уь...,у/)-вектор ответов на обучающих объектах, угу (*/)•

Требуется построить алгоритм а1&Х—*У, аппроксимирующий целевое отображение у на множестве X.

Введем так называемое пространство оценок R. Рассмотрим алгоритмы, которые представляются в виде суперпозиции:

alg(x) = аНх)), где b : X—► R алгоритмический оператор,

/7: R—>Y- решающее правило.

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

В работе был использован вариант:

7= {-1,+1}, /7(z) = sign(z), aig(x) = Ф'(х) = sign(<w,x > + b).

Так вот, разработкой теоретических положений построения

alg(x) = mix))

и будут посвящены дальнейшие научные исследования, которые позволят повысить эффективность фильтрации спама.

Перечень опубликованных автором работ по теме диссертации

1. Блинов С.Ю., Коробейников А.Г., Кувшинов С.С., Лейман A.B., Кутузов И.М. Цифровые водяные знаки в графических файлах//Научно-технический вестник информационных технологий, механики и оптики -СПб: СПБНИУ ИТМО, 2013, 1(83)- с.152 - 157.

2. Блинов С.Ю., Коробейников А.Г., Кувшинов С.С., Лейман A.B. Генерация цифровых водяных знаков в графических файлах //Программные системы и вычислительные методы. - Москва: М: "НБ-Медиа", 2013.-Вып. 2.-№1. - Модели и методы управления информационной безопасностью. - С. 35 - 44. - 144 с. - ISSN 2305-6061.

3. Блинов С.Ю., Коробейников А.Г., Кувшинов С.С., Лейман A.B., Нестеров С.И. Разработка стеганоалгоритма на базе форматных и пространственных принципов сокрытия данных//Научно-технический вестник информационных технологий, механики и оптики - СПб: СПБНИУ ИТМО, 2012, 1(77)- с. 116 -119.

4. Блинов С.Ю., Коробейников А.Г., Лейман А.В.Методы систематизации разнородной информации для задачи фильтрации спама//Информационные технологии в профессиональной

деятельности и научной работе: сборник материалов Всероссийской научно-практической конференции с международным участием: в 2 ч. - Йошкар-Ола: Марийский государственный технический университет, 2012. - Т. 1. - С.20-24. - 232 с. - ISBN 978-5-8158-1002-0.

5. Блинов С.Ю., Коробейников А.Г., Лейман A.B., Святкина М.Н. Мониторинг объектов на базе мультиагентных систем интеллектуальных агентов магнитных измерений.//Материалы 1-го Международного симпозиума "Гибридные и синергетические интеллектуальные системы: теория и практика". Изд-во БФУ им. И.Канта, 2012. - Т. 2. - С. 155-160. - 444 с. - ISBN 978-5-9971-0212-8.

6. Блинов С.Ю., Коробейников А.Г., Лейман A.B., Демина Е.А. Систематизация разнородной информации в задаче фильтрации спама// В книге "Труды конгресса по интеллектуальным системам и информационным технологиям AIS-IT'12. Научное издание в 4-х томах. М.:Физматлит, 2012, -Т.2. стр.18-22.

7. Блинов С.Ю., Коробейников А.Г., Лейман A.B., Маркина Г.Л., Кутузов И.М. Разработка алгоритма определения спамности документов на основе фейеровских отображений//Научно-технический вестник информационных технологий, механики и оптики - СПб: СПБНИУ ИТМО, 2012,6(82)- с. 123 -127.

8. Блинов С.Ю., Коробейников А.Г., Кувшинов С.С., Лейман A.B. Анализ принципов создания и работы стеганографических алгорит-мов//Программные системы и вычислительные методы. - Москва: М: "НБ-Медиа", 2012,-Вып. 1.-№ l.-Модели и методы управления информационной безопасностью. - С. 28 - 36. - 102 с. - ISSN 2305-6061.

9. Блинов С.Ю., Коробейников А.Г., Сидоркина И.Г., Лейман A.B. Алгоритм классификации информации для решения задачи фильтрации нежелательных сообщений//Программные системы и вычислительные методы.-Москва: М:"НБ-Медиа",2012.- Вып.1.-№ 1.-Математическое и программное обеспечение новых информационных технологий. - С. 89-95.-102 c.-ISSN 2305-6061.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел.(812)233 46 69. ' Объем 1,0 у.п.л. Тираж 100 экз.

САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

На правах рукописи

04201360082

Блинов Станислав Юрьевич

Методы и алгоритмы классификации информации для защиты от спама

Специальность: 05.13.19. Методы и системы защиты информации, информационная безопасность

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., проф. Коробейников Анатолий Григорьевич

Санкт-Петербург 2013 г.

Оглавление

Введение...............................................................................................................4

Глава 1. Анализ тенденций и закономерности развития систем классификации информации..............................................................................9

1.1 Анализ тенденций развития систем классификации..............................9

1.2 Основные методы классификации.........................................................12

1.2.1 Иерархический метод классификации.............................................12

1.2.2 Фасетный метод классификации......................................................13

1.2.3 Дескрипторный метод.......................................................................13

1.2.4 Метод "ближайшего соседа" или системы рассуждений на базе аналогичных случаев..................................................................................14

1.2.5 Многомерная классификация...........................................................16

1.3. Спам..........................................................................................................18

1.3.1 Понятие о спаме................................................................................18

1.3.2 Спам без вложений...........................................................................18

1.3.3 Спам с вложением..............................................................................21

1.3.4 Многочисленные методы рассылки.................................................27

1.3.5 Ущерб от спама спама.......................................................................28

1.3.6 Методы борьбы со спамом...............................................................31

1.4 Выводы по главе.......................................................................................33

Глава 2. Постановка и алгоритмы решения задачи классификации............35

2.1 Математическая постановка задачи классификации............................35

2.2 Обзор основных алгоритмов классификации........................................36

2.3. Метод опорных векторов........................................................................39

2.3.1 Основные преимущества БУМ.........................................................43

2.3.2 Основные недостатки 8УМ.............................................................44

2.3 Выводы по главе.......................................................................................45

Глава 3. Основные методы порождения и обнаружения поискового спама. Математические модели генерации неестественных текстов......................46

3.1 Методы порождения поискового спама.................................................46

3.2 Методы обнаружения поискового спама...............................................49

3.3. Математические модели генерации неестественных текстов............51

3.4 Выводы по главе.......................................................................................56

Глава 4. Разработка и анализ метода классификации текстов на базе метода опорных векторов..............................................................................................57

4.1. Разработка алгоритма решения задачи защиты от спама при нестационарных данных на базе БУМ.........................................................57

4.2. Алгоритмы решения задачи сильной отделимости.............................59

4.3 Создание обучающей выборки...............................................................64

4.4 Признаки ссылочного спама...................................................................67

4.5 Алгоритм определения спамности документа......................................72

4.6 Выводы по главе.......................................................................................73

Глава 5. Результаты экспериментального исследования разработанного метода..................................................................................................................74

5.1 Подготовка обучающей выборки...........................................................74

5.2 Результаты экспериментов......................................................................76

5.2.1 Полученные результаты и анализ первого эксперимента.............76

5.2.2 Полученные результаты и анализ второго эксперимента.............79

5.2.3 Полученные результаты и анализ третьего эксперимента............82

5.2.3 Результаты сравнения и анализ с Kaspersky Anti-Spam.................85

5.2 Выводы по главе.......................................................................................87

Заключение.........................................................................................................88

Список литературы............................................................................................91

Введение

Актуальность работы.

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

Классификация информации в сетях, и в частности в сети Интернет, позволяет решать различные задачи, например: документооборот, автоматическое аннотирование и реферирование, машинный перевод, составление интернет-каталогов, ограничение области поиска в поисковых системах, определение кодировки и языка текста, классификация новостей и т.д.

В России активно развиваются системы автоматической классификации текста и специализированные системы полнотекстового анализа, позволяющие производить автоматическую классификацию и реферирование текстов, например, "Следопыт", "ТекстАналист" и другие.

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

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

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

В настоящее время существуют технологии создания фильтров-сервисов отсекания навязываемой информации. Их принято разделять на два класса: настраиваемые вручную и автоматизированные. Технологии из первого класса применяют списки доступа и настраиваются пользователем, выбирающему или запрещенные, при политике «черного списка», или разрешенные, при политике «белого списка», адреса. Но такие разделения навязываемой информации неэффективны так как необходимо частое обновление списков доступа. Кроме того, ручная категоризация неприменима, если необходимо классифицировать большой объем информации за ограниченное время.

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

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

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

Увеличить эффективность таких фильтров можно, если учесть семантические связи у термами. Но это потребует применения методов

семантического анализа, что вызовет увеличение нагрузки на систему, то есть приведет к изменению времени обработки документов фильтром.

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

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

Все вышесказанное определило цели и задачи диссертационного исследования.

Целью диссертационной работы является повышение эффективности фильтрации информации в сети Интернет с использованием разработанных методов и алгоритмов.

Для достижения поставленной цели в диссертационном исследовании были сформулированы и решены следующие задачи:

• Разработка и анализ алгоритмов детектирования текстового спама на базе машинного обучения.

• Исследование моделей массово создаваемых неестественных текстов.

• Разработка и реализация метода построения разделяющей гиперплоскости в гильбертовом пространстве на основе фейеровского отображения для решения задачи сильной отделимости.

• Разработка системы классификации информации в Интернете, удовлетворяющей следующим условиям:

-точность и полнота обнаружения спам-документов; - применимость к различным естественным языкам.

Объектом исследования методы и модели классификации информации в Интернете.

Методы исследования. Решение вышеперечисленных задач происходит с применением методов теории защиты информации, системного и структурного анализа, функционального анализа и методов математического моделирования.

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

Положения, выносимые на защиту:

1. Математические модели построения обучающей выборки.

2. Метод построения разделяющей гиперплоскости обучающей выборки на базе фейеровского отображения;

3. Алгоритм классификации документов.

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

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

Апробация работы. Основные положения диссертационного исследования докладывались и обсуждались на международных конгрессах и конференциях различного уровня: Всероссийская научно-

практическая конференции с международным участием. Йошкар-Ола: Марийский государственный технический университет, 2012; 1-ый Международный симпозиум "Гибридные и синергетические интеллектуальные системы: теория и практика". Россия, Калининград, БФУ им. И.Канта, 2012; Международный конгресс по интеллектуальным системам и информационным технологиям AIS-IT'12. Россия, Дивноморское (Геленджик), 2012.

Результаты исследований реализованы в СПб НИУ ИТМО и используются в учебном процессе при проведении занятий по дисциплинам: «Защита информации», «Информационная безопасность», «Информационная безопасность и защита информации».

Публикации. По тематике диссертации опубликовано девять работ, в том числе три работы входят в список рекомендованных ВАК для защиты кандидатских диссертаций.

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы.

Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, изложенных на 98 листах машинописного текста, содержит 14 рисунков и 11 таблиц. Список литературы включает 62 наименования.

Глава 1, Анализ тенденций и закономерности развития систем классификации информации

1.1 Анализ тенденций развития систем классификации '

В настоящее время, по различным оценкам, объем информации увеличивается экспоненциально. Поэтому одной актуальнейших научных задач является систематизация (классификация) информации, в т. ч. в Интернете.

Классификация (категоризация, рубрикация) документов (text categorization, text classification, topic spotting) - является одной из задач информационного поиска, результат который заключается в занесении документа в одну из категорий на основании содержания документа (Рис. 1.1).

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

Классификация на основе правил широко применялась до начала 1990-х гг. [1-2]. В соответствии с правилами, написанными экспертами, документ относился к той или иной категории. Часто правила имели форму регулярных выражений. Таким образом, от эксперта требовалось не только знание предметной области, но и навыки написания правил. Этот подход в некоторых случаях превосходит по точности другие методы, однако для поддержания базы правил в актуальном состоянии необходима постоянная работа эксперта, поэтому в 90-х гг. правила сменились машинным обучением [1-2], которое базируется на методах распознавания образов, искусственного интеллекта, математической статистики и т.д.

Рис. 1.1 Обобщенная схема задачи классификации информации

Автоматической классификации предшествует этап индексирования документов. Индексация - это процесс приведения документа к единому формату. Индексирование включает в себя построение модели документа и уменьшение размерности. Наиболее распространенными моделями документов являются варианты моделей множества слов (bag-of-words), а именно бинарная модель и модель с весами терминов. Бинарная модель учитывает только наличие или отсутствие слова в документе, во взвешенной же модели каждому термину ставится в соответствие его вес.

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

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

Все методы классификации базируются на отношение эквивалентности (equivalence relation) [3]. При решении задачи классификации какого-нибудь множества, определяют одно или несколько отношений эквивалентности и после этого исследуют классы эквивалентности, заданные этими отношениями.

Далее рассмотрим основные методы классификации объектов [410].

1.2 Основные методы классификации

1.2.1 Иерархический метод классификации

Учтя задаваемую определенным образом процедуру создания классификационной структуры, перед началом работы требуется знание признаков, при наличии которых объект относится к какому-то классу. Эти признаки и будут признаками классификации. Иерархический метод классификации подразумевает, что любой объект на каждом уровне относится к одному классу, характеризуемым конкретным значением своего классификационного признака [11-14].

В следующей операции группирования в любом новом классе задаются свои конкретные классификационные признаки. Следовательно, набор классификационных признаков зависит от семантического содержания класса, в котором требуется группировка на следующем уровне иерархии. Число уровней классификации, которое соответствует количеству классификационных признаков, определяет глубину классификации.

Преимущества иерархической системы: достаточно простая процедура создания и применение классификационных признаков в различных ветвях иерархической структуры.

Недостатками иерархической системы являются: жесткая структура, приводящая к проблемам модификации, так необходимо переформировать существующие классификационные группировки; невозможность группировки объектов по неизвестным или заранее не определенными группами признаков.

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

1.2.2 Фасетный метод классификации

В отличие от иерархического метода классификации, данный метод выбирает независимые друг от друга классификационные приз�