Меню

Apriori алгоритъм в извличането на данни: внедряване с примери

  • Основен
  • Други
  • Apriori алгоритъм в извличането на данни: внедряване с примери

apriori algorithm data mining

Опитайте Нашия Инструмент За Премахване На Проблемите

Подробен урок за алгоритъма на Apriori за откриване на чести набори от елементи в извличането на данни. Този урок обяснява стъпките в Apriori и как работи:

В това Поредица от уроци за извличане на данни , разгледахме Алгоритъм на дървото на решенията в предишния ни урок.

Има няколко метода за извличане на данни като асоцииране, корелация, класификация и клъстериране.

qa срещу qc при тестване на софтуер

Този урок се фокусира основно върху копаенето с помощта на правила за асоцииране. Чрез правила за асоцииране ние идентифицираме набора от елементи или атрибути, които се срещат заедно в таблица.

Алгоритъм на Apriori

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

Какво представлява артикулът?

Набор от елементи заедно се нарича елемент. Ако някой набор от елементи има k-елементи, той се нарича k-itemset. Наборът от елементи се състои от два или повече елемента. Набор от елементи, който се среща често, се нарича чест набор от предмети. По този начин честото извличане на елементи е техника за извличане на данни за идентифициране на елементите, които често се срещат заедно.

Например , Хляб и масло, Лаптоп и Антивирусен софтуер и др.

Какво е честият артикул?

Набор от елементи се нарича често, ако отговаря на минимална прагова стойност за подкрепа и увереност. Поддръжката показва транзакции с артикули, закупени заедно в една транзакция. Доверието показва транзакции, при които артикулите се купуват един след друг.

За чести методи за извличане на артикули, ние разглеждаме само тези транзакции, които отговарят на минималните изисквания за поддръжка и доверие. Статистика от тези алгоритми за добив предлага много предимства, намаляване на разходите и подобрено конкурентно предимство.

Има време за компромис, необходимо за добив на данни и обем от данни за често копаене. Честият алгоритъм за добив е ефективен алгоритъм за извличане на скритите модели на набори от елементи за кратко време и по-малко потребление на памет.

Копаене на чести образци (FPM)

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

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

Честите набори от елементи, открити чрез Apriori, имат много приложения в задачи за извличане на данни. Задачи като намиране на интересни модели в базата данни, установяване на последователност и извличане на правила за асоцииране е най-важната от тях.

Правилата за асоцииране се прилагат към данните за транзакциите в супермаркетите, т.е. за изследване на поведението на клиентите по отношение на закупените продукти. Правилата за асоцииране описват колко често предметите се купуват заедно.

Правила за асоцииране

Копаенето на правила за асоцииране се определя като:

„Нека I = {…} е набор от‘ n ’двоични атрибути, наречени елементи. Нека D = {….} Е набор от транзакция, наречена база данни. Всяка транзакция в D има уникален идентификатор на транзакция и съдържа подмножество от елементите в I. Правило се дефинира като импликация на форма X-> Y, където X, Y? I и X? Y = ?. Наборът от елементи X и Y се нарича съответно антецедент и следствие от правилото. '

Изучаването на правила за асоцииране се използва за намиране на връзки между атрибутите в големи бази данни. Правило за асоцииране, A => B, ще бъде под формата 'за набор от транзакции, някаква стойност на артикула A определя стойностите на артикула B при условието, при което са изпълнени минималната подкрепа и доверие'.

Подкрепата и доверието могат да бъдат представени от следния пример:

Bread=> butter (support=2%, confidence-60%)

Горното изявление е пример за правило за асоцииране. Това означава, че има 2% сделка, която е купувала хляб и масло заедно и има 60% от клиентите, които са купували хляб, както и масло.

Подкрепата и доверието за артикули А и Б са представени чрез формули:

Формула за подкрепа и увереност за артикули А и Б

Извличането на правила за асоцииране се състои от 2 стъпки:

  1. Намерете всички чести набори от предмети.
  2. Генерирайте правила за асоцииране от горните чести набори от предмети.

Защо често копаене на артикули?

Честото извличане на елементи или модели се използва широко поради широкото му приложение в правилата за асоцииране на добива, ограниченията и ограниченията на графичните модели, което се основава на чести модели, последователни модели и много други задачи за добив на данни.

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

Алгоритъмът Apriori беше първият алгоритъм, който беше предложен за често копаене на артикули. По-късно беше подобрен от R Agarwal и R Srikant и стана известен като Apriori. Този алгоритъм използва две стъпки „присъединяване“ и „подрязване“, за да намали пространството за търсене. Това е итеративен подход за откриване на най-честите набори от предмети.

Априори казва:

Вероятността елемент I да не е чест е, ако:

  • P (I)
  • P (I + A)
  • Ако набор от елементи има стойност по-малка от минималната поддръжка, тогава всички негови суперсетове също ще паднат под минималната поддръжка и по този начин могат да бъдат игнорирани. Това свойство се нарича свойство Антимонотон.

Следваните стъпки в алгоритъма на Apriori за извличане на данни са:

  1. Присъединете се към Стъпка : Тази стъпка генерира (K + 1) набор от елементи от K-itemsets чрез присъединяване на всеки елемент със себе си.
  2. Подрязване на стъпка : Тази стъпка сканира броя на всеки елемент в базата данни. Ако кандидатният елемент не отговаря на минимална подкрепа, тогава той се счита за рядък и по този начин се премахва. Тази стъпка се извършва, за да се намали размерът на кандидатурите.

Стъпки в Apriori

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

# 1) При първата итерация на алгоритъма, всеки елемент се приема като кандидат за 1 елемент. Алгоритъмът ще отчита появата на всеки елемент.

# две) Нека има някаква минимална поддръжка, min_sup (напр. 2). Определят се наборите от 1 - артикули, чиято поява отговаря на минималната сума. Само тези кандидати, които броят повече или равно на min_sup, се вземат напред за следващата итерация, а останалите се подрязват.

# 3) След това се откриват 2 елемента с чести елементи с min_sup. За това в стъпката на присъединяване наборът от 2 елемента се генерира чрез образуване на група от 2 чрез комбиниране на елементи със себе си.

# 4) Кандидатите от 2 елемента се подрязват, като се използва минимална стойност на прага. Сега таблицата ще има 2 -imsetset само с min-sup.

# 5) Следващата итерация ще формира 3 –itemsets, използвайки стъпка join и prune. Тази итерация ще последва антимонотонното свойство, където подмножествата от 3-позиции, т.е. 2-позициите от всяка група попадат в min_sup. Ако всички подмножества от 2 елемента са чести, тогава супермножеството ще бъде често, в противен случай се подрязва.

# 6) Следващата стъпка ще последва създаването на набор от 4 елемента чрез присъединяване на 3 елемента със себе си и подрязване, ако неговото подмножество не отговаря на критериите min_sup. Алгоритъмът се спира, когато се постигне най-честият набор от елементи.

Apriori Steps

(изображение източник )

Пример за Apriori:Праг на подкрепа = 50%, доверие = 60%

МАСА 1

ТранзакцияСписък на артикулите
Т1I1, I2, I3
Т2I2, I3, I4
Т3I4, I5
Т4I1, I2, I4
Т5I1, I2, I3, I5
Т6I1, I2, I3, I4

Решение:

Праг на подкрепа = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Брой на всеки артикул

ТАБЛИЦА-2

ВещБроя
I14
I25
I34
I44
I5две

две. Стъпка на подрязване: ТАБЛИЦА -2 показва, че елементът I5 не отговаря на min_sup = 3, като по този начин се изтрива, само I1, I2, I3, I4 отговарят на броя на min_sup.

ТАБЛИЦА-3

ВещБроя
I14
I25
I34
I44

3. Присъединете се към стъпка: Форма от 2 елемента. От МАСА 1 разберете появата на 2-itemset.

ТАБЛИЦА-4

ВещБроя
I1, I24
I1, I33
I1, I4две
I2, I34
I2, I43
I3, I4две

Четири. Стъпка на подрязване: ТАБЛИЦА -4 показва, че набор от елементи {I1, I4} и {I3, I4} не отговаря на min_sup, поради което се изтрива.

ТАБЛИЦА-5

ВещБроя
I1, I24
I1, I33
I2, I34
I2, I43

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%

Това показва, че всички горепосочени правила за асоцииране са силни, ако минималният праг на доверие е 60%.

Алгоритъмът на Apriori: Псевдокодекс

C: Набор от кандидати с размер k

L: Чести елементи от размер k

отваряне на .jar файлове на Windows 10

Псевдокод

(изображение източник )

Предимства

  1. Лесен за разбиране алгоритъм
  2. Стъпките за присъединяване и подрязване са лесни за изпълнение в големи набори от елементи в големи бази данни

Недостатъци

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

Методи за подобряване на ефективността на Apriori

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

  1. Техника, базирана на хеш: Този метод използва хеш-базирана структура, наречена хеш-таблица за генериране на k-itemsets и съответния брой. Той използва хеш функция за генериране на таблицата.
  2. Намаляване на транзакциите: Този метод намалява броя на транзакциите, сканирани в итерации. Транзакциите, които не съдържат чести артикули, се маркират или премахват.
  3. Разделяне: Този метод изисква само две сканирания на база данни, за да се минират честите набори от елементи. В него се казва, че за да може всеки набор от елементи да бъде потенциално чест в базата данни, той трябва да бъде чест в поне един от дяловете на базата данни.
  4. Вземане на проби: Този метод избира произволна извадка S от базата данни D и след това търси чести набори от елементи в S. Може да е възможно да загубите глобален чест набор от предмети. Това може да бъде намалено чрез намаляване на min_sup.
  5. Динамично преброяване на артикулите: Тази техника може да добавя нови набори от кандидати във всяка маркирана начална точка на базата данни по време на сканирането на базата данни.

Приложения на алгоритъма на Apriori

Някои полета, в които се използва Apriori:

  1. В областта на образованието: Извличане на правила за асоцииране при извличане на данни на приети студенти чрез характеристики и специалности.
  2. В областта на медицината: Например Анализ на базата данни на пациента.
  3. В горското стопанство: Анализ на вероятността и интензивността на горския пожар с данните за горските пожари.
  4. Apriori се използва от много компании като Amazon в Препоръчваща система и от Google за функцията за автоматично попълване.

Заключение

Apriori алгоритъмът е ефективен алгоритъм, който сканира базата данни само веднъж.

Намалява значително размера на наборите от елементи в базата данни, като осигурява добра производителност. По този начин извличането на данни помага на потребителите и индустриите по-добре в процеса на вземане на решения.

Вижте нашия предстоящ урок, за да научите повече за алгоритъма за растеж на честия модел !!

PREV Урок | СЛЕДВАЩ урок

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

^