CN103713885A - 一种面向多核集群的smo并行处理方法 - Google Patents

Abstract

本发明涉及一种面向多核集群的SMO并行处理方法。包括：根据全局参数给本地问题参数赋初始值，并对算法参数赋初始值；根据本地问题参数的初始值，计算本地问题参数的本地第一界和本地第二界；根据本地第一界和本地第二界，获取全局第一界和全局第二界；在全局第一界和全局第二界之差不小于预设的精度时，迭代计算全局第一界对应的第一乘子以及全局第二界对应的第二乘子；其中，每次迭代后多线程更新本地问题参数；在迭代达到预设的迭代次数时，根据本地样本乘子计算待分类数据的本地解，根据本地解获取全局解，完成数据分类。本发明解决了传统的数据分类成本高、误码率高以及反应速度慢的问题。

Description

一种面向多核集群的SMO并行处理方法

技术领域

本发明涉及数据分类，尤其涉及到一种面向多核集群的SMO并行处理方法。

背景技术

本发明要解决问题的是实现文本分类并行化，不仅提升文本分类的速度，而且更加合理有效地分布存储数据。该技术问题来源于搜狗公司，搜狗搜索作为一家互动式中文搜索引擎，分类技术是其核心技术之一。由于现代互联网的数据规模不断增加，其需要分类的样本容量巨大，然而将这些资料存储在同地同磁盘的方案显然很难应对未来数据世界的变化。因此，急需一种技术方案来实现这些资料的分布式存储，以及并行化的分类。根据目前搜狗公司在分类业务方面的实际需求，我们需要完成如下样本规模的分类：一个样本文件10000行，每天2个样本文件(2类)，脚本中设置了学习10天的样本文件，即200000个样本，核矩阵的规模是样本数平方，即4*1010个元素(但核矩阵)，假设4字节一个字符，考虑对称性需要大于4*4*1010/2byte=80Gbyte,存储样本时需要的空间较大，成本高，而且处理大规模数据时，存储的反映速度慢。

发明内容

本发明的目的是提供了一种面向多核集群的SMO并行处理方法。

为实现上述目的，本发明提供了一种面向多核集群的SMO并行处理方法，包括：

获取待分类数据的本地问题参数；根据所述本地问题参数获取全局参数；根据所述全局参数给所述本地问题参数赋初始值，并对算法参数赋初始值；

根据所述本地问题参数的初始值，计算所述本地问题参数的本地第一界和本地第二界；根据所述本地第一界和本地第二界，获取所述全局第一界和全局第二界；

在所述全局第一界和全局第二界之差不小于预设的精度时，根据所述算法参数的初始值和所述本地问题参数的初始值迭代计算所述全局第一界对应的第一乘子以及全局第二界对应的第二乘子；其中，每次迭代后多线程更新所述本地问题参数；

在迭代达到预设的迭代次数时，根据本地样本乘子计算待分类数据的本地解，根据所述本地解获取全局解，完成数据分类。

优选地，所有进程创建线程池，读取待分类数据，将所述待分类数据转成liblinear格式。优选地，所述方法还包括：在迭代未达到预设的迭代次数时，继续计算所述本地问题参数，求解本地第一界和本地第二界。

优选地，根据

求得所述第二乘子，根据求得所述第一乘子，其中，

为第二乘子，

为第一乘子，S、η、为中间参数，E_i为本地问题参数，y2为第二样本标签。优选地，所述中间参数s根据公式s=y₁y₂得到，其中，y₁为第一样本标签，y₂第二样本标签。

优选地，所述中间参数η根据公式η=2K(x₁,x₂)-K(x₁,x₁}-K(x₂,x₂)求得，其中，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。

优选地，所述本地问题参数E_i根据公式求得，其中，y_i,y_i为各个样本标签，α_j为乘子，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。

优选地，所述根据所述本地的第一界和本地第二界，获取所述全局第一界和全局第二界还包括：在y1≠y2时，则 $L=\max (0,{\mathrm{\α}}_2^{\mathrm{old}}-{\mathrm{\α}}_1^{\mathrm{old}}),$ $H=\min (C,C+{\mathrm{\α}}_2^{\mathrm{old}}-{\mathrm{\α}}_1^{\mathrm{old}}),$ 在y1=y2时， $L=\max (0,{\mathrm{\α}}_2^{\mathrm{old}}+{\mathrm{\α}}_1^{\mathrm{old}}-C),$ $H=\min (C,{\mathrm{\α}}_2^{\mathrm{old}}+{\mathrm{\α}}_1^{\mathrm{old}}),$ 其中，y1为第一样本标签，y2为第二样本标签，L为乘子α_i的第二界，H为乘子α_i的第一界，

为第二乘子，

为第一乘子，C为惩罚因子。

优选地，所述采用多线程技术更新所述本地问题参数具体包括：根据 $E_i^{\mathrm{new}}=E_i^{\mathrm{old}}+y_1({\mathrm{\α}}_1^{\mathrm{new}}-{\mathrm{\α}}_1^{\mathrm{old}})K(x_1,x_i)+y_2({\mathrm{\α}}_2^{\mathrm{new}}-{\mathrm{\α}}_2^{\mathrm{old}})K(x_2,x_i),$ 多个线程同时更新本地问题参数E_i，其中，

为全局第二乘子，

为全局第一乘子，y₁第一样本标签，y₂为第二样本标签，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。

优选地，根据

求得待分类数据的本地解，根据所述本地解获取全局解，其中，

为本地样本乘子，y_i为样本标签，x_i为第i个样本的特征向量。

SMO（Sequential minimal optimization,最小贯序列方法）是一种简单化的SVM（support vector machine,支持向量机）算法，且适用于处理大规模数据分类问题。它将一个大的QP问题分解为一系列小的QP问题，因此能够快速解决并获得解析解，有效的改善空间和时间复杂度以及解决传统的数据分类时成本高、误码率高以及反应速度慢的问题。

附图说明

图1为本发明实施例面向多核集群的SMO并行处理流程图；

图2为本发明实施例中样本分类示意图；

图3为本发明实施例一提供的面向多核集群的SMO的2类分类流程示意图；

图4为本发明实施例二提供的面向多核集群的SMO的多类分类流程示意图。

具体实施方式

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

图1为本发明实施例面向多核集群的SMO并行处理流程图。其中，执行主体是所有进程。该实施例包括以下步骤：

步骤S101，获取待分类数据的本地问题参数；根据本地问题参数获取全局参数；根据全局参数给本地问题参数赋初始值，并对算法参数赋初始值。

所有进程初始化工作，对算法参数赋初值，将算法中的乘子设定为a_i＝0，中间变量E_i＝-y_i，其中，y_i为各样本标签，E_i为本地问题参数。

${\mathrm{\α}}_i=0\⇔y_{i}f\left(x_i\right)\≥1---\left(1\right)$

$0<{\mathrm{\&alpha;}}_i<C\&DoubleLeftRightArrow;y_{i}f\left(x_i\right)=1---\left(2\right)$

${\mathrm{\&alpha;}}_i=C\&DoubleLeftRightArrow;y_{i}f\left(x_i\right)\&le;1---\left(3\right)$

其中， $f\left(x_i\right)=\underset{j=1}{\overset{L}{\mathrm{\&Sigma;}}}{y}_j{\mathrm{\&alpha;}}_{j}K(x_i,y_j)+b,$ b是分类的阈值。

而经验证，最优解a_i需要满足KKT条件，即满足（1）（2）（3），SMO算法启发式的选择两个a_i进行优化。

根据公式（1）、（2）和（3），将样本数据分为如下五类：

I₀＝{i:0＜α_i＜C};

I₁＝{i:y_i＝+1,α_i＝0};

I₂＝{i:y_i＝-1,α_i＝C};    （4）

I₃＝{i:y_i＝+1,α_i＝C};

I₄＝{i:y_i＝-1,α_i＝0}。

其中，y_i为各个样本标签，标签指的是样本对应的类别，a_i为样本的乘子，C为惩罚因子，代表你想对利群点带来的损失有多少，根据经验，C一般为1。

步骤S102，根据本地问题参数的初始值，计算本地问题参数的本地第一界和本地第二界；根据本地第一界和本地第二界，获取全局第一界和全局第二界全局第一界全局第二界

需要说明的是，在以下实施例中，各字母的含义分别为：本地第一界即本地参数上界以bup表示，本地第二界即本地参数下界以blow表示，全局第一界即全局参数上界以g_bup表示，全局第二界即全局参数下界以g_blow表示。

bup＝min{E_i:i∈I₀∪I₁∪I₂}    （5）

blow＝max{E_i:i∈I₀∪I₃∪I₄}    （6）

g_bup=min bup，假设g_bup所在进程设为P1；

g_blow=max blow，假设g_blow所在进程设为P2。

步骤S103，在全局第一界和全局第二界之差不小于预设的精度时，根据算法参数的初始值和本地问题参数的初始值迭代计算全局第一界对应的第一乘子以及全局第二界对应的第二乘子；其中，每次迭代后多线程更新本地问题参数。

具体地，如果g_bup-g_blow不小于预设的精度e时，分别进行全局第一界对应的第一乘子以及全局第二界对应的第二乘子的计算。

如果g_bup-g_blow小于预设的精度e时，则销毁线程池，结束所有进程。

在一个具体的实施例中，以α1是P1进程g_bup样本所对应的第一乘子，α2是P2进程g_blow样本对应的第二乘子为例，根据算法参数的初始值（a_i＝0，中间变量E_i＝-y_i），循环计算全局参数下界对应的第二乘子和全局参数上界对应的第一乘子

${\mathrm{\&alpha;}}_2^{\mathrm{new}}={\mathrm{\&alpha;}}_2^{\mathrm{old}}-\frac{y_2(E_1^{\mathrm{old}}-E_2^{\mathrm{old}})}{\mathrm{\&eta;}}---\left(7\right)$

${\mathrm{\&alpha;}}_1^{\mathrm{new}}={\mathrm{\&alpha;}}_1^{\mathrm{old}}+s({\mathrm{\&alpha;}}_2^{\mathrm{old}}-{\mathrm{\&alpha;}}_2^{\mathrm{new}})---\left(8\right)$

其中，中间参数的计算公式如下：

s=y₁y₂    （9）

η=2K(x₁,x₂)-K(x₁,x₁}-K(x₂,x₂)    （10）

$E_i=\underset{j=1}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_j{y}_{j}K(x_j,x_i)-y_i---\left(11\right)$

其中，y1即为α1对应的第一样本标签，y2即为α2对应的第二样本标签，K(x_j,x_i)为x_j和x_i的内积函数，y_i,y_i为各个样本标签，α_j为乘子。

在每次迭代后，多线程更新本地问题参数。

$E_i^{\mathrm{new}}=E_i^{\mathrm{old}}+y_1({\mathrm{\&alpha;}}_1^{\mathrm{new}}-{\mathrm{\&alpha;}}_1^{\mathrm{old}})K(x_1,x_i)+y_2({\mathrm{\&alpha;}}_2^{\mathrm{new}}-{\mathrm{\&alpha;}}_2^{\mathrm{old}})K(x_2,x_i)---\left(12\right)$

公式（12）中，

为全局第二乘子，为全局第一乘子，y₁第一样本标签，y₂为第二样本标签，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。多线程同时进行本地问题参数E_i的更新，大大加速数据运算的速度。

可选地，所述根据所述本地的第一界和本地第二界，获取所述全局第一界和全局第二界还包括：在y1≠y2时，则 $L=\max (0,{\mathrm{\&alpha;}}_2^{\mathrm{old}}-{\mathrm{\&alpha;}}_1^{\mathrm{old}}),$ $H=\min (C,C+{\mathrm{\&alpha;}}_2^{\mathrm{old}}-{\mathrm{\&alpha;}}_1^{\mathrm{old}}),$ 在y1=y2时， $L=\max (0,{\mathrm{\&alpha;}}_2^{\mathrm{old}}+{\mathrm{\&alpha;}}_1^{\mathrm{old}}-C),$ $H=\min (C,{\mathrm{\&alpha;}}_2^{\mathrm{old}}+{\mathrm{\&alpha;}}_1^{\mathrm{old}}),$ 其中，y1为第一样本标签，y2为第二样本标签，L为乘子α_i的第二界，H为乘子α_i的第一界，

为第二乘子，

为第一乘子，C为惩罚因子。

步骤S104，在迭代达到预设的迭代次数时，根据本地样本乘子计算待分类数据的本地解，根据本地解获取全局解，完成数据分类。

可选地，在迭代未达到预设的迭代次数时，继续计算所述本地问题参数，求解本地第一界和本地第二界。

$w^{*}=\underset{i=1}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i^{*}{y}_i{x}_i---\left(13\right)$

在迭代达到指定的次数时，根据公式（13）求得所述待分类数据的本地解，根据Allreduce函数，获取全局解。其中，

为本地样本乘子，y_i为样本标签，x_i为第i个样本的特征向量。

可以理解的是，每次选择两个乘子进行优化，迭代产生第一乘子和第二乘子，本地样本乘子是每次优化后所有乘子的集合。

其中，该公式（13）根据以下过程推导而得，对以下推导过程中的公式，不作具体的标号。图2为本发明实施例中样本分类示意图。

假设给定一组数据集合

（xi∈Rn是第i个输入样本向量，yi为第i个样本的类别，L是样本的总数。如下图所示，空心圆点和正方形代表两类训练样本，H是把两类没有错误分开的分类线，H1与H2分别为过各类样本中离分类线最近的点且平行于分类线的直线，假设我们有一个函数g(x)=wx+b，各条线上的样本点设定满足如下条件H1：wx+b=+1；H2：wx+b=-1；H：wx+b=0。H1与H2之间的距离叫做分类间隔margin=2/||w||。SVM算法是寻找一个超平面wxi+b=0，使两个分类样本的几何间隔（margin）最大，而对于正样本点wxi+b>0,负样本点δ=wxi+b<0。

即优化目标为：

$\max \frac{2}{\left|\right|w\left|\right|}$

根据样本数据在H1和H2两侧，满足y_i[(wx_i)+b]-1≥0(i=1,2…L)(L是样本数)

得出初始公式：

$\min \frac{1}{2}{\left|\right|w\left|\right|}^2$

subject to y_i[(wx_i)+b]-1≥0(i=1,2…L)(L是样本数)

需求得公式中的参数w（w是个n维向量）和b，实际上是只需要落在H1和H2上的样本点唯一确定分类函数，即将上公式中的≥转化为=，引入拉格朗日乘子：α

$L(w,b,\mathrm{\&alpha;})=\frac{1}{2}{\left|\right|w\left|\right|}^2-\underset{i=1}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i{y}_i[(w^T{x}_i+b)-1]$

求偏导：

$\frac{\&PartialD;L}{\&PartialD;w}=0\&DoubleRightArrow;w=\underset{i=1}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i{y}_i{x}_i$

$\frac{\&PartialD;L}{\&PartialD;x}=0\&DoubleRightArrow;\underset{i=1}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i{y}_i=0$

数学表示：

$\min W\left(\mathrm{\&alpha;}\right)=\frac{1}{2}\underset{i,j}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i{\mathrm{\&alpha;}}_j{y}_i{y}_j{x}_i{x}_j-\underset{i}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i$

$\mathrm{subject\; to}{\mathrm{\&alpha;}}_i\&GreaterEqual;0,\underset{i=1}{\overset{L}{\mathrm{\&Sigma;}}}{\mathrm{\&alpha;}}_i{y}_i=0$

其中，α有L个，即每一个样本对应一个α，而落在H1和H2上的样本点的α不为0，其他大部分都为0。

因此有求w值转化为求α值，在求得最优的乘子α^*，可由下面的公式求出最优的w^*，即得到公式（13）

图3为本发明实施例一提供的面向多核集群的SMO的2类分类流程示意图。图3包括如下步骤：

步骤S301，所有进程创建线程池（线程处于阻塞状态），读入数据，并计算liblinear变量参数。

步骤S302，所有进程根据自己子问题local参数，求得整个问题的global参数。

步骤S303，所有进程根据整个问题全局参数给自己子问题参数重新赋值。

步骤S304,所有进程处理自己子问题，使同一标签的样本相邻且在原问题排名靠前的样本仍排在前面。

可以将步骤S301-步骤S304具体到如下步骤：

在一个具体的实施例中，将数据从文件读入内存，计算liblinear中parameter和problem结构体的一些参数值。

2）所有进程根据自己子问题local参数，求得整个问题的global参数：

首先求出local参数（本地进程）：nr_class标签数

label标签

count；标签所对应的样本数

进而求出global参数（所有进程）：g_nr_class；标签数

g_label；标签

g_count；标签所对应的样本数

例如如下数据，假如有2个处理器，分别为0处理器和1处理器，将0处理器数据如下：

1  4:1  15:1  23:1  79:1

2  2:1  45:1  61:1  88:1  99:1

1  8:1  25:1  29:1  79:1

将1处理器数据如下：

1  7:1  19:1  22:1  89:1

5  3:1  40:1  60:1  80:1  100:1

5  3:1  42:1  60:1  81:1  100:1

则0进程的本地参数为：

nr_class=2；标签有2个

label=1 2；这2个标签分别为1和2

count=2 1；1标签的样本有2个，2标签的样本有1个

data_label 0 1；1标签记为0，2标签记为1

1进程的本地参数为：

nr_class=2；标签有2个

label=1 5；这2个标签分别为1和5

count=1 2；1标签的样本有1个，5标签的样本有2个

全局参数为：

g_nr_class=3；综合0和1处理器，标签有3个

g_label=1 2 5；这3个标签分别为1、2和5

g_count=3 1 2；1标签对应的样本有3个，2标签对应的样本有1个，5标签对应的样本有2个

3）所有进程根据整个问题全局参数给自己子问题参数重新赋值。

子问题的需赋值的参数：l_g_count；子问题标签的个数

l_g_start;0,第1个标签的样本数，第1和第2标签样本总数,…，第1至第n-1标签的样本总数

l_g_perm；排序需要的中间变量

以如上数据为例，0进程的l_g_count=2 1 0

1进程的l_g_count=1 0 2

4）所有进程处理自己子问题，使同一标签的样本相邻且在原问题中排名靠前的样本仍排在前面

排序问题：实际存储没变，用指针数组表明顺序

如0处理器排序前数据如下：

1  4:1  15:1  23:1  79:1

2  2:1  45:1  61:1  88:1  99:1

1  8:1  25:1  29:1  79:1

排序后，指针所指的顺序：

1  4:1  15:1  23:1  79:1

1  8:1  25:1  29:1  79:1

2  2:1  45:1  61:1  88:1  99:1

步骤S305，所有进程初始化SMO算法参数：乘子a,中间参数E，I。

步骤S306，所有进程计算并广播本地参数的上界bup和本地参数的下界blow，求全局参数的上界g_bup和全局参数的下界g_blow。

步骤S307，在g_bup与g_blow之差小于指定精度e时，执行步骤S315；在g_bup与g_blow之差不小于指定精度e时，执行步骤S308。

步骤S308，P1进程计算α1(α1为g_bup对应的乘子），P2进程计算α2(α2为g_blow对应的乘子）；

步骤S309，P1和P2进程更新α1，α2；I1(I1与g_bup对应），I2(I2与g_bup对应）

步骤S310，P1和P2进程广播α1，α2，x1，x2，y1，y2；

步骤S311，每个进程从线程池中唤醒k个线程；

步骤S312,线程进行E_i更新；

步骤S313，每个进程将完成计算任务的k个线程休眠;

步骤S314，判断是否达到最大迭代次数，在达到最大迭代次数时，执行步骤S315。

步骤S315，销毁线程池，求解分类结果，退出。

图4为本发明实施例二提供的面向多核集群的SMO的多类分类流程示意图。多类分类时，假如有n个类:1,2,3……n。先将第1类作为正类，其它类别作为负类，利用如上的2类分类方法进行分类；然后将第2类作为正类，其它类别作为负类，利用同样的方法进行分类；这样下去一直可以训练出n个分类器。当对某一文本进行分类时，遍历如上分类器，直至得出分类结果，如果遍历n个之后仍然无法确定文本属于哪一类，则将分在其它类别中。

步骤S401，所有进程创建线程池（线程处于阻塞状态），读入数据，转成liblinear格式，求得本地问题参数，并将本地问题的参数广播给所有进程。

步骤S402，所有进程根据问题的全局参数给本地问题参数赋值，对样本数据做预处理（按标签和出现先后顺序排序），给算法参数赋初始值。

此时，算法参数的初始值包括设置a_i＝0，E_i＝-y_i。

步骤S403，所有进程计算bup和blow值。

步骤S404，所有进程利用Allreduce函数计算g_bup和g_blow值，主进程判断g_bup-g_blow<e,在成立时转到步骤S410，在不成立时，记录g_bup和g_blow所在的进程P1、P2，假设分别为2（P1）、3（P2）进程

步骤S405，2（P1）进程计算α1（α1为g_bup所对应的乘子）并进行其对应的α和I的更新，3（P2）进程计算α2（α2为g_blow所对应的乘子）并进行其对应的α和I的更新。

步骤S406，2（P1）将α1、x1、y1的值广播给所有进程，3（P2）将α2、x2、y2的值广播给所有进程。

步骤S407，每个进程从线程池中唤醒k个线程，进行算法参数Ei的更新。

步骤S408，每个进程将完成计算任务的k个线程休眠。

步骤S409，主进程判断是否达到最大迭代精度，如没有达到，返回到步骤S403继续运算，否则继续

步骤S410,所有进程计算本地w值（本地解）

步骤S411，所有进程利用Allreduce求得全局w值（全局解），销毁线程池，结束。

综上，本发明实施例实现了分类样本的分布式存储以及并行化分类，并且在分类过程中，数据分类成本低、误码率低、反映速度快，大大的提升了数据的处理速度。

专业人员应该还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

结合本文中所公开的实施例描述的方法或算法的步骤可以用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器（RAM）、内存、只读存储器（ROM）、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (10)

1.一种面向多核集群的SMO并行处理方法，其特征在于，所述方法包括：

获取待分类数据的本地问题参数；根据所述本地问题参数获取全局参数；根据所述全局参数给所述本地问题参数赋初始值，并对算法参数赋初始值；

根据所述本地问题参数的初始值，计算所述本地问题参数的本地第一界和本地第二界；根据所述本地第一界和本地第二界，获取所述全局第一界和全局第二界；

在所述全局第一界和全局第二界之差不小于预设的精度时，根据所述算法参数的初始值和所述本地问题参数的初始值迭代计算所述全局第一界对应的第一乘子以及全局第二界对应的第二乘子；其中，每次迭代后多线程更新所述本地问题参数；

在迭代达到预设的迭代次数时，根据本地样本乘子计算待分类数据的本地解，根据所述本地解获取全局解，完成数据分类。

2.如权利要求1所述的面向多核集群的SMO并行处理方法，其特征在于，所述方法之前包括：所有进程创建线程池，读取待分类数据，将所述待分类数据转成liblinear格式。

3.如权利要求1所述的面向多核集群的SMO并行处理方法，其特征在于，所述方法还包括：在迭代未达到预设的迭代次数时，继续计算所述本地问题参数，求解本地第一界和本地第二界。

4.如权利要求1所述的面向多核集群的SMO并行处理方法，其特征在于，根据 ${\mathrm{\&alpha;}}_2^{\mathrm{new}}={\mathrm{\&alpha;}}_2^{\mathrm{old}}-\frac{y_2(E_1^{\mathrm{old}}-E_2^{\mathrm{old}})}{\mathrm{\&eta;}}$ 求得所述第二乘子，根据 ${\mathrm{\&alpha;}}_1^{\mathrm{new}}={\mathrm{\&alpha;}}_1^{\mathrm{old}}+s({\mathrm{\&alpha;}}_2^{\mathrm{old}}-{\mathrm{\&alpha;}}_2^{\mathrm{new}})$ 求得所述第一乘子，其中，

为第二乘子，

为第一乘子，S、η、为中间参数，E_i为本地问题参数，y2为第二样本标签。

5.如权利要求4所述的面向多核集群的SMO并行处理方法，其特征在于，所述中间参数s根据公式s=y₁y₂得到，其中，y₁为第一样本标签，y₂第二样本标签。

6.如权利要求4所述的面向多核集群的SMO并行处理方法，其特征在于，所述中间参数η根据公式η=2K(x₁,x₂)-K(x₁,x₁}-K(x₂,x₂)求得，其中，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。

7.如权利要求4所述的面向多核集群的SMO并行处理方法，其特征在于，所述本地问题参数E_i根据公式

求得，其中，y_i,y_i为各个样本标签，α_j为乘子，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。

8.如权利要求1所述的面向多核集群的SMO并行处理方法，其特征在于，所述根据所述本地的第一界和本地第二界，获取所述全局第一界和全局第二界还包括：在y1≠y2时，则 $L=\max (0,{\mathrm{\&alpha;}}_2^{\mathrm{old}}-{\mathrm{\&alpha;}}_1^{\mathrm{old}}),$ $H=\min (C,C+{\mathrm{\&alpha;}}_2^{\mathrm{old}}-{\mathrm{\&alpha;}}_1^{\mathrm{old}}),$ 在y1=y2时， $L=\max (0,{\mathrm{\&alpha;}}_2^{\mathrm{old}}+{\mathrm{\&alpha;}}_1^{\mathrm{old}}-C),$ $H=\min (C,{\mathrm{\&alpha;}}_2^{\mathrm{old}}+{\mathrm{\&alpha;}}_1^{\mathrm{old}}),$ 其中，y1为第一样本标签，y2为第二样本标签，L为乘子α_i的第二界，H为乘子α_i的第一界，为第二乘子，

为第一乘子，C为惩罚因子。

9.如权利要求1所述的面向多核集群的SMO并行处理方法，其特征在于，所述采用多线程技术更新所述本地问题参数具体包括：根据 $E_i^{\mathrm{new}}=E_i^{\mathrm{old}}+y_1({\mathrm{\&alpha;}}_1^{\mathrm{new}}-{\mathrm{\&alpha;}}_1^{\mathrm{old}})K(x_1,x_i)+y_2({\mathrm{\&alpha;}}_2^{\mathrm{new}}-{\mathrm{\&alpha;}}_2^{\mathrm{old}})K(x_2,x_i),$ 多个线程同时更新本地问题参数E_i；其中，

为全局第二乘子，

为全局第一乘子，y₁第一样本标签，y₂为第二样本标签，K(x_j,x_i)为x_j和x_i的内积函数，x_j为第j个样本的特征向量，x_i为第i个样本的特征向量。

10.如权利要求1所述的面向多核集群的SMO并行处理方法，其特征在于，根据

求得待分类数据的本地解，根据所述本地解获取全局解，其中，为本地样本乘子，y_i为样本标签，x_i为第i个样本的特征向量。

Images