基于k均值聚类的支持向量svdd学习算法

基于k均值聚类的支持向量svdd学习算法

1总结支持向量数据的描述（svdd支持向量数据的描述）是一种单值分类算法。2正则化控制函数根据文献[1],SVDD算法的思想为寻找一个超球体,使其半径尽可能小的同时,包含的训练样本数尽可能多。其目标函数为其中,R为球体半径;a为球心;ξ为松弛变量;C为正则化参数,控制对错分样本的惩罚程度,实现对球的大小和所包含的样本数之间的折衷。同SVM类似,当样本点非线性可分时,使用非线性映射Φ(x式(1)、式(2)的对偶问题为其中,α根据最优化原理,当所有α其中,d3kmsvdd算法的概念和缺陷分析3.1kmsvdd算法KMSVDD算法可概括为3个步骤:Step1使用K均值聚类方法将整个数据集分成K个较小的子数据集。Step2在K个子数据集上分别进行SVDD学习,得到由K组支持向量集描述的局部训练模型。Step3对K组支持向量集再次进行SVDD学习,得到最终的全局学习模型。KMSVDD算法的学习时间主要分为3个组成部分:K均值聚类时间,K个子数据集的SVDD学习时间之和,K组支持向量集的SVDD学习时间。一般解决QP问题的时间复杂度为O(N因此,该方法是一种快速的SVDD学习算法。3.2增加了大量的学习数据的加入算法KMSVDD利用各聚类簇中少量的局部支持向量集进行学习来获得一个全局的SVDD学习模型,而支持向量以外的数据则完全舍弃。虽然这种方法在很大程度上降低了计算开销,但同时也可能影响了全局模型的识别精度。因为,随着新增学习数据的加入,原训练数据集中非支持向量数据的地位可能会发生变化,即部分非支持向量数据可能会转换为新的支持向量数据(因篇幅有限,此结论的证明可参照文献[6]中定理3)。KMSVDD在聚类之后就已经删除全部非支持向量数据,从而造成有价值学习数据的流失,导致最终学习模型识别精度的下降。4采用k平均值聚集高级swdd学习算法4.1聚类簇中非支持向量的lagrange乘子生成定理1在分类SVDD中,对应于α证明:由上述KKT条件即可得证。定理2若各聚类簇中非支持向量数据均满足KMSVDD的KKT条件,则其中肯定不存在新支持向量(新支持向量指对整个初始训练样本学习后的支持向量)。证明:所有非支持向量数据的Lagrange乘子皆为0,因其均满足KMSVDD的KKT条件。则由定理1可知,这些数据分布于超球内(包含超球边界),这样SVDD对整个初始训练样本进行优化与对各聚类簇中支持向量集合并优化的结果是等价的,所有非支持向量的Lagrange乘子(皆为0)与支持向量的原Lagrange乘子组合后生成的新Lagrange乘子就是新SVDD的最优解。由于非支持向量的Lagrange乘子皆为0,因此非支持向量数据中不存在新支持向量。定理2得证。定理3若各聚类簇中非支持向量数据存在违背KMSVDD的KKT条件的样本,则违背KKT条件的样本中必存在新支持向量。反证法:证明:若违背KKT条件的样本中不存在新支持向量,结合定理2可进一步推知,所有非支持向量数据中不存在新支持向量。因此,若对整个初始训练数据进行学习,各聚类簇中所有非支持向量数据的Lagrange乘子皆为0,这样SVDD对整个初始训练数据进行优化与对各聚类簇中支持向量集合并优化的结果是等价的。由于所有非支持向量数据肯定满足对整个初始训练数据进行优化后SVDD的KKT条件,因此也应该满足KMSVDD的KKT条件。显然与命题的假设条件矛盾。定理3得证。4.2改进算法hkmsvdd由定理2和定理3可知:对于各聚类簇中非支持向量数据,满足全局训练模型KMSVDD的KKT条件的数据可以舍弃,因为KMSVDD已经包含了这部分数据的信息,所以无需再对这些数据进行学习。而那些违反KKT条件的数据,则需要对其再进行学习,因为KMSVDD没有包含这部分数据的信息。所以,若从非支持向量数据中选出那些违反KMSVDD的KKT条件的样本,结合各聚类簇的支持向量集一同学习,将会提高全局训练模型的识别精度。本文提出一种改进的KMSVDD算法UKMSVDD,具体描述如下:Step1使用K均值聚类方法将整个数据集DataSet分成K个较小的子数据集(簇)。Step2在K个簇上分别进行SVDD学习,得到K组支持向量集,记为:SVs＿1,SVs＿2,…,SVs＿K。Step3对K组支持向量集进行SVDD学习,得到KMSVDD模型。Step4从非支持向量数据中找出违反KMSVDD的KKT条件的样本,记为Temp＿Points。Step5对SVs＿1,SVs＿2,…,SVs＿K和Temp＿Points进行SVDD学习,得到最终的全局学习模型。与KMSVDD算法相比,UKMSVDD的学习时间多了2个组成部分,即寻找Temp＿Points时间和K组支持向量集结合Temp＿Points的SVDD学习时间。由于Temp＿Points只是非支持向量数据中极少数的样本,因此这2个组成部分的时间和是微乎其微的,UKMSVDD算法的学习时间复杂度依然可近似为KO((N/K)5实验结果和分析实验数据分别采用UCI数据库中的PHD(Pen-basedHandwrittenDigits)数据集和ORHD(OpticalRecognitionofHandwrittenDigits)数据集第2个数据集中共包括3823个训练数据和1797个测试数据,如表2所示,每个数据为64维向量。对于每类数据分别采用SVDD,KMSVDD和UKMSVDD3种算法进行学习,并用相应的测试数据进行检验。实验环境为Intel1.8GHz的CPU、256MB内存、WinXP操作系统和Matlab6工具软件。实验中核函数均采用高斯核,即C和σ均取相同的值,分别为0.8和50。在聚类中,K的取值分别为6(PHD数据集)和4(ORHD数据集)。从表3可知,对于PHD数据集,KMSVDD的平均学习时间为13.24s,远低于SVDD的761.63s,平均检测率比SVDD低了2.38个百分点。UKMSVDD的平均学习时间为14.49s,比KMSVDD慢了1.25s,平均检测率与SVDD相同。对于ORHD数据集,KMSVDD的平均学习时间为3.73s,远低于SVDD的61.23s,平均检测率比SVDD低了1.77个百分点;UKMSVDD的平均学习时间为4.11s,比KMSVDD慢了0.38s,平均检测率与SVDD相同。综合实验结果可得,本文提出的UKMSVDD算法利用极少的时间代价提高了KMSVDD对未知类的识别精度,因此,算法UKMSVD