Задача

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

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

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

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

Самый простой вариант — использование 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