ݺߣ

ݺߣShare a Scribd company logo

Мадорский. Извлечение тематически сгруппированных ключевых терминов из текстовых документов

•Download as PPTX, PDF•
•
С
Спецсеминар "Искусственный Интеллект" кафедры АЯ ВМК МГУ

осень 2014

1 of 42
Download to read offline
Извлечение тематически сгруппированных ключевых терминов из текстовых документов Автор: Мадорский Константин Научный руководитель: м.н.с. Баева Н.В.
Ключевые термины • Ключевые термины — термины в документе, которые могут дать высокоуровневое описание содержания документа для читателя • Извлечение ключевых терминов является базисным этапом для многих задач обработки естественного языка, например: – классификация документов – кластеризация документов – составление аннотации текста – вывод общей темы документа
О методе • использует Википедию в качестве информационного ресурса для вычисления семантической близости терминов • использует два базовых алгоритма: – алгоритм вычисления меры семантической близости, посчитанной по Википедии – алгоритм анализа сетей Гирвана-Ньюмана для выделения плотных подграфов
Википедия • www.wikipedia.org • свободно распространяемая энциклопедия, на сегодняшний день являющаяся самой большой энциклопедией в мире • в русскоязычном разделе на 23 ноября 2014 года количество статей — 1 165 325 • в англоязычном разделе на 25 апреля 2014 года количество статей — 4 500 000
Википедия: категории https://ru.wikipedia.org/wiki/Категория:География
Википедия: визуализация категорий tools.wmflabs.org/vcat/catgraphRedirect?wiki=wiki pedia&lang=ru&cat=География&d=0&n=0&format= png&links=graph&sub=1&depth=2
Википедия: визуализация категорий (1) tools.wmflabs.org/vcat/catgraphRedirect?wiki=wiki pedia&lang=ru&cat=География&d=0&n=0&format= png&links=graph&sub=0&depth=2
Википедия: страницы для многозначных терминов
Википедия: перенаправляющие страницы
Википедия: инфобокс
Википедия: See also .ɾ쾱徱.ǰ/ɾ쾱/Искусственныйинтеллект
Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
Шаг 1: Извлечение терминов- кандидатов • Разбор исходного документа на все возможные N-граммы (N ограничено максимальным количеством слов в заголовках статей Википедии) • Построение для каждой N-граммы ее морфологических вариаций • Для каждой из вариации производится поиск по всем заголовкам статей Википедии. Таким образом, для каждой N-граммы мы получаем набор статей Википедии, которые могут описывать ее значение
Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
Шаг 2: Разрешение лексической многозначности терминов • На данном шаге для каждой N-граммы необходимо выбрать наиболее подходящую статью Википедии из набора статей, который был построен для нее на предыдущем шаге • Подходящее значение многозначного слова может быть установлено при помощи контекста, в котором это слово упоминается • В статье используется метод, предложенный Д. Турдаковым и П. Велиховым
Шаг 2: Метод, предложенный Д. Турдаковым и П. Велиховым • Используя страницы описания многозначных терминов и перенаправляющие страницы, строится набор возможных значений термина • Для каждого возможного значения термина вычисляется степень его семантической близости с контекстом • В итоге выбирается то значение термина, степень семантической близости с контекстом которого было наибольшим • Результатом работы данного шага является список терминов, в котором каждый термин соотнесен с одной соответствующей статьей Википедии
Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
Шаг 3: Построение семантического графа • По списку терминов, полученном на предыдущем шаге, строится семантический взвешенный граф • Узлы графа - термины документа • Ребро между парой терминов означает, что эти два термина семантически близки • Весом ребра является численное значение семантической близости этих двух терминов
Шаг 3: Вычисление семантической близости терминов Можно посчитать двумя способами: • используя гипертекстовые ссылки между статьями Википедии, которые соответствуют данным терминам • измеряя косинус угла между векторами, построенными по текстам соответствующих статей Википедии
Шаг 3: Мера Дайса • Мера Дайса помогает определить семантическую близость двух концепций Википедии: D푖푐푒 퐴, 퐵 = 2 ∗ |푛 퐴 푛(퐵)| 푛 퐴 + |푛(퐵)| • где 푛 퐴 , 푛(퐵) – наборы входящих и исходящих ссылок, ведущих к 퐴 и 퐵, соответственно; |푛 퐴 푛(퐵)| – в данной статье количество ссылок, ведущих из 퐴 в 퐵 и наоборот • Экспериментально было выяснено, что одни типы ссылок свойственны семантически близким концепциям, в то время как другие приводят к ошибочным результатам
Шаг 3: Типы ссылок Веса для различным ссылок: See also 5 Обычные ссылки 1 Обратные See also 2 Ссылки в инфобоксах 1 Двойные ссылки 2 Обратные обычные ссылки 0.5 Общая категория 1.5 Даты 0 + нормализация
Шаг 3: Граф к статье «Apple to Make ITunes More Accessible For the Blind»
Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
Шаг 4: Сообщества • Семантически близкие термины «сбиваются» в плотные подграфы, в так называемые сообщества • Наиболее массивные и сильно связанные подграфы, как правило, соотносятся с главными темами документа • Термины, входящие в такие подграфы, являются ключевыми для данного документа
Шаг 4: Модулярность графа • является свойством графа и некоторого его разбиения на подграфы • Показывает, насколько данное разбиение качественно: в том смысле, что существует много ребер, лежащих внутри сообществ, и мало ребер, лежащих вне сообществ(соединяющих сообщества между собой) • На практике значение модулярности, лежащее в диапазоне от 0.3 до 0.7, означает, что сеть имеет вполне различимую структуру с сообществами, и применение алгоритма обнаружения сообществ имеет смысл
Шаг 4: Обнаружение сообществ в семантическом графе • Для решения этой задачи используется алгоритм Гирвана-Ньюмана • Для оценки качества разбиения некоторого графа на сообщества предложено использовать меру модулярности графа • В результате работы алгоритма исходный граф разбивается на подграфы, которые представляют собой тематические сообщества терминов
Шаг 4: Промежуточность Промежуточность — мера важности, пропорциональная числу кратчайших путей от всех вершин до всех, проходящих через данное ребро 푙: 퐶퐵 푙 = 푠≠푡, 푠,푡∈푉 휎푠푡 (푙) 휎푠푡 휎푠푡 — количество кратчайших путей из 푠 в 푡, 휎푠푡(푙) — количество кратчайших путей из 푠 в 푡, через 푙.
Шаг 4: Алгоритм Гирвана-Ньюмана 1. Вычислить промежуточность для всех рёбер графа. 2. Удалить ребро с наивысшим показателем 3. Пересчитать промежуточность с учётом изменений 4. Повторять предыдущий шаг до тех пор, пока не будет падения модулярности либо рёбра не закончатся Ребра с наибольшей промежуточностью находятся именно на границах между сообществами, тогда как ребра с малой промежуточностью – внутри сообществ. Алгоритм выполняет иерархическую кластеризацию. Итогом работы алгоритма является дендрограмма.
Шаг 4: Пример графа Промежуточность (для вершин). Красный — низкая, синий — высокая.
Шаг 4: Дендрограмма На дендрограмме объекты располагаются по иерархическим уровням так, чтобы подчеркнуть их взаимное сродство на основе измеряемых свойств.
Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
Шаг 5: Выбор подходящих сообществ • Выполняется ранжирование на основании плотности и информативности сообщества • Предполагается, что все сообщества с высоким рангом будут содержать важные (ключевые) термины
Шаг 5: Плотность и информативность сообщества • Плотность сообщества - сумма весов ребер, соединяющих вершины этого сообщества • Информативность сообщества – сумма tf.idf- терминов, входящих в это сообщество, деленное на количество терминов сообщества. • Ранг сообщества вычисляется как плотность сообщества, умноженная на его информативность • На практике имеет смысл использовать 1-3 сообщества с наивысшими рангами • На основании различных мер можно отсеивать термины из выбранных сообществ
Шаг 5: Вычисление tf.idf для терминов в пределах сообщества 푇퐹 × 퐼퐷퐹 = 푓푟푒푞(푇, 퐷) 푠푖푧푒(퐷) × −푙표푔2 푐표푢푛푡 푇 푁 푓푟푒푞(푇, 퐷) — частота термина 푇 в данном документе 퐷, 푠푖푧푒(퐷) — количество слов в документе 퐷, 푐표푢푛푡 푇 — количество статей из сообщества, в которых встречается термин 푇, 푁 — количество статей в сообществе.
Архитектурные принципы • Для достижения лучшей производительности семантическая близость всех пар терминов Википедии заранее не вычислялась. • Данные, необходимые для подсчета семантической близости терминов на лету, а именно, – заголовки статей Википедии, – информация о ссылках между статьями, – статистическая информация о терминах были загружены в оперативную память (на тот момент 4.5 Гб) • Дополнительная нормализация заголовков статей может ускорить поиск соответствующих статей для N-грамм на первом этапе.
Экспериментальная оценка метода Полнота и точность извлеченных ключевых слов оценивались участниками эксперимента: из каждого документа выбиралось 5-10 ключевых терминов, имеющих соответствующую статью в Википедии и покрывающих все темы документа. В результате для каждого документа были выбраны ключевые термины, выделенные, по крайней мере, двумя участниками.
Полнота и точность Полнота = |{изв. вручную} {изв. автоматически}| |{изв. вручную}| Точность = |{изв. вручную} {изв. автоматически}| |{изв. автоматически}|
Результаты реализованного приложения • Для 30 блог-постов (500-900 слов) технической тематики: – 180 ключевых терминов, выделенных участниками эксперимента вручную – 297 выделенных автоматически – 127 вручную выделенных ключевых слов оказались среди выделенных автоматически • Таким образом, полнота равна 68%, а точность равна 41%
Пересмотр оценки полноты и точности • Иногда метод извлекает ключевые термины с лучшим покрытием основных тем документа, чем это делает человек • Для каждого блог-поста участник должен был изучить ключевые термины, выделенные автоматически, и, по возможности, расширить свой набор ключевых слов • После такого пересмотра были получены 213 ключевых слов, выделенных вручную (вместо 180) • В итоге, полнота равна 73% и точность – 52%
Преимущества метода • не требует обучения (в случае локального хранения информации требуется лишь синхронизация с Википедией) • основной источник информации, Википедия, постоянно обновляется, остается актуальной и покрывает много специфических областей знаний • ключевые термины сгруппированы по темам, и метод извлекает столько различных тематических групп терминов, сколько различных тем покрывается в документе • высокая эффективность с точки зрения качества извлеченных ключевых терминов
Литература • Мария Гринева, Максим Гринев. 2009. Анализ текстовых документов для извлечения тематически сгруппированных ключевых терминов • Denis Turdakov, Pavel Velikhov. 2008. Semantic Relatedness Metric for Wikipedia Concepts Based on Link Analysis and its Application to Word Sense Disambiguation • Olena Medelyan, Ian H. Witten, David Milne. 2008. Topic Indexing with Wikipedia
Мадорский. Извлечение тематически сгруппированных ключевых терминов из текстовых документов

More Related Content

Мадорский. Извлечение тематически сгруппированных ключевых терминов из текстовых документов

  • 1. Извлечение тематически сгруппированных ключевых терминов из текстовых документов Автор: Мадорский Константин Научный руководитель: м.н.с. Баева Н.В.
  • 2. Ключевые термины • Ключевые термины — термины в документе, которые могут дать высокоуровневое описание содержания документа для читателя • Извлечение ключевых терминов является базисным этапом для многих задач обработки естественного языка, например: – классификация документов – кластеризация документов – составление аннотации текста – вывод общей темы документа
  • 3. О методе • использует Википедию в качестве информационного ресурса для вычисления семантической близости терминов • использует два базовых алгоритма: – алгоритм вычисления меры семантической близости, посчитанной по Википедии – алгоритм анализа сетей Гирвана-Ньюмана для выделения плотных подграфов
  • 4. Википедия • www.wikipedia.org • свободно распространяемая энциклопедия, на сегодняшний день являющаяся самой большой энциклопедией в мире • в русскоязычном разделе на 23 ноября 2014 года количество статей — 1 165 325 • в англоязычном разделе на 25 апреля 2014 года количество статей — 4 500 000
  • 6. Википедия: визуализация категорий tools.wmflabs.org/vcat/catgraphRedirect?wiki=wiki pedia&lang=ru&cat=География&d=0&n=0&format= png&links=graph&sub=1&depth=2
  • 7. Википедия: визуализация категорий (1) tools.wmflabs.org/vcat/catgraphRedirect?wiki=wiki pedia&lang=ru&cat=География&d=0&n=0&format= png&links=graph&sub=0&depth=2
  • 8. Википедия: страницы для многозначных терминов
  • 11. Википедия: See also .ɾ쾱徱.ǰ/ɾ쾱/Искусственныйинтеллект
  • 12. Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
  • 13. Шаг 1: Извлечение терминов- кандидатов • Разбор исходного документа на все возможные N-граммы (N ограничено максимальным количеством слов в заголовках статей Википедии) • Построение для каждой N-граммы ее морфологических вариаций • Для каждой из вариации производится поиск по всем заголовкам статей Википедии. Таким образом, для каждой N-граммы мы получаем набор статей Википедии, которые могут описывать ее значение
  • 14. Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
  • 15. Шаг 2: Разрешение лексической многозначности терминов • На данном шаге для каждой N-граммы необходимо выбрать наиболее подходящую статью Википедии из набора статей, который был построен для нее на предыдущем шаге • Подходящее значение многозначного слова может быть установлено при помощи контекста, в котором это слово упоминается • В статье используется метод, предложенный Д. Турдаковым и П. Велиховым
  • 16. Шаг 2: Метод, предложенный Д. Турдаковым и П. Велиховым • Используя страницы описания многозначных терминов и перенаправляющие страницы, строится набор возможных значений термина • Для каждого возможного значения термина вычисляется степень его семантической близости с контекстом • В итоге выбирается то значение термина, степень семантической близости с контекстом которого было наибольшим • Результатом работы данного шага является список терминов, в котором каждый термин соотнесен с одной соответствующей статьей Википедии
  • 17. Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
  • 18. Шаг 3: Построение семантического графа • По списку терминов, полученном на предыдущем шаге, строится семантический взвешенный граф • Узлы графа - термины документа • Ребро между парой терминов означает, что эти два термина семантически близки • Весом ребра является численное значение семантической близости этих двух терминов
  • 19. Шаг 3: Вычисление семантической близости терминов Можно посчитать двумя способами: • используя гипертекстовые ссылки между статьями Википедии, которые соответствуют данным терминам • измеряя косинус угла между векторами, построенными по текстам соответствующих статей Википедии
  • 20. Шаг 3: Мера Дайса • Мера Дайса помогает определить семантическую близость двух концепций Википедии: D푖푐푒 퐴, 퐵 = 2 ∗ |푛 퐴 푛(퐵)| 푛 퐴 + |푛(퐵)| • где 푛 퐴 , 푛(퐵) – наборы входящих и исходящих ссылок, ведущих к 퐴 и 퐵, соответственно; |푛 퐴 푛(퐵)| – в данной статье количество ссылок, ведущих из 퐴 в 퐵 и наоборот • Экспериментально было выяснено, что одни типы ссылок свойственны семантически близким концепциям, в то время как другие приводят к ошибочным результатам
  • 21. Шаг 3: Типы ссылок Веса для различным ссылок: See also 5 Обычные ссылки 1 Обратные See also 2 Ссылки в инфобоксах 1 Двойные ссылки 2 Обратные обычные ссылки 0.5 Общая категория 1.5 Даты 0 + нормализация
  • 22. Шаг 3: Граф к статье «Apple to Make ITunes More Accessible For the Blind»
  • 23. Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
  • 24. Шаг 4: Сообщества • Семантически близкие термины «сбиваются» в плотные подграфы, в так называемые сообщества • Наиболее массивные и сильно связанные подграфы, как правило, соотносятся с главными темами документа • Термины, входящие в такие подграфы, являются ключевыми для данного документа
  • 25. Шаг 4: Модулярность графа • является свойством графа и некоторого его разбиения на подграфы • Показывает, насколько данное разбиение качественно: в том смысле, что существует много ребер, лежащих внутри сообществ, и мало ребер, лежащих вне сообществ(соединяющих сообщества между собой) • На практике значение модулярности, лежащее в диапазоне от 0.3 до 0.7, означает, что сеть имеет вполне различимую структуру с сообществами, и применение алгоритма обнаружения сообществ имеет смысл
  • 26. Шаг 4: Обнаружение сообществ в семантическом графе • Для решения этой задачи используется алгоритм Гирвана-Ньюмана • Для оценки качества разбиения некоторого графа на сообщества предложено использовать меру модулярности графа • В результате работы алгоритма исходный граф разбивается на подграфы, которые представляют собой тематические сообщества терминов
  • 27. Шаг 4: Промежуточность Промежуточность — мера важности, пропорциональная числу кратчайших путей от всех вершин до всех, проходящих через данное ребро 푙: 퐶퐵 푙 = 푠≠푡, 푠,푡∈푉 휎푠푡 (푙) 휎푠푡 휎푠푡 — количество кратчайших путей из 푠 в 푡, 휎푠푡(푙) — количество кратчайших путей из 푠 в 푡, через 푙.
  • 28. Шаг 4: Алгоритм Гирвана-Ньюмана 1. Вычислить промежуточность для всех рёбер графа. 2. Удалить ребро с наивысшим показателем 3. Пересчитать промежуточность с учётом изменений 4. Повторять предыдущий шаг до тех пор, пока не будет падения модулярности либо рёбра не закончатся Ребра с наибольшей промежуточностью находятся именно на границах между сообществами, тогда как ребра с малой промежуточностью – внутри сообществ. Алгоритм выполняет иерархическую кластеризацию. Итогом работы алгоритма является дендрограмма.
  • 29. Шаг 4: Пример графа Промежуточность (для вершин). Красный — низкая, синий — высокая.
  • 30. Шаг 4: Дендрограмма На дендрограмме объекты располагаются по иерархическим уровням так, чтобы подчеркнуть их взаимное сродство на основе измеряемых свойств.
  • 31. Шаги метода 1. Извлечение терминов-кандидатов 2. Разрешение лексической многозначности терминов 3. Построение семантического графа 4. Обнаружение сообществ в семантическом графе 5. Выбор подходящих сообществ
  • 32. Шаг 5: Выбор подходящих сообществ • Выполняется ранжирование на основании плотности и информативности сообщества • Предполагается, что все сообщества с высоким рангом будут содержать важные (ключевые) термины
  • 33. Шаг 5: Плотность и информативность сообщества • Плотность сообщества - сумма весов ребер, соединяющих вершины этого сообщества • Информативность сообщества – сумма tf.idf- терминов, входящих в это сообщество, деленное на количество терминов сообщества. • Ранг сообщества вычисляется как плотность сообщества, умноженная на его информативность • На практике имеет смысл использовать 1-3 сообщества с наивысшими рангами • На основании различных мер можно отсеивать термины из выбранных сообществ
  • 34. Шаг 5: Вычисление tf.idf для терминов в пределах сообщества 푇퐹 × 퐼퐷퐹 = 푓푟푒푞(푇, 퐷) 푠푖푧푒(퐷) × −푙표푔2 푐표푢푛푡 푇 푁 푓푟푒푞(푇, 퐷) — частота термина 푇 в данном документе 퐷, 푠푖푧푒(퐷) — количество слов в документе 퐷, 푐표푢푛푡 푇 — количество статей из сообщества, в которых встречается термин 푇, 푁 — количество статей в сообществе.
  • 35. Архитектурные принципы • Для достижения лучшей производительности семантическая близость всех пар терминов Википедии заранее не вычислялась. • Данные, необходимые для подсчета семантической близости терминов на лету, а именно, – заголовки статей Википедии, – информация о ссылках между статьями, – статистическая информация о терминах были загружены в оперативную память (на тот момент 4.5 Гб) • Дополнительная нормализация заголовков статей может ускорить поиск соответствующих статей для N-грамм на первом этапе.
  • 36. Экспериментальная оценка метода Полнота и точность извлеченных ключевых слов оценивались участниками эксперимента: из каждого документа выбиралось 5-10 ключевых терминов, имеющих соответствующую статью в Википедии и покрывающих все темы документа. В результате для каждого документа были выбраны ключевые термины, выделенные, по крайней мере, двумя участниками.
  • 37. Полнота и точность Полнота = |{изв. вручную} {изв. автоматически}| |{изв. вручную}| Точность = |{изв. вручную} {изв. автоматически}| |{изв. автоматически}|
  • 38. Результаты реализованного приложения • Для 30 блог-постов (500-900 слов) технической тематики: – 180 ключевых терминов, выделенных участниками эксперимента вручную – 297 выделенных автоматически – 127 вручную выделенных ключевых слов оказались среди выделенных автоматически • Таким образом, полнота равна 68%, а точность равна 41%
  • 39. Пересмотр оценки полноты и точности • Иногда метод извлекает ключевые термины с лучшим покрытием основных тем документа, чем это делает человек • Для каждого блог-поста участник должен был изучить ключевые термины, выделенные автоматически, и, по возможности, расширить свой набор ключевых слов • После такого пересмотра были получены 213 ключевых слов, выделенных вручную (вместо 180) • В итоге, полнота равна 73% и точность – 52%
  • 40. Преимущества метода • не требует обучения (в случае локального хранения информации требуется лишь синхронизация с Википедией) • основной источник информации, Википедия, постоянно обновляется, остается актуальной и покрывает много специфических областей знаний • ключевые термины сгруппированы по темам, и метод извлекает столько различных тематических групп терминов, сколько различных тем покрывается в документе • высокая эффективность с точки зрения качества извлеченных ключевых терминов
  • 41. Литература • Мария Гринева, Максим Гринев. 2009. Анализ текстовых документов для извлечения тематически сгруппированных ключевых терминов • Denis Turdakov, Pavel Velikhov. 2008. Semantic Relatedness Metric for Wikipedia Concepts Based on Link Analysis and its Application to Word Sense Disambiguation • Olena Medelyan, Ian H. Witten, David Milne. 2008. Topic Indexing with Wikipedia

Editor's Notes

  • #17: Первый пункт своими словами
  • #22: See Also Links: Most Wikipedia articles have a See Also section that lists related articles. These links explicitly signify that a linked page is semantically related. Therefore, see also links are very important for semantic relatedness and we assign the highest weight to the links of this type. Inverse See Also Links (incoming links) are also quite important and they receive a high weight also. Double links: Articles that link to each other directly by regular links in most cases turn out to be quite related, hence these types of links come next in our weighting scheme. Links between articles in the same category: Wikipedia has a rich category structure, and articles belonging to the same category are related. However, some categories are very broad and consist of unrelated articles. For example, the category “Indian Actors” contains over 600 articles and the degree of relatedness between all of these actors is not very significant. Therefore, we identify articles that have both: a link between them, and share the same category, as the next most relevant type of link. The rest of the links are just regular Wikipedia links, but we separate out of them into further types: Date links and Template Links, which receive the lowest weights in our scheme. In our experiments we have used the following weighting scheme, shown in Table 1.