apriori algorithm data mining
Поглиблений навчальний посібник з алгоритму Apriori для виявлення частих наборів предметів у видобутку даних. Цей посібник пояснює кроки в апріорі та як це працює:
У цьому Серія підручників з обробки даних , ми подивились Алгоритм дерева рішень у нашому попередньому уроці.
Існує кілька методів видобутку даних, таких як асоціація, кореляція, класифікація та кластеризація.
яке найкраще видалення вірусів -
Цей підручник головним чином зосереджений на майнінгу з використанням правил асоціації. За правилами асоціації ми ідентифікуємо набір елементів або атрибутів, які зустрічаються разом у таблиці.
Що ви дізнаєтесь:
- Що таке набір предметів?
- Чому часто видобуток наборів предметів?
- Методи підвищення ефективності апріорі
- Застосування алгоритму Апріорі
- Висновок
Що таке набір предметів?
Сукупність предметів разом називається набором предметів. Якщо будь-який набір елементів має k-елементи, він називається k-набором предметів. Набір предметів складається з двох або більше елементів. Часто зустрічається набір елементів називається частим набором предметів. Таким чином, частий видобуток наборів елементів - це техніка видобутку даних для ідентифікації елементів, які часто трапляються разом.
Наприклад , Хліб та масло, ноутбуки та антивірусні програми тощо.
Що таке найчастіший набір предметів?
Набір елементів називається частим, якщо він відповідає мінімальному пороговому значенню підтримки та впевненості. Підтримка відображає транзакції з предметами, придбаними разом в одній транзакції. Довіра показує операції, коли предмети купуються одна за одною.
Для частого методу видобутку елементів набору ми розглядаємо лише ті транзакції, які відповідають мінімальним вимогам щодо підтримки та довіри. Статистика цих алгоритмів майнінгу пропонує масу переваг, зниження витрат та покращення конкурентних переваг.
Існує час компромісу для видобутку даних та обсягу даних для частого видобутку. Частий алгоритм видобутку - це ефективний алгоритм для видобування прихованих зразків наборів предметів за короткий час і менше споживання пам'яті.
Часте видобуток шаблонів (FPM)
Алгоритм частого аналізу шаблонів є одним з найважливіших методів аналізу даних для виявлення взаємозв’язків між різними елементами набору даних. Ці відносини представлені у формі правил асоціації. Це допомагає виявити порушення в даних.
FPM має багато додатків у галузі аналізу даних, помилок програмного забезпечення, перехресного маркетингу, аналізу кампаній продажу, аналізу кошика ринку тощо.
Часті набори предметів, виявлені через Apriori, мають багато додатків у завданнях інтелектуального аналізу даних. Такі завдання, як пошук цікавих зразків у базі даних, з'ясування послідовності та видобуток правил асоціацій є найважливішими з них.
Правила асоціації застосовуються до даних транзакцій супермаркету, тобто для вивчення поведінки клієнтів з точки зору придбаних товарів. Правила асоціації описують, як часто предмети купуються разом.
Правила асоціації
Видобуток правил асоціації визначається як:
“Нехай I = {…} - це набір‘ n ’двійкових атрибутів, що називаються елементами. Нехай D = {….} - набір транзакцій, що називається базою даних. Кожна транзакція в D має унікальний ідентифікатор транзакції і містить підмножину елементів у I. Правило визначається як імплікація форми X-> Y де X, Y? Я і X? Y = ?. Сукупність елементів X та Y називаються попередніми та наслідками правила відповідно. '
Вивчення правил асоціації використовується для пошуку зв’язків між атрибутами у великих базах даних. Правило асоціації, A => B, матиме вигляд 'для набору транзакцій деяке значення набору елементів A визначає значення набору елементів B за умови, що забезпечується мінімальна підтримка та довіра'.
Підтримку та впевненість можна представити на наступному прикладі:
Bread=> butter (support=2%, confidence-60%)Наведене вище твердження є прикладом правила асоціації. Це означає, що є 2% операція, яка купує хліб і масло разом, і є 60% клієнтів, які купують хліб, а також масло.
Підтримка та впевненість для наборів елементів A та B представлені формулами:
Майнінг правил асоціації складається з 2 етапів:
- Знайдіть усі найпоширеніші набори предметів.
- Створіть правила асоціації з вищезазначених частих наборів предметів.
Чому часто видобуток наборів предметів?
Частий набір елементів або вибірка шаблонів широко використовується через його широке застосування в правилах асоціації майнінгу, обмеженнях кореляцій та графіків, що базується на частих шаблонах, послідовних шаблонах та багатьох інших завданнях з видобутку даних.
Алгоритм Апріорі - Алгоритми частого малюнка
Алгоритм Apriori був першим алгоритмом, який був запропонований для частого видобутку наборів предметів. Пізніше його вдосконалили Р. Агарвал та Р. Шрікант і став відомим як Апріорі. Цей алгоритм використовує два етапи “приєднання” та “обрізання” для зменшення простору пошуку. Це ітераційний підхід до виявлення найпоширеніших наборів предметів.
Апріорі каже:
Ймовірність того, що пункт I не часто зустрічається, є, якщо:
- P (I)
- P (I + A)
- Якщо набір елементів має значення менше мінімальної підтримки, тоді всі його набори також опускатимуться нижче мінімальної підтримки, і, отже, їх можна ігнорувати. Ця властивість називається властивістю Антимонотон.
- P (I + A)
Етапи, які виконуються в Apriori Algorithm для видобування даних, такі:
- Приєднуйтесь до кроку : Цей крок генерує (K + 1) набір предметів з наборів K-об’єктів, об’єднуючи кожен елемент із собою.
- Крок чорносливу : Цей крок сканує кількість кожного елемента в базі даних. Якщо позиція кандидата не відповідає мінімальній підтримці, вона вважається рідкісною, і, таким чином, її видаляють. Цей крок виконується для зменшення розміру наборів кандидатів.
Сходинки в апріорі
Алгоритм Апріорі - це послідовність кроків, яких слід дотримуватися, щоб знайти найчастіший набір елементів у даній базі даних. Ця техніка видобутку даних послідовно повторює кроки з’єднання та обрізки, поки не буде досягнуто найчастіший набір елементів. У проблемі вказано мінімальний поріг підтримки або він передбачається користувачем.
# 1) На першій ітерації алгоритму кожен предмет приймається як кандидат набору з 1 предмета. Алгоритм буде рахувати випадки появи кожного елемента.
# два) Нехай буде якась мінімальна підтримка, min_sup (наприклад, 2). Визначається набір 1 - наборів предметів, поява яких задовольняє мінімальну суму. Тільки тих кандидатів, які рахують більше або дорівнює min_sup, приймають на наступну ітерацію, а інших обрізають.
# 3) Далі виявляються часті предмети з набором min_sup із набором предметів. Для цього на етапі об’єднання набір із 2 елементів формується шляхом формування групи з 2 шляхом комбінування елементів із собою.
# 4) Кандидати з 2 елементів обрізаються з використанням порогового значення min-sup. Тепер у таблиці буде 2 –імсети з мінімальною сумою.
# 5) Наступна ітерація сформує 3 –імсети, використовуючи крок об’єднання та обрізки. Ця ітерація буде слідувати властивості антимонотону, коли підмножини 3-наборів елементів, тобто 2-підмножини підгруп кожної групи, потрапляють у min_sup. Якщо всі підмножини з 2 елементів є частими, тоді надмножина буде частою, інакше вона буде обрізана.
# 6) Наступним кроком буде наступне створення набору 4-елементів, з'єднавши 3-набір елементів із собою та обрізання, якщо його підмножина не відповідає критеріям min_sup. Алгоритм зупиняється, коли досягається найчастіший набір елементів.
(зображення джерело )
Приклад апріорі:Поріг підтримки = 50%, впевненість = 60%
ТАБЛИЦЯ-1
| Транзакція | Перелік предметів |
|---|---|
| Т1 | I1, I2, I3 |
| Т2 | I2, I3, I4 |
| T3 | I4, I5 |
| T4 | I1, I2, I4 |
| Т5 | I1, I2, I3, I5 |
| Т6 | I1, I2, I3, I4 |
Рішення:
Поріг підтримки = 50% => 0,5 * 6 = 3 => min_sup = 3
1. Кількість кожного предмета
ТАБЛИЦЯ-2
| Елемент | Рахувати |
|---|---|
| I1 | 4 |
| I2 | 5 |
| I3 | 4 |
| I4 | 4 |
| I5 | два |
2. Крок чорносливу: ТАБЛИЦЯ -2 показує, що елемент I5 не відповідає min_sup = 3, таким чином він видаляється, лише I1, I2, I3, I4 відповідає min_sup count.
ТАБЛИЦЯ-3
| Елемент | Рахувати |
|---|---|
| I1 | 4 |
| I2 | 5 |
| I3 | 4 |
| I4 | 4 |
3. Приєднуйтесь до кроку: Форма 2-позиційного набору. Від ТАБЛИЦЯ-1 з'ясувати випадки набору 2 предметів.
ТАБЛИЦЯ-4
| Елемент | Рахувати |
|---|---|
| I1, I2 | 4 |
| I1, I3 | 3 |
| I1, I4 | два |
| I2, I3 | 4 |
| I2, I4 | 3 |
| I3, I4 | два |
Чотири. Крок чорносливу: ТАБЛИЦЯ -4 показує, що набір елементів {I1, I4} та {I3, I4} не відповідає min_sup, тому він видаляється.
ТАБЛИЦЯ-5
| Елемент | Рахувати |
|---|---|
| I1, I2 | 4 |
| I1, I3 | 3 |
| I2, I3 | 4 |
| I2, I4 | 3 |
5. Приєднуйтесь та обрізайте крок: 3-позиційна форма. Від ТАБЛИЦЯ - 1 з'ясувати випадки 3-позиційного набору. Від ТАБЛИЦЯ-5 , знайдіть підмножини з 2 елементів, які підтримують min_sup.
Ми можемо бачити для підмножин елементів {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3}, що трапляються в ТАБЛИЦЯ-5 таким чином, {I1, I2, I3} є частим явищем.
Ми можемо бачити, що підмножини елементів {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} не є частими, оскільки це не відбувається в ТАБЛИЦЯ-5 таким чином {I1, I2, I4} не є частим, тому його видаляють.
ТАБЛИЦЯ-6
| Елемент |
|---|
| I1, I2, I3 |
| I1, I2, I4 |
| I1, I3, I4 |
| I2, I3, I4 |
Часті лише {I1, I2, I3} .
6. Сформувати правила асоціації: З частих наборів предметів, виявлених вище, може бути:
{I1, I2} => {I3}
Впевненість = підтримка {I1, I2, I3} / підтримка {I1, I2} = (3/4) * 100 = 75%
{I1, I3} => {I2}
Впевненість = підтримка {I1, I2, I3} / підтримка {I1, I3} = (3/3) * 100 = 100%
{I2, I3} => {I1}
Впевненість = підтримка {I1, I2, I3} / підтримка {I2, I3} = (3/4) * 100 = 75%
{I1} => {I2, I3}
Впевненість = підтримка {I1, I2, I3} / підтримка {I1} = (3/4) * 100 = 75%
{I2} => {I1, I3}
Впевненість = підтримка {I1, I2, I3} / підтримка {I2 = (3/5) * 100 = 60%
{I3} => {I1, I2}
Впевненість = підтримка {I1, I2, I3} / підтримка {I3} = (3/4) * 100 = 75%
найкраще програмне забезпечення для завантаження відео YouTube
Це показує, що всі вищезазначені правила асоціації є сильними, якщо мінімальний поріг довіри становить 60%.
Алгоритм Апріорі: Псевдокодекс
C: Набір предметів-кандидатів розміром k
L: Часті набори елементів розміром k
(зображення джерело )
Переваги
- Легко зрозумілий алгоритм
- Кроки Join і Prune легко реалізувати на великих наборах предметів у великих базах даних
Недоліки
- Це вимагає великих обчислень, якщо набори елементів дуже великі, а мінімальна підтримка дуже низька.
- Потрібно відсканувати всю базу даних.
Методи підвищення ефективності апріорі
Для підвищення ефективності алгоритму доступно багато методів.
- Техніка на основі хешу: Цей метод використовує структуру на основі хешу, яка називається хеш-таблицею, для генерації наборів елементів k та відповідного їм підрахунку. Він використовує хеш-функцію для створення таблиці.
- Зниження трансакції: Цей метод зменшує кількість сканування транзакцій в ітераціях. Операції, які не містять частих предметів, позначаються або видаляються.
- Розбиття: Цей метод вимагає лише двох сканувань бази даних для видобування частих наборів предметів. Там сказано, що для того, щоб будь-який набір елементів був потенційно частим у базі даних, він повинен бути частим хоча б в одному з розділів бази даних.
- Відбір проб: Цей метод відбирає випадкову вибірку S з бази даних D, а потім здійснює пошук частого набору предметів у S. Можливо, можливо втратити загальний набір частин. Це можна зменшити, знизивши min_sup.
- Динамічний підрахунок наборів елементів: Ця техніка може додавати нові набори кандидатів у будь-яку позначену початкову точку бази даних під час сканування бази даних.
Застосування алгоритму Апріорі
Деякі поля, де використовується Apriori:
- В освітній галузі: Витяг правил асоціації при аналізі даних студентів, що приймаються, за характеристиками та спеціальностями.
- У галузі медицини: Наприклад, аналіз бази даних пацієнта.
- У лісовому господарстві: Аналіз ймовірності та інтенсивності лісової пожежі з даними лісової пожежі.
- Apriori використовується багатьма компаніями, такими як Amazon Рекомендаційна система і Google за функцію автозаповнення.
Висновок
Алгоритм Apriori - це ефективний алгоритм, який сканує базу даних лише один раз.
Це значно зменшує розмір наборів елементів у базі даних, забезпечуючи хорошу продуктивність. Таким чином, видобуток даних допомагає споживачам та галузям краще у процесі прийняття рішень.
Перегляньте наш майбутній підручник, щоб дізнатися більше про Алгоритм частого зростання шаблону !!
НАЗАД Підручник | НАСТУПНИЙ підручник
Рекомендована література
- Методи видобутку даних: алгоритм, методи та найпопулярніші інструменти видобування даних
- Видобуток даних: процес, методи та основні проблеми аналізу даних
- Приклади інтелектуального аналізу даних: Найпоширеніші програми інтелектуального аналізу даних 2021
- Приклади алгоритму дерева рішень у видобутку даних
- Процес видобутку даних: задіяні моделі, етапи процесу та виклики
- Видобуток даних проти машинного навчання проти штучного інтелекту проти глибокого навчання
- 15 найкращих безкоштовних інструментів для видобутку даних: найповніший список
- Параметризація даних JMeter за допомогою користувацьких змінних