文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Optimizing Constraint-Based Mining by Automatically Relaxing Constraints
侵权投诉

Optimizing Constraint-Based Mining by Automatically Relaxing Constraints

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-

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email