K-boyutlu ağaç ve uyarlanabilir yarıçap (KD-AR Stream) tabanlı gerçek zamanlı akan veri kümeleme

Year 2020, Volume: 35 Issue: 1, 337 - 354, 25.10.2019

Ali Şenol Hacer Karacan

https://doi.org/10.17341/gazimmfd.467226

Cited By: 1

Abstract

Akan veri kümeleme, teknolojik
gelişmelere paralel olarak veri miktarının inanılmaz boyutlara ulaştığı
gümünüzün popüler konularından biridir. Akan veri kümeleme yaklaşımlarında
karşılaşılan en önemli problemler çoğu yaklaşımın çevrimiçi ve çevrimdışı
evreden oluşması, küme sayısını tanımlama veya bu sayıya bir sınır koyma
zorunluluğu, en doğru yarıçap değerini belirlemede yaşanan problemler ve
önerilen modellerin kendisini gelen yeni verilere adapte etmesinde (concept
evolution)  yaşanan problemlerdir. Bu
problemlerin yanında, neredeyse bu alandaki bütün çalışmaların sayısal miktar
tabanlı bir özetleme yapması da bazı uygulamalar için ihtiyacı
karşılamamaktadır. Oysa son 1 saniyede veya son 1 saatte gelen veriler şeklinde
çalışan zaman tabanlı bir özetleme yaklaşımına da ihtiyaç vardır. Bu çalışmada,
K-boyutlu ağaç, uyarlanabilir yarıçap tabanlı (KD-AR Stream) ve kümeleme
adaptasyonu özelliğine sahip gerçek zamanlı akan verileri kümeleyen bir
yaklaşım önerilmektedir. Önerdiğimiz yöntem SE-Stream, DPStream ve CEDAS
algoritmaları ile hem kümeleme başarısı hem de işlem performansı açısından
karşılaştırılmıştır. Elde edilen sonuçlar KD-AR Stream algoritmasının diğer
algoritmalara göre yüksek bir kümeleme başarısını makul bir sürede
gerçekleştirdiğini göstermektedir.

Keywords

Akan veri kümeleme, k-boyutlu ağaç, uyarlanabilir yarıçap, tamamen çevrimiçi, evrimsel kümeleme

Kd-tree and adaptive radius (KD-AR Stream) based real-time data stream clustering

Abstract

Data stream clustering is one
of the most popular topics of today's world where the amount of data
reaches incredible levels in parallel with technological developments. The most
important problems encountered in data stream clustering approaches are the
fact that most of the approaches consists of an online and offline phases, the
definition of the number of cluster, or the need to set a limitation to this
number, the problems encountered in determining optimum radius value, and the
problems encountered in concept evolution. The present study proposes an
evolutionary based solution method, which is based on Kd-Tree and adaptive
radius (KD-AR Stream) to perform real-time clustering on the streaming data.
The proposed approach has been compared with SE-Stream, DPStream and CEDAS
algorithms in terms of both cluster quality and execution time. The results
showed that KD-AR Stream algorithm has a good clustering performance within a reasonable
time by comparison with the other algorithms.

Keywords

Data stream clustering, kd-tree, adaptive radius, fully online, evolving clustering

References

• Antonellis, P., C. Makris, and N. Tsirakis, Algorithms for clustering clickstream data. Information Processing Letters, 2009. 109(8): p. 381-385.
• Yin, C., L. Xia, and J. Wang. Application of an Improved Data Stream Clustering Algorithm in Intrusion Detection System. in Advanced Multimedia and Ubiquitous Engineering. 2017. Singapore: Springer Singapore.
• Yin, C., L. Xia, and J. Wang. Data Stream Clustering Algorithm Based on Bucket Density for Intrusion Detection. in Advances in Computer Science and Ubiquitous Computing. 2018. Singapore: Springer Singapore.
• Li, Z.Q., A New Data Stream Clustering Approach about Intrusion Detection. Advanced Materials Research, 2014. 926-930: p. 2898-2901.
• Hendricks, D., Using real-time cluster configurations of streaming asynchronous features as online state descriptors in financial markets. Pattern Recognition Letters, 2017. 97: p. 21-28.
• Aggarwal, C.C., Data Streams: An Overview and Scientific Applications, in Scientific Data Mining and Knowledge Discovery: Principles and Foundations, M.M. Gaber, Editor. 2010, Springer Berlin Heidelberg: Berlin, Heidelberg. p. 377-397.
• King, R.C., et al., Application of data fusion techniques and technologies for wearable health monitoring. Medical Engineering & Physics, 2017. 42: p. 1-12.
• Gravina, R., et al., Multi-sensor fusion in body sensor networks: State-of-the-art and research challenges. Information Fusion, 2017. 35: p. 68-80.
• Manzi, A., P. Dario, and F. Cavallo, A Human Activity Recognition System Based on Dynamic Clustering of Skeleton Data. Sensors (Basel, Switzerland), 2017. 17(5): p. 1100.
• Diaz-Rozo, J., C. Bielza, and P. Larrañaga, Clustering of Data Streams with Dynamic Gaussian Mixture Models. An IoT Application in Industrial Processes. IEEE Internet of Things Journal, 2018: p. 1-1.
• Tasnim, S., et al. Semantic-Aware Clustering-based Approach of Trajectory Data Stream Mining. in 2018 International Conference on Computing, Networking and Communications (ICNC). 2018.
• Ankleshwaria, T.B. and J.S. Dhobi, Mining Data Streams: A Survey. International Journal of Advance Research in Computer Science and Management Studies, 2014. 2(2): p. 379-386.
• Ikonomovska, E., S. Loskovska, and D. Gjorgjevik, A survey of stream data mining, in Eighth International Conference with International Participation – ETAI 2007. 2007: Ohrid, Republic of Macedonia.
• Şenol, A. and Karacan H., A Survey on Data Stream Clustering Techniques. European Journal of Science and Technology, 2018(13): p. 17-30.
• Aggarwal, C.C., Data Streams: Models and Algorithms. 1 ed. Advances in Database Systems. 2007: Springer US.
• Bifet, A. and R. Kirkby, Data stream mining a practical approach. 2009.
• O'Callaghan, L., et al. Streaming-data algorithms for high-quality clustering. in Proceedings 1st International Conference on Data Engineering. 2002. San Jose, CA, USA, USA: IEEE.
• Keogh, E., et al. An online algorithm for segmenting time series. in Proceedings 2001 IEEE International Conference on Data Mining 2001. San Jose, CA, USA, USA: IEEE.
• Khalilian, M., N. Mustapha, and N. Sulaiman, Data stream clustering by divide and conquer approach based on vector model. Journal of Big Data, 2016. 3(1): p. 1.
• Aggarwal, C.C., et al., A framework for clustering evolving data streams, in Proceedings of the 29th international conference on Very large data bases - Volume 29. 2003, VLDB Endowment: Berlin, Germany. p. 81-92.
• Charu, C.A., et al., A framework for projected clustering of high dimensional data streams, in Proceedings of the Thirtieth international conference on Very large data bases - Volume 30 %@ 0-12-088469-0. 2004, VLDB Endowment: Toronto, Canada. p. 852-863.
• Zhang, T., R. Ramakrishnan, and M. Livny, BIRCH: an efficient data clustering method for very large databases. SIGMOD Rec., 1996. 25(2): p. 103-114.
• Karypis, G., E.-H. Han, and V. Kumar, Chameleon: Hierarchical Clustering Using Dynamic Modeling. Computer, 1999. 32(8): p. 68-75.
• Udommanetanakit, K., T. Rakthanmanon, and K. Waiyamai. E-Stream: Evolution-Based Technique for Stream Clustering. 2007. Berlin, Heidelberg: Springer Berlin Heidelberg.
• Rodrigues, P.P., J. Gama, and J. Pedroso, Hierarchical Clustering of Time-Series Data Streams. IEEE Transactions on Knowledge and Data Engineering, 2008. 20(5): p. 615-627.
• Chairukwattana, R., et al. Efficient evolution-based clustering of high dimensional data streams with dimension projection. in 2013 International Computer Science and Engineering Conference (ICSEC). 2013.
• Meesuksabai, W., T. Kangkachit, and K. Waiyamai. HUE-Stream: Evolution-Based Clustering Technique for Heterogeneous Data Streams with Uncertainty. 2011. Berlin, Heidelberg: Springer Berlin Heidelberg.
• Yeh, M.Y., B.R. Dai, and M.S. Chen, Clustering over Multiple Evolving Streams by Events and Correlations. IEEE Transactions on Knowledge and Data Engineering, 2007. 19(10): p. 1349-1362.
• Kranen, P., et al., The ClusTree: indexing micro-clusters for anytime stream mining. Knowledge and Information Systems, 2011. 29(2): p. 249-272.
• Wang, W., J. Yang, and R.R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, in Proceedings of the 23rd International Conference on Very Large Data Bases. 1997, Morgan Kaufmann Publishers Inc. p. 186-195.
• Sheikholeslami, G., S. Chatterjee, and A. Zhang, WaveCluster: a wavelet-based clustering approach for spatial data in very large databases. The VLDB Journal, 2000. 8(3): p. 289-304.
• Agrawal, R., et al., Automatic subspace clustering of high dimensional data for data mining applications. SIGMOD Rec., 1998. 27(2): p. 94-105.
• Tu, L. and Y. Chen, Stream data clustering based on grid density and attraction. ACM Trans. Knowl. Discov. Data, 2009. 3(3): p. 1-27.
• Gao, J., et al. An Incremental Data Stream Clustering Algorithm Based on Dense Units Detection. 2005. Berlin, Heidelberg: Springer Berlin Heidelberg.
• Jia, C., C. Tan, and A. Yong. A Grid and Density-Based Clustering Algorithm for Processing Data Stream. in 2008 Second International Conference on Genetic and Evolutionary Computing. 2008.
• Wan, L., et al., Density-based clustering of data streams at multiple resolutions. ACM Trans. Knowl. Discov. Data, 2009. 3(3): p. 1-28.
• Dempster, A., N.M. Laird, and D.B. Rubin, Maximum Likelihood from Incomplete Data via the EM Algorithm, in Paper presented at the Royal Statistical Society at a meeting organized by the Research Section. 1976.
• Dang, X.H., et al. An EM-Based Algorithm for Clustering Data Streams in Sliding Windows. 2009. Berlin, Heidelberg: Springer Berlin Heidelberg.
• Chaovalit, P. and A. Gangopadhyay, A method for clustering transient data streams, in Proceedings of the 2009 ACM symposium on Applied Computing. 2009, ACM: Honolulu, Hawaii. p. 1518-1519.
• Choromanski, K., S. Kumar, and X. Liu, Fast Online Clustering with Randomized Skeleton Sets. CoRR, 2015. abs/1506.03425.
• Ester, M., et al., A density-based algorithm for discovering clusters in large spatial databases with noise, in Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. 1996, AAAI Press: Portland, Oregon. p. 226-231.
• Ankerst, M., et al., OPTICS: ordering points to identify the clustering structure. SIGMOD Rec., 1999. 28(2): p. 49-60.
• Hinneburg, A. and D.A. Keim, An efficient approach to clustering in large multimedia databases with noise, in Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining. 1998, AAAI Press: New York, NY. p. 58-65.
• Ntoutsi, I., et al. Density-based Projected Clustering over High Dimensional Data Streams. in SIAM International Conference on Data Mining. 2012.
• Amini, A. and T.Y. Wah, LeaDen-Stream: A Leader Density-Based Clustering Algorithm over Evolving Data Stream. Journal of Computer and Communications, 2013. 1: p. 26-31.
• Hyde, R. and P. Angelov. A new online clustering approach for data in arbitrary shaped clusters. in 2015 IEEE 2nd International Conference on Cybernetics (CYBCONF). 2015.
• Mousavi, M. and A. Abu Bakar, Improved density based algorithm for data stream clustering. Jurnal Teknologi, 2015. 77(18): p. 73-77.
• Ahmed, I., I. Ahmed, and W. Shahzad, Scaling up for high dimensional and high speed data streams: HSDStream. CoRR, 2015. abs/1510.03375.
• Liu, L.x., et al. rDenStream, A Clustering Algorithm over an Evolving Data Stream. in 2009 International Conference on Information Engineering and Computer Science. 2009.
• Cao, F., et al., Density-Based Clustering over an Evolving Data Stream with Noise, in Proceedings of the 2006 SIAM International Conference on Data Mining. 2006, Society for Industrial and Applied Mathematics. p. 328-339.
• Ren, J. and R. Ma. Density-Based Data Streams Clustering over Sliding Windows. in 2009 Sixth International Conference on Fuzzy Systems and Knowledge Discovery. 2009.
• Hyde, R., P. Angelov, and A.R. MacKenzie, Fully online clustering of evolving data streams into arbitrarily shaped clusters. Information Sciences, 2017. 382-383: p. 96-114.
• Chaoji, V., et al. SPARCL: Efficient and Effective Shape-Based Clustering. in 2008 Eighth IEEE International Conference on Data Mining. 2008.
• Cao, F., et al., Density-Based Clustering over an Evolving Data Stream with Noise, in Proceedings of the 2006 SIAM International Conference on Data Mining. p. 328-339.
• Xu, J., et al., Fat node leading tree for data stream clustering with density peaks. Knowledge-Based Systems, 2017. 120: p. 99-117.
• Badiozamany, S., K. Orsborn, and T. Risch, Framework for real-time clustering over sliding windows, in Proceedings of the 28th International Conference on Scientific and Statistical Database Management. 2016, ACM: Budapest, Hungary. p. 1-13.
• Hahsler, M. and M. Bolaños, Clustering Data Streams Based on Shared Density between Micro-Clusters. IEEE Transactions on Knowledge and Data Engineering, 2016. 28(6): p. 1449-1461.
• Guha, S., R. Rastogi, and K. Shim, Cure: an efficient clustering algorithm for large databases. Information Systems, 2001. 26(1): p. 35-58.
• Aggarwal, C., Y. Zhao, and P. Yu, On Clustering Graph Streams, in Proceedings of the 2010 SIAM International Conference on Data Mining. 2010, Society for Industrial and Applied Mathematics. p. 478-489.
• Chen, J., P. Chen, and X.g. Sheng, A Sketch-based Clustering Algorithm for Uncertain Data Streams. JNW, 2013. 8: p. 1536-1542.
• Ye, Y. Spatial data structure: the K-D tree. 10 May 2018]; Spatial data structure: the K-D tree]. Available from: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/moretrees.php.
• Kreveld, M.v. and W.v. Toll. Computational Geometry - Lecture 7: Range searching and kd-trees. 2018 12 January 2018]; Lecture Notes]. Available from: http://www.cs.uu.nl/docs/vakken/ga/slides5a.pdf.