多类支持向量机算法综述

传统的支持向量机是基于两类问题提出的,如何将其有效的推广至多类问题仍是一个有待研究的问题。本文中作者致力于对现有的几种较有成效的多类支持向量机做一介绍,并比较其优劣,以期对研究者以后的研究能有所启发。     

交互迭代一对一分类算法

在基于支持向量机的多分类算法中,一对一算法表现出较好的性能.然而此算法却存在不可分区域,落入该区域的样本不能有效被识别,因此影响了一对一算法的性能.为解决这个难题,提出交互迭代一对一分类算法,同时给出算法的有效性分析和计算复杂度证明.为了验证该算法解决不可分区域的能力,我们选用UCI数据集来做对比实验.实验结果显示,本文算法不但可以较成功解决不可分区域问题而且表现出比其它算法更好的性能.     

视频监控系统中小运动目标分类算法

给出了视频监控中的一个小目标分类算法．首先，利用最大互信息获得一组可靠、独立且具辨认力的目标特征集．然后，用有向无环图的多类支持向量机进行分类．分类器的训练分为两步，首先使用场景无关的特征量训练得到基准分类器；然后再利用与场景相关和无关的特征量，进一步训练分类器，以便提高分类器的精度．实验结果证明该算法不仅能满足一定的分类精度，而且对新场景具有很好的适应能力．     

基于节点选择优化的DAG-SVM多类别分类

有向无环图支持向量机( DAG-SVM)对于N类别分类问题,会构造N ×( N-1)/2个支持向量机分类器(为每2个类构造一个支持向量机),DAG-SVM可能出现由于节点选择不佳而导致整个分类器分类结果较差的情况。为此,提出一种改进的DAG-SVM。通过为每一层建立备选节点集合进行节点选择,选取下层备选节点集合中训练分类精度最高的一个节点组合作为当前层节点的下层节点,从而优化DAG-SVM的拓扑结构。实验结果表明,与已有的DAG-SVM,1-vs-1 SVM,1-vs-a SVM方法相比,该方法的分类精度较高。     

基于改进型人工鱼群算法的支持向量机参数优化

支持向量机在高维度、小样本情况下具有独特优势,但同时支持向量机的参数优化极大制约了其分类效果,目前参数优化缺乏系统的理论指导;针对传统DAG-SVM训练分类器较多,训练耗时长,分类效果受到结构排序的影响,提出了一种基于“1 vs R”策略的改进型算法;针对 SVM传统参数优化方式耗时大,优化精度不高,提出了改进型人工鱼群算法;最后结合1 vs R-DAG支持向量机算法与改进型人工鱼群算法,得到一种新的改进型支持向量机算法;仿真对比实验证实,对支持向量机的参数优化是有效可行的。     

一种改进的DAGSVM 手势识别方法及其应用

在支持向量机多分类方法基础上,提出了一种改进的有向无环图支持向量机( Directed Acyclic Graph Support Vector Machine,DAGSVM) 手势识别方法。首先根据Kinect 采集到 的场景深度信息将前景和背景分开,分割得到手,然后提取其特征向量,利用特征向量训练多 个SVM 两分类器,采用DAG 拓扑结构构成DAGSVM 多分类器,并对其结构排序进行改进。 实验证明,与其他支持向量机多分类方法相比,改进后的DAGSVM 分类器能够达到更高的识 别率,并将这个手势识别方法用于智能轮椅的控制上,收到了良好的效果。     

一种改进的有向无环图支持向量机

构造合理的有向无环图是有向无环图支持向量机亟需解决的一个关键问题。本文提出一种改进的有向无环图支持向量机,根据超球支持向量机获得类的最小包围球,根据该最小包围球计算类与类之间的最短距离,根据该最短距离形成最短距离矩阵,根据该最短距离矩阵来构造有向无环图。实验结果表明,该改进算法较传统有向无环图支持向量机分类精度有明显提高。     

结合归一化中心矩与DAGSVM的机器人交互手势识别

将归一化中心矩和DAGSVM相结合应用于机器人人机交互中的手势识别。归一化中心矩作为手势特征具有平移和比例不变性,同时对方向变化比较敏感,这正是机器人识别不同指向的手势时特征所需具有的特性,然后,将这个手势特征向量输入到DAGSVM分类器进行分类识别。实验结果表明,该方法能够有效地识别手势,且用于控制机器人运动效果良好。     

基于马氏距离的孪生多分类支持向量机

孪生支持向量机(TWSVM)的研究是近来机器学习领域的一个热点。TWSVM具有分类精度高、训练速度快等优点,但训练时没有充分利用样本的统计信息。作为TWSVM的改进算法,基于马氏距离的孪生支持向量机(TMSVM)在分类过程中考虑了各类样本的协方差信息,在许多实际问题中有着很好的应用效果。然而TMSVM的训练速度有待提高,并且仅适用于二分类问题。针对这两个问题,将最小二乘思想引入TMSVM,用等式约束取代TMSVM中的不等式约束,将二次规划问题的求解简化为求解两个线性方程组,得到基于马氏距离的最小二乘孪生支持向量机(LSTMSVM),并结合有向无环图策略(DAG)设计出基于马氏距离的最小二乘孪生多分类支持向量机。为了减少DAG结构的误差累积,构造了基于马氏距离的类间可分性度量。人工数据集和UCI数据集上的实验均表明,所提算法不仅有效,而且相对于传统多分类SVM,其分类性能有明显提高。     

基于最优DAGSVM的服务机器人交互手势识别父且手亍劣识别

针对目前服务机器人手势交互方法在输入方式自然性和识别方法可靠性方面的不足,提出采用结合人脸和人手的姿态作为输入方式,实现了一个基于最优有向无环图支持向量机（DAGSVM）的手势识别系统。系统采用分步细化特征检测过程,即先粗检肤色,然后分别利用人眼Gabor特征和人手边缘小波矩特征检测脸和手部,可克服背景中的肤色干扰,并显著提高特征提取的可靠性;综合利用脸手区域不变矩和手的位置信息组成混合特征向量,采用优化拓扑排序策略组织多个两分类支持向量机（SVM）,构成最优DAGSVM多分类器,达到比普通DAGSVM更高的多分类准确率。实验验证了该方法的有效性和可靠性,并用于实现一种自然友好的人机交互方式。     

Hybrid similarity measure for case retrieval in CBR and its application to emergency response towards gas explosion

Case retrieval is a primary step in case-based reasoning (CBR). It is important to measure the similarity between each historical case and the target case during the case retrieval process. In recent years, some methods for similarity measure with multiple formats of attribute values can be found in the practical CBR applications, but the in-depth study is still lacking. The objective of this paper is to develop a new method for hybrid similarity measure with five formats of attribute values: crisp symbols, crisp numbers, interval numbers, fuzzy linguistic variables and random variables. First, for each format of the attribute values, the calculation formula to measure the attribute similarity is presented. Then, the method for measuring hybrid similarity between each historical case and the target case is given by aggregating attribute similarities using the simple additive weighting method, and the proper historical case(s) can be retrieved according to the obtained hybrid similarities afterwards. Finally, a case study in the field of emergency response towards gas explosion is introduced to illustrate the use of the proposed method.     

A case-based reasoning system development for statistical process control: Case representation and retrieval

Statistical process control (SPC) is a sub-area of statistical quality control. Considering the successful results of the SPC applications in various manufacturing and service industries, this field has attracted a large number of experts. Despite the development of knowledge in this field, it is hard to find a comprehensive perspective or model covering such a broad area and most studies related to SPC have focused only on a limited part of this knowledge area. According to many implemented cases in statistical process control, case-based reasoning (CBR) systems have been used in this study for developing of a knowledge-based system (KBS) for SPC to organize this knowledge area. Case representation and retrieval play an important role to implement a CBR system. Thus, a format for representing cases of SPC and the similarity measures for case retrieval are proposed in this paper.     

基于贝叶斯方法的范例检索

提出了利用贝叶斯概率理论进行范例推理,因为在范例库中进行范例检索是范例推理中的一个非常重要的组成部分。该文中主要考虑的是如何利用贝叶斯方法进行范例检索并提出了一个评估两个范例相似程度的匹配函数。在传统的方法中,可以用欧氏距离等方法来评估两个范例的相似性。在实验中,把这两种方法进行了比较,实验结果表明贝叶斯方法不仅呵行,而且比用欧氏距离方法更优。     

Active learning for image retrieval with Co-SVM

In relevance feedback algorithms, selective sampling is often used to reduce the cost of labeling and explore the unlabeled data. In this paper, we proposed an active learning algorithm, Co-SVM, to improve the performance of selective sampling in image retrieval. In Co-SVM algorithm, color and texture are naturally considered as sufficient and uncorrelated views of an image. SVM classifiers are learned in color and texture feature subspaces, respectively. Then the two classifiers are used to classify the unlabeled data. These unlabeled samples which are differently classified by the two classifiers are chose to label. The experimental results show that the proposed algorithm is beneficial to image retrieval.     

An algorithm for semi-supervised learning in image retrieval

We study the problem of image retrieval based on semi-supervised learning. Semi-supervised learning has attracted a lot of attention in recent years. Different from traditional supervised learning. Semi-supervised learning makes use of both labeled and unlabeled data. In image retrieval, collecting labeled examples costs human efforts, while vast amounts of unlabeled data are often readily available and offer some additional information. In this paper, based on support vector machine (SVM), we introduce a semi-supervised learning method for image retrieval. The basic consideration of the method is that, if two data points are close to each, they should share the same label. Therefore, it is reasonable to search a projection with maximal margin and locality preserving property. We compare our method to standard SVM and transductive SVM. Experimental results show efficiency and effectiveness of our method.     

基于归纳技术的范例推理及其应用

首先研究了可以与范例推理相结合的多种技术，并着重研究了基于范例推理和归纳技术的集成方法，以充分利用范例推理和归纳技术的各自优势，提高求解问题的能力。该文提出了一个基于归纳技术的范例推理分类算法，实验证明了此算法有着良好的分类准确率。     

A self-stabilizing algorithm for coloring planar graphs

Summary This paper describes an algorithm for coloring the nodes of a planar graph with no more than six colors using a self-stabilizing approach. The first part illustrates the coloring algorithm on a directed acyclic version of the given planar graph. The second part describes a selfstabilizing algorithm for generating the directed acyclic version of the planar graph, and combines the two algorithms into one. Sukumar Ghosh received his Ph.D. degree in Computer Science from Calcutta University in 1971. From 1969 to 1984, he taught at Jadavpur University, Calcutta. During 1976–77, he was a Fellow of the Alexander von Humboldt Foundation at the University of Dortmund, Germany. Since 1984, he is with the Department of Computer Science of the University of Iowa. His current research interests are in the areas of Distributed Systems, Petri Nets and Self-Stabilizating Systems. Mehmet Hakan Karaata received the Sc. B. degree in Computer Science and Engineering from Hacettepe University in Turkey in 1987, and the M.S. degree in Computer Science from the University of Iowa in 1990. He is currently studying towards his Ph.D. at the same university. His research interests are in the areas of Distributed Systems, Self-Stabilizing Systems and Database Systems.This research was supported in part by the National Science Foundation under grant CCR-9109078, and the Old Gold Summer Fellowship of the University of Iowa. An abstract of this paper was presented at the 29th Allerton Conference on Control, Communication & Computing in October 1991.     

A practical algorithm for evaluating database queries

This paper describes an algorithm for evaluating database queries represented as expressions in a logical language. Such a database query expression can be evaluated efficiently by focusing on the variable dependencies. The algorithm recursively computes the values of subexpressions to evaluate the input expression, but it avoids re-evaluation of those subexpressions whose values are not affected by new variable assignments. The input expression is internally structured as a directed acyclic graph. Two additional techniques to improve efficiency of the evaluation are discussed: transformations of the input expression and special primitive database operations. Finally, its implementation in the natural language question-answering system SPICOS is described.     

Integrating a semantic-based retrieval agent into case-based reasoning systems: A case study of an online bookstore

Natural language search engines should be developed to provide a friendly environment for business-to-consumer e-commerce that reduce the fatigue customers experience and help them decide what to buy. To support product information retrieval and reuse, this paper presents a novel framework for a case-based reasoning system that includes a collaborative filtering mechanism and a semantic-based case retrieval agent. Furthermore, the case retrieval agent integrates short-text semantic similarity (STSS) and recognizing textual entailment (RTE). The proposed approach was evaluated using competitive methods in the performance of STSS and RTE, and according to the results, the proposed approach outperforms most previously described approaches. Finally, the effectiveness of the proposed approach was investigated using a case study of an online bookstore, and according to the results of case study, the proposed approach outperforms a compared system using string similarity and an existing e-commerce system, Amazon.     

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

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