时间序列,非常好
482IEEETRANSACTIONSONKNOWLEDGEANDDATAENGINEERING,VOL.18,NO.4,APRIL2006
AUnifyingFrameworkforDetectingOutliers
andChangePointsfromTimeSeries
Jun-ichiTakeuchi,Member,IEEE,andKenjiYamanishi,Member,IEEE
Abstract—Weareconcernedwiththeissueofdetectingoutliersandchangepointsfromtimeseries.Intheareaofdatamining,therehavebeenincreasedinterestintheseissuessinceoutlierdetectionisrelatedtofrauddetection,rareeventdiscovery,etc.,whilechange-pointdetectionisrelatedtoevent/trendchangedetection,activitymonitoring,etc.Although,inmostpreviouswork,outlierdetectionandchangepointdetectionhavenotbeenrelatedexplicitly,thispaperpresentsaunifyingframeworkfordealingwithbothofthem.Inthisframework,aprobabilisticmodeloftimeseriesisincrementallylearnedusinganonlinediscountinglearningalgorithm,whichcantrackadriftingdatasourceadaptivelybyforgettingout-of-datestatisticsgradually.Ascoreforanygivendataiscalculatedintermsofitsdeviationfromthelearnedmodel,withahigherscoreindicatingahighpossibilityofbeinganoutlier.Bytakinganaverageofthescoresoverawindowofafixedlengthandslidingthewindow,wemayobtainanewtimeseriesconsistingofmoving-averagedscores.Changepointdetectionisthenreducedtotheissueofdetectingoutliersinthattimeseries.Wecomparetheperformanceofourframeworkwiththoseofconventionalmethodstodemonstrateitsvaliditythroughsimulationandexperimentalapplicationstoincidentsdetectioninnetworksecurity.
IndexTerms—Timeseries,changepoint,datamining,networksecurity,ARmodel.
æ
1
1.1
INTRODUCTION
proposeaframeworkwhichcandealwithbothoftheissuesatonce.
In[16],[17],weproposedageneralframeworkforstatisticaloutlierdetection,undertheassumptionthateachdataisindependentlydrawnaccordingtoit.Init,weemployedasastatisticalmodelaGaussianmixturemodelforcontinuousvariableswhileahistogramdensityfordiscretevariables.Wedevelopedalgorithmsforonlinediscountinglearningofthesemodels,wheretheycantracktime-varyingdatasourcesadaptivelybygraduallyforget-tingout-of-datestatistics.Then,foranewinputdata,itsscoreiscalculatedintermsofitsdeviationfromthelearnedmodel,withahighscoreindicatingahighpossibilityofbeingastatisticaloutlier.
Inthispaper,weextendtheframeworkin[16],[17]towardthefollowingtwodirections:1)dealingwithtimeseriesand2)detectingchangepointsinit.
Asfor1),weconsidertime-seriesmodelssuchasAR(autoregression)model(see,e.g.,[1])inplaceofindependentmodelssuchasGaussianmixturesasin[16],[17].Weemployanalgorithmforonlinediscountinglearningofatime-seriesmodelandapplyittodetectingoutliersfromtimeseries.Ascoreforanygivendataiscalculatedintermsofitsdeviationfromthelearnedmodel,withahigherscoreindicatingahighpossibilityofbeinganoutlier.
Asfor2),wepresentanewtwo-stagetime-serieslearningscheme,whichconnectschangepointdetectiontooutlierdetection,theprocessofwhichissummarizedasfollows:First,bytakinganaverageofthescoresoverawindowofafixedlengthandslidingthewindow,weobtainanewtimeseriesconsistingofmoving-averagedscores.Changepointdetectionisthenreducedtotheissueofdetectingoutliersinthattimeseries.WenamethisschemeChangeFinder.
PublishedbytheIEEEComputerSociety
I
ContributionofThisPaper
DENTIFICATIONofoutliersinadatastreamhasbeenoneofthemostexcitingtopicsindatamining(e.g.,[11],[3],[16])andinstatistics(e.g.,[2])sinceitcanleadtothediscoveryofunexpectedandinterestingknowledge.Ontheotherhand,theissueofdetectingchangepointsintime-seriesdatahasextensivelybeenaddressedinstatistics(e.g.,[8])andhasbecomeoneoftheissuesreceivingvastattentionindatamining,whichisrecognizedaseventchangedetection[6]andcloselyrelatedtoactivitymonitoring[5].Here,bythetermchangepoint,wemeanatimepointatwhichthedatapropertiessuddenlychange.
Letusillustratetheseissuesthroughnetworkaccessloganalysisasanexample.Supposethatyouhaveadatastreamofnetworkaccesslogswhereeachrecordisspecifiedbynumericalvariablesincludingaccesstime,duration,etc.Wemayfirstlearnastatisticalregularityfromthedata,thendetectoutliersbyinvestigatinghowlargeeachdataisdeviatedfromtheregularity.Identifyingsuchoutliersmayleadtonetworkintrusiondetectionsincecriminalorsuspiciousactivitiesmayofteninducestatisticaloutliers(seee.g.,[3],[16]).Theproblemofchangepointdetectionisheretoidentifythetimewhenasignificantchangeofstatisticalregularityoftheaccesspatternhasoccurredorwhenaburstofoutliershasemerged.Conventionally,outlierdetectionandchangepointdetec-tionhavebeenaddressedindependently.Inthispaper,we
.TheauthorsarewiththeInternetSystemsResearchLaboratories,NECCorporation,1753Shimonumabe,Nakahara-ku,Kawasaki,Kanagawa,211-8666,Japan.
E-mail:tak@ap.jp.nec.comandk-yamanishi@cw.jp.nec.com.Manuscriptreceived27Oct.2004;revised1Apr.2005;accepted5Aug.2005;publishedonline17Feb.2006.
Forinformationonobtainingreprintsofthisarticle,pleasesende-mailto:tkde@computer.org,andreferenceIEEECSLogNumberTKDE-0281-0804.
1041-4347/06/$20.00ß2006IEEE
热门文档