This paper proposes a novel hybrid approach for learning Bayesian networks from incomplete data in the presence of missing values, which combines an evolutionary algorithm with the traditional expectation-maximization (EM) algorithm. The new algorithm can overcome the problem of getting stuck in sub-optimal solutions which occurs in most existing learning algorithms. The experimental results on the data sets generated from several benchmark networks illustrate that the new algorithm has better performance than some state-of-the-art algorithms. We also apply the approach to a data set of direct marketing and compare the performance of the discovered Bayesian networks obtained by the new algorithm with the networks generated by other methods. In the comparison, the Bayesian networks learned by the new algorithm outperform other networks.

Bayesian Network (BN) is a powerful network model, which represents a set of variables in the domain and provides the probabilistic relationships among them. But BN can handle discrete values only; it cannot handle continuous, interval and ordinal ones, which must be converted to discrete values and the order information is lost. Thus, BN tends to have higher network complexity and lower understandability. In this paper, we present a novel dependency network which can handle discrete, continuous, interval and ordinal values through functions; it has lower network complexity and stronger expressive power; it can represent any kind of relationships; and it can incorporate a-priori knowledge though user-defined functions. We also propose a novel Genetic Programming (GP) to learn dependency networks. The novel GP does not use any knowledge-guided nor application-oriented operator, thus it is robust and easy to replicate. The experimental results demonstrate that the novel GP can successfully discover the target novel dependency networks, which have the highest accuracy and the lowest network complexity.

The scalability problem in data mining involves the development of methods for handling large databases with limited computational resources. We present a two-phase scalable model-based clustering framework: first, a large data set is summed up into subclusters; Then, clusters are directly generated from the summary statistics of subclusters by a specifically designed expectation-maximization (EM) algorithm. Taking example for Gaussian mixture models, we establish a provably convergent EM algorithm, EMADS, which embodies cardinality, mean, and covariance information of each subcluster explicitly. Combining with different data summarization procedures, EMADS is used to construct two clustering systems: gEMADS and bEMADS. The experimental results demonstrate that they run several orders of magnitude faster than the classic EM algorithm with little loss of accuracy. They generate significantly better results than other model-based clustering systems using similar computational resources.

The self-organizing map (SOM) is a powerful tool in the exploratory phase of data mining. However, due to the dimensional conflict, neighborhood preservation cannot always lead to perfect topology preservation. In this paper we establish an expanding SOM (ESOM) to detect and preserve better topology correspondence between the two spaces. Our experiment results demonstrate that the ESOM constructs better mappings than the classic SOM in terms of both topological and quantization errors. Furthermore, clustering results generated by the ESOM are more accurate than those of the SOM.

Describes a data mining approach that employs evolutionary programming to discover knowledge represented in Bayesian networks. There are two different approaches to the network learning problem. The first one uses dependency analysis, while the second one searches good network structures according to a metric. Unfortunately, both approaches have their own drawbacks. Thus, we propose a hybrid algorithm of the two approaches, which consists of two phases, namely, the conditional independence test and the search phases. A new operator is introduced to further enhance the search efficiency. We conduct a number of experiments and compare the hybrid algorithm with our previous algorithm, MDLEP, which uses EP for network learning. The empirical results illustrate that the new approach has better performance. We apply the approach to data sets of direct marketing and compare the performance of the evolved Bayesian networks obtained by the new algorithm with the models generated by other methods. In the comparison, the induced Bayesian networks produced by the new algorithm outperform the other models.

Multiregression is one of the most common approaches used to discover dependency pattern among attributes in a database. Nonadditive set functions have been applied to deal with the interactive predictive attributes involved, and some nonlinear integrals with respect to nonadditive set functions are employed to establish a nonlinear multiregression model describing the relation between the objective attribute and predictive attributes. The values of the nonadditive set function play a role of unknown regression coefficients in the model and are determined by an adaptive genetic algorithm from the data of predictive and objective attributes. Furthermore, such a model is now improved by a new numericalization technique such that the model can accommodate both categorical and continuous numerical attributes. The traditional dummy binary method dealing with the mixed type data can be regarded as a very special case of our model when there is no interaction among the predictive attributes and the Choquet integral is used. When running the algorithm, to avoid a premature during the evolutionary procedure, a technique of maintaining diversity in the population is adopted. A test example shows that the algorithm and the relevant program have a good reversibility for the data. © 2001 John Wiley & Sons, Inc.16: 949–962 (2001)

In data mining, we emphasize the need for learning from huge, incomplete, and imperfect data sets. To handle noise in the problem domain, existing learning systems avoid overfitting the imperfect training examples by excluding insignificant patterns. The problem is that these systems use a limiting attribute-value language for representing the training examples and the induced knowledge. Moreover, some important patterns are ignored because they are statistically insignificant. In this article, we present a framework that combines Genetic Programming and Inductive Logic Programming to induce knowledge represented in various knowledge representation formalisms from noisy databases. The framework is based on a formalism of logic grammars, and it can specify the search space declaratively. An implementation of the framework, LOGENPRO (The Logic grammar based GENetic PROgramming system), has been developed. The performance of LOGENPRO is evaluated on the chess end-game domain. We compare LOGENPRO with FOIL and other learning systems in detail, and find its performance is significantly better than that of the others. This result indicates that the Darwinian principle of natural selection is a plausible noise handling method that can avoid overfitting and identify important patterns at the same time. Moreover, the system is applied to one real-life medical database. The knowledge discovered provides insights to and allows better understanding of the medical domains.