Büyük boyutlu veriler için metasezgisel yöntemler ile öznitelik indirgemede yeni bir yaklaşım geliştirilmesi = Developing a new approach to feature selection with metaheuristic methods for large scale data

Abstract

Teknolojinin gelişmesi ve çevrimiçi dünyanın genişlemesi ile iş dünyası, bilim, sağlık ve mühendislik gibi bir çok alanda çok büyük boyut ve tür içeren gerçek dünya verileri ortaya çıkmıştır. Günümüz dünyasında bu verilerin en faydalı kullanımı ve en az saklama maliyeti hedeflendiğinden, ancak belirli anlam taşıyan verilerin saklanması gerekmektedir. Boyutları büyüyen ham verideki örüntüler bulunmadığı sürece veriler gereksizdir. Büyük boyutlu veriyi işlemek ise onları kullanan sistemlerin verimliliğini doğrudan etkileyen bir darboğaz problemidir. Büyük veri ve büyük boyutlu veri için nitelik azaltma olarak da adlandırılan öznitelik seçme problemi, orijinal özelliklerin ayırt edici gücünü koruyarak veri boyutunu indirgemeyi amaçlamaktadır. Öznitelik seçimi, öğrenme sürecinin önemli adımlarından biridir. En iyi çözümün büyük bir arama uzayında uygun sürede bulunmasını gerektirir. Öznitelik seçim problemi için tasarlanan algoritmalar, orijinal özelliklerin hesapsal maliyetini azaltırken en uygun özellik alt kümesini bulma amaçlı rastgele veya sezgisel arama stratejileri kullanır. Veri hacmi arttıkça veri ile yapılacak tüm işlemler de doğrusal olarak zorlaşmaktadır. Bu sebeple ortaya atılan öznitelik seçim probleminin çözümü için literatürde birden çok yöntem kullanılmıştır. Klasik sezgisel algoritmalar büyük boyutlu ve karmaşık problemlere uygulandığında tasarımındaki avantaj ve etkinliklerini kaybetmektedirler. Çünkü bu algoritmalar, yerel çözümlere takılma, kararsız performans sergileme, bellek verimliliğinden yoksun olma gibi kısıtlamalara sahip olabilirler (Qiu & Liu, 2016). Bu nedenle bu tip problemlerin çözümü için daha etkili algoritmalara ihtiyaç duyulmaktadır. Öznitelik seçim probleminin çözümü için etkili yaklaşımlardan biri de Metasezgisel algoritmalardır. Doğadan esinlemeli algoritmalar çözüm uzayında, sezgisel bir arama yaparak daha makul sürelerde daha uygun sonuçların elde edilmesini sağlar. Bu kapsamda, ana veri kümesinin küçük ama etkili bir alt kümesi olarak tespit edilecek olan niteliklerin belirlenmesi için algoritmanın küresel arama yeteneğini ve sezgiselliğini kaybetmeden, bir yerel arama fonksiyonu ile desteklenmesinin başarıyı artıracağı düşünülmüştür (X.-M. Hu vd., 2017). Sezgisel algoritmalar evrimsel algoritmalar ve sürü temelli algoritmalar temel iki grup olarak nitelendirilir. Evrimsel algoritmalar ile gerçek dünya problemlerine başarılı sonuçlar üretilebilmektedir. Bu algoritmalara Genetik Algoritma, Evrimsel Strateji ve Diferansiyel Evrim algoritması en bilinen örneklerdendir. Doğada var olan çeşitli canlıların davranışlarını taklit ederek geliştirilen sürü temelli algoritmalar ise gün geçtikçe popülerliği artan algoritmalardır. Bu algoritmalara Parçacık Sürü Optimizasyon Algoritması, Yarasa Algoritması, Karınca Kolonisi Optimizsyon Algoritması, Yapay Arı Kolonisi Algoritması örnek verilebilir. At Sürüsü Algoritması (HOA) ise, en yeni sürü tabanlı optimizasyon algoritmalarından biridir. HOA, doğada birlikte yaşayan atların sürü olarak davranışlarından ilham alarak tasarlanmıştır. Atların farklı yaşlarda gösterdikleri otlama, hiyerarşi, sosyallik, taklit, savunma ve dolaşma olmak üzere altı kategorideki sosyal davranışları algoritmanın temelini oluşturmaktadır. Literatürde optimizasyon algoritmalarının ikili arama uzayına taşınarak sıkça öznitelik seçim problemine uygulandığı gözlenmektedir. Bu tez kapsamında öznitelik seçimi için HOA'nın ikili bir versiyonu iyi bilinen iki farklı sınıflandırma algoritması (k-NN ve SVM) ile önerilmiştir. HOA'nın nitelik seçimi için önerilen ikili versiyonu öncelikle küçük boyutlu (10,20,30) veriler ile test edilmiştir. Ardından büyük boyutlu verilerde de efektif sonuçlar üretmesi amacıyla yerel arama tekniği olan Minimum Mesafe Fonksiyonu ve Sürü Merkezi Bulma Fonksiyonu geliştirilerek İkili At Sürüsü Algoritması (BHOAFS) önerilmiştir. BHOAFS'nin eklenen yöntemler ile yerel ve küresel arama yeteneği artmıştır. BHOAFS'nin düşük, orta ve yüksek boyutlu (10,20,30,100,500 ve 1000) problemlerde başarısı test edilmiştir. BHOAFS-k-NN algoritmasının BHOAFS-SVM'ye göre daha iyi sonuçlar ürettiği gözlemlenmiştir. Literatürde metasezgisel optimizasyon algoritmaların keşif ve sömürü sürecindeki dengeyi sağlayarak süreci güçlendirmek için kaos teorisi, levy uçuşu, zeki arama, kuantum davranışı gibi çeşitli stratejiler kullanılmıştır. Bu tez çalışmasında HOA'nın önerilen ikili versiyonu algoritmanın başarısı ve kararlılığını arttırmak amacıyla iyi bilinen beş farklı kaotik harita ile güçlendirilerek Kaotik İkili At Sürüsü Algoritması BCHOAFS olarak adlandırılan yeni bir yaklaşım geliştirilmiştir. Önerilen BCHOAFS, büyük ölçekli veriler için özel olarak tasarlanmış bir optimizasyon algoritması olan HOA'nın özellik seçim problemleri için özel olarak geliştirilmiş ilk ikili kaotik tabanlı algoritmadır. k-NN sınıflandırmasını kullanan BHOAFS-k-NN yöntemi daha iyi sonuçlar ürettiğinden, beş kaotik harita ile birleştirilmiş ve BCHOAFS-Logistic, BCHOAFS-Tent, BCHOAFS-Piecewise, BCHOAFS-Singer, BCHOAFS-Sinusoidal olarak adlandırılmıştır. Geliştirilen bu yaklaşımın performansı farklı boyuttaki on sekiz veri seti ile ölçülmüştür. Kaotik tabanlı yeni yaklaşım literatürde öznitelik seçimi için geliştirilen çeşitli algoritmalar ile kıyaslanmış, doğruluk, seçilen öznitelik sayısı, uygunluk fonksiyonu testleri yapılarak güvenilirliği sağlanmıştır. Önerilen yaklaşımın kıyaslanan algoritmalardan daha performanslı olduğu istatistiksel yöntemlerden Friedman işaret testi ve post hoc Wilcoxon testi kullanılarak doğrulanmıştır.

With the development of technology and the expansion of the online world, real-world data of enormous size and type has emerged in many fields such as business, science, health and engineering. In today's world, since the most beneficial use of this data and the least storage cost is aimed, only data that has a certain meaning should be stored. Data is useless unless there are patterns in the growing raw data. Processing largescale data is a bottleneck problem that directly affects the efficiency of the systems that use them. Feature selection problem, also called feature reduction for big data and large size data, aims to reduce the data size while preserving the distinctive power of the original features. Feature selection is one of the important steps of the learning process. It requires the best solution to be found in a large search space in a reasonable amount of time. Algorithms designed for the feature selection problem use random or heuristic search strategies to find the optimal subset of features while reducing the computational cost of the original features. As the volume of data increases, all operations with the data become linearly difficult. For this reason, more than one method has been used in the literature to solve the proposed feature selection problem. When classical heuristic algorithms are applied to large and complex problems, they lose their advantages and effectiveness in design. Because these algorithms may have limitations such as being stuck in native solutions, unstable performance, and lack of memory efficiency. Therefore, more effective algorithms are needed to solve such problems. Metaheuristic algorithms are one of the effective approaches for solving the feature selection problem. Nature-inspired algorithms perform an intuitive search in the solution space, resulting in more appropriate results in more reasonable time. In this context, it is thought that supporting the algorithm with a local search function without losing its global search capability and heuristics in order to determine the features that will be detected as a small but effective subset of the main dataset will increase the success. Heuristic algorithms, evolutionary algorithms and swarm-based algorithms are characterized as the two main groups. Successful results can be produced for real world problems with evolutionary algorithms. Among these algorithms, Genetic Algorithm, Evolutionary Strategy and Differential Evolution algorithm are the best-known examples. Swarm-based algorithms, which are developed by imitating the behavior of various living things in nature, are the algorithms that are increasing in popularity day by day. Particle Swarm Optimization Algorithm, Bat Algorithm, Ant Colony Optimization Algorithm, Artificial Bee Colony Algorithm can be given as examples to these algorithms. Horse Herd Algorithm (HOA) is one of the newest herd-based optimization algorithms. HOA is a new metaheuristic algorithm created by modeling the herd behavior of horses and was designed with inspiration from the herd behavior of horses living together in nature developed for large scale optimization problems. The social behaviors of horses in six categories: grazing, hierarchy, sociability, imitation, defense and wandering at different ages form the basis of the algorithm. In the literature, it is observed that optimization algorithms are frequently applied to the feature selection problem by moving to binary search space. One of the most challenging and common problems in machine learning is the Feature Selection (FS) process, which reduces the dataset size by finding optimal subsets of features. This thesis proposes the binary version of HOA, which mimics the life cycles and searching behaviors of horses, has been applied to a wrapper-based FS problem using classification algorithms (BHOAFS-kNN and BHOAFS-SVM). A binary version of HOA is proposed for feature selection with two well-known classification algorithms (k-NN and SVM). In this thesis, a binary version of HOA is proposed for feature selection with two wellknown classification algorithms (k-NN and SVM). The proposed binary version of the HOA for feature selection was first tested with small data. Then, in order to produce effective results in large-scale data, the Minimum Distance Function and Herd Center Finding Function, which are local search techniques, were developed and Binary Horse Herd Algorithm (BHOAFS) was proposed. Local and global search capability of BHOAFS has increased with the added methods. The success of BHOAFS has been tested in low, medium and high dimensional (e.g.,10, 20, 30, 100, 500 and 1000) problems. It has been observed that the BHOAFS-k-NN algorithm produces better results than BHOAFS-SVM. In the literature, various strategies such as chaos theory, levy flight, intelligent search, and quantum behavior have been used to strengthen the process by providing the balance in the discovery and exploitation process of metaheuristic optimization algorithms. This paper proposes the binary version of the HOA as a wrapper FS method to solve the FS problem. The proposed algorithm is a binary chaotic horse herd optimization algorithm for feature selection (BCHOAFS). This thesis proposes the binary version of HOA, which mimics the life cycles and searching behaviors of horses, has been applied to a wrapper-based FS problem using classification algorithms (BHOAFS-kNN and BHOAFS-SVM). In this thesis, a new approach called Binary Chaotic Horse Herd Algorithm BCHOAFS has been developed by strengthening the proposed binary version of HOA with five different well-known chaotic maps in order to increase the success and stability of the algorithm. The proposed BCHOAFS is the first binary chaotic based algorithm specially developed for feature selection problems of HOA, an optimization algorithm specially designed for large-scale data. Since the BHOAFS-k-NN method using k-NN classification produced better results, it was combined with five chaotic maps and named as BHOAFS-Logistics (BCHOAFS1), BCHOAFS - Tent (BCHOAFS2), BCHOAFS - Piecewise (BCHOAFS3), BCHOAFS - Singer (BCHOAFS4), and BCHOAFS - Sinusoidal (BCHOAFS5). The Age Determination process used in the proposed algorithm allows the horses to do a global search in the search space. The SMF operator, which is proposed as a local search technique, has been developed to overcome the disadvantages, such as early convergence while preserving population diversity. A comprehensive study was conducted using 18 standard datasets from theUCI repository of varying sizes and characters to evaluate the effectiveness of the proposed BHOAFS and BCHOAFS versions. The chaotic-based new approach has been compared with various popular algorithms developed for feature selection in the literature, and its reliability has been ensured by performing tests in terms of accuracy, number of selected features, fitness function and runtime. It has been verified by using Friedman Signed Rank and post hoc Wilcoxon test from statistical methods that the proposed approach is more performant than the compared algorithms. The performance of the proposed methods was compared with various methods such as well-known optimization algorithms in the literature such as GA, PSO, ALO, GWO, SSA, and binary optimization algorithms such as BGA, BPSO, BALO, BGWO, and BSSA. When the FS problem is considered a multi-objective problem, the classification accuracy should be at the highest level, and the number of selected features should be at the lowest level. When the results were examined, the best performance among the recommended algorithms was found to belong to BCHOAFS3 and BCHOAFS4 algorithms (BCHOAFS-Piecewise and BCHOAFS-Singer) in terms of classification accuracy and FS. In general, applying chaotic maps to optimization algorithms is easy and practical. According to this study, chaotic maps can improve results when applied to previously proposed algorithms. The main reason for this improvement is that the algorithm can more accurately since the initial conditions are designed in advance. Thus, bitchanging operations during the iteration will result in more specific exploitation and exploratiand a balance will be stablished between the algorithm's local and global search operations. Taking full advantage of this situation, our proposed algorithm proves that chaotic maps are one of the best enhancement options for currently proposed algorithms when the results obtained are examined. Based on the promising results of BCHOAFS, there is enough evidence to compare its performance with similar methods.Finally, the results show that the proposed BCHOAFS achieves high competitive results and can be expressed as a multi-objective optimization problem. The most important result of this study is that BCHOAFS versions are useful selection algorithms. When the SMF operator designed as a local search strategy and chaotic maps are combined, the results prove the novelty of the proposed algorithm. In the proposed method in future studies, the movement of the horse herd directed towards the center of the search space with the SMF function can be improved with a different solution in terms of exploration capability by calculating the movement sensitivity. HOA can be combined with other algorithms to improve the multi-purpose version. Customized solutions for the position of each horse in the search space can be developed by supporting various statistical methods. The U-shaped transfer function used in the transition from continuous space to discrete space can be tested by replacing it with other transfer functions. The classifiers used for feature selection performance measurement can be replaced with other classification algorithms and their accuracy can be compared.