3-KCP ÇÖZÜM BULMAK İÇİN DENETİMSİZ ÖĞRENME ALGORİTMASI: MODÜLERLİK, KLİK SÜZME, SPEKTRAL, MERKEZİYET VE HİYERARŞİK KÜMELEME

Year 2021, Volume: 8 Issue: 14, 169 - 178, 30.06.2021

Serkan Güldal

Abstract

Denetimsiz öğrenme algoritmaları, bilgiyi minimum insan etkileşimi ile çıkardıkları için birçok mühendislik uygulamasında kullanılırlar. Modülerlik verileri sınıflandırmak için iyi bilinen denetimsiz öğrenme algoritmalarından biridir, böylece ilişkisel bilgiler vurgulanır. Yakın ilişkili veri noktaları, nispeten yoğun alt topluluklar oluşturmak için bir araya gelir. Böylece, veri noktaları (yada düğümler) arasındaki anlamlı ilişkiler, veri noktalarının ortak özelliklerine genişletilebilir. Bu çalışmada, modülerlik sınıflandırması ile doğası gereği kombinatorik bir problem olan 3-KCP'yi çözmeyi amaçlıyoruz. Bununla birlikte sonuçlarımızı iyi bilinen kümeleme algoritmaları Klik Süzme, Spektral, Merkeziyet ve Hiyerarşik kümeleme ile karşılaştırdık. Araştırmamız, 0.1'den 2.1'e genişletilmiş çözünürlükleri içerir ve 1.0, tüm 3-KCP çözümlerini bulmak için en uygun çözünürlük olduğunu gösteriyor. Modülerliğin belirtilen kümeleme algoritmalarıyla karşılaştırılmamız modülerlik algoritmasının diğer metotlara göre daha avantajlı olduğu gösterdi çünkü karşılaştırılan algoritma, N-KCP anlamında yanlış kümeler veya modülerlikle tanımlanan kümeler olarak sonuçlandı.

Keywords

At Çizelgesi, Modülerlik, Denetimsiz öğrenme, 3-KCP

UNSUPERVISED MACHINE LEARNING ALGORITHMS TO FIND 3-KCP SOLUTION: MODULARITY, CLIQUE PERCOLATION, SPECTRAL, CENTRALITY, AND HIERARCHICAL CLUSTERING

Abstract

Unsupervised learning algorithms are used in many engineering applications since they extract information by the minimum human interaction. Modularity is one of the well known unsupervised machine learning algorithms to classify the network of information, so the relational information is highlighted. The closely related data points gather together to create relatively dense subcommunities. Thus, the meaningful relationships between data points (a.k.a. nodes or vertices) could be extended to the common properties of the data points. In this study, we aim to solve 3-KCP which is inherently a combinatorics problem by the modularity classification. Additionally, we compared the result with the well-known clustering algorithms, namely Clique Percolation, Spectral, Centrality, and Hierarchical clustering. Our investigation by means of modularity includes extended resolutions from 0.1 to 2.1, and 1.0 is the optimum resolution to find all 3-KCP solutions for the Modularity algorithm. Comparison of the modularity with the specified clustering algorithms shows the superiority of the modularity algorithm because compared algorithm provides wrong clusters by means of N-KCP or identified clusters by modularity.

Keywords

Knight Graph, Modularity, Unsupervised Learning, 3-KCP

References

• V. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. J. J. o. s. m. t. Lefebvre, and experiment, "Fast unfolding of communities in large networks," vol. 2008, no. 10, p. P10008, 2008.
• Y. Tian and M. Compere, "A Case Study on Visual-Inertial Odometry using Supervised, Semi-Supervised and Unsupervised Learning Methods," in 2019 IEEE International Conference on Artificial Intelligence and Virtual Reality (AIVR), 9-11 Dec. 2019 2019, pp. 203-2034, doi: 10.1109/AIVR46125.2019.00043.
• H. Yan, P. Yu, and D. Long, "Study on Deep Unsupervised Learning Optimization Algorithm Based on Cloud Computing," in 2019 International Conference on Intelligent Transportation, Big Data & Smart City (ICITBS), 12-13 Jan. 2019 2019, pp. 679-681, doi: 10.1109/ICITBS.2019.00168.
• M. S. Bartlett, J. R. Movellan, and T. J. Sejnowski, "Face recognition by independent component analysis," IEEE Transactions on Neural Networks, vol. 13, no. 6, pp. 1450-1464, 2002, doi: 10.1109/TNN.2002.804287.
• M. A. Kabir and X. Luo, "Unsupervised Learning for Network Flow Based Anomaly Detection in the Era of Deep Learning," in 2020 IEEE Sixth International Conference on Big Data Computing Service and Applications (BigDataService), 3-6 Aug. 2020 2020, pp. 165-168, doi: 10.1109/BigDataService49289.2020.00032.
• Q. Li, J. Zhao, and X. Zhu, "An Unsupervised Learning Algorithm for Intelligent Image Analysis," in 2006 9th International Conference on Control, Automation, Robotics and Vision, 5-8 Dec. 2006 2006, pp. 1-5, doi: 10.1109/ICARCV.2006.345232.
• Y. Wang and Y. Xu, "Unsupervised Learning of Accurate Camera Pose and Depth From Video Sequences With Kalman Filter," IEEE Access, vol. 7, pp. 32796-32804, 2019, doi: 10.1109/ACCESS.2019.2903871.
• Y. He, N. Sang, C. Gao, and J. Han, "Online Unsupervised Learning Classification of Pedestrian and Vehicle for Video Surveillance," Chinese Journal of Electronics, vol. 26, no. 1, pp. 145-151, 2017, doi: 10.1049/cje.2016.08.011.
• C. Teng and Y. Chen, "Syndrome-Enabled Unsupervised Learning for Neural Network-Based Polar Decoder and Jointly Optimized Blind Equalizer," IEEE Journal on Emerging and Selected Topics in Circuits and Systems, vol. 10, no. 2, pp. 177-188, 2020, doi: 10.1109/JETCAS.2020.2992593.
• T. C. Clancy, A. Khawar, and T. R. Newman, "Robust Signal Classification Using Unsupervised Learning," IEEE Transactions on Wireless Communications, vol. 10, no. 4, pp. 1289-1299, 2011, doi: 10.1109/TWC.2011.030311.101137.
• D. Ying, Y. Yan, J. Dang, and F. K. Soong, "Voice Activity Detection Based on an Unsupervised Learning Framework," IEEE Transactions on Audio, Speech, and Language Processing, vol. 19, no. 8, pp. 2624-2633, 2011, doi: 10.1109/TASL.2011.2125953.
• Y. Chang, X. Yuan, B. Li, D. Niyato, and N. Al-Dhahir, "A Joint Unsupervised Learning and Genetic Algorithm Approach for Topology Control in Energy-Efficient Ultra-Dense Wireless Sensor Networks," IEEE Communications Letters, vol. 22, no. 11, pp. 2370-2373, 2018, doi: 10.1109/LCOMM.2018.2870886.
• A. Philip, "A Generalized Pseudo-Knight?s Tour Algorithm for Encryption of an Image," IEEE Potentials, vol. 32, no. 6, pp. 10-16, 2013, doi: 10.1109/MPOT.2012.2219651.
• J. Kumar and S. Nirmala, "Securing the contents of document images using knight moves and genetic approach," in 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 10-13 Aug. 2015 2015, pp. 1091-1095, doi: 10.1109/ICACCI.2015.7275755.
• J. Delei, B. Sen, and D. Wenming, "An Image Encryption Algorithm Based on Knight's Tour and Slip Encryption-Filter," in 2008 International Conference on Computer Science and Software Engineering, 12-14 Dec. 2008 2008, vol. 1, pp. 251-255, doi: 10.1109/CSSE.2008.1142.
• S. Bai, G. Zhu, and J. Huang, "An Intelligent Algorithm for the (1,2,2)-Generalized Knight's Tour Problem," in 2013 Ninth International Conference on Computational Intelligence and Security, 14-15 Dec. 2013 2013, pp. 583-588, doi: 10.1109/CIS.2013.129.
• H. Jian and B. Sen, "An Efficient Algorithm for the Generalized (1,k)-Knight's Tours Problem," in 2009 First International Workshop on Education Technology and Computer Science, 7-8 March 2009 2009, vol. 1, pp. 697-701, doi: 10.1109/ETCS.2009.161.
• S. Bai, X. Liao, X. Qu, and Y. Liu, "Generalized Knight's Tour Problem and Its Solutions Algorithm," in 2006 International Conference on Computational Intelligence and Security, 3-6 Nov. 2006 2006, vol. 1, pp. 570-573, doi: 10.1109/ICCIAS.2006.294200.
• D. C. Fisher, "On the n x n Knight Cover Problem," Ars Comb., vol. 69, / 2003.
• F. Rubin, "Improved Knight Coverings," Ars Combinatoria, vol. 69, / 2003.
• F. Rubin, "Knight Covers for the 50x50 Chessboard," presented at the Mathfest 2004, Providence RI, 2004.
• F. Rubin, "A Family of Efficient Knight Covering Patterns," Journal of Recreational Mathematics, Article vol. 33, no. 3, pp. 165-175, 2005. [Online]. Available: http://search.ebscohost.com/login.aspx?direct=true&db=aph&AN=26073841&site=ehost-live.
• F. Rubin, "An Improved Method for Finding Knight Covers," Ars Combinatoria, vol. 82, / 2007.
• B. Lemaire, "Knights Covers on NxN Chessboards," J. Recr. Math., vol. 31, pp. 87-99, 2003.
• A. H. Jackson and R. P. Pargas, "Solutions to the NxN Knights Covering Problem," Journal of Recreational Mathematics vol. 23, pp. 255-267, 1991.
• F. Wei, "Research on Knight Covering Based on Breadth First Search Algorithm," (in English), Applied Mechanic and Materials, vol. 686, pp. 377-380, 2014.
• S. Güldal, M. Lipscomb, and M. M. Tanik, "Solving Knights Covering Problem: Backtracking, Permutation, Bipartite Graph, and Independent Set," presented at the Nineteenth Annual Early Career Technical Conference, Birmingham, Alabama USA, 2019.
• S. Güldal, M. M. Tanik, and M. M. Lipscomb, "Solving Knights Covering Problem by a Hybrid Algorithm," presented at the IEEE SouthEastConn, Huntsville, Alabama, April 11 - 14 2019, 2019.
• S. Güldal, "Connectives of Knights Covering Problem By Girvan-Newman Clustering," presented at the SDPS 2019 Workshop, Madrid, Spain, November 25-26 2019, 2019.
• U. Brandes et al., "On Modularity Clustering," IEEE Transactions on Knowledge and Data Engineering, vol. 20, no. 2, pp. 172-188, 2008, doi: 10.1109/TKDE.2007.190689.
• R. Rotta and A. Noack, "Multilevel local search algorithms for modularity clustering," vol. 16, p. Article 2.3, 2011, doi: 10.1145/1963190.1970376 %J J. Exp. Algorithmics.
• M. Bastian, S. Heymann, and M. Jacomy, "Gephi: an open source software for exploring and manipulating networks," in International AAAI Conference on Weblogs and Social Media, 2009.
• R. Lambiotte, J.-C. Delvenne, and M. J. a. p. a. Barahona, "Laplacian dynamics and multiscale modular structure in networks," 2008.