重庆大学：《数据仓库与数据挖掘 Data Warehouse and Data mining》课程PPT教学课件（英文版）Chapter 9 Outlier Analysis

Chapter 9. Outlier Analysis Outlier and outlier Analysis Outlier Detection Methods Statistical Approaches Proximity-Base Approaches Clustering-Base Approaches Classification Approaches Summary

1 Chapter 9. Outlier Analysis ◼ Outlier and Outlier Analysis ◼ Outlier Detection Methods ◼ Statistical Approaches ◼ Proximity-Base Approaches ◼ Clustering-Base Approaches ◼ Classification Approaches ◼ Summary

What Is Outlier Discovery? What are outliers? The set of objects are considerably dissimilar from the remainder of the data EXample: Sports: Michael Jordon, Wayne Gretzky, Problem: Define and find outliers in large data sets Applications Credit card fraud detection Telecom fraud detection Customer segmentation ■ Medical analysis network intrusion detection fault detection

2 What Is Outlier Discovery? ◼ What are outliers? ◼ The set of objects are considerably dissimilar from the remainder of the data ◼ Example: Sports: Michael Jordon, Wayne Gretzky, ... ◼ Problem: Define and find outliers in large data sets ◼ Applications: ◼ Credit card fraud detection ◼ Telecom fraud detection ◼ Customer segmentation ◼ Medical analysis ◼ network intrusion detection ◼ fault detection

What Are outliers? Outlier: A data object that deviates significantly from the normal objects as if it were generated by a different mechanism EX: Unusual credit card purchase, sports: Michael Jordon, Wayne Gretzky,… Outliers are different from the noise data Noise is random error or variance in a measured variable Noise should be removed before outlier detection Outliers are interesting: It violates the mechanism that generates the normal data R Outlier detection Vs novelty detection: early stage outlier; but later merged into the model

3 What Are Outliers? ◼ Outlier: A data object that deviates significantly from the normal objects as if it were generated by a different mechanism ◼ Ex.: Unusual credit card purchase, sports: Michael Jordon, Wayne Gretzky, ... ◼ Outliers are different from the noise data ◼ Noise is random error or variance in a measured variable ◼ Noise should be removed before outlier detection ◼ Outliers are interesting: It violates the mechanism that generates the normal data ◼ Outlier detection vs. novelty detection: early stage , outlier; but later merged into the model

Anomaly Detection Challenges a How many outliers are there in the data? Method is unsupervised Validation can be quite challenging just like for clustering) Finding needle in a haystack Working assumption a There are considerably more normal observations than abnormal observations (outliers/anomalies )in the data

4 Anomaly Detection ◼ Challenges ◼ How many outliers are there in the data? ◼ Method is unsupervised ◼ Validation can be quite challenging (just like for clustering) ◼ Finding needle in a haystack ◼ Working assumption: ◼ There are considerably more “normal” observations than “abnormal” observations (outliers/anomalies) in the data

Anomaly Detection Schemes General steps Build a profile of the"normal behavior Profile can be patterns or summary statistics for overall population Use the normal profile to detect anomalies Anomalies are observations whose characteristics differ significantly from the normal profile Types of anomaly detection schemes Graphical Statistical-based Distance-based Model-based 5

5 Anomaly Detection Schemes ◼ General Steps ◼ Build a profile of the “normal” behavior ◼ Profile can be patterns or summary statistics for overall population ◼ Use the “normal” profile to detect anomalies ◼ Anomalies are observations whose characteristics differ significantly from the normal profile ◼ Types of anomaly detection schemes ◼ Graphical & Statistical-based ◼ Distance-based ◼ Model-based

R Types of Outliers o Three kinds: global, contextual and collective outliers Global outlier (or point anomaly) Global outlier Object is Oa if it significantly deviates from the rest of the data set EX Intrusion detection in computer networks Issue: Find an appropriate measurement of deviation Contextual outlier (or conditionaloutlier Object is Oc if it deviates significantly based on a selected context EX 800 F in Urbana: outlier? (depending on summer or winter?) Attributes of data objects should be divided into two groups Contextual attributes defines the context, e.g., time location Behavioral attributes characteristics of the object, used in outlier evaluation, e.g., temperature Can be viewed as a generalization of local out/iers-whose density significantly deviates from its local area Issue: How to define or formulate meaningful context?

6 Types of Outliers (I) ◼ Three kinds: global, contextual and collective outliers ◼ Global outlier(or point anomaly) ◼ Object is Og if it significantly deviates from the rest of the data set ◼ Ex. Intrusion detection in computer networks ◼ Issue: Find an appropriate measurement of deviation ◼ Contextual outlier(or conditional outlier) ◼ Object is Oc if it deviates significantly based on a selected context ◼ Ex. 80o F in Urbana: outlier? (depending on summer or winter?) ◼ Attributes of data objects should be divided into two groups ◼ Contextual attributes: defines the context, e.g., time & location ◼ Behavioral attributes: characteristics of the object, used in outlier evaluation, e.g., temperature ◼ Can be viewed as a generalization of local outliers—whose density significantly deviates from its local area ◼ Issue: How to define or formulate meaningful context? Global Outlier

Types of Outliers (D) Collective Outliers A subset of data objects collectively deviate o OO significantly from the whole data set, even if the individual data objects may not be outliers Applications: E.g., intrusion detection Collective Outlier hen a number of computers keep sending denial-of-service packages to each other Detection of collective outliers Consider not only behavior of individual objects, but also that of groups of objects Need to have the background knowledge on the relationship among data objects, such as a distance or similarity measure on objects a data set may have multiple types of outlier One object may belong to more than one type of outlier

7 Types of Outliers (II) ◼ Collective Outliers ◼ A subset of data objects collectively deviate significantly from the whole data set, even if the individual data objects may not be outliers ◼ Applications: E.g., intrusion detection: ◼ When a number of computers keep sending denial-of-service packages to each other Collective Outlier ◼ Detection of collective outliers ◼ Consider not only behavior of individual objects, but also that of groups of objects ◼ Need to have the background knowledge on the relationship among data objects, such as a distance or similarity measure on objects. ◼ A data set may have multiple types of outlier ◼ One object may belong to more than one type of outlier

Challenges of Outlier Detection Modeling normal objects and outliers properly Hard to enumerate all possible normal behaviors in an application The border between normal and outlier objects is often a gray area Application-specific outlier detection Choice of distance measure among objects and the model of relationship among objects are often application-dependent E.g., clinic data: a small deviation could be an outlier; while in marketing analysis, larger fluctuations Handling noise in outlier detection Noise may distort the normal objects and blur the distinction between normal objects and outliers. It may help hide outliers and reduce the effectiveness of outlier detection Understandability Understand why these are outliers Justification of the detection Specify the degree of an outlier: the unlikelihood of the object being generated by a normal mechanism

8 Challenges of Outlier Detection ◼ Modeling normal objects and outliers properly ◼ Hard to enumerate all possible normal behaviors in an application ◼ The border between normal and outlier objects is often a gray area ◼ Application-specific outlier detection ◼ Choice of distance measure among objects and the model of relationship among objects are often application-dependent ◼ E.g., clinic data: a small deviation could be an outlier; while in marketing analysis, larger fluctuations ◼ Handling noise in outlier detection ◼ Noise may distort the normal objects and blur the distinction between normal objects and outliers. It may help hide outliers and reduce the effectiveness of outlier detection ◼ Understandability ◼ Understand why these are outliers: Justification of the detection ◼ Specify the degree of an outlier: the unlikelihood of the object being generated by a normal mechanism

Outlier Detection I: Supervised Methods Two ways to categorize outlier detection methods Based on whether user-labeled examples of outliers can be obtained Supervised, semi-supervised vS unsupervised methods Based on assumptions about normal data and outliers Statistical, proximity-based, and clustering-based methods Outlier Detection I: Supervised Methods Modeling outlier detection as a classification problem Samples examined by domain experts used for training& testing Methods for Learning a classifier for outlier detection effectively Model normal objects report those not matching the model as outliers, or Model outliers and treat those not matching the model as normal Challenges Imbalanced classes. i.e., outliers are rare: boost the outlier class and make up some artificial outliers Catch as many outliers as possible, i.e., recall is more important than accuracy(i.e, not mislabeling normal objects as outliers)

Outlier Detection I: Supervised Methods ◼ Two ways to categorize outlier detection methods: ◼ Based on whether user-labeled examples of outliers can be obtained: ◼ Supervised, semi-supervised vs. unsupervised methods ◼ Based on assumptions about normal data and outliers: ◼ Statistical, proximity-based, and clustering-based methods ◼ Outlier Detection I: Supervised Methods ◼ Modeling outlier detection as a classification problem ◼ Samples examined by domain experts used for training & testing ◼ Methods for Learning a classifier for outlier detection effectively: ◼ Model normal objects & report those not matching the model as outliers, or ◼ Model outliers and treat those not matching the model as normal ◼ Challenges ◼ Imbalanced classes, i.e., outliers are rare: Boost the outlier class and make up some artificial outliers ◼ Catch as many outliers as possible, i.e., recall is more important than accuracy (i.e., not mislabeling normal objects as outliers) 9

Outlier Detection I: Unsupervised Methods Assume the normal objects are somewhat clustered" into multiple groups, each having some distinct features An outlier is expected to be far away from any groups of normal objects Weakness: Cannot detect collective outlier effectively Normal objects may not share any strong patterns, but the collective outliers may share high similarity in a small area Ex. In some intrusion or virus detection normal activities are diverse Unsupervised methods may have a high false positive rate but still miss many real outliers Supervised methods can be more effective, e. g, identify attacking some key resources Many clustering methods can be adapted for unsupervised methods Find clusters, then outliers: not belonging to any cluster Problem 1: Hard to distinguish noise from outliers Problem 2: Costly since first clustering: but far less outliers than normal objects Newer methods: tackle outliers directly 10

Outlier Detection II: Unsupervised Methods ◼ Assume the normal objects are somewhat ``clustered'‘ into multiple groups, each having some distinct features ◼ An outlier is expected to be far away from any groups of normal objects ◼ Weakness: Cannot detect collective outlier effectively ◼ Normal objects may not share any strong patterns, but the collective outliers may share high similarity in a small area ◼ Ex. In some intrusion or virus detection, normal activities are diverse ◼ Unsupervised methods may have a high false positive rate but still miss many real outliers. ◼ Supervised methods can be more effective, e.g., identify attacking some key resources ◼ Many clustering methods can be adapted for unsupervised methods ◼ Find clusters, then outliers: not belonging to any cluster ◼ Problem 1: Hard to distinguish noise from outliers ◼ Problem 2: Costly since first clustering: but far less outliers than normal objects ◼ Newer methods: tackle outliers directly 10