仿射子空间最近点分类算法

为了取得更好的识别效果,受支持向量机的几何解释和最近点问题启发,提出了一种新的模式分类算法——仿射子空间最近点算法。该算法是将支持向量机最近点法的最近点搜索区域由两类训练集凸包推广到两类训练样本各自张成的仿射子空间,并以仿射子空间作为样本分布的粗略估计,通过仿射子空间中的最近点对来构造平分仿射子空间间隔的最优分类超平面。该算法在ORL人脸识别数据库上进行的比较实验中取得了较好的识别效果,从而证实了该方法的可行性和有效性。     

一种新颖的核学习算法用于小波特征的人脸识别

文中将一种新颖的核学习算法一核最近邻凸包分类算法用于人脸的小波特征识别。该算法的设计受到支持向量机几何解释启发，利用核函数方法将数据映射到高维核空间，并在核空间构造以训练集凸包为扩展类集的最近邻分类器。文中采用的人脸图像的小波低频特征对人脸识别十分有效。人脸的小波低频特征不但保留了人脸的主要信息，而且具有较少的维度。在ORL人脸图像库上的“leave-one-out”测试方法的实验中，这种基于小波低频特征的核最近邻凸包分类算法取得了99．25％的识别率。     

基于类间最近邻支持向量信息测度排序的快速分类算法研究

提出了基于特征空间中最近邻类间支持向量信息测度排序的快速支持向量机分类算法,对于训练样本首先进行最近邻类间支持向量信息测度升序排列处理;然后根据排序的结果选择最优的训练样本子空间,在选择的样本子空间内采用乘性规则直接求取Lagrange因子,而不是传统的二次优化方法;最后加入附加剩余样本进行交叉验证处理,直到算法满足收敛性准则。各种分类实验结果表明,该算法具有非常良好的性能,特别是在训练样本庞大,支持向量数量较多的情况下,能够较大幅度地减少计算复杂度,提高分类速度。     

支持向量机分类算法研究

支持向量机在处理两类分类问题时,当两类样本混杂严重时会降低分类精度。在NN-SVM分类算法的基础上,通过计算样本点与其最近邻点类别的异同以及该点与其k个同类近邻点在核空间的平均距离修剪混淆点,进而提出了一种改进的NN-SVM算法——KCNN-SVM。实验数据表明,KCNN-SVM算法与SVM以及NN-SVM相比,有着更高的分类精度和更快的训练、分类时间。     

改进的支持向量机特征选择算法

针对采用支持向量机进行分类的特征子集选择问题,提出一种改进的基于梯度向量的特征评测算法。该算法在核特征空间中,利用数据点到分类超平面的距离函数的梯度向量对各个特征的重要性进行排序,省去了已有算法中计算梯度向量与各个坐标轴夹角的过程,实验结果表明,该算法简化了已有的基于角度的特征选择方法,并且结果保持一致。     

多类分类预选取的SVM在语音识别中的应用

支持向量机在训练过程中,将很多时间都浪费在对非支持向量的复杂计算上,特别是对于大规模数据量的语音识别系统来说,支持向量机在训练时间上不必要的开销将会更加显著。核模糊C均值聚类是一种常用的典型动态聚类算法,并且有核函数能够把模式空间的数据非线性映射到高维特征空间。在核模糊C均值聚类的基础上,结合了多类分类支持向量机中的一对一方法,按照既定的准则把训练样本集中有可能属于支持向量的样本数据进行预选取,并应用到语音识别中。实验取得了较好的结果,该方法有效地提高了支持向量机分类器的学习效率和泛化能力。     

基于几何思想的快速支持向量机算法

为了快速地进行分类,根据几何思想来训练支持向量机,提出了一种快速而简单的支持向量机训练算法——几何快速算法。由于支持向量机的最优分类面只由支持向量决定,因此只要找出两类样本中所有支持向量,那么最优分类面就可以完全确定。该新的算法根据两类样本的几何分布,先从两类样本的最近点开始;然后通过不断地寻找违反KKT条件的样本点来找出支持向量;最后确定最优分类面。为了验证新算法的有效性,分别利用两个公共数据库,对新算法与SMO算法及DIRECTSVM算法进行了实验对比,实验结果显示,新算法的分类精度虽与其他两个方法相当,但新算法的运算速度明显比其他两个算法快。     

一种基于Morlet小波核的约简支持向量机

针对支持向量机（SVM）的训练数据量仅局限于较小样本集的问题,结合Morlet小波核函数,提出了一种基于Morlet小波核的约倚支持向量机（MWRSVM—DC）．算法的核心是通过密度聚类寻找聚类中每个簇的边缘点作为约倚集合,并利用该约倚集合寻找支持向量．实验表明,利用小波核,该算法不仅提高了分类的准确率,而且提高了整体分类效率．     

一种不平衡支持向量机的校正方法

针对支持向量机中两类不平衡数据的分离超平面的偏移问题提出一种校正方法：先对两类样本数据在核空间中进行核主成分分析，分别求出两类样本数据的在特征空间中的主要特征值；然后根据两样本容量以及各自的特征值所提供的信息，对两类数据给出惩罚因子比例；最后通过优化训练产生一个新的分离超平面。该分类面校正了标准支持向量机的分类误差，与标准的支持向量机相比，该方法不仅平衡了错分率，同时还能减少错分率。实验结果验证了方法的有效性。     

基于模糊核聚类的图像SVM分类辨识

提出一种结合特征场和模糊核聚类支持向量机的图像分类辨识方法。首先,构造符合人类视觉特性的图像彩色和纹理特征数据场,一方面,引入新阈值,建立图像纹理特征;另一方面,在图像彩色特征上,对能够引起注意的像素区域的像素点进行加权处理,并使用彩色空间分布离散度来描述彩色的空间分布。其次,采用模糊核聚类支持向量机对图像进行分类研究。在使用特征空间时,不仅考虑了样本与类中心间的关系,还考虑了类中各个样本间的关系,以模糊连接度来度量类中各个样本间的关系,并以二叉树方式构造子分类器。实验结果表明,该方法可以获得较好的图像分类效果。     

基于相似压缩的近似线性SVM

为了解决模式识别中的近似线性可分问题,提出了一种新的近似线性支持向量机(SVM).首先对近似线性分类中的训练集所形成的两类凸壳进行了相似压缩,使压缩后的凸壳线性可分;基于压缩后线性可分的凸壳,再用平分最近点和最大间隔法求出最优的分划超平面.然后再通过求解最大间隔法的对偶问题,得到基于相似压缩的近似线性SVM.最后,从理论和实证分析两个方面,将该方法与线性可分SVM及推广的平分最近点法进行了对比分析,说明了该方法的优越性与合理性.     

改进的基于凸壳仿射不变量的图像识别和配准算法

提出了一种新的基于凸壳和仿射不变量的图像识别和配准的方法。该方法利用从参考图和测试图中得到的特征点提取其凸壳，并计算凸壳的仿射不变特征向量。通过比较参考图和测试图特征向量的一致性，建立它们的仿射变换关系，最后利用凸壳内特征点的匹配来实现识别和配准。该方法的优点是即使目标物体被部分覆盖或者缺损，其图像也能够达到较好的识别和配准效果。     

基于Voronoi图的反向最近邻查询

为了解决反向最近邻查询问题,利用Voronoi图及数据集中点的凸包进行反向最近邻查询,通过判断查询点与凸包的位置关系,可去除大量的数据点,并且给出在数据点被加入或删除后,对查询点的反向最近邻变化情况的判断方法与算法。为了便于查询,设计相应的空间存储数据结构。比较分析表明,该方法在处理多个查询点的反向最近邻时有一定的优势。     

Clipping algorithms for solving the nearest point problem over reduced convex hulls

The nearest point problem (NPP), i.e., finding the closest points between two disjoint convex hulls, has two classical solutions, the Gilbert-Schlesinger-Kozinec (GSK) and Mitchell-Dem’yanov-Malozemov (MDM) algorithms. When the convex hulls do intersect, NPP has to be stated in terms of reduced convex hulls (RCHs), made up of convex pattern combinations whose coefficients are bound by a μ<1 value and that are disjoint for suitable μ. The GSK and MDM methods have recently been extended to solve NPP for RCHs using the particular structure of the extreme points of a RCH. While effective, their reliance on extreme points may make them computationally costly, particularly when applied in a kernel setting. In this work we propose an alternative clipped extension of classical MDM that results in a simpler algorithm with the same classification accuracy than that of the extensions already mentioned, but also with a much faster numerical convergence.     

一种改进的线性SVM

对模式分类中的近似线性可分问题提出了一种新的近似线性支持向量机（SVM）：先对近似线性分类中的训练集所形成的两类凸壳进行了相似变形,使变形后的凸壳线性可分,再用平分最近点和最大间隔法求出理想的分划超平面,然后再通过求解最大间隔法的对偶问题得到基于相似压缩的近似线性SVM。此外,还从理论和实证分析两个方面将该方法与线性可分SVM及已有的近似线性可分SVM进行了对比分析,说明了该方法的优越性与合理性。     

基于样本选择的最近邻凸包分类器

最近邻凸包分类算法是一种以测试点到各类别样本凸包的距离为分类度量的最近邻分类算法。然而,该算法的凸二次规划问题优化求解的较高的计算复杂度限制了其在较大规模数据集上的应用。本文提出一种样本选择方法——子类凸包生长法。通过迭代,选择距离选出样本凸包最远的点,直到满足终止条件,从而实现数据集的有效约简。ORL数据库和MIT-CBCL人脸识别training-synthetic库上的实验结果表明,子类凸包生长法选出的少量样本生成的凸包能够很好的表征训练集,在不降低最近邻凸包分类器性能的同时,使得算法的计算速度大为提高。     

Incremental algorithms for collision detection between polygonalmodels

Fast and accurate collision detection between general polygonal models is a fundamental problem in physically based and geometric modeling, robotics, animation, and computer-simulated environments. Most earlier collision detection algorithms are either restricted to a class of models (such as convex polytopes) or are not fast enough for practical applications. The authors present an incremental algorithm for collision detection between general polygonal models in dynamic environments. The algorithm combines a hierarchical representation with incremental computation to rapidly detect collisions. It makes use of coherence between successive instances to efficiently determine the number of object features interacting. For each pair of objects, it tracks the closest features between them on their respective convex hulls. It detects the objects' penetration using pseudo internal Voronoi cells and constructs the penetration region, thus identifying the regions of contact on the convex hulls. The features associated with these regions are represented in a precomputed hierarchy. The algorithm uses a coherence based approach to quickly traverse the precomputed hierarchy and check for possible collisions between the features. They highlight its performance on different applications     

Convex sets as prototypes for classifying patterns

We propose a general framework for nonparametric classification of multi-dimensional numerical patterns. Given training points for each class, it builds a set cover with convex sets each of which contains some training points of the class but no points of the other classes. Each convex set has thus an associated class label, and classification of a query point is made to the class of the convex set such that the projection of the query point onto its boundary is minimal. In this sense, the convex sets of a class are regarded as “prototypes” for that class. We then apply this framework to two special types of convex sets, minimum enclosing balls and convex hulls, giving algorithms for constructing a set cover with them and for computing the projection length onto their boundaries. For convex hulls, we also give a method for implicitly evaluating whether a point is contained in a convex hull, which can avoid computational difficulty for explicit construction of convex hulls in high-dimensional space.