Применение алгоритма BIRCH к кластеризации текстов Карпов И.А., Горославский А.И. ИПС РАН, Переславль-Залесский 17.10.2012. - презентация

1 Применение алгоритма BIRCH к кластеризации текстов Карпов И.А., Горославский А.И. ИПС РАН, Переславль-Залесский

2 План доклада Постановка задачи кластеризации Описание текстового анализа Сегментация Морфологическая обработка Разрешение лексической многозначности Описание сокращения размерности Сегментация ЛСА Создание микровыборки документов Описание кластеризации Результаты работы 2

3 Постановка задачи кластеризации 3 Кластеризация определение наличия и состава тематически однородных групп в текстовой коллекции в случае, когда априорное описание групп отсутствует.

4 Текстовый анализ 4 Цель: Построить векторную модель документа для дальнейшего анализа. Особенности реализации Поиск собственных имен TF/IDF метрика взвешивания слов Использование Хеш-таблиц Основные характеристики П роизводительность слов/сек Поиск собственных имен, географических объектов и организаций Снятие многозначности

5 Сегментация 5 Поиск имен собственных

6 Лемматизация 6 ДАННЫЙ прилагательное, мн.ч., именительный падеж ДАННЫЙ прилагательное, мн.ч., винительный падеж ДАННЫЙ местоимение, мн.ч., винительный падеж ДАННЫЙ местоимение, мн.ч., именительный падеж ДАННЫЕ существительное, нарицательное, мн.ч., винительный падеж ДАННЫЕ существительное, нарицательное, мн.ч., именительный падеж Многозначность после морфологического анализа

7 Лемматизация 7 Многозначность после морфологического анализа ДАННЫЙ прилагательное, мн.ч., именительный падеж ДАННЫЙ прилагательное, мн.ч., винительный падеж ДАННЫЙ местоимение, мн.ч., винительный падеж ДАННЫЙ местоимение, мн.ч., именительный падеж ДАННЫЕ существительное, нарицательное, мн.ч., винительный падеж ДАННЫЕ существительное, нарицательное, мн.ч., именительный падеж

8 Построение векторной модели 8 ДАННЫЕсущ, ОТПРАВИТЬприч Впредл НИЯУ МИФИсущ ЯВЛЯТЬСЯгл ОШИБОЧНЫЙприл СЛЕДОВАТЕЛЬНОвводн ДАННЫЙприл РАБОТАсущ НУЖНОнареч ПОВТРОИТЬинф ДАННЫЕсущ НИЯУ МИФИсущ РАБОТАсущ НИЯУ МИФИ1,25 РАБОТА0,93 ДАННЫЕ0,87 Векторная модельОграничение по части речиВеса слов

9 Сокращение размерности 9 Цель: Сократить размер индекса для ускорения дальнейшей работы Основные подходы: Порог ключевых слов Латентно-семантический анализ Создание репрезентативной подвыборки основной коллекции НИЯУ МИФИ1,25 РАБОТА0,93 ДАННЫЕ0,87 НИИ "КВАНТ"0,86 ОТЧЕТ0,74 РАСПРЕДЕЛЕНИЕ0,31 СИСТЕМА0,14 РАЗРАБОТКА0,12 РЕАЛИЗАЦИЯ0,1 МАШИНА0,09 НИЯУ МИФИ1,25 РАБОТА0,93 ДАННЫЕ0,87 НИИ "КВАНТ"0,86 ОТЧЕТ0,74 РАСПРЕДЕЛЕНИЕ0,31 СИСТЕМА0,14 РАЗРАБОТКА0,12 РЕАЛИЗАЦИЯ0,1 МАШИНА0,09 НИЯУ МИФИ1,25 РАБОТА0,93 ДАННЫЕ0,87 НИИ "КВАНТ"0,86 ОТЧЕТ0,74 СИСТЕМА/РАЗРАБОТКА0,44 РАСПРЕДЕЛЕНИЕ0,31 РЕАЛИЗАЦИЯ0,1 МАШИНА0,09

10 Кластеризация: алгоритм BIRCH 10 За счет добавления кластеризуемых точек в CF-дерево формируется множество первичных кластеров (несколько тысяч), радиус которых не больше некоторого порога T. Первичные кластеры сами подвергаются агломеративной кластеризации. CF-дерево: С1С1 С11С11 С12С12 С13С13 С 111 :R(C 111 )

11 Кластеризация 11 Достоинства алгоритма BIRCHНедостатки алгоритма BIRCH 1.Очень высокая скорость и хорошая масштабируемость (зависимость времени работы от числа точек линейна). 1.Сложно оценить параметр T, обеспечивающий получение требуемого количества первичных кластеров. 2.Ошибки в ходе кластеризации, обусловленные тем, что для добавляемой в дерево точки очень часто находится не самый близкий к ней листовой узел. Кластеризация: алгоритм BIRCH

12 Кластеризация 12 1.Предложено проводить разбиение узла за счет агломеративной кластеризации его потомков. При этом число узлов, получаемых после разбиения, не обязательно равно двум и определяется самим агломеративным алгоритмом. 2.Предложено при поиске близкой к точке листовой вершины спускаться на каждом уровне дерева не только в единственный ближайший к точке узел, а в несколько (SearchingNodeCount) ближайших к ней узлов. 3.Разработан алгоритм поиска порога T, обеспечивающий получение требуемого количества листовых узлов. Сначала дерево строится для T=0. Если максимальное число листовых узлов превышается, то порог увеличивается и дерево перестраивается. Для оценки нового порога (Tnext) выделяется заданное количество случайных предлистовых узлов. Для i-го предлистового узла вычисляются радиусы кластеров, соответствующих всем возможным объединениям пар его дочерних узлов. Далее, порог Tnext_i определяется так, чтобы он был больше заданного процента этих радиусов. В качестве Tnext выбирается среднее всех Tnext_i. Кластеризация: алгоритм BIRCH

13 Кластеризация 13 Характеристики времени работы: сравнение с другими алгоритмами

14 Кластеризация 14 Характеристики качества алгоритма N docsk-means (rand)k-means (10%)BIRCH* ,26043,40081, ,84539,50051, ,669846,28552, , ,10355, , ,0098, , , ,59 Время работы алгоритмов на коллекциях разного объема Качество работы алгоритмов по Ф-мере Measure k-means (rand) 30 iterations k-means (10%) 3 iterations BIRCH* avg(F) wiki_Sci0,9480,9330,923 avg(F) wiki_Geo0,5670,5720,563 avg(F) wiki_Geo0,7120,7190,713

15 Основные результаты работы 15 Спроектирована и реализована система тематической кластеризации и классификации документов Разработан новый комбинированный метод сокращения размерности Усовершенствованы алгоритм кластеризации BIRCH: повышено качество кластеризации и предложены способы оценки входных параметров алгоритмов

16 16 Спасибо за внимание!