Evolutionary fuzzy clustering of relational data

This paper is concerned with the computational efficiency of fuzzy clustering algorithms when the data set to be clustered is described by a proximity matrix only (relational data) and the number of clusters must be automatically estimated from such data. A fuzzy variant of an evolutionary algorithm for relational clustering is derived and compared against two systematic (pseudo-exhaustive) approaches that can also be used to automatically estimate the number of fuzzy clusters in relational data. An extensive collection of experiments involving 18 artificial and two real data sets is reported and analyzed. (C) 2011 Elsevier B.V. All rights reserved.

On the efficiency of evolutionary fuzzy clustering

This paper tackles the problem of showing that evolutionary algorithms for fuzzy clustering can be more efficient than systematic (i.e. repetitive) approaches when the number of clusters in a data set is unknown. To do so, a fuzzy version of an Evolutionary Algorithm for Clustering (EAC) is introduced. A fuzzy cluster validity criterion and a fuzzy local search algorithm are used instead of their hard counterparts employed by EAC. Theoretical complexity analyses for both the systematic and evolutionary algorithms under interest are provided. Examples with computational experiments and statistical analyses are also presented.

Evolutionary tuning of SVM parameter values in multiclass problems

Support vector machines (SVMs) were originally formulated for the solution of binary classification problems. In multiclass problems, a decomposition approach is often employed, in which the multiclass problem is divided into multiple binary subproblems, whose results are combined. Generally, the performance of SVM classifiers is affected by the selection of values for their parameters. This paper investigates the use of genetic algorithms (GAs) to tune the parameters of the binary SVMs in common multiclass decompositions. The developed GA may search for a set of parameter values common to all binary classifiers or for differentiated values for each binary classifier. (C) 2008 Elsevier B.V. All rights reserved.

A hybrid approach to learn with imbalanced classes using evolutionary algorithms

There is an increasing interest in the application of Evolutionary Algorithms (EAs) to induce classification rules. This hybrid approach can benefit areas where classical methods for rule induction have not been very successful. One example is the induction of classification rules in imbalanced domains. Imbalanced data occur when one or more classes heavily outnumber other classes. Frequently, classical machine learning (ML) classifiers are not able to learn in the presence of imbalanced data sets, inducing classification models that always predict the most numerous classes. In this work, we propose a novel hybrid approach to deal with this problem. We create several balanced data sets with all minority class cases and a random sample of majority class cases. These balanced data sets are fed to classical ML systems that produce rule sets. The rule sets are combined creating a pool of rules and an EA is used to build a classifier from this pool of rules. This hybrid approach has some advantages over undersampling, since it reduces the amount of discarded information, and some advantages over oversampling, since it avoids overfitting. The proposed approach was experimentally analysed and the experimental results show an improvement in the classification performance measured as the area under the receiver operating characteristics (ROC) curve.

Evolutionary model trees for handling continuous classes in machine learning

Model trees are a particular case of decision trees employed to solve regression problems. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is an NP-Complete problem, traditional model tree induction algorithms make use of a greedy top-down divide-and-conquer strategy, which may not converge to the global optimal solution. In this paper, we propose a novel algorithm based on the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to globally near-optimal solutions. We call our new approach evolutionary model tree induction (E-Motion). We test its predictive performance using public UCI data sets, and we compare the results to traditional greedy regression/model trees induction algorithms, as well as to other evolutionary approaches. Results show that our method presents a good trade-off between predictive performance and model comprehensibility, which may be crucial in many machine learning applications. (C) 2010 Elsevier Inc. All rights reserved.

The Crystal Complex of Phosphofructokinase-2 of Escherichia coli with Fructose-6-phosphate KINETIC AND STRUCTURAL ANALYSIS OF THE ALLOSTERIC ATP INHIBITION

Substrate inhibition by ATP is a regulatory feature of the phosphofructokinases isoenzymes from Escherichia coli (Pfk-1 and Pfk-2). Under gluconeogenic conditions, the loss of this regulation in Pfk-2 causes substrate cycling of fructose-6-phosphate (fructose-6-P) and futile consumption of ATP delaying growth. In the present work, we have broached the mechanism of ATP-induced inhibition of Pfk-2 from both structural and kinetic perspectives. The crystal structure of Pfk-2 in complex with fructose-6-P is reported to a resolution of 2 angstrom. The comparison of this structure with the previously reported inhibited form of the enzyme suggests a negative interplay between fructose-6-P binding and allosteric binding of MgATP. Initial velocity experiments show a linear increase of the apparent K(0.5) for fructose-6-P and a decrease in the apparent k(cat) as a function of MgATP concentration. These effects occur simultaneously with the induction of a sigmoidal kinetic behavior (n(H) of approximately 2). Differences and resemblances in the patterns of fructose-6-P binding and the mechanism of inhibition are discussed for Pfk-1 and Pfk-2, as an example of evolutionary convergence, because these enzymes do not share a common ancestor.

Quartz recrystallization regimes, c-axis texture transitions and fluid inclusion reequilibration in a prograde greenschist to amphibolite facies mylonite zone (Ribeira Shear Zone, SE Brazil)

The crystal-plastic behavior of quartz mylonites from the Ribeira Shear Zone (SE Brazil), a major strike-slip structure that was active during a prograde metamorphic phase related to the Neoproterozoic Brasiliano-Pan African Orogeny, was investigated using a multi-method approach. Geothermobarometry results indicate deformational conditions ranging from similar to 300 to similar to 630 degrees C and 500-700 MPa. A strong correlation between mapped metamorphic zones and a dominance of different dynamic recrystallization mechanisms of quartz occurs within the mylonite zone. Bulging recrystallization (BLG) dominates within the chlorite zone between 300 and 410 degrees C, subgrain rotation recrystallization (SGR) operates within the biotite zone from 410 to 520 degrees C, and grain boundary migration recrystallization (GBM) dominates in the garnet zone above 520 degrees C. The development of quartz c-axis textures is mainly governed by temperature and dynamic recrystallization mechanisms. Textures from BLG zone mylonites are characterized by maxima around Z; SGR zone mylonites display single girdles or asymmetric type I crossed girdles; and GBM zone mylonites comprise maxima around Y and intermediate between X and Z. The scarcity or absence of water-bearing fluid inclusions in quartz mylonites from the SGR and GBM zones, which are dominated by carbonic inclusions, suggests water-deficient conditions, whereas BLG zone mylonites are dominated by water-bearing inclusions. This evidence indicates that water was available in the protoliths but has been eliminated with increasing deformation and deformation temperature. No effect of the water content variation on the quartz microstructural and recrystallized grain size evolution was detected, and little influence on c-axis texture development was observed. Most of the fluid inclusion densities were reequilibrated during the shear zone exhumation history, recording a decompression in the range of 300-500 MPa, while microstructural reequilibration effects related to the prograde metamorphism are largely preserved. Fluid inclusion microstructures and densities from two SGR zone samples preserved evidence for a near isothermal compression within the interior of the Ribeira Shear Zone during the prograde metamorphism. (C) 2009 Elsevier B.V. All rights reserved.

Bootstrap percolation on homogeneous trees has 2 phase transitions

We study the threshold theta bootstrap percolation model on the homogeneous tree with degree b + 1, 2 <= theta <= b, and initial density p. It is known that there exists a nontrivial critical value for p, which we call p(f), such that a) for p > p(f), the final bootstrapped configuration is fully occupied for almost every initial configuration, and b) if p < p(f) , then for almost every initial configuration, the final bootstrapped configuration has density of occupied vertices less than 1. In this paper, we establish the existence of a distinct critical value for p, p(c), such that 0 < p(c) < p(f), with the following properties: 1) if p <= p(c), then for almost every initial configuration there is no infinite cluster of occupied vertices in the final bootstrapped configuration; 2) if p > p(c), then for almost every initial configuration there are infinite clusters of occupied vertices in the final bootstrapped configuration. Moreover, we show that 3) for p < p(c), the distribution of the occupied cluster size in the final bootstrapped configuration has an exponential tail; 4) at p = p(c), the expected occupied cluster size in the final bootstrapped configuration is infinite; 5) the probability of percolation of occupied vertices in the final bootstrapped configuration is continuous on [0, p(f)] and analytic on (p(c), p(f) ), admitting an analytic continuation from the right at p (c) and, only in the case theta = b, also from the left at p(f).

Network genealogy of 195-bp satellite DNA supports the superimposed hybridization hypothesis of Trypanosoma cruzi evolutionary pattern

Trypanosoma cruzi is highly diverse genetically and has been partitioned into six discrete typing units (DTUs), recently re-named T. cruzi I-VI. Although T. cruzi reproduces predominantly by binary division, accumulating evidence indicates that particular DTUs are the result of hybridization events. Two major scenarios for the origin of the hybrid lineages have been proposed. It is accepted widely that the most heterozygous TcV and TcVI DTUs are the result of genetic exchange between TcII and TcIII strains. On the other hand, the participation of a TcI parental in the current genome structure of these hybrid strains is a matter of debate. Here, sequences of the T. cruzi-specific 195-bp satellite DNA of TcI, TcII, Tat, TcV, and TcVI strains have been used for inferring network genealogies. The resulting genealogy showed a high degree of reticulation, which is consistent with more than one event of hybridization between the Tc DTUs. The data also strongly suggest that Tat is a hybrid with two distinct sets of satellite sequences, and that genetic exchange between TcI and TcII parentals occurred within the pedigree of the TcV and TcVI DTUs. Although satellite DNAs belong to the fast-evolving portion of eukaryotic genomes, in >100 satellite units of nine T. cruzi strains we found regions that display 100% identity. No DTU-specific consensus motifs were identified, inferring species-wide conservation. (C) 2010 Elsevier B.V. All rights reserved.

Developing Box-Pushing Behaviours Using Evolutionary Robotics

The context of this report and the IRIDIA laboratory are described in the preface. Evolutionary Robotics and the box-pushing task are presented in the introduction.The building of a test system supporting Evolutionary Robotics experiments is then detailed. This system is made of a robot simulator and a Genetic Algorithm. It is used to explore the possibility of evolving box-pushing behaviours. The bootstrapping problem is explained, and a novel approach for dealing with it is proposed, with results presented.Finally, ideas for extending this approach are presented in the conclusion.