CREATION OF OPTIMUM SPAM FILTER ON THE BASIS OF COMBINATION OF STATISTICAL QUALIFIERS

Full Text

Введение В предыдущих работах авторов освещались вопросы реализации спам-фильтра в интерактивных частях сайтов в сети Internet на основе применения модифицированных методов Байеса и Фишера [1-2]. В данной статье излагаются подходы к тестированию разработанных классификаторов и оценке работы совмещенного фильтра. Критерии оптимальности при классификации сообщений на основе статистических методов Предположим, что вся совокупность сообщений подразделяется на классы A и B, где A - класс спам-сообщений, B - класс не спам-сообщений. Задача соотнесения сообщения к одному из этих классов напрямую связана со статистической проверкой гипотез: простой гипотезы HA: XGA против альтернативной HB: ХЄВ, где Xесть признак, характеризующий сообщения. Как известно из математической статистики, при этом если сообщение принадлежит классу A, а его соотнесли к B, то будет допущена ошибка первого рода, условная вероятность которой равна а - уровень значимости. Это будет ошибкой выбора альтернативной гипотезы HB вместо правильной H Если же справедлива гипотеза HB, но при этом выбрана HA, то будет допущена ошибка второго рода, условная вероятность которой равна ß . Ошибка первого рода, или ложноотрицательная ошибка, будет допущена, если спам-фильтр ошибочно пропускает нежелательное сообщение, определяя его как не спам (пропуск спама или недостаточная полнота метода). В то же время как спам-фильтр способен распознать большой процент нежелательных сообщений, может стать более важной задача минимизация числа ошибочных отсечений нужных сообщений, т.е. минимизация ошибки второго рода. Ошибка второго рода, или ложноположительная ошибка, будет допущена, если спам-фильтр ошибочно классифицирует легитимное сообщение как спам (ложные срабатывания или точность метода). Спам-фильтр будет эффективным при низком уровне таких ошибок, то есть при минимальной ошибке второго рода. Однако в настоящее время все антиспамовые системы имеют корреляцию между ошибками первого и второго родов. В классификаторах обычно допускают компромисс между приемлемым уровнем ошибок первого и второго рода и при принятии решения используют пороговые значения, которые могут варьироваться. От этого зависит, насколько классификатор более «строгий» или более «мягкий». В качестве порогового значения выбирают уровень значимости, который задают при проверке статистических гипотез. При этом повышение чувствительности фильтра приводит к увеличению ошибки первого рода (пропуск спама), а понижение чувствительности - к увеличению ошибки второго рода (ложные срабатывания). Критерий оптимальности Байеса Для оценки качества классификации, необходимо учитывать потери, связанные с ошибками первого и второго родов. Для этого пространство признака X разделим точкой x0 на два полупространства XA и XB. Пусть c1 - условная цена ошибки первого рода, c2 - условная цена ошибки второго рода, P(A) - априорная вероятность класса A, P(B) - априорная вероятность класса B, P(A) + P(B) = 1. Величины c1 и c2 зависят от коэффициентов матрицы цен C2x2 = {c „} и от ошибок первого и второго родов: ci = ci2 а +сц(1 - а); (1) c2=c2iß +с22(1 - ß). (2) Эти величины также называют условными рисками при справедливости гипотез HA и HB соответственно. В соответствии с теорией принятия решений введем решающее правило классификации, минимизирующее функцию потерь (риска) [3]: R = ClP(A) + c2P(B), (3) где c1 и c2 определяются выражениями (1) и (2). Функция (3) представляет собой средний риск, причем зависящий от порогового значения х0 , так как величины c1 и c2 через ошибки первого и второго родов зависят от значения х0 , следовательно, ошибки первого и второго родов коррелированы между собой. Минимальное значение R функции риска min ~J г (3), достигаемое в точке х0 , называется байесовским риском. «Инфокоммуникационные технологии» Том 11, № 4, 2013 Тарасов В.Н., Мезенцева Е.М. 55 Ж1. f2(x) С21 С22 Р(В) (4) С12 ci і Р( А) где у(х)иУ2(х) плотности вероятностей распределения признака X по классам A и B соответственно. Правая часть в выражении (4) называется отношением правдоподобия, которое является постоянным для данного выбора с.. . При этом, если имеет место неравенство то наблюдаемый век- ^ С21 С22 Р(Р) f г(Ж) С12—С11 Р(-4) тор X относится к классу A, в противном случае вектор X относится к классу B. Если же выполняется равенство /,(х) С„-Са Р(В) /.(*) сч~сп А+ то наблюдаемый вектор X относится к одному из классов A или B. Последнее выражение представляет собой уравнение границы классов A и B. Сформулированное решающее правило принятия решений относится к так называемым правилам Байеса [3-4]. Такую методику можно применять ко многим практическим задачам, формулируя их в терминах статистической теории принятия решений, но эта теория ограничена допущением, что плотности вероятностей /ХЖ и fifö) известны. Но чаще всего на практике функции /і(х) и/2(х) неизвестны, и необходимо определить их оценки f (x\f {х) по обучающим выборкам аппроксимативными методами [3-4]. Последнее сильно будет тормозить работу классификатора. Учитывая данный факт, в работе выбран следующий подход, заключающийся в получении оценок /№),?№) только на малых обучающих выборках объема 100-200 на стадии обучения фильтра, а сам критерий оптимальности с получением таких оценок в работу программы не включен. Результаты х экспериментов на обучающих выборках, позволили определить оптимальные пороговые значения для принятия решений: хв = 0,95 для верхнего порога и хш = 0,4 для нижнего порога. Тем самым были установлены жесткие рамки по спаму и обычные для не спам-сообщений. Такие пороговые значения обеспечивают минимум пропуска в спам нужных сообщений, то есть минимум ложных срабатываний. Следует заметить, что каждый администратор сети может иметь свои предпочтения и легко может задать угодные ему значения пороговых значений. Для оценки алгоритмов фильтрации сообщений используют комбинацию двух критериев оценки качества: Доля пропущенного спама Этот параметр обозначает количество нормальных сообщений оцененных как спам к общему количеству сообщений со спамом в тестовом наборе. Этот критерий характеризует пропуск спама алгоритмом. Таким образом, 15% пропусков (85% уровень фильтрации спама) означают, например, что всего пришло 1000 спамовых писем, из которых 150 не было распознано как спам. Доля ложных срабатываний Это отношение количества нормальных сообщений, ошибочно распознанных алгоритмом как спам, к общему количеству нормальных сообщений в тестовом наборе. Этот критерий характеризует, насколько редко алгоритм ошибается, помечая нормальные сообщения как спам. Таким образом, 0,5% ложных срабатываний означают, например, что всего пришло 1000 легитимных сообщений, и из них 5 было ошибочно признано спамом. Критерий на основе доли «пропущенного спама» является наиболее понятным интуитивно - если один классификатор распознает 70%, а второй - 80% спама, то второй спам-фильтр можно считать лучшим. Однако, с другой стороны, необходимо знать, что повышение уровня распознавания влечет за собой рост количества ложных срабатываний. Это означает, что ошибки первого и второго родов при принятии решений в задаче классификации коррелированны между собой. Поэтому оба критерия нужно рассматривать совместно, причем оценка количества ложных срабатываний должна иметь приоритет при составлении суммарной оценки фильтра. Полностью избавиться от данных ошибок невозможно, но необходимо максимально уменьшить их число. Особенности тестирования и обучения спам-фильтра Так как мы ведем речь о байесовских и им подобных классификаторах, то есть об обучаемых пользователем системах, то при их тестировании необходимо использовать тот режим обучения, который будет применяться при реальной эксплуатации. Таким образом, необходимо проводить регулярное обучение системы по пропущенному спаму и ложным срабатываниям, сделав это тем самым штатным режимом эксплуатации спам-фильтра в конкретной организации. «Инфокоммуникационные технологии» Том 11, № 4, 2013 56 Тарасов В.Н., Мезенцева Е.М. Достоверные результаты тестирования можно получить при выполнении следующих необходимых условий: - тестирование должно проводиться с установкой спам-фильтра на тот же поток сообщений на форуме, где его предполагается в дальнейшем использовать; - продолжительность тестирования - несколько недель; - объем тестируемого набора документов - от нескольких сотен до нескольких тысяч сообщений в день; - анализ результатов с использованием кор -ректного определения категорий спама/не спама, ложных срабатываний и пропуска спама. Из сказанного следует, что спам-фильтр, обученный в одной организации, не обязательно будет хорошо работать в другой организации. Это является недостатком всех обучаемых фильтров. Его можно устранить быстрым обучением фильтра, организовав «коллективное обучение» совместно на веб-сервере верхнего уровня управления спам-фильтром и серверах уровня сайтов, на основе обмена данными по модификации базы данных веб-сервера. Для приукрашивания реальной картины при рекламировании спам-фильтров довольно часто используют результаты тестирования при условиях, когда один фильтр используется на наборе спам-сообщений, полученном при работе другого фильтра. При этом если у второго фильтра случится пропуск спама, обнаруженного первым фильтром, то второй считается хуже, чем первый. Однако на самом деле данное утверждение несправедливо, так как такое может случиться и с первым фильтром при тех же условиях тестирования. Поэтому необходимо проводить анализ множества результатов работы отдельных фильтров и подмножества их пересечений Нами предлагается подход к организации классификатора, который заключается в совместном использовании методов Байеса и Фишера для повышения качества фильтрации на основе анализа подмножеств пересечения множеств, распознанных обоими методами (спам - не спам, ложные срабатывания и пропуск спама). Пусть S = {st} (/ =1 ... M - множество документов (сообщений), включающее как легитимные, так и спам-сообщения; Sp CI S и Sp CI S - множества документов, распознаваемые соответственно классификаторами Байеса и Фишера. Тогда подмножество - пересечение SBflSF по всем вышеуказанным категориям может быть использовано для оценки качества работы совмещенного фильтра (см. рис. 1). Рис. 1. Иллюстрация меры близости двух множеств Sb и Sf Полнота такого пересечения SBflSF также будет давать оценки для подмножеств STS и S \ B F F SB. В качестве меры близости двух множеств SB и SF предложено использовать абсолютную меру N(SBfl SF) - число общих документов в этих множествах. Таким образом, в работе в качестве оптимального критерия для оценки качества обучения спам-фильтра принимается максимальное значение меры по категориям l (спам - не спам, ложные срабатывания, пропуск спама): ЛД S^n S^p) —»max. После достижения наилучших показателей меры близости множеств SB и SF по всем категориям, администратор может сделать выбор, каким фильтром в дальнейшем ему пользоваться (см. рис. 2). Заключение Предложенная общая схема оценки качества обученности совмещенного фильтра включает следующие этапы (см. рис. 3): - построение множеств спам-сообщений: легитимных, ложных срабатываний и пропуска спама на основе фильтра Байеса; - построение множеств спам-сообщений: легитимных, ложных срабатываний и пропуска спама на основе фильтра Фишера; - выполнение операции пересечения по спам-сообщениям, общим для обоих фильтров; - выполнение операции пересечения по легитимным сообщениям, общим для обоих фильтров; - выполнение операции пересечения по ложным срабатываниям, общим для обоих фильтров; - выполнение операции пересечения по пропускам спама, общим для обоих фильтров. В этом случае действительно будет возможно оценить все компоненты общей картины: - спам-сообщения, которые улавливаются обоими фильтрами; - спам-сообщения, которые улавливаются только фильтром Байеса или только фильтром Фишера; - одновременные ложные срабатывания обоих фильтров; «Инфокоммуникационные технологии» Том 11, № 4, 2013 Тарасов В.Н., Мезенцева Е.М. 57 - ложные срабатывания каждого фильтра по отдельности; - одновременный пропуск спама обоими фильтрами; - пропуск спама каждым фильтром по отдельности. Только имея такую полную картину, можно обоснованно сравнивать качество обученности совмещенного фильтра. Рис. 3. Схема оценки качества работы совмещенного

About the authors

V. N Tarasov

Email: vt@ist.psati.ru

E. M Mezentseva

Email: katya-mem@psuti.ru

References

Supplementary files