數(shù)據(jù)挖掘之異常檢測

AnomalyDetection:AintroductionSourceofslides: TutorialAtAmericanStatisticalAssociation(ASA2008)

JiaweiHan-datamining:conceptsandtechniques

TutorialattheEuropeanConferenceonPrinciplesandPracticeofKnowledge DiscoveryinDatabasesSpeaker:

WentaoLiOutlineDefinitionApplicationMethodsLimitedtime,SoIjustdrawthepictureofanomalydetection,formoredetail,pleaseturntothepaperforhelp.WhatareAnomalies?Anomalyisapatterninthedatathatdoesnotconformtotheexpected

behaviorAnomalyisAdataobjectthatdeviatessignificantlyfromthenormalobjectsasifitweregeneratedbyadifferentmechanismAlsoreferredtoasoutliers,exceptions,peculiarities,surprises,etc.Anomaliestranslatetosignificant(oftencritical)reallifeentitiesCyberintrusionsCreditcardfraudFaultsinmechanicalsystemsRelatedproblemsOutliersaredifferentfromthenoisedataNoiseisrandomerrororvarianceinameasuredvariableNoiseshouldberemovedbeforeoutlierdetectionOutliersareinteresting:ItviolatesthemechanismthatgeneratesthenormaldataOutlierdetectionvs.noveltydetection:earlystage,outlier;butlatermergedintothemodelKeyChallengesDefiningarepresentativenormalregionischallengingTheboundarybetweennormalandoutlyingbehaviorisoftennotpreciseAvailabilityoflabeleddatafortraining/validationTheexactnotionofanoutlierisdifferentfordifferentapplicationdomainsDatamightcontainnoiseNormalbehaviorkeepsevolvingAppropriateselectionofrelevantfeaturesMapRelatedareas(theory)Application(practice)ProblemformulationDetectioneffect+AspectsofAnomalyDetectionProblemNatureofinputdataWhatisthecharacteristicofinputdataAvailabilityofsupervisionNumberoflabelTypeofanomaly:point,contextual,structuralTypeofanomalyOutputofanomalydetectionScorevslabelEvaluationofanomalydetectiontechniquesWhatkindofdetectionisgoodInputDataMostcommonformofdatahandledbyanomalydetectiontechniquesisRecordDataUnivariateMultivariateInputDataMostcommonformofdatahandledbyanomalydetectiontechniquesisRecordDataUnivariateMultivariateInputData–NatureofAttributesNatureofattributesBinaryCategoricalContinuousHybridcategoricalcontinuouscontinuouscategoricalbinaryInputData–ComplexDataTypesRelationshipamongdatainstancesSequentialTemporalSpatialSpatio-temporalGraphDataLabelsSupervisedAnomalyDetectionLabelsavailableforbothnormaldataandanomaliesSemi-supervisedAnomalyDetectionLabelsavailableonlyfornormaldataUnsupervisedAnomalyDetectionNolabelsassumedBasedontheassumptionthatanomaliesareveryrarecomparedtonormaldataPayattention:heresomematerialsgivedifferentdescriptions,andwetreatadoptthedefinitionherethoughitisabitambiguouswiththetraditionaldefinitionalTypeofAnomalies*PointAnomaliesContextualAnomaliesCollectiveAnomaliesPointAnomaliesAnindividualdatainstanceisanomalousw.r.t.thedataXYN1N2o1o2O3ContextualAnomaliesAnindividualdatainstanceisanomalouswithinacontextRequiresanotionofcontextAlsoreferredtoasconditionalanomalies*Dangerous+theftcondition=theftMoneyconsumer:thepoorandtherich*XiuyaoSong,MingxiWu,ChristopherJermaine,SanjayRanka,ConditionalAnomalyDetection,IEEETransactionsonDataandKnowledgeEngineering,2006.NormalAnomalyCollectiveAnomaliesAcollectionofrelateddatainstancesisanomalousRequiresarelationshipamongdatainstancesSequentialDataSpatialDataGraphDataTheindividualinstanceswithinacollectiveanomalyarenotanomalousbythemselvesAnomalousSubsequenceOutputofAnomalyDetectionLabelEachtestinstanceisgivenanormaloranomalylabelThisisespeciallytrueofclassification-basedapproachesScoreEachtestinstanceisassignedananomalyscoreAllowstheoutputtoberankedRequiresanadditionalthresholdparameterEvaluationofAnomalyDetection–F-valueAccuracyisnotsufficientmetricforevaluationExample:networktrafficdatasetwith99.9%ofnormaldataand0.1%ofintrusionsTrivialclassifierthatlabelseverythingwiththenormalclasscanachieve99.9%accuracy!!!!!anomalyclass – Cnormalclass –NCFocusonbothrecallandprecisionRecall(R) = TP/(TP+FN)?truepredictedanomaly/allanomalyPrecision(P) = TP/(TP+FP)?truepredictedanomaly/allpredictedF–measure = 2*R*P/(R+P)=EvaluationofOutlierDetection–ROC&AUCStandardmeasuresforevaluatinganomalydetectionproblems:Recall(Detectionrate)-ratiobetweenthenumberofcorrectlydetectedanomaliesandthetotalnumberofanomaliesFalsealarm(falsepositive)

rate–ratio

betweenthenumberofdatarecords

fromnormalclassthataremisclassified

asanomaliesandthetotalnumberof

datarecordsfromnormalclassROCCurveisatrade-offbetween

detectionrateandfalsealarmrateAreaundertheROCcurve(AUC)is

computedusingatrapezoidruleThebest:|_theworest:_|anomalyclass – Cnormalclass –NCAUCIdealROCcurveApplicationsofAnomalyDetectionNetworkintrusiondetectionInsurance/CreditcardfrauddetectionHealthcareInformatics/MedicaldiagnosticsIndustrialDamageDetectionImageProcessing/VideosurveillanceNovelTopicDetectioninTextMining…IntrusionDetectionIntrusionDetection:Processofmonitoringtheeventsoccurringinacomputersystem(inner)ornetwork

(outer)andanalyzingthemforintrusionsIntrusionsaredefinedasattemptstobypassthesecuritymechanismsofacomputerornetwork?ChallengesTraditionalsignature-basedintrusiondetection

systemsarebasedonsignaturesofknown

attacksandcannotdetectemergingcyberthreatsSubstantiallatencyindeploymentofnewly

createdsignaturesacrossthecomputersystemAnomalydetectioncanalleviatethese

limitationsFraud

DetectionFrauddetectionreferstodetectionofcriminalactivitiesoccurringincommercialorganizationsMalicioususersmightbetheactualcustomersoftheorganizationormightbeposingasacustomer(alsoknownasidentitytheft).TypesoffraudCreditcardfraudInsuranceclaimfraudMobile/cellphonefraudInsidertradingChallengesFastandaccuratereal-timedetectionMisclassificationcostisveryhighHealthcareInformaticsDetectanomalouspatientrecordsIndicatediseaseoutbreaks,instrumentationerrors,etc.KeyChallengesOnlynormallabelsavailableMisclassificationcostisveryhighDatacanbecomplex:spatio-temporalIndustrialDamageDetectionIndustrialdamagedetectionreferstodetectionofdifferentfaultsandfailuresincomplexindustrialsystems,structuraldamages,intrusionsinelectronicsecuritysystems,abnormalenergyconsumption,etc.Example:AircraftSafetyAnomalousAircraft(Engine)/FleetUsageAnomaliesinenginecombustiondataTotalaircrafthealthandusagemanagementKeyChallengesDataisextremelyhuge,noisyandunlabelledMostofapplicationsexhibittemporalbehaviorDetectinganomalouseventstypicallyrequireimmediateinterventionImageProcessingDetectingoutliersinaimageorvideomonitoredovertimeDetectinganomalousregionswithinanimageUsedinmammographyimageanalysisvideosurveillancesatelliteimageanalysisKeyChallengesDetectingcollectiveanomaliesDatasetsareverylargeAnomalyTaxonomy*AnomalyDetectionContextualAnomalyDetectionCollectiveAnomalyDetectionOnlineAnomalyDetectionDistributedAnomalyDetectionPointAnomalyDetectionClassificationBasedRuleBasedNeuralNetworksBasedSVMBasedNearestNeighborBasedDensityBasedDistanceBasedStatisticalParametricNon-parametricClusteringBasedOthersInformationTheoryBasedSpectralDecompositionBasedVisualizationBasedStatisticalApproachesStatisticalapproachesassumethattheobjectsinadatasetaregeneratedbyastochasticprocess(agenerativemodel)Idea:learnagenerativemodelfittingthegivendataset,andthenidentifytheobjectsinlowprobabilityregionsofthemodelasoutliersMethodsaredividedintotwocategories:parametricvs.non-parametric

ParametricmethodAssumesthatthenormaldataisgeneratedbyaparametricdistributionwithparameterθTheprobabilitydensityfunctionoftheparametricdistributionf(x,θ)givestheprobabilitythatobjectxisgeneratedbythedistributionThesmallerthisvalue,themorelikelyxisanoutlierNon-parametricmethodNotassumeana-prioristatisticalmodelanddeterminethemodelfromtheinputdataNotcompletelyparameterfreebutconsiderthenumberandnatureoftheparametersareflexibleandnotfixedinadvanceExamples:histogramandkerneldensityestimationParametricMethodsI:DetectionUnivariateOutliersBasedonNormalDistributionUnivariatedata:AdatasetinvolvingonlyoneattributeorvariableOftenassumethatdataaregeneratedfromanormaldistribution,learntheparametersfromtheinputdata,andidentifythepointswithlowprobabilityasoutliersEx:Avg.temp.:{24.0,28.9,28.9,29.0,29.1,29.1,29.2,29.2,29.3,29.4}UsethemaximumlikelihoodmethodtoestimateμandσTakingderivativeswithrespecttoμandσ2,wederivethefollowingmaximumlikelihoodestimatesFortheabovedatawithn=10,wehaveThen(24–28.61)/1.51=–3.04<–3,24isanoutliersinceParametricMethodsI:TheGrubb’sTestUnivariateoutlierdetection:TheGrubb'stest(maximumnormedresidualtest)─anotherstatisticalmethodundernormaldistributionForeachobjectxinadataset,computeitsz-score:xisanoutlierifwhereisthevaluetakenbyat-distributionatasignificancelevelofα/(2N),andNisthe#ofobjectsinthedatasetParametricMethodsII:DetectionofMultivariateOutliersMultivariatedata:AdatasetinvolvingtwoormoreattributesorvariablesTransformthemultivariateoutlierdetectiontaskintoaunivariateoutlierdetectionproblemMethod1.ComputeMahalaobisdistanceLetōbethemeanvectorforamultivariatedataset.MahalaobisdistanceforanobjectotoōisMDist(o,ō)=(o–ō)TS–1(o–ō)whereSisthecovariancematrixUsetheGrubb'stestonthismeasuretodetectoutliersMethod2.Useχ2–statistic:whereEiisthemeanofthei-dimensionamongallobjects,andnisthedimensionalityIfχ2–statisticislarge,thenobjectoiisanoutlierParametricMethodsIII:UsingMixtureofParametricDistributionsAssumingdatageneratedbyanormaldistributioncouldbesometimesoverlysimplifiedExample(rightfigure):TheobjectsbetweenthetwoclusterscannotbecapturedasoutlierssincetheyareclosetotheestimatedmeanToovercomethisproblem,assumethenormaldataisgeneratedbytwonormaldistributions.Foranyobjectointhedataset,theprobabilitythatoisgeneratedbythemixtureofthetwodistributionsisgivenbywherefθ1andfθ2aretheprobabilitydensityfunctionsofθ1andθ2

ThenuseEMalgorithmtolearntheparametersμ1,σ1,μ2,σ2fromdataAnobjectoisanoutlierifitdoesnotbelongtoanyclusterNon-ParametricMethods:DetectionUsingHistogramThemodelofnormaldataislearnedfromtheinputdatawithoutanyaprioristructure.Oftenmakesfewerassumptionsaboutthedata,andthuscanbeapplicableinmorescenariosOutlierdetectionusinghistogram:FigureshowsthehistogramofpurchaseamountsintransactionsAtransactionintheamountof$7,500isanoutlier,sinceonly0.2%transactionshaveanamounthigherthan$5,000Problem:HardtochooseanappropriatebinsizeforhistogramToosmallbinsize→normalobjectsinempty/rarebins,falsepositiveToobigbinsize→outliersinsomefrequentbins,falsenegativeSolution:Adoptkerneldensityestimationtoestimatetheprobabilitydensitydistributionofthedata.Iftheestimateddensityfunctionishigh,theobjectislikelynormal.Otherwise,itislikelyanoutlier.Proximity-BasedApproaches:Distance-Basedvs.Density-BasedOutlierDetectionIntuition:ObjectsthatarefarawayfromtheothersareoutliersAssumptionofproximity-basedapproach:TheproximityofanoutlierdeviatessignificantlyfromthatofmostoftheothersinthedatasetTwotypesofproximity-basedoutlierdetectionmethodsDistance-basedoutlierdetection:AnobjectoisanoutlierifitsneighborhooddoesnothaveenoughotherpointsDensity-basedoutlierdetection:Anobjectoisanoutlierifitsdensityisrelativelymuchlowerthanthatofitsneighbors34Distance-BasedOutlierDetectionForeachobjecto,examinethe#ofotherobjectsinther-neighborhoodofo,whererisauser-specifieddistancethresholdAnobjectoisanoutlierifmost(takingπasafractionthreshold)oftheobjectsinDarefarawayfromo,i.e.,notinther-neighborhoodofoAnobjectoisaDB(r,π)outlierifEquivalently,onecancheckthedistancebetweenoanditsk-thnearestneighborok,where.oisanoutlierifdist(o,ok)>rEfficientcomputation:NestedloopalgorithmForanyobjectoi,calculateitsdistancefromotherobjects,andcountthe#ofotherobjectsinther-neighborhood.Ifπ?notherobjectsarewithinrdistance,terminatetheinnerloopOtherwise,oiisaDB(r,π)outlierEfficiency:ActuallyCPUtimeisnotO(n2)butlineartothedatasetsizesinceformostnon-outlierobjects,theinnerloopterminatesearly35Density-BasedOutlierDetectionLocaloutliers:Outlierscomparingtotheirlocalneighborhoods,insteadoftheglobaldatadistributionInFig.,o1ando2arelocaloutlierstoC1,o3isaglobaloutlier,buto4isnotanoutlier.However,proximity-basedclusteringcannotfindo1ando2areoutlier(e.g.,comparingwithO4).36Intuition(density-basedoutlierdetection):ThedensityaroundanoutlierobjectissignificantlydifferentfromthedensityarounditsneighborsMethod:Usetherelativedensityofanobjectagainstitsneighborsastheindicatorofthedegreeoftheobjectbeingoutliersk-distanceofanobjecto,distk(o):distancebetweenoanditsk-thNNk-distanceneighborhoodofo,Nk(o)={o’|o’inD,dist(o,o’)≤distk(o)}Nk(o)couldbebiggerthanksincemultipleobjectsmayhaveidenticaldistancetooLocalOutlierFactor:LOFReachabilitydistancefromo’too:wherekisauser-specifiedparameterLocalreachabilitydensityofo:37LOF(Localoutlierfactor)ofanobjectoistheaverageoftheratiooflocalreachabilityofoandthoseofo’sk-nearestneighborsThelowerthelocalreachabilitydensityofo,andthehigherthelocalreachabilitydensityofthekNNofo,thehigherLOFThiscapturesalocaloutlierwhoselocaldensityisrelativelylowcomparingtothelocaldensitiesofitskNNClustering-BasedOutlierDetection(1&2):

Notbelongtoanycluster,orfarfromtheclosestoneAnobjectisanoutlierif(1)itdoesnotbelongtoanycluster,(2)thereisalargedistancebetweentheobjectanditsclosestcluster,or(3)itbelongstoasmallorsparseclusterCaseI:NotbelongtoanyclusterIdentifyanimalsnotpartofaflock:Usingadensity-basedclusteringmethodsuchasDBSCANCase2:FarfromitsclosestclusterUsingk-means,partitiondatapointsofintoclustersForeachobjecto,assignanoutlierscorebasedonitsdistancefromitsclosestcenterIfdist(o,co)/avg_dist(co)islarge,likelyanoutlierEx.Intrusiondetection:ConsiderthesimilaritybetweendatapointsandtheclustersinatrainingdatasetUseatrainingsettofindpatternsof“normal”data,e.g.,frequentitemsetsineachsegment,andclustersimilarconnectionsintogroupsComparenewdatapointswiththeclustersmined—Outliersarepossibleattacks39FindCBLOF:DetectoutliersinsmallclustersFindclusters,andsortthemindecreasingsizeToeachdatapoint,assignacluster-basedlocaloutlierfactor(CBLOF):Ifobjpbelongstoalargecluster,CBLOF=cluster_sizeXsimilaritybetweenpandclusterIfpbelongstoasmallone,CBLOF=clustersizeXsimilaritybetw.pandtheclosestlargecluster40Clustering-BasedOutlierDetection(3):

DetectingOutliersinSmallClustersEx.Inthefigure,oisoutliersinceitsclosestlargeclusterisC1,butthesimilaritybetweenoandC1issmall.ForanypointinC3,itsclosestlargeclusterisC2butitssimilarityfromC2islow,plus|C3|=3issmallClustering-BasedMethod:StrengthandWeaknessStrengthDetectoutlierswithoutrequiringanylabeleddataWorkformanytypesofdataClusterscanberegardedassummariesofthedataOncetheclusterareobtained,needonlycompareanyobjectagainsttheclusterstodeterminewhetheritisanoutlier(fast)WeaknessEffectivenessdependshighlyontheclusteringmethodused—theymaynotbeoptimizedforoutlierdetectionHighcomputationalcost:NeedtofirstfindclustersAmethodtoreducethecost:Fixed-widthclusteringApointisassignedtoaclusterifthece