Анализ покупательских тенденций - довольно важное дело в науке о данных, и анализ рыночной корзины - один из способов сделать это. Методы в этом подполе направлены на понимание того, как покупка определенных предметов влияет на покупку других предметов. Это позволяет розничным торговцам увеличивать доход за счет дополнительных или перекрестных продаж своих существующих клиентов.
Понимание алгоритма априори является основополагающим для понимания многих методов анализа рыночной корзины. Он используется для поиска групп товаров, которые часто встречаются вместе в наборе данных о покупках. Обычно это первый шаг к поиску новых способов продвижения товаров.
Итак ... Как выглядят данные о покупках?
Представьте, что у нас есть файл, в котором каждая строка представляет корзину покупателя во время оформления заказа. Назовем это корзиной.
Каждая корзина состоит из предметов. Наша цель - найти наборы элементов, которые часто встречаются вместе в наборе данных. Мы будем называть их часто используемыми наборами элементов.
Наша цель - найти наборы элементов, которые часто встречаются вместе в наборе данных.
Мы дадим собственное определение того, что означает часто. Это определение, вероятно, изменится в зависимости от количества корзин в наборе данных. Как правило, нас будут интересовать частые наборы товаров определенного размера. Предположим, сегодня мы ищем частые тройки (т. Е. Наборы 3-го размера).
Продолжая изучение ниже, давайте воспользуемся этим примером набора данных, чтобы расширить обсуждение. Он принимает формат, описанный выше.
Некоторые краткие статистические данные о примере набора данных:
- В нем 100000 корзин.
- В этом супермаркете продается 5000 наименований товаров.
- У каждого предмета есть поддельный номер ISBN (ну, как у книг 📚)
Предположим также, что появление более 1000 раз делает набор элементов частым. (Примечание: количество элементов набора часто называют его поддержкой.)
Наивный подход
Первое, что приходит в голову, - это просмотреть набор данных, подсчитать появление всех троек, а затем отфильтровать те, которые встречаются нечасто.
Наивный подход привлекает своей простотой. Однако в итоге мы считаем очень много троек.
В примере набора данных более 7 миллионов троек, но только 168 из них являются частыми.
Всего троек более 7 миллионов, но частые только 168 из них.
Это проблема по двум причинам:
- Отсчет этих миллионов троек занимает много места.
- На построение и подсчет всех этих троек уходит много времени.
Если бы только был способ не строить и не считать столько троек…
Ключевая интуиция
Есть способ избежать этого! И он полагается на ключевую информацию. Не волнуйтесь, мы вместе разберемся, но вот он:
Основная интуиция заключается в том, что все подмножества частых наборов элементов также являются частыми наборами элементов.
Для большей ясности рассмотрим эти четыре корзины:
Хорошо видно, что набор {яйца, мука, молоко} повторяется 3 раза. И рискуем показаться слишком упрощенным: каждый раз, когда мы видим группу {яйца, мука, молоко}, мы видим отдельные элементы {яйца}, {мука} и {молоко}. В результате мы можем с уверенностью сказать, что поддержка (то есть количество) {яиц} будет не меньше поддержки набора {яйца, мука, молоко}. То же касается муки и молока.
Фактически, мы можем распространить этот факт на пары предметов внутри набора {яйца, мука, молоко}. Это означает Поддержка ({яйца, мука}) ≥ Поддержка ({яйца, мука, молоко}). Опять же, это потому, что набор {яйца, мука} обязательно встречается всякий раз, когда встречается набор {яйца, мука, молоко}, поскольку он является его подмножеством. Конечно, это распространяется на наборы и подмножества большего размера.
Хорошо ... И что?
Обозначенный выше факт становится полезным, когда вы думаете об этом в другом направлении. Так как сахар, например, встречается только один раз, мы знаем, что любой набор, содержащий сахар, может встречаться только один раз.
Подумайте об этом: если тройка, содержащая сахар, встречается более одного раза, это будет означать, что сахар встречается более одного раза. А поскольку сахар встречается только один раз, мы можем гарантировать, что любая тройка, содержащая сахар, не появится более одного раза.
Это означает, что мы можем просто игнорировать все наборы, содержащие сахар, поскольку мы знаем, что они не могут быть частыми наборами элементов.
Мы можем применить ту же логику и к более крупным подмножествам. На изображении выше {молоко} и {масло} появляются по три раза. Но в паре они появляются вместе только дважды (т. Е. Support ({milk, butter}) = 2). Это означает, что любая тройка, содержащая пару {молоко, масло}, может встречаться не более двух раз. При сканировании троек, которые появляются 3 или более раз, мы могли бы просто игнорировать {молоко, масло, мука}, поскольку оно содержит {молоко, масло}, поэтому мы знаем, что оно должно появляться не более двух раз. .
Алгоритм априори использует этот факт, чтобы исключить ненужное построение и подсчет наборов элементов.
Алгоритм априори
В отличие от наивного подхода, который делает один проход по набору данных, априорный алгоритм выполняет несколько проходов, увеличивая размер подсчитываемых наборов элементов каждый раз. Он отфильтровывает нерелевантные наборы элементов, используя знания, полученные на предыдущих этапах.
Вот схема алгоритма:
Первый проход
- Получите количество всех элементов в наборе данных
- Отфильтровать элементы, которые не часто встречаются
Второй проход
- Получите количество пар элементов в наборе данных. НО: учитывайте только пары, в которых оба элемента в паре часто встречаются. (Они называются парами кандидатов.)
- Отфильтруйте пары, которые встречаются не часто.
Третий проход
- Получите количество троек в наборе данных. НО: учитывайте только тройки кандидатов . Если какие-либо элементы в тройке не часто встречаются, тройка не является кандидатом на тройку. Если какая-либо из пар элементов в тройке не является частой, тройка не является тройкой-кандидатом.
- Отфильтруйте нечастые тройки.
N-й проход
- Получите количество наборов-кандидатов размера N. (Помните: если какие-либо подмножества элементов в наборе элементов не часто встречаются, то набор элементов не может быть частым.)
- Отфильтруйте наборы элементов, которые не используются часто.
Хотя этот алгоритм в конечном итоге выполняет больше проходов по данным, он экономит много времени, сокращая количество наборов элементов, которые он создает и считает.
Взгляните на эту статистику из нашего примера набора данных:
В конечном итоге именно это сокращение количества рассматриваемых наборов элементов делает алгоритм априори намного лучше, чем наивный подход.
Хотите по-настоящему понять это…?
Я рекомендую вам реализовать алгоритм априори самостоятельно, чтобы укрепить свое понимание.
Для начала я создал репозиторий Github с некоторыми примерами наборов данных и другими ресурсами, которые помогут вам начать работу.
Вот две проблемы - одна намного сложнее другой.
Соревнование
Извлеките частые тройки из примеров наборов данных, реализовав алгоритм априори и проведя три прохода по набору данных.
Проверьте свою реализацию, также применяя наивный подход и сравнивая свои результаты.
Бонусное испытание
Реализуйте алгоритм априори так, чтобы он часто извлекал наборы элементов любого заданного размера. Например, если я хочу извлекать частые наборы элементов, скажем, размера 13, он должен уметь это делать.
Репозиторий Github включает скрипт, который можно использовать для создания очень больших наборов данных. Используйте это, чтобы протестировать вашу более общую реализацию.
(Если вы решите принять бонусное испытание, я рекомендую вам сначала выполнить трехпроходную реализацию. Я думаю, это поможет вам лучше понять.)
Избегайте этой распространенной ошибки
Одна из наиболее распространенных ошибок при реализации этого алгоритма происходит при проверке наборов-кандидатов. Люди часто не забывают проверять, часто ли встречаются отдельные элементы в наборе элементов, но забывают проверить, часто ли встречаются все подмножества текущего набора элементов.
Люди часто не забывают проверять, часто ли встречаются отдельные элементы в наборе, но забывают проверить, часто ли встречаются все подмножества текущего набора.
Помните: тройки содержат пары. Квадроциклы содержат тройки и пары. И так далее.
Давай поговорим!
Если вы решите одну из вышеперечисленных задач, дайте мне знать. Я хотел бы обменяться с вами реализациями алгоритма и узнать о вашем опыте.
Я указал свой адрес электронной почты в репозитории Github, поэтому обращайтесь к нам.
Хотите оставаться в курсе таких вопросов? Присоединяйтесь к моему списку рассылки, где я каждую неделю делюсь ресурсами по Data Science.
Поделитесь своими мыслями в комментариях ниже!
