文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > A unifying framework for detecting outliers and change points from time series
侵权投诉

A unifying framework for detecting outliers and change points from time series

时间序列,非常好

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

第1页

TOP相关主题

你可能喜欢

热门文档

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