COMBINING MULTIPLE CLASSIFIERS USING DEMPSTER'S RULE FOR TEXT CATEGORIZATION

In this paper we investigate the combination of four machine learning methods for text categorization using Dempster's rule of combination. These methods include Support Vector Machine (SVM), kNN (Nearest Neighbor), kNN model-based approach (kNNM), and Rocchio. We first present a general representation of the outputs of different classifiers, in particular, modeling it as a piece of evidence by using a novel evidence structure called focal element triplet. Furthermore, we investigate an effective method for combining pieces of evidence derived from classifiers generated by a 10-fold cross-validation. Finally, we evaluate our methods on the 20-newsgroup and Reuters-21578 benchmark data sets and perform the comparative analysis with majority voting in combining multiple classifiers along with the previous result. Our experimental results show that the best combined classifier can improve the performance of the individual classifiers and Dempster's rule of combination outperforms majority voting in combining multiple classifiers.     

Troika - An improved stacking schema for classification tasks

Stacking is a general ensemble method in which a number of base classifiers are combined using one meta-classifier which learns their outputs. Such an approach provides certain advantages: simplicity; performance that is similar to the best classifier; and the capability of combining classifiers induced by different inducers. The disadvantage of stacking is that on multiclass problems, stacking seems to perform worse than other meta-learning approaches. In this paper we present Troika, a new stacking method for improving ensemble classifiers. The new scheme is built from three layers of combining classifiers. The new method was tested on various datasets and the results indicate the superiority of the proposed method to other legacy ensemble schemes, Stacking and StackingC, especially when the classification task consists of more than two classes.     

A dynamic overproduce-and-choose strategy for the selection of classifier ensembles

The overproduce-and-choose strategy, which is divided into the overproduction and selection phases, has traditionally focused on finding the most accurate subset of classifiers at the selection phase, and using it to predict the class of all the samples in the test data set. It is therefore, a static classifier ensemble selection strategy. In this paper, we propose a dynamic overproduce-and-choose strategy which combines optimization and dynamic selection in a two-level selection phase to allow the selection of the most confident subset of classifiers to label each test sample individually. The optimization level is intended to generate a population of highly accurate candidate classifier ensembles, while the dynamic selection level applies measures of confidence to reveal the candidate ensemble with the highest degree of confidence in the current decision. Experimental results conducted to compare the proposed method to a static overproduce-and-choose strategy and a classical dynamic classifier selection approach demonstrate that our method outperforms both these selection-based methods, and is also more efficient in terms of performance than combining the decisions of all classifiers in the initial pool.     

Statistical approaches to combining binary classifiers for multi-class classification

One of the popular methods for multi-class classification is to combine binary classifiers. In this paper, we propose a new approach for combining binary classifiers. Our method trains a combining method of binary classifiers using statistical techniques such as penalized logistic regression, stacking, and a sparsity promoting penalty. Our approach has several advantages. Firstly, our method outperforms existing methods even if the base classifiers are well-tuned. Secondly, an estimate of conditional probability for each class can be naturally obtained. Furthermore, we propose selecting relevant binary classifiers by adding the group lasso type penalty in training the combining method.     

Bagging, Boosting and the Random Subspace Method for Linear Classifiers

Recently bagging, boosting and the random subspace method have become popular combining techniques for improving weak classifiers. These techniques are designed for, and usually applied to, decision trees. In this paper, in contrast to a common opinion, we demonstrate that they may also be useful in linear discriminant analysis. Simulation studies, carried out for several artificial and real data sets, show that the performance of the combining techniques is strongly affected by the small sample size properties of the base classifier: boosting is useful for large training sample sizes, while bagging and the random subspace method are useful for critical training sample sizes. Finally, a table describing the possible usefulness of the combining techniques for linear classifiers is presented. Received: 03 November 2000, Received in revised form: 02 November 2001, Accepted: 13 December 2001     

An ensemble-based data fusion approach for characterizing ultrasonic liver tissue

This study investigates the feasibility of an ensemble of classifiers in characterizing ultrasonic liver tissue. Texture analysis generally requires feature representation and classification algorithm. From a variety of feature representations and classification algorithms, obtaining optimal ensembles composed of any feature-classifier pairs is difficult. This paper proposes an ensemble creation algorithm that can form an ensemble with high generalization performance. The pattern recognition process comprises four main stages. The first stage utilized multiresolution analysis to extract intrinsic features of ultrasonic liver images. By utilizing spatial-frequency decomposition, a feature vector was obtained by collecting the feature representation for each subimage. In the second stage of the study, various classification algorithms with diverse feature vectors were trained. Based on the trained classifiers, an ensemble was created by using the proposed algorithm in the third stage. The last stage was concerned with the aggregation of individual classifiers. The proposed approach was applied to discriminate ultrasonic liver images from three liver states: normal liver, cirrhosis, and hepatoma. Based on the six well-known fusion schemes, the experimental results showed that the ensemble proposed in this study yields more discrimination. The results indicate that the combining multiple classifiers with different features is an effective approach for characterizing ultrasonic live r tissue. Furthermore, a clinician can use the quantitative index of the classification results when deciding whether to conduct an advanced medical examination, thus improving the quality of medical care.     

Fusion of covariance matrices of PCA and FLD

In this paper, we propose a novel approach for fusing two classifiers, specifically classifiers based on subspace analysis, during feature extraction. A method of combining the covariance matrices of the Principal Component Analysis (PCA) and Fisher Linear Discriminant (FLD) is presented. Unlike other existing fusion strategies which fuse classifiers either at data level, or at feature level or at decision level, the proposed work combines two classifiers while extracting features introducing a new unexplored area for further research. The covariance matrices of PCA and FLD are combined using a product rule to preserve the natures of both covariance matrices with an expectation to have an increased performance. In order to show the effectiveness of the proposed fusion method, we have conducted a visual simulation on iris data. The proposed model has also been tested by performing clustering on standard datasets such as Zoo, Wine, and Iris. To study the versatility of the proposed method we have carried out an experimentation on sports video shot retrieval problem. The experimental results signify that the proposed fusing approach has an improved performance over individual classifiers.     

A multi-model selection framework for unknown and/or evolutive misclassification cost problems

In this paper, we tackle the problem of model selection when misclassification costs are unknown and/or may evolve. Unlike traditional approaches based on a scalar optimization, we propose a generic multi-model selection framework based on a multi-objective approach. The idea is to automatically train a pool of classifiers instead of one single classifier, each classifier in the pool optimizing a particular trade-off between the objectives. Within the context of two-class classification problems, we introduce the “ROC front concept” as an alternative to the ROC curve representation. This strategy is applied to the multi-model selection of SVM classifiers using an evolutionary multi-objective optimization algorithm. The comparison with a traditional scalar optimization technique based on an AUC criterion shows promising results on UCI datasets as well as on a real-world classification problem.     

Combining rules using local statistics and uncertainty estimates for improved ensemble segmentation

Segmentation using an ensemble of classifiers (or committee machine) combines multiple classifiers’ results to increase the performance when compared to single classifiers. In this paper, we propose new concepts for combining rules. They are based (1) on uncertainties of the individual classifiers, (2) on combining the result of existing combining rules, (3) on combining local class probabilities with the existing segmentation probabilities at each individual segmentation, and (4) on using uncertainty-based weights for the weighted majority rule. The results show that the proposed local-statistics-aware combining rules can reduce the effect of noise in the individual segmentation result and consequently improve the performance of the final (combined) segmentation. Also, combining existing combining rules and using the proposed uncertainty- based weights can further improve the performance.     

N-division output coding method applied to face recognition

Most research on face recognition has focused on representation of face appearances rather than the classifiers. For robust classification performance, we need to adopt elaborate classifiers. Output coding is suitable for this purpose because it can allow online learning. In this paper, we propose an N-division output coding method. In the experiments we demonstrate such properties as problem complexity, margin of separation, machine relevance and the recognition performance among different output coding methods.     

基于动态分类器集成系统的卷烟感官质量预测方法

集成学习是一种可以有效改善分类系统性能的数据挖掘方法。采用动态分类器集成选择算法对卷烟感官质量进行智能评估。产生包含多个基分类器的分类器池;根据基分类器在被测样本邻域内的表现选择满足要求的分类器;采用被选择的分类器产生最终的预测结果。为了验证该方法的有效性,采用国内某烟草公司提供的卷烟感官评估历史数据集进行了实验比较分析。实验结果表明,与其他方法相比,该方法获得的效果明显改善。     

Prior Knowledge for Part Correspondence

Classical approaches to shape correspondence base their computation purely on the properties, in particular geometric similarity, of the shapes in question. Their performance still falls far short of that of humans in challenging cases where corresponding shape parts may differ significantly in geometry or even topology. We stipulate that in these cases, shape correspondence by humans involves recognition of the shape parts where prior knowledge on the parts would play a more dominant role than geometric similarity. We introduce an approach to part correspondence which incorporates prior knowledge imparted by a training set of pre‐segmented, labeled models and combines the knowledge with content‐driven analysis based on geometric similarity between the matched shapes. First, the prior knowledge is learned from the training set in the form of per‐label classifiers. Next, given two query shapes to be matched, we apply the classifiers to assign a probabilistic label to each shape face. Finally, by means of a joint labeling scheme, the probabilistic labels are used synergistically with pairwise assignments derived from geometric similarity to provide the resulting part correspondence. We show that the incorporation of knowledge is especially effective in dealing with shapes exhibiting large intra‐class variations. We also show that combining knowledge and content analyses outperforms approaches guided by either attribute alone.     

AdaBoost-based algorithm for network intrusion detection.

Network intrusion detection aims at distinguishing the attacks on the Internet from normal use of the Internet. It is an indispensable part of the information security system. Due to the variety of network behaviors and the rapid development of attack fashions, it is necessary to develop fast machine-learning-based intrusion detection algorithms with high detection rates and low false-alarm rates. In this correspondence, we propose an intrusion detection algorithm based on the AdaBoost algorithm. In the algorithm, decision stumps are used as weak classifiers. The decision rules are provided for both categorical and continuous features. By combining the weak classifiers for continuous features and the weak classifiers for categorical features into a strong classifier, the relations between these two different types of features are handled naturally, without any forced conversions between continuous and categorical features. Adaptable initial weights and a simple strategy for avoiding overfitting are adopted to improve the performance of the algorithm. Experimental results show that our algorithm has low computational complexity and error rates, as compared with algorithms of higher computational complexity, as tested on the benchmark sample data.     

Adaptively entropy-based weighting classifiers in combination using Dempster–Shafer theory for word sense disambiguation

In this paper we introduce an evidential reasoning based framework for weighted combination of classifiers for word sense disambiguation (WSD). Within this framework, we propose a new way of defining adaptively weights of individual classifiers based on ambiguity measures associated with their decisions with respect to each particular pattern under classification, where the ambiguity measure is defined by Shannon’s entropy. We then apply the discounting-and-combination scheme in Dempster–Shafer theory of evidence to derive a consensus decision for the classification task at hand. Experimentally, we conduct two scenarios of combining classifiers with the discussed method of weighting. In the first scenario, each individual classifier corresponds to a well-known learning algorithm and all of them use the same representation of context regarding the target word to be disambiguated, while in the second scenario the same learning algorithm applied to individual classifiers but each of them uses a distinct representation of the target word. These experimental scenarios are tested on English lexical samples of Senseval-2 and Senseval-3 resulting in an improvement in overall accuracy.     

A theoretical and experimental analysis of linear combiners for multiple classifier systems

In this paper, a theoretical and experimental analysis of linear combiners for multiple classifier systems is presented. Although linear combiners are the most frequently used combining rules, many important issues related to their operation for pattern classification tasks lack a theoretical basis. After a critical review of the framework developed in works by Turner and Ghosh [1996], [1999] on which our analysis is based, we focus on the simplest and most widely used implementation of linear combiners, which consists of assigning a nonnegative weight to each individual classifier. Moreover, we consider the ideal performance of this combining rule, i.e., that achievable when the optimal values of the weights are used. We do not consider the problem of weights estimation, which has been addressed in the literature. Our theoretical analysis shows how the performance of linear combiners, in terms of misclassification probability, depends on the performance of individual classifiers, and on the correlation between their outputs. In particular, we evaluate the ideal performance improvement that can be achieved using the weighted average over the simple average combining rule and investigate in what way it depends on the individual classifiers. Experimental results on real data sets show that the behavior of linear combiners agrees with the predictions of our analytical model. Finally, we discuss the contribution to the state of the art and the practical relevance of our theoretical and experimental analysis of linear combiners for multiple classifier systems.     

Modeling recurring concepts in data streams: a graph-based framework

Classifying a stream of non-stationary data with recurrent drift is a challenging task and has been considered as an interesting problem in recent years. All of the existing approaches handling recurrent concepts maintain a pool of concepts/classifiers and use that pool for future classifications to reduce the error on classifying the instances from a recurring concept. However, the number of classifiers in the pool usually grows very fast as the accurate detection of an underlying concept is a challenging task in itself. Thus, there may be many concepts in the pool representing the same underlying concept. This paper proposes the GraphPool framework that refines the pool of concepts by applying a merging mechanism whenever necessary: after receiving a new batch of data, we extract a concept representation from the current batch considering the correlation among features. Then, we compare the current batch representation to the concept representations in the pool using a statistical multivariate likelihood test. If more than one concept is similar to the current batch, all the corresponding concepts will be merged. GraphPool not only keeps the concepts but also maintains the transition among concepts via a first-order Markov chain. The current state is maintained at all times and new instances are predicted based on that. Keeping these transitions helps to quickly recover from drifts in some real-world problems with periodic behavior. Comprehensive experimental results of the framework on synthetic and real-world data show the effectiveness of the framework in terms of performance and pool management.     

Improving malware detection by applying multi-inducer ensemble

Detection of malicious software (malware) using machine learning methods has been explored extensively to enable fast detection of new released malware. The performance of these classifiers depends on the induction algorithms being used. In order to benefit from multiple different classifiers, and exploit their strengths we suggest using an ensemble method that will combine the results of the individual classifiers into one final result to achieve overall higher detection accuracy. In this paper we evaluate several combining methods using five different base inducers (C4.5 Decision Tree, Naïve Bayes, KNN, VFI and OneR) on five malware datasets. The main goal is to find the best combining method for the task of detecting malicious files in terms of accuracy, AUC and Execution time.     

Shape retrieval using triangle-area representation and dynamic space warping

In this paper, we present a shape retrieval method using triangle-area representation for nonrigid shapes with closed contours. The representation utilizes the areas of the triangles formed by the boundary points to measure the convexity/concavity of each point at different scales (or triangle side lengths). This representation is effective in capturing both local and global characteristics of a shape, invariant to translation, rotation, and scaling, and robust against noise and moderate amounts of occlusion. In the matching stage, a dynamic space warping (DSW) algorithm is employed to search efficiently for the optimal (least cost) correspondence between the points of two shapes. Then, a distance is derived based on the optimal correspondence. The performance of our method is demonstrated using four standard tests on two well-known shape databases. The results show the superiority of our method over other recent methods in the literature.     

An integration of online and pseudo-online information for cursive word recognition

In this paper, we present a novel method to extract stroke order independent information from online data. This information, which we term pseudo-online, conveys relevant information on the offline representation of the word. Based on this information, a combination of classification decisions from online and pseudo-online cursive word recognizers is performed to improve the recognition of online cursive words. One of the most valuable aspects of this approach with respect to similar methods that combine online and offline classifiers for word recognition is that the pseudo-online representation is similar to the online signal and, hence, word recognition is based on a single engine. Results demonstrate that the pseudo-online representation is useful as the combination of classifiers perform better than those based solely on pure online information.