Overview of Different Methods Used in Clustering Algorithms

Year 2020, , 173 - 189, 01.10.2020

Tohid Yousefi , Mehmet Serhat Odabas , Recai Oktaş

https://doi.org/10.34248/bsengineering.698741

Abstract

Data mining is the process of extracting meaningful information from large databases using many techniques and algorithms. Data mining is often referred to as "information discovery in data" and many methods are used to find this information. Clustering method, which is one of the basic methods of data mining, is one of the most powerful methods to analyze these data, while data is being produced rapidly in today's world. Clustering is the technique of finding natural groupings or clusters in data based on some similarity distances. Also clustering is essentially a fundamental step in many different data analyzes. Therefore, different methods used in clustering algorithms are briefly described in this review.

Keywords

Algorithm, Clustering, Partitional clustering, Density-based clustering, Hierarchical clustering

Kümeleme Algoritmalarında Kullanılan Farklı Yöntemlere Genel Bakış

Abstract

Veri madenciliği, birçok teknik ve algoritmayı kullanarak büyük veri tabanlarından anlamlı bilgileri çıkarma işlemidir. Veri madenciliği genellikle, “verilerde bilgi keşfi” olarak adlandırılan ve bu bilgileri bulmak için kullanılan yöntemlerdir. Veri madenciliğinin temel yöntemlerinden birisi olan kümeleme yöntemidir. Kümeleme yöntemi günümüz dünyasında hızla çoğalan verilerin analizinde kullanılacak en güçlü yöntemlerdendir. Kümeleme bazı benzerlik mesafelerine dayalı olarak verilerdeki doğal gruplamaları veya kümeleri bulma tekniğidir. Kümeleme aslında birçok farklı veri analizlerinde temel bir adımdır. Bundan dolayı bu derlemede kümeleme algoritmalarında kullanılan farklı yöntemler özet bir şekilde anlatılmıştır.

Keywords

Algoritma, Kümeleme, Hiyerarşik kümeleme, Bölümsel Kümeleme, Yoğunluk tabanlı kümeleme

References

• Agrawal R, Gehrke J, Gunopulos D, Raghavan P. 1998. Automatic subspace clustering of high dimensional data for data mining applications. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data.
• Agrawal R, Gehrke JE, Gunopulos D, Raghavan P. 1999.Automatic subspace clustering of high dimensional data for data mining applications. In: Google Patents.
• Alldrin N, Smith A, Turnbull DJ. 2003. Clustering with EM and K-means. University of San Diego, California, Tech Report. 261-295.
• Anderberg MR. 2014.Cluster analysis for applications: probability and mathematical statistics: a series of monographs and textbooks, Cilt 19. Academic press.
• Ankerst M, Breunig MM, Kriegel HP, Sander J. 1999. OPTICS: ordering points to identify the clustering structure. ACM SIGMOD Record, 28(2): 49-60.
• Belacel N, Wang Q,Cuperlovic-Culf M. 2006. Clustering methods for microarray gene expression data. OMICS, 104: 507-531.
• Belli F, Beyazit M, Güler N. 2012. Event-Oriented, Model-Based GUI Testing and Reliability Assessment—Approach and Case Study. Advances in Computers, 85: 277-326.
• Berggren JL. 2017.Episodes in the mathematics of medieval Islam: Springer.
• Berkhin P. 2006. A survey of clustering data mining techniques. Grouping multidimensional data s. 25-71: Springer.
• Bezdek JC. 1973. Cluster validity with fuzzy sets.
• Bezdek JC. 1981. Objective function clustering. Pattern recognition with fuzzy objective function algorithms. 43-93: Springer.
• Bezdek JC, Pal SK. 1994. Fuzzy models for pattern recognition.
• Bezdek JC. 1980. A convergence theorem for the fuzzy ISODATA clustering algorithms. IEEE transact, 1: 1-8.
• Bhat A. 2014. K-medoids clustering using partitioning around medoids for performing face recognition. Int J Soft Comput, Math Cont, 3(3): 1-12.
• Bishop CM. 1995.Neural networks for pattern recognition: Oxford university press.
• Blass A, Gurevich Y. 2004. Algorithms: A quest for absolute definitions. Current Trends in Theoretical Computer Science: The Challenge of the New Century Vol 1: Algorithms and Complexity Vol 2: Formal Models and Semantics, Scientific.
• Böhm C, Noll R, Plant C, Wackersreuther B. 2009. Density-based clustering using graphics processors. Proceedings of the 18th ACM conference on Information and knowledge management.
• Brecheisen S, Kriegel HP, Pfeifle M. 2004. Efficient density-based clustering of complex objects. Paper presented at the Fourth IEEE International Conference on Data Mining ICDM'04.
• Brecheisen S, Kriegel HP, Pfeifle M. 2006. Parallel density-based clustering of complex objects. Pacific-Asia Conference on Knowledge Discovery and Data Mining.
• Chakravarthy SV, Ghosh J. 1996. Scale-based clustering using the radial basis function network. IEEE Transact, 7(5): 1250-1261.
• Chauhan R. 2014. Clustering Techniques: a comprehensive study of various clustering techniques. Inter J Advance Res Comput Sci, 5(5).
• Chen S, Zhang D. 2004. Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure. IEEE Transact, 34(4): 1907-1916.
• Cheng W, Wang W, Batista S. 2018. Grid-based clustering. Data Clustering s. 128-148: Chapman and Hall/CRC.
• Cherng JS, Lo MJ. 2001. A hypergraph based clustering algorithm for spatial data sets. Proceedings 2001 IEEE International Conference on Data Mining.
• Cord M,Cunningham P. 2008.Machine learning techniques for multimedia: case studies on organization and retrieval: Springer Science & Business Media.
• Cormen TH, Leiserson CE, Rivest RL, Stein C. 2009.Introduction to algorithms: MIT press.
• Cottrell M, Olteanu M, Rossi F, Villa Vialaneix N. 2018. Self-organizing maps, theory and applications.
• Dabhi DP, Patel MR. 2016. Extensive survey on hierarchical clustering methods in data mining. Int Res J Eng and Tech IRJET, 3: 659-665.
• Davies ER. 2004.Machine vision: theory, algorithms, practicalities: Elsevier.
• Deepa MS, Sujatha N. 2014. Comparative Studies of Various Clustering Techniques and Its Characteristics. Int J Adv Netw App, 5(6): 2104.
• Dellaert F. 2002. The expectation maximization algorithm.
• Dempster AP, Laird NM,Rubin DB. 1977. Maximum likelihood from incomplete data via the EM algorithm. J Royal Stat Soc: Series B Meth, 39(1): 1-22.
• Dunham MH. 2006.Data mining: Introductory and advanced topics: Pearson Education India.
• Edla DRJana PK. 2012. A grid clustering algorithm using cluster boundaries. World Congress on Information and Communication Technologies.
• Emami H, Dami S, Shirazi H. 2015. K-Harmonic means data clustering with ımperialist competitive algorithm. UPB Sci Bull, Series C, 77(1): 91-104.
• Erickson J. 2019.Algorithms Jeff Erickson.
• Ester M, Kriegel HP, Sander J, Xu X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. Paper presented at the Kdd.
• Estivill Castro V. 2002. Why so many clustering algorithms: a position paper. ACM SIGKDD, 4(1): 65-75.
• Everitt BS. 1979. Unresolved problems in cluster analysis. Biometrics, 169-181.
• Firdaus S, Uddin MA. 2015. A survey on clustering algorithms and complexity analysis. Int J Comp Sci Iss IJCSI, 12(2): 62.
• Fisher DH. 1987. Improving Inference through Conceptual Clustering. AAAI, 461-465.
• Fisher DH. 1987. Knowledge acquisition via incremental conceptual clustering. Mach Learn, 2(2): 139-172.
• Forgy EW. 1965. Cluster analysis of multivariate data: efficiency versus interpretability of classifications. Biometrics, 21: 768-769.
• Frigui H, Krishnapuram R. 1997. Clustering by competitive agglomeration. Pattern Recog, 30(7): 1109-1119.
• Goldschlager L, Lister A. 1988. Computer science: a modern introduction: Prentice Hall International UK Ltd.
• Goodrich MT, Tamassia R. 2014.Algorithm design and applications: Wiley Publishing.
• Guha S, Rastogi R, Shim K. 1998. CURE: an efficient clustering algorithm for large databases. ACM Sigmod Rec, 27(2): 73-84.
• Guha S, Rastogi R, Shim K. 2000. ROCK: A robust clustering algorithm for categorical attributes. Information Sys, 25(5): 345-366.
• Guo C, Peng L. 2008. A hybrid clustering algorithm based on dimensional reduction and k-harmonic means. 4th International Conference on Wireless Communications, Networking and Mobile Computing.
• Gupta GK. 2014.Introduction to data mining with case studies: PHI Learning Pvt. Ltd.
• Hamerly G, Elkan C. 2002. Alternatives to the k-means algorithm that find better clusterings. Proceedings of the eleventh international conference on Information and knowledge management.
• Hamerly GJ, Elkan CP. 2003. Learning structure and concepts in data through data clustering. University of California, San Diego,
• Han J, Kamber M, Pei J. 2012. Data mining: concepts and techniques. Elsevier.
• Han J, Pei J, Kamber M. 2011.Data mining: concepts and techniques: Elsevier.
• Hartigan JA. 1996.Clustering algorithms. New York: John Wiley & Sons.
• Hartigan JA, Wong MA. 1979. Algorithm AS 136: a k-means clustering algorithm. J Royal Stat Soc, Series C, 28(1): 100-108.
• Hilton ML, Jawerth BD, Sengupta A. 1994. Compressing still and moving images with wavelets. Multimedia Sys, 2(5): 218-227.
• Hinneburg A, Keim DA. 1998. An efficient approach to clustering in large multimedia databases with noise. Paper presented at the KDD.
• Hinton GE, Sejnowski TJ, Poggio TA. 1999.Unsupervised learning: foundations of neural computation: MIT press.
• Huang Z. 1998. Extensions to the k-means algorithm for clustering large data sets with categorical values. Data Mining Know Disc, 2(3): 283-304.
• Iba W, Langley P. 2011. 11 cobweb models of categorization and probabilistic concept formation. Formal approaches in categorization, 253.
• Ilango M, Mohan V. 2010. A survey of grid based clustering algorithms. Int J Eng Sci and Tech, 2(8): 3441-3446.
• Issaq HJ, Veenstra TD. 2019.Proteomic and metabolomic approaches to biomarker discovery: Academic Press.
• Jain AK, Dubes RC. 1988.Algorithms for clustering data. Englewood Cliffs, New Jersey: Prentice-Hall.
• Jain AK, Maheswari S. 2012. Survey of recent clustering techniques in data mining. Int J Comput Sci Manag Res, 3(2): 68-75.
• Jain AK, Murty MN, Flynn PJ. 1999. Data clustering: a review. ACM Comp Surv CSUR, 31(3): 264-323.
• Jiang C, Pan X, Gu M. 1994. The use of mixture models to detect effects of major genes on quantitative characters in a plant breeding experiment. Genetics, 136(1): 383-394.
• Joshi A, Kaur R. 2013. A review: Comparative study of various clustering techniques in data mining. Int J Adv Res in Comp Sci and Softw Eng, 3(3).
• Kailing K, Kriegel HP, Kröger P. 2004. Density-connected subspace clustering for high-dimensional data. Proceedings of the 2004 SIAM International Conference On Data Mining.
• Karypis G, Han EH, Kumar V. 1999. Chameleon: Hierarchical clustering using dynamic modeling. Comp, 32(8): 68-75.
• Kaufman L, Rousseeuw PJ. 2009.Finding groups in data: an introduction to cluster analysis. John Wiley & Sons.
• Kaufmann L. 1987. Clustering by Means of medoids. Proc. Statistical Data Analysis Based on the L1 Norm Conference, Neuchatel, 1987, 405-416.
• Kaur PJ. 2015. A survey of clustering techniques and algorithms. Paper presented at the 2015 2nd international conference on computing for sustainable global development (INDIACom).
• Khatami A, Mirghasemi S, Khosravi A, Nahavandi S. 2015. A new color space based on k-medoids clustering for fire detection. IEEE International Conference on Systems, Man, and Cybernetics.
• Knuth DE. 1980. Algorithms in Modern Mathematics and Computer Science.
• Knuth DE. 2014.Art of computer programming, volume 2: Seminumerical algorithms: Addison-Wesley Professional.
• Kohonen T. 1982. Self-organized formation of topologically correct feature maps. Biol Cyber, 43(1): 59-69.
• Kohonen T. 1990. The self-organizing map. Proceedings of the IEEE, 78(9): 1464-1480.
• Kokate U, Deshpande A, Mahalle P, Patil P. 2018. Data stream clustering techniques, applications, and models: comparative analysis and discussion. Big Data Cogn Comput, 2(4): 32.
• Kothari R, Pitts D. 1999. On finding the number of clusters. Pattern Recog Lett, 20(4): 405-416.
• Kotsiantis S, Pintelas P. 2004. Recent advances in clustering: A brief survey. WSEAS Transactions on Information Sci and App, 1(1): 73-81.
• Kriegel HP, Zimek A. 2010. Subspace clustering, ensemble clustering, alternative clustering, multiview clustering: what can we learn from each other. Paper presented at the Proceedings of the 1st international workshop on discovering, summarizing and using multiple clusterings MultiClust held in conjunction with KDD.
• Kriegel HP, Kröger P, Sander J, Zimek A. 2011. Density‐based clustering. Wiley Interdis Rev: Data Mining Know Disc, 1(3): 231-240.
• Lai C, Nguyen NT. 2004. Predicting density-based spatial clusters over time. Fourth IEEE International Conference on Data Mining ICDM'04.
• Leung Y, Zhang JS, Xu ZB. 2000. Clustering by scale-space filtering. IEEE trans, 22(12): 1396-1410.
• Lu B, Charlton M, Brunsdon C, Harris P. 2016. The Minkowski approach for choosing the distance metric in geographically weighted regression. Inter J Geo Inf Sci, 30(2): 351-368.
• Mahi H, Farhi N, Labed K. 2015. Remotely sensed data clustering using K-harmonic means algorithm and cluster validity index. IFIP International Conference on Computer Science and its Applications.
• Malkauthekar M. 2013. Analysis of Euclidean distance and Manhattan distance measure in Face recognition.
• Mallick P, Ghosh O, Seth P, Ghosh A. 2019. Kohonen’s Self-organizing Map Optimizing Prediction of Gene Dependency for Cancer Mediating Biomarkers. merging Technologies in Data Mining and Information Security, 863-870: Springer.
• McLachlan GJ, Krishnan T. 2007. The EM algorithm and extensions. John Wiley & Sons.
• Mehrotra K, Mohan CK, Ranka S. 1997.Elements of artificial neural networks: MIT press.
• Melnykov V, Michael S, Melnykov I. 2015. Recent developments in model-based clustering with applications. Partitional clustering algorithms s. 1-39: Springer.
• Merigo JM, Casanovas M. 2011. A new Minkowski distance based on induced aggregation operators. Int J Comput Intel Sys, 4(2): 123-133.
• Mesquita DP, Gomes JP, Junior AHS, Nobre JS. 2017. Euclidean distance estimation in incomplete datasets. Neurocomp, 248: 11-18.
• Metcalf L, Casey W. 2016.Cybersecurity and Applied Mathematics: Syngress.
• MITS M. 2017. Mining of Images by K-Medoid Clustering Using Content Based Descriptors. Int J Signal Proces, Image Proces and Pattern Recog, 10(8): 135-144.
• Müldner T. 2003. An algorithm for explaining algorithms. Unpublished manuscript, Acadia University.
• Murtagh F, Contreras P. 2011. Methods of hierarchical clustering. arXiv preprint arXiv:1105.0121.
• Murtagh F. 1984. Counting dendrograms: a survey. Discrete App Math, 7(2): 191-199.
• Myatt GJ, Johnson WP. 2009.Making sense of data II: A practical guide to data visualization, advanced data mining methods, and applications: Wiley Online Library.
• Na S, Xumin L, Yong G. 2010. Research on k-means clustering algorithm: An improved k-means clustering algorithm. Paper presented at the 2010 Third International Symposium on intelligent information technology and security informatics.
• Nakamura E, Kehtarnavaz N. 1998. Determining number of clusters and prototype locations via multi-scale clustering. Pattern Recog Let, 19(14): 1265-1283.
• Nazeer KA, Sebastian M. 2009. Improving the Accuracy and Efficiency of the k-means Clustering Algorithm. Paper presented at the Proceedings of the world congress on engineering.
• Nielsen F. 2016. Hierarchical clustering. Introduction to HPC with MPI for Data Science s. 195-211: Springer.
• Pandya AS, Macy RB. 1995.Pattern recognition with neural networks in C++: CRC press.
• Parikh M, Varma T. 2014. Survey on different grid based clustering algorithms. International Journal of Advance Research in Computer Science and Management Studies, 2(2).
• Park HS, Lee JS, Jun CH. 2006. A K-means-like Algorithm for K-medoids Clustering and Its Performance. Proceedings of ICCIE, 102-117.
• Polycarpou MM, Helmicki AJ. 1995. Automated fault detection and accommodation: a learning systems approach. IEEE Trans, 25(11): 1447-1458.
• Pujari AK. 2001.Data mining techniques: Universities press.
• Rao C, Gudivada VN. 2018.Computational Analysis and Understanding of Natural Languages: Principles, Methods and Applications . Elsevier.
• Rao VS, Vidyavathi DS. 2010. Comparative investigations and performance analysis of FCM and MFPCM algorithms on iris data. Indian J Comp Sci and Eng, 1(2): 145-151.
• Reddy BO, Ussenaiah DM. 2012. Literature survey on clustering techniques. IOSR J Comp Eng, 3: 01-12.
• Reddy M, Makara V, Satish R. 2017. Divisive Hierarchical Clustering with K-means and Agglomerative Hierarchical Clustering. Int J Comp Sci Trends Technol, 5(5): 6-11.
• Redner RA, Walker HF. 1984. Mixture densities, maximum likelihood and the EM algorithm. SIAM Rev, 26(2): 195-239.
• Rezende HR, Esmin AAA. 2010. Proposed application of data mining techniques for clustering software projects. INFOCOMP J Comp Sci, 9(6): 43-48.
• Roberts SJ. 1997. Parametric and non-parametric unsupervised cluster analysis. Pattern Recog, 30(2): 261-272.
• Rodriguez A, Laio A. 2014. Clustering by fast search and find of density peaks. Sci, 344 6191: 1492-1496.
• Rokach L, Maimon O. 2005. Clustering methods. Data mining and knowledge discovery handbook. 321-352. Springer.
• Romesburg C. 2004.Cluster analysis for researchers: Lulu. com.
• Ruspini EH. 1969. A new approach to clustering. Inf Cont, 15(1): 22-32.
• Ruspini EHJIS. 1970. Numerical methods for fuzzy clustering. Inform Sci, 2(3): 319-350.
• Sathya R, Abraham A. 2013. Comparison of supervised and unsupervised learning algorithms for pattern classification. Int J Adv Res in Artif Intel, 2(2): 34-38.
• Schmee J, Hahn GJ. 1979. A simple method for regression analysis with censored data. Technometrics, 21(4): 417-432.
• Shah M, Nair S. 2015. A survey of data mining clustering algorithms. Int J Comp App, 128(1): 1-5.
• Sheikholeslami G, Chatterjee S, Zhang A. 1998. Wavecluster: A multi-resolution clustering approach for very large spatial databases. Proceedings the VLDB, 98.
• Sheikholeslami G, Chatterjee S, Zhang A. 2000. WaveCluster: a wavelet-based clustering approach for spatial data in very large databases. The VLDB J, 8(3-4): 289-304.
• Sheikholeslami G, Zhang A. 1997. Approach to clustering large visual databases using wavelet transform. Visual Data Exploration and Analysis IV.
• Sheikholeslami G, Zhang A, Bian L. 1997. Geographical image classification and retrieval. 5th ACM international workshop on Advances in geographic information systems.
• Singh M. 2015. A survey on various k-means algorithms for clustering. Inter J Comput Sci Network Sec 15(6): 60.
• Smith JR, Chang SF. 1994. Transform features for texture classification and discrimination in large image databases. Proceedings of 1st International Conference on Image Processing.
• Sneath PH, Sokal RR. 1973.Numerical taxonomy. The principles and practice of numerical classification.
• Sun S, Qin K. 2007. Research on Modified k-means Data Cluster Algorithm. Fine Particles, Thin Films and Exchange Anisotropy. Comp Eng, 7(6): 200-202.
• Swarndeep Saket J, Pandya S. 2016. Implementation of Extended K-Medoids Algorithms to Increase Efficiency and Scalability using Large Dataset. Int J Comp App, 975: 8887.
• Szabo F. 2015.The linear algebra survival guide: illustrated with Mathematica: Academic Press.
• Thakare YBagal SJIJoCA. 2015. Performance evaluation of K-means clustering algorithm with various distance metrics. IEEE Trans, 110(11): 12-16.
• Theodorakis M, Vlachos A, Kalamboukis TZ. 2004. Using hierarchical clustering to enhance classification accuracy. Paper presented at the Proceedings of 3rd Hellenic Conference in Artificial Intelligence, Samos.
• Thilagavathi G, Srivaishnavi D, Aparna N. 2013. A survey on efficient hierarchical algorithm used in clustering. Int J Eng, 2(9): 165-176.
• Tian Y, Liu D, Qi H. 2009. K-harmonic means data clustering with differential evolution. International Conference on Future BioMedical Information Engineering FBIE.
• Turi RH. 2001.Clustering-based colour image segmentation: Monash University PhD thesis.
• Tyagi A, Sharma S. 2012. Implementation Of ROCK Clustering Algorithm For The Optimization Of Query Searching Time. Int J Comp Sci and Eng, 4(5): 809.
• Uppada SK. 2014. Centroid based clustering algorithms—A clarion study. Int J Comp Sci Inf Tech, 5(6): 7309-7313.
• Veenman CJ, Reinders MJT, Backer E. 2002. A maximum variance cluster algorithm. IEEE Trans, 24(9): 1273-1280.
• Vimal A, Valluri SR, Karlapalem K. 2008. An Experiment with Distance Measures for Clustering. Proceedings COMAD 2008.
• Wang W, Yang J, Muntz R. 1997. STING: A statistical information grid approach to spatial data mining. Proceedings VLDB '97.
• Weinstein E. 2006. Expectation maximization algorithm and applications. Courant Institute of Mathematical Sciences.
• Wu X, Kumar V, Quinlan JR, Ghosh J, Yang Q, Motoda H, McLachlan GJ, Ng A, Liu B, Philip SY. 2008. Top 10 algorithms in data mining. Know Inf Sys, 14(1): 1-37.
• Xia Y, Xi B. 2007. Conceptual clustering categorical data with uncertainty. 19th IEEE International Conference on Tools with Artificial Intelligence ICTAI 2007.
• Xu D, Tian Y. 2015. A comprehensive survey of clustering algorithms. Annals Data Sci, 2(2): 165-193.
• Xu R, Wunsch DC. 2005. Survey of clustering algorithms.
• Zhang B, Hsu M, Dayal U. 2000. K-harmonic means-a spatial clustering algorithm with boosting. International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining.
• Zhang B, Hsu M, Dayal U. 1999. K-harmonic means-a data clustering algorithm. Hewlett-Packard Labs Technical Report HPL 1999-124, 1999, 55.
• Zhang T, Ramakrishnan R, Livny M. 1996. BIRCH: an efficient data clustering method for very large databases. ACM Sigmod Rec, 25(2): 103-114.
• Zhang X, Wang J, Wu F, Fan Z, Li X. 2006. A novel spatial clustering with obstacles constraints based on genetic algorithms and K-medoids. Sixth International Conference on Intelligent Systems Design and Applications.