A Computational Cost-Effective Clustering Algorithm in Multidimensional Space Using the Manhattan Metric: Application to the Global Terrorism Database

Authors: Semeh Ben Salem, Sami Naouali, Moetez Sallami

Abstract:

The increasing amount of collected data has limited the performance of the current analyzing algorithms. Thus, developing new cost-effective algorithms in terms of complexity, scalability, and accuracy raised significant interests. In this paper, a modified effective k-means based algorithm is developed and experimented. The new algorithm aims to reduce the computational load without significantly affecting the quality of the clusterings. The algorithm uses the City Block distance and a new stop criterion to guarantee the convergence. Conducted experiments on a real data set show its high performance when compared with the original k-means version.

Keywords: Pattern recognition, partitional clustering, K-means clustering, Manhattan distance, terrorism data analysis.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1130685

References:

[1] De Bruin, J. S, Cocx, T. K, Kosters, W. A, Laros, “Data Mining approaches to criminal career analysis.” In Proceedings of the 6th International Conference on Data Mining ICDM’06, pp 11-18, 2006.
[2] T. Abraham and O. de Vel, “Investigating profiling with computer forensic log data and associations rules.” Proceedings of the IEEE International Conference on Data Mining (ICDM’06), pp 11-18, 2006.
[3] Jiawei Han M. K, “Data Mining concepts and techniques.” Morgan Kaufmann Publishers, An Imprint of Elsevier, 2006.
[4] Huang Z, “Extension to the k-means algorithm for clustering large datasets with categorical values”, Data Mining and Knowledge Discovery, (2):283-304, 1998.
[5] Amir Ahmad, Lipika Dey, “A k-means clustering algorithm for mixed numeric and categorical data.” Data and Knowledge Engineering 63, pp 503-527, 2007.
[6] V. Ganti, J. E Gekhre, R. Ramakrishnan, “CACTUS clustering categorical data using summaries”, Proceedings of the 5th ACM SIGKDD International Conference On Knowledge Discovery and Data Mining, 1999, pp 73-83.
[7] T. Zhang, R. Ramakrishnan, M. Livny, “BIRCH: an efficient data clustering method for very large databases.” SIGMOD Conference, 1996, pp 130-114.
[8] Dong Kuan Xu, Yingjie Tian, “A Comprehensive Survey of Clustering Algorithms”, Ann. Data. Sci. , Springer-Verlag Berlin Heidelberg 2015, DOI 10.1007/s40745-015-0040-1
[9] Celebi M E, Kingravi H A Vela P A, “A comparative study of efficient initialization methods for the k-means clustering algorithm”. Expert Systems with Applications 40:200–210, 2013.
[10] Celebi M E, Kingravi H, “Deterministic initialization of the K-means algorithm using hierarchical clustering”, International Journal of Pattern Recognition and Artificial Intelligence 26(7):1250018, 2012.
[11] Celebi M E, Kingravi H, “Linear, deterministic, and order-invariant initialization methods for the K-means clustering algorithm.’’ Celebi M E (ed) Partitional clustering algorithms. Springer, Berlin, pp 79–98, 2014.
[12] Kalogeratos A, Likas A, “Dip-means: an incremental clustering method for estimating the number of clusters.” In: Advances in neural information processing systems (NIPS), pp 2402–2410, 2012.
[13] Tzortzis G, Likas A, “The Min-Max k-Means clustering algorithm”. Pattern Recognition 47:2505–2516-2014.
[14] Eslamnezhad M, Varjani A Y, “Intrusion detection based on Min-Max K-means clustering.” In 7th International symposium on telecommunications (IST’2014), pp 804–808-2014.
[15] Yuan F, Meng Z. H, Zhang H, X and Dong C. R, “A new algorithm to get the initial centroids.” Proceedings of the 3rd International Conference on Machine Learning and Cybernetics, pages 26-29, 2004.
[16] Xiaoyan Wang, Yanping Bai, “The global Min-Max k means algorithm”, Wang and Bai SpringerPlus 5:1665, DOI 10.1186/s40064 016 3329 4-2016.
[17] Zengyou He, Shengchun Deng “Improving K-modes Algorithm considering frequencies of attributes values in mode.” Conference paper in Lecture notes in computer science, December 2005.
[18] G. La Free, “The Global Terrorism Database: Accomplishments and Challenges”, Perspectives on Terrorism, Vol. 4 (2010).
[19] X. Wang, E. Miller, K. Smarick, W. Ribarsky and R. Chang, “Investigative Visual Analysis of Global terrorism.”, Proceeding of the 10th Joint Eurographics/ IEEE-VGTC conference on Visualization, Vol. 27 (2008): 919-926.
[20] M. Adnan, M. Rafi, “Extracting patterns from Global Terrorism Database (GTD) sing co-clustering approach.” Journal of independent studies and research computing, Volume 13, 2015.
[21] Semeh Ben Salem and Sami Naouali, “Pattern Recognition Approach in Multidimensional Databases: Application to the Global Terrorism Database” International Journal of Advanced Computer Science and Applications (IJACSA), 7(8), 2016.
[22] Silke Wagner, Dorothea Wagner, “Comparing Clusterings-An Overview”, January 12, 2007.