Fast Algorithms for Mining Generalized Association Rules and Sequential Patterns in Massive Databases

Abstract

Dataminingisanemergingfieldinthedatabasetechnology.Thegoalofdataminingisknowledgediscovery,thatis,toexcavateinformationfromhistoricalorganizationaldatabasesthatcanbeusedtoguidebusinessstrategiesanddecisionmaking.Inthisdissertation,fastandefficientalgorithmsformininggeneralizedassociationrulesandsequentialpatternsinmassivedatabasesarepresented.Anassociationrule,forexample,couldbe“98%ofthecustomerswhobuybreadandbutteralsobuyjam”.Theproblemistofindoutallsuchruleswhosefrequencyisgreaterthansomeuser-definedminimumsupport.Thisthesisdealswithalgorithmicandsystemsaspectsofscalabledataminingalgorithmsappliedtomassivedatabases.Thealgorithmicaspectsfocusonthedesignofefficientandscalablealgorithmsfortwo-keyrulediscoverytechniques-generalizedassociationrulesandgeneralizedsequentialpatterns.Thesystemsaspectsdealwiththescalableimplementationofthesemethodsonsequentialmachines.Twoincrementalupdatedtechniquesformininggeneralizedassociationrulesandsequentialpatternstogeneraterulesandpatternsinmassivedatasetsarepresented.Thefirstoneisthedatabase,whichisfixedwithchangingminimumsupport.Thesecondoneisthegivenoriginaldatabase,whennewincrementdb(transactionaldatabase)isaddedtotheoriginaldatabaseDBwithfixedminimumsupportandminimumconfidence. Usingpartitionmethodassociationrulesandsequentialpatternshavebeengenerated.Themajoradvantageofthepartitionmethodisscanningthedatabaseexactlytwotimestocomputethelargeitemsetsbymeansofconstructingatransactionlistforeachlargeitemset.Insequentialpattern,largemaximalsequencesaregeneratedusingparallelpartitionmethod.Thespeed-upandsize-uppropertiesshowthattheproposedparallelpartitionmethodisbetterthansequentialpartitionmethod.Themethodofpatterndecompositioncanavoidthecostlyprocessofcandidatesetgenerationandsaveagreatamountofcomputingtimewithreduceddatabasesize.TheproblemofmininggeneralizedassociationrulesandsequentialpatternsusingTIDmethodhasbeenanalyzed.Byusingthismethod,thecostofexecutiontimehasbeenreducedandlinearlyscalable.Anothermostimportantproblemofmininggeneralizedassociationrulesinthedistributedenvironmenthasalsobeenpresentedhere.ThecomputingtimeofthefastdistributedalgorithmisintheO(n),whereastheparallelbasedalgorithmformininggeneralizedassociationruleisintheO(n2).Hence,theproposedfast-distributedalgorithmismorereliablethanthepreviousparallelandsequentialalgorithm.Extensiveexperimentshavebeenconductedforsolvingtheabovetwoproblems(generalizedassociationrulesandgeneralizedsequentialpatterns),showingimmenseimprovementoverthepreviousapproaches,withlinearscalabilityindatabasesize.