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

返回 相似
基于随机投影的快速凸包分类器_第1页
第1页 / 共8页
基于随机投影的快速凸包分类器_第2页
第2页 / 共8页
基于随机投影的快速凸包分类器_第3页
第3页 / 共8页
基于随机投影的快速凸包分类器_第4页
第4页 / 共8页
基于随机投影的快速凸包分类器_第5页
第5页 / 共8页
点击查看更多>>
资源描述:
第35卷第5期控制与决策Vol.35 No.5 2020年5月Control and Decision May 2020 文章编号 1001-0920202005-1151-08 DOI 10.13195/j.kzyjc.2018.1266 基于随机投影的快速凸包分类器 顾晓清,张聪,倪彤光y 常州大学信息科学与工程学院,江苏常州213164 摘要传统的基于核函数的分类方法中核矩阵运算复杂度较高,无法满足大规模数据分类的要求.针对这一问 题,提出基于随机投影的快速凸包分类器FCHC-RP.首先,使用随机投影的方法将样本投影到多个二维子空间, 并将子空间数据映射到特征空间;其次,根据数据分布的几何特征得到凸包候选集;再次,基于凸包的定义计算出 特征空间中的凸包向量;最后,使用与凸包向量对应的原始样本及其权值训练支持向量机.此外,FCHC-RP还适用 于不平衡数据的分类问题,根据两类样本的不平衡程度选择不同的参数,可以得到规模相当的两类样本的凸包集, 实现训练数据的类别平衡.理论分析和实验结果验证了FCHC-RP在分类性能和训练时间上的优势. 关键词大规模数据;凸包;随机投影;核方法;分类;快速 中图分类号 TP273文献标志码 A Fast convex hull classifier based on random projection GU Xiao-qing, ZHANG Cong, NI Tong-guangy School of Ination Science and Technology,Changzhou University,Changzhou 213164,China Abstract Due to the high computational complexity of kernel matrixes, traditional kernel-based s can not satisfy the requirement of large-scale data classification. To solve this problem, a fast convex hull classifier based on random projectionFCHC-RP is proposed. In the FCHC-RP, the samples in the original space are projected into several two-dimensional subspaces, and then the data in subspaces are mapped into the kernel space. Then, the convex hull candidate set is computed according to the geometric characteristics of data distribution in the kernel space. Based on the definition of the convex hull, the convex hull vectors in the kernel space are computed. Finally, the support vector machine is trained by the convex hull vectors and their weights. In addition, the FCHC-RP is also suitable for imbalanced classification problems. The FCHC-RP adopts classifier parameters according to the degree of class imbalance between two classes, so that the size of convex hull sets belonging to two class samples is similar. Thus, the training data in two classes are comparative. Theoretical analysis and experimental results verify the advantages of the FCHC-RP in classification perance and training time. Keywords large-scale data;convex hull;random projection;kernel ;classification;fast 0引null 基于核函数的方法在机器学习和模式识别领域 取得了广泛应用,如文本识别、图像处理、基因数据识 别、人脸识别以及语音识别等领域[1-5].基于核函数 方法的主要思想是将数据通过特征映射非线性变 换转换到希尔伯特空间特征空间,使得原空间的 线性不可分的问题转变成特征空间的线性可分的问 题,这些方法具有较好的分类性能.但是,核矩阵的存 储和计算使得基于核函数分类方法的时间复杂度至 少为ON2[6],其中N是训练集样本数.显然,随着数 据量的增加,训练时间也会大量增加,因此,这些分类 方法不适合大规模数据的分类问题. 以支持向量机support vector machine,SVM[7-8] 为代表的核分类方法在构建分类面时旨在寻找不 同类别样本的最优分类超平面,使得其两侧的样本 点到分类面的最小距离最大化.目前,越来越多的研 究者从考虑样本分布的几何结构入手,筛选出能影 响分类面的核心样本以减少训练集的规模,提高分 类器的训练效率.如核心集向量机generalized core vector machines,GCVM及其变种[9-10]寻找一个最 小体积超球,使得数据最大可能或全部包含在内;快 速核密度估计fast density estimator,FastKDE[11]从 收稿日期 2018-09-16;修回日期 2018-11-27. 基金项目国家自然科学基金项目61806026,61572085;江苏省自然科学基金项目BK20160187,BK20180956;江 苏省教育科学“十三五”规划2018年度课题项目B-a/2018/01/41. y通讯作者. E-mail hbxtntg-12. 1152控制与决策第35卷 理论上建立了核密度估计与二次规划问题间的联 系,并使用简单采样的方法建立训练集.但GCVM和 FastKDE只适用于平方型hinge损失函数的SVM.随 机逼近凸包randomized approximation convex hull,ApproxHull[12]使用遗传算法求得样本集在线 性空间的凸包集并用于分类问题,但该方法无法扩 展至特征空间.快速凸包方法fast convex-hull vector machine,CHVM[13]使用高斯核和可加性核得到特 征空间的凸包集并应用于大规模ncRNA数据的分 类,但实际应用时需将数据作降维处理.凸包顶点选 择convex hull vertices selection,CHVS[14]通过计算 样本与线性子空间的距离选择凸包,但该方法的时间 复杂度与样本维数的4次方成正比,随着样本维数的 增加,CHVM的时间复杂度会急剧增加. 任意点集的凸包是指能包含点集中所有样本的 最小凸多边形.因此,SVM最优分类面可等价为寻找 最接近两类样本凸包且具有最大距离的超平面.基 于这一思想,本文提出一种基于随机投影的快速凸 包分类器fast convex hull classifier based on random projection,FCHC-RP.首先,FCHC-RP通过随机投影 策略将样本投影到多个二维子空间,并将二维子空间 数据映射至特征空间;其次,FCHC-RP在特征空间求 得凸包候选集;再次,在凸包候选集的基础上进一步 得到凸包集;最后,FCHC-RP将凸包向量还原至原始 样本,连同其权值一起用于分类器的训练. FCHC-RP 能有效减少训练集的规模,能够处理大规模数据的分 类问题.另外,现实中的数据还常常面临数据不平衡 的问题.对此,本文在不同类别的样本中调整算法参 数,得到规模相当的凸包集,将FCHC-RP拓展至不平 衡数据的分类问题. FCHC-RP的优势在于,能充分利 用样本的几何结构,分类效果几乎不受训练样本减少 的影响,同时分类器的训练时间有效减少. 1相关工作 1.1凸包 定义1凸包[15]设X Rd,X fx1;x2;; xNg由N个点组成,样本集X的凸包为 CHX { ∑ xi2X ixi N∑ i1 i 1; 0 ⩽ i ⩽ 1 } 1 样本集X的凸包是指能包含X中所有点的最 小凸集.式1给出了线性空间中凸包的定义,如果 使用特征映射ϕ x ϕx将样本x映射到特征 空间,特征空间中X的映像表示为ϕX fϕx1; ϕx2;;ϕxNg,则样本集X在特征空间中的凸包 可定义为 KerCHX { ∑ xi2X iϕxi k∑ i1 i 1; 0 ⩽ i ⩽ 1 } 2 1.2随机投影 随机投影randomprojections,RP[16]使用随机矩 阵R将向量投影到一个低维空间,随机矩阵独立于 训练数据,无需按照某种准则通过训练数据产生,能 够快速有效地解决高维数据的降维问题.定义Rd Rp是随机投影映射,对于给定的数据集X,使用随机 矩阵R将d维向量投影到一个p维空间p ≪ d,得到 低维向量集fz1;z2;;zNg,其中 zi Rxi 3 R是标准正交矩阵,各行都是单位化的零均值正态变 量,满足独立同分布.随机投影矩阵能保持样本间成 对的距离,与SVM同属于距离学习方法.文献[16]从 理论上证明了基于随机投影的SVM可以得到与原问 题相近的分类误差,投影后的数据可以保持特征空间 的几何性质. 2基于随机投影的快速凸包分类器 2.1基于随机投影的凸包学习方法 定理1 [17]假设XA是X的凸包集A是X中的 样本标号,将X投影至任意低维子空间,得到低维子 空间的凸包集Y A A是投影空间中的样本标号,则得 到A A. 根据定理1,样本在投影低维空间时仍能保持高 维空间下的几何结构.如果样本是投影低维空间的凸 包向量,则它在原空间中一定也是凸包向量.当高维 空间的凸包难以计算时,将数据多次投影到低维子空 间,低维子空间下的凸包集组合可近似等价于高维空 间下的凸包集.基于这一想法,本文提出随机投影策 略下凸包学习方法.本算法由以下几个阶段组成 1随机投影阶段.使用高斯随机投影矩阵将 数据集X投影至L个二维子空间,得到子空间数据 PjXj 1;2;;L,然后使用特征函数将各子空 间的数据PjX映射至特征空间,得到特征空间数据 ϕPjX.以特征空间的原点为中心将ϕPjX划 分为k组对称等分区域,第i组对称区域分别表示为 sj;i和s j;ii 0;1;;k 1,即 sj;i fϕPjX atanPjX 2 [ i; i 1g; s j;i fϕPjX atanPjX 2 [ i; i1g; 4 其中 /k. 第5期顾晓清等基于随机投影的快速凸包分类器1153 2凸包候选集计算阶段.定义对称区域sj;i和 s j;i的单位向量kerui和keru i ,即 kerui ϕ cos i 2 ; sin i 2 ; keru i ϕ cos i 2 ; sin i 2 5 在第i组对称区域sj;i和s j;i中,计算ϕPjX与单位 向量kerui和keru i内积的最大值mj;i和m j;i,有 mj;i max ϕx2sj;i kerui Tϕx; m j;i max ϕx2s j;i keru i Tϕx 6 在区域sj;i中求得与kerui内积值为mj;i的向量 Mj;i,在区域s j;i中求得与keru i内积值为m j;i的向 量M j;i,有 Mj;i fϕx 2 sj;i kerui Tϕx mj;ig; M j;i fϕx 2 s j;i keru i Tϕx m j;ig 7 在区域sj;i和s j;i中,求得凸包候选向量vj;i和v j;i,有 vj;i max max ϕx2s j;i M j;i kerui Tϕx;Mj;i; v j;i max max ϕx2sj;i Mj;i keru i Tϕx;M j;i 8 值得说明的是如果特征空间的原点在 ϕPjX几何结构的内部,则凸包候选向量vj;i和 v j;i分别等于向量Mj;i和M j;i;但如果特征空间的原 点不在ϕPjX几何结构的内部,则由式8可以计 算得到ϕPjX的全部凸包候选向量.然后,使用每 一组对称区域中的凸包候选向量vj;i和v j;i构建凸包 候选集V ,即 V L∪ j1 ffvj;i ∥vj;i∦ 1g∪fv j;i ∥v j;i∦ 1gg 9 最后,将凸包候选集V中的特征向量还原至原始 数据中的d维样本,并统计各样本出现的频次. 3凸包集构建阶段.根据凸包的定义,设V 是V 的任意子集,即V V .对于V中的任意样本vi,建 立函数fvi;V ,即 fvi;V min vi ∑ vt2V i;tvt 2 ; st 0 ⩽ i;t ⩽ 1; ∑ vt2V i;t 1 10 如果满足max vi2V fvi;V 小于阈值“,则定义V 为V 在特征空间中的凸包集.在这种情况下,V中的任意 样本vi都可以写成与V 中向量的线性组合关系,即 vi ∑ vt2V i;tvt i 11 其中∥ i∥2 ⩽ “;且 i;t 8 “, 说明vi不能用当前凸包集V 线性表示,则将vi加入 到凸包集V 中,更新V 得到V V ∪vi.对式 10进行求解时,展开各项并忽略常数项,式10可以 写成如下形式 min 2viTV TV TV ; st ∑ vt2V i;t 1; 0 ⩽ i;t ⩽ 1 12 式12是一个标准的凸二次规划问题,本文使用序贯 最小优化sequentialminimaloptimization,SMO[18]算 法来求解. 设 t是凸包集V 中每个凸包向量xt的权值,用 来体现每个凸包向量在凸包集中的“重要程度”. t 的值可以通过下式计算得到 t N∑ i1 i;t 13 2.2基于随机投影的快速凸包分类器 不失一般性,本文讨论二元分类问题.假设数据 集X在正负两类样本X和X 上分别得到特征空 间凸包集KerCHX和KerCHX . KerCHX 和KerCHX 对应的原始样本连同其权值一起参 与SVM分类器的训练.因此,基于随机投影的快速凸 包分类器FCHC-RP的无约束原始问题表示为 min w;b 1 2∥w∥ 2 C N jV j∑ t1 tlw;b;ϕxt 14 其中lw;b;ϕxt为损失函数,jV j为凸包集V 的 容量. FCHC-RP能使用不同类型的损失函数,鉴于 hinge损失函数在SVM中应用最广泛,将hinge损失函 数代入式14,得到 min w;b 1 2∥w∥ 2 C N jV j∑ t1 t t; st yiwTϕxi b ⩾ 1 i; i ⩾ 0; i 1;;jV j 15 引入拉格朗日乘子 ,式15可写成如下的对偶形式 1154控制与决策第35卷 max jV j∑ i1 i 12 jV j∑ i1 jV j∑ j1 i jyiyjϕxiTϕxj; st jV j∑ i1 yi i 0; 0 ⩽ i ⩽ CN t; i 1;;jV j 16 与传统SVM方法类似,求解出超平面法向量w和偏 移量b,可得FCHC-RP的分类决策函数 fx wTϕx b 17 2.3 FCHC-RP算法描述 根据以上分析,本节给出FCHC-RP算法的描述. 算法1 FCHC-RP算法. step1使用式3将X投影至L个二维空间; for j 1 to L step2使用式4建立k个等分区域对fsj;i;s j;ig; step3使用式5定义sj;i和s j;i的单位向量 kerui和keru i ; step4使用式6 8计算sj;i和s j;i中的凸包候 选点; endfor step5使用式9 12建立凸包候选集V ; step6还原V至原始空间,统计样本出现的频次 并删除重复样本; step7使用式12计算凸包集V ; step8使用式13计算权重 t; step9将V 对应的原始样本和 代入式15和 16求解参数w;b; step10将w;b代入式17,得到决策函数fx. 3问题讨论 3.1 FCHC-RP精度误差分析 定义L1-SVM的无约束最优化问题F1w;b为 min w;b F1w;b 12∥w∥2 CN N∑ t1 lw;b;ϕxt; FCHC-RP的无约束最优化问题F2w;b为 min w;b F2w;b 12∥w∥2 CN jV j∑ t1 tlw;b;ϕxt; 其中 lw;b;ϕxt maxf0;1 ytwTϕxt bg 定理2设L1-SVM的最优解是w 1;b 1,FCHC- RP的最优解是w 2;b 2,则 F1w 1;b 1 F2w 2;b 2 ⩽ CpC“ 证明定义F3w;b为 min w;b F3w;b 12∥w∥2 CN N∑ t1 lw;b;ut; 其中ui jV j∑ t1 i;tϕxt;ϕxt 2 V ,则 L3w;b;V C N N∑ i1 max [ 0; { 1 yi wT jV j∑ t1 i;tϕxt b }] ⩽ C N N∑ i1 jV j∑ t1 max[0; i;tf1 ytwTϕxt bg] C N jV j∑ t1 max[0;1 ytwTϕxt b] N∑ i1 i;t L2w;b;V 等式的两端加上1/2∥w∥2可得F3w;b ⩽ F2w; b.由式10同理可得 CN N∑ i1 maxf0;yiwT ig⩽ F1w;b F3w;bCN N∑ i1 maxf0; yiwT ig 由此可得 F1w 1; b 1 F3w 2;b 2 ⩽ C N N∑ i1 maxf0; yiw 2T ig⩽ CN N∑ i1 ∥w 2∥∥ i∥ 由文献[19]可得∥w 2∥⩽pC,因此 F1w 1; b 1 F3w 2; b 2⩽ CN N∑ i1 pC“ CpC“ 2 定理2证明了FCHC-RP与传统使用hinge损失 函数的L1-SVM在分类精度上是相当的. 3.2 FCHC-RP精度误差分析 FCHC-RP方法可以分为随机投影、计算凸包候 选集、计算凸包集和建立分类器4个阶段.给定规 模为N的d维数据集,FCHC-RP前2个阶段的时间复 杂度分别是OL2dN和ON 2k/2.其中L 是执行随机投影的次数,k是等分区域对的个数.第 3阶段以渐近方式使用SMO算法求解式10,时间 复杂度是O jVj∑ i1 n2i ,其中jVj和ni分别是凸包候 选集和当前凸包集的容量.第4阶段仍然使用SMO 算法训练分类器,时间复杂度为OjV j2,其中jV j 是FCHC-RP在第3阶段结束时得到的凸包集的容 量.因此,FCHC-RP分类器的时间复杂度是 O L2dN N 2k/2 jVj∑ i1 n2i jV j2 需要说明的是第1和第2阶段在并行环境下执 行时间复杂度会有效降低;而凸包集V 的规模远小 第5期顾晓清等基于随机投影的快速凸包分类器1155 于样本总体规模N.因此,FCHC-RP时间复杂度远小 于传统SVM高达ON3的时间复杂度. 3.3 FCHC-RP不平衡数据的分类 一般认为,两分类样本规模的比例低于12时,数 据集具有不平衡特征. SVM在处理不平衡数据的分 类问题时,分类超平面易向少数类样本偏移,导致少 数类样本的误判率较高.对此,FCHC-RP可通过等分 区域参数k或凸包阈值“来调节凸包集的规模.当k 值较小时,等分区域数量就少,FCHC-RP最终得到的 凸包集的规模也较小.当“值较小时,凸包候选集中 不满足max vi2V fvi;V ⩽ “的向量数目就多,最终得 到的凸包集的规模就越大;反之,当“值较大时,得到 的凸包集的规模较小.实际应用中,在不平衡比例不 高的大规模数据分类问题中两类比例小于130,可 在k或“设定的搜索范围内,在少数类样本中使用较 小的k或“值,同时在多数类样本中使用较大的k或 “值,使得两类样本得到的凸包集规模相当.当大规 模数据不平衡比例较高时正负类比例大于130,可 仅在多数类样本中计算凸包集,保留全部的少数类样 本,此时式14中少数类样本对应的 值均为1. 4实验分析 4.1实验设置 为验证本文所提出FCHC-RP分类器的有效性, 本节将在10个不同类型的数据集[20]如表1所示上 设计多个学习任务1 FCHC-RP与基线分类器L1- SVM[21]以及几种适用于大规模数据分类器进行比 较,包括CVM[22]、CHVM[14]和FastKDE[11];2 FCHC- RP与几种适用于不平衡数据分类方法进行比较,包 括IM-FastKDE[11]、CS-SVM[23]和MLWSVM[24]. 实验参数设置如下FCHC-RP等分区域参数k 的取值范围是f4,6,9,18g,凸包阈值“的取值范围是 f10 3;10 2;10 1g.随机投影矩阵有多种形式,本文 使用高斯随机投影矩阵.根据大量的实验,当样本的 维数小于20维时,随机投影迭代次数等于样本维数 表1 10个真实数据集的基本信息 数据集规模维数两类样本比例 a9a 35000 123 12 buzz 140707 77 45 dosvsnormal 250000 41 11 forest 581012 54 11 ijcnn1 33895 22 23 kdd99 300000 41 11 letter26 20000 16 11 multi-ncRNA 448601 8 12 normalvsprb 123000 41 12 nursery 12960 8 23 2;当样本的维数大于20维时,随机投影迭代次 数等于样本维数 12. FastKDE按15训练集的样 本数进行采样;IM-FastKDE基于FastKDE在两类样 本上按不同比例进行采样,使得两类样本比例为 11. CVM的逼近精度是10 5;L1-SVM使用libsvm 工具箱[21]实现;CS-SVM和MLWSVM中两类样本的 正则化参数比例与两类样本的容量成反比.所有 SVM算法中的核函数均采用高斯核,核参数和正则 化参数的取值范围均为f10 3;10 2;;103g.所有 参数均采取5重交叉验证法来选取最优值. 大规模数据分类方法采用分类精度、G-mean[25] 和训练时间3种评价指标;不平衡数据分类方法采 用G-mean、F-measure[25]和训练时间3种评价指标. 其中分类精度用来评价数据集整体分类性能,G- mean用来评价在保持正负类分类精度平衡下最大 化两类的精度,F-measure用来评价分类器对少数 类的分类性能.实验在2.53-GHz quad-core CPU,8- GB RAM,Windows 7系统下执行,所有分类器均在 Matlab2016b环境下实现. 4.2大规模数据集的分类 本节在10个数据集上评价FCHC-RP方法的性 能表2比较了所有方法的分类精度及其方差括号 内数值为方差,表3比较了所有方法的G-mean及其 方差,表4比较了所有方法的训练时间及其方差. 表2不同方法在10个真实数据集上的分类精度及其方差的比较 数据集L1-SVM CVM CHVS FastKDE FCHC-RP a9a 8242028 80.780.32 81.580.30 80.220.36 8242028 buzz 92.390.33 93.560.32 92.230.35 9453032 dosvsnormal 94.230.17 96.250.17 94.390.37 9660015 forest 93.970.20 97.400.10 95.400.28 9788010 ijcnn1 9102038 90.480.43 90.120.37 88.050.49 90.740.36 kdd99 91.000.33 91.950.30 90.510.42 9243030 letter26 97.600.10 97.420.13 97.250.12 97.230.15 9764011 multi-ncRNA 93.490.28 95.410.24 92.370.31 9566021 normalvsprb 92.670.25 92.740.19 92.050.27 9314019 nursery 9078027 90.020.34 90.510.28 90.000.39 90.570.27 1156控制与决策第35卷 表3不同方法在10个真实数据集上的G-mean及其方差的比较 数据集L1-SVM CVM CHVS FastKDE FCHC-RP a9a 82.200.28 80.700.34 81.360.32 79.650.35 82.210.28 buzz 92.510.32 93.820.32 92.380.34 94.610.31 dosvsnormal 94.170.19 96.090.19 94.180.23 96.630.16 forest 93.900.16 97.350.15 95.260.26 97.340.12 ijcnn1 90.410.40 90.200.48 90.030.43 87.270.52 90.190.42 kdd99 91.020.42 91.370.40 90.540.50 92.350.40 letter26 97.630.11 97.490.12 97.160.13 97.120.12 97.630.11 multi-ncRNA 93.100.24 95.380.27 92.040.32 95.620.23 normalvsprb 92.610.23 92.560.21 92.310.24 93.400.19 nursery 90.540.30 89.990.32 90.040.30 89.870.40 90.460.31 表4不同方法在10个真实数据集上的训练时间单位s及其方差的比较 数据集L1-SVM CVM CHVS FastKDE FCHC-RP a9a 568.855.67 84.750.80 67.850.67 11.560.16 17.470.23 buzz 2865.8520.45 248.712.62 497.215.00 92.390.87 dosvsnormal 12586.48109.17 313.393.48 215.383.40 200.153.00 forest 40344.37220.69 466.603.16 2196.5822.52 325.983.33 ijcnn1 480.454.55 70.750.47 14.720.15 10.490.19 10.480.12 kdd99 3300.9040.15 480.364.22 350.784.18 329.123.60 letter26 198.423.01 20.530.42 4.970.07 2.470.03 3.730.05 multi-ncRNA 3160.1830.63 155.890.79 750.838.92 83.700.71 normalvsprb 5268.6624.63 107.541.92 80.430.55 78.420.50 nursery 150.821.08 25.480.22 12.740.17 9.36 0.08 9.59 0.10 1从表2中可以看出,由于L1-SVM使用Libsvm 工具箱实现,其在multi-ncRNA、kdd99和forest等6个 数据集上的训练时间超过5个小时,实验没有记录其 结果.但在有记录的a9a、ijcnn1和nursery这3个数据 集上L1-SVM取得了最高分类精度,这是因为所有的 训练样本均参与到L1-SVM分类器的训练中. FCHC- RP则在其余的7个数据集上取得了最佳分类精度,因 为FCHC-RP中的训练样本是能够表示数据集在特征 空间几何结构的凸包向量. CHVS和CVM也取得了 较高的分类精度.而FastKDE的分类精度相对较低, 其原因在于FastKDE使用随机采样的策略来获得训 练样本,而随机采样的不确定性容易导致得到的样本 不能表示数据集的几何结构. 2从表3中可以看出,G-mean评价指标上的结 果与表2的分类精度保持了一致性.由于10个数据 集都属于类别平衡的数据集,少数类和多数类的样本 规模大致相当,所有分类器在不同类别样本上的准确 率均较接近,可以看到,FCHC-RP取得了令人满意的 结果,在10个数据集上胜出了7次. 3从表4中可以看出,除a9a、nursery和letter26 数据集外,FCHC-RP在7个真实数据集上的训练时 间最短. FCHC-RP计算凸包候选集的时间复杂度是 近似线性的,大多数数据集上获得的凸包候选集仅 占训练集规模的不到10,随后FCHC-RP以渐近的 方式计算凸包集,因此,FCHC-RP可以实现分类器 的快速训练.随着训练数据规模的增加,CVM的训 练时间增加幅度较大,因为CVM的时间复杂度在 理论上与训练数据的规模无关,但在大规模数据的 分类问题中,CVM往往需要较长时间找到近似最小 包含球. CHVS在维数较高的数据集上训练时间较 长,CHVS的时间复杂度是 O Nd4 l∑ i1 n msv 其中d是样本的维数,n和 msv分别是凸包向量 的个数和每次迭代中的支持向量数,l是迭代的次 数.因此,CHVS在高维大规模数据上训练时间较长. FastKDE在10万规模以下的训练集上具有一定的优 势,在a9a、letter26和nursery数据集上取得了最优结 果. 4.3不平衡数据集的分类 为了更好地呈现样本的不平衡性对算法性能的 影响,本节对数据集ijcnn1、dosvsnormal和Nursery进 行改造.依照不平衡数据分类问题中常用的设定方 法,少数类为正类,多数类为负类. ijcnn1数据集分别 随机取正类样本4000、1000、500和400,负类样本 取20000;dosvsnormal数据集分别取正类样本2500、 625、312和250,负类样本取125000;Nursery数据集 分别取正类样本1555、389、195和156,负类样本取 7776.正负类样本比例分别为15、120、140、150. 如前文所述,FCHC-RP在处理不平衡数据分类 问题时,若正负类比例小于130,则在正负类样本中 使用不同的k来计算两类样本的凸包集;若正负类比 第5期顾晓清等基于随机投影的快速凸包分类器1157 例达到或大于130,则仅在多数类样本中计算凸包 集,保留全部的少数类样本.图1比较了所有方法的 G-mean及其方差,图2比较了所有方法的F-measure 及其方差,图3比较了所有方法的训练时间及其方差. 1501401201565 70 75 80 85 90 G- me an s/ UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b a ijcnn1 FCHC-RPIM-FastKDE MLWSVMECS-SVM 1501401201580 83 86 89 92 G- me an s/ UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b b dosvsnormal FCHC-RPIM-FastKDE MLWSVMECS-SVM 80 82 84 86 88 90 15014012015 UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b c nursery G- me an s/ FCHC-RPIM-FastKDE MLWSVMECS-SVM 图1不同方法的G-mean比较 65 70 75 80 85 F-m eas ure / 15014012015 UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b a ijcnn1 FCHC-RPIM-FastKDE MLWSVMECS-SVM 84 87 90 93 15014012015 UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b b dosvsnormal F-m eas ure / FCHC-RPIM-FastKDE MLWSVMECS-SVM 80 82 84 86 88 15014012015 UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b c nursery F-m eas ure / FCHC-RPIM-FastKDE MLWSVMECS-SVM 图2不同方法的F-measure比较 15014012015 UNI6b63UNI8d1fUNI7c7bUNI6bd4UNI4f8b a ijcnn1 0 100 200 300 400 500
展开阅读全文
收藏
下载资源

加入会员免费下载