Random one-dependence estimators

Many approaches attempt to improve naive Bayes and have been broadly divided into five main categories: (1) structure extension; (2) attribute weighting; (3) attribute selection; (4) instance weighting; (5) instance selection, also called local learning. In this paper, we work on the approach of structure extension and single out a random Bayes model by augmenting the structure of naive Bayes. We called it random one-dependence estimators, simply RODE. In RODE, each attribute has at most one parent from other attributes and this parent is randomly selected from log₂m (where m is the number of attributes) attributes with the maximal conditional mutual information. Our work conducts the randomness into Bayesian network classifiers. The experimental results on a large number of UCI data sets validate its effectiveness in terms of classification, class probability estimation, and ranking.     

A Novel Bayes Model: Hidden Naive Bayes

Because learning an optimal Bayesian network classifier is an NP-hard problem, learning-improved naive Bayes has attracted much attention from researchers. In this paper, we summarize the existing improved algorithms and propose a novel Bayes model: hidden naive Bayes (HNB). In HNB, a hidden parent is created for each attribute which combines the influences from all other attributes. We experimentally test HNB in terms of classification accuracy, using the 36 UCI data sets selected by Weka, and compare it to naive Bayes (NB), selective Bayesian classifiers (SBC), naive Bayes tree (NBTree), tree-augmented naive Bayes (TAN), and averaged one-dependence estimators (AODE). The experimental results show that HNB significantly outperforms NB, SBC, NBTree, TAN, and AODE. In many data mining applications, an accurate class probability estimation and ranking are also desirable. We study the class probability estimation and ranking performance, measured by conditional log likelihood (CLL) and the area under the ROC curve (AUC), respectively, of naive Bayes and its improved models, such as SBC, NBTree, TAN, and AODE, and then compare HNB to them in terms of CLL and AUC. Our experiments show that HNB also significantly outperforms all of them.     

An exact schema theorem for adaptive genetic algorithm and its application to machine cell formation

This paper proposes an exact schema theorem that is able to predict the expected number of copies of schemas in the next GA generation. It focuses on two-point crossover, which is widely used in many GA applications. As two important GA control parameters, crossover probability (p_c) and mutation probability (p_m) affect the performance of GAs drastically. A set of good GA parameters help in improving the ability of a GA to search for near global optimal solutions. This work shows that optimal p_c and p_m do not exist in most cases. As a result, a compromised pair of p_c and p_m may help improve the performance of GA. A multiple population search strategy enabled fuzzy c-means based evolutionary approach, which embeds the proposed exact schema theorem, to machine cell formation is then proposed. The approach enables the crossover and mutation probabilities of GAs to be made adaptive to suit different stages of the search for near optimal solutions. Three case studies were conducted. The proposed approach was able to provide better solutions consistently.     

Estimation of probabilities of label imperfections and correction of mislabels

Schemes that use both the imperfectly labeled and unlabeled pattern sets for the estimation of probabilities of label imperfections and correction of mislabels are presented in this paper. Using relationships between the class conditional densities, and a priori probabilities with and without imperfections in the labels, the problem of estimating probabilities of label imperfections is formulated as that of minimizing the Bayes probability of error. Experimental results are presented from the processing of remotely sensed multi-spectral scanner imagery data. A thresholding scheme is proposed for the correction of pattern mislabels. For a symmetric mislabeling case, a relationship is developed between the probability that such a scheme gives a bad label to a pattern and the probability that the scheme accepts the original label of the pattern. This relationship could be used for computing the threshold from unlabeled samples for a specified probability of bad labeling. An example is presented to illustrate the behavior of the scheme. Furthermore, bounds are presented between the Bayes errors with and without imperfections in the labels and are shown to become equalities when the imperfections in the labels become symmetric.     

On Discriminative Bayesian Network Classifiers and Logistic Regression

Discriminative learning of the parameters in the naive Bayes model is known to be equivalent to a logistic regression problem. Here we show that the same fact holds for much more general Bayesian network models, as long as the corresponding network structure satisfies a certain graph-theoretic property. The property holds for naive Bayes but also for more complex structures such as tree-augmented naive Bayes (TAN) as well as for mixed diagnostic-discriminative structures. Our results imply that for networks satisfying our property, the conditional likelihood cannot have local maxima so that the global maximum can be found by simple local optimization methods. We also show that if this property does not hold, then in general the conditional likelihood can have local, non-global maxima. We illustrate our theoretical results by empirical experiments with local optimization in a conditional naive Bayes model. Furthermore, we provide a heuristic strategy for pruning the number of parameters and relevant features in such models. For many data sets, we obtain good results with heavily pruned submodels containing many fewer parameters than the original naive Bayes model.Editors: Pedro Larrañaga, Jose A. Lozano, Jose M. Peña and Iñaki Inza     

Using phrases as features in email classification

In this paper, we report our experience on the use of phrases as basic features in the email classification problem. We performed extensive empirical evaluation using our large email collections and tested with three text classification algorithms, namely, a naive Bayes classifier and two k-NN classifiers using TF-IDF weighting and resemblance respectively. The investigation includes studies on the effect of phrase size, the size of local and global sampling, the neighbourhood size, and various methods to improve the classification accuracy. We determined suitable settings for various parameters of the classifiers and performed a comparison among the classifiers with their best settings. Our result shows that no classifier dominates the others in terms of classification accuracy. Also, we made a number of observations on the special characteristics of emails. In particular, we observed that public emails are easier to classify than private ones.     

Learning Instance Weighted Naive Bayes from labeled and unlabeled data

In real-world data mining applications, it is often the case that unlabeled instances are abundant, while available labeled instances are very limited. Thus, semi-supervised learning, which attempts to benefit from large amount of unlabeled data together with labeled data, has attracted much attention from researchers. In this paper, we propose a very fast and yet highly effective semi-supervised learning algorithm. We call our proposed algorithm Instance Weighted Naive Bayes (simply IWNB). IWNB firstly trains a naive Bayes using the labeled instances only. And the trained naive Bayes is used to estimate the class membership probabilities of the unlabeled instances. Then, the estimated class membership probabilities are used to label and weight unlabeled instances. At last, a naive Bayes is trained again using both the originally labeled data and the (newly labeled and weighted) unlabeled data. Our experimental results based on a large number of UCI data sets show that IWNB often improves the classification accuracy of original naive Bayes when available labeled data are very limited.     

Linear dimension reduction and Bayes classification with unknown population parameters

Odell and Decell, Odell and Coberly gave necessary and sufficient conditions for the smallest dimension compression matrix B such that the Bayes classification regions are preserved. That is, they developed an explicit expression of a compression matrix B such that the Bayes classification assignment are the same for both the original space x and the compressed space Bx. Odell indicated that whenever the population parameters are unknown, then the dimension of Bx is the same as x with probability one. Furthermore, Odell posed the problem of finding a lower dimension q < p which in some sense best fits the range space generated by the matrix M. The purpose of this paper is to discuss this problem and provide a partial solution.     

Variational Bayes via propositionalized probability computation in PRISM

We propose a logic-based approach to variational Bayes (VB) via propositionalized probability computation in a symbolic-statistical modeling language PRISM. PRISM computes probabilities of logical formulas by reducing them to AND/OR boolean formulas called explanation graphs containing probabilistic ${\tt msw/2}$ atoms. We put Dirichlet priors on parameters of ${\tt msw/2}$ atoms and derive a variational Bayes EM algorithm that learns their hyper parameters from data. It runs on explanation graphs deduced from a program and a goal and computes probabilities in a dynamic programming manner in time linear in the size of the graphs. To show the genericity and effectiveness of Bayesian modeling by the proposed approach, we conducted two learning experiments, one with a probabilistic right-corner grammar and the other with a profile-HMM. To our knowledge, no previous report has been made of VB applied to these models.     

Convergence of continuous-time partitioned adaptive state estimators

The asymptotic behaviour of Bayes optimal adaptive state estimation schemes (also called the partitioned adaptive estimation algorithms) for continuous-time linear dynamic Gauss-Markov systems with unknown parameters is investigated. The unknown system parameters are asssumed to belong to a finite set. The results are developed through, weak consistency of the maximum likelihood and the maximum a posteriori probability estimates of the unknown parameters.     

Naive Bayes text classifiers: a locally weighted learning approach

Due to being fast, easy to implement and relatively effective, some state-of-the-art naive Bayes text classifiers with the strong assumption of conditional independence among attributes, such as multinomial naive Bayes, complement naive Bayes and the one-versus-all-but-one model, have received a great deal of attention from researchers in the domain of text classification. In this article, we revisit these naive Bayes text classifiers and empirically compare their classification performance on a large number of widely used text classification benchmark datasets. Then, we propose a locally weighted learning approach to these naive Bayes text classifiers. We call our new approach locally weighted naive Bayes text classifiers (LWNBTC). LWNBTC weakens the attribute conditional independence assumption made by these naive Bayes text classifiers by applying the locally weighted learning approach. The experimental results show that our locally weighted versions significantly outperform these state-of-the-art naive Bayes text classifiers in terms of classification accuracy.     

On One Problem in Multichannel Signal Detection

We consider a statistical problem of detecting a signal with unknown energy in a multichannel system, observed in a Gaussian noise. We assume that the signal can appear in the kth channel with a known small prior probability πk. Using noisy observations from all channels, we would like to detect whether the signal is presented in one of the channels or we observe pure noise. We describe and compare statistical properties of the maximum posterior probability test and optimal Bayes test. In particular, for these tests we obtain limiting distributions of test statistics and define sets of their undetectable signals.     

Probabilistic skylines on uncertain data: model and bounding-pruning-refining methods

Uncertain data are inherent in some important applications. Although a considerable amount of research has been dedicated to modeling uncertain data and answering some types of queries on uncertain data, how to conduct advanced analysis on uncertain data remains an open problem at large. In this paper, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all objects whose skyline probabilities are at least p (0 < p ≤ 1). Computing probabilistic skylines on large uncertain data sets is challenging. We develop a bounding-pruning-refining framework and three algorithms systematically. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Combining the advantages of the bottom-up algorithm and the top-down algorithm, we develop a hybrid algorithm to further improve the performance. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our algorithms are efficient on large data sets.     

Efficient classification for longitudinal data

A new classifier, QIFC, is proposed based on the quadratic inference function for longitudinal data. Our approach builds a classifier by taking advantage of modeling information between the longitudinal responses and covariates for each class, and assigns a new subject to the class with the shortest newly defined distance to the subject. For finite sample applications, this enables one to overcome the difficulty in estimating covariance matrices while still incorporating correlation into the classifier. The proposed classifier only requires the first moment condition of the model distribution, and hence is able to handle both continuous and discrete responses. Simulation studies show that QIFC outperforms competing classifiers, such as the functional data classifier, support vector machine, logistic regression, linear discriminant analysis, the naive Bayes classifier and the decision tree in various practical settings. Two time-course gene expression data sets are used to assess the performance of QIFC in applications.     

基于纠错输出编码的多类概率建模

目前模式识别领域中缺乏有效的多类概率建模方法,对此提出利用纠错输出编码作为多类概率建模框架,将二元纠错输出编码研究的概率输出问题转化为线性超定方程的求解问题,通过线性最小二乘法来求解并获取多类后验概率的结果;而对于三元纠错输出编码的等价非线性超定方程组,提出一种迭代法则来求解多类概率输出.实验中通过与3种经典方法相比较可以发现,新方法求取的概率输出具有更好的分布形态,并且该方法具有较好的分类性能.     

Application of non-normal p-norm trapezoidal fuzzy number in reliability evaluation of electrical substations

This paper presented a non-normal p-norm trapezoidal fuzzy number–based fault tree technique to obtain the reliability analysis for substations system. Due to uncertainty in the collected data, all the failure probabilities are represented by non-normal p-norm trapezoidal fuzzy number. In this paper, the fault tree incorporated with the non-normal p-norm trapezoidal fuzzy number and minimal cut sets approach are used for reliability assessment of substations. An example of 66/11 kV substation is given to demonstrate the method. Further, fuzzy risk analysis problems are described to find out the probability of failure of each components of the system using linguistic variables, which could be used for managerial decision making and future system maintenance strategy.     

A Generic Ensemble Approach to Estimate Multidimensional Likelihood in Bayesian Classifier Learning

In Bayesian classifier learning, estimating the joint probability distribution p( x ,y) or the likelihood p( x |y) directly from training data is considered to be difficult, especially in large multidimensional data sets. To circumvent this difficulty, existing Bayesian classifiers such as Naive Bayes, BayesNet, and AηDE have focused on estimating simplified surrogates of p( x ,y) from different forms of one‐dimensional likelihoods. Contrary to the perceived difficulty in multidimensional likelihood estimation, we present a simple generic ensemble approach to estimate multidimensional likelihood directly from data. The idea is to aggregate p_i( x |y) estimated from a random subsample of data . This article presents two ways to estimate multidimensional likelihoods using the proposed generic approach and introduces two new Bayesian classifiers called ENNBayes and MassBayes that estimate p_i( x |y) using a nearest‐neighbor density estimation and a probability estimation through feature space partitioning, respectively. Unlike the existing Bayesian classifiers, ENNBayes and MassBayes have constant training time and space complexities and they scale better than existing Bayesian classifiers in very large data sets. Our empirical evaluation shows that ENNBayes and MassBayes yield better predictive accuracy than the existing Bayesian classifiers in benchmark data sets.     

Research on the unbiased probability estimation of error-correcting output coding

Supervised classification based on error-correcting output codes (ECOC) is an efficient method to solve the problem of multi-class classification, and how to get the accurate probability estimation via ECOC is also an attractive research direction. This paper proposed three kinds of ECOC to get unbiased probability estimates, and investigated the corresponding classification performance in depth at the same time. Two evaluating criterions for ECOC that has better classification performance were concluded, which are Bayes consistence and unbiasedness of probability estimation. Experimental results on artificial data sets and UCI data sets validate the correctness of our conclusion.