Главная » Хабрахабр » [Из песочницы] Как я понял, что ем много сладкого, или классификация товаров по чекам в приложении

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

Задача

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

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

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

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

Вдобавок никакой дополнительной информации из названий этот подход не извлекает. Самый простой вариант — использование 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

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

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

Для этого алгоритма мы использовали простейший вариант токенизации: разбили название на отдельные слова и взяли их начальные формы. Этот подход может решить проблему большой размерности и разряженности пространства, получающегося методом 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 '.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” будут считаться разными. В названиях также присутствует множество других опечаток и сокращений.

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Вышел Rust 2018… но что это такое?

Статья написана Лин Кларк в сотрудничестве с командой разработчиков Rust («мы» в тексте). Можете прочитать также сообщение в официальном блоге Rust. В этом релизе мы сосредоточились на производительности, чтобы разработчики Rust стали работать максимально эффективно. 6 декабря 2018 года вышла ...

50 лет спустя. The Mother of All Demos

«Компьютерная революция еще не случилась.(The computer revolution hasnt happened yet)»— Алан Кей Всем привет. И я стартую проект «Энгельбарт» (чтобы это ни было и что бы это ни значило). Сегодня 50 лет с исторического события, известного как "Мать всех демонстраций" ...