极限学习机(extreme learning machine，ELM)因其良好的泛化性能和极快的学习速度，在分类和回归问题中得到了广泛的应用.然而，由于数据生成和采集过程中的测量误差、噪声、数据缺失等原因，数据集中的训练样本具有不确定性.包括极限学习机在内的传统分类算法无法直接对不确定数据进行学习，在分类过程中考虑数据的不确定属性是有待解决的问题之一.因此，本文针对不确定数据分类问题，提出了基于蒙特卡洛抽样的不确定极限学习机(Monte Carlo based extreme learning machine,MC-ELM).

描述一个不确定对象通常使用离散模型或者连续模型，其中，离散模型使用带有概率值的离散实例集合进行描述，连续模型使用概率密度函数进行描述.本文基于离散模型对不确定数据的分类问题进行分析.首先给出离散模型的正式定义，如定义1所描述.

定义1 给定一组不确定对象U={U₁,…,U_n}，其中每个不确定对象U_i由一组不确定对象实例组成，即U_i={u_i¹,…,u_i^m},则有每个不确定对象之间相互独立，每个不确定对象的所有实例都相互独立，每个不确定对象的所有实例的存在概率之和为1.

在给定不确定数据模型的基础上，本文给出不确定数据分类的问题定义，如定义2所描述.

定义2 给定一个不确定数据集[U,c]∈X×C，其中U是不确定对象，c是不确定对象对应的类别标签，X和C分别是数据和类标签所属的空间.不确定数据分类就是要训练出一个由X到C的映射φ，使得不确定对象U_i的每个实例u_i^j 都以一定的概率属于一个类c_i，并且该不确定对象U_i属于类别c，如果属于类别c的U_i的所有实例的分类概率和最大.

最基本的方法是枚举不确定数据集中每个不确定对象的所有实例，使用某种学习算法进行训练之后，计算每个样本的所有实例的分类结果及其概率，并将每个不确定对象的实例中属于同一个类别的实例的分类概率求和，概率和最大的类别即为该不确定对象的所属类别.该方法能够保证不确定数据分类的准确性，但是在现实应用中，枚举所有可能世界的代价太大，几乎是不可操作的，再将得到的庞大的枚举实例训练集进行训练不具有实际意义.

极限学习机^{[1, 2, 3]}是一种广义单隐层前馈后传神经网络.极限学习机首先随机生成输入权重和偏置，并通过矩阵运算直接计算出输出权重，形成分类器模型.相比传统的前馈后传神经网络，极限学习机的训练速度极快，泛化性能更好，实现更容易.此外，极限学习机和支持向量机(support vector machine，SVM)^[4]优化角度是一致的^[5].

给定N个训练样本(x_i,t_i)∈R^n×m，极限学习机的输出为

极限学习机的计算过程是首先随机生成输入权重ω和b，使用随机生成的参数和训练数据x利用公式(2)计算矩阵H，再使用公式(3)计算输出权重矩阵β.具体如算法1所描述.

算法1 ELM

输入：训练数据x.

输出：输出权重矩阵β.

01. 随机生成输入权重ω和b;

02. 计算H矩阵;

03. 计算输出权重矩阵β=T.

极限学习机的输出函数为

不失一般性，训练数据集中的样本个数要远远大于隐藏层节点数，因此，为了降低计算代价，极限学习机的输出函数可以改写为

文献[6]提出了一种不确定极限学习机，在枚举所有不确定对象的所有实例后，利用实例的存在概率判断不确定对象对应所属类别的分类概率，从而实现对不确定数据的分类.

然而，枚举不确定数据集中每个不确定对象的所有实例的枚举代价呈指数级增长，尤其是当不确定对象可能的实例很多的时候，枚举代价是巨大的和不可行的.

为此，本节提出一种基于蒙特卡洛方法的不确定极限学习机MC-ELM.该算法使用蒙特卡洛方法对不确定数据集中的不确定对象进行抽样，在对抽样得到的抽样样本进行训练后，计算抽样估计量，并以此作为不确定分类概率.MC-ELM不使用不确定对象的实例的存在概率作为分类概率，而是使用抽样方法的抽样估计量.

蒙特卡洛方法是一种随机抽样方法，在特定概率分布的概率模型中，利用抽样实验的方法，产生该已知概率分布的随机变量.基于本文所采用的不确定概率模型，首先给出该随机变量的标记规则.

假定一个不确定对象Ui实际属于类别cs，uij是Ui的第j个抽样实例，抽样标记εuijct的取值规则为

不确定对象U_i对于类别c_s的抽样估计为

估计量Pr_Ui^c_s是无偏估计，即，估计偏差为

本节提出一种基于蒙特卡洛的不确定极限学习机(MC-ELM).与直接对枚举实例进行训练的分类算法不同，MC-ELM利用上一节介绍的蒙特卡洛方法的抽样估计量对不确定对象的分类概率进行估计.根据蒙特卡洛抽样方法及其估计量的定义，MC-ELM算法的具体流程如算法2所描述.

算法2 MC-ELM

输入：训练数据集

输出：分类结果

01. ForEach U_i∈D_train DO

02.    对U_i进行抽样;

03.    将抽样实例放入D_train^sampled;

04. End ForEach

05. 使用D_train^sampled计算β=T;

06. ForEach U_i∈D_test DO

07.    对U_i进行抽样;

08.    将抽样实例放入D_test^sampled;

09. End ForEach

10. 计算输出O=Hβ;

11. ForEach U_i∈D_test^sampled DO

12.    ForEach u_i^j∈S_Ui DO

13.        从O中获取u_i^j的类标签c_out;

14.        对应估计量Pr_Ui^c_out=Pr_Ui^c_out+;

15.        End ForEach

16.        c=argmax_cout∈CPr_Ui^c_out为U_i的类标签;

17. End ForEach

首先初始化两个空数据集D_train^sampled和D_test^sampled.第1~4行对原始训练数据集中的每个不确定对象进行抽样，并将抽样实例存入数据集D_train^sampled，第5行根据传统ELM的计算理论，使用该数据集中的数据计算分类器的β参数.第6~9行对原始测试数据集中的每个不确定对象进行抽样，并将所有抽样实例存入数据集D_test^sampled.第10行根据传统ELM的计算理论和测试抽样实例计算输出矩阵O.第11~17行判断每个不确定对象的所属类别，其中第12~15行计算每个抽样实例对应所有类别的抽样估计量标记，第16行将不确定对象划分给抽样估计量总和最大的类别.

本文实验使用一台配置英特尔酷睿i7-3667U 3.4 GHz处理器和8GB DDR3内存的商用台式机，ELM相关算法使用Matlab R2009a编写和实现.

实验数据集采用UCI Machine Learning Respository^[7]中的真实数据集作为原始数据集，并根据一定的概率分布将原始数据集转换成不确定数据集.具体做法是，将原始确定数据集中每个真实的样本作为不确定数据集中一个不确定对象的中心，然后利用概率分布为每个不确定对象随机生成多个实例.原始数据集的信息如表 1所示.

表 1

Table 1

表 1(Table 1)

表 1 数据集信息 Table 1 Brief of datasets 数据集 样本数 类别数 Vowel 1 348 11 Diabete 1 142 2 Credit 1 060 2

表 1 数据集信息 Table 1 Brief of datasets

由于基于抽样的不确定极限学习机MC-ELM的训练时间和准确率都与抽样程度直接相关，因此本节所给出的实验结论都没有与现有算法进行直接对比，而是单独给出与抽样率相关的实验结果变化情况.

MC-ELM的训练时间随抽样率变化的实验结果图如图 1所示.由图中可以看出，随着抽样率的增大，抽样实例的个数增加，因此训练时间也相应地增长.

图 1(Figure 1)

Fig. 1

图 1 MC-ELM的训练时间 Fig. 1 Training time of MC-ELM

估计量的相对误差能够反映实际学习结果R与估计结果的相对差值.本文实验的相对误差使用式(9)计算:

MC-ELM算法的相对误差随着抽样率增大而变化的趋势如图 2所示.

图 2(Figure 2)

Fig. 2

图 2 MC-ELM的相对误差 Fig. 2 Relative error of MC-ELM

从图中可以看出，随着抽样率的增加，估计量的相对误差在减小，并逐渐收敛于0.这一实验结果表明该估计量具有较高的估计能力.

准确率是衡量分类算法的重要指标之一.本组实验测得MC-ELM算法随抽样率增加的测试准确率的变化趋势如图 3所示.

图 3(Figure 3)

Fig. 3

图 3 MC-ELM的相对误差 Fig. 3 Testing accuracy of MC-ELM

由于抽样估计量具有相对误差，基于抽样的不确定极限学习机的准确率会小于基于存在概率的不确定极限学习机.当抽样率上升时，分类准确率也随之上升；当抽样率为1时，二者理论上相等.

本文针对不确定数据的分类问题，提出一种基于蒙特卡洛抽样的不确定极限学习机MC-ELM.该算法通过对不确定对象进行抽样，通过基于极限学习机计算理论对抽样实例进行学习，并使用抽样估计量代替存在概率计算不确定对象的分类概率.MC-ELM算法能够有效避免枚举不确定对象实例的代价高等问题.实验结果表明，本文提出的MC-ELM算法在不确定数据分类问题中，具有有效性和高效性.