Алгоритъм за растеж на често срещания модел (FP) в извличането на данни

frequent pattern growth algorithm data mining

Подробен урок за алгоритъма за чест растеж на модела, който представлява базата данни във формата FP дърво. Включва сравнение на FP Growth Vs Apriori:

Алгоритъм на Apriori беше обяснено подробно в предишния ни урок. В този урок ще научим за Честия растеж на модела - FP Growth е метод за добив на чести набори от предмети.

какво е 7z файл?

Както всички знаем, Apriori е алгоритъм за често копаене на шаблони, който се фокусира върху генерирането на набори от предмети и откриването на най-често срещания набор от предмети. Това значително намалява размера на набора от елементи в базата данни, но Apriori също има свои собствени недостатъци.

Прочетете нашите Цяла серия за обучение по извличане на данни за пълно познаване на концепцията.

Какво ще научите:

• Недостатъци на алгоритъма на Apriori
• Алгоритъм за чест растеж на модела
• FP дърво
• Чести стъпки от алгоритъма на модела
• Пример за алгоритъм за растеж на FP
• Предимства на алгоритъма за растеж на FP
• Недостатъци на алгоритъма за растеж на FP
• Растеж на FP срещу Apriori
• ECLAT
• Заключение
• Препоръчително четене

Недостатъци на алгоритъма на Apriori

1. Използването на Apriori се нуждае от поколение набори от кандидати. Тези набори от елементи може да са големи, ако наборът от елементи в базата данни е огромен.
2. Apriori се нуждае от множество сканирания на базата данни, за да провери поддръжката на всеки генериран набор от елементи и това води до високи разходи.

Тези недостатъци могат да бъдат преодолени с помощта на алгоритъма за растеж на FP.

Алгоритъм за чест растеж на модела

Този алгоритъм е подобрение на метода на Apriori. Генерира се чест модел, без да е необходимо генериране на кандидати. Алгоритъмът за растеж на FP представлява базата данни под формата на дърво, наречено често дърво на шаблона или FP дърво.

Тази дървовидна структура ще поддържа връзката между наборите елементи. Базата данни е фрагментирана с помощта на един чест елемент. Тази фрагментирана част се нарича „фрагмент от шаблон“. Анализират се наборите от тези фрагментирани модели. По този начин с този метод търсенето на чести набори от предмети се намалява сравнително.

FP дърво

Дървото на честите образци е дървовидна структура, която се прави с първоначалните набори от елементи на базата данни. Целта на FP дървото е да добие най-често срещания модел. Всеки възел на FP дървото представлява елемент от набора от елементи.

Коренният възел представлява нула, докато долните възли представляват наборите елементи. Асоциацията на възлите с долните възли, която е наборите от предмети, се поддържа, докато се формира дървото.

Чести стъпки от алгоритъма на модела

Методът за често нарастване на модела ни позволява да намерим честия модел без генериране на кандидати.

Нека да видим стъпките, следвани за копаене на честия модел, използвайки алгоритъм за често нарастване на модела:

# 1) Първата стъпка е да сканирате базата данни, за да намерите появите на наборите от елементи в базата данни. Тази стъпка е същата като първата стъпка на Apriori. Броят на наборите от 1 артикул в базата данни се нарича брой на поддръжката или честота на набора от 1 артикул.

# две) Втората стъпка е да се изгради FP дървото. За това създайте корена на дървото. Коренът е представен с null.

# 3) Следващата стъпка е да сканирате базата данни отново и да разгледате транзакциите. Разгледайте първата транзакция и разберете елемента в нея. Наборът с максимален брой се взема отгоре, следващият с по-малък брой и така нататък. Това означава, че клонът на дървото е конструиран с набори от елементи на транзакции в низходящ ред на броя.

# 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

кой е най-добрият безплатен изтеглящ YouTube

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 Tree е по-тромав и труден за изграждане от Apriori.
2. Може да е скъпо.
3. Когато базата данни е голяма, алгоритъмът може да не се побере в споделената памет.

Растеж на FP срещу Apriori

ECLAT

Горният метод, растеж на Apriori и FP, добива чести набори от елементи, използвайки хоризонтален формат на данните. ECLAT е метод за извличане на чести набори от елементи, използвайки вертикалния формат на данните. Той ще трансформира данните в хоризонтален формат на данните във вертикален формат.

Например,Използване на растежа на Apriori и FP:

ECLAT ще има формата на таблицата като:

Този метод ще формира 2-itemsets, 3 itemsets, k itemsets във вертикалния формат на данните. Този процес с k се увеличава с 1, докато не бъдат намерени кандидат-набори от артикули. Някои техники за оптимизация като дифсет се използват заедно с Apriori.

Този метод има предимство пред Apriori, тъй като не изисква сканиране на базата данни, за да се намери поддръжката на k + 1 артикули. Това е така, защото наборът от транзакции ще съдържа броя на появата на всеки елемент в транзакцията (поддръжка). Тесното място идва, когато има много транзакции, отнемащи огромна памет и изчислително време за пресичане на множествата.

Заключение

Алгоритъмът Apriori се използва за правила за асоцииране на майнинг. Той работи на принципа, „непразните подмножества на честите набори от предмети също трябва да са чести“. Той формира k-itemset кандидати от (k-1) набори от елементи и сканира базата данни, за да намери честите набори от предмети.

Алгоритъмът за чест растеж на модела е методът за намиране на чести модели без генериране на кандидати. Той конструира FP дърво, вместо да използва стратегията за генериране и тестване на Apriori. Фокусът на алгоритъма за растеж на FP е върху фрагментирането на пътищата на елементите и извличането на чести модели.

Надяваме се, че тези уроци от серията Data Mining обогатиха вашите познания за Data Mining !!

въпроси за интервю за javascript за опитни професионалисти

PREV Урок | ПЪРВИ Урок

Препоръчително четене

• Техники за извличане на данни: Алгоритъм, методи и най-добрите инструменти за извличане на данни
• Apriori алгоритъм в извличането на данни: внедряване с примери
• Примери за алгоритъм на дървото на решенията в извличането на данни
• Примери за извличане на данни: Най-често срещаните приложения за извличане на данни 2021
• Извличане на данни: процес, техники и основни проблеми при анализа на данни
• Процес на извличане на данни: включени модели, стъпки и предизвикателства
• Модел за изпит за сертифициране на изпит за сертифициране на CSTE
• Извличане на данни срещу машинно обучение срещу изкуствен интелект срещу дълбоко обучение