apriori algorithm data mining
Dubinski vodič o Apriori algoritmu za pronalaženje čestih skupova predmeta u rudarstvu podataka. Ovaj vodič objašnjava korake u Aprioriju i kako to funkcionira:
U ovome Serije vodiča za rudarenje podataka , pogledali smo Algoritam stabla odlučivanja u našem prethodnom vodiču.
Postoji nekoliko metoda za rudarenje podataka kao što su udruživanje, korelacija, klasifikacija i klasterizacija.
kako otvoriti .bin datoteke windows 10
Ovaj se vodič prvenstveno fokusira na rudarstvo pomoću pravila pridruživanja. Pravilima udruživanja identificiramo skup predmeta ili atributa koji se pojavljuju zajedno u tablici.
Što ćete naučiti:
- Što je set predmeta?
- Zašto često rudanje skupa predmeta?
- Metode za poboljšanje učinkovitosti apriorija
- Primjene Apriori algoritma
- Zaključak
Što je set predmeta?
Skup predmeta zajedno naziva se skup predmeta. Ako bilo koji skup predmeta ima k-stavki, naziva se k-stavka. Skup predmeta sastoji se od dvije ili više stavki. Skup predmeta koji se često događa naziva se čestim skupom predmeta. Stoga je često rukovanje stavkama tehnika rudarenja podataka radi identificiranja predmeta koji se često javljaju zajedno.
Na primjer , Kruh i maslac, softver za prijenosna računala i antivirus itd.
Što je česti skup predmeta?
Skup predmeta naziva se čestim ako zadovoljava minimalnu vrijednost praga za podršku i samopouzdanje. Podrška prikazuje transakcije s predmetima kupljenim zajedno u jednoj transakciji. Povjerenje pokazuje transakcije u kojima se predmeti kupuju jedan za drugim.
Za čestu metodu rukovanja stavkama uzimamo u obzir samo one transakcije koje udovoljavaju minimalnim zahtjevima za podršku i povjerenje. Uvidi iz ovih algoritama rudarstva nude puno prednosti, smanjenje troškova i poboljšanu konkurentsku prednost.
Potrebno je vrijeme kompromisa za miniranje podataka i količinu podataka za često rudarstvo. Česti algoritam rudarstva učinkovit je algoritam za miniranje skrivenih uzoraka skupova predmeta u kratkom vremenu i uz manju potrošnju memorije.
Učestalo iskopavanje uzoraka (FPM)
Česti algoritam rudarenja uzoraka jedna je od najvažnijih tehnika rudarenja podataka radi otkrivanja odnosa između različitih stavki u skupu podataka. Ti su odnosi predstavljeni u obliku pravila udruživanja. Pomaže u pronalaženju nepravilnosti u podacima.
FPM ima mnogo aplikacija na području analize podataka, softverskih grešaka, unakrsnog marketinga, analize prodajnih kampanja, analize tržišnih košarica itd.
Česti skupovi predmeta otkriveni putem Apriorija imaju mnogo aplikacija u zadacima rudarenja podataka. Zadaci kao što su pronalaženje zanimljivih obrazaca u bazi podataka, utvrđivanje slijeda i Rudanje pravila pridruživanja najvažniji su od njih.
Pravila udruživanja primjenjuju se na podatke o transakcijama u supermarketu, odnosno za ispitivanje ponašanja kupaca u smislu kupljenih proizvoda. Pravila udruživanja opisuju koliko često se predmeti kupuju zajedno.
Pravila udruživanja
Udruženje pravila ruda definirano je kao:
„Neka I = {...} bude skup 'n' binarnih atributa koji se nazivaju stavke. Neka je D = {….} Skup transakcija koja se naziva baza podataka. Svaka transakcija u D ima jedinstveni ID transakcije i sadrži podskup stavki u I. Pravilo je definirano kao implikacija oblika X-> Y gdje X, Y? I i X? Y = ?. Skup elemenata X i Y nazivaju se prethodnicima, odnosno posljedicama pravila. '
Učenje pravila pridruživanja koristi se za pronalaženje odnosa između atributa u velikim bazama podataka. Pravilo pridruživanja, A => B, bit će oblika: 'za skup transakcija neka vrijednost stavke A određuje vrijednosti skupa stavki B pod uvjetom da su zadovoljene minimalna podrška i povjerenje'.
Podrška i povjerenje mogu se predstaviti na sljedećem primjeru:
Bread=> butter [support=2%, confidence-60%]
Gornja izjava primjer je pravila udruživanja. To znači da postoji transakcija od 2% koja je zajedno kupila kruh i maslac, a 60% kupaca je kupilo kruh kao i maslac.
Podrška i povjerenje za stavke A i B predstavljaju formule:
Rudarstvo pravila pridruživanja sastoji se od 2 koraka:
- Pronađite sve česte skupove predmeta.
- Generirajte pravila pridruživanja iz gore navedenih čestih skupova predmeta.
Zašto često rudanje skupa predmeta?
Učestalo rukovanje skupovima predmeta ili uzoraka široko se koristi zbog svoje široke primjene u pravilima udruživanja rudnika, korelacijama i ograničenjima uzoraka grafikona koji se temelji na čestim uzorcima, sekvencijalnim uzorcima i mnogim drugim zadacima rudarenja podataka.
Apriori algoritam - Algoritmi čestih obrazaca
Apriori algoritam bio je prvi algoritam koji je predložen za često rukovanje skupom predmeta. Kasnije su ga poboljšali R Agarwal i R Srikant i postao poznat kao Apriori. Ovaj algoritam koristi dva koraka 'pridruživanje' i 'obrezivanje' kako bi smanjio prostor za pretraživanje. To je iterativni pristup otkrivanju najčešćih skupova predmeta.
Apriori kaže:
Vjerojatnost da stavka I nije česta jest ako:
- P (I)
- P (I + A)
- Ako skup skupova predmeta ima vrijednost manju od minimalne podrške, tada će svi njegovi supersetovi također pasti ispod minimalne podrške, pa se stoga mogu zanemariti. Ovo se svojstvo naziva Antimonotone svojstvo.
- P (I + A)
Koraci koji se slijede u Apriorijevom algoritmu rudarenja podacima su:
- Pridružite se koraku : Ovaj korak generira (K + 1) skup predmeta iz skupova predmeta K spajanjem svake stavke sa sobom.
- Korak orezati : Ovaj korak skenira broj svake stavke u bazi podataka. Ako stavka kandidata ne zadovoljava minimalnu potporu, tada se smatra rijetkom i stoga se uklanja. Ovaj se korak izvodi kako bi se smanjila veličina skupova predmeta koji su kandidati.
Koraci u Apriori
Apriori algoritam je slijed koraka koje treba slijediti kako bi se pronašao najčešći skup predmeta u datoj bazi podataka. Ova tehnika pretraživanja podataka iterativno slijedi korake spajanja i obrezivanja dok se ne postigne najčešći skup predmeta. Minimalni prag podrške naveden je u problemu ili ga pretpostavlja korisnik.
# 1) U prvoj iteraciji algoritma, svaka se stavka uzima kao kandidat za 1 skup predmeta. Algoritam će brojati pojave svake stavke.
#dva) Neka postoji neka minimalna podrška, min_sup (npr. 2). Određuje se skup skupova od 1 predmeta čija pojava zadovoljava minimalnu sup. Samo oni kandidati koji broje više ili jednako min_sup, uzimaju se naprijed za sljedeću iteraciju, a ostali se obrezuju.
# 3) Dalje se otkrivaju česte stavke s 2 stavke s min_sup. Za to se u koraku spajanja skup 2 predmeta generira formiranjem grupe od 2 kombiniranjem predmeta sa sobom.
# 4) Kandidati s 2 stavke obrezuju se pomoću praga min-sup. Sada će tablica imati 2 -set skupova s samo min-supom.
# 5) Sljedeća će se iteracija oblikovati u 3 elementa pomoću koraka spajanja i obrezivanja. Ova će iteracija slijediti svojstvo antimonotone gdje podskupovi skupova od 3 predmeta, odnosno 2 podskupa svih skupina padaju u min_sup. Ako su svi podskupovi skupa od dva predmeta česti, tada će superset biti čest, inače se obrezuje.
# 6) Sljedeći korak slijedit će izradu skupa od 4 predmeta spajanjem skupa od 3 predmeta i obrezivanjem ako njegov podskup ne zadovoljava kriterije min_sup. Algoritam se zaustavlja kada se postigne najčešći skup predmeta.
[slika izvor ]
Primjer Apriorija:Prag podrške = 50%, povjerenje = 60%
STOL 1
Transakcija | Popis predmeta |
---|---|
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 |
Riješenje:
Prag potpore = 50% => 0,5 * 6 = 3 => min_sup = 3
najbolje slušalice za virtualnu stvarnost za xbox one
1. Brojanje svake stavke
TABLICA-2
Artikal | Računati |
---|---|
I1 | 4 |
I2 | 5 |
I3 | 4 |
I4 | 4 |
I5 | dva |
dva. Korak orezivanja: TABLICA -2 pokazuje da stavka I5 ne ispunjava min_sup = 3, stoga se briše, samo I1, I2, I3, I4 ispunjavaju min_sup count.
TABLICA-3
Artikal | Računati |
---|---|
I1 | 4 |
I2 | 5 |
I3 | 4 |
I4 | 4 |
3. Pridružite se koraku: Obrazac od 2 stavke. Iz STOL 1 saznajte pojave skupa od 2 predmeta.
TABLICA-4
Artikal | Računati |
---|---|
I1, I2 | 4 |
I1, I3 | 3 |
I1, I4 | dva |
I2, I3 | 4 |
I2, I4 | 3 |
I3, I4 | dva |
Četiri. Korak orezivanja: TABLICA -4 pokazuje da skup stavki {I1, I4} i {I3, I4} ne zadovoljava min_sup, pa je izbrisan.
TABLICA-5
Artikal | Računati |
---|---|
I1, I2 | 4 |
I1, I3 | 3 |
I2, I3 | 4 |
I2, I4 | 3 |
5. Pridružite se i orežite korak: Obrazac od 3 stavke. Od STOL 1 saznajte pojave skupa od 3 stavke. Iz TABLICA-5 , saznajte podskup 2-itemset koji podržavaju min_sup.
Možemo vidjeti za podskupove stavki {I1, I2, I3}, {I1, I2}, {I1, I3}, {I2, I3} pojavljuju se u TABLICA-5 stoga su {I1, I2, I3} česti.
Vidimo da podskupovi {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} nisu česti, jer se ne pojavljuju u TABLICA-5 stoga {I1, I2, I4} nije čest, stoga se briše.
TABLICA-6
Artikal |
---|
I1, I2, I3 |
I1, I2, I4 |
I1, I3, I4 |
I2, I3, I4 |
Česti su samo {I1, I2, I3} .
6. Generiraj pravila pridruživanja: Iz učestalog skupa predmeta otkrivenog iznad, povezanost bi mogla biti:
{I1, I2} => {I3}
Pouzdanje = podrška {I1, I2, I3} / podrška {I1, I2} = (3/4) * 100 = 75%
{I1, I3} => {I2}
Povjerenje = podrška {I1, I2, I3} / podrška {I1, I3} = (3/3) * 100 = 100%
{I2, I3} => {I1}
Pouzdanje = podrška {I1, I2, I3} / podrška {I2, I3} = (3/4) * 100 = 75%
{I1} => {I2, I3}
Pouzdanje = podrška {I1, I2, I3} / podrška {I1} = (3/4) * 100 = 75%
{I2} => {I1, I3}
Pouzdanje = podrška {I1, I2, I3} / podrška {I2 = (3/5) * 100 = 60%
{I3} => {I1, I2}
Pouzdanje = podrška {I1, I2, I3} / podrška {I3} = (3/4) * 100 = 75%
To pokazuje da su sva gore navedena pravila pridruživanja jaka ako je minimalni prag povjerenja 60%.
Apriori algoritam: Pseudo kod
C: Skup predmeta veličine kandidata k
L: Česti skup predmeta veličine k
[slika izvor ]
Prednosti
- Lako razumljiv algoritam
- Korake pridruživanja i obrezivanja lako je implementirati na velikim skupovima predmeta u velikim bazama podataka
Mane
- To zahtijeva velike proračune ako su skupovi predmeta vrlo veliki, a minimalna podrška je vrlo niska.
- Treba skenirati cijelu bazu podataka.
Metode za poboljšanje učinkovitosti apriorija
Dostupne su mnoge metode za poboljšanje učinkovitosti algoritma.
- Tehnika temeljena na hashu: Ova metoda koristi strukturu temeljenu na raspršivanju koja se naziva tablica raspršivanja za generiranje k-predmeta i odgovarajućeg broja. Za generiranje tablice koristi hash funkciju.
- Smanjenje transakcija: Ova metoda smanjuje broj skeniranja transakcija u iteracijama. Transakcije koje ne sadrže česte stavke označene su ili uklonjene.
- Pregrađivanje: Ova metoda zahtijeva samo dva skeniranja baze podataka za miniranje čestih skupova predmeta. U njemu se kaže da bi bilo koji skup predmeta mogao biti čest u bazi podataka, trebao bi biti čest na barem jednoj od particija baze podataka.
- Uzorkovanje: Ova metoda odabire slučajni uzorak S iz baze podataka D, a zatim pretražuje učestali skup predmeta u S. Možda će biti moguće izgubiti globalni učestali skup predmeta. To se može smanjiti smanjenjem min_sup.
- Dinamičko brojanje skupova predmeta: Ova tehnika može dodati nove skupove stavki kandidata na bilo kojoj označenoj početnoj točki baze podataka tijekom skeniranja baze podataka.
Primjene Apriori algoritma
Neka polja u kojima se koristi Apriori:
- U području obrazovanja: Izdvajanje pravila o udruživanju u pretraživanju podataka primljenih učenika kroz karakteristike i specijalnosti.
- U području medicine: Na primjer Analiza baze podataka pacijenta.
- U šumarstvu: Analiza vjerojatnosti i intenziteta šumskog požara s podacima o šumskim požarima.
- Apriori koriste mnoge tvrtke poput Amazona u Sustav preporuke i Google za značajku automatskog dovršavanja.
Zaključak
Apriori algoritam je učinkovit algoritam koji skenira bazu podataka samo jednom.
Značajno smanjuje veličinu skupova predmeta u bazi podataka pružajući dobre performanse. Dakle, rudarenje podataka pomaže potrošačima i industrijama bolje u procesu donošenja odluka.
Pogledajte naš predstojeći vodič da biste saznali više o algoritmu rasta učestalog uzorka !!
Preporučena literatura
- Tehnike rudarstva podataka: algoritam, metode i vrhunski alati za miniranje podataka
- Rudarstvo podataka: proces, tehnike i glavni problemi u analizi podataka
- Primjeri rudarenja podataka: Najčešća primjena rudarstva podataka 2021
- Primjeri algoritma stabla odlučivanja u rudarstvu podataka
- Proces rudarenja podataka: uključeni modeli, koraci i izazovi
- Data Mining vs Machine Learning vs Artificial Intelligence vs Deep Learning
- 15 najboljih besplatnih alata za rudarenje podataka: Najopsežniji popis
- JMeter parametalizacija podataka korištenjem korisnički definiranih varijabli