A Novel and Principled Multiclass Support Vector Machine

Support vector machines (SVMs) have been demonstrated very efficient for binary classification problems; however, computationally efficient and effective multiclass SVMs are still missing. Most existing multiclass SVM classifiers are constructed either by combining multiple binary SVM classifiers, which often perform moderately for some problems, or by converting multiclass problems into one single optimization problem, which is unfortunately computationally expensive. To address these issues, a novel and principled multiclass SVM based on geometric properties of hyperspheres, termed SVMGH, is proposed in this paper. Different from existing SVM‐based methods that seek a cutting hyperplane between two classes, SVMGH draws the discriminative information of each class by constructing a minimum hypersphere containing all class members, and then defines a label function based on the geometric properties of the minimum hyperspheres. We prove theoretically the geometric properties of the minimum hyperspheres to guarantee the validation of SVMGH. The computational efficiency is enhanced by a data reduction strategy as well as a fast training method. Experimental results demonstrate that the proposed SVMGH shows better performance and higher computational efficiency than the state of the art on multiclassification problems while maintaining comparable performance and efficiency on binary classification problems.     

一种基于混合二叉树结构的多类支持向量机分类算法

为提高多类支持向量机的分类效率,提出了一种基于混合二叉树结构的多类支持向量机分类算法。该混合二叉树中的每个内部结点对应一个分割超平面,该超平面通过计算两个距离最远的类的质心而获得,即该超平面为连接两质心线段的垂直平分线。每个终端结点(即决策结点)对应一个支持向量机,它的训练集不再是质心而是两类(组)样本集。该分类模型通常是超平面和支持向量机的混合结构,其中超平面实现训练早期的近似划分,以提升分类速度;而支持向量机完成最终的精确分类,以保证分类精度。实验结果表明,相比于经典的多类支持向量机方法,该算法在保证分类精度的前提下,能够有效缩短计算时间,提升分类效率。     

A decision based one-against-one method for multi-class support vector machine

The support vector machine (SVM) has a high generalisation ability to solve binary classification problems, but its extension to multi-class problems is still an ongoing research issue. Among the existing multi-class SVM methods, the one-against-one method is one of the most suitable methods for practical use. This paper presents a new multi-class SVM method that can reduce the number of hyperplanes of the one-against-one method and thus it returns fewer support vectors. The proposed algorithm works as follows. While producing the boundary of a class, no more hyperplanes are constructed if the discriminating hyperplanes of neighbouring classes happen to separate the rest of the classes. We present a large number of experiments that show that the training time of the proposed method is the least among the existing multi-class SVM methods. The experimental results also show that the testing time of the proposed method is less than that of the one-against-one method because of the reduction of hyperplanes and support vectors. The proposed method can resolve unclassifiable regions and alleviate the over-fitting problem in a much better way than the one-against-one method by reducing the number of hyperplanes. We also present a direct acyclic graph SVM (DAGSVM) based testing methodology that improves the testing time of the DAGSVM method.     

Fuzzy rules extraction from support vector machines for multi-class classification

This paper proposes a new method for fuzzy rule extraction from trained support vector machines (SVMs) for multi-class problems, named FREx_SVM. SVMs have been used in a variety of applications. However, they are considered “black box models,” where no interpretation about the input–output mapping is provided. Some methods to reduce this limitation have already been proposed, but they are restricted to binary classification problems and to the extraction of symbolic rules with intervals or functions in their antecedents. In order to improve the interpretability of the generated rules, this paper presents a new model for extracting fuzzy rules from a trained SVM. The proposed model is suited for classification in multi-class problems and includes a wrapper feature selection algorithm. It is evaluated in four benchmark databases, and results obtained demonstrate its capacity to generate a reduced set of interpretable fuzzy rules that explains both the classification database and the influence of each input variable on the determination of the final class.     

Using discriminant analysis for multi-class classification: an experimental investigation

Many supervised machine learning tasks can be cast as multi-class classification problems. Support vector machines (SVMs) excel at binary classification problems, but the elegant theory behind large-margin hyperplane cannot be easily extended to their multi-class counterparts. On the other hand, it was shown that the decision hyperplanes for binary classification obtained by SVMs are equivalent to the solutions obtained by Fisher's linear discriminant on the set of support vectors. Discriminant analysis approaches are well known to learn discriminative feature transformations in the statistical pattern recognition literature and can be easily extend to multi-class cases. The use of discriminant analysis, however, has not been fully experimented in the data mining literature. In this paper, we explore the use of discriminant analysis for multi-class classification problems. We evaluate the performance of discriminant analysis on a large collection of benchmark datasets and investigate its usage in text categorization. Our experiments suggest that discriminant analysis provides a fast, efficient yet accurate alternative for general multi-class classification problems. Tao Li is currently an assistant professor in the School of Computer Science at Florida International University. He received his Ph.D. degree in Computer Science from University of Rochester in 2004. His primary research interests are: data mining, machine learning, bioinformatics, and music information retrieval. Shenghuo Zhu is currently a researcher in NEC Laboratories America, Inc. He received his B.E. from Zhejiang University in 1994, B.E. from Tsinghua University in 1997, and Ph.D degree in Computer Science from University of Rochester in 2003. His primary research interests include information retrieval, machine learning, and data mining. Mitsunori Ogihara received a Ph.D. in Information Sciences at Tokyo Institute of Technology in 1993. He is currently Professor and Chair of the Department of Computer Science at the University of Rochester. His primary research interests are data mining, computational complexity, and molecular computation.     

基于原型超平面的多类最接近支持向量机

基于广义特征值的最接近支持向量机（proximal support vector machine via generalized eigenvalues,GEPSVM）摒弃了传统意义下支持向量机典型平面的平行约束,代之以通过优化使每类原型平面尽可能接近本类样本,同时尽可能远离它类样本的准则来解析获得原型平面;从而避免了SVM的二次规划,其分类性能达到甚至超过了SVM．但GEPSVM仍存在如下不足：①仅对两分类问题而提出,无法直接求解多分类问题;②存在正则化因子的选择问题;③求解原型平面的广义特征值问题中所涉及的矩阵一般仅为半正定,容易导致奇异性问题．通过定义新的准则,构建了一个能直接求解多个原型超平面的多分类方法,称之为基于原型超平面的多类最接近支持向量机,较之GEPSVM,该方法优势在于：①无正则化因子选择的困扰;②可同时求解多个超平面,对两分类问题,分类性能达到甚至优于GEPSVM;③超平面的选择问题转化为简单特征值而非广义特征值求解问题;④原型平面的选择只依赖于本类样本,故不必考虑多分类情形时的数据不平衡问题．     

多决策模板分类器融合

针对多类分类问题提出了一种新的度量层分类器融合方法,为每个模式类设置多个决策模板,每个决策模板针对一种容易发生的分类错误,从而能够有效地降低错误率;此外,采用模糊系统表示Meta层样本与各个决策模板之间的关系,能够比较准确地计算样本属于各个模式类的总分类置信度。从公用数据仓库中选取了三个较大规模数据集对新方法进行测试,并且与k-近邻规则、投票法、朴素贝叶斯法、线性规则、模板匹配法等常用的分类器融合方法进行了比较。大量实验结果表明,对于类别数在3~15之间的分类问题,该方法具有较好的综合性能。     

基于融合的多类支持向量机

支持向量机可以处理2类问题,通过“一对一”和“一对多”方式能将2类支持向量机扩展为多类支持向量机。提出一种基于两类支持向量机融合的多类支持向量机构成方法。对分类器融合采用极大值法、极小值法、乘积法、均值法、中值法、投票法和各种决策模板融合方法。在日本女性表情数据库JAFFE上应用该方法进行人脸表情识别,结果证明了其有效性。     

Fingerprint classification using one-vs-all support vector machines dynamically ordered with naı¨ve Bayes classifiers

Fingerprint classification reduces the number of possible matches in automated fingerprint identification systems by categorizing fingerprints into predefined classes. Support vector machines (SVMs) are widely used in pattern classification and have produced high accuracy when performing fingerprint classification. In order to effectively apply SVMs to multi-class fingerprint classification systems, we propose a novel method in which the SVMs are generated with the one-vs-all (OVA) scheme and dynamically ordered with na?¨ve Bayes classifiers. This is necessary to break the ties that frequently occur when working with multi-class classification systems that use OVA SVMs. More specifically, it uses representative fingerprint features as the FingerCode, singularities and pseudo ridges to train the OVA SVMs and na?¨ve Bayes classifiers. The proposed method has been validated on the NIST-4 database and produced a classification accuracy of 90.8% for five-class classification with the statistical significance. The results show the benefits of integrating different fingerprint features as well as the usefulness of the proposed method in multi-class fingerprint classification.     

Combining binary classifiers in different dichotomy spaces for text categorization

Several supervised machine learning applications are commonly represented as multi-class problems, but it is harder to distinguish several classes rather than just two classes. In contrast to the approaches one-against-all and all-pairs that transform a multi-class problem into a set of binary problems, Dichotomy Transformation (DT) converts a multi-class problem into a different problem where the goal is to verify if a pair of documents belongs to the same class or not. To perform this task, DT generates a dichotomy set obtained by combining a pair of documents, each belongs to either a positive class (documents in the pair that have the same class) or a negative class (documents in the pair that come from different classes). The definition of this dichotomy set plays an important role in the overall accuracy of the system. So, an alternative to avoid searching for the best dichotomy set is using multiple classifier systems because we can have many different sets where each one is used to train one binary classifier instead of having only one dichotomy set. Herein we propose Combined Dichotomy Transformations (CoDiT), a Text Categorization system that combines binary classifiers that are trained with different dichotomy sets using DT. By using DT, the number of training examples increases exponentially when compared with the original training set. This is a desirable property because each classifier can be trained with different data without reducing the number of examples or features. Therefore, it is possible to compose an ensemble with diverse and strong classifiers. Experiments using 14 databases show that CoDiT achieves statistically better results in comparison to SVM, Bagging, Random Subspace, BoosTexter, and Random Forest.     

基于判别性解析字典与分类器学习的模式分类

稀疏表示（Sparse Representation,SR）和字典学习（Dictionary Learning,DL）已被广泛用于编码特征数据并有助于模式分类。现有方法通常使用[l1/l2]范数或每类使用特定字典来强制SR的类判别能力,但由此产生的类判别能力有限。在这项工作中,提出使用训练集作为训练样本的SR的综合字典,因为它为每类数据提供了最自然的特定字典。训练集的类信息可用于增强SR的判别能力：精确块对角线结构,意味着每个数据只能由同类中数据表示。为了使测试阶段容易,在训练集的判别SR的监督下学习解析字典和线性分类器。一旦学习了解析字典和分类器,测试阶段就非常简单并且高效。称之为判别分析字典与分类器学习（Discriminative Analysis Dictionary and Classifier Learning,DADCL）。大量实验表明,该方法具有较好的分类性能。     

基于SVM 的二叉树多类分类算法及其在故障诊断中的应用

基于结构风险最小化原则的支持向量机(SVM)对小样本决策具有较好的学习推广性。但由于常规SVM算法是从2类分类问题推导出的，在解决故障诊断这种典型的多类分类问题时存在因雄，因而提出一种依赖故障优先级的基于SVM的二叉树多级分类器实现(2PTMC)方法，该方法具有简单、直观，重复训练样本少的优点。通过将其应用于柴油机振动信号的故障诊断，获得了令人满意的效果。     

Cost-Sensitive back-propagation neural networks with binarization techniques in addressing multi-class problems and non-competent classifiers

Multi-class classification problems can be addressed by using decomposition strategy. One of the most popular decomposition techniques is the One-vs-One (OVO) strategy, which consists of dividing multi-class classification problems into as many as possible pairs of easier-to-solve binary sub-problems. To discuss the presence of classes with different cost, in this paper, we examine the behavior of an ensemble of Cost-Sensitive Back-Propagation Neural Networks (CSBPNN) with OVO binarization techniques for multi-class problems. To implement this, the original multi-class cost-sensitive problem is decomposed into as many sub-problems as possible pairs of classes and each sub-problem is learnt in an independent manner using CSBPNN. Then a combination method is used to aggregate the binary cost-sensitive classifiers. To verify the synergy of the binarization technique and CSBPNN for multi-class cost-sensitive problems, we carry out a thorough experimental study. Specifically, we first develop the study to check the effectiveness of the OVO strategy for multi-class cost-sensitive learning problems. Then, we develop a comparison of several well-known aggregation strategies in our scenario. Finally, we explore whether further improvement can be achieved by using the management of non-competent classifiers. The experimental study is performed with three types of cost matrices and proper statistical analysis is employed to extract the meaningful findings.     

Using robust dispersion estimation in support vector machines

In this paper, a novel Support Vector Machine (SVM) variant, which makes use of robust statistics, is proposed. We investigate the use of statistically robust location and dispersion estimators, in order to enhance the performance of SVMs and test it in two-class and multi-class classification problems. Moreover, we propose a novel method for class specific multi-class SVM, which makes use of the covariance matrix of only one class, i.e., the class that we are interested in separating from the others, while ignoring the dispersion of other classes. We performed experiments in artificial data, as well as in many real world publicly available databases used for classification. The proposed approach performs better than other SVM variants, especially in cases where the training data contain outliers. Finally, we applied the proposed method for facial expression recognition in three well known facial expression databases, showing that it outperforms previously published attempts.     

A simple and fast multi-class piecewise linear pattern classifier

A simple and fast multi-class piecewise linear classifier is proposed and implemented. For a pair of classes, the piecewise linear boundary is a collection of segments of hyperplanes created as perpendicular bisectors of line segments linking centroids of the classes or parts of classes. For a multi-class problem, a binary partition tree is initially created which represents a hierarchical division of given pattern classes into groups, with each non-leaf node corresponding to some group. After that, a piecewise linear boundary is constructed for each non-leaf node of the partition tree as for a two-class problem. The resulting piecewise linear boundary is a set of boundaries corresponding to all non-leaf nodes of the tree. The basic data structures of algorithms of synthesis of a piecewise linear classifier and classification of unknown patterns are described. The proposed classifier is compared with a number of known pattern classifiers by benchmarking with the use of real-world data sets.     

A corporate credit rating model using multi-class support vector machines with an ordinal pairwise partitioning approach

Predicting corporate credit-rating using statistical and artificial intelligence (AI) techniques has received considerable research attention in the literature. In recent years, multi-class support vector machines (MSVMs) have become a very appealing machine-learning approach due to their good performance. Until now, researchers have proposed a variety of techniques for adapting support vector machines (SVMs) to multi-class classification, since SVMs were originally devised for binary classification. However, most of them have only focused on classifying samples into nominal categories; thus, the unique characteristic of credit-rating - ordinality - seldom has been considered in the proposed approaches. This study proposes a new type of MSVM classifier (named OMSVM) that is designed to extend the binary SVMs by applying an ordinal pairwise partitioning (OPP) strategy. Our model can efficiently and effectively handle multiple ordinal classes. To validate OMSVM, we applied it to a real-world case of bond rating. We compared the results of our model with those of conventional MSVM approaches and other AI techniques including MDA, MLOGIT, CBR, and ANNs. The results showed that our proposed model improves the performance of classification in comparison to other typical multi-class classification techniques and uses fewer computational resources.     

支持向量机多类目标分类器的结构简化研究

由于支持向量机(SVM)在模式识别和回归分析中有着独特优势，因此成为近来研究的热点，其优势主要体现在处理非线性和高维数据问题方面。最初的SVM特别适合解决两类目标分类问题，而对于多类目标分类，则需将其转化为多个两类目标分类问题，相应地即可构造多个两类目标子分类器，但由于这种情况导致了分类器结构的过于复杂，从而导致判决速度的降低。为了快速地进行分类．提出了一种简化结构的多类目标分类器，其不仅使得子分类器数目大大减少，而且使分类速度明显提高；同时对其分类精度和复杂度进行了对比分析。实验结果证明。该分类器是有效的。     

Support Vector Machines for TCP traffic classification

Support Vector Machines (SVM) represent one of the most promising Machine Learning (ML) tools that can be applied to the problem of traffic classification in IP networks. In the case of SVMs, there are still open questions that need to be addressed before they can be generally applied to traffic classifiers. Having being designed essentially as techniques for binary classification, their generalization to multi-class problems is still under research. Furthermore, their performance is highly susceptible to the correct optimization of their working parameters. In this paper we describe an approach to traffic classification based on SVM. We apply one of the approaches to solving multi-class problems with SVMs to the task of statistical traffic classification, and describe a simple optimization algorithm that allows the classifier to perform correctly with as little training as a few hundred samples. The accuracy of the proposed classifier is then evaluated over three sets of traffic traces, coming from different topological points in the Internet. Although the results are relatively preliminary, they confirm that SVM-based classifiers can be very effective at discriminating traffic generated by different applications, even with reduced training set sizes.