Improvement of Fuzzy Geographically Weighted Clustering-Ant Colony Optimization Performance using Context-Based Clustering and CUDA Parallel Programming
DOI:
https://doi.org/10.5614/itbj.ict.res.appl.2017.11.1.2Abstract
Geo-demographic analysis (GDA) is the study of population characteristics by geographical area. Fuzzy Geographically Weighted Clustering (FGWC) is an effective algorithm used in GDA. Improvement of FGWC has been done by integrating a metaheuristic algorithm, Ant Colony Optimization (ACO), as a global optimization tool to increase the clustering accuracy in the initial stage of the FGWC algorithm. However, using ACO in FGWC increases the time to run the algorithm compared to the standard FGWC algorithm. In this paper, context-based clustering and CUDA parallel programming are proposed to improve the performance of the improved algorithm (FGWC-ACO). Context-based clustering is a method that focuses on the grouping of data based on certain conditions, while CUDA parallel programming is a method that uses the graphical processing unit (GPU) as a parallel processing tool. The Indonesian Population Census 2010 was used as the experimental dataset. It was shown that the proposed methods were able to improve the performance of FGWC-ACO without reducing the clustering quality of the original method. The clustering quality was evaluated using the clustering validity index.
References
Son, L.H., Cuong, B.C., Lanzi, P.L. & Thong, N.T., A Novel Intuitionistic Fuzzy Clustering Method for Geo-demographic Analysis, Expert Systems with Applications, 39(10), pp. 9848-9859, 2012.
Son, L.H., Enhancing Clustering Quality of Geo-demographic Analysis using Context Fuzzy Clustering Type-2 and Particle Swarm Optimization, Applied Soft Computing Journal, 22, pp. 566-584, 2014.
Wijayanto, A.W. & Purwarianti, A., Improvement of Fuzzy Geographically Weighted Clustering using Particle Swarm Optimization, in 2014 International Conference on Information Technology System and Innovation (ICITSI), pp. 7-12, 2014.
Wijayanto, A.W., Purwarianti, A. & Son, L.H., Fuzzy Geographically Weighted Clustering using Artificial Bee Colony: An Efficient Geo-demographic Analysis Algorithm and Applications to the Analysis of Crime Behavior in Population, Applied Intelligence, 44(2), pp. 377-398, 2016.
Mason, G.A. & Jacobson, R.D., Fuzzy Geographically Weighted Clustering, in Proceedings of the 9th International Conference on Geocomputation, (1998), pp. 1-7, 2007.
Son, L.H., Cuong, B.C. & Long, H.V., Spatial Interaction - Modification Model and Applications to Geo-demographic Analysis, Knowledge-Based Systems, 49, pp. 152-170, 2013.
Gan, G., Ma, C. & Wu, J., Data Clustering: Theory, Algorithms, and Applications, the American Statistical Association and the Society for Industrial and Applied Mathematics (SIAM), 2007.
Wijayanto, A.W., Improvement of Fuzzy Geo-Demographic Clustering Using Metaheuristic Optimization on Indonesia Population Census, Master's Program Thesis, Institut Teknologi Bandung, Bandung, 2015.
Cuong, B.C., Son, L.H. & Chau, H.T.M., Some Context Fuzzy Clustering Methods for Classification Problems, in Proceedings of the 2010 Symposium on Information and Communication Technology - SoICT '10, p. 34, 2010.
Son, L.H., Lanzi, P.L., Cuong, B.C. & Hung, H.A., Data Mining in GIS"i: A Novel Context-Based Fuzzy Geographically Weighted Clustering Algorithm, International Journal of Machine Learning and Computing, 2(3), pp. 1-4, 2012.
Pedrycz, W., Conditional Fuzzy C-Means, Pattern Recognition Letters, 17(6), pp. 625-631, May 1996.
Nurmala, N. & Purwarianti, A., Improvement of Fuzzy Geographically Weighted Clustering-Ant Colony Optimization using Context-Based Clustering, in 2015 International Conference on Information Technology Systems and Innovation (ICITSI), pp. 1-6, 2015.
Luebke, D., Cuda: Scalable Parallel Programming for High-Performance Scientific Computing, in 2008 5th IEEE International Symposium on Biomedical Imaging: From Nano to Macro, pp. 836-838, 2008.
Jiang, Y., Li, E. & Gao, Z., A GPU-Based Harmony K-Means Algorithm For Document Clustering, in IET International Conference on Information Science and Control Engineering 2012 (ICISCE 2012), pp. 3.29-3.29, 2012,
Glenis A. & Pham, V., A Linear Algebra Approach to C-Means Clustering Using GPUs and MPI, in 2012 16th Panhellenic Conference on Informatics, 7, pp. 198-203, 2012.
Runkler, T.A. & Katz, C., Fuzzy Clustering by Particle Swarm Optimization, in 2006 IEEE International Conference on Fuzzy Systems, pp. 601-608, 2006.
Dorigo, M. & St1/4tzle, T., Ant Colony Optimization, The MIT Press, Cambridge, Massachusetts, United States of America, 2004.
Minh, N.V & Son, L.H., Fuzzy Approaches to Context Variables in Fuzzy Geographically Weighted Clustering, in Computer Science & Information Technology (CS & IT), pp. 21-30, 2015.
Sanders, J. & Kandrot, E., CUDA by Example: An Introduction to General Purpose GPU Programming, Pearson Education Inc., Boston, Massachusetts, United States of America, 2008.
Kirk, D.B. & Hwu, W.W., Programming Massively Parallel Processors: A Hands-on Approach, Elsevier Inc., Burlington, Massachusetts, United States of America, 2010.
Garland, M., Le Grand, S., Nickolls, J., Anderson, J., Hardwick, J., Morton, S., Phillips, E., Zhang, Y. & Volkov, V., Parallel Computing Experiences with CUDA, IEEE Micro, 28(4), pp. 13-27, 2008.
Lee, J.S., Park, S.C., Lee, J.J. & Ham, H.H., Document Clustering using Multi-Objective Genetic Algorithms with Parallel Programming Based on CUDA, in Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics, pp. 280-287, 2014.
Balasko, B., Abonyi, J. & Feil, B., Fuzzy Clustering and Data Analysis Toolbox for Use with Matlab, Veszprem, Hungary, 2005.
Grekousis, G. & Thomas, H., Comparison of Two Fuzzy Algorithms in Geodemographic Segmentation Analysis: The Fuzzy C-Means and Gustafson-Kessel Methods, Applied Geography, 34, pp. 125-136, 2012.
Badan Pusat Statistik, Statistics Indonesia-2010 Population Census, http://sp2010.bps.go.id/, (1 April 2015).
