基于主成分分析方法确定超平面的任务分解方法

摘要

一种用于智能信息处理技术领域的基于超平面划分过程可以用于最小最大模块化分类器的任务分解，使用主成分分析方法来确定该超平面的方向。本发明提出了使用一种简单的排序过程来实现这个超平面划分过程，避免了巨量的聚类算法的时间消耗，同时它有效地保证了分解后产生的分类器组合的精度，避免了以往的随机的样本抽取过程无法保证最终的分类器组合精度的情况。此外，基于超平面划分方法产生的最小最大模块化分类器具有更好的测试性能。

说明书

技术领域

本发明涉及一种智能信息处理技术领域的任务分解方法，具体是一种基于主成分分析方法确定超平面的任务分解方法。

背景技术

最小最大模块化分类器(简称M³分类器)是一种新型的模式分类器。最小最大模块化分类器按照训练集划分将K类问题分解成多个二类问题，每个二类问题由一个基分类器进行训练。各个基分类器的分类结果通过MIN单元和MAX单元组合成最终的分类结果，其中的基分类器可以是某种简单的判别器，k-NN分类器、SVM或多层神经网络等。最小最大模块化分类器在模式分类上具有分类精度高、训练速度快和大规模并行性的特点，已经被成功地应用于解决文本分类、工业故障检测、脑信号分类、词性标注等问题。

在传统的最小最大模块化分类器任务分解过程中，对于训练集的划分是随机进行的。这种随机的训练集划分方法，不能保证不同的训练集划分对最终组合分类器具有稳定的、良好的分类精度。然而，对于弹性的分类来说，常常涉及到多种不同规模的任务分解需求，这就提出了基于训练集划分的有效的任务分解问题。因此，是否能够找到一种有效的任务分解方法，对于最小最大模块化分类器是一件非常重要的任务。

经对现有技术的文献检索，至今尚未发现与本发明主题相同或者类似的文献报道。

发明内容

本发明的目的在于针对现有技术中存在的不足，提出一种基于主成分分析方法确定超平面的任务分解方法，使其用于最小最大模块化分类器的任务分解，以实现保证弹性任务分解情形下的组合分类精度的目的。

本发明是通过以下技术方案实现的，本发明利用一组平行的超平面对各个单类训练集作分割，使用主成分分析方法中的散度矩阵的特征向量作为划分的一组超平面的法向量，在训练集的超平面划分中，采用训练样本数量的加权排序实现样本的顺序抽取，继而将分割的训练子集按照最小最大模块化分类器的要求实现指定的任务分解。具体描述为两个步骤如下：

第一个步骤，所述的超平面法向量，其确定方法如下：

(1)计算所有样本的均值

$>>m>=>>\Sigma >>k>=>1>>n>>>x>k>>>s>$

(2)计算该训练集所有输入样本的散度矩阵

$>>S>=>>\Sigma >>k>=>1>>n>>>(>>x>k>>->m>)>{}^{}$

(3)计算散度矩阵的最大特征值e，取划分超平面的法向量A＝e。

其中，x_k是第k个训练样本，n是单类样本数量，m是单类样本均值，S是全部单类训练样本的散度矩阵，e是S的最大特征值。

第二个步骤，所述的训练集的超平面划分，具体实现如下：

(1)对于每个类别，按照第一个步骤确定相应的超平面P：Ax＝0；

(2)计算单类训练集中所有样本x的加权值d(x，P)＝Ax；

(3)对于所有这些值Ax排序；

(4)根据各个子集的样本数量要求，顺序抽取指定数量的样本数量构成划分后的子样本集；

(5)对于各个单类划分出来的各个单类训练子集，按照最小最大模块化分类器的要求实现各个子任务生成，从而实现所要求的任务分解。

其中，P是超平面代号，A是按照第一个步骤确定的超平面法向量，x是任意一个单类训练样本，d(x，P)表示所需的加权值。

最小最大模块化分类器的实现分为两个步骤，第一个步骤是多类到二类的分解以及对应的结果合成，第二个步骤是二类问题的进一步分解和对应的结果合成。

对于一个多类问题，根据一类对一类分解策略实现任务分解，也就是对于一个K类问题，分别一一搭配不同类别的训练集，生成K(K-1)/2个训练集对，用对应的K(K-1)/2个二类分类器进行训练。从而实现了多类到二类问题的分解。记各个二类分类器为M_ij，0＜＝i，j＜k且i和j不等。如果M_ij的分类结果为1，表明这个二类分类器支持i类的分类结果，如果分类输出为0，则表明它支持j类的分类结果。对于每一个二类分类器M_ij，将其结果取反作为分类器的M_ij结果，这样可以本发明可以调用K(K-1)个二类分类器。称这样一些二类分类器M_ij，j＝0，1，2，…，K-1，且i和j不等为一组二类分类器。i称为它的组号。对于各个二类分类器的测试结果的组合，使用两个阶段来实现，第一阶段，在各组二类分类器中，所有的二类分类器输出的分类结果Min操作作为该组的类别输出，这里Min操作是从多个输入中找出最小的输入。第二阶段，将第一阶段的操作的所有结果进行Max操作得到本阶段的组合结果，这里Max操作是从多个输入中找出最大的输入。如果第二阶段的组合结果是0，则组合分类结果本发明定义为未知类别，也就是不是任何已知的类别，如果第二阶段的组合结果是1，则在Max过程中导致了这个结果的那一组二类分类器的组号作为最终的组合分类结果。

对于一个二类问题，将其类别输出分别表示为0和1。设，0类训练集划分为n个模块，1类训练集划分为m个模块。分别完全搭配这m个和n个训练集产生m*n个训练集对。如果每个训练集对由一个二值分类器来学习，就将一个原始的较大规模的二类问题分解为m*n个较小规模二类问题。对于原始的二类问题，称用于解决分解后产生的较小规模的二类问题的二值分类器为相应的基分类器。

设原始分类问题中，用T_ij表示划分后的训练集对，其中i＝1，2，...，m，j＝1，...，n，相对应的基分类器表示为X_ij。最小最大组合定义了如何将这m*n个基分类器的分类结果重新合成为原始问题的分类结果。在组合之前，需要对m*n个基分类器进行分组，对于一个固定的i，定义X_ij，其中j＝1，...，n，为一个1类组。i称为该组的组号。分类结果的最小最大组合过程分为两个阶段：第一阶段，在各个1类组中，所有的基分类器输出的分类结果Min操作作为该组的类别输出，这里Min操作是从多个输入中找出最小的输入。第二阶段，将第一阶段的操作的所有结果进行Max操作就得到组合后的最终分类结果，这里Max操作是从多个输入中找出最大的输入。

本发明提出了使用一种简单的排序过程来实现这个超平面划分过程，避免了巨量的聚类算法的时间消耗，同时它有效地保证了分解后产生的分类器组合的精度，避免了以往的随机的样本抽取过程无法保证最终的分类器组合精度的情况。此外，基于超平面划分方法产生的最小最大模块化分类器具有更好的测试性能。

具体实施方式

以下结合本发明的内容提供具体实施例：

实施例1

数据集取自UCI数据库和STATLOG benchmark repository的3组两类数据，数据特性如表1所示。

由于二类问题是所有分类问题的基础，多类问题总是可以通过二类问题组合的最小最大化等方法实现，而本发明提出的技术也只需要考虑单类上的训练集分解，具体的实现和类别数特性无关。因此，二类问题分类效果展示足以本发明提出的技术的效果。

                             表1。数据集的类别信息和SVM训练参数

  数据集        训练样本数量        测试样本数量     SVM训练参数   Adult  banana  Hear  总共  32561  40000  17000  0类  24720  21847  9440  1类  7841  18153  7560  总共  16281  49000  10000  0类  12435  27026  5560  1类  3846  21974  4440  C  16  316.2  3.162  gamma  0.25  1  0.008333

针对两类较小规模的那个类别，依次分为2到26个模块，较大的类别进行对应的划分，使得划分出来的单类样本数量和较小类别的单类样本数量相当。两种分类算法：k-NN和RBF核的SVM用来进行算法效果的验证工作。SVM训练参数如表1所示。k-NN算法均使用从1-40的40组不同k值进行测试。

实施过程具体如下：

1、按照随机划分和本发明所提的方法分别进行单类训练集上的指定模块规模的划分。

2、按照最小最大模块化分类器的构成方法进行训练，分别使用k-NN分类器和SVM分类器。

3、对于测试集中的样本进行逐一测试，按照最小最大模块化分类器的结果合成方法输出测试结果。

通过比较随机训练集划分、法向量A＝[1，1，…，1]的超平面划分以及由主成分分析方法确定的超平面划分的分类精度，所获得的结论是，由主成分分析方法确定的超平面划分的分类精度在所有数据集上是最佳的，同时分类精度曲线平稳，能够有效保证更多模块数量下的组合分类器的分类效果。在不同的数据集上的一致效果表明了本发明所提方法的通用性。

实施例2

基分类器采用SVM算法。SVM训练参数如表1所示。针对两类较小规模的那个类别，依次分为2到26个模块，较大的类别进行对应的划分，使得分出来的单类样本数量和较小类别的单类样本数量相当。

实施过程具体如下：

1、按照随机划分和本发明所提的方法分别进行单类训练集上的指定模块规模的划分。

2、按照最小最大模块化分类器的构成方法进行SVM分类器训练。

3、对于测试集中的样本进行逐一测试，按照最小最大模块化分类器的结果合成方法输出测试结果。

通过比较随机训练集划分、法向量A＝[1，1，…，1]的超平面划分以及由主成分分析方法确定的超平面划分的分类速度，所获得的结论是，由主成分分析方法确定的超平面划分在所有数据集上的分类速度是最快的。在不同的数据集上的一致效果表明了本发明所提方法的通用性。