UUtah Data Mining | Fall 2026 | L20: Outliers
Overview
Outlier detection depends on how the data’s noise is generated and on whether the model used to identify unusual points is itself distorted by them. The lecture develops a residual-based pruning loop, explains why clustered adversarial outliers can defeat simple distance thresholds in high dimensions, and presents covariance-guided pruning, breakdown point, DBSCAN, and reverse nearest neighbors as complementary approaches.
Key takeaways
- Outlier detection is only as reliable as its fitted model: a model family mismatch or outlier-distorted fit can make genuine inliers appear anomalous and hide the actual outliers.
- Iterative pruning should be conservative: remove only high-residual points, refit, and repeat until the selected set stabilizes.
- In a d-dimensional unit-variance Gaussian model, the sample mean’s expected squared error is d/n, so high-dimensional estimation can require sample counts much larger than the dimension.
- Clustered adversarial points can evade simple distance thresholds while collectively pulling the mean; covariance eigenvalues can reveal the excess variation in the direction of that distortion.
- The one-dimensional mean has breakdown point 1/n, while the median withstands a much larger fraction of extreme contamination, but median-based methods do not transfer cleanly or efficiently to high dimensions.
- DBSCAN detects points outside sufficiently dense clusters, while reverse nearest neighbors compare local distance scales; both offer alternatives when a parametric residual model is unsuitable.
Chapters
- The lecture begins a section on noise and outliers, followed by anomaly detection and privacy.
- Upcoming graph topics include graph embeddings and an in-class ethics activity about bias in embeddings.
- The final noise and graph assignments are planned as two shorter half-assignments.
- Spurious readings include sensor malfunctions and mislabeling, which can create outlier points.
- Measurement noise is ordinary variation, such as small errors when measuring a person’s height.
- Gaussian noise is a common default: minimizing squared error corresponds to maximum-likelihood fitting under that model.
- Other processes may need different noise models, such as delays that are always positive.
- Background data can be valid data but irrelevant to the measurement, rather than erroneous or anomalous.
- An election poll should exclude people under 18 and people who do not plan to vote.
- In satellite crop measurements, pixels outside the planted region should not be included in the crop estimate.
- Fit a model M from a chosen family by optimizing a cost on the observed data.
- Compute each point’s residual, measuring how poorly the fitted model explains that point.
- Mark points with residuals above a threshold as outliers; residuals may be prediction errors or geometric distances.
- For k-means, residuals can be distances to cluster centers; for dimensionality reduction, they can be projection errors.
- A threshold that is too small can discard too much data, leaving too little to fit the target pattern.
- A mismatched model family, such as clustering when the data lies near a low-dimensional subspace, can misclassify inliers.
- Outliers may be the objects of interest, so detection can support investigation rather than removal.
- If outliers distort the fitted model, their residuals may not reveal them, creating a model-fitting and pruning feedback problem.
- Fit an initial model, calculate residuals, and remove only points whose residuals exceed a conservative threshold.
- Refit the model on the remaining data and repeat until the selected points stabilize.
- A threshold may be reduced gradually, but aggressive pruning risks discarding genuine observations.
- The method is a general framework; its threshold and details depend on the model and data setting.
- For a one-dimensional normal distribution, observations naturally occur at varying distances from the mean.
- About 68% of observations lie within one standard deviation and about 95% within two.
- There is no universally correct cutoff: even points far into the tails can be legitimate draws from the assumed process.
- Estimating the mean and variance from the same data makes pruning decisions less certain and can shift the estimate.
- Consider IID samples in R^d from a d-dimensional normal distribution with mean μ and unit variance in each coordinate.
- A single sample has expected squared Euclidean distance d from μ because the coordinate variances add.
- The sample mean has expected squared error d/n, so its error decreases as the sample count n grows.
- Without further assumptions, obtaining small error requires n to be substantially larger than d.
- The d/n error term can be costly for embeddings with thousands of coordinates, such as d = 4,000.
- The corresponding distance scale is roughly the square root of d/n.
- If every data point is normalized to lie within a unit ball around the true mean, the stated dimension dependence can be avoided.
- High-dimensional sample requirements make data normalization a potentially important preprocessing choice.
- Estimate μ with the sample mean, then compute each point’s residual from that estimate.
- A residual-squared cutoff set to a constant multiple of d, such as 2d, can flag points far beyond the expected scale.
- In high dimensions, Gaussian sample distances concentrate near their expected scale, making very distant points comparatively easy to identify.
- After pruning, refit the mean and repeat the conservative filtering loop.
- An adversary can place a small fraction of outliers within the normal distance range, so pointwise distance filtering misses them.
- If those outliers cluster in one direction, they can pull the sample mean away from the true mean.
- A 5% group can cause substantial estimation error in high dimensions even when its individual members do not look unusually distant.
- The important signal is the group’s collective effect, not necessarily an extreme residual for each point.
- Under the assumed isotropic normal model, the sample covariance should have eigenvalues approximately near 1.
- A cluster of outliers that shifts the mean can also create excessive variation along a particular direction.
- Inspecting the leading covariance eigenvectors can expose that direction even when individual residuals appear plausible.
- Careful directional pruning can remove points contributing to the distortion, then repeat the estimation process.
- The breakdown point is the fraction of adversarial data needed to make an estimator arbitrarily bad.
- In one dimension, moving a single observation arbitrarily far can move the mean arbitrarily far, giving the mean a breakdown point of 1/n.
- The median is based on the middle sorted rank and resists a small number of extreme points.
- For a one-dimensional sample, roughly half the observations must be corrupted to make the median arbitrarily bad.
- The median can jump between separated data blocks, while the mean may remain between them and better represent the overall distribution.
- Under Gaussian noise, the mean is a natural estimator; indiscriminate trimming can remove valid points unevenly.
- A coordinate-wise median in high dimensions can lie outside the data’s convex hull.
- Some high-dimensional robust estimators are computationally impractical, whereas covariance-guided methods can offer polynomial-time alternatives.
- DBSCAN groups connected regions with sufficient local density and labels points outside those regions as noise or outliers.
- Its decisions depend on parameters including neighborhood radius and minimum points.
- Poor parameter choices can mark a large share of data as outliers; one cited project group saw about 30%.
- Density-based clustering assumes useful local density structure rather than the parametric normal model used for mean estimation.
- For each point, find its k-th nearest neighbor, then compare that distance with the neighbor’s own k-th-neighbor distance.
- A point whose neighborhood scale is much larger than its neighbor’s can be flagged as an outlier.
- Comparing local distance scales helps distinguish anomalies across dense and sparse regions.
- The method relies on a meaningful distance function and nearest-neighbor search, and concludes the lecture before the next session on anomaly detection.
Transcript excerpt
0:16 Welcome back everyone. So, let's get started. Uh oh. Um so, today we're kind of uh transitioning into a kind of newer kind of um so section of the lecture thinking about and modeling the noise in the data and so we'll start today talking about outliers um before we get started I want to look at a couple things uh um so the schedule let's see so we we kind of finished dimensionality reduction looking um and we're looking into the noise section we'll talk about next week we'll talk about anom anomaly detection um at least a slight view into this and then so some privacy um and
1:07 then the Tuesday before Thanksgiving break we're going to start moving into graphs but I'm going to start with graph embeddings and we're going to have like a little ethics module during the class as well where we're going to kind of look at the ethics involved in bias inside of embeddings. Um, and so that's will it will it will kind of build on a bunch of the stuff that we talked about in the course that you guys now will understand. Uh, so we can dig a little bit deeper into this issue than you could in like um just one of the pure ethics courses where you may not have understood this machinery as well. Um, there will be an in-class activity on that day. This is on this is you'll see
1:56 there's a homework or some assignment on canvas. Um so it is it is definitely kind of uh it's good to be in class for that day. If there are reasons you can't be in class, I will try and provide some sort of like zoom zoom online option. It's not as essential as some of the
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, UofU Data Science.