Маркировка кластеров

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

Дифференциальная маркировка кластеров

Дифференциальная маркировка кластеров помечает кластер путем сравнения распределений терминов по кластерам с использованием методов, также используемых для выбора признаков при классификации документов , таких как взаимная информация и выбор признаков по хи-квадрату . Термины с очень низкой частотой не лучшим образом отражают весь кластер и могут быть опущены при обозначении кластера. Опуская эти редкие термины и используя дифференциальный тест, можно добиться наилучших результатов при дифференциальной маркировке кластеров. ^[1]

Точечная взаимная информация

В области теории вероятностей и теории информации взаимная информация измеряет степень зависимости двух случайных величин . Взаимная информация двух переменных X и Y определяется как:

${\displaystyle I(X,Y)=\sum _{x\in X}{\sum _{y\in Y}{p(x,y)log_{2}\left({\frac {p(x,y)}{p_{1}(x)p_{2}(y)}}\right)}}}$

где p(x, y) — совместное распределение вероятностей двух переменных, p ₁ (x) — распределение вероятностей X, а p ₂ (y) — распределение вероятностей Y.

В случае разметки кластера переменная X связана с принадлежностью к кластеру, а переменная Y — с наличием термина. ^[2] Обе переменные могут иметь значения 0 или 1, поэтому уравнение можно переписать следующим образом:

${\displaystyle I(C,T)=\sum _{c\in {0,1}}{\sum _{t\in {0,1}}{p(C=c,T=t)log_{2}\left({\frac {p(C=c,T=t)}{p(C=c)p(T=t)}}\right)}}}$

В этом случае p(C = 1) представляет вероятность того, что случайно выбранный документ является членом определенного кластера, а p(C = 0) представляет вероятность того, что это не так. Аналогично, p(T = 1) представляет вероятность того, что случайно выбранный документ содержит данный термин, а p(T = 0) представляет вероятность того, что это не так. Совместная функция распределения вероятностей p(C, T) представляет вероятность того, что два события произойдут одновременно. Например, p(0, 0) — это вероятность того, что документ не является членом кластера c и не содержит термин t ; p(0, 1) — вероятность того, что документ не является членом кластера C и содержит термин T ; и так далее.

Выбор по хи-квадрату

Критерий хи-квадрат Пирсона можно использовать для расчета вероятности того, что возникновение события соответствует первоначальным ожиданиям. В частности, его можно использовать для определения того, являются ли два события A и B статистически независимыми . Значение статистики хи-квадрат:

${\displaystyle X^{2}=\sum _{a\in A}{\sum _{b\in B}{\frac {(O_{a,b}-E_{a,b})^{2}}{E_{a,b}}}}}$

где O _a,b — наблюдаемая частота одновременного появления a и b, а E _a,b — ожидаемая частота совместного появления.

В случае разметки кластера переменная A связана с членством в кластере, а переменная B связана с наличием термина. Обе переменные могут иметь значения 0 или 1, поэтому уравнение можно переписать следующим образом:

${\displaystyle X^{2}=\sum _{a\in {0,1}}{\sum _{b\in {0,1}}{\frac {(O_{a,b}-E_{a,b})^{2}}{E_{a,b}}}}}$

Например, O _1,0 — это наблюдаемое количество документов, находящихся в определенном кластере, но не содержащих определенного термина, а E _1,0 — ожидаемое количество документов, которые находятся в определенном кластере, но не содержат определенный термин. Наше первоначальное предположение состоит в том, что эти два события независимы, поэтому ожидаемые вероятности совместного возникновения могут быть рассчитаны путем умножения отдельных вероятностей: ^[3]

Е _1,0 = Н * Р(С = 1) * Р(Т = 0)

где N — общее количество документов в коллекции.

Внутрикластерная маркировка

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

Метки центроида

Часто используемой моделью в области поиска информации является модель векторного пространства, которая представляет документы в виде векторов. Элементы вектора соответствуют терминам словаря . Бинарные векторы имеют значение 1, если термин присутствует в конкретном документе, и 0, если он отсутствует. Многие векторы используют веса, которые отражают важность термина в документе и/или важность термина в коллекции документов. Для определенного кластера документов мы можем вычислить центроид, найдя среднее арифметическое всех векторов документов. Если запись в векторе центроида имеет высокое значение, то соответствующий термин часто встречается в кластере. Эти термины можно использовать в качестве обозначения кластера. Одним из недостатков использования маркировки центроидов является то, что они могут выбирать такие слова, как «место» и «слово», которые часто встречаются в письменном тексте, но имеют мало отношения к содержимому конкретного кластера.

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

Простой и экономичный способ преодолеть вышеуказанное ограничение — встроить термины центроида с наибольшим весом в структуру графа, которая обеспечивает контекст для их интерпретации и выбора. ^[4] В этом подходе для каждого кластера сначала строится матрица совпадения терминов, называемая «термин-термин» . Каждая ячейка представляет количество раз, когда термин встречается вместе с термином в определенном окне текста (предложение, абзац и т. д.). На втором этапе матрица сходства получается путем умножения на ее транспонирование. У нас есть . Будучи скалярным произведением двух нормализованных векторов и , обозначает косинусное сходство между терминами и . Полученную таким образом информацию можно затем использовать в качестве взвешенной матрицы смежности графа сходства терминов. Термины центроида являются частью этого графика, и поэтому их можно интерпретировать и оценивать, проверяя термины, которые окружают их на графике. ${\displaystyle T_{k}}$ ${\displaystyle S_{k}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle T_{k}^{sim}}$ ${\displaystyle T_{k}}$ ${\displaystyle T_{k}^{sim}=T_{k}'T_{k}=(t_{{sim}_{ij}})}$ ${\displaystyle {\tilde {t}}_{i}}$ ${\displaystyle {\tilde {t}}_{j}}$ ${\displaystyle t_{{sim}_{ij}}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle T_{k}^{sim}}$

Этикетки с названиями

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

Ярлыки внешних знаний

Маркировка кластеров может быть выполнена косвенно с использованием внешних знаний, таких как предварительно классифицированные знания, такие как знания из Википедии. ^[5] В таких методах набор важных текстовых особенностей кластера сначала извлекается из документов кластера. Эти функции затем можно использовать для извлечения (взвешенных) K-ближайших классифицированных документов, из которых можно извлечь кандидатов на метки кластера. Последний этап включает ранжирование таких кандидатов. Подходящие методы основаны на голосовании или процессе объединения, который определяется с использованием набора классифицированных документов и исходных признаков кластера.

Объединение нескольких кластерных этикетировщиков

Метки кластеров нескольких различных устройств для маркировки кластеров можно дополнительно объединить для получения более качественных меток. Например, линейную регрессию можно использовать для изучения оптимальной комбинации оценок маркировщика. ^[6] Более сложный метод основан на подходе слияния и анализе устойчивости решений по кластерным меткам различных меток. ^[7]

Внешние ссылки

• Иерархическая кластеризация
• Автоматическая маркировка иерархических кластеров

Рекомендации

1. Мэннинг, Кристофер Д., Прабхакар Рагхаван и Хинрих Шютце. Введение в поиск информации . Кембридж: Кембриджский университет, 2008. Маркировка кластеров . Стэнфордская группа обработки естественного языка. Веб. 25 ноября 2009 г. <http://nlp.stanford.edu/IR-book/html/htmledition/cluster-labeling-1.html>.
2. Мэннинг, Кристофер Д., Прабхакар Рагхаван и Хинрих Шютце. Введение в поиск информации . Кембридж: Кембриджский университет, 2008. Взаимная информация . Стэнфордская группа обработки естественного языка. Веб. 25 ноября 2009 г. <http://nlp.stanford.edu/IR-book/html/htmledition/mutual-information-1.html>.
3. Мэннинг, Кристофер Д., Прабхакар Рагхаван и Хинрих Шютце. Введение в поиск информации . Кембридж: Кембриджский университет, 2008. Выбор функций Chi2 . Стэнфордская группа обработки естественного языка. Веб. 25 ноября 2009 г. <http://nlp.stanford.edu/IR-book/html/htmledition/feature-selectionchi2-feature-selection-1.html>.
4. Франсуа Роль, Моахмед Надиф. Помимо маркировки кластеров: семантическая интерпретация содержимого кластеров с использованием графового представления. Системы, основанные на знаниях, том 56, январь 2014 г.: 141–155.
5. Дэвид Кармель, Хаггай Ройтман, Наама Цвердлинг. Улучшение маркировки кластеров с помощью Википедии. СИГИР 2009: 139-146.
6. Дэвид Кармель, Хаггай Ройтман, Наама Цвердлинг. Улучшение маркировки кластеров с помощью Википедии. СИГИР 2009: 139-146.
7. Хаггай Ройтман, Шей Хаммел, Михал Шмуэли-Шойер. Объединенный подход к маркировке кластеров. СИГИР 2014: 883-886.