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.     

一种新的二叉树多类支持向量机算法

采用二叉树结构对多个二值支持向量机(SVM)子分类器组合,可实现多类问题的分类,并且还可克服传统多类SVM算法存在的不可分区域的情况。针对现有二叉树多类SVM方法未采用有效的二叉树生成算法,该文采用聚类分析中的类距离思想,提出了一种新的基于二叉树的多类SVM分类方法。实验结果表明,新算法具有较高的推广性能。     

Adaptive binary tree for fast SVM multiclass classification

This paper presents an adaptive binary tree (ABT) to reduce the test computational complexity of multiclass support vector machine (SVM). It achieves a fast classification by: (1) reducing the number of binary SVMs for one classification by using separating planes of some binary SVMs to discriminate other binary problems; (2) selecting the binary SVMs with the fewest average number of support vectors (SVs). The average number of SVs is proposed to denote the computational complexity to exclude one class. Compared with five well-known methods, experiments on many benchmark data sets demonstrate our method can speed up the test phase while remain the high accuracy of SVMs.     

Multiclass LS-SVMs: Moderated Outputs and Coding-Decoding Schemes

A common way of solving the multiclass categorization problem is to reformulate the problem into a set of binary classification problems. Discriminative binary classifiers like, e.g., Support Vector Machines (SVMs), directly optimize the decision boundary with respect to a certain cost function. In a pragmatic and computationally simple approach, Least Squares SVMs (LS-SVMs) are inferred by minimizing a related regression least squares cost function. The moderated outputs of the binary classifiers are obtained in a second step within the evidence framework. In this paper, Bayes' rule is repeatedly applied to infer the posterior multiclass probabilities, using the moderated outputs of the binary plug-in classifiers and the prior multiclass probabilities. This Bayesian decoding motivates the use of loss function based decoding instead of Hamming decoding. For SVMs and LS-SVMs with linear kernel, experimental evidence suggests the use of one-versus-one coding. With a Radial Basis Function kernel one-versus-one and error correcting output codes yield the best performances, but simpler codings may still yield satisfactory results. This revised version was published online in August 2006 with corrections to the Cover Date.     

一种新的基于二叉树的SVM多类分类方法

介绍了几种常用的支持向量机多类分类方法,分析其存在的问题及缺点。提出了一种基于二叉树的支持向量机多类分类方法（BT SVM）,并将基于核的自组织映射引入进行聚类。结果表明,采用该方法进行多类分类比1 v r SVMs和1 v 1 SVMs具有更高的分类精度。     

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

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

Pattern classification with mixtures of weighted least-squares support vector machine experts

Support Vector Machine (SVM) classifiers are high-performance classification models devised to comply with the structural risk minimization principle and to properly exploit the kernel artifice of nonlinearly mapping input data into high-dimensional feature spaces toward the automatic construction of better discriminating linear decision boundaries. Among several SVM variants, Least-Squares SVMs (LS-SVMs) have gained increased attention recently due mainly to their computationally attractive properties coming as the direct result of applying a modified formulation that makes use of a sum-squared-error cost function jointly with equality, instead of inequality, constraints. In this work, we present a flexible hybrid approach aimed at augmenting the proficiency of LS-SVM classifiers with regard to accuracy/generalization as well as to hyperparameter calibration issues. Such approach, named as Mixtures of Weighted Least-Squares Support Vector Machine Experts, centers around the fusion of the weighted variant of LS-SVMs with Mixtures of Experts models. After the formal characterization of the novel learning framework, simulation results obtained with respect to both binary and multiclass pattern classification problems are reported, ratifying the suitability of the novel hybrid approach in improving the performance issues considered.     

Parallelizing multiclass support vector machines for scalable image annotation

Machine learning techniques have facilitated image retrieval by automatically classifying and annotating images with keywords. Among them, Support Vector Machines (SVMs) are used extensively due to their generalization properties. SVM was initially designed for binary classifications. However, most classification problems arising in domains such as image annotation usually involve more than two classes. Notably, SVM training is a computationally intensive process especially when the training dataset is large. This paper presents a resource aware parallel multiclass SVM algorithm (named RAMSMO) for large-scale image annotation which partitions the training dataset into smaller binary chunks and optimizes SVM training in parallel using a cluster of computers. A genetic algorithm-based load balancing scheme is designed to optimize the performance of RAMSMO in balancing the computation of multiclass data chunks in heterogeneous computing environments. RAMSMO is evaluated in both experimental and simulation environments, and the results show that it reduces the training time significantly while maintaining a high level of accuracy in classifications.     

超球体多类支持向量机理论

目前的多类分类器大多是经二分类器组合而成的,存在训练速度较慢的问题,在分类类别多的时候,会遇到很大困难,超球体多类支持向量机将超球体单类支持向量机扩展到多类问题,由于每类样本只参与一个超球体支持向量机的训练.因此,这是一种直接多类分类器,训练效率明显提高.为了有效训练超球体多类支持向量机,利用SMO算法思想,提出了超球体支持向量机的快速训练算法.同时对超球体多类支持向量机的推广能力进行了理论上的估计.数值实验表明,在分类类别较多的情况,这种分类器的训练速度有很大提高,非常适合解决类别数较多的分类问题.超球体多类支持向量机为研究快速直接多类分类器提供了新的思路.     

基于混合粒子群算法的运动估计研究

针对块匹配运动估计算法中传统搜索方法的不足,提出了一种新的基于混合粒子群的块匹配运动估计算法。在保留系统随机搜索性能的同时根据运动矢量特性合理地设计初始搜索种群,并通过混沌差分进化搜索协同粒子群算法迭代寻优,混沌序列用于优化差分变异算子,以提高算法的精细搜索能力。通过相同点检测技术和恰当的终止计划有效地降低了系统的运算复杂度。经实验测试与验证,该算法在搜索质量和运算复杂度中达到了一种动态平衡的状态,其整体性能高于传统的快速运动估计算法,效果更逼近于穷举搜索法。     

基于概率投票策略的多类支持向量机及应用

传统的支持向量机是基于两类问题提出的,如何将其有效地推广至多类分类仍是一个研究的热点问题。在分析比较现有支持向量机多类分类OVO方法存在的问题及缺点的基础上,该文提出一种新的基于概率投票策略的多类分类方法。在该策略中,充分考虑了OVO方法中各个两类支持向量机分类器的差异,并将该差异反映到投票分值上。所提多类支持向量机方法不仅具有较好的分类性能,而且有效解决了传统投票策略中存在的拒分区域问题。将基于概率投票的多分类支持向量机作为关键技术应用于实际齿轮箱故障诊断,并与传统投票策略的结果进行对比,表明所提方法的上述优点。     

基于球结构的完全二叉树SVM多类分类算法*

针对一般的SVM方法不能有效地处理不平衡样本数据及现有的偏二叉树结构SVM分类器速度慢的这两个问题,提出了一种基于球结构的完全二叉树SVM多分类算法。该算法利用球结构的SVM考虑了每个类的分布情况,能有效地处理不平衡样本数据;构建完全二叉树结构,使得同层节点所代表的SVM分类器可以并行工作,能提高其训练和分类速度,分类速度相当于折半查找。实例验证两者结合后的算法可实现准确且高效的多类分类。     

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.     

Binary tree of SVM: a new fast multiclass training and classification algorithm

We present a new architecture named Binary Tree of support vector machine (SVM), or BTS, in order to achieve high classification efficiency for multiclass problems. BTS and its enhanced version, c-BTS, decrease the number of binary classifiers to the greatest extent without increasing the complexity of the original problem. In the training phase, BTS has N-1 binary classifiers in the best situation (N is the number of classes), while it has log/sub 4/3/((N+3)/4) binary tests on average when making a decision. At the same time the upper bound of convergence complexity is determined. The experiments in this paper indicate that maintaining comparable accuracy, BTS is much faster to be trained than other methods. Especially in classification, due to its Log complexity, it is much faster than directed acyclic graph SVM (DAGSVM) and ECOC in problems that have big class number.     

一种新的多类支持向量机决策方法及其应用

讨论和比较了现有的几种多类SVM方法．在此基础上,提出了一种组合多个两类分类器结果的多类SVM决策方法．在该方法中,定义了新的决策函数,其值是在传统投票决策值的基础上乘以不同分类器的权重．新的多类SVM在一定程度上解决了传统投票决策方法的不可分区域问题,因此具有更好的分类性能．最后,将新方法作为关键技术应用于故障诊断实例,实际诊断结果证明了所提多类SVM决策方法的优越性．     

一种新的支持向量机多类分类方法

分析了目前的支持向量机多类分类方法存在的问题以及缺点．针对以上问题及缺点，提出了基于二叉树的支持向量机的多类分类方法，并在UCI数据库上进行了验证，取得了良好效果．     

A new fast algorithm for multiclass hyperspectral image classification with SVM

The support vector machine (SVM) has been a dominant machine-learning technique in the last decade and has demonstrated its efficiency in many applications. Research on classification of hyperspectral images have shown the efficiency of this method to overcome the Hughes phenomenon for classification of such images. A major drawback of classification by SVM is that this classifier was originally developed to solve binary problems, and the algorithms for multiclass problems usually have a high-computational load. In this article, a new and fast method for multiclass problems is proposed. This method has two stages. In the first stage, samples are classified by a maximum likelihood (ML) classifier, and in the second stage, SVM selects the final label of a sample among high-probability classes for that sample by a tree structure. So, for each sample, only some classes must be searched by SVM to find its label. The uncertainty of ML classification for a sample is obtained by the entropy of probabilities, and the number of classes that must be searched by SVM for a sample is obtained based on the uncertainty of that sample in the primary ML classification. This approach is compared with two widely used multiclass algorithms: one-against-one (OAO) and directed acyclic graph (DAGSVM). The obtained results on real data from the Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) revealed less computational time and better accuracy compared to these multiclass algorithms.     

High dimensional low sample size activity recognition using geometric classifiers

Research on high dimension, low sample size (HDLSS) data has revealed their neighborless nature. This paper addresses the classification of HDLSS image or video data for human activity recognition. Existing approaches often use off-the-shelf classifiers such as nearest neighbor techniques or support vector machines and tend to ignore the geometry of underlying feature distributions. Addressing this issue, we investigate different geometric classifiers and affirm the lack of neighborhoods within HDLSS data. As this undermines proximity based methods and may cause over-fitting for discriminant methods, we propose a QR factorization approach to Nearest Affine Hull (NAH) classification which remedies the HDLSS dilemma and noticeably reduces time and memory requirements of existing methods. We show that the resulting non-parametric models provide smooth decision surfaces and yield efficient and accurate solutions in multiclass HDLSS scenarios. On several action recognition benchmarks, the proposed NAH classifier outperforms other instance based methods and shows competitive or superior performance than SVMs. In addition, for online settings, the proposed NAH method is faster than online SVMs.     

Type-2 fuzzy logic-based classifier fusion for support vector machines

As a machine-learning tool, support vector machines (SVMs) have been gaining popularity due to their promising performance. However, the generalization abilities of SVMs often rely on whether the selected kernel functions are suitable for real classification data. To lessen the sensitivity of different kernels in SVMs classification and improve SVMs generalization ability, this paper proposes a fuzzy fusion model to combine multiple SVMs classifiers. To better handle uncertainties existing in real classification data and in the membership functions (MFs) in the traditional type-1 fuzzy logic system (FLS), we apply interval type-2 fuzzy sets to construct a type-2 SVMs fusion FLS. This type-2 fusion architecture takes considerations of the classification results from individual SVMs classifiers and generates the combined classification decision as the output. Besides the distances of data examples to SVMs hyperplanes, the type-2 fuzzy SVMs fusion system also considers the accuracy information of individual SVMs. Our experiments show that the type-2 based SVM fusion classifiers outperform individual SVM classifiers in most cases. The experiments also show that the type-2 fuzzy logic-based SVMs fusion model is better than the type-1 based SVM fusion model in general.     

快速的支持向量机多类分类研究

研究了支持向量机多类算法DAGSVM（Direct Acyclic Graph SVM）的速度优势,提出了结合DAGSVM和简化支持向量技术的一种快速支持向量机多类分类方法。该方法一方面减少了一次分类所需的两类支持向量机的数量,另一方面减少了支持向量的数量。实验采用UCI和Statlog数据库的多类数据,并和四种多类方法进行比较,结果表明该方法能有效地加快分类速度。