Учебное пособие по Python: таблица поиска имен для наборов данных с нечеткими именами

Серия учебных пособий по статистике Python

Учебное пособие по Python: таблица поиска имен для наборов данных с нечеткими именами

Повышение точности сопоставления имен людей за счет использования комбинаций компонентов имени

Это шестая статья нашего путешествия в мир исследования данных Python. Щелкните ссылку над заголовком, чтобы получить список всех статей.

Цель этого урока

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

Алгоритм может обрабатывать опечатки, специальные символы и другие различия в атрибуте имени НО он не работает, если какой-либо из компонентов имени отсутствует на стороне имени учетной записи Twitter.

Проблема в том, что имя учетной записи Twitter объединено пользователем и, следовательно, не детерминировано (мы предполагаем, что он не использует псевдоним и есть шанс на совпадение). Как мы видели в последнем руководстве, мы пытались исправить определенные аномалии, но разработанное решение кажется недостаточно надежным. Поэтому нам нужно потратить дополнительное время на создание более надежного решения, которое решает проблему «отсутствующих компонентов имени» с помощью комбинаторики.

Получите Jupyter Notebook, чтобы получить дополнительные пояснения к руководству

В рамках моего собственного продвижения в мир науки о данных Python я недавно начал экспериментировать с Jupyter Notebook для Python.

Jupyter Notebook - это веб-приложение с открытым исходным кодом, которое позволяет создавать и обмениваться документами, содержащими живой код, уравнения, визуализации и повествовательный текст. Области применения: очистка и преобразование данных, численное моделирование, статистическое моделирование, визуализация данных, машинное обучение и многое другое.

Это просто потрясающе и с помощью дистрибутива Ancaconda устанавливается за считанные минуты (ну, вам нужно немного свободного дискового пространства на вашей машине).

Я интегрировал его в свой учебный процесс и с этого момента буду более подробно описывать построение алгоритмов и кодирование в специальных блокнотах Jupyter.

Вы можете найти блокнот Jupyter для этого руководства в моем проекте Github. Использование Jupyter Notebook (наряду с этим руководством) позволяет вам экспериментировать и вносить изменения в кодовые последовательности в записной книжке в реальном времени. Удивительно, но Github отображает файл Jupyter Notebook в исходном и легко читаемом формате веб-представления. Если хотите посмотреть формат только для чтения!

Обработка отсутствующих компонентов имени в процессе сопоставления имен

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

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

«Доктор. мед. Питер А. Эшер (Цюрих) »или
«Доктор. мед. Питер А. Эшер (Цюрих) », где пользователь допустил опечатку.

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

Мягкое введение в комбинации и перестановки

Чтобы получить любую комбинацию компонентов имени в случае отсутствия элементов, мы должны понимать основные концепции комбинаторики.

Должны ли мы использовать комбинации или перестановки

Давайте сначала ответим на этот вопрос. Слишком далеко от школы? Посмотрите это полезное шестиминутное видео (с сайта betterExplained.com), которое освежает различные концепции.

Python уже предоставляет в своей стандартной библиотеке itertools функции permutations и комбинации, которые мы хотим изучить немного дальше.

Давайте применим его к нашему образцу имени, чтобы понять его механизм. Сначала функция комбинаций

А также функция перестановок:

Как вы можете видеть в перестановке, порядок компонента имени играет роль. Есть кортеж для ('peter','alfred'), а также один для ('alfred','peter'). В комбинации порядок компонентов имени не имеет значения.

Для нас порядок не играет роли, 'peter escher' рассматривается как'escher peter' Мы все равно сортируем компоненты имени, прежде чем применять алгоритм двойного метафона. Поэтому мы используем комбинированную функцию.

Всегда думайте о «пин-коде» как о шпаргалке для «перестановок». Любой механизм блокировки с помощью пин-кода основан на количестве перестановок данного набора «цифр» из 10 элементов: «1234» не разблокирует экран, который заблокирован с помощью «4321».

Создание каталога поиска для комбинаций имен

Теперь мы создаем класс справочника, который позволяет нам хранить комбинации компонентов имени и сравнивать их с именем человека, которое мы получили из Twitter API.

Добавление человека в справочник

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

Схема последовательности этого метода показана ниже, давайте рассмотрим различные необходимые вспомогательные методы.

Метод: generate_combinations

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

сам кортеж из трех элементов
все кортежи комбинации с 2 элементами из 3
все кортежи комбинации с 1 из 3 элементов

Например, приведенные ниже 3 кортежа имен приводят к следующему списку комбинаций.

Метод: add_combinations_to_directory

В этом методе мы создаем каталог, добавляя каждый кортеж в наш каталог поиска.

Наша справочная директория состоит из кортежа из двух словарей, которые используются для хранения пар ключ-значение. Наши ключи - это двойной кортеж метафона, созданный из имени, а значение - это уникальный идентификатор человека.

__lookup_dict = ({}, {})

Метод показан ниже

В строке кода 3 мы создаем нормализованную строку имени из кортежа компонента имени. Метод выглядит следующим образом

Результатом является строка в нижнем регистре отсортированных элементов имени конкатенированного кортежа:

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

В строках кода 5 и 10 мы проверяем, есть ли в словаре запись с таким же ключом.

Если нет, мы добавляем новую пару ключ-значение.
Если запись уже существует, мы сначала проверяем, сохранен ли уже person_id. Если нет, мы добавляем person_id в массив значений.

Метод: add_person_to_lookup_directory

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

В качестве примера мы добавляем в нашу таблицу поиска следующих трех человек.

Как видно из выходных данных, наша запись для Питера с ключом 'PTR' имеет массив идентификаторов из трех человек.

Соответствие имени в нашем справочнике

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

Чего не хватает match_name метода, который позволяет нам искать имя, полученное через Twitter API. Мы займемся этим сейчас.

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

В строке кода 3 мы генерируем все комбинации компонентов имени с помощью нашего существующего метода, и выполняется итерация по всем комбинациям.
В строках кода 5 и 6 мы подготавливаем ключевой кортеж комбинированного кортежа для поиска.
В строке кода 7 мы проверяем, существует ли наш ключ. Как видите, мы выполняем проверку только с первой записью двойного кортежа метафона, которая хранится в первой записи справочника. Мы оставляем полную реализацию на основе функции ранжирования двойного метафонного кортежа в качестве упражнения.

if metaphone_tuple[0] in self.__lookup_dict[0]:

Запуск метода match_name в нашем примере загруженного каталога поиска дает следующий результат:

Как мы видим, у нас есть два кортежа, которые указывают на один person_id и один кортеж peter, который указывает на 3 человека (очевидно, что фамилии повторно используются несколькими людьми). Два кортежа, указывающие на одного человека, имеют одинаковый идентификатор 'A123'. Это означает, что наш матч идентифицировал ровно одного человека. Если бы в нашем результате были кортежи из одного человека, указывающие на разных людей, это означало бы, что наше совпадение не является уникальным.

Поэтому мы улучшаем наш метод, чтобы он также выполнял эту проверку на уникальность (строка кода 12–20):

Есть ли в нашем списке совпадений один или несколько кортежей, которые всегда указывают на одного человека?
Если да, мы нашли уникальную запись, в противном случае мы вернем None.

Давайте проверим алгоритм на нашем тестовом образце (как объяснялось выше, весь контент также доступен в виде интерактивной записной книжки Jupyter).

Итак, мы готовы применить новую стратегию поиска к нашей программе.

Реорганизуйте существующие классы

Расширение класса GovAPI

Мы улучшаем наш абстрактный GovAPI класс, интегрируя экземпляр NameLookupDirectory класса.

class GovAPI(ABC):
  def __init__(self):
    self._members = []
    self._nameLookupDirectory =  NameLookupDirectory()

Мы улучшаем add_person_record последовательностью кода для создания нашего справочного каталога (строка кода 22–29).

Мы также добавляем новый метод для match_name проверки, который будет вызываться, когда мы попытаемся объединить записи таблицы.

def match_name(self, name_tuple):
    return self._nameLookupDirectory.match_name(name_tuple)

Метод belowcalculate_name_matching больше не требуется.

Рефакторинг класса SocialMediaAnalyzer

В этом классе мы также должны реорганизовать метод calculate_name_matching, теперь мы вызываем для сопоставления методmatch_name экземпляра класса govAPI (строка 5).

Если у нас есть совпадение (7–14), мы получаем полную запись о человеке из класса govAPI.

Помните, что метод thecalculate_name_matching вызывается через метод Panda apply для каждой записи строки, и в результате строка будет дополнена дополнительными новыми столбцами:

panda_data = { 'ScreenName' : self.__col_screen_name,
               'Name': self.__col_name,
               'Description': self.__col_description,
               "FollowersCount": self.__col_followers_count,
               "FriendsCount": self.__col_friends_count,
               "Party": self.__col_party
               }
df = DataFrame(panda_data, index=self.__labels)
df = df.apply(self.__calculate_name_matching, axis=1)

Когда мы снова выполняем нашу программу, наша таблица, полученная из Twitter, выглядит так:

В col_match1 мы перечисляем уникальный идентификатор govAPI, а в col_match2 наш список кортежей результатов, который был проанализирован. Например.

Для имени Twitter «Christian Levrat» мы нашли три записи в нашей таблице поиска:

"Christian leverat", который соответствует идентификатору 1 человека (1150)
«Христианин», который соответствует идентификатору 5 человек
Leverat, который соответствует идентификатору 1 человека (11509

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

Оцените наш алгоритм на предмет ложных срабатываний

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

Что такое ложные срабатывания?

Ложноположительный результат - это когда вы получаете положительный результат теста, тогда как вы должны были получить отрицательный результат. Иногда это называют ложной тревогой или ложноположительной ошибкой. Обычно он используется в области медицины, но может применяться и в других областях (например, при тестировании программного обеспечения). (Ref)

Ложное срабатывание означает, что есть проблемы с точностью нашего алгоритма.

Ложноположительный 1

Просматривая нашу таблицу Twitter, мы встречаем записи ниже.

Оба они указывают на один и тот же идентификатор человека. При проверке записи в таблице govAPI мы получаем следующую запись «74 Christoph Eymann», которая не имеет учетной записи Twitter и поэтому не может быть найдена в таблице Twitter.

Что пошло не так:

«Christophe Darbellay», а также «Christoph Mörgeli» в прошлом были политиками Швейцарского совета и, следовательно, не входили в список govAPI, который мы отфильтровали только для активных членов.

«Christophe» и «Christoph» преобразуются в одну и ту же двойную метафонную строку и соответствуют записи 74 govAPI «Christoph Leymann». В связи с тем, что в списке govAPI есть только одно лицо с фамилией «Кристоф», наш алгоритм возвращает ложное срабатывание для любого человека с фамилией «Кристоф (е)» и сопоставляет его с «Кристоф Лейманн». Если бы govAPI перечислил двух человек с фамилией «Кристоф», запись совпадения указала бы на идентификатор двух человек и больше не была бы уникальной. В этом случае наш алгоритм не даст ложного срабатывания.

Решение:

Что ж, нам нужно скорректировать наш алгоритм и сделать его более строгим. Это означает, что мы изменяем условие нашего генератора кортежей имен, которое мы

разрешены только те кортежи компонентов имени, которые содержат хотя бы фамилию в качестве элемента.

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

def add_person_to_lookup_directory(self, person_id, name_tuple, last_name_pos):
    tuples = self.generate_combinations(name_tuple)
    self.add_combinations_to_directory(tuples, person_id, name_tuple[last_name_pos])

Теперь в метод add_combinations_to_directory мы добавляем только кортежи, содержащие last_name (строка 3).

Повторный запуск нашей программы приводит к следующей статистике совпадений.

На самом деле это не лучше, чем в нашей первой попытке (см. Следующий учебник), но мы получили более надежный алгоритм сопоставления. Похоже, что используемый список политиков Twitter не совсем актуален в контексте активных членов федерального собрания. Однако это кое-что для следующего урока, где мы хотим завершить тему сопоставления данных и двигаться дальше.

Исходный код вы можете найти в соответствующем проекте Github, список всех остальных статей - здесь.

Тогда удачного кодирования.

Учебное пособие по Python: таблица поиска имен для наборов данных с нечеткими именами

Серия учебных пособий по статистике Python