Improved Symbiotic Organism Search Algorithm for Biomedical Data Clustering

Improved Symbiotic Organism Search Algorithm for Biomedical Data Clustering Saida Ishak Boushaki1, Nabila Rahmoune2, Omar Bendjeghaba3, and Sadjia Lahiani3 1LIMOSE Laboratory, University Mhamed Bougara, Boumerdes, Algeria, [email protected] 2LIMOSE Laboratory, University Mhamed Bougara, Boumerdes, Algeria, [email protected] 3(LREEI), University M’Hamed Bougara Boumerdes, 35000, Algeria, [email protected] 4Biological Resources Valorization and Conservation Laboratory “VALCORE”, Universit´e M’Hamed Bougara Boumerd`es, Avenue de l’ind´ependance, 35000, Boumerdes, Algeria, [email protected] Abstract Biomedical datasets have grown exponentially with advancements in digital data acquisition and storage technologies. This explosion of data has heightened the need for effective methods to uncover actionable insights, a task central to the field of data mining. Among data mining techniques, clustering holds particular importance for its ability to group data into meaningful subsets, revealing underlying patterns and critical features. In this paper, we present an improved version of the Symbiotic Organisms Search (SOS) algorithm, augmented with a novel Fitness-Distance Balance (FDB) selection method. This enhanced algorithm is specifically adapted for the clustering of biomedical data. The SOS algorithm, inspired by natural symbiotic interactions, excels at exploring solution spaces to locate global optima. With the addition of the FDB method, the algorithm achieves superior efficiency and performance, overcoming challenges inherent in traditional clustering methods. Keywords: Clustering, Symbiotic Organism Search Algorithm, Fitness-Distance Balance (FDB) selection, I index, Biomedical data, Datamining, Metaheuristic. 1 Introduction The rapid advancements in digital technologies have led to an unprecedented growth of large-scale datasets, particularly in the biomedical field. Extracting actionable insights from these datasets is a core objective of data mining, a discipline that involves analyzing data to uncover hidden relationships and summarize information in innovative and practical ways. Clustering plays a pivotal role in data mining, functioning as an exploratory analysis technique that organizes data into meaningful groups or clusters [7]. These clusters reveal intrinsic data patterns, enabling better understanding and characterization of datasets. Biomedical research, in particular, has benefitted from clustering algorithms, which are extensively used to analyze gene expression data. Such analyses help identify groups of genes exhibiting similar behavior, contributing to insights into complex biological processes and facilitating the development of personalized medical treatments [1] . Clustering techniques can be broadly categorized into hierarchical and partition-based approaches. Hierarchical clustering builds a tree-like structure (dendrogram) of clusters, providing multilevel exploration and rich visualizations [1]. Despite its descriptive power, it suffers from high computational complexity, which scales quadratically in the best-case scenario. Partitionbased clustering, exemplified by the popular K-means algorithm, offers greater computational efficiency due to its linear complexity. However, K-means often struggles with random initialization, which can result in suboptimal solutions [5]. Metaheuristics, inspired by natural phenomena, have gained prominence for their ability to solve complex optimization problems like clustering [8], [2]. Among these, the Symbiotic Organisms Search (SOS) algorithm, introduced by Cheng and Prayogo [3], has shown great promise. The SOS algorithm models symbiotic interactions in nature, enabling efficient exploration of solution spaces without requiring complex parameter tuning. This study proposes an improved SOS algorithm for clustering biomedical data, integrating a FitnessDistance Balance (FDB) selection method [4]. The enhanced algorithm leverages the strengths of SOS while addressing its limitations to achieve superior clustering outcomes. The FDB method enhances the search process by balancing solution quality and diversity, leading to improved convergence and clustering accuracy. 209 The paper is organized as follows. Section 2 introduces the theoretical underpinnings of the proposed approach, including a detailed overview of the SOS algorithm and its optimization mechanisms. Section 3 presents the improved algorithm, providing an in-depth explanation of its core components and workflow. Section 4 discusses the results of numerical experiments, highlighting the algorithm’s effectiveness through a comparative analysis with existing techniques. Section 5 concludes the study by summarizing key findings and offering recommendations for future research directions. . 2 THE SYMBIOTIC ORGANISMS SEARCH (SOS) ALGORITHM The Symbiotic Organisms Search (SOS) algorithm is a population-based metaheuristic inspired by the symbiotic relationships found in nature, such as mutualism, commensalism, and parasitism. SOS mimics how organisms interact to improve their chances of survival and adapt to their environment. Like traditional metaheuristics, the initial population in the SOS algorithm is generated randomly, with each organism representing a potential solution to the problem at hand. During each iteration, the algorithm simulates three primary types of symbiotic relationships: mutualism, commensalism, and parasitism, to explore and optimize the solution space effectively. •Mutualism Phase In the mutualism phase, a new solution is derived for Oi (representing the i-th organism in the ecosystem) and Oj (randomly selected from the population) by simulating mutualistic symbiosis. This interaction models the mutual benefit between Oi and Oj, resulting in an updated solution calculated as follows: Oinew =Oi+rand(0,1) ×(Obest −mutuel vec ×bef1) (1) Ojnew =Oj+rand(0,1) ×(Obest −mutuel vec ×bef2) (2) Here, rand(0,1) represents a vector of random numbers uniformly distributed within the range [0,1]. The benefit factors bef1 and bef2 are integers randomly assigned as either 1 or 2, indicating the level of benefit received by each organism. The interaction between organisms Oi and Oj is represented by a mutual vector, defined as: Oinew =Oi+rand(−1,1) ×(Obest −Oj) (3) The mutual vector represents the highest degree of adaptation, serving as the target point for improving the fitness of both organisms. Accordingly, the organisms are updated only if their newly computed fitness exceeds their fitness levels prior to the interaction. •Commensalism Phase Similar to the mutualism phase, a new candidate solution for Oi is generated based on the commensal symbiosis between organism Oi and another randomly selected organism from the ecosystem. This interaction is modeled using Equation (4). In line with the rules, Oi is updated only if the newly calculated fitness improves upon its fitness prior to the interaction. Oinew =Oi+rand(−1,1) ×(Obest −Oj) (4) •Parasitism Phase In the parasitism phase, a parasite vector is created by modifying randomly selected dimensions of the organism Oi. Another organism, Oj, is randomly chosen from the ecosystem to act as the host for the parasite vector. The parasite vector competes to replace Oj in the ecosystem by attempting to achieve a better fitness value. If the parasite vector’s fitness surpasses that of Oj , it ”kills” Oj and takes its place in the ecosystem. Conversely, if the parasite vector’s fitness is inferior, it cannot survive and is discarded. The SOS algorithm employs a population of candidate solutions to systematically explore promising regions of the search space for the optimal global solution. Each iteration involves organisms interacting randomly through the three symbiotic phases: mutualism, commensalism, and parasitism. This iterative process continues until the specified termination criteria are satisfied. 210 3 The proposed algorithm In the SOS clustering algorithm, each solution is considered as an organism, represented by a matrix with k rows and l columns. Each row of the matrix corresponds to the centroid of a cluster, and l denotes the dimensionality of the concept space. The primary objective of the SOS algorithm is to identify k optimal cluster centroids that minimize (or maximize) a given objective function. In this study, in order to produce compact clusters, the fitness function, that calculates The I index, proposed by Maulik and Bandyopadhyay [6], is used. It is given by the following formula: I(K) = 1 K·E1 EK ·DKP (5) Where K is the number of clusters. Here, EK= K X k=1 n X j=1 ukj ∥xj−zk∥(6) And DK=K max i,j=1 ∥zi−zj∥(7) Such that nis the number of data points in the dataset, U(X) = [ukj]K×nis a partition matrix of the data, and zkis the centroid of the k-th cluster. Given the selected fitness function, the clustering task is formulated as a typical maximization problem. To address the issue of premature convergence in the SOS clustering algorithm, the Fitness-Distance Balance (FDB) selection method is employed. This method calculates a selection score for each candidate by considering both its fitness value and its distance from the best solution in the population. The FDB approach provides two key insights into the state of the population: •It identifies candidates that are very similar to the best solution. •It highlights individuals with high fitness values, even if they differ significantly from the current best. Based on the first insight, the selection process avoids choosing candidates that are too similar to one another, thereby maintaining population diversity. In other words, individuals occupying closely located positions in the search space are not selected simultaneously. According to the second insight, the method ensures that candidates capable of compensating for the weaknesses of the current best solution are retained, thereby enhancing the exploration capability of the algorithm. Given a population of nsolution candidates O1, O2, . . . , On, the Fitness-Distance Balance (FDB) method proceeds in two main steps. In the first step, the fitness value F it(Oi) of each candidate Oi, as well as its distance from the current best solution dist(Oi, Obest), are calculated. Since a candidate solution in the clustering problem consists of a set of kcentroids, the distance between Oiand Obest is computed as the average distance between corresponding centroids. This approach captures the overall similarity between candidate solutions by considering the mean positional difference across all centroids. In the second step, a score is assigned to each candidate based on its normalized fitness Norm(F it(Oi)) and normalized distance Norm(dist(Oi, Obest)). A weight coefficient w, where 0 < w < 1, is used to balance the influence of fitness and distance in the score computation. In this study, the weight is set to w= 0.5, giving equal importance to both factors. Two alternative equations can be used to calculate the score of a candidate in the FDB method: •Linear combination (Score1): Score1(Oi) = w·Norm(F it(Oi)) + (1 −w)·Norm(dist(Oi, Obest)) (8) •Multiplicative combination (Score2): Score2(Oi) = Norm(F it(Oi)) ·Norm(dist(Oi, Obest)) (9) Both formulations serve to guide the selection process by favoring candidates that either combine high fitness with diversity (distance from the best) or strike a balance between the two. The initial population 211 of the SOS (Symbiotic Organisms Search) ecosystem is generated randomly, where each organism represents a potential solution to the clustering problem. During each iteration, the algorithm sequentially executes the three phases of the original SOS: Mutualism, Commensalism, and Parasitism. The detailed steps of the ISOS-based clustering algorithm are : •Randomly initialize the ecosystem with an initial population of organisms. •Repeat until t≤MaxGeneration or a stopping criterion is met: –For each organism Oiin the population (i= 1 to eco size): 1. Employ the FDB selection method to select another organism Ojsuch that Oj=Oi. 2. Generate new candidate solutions for both Oiand Ojbased on mutualistic symbiosis, using Equations (1), (2), and (3). 3. If the modified organisms are fitter than their previous versions, replace them accordingly. 4. Employ the FDB selection method to select another organism Ojsuch that Oj=Oi. 5. Generate a new candidate solution for Oibased on commensal symbiosis, using Equation (4). 6. If the modified Oiis fitter than its previous version, accept it. 7. Employ the FDB selection method to select another organism Ojsuch that Oj=Oi. 8. Generate a parasite vector from Oi. 9. If the parasite vector is fitter than Oj, replace Ojwith the parasite. –End For •Identify the current best organism in the population. •End While •Output the best organism and its fitness value. 4 Experiments and results The study employs three biomedical datasets: Breast A, NOVARTIS, and Breast B. Each dataset varies in terms of the number of genes, samples, and predefined clusters. The Breast A dataset contains 98 genes and 1,213 samples, which are grouped into 3 clusters. The NOVARTIS dataset includes 103 genes and 1,000 samples, divided into 4 clusters. Finally, the Breast B dataset consists of 49 genes and also 1,213 samples, organized into 4 clusters. To evaluate the effectiveness of the proposed algorithm, ISOS is compared against the standard SOS. All tested methods were executed with a fixed population size of 10 and a total of 100 iterations. For a fair and accurate comparison, the most commonly used configurations and the best-performing settings were adopted, based on the guidelines provided in the original publications. Table 1 presents the fitness values obtained using the ISOS and standard SOS clustering techniques. The best results are highlighted in bold for clarity. The results in this table clearly demonstrate that ISOS outperforms the standard SOS across all evaluated datasets. This superior performance reflects the algorithm’s ability to maintain a diverse population and effectively explore new regions of the search space. This can be largely attributed to the incorporation of the FDB selection mechanism in ISOS, which enhances the standard SOS by reducing the risk of premature convergence to local optima. Furthermore, the use of the selected fitness function contributes to generating more compact and cohesive clustering results. Datasets SOS ISOS Novartis 25087.5751 25491.1220 Breast A 6.39510 6.57300 Breast B 5.54010 5.82124 Table 1: Comparison of SOS and ISOS results for different datasets. A comparison of the convergence behavior of all the experimented algorithms on the NOVARTIS, Breast A and Breast B datasets is seen in Figures 1,2, and 3, in that order. It is clear from these results that the suggested ISOS converges more quickly than the standard SOS. Therefore, ISOS is better than the standard SOS algorithm. 212 Figure 1: The Fitness function variation of ISOS and SOS clustering algorithms on Novartis dataset Figure 2: The Fitness function variation of ISOS and SOS clustering algorithms on Breast A dataset 5 Conclusion In this study, we proposed an improved Symbiotic Organisms Search (SOS) algorithm, enhanced with the Fitness-Distance Balance (FDB) selection method, for effective clustering of biomedical data. The SOS algorithm, inspired by natural symbiotic relationships, provides a robust and flexible framework for exploring high-dimensional solution spaces. By incorporating the FDB strategy, the proposed algorithm successfully addresses the challenge of premature convergence often encountered in metaheuristic search processes. The integration of the I index as a fitness function further ensures the formation of compact and well-separated clusters, which is particularly beneficial in the context of biomedical datasets where precision and interpretability are critical. Experimental evaluations demonstrate that the improved SOS algorithm (ISOS) outperforms traditional clustering methods and baseline metaheuristic approaches in terms of clustering quality and convergence behavior. Overall, this work underscores the potential of nature-inspired optimization algorithms in handling complex biomedical data analysis tasks. Future research may focus on extending the approach to dynamic and multi-objective clustering scenarios, as well as exploring hybridization with other machine learning models to further enhance clustering accuracy and scalability. 213 Figure 3: The Fitness function variation of ISOS and SOS clustering algorithms on Breast B dataset References [1] O. Al-Janabee and B. Al-Sarray. Review of clustering for gene expression data. AIP Conference Proceedings, 2475(1):070019, 2023. [2] S. Ishak Boushaki, O. Bendjeghaba, N. Kamel, and D. E. Salhi. Enhanced gaussian quantum particle swarm optimization for the clustering of biomedical data. In H. Drias and F. Yalaoui, editors, Quantum Computing: Applications and Challenges, volume 2 of Information Systems Engineering and Management. Springer, Cham, 2024. [3] Min-Yuan Cheng and Doddy Prayogo. Symbiotic organisms search: A new metaheuristic optimization algorithm. Computers & Structures, 139:98–112, 2014. [4] Hamdi Tolga Kahraman, Sefa Aras, and Ey¨up Gedikli. Fitness-distance balance (fdb): A new selection method for meta-heuristic search algorithms. Knowledge-Based Systems, 190:105169, 2020. [5] Z. Liu, Y. Li, C. Liu, X. Zhao, and W. Yin. Application of k-means clustering algorithm in analyzing college students’ mental health. In 2024 3rd International Conference on Artificial Intelligence and Autonomous Robot Systems (AIARS), pages 175–180, Bristol, United Kingdom, 2024. [6] U. Maulik and S. Bandyopadhyay. Performance evaluation of some clustering algorithms and validity indices. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(12):1650–1654, 2002. [7] Jaswinder Singh and Damanpreet Singh. A comprehensive review of clustering techniques in artificial intelligence for knowledge discovery: Taxonomy, challenges, applications and future prospects. Advanced Engineering Informatics, 62(Part C):102799, 2024. [8] Farhad Soleimanian Gharehchopogh, Benyamin Abdollahzadeh, Nima Khodadadi, and Seyedali Mirjalili. Chapter 20 - metaheuristics for clustering problems. In Seyedali Mirjalili and Amir H. Gandomi, editors, Comprehensive Metaheuristics, pages 379–392. Academic Press, 2023. 214