Search

The structured case representation improves case-based reasoning (CBR) by exploring structures in the case base and the relevance of case structures. Recent CBR classifiers have mostly been built upon the attribute-value case representation rather than structured case representation, in which the structural relations embodied in their representation structure are accordingly overlooked in improving the similarity measure. This results in retrieval inefficiency and limitations on the performance of CBR classifiers. This paper proposes a hierarchical case-based classifier, HCBC, which introduces a concept lattice to hierarchically organize cases. By exploiting structural case relations in the concept lattice, a novel dynamic weighting model is proposed to enhance the concept similarity measure. Based on this similarity measure, HCBC retrieves the top-K concepts that are most similar to a new case by using a bottom-up pruning-based recursive retrieval (PRR) algorithm. The concepts extracted in this way are applied to suggest a class label for the case by a weighted majority voting. Experimental results show that HCBC outperforms other classifiers in terms of classification performance and robustness on categorical data, and also works confidently well on numeric datasets. In addition, PRR effectively reduces the search space and greatly improves the retrieval efficiency of HCBC. [ABSTRACT FROM AUTHOR]

Nowadays information is crucial in many fields such as medicine, science and business, where databases are used effectively for information sharing. However, the databases face the risk of being pirated, stolen or misused, which may result in a lot of security threats concerning ownership rights, data tampering and privacy protection. Watermarking is utilized to enforce ownership rights on shared relational databases. Many reversible watermarking methods are proposed recently to protect rights of owners along with recovering original data. Most state-of-the-art methods modify the original data to a large extent, result in data quality degradation, and cannot achieve good balance between robustness against malicious attacks and data recovery. In this paper, we propose a robust and reversible database watermarking technique, Genetic Algorithm and Histogram Shifting Watermarking (GAHSW), for numerical relational database. The genetic algorithm is used to select the best secret key for grouping database, where the watermarking can be embedded with balanced distortion and capacity. The histogram of the prediction error is shifted to embed the watermark with good robustness. Experimental results demonstrate the effectiveness of GAHSW and show that it outperforms state-of-the-art approaches in terms of robustness against malicious attacks and preservation of data quality. [ABSTRACT FROM AUTHOR]

Advancement in information technology is playing an increasing role in the use of information systems comprising relational databases. These databases are used effectively in collaborative environments for information extraction; consequently, they are vulnerable to security threats concerning ownership rights and data tampering. Watermarking is advocated to enforce ownership rights over shared relational data and for providing a means for tackling data tampering. When ownership rights are enforced using watermarking, the underlying data undergoes certain modifications; as a result of which, the data quality gets compromised. Reversible watermarking is employed to ensure data quality along-with data recovery. However, such techniques are usually not robust against malicious attacks and do not provide any mechanism to selectively watermark a particular attribute by taking into account its role in knowledge discovery. Therefore, reversible watermarking is required that ensures; (i) watermark encoding and decoding by accounting for the role of all the features in knowledge discovery; and, (ii) original data recovery in the presence of active malicious attacks. In this paper, a robust and semi-blind reversible watermarking (RRW) technique for numerical relational data has been proposed that addresses the above objectives. Experimental studies prove the effectiveness of RRW against malicious attacks and show that the proposed technique outperforms existing ones. [ABSTRACT FROM PUBLISHER]

The discovery of evolving communities in dynamic networks is an important research topic that poses challenging tasks. Evolutionary clustering is a recent framework for clustering dynamic networks that introduces the concept of temporal smoothness inside the community structure detection method. Evolutionary-based clustering approaches try to maximize cluster accuracy with respect to incoming data of the current time step, and minimize clustering drift from one time step to the successive one. In order to optimize both these two competing objectives, an input parameter that controls the preference degree of a user towards either the snapshot quality or the temporal quality is needed. In this paper the detection of communities with temporal smoothness is formulated as a multiobjective problem and a method based on genetic algorithms is proposed. The main advantage of the algorithm is that it automatically provides a solution representing the best trade-off between the accuracy of the clustering obtained, and the deviation from one time step to the successive. Experiments on synthetic data sets show the very good performance of the method when compared with state-of-the-art approaches. [ABSTRACT FROM PUBLISHER]

Clustering is inherently a difficult task and is made even more difficult when the selection of relevant features is also an issue. In this paper, we propose an approach for simultaneous clustering and feature selection using a niching memetic algorithm. Our approach (which we call NMA̱CFS) makes feature selection an integral part of the global clustering search procedure and attempts to overcome the problem of identifying less promising locally optimal solutions in both clustering and feature selection, without making any a priori assumption about the number of clusters. Within the NMA̱CFS procedure, a variable composite representation is devised to encode both feature selection and cluster centers with different numbers of clusters. Furthermore, local search operations are introduced to refine feature selection and cluster centers encoded in the chromosomes. Finally, a niching method is integrated to preserve the population diversity and prevent premature convergence. In an experimental evaluation, we demonstrate the effectiveness of the proposed approach by using both synthetic and real data. [ABSTRACT FROM AUTHOR]

The multicampaign assignment problem is a campaign model to overcome the multiple-recommendation problem that occurs when conducting several personalized campaigns simultaneously. In this paper, we propose a Lagrangian method for the problem. The original problem space is transformed to another simpler one by introducing Lagrange multipliers, which relax the constraints of the multicampaign assignment problem. When the Lagrangian vector is supplied, we can compute the optimal solution under this new environment in O(NK2) time, where N and K are the numbers of customers and campaigns, respectively. This is a linear-time method when the number of campaigns is constant. However, it is not easy to find a Lagrangian vector inexact accord with the given problem constraints. We thus combine the Lagrangian method with a genetic algorithm to find good near-feasible solutions. We verify the effectiveness of our evolutionary Lagrangian approach in both theoretical and experimental viewpoints. The suggested Lagrangian approach is practically attractive for large-scale real-world problems. [ABSTRACT FROM AUTHOR]

UCS is a supervised learning classifier system that was introduced in 2003 for classification in data mining tasks. The representation of a rule in UCS as a univariate classification rule is straightforward for a human to understand. However, the system may require a large number of rules to cover the input space. Artificial neural networks (NNs), on the other hand, normally provide a more compact representation. However, it is not a straightforward task to understand the network. In this paper, we propose a novel way to incorporate NNs into UCS. The approach offers a good compromise between compactness, expressiveness, and accuracy. By using a simple artificial NN as the classifier's action, we obtain a more compact population size, better generalization, and the same or better accuracy while maintaining a reasonable level of expressiveness. We also apply negative correlation learning (NCL) during the training of the resultant NN ensemble. NCL is shown to improve the generalization of the ensemble. [ABSTRACT FROM AUTHOR]

Instance coreference resolution is an essential problem in studying semantic web, and it is also critical for the implementation of web of data and future integration and application of semantic data. In this paper, we propose to use Memetic Algorithm (MA) to solve this instance coreference problem in a sequential stage, i.e., the instance-level matching is carried out with the result of schema-level matching. We first give the optimization model for schema-level matching and instance-level matching. Then, we, respectively, present profile similarity measures and the rough evaluation metrics with the assumption that the golden alignment for both schema-level matching and instance-level matching is one-to-one. Furthermore, we give the details of the MA. Finally, the experiments of comparing our approach with the state-of-the-art systems on OAEI benchmarks and real-world datasets are conducted and the results demonstrate that our approach is effective. [ABSTRACT FROM AUTHOR]

In this paper we present a framework for automatic exploitation of news in stock trading strategies. Events are extracted from news messages presented in free text without annotations. We test the introduced framework by deriving trading strategies based on technical indicators and impacts of the extracted events. The strategies take the form of rules that combine technical trading indicators with a news variable, and are revealed through the use of genetic programming. We find that the news variable is often included in the optimal trading rules, indicating the added value of news for predictive purposes and validating our proposed framework for automatically incorporating news in stock trading strategies. [ABSTRACT FROM AUTHOR]

Data and object clustering techniques are used in a wide variety of scientific applications such as biology, pattern recognition, information systems, etc. Traditionally, clustering methods have focused on optimizing a single metric, however, several multidisciplinary applications such as robot team deployment, ad hoc networks, facility location, etc., require the simultaneous examination of multiple metrics during clustering. In this paper, we propose a novel approach for spatial data clustering based on the concepts of microeconomic theory, which can simultaneously optimize both the compaction and the equipartitioning objectives. The algorithm models a multistep, normal form game consisting of randomly initialized clusters as players that compete for the allocation of data objects from resource locations. A Nash-equilibrium-based methodology is used to derive solutions that are socially fair for all the players. After each step, the clusters are updated using the KMeans algorithm, and the process is repeated until the stopping criteria are satisfied. Extensive simulations were performed on several real data sets as well as artificially synthesized data sets to evaluate the efficacy of the algorithm. Experimental results indicate that the proposed algorithm yields significantly better results as compared to the traditional algorithms. Further, the proposed algorithm yields a high value of fairness, a metric that indicates the quality of the solution in terms of simultaneous optimization of the objectives. Also, the sensitivity of the various design parameters on the performance of our algorithm is analyzed and reported. [ABSTRACT FROM AUTHOR]

In this paper, a new symmetry-based genetic clustering algorithm is proposed which automatically evolves the number of clusters as well as the proper partitioning from a data set. Strings comprise both real numbers and the don't care symbol in order to encode a variable number of clusters. Here, assignment of points to different clusters are done based on a point symmetry (PS)-based distance rather than the euclidean distance. A newly proposed PS-based cluster validity index, Sym-index, is used as a measure of the validity of the corresponding partitioning. The algorithm is, therefore, able to detect both convex and nonconvex clusters irrespective of their sizes and shapes as long as they possess the symmetry property. Kd-tree-based nearest neighbor search is used to reduce the complexity of computing PS-based distance. A proof on the convergence property of variable string length genetic algorithm with PS- distance-based clustering (VGAPS-clustering) technique is also provided. The effectiveness of VGAPS-clustering compared to variable string length Genetic K-means algorithm (GCUK-clustering) and one recently developed weighted sum validity function-based hybrid niching genetic algorithm (HNGA-clustering) is demonstrated for nine artificial and five real-life data sets. [ABSTRACT FROM AUTHOR]

In most pattern recognition algorithms, amino acids cannot be used directly as inputs since they are nonnumerical variables. They, therefore, need encoding prior to input. In this regard, bio-basis function maps a nonnumerical sequence space to a numerical feature space. It is designed using an amino acid mutation matrix. One of the important issues for the bio-basis function is how to select the minimum set of bio-bases with maximum information. In this paper, we describe an algorithm, termed as rough-fuzzy c-medoids (RFCMdd) algorithm, to select the most informative bio-bases. It is comprised of a judicious integration of the principles of rough sets, fuzzy sets, the c-medoids algorithm, and the amino acid mutation matrix. While the membership function of fuzzy sets enables efficient handling of overlapping partitions, the concept of lower and upper bounds of rough sets deals with uncertainty, vagueness, and incompleteness in class definition. The concept of crisp lower bound and fuzzy boundary of a class, introduced in RFCMdd, enables efficient selection of the minimum set of the most informative bio-bases. Some new indices are introduced for evaluating quantitatively the quality of selected bio-bases. The effectiveness of the proposed algorithm, along with a comparison with other algorithms, has been demonstrated on different types of protein data sets. [ABSTRACT FROM AUTHOR]

This paper studies continuous monitoring of nearest neighbor (NN) queries over sliding window streams. According to this model, data points continuously stream in the system, and they are considered valid only while they belong to a sliding window that contains 1) the W most recent arrivals (count-based) or 2) the arrivals within a fixed interval W covering the most recent time stamps (time-based). The task of the query processor is to constantly maintain the result of long-running NN queries among the valid data. We present two processing techniques that apply to both count-based and time-based windows. The first one adapts conceptual partitioning, the best existing method for continuous NN monitoring over update streams, to the sliding window model. The second technique reduces the problem to skyline maintenance in the distance-time space and precomputes the future changes in the NN set. We analyze the performance of both algorithms and extend them to variations of NN search. Finally, we compare their efficiency through a comprehensive experimental evaluation. The skyline-based algorithm achieves lower CPU cost, at the expense of slightly larger space overhead. [ABSTRACT FROM AUTHOR]

Data broadcast is a promising technique to improve the bandwidth utilization and conserve the power consumption in a mobile computing environment. In many applications, the data items broadcast are dependent upon one another. However, most prior studies on broadcasting dependent data are restricted to a single broadcast channel environment, and as a consequence, the results are of limited applicability to the upcoming mobile environments. In view of this, we relax this restriction and explore in this paper the problem of broadcasting dependent data in multiple broadcast channels. By analyzing the model of dependent data broadcasting, we derive several theoretical properties for the average access time in a multiple channel environment. In light of the theoretical results, we develop a genetic algorithm to generate broadcast programs. Our experimental results show that the theoretical results derived are able to guide the search of the genetic algorithm very effectively, thus leading to broadcast programs of very high quality. [ABSTRACT FROM AUTHOR]

Community structure division is a crucial problem in the field of network data analysis. Algorithms based on Markov chains are easy to use and provide promising solutions for community detection. In a Markov chain-based algorithm (i.e., MCL), a flow distribution matrix and a transition matrix are used to describe stochastic flows and transition probabilities, respectively, on a network. The dynamic interaction process between stochastic flows and transition probabilities in MCLs is manifested through an iterative process of updating the abovementioned two matrices. As one of the key mechanisms of MCLs, such a dynamic process for increasing the inhomogeneity directly affects the accuracy and computational cost of MCL-based methods. Inspired by a kind of positive feedback interaction of a dendritic network of tube-like amoeba cell pseudopodia (named the Physarum foraging network), a Physarum-inspired relationship among vertices is proposed to enhance the transition probability in the dynamic process of MCL-based community detection algorithms. Specifically, the proposed hybrid community detection algorithm can adaptively search for a better combination of parameters based on a genetic algorithm. Some experiments are carried out on both static and dynamic networks. The results show that the unique Physarum inspired algorithm achieved better computational efficiency and detection performance than other algorithms. [ABSTRACT FROM AUTHOR]

Focuses on the impact of using image registration on the global optimization. Application of genetic algorithm on the problems; Determination of local minima entrapment on the Terminal Repeller Unconstrained Subenery Tunneling; Appropriation of noise models on the experiments.

Several systems that rely on consistent data to offer high-quality services, such as digital libraries and e-commerce brokers, may be affected by the existence of duplicates, quasi replicas, or near-duplicate entries in their repositories. Because of that, there have been significant investments from private and government organizations for developing methods for removing replicas from its data repositories. This is due to the fact that clean and replica-free repositories not only allow the retrieval of higher quality information but also lead to more concise data and to potential savings in computational time and resources to process this data. In this paper, we propose a genetic programming approach to record deduplication that combines several different pieces of evidence extracted from the data content to find a deduplication function that is able to identify whether two entries in a repository are replicas or not. As shown by our experiments, our approach outperforms an existing state-of-the-art method found in the literature. Moreover, the suggested functions are computationally less demanding since they use fewer evidence. In addition, our genetic programming approach is capable of automatically adapting these functions to a given fixed replica identification boundary, freeing the user from the burden of having to choose and tune this parameter. [ABSTRACT FROM AUTHOR]

Ranking and optimization of web service compositions represent challenging areas of research with significant implications for the realization of the “Web of Services” vision. “Semantic web services” use formal semantic descriptions of web service functionality and interface to enable automated reasoning over web service compositions. To judge the quality of the overall composition, for example, we can start by calculating the semantic similarities between outputs and inputs of connected constituent services, and aggregate these values into a measure of semantic quality for the composition. This paper takes a specific interest in combining semantic and nonfunctional criteria such as quality of service (QoS) to evaluate quality in web services composition. It proposes a novel and extensible model balancing the new dimension of semantic quality (as a functional quality metric) with a QoS metric, and using them together as ranking and optimization criteria. It also demonstrates the utility of Genetic Algorithms to allow optimization within the context of a large number of services foreseen by the “Web of Services” vision. We test the performance of the overall approach using a set of simulation experiments, and discuss its advantages and weaknesses. [ABSTRACT FROM PUBLISHER]

Redistricting is the process of dividing a geographic area consisting of spatial units—often represented as spatial polygons—into smaller districts that satisfy some properties. It can therefore be formulated as a set partitioning problem where the objective is to cluster the set of spatial polygons into groups such that a value function is maximized [1]. Widely used algorithms developed for point-based data sets are not readily applicable because polygons introduce the concepts of spatial contiguity and other topological properties that cannot be captured by representing polygons as points. Furthermore, when clustering polygons, constraints such as spatial contiguity and unit distributedness should be strategically addressed. Toward this, we have developed the Constrained Polygonal Spatial Clustering (CPSC) algorithm based on the A^\ast search algorithm that integrates cluster-level and instance-level constraints as heuristic functions. Using these heuristics, CPSC identifies the initial seeds, determines the best cluster to grow, and selects the best polygon to be added to the best cluster. We have devised two extensions of CPSC—CPSC* and CPSC*-PS—for problems where constraints can be soft or relaxed. Finally, we compare our algorithm with graph partitioning, simulated annealing, and genetic algorithm-based approaches in two applications—congressional redistricting and school districting. [ABSTRACT FROM AUTHOR]

Electronic negotiation systems have been devised to create an electronic marketplace for bargaining, auctions, reverse auctions, and exchanges between multiple buyers and sellers. Most studies of negotiation systems concentrate on negotiation process modeling and data modeling—rather than on strategies and efficiency—for a multiple-criteria decision making (MCDM) problem in which many criteria are taken into account as attributes for decision making. This study proposes an active collaboration and negotiation framework (ACNF), which is a negotiation support system that uses active documents with embedded business logics or business rules that can adapt to different collaborative strategies in a business-to-business (B2B) environment. The risk preferences of negotiators are modeled and measured by utility functions that provide mathematical tools to compute the relative value of different courses of action. The system is demonstrated, and three experiments are conducted to validate its performance. The experiments show that the negotiation process is very efficient, and the results are both close to the efficient point—or the Pareto frontier—and are fair to both negotiating parties. The framework can be used to efficiently and effectively achieve a settlement in various multiple-criteria bargaining schemes in the electronic marketplace. [ABSTRACT FROM AUTHOR]

The comprehensibility aspect of rule discovery is of emerging interest in the realm of knowledge discovery in databases. Of the many cognitive and psychological factors relating the comprehensibility of knowledge, we focus on the use of human amenable concepts as a representation language in expressing classification rules. Existing work in neural logic networks (or neulonets) provides impetus for our research; its strength lies in its ability to learn and represent complex human logic in decision-making using symbolic-interpretable net rules. A novel technique is developed for neulonet learning by composing net rules using genetic programming. Coupled with a sequential covering approach for generating a list of neulonets, the straightforward extraction of human-like logic rules from each neulonet provides an alternate perspective to the greater extent of knowledge that can potentially be expressed and discovered, while the entire list of neulonets together constitute an effective classifier. We show how the sequential covering approach is analogous to association-based classification, leading to the development of an association-based neulonet classifier. Empirical study shows that associative classification integrated with the genetic construction of neulonets performs better than general association-based classifiers in terms of higher accuracies and smaller rule sets. This is due to the richness in logic expression inherent in the neulonet learning paradigm. [ABSTRACT FROM AUTHOR]

Microarray techniques are leading to the development of sophisticated algorithms capable of extracting novel and useful knowledge from a biomedical point of view. In this work, we address the biclustering of gene expression data with evolutionary computation. Our approach is based on evolutionary algorithms, which have been proven to have excellent performance on complex problems, and searches for biclusters following a sequential covering strategy. The goal is to find biclusters of maximum size with mean squared residue lower than a given δ. In addition, we pay special attention to the fact of looking for high-quality biclusters with large variation, i.e., with a relatively high row variance, and with a low level of overlapping among biclusters. The quality of biclusters found by our evolutionary approach is discussed and the results are compared to those reported by Cheng and Church, and Yang et al. In general, our approach, named SEBI, shows an excellent performance at finding patterns in gene expression data. [ABSTRACT FROM AUTHOR]

Feature construction in classification is a preprocessing step in which one or more new attributes are constructed from the original attribute set, the object being to construct features that are more predictive than the original feature set. Genetic programming allows the construction of nonlinear combinations of the original features. We present a comprehensive analysis of genetic programming (GP) used for feature construction, in which four different fitness functions are used by the GP and four different classification techniques are subsequently used to build the classifier. Comparisons are made of the error rates and the size and complexity of the resulting trees. We also compare the overall performance of GP in feature construction with that of GP used directly to evolve a decision tree classifier, with the former proving to be a more effective use of the evolutionary paradigm. [ABSTRACT FROM AUTHOR]

The problem of computing a route for a mobile agent that incrementally fuses the data as it visits the nodes in a distributed sensor network is considered. The order of nodes visited along the route has a significant impact on the quality and cost of fused data, which, in turn, impacts the main objective of the sensor network, such as target classification or tracking. We present a simplified analytical model for a distributed sensor network and formulate the route computation problem in terms of maximizing an objective function, which is directly proportional to the received signal strength and inversely proportional to the path loss and energy consumption. We show this problem to be NP-complete and propose a genetic algorithm to compute an approximate solution by suitably employing a two-level encoding scheme and genetic operators tailored to the objective function We present simulation results for networks with different node sizes and sensor distributions, which demonstrate the superior performance of our algorithm over two existing heuristics, namely, local closest first and global closest first methods. [ABSTRACT FROM AUTHOR]

A methodology is described for evolving a Rough-fuzzy multi layer pemeptron with modular concept using a genetic algorithm to obtain a structured network suitable for both classification and rule extraction. The modular concept, based on "divide and conquer" strategy, provides accelerated training and a compact network suitable for generating a minimum number of rules with high certainty values. The concept of variable mutation operator is introduced for preserving the localized structure of the constituting knowledge-based subnetworks, while they are integrated and evolved. Rough set dependency rules are generated directly from the real valued attribute table containing fuzzy membership values. Two new indices viz., "certainty" and "confusion" in a decision are defined for evaluating quantitatively the quality of rules; The effectiveness of the model and the rule extraction algorithm is extensively demonstrated through experiments along with comparisons. [ABSTRACT FROM AUTHOR]