Работаем с почтовыми адресами и их качеством. Как правильно

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

В чем проблема?

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

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

Здесь уместно говорить о качестве адресной информации. Применительно к адресам понятие «качество» можно определить как достоверный ответ на вопрос «какова вероятность того, что попытка физического прибытия в соответствии с данным адресом будет успешной без дополнительных уточнений?». Если 100% — это качественная адресная информация. Меньше – хуже. И так вплоть до худшего варианта «нулевого» качества, это когда адрес как-бы есть, а вот соответствующего ему физического объекта и вовсе не существует.

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

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

%d1%88%d0%b0%d1%80%d0%b8%d0%ba%d0%be%d0%b2-%d0%b0%d0%b4%d1%80%d0%b5%d1%81%d0%b0

Теперь давайте представим, что мы более-менее точно знаем каково качество этой адресной информации. Мы знаем, что 82 адресам точно соответствуют физические объекты. А из оставшихся 12 неоднозначны, а 6 вообще, похоже, не существуют. В этом случае мы можем принять превентивные меры, например, заранее прозвонить получателей через колл-центр и уточнить адреса, не отвлекая для этого экспедитора от маршрута, доведя количество «уверенных» адресов в маршрутном листе до 100% еще до выезда. Если учесть, что проверка этих 100 адресов по сложившимся на рынке ценам сервисов валидации будет стоить меньше одного рубля, — согласитесь, соотношение расходов к экономии здесь превосходное.

Резюме: При работе с почтовыми адресами главная цель – получить «уверенный» адрес, а так же иметь понятную оценку его качества. Для достижения ее необходимо решить задачу проверки («валидации») адреса.

Откуда взять уверенность?

Решить задачу валидации можно одним единственным способом – распознанием адреса и его последующей проверкой по эталонному справочнику, который в идеале должен включать в себя все адресуемые в принципе объекты. Этот способ является единственно применимым, поскольку никакие проверки без обращения к справочнику тут не дают нужного результата. «123456, Когалым, ул. Синих Финтифлюшек д. 1345 кв А» — по структуре и логике является совершенно нормальным адресом. Но едва ли туда дойдет отправленный груз.

Таким образом, любой сервис валидации адресов делает три простых шага:

  1. Распознает и квантифицирует адрес.
  2. Находит его в эталонной базе
  3. Корректирует и дополняет его в соответствии с эталонной базой и оценивает степень соответствия ей.

Однако, просты эти шаги только на первый взгляд. До сих пор находятся товарищи, которые действуют по схеме «берем КЛАДР, пишем парсер адресной строки на регулярных выражениях, а дальше же совсем все просто, поиск по таблицам, любой студент за две недели справится».

Полиграф Полиграфович о валидации

У нас целая коллекция таких подходов накопилась, спешим поделиться результатом: такая система после длительной доработки напильником успешно валидирует где-то 60, максимум 65% адресов из тех практических потоков, что встречаются, к примеру, у курьерских и почтовых служб. Безусловно, это лучше, чем ничего, но в том-то и проблема, что из оставшихся 35…40% большинство адресов «невалидны» не потому, что они не существуют, а лишь потому, что в них есть мелкие неточности, опечатки, сокращения и так далее! Зиленая улица, город Мсква.

Польза от такой валидации сомнительна, поскольку мы с точки зрения бизнеса ситуацию не улучшили, а ухудшили. Раньше у нас экспедитор отвлекался на 18% адресов и приезжал «не туда» в 6% случаев, то теперь у нас на 35..40% адресов задействованы операторы для уточнения. Явно не тот бизнес-результат, который хотелось бы получить!

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

Основным источником ошибок является, конечно же, человек. А именно:

  1. Безграмотность, невнимательность, элементарная усталость. Очепятки и орфографические ошибки в первую очередь дают искажения, которые мешают компьютерам с их формальной логикой сравнивать с эталоном. Мы при чтении легко и незаметно компенсируем это, компьютеру это сделать намного сложнее.
  2. Ориентация не человека же, который будет читать. Из этого принцип «понятности человеку», сокращения, пропуски «незначительных» с точки зрения человека элементов. Человек спокойно пишет «мск, вернадского 23-1, 112» — и для человека же здесь все понятно.
  3. Неоднозначность топонимики, зачастую неизвестная оператору. Так, респондент спокойно пишет «Мск, Фрунзенская 45», имея ввиду Фрунзенскую набережную и просто не зная, что в Москве есть еще три «номерных» Фрунзенских улицы.

И все эти факторы, вдобавок, накладываются друг на друга.

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

  1. Уметь максимально корректно распознавать части адреса во всех встречающихся комбинациях расположения и порядка следования адресных элементов.
  2. Сравнивать с эталоном не строго, а с учетом возможных опечаток и ошибок.
  3. Сравнивать с эталоном не по элементам, а с учетом всех известных частей адреса.
  4. Четко оценивать «достаточность информации» для точного определения соответствия эталону.
  5. Никогда не «додумывать за клиента». То есть никогда не выдавать «самый похожий», если есть множество вариантов эталона, каждый из которых в принципе похож.

Из этого следует, что качество сервиса определяется следующими факторами:

  1. Насколько хорош его эталонный справочник? Если справочник слабый и неполный – то и сервис хорошо работать не будет. Если справочник содержит много ошибок – то и результат будет содержать именно эти ошибки.
  2. Насколько хороши его алгоритмы «разбора» адреса и поиска его в эталонном справочнике? Мы намеренно не отделяем разбор и поиск, ибо считаем, что это очень сильно связанные вещи. Нельзя хорошо разобрать адресную строку не обращаясь к справочникам для подтверждения смысла отдельных элементов.
  3. Насколько хороши и адекватны его алгоритмы оценки качества полученного результата? Ведь как только мы начинаем «нестрогий» поиск мы сталкиваемся с тем, что тот или иной результат мы получаем всегда. В конце концов слово «хлеб» — это всего лишь слово «пиво» с четырьмя ошибками.

В итоге, хороший сервис должен с высокой надежностью давать один из трех базовых ответов:

  1. Да, узнал, проверил, уверен!
  2. Нет, что узнал, проверил, нет такого объекта!
  3. Есть варианты! Узнаю более одного адресного объекта, решать не берусь.

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

Когда сервис «додумывает за человека», он вместо «есть варианты» возвращает «Узнал!», но возвращает он зачастую вовсе не то, что имел ввиду автор адреса. По формальному критерию «процент разобранных адресов» он будет иметь выдающиеся характеристики. Но беда в том, что в итоге мы получаем т.н. «обратную ошибку», ложно распознанные адреса или самостоятельно выбранные сервисом варианты – и наш экспедитор едет не туда. А это плохо.

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

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

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

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

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

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

Ключ к качеству – в алгоритмах

Из вышесказанного следует, что ключевых факторов в таком сервисе два: эталонный справочник и алгоритмы.

Про эталонные справочники мы говорить сейчас не будем по одной причине: у нас все равно не на что опереться, кроме ФИАС/КЛАДР. Эта проблематика достойна отдельной стати, наполненной гневом и претензиями в адрес ответственных за эти фундаментальные, для всей экономики важные опорные данные. Скажем только, что нам приходится прилагать огромные усилия по «дочистке» этих справочников от весьма банальных ошибок и неточностей. Пока же мы просто будем полагать, что для решения этой задачи все, кто за нее берутся с точки зрения эталонной базы находятся в более-менее равном положении.

Поэтому мы сконцентрируемся на алгоритмах. Из которых ключевыми являются алгоритмы сравнения.

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

Существует множество популярных алгоритмов «приблизительного поиска и оценки похожести», например, самые популярные – расстояние Левенштейна, или использование N-грамм. Однако есть одна проблема: в нашем конкретном случае «похожесть» не дает ответа на «нашли ли мы то, что искали». Например, 1-я, 2-я и 3-я Фрунзенские похожи на 93%, ровно так же как на 93% похожи «1-я Фрунзенская» и «1-я Франзенская». При этом чтобы выбрать из трех номерных улиц нам надо точно знать номер, а для того, чтобы уверенно компенсировать опечатку во втором случае – достаточно знать, что «франзенская» не значится в эталонном справочнике.  В общем, принцип «релевантности» как его понимают поисковые системы, т.е. «максимальной похожести» здесь, увы, не работает.

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

Таким образом, задача «признания идентичности» и задача «оценки похожести» — это все же разные задачи. И применительно к адресам говорить, что «идентичные – это похожие на ХХ%» — никак нельзя!

Надо заметить, что обычно адресная база хранится в СУБД, а СУБД в принципе не умеет искать «приблизительно». Максимуму – по маске. Поэтому попытка «поискать по Левенштейну» по базе в несколько миллионов записей – это серьезная проблема, потому что нужно для каждой пары отработать довольно сложный алгоритм сравнения. Ресурсоемкость получается чудовищная, а производительность построенной таким образом системы – весьма небольшая.

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

Теоретически это должно прекрасно работать. И оно даже в принципе работает, нам такие реализации известны. Но есть нюанс: база, в которой надо искать, растет как на дрожжах. Число вариантных хэш-записей в ней может в десятки раз превышать число исходных. Больше места, дольше поиск. Но и это еще не вся печаль.

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

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

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

Но по факту такая система не учитывает ни логику языка, ни семантику, неспособна работать с «неизвестными» отклонениями. И когда мы берем реальный поток адресных строк, как их вводят люди – то обычно мы получаем 70..80% распознавания, что, безусловно больше, чем дает просто «поиск по базе», но все же недостаточно хорошо. При этом это будет процент не от адресов вообще, а от адресов, которые смог бы разобрать человек.

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

Как это делаем мы

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

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

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

В-третьих, мы используем словари синонимов, но огромная разница в том, что для нас это именно синонимы, а не словоформы или варианты написания. Образно, синонимом Санкт-Петербурга является Ленинград, но это и все, все остальное словообразование, опечатки, анализ – в алгоритмах, и автоматом применяется ко всем синонимам точно так же, как к «эталонным» названиям.

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

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

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

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

Результаты такого подхода – это отработка адреса, максимально близкая к распознаванию его «человеком с эталонной базой в голове». На практических потоках мы распознаем более 90% адресов, причем, заметим, что это процент от всего потока. Фактически весь остаток – это адреса, требующие не столько распознания, сколько уточнения, ибо просто не несут в себе достаточной информации. Мы не можем полностью гарантировать отсутствие «обратной ошибки» или «ложного узнавания», но число таких ошибок пренебрежительно мало и составляет единицы на миллионы обработанных адресов.

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

Все описанные технологии — реализованы в продукте IQ Data Quality Server и сервисе iqdq.ru.

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

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

Share