Задача об адресе. Машинное обучение

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

 

---

Содержание

1. Задача об Адресе. Предыдущая статья
2. Введение
3. Разделение строки адреса по реквизитам. Простейший способ
4. Пореквизитная разметка адресной строки
   1. Промежуточные выводы
5. Особенности стемминга и векторной модели адресных строк
6. Ранжирование результатов поиска адресных строк
7. Выделение признаков адресных строк
8. Ограничение тематики документов
9. Словарный запас адресных строк
10. О статистических признаках адресов
11. Слова, образующие контекст
12. О смысловом распознавании значений реквизитов
13. Пространственные методы решения задачи кластеризации
14. Заключение
15. Приложение. Пореквизитная разметка адресной строки (проект MarkingAddress)
    1. Головной модуль (main)
    2. Модуль подготовки адреса (PrepareAddresses)
    3. Модуль разделения адреса (SplitingAddresses)
    4. Модуль unit-тестирования (SplitingAddressTest)
    5. Архив проекта MarkingAddress в среде PyCharm 2022.1 (Community Edition)
16. Сноски
17. Литература

---

Введение

Святому Августину принадлежит высказывание, — «Что же такое время? Пока меня о том никто не спрашивает, я понимаю, нисколько не затрудняясь; но как скоро хочу дать ответ об этом, я становлюсь совершенно в тупик»[*¹] . В какой-то мере тоже самое может быть сказано об адресах. Особенно об адресах в строковой форме. Думаю, не просто найти взрослого гражданина нашей страны, который не имел преставления и не мог уверенно использовать адрес для почтовых отправлений и заказе товаров в интернет-магазинах. И эта простота использования создаёт уверенность в отсутствии проблем с адресами. Даже тогда, когда человек сталкивается со сложностями в регистрации собственности на своё имущество по причине того, что адрес его проживания не совпадает по форме с адресом, под которым значится его квартира в ЕГРН[*²], он всё равно рассматривает случившееся как частный случай и недоразумение.

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

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

Общая задача извлечения значений реквизитов (Общая задача). Задан документ D. Выделить в нём все адресные именованные сущности, отнести каждую сущность к одному реквизиту из множества {R1, R2, …, Rn}.

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

Задача извлечения значений реквизитов из НПА (Задача с НПА). В этой версии задачи документом D является нормативный правовой акт (НПА), присваивающий, изменяющий или аннулирующий адрес в муниципальном образовании.

Задача извлечения значений реквизитов из Адресной строки (Специальная задача). В этой версии задачи документ D содержит только строковый адрес.

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

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

Режим кластеризации. Задача решается в режиме кластеризации, когда заданное множества реквизитов неполно. Т.е. прежде чем некоторое значение может быть отнесено к реквизиту, он должен быть определён и добавлен в множество реквизитов.

К настоящему моменту известны следующие подходы к пониманию ИИ: символический ИИ и машинное обучение. Под символическим ИИ понимается создание правил (алгоритмов, программ), с помощью которых обрабатываются данные и получают ответы. Под машинным обучением понимается модель, когда люди вводят данные и ответы, соответствующие этим данным, а на выходе получают правила. Эти правила затем можно применить к новым данным для получения оригинальных ответов [1 стр. 27-28].

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

Разделение строки адреса по реквизитам. Простейший способ

Начнём с рассмотрения, пожалуй, самого простого алгоритма автоматического преобразования адресной строки к её пореквизитному аналогу. И для наглядности применим его следующему адресу в привычной форме — «Манский р-н, поселок Камарчага, ул. Черняка, д 7а». Как отмечалось выше простота алгоритма напрямую зависит от строгости ограничений, наложенных на форму адресной строки. Поэтому будем считать, что: 1) значения реквизитов адресной строки всегда разделены запятыми[*³] , и 2) адресу, неизвестным пока способом, поставлена в соответствие его структура (C-маркер по Хомскому [[2 стр. 25].), так чтобы порядковый номер значения однозначно определял реквизит.

Рис. 1. Результат разделения строкового адреса на реквизиты

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

• выделение из адресной строки частей, отделенных от прочих частей символом «запятая»;
• перенумерация выделенных частей в порядке их следования слева направо в адресной строке;
• приведение каждой выделенной части по её порядковому номеру в соответствие реквизиту.

Ниже приведены примеры алгоритмов, возвращающих эту таблицу разбора строки адреса на реквизиты на языках PYTHON и PL/pgSQL(PostgreSQL)

Рис. 1 демонстрирует не только результат применения данного алгоритма, но и его слабость.

Во-первых, пара элементов каждой подстроки разделяется друг от друга символом пробела. А значит, такой алгоритм перестанет возвращать правильный результат, если непосредственное значение реквизита состоит из двух и более слов, например, если адрес будет содержать подстроку — «ул. Александра Матросова».

Во-вторых, в различных реквизитах использован свой порядок следования типов и непосредственных значений: «Манский р-н», но «поселок Камарчага».

Одним из решений может быть ввод символа-разделителя между типами и непосредственным значением каждого реквизита. Например, «Манский \t р-н, поселок \t Камарчага, ул \t Черняка, д \t 7а»[*⁴] , где в качестве дополнительного разделителя использован символ табуляции. (Использование любого другого символа для этой цели будет столь же непривычным)

В качестве альтернативы можно принять единый порядок следования типа и непосредственного значения для всех подстрок реквизитов. Но какой порядок выбрать? «район Манский» или «Камарчага посёлок»?

Оба решения противоречат сложившейся практике написания адреса, поэтому приведут большому количеству ошибок при работе с ними.

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

Пореквизитная разметка[*⁵] адресной строки

Несколько слов о том, что такое разметка текста.

Разметка важный шаг подготовки текста перед включением как в отдельную в поисковую систему, так и в систему машинного обучения. Разметка предполагает разделение текста на фрагменты, а также классификацию их путём присвоения каждому фрагменту ярлыка или токена. Поэтому это процесс часто называется токенизацией [[1 стр. 209]. Наиболее распространенными вариантами токенизации являются «частеречная разметка» [[66 стр. 55], т.е. классификация слов текста по частям речи, и «распознавание именованных сущностей» [[66 стр. 178], таких как имена людей, географических названий и т.д. Пореквизитную разметку чаще относят ко второму варианту.

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

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

Таблица 1. Примеры семантических характеристик

Таблица 2. Примеры синтаксических характеристик

Таблица 3. Предполагаемые результаты пореквизитной разметки

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

Не слишком усложняет решение задачи то, что каждая метка реквизита имеет несколько значений:

• краткое и полное;
• множество синонимов [3].

Рис. 2. Структура типов реквизитов

Такая структура словарей типов реквизитов с одной стороны обеспечивает гибкость поиска меток в подстроке, с другой — устойчивость к изменениям формы написания метки. В чём можно убедиться, взглянув на пример, который содержит Таблица 4

Таблица 4. Несколько значений метки «микрорайон»

Актуальная метка краткая	Актуальная метка полная	Синоним 1	Синоним 2
МКР	МИКРОРАЙОН	М-Н	М-ОН

В общем случае алгоритм разметки в подстроке с одним значением произвольного реквизита состоит из следующих шагов: 1) поиск в подстроке одного из значений словаря, объединяющего актуальные метки и их синонимы; 2) извлечение из подстроки найденной метки; 3) преобразование найденной метки к актуальной форме; 4) остаток подстроки, из которой вырезана метка представить непосредственным значением реквизита.

Для полной адресной строки напрашивается способ последовательного применения поиска очередной метки реквизита, например, слева направо. При этом следует помнить о следующих ограничениях-предусловиях[*⁶] основного цикла:

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

В этом случае алгоритм пореквизитной разметки адресной строки может выглядеть как последовательность следующих шагов[*⁷] .

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

Таблица 5. Статистика типов населенных пунктов и улиц в Красноярском крае по состоянию на ноябрь 2015 года

Промежуточные выводы

Несмотря то, что алгоритм пореквизитной разметки представлен довольно подробно, тем не менее в нём не отражены существенные детали, которые могут повлиять на его эффективность и, даже, осуществимость. Поэтому создана программа на языке программирования python[*¹⁸]
, на основании выполнения которой и делаются выводы о возможностях рассматриваемого здесь подхода. Что, заметим мимоходом, соответствует идеям конструктивной логики [4], которая рассматривает алгоритм, как инструмент доказательства или опровержения гипотез. В данном случае речь идет о возможности отказа от использования разделителей между подстроками значений реквизитов с помощью алгоритма пореквизитной разметки.

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

Во-первых, необходимо уточнить способ поиска меток реквизитов, т.к. строка со значением типа одного реквизита часто является подстрокой типа другого реквизита, а также его непосредственного значения. Поэтому при поиске меток, в адресной строке тип реквизита следует «окружать» пробелами, знаками запятых и точек, а также признаками начала и окончания адресной строки. Для этого удобно использовать механизм регулярных выражений [5].

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

В-третьих, алгоритм пореквизитной разметки позволяет отказаться от разделителей между подстроками реквизитом, но только при условии, что все подстроки реквизитов сохраняют общий порядок. Или у всех реквизитов «тип» предшествует «значению», или «значение» предшествует «типу». Но не вперемешку, например, в адресной строке «Манский р-н д. Выезжий Лог Заречная ул. д.28 корп. 5 стр. 7» названия населённого пункта и улицы неразделимы. Т.е. алгоритм пореквизитной разметки, основанный на методе поиска типов реквизитов, корректно выполняется лишь ограниченном множестве форматов адресных строк.

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

Несмотря на слабую перспективу решения общей задачи преобразования адресной строки к набору реквизитов в рамках пореквизитной разметки, этот подход оказывается весьма полезным для решения различных вспомогательных задач. В первую очередь речь идет о задачах предварительного анализа и обработки адресных строк перед непосредственным преобразованием. В этом списке очень важную роль играет функция проверки исходной строки на принадлежность к соответствию предусловия к преобразованию. Это необходимо, для того, чтобы на ранней стадии отклонять строки, не содержащие значений реквизитов адресов, или, содержащие слишком широкое описание местоположение объекта, такое, например, как следующее — «расположенное в 28-30 км по лоцманской карте р. Енисей от устья р. Ангара до устья р. Подкаменная Тунгуска в Енисейском районе Красноярского края».

Особенности стемминга и векторной модели адресных строк

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

Рис. 3. Шаги подготовки адресной строки к включению в таблицу соответствия

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

При этом к каждой адресной строке, которая рассматривается как документ на естественном языке [6 стр. 367], содержащий неструктурированный текст, применяются обычные для лингвистического анализа операции: разделение адреса на слова (токенизация); преобразование слов в нижний регистр, формирование вектора лексем, путём отсечения от слов суффиксов и окончаний (стемминг), и т.д. Подробнее c методами NLP[*⁸], а также примерами их реализации на python, можно ознакомиться [1 стр. 210]. Здесь следует лишь обратить внимание на особенность обработки стоп-слов, проявляющуюся, например, в том, что «с» это не предлог, а сокращение о слова «село».

Для поиска в таблице соответствия используются запросы в форме адресной строки, которые предварительно преобразуются к набору лексем соединённых логической операцией «И» (&), как это показывает Рис. 4. При этом, каждая лексема в запросе понимается, как метке следующего суждения — «эта лексема присутствует (отсутствует) в списке лексем адреса». Таким образом запрос становится логическим предикатом, значение истинности которого определяется наличием или отсутствием записей в таблице, соответствующих этому предикату.

Рис. 4. Упрощённая схема поиска адреса по запросу

Рис. 5. Пример независимости результата поиска адреса от порядка адресных реквизитов в строке запроса. (Красным цветом здесь выделен подзапрос, не возвращающий адреса)

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

Процесс присвоения двоичного кода можно представить так, как будто каждая лексема является осью векторного пространства [6 стр. 85-89]. При этом каждой оси пространства присваивается уникальный порядковый номер. Порядок перенумерации осей неважен. Далее каждой оси ставится в соответствие битовая строка, состоящая из нулей во всех позициях, кроме той, что соответствует её порядковому номеру, которая устанавливается в единицу. Таким образом каждая адресная строка оказывается представимой битовой строкой, полученной в результате операции логического ИЛИ над битовыми строками лексем.

Очевидно, что длина битовых строк равна числу лексем-осей. Так, например, битовых строк для всех адресов Красноярского края может колебаться в пределах от 8800 до 9000 битов, и потому не слишком подходит для организации поиска. Но, как показывает Рис. 6, каждая в отдельности адресная строка содержит значительно меньшее количество лексем. И это не удивительно, ведь каждый адрес должен быть уникальным, а значит содержит идентифицирующий только его набор ключевых лексем.

Это свойство позволяем значительно сократить длины битовых кодов, т.к. ключевые лексемы различных адресных строк могут отображаться в одних и тех же позициях. Такой подход используется, например, в СУБД PostgreSQL, для создания индекса для полнотекстового поиска в виде RD-дерева. Подробности можно прочитать в книге Егора Рогова «PostgreSQL изнутри» [8 стр. 562-571].

Рис. 6. Количественные характеристики: максимальное, минимальное и среднее число лексем в одной адресной строке. С учётом наличия среди них синонимов

В том случае, когда запрос содержит достаточно полный набор лексем поиск известными средствами[*⁹] в основном приводит к релевантным результатам. Причиной тому является наличие ключевых лексем у каждой адресной строки, а также естественная близость их в составе вектора использования. Другое дело, когда запрос не полон, а значит содержит не все ключевые лексемы, и результатом является несколько адресных строк. В этом случае необходимо т.е. вычислять степень соответствия («близости») найденных адресных строк запросу. Другими словами, оценивать релевантность найденных адресных строк путём присвоения им числового значения — ранга.

Существующие методы вычисления ранга созданы из предположения поиска слов в произвольных документах, в которых обычно учитывается частота нахождения каждой лексемы в найденном документе, а также близость (proximity) и плотность (density) расположения в нём всех лексем запроса.

Ясно, что для адресных строк эти понятия имеют другой смысл. Так «Ачинский р-н, п. Ключи» и «Ачинский р-н, г. Ачинск» должны иметь одинаковый ранг, несмотря на то, что в последней подстроке лексема «Ачинск» повторяется дважды. Кроме того, близость и плотность лексем должны определяться не по расположению в строках запроса или адреса, а по отношению к естественному порядку реквизитов [9]. Действительно, вклад в ранг одной и той же лексемы «Ачинск» должен быть разным в зависимости от того относится ли она к реквизиту «район» или «населённый пункт». А под близостью двух лексем следует понимать соответствие их соседним реквизитам.

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

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

Рис. 7. Пример пореквизитной разметки лексем запроса

Устанавливать соответствие между лексемами запроса и реквизитами можно двумя способами — пореквизитным разбором строки запроса или сравнением её лексем с лексемами реквизитов адресной строки.

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

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

Специальный вектор сформирован из реквизитов найденной строки, а запрос не является расширенным, поэтому все лексемы запроса содержатся среди лексем адресной строки. А значит каждой лексеме запроса может быть поставлен в соответствие её порядковый номер в векторе адресной строки. Найденный порядковый номер в свою очередь укажет на реквизит, которому принадлежит лексема. Смотри Рис. 7.

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

где i — индекс найденной адресной строки, j — индекс ключевого реквизита, — показатель соответствия значений j-го реквизита в i-й адресной строки и запросе, B — максимальное значение ранга. Коэффициент B предназначен для того, что определять диапазон наиболее значимых найденных адресных строк, ранг которых принадлежит отрезку [1,B].

Ранг рассчитывает только по значениям отдельных реквизитов, называемых ключевыми. Так для поиска адресов в Красноярском крае, не имеет смысла упоминать его название в каждом запросе. Это позволяет использовать более компактные запросы для поиска.

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

где — значение j-го реквизита в запросе.

Рассмотрим пример расчета ранга на основе индикаторной функции. По полнотекстовому запросу «5, ул Ленина, Енисейск» средствами СУБД PostgreSQL находится три адреса и для каждого возвращается одно и то же значение ранга (функция ts_rank) равное 1. И при том, что запрашивается адрес в городе Енисейск, дополнительно находятся два адреса в городском посёлке Северо-Енисейский.

При расчете ранг обратного сравнения используется B=1.3, а также следующий набор ключевых реквизитов: «название района», «название населённого пункта», «тип улицы», «название улицы», «номер дома».

Таблица 6. Значения индикаторного ранга для адресных строк, найденных по запросу «5, ул Ленина, Енисейск»

Найденные Адреса	ts_rank PostgresSQL	Ранг индикаторный
Енисейский р-н, г. Енисейск, ул. Ленина, д.5	1,0	1,3
Северо-Енисейский р-н, пгт. Северо-Енисейский, ул. Ленина, д.5	1,0	0,0
Северо-Енисейский р-н, п. Новоерудинский, ул. Ленина, д.5	1,0	0,0

Причина того, что Таблица 6 содержит нули для второго и третьего найденного адреса заключается в том, что названия района «Северо-Енисейский» не совпадает с «Енисейский», одновременно не совпадают названия населённых пунктов «Северо-Енисейский» и «Новоерудинский» с «Енисейск». Эти несовпадения образуют сомножители равные нулю в результате чего равен нулю и общий ранг этих адресных строк.

Недостаток такого расчёта показателя в том, что с нулевым рангом, например, окажутся адресные строки, значения реквизита которых отличается от соответствующего реквизита запроса порядковым числительным, т.е. значения «ул. Садовая» и «ул. 1-я Садовая». Поэтому для этого показателя лучше использовать частное от деления длины значения реквизита запроса, на длину значения этого же реквизита адресной строки. Значение показателя в этом случае буде всегда меньше или равно 1, т.к. найденная строка обязана содержать значение, заданное в запросе.

Отношение длины строки «енисейск» к сумме длин «север» и «енисейск» равно 0,615385, а так как оно вычисляется дважды для названий района и населённого пункта, то Таблица 7 содержит произведение этих отношений, умноженное на коэффициент максимального значения ранга.

Таблица 7. Значения ранга с функцией отношения длин значений для адресных строк, найденных по запросу «5, ул Ленина, Енисейск»

Найденные Адреса	ts_rank PostgresSQL	Ранг отношением длин
Енисейский р-н, г. Енисейск, ул. Ленина, д.5	1,0	1,3000
Северо-Енисейский р-н, пгт. Северо-Енисейский, ул. Ленина, д.5	1,0	0,4923
Северо-Енисейский р-н, п. Новоерудинский, ул. Ленина, д.5	1,0	0,0000

Дополнительная гибкость в вычислении ранга найденной строки достигается благодаря исключению из значения адресных строк стоп-слов таких как, «имени», «Академика», «Космонавта» и т.д.

Выделение признаков адресных строк

Последнее время для работы с адресами всё чаще применяются алгоритмы машинного обучения на основе обработки естественного языка[*¹⁰] и распознавания именованных сущностей[*¹¹] , к которым, в частности, относят имена людей, названия географических объектов (топонимы), организаций, и т.д. А значит к именованным сущностям относятся названия адресообразующих элементов, образованные, в том числе, из подклассов топонимов[*¹²] , таких как ойконимов, урбанонимов, и т.п.

При этом машинное обучение на основе текстовых данных начинается с предварительного выделения признаков, которые затем должны быть отображены на вещественные векторы [11 стр. 77]. В добавок следует учитывать, что адресные строки не являются обычными предложениями, состоящими из взаимосвязанных частей речи. Во-вторых, ещё Джон Милль обратил внимание на то, что «собственное имя есть просто отметка, налагаемая на индивидуальный предмет и характеризующаяся тем, что у нее нет значения» [10 стр. 146].

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

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

Рис. 8. Схема взаимосвязи названий улиц и именованных сущностей

При этом следует учитывать, что значения части реквизитов, как адресообразующих элементов, часто представляют собой не самостоятельные имена, а, скорее ссылки на другие именованные сущности. Так Рисунок 8 содержит схему источников образования 69% названий улиц, из которых 27% ссылается на имена людей, 22% — к названиям организаций, 16% — к названия природных объектов и 3% на исторические события. Т.е. улицы называются по фамилиям знаменитых людей, по названиям организаций, рек, городов и т.д., которые в свою очередь являются именованными сущностями. При этом, в отличие от омонимов, совпадающих по форме, но отличных по значению, в предложениях «подвиг Александра Матросова» и «улица Александра Матросова» речь идет об одном и том же человеке. Другая часть значений реквизитов представляет собой широко используемые в языке прилагательные, например, «Центральная», «Новая», «Зелёная» и т.д. Такие названия характеризуются только синтаксическими и морфологическими признаками: написанием с заглавной буквы, родительным падежом и т.д.

В результате такой двусмысленности универсальный алгоритм распознавания именованных сущностей выполняется в условиях неопределённости, когда одно и тоже название улицы может быть классифицировано либо как имя человека (person, PER), либо как название организации (organization, ORG), либо как местоположение (locality, LOC). Более того, такие алгоритмы обычно не содержат достаточного количества меток для распознавания значений реквизитов.

Таблица 8. Некоторые результаты выполнения NER при помощи библиотеки spaCy с моделью «ru_core_news_sm»[*¹³]

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

Важнейшими признаками адресных реквизитов являются их типы, но на практике они часто опускаются. Тогда результат работы алгоритма может оказаться неожиданным. Так в стихотворении Владимира Высоцкого «Где твои семнадцать лет? На Большом Каретном» нет указания на тип — «переулок». А в строке «По улице моей который год» из стихотворения Беллы Ахмадулиной нет названия улицы. Поэтому хорошие результаты распознавания достигаются с помощью словарей, состоящих как из значений, так и из типов реквизитов. При этом использование дополнительных словарей сказывается на необходимости увеличения вычислительных мощностей.

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

• Ограничить тематику документов, например, списком адресных строк;
• Создавать специализированные программы для каждой заранее выбранной подкатегории именованных сущностей (Такой подход реализовал Александр Кукушкин в библиотеке Natasha[*¹⁴]);
• Распознавать именованные сущности вместе дополнительными словами, определяющими контекст части текста, в котором те и другие встретились.

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

Ограничение тематики документов

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

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

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

В случае адресной строки[*¹⁵] каждое слово является именованной сущностью, которое после применения алгоритма распознавания должно быть помечено признаком соответствия одному из реквизитов, а наличие непомеченных слов сигналом к совершенствованию алгоритма и редактированию словарей. При этом, большинство слов в НПА составляют лишь контекст, окружающий одну или несколько адресных строк, значения реквизитов которых расположены в нём не обязательно компактно.

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

Словарный запас адресных строк

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

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

Присутствие слова адресной строки в словаре реквизита является признаком существования. При этом словари реквизитов делятся на две группы: ключевые и различительные [9 стр. 78]. Ключевые словари используются для основных шагов распознавания названий в адресных строках, а различительные — на вспомогательном шаге, когда словарей ключевых реквизитов оказывается недостаточно. Таким образом, признак существования может дополниться указанием на группу реквизита.

Необходимым условием качественного распознавания адресных строк является поддержка словарей в актуальном состоянии, требующая своевременной реакции на изменения в адресах. И дело не только в естественной изменчивости, проявляющейся в результате присвоения, переименования и аннулирования адресов, но и в изменчивости адресов, порождённой законами Российской федерации, влияющими на порядок административной (муниципальной) подчинённости, а значит порядок следования значений реквизитов в адресе. Особым источником изменчивости в адресах широкое распространение новых поселений, не относящихся законодательно адресообразующим элементам[*¹⁶].

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

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

Рис. 9. Дом с несколькими адресами. Источники: Яндекс-карта и ГАР ФИАС

Наличие признака неполноты распознавания адресной строки создаёт необходимость подробного рассмотрения соответствия справочников реквизитов справочнику адресуемых объектов. Для этого введём вспомогательный признак адресной строки, который называется прямая мощность или мощность, т.е. количество объектов, соответствующих адресу. Этот признак для нормальных адресов должен равняться 1, когда адрес взаимно однозначно соответствует адресуемому объекту. Другие значения этого признака указывают на нарушения: так, значение 0 означает, что адрес не соответствует ни одному объекту, а значение n больше 1 означает, что существует n объектов с одним и тем же адресом. Альтернативным вспомогательным признаком является адресная мощность объекта или обратная мощность, т.е. количество адресов, указывающих на объект. Вычисление как прямой, так и обратной мощностей выполняется путём сравнения геометрии адресуемых объектов. В первом сравнении это объекты с общей геометрией, но одним адресом, во-втором — несколько адресов, указывающих на один или несколько объектов с совпадающей геометрией.

Последний случай инициирует соединение нескольких адресов в один, выделяющий одно актуальное значение, помечая все остальные его версии как синонимы[3 стр. 47-49]. Пример, дома в городе Красноярске, с адресом «улица Ленина дом 29» с координатами его центра MULTIPOINT(92.8811557286135 56.0138357515202) содержит Рис. 9. Как видно из приведённого примера, для выявления нарушений целостности можно либо организовать связь словарей с электронной картой объектов адресации, либо дополнить словари пространственными характеристиками.

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

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

О статистических признаках адресов

Предыдущий раздел завершился обозначением задач, которые относят к одной из категорий распределения по группам, в нашем случае, по реквизитам адреса [7 стр. 122]: классификации и кластеризации. При этом задача соотнесения неразмеченного значения с одним из списка заранее определённых реквизитов называют классификацией. Если же значение должно быть связано автоматически дополненным реквизитом, то такую задачу следует считать особым случаем кластеризации.

И тот и другой методы оперируют понятиями «векторное пространство», один или несколько характеристик объектов, значения которых представлены точками в этом пространстве, а также метрика – расстояние между точками пространства. Но, как уже отмечалось, адреса имеют свои особенности. Во-первых, характеристиками реквизитов являются только они сами, включая те, что составляют их префикс. Во-вторых, каждое значение реквизита представлено в адресе только один раз. Эти особенности очень ограничивает использование модели TF-IDF[*¹⁷] [6 стр. 88-89] для целей распределения элементов адресной строки по реквизитам.

Действительно, показатель TF-IDF — это дробь, в числителе (TF) которой число вхождений значения слова текущий документ, а знаменатель (DF) — общее число его вхождений во все документы. Для случая уникальных адресных строк TF всегда равен 1. Это справедливо даже в том случае, когда написание значений двух разных реквизитов совпадают. Например, так как адресной строке «Северо-Енисейский р-н, гп. Северо-Енисейский, ул. Ленина, 5», два значения «Северо-Енисейский» в которой следует рассматривать как омонимы. Как следствие, DF — число адресов, в которых реквизит имеет одно и тоже значение.

Как уже говорилось числовое векторное пространство адресов, строится так, что каждая его координатная ось соответствует паре реквизит-значение, а координата на такой оси вычисляется при помощи показателя TF-IDF.

Размерность такого пространства довольно велика. Так, например, размерность пространства значений адресов Красноярского края 34 000. Но часть задач можно решать на отображенном пространстве значений, размерность которого соответствует числу реквизитов.
Идея такого отображения состоит в том, что любой адрес содержит по одному значению для каждого реквизита, а это значит, что в векторе значений каждого адреса количество ненулевых координат ограничено числом реквизитов.
Обозначим векторное пространство значений адресов через VVa и определим новое векторное пространство реквизитов адресов VRa. Так как каждая ость пространства VVa соответствует паре «реквизит-значение», то возможно определить отображение fv, которое каждому вектору пространства VVa ставит в соответствие вектор пространства VRa, состоящий из ненулевых координат, но как что каждое значение оказывается на месте соответствующего реквизита.

Таким образом доказано следующее утверждение.

Лемма о векторном пространстве адресов. Адреса могут быть представлены векторами пространства VRa, где координаты, соответствует одному реквизиту, величина которых обратна числу адресов с его значением.

где — мера различия векторов; v(a₁), v₁ и v(a₂), v₂ —вектора, соответствующие адресам a₁ и a₂; c_1i и c_2i — i-е координаты этих векторов.

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

Утверждение о коллинеарности префиксов. Т.к. мера различия векторов — это косинус угла между ними, то векторы общих префиксов адресов [9 стр. 68] являются коллинеарными.

Таблица 9 содержит пример, демонстрирующий ограниченность использования векторной модели TF-IDF для случая адресов. Причина этого в формальном подходе к вычислению координат, что приводит случайным и интуитивно не убедительным совпадениям векторов. Действительно, факты совпадения векторов для адресов с номерами домов «21Б» и «19Б» на одной улице, а также «отдалённость» домов «21» и «21А» свидетельствуют скорее о неприменимости этой модели к документам, состоящим только из строк адресов.

Для разрешения противоречия между интуитивным взглядом на близость адресов и их векторных представлений необходимо, чтобы на значениях каждого реквизита было определено отношение порядка, которое бы сохранялось в соответствующих координатах векторного представления. Ни порядка на множестве имен, представляющих собой значения большинства реквизитов, ни расстояния между ними определить нельзя. Причина в том, что имена не имеют характеристик, которые позволяли бы их сравнивать. При этом, речь не идет о текстовом представлении имен или частоте их присутствия в хранилище. И в том и в другом случае попытки сравнения адресов будут приводить к коллизиям.
Особняком стоит реквизит с номерами домов, корпусов, строений. Любому значению номера дома можно поставить в соответствие число, как показывает Рис. 10.

Рис. 10. Принципиальная схема преобразования номера дома в число

Главная идея такого преобразования состоит в том, чтобы номеру дома сопоставить целую часть результирующего числа, дробную часть использовать для представления букв в номера дома, а также номеров корпуса и строения. Для этого, если считать N цифровой частью номера дома, то отрезок (N, N+1) делится на три части. При этом буква представляется числом 0,3*n_l/N_A), где n_l – порядковый номер буквы в алфавите A, а N_A — число букв в алфавите. Вторая и третья часть отрезка предназначена для отображения номера корпуса и строения соответственно, преобразование номеров которых выполняется не на много сложение, чем это показано для буквы. Так, например, значение «д. 2» преобразуется в число 2, «д. 2а» преобразуется в число 2,200909, а «д. 2а корп. 1» —2,30939. Это при условии, что величина номера корпуса ограничена числом 1000.

Применимость модели TF-IDF к адресным строкам не исчерпывается решением задач классификации и кластеризации. Так, адресная строка оказывается не уникальной, когда при фиксированном контексте числитель TF оказывается больше 1. Т.к. значение показателя TF-IDF может использоваться как триггер процедур поиска и даже создания нового реквизита.

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

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

Слова, образующие контекст

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

С другой стороны, в поисковых запросах на первом месте по значимости оказываются именно названия районов, населённых пунктов, улиц и номера домов благодаря их высокой степени влияния на релевантность ответов. Так, например, запрос «Ленина 143» в Красноярске, несмотря на отсутствие в нем явного указания типов реквизитов, позволит найти адрес «город Красноярск, улица Ленина, дом 143». Т.е. и значения реквизитов следует считать ключевыми словами второго уровня после их типов.

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

Из приведённых рассуждений следуют два вывода:

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

Дополнительно, когда исходными документами являются нормативные правовые и информационно-справочные акты, контекст могут составлять слова, описывающие их характеристики. Например, в Красноярске адреса утверждаются распоряжениями администрации города, номер которых содержит суффикс «-недв», а тема содержит текст «о присвоении адресов объектам адресации».

О смысловом распознавании значений реквизитов

Поиск значений реквизитов в соответствующем словаре является удобным методом для решения многих задач. Но что делать, когда такой поиск завершается неудачей? В этом случае пытаются искать близкие по написанию значения, в надежде, что неудача стала следствием синтаксической ошибки в запросе или словаре. При этом, «близость» слов определяется редакционным расстоянием, т.е. количеством операций редактирования, необходимых для превращения одной строки в другую. Обычно это расстояния Левенштейна или Дамерау-Левенштейна. Последнее добавляет к первому операцию перестановки соседних букв [6 стр. 144-151]. Величина редакционного расстояния, на первый взгляд, представляется удобным признаком синонима реквизита, который должен быть добавлен в словарь.

Рис. 11. Пример улиц, редакционное расстояние от которых меньше или равно 2

Как показывает Рис. 11, редакционное расстояние слишком универсальная мера для того, чтобы использовать его для автоматического создания синонимов. Например, расстояние между названиями улиц «Луговая» и «Логовая» («Дуговая») равняется 1, при этом вряд ли без дополнительной информации признать их синонимами.

Дополнительными признаками новых значений могут служить:

• Значение начинается с заглавной буквы;
• Значение реквизита в адресной строке находятся справа или слева от его типа;
• Название улицы является прилагательным, например, «Зелёная», «Центральная» и т.д.;
• Название улицы является существительным в родительном падеже, например, «Александра Матросова», «Академика Киренского», и т.д.

В общем случае, такие правила относятся к группам: «сравнение с помощью n-грамм» [6 стр.158], «частеречная разметка» [6 стр.55] и, конечно, «идентификация сущностей» или «распознаванием именованных сущностей» [6 стр.178]. При этом, практическое применение этих правил зависит от происхождения названий реквизитов, которое разделяет их на классы.

Здесь же делается попытка анализа возможности распознавания неизвестных значений реквизитов, используя их генезис (источники происхождения) на примере улиц.

Ранее уже упоминалось, что названия улиц можно разделить на классы по признаку их происхождения. Так, Рис. 12 демонстрирует диаграмму распределения неповторяющихся названий улиц красноярского края. Здесь под объектами, расположенными на улицах понимаются магазины, школы, предприятия и т.д. К улицам, попадающим в класс «Особенности расположения на территории населённого пункта» относятся, например, улицы: Центральная, Северная, Восточная, и т.д. К названиям по ассоциативному восприятию отнесены, например, улицы Весёлая, Зелёная, Раздольная, Тенистая и т.д.

Как показывает Рис. 12. Диаграмма распределения названий улиц Красноярского края по классам источников

Такое распределение источников названий улиц по классам позволяет создавать специализированные функции распознавания. Так, названия улиц в честь знаменитых людей именам собственным может предшествовать дополнительное слово «имени», а также слова, указывающие на их статус. Например, в Красноярске есть «сквер имени Сурикова», «улица Академика Киренского», в Минусинске — «улица Маршала Жукова» и т.д.

Объекты, расположенные на улице, отражаются в её названии видом деятельности и даже непосредственным наименованием: «Заводская», «Почтовая», «Вокзальная», «Совхозная», «Клубная», «Сад Крутовского», «Шилинский Дом-интернат».

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

Пространственные методы решения задачи кластеризации

Отсутствие признаков адресов и адресообразующих элементов привело к мысли о необходимости сознания для них искусственных признаков, наилучшими из которых являются пространственные признаки. Главным преимуществом последних является их измеримость, а недостатком — необходимость прогнозирования (или указания вручную) значений пространственных признаков для новых адресов.

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

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

Для рассматриваемых в этой статье задач особый интерес представляет признак — количество точек-адресов в пространстве реквизита (для линии — это число адресов в прилегающих гранях). Этот подход позволяет переформулировать, введённые ранее понятия прямой и обратной мощности. Так прямая мощность адреса — это соответствующее ему число точек с одинаковыми координатами, а обратная мощность точки — число связанных с ней различных адресов.

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

В этих условиях существует простое решение для адресов с признаком неполноты словаря реквизита.

Утверждение о синониме реквизита. Пусть в адресной строке w — нераспознанное слово (набор слов) обладает пространственной характеристикой g(w). Пусть также r — значение одного из реквизитов R чья пространственная характеристика g(r) совпадает с g(w). Тогда w синоним r. Более того, каждый адрес, содержащий значение w для реквизита R, является синонимом этого же адреса, если в нём w заменено на r.

Утверждение о дополнительном значении реквизита. Пусть в адресной строке w — нераспознанное слово (набор слов) обладает пространственной характеристикой g(w). Пусть также существует реквизит R, пространственная характеристика родителя которого содержит g(w). Тогда w дополнительное значение реквизита R.

Утверждение о неполноте множества реквизитов. Пусть a₁ и a₂ — совпадающие адресные строки. Пусть также существует порядковый номер i такой, что значения реквизита с этим номером r_i(a₁) и r_i(a₂) совпадают r_i(a₁)=r_i(a₂), а пространственные характеристики нет, т.е. g(r_i(a₁))≠g(r_i(a₂)). Более того, не существует ни одной другой адресной строки, у которой пространственные характеристики i-го реквизита совпадают либо с a₁, либо с a₂, т.е. g(r_i(a)) ≠g(r_i(a₁)) ∧ g(r_i(a)) ≠g(r_i(a₂)). В этом случае будем говорить о признаке возможной неполноты множества реквизитов.

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

Рис. 13. Преобразование адреса с мощностью большей 1 (слева) в несколько адресов с различными пространственными характеристиками и различение этих адресов с помощью значений дополнительного реквизита (справа)

Рис. 13 иллюстрирует основной метод разделения адресов с мощностью большей 1 при помощи поиска подходящих значений в одном из заранее подготовленных различающих реквизитов [9 стр. 78]. При этом, различающий реквизит характеризуется следующим свойством.

О различающем реквизите. Реквизит, различающий адрес a с мощностью p(a)=n, где n>1, должен обладать не менее чем n-1 различающих значений.

Действительно, пусть существует адрес a с мощностью p(a)=2, тогда различающий реквизит должен иметь значение r_d такое, что a₁ ∈ r_d ∧ a₂∉ r_d или наоборот. Следовательно, когда мощность адреса p(a)=n, то дополнительный реквизит должен обладать не менее чем n-1 различающим значением.

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

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

<

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

Заключение

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

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

Во-первых, корпус адресных данных слишком изменчив, поэтому основанную на нём модель необходимо постоянно переобучать. Причем изменчивость адресов спонтанна, т.к. порождается новыми нормативно-правовыми актами, принятыми законодательной или исполнительной властью. Альберту Энштейну, кажется, принадлежит высказывание «Господь Бог изощрен, но не злонамерен». Требование «незлонамеренности» является обязательным условием качества данных, на которых обучается любая нейросеть. Иначе её переобучение станет постоянным, а её применение окажется слишком затратным.

Во-вторых, для моделей на основе документов наиболее распространен подход назначения весов с использованием показателя TF-IDF (term frequency-inverse document frequency – частота термов-обратная частота документа). В случае, когда в качестве документа рассматривается адрес, число различных термов (значений реквизитов) стремится к 1, поэтому этот показатель теряет свою значимость для построения меры отличия адресов.

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

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

Смотри также:

1. Эх, ФИАС, ФИАС… Почему ты не адресный реестр?
2. Эх, ФИАС… Восемь лет спустя
3. Ах! 2ГИС. Ох! 2ГИС
4. Анализ адресов ФИАС
5. Адреса ФИАС в среде PostgreSQL
6. Дома ФИАС в среде PostgreSQL
7. Зачем Красноярску адресный реестр?
8. Цена беспорядка в адресах

 

ПРИЛОЖЕНИЕ. Пореквизитная разметка адресной строки (проект MarkingAddress)

В приложении приведены тексты программы «Пореквизитная разметка адресной строки», результаты выполнения которой используются в тексте статьи. Упоминание о ней находится здесь. Модули объединены в проект MarkingAddress, разработанный и проверенный в среде PyCharm 2022.1 (Community Edition)

Головной модуль main

Модуль подготовки адреса PrepareAddresses

Модуль разделения адреса SplitingAddresses

Модуль Unit-тестов SplitingAddressTest

Архив проекта MarkingAddress

скачать архив проекта MarkingAddress.

 

Сноски

[*¹] Августин Аврелий. Исповедь / пер. с лат. М. Сергеенко. — СПб. : Азбука, Азбука-Аттикус, 2023. — 400 с. — (Азбука-классика). XIV Книга одиннадцатая, стр. 294.

[*²] ЕГРН — Единый Государственный Реестр Недвижимости.

[*³] Запятая, как символ-разделитель реквизитов адресной строки указана здесь лишь для наглядности, т.к. в этом качестве могут использоваться и другие символы, в том числе управляющие, такие как символ табуляции (\t), конец строки (\n), перевод каретки (\r) и т.д.

[*⁴]\t — так обозначается символ табуляции (Tab) в языке программирования Python.

[*⁵]Разметка важный шаг подготовки текста перед включением как в отдельную в поисковую систему, так и в систему машинного обучения. Разметка предполагает разделение текста на фрагменты, а также классификацию их путём присвоения каждому фрагменту ярлыка или токена. Поэтому это процесс часто называется токенизацией [7 стр. 209]. Наиболее распространенными вариантами токенизации являются «частеречная разметка» [6 стр. 55], т.е. классификация слов текста по частям речи, и «распознавание именованных сущностей» [6 стр. 178], таких как имена людей, географических названий и т.д. Пореквизитную разметку чаще относят ко второму варианту.

[*⁶]Понятие предусловия цикла введено Эдсгером Дейкстрой в его книге «Дисциплина программирования»[13]

[*⁷]# — признак следующего за ним комментария

[*⁸]NLP (Natural Language Processing) — обработка естественного языка, область искусственного интеллекта, которая фокусируется на взаимодействии между компьютерами и людьми с помощью естественного языка.

[*⁹]Например, средства полнотекстового поиска в СУБД PostgreSQL.

[*¹⁰]Natural Language Processing (NLP)

[*¹¹]Named Entity Recognition (NER)

[*¹²]Подольская Н. В. Словарь русской ономастической терминологии / Отв. ред. А. В. Суперанская; Институт языкознания АН СССР. — М.: Наука, 1978. — 200 с. — 35 700 экз.

[*¹³]Здесь \t заменяет знак табуляции

[*¹⁴]Александр Кукушкин(alexanderkuk) Yargy-парсер и библиотека Natasha. Извлечения структурированной информации из текстов на русском языке и Проект Natasha. Набор качественных открытых инструментов для обработки естественного русского языка (NLP).

[*¹⁵]Здесь уместно напомнить о том, что адресная строка не содержит стоп-слов.

[*¹⁶]Например, СНТ (ОНТ) садовые (огороднические) некоммерческие товарищества .

[*¹⁷]Term Frequency-Inverse Document Frequency – частота термов-обратная частота документа.

[*¹⁸]Проект MarkingAddress Пореквизитная разметка адресной строки.

Литература

1. Шолле Франсуа Глубокое обучение на Python. Пер. с англ. А. Киселева. — СПб.: Питер, 2018. — 400 с.: ил. — (Серия «Библиотека программиста»).
2. Хомский Н., Миллер Дж. Введение в формальный анализ естественных языков. Изд.3 Либроком 2010 г. 66с.
3. Гладков С.Л. Нормализация адреса // Журнал «Информатизация и связь». – 2018. №5. – С. 46 – 50.
4. Марков А. А. О логике конструктивной математики// Избранные труды. ред.-сост. Н. М. Нагорный. Том II Теория алгоритмов и конструктивная математика, математическая логика. информатика и смежные вопросы – М.: Изд-во МЦНМО,. — 2003. – С. 328-356
5. Фридл Дж. Регулярные выражения. 3-е изд. — СПб.: Питер, 2018. — 608 с.: ил. — (Серия «Бестселлеры O’Reilly»).
6. Ингерсолл Грант С., Мортон Томас С., Фэррис Эндрю Л., Обработка неструктурированных текстов. Поиск, организация и манипулирование. / Пер. с англ. Слинкин А.А. – М.: ДМК Пресс, 2015. – 414 с.: ил.
7. Бринк Хенрик, Ричардс Джозеф, Феверолф Марк. Машинное обучение. Пер. с англ. И. Рузмайкиной.-СПб.: Питер, 201 7. -336 с.: и л. -(Серия «Библиотека программиста»).
8. Рогов Е. В. PostgreSQL 17 изнутри. — М.: ДМК Пресс, 2025. — 668 с.
9. Гладков С.Л. ЗАДАЧА ПРИВЕДЕНИЯ ПОРЕКВИЗИТНОГО АДРЕСА К СТРОКОВОЙ ФОРМЕ. //Образовательные ресурсы и технологии. – 2024. – № 2 (47). – С. 65-81. doi: 0.21777/2500-2112-2024-2-65-81
10. Милль Джон Стюарт, Система логики силлогистической и индуктивной: Изложение принципов доказательства в связи с методами научного исследования. Пер. с англ. под редакцией В. Н. Ивановского/Предисл. и прил. В. К. Финна. Изд. 5-е, испр. и доп. — М.: ЛЕНАНД, 2011. — 832 с. (Из наследия мировой философской мысли: логика.)
11. Гольдберг Й. Нейросетевые методы в обработке естественного языка / пер. с анг. А. А. Слинкина. – М.: ДМК Пресс, 2019. – 282 с.: ил.
12. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. — М.: Мир, 1989. — 478 с.
13. Дейкстра Э. Дисциплина программирования. М: Мир, 1978.
14. Хобсон Лейн, Ханнес Хапке, Коул Ховард, Обработка естественного языка в действии. / Пер. с англ. И. Пальти, С. Черников — СПб.: Питер, 2020. — 576 с.: ил. — (Серия «Для профессионалов»).