Тема доклада Метод обнаружения изменений структуры веб-сайтов в системе сбора новостной информации

Задача сбора новостной информации

Задача обнаружения сбоев Последствия изменения структуры веб-сайта: Данные не извлекаются (проблема может быть обнаружена самой системой сбора) Извлекаются некорректные данные (для обнаружения проблемы необходима подсистема детектирования)

Подходы к обнаружению сбоев Оперативное обнаружение анализируется только одна веб- страница Отложенное обнаружение анализируется набор из нескольких веб- страниц

Анализ одной веб-страницы +: скорость реакции на сбой - : частые ложные срабатывания

Анализ набора веб-страниц +: высокое качество проверки - : задержка обнаружения сбоя

Двухступенчатый анализ веб-страниц

Модель документа Характеристики документа: P – объем веб-страницы S – суммарный размер параграфов N – количество параграфов в статье V – дисперсия размера параграфа в рамках статьи Класс html-элементовХарактеристика H – гиперссылкиTHTH B – текстовые блокиTBTB S – форматированиеTSTS I – изображенияTITI O - прочееTOTO

Модель набора документов 1 Характеристики, описывающие свойства текста: Формула Стерджесса: Области значений разбиваются на m интервалов равной длины

Модель набора документов 2 Характеристики, описывающие свойства разметки: Количество тэгов различных классов в наборе документов: Модель набора документов:

Принципы оперативного детектирования 1 Методы бинарной классификации SVM Логистическая регрессия Наивный байесовский классификатор

Принципы оперативного детектирования 2 Распределение значений параметров N и P для kp.ru подозрительные статьи

Измененная модель документа Требования к векторам: небольшая размерность отсутствие бесполезных векторов Тэги: Остальные параметры:

Основные требования к методу кластеризации Небольшое количество кластеров Гиперсферическая форма кластеров Высокая плотность кластеров

Методы кластеризации Итерационные –Метод k-средних –EM-алгоритм Иерархические –Метод одиночной связи –Метод полной связи –Метод средней связи

Предложенный алгоритм кластеризации 1.Выбрать из множества документов n элементов 2.Произвести кластеризацию методом средней связи 3.Найти центроиды полученных k кластеров 4.Поместить центроиды в множество элементов 5.Повторять пункты 1-4 до достижения нужного числа элементов 6.Определить принадлежность исходных элементов кластерам Максимальное быстродействие достигается при n=2*k

Ограничивающие поверхности гиперпараллелепипеды гиперэллипсоиды гиперсферы

Отложенный детектор Анализ сходства тестовой и эталонной выборок Эталонная (lenta.ru) Тестовая (корректные данные - lenta.ru) Тестовая (некорректные данные – cnews.ru) 3 выборки случайной величины S:

Оценивание сходства выборок Расстояние Кульбака-Лейблера (KLIC) Статистический рядKLICКритерий Необходимо задать пороговое значение K:

Пороговая функция 1 Простая пороговая функция:

Пороговая функция 2 Универсальная пороговая функция: Коэффициенты определяются методом наименьших квадратов

Функциональная схема системы детектирования

Исходные данные для экспериментов Источники данных: –mail.ru –itar-tass.com –kp.ru –rbc.ru –kommersant.ru –ria.ru –rambler.ru Параметры детектора: –Пороговое значение при самопроверке: 10% –Количество кластеров, формируемых оперативным детектором: 10 Эталонные данные: –72888 корректных документов Тестовые данные –5169 корректных документов –356 некорректных документов

Эксперимент 1. Оперативный детектор Ложные срабатывания оперативного детектора M L - размер обучающей выборки M T - размер тестовой выборки M S - средний размер анализируемого набора документов при самопроверке N D - количество подозрительных статей N S - количество подозрительных статей после самопроверки ИсточникMLML MTMT MSMS NDND NSNS mail itar-tass kp rbc kommersant ria rambler Всего:

Эксперимент 1. Отложенный детектор Ложные срабатывания отложенного детектора ИсточникMLML MTMT FPFP FSFS FNFN FVFV FTFT NFNF mail из 5 itar-tass из 5 kp из 5 rbc из 5 kommersant из 5 ria из 5 rambler из 5 Всего: из 35 M L - размер обучающей выборки M T - размер тестовой выборки F P, F S, F N, F V, F T - значения критериев N F - количество критериев, показавших наличие сбоя

Эксперимент 2. Оперативный детектор Пропуск сбоев оперативным детектором M L - размер обучающей выборки M T - размер тестовой выборки M S - средний размер анализируемого набора документов при самопроверке N D - количество подозрительных статей N S - количество подозрительных статей после самопроверки ИсточникMLML MTMT MSMS NDND NSNS mail itar-tass kp rbc kommersant ria rambler Всего:

Эксперимент 2. Отложенный детектор Пропуск сбоев отложенным детектором M L - размер обучающей выборки M T - размер тестовой выборки F P, F S, F N, F V, F T - значения критериев N F - количество критериев, показавших наличие сбоя ИсточникMLML MTMT FPFP FSFS FNFN FVFV FTFT NFNF mail из 5 itar-tass из 5 kp из 5 rbc из 5 kommersant из 5 ria из 5 rambler из 5 Всего: из 35

Основные результаты Характеристики разработанного подхода к обнаружению сбоев: Двухступенчатый анализ Быстрая иерархическая кластеризация Сравнение выборок с помощью расстояния Кульбака- Лейблера Использование пороговой функции Качество работы оперативного детектора: 99,54% на корректных данных 100% на некорректных данных Качество работы отложенного детектора: 97,14% на корректных данных 77,15% на некорректных данных