На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Сентября 2024

Эффективность алгоритмов сопоставления персональных данных

Effectiveness of algorithms of comparison of the personal data
Статья опубликована в выпуске журнала № 1 за 2011 год.
Аннотация:Рассматривается эффективность работы усовершенствованного алгоритма сравнения данных о физических лицах в разнородных системах на основе фонетических правил русского языка и проводится сопоставление с результатами, полученными с использованием других методов поиска сходных объектов.
Abstract:The article describes the effectiveness of the improved algorithm for comparing personal data in heterogeneous systems, based on the phonetic rules of the Russian language. Also the article compares results of applying this algorithm with results obtained using other methods of searching similarities.
Авторы: Гусятников В.Н. (victorgsar@rambler.ru) - Саратовский государственный социально-экономический университет, доктор физико-математических наук, Палькин Е.А. (pea@bankfininvest.ru) - Саратовский государственный социально-экономический университет
Ключевые слова: релевантность алгоритма, фонетический алгоритм, распознавание речи, алгоритмы анализа строк
Keywords: relevance of algorithm, phonetic algorithm, speech recognition, string algorithms
Количество просмотров: 16482
Версия для печати
Выпуск в формате PDF (5.09Мб)
Скачать обложку в формате PDF (1.32Мб)

Размер шрифта:       Шрифт:

Методы и алгоритмы анализа строк находят практическое применение во многих областях науки и информационных технологий: глобальные поисковые системы, сжатие данных, криптография, распознавание речи, компьютерное зрение, генетика и молекулярная биология. Одной из актуальных сфер применения таких алгоритмов являются также задачи сопровождения БД, входящих в состав различных информационных систем (ИС). Типичными и часто обсуждаемыми на форумах программистов являются задачи сопоставления и идентификации объектов, сведения о которых хранятся в разных БД. В частности, к подобным задачам относят поиск, сопоставление и слияние персональных данных о физических лицах. Это могут быть, например, списки клиентов телефонных компаний, покупателей различных товаров и услуг, клиентов банка, сведения о пассажирах различных видов транспорта, которые должны поступать в единую БД, и т.д.

Разнородность систем управления БД, используемых в ИС, и структур данных, содержащих информацию, подлежащую слиянию, влечет за собой необходимость классификации данных при сопоставлении объектов. Подчас один и тот же объект, описанный в соответствии с требованиями одной БД, не может быть однозначно идентифицирован в другой БД без специальных процедур сравнения.

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

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

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

Для последующих шагов существует ряд алгоритмов, таких как алгоритм Вагнера–Фишера [1] или алгоритм Смита–Ватермана [2], позволяющих количественно оценить близость строк между собой, используя в качестве меры близости дистанции редактирования. К подобным мерам относится расстояние Левенштейна, то есть минимальное количество элементарных операций вставки, удаления и замены одного символа, необходимых для превращения одной строки в другую, или расстояние Хэмминга, используемое для сравнения строк одинаковой размерности.

Следует отметить, что ни один из вышеперечисленных алгоритмов изначально не разрабатывался для сравнения данных о физических лицах. Специфика обработки имен физических лиц более полно учтена в известных алгоритмах сравнения двух строк по их звучанию – Soundex и MetaPhone. Описание алгоритма Soundex дано в классическом учебнике по программированию [3], алгоритм MetaPhone адаптирован для русского языка в работе [4]. Эти алгоритмы основаны на построении некоторой хэш-функции, преобразующей исходные строки в хэш-код, одинаковый для схожих строк. Процесс сравнения двух строк сводится к вычислению хэш-кодов этих строк и их последующего строгого сравнения. Строки, имеющие одинаковый хэш-код, считаются похожими.

Об эффективности подобных алгоритмов говорит тот факт, что в некоторых языках программирования сравнение подобного рода организовано в качестве стандартной процедуры. Например, в MySQL и PHP функция Soundex является встроенной [5].

В основе алгоритма Фонетик, реализованного в данной работе в среде Delphi 7, лежит вариант алгоритма MetaPhone, предложенный в [4].

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

Алгоритм включает следующие шаги.

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

2.   Удаление непроизносимых букв, а также знаков препинания.

3.   Замена сходных по начертанию латинских букв (A, B, C, E, H, O, P, T X, Y) на русские аналогичного начертания (А, В, С, Е, Н, О, Р, Т, Х, У).

4.   Выработка ключа с использованием имени и отчества либо только инициалов в зависимости от выбранной настройки и полноты исходных данных.

5.   Замена гласных букв на те, которые слышатся на их месте в безударном слоге. Буквы О, Ы, А, Я заменяются на А; Ю, У на У; Е, Е, Э, И на И. Несмотря на то, что в русском языке произношение буквы часто не соответствует написанию, сокращать слова до одних согласных нельзя, поскольку существует ряд парных глухих и звонких. С точки зрения грамматики русского языка такой подход не является абсолютно верным, но на практике показывает хорошие результаты.

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

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

8.   Удаление парных согласных. Частой ошибкой является некорректное написание парных согласных. Для этих ситуаций создаются одинаковые ключи с одной повторяющейся буквой, которые будут найдены независимо от написания.

9.   Замена типовых для русского языка окончаний фамилий на специальные символы. Эта команда сокращает время обработки и экономит место для хранения ключей. Данное преобразование имеет смысл только для фамилий.

Пункты 1, 2, 5, 6, 8, 9 с некоторыми изменениями заимствованы из реализации алгоритма MetaPhone [4]. Для повышения качества сравнения алгоритм дополнен следующими этапами.

10.     В большинстве случаев в информации- онной системе вместе с фамилией присутству- ют имя и отчество, тогда имеет смысл привязать их к ключу. Имя и отчество обрабатываются отдельно от фамилии согласно пп. 1–6 алгоритма и дополняют ключ, полученный на основе фамилии. Если в одной системе в данных присутствуют лишь инициалы, то у обеих строк данные для обработки сокращаются до фамилии и первых букв имени и отчества, преобразованных к верхнему регистру.

11.     В связи с тем, что персональные данные нередко получают из источника данных невысокого качества, о чем свидетельствует наличие инициалов вместо полноценных имени и отчества, имеет смысл заменять в ключе символы инициалов на сходные по написанию. Если рассмотреть графическое начертание букв, то И имеет сходство с Н, следовательно, в инициалах они могут быть заменены друг на друга. Замены производятся следующим образом:

Исходный символ

А, Л

Б, В, Е

Г, Т

И, Н, П

Ц, Ш, Щ

Заменяющий символ

А

В

Т

Н

Ш

Остальные буквы остаются без изменений.

12.     Итоговый ключ формируется конкатенацией ключа, полученного из фамилии, и результатов обработки имени и отчества или инициалов.

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

Таблица 1

Исходное слово

Ключ

Годеева А.В.

ГАД9АВ

Годиева И.А.

ГАД9ИА

Иванюков П.В.

ИВАНУК4ПВ

Иванников С.А.

ИВАНИК4СА

Ковалева С.А.

КАВАЛИВА СА

Ковалева О.А.

КАВАЛИВА ОА

Голушков О.В.

ГАЛУШК4ОВ

Колушков С.П.

КАЛУШК4СП

Куликов А.А.

КУЛИК4АА

Куликова О.И.

КУЛИК9ОИ

Белов А.А.

БИЛ4АА

Соколова Т.В.

САКАЛ9ТВ

Азовская А.С.

АЗ$АС

Ильина И.П.

ИЛ1ИП

Алиева А.Т.

АЛ9АТ

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

Для проверки релевантности алгоритма Фонетик из автоматизированной банковской системы было выгружено 25907 записей о физических лицах. Этот массив данных был получен слиянием нескольких БД и содержал некоторое количество дублирующих записей о физических лицах, которые не были обнаружены средствами СУБД во время слияния. Весь массив данных обработан экспертами, которые выявили в нем 661 дублирующую запись.

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

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

Таблица 2

Результат работы алгоритма

Верная гипотеза для входных данных

H0

H1

H0

H0 верно принята

H0 неверно принята (ошибка второго рода)

H1

H0 неверно отвергнута (ошибка первого рода)

H0 верно отвергнута

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

Подпись:  Схема подсчета ошибок при сопоставлении объектовПо итогам работы всех алгоритмов была заполнена результирующая таблица с количеством ошибок для каждого алгоритма (табл. 3).

Таблица 3

Алгоритм

Выявлено сходство

Ошибка 1-го рода

Ошибка 2-го рода

Выявлено различие

Фонетик

660

1

0

25246

Дистанция Левенштейна

653

8

74

25172

Soundex

650

11

48

25198

Прямое сравнение

638

23

0

25246

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

По количеству ошибок первого рода алгоритм Фонетик на порядок эффективнее алгоритмов, вычисляющих дистанцию Левенштейна, и алгоритма Soundex. Алгоритм прямого сравнения оказался наименее эффективным по количеству ошибок 1-го рода.

Алгоритм Фонетик при сравнении строк, содержащих фамилию, имя и отчество физического лица, показывает высокую стабильность и эффективность в работе, отличается хорошей приспособленностью к нормам и правилам русского языка, высокой релевантностью, низкими показателями ошибок первого и второго рода. Использование технологии поиска сходных записей на основе данного алгоритма позволяет снизить избыточность БД, сократить долю ручного труда опера- торов, в реальном времени отслеживать историю обращений клиента, а также проводить интеллектуальную обработку, например резервирование или репликацию, и прочие операции с данными, требующие больших затрат времени. Фонетик хорошо подходит в качестве инструмента сопровождения автоматизированных банковских систем, систем денежных переводов, иных программных средств, требующих непосредственного взаимодействия оператора системы с физическими лицами, информация о которых вносится в систему.

Литература

1. Wagner R.A., Fischer M.J. The string-to-string correction problem / Journal of the ACM, 1974. Vol. 21, № 1, pp. 168–173.

2. Smith T.F., Waterman M.S. Identification of common molecular subsequences / Journal of Molecular Biology, 1981. Vol. 147, pp. 195–197.

3. Дональд Э. Кнут. Искусство программирования. Т. 3. Сортировка и поиск. М.: Издат. дом «Вильямс», 2005. 824 с.

4. Каньковски П. «Как ваша фамилия», или Русский MetaPhone // Программист. 2002. № 8. С. 36–39.

5. Гешвинде Э., Шениг Г. Разработка Web-приложений на PHP и PostgreSQL. Руководство разработчика и администратора. СПб: ДиаСофтЮП, 2003. 608 с.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=2726&lang=&lang=&like=1
Версия для печати
Выпуск в формате PDF (5.09Мб)
Скачать обложку в формате PDF (1.32Мб)
Статья опубликована в выпуске журнала № 1 за 2011 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: