Apriori [1] - это алгоритм для частого анализа наборов элементов и изучения правил ассоциации в реляционных базах данных . Он продолжается путем определения часто встречающихся отдельных элементов в базе данных и расширения их на все большие и большие наборы элементов, пока эти наборы элементов появляются в базе данных достаточно часто. Частые наборы товаров, определенные Apriori, могут использоваться для определения правил ассоциации, которые выделяют общие тенденции в базе данных : это имеет приложения в таких областях, как анализ рыночной корзины .
Обзор
Алгоритм Apriori был предложен Agrawal и Srikant в 1994 году. Apriori предназначен для работы с базами данных, содержащими транзакции (например, коллекции товаров, купленных клиентами, или сведения о посещении веб-сайтов или IP-адреса [2] ). Другие алгоритмы предназначены для поиска ассоциативных правил в данных, не имеющих транзакций ( Winepi и Minepi) или не имеющих временных меток (секвенирование ДНК). Каждая транзакция рассматривается как совокупность элементов (An НИКАКИХ гарантий ). Учитывая порог, алгоритм Apriori идентифицирует наборы элементов, которые являются подмножествами не менее транзакции в базе данных.
Apriori использует подход «снизу вверх», когда частые подмножества расширяются по одному элементу за раз (этап, известный как генерация кандидатов ), а группы кандидатов проверяются на основе данных. Алгоритм завершается, когда не обнаруживаются дальнейшие успешные расширения.
Apriori использует поиск в ширину и древовидную структуру хэша для эффективного подсчета наборов элементов-кандидатов. Он генерирует наборы элементов-кандидатов длины из комплектов изделий длины . Затем он обрезает кандидатов, которые имеют нечасто повторяющийся шаблон. Согласно лемме о закрытии сверху вниз, множество кандидатов содержит все частые-длина комплектов предметов. После этого он сканирует базу данных транзакций, чтобы определить частые наборы элементов среди кандидатов.
Псевдокод алгоритма приведен ниже для базы данных транзакций. , и порог поддержки . Используются обычные теоретико-множественные обозначения, хотя обратите внимание, чтоэто мультимножество . кандидат установлен на уровень . Предполагается, что на каждом шаге алгоритм генерирует наборы кандидатов из больших наборов элементов предыдущего уровня, соблюдая лемму о нисходящем закрытии. обращается к полю структуры данных, которое представляет набор кандидатов , который изначально предполагается равным нулю. Многие детали опускаются ниже, обычно наиболее важной частью реализации является структура данных, используемая для хранения наборов кандидатов и подсчета их частот.
Априори (T, ε) L 1 ← {large 1 - itemsets} k ← 2 а L k − 1 не пусто C k ← Apriori_gen (L k − 1 , k) для транзакций t в T D t ← {c in C k : c ⊆ t} для кандидатов c в D t count [c] ← count [c] + 1 L k ← {c в C k : count [c] ≥ ε} к ← к + 1 возвратный союз (L k ) Apriori_gen (L, k) результат ← список () для всех p ⊆ L, q ⊆ L, где p 1 = q 1 , p 2 = q 2 , ..., p k-2 = q k-2 и p k-1 k-1 c = p ∪ { q k-1 }, если u ⊆ c для всех u в L result.add (c) вернуть результат
Примеры
Пример 1
Рассмотрим следующую базу данных, где каждая строка является транзакцией, а каждая ячейка - отдельным элементом транзакции:
альфа | бета | эпсилон |
альфа | бета | тета |
альфа | бета | эпсилон |
альфа | бета | тета |
Из этой базы данных можно определить следующие правила ассоциации:
- 100% наборов с альфой также содержат бета
- 50% наборов с альфа, бета также имеют эпсилон
- 50% сетов с альфа, бета также имеют тета
мы также можем проиллюстрировать это на различных примерах.
Пример 2
Предположим, что большой супермаркет отслеживает данные о продажах по единицам складского учета (SKU) для каждого товара: каждый товар, например «масло» или «хлеб», идентифицируется числовым SKU. В супермаркете есть база данных транзакций, где каждая транзакция представляет собой набор SKU, купленных вместе.
Пусть база данных транзакций состоит из следующих наборов элементов:
Наборы предметов |
---|
{1,2,3,4} |
{1,2,4} |
{1,2} |
{2,3,4} |
{2,3} |
{3,4} |
{2,4} |
Мы будем использовать Apriori для определения частых наборов элементов этой базы данных. Для этого мы скажем, что набор элементов является частым, если он появляется как минимум в 3 транзакциях базы данных: значение 3 является порогом поддержки .
Первый шаг Apriori - подсчитать количество появлений, называемых поддержкой, каждого элемента-члена отдельно. При первом сканировании базы данных получаем следующий результат
Пункт | Служба поддержки |
---|---|
{1} | 3 |
{2} | 6 |
{3} | 4 |
{4} | 5 |
Все наборы элементов размера 1 имеют поддержку как минимум 3, поэтому все они встречаются часто.
Следующим шагом является создание списка всех пар часто встречающихся элементов.
Например, относительно пары {1,2}: первая таблица в примере 2 показывает элементы 1 и 2, появляющиеся вместе в трех наборах элементов; поэтому мы говорим, что элемент {1,2} поддерживает три.
Пункт | Служба поддержки |
---|---|
{1,2} | 3 |
{1,3} | 1 |
{1,4} | 2 |
{2,3} | 3 |
{2,4} | 4 |
{3,4} | 3 |
Пары {1,2}, {2,3}, {2,4} и {3,4} все соответствуют минимальной поддержке 3 или превышают ее, поэтому они встречаются часто. Пары {1,3} и {1,4} - нет. Теперь, поскольку {1,3} и {1,4} не часто встречаются, любой больший набор, содержащий {1,3} или {1,4}, не может быть частым. Таким образом, мы можем сократить наборы: теперь мы будем искать частые тройки в базе данных, но мы уже можем исключить все тройки, которые содержат одну из этих двух пар:
Пункт | Служба поддержки |
---|---|
{2,3,4} | 2 |
в примере нет частых троек. {2, 3, 4} ниже минимального порога, а другие тройки были исключены, потому что они были суперсистемами пар, которые уже были ниже порогового значения.
Таким образом, мы определили часто встречающиеся наборы элементов в базе данных и проиллюстрировали, как некоторые элементы не учитывались, потому что одно из их подмножеств, как уже было известно, ниже порогового значения.
Ограничения
Априори, будучи исторически значимым, страдает рядом недостатков или компромиссов, которые породили другие алгоритмы. Генерация кандидатов генерирует большое количество подмножеств (алгоритм пытается загрузить набор кандидатов с максимально возможным количеством подмножеств перед каждым сканированием базы данных). Исследование подмножеств снизу вверх (по сути, обход решетки подмножеств в ширину) находит любое максимальное подмножество S только после того, как все собственных подмножеств.
Алгоритм сканирует базу данных слишком много раз, что снижает общую производительность. В связи с этим алгоритм предполагает, что база данных постоянно находится в памяти.
Кроме того, как временная, так и пространственная сложность этого алгоритма очень высока: , таким образом, экспоненциальная, где - горизонтальная ширина (общее количество элементов), присутствующая в базе данных.
Более поздние алгоритмы, такие как Max-Miner [3], пытаются идентифицировать максимально частые наборы элементов без перечисления их подмножеств и выполняют «скачки» в пространстве поиска, а не только восходящий подход.
Рекомендации
- ^ Ракеш Агравал и Рамакришнан Шрикант Быстрые алгоритмы для правил ассоциации майнинга . Труды 20-й Международной конференции по очень большим базам данных, VLDB, страницы 487-499, Сантьяго, Чили, сентябрь 1994 г.
- ^ Наука о данных, лежащая в основе сопоставления IP-адресов Опубликовано deductive.com, 6 сентября 2018 г., получено 7 сентября 2018 г.
- ^ Bayardo Jr, Роберто J. (1998). «Эффективное извлечение длинных шаблонов из баз данных» (PDF) . ACM SIGMOD Запись . 27 (2).
Внешние ссылки
- ARtool , GPL Java-приложение для извлечения ассоциативных правил с графическим интерфейсом пользователя, предлагающее реализации нескольких алгоритмов для обнаружения частых шаблонов и извлечения ассоциативных правил (включая Apriori)
- SPMF предлагает Java-реализации Apriori с открытым исходным кодом и несколько вариантов, таких как AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID и другие более эффективные алгоритмы, такие как FPGrowth и LCM.
- Кристиан Боргельт предоставляет реализации C для Apriori и многих других часто используемых алгоритмов анализа шаблонов (Eclat, FPGrowth и т. Д.). Код распространяется как бесплатное программное обеспечение по лицензии MIT .
- В R пакет arules содержит Apriori и Eclat и инфраструктуры для представления, обработки и анализа данных транзакций и моделей.
- Efficient-Apriori - это пакет Python с реализацией алгоритма, представленного в исходной статье.