© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Publications by Prof Alex Freitas
Also view these in the Kent Academic Repository
Article
Ribeiro, C. and Freitas, A. A. (2021) “A data-driven missing value imputation approach for longitudinal datasets”, Artificial Intelligence Review. Springer. doi: 10.1007/s10462-021-09963-5.
Longitudinal datasets of human ageing studies usually have a high volume of missing data, and one way to handle missing values in a dataset is to replace them with estimations. However, there are many methods to estimate missing values, and no single method is the best for all datasets. In this article, we propose a data-driven missing value imputation approach that performs a feature-wise selection of the best imputation method, using known information in the dataset to rank the five methods we selected, based on their estimation error rates. We evaluated the proposed approach in two sets of experiments: a classifier-independent scenario, where we compared the applicabilities and error rates of each imputation method; and a classifier-dependent scenario, where we compared the predictive accuracy of Random Forest classifiers generated with datasets prepared using each imputation method and a baseline approach of doing no imputation (letting the classification algorithm handle the missing values internally). Based on our results from both sets of experiments, we concluded that the proposed data-driven missing value imputation approach generally resulted in models with more accurate estimations for missing data and better performing classifiers, in longitudinal datasets of human ageing. We also observed that imputation methods devised specifically for longitudinal data had very accurate estimations. This reinforces the idea that using the temporal information intrinsic to longitudinal data is a worthwhile endeavour for machine learning applications, and that can be achieved through the proposed data-driven approach.
Tighe, D., Fabris, F. and Freitas, A. (2021) “Machine learning methods applied to audit of surgical margins after curative surgery for head and neck cancer”, British Journal of Oral and Maxillofacial Surgery. Elsevier, pp. 209-216. doi: 10.1016/j.bjoms.2020.08.041.
Most surgical specialties have attempted to address concerns about the unfair comparison of outcomes by ‘risk-adjusting’ data to benchmark specialty-specific outcomes that are indicative of quality of care. We explore the ability to predict for positive margin status so that effective benchmarking that will account for complexity of case mix is possible. A dataset of care episodes recorded as a clinical audit of margin status after surgery for head and neck squamous cell carcinoma (n=1316) was analysed within the Waikato Environment for Knowledge Analyisis (WEKA) machine learning programme. The outcome was a classification model that can predict for positivity of tumour margins (defined as less than 1mm) using data on preoperative demographics, operations, functional status, and tumour stage. Positive resection margins of less than 1mm were common, and varied considerably between treatment units (19%-29%). Four algorithms were compared to attempt to risk-adjust for case complexity. The 'champion' model was a Naïve Bayes classifier (AUROC 0.72) that suggested acceptable discrimination. Calibration was good (Hosmer-Lemershow goodness-of-fit test p=0.9). Adjusted positive margin rates are presented on a funnel plot. Subspecialty groups within oral and maxillofacial surgery are seeking metrics that will allow for meaningful comparison of the quality of care delivered by surgical units in the UK. To enable metrics to be effective, we argue that they can be modelled so that meaningful benchmarking, which takes account of variation in complexity of patient need or care, is possible.
Palmer, D., Fabris, F., Doherty, A., Freitas, A. A. and de Magalhaes, J. P. (2021) “Ageing transcriptome meta-analysis reveals similarities between key mammalian tissues”, Aging. Impact Journals, pp. 3313-3341. doi: 10.18632/aging.202648.
By combining transcriptomic data with other data sources, inferences can be made about functional changes during ageing. Thus, we conducted a meta-analysis on 127 publicly available microarray and RNA-Seq datasets from mice, rats and humans, identifying a transcriptomic signature of ageing across species and tissues. Analyses on subsets of these datasets produced transcriptomic signatures of ageing for brain, heart and muscle. We then applied enrichment analysis and machine learning to functionally describe these signatures, revealing overexpression of immune and stress response genes and underexpression of metabolic and developmental genes. Further analyses revealed little overlap between genes differentially expressed with age in different tissues, despite ageing differentially expressed genes typically being widely expressed across tissues. Additionally we show that the ageing gene expression signatures (particularly the overexpressed signatures) of the whole meta-analysis, brain and muscle tend to include genes that are central in protein-protein interaction networks. We also show that genes underexpressed with age in the brain are highly central in a co-expression network, suggesting that underexpression of these genes may have broad phenotypic consequences. In sum, we show numerous functional similarities between the ageing transcriptomes of these important tissues, along with unique network properties of genes differentially expressed with age in both a protein-protein interaction and co-expression networks.
Pavelski, L., Delgado, M., Kessaci, M. and Freitas, A. A. (2020) “Stochastic local search and parameters recommendation: a case study on flowshop problems”, International Transactions in Operational Research. Wiley, pp. 1-26. doi: 10.1111/itor.12922.
Neumann, N. M., Plastino, A., Pinto Junior, J. A. and Freitas, A. A. (2020) “A study on the statistical evaluation of classifiers”, Knowledge Engineering Review. Cambridge University Press, pp. 1-26. doi: 10.1017/S0269888920000417.
Statistical significance analysis, based on hypothesis tests, is a common approach for comparing classifiers. However, many studies oversimplify this analysis by simply checking the condition p-value < 0.05, ignoring important concepts such as the effect size and the statistical power of the test. This problem is so worrying that the American Statistical Association has taken a strong stand on the subject, noting that although the p-value is a useful statistical measure, it has been abusively used and misinterpreted. This work highlights problems caused by the misuse of hypothesis tests and shows how the effect size and the power of the test can provide important information for better decision-making. To investigate these issues, we perform empirical studies with different classifiers and 50 datasets, using the Student’s t-test and the Wilcoxon test to compare classifiers. The results show that an isolated p-value analysis can lead to wrong conclusions and that the evaluation of the effect size and the power of the test contributes to a more principled decision-making.
Basgalupp, M., Barros, R., de Sá, A., Pappa, G., Mantovani, R., de Carvalho, A. and Freitas, A. (2020) “An extensive experimental evaluation of automated machine learning methods for recommending classification algorithms”, Evolutionary Intelligence. Springer, pp. 1895-1914. doi: 10.1007/s12065-020-00463-z.
This paper presents an experimental comparison among four automated machine learning (AutoML) methods for recommending the best classification algorithm for a given input dataset. Three of these methods are based on evolutionary algorithms (EAs), and the other is Auto-WEKA, a well-known AutoML method based on the combined algorithm selection and hyper-parameter optimisation (CASH) approach. The EA-based methods build classification algorithms from a single machine learning paradigm: either decision-tree induction, rule induction, or Bayesian network classification. Auto-WEKA combines algorithm selection and hyper-parameter optimisation to recommend classification algorithms from multiple paradigms. We performed controlled experiments where these four AutoML methods were given the same runtime limit for different values of this limit. In general, the difference in predictive accuracy of the three best AutoML methods was not statistically significant. However, the EA evolving decision-tree induction algorithms has the advantage of producing algorithms that generate interpretable classification models and that are more scalable to large datasets, by comparison with many algorithms from other learning paradigms that can be recommended by Auto-WEKA. We also observed that Auto-WEKA has shown meta-overfitting, a form of overfitting at the meta-learning level, rather than at the base-learning level.
da Silva, P. N., Plastino, A. and Freitas, A. A. (2020) “Prioritizing positive feature values: a new hierarchical feature selection method”, Applied Intelligence. Springer. doi: 10.1007/s10489-020-01782-5.
In this work, we address the problem of feature selection for the classification task in hierarchical and sparse feature spaces, which characterise many real-world applications nowadays. A binary feature space is deemed hierarchical when its binary features are related via generalization-specialization relationships, and is considered sparse when in general the instances contain much fewer “positive” than “negative” feature values. In any given instance, a feature value is deemed positive (negative) when the property associated with the feature has been (has not been) observed for that instance. Although there are many methods for the traditional feature selection problem in the literature, the proper treatment to hierarchical feature structures is still a challenge. Hence, we introduce a novel hierarchical feature selection method that follows the lazy learning paradigm – selecting a feature subset tailored for each instance in the test set. Our strategy prioritizes the selection of features with positive values, since they tend to be more informative – the presence of a relatively rare property is usually a piece of more relevant information than the absence of that property. Experiments on different application domains have shown that the proposed method outperforms previous hierarchical feature selection methods and also traditional methods in terms of predictive accuracy, selecting smaller feature subsets in general.
Fabris, F., Palmer, D., de Magalhaes, J. P. and Freitas, A. A. (2020) “Comparing enrichment analysis and machine learning for identifying gene properties that discriminate between gene classes”, Briefings in Bioinformatics. Oxford University Press, pp. 803-814. doi: 10.1093/bib/bbz028.
Biologists very often use enrichment methods based on statistical hypothesis tests to identify gene properties that are significantly over-represented in a given set of genes of interest, by comparison with a ‘background’ set of genes. These enrichment methods, although based on rigorous statistical foundations, are not always the best single option to identify patterns in biological data. In many cases, one can also use classification algorithms from the machine-learning field. Unlike enrichment methods, classification algorithms are designed to maximize measures of predictive performance and are capable of analysing combinations of gene properties, instead of one property at a time. In practice, however, the majority of studies use either enrichment or classification methods (rather than both), and there is a lack of literature discussing the pros and cons of both types of method. The goal of this paper is to compare and contrast enrichment and classification methods, offering two contributions. First, we discuss the (to some extent complementary) advantages and disadvantages of both types of methods for identifying gene properties that discriminate between gene classes. Second, we provide a set of high-level recommendations for using enrichment and classification methods. Overall, by highlighting the strengths and the weaknesses of both types of methods we argue that both should be used in bioinformatics analyses.
Da Silva, P. N., Plastino, A., Fabris, F. and Freitas, A. A. (2020) “A Novel Feature Selection Method for Uncertain Features: An Application to the Prediction of Pro-/Anti- Longevity Genes”, IEEE/ACM Transactions on Computational Biology and Bioinformatics. IEEE. doi: 10.1109/TCBB.2020.2988450.
Understanding the ageing process is a very challenging problem for biologists. To help in this task, there has been a growing use of classification methods (from machine learning) to learn models that predict whether a gene influences the process of ageing or promotes longevity. One type of predictive feature often used for learning such classification models is Protein-Protein Interaction (PPI) features. One important property of PPI features is their uncertainty, i.e., a given feature (PPI annotation) is often associated with a confidence score, which is usually ignored by conventional classification methods. Hence, we propose the Lazy Feature Selection for Uncertain Features (LFSUF) method, which is tailored for coping with the uncertainty in PPI confidence scores. In addition, following the lazy learning paradigm, LFSUF selects features for each instance to be classified, making the feature selection process more flexible. We show that our LFSUF method achieves better predictive accuracy when compared to other feature selection methods that either do not explicitly take PPI confidence scores into account or deal with uncertainty globally rather than using a per-instance approach. Also, we interpret the results of the classification process using the features selected by LFSUF, showing that the number of selected features is significantly reduced, assisting the interpretability of the results. The datasets used in the experiments and the program code of the LFSUF method are freely available on the web at http://github.com/pablonsilva/FSforUncertainFeatureSpaces.
Xavier-Junior, J. C., Freitas, A. A., Ludermir, T. B., Feitosa-Neto, A. and Barreto, C. A. (2020) “An evolutionary algorithm for automated machine learning focusing on classifier ensembles: an improved algorithm and extended results”, Theoretical Computer Science. Elsevier, pp. 1-18. doi: 10.1016/j.tcs.2019.12.002.
A large number of classification algorithms have been proposed in the machine learning literature. These algorithms have different pros and cons, and no algorithm is the best for all datasets. Hence, a challenging problem consists of choosing the best classification algorithm with its best hyper-parameter settings for a given input dataset. In the last few years, Automated Machine Learning (Auto-ML) has emerged as a promising approach for tackling this problem, by doing a heuristic search in a large space of candidate classification algorithms and their hyper-parameter settings. In this work we propose an improved version of our previous Evolutionary Algorithm (EA) – more precisely, an Estimation of Distribution Algorithm – for the Auto-ML task of automatically selecting the best classifier ensemble and its best hyper-parameter settings for an input dataset. The new version of this EA was compared against its previous version, as well as against a random forest algorithm (a strong ensemble algorithm) and a version of the well-known Auto-ML method Auto-WEKA adapted to search in the same space of classifier ensembles as the proposed EA. In general, in experiments with 21 datasets, the new EA version obtained the best results among all methods in terms of four popular predictive accuracy measures: error rate, precision, recall and F-measure.
Fabris, F., Palmer, D., Salama, K. M., de Magalhaes, J. P. and Freitas, A. A. (2019) “Using deep learning to associate human genes with age-related diseases”, Bioinformatics. Oxford University Press, pp. 2202-2208. doi: 10.1093/bioinformatics/btz887.
Motivation: One way to identify genes possibly associated with ageing is to build a classification model (from the machine learning field) capable of classifying genes as associated with multiple age-related diseases. To build this model, we use a pre-compiled list of human genes associated with age-related diseases and apply a novel Deep Neural Network (DNN) method to find associations between gene descriptors (e.g. Gene Ontology terms, protein–protein interaction data and biological pathway information) and age-related diseases. Results: The novelty of our new DNN method is its modular architecture, which has the capability of combining several sources of biological data to predict which ageing-related diseases a gene is associated with (if any). Our DNN method achieves better predictive performance than standard DNN approaches, a Gradient Boosted Tree classifier (a strong baseline method) and a Logistic Regression classifier. Given the DNN model produced by our method, we use two approaches to identify human genes that are not known to be associated with age-related diseases according to our dataset. First, we investigate genes that are close to other disease-associated genes in a complex multi-dimensional feature space learned by the DNN algorithm. Second, using the class label probabilities output by our DNN approach, we identify genes with a high probability of being associated with age-related diseases according to the model. We provide evidence of these putative associations retrieved from the DNN model with literature support. The source code and datasets can be found at: https://github.com/fabiofabris/Bioinfo2019.
Cramer, S., Kampouridis, M., Freitas, A. A. and Alexandridis, A. (2019) “Stochastic Model Genetic Programming: Deriving Pricing Equations for Rainfall Weather Derivatives”, Swarm and Evolutionary Computation. Elsevier, pp. 184-200. doi: 10.1016/j.swevo.2019.01.008.
Rainfall derivatives are in their infancy since starting trading on the Chicago Mercantile Exchange (CME) in 2011. Being a relatively new class of financial instruments there is no generally recognised pricing framework used within the literature. In this paper, we propose a novel Genetic Programming (GP) algorithm for pricing contracts. Our novel algorithm, which is called Stochastic Model GP (SMGP), is able to generate and evolve stochastic equations of rainfall, which allows us to probabilistically transform rainfall predictions from the risky world to the risk-neutral world. In order to achieve this, SMGP’s representation allows its individuals to comprise of two weighted parts, namely a seasonal component and an autoregressive component. To create the stochastic nature of an equation for each SMGP individual, we estimate the weights by using a probabilistic approach. We evaluate the models produced by SMGP in terms of rainfall predictive accuracy and in terms of pricing performance on 42 cities from Europe and the USA. We compare SMGP to 8 methods: its predecessor DGP, 5 well-known machine learning methods (M5 Rules, M5 Model trees, k-Nearest Neighbors, Support Vector Regression, Radial Basis Function), and two statistical methods, namely AutoRegressive Integrated Moving Average (ARIMA) and Monte Carlo Rainfall Prediction (MCRP). Results show that the proposed algorithm is able to statistically outperform all other algorithms.
Freitas, A. A. (2019) “Investigating the Role of Simpson’s Paradox in the Analysis of Top-Ranked Features in High-Dimensional Bioinformatics Datasets”, Briefings in Bioinformatics. Oxford University Press, pp. 421-428. doi: 10.1093/bib/bby126.
An important problem in bioinformatics consists of identifying the most important features (or predictors), among a large number of features in a given classification dataset. This problem is often addressed by using a machine learning-based feature ranking method to identify a small set of top-ranked predictors (i.e. the most relevant features for classification). The large number of studies in this area have, however, an important limitation: they ignore the possibility that the top-ranked predictors occur in an instance of Simpson’s paradox, where the positive or negative association between a predictor and a class variable reverses sign upon conditional on each of the values of a third (confounder) variable. In this work, we review and investigate the role of Simpson’s paradox in the analysis of top-ranked predictors in high-dimensional bioinformatics datasets, in order to avoid the potential danger of misinterpreting an association between a predictor and the class variable. We perform computational experiments using four well-known feature ranking methods from the machine learning field and five high-dimensional datasets of ageing-related genes, where the predictors are Gene Ontology terms. The results show that occurrences of Simpson’s paradox involving top-ranked predictors are much more common for one of the feature ranking methods.
Tighe, D., Lewis-Morris, T. and Freitas, A. A. (2019) “Machine learning methods applied to audit of surgical outcomes after treatment for cancer of the head and neck”, British Journal of Oral and Maxillofacial Surgery. Elsevier, pp. 771-777. doi: 10.1016/j.bjoms.2019.05.026.
Most surgical specialties have attempted to address concerns about unfair comparison of outcomes by “risk-adjusting” data to benchmark specialty-specific outcomes that are indicative of the quality of care. We are building on previous work in head and neck surgery to address the current need for a robust validated means of risk adjustment. A dataset of care episodes, which were recorded as a clinical audit of complications after operations for squamous cell carcinoma (SCC) of the head and neck (n = 1254), was analysed with the Waikarto Environment for Knowledge Analysis (WEKA) machine learning tool. This produced 4 classification models that could predict complications using data on the preoperative demographics of the patients, operation, functional status, and tumour stage. Three of them performed acceptably: one that predicted “any complication” within 30 days (area under the receiver operating characteristic curve (AUROC) 0.72), one that predicted severe complications (Clavien-Dindo grade 3 or above) within 30 days (AUROC 0.70), and one that predicted a prolonged duration of hospital stay of more than 15 days, (AUROC 0.81). The final model, which was developed on a subgroup of patients who had free tissue transfer (n = 443), performed poorly (AUROC 0.59). Subspecialty groups within oral and maxillofacial surgery are seeking metrics that will allow a meaningful comparison of the quality of care delivered by surgical units in the UK. For these metrics to be effective they must show variation between units and be amendable to change by service personnel. Published baseline data must also be available. They should be modelled effectively so that meaningful comparison, which takes account of variations in the complexity of the patients’ needs or care, is possible.
Zhou, N., Jiang, Y., Bergquist, T. R., Lee, A. J., Kacsoh, B. Z., Crocker, A. W., Lewis, K. A., Georghiou, G., Nguyen, H. N., Hamid, M. N., Davis, L., Dogan, T., Atalay, V., Rifaioglu, A. S., Dalkıran, A., Cetin Atalay, R., Zhang, C., Hurto, R. L., Freddolino, P. L., Zhang, Y., Bhat, P., Supek, F., Fernández, J. M., Gemovic, B., Perovic, V. R., Davidović, R. S., Sumonja, N., Veljkovic, N., Asgari, E., Mofrad, M. R., Profiti, G., Savojardo, C., Martelli, P. L., Casadio, R., Boecker, F., Schoof, H., Kahanda, I., Thurlby, N., McHardy, A. C., Renaux, A., Saidi, R., Gough, J., Freitas, A. A., Antczak, M., Fabris, F., Wass, M. N., Hou, J., Cheng, J., Wang, Z., Romero, A. E., Paccanaro, A., Yang, H., Goldberg, T., Zhao, C., Holm, L., Törönen, P., Medlar, A. J., Zosa, E., Borukhov, I., Novikov, I., Wilkins, A., Lichtarge, O., Chi, P.-H., Tseng, W.-C., Linial, M., Rose, P. W., Dessimoz, C., Vidulin, V., Dzeroski, S., Sillitoe, I., Das, S., Lees, J. G., Jones, D. T., Wan, C., Cozzetto, D., Fa, R., Torres, M., Warwick Vesztrocy, A., Rodriguez, J. M., Tress, M. L., Frasca, M., Notaro, M., Grossi, G., Petrini, A., Re, M., Valentini, G., Mesiti, M., Roche, D. B., Reeb, J., Ritchie, D. W., Aridhi, S., Alborzi, S. Z., Devignes, M.-D., Koo, D. C. E., Bonneau, R., Gligorijević, V., Barot, M., Fang, H., Toppo, S., Lavezzo, E., Falda, M., Berselli, M., Tosatto, S. C., Carraro, M., Piovesan, D., Ur Rehman, H., Mao, Q., Zhang, S., Vucetic, S., Black, G. S., Jo, D., Suh, E., Dayton, J. B., Larsen, D. J., Omdahl, A. R., McGuffin, L. J., Brackenridge, D. A., Babbitt, P. C., Yunes, J. M., Fontana, P., Zhang, F., Zhu, S., You, R., Zhang, Z., Dai, S., Yao, S., Tian, W., Cao, R., Chandler, C., Amezola, M., Johnson, D., Chang, J.-M., Liao, W.-H., Liu, Y.-W., Pascarelli, S., Frank, Y., Hoehndorf, R., Kulmanov, M., Boudellioua, I., Politano, G., Di Carlo, S., Benso, A., Hakala, K., Ginter, F., Mehryary, F., Kaewphan, S., Björne, J., Moen, H., Tolvanen, M. E., Salakoski, T., Kihara, D., Jain, A., Šmuc, T., Altenhoff, A., Ben-Hur, A., Rost, B., Brenner, S. E., Orengo, C. A., Jeffery, C. J., Bosco, G., Hogan, D. A., Martin, M. J., O’Donovan, C., Mooney, S. D., Greene, C. S., Radivojac, P. and Friedberg, I. (2019) “The CAFA challenge reports improved protein function prediction and new functional annotations for hundreds of genes through experimental screens”, Genome Biology. BMC. doi: 10.1186/s13059-019-1835-8.
Background: The Critical Assessment of Functional Annotation (CAFA) is an ongoing, global, community-driven effort to evaluate and improve the computational annotation of protein function. Results: Here, we report on the results of the third CAFA challenge, CAFA3, that featured an expanded analysis over the previous CAFA rounds, both in terms of volume of data analyzed and the types of analysis performed. In a novel and major new development, computational predictions and assessment goals drove some of the experimental assays, resulting in new functional annotations for more than 1000 genes. Specifically, we performed experimental wholegenome mutation screening in Candida albicans and aeruginosa genomes, which provided us with genome-wide experimental data for genes associated with biofilm formation and motility. We further performed targeted assays on selected genes in Drosophila melanogaster, which we suspected of being involved in long-term memory. Conclusion: We conclude that while predictions of the molecular function and biological process annotations have slightly improved over time, those of the cellular component have not. Term-centric prediction of experimental annotations remains equally challenging; although the performance of the top methods is significantly better than the expectations set by baseline methods in C. albicans and D. melanogaster, it leaves considerable room and need for improvement. Finally, we report that the CAFA community now involves a broad range of participants with expertise in bioinformatics, biological experimentation, biocuration, and bio-ontologies, working together to improve functional annotation, computational function prediction, and our ability to manage big data in the era of large experimental screens.
Cramer, S., Kampouridis, M. and Freitas, A. A. (2018) “Decomposition Genetic Programming: An Extensive Evaluation on Rainfall Prediction in the Context of Weather Derivatives”, Applied Soft Computing. Elsevier, pp. 208-224. doi: 10.1016/j.asoc.2018.05.016.
Regression problems provide some of the most challenging research opportunities in the area of machine learning, where the predictions of some target variables are critical to a specific application. Rainfall is a prime example, as it exhibits unique characteristics of high volatility and chaotic patterns that do not exist in other time series data. Moreover, rainfall is essential for applications that surround financial securities, such as rainfall derivatives. This paper extensively evaluates a novel algorithm called Decomposition Genetic Programming (DGP), which is an algorithm that decomposes the problem of rainfall into subproblems. Decomposition allows the GP to focus on each subproblem, before combining back into the full problem. The GP does this by having a separate regression equation for each subproblem, based on the level of rainfall. As we turn our attention to subproblems, this reduces the difficulty when dealing with data sets with high volatility and extreme rainfall values, since these values can be focused on independently. We extensively evaluate our algorithm on 42 cities from Europe and the USA, and compare its performance to the current state-of-the-art (Markov chain extended with rainfall prediction), and six other popular machine learning algorithms (Genetic Programming without decomposition, Support Vector Regression, Radial Basis Neural Networks, M5 Rules, M5 Model trees, and k-Nearest Neighbours). Results show that the DGP is able to consistently and significantly outperform all other algorithms. Lastly, another contribution of this work is to discuss the effect that DGP has had on the coverage of the rainfall predictions and whether it shows robust performance across different climates.
Fabris, F., Doherty, A., Palmer, D., de Magalhães, J. P. and Freitas, A. A. (2018) “A new approach for interpreting Random Forest models and its application to the biology of ageing”, Bioinformatics. Oxford University Press, pp. 2449-2456. doi: 10.1093/bioinformatics/bty087.
This work uses the Random Forest (RF) classification algorithm to predict if a gene is over-expressed, under-expressed or has no change in expression with age in the brain. RFs have high predictive power, and RF models can be interpreted using a feature (variable) importance measure. However, current feature importance measures evaluate a feature as a whole (all feature values). We show that, for a popular type of biological data (Gene Ontology-based), usually only one value of a feature is particularly important for classification and the interpretation of the RF model. Hence, we propose a new algorithm for identifying the most important and most informative feature values in an RF model.
de Oliveira, L. L., Freitas, A. A. and Tinós, R. (2017) “Multi-objective genetic algorithms in the study of the genetic code’s adaptability”, Information Sciences. Elsevier, pp. 48-61. doi: 10.1016/j.ins.2017.10.022.
Using a robustness measure based on values of the polar requirement of amino acids, Freeland and Hurst (1998) showed that less than one in one million random hypothetical codes are better than the standard genetic code. In this paper, instead of comparing the standard code with randomly generated codes, we use an optimisation algorithm to find the best hypothetical codes. This approach has been used before, but considering only one objective to be optimised. The robustness measure based on the polar requirement is considered the most effective objective to be optimised by the algorithm. We propose here that the polar requirement is not the only property to be considered when computing the robustness of the genetic code. We include the hydropathy index and molecular volume in the evaluation of the amino acids using three multi-objective approaches: the weighted formula, lexicographic and Pareto approaches. To our knowledge, this is the first work proposing multi-objective optimisation approaches with a non-restrictive encoding for studying the evolution of the genetic code. Our results indicate that multi-objective approaches considering the three amino acid properties obtain better results than those obtained by single objective approaches reported in the literature. The codes obtained by the multi-objective approach are more robust and structurally more similar to the standard code.
Salama, K. M., Abdelbar, A. M., Helal, A. and Freitas, A. A. (2017) “Instance-based classification with ant colony optimization”, Intelligent Data Analysis. IOS Press, pp. 913-944. doi: 10.3233/IDA-160031.
Instance-based learning (IBL) methods predict the class label of a new instance based directly on the distance between the new unlabeled instance and each labeled instance in the training set, without constructing a classification model in the training phase. In this paper, we introduce a novel class-based feature weighting technique, in the context of instance-based distance methods, using the Ant Colony Optimization meta-heuristic. We address three different approaches of instance-based classification: k-Nearest Neighbours, distance-based Nearest Neighbours, and Gaussian Kernel Estimator. We present a multi-archive adaptation of the ACO? algorithm and apply it to the optimization of the key parameter in each IBL algorithm and of the class-based feature weights. We also propose an ensemble of classifiers approach that makes use of the archived populations of the ACO? algorithm. We empirically evaluate the performance of our proposed algorithms on 36 benchmark datasets, and compare them with conventional instance-based classification algorithms, using various parameter settings, as well as with a state-of-the-art coevolutionary algorithm for instance selection and feature weighting for Nearest Neighbours classifiers.
Barardo, D. G., Newby, D., Thornton, D., Ghafourian, T., Pedro de Magalhães, J. and Freitas, A. A. (2017) “Machine learning for predicting lifespan-extending chemical compounds”, Aging, pp. 1721-1737. doi: 10.18632/aging.101264.
Increasing age is a risk factor for many diseases; therefore developing pharmacological interventions that slow down ageing and consequently postpone the onset of many age-related diseases is highly desirable. In this work we analyse data from the DrugAge database, which contains chemical compounds and their effect on the lifespan of model organisms. Predictive models were built using the machine learning method random forests to predict whether or not a chemical compound will increase Caenorhabditis elegans’ lifespan, using as features Gene Ontology (GO) terms annotated for proteins targeted by the compounds and chemical descriptors calculated from each compound’s chemical structure. The model with the best predictive accuracy used both biological and chemical features, achieving a prediction accuracy of 80%. The top 20 most important GO terms include those related to mitochondrial processes, to enzymatic and immunological processes, and terms related to metabolic and transport processes. We applied our best model to predict compounds which are more likely to increase C. elegans’ lifespan in the DGIdb database, where the effect of the compounds on an organism’s lifespan is unknown. The top hit compounds can be broadly divided into four groups: compounds affecting mitochondria, compounds for cancer treatment, anti-inflammatories, and compounds for gonadotropin-releasing hormone therapies.
Cramer, S., Kampouridis, M., Freitas, A. A. and Alexandridis, A. (2017) “An extensive evaluation of seven machine learning methods for rainfall prediction in weather derivatives”, Expert Systems with Applications. Elsevier, pp. 169-181. doi: 10.1016/j.eswa.2017.05.029.
Regression problems provide some of the most challenging research opportunities in the area of machine learning, and more broadly intelligent systems, where the predictions of some target variables are critical to a specific application. Rainfall is a prime example, as it exhibits unique characteristics of high volatility and chaotic patterns that do not exist in other time series data. This work’s main impact is to show the benefit machine learning algorithms, and more broadly intelligent systems have over the current state-of-the-art techniques for rainfall prediction within rainfall derivatives. We apply and compare the predictive performance of the current state-of-the-art (Markov chain extended with rainfall prediction) and six other popular machine learning algorithms, namely: Genetic Programming, Support Vector Regression, Radial Basis Neural Networks, M5 Rules, M5 Model trees, and k-Nearest Neighbours. To assist in the extensive evaluation, we run tests using the rainfall time series across data sets for 42 cities, with very diverse climatic features. This thorough examination shows that the machine learning methods are able to outperform the current state-of-the-art. Another contribution of this work is to detect correlations between different climates and predictive accuracy. Thus, these results show the positive effect that machine learning-based intelligent systems have for predicting rainfall based on predictive accuracy and with minimal correlations existing across climates.
Ribeiro, C., Brito, L., Nobre, C., Freitas, A. A. and Zarate, L. (2017) “A revision and analysis of the comprehensiveness of the main longitudinal studies of human ageing for data mining research”, WIREs : Data Mining and Knowledge Discovery. Wiley. doi: 10.1002/widm.1202.
Human aging is a global problem that will have a large socioeconomic impact. A better understanding of aging can direct public policies that minimize its negative effects in the future. Over many years, several longitudinal studies of human aging have been conducted aiming to comprehend the phenomenon, and various factors influencing human aging are under analysis. In this review, we categorize the main aspects affecting human aging into a taxonomy for assisting data mining (DM) research on this topic. We also present tables summarizing the main characteristics of 64 research articles using data from aging-related longitudinal studies, in terms of the aging-related aspects analyzed, the main data analysis techniques used, and the specific longitudinal database mined in each article. Finally, we analyze the comprehensiveness of the main databases of longitudinal studies of human aging worldwide, regarding which proportion of the proposed taxonomy's aspects are covered by each longitudinal database. We observed that most articles analyzing such data use classical (parametric, linear) statistical techniques, with little use of more modern (nonparametric, nonlinear) DM methods for analyzing longitudinal databases of human aging. We hope that this article will contribute to DM research in two ways: first, by drawing attention to the important problem of global aging and the free availability of several longitudinal databases of human aging; second, by providing useful information to make research design choices about mining such data, e.g., which longitudinal study and which types of aging-related aspects should be analyzed, depending on the research's goals.
Fabris, F., Freitas, A. A. and de Magalhaes, J. P. (2017) “A Review of Supervised Machine Learning Applied to Ageing Research”, Biogerontology. Springer, pp. 171-188. doi: 10.1007/s10522-017-9683-y.
Broadly speaking, supervised machine learning is the computational task of learning correlations between variables in annotated data (the training set), and using this information to create a predictive model capable of inferring annotations for new data, whose annotations are not known. Ageing is a complex process that affects nearly all animal species. This process can be studied at several levels of abstraction, in different organisms and with different objectives in mind. Not surprisingly, the diversity of the supervised machine learning algorithms applied to answer biological questions reflects the complexities of the underlying ageing processes being studied. Many works using supervised machine learning to study the ageing process have been recently published, so it is timely to review these works, to discuss their main findings and weaknesses. In summary, the main findings of the reviewed papers are: the link between specific types of DNA repair and ageing, ageing-related proteins tend to be highly connected and seem to play a central role in molecular pathways; ageing/longevity is linked with autophagy and apoptosis, nutrient receptor genes, and copper and iron ion transport. Additionally, several biomarkers of ageing were found by machine learning. Despite some interesting machine learning results, we also identified a weakness of current works on this topic: only one of the reviewed papers has corroborated the computational results of machine learning algorithms through wet-lab experiments. In conclusion, supervised machine learning has contributed to advance our knowledge and has provided novel insights on ageing, yet future work should have a greater emphasis in validating the predictions.
Wan, C. and Freitas, A. A. (2017) “An empirical evaluation of hierarchical feature selection methods for classification in bioinformatics datasets with gene ontology-based features”, Artificial Intelligence Review. Springer, pp. 201-240. doi: 10.1007/s10462-017-9541-y.
Hierarchical feature selection is a new research area in machine learning/data mining, which consists of performing feature selection by exploiting dependency relationships among hierarchically structured features. This paper evaluates four hierarchical feature selection methods, i.e., HIP, MR, SHSEL and GTD, used together with four types of lazy learning-based classifiers, i.e., Naïve Bayes, Tree Augmented Naïve Bayes, Bayesian Network Augmented Naïve Bayes and k-Nearest Neighbors classifiers. These four hierarchical feature selection methods are compared with each other and with a well-known “flat” feature selection method, i.e., Correlation-based Feature Selection. The adopted bioinformatics datasets consist of aging-related genes used as instances and Gene Ontology terms used as hierarchical features. The experimental results reveal that the HIP (Select Hierarchical Information Preserving Features) method performs best overall, in terms of predictive accuracy and robustness when coping with data where the instances’ classes have a substantially imbalanced distribution. This paper also reports a list of the Gene Ontology terms that were most often selected by the HIP method.
Aniceto, N., Freitas, A. A., Bender, A. and Ghafourian, T. (2016) “A novel applicability domain technique for mapping predictive reliability across the chemical space of a QSAR: reliability-density neighbourhood”, Journal of Cheminformatics. Springer. doi: 10.1186/s13321-016-0182-y.
Otero, F. E. and Freitas, A. A. (2016) “Improving the Interpretability of Classification Rules Discovered by an Ant Colony Algorithm: Extended Results”, Evolutionary Computation. MIT Press, pp. 385-409. doi: 10.1162/EVCO_a_00155.
The vast majority of Ant Colony Optimization (ACO) algorithms for inducing classification rules use an ACO-based procedure to create a rule in an one-at-a-time fashion. An improved search strategy has been proposed in the cAnt-MinerPB algorithm, where an ACO-based procedure is used to create a complete list of rules (ordered rules)-i.e., the ACO search is guided by the quality of a list of rules, instead of an individual rule. In this paper we propose an extension of the cAnt-MinerPB algorithm to discover a set of rules (unordered rules). The main motivations for this work are to improve the interpretation of individual rules by discovering a set of rules and to evaluate the impact on the predictive accuracy of the algorithm. We also propose a new measure to evaluate the interpretability of the discovered rules to mitigate the fact that the commonly-used model size measure ignores how the rules are used to make a class prediction. Comparisons with state-of-the-art rule induction algorithms, support vector machines and the cAnt-MinerPB producing ordered rules are also presented.
Fernandes, M., Wan, C., Tacutu, R., Barardo, D., Rajput, A., Wang, J., Thoppil, H., Thornton, D., Yang, C., Freitas, A. A. and de Magalhaes, J. P. (2016) “Systematic analysis of the gerontome reveals links between aging and age-related diseases”, Human Molecular Genetics. Oxford University Press, pp. 4804-4818. doi: 10.1093/hmg/ddw307.
In model organisms, over 2,000 genes have been shown to modulate aging, the collection of which we call the ‘gerontome’. Although some individual aging-related genes have been the subject of intense scrutiny, their analysis as a whole has been limited. In particular, the genetic interaction of aging and age-related pathologies remain a subject of debate. In this work, we perform a systematic analysis of the gerontome across species, including human aging-related genes. First, by classifying aging-related genes as pro- or anti-longevity, we define distinct pathways and genes that modulate aging in different ways. Our subsequent comparison of aging-related genes with age-related disease genes reveals species-specific effects with strong overlaps between aging and age-related diseases in mice, yet surprisingly few overlaps in lower model organisms. We discover that genetic links between aging and age-related diseases are due to a small fraction of aging-related genes which also tend to have a high network connectivity. Other insights from our systematic analysis include assessing how using datasets with genes more or less studied than average may result in biases, showing that age-related disease genes have faster molecular evolution rates and predicting new aging-related drugs based on drug-gene interaction data. Overall, this is the largest systems-level analysis of the genetics of aging to date and the first to discriminate anti- and pro-longevity genes, revealing new insights on aging-related genes as a whole and their interactions with age-related diseases.
Aniceto, N., Freitas, A. A., Bender, A. and Ghafourian, T. (2016) “Simultaneous prediction of four ATP-binding cassette transporters substrates using multi-label QSAR”, Molecular Informatics. Wiley, pp. 514-528. doi: 10.1002/minf.201600036.
Efflux by the ATP-binding cassette (ABC) transporters affects the pharmacokinetic profile of drugs and it has been implicated in drug-drug interactions as well as its major role in multi-drug resistance in cancer. It is therefore important for the pharmaceutical industry to be able to understand what phenomena rule ABC substrate recognition. Considering a high degree of substrate overlap between various members of ABC transporter family, it is advantageous to employ a multi-label classification approach where predictions made for one transporter can be used for modeling of the other ABC transporters. Here, we present decision tree-based QSAR classification models able to simultaneously predict substrates and non-substrates for BCRP1, P-gp/MDR1 and MRP1 and MRP2, using a dataset of 1493 compounds. To this end, two multi-label classification QSAR modelling approaches were adopted: Binary Relevance (BR) and Classifier Chain (CC). Even though both multi-label models yielded similar predictive performances in terms of overall accuracies (close to 70?%), the CC model overcame the problem of skewed performance towards identifying substrates compared with non-substrates, which is a common problem in the literature. The models were thoroughly validated by using external testing, applicability domain and activity cliffs characterization. In conclusion, a multi-label classification approach is an appropriate alternative for the prediction of ABC efflux.
Fabris, F. and Freitas, A. A. (2016) “New KEGG pathway-based interpretable features for classifying ageing-related mouse proteins”, Bioinformatics. Oxford University Press, pp. 2988-2995. doi: 10.1093/bioinformatics/btw363.
Motivation: The incidence of ageing-related diseases has been constantly increasing in the last decades, raising the need for creating effective methods to analyze ageing-related protein data. These methods should have high predictive accuracy and be easily interpretable by ageing experts. To enable this, one needs interpretable classification models (supervised machine learning) and features with rich biological meaning. In this paper we propose two interpretable feature types based on Kyoto Encyclopedia of Genes and Genomes (KEGG) pathways and compare them with traditional feature types in hierarchical classification (a more challenging classification task regarding predictive performance) and binary classification (a classification task producing easier to interpret classification models). As far as we know, this work is the first to: (i) explore the potential of the KEGG pathway data in the hierarchical classification setting, (i) use the graph structure of KEGG pathways to create a feature type that quantifies the influence of a current protein on another specific protein within a KEGG pathway graph and (iii) propose a method for interpreting the classification models induced using KEGG features. Results: We performed tests measuring predictive accuracy considering hierarchical and binary class labels extracted from the Mouse Phenotype Ontology. One of the KEGG feature types leads to the highest predictive accuracy among five individual feature types across three hierarchical classification algorithms. Additionally, the combination of the two KEGG feature types proposed in this work results in one of the best predictive accuracies when using the binary class version of our datasets, at the same time enabling the extraction of knowledge from ageing-related data using quantitative influence information.
Fabris, F., Freitas, A. A. and Tullet, J. M. (2015) “An Extensive Empirical Comparison of Probabilistic Hierarchical Classifiers in Datasets of Ageing-Related Genes”, IEEE/ACM Transactions on Computational Biology and Bioinformatics. IEEE, pp. 1045-1058. doi: 10.1109/TCBB.2015.2505288.
This study comprehensively evaluates the performance of 5 types of probabilistic hierarchical classification methods used for predicting Gene Ontology (GO) terms related to ageing. Of those tested, a new hybrid of a Local Hierarchical Classifier (LHC) and the Predictive Clustering Tree algorithm (LHC-PCT) had the best predictive accuracy results. We also tested the impact of two types of variations in most hierarchical classification algorithms, namely: (a) changing the base algorithm (we tested Naive Bayes and Support Vector Machines), and the impact of (b) using or not the Correlation based Feature Selection (CFS) algorithm in a pre-processing step. In total, we evaluated the predictive performance of 17 variations of hierarchical classifiers across 15 datasets of ageing and longevityrelated genes. We conclude that the LHC-PCT algorithm ranks better across several tests (7 out of 12). In addition, we interpreted the models generated by the PCT algorithm to show how hierarchical classification algorithms can be used to extract biological insights out of the ageing-related datasets that we compiled.
Wan, C., Freitas, A. A. and de Magalhaes, J. P. (2015) “Predicting the pro-longevity or anti-longevity effect of model organism genes with new hierarchical feature selection methods”, IEEE/ACM Transactions on Computational Biology and Bioinformatics. IEEE, pp. 262-275. doi: 10.1109/TCBB.2014.2355218.
Ageing is a highly complex biological process that is still poorly understood. With the growing amount of ageing-related data available on the web, in particular concerning the genetics of ageing, it is timely to apply data mining methods to that data, in order to try to discover novel patterns that may assist ageing research. In this work, we introduce new hierarchical feature selection methods for the classification task of data mining and apply them to ageing-related data from four model organisms: Caenorhabditis elegans (worm), Saccharomyces cerevisiae (yeast), Drosophila melanogaster (fly), and Mus musculus (mouse). The main novel aspect of the proposed feature selection methods is that they exploit hierarchical relationships in the set of features (Gene Ontology terms) in order to improve the predictive accuracy of the Naïve Bayes and 1-Nearest Neighbour (1-NN) classifiers, which are used to classify model organisms’ genes into pro-longevity or anti-longevity genes. The results show that our hierarchical feature selection methods, when used together with Naïve Bayes and 1-NN classifiers, obtain higher predictive accuracy than the standard (without feature selection) Naïve Bayes and 1-NN classifiers, respectively. We also discuss the biological relevance of a number of Gene Ontology terms very frequently selected by our algorithms in our datasets.
Cerri, R., Pappa, G. L., de Carvalho, A. C. and Freitas, A. A. (2015) “An extensive evaluation of decision-tree based hierarchical multilabel classification methods and performance measures”, Computational Intelligence, pp. 1-46.
Newby, D., Freitas, A. A. and Ghafourian, T. (2015) “Decision trees to characterise the roles of permeability and solubility on the prediction of oral absorption.”, European Journal of Medicinal Chemistry, pp. 751-765.
Newby, D., Freitas, A. A. and Ghafourian, T. (2015) “Comparing Multi-Label Classification Methods for Provisional Biopharmaceutics Class Prediction.”, Molecular Pharmaceutics, pp. 87-102.
Freitas, A. A., Limbu, K. and Ghafourian, T. (2015) “Predicting volume of distribution with decision tree-based regression methods using predicted tissue:plasma partition coefficients”, Journal of Cheminformatics. doi: 10.1186/s13321-015-0054-x.
Background Volume of distribution is an important pharmacokinetic property that indicates the extent of a drug’s distribution in the body tissues. This paper addresses the problem of how to estimate the apparent volume of distribution at steady state (Vss) of chemical compounds in the human body using decision tree-based regression methods from the area of data mining (or machine learning). Hence, the pros and cons of several different types of decision tree-based regression methods have been discussed. The regression methods predict Vss using, as predictive features, both the compounds’ molecular descriptors and the compounds’ tissue:plasma partition coefficients (Kt:p) – often used in physiologically-based pharmacokinetics. Therefore, this work has assessed whether the data mining-based prediction of Vss can be made more accurate by using as input not only the compounds’ molecular descriptors but also (a subset of) their predicted Kt:p values. Results Comparison of the models that used only molecular descriptors, in particular, the Bagging decision tree (mean fold error of 2.33), with those employing predicted Kt:p values in addition to the molecular descriptors, such as the Bagging decision tree using adipose Kt:p (mean fold error of 2.29), indicated that the use of predicted Kt:p values as descriptors may be beneficial for accurate prediction of Vss using decision trees if prior feature selection is applied. Conclusions Decision tree based models presented in this work have an accuracy that is reasonable and similar to the accuracy of reported Vss inter-species extrapolations in the literature. The estimation of Vss for new compounds in drug discovery will benefit from methods that are able to integrate large and varied sources of data and flexible non-linear data mining methods such as decision trees, which can produce interpretable models.
Salama, K. M. and Freitas, A. A. (2015) “Ant colony algorithms for constructing Bayesian multi-net classifiers”, Intelligent Data Analysis. IOS Press, pp. 233-257. doi: 10.3233/IDA-150715.
Bayesian Multi-nets (BMNs) are a special kind of Bayesian network (BN) classifiers that consist of several local Bayesian networks, one for each predictable class, to model an asymmetric set of variable dependencies given each class value. Deterministic methods using greedy local search are the most frequently used methods for learning the structure of BMNs based on optimizing a scoring function. Ant Colony Optimization (ACO) is a meta-heuristic global search method for solving combinatorial optimization problems, inspired by the behavior of real ant colonies. In this paper, we propose two novel ACO-based algorithms with two different approaches to build BMN classifiers: ABC-Miner^{mn}_l and ABC-Miner^{mn}_g . The former uses a local learning approach, in which the ACO algorithm completes the construction of one local BN at a time. The latter uses a global approach, which involves building a complete BMN classifier by each single ant in the colony. We experimentally evaluate the performance of our ant-based algorithms on 33 benchmark classification datasets, where our proposed algorithms are shown to be significantly better than other commonly used deterministic algorithms for learning various Bayesian classifiers in the literature, as well as competitive to other well-known classification algorithms.
Salama, K. M. and Freitas, A. A. (2014) “Classification with cluster-based Bayesian multi-nets using Ant Colony Optimisation”, Swarm and Evolutionary Computation. Elsevier, pp. 54-70. doi: 10.1016/j.swevo.2014.05.001.
Bayesian multi-net (BMN) classifiers consist of several local models, one for each data subset, to model asymmetric, more consistent dependency relationships among variables in each subset. This paper extends an earlier work of ours and proposes several contributions to the field of clustering-based BMN classifiers, using Ant Colony Optimisation (ACO). First, we introduce a new medoid-based method for ACO-based clustering in the Ant-ClustBMB algorithm to learn BMNs. Both this algorithm and our previously introduced Ant-ClustBIB for instance-based clustering have their effectiveness empirically compared in the context of the “cluster-then-learn” approach, in which the ACO clustering step completes before learning the local BN classifiers. Second, we propose a novel “cluster-with-learn” approach, in which the ACO meta-heuristic performs the clustering and the BMN learning in a synergistic fashion. Third, we adopt the latter approach in two new ACO algorithms: ACO-ClustBIB, using the instance-based method, and ACO-ClustBMB, using the medoid-based method. Empirical results are obtained on 30 UCI datasets.
Salama, K. M. and Freitas, A. A. (2014) “ABC-Miner+: constructing Markov blanket classifiers with ant colony algorithms”, Memetic Computing. Springer, pp. 183-206. doi: 10.1007/s12293-014-0138-6.
ABC-Miner is a Bayesian classification algorithm based on the Ant colony optimization (ACO) meta-heuristic. The algorithm learns Bayesian network Augmented Naïve-Bayes (BAN) classifiers, where the class node is the parent of all the nodes representing the input variables. However, this assumes the existence of a dependency relationship between the class variable and all the input variables, and this relationship is always a type of “causal” (rather than “effect”) relationship, which restricts the flexibility of the algorithm to learn. In this paper, we extended the ABC-Miner algorithm to be able to learn the Markov blanket of the class variable. Such a produced model has a more flexible Bayesian network classifier structure, where it is not necessary to have a (direct) dependency relationship between the class variable and each of the input variables, and the dependency between the class and the input variables varies from “causal” to “effect” relationships. In this context, we propose two algorithms: ABC-Miner+1, in which the dependency relationships between the class and the input variables are defined in a separate phase before the dependency relationships among the input variables are defined, and ABC-Miner+2, in which the two types of dependency relationships in the Markov blanket classifier are discovered in a single integrated process. Empirical evaluations on 33 UCI benchmark datasets show that our extended algorithms outperform the original version in terms of predictive accuracy, model size and computational time. Moreover, they have shown a very competitive performance against other well-known classification algorithms in the literature.
Freitas, A. A. (2014) “Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms”, Genetic Programming and Evolvable Machines. Springer, pp. 3-35. doi: 10.1007/s10710-013-9186-9.
The fields of machine meta-learning and hyper-heuristic optimisation have developed mostly independently of each other, although evolutionary algorithms (particularly genetic programming) have recently played an important role in the development of both fields. Recent work in both fields shares a common goal, that of automating as much of the algorithm design process as possible. In this paper we first provide a historical perspective on automated algorithm design, and then we discuss similarities and differences between meta-learning in the field of supervised machine learning (classification) and hyper-heuristics in the field of optimisation. This discussion focuses on the dimensions of the problem space, the algorithm space and the performance measure, as well as clarifying important issues related to different levels of automation and generality in both fields. We also discuss important research directions, challenges and foundational issues in meta-learning and hyper-heuristic research. It is important to emphasize that this paper is not a survey, as several surveys on the areas of meta-learning and hyper-heuristics (separately) have been previously published. The main contribution of the paper is to contrast meta-learning and hyper-heuristics methods and concepts, in order to promote awareness and cross-fertilisation of ideas across the (by and large, non-overlapping) different communities of meta-learning and hyper-heuristic researchers. We hope that this cross-fertilisation of ideas can inspire interesting new research in both fields and in the new emerging research area which consists of integrating those fields.
Basgalupp, M. P., Barros, R. C., de Carvalho, A. C. and Freitas, A. A. (2014) “Evolving Decision Trees with Beam Search-based Initialization and Lexicographic Multi-Objective Evaluation”, Information Sciences, pp. 160-181. doi: 10.1016/j.ins.2013.07.025.
Decision tree induction algorithms represent one of the most popular techniques for dealing with classification problems. However, traditional decision-tree induction algorithms implement a greedy approach for node splitting that is inherently susceptible to local optima convergence. Evolutionary algorithms can avoid the problems associated with a greedy search and have been successfully employed to the induction of decision trees. Previously, we proposed a lexicographic multi-objective genetic algorithm for decision-tree induction, named LEGAL-Tree. In this work, we propose extending this approach substantially, particularly w.r.t. two important evolutionary aspects: the initialization of the population and the fitness function. We carry out a comprehensive set of experiments to validate our extended algorithm. The experimental results suggest that it is able to outperform both traditional algorithms for decision-tree induction and another evolutionary algorithm in a variety of application domains.
Paes, B., Plastino, A. and Freitas, A. A. (2014) “Exploring attribute selection in hierarchical classification.”, Journal of Information and Data Management. Sociedade Brasileira de Computacao, pp. 124-133.
In the domain of many classification problems, classes have relations of dependency that are represented in hierarchical structures. These problems are known as hierarchical classification problems. Methods based on different approaches, considering hierarchical relations in different ways, have been proposed to solve them, in the attempt to achieve better predictive performance. In this work, we explore attribute selection techniques in conjunction with hierarchical classifiers from different categories, with the goal of improving their respective performances. Computational experiments, made with 18 hierarchical datasets, have indicated that the adopted classifiers attain better predictive accuracy when the most relevant attributes are considered in their construction.
Barros, R., Basgalupp, M., Freitas, A. A. and de Carvalho, A. (2013) “Evolutionary design of decision-tree algorithms tailored to microarray gene expression data sets”, IEEE Transactions on Evolutionary Computation. IEEE, pp. 873-892. doi: 10.1109/TEVC.2013.2291813.
Decision-tree induction algorithms are widely used in machine learning applications in which the goal is to extract knowledge from data and present it in a graphically intuitive way. The most successful strategy for inducing decision trees is the greedy top-down recursive approach, which has been continuously improved by researchers over the past 40 years. In this paper, we propose a paradigm shift in the research of decision trees: instead of proposing a new manually designed method for inducing decision trees, we propose automatically designing decision-tree induction algorithms tailored to a specific type of classification data set (or application domain). Following recent breakthroughs in the automatic design of machine learning algorithms, we propose a hyper-heuristic evolutionary algorithm called hyper-heuristic evolutionary algorithm for designing decision-tree algorithms (HEAD-DT) that evolves design components of top-down decision-tree induction algorithms. By the end of the evolution, we expect HEAD-DT to generate a new and possibly better decision-tree algorithm for a given application domain. We perform extensive experiments in 35 real-world microarray gene expression data sets to assess the performance of HEAD-DT, and compare it with very well known decision-tree algorithms such as C4.5, CART, and REPTree. Results show that HEAD-DT is capable of generating algorithms that significantly outperform the baseline manually designed decision-tree algorithms regarding predictive accuracy and F-measure.
Salama, K. M. and Freitas, A. A. (2013) “Learning Bayesian network classifiers using ant colony optimization”, Swarm Intelligence, pp. 229-254. doi: 10.1007/s11721-013-0087-6.
Bayesian networks are knowledge representation tools that model the (in)dependency relationships among variables for probabilistic reasoning. Classification with Bayesian networks aims to compute the class with the highest probability given a case. This special kind is referred to as Bayesian network classifiers. Since learning the Bayesian network structure from a dataset can be viewed as an optimization problem, heuristic search algorithms may be applied to build high-quality networks in medium- or large-scale problems, as exhaustive search is often feasible only for small problems. In this paper, we present our new algorithm, ABC-Miner, and propose several extensions to it. ABC-Miner uses ant colony optimization for learning the structure of Bayesian network classifiers. We report extended computational results comparing the performance of our algorithm with eight other classification algorithms, namely six variations of well-known Bayesian network classifiers, cAnt-Miner for discovering classification rules and a support vector machine algorithm.
Freitas, A. A. (2013) “Comprehensible classification models - a position paper”, ACM SIGKDD Explorations. ACM, pp. 1-10. Available at: http://www.kdd.org/explorations.
The vast majority of the literature evaluates the performance of classification models using only the criterion of predictive accuracy. This paper reviews the case for considering also the comprehensibility (interpretability) of classification models, and discusses the interpretability of five types of classification models, namely decision trees, classification rules, decision tables, nearest neighbors and Bayesian network classifiers. We discuss both interpretability issues which are specific to each of those model types and more generic interpretability issues, namely the drawbacks of using model size as the only criterion to evaluate the comprehensibility of a model, and the use of monotonicity constraints to improve the comprehensibility and acceptance of classification models by users.
Otero, F. E., Freitas, A. A. and Johnson, C. G. (2013) “A new sequential covering strategy for inducing classification rules with ant colony algorithms”, IEEE Transactions on Evolutionary Computation. IEEE Press, pp. 64-76. doi: 10.1109/TEVC.2012.2185846.
Ant colony optimization (ACO) algorithms have been successfully applied to discover a list of classification rules. In general, these algorithms follow a sequential covering strategy, where a single rule is discovered at each iteration of the algorithm in order to build a list of rules. The sequential covering strategy has the drawback of not coping with the problem of rule interaction, i.e., the outcome of a rule affects the rules that can be discovered subsequently since the search space is modified due to the removal of examples covered by previous rules. This paper proposes a new sequential covering strategy for ACO classification algorithms to mitigate the problem of rule interaction, where the order of the rules is implicitly encoded as pheromone values and the search is guided by the quality of a candidate list of rules. Our experiments using 18 publicly available data sets show that the predictive accuracy obtained by a new ACO classification algorithm implementing the proposed sequential covering strategy is statistically significantly higher than the predictive accuracy of state-of-the-art rule induction classification algorithms.
Salama, K. M., Abdelbar, A. M., Otero, F. E. and Freitas, A. A. (2013) “Utilizing multiple pheromones in an ant-based algorithm for continuous-attribute classification rule discovery.”, Applied Soft Computing. Elsevier Science, pp. 667-675. doi: 10.1016/j.asoc.2012.07.026.
The cAnt-Miner algorithm is an Ant Colony Optimization (ACO) based technique for classification rule discovery in problem domains which include continuous attributes. In this paper, we propose several extensions to cAnt- Miner. The main extension is based on the use of multiple pheromone types, one for each class value to be predicted. In the proposed ?cAnt-Miner algorithm, an ant first selects a class value to be the consequent of a rule and the terms in the antecedent are selected based on the pheromone levels of the selected class value; pheromone update occurs on the corresponding pheromone type of the class value. The pre-selection of a class value also allows the use of more precise measures for the heuristic function and the dynamic discretization of continuous attributes, and further allows for the use of a rule quality measure that directly takes into account the confidence of the rule. Experimental results on 20 benchmark datasets show that our proposed extension improves classification accuracy to a statistically significant extent compared to cAnt-Miner, and has classification accuracy similar to the well-known Ripper and PART rule induction algorithms.
Newby, D., Freitas, A. A. and Ghafourian, T. (2013) “Coping with unbalanced class data sets in oral absorption models”, Journal of Chemical Information Modeling. ACS, pp. 461-474. doi: 10.1021/ci300348u.
Barros, R. C., Basgalupp, M. P., Freitas, A. A. and de Carvalho, A. C. (2013) “Automatic Design of Decision-Tree Algorithms with Evolutionary Algorithms”, Evolutionary Computation. MIT Press, pp. 659-684. doi: 10.1162/EVCO_a_00101.
This study reports the empirical analysis of a hyper-heuristic evolutionary algorithm that is capable of automatically designing top-down decision-tree induction algorithms. Top-down decision-tree algorithms are of great importance, considering their ability to provide an intuitive and accurate knowledge representation for classification problems. The automatic design of these algorithms seems timely, given the large literature accumulated over more than 40 years of research in the manual design of decision-tree induction algorithms. The proposed hyper-heuristic evolutionary algorithm, HEAD-DT, is extensively tested using 20 public UCI datasets and 10 microarray gene expression datasets. The algorithms automatically designed by HEAD-DT are compared with traditional decision-tree induction algorithms, such as C4.5 and CART. Experimental results show that HEAD-DT is capable of generating algorithms which are significantly more accurate than C4.5 and CART.
Newby, D., Freitas, A. A. and Ghafourian, T. (2013) “Pre-processing feature selection for improved C&RT models for oral absorption”, Journal of Chemical Information and Modeling. ACS, pp. 2730-2742. doi: 10.1021/ci400378j.
There are currently thousands of molecular descriptors that can be calculated to represent a chemical compound. Utilizing all molecular descriptors in Quantitative Structure–Activity Relationships (QSAR) modeling can result in overfitting, decreased interpretability, and thus reduced model performance. Feature selection methods can overcome some of these problems by drastically reducing the number of molecular descriptors and selecting the molecular descriptors relevant to the property being predicted. In particular, decision trees such as C&RT, although they have an embedded feature selection algorithm, can be inadequate since further down the tree there are fewer compounds available for descriptor selection, and therefore descriptors may be selected which are not optimal. In this work we compare two broad approaches for feature selection: (1) a “two-stage” feature selection procedure, where a pre-processing feature selection method selects a subset of descriptors, and then classification and regression trees (C&RT) selects descriptors from this subset to build a decision tree; (2) a “one-stage” approach where C&RT is used as the only feature selection technique. These methods were applied in order to improve prediction accuracy of QSAR models for oral absorption. Additionally, this work utilizes misclassification costs in model building to overcome the problem of the biased oral absorption data sets with more highly absorbed than poorly absorbed compounds. In most cases the two-stage feature selection with pre-processing approach had higher model accuracy compared with the one-stage approach. Using the top 20 molecular descriptors from the random forest predictor importance method gave the most accurate C&RT classification model. The molecular descriptors selected by the five filter feature selection methods have been compared in relation to oral absorption. In conclusion, the use of filter pre-processing feature selection methods and misclassification costs produce models with better interpretability and predictability for the prediction of oral absorption.
Ghafourian, T., Freitas, A. A. and Newby, D. (2012) “The impact of training set data distributions for modelling of passive intestinal absorption.”, International Journal of Pharmaceutics. Elsevier, pp. 711-720. doi: 10.1016/j.ijpharm.2012.07.041.
Otero, F. E., Freitas, A. A. and Johnson, C. G. (2012) “Inducing decision trees with an ant colony optimization algorithm”, Applied Soft Computing, pp. 3615-3626. doi: 10.1016/j.asoc.2012.05.028.
Decision trees have been widely used in data mining and machine learning as a comprehensible knowledge representation. While ant colony optimization (ACO) algorithms have been successfully applied to extract classification rules, decision tree induction with ACO algorithms remains an almost unexplored research area. In this paper we propose a novel ACO algorithm to induce decision trees, combining commonly used strategies from both traditional decision tree induction algorithms and ACO. The proposed algorithm is compared against three decision tree induction algorithms, namely C4.5, CART and cACDT, in 22 publicly available data sets. The results show that the predictive accuracy of the proposed algorithm is statistically significantly higher than the accuracy of both C4.5 and CART, which are well-known conventional algorithms for decision tree induction, and the accuracy of the ACO-based cACDT decision tree algorithm.
Barros, R. C., Basgalupp, M. P., de Carvalho, A. C. and Freitas, A. A. (2012) “A survey of evolutionary algorithms for decision-tree induction”, IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews. IEEE, pp. 291-312. doi: 10.1109/TSMCC.2011.2157494.
Paes, B. C., Plastino, A. and Freitas, A. A. (2012) “Improving local per level hierarchical classification.”, Journal of Information and Data Management. Sociedade Brasileira de Computacao, pp. 394-409.
Salama, K. M., Abdelbar, A. M. and Freitas, A. A. (2011) “Multiple Pheromone Types and Other Extensions to the Ant-Miner Classification Rule Discovery Algorithm.”, Swarm Intelligence. Springer, pp. 182-196. doi: 10.1007/s11721-011-0057-9.
Silla Jr, C. N. and Freitas, A. A. (2011) “Selecting different protein representations and classification algorithms in hierarchical protein function prediction”, Intelligent Data Analysis. IOS Press, pp. 182-196. doi: 10.3233/IDA-2011-0505.
Cerri, R., de Carvalho, A. C. and Freitas, A. A. (2011) “Adapting non-hierarchical multilabel classification methods for hierarchical multilabel classification”, Intelligent Data Analysis. IOS Press, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2011/3191.
Pereira, R. B., Plastino, A., Zadrozny, B., Merschmann, L. H. de C. and Freitas, A. A. (2011) “Improving lazy attribute selection”, Journal of Information and Data Management. Sociedade Brasileira de Computacao, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2011/3170.
Tsunoda, D. F., Freitas, A. A. and Lopes, H. S. (2011) “A genetic programming method for protein motif discovery and protein classification”, Soft Computing. Springer, pp. 182-196. doi: 10.1007/s00500-010-0624-9.
Pereira, R. B., Plastino, A., Zadrozny, B., Merschmann, L. H. de C. and Freitas, A. A. (2011) “Lazy Attribute selection: Choosing attributes at classification time.”, Intelligent Data Analysis. IOS Press, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2011/3158.
Davies, M. N., Gloriam, D. E., Secker, A. D., Freitas, A. A., Timmis, J. and Flower, D. R. (2011) “Present perspectives on the automated classification of the G-Protein Coupled Receptors (GPCRs) at the Protein Sequence Level”, Current Topics in Medicinal Chemistry. Bentham Science Publishers, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2011/3169.
Freitas, A. A. and de Magalhaes, J. P. (2011) “A review and appraisal of the DNA damage theory of ageing”, Mutation Research. Elsevier, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2011/3148.
Plastino, A., Fuchshuber, R., Martins, S. de L., Freitas, A. A. and Salhi, S. (2011) “A hybrid data mining metaheuristic for the p-median problem”, Statistical Analysis & Data Mining Journal. Wiley Periodicals, pp. 313-335. doi: 10.1002/sam.10116.
Metaheuristics represent an important class of techniques to solve, approximately, hard combinatorial optimization problems for which the use of exact methods is impractical. In this work, we propose a hybrid version of the Greedy Randomized Adaptive Search Procedures (GRASP) metaheuristic, which incorporates a data mining process, to solve the p-median problem. We believe that patterns obtained by a data mining technique, from a set of suboptimal solutions of a combinatorial optimization problem, can be used to guide metaheuristic procedures in the search for better solutions. Traditional GRASP is an iterative metaheuristic which returns the best solution reached over all iterations. In the hybrid GRASP proposal, after executing a significant number of iterations, the data mining process extracts patterns from an elite set of suboptimal solutions for the p-median problem. These patterns present characteristics of near optimal solutions and can be used to guide the following GRASP iterations in the search through the combinatorial solution space. Computational experiments, comparing traditional GRASP and different data mining hybrid proposals for the p-median problem, showed that employing patterns mined from an elite set of suboptimal solutions made the hybrid GRASP find better results. Besides, the conducted experiments also evidenced that incorporating a data mining technique into a metaheuristic accelerated the process of finding near optimal and optimal solutions. © 2011 Wiley Periodicals, Inc. Statistical Analysis and Data Mining 2011
Freitas, A. A., Vasieva, O. and de Magalhaes, J. P. (2011) “A data mining approach for classifying DNA repair genes into ageing-related or non-ageing-related”, BMC Genomics, pp. 182-196. doi: 10.1186/1471-2164-12-27.
Silla Jr, C. N. and Freitas, A. A. (2011) “A survey of hierarchical classification across different application domains”, Data Mining and Knowledge Discovery, pp. 182-196. doi: 10.1007/978-3-642-01799-5â??.
Otero, F. E., Freitas, A. A. and Johnson, C. G. (2010) “A hierarchical multi-label classification ant colony algorithm for protein function prediction”, Memetic Computing. Springer, pp. 165-181. doi: 10.1007/s12293-010-0045-4.
This paper proposes a novel ant colony optimisation (ACO) algorithm tailored for the hierarchical multi-label classification problem of protein function prediction. This problem is a very active research field, given the large increase in the number of uncharacterised proteins available for analysis and the importance of determining their functions in order to improve the current biological knowledge. Since it is known that a protein can perform more than one function and many protein functional-definition schemes are organised in a hierarchical structure, the classification problem in this case is an instance of a hierarchical multi-label problem. In this type of problem, each example may belong to multiple class labels and class labels are organised in a hierarchical structure—either a tree or a directed acyclic graph structure. It presents a more complex problem than conventional flat classification, given that the classification algorithm has to take into account hierarchical relationships between class labels and be able to predict multiple class labels for the same example. The proposed ACO algorithm discovers an ordered list of hierarchical multi-label classification rules. It is evaluated on sixteen challenging bioinformatics data sets involving hundreds or thousands of class labels to be predicted and compared against state-of-the-art decision tree induction algorithms for hierarchical multi-label classification.
La Torre, A., Pena, J., Muelas, S. and Freitas, A. A. (2010) “Learning hybridization strategies in evolutionary algorithms”, Intelligent Data Analysis. IOS Press, pp. 182-196. doi: 10.3233/IDA-2010-0424.
Freitas, A. A., Wieser, D. C. and Apweiler, R. (2010) “On the importance of comprehensible classification models for protein function prediction”, IEEE/ACM Transactions on Computational Biology and Bioinformatics, pp. 182-196. doi: 10.1109/TCBB.2008.47.
Secker, A. D., Davies, M. N., Freitas, A. A., Clark, E., Timmis, J. and Flower, D. R. (2010) “Hierarchical classification of G-Protein-Coupled Receptors with data-driven selection of attributes and classifiers”, International Journal of Data Mining and Bioinformatics, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2010/3111.
Pappa, G. L. and Freitas, A. A. (2009) “Evolving rule induction algorithms with multi-objective grammar-based genetic programming”, Knowledge and Information Systems. Springer, pp. 283-309. doi: 10.1007/s10115-008-0171-1.
Multi-objective optimization has played a major role in solving problems where two or more conflicting objectives need to be simultaneously optimized. This paper presents a Multi-Objective grammar-based genetic programming (MOGGP) system that automatically evolves complete rule induction algorithms, which in turn produce both accurate and compact rule models. The system was compared with a single objective GGP and three other rule induction algorithms. In total, 20 UCI data sets were used to generate and test generic rule induction algorithms, which can be now applied to any classification data set. Experiments showed that, in general, the proposed MOGGP finds rule induction algorithms with competitive predictive accuracies and more compact models than the algorithms it was compared with.
Secker, A. D., Davies, M. N., Freitas, A. A., Timmis, J., Clark, E. and Flower, D. R. (2009) “An artificial immune system for clustering amino acids in the context of protein function classification”, Journal of Mathematical Modelling and Algorithms. Springer, pp. 103-123. doi: 10.1007/s10852-009-9107-3.
This paper addresses the classification task of data mining (a form of supervised learning) in the context of an important bioinformatics problem, namely the prediction of protein functions. This problem is cast as a hierarchical classification problem. The protein functions to be predicted correspond to classes that are arranged in a hierarchical structure (this takes the form of a class tree). The main contribution of this paper is to propose a new Artificial Immune System that creates a new representation for proteins, in order to maximize the predictive accuracy of a hierarchical classification algorithm applied to the corresponding protein function prediction problem.
Pappa, G. L. and Freitas, A. A. (2009) “Automatically evolving rule induction algorithms tailored to the prediction of postsynaptic activity in proteins”, Intelligent Data Analysis. IOS Press, pp. 243-259. doi: 10.3233/IDA-2009-0366.
It is well-known that no classification algorithm is the best in all application domains. The conventional approach for coping with this problem consists of trying to select the best classification algorithm for the target application domain. We propose a refreshing departure from this approach, consisting of automatically creating a rule induction algorithm tailored to the target application domain. This work proposes a grammar-based genetic programming (GGP) system to perform "algorithm construction". The GGP is used to build a complete rule induction algorithm tailored to 5 well-known UCI data sets and a protein data set, where the goal is to predict whether or not a protein presents postsynaptic activity. The results show that the rule induction algorithms automatically constructed by the GGP are competitive with well-known human-designed rule induction algorithms. Moreover, in the postsynaptic case study, the GGP was more successful than the human-designed algorithms in discovering accurate rules predicting the minority class - whose prediction is more difficult and tends to be more important to the user than the prediction of the majority class
Hruschka, E. R., Campello, R. J. G. B., Freitas, A. A. and de Carvalho, A. C. (2009) “A survey of evolutionary algorithms for clustering”, IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews. IEEE Press, pp. 133-155. doi: 10.1109/TSMCC.2008.2007252.
This paper presents a survey of evolutionary algorithms designed for clustering tasks. It tries to reflect the profile of this area by focusing more on those subjects that have been given more importance in the literature. In this context, most of the paper is devoted to partitional algorithms that look for hard clusterings of data, though overlapping (i.e., soft and fuzzy) approaches are also covered in the paper. The paper is original in what concerns two main aspects. Firsts it provides an up-to-date overview that is fully devoted to evolutionary algorithms for clustering, is not limited to any particular kind of evolutionary approach, and comprises advanced topics like multiobjective and ensemble-based evolutionary clustering. Second, it provides a taxonomy that highlights some very important aspects in the context of evolutionary data clustering, namely, fixed or variable number of clusters, cluster-oriented or nonoriented operators, context-sensitive or context-insensitive operators, guided or unguided operators, binary, integer, or real encodings, centroid-based, medoid-based, label-based, tree-based, or graph-based representations, among others. A number of references are provided that describe applications of evolutionary algorithms for clustering in different domains, such as image processing, computer security, and bioinformatics. The paper ends by addressing some important issues and open questions that can be subject of future research.
Holden, N. and Freitas, A. A. (2009) “Hierarchical classification of protein function with ensembles of rules and particle swarm optimisation”, Soft Computing. Springer Berlin, pp. 259-272. doi: 10.1007/s00500-008-0321-0.
This paper focuses on hierarchical classification problems where the classes to be predicted are organized in the form of a tree. The standard top-down divide and conquer approach for hierarchical classification consists of building a hierarchy of classifiers where a classifier is built for each internal (non-leaf) node in the class tree. Each classifier discriminates only between its child classes. After the tree of classifiers is built, the system uses them to classify test examples one class level at a time, so that when the example is assigned a class at a given level, only the child classes need to be considered at the next level. This approach has the drawback that, if a test example is misclassified at a certain class level, it will be misclassified at deeper levels too. In this paper we propose hierarchical classification methods to mitigate this drawback. More precisely, we propose a method called hierarchical ensemble of hierarchical rule sets (HEHRS), where different ensembles are built at different levels in the class tree and each ensemble consists of different rule sets built from training examples at different levels of the class tree. We also use a particle swarm optimisation (PSO) algorithm to optimise the rule weights used by HEHRS to combine the predictions of different rules into a class to be assigned to a given test example. In addition, we propose a variant of a method to mitigate the aforementioned drawback of top-down classification. These three types of methods are compared against the standard top-down hierarchical classification method in six challenging bioinformatics datasets, involving the prediction of protein function. Overall HEHRS with the rule weights optimised by the PSO algorithm obtains the best predictive accuracy out of the four types of hierarchical classification method
Basgalupp, M. P., de Carvalho, A. C., Barros, R. C., Ruiz, D. D. and Freitas, A. A. (2009) “Lexicographic multi-objective evolutionary induction of decision trees”, International Journal of Bio-Inspired Computation, pp. 105-117. doi: 10.1504/IJBIC.2009.022779.
Among the several tasks that evolutionary algorithms have successfully employed, the induction of classification rules and decision trees has been shown to be a relevant approach for several application domains. Decision tree induction algorithms represent one of the most popular techniques for dealing with classification problems. However, conventionally used decision trees induction algorithms present limitations due to the strategy they usually implement: recursive top-down data partitioning through a greedy split evaluation. The main problem with this strategy is quality loss during the partitioning process, which can lead to statistically insignificant rules. In this paper, we propose a new GA-based algorithm for decision tree induction. The proposed algorithm aims to prevent the greedy strategy and to avoid converging to local optima. For such, it is based on a lexicographic multi-objective approach. In order to evaluate the proposed algorithm, it is compared with a well-known and frequently used decision tree induction algorithm using different public datasets. According to the experimental results, the proposed algorithm is able to avoid the previously described problems, reporting accuracy gains. Even more important, the proposed algorithm induced models with a significantly reduction in the complexity considering tree sizes.
Davies, M. N., Secker, A. D., Freitas, A. A., Timmis, J., Clark, E. and Flower, D. R. (2008) “Alignment-independent techniques for protein classification”, Current Proteomics, pp. 217-223.
Ghosh, S., Froebrich, D. and Freitas, A. A. (2008) “Robust autonomous detection of the defective pixels in detectors using a probabilistic technique”, Applied Optics. Optics Society of America, pp. 6904-6924.
Detection of defective pixels in solid-state detectors/sensor arrays has received limited research attention. Few approaches currently exist lior detecting the defective pixels using real images captured with cameras equipped with such detectors, and they are ad hoe and limited in their applicability In this paper, we present a probabilistic novel integrated technique for autonomously detecting the defective pixels in image sensor arrays. It can be applied to images containing rich scene information, captured with any digital camera equipped with a solid-state detector, to detect diffierent kinds of defective pixels in the detector. We apply our technique to the detection of various defective pixels in an experimental camera equipped with a charge coupled device (CCD) array and two out of the four HgCdTe detectors of the UKIRT's wide field camera (WFCAM) used for infrared (IR) astronomy [Astron. Astrophys. 467, 777-784 (2007)].
Iqbal, M., Freitas, A. A., Johnson, C. G. and Vergassola, M. (2008) “Message-passing algorithms for the prediction of protein domain interactions from protein?protein interaction data”, Bioinformatics. Oxford University Press, pp. 2064-2070. doi: 10.1093/bioinformatics/btn366.
Motivation: Cellular processes often hinge upon specific interactions among proteins, and knowledge of these processes at a system level constitutes a major goal of proteomics. In particular, a greater understanding of protein-protein interactions can be gained via a more detailed investigation of the protein domain interactions that mediate the interactions of proteins. Existing high-throughput experimental techniques assay protein-protein interactions, yet they do not provide any direct information on the interactions among domains. Inferences concerning the latter can be made by analysis of the domain composition of a set of proteins and their interaction map. This inference problem is non-trivial, however, due to the high level of noise generally present in experimental data concerning protein-protein interactions. This noise leads to contradictions, i.e. the impossibility of having a pattern of domain interactions compatible with the protein-protein interaction map. Results: We formulate the problem of prediction of protein domain interactions in a form that lends itself to the application of belief propagation, a powerful algorithm for such inference problems, which is based on message passing. The input to our algorithm is an interaction map among a set of proteins, and a set of domain assignments to the relevant proteins. The output is a list of probabilities of interaction between each pair of domains. Our method is able to effectively cope with errors in the protein-protein interaction dataset and systematically resolve contradictions. We applied the method to a dataset concerning the budding yeast Saccharomyces cerevisiae and tested the quality of our predictions by cross-validation on this dataset, by comparison with existing computational predictions, and finally with experimentally available domain interactions. Results compare favourably to those by existing algorithms. Availability: A C language implementation of the algorithm is available upon request.
Davies, M. N., Secker, A. D., Freitas, A. A., Clark, E., Timmis, J. and Flower, D. R. (2008) “Optimizing amino acid groupings for GPCR classification”, Bioinformatics. Oxford University Press, England, pp. 1980-1986. doi: 10.1093/bioinformatics/btn382.
Motivation: There is much interest in reducing the complexity inherent in the representation of the 20 standard amino acids within bioinformatics algorithms by developing a so-called reduced alphabet. Although there is no universally applicable residue grouping, there are numerous physiochemical criteria upon which one can base groupings. Local descriptors are a form of alignment-free analysis, the efficiency of which is dependent upon the correct selection of amino acid groupings. Results: Within the context of G-protein coupled receptor (GPCR) classification, an optimization algorithm was developed, which was able to identify the most efficient grouping when used to generate local descriptors. The algorithm was inspired by the relatively new computational intelligence paradigm of artificial immune systems. A number of amino acid groupings produced by this algorithm were evaluated with respect to their ability to generate local descriptors capable of providing an accurate classification algorithm for GPCRs.
Davies, M. N., Secker, A. D., Halling-Brown, M., Moss, D. S., Freitas, A. A., Timmis, J., Clark, E. and Flower, D. R. (2008) “GPCRTree: online hierarchical classification of GPCR function”, BMC Research Notes, p. 5 pages. doi: 10.1186/1756-0500-1-67.
G protein-coupled receptors (GPCRs) play important physiological roles transducing extracellular signals into intracellular responses. Approximately 50% of all marketed drugs target a GPCR. There remains considerable interest in effectively predicting the function of a GPCR from its primary sequence. FINDINGS: Using techniques drawn from data mining and proteochemometrics, an alignment-free approach to GPCR classification has been devised. It uses a simple representation of a protein's physical properties. GPCRTree, a publicly-available internet server, implements an algorithm that classifies GPCRs at the class, sub-family and sub-subfamily level. CONCLUSION: A selective top-down classifier was developed which assigns sequences within a GPCR hierarchy. Compared to other publicly available GPCR prediction servers, GPCRTree is considerably more accurate at every level of classification.
Poli, R., Kennedy, J., Blackwell, T. and Freitas, A. A. (2008) “Special Issue Editorial: Particle Swarms: the Second Decade”, Journal of Artificial Evolution and Applications. Hindawi Publishing Corporation, p. 3 pages. doi: 10.1155/2008/108972.
Correa, E. S., Freitas, A. A. and Johnson, C. G. (2008) “Particle swarm for attribute selection in Bayesian classification: an application to protein function prediction”, Journal of Artificial Evolution and Applications. Hindawi Publishing Corporation, p. 12 pages. doi: 10.1155/2008/876746.
Holden, N. and Freitas, A. A. (2008) “A hybrid PSO/ACO algorithm for discovering classification rules in data mining”, Journal of Artificial Evolution and Applications. Hindawi Publishing Corporation, p. 11 pages. doi: 10.1155/2008/316145.
We have previously proposed a hybrid particle swarm optimisation/ant colony optimisation (PSO/ACO) algorithm for the discovery of classification rules. Unlike a conventional PSO algorithm, this hybrid algorithm can directly cope with nominal attributes, without converting nominal values into binary numbers in a preprocessing phase. PSO/ACO2 also directly deals with both continuous and nominal attribute values, a feature that current PSO and ACO rule induction algorithms lack. We evaluate the new version of the PSO/ACO algorithm (PSO/ACO2) in 27 public-domain, real-world data sets often used to benchmark the performance of classification algorithms. We compare the PSO/ACO2 algorithm to an industry standard algorithm PART and compare a reduced version of our PSO/ACO2 algorithm, coping only with continuous data, to our new classification algorithm for continuous data based on differential evolution. The results show that PSO/ACO2 is very competitive in terms of accuracy to PART and that PSO/ACO2 produces significantly simpler (smaller) rule sets, a desirable result in data mining—where the goal is to discover knowledge that is not only accurate but also comprehensible to the user. The results also show that the reduced PSO version for continuous attributes provides a slight increase in accuracy when compared to the differential evolution variant.
Secker, A. D., Freitas, A. A. and Timmis, J. (2008) “AISIID: An artificial immune system for interesting information discovery on the web”, Applied Soft Computing. Elsevier Science, pp. 885-905. doi: 10.1016/j.asoc.2007.07.007.
There exist numerous systems for mining the web in search of relevant information but few exist for the discovery of interesting information. The discovery of interesting information is an advance on basic text mining in that it aims to identify text that is novel, unexpected or surprising to a user, whilst still being relevant. This article investigates the use of artificial immune systems (AIS) applied to discovery of interesting information. AIS are thought to confer the adaptability and learning required for this task. Artificial immune system for interesting information discovery (AISIID) is described in some detail, then an evaluative study is undertaken involving the subjective evaluation of the results by users. AISIID is found to discover pages rated more interesting by users than a comparative system.
Davies, M. N., Secker, A. D., Freitas, A. A., Mendao, M., Timmis, J. and Flower, D. R. (2007) “On the hierarchical classification of G Protein-Coupled Receptors”, Bioinformatics. Oxford University Press, pp. 3113-3118. doi: 10.1093/bioinformatics/btm506.
Motivation: G protein-coupled receptors (GPCRs) play an important role in many physiological systems by transducing an extracellular signal into an intracellular response. Over 50% of all marketed drugs are targeted towards a GPCR. There is considerable interest in developing an algorithm that could effectively predict the function of a GPCR from its primary sequence. Such an algorithm is useful not only in identifying novel GPCR sequences but in characterizing the interrelationships between known GPCRs. Results: An alignment-free approach to GPCR classification has been developed using techniques drawn from data mining and proteochemometrics. A dataset of over 8000 sequences was constructed to train the algorithm. This represents one of the largest GPCR datasets currently available. A predictive algorithm was developed based upon the simplest reasonable numerical representation of the protein's physicochemical properties. A selective top-down approach was developed, which used a hierarchical classifier to assign sequences to subdivisions within the GPCR hierarchy. The predictive performance of the algorithm was assessed against several standard data mining classifiers and further validated against Support Vector Machine-based GPCR prediction servers. The selective top-down approach achieves significantly higher accuracy than standard data mining methods in almost all cases.
Secker, A. D., Davies, M. N., Freitas, A. A., Timmis, J., Mendao, M. and Flower, D. R. (2007) “An experimental comparison of classification algorithms for hierarchical prediction of protein function”, Expert Update (Magazine of the British Computer Society’s Specialist Group on AI), pp. 17-22.
Freitas, A. A. and Timmis, J. (2007) “Revisiting the Foundations of Artificial Immune Systems for Data Mining”, IEEE Transactions on Evolutionary Computation. IEEE Press, pp. 521-540. doi: 10.1109/TEVC.2006.884042.
This paper advocates a problem-oriented approach for the design of artificial immune.systems (AIS) for data mining. By problem-oriented approach we mean that, in real-world data mining applications the design of an AIS should take into account the characteristics of the data to be mined together with the application domain: the components of the AIS-such as its representation, affinity function, and immune process-should be tailored for the data and the application. This is in contrast with the majority of the literature, where a very generic AIS algorithm for data mining is developed and there is little or no concern in tailoring the components of the AIS for the data to be mined or the application domain. To support this problem-oriented approach, we provide an extensive critical review of the current literature on AIS for data mining, focusing on the data mining tasks of classification and anomaly detection. We discuss several important lessons to be taken from the natural immune system to design new AIS that are considerably more adaptive than current AIS. Finally, we conclude this paper with a summary of seven limitations of current AIS for data mining and ten suggested research directions.
Davies, M. N., Gloriam, D. E., Secker, A. D., Freitas, A. A., Mendao, M., Timmis, J. and Flower, D. R. (2007) “Proteomic applications of automated GPCR classification”, Proteomics. Wiley-VHC Verlag, pp. 2800-2814. doi: 10.1002/pmic.200700093.
The G-protein coupled receptor (GPCR) superfamily fulfils various metabolic functions and interacts with a diverse range of ligands. There is a lack of sequence similarity between the six classes that comprise the GPCR superfamily. Moreover, most novel GPCRs found have low sequence similarity to other family members which makes it difficult to infer properties from related receptors. Many different approaches have been taken towards developing efficient and accurate methods for GPCR classification, ranging from motif-based systems to machine learning as well as a variety of alignment-free techniques based on the physiochemical properties of their amino acid sequences. This review describes the inherent difficulties in developing a GPCR classification algorithm and includes techniques previously employed in this area.
Freitas, A. A. (2006) “Are we really discovering ’’interesting’’ knowledge from data?”, Expert Update (the BCS-SGAI Magazine). The British Computer Society, pp. 41-47.
This paper is a critical review of the literature on discovering comprehensible, interesting knowledge (or patterns) from data. The motivation for this review is that the majority of the literature focuses only on the problem of maximizing the accuracy of the discovered patterns, ignoring other important pattern-quality criteria that are user-oriented, such as comprehensibility and interestingness. The word “interesting” has been used with several different meanings in the data mining literature. In this paper interesting essentially means novel or surprising. Although comprehensibility and interestingness are considerably harder to measure in a formal way than accuracy, they seem very relevant criteria to be considered if we are serious about discovering knowledge that is not only accurate, but also useful for human decision making. The paper discusses both data-driven methods (based mainly on statistical properties of the patterns) and user-driven methods (which take into account the user’s background knowledge or believes) for discovering interesting knowledge. Data-driven methods are discussed in more detail because they are more common in the literature and are more controversial. The paper also suggests future research directions in the discovery of interesting knowledge.
Pappa, G. L., Baines, A. J. and Freitas, A. A. (2005) “Predicting Post-Synaptic Activity in Proteins with Data Mining”, Bioinformatics. Oxford University Press, pp. ii19-ii25. doi: 10.1093/bioinformatics/bti1102.
The bioinformatics problem being addressed in this paper is to predict whether or not a protein has post-synaptic activity. This problem is of great intrinsic interest because proteins with post-synaptic activities are connected with functioning of the nervous system. Indeed, many proteins having post-synaptic activity have been functionally characterized by biochemical, immunological and proteomic exercises. They represent a wide variety of proteins with functions in extracellular signal reception and propagation through intracellular apparatuses, cell adhesion molecules and scaffolding proteins that link them in a web. The challenge is to automatically discover features of the primary sequences of proteins that typically occur in proteins with post-synaptic activity but rarely (or never) occur in proteins without post-synaptic activity, and vice-versa. In this context, we used data mining to automatically discover classification rules that predict whether or not a protein has post-synaptic activity. The discovered rules were analysed with respect to their predictive accuracy (generalization ability) and with respect to their interestingness to biologists (in the sense of representing novel, unexpected knowledge).
Carvalho, D. R. and Freitas, A. A. (2005) “Evaluating six candidate solutions for the small-disjunct problem and choosing the best solution via meta-learning”, Artificial Intelligence Review. Springer, pp. 61-98.
A set of classification rules can be considered as a disjunction of rules, where each rule is a disjunct. A small disjunct is a rule covering a small number of examples. Small disjuncts are a serious problem for effective classification, because the small number of examples satisfying these rules makes their prediction unreliable and error-prone. This paper offers two main contributions to the research on small disjuncts. First, it investigates six candidate solutions (algorithms) for the problem of small disjuncts. Second, it reports the results of a meta-learning experiment, which produced meta-rules predicting which algorithm will tend to perform best for a given data set. The algorithms investigated in this paper belong to different machine learning paradigms and their hybrid combinations, as follows: two versions of a decision-tree (DT) induction algorithm; two versions of a hybrid DT/genetic algorithm (GA) method; one GA; one hybrid DT/instance-based learning (IBL) algorithm. Experiments with 22 data sets evaluated both the predictive accuracy and the simplicity of the discovered rule sets, with the following conclusions. If one wants to maximize predictive accuracy only, then the hybrid DT/IBL seems to be the best choice. On the other hand, if one wants to maximize both predictive accuracy and rule set simplicity - which is important in the context of data mining - then a hybrid DT/GA seems to be the best choice.
Freitas, A. A. (2004) “A critical review of multi-objective optimization in data mining: a position paper”, SIGKDD Explorations. ACM Press, pp. 77-86. doi: 10.1145/1046456.1046467.
This paper addresses the problem of how to evaluate the quality of a model built from the data in a multi-objective optimization scenario, where two or more quality criteria must be simultaneously optimized. A typical example is a scenario where one wants to maximize both the accuracy and the simplicity of a classification model or a candidate attribute subset in attribute selection. One reviews three very different approaches to cope with this problem, namely: (a) transforming the original multi-objective problem into a single-objective problem by using a weighted formula; (b) the lexicographical approach, where the objectives are ranked in order of priority; and (c) the Pareto approach, which consists of finding as many non-dominated solutions as possible and returning the set of non-dominated solutions to the user. One also presents a critical review of the case for and against each of these approaches. The general conclusions are that the weighted formula approach -- which is by far the most used in the data mining literature -- is to a large extent an ad-hoc approach for multi-objective optimization, whereas the lexicographic and the Pareto approach are more principled approaches, and therefore deserve more attention from the data mining community.
Carvalho, D. R. and Freitas, A. A. (2004) “A hybrid decision tree/genetic algorithm method for data mining”, Information Sciences. Elsevier, pp. 13-35. doi: 10.1016/j.ins.2003.03.013.
This paper addresses the well-known classification task of data mining, where the objective is to predict the class which an example belongs to. Discovered knowledge is expressed in the form of high-level, easy-to-interpret classification rules. In order to discover classification rules, we propose a hybrid decision tree/genetic algorithm method. The central idea of this hybrid method involves the concept of small disjuncts in data mining, as follows. In essence, a set of classification rules can be regarded as a logical disjunction of rules, so that each rule can be regarded as a disjunct. A small disjunct is a rule covering a small number of examples. Due to their nature, small disjuncts are error prone. However, although each small disjunct covers just a few examples, the set of all small disjuncts can cover a large number of examples, so that it is important to develop new approaches to cope with the problem of small disjuncts. In our hybrid approach, we have developed two genetic algorithms (GA) specifically designed for discovering rules covering examples belonging to small disjuncts, whereas a conventional decision tree algorithm is used to produce rules covering examples belonging to large disjuncts. We present results evaluating the performance of the hybrid method in 22 real-world data sets.
Romao, W., Freitas, A. A. and Gimenes, I. M. de S. (2004) “Discovering interesting knowledge from a science & technology database with a genetic algorithm”, Applied Soft Computing. Elsevier, pp. 121-137. doi: 10.1016/j.asoc.2003.10.002.
Data mining consists of extracting interesting knowledge from data. This paper addresses the discovery of knowledge in the form of prediction IF-THEN rules, which are a popular form of knowledge representation in data mining. In this context, we propose a genetic algorithm (GA) designed specifically to discover interesting fuzzy prediction rules. The GA searches for prediction rules that are interesting in the sense of being new and surprising for the user. This is done adapting a technique little exploited in the literature, which is based on user-defined general impressions (subjective knowledge). More precisely, a prediction rule is considered interesting (or surprising) to the extent that it represents knowledge that not only was previously unknown by the user but also contradicts his original believes. In addition, the use of fuzzy logic helps to improve the comprehensibility of the rules discovered by the GA. This is due to the use of linguistic terms that are natural for the user. A prototype was implemented and applied to a real-world science & technology database, containing data about the scientific production of researchers. The GA implemented in this prototype was evaluated by comparing it with the J4.8 algorithm, a variant of the well-known C4.5 algorithm. Experiments were carried out to evaluate both the predictive accuracy and the degree of interestingness (or surprisingness) of the rules discovered by both algorithms. The predictive accuracy obtained by the proposed GA was similar to the one obtained by J4.8, but the former, in general, discovered rules with fewer conditions. In addition it works with natural linguistic terms, which leads to the discovery of more comprehensible knowledge. The rules discovered by the proposed GA and the best rules discovered by J4.8 were shown to a user (a University Director) in an interview who evaluated the degree of interestingness (surprisingness) of the rules to him. In general the user considered the rules discovered by the GA much more interesting than the rules discovered by J4.8.
Correa, E. S., Steiner, M. T. A., Freitas, A. A. and Carnieri, C. (2004) “A genetic algorithm for solving a capacitated p-median problem”, Numerical Algorithms. Kluwer, pp. 373-388. doi: 10.1023/B:NUMA.0000021767.42899.31.
Facility-location problems have several applications, such as telecommunications, industrial transportation and distribution. One of the most well-known facility-location problems is the p-median problem. This work addresses an application of the capacitated p-median problem to a real-world problem. We propose a genetic algorithm (GA) to solve the capacitated p-median problem. The proposed GA uses not only conventional genetic operators, but also a new heuristic "hypermutation" operator suggested in this work. The proposed GA is compared with a tabu search algorithm.
Bojarczuk, C. C., Lopes, H. S., Freitas, A. A. and Michalkiewicz, E. L. (2004) “A constrained-syntax genetic programming system for discovering classification rules: application to medical data sets”, Artificial Intelligence in Medicine. Elsevier, pp. 27-48. doi: 10.1016/j.artmed.2003.06.001.
This paper proposes a new constrained-syntax genetic programming (GP) algorithm for discovering classification rules in medical data sets. The proposed GP contains several syntactic constraints to be enforced by the system using a disjunctive normal form representation, so that individuals represent valid rule sets that are easy to interpret. The GP is compared with C4.5, a well-known decision-tree-building algorithm, and with another GP that uses Boolean inputs (BGP), in five medical data sets: chest pain, Ljubljana breast cancer, dermatology, Wisconsin breast cancer, and pediatric adrenocortical tumor. For this last data set a new preprocessing step was devised for survival prediction. Computational experiments show that, overall, the GP algorithm obtained good results with respect to predictive accuracy and rule comprehensibility, by comparison with C4.5 and BGP.
Ghosh, A. and Freitas, A. A. (2003) “Guest Editorial: Data Mining and Knowledge Discovery with Evolutionary Algorithms”, IEEE Transactions on Evolutionary Computation. IEEE Press, pp. 517-518. doi: 10.1109/TEVC.2003.819653.
Carvalho, D. R. and Freitas, A. A. (2002) “A genetic algorithm for discovering small disjunct rules in data mining”, Applied Soft Computing. Elsevier, pp. 75-88. doi: 10.1016/S1568-4946(02)00031-5.
This paper addresses the well-known classification task of data mining, where the goal is to discover rules predicting the class of examples (records of a given dataset). In the context of data mining, small disjuncts are rules covering a small number of examples. Hence, these rules are usually error-prone, which contributes to a decrease in predictive accuracy. At first glance, this is not a serious problem, since the impact on predictive accuracy should be small. However, although each small-disjunct covers few examples, the set of all small disjuncts can cover a large number of examples. This paper presents evidence that this is the case in several datasets. This paper also addresses the problem of small disjuncts by using a hybrid decision-tree/genetic-algorithm approach. In essence, examples belonging to large disjuncts are classified by rules produced by a decision-tree algorithm (C4.5), while examples belonging to small disjuncts are classified by a genetic-algorithm specifically designed for discovering small-disjunct rules. We present results comparing the predictive accuracy of this hybrid system with the prediction accuracy of three versions of C4.5 alone in eight public domain datasets. Overall, the results show that our hybrid system achieves better predictive accuracy than all three versions of C4.5 alone.
Parpinelli, R. S., Lopes, H. S. and Freitas, A. A. (2002) “Data Mining with an Ant Colony Optimization Algorithm”, IEEE Transactions on Evolutionary Computation. IEEE Press, pp. 321-332. doi: 10.1109/TEVC.2002.802452.
The paper proposes an algorithm for data mining called Ant-Miner (ant-colony-based data miner). The goal of Ant-Miner is to extract classification rules from data. The algorithm is inspired by both research on the behavior of real ant colonies and some data mining concepts as well as principles. We compare the performance of Ant-Miner with CN2, a well-known data mining algorithm for classification, in six public domain data sets. The results provide evidence that: 1) Ant-Miner is competitive with CN2 with respect to predictive accuracy, and 2) the rule lists discovered by Ant-Miner are considerably simpler (smaller) than those discovered by CN2
Freitas, A. A. (2001) “Understanding the crucial role of attribute interaction in data mining”, Artificial Intelligence Review. Kluwer, pp. 177-199. doi: 10.1023/A:1011996210207.
This is a review paper, whose goal is to significantly improve our understanding of the crucial role of attribute interaction in data mining. The main contributions of this paper are as follows. Firstly, we show that the concept of attribute interaction has a crucial role across different kinds of problem in data mining, such as attribute construction, coping with small disjuncts, induction of first-order logic rules, detection of Simpson's paradox, and finding several types of interesting rules. Hence, a better understanding of attribute interaction can lead to a better understanding of the relationship between these kinds of problems, which are usually studied separately from each other. Secondly, we draw attention to the fact that most rule induction algorithms are based on a greedy search which does not cope well with the problem of attribute interaction, and point out some alternative kinds of rule discovery methods which tend to cope better with this problem. Thirdly, we discussed several algorithms and methods for discovering interesting knowledge that, implicitly or explicitly, are based on the concept of attribute interaction.
Romao, W., Freitas, A. A. and Pacheco, R. (2000) “Uma revisao de abordagens geneticodifusas para descoberta de conhecimento em banco de dados”, Acta Scientiarum. Universidade Estadual de Maringa, Brazil, pp. 1347-1359.
Book section
Cagnini, H. E. L., Freitas, A. A. and Barros, R. C. (2020) “An Evolutionary Algorithm for Learning Interpretable Ensembles of Classifiers”, in Cerri, R. and Prati, R. C. (eds.) Intelligent Systems. 9th Brazilian Conference, BRACIS 2020, Rio Grande, Brazil, October 20–23, 2020, Proceedings, Part I. Springer, pp. 18-33. doi: 10.1007/978-3-030-61377-8_2.
Ensembles of classifiers are a very popular type of method for performing classification, due to their usually high predictive accuracy. However, ensembles have two drawbacks. First, ensembles are usually considered a ‘black box’, non-interpretable type of classification model, mainly because typically there are a very large number of classifiers in the ensemble (and often each classifier in the ensemble is a black-box classifier by itself). This lack of interpretability is an important limitation in application domains where a model’s predictions should be carefully interpreted by users, like medicine, law, etc. Second, ensemble methods typically involve many hyper-parameters, and it is difficult for users to select the best settings for those hyper-parameters. In this work we propose an Evolutionary Algorithm (an Estimation of Distribution Algorithm) that addresses both these drawbacks. This algorithm optimizes the hyper-parameter settings of a small ensemble of 5 interpretable classifiers, which allows users to interpret each classifier. In our experiments, the ensembles learned by the proposed Evolutionary Algorithm achieved the same level of predictive accuracy as a well-known Random Forest ensemble, but with the benefit of learning interpretable models (unlike Random Forests).
de Sá, A. G. C., Pimenta, C. G., Pappa, G. L. and Freitas, A. A. (2020) “A robust experimental evaluation of automated multi-label classification methods”, in GECCO ’20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 2020 Genetic and Evolutionary Computation Conference (GECCO’20), New York, USA: ACM, pp. 175-183. doi: 10.1145/3377930.3390231.
Automated Machine Learning (AutoML) has emerged to deal with the selection and configuration of algorithms for a given learning task. With the progression of AutoML, several effective methods were introduced, especially for traditional classification and regression problems. Apart from the AutoML success, several issues remain open. One issue, in particular, is the lack of ability of AutoML methods to deal with different types of data. Based on this scenario, this paper approaches AutoML for multi-label classification (MLC) problems. In MLC, each example can be simultaneously associated to several class labels, unlike the standard classification task, where an example is associated to just one class label. In this work, we provide a general comparison of five automated multi-label classification methods - two evolutionary methods, one Bayesian optimization method, one random search and one greedy search - on 14 datasets and three designed search spaces. Overall, we observe that the most prominent method is the one based on a canonical grammar-based genetic programming (GGP) search method, namely Auto-MEKAGGP. Auto-MEKAGGP presented the best average results in our comparison and was statistically better than all the other methods in different search spaces and evaluated measures, except when compared to the greedy search method.
Fabris, F. and Freitas, A. A. (2020) “Analysing the overfit of the auto-sklearn automated machine learning tool.”, in Machine Learning, Optimization, and Data Science 5th International Conference. 5th International Conference on Machine Learning, Optimization and Data Science (LOD 2019), Cham, Switzerland: Springer, pp. 508-520. doi: 10.1007/978-3-030-37599-7_42.
With the ever-increasing number of pre-processing and classification algorithms, manually selecting the best algorithm and their best hyper-parameter settings (i.e. the best classification workflow) is a daunting task. Automated Machine Learning (Auto-ML) methods have been recently proposed to tackle this issue. Auto-ML tools aim to automatically choose the best classification workflow for a given dataset. In this work we analyse the predictive accuracy and overfit of the state-of-the-art auto-sklearn tool, which iteratively builds a classification ensemble optimised for the user’s dataset. This work has 3 contributions. First, we measure 3 types of auto-sklearn’s overfit, involving the differences of predictive accuracies measured on different data subsets: two parts of the training set (for learning and internal validation of the model) and the hold-out test set used for final evaluation. Second, we analyse the distribution of types of classification models selected by auto-sklearn across all 17 datasets. Third, we measure correlations between predictive accuracies on different data subsets and different types of overfitting. Overall, substantial degrees of overfitting were found in several datasets, and decision tree ensembles were the most frequently selected types of models.
de Sá, A. G. C., Freitas, A. A. and Pappa, G. L. (2018) “Automated Selection and Configuration of Multi-Label Classification Algorithms with Grammar-Based Genetic Programming”, in Auger, A., Fonseca, C. M., Lourenço, N., Machado, P., Paquete, L., and Whitley, D. (eds.) Parallel Problem Solving from Nature – PPSN XV. PPSN: 15th International Conference on Parallel Problem Solving from Nature, Springer, pp. 308-320. doi: 10.1007/978-3-319-99259-4_25.
This paper proposes Auto-MEKAGGP, an Automated Machine Learning (Auto-ML) method for Multi-Label Classification (MLC) based on the MEKA tool, which offers a number of MLC algorithms. In MLC, each example can be associated with one or more class labels, making MLC problems harder than conventional (single-label) classification problems. Hence, it is essential to select an MLC algorithm and its configuration tailored (optimized) for the input dataset. Auto-MEKAGGP addresses this problem with two key ideas. First, a large number of choices of MLC algorithms and configurations from MEKA are represented into a grammar. Second, our proposed Grammar-based Genetic Programming (GGP) method uses that grammar to search for the best MLC algorithm and configuration for the input dataset. Auto-MEKAGGP was tested in 10 datasets and compared to two well-known MLC methods, namely Binary Relevance and Classifier Chain, and also compared to GA-AutoMLC, a genetic algorithm we recently proposed for the same task. Two versions of Auto-MEKAGGP were tested: a full version with the proposed grammar, and a simplified version where the grammar includes only the algorithmic components used by GA-Auto-MLC. Overall, the full version of Auto-MEKAGGP achieved the best predictive accuracy among all five evaluated methods, being the winner in six out of the 10 datasets.
de Sá, A. G., Pappa, G. L. and Freitas, A. A. (2017) “Towards a method for automatically selecting and configuring multi-label classification algorithms”, in Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO 2017 - 7th Workshop on Evolutionary Computation for the Automated Design of Algorithms, New York, USA: ACM, pp. 1125-1132. doi: 10.1145/3067695.3082053.
Given a new dataset for classification in Machine Learning (ML), finding the best classification algorithm and the best configuration of its (hyper)-parameters for that particular dataset is an open issue. The Automatic ML (Auto-ML) area has emerged to solve this task. With this issue in mind, in this work we are interested in a specific type of classification problem, called multi-label classification (MLC). In MLC, each example in the dataset can be associated to one or more class labels, making the task considerably harder than traditional, single-label classification. In addition, the cost of learning raises due to the higher complexity of the data. Although the literature has proposed some methods to solve the Auto-ML task, those methods address only the traditional, single-label classification problem. By contrast, this work proposes the first method (an evolutionary algorithm) for solving the Auto-ML task in MLC, i.e., the first method for automatically selecting and configuring the best MLC algorithm for a given input dataset. The proposed evolutionary algorithm is evaluated on three MLC datasets, and compared against two baseline methods according to four different multi-label predictive accuracy measures. The results show that the proposed evolutionary algorithm is competitive against the baselines, but there is still room for improvement.
Cramer, S., Kampouridis, M., Freitas, A. A. and Alexandridis, A. (2016) “Predicting Rainfall in the Context of Rainfall Derivatives Using Genetic Programming”, in 2015 IEEE Symposium Series on Computational Intelligence. IEEE Computational Intelligence for Financial Engineering & Economics, Symposium Series on Computational Intelligence, IEEE, pp. 711-718. doi: 10.1109/SSCI.2015.108.
Rainfall is one of the most challenging variables to predict, as it exhibits very unique characteristics that do not exist in other time series data. Moreover, rainfall is a major component and is essential for applications that surround water resource planning. In particular, this paper is interested in the prediction of rainfall for rainfall derivatives. Currently in the rainfall derivatives literature, the process of predicting rainfall is dominated by statistical models, namely using a Markov-chain extended with rainfall prediction (MCRP). In this paper we outline a new methodology to be carried out by predicting rainfall with Genetic Programming (GP). This is the first time in the literature that GP is used within the context of rainfall derivatives. We have created a new tailored GP to this problem domain and we compare the performance of the GP and MCRP on 21 different data sets of cities across Europe and report the results. The goal is to see whether GP can outperform MCRP, which acts as a benchmark. Results indicate that in general GP significantly outperforms MCRP, which is the dominant approach in the literature.
Fabris, F. and Freitas, A. A. (2015) “A novel extended hierarchical dependence network based on non-hierarchical predictive classes and applications to ageing-related data”, in 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI). 2015 IEEE 27th International Conference on Tools with Artificial Intelligence, IEEE, pp. 711-718. doi: 10.1109/ICTAI.2015.53.
We propose a novel algorithm for hierarchical classification, the Hierarchical Dependence Network based on non-Hierarchical Predictive Classes (HDN-nHPC) algorithm. HDN-nHPC uses relationships among predictive classes that are not descendants or ancestors of each other to improve classification performance and, at the same time, provide insights to non-obvious predictive class relationships. To test our algorithm and baselines, we have used hierarchical ageing-related datasets where the classes are terms in the Gene Ontology. We have concluded, based on our experiments, that using non-hierarchical predictive class relationships improves the performance of the classification algorithm and that, considering one out of three accuracy measures, the HDN-nHPC is statistically significantly better than the other three algorithms that we have tested, while no statistical significant differences were found on the other two measures.
Jungjit, S. and Freitas, A. A. (2015) “A new genetic algorithm for multi-label correlation-based feature selection.”, in ESANN 2015 23rd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. The 23rd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN, pp. 285-290.
This paper proposes a new Genetic Algorithm for Multi-Label Correlation-Based Feature Selection (GA-ML-CFS). This GA performs a global search in the space of candidate feature subset, in order to select a high-quality feature subset is used by a multi-label classification algorithm - in this work, the Multi-Label k-NN algorithm. We compare the results of GA-ML-CFS with the results of the previously proposed Hill-Climbing for Multi-Label Correlation-Based Feature Selection (HC-ML-CFS), across 10 multi-label datasets.
Jungjit, S. and Freitas, A. A. (2015) “A lexicographic multi-objective genetic algorithm for multi-label correlation-based feature selection”, in Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. Workshop on Evolutionary Rule Learning at the 2015 Genetic and Evolutionary Computation Conference (GECCO-2015), New York, USA: ACM, pp. 989-996. doi: 10.1145/2739482.2768448.
This paper proposes a new Lexicographic multi-objective Genetic Algorithm for Multi-Label Correlation-based Feature Selection (LexGA-ML-CFS), which is an extension of the previous single-objective Genetic Algorithm for Multi-label Correlation-based Feature Selection (GA-ML-CFS). This extension uses a LexGA as a global search method for generating candidate feature subsets. In our experiments, we compare the results obtained by LexGA-ML-CFS with the results obtained by the original hill climbing-based ML-CFS, the single-objective GA-ML-CFS and a baseline Binary Relevance method, using ML-kNN as the multi-label classifier. The results from our experiments show that LexGA-ML-CFS improved predictive accuracy, by comparison with other methods, in some cases, but in general there was no statistically significant different between the results of LexGA-ML-CFS and other methods.
Gonçalves, E. C., Plastino, A. and Freitas, A. A. (2015) “Simpler is better: a novel genetic algorithm to induce compact multi-label chain classifiers”, in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. 2015 Conference on Genetic and Evolutionary Computation Conference (GECCO-2015), New York, USA: ACM, pp. 559-566. doi: 10.1145/2739480.2754650.
Multi-label classification (MLC) is the task of assigning multiple class labels to an object based on the features that describe the object. One of the most effective MLC methods is known as Classifier Chains (CC). This approach consists in training q binary classifiers linked in a chain, y1 → y2 → ... → yq, with each responsible for classifying a specific label in {l1, l2, ..., lq}. The chaining mechanism allows each individual classifier to incorporate the predictions of the previous ones as additional information at classification time. Thus, possible correlations among labels can be automatically exploited. Nevertheless, CC suffers from two important drawbacks: (i) the label ordering is decided at random, although it usually has a strong effect on predictive accuracy; (ii) all labels are inserted into the chain, although some of them might carry irrelevant information to discriminate the others. In this paper we tackle both problems at once, by proposing a novel genetic algorithm capable of searching for a single optimized label ordering, while at the same time taking into consideration the utilization of partial chains. Experiments on benchmark datasets demonstrate that our approach is able to produce models that are both simpler and more accurate.
Wan, C. and Freitas, A. A. (2015) “Two methods for constructing a gene ontology-based feature network for a Bayesian network classifier and applications to datasets of aging-related genes.”, in Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics. The 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics (ACM-BCB 2015)., New York, USA: ACM, pp. 27-36. doi: 10.1145/2808719.2808722.
In the context of the classification task of data mining or machine learning, hierarchical feature selection methods exploit hierarchical relationships among features in order to select a subset of features without hierarchical redundancy. Hierarchical feature selection is a new research area in classification research, since nearly all feature selection methods ignore hierarchical relationships among features. This paper proposes two methods for constructing a network of features to be used by a Bayesian Network Augmented Naïve Bayes (BAN) classifier, in datasets of aging-related genes where Gene Ontology (GO) terms are used as hierarchically related predictive features. One of the BAN network construction method relies on a hierarchical feature selection method to detect and remove hierarchical redundancies among features (GO terms); whilst the other BAN network construction method simply uses a conventional, flat feature selection method to select features, without removing the hierarchical redundancies associated with the GO. Both BAN network construction methods may create new edges among nodes (features) in the BAN network that did not exist in the original GO DAG (Directed Acyclic Graph), in order to preserve the generalization-specialization (ancestor-descendant) relationship among selected features. Experiments comparing these two BAN network construction methods, when using two different hierarchical feature selection methods and one at feature selection method, have shown that the best results are obtained by the BAN network construction method using one type of hierarchical feature selection method, i.e., select Hierarchical Information-Preserving features (HIP).
Fabris, F. and Freitas, A. A. (2014) “Dependency network methods for hierarchical multi-label classification of gene functions”, in 2014 IEEE Symposium on Computational Intelligence and Data Mining (CIDM). IEEE, pp. 241-248. doi: 10.1109/CIDM.2014.7008674.
Hierarchical Multi-label Classification (HMC) is a challenging real-world problem that naturally emerges in several areas. This work proposes two new algorithms using a Probabilistic Graphical Model based on Dependency Networks (DN) to solve the HMC problem of classifying gene functions into pre-established class hierarchies. DNs are especially attractive for their capability of using traditional, “out-of-the-shelf”, classification algorithms to model the relationship among classes and for their ability to cope with cyclic dependencies, resulting in greater flexibility with respect to Bayesian Networks. We tested our two algorithms: the first is a stand-alone Hierarchical Dependency Network (HDN) algorithm, and the second is a hybrid between the HDN and the Predictive Clustering Tree (PCT) algorithm, a well-known classifier for HMC. Based on our experiments, the hybrid classifier, using SVMs as base classifiers, obtained higher predictive accuracy than both the standard PCT algorithm and the HDN algorithm, considering 22 bioinformatics datasets and two out of three predictive accuracy measures specific for hierarchical classification (AU(PRC) and AUPRC w).
Freitas, A. A. (2014) “An Efficient Algorithm for Hierarchical Classification of Protein and Gene Functions”, in 2014 25th International Workshop on Database and Expert Systems Applications. Twenty-Fifth International Workshop on Database and Expert System Applications (DEXA 2014), IEEE, pp. 64-68. doi: 10.1109/DEXA.2014.29.
The classification of protein and gene functions is a complex problem that is becoming more relevant as the number of sequenced genes and proteins increases. This work presents a modified version of the Extended Local Hierarchical Naive Bayes algorithm, which exploits the requirements of the original algorithm (single-path, mandatory-leaf-prediction hierarchical classification problems in tree-structured class hierarchies) to greatly improve classification run-time. We show that, considering 18 hierarchical classification datasets, the modified algorithm yields equivalent predictive performance and significantly improves run-time in the training and prediction phases.
Nascimento da Silva, P., Corrêa Gonçalves, E., Plastino, A. and Freitas, A. A. (2014) “Distinct chains for different instances: an effective strategy for multi-label classifier chains”, in Machine Learning and Knowledge Discovery in Databases European Conference. ECML PKDD: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Berlin, Germany: Springer, pp. 453-468. doi: 10.1007/978-3-662-44851-9_29.
Multi-label classification (MLC) is a predictive problem in which an object may be associated with multiple labels. One of the most prominent MLC methods is the classifier chains (CC). This method induces q binary classifiers, where q represents the number of labels. Each one is responsible for predicting a specific label. These q classifiers are linked in a chain, such that at classification time each classifier considers the labels predicted by the previous ones as additional information. Although the performance of CC is largely influenced by the chain ordering, the original method uses a random ordering. To cope with this problem, in this paper we propose a novel method which is capable of finding a specific and more effective chain for each new instance to be classified. Experiments have shown that the proposed method obtained, overall, higher predictive accuracies than the well-established binary relevance, CC and CC ensemble methods.
Freitas, A. A. (2013) “Prediction of the Pro-longevity or Anti-Longevity Effect of Caenorhabditis Elegans Genes Based on Bayesian Classification Methods”, in 2013 IEEE International Conference on Bioinformatics and Biomedicine. 2013 IEEE International Conference on Bioinformatics and Medicine, IEEE, pp. 373-380. doi: 10.1109/BIBM.2013.6732521.
The genetic mechanisms of ageing are mysterious and sophisticated issues that attract biologists' attention. With the help of data mining techniques, some findings relevant to the ageing problem can be revealed. This paper studies the performance of Bayesian network augmented naive Bayes classifier, naive Bayes classifier and proposed feature selection methods for naive Bayes on predicting a C. elegans gene's effect on the organism's longevity. The results show that due to the hierarchical structure of predictor attribute values (Gene Ontology terms), the Bayesian network augmented naive Bayes classifier performs better than the naive Bayes classifier, and the proposed feature selection methods for naive Bayes can effectively optimize the predictive performance of naive Bayes.
Goncalves, E. C., Plastino, A. and Freitas, A. A. (2013) “A Genetic Algorithm for Optimizing the Label Ordering in Multi-Label Classifier Chains”, in 2013 IEEE 25th International Conference on Tools with Artificial Intelligence. IEEE 25th International Conference on Tools with Artificial Intelligence, IEEE, pp. 469-476. doi: 10.1109/ICTAI.2013.76.
First proposed in 2009, the classifier chains model (CC) has become one of the most influential algorithms for multi-label classification. It is distinguished by its simple and effective approach to exploit label dependencies. The CC method involves the training of q single-label binary classifiers, where each one is solely responsible for classifying a specific label in l1,..., lq. These q classifiers are linked in a chain, such that each binary classifier is able to consider the labels predicted by the previous ones as additional information at classification time. The label ordering has a strong effect on predictive accuracy, however it is decided at random and/or combining random orders via an ensemble. A disadvantage of the ensemble approach consists of the fact that it is not suitable when the goal is to generate interpretable classifiers. To tackle this problem, in this work we propose a genetic algorithm for optimizing the label ordering in classifier chains. Experiments on diverse benchmark datasets, followed by the Wilcoxon test for assessing statistical significance, indicate that the proposed strategy produces more accurate classifiers.
de Campos Merschmann, L. H. and Freitas, A. A. (2013) “An Extended Local Hierarchical Classifier for Prediction of Protein and Gene Functions.”, in Bellatreche, L. and Mohania, M. K. (eds.) Data Warehousing and Knowledge Discovery 15th International Conference. Data Warehousing and Knowledge Discovery, 15th International Conference (DaWaK 2013), Berlin, Germany: Springer, pp. 159-171. doi: 10.1007/978-3-642-40131-2_14.
Gene function prediction and protein function prediction are complex classification problems where the functional classes are structured according to a predefined hierarchy. To solve these problems, we propose an extended local hierarchical Naive Bayes classifier, where a binary classifier is built for each class in the hierarchy. The extension to conventional local approaches is that each classifier considers both the parent and child classes of the current class. We have evaluated the proposed approach on eight protein function and ten gene function hierarchical classification datasets. The proposed approach achieved somewhat better predictive accuracies than a global hierarchical Naive Bayes classifier.
Salama, K. M. and Freitas, A. A. (2013) “Extending the ABC-Miner Bayesian classification algorithm.”, in Nature Inspired Cooperative Strategies for Optimization (NICSO 2013) Learning, Optimization and Interdisciplinary Applications. International Workshop on Natural Inspired Cooperative Strategies for Optimization (NICSO 2013), Cham, Switzerland: Springer, pp. 1-12. doi: 10.1007/978-3-319-01692-4_1.
ABC-Miner is a Bayesian classification algorithm based on the Ant Colony Optimization (ACO) meta-heuristic. The algorithm learns Bayesian network Augmented Naïve-Bayes (BAN) classifiers, where the class node is the parent of all the nodes representing the input variables. However, this assumes the existence of a dependency relationship between the class variable and all the input variables, and this relationship is a type of “causal” (rather than “effect”) relationship, which restricts the flexibility of the algorithm to learn. In this paper, we propose ABC-Miner+, an extension to the ABC-Miner algorithm which is able to learn more flexible Bayesian network classifier structures, where it is not necessary to have a (direct) dependency relationship between the class variable and each of the input variables, and the dependency between the class and the input variables varies from “causal” to “effect” relationships. The produced model is the Markov blanket of the class variable. Empirical evaluations on UCI benchmark datasets show that our extended ABC-Miner+ outperforms its previous version in terms of predictive accuracy, model size and computational time.
Barros, R. C., Cerri, R., Freitas, A. A. and de Carvalho, A. C. (2013) “Probabilistic clustering for hierarchical multi-label classification of protein functions”, in Machine Learning and Knowledge Discovery in Databases European Conference. Machine Learning and Knowledge Discovery in Databases: European Conference (ECMLPKDD-2013), Berlin, Germany: Springer, pp. 385-400. doi: 10.1007/978-3-642-40991-2_25.
Hierarchical Multi-Label Classification is a complex classification problem where the classes are hierarchically structured. This task is very common in protein function prediction, where each protein can have more than one function, which in turn can have more than one sub-function. In this paper, we propose a novel hierarchical multi-label classification algorithm for protein function prediction, namely HMC-PC. It is based on probabilistic clustering, and it makes use of cluster membership probabilities in order to generate the predicted class vector. We perform an extensive empirical analysis in which we compare our new approach to four different hierarchical multi-label classification algorithms, in protein function datasets structured both as trees and directed acyclic graphs. We show that HMC-PC achieves superior or comparable results compared to the state-of-the-art method for hierarchical multi-label classification.
Salama, K. M. and Freitas, A. A. (2013) “Investigating the Impact of Various Classification Quality Measures in the Predictive Accuracy of ABC-Miner”, in 2013 IEEE Congress on Evolutionary Computation. 2013 IEEE Congress on Evolutionary Computation (CEC-2013), IEEE, pp. 2321-2328. doi: 10.1109/CEC.2013.6557846.
Learning classifiers from datasets is a central problem in data mining and machine learning research. ABC-Miner is an Ant-based Bayesian Classification algorithm that employs the Ant Colony Optimization (ACO) meta-heuristics to learn the structure of Bayesian Augmented Naive-Bayes (BAN) Classifiers. One of the most important aspects of the ACO algorithm is the choice of the quality measure used to evaluate a candidate solution to update pheromone. In this paper, we explore the use of various classification quality measures for evaluating the BAN classifiers constructed by the ants. The aim of this investigation is to discover how the use of different evaluation measures affects the quality of the output classifier in terms of predictive accuracy. In our experiments, we use 6 different classification measures on 25 benchmark datasets. We found that the hypothesis that different measures produce different results is acceptable according to the Friedman's statistical test.
Salama, K. M. and Freitas, A. A. (2013) “Clustering-based Bayesian Multi-net Classifier Construction with Ant Colony Optimization”, in 2013 IEEE Congress on Evolutionary Computation. 2013 IEEE Congress on Evolutionary Computation (CEC-2013), IEEE, pp. 3079-3086. doi: 10.1109/CEC.2013.6557945.
Bayesian Multi-nets (BMNs) are a special kind of Bayesian network (BN) classifiers that consist of several local networks, typically, one for each predictable class, to model an asymmetric set of variable dependencies given each class value. Alternatively, multi-nets can be learnt upon arbitrary partitions of a dataset, in which each partition holds more consistent variable dependencies given the data subset in the partition. This paper proposes two contributions to the approach that clusters the dataset into separate data subsets to build asymmetric local BN classifiers, one for each subset. First, we extend the K-modes algorithm, previously used by the Case-Based Bayesian Network Classifiers (CBBN) approach to create clusters before learning the BN classifiers. Second, we introduce the Ant-Clust-B algorithm that employs Ant Colony Optimization (ACO) to learn clustering-based BMNs. Ant-Clust-B uses ACO in the clustering step before learning the local BN classifiers. Empirical results are obtained from experiments on 18 UCI datasets.
Cerri, R., Barros, R. C., de Carvalho, A. C. and Freitas, A. A. (2013) “A grammatical evolution algorithm for the generation of hierarchical multi-label classification rules”, in 2013 IEEE Congress on Evolutionary Computation. 2013 IEEE Congress on Evolutionary Computation (CEC-2013), IEEE, pp. 454-461. doi: 10.1109/CEC.2013.6557604.
Hierarchical Multi-Label Classification (HMC) is a challenging task in data mining and machine learning. Each instance in HMC can be classified into two or more classes simultaneously. These classes are structured in a hierarchy, in the form of either a tree or a directed acyclic graph. Therefore, an instance can be assigned to two or more paths from the hierarchical structure, resulting in a complex classification problem with hundreds or thousands of classes. Several methods have been proposed to deal with such problems, including several algorithms based on well-known bio-inspired techniques, such as neural networks, ant colony optimization, and genetic algorithms. In this work, we propose a novel global method called GEHM, which makes use of grammatical evolution for generating HMC rules. In this approach, the grammatical evolution algorithm evolves the antecedents of classification rules, in order to assign instances from a HMC dataset to a probabilistic class vector. Our method is compared to bio-inspired HMC algorithms in protein function prediction datasets. The empirical analysis conducted in this work shows that GEHM outperforms the bio-inspired algorithms with statistical significance, which suggests that grammatical evolution is a promising alternative to deal with hierarchical multi-label classification of biological data.
Salama, K. M. and Freitas, A. A. (2013) “ACO-based Bayesian network ensembles for the hierarchical classification of ageing-related proteins”, in Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics 11th European Conference. 11th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, Berlin, Germany: Springer, pp. 80-91. doi: 10.1007/978-3-642-37189-9_8.
The task of predicting protein functions using computational techniques is a major research area in the field of bioinformatics. Casting the task into a classification problem makes it challenging, since the classes (functions) to be predicted are hierarchically related, and a protein can have more than one function. One approach is to produce a set of local classifiers; each is responsible for discriminating between a subset of the classes in a certain level of the hierarchy. In this paper we tackle the hierarchical classification problem in a local fashion, by learning an ensemble of Bayesian network classifiers for each class in the hierarchy and combining their outputs with four alternative methods: a) selecting the best classifier, b) majority voting, c) weighted voting, and d) constructing a meta-classifier. The ensemble is built using ABC-Miner, our recently introduced Ant-based Bayesian Classification algorithm. We use different types of protein representations to learn different classification models. We empirically evaluate our proposed methods on an ageing-related protein dataset created for this research.
Salama, K. M. and Freitas, A. A. (2012) “ABC-Miner: an ant-based Bayesian classification algorithm.”, in Swarm Intelligence 8th International Conference. Swarm Intelligence: 8th International Conference (ANTS 2012)., Berlin, Germany: Springer, pp. 13-24. doi: 10.1007/978-3-642-32650-9_2.
Bayesian networks (BNs) are powerful tools for knowledge representation and inference that encode (in)dependencies among random variables. A Bayesian network classifier is a special kind of these networks that aims to compute the posterior probability of each class given an instance of the attributes and predicts the class with the highest posterior probability. Since learning the optimal BN structure from a dataset is NP -hard, heuristic search algorithms need to be applied effectively to build high-quality networks. In this paper, we propose a novel algorithm, called ABC-Miner, for learning the structure of BN classifiers using the Ant Colony Optimization (ACO) meta-heuristic. We describe all the elements necessary to tackle our learning problem using ACO, and experimentally compare the performance of our ant-based Bayesian classification algorithm with other algorithms for learning BN classifiers used in the literature.
Basgalupp, M. P., Barros, R. C., de Carvalho, A. C. and Freitas, A. A. (2012) “A beam search based decision tree induction algorithm”, in Kulkarni, S. (ed.). IGI Global, pp. 357-370. doi: 10.4018/978-1-4666-1833-6.ch020.
Barros, R. C., Basgalupp, M. P., de Carvalho, A. C. and Freitas, A. A. (2012) “A hyper-heuristic evolutionary algorithm for automatically designing decision-tree algorithms”, in Moore, J. H., Soule, T., Banzhaf, W., Llora, X., Auger, A., Ritchie, M., Ochoa, G., Rand, B., Bongard, J., Loiacono, D., Mehnen, J., and Davis, D. (eds.) Proceedings of the 14th annual conference on Genetic and evolutionary computation. Proceedings of 2012 Genetic and Evolutionary Computation Conference (GECCO), New York, USA: ACM, pp. 1237-1244. doi: 10.1145/2330163.2330335.
Decision tree induction is one of the most employed methods to extract knowledge from data, since the representation of knowledge is very intuitive and easily understandable by humans. The most successful strategy for inducing decision trees, the greedy top-down approach, has been continuously improved by researchers over the years. This work, following recent breakthroughs in the automatic design of machine learning algorithms, proposes a hyper-heuristic evolutionary algorithm for automatically generating decision-tree induction algorithms, named HEAD-DT. We perform extensive experiments in 20 public data sets to assess the performance of HEAD-DT, and we compare it to traditional decision-tree algorithms such as C4.5 and CART. Results show that HEAD-DT can generate algorithms that significantly outperform C4.5 and CART regarding predictive accuracy and F-Measure.
Jungjit, S., Freitas, A. A., Michaelis, M. and Cinatl, J. (2012) “A multi-label correlation-based feature selection method for the classification of neuroblastoma microarray data.”, in Bichindaritz, I., Perner, P., Ruß, G., and Schmidt, R. (eds.) Advances in Data Mining: 12 Industrial Conference ICDM 2012 Workshop Proceedings. Advances in Data Mining: 12th Industrial Conference (ICDM 2012) Workshop Proceedings Â? Workshop on Data Mining in Life Sciences (DMLS 2012)., IBAI Publishing, pp. 149-157. Available at: http://www.cs.kent.ac.uk/pubs/2012/3253.
Xavier, J. C., Canuto, A. M., Freitas, A. A., Gonçalves, L. M. and Silla Jr, C. N. (2011) “A hierarchical approach to represent relational data applied to clustering tasks”, in The 2011 International Joint Conference on Neural Networks. Proceedings of the 2011 International Joint Conference on Neural Networks, IEEE, pp. 182-196. doi: 10.1109/IJCNN.2011.6033624.
Nowadays, the representation of many real word problems needs to use some type of relational model. As a consequence, information used by a wide range of systems has been stored in multi relational tables. However, from a data mining point of view, it has been a problem, since most of the traditional data mining algorithms have not been originally proposed to handle this type of data without discarding relationship information. Aiming to ameliorate this problem, we propose a hierarchical approach for handling relational data. In this approach the relational data is converted into a hierarchical structure (the main table as the root and the relations as the nodes). This hierarchical way to represent relational data can be used either for classification or clustering purposes. In this paper, we will use it in clustering algorithms. In order to do so, we propose a hierarchical distance metric to compute the similarity between the tables. In the empirical analysis, we will apply the proposed approach in two well-known clustering algorithms (k-means and agglomerative hierarchical). Finally, this paper also compares the effectiveness of our approach with one existing relational approach.
Barros, R. C., Basgalupp, M. P., de Carvalho, A. C. and Freitas, A. A. (2011) “Towards the automatic design of decision tree induction algorithms”, in Proceedings of the 13th annual conference companion on Genetic and evolutionary computation. Proceedings of the GECCO-2011 First Workshop on Evolutionary Algorithms for Evolving Generic Algorithms, New York, USA: ACM, pp. 182-196. doi: 10.1145/2001858.2002050.
Decision tree induction is one of the most employed methods to extract knowledge from data, since the representation of knowledge is very intuitive and easily understandable by humans. The most successful strategy for inducing decision trees, the greedy top-down approach, has been continuously improved by researchers over the years. This work, following recent breakthroughs in the automatic design of machine learning algorithms, proposes two different approaches for automatically generating generic decision tree induction algorithms. Both approaches are based on the evolutionary algorithms paradigm, which improves solutions based on metaphors of biological processes. We also propose guidelines to design interesting fitness functions for these evolutionary algorithms, which take into account the requirements and needs of the end-user.
Keysermann, M., Freitas, A. and Vargas, P. (2011) “Implementing a data mining approach to episodic memory modelling for artificial companions”, in Kazakov, D. and Tsoulas, G. (eds.) Human Memory for Artificial Agents: AISB 2011 Symposium. Proceedings of AISBÂ?11: Human Memory for Artificial Agents, Society for the Study of Artificial Intelligence and the Simulation of Behaviour, pp. 182-196.
Pappa, G. L. and Freitas, A. A. (2010) “Creating rule ensembles from automatically-evolved rule induction algorithms”, in Advances in Machine Learning I: Dedicated to the memory of Prof. Ryszard S. Michalski. Springer, pp. 182-196. doi: 10.1007/978-3-642-05177-7.
Xavier, J. C., Freitas, A. A., Canuto, A. M. and Gonçalves, L. M. (2010) “Web log data clustering for a multi-agent recommendation system”, in 2010 International Conference on Machine Learning and Cybernetics. Machine Learning and Cybernetics (ICMLC): 2010 International Conference on, IEEE, pp. 182-196. doi: 10.1109/ICMLC.2010.5581017.
In this paper, we propose an automatic way of recommending information to be visualized by users. The list of information to be recommended is generated based on the web logs of the users stored by the system in a multi relational database. This system is a web-based multi-agent system which provides geographical information and monitors the actions of the users by generating logs. Frequently, the system joins the relational web log data and runs a clustering algorithm in order to recommend a list of most accessed information up to that moment to registered users who log in the system.
Alves, R. T., Delgado, M. and Freitas, A. A. (2010) “Knowledge discovery with artificial immune systems for hierarchical multi-label classification of protein functions”, in Sobrevilla, P., Aranda, J., and Xambo, S. (eds.) International Conference on Fuzzy Systems. 2010 World Congress on Computational Intelligence (WCII/FUZZ-IEEE 2010), IEEE, pp. 182-196. doi: 10.1109/FUZZY.2010.5584298.
This work presents a system for knowledge discovery from protein databases, based on an Artificial Immune System. The discovered rules have the advantage of representing comprehensible knowledge to biologist users. This task leads to a very challenging problem since a protein can be assigned multiple classes (functions or Gene Ontology (GO) terms) across several levels of the GO's term hierarchy. To solve this problem we present two versions of an algorithm called MHC-AIS (Multi-label Hierarchical Classification with an Artificial Immune System), which is a sophisticated classification algorithm tailored to both multi-label and hierarchical classification. The first version of MHC-AIS builds a global classifier to predict all classes in the dataset, whilst the second version builds a local classifier to predict each class. The proposed versions and an algorithm chosen for comparison are evaluated on a protein dataset, and the results show that MHC-AIS outperformed the compared algorithm in general.
Barros, R. C., Basgalupp, M. P., Ruiz, D. D., de Carvalho, A. C. and Freitas, A. A. (2010) “Evolutionary model tree induction”, in Shin, D. (ed.) SAC ’10 Proceedings of the 2010 ACM Symposium on Applied Computing. Applied Computing 2010: Proc. 25th Annual ACM Symposium on Applied Computing (SAC-2010), New York, USA: ACM, pp. 182-196. doi: 10.1145/1774088.1774327.
Model trees are a particular case of decision trees employed to solve regression problems. They have the advantage of presenting an interpretable output with an acceptable level of predictive performance. Since generating optimal model trees is a NP-Complete problem, the traditional model tree induction algorithms make use of a greedy heuristic, which may not converge to the global optimal solution. We propose the use of the evolutionary algorithms paradigm (EA) as an alternate heuristic to generate model trees in order to improve the convergence to global optimal solutions. We test the predictive performance of this new approach using public UCI datasets, and compare the results with traditional greedy regression/model trees induction algorithms.
Tsunoda, D. F., Freitas, A. A. and Lopes, H. S. (2009) “A Genetic Programming-Based Tool for Protein Classification”, in Abraham, A., Benitez, J., Herrera, F., Loia, V., Marcelloni, F., and Senatore, S. (eds.) 2009 Ninth International Conference on Intelligent Systems Design and Applications. Proc. 9th Int. Conf. on Intelligent System Design and Applications (ISDAÂ?09), IEEE, pp. 182-196. doi: 10.1109/ISDA.2009.14.
Proteins can be grouped into families according to some features such as hydrophobicity, composition or structure, aiming to establish common biological functions. This paper presents a system that was conceived to discover features (particular sequences of amino acids, or motifs) that occur very often in proteins of a given family but rarely occur in proteins of other families. These features can be used for the classification of unknown proteins, that is, to predict their function by analyzing their primary structure. Experiments were done with a set of enzymes extracted from the protein data bank. The heuristic method used was based on genetic programming using operators specially tailored for the target problem. The final performance was measured using sensitivity (Se) and specificity (Sp). The best results obtained for the enzyme dataset suggest that the proposed evolutionary computation method is very effective to find predictive features (motifs) for protein classification.
Silla Jr, C. N. and Freitas, A. A. (2009) “A global-model naive Bayes approach to the hierarchical prediction of protein functions”, in Wang, W., Kargupta, H., Ranka, S., Yu, P. S., and Wu, X. (eds.) 2009 Ninth IEEE International Conference on Data Mining. Proc. Ninth IEEE Int. Conf. on Data Mining (ICDM-2009), IEEE, pp. 182-196. doi: 10.1109/ICDM.2009.85.
In this paper we propose a new global-model approach for hierarchical classification, where a single global classification model is built by considering all the classes in the hierarchy - rather than building a number of local classification models as it is more usual in hierarchical classification. The method is an extension of the flat classification algorithm naive Bayes. We present the extension made to the original algorithm as well as its evaluation on eight protein function hierarchical classification datasets. The achieved results are positive and show that the proposed global model is better than using a local model approach.
Tsunoda, D. F., Lopes, H. S. and Freitas, A. A. (2009) “A hybrid evolutionary approach for the protein classification problem”, in Nguyen, N. T., Kowalczyk, R., and Chen, S.-M. (eds.) Computational Collective Intelligence. Semantic Web, Social Networks and Multiagent Systems First International Conference. Proc. 1st Int. Conf. on Collective Intelligence ( ICCI 2009), Berlin, Germany: Springer, pp. 182-196. doi: 10.1007/978-3-642-04441-0_55.
This paper proposes a hybrid algorithm that combines characteristics of both Genetic Programming (GP) and Genetic Algorithms (GAs), for discovering motifs in proteins and predicting their functional classes, based on the discovered motifs. In this algorithm, individuals are represented as IF-THEN classification rules. The rule antecedent consists of a combination of motifs automatically extracted from protein sequences. The rule consequent consists of the functional class predicted for a protein whose sequence satisfies the combination of motifs in the rule antecedent. The system can be used in two different ways. First, as a stand-alone classification system, where the evolved classification rules are directly used to predict the functional classes of proteins. Second, the system can be used just as an “attribute construction” method, discovering motifs that are given, as predictor attributes, to another classification algorithm. In this usage of the system, a classical decision tree induction algorithm was used as the classifier. The proposed system was evaluated in these two scenarios and compared with another Genetic Algorithm designed specifically for the discovery of motifs – and therefore used only as an attribute construction algorithm. This comparison was performed by mining an enzyme data set extracted from the Protein Data Bank. The best results were obtained when using the proposed hybrid GP/GA as an attribute construction algorithm and performing the classification (using the constructed attributes) with the decision tree induction algorithm.
Silla Jr, C. N. and Freitas, A. A. (2009) “Novel top-down approaches for hierarchical classification and their application to automatic music genre classification”, in Chen, C. and Roberts, R. (eds.) 2009 IEEE International Conference on Systems, Man and Cybernetics. Proc. 2009 IEEE Int. Conf. on Systems, Man and Cybernetics (SMC-2009), IEEE, pp. 182-196. doi: 10.1109/ICSMC.2009.5346776.
This paper presents two novel hierarchical classification methods which are extensions of a previously proposed selective classifier top-down approach, which consists of selecting - during the training phase - the best classifier at each node of a classifier tree. More precisely, we propose two novel selective top-down hierarchical methods. First, a method that selects the best feature set instead of the best classifier. Secondly, a method that selects both the best classifier and the best representation simultaneously. These methods are evaluated on the task of hierarchical music genre classification using four different types of feature sets extracted from each song and four classifiers.
de Carvalho, A. C. and Freitas, A. A. (2009) “A tutorial on multi-label classification techniques”, in Abraham, A., Hassanien, A.-E., and Snasel, V. (eds.) Foundations of Computational Intelligence. Springer, pp. 177-195.
Iqbal, M., Freitas, A. A. and Johnson, C. G. (2009) “A hybrid rule-induction/likelihood-ratio based approach for predicting protein-protein interactions”, in Mumford, C. L. and Jain, L. C. (eds.) Computational Intelligence: Collaboration, Fusion and Emergence. Springer, pp. 623-637. doi: 10.1007/978-3-642-01799-519.
Otero, F. E., Segond, M., Freitas, A. A., Johnson, C. G., Robilliard, D. and Fonlupt, C. (2009) “An empirical evaluation of the effectiveness of different types of predictor attributes in protein function prediction.”, in Abraham, A., Hassanien, A.-E., and Snasel, V. (eds.) Studies in Computational Intelligence. Berlin: Springer, pp. 339-357. doi: 10.1007/978-3-642-01536-6_13.
Many classification schemes for defining protein functions, such as Gene Ontology (GO), are organised in a hierarchical structure. Nodes near the root of the hierarchy represent general functions while nodes near the leaves of the hierarchy represent more specific functions, giving the flexibility to specify at which level the protein will be annotated. In a data mining perspective, hierarchical structures present a more challenging problem, since the relationship between nodes need to be considered. This chapter presents an empirical evaluation of different protein representations for protein function prediction in terms of maximizing predictive accuracy, investigating which type of representation is more suitable for different levels of the GO hierarchy.
Basgalupp, M. P., Barros, R. C., de Carvalho, A. C., Freitas, A. A. and Ruiz, D. D. (2009) “LEGAL-Tree: a lexicographic multi-objective genetic algorithm for decision tree induction”, in Shin, S., Ossowski, S., Martins, P., Menezes, R., Virol, M., Hong, J., Shin, D., Palakal, M., Fritzke, U., Crosby, M., and Haddad, H. (eds.) SAC ’09 Proceedings of the 2009 ACM symposium on Applied Computing. Proceedings of the 2009 ACM Symposium on Applied Computing, New York, USA: ACM, pp. 1085-1090. doi: 10.1145/1529282.1529521.
Decision trees are widely disseminated as an effective solution for classification tasks. Decision tree induction algorithms have some limitations though, due to the typical strategy they implement: recursive top-down partitioning through a greedy split evaluation. This strategy is limiting in the sense that there is quality loss while the partitioning process occurs, creating statistically insignificant rules. In order to prevent the greedy strategy and to avoid converging to local optima, we present a novel Genetic Algorithm for decision tree induction based on a lexicographic multi-objective approach, and we compare it with the most well-known algorithm for decision tree induction, J48, over distinct public datasets. The results show the feasibility of using this technique as a means to avoid the previously described problems, reporting not only a comparable accuracy but also, importantly, a significantly simpler classification model in the employed datasets.
Otero, F. E., Freitas, A. A. and Johnson, C. G. (2009) “A hierarchical classification ant colony algorithm for predicting gene ontology terms”, in Pizzuti, C., Ritchie, M., and Giacobini, M. (eds.) Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics 7th European Conference. Proc. 7th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics (EvoBio-2009), Berlin, Germany: Springer, pp. 68-79. doi: 10.1007/978-3-642-01184-9_7.
This paper proposes a novel Ant Colony Optimisation algorithm for the hierarchical problem of predicting protein functions using the Gene Ontology (GO). The GO structure represents a challenging case of hierarchical classification, since its terms are organised in a direct acyclic graph fashion where a term can have more than one parent in contrast to only one parent in tree structures. The proposed method discovers an ordered list of classification rules which is able to predict all GO terms independently of their level. We have compared the proposed method against a baseline method, which consists of training classifiers for each GO terms individually, in five different ion-channel data sets and the results obtained are promising.
Bevilacqua, V., Menolascina, F., Alves, R. T., Tommasi, S., Mastronardi, G., Delgado, M., Paradiso, A., Nicosia, G. and Freitas, A. A. (2008) “Artificial Immune Systems in Bioinformatics”, in Smolinski, T., Milanova, M. G., and Hassanien, A.-E. (eds.) Computational Intelligence in Biomedicine and Bioinformatics: current trends and applications. Berlin: Springer, pp. 271-296. doi: 10.1007/978-3-540-70778-3_113.
Otero, F. E., Freitas, A. A. and Johnson, C. G. (2008) “cAnt-Miner: an ant colony classification algorithm to cope with continuous attributes”, in Dorigo, M. (ed.) Ant Colony Optimization and Swarm Intelligence 6th International Conference. Ant Colony Optimization and Swarm Intelligence (Proc. ANTS 2008), LNCS 5217, Berlin, Germany: Springer, pp. 48-59. doi: 10.1007/978-3-540-87527-7_5.
This paper presents an extension to Ant-Miner, named cAnt-Miner (Ant-Miner coping with continuous attributes), which incorporates an entropy-based discretization method in order to cope with continuous attributes during the rule construction process. By having the ability to create discrete intervals for continuous attributes "on-the-fly", cAnt-Miner does not requires a discretization method in a preprocessing step, as Ant-Miner requires. cAnt-Miner has been compared against Ant-Miner in eight public domain datasets with respect to predictive accuracy and simplicity of the discovered rules. Empirical results show that creating discrete intervals during the rule construction process facilitates the discovery of more accurate and significantly simpler classification rules
Costa, E. P., Lorena, A. C., Carvalho, A. C. P. L. F. and Freitas, A. A. (2008) “Top-down hierarchical ensembles of classifiers for predicting G-Protein-Coupled-Receptor functions”, in Bazzan, A. L., Craven, M., and Martins, N. F. (eds.) Advances in Bioinformatics and Computational Biology Third Brazilian Symposium on Bioinformatics. Advances in Bioinformatics and Computational Biology (Proc. 2008 Brazilian Symposium in Bioinformatics (BSB-2008)), Lecture Notes in Bioinformatics 5167, Berlin, Germany: Springer, pp. 35-46. doi: 10.1007/978-3-540-85557-6_4.
Despite the recent advances in Molecular Biology, the function of a large amount of proteins is still unknown. An approach that can be used in the prediction of a protein function consists of searching against secondary databases, also known as signature databases. Different strategies can be applied to use protein signatures in the prediction of function of proteins. A sophisticated approach consists of inducing a classification model for this prediction. This paper applies five hierarchical classification methods based on the standard Top-Down approach and one hierarchical classification method based on a new approach named Top-Down Ensembles - based on the hierarchical combination of classifiers - to three different protein functional classification datasets that employ protein signatures. The algorithm based on the Top-Down Ensembles approach presented slightly better results than the other algorithms, indicating that combinations of classifiers can improve the performance of hierarchical classification models.
Alves, R. T., Delgado, M. and Freitas, A. A. (2008) “Multi-label hierarchical classification of protein functions with artificial immune systems”, in Bazzan, A. L., Craven, M., and Martins, N. F. (eds.) Advances in Bioinformatics and Computational Biology Third Brazilian Symposium on Bioinformatics. Advances in Bioinformatics and Computational Biology (Proc. 2008 Brazilian Symposium in Bioinformatics (BSB-2008)), Lecture Notes in Bioinformatics 5167, Berlin, Germany: Springer, pp. 1-12. doi: 10.1007/978-3-540-85557-6_1.
This work proposes two versions of an Artificial Immune System (AIS) - a relatively recent computational intelligence paradigm - for predicting protein functions described in the Gene Ontology (GO). The GO has functional classes (GO terms) specified in the form of a directed acyclic graph, which leads to a very challenging multi-label hierarchical classification problem where a protein can be assigned multiple classes (functions, GO terms) across several levels of the GO's term hierarchy. Hence, the proposed approach, called MHC-AIS (Multi-label Hierarchical Classification with an Artificial Immune System), is a sophisticated classification algorithm tailored to both multi-label and hierarchical classification. The first version of the MHC-AIS builds a global classifier to predict all classes in the application domain, whilst the second version builds a local classifier to predict each class. In both versions of the MHC-AIS the classifier is expressed as a set of IF-THEN classification rules, which have the advantage of representing comprehensible knowledge to biologist users. The two MHC-AIS versions are evaluated on a dataset of DNA-binding and ATPase proteins.
Secker, A. D., Davies, M. N., Freitas, A. A., Timmis, J., Clark, E. and Flower, D. R. (2008) “An artificial immune system for evolving amino acid clusters tailored to protein function prediction”, in Bentley, P. J., Lee, D., and Jung, S. (eds.) Artificial Immune Systems. 7th International Conference on Artificial Immune Systems, Springer, pp. 242-253.
This paper addresses the classification task of data mining (a form of supervised learning) in the context of an important bioinformatics problem, namely the prediction of protein functions. This problem is cast as a hierarchical classification problem, where the protein functions to be predicted correspond to classes that are arranged in a hierarchical structure, in the form of a class tree. The main contribution of this paper is to propose a new Artificial Immune System that creates a new representation for proteins, in order to maximize the predictive accuracy of a hierarchical classification algorithm applied to the corresponding protein function prediction problem.
Correa, E. S., Freitas, A. A. and Johnson, C. G. (2008) “A New Discrete Particle Swarm Algorithm Applied to Attribute Selection in a Bioinformatics Data Set”, in Proceedings of the 8th annual conference on Genetic and evolutionary computation. 8th annual conference on Genetic and evolutionary computation, New York, USA: ACM, pp. 35-42. doi: 10.1145/1143997.1144003.
Many data mining applications involve the task of build- ing a model for predictive classification. The goal of such a model is to classify examples (records or data instances) into classes or categories of the same type. The use of variables (attributes) not related to the classes can reduce the accu- racy and reliability of a classification or prediction model. Superfluous variables can also increase the costs of build- ing a model - particularly on large data sets. We propose a discrete Particle Swarm Optimization (PSO) algorithm de- signed for attribute selection. The proposed algorithm deals with discrete variables, and its population of candidate solu- tions contains particles of different sizes. The performance of this algorithm is compared with the performance of a standard binary PSO algorithm on the task of selecting at- tributes in a bioinformatics data set. The criteria used for comparison are: (1) maximizing predictive accuracy; and (2) finding the smallest subset of attributes.
Ghosh, S., Marshall, I. W. and Freitas, A. A. (2008) “Autonomously detecting the defective pixels in an imaging sensor array using a robust statistical technique”, in Image Quality and System Performance V. Image Quality and Systems Performance V ? Proc. of SPIE-IS&T Electronic Imaging, SPIE Vol. 6808, Bellingham, Washington: SPIE. doi: 10.1117/12.765147.
We propose a statistical technique for autonomously detecting defective pixels in a CCD sensor array. Our data-driven analysis technique can autonomously identify a wide range of faulty and 'suspect' pixels (hypo-sensitive or hyper-sensitive pixels), without the need for any defect model or prior knowledge of the nature of pixel faults. We apply our technique to the autonomous detection of the defective pixels in regular images captured with a camera, equipped with a CCD.
Holden, N. and Freitas, A. A. (2008) “Improving the performance of hierarchical classification with swarm intelligence”, in Marchiori, E. and Moore, J. H. (eds.) Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics 6th European Conference. 6th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, Berlin, Germany: Springer, pp. 48-60. doi: 10.1007/978-3-540-78757-0_5.
In this paper we propose a new method to improve the performance of hierarchical classification. We use a swarm intelligence algorithm to select the type of classification algorithm to be used at each "classifier node" in a classifier tree. These classifier nodes are used in a top-down divide and conquer fashion to classify the examples from hierarchical data sets. In this paper we propose a swarm intelligence based approach which attempts to mitigate a major drawback with a recently proposed local search-based, greedy algorithm. Our swarm intelligence based approach is able to take into account classifier interactions whereas the greedy algorithm is not. We evaluate our proposed method against the greedy method in four challenging bioinformatics data sets and find that, overall, there is a significant increase in performance.
Iqbal, M., Freitas, A. A. and Johnson, C. G. (2008) “Protein interaction inference using particle swarm optimization algorithm”, in Marchiori, E. and Moore, J. H. (eds.) Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics 6th European Conference. 6th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, Berlin, Germany: Springer, pp. 61-70. doi: 10.1007/978-3-540-78757-0_6.
Many processes in the cell involve interaction among the proteins and determination of the networks of such interactions is of immense importance towards the complete understanding of cellular functions. As the experimental techniques for this purpose are expensive and potentially erroneous, there are many computational methods being put forward for prediction of protein-protein interactions. These methods use different genomic features for indirect inference of protein- protein interactions. As the interaction among two proteins is facilitated by domains, there are many methods being put forward for inference of such interactions using the specificity of assignment of domains to proteins. We present here an heuristic optimization method, particle swarm optimization, which predicts protein-protein interaction by using the domain assignments information. Results are compared with another known method which predicts domain interactions by casting the problem of interactions inference as a maximum satisfiability (MAX-SAT) problem.
Ghosh, S., Freitas, A. and Marshall, I. (2007) “Robust Autonomous Detection of the Faulty Sensors of a Sensor Array”, in 2007 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2007, CAMPSAP 2007, IEEE, pp. 233-236. doi: 10.1109/CAMSAP.2007.4498008.
We propose a technique for the autonomous detection of the faulty sensors of a sensor array that are aberrant relative to the rest. Our approach is based on probabilistically modeling the distribution of the differences between the sensor measurements as a mixture of gaussians and then classifying further instances of the sensor differences using a naive bayes classifier. We demonstrate the applicability of this technique to the diagnosis of the sensors/photosites of a CCD array, using sensor array data comprising of randomly selected images. Our technique performs well for different combinations of parameter settings at the detection of the faulty photosites of a CCD array.
Pappa, G. L. and Freitas, A. A. (2007) “Discovering new rule induction algorithms with grammar-based genetic programming”, in Maimon, O. and Rokach, L. (eds.) Soft Computing for Knowledge Discovery and Data Mining. New York: Springer, pp. 133-152. doi: 10.1007/978-0-387-69935-6_6.
Rule induction is a data mining technique used to extract classification rules of the form IF (conditions) THEN (predicted class) from data. The majority of the rule induction algorithms found in the literature follow the sequential covering strategy, which essentially induces one rule at a time until (almost) all the training data is covered by the induced rule set. This strategy describes a basic algorithm composed by several key elements, which can be modified and/or extended to generate new and better rule induction algorithms. With this in mind, this work proposes the use of a grammar-based genetic programming (GGP) algorithm to automatically discover new sequential covering algorithms. The proposed system is evaluated using 20 data sets, and the automatically-discovered rule induction algorithms are compared with four well-known human-designed rule induction algorithms. Results showed that the GGP system is a promising approach to effectively discover new sequential covering algorithms.
Freitas, A. A. (2007) “A review of evolutionary algorithms for data mining”, in Maimon, O. and Rokach, L. (eds.) Soft Computing for Knowledge Discovery and Data Mining. Springer, pp. 61-93.
Secker, A. D. and Freitas, A. A. (2007) “WAIRS: Improving Classification Accuracy by Weighting Attributes in the AIRS Classifier”, in 2007 IEEE Congress on Evolutionary Computation. Proceedings of the 2007 IEEE Congress on Evolutionary Computation (CEC 2007), IEEE, pp. 3759-3765. doi: 10.1109/CEC.2007.4424960.
AIRS (Artificial Immune Recognition System) has shown itself to be a competitive classifier. It has also proved to be the most popular immune inspired classifier. However, rather than AIRS being a classifier in its own right as previously described, we see AIRS more as a pre-processor to a KNN classifier. It is our view that by not explicitly classing it as such development of this algorithm has been rather held back. Seeing it as a pre-processor allows inspiration to be taken from the machine learning literature where such pre-processors are not uncommon. With this in mind, this paper takes a core feature of many such pre-processors, that of attribute weighting, and applies it to AIRS. The resultant algorithm called WAIRS (Weighted AIRS) uses a weighted distance function during all affinity evaluations. WAIRS is tested on 9 benchmark datasets and is found to outperform AIRS in the majority of cases.
Costa, E. P., Lorena, A. C., Carvalho, A. C. P. L. F., Freitas, A. A. and Holden, N. (2007) “Comparing several approaches for hierarchical classification of proteins with decision trees”, in Sagot, M.-F. and Walter, M. E. M. T. (eds.) Advances in Bioinformatics and Computational Biology: Second Brazilian Symposium on Bioinformatics. Advances in Bioinformatics and Computational Biology (Proc. of the Second Brazilian Symposium on Bioinformatics, BSB-2007), Lecture Notes in Bioinformatics 4643, Berlin, Germany: Springer, pp. 126-137. doi: 10.1007/978-3-540-73731-5_12.
Proteins are the main building blocks of the cell, and perform almost all the functions related to cell activity. Despite the recent advances in Molecular Biology, the function of a large amount of proteins is still unknown. The use of algorithms able to induce classification models is a promising approach for the functional prediction of proteins, whose classes are usually organized hierarchically. Among the machine learning techniques that have been used in hierarchical classification problems, one may highlight the Decision Trees. This paper describes the main characteristics of hierarchical classification models for Bioinformatics problems and applies three hierarchical methods based on the use of Decision Trees to protein functional classification datasets.
Costa, E. P., Lorena, A. C., Carvalho, A. C. and Freitas, A. A. (2007) “A review of performance evaluation measures for hierarchical classifiers”, in Drummond, C., Elazmeh, W., Japkowicz, N., and Macskassy, S. (eds.) Proceedings of the 2007 AAAI Workshop Evaluation Methods for Machine Learning II. Evaluation Methods for Machine Learning II: papers from the AAAI-2007 Workshop, AAAI Press, pp. 1-6.
Criteria for evaluating the performance of a classifier are an important part in its design. They allow to estimate the behavior of the generated classifier on unseen data and can be also used to compare its performance against the performance of classifiers generated by other classification algorithms. There are currently several performance measures for binary and flat classification problems. For hierarchical classification problems, where there are multiple classes which are hierarchically related, the evaluation step is more complex. This paper reviews the main evaluation metrics proposed in the literature to evaluate hierarchical classification models.
Holden, N. and Freitas, A. A. (2007) “A hybrid PSO/ACO algorithm for classification”, in Yu, T. (ed.) GECCO ’07 Proceedings of the 9th annual conference companion on Genetic and evolutionary computation. Proc. of the GECCO-2007 Workshop on Particle Swarms: The Second Decade, New York, USA: ACM, pp. 2745-2750. doi: 10.1145/1274000.1274080.
In a previous work we have proposed a hybrid Particle Swarm Optimisation/Ant Colony Optimisation (PSO/ACO) algorithm for the discovery of classification rules, in the context of data mining. Unlike a conventional PSO algorithm, this hybrid algorithm can directly cope with nominal attributes, without converting nominal values into numbers in a pre-processing phase. The design of this hybrid algorithm was motivated by the fact that nominal attributes are common in data mining, but the algorithm can in principle be applied to other kinds of problems involving nominal variables (though this paper focuses only on data mining). In this paper we propose several modifications to the original PSO/ACO algorithm. We evaluate the new version of the PSO/ACO algorithm (PSO/ACO2) in 16 public-domain real-world datasets often used to benchmark the performance of classification algorithms. PSO/ACO2 is evaluated with two different rule quality (particle "fitness") functions. We show that the choice of rule quality measure greatly effects the end performance of PSO/ACO2. In addition, the results show that PSO/ACO2 is very competitive with respect to two well-known rule induction algorithms.
Correa, E. S., Freitas, A. A. and Johnson, C. G. (2007) “Particle swarm and bayesian networks applied to attribute selection for protein functional classification”, in Yu, T. (ed.) GECCO ’07 Proceedings of the 9th annual conference companion on Genetic and evolutionary computation. Proc. of the GECCO-2007 Workshop on Particle Swarms: The Second Decade, New York, USA: ACM, pp. 2651-2658. doi: 10.1145/1274000.1274081.
The Discrete Particle Swarm (DPSO) algorithm is an optimizationmethod that belongs to the fertile paradigm of Swarm Intelligence. The DPSO was designed for the task of attribute selection and it deals with discrete variables in a straightforward manner. This work extends the DPSO algorithm in two ways. First, we enable the DPSO to select attributes for a Bayesian network algorithm, which is a much more sophisticated algorithm than the Naive Bayes classifier previously used by this algorithm. Second, we apply the DPSO to a challenging protein functional classification data set, involving a large number of classes to be predicted. The performance of the DPSO is compared to the performance of a Binary PSO on the task of selecting attributes in this challenging data set. The criteria used for comparison are: (1) maximizing predictive accuracy; and (2) finding the smallest subset of attributes.
Freitas, A. A. and de Carvalho, A. C. (2007) “A Tutorial on Hierarchical Classification with Applications in Bioinformatics.”, in Taniar, D. (ed.) Research and Trends in Data Mining Technologies and Applications. USA: IGI Publishing, pp. 175-208.
Freitas, A. A., McGarry, K. and Correa, E. S. (2007) “Integrating Bayesian networks and Simpson’s paradox in data mining”, in Russo, F. and Williamson, J. (eds.) Causality and Probability in the Sciences. United Kingdom: College Publications, pp. 43-62.
Miles, N., Freitas, A. A. and Serjeant, S. (2006) “Estimating photometric redshifts using genetic algorithms”, in Ellis, R., Allen, T., and Tuson, A. (eds.) Applications and Innovations in Intelligent Systems XIV Proceedings of AI-2006, the Twenty-sixth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence. Applications and innovations in intelligent systems XIV - Proc. of AI-2006, New York, USA: Springer, pp. 75-87. doi: 10.1007/978-1-84628-666-7_6.
Photometry is used as a cheap and easy way to estimate redshifts of galaxies, which would otherwise require considerable amounts of expensive telescope time. However, the analysis of photometric redshift datasets is a task where it is sometimes difficult to achieve a high classification accuracy. This work presents a custom Genetic Algorithm (GA) for mining the Hubble Deep Field North (HDF-N) datasets to achieve accurate IF-THEN classification rules. This kind of knowledge representation has the advantage of being intuitively comprehensible to the user, facilitating astronomers' interpretation of discovered knowledge. The GA is tested against the state of the art decision tree algorithm C5.0 [6] achieving significantly better results.
McGarry, K., Morris, N. and Freitas, A. A. (2006) “The integration of heterogeneous biological data using Bayesian networks”, in Ellis, R., Allen, T., and Tuson, A. (eds.) Applications and Innovations in Intelligent Systems XIV Proceedings of AI-2006, the Twenty-sixth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence. Applications and innovations in intelligent systems XIV - Proc. of AI-2006, Springer, pp. 44-57. doi: 10.1007/978-1-84628-666-7_4.
Bayesian networks can provide a suitable framework for the integration of highly heterogeneous experimental data and domain knowledge from experts and ontologies. In addition, they can produce interpretable and understandable models for knowledge discovery within complex domains by providing knowledge of casual and other relationships in the data. We have developed a system using Bayesian Networks that enables domain experts to express their knowledge and integrate it with a variety of other sources such as protein-protein relationships and to cross-reference this against new knowledge discovered by the proteomics experiments. The underlying Bayesian mechanism enables a form of hypothesis testing and evaluation.
Pappa, G. L. and Freitas, A. A. (2006) “Automatically Evolving Rule Induction Algorithms”, in Fuernkranz, J., Scheffer, T., and Spiliopoulou, M. (eds.) Machine Learning: ECML 2006 17th European Conference on Machine Learning. Proc. of the 17th European Conference on Machine Learning, Berlin: Springer, pp. 341-352. doi: 10.1007/11871842_34.
Research in the rule induction algorithm field produced many algorithms in the last 30 years. However, these algorithms are usually obtained from a few basic rule induction algorithms that have been often changed to produce better ones. Having these basic algorithms and their components in mind, this work proposes the use of Grammar-based Genetic Programming (GGP) to automatically evolve rule induction algorithms. The proposed GGP is evaluated in extensive computational experiments involving 11 data sets. Overall, the results show that effective rule induction algorithms can be automatically generated using GGP. The automatically evolved rule induction algorithms were shown to be competitive with well-known manually designed ones. The proposed approach of automatically evolving rule induction algorithms can be considered a pioneering one, opening a new kind of research area.
Chan, A. and Freitas, A. A. (2006) “A New Ant Colony Algorithm for Multi-Label Classification with Applications in Bioinformatics”, in Keijzer, M. (ed.) Proceedings of the 8th annual conference on Genetic and evolutionary computation. 2006 Genetic and Evolutionary Computation Conference, New York, USA: ACM, pp. 27-34. doi: 10.1145/1143997.1144002.
The conventional classification task of data mining can be called single-label classification, since there is a single class attribute to be predicted. This paper addresses a more challenging version of the classification task, where there are two or more class attributes to be predicted. We propose a new ant colony algorithm for the multi-label classification task. The new algorithm, called MuLAM (Multi-Label Ant-Miner) is a major extension of Ant-Miner, the first ant colony algorithm for discovering classification rules. We report results comparing the performance of MuLAM with the performance of three other classification techniques, namely the very simple majority classifier, the original Ant-Miner algorithm and C5.0, a very popular rule induction algorithm. The experiments were performed using five bioinformatics datasets, involving the prediction of several kinds of protein function.
Smaldon, J. and Freitas, A. A. (2006) “A New Version of the Ant-Miner Algorithm Discovering Unordered Rule Sets”, in Keijzer, M. (ed.) Proceedings of the 8th annual conference on Genetic and evolutionary computation. 2006 Genetic and Evolutionary Computation Conference, New York, USA: ACM, pp. 43-50. doi: 10.1145/1143997.1144004.
The Ant-Miner algorithm, first proposed by Parpinelli and colleagues, applies an ant colony optimization heuristic to the classification task of data mining to discover an ordered list of classification rules. In this paper we present a new version of the Ant-Miner algorithm, which we call Unordered Rule Set Ant-Miner, that produces an unordered set of classification rules. The proposed version was evaluated against the original Ant-Miner algorithm in six public-domain datasets and was found to produce comparable results in terms of predictive accuracy. However, the proposed version has the advantage of discovering more modular rules, i.e., rules that can be interpreted independently from other rules - unlike the rules in an ordered list, where the interpretation of a rule requires knowledge of the previous rules in the list. Hence, the proposed version facilitates the interpretation of discovered knowledge, an important point in data mining.
Noda, E. and Freitas, A. A. (2006) “Discovering knowledge nuggets with a genetic algorithm”, in Triantaphyllou, E. and Felici, G. (eds.) Data Mining and Knowledge Discovery Approaches Based on Rule Induction Techniques. New York, New York (USA): Springer, pp. 395-432. doi: 10.1007/0-387-34296-6_12.
Measuring the quality of a prediction rule is a difficult task, which can involve several criteria. The majority of the rule induction literature focuses on discovering accurate, comprehensible rules. In this chapter we also take these two criteria into account, but we go beyond them in the sense that we aim at discovering rules that are interesting (surprising) for the user. Hence, the search for rules is guided by a rule-evaluation function that considers both the degree of predictive accuracy and the degree of interestingness of candidate rules. The search is performed by two versions of a genetic algorithm (GA) specifically designed to the discovery of interesting rules - or “knowledge nuggets.” The algorithm addresses the dependence modeling task (sometimes called “generalized rule induction”), where different rules can predict different goal attributes. This task can be regarded as a generalization of the very well known classification task, where all rules predict the same goal attribute. This chapter also compares the results of the two versions of the GA with the results of a simpler, greedy rule induction algorithm to discover interesting rules.
Chan, A. and Freitas, A. A. (2006) “A New Classification-Rule Pruning Procedure for an Ant Colony Algorithm”, in Talbi, E.-G., Liardet, P., Collet, P., Lutton, E., and Schoenauer, M. (eds.) Artificial Evolution 7th International Conference. Artificial Evolution: Proc. 7th Int. Conf. (EA-2005, Lille, France, Oct. 2005), Berlin, Germany: Springer, pp. 25-36. doi: 10.1007/11740698_3.
This work proposes a new rule pruning procedure for Ant-Miner, an Ant Colony algorithm that discovers classification rules in the context of data mining. The performance of Ant-Miner with the new pruning procedure is evaluated and compared with the performance of the original Ant-Miner across several datasets. The results show that the new pruning procedure has a mixed effect on the performance of Ant-Miner. On one hand, overall it tends to decrease the classification accuracy more often than it improves it. On the other hand, the new pruning procedure in general leads to the discovery of classification rules that are considerably shorter, and so simpler (more easily interpretable by the users) than the rules discovered by the original Ant-Miner.
Carvalho, D. R., Freitas, A. A. and Ebecken, N. (2005) “Evaluating the correlation between objective rule interestingness measures and real human interest”, in Jorge, A., Torgo, L., Brazdil, P., Camacho, R., and Gama, J. (eds.) Knowledge Discovery in Databases: PKDD 2005 9th European Conference on Principles and Practice of Knowledge Discovery in Databases. Knowledge Discovery in Databases: Proc. of PKDD-2005. LNAI 3731, Berlin, Germany: Springer, pp. 453-461. doi: 10.1007/11564126_45.
In the last few years, the data mining community has proposed a number of objective rule interestingness measures to select the most interesting rules, out of a large set of discovered rules. However, it should be recalled that objective measures are just an estimate of the true degree of interestingness of a rule to the user, the so-called real human interest. The latter is inherently subjective. Hence, it is not clear how effective, in practice, objective measures are. More precisely, the central question investigated in this paper is: “how effective objective rule interestingness measures are, in the sense of being a good estimate of the true, subjective degree of interestingness of a rule to the user?” This question is investigated by extensive experiments with 11 objective rule interestingness measures across eight real-world data sets.
Polack, F. A., Stepney, S., Turner, H., Welch, P. H. and Barnes, F. R. (2005) “An Architecture for Modelling Emergence in CA-Like Systems”, in Capcarrere, M. S., Freitas, A. A., Bentley, P. J., Johnson, C. G., and Timmis, J. (eds.) Advances in Artificial Life 8th European Conference. Advances in Artificial Life, 8th European Conference on Artificial Life (ECAL 2005), Berlin, Germany: Springer, pp. 427-436. doi: 10.1007/11553090_44.
We consider models of emergence, adding downward causation to conventional models where causation permeates from low-level elements to high-level behaviour. We describe an architecture and prototype simulation medium for tagging and modelling emergent features in CA-like systems. This is part of ongoing work on engineering emergence.
Chu, D. and Rowe, J. (2005) “A Fitness-Landscape for the Evolution of Uptake Signal Sequences on Bacterial DNA”, in Capcarrere, M. S., Freitas, A. A., Bentley, P. J., Johnson, C. G., and Timmis, J. (eds.) Advances in Artificial Life 8th European Conference. Advances in Artificial Life: 8th European Conference, ECAL 2005, Berlin, Germany: Springer, pp. 845-853. doi: 10.1007/11553090_85.
In a recent article Chu et al. presented a computational model investigating the evolutionary origin of so-called uptake signal sequences in bacteria. In that contribution the authors used an agent-based approach. The main aim of this article is to understand the fitness-landscape on which the agents operate. We propose such a fitness- landscape and discuss its implications. This opens the possibility to use GAs for future simulations rather than the computationally expensive agent-based model.
Holden, N. and Freitas, A. A. (2005) “A hybrid particle swarm/ant colony algorithm for the classification of hierarchical biological data”, in Arabshahi, P. and Martinoli, A. (eds.) Proceedings 2005 IEEE Swarm Intelligence Symposium, 2005. 2005 IEEE Swarm Intelligence Symposium, IEEE, pp. 100-107. doi: 10.1109/SIS.2005.1501608.
This paper proposes a hybrid PSO/ACO algorithm for hierarchical classification, where the classes to be predicted are arranged in a tree-like hierarchy. The performance of the algorithm is evaluated on a challenging biological data set, involving the hierarchical functional classification of enzymes. The proposed algorithm is compared with an existing PSO for classification, which was also adapted for hierarchical classification.
Tsunoda, D. F., Lopes, H. S. and Freitas, A. A. (2005) “An evolutionary approach for motif discovery and transmembrane protein classification”, in Rothlauf, F. (ed.) Applications of Evolutionary Computing EvoWorkkshops 2005: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoMUSART, and EvoSTOC. Applications of Evolutionary Computing (Proc. of EvoBIO-2005: 3rd European Workshop on Evolutionary Bioinformatics), LNCS 3449, Berlin, Germany: Springer, pp. 105-114. doi: 10.1007/978-3-540-32003-6_11.
Proteins can be grouped into families according to their biological functions. This paper presents a system, named GAMBIT, which discovers motifs (particular sequences of amino acids) that occur very often in proteins of a given family but rarely occur in proteins of other families. These motifs are used to classify unknown proteins, that is, to predict their function by analyzing the primary structure. To search for motifs in proteins, we developed a GA with specially tailored operators for the problem. GAMBIT was compared with MEME, a web tool for finding motifs in the TransMembrane Protein DataBase. Motifs found by both methods were used to build a decision tree and classification rules, using, respectively, C4.5 and Prism algorithms. Motifs found by GAMBIT led to significantly better results, when compared with those found by MEME, using both classification algorithms.
Parpinelli, R. S., Lopes, H. S. and Freitas, A. A. (2005) “Classification-Rule Discovery with an Ant Colony Algorithm.”, in Khosrow-Pour, M. (ed.) Encyclopedia of Information Science and Technology. Hershey: Idea Group, pp. 420-424.
Secker, A. D., Freitas, A. A. and Timmis, J. (2005) “Towards a danger theory inspired artificial immune system for web mining”, in Scime, A. (ed.) Web Mining: applications and techniques. Idea Group, pp. 145-168.
The natural immune system exhibits many properties that are of interest to the area of web mining. Of particular interest is the dynamic nature of the immune system when compared with the dynamic nature of mining information from the web. As part of a larger project to construct a large-scale dynamic web-mining system, this chapter reports initial work on constructing an E-mail classifier system. The Artificial Immune System for Email Classification (AISEC) is described in detail and compared with a traditional approach of naive Bayesian classification. Results reported compare favorably with the Bayesian approach and this chapter highlights how the Danger Theory from immunology can be used to further improve the performance of such an artificial immune system.
Freitas, A. A. (2005) “Evolutionary Algorithms for Data Mining”, in Maimon, O. and Rokach, L. (eds.) Data Mining and Knowledge Discovery Handbook. Springer, pp. 435-467. doi: 10.1007/b107408.
Evolutionary Algorithms (EAs) are stochastic search algorithms inspired by the process of Darwinian evolution. The motivation for applying EAs to Data Mining is that they are robust, adaptive search techniques that perform a global search in the solution space. This chapter reviews mainly two kinds of EAs, viz. Genetic Algorithms (GAs) and Genetic Programming (GP), and discusses how EAs can be applied to several Data Mining tasks, namely: discovery of classification rules, clustering, attribute selection and attribute construction. It also discusses the basic idea of Multi-Objective EAs, based on the concept of Pareto dominance, which also has applications in Data Mining.
Goncalves, A., Freitas, A. A., Kato, R. and de Oliveira, R. (2005) “Using genetic algorithms to mine interesting dependence modeling rules”, in Hamza, M. (ed.) Databases and Applications. Proc. 23rd IASTED Int. Multi-Conference on Databases and Applications (DBA-2005), ACTA Press, pp. 1-6.
The challenge of KDD (Knowledge Discovery in Databases) is to efficiently and automatically analyze the available information, extracting useful knowledge from databases. We present GenMiner - a Data Mining tool for the Dependence Modeling task. GenMiner is a genetic algorithm based tool that searches for interesting rules involving correlated attributes on a relational database. Generated rules are evaluated on an individual basis, favoring accurate and surprising rules. The genetic individual encoding provided relational database integration. Chromosomes in our GA are represented by SQL queries. GenMiner evaluation was based on a public domain database including information about applications for nursery schools.
Pappa, G. L., Freitas, A. A. and Kaestner, C. A. (2004) “Multi-Objective Algorithms for Attribute Selection in Data Mining”, in Coello, C. C. and Lamont, G. (eds.) Applications of Multi-Objective Evolutionary Algorithms. World Scientific, pp. 603-626.
Alves, R. T., Delgado, M., Lopes, H. S. and Freitas, A. A. (2004) “Induction of fuzzy classification rules with an artificial immune system”, in Barros, A., Araujo, A., Yehia, H., and Teixeira, R. (eds.) Proceedings of the 8th Brazillian Symposium on Neural Networks. Proc. 8th Brazilian Symp. on Neural Networks, IEEE.
Fuzzy systems were designed to compute with uncertainties and linguistic information and allow us to develop mathematical tools for information processing. Artificial immune systems (AIS) consist of methods inspired by the biological immune system and designed for solving real-world problems. This work integrates these two kinds of systems, proposing a novel AIS for discovering fuzzy classification rules from data. The results of the proposed algorithm are compared with the results of C4.5Rules, a very popular algorithm for discovering classification rules.
Silla Jr, C. N., Pappa, G. L., Freitas, A. A. and Kaestner, C. A. (2004) “Automatic Text Summarization with Genetic Algorithm-Based Attribute Selection”, in Lemaitre, C., Reyes, C. A., and Gonzalez, J. A. (eds.) Advances in Artificial Intelligence – IBERAMIA 2004 9th Ibero-American Conference on AI. 9th Ibero-American Conference on Artificial Intelligence (IBERAMIA 2004), Berlin, Germany: Springer, pp. 305-314. doi: 10.1007/978-3-540-30498-2_31.
The task of automatic text summarization consists of generating a summary of the original text that allows the user to obtain the main pieces of information available in that text, but with a much shorter reading time. This is an increasingly important task in the current era of information overload. given the huge amount of text available in documents. In this paper the automatic text summarization is cast as a classification (supervised learning) problem, so that machine learning-oriented classification methods are used to produce summaries for documents based on a set of attributes describing those documents. The goal of the paper is to investigate the effectiveness of Genetic Algorithm (GA)-based attribute selection in improving the performance of classification algorithms solving the automatic text summarization task. Computational results are reported for experiments with a document base formed by news extracted from The Wall Street Journal of the TIPSTER collection-a collection that is often used as a benchmark in the text summarization literature.
Holden, N. and Freitas, A. A. (2004) “Web page classification with an ant colony algorithm”, in Parallel Problem Solving from Nature - PPSN VIII 8th International Conference. Parallel Problem Solving from Nature - PPSN VIII, LNCS 3242, Berlin, Germany: Springer, pp. 1092-1102. doi: 10.1007/978-3-540-30217-9_110.
This paper utilizes Ant-Miner - the first Ant Colony algorithm for discovering classification rules - in the field of web content mining, and shows that it is more effective than C5.0 in two sets of BBC and Yahoo web pages used in our experiments. It also investigates the benefits and dangers of several linguistics-based text preprocessing techniques to reduce the large numbers of attributes associated with web content mining.
Alves, R. T., Delgado, M., Lopes, H. S. and Freitas, A. A. (2004) “An artificial immune system for fuzzy-rule induction in data mining”, in Yao, X. (ed.) Parallel Problem Solving from Nature - PPSN VIII 8th International Conference. Parallel Problem Solving from Nature - PPSN VIII, LNCS 3242, Berlin, Germany: Springer, pp. 1011-1020. doi: 10.1007/978-3-540-30217-9_102.
This work proposes a classification-rule discovery algorithm integrating artificial immune systems and fuzzy systems. The algorithm consists of two parts: a sequential covering procedure and a rule evolution procedure. Each antibody (candidate solution) corresponds to a classification rule. The classification of new examples (antigens) considers not only the fitness of a fuzzy rule based on the entire training set, but also the affinity between the rule and the new example. This affinity must be greater than a threshold in order for the fuzzy rule to be activated, and it is proposed an adaptive procedure for computing this threshold for each rule. This paper reports results for the proposed algorithm in several data sets. Results are analyzed with respect to both predictive accuracy and rule set simplicity, and are compared with C4.5rules, a very popular data mining algorithm.
Ferreira, S. N., Freitas, A. A. and Avila, B. C. (2004) “Handling inconsistency in distributed data mining with paraconsistent logic”, in Guzelis, C., Alpaydin, E., Yakhno, T., and Gurgen, F. (eds.) Proceedings of the Thirteenth Turkish Symposium on Artificial Intelligence and Neural Networks. Proc. 13th Turkish Symposium on Artificial Intelligence and Neural Networks (TAINN-2004), pp. 19-28.
This paper addresses the problem of inconsistent rule subsets in distributed data mining. In this scenario, N rule subsets are independently discovered from N different data subsets. This can result in inconsistent rules – i.e. rules with the same antecedent but different class predictions – across the N rule subsets. In order to handle these rule inconsistencies, this paper proposes a paraconsistent logic-based method for post-processing different rule subsets discovered by a rule induction algorithm in a distributed data mining scenario. The proposed method produces a global inconsistency-free rule set by using principles and concepts of paraconsistent logic, a relatively novel kind of logic developed specifically for inconsistency handling.
Secker, A. D., Freitas, A. A. and Timmis, J. (2003) “AISEC: An Artificial Immune System for E-mail Classification”, in Sarker, R. A., Reynolds, R., Abbass, H. A., Kay-Chen, T., McKay, R., Essam, D., and Gedeon, T. (eds.) The 2003 Congress on Evolutionary Computation. Proceedings of the Congress on Evolutionary Computation, IEEE, pp. 131-139. doi: 10.1109/CEC.2003.1299566.
With the increase in information on the Internet, the strive to find more effective tools for distinguishing between interesting and non-interesting material is increasing. Drawing analogies from the biological immune system, this paper presents an immune-inspired algorithm called AISEC that is capable of continuously classifying electronic mail as interesting and non-interesting without the need for re-training. Comparisons are drawn with a nave Bayesian classifier and it is shown that the proposed system performs as well as the nave Bayesian system and has a great potential for augmentation
Carvalho, D. R., Freitas, A. A. and Ebecken, N. (2003) “A critical review of rule surprisingness measures”, in Ebecken, N., Brebbia, C., and Zanasi, A. (eds.) Data Mining. Proc. Data Mining IV - Int. Conf. on Data Mining, WIT Press, pp. 545-556. doi: 10.2495/DATA030531.
In data mining it is usually desirable that discovered knowledge have some characteristics such as being as accurate as possible, comprehensible and surprising to the user. The vast majority of data mining algorithms produce, as part of their results, information of a statistical nature that allows the user to assess how accurate and reliable the discovered knowledge is. However, in many cases this is not enough for the user. Even if discovered knowledge is highly accurate from a statistical point of view, it might not be interesting for the user. Few data mining algorithms produce, as part of their results, a measure of the degree of surprisingness of discovered knowledge. However, these measures can be computed in a post-processing phase, as a form of additional evaluation of the quality of discovered knowledge, complementing (rather than replacing) statistical measures of discovered knowledge accuracy. This papers presents a review of four measures of classification-rule surprisingness, discussing their main characteristics, advantages and disadvantages. Hence, the main contribution of this paper is to improve our understanding of these rule surprisingness measures, which is a step towards solving the very difficult problem of selecting the "best" rule surprisingness measure for a given application domain.
Parpinelli, R. S., Lopes, H. S. and Freitas, A. A. (2003) “Mining comprehensible rules from data with an ant colony algorithm”, in Bittencourt, G. and Ramalho, G. L. (eds.) Advances in Artificial Intelligence 16th Brazilian Symposium on Artificial Intelligence. Proc. 16th Brazilian Symp. on Artificial Intelligence (SBIA-2002). Lecture Notes in Artificial Intelligence 2507, Berlin, Germany: Springer, pp. 259-269. doi: 10.1007/3-540-36127-8_25.
This work describes an algorithm for data mining called Ant-Miner (Ant Colony-based Data Miner).The goal of Ant-Miner is to extract classification rules from data. The algorithm is inspired by both research on the behavior of real ant colonies and some data mining concepts and principles. We compare the performance of Ant-Miner with CN2, a well-known data mining algorithm for classification, in six public domain data sets. The results provide evidence that: (a) Ant-Miner is competitive with CN2 with respect to predictive accuracy; and (b) The rule lists discovered by Ant-Miner are considerably simpler (smaller) than those discovered by CN2.
Neto, J. L., Freitas, A. A. and Kaestner, C. A. (2003) “Automatic text summarization using a machine learning approach”, in Bittencourt, G. and Ramalho, G. L. (eds.) Advances in Artificial Intelligence 16th Brazilian Symposium on Artificial Intelligence. Proc. 16th Brazilian Symp. on Artificial Intelligence (SBIA-2002). Lecture Notes in Artificial Intelligence 2507, Springer, pp. 205-215. doi: 10.1007/3-540-36127-8_20.
In this paper we address the automatic summarization task. Recent research works on extractive-summary generation employ some heuristics, but few works indicate how to select the relevant features. We will present a summarization procedure based on the application of trainable Machine Learning algorithms which employs a set of features extracted directly from the original text. These features are of two kinds: statistical - based on the frequency of some elements in the text; and linguistic - extracted from a simplified argumentative structure of the text. We also present some computational results obtained with the application of our summarizer to some well known text databases, and we compare these results to some baseline summarization procedures.
Otero, F. E., Silva, M. M., Freitas, A. A. and Nievola, J. C. (2003) “Genetic Programming for Attribute Construction in Data Mining”, in Ryan, C., Keijzer, M., Poli, R., Soule, T., Tsang, E., and Costa, E. (eds.) Genetic Programming 6th European Conference. Genetic Programming: Proc. 6th European Conference (EuroGP-2003)., Berlin, Germany: Springer, pp. 384-393. doi: 10.1007/3-540-36599-0_36.
For a given data set, its set of attributes defines its data space representation. The quality of a data space representation is one of the most important factors influencing the performance of a data mining algorithm. The attributes defining the data space can be inadequate, making it difficult to discover high-quality knowledge. In order to solve this problem, this paper proposes a Genetic Programming algorithm developed for attribute construction. This algorithm constructs new attributes out of the original attributes of the data set, performing an important preprocessing step for the subsequent application of a data mining algorithm.
Bojarczuk, C. C., Lopes, H. S. and Freitas, A. A. (2003) “An innovative application of a constrained-syntax genetic programming system to the problem of predicting survival of patients”, in Ryan, C., Keijzer, M., Poli, R., Soule, T., Tsang, E., and Costa, E. (eds.) Genetic Programming 6th European Conference. Genetic Programming: Proc. 6th European Conference (EuroGP-2003), Berlin, Germany: Springer, pp. 11-21. doi: 10.1007/3-540-36599-0_2.
This paper proposes a constrained-syntax genetic programming (GP) algorithm-for discovering classification rules in medical data sets. The proposed GP contains several syntactic constraints to be enforced by the system using a disjunctive normal form representation, so that individuals represent valid rule sets that are easy to interpret. The GP is compared with C4.5 in a real-world medical data set. This data set represents a difficult classification problem, and a new preprocessing method was devised for mining the data.
Freitas, A. A. (2003) “A survey of evolutionary algorithms for data mining and knowledge discovery”, in Ghosh, A. and Tsutsui, S. (eds.) Advances in Evolutionary Computation. Berli: Springer-Verlag, pp. 819-845. Available at: http://www.cs.kent.ac.uk/pubs/2002/1582.
Noda, E., Freitas, A. A. and Yamakami, A. (2002) “A Distributed-Population GA for Discovering Interesting Prediction Rules”, in Benitez, J. and Gordon, O. (eds.) Advances in Soft Computing: Engineering Design and Manufacturing. 7th Online World Conference on Soft Computing in Industrial Applications (WSC7), London: Springer, pp. 287-296. doi: 10.1007/978-1-4471-3744-3_28.
In data mining, the quality of prediction rules basically involve three criteria: accuracy, comprehensible and interestingness. The majority of the rule induction, literature focuses on discovering accurate, comprehensible rules. In this paper we also take these two criteria into account, but we go beyond them in the sense that we aim at discovering rules that are interesting (surprising) for the user. The search is performed by distributed genetic algorithm (DGA) specifically designed to the discovery of interesting rules.
Pappa, G. L., Freitas, A. A. and Kaestner, C. A. (2002) “A multiobjective genetic algorithm for attribute selection”, in Lofti, A., Garibaldi, J., and John, R. (eds.) Proceedings Of The 4th International Conference On Recent Advances In Soft Computing. Proc. 4th Int. Conf. on Recent Advances in Soft Computing (RASC-2002), Nottingham Trent University, pp. 116-121.
The problem of feature selection in data mining is an important real-world problem that involves multiple objectives to be simultaneously optimized. In order to tackle this problem this work proposes a multiobjective genetic algorithm for feature selection based on the wrapper approach. The algorithm’s main goal is to find the best subset of features that minimizes both the error rate and the size of the tree discovered by a classification algorithm, namely C4.5, using the Pareto dominance concept
Parpinelli, R. S., Lopes, H. S. and Freitas, A. A. (2002) “An Ant Colony Algorithm for Classification Rule Discovery”, in Abbass, H. A., Sarker, R. A., and Newton, C. S. (eds.) Data Mining: a Heurstic Approach. London: Idea Group Publishing, pp. 191-208.
Real life problems are known to be messy, dynamic and multi-objective, and involve high levels of uncertainty and constraints. Because traditional problem-solving methods are no longer capable of handling this level of complexity, heuristic search methods have attracted increasing attention in recent years for solving such problems. Inspired by nature, biology, statistical mechanics, physics and neuroscience, heuristics techniques are used to solve many problems where traditional methods have failed. Data Mining: A Hueristic Approach will be a repository for the applications of these techniques in the area of data mining.
Freitas, A. A. (2002) “A Review of Evolutionary Algorithms for E-Commerce”, in Segovia, J., Szczepaniak, P., and Niedzwiedzinski, M. (eds.) E-Commerce and Intelligent Methods. Studies in Fuzziness and Soft Computing. Heidelberg, Berlin: Springer-Verlag, pp. 159-179.
Evolutionary Algorithms (EAs) are adaptive algorithms based on the Darwinian principle of natural selection. Intuitively, their adaptive nature makes them suitable for highly dynamic environments, which is often the case in e-commerce applications. This chapter presents a review of EAs in general. Then it discusses several EAs developed for e-commerce applications, focusing on three kinds of e-commerce related tasks, namely: information retrieval on the web, discovery of negotiation strategies and improvement of web-page presentation.
Otero, F. E., Silva, M. M. and Freitas, A. A. (2002) “Genetic Programming for Attribute Construction in Data Mining”, in Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. Proc Genetic and Evolutionary Computation Conf (GECCO-2002), San Francisco, California, USA: Morgan Kaufmann, pp. 1270-1270.
Freitas, A. A. (2002) “Evolutionary Computation”, in Klosgen, W. and Zytkow, J. (eds.) Handbook of Data Mining and Knowledge Discovery. New York: Oxford University Press.
Romao, W., Freitas, A. A. and Pacheco-Lopez, R. (2002) “A Genetic Algorithm for Discovering Interesting Fuzzy Prediction Rules: applications to science and technology data”, in Langdon, W. B. and Cantu-Paz, E. (eds.) Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2002), San Francisco, California, USA: Morgan Kaufmann, pp. 1188-1195.
Data mining consists of extracting knowledge from data. This paper addresses the discovery of knowledge in the form of prediction IF-THEN rules, which are a popular form of knowledge representation in data mining. In this context, we propose a new Genetic Algorithm (GA) designed specifically for discovering interesting fuzzy prediction rules. The GA searches for prediction rules that are interesting in the sense of being surprising for the user. More precisely, a prediction rule is considered interesting (or surprising) to the extent that it represents knowledge that not only was previously unknown by the user but also contradicts the original believes of the user. In addition, the use of fuzzy logic helps to improve the comprehensibility of the rules discovered by the GA, due to the use of linguistic terms that are natural for the user. The proposed GA is applied to a real-world science & technology data set, containing data about the scientific production of researchers. Experiments were performed to evaluate both the predictive accuracy and the degree of interestingness (or surprisingness) of the rules discovered by the GA, and the results were found to be satisfactory. 1
Carvalho, D. R. and Freitas, A. A. (2002) “A genetic algorithm with sequential niching for discovering small-disjunct rules”, in Langdon, W. B. and Cantu-Paz, E. (eds.) Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. Proceedings Genetic and Evolutionary Computation Conference (GECCO-2002), San Francisco, California, USA: Morgan Kaufmann, pp. 1035-1042.
This work addresses the well-known classification task of data mining. In this context, small disjuncts are classification rules covering a small number of examples. One approach for coping with small disjuncts, proposed in our previous work, consists of using a decision-tree/genetic algorithm method. The basic idea is that examples belonging to large disjuncts are classified by rules produced by a decision-tree algorithm (C4.5), while examples belonging to small disjuncts are classified by a genetic algorithm (GA) designed for discovering small-disjunct rules. In this paper we follow this basic idea, but we propose a new GA which consists of several major modifications to the original GA used for coping with small disjuncts. The performance of the new GA is extensively evaluated by comparing it with two versions of C4.5, across several data sets, and with several different sizes of small disjuncts.
Larsen, O., Freitas, A. A. and Nievola, J. C. (2002) “Constructing X-of-N Attributes with a Genetic Algorithm”, in Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. Proc Genetic and Evolutionary Computation Conf (GECCO-2002), San Francisco, California, USA: Morgan Kaufmann.
The predictive accuracy obtained by a classification algorithm is strongly dependent on the quality of the attributes of the data being mined. When the attributes are little relevant for predicting the class of a record, the predictive accuracy will tend to be low. To combat this problem, a natural approach consists of constructing new attributes out of the original attributes. Many attribute construction algorithms work by simply constructing conjunctions and/or disjunctions of attribute-value pairs. This kind of representation has a limited expressiveness power to represent attribute interactions. A more expressive representation is X-of-N [Zheng 1995]. An X-of-N condition consists of a set of N attribute-value pairs. The value of an X-of-N condition for a given example (record) is the number of attribute-value pairs of the example that match with the N attribute-value pairs of the condition. For instance, consider the following X-of-N condition: X-of-{"Sex = male", "Age < 21", "Salary = high"}. Suppose that a given example has the following attribute-value pairs: {"Sex = male", "Age = 51", "Salary = high"}. This example has 2 out of the 3 attribute-value pairs of the X-of-N condition, so that the value of the X-of-N condition for this example is 2.
Carvalho, D. R. and Freitas, A. A. (2001) “An Immunological Algorithm for Discovering Small-disjunct Rules in Data Mining”, in Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. Proc Graduate Student Workshop at GECCO-2001, San Francisco, California, USA: Morgan Kaufmann, pp. 401-404.
Parpinelli, R. S., Lopes, H. S. and Freitas, A. A. (2001) “An ant colony based system for data mining: applications to medical data”, in Spector, L. E. and Goodman, E. D. (eds.) Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. Proc. 2001 Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, California, USA: Morgan Kaufmann, pp. 791-798.
This work describes an algorithm for rulediscovery in databases called AntMiner. Theobjective of the algorithm is the extraction ofclassification rules to be applied to unseen dataas a decision aid. The algorithm used todiscover such rules is inspired in the behaviorof a real ant colony, as well as some conceptsof information theory and data mining.AntMiner was applied to medical databases toobtain classification rules
Santos Correa, E., Steiner, M. T. A., Freitas, A. A. and Carnieri, C. (2001) “A Genetic Algorithm for the P-median Problem”, in Spector, L. E. and Goodman, E. D. (eds.) Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. Proc. 2001 Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, California, USA: Morgan Kaufmann, pp. 1268-1275.
Facility-location problems have several applications in telecommunications, industrial transportation and distribution, etc. One of the most well-known facility-location problems is the p-median problem. This work addresses an application of the capacitated p-median problem to a real-world problem. We propose a genetic algorithm (GA) to solve the capacitated pmedian problem. The proposed GA uses not only conventional genetic operators but also a new heuristic ''hypermutation'' operator proposed in this work. The proposed GA is compared with a tabu search algorithm.
Mendes, R., Voznika, F., Freitas, A. A. and Nievola, J. C. (2001) “Discovering fuzzy classification rules with genetic programming and co-evolution”, in Principles of Data Mining and Knowledge Discovery 5th European Conference. Principles of Data Mining and Knowledge Discovery (Proc. 5th European Conference PKDD 2001) - Lecture Notes in Artificial Intelligence, Berlin, Germany: Springer, pp. 314-325. doi: 10.1007/3-540-44794-6_26.
In essence, data mining consists of extracting knowledge from data. This paper proposes a co-evolutionary system for discovering fuzzy classification rules. The system uses two evolutionary algorithms: a genetic programming (GP) algorithm evolving a population of fuzzy rule sets and a simple evolutionary algorithm evolving a population of membership function definitions. The two populations co-evolve, so that the final result of the co-evolutionary process is a fuzzy rule set and a set of membership function definitions which are well adapted to each other. In addition, our system also has some innovative ideas with respect to the encoding of GP individuals representing rule sets. The basic idea is that our individual encoding scheme incorporates several syntactical restrictions that facilitate the handling of rule sets in disjunctive normal form. We have also adapted GP operators to better work with the proposed individual encoding scheme.
Conference or workshop item
Ribeiro, C. and Freitas, A. (2021) “Constructed temporal features for longitudinal classification of human ageing data”, in. 2021 IEEE 9th International Conference on Healthcare Informatics (ICHI), IEEE, pp. 106-112. doi: 10.1109/ICHI52183.2021.00027.
Standard classification algorithms ignore the time-related information contained in longitudinal data, as they do not consider the time indexes of the features’ different measurements. Accounting for temporal patterns may improve the algorithms’ performance, when applied to longitudinal data. Representing temporal patterns in the data itself has the advantage that those patterns are generic enough to be used with existing powerful classification algorithms, without requiring the design of new and more complex algorithms to exploit them. In this article, we propose 6 different types of constructed temporal features (3 of them being novel contributions), calculated from the values of the different feature measurements taken over time, and investigate whether adding those constructed temporal features to the original longitudinal dataset improves the classification model’s predictive accuracy. Our experiments involved 20 real-world longitudinal datasets created from a human-ageing study, and showed that the proposed approach of adding the constructed temporal features to the original feature set produced better classifiers overall.
Maia, M., Plastino, A. and Freitas, A. A. (2021) “An ensemble of naïve Bayes classifiers for uncertain categorical data”, in. 21st IEEE International Conference on Data Mining (ICDM 2021), Los Alamitos, CA, USA: IEEE Computer Society – Conference Publishing Services, pp. 1216-1221. doi: 10.1109/ICDM51629.2021.00148.
Pomsuwan, T. and Freitas, A. A. (2020) “Adapting random forests to cope with heavily censored datasets in survival analysis”, in. 2020 European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2020), dblp, pp. 697-702. Available at: https://www.esann.org/sites/default/files/proceedings/2020/ES2020-117.pdf.
We address a survival analysis task where the goal is to predict the time passed until a subject is diagnosed with an age-related disease. The main challenge is that subjects’ data are very often censored, i.e., their time to diagnosis is only partly known. We propose a new Random Forest variant to cope with censored data, and evaluate it in experiments predicting the time to diagnosis of 8 age-related diseases, for data from the English Longitudinal Study of Ageing (ELSA) database. In these experiments, the proposed Random Forest variant, in general, outperformed a well-known Random Forest variant for censored data.
Ribeiro, C. and Freitas, A. A. (2020) “A New Random Forest Method for Longitudinal Data Classification Using a Lexicographic Bi-Objective Approach”, in. 2020 IEEE Symposium Series on Computational Intelligence (SSCI 2020), IEEE.
Wan, C. and Freitas, A. A. (2020) “Hierarchical Dependency Constrained Averaged One-Dependence Estimators Classifiers for Hierarchical Feature Spaces.”, in. 10th International Conference on Probabilistic Graphic Models (PGM 2020), pp. 557-568. doi: http://proceedings.mlr.press/v138/wan20a.html.
Ovchinnik, S., Otero, F. E. and Freitas, A. A. (2019) “Monotonicity Detection and Enforcement in Longitudinal Classification”, in Bramer, M. and Petridis, M. (eds.). 39th SGAI International Conference on Artificial Intelligence, AI 2019, Springer. doi: 10.1007/978-3-030-34885-4_5.
Longitudinal datasets contain repeated measurements of the same variables at different points in time, which can be used by researchers to discover useful knowledge based on the changes of the data over time. Monotonic relations often occur in real-world data and need to be preserved in data mining models in order for the models to be acceptable by users. We propose a new methodology for detecting monotonic relations in longitudinal datasets and applying them in longitudinal classification model construction. Two different approaches were used to detect monotonic relations and include them into the classification task. The proposed approaches are evaluated using data from the English Lon- gitudinal Study of Ageing (ELSA) with 10 different age-related diseases used as class variables to be predicted. A gradient boosting algorithm (XGBoost) is used for constructing classification models in two scenarios: enforcing and not enforcing the constraints. The results show that enforcement of monotonicity constraints can consistently improve the predictive accuracy of the constructed models. The produced models are fully monotonic according to the monotonicity constraints, which can have a positive impact on model acceptance in real world applications.
Freitas, A. A. (2019) “Automated machine learning for studying the trade-off between predictive accuracy and interpretability”, in. Third IFIP International Cross-Domain Conference for Machine Learning and Knowledge Extraction (CD-MAKE 2019), Springer, pp. 48-66. doi: 10.1007/978-3-030-29726-8_4.
Automated Machine Learning (Auto-ML) methods search for the best classification algorithm and its best hyper-parameter settings for each input dataset. Auto-ML methods normally maximize only predictive accuracy, ignoring the classification model’s interpretability – an important criterion in many applications. Hence, we propose a novel approach, based on Auto-ML, to investigate the trade-off between the predictive accuracy and the interpretability of classification-model representations. The experiments used the Auto-WEKA tool to investigate this trade-off. We distinguish between white box (interpretable) model representations and two other types of model representations: black box (non-interpretable) and grey box (partly interpretable). We consider as white box the models based on the following 6 interpretable knowledge representations: decision trees, If-Then classification rules, decision tables, Bayesian network classifiers, nearest neighbours and logistic regression. The experiments used 16 datasets and two runtime limits per Auto-WEKA run: 5 h and 20 h. Overall, the best white box model was more accurate than the best non-white box model in 4 of the 16 datasets in the 5-hour runs, and in 7 of the 16 datasets in the 20-hour runs. However, the predictive accuracy differences between the best white box and best non-white box models were often very small. If we accept a predictive accuracy loss of 1% in order to benefit from the interpretability of a white box model representation, we would prefer the best white box model in 8 of the 16 datasets in the 5-hour runs, and in 10 of the 16 datasets in the 20-hour runs.
Miranda, E. S., Fabris, F., Nascimento, C. G. M., Freitas, A. A. and Oliveira, A. C. M. (2018) “Meta-Learning for Recommending Metaheuristics for the MaxSAT Problem”, in. 2018 7th Brazilian Conference on Intelligent Systems (BRACIS), USA: IEEE, pp. 169-174. doi: 10.1109/BRACIS.2018.00037.
It is of great interest to build recommendation systems capable of choosing the best solver for a particular problem of a combinatorial optimisation task given past runs of solvers in various problems of that optimisation task. In this paper, a meta-learning approach is proposed to predict which metaheuristic is the best solver for MaxSAT problems. The proposal includes the creation of new meta-features derived from graph descriptions of MaxSAT problems and an interpretation of the meta-model. Our approach successfully selected the best metaheuristic to solve each problem in 87% of the cases. Also, the new meta-features have shown to be as good as the state-of-the-art meta-features, and the meta-model interpretation found interesting problem-specific knowledge.
Xavier-Junior, J. C., Freitas, A. A., Feitosa-Neto, A. and Ludermir, T. B. (2018) “A Novel Evolutionary Algorithm for Automated Machine Learning Focusing on Classifier Ensembles”, in. 2018 7th Brazilian Conference on Intelligent Systems (BRACIS), USA: IEEE, pp. 462-467. doi: 10.1109/BRACIS.2018.00086.
Automated Machine Learning (Auto-ML) is an emerging area of ML which consists of automatically selecting the best ML algorithm and its best hyper-parameter settings for a given input dataset, by doing a search in a large space of candidate algorithms and settings. In this work we propose a new Evolutionary Algorithm (EA) for the Auto-ML task of automatically selecting the best ensemble of classifiers and their hyper-parameter settings for an input dataset. The proposed EA was compared against a version of the well-known Auto-WEKA method adapted to search in the same space of algorithms and hyper-parameter settings as the EA. In general, the EA obtained significantly smaller classification error rates than that Auto-WEKA version in experiments with 15 classification datasets.
Freitas, A. A., Pinto Junior, J. A., Plastino, A. and Neumann, N. M. (2018) “Is P-value<0.05 Enough? Two Case Studies in Classifiers Evaluation”, in. XV National Meeting of Artificial and Computational Intelligence (ENIAC), pp. 94-103. doi: 10.5753/eniac.2018.4407.
A common tool used in the process of comparing classifiers is the statistical significance analysis, performed through the hypothesis test. However, there are many researchers attempting to obtain statistical significance through a blinding evaluating of the p-value<0.05 condition, ignoring important concepts such as the effect size and statistical power. This work highlights possible problems caused by the misuse of the hypothesis test and how the effect size and the statistical power can provide information for a better decision making. Therefore, two case studies applying Student’s t-test and Wilcoxon signed-rank test for the comparison of two classifiers are presented.
Goncalves, E., Freitas, A. A. and Plastino, A. (2018) “A survey of genetic algorithms for multi-label classification”, in. 2018 IEEE Congress on Evolutionary Computation (CEC 2018), New York, NY, USA: IEEE, pp. 981-988. doi: 10.1109/CEC.2018.8477927.
In recent years, multi-label classification (MLC) has become an emerging research topic in big data analytics and machine learning. In this problem, each object of a dataset may belong to multiple class labels and the goal is to learn a classification model that can infer the correct labels of new, previously unseen, objects. This paper presents a survey of genetic algorithms (GAs) designed for MLC tasks. The study is organized in three parts. First, we propose a new taxonomy focused on GAs for MLC. In the second part, we provide an up-to-date overview of the work in this area, categorizing the approaches identified in the literature with respect to the taxonomy. In the third and last part, we discuss some new ideas for combining GAs with MLC.
da Silva, P., Plastino, A. and Freitas, A. A. (2018) “A Novel Genetic Algorithm for Feature Selection in Hierarchical Feature Spaces”, in. SIAM International Conference on Data Mining (SDM18), pp. 738-746. doi: 10.1137/1.9781611975321.83.
Pomsuwan, T. and Freitas, A. A. (2017) “Feature Selection for the Classification of Longitudinal Human Ageing Data”, in. Data Mining Workshops (ICDMW), 2017 IEEE International Conference, USA: IEEE, pp. 739-746. doi: 10.1109/ICDMW.2017.102.
We propose a new variant of the Correlation-based Feature Selection (CFS) method for coping with longitudinal data where variables are repeatedly measured across different time points. The proposed CFS variant is evaluated on ten datasets created using data from the English Longitudinal Study of Ageing (ELSA), with different age-related diseases used as the class variables to be predicted. The results show that, overall, the proposed CFS variant leads to better predictive performance than the standard CFS and the baseline approach of no feature selection, when using Naïve Bayes and J48 decision tree induction as classification algorithms (although the difference in performance is very small in the results for J4.8). We also report the most relevant features selected by J48 across the datasets.
Martire, I., da Silva, P., Plastino, A., Fabris, F. and Freitas, A. A. (2017) “A novel probabilistic Jaccard distance measure for classification of sparse and uncertain data”, in Rebeiro de Faria Paiva, E., Merschmann, L., and Cerri, R. (eds.). 5th Brazilian Symposium on Knowledge Discovery, Mining and Learning (KDMiLe), pp. 81-88. Available at: http://www.facom.ufu.br/~kdmile/proceedings/anais-kdmile-2017.pdf.
Cramer, S., Kampouridis, M., Freitas, A. A. and Alexandridis, A. (2017) “Pricing Rainfall Based Futures Using Genetic Programming”, in. 20th European Conference, EvoApplications: European Conference on the Applications of Evolutionary Computation, Springer, pp. 17-33. doi: 10.1007%2F978-3-319-55849-3_2.
Rainfall derivatives are in their infancy since starting trading on the Chicago Mercantile Exchange (CME) since 2011. Being a relatively new class of financial instruments there is no generally recognised pricing framework used within the literature. In this paper, we propose a novel framework for pricing contracts using Genetic Programming (GP). Our novel framework requires generating a risk-neutral density of our rainfall predictions generated by GP supported by Markov chain Monte Carlo and Esscher transform. Moreover, instead of having a single rainfall model for all contracts, we propose having a separate rainfall model for each contract. We compare our novel framework with and without our proposed contract-specific models for pricing against the pricing performance of the two most commonly used methods, namely Markov chain extended with rainfall prediction (MCRP), and burn analysis (BA) across contracts available on the CME. Our goal is twofold, (i) to show that by improving the predictive accuracy of the rainfall process, the accuracy of pricing also increases. (ii) contract-specific models can further improve the pricing accuracy. Results show that both of the above goals are met, as GP is capable of pricing rainfall futures contracts closer to the CME than MCRP and BA. This shows that our novel framework for using GP is successful, which is a significant step forward in pricing rainfall derivatives.
Cramer, S., Kampouridis, M. and Freitas, A. A. (2016) “Feature Engineering for Improving Financial Derivatives-based Rainfall Prediction”, in. IEEE World Congress on Evolutionary Computation.
Rainfall is one of the most challenging variables to predict, as it exhibits very unique characteristics that do not exist in other time series data. Moreover, rainfall is a major component and is essential for applications that surround water resource planning. In particular, this paper is interested in extending previous work carried out on the prediction of rainfall using Genetic Programming (GP) for rainfall derivatives. Currently in the rainfall derivatives literature, the process of predicting rainfall is dominated by statistical models, namely using a Markov-chain extended with rainfall prediction (MCRP). In this paper we further extend our new methodology by looking at the effect of feature engineering on the rainfall prediction process. Feature engineering will allow us to extract additional information from the data variables created. By incorporating feature engineering techniques we look to further tailor our GP to the problem domain and we compare the performance of the previous GP, which previously statistically outperformed MCRP, against our new GP using feature engineering on 21 different data sets of cities across Europe and report the results. The goal is to see whether GP can outperform its predecessor without extra features, which acts as a benchmark. Results indicate that in general GP using extra features significantly outperforms a GP without the use of extra features.
Cramer, S., Kampouridis, M. and Freitas, A. A. (2016) “A Genetic Decomposition Algorithm for Predicting Rainfall within Financial Weather Derivatives”, in. Genetic and Evolutionary Computation Conference (GECCO 2016).
Regression problems provide some of the most challenging research opportunities, where the predictions of such domains are critical to a specific application. Problem domains that exhibit large variability and are of chaotic nature are the most challenging to predict. Rainfall being a prime example, as it exhibits very unique characteristics that do not exist in other time series data. Moreover, rainfall is essential for applications that surround financial securities such as rainfall derivatives. This paper is interested in creating a new methodology for increasing the predictive accuracy of rainfall within the problem domain of rainfall derivatives. Currently, the process of predicting rainfall within rainfall derivatives is dominated by statistical models, namely Markov-chain extended with rainfall prediction (MCRP). In this paper, we propose a novel algorithm for decomposing rainfall, which is a hybrid Genetic Programming/Genetic Algorithm (GP/GA) algorithm. Hence, the overall problem becomes easier to solve. We compare the performance of our hybrid GP/GA, against MCRP, Radial Basis Function and GP without decomposition. We aim to show the effectiveness that a decomposition algorithm can have on the problem domain. Results show that in general decomposition has a very positive effect by statistically outperforming GP without decomposition and MCRP.
Jungjit, S., Freitas, A. A., Michaelis, M. and Cinatl, J. (2014) “Extending multi-label feature selection with KEGG pathway information for microarray data analysis”, in. 2014 IEEE International Conference on Computational Intelligence in Bioinformatics and Computational Biology.
Jungjit, S., Freitas, A. A., Michaelis, M. and Cinatl, J. (2013) “Two extensions to multi-lable correlation-based feature selection: a case study in bioinformatics.”, in. 2013 IEEE International Conference on Systems, Man and Cybernetics (SMC-2013), IEEE Press, pp. 1519-1524.
Otero, F. E. and Freitas, A. A. (2013) “Improving the interpretability of classification rules discovered by an ant colony algorithm.”, in. 2013 Genetic and Evolutionary Computation Conference (GECCO’13), New York, NY, USA.: ACM Press, pp. 73-80.
The vast majority of Ant Colony Optimization (ACO) al- gorithms for inducing classification rules use an ACO-based procedure to create a rule in an one-at-a-time fashion. An improved search strategy has been proposed in the cAnt- MinerPB algorithm, where an ACO-based procedure is used to create a complete list of rules (ordered rules)—i.e., the ACO search is guided by the quality of a list of rules, instead of an individual rule. In this paper we propose an extension of the cAnt-MinerPB algorithm to discover a set of rules (unordered rules). The main motivation for discovering a set of rules is to improve the interpretation of individual rules and evaluate the impact on the predictive accuracy of the algorithm. We also propose a new measure to evaluate the interpretability of the discovered rules to mitigate the fact that the commonly-used model size measure ignores how the rules are used to make a class prediction. Comparisons with state-of-the-art rule induction algorithms and the cAnt-MinerPB producing ordered rules are also presented.
Medland, M., Otero, F. E. and Freitas, A. A. (2012) “Improving the cAnt-MinerPB Classification Algorithm”, in Dorigo, M., Birattari, M., Blum, C., Christensen, A. L., Engelbrecht, A. P., Groß, R., and Stützle, T. (eds.). 8th International Conference on Swarm Intelligence (ANTS 2012), Springer Berlin Heidelberg, pp. 73-84. doi: 10.1007/978-3-642-32650-9.
Ant Colony Optimisation (ACO) has been successfully applied to the classification task of data mining in the form of Ant-Miner. A new extension of Ant-Miner, called cAnt-MinerPB, uses the ACO procedure in a different fashion. The main difference is that the search in cAnt-MinerPB is optimised to find the best list of rules, whereas in Ant-Miner the search is optimised to find the best individual rule at each step of the sequential covering, producing a list of best rules. We aim to improve cAnt-MinerPB in two ways, firstly by dynamically finding the rule quality function which is used while the rules are being pruned, and secondly improving the rule-list quality function which is used to guide the search. We have found that changing the rule quality function has little effect on the overall performance, but that by improving the rule-list quality function we can positively affect the discovered lists of rules.
Moraglio, A., Otero, F. E., Johnson, C. G., Thompson, S. and Freitas, A. A. (2012) “Evolving Recursive Programs using Non-recursive Scaffolding”, in. Proceedings of the 2012 IEEE World Congress on Computational Intelligence, pp. 1596-1603. Available at: http://www.cs.kent.ac.uk/pubs/2012/3225.
Genetic programming has proven capable of evolving solutions to a wide variety of problems. However, the successes have largely been with programs without iteration or recursion; evolving recursive programs has turned out to be particularly challenging. The main obstacle to evolving recursive programs seems to be that they are particularly fragile to the application of search operators: a small change in a correct recursive program generally produces a completely wrong program. In this paper, we present a simple and general method that allows us to pass back and forth from a recursive program to an associated non-recursive program. Finding a recursive program can be reduced to evolving non-recursive programs followed by converting the optimum non-recursive program found to the associated optimum recursive program. This avoids the fragility problem above, as evolution does not search the space of recursive programs. We present promising experimental results on a test-bed of recursive problems.
Meiguins, A. S. G., Limao, R., Meiguins, B. S., Junior, S. and Freitas, A. A. (2012) “AutoClustering: an estimation of distribution algorithm for the automatic generation of clustering algorithms.”, in. Proceedings of WCCI 2012 Â? IEEE World Congress on Computational Intelligence (Congress on Evolutionary Computation), IEEE Press, pp. 2560-2566. Available at: http://www.cs.kent.ac.uk/pubs/2012/3249.
Otero, F. E., Johnson, C. G., Freitas, A. A. and Thompson, S. (2010) “Refactoring in Automatically Generated Programs”, in. 2nd International Symposium on Search Based Software Engineering.
Refactoring aims at improving the design of ex- isting code by introducing structural modifications without changing its behaviour. It is used to adjust a system’s design in order to facilitate its maintenance and extendability. Since deciding which refactoring to apply and where it should be applied is not a straightforward decision, search-based approaches to automating the task of software refactoring have been proposed recently. So far, these approaches have been applied only to human-written code. Despite many years of computer programming experience, certain problems are very difficult for programmers to solve. To address this, researches have developed methods where computers automatically create program code from a description of the problem to be solved. One of the most popular forms of automated program creation is called Genetic Programming (GP). The aim of this work is to make GP more effective by introducing an automated refactoring step, based on the refactoring work in the software engineering community. We believe that the refactoring step will enhance the ability of GP to produce code that solves more complex problems, as well as result in evolved code that is both simpler and more idiomatically structured than that produced by traditional GP methods.
Otero, F. E., Freitas, A. A. and Johnson, C. G. (2009) “Handling continuous attributes in ant colony classification algorithms”, in. Proc. of the 2009 IEEE Symposium on Computational Intelligence in Data Mining (CIDM 2009), IEEE, pp. 225-231. doi: 10.1109/CIDM.2009.4938653.
Most real-world classification problems involve continuous (real-valued) attributes, as well as, nominal (discrete) attributes. The majority of Ant Colony Optimisation (ACO) classification algorithms have the limitation of only being able to cope with nominal attributes directly. Extending the approach for coping with continuous attributes presented by cAnt-Miner (Ant-Miner coping with continuous attributes), in this paper we propose two new methods for handling continuous attributes in ACO classification algorithms. The first method allows a more flexible representation of continuous attributes' intervals. The second method explores the problem of attribute interaction, which originates from the way that continuous attributes are handled in cAnt-Miner, in order to implement an improved pheromone updating method. Empirical evaluation on eight publicly available data sets shows that the proposed methods facilitate the discovery of more accurate classification models.
Salhi, S., Plastino, A., Fonseca, E. R., Martins, S. de L., Freitas, A. A., Luis, M. and Fuchshuber, R. (2009) “Hybrid data mining metaheuristic for the p median problem”, in. SIAM conference.
de Oliveira, C. S., Meiguins, A. S. G., Meiguins, B. S., Godinho, P. I. and Freitas, A. A. (2007) “An evolutionary density and grid-based clustering algorithm.”, in daSilva, A., Soares, V., and Elias, G. (eds.). Proc. of the XXIII Brazilian Symposium on Databases (SBBD-2007), Sociedade Brasileira de Computacao, pp. 175-189.
Alves, R. T., Delgado, M., Camargo, F., Benelli, E. and Freitas, A. A. (2007) “Discovering multi-label hierarchical classification rules for protein function prediction”, in Plastino, A., de Carvalho, A. C., Ramos, R., and Junior, W. (eds.). Proc. II Workshop em Algoritmos e Aplicacoes de Mineracao de Dados (Workshop on Algorithms and Applications of Data Mining), Sociedade Brasileira de Computacao, pp. 87-90.
Smaldon, J. and Freitas, A. A. (2006) “Improving the interpretability of classification rules in sparse bioinformatics datasets”, in Bramer, M., Coenen, F., and Tuson, A. (eds.). Research and Development in Intelligent Systems XXIII - Proc. AI-2006, New York: Springer-Verlag, pp. 377-381.
Holden, N. and Freitas, A. A. (2006) “Hierarchical classification of G-protein-coupled receptors with a PSO/ACO algorithm”, in. IEEE Swarm Intelligence Symposium 2006, IEEE Press, pp. 77-84.
In our previous work we have proposed a hybrid Particle Swarm Optimisation / Ant Colony Optimisation (PSO/ACO) algorithm for discovering classification rules. In this paper we propose some modifications to the algorithm and apply it to a challenging hierarchical classification problem. This is a bioinformatics problem involving the prediction of G-Protein- Coupled Receptor’s (GPCR) hierarchical functional classes. We report the results of an extensive comparison between four versions of swarm intelligence algorithms – two versions based on our proposed algorithm and two versions based on Discrete PSO for discovering classification rules proposed in the literature. The experiments also compared the effectiveness of different kinds of protein signatures when used as predictor attributes, namely Prints, Interpro and Prosite signatures.
Iqbal, M., Freitas, A. A. and Johnson, C. G. (2005) “Varying the Topology and Probability of Re-Initialization in Particle Swarm Optimization”, in Talbi, E.-G. (ed.). Evolution Artificielle 2005.
This paper introduces two new versions of dissipative particle swarm optimization. Both of these use a new time-dependent strategy for randomly re-initializing the positions of the particles. In addition, one variation also uses a novel dynamic neighbourhood topology based on small world networks. We present results from applying these algorithms to two well-known function optimization problems. Both algorithms perform considerably better than both standard PSO and the original dissipative PSO algorithms. In particular one version performs significantly better on high-dimensional problems that are inaccessible to traditional methods.
Pappa, G. L. and Freitas, A. A. (2004) “Towards a genetic programming algorithm for automatically evolving rule induction algorithms”, in Furnkranz, J. (ed.). Proc. ECML/PKDD-2004 Workshop on Advances in Inductive Learning, Pisa, Italy, pp. 93-108.
Silla Jr, C. N., Kaestner, C. A. and Freitas, A. A. (2003) “A non-linear topic detection method for text summarization using Wordnet”, in Nunes, M. da G. V., Aluisio, S., Oliveira, L., and Teles, J. (eds.). Proc. I Workshop em Tecnologia da Informacao e Linguagem Humana, ICMC-USP, Brazil. Available at: http://www.cs.kent.ac.uk/pubs/2003/1761.
This paper deals with the problem of automatic topic detection in text documents. The proposed method follows a non-linear approach. The method uses a simple clustering algorithm to group the semantically-related sentences. The distance between two sentences is calculated based on the distance between all nouns that appear in the sentences. The distance between two nouns is calculated using the Wordnet thesaurus. An automatic text summarization system using a topic strength method was used to compare the results achieved by the Text Tiling Algorithm and the proposed method. The obtained initial results shows that the proposed method is a promising approach.
Freitas, A. A. and Timmis, J. (2003) “Revisiting the Foundations of Artificial Immune Systems: A Problem Oriented Perspective”, in Timmis, J., Bentley, P. J., and Hart, E. (eds.). Proceedings of the 2nd International Conference on Artificial Immune Systems, Springer, pp. 229-241. Available at: http://www.cs.kent.ac.uk/pubs/2003/1693.
Since their development, AIS have been used for a number of machine learning tasks including that of classification. Within the literature, there appears to be a lack of appreciation for the possible bias in the selection of various representations and affinity measures that may be introduced when employing AIS in classification tasks. Problems are then compounded when inductive bias of algorithms are not taken into account when applying seemingly generic AIS algorithms to specific application domains. This paper is an attempt at highlighting some of these issues. Using the example of classification, this paper explains the potential pitfalls in representation selection and the use of various affinity measures. Additionally, attention is given to the use of negative selection in classification and it is argued that this may be not an appropriate algorithm for such a task. This paper then presents ideas on avoiding unnecessary mistakes in the choice and design of AIS algorithms and ultimately delivered solutions.
Secker, A. D., Freitas, A. A. and Timmis, J. (2003) “A Danger Theory Approach to Web Mining”, in Timmis, J., Bentley, P. J., and Hart, E. (eds.). Proceedings of the 2nd International Conference on Artificial Immune Systems, Springer, pp. 156-167. doi: 10.1007/b12020.
Within immunology, new theories are constantly being proposed that challenge current ways of thinking. These include new theories regarding how the immune system responds to pathogenic material. This conceptual paper takes one relatively new such theory: the Danger theory, and explores the relevance of this theory to the application domain of web mining. Central to the idea of Danger theory is that of a context dependant response to invading pathogens. This paper argues that this context dependency could be utilised as powerful metaphor for applications in web mining. An illustrative example adaptive mailbox filter is presented that exploits properties of the immune system, including the Danger theory. This is essentially a dynamical classification task: a task that this paper argues is well suited to the field of artificial immune systems, particularly when drawing inspiration from the Danger theory.
Larsen, O., Freitas, A. A. and Nievola, J. C. (2002) “Constructing X-of-N attributes with a genetic algorithm”, in Lofti, A., Garibaldi, J., and John, R. (eds.). Proc. 4th Int. Conf. on Recent Advances in Soft Computing (RASC-2002), Nottingham Trent University, pp. 326-331.
The predictive accuracy obtained by a classification algorithm is strongly dependent on the quality of the attributes of the data being mined. When the attributes are little relevant for predicting the class of a record, the predictive accuracy will tend to be low. To combat this problem, a natural approach consists of constructing new attributes out of the original attributes. Many attribute construction algorithms work by simply constructing conjunctions and/or disjunctions of attribute-value pairs. This kind of representation has a limited expressiveness power to represent attribute interactions. A more expressive representation is X-of-N [Zheng 1995]. An Xof- N condition consists of a set of N attribute-value pairs. The value of an X-of-N condition for a given example (record) is the number of attribute-value pairs of the example that match with the N attribute-value pairs of the condition. For instance, consider the following X-of-N condition: X-of-{“Sex = male”, “Age < 21”, “Salary = high”}. Suppose that a given example has the following attribute-value pairs: {“Sex = male”, “Age = 51”, “Salary = high”}. This example has 2 out of the 3 attribute-value pairs of the X-of-N condition, so that the value of the Xof- N condition for this example is 2.
Carvalho, D. R. and Freitas, A. A. (2002) “New results for a hybrid decision tree/genetic algorithm for data mining”, in Lofti, A., Garibaldi, J., and John, R. (eds.). Proc. 4th Int. Conf. on Recent Advances in Soft Computing (RASC-2002), Berlin: Springer, pp. 260-265.
This paper proposes a hybrid decision tree/genetic algorithm for solving the problem of small disjuncts in the classification task of data mining. It reports computational results comparing the proposed algorithm with two versions of C4.5 (one of them also specifically designed for solving the problem of small disjuncts) in 22 data sets.
Pappa, G. L., Freitas, A. A. and Kaestner, C. A. (2002) “Attribute Selection with a Multiobjective Genetic Algorithm”, in Bittencourt, G. and Ramalho, G. L. (eds.). Proc. 16th Brazilian Symp. on Artificial Intelligence (SBIA-2002), Berlin: Springer-Verlag, pp. 280-290. doi: 10.1007/3-540-36127-8_27.
In this paper we address the problem of multiobjective attribute selection in data mining. We propose a multiobjective genetic algorithm (GA) based on the wrapper approach to discover the best subset of attributes for a given classification algorithm, namely C4.5, a well-known decision-tree algorithm. The two objectives to be minimized are the error rate and the size of the tree produced by C4.5. The proposed GA is a multiobjective method in the sense that it discovers a set of non-dominated solutions (attribute subsets), according to the concept of Pareto dominance.
Fabris, C. C. and Freitas, A. A. (2001) “Incorporating deviation-detection functionality into the OLAP paradigm”, in Mattoso, M. and Xexeo, G. (eds.). Proc. XVI Brazilian Symposium on Databases (SBBD-2001), Rio de Janeiro, Brazil, pp. 274-285.
Bojarczuk, C. C., Lopes, H. S. and Freitas, A. A. (2001) “Data Mining with Constrained-syntax Genetic Programming: Applications in Medical Data Sets”, in. Proc Intelligent Data Analysis in Medicine and Pharmacology - a workshop at MedInfo-2001, London.
Book
Pappa, G. L. and Freitas, A. A. (2010) Automating the design of data mining algorithms: an evolutionary computation approach. Springer, pp. 182-196. Available at: http://www.cs.kent.ac.uk/pubs/2010/2999.
Freitas, A. A. (2002) Data Mining and Knowledge Discovery with Evolutionary Algorithms. Berlin: Spinger-Verlag.
This book integrates two areas of computer science, namely data mining and evolutionary algorithms. Both these areas have become increasingly popular in the last few years, and their integration is currently an area of active research. In general, data mining consists of extracting knowledge from data. In this book we particularly emphasize the importance of discovering comprehensible, interesting knowledge, which is potentially useful for the reader for intelligent decision making. In a nutshell, the motivation for applying evolutionary algorithms to data mining is that evolutionary algorithms are robust search methods which perform a global search in the space of candidate solutions. In contrast, most rule induction methods perform a local, greedy search in the space of candidate rules. Intuitively, the global search of evolutionary algorithms can discover interesting rules and patterns that would be missed by the greedy search.
Datasets / databases
Newby, D., Freitas, A. A. and Ghafourian, T. (2014) “A Compilation of Aqueous Solubility of Drugs and Drug-Like Compounds.”
Other
Ghosh, A. and Freitas, A. A. (2003) “Special Issue on data mining and knowledge discovery with evolutionary algorithms”. IEEE Trans. on Evolutionary Computation 7(6), pp. 517-575. Available at: http://www.cs.kent.ac.uk/pubs/2003/1767.
Edited book
Capcarrere, M. S., Freitas, A. A., Bentley, P. J., Johnson, C. G. and Timmis, J. (eds.) (2005) Advances in Artificial Life 8th European Conference, ECAL 2005, Canterbury, UK, September 5-9, 2005. Proceedings, Advances in Artificial Life: 8th European Conference, ECAL 2005, Canterbury, UK, September 5-9, 2005, Proceedings (Lecture Notes in Computer Science / Lecture Notes in Artificial Intelligence). 8th European Conference, ECAL 2005, Berlin, Germany: Springer. doi: 10.1007/11553090.
The Artificial Life term appeared more than 20 years ago in a small corner of New Mexico, USA. Since then the area has developed dramatically, many researchers joining enthusiastically and research groups sprouting everywhere. This frenetic activity led to the emergence of several strands that are now established fields in themselves. We are now reaching a stage that one may describe as maturer: with more rigour, more benchmarks, more results, more stringent acceptance criteria, more applications, in brief, more sound science. This, which is the natural path of all new areas, comes at a price, however. A certain enthusiasm, a certain adventurousness from the early years is fading and may have been lost on the way. The field has become more reasonable. To counterbalance this and to encourage lively discussions, a conceptual track, where papers were judged on criteria like importance and/or novelty of the concepts proposed rather than the experimental/theoretical results, has been introduced this year. A conference on a theme as broad as Artificial Life is bound to be very diverse, but a few tendencies emerged. First, fields like ‘Robotics and Autonomous Agents’ or ‘Evolutionary Computation’ are still extremely active and keep on bringing a wealth of results to the A-Life community. Even there, however, new tendencies appear, like collective robotics, and more specifically self-assembling robotics, which represent now a large subsection. Second, new areas appear.
Review
Freitas, A. A. (2001) “Book Review: Data Mining Using Grammar-based Genetic Programming and Applications”, Genetic Programming and Evolvable Machines. Kluwer, pp. 197-199. doi: 10.1023/A:1011564616547.