Как выбрать алгоритм для адресного фильтра

Довольно часто на Хабре появляются статьи с новыми алгоритмами автоматического разбора адресов, записанных одной строкой. Кроме этого, услуги по обработке адресов предоставляют различные it-компании. В статье мы расскажем как использовать свою адресную базу для выбора алгоритма автоматического разбора адресов, и на что стоит обратить внимание при тестировании и разработке алгоритмов адресных фильтров.

Эта статья для всех, кто хранит данные клиентов и хочет решить одну из следующих задач:

1. убедиться, что адрес существует, чтобы не отправить посылку или письмо в никуда;


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


3. дополнить адрес недостающей информацией, чтобы оптимизировать план работы курьеров;


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


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

Задача автоматического разбора почтовых адресов кажется довольно простой на первый взгляд — бери да сопоставляй адресному справочнику (например, ФИАСу) слова из входной строки. Но все, кто за неё берутся, утопают в большом количестве особенностей адресов…

Что мы знаем об адресах

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

В течение последнего года мы разрабатывали новую версию алгоритма (мы его называем адресным фильтром) с целью поставить точку в алгоритме разбора адресов.

Определяем задачу

Мы знаем три способа, как получить актуальные корректные адреса:

1. получить хороший адрес от клиента сразу (например, при помощи подсказок по адресам);


2. нанять операторов для ручного разбора адресов;


3. автоматически разобрать данные.

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

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

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

Мы рекомендуем использовать синтезированный вариант из 2-го и 3-го пунктов:

1. разобрать адреса автоматически с указанием показателя качества разбора адреса;


2. адреса с хорошим показателем качества — отправить в бизнес-процессы, а с плохим — отдать на разбор операторам.

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

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

Готовим адреса

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

Заблуждение первое: автоматически исправлять любые опечатки — хорошо

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

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

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

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

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

Таким образом, мы советуем проверять алгоритмы только на реальных данных без искусственных искажений. Например, если у вас в базе есть адрес Москва Пушкина 13, то и используйте его, а не Маск Пушикино 13.

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

Заблуждение второе: процент хорошо разобранных адресов — основной критерий выбора фильтра (кроме стоимости, конечно)

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

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

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

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

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

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

На какие адреса обратить внимание

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

• Адреса с опечатками или неправильным указанием компонента адреса (например, 3ая Мытищинская вместо 3-я Мытищинская).


• Неоднозначные адреса, для которых только по исходным данным нельзя однозначно определить, о чём идёт речь, в том числе при анализе оператором. Например, пропущенные или некорректно указанные компоненты адреса: Москва, Тверская может подразумевать как Тверскую площадь, так и улицу.


• Ошибку в указании типа адресного компонента. По нашим данным, около 5% адресов заказчиков содержат те или иные ошибки указания типа компонента адреса: вместо «посёлок городского типа» пишут «деревня», вместо «тупик» пишут «переулок» и так далее.


• Ошибку в указании самого компонента. Чаще всего неправильно указывают:
  
  
  
  • Район, в котором находится населённый пункт, если он находится на границе двух районов. Например, в адресе Московская область, Дмитровский район, пгт Запрудня некорректно указан район, правильно — Талдомский.
  
  
  • Регион, в котором находится объект. Особенно часто это встречается с адресами Москвы и Санкт-Петербурга, например:
    
    
    
    • Ленинградская область, Санкт-Петербург, Фонтанка
    
    
    • Московская область, Москва, ул. Расторгуева
    
    
    • Московская область, Зеленоград, к 3113
    
    
    
    
  
  
  
  


• Ошибку в имени, звании или другое распространённое заблуждение. Например, вместо улицы Алексея Толстого пишут Льва Толстого, или вместо маршала Жукова пишут генерала Жукова. Иногда также дают какое-то устаревшее или локальное, известное только местным жителям, наименование.


• Дублирование слов в исходной строке. Иногда после многих преобразований и переходов из системы в систему образуются адреса с дублирующими компонентами. Например, у одной конференции был адрес: Москва, Москва, Москва, Москва, Москва, Ленинградский проспект д. 39 стр. 79. Очевидно, что здесь слово Москва написано несколько раз по ошибке и алгоритм может не принимать во внимание дубли из исходного адреса. Но можно ли удалять дубли всегда? Другой пример: Сахалинская, Южно-Сахалинск, Сахалинская подразумевает адрес Сахалинская область, Южно-Сахалинск, Сахалинская улица. Хороший алгоритм должен находить дубли только если они являются действительно дублями и не уводить адрес в неправильный разбор.


• Мусор или дополнительную информацию в исходных данных. Обычно это либо ФИО, либо дополнительная информация про само здание и про то, как к нему пройти. Например: Иванов Иван, Пирогова 20 к 1 общ 8/1 ком 313, Новосибирск, НСО или Москва, Турчанинов, БЦ Крымский мост, дом 6 стр 2, 2 минуты от метро и хорошая зарплата . В таких случаях все компоненты входной строки, которые не являются адресными компонентами или часто встречаемой дополнительной адресной информацией (например, метро или районы города), должны быть вынесены на анализ оператору, так как могут влиять на качество разбора адреса.


• Устаревшие адреса. Это адреса, которые теперь другие: бывает, улицы переименовывают, бывает, что они переезжают в другой населённый пункт, объединяются и т.д. Когда есть два адреса: Самара 13 проезд и Самара Георгия Ратнера, то неплохо бы понимать, что это один и тот же адрес. Алгоритм должен уметь актуализировать адрес и ставить ему хороший код качества только в случае актуализации.

Сравниваем алгоритмы

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

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


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


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


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

Выводы

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

P.S.: В течение месяца мы установим новую версию адресного фильтра, про которую шла речь в начале статьи, на dadata.ru. Зарегистрируйтесь и подпишитесь на новости, чтобы оказаться в числе первых исследователей.

Спасибо chipQA за помощь при подготовке статьи.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.