Текстовая кластеризация алгоритмом ROCK студент 4 курса МИЭМ, каф. ИКТ Иван Савин 1

Задачи при работе с базой статей Поиск дублирующих документов Группировка документов похожей тематики Составление списков рекомендаций 2

Анализ данных в решении задач Человеку трудно ориентироваться в базах статей, построенных по принципу wiki. Интеллектуальный анализ данных может предоставить средства относительно быстрого решения задач для базы любого масштаба 3

Подзадачи анализа данных Приведение текста к виду удобному для извлечения полезных данных - нормализация Группировка документов по схожим признакам - кластеризация 4

Нормализация 1.Разбиение документа на слова 2.В заголовках – ключевые слова 3.Стемминг однокоренных слов 4.Удаление стоп-слов Можно извлечь частоту слов в документе и примерно узнать о чем он 5

Задачи стеммера Извлечение значимой части слова – терма Баланс скорости и точности Последовательное удаление окончаний и суффиксов Определение части речи для уменьшения списка возможных суффиксов Алгоритм Портера 6

Итог нормализации 7 Векторная модель документа Term IDDoc IDRating 4214 ………… 2312 Статья - объект данных Рейтинг термов - атрибуты

Подзадачи кластеризации Выбор метрики сравнения двух объектов Выбор алгоритма кластеризации 8

Метрика близости Традиционные метрики (например, Эвклидово расстояние) предназначены для небольшого количества числовых атрибутов Коэффициент Жаккарда подходит для любого количества числовых и номинальных атрибутов, быстро вычисляется и более достоверен 9

Соседства недостаточно Большинство алгоритмов кластеризации работают с четко разделяемыми данными Текстовые документы обычно нельзя достаточно четко разделить 10

Решение - ROCK Robust Clustering using links (четкое разделение с использованием ссылок) 11 Введение новой метрики на основе метрики соседства – количество общих соседей (ссылок) А С В Есть общий сосед Сосед Может не быть соседом

Характеристика ROCK Агломеративный иерархический алгоритм Четкость разделения за счет учета ссылок 12

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

Итоговая метрика ROCK Идея формулы: Используемый вариант: 14 θ – коэффициент соседства n – размер статей кластера

Реализация 15 Управление (wiki extension, PHP) Нормализация (Python) Нормализация (Python) База wiki (mysql) База wiki (mysql) Вывод кластеров (wiki extension, PHP) Вывод кластеров (wiki extension, PHP) Кластеризация (Python) Кластеризация (Python)

План развития Доработка и оптимизация стеммера Оптимизация алгоритма кластеризации (аппроксимация таблиц) Учет сложных конструкций разметка (код, формулы) Автоматический выбор наиболее подходящих меток кластера Глобальная цель: кластеризация Википедии за приемлемое время 16

Вопросы Спасибо за внимание 17