Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.3.ODKRYWANIEBINARNYCHREGUŁASOCJACYJNYCH
2.3.Odkrywaniebinarnychregułasocjacyjnych:alternatywne
sformułowanieproblemu
Sformułowanieproblemuodkrywaniasilnych,jednopoziomowych,jednowymia-
rowych,binarnychregułasocjacyjnych,przedstawionewpodrozdz.2.2,abstrahuje
odrzeczywistychmetodprzechowywaniadanych.Założenie,żeobiektemeksplo-
racjidanychjestzero-jedynkowatablicaobserwacji,jestmałorealistycznewprak-
tyce.Stądwliteraturzeznacznieczęściejspotykamyalternatywnesformułowanie
problemuodkrywaniabinarnychregułasocjacyjnych.
NiechL={l1,l2,...,lm}oznaczazbiórliterałównazywanychdalejelemen-
tami.Dowolny,niepustypodzbiórTzbioruL,T⊆LiT/=∅,będziemynazywać
transakcjąelementówlub,krótko,transakcją.RozmiaremtransakcjiT,oznaczo-
!
nymsize(T),nazywaćbędziemyliczbęelementówwtransakcjiT.Baządanych
DnazywaćbędziemyzbiórtransakcjiT,D=(T1,T2,...,Tn),gdzieTi⊆L,i=
1,2,...,n.Mówimy,żetransakcjaTwspieraelementxEL,jeżelixnależydo
T,xET.Mówimy,żetransakcjaTwspierazbiórX⊆L,jeżeliTwspierakażdy
elementzezbioruX,X⊆T.WsparciemzbioruXwbaziedanychD,oznaczonym
wsparcie(X),nazywaćbędziemyilorazliczbytransakcjiwD,którewspierająX,
doliczbywszystkichtransakcjiwD.
BinarnąregułąasocjacyjnąnazywamyrelacjępostaciX→Y,gdzieX⊂L,
Y⊂LiX∩Y=∅.ZbiórXnazywamypoprzednikiemreguły(ang.body,an-
tecedent),azbiórY–następnikiemreguły(ang.head,consequent).Mówimy,że
!
binarnaregułaasocjacyjnaX→YmawsparcieswbaziedanychD,0<s<1,
jeżelis%transakcjiwDwspieraX∪Y.Mówimy,żebinarnaregułaasocjacyjna
X→YmaufnośćcwbaziedanychD,0<c<1,jeżelic%transakcjiwD,które
wspierająX,wspierarównieżY.Formalnie,definicjewsparciaiufnościmożna
zapisaćwnastępującysposób:
wsparcie(X→Y)=
|{TiED|TiwspieraX∪Y}|
|D|
,
ufność(X→Y)=
|{TiED|TiwspieraX∪Y}|
|{TjED|TjwspieraX}|
.
(2.17)
(2.18)
Wsparciejestistotnąmiarąwartościującądanąregułęasocjacyjną,gdyżokre-
ślaliczbętransakcjiwanalizowanymzbiorzeD,którepotwierdzajądanąregułę.
Odwołującsiędoprzykładusupermarketu,wsparcieregułyokreślaliczbęklien-
tów,którzyzachowująsięzgodniezdanąregułą.Łatwozauważyć,żemiarawspar-
ciajestsymetrycznawzględemzbiorówstanowiącychpoprzednikinastępnikre-
guły,toznaczy,jeżeliregułaasocjacyjnaX→YmawzbiorzeDwsparcies,to
takiesamowsparciewzbiorzeDmaregułaasocjacyjnaY→X.Regułyonie-
wielkimwsparciusąmałoreprezentatywne,gdyżopisujązachowanieniewielkiej
17
