Anomaly Detection Via Online Over-Sampling Principal Component Analysis
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Online Over-SamplingPrincipal Component AnalysisYi-Ren Yeh1 , Yuh-Jye Lee2 and Yu-Chiang Frank Wang11 ResearchCenter for Information Technology Innovation, Academia Sinicaof Computer Science and Information Engineering, NTUST2 DepartmentDecember 30, 20101 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOutlineOutline1Introduction2Anomaly Detection via Principal Component Analysis3Over-Sampling PCA for Anomaly Detection4Experimental Results5Conclusion2 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisIntroductionOutline1Introduction2Anomaly Detection via Principal Component Analysis3Over-Sampling PCA for Anomaly Detection4Experimental Results5Conclusion3 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisIntroductionIntroductionOutlier detection is an important issue in data mining and hasbeen studied in different research areas.Outlier detection methods are designed for finding the rareinstances or deviated data.In this work, we use “Leave One Out” procedure to checkeach individual point the “with or without” effect on thevariation of principal directions.An over-sampling principal component analysis (PCA) outlierdetection method is proposed for emphasizing the influence ofan abnormal instance as well.We also present a quick updating technique which satisfiesthe on-line scenarios.4 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisIntroductionOne Possible Definition of OutliersAn outlier is an observation that deviates so much from otherobservations as to arouse suspicion that it was generated by adifferent mechanism (by Hawkins).5 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisIntroductionOne Possible Definition of OutliersAn outlier is an observation that deviates so much from otherobservations as to arouse suspicion that it was generated by adifferent mechanism (by Hawkins).Michael Jordan is an outlier because of a well-knownquotation by Charles Barkley: “I am the best basketball playerin the earth, Jordan? He is an alien”.6 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisIntroductionAnother Possible Definition of OutliersAn outlier is an observation that enormously affects modelwhen we add or remove it from the entire dataset.7 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisIntroductionAnother Possible Definition of OutliersAn outlier is an observation that enormously affects modelwhen we add or remove it from the entire dataset.Wilt Chamberlain is an outlier on account of his responsibilityfor several rule changes in basketball. In order to diminish hisdominance, the basketball authorities set some rules includingwidening the lane, as well as changes to rules regardinginbounding the ball and shooting free throws.8 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Principal Component AnalysisOutline1Introduction2Anomaly Detection via Principal Component Analysis3Over-Sampling PCA for Anomaly Detection4Experimental Results5Conclusion9 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Principal Component AnalysisPrincipal Component Analysis n p be the data matrix.Let A [x 1 ; x2 ; · · · ; xn ] RTypically, PCA is formulated as the following optimizationproblemmaxU Rp k ,kUk InXi 1U (xi µ)(xi µ) U.(1)Alternatively, one can approach the PCA problem asminimizing the data reconstruction error, i.e.minU Rp k ,kUk IJ(U) nXi 1k(xi µ) UU (xi µ)k2 .(2)U is a matrix consisting of k dominant eigenvectors.10 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Principal Component AnalysisPrincipal Component Analysis (cont’d)Generally, the problem in either (1) or (2) can be solved byderiving an eigenvalue decomposition problem:ΣA U UΛ(3)ΣA is the covariance matrix.The time complexity and memory requirement are O(p 3 ) andO(p 2 ) respectively.11 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Principal Component AnalysisThe Effect of An Outlier on Principal DirectionsPCA is sensitive to outliers.We use the leave one out (LOO) procedure to explore thevariation of principal direction.A particular instance with high variation of the principaldirections will bean abnormal instance.·6Remove an outlierAdd an outlierRemove a normal data pointAdd a normal data pointFig. 1. The effect of adding/removing an outlier or a normal data instance on the principaldirection.Figure: The effect of adding/removing an outlier or a normal datainstance on the principal direction.Once these eigenvectors ũt are obtained, we use the absolute value of cosine similarity to measure the variation of the principal directions, i.e.st 1 ⟨ũt , u⟩ . ũt u (7)12 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Principal Component AnalysisDecremental PCA with LOO Scheme for AnomalyDetectionIn our framework, we need to evaluate a decremental PCAproblem n times in the LOO procedure:Σà ũt λũt ,(4)where à A/{xt } and Σà is the covariance of Ã.,uiUse st 1 kũhũt tkkuk to measure the variation of the principaldirections.Note that u is the the dominant principal direction from A.A higher st score (closer to 1) means that the target instanceis more likely to be an outlier.13 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisAnomaly Detection via Principal Component AnalysisIncremental PCA for Anomaly DetectionIn contrast with decremental PCA, we also consider the use ofincremental PCA for outlier detection.This strategy is preferable in online anomaly detectionapplications.That is, we can use it to determine whether a newly receiveddata instance is an outlier.The incremental PCA can be formulated as followsΣà ũt λũt ,(5)where à A {xt }.Similarly, we check the score st of each newly receivedinstance and determine its outlierness accordingly.14 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionOutline1Introduction2Anomaly Detection via Principal Component Analysis3Over-Sampling PCA for Anomaly Detection4Experimental Results5Conclusion15 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionOver-Sampling Principal Components Analysis (osPCA)A single outlier instance will not significantly change theprincipal direction when the size of the data is large.We employ an over-sampling scheme to emphasize theinfluence of an outlier.The variation of principal directions and mean of the data willbe enlarged if we duplicate an outlier.We integrate the over-sampling and LOO strategies togetherwith the incremental PCA.16 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionAnomaly Detection via Online Over-Sampling PCA·9dulpicated pointssingle point(a) Over-sampling a normal data pointsingle pointdulpicated points(b) Over-sampling an outlierFig. 2. The effect of an over-sampled normal data or outlier instance on the principal direction.Figure: The effect of an over-sampled normal data or outlier instance onthe outerproduct matrix and xt be the target instance (to be over-sampled), wethe principaldirection.use the following technique to update the mean µ̃ and the covariance matrix Σ :õ r·x17 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionosPCA (cont’d)Our osPCA algorithm can be formulated as followsΣà ũt λũt ,(6)where à A {xt , . . . , xt } R(n ñ) p .Note thatñ1 X1 X (xi µ̃)(xi µ̃) Σà xt x t µ̃µ̃ , (7)n ñn ñxi Ai 1i.e., we will duplicate the target instance ñ times.The major concern is the computation cost of calculating orupdating the principal directions in large-scale problems.18 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionRemarks on µ and ΣA for osPCAIt is unnecessary to re-compute the covariance matrix in LOO.The covariance matrix can be easily updated while duplicatinga target instance.Let Q AA nbe the original outer product matrix.We update µ̃ and ΣÃ by:µ̃ µ r · xt1r and ΣÃ Q xt x t µ̃µ̃ .1 r1 r1 rNote that 0 r 1 is the parameter controlling the sizewhen over-sampling xt .19 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionThe Power Method for osPCATo alleviate this computation load, we apply the well-knownpower method to determine ũ.This method starts with an initial normalized vector ũ(0) .ũ is determined byWhile (ũ(k) 6 ũ(k 1) )ũ(k 1) EndΣÃ ũ(k)kΣÃ ũ(k) kWe only use the first principal component in our experiments.20 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionSome Remarks on Power MethodStill need to solve an eigenvalue decomposition.We can use the previous principal direction as the initial pointin power method to reduce computation time.For high dimensional data, it is not practical to keep thecovariance matrix.An online PCA algorithm to update the eigenvector ispreferable, which approximates the minimization ofreconstruction error formulation.21 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionLeast Squares Approximation for PCAStandard PCA:minU Rp k ,kUk IJ(U) nXi 1kx̄i UU x̄i k2 ,(8)where U is a set eigenvectors and x̄i is (xi µ).The above formulation can be further approximated by a leastsquares form (i.e., has a closed form solution):minU Rp k ,kUk IJls (U) nXi 1kx̄i Uyi k2 ,(9)where yi U0 x̄i Rk and U0 is the approximation of U.The trick for this least squares problem is the approximationof U x̄i by yi U0 x̄i .22 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionOnline Updating for (Least Squares) osPCAIn an online setting, we approximate the current yi U t x̄i bythe previous solution U x̄asfollowst 1 iminUt Rp k ,kUk IJls (Ut ) tXi 1kx̄i Ut yi k2 ,(10)where yi U t 1 x̄i .For a target instance, we haveminŨ Rp k ,kŨk IJls (Ũ) nXi 1kx̄i Ũyi k2 kx̄t Ũyt k2 ,(11)where yt is approximated by U x̄t .23 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionOnline Updating for osPCA (cont’d)When over-sampling the target instance ñ times, we haveminŨ Rp k ,kŨk IJls (Ũ) nXi 1kx̄i Ũyi k2 ñkx̄t Ũyt k2 .(12)Equivalently, we convert the above problem into the followingformminŨ Rp k ,kŨk InXJls (Ũ) β(kx̄i Ũyi k2 ) kx̄t Ũyt k2 .(13)i 1β can be regarded as a weighting factor to suppress theinformation from existing data.The relation between β and the over-sampled number ñ isβ ñ1 nr1 .24 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisOver-Sampling PCA for Anomaly DetectionOnlineUpdatingfor osPCA (cont’d)12·Algorithm1: AnomalyDetectionOver-samplingPCAWecalculatethe solutionofviaũ Onlineby takingthe derivativeof (13) Input: The data matrix A [x ;x;···;x]andtheweightβ.n12withrespect to ũ, and thus we haveOutput: Score of outlierness s [s1 s2 · · · sn ]. If si is higher than a threshold,xi is an outlier.nPβ(u byyiusingx̄i ) (18);yt x̄tCompute first principal directionn i 1n ,ũ 2n(22); 2yPyj x̄j and y Keep x̄proj j in 2β(j 1j 1(14)yi ) yti 1for i 1 to n doβ x̄proj yi x̄iũ by (18);2 ixwhere yi βy yu⟨ i and yt u xtw̃,w⟩s 1 by(7);iũ xi and ũ ũ u xt , respectively.are the approximations ofTable I. Comparisons of the power method and our proposed online osPCA for anomaly detectionin terms of computational complexity and memory requirements. Note that m indicates thenumber of iterations.Power MethodOnline Over-sampling PCAComputation complexityO(nmp2 )O(np)2Memory requirementO(p )O(p)(a)6(b)0.04525 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisExperimental ResultsOutline1Introduction2Anomaly Detection via Principal Component Analysis3Over-Sampling PCA for Anomaly Detection4Experimental Results5Conclusion26 / 36
xi is an outlier.Anomaly Detection via Online Over-SamplingPrincipal Component AnalysisExperimental ResultsCompute first principal direction u by using (18);Keep x̄proj n yj x̄j and y j 12D SyntheticSetfor i 1 to Datan doũ n j 1yj2 in (22);β x̄proj yi x̄iby (18);βy yi2⟨w̃,w⟩1 ũ u by (7);si We generatea 2-D synthetic data, which consists of 190normal instances and 10 deviated instances.TableI. Comparisonsof the powerproposedanomaly detectionWeaimto identifythemethodtop and5%ourofthe onlinedataosPCAas fordeviateddatain terms of computational complexity and memory requirements. Note that m indicates the(thenumberofoutlierswegenerated).number of iterations.Power MethodOnline Over-sampling PCAComputationcomplexity)O(np)The scoresof outliernessofO(nmpall 200data pointsare shown theMemory requirementO(p )O(p)following plot.22(a)(b)60.0450.0440.035scores of outlierness220 2Normal data:190 ptsDeviated data: 10 ptsThe first PC of normal dataOutlier identified mark (5%) 4 6 10 5Fig. 3.0x15100.030.0250.020.0150.010.0050050100indices of instances150The result of identifying outliers in the 2-D synthetic data.20027 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisExperimental ResultsUCI and KDD datasetsIn our experiments, we evaluate our methods on pendigitsand KDD Cup 99 intrusion detection datasets.We compare our methodsdPCA (only removing one instance in LOO)osPCA with power methodOsPCA with online updatingwithLOF (local outlier factor, ACM SIGMOD 2000)Fast ABOD (angle-based outlier detection, ACM SIGKDD2008)In our experiments, we use AUC to evaluate the suspiciousoutlier ranking in outlier detection phase28 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisExperimental ResultsCompared with Other Methods (pendigits dataset)Fixed the digit “0” as the normal data (780 instances) and set up 9different combination via other digits (20 data points for 23456789dPCA(power method)0.9145 (0.0385)0.9573 (0.0317)0.4570 (0.0554)0.7392 (0.0686)0.8126 (0.0485)0.9773 (0.0077)0.8387 (0.0439)0.8519 (0.0476)0.6914 (0.0635)osPCA(power method)0.9965 (0.0004)0.9959 (0.0003)0.9987 (0.0003)0.9897 (0.0016)0.9961 (0.0005)0.9793 (0.0015)0.9968 (0.0003)0.9816 (0.0172)0.9968 (0.0008)osPCA(online updating)0.9869 (0.0104)0.9879 (0.0225)0.9199 (0.0453)0.8442 (0.0582)0.9623 (0.0260)0.9851 (0.0176)0.9800 (0.0305)0.9245 (0.0395)0.9776 (0.0290)Fast ABOD(SIGKDD 2008)0.9519 (0.0287)0.9214 (0.0279)0.9342 (0.0157)0.9737 (0.0069)0.9721 (0.0086)0.9447 (0.0196)0.9642 (0.0087)0.9913 (0.0019)0.9901 (0.0025)LOF(SIGMOD 2000)0.9943 (0.0007)0.9966 (0.0002)0.9970 (0.0002)0.9859 (0.0017)0.9980 (0.0003)0.9741 (0.0028)0.9968 (0.0004)0.9939 (0.0016)0.9945 (0.0006)Table: The AUC scores of decremental PCA (dPCA), over-sampling PCA(osPCA) with power method, our osPCA with online updating algorithm, fastABOD, and LOF on the pendigits data set.29 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisExperimental ResultsMethodsdPCATime (sec.)0.0589osPCA(with power method)0.0892osPCA(with online updating)0.0121Fast ABODLOF13.8040.0789Table: Average CPU time (in seconds) of decremental PCA (dPCA),over-sampling PCA (osPCA) with power method, our osPCA with onlineupdating algorithm, fast ABOD, and LOF on the pendigits data set.30 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisExperimental ResultsResults on KDD 99 Data (Outlier Detection)We extract instances under the tcp protocal in 10% KDD cupdata and test our method and LOF on themThe size of normal data is 76813 and we also extract fourdifferent attacks as the outliers respectively.Types & sizesof outliersdos (50)probe (50)r2l (50)u2r (49)osPCA (online updating)AUCTime AUC0.92870.96310.82530.8868LOFTime (sec.)24.8424.7222.1220.36*It takes about 24 seconds to complete the procedure by using power mehtod31 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisExperimental ResultsResults on KDD 99 Data (On-line Anomaly Detection)We extract 2000 normal instances points as the training setand apply the data cleaning phase to filter 100 points (5%) inthe normal data to avoid the deviated dataFor testing, we select another 2000 normal instances anddifferent size of attacks as our testing set.AttacktypeDosProbeR2LU2RTesting data sizenormal .0230.0720.038*TP rate is the percentage of attacks detected; FP rate is the percentage ofnormal connections falsely classified as attacks.32 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisConclusionOutline1Introduction2Anomaly Detection via Principal Component Analysis3Over-Sampling PCA for Anomaly Detection4Experimental Results5Conclusion33 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisConclusionConclusion and Future WorkVariation of principal directions caused by outliers candetermine data anomaly.The proposed osPCA can be used to enlarge the outlierness ofan outlier in large-scale problems.Our online osPCA algorithm efficiently updates the principaldirections without solving eigenvalue decomposition problems.Our method does not need to keep the entire covariance ordata matrices during the evaluation process.Future research directions:multi-clustering structuredata in a extremely high dimensional space34 / 36
detection lies in the field of statistics. Intuitively, outliers can be deics. These studies can be broadly classified intoAnomalyvia OnlinewhereOver-Samplingfined Principalas given byComponentHawkins [10].Analysishe firstcategoryDetectionis distribution-based,aon (e.g.ConclusionNormal, Poisson, etc.) is used to fit theDefinition 1: (Hawkins-Outlier)are defined based on the probability distribution.An outlier is an observation that deviates so much from otherd tests of this category, called discordancy tests,observations as to arouse suspicion that it was generated by aped for different scenarios (see [5]). A key drawdifferent mechanism.ory of tests is that most of the distributions usedThis notion is formalized by Knorr and Ng [13] in the followingere are some tests that are multivariate (e.g. muldefinition of outliers. Throughout this paper, we use o, p, q to deutliers). But for many KDD applications, the unnote objects in a dataset. We use the notation d(p, q) to denote theon is unknown. Fitting the data with standard disdistance between objects p and q. For a set of objects, we use Cy, and may not produce satisfactory results.(sometimes with the intuition that C forms a cluster). To simplifyory of outlier studies in statistics is depth-based.our notation, we use d(p, C) to denote the minimum distance bes represented as a point in a k-d space, and is astween p and object q in C, i.e. d(p,C) min{ d(p,q) q C }.ith respect to outlier detection, outliers are moreDefinition 2: (DB(pct, dmin)-Outlier)bjects with smaller depths. There are many defiat have been proposed (e.g. [20], [16]). In theory,An object p in a dataset D is a DB(pct, dmin)-outlier if at leastaches could work for large values of k. However,percentage pct of the objects in D lies greater than distancethere exist efficient algorithms for k 2 or 3dmin from p, i.e., the cardinality of the set {q D d(p, q) depth-based approaches become inefficient fordmin} is less than or equal to (100 pct)% of the size of D.k 4. This is because depth-based approachesThe above definition captures only certain kinds of outliers. Beutation of k-d convex hulls which has a lowercause the definition takes a global view of the dataset, these outliersof Ω(nk/2) for n objects.can be viewed as “global” outliers. However, for many interestingLocal Outlier FactorOne of the most popular outlier detection methods.A local density-based method to evaluate the outlierness foreach instance.Considers the local data structure for estimating the density.The density of each individual instance’s k-nearest neighborswhich exhibita more complex structure, thereis used to definereal-worldthe datasetsdegreeof outlierness.nd Ng proposed the notion of distance-based outeir notion generalizes many notions from the disproaches, and enjoys better computational compth-based approaches for larger values of k. Laterwill discuss in detail how their notion is differentlocal outliers proposed in this paper. In [17] thebased outliers is extended by using the distanceighbor to rank the outliers. A very efficient algoe the top n outliers in this ranking is given, butoutlier is still distance-based.nce of the area, fraud detection has received moregeneral area of outlier detection. Depending onhe application domains, elaborate fraud modelsn algorithms have been developed (e.g. [8], [6]).is another kind of outliers. These can be objects that are outlyingC1C2o2o1Figure 1: 2-d dataset DS135 / 36
Anomaly Detection via Online Over-Sampling Principal Component AnalysisConclusionAngle-based Outlier DetectionMain concept of ABOD is using the variation of the anglesbetween the each target instance and the rest instancesAn outlier or deviated instance will generate a smaller varianceamong its associated anglesf a change of resolution.the number of objectsn data object and, thus,istances rather than ons or an ε-neighborhoodrization. An approachnsional data is proposedsed subspace clusteringe grid cells are sought tols as outliers. Since thisality, an evolutionary alically for sparse cells.Asoutlier detection, somen for the outlierness of aa is to navigate gure 1: Intuition of angle-based outlier detection.136 / 36
Anomaly Detection via Online Over-Sampling Principal Component Analysis Anomaly Detection via Principal Component Analysis The E ect of An Outlier on Principal Directions PCA is sensitive to outliers. We use the leave one out (LOO) procedure to explore the variation of principal direction. A particular instance with high variation of the principal
The key motivation behind our project is to expand upon the traditional approach of node and link based anomaly detection within graphs by considering full graph level anomaly detection. Graph level anomaly detection looks to broaden the scope of anomaly detect
Daattaa iMMiinninngg &CChhaapptteerr-- u66 e& t77:: AAAnnoommaallyy// iFFrraaudd iDDetteecctiioonn && Addvvaanncceedd DDaattaa MMiinninngg AApppplliiccaattioonn Prreeppaarreedd pBByy:: aEErr. Prraattaapp SSaapkkootta 1 Chapter 6: Anomaly/Fraud Detection Anomaly Detection - Anomaly detection is a form of classification. - Is the process to localize objects that are different from other objects .
Insider Threat Detection: The problem of insider threat detection is usually framed as an anomaly detection task. A comprehensive and structured overview of anomaly detection techniques was provided by Chandola et al. [3]. They defined that the purpose of anomaly detection is finding patterns in data which did not conform to
Graph based Anomaly Detection and Description: A Survey 3 (a) Clouds of points (multi-dimensional) (b) Inter-linked objects (network) Fig. 1 (a) Point-based outlier detection vs. (b) Graph-based anomaly detection. as well as how other reviewers rated the same products, to an extent how trustwor-
The business value of anomaly detection use cases within financial services is obvious. From credit card or check fraud to money laundering and cybersecurity, accurate, fast anomaly detection is necessary in order to conduct bu
Quantum machine learning for quantum anomaly detection NANA LIU CQT AND SUTD, SINGAPORE ARXIV:1710.07405 TUESDAY 7TH . Chandola et al, Anomaly detection: a survey, ACM computing surveys, 2009 arXiv:1710.07405. Types of anomalies Supervised Unsupervised Semi-supervised Point Contextual Collective arXiv:1710.07405. Types of anomalies Supervised .
Deep learning is "learning feature hierarchies with features from higher levels of the hierarchy formed by the composition of lower-level features" [12]. Means deep learning learns layers of features. B. Anomaly Detection Anomaly detection is the process of identifying data in-
Literary Studies. London: Longman, 1993. INTRODUCTION While most of you have already had experience of essay writing, it is important to realise that essay writing at University level may be different from the practices you have so far encountered. The aim of this tutorial is to discuss what is required of an English Literature essay at University level, including: 1. information on the .
