Как я понял, что ем много сладкого, или классификация товаров по чекам в приложении

Задача


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

Кластеризация


Одна из проблем заключалась в том, что названия товаров, которые мы получаем из чеков, не всегда легко расшифровать, даже человеку. Вряд ли вы узнаете, какой именно товар с названием “УТРУСТА крншт” был куплен в одном из российских магазинов? Истинные ценители шведского дизайна конечно ответят нам сразу: Кронштейн для духовки Утруста, но держать в штабе таких специалистов довольно затратно. К тому же у нас не было готовой, размеченной выборки, подходящей под наши данные, на который мы смогли бы обучить модель. Поэтому сначала мы расскажем о том, как в отсутствии данных для обучения мы применили алгоритмы кластеризации и почему нам не понравилось.

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

Самый простой вариант — использование Tf-Idf, но в этом случае размерность векторного пространства получается довольно большой, а само пространство разряженным. Вдобавок никакой дополнительной информации из названий этот подход не извлекает. Таким образом, в одном кластере может быть множество продуктов из разных категорий, объединенных общим словом, таким как, например, “картофельный” или “салат”:


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

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

Таблица 1. Расстояния между кластерами.
Кластер С1 С2 С3 С4 С5 С6 С7 С8 С9
C1 0.0 0.502 0.354 0.475 0.481 0.527 0.498 0.501 0.524
C2 0.502 0.0 0.614 0.685 0.696 0.728 0.706 0.709 0.725
C3 0.354 0.614 0.0 0.590 0.597 0.635 0.610 0.613 0.632
C4 0.475 0.685 0.590 0.0 0.673 0.709 0.683 0.687 0.699
C5 0.481 0.696 0.597 0.673 0.0 0.715 0.692 0.694 0.711
C6 0.527 0.727 0.635 0.709 0.715 0.0 0.726 0.728 0.741
C7 0.498 0.706 0.610 0.683 0.692 0.725 0.0 0.707 0.714
C8 0.501 0.709 0.612 0.687 0.694 0.728 0.707 0.0 0.725
C9 0.524 0.725 0.632 0.699 0.711 0.741 0.714 0.725 0.0

Таблица 2. Краткая информация о кластерах
Кластер Количество объектов Среднее расстояние Минимальное расстояние Максимальное расстояние
С1 62530 0.999 0.041 1.001
С2 2159 0.864 0.527 0.964
С3 1099 0.934 0.756 0.993
С4 1292 0.879 0.733 0.980
С5 746 0.875 0.731 0.965
С6 2451 0.847 0.719 0.994
С7 1133 0.866 0.724 0.986
С8 876 0.863 0.704 0.999
С9 1879 0.849 0.526 0.981


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



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

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

max_epochs = 100
vec_size = 20
alpha = 0.025

model = doc2vec.Doc2Vec(vector_size=vec_size,
                alpha=alpha, 
                min_alpha=0.00025,
                min_count=1,
                dm =1)
  
model.build_vocab(train_corpus)

for epoch in range(max_epochs):
    print('iteration {0}'.format(epoch))
    model.train(train_corpus,
                total_examples=model.corpus_count,
                epochs=model.iter)
    # decrease the learning rate
    model.alpha -= 0.0002
    # fix the learning rate, no decay
    model.min_alpha = model.epochs

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


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

Классификация


Предобработка данных


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

Мы изучили нашу базу и нашли типичные ошибки в названиях. На этом этапе мы обошлись регулярными выражениями, с помощью которых мы подчистили названия и привели их к некоему общему виду. При использовании этого подхода результат повышается приблизительно на 7%. В совокупности с простым вариантом SGD Classifier на основе функции потерь Хьюбера с подкрученными параметрами мы получили точность в 81% по F1 (средняя точность по всем категориям продуктов).

sgd_model = SGDClassifier()
parameters_sgd = {
    'max_iter':[100],
    'loss':['modified_huber'],
    'class_weight':['balanced'],
    'penalty':['l2'],
    'alpha':[0.0001]
}
sgd_cv = GridSearchCV(sgd_model, parameters_sgd,n_jobs=-1)
sgd_cv.fit(tf_idf_data, prod_cat)
sgd_cv.best_score_, sgd_cv.best_params_

Также не стоит забывать о том, что некоторые категории люди покупают чаще, чем другие: например “Чай и сладкое” и “Овощи и фрукты” намного популярнее, чем “Услуги” и “Косметика”. При подобном распределении данных лучше использовать алгоритмы, которые позволяют задавать веса (степень важности) для каждого класса. Вес класса можно определить обратно пропорционально величине, равной отношению количеству продуктов в классе к общему количеству продуктов. Но об этом можно не задумываться, так как в имплементациях этих алгоритмов, есть возможность автоматически определять вес категорий.


Получение новых данных для обучения


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

Там мы воспользовались такой формой задания:

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

Мы создали подробную инструкцию с примерами, которая объясняла особенности каждой категории, а также использовали методы контроля качества: сет с эталонными ответами, которые показывались вместе с обычными заданиями (эталонные ответы мы реализовали сами, разметив несколько сотен продуктов). По результатам ответов на эти задания отсеивались пользователи, которые неправильно размечали данные. Однако за весь проект мы забанили всего трёх пользователей из 600+.


С новыми данными мы получили модель, которая лучше подходила под наши данные, и точность ещё немного возросла (на ~11%) и получили уже 92%.

Финальная модель


Процесс классификации мы начали с комбинации данных с нескольких датасетов с Kaggle — 74%, после чего усовершенствовали препроцессинг — 81%, собрали новый набор данных — 92% и наконец-то усовершенствовали сам процесс классификации: изначально с помощью логистической регрессии получаем предварительные вероятности принадлежности товаров к категориям, основываясь на названиях товаров, SGD давал большую точность в процентах, но всё-таки имел большие значения на функциях потерь, что плохо сказалось на результатах итогово классификатора. Далее полученные данные мы совмещаем с другими данными по товару (цена продукта, магазин, в котором он был приобретен, статистика по магазину, чеку и другую мета-информацию), и на всём этом объеме данных обучается XGBoost, что дало точность 98% (прирост ещё 6%). Как оказалось самый большой вклад внесло качество обучающей выборки.

Запуск на сервере


Чтобы ускорить деплоймент, мы подняли на Docker простенький сервер на Flask. Там был один метод, который принимал от сервера товары, которые необходимо категоризировать и возвращал уже товары с категориями. Таким образом мы легко встроились в существующую систему, центром которой был Tomcat, и нам не пришлось вносить изменения в архитектуру — мы просто дополнили её ещё одним блоком.

Релиз


Несколько недель назад мы выложили релиз с категоризацией в Google Play (через некоторое время появится в App Store). Получилось вот так:


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

Упомянутые соревнования на Kaggle:

www.kaggle.com/c/receipt-categorisation
www.kaggle.com/c/market-basket-analysis
www.kaggle.com/c/prod-price-prediction
Поделиться публикацией
Комментарии 21
    0
    А почему чай и сладкое обьединены?
      0
      Объединены в чаепитие: сладкое — каждый день, чай — раз в месяц.
        0
        Мы не придумывали названия категорий сами, мы взяли уже существующее разделение на категории и немного его подкорректировали под специфичность наших данных. К тому же к такому делению привыкли маркетологи и ритейлеры, так как эти категории часто находятся рядом (например, в супермаркетах чай и шоколад всегда рядом).
        +4
        Я и так знаю что я ем много сладкого, напишите софт который будет есть за меня бить мне по рукам…
          0
          Ну в принципе можно.
          Микрофон же есть у телефона.
          Как только вы начинаете хрустеть — издается какой-нибудь противный для вас звук(мелодия).)
          +1
          Кластер у вас относительно чего строится?
          Цены, количества? Ну дык тортики же дорогие, однако их мало.
            0
            Doc2Vec ещё один из алгоритмов, которые позволяют представлять тексты в векторном виде. При использовании этого подхода каждое название будет описано вектором меньшей размерности, чем при использовании Tf-Idf. В получившемся векторном пространстве похожие тексты будут находиться близко друг к другу, а различные далеко.

            Простите, а для tf-idf "похожие тексты" не будут находиться близко?


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

            Так какой же все-таки вы используете алгоритм векторизации и почему?


            Процесс классификации мы начали

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

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

              Я, на самом деле, не понимаю, почему вы ожидали, что это сработает. Возьмем простой список:


              • молоко
              • творожный сырок
              • масло сливочное
              • масло оливковое
              • оливки
              • масло арахисовое

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

                –1

                Жаль, что на 4PDA программы нет. Google Play всё-таки неудобный.


                А почему вы пишете 'Несколько недель назад мы выложили релиз'? Упоминания ЧекСкан есть минимум с начала 2018 года – или это была версия без категоризации?

                  0
                  Google Play всё-таки неудобный.

                  Простите за любопытство, но чем он неудобен?
                    +1

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

                      0

                      А вы не боитесь, что в одном из модов будет неприятный вирус?

                        0

                        4PDA – место популярное, если за прошедшие после появления мода месяцы никто вирус не нашёл, то его, наверное, и нет.


                        Впрочем, несмотря на это, я очень обрадовался, когда приложение Сбербанка стало работать под рутом из коробки, и необходимость в моде на НЕГО отпала.

                          0
                          В ГП тоже можно найти вирусы. На 4пда, как на любом приличном ресурсе, при должной осмотрительности риски невелики.
                            0
                            Только в GP их хотя-бы Google сканирует на уязвимости. А кому это нужно на 4pda?
                      0
                      Да, это была версия без категоризации. Мы добавили её для создания функционала по статистике покупок для пользователей.

                      Мы, кстати, хотели начать выкладывать на 4PDA, но как-то не добрались пока.
                      +1

                      У нас внутри компании (алкогольный сектор) примерно тот же процесс, только приходит поток не от чеков и разбирается по классам не для нужд пользователей а для мастер-данных наших систем.
                      И качество классификации требуется много выше чем в статье, ибо "ВИСКИ ШОТЛАНДСКИЙ БАРКЛАЙС 3 ГОДА 40% 0,7Л" и "Нап ром SHARK TOOTH Silver 40% 0.5L" это не класс "крепкий алкоголь" (что для чеков в Вашей задаче было бы вполне достаточно) а вполне определённые объекты мастер-данных "Виски Барклайс 3 года 0,7" и "Настойка Шарк Тус Сильвер на основе рома 0,50". А есть еще рядом близкие классы с разницей в один символ "Виски Барклайс 3 года 0,5" при том что TF-IDF емкости бутылки стремится к нулю ибо это высокочастотник в алкоголе, а есть еще вина со своей франко-итальянской особенностью написания в кириллице, и много чего еще…
                      Но у в статье задача сильно проще тем не менее, странно что автор упомянул про "залетную" транслитерацию букв (сходных по написанию), а про принудительное разделение термов из серии "МЕРЛОвино МаулеВелле кр.сух.0.75л", "ASCHERIвиноБАРОЛО СОРАНО МаулеВелле кр.сух.14%0.75л" как- то позабыл. (боремся так же -регулярками)
                      Так же учитывая что в текстовое поле ограниченной длины пытаются указать название продукта делая одни и те же слова с разной степенью сокращения, стемминг ну очень сильно помогает в классификации, однако специфика задачи не позволяет использовать стеммер Портера или лемматизацию — специфика сокращений и транслитов на русский. Тут уже чисто свой велосипед стемминга- но оно на практике того стоит.

                        0
                        Ох. Ошибку-то поправьте, «пренадлежит». Не понимаю, как такое может проскочить, когда любой браузер и редактор сразу вопят о неправильности написания.
                          0
                          Спасибо за комментарий. Исправим :)
                          0
                          Чебурек с мясом в категории кошачьих кормов. Машинный разум что-то подозревает )
                            0
                            Главное — что не в домашних животных.

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

                          Самое читаемое