ML | ECLAT алгоритм
Предпосылки: алгоритм априори
Алгоритм ECLAT означает кластеризацию классов эквивалентности и обход решетки снизу вверх. Это один из популярных методов майнинга правил ассоциации. Это более эффективная и масштабируемая версия алгоритма Apriori. В то время как алгоритм Apriori работает по горизонтали, имитируя поиск в ширину графа, алгоритм ECLAT работает по вертикали, как и поиск в глубину графа. Этот вертикальный подход алгоритма ECLAT делает его более быстрым алгоритмом, чем алгоритм Apriori.
Как работает алгоритм? :
Основная идея состоит в том, чтобы использовать пересечения наборов идентификаторов транзакций (tidsets) для вычисления поддерживающего значения кандидата и предотвращения создания подмножеств, которые не существуют в дереве префиксов. При первом вызове функции используются все отдельные элементы вместе с их наборами элементов. Затем функция вызывается рекурсивно, и в каждом рекурсивном вызове каждая пара элемент-набор-набор проверяется и комбинируется с другими парами элемент-набор-набор. Этот процесс продолжается до тех пор, пока никакие пары-кандидаты-элемент-набор не могут быть объединены.
Давайте теперь разберемся с изложенным выше на примере: -
Рассмотрим следующую запись транзакции: -
Приведенные выше данные представляют собой логическую матрицу, где для каждой ячейки (i, j) значение указывает, включен ли j-й элемент в i-ю транзакцию или нет. 1 означает истину, а 0 означает ложь.
Теперь мы вызываем функцию в первый раз и располагаем каждый элемент с его набором элементов в табличной форме: -
k = 1, минимальная опора = 2
| Пункт | Tidset |
|---|---|
| Хлеб | {T1, T4, T5, T7, T8, T9} |
| Масло | {T1, T2, T3, T4, T6, T8, T9} |
| Молоко | {T3, T5, T6, T7, T8, T9} |
| Кокс | {T2, T4} |
| Варенье | {T1, T8} |
Теперь мы рекурсивно вызываем функцию до тех пор, пока больше не удастся объединить пары элемент-набор данных: -
k = 2
| Пункт | Tidset |
|---|---|
| {Хлеб, Масло} | {T1, T4, T8, T9} |
| {Хлеб, Молоко} | {T5, T7, T8, T9} |
| {Хлеб, Кола} | {T4} |
| {Хлеб, Джем} | {T1, T8} |
| {Сливочное масло, молоко} | {T3, T6, T8, T9} |
| {Сливочное масло, кока-кола} | {T2, T4} |
| {Масло, Джем} | {T1, T8} |
| {Молоко, Джем} | {T8} |
k = 3
| Пункт | Tidset |
|---|---|
| {Хлеб, Масло, Молоко} | {T8, T9} |
| {Хлеб, Масло, Джем} | {T1, T8} |
к = 4
| Пункт | Tidset |
|---|---|
| {Хлеб, Масло, Молоко, Джем} | {T8} |
Мы останавливаемся на k = 4, потому что больше нет пар элемент-набор данных для объединения.
Поскольку минимальная поддержка = 2, мы заключаем следующие правила из данного набора данных: -
| Купленные товары | Рекомендуемые продукты |
|---|---|
| Хлеб | Масло |
| Хлеб | Молоко |
| Хлеб | Варенье |
| Масло | Молоко |
| Масло | Кокс |
| Масло | Варенье |
| Хлеб и масло | Молоко |
| Хлеб и масло | Варенье |
Преимущества перед алгоритмом Apriori: -
- Требования к памяти: поскольку алгоритм ECLAT использует подход поиска в глубину, он использует меньше памяти, чем алгоритм Apriori.
- Скорость: алгоритм ECLAT обычно быстрее, чем алгоритм Apriori.
- Количество вычислений: алгоритм ECLAT не включает повторное сканирование данных для вычисления индивидуальных значений поддержки.
Внимание компьютерщик! Укрепите свои основы с помощью базового курса программирования Python и изучите основы.
Для начала подготовьтесь к собеседованию. Расширьте свои концепции структур данных с помощью курса Python DS. А чтобы начать свое путешествие по машинному обучению, присоединяйтесь к курсу Машинное обучение - базовый уровень.