Проблемы построения систем защиты от спама в Интернете Карбачинский И.О.

Виды спама - Почтовые рассылки - SMS спам - Спам в мессенджерах - Выдача поисковой системы

Антиспам система бинарный классификатор С = { 0 – не спам, 1 – спам }

Построение классификатора Шаг 1: Составляем размеченную выборку ClassUrl Spamhttp:// Spamhttp://bancdyx.narod.ru/znakomstva-transseksulka.html Not Spamhttp://dating-01.narod.ru/znakomstva-moskva-siando.html Spamhttp://defushka-vapen.narod.ru/prostitutki-g-vologda.html Not Spamhttp:// Spamhttp://

Построение классификатора Шаг 2: Обучающее и проверочное множества ClassUrl Spamhttp:// Spamhttp://bancdyx.narod.ru/znakomstva-transseksulka.html Not Spamhttp://dating-01.narod.ru/znakomstva-moskva-siando.html Spamhttp://defushka-vapen.narod.ru/prostitutki-g-vologda.html Not Spamhttp:// Spamhttp://

Построение классификатора Шаг 3: Выделяем признаки. Нормализация ClassFeature1Feature2...FeatureN Spam Spam Not Spam Spam Not Spam Spam F: (f1, …, fn) (0,1)

Построение классификатора Пусть X множество объектов Y множество классов {0,1} X* обучающая выборка из X. Также известно h*: X* Y Задача: Для, найти h: X Y.

Как найти h(x)?

Построение классификатора Шаг 4: Выбираем алгоритм обучения и строим модель KNN Байесовские методы Нейронные сети Деревья решений SVM...

Построение классификатора Шаг 4: Оценка качества

Классификатор спама Большое обучающее множество ( > страниц) Долго обучается ( > 10 часов ) Сотни признаков Обучить несколько моделей нельзя Необходимо постоянно пополнять обучающее множество и заново обучать классификатор Скорость / Надежность / 24x7

Плохое качество! Что делать? Плохое обучающее множество Плохой алгоритм обучения Плохо подобраны признаки

Feature Selection Много алгоритмов Большинство неприменимы к большим объемам данных Некоторые алгоритмы содержат в себе отбор признаков Большинство методов требует построения модели на каждой итерации Wrapper, Filter, Embeded методы

Minimum-redundancy-maximum-relevance (mRMR) X – множество признаков, С – класс. U – произвольное подмножество признаков из X - вектор значений k-ого признака из U - взаимная информация признаков Избыточность подмножества признаков: Релевантность подмножества признаков: Критерий MRMR:

Minimum-redundancy-maximum-relevance (mRMR) Не требует построения модели Быстрая скорость работы Упорядоченный рейтинг признаков Показывает избыточные признаки Прирост качества

Как еще уменьшить размерность простарнства признаков? Сжать без потери информации! 1. Principal component analysis 2. Random Projection

Principal component analysis X – множество признаков Представим X в виде произведения двух матриц T ( ) и P ( ), z < n. T – матрица счетов, P – матрица нагрузок. После разложения матрицы в композицию матриц T, P и E, вводятся новые, формальные переменные: - линейная комбинация исходных переменных.

Проблема переобучения Явление, когда построенная модель хорошо объясняет примеры из обучающей выборки, но достаточно плохо работает на примерах, не участвовавших в обучении (на примерах из тестовой выборки). Способы борьбы: 1. Cross-validation 2. Регуляризация

Спасибо! Вопросы?