DESIGN OF DECISION TREE VIA KERNELIZED HIERARCHICAL CLUSTERING FOR MULTICLASS SUPPORT VECTOR MACHINES

As a very effective method for universal purpose pattern recognition, support vector machine (SVM) was proposed for dichotomic classification problem, which exhibits a remarkable resistance to overfitting, a feature explained by the fact that it directly implements the principle of structural risk minimization. However, in real world, most of classification problems consist of multiple categories. In an attempt to extend the binary SVM classifier for multiclass classification, decision-tree-based multiclass SVM was proposed recently, in which the structure of decision tree plays an important role in minimizing the classification error. The present study aims at developing a systematic way for the design of decision tree for multiclass SVM. Kernel-induced distance function between datasets was discussed and then kernelized hierarchical clustering was developed and used in determining the structure of decision tree. Further, simulation results on satellite image interpretation show the superiority of the proposed classification strategy over the conventional multiclass SVM algorithms.     

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 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 review on the combination of binary classifiers in multiclass problems

Several real problems involve the classification of data into categories or classes. Given a data set containing data whose classes are known, Machine Learning algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, performing the desired discrimination. Some learning techniques are originally conceived for the solution of problems with only two classes, also named binary classification problems. However, many problems require the discrimination of examples into more than two categories or classes. This paper presents a survey on the main strategies for the generalization of binary classifiers to problems with more than two classes, known as multiclass classification problems. The focus is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are combined to obtain the final prediction.     

A technique for feature selection in multiclass problems

One of the main phases in the development of a system for the classification of remote sensing images is the definition of an effective set of features to be given as input to the classifier. In particular, it is often useful to reduce the number of features available, while saving the possibility to discriminate among the different land-cover classes to be recognized. This paper addresses this topic with reference to applications that involve more than two land-cover classes (multiclass problems). Several criteria proposed in the remote sensing literature are considered and compared with one another and with the criterion presented by the authors. Such a criterion, unlike those usually adopted for multiclass problems, is related to an upper bound to the error probability of the Bayes classifier. As the objective of feature selection is generally to identify a reduced set of features that minimize the errors of the classifier, the aforementioned property is very important because it allows one to select features by taking into account their effects on classification errors. Experiments on two remote sensing datasets are described and discussed. These experiments confirm the effectiveness of the proposed criterion, which performs slightly better than all the others considered in the paper. In addition, the results obtained provide useful information about the behaviour of different classical criteria when applied in multiclass cases.     

Automatic land cover analysis for Tenerife by supervised classification using remotely sensed data

Automatic land cover classification from satellite images is an important topic in many remote sensing applications. In this paper, we consider three different statistical approaches to tackle this problem: two of them, namely the well-known maximum likelihood classification (ML) and the support vector machine (SVM), are noncontextual methods. The third one, iterated conditional modes (ICM), exploits spatial context by using a Markov random field. We apply these methods to Landsat 5 Thematic Mapper (TM) data from Tenerife, the largest of the Canary Islands. Due to the size and the strong relief of the island, ground truth data could be collected only sparsely by examination of test areas for previously defined land cover classes.We show that after application of an unsupervised clustering method to identify subclasses, all classification algorithms give satisfactory results (with statistical overall accuracy of about 90%) if the model parameters are selected appropriately. Although being superior to ML theoretically, both SVM and ICM have to be used carefully: ICM is able to improve ML, but when applied for too many iterations, spatially small sample areas are smoothed away, leading to statistically slightly worse classification results. SVM yields better statistical results than ML, but when investigated visually, the classification result is not completely satisfying. This is due to the fact that no a priori information on the frequency of occurrence of a class was used in this context, which helps ML to limit the unlikely classes.     

基于二叉树的多分类SVM算法在电子邮件过滤中的应用

目前性能较好的多分类算法有1-v-r支持向量机（SVM）、1-1-1SVM、DDAG SVM等，但存在大量不可分区域且训练时间较长的问题。提出一种基于二叉树的多分类SVM算法用于电子邮件的分类与过滤，通过构建二叉树将多分类转化为二值分类，算法采用先聚类再分类的思想，计算测试样本与子类中心的最大相似度和子类间的分离度，以构造决策节点的最优分类超平面。对于C类分类只需C-1个决策函数，从而可节省训练时间。实验表明，该算法得到了较高的查全率、查准率。     

基于小波和支持向量机的光纤微振动传感器模式识别

为实现对双M-Z型光纤传感器的振动信号进行识别,提出一种基于小波能熵和支持向量机(SVM)的光纤传感信号模式识别方法。该方法对小波分解得到的各频段系数求解其能量信息熵,归一化后得到特征向量。其作为SVM的输入,通过选用合适的核函数和多类的分类方法,对SVM多类分类器进行建模。在多种振动信号的条件下,用测试样本对SVM分类器模型进行测试,测试结果表明:该方法对双M-Z型光纤微振动传感器的振动信号的分类达到了较高的识别率。     

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.     

Classification of complex environments using pixel level fusion of satellite data

The present study reports classification and analysis of composite land features using fusion images obtained by fusing two original hyperspectral and multispectral datasets. The high spatial-spectral resolution, multi-instrument and multi-period satellite images were used for fusion. Three pixel level fusion based techniques, Color Normalized Spectral Sharpening (CNSS), Principal Component Spectral Sharpening Transform (PCSST) and Gram-Schmidt Transform (GST), were implemented on the datasets. Performance evaluations of three fusion algorithms were done using classification results. The Support Vector Machine (SVM) and Gaussian Maximum Likelihood Classification (MLC) were used for classification using five types of images, viz. hyperspectral, multispectral and three fused images. Number of classes considered was eight. Sufficient number of ground field data for each class has also been acquired which was needed for supervise based classification. The accuracy was improved from 74.44 to 97.65% when the fused images were considered with SVM classifier. Similarly, the results were improved from 69.25 to 94.61% with original and fused data using MLC classifier. The fusion image technique was found to be superior to the single original image and the SVM is better than the MLC method.

     

一种新型的多元分类支持向量机

最小二乘支持向量机采用最小二乘线性系统代替传统的支持向量机采用二次规划方法解决模式识别问题。该文详细推理和分析了二元分类最小二乘支持向量机算法，构建了多元分类最小二乘支持向量机，并通过典型样本进行测试，结果表明采用多元分类最小二乘支持向量机进行模式识别是有效、可行的。     

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.     

基于支持向量机和距离度量的纹理分类

针对图象纹理分类问题，提出了一种将支持向量机和距离度量相结合，以构成两级组合分类器的分类方法，用该方法分类时，先采用距离度量进行前级分类，然后根据图象的纹理统计特征，采用欧氏距离来度量图象之间的相似性，若符合条件，则给出分类结果，否则拒识，并转入后级分类器，而后级分类器则采用一种新的模式分类方法－支持向量机进行分类，该组合分类方法不仅充分利用了支持向量机识别率高和距离度量速度快的优点，并且还利用距离度量的结果去指导支持向量机的训练和测试，由纹理图象分类的实验表明，该算法具有较高的效率和识别精度，同时也对推动支持向量机这一新的模式分类方法的实际应用具有积极意义。     

A cluster-assumption based batch mode active learning technique

In this paper, we propose an active learning technique for solving multiclass problems with support vector machine (SVM) classifiers. The technique is based on both uncertainty and diversity criteria. The uncertainty criterion is implemented by analyzing the one-dimensional output space of the SVM classifier. A simple histogram thresholding algorithm is used to find out the low density region in the SVM output space to identify the most uncertain samples. Then the diversity criterion exploits the kernel k-means clustering algorithm to select uncorrelated informative samples among the selected uncertain samples. To assess the effectiveness of the proposed method we compared it with other batch mode active learning techniques presented in the literature using one toy data set and three real data sets. Experimental results confirmed that the proposed technique provided a very good tradeoff among robustness to biased initial training samples, classification accuracy, computational complexity, and number of new labeled samples necessary to reach the convergence.     

基于多类SVM和D—S证据理论的决策融合算法研究

D-S证据理论是决策融合领域研究较多的一种有效方法。然而,如何根据实际情况构造D—S证据理论中的基本概率赋值函数是必须面对的一个重要课题。本文提出了一种基于多类支持向量机和D—S证据理论的决策融合算法,将多类支持向量机作为局部判决器,构造了相应的基本概率赋值函数,然后用D—S证据理论对各初步判决结果进行融合,得出对目标的最终识别结论。最后与投票表决法对比,做出仿真,并进行分析,验证了算法的合理性和有效性。     

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.     

基于OCSVM的DDOS攻击实时检测模型

为了提高DDOS攻击检测器的准确率,解决因离线训练分类器而导致的样本标注困难,分类器不能随流量模式变化而更新的问题,提出了一种DDOS攻击的实时检测模型。该模型以One-class SVM做分类器,可减少标注样本的时间。使用主动学习机制,能主动挑选最有利于分类器性能提高的样本进行训练。以拥塞控制理论为基础,通过对分类结果进行主动错误识别和纠正,使学习机可以随流量变化更新其状态。实验结果表明,该模型有较好的分类准确性,通过错误纠正功能可以提高检测率,可用于实时检测DDOS攻击。     

Shared feature extraction for nearest neighbor face recognition.

In this paper, we propose a new supervised linear feature extraction technique for multiclass classification problems that is specially suited to the nearest neighbor classifier (NN). The problem of finding the optimal linear projection matrix is defined as a classification problem and the Adaboost algorithm is used to compute it in an iterative way. This strategy allows the introduction of a multitask learning (MTL) criterion in the method and results in a solution that makes no assumptions about the data distribution and that is specially appropriated to solve the small sample size problem. The performance of the method is illustrated by an application to the face recognition problem. The experiments show that the representation obtained following the multitask approach improves the classic feature extraction algorithms when using the NN classifier, especially when we have a few examples from each class.     

Classification model for product form design using fuzzy support vector machines

Consumer preferences regarding product design are often affected by a large variety of form features. Traditionally, the quality of product form design depended heavily on designers’ intuitions and did not always prove to be successful in the marketplace. In this study, to help product designers develop appealing products in a more effective manner, an approach based on fuzzy support vector machines (fuzzy SVM) is proposed. This constructs a classification model of product form design based on consumer preferences. The one-versus-one (OVO) method is adopted to handle a multiclass problem by breaking it into various two-class problems. Product samples were collected and their form features were systematically examined. To formulate a classification problem, each product sample was assigned a class label and a fuzzy membership that corresponded to this label. The OVO fuzzy SVM model was constructed using collected product samples. The optimal training parameter set for the model was determined by a two-step cross-validation. A case study of mobile phone design is given to demonstrate the effectiveness of the proposed methodology. The performance of fuzzy SVM is also compared with SVM. The results of the experiment show that fuzzy SVM performed better than SVM.     

融合特征选取和学习策略的支持向量机研究

支持向量机是重要的机器学习方法之一,已成功解决了许多实际的分类问题。围绕如何提高支持向量机的分类精度与训练效率,以分类过程为主线,主要综述了在训练支持向量机之前不同的特征选取方法与学习策略。在此基础上,比较了不同的特征选取方法SFS,IWSS,IWSSr以及BARS的分类精度,分析了主动学习策略与支持向量机融合后获得的分类器在测试集上的分类精度与正确率/召回率平衡点两个性能指标。实验结果表明,包装方法与过滤方法相结合的特征选取方法能有效提高支持向量机的分类精度和减少训练样本量;在标签数据较少的情况下,主动学习能达到更好的分类精度,而为了达到相同的分类精度,被动学习需要的样本数量必须要达到主动学习的6倍。