Overcoming the Curse of Dimensionality in Clustering by Means of the Wavelet Transform

We use a redundant wavelet transform analysis to detect clusters in high-dimensional data spaces. We overcome Bellman's `curse of dimensionality' in such problems by (i) using some canonical ordering of observation and variable (document and term) dimensions in our data, (ii) applying a wa...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2000-01, Vol.43 (2), p.107-120
Main Authors: Murtagh, Fionn, Starck, Jean-Luc, Berry, Michael W
Format: Article
Language:English
Subjects:
Algorithms
Cluster analysis
Clustering
Computer science
Discriminant analysis
Information retrieval
Methods
Noise
Sparsity
Visualization
Wavelet transforms
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We use a redundant wavelet transform analysis to detect clusters in high-dimensional data spaces. We overcome Bellman's `curse of dimensionality' in such problems by (i) using some canonical ordering of observation and variable (document and term) dimensions in our data, (ii) applying a wavelet transform to such canonically ordered data, (iii) modelling the noise in wavelet space, (iv) defining significant component parts of the data as opposed to insignificant or noisy component parts, and (v) reading off the resultant clusters. The overall complexity of this innovative approach is linear in the data dimensionality. We describe a number of examples and test cases, including the clustering of high-dimensional hypertext data.
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/43.2.107