核子空间样本选择方法的核最近邻凸包分类器

为了保证核最近邻凸包分类器有效地处理大训练集的应用问题,提出一种核子空间样本选择方法与该分类器相结合。核子空间样本选择方法是一个类内迭代算法,该算法在核空间里每次迭代选择一个距离选择集样本张成子空间最远的样本。在MIT-CBCL人脸识别数据库的training-synthetic子库上的实验中,该方法不但可以取得100%的识别率,而且与未经选样的核最近邻凸包分类器相比,其执行速度要快许多。     

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

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

基于子空间样本选择的最近凸包分类器

最近邻凸包分类器需要求解测试样本到训练集凸包距离的凸二次规划问题,对于训练集规模较大的情况,有必要在分类之前进行适当的样本选择。为此该文提出基于子空间样本选择的最近凸包分类方法。该方法首先采用子空间样本选择算法对训练集样本进行筛选,然后将各类选出的样本作为最近邻分类器的新的训练集。子空间样本选择方法的原理是在一类训练样本集内,迭代选择距离已选样本张成子空间最远的样本。在MIT-CBCL人脸识别数据库的training-synthetic子库的实验中,该方法只需5.6%的训练样本即可取得100%的识别率,并且执行时间较未经选样的最近邻凸包分类器也大为减少。     

核最近邻凸包分类算法

为了增强最近邻凸包分类器的非线性分类能力,提出了基于核函数方法的最近邻凸包分类算法。该算法首先利用核函数方法将输入空间映射到高维特征空间,然后在高维特征空间采用最近邻凸包分类器对样本进行分类。最近邻凸包分类器是一类以测试点到各类别凸包的距离为相似性度量,并按最近邻原则归类的分类算法。人脸识别实验结果证实,这种核函数方法与最近邻凸包分类算法的融合是可行的和有效的。     

核子类凸包样本选择方法及其SVM应用

提出一种基于核函数方法的类内训练样本选择方法——核子类凸包样本选择法,并将其用于支持向量机。该样本选择方法通过迭代方法,逐一选择了那些经映射后“距离已选样本”,并将其映射、生成“凸包最远的样本”。实验结果表明,该方法选择的少量样本使支持向量机获得了较高的识别比率,减少了存储需求,提高了分类速度。     

Fisher鉴别特征的最近邻凸包分类

基于Fisher准则的特征提取方法是模式识别技术的重要分支,其中,Foley-Sammon变换和具有统计不相关性的最佳鉴别变换是这一技术典型代表,本文将它们与一种新型分类器一最近邻凸包分类器相结合,从而实现Fisher鉴别特征的有效分类。最近邻凸包分类器是一类以测试样本点到各类训练集生成类别凸包的距离为分类判别依据的模式分类新方法,具有非线性性,无参性,多类别适用性等特点。实验证实了本文方法的有效性。     

基于小波和最近邻凸包分类器的人脸识别

本文提出一种新型的人脸识别方法.该方法首先通过二维小波变换提取人脸图像的低频特征,然后采用最近邻凸包分类器对该特征进行分类.二维小波变换是提取图像特征的有效方法之一,在保留原始图像的主要特征的同时,还能够有效降低图像维数;最近邻凸包分类器是一种以测试样本点到各类别训练样本凸包的距离作为相似性度量的分类算法.本文将这两项技术相结合在ORL人脸识别数据库上取得了良好的实验效果.     

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

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

基于随机投影的快速凸包分类器

传统的基于核函数的分类方法中核矩阵运算复杂度较高,无法满足大规模数据分类的要求.针对这一问题,提出基于随机投影的快速凸包分类器(FCHC-RP).首先,使用随机投影的方法将样本投影到多个二维子空间,并将子空间数据映射到特征空间;其次,根据数据分布的几何特征得到凸包候选集;再次,基于凸包的定义计算出特征空间中的凸包向量;最后,使用与凸包向量对应的原始样本及其权值训练支持向量机.此外,FCHC-RP还适用于不平衡数据的分类问题,根据两类样本的不平衡程度选择不同的参数,可以得到规模相当的两类样本的凸包集,实现训练数据的类别平衡.理论分析和实验结果验证了FCHC-RP在分类性能和训练时间上的优势.     

l1范数最近邻凸包分类器在人脸识别中的应用

l1范数作为重要的距离测度,在模式识别中有着较为广泛的应用。在不同的范数定义下,相同分类机理的分类算法一般会有不同的分类效果。本文提出l1范数下的最近邻凸包人脸识别算法。该算法将最近邻凸包分类算法的范数定义由l2范数推广到l1范数,以测试点到各训练类凸包的l2范数距离作为最近邻分类的相似性度量。在ORL标准人脸数据库上的验证实验中,该方法取得了良好的识别效果。     

Convex Decomposition Based Cluster Labeling Method for Support Vector Clustering

Support vector clustering (SVC) is an important boundary-based clustering algorithm in multiple applications for its capability of handling arbitrary cluster shapes.However,SVC’s popularity is degraded by its highly intensive time complexity and poor label performance.To overcome such problems,we present a novel efficient and robust convex decomposition based cluster labeling (CDCL) method based on the topological property of dataset.The CDCL decomposes the implicit cluster into convex hulls and each one is comprised by a subset of support vectors (SVs).According to a robust algorithm applied in the nearest neighboring convex hulls,the adjacency matrix of convex hulls is built up for finding the connected components;and the remaining data points would be assigned the label of the nearest convex hull appropriately.The approach’s validation is guaranteed by geometric proofs.Time complexity analysis and comparative experiments suggest that CDCL improves both the efficiency and clustering quality significantly.     

基于栅格划分构建平面点集凸壳的算法研究

提出了一个构建平面点集凸壳的新算法。该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳。由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率。在最坏情况下该算法的时间复杂度为O(NlogN)。     

Experiments in the Parallel Computation of 3D Convex Hulls

Two parallel implementations of a 3D convex hull algorithm are reported. The paper considers a MIMD distributed memory architecture and the implementations are carried out on the Meiko Computing Surface using T800 transputers and the programming languages Occam and C. The first method uses a simple parallel geometric decomposition strategy and produces encouraging results. With the second approach a parallel generic Divide-and-Conquer kernel is incorporated. This is an example of the algorithmic skeleton approach to parallel programming and involves run-time, dynamic allocation of work to processors. The resulting performances for both methods are measured and compared.     

A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON

ＡＮＥＷＣＯＮＶＥＸＨＵＬＬＡＬＧＯＲＩＴＨＭＦＯＲＡＮＹＰＯＬＹＧＯＮＨｕＺｈａｎｑｉＬｉＹｕｐｅｎｇＷａｎｇＪｕｎＱｉａｏＬｅｉＡｂｓｔｒａｃｔＡｎｅｗａｌｇｏｒｉｔｈｍｆｏｒｆｉｎｄｉｎｇｃｏｎｖｅｘｈｕｌｏｆａｐｏｌｙｇｏｎｉｓｐｒｏｐｏｓｅ...