apriori algorithm data mining
Szczegółowy samouczek dotyczący algorytmu Apriori, aby znaleźć częste zestawy elementów w eksploracji danych. Ten samouczek wyjaśnia kroki w Apriori i jak to działa:
W tym Seria samouczków dotyczących eksploracji danych , przyjrzeliśmy się plikowi Algorytm drzewa decyzyjnego w naszym poprzednim samouczku.
Istnieje kilka metod eksploracji danych, takich jak asocjacja, korelacja, klasyfikacja i grupowanie.
narzędzia do łamania haseł dla systemu Windows 7
Ten samouczek koncentruje się głównie na eksploracji przy użyciu reguł asocjacji. Za pomocą reguł asocjacyjnych identyfikujemy zestaw elementów lub atrybutów, które występują razem w tabeli.
Czego się nauczysz:
- Co to jest zestaw przedmiotów?
- Dlaczego częste wydobywanie zestawów przedmiotów?
- Metody poprawy efektywności Apriori
- Zastosowania algorytmu Apriori
- Wniosek
Co to jest zestaw przedmiotów?
Zestaw elementów razem nazywany jest zestawem elementów. Jeśli jakikolwiek zestaw elementów ma k-elementów, nazywany jest zestawem k-elementów. Zestaw przedmiotów składa się z dwóch lub więcej elementów. Często występujący zestaw elementów nazywany jest częstym zestawem elementów. Dlatego częste eksploracja zestawów elementów jest techniką eksploracji danych służącą do identyfikacji elementów, które często występują razem.
Na przykład , Chleb i masło, oprogramowanie do laptopów i antywirusów itp.
Co to jest częsty zestaw przedmiotów?
Zestaw elementów nazywany jest częstymi, jeśli spełnia minimalną wartość progową wsparcia i zaufania. Wsparcie pokazuje transakcje z przedmiotami zakupionymi razem w jednej transakcji. Zaufanie pokazuje transakcje, w których przedmioty są kupowane jeden po drugim.
W przypadku metody wyszukiwania często zestawów przedmiotów rozważamy tylko te transakcje, które spełniają minimalne wymagania dotyczące wsparcia progowego i zaufania. Informacje z tych algorytmów wydobywczych oferują wiele korzyści, obniżają koszty i zwiększają przewagę konkurencyjną.
Wydobywanie danych wymaga kompromisu, a ich ilość wymaga częstego wydobywania. Algorytm częstego wyszukiwania jest skutecznym algorytmem do wydobywania ukrytych wzorców zestawów przedmiotów w krótkim czasie i przy mniejszym zużyciu pamięci.
Częste wydobywanie wzorców (FPM)
Algorytm częstego eksploracji wzorców jest jedną z najważniejszych technik eksploracji danych służących do wykrywania relacji między różnymi elementami w zbiorze danych. Relacje te są przedstawiane w postaci reguł asocjacyjnych. Pomaga znaleźć nieprawidłowości w danych.
FPM ma wiele zastosowań z zakresu analizy danych, błędów oprogramowania, cross-marketingu, analizy kampanii sprzedażowych, analizy koszyka rynkowego itp.
Częste zestawy elementów odkrywane przez Apriori mają wiele zastosowań w zadaniach eksploracji danych. Zadania takie jak wyszukiwanie interesujących wzorców w bazie danych, ustalanie kolejności i wyszukiwanie reguł asocjacyjnych to najważniejsze z nich.
Reguły asocjacyjne mają zastosowanie do danych transakcyjnych supermarketów, to znaczy do badania zachowań klientów pod kątem zakupionych produktów. Reguły asocjacyjne opisują, jak często przedmioty są kupowane razem.
Zasady stowarzyszenia
Association Rule Mining definiuje się jako:
„Niech I = {…} będzie zbiorem atrybutów binarnych„ n ”zwanych elementami. Niech D = {….} Będzie zbiorem transakcji zwanej bazą danych. Każda transakcja w D ma unikalny identyfikator transakcji i zawiera podzbiór pozycji w I. Reguła jest definiowana jako implikacja postaci X-> Y, gdzie X, Y? Ja i X? Y = ?. Zbiór elementów X i Y nazywane są odpowiednio poprzedzającymi i następującymi regułami. ”
Uczenie się reguł asocjacji służy do znajdowania relacji między atrybutami w dużych bazach danych. Reguła asocjacyjna A => B będzie miała postać „dla zbioru transakcji pewna wartość zbioru pozycji A określa wartości zbioru pozycji B pod warunkiem, że spełnione są minimalne wsparcie i zaufanie”.
Wsparcie i zaufanie można przedstawić na następującym przykładzie:
Bread=> butter [support=2%, confidence-60%]
Powyższe stwierdzenie jest przykładem reguły asocjacyjnej. Oznacza to, że istnieje 2% transakcji, która kupiła razem chleb i masło, a 60% klientów kupiło zarówno chleb, jak i masło.
Wsparcie i zaufanie dla zestawu pozycji A i B są reprezentowane przez formuły:
Eksploracja reguł asocjacyjnych składa się z 2 kroków:
- Znajdź wszystkie często używane zestawy przedmiotów.
- Wygeneruj reguły asocjacji z powyższych częstych zestawów elementów.
Dlaczego częste wydobywanie zestawów przedmiotów?
Częste eksploracja zestawów elementów lub wzorców jest szeroko stosowana ze względu na jego szerokie zastosowanie w regułach asocjacji, korelacjach i ograniczeniach wzorców wykresów, które są oparte na częstych wzorcach, wzorcach sekwencyjnych i wielu innych zadaniach eksploracji danych.
Algorytm Apriori - Częste algorytmy wzorców
Algorytm Apriori był pierwszym algorytmem zaproponowanym do częstego eksploracji zestawów przedmiotów. Został później ulepszony przez R Agarwal i R. Srikant i stał się znany jako Apriori. Algorytm ten wykorzystuje dwa kroki „dołącz” i „przycinaj”, aby zmniejszyć przestrzeń wyszukiwania. Jest to iteracyjne podejście do odkrywania najczęściej używanych zestawów przedmiotów.
Apriori mówi:
Prawdopodobieństwo, że pozycja I nie występuje często, jest następujące:
- LICZBA PI)
- P (I + A)
- Jeśli zestaw elementów ma wartość mniejszą niż minimalne wsparcie, wszystkie jego supersety również spadną poniżej minimalnego wsparcia, a zatem mogą zostać zignorowane. Ta właściwość jest nazywana właściwością antymonotonu.
- P (I + A)
Kroki wykonywane w algorytmie Apriori eksploracji danych to:
- Dołącz do Step : Ten krok generuje (K + 1) zestaw przedmiotów z zestawów K-itemów, łącząc każdy element ze sobą.
- Prune Step : Ten krok skanuje liczbę każdego elementu w bazie danych. Jeśli pozycja kandydata nie spełnia minimalnego wsparcia, jest uważana za rzadką i dlatego jest usuwana. Ten krok jest wykonywany w celu zmniejszenia rozmiaru zestawów pozycji kandydatów.
Kroki w Apriori
Algorytm Apriori to sekwencja kroków, które należy wykonać, aby znaleźć najczęściej występujący zestaw pozycji w danej bazie danych. Ta technika eksploracji danych następuje iteracyjnie po łączeniu i przycinaniu, aż zostanie osiągnięty najczęstszy zestaw elementów. Minimalny próg wsparcia jest podany w problemie lub jest zakładany przez użytkownika.
# 1) W pierwszej iteracji algorytmu każdy element jest traktowany jako kandydat na 1-elementowy zestaw. Algorytm policzy wystąpienia każdego elementu.
#dwa) Niech będzie jakieś minimalne wsparcie, min_sup (np. 2). Określany jest zbiór 1 - zestawy elementów, których wystąpienie spełnia min sup. Tylko ci kandydaci, których wartość jest większa lub równa min_sup, są przejmowani do następnej iteracji, a pozostałe są przycinane.
# 3) Następnie wykrywane są częste pozycje z 2 zestawami z min_sup. W tym celu w etapie łączenia zestaw 2 elementów jest generowany przez utworzenie grupy 2 elementów poprzez połączenie elementów ze sobą.
# 4) Kandydaci na zestawy 2 elementów są przycinani przy użyciu wartości progowej min-sup. Teraz tabela będzie zawierała 2 - zestawy tylko z min-sup.
# 5) Następna iteracja utworzy 3 - zestawy przy użyciu kroku łączenia i przycinania. Ta iteracja będzie następować po właściwości antymonotonu, gdzie podzbiory 3-elementów, to znaczy podzbiory 2-elementów każdej grupy, przypadają na min_sup. Jeśli wszystkie podzbiory 2-elementowe są częste, superzbiór będzie częsty, w przeciwnym razie zostanie przycięty.
# 6) Następnym krokiem będzie utworzenie zestawu 4 elementów poprzez połączenie zestawu 3 elementów ze sobą i przycięcie, jeśli jego podzbiór nie spełnia kryteriów min_sup. Algorytm jest zatrzymywany po osiągnięciu najczęstszego zestawu elementów.
[wizerunek źródło ]
Przykład Apriori:Próg wsparcia = 50%, zaufanie = 60%
TABELA 1
Transakcja | Lista rzeczy |
---|---|
T1 | I1, I2, I3 |
T2 | I2, I3, I4 |
T3 | I4, I5 |
T4 | I1, I2, I4 |
T5 | I1, I2, I3, I5 |
T6 | I1, I2, I3, I4 |
Rozwiązanie:
Próg wsparcia = 50% => 0,5 * 6 = 3 => min_sup = 3
1. Liczba każdej pozycji
TABELA 2
Pozycja | Liczyć |
---|---|
I1 | 4 |
I2 | 5 |
I3 | 4 |
I4 | 4 |
I5 | dwa |
dwa. Krok przycinania: TABELA 2 pokazuje, że element I5 nie spełnia min_sup = 3, więc jest usuwany, tylko I1, I2, I3, I4 spotykają się z liczbą min_sup.
TABELA 3
Pozycja | Liczyć |
---|---|
I1 | 4 |
I2 | 5 |
I3 | 4 |
I4 | 4 |
3. Dołącz do kroku: Formularz 2-elementowy zestaw. Od TABELA 1 znajdź wystąpienia 2-itemset.
TABELA-4
Pozycja | Liczyć |
---|---|
I1, I2 | 4 |
I1, I3 | 3 |
I1, I4 | dwa |
I2, I3 | 4 |
I2, I4 | 3 |
I3, I4 | dwa |
Cztery. Krok przycinania: TABELA -4 pokazuje, że zestaw elementów {I1, I4} i {I3, I4} nie spełnia min_sup, więc jest usuwany.
TABELA-5
Pozycja | Liczyć |
---|---|
I1, I2 | 4 |
I1, I3 | 3 |
I2, I3 | 4 |
I2, I4 | 3 |
5. Krok łączenia i czyszczenia: Formularz 3-elementowy zestaw. Z TABELA 1 znajdź wystąpienia zestawu 3 elementów. Od TABELA-5 , znajdź podzbiory 2-pozycji, które obsługują min_sup.
Widzimy, że podzbiory zestawu {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} występują w TABELA-5 tak więc {I1, I2, I3} jest częste.
Widzimy dla zestawu elementów {I1, I2, I4} podzbiory, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} nie występuje często, ponieważ nie występuje w TABELA-5 zatem {I1, I2, I4} nie jest częste, stąd jest usuwane.
TABELA-6
Pozycja |
---|
I1, I2, I3 |
I1, I2, I4 |
I1, I3, I4 |
I2, I3, I4 |
Tylko {I1, I2, I3} są częste .
6. Wygeneruj reguły asocjacji: Z częstego zestawu pozycji odkrytego powyżej skojarzenia mogą wynikać:
{I1, I2} => {I3}
Zaufanie = wsparcie {I1, I2, I3} / wsparcie {I1, I2} = (3/4) * 100 = 75%
algorytm szybkiego sortowania c ++
{I1, I3} => {I2}
Zaufanie = wsparcie {I1, I2, I3} / wsparcie {I1, I3} = (3/3) * 100 = 100%
{I2, I3} => {I1}
Zaufanie = wsparcie {I1, I2, I3} / wsparcie {I2, I3} = (3/4) * 100 = 75%
{I1} => {I2, I3}
Zaufanie = wsparcie {I1, I2, I3} / wsparcie {I1} = (3/4) * 100 = 75%
{I2} => {I1, I3}
Zaufanie = wsparcie {I1, I2, I3} / wsparcie {I2 = (3/5) * 100 = 60%
{I3} => {I1, I2}
Zaufanie = wsparcie {I1, I2, I3} / wsparcie {I3} = (3/4) * 100 = 75%
To pokazuje, że wszystkie powyższe reguły asocjacji są mocne, jeśli minimalny próg ufności wynosi 60%.
Algorytm Apriori: pseudokod
C: Kandydat na zestaw przedmiotów o rozmiarze k
L: Częsty zestaw w rozmiarze k
[wizerunek źródło ]
Zalety
- Łatwy do zrozumienia algorytm
- Kroki łączenia i czyszczenia są łatwe do wdrożenia w dużych zestawach elementów w dużych bazach danych
Niedogodności
- Wymaga wysokich obliczeń, jeśli zestawy elementów są bardzo duże, a minimalne wsparcie jest bardzo niskie.
- Należy przeskanować całą bazę danych.
Metody poprawy efektywności Apriori
Dostępnych jest wiele metod poprawy wydajności algorytmu.
- Technika oparta na skrócie: Ta metoda wykorzystuje strukturę opartą na skrótach zwaną tablicą skrótów do generowania zestawów k-elementów i odpowiadającej im liczby. Używa funkcji skrótu do generowania tabeli.
- Redukcja transakcji: Ta metoda zmniejsza liczbę operacji skanowania w iteracjach. Transakcje, które nie zawierają częstych pozycji są zaznaczane lub usuwane.
- Partycjonowanie: Ta metoda wymaga tylko dwóch skanowań bazy danych, aby wydobyć częste zestawy elementów. Mówi się, że aby jakikolwiek zestaw elementów był potencjalnie częsty w bazie danych, powinien występować często przynajmniej w jednej z partycji bazy danych.
- Próbowanie: Ta metoda wybiera losową próbkę S z bazy danych D, a następnie wyszukuje częste zestawy pozycji w S. Może się zdarzyć, że utracisz globalny częsty zestaw pozycji. Można to zmniejszyć, obniżając min_sup.
- Dynamiczne liczenie zestawów przedmiotów: Ta technika może dodawać nowe zestawy pozycji kandydatów w dowolnym zaznaczonym punkcie początkowym bazy danych podczas skanowania bazy danych.
Zastosowania algorytmu Apriori
Niektóre pola, w których stosuje się Apriori:
- W dziedzinie edukacji: Wyodrębnianie reguł asocjacyjnych w eksploracji danych przyjętych studentów według cech i specjalności.
- W dziedzinie medycyny: Na przykład analiza bazy danych pacjenta.
- W leśnictwie: Analiza prawdopodobieństwa i intensywności pożarów lasu wraz z danymi o pożarach lasu.
- Apriori jest używany przez wiele firm, takich jak Amazon w System rekomendujący i Google za funkcję autouzupełniania.
Wniosek
Algorytm Apriori to wydajny algorytm, który skanuje bazę danych tylko raz.
Znacznie zmniejsza rozmiar zestawów elementów w bazie danych, zapewniając dobrą wydajność. W ten sposób eksploracja danych pomaga konsumentom i branżom lepiej w procesie podejmowania decyzji.
Sprawdź nasz nadchodzący samouczek, aby dowiedzieć się więcej o algorytmie częstego wzrostu wzorców !!
POPRZEDNIA samouczek | NEXT Tutorial
rekomendowane lektury
- Techniki eksploracji danych: algorytm, metody i najlepsze narzędzia eksploracji danych
- Eksploracja danych: proces, techniki i główne problemy w analizie danych
- Przykłady eksploracji danych: najczęstsze zastosowania eksploracji danych 2021
- Przykłady algorytmów drzew decyzyjnych w eksploracji danych
- Proces wyszukiwania danych: modele, etapy procesu i związane z nim wyzwania
- Wydobywanie danych kontra uczenie maszynowe, sztuczna inteligencja kontra uczenie głębokie
- 15 najlepszych bezpłatnych narzędzi do wyszukiwania danych: najbardziej kompleksowa lista
- Parametryzacja danych JMeter za pomocą zmiennych zdefiniowanych przez użytkownika