In constraint-based mining, the monotone and antimonotone properties are exploited to reduce the search space. Even if a constraint has not such suitable properties, existing algorithms can be re-used thanks to an approximation, called relaxation. In this
OptimizingConstraint-BasedMiningbyAutomaticallyRelaxingConstraints
ArnaudSouletBrunoCr´emilleuxGREYC,CNRS-UMR6072,Universit´edeCaen
CampusC otedeNacreF-14032CaenC´edexFrance
{Forename.Surname}@info.unicaen.frAbstract
Inconstraint-basedmining,themonotoneandanti-monotonepropertiesareexploitedtoreducethesearchspace.Evenifaconstrainthasnotsuchsuitableproperties,existingalgorithmscanbere-usedthankstoanapproxima-tion,calledrelaxation.Inthispaper,weautomaticallycom-putemonotonerelaxationsofprimitive-basedconstraints.First,weshowthatthelatterareasuperclassofcombina-tionsofbothkindsofmonotoneconstraints.Second,weaddtwooperatorstodetectthepropertiesofmonotonicityofsuchconstraints.Finally,wede nerelaxingoperatorstoobtainmonotonerelaxationsofthem.
1Introduction
Miningpatternsunderconstraintsisasigni cant eldofresearchindatamining.Manyconstraintslikeinteresting-nessmeasuresorsyntacticconstraintsareusefultoachieverelevantpatterns.Althoughtheconstraintischosenbytheuser,theminingstephastobeautomatedinordertofacili-tatetheKDDprocess.Inparticular,tohandletheconstraintshouldbeindependentfromtheuser.
Manyalgorithmsreducethesearchspaceofpatternsbyusingthemonotonicityproperty[9].Unfortunately,mostoftheconstraintsareneithermonotone,noranti-monotone.Nevertheless,such“dif cult”constraintscanbeextractedbyre-usingavailablealgorithms.Indeed,theconstraintisapproximatedbyanotherhavingsuitablemonotoneprop-erty[5,4].Thecollectionofextractedpatternscorrespond-ingtothisapproximationhastobeasupersetofthecollec-tionsatisfyingtheoriginalconstraint.Thereby,inapost-processedstep,abasic lteringselectsthedesiredpatterns.Theapproximatedconstraintiscalledrelaxation.Tothebestofourknowledge,thereisnoexistingtheoreticalworkwhichproposesageneralapproachtoobtainrelaxationshavingmonotoneproperties.Aspecialistofdataminingoramathematiciancancomputearelaxationofagivencon-
straint.However,aprocessoracommonuserhavenottheabilityto ndit.
Inthispaper,weproposethreemaincontributions.At rst,weshowthattheprimitive-basedconstraintsareasu-perclassofbothkindsofmonotoneconstraintsandtheircombinations.Secondly,weproposeanoriginalapproachtodetectmonotoneconstraintsbyapplyingnewformalop-erators,namedthemonotoneandanti-monotonetestingoperators.Finally,weprovideamonotoneandananti-monotonerelaxationsforeachprimitive-basedconstraint,theserelaxationsareautomaticallyobtainedbythemono-toneandanti-monotonerelaxingoperators.
Thispaperisorganizedinthefollowingway.Section2introducesthebasicnotationsandrelatedworks.Section3depictsthesetofconstraintsthatweaddressandlinksthemtothemonotoneconstraints.Section4de nestheopera-torswhichallowsustodetectmonotonicity.Finally,theseoperatorsareexploitedtorelaxconstraintsinSection4.
2Contextandrelatedworks
Basicde nitionsAtransactionaldatasetDisatriplet(A,O,R)whereAisasetofattributes,Oisasetofob-jectsandR A×Oisabinaryrelationbetweentheat-tributesandtheobjects.(a,o)∈Rexpressesthattheobjectohastheattributea.Apatternisasetofattributes.TheaimofconstrainedpatternsminingistoextractallpatternspresentinDandsatisfyingapredicateq(alsocalledqueryorconstraint).Manypredicateshaveaparticularpropertynamedmonotonicity.Aconstraintqismonotone(resp.anti-monotone)accordingtothespecializationiffwheneverX Ythenq(X) q(Y)(resp.q(Y) q(X)).Thesetofmonotone(resp.anti-monotone)constraintsisde-notedbyQM(resp.QAM).Letusremarkthatweof-tenuse“(anti-)monotone”insteadof“monotoneandanti-monotone”whenthatisnotambiguous.
Table1providesseveralexamplesofconstraintswiththeirpropertiesaboutmonotonicity(i.e.,QMandQIngeneral,aconstraintisnotmonotone,neitherAM).anti-
Constraint based mining is an ongoing area of research. Two important categories of constraints are monotone and antimonotone [13]. Anti-monotone ...
Constraint based mining is an ongoing area of research. Two important categories of constraints are monotone and antimonotone [13]. Anti-monotone ...
热门文档