Meni

Apriorijev algoritem v rudarjenju podatkov: izvedba s primeri

  • Glavni
  • Drugo
  • Apriorijev algoritem v rudarjenju podatkov: izvedba s primeri

apriori algorithm data mining

Preizkusite Naš Instrument Za Odpravo Težav

Poglobljena vadnica o algoritmu Apriori za iskanje pogostih naborov elementov pri rudarjenju podatkov. Ta vadnica razlaga korake v Aprioriju in kako deluje:

V tem Serija vadnic za rudarjenje podatkov , smo si ogledali Algoritem drevesa odločitev v naši prejšnji vadnici.

Obstaja več metod za pridobivanje podatkov, kot so povezovanje, korelacija, klasifikacija in združevanje v skupine.

razlika med levim in zunanjim levim spojem v sql

Ta vadnica se osredotoča predvsem na rudarjenje z uporabo pravil pridružitve. Po pravilih združevanja določimo nabor elementov ali atributov, ki se pojavljajo skupaj v tabeli.

Apriorijev algoritem

Kaj se boste naučili:

Kaj je postavka?

Nabor elementov skupaj se imenuje nabor elementov. Če ima kateri koli element k-postavke, se imenuje k-element. Nabor elementov je sestavljen iz dveh ali več elementov. Pogosti nabor elementov se imenuje pogosti nabor elementov. Tako je pogosto nabiranje elementov tehnika podatkovnega rudarjenja za prepoznavanje elementov, ki se pogosto pojavljajo skupaj.

Na primer , Kruh in maslo, prenosna in protivirusna programska oprema itd.

Kaj je pogost nabor izdelkov?

Nabor elementov se imenuje pogost, če izpolnjuje najnižjo vrednost praga za podporo in zaupanje. Podpora prikazuje transakcije s predmeti, kupljenimi skupaj v eni transakciji. Zaupanje prikazuje transakcije, pri katerih se predmeti kupujejo eden za drugim.

Pri pogostih metodah nabora elementov upoštevamo samo tiste transakcije, ki izpolnjujejo minimalne zahteve glede podpore in zaupanja. Vpogledi teh rudarskih algoritmov ponujajo veliko prednosti, zmanjšanje stroškov in izboljšano konkurenčno prednost.

Za rudarske podatke je potreben čas zamenjave in obseg podatkov za pogosto rudarjenje. Pogost algoritem rudarjenja je učinkovit algoritem za iskanje skritih vzorcev naborov elementov v kratkem času in manj porabe pomnilnika.

Pogosto pridobivanje vzorcev (FPM)

Pogost algoritem rudarjenja vzorcev je ena najpomembnejših tehnik rudarjenja podatkov za odkrivanje odnosov med različnimi elementi v naboru podatkov. Ta razmerja so predstavljena v obliki pravil o pridružitvi. Pomaga pri odkrivanju nepravilnosti v podatkih.

FPM ima veliko aplikacij na področju analize podatkov, programskih napak, navzkrižnega trženja, analize prodajnih akcij, analize tržne košarice itd.

Pogosti nabori predmetov, odkriti prek Apriorija, imajo veliko aplikacij pri nalogah rudarjenja podatkov. Naloge, kot so iskanje zanimivih vzorcev v zbirki podatkov, ugotavljanje zaporedja in rudarstvo pravil pridružitve, so najpomembnejše med njimi.

Pravila pridružitve veljajo za podatke o transakcijah v supermarketih, to je za preučitev vedenja kupcev glede na kupljene izdelke. Pravila združenja opisujejo, kako pogosto se predmeti kupujejo skupaj.

Pridružitvena pravila

Pridružitveno pravilo rudarjenja je opredeljeno kot:

»Naj bo I = {…} niz binarnih atributov, imenovanih elementov. Naj bo D = {….} Niz transakcij, imenovanih baza podatkov. Vsaka transakcija v D ima enoličen ID transakcije in vsebuje podmnožico elementov v I. Pravilo je opredeljeno kot implikacija obrazca X-> Y, kjer X, Y? I in X? Y = ?. Nabor postavk X in Y se imenuje predhodnik in posledično pravilo. '

Učenje pravil pridružitve se uporablja za iskanje odnosov med atributi v velikih zbirkah podatkov. Pravilo pridružitve, A => B, bo v obliki 'za nabor transakcij neka vrednost postavke A določa vrednosti postavke B pod pogojem, da sta izpolnjeni minimalna podpora in zaupanje'.

Podporo in zaupanje lahko predstavimo z naslednjim primerom:

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

Zgornja izjava je primer pravila o pridružitvi. To pomeni, da obstaja 2-odstotna transakcija, ki je kruh in maslo kupila skupaj, 60% kupcev pa je kupilo kruh in maslo.

Podporo in zaupanje za postavki A in B predstavljata formuli:

Formula za podporo in zaupanje za postavki A in B

Pridružitveno pravilo je sestavljeno iz dveh korakov:

  1. Poiščite vse pogoste nabore predmetov.
  2. Iz zgoraj navedenih pogostih naborov ustvarite pravila pridružitve.

Zakaj pogosto rudarstvo nabora predmetov?

Pogosto nabiranje elementov ali vzorcev se pogosto uporablja zaradi široke uporabe v pravilih rudarskih povezav, korelacijah in omejitvah vzorcev grafov, ki temeljijo na pogostih vzorcih, zaporednih vzorcih in številnih drugih nalogah za rudarjenje podatkov.

Apriori algoritem - Pogosti algoritmi vzorcev

Apriori algoritem je bil prvi algoritem, ki je bil predlagan za pogosto rudarjenje elementov. Kasneje sta ga izboljšala R Agarwal in R Srikant in je postal znan kot Apriori. Ta algoritem uporablja dva koraka 'pridruži se' in 'obreži', da zmanjša prostor za iskanje. To je iterativni pristop pri odkrivanju najpogostejših naborov predmetov.

Apriori pravi:

Verjetnost, da postavka I ni pogosta, je, če:

  • P (I)
  • P (I + A)
  • Če ima nabor elementov vrednost manjšo od minimalne podpore, bodo tudi vsi njegovi nabori pod minimalno podporo, zato jih lahko prezremo. Ta lastnost se imenuje lastnost Antimonotone.

Koraki v Apriorijevem algoritmu podatkovnega rudarjenja so:

  1. Pridružite se koraku : Ta korak generira (K + 1) nabor elementov iz nabora K-elementov, tako da vsak element povežete s seboj.
  2. Obrežite korak : Ta korak pregleda število posameznih elementov v zbirki podatkov. Če postavka kandidata ne izpolnjuje minimalne podpore, se šteje za redko in je zato odstranjena. Ta korak se izvede za zmanjšanje velikosti kandidatnih naborov elementov.

Koraki v Aprioriju

Apriorijev algoritem je zaporedje korakov, ki jih je treba uporabiti za iskanje najpogostejšega nabora elementov v dani bazi podatkov. Ta tehnika rudarjenja podatkov iteracijsko sledi korakom združevanja in obrezovanja, dokler ni dosežen najpogostejši nabor elementov. V težavi je naveden minimalni prag podpore ali pa ga uporabnik predpostavlja.

# 1) V prvi ponovitvi algoritma se vsak element šteje za kandidata za 1 element. Algoritem bo upošteval pojavitve vsakega predmeta.

#two) Naj bo nekaj minimalne podpore, min_sup (npr. 2). Določen je sklop 1 - nizov predmetov, katerih pojavnost izpolnjuje najnižjo vrednost. Samo tisti kandidati, ki štejejo več ali enako min_sup, se vodijo v naslednjo ponovitev, ostali pa se obrezujejo.

# 3) Nato se odkrijejo pogosti predmeti z dvema postavkama z min_sup. Za to v koraku združevanja nabor z dvema elementoma ustvari tako, da tvori skupino po 2 s kombiniranjem elementov s samim seboj.

# 4) Kandidati z dvema postavkama so obrezani z uporabo praga min-sup. Zdaj bo tabela imela dve stavki s samo min-sup.

# 5) Naslednja ponovitev bo tvorila 3 -imsete s korakom združevanja in obrezovanja. Ta ponovitev bo sledila antimonotonski lastnosti, kjer bodo podmnožice 3-elementov, to je podmnožice 2-elementov vsake skupine, padle v min_sup. Če so pogosti vsi podnabori z dvema postavkama, bo nadnabor pogost, sicer je obrezan.

# 6) Naslednji korak bo sledil izdelavi nabora 4-ih, tako da nabor 3-elementov povežete s seboj in obrežete, če njegov nabor ne izpolnjuje meril min_sup Algoritem se ustavi, ko je dosežen najpogostejši nabor elementov.

Apriori koraki

(slika vir )

Primer Apriori:Prag podpore = 50%, zaupanje = 60%

TABELA-1

TransakcijaSeznam predmetov
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Rešitev:

Prag podpore = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Štetje vsakega predmeta

TABELA-2

PostavkaŠtetje
I14.
I25.
I34.
I44.
I5dva

dva. Korak suhe slive: TABELA -2 kaže, da element I5 ne ustreza min_sup = 3, zato se izbriše, štejejo se le I1, I2, I3, I4.

TABELA-3

PostavkaŠtetje
I14.
I25.
I34.
I44.

3. Pridružite se koraku: Obrazec z dvema postavkama. Od TABELA-1 ugotovi pojav 2-itemset.

TABELA-4

PostavkaŠtetje
I1, I24.
I1, I33.
I1, I4dva
I2, I34.
I2, I43.
I3, I4dva

Štiri. Korak suhe slive: TABELA -4 kaže, da nabor elementov {I1, I4} in {I3, I4} ne ustreza min_sup, zato je izbrisan.

TABELA-5

PostavkaŠtetje
I1, I24.
I1, I33.
I2, I34.
I2, I43.

5. Pridružite se in obrežite korak: Obrazec s tremi elementi. Iz TABELA - 1 ugotovite pojav 3-elementov. Od TABELA-5 , poiščite podnabore z dvema postavkama, ki podpirajo min_sup.

Za podnabore postavk {I1, I2, I3} lahko opazimo, {I1, I2}, {I1, I3}, {I2, I3} se pojavljajo v TABELA-5 zato so {I1, I2, I3} pogoste.

Opazimo lahko, da podskupine {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} niso pogoste, saj se ne pojavljajo v TABELA-5 zato {I1, I2, I4} ni pogost, zato je izbrisan.

TABELA-6

Postavka
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Pogosti so samo {I1, I2, I3} .

6. Ustvari pridružitvena pravila: Iz pogostega nabora elementov, odkritega zgoraj, je lahko povezava:

{I1, I2} => {I3}

Zaupanje = podpora {I1, I2, I3} / podpora {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Zaupanje = podpora {I1, I2, I3} / podpora {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Zaupanje = podpora {I1, I2, I3} / podpora {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Zaupanje = podpora {I1, I2, I3} / podpora {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Zaupanje = podpora {I1, I2, I3} / podpora {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Zaupanje = podpora {I1, I2, I3} / podpora {I3} = (3/4) * 100 = 75%

To kaže, da so vsa zgornja pravila o pridružitvi močna, če je minimalni prag zaupanja 60%.

Apriorijev algoritem: psevdo koda

C: Nabor postavk kandidatov velikosti k

L: Pogosti nabor elementov velikosti k

Psudocode

(slika vir )

Prednosti

  1. Enostaven za razumevanje algoritem
  2. Korake združevanja in obrezovanja je enostavno izvesti na velikih naborih elementov v velikih zbirkah podatkov

Slabosti

  1. Zahteva veliko izračun, če so nabori elementov zelo veliki in je minimalna podpora zelo nizka.
  2. Celotno bazo podatkov je treba pregledati.

Metode za izboljšanje učinkovitosti apriorija

Na voljo je veliko metod za izboljšanje učinkovitosti algoritma.

  1. Tehnika, ki temelji na razpršitvi: Ta metoda uporablja strukturo, ki temelji na razpršitvi, imenovano razpršilno tabelo, za generiranje naborov k-elementov in ustrezno število. Za generiranje tabele uporablja funkcijo zgoščevanja.
  2. Zmanjšanje transakcije: Ta metoda zmanjša število pregledov transakcij v ponovitvah. Transakcije, ki ne vsebujejo pogostih postavk, so označene ali odstranjene.
  3. Pregrada: Ta metoda zahteva le dva skeniranja baze podatkov, da se mine najpogostejši nabori elementov. Pravi, da bi moral biti kateri koli nabor elementov v bazi podatkov potencialno pogost, vsaj v eni od particij baze podatkov.
  4. Vzorčenje: Ta metoda izbere naključni vzorec S iz zbirke podatkov D in nato poišče pogosti nabor elementov v S. Morda bo mogoče izgubiti splošni pogosti nabor elementov. To lahko zmanjšate tako, da znižate min_sup.
  5. Dinamično štetje nabora elementov: Ta tehnika lahko doda nove nabore elementov kandidatov na kateri koli označeni začetni točki baze podatkov med skeniranjem baze podatkov.

Aplikacije Apriorijevega algoritma

Nekaj ​​polj, kjer se uporablja Apriori:

  1. Na področju izobraževanja: Pridobivanje asociacijskih pravil pri rudarjenju podatkov sprejetih študentov skozi značilnosti in posebnosti.
  2. Na področju medicine: Na primer Analiza bolnikove baze podatkov.
  3. V gozdarstvu: Analiza verjetnosti in intenzivnosti gozdnih požarov s podatki o gozdnih požarih.
  4. Apriori v ZDA uporabljajo številna podjetja, kot je Amazon Sistem priporočil in Google za funkcijo samodejnega dokončanja.

Zaključek

Apriori algoritem je učinkovit algoritem, ki bazo podatkov pregleda samo enkrat.

Zmanjša velikost naborov elementov v zbirki podatkov, kar zagotavlja dobro delovanje. Tako podatkovno rudarjenje pomaga potrošnikom in panogam v procesu odločanja.

vrste preskušanja računalniškega sistema vključujejo

Oglejte si našo prihajajočo vadnico, če želite izvedeti več o algoritmu pogoste rasti vzorca !!

PREV Vadnica | NASLEDNJA Vadnica

Priporočeno branje

^