Open Collections

An efficient and effective computation of 2-dimensional depth contours

University of British Columbia

Depth contour computation is a useful aid to outlier detection. For two-dimensional datasets, Rousseeuw and Ruts' ISODEPTH has been the state-of-the-art algorithm. Further contributions involve improving its efficiency and effectiveness, and resolving the issue of higher-dimensional datasets. This thesis details our research in these two areas. It presents a Fast Depth Contour Algorithm - FDC, which permits the selection of useful data points for processing and the removal of data point positioning limitations. Different selection methods result in the creation of FDC-basic and FDC-enhanced; and for buffer-space-compatibility, three further variants (FDC-M1, FDC-M2, and FDC-M3) of FDC-basic have been developed. FDC-basic capitalizes on the normal location of outiers and the relevancy of the vertices of convex hulls in depth contour computation. By computing with only the useful data points, it proves to run 150 times faster than ISODEPTH when computing the first 21 depth contours of a 6500-point dataset. FDCenhanced takes only a quarter of the time required by FDC-basic to compute the first 151 depth contours of a 100,000-point dataset because it maintains a constantly adjusted sorted list of the useful data points to reduce redundant computation. FDC-M1 keeps dividing the dataset into subsets and discarding the useless data points until the union of the subsets fits the buffer size. FDC-M2 further uses a periodically adjusted inner convex hull to filter useless data points. FDC-M3 saves buffer space by starting the computation with a minimum dataset, which is enlarged with additional useful data points for each succeeding computation. To tackle datasets of higher dimensions, we have pioneered a promising algorithm in 3-dimensional computation, FDC-3D, which can be improved with the use of sorted lists. Algorithm Fast Depth Contour not only provides an efficient and effective tool for immediate use, but also suggests a direction for future studies.

Thesis/Dissertation

application/pdf

2009-06-26

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.

http://hdl.handle.net/2429/9682

Computer Science

University of British Columbia

UBCV

DSpace