专利摘要

一种可伸缩的自适应多核分类方法，涉及人工智能领域，特别是数据挖掘技术。预处理阶段，得到多核矩阵；建模阶段，构建一个簇相关的多核分类器；参数学习阶段，在统一的框架内对分类器参数及多组多核权值参数进行优化；数据分类阶段，对待分类的样本，首先确定其属于哪一个簇，再利用学习好的分类器进行数据分类。本发明通过引入中间表达“簇”挖掘复杂数据集的类间相关性和类内多样性，建立了簇相关的自适应和可伸缩多核分类器，并通过迭代的方式在统一的学习框架下优化分类器参数和多组多核权值参数。面对类别繁多且特征表现复杂的数据分类问题，解决类间相关性和类内多样性带来的数据混叠问题，提高了分类准确率，且分类效果更为鲁棒。

权利要求

1、一种可伸缩的自适应多核分类方法，其特征在于，该方法包括以下步骤：

1)预处理阶段：利用样本的特征对所有训练样本进行无监督聚类，将相关性强的样本聚到同一个簇中，并计算训练集中所有样本对的多个核函数值，得到多核矩阵；

2)建模阶段：构建簇相关的自适应多核分类器模型；

3)学习阶段：对多核分类器的参数及多组多核权值参数进行优化；

4)数据分类阶段：利用学习好的多核分类器对待分类的样本进行数据分类。

2、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，所述预处理阶段包括对提取特征后的数据进行无监督聚类，其聚类方法采用K均值聚类算法或均值漂移算法或概率潜在语义分析算法。

3、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，所述预处理阶段计算训练集中所有样本对的多个核函数值，所使用的基本核函数包含通用的高斯、多项式或Sigmoid核函数，或者空间金字塔核函数、近邻分布核函数。

4、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，所述建模阶段为同一个簇内的样本赋予相同的多核权值，而对不同的簇赋予不同的多核权值，从而构建簇相关的多核分类器。

5、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，在所述建模阶段所有数据聚成唯一的一个簇时，所述簇相关的自适应多核分类模型回归到传统的多核分类模型；当每个簇只有一个训练样本时，所述簇相关的自适应多核分类模型等同于单样本的多核分类模型。

6、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，所述学习阶段将多核分类器参数及多组多核权值参数统一进行优化，通过求解最大最小的鞍点问题来进行学习，从而得到判别函数。

7、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，所述学习阶段中求解最大最小的鞍点问题包括如下步骤：

31)给定自适应多核权值参数，用支持向量机求解方法进学习分类器参数；

32)给定分类器参数，用二次规划来学习自适应多核权值参数；

33)迭代执行31)步骤和32)步骤，直至满足迭代的终止条件。

8、根据权利要求7所述的可伸缩的自适应多核分类方法，其特征在于，所述迭代终止条件包括连续两次迭代参数的变化阈值、迭代次数上限。

9、根据权利要求1所述的可伸缩的自适应多核分类方法，其特征在于，所述数据分类阶段包括如下步骤：

41)利用无监督聚类判断待分类数据所属簇的编号；

42)计算待分类数据对所有类别对应的判别函数的响应值，选出响应值中的最大值所对应的类别作为该待分类数据所属的数据类别。

说明书

技术领域

本发明涉及一种数据分类方法，特别是关于一种可伸缩的自适应多核分类方法，属于人工智能领域，具体属于数据挖掘技术领域。

背景技术

核方法(Kernel Methods)是目前广为流行的数据分类方法，在很多领域都被广泛的应用。当数据分类任务比较简单，使用基于单个核函数的传统的支持向量机(Support Vector Machine，SVM)能够在预先选定合适的核函数的情况下，通过学习分类器参数来有效地进行数据分类。但在数据类别繁多且特征分布复杂的数据集中，相同类别的不同实例间存在特征表现的多样性，而不同类别的实例间存在特征相关性。如图1所示，其中左框内的六幅图像是属于“桥”这个类别的不同样例。从图1中可以看到，即使属于同一个类别，不同实例也存在不同的视觉外观，从而在特征属性上有较大差异。例如，第一行的两幅图更倾向用“形状”特征对桥进行刻画；中间一行的两幅石桥更倾向用“纹理”特征；最下面一行的两幅更倾向用“颜色”和“形状”来描述。因此，同一类别的图像存在视觉特征的多样性，称之为“类内多样性(Intra-class diversity)”。再看图1中最右边的两幅图像，右上是属于“建筑物”这个类别的图像，右下是属于“城市夜景”这个类别的图像。可以看到不同类别的图像也有可能在某些特征属性上具有一定的相似性。例如石桥和建筑物在“形状”和“纹理”上有一定的相似性；而城市夜景和桥的夜景在颜色上有一定的相似性。这种不同类的样本在特征上的相似性称为“类间相关性(Inter-class correlation)”。因此，在进行图像分类时，需要考虑到类内多样性和类间相关性，并需从不同的侧面对图像类别进行描述与刻画。而当所有的图像都使用相同的特征集来进行描述时，一个好的分类方法应对不同类别的图像使用不同的特征权重。显然，在这种情况下，使用单一的核函数方法对所有的特征属性等权重看待，忽略了某些属性的特殊性，因此分类性能较差。

基于多个支持向量机融合的方法通过分别训练多个基于不同核函数的支持向量机，再对训练好的多个支持向量机进行加权融合构成最终的分类器。该方法比基于单核的支持向量机的分类性能更好。但由于需要分别学习多个支持向量机的参数，且这些参数和融合时的权值不能在统一的框架下进行优化，因此不仅训练效率较低，而且不能获得全局最优的参数组合。在处理较为复杂的分类任务时，分类性能较差。

基于多核的分类方法(Multiple Kernel Learning)通过学习多个核函数的最优权值将数据映射到更可分的特征空间中，并在统一的框架下对分类器的参数及多核权值参数进行学习，通过凸规划可获得全局最优解，从而可以获得比基于单一核函数的支持向量机或者多个支持向量机融合的分类方法更好的分类性能。然而，由于其对所有的数据采用全局统一的加权策略，在面对类别繁多且数据分布复杂的任务时，很难有效地训练一个泛化性强的决策函数，从而导致仍然不能获得较好的分类性能。

在申请号为00808062.3、名称为“使用多个支持向量机从多个数据组中提升知识发现”中国专利申请中，提出在多个数据组中采用多个支持向量机的分类方法。该方法强调多个基于单个核函数的支持向量机的使用，需要首先分别在多个数据组中依次训练多个支持向量机，再用训练好的多个支持向量机测试其对应数据组的测试数据，比较其多个支持向量机的测试输出以便决定哪一个测试输出表示一个最佳解。本发明与该方法的不同点：在本发明中，不是对多个基于单核的支持向量机分别进行训练及测试比较最优解，而是将多个核函数引入同一个自适应多核分类器中，只需对唯一的分类器进行训练，不仅提高分类准确率，同时提高训练效率。

从2004年开始，机器学习领域出现对多核学习的研究，并用于数据分类。此类研究通过核函数组合的方式(常用的权值约束是所有核函数权值之和为1)，隐式地将数据映射到更可分的特征空间进行分类处理。论文Multiple kernellearning，conic duality，and the SMO algorithm(F.R.Bach，G.R.G.Lanckriet，andM.I.Jordan的论文“多核学习，圆锥对偶及顺序最小化优化算法”，发表于2004年7月4日的国际机器学习会议ICML)提出了一种改进的顺序最小的优化算法提高求解多核学习问题的效率；论文Large scale multiple kernel learning(S.Sonnenburg，G.Raetsch，C.Schaefer，B.Scholkopf.的论文“大规模的多核学习”，2006年7月发表于机器学习研究杂志Journal of Machine Learning Research)采用将多核学习问题转化为一个半无限线性规划问题进行求解，可适用于大规模的多核学习问题；论文More Efficiency in Multiple Kernel Learning(ARakotomamonjy，F Bach，S Canu，Y Grandvalet的论文“更有效的多核学习”，2007年6月20日发表于国际机器学习会议ICML)提出用即约梯度下降法对多核权值进行快速优化。以上研究者虽然提出多种不同的方法对多核权值进行优化，但仍然是对多个核函数采用全局统一的加权策略。本发明与这些方法的不同点：在本发明中，采用自适应的多核权值策略，其多核权值不仅与核函数有关，而且与样本相关。使得对特征表现差异较大的样本采用不同的多核加权策略，以提升处理类别繁多且分布复杂的数据分类性能。

在专利申请号为200710177097.3、名称为“一种多核支持向量机分类方法”的中国专利申请中，提出通过多个核函数来提高支持向量机处理复杂数据的能力。该方法中分类器采用唯一的一组多核权值，即多核权值与样本完全独立。本发明与该方法的不同点：在本发明中，分类器不是采用完全相同的多核权值对所有数据进行分类处理，而是采取多核权值与样本相关的策略，自适应的学习多组多核权值。使得分类器面对不同复杂程度的数据时均保持较高的数据分类性能。

发明内容

本发明的目的在于提供一种可伸缩的自适应多核分类方法。

本发明要解决的技术问题是：面对类别繁多且特征表现复杂的数据分类问题，如何从不同侧面和不同粒度对数据类别进行建模，以解决类间相关性和类内多样性带来的数据混叠问题，并有效地提高分类准确性。

为了实现上述发明目的，本发明提供了一种可伸缩的自适应多核分类方法，其中自适应是指分类器采用簇相关多核加权策略；可伸缩是指在一定情况下，本发明的多核分类方法可转化为传统的多核分类方法或基于标本的多核分类方法。

本发明包括以下步骤：

1)预处理阶段：利用特征对所有训练样本进行无监督聚类，将相似性大的的样本聚类到同一个“簇”中，并计算训练集中所有样本对的多个核函数值，得到多核矩阵；

2)建模阶段：构建一个簇相关的自适应多核分类模型；

3)参数学习阶段：对多核分类器的参数及多组多核权值参数进行统一优化；

4)数据分类阶段：对待分类的样本，首先确定其属于哪一个簇，再利用学习好的分类器进行数据分类。

所述预处理阶段包括两个步骤：无监督聚类及计算多个核函数矩阵。

(1)利用特征对训练集中的数据进行无监督聚类，将相似性大的样本聚到同一个簇中，并记录每个样本对应的簇的编号。由于类间相关性和类内多样性造成的数据混叠现象，使得相同类别的样本由于特征表现的差异可能被分到不同的簇；不同类别的样本由于特征相关性强也可能被分到同一个簇。簇的数目可通过实验进行选择。本发明的聚类方法可采用多种无监督聚类方法，包含且不限于K-means(k均值聚类算法)、Mean Shift(均值漂移算法)或pLSA(概率潜在语义分析算法)。

(2)选择不同的核函数，分别计算其训练集中所有样本对的核函数值，最终得到多个核函数矩阵。本发明中可采用多种核函数来作为基本核函数，包含且不限于通用的核函数，例如高斯核函数(Gaussian kernel)、多项式核函数(polynomial kernel)、Sigmoid核函数(Sigmoid kernel)等；或者领域知识相关的核函数，例如多媒体领域中的空间金字塔核函数(Spatial Pyramid Kernel，SPK)、近邻分布核函数(Proximity Distribution Kernel，PDK)等。不同的核函数还可以选择不同的参数，例如高斯核函数中不同的宽度σ。同时，在计算样本对的核函数值时，可以使用样本的所有特征，也可以使用其部分特征，例如在多媒体领域分别计算图像的颜色、纹理或形状特征对应的核函数的值。

所述建模阶段为同一个簇内的样本赋予相同的多核权值，而对不同的簇赋予不同的多核权值，从而构建对簇相关的多核分类器。当所有数据聚成唯一的一个簇时，所述簇相关的自适应多核分类模型回归到传统的多核分类模型；当每个簇只有一个训练样本时，所述簇相关的自适应多核分类模型等同于单样本的多核分类模型。

所述参数学习阶段将分类器参数及多组多核权值参数放在统一的框架中，通过求解一个最大最小的鞍点问题来进行学习，从而得到类别特定的判别函数。

所述求解最大最小的鞍点问题包括如下步骤：

31)给定自适应多核权值参数，用已有的支持向量机求解方法学习分类器参数；

32)给定分类器参数，用二次规划来学习自适应多核权值参数；

33)迭代执行31)步骤和32)步骤，直至满足迭代的终止条件。

所述参数学习阶段的迭代的终止条件包括且不限于连续两次迭代参数的变化阈值、迭代次数上限。

所述数据分类阶段包括如下步骤：

41)利用无监督聚类判断待分类数据所属簇的编号；

42)计算待分类数据对所有类别对应的判别函数的响应值，选出响应值中的最大值所对应的类别为该待分类数据所属的数据类别。

本发明的优点包括：

(1)引入中间表达“簇”挖掘复杂数据集的类间相关性和类内多样性。

(2)建立了簇相关的多核分类模型，该分类模型具有自适应及可伸缩的特性。其中自适应体现在该分类器为每一个簇内的样本学习一组最佳的多核权值，其多核权值参数局部相关(非全局统一)；可伸缩体现在随着簇的数目的变化，本发明的多核分类模型可以转化为传统的多核分类模型和基于标本的多核分类模型。

(3)在统一的学习框架下优化分类器参数和多组多核权值参数。

本发明的有益效果：利用本发明所提供的可伸缩的自适应多核分类方法，面对类别繁多且特征表现复杂的数据分类问题，能较好的解决类间相关性和类内多样性带来的数据混叠问题，提高了分类准确率，而且分类效果更为鲁棒。

附图说明

图1是本发明所提到的类内相关性和类间相似性的示意图；

图2是按照本发明的一个实施方式的工作流程图；

图3是按照本发明的一个实施方式的可伸缩的自适应多核分类模型图；

图4是按照本发明的一个实施方式的自适应多核分类器的判别函数的参数学习流程图；

图5是应用本发明所述分类方法到Caltech256数据集上的分类结果。

具体实施方式

下面结合附图和具体实施例对本发明进一步说明。

图2是按照本发明的一个实施方式的工作流程图。利用本发明解决复杂图像分类问题，以Caltech256图像数据集为例，该数据集包含257个类别的图像数据，其中每类图像包含80幅以上的图像样本。在实施过程中，每类选择30个样本作为训练和校正，剩余样本用于测试。在所有图像样本进行颜色、纹理、形状等特征提取后，利用本发明实现图像分类的步骤如下(工作流程图见图2)：

步骤1、预处理阶段

采用PLSA(概率潜在语义分析)方法对特征提取后的图像数据进行启发式的无监督聚类，将视觉相关性较强的图像聚到同一个簇中，并记录每副图像对应的簇的编号。相同类别的图像由于视觉表现的差异可能被分到不同的簇；不同类别的图像由于视觉相关性强也可能被分到同一个簇。通过校正实验，选择最佳的簇的数目为600。本实施例将在后面的步骤中进一步为每个簇学习相应的多核权值参数，并用于构建图像类别的分类器。

按照本发明的一个具体实施方式，采用三种与图像领域知识相关的核函数：空间金字塔核函数(SPK)、近似分布核函数(PDK)、多分辨率立方图核(multi-resolution histogram kernel)。分别计算训练集中所有样本对的如上三种核函数值，构建成多个核函数矩阵。

步骤2、建模阶段

构建可伸缩的自适应多核分类模型。图3是按照本发明的一个实施方式的可伸缩的自适应多核分类模型图。

图3的左侧是传统的多核分类器模型，包括输入数据(即待分类样本)、多核模型(统一的多核组合权值)、支持向量集合(来自于全体训练样本)，以及判别函数f_MKL(*)。其中支持向量是SVM中对分类起关键作用的样本；而判别函数f_MKL(*)用于计算待分类样本属于某个类别的响应(Score)，通过选择响应值最大所对应的类别为该样本所属的类别。传统多核分类器模型的基本分类流程如下：输入类别未知的待分类样本，其特征被输入到具有统一多核权值的多核模型中，并与来自全体训练样本的支持向量进行比对，最后通过判别函数f_MKL(*)来输出该样本所属的类别。

图3的右侧是基于标本的多核分类器模型，包括输入数据(即待分类样本)、多核模型(与标本相关的多核组合，即多个核函数的加权组合与每个训练样本相关，不同的训练样本有不同的多核权值)、支持向量(即每个训练样本都是支持向量，故称为标本)，以及判别函数f_PS-MKL(*)。其基本分类流程如下：输入类别未知的待分类样本，其特征被输入到不同标本对应的多核模型中，并分别进行比对，最后通过判别函数f_PS-MKL(*)来综合不同标本的比对结果后输出该样本所属的类别。

图3的中间是本发明的自适应多核分类器模型，包括输入数据(即待分类样本)、多核模型(簇相关的多核组合，即同一簇内所有图像赋予相同的多核权值而不同簇图像采用不同的多核权值)、支持向量集合(不同簇有不同的支持向量集合，分别来自于该簇的训练样本)，以及判别函数f_AMKL(*)。其基本分类流程如下：输入类别未知的待分类样本，其特征被输入到不同簇的多核模型中，并与来自每个簇的支持向量分别进行比对，最后通过判别函数f_AMKL(*)来综合不同簇的比对结果后输出该样本所属的类别。

因此，按照本发明的一个具体实施方式，多核权值不仅与步骤1中的三种核函数形式有关，同时与核函数的图像对所属的簇的编号有关，其多核组合形式表达如下：

K(xi,xj)=Σm=13βmg(xi)βmg(xj)Km(xi,xj)]]>

其中K₁(x_i，x_j)、K₂(x_i，x_j)、K₃(x_i，x_j)分别为步骤1中选择的三种基本核函数， 为自适应多核权值，g(x_i)为用于训练的图像x_i所属的簇的编号。

步骤3、学习阶段

通过参数联合学习的方式对分类器参数α_i及多组多核权值参数 进行优化，按照本发明的一个具体实施方式，将此参数学习转化为一个最大最小的鞍点问题，包括优化分类器参数及多组多核权值参数、计算给定类别的判决函数。其优化过程如下：

(1)优化分类器参数及多组多核权值参数

首先，给定自适应多核权值参数β，求解分类器参数α：

minαJ,where]]>

J=12Σi=1NΣj=1NαiαjyiyjK(xi,xj)-Σi=1Nαi,---(1)]]>

s.t.Σi=1Nαiyi=0,0≤αi≤Cfor∀i,]]>

其中K(xi,xj)=Σm=1Mβmg(xi)βmg(xj)Km(xi,xj).]]>给定自适应多核权值β，最小化目标函数J求解α等价于标准的SVM对偶问题，可以用已有的SVM解决方法进行求解。

其次，给定分类器参数α，求解自适应多核权值参数β：

为了便于求解β，目标函数可以重写为：

J=Σg=1GΣg,=1GΣm=1Mβmgβmg,Smgg,(α)-Σi=1Nαi,---(2)]]>

其中Smgg′(α)=12Σ{i|xi∈Cg}Σ{j|xj∈Cg′}αiyiαjyjKm(xi,xj),]]>C_g表示簇编号为g。

相应地，给定分类器参数α，最大化目标函数J求解β简化为如下形式：

maxΣg=1GΣg,=1GΣm=1Mβmgβmg,Smgg,(α)-Σi=1Nαi,]]>

s.t.βmg≥0,Σm=1Mβmg=1for∀g,∀m.---(3)]]>

上述最大化目标函数求解自适应多核权值参数β可以用二次规划进行求解。

按照本发明的一个具体实施方式，设置迭代的终止条件可采用且不限于：连续两次迭代参数的变化阈值、迭代次数。在迭代满足终止条件后，分类器参数α及自适应多核权值β优化完成。最终二值分类器的判别函数如下：

f(x)=Σi=1Nαi*yiΣm=1Mβmg(xi)*βmg(x)*Km(xi,x)+b*---(4)]]>

其中 为优化后的分类器参数， 为优化后的自适应多核权值，b^*为偏置项。

参数联合学习的流程图见图4，参数优化的具体过程如下：

(a)初始化自适应多核权值参数：

设置βmg=1/3,]]>g＝1，...，600，m＝1，2，3

(b)最小化目标函数优化分类器参数：

利用多核组合形式K(xi,xj)=Σm=13βmg(xi)βmg(xj)Km(xi,xj),]]>用标准的SVM方法求解分类器参数α.

(c)最大化目标函数优化自适应多核权值参数：

求解自适应多核权值β，用二次规划方法求解如下问题：

maxΣg=1600Σg,=1600Σm=13βmgβmg,Smgg,(α)-Σi=1Nαi,]]>

s.t.βmg≥0,Σm=13βmg=1for∀g,∀m.---(5)]]>

(d)参数更新：

更新分类器参数及自适应多核权值参数。

(e)判断其终止条件(迭代次数＝20)是否满足：

若满足，结束参数优化步骤，进入(2)计算给定类别的判别函数

若不满足，用优化后的参数更新目标函数，进入(b)继续优化分类器参数。

(2)计算给定类别的判别函数：

(a)保存最佳的分类器参数α及多核权值参数β：

αi*=αi,βmg*=βmg,for∀i,∀g,∀m---(6)]]>

(b)计算判别函数的偏置b：

b*=yj-Σi=1Nαi*yiΣm=1Mβmg(xi)*βmg(xj)*Km(xi,xj),∀j∈{j|αj*>0}---(7)]]>

(c)对给定类别的二值分类器的判决函数如下：

f(x)=Σi=1Nαi*yiΣm=13βmg(xi)*βmg(x)*Km(xi,x)+b*---(8)]]>

步骤4、数据分类阶段

具体包括如下两部分：

(1)首先通过步骤1中的基于PLSA的无监督聚类方法，判断待分类图像x所属的簇的编号g(x)。

(2)计算待分类图像x对步骤3中学习得到的给定图像类别的判别函数f(x)的响应。顺序求得所有257个图像类别的判别函数的响应值，选取响应值中的最大值所对应的类别作为该待分类图像所属的图像类别。

图5给出了应用本发明的多核分类方法在Caltech256数据集上的分类结果，横轴是每个类别选取的图像数目，纵轴是平均识别准确率。当对每个类别选取50幅图像作为训练，剩下的图像作为测试。通过本发明的自适应多核分类方法获得了74.4％的分类准确率，比目前报道出的最好的分类准确率提高了7％左右。

上述仅为本发明的较佳实施例，并不用来限定本发明的实施范围。也就是说，任何依照本发明的权利要求范围所做的同等变化与修改，皆为本发明的权利要求范围所涵盖。

一种可伸缩的自适应多核分类方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。