Речь пойдет про алгоритмы выделения ключевых слов Rake, YAKE! И TextRank. Выделение ключевых слов становится все более актуальным с постоянным ростом объемов текстовой информации, которую необходимо каким-то образом классифицировать по тематике. Рассмотренные модели обладают интересными свойствами и преимуществами по сравнению с классическими алгоритмами, поскольку не требуют обучения.
В условиях значительного потока информации, в том числе и текстовой, появляется необходимость фильтровать ее автоматически, с помощью алгоритмов. Одним из возможных подходов к выделению смысла текста и оценке его релевантности является задача извлечения ключевых слов. Идея заключается в том, чтобы выделить слова или фразы, которые являются наиболее важными для всего текста и передают его основную тематику.
Алгоритмы без учителя обладают преимуществом в условиях большого объема данных – нет необходимости в разметке данных, которая для данной задачи является достаточно трудоемкой. Дополнительной характеристикой методов, о которых пойдет речь, является отсутствие моделей. Все 3 метода основаны на эвристиках, которые заданы заранее, а не обучаются. Это позволяет обрабатывать каждый текст отдельно и не требует большой выборки текстов.
Основной идеей алгоритма является то, что ключевые слова зачастую находятся в окружении стоп-слов и пунктуации.
Обычно в множество стоп-слов входят предлоги, союзы и другие функциональные части речи. В большинстве приложений интеллектуального текстового анализа стоп-слова считаются незначимыми и убираются на этапе предобработки, однако в данном методе играют важную роль.
Стоп-слова и пунктуация расценивается как разделители фраз – текст разбивается по этим элементам на фразы кандидаты. Далее фразы-кандидаты ранжируются по метрике deg(w)/freq(w) и выбираются k кандидатов с наибольшим значением метрики.
Метрика основана на следующей логике:
- freq(w) – Частота слова в тексте, поощряет часто встречающиеся слова
- deg(w) - Определяется как сумма совместных появлений других слов с этим словом. Совместным появлением считается появление в одной фразе. Данная метрика поощряет слова, которые часто встречаются в длинных кандидатах
- freq(w)/deg(w) – Поощряет слова, которые появляются в основном в длинных кандидатах
YAKE!
Этот метод похож по смыслу на Rake, однако была убрана идея о выделении фраз на основе стоп-слов. В данном методе используется стандартная для текстового анализа методика выделения слов и фраз с помощью токенизации. Фактически такая методика позволяет проверить все сочетания слов на их важность, а не только разделенные стоп-словами. YAKE! использует более сложную метрику, чем Rake – она собирается из 5 отдельных метрик.
Casing
Метрика Casing основана на идее о том, что ключевые слова зачастую могут быть названиями или аббревиатурами. Она измеряет количество раз, когда слово в тексте встречается с большой буквы или является аббревиатурой (написано полностью большими буквами).
Где:
- TF(U(w)) – Количество раз, когда слово начинается с большой буквы
- TF(A(w)) – Количество раз, когда слово отмечается алгоритмом, как аббревиатура (Состоит из больших букв)
- TF(w) – Общая частота слова
Word Position
Авторы утверждают, что ключевые слова чаще стоят в начале текста. Из-за этого вводится метрика Word Position, которая учитывает положение слова относительно других.
Где:
- Senw – множество позиций слова в документе
Word Frequency
Как и в Rake учитывается частота слова. В данном случае частота слова нормируется с учетом среднего и стандартного отклонения частоты:
Где:
- TF(w) – Частота слова в тексте
Word Relatedness to Context
Авторы утверждают, что данная метрика способна оценивать насколько слово похоже на стоп-слово – насколько оно важно для контекста. Метрика использует количество слов, появляющихся слева и справа от слова-кандидата
Где:
- WL – отношение количества слов слева от кандидата к количеству всех слов, которые появляются вместе с ним
- WR – отношение количества слов справа от кандидата к количеству всех слов, которые появляются вместе с ним
- PL – Отношение количества разных слов, которые появляются слева от кандидата к MaxTF
- PR - Отношение количества разных слов, которые появляются справа от кандидата к MaxTF
Утверждается, что стоп-слова имеют высокое значение метрики WRel
DifSentence
Эта метрика учитывает количество предложений, в которых используется слово-кандидат.
Где:
- SF(w) – Частота появления слова в предложениях
- # Sentences – Количество предложений в тексте
Итоговая метрика
Итоговая метрика составляется из описанных выше метрик.
Далее происходит сортировка ключевых слов по этой метрике и выбирается k наиболее значимых.
TextRank
Метод TextRank наиболее сильно отличается от двух предыдущих. Он использует идею, что любой текст можно представить в виде графа, где слова являются вершинами, а связи между ними – ребрами графа. После переведения текста в графовое представление используется классическая метрика важности вершин графа PageRank.
Построение графа
Для построения графа вокруг каждого слова берется контекст – берутся все слова, которые находятся на расстоянии n-слов от главного. Например, для контекста размера 2 берутся два слова слева и два слова справа от текущего. Все слова в контексте текущего связываются с ним ребрами графа.
PageRank
Рассмотрим метрику, которая используется для выделения важных вершин на графе.
Где:
- S(Vi)S(Vi) – важность i-ой вершины
- In(Vi)In(Vi) – множество вершин, имеющих входящие в i-ую вершину ребра
- Out(Vi) – множество вершин, связанных с i-ой вершиной исходящими из нее ребрами
- dd –Коэффициент затухания, выбирается пользователем
Важность инициализируется случайными числами и потом итеративно сходится к правильным значениям. Таким образом, важность слова определяется связью с другими важными словами.
Python-реализация алгоритмов
Для демонстрации работы алгоритмов используем текст про алгоритм Евклида из Википедии.
Все три алгоритма решают одну и ту же задачу с разных сторон и с использованием разной логики. Результаты работы алгоритмов из-за этого отличаются. Нельзя однозначно сказать, какой из них лучше решает конкретную задачу. На отдельной задаче имеет смысл тестировать качество каждого из алгоритмов и делать выбор исходя из этого.