«Расстояние Левенштейна» для анализа данных в модели

Время прочтения: 4 мин.

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

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

Рассмотрим стандартную ситуацию, когда аудитору для проверки гипотезы о некорректности заполнения данных в модели необходимо было отобрать из огромного массива данных номера договоров, в которых, возможно, допущена ошибка при наполнении данными модель.

Обработка генеральной совокупности данных вручную могла занять существенное время.  Для сокращения временных издержек мы приняли решение разработать алгоритм на основе Python, который автоматически сравнивает строковые значения и количественно выражает разницу между ними. Это позволило существенно снизить объем выборки для ручной проверки.

В основу алгоритма был положен расчет расстояния Левенштейна – посимвольной разницы между двумя строковыми значениями. На выходе алгоритма мы получили номера договоров из одного источника, из другого и «расстояние» между ними.

Далее представлены примеры:

Поясним как рассчитывается этой расстояние. В первом примере у нас есть два номера – «1111-А» и «1111/А». Что нам надо сделать чтобы оба номера были одинаковыми? Достаточно, например, в первом поменять символ «-» на символ «/», тогда оба номера будут равны «1111/А». Или наоборот, мы можем поменять во втором «/» на «-» и будет два номера «1111-А». На самом деле не важно, какой именно номер мы поменяем – важно, что нам будет достаточно поменять всего 1 символ и номера будут равны друг другу. Отсюда и берется расстояние Левенштейна – нам достаточно проделать путь всего в 1 шаг (тут шаг – замена символа), чтобы строки были равны.

Во втором примере у нас одинаковые строки, соответственно нам не надо ничего делать – мы уже на месте.

В третьем примере в первом номере на один символ больше – на «1» в конце. Или мы можем сказать, что во втором номере не хватает единички и ее надо добавить, опять же это не важно, важно, что нам достаточно добавить/удалить один символ и строки будут равны. Соответственно, расстояние Левенштейна равно 1.

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

Код программы:

import pandas as pd
from tqdm import tqdm
from itertools import product
from Levenshtein import distance
# pandas - работа с файлами Excel (*.xlsx/*.csv)
# tqdm - визуализация итераций
# itertools - функция product для составления декартова произведения двух списков
# Levenshtein - расстояние Левенштейна

# подгрузка номеров договоров
# конкретная реализация зависит от того, в каком виде у вас сформированы данные
# здесь номера договоров из обоих источников находятся в одном файле - YOUR_DATA.XLSX
data = pd.read_excel('../dog_obes.xlsx')

# отдельные объекты под номера договоров из каждого источника
agrs_1 = data.iloc[:,0].dropna()
agrs_2 = data.iloc[:,1].dropna()

"""
расчет расстояния Левенштейна (посимвольной разницы) для каждой пары договоров

отметим, что такой алгоритм вычислительно "тяжелый"
как в смысле сложности алгоритма, например, для 2000 в одном и втором источнике мы получим
мы получим 2000 * 2000 = 4 000 000 уникальных пар (!), т.е. сложность равна O(n * m)
так и в смысле дополнительно выделяемой памяти
поэтому, запись результата сравнения договоров идет сразу в файл, чтобы не "грузить" оперативную память
"""

with open('agr_diff.csv', 'w', encoding = 'windows-1251') as f: # agr_diff.csv - выходной файл
    
    f.write('~'.join(['AGR_S1', 'AGR_S2', 'DIFF'])) # запись заголовка таблицы
    f.write('\n')    
    
    # основной цикл - сравнение каждого с каждым
    for agr in tqdm(agrs_1.astype(str).items()): 
        for row in [[x[0], x[1], distance(x[0], x[1])] for x in list(product([agr[1]],   agrs_2.to_list()))]:
            f.write('~'.join([str(x) for x in row]))
            f.write('\n')

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

В процессе ручного анализа полученной выборки была подтверждена гипотеза о многочисленных ошибках в введенных данных в модель – по номеру договора обеспечения, в т.ч. связанных с отсутствием реквизитов (пустое значение), наличием лишних букв или некорректным их обозначением, отсутствием промежуточных цифр, пробелов, точек, наличием дефисов вместо слэша или отсутствием слэша (например, «1751/2», «17512»), и т.д.

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

Не бойтесь экспериментировать и осваивать современные языки программирования.