Пример очистки данных

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

В общем, расскажу на примере одной недавней задачки.

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

Начинаем разбирать... Фантазия людей безгранична: вот возьмем к примеру Евросеть, как название только не напишут, могут как «ЕВРОСЕТЬ ЦЕНТР», или «ЕВРОСЕТЬ (ООО ЦЕНТР ХАБАРОВСК)». Ну с этим все более понятно, есть вхождение слова Евросеть и значит нашли магазин.

Следующий вариант это написание типа «Evroset». Сразу не найдем, тут нам надо сделать обратную транслитерацию. А есть, кстати, тот же DIXIS, для которого получается надо делать обратную операцию.

С учетом транслитерации и самих ошибок начинаются проблемы, потому люди пишут и как «Evroset», и как «Euroset», как «euroset.ru», да и в общем-то тоже самое для русского. К тому же бывают опечатки, или просто незнания правильного написания. «Техносила» может быть написана как «TECHNOSILA», или как «TEHNO SILA» (буковки C вообще нет), и т.д. А как вам «ЦИФРАГАД»(видимо не угодил он покупателю) и «ЦИФР0ГРАД» (Ноль вместо О, не иначе как кулхаксор писал), или «ЦЫФРАГРАТ» (ага, афтар жжет)?
Вывод такой: искать по вхождению не имеет смысла. Перебирать все варианты возможных ошибок, фантазий и пр. для каждого магазина просто нереально. Итого остается вариант искать по близости написания. Т.е. строка сравнивается по написанию со всеми магазинами, и берется тот, который наиболее похож. Естественно нужно еще найти какой-то минимальный порог, меньший 100% совпадения, но очень высокий, чтобы «ТЕХНОМИКС» не совпадал с «ТЕХНОМИР».

Сравнивать полную строку нет смысла, потому что чисто символьная разница между «СВЯЗНОЙ В ОКЕЕ НА МАРШАЛА ЖУКОВА», «СЕТЬ МАГАЗИНОВ САТЕЛЛИТ» и пр. далека от написания самого названия магазина. Из первой фразы надо сразу убирать адрес, но это просто, мы убираем все окончания начинающиеся на «на», «у», «ул», «в», «пр». Второй случай содержит часто употребимые слова, их можно выделить даже мельком пробежав все названия, хотя лучше с этим справился простенький скрипт. Но, так как даже после этого, во фразе все равно может остаться невыловленный нами мусор, надо сравнивать слова по отдельности, а не всю фразу.

Думаете стало находить? А фиг то там! Потому что если мы начнем таким образом сравнивать «EURO SET» и «BETA LINK», или, что еще хуже, «ЗАОБЕТА ЛИНК СПБ», то они станут непохожи, ведь из слова «BETA LINK», что «бета» что «линк» лишь наполовину похожи на «беталинк»... Поэтому надо сравнивать слова не только по одному, но и группами близлежащих, и к тому же не учитывая пробелы...

А еще надо учитывать чтобы из-за этой похожести «ДОМ.ТЕХНИКА» не совпал с «ДОМОТЕХНИКА» 🙂 Тут, на самом деле, начинается новая проблема. И если дальше копать, то выясняем что магазинов с элементами «техно/техника/техникс», «мир», «центр», «видео» и пр. просто немеряно 🙁 А ведь чем длиннее строка тем меньшую непохожесть вносит всего одна опечатка. Поэтому подобные элементы нужно сразу учитывать, чтобы не вносили погрешности. Но, опять же, тут надо учитывать что есть «М-ВИДЕО», который почти полностью состоит из одного из этих самых частоупотребимых элементов. Т.е. в данном случае нельзя отбрасывать эту часть, как мы делали с простым мусором (который упомянул выше, как например «СЕТЬ МАГАЗИНОВ»). Эти элементы надо сравнивать как обязательную и неотемлимую часть. И в тоже время требовать, чтобы ничего лишнего не было, т.е. «МИР ВИДЕО И АУДИО» это уже должно подпадать под мусор.

Да, и еще, насчет этих частоупотребымих элементов и мусора. Есть не только магазины, который в офлайне, но и интернет-магазины. А уж они то любят занять распространенное слово. И если на сайте telephone.ru продается достаточно товаров чтобы быть заметным, то нужно уметь его выделять. Вы думаете что его пишут как название сайта? Фиг то там! Он и сам себя именует как телефон.ру, и поэтому его пишут например как: «РОСТОВ.ТЕЛЕФОН.РУ» и так далее с учетом всех возможных опечаток. И выделяя его, нам ни в коем случае нельзя ошибиться и выделить «СОТОВЫЕ ТЕЛЕФОНЫ». Хотя в действительности для подобных сайтов не требует внесения каких-то особо уникальных вещей в алгоритм, но иметь ввиду это надо.

Ладно, это мы чуток разобрались с общеизвестными брендами, написание которых, чаще все же уникально. А ведь есть некоторые «псевдобренды», или не знаю как назвать. В общем, суть в том, что многим нашим предпринимателям лень думать над уникальным названием, и очень многие берут себе название типа «МИР», «МИР ТЕХНИКИ», «БЫТОВАЯ ТЕХНИКА», «ЭЛЕКТРОНИКА». И этих название просто куча в анкетах, и хотя клиент прекрасно понимает, что как таковой сети магазинов с таким именем нет в природе, но учитывать надо, из-за того, что слишком часто упоминается. И ведь приходится 🙂 И, с учетом всего вышенаписанного, «БЫТОВАЯ ТЕХНИКА» должна отличатся от «МИР БЫТОВОЙ ТЕХНИКИ», от «ВИДЕО И БЫТОВАЯ ТЕХНИКА», но совпадать с «БЫТОВАЯ ТЕХНИКА 4», «БЫТОВАЯ ТЕХНИКА МАГАЗИН №12 ЧП СОКОЛОВ С.И.», а «МИР» не должен совпасть с «АПЕЛЬСИНОВЫЙ МИР», «МИР ТЕХНИКИ», но совпадать с «МИР В ГИПЕРМАРКЕТЕ СЕМЬЯ» ну и т.д. Т.е. мусор если и может присутствовать, то только указывающий на месторасположение или тип.

Вот примерно такими вещами я сейчас и занимаюсь, если кому не лень тот может попробовать реализовать такой алгоритм, он не такой уж и сложный 🙂 Я привел на примере магазинов цифровой техники, но примерно также делается и для многих других вещей: для брендов, названий товаров, автомобилей и пр. что имеет конечный описанный объем названий. А вот когда требуется просто выделить что-то из фразы, к примеру адрес, то тут все гораздо хитрей.
А еще подумайте как вообще можно написать адрес, или телефон, и как же определить настоящие это данные или нет, и поверьте, фантазия людей похоже действительно не имеет границ.
А ведь мало написать выделение данных, нужно чтобы алгоритм сразу отбрасывал, как мусор, данные о человеке типа «Мери Попинс, ул. Ленина 1 кв. 1, тел. 123-12-34» 🙂

Если интересно, то еще немного можно почитать на OSP.RU: Фываяч и Микки Маус и Пылесосы в ассортименте

  • http:// Елена Холодова

    Игорь, я в восхищении 🙂

  • http:// Melnikoff

    Жжош. В тайне мечтаю о такой или похожей работе. Только вот она мне не приносила бы даже столько, сколько сейчас есть, не говоря уж о том, сколько мне надо... =(

  • http:// Александр Савченко

    А еще надо разработать такой алгоритм дня за два, максимум за три :). Да и работать он должен с производительностью порядка 100 записей в секунду.

    Так вот читаешь — жуть, однако что только люди не придумают.

  • http:// j2a

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

  • http:// igor

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

  • http:// SergINI

    Не знаю как в Москве, но в таком сравнительно маленьком городке как Новороссийск можно найти компании с абсолютно одинаковыми названиями. Например, Эльдорадо(в Новороссийске есть компьютерная фирма с таким же названием, что и известная сеть, при этом первая появилась значительно раньше) Такие задачи всегда назывались экспертными системами, и хорошо если такие программы «угадают» в 80% случаев. А собственно вопрос в другом: кто платит за такие системы?

  • http:// igor

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

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

  • http:// SergINI

    Можно и забить. Но один из наших бухгалтеров уже второй раз перечислил деньги другому Эльдорадо 🙂

  • http:// igor

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

  • http:// SergINI

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

    Может быть... Но я обычно сталкиваюсь с другими фирмами, для которых важно чтобы 100% данных было введено правильно!

    И для них лучше вручную и чтобы за это кто-то отвечал, чем 80%, которые никто не гарантирует.

  • http:// igor

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

    И в любом случае оператор чаще ошибается определаяя является ли S/N GY75K82014W серийным номером указанного здесь же в анкете телевизора, что в данным момент он уже был произведен и т.д.

    Определяя правильность адреса Крупской 14б он не узнает, что такого адреса в указанном городе не существует.

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

    И т.д. и т.д.

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

  • http:// aefimov

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

    Также можно применить вероятностное совпатение двух фонетических участков. Там буквы А и О примерно одинаковы по звучанию. Также П/Б и т.п.

    Некоторые звуки можно просто не учитывать — они могут быть «проглочены» в произношении и следовательно в написании.

    Т.е. получается трехмерная матрица — x — транскрипция символа, y — его вероятность быть не проглоченным, и z — его уникальность, т.е. непохожесть на другие символы по звучанию.

    Затем берем верную строку, переводим ее в такую форму, считаем ее «вес» и начинаем проверять распарсенные строки («взвешивать» в той же самой системе).

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

  • http:// igor

    Да, само сравнение строк сейчас примерно так и происходит. Но, как видишь, тут и помимо этого куча работы 🙂

  • http:// mdemm

    Оч. любопытно.

  • http:// Игорь

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

  • http:// igor

    Пока как-то до нейронных сетей не дошли, по крайней мере в этой задаче 🙂

  • http:// Дмитрий

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

  • http:// igor

    Точно! У меня что-то в голове покрутилось подобное сомнение по поводу нейронных сетей, но сформулировать не смог 🙂

  • http:// Игорь

    Это ограничение само собой присутствует. Просто из приведённых условий задачи не ясно, что заказчик хочет знать ПОЧЕМУ не прошла классификация.

    Заказчику бывает полезно предложить на выбор: либо 3-4 дня времени на создание и обучение нейронной сети, которая точно будет работать, но неизвестно каким образом, либо 3-4 недели написания и отладки синтаксического анализатора, который тоже скорее всего будет работать, но предсказуемо и понятно. Классический выбор между технологиями искусственного интеллекта и алгоритмическим подходом, между прочим 🙂

    P.S. Кстати, можно как-нибудь на Вашем сайте получать уведомления о новых комментариях по почте?

  • http:// igor

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

  • http:// Михаил Конинин

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

    Сильно я не замарачивался, пришел к следующему алгоритму:

    1) Вырезал орг.форму (ОАО, ООО, и т.п.)

    2) Удалял из строки все пробелы, тире, запятые и пр. незначимые символы. Для того чтобы поймать компании с различным написаниям: «Регистр А-Плюс» и «Регистр А Плюс»

    3) А потом тупо сопоставлял в Access по двум-трем полям:

    -Название,

    -Орг.форма,

    -Регион.

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

    А так как у меня в одной базе было только два информативных поля (название и регион), то если две компании с одинаковыми названиямии в регионе — я их никак не сопоставлял.

  • http:// иван

    Хэширование + конечные автоматы = решаемая задача

    MatLab для моделирования

  • http:// 0xdeadc0de

    Если названия длинные — то можно применить complearn.org

    Вообще очень красивая и универсальная технология.

    Но для коротких названий может не пойти.

  • http:// kmmbvnr

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

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

    Если введенное примерно хорошо попадает под несколько компаний — уходит на ручной разбор.

  • http:// igor

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