Кластеризация документов Лидия Михайловна Пивоварова Системы понимания текста

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

Матрица несоответствий КЛАССЫ КЛАСТЕРЫABC a220 b220 c008 - способ примитивный, зато наглядный

Метрики заимствованные из информационного поиска Полнота (recall): R = tp / (tp+fn) Точность (presicion): P = tp / (tp+fn) F-мера: Аккуратность (accuracy): A = (tp + tn) / (tp + tn +fp +fn) Релевант ные Нерелева нтные Найденн ые tpfp Ненайден ные fntn

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

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

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

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

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

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

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

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

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

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

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

Алгоритм divide & merge

Нечеткая совместная корреляция Кластеризуются сразу и термины, и документы Кластеризуются сразу и термины, и документы Границы между кластерами нечеткие - термин или документ может входить сразу в несколько кластеров (с различными весами) Границы между кластерами нечеткие - термин или документ может входить сразу в несколько кластеров (с различными весами) Пример: Fuzzy Codok алгоритм Пример: Fuzzy Codok алгоритм u ci – степень вхождения документа i в кластер с, v cj – степень вхождения термина j в кластер с, d ij – уровень корреляции между документом и термином; m – число терминов, n – число документов, С – число кластеров документов, K – число кластеров терминов. T u, T v – параметры, их надо подбирать – слабое место алгоритма; оптимальные значения параметров зависят от коллекции.

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

Метод главных компонентов (PCA) Главные компоненты – ортогональные (независимые) проекции, которые вместе описывают максимальное разнообразие в данных Главные компоненты – ортогональные (независимые) проекции, которые вместе описывают максимальное разнообразие в данных Задача эквивалентна поиску оптимального разбиения в двудольном графе Задача эквивалентна поиску оптимального разбиения в двудольном графе Главные компоненты получаются из сингулярного разложения матрицы: Главные компоненты получаются из сингулярного разложения матрицы: A = UΣV T, Σ – диагональная Σ k – диагональная матрица меньшего ранга, в нее входят k наибольших чисел из Σ Σ k – диагональная матрица меньшего ранга, в нее входят k наибольших чисел из Σ Искомая проекция: Искомая проекция: A = UΣ k V T A = UΣ k V T Чем больше k, тем лучше аппроксимация Чем больше k, тем лучше аппроксимация

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

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

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

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

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

Содержание 1. Оценка качества кластеризации 2. Применение векторной модели в кластеризации 3. Иерархическая кластеризация 4. «Разделяющая» кластеризация 5. Генеративные алгоритмы 6. Спектральная кластеризация 7. Снижение размерности 8. Модели с учетом порядка слов

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

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

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

Граф документа Doc1: cat chased rat, dog chased rat Doc1: cat chased rat, dog chased rat Doc2: angry dog chased fat mailman mailman ran Doc2: angry dog chased fat mailman mailman ran Doc3: little dog chased ran Doc3: little dog chased ran Слова хранятся в вершинах, с учетом частоты Слова хранятся в вершинах, с учетом частоты Нет избыточной информации (как в суффиксных деревьях) Нет избыточной информации (как в суффиксных деревьях) Это не алгоритм кластеризации, а модель документа; мера близости основана на перекрывающихся подграфах Это не алгоритм кластеризации, а модель документа; мера близости основана на перекрывающихся подграфах Лучше работает совместно с косинусной метрикой, но это – двойная стоимость вычислений Лучше работает совместно с косинусной метрикой, но это – двойная стоимость вычислений

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

Источники Nicholas O. Andrews and Edward A. Fox, Recent Developments in Document Clustering, October 16, docclust.pdf Nicholas O. Andrews and Edward A. Fox, Recent Developments in Document Clustering, October 16, docclust.pdf docclust.pdf docclust.pdf