选择性集成算法

选择性集成算法（通用7篇）

选择性集成算法 篇1

摘要：本文提出一种基于SFLA聚类的选择性ELM集成方法。实验结果表明, 与集成RBF神经网络模型相比, 采用本文方法对模拟电路进行在线故障诊断具有较高的准确性。

关键词：混合蛙跳算法,极端学习机,选择性集成

1 引言

本文参照CLUSEN方法, 提出一种基于混合蛙跳算法 (Shuffled frog-leaping algorithm, SFLA) 聚类的选择性极端学习机 (Extreme Learning Machine, ELM) 集成算法, 即对采用SFLA对个体ELM基分类器的结果进行聚类, 去除冗余个体, 提高集成个体分类器的差异度。

2 基于SFLA的聚类算法

基于SFLA[1]的聚类算法步骤如下:

Step 1:种群的初始化。

Step 2:将N只青蛙按适应度值降序排列并按照分组算子将N只青蛙分给m个模因组。

Step 3:每个模因组中的位置最差青蛙执行局部位置更新算子。

Step 4:各个模因组中的所有青蛙重新混合, 组成数量为N只青蛙的总群体。

Step 5:对新的青蛙群体, 更新种群中最好位置的青蛙Fg。

Step 6:判断终止条件是否满足, 如果满足, 结束迭代, 否则转向Step 2继续执行。

3 极端学习机算法

极端学习机在随机给定输入权值与神经元参数的基础上, 将传统前馈神经网络参数训练问题转化为求解线性方程组, 以直接计算输出权值的最小二乘解的方式完成网络训练过程。

4 基于SFLA聚类算法的选择性ELM集成算法

算法首先在训练集上利用Bootstrap方法训练多个ELM个体, 然后对这些神经网络个体进行聚类, 并选出其中靠近聚类中心的个体, 组成选择后的个体集合。对于聚类的类别个数通过验证集进行确定, 选择使得验证集精度最高的类别个数。选择好个体后, 通过多数投票法建立集成模型。最后用测试数据进行测试。

5 实例分析

本文以文献[2]中的带通滤波器电路为例来验证所提出算法的有效性。这里对表1中包括无故障在内的9种双故障进行分析。针对每种故障模式分别进行50次Monte Carlo分析, 共获取450组故障样本数据, 选择db3小波函数对故障样本数据进行3层小波包分解, 并以第3层各项分解系数归一化能量作为故障特征, 得到4508的故障特征矩阵。选择各模式30组样本作为训练样本, 其余20组样本作为测试样本 (见表1) 。

为了验证算法效果, 选择集成RBF神经网络模型进行对比。在离线故障诊断中, 采用本文方法的测试准确率达到100%, 而集成RBF神经网络模型仅为79.33%。为了验证模型在线诊断能力, 对电路各故障连续运行5s重新采集50组样本。设定两种工况: (1) 电路连续正常运行5s; (2) 正常运行2.5s后出现一种双故障, 这里选择Df5和Df7两种故障。从图1和图2中可以看出, 对于正常状态两种模型都能够准确实现故障的在线诊断, 但对于双故障本文算法仅出现了2次误诊, 算法在线诊断能力优于集成RBF神经网络模型。

6 结语

为了提高集成个体的差异度, 本文提出了一种利用SFLA聚类算法去除冗余个体的选择性ELM集成方法。实验结果表明, 与集成RBF神经网络模型相比, 采用本文方法对模拟电路进行在线故障诊断具有较高的准确性。

参考文献

[1]杨淑莹, 张桦.群体智能与仿生计算——Matlab技术实现[M].电子工业出版社, 2014.

[2]王宏力, 何星, 陆敬辉, 等.基于固定尺寸序贯极端学习机的模拟电路在线故障诊断[J].仪器仪表学报, 2014, 35 (4) :738-744.

选择性集成算法 篇2

对于云图的识别研究，国内外主要集中在卫星遥感云图方面，卫星云观测在大尺度云的识别和云顶高测量等方面取得了良好的成果。相对卫星云观测，地基云观测近年来也基本实现了对云量和云高的自动测量。然而，目前对地基云状的识别仍然采用的是经验性的人工定性判断。由于地基云图云状种类繁多，主要依赖于观测员的经验进行人工观测，主观随意性较大，存在很多的缺陷[1]。

近年来，国内外学者对地基云图分类的研究，主要集中于基于最小距离分类器、神经网络分类方法。文献[2]采用自相关、共生矩阵、LAWS能量等方法提取纹理特征，但分类效果仅限方法上的讨论。文献[1]采用最小距离分类方法实现云状判定，但该方法过分依赖于初始中心的选择，容易陷入局部最优值。文献[3]提出采用BP神经网络分类器对云图进行自动分类识别，但该方法没有克服传统BP神经网络存在的缺陷，容易陷入局部最小值，算法收敛速度较慢，导致分类结果不稳定。传统的BP＿AdaBoost算法用于云图的分类，虽然在一定程度上克服了单个BP神经网络易陷入局部极小值的缺点，提高了云图识别的准确率，但算法并没有考虑到网络之间的差异性问题，使得最终集成的分类器的性能受到削弱，并没有得到明显的增强。

针对以上存在的问题，本文提出一种基于K均值聚类算法的选择性神经网络集成方法。该方法以BP神经网络集成模型为基础，利用K均值聚类算法来选择部分有差异性的个体神经网络，最后通过Ada Boost算法集成，得到由多个精度较高、差异性不同的BP神经网络组成的强分类器，应用于地基云图的识别和分类。

1 BP神经网络算法与AdaBoost算法

1.1 BP神经网络算法原理

BP神经网络是一种典型的多层前馈网络，它分为信息的正向传播和误差的反向传播两个阶段。正向传播阶段输入层各神经元负责接收来自外界的输入信息，并传递给中间层各神经元，中间层各神经元经过处理变换后传递给输出层，得到预测结果。反向传播阶段将输出层预测的结果与真实结果之间的误差反传给中间层各神经元，然后通过梯度下降方法最小化网络输出值和目标值之间的误差平方，以此来学习神经网络单元的权值[4]。由于结构简单，健壮性强，BP神经网络在近30年内解决了很多复杂的工程问题，取得了惊人的成就[5]。

1.2 AdaBoost算法原理

Ada Boost算法是一种集成学习算法，它的核心思想是针对同一个训练集下不同的样本分布，训练不同的弱分类器，这些弱分类器的性能只要略比随机猜测的好点即可，Ada Boost最终将多个这样的弱分类器通过加权机制级联成一个强分类器[6]。算法本质上是通过改变样本数据的分布来实现的，在每次的迭代过程中，样本的权值会根据上次分类的总体正确率和每个样本的分类情况正确与否来决定。对于分类错误的样本，加大其权值;而对于分类正确的样本，则降低其权重，从而得到不同的样本分布。

1.3 传统BP＿AdaBoost的分类器模型

传统的BP＿AdaBoost模型即把BP神经网络作为弱分类器，在不同的样本分布情况下，反复训练多个BP神经网络弱分类器来分类样本，最后通过Ada Boost算法将多个弱分类器组成强分类器。基于传统的BP＿AdaBoost模型用于云图识别，算法流程如图1所示。

BP＿AdaBoost训练强分类器算法步骤如下:

(1)选择数据和初始化BP网络

从云图样本空间中随机选择m组训练数据，初始化Ada Boost算法训练数据的分布权值D1(i)=1/m及BP神经网络的权值和阈值，并根据样本的输入输出维数确定神经网络结构。

(2)训练弱分类器

训练第t个弱分类器时，将第t-1次训练后调整分布权值的训练数据作为BP神经网络的输入，得到分类器gt的误差和εt，误差和εt的计算公式为:

(3)计算分类器的权重

各个分类器权重主要根据各个分类器的误差来计算的，第t个分类器权重的计算公式为:

(4)调整训练数据权值

根据第t个分类器的权值αt来调整第t+1个分类器训练样本的权值，权值的调整公式为:

式中，Zt是归一化因子，使得样本分布的权值和为1。

(5)生成云图强分类器

Ada Boost算法经过T次训练后得到T个BP神经网络弱分类器，依权重联合T个弱分类器得到的最终的强分类器h(x)的形式如下:

2 基于K-means的选择性神经网络集成

2.1 K-means聚类算法

K-means聚类的原理是利用相似度计算方法将相似的对象归入到同一簇，将不相似的对象归入到不同簇中。这种方法具有很好的几何意义和统计意义。本文利用这种思想将训练出的神经网络基分类器进行聚类，在保证精度的同时有选择性的选择部分差异性的个体分类器进行集成。K-means聚类算法的算法流程如下:

输入:训练数据集X={x1,x2，…，xn}，聚类数目k;

输出:k个类簇Cj,j=1,2，…，k

步骤1令I=1，随机选择k个训练样本作为k个类簇的初始簇中心mj(I),j=1,2，…，k,I表示算法迭代的次数;

步骤2计算每一个训练样本与这k个簇中心的距离d(xi,mj(I)),i=1,2，…，n;j=1,2，…，k，如果满足d(xi,mj(I))=min{d(xi,mj(I)),j=1,2，…，k}，则xi∈Cj;

步骤3计算k个新的聚类中心

步骤4如果mj(I+1)≠mj(I),j=1,2，…，k,

则I=I+1，返回步骤2;否则算法结束。

2.2 选择性神经网络设计思路

训练集的差异和每个BP网络初始权值和阈值的差异都是影响个体网络之间差异的重要因素。然而传统的BP＿Adaboost集成方式，由于学习算法的随机性可能会产生彼此非常相似的神经网络分类器，将各个差异度较小的分类器进行集成，并不一定能够降低集成的泛化误差，还有可能导致泛化能力减弱，组成集成学习模型的各个网络的精度越高，成员之间的差异度较大，越有利于集成学习泛化误差的降低[7]。本文在训练集有限的情况下，通过重复取样技术获得训练集之间的差异度，在子训练集中原始数据有可能重复出现，也有可能不出现，利用Bootstrap技术采样得到N组规模为n的训练样本集。然后利用BP神经网络独立训练这N组样本集获得每个网络的权值和阈值，用K-means算法将得到所有权值阈值进行分类，得到与基分类器个数相同的聚类中心，最后选择靠近每个聚类中心的个体分类器的权值和阈值，将其作为M个基分类器的初始权值和阈值，这样就构成了M个具有差异性的基分类器，通过Ada Boost算法将M个基分类器级联为一个最终的强分类器，建立起地基云图分类模型。

3 实验结果与分析

3.1 实验数据

根据观测和天气预报的需要，按云的底部距地面的高度将云分为低、中和高三族，按云的宏观特征、物理结构和成因划分为十属二十九类云状[8]。本文选取秃积雨云、淡积云、密卷云和层云四种典型云类建立分类样本库。实验样本选取来自于南京信息工程大学大气综合观测基地的云图数据资料、山西省气象局官网云图资料、数码实地采集的云图资料和《中国云图》数据资料等。四种典型云类样本如图2所示。

通常情况下，如图2所示，积雨云云浓而厚，云体庞大如高耸的山岳，高度不一，底部阴暗，纹理较为光滑均匀;积云一般是积云群，轮廓分明，云底平坦，云块之间多不相连，造成纹理起伏、边界不整;卷云的纹理呈白色细丝状或窄条状，分布比较均匀;层云云底很低，纹理均匀呈层，似雾，但不与地接，云顶厚度和高度相差很小。

3.2 纹理特征提取

基于灰度共生矩阵来提取纹理特征在图像识别领域得到了广泛的应用，如文献[9,10,11]。文献[12]详细描述了从灰度共生矩阵中可以提取图像纹理的各种统计量作为特征值。文献[2]讨论了相对于其他的纹理特征手段，灰度共生矩阵提取的特征对云图分类的效果更佳。文献[13,14]将图像的梯度信息加进灰度共生矩阵，使得共生矩阵更能包含图像的纹理基元及其排列信息。本文结合已有相关的研究，采用灰度-梯度共生矩阵方法来提取云图的纹理特征。

灰度-梯度共生矩阵纹理分析方法是利用图像的灰度和梯度的综合信息提取纹理特征，它是像素灰度和边缘梯度大小的联合分布，集中反映了图像中的两种基本要素，即像素的灰度和梯度的相互关系。像素的灰度是构成一幅图像的基础，而梯度则是构成图像边缘轮廓的要素。灰度-梯度空间很好地描绘了图像的纹理，清晰地表现出图像内像素灰度和梯度的分布规律。

灰度-梯度共生矩阵的元素h(x,y)定义为在归一化的灰度图像f(i,j)及其归一化的梯度图像g(i,j)中具有灰度值x和梯度值y的像素数，即在集合{(i,j)|f(i,j)=x∩g(i,j)=y}中元素的个数。梯度图像g(i,j)可由灰度图像经过微分算子计算得到。

然而实际所面临的情况是采用灰度-梯度共生矩阵提取云图图像纹理特征，其计算量由云图的灰度级数和维数来决定的[15]，而通常情况下，一幅云图灰度图像的灰度级为256级。为了提高云图整体识别性能的时间效率，本文在进行灰度-梯度共生矩阵计算时，在不影响纹理特征的前提下，将原始的云图样本图像的灰度级压缩为32个灰度级。从计算出的灰度-梯度共生矩阵中提取出了如小梯度优势、大梯度优势、灰度不均匀、梯度不均匀和能量等15种常用的二次统计特征参数，建立云图样本特征库。在特征提取前，对样本初始图像进行必要的预处理，使得图像的纹理特征更加突出，尽量减少噪声等其他因素的干扰，为更加准确提取云图的特征参数创造有利的条件。

3.3 实验及结果分析

本文实验共选取了800个云图样本，每类云图样本各为200个，每类选择其中150个样本作为训练样本，剩下的作为测试样本，在本文提出的算法模型中，首先使用Bootstrap方法生成N(N=200)组规模为n的云图训练样本集(本文n=150，与原始训练集大小相同)，然后每组训练出一个神经网络弱分类器，接着利用K均值算法将生成的每个弱分类器的初始权值和阈值进行聚类，得到M个类簇(M的取值与基分类器的个数相同，本文集成网络中基分类器的个数由实验探索得到，M=15)，选择靠近M个类簇中心的个体分类器的初始权值和阈值，将其值作为集成网络个体的初始权值和阈值，最后通过Ada Boost算法将训练的各个基分类器集成为一个强的分类器。传统的BP＿Ada Boost算法模型和本文提出的算法模型在基分类器个数取值相同时在云图测试样本上的错误率比较如图3所示(其中每个基分类器的训练误差精度值取0.003)。

在传统的BP＿AdaBoost集成方式中，由于各个基分类器的初始权值和阈值的产生是随机的，无法保证网络之间具有较大的差异性，从而使得训练生成的各个基分类器的差异性不明显，集成这些基分类器并没有使得整个云图分类器的泛化能力得到提高，且云图测试集错误率曲线呈现出一种震荡的趋势，如图3所示。但本文提出的基于K-means算法有选择性的选择个体网络的权值和阈值来训练分类器，使得生成的基分类器之间具有一定的差异性，集成这些差异性的个体网络用于云图识别，错误率能够持续平稳降低，图3可以看出利用本文提出的算法模型训练生成的强分类器在云图测试集上的错误率明显要低于传统型BP＿AdaBoost算法在云图测试集上的错误率。

本文还比较了在基分类器的训练误差精度取不同值时，单个BP神经网络模型、传统的BP＿AdaBoost模型及本文提出的模型在云图分类识别上的性能。对于三种模型共进行了4次实验，在每次试验下，每个基分类器的训练误差精度值分别设定为0.04、0.01、0.008和0.003，在集成模型中，基分类器的个数取为15，实验结果如图4所示，其中x轴为实验序号，y轴为在测试样本下的错误率。如图4所示，组成集成学习模型的各个网络的精度越高，成员之间的差异性越大，越有利于集成学习泛化误差的降低。

通过上述云图数据的验证实验，说明本文提出的基于K-means算法选择性集成BP神经网络分类的方法相对于传统的BP＿AdaBoost算法在云图分类上取得了更好的识别精度，且稳定性也得到了可靠的保障，能够有效提高云图分类的性能。

4 结语

本文构建了一种基于K均值算法选择性集成BP神经网络分类的云图强分类器。相对于传统的BP＿AdaBoost算法，本文提出的模型采用K均值将BP神经网络独立训练出的若干弱分类器进行聚类，有选择性地集成了部分有差异性的个体网络，最后通过Ada Boost集成为一个强分类器。实验结果表明本文提出的算法用于云图识别具有较高的分类精度，能够有效提高云图分类的准确性和稳定性，降低了传统神经网络集成的泛化误差。如何有效确定云图分类的关键特征及确定集成分类器中基分类器的个数是下一步研究的主要内容。

摘要：针对传统地基云图云状识别模型精度较低的问题,提出一种基于K均值算法的选择性神经网络集成的方法。该方法以BP神经网络集成模型为基础,采用K均值聚类算法选择部分有差异性的个体神经网络进行集成,建立了云状分类模型。通过对云图样本进行仿真实验,结果表明所提出的算法相对于单个BP神经网络及传统的BPAdaBoost集成算法用于云图的分类,能有效地提高云图识别分类的精度。

选择性集成算法 篇3

财务困境是指企业因遭受严重的外部挫折或内部财务活动失去控制而使得财务状况所处的危险或紧急状态, 一般包括流动性不足、无力支付到期债务、拖欠优先股股利、盈利能力实质性或持续性削弱、甚至破产等情形。它不但给公司本身带来各种直接或间接的成本甚至影响其生存和发展, 而且直接伤害到投资者的利益。进行企业财务困境预测 (Financial Distress Prediction, FDP) 能够在其财务状况陷入困境前予以警示。由于企业财务困境预测的关键是预测模型的构建, 如何构建准确、有效的财务困境预测模型一直属于该领域理论研究的热点问题。

2 文献回顾

财务困境预测建模方法基本的研究进展可以简要概括为:从单变量分析到多变量预测, 从传统统计方法到基于人工智能的机器学习方法, 以及从单一分类器独立预测到多分类器组合预测。Kumar和Ravi (2007) 在对1968～2005年的破产预测方法进行综述的文献中指出:组合模型往往能够弥补各单一分类方法的不足, 充分利用各自的信息优势, 进而提高组合系统的预测精度。并且他们指出构建新颖的或者更加合理的组合系统将是未来财务困境预测研究的热点问题[1]。此后, 利用各种新颖的分类算法和融合技术进行FDP组合研究的成果越来越丰富。构造多分类器系统的方法非常多, 但大致可以分为两类:分类器扰动和样例扰动。分类器扰动即利用分类学习算法的不稳定性或利用多种算法在一个数据集构造多分类器系统。Sun和Li (2008) 以先验分类性能为权重, 对各基本分类器的预测结果进行加权投票融合, Cho等 (2009) 利用人工神经网络对各基本分类器进行赋权融合, 实验结果均表明多分类器系统在准确率和稳定性上均优于单分类器模型[2,3];Li和Sun (2009) 利用基于不同度量的CBR模型构造组合模型, 比较多数投票和加权多数投票的融合结果, 并与MDA和Logit模型比较, 实验结果证明了基于加权多数投票的多案例推理分类器系统的可行性和有效性[4]。样本扰动又可以分为两种, 一种是利用不同的训练样本子集获得基本分类器, 如Bagging方法和boosting方法;另一种是利用数据集的不同特征子空间构建基本分类器, 如随机特征子空间法 (Random Subspace Technique) 。Tsai和Wu (2008) 分别在同一数据集上、多个数据集上构造神经网络多分类器系统, 实验结果表明组合分类器的性能并没有优于单一分类器, 他们认为其构造的多分类器系统可能并不适用于二元分类[5]。利用与Tsai和Wu相同的数据集, Nanni和Lumini (2009) 比较了各种多分类器构造方法, 认为基于Leveberg-Marquardt神经网络的随机特征子空间方法优于其它多分类器模型[6]。国内学者孙洁等 (2009) 提出了FDP的多分类器混合组合模型, 采用差异化原则和个体优化原则作为选择基本分类器的标准, 首次将组合模型结构选择引入FDP研究之中, 实验结果表明该模型显著优于单分类器FDP模型[7]。

目前模式识别领域有关多分类器系统的研究普遍认为:组合自身分类精度高且个体之间差异大的多个分类器能形成强大的分类系统[8,9];此外, 挑选部分分类器进行融合分类效果比组合全部分类器更好[10]。当可供选择的基本分类器较多时, 如何从中选择一部分分类器进行集成, 形成一个简洁高效的组合分类系统, 本文将其定义为选择性集成问题。针对上述问题, 目前国内外的FDP研究鲜有涉及, 文献[7]采用差异化和个体优化的策略选择基本分类器, 但是该种方法也没有得到一致有效的结果, 并且如何定义基本分类器之间的差异也还存在分歧[11]。

遗传算法 (Genetic Algorithm, GA) 是由Holland教授在20世纪60～70年代发展起来的一种全局优化自适应概率搜索算法。它使用群体搜索技术, 通过对当前群体施加选择、交叉、变异等一系列操作来产生出下一代群体, 从而使群体逐步进化到包含或者接近最优解得状态[12]。在FDP领域, GA应用成果丰富, 如Shin和Lee (2002) 使用GA提取破产模型的判别规则[13], 但更多的是利用GA进行特征子集的选择或模型参数的优化[14,15,16,17]。对于利用GA进行最优组合多分类系统搜索的可行性, 目前尚缺乏有效的证据予以支持。

在FDP研究的环境下, 与多数文献事先静态给定组合系统的基本分类器构成不同, 本文利用GA从众多基本分类器中进行最优组合系统的动态集成, 该方法无需计算分类器之间的差异性, 从而形成一种新的财务困境组合预测方法。实证研究中, 利用中国上市公司的实际数据对该模型的应用效果进行实验和验证, 证明了该方法在中国上市公司FDP方面具有可操作性和有效性。

3 GA选择性集成多分类器系统基本原理

3.1 设计思路及模型构架

利用GA进行多分类器系统的选择性集成需要三个步骤:①备选基本分类器库的构建;②利用GA从基本分类器库中对最优组合系统进行动态挖掘, 即选择性集成过程;③最优组合系统内部各基本分类器信息融合机制。其基本结构如图1所示。

步骤1:对包含N个财务指标的初始数据集进行特征提取, n种不同的方法可以获得n个相异的特征子集, 它们包含了企业财务困境的不同信息侧面, 是进行信息融合的基础;对于某一特征子集, 分别使用m种不同的学习算法训练基本分类器, 这样可获得的备选基本分类器个数=m×n;由于它们或是基于不同特征空间构建, 或是基于不同学习算法训练而成, 因此一定是差异性基本分类器, 满足构建组合系统的基本前提。

步骤2:针对步骤1所构建的基本分类器库, 利用GA搜索最优基本分类器组合, 该方法直接以组合系统预测精度为优化目标, 通过引入自然界的适者生存和优胜劣汰机制, 逐步进化到最优解或满意解。

步骤3:对经过GA选择得到的最优基本分类器组合进行预测结果集成, 得到经优化的组合系统。本文采用目前较为常用的加权多数投票方式。由于步骤2中直接以组合系统预测精度为优化目标, 过程涉及大量基本分类器组合寻优, 所以步骤3中所使用的加权多数投票方法在2中亦有所体现。

步骤2是该方法的核心部分, 下面详细予以讨论。

3.2 GA搜索最优系统算法设计

遗传算法可定义为一个8元组:

$SGA=(C,E,{\rm P}{}_0,{\rm M},\Phi ,\Gamma ,\Psi ,{\rm T})(1)$

其中:C为个体的编码方法;E为个体适应度评价函数;P0为初始种群;M为种群规模;Φ为选择算子;Γ为交叉算子;Ψ为变异算子;T为遗传运算终止条件。

(1) 个体编码方法

遗传算法使用固定长度的二进制基因符号串来表示群体中的个体染色体 (Uk, k=1, 2, …, M) , 其等位基因由{0, 1}所组成。备选基本分类器个数为m×n, 则每一个可能的多分类器系统 (即Uk) 可由m×n位二进制的基因符号串来编码, 每个等位基因与一个备选基本分类器相对应。基因值为1表示该等位基因对应的基本分类器被包含进组合系统之中, 为0则表示不被选中。

(2) 个体适应度函数

个体适应度用来度量群体中各个个体在优化计算中能达到或接近于最优解得优良程度。适应度较高的个体遗传到下一代的概率就较大;而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数。对于多分类器系统选择性集成问题, 由于我们的目标是选择出泛化性能优良的组合系统作为最终结果, 因此可以将群体中个体染色体 (多分类器系统) 的v折交叉验证[18]5种特征提取方法在数据集U′t-2和U′t-3上进行特征提取。在数据集U′t-2上, t检验和ANOVA的显著性水平设定为1%, U′t-3数据集设定为5%; NRS的邻域度量设定为δ=0.15, 停止准则为特征子集的显著性增量ΔSIG≤0.001。特征提取结果如表2所示, 除t检验和ANOVA特征提取结果相同外, 其它特征提取方法结果差异较大。

(2) 备选基本分类器库构建

基本分类器学习算法选择目前财务困境预测领域较为流行的4种方法:包括支持向量机 (SVM) 、多元判别分析 (MDA) 、逻辑回归 (Logit) 、决策树 (CART) 。针对某一数据集U′t-x, 在3.3 (1) 所获4个相异特征子集和原始特征集上分别利用上述4种方法构建基本分类器, 故备选基本分类器个数=5 (特征子集个数) ×4 (分类学习算法数) =20。20个基本分类器的10折交叉验证预测准确率列于表3和表4。

(3) GA搜索最优系统参数设置及实验结果

在GA搜索最优组合系统的实验中, 根据遗传算法参数的经验范围并经多次实验, 最终选定参数如下:群体规模M=50, 交叉概率Pc=0.8, 变异概率Pm=0.1, 个体染色体基因串长度=5×4=20, 民终止代数T=150; 同时, 以表3和表4所示的准确率作为权重对组合系统内各基本分类器的预测结果进行加权多数投票集成, 例如, 若 (t-2) 数据集的SLR+SVM基本分类器被选中, 则对其预测结果赋权89%, 而对相反结果赋权11%, 组合预测结果为系统内获取较大权重和的类别预测结果。按照上述参数在两个数据集上分别进行实验的结果如图3、图4、表5所示。同时, 在 (t-2) 年和 (t-3) 年分别利用GA选择最优组合系统的基本分类器构成如表3和表4中黑体所示。

4.4 实验结果分析及讨论

① 如表3、表4所示, (t-2) 模型的准确率普遍高于 (t-3) 模型的准确率, 说明越临近困境点, 企业状况在财务指标上所反映的恶化征兆越明显, 因此构建的模型预测能力越强。从横向均值的比较来看, SVM都具有最优的预测准确率, MDA和Logit性能接近, 而CART则最差。纵向均值反映各种特征提取方法挖掘分类信息的能力, 从中可以看出:各种特征提取方法构建的模型均优于原始特征集, 说明了财务困境特征提取的重要性;各种方法所获特征子集差异较大, 但均具有较强的预测性能, 满足组合系统对基本分类器准确性的要求。

② 如表5所示, 将20个基本分类器全部集成的组合系统预测准确率低于基本分类器最优准确率, 下降幅度分别为 (t-2) 数据集0.5%、 (t-3) 数据集0.75%, 而利用GA选择性集成系统预测准确率分别达到91.25%和80.75%, 较之全集成分别提高了2%和3.75%, 可见组合并不一定会带来系统预测准确率的提升以及选择性集成的必要性。从图3和图4的种群适应度最大值曲线来看, 其形状大致呈阶梯上升趋势, 并在100代左右收敛;从适应度均值曲线可见, 其大部分高于基本分类器最优线, 说明了设计良好的组合系统确实可以提高预测性能, 其大致向上的进化方向也说明了GA选择性集成的有效性。从表3和表4阴影所示的组合系统内部构成来看, 在 (t-2) 数据集上, GA优化系统选择了7个基本分类器, 组合系统预测准确率高于系统内个体最优准确率 (也是基本分类器最优准确率) 1.5%; (t-3) 数据集上选择了8个基本分类器, 组合系统预测准确率高于系统内个体最优准确率3.25%, 高于基本分类器最优准确率3%, 离标准年份t越远, GA优化组合系统的性能提高越明显, 进一步说明了该方法的有效性; 不同年份的最优组合系统并不是基分类器库前7个或8个性能较好的基本分类器组合, 基于CART构建的基本分类器性能较差, 但是在最优组合系统中分别占据3个和4个位置, CART算法的不稳定性为组合系统内部提供了较大的差异性, 即信息互补性, 表明在满足准确性的前提下, 提高系统内个体的差异性是提高系统性能的有效手段。

5 结论

多分类器组合预测是目前财务困境预测领域研究的热点。现有研究大多静态给定组合系统构成, 没有考虑当可供选择的基本分类器个数较多时所面临的选择性集成问题。因此, 本文提出了GA选择性集成多分类器模型, 该方法无需度量个体分类器之间的差异性, 直接以组合系统预测准确率为优化目标, 实现了组合系统结构的动态挖掘。以中国上市公司为对象的实证研究中, 通过与全集成模型的比较, 说明了选择性集成的必要性;通过与最优基本分类器以及系统内最优个体分类器进行比较, 证明了选择性集成的有效性;并且距离标准年份越远, 组合模型的优化效果越显著。本文的不足之处在于:建立模型过程所需实验参数较多, 并且对于如何确定合适的实验参数缺乏较好的理论依据, 所采用的遗传搜索需要较多的计算时间, 这是后续工作中需要进一步研究的问题。

摘要：为了更加有效地进行企业财务困境预测, 本文提出了基于遗传算法选择性集成的多分类器系统。与事先静态给定系统内部基本分类器组成不同, 该方法以组合系统预测准确率为优化目标, 无需度量各基本分类器之间的差异性, 可以动态挖掘最优组合系统。实证研究中以中国上市公司为研究对象, 以10折交叉验证准确率作为评价标准, 结果表明该方法显著优于全集成以及单分类器最优模型。

超文本的集成分类算法研究 篇4

关键词：文本分类,超文本分类,集成算法

随着Internet的迅速增长,WWW上超过20亿个网页是通过超链接互连的,这使得在Web上找到准确的信息日益困难。如何自动处理这些海量信息成为目前热门和重要的研究课题[1]。

智能信息分类是人工智能(Artificial Intelligence,AI)和信息分类相结合的一个交叉学科,是一种智能化的计算机信息分类系统,它模拟人类关于信息处理的思维过程和智能活动,实现信息知识的抽取、分类和检索,并向用户提供智能辅助。许多传统的分类算法是在研究人工智能领域中的机器学习(Machine Learning,ML)方法的基础上提出的[2]。通过智能方法,有效地自动分类与日俱增的信息成为信息处理的重要研究趋势之一。

超文本有别于普通的纯文本,包含有丰富的结构化信息,例如超链接、HTML标记、元信息和标题等等。这些结构化信息为提高分类效率提供了非常丰富而有效的资源,使得自动的超文本分类方法的研究变得越来越重要,同样也为自动文本分类提出了挑战。

文献[7]中Yang对近年来的工作加以分析,指出超文本分类一些未解决的问题,例如,利用超链接上的单词进行分类,对于Furnkranz所用的WebKB数据集可以提高分类精度[7],但对于Chakrabarti所用的IBM专利文档数据集却降低了分类性能[7]。为什么用类似的方法分类对于不同数据集效果不同?数据集的不同对分类性能有什么影响?此外,用不同的分类算法对分类性能的影响有什么不同?近年这些工作对这些问题都没有直接的比较和分析。

Yang对近年这些工作做了系统化的分析和比较,对于利用超文本信息进行分类总结出五条规则,并用三种传统分类算法(贝叶斯、最临近和最先顺序归纳学习算法)分别结合这五条规则进行超文本分类[7]。实验中采用WebKB和Hoovers等超文本数据集进行分析比较。Yang总结了一些利用超文本信息的规则,并且对于不同算法和不同的超文本数据集,就这些不同的信息规则做了直接的比较和总结,但是并没有对这些信息规则加以综合分析和利用。

总结现有对超文本分类的研究,工作利用超文本中不同于纯文本的各种信息进行自动分类,但仍只是初步的研究和分析,其中很多超文本分类的问题仍没解决。比如,这些工作往往针对某些超文本数据集的特点,发掘出一些规则来利用超文本信息,但不同规律和特点没有加以分析和综合利用;按某种规则使用超文本信息(如使用超链接)对某些数据集可以提高分类效率,对另一些数据集则降低分类效率;然而按某些规则使用超文本信息(如使用元信息数据)对大多数数据集都可以提高分类效率。由于超文本信息的多样化和灵活性,单独使用某种规则利用超文本信息,不能较全面的综合超文本信息,而且分类稳定性不高。本文利用神经网络集成利用多元超文本信息[7],以提高超文本分类效率。

以Yang所总结的超文本信息规则和实验结果为基础,综合利用超文本的各种多元化信息建立统计模型,提出利用超文本元信息的集成分类方法。

1 超文本分类模型

对于具体的超文本数据集使用以上所总结的规则,表现为使用不同的超文本信息。如对于WebKB数据集,用到的超文本信息有页面本身文字(page only规则)、链接上的文字(预分类规则)和HTML标题(元信息规则)等等。本文着重于综合利用各种使用超文本信息的规则,即协调各种抽取的超文本信息,来建立超文本分类器进行有效的超文本分类。

超文本分类模型如图1所示:

挖掘超文本信息及其规则,以及怎样表示超文本信息是研究超文本分类的关键。近年研究超文本分类的工作,往往分析某种的超文本数据集的特性,发掘超文本信息的某些规律来分类,但不同规律和特点没有加以分析和综合利用。由于超文本信息的多样化和灵活性,单独使用某种规则利用超文本信息,不能较全面的综合超文本信息,而且分类稳定性高。因此利用神经网络集成利用多元超文本信息,以提高超文本分类效率。

2 超文本元信息的集成分类方法(EHC)

超文本元信息的集成分类方法利用超文本的各种多元化信息规则建立超文本分类模型,即对于抽取到的数据集文档中的标题、超连接和标记等超文本特征项中的单词分别建立分类模型,然后根据各个分类模型建立神经网络,提出一种基于神经网络的集成分类算法(图2)。

首先,根据训练文本集分别建立KNN,NB和TFIDF的超文本分类模型;然后,构造一个BP网络,其中将KNN,NB和TFIDF的超文本分类模型结果作为BP网络的输入,输出为文档的类别。最后,对整个系统训练完成后,根据测试集来测试该算法的性能。进行加权处理后,再通过分类器进行分类,更好的综合协调的利用了超文本的多元结构化信息。

构建BP网络模型如图2所示:

其中输入层结点有12个,隐含层结点有10个,输出层结点有5个,输出层的期望输出为:

BP网络按照如下步骤进行训练

Step 1.网络初始化

Step 2.输入第一个学习样本

Step 3.求中间层的输入和输出

式中f是Sigmold函数。

Step 4.求输出层的输出

Step 5.计算输出层的误差

Step 6.计算中间层的误差

Step 7.调整各层的误差

Step 8.输入下一个学习样本。

3 实验与结果

3.1 数据集

我们采用三个数据集作为实验进行比较的超文本数据集:Web KB的两个子数据集Course(分5类共830篇超文本文档);Faculty(分5类共1124篇超文本文档);我们从Hoovers online(www.Hoovers.com)上搜集的1 500个公司网页(分航空、商务、计算机、金融和金属采矿5类,每类300个公司网页)构成hoovers-5数据集。

3.2 实验和结果

实验分为两部分:

第一部分:对传统分类算法进行实验。我们分别用不同超文本信息分别进行分类。用到的超文本信息有页面文字(page only规则)、HTML标题、HTML Meta(元信息规则)和超链接文字(预分类规则)。

用NB、KNN和TFIDF三种传统的文本分类器和超文本特征向量分别建立三种超文本分类器,进行实验并比较分析结果。实验中,我们用数据集的90%做训练集,10%做测试集。

实验结果如表1所示:

从表1中可以看出,对于WebKB的两个子集Course和Faculty,用超文本信息分类的精度比用页面文字分类精度都有一定提高;其中,用超链接文字信息分类精度较其他信息都稍高一些。这是由于WebKB的两个子数据集超链接信息比较多,而且数据集特点比较符合预分类规则(链接的网页往往具有相同的主题,属于同一类别)。此外,对于数据集Hoovers-5,用元信息分类比用页面文字分类精度有所提高,特别是用HTML Meta信息分类的精度提高显著;而用超链接文字信息分类精度较页面文本文字却有所降低。分析所搜集的Hoovers-5中的公司网页,发现有些网页含链接较多,所指范围较为广泛;而另外许多介绍公司各种信息的网页所含链接较少,而且对公司的类别没有一定代表性。综合分析,发现三种分类器对三个数据集用元信息分类都有较好的性能,元信息对于超文本分类具有一定的代表性。

第二部分:根据训练文本集分别建立KNN,NB和TFIDF的超文本分类模型,然后,构造一个BP网络,其中将KNN,NB和TFIDF的超文本分类模型结果作为BP网络的输入,输出为文档的类别。输入层结点有12个,隐含层结点有10个,输出层结点有5个。用数据集的90%做训练集,10%做测试集。实验结果如图3～图5所示:

图3～图5显示了对于三个数据集,单独用每种超文本信息与集成分类方法分类精度的情况。

首先,可以看出对于不同数据集和不同分类器,利用超文本信息进行集成分类取得好的超文本分类精度,优于各种单独使用不同超文本信息的分类精度,具有较好的性能。

其次,在超文本分类时,不同的分类方法对于在不同的数据集上取得的分类性能不同,ECB则在所有数据集上取得好的分类性能。比较单独使用资源的某种超文本规则,集成算法综合利用各种超文本信息,更好的利用超文本资源,分类具有较好的稳定性。

3.3 实验小结

综合利用超文本的各种多元化信息规则建立文本分类器,提出一种基于元信息的超文本集成分类算法。在三个数据集(WebKB的两个子集Course、Faculty以及Hoovers-5数据集),分别用NB、TFIDF和KNN三个分类器以及集成分类算法进行综合实验。实验结果表明,相对于单独利用某种超文本结构信息进行分类的方法,基于元信息的超文本集成分类算法具有较好的性能和稳定性。

4 结论

本文主要研究了信息分类中的超文本信息分类的多元化信息规则,分析了不同分类算法在不同规则中的分类性能。通过对抽取到的数据集文档中的标题,超连接和标记等超文本信息,以及文档内容本身分别建立分类模型,然后根据神经网络集成各个分类模型得出判别结果,提出一种基于元信息的超文本集成分类算法,该算法更好的综合利用了超文本的多元结构化信息。实验结果表明,相对于单独利用某种超文本结构信息进行分类的方法,基于元信息的超文本集成分类算法具有更好的分类性能。

参考文献

[1]Craven D,DiPasquo D,Freitag,et al.Learning to Construct Knowledge Bases from the World Wide Web[J].Artificial Intelligence,2000,118(1-2):69-113.

[2]Sebastiani F.Machine Learning in Automated Text Categorization[J].ACM Computing Surveys,34(1):1-47.

[3]Jaakkola T,Meila M,Jebara T.Maximum Entropy Discrimination[J].Advances in Neural Information Processing System,2000,12:470-476.

[4]Chen H,Dumais S.T.Bringing order to the web:Automatically Catego-rizing Search Results[C].In:Proceeding of CHI’00,Human Factors in Computing Systems,2000:145-152.

[5]Johannes Furnkranz.Exploiting Structural Information for Text Classi-fication on the WWW[C].In:Proceedings of IDA-99,3rd Symposiumon Intelligent Data Analysis.Number 1642 in Lecture Notes in Com-puter Science,Amsterdam,NL,Springer Verlag.Heidelberg.DE.1999:487-497.

[6]Joachims T,Cristianini N,Shawe-taylor J.Composite Kernals for Hy-pertext Categorization[C].In:International Conference on Machine Learning(ICML’01),San Francisco,CA,Morgan Kaufmann,2001:89-126.

[7]Yiming Yang,Sean Slattery,Rayid Ghani.A study of approaches to hy-pertext categorization[J].Journal of Intelligent Information Systems.2002,18(2/3):219-241.

[8]李蓉,叶世伟,史忠植.SVM-KNN分类器[J],电子学报,2002,30(5):745-748.

[9]董乐红,耿国华,周明全.基于Boosting算法的文本自动分类器设计,计算机应用[J],2007,27(2):384-386.

[10]沈学华,周志华.Boosting和Bagging综述[J].计算机工程与应用,2000,36(12):31-32,40.

[11]范焱,郑诚,王清毅,等.用Naive Bayes方法协调分类Web网页[J].软件学报,2001,12(09):1386-1392.

基于数据集成的多版本控制算法 篇5

1.1 数据集成概念

数据集成就是指将分布的、异构的独立信息源中的有用数据抽取出来,经过转换、传输并集成到目的数据库系统中,最终给用户提供一个统一的数据视图。

视图是定义在一个或几个基本关系上的导出关系,当视图中的元组被实际存储时,则称为实化视图[1]。实化视图的优点在于:对实化视图的查询可在预先存储的元组集合上进行,而对传统视图的查询则必须转换成对基本关系的查询。而且当基本关系发生变化时,就必须修改实化视图以反映这一变化。当数据源的数据发生变化后,实化视图即需做出相应的变换以保持数据与数据源的一致性,这一过程就称为实化视图的维护[2]。

1.2 数据的一致性程度

在数据仓库维护环境中,维护算法的选择除了要考察算法效率外,更重要的则需衡定其算法是否能够满足实际数据的一致性。文献[3-6]中提出了数据仓库环境下数据一致性程度的几个层次,在此,按一致性程度由低到高归纳如下:

(1)不一致(inconsistency):当所有数据源基表更新操作停止,视图维护操作完成以后,视图状态与数据源状态不一致(不正确性)。

(2)收敛一致性(convergence):当所有数据源基表更新操作停止,视图维护操作完成以后,视图状态与数据源状态保持一致。

(3)弱一致性(weak consistency):在视图维护过程中,视图出现的每一个状态都能反映数据源更新过程中相应的某一个有效状态。

(4)强一致性(strong consistency):在视图维护过程中,视图出现的每一个状态都能反映数据源更新过程中的某一时刻的有效状态。并且维护过程中视图状态之间的时序关系与其反映的数据源状态之间的时序关系一致。

(5)完全一致性(completeness):在强相容的前提下,数据源更新过程中的每一个有效状态都能找到与其对应的视图状态。也就是说数据源和视图之间的状态变化是一一对应的[3,4,5,6]。

2 视图维护算法分类

视图维护的算法可以分为:重新计算视图方法(recompute the view)、补偿查询方法(compensating queries)、自维护方法(self-maintanence)以及多版本控制方法(multiversion control)。

上述方法中,多版本控制方法已经成为当前的研究热点与焦点。在现有数据仓库产品中,由于对数据仓库的维护是定时进行的,所以数据的维护与读取在某种程度上是互不相关的,但在联机维护环境下,二者之间的冲突却是无可避免的。为了提高查询效率,系统可能就要保留部分汇总视图,如何存取这种视图数据并确保其一致性就成为实体化视图维护的一个关键问题。多版本控制技术即利用版本控制的办法,对不同的数据标以不同的版本戳,在逻辑上即将要维护的与要查询的数据彼此分开,避免了死锁等待的发生,保证了数据的一致性。多版本控制技术为解决实体化视图的联机维护和一致性问题提供了一条新途径[7]。文中对多版本控制技术进行了深入的探讨,具体阐析如下。

3 多版本控制算法

3.1 多版本控制算法下的事务和会话

不需考虑数据库版本信息,维护事务的情况如图1所示。由图1可以注意到维护事务执行的同时,用户事务也在执行,这就意味着维护事务可执行得更久一些或者更频繁一些,同时使得用户事务在数据仓库修改期间也能够执行。

有关会话的策略亦需参照图1所示。由图1可得用户必须能够检测到其会话周期是否已经结束,可以用几种方法来实现。当用户准备去访问一个在用户会话开始之后已被多个维护事务修改过的元组的时候,用户能够检测其会话周期是否已经终止。在这种情况下,正确的元组版本是得不到访问的,因为当前的版本和更新以前的版本都被最近的更新所维护。

3.2 修改关系表

数据仓库中的每一个关系表都需要用额外的属性去扩充。例如,设A={A1,A2,…,An}是关系R的初始化属性集合,A′={A1,A2,…,Ak}是A的属性子集,这些属性都是可更新的。R的扩展表为{tupleVN,operation,A1,A2,…,An,A1p,A2p,…,AkP},其中,Aip表示更新前的属性,与可更新的属性Ai相对应。属性tupleVN包括维护事务的版本号maintenanceVN,该事务对应最近的元组修改;属性operation包括了作用在这个维护事务上的逻辑操作;属性{A1,A2,…,An}包括着元组属性的当前值,更新前的属性{A1p,A2p,…,AkP}则包括被维护事务更新前的可变化的属性值(在执行插入操作的情况下,更新前的属性为空,在删除操作的情况下,则包括了删除前的值)。

在最坏的情况下,即每一个属性都是可更新的时候,则表示每一个元组的多个版本均需要数据仓库的多倍存储空间。但是最经常的,数据仓库中有很多属性并不能更新。例如,数据仓库总会包含多个汇总表,这些汇总表通常会被认为是select-from-where-groupby的聚集视图。虽然维护事务能在一个汇总表中对元组进行插入删除操作,但是那些group-by属性的值是不能修改的,只有那些表示聚集函数结果的属性才是可更新的。因此,对汇总表而言,本算法所要求的额外存储空间是很小的。

3.3 对用户的算法

现在将用提取一个元组的正确版本以便用户能访问到数据库的某个一致性状态来说明对用户的算法。常见的方法是通过查看tupleVN,使用户得以确认应该访问元组的当前版本,还是访问元组更新前的版本。并且,通过查看operation属性,当前属性,以及更新前的属性,将能得到任一元组的恰当状态。

用户所访问元组的版本就是在数据库版本sessionVN之中的当前版本,同时这也意味着该版本包括了所有满足maintenanceVN<=sessionVN的维护事务的作用影响,而没有包含其他维护事务的作用影响。

前已叙及,tupleVN包括着最后一次修改元组的维护事务的maintenanceVN,在此有3种情况要考虑:

(1)sessionVN>=tupleVN:访问元组的当前版本。

(2)sessionVN=tupleVN-1:访问元组更新前的版本。

(3)sessionVN

第一种情况表明,元组当前版本的状态为:该版本与当前数据库版本tupleVN是一致的,也就是相同的。第二种情况说明,更新前的元组版本的状态为:此版本就是当前数据库版本,也就是tupleVN-1。第三种情况,也就是会话到期的这种情况就表示了既然只有元组的2个状态版本可以访问,那么此时已经无法确定数据库版本中的元组状态是tupleVN-2还是更早的。因此在这种情况下,应该通知用户开始一个新的会话。

根据operation属性,应如何提取元组当前和更新前的版本,则如表1所示。比如,在元组更新前的版本被访问并且operation=“insert”的状况下,元组就应该被忽略。

3.4 对维护事务的算法

当一个维护事务访问一个元组的时候,总是访问当前的版本。因此,必将遵循表1的第一行去访问元组。

当一个维护事务对一个元组进行插入,删除,或者更新操作的时候,多个动作将会发生,以便维护元组当前的版本和更新前的版本。所发生的动作列置如下:

(1)在一些情况下,当前的属性值被移植为更新前的属性值,以便元组更新前的版本得到保存。

(2)当前的属性值设置为维护事务操作后定义的值。

(3)tupleVN设置为maintenanceVN。

(4)operation设置为逻辑操作(insert,delete,或者update)。

这些操作被维护事务作用在元组上。由维护事务作用的逻辑操作结果与作用在元组上的物理操作结果可能会有所不同。例如,当一个逻辑操作是删除操作的时候,元组通常并没有在物理上被从数据库中删除,这是因为元组更新前的版本可能还需要被用户所访问。一旦逻辑上已经删除的元组不再为用户所需要,那么这些元组就将被进行垃圾回收,该回收机制即是通过周期的运行以在物理上将其删除。此后,将在下一步的工作中去检验这个垃圾回收机制。

另外,在属性operation中的操作记录都要表现出由维护事务作用在元组上的所有操作的网络效应。举例说明,如果一个维护事务插入了一个元组,然后在该维护事务中更新了这个元组,那么网络效应就仍然表现为一个插入操作。如果operation错误地进行了更新操作,那么当用户查看元组更新前的版本时,用户访问到的将是更新前的属性值,而不是忽略这个元组。

(5)在元组上执行恰当的物理操作。

作用在元组上的准确操作依赖于3个条件:维护事务的操作,元组的tupleVN属性值和元组的operation属性值。假如要进行以下操作:插入,更新和删除。则将maintenanceVN值赋给维护事务,再将元组已经存在的值指给tupleVN和operation,这样就表明了作用在元组上的正确的物理操作,以便当前和更新前的元组版本进行保存。设:

(1)CV表示元组的当前属性值。

(2)PV表示元组更新前的属性值。

(3)MV表示在维护事务操作中说明的属性值(如果这个维护事务操作是一个插入或者是一个更新操作)。

因此,表达式“PV<-CV”说明将元组更新前的属性值设置为相应的当前属性值,“CV<-MV”则表示将元组当前的属性值设置为维护操作中作用的属性值。

注意到,既然在一个时刻只能有一个维护事务在执行,那么就可知道tupleVN<=maintenanceVN。每个表的第一行指明了当元组版本号小于维护事务版本号的时候,将发生的动作,即要进行的操作。当tupleVN=maintenanceVN的时候,元组被同一个维护事务预先修改了。此种情况下发生的动作将在每个表的第二行作以说明。正如前面所提到的,赋值在第二行的operation值说明了由作用在这个元组上的维护事务所采取的全部操作将产生的影响。

4 结束语

本文主要介绍了一种数据仓库中基于数据集成的多版本控制算法。重点介绍了数据仓库中基于数据集成的多版本控制算法中事务和会话如何进行、关系表如何修改、对用户算法描述以及对事务维护算法的描述。今后还要进一步改善多版本控制算法,使得在并行的同时进一步提高效率。

参考文献

[1]HAMMER J,GARCIA-MOLINA H,WIDOM J,et al.The St-anford data warehousing project[C]//IEEE Data EngineeringBulletin,1995,18(2):41-48.

[2]WIDOM J.Research problems in data warehousing[C]//Proce-edings of the 4th,Int’L Conference on Information and Knowl-edge Management(CIKM),1995,19(1):124-129.

[3]ZHUGE Y,GARCIA-MOLINA H,HAMMER J,et al.View m-aintenance in a warehousing environment,In SIGMOD,1995,32(1):256-262.

[4]ZHUGE Y,GARCIA-MOLINA H,WIENER J L.The strobealgorithms for multi-source warehouse consistency.PDIS'2005,Miami Beach,Florida,1996-12.

[5]ZHUGE Y,GARCIA-MOLINA H,WIENER J L.Consistencyalgorithms for multi-source warehouse view maintenance.Dist-ributed and Parallel Databases Journal(DAPD),Kluwer,1997-07.

[6]ZHUGE Y,WIENER J L,GARCIA-MOLINA H.Multiple vi-ew consistency for data warehousing.ICDE'97,Birmingham,UK,1997-04.

选择性集成算法 篇6

网络流分类是认识、管理、优化各种网络资源的重要依据, 随着动态端口和加密技术的广泛使用, 传统的基于端口号映射和基于载荷分析的网络流量分类方法[1]不再具有普遍适用性。为克服上述方法的不足, 许多学者运用基于流统计特征的机器学习[2]方法来解决流量分类问题, 该方法利用流在传输层表现出的各种特征统计信息进行分类, 不受动态端口、载荷加密及网络地址转换的影响。但绝大多数的网络流量分类方法的性能在分类器间的互补性和预测阶段的开销方面受限, 难以适应网络环境的动态变化, 在不同环境下分类效果不明显。

集成学习[3]通过对样本学习训练出若干个分类器 (称为基分类器) , 然后通过某种规则将这些分类器的分类结果进行整合以解决某一具体的问题。传统的集成学习方法如Bagging、Adaboost等都是将所有分类器进行集成, 而近来研究发现, 选择部分分类器进行集成学习比选择所有的分类器进行学习具有更好的泛化性能, 这种方法称为选择性集成[4]。国内外学者对选择性集成的研究主要集中在基分类器的选择上, 一方面, 通过剔除对集成学习有负面影响的基分类器, 进一步提高分类精度;另一方面, 通过去掉冗余的基分类器, 降低预测时间复杂度。

本文基于流统计特征的机器学习方法, 同时考虑单个基分类器的预测精度和多个基分类器间的多样性, 通过选择性集成方法MCSE对多个分类器进行集成来实现网络流量分类。在Moore数据集上进行实验, 实验表明, 与同类集成学习和选择性集成算法相比较, 本文提出的算法在分类准确率、分类器选择时间和目标集成分类器大小方面更具优势。

1 国内外研究现状

分类器选择性集成学习的目的是在不降低甚至进一步提供原数据集成学习机预测精度的前提下, 尽可能减少参与集成学习的基分类器数目。周志华提出基于遗传算法的选择性集成算法GASEN[4], 通过遗传算法对每个分类器的权重进行调整, 直至各分类器权重的分布接近全局最优, 最后选择权重大于阈值的分类器参与集成, 但遗传算法需要大量的计算和存储空间;基于分簇的选择性集成模型 (CPF) [5], 把所有的基分类器进行分组, 在各个分组内部进行选择, 其缺点是运算量和存储空间占用大, 选择的效率不佳;方向排序OO (Oriented Order) 算法[6]是目前速度最快、空间效率最好的选择性集成算法, 其缺点是无法给定一个恰当的名次判断标准, 得到的集成分类器规模较大。

此外, 盛高斌针对小数据量的有标记样本问题, 提出一种基于半监督回归的选择性集成学习算法SSRES[7]。同时用有标记样本和未标记样本训练学习器, 使用选择性集成算法GRES对不同学习器进行适当的选择, 但该方法仅局限于回归情况;汪为汉等人[8]提出基于贝叶斯学习的集成流量分类方法, 利用测试集获得各贝叶斯分类器的权重, 并通过加权平均组合各分类器来实现网络流量分类, 此方法虽然在准确率上有一定提高, 但计算开销较大;孔蓓蓓等人[9]提出一种多分类器联合的集成网络流量分类方法, 通过对不同算法的分类器采用投票和实例选择性集成来实现流量分类, 增加实现的复杂度和计算开销。

2 选择性集成学习流量分类框架

选择性集成网络流量分类框架的关键是如何从若干基分类器中, 挑出差异性大、分类能力强的基分类器集合, 并准确地组合各个体分类器的输出结果, 来更好地提升集成分类器的整体性能。如图1所示, 选择性集成的思想是从多个分类器中选择一部分具有代表性的分类器进行组合, 剔除掉分类性能差且具有冗余的分类器, 从整体上提高分类器的泛化能力。

如图2所示, 在选择性集成基本思想的基础上, 提出了选择性集成网络流量分类框架。网络流量分类就是把具有相同五元组 (源IP、目的IP、源端口、目的端口、协议类型) 的网络流 (flow) 按照不同的应用类型分类[10]。整个过程可分为四个阶段:第一阶段, 流量捕获。利用流量捕获软件如Net Mate、Netflow、Ether Peek等从真实的网络环境中捕获数据包, 并将其抽象为包含网络属性的流向量;第二阶段, 特征提取和选择。根据捕获流量统计属性 (如分组数量、分组到达时间间隔、最大分组长度、分组数量等) , 进行特征提取和特征选择, 得到最优或者次优的特征子集用于训练分类器模型。第三阶段, 多分类器选择性集成。选取网络应用类型多样、规模适中的样本组成训练集, 结合相关的流量分类算法如支持向量机、贝叶斯、决策树和神经网络等对其进行训练, 构造多个独立的基分类器, 采用选择性集成的方法, 从多个级分类器中选出一部分差异性大且分类能力强的基分类器来提高集成分类器的效果;第四阶段, 分类模型测试。为了验证流量分类基分类器的可靠性, 需要选取一定的测试集, 验证网络流量分类的准确性, 并根据验证结果对分类算法进一步进行优化和改进, 以确保分类的有效性。

3 多分类器选择性集成网络流量分类方法

3.1 分类器差异性度量

分类器差异性体现在至少有分类器对其它分类器预测错误的样本作出正确的预测。比较典型的是Castro[11]的人工免疫算法, 周志华的基于遗传算法的GASEN[4], 但人工免疫和遗传算法在选择部分个体分类器的时间复杂度较高。Kuncheva[12]在研究成果中总结了10种差异性度量方法, 常见的分类器差异性度量方法包括Q统计量法、相关系数法、不一致度量法、熵度量法、双错度量法。根据Kuncheva等人对各种度量方法进行的试验来看, 以上各种度量方法分类准确率近似, 但由于不一致度量方法具有较好的可理解性和稳定性, 被广泛地运用于度量分类器间的差异性。分类器di和dj之间的不一致度量定义如下:

对不同的分类目标, N11与N00分别表示对分类样本均预测正确和均预测错误, N10表示基分类器di预测正确而dj预测错误, N01表示基分类器di预测错误而dj预测正确。dij的值的变化范围在[0, 1]之间, dij值越大, 表示分类器间的差异性越大。

3.2 改进不一致性度量方法

为选出具较大差异性的分类器, 需要将分类器与其他分类器进行比较, 得出相应的差异性值。应用不一致度量策略度量n个分类器间的差异, 可得如下所示的分类器差异性矩阵D, 其中dij表示分类器di与dj的差异性值。

将分类器差异性矩阵D中各分类器的差异性与平均差异性值进行比较, 选择差异性值大于平均差异性值的分类器参与分类器的集成, 此时比较的次数为nxn。注意到, 当分类器的数目n较大时, 比较次数是n2, 急剧增加了算法计算的复杂度和计算存储空间, 为减少算法的比较次数, 降低计算的时间复杂度和空间复杂度, 本文对该方法进行改进, 作了进一步的简化:

令:

其中, 表示分类器di在整体分类器中的差异性值, 则分类器差异性矩阵可得如下优化:

式 (3) 表示第i个分类器di与其他所有分类器差异性值总和的平均值, 本文将该值作为分类器di在整体分类器中的差异性值。

整体分类器平均差异性值是指n个分类器差异性值总和的平均值, 用AV表示整体分类器平均差异性值, 计算公式为:

此时, 选取具有较好差异性的分类器的策略为:当, 则选重分类器i参与最后的集成预测, 否则将其删除, 最终选出m (m≤n) 个具有较好差异性的分类器, 这个过程的比较次数为n, 有效地减少了计算的开销, 提高了效率。

3.3 MCSE方法描述

MCSE方法结合半监督学习技术, 同时利用已标记的流量样本和无标记的流量样本训练分类器, 设定分类器准确率阈值λ以保证选择具有较高正确率的分类器。MCSE分两阶段对多分类器选择性集成:第一阶段选择具有较高正确率的分类器, 以保证分类器集的鲁棒性;第二阶段筛选具有较好差异性的分类器, 以保证分类器集的高效性。MCSE方法的描述如下:

阶段一选择分类识别率高的基分类器

输入:有标记的网络流量样本集L, 无标记网络流量样本集U, 测试样本集Y

输出:S个分类识别率高的基分类器集PS

(1) 用样本集L和U同时训练N (N>S) 个分类器Ci (1≤i≤N) 。

(2) 用Y测试各个基分类器di, 计算每个分类器的分类识别准确率Ri, 得R={R1, R2, …, Rt}。

(3) 对集合R中的元素按降序进行排列, 取大于准确率阈值λ的分类器, 得S={d0, d1, …, dn-1}。

阶段二从识别率高的基分类器中选出差异性大的分类器

输入:基分类集S

输出:新的差异性集合C

(1) 根据不一致性度量公式 (1) 计算分类器集Pk中各分类器间的差异性值dij, 得分类器差异性矩阵D;

(2) 令, 得优化的分类差异性矩阵DS;i=1

(3) 计算整体分类器的差异性平均值

(4) 选择差异性分类器:

为了从所有的分类器中选出同时满足出泛化能力强、差异性大条件的基分类器, MCSE方法将“选优”和“剔差”的思想相结合, 首先选出分类精度较高的分类器, 以丢弃可能对选择性集成学习造成负面影响的基分类器, 再剔除选出的分类器集中相关或者冗余的基分类器, 剩余的就是用于集成的个体分类器。在剔除基分类器的过程中, MCSE方法利用半监督学习能同时利用有标记样本和无标记样本的优势来训练初始分类器, 并用改进的不一致度量方法对分类器的差异性进行评估, 相比多对多的选择方法, 该方法能明显减小搜索空间, 提高多分类器选择性集成系统的性能。

4 实验与结果分析

4.1 实验数据

实验采用剑桥大学Moore教授在文献[13]中使用的数据集[14], 本文称之为Moore-set, 该数据集共包含377526个网络流量样本, 分为10大类, 每类的统计信息如表1所示。由于IN-TERACTIVE和GAMES的数量较少, 不具代表性, 因此在本实验中不采用这两种数据。

每个在Moore-set中的样本都是完备的TCP双向流, 有249种特征属性, 由端口号等网络属性和平均间隔时间等统计属性组成, 最后一项属性为分类目标属性, 表明该样本的流量类型。众多的特征中存在不相关或者冗余的特征, 首先使用FCBF (fast correlation-based filter) 特征选算法进行特征选择。实验所用的数据处理和分析工具是Matlab 7.1.0和weka3.7.0。

本文选择Bagging、GASEN和MCSE算法作对比实验, 其中, Bagging是最传统、最常用的集成算法, 将所有分类器直接进行集成。GASEN是典型的选择性集成算法。

实验采用重复抽样的方式, 以训练出不同类型的分类器, 从Moore-set中抽取每类应用的1%构成训练集trian-set和每类应用的1%为测试集test-set。为进一步验证选择性集成的作用, 分别用Bagging、GASEN和MCSE算法进行网络流量分类, 比较基分类器数目在20、40、60、80、100、120和140下的分类性能。评价指标是分类准确率、分类器训练时间和参与集成的分类器数目。其结果分别如图3-图5所示。

4.2 实验结果分析

在分类精度方面, 两种选择性算法MCSE、GASEN在不同基分类器数目下, 分类精度都优于Bagging算法。当基分类器的数目在20以GASEN的分类精度与MCSE方法无太大的差距, 但当基分类器的数目超过20后, MCSE的分类精度开始不断提高, 明显高于GASEN, 选择性集成的正面效应越来越明显。在训练时间方面, Bagging方法直接对所有基分类器的预测结果进行多数投票法组合, 需要考虑的基分类器数目较多, 消耗了更多的时间, GASEN选择性集成算法是基于遗传算法的, 需要运算和存储空间开销都较大, MCSE简化了比较模式, 从而减少了比较时间开销, 具有较好的优势。从图5可以看出, 选择性集成算法选择出来的基分类器数目远远小于原始的基分类器数目, 当基分类器的数目大于40的时候, MCSE选择性集成方法的优势越来越明显。

实验结果表明, 从基分类器的精度和差异性来设计和改进多分类系统是非常有效的。MCSE方法结合基分类器个体的精度和基分类器间的差异性, 避免了选择过程中重复进行基分类器预测结果, 能剔除对提高泛化能力不起作用的基分类器。但选择性集成必须在具备一定规模的分类器上才能发挥其作用, 因为对许多算法, 集成分类器越小, 越不容易被分辨出性能不佳的基分类器, 选择性过程中越可能将有用的基分类器丢弃。本实验中, 当分类器规模超过40后, MCSE选择性集成的优势越越来越明显。

5 结语

本文在基于选择性集成网络流量分类框架下, 提出了一种多分类器选择性集成的网络流量分类算法, 改进不一致性度量策略, 将单个分类器的精度和多个分类器间的差异性有机结合进行选择性集成, 比同类算法具有更好的分类性能。在高速网络环境中, 下一步的研究工作是:把增量学习技术运用到选择性集成方法中, 结合高性能计算平台, 研究选择性集成算法的并行化, 选择尽可能少的基分类器进一步提升流量分类的性能。

摘要：针对多分类器集成方法产生的流量分类器在泛化能力方面的局限性, 提出一种选择性集成网络流量分类框架, 以满足流量分类对分类器高效的需求。基于此框架, 提出一种多分类器选择性集成的网络流量分类方法 MCSE (Multiple Classifiers Selective Ensemble network traffic classification method) , 解决多分类器的选取问题。该方法首先利用半监督学习技术提升基分类器的精度, 然后改进不一致性度量方法对分类器差异性的度量策略, 降低多分类器集成方法实现网络流量分类的复杂性, 有效减少选择最优分类器的计算开销。实验表明, 与Bagging算法和GASEN算法相比, MCSE方法能更充分利用基分类器间的互补性, 具有更高效的流量分类性能。

选择性集成算法 篇7

近年来,Web2. 0技术获得了迅速发展,而与此同时,微博作为一种新兴的网络交流媒介,正因其独具的及时性、简洁性和对信息传播的便捷性特点[1],吸引了越来越多的使用者和研究者。以国内的新浪微博为例,目前其上的注册用户已超过3亿,用户每日的发博量则突破1亿条[2]。微博中用户发表的大量信息直接反映了该用户本体对某个事件或者政府出台的某项政策的反应和倾向。而且,情绪作为人的内心感受和表达,在判读其对事物的观点倾向具有重要作用[3]。可以说微博中涉及到的任何观点都与作者的情绪有着紧密的联系,因而开展微博情绪的识别和划分研究对于分析微博中海量的评论信息即具有实际现实的参考价值。但目前大部分的微博情绪分析却只是集中在粗粒度的情绪划分( 也就是有无情绪的判断) ,这在某些情况下已经无法满足对文本信息处理的高精要求。基于此,本文根据对目前分类方法的研究提出了一种用于对微博进行细粒度情绪划分( 也就是文本情绪具体类别) 的集成算法。具体来说,就是对于一条微博,先识别其是否包含情绪,而对于包含情绪的微博,则需判别其具体的情绪分类。

本文第0节分析了微博情绪识别的背景和意义,简要介绍了本文的研究内容。第1节概略介绍了微博情绪细粒度划分的目标以及在微博情绪方面国内外的一些研究现状。第2节框架性地提出了本文针对微博情绪细粒度识别的总体方案,第3节完整给出了情绪细粒度识别的关键性技术,第4节则是集成算法的设计,而且通过实验结合其他的算法对比了对情绪分类的效果,第5节即总结了本文工作的不足以及对下一步研究的展望。

1相关工作

细粒度的微博情绪划分包含两个方面,首先判断一条微博是否包含情绪,然后对于包含情绪的微博再进行细粒度的情绪划分,判断出该微博博主的主要情绪。针对于目前对情绪的分类[4],即anger( 愤怒) 、disgust( 厌恶) 、fear( 恐惧) 、happiness( 高兴 ) 、like ( 喜好 ) 、sadness ( 悲伤 ) 、surprise ( 惊讶) 、none( 无情绪) ,细粒度的情绪划分旨在能够对一条微博进行上述分类的单分类输出。

目前,国内外针对微博情绪方面取得了一定的研究成果。Alec等使用微博中的表情符号来标注正负情绪的训练集,并通过训练集运用距离监督的方法对微博信息解决了正负情绪的自动分类[5]。Aman等则通过一种基于知识的方法实现句子级的情绪识别[3,6]。在此基础上,Quan Changqin等使用情绪词对句子的情绪进行了识别,同时也研究了基于情绪词的句子级情绪分析[3,7]。进一步地,刘欢欢等人针对微博语料中类别样本数不平衡的问题,提出了一种提高情绪识别方法性能的样本集成方法,主要是针对微博粗粒度的划分,即判断其是否包含情绪[3]。另外,庞磊等人又通过表情图片和情绪关键词对微博语料进行收集和标注,而且将情绪知识运用到了中文微博的情感分类方面[8]。

由此可见,目前对微博情绪的分析研究仍然主要集中在粗粒度情绪识别,一方面是有无情绪的识别,另一方面是正负情绪的识别。微博作为一种开放化的社交服务,无论在商业领域或是在管理领域都有着极高的应用价值。企业可以将其作为一个理想的营销平台,而政府则可凭此了解人们对社会公共事件和热点问题的看法观点。但由于其特有的语言风格和本身内容信息的多样、海量等特点,粗粒度的情绪划分在某些情况下已经不能满足当前发展变化的要求,因而对微博情绪的细粒度划分将会日益突显其核心且先进的研究价值。

2情绪细粒度识别的总体方案

图1给出了情绪细粒度识别的总体流程图,从图中可以看到细粒度划分微博情绪的总体流程是先扩展本体库,在大连理工构建的情感本体词汇库的基础上扩展针对微博中网络用语的词汇,而后对测试集和训练集中的微博进行分词。分词结束后,将根据一定规则统计出词语中用于贝叶斯分类的特征项,再通过特征项进行微博有无情绪的识别。下一步,即对测试集和训练集中有情绪的微博文本进行向量化处理,采用K最近邻算法,计算待预测情绪微博与已标注情绪微博的向量相似度,从而获取待预测微博的细粒度情绪。

3关键性技术

3. 1扩展本体库

本文对微博的情绪分类识别沿用大连理工大学建立的情感词汇本体。该资源从不同的角度描述一个中文词汇或者短语,包括词语词性种类、情感类别、情感强度连同极性等信息。该本体库的情感共分为7大类21小类,具体来说,7类为乐、好、怒、哀、惧、恶、惊; 21类为快乐( PA) 、安心( PE) 、尊敬( PD) 、赞扬( PH) 、相信( PG) 、喜爱( PB) 、祝愿( PK) 、愤怒( NA) 、悲伤( NB) 、失望( NJ) 、疚( NH) 、思( PF) 、慌( NI) 、恐惧( NC) 、羞( NG) 、烦闷( NE) 、憎恶( ND) 、贬责( NN) 、妒忌( NK) 、怀疑( NL) 、惊奇( PC) ,情感强度分为1,3,5,7,9五档,9表示强度最大,1为强度最小[4]。

微博作为目前流行的一种互联网应用,内容中综合着各式各样的网络用语,因此研究从4 000条已经人工标注了情绪分类的新浪微博中人为地筛选出常用的网络用语和所有的QQ表情所代表的词语以及对情绪识别有表征意义的其他词汇,从而完成了对极性和强度等相应属性的标注,由此获得了对情感本体库的有效扩展。

3. 2分词

针对于待分类的每条微博,首先采用中科院计算所开发的ICTCLAS分词系统进行分词,但考虑到微博语言的特殊性,研究中构建了分词器中特有的停用词库。这样做是因为在微博的情绪识别中,有很多诸如语气词之类的所谓停用词在情绪识别的过程中都发挥了重要的表征作用。另外,研究中进一步将情绪识别所用到的大连理工构建的情感词汇本体库和扩展的网络语言情感词汇库加入到分词器的用户词典以保证分词器对微博语句分词的准确性。

3. 3特征项提取

为了便于对微博进行有无情绪的贝叶斯分类,则对训练集中的每条微博进行了科学的抽象,即进行了特征项的提取。而将微博进行分词之后,就要统计出各个词在有无情绪两种情况下分别出现的次数,再会选择出一部分在有无情绪这两种情况下出现次数差别较大的词,并将其作为特征项。

3. 4文本表示

文本表示是指将文本从一个非结构化格式转化成计算机可识别的结构化格式的处理过程[1]。针对于那些包含情绪的微博,在此选择的文本表示模型则是向量空间模型,也就是将微博文本向量化。根据本体库的构建规则,可将每条微博表示成21维的向量。其中,每一维的分量相应代表本体库中的每一个具体的小情感分类,即每条微博均有21个小类情绪特征。并且,每个分量值将依赖于本体库,如果微博中的词能与本体库中的词相匹配,则将该词的强度作为分量值,出现多个词的小情感类别相同的情况就将各个词对应的强度累加作为分量值; 而对于那些小情感类别中没有出现词的情况,则在向量中对应的该分量值将设定为零。例如对于如下的一条真实的微博: “妹妹2年多的顽固性失眠,这次经刘医生3次针术后,已连续一周安然入睡到自然醒,我真高兴。”经过分词之后该微博与本体库匹配的词为: 顽固、失眠、安然、自然、高兴。在本体库中,顽固属于NN( 贬责) ,强度为3; 失眠属于NE( 烦闷) ,强度为5; 安然和自然都属于PE( 安心) ,强度分别为5、3; 高兴属于PA( 快乐) ,强度为5。那么对于该微博形成的21维向量的各分量值即可表述为:PA( 5. 0) ,PE ( 8. 0 ) ,PD ( 0. 0 ) ,PH ( 0. 0 ) ,PG ( 0. 0 ) ,PB ( 0.0) ,PK( 0. 0) ,NA( 0. 0 ) ,NB( 0. 0 ) ,NJ( 0. 0 ) ,NH( 0. 0 ) ,PF( 0. 0) ,NI( 0. 0) ,NC( 0. 0) ,NG( 0. 0) ,NE( 5. 0) ,ND( 0. 0) ,NN( 3. 0) ,NK( 0. 0) ,NL( 0. 0) ,PC( 0. 0) 。

4算法设计与实验分析

4. 1算法思想

本文对微博细粒度情绪划分采用朴素贝叶斯和K最近邻的集成算法[9]。其中,用朴素贝叶斯算法进行大粒度的划分,也就是有无情绪的划分; 在此基础上,针对包含情绪的微博,即运用K最近邻的算法进行细粒度的情绪划分。

根据算法的总体思想,文中构建了朴素贝叶斯 - K最近邻的集成算法,对于大粒度的情绪划分,主要有两个类别:CY,CN分别代表有情绪的类别和无情绪的类别,其伪代码如下:

在上述算法的基础上针对有情绪的微博进行细粒度的情绪划分,主要有七个类别: anger( 愤怒) 、disgust( 厌恶) 、fear( 恐惧) 、happiness( 高兴) 、like( 喜好) 、sadness( 悲伤) 、surprise( 惊讶) ,而在运算之前先要将待测试微博和训练微博实施向量化操作。其伪代码具体实现如下:

输入: 含有情绪的微博向量( 集) STS,训练集中含有情绪的微博向量( 集) TS

输出: 每条微博的细粒度情绪

4. 2实验设置

实验使用的语料是由计算机学会发布的训练语料,该语料是基于相对细粒度情绪标注规则的语料库,以XML文档格式组织,包括了微博的整体细粒度情绪标注以及单个句子的细粒度情绪标注。语料主要来自新浪微博,共有4 000条微博数据。语料中有8种基本的情绪: 即anger( 愤怒) 、disgust( 厌恶) 、fear ( 恐惧) 、happiness ( 高兴) 、like ( 喜好) 、sadness( 悲伤) 、surprise( 惊讶) 、none( 无情绪) 。

实验中使用了3种分类方法: 支持向量机分类方法、K最近邻分类方法、以及朴素贝叶斯 - K最近邻集成方法,针对衡量分类的性能,采用准确率作为细粒度情绪划分的衡量标准,准确率计算如公式( 1) 所示:

其中,#sample_correct是被正确划分测试样本的数目,#sample_proposed是提供的测试样本总数。

4. 3实验结果分析

实验使用的训练语料中共有4 000条微博数据,其中有情绪的微博为2 647条,无情绪的微博为1 533条。在这次实验中,将用3 500条微博作为训练集,其中包含有情绪的2172条,来训练分类模型,而用剩下的500条微博来做测试。使用SVM做8类分类预测,特征值的计算来源于对大连理工本体库扩展后的词汇,使用21维情绪作为最终的特征,准确率为46. 8% 。使用K最近邻算法,用待测试的500条微博特征向量分别与训练集中的3 500条微博特征向量进行余弦相似度计算得到3 500个相似度值,并取K = 21( 试验中得到) 个最大值,对这21个分量情绪做相似度累加,累加和最大的情绪将作为预测情绪,准确率为51. 6% 。使用基于朴素贝叶斯 - K最近邻集成算法,先通过朴素贝叶斯进行有无情绪的识别,在此基础上,对有情绪的微博,则用K最近邻算法进行细粒度的情绪划分,做法同上,准确率为60. 6% 。图2为分别使用支持向量机分类方法、K最近邻分类方法、以及朴素贝叶斯 - K最近邻集成方法的情绪细粒度分类的效果。

由图2可以很直观地看出,基于朴素贝叶斯 - K最近邻的集成方法对微博细粒度情绪分类的效果要明显好于其他两个方法,而其提升的幅度已然都超过了5% 。

5总结与展望