基于多示例学习框架的文本分类算法

徐建国，肖海峰，赵 华

(山东科技大学 计算机科学与工程学院，山东 青岛 266590)

0 引 言

SVM(support vector machine)算法在处理文本分类问题时有着较好的应用。张华鑫等[1]通过对比实验发现在处理短文本时，SVM使用多项式核函数的分类准确度普遍高于采用KNN(K-nearest neighbor)算法的分类准确率。董放等[2]利用SVM模型提出了一种基于时间序列的新兴技术预测方法，通过对文本摘要的分类，预测了技术驱动力新兴技术发展趋势。上述SVM算法在处理短文本内容时有着较好的表现，但是在处理较大规模文本分类问题时，分类的准确率存在不足。传统的机器学习算法在处理具有特殊结构的本文时，已经不能满足对准确率的要求。针对以上问题，本文从一个新的解决文本分类问题的角度，综合考虑文本的特征结构，充分利用多示例学习框架的优点，结合支持向量机中的多类分类算法，对具有特殊结构的文本分类问题展开研究，最后通过实验验证本文提出算法的有效性。

1 相关研究

多示例学习(multi instance learning，MIL)源于20世纪90年代Dietterich等在研究药物分子活性(drug activity prediction)检测问题时提出的一种新的学习方法[3]。多示例学习方法作为机器学习中从监督式学习演变出的一种新方法，自提出以来，一直是学者研究的热点之一[4-6]。在多示例学习框架中，训练集中的每个正包被定义为一个有标记的对象，负包由没有标记的示例组成，训练器对包中的示例进行学习，从而对示例进行预测。将所有正包的示例视为正示例，如果一个正包中的所有示例都被判断为负，那么则将该包中具有最大函数决策值的示例标记为正；支持向量机再对这些被标记为正的示例和所有负包中的示例不断进行训练和标记，直到训练集中所有示例的类别标签不再发生变化[7]，多示例学习的目标是预测新的包，这些包是事先没有标记的标签。

多示例学习方法的应用场景和应用领域非常丰富，突出表现是在目标识别与图像检索领域[8]。由于多示例学习能够基于图像的局部内容，对字块进行学习，而不是整个图片，对图像进行分部处理，将图像不同的部分作为示例，因此多示例学习能够有效处理图片的二义性。文献[9]利用在线多示例目标跟踪算法，根据数据的特性在深度图中提取多尺度特征，利用多示例学习策略将多尺度特征融合；文献[10]将图像看作是多示例包，将包中的示例训练成特征空间，利用训练的包构造字典，提出基于稀疏表示的分类方法，有效地利用多示例学习框架解决了图像分类问题。

多示例学习的优点是可以通过多示例的方法充分得到目标对象的多特征，而不是对象的单一特征[11]。因此能够更加精确地描述目标对象的属性，提高分类的准确性，比如图像识别、文本分类。现实情况下，我们遇到的许多文本都是有特定结构的，例如科技通报文章、微博数据、网页评论、网络舆情数据等。因此，在文本识别中可以运用多示例学习的框架，将整篇文本作为一个由多个示例组成的包，将文本内容分割映射为多个示例，每个文本对应一个分类主题。

基于以上研究基础，本文将使用多示例学习框架，结合支持向量机算法对采集的新闻文本数据集进行分类研究。将每个文本作为一个示例包，每个文本中的标题和正文作为包的两个示例。将这两个具有标记的样本称为正包，同时将包映射到高维特征空间中，然后构建基于一类分类的多类分类支持向量机算法，利用高斯核函数训练分类器，最终实现对实验数据集文本内容的自动分类。

2 基于多示例学习框架的文本分类算法

2.1 定义多示例学习

给定集合X表示示例空间，其中的一个数据集为 {(x1,y1),…,(xi,yi),…(xn,yn)}，xi={xi1,…,xij,…xi,ni}∈X，n是训练集中包的个数，xij∈Rn,j=1,…,li;i=1,…,l， 输出yi是对xi的类别标记，xi∈{-1,1}，yi∈{-1,1},i=1,…l， 目的是根据这个规则建立分类器，从而实现对为标记包的分类。其中xij∈X， 是一个示例， {xij1,…xijl,…xijk} 中xijk是示例xij中的第k个特征值，ni表示的是包Xi中示例的个数，k表示的是示例中特征值的个数。如果存在f∈(1,…,ni)， 使得定义的示例xij是一个正示例，那么包Xi就是一个正包，即yi=+1， 否则，yi=-1[12]。通过上述定义可知，多示例分类问题就是通过已经标记过的正包和负包，然后构建分类器来预测一个新的包是正包还是负包[4]。图1表示空间R2中多示例的分类情况，其中的每一个圈表示一个包，“”和“”表示包中的示例；用“”表示的示例视作正包，用“”表示的示例视作负包。需要解决的问题是，预测平面上的集合是正包还是负包。

图1 多示例学习两类分类

以图像分类为例，我们希望可以根据图像看见的内容了解图像所属的目标类。例如，目标类可能是“海滩”，其中的图像包含“沙子”和“水”。在多示例学习中，此图像被描述为包X={X1,…,XN} 每个Xi是从图像中相应的第i个区域提取的特征向量(称为示例),N是分割图像的总区域(实例)。如果包中包含“沙子”区域示例和“水”区域示例，则将包标记为正(“海滩”)，否则为负图像。

2.2 支持向量机文本分类方法

本文运用支持向量机算法构建分类器对文本进行分类。SVM本质上是基于统计学习理论的机器学习方法，被广泛应用于函数估计(回归)、模式识别(分类)等数据挖掘问题，并在很多领域，如数字识别、人脸图像识别、时间序列预测等方面得到成功应用。支持向量机算法的基本思想是：通过非线性变化将进入空间中的样本特征映射到一个高维的特征空间，并在新空间中寻找到最优超平面，使得样本之间的间隔达到最大[13]。面对非线性分类问题时，支持向量机首先是在低维度空间中计算，然后通过选择合适的核函数k(xi,yi) 将输入的数据映射到高维空间中，最终原空间中的非线性分类就变成了高维特征空间中的线性可分问题[14]，图2表示非线性分类时，通过核函数方法将数据映射到高维空间之中。

图2 核函数方法将非线性可分数据映射到高维空间

2.3 构造多类分类算法

构造多类分类的方法算法的复杂度很高，所以需要找到一种简单实用的多类分类算法。本文以一类分类算法为基础建立一种多类分类算法。首先在高维特征空间上对每一类样本求出它们的超球体中心，然后计算出后续样本和超球体中心之间的距离，再根据它们之间的最小距离来判断该点所属的类，算法的具体步骤如下：定义样本为 {(x1,y1),…,(xl,yl)}⊂Rn×Y，Y={1,2,…,M}, 其中，n为测试样本向量的维数，M为类别数目。将样本分为M类，每个类分开写成： {(x1(s),y1(s)),…,(xl(s),yl(s)),s=1,…,M} 其中， {(xi(s),yi(s)),i=1,…,ls} 代表第s类训练样本，l1+…+lM=l。 为了得到包含每类样本的最小超球体距离，构造下面的二次规划

(1)

约束为

si≥0,s=1,…,M,i=1,…,ls

该优化问题转换成对偶形式为

(2)

约束为

同时引入核函数方法，本文通过核函数k(xi,xj) 来代替高维特征空间中的內积运算。采用高斯核函数kG， 给定两个包含多示例的包xi,xj， 则在多示例情况下高斯核函数可以表示为

(3)

其中，γ是高斯核函数的参数，本文采取麦克劳林展开式来确定γ的取值[6]。将多示例包所处的原空间映射到高维特征空间，并对这个多示例包在高维特征空间中做优化处理，最终得到核方法下的优化方程为

(4)

约束为

最终优化为

(5)

式(5)是多类分类问题最终的优化方程，需要优化的参数个数是样本的总数l，可以通过调整参数c的值来抑制噪声的影响。该优化方程的算法计算复杂度受样本数量影响较大，而数据集的类别数量对算法计算复杂度影响较小。因此，可以利用基于一类分类的多类分类算法解决多分类问题。

2.4 示例间距离计算方法

对于多示例学习问题的研究，国内外学者做出了深入研究，提出了很多优秀的算法，例如：多示例核方法、多示例K近邻算法、多示例图方法[15]等。

其中，多示例K近邻算法利用最大或者最小Hausdorff距离搜索邻近的包来度量示例之间的距离，是一种利用近邻规则的多示例学习算法，在应用中取得了比较优异的表现。

dmax H(A,B)=max{d(A,B),d(B,A)}

(6)

(7)

式(6)中的d(A,B),d(B,A) 表示距离，分别表示为

(8)

(9)

通过分析，发现最大Hausdorff距离容易受到噪声的干扰，受到异常示例的影响非常大，下面通过一个实际例子加以说明。首先设置每个示例D=1， 即示例为标量。假设包A={-2,-3,-4,-5}， 包B={2,3,4,40} 都是由4个示例构成，其中包B中的示例40为一个噪声数据，定义为异常示例。由式(8)、式(9)可知，d(A,B)=max{4,5,6,7}，d(B,A)=max{4,5,6,42}， 根据式(6)可知dmax H(A,B)=max{7,42} 很突出，B包中的噪声示例40会对最大Hausdorff距离的产生影响。再根据式(7)，可知dmin H(A,B)=4， 包A,B之间的最小Hausdorff距离没有受到噪声示例的干扰。因此最小Hausdorff距离(minimum Hausdorff distance)对于异常示例并不敏感，可以使用最小Hausdorff距离作为度量多示例包之间的距离。

对于本文处理的文本示例来说，所有的属性值都是非数值的，所以不能直接使用最小Hausdorff距离来计算。为了使MIL-SVM算法能够适用多示例学习框架，就必须给出两个包之间距离的度量方法，多示例学习中两个示例之间的距离我们可以通过计算两个包之间特征向量的距离。一个文本中出现频率较高的词能够从某一方面代表这个文本的主题，但是对于一些“的”、“啊”、“呵”等停用词可以不作为文本的特征词考虑。所以，我们选取文本中的高频词作为文本的特征词语来对文本进行表示。

本文使用文本中出现的一系列高频词汇组成一个q维特征向量用w=[w1,…,wq]T来表示文本代表的主要内容，其中wi(i=1,2,…,q) 是对应的文本中词汇出现次数第i高的高频词。在本文中，一个包含有n个文本的数据集就可以表示为一个含有n个示例的包Bag={[w11,w12,…,w1q],[w21,w22,…,w2q],…,[wn1,wn2,…,wnq]}， 通过这种方式就能够将文本中的文本特征通过提取高频词的方式表示出来。每一个包通过一个q维特征向量来表示，第i维的属性值是文本中对应的第i高词频的词汇。如果两个文本之间的内容越相近，那么文本中出现相同高频词的概率也就越大，因此两个特征向量之间包含的相同词汇越多，那么它们之间的距离也就越小，根据这个启发式原则，可以定义以下距离计算方法。

假设两个示例a=[x1,x2,…,xq]T，b=[y1,y2,…,yq]T是q维的文本特征向量，那么a和b之间的距离为

(10)

其中，δ(x,y)=1当且仅当x=y。

这样，就可以通过式(10)代替式(7)中计算两个示例之间的距离，从而可以得到适合多示例学习中示例之间距离计算的方法。MIL-SVM算法使用时，训练数据来自具有标记的“正示例”和“负示例”，将所有正包的示例看作是“正示例”，加上负包中的“负示例”即可训练出一个SVM分类器。利用SVM分类器重新标记训练集中的所有包，并对示例进行标记，只有当一个正包中的所有示例都被判定为负，才能够将这个包中拥有最小距离的示例标记为正。利用被标记为正的示例和负包中的示例不断标记和训练，当全部数据集中包的示例标签稳定下来，不再发生改变时，SVM便被重新训练完毕。

3 实验分析

3.1 实验数据集

为了检验MIL-SVM算法在文本分类领域的有效性，本文采用来自Python程序爬取的语料库进行实验分析。数据来源于新浪、微博、知乎等知名中文网站的新闻以及评论数据，经过数据预处理，删去不满足要求的文本之后，最终数据集包括8个分类，每个分类6000条数据，训练集30 000条，测试集18 000条。类别如下：时政、体育、房产、财经、旅游、教育、科技、健康，并对数据集标记为(U1-U8)。随机对8个分类中的数据进行标记，每个数据集中的正示例与反示例分布情况见表1。

文本分词采用jieba中文分词工具，通过多进程分词，对训练集、测试集进行分词，特征值提取阶段通过词频统计工具，将文本中的高频词统计出来后构建特征向量。将实验数据集分为训练集和测试集，通过上述分类算法对训练集构建模型，然后对测试集进行分类预测。

表1 数据集中正例和反例分布情况

3.2 实验过程及评价指标

本文使用两种常用的监督式学习经典文本分类算法与多示例学习MIL-SVM算法进行对比实验，支持向量机(SVM)算法和KNN算法。SVM算法是一个经久不衰的算法，具有高准确率特性，在线性不可分的情况下，只要给定一个合适的核函数，就可以发挥出很好的效果；KNN算法思想简单，既可以用来做分类也可以用来做回归分析，可用于非线性分类，KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练。由于这两种非多示例学习算法不需要运用多示例学习方法，所以将标题和正文视作一个整体。其中SVM算法采用LIBSVM实现，本实验中核函数采取高斯核函数，参数c=5； KNN算法由Matlab内置集成的fitcknn函数实现。

本文使用能对数据集进行充分利用的K-折交叉验证法验证数据集上算法对文本分类的准确性。该方法的步骤为：①将数据分为随机的k个包；②不重复地从k个包中选一个包当作测试集，剩余的k-1个包作训练集；③重复步骤②，直到k个包均被选择1次。这样经过N次循环验证，对每次的评价指标数据进行平均，得到分类算法的准确性。本文采取常用的10-折交叉验证法，选取准确率(Precision，P)、召回率(Recall，R)和综合评价指标(F1-Measure，F1)值作为文本分类的评测指标。其中准确率表示模型对于正样本的区分程度，召回率表示模型对负样本的区分程度，F值是两者的平均值。准确率、召回率、F值的计算公式如式(11)-式(13)所示

(11)

(12)

(13)

其中，实验测试集中包含X个正示例和Y个负示例，正示例中包含能够被分类器正确分类的Xa个样本和被分类器错误分类的Yb个样本，负示例中包含被分类器正确分类的正示例的Xa个样板和错误识别的负示例样本Yb。

3.3 实验结果与分析

实验中，由于特征向量中高频词的个数对示例的表征能力有直接的影响，所以，实验需要在不同的高频词个数下比较3种算法的分类效果。在高频词个数相同的情况下，得到了KNN，SVM，MIL-SVM这3种算法在对应数据集上的准确率P、召回率R和综合评价指标F1值，然后计算出3种评价指标在对应数据集上的平均值。如图3-图5所示，分别对应高频词为5,10,15时的评价指标实验结果。

图3 3种分类算法在5维特征向量下的分类比较结果

图4 3种分类算法在10维特征向量下的分类比较结果

图5 3种分类算法在15维特征向量下的分类比较结果

从图3-图5可以看出，在实验中选择的特征向量数量相同的情况下，多示例学习MIL-SVM算法在数据集上的平均准确率明显好于其它两种传统的非多示例学习算法。并且MIL-SVM算法在所有数据集上的分类效果都比较平均，没有出现特别大的评价标准值异常波动的情况，例如SVM算法在5维特征向量下对于数据集U1的分类就出现异常波动。如图6所示，多示例学习MIL-SVM算法的准确率比较平均，没有出现异常波动的情况，且准确率优于其它两种对比算法的分类准确率。

图6 KNN，SVM和MIL-SVM不同特征向量个数下的准确率对比

从召回率角度看，多示例学习MIL-SVM算法在3种不同的特征向量情况下，分类效果比KNN和SVM算法好。从图3-图5的数据中可以计算出MIL-SVM算法的平均召回率为82.8%，而KNN和SVM算法的平均召回率分别是68.4%和66.9%。从综合评价指标F1值来看，多示例学习MIL-SVM算法在3种不同的特征向量情况下表现的分类数据更加稳定。因此，多示例学习MIL-SVM算法相比于实验中的其它两种算法有更加优越的分类效果。

综合3项评价指标来分析，采用多示例学习框架的MIL-SVM算法分类的效果明显优于非多示例学习框架KNN和SVM算法。这说明，在使用多示例学习框架的SVM分类算法，对于具有特殊结构文本分类问题能够提升其分类的准确率。

通过实验验证分析，我们可以发现本文提出的基于多示例学习框架的支持向量机分类算法相对于传统的机器学习分类算法有比较大的优势。不同于只考虑了一种示例特征结构的传统机器学习方法，本文提出的方法将实验数据集的特征结构进行充分细致的考虑，作为分类的特征项的示例源于多角度的选择，因此原始数据集的利用率和分类器的分类精度得以显著提高。同时，本文提出的多示例学习框架算法适用性很好，只要数据集有特定的文本结构，并且合理定义包中的示例，就能很好解决很多文本分类问题。但是，我们提出的多示例学习MIL-SVM分类算法在时间复杂度的表现上比实验中的其它两种算法差，存在劣势，需要进一步优化模型。

4 结束语

本文提出的基于多示例学习框架的支持向量机文本分类方法，借鉴机器学习领域的多示例学习方法和支持向量机算法。针对数据集具有的特殊结构，将每个文本当作一个示例包，文本中的标题和正文视作为示例包的两个示例，将示例包映射到高维特征空间中，利用高斯核函数训练分类器，有效地提高了分类的准确性。实验结果表明，该算法相较于传统的KNN算法和SVM算法在分类的准确率上有明显的提高。在今后的研究中，将继续优化模型算法的时间复杂度，使其适应海量数据的文本分类需求。