Блог Игоря Шевченко

Cуммаризация с помощью TextRank

В марте интернеты бурно обсуждали покупку компанией «Yahoo!» сервиса «Summly». Купленное у семнадцатилетнего стартапера за тридцать миллионов долларов приложение для айфона показывает новости, автоматически создавая для них краткое изложение (саммари, если не по-русски).

Оценивая величину поднявшегося шума по поводу этой покупки и основателя сервиса Ника Д'Алоизио, который стал после неё одним из самых молодых «самодельных» миллионеров, говорили, что только пиар окупил бы вложения «Яху!». Но и сам суммаризатор как сервис кажется перспективным. Вполне соответствует тенденциям: распространяются мобильные устройства, с которых можно выходить в интернет, но сложно читать длинные статьи. Да и вообще длинные тексты читают всё реже. Наконец, есть смысл заняться технологиями автоматической суммаризации, потому что их еще есть куда улучшать.

Есть два основных подхода к созданию саммари: обобщение и извлечение. Обобщающие алгоритмы анализируют структуру текста, чтобы «понять», о чем он, а затем создают новый текст с основным содержанием. В общем, обобщение работает так, как делал бы живой человек. И хотя понятно, что за таким подходом будущее, сейчас подобные методы еще развиты слабо. Поэтому чаще применяются извлекающие алгоритмы, которые анализируют текст статистически, а потом выбирают из него наиболее важные куски.

Например, можно преобразовывать текст в граф. Тогда для определения самых важных вершин можно использовать алгоритмы ссылочного ранжирования вроде PageRank, который когда-то лег в основу Гугла. По связям между вершинами графа PageRank назначает каждой из них рейтинг, учитывая две вещи:

1) количество ребер, которые идут из других вершин,

2) рейтинг этих ребер.

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

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

Этот алгоритм, который называется TextRank, предложила в этой статье Рада Михальча (надеюсь, правильно транскрибировал). Статья довольно понятная, сам алгоритм несложный. Его можно реализовать на питоне примерно в тридцать строк, используя библиотеки nltk для работы с естественным языком и networkx для графов.

Примерно так.

from nltk.tokenize import sent_tokenize

sentences = sent_tokenize(text)

Разбиваем текст на предложения с помощью токенизатора из nltk.

from nltk.tokenize import RegexpTokenizer
from nltk.stem.snowball import RussianStemmer

tokenizer = RegexpTokenizer(r'\w+')
lmtzr = RussianStemmer()
words = [set(lmtzr.stem(word) for word in tokenizer.tokenize(sentence.lower()))
         for sentence in sentences]

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

from itertools import combinations

pairs = combinations(range(len(sentences)), 2)
scores = [(i, j, similarity(words[i], words[j])) for i, j in pairs]

Для каждой пары предложений вычислим их похожесть.

def similarity(s1, s2):
    if not len(s1) or not len(s2):
        return 0.0
    return len(s1.intersection(s2))/(1.0 * (len(s1) + len(s2)))

В качестве меры похожести возьмем отношение количества одинаковых слов в предложениях к суммарной длине предложений. Кажется, это называется коэффициентом Сёренсена.

scores = filter(lambda x: x[2], scores)

Уберем пары, у которых нет ничего общего (похожесть равна нулю).

import networkx as nx

g = nx.Graph()
g.add_weighted_edges_from(scores)

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

pr = nx.pagerank(g)

Посчитаем пейджранки в этом графе.

result = sorted(((i, pr[i], s) for i, s in enumerate(sentences) if i in pr), 
                key=lambda x: pr[x[0]], reverse=True)

Результатом будет список предложений, отсортированный по их пейджранку.

Полностью код выглядит так:

from itertools import combinations
from nltk.tokenize import sent_tokenize, RegexpTokenizer
from nltk.stem.snowball import RussianStemmer
import networkx as nx

def similarity(s1, s2):
    if not len(s1) or not len(s2):
        return 0.0
    return len(s1.intersection(s2))/(1.0 * (len(s1) + len(s2)))

def textrank(text):
    sentences = sent_tokenize(text)
    tokenizer = RegexpTokenizer(r'\w+')
    lmtzr = RussianStemmer()
    words = [set(lmtzr.stem(word) for word in tokenizer.tokenize(sentence.lower()))
             for sentence in sentences]

    pairs = combinations(range(len(sentences)), 2)
    scores = [(i, j, similarity(words[i], words[j])) for i, j in pairs]
    scores = filter(lambda x: x[2], scores)

    g = nx.Graph()
    g.add_weighted_edges_from(scores)
    pr = nx.pagerank(g)

    return sorted(((i, pr[i], s) for i, s in enumerate(sentences) if i in pr),
                  key=lambda x: pr[x[0]], reverse=True)

def extract(text, n=5):
    tr = textrank(text)
    top_n = sorted(tr[:n])
    return ' '.join(x[2] for x in top_n)

Сразу же можно предложить несколько изменений:

  1. Не учитывать при определении похожести частые слова (например, предлоги, частицы), наличие которых в двух предложениях ничего не говорит о смысловой связи между ними.
  2. Попробовать вычислять коэффициент похожести другими способами, возможно, какие-то будут давать лучший результат.
  3. Использовать другой алгоритм ссылочного ранжирования (HITS, например).

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

Вот, например, сюжет фильма «Иван Васильевич меняет профессию» из Википедии, ужатый до пяти предложений:

В присутствии управдома Ивана Васильевича Бунши Шурик испытывает машину на небольшой мощности, и стена между квартирами Шурика и Шпака исчезает. Увидев пришельцев и приняв их за демонов, Феофан убегает за стражей, а Иван Грозный пугается чёрной кошки и убегает в квартиру Шурика. На обеде Иван Васильевич Бунша заигрывает с миловидной Марфой Васильевной (супругой Ивана Грозного) и приходит в состояние алкогольного опьянения. Но, наконец, срабатывает починенная Шуриком машина времени и Иван Васильевич Бунша с Жоржем Милославским вбегают в свой XX век. Воспользовавшись суматохой, из машины «Скорой помощи» выбегает Иван Грозный и бежит в квартиру к Шурику, который снова запускает свою машину.

Хорошо работает c новостями. Так выглядит саммари новости «В Москве и Белгороде разрешили правый поворот на „красный“»:

Российская Госавтоинспекция запустила эксперимент, в рамках которого поворот направо на запрещающий сигнал светофора будет разрешен на некоторых перекрестках Москвы и Белгорода. В Москве эксперимент был запущен в 13:00 на шести перекрестках. На светофорах на перекрестках, участвующих в эксперименте, установлен представленный ранее знак в виде зеленой стрелки, указывающей направо. Перед въездом на перекрестки также расположены щиты, сообщающие о проведении эксперимента. Инициатива о разрешении поворота направо на «красный» была впервые предложена в 2011 году.

20 июня 2013 14:43

Комментарии

Володя Коган 29 июля 2013 08:33

Хорошая надстройка\замена Evernote - Clearly и подобного. Я думаю эти ребята уже работают над самари либо готовы "проинвестировать" в команду, которая разрабатывает подобное :)

{% шутка %}
Дальше самари заменит какой-нибудь emotificator - вместо текста гифка эмоции, которую вызывает новость :D
{% конец шутки %}

Игорь Шевченко 29 июля 2013 10:36

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

Володя Коган 31 июля 2013 14:25

Твоя статья из твоего же самаризатора :D

>>
Тогда всё получается так же логично, как и для веб-страниц: одно предложение рекомендует другое, а самыми важными являются те, которые содержат информацию из нескольких других предложений. После этого у нас есть список предложений, которые представлены в виде множества слов. Вершинами в нем являются предложения (если точнее, то номера предложений в тексте), а ребра между ними имеют вес, равный похожести вершин, которым оно инцидентно. Текстранк предложения учитывается вместе с другими факторами — его положением в тексте, длиной, первым словом, количество имен собственных или еще какими-нибудь сложными фичами. Так выглядит саммари новости «В Москве и Белгороде разрешили правый поворот на „красный“»: Российская Госавтоинспекция запустила эксперимент, в рамках которого поворот направо на запрещающий сигнал светофора будет разрешен на некоторых перекрестках Москвы и Белгорода.

Игорь Шевченко 31 июля 2013 14:54

Володя Коган, не сказать, что это самодостаточный текст, но кажется, тут саммари лучше сделать тяжело :)

Сонечка Мармеладова 8 декабря 2015 21:23

Вопрос: как эта программа работает, если sent_tokenize по умолчанию считает, что работает с английским языком, и при попытке подсунуть этой функции текст на русском ругается на юникод?

Игорь Шевченко 8 декабря 2015 21:46

Сонечка Мармеладова, я проверил сейчас на python 2.7.6 с nltk 3.1. Потребовалось скачать punkt из пакетов nltk, чтобы sent_tokenize в принципе заработал. С русским всё отработало нормально:

>>> from nltk.tokenize import sent_tokenize
>>> sent_tokenize(u'Один. Два.')
[u'\u041e\u0434\u0438\u043d.', u'\u0414\u0432\u0430.']

Можно посмотреть ваш код и с какой ошибкой он падает?

Оставить комментарий

Вы можете войти через Твитер или ВКонтакте