FREM
Published 4 November 2002
Carlos Ordońẽz, Edward Omiecinski
Citations69
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An improved EM algorithm to cluster large data sets having high dimensionality, noise and zero variance problems is presented and is compared against the standard EM algorithm and the On-Line EM algorithm.
Abstract
Clustering is a fundamental Data Mining technique. This article presents an improved EM algorithm to cluster large data sets having high dimensionality, noise and zero variance problems. The algorithm incorporates improvements to increase the quality of solutions and speed. In general the algorithm can find a good clustering solution in 3 scans over the data set. Alternatively, it can be run until it converges. The algorithm has a few parameters that are easy to set and have defaults for most cases. The proposed algorithm is compared against the standard EM algorithm and the On-Line EM algorithm.
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
TechnometricsThe EM Algorithm and Extensions
5,108 Citations1998Debashis Kushary, Geoffrey J. McLachlan +1 more
IEEE ExpertData mining and knowledge discovery: making sense out of data
4,643 Citations1996U.M. Feyyad
Find loads of the data mining and knowledge discovery making sense out of data book catalogues in this site as the choice of you visiting this page.
BIRCH
3,906 Citations1996Tian Zhang, Raghu Ramakrishnan +1 more
A data clustering method named BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) is presented, and it is demonstrated that it is especially suitable for very large databases.
Journal of the Royal Statistical Society Series A (General)Pattern Classification and Scene Analysis.
3,240 Citations1974Mairi Clarke, Richard O. Duda +1 more
SIAM ReviewMixture Densities, Maximum Likelihood and the EM Algorithm
2,686 Citations1984Richard A. Redner, Homer F. Walker
This work discusses the formulation and theoretical and practical properties of the EM algorithm, a specialization to the mixture density context of a general algorithm used to approximate maximum-likelihood estimates for incomplete data problems.
Neural ComputationHierarchical Mixtures of Experts and the EM Algorithm
2,639 Citations1994Michael I. Jordan, Robert A. Jacobs
Data Mining and Knowledge DiscoveryExtensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values
2,409 Citations1998Zhexue Huang
Two algorithms which extend the k-means algorithm to categorical domains and domains with mixed numeric and categorical values are presented and are shown to be efficient when clustering large data sets, which is critical to data mining applications.
Automatic subspace clustering of high dimensional data for data mining applications
2,386 Citations1998Rakesh Agrawal, Johannes Gehrke +2 more
CLIQUE is presented, a clustering algorithm that satisfies each of these requirements of data mining applications including the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records.
Lecture notes in computer scienceWhen Is “Nearest Neighbor” Meaningful?
2,297 Citations1999Kevin Beyer, Jonathan Goldstein +2 more
The effect of dimensionality on the "nearest neighbor" problem is explored, and it is shown that under a broad set of conditions, as dimensionality increases, the Distance to the nearest data point approaches the distance to the farthest data point.
A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
2,187 Citations1998Radford M. Neal, Geoffrey E. Hinton
An incremental variant of the EM algorithm in which the distribution for only one of the unobserved variables is recalculated in each E step is shown empirically to give faster convergence in a mixture estimation problem.
CURE
1,909 Citations1998Sudipto Guha, Rajeev Rastogi +1 more
This work proposes a new clustering algorithm called CURE that is more robust to outliers, and identifies clusters having non-spherical shapes and wide variances in size, and demonstrates that random sampling and partitioning enable CURE to not only outperform existing algorithms but also to scale well for large databases without sacrificing clustering quality.
Communications of the ACMThe KDD process for extracting useful knowledge from volumes of data
1,899 Citations1996Usama M. Fayyad, Gregory Piatetsky-Shapiro +1 more
A new generation of computational techniques and tools is required to support the extraction of useful knowledge from the rapidly growing volumes of data, the subject of the emerging field of knowledge discovery in databases (KDD) and data mining.
Efficient and Effective Clustering Methods for Spatial Data Mining
1,788 Citations1994Raymond T. Ng, Jiawei Han
The analysis and experiments show that with the assistance of CLAHANS, these two algorithms are very effective and can lead to discoveries that are difficult to find with current spatial data mining algorithms.
Outlier detection for high dimensional data
1,034 Citations2001Charų C. Aggarwal, Philip S. Yu
New techniques for outlier detection are discussed which find the outliers by studying the behavior of projections from the data set by studying the behavior of projections from the data set.
Neural ComputationA Unifying Review of Linear Gaussian Models
883 Citations1999Sam T. Roweis, Zoubin Ghahramani
A new model for static data is introduced, known as sensible principal component analysis, as well as a novel concept of spatially adaptive observation noise, which shows how independent component analysis is also a variation of the same basic generative model.
Neural ComputationOn Convergence Properties of the EM Algorithm for Gaussian Mixtures
763 Citations1996Lei Xu, Michael I. Jordan
The mathematical connection between the Expectation-Maximization (EM) algorithm and gradient-based approaches for maximum likelihood learning of finite gaussian mixtures is built up and an explicit expression for the matrix is provided.
Scaling clustering algorithms to large databases
709 Citations1998Patricia Bradley, Usama M. Fayyad +1 more
A scalable clustering framework applicable to a wide class of iterative clustering that requires at most one scan of the database and is instantiated and numerically justified with the popular K-Means clustering algorithm.
ROCK: a robust clustering algorithm for categorical attributes
601 Citations1999Suvajyoti Guha, R. Rastogi +1 more
This work develops a robust hierarchical clustering algorithm, ROCK, that employs links and not distances when merging clusters, and shows that ROCK not only generates better quality clusters than traditional algorithms, but also exhibits good scalability properties.
ACM SIGMOD RecordFinding generalized projected clusters in high dimensional spaces
532 Citations2000Charų C. Aggarwal, Philip S. Yu
CACTUS—clustering categorical data using summaries
470 Citations1999Venkatesh Ganti, Johannes Gehrke +1 more
This paper introduces a novel formalization of a cluster for categorical attributes by generalizing a definition of a clusters for numerical attributes and describes a very fast summarizationbased algorithm called CACTUS that discovers exactly such clusters in the data.
Finding Intensional Knowledge of Distance-Based Outliers
421 Citations1999Edwin M. Knorr, Raymond T. Ng
Neural ComputationSMEM Algorithm for Mixture Models
411 Citations2000Naonori Ueda, Ryohei Nakano +2 more
A split-and-merge expectation-maximization algorithm to overcome the local maxima problem in parameter estimation of finite mixture models and is applied to the training of gaussian mixtures and mixtures of factor analyzers and shows the practical usefulness by applying it to image compression and pattern recognition problems.
Accelerating exact<i>k</i>-means algorithms with geometric reasoning
377 Citations1999Dan Pelleg, Andrew Moore
New algorithms for the k-means clustering problem are presented that use the kd-tree data structure to reduce the large number of nearest-neighbor queries issued by the traditional algorithm.
KOPS (University of Konstanz)Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering
336 Citations1999Alexander Hinneburg, Daniel A. Keim
A new clustering technique called OptiGrid is developed which is based on constructing an optimal grid-partitioning of the data and has a mathematical basis which is by far more e ectiveness andiency than existing clustering algorithms for highdimensional data.
Finding generalized projected clusters in high dimensional spaces
291 Citations2000Charų C. Aggarwal, Philip S. Yu
Very general techniques for projected clustering are discussed which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality, which is substantially more general and realistic than currently available techniques.
Advances in computersClustering Methodologies in Exploratory Data Analysis
287 Citations1980Richard C. Dubes, Anil Jain
The chapter focuses on the four operations highlighted by reviewing techniques for assessing the tendency of the data to cluster, performing the clustering itself, and evaluating the validity of the results, and introduces the concept of intrinsic dimensionality that helps determine an appropriate number of factors for representing data.
Neural ComputationOn-line EM Algorithm for the Normalized Gaussian Network
280 Citations2000Masa-aki Sato, Shin Ishii
ACM SIGKDD Explorations NewsletterScalability for clustering algorithms revisited
246 Citations2000Fredrik Farnstrom, James F. Lewis +1 more
A simple new algorithm that performs k-means clustering in one scan of a dataset, while using a bu er for points from the dataset of xed size is presented, and experiments show that the new method is several times faster than standard k-Means, and that it produces clusterings of equal or almost equal quality.
Scaling EM (Expectation Maximization) Clustering to Large Databases
170 Citations1998Paul S. Bradley, Usama M. Fayyad +1 more
A scalable implementation of the Expectation-Maximization (EM) algorithm, which constructs proper statistical models of the underlying data source and naturally generalizes to cluster databases containing both discrete-valued and continuous-valued data.
Mining constrained association rules to predict heart disease
104 Citations2002Carlos Ordońẽz, Edward Omiecinski +7 more
This work describes the experiences in discovering association rules in medical data to predict heart disease, and introduces an improved algorithm to discover constrained association rules.
Neural ComputationStatistical Physics, Mixtures of Distributions, and the EM Algorithm
100 Citations1994Alan Yuille, Paul Stolorz +1 more
There are strong relationships between approaches to optmization and learning based on statistical physics or mixtures of experts, and the EM algorithm can be interpreted as converging either to a local maximum of the mixtures model or to a saddle point solution to the statistical physics system.
C2P: Clustering based on Closest Pairs
97 Citations2001Αλέξανδρος Νανόπουλος, Yannis Theodoridis +1 more
C 2 P is presented, a new clustering algorithm for large spatial databases, which exploits spatial access methods for the determination of closest pairs and attains the advantages of hierarchical clustering and graphtheoretic algorithms providing both efficiency and quality of clustering result.
Data bubbles
79 Citations2001Markus Breunig, Hans‐Peter Kriegel +2 more
This paper proposes an efficient post-processing step and the concept of a Data Bubble as a special kind of compressed data item that allows for a very accurate approximation of the clustering structure of a large data set even for very high compression rates.
On Convergence Properties of the EM Algorithm for Gaussian Mixtures.
59 Citations1995Michael I. Jordan, Lei Xu
SQLEM
29 Citations2000Carlos Ordońẽz, Paul Cereghini
This paper presents an efficient SQL implementation of the EM algorithm to perform clustering in very large databases that can effectively handle high dimensional data, a high number of clusters and more importantly, a very large number of data records.
A fast algorithm to cluster high dimensional basket data
19 Citations2002Carlos Ordońẽz, Edward Omiecinski +1 more
This article introduces a fast algorithm to cluster large binary data sets where data points have high dimensionality and most of their coordinates are zero, which is the case with basket data transactions containing items.
Mining complex databases using the EM algorithm
1 Citations2000Carlos Ordońẽz, Edward Omiecinski
This thesis proved association rule mining can be solved as a clustering problem and an algorithm to mine association rules from a collection of images segmented by EM is introduced.