Как превратить книгу о Гарри Поттере в граф знаний

Обработка естественного языка — это не только нейронные сети, а данные — это не только строки, числа и перечисления. Область работы с данными простирается намного дальше. К старту флагманского курса по Data Science представляем вашему вниманию перевод из блога разработчиков графовой базы данных neo4j о том, как при помощи SpaCy и Selenium извлечь из книги граф взаимоотношений героев. Подробности и код, как всегда, под катом.

Скорее всего, вы уже видели созданный Эндрю Бевериджем граф Game of Thrones. Эндрю построил граф взаимодействий книжных персонажей. Если два персонажа появляются на некотором расстоянии друг от друга в тексте, мы можем предположить, что в книге они как-то связаны или взаимодействуют. Я решил создать подобный проект, но выбрать популярную книгу, не имеющую известной мне стратегии извлечения данных из сети. Так родился проект по извлечению графа персонажей книги “Гарри Поттер и философский камень”.

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

Нам известна глава первого появления каждого героя, это поможет разделить персонажей. Чтобы найти все упоминания персонажа, воспользуемся основанным на правилах матчером SpaCy. Останется определить метрику совместных вхождений и сохранить результаты в Neo4j.

Порог совпадений возьмём из проекта графа "Игры престолов": когда два персонажа появляются в пределах 14 слов друг от друга, будем считать, что они взаимодействовали, и сохраним количество этих взаимодействий как вес отношений.

План

1. Парсим страницу фэндома Гарри Поттера.

2. Предварительно обрабатываем текст книги, решая проблему разрешения совместных ссылок.

3. Распознаём сущности сопоставлением на основе правил SpaCy.

4. Делаем выводы об отношениях персонажей.

5. Сохраняем результаты в графовой базе данных Neo4j.

На случай если вы хотите повторить шаги, я подготовил блокнот Google Colab.

Скрэпинг страниц фэндома Гарри Поттера

Работать будем с Selenium, соберём данные персонажей книги "Гарри Поттер и философский камень", вот список их упоминаний.

wd = webdriver.Chrome('chromedriver',chrome_options=chrome_options)
wd.get(url)
character_dict = dict()
elem = wd.find_element_by_class_name("mw-parser-output")

# Locate character by chapter
tables = elem.find_elements_by_tag_name('table')
for i, chapter in enumerate(tables):
  list_of_characters = []
  characters = chapter.find_elements_by_tag_name('a')
  for character in characters:
    if not character.get_attribute('title'):
      continue
    list_of_characters.append({'title': character.get_attribute('title'), 'url': character.get_attribute('href')})
  character_dict['chapter_' + str(i + 1)] = list_of_characters

Благодаря коду выше мы получили список персонажей с информацией об их первом появлении в книге. У каждого персонажа есть веб-страница с подробной информацией о нём.

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

  for chapter in character_dict:
    for index, character in enumerate(character_dict[chapter]):
      # Rate limit sleep
      time.sleep(1)
      # Get the character page with selenium
      wd.get(character['url'])
      # Enrich aliases
      try:
        alias_div = wd.find_element_by_xpath("//div[@data-source = 'alias']")
        aliases = alias_div.find_elements_by_tag_name('li')
        result = []
        for a in aliases:
          # Ignore under the cloak-guise and the name he told
          if "disguise" in a.text or "the name he told" in a.text:
            continue
          alias = a.text.split('[')[0].split('(')[0].strip()
          result.append(alias)
        character_dict[chapter][index]['aliases'] = result
      except:
        pass
      # Enrich blood
      character_dict[chapter][index]['blood'] = enrich_single_item('blood')
      # Enrich nationality
      character_dict[chapter][index]['nationality'] = enrich_single_item('nationality')

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

• Грегори Гойл (под маскировкой Polyjuice).

Проигнорируем псевдонимы под маскировкой Polyjuice. А ещё, кажется, Гарри сказал Стэнли Шанпайку, что он Невилл Лонгботтом, это мы тоже пропустим. Прежде чем продолжить извлечение именованных сущностей, сохраним собранную информацию в Neo4j. Наши атрибуты:

• имя;

• адрес страницы;

• псевдонимы;

• национальность;

• группа крови;

• пол;

• биологический вид.

Взаимоотношения:

• дом;

• сообщество, которому предан персонаж;

• семья.

entity_query = """
UNWIND $data as row
MERGE (c:Character{name:row.title})
SET c.url = row.url,
    c.aliases = row.aliases,
    c.blood = row.blood,
    c.nationality = row.nationality,
    c.species = row.species,
    c.gender = row.gender
FOREACH (h in CASE WHEN row.house IS NOT NULL THEN [1] ELSE [] END | MERGE (h1:House{name:row.house}) MERGE (c)-[:BELONGS_TO]->(h1))
FOREACH (l in row.loyalty | MERGE (g:Group{name:l}) MERGE (c)-[:LOYAL_TO]->(g))
FOREACH (f in row.family | MERGE (f1:Character{name:f.person}) MERGE (c)-[t:FAMILY_MEMBER]->(f1) SET t.type = f.type)    

"""
with driver.session() as session:
  for chapter in character_dict:
    session.run(entity_query, {'data': character_dict[chapter]})

Сохраняем информацию о персонажах в Neo4j

Похоже, Гермиона также известна как Маленькая мисс Совершенство и предана Обществу содействия благосостоянию эльфов. К сожалению, данные не разделены по времени, поэтому Фред Уизли уже сейчас оказывается шурином Маленькой мисс Совершенство.

Предварительная обработка текста

Прежде всего, мы должны получить текст книги. Я нашёл на GitHub репозиторий с текстами первых четырёх книг о Гарри Поттере. К данным не прилагается лицензия, поэтому предположу, что вправе использовать данные в образовательных целях с чистой совестью:

def get_text(url):
  try:
    return requests.get(url).text
  except:
    print("No text was found")
    return None

Мы должны быть внимательны и передать функции ссылку на необработанное текстовое содержимое, и это должно сработать.

Когда я впервые извлекал сущности, то забыл предварительно провести разрешение кореферентности, то есть определить относящиеся к одному и тому же объекту лингвистические выражения. Посмотрите мой пост о конвейере извлечения информации, в нём показан работающий пример.

Я искал модели разрешения кореферентности с открытым исходным кодом, но, насколько я знаю, их всего две. Первая — NeuralCoref, она работает поверх SpaCy, вторая — AllenNLP. Ранее я работал с NeuralCoref и решил посмотреть, как работает AllenNLP.

К сожалению, в Colab 16 ГБ ОЗУ и память быстро закончилась, когда я вводил всю главу в AllenNLP. Затем я нарезал главу на предложения, но это работало очень медленно, возможно, из-за фреймворка BERT, поэтому я по умолчанию использую NeuralCoref, который легко справляется с целой главой и работает быстрее. Код подготовки текста:

def coref_resolution(text):
    """Function that executes coreference resolution on a given text"""
    doc = nlp(text)
    # fetches tokens with whitespaces from spacy document
    tok_list = list(token.text_with_ws for token in doc)
    for cluster in doc._.coref_clusters:
        # get tokens from representative cluster name
        cluster_main_words = set(cluster.main.text.split(' '))
        for coref in cluster:
            if coref != cluster.main:  # if coreference element is not the representative element of that cluster
                if coref.text != cluster.main.text and bool(set(coref.text.split(' ')).intersection(cluster_main_words)) == False:
                    # if coreference element text and representative element text are not equal and none of the coreference element words are in representative element. This was done to handle nested coreference scenarios
                    tok_list[coref.start] = cluster.main.text + \
                        doc[coref.end-1].whitespace_
                    for i in range(coref.start+1, coref.end):
                        tok_list[i] = ""

    return "".join(tok_list)

Распознавание сущностей с помощью сопоставления на основе правил SpaCy

Я хотел использовать модель распознавания именованных сущностей, пробовал модели SpaCy, HuggingFace, Flair и даже Stanford NLP, но ни одна из них не работала достаточно хорошо, поэтому вместо обучения модели я воспользовался шаблонами сопоставления на основе правил в SpaCy.

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

def get_matcher_patterns(character):
  matcher_pattern = []
  stop_words = ['of', 'the', 'at', 'family', 'keeper', 'wizard', 'fat', 'de', 'hogwarts']
  parts_of_name = [el for el in character['title'].split(' ') if len(el) > 2]
  # Append the whole pattern
  matcher_pattern.append([{"LOWER": n.lower(), "IS_TITLE": True} for n in parts_of_name])
  
  # Append parts of names
  if not "'" in character['title']: # Skip names like Vernon Dursley's secretary
    for n in parts_of_name:
      if n.lower() in stop_words: # Skip appending stop words
        continue
      matcher_pattern.append([{"LOWER": n.lower(), "IS_TITLE": True}])
      # Special case for Ronald Weasley -> Also add Ron
      if n == "Ronald":
        matcher_pattern.append([{"LOWER": "ron", "IS_TITLE": True}])
  return matcher_pattern

Сначала как искомый шаблон добавляем полное имя, затем разбиваем имя пробелом и создаём шаблон из каждого слова. Пример: определяя шаблоны для Альбуса Дамблдора, получим три различных шаблона, которые могут представлять данного персонажа:

• полное имя: Альбус Дамблдор;

• имя: Альбус;

• фамилия: Дамблдор.

Есть и кое-какие исключения: я определил список стоп-слов, которых не должно быть в шаблоне персонажа. Например, в книге присутствует персонаж Смотритель зоопарка [Keeper of the Zoo]. Интуитивно понятно, что не следует определять "of" или "the" как шаблоны сопоставления сущности.

Хочется, чтобы все отдельные слова были чувствительны к регистру. Это делается, чтобы все слова black не распознавались как ссылка на Сириуса Блэка.

Будем считать, что речь идёт о Сириусе Блэке, только если Black написано заглавными. Решение не идеально: Black может быть написано заглавными из-за того, что слово находится в начале предложения, но такого решения достаточно.

Особый случай — Рональд Уизли, который в тексте в основном Рон. Не отделяются друг от друга сущности "секретарь Вернона Дурсли" и "филин Драко Малфоя".

При таком подходе возникает две проблемы. Первая — в тексте "Альбус Дамблдор — хороший волшебник" найдётся три совпадения, поскольку в шаблоне есть как полное имя, так и его части. Решение: мы будем отдавать приоритет сущностям длиннее. Если в одном и том же месте есть совпадение из нескольких слов, а также другое совпадение из одного слова, то приоритет отдадим совпадению с несколькими словами.

  # Find matches
  doc = nlp(text)
  matches = matcher(doc)
  result = []
  for match_id, start, end in matches:
      string_id = nlp.vocab.strings[match_id]  # Get string representation
      span = doc[start:end]  # The matched span

      # Get predicates for correct result appendment
      exists_longer = [(start == e['start'] and end < e['end']) or (start > e['start'] and end == e['end']) for e in result]
      same = [start == e['start'] and end == e['end'] for e in result]
      shorter_end = [start == e['start'] and end > e['end'] for e in result]
      shorter_start = [start < e['start'] and end == e['end'] for e in result]
      
      # Append to results
      if any(exists_longer): # If there is a longer version of the given entity already in results
        continue
      
      if any(shorter_end): # If there is any entity with the same start span but has shorter end
        del result[shorter_end.index(True)]
        result.append({'string_id': [string_id], 'start': start, 'end': end, 'text': span.text}) 
      elif any(shorter_start): # If there is any entity with the same end span but has shorter start
        del result[shorter_start.index(True)]
        result.append =({'string_id': [string_id], 'start': start, 'end': end, 'text': span.text}) 
      elif not any(same): # If not exists yet
        result.append({'string_id': [string_id], 'start': start, 'end': end, 'text': span.text})
      else: # Add more entities to a single span
        i = same.index(True)
        result[i]['string_id'].append(string_id)

Результаты работы шаблона сопоставления с приоритезацией.

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

Затем проверяется, не длиннее ли все существующие сущности в той же позиции, чем текущий результат. Наконец, если ещё нет существующих сущностей, добавляется новый результат. Интересна последняя инструкция "else", ведь иногда одной сущности соответствует несколько персонажей: "Уизли, иди сюда!". В книге есть несколько Уизли. Проблема возникает, когда на человека ссылаются по его фамилии, а персонажей с такой фамилией много. Чтобы разграничить такие сущности, мы должны придумать общее решение:

hardcoded_options = dict()
hardcoded_options['Malfoy'] = ['Draco Malfoy']
hardcoded_options['Patil'] = ['Padma Patil', 'Parvati Patil']
hardcoded_options['Tom'] = ['Tom']

def handle_multiple_options(result, doc):
  needs_deduplication = [(i,x) for i,x in enumerate(result) if len(x['string_id']) > 1]
  for index, multiple_options in needs_deduplication:
    # Special logic for Dursleys, if there if Mr. then Vernon, if Mrs. then Petunia
    prefix = doc[multiple_options['start']-3 : multiple_options['start']]
    if (multiple_options['text'] == 'Dursley') and ("Mr." in prefix.text):
      resolution = ["Vernon Dursley"]
    elif (multiple_options['text'] == 'Dursley') and ("Mrs." in prefix.text):
      resolution = ["Petunia Dursley"]
    # Find nearest entity
    else:
      end_char = multiple_options['end']
      distance = sys.maxsize
      resolution = []
      for possible_option in result:
        # Skip multiple options and entities that don't have any of the multiple option
        if (not len(possible_option['string_id']) == 1) or (not possible_option['string_id'][0] in multiple_options['string_id']):
          continue
        new_distance = abs(multiple_options['end'] - possible_option['end'])
        if new_distance < distance:
          distance = new_distance
          resolution = possible_option['string_id']
      
      if not resolution:
        try:
          ho = hardcoded_options[multiple_options['text']]
          if len(ho) == 1:
            resolution = ho
          else:
            resolution = [random.choice(ho)]
        except:
          print(f"no way to disambiguate {multiple_options['text']} from options: {multiple_options['string_id']}")
    
    result[index]['string_id'] = resolution
  return result

Эта функция длиннее. Мы начинаем с определения требующих разделения сущностей. Я написал логику, которая устраняет неоднозначность с мистером и миссис Дурсли. Если перед термином "Дурсли" присутствует "мистер", то это ссылка на Вернона, а если "миссис" — на Петунию. И вот обобщённое решение: алгоритм присваивает ссылку ближайшему соседу.

Теперь предположим, что невозможно выбрать между Гарри Поттером, Джеймсом Поттером и Лили Поттер. Тогда алгоритм определяет ближайшую в тексте сущность из трёх и присваивает текущему элементу её значение. Есть исключения, когда полное или обычное имя не упоминается в пределах одной главы, так что как последнее средство я жёстко закодировал варианты.

Выявление отношений между персонажами

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

Если два характера встречаются на расстоянии 14 слов, предполагается, что они должны были взаимодействовать. Чтобы не искажать результаты, я объединил сущности. О чём я говорю? Есть два предложения:

"У Гарри был хороший день. После обеда он пошёл поговорить с Дамблдором".

Здесь будет определено три сущности: "Гарри", "Он" как ссылка на Гарри и "Дамблдор". Решая задачу в лоб, мы могли бы сделать вывод о двух взаимодействиях между Гарри и Дамблдором, поскольку два упоминания "Гарри" близки к упоминанию "Дамблдора". Такого хочется избежать, поэтому я объединил сущности в последовательности, где на одного персонажа ссылаются как на одну сущность. Посчитаем взаимодействия пар персонажей:

def get_distances(result, distance_threshold):
  #sort by start character
  result = sorted(result, key=lambda k: k['start'])
  compact_entities = []
  # Merge entities
  for entity in result:
    # If the same entity occurs, prolong the end 
    if (len(compact_entities) > 0) and (compact_entities[-1]['string_id'] == entity['string_id']):
      compact_entities[-1]['end'] = entity['end']
    else:
      compact_entities.append(entity)
  distances = list()
  # Iterate over all entities
  for index, source in enumerate(compact_entities[:-1]):
    # Compare with entities that come after the given one
    for target in compact_entities[index + 1:]:
      if (source['string_id'] != target['string_id']) and (abs(source['end'] - target['start']) < distance_threshold):
        link = sorted([source['string_id'][0], target['string_id'][0]])
        distances.append(link)
      else:
        break
  # Count the number of interactions
  return Counter(map(tuple, distances))
  

Сохранение результатов в графовой базе данных Neo4j

Мы извлекли граф взаимодействий между персонажами, и осталось только сохранить результаты в графовой базе данных. Запрос на импорт очень прост, поскольку мы имеем дело с сетью моночастиц. Если вы используете подготовленный мной блокнот Colab, для хранения результатов проще всего создать бесплатные Neo4j Sandbox или инстанс базы данных Aura:

def store_to_neo4j(distances):
  data = [{'source': el[0], 'target': el[1], 'weight': distances[el]} for el in distances]
  with driver.session() as session:
    session.run("""
    UNWIND $data as row
    MERGE (c:Character{name:row.source})
    MERGE (t:Character{name:row.target})
    MERGE (c)-[i:INTERACTS]-(t)
    SET i.weight = coalesce(i.weight,0) + row.weight
    """, {'data': data})

Визуализируем результаты, чтобы изучить их:

На первый взгляд, результаты выглядят классно. В центре сети — Гарри Поттер, книга в основном написана о Гарри. Видно, что мне следовало бы добавить несколько стоп-слов в шаблон матчера. Век живи — век учись.

• Код проекта.

• Песочница алгоритмов на графах.

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

Data Science и Machine Learning

• Профессия Data Scientist

• Профессия Data Analyst

• Курс «Математика для Data Science»

• Курс «Математика и Machine Learning для Data Science»

• Курс по Data Engineering

• Курс «Machine Learning и Deep Learning»

• Курс по Machine Learning

Python, веб-разработка

• Профессия Fullstack-разработчик на Python

• Курс «Python для веб-разработки»

• Профессия Frontend-разработчик

• Профессия Веб-разработчик

Мобильная разработка

• Профессия iOS-разработчик

• Профессия Android-разработчик

Java и C#

• Профессия Java-разработчик

• Профессия QA-инженер на JAVA

• Профессия C#-разработчик

• Профессия Разработчик игр на Unity

От основ — в глубину

• Курс «Алгоритмы и структуры данных»

• Профессия C++ разработчик

• Профессия Этичный хакер

А также:

• Курс по DevOps