DataminingConceptsandteniques2.ppt

* * * * * * * * Clustering-Based Method: Strength and Weakness Strength Detect outliers without requiring any labeled data Work for many types of data Clusters can be regarded as summaries of the data Once the cluster are obtained, need only compare any object against the clusters to determine whether it is an outlier (fast) Weakness Effectiveness depends highly on the clustering method used—they may not be optimized for outlier detection High computational cost: Need to first find clusters A method to reduce the cost: Fixed-width clustering A point is assigned to a cluster if the center of the cluster is within a pre-defined distance threshold from the point If a point cannot be assigned to any existing cluster, a new cluster is created and the distance threshold may be learned from the training data under certain conditions * Chapter 12. Outlier Analysis Outlier and Outlier Analysis Outlier Detection Methods Statistical Approaches Proximity-Base Approaches Clustering-Base Approaches Classification Approaches Mining Contextual and Collective Outliers Outlier Detection in High Dimensional Data Summary Classification-Based Method I: One-Class Model Idea: Train a classification model that can distinguish “normal” data from outliers A brute-force approach: Consider a training set that contains samples labeled as “normal” and others labeled as “outlier” But, the training set is typically heavily biased: # of “normal” samples likely far exceeds # of outlier samples Cannot detect unseen anomaly * One-class model: A classifier is built to describe only the normal class. Learn the decision boundary of the normal class using classification methods such as SVM Any samples that do not belong to the normal class (not within the decision boundary) are declared as outliers Adv: can detect new outliers that may not appear close to any outlier objects in the training set Extension: Normal objects may belong to multiple classes Classification-Based Method II: Semi-Supervised Lear