Mining Sequential Patterns

MiningSequentialPatternsRakeshAgrawalRamakrishnanSrikant*IBMAlmadenResearchCenter650HarryRoad,SanJose,CA95120AbstractWearegivenalargedatabaseofcustomertransac-tions,whereeachtransactionconsistsofcustomer-id,transactiontime,andtheitemsboughtinthetransac-tion.Weintroducetheproblemofminingsequentialpattrriisoversuchdatabases.Wepresentthreealgo-rithmstosolvethisproblem,andempiricallyevalu-atetheirperformanceusingsyntheticdata.Twooftheproposedalgorithms,AprioriSomeandApriori-All,havecomparableperformance,albeitAprioriSomeperformsalittlebetterwhentheminimumnumberofcustomersthatmustsupportasequentialpatternislow.Scale-upexperimentsshowthatbothApri-oriSomeandAprioriAllscalelinearlywiththenum-berofcustomertransactions.Theyalsohaveexcel-lentscale-uppropertieswithrespecttothenumberoftransactioiispercustomerandthenumberofitemsinatransartion.1IntroductionDaIal)a~(~miningismotivatedbythedecisionsup-port.prol)lciiifacedbymostlargeretailorganizations.Progressinbar-codetechnologyhasmadeitpossibleforretailorganizationstocollectandstoremassiveamount.sofsalesdata,referredtoasthebasketdata.Arecordinsuchdatatypicallyconsistsofthetrans-actiont1at.eandtheitemsboughtinthetransaction.Veryoften,datarecordsalsocontaincustomer-id,par-ticularlywhenthepurchasehasbeenmadeusingacredit.cardorafrequent-buyercard.Catalogcompa-niesalsocollectsuchdatausingtheorderstheyre-ceive.Weint.roducetheproblemofminingsequenttalpat-ternsoverthisdata.Anexampleofsuchapatternis‘AlsoDepartmentofComputerScience,UniversityofWis-c