求解MEB问题的一种SMO-型方法

目的求解n维空间中m个点的最小闭包球(MEB)问题。方法基于序列最小优化(SMO)的方法,提出了一种近似算法,求解MEB问题的一个(1+ε)-近似。结果建立了此算法的计算复杂度为O(mn/ε),并且算法最终得到一个独立于m,n的大小为O(1/ε)的核心集。结论数值结果表明对于求解高精度的大规模问题,算法是很有效的。

基于二阶远离步的积极集最小闭包球算法

对高维大规模数据集的近似最小闭包球(Minimum Enclosing Ball,MEB)问题进行研究,提出一种基于二阶远离步的积极集最小闭包球算法。首先,基于对偶目标函数的二阶泰勒展开选择远离步指标,给出求解MEB问题的二阶远离步算法,并计算算法的多项式时间复杂度。然后,进一步设计一个改进的积极集算法计算高维大规模数据集的近似MEB,算法每次迭代选取距离球心较远的数据点构造积极集,并调用二阶远离步算法求解。数值实验结果表明,所提算法能够快速有效地处理高维大规模数据集的高精度近似MEB问题。

求解加权最小包容球问题的两种算法

研究在高维空间中的加权最小包容球问题,该问题是非光滑的凸优化问题.提出光滑逼近和非精确牛顿共轭梯度算法求解该问题,并证明其收敛性.此外,给出数值实验,比较这2种算法和经典牛顿共轭梯度算法的计算效率,其中非精确牛顿共轭梯度算法的计算效率更高.

适合大样本快速训练的最大夹角间隔核心集向量机

许多核化形式的分类方法如SVM,SVDD等都是对应一个二次规划(QP)问题,而核矩阵计算需要O(m2)空间复杂度,求解QP需要O(m3)时间复杂度,限制了这类方法对大样本数据的训练.本文基于一种新的分类间隔概念提出最大向量夹角间隔分类器MAMC,目标是在样本空间找到最优向量c,测试样本通过c与训练样本之间的最大化向量夹角间隔ρ(称为Margin)实现分类.同时,文中证明了该方法的核化形式等价于核化的最小包络球MEB问题,并通过引入核心集向量机CVM将MAMC扩展为MAM-CVM,进而快速实现对大样本的训练和分类.人造和真实数据集实验表明了MAMC和MAM-CVM算法的有效性.

隐私保护的SVM快速分类方法

许多核分类方法的决策函数可以表示为支持向量的组合,如SVM,而支持向量含有非常重要的隐私信息,因此,在分类决策时可能会暴露此类信息,同时分类速度受限于支持向量的个数,如SVM的分类复杂度为O(|SVs|).为解决上述两个问题,本文基于最小包含球球心在原始空间中的代理原像,提出了一种隐藏支持向量信息并能快速实现分类的SVM方法,称为隐私保护的快速SVM分类方法(Fast Classification Approach of SVM with Privacy Preservation,FCA-SVMWPP).同时提供了两种求解代理球心原像的方法,分别称为QP解法和直接解法.UCI和PIE人脸数据集的实验结果表明,本文方法可解决上述两个问题并具有较好的效果.

基于工业机器人的三维扫描技术研究

在被测曲面表面形貌和轮廓未知的情况下,由于存在无法准确布置采样点、视点偏移等问题,三维扫描过程中会出现缺失区域,严重影响表面完整性和扫描质量。因此,提出了一种工业机器人+三维扫描仪的解决方案,以工业机器人为运动平台,搭载三维扫描仪对曲面进行扫描操作。在获取快速扫描点云数据后,通过弦长离散法判断缺失区域并确定边界点,然后运用最小包容球对缺失区域进行包容计算,预估扫描缺失区域的范围和无效扫描区域的法线方向,并采用圆周等分法重新布置采样点,规划扫描路径,最后转化为工业机器人精扫描运动轨迹,补全缺失区域。

大样本领域自适应支撑向量回归机

针对回归问题中存在采集数据不完整而导致预测性能降低的情况,根据支撑向量回归机(support vector regression,简称SVR)等价于中心约束最小包含球(center-constrained minimum enclosing ball,简称CC-MEB)以及相似领域概率分布差异只与两域各自的最小包含球中心点位置有关的理论新结果,提出了针对大数据集的领域自适应核心集支撑向量回归机(adaptive-core vector regression,简称A-CVR).该算法利用源域CC-MEB中心点对目标域CC-MEB中心点进行校正,从而提高目标域的回归预测性能.实验结果表明,这种领域自适应算法可以弥补目标域缺失数据的不足,大大提高回归预测性能.

采用改进最小闭包球向量机的电力信息网络入侵检测方法

为降低电力信息网络入侵检测的检测误差和检测耗时,提出一种基于改进最小闭包球向量机(minimum enclosing ball vector machine,MEBVM)的入侵检测方法。该方法将入侵检测抽象成多分类问题,通过改进MEBVM对历史数据样本的训练学习来得到入侵检测模型。改进MEBVM利用最小闭包球降低检测耗时,并在训练过程中利用粒子群优化算法动态搜索MEBVM的最优训练参数以降低入侵检测模型误差。最后基于电力信息网络现场数据的实验证明,该方法与传统方法相比具有更高的检测精度和更少的检测耗时。

分类大规模数据的核向量机方法研究

标准的支持向量机算法需要求解二次规划问题,因此,在处理大规模样本的时候,求解二次规划问题的时间复杂度和空间复杂度就成为支持向量机应用的一个瓶颈.核向量机将传统支持向量机中的二次规划问题转化为求解最小包围球问题,从而显著降低了二次规划的复杂程度.使用核向量机对大规模数据进行分类,所选用的数据样本数均超过2000,并与标准的支持向量机作了对比实验结果表明:核向量机在处理大规模数据分类时,比标准的支持向量机计算复杂度低,训练速度快,耗费空间少.

一种新颖的QAR数据特征提取方法

针对快速存储器(QAR)数据特征提取问题,首先给出适用于一类分类的最大间隔判别分析方法,并通过增加正交约束,给出适用于一类分类的最大间隔特征提取算法;在此基础上,针对QAR数据大样本的特性,给出正交约束的一类分类问题的最大间隔判别分析问题的修改形式,并将该修改形式转化为闭包球问题,进而给出了基于正交约束闭包球的最大间隔QAR数据特征提取方法,通过实验表明该方法对某一机型的飞行纪录数据取得了良好的实验结果,有效解决了QAR数据大样本特征提取的问题。

一般化最小包含球的大样本快速学习方法

标准最小包含球(Minimum enclosing ball,MEB)模型的对偶问题可视为MEB问题并能够利用核心集向量机(Core vector machine,CVM)实现大样本的快速训练,但对于一般化MEB模型,对偶问题中的不等式约束发生了变化而不能视为MEB问题,不能方便地使用CVM来解决大样本的快速训练.为此,提出了一般化MEB快速学习方法(Fast learning of generalized MEB,FL-GMEB),首先放松对偶问题中的不等式约束条件,使其等价于中心约束的MEB问题,从而利用CVM获得其核心集(Coreset,CS);然后利用局部线性嵌入(Locally linear embedding,LLE)的逆思想将CS扩充为拓展核心集(Extended core set,ECS);最后将ECS及其对应的优化权作为一般化MEB模型的逼近解.UCI和USPS数据集上的实验结果表明,FL-GMEB在大样本快速训练方面具有较好的性能优势.

基于支持向量数据描述的高效异常数据检测算法

为了解决大规模数据中的异常检测问题,提出了基于支持向量数据描述(SVDD)的高效离群数据检测算法。该算法的核心思想为:首先利用SVDD获得包含单类数据的最小球形边界,然后通过该边界对未知样本数据进行分类,并利用最小闭包球算法对SVDD分类器进行优化求解。在UCI机器学习数据集和入侵检测数据集上将该算法与其他离群数据检测算法进行了实验比较,结果表明,该算法不仅获得了更高的检测准确率,而且具有较低的运行时间。

一种用于中文主题分类的CSVM算法

提出一种新的级联支持向量机分类算法CSVM,结合AdaBoost算法框架与支持向量机(SVM)进行多分类处理。针对多分类问题中支持向量机处理样本数量多和计算时间过长的问题,引入最小闭合球算法对原始样本数据进行提取,以缩短SVM的训练时间。实验结果表明,CSVM算法具有与AdaBoost-SVM算法相似的精确度,而计算时间仅为AdaBoost-SVM算法的35%。

基于中心加权的局部核向量机算法

为了解决大规模非线性分类中局部学习的不平衡性问题,提出一种改进的局部支持向量机算法,在高维特征空间中聚类后,为每一个簇构造局部非线性支持向量机。为了克服簇内样本的分布不均衡问题,根据闭合超平面不规则边界的几何特点,经过梯度下降寻找稳定均衡向量,以此构造簇几何中心;再结合簇密度中心共同约束类心形成双重加权中心。然后通过求解加权最小闭球问题实现对大规模样本向量的分类。对照实验显示,除了个别数据集以外,改进的算法在训练时间、测试时间以及测试精度等方面都比另外两种分类算法表现更佳。

基于球向量机的图像分割

由于图像数据量庞大,将标准支持向量机应用于图像分割时,其训练的时间复杂度较高。通过使用球向量机对图像进行分割,以降低训练过程消耗的时间。实验表明,在无噪声和有噪声情况下,使用球向量机对图像进行分割,其分割效果和抗噪性能与标准支持向量机的分割效果基本相同。然而,球向量机在训练过程中所消耗的时间显著小于标准支持向量机。应用球向量机进行图像分割,可以显著提高图像分割的整体性能。

基于积极集策略的最小闭包球问题算法研究

首先,基于每次迭代计算距离当前球心最远的两个点,提出一种求解n维空间中m个点的最小闭包球问题的(1+ε)-近似算法。对于ε∈(0,1),建立了该算法的核心集大小和计算复杂度,分别为O(1/ε)和O(mn/ε)。然后,给出一种积极集策略,每次迭代计算距离当前球心最远的N个点。将该策略结合到提出的算法中,得到一个基于积极集策略的算法。最后,实验结果表明基于积极集策略的算法能够快速、有效地求解m>>n的大规模数据集的近似最小闭包球。

一种新的最大间隔分类器的求解算法及其在测井岩性识别中的应用

首先介绍了尺度不变凸壳的概念,提出当2个凸壳独立时,可以通过求解2个凸壳的最大间隔来建立一种新的分类器。然后通过论证尺度不变凸壳与最小闭球的关系,提出了利用最小闭球求解分类器的快速算法。通过对测井岩性识别的试验表明,与已有的方法相比,在取得相同分类成功率的同时,该算法的核估计次数和训练时间明显减少。

基于核向量机的模式分类及其实验测试

文中使用一种新的SVM变种——核向量机来对大样本数据集进行训练建模,进而求解模式分类问题.CVM算法是将核函数转换为最小包围球问题进行求解,可以解决任何线性或非线性分类问题.测试结果表明,核向量机可以快速对大样本数据进行分类并能产生较少的支持向量.

一种新颖的领域自适应概率密度估计器

传统概率密度估计法建立好密度估计模型后,无法将源域知识传递给相关目标域密度估计模型。提出用无偏置v-SVR的回归函数来表示传统概率密度估计法获得密度估计信息,并说明无偏置v-SVR等价于中心约束最小包含球及概率密度回归函数可由中心约束最小包含球中心点表示。在上述理论基础上提出中心点知识传递领域自适应概率密度估计法,用于解决因目标域信息不足而无法建立概率密度函数的场景。实验表明,此种领域自适应方法进行领域间知识传递的同时,还能达到源域隐私保护的目的。

求解最小闭包球问题改进的SMO-型算法

研究n维空间中m个点的最小闭包球(MEB)问题。通过结合确定并删除内部点的技术到序列最小最优化(SMO)方法中,提出一种近似求解MEB问题的改进的SMO-型算法。证明了该算法具有线性收敛性。数值结果表明对于一些mn的大规模数据集,改进的算法与原算法相比速度可以提高10倍以上。尤其,当n等于100且m等于100000时,改进的SMO-型算法仅需执行8s。此外,对于n等于10000且m等于1000的大规模数据集,改进的算法也仅需执行150s。