Алгоритмы поиска и обработки естественного языка (Natural Language Processing, NLP) давно являются сферой моих научных хобби/интересов. Кое-кто даже знает, что я пишу магистерскую диссертацию по теме семантического поиска. К счастью или сожалению эта сфера настолько огромна и закрыта, что информацию приходится собирать долго, по крупицам, в большинстве случаев мучительно выдумывая свои подходы, тестируя и участь в основном на своих ошибках. Благодаря интернету в современном мире можно легко найти информацию практически по любым сферам интересов, особенно в программировании, практически любые методологии разработки тех или иных систем описаны вдоль и поперек.

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

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

В алгоритмах NLP всё по-другому по двум причинам. Первая — небольшая элитарная «туса» достаточно крупных компаний владеет большей частью информации в области и либо совсем отказывается, либо очень неохотно делится даже абстрактными описаниями любых применяемых даже в прошлом методик. А те, кто делятся, рассказывают обычно то, что описано в википедии или уже имеется в общем доступе (типичный пример). Их в принципе можно понять, они делают на этом очень большие деньги и не закрывать это 20 уровнями NDA для них было бы суицидом. По крайней мере они так считают. Хотите знать — приходите работать.

Имеющаяся же информация, выходящая за рамки начального уровня, обычно является «сырой». То есть доступной в основном в виде научных статей и диссертаций по 300 страниц, где подается в весьма специфичной форме и для понимания требует долгой упорной переработки. А так как я знаю как пишется большинство «научных» статей (сам имел дело), то практически всегда возникает проблема «нужно ли тратить вечер на чтение этого, или там опять написаны очевидные вещи сложными словами». Именно переработка такой сырой информации и занимает огромную часть времени, но другого выхода нет. Подходящих знакомых в Гугле, Яндексе, ABBYY у меня к сожалению пока нет, так что спрашивать советов тоже не у кого. Завести таких знакомых всё еще не удалось.

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

Многие здесь в курсе, что в свободное время я занимаюсь одним хобби-проектом, Futurise. После выхода пробной публичной версии и небольшого опроса пользователей я увидел два пути его развития: упор на личный планировщик, либо на сбор полной базу данных событий в городе. Как сказал @mutantcornholio, практически определив мое решение, «хочется первого, но успешно использовать удавалось только как второе».

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

Я оцениваю свои знания по NLP как ниже среднего, потому нисколько не претендую на гуру-мастер-класс, а исключительно заполняю информационную пустоту по данной теме.

Шаг первый: найти данные.

Прикинув и поспрашивав знакомых о том, как они узнают о новых событиях, стало понятно, что основной источник для них это ВКонтакте, за ним с упором на концерты идет last.fm, далее — всё остальное примерно в одинаковых пропорциях. Собирать данные вручную у меня нет ресурсов и возможностей, потому очевидно, что собирать надо было автоматически. Но как? Ведь ВКонтакте даже нельзя спросить «все события в городе N», только искать конкретные названия. Last.fm можно, но там отражается такой минимум разве что самых крупных гастролей каких-либо групп. Так же было очевидно, что необходимо подключить к сбору некоторые локальные афиши, на которых никто специально не сидит, но часто заходит из поисковиков. С последним всё понятно, написать простые парсеры лишь дело времени, хотя хотелось бы делать обработку страниц универсально, но пока добавим ручной парсинг одного популярного местного ресурса и успокоимся.

С last.fm получать все данные по городу проще всего, они забираются одним запросом через чудесный API даже не требуя авторизации (хотя на самом деле я сделал чуть по-другому, но это мелочи). Попутно еще воспользовался таким же простым и приятным API MyShows, распарсив топ-100 активных сериалов. Самая главная проблема и самый большой источник данных — это ВКонтакте. ВКонтакте очень большой сайт, потому я понимаю, что они не могут охватить в своем API все его аспекты, как тот же last.fm (хотя иногда там явно к разработчикам приходил ТУПОЛЕНЬ). С ним нужно что-то делать.

Сериалы парсятся проще всего

А делать было решено две вещи (снова две, ага). Первая — найти в ВК официальные группы тех или иных площадок: клубов, театров, музеев, и.т.д. и парсить с них все анонсы, полагаясь на их SMM'щиков. Вторая — парсить события пользователей, подключивших свои ВК к Futurise. А еще события их друзей. Второй метод диаметрально противоположен первому. В первом проблемой является найти события по площадке, в то время как во втором наоборот сложность представляет связать с местом проведения по имеющемуся событию (события о вечеринках в некоторых клубах создают простые пользователи, а система должна понимать о каком клубе идет речь просто из описания). Оба подхода интересны и перспективны, но для начала реализовать необходимо первый, потому что пользователей у нас пока нет.

Для всего этого нам необходимы данные о всех интересующих местах в городе по нескольким категориям: клубы, концертные залы, театры, филармонии, музеи, планетарии ну и еще парочку. Здесь, к моему глубочайшему сожалению, нет выбора и надо использовать API 2gis. Выполнив все архаичные пляски для получения ключа доступа (нужно оплатить госпошлину заполнить анкету и каждый ключ выдается лично живым (!) человеком, колл-центр ведь целый этаж занимает, надо их чем-то занять) я получил код на 1000 запросов к API. Нет 1000 не в секунду, 1000 запросов ВООБЩЕ. Прямо совок — живые очереди, API по талонам. Ну ладно, дед на войне голодал, придется и мне. Чтобы получить больше запросов, надо выполнить их условия: расставить по всем страницам ссылки на них и вставить загрузку javascript-файла с их сервера. Отличный способ собирать куки и тормозить загрузку страниц конкурентов, молодцы. И еще они запрещают кешировать. Но с этим еще предстоит разобраться.

Пример объединения данных из разных источников

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

Чаще всего для площадок нет нормальных картинок, которые можно было бы использовать в качестве аватарок и фонов, аватарки в ВК имеют очень маленькое разрешение, а в остальных источниках чаще всего отсутствуют. Недолго думая я решил воспользоваться тем же, что я делаю всегда — нагуглить. Сначала хотел искать Яндексом, но у него какой-то сильно разухабистый API, требующий регистрации и принятия лицензии, что сразу напугало меня, и был найден старый API гугла, который делал поиск по картинкам просто и молча: https://ajax.googleapis.com/ajax/services/search/images?v=1.0&q=Запрос&start=0&userip=NO&rsz=8.

Он еще и возвращает размеры изображений, какой молодец, но к сожалению не больше 8 за раз (параметр rsz). Потому простая функция на питоне, которая перебирает картинки пока не найдет подходящую, а так же формирование запроса типа «[название заведение] [название города]» решает проблему с аватарками. Можно поиграть еще с добавлением ключевых слов типа «лого». Неприятный момент вышел всего 1 раз с клубом FIRST, когда его аватаркой стала фотка с камеры наблюдения из статьи на тайга.инфо про перестрелку рядом с ним.

Шаг второй: парсинг.

Данные из 2gis, ВК, last.fm и др. являются «источниками», которые затем группируются в «продюсеров» (они же потом превращаются в юзеров). Группируются достаточно просто, но умно: определяется наилучшее название (об этом далее), затем данными из каждого источника заполняются пустые поля продюсера. То есть из 2gis можно вытащить телефоны и координаты, а из ВК, например, описание. Есть несколько метрик определения наилучшего источника по данному полю: самый простой — «первый не пустой» (например для картинки-аватарки), самый понятный — «самое популярное значение» (для города или категории), и самый интересный — «максимально чистый текст» (для названий и описаний).

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

— 23 АПРЕЛЯ ;;;;;БУДЕТ ЖАРКО;;;;;~☼~Комитет Охраны Тепла (Санкт-Петербург)~☼~
— •••♔•••♔•••♔••• POSH™ BOUTIQUE для женщин •••♔•••♔•••♔•••
— 12 июЛя. Концерт группы "КОРИДОР" в честь Дня Рождения Алексея Костюшкина. Клуб "Рок Сити". Сбор гостей в 19:00Телефон 227-01-08

Да, это настоящие заголовки настоящих событий в ВКонтакте, которые создают настоящие SMM-профессионалы, мастера своего дела. Именно здесь и начинается то, что я называю обработкой «ну очень естественного» языка. Метрика «максимально чистый текст» как раз находит из всех источников один с максимально адекватным названием, к которому не прикладывал руку SMM-гуру. Работает так: для каждого текста заводится шкала баллов неадекватности. За каждый символ, написанный капсом, дается +1 балл. За каждый символ ?, !, ) и еще некоторые популярные печатные знаки дается еще +4 балла. За каждый символ, не являющийся буквой (ru/en) или цифрой дается 2-3 балла. За остальное не дается ничего. Затем количество баллов нормируется, путем деления на длину строки и выбирается строка с наименьшим количеством заработанных баллов неадекватности.

Но на этом обработка не заканчивается. Перед тем как действительно создать то, что будет видно пользователям, каждый заголовок проходит процедуру под названием unidiot_text — превращение текста, написанного SMM-идиотом, в нормальный. Иногда даже слишком стерильный, но куда лучший, чем изначальный. Во-первых, удаляются даты. В любом виде, начиная от «10.05», кончая «3 января». Регуляркой. Во-вторых, все повторяющиеся!!!! символы))))), кроме букв и цифр, сносятся к чертям. Затем выпиливаются все символы в начале и в конце до первой или после последней буквы/цифры. То есть -=== такое ===-. Вырезаются стоп-слова типа «только» и «впервые» (список из нескольких десятков). Ну и напоследок вырезаются названия вместе с предлогами, однако здесь нужно еще поработать, так как никто из SMM-щиков никогда не называет место своей работы правильно. В конце текст приводится в нижний регистр, капитализуется и типографируется. В итоге из •••♔ 11 января!!! ТОЛЬКО В ROCK-CITY! КОНЦЕРТ ГРУППЫ "РАНЕТКИ"))))) ♔••• заголовок превращается во что-то типа — Концерт Группы «Ранетки». Чаще всего проблемы возникают с интересными названиями групп, содержащими стоп-слова в себе, а так же с другими нетипичными названиями, но это мелочи и они правятся руками.

Дальше, как мы помним, у нас есть список источников для каждой площадки надо эти источники разбирать. Задача чисто техническая, красиво решаемая через полиморфизм и паттерны типа фабрик. Со вконтакте снова выходит проблема: в его API отсутствует метод получения списка событий для группы. Вместо этого списки событий грузятся чуть ли не в iframe, который подгружает POST'ом простой HTML. Потому здесь нам пригодится парсинг HTML, а в остальном обычный JSON.

Celery всегда помогает если стоит задача много считать в фоне

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

Грубо говоря метрика tf-idf учитывает то как часто слово встречается в данном тексте и во всех остальных документах. Если слово встречается часто во всех документах, его вес практически нулевой, оно не важно, но если слово встречается только в определенных документах, то скорее всего они похожи. Посчитав меру tf-idf для всех слов одного и второго документа можно получить их вектора, между которыми можно посчитать косинус угла, который и будет очень красиво от 0 до 1 показывать насколько два документа похожи (кто забыл, косинус равен скалярному произведению деленному на произведение длинн). Не получается сейчас подробно описывать это, статья и так получается очень объемной, но раз я вызвался писать про NLP для самых маленьких, по просьбе в комментариях могу описать векторную модель в поиске подробнее.

Этот метод определения схожести показал себя вполне неплохо, хоть иногда и приходится руками корректировать плохие случаи. Но это еще не всё, кроме всего этого перед созданием настоящего события необходимо определить к какой категории из существующих 9 его отнести: Концерты, Театры, Вечеринки, Сериалы, Выставки, Мероприятия, Спорт, Образование, Шоппинг. Конечно, можно было бы ориентироваться на категорию продюсеров (мы ее знаем с самого начала). Это справедливо для музеев, в которых скорее всего проводят только выставки, однако не срабатывает для клубов, в которых концерты и вечеринки проходят с равной частотой.

Здесь нам снова поможет воистину волшебная метрика tf-idf, однако теперь простым подсчетом угла между векторами нам не обойтись. Нужен классификатор. Когда я был маленький и познавал мир, я писал свой наивный байесовский классификатор. Это было весело, но в современных реалиях лучше использовать штуку давно проверенную и самую эффективную для широкого круга задач — метод опорных векторов (SVM). Самая популярная реализация — это libsvm, написана на C++ и у нее в комплекте сразу есть биндинги под Python, благодаря чему она удобна и обучается со скоростью света, на вычисление tf-idf уходит времени куда больше, чем на первичное обучение классификатора. А нужно ей для обучения всего-лишь руками раскидать все неподходящие под свои категории события (всего их сейчас около 400) и скормить пары «вектор tf-idf» — «категория». Обучающая выборка пока небольшая, так что до идеальной классификации нужно собрать немного больше данных, но даже на таком объеме она работает примерно в 80% скормленных мной новых событиях, правильно определяя их категории.

Это не вся, но бОльшая часть процессинга, происходящего при создании события в Futurise. И хоть ее описание или код и могут занимать десяток экранов, то работает это всё достаточно быстро, на обработку 1 события уходит меньше секунды, точных данных не замерял, да и рано пока.

Пара примеров:
— Несколько источников в одном событии http://futurise.ru/rock-city/event/3695/
— Список http://futurise.ru/search/concert/
— Сериал http://futurise.ru/how-i-met-your-mother-show/
— Парсинг только ВК http://futurise.ru/pinmixnsk/

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

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