Title :
Approximation of kernel k-means for streaming data
Author :
Havens, Timothy C.
Author_Institution :
Dept. of Electr. & Comput. Eng., Michigan Technol. Univ., Houghton, MI, USA
Abstract :
Streaming data are any data that are sequentially presented to a system such that future data cannot be accessed. By their nature, streaming data are often large data sets and can quickly outgrow the working memory for a typical computer. Clustering is one of the primary tasks used in the pattern recognition and data mining communities and kernel k-means is a well-studied and popular algorithm. However, kernel k-means is ill-suited to streaming data. In this paper, I develop an approximation to the kernel k-means that only needs access to data from time-step t and (t-1); hence, the memory requirement of the proposed algorithm is only O(n2), where n is the size of the data chunk at time t. Empirical results show that streaming kernel k-means (skKM) produces partitions similar to those produced by kernel k-means run on the entire data set.
Keywords :
approximation theory; data mining; pattern clustering; O(n2); approximation; clustering analysis; data chunk; data mining communities; kernel k-means; pattern recognition; streaming data; Clustering algorithms; Complexity theory; Equations; Kernel; Memory management; Standards; Vectors;
Conference_Titel :
Pattern Recognition (ICPR), 2012 21st International Conference on
Conference_Location :
Tsukuba
Print_ISBN :
978-1-4673-2216-4