Apriori алгоритм

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

Описание

Алгоритм Apriori был предложен Агравалом и Шрикантом в 1994 году. Apriori предназначен для работы с базами данных, содержащими транзакции (например, коллекции товаров, купленных клиентами, или сведения о посещаемости веб-сайта, или IP-адреса). Другие алгоритмы предназначены для поиска ассоциативных правил в данных, не содержащих транзакций (Winepi и Minepi) или не имеющих временных меток (секвенирование ДНК). Каждая транзакция рассматривается как набор элементов (itemset). При заданном пороговом значении $ C $ алгоритм Apriori идентифицирует наборы элементов, которые являются подмножествами, по меньшей мере, транзакций $ C $ в базе данных.

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

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

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

Для наглядности рассмотрим следующую базу данных, в которой каждая строка представляет собой транзакцию, а каждый столбец — отдельный элемент транзакции:

A	B	C
alpha	beta	epsilon
alpha	beta	theta
alpha	beta	epsilon
alpha	beta	theta

Правила ассоциации, которые можно определить на основе данной базы данных, следующие:

100% наборов с alpha также содержат beta
50% наборов с alpha, beta также содержат epsilon
50% наборов с alpha, beta также содержат theta

Реализация

python

from itertools import combinations


def load_data() -> list[list[str]]:
    # (1)!
    return [["milk"], ["milk", "butter"], ["milk", "bread"], ["milk", "bread", "chips"]]


def prune(itemset: list, candidates: list, length: int) -> list:
    # (2)!
    pruned = []
    for candidate in candidates:
        is_subsequence = True
        for item in candidate:
            if item not in itemset or itemset.count(item) < length - 1:
                is_subsequence = False
                break
        if is_subsequence:
            pruned.append(candidate)
    return pruned


def apriori(data: list[list[str]], min_support: int) -> list[tuple[list[str], int]]:
    # (3)!
    itemset = [list(transaction) for transaction in data]
    frequent_itemsets = []
    length = 1

    while itemset:
        # (4)!
        counts = [0] * len(itemset)
        for transaction in data:
            for j, candidate in enumerate(itemset):
                if all(item in transaction for item in candidate):
                    counts[j] += 1

        # (5)!
        itemset = [item for i, item in enumerate(itemset) if counts[i] >= min_support]

        # (6)!
        for i, item in enumerate(itemset):
            frequent_itemsets.append((sorted(item), counts[i]))

        length += 1
        itemset = prune(itemset, list(combinations(itemset, length)), length)

    return frequent_itemsets

Возвращает примерный набор данных транзакции
Необходимо провести фильтрацию наборов элементов-кандидатов, которые встречаются в данных нечасто. Для этого следует проверить, присутствуют ли все (k-1) подмножества набора элементов-кандидатов в частых наборах элементов предыдущей итерации
Возвращает список часто используемых наборов элементов и количество их поддерживаемых элементов
Поддержка подсчёта набора элементов
Обрезайте редкие продукты
Добавляйте часто используемые наборы элементов (в виде списка для поддержания порядка)