Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.4.PODSTAWOWYALGORYTMODKRYWANIAREGUŁ
Własnośćmonotonicznościmiaryfoznacza,żejeżeliXjestpodzbiorem
zbioruY,towartośćmiaryf(X)niemożebyćwiększaodf(Y).
Własnośćantymonotoniczności.NiechbędziedanyzbiórelementówLorazjego
zbiórpotęgowyJ=2|L|.Mówimy,żemiarafjestantymonotonicznanazbiorze
J,jeżeli:
∀X,YEJ:(X⊆Y)→f(Y)<f(X).
(2.20)
Własnośćantymonotonicznościmiaryfoznacza,żejeżeliXjestpodzbio-
remzbioruY,towartośćmiaryf(Y)niemożebyćwiększaodf(X).Antymo-
notonicznośćmiarywsparciazbioruoznacza,żezbiórXjestzbioremczęstym
wtedyitylkowtedy,gdywszystkiepodzbioryzbioruXsąrównieżzbioramiczę-
stymi.Innymisłowy,jeżelizbiórXniejestzbioremczęstym,tożadennadzbiór
zbioruXniejestzbioremczęstym.Tooznacza,żeniemusimyrozważaćwspar-
ciazbioruX,któregojakikolwiekpodzbiórniejestzbioremczęstym.Własność
antymonotonicznościmiarywsparciamożnawykorzystaćdoredukcjiprzestrze-
niposzukiwańzbiorówczęstych.Rozważmyponowniekratępodzbiorówzbio-
ruL={A,B,C,D}przedstawionąnarys.2.2.Jeżeliwsparciezbioru{A,C}jest
mniejszeniżwartośćminimalnegowsparciaminsup,tożadenznadzbiorówzbio-
ru{A,C},czyli{A,B,C},{A,C,D},{A,B,C,D},niebędziezbioremczęstym.Mo-
żemyzatemzredukowaćprzestrzeńposzukiwańzbiorówczęstych,usuwajączniej
wszystkienadzbioryzbioru{A,C}.
Rysunek2020KratapodzbiorówzbioruL={A,B,C,D}zawierającapodzbiór{A,C},któryniejest
częsty
23
