Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ROZDZIAŁ2.ODKRYWANIEASOCJACJI
reguł,dlaktórychnależyobliczyćwsparcieiufność,jestbardzoduża.Cowię-
cej,najczęściejokazujesię,żeliczbawygenerowanychregułasocjacyjnych,które
niespełniająwarunkówminimalnegowsparciaiminimalnejufności,jestznacznie
większaodliczbyotrzymanychsilnychregułasocjacyjnych.Rozważmyponow-
nie,dlailustracji,bazędanychDzprzykładu2.2.ZbiórelementówL=4.Liczba
wszystkichmożliwychregułasocjacyjnych,któremożnawygenerowaćdlazbioru
elementówL,wynosi3|L|−2|L|+1+1=50.Liczbawszystkichsilnychbinarnych
regułasocjacyjnychwygenerowanychdlabazydanychDzprzykładu2.2wyno-
si14,tojest28%liczbywszystkichmożliwychregułasocjacyjnych,któremożna
wygenerowaćdlazbioruelementówL.Oznaczatomarnotrawstwoczasupoświę-
conegonaobliczaniewartościwsparciaiufnościodrzuconychreguł.Wszystkoto
powoduje,żepodejścienaiwnejestwpraktycemałoprzydatne.
Pojawiasięzatempytanie,wjakisposóbograniczyćliczbęgenerowanychre-
gułasocjacyjnych,takabyniezachodziłakoniecznośćobliczaniawartościwspar-
ciaiufnościodrzucanychreguł?Odpowiedźnatopytaniebrzmi:należy,generując
regułyasocjacyjne,osobnorozważaćograniczeniaminimalnegowsparciaimini-
malnejufności.Zauważmy,żezgodniezewzorem(2.17)idefinicjąwsparciazbio-
ruXwsparcieregułyX→YjestrównewsparciuzbioruX∪Y.Łatwozauważyć,
żewsparcieregułyY→XjestrównieżrównewsparciuzbioruX∪Y.Oznacza
to,żejeżeliwsparciezbioruX∪Yjestmniejszeniżminimalnewsparcieminsup,
towówczasmożemypominąćobliczanieufnościregułasocjacyjnychX→Yoraz
Y→X,gdyżregułytezostanąodrzucone.Jeszczewiększyzyskczasowyuzysku-
jemywprzypadkuodrzuceniazbioru3-elementowegoX∪Y∪Z.Jeżeliwsparcie
zbioruX∪Y∪Zjestmniejszeniżminimalnewsparcieminsup,towówczasmoże-
mypominąćobliczanieufnościnastępujących6regułasocjacyjnych:
X→Y,Z,
Y→X,Z,
Z→X,Y,
X,Y→Z,
X,Z→Y,
Y,Z→X.
Wogólnymprzypadkuodrzuceniezbioruk-elementowegoX1∪X2∪...∪Xk,
któregowsparciejestmniejszeniżminimalnewsparcieminsup,pozwalapomi-
nąćobliczanieufności2k−2regułasocjacyjnych2).Powyższespostrzeżeniale-
głyupodstawwiększościalgorytmówodkrywaniabinarnychregułasocjacyjnych,
którezostanąprzedstawionewnastępnychpunktachtegorozdziału.
2)UdowodnienietegofaktupozostawiamyCzytelnikowijakoćwiczenie;patrzzadania.
20
