Алгоритм зростання частого зразка (FP) при видобутку даних

frequent pattern growth algorithm data mining

Детальний підручник з алгоритму частого зростання шаблону, який представляє базу даних у формі дерева FP. Включає порівняння зростання FP проти Apriori:

Апріорі Алгоритм було детально пояснено в нашому попередньому навчальному посібнику. У цьому підручнику ми дізнаємося про Часте зростання шаблонів - FP Growth - це метод видобутку частих наборів предметів.

Як відкрити торрент-файл у Windows -

Як ми всі знаємо, Apriori - це алгоритм частого видобутку шаблонів, який фокусується на генерації наборів предметів та виявленні найпоширеніших наборів елементів. Це значно зменшує розмір набору елементів у базі даних, однак у Apriori також є свої недоліки.

Прочитайте наш Весь навчальний цикл з обробки даних для повного знання концепції.

Що ви дізнаєтесь:

• Недоліки алгоритму Апріорі
• Алгоритм частого зростання
• Дерево FP
• Часті кроки з алгоритму зразків
• Приклад алгоритму зростання FP
• Переваги алгоритму зростання FP
• Недоліки алгоритму зростання FP
• Зростання FP проти Апріорі
• СВІТИТИ
• Висновок
• Рекомендована література

Недоліки алгоритму Апріорі

1. Використання Apriori потребує генерації наборів кандидатів. Кількість цих наборів може бути великою, якщо набір елементів у базі даних величезний.
2. Apriori потребує багаторазового сканування бази даних, щоб перевірити підтримку кожного згенерованого набору елементів, що призводить до великих витрат.

Ці недоліки можна подолати, використовуючи алгоритм зростання FP.

Алгоритм частого зростання

Цей алгоритм є вдосконаленням методу Апріорі. Частий шаблон формується без необхідності генерації кандидатів. Алгоритм зростання FP представляє базу даних у вигляді дерева, яке називається деревом частого шаблону або деревом FP.

Ця деревна структура буде підтримувати зв'язок між наборами предметів. База даних фрагментована за допомогою одного частого елемента. Ця фрагментована частина називається «фрагментом візерунка». Проаналізовано набори елементів цих фрагментованих моделей. Таким чином, за допомогою цього методу пошук частих наборів предметів порівняно зменшується.

Дерево FP

Дерево частого візерунка - це деревоподібна структура, яка створюється з початковими наборами елементів бази даних. Призначення дерева FP полягає у видобуванні найбільш частого шаблону. Кожен вузол дерева FP представляє елемент набору елементів.

Кореневий вузол представляє нуль, тоді як нижні вузли представляють набори елементів. Пов’язання вузлів з нижніми вузлами, що є наборами елементів, з іншими наборами елементів зберігається під час формування дерева.

Часті кроки з алгоритму зразків

Метод частого зростання моделей дозволяє нам знайти частий шаблон без генерації кандидатів.

Давайте подивимося кроки, які виконувались для видобування частого шаблону, використовуючи алгоритм частого зростання шаблону:

# 1) Першим кроком є ​​сканування бази даних, щоб знайти випадки наборів елементів у базі даних. Цей крок такий самий, як і перший крок Apriori. Кількість наборів 1 елемента в базі даних називається підтримкою або частотою набору 1 елемента.

# два) Другим кроком є ​​побудова дерева FP. Для цього створіть корінь дерева. Корінь представлений нулем.

# 3) Наступним кроком є ​​повторне сканування бази даних та перевірка транзакцій. Вивчіть першу транзакцію та з’ясуйте в ній набір предметів. Набір предметів з максимальним числом береться вгорі, наступний набір предметів з меншим числом тощо. Це означає, що гілка дерева будується з наборами елементів транзакцій у порядку зменшення кількості.

що таке план тестування в qa

# 4) Розглядається наступна транзакція в базі даних. Набори елементів впорядковані у порядку зменшення підрахунку. Якщо будь-який набір елементів цієї транзакції вже присутній в іншій гілці (наприклад, у 1-й транзакції), тоді ця гілка транзакції матиме спільний префікс до кореневої.

Це означає, що загальний набір елементів пов'язаний з новим вузлом іншого набору елементів у цій транзакції.

# 5) Крім того, підрахунок набору елементів збільшується, оскільки це відбувається в транзакціях. Як загальний вузол, так і кількість нових вузлів збільшуються на 1, коли вони створюються та зв’язуються відповідно до транзакцій.

# 6) Наступним кроком є ​​видобуток створеного дерева FP. Для цього спочатку досліджується найнижчий вузол разом із посиланнями найнижчих вузлів. Найнижчий вузол представляє довжину частотної картини 1. Від цього пройдіть шлях у дереві FP. Цей шлях або шляхи називаються умовною базою шаблонів.

База умовного шаблону - це підбаза даних, що складається із шляхів префіксу в дереві FP, що відбуваються з найнижчим вузлом (суфіксом).

# 7) Побудуйте умовне дерево FP, яке формується підрахунком наборів елементів у шляху. Набори елементів, що відповідають пороговій підтримці, розглядаються в Умовному дереві FP.

# 8) Часті шаблони генеруються з умовного дерева FP.

Приклад алгоритму зростання FP

Поріг підтримки = 50%, впевненість = 60%

Таблиця 1

Рішення:

Поріг підтримки = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Графа кожного предмета

Таблиця 2

2. Відсортуйте набір предметів за спаданням.

Таблиця 3

3. Побудувати дерево FP

1. Враховуючи кореневий вузол нулем.
2. Перше сканування транзакції T1: I1, I2, I3 містить три елементи: {I1: 1}, {I2: 1}, {I3: 1}, де I2 як дочірній зв’язаний з коренем, I1 пов’язаний з I2 та I3 пов'язаний з I1.
3. T2: I2, I3, I4 містить I2, I3 та I4, де I2 пов'язаний з коренем, I3 пов'язаний з I2, а I4 пов'язаний з I3. Але ця гілка поділяла б вузол I2 настільки ж загальний, як це вже використовується в T1.
4. Збільшення кількості I2 на 1 і I3 пов'язаний як дитина з I2, I4 пов'язаний як дитина з I3. Кількість становить {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Подібним чином, нова гілка з I5 пов'язана з I4, коли створюється дитина.
6. T4: I1, I2, I4. Послідовність буде I2, I1 та I4. I2 вже пов'язаний з кореневим вузлом, отже, він буде збільшений на 1. Подібним чином I1 буде збільшений на 1, оскільки він вже пов'язаний з I2 в T1, таким чином {I2: 3}, {I1: 2}, {I4: 1}.
7. T5: I1, I2, I3, I5. Послідовність буде I2, I1, I3 та I5. Таким чином, {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. Послідовність буде I2, I1, I3 та I4. Таким чином, {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

моє запитання та відповіді на співбесіду в

4. Видобуток FP-дерева узагальнено нижче:

1. Елемент найнижчого вузла I5 не розглядається, оскільки він не має мінімальної кількості підтримки, отже, його видаляють.
2. Наступний нижній вузол - I4. I4 зустрічається у 2 гілках, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Тому, розглядаючи I4 як суфікс, префіксними шляхами буде {I2, I1, I3: 1}, {I2, I3: 1}. Це формує умовну базу шаблону.
3. База умовного шаблону вважається базою даних транзакцій, будується FP-дерево. Він міститиме {I2: 2, I3: 2}, I1 не враховується, оскільки він не відповідає мінімальній кількості підтримки.
4. Цей шлях генерує всі комбінації частих шаблонів: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Для I3 шлях префіксу буде таким: {I2, I1: 3}, {I2: 1}, це генерує FP-дерево з 2 вузлами: {I2: 4, I1: 3} і генеруються часті шаблони: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Для I1 шлях до префіксу буде таким: {I2: 4} це генерує єдине вузол FP-дерева: {I2: 4} і формуються часті шаблони: {I2, I1: 4}.

Наведена нижче діаграма зображує умовне дерево FP, пов'язане з умовним вузлом I3.

Переваги алгоритму зростання FP

1. Цей алгоритм повинен сканувати базу даних лише двічі у порівнянні з Apriori, який сканує транзакції для кожної ітерації.
2. У цьому алгоритмі не виконується сполучення елементів, і це робить його швидшим.
3. База даних зберігається в компактній версії в пам'яті.
4. Це ефективно і масштабовано для видобутку як довгих, так і коротких частих шаблонів.

Недоліки алгоритму зростання FP

1. Дерево FP є громіздкішим і складнішим для побудови, ніж Apriori.
2. Це може коштувати дорого.
3. Коли база даних велика, алгоритм може не поміститися у спільній пам'яті.

Зростання FP проти Апріорі

СВІТИТИ

Вищевказаний метод, зростання Apriori та FP, видобуває часті набори предметів із використанням горизонтального формату даних. ECLAT - це метод видобування частих наборів предметів із використанням вертикального формату даних. Це перетворить дані у горизонтальному форматі у вертикальний формат.

Наприклад,Використання апріорі та РР:

ECLAT матиме формат таблиці як:

Цей метод формує 2-набір елементів, 3 набори елементів, k наборів елементів у вертикальному форматі даних. Цей процес з k збільшується на 1, поки не буде знайдено наборів кандидатів. Деякі методи оптимізації, такі як дифсет, використовуються разом з Apriori.

Цей метод має перевагу перед Apriori, оскільки не вимагає сканування бази даних, щоб знайти підтримку k + 1 наборів елементів. Це пов’язано з тим, що набір транзакцій буде містити кількість зустрічей кожного елемента в транзакції (підтримка). Вузьке місце виникає, коли багато транзакцій займають величезну пам’ять і обчислювальний час для перетину множин.

Висновок

Алгоритм Апріорі використовується для правил асоціації майнінгу. Це працює за принципом, 'непорожні підмножини частих наборів предметів також повинні бути частими'. Він формує кандидатів k-itemset із наборів елементів (k-1) та сканує базу даних, щоб знайти часті набори елементів.

Алгоритм частого зростання шаблону - це метод пошуку частих моделей без генерації кандидатів. Він створює дерево FP, а не використовує стратегію генерації та тестування Apriori. Фокус алгоритму FP Growth зосереджений на фрагментації шляхів до елементів та видобутку частих шаблонів.

Ми сподіваємось, що ці підручники з серії Data Mining збагатили ваші знання про Data Mining !!

НАЗАД Підручник | ПЕРШИЙ підручник

Рекомендована література

• Методи видобутку даних: алгоритм, методи та найпопулярніші засоби видобування даних
• Алгоритм Апріорі у видобутку даних: реалізація на прикладах
• Приклади алгоритму дерева рішень у видобутку даних
• Приклади інтелектуального аналізу даних: Найпоширеніші програми інтелектуального аналізу даних 2021
• Видобуток даних: процес, методи та основні проблеми аналізу даних
• Процес видобутку даних: задіяні моделі, етапи та виклики
• Шаблон запитань на сертифікаційний іспит для тестування програмного забезпечення CSTE
• Видобуток даних проти машинного навчання проти штучного інтелекту проти глибокого навчання