Multi-objective genetic algorithm based approaches for mining optimized fuzzy association rules

Association rules form one of the most widely used techniques to discover correlations among attribute in a database. So far, some efficient methods have been proposed to obtain these rules with respect to an optimal goal, such as: to maximize the number of large itemsets and interesting rules or the values of support and confidence for the discovered rules. This paper first introduces optimized fuzzy association rule mining in terms of three important criteria; strongness, interestingness and comprehensibility. Then, it proposes multi-objective Genetic Algorithm (GA) based approaches for discovering these optimized rules. Optimization technique according to given criterion may be one of two different forms; The first tries to determine the appropriate fuzzy sets of quantitative attributes in a prespecified rule, which is also called as certain rule. The second deals with finding both uncertain rules and their appropriate fuzzy sets. Experimental results conducted on a real data set show the effectiveness and applicability of the proposed approach.     

Multi-objective genetic algorithms based automated clustering for fuzzy association rules mining

Researchers realized the importance of integrating fuzziness into association rules mining in databases with binary and quantitative attributes. However, most of the earlier algorithms proposed for fuzzy association rules mining either assume that fuzzy sets are given or employ a clustering algorithm, like CURE, to decide on fuzzy sets; for both cases the number of fuzzy sets is pre-specified. In this paper, we propose an automated method to decide on the number of fuzzy sets and for the autonomous mining of both fuzzy sets and fuzzy association rules. We achieve this by developing an automated clustering method based on multi-objective Genetic Algorithms (GA); the aim of the proposed approach is to automatically cluster values of a quantitative attribute in order to obtain large number of large itemsets in less time. We compare the proposed multi-objective GA based approach with two other approaches, namely: 1) CURE-based approach, which is known as one of the most efficient clustering algorithms; 2) Chien et al. clustering approach, which is an automatic interval partition method based on variation of density. Experimental results on 100 K transactions extracted from the adult data of USA census in year 2000 showed that the proposed automated clustering method exhibits good performance over both CURE-based approach and Chien et al.’s work in terms of runtime, number of large itemsets and number of association rules.     

Discovering gene association networks by multi-objective evolutionary quantitative association rules

In the last decade, the interest in microarray technology has exponentially increased due to its ability to monitor the expression of thousands of genes simultaneously. The reconstruction of gene association networks from gene expression profiles is a relevant task and several statistical techniques have been proposed to build them. The problem lies in the process to discover which genes are more relevant and to identify the direct regulatory relationships among them. We developed a multi-objective evolutionary algorithm for mining quantitative association rules to deal with this problem. We applied our methodology named GarNet to a well-known microarray data of yeast cell cycle. The performance analysis of GarNet was organized in three steps similarly to the study performed by Gallo et al. GarNet outperformed the benchmark methods in most cases in terms of quality metrics of the networks, such as accuracy and precision, which were measured using YeastNet database as true network. Furthermore, the results were consistent with previous biological knowledge.     

Optimizing reliability-based robust design model using multi-objective genetic algorithm

Reliability-based robust design optimization (RBRDO) is one of the most important tools developed in recent years to improve both quality and reliability of the products at an early design stage. This paper presents a comparative study of different formulation approaches of RBRDO models and their performances. The paper also proposes an evolutionary multi-objective genetic algorithm (MOGA) to one of the promising hybrid quality loss functions (HQLF)-based RBRDO model. The enhanced effectiveness of the HQLF-based RBRDO model is demonstrated by optimizing suitable examples.     

Extracting linguistic rules from data sets using fuzzy logic and genetic algorithms

Linguistic rules in natural language are useful and consistent with human way of thinking. They are very important in multi-criteria decision making due to their interpretability. In this paper, our discussions concentrate on extracting linguistic rules from data sets. In the end, we firstly analyze how to extract complex linguistic data summaries based on fuzzy logic. Then, we formalize linguistic rules based on complex linguistic data summaries, in which, the degree of confidence of linguistic rules from a data set can be explained by linguistic quantifiers and its linguistic truth from the fuzzy logical point of view. In order to obtain a linguistic rule with a higher degree of linguistic truth, a genetic algorithm is used to optimize the number and parameters of membership functions of linguistic values. Computational results show that the proposed method is an alternative method for extracting linguistic rules with linguistic truth from data sets.     

Non-dominated sorting genetic algorithm using fuzzy membership chromosome for categorical data clustering

In this research, a data clustering algorithm named as non-dominated sorting genetic algorithm-fuzzy membership chromosome (NSGA-FMC) based on K-modes method which combines fuzzy genetic algorithm and multi-objective optimization was proposed to improve the clustering quality on categorical data. The proposed method uses fuzzy membership value as chromosome. In addition, due to this innovative chromosome setting, a more efficient solution selection technique which selects a solution from non-dominated Pareto front based on the largest fuzzy membership is integrated in the proposed algorithm. The multiple objective functions: fuzzy compactness within a cluster (π) and separation among clusters (sep) are used to optimize the clustering quality. A series of experiments by using three UCI categorical datasets were conducted to compare the clustering results of the proposed NSGA-FMC with two existing methods: genetic algorithm fuzzy K-modes (GA-FKM) and multi-objective genetic algorithm-based fuzzy clustering of categorical attributes (MOGA (π, sep)). Adjusted Rand index (ARI), π, sep, and computation time were used as performance indexes for comparison. The experimental result showed that the proposed method can obtain better clustering quality in terms of ARI, π, and sep simultaneously with shorter computation time.     

Hybrid multi-objective shape design optimization using Taguchi’s method and genetic algorithm

This research is based on a new hybrid approach, which deals with the improvement of shape optimization process. The objective is to contribute to the development of more efficient shape optimization approaches in an integrated optimal topology and shape optimization area with the help of genetic algorithms and robustness issues. An improved genetic algorithm is introduced to solve multi-objective shape design optimization problems. The specific issue of this research is to overcome the limitations caused by larger population of solutions in the pure multi-objective genetic algorithm. The combination of genetic algorithm with robust parameter design through a smaller population of individuals results in a solution that leads to better parameter values for design optimization problems. The effectiveness of the proposed hybrid approach is illustrated and evaluated with test problems taken from literature. It is also shown that the proposed approach can be used as first stage in other multi-objective genetic algorithms to enhance the performance of genetic algorithms. Finally, the shape optimization of a vehicle component is presented to illustrate how the present approach can be applied for solving multi-objective shape design optimization problems.     

Multi-objective PSO algorithm for mining numerical association rules without a priori discretization

In the domain of association rules mining (ARM) discovering the rules for numerical attributes is still a challenging issue. Most of the popular approaches for numerical ARM require a priori data discretization to handle the numerical attributes. Moreover, in the process of discovering relations among data, often more than one objective (quality measure) is required, and in most cases, such objectives include conflicting measures. In such a situation, it is recommended to obtain the optimal trade-off between objectives. This paper deals with the numerical ARM problem using a multi-objective perspective by proposing a multi-objective particle swarm optimization algorithm (i.e., MOPAR) for numerical ARM that discovers numerical association rules (ARs) in only one single step. To identify more efficient ARs, several objectives are defined in the proposed multi-objective optimization approach, including confidence, comprehensibility, and interestingness. Finally, by using the Pareto optimality the best ARs are extracted. To deal with numerical attributes, we use rough values containing lower and upper bounds to show the intervals of attributes. In the experimental section of the paper, we analyze the effect of operators used in this study, compare our method to the most popular evolutionary-based proposals for ARM and present an analysis of the mined ARs. The results show that MOPAR extracts reliable (with confidence values close to 95%), comprehensible, and interesting numerical ARs when attaining the optimal trade-off between confidence, comprehensibility and interestingness.     

Fuzzy c-means: Optimality of solutions and effective termination of the algorithm

In this paper, the solutions produced by the fuzzy c-means algorithm for a general class of problems are examined and a method to test for the local optimality of such solutions is established. An equivalent mathematical program is defined for the c-means problem utilizing a generalized norm, then the properties of the resulting optimization problem are investigated. It is shown that the gradient of the resulting objective function at the solution produced by the c-means algorithm in this case takes a special structure which can be used in terminating the algorithm. Moreover, the local optimality of the solution obtained is checked utilizing the Hessian of the criterion function. The solution is a local minimum point if the Hessian matrix at this point is positive semidefinite. Simple rules are proposed to help in checking the definiteness of the matrix.     

An efficient genetic algorithm for automated mining of both positive and negative quantitative association rules

In this paper, a genetic algorithm (GA) is proposed as a search strategy for not only positive but also negative quantitative association rule (AR) mining within databases. Contrary to the methods used as usual, ARs are directly mined without generating frequent itemsets. The proposed GA performs a database-independent approach that does not rely upon the minimum support and the minimum confidence thresholds that are hard to determine for each database. Instead of randomly generated initial population, uniform population that forces the initial population to be not far away from the solutions and distributes it in the feasible region uniformly is used. An adaptive mutation probability, a new operator called uniform operator that ensures the genetic diversity, and an efficient adjusted fitness function are used for mining all interesting ARs from the last population in only single run of GA. The efficiency of the proposed GA is validated upon synthetic and real databases.     

A decision support tool coupling a causal model and a multi-objective genetic algorithm

A significant class of decision making problems consists of choosing actions, to be carried out simultaneously, in order to achieve a trade-off between different objectives. When such decisions concern complex systems, decision support tools including formal methods of reasoning and probabilistic models are of noteworthy helpfulness. These models are often built through learning procedures, based on an available knowledge base. Nevertheless, in many fields of application (e.g. when dealing with complex political, economic and social systems), it is frequently not possible to determine the model automatically, and this must then largely be derived from the opinions and value judgements expressed by domain experts. The BayMODE decision support tool (Bayesian Multi Objective Decision Environment), which we describe in this paper, operates precisely in such contexts. The principal component of the program is a multi-objective Decision Network, where actions are executed simultaneously. If the noisy-OR assumptions are applicable, such a the model has a reasonably small number of parameters, even when actions are represented as non-binary variables. This makes the model building procedure accessible and easy. Moreover, BayMODE operates with a multi-objective approach, which provides the decision maker with a set of non-dominated solutions, computed using a multi-objective genetic algorithm. Ivan Blecic is Assistant Professor of Economic Appraisal and Evaluation at the Faculty of Architecture in Alghero (University of Sassari, Italy) and member of Interuniversity Laboratory of Analysis and Models for Planning (LAMP). He received a Ph.D. in Planning and Public Policies in 2005 from IUAV University of Venice where he has also been a research fellow at the Department of Planning. His current research interests include analysis and modelling for planning, evaluation techniques and modelling, decision support systems and methods for public participation. Arnaldo Cecchini graduated cum laude in Physics at the University of Bologna in 1972. He is Professor of Analysis of Urban Systems at the Faculty of Architecture in Alghero (University of Sassari), Director of the Urban and Environmental Planning Course, Vice-Dean of the Faculty of Architecture in Alghero and Director of the Interuniversity Laboratory of Analysis and Models for Planning - LAMP. He is the author of more than 100 articles and papers published in books and refereed journals and is an expert in techniques of urban analysis and for public participation: simulation, gaming simulation, cellular automata, scenario techniques. Giuseppe A. Trunfio gained a Ph.D. in Computational Mechanics in 1999 at the University of Calabria, Italy. He has been a research fellow at the Italian National Research Council where he has worked extensively on the application of parallel computing to the simulation of complex systems. He is Assistant Professor of Computer Engineering at the Department of Architecture and Planning of the University of Sassari and his current research interests include decision support, probabilistic models, neural networks, evolutionary computation and cellular automata.     

Multiple sequence alignment with affine gap by using multi-objective genetic algorithm

Multiple sequence alignment is of central importance to bioinformatics and computational biology. Although a large number of algorithms for computing a multiple sequence alignment have been designed, the efficient computation of highly accurate and statistically significant multiple alignments is still a challenge. In this paper, we propose an efficient method by using multi-objective genetic algorithm (MSAGMOGA) to discover optimal alignments with affine gap in multiple sequence data. The main advantage of our approach is that a large number of tradeoff (i.e., non-dominated) alignments can be obtained by a single run with respect to conflicting objectives: affine gap penalty minimization and similarity and support maximization. To the best of our knowledge, this is the first effort with three objectives in this direction. The proposed method can be applied to any data set with a sequential character. Furthermore, it allows any choice of similarity measures for finding alignments. By analyzing the obtained optimal alignments, the decision maker can understand the tradeoff between the objectives. We compared our method with the three well-known multiple sequence alignment methods, MUSCLE, SAGA and MSA-GA. As the first of them is a progressive method, and the other two are based on evolutionary algorithms. Experiments on the BAliBASE 2.0 database were conducted and the results confirm that MSAGMOGA obtains the results with better accuracy statistical significance compared with the three well-known methods in aligning multiple sequence alignment with affine gap. The proposed method also finds solutions faster than the other evolutionary approaches mentioned above.     

Application of fuzzy ARTMAP and fuzzy <Emphasis Type="Italic">c</Emphasis>-means clustering to pattern classification with incomplete data

In this paper, a hybrid neural network that is capable of incremental learning and classification of patterns with incomplete data is proposed. Fuzzy ARTMAP (FAM) is employed as the constituting network for pattern classification while fuzzy c-means (FCM) clustering is used as the underlying algorithm for processing training as well as test samples with missing features. To handle an incomplete training set, FAM is first trained using complete samples only. Missing features of the training samples are estimated and replaced using two FCM-based strategies. Then, network training is conducted using all the complete and estimated samples. To handle an incomplete test set, a non-substitution FCM-based strategy is employed so that a predicted output can be produced rapidly. The performance of the proposed hybrid network is evaluated using a benchmark problem, and its practical applicability is demonstrated using a medical diagnosis task. The results are compared, analysed and quantified statistically with the bootstrap method. Implications of the proposed network for pattern classification tasks with incomplete data are discussed.     

A fuzzy clustering algorithm based on evolutionary programming

In this paper, a fuzzy clustering method based on evolutionary programming (EPFCM) is proposed. The algorithm benefits from the global search strategy of evolutionary programming, to improve fuzzy c-means algorithm (FCM). The cluster validity can be measured by some cluster validity indices. To increase the convergence speed of the algorithm, we exploit the modified algorithm to change the number of cluster centers dynamically. Experiments demonstrate EPFCM can find the proper number of clusters, and the result of clustering does not depend critically on the choice of the initial cluster centers. The probability of trapping into the local optima will be very lower than FCM.     

An approach of clustering data with noisy or imprecise feature measurement

In this paper we considered clustering of data corrupted by noise or suffering from imprecision due to finite resolution of the feature measuring device. Our work is motivated by the fact that no measurement can be made perfect and addition of noise is not an uncommon phenomenon for telemetric data. Here we tried to show how the classical k-means algorithm should be modified to take care of the noise/imprecision. Experimental results on Fisher's Iris data and a Nutrition data are demonstrated.     

Multi-objective optimization of sensor array using genetic algorithm

A multi-objective optimization method using genetic algorithm was proposed for sensor array optimization. Based on information theory, selectivity and diversity were used as the criteria for constructing two objective functions. A statistic measurement of resolving power, general resolution factor, and visual inspection were used to evaluate the optimization results with the aid of principal component analysis. In each Pareto set, most nondominated solutions had better statistics than the combination using all potential sensors. Also the principal component plots showed that different vapor classes were generally better separated after optimization. The experiment results indicated that the proposed method could successfully identify a set of Pareto optimal solutions of small size; and most optimized sensor arrays provided input with improved quality, i.e. better separation of target analytes. The running time for implementing the multi-objective optimization was satisfactory.     

A systematic approach to the assessment of fuzzy association rules

In order to allow for the analysis of data sets including numerical attributes, several generalizations of association rule mining based on fuzzy sets have been proposed in the literature. While the formal specification of fuzzy associations is more or less straightforward, the assessment of such rules by means of appropriate quality measures is less obvious. Particularly, it assumes an understanding of the semantic meaning of a fuzzy rule. This aspect has been ignored by most existing proposals, which must therefore be considered as ad-hoc to some extent. In this paper, we develop a systematic approach to the assessment of fuzzy association rules. To this end, we proceed from the idea of partitioning the data stored in a database into examples of a given rule, counterexamples, and irrelevant data. Evaluation measures are then derived from the cardinalities of the corresponding subsets. The problem of finding a proper partition has a rather obvious solution for standard association rules but becomes less trivial in the fuzzy case. Our results not only provide a sound justification for commonly used measures but also suggest a means for constructing meaningful alternatives.

Performance evaluation of fuzzy rule-based classification systems obtained by multi-objective genetic algorithms

In this paper, we examine the classification performance of fuzzy if-then rules selected by a GA-based multi-objective rule selection method. This rule selection method can be applied to high-dimensional pattern classification problems with many continuous attributes by restricting the number of antecedent conditions of each candidate fuzzy if-then rule. As candidate rules, we only use fuzzy if-then rules with a small number of antecedent conditions. Thus it is easy for human users to understand each rule selected by our method. Our rule selection method has two objectives: to minimize the number of selected fuzzy if-then rules and to maximize the number of correctly classified patterns. In our multi-objective fuzzy rule selection problem, there exist several solutions (i.e., several rule sets) called “non-dominated solutions” because two conflicting objectives are considered. In this paper, we examine the performance of our GA-based rule selection method by computer simulations on a real-world pattern classification problem with many continuous attributes. First we examine the classification performance of our method for training patterns by computer simulations. Next we examine the generalization ability for test patterns. We show that a fuzzy rule-based classification system with an appropriate number of rules has high generalization ability.     

On cluster validity index for estimation of the optimal number of fuzzy clusters

A new cluster validity index is proposed that determines the optimal partition and optimal number of clusters for fuzzy partitions obtained from the fuzzy c-means algorithm. The proposed validity index exploits an overlap measure and a separation measure between clusters. The overlap measure, which indicates the degree of overlap between fuzzy clusters, is obtained by computing an inter-cluster overlap. The separation measure, which indicates the isolation distance between fuzzy clusters, is obtained by computing a distance between fuzzy clusters. A good fuzzy partition is expected to have a low degree of overlap and a larger separation distance. Testing of the proposed index and nine previously formulated indexes on well-known data sets showed the superior effectiveness and reliability of the proposed index in comparison to other indexes.