基于不均衡样本重构的加权在线贯序极限学习机

摘要：针对现有学习算法难以有效提高不均衡在线贯序数据中少类样本分类精度的问题，提出一种基于不均衡样本重构的加权在线贯序极限学习机。该算法从提取在线贯序数据的分布是否用特征更恰当？这里主要想表达提取数据内在的分布规律，还是觉得用特性好一些。特性入手，主要包括离线和在线两个阶段：离线阶段主要采用主曲线构建少类样本的可信区域，并通过对该区域内样本进行过采样，来构建符合样本分布趋势的均衡样本集，进而建立初始模型；而在线阶段则对贯序到达的数据根据训练误差赋予各样本相应权重，同时动态更新网络权值。采用UCI标准数据集和澳门实测气象数据进行实验对比，结果表明，与现有在线贯序极限学习机（OSELM）、极限学习机（ELM）和元认知在线贯序极限学习机（MCOSELM）相比，所提算法对少类样本的识别能力更高，以澳门气象数据为例，所提算法对少类样本的预测精度分别比其他三种算法提高了22.87%、25.76%和22.42%，且所提算法的模型训练时间与其他三种算法相差不大。结果表明在不影响算法复杂度的情况下，所提算法能有效提高少类样本的分类精度。

关键词：样本重构；极限学习机；主曲线；过采样；不均衡数据

中图分类号： TP181 文献标志码：A

英文摘要

Abstract：Many traditional machine learning methods tend to get biased classifier which leads to low classification precision for minor class in imbalanced online sequential data. To improve the classification accuracy of minor class， a new weighted online sequential extreme learning machine based on imbalanced samplereconstruction was proposed. The algorithm started from exploiting distributed characteristics of online sequential data， and contained two stages. In offline stage， the principal curve was introduced to construct the confidence region， where oversampling was achieved for minor class to construct the equilibrium sample set which was consistent with the sample distribution trend， and then the initial model was established. In online stage， a new weighted method was proposed to update sample weight dynamically， where the value of weight was related to training error. The proposed method was evaluated on UCI dataset and Macao meteorological data. Compared with the existing methods， such as Online SequentialExtreme Learning Machine （OSELM）， Extreme Learning Machine （ELM）and MetaCognitive Online Sequential Extreme Learning Machine （MCOSELM）， the experimental results show that the proposed method can identify the minor class with a higher ability. Moreover， the training time of the proposed method has not much difference compared with the others， which shows that the proposed method can greatly increase the minor prediction accuracy without affecting the complexity of algorithm.

英文关键词

Key words：samplereconstruction； Extreme Learning Machine （ELM）； principal curve； oversampling； imbalanced data

0 引言

在线贯序学习是一种常见的机器学习问题。在实际工程应用中，在线贯序数据往往同时具有类别严重不均衡的特点。利用传统机器学习方法如支持向量机，得到的分类器往往表现出较大的偏向性，少类样本的识别率远远低于多类样本。以二分类为例，由于样本的极度不均衡，必将导致分类面偏离，易对少类样本形成误判，并造成多类样本“虚高”的分类精度。而实际问题中，人们更关心的是少类样本，且少类样本的错分代价通常大于多类样本[1]，例如，在气象时间序列数据中，对雾霾天气的错判更容易产生不良影响，在医疗诊断时，对早期疾病状态的误判后果更为严重。因此，提高不均衡在线贯序数据中少类样本的分类精度具有重要的理论和工程意义。

目前针对不均衡数据分类的处理方法主要分为基于数据的策略和基于算法的策略。前者通过对数据过采样和欠采样来降低类别的不均衡程度，从而提高分类精度；后者主要通过构建新的分类算法，如代价敏感、集成学习等，或改进现有算法，如加权支持向量机等，来解决数据的不均衡问题。对于基于数据的策略，目前常用的方法是少类样本合成过采样技术（Synthetic Minority Oversampling Technique，SMOTE）[2]。然而，SMOTE算法存在一定的盲目性，即新生成的合成样本可能不符合原始数据分布，特别是在样本集严重失衡的情况下，容易产生样本混合现象，影响分类效果。为解决该问题，杨智明等[3]提出了一种自适应SMOTE，根据样本集内部特征，自适应调整近邻选择策略，控制样本合成质量。Zhai等[4]通过采用分层过滤机制来处理噪声数据，运用少类选择策略和动态分布密度相结合，改进数据分布的不均衡程度。许丹丹等[5]把少类样本过采样的范围推广到n维球体，既解决了传统过采样技术引起的过拟合问题，又解决了SMOTE算法中对虚拟少类样本的范围限制。但上述研究并未考虑在线贯序数据的分布规律，生成的虚拟样本缺乏可信度，因此无法有效解决在线贯序学习问题。从算法角度出发，在线贯序极限学习机（Online Sequential Extreme Learning Machine，OSELM）[6]在解决在线贯序数据的分类问题时表现出良好的性能。但OSELM以整体分类精度为目标，对少类样本的识别能力有限，尤其当样本集严重不均衡时，极易导致对少类样本的误判。例如，当容量为100的样本集中仅有5个少类样本时，分类面将严重偏离，此时多类样本可能全部分类正确，即使少类样本全部误判，整体分类精度仍可达到95%，显然这一结果对少类样本是“虚假”的，对实际工程问题的解决毫无意义。

综上可知，单独考虑数据层面或者算法层面，均难以有效解决不均衡在线贯序数据的分类问题。不难发现，提取在线贯序数据的分布特性是解决该问题的关键所在。为此，本文同时从数据策略和算法策略入手，通过引入主曲线提取在线数据的分布特性，并在此基础上改进SMOTE方法，提高对少类样本的过采样质量；同时引入动态加权的思想，提出一种基于不均衡样本重构的加权在线贯序极限学习机（Imbalanced Samplereconstruction Weighted Online Sequential Extreme Learning Machine，ISWOSELM）；最后采用UCI标准数据集和实际的澳门气象数据验证了该方法的有效性。

1 相关工作

1.1 在线贯序极限学习机

极限学习机（Extreme Learning Machine，ELM）[7]是一种单隐层前馈神经网络。该算法随机挑选输入层参数，直接利用MoorePenrose广义逆，即可求得最小L2范数的输出层权重。整个学习过程只有隐神经元个数可调，结构简单，具有非常快的学习速度和优秀的泛化能力。在线贯序极限学习机是在原始ELM算法的基础上提出的在线增量式快速学习算法。由文献[8]可知，算法步骤分为两个阶段：

步骤1 初始化阶段。

1.2 主曲线

主曲线是通过数据集“中间”的光滑无参数曲线，是线性主成分分析的非线性推广，也是嵌入高维数据的非欧空间的一维流形表述[9]。主曲线理论基于一定概率分布下曲线的“自相合”性，即曲线上任意点都是所有投影至该点的数据点的条件对偶。不同于传统的非线性回归方法，主曲线具有两个明显的优点：1）数据信息的保持性好；2）可有效勾勒出原始信息的轮廓，即数据集是“云”，主曲线是该数据集的“骨架”。目前应用最广泛的是K主曲线。

2 不均衡样本重构加权在线贯序极限学习机

为减少少类样本合成过程中的盲目性，提高其分类精度，本文同时从数据和算法两个角度出发，提出一种基于不均衡样本重构的加权在线贯序极限学习机算法，主要分为离线和在线两个阶段。

2.1 离线阶段

初始离线阶段，通过改进SMOTE算法，对不均衡样本重构，并建立初始模型。其基本思想是首先采用主曲线构建少类样本的可信区域，得到种子样本，再分别对每个种子样本，采用所改进的SMOTE算法生成虚拟样本，同时判断其可信度；考虑到样本的离散度，引入类中心和类平均距离的概念，进一步对虚拟样本筛选进而得到均衡的样本集，最后建立初始训练模型。

首先给出几个定义：设某类样本集合S={xi， i=1，2，…， n}，这里将”|”改成逗号，全文统一。其中xi表示m维向量，维数大小代表样本特征个数。

定义1 类中心（class center）[10]是指某类样本在数据空间的平均中心点。类中心点c是与样本维数相同的请核实，c是否为向量为黑斜。c为黑斜向量，计算方法如下所示：

c=1n∑ni=1x是否黑？xi表示向量，为黑。xi（4）

定义2 类平均距离（class average distance）[10]是指某类中各样本到类中心距离和的平均值，是一标量。该距离d能够反映出类的距离程度，值越小类距离程度越紧，反之较松散。计算方法如下所示：

d=1n∑ni=1D（xi， c）（5）

其中函数D（・）表示欧氏距离计算方法。

改进的SMOTE算法通过生成符合样本本身分布规律的少类样本实现过采样，主要包括三个阶段：1）寻找种子样本；2）对种子样本进行过采样得到虚拟样本；3）筛选合理的虚拟样本。具体步骤如下：

步骤1 生成种子样本。

采用主曲线描绘出原始少类样本的分布趋势，如图1（a）所示。根据数据分布特点，基于主曲线设定上下阈值η1、η2，得到以主曲线为中心的带状区域，即可信区域。定义该可信区域内的点为种子样本，如图1（b）所示。其中：实心点代表原始少类样本，空心点代表种子样本。

步骤2 生成虚拟样本。

对种子样本集Seed={（Xi， yi）， i=1，2，…，N}（其中：Xi为n维向量，n为特征个数，yi为标签，N为种子个数）的每一个种子Xj，寻找与其距离最近的k个种子样本Xnear（near=1，2，…，k）。本文中k=5，如图2（a）所示。分别以Xj为中心，以它到Xnear的欧氏距离为半径做n维球体并在球内随机插值，得到虚拟样本。具体来说，设Xj为种子样本实例，Xi为其近邻。以Xj为中心，Xj与Xi之间的欧氏距离Xj-Xi为半径做n维球体，在该球体内随机插值得到t个虚拟样本点Xnew（new=1，2，…， t），如图2（b）所示。其中：空心方块代表虚拟样本，t为单次要增加的虚拟样本点数。根据文献[5]，在SMOTE算法中，通常取给定样本的5个近邻插值，因此，本文在n维球体内作插值时，也参照通常的取值方法，令t=5。

3 仿真实验与分析

本文采用UCI标准数据集和实际的澳门气象数据[11]进行仿真实验，分别采用极限学习机（ELM）、在线贯序极限学习机（OSELM）和元认知在线贯序极限学习机（MetaCognitive Online Sequential Extreme Learning Machine， MCOSELM）[12]与本文所提算法进行对比。其中，MCOSELM是针对在线不均衡问题的元认知在线序列极限学习机算法，所有样本被线性归一化到[-1，1]。根据第1章的分析，类别的严重不均衡易造成总体和多类样本“虚高”的分类效果，因此，本文更关注算法在少类样本上的分类精度。

3.1 UCI标准数据集

选择两个标准数据集Blood和Abalone来进行仿真实验。

离线阶段，采用改进SMOTE算法对数据预处理，得到均衡的样本集，见表1。

给定隐层激活函数为中英全径向基函数（Radial basis function， RBF）核函数，隐层节点分别为25、45，运行30次取均值，四种模型的性能如表2和表3所示。

从表2和3可以看出，尽管ISWOSELM的总体训练精度和总体测试精度未能达到最高，但ISWOSELM的少类测试精度明显高于其他三种算法，即ISWOSELM对少类样本的识别率最高。以Blood标准数据集为例，ISWOSELM的少类测试精度比经典ELM和OSELM分别提高了24.30%和22.15%，比核实，是否为Vong？应为Vong，对应文献12。Vong等提出的MCOSELM提高了6.02%，且四种算法的训练时间基本相同，表明ISWOSELM在不增加算法复杂度的前提下，对少类样本的预测精度更高。同样的结果也体现在Abalone数据集的仿真实验中，进一步表明ISWOSELM对提高少类样本分类精度的有效性。

3.2 澳门气象数据

在空气质量监测等实际问题中，数据往往具有在线序列到达的特点，且空气质量良好的天数远远大于空气严重污染的天数，因此是一种典型的不均衡在线贯序问题。由于采集数据的局限性，本文采用澳门气象局网站上公布的空气质量数据[11]进行仿真实验。

给定训练数据集D=（是向量吗，是否为黑斜，核实x是向量，用黑斜；t为普通变量，不用黑斜。x， t），x表示输入向量，即当天的PM10、SO2、NO2、O3的浓度值，x=（d（PM10）， d（SO2）， d（NO2）， d（O3））；t是输出是否黑斜？不是黑斜变量量即第二天的PM10的值，即t=d+1（PM10）。

为验证ISWOSELM的有效性，利用2010一字线指什么？破折线的一半―2012年澳门胱械焊窭嫉缕象站收集的序列数据进行实验。其中，2010年的数据作为初始离线训练样本，2011年数据作为在线训练样本，2012年的数据作为测试样本。

对2010年初始训练样本，采用改进SMOTE算法重构样本集。首先利用主曲线描绘出少类样本的大致轮廓，如图5（a）。基于设定上下阈值分别为η1=20，η2=25，得到以主曲线为中心的可信区域，如图5（b），选择可信区域内的少类样本点为种子样本。

分别以每个种子样本为中心，生成虚拟样本并筛选，最终得到均衡的初始训练样本集。使用改进SMOTE算法前后2010年的样本数目如表4。

由表4可知，经改进SMOTE算法处理之后，两类样本的数据比近似于1∶1，从而解决了离线阶段的数据不均衡问题。

利用处理后的均衡离线样本集，建立初始模型。给定隐层激活函数为RBF核函数，对2011的数据进行在线贯序训练。图6和图7分别为随隐层节点个数变化，ISWOSELM、MCOSELM、OSELM和ELM的训练精度和测试精度的变化。

设定隐节点个数为30，分别用ISWOSELM、OSELM、ELM和MCOSELM四种算法对气象数据进行仿真实验，表5为四种算法运行30次所得结果的平均性能比较。

从表5中可以看出，尽管ISWOSELM对多类样本的识别率略有下降，总体测试精度也未达到最佳，但其少类训练精度和测试精度均明显优于其他三种算法，其中少类测试精度分别比其他三种算法提高了22.87%、25.76%和22.42%，因而大大减少了少类样本的误判率。从另一个方面来说，ELM和OSELM多类测试精度明显较高，恰恰表明直接对类别严重不均衡的样本分类，分类面更加偏向于少类样本，从而造成多类样本分类效果的“虚假”提升。是否应为图6和图7？图6和图7中，随隐层节点变化，四种算法的图形均有一定程度的波动，这是ELM本身的随机性所致。但不难发现，较其他三种算法，ISWOSELM的图形波动相对较小，表现出良好的稳健性。从表5可以看出，ISWOSELM的训练时间与其他三种算法接近，但少类的测试精度明显提高，由此可以看出，在不增加算法时间复杂度的前提下，ISWOSELM对少类样本的识别率更高，更适合于不均衡在线贯序数据的分类问题。

4 结语

本文提出了一种基于不均衡样本重构的加权在线贯序极限学习机，继承了OSELM算法在线、快速学习的特点，通过引入主曲线提取数据的分布特性，减少了少类样本合成过程的盲目性，在不影响算法计算复杂度的情况下，明显提高了少类样本的分类精度，对解决实际气象问题具有重要的理论和工程意义。但本文所提算法有一定的局限性，主要针对典型的二分类问题，对多分类不均衡问题并未很好解决。因此，完善并改进该算法，是下一步研究的方向。

参考文献：

[1]TAO X， HAO S， ZHANG D， et al.Overview of classification algorithms for unbalanced data [J]. Journal of Chongqing University of Posts and Telecommunications： Natural Science Edition， 2013， 25（1）： 101-121. （陶新民，郝思媛，张冬雪，等.不均衡数据分类算法的综述[J]. 重庆邮电大学学报：自然科学版，2013，25（1）：101-121.）

[2]CHAWLA N， BOWYER K， HALL L， et al. SMOTE： Synthetic minority oversampling technique [J]. Journal of Artificial Intelligence Research， 2002， 16（1）： 321-357.

[3]YANG Z， QIAO L， PENG X. Research on datamining method for imbalanced dataset based on improved SMOTE [J]. Acta Electronica Sinica， 2007， 35（12A）： 22-26.（杨智明，乔立岩，彭喜元.基于改进SMOTE的不平衡数据挖掘方法研究[J].电子学报，2007，35（12A）：22-26.）

[4]ZHAI Y， MA N， RUAN D， et al. An effective oversampling method for imbalanced data sets classification [J]. Chinese Journal of Electronics， 2011， 20（3）： 489-494.

[5]XU D， WANG Y， CAI L. ISMOTE algorithm for imbalanced data sets [J]. Journal of Computer Applications， 2011， 31（9）： 2399-2401.（许丹丹，王勇，蔡立军.面向不均衡数据集的ISMOTE算法[J]. 计算机应用，2011，31（9）：2399-2401.）

[6]LIANG N Y， HUANG G B， SARATCHANDRAN P， et al. A fast accurate online sequential learning algorithm for feedforword networks [J]. IEEE Transactions on Neural Networks， 2006，17（6）： 1411-1423.

[7]HUANG G B， ZHOU H， DING X， et al. Extreme learning machine for regression and multiclass classification [J]. IEEE Transactions on Systems， Man， and Cybernetics ― Part B： Cybernetics， 2012， 42（2）： 513-529.

[8]YANG L， ZHANG R. Online sequential ELM algorithm and its improvement [J]. Journal of Northwest University： Natural Science Edition， 2012， 42（6）： 885-896.（杨乐，张瑞.在线序列ELM算法及其发展[J]. 西北大学学报：自然科学版，2012，42（6）：885-896.）

[9]ZHANG J， WANG J. An overview of principal curves [J]. Chinese Journal of Computers， 2003， 26（2）： 129-146.（张军平，王钰. 主曲线研究综述[J]. 计算机学报，2003，26（2）：129-146.）

[10]LIU Y， LIU S， LIU T， et al. New oversampling algorithm DB_SMOTE [J]. Computer Engineering and Applications，2014，50（6）： 92-95.（刘余霞，刘三民，刘涛，等.一种新的过采样算法DB_SMOTE[J].计算机工程与应用，2014，50（6）：92-95.）

[11]SMG. Epublication Download Page [EB/OL]. [2014-12-06]. http：//www.smg.gov.mo/www/ccaa/pdf/e_pdf_download.php.

[12]VONG CM， IP WF， WONG PK， et al. Prediction minority class for suspended particulate matters level by extreme learning machine [J]. Neurocomputing， 2014， 128： 136-144.