资源描述:
《efficient mining of association rules using closed itemset lattices.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、InformationSystemVol.24,No.1.pp.%-$6,19Bp01999Else&rScienceLtd.AllrightsreeervedPrintedinGreatBritain(!so&4sTep$20.00+0.00PII:s0999479(99)99998-4EFFICIENTMININGOFASSOCIATIONRULESUSINGCLOSEDITEMSETLATTICES+NICOLASPASQUIER,YVESBASTIDE,RAFIKTAOUILandLOTFILAKHALLaboratoired’In
2、formatique(LIMOS),Universit.6BIaisePascaI-CIerznont-FerrwxiII,CompiexeScientifiquedesC&saux,63177Aubl&reCedexFkauce(Rearivcd13June1999;infinalretiedform16October1999)Abstract-Dlscoverisssociatlonrulesisoneofthemostimportanttaskindatamining.Manye&ientalgorithmshaveYssnpropo
3、sedintheliterature.ThemostnoticeableareApriori,Mannilasalgorithm,Partition,SamplingandDIC,thatareallbasedontheAprioriminingmethod:pruningthesubsetlattice(items&lattice).Inthispaperweproposeanefficientalgorithm,calledClose,basedonanewminingmethod:pruningtheclosedsetlattice(
4、closeditemsetlattice).Thislattice,whichisasub-orderofthes&retlattice,iscloselyreIatedtoWilIesconceptlatticeinformalconceptanaIysls.ExperimentscomparingCl-toauoptimlsedversionofApriorlshowedthatCloseisverye&lentforminingdense.and/orcorrelateddatasuchascensusstyledata,andper
5、formsreasonablywellformarlret~atyledata~1999Eteavierseien~Ltd.AllrightstpaervedKeywovdzxDataMining,KnowlsdgeDiiry,AssociationRules,DataClustering,Lattices,A@ri6hms1.INTRODUCTIONOneofthemostimportanttaskindataminingisthediscoveryofassocicrtionrulesfirstin-troducedin[l].Thea
6、imofassociationrulediscoveryistoidentifyrelationshipsbetweenitemsinverylargedatabases.Forexample,givenamarketbasketdatabase,itwouIdbeinterestingfordecisionsupporttoknowthefactthat80%ofcustomerswhoboughtcerealsandsugaralsoboughtmilk.Inacensusdatabase,weshoulddiscoverthat60%
7、ofpersonswhoworkedlastyearearnedleasthantheaverageincome,orinamedicaldatabase,that70%ofpatientswhoarestiffandhavefeveralsohaveheadaches.Agrawalsstatementoftheproblemofdiscoveringassociationrulesinmarketbasketdatabasesisthefollowing[l,21.LetZ={ir,ia,...,im)beasetofmliterals
8、calleditems.Letthedatabasev={tr,ts,...,t,,}beasetofntransactions,eachoneconsistingofaseto