Эклат

Добыча часто встречающихся наборов элементов с эффективным вертикальным представлением данных

Введение:

Eclat (кластеризация классов эквивалентности и обход решетки снизу вверх) — это эффективный алгоритм, используемый для извлечения часто встречающихся наборов элементов из наборов транзакционных данных. Он работает с вертикальным представлением данных, что делает его легко масштабируемым и подходящим для больших наборов данных. В этом блоге мы рассмотрим принципы работы алгоритма Eclat, обсудим его основные концепции, предоставим пример реализации кода на Python и рассмотрим его преимущества и ограничения.

Работающий:

Алгоритм Eclat обнаруживает часто встречающиеся наборы элементов, используя подход, основанный на пересечении. Рабочий процесс можно обобщить следующим образом:

1. Вертикальное представление данных. Преобразуйте набор транзакционных данных в вертикальный формат, где каждый столбец представляет элемент, а строки соответствуют транзакциям. Каждый столбец содержит список идентификаторов транзакций, в которых появляется элемент.
2. Инициализация: начните с набора отдельных элементов в качестве кандидатов на частые наборы элементов.
3. Подсчет поддержки: рассчитайте поддержку (частоту) каждого набора элементов-кандидатов путем пересечения идентификаторов транзакций составляющих его элементов. Этот процесс включает в себя сравнение вертикальных списков элементов и поиск общих идентификаторов транзакций.
4. Сокращение: удалите наборы элементов-кандидатов, которые не соответствуют минимальному порогу поддержки. Сокращение помогает сократить пространство поиска и фокусируется на релевантных наборах элементов.
5. Генерация новых кандидатов: создавайте новые наборы элементов-кандидатов, объединяя часто встречающиеся наборы элементов из предыдущей итерации. Процесс объединения включает в себя слияние вертикальных списков элементов в наборах элементов.
6. Повторяйте шаги с 3 по 5: продолжайте поддерживать подсчет, сокращение и генерацию кандидатов, пока не будут найдены новые часто встречающиеся наборы элементов.

Основные концепции:

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

Пример кода на Python с объяснением:

from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import eclat

# Sample transaction dataset
dataset = [['Apple', 'Banana', 'Egg'],
           ['Banana', 'Egg', 'Milk'],
           ['Apple', 'Banana'],
           ['Banana', 'Milk']]

# Convert dataset to one-hot encoded format
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

# Mining frequent itemsets using Eclat
frequent_itemsets = eclat(df, min_support=0.3, use_colnames=True)

# Display the frequent itemsets
print(frequent_itemsets)

В этом фрагменте кода мы сначала импортируем необходимые библиотеки. Затем мы определяем образец набора данных транзакций, представленный списком dataset списков.

Затем мы выполняем горячее кодирование набора данных, используя TransactionEncoder из модуля mlxtend.preprocessing. На этом этапе набор данных преобразуется в двоичное матричное представление, где каждый столбец соответствует элементу, а каждая строка представляет транзакцию.

После этого мы создаем DataFrame, используя матрицу с горячим кодированием, назначая имена столбцов на основе уникальных элементов в наборе данных.

Затем мы применяем алгоритм Eclat, используя функцию eclat() из модуля mlxtend.frequent_patterns. Мы указываем минимальный порог поддержки как 0.3 и устанавливаем use_colnames=True, чтобы использовать имена элементов в результирующих частых наборах элементов.

Наконец, мы печатаем наборы часто встречающихся элементов, полученные с помощью алгоритма Eclat.

Преимущества:

1. Масштабируемость: Eclat хорошо масштабируется и эффективен, особенно для больших наборов данных, благодаря вертикальному представлению данных и подходу, основанному на пересечении.
2. Эффективность использования памяти. Вертикальное представление данных требует меньше памяти по сравнению с другими алгоритмами, использующими горизонтальное представление, что делает Eclat подходящим для сред с ограниченным объемом памяти.
3. Простая интерпретация: Eclat предоставляет интерпретируемые результаты в виде частых наборов элементов, которые позволяют получать ценную информацию и обнаруживать закономерности в наборах данных о транзакциях.

Однако у Eclat также есть ограничения:

Ограничения:

1. Ограничено частыми наборами элементов: Eclat фокусируется исключительно на частых наборах элементов и не предоставляет информацию о нечастых или редких наборах элементов, которые могут по-прежнему содержать важную информацию.
2. Высокое использование памяти для разреженных наборов данных. В случаях, когда набор транзакционных данных является разреженным, вертикальное представление может по-прежнему потреблять значительный объем памяти, что влияет на производительность алгоритма.

Заключение:

Eclat — это мощный алгоритм для извлечения частых наборов элементов из наборов транзакционных данных. Его использование вертикального представления данных и подхода, основанного на пересечении, обеспечивает эффективный и масштабируемый анализ шаблонов. Используя Eclat, аналитики и специалисты по данным могут обнаруживать скрытые связи и зависимости в транзакционных данных, получая ценную информацию для различных приложений, таких как анализ потребительской корзины, системы рекомендаций и анализ поведения клиентов. Хотя у Eclat есть свои ограничения, его способность эффективно обрабатывать большие наборы данных и предоставлять интерпретируемые результаты делает его ценным инструментом в области неконтролируемого обучения и анализа шаблонов.