Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ROZDZIAŁ2.ODKRYWANIEASOCJACJI
generowanewszystkiesilnebinarneregułyasocjacyjne,którychufnośćjestnie
mniejszaniżzadanyprógminimalnejufnościminconf.Wkolejnychpunktach
omówimyalgorytmygenerowaniazbiorówczęstychiregułasocjacyjnych.
2.4.1.Odkrywaniezbiorówczęstych
Kluczoweznaczenie,zpunktuwidzeniaefektywnościalgorytmuodkrywaniasil-
nychbinarnychregułasocjacyjnych,mapierwszykrokalgorytmu–znajdowanie
zbiorówczęstych,tojestznajdowaniepodzbiorówzbioruL,którychwsparciejest
większelubrówneminimalnejwartościwsparciaminsup.Jakjużwspominaliśmy,
trywialnametodaznajdowaniazbiorówczęstych,polegającanawygenerowaniu
wszystkichpodzbiorówzbioruL,anastępnienaobliczeniudlakażdegopodzbio-
ruwartościwsparciategopodzbioru,wpraktycejestnieakceptowalnazewzględu
naliczbępotencjalnychzbiorówczęstych.
ZbiórwszystkichpodzbiorówzbioruL,zewzględunarelacjęzawieraniasię,
tworzykratę,którejkresemdolnymjestzbiórpusty,natomiastkresemgórnymjest
całyzbiórL.PrzykładowąkratępodzbiorówzbioruL={A,B,C,D}przedstawia
rys.2.1.Celemalgorytmówodkrywaniazbiorówczęstychjestograniczenieliczby
analizowanychzbiorówelementówwystępującychwtejkracie.Podstawowezna-
czeniedlaefektywnościalgorytmuznajdowaniazbiorówczęstychmaspostrzeże-
nie,żemiarawsparciazbioruelementówmawłasnośćantymonotoniczności.
Rysunek2010KratapodzbiorówzbioruL={A,B,C,D}
Własnośćmonotoniczności.NiechbędziedanyzbiórelementówLorazjegozbiór
potęgowyJ=2|L|.Mówimy,żemiarafjestmonotonicznanazbiorzeJ,jeżeli:
∀X,YEJ:(X⊆Y)→f(X)<f(Y).
22
(2.19)
