Изчисляване от Правилата за асоцииране - ppt изтегляне
Изчисляване на правила за асоцииране Лекция в хранилището на данни и копаенето
Съдържание Въведение: Произход, номенклатура Apriori: основен алгоритъм Йерархични елементи Количествено оценени елементи Правила за асоцииране в 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 Йерархия Количествен алгоритъм Apriori Откриване на правила за асоцииране, които могат да бъдат разделени на два проблема. Намерете всички набори от предмети с минимална поддръжка Използвайте тези набори от предмети, за да определите Правилата за асоцииране Правила за асоцииране
Намиране на набори от елементи Намиране на всички набори с минимална поддръжка Въведение Априорна йерархия Количество Намиране на набори от предмети Намиране на всички набори от елементи с минимална поддръжка Започнете с едноелементни набори (1-набори) -> просто "преброяване" Комбинирайте определените (k-1) набори в нови k-набори Стъпка за присъединяване: Създаване на кандидатите Стъпка за подрязване: Изтриване на всички кандидати, които имат „грешна“ подгрупа правила за асоцииране
Пример: Набори артикули Пример: 3-сета кандидати за 4-сета Въведение Apriori йерархия Количество Пример: Елементи набори Пример: 3-сета кандидати за 4-сета Присъединете се към Prune 4-сета Правила за асоцииране
Поколение Генериране на правила за асоцииране Въведение Apriori Йерархия Количество Поколение Генериране на правила за асоцииране Проверка на всички подмножества a на елемент, зададен I a (I - a), ако Поддръжка (I) Поддръжка (a)> = minconf Правила за асоцииране
Пример: Генериране на въвеждане априорна йерархия, количество Пример: Поколение I = [40%] Подмножества: minconf = 75% Поддръжка (I) = 40% Поддръжка (a) = 50% Увереност = 80% ОК! Подкрепа (I) = 40% Поддръжка (a) = 80% доверие = 50% НЕ! Правила за асоцииране
Въведение Apriori Йерархия Количество Въведение Досега: Мляко Хляб [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 Йерархия Количество Въведение Досега: само "двоични" правила за асоцииране напр. Хляб Разширение на млякото до „количествени“ правила за асоцииране, напр. Rules Правила за асоцииране
Проблеми Тривиално преобразуване на стойността, зададена в двоична таблица, НО: Въведение априорно количество на йерархията Проблеми Тривиално преобразуване на стойност, зададена в двоична таблица, НО: Експлодира номерът на артикула (време за изпълнение!) Брой правила експлодира Правила на асоцииране
Модифициран алгоритъм на интервали: Въведение Apriori Йерархия Количество Интервали Модифициран алгоритъм: Интервал е избран за всеки атрибут количество Правила за асоцииране
Избор на интервали Проблем с избора на интервал: Въведение Количество на йерархията на Apriori Избор на интервали Проблем с избора на интервал: твърде много комбинации от интервали Въвеждане на частична пълнота: мярка за загубата на информация при обобщаване на интервал Правила за асоцииране
Частична пълнота k-Частична пълнота: Въведение Apriori Йерархия Количество Частична пълнота k-Частична пълнота: За обобщаването на набор от артикули подкрепата не трябва да се увеличава с повече от фактор k 1,5-Частична цялост: 5% 6% 8% 5% 6 % 6% 8% 6% Правила за асоцииране
Намаляване на AR Изтриване на "очакваните" правила за асоцииране Въведение Количество йерархия на Apriori Намаляване на AR Изтриване на "очакваните" правила на асоцииране 12x 3x -> 8% поддръжка, 70% доверие -> 2% поддръжка, 70% доверие Може да бъде изтрито, тъй като няма ново откритие Правила за асоцииране
Алгоритъм за перспективи на apriori за йерархия на Apriori „apriori“: оптимизирани версии с по-бързо изпълнение или с по-малко изисквания за памет