Текст
<<  Классификация и кластеризация документов Классификация документов  >>
Кластеризация документов
Кластеризация документов
Disclaimer
Disclaimer
1. Введение
1. Введение
Основные типы кластеризации
Основные типы кластеризации
Восходящая/нисходящая кластеризация
Восходящая/нисходящая кластеризация
Исключающая, перекрывающая и нечеткая кластеризации (exclusive /
Исключающая, перекрывающая и нечеткая кластеризации (exclusive /
Полная и частичная кластеризации (complete/ partial)
Полная и частичная кластеризации (complete/ partial)
Определение расстояние между элементами
Определение расстояние между элементами
Методы объединения кластеров
Методы объединения кластеров
2. Оценка качества кластеризации
2. Оценка качества кластеризации
Матрица несоответствий
Матрица несоответствий
Метрики заимствованные из информационного поиска
Метрики заимствованные из информационного поиска
Применительно к кластеризации
Применительно к кластеризации
Чистота
Чистота
Энтропия
Энтропия
Взаимная информация
Взаимная информация
Стабильность
Стабильность
3. Векторная модель
3. Векторная модель
3.1 Предобработка
3.1 Предобработка
4. Иерархическая кластеризация
4. Иерархическая кластеризация
«Разделяющая» кластеризация
«Разделяющая» кластеризация
Недостатки kmeans
Недостатки kmeans
Лирическое отступление: O
Лирическое отступление: O
4.1 Online spherical kmeans (oskmns)
4.1 Online spherical kmeans (oskmns)
4.2 Kernel kmeans
4.2 Kernel kmeans
5. Генеративные алгоритмы
5. Генеративные алгоритмы
5.1 Гауссова модель
5.1 Гауссова модель
Гауссова модель
Гауссова модель
5.2 expectation maximization (em-алгоритм)
5.2 expectation maximization (em-алгоритм)
Em-алгоритм
Em-алгоритм
5.3 Модель фон Мисес-Фишера
5.3 Модель фон Мисес-Фишера
6. Спектральная кластеризация
6. Спектральная кластеризация
6.1 Алгоритм divide & merge
6.1 Алгоритм divide & merge
Алгоритм divide & merge
Алгоритм divide & merge
6.2 Нечеткая совместная корреляция
6.2 Нечеткая совместная корреляция
7. Снижение размерности
7. Снижение размерности
7.1 Метод главных компонентов (PCA)
7.1 Метод главных компонентов (PCA)
Метод главных компонентов
Метод главных компонентов
7.2 Неотрицательная факторизация (NMF)
7.2 Неотрицательная факторизация (NMF)
7.3 Мягкая спектральная кластеризация
7.3 Мягкая спектральная кластеризация
Мягкая спектральная кластеризация
Мягкая спектральная кластеризация
7.4 Lingo
7.4 Lingo
8. Модели с учетом порядка слов
8. Модели с учетом порядка слов
8.1 Кластеризация на основе суффиксных деревьев
8.1 Кластеризация на основе суффиксных деревьев
Кластеризация на основе суффиксных деревьев
Кластеризация на основе суффиксных деревьев
8.2 Граф документа
8.2 Граф документа
Анализ
Анализ
Спасибо за внимание
Спасибо за внимание

Презентация: «Кластеризация документов». Автор: Юля. Файл: «Кластеризация документов.ppt». Размер zip-архива: 736 КБ.

Кластеризация документов

содержание презентации «Кластеризация документов.ppt»
СлайдТекст
1 Кластеризация документов

Кластеризация документов

На основе статьи: Nicholas O. Andrews and Edward A. Fox, Recent Developments in Document Clustering, October 16, 2007 http://eprints.cs.vt.edu/archive/00001000/01/docclust.pdf дополнение из книги "Introduction to data mining, by Tan, Steinbach, and Kumar"

Лидия Пивоварова

2 Disclaimer

Disclaimer

Очень много математики. Я не со всем до конца разобралась Зато я развернула некоторые базовые понятия, которые в статье даются без пояснений Плохая новость: 42 слайда Хорошая новость: я не собираюсь подробно обсуждать все

3 1. Введение

1. Введение

Кластеризация документов (далее – просто кластеризация) – это процесс обнаружения естественных групп в коллекции документов. Текст обзорный, он упоминает основные классы алгоритмов и описывает по два-три самых распространенных алгоритма из каждого класса.

4 Основные типы кластеризации

Основные типы кластеризации

Восходящая/нисходящая кластеризации (hierarcical / partitional) Исключающая, перекрывающая и нечеткая кластеризации (exclusive / overlapping) Полная и частичная кластеризации (complete / partial clustering)

5 Восходящая/нисходящая кластеризация

Восходящая/нисходящая кластеризация

Иерархическая кластеризация (восходящая) - допускаем наличие подкластеров, осуществляется в несколько приемов, в результате образуется в иерархическое дерево (дендрограмму). Нисходящая (плоская) кластеризация - предполагает разделение на кластеры сразу, причем один объект относится только к одному кластеру.

6 Исключающая, перекрывающая и нечеткая кластеризации (exclusive /

Исключающая, перекрывающая и нечеткая кластеризации (exclusive /

overlapping/ fuzzing)

Исключающая – каждый объект может быть отнесен только к одному кластеру Перекрывающая - используется, если объект принадлежит к нескольким группам или находится между двумя кластерами. Нечеткая или вероятностные кластеризации являются частными случаями перекрывающей кластеризации. Тогда каждый объект относится к кластеру с определенным весом или вероятностью. Например, вес от 0 до1, где 0 – абсолютно не принадлежит, 1 – полностью принадлежит.

7 Полная и частичная кластеризации (complete/ partial)

Полная и частичная кластеризации (complete/ partial)

Метод полной кластеризации - каждый объект обязательно относится к кластеру Частичная кластеризация –некоторые объекты не принадлежат к четко определенным группам, поскольку могут являться выбросами, шумами и т.п.

8 Определение расстояние между элементами

Определение расстояние между элементами

Вычисление Евклидова расстояния (если известны координаты точек в пространстве) Квадрат Евклидова расстояния Манхэттенское расстояние (дает те же результаты, что и Евклидово расстояние, но влияние отдельных выбросов уменьшается): Расстояние Чебышева Используется, когда нужно определить два объекта как «различные», если они различаются по какой-либо одной координате

9 Методы объединения кластеров

Методы объединения кластеров

Метод ближнего соседа или одиночная связь. Расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами в различных кластерах. Метод наиболее удаленных соседей. Расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах Метод Варда. Расстояние как прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения Метод невзвешенного попарного среднего. В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Метод взвешенного попарного среднего. Метод похож на метод невзвешенного попарного среднего, но в качестве весового коэффициента используется размер кластера Невзвешенный центроидный метод. В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести. Взвешенный центроидный метод. Метод похож на предыдущий, но для учета разницы между размерами кластеров (числе объектов в них), используются веса.

10 2. Оценка качества кластеризации

2. Оценка качества кластеризации

Не существует единого (общепризнанного, применимого во всех случаях) метода оценки Оценка предполагает, что коллекция (или часть коллекции) размечена человеком Кластеры – результат кластеризации, классы – результат ручной разметки

11 Матрица несоответствий

Матрица несоответствий

- Способ примитивный, зато наглядный

Классы

К л а с т е р ы

A

B

C

a

2

2

0

b

2

2

0

c

0

0

8

12 Метрики заимствованные из информационного поиска

Метрики заимствованные из информационного поиска

Полнота (recall): R = tp / (tp+fn) Точность (presicion): P = tp / (tp+fn) F-мера: Аккуратность (accuracy): A = (tp + tn) / (tp + tn +fp +fn)

13 Применительно к кластеризации

Применительно к кластеризации

i – классы, j – кластеры, n – общее число документов, ni – число документов в классе i Т.е. для каждого класса выбираем кластер, который ему больше соответствует (argmax), суммируем меры соответствия (F) для всех классов, при этом чем больше класс, тем больше его вес в общей сумме (ni ). F-мера показывает общее качество кластеризации, но не показывает как устроены сами кластеры.

14 Чистота

Чистота

i – классы, j – кластеры, n – общее число документов, nj – число документов в кластере j, P(i,j) – доля документов из класса i в кластере j . Т.е. берем долю доминирующего (argmax) класса в кластере (P(i,j)), и суммируем по всем кластерам, при этом чем больше кластер, тем больше его вес в сумме (nj ). Чем выше значение чистоты, тем лучше. В идеальном случае P=1.

15 Энтропия

Энтропия

i – классы, j – кластеры, n – общее число документов, nj – число документов в кластере j, P(i,j) – доля документов из класса i в кластере j , k – число кластеров. Энтропия – степень «размазанности» класса по кластерам. Чем меньше, тем лучше, в идеале E=0.

16 Взаимная информация

Взаимная информация

Чистота и энтропия хороши тогда, когда число классов и кластеров совпадает. В других случаях лучше MI (или NMI – нормализованная взаимная информация).

N – общее число документов, nh – число документов в классе h, nl – число документов в кластере l, nh,l – число документов в пересечении.

Класс nh

nh,l Кластер nl

n

17 Стабильность

Стабильность

С помощью взаимной информации можно считать стабильность, т.е. степень пересечения кластеризации при разных прогонах одного и того же алгоритма.

? – множество различных кластеризаций, ? – конкретная кластеризация, r – число кластеров.

18 3. Векторная модель

3. Векторная модель

Коллекция из n документов и m различных терминов представляется в виде матрицы mxn, где каждый документ – вектор в m-мерном пространстве. Веса терминов можно считать по разному: частота, бинарная частота (входит – не входит), tf*idf… Порядок слов не учитывается (bag of words) Матрица очень большая (большое число различных терминов в гетерогенной коллекции). В матрице много нулей

19 3.1 Предобработка

3.1 Предобработка

Фильтрация (удаление спецсимволов и пунктуации) Токенизация (разбиваем текст на термины – слова или словосочетания) Стемминг (приведение слова к основе) Удаление стоп-слов Сокращение (удаление низкочастотных слов)

20 4. Иерархическая кластеризация

4. Иерархическая кластеризация

На начальной стадии каждый документ – сам себе кластер. На каждом шаге документы объединяются до построения полного дерева. Число кластеров заранее не оговаривается. Не подходит для больших объемов данных (подсчет расстояния на каждой стадии).

21 «Разделяющая» кластеризация

«Разделяющая» кластеризация

Классический пример - kmeans: Выбирается k случайных документов, которые считаются центроидами кластеров, все остальные документы распределяются по кластерам по степени близости к центроидам На следующих итерациях центроиды пересчитываются и документы перераспределяются Косинусная метрика лучше, чем Евклидово расстояние

22 Недостатки kmeans

Недостатки kmeans

Результаты могут быть различными в зависимости от инициализации. Может останавливаться на субоптимальном локальном минимуме Чувствителен к шуму и случайным выбросам Вычислительная сложность: где n – число документов, k – число кластеров, l – число итераций.

23 Лирическое отступление: O

Лирическое отступление: O

Вычислительная сложность алгоритма O(f(n)), где n – это объем данных – означает, что в худшем случае для выполнения алгоритма понадобится c1+c2*f(n) операций, где c1и c2 константы. Примеры: O(n) – линейный алгоритм O(na) – полиномиальный алгоритм O(an) – экспоненциальный алгоритм (очень плохо) O(n*log(n)) – часто встречается; медленнее линейного, но быстрее полиномиального

24 4.1 Online spherical kmeans (oskmns)

4.1 Online spherical kmeans (oskmns)

Документы не обрабатываются все сразу, а добавляются Новый документ добавляется в тот кластер, к которому он ближе Центроид не пересчитывается как среднее всех элементов, а «поправляется»:

K(x) – кластер, к которому ближе всего документ, ? – центроид, d – вектор документа,? – убывающий коэффициент итерации:

N – число документов, M – число итераций, ?f – желаемое конечное значение (0,01)

25 4.2 Kernel kmeans

4.2 Kernel kmeans

На множестве документов вводится функция, которая отражает степень близости между документами. После этого проводится кластеризация обычным методом kmeans Выбор функции очень важен; считается, что для текстовых данных лучше всего косинусная мера близости Для конкретных коллекция какая-то другая функция может работать лучше Вообще в этом методе пока довольно много сложностей и неопределенности; вычислительно метод очень тяжел Существует разновидность, которая порождает нечеткую кластеризацию (fuzzy c-means)

Kmeans бессилен в тех случаях, кластеры разделяются нелинейно. Kernel kmeans позволяет перейти в пространство более высокой размерности, где кластеры будут разделяться линейно.

26 5. Генеративные алгоритмы

5. Генеративные алгоритмы

Дискриминативные алгоритмы, которые основаны на попарной близости документов, имеют сложность O(n2) по определению. Генеративные алгоритмы не требуют такого сравнения, используя итеративные процедуры.

27 5.1 Гауссова модель

5.1 Гауссова модель

Ковариация: Если между x и у нет корреляции, то ковариация равна нулю. Матрица ковариации: матрица, элементы которой – это попарные ковариации двух векторов. Если речь идет об одном и том же наборе векторов (наш случай: одни и те же документы в столбцах и строках), то матрица ковариации – это обобщение дисперсии для многомерной случайной величины.

Предполагается, что распределение документов в векторном пространстве – это набор Гауссовых распределений; каждый кластер ассоциирован со средним распределения и матрицей ковариации.

28 Гауссова модель

Гауссова модель

Вероятность того, что документ d принадлежит кластеру ? из набора ?:

P(d| ?) - вероятность того, что документ d принадлежит кластеру ?, m – размерность пространства, ? – сентроид, ? – матрица ковариации. Общая вероятность (правдоподобие того, что данный документ описывается моделью): Задача кластеризации: максимизировать это число, максимизировав каждое из слагаемых (т.е. найдя наилучшее среднее и матрицу ковариации для каждого кластера).

29 5.2 expectation maximization (em-алгоритм)

5.2 expectation maximization (em-алгоритм)

Итеративная процедура для нахождения максимального правдоподобия параметров модели. Две стадии: E(xpectation) – вывод скрытых данных из наблюдаемых данных (документы) и текущей модели (кластеры)

M(aximization) – максимизация правдоподобия в предположении, что скрытые данные известны

30 Em-алгоритм

Em-алгоритм

Большое число свободных параметров может приводить к переобучению. Сокращение размерности: выбор дискриминирующих свойств для каждого кластера. Сложность: O(k2n) Нестабильность, зависимость от инициализации.

31 5.3 Модель фон Мисес-Фишера

5.3 Модель фон Мисес-Фишера

На самом деле, распределение текстов по кластерам гауссианами описывается плохо. Было доказано, что лучше всего подходит vMF-распределение:

Z – функция Басселя (фактор нормализации). Затем используют алгоритм, похожий на em. Качество получается лучше, чем spherical k-means.

32 6. Спектральная кластеризация

6. Спектральная кластеризация

Основная гипотеза: термины, которые часто встречаются вместе, описывают близкие понятия. Поэтому важна группировка не только кластеров, но и терминов. Т.е. речь идет о совместной кластеризации терминов и документов. Матрица термин-документ преобразуется в двудольный граф:

Тогда задача кластеризации – разбить этот граф на сильно связанные компоненты. Почему спектральная: используется сразу несколько функций-критериев разбиения.

33 6.1 Алгоритм divide & merge

6.1 Алгоритм divide & merge

Нахождение оптимального разбиения в графе – NP-полная задача (на практике означает, что алгоритм экспоненциальный). Однако существует аппроксимация. Две стадии: Иерархическая кластеризация (существует метод с использованием собственных векторов матрицы, который позволяет избежать неэффективного попарного сравнения) Кластеризация результатов предыдущей стадии с использованием стандартных алгоритмов – kmeans, либо другие алгоритмы, с неизвестным заранее числом кластеров

34 Алгоритм divide & merge

Алгоритм divide & merge

35 6.2 Нечеткая совместная корреляция

6.2 Нечеткая совместная корреляция

Кластеризуются сразу и термины, и документы Границы между кластерами нечеткие - термин или документ может входить сразу в несколько кластеров (с различными весами) Пример: Fuzzy Codok алгоритм

uci – степень вхождения документа i в кластер с, vcj – степень вхождения термина j в кластер с, dij – уровень корреляции между документом и термином; m – число терминов, n – число документов, С – число кластеров документов, K – число кластеров терминов. Tu, Tv – параметры, их надо подбирать – слабое место алгоритма; оптимальные значения параметров зависят от коллекции.

36 7. Снижение размерности

7. Снижение размерности

Матрица термин документ А аппроксимируется матрицей меньшего ранга k Ak. Принятая мера качества такой аппроксимации – норма Фробениуса (чем меньше, тем лучше):

37 7.1 Метод главных компонентов (PCA)

7.1 Метод главных компонентов (PCA)

Главные компоненты – ортогональные (независимые) проекции, которые вместе описывают максимальное разнообразие в данных Задача эквивалентна поиску оптимального разбиения в двудольном графе

Главные компоненты получаются из сингулярного разложения матрицы: A = U?VT, U,V – квадратные, ? – диагональная ?k – диагональная матрица меньшего ранга, в нее входят k наибольших чисел из ? Искомая проекция: A = U?kVT Чем больше k, тем лучше аппроксимация

38 Метод главных компонентов

Метод главных компонентов

+ В результате получается оптимальная аппроксимация + Различие в расстояниях внутри кластеров и между кластерами становится более резким В новом пространстве остаются недискриминирующие свойства – т.е. результаты метода нельзя рассматривать как готовую кластеризацию Компоненты должны быть ортогональными – не совсем подходит для текстов, которые могут покрывать несколько тем Вычислительно сложный алгоритм, не может использоваться итеративно

39 7.2 Неотрицательная факторизация (NMF)

7.2 Неотрицательная факторизация (NMF)

Цель: получить аппроксимацию, которая содержит только дискриминирующие факторы Исходная матрица аппроксимируется произведением: A ? UVT U – базис mxk, V – матрица коэффициентов nxk U может интерпретироваться как набор семантических переменных, V - распределение документов по этим темам Начальные значения U и V инициализируются случайно, затем итеративно улучшаются (em-алгоритм) Мера качества – обычно Евклидово расстояние (чем меньше, тем лучше): Вместо случайно инициализации можно использовать результаты более простого метода кластеризации (skmns) Быстрее, чем метод главных компонентов

40 7.3 Мягкая спектральная кластеризация

7.3 Мягкая спектральная кластеризация

Из редуцированного пространства трудно породить нечеткую кластеризацию, потому что усечение матрицы приводит к искажениям Выход: независимая кластеризация терминов и документов; на основе кластеризации терминов порождается нечеткая кластеризация документов и vice versa

41 Мягкая спектральная кластеризация

Мягкая спектральная кластеризация

Пространство редуцируется методом главных компонентов Проводится кластеризация методом kmeans (или другим) Для этих кластеров порождается матрица P1 описывает распределение терминов по кластерам, P2 – документов Веса терминов высчитываются с помощью трансформации A P2 – проекция ценроидов в исходное пространство Аналогичная матрица S порождается из кластеризации исходного пространства ATS1 используется как функция вхождения для документов, AP2 – для терминов (используются только дискриминирующие термины) Хорошее качество для пересекающихся тем, но высокая вычислительная сложность

42 7.4 Lingo

7.4 Lingo

“description comes first” Сокращается размерность пространства Базисные вектора полученной редуцированной матрицы воспринимаются как метки кластеров Эти метки используются для «поиска» документов (как в информационном поиске)

43 8. Модели с учетом порядка слов

8. Модели с учетом порядка слов

Маша любит Васю, Вася любит Машу – векторная модель не учитывает различие, но оно есть Гипотеза: учет порядка слов может улучшить качество кластеризации Кроме того, он позволит создавать более разумные описания кластеров (не набор слов, а короткие фразы)

44 8.1 Кластеризация на основе суффиксных деревьев

8.1 Кластеризация на основе суффиксных деревьев

Суффикс – несколько слов с конца предложения (вплоть до предложения целиком) Суффиксное дерево: описывает все общие суффиксы документов

Общие суффиксы используются для выделения базовых кластеров, которые затем объединяются методом связанных компонентов Общая сложность алгоритма: O(n log(n))

dog chased cat, dog chased mailman

45 Кластеризация на основе суффиксных деревьев

Кластеризация на основе суффиксных деревьев

Кластеры включают не все документы (документ может иметь суффикс, которые не пересекается ни с одним другим) Не учитывается распределение слов по коллекции (не все слова одинаково полезны) Учитываются только совпадающие суффиксы, не совпадающие суффиксы не учитываются Проверялось на сниппетах, на длинных текстах и больших коллекциях работает плохо Можно совмещать учет порядка слов с обычной косинусной мерой

46 8.2 Граф документа

8.2 Граф документа

Doc1: “cat chased rat”, “dog chased rat” Doc2: “angry dog chased fat mailman” “mailman ran” Doc3: “little dog chased ran”

Слова хранятся в вершинах, с учетом частоты Нет избыточной информации (как в суффиксных деревьях) Это не алгоритм кластеризации, а модель документа; мера близости основана на перекрывающихся подграфах Лучше работает совместно с косинусной метрикой, но это – двойная стоимость вычислений

47 Анализ

Анализ

Качество кластеризации определяется по стандартным мерам, при этом итоговая кластеризация не всегда выглядит «естественно» Проблема инициализации (итеративные алгоритмы используют случайную инициализацию) Проблема описания кластеров (меток) Проблема числа кластеров Существуют другие методы кластеризации, возможно, они окажутся хороши для текстовых данных Возможно другие меры близости, помимо косинусной, окажутся применимы

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

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

«Кластеризация документов»
http://900igr.net/prezentacija/informatika/klasterizatsija-dokumentov-88310.html
cсылка на страницу

Текст

15 презентаций о тексте
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Текст > Кластеризация документов