Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
18
correspondingtothisfrequencythresholdinDis3.Alltheitemsetsfrequentin
Dwithrespecttominfreq=50%(i.e.,supportedbyatleast3transactionsfrom
D)arelistedinTable2.1togetherwiththeirsupportsandfrequencies.
Table2.1.Frequentitemsetsintheexampledatabase
Itemset
{a,c,d}
{a,b}
{a,d}
{c,d}
{a,c}
{a}
{b}
{c}
{d}
Support
5
3
4
4
3
4
4
3
3
Frequency
100%
60%
80%
80%
60%
80%
80%
60%
60%
u
2.3.ComputationalComplexityoftheProblem
Theproblemofminingfrequentitemsetsfromthetimeofitsintroductionhas
beenintuitivelyconsideredascomputationallyhard.Thereasonbehindthis
intuitionwasthattheitemsetsearchspaceisexponentialtothenumberof
differentitemsinthedatabase.Intheworstcase,allsubsetsofthesetIof
differentitemspresentinthedatabasemaybefrequent,whichwouldrequire
exponentialtimejusttooutputtheminingresult(2
|I|-1nonemptysubsetsofI),
notmentioningthecostofcheckingtheirfrequency.Nevertheless,theformal
proofofcomputationalhardnesswasnotpresentforadecadesincethe
formulationoffrequentitemsetminingproblem.
Formally,frequentitemsetminingisanenumerationproblem(adatamining
algorithmhastoenumerateandproduceallfrequentitemsetsinagiven
database).Gunopulosetal.[74]approachedthecomputationalcomplexityof
frequentitemsetminingbyanalyzingcomplexityofitsrelatedcounting
problem,i.e.,findingthenumberoffrequentitemsets.
Theoreticalfoundationsforstudyingcomputationalcomplexityofcounting
problemswereprovidedbyValiant[185],whointroducedtheclass#Pof
countingproblemsforwhichanysinglesolutioncanbecomputedby
anondeterministicTuringmachineinpolynomialtime.Thetheoryof
computationalcomplexityofcountingproblemscontainsmanyanalogiestothe
moreinvestigatedtheoryfordecisionproblems[61].Inparticular,itdefinesthe
#P-completeand#P-hardclassesofproblems.AnalogouslytoNP-completeness
whichcapturesthehardestproblemsfromtheclassofdecisionproblemsNP
[61],#P-completenessreferstothehardestproblemsin#P.Formally,acounting
problemis#P-completeifallproblemsin#Preducetoit(byapplying
polynomialtimeTuringreduction[61,185])andtheproblemitselfbelongsto