Clustering binary data streams with K-means
Published 13 June 2003
Carlos Ordońẽz
Citations188
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
Three variants of the K-means algorithm to cluster binary data streams are presented and a proposed variant introduced that finds higher quality solutions in less time is introduced.
Abstract
Clustering data streams is an interesting Data Mining problem. This article presents three variants of the K-means algorithm to cluster binary data streams. The variants include On-line K-means, Scalable K-means, and Incremental K-means, a proposed variant introduced that finds higher quality solutions in less time. Higher quality of solutions are obtained with a mean-based initialization and incremental learning. The speedup is achieved through a simplified set of sufficient statistics and operations with sparse matrices. A summary table of clusters is maintained on-line. The K-means variants are compared with respect to quality of results and speed. The proposed algorithms can be used to monitor transactions.
Keywords
Computer Science
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Some methods for classification and analysis of multivariate observations
22,787 Citations1967James B. MacQueen
Mining association rules between sets of items in large databases
14,720 Citations1993Rakesh Agrawal, Tomasz Imieliński +1 more
An efficient algorithm is presented that generates all significant association rules between items in the database of customer transactions and incorporates buffer management and novel estimation and pruning techniques.
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
ACM SIGMOD RecordMining frequent patterns without candidate generation
6,360 Citations2000Jiawei Han, Jian Pei +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.
Mining frequent patterns without candidate generation
3,195 Citations2000Jiawei Han, Jian Pei +1 more
This study proposes a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develops an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth.
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.
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.
ACM SIGMOD RecordFast algorithms for projected clustering
903 Citations1999Charų C. Aggarwal, Joel L. Wolf +3 more
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.
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.
Clustering data streams
628 Citations2002Suvajyoti Guha, Nita Mishra +2 more
This work gives constant-factor approximation algorithms for the k-median problem in the data stream model of computation in a single pass, and shows negative results implying that these algorithms cannot be improved in a certain sense.
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.
Streaming-data algorithms for high-quality clustering
579 Citations2003Liadan O'Callaghan, Nita Mishra +3 more
This work describes a streaming algorithm that effectively clusters large data streams and provides empirical evidence of the algorithm's performance on synthetic and real data streams.
ACM SIGMOD RecordFinding generalized projected clusters in high dimensional spaces
532 Citations2000Charų C. Aggarwal, Philip S. Yu
Fast algorithms for projected clustering
482 Citations1999Charų C. Aggarwal, Joel L. Wolf +3 more
An algorithmic framework for solving the projected clustering problem, in which the subsets of dimensions selected are specific to the clusters themselves, is developed and tested.
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.
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.
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.
Neural Processing LettersThe LBG-U Method for Vector Quantization – an Improvement over LBG Inspired from Neural Networks
86 Citations1997Bernd Fritzke
It can be proved that LBG-U terminates in a finite number of steps, and experiments with artificial data demonstrate significant improvements in terms of RMSE over LBG combined with only modestly higher computational costs.
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.
FREM
69 Citations2002Carlos Ordońẽz, Edward Omiecinski
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.
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.