One-against-all ensemble for multiclass pattern classification

This paper presents a new method called one-against-all ensemble for solving multiclass pattern classification problems. The proposed method incorporates a neural network ensemble into the one-against-all method to improve the generalization performance of the classifier. The experimental results show that the proposed method can reduce the uncertainty of the decision and it is comparable to the other widely used methods.     

Fast Multiclass SVM Classification Using Decision Tree Based One-Against-All Method

We present an improved version of One-Against-All (OAA) method for multiclass SVM classification based on a decision tree approach. The proposed decision tree based OAA (DT-OAA) is aimed at increasing the classification speed of OAA by using posterior probability estimates of binary SVM outputs. DT-OAA decreases the average number of binary SVM tests required in testing phase to a greater extent when compared to OAA and other multiclass SVM methods. For a balanced multiclass dataset with K classes, under best situation, DT-OAA requires only (K + 1)/2 binary tests on an average as opposed to K binary tests in OAA; however, on imbalanced multiclass datasets we observed DT-OAA to be much faster with proper selection of order in which the binary SVMs are arranged in the decision tree. Computational comparisons on publicly available datasets indicate that the proposed method can achieve almost the same classification accuracy as that of OAA, but is much faster in decision making.     

Comparing Combination Rules of Pairwise Neural Networks Classifiers

A decomposition approach to multiclass classification problems consists in decomposing a multiclass problem into a set of binary ones. Decomposition splits the complete multiclass problem into a set of smaller classification problems involving only two classes (binary classification: dichotomies). With a decomposition, one has to define a recombination which recomposes the outputs of the dichotomizers in order to solve the original multiclass problem. There are several approaches to the decomposition, the most famous ones being one-against-all and one-against-one also called pairwise. In this paper, we focus on pairwise decomposition approach to multiclass classification with neural networks as the base learner for the dichotomies. We are primarily interested in the different possible ways to perform the so-called recombination (or decoding). We review standard methods used to decode the decomposition generated by a one-against-one approach. New decoding methods are proposed and compared to standard methods. A stacking decoding is also proposed which consists in replacing the whole decoding or a part of it by a trainable classifier to arbiter among the conflicting predictions of the pairwise classifiers. Proposed methods try to cope with the main problem while using pairwise decomposition: the use of irrelevant classifiers. Substantial gain is obtained on all datasets used in the experiments. Based on the above, we provide future research directions which consider the recombination problem as an ensemble method.     

A comparison of methods for multiclass support vector machines

Support vector machines (SVMs) were originally designed for binary classification. How to effectively extend it for multiclass classification is still an ongoing research issue. Several methods have been proposed where typically we construct a multiclass classifier by combining several binary classifiers. Some authors also proposed methods that consider all classes at once. As it is computationally more expensive to solve multiclass problems, comparisons of these methods using large-scale problems have not been seriously conducted. Especially for methods solving multiclass SVM in one step, a much larger optimization problem is required so up to now experiments are limited to small data sets. In this paper we give decomposition implementations for two such "all-together" methods. We then compare their performance with three methods based on binary classifications: "one-against-all," "one-against-one," and directed acyclic graph SVM (DAGSVM). Our experiments indicate that the "one-against-one" and DAG methods are more suitable for practical use than the other methods. Results also show that for large problems methods by considering all data at once in general need fewer support vectors.     

后验概率在多分类支持向量机上的应用

支持向量机是基于统计学习理论的一种新的分类规则挖掘方法。在已有多分类支持向量机基础上,首次提出了几何距离多分类支持向量分类器;随后,将二值支持向量机的后验概率输出也推广到多分类问题,避免了使用迭代算法,在快速预测的前提下提高了预测准确率。数值实验的结果表明,这两种方法都具有很好的推广性能,能明显提高分类器对未知样本的分类准确率。     

A heuristic supervised Euclidean data difference dimension reduction for KNN classifier and its application to visual place classification

In this paper, we propose a novel supervised dimension reduction algorithm based on K-nearest neighbor (KNN) classifier. The proposed algorithm reduces the dimension of data in order to improve the accuracy of the KNN classification. This heuristic algorithm proposes independent dimensions which decrease Euclidean distance of a sample data and its K-nearest within-class neighbors and increase Euclidean distance of that sample and its M-nearest between-class neighbors. This algorithm is a linear dimension reduction algorithm which produces a mapping matrix for projecting data into low dimension. The dimension reduction step is followed by a KNN classifier. Therefore, it is applicable for high-dimensional multiclass classification. Experiments with artificial data such as Helix and Twin-peaks show ability of the algorithm for data visualization. This algorithm is compared with state-of-the-art algorithms in classification of eight different multiclass data sets from UCI collection. Simulation results have shown that the proposed algorithm outperforms the existing algorithms. Visual place classification is an important problem for intelligent mobile robots which not only deals with high-dimensional data but also has to solve a multiclass classification problem. A proper dimension reduction method is usually needed to decrease computation and memory complexity of algorithms in large environments. Therefore, our method is very well suited for this problem. We extract color histogram of omnidirectional camera images as primary features, reduce the features into a low-dimensional space and apply a KNN classifier. Results of experiments on five real data sets showed superiority of the proposed algorithm against others.     

Direct estimation of class membership probabilities for multiclass classification using multiple scores

Accurate estimation of class membership probability is needed for many applications in data mining and decision-making, to which multiclass classification is often applied. Since existing methods for estimation of class membership probability are designed for binary classification, in which only a single score outputted from a classifier can be used, an approach for multiclass classification requires both a decomposition of a multiclass classifier into binary classifiers and a combination of estimates obtained from each binary classifier to a target estimate. We propose a simple and general method for directly estimating class membership probability for any class in multiclass classification without decomposition and combination, using multiple scores not only for a predicted class but also for other proper classes. To make it possible to use multiple scores, we propose to modify or extend representative existing methods. As a non-parametric method, which refers to the idea of a binning method as proposed by Zadrozny et al., we create an “accuracy table” by a different method. Moreover we smooth accuracies on the table with methods such as the moving average to yield reliable probabilities (accuracies). As a parametric method, we extend Platt’s method to apply a multiple logistic regression. On two different datasets (open-ended data from Japanese social surveys and the 20 Newsgroups) both with Support Vector Machines and naive Bayes classifiers, we empirically show that the use of multiple scores is effective in the estimation of class membership probabilities in multiclass classification in terms of cross entropy, the reliability diagram, the ROC curve and AUC (area under the ROC curve), and that the proposed smoothing method for the accuracy table works quite well. Finally, we show empirically that in terms of MSE (mean squared error), our best proposed method is superior to an expansion for multiclass classification of a PAV method proposed by Zadrozny et al., in both the 20 Newsgroups dataset and the Pendigits dataset, but is slightly worse than the state-of-the-art method, which is an expansion for multiclass classification of a combination of boosting and a PAV method, on the Pendigits dataset.

Least squares twin support vector machines for pattern classification

In this paper we formulate a least squares version of the recently proposed twin support vector machine (TSVM) for binary classification. This formulation leads to extremely simple and fast algorithm for generating binary classifiers based on two non-parallel hyperplanes. Here we attempt to solve two modified primal problems of TSVM, instead of two dual problems usually solved. We show that the solution of the two modified primal problems reduces to solving just two systems of linear equations as opposed to solving two quadratic programming problems along with two systems of linear equations in TSVM. Classification using nonlinear kernel also leads to systems of linear equations. Our experiments on publicly available datasets indicate that the proposed least squares TSVM has comparable classification accuracy to that of TSVM but with considerably lesser computational time. Since linear least squares TSVM can easily handle large datasets, we further went on to investigate its efficiency for text categorization applications. Computational results demonstrate the effectiveness of the proposed method over linear proximal SVM on all the text corpuses considered.     

An all-pair quantum SVM approach for big data multiclass classification

In this paper, we discuss a quantum approach for the all-pair multiclass classification problem. In an all-pair approach, there is one binary classification problem for each pair of classes, and so there are k(k???1)/2 classifiers for a k-class classification problem. As compared to the classical multiclass support vector machine that can be implemented with polynomial run time complexity, our approach exhibits exponential speedup due to quantum computing. The quantum all-pair algorithm can also be used with other classification algorithms, and a speedup gain can be achieved as compared to their classical counterparts.     

一种基于改进的支持向量机的多类文本分类方法

提出了一种基于二叉树、预抽取支持向量机及循环迭代算法的改进的支持向量机(SVM)的多类文本分类方法, 与现有的多类分类SVM算法相比,该方法具有较高的计算效率。给出了具体实现过程并将其用于文本分类中,实验表明该算法用于文本分类的有效性及其高效率。     

Multiclass classification and gene selection with a stochastic algorithm

Microarray technology allows for the monitoring of thousands of gene expressions in various biological conditions, but most of these genes are irrelevant for classifying these conditions. Feature selection is consequently needed to help reduce the dimension of the variable space. Starting from the application of the stochastic meta-algorithm “Optimal Feature Weighting” (OFW) for selecting features in various classification problems, focus is made on the multiclass problem that wrapper methods rarely handle. From a computational point of view, one of the main difficulties comes from the unbalanced classes situation that is commonly encountered in microarray data. From a theoretical point of view, very few methods have been developed so far to minimize the classification error made on the minority classes. The OFW approach is developed to handle multiclass problems using CART and one-vs-one SVM classifiers. Comparisons are made with other multiclass selection algorithms such as Random Forests and the filter method F-test on five public microarray data sets with various complexities. Statistical relevancy of the gene selections is assessed by computing the performances and the stability of these different approaches and the results obtained show that the two proposed approaches are competitive and relevant to selecting genes classifying the minority classes.Application to a pig folliculogenesis study follows and a detailed interpretation of the genes that were selected shows that the OFW approach answers the biological question.     

Multi-class pattern classification using neural networks

Multi-class pattern classification has many applications including text document classification, speech recognition, object recognition, etc. Multi-class pattern classification using neural networks is not a trivial extension from two-class neural networks. This paper presents a comprehensive and competitive study in multi-class neural learning with focuses on issues including neural network architecture, encoding schemes, training methodology and training time complexity. Our study includes multi-class pattern classification using either a system of multiple neural networks or a single neural network, and modeling pattern classes using one-against-all, one-against-one, one-against-higher-order, and P-against-Q. We also discuss implementations of these approaches and analyze training time complexity associated with each approach. We evaluate six different neural network system architectures for multi-class pattern classification along the dimensions of imbalanced data, large number of pattern classes, large vs. small training data through experiments conducted on well-known benchmark data.     

基于多核学习的多特征融合图像分类研究

图像分类任务是计算机视觉中的一个重要研究方向。组合多种特征在一定程度上能够使得图像分类准确度得到提高。然而,如何组合多种图像特征是一个悬而未决的难题。提出了一种基于多类多核学习的多特征融合算法,并应用到图像分类任务。算法在有效地利用多核学习自动选取对当前任务有价值特征的优势的同时,避免了在多核学习中将多类问题分解为多个二分问题。在图像特征表示方面,使用字典自学习方法。实验结果表明,提出的算法能够有效地提高图像分类的准确度。     

Domain density description for multiclass pattern classification with reduced computational load

We propose a novel classification method that can reduce the computational cost of training and testing for multiclass problems. The proposed method uses the distance in feature space between a test sample and high-density region or domain that can be described by support vector learning. The proposed method shows faster training speed and has ability to represent the nonlinearity of data structure using a smaller percentage of available data sample than the existing methods for multiclass problems. To demonstrate the potential usefulness of the proposed approach, we evaluate the performance about artificial and actual data. Experimental results show that the proposed method has better accuracy and efficiency than the existing methods.     

Electrocardiogram beat classification using empirical mode decomposition and multiclass directed acyclic graph support vector machine

In this paper, a classifier motivated from statistical learning theory, i.e., support vector machine, with a new approach based on multiclass directed acyclic graph has been proposed for classification of four types of electrocardiogram signals. The motivation for selecting Directed Acyclic Graph Support Vector Machine (DAGSVM) is to have more accurate classifier with less computational cost. Empirical mode decomposition and subsequently singular value decomposition have been used for computing the feature vector matrix. Further, fivefold cross-validation and particle swarm optimization have been used for optimal selection of SVM model parameters to improve the performance of DAGSVM. A comparison has been made between proposed algorithm and other two classifiers, i.e., K-Nearest Neighbor (KNN) and Artificial Neural Network (ANN). The DAGSVM has yielded an average accuracy of 98.96% against 95.83% and 96.66% for the KNN and the ANN, respectively. The results obtained clearly confirm the superiority of the DAGSVM approach over other classifiers.     

A Fast Multiclass Classification Algorithm Based on Cooperative Clustering

We present a fast multiclass classification algorithm to address the multiclass problems with a new clustering method, namely cooperative clustering. In the method of cooperative clustering, we iteratively compute the cluster centers of all classes simultaneously. For every cluster center in a class, a cluster center in an adjacent class is selected and the pair of cluster centers is drawn towards the boundary. In this way, the data set around a class is found and the data set plus the data in this class can be trained to form a classifier. With cooperative clustering, one binary classifier in the one-vs-all approach can be trained with far less samples. Furthermore, a kNN method is proposed to accelerate the classifying procedure. With this algorithm, both training and classification efficiency are improved with a slight impact on classification accuracy.     

Micro‐Doppler classification of human movements using spectrogram spatial features and support vector machine

Accurate distinction of dynamic moving objects especially in the context of security surveillance attracts great attention of researchers and practitioners. In the same context, present study proposes an advancement in feature extraction method from the micro‐Doppler spectrogram with the application of spatial statistics for moving human subject classification which minimizes the spectrogram analysis. A novel approach of spatial feature extraction from whole image spectrogram, followed by support vector machine (SVM) classifiers algorithm for multiclass classification, has been proposed in the present study. The proposed method has been tested for prediction accuracy and validated by applying on a very close and important five distinct human activities (which usually arise at any security observation site) as reported in the available literature. The results obtained adopting the proposed approach exhibit high accuracy for multiclass classification; yielding cross‐validation accuracy of 96.7% while actual predication of testing data provides the accuracy of 93.33%. For the prediction of accurate data classes, the post‐processing of the spectrogram prior to feature definition has also been performed using spatial based methods to enhance micro‐Doppler signatures.     

一种基于反向文本频率互信息的文本挖掘算法研究

针对传统的文本分类算法存在着各特征词对分类结果的影响相同,分类准确率较低,同时造成了算法时间复杂度的增加,在分析了文本分类系统的一般模型,以及在应用了互信息量的特征提取方法提取特征项的基础上,提出一种基于反向文本频率互信息熵文本分类算法。该算法首先采用基于向量空间模型(vector spacemodel,VSM)对文本样本向量进行特征提取;然后对文本信息提取关键词集,筛选文本中的关键词,采用互信息来表示并计算词汇与文档分类相关度;最后计算关键词在文档中的权重。实验结果表明了提出的改进算法与传统的分类算法相比,具有较高的运算速度和较强的非线性映射能力,在收敛速度和准确程度上也有更好的分类效果。