数据挖掘之异常检测.ppt

AnomalyDetection Aintroduction Sourceofslides TutorialAtAmericanStatisticalAssociation ASA2008 JiaweiHan datamining conceptsandtechniquesTutorialattheEuropeanConferenceonPrinciplesandPracticeofKnowledgeDiscoveryinDatabasesSpeaker WentaoLi Outline DefinitionApplicationMethodsLimitedtime SoIjustdrawthepictureofanomalydetection formoredetail pleaseturntothepaperforhelp WhatareAnomalies AnomalyisapatterninthedatathatdoesnotconformtotheexpectedbehaviorAnomalyisAdataobjectthatdeviatessignificantlyfromthenormalobjectsasifitweregeneratedbyadifferentmechanismAlsoreferredtoasoutliers exceptions peculiarities surprises etc Anomaliestranslatetosignificant oftencritical reallifeentitiesCyberintrusionsCreditcardfraudFaultsinmechanicalsystems Relatedproblems OutliersaredifferentfromthenoisedataNoiseisrandomerrororvarianceinameasuredvariableNoiseshouldberemovedbeforeoutlierdetectionOutliersareinteresting ItviolatesthemechanismthatgeneratesthenormaldataOutlierdetectionvs noveltydetection earlystage outlier butlatermergedintothemodel KeyChallenges DefiningarepresentativenormalregionischallengingTheboundarybetweennormalandoutlyingbehaviorisoftennotpreciseAvailabilityoflabeleddatafortraining validationTheexactnotionofanoutlierisdifferentfordifferentapplicationdomainsDatamightcontainnoiseNormalbehaviorkeepsevolvingAppropriateselectionofrelevantfeatures MapRelatedareas theory Application practice ProblemformulationDetectioneffect AspectsofAnomalyDetectionProblem NatureofinputdataWhatisthecharacteristicofinputdataAvailabilityofsupervisionNumberoflabelTypeofanomaly point contextual structuralTypeofanomalyOutputofanomalydetectionScorevslabelEvaluationofanomalydetectiontechniquesWhatkindofdetectionisgood InputData MostcommonformofdatahandledbyanomalydetectiontechniquesisRecordDataUnivariateMultivariate InputData MostcommonformofdatahandledbyanomalydetectiontechniquesisRecordDataUnivariateMultivariate InputData NatureofAttributes NatureofattributesBinaryCategoricalContinuousHybrid categorical continuous continuous categorical binary InputData ComplexDataTypes RelationshipamongdatainstancesSequentialTemporalSpatialSpatio temporalGraph DataLabels SupervisedAnomalyDetectionLabelsavailableforbothnormaldataandanomaliesSemi supervisedAnomalyDetectionLabelsavailableonlyfornormaldataUnsupervisedAnomalyDetectionNolabelsassumedBasedontheassumptionthatanomaliesareveryrarecomparedtonormaldataPayattention heresomematerialsgivedifferentdescriptions andwetreatadoptthedefinitionherethoughitisabitambiguouswiththetraditionaldefinitional TypeofAnomalies PointAnomaliesContextualAnomaliesCollectiveAnomalies PointAnomalies Anindividualdatainstanceisanomalousw r t thedata ContextualAnomalies AnindividualdatainstanceisanomalouswithinacontextRequiresanotionofcontextAlsoreferredtoasconditionalanomalies Dangerous theftcondition theftMoneyconsumer thepoorandtherich XiuyaoSong MingxiWu ChristopherJermaine SanjayRanka ConditionalAnomalyDetection IEEETransactionsonDataandKnowledgeEngineering 2006 Normal Anomaly CollectiveAnomalies AcollectionofrelateddatainstancesisanomalousRequiresarelationshipamongdatainstancesSequentialDataSpatialDataGraphDataTheindividualinstanceswithinacollectiveanomalyarenotanomalousbythemselves AnomalousSubsequence OutputofAnomalyDetection LabelEachtestinstanceisgivenanormaloranomalylabelThisisespeciallytrueofclassification basedapproachesScoreEachtestinstanceisassignedananomalyscoreAllowstheoutputtoberankedRequiresanadditionalthresholdparameter EvaluationofAnomalyDetection F value AccuracyisnotsufficientmetricforevaluationExample networktrafficdatasetwith99 9 ofnormaldataand0 1 ofintrusionsTrivialclassifierthatlabelseverythingwiththenormalclasscanachieve99 9 accuracy anomalyclass Cnormalclass NC FocusonbothrecallandprecisionRecall R TP TP FN truepredictedanomaly allanomalyPrecision P TP TP FP truepredictedanomaly allpredictedF measure 2 R P R P EvaluationofOutlierDetection ROC AUC Standardmeasuresforevaluatinganomalydetectionproblems Recall Detectionrate ratiobetweenthenumberofcorrectlydetectedanomaliesandthetotalnumberofanomaliesFalsealarm falsepositive rate ratiobetweenthenumberofdatarecordsfromnormalclassthataremisclassifiedasanomaliesandthetotalnumberofdatarecordsfromnormalclassROCCurveisatrade offbetweendetectionrateandfalsealarmrateAreaundertheROCcurve AUC iscomputedusingatrapezoidruleThebest theworest anomalyclass Cnormalclass NC ApplicationsofAnomalyDetection NetworkintrusiondetectionInsurance CreditcardfrauddetectionHealthcareInformatics MedicaldiagnosticsIndustrialDamageDetectionImageProcessing VideosurveillanceNovelTopicDetectioninTextMining IntrusionDetection IntrusionDetection Processofmonitoringtheeventsoccurringinacomputersystem inner ornetwork outer andanalyzingthemforintrusionsIntrusionsaredefinedasattemptstobypassthesecuritymechanismsofacomputerornetwork ChallengesTraditionalsignature basedintrusiondetectionsystemsarebasedonsignaturesofknownattacksandcannotdetectemergingcyberthreatsSubstantiallatencyindeploymentofnewlycreatedsignaturesacrossthecomputersystemAnomalydetectioncanalleviatetheselimitations FraudDetection FrauddetectionreferstodetectionofcriminalactivitiesoccurringincommercialorganizationsMalicioususersmightbetheactualcustomersoftheorganizationormightbeposingasacustomer alsoknownasidentitytheft TypesoffraudCreditcardfraudInsuranceclaimfraudMobile cellphonefraudInsidertradingChallengesFastandaccuratereal timedetectionMisclassificationcostisveryhigh HealthcareInformatics DetectanomalouspatientrecordsIndicatediseaseoutbreaks instrumentationerrors etc KeyChallengesOnlynormallabelsavailableMisclassificationcostisveryhighDatacanbecomplex spatio temporal IndustrialDamageDetection Industrialdamagedetectionreferstodetectionofdifferentfaultsandfailuresincomplexindustrialsystems structuraldamages intrusionsinelectronicsecuritysystems abnormalenergyconsumption etc Example AircraftSafetyAnomalousAircraft Engine FleetUsageAnomaliesinenginecombustiondataTotalaircrafthealthandusagemanagementKeyChallengesDataisextremelyhuge noisyandunlabelledMostofapplicationsexhibittemporalbehaviorDetectinganomalouseventstypicallyrequireimmediateintervention ImageProcessing DetectingoutliersinaimageorvideomonitoredovertimeDetectinganomalousregionswithinanimageUsedinmammographyimageanalysisvideosurveillancesatelliteimageanalysisKeyChallengesDetectingcollectiveanomaliesDatasetsareverylarge Anomaly Taxonomy AnomalyDetection ContextualAnomalyDetection CollectiveAnomalyDetection OnlineAnomalyDetection DistributedAnomalyDetection PointAnomalyDetection ClassificationBased RuleBasedNeuralNetworksBasedSVMBased NearestNeighborBased DensityBasedDistanceBased Statistical ParametricNon parametric ClusteringBased Others InformationTheoryBasedSpectralDecompositionBasedVisualizationBased StatisticalApproaches Statisticalapproachesassumethattheobjectsinadatasetaregeneratedbyastochasticprocess agenerativemodel Idea learnagenerativemodelfittingthegivendataset andthenidentifytheobjectsinlowprobabilityregionsofthemodelasoutliersMethodsaredividedintotwocategories parametricvs non parametricParametricmethodAssumesthatthenormaldataisgeneratedbyaparametricdistributionwithparameter Theprobabilitydensityfunctionoftheparametricdistributionf x givestheprobabilitythatobjectxisgeneratedbythedistributionThesmallerthisvalue themorelikelyxisanoutlierNon parametricmethodNotassumeana prioristatisticalmodelanddeterminethemodelfromtheinputdataNotcompletelyparameterfreebutconsiderthenumberandnatureoftheparametersareflexibleandnotfixedinadvanceExamples histogramandkerneldensityestimation ParametricMethodsI DetectionUnivariateOutliersBasedonNormalDistribution Univariatedata 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 wederivethefollowingmaximumlikelihoodestimates Fortheabovedatawithn 10 wehaveThen 24 28 61 1 51 3 04 3 24isanoutliersince ParametricMethodsI TheGrubb sTest Univariateoutlierdetection TheGrubb stest maximumnormedresidualtest anotherstatisticalmethodundernormaldistributionForeachobjectxinadataset computeitsz score xisanoutlierifwhereisthevaluetakenbyat distributionatasignificancelevelof 2N andNisthe ofobjectsinthedataset ParametricMethodsII DetectionofMultivariateOutliers Multivariatedata AdatasetinvolvingtwoormoreattributesorvariablesTransformthemultivariateoutlierdetectiontaskintoaunivariateoutlierdetectionproblemMethod1 ComputeMahalaobisdistanceLet bethemeanvectorforamultivariatedataset Mahalaobisdistanceforanobjectoto isMDist o o TS 1 o whereSisthecovariancematrixUsetheGrubb stestonthismeasuretodetectoutliersMethod2 Use 2 statistic whereEiisthemeanofthei dimensionamongallobjects andnisthedimensionalityIf 2 statisticislarge thenobjectoiisanoutlier ParametricMethodsIII UsingMixtureofParametricDistributions AssumingdatageneratedbyanormaldistributioncouldbesometimesoverlysimplifiedExample rightfigure Theobjectsbetweenthetwoclusterscannotbecapturedasoutlierssincetheyareclosetotheestimatedmean Toovercomethisproblem assumethenormaldataisgeneratedbytwonormaldistributions Foranyobjectointhedataset theprobabilitythatoisgeneratedbythemixtureofthetwodistributionsisgivenbywheref 1andf 2aretheprobabilitydensityfunctionsof 1and 2ThenuseEMalgorithmtolearntheparameters 1 1 2 2fromdataAnobjectoisanoutlierifitdoesnotbelongtoanycluster Non ParametricMethods DetectionUsingHistogram Themodelofnormaldataislearnedfromtheinputdatawithoutanyaprioristructure 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 BasedOutlierDetection Intuition ObjectsthatarefarawayfromtheothersareoutliersAssumptionofproximity basedapproach TheproximityofanoutlierdeviatessignificantlyfromthatofmostoftheothersinthedatasetTwotypesofproximity basedoutlierdetectionmethodsDistance basedoutlierdetection AnobjectoisanoutlierifitsneighborhooddoesnothaveenoughotherpointsDensity basedoutlierdetection Anobjectoisanoutlierifitsdensityisrelativelymuchlowerthanthatofitsneighbors 34 Distance BasedOutlierDetection Foreachobjecto 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 theinnerloopterminatesearly 35 Density BasedOutlierDetection Localoutliers Outlierscomparingtotheirlocalneighborhoods insteadoftheglobaldatadistributionInFig o1ando2arelocaloutlierstoC1 o3isaglobaloutlier buto4isnotanoutlier However proximity basedclusteringcannotfindo1ando2areoutlier e g comparingwithO4 36 Intuition density basedoutlierdetection ThedensityaroundanoutlierobjectissignificantlydifferentfromthedensityarounditsneighborsMethod Usetherelativedensityofanobjectagainstitsneighborsastheindicatorofthedegreeoftheobjectbeingoutliersk distanceofanobjecto distk o distancebetweenoanditsk thNNk distanceneighborhoodofo Nk o o o inD dist o o distk o Nk o couldbebiggerthanksincemultipleobjectsmayhaveidenticaldistancetoo LocalOutlierFactor LOF Reachabilitydistancefromo too wherekisauser specifiedparameterLocalreachabilitydensityofo 37 LOF Localoutlierfactor ofanobjectoistheaverageoftheratiooflocalreachabilityofoandthoseofo sk nearestneighborsThelowerthelocalreachabilitydensityofo andthehigherthelocalreachabilitydensityofthekNNofo thehigherLOFThiscapturesalocaloutlierwhoselocaldensityisrelativelylowcomparingtothelocaldensitiesofitskNN Clustering BasedOutlierDetection 1 2 Notbelongtoanycluster orfarfromtheclosestone Anobjectisanoutlierif 1 itdoesnotbelongtoanycluster 2 thereisalargedistancebetweentheobjectanditsclosestcluster or 3 itbelongstoasmallorsparsecluster CaseI NotbelongtoanyclusterIdentifyanimalsnotpartofaflock Usingadensity basedclusteringmethodsuchasDBSCANCase2 FarfromitsclosestclusterUsingk means partitiondatapointsofintoclustersForeachobjecto assignanoutlierscorebasedonitsdistancefromitsclosestcenterIfdist o co avg dist co islarge likelyanoutlierEx Intrusiondetection Considerthesimilaritybetweendatapointsandtheclustersinatrainingdataset Useatrainingsettofindpatternsof normal data e g frequentitemsetsineachsegment andclustersimilarconnectionsintogroupsComparenewdatapointswiththeclustersmined Outliersarepossibleattacks 39 FindCBLOF DetectoutliersinsmallclustersFindclusters andsortthemindecreasingsizeToeachdatapoint assignacluster basedlocaloutlierfactor CBLOF Ifobjpbelongstoalargecluster CBLOF cluster sizeXsimilaritybetweenpandclusterIfpbelongstoasmallone CBLOF clustersizeXsimilaritybetw pandtheclosestlargecluster 40 Clustering BasedOutlierDetection 3 DetectingOutliersinSmallClusters Ex Inthefigure oisoutliersinceitsclosestlargeclusterisC1 butthesimilaritybetweenoandC1issmall ForanypointinC3 itsclosestlargeclusterisC2butitssimilarityfromC2islow plus C3 3issmall Clustering BasedMethod StrengthandWeakness StrengthDetectoutlierswithoutrequiringanylabeleddataWorkformanytypesofdataClusterscanberegardedassummariesofthedataOncetheclusterareobtained needonlycompareanyobjectagainsttheclusterstodeterminewhetheritisanoutlier fast WeaknessEffectivenessdependshighlyontheclusteringmethodused theymaynotbeoptimizedforoutlierdetectionHighcomputationalcost NeedtofirstfindclustersAmethodtoreducethecost Fixed widthclusteringApointisassignedtoaclusterifthecenteroftheclusteriswithinapre defined