Обнаружение структурного подобия HTML-документов И. Некрестьянов Е. Павлова

Задача извлечения информации Информация с регулярной структурой зачастую скрыта среди презентационных деталей Детали форматирования могут различаться даже в одном источнике Огромный объем информации => Извлечение структурированной информации и выполнение запросов

Типы подходов к извлечению информации Специализированные языки Использование HTML-разметки Работа с текстами на естественном языке Индуктивные подходы Моделирование искомой информации Использование онтологии

Рассматриваемая задача Контекст: Автоматическая генерация посредника для извлечения информации подразумевает наличие образцов. Проблема: Как подбирать их автоматически? Общая идея: Кластеризация документов по структурному подобию.

Агломеративно-иерархическая кластеризация Стандартный статистический метод Результат – дерево (не надо знать искомое число кластеров) Построение «снизу- вверх»

Как представлять документы? Basis(k, l, attr) Модель DOM Имя тэга Входящий путь длины k Потомки на глубину l Атрибуты тэга … k l

Как вычислять веса? Наличие признака (0/1) Количество вхождений признака Частота встречаемости признака TFIDF

Что такое хороший результат? Классический подход – сравнение с идеалом или другим результатом Цель: автоматически обработать максимум документов «Хороший» кластер: – Все документы обрабатываются одним посредником – Кластер достаточно велик (N>2)

Меры для оценки Энтропия (характеризует «чистоту» кластеров) Доля документов, которые находятся в «хороших» кластерах на уровне i (WScore i ) Максимально возможная доля документов в «хороших» кластерах по всем разбиениям на кластеры, встречающихся в построенном дереве (WScore)

WScore i и WScore WScore 2 = 0WScore = 4/6

Постановка экспериментов Наборы данных: – List.Ru (11 классов) – IMDB (34 класса) Рассматривались подмножества размером от 1000 до 3000 документов

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

Наблюдаемые закономерности Расширение признаков вниз ухудшает результаты Информация об атрибутах бесполезна Входящие пути полезны (оптимальная длина зависит от набора) Сложные схемы взвешивания имеют смысл (большинство наилучших результатов получено с TFIDF)