The k-means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and are inefficient for solving clustering problems in large datasets. Recently, incremental approaches have been developed to resolve difficulties with the choice of starting points. The global k-means and the fast global k-means algorithms are based on such an approach. They iteratively add one cluster center at a time. Numerical experiments show that these algorithms considerably improve the k-means algorithm. However, they require storing the whole affinity matrix or computing this matrix at each iteration. This makes both algorithms time consuming and memory demanding for clustering even moderately large datasets. Also the continuously arriving data stream has become common phenomenon for many fields recent years; for example, sensor networks, web click stream and internet traffic flow. Researchers proposes many innovative technologies to manage such streaming datasets. Finding efficient data stream mining algorithm has become an important research subject. In this paper we propose a fast global k-means algorithm for datasets having streaming behavior. Experiment shows that our proposed algorithm is more efficient than the fast global k-means algorithm in case of streaming datasets

k-Means, Global k-Means, Fast Global k-Means, Data Streaming

[1] Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, “Models and issues in data stream systems,” in Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, ser. PODS ’02, 2002, pp. 1–16.
[2] L. Bai, J. Liang, C. Sui, and C. Dang, “Fast global k-means clustering based on local geometrical information,” Information Sciences, vol. 245, no. 0, pp. 168 – 180, 2013.
[3] I. Fodor. (2002) A Survey of Dimen sion Reduction Techniques. [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.5098
[4] S. T. Roweis and L. K. Saul, “Nonlinear dimensionality reduction by locally linear embedding,” SCIENCE, vol. 290, pp. 2323–2326, 2000.
[5] J. B. Tenenbaum, V. d. Silva, and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction,” Science, vol. 290, no. 5500, pp. 2319–2323, 2000.
[6] H.-P. Kriegel, P. Kro¨ger, and A. Zimek, “Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering,” ACM Trans. Knowl. Discov. Data, vol. 3, no. 1, pp. 1:1–1:58, Mar. 2009.
[7] A. Jain and R. Dubes, Eds., Algorithms for Clustering Data. Prentice Hall, 1988.
[8] A. Likas, M. Vlassis, and J. Verbeek, “The global k-means clustering algorithm,” Pattern Recognition, vol. 35, no. 2, pp. 451–461, 2003.
[9] A. Bagirov, “Modified global k-means algorithm for sum-of-squares clustering problem,” Pattern Recognition, vol. 41, pp. 3192–3199, 2008.
[10] L. O’Callaghan, N. Mishra, A. Meyerson, S. Guha, and R. Motwani, “Streaming-data algorithms for high-quality clustering,” in Data Engi- neering, 2002. Proceedings. 18th International Conference on, 2002, pp. 685–694.
[11] P. Domingos and G. Hulten, “A general method for scaling up machine learning algorithms and its application to clustering,” in Proceedings of the Eighteenth International Conference on Machine Learning, ser. ICML ’01, 2001, pp. 106–113.
[12] C. C. Aggarwal, J. Han, J. Wang, and P. S. Yu, “A framework for clus tering evolving data streams,” in Proceedings of the 29th international conference on Very large data bases - Volume 29, ser. VLDB ’03, 2003, pp. 81-92
[13] R. Wan, X. Yan, and X. Su, “A weighted fuzzy clustering algorithm for data stream,” in Proceedings of the 2008 ISECS International Colloquium on Computing, Communication, Control, and Management- Volume 01, ser. CCCM ’08, 2008, pp. 360–364.
[14] L. Bai, J. Liang, C. Sui, and C. Dang, “Fast global k-means clustering based on local geometrical information,” Information Sciences, vol. 245, no. 0, pp. 168 – 180, 2013.
[15] J. Xie and S. Jiang, “A simple and fast algorithm for global k-means clustering,” in Education Technology and Computer Science (ETCS), 2010 Second International Workshop on, vol. 2, March 2010, pp. 36– 40.
[16] L.-E. Sal, J. Carrasco-Ochoa, and M.-T. Fco, “Fast global k-means with similarity functions algorithm,” in Intelligent Data Engineering and Automated Learning IDEAL 2006, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006, vol. 4224, pp. 512–521.