Clustering very large databases using EM mixture models

Clustering very large databases is a challenge for traditional pattern recognition algorithms, e.g. the expectation-maximization (EM) algorithm for fitting mixture models, because of high memory and iteration requirements. Over large databases, the cost of the numerous scans required to converge and...

Full description

Saved in:
Bibliographic Details
Main Authors: Bradley, P.S., Fayyad, U.M., Reina, C.A.
Format: Conference Proceeding
Language:English
Subjects:
Clustering algorithms
Costs
Data mining
Distributed databases
Machine learning algorithms
Maximum likelihood estimation
Pattern recognition
Probability density function
Read-write memory
Visual databases
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Clustering very large databases is a challenge for traditional pattern recognition algorithms, e.g. the expectation-maximization (EM) algorithm for fitting mixture models, because of high memory and iteration requirements. Over large databases, the cost of the numerous scans required to converge and large memory requirement of the algorithm becomes prohibitive. We present a decomposition of the EM algorithm requiring a small amount of memory by limiting iterations to small data subsets. The scalable EM approach requires at most one database scan and is based on identifying regions of the data that are discardable, regions that are compressible, and regions that must be maintained in memory. Data resolution is preserved to the extent possible based upon the size of the memory buffer and fit of the current model to the data. Computational tests demonstrate that the scalable scheme outperforms similarly constrained EM approaches.
ISSN:1051-4651
2831-7475
DOI:10.1109/ICPR.2000.906021