Алгоритм априори - Apriori algorithm - Wikipedia

Априори^[1] является алгоритм для частого поиска наборов элементов и изучения ассоциативных правил над реляционными базы данных. Он продолжается путем выявления часто встречающихся отдельных элементов в базе данных и расширения их на все большие и большие наборы элементов, пока эти наборы элементов появляются в базе данных достаточно часто. Частые наборы предметов, определенные Apriori, могут использоваться для определения правила ассоциации которые подчеркивают общие тенденции в база данных: у этого есть приложения в таких доменах, как анализ корзины.

Обзор

Алгоритм Априори был предложен Агравалом и Шрикантом в 1994 году. Априори предназначен для работы на базы данных содержащие транзакции (например, коллекции товаров, купленных клиентами, или сведения о посещении веб-сайтов или IP-адреса^[2]). Другие алгоритмы предназначены для поиска ассоциативных правил в данных, не имеющих транзакций (Winepi и Minepi) или без отметок времени (секвенирование ДНК). Каждая транзакция рассматривается как набор элементов ( набор предметов). Учитывая порог ${ displaystyle C}$ , алгоритм Apriori идентифицирует наборы элементов, которые являются подмножествами не менее ${ displaystyle C}$ транзакции в базе данных.

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

Априори использует поиск в ширину и Хеш-дерево структура для эффективного подсчета наборов элементов-кандидатов. Он генерирует наборы элементов-кандидатов длины ${ displaystyle k}$ из комплектов изделий длины ${ displaystyle k-1}$ . Затем он обрезает кандидатов, которые имеют нечасто повторяющийся шаблон. Согласно лемме о закрытии сверху вниз, множество кандидатов содержит все частые ${ displaystyle k}$ -длина комплектов предметов. После этого он сканирует базу данных транзакций, чтобы определить частые наборы элементов среди кандидатов.

Псевдокод алгоритма приведен ниже для базы данных транзакций. ${ displaystyle T}$ , и порог поддержки ${ displaystyle epsilon}$ . Используются обычные теоретико-множественные обозначения, хотя обратите внимание, что ${ displaystyle T}$ это мультимножество. ${ displaystyle C_ {k}}$ кандидат установлен на уровень ${ displaystyle k}$ . Предполагается, что на каждом шаге алгоритм генерирует наборы кандидатов из больших наборов элементов предыдущего уровня, соблюдая лемму о нисходящем закрытии. ${ displaystyle count [c]}$ обращается к полю структуры данных, которое представляет набор кандидатов ${ displaystyle c}$ , который изначально предполагается равным нулю. Многие детали опускаются ниже, обычно наиболее важной частью реализации является структура данных, используемая для хранения наборов кандидатов и подсчета их частот.

${ displaystyle { begin {align} & mathrm {Apriori} (T, epsilon) & qquad L_ {1} gets { mathrm {large ~ 1-itemsets} } & qquad k получает 2 & qquad mathrm { textbf {while}} ~ L_ {k-1} neq emptyset & qquad qquad C_ {k} gets {c = a cup {b } mid a in L_ {k-1} land b not in a, {s substeq c mid | s | = k-1 } substeq L_ {k-1} } & qquad qquad mathrm {{ textbf {for}} ~ транзакции} ~ t in T & qquad qquad qquad D_ {t} gets {c in C_ {k } mid c substeq t } & qquad qquad qquad mathrm {{ textbf {for}} ~ кандидаты} ~ c in D_ {t} & qquad qquad qquad qquad { mathit {count}} [c] gets { mathit {count}} [c] +1 & qquad qquad L_ {k} gets {c in C_ {k} mid { mathit {count}} [c] geq epsilon } & qquad qquad k получает k + 1 & qquad mathrm { textbf {return}} ~ bigcup _ {k} L_ { к} конец {выровнено}}}$

Примеры

Пример 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}, не может быть частым. Таким образом, мы можем чернослив sets: теперь мы будем искать частые тройки в базе данных, но мы уже можем исключить все тройки, которые содержат одну из этих двух пар:

Элемент	Поддерживать
{2,3,4}	2

в примере нет частых троек. {2, 3, 4} ниже минимального порога, а другие тройки были исключены, потому что они были суперпарами, которые уже были ниже порога.

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

Ограничения

Априори, будучи исторически значимым, страдает рядом недостатков или компромиссов, которые породили другие алгоритмы. Генерация кандидатов генерирует большое количество подмножеств (алгоритм пытается загрузить набор кандидатов с максимально возможным количеством подмножеств перед каждым сканированием базы данных). Исследование подмножества снизу вверх (по сути, обход решетки подмножеств в ширину) находит любое максимальное подмножество S только после того, как все ${ displaystyle 2 ^ {| S |} -1}$ собственных подмножеств.

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

Кроме того, как временная, так и пространственная сложность этого алгоритма очень высока: ${ Displaystyle O (2 ^ {| D |})}$ , таким образом, экспоненциальная, где ${ displaystyle | D |}$ - горизонтальная ширина (общее количество элементов) в базе данных.

Более поздние алгоритмы, такие как Макс-Майнер^[3] попытайтесь определить максимально частые наборы элементов, не перечисляя их подмножества, и выполните «скачки» в пространстве поиска, а не чисто восходящий подход.

внешняя ссылка

ARtool, GPL Java-приложение для извлечения ассоциативных правил с графическим интерфейсом, предлагающее реализации нескольких алгоритмов для обнаружения частых шаблонов и извлечения ассоциативных правил (включая Apriori)
SPMF предлагает Java-реализации Apriori с открытым исходным кодом и несколько вариаций, таких как AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID и другие более эффективные алгоритмы, такие как FPGrowth и LCM.
Кристиан Боргельт предоставляет реализации C для Apriori и многих других частый поиск паттернов алгоритмы (Eclat, FPGrowth и др.). Код распространяется как бесплатное программное обеспечение под Лицензия MIT.
В р упаковка Arules содержит Apriori и Eclat, а также инфраструктуру для представления, обработки и анализа данных и шаблонов транзакций.
Эффективный-Априори представляет собой пакет Python с реализацией алгоритма, представленного в исходной статье.

[apriori-1] Ракеш Агравал и Рамакришнан Шрикант Быстрые алгоритмы ассоциативных правил майнинга. Труды 20-й Международной конференции по очень большим базам данных, VLDB, страницы 487-499, Сантьяго, Чили, сентябрь 1994 г.

[2] Наука о данных, лежащая в основе сопоставления IP-адресов Опубликовано deductive.com, 6 сентября 2018 г., получено 7 сентября 2018 г.

[3] Баярдо-младший, Роберто Дж. (1998). «Эффективное извлечение длинных шаблонов из баз данных» (PDF). Запись ACM SIGMOD. 27 (2).

[1]

[2]

[3]