Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
descriptionsfromdifferentlevelsoftheconcepthierarchy.Quantitative
associationrules[177]concernnotonlycategoricalbutalsonumerical
attributes.Finally,multidimensionalassociationrules[107]refertodataor
transactionslocatedinamultidimensionalspace.
Frequentitemsetminingbelongstofundamentaldataminingproblems,and
isarguablythemostsignificantcontributionofthedatabasecommunitytothe
areaofknowledgediscovery,notonlybecauseofitsnumerousapplicationsbut
alsobecauseofitsrelationshipswithandinfluenceonotherdatamining
techniques.Frequentitemsetsinspiredtheresearchonothertypesoffrequent
patternsincludingsequentialpatterns[10]andepisodes[128]aswellas
structuralpatternssuchasfrequentsubgraphsandsubtrees[190].Typically,
specificproblems(e.g.,miningclosedormaximalpatterns)statedinthecontext
offrequentitemsetslatercarriedovertoothertypesoffrequentpatterns.
Similarly,manyalgorithmsforminingfrequentpatternsofotherkindsare
adaptationsofalgorithmsinitiallyproposedfordiscoveryoffrequentitemsets.
Moreover,sometechniquesproposedforfrequentitemsetminingareso
universalthattheycanbeadoptedtoproblemsapparentlynotdirectlyrelatedto
frequentpatternminingsuchasclustering[3],icebergcubecomputation[19],as
wellasinclusionandfunctionaldependencies[126].
Aswementionedearlier,associationrulescanbeeasilygeneratedfrom
discoveredfrequentitemsets.Thissanctionedtheroleoffrequentitemsetsas
dataminingprimitivesthatshouldbethetargetofsupportprovidedfordata
miningbydatabasemanagementsystems.Suchaviewoffrequentitemsetshas
beenfurtherjustifiedbytheintroductionofalgorithmssolvingotherdatamining
problemsbystartingwiththediscoveryoffrequentitemsets.Suchalgorithms
havebeenproposedforsequentialpatternmining[10],classification[123],and
clustering[77].
2.2.FormulationoftheFrequentItemsetMiningProblem
Definition2.1
LetIbeasetofliterals,calleditems.AnitemsetXisasetofitemsfromI
(X;I).Thesizeofanitemsetisthenumberofitemsinit.Anitemsetofsizekis
calledak-itemset.
Definition2.2
AtransactionoverIisacoupleT=(tid,X),wheretidisatransaction
identifierandXisanitemset.AdatabaseDoverIisasetoftransactionsoverI
suchthateachtransactionhasauniqueidentifier.
Definition2.3
AtransactionT=(tid,X)supportsanitemsetYifY;X.Thesupport(also
calledabsolutesupport)ofanitemsetYinDisthenumberoftransactionsinD