Metaheuristic Search Algorithms in Solving the n-Similarity Problem

• Autorzy: Mirhosseini M. , Nezamabadi-pour H.

Identyfikatory

DOI

10.3233/FI-2017-1516

• Języki publikacji: EN

Abstrakty

EN

The - similarity problem, finding a group of objects which have the most similarity to each other, has become an important issue in information retrieval and data mining. The theory of this concept is mathematically proven, but it practically has high time complexity. Binary Genetic Algorithm (BGA) has been applied to improve solutions quality of this problem, but a more efficient algorithm is required. Therefore, we aim to study and compare the performance of four metaheuristic algorithms called Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA), Imperialist Competitive Algorithm (ICA) and Fuzzy Imperialist Competitive Algorithm (FICA) to tackle this problem. The experiments are conducted on two applications; the former is on four UCI datasets as a general application and the latter is on the text resemblance application to detect multiple similar text documents from Reuters datasets as a case study. The results of experiments give a ranking of the algorithms in solving the -similarity problem in both applications based on the exploration and exploitation abilities, that the FICA achieves the first rank in both applications as well as based on the both criteria.

Słowa kluczowe

EN

fuzzy imperialist competition algorithm; gravitational search algorithm; imperialist competition algorithm; n-similarity; particle swarm optimization (PSO); text document similarity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 2
• Strony: 145--166
• Opis fizyczny: Bibliogr. 35 poz., tab., wykr.

Twórcy

autor

Mirhosseini M.

• Department of Computer Science, Higher Education Complex of Bam, Bam, Iran

autor

Nezamabadi-pour H.

• Department of Electrical Engineering, Shahid Bahonar University of Kerman, Kerman, Iran

Bibliografia

• [1] Keshavarzi M, Dehghan MA, Mashinchi M. Applications of classification based on similarities and dissimilarities, Fuzzy Information and Engineering, 2012;4(1):75–92. doi:10.1007/s12543-012-0102-4.
• [2] Keshavarzi M, Dehghan MA, Mashinchi M. Classification based on 3-similarity, Iranian Journal of Mathematical Sciences and Informatics, 2011;6(1):7–21. doi:10.7508/ijmsi.2011.01.002.
• [3] Keshavarzi M. Classification based on similarity and dissimilarity, PhD thesis, Shahid Bahonar University of Kerman, Iran, 2010.
• [4] Kaufman L, Rousseeuw PJ. Finding Group in Data, Wiley, New York, 1990. doi:10.2307/2532178.
• [5] Theodoridis S, Koutroumbas K. Pattern Recognition, Academic Press, 2008. ISBN:1597492728, 9781597492720.
• [6] Sun H, Peng Y, Chen J, Liu Ch, Sun Y. A new similarity measure based on adjusted Euclidean distance for memory-based collaborative filtering, Journal of Software, 2011;6(6):993–1000. doi:10.4304/jsw.6.6.993-1000.
• [7] Zadeh LA. Fuzzy sets, Information and Control, 1965;8(3):338–353. URL http://dx.doi.org/10.1016/S0019-9958(65)90241-X.
• [8] Hyung LK, Song YS, Lee KM. Similarity measure between fuzzy sets and elements, Fuzzy Sets and Systems, 1994;62(3):291–293. doi:10.1016/0165-0114(94)90113-9.
• [9] Wang WJ. New similarity measure on fuzzy sets and their applications, Mathematical and Computer Modeling, 2011;53(1-2):91–97.
• [10] Chen SM, Yeh MSh, Hsiao PY. A comparison of similarity measures of fuzzy values, Fuzzy Sets and Systems, 1995;72(1):79–89. doi:10.1016/0165-0114(94)00284-E.
• [11] Rezaei H, Emoto M, Mukaidono M. New similarity measure between two fuzzy sets, Journal of Advanced Computational Intelligence and Intelligent Informatics, 2006;10(6):946-953. doi:10.20965/jaciii.2006.p0946.
• [12] Ye J. Cosine similarity measures for intuitionistic fuzzy sets and their applications, Mathematical and Computer Modeling, 2011;53:91–97. URL http://dx.doi.org/10.1016/j.mcm.2010.07.022.
• [13] Huang A. Similarity measures for text document clustering. 6th New Zealand Computer Science Research Student Conference, Christchurch, 14-18 April 2008, pp. 49-56.
• [14] Patidar AK, Agrawal J, Mishra N. Analysis of different similarity measure functions and their impacts on shared nearest neighbor clustering approach, International Journal of Computer Applications, 2012;40(16):1–5. doi:10.5120/5061-7221.
• [15] Sarac R, Tu K, Allahverdi N. A fuzzy clustering approach for finding similar documents using a novel similarity measure, Expert systems with applications, 2007;33(3):600–605. URL http://dx.doi.org/10.1016/j.eswa.2006.06.002.
• [16] Phridviraja MSB, Vangipuram RadhaKrishnab, Chintakindi Srinivasa, GuruRao CV. A novel Gaussian based similarity measure for clustering customer transactions using transaction sequence vector, Procedia Technology, 2015;19:880–887. URL http://dx.doi.org/10.1016/j.protcy.2015.02.126.
• [17] Phridviraj MSB, Vangipuram Radhakrishna, Vinay Kumar K, GuruRao CV. A novel similarity measure for clustering customer transactions using ternary sequence vector, Artificial Intelligence Perspectives and Applications, 2015;347:297–308. doi:10.1007/978-3-319-18476-0_30.
• [18] Mirhoseini M, Mashinchi M, Nezamabadi-pour H. Improving n-Similarity problem by genetic algorithm and its application in text document resemblance, Fuzzy Information and Engineering, 2014;6(3):263–278. URL http://dx.doi.org/10.1016/j.fiae.2014.12.001.
• [19] Caserta M, Voss S. Metaheuristics: Intelligent Problem Solving, Matheuristics Annals of Information Systems Vol. 10, pp. 1–38, 2010, doi:10.1007/978-1-4419-1306-7_1.
• [20] Kennedy J, Eberhart R. Particle Swarm Optimization, Proceedings of IEEE International Conference on Neural Networks., Vol. 4, pp. 1942–1948, 1995. doi:10.1109/ICNN.1995.488968.
• [21] Jordehi AR. Particle swarm optimisation for dynamic optimisation problems: a review, Neural Computing and Applications, 2014;25(7-8):1507–1516. doi:10.1007/s00521-014-1661-6.
• [22] Clerc M. Particle Swarm Optimization, John Wiley & Sons, 2010.
• [23] Rashedi E, Nezamabadi-pour H, Saryazdi S. GSA: A Gravitational Search Algorithm, Information Sciences, 2009;179(13):2232–2248. URL http://dx.doi.org/10.1016/j.ins.2009.03.004.
• [24] Ayyildiz M, Cetinkaya K. Comparison of four different heuristic optimization algorithms for the inverse kinematics solution of a real 4-DOF serial robot manipulator, Neural Computing and Applications, 2015;27(4):825–836. doi:10.1007/s00521-015-1898-8.
• [25] Atashpaz-Gargari E, Lucas C. Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialistic competition, IEEE Congress on Evolutionary Computation, pp. 4661–4667, 2009.
• [26] Khaled AA, Hosseini S. Fuzzy adaptive imperialist competitive algorithm for global optimization, Neural Computing and Applications, 2015;26(4):813-825. doi:10.1007/s00521-014-1752-4.
• [27] Arish S, Amiri A, and Noori K. FICA: fuzzy imperialist competitive algorithm, journal of Zhejiang university-SCIENCE C, 2014;15(5):363–371. doi:10.1631/jzus.C1300088.
• [28] UCI Machine Learning Repository. Center for Machine Learning and Intelligent Systems, URL http://archieve.ics.uci.edu/ml/datasets.html.
• [29] Hastie T, Tibshirani R, Friedman J. The elements of statistical learning: Data mining, inference, and prediction. Springer, 2001.
• [30] Gomaa WH, Fahmy AA. A survey of text similarity approaches, International Journal of Computer Applications, 2013;68(13):13–18. doi:10.5120/11638-7118.
• [31] Lewis DD. Reuters-21578 text categorization test collection distribution 1.0, 1999. URL http://www.Research.att.com/lewis/reuters21578.html.
• [32] http://jmlr.csail.mit.edu/papers/volume5/lewis04a/a11-smart-stoplist/english.stop.
• [33] Porter MF. An algorithm for suffix stripping, Program, 1980;14(3):130–137. URL http://dx.doi.org/10.1108/eb046814.
• [34] Berry M, Browne M. Lecture Notes in Data Mining, World Scientific Publishing of Hackensack, New Jersey, 2006.
• [35] Qimin C, Qiao G, Yongliang W, Xianghu W. Text clustering using VSM with feature clusters, Neural Computing and Applications, 2015;26(4):995–1003. doi:10.1007/s00521-014-1792-9.