减少训练时间与支持向量的方法

摘要

一种智能信息处理技术领域的减少训练时间与支持向量的方法，包括如下具体步骤：步骤一，从训练样本中抽取邻界样本得到邻界样本集，得到空间分布的边界信息；步骤二，在步骤一抽取邻界样本后，抽取训练样本中的非邻界样本，得到精简样本集；步骤三，合并邻界样本集与精简样本集得到最终训练样本集。本发明由于保留样本分布的边界特征，又保留非边界样本，用得到的最终样本集进行支持向量机的训练，得到最终的分类器，本发明可大幅度精简训练样本，泛化能力几乎没有改变。

说明书

技术领域

本发明涉及一种信息处理技术领域的方法，具体是一种减少训练时间与支持向量的方法。

背景技术

人们认识世界是从分类开始的，分类是人们认识世界的最基础性方法。传统的分类方法kNN(K-最近邻)是基本而且重要的方法。随着神经网络应用范围的扩展，应用复杂性的提高，上世纪九十年代提出了几种很新的性能更好的方法。最具代表并独立成系统的方法是吕宝粮教授提出的M³方法(Max-Min-Model最大最小模块)以及Vapnik提出的关于结构风险最小化的代表方法SVM(支持向量机)。SVM方法是结构风险最小化理论的实现方法，其最主要的思想就是要借助求解二次规划问题来求解两类样本之间最大距离，因此随着问题复杂程度的增加以及样本数量的增加，SVM的执行效率尤其是训练过程就是很大的问题了。训练样本越多越能够得到更多的样本分布的结构信息，因此更多的训练样本必然可以得到泛化能力更强的SVM。但是，由于参数选取的困难，对大的训练样本来说，搜索到合适的训练参数是个很困难的事情，因此，如果能够减少训练样本的数量，则必然可以增加训练参数搜索的速度。随着训练样本的减少，得到的支持向量的个数也在减少，更为重要的是，增加了测试速度。

经对现有技术的文献检索发现，S.Amari等于1999年在《Neural Networks》(神经网络)12卷783页上发表的“Improving support vector machineclassifiers by modifying kernel functions”(通过修改核函数方法提高支持向量机的性能)该文谈到提高性能的方法，该方法从修改核函数的角度减少支持向量的个数，该方法基于黎曼几何空间，通过加大超平面附近的样本之间的距离增加样本之间的可分性来减少支持向量，这是一个全新的方法。但该方法需要对全部样本反复训练，不断调整超平面的位置，最后达到最优。该方法并没有对训练样本进行任何精简，因此对于大规模的训练样本，由于需要反复训练，该方法同样存在训练效率以及测试效率的问题。

发明内容

本发明针对上述现有技术的不足，提出了一种减少训练时间与支持向量的方法，使其解决现有支持向量机方法在解决大规模问题时训练时间过长、支持向量过多的不足。

本发明是通过如下技术方案实现的，包括如下步骤：

步骤一，从训练样本中抽取邻界样本得到邻界样本集，得到空间分布的边界信息。

所述抽取邻界样本，具体如下：

第1步、若训练样本中只有一个两类样本集，两类样本集包括：正类样本和负类样本，计算出一类中的每个样本到另外一类每个样本的距离，每个距离对应两个分别属于两个类别的样本；若训练样本超过一个两类样本集，通过两两组合成多个两类样本集，再重复如上操作；

第2步、把距离从小到大进行排序，并预先定义两个集合A、B，集合A用于存放正类邻界样本，集合B用于存放负类邻界样本，并将集合A、B置空；

第3步、按照距离从小到大的先后关系，取出最小距离对应的正类邻界样本和负类邻界样本；

第4步、将正类邻界样本并入集合A，负类邻界样本并入集合B，然后计算训练样本中除步骤4的正类邻界样本和负类邻界样本之外的每个正类样本和负类样本分别到集合A、B中的样本的距离；

第5步、对于训练样本中每个正类样本x，如果集合A存在一个样本a，使得正类样本x到样本a的距离小于正类样本x到集合B中的任意一个样本b的距离，则用集合A、B把正类样本全部正确分类，否则进入步骤6；

如果用集合A、B同样按照上述方法把负类样本全部正确分类，则步骤一结束，集合A、B中的样本就是抽取的邻界样本，否则进入步骤6；

第6步、如果最小距离对应的正类邻界样本和负类邻界样本不能将正类样本和负类样本全部正确分类，按照距离从小到大的先后关系，取出下一个距离对应的两个邻界样本，转到步骤4，重复第4步和第5步。

第7步、经过上述步骤，当使得每一个样本与本类邻界样本的最小距离小于该样本到另一类邻界样本的最小距离，表明得到邻界样本集，即得到一个两类样本的边界空间信息。

步骤二，在步骤一抽取邻界样本后，抽取训练样本中的非邻界样本，得到精简样本集；

所述非邻界样本，是指邻界样本集合构造完成以后，训练样本中剩余的样本就是非邻界样本。

所述抽取训练样本中的非邻界样本，具体如下：

建立中心样本集合C、D并置空，中心样本集合C用于存放正类样本、中心样本集合D用于存放负类样本，在非邻界的正类样本和负类样本中随机各选择一个样本作为中心样本分别并入中心样本集合C、D，计算其他非邻界样本与本类中心样本的距离，如果一个非邻界样本与所有中心样本的距离均大于设定的精简半径，则把该非邻界样本并入中心样本集，否则把该非邻界样本精简掉，然后进行下一个非邻界样本的判断，直到所有的非邻界样本被判断完毕，形成两个经过选择的精简正类样本中心样本集合C和负类样本中心样本集合D。

所述精简半径的大小反映训练样本被精简的程度，精简半径越大，被精简的非邻界样本越多。

步骤三，合并邻界样本集与精简样本集得到最终的训练样本集，。

所述得到最终的邻界样本，是指将正类邻界样本集合A、负类邻界样本集合B和正类样本中心样本集合C、负类样本中心样本集合D合并，得到最终的训练样本集，最终的训练样本数目大幅度减少，保持了训练样本的符合支持向量机训练特性的复杂特征，并保持了支持向量机的泛化能力。

与现有技术相比，本发明的有益效果具体如下：(1)本发明由于保留样本分布的边界特征，又保留非边界样本，用得到的最终样本集进行支持向量机的训练，得到最终的分类器，使得该分类器与用全部训练样本得到的分类器保持一致的识别准确率；(2)本发明提出保留邻界样本，精简非邻界样本的方法可以避免训练时间过长，支持向量过多的不足，本发明保留了样本的分布信息，可大幅度精简训练样本，泛化能力几乎没有改变，训练样本减少90％，支持向量减少近60％，与通过参数搜索得到的最好的泛化能力相比，泛化能力的下降还不到0.8％。

具体实施方式

下面对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

实施例1

本实施例所使用的数据为Benchmark(基准数据库)提供的Banana(香蕉)数据库，其中使用训练样本的前第1-50组，每组样本数量为400，总共20000个训练样本，测试样本的前面第1-5组，每组样本数量为4900，总共24500个测试样本。

步骤一，从训练样本中抽取邻界样本得到邻界样本集，得到空间分布的边界信息。

第1步、若训练样本中只有一个两类样本集，两类样本集包括：正类样本和负类样本，计算出一类中的每个样本到另外一类每个样本的距离，每个距离对应两个分别属于两个类别的样本；若训练样本超过一个两类样本集，通过两两组合成多个两类样本集，再重复如上操作；

第2步、把距离从小到大进行排序，并预先定义两个集合A、B，集合A用于存放正类邻界样本，集合B用于存放负类邻界样本，并将集合A、B置空；

第3步、按照距离从小到大的先后关系，取出最小距离对应的正类邻界样本和负类邻界样本；

第4步、将正类邻界样本并入集合A，负类邻界样本并入集合B，然后计算训练样本中除步骤4的正类邻界样本和负类邻界样本之外的每个正类样本和负类样本分别到集合A、B中的样本的距离；

第5步、对于训练样本中每个正类样本x，如果集合A存在一个样本a，使得正类样本x到样本a的距离小于正类样本x到集合B中的任意一个样本b的距离，则用集合A、B把正类样本全部正确分类，否则进入步骤6；

如果用集合A、B同样按照上述方法把负类样本全部正确分类，则步骤一结束，集合A、B中的样本就是抽取的邻界样本，否则进入步骤6；

第6步，如果最小距离对应的正类邻界样本和负类邻界样本不能将正类样本和负类样本全部正确分类，按照距离从小到大的先后关系，取出下一个距离对应的两个邻界样本，转到步骤4，重复第4步和第5步。

第7步，经过上述步骤，当使得每一个样本与本类邻界样本的最小距离小于该样本到另一类邻界样本的最小距离，表明得到邻界样本集，即得到一个两类样本的边界空间信息。

步骤二，精简步骤一抽取邻界样本后训练样本中的非邻界样本，得到精简样本集；

所述非邻界样本，是指邻界样本集合构造完成以后，训练样本中剩余的样本就是非邻界样本。

所述抽取训练样本中的非邻界样本，具体如下：

建立中心样本集合C、D并置空，中心样本集合C存放正类样本、中心样本集合D存放负类样本，在非邻界的正样本和负样本中随机各选择一个样本分别并入中心样本集合C、D，计算其他非邻界样本与本类中心样本的距离，如果一个非邻界样本与所有中心样本的距离均大于设定的精简半径，则把该非邻界样本并入中心样本集，否则把该非邻界样本精简掉，然后进行下一个非邻界样本的判断，直到所有的非邻界样本被判断完毕，形成两个经过选择的精简样本集合C、D。

所述精简半径的大小反映训练样本被精简的程度，精简半径越大，被精简的非邻界样本越多。

步骤三，合并邻界样本集与精简样本集得到最终的训练样本集。

所述得到最终的邻界样本，是指将正类邻界样本集合A、负类邻界样本集合B和正类样本中心样本集合C、负类样本中心样本集合D合并，得到最终的训练样本集，最终的训练样本数目大幅度减少，保持了训练样本的符合支持向量机训练特性的复杂特征，并保持了支持向量机的泛化能力。

本实施例用得到的最终的训练样本集进行支持向量机的训练，得到最终的分类器。此分类器的性能如表格1所示，下面对表格1的数据进行说明。

              表1不同参数下的最优测试准确率的比较

  精简半径  样本数量  Gamma  Cost  支持向量  测试准确率(％)  0  0.001  0.002  0.005  0.007  0.010  0.015  20000  4558  3833  3230  2581  2211  1991  8192  8192  8192  8192  16384  32768  16384  64  128  128  128  128  32  64  4654  4022  3648  3157  2571  2210  1984  98.55  98.53  98.04  97.83  97.77  97.78  97.76

Gamma，Cost表示训练支持向量机时需要调节的与性能相关的重要参数，Gamma表示半径基函数的半径大小，Cost用来平衡SVM的复杂性与不可分的样本数量之间关系的参数，Gamma和Cost均由使用者自己指定，寻找两者最佳组合，使得SVM达到最好的测试能力，但目前没有好的办法，但可以通过长时间搜索而得到最佳参数。因此表格中的Gamma，Cost是通过8台计算机(800MHz，256MRAM Pentium II PC)并行36个小时搜索得到的。搜索的Cost范围为2^-2-2¹⁰，Gamma的搜索范围是2²-2¹⁶，每一个不同的精简半径下的Gamma，Cost参数都是“最佳”的，都具有最好的泛化性能。在精简半径为0时，没有精简任何样本，即原始数据样本，得到最好的泛化能力为98.55％。

在精简半径为0.001时，精简的样本的数量只有原始样本数量的五分之一，但是测试的准确率几乎没有下降，实际上这也可以从支持向量的个数上反映出来，因为这时的支持向量的数量也与原来的差不多。这说明了本实施例方法保留了最关键的样本，精简的只是一些非邻界的样本，是一些“重复”的非关键的样本，丢掉这些样本对训练支持向量机没有大的影响。

在精简半径为0.015时，训练样本减少90％，支持向量减少近60％，与通过参数搜索得到的最好的泛化能力相比，泛化能力的下降还不到0.8％。

实施例2

本实施例数据库为Benchmark提供的Waveform数据库，为两类样本，输入的维数为21。该数据库共有训练样本集与测试样本集各100组，训练样本集每组400个样本，测试样本集每组4600个样本。在本实施例中，使用训练样本集的前第1-25组总共10000个样本作为训练样本，使用测试样本集的1-2组共9200个样本作为测试样本。

     表2以原始样本下的最优参数精简后的比较

  精简半径  样本数量  支持向量  测试准确率(％)  0  0.6  0.7  0.8  0.9  1.0  1.1  4600  3214  2637  2116  1735  1504  1355  2369  1738  1612  1466  1342  1248  1177  98.00  97.30  96.82  96.52  96.32  96.08  96.12

本实施例的具体操作过程与实施例1相同，在此不作进一步的阐述。但是，与实施例1不同的是，本实施例中训练支持向量机的参数没有经过刻意的选取，均为Gamma＝2，Cost＝2。如表2所示，虽然随着精简半径的不同，有不同的样本数量被精简，但由于保留了最为关键的邻界样本信息，因此对支持向量机的泛化能力没有太大的影响。本实施例也为了验证方法的普遍适用性。