Back to search

University of British Columbia

Outliers and data mining : finding exceptions in data

Abstract

dc:description

Our thesis is that we can efficiently identify meaningful outliers in large, multidimensional datasets. In particular, we introduce and study the notion and utility of distance-based outliers (DB-outliers). First, we focus on outlier identification, and present nested-loop, index-based, and cell-based algorithms. For datasets that are mainly disk-resident, we present another version of the cell-based algorithm that guarantees at most 3 passes over a dataset. We provide experimental results showing that these cell-based algorithms are by far the best for 4 or fewer dimensions. Second, we focus on the computation of intensional knowledge, that is, we provide a description or an explanation of why an identified outlier is exceptional. We provide an algorithm to compute the "strongest" outliers in a dataset (i.e., outliers that are dominant for certain attributes or dimensions). Our notion of strongest outliers allows significant pruning to take place in the search tree. We also define the notion of "weak" outliers. With respect to the computation of intensional knowledge, we develop naive, semi-naive, and I/O optimized algorithms. The latter class of algorithms intelligently schedules I/O's, and achieves optimization via page sharing. Third, we focus on robust space transformations to achieve meaningful results when mining Ac-D datasets for Z?.B-outliers. Robust estimation is used to: (a) account for differences among attributes in scale, variability, and correlation, (b) account for the effects of outliers in the data, and (c) prevent undesirable masking and flooding during the search for outliers. We propose using a robust space transformation called the Donoho-Stahel estimator (DSE), and we show key properties of the DSE. Of particular importance to data mining applications involving large or dynamic datasets is the stability property, which says that in spite of frequent updates, the estimator does not: (a) change much, (b) lose its usefulness, or (c) require re-computation. We develop randomized algorithms and evaluate how well they perform empirically. The novel algorithm that we develop is called the Hybrid-Random algorithm, which can significantly outperform the other DSE algorithms for moderate-high levels of recall. Experimental results using real-world data are included to show the utility and efficiency of Di>-outiiers.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2002

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Knorr, Edwin M.

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/12783

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Knorr, Edwin M.. Outliers and data mining : finding exceptions in data. doctoral thesis, University of British Columbia, 2002. http://hdl.handle.net/2429/12783