Розрахунок за правилами асоціації - ppt завантажити
Розрахунок правил асоціації Лекція у сховищі даних та видобутку корисних копалин
Зміст Вступ: Походження, номенклатура Апріорі: базовий алгоритм Ієрархічні елементи Кількісно визначені елементи Правила асоціації Outlook
Вступ Створення апріорної ієрархії, кількості Вступ Створення більших наборів даних, точніших наборів даних, кращих апаратних ресурсів
Номенклатура транзакцій: Дія з базою даних (закупівля.) Вступ Ієрархія Apriori, кількість. Номенклатурна операція: Дія з базою даних (закупівля.) Пункт: Частина транзакції (молоко.) Набір предметів: Кількість предметів Правило асоціації: X Y (якщо транзакція містить X, тоді він також містить Y) Довіра c: c% транзакцій підкоряється Правилам асоціації (minconf: нижня межа для алгоритму) Підтримка s: s% транзакцій містять X та Y (minsup: нижня межа для алгоритму) Правила асоціації
Приклад T1 T2 Вступ Apriori Ієрархія Кількість Приклад T1 T2 T3 T4 T5 Довіра Підтримка Хліб Сир 100% 40% Сир Молоко 66,6% 40% Зубна паста Шоколад 50% 20% Правила асоціації
Вступ Ієрархія Apriori Кількість Мотивація Бажання машинного розпізнавання цих Правил асоціації: Алгоритм 'Apriori' Деякі елементи мають основну залежність, ієрархічне походження (молоко незбиране молоко) Деякі правила асоціації потребують кількісних елементів (2 машини 2 діти старше 18 років) Правила асоціації
Вступ Apriori Hierarchy Quantity Algorithm Apriori Discovering Association Rules, які можна розділити на дві проблеми. Знайдіть усі набори предметів з мінімальною підтримкою Використовуйте ці набори елементів, щоб визначити Правила асоціації Правила асоціації
Знайти набори предметів Знайти всі набори предметів з мінімальною підтримкою Вступ Апріорна ієрархія Кількість Знайти набори предметів Знайти всі набори предметів з мінімальною підтримкою Почніть з наборів одноелементів (1-набори) -> простий "підрахунок" Об'єднайте визначені (k-1) набори в нові набори k Крок приєднання: Створення кандидатів Крок обрізки: Видалення всіх кандидатів, які мають "неправильну" підгрупу правил асоціації
Приклад: Набори елементів Приклад: 3-набори кандидатів для 4-наборів Вступ Apriori ієрархія Кількість Приклад: Набори елементів Приклад: 3-набори кандидатів на 4-набори Приєднуйтесь до обрізання 4-наборів Правила асоціації
Покоління Генерація правил асоціації Вступ Апріорі Ієрархія Кількість Генерація Генерація правил асоціації Перевірка всіх підмножин a набору елементів I a (I - a), якщо підтримка (I) Підтримка (a)> = minconf Правила асоціації
Приклад: Генерація вступної апріорної ієрархії, кількість Приклад: Покоління I = [40%] Підмножини: minconf = 75% Підтримка (I) = 40% Підтримка (a) = 50% Впевненість = 80% ОК! Підтримка (I) = 40% Підтримка (a) = 80% Впевненість = 50% НІ! Правила асоціації
Вступ Апріорі Ієрархія Кількість Вступ Поки що: Молоко Хліб [80%] буде набагато інформативнішим, якщо дієтичне молоко Білий Хліб [75%] побажає правил Асоціації Ієрархії
Приклад Чим глибше елемент знаходиться в ієрархії, тим більше ініціативна апріорна ієрархія, кількість, приклад, їжа, молоко, хліб. Дієта. Повно біле цільне зерно. Чим глибше елемент знаходиться в ієрархії, тим меншою необхідною підтримкою повинні бути Правила асоціації
Розширення кодування Apriori: Введення кількості ієрархії Apriori Розширення кодування Apriori: Кодування різних продуктів Молоко 1 Дієтичне молоко 11 Цільне молоко 12 Хліб 2 Білий хліб 21 Цільнозерновий хліб 22 Таблиця транзакцій: T1: T2:. Правила асоціації
Перші набори елементів Перший на верхньому рівні Пошук наборів елементів: Вступ апріорна ієрархія, кількість Перші набори елементів Перший на верхньому рівні, пошук наборів елементів: Розрахунок правил асоціації та фільтрація таблиці транзакцій 30% 40% 30% T1: T2: Правила асоціації
Вступ Ієрархія Apriori Кількість ітерацій Ітерація: пошук наступних наборів елементів у відфільтрованій таблиці (до порожньої таблиці або в кінці ієрархії) Розрахунок правил асоціації та фільтрація таблиці транзакцій 20% 30% 30% 20% 20% Правила асоціації
Вступ Поки що: лише "двійкові" Правила асоціації, наприклад, хліб молоко Кількість ієрархії Апріорі Вступ Поки що: лише "двійкові" Правила асоціації, наприклад, хліб Розширення молока до "кількісних" Правил асоціації, наприклад Правила асоціації
Проблеми Тривіальне перетворення значення, встановленого у двійкову таблицю, АЛЕ: Введення апріорної величини ієрархії Проблеми Тривіальне перетворення значення, встановленого у двійкову таблицю, АЛЕ: кількість елементів вибухає (час виконання!) Кількість правил вибухає Правила асоціації
Модифікований алгоритм інтервалів: Вступ Ієрархія Apriori Кількість Інтервали Модифікований алгоритм: Інтервал вибирається для кожного атрибута величини Правила асоціації
Вибір інтервалів Проблема з вибором інтервалу: Вступ Кількість ієрархії Апріорі Вибір інтервалів Проблема з вибором інтервалу: занадто багато комбінацій інтервалів Введення часткової повноти: міра втрати інформації при узагальненні інтервалу Правила асоціації
Часткова повнота k-Часткова повнота: Вступ Апріорі Ієрархія Кількість Часткова повнота k-Часткова повнота: Для узагальнення набору предметів підтримка не повинна збільшуватися більш ніж на коефіцієнт k 1,5-Частково-Повна: 5% 6% 8% 5% 6 % 6% 8% 6% Правила асоціації
Зменшення AR Видалення "очікуваних" правил асоціації Вступ Кількість ієрархії Apriori Зменшення AR Видалення "очікуваних" правил асоціації 12x 3x -> 8% підтримки, 70% впевненості -> 2% підтримки, 70% впевненості Можна видалити, оскільки немає нових знахідок Правила асоціації
Алгоритм перспективи прогнозування кількості ієрархій Apriori 'apriori': оптимізовані версії з більш швидким виконанням або з меншими вимогами до пам'яті ієрархічні елементи: не тільки знаходять правила асоціації на одному рівні, але й правила асоціації на різних рівнях