0 概述

极限学习机(Extreme Learning Machine, ELM)是一种单隐含层前馈型神经网络^[1]。ELM可随机指定输入层与隐含层间的连接权值以及隐含层各节点的偏置值, 并采用解析方法求解隐含层与输出层间的连接权值。与传统基于梯度下降方法的神经网络相比, ELM具有更好的泛化能力与更高的计算效率。文献[2]将约束优化理论引入到ELM的求解过程中, 进一步完善了ELM的理论体系。

不平衡数据集是指其中某一类别样本数量远少于其他类别样本数量的数据集。传统ELM在设计过程中并未考虑训练数据集的不平衡性给分类器带来的影响^[3-5]。因此, 文献[6-8]借鉴代价敏感学习的思想, 从样本加权和惩罚因子调节2个方面对ELM算法进行改进, 以改善ELM在不平衡数据集中对少数类样本的分类性能。

样本加权方法在模型训练过程中对样本施以不同的加权值, 从而改善少数类样本的分类效果。文献[9]提出一种加权极限学习机(Weighted Extreme Learning Machine, WELM), 其在求解ELM等价约束优化问题时, 通过为不同类别样本赋予与其所属类别数量成反比的权重, 来提高少数类样本被错分的代价, 从而降低该类样本的错分概率。文献[10]提出一种面向不平衡数据流的自适应加权在线ELM算法, 其通过设计自动调整实时到达训练样本加权值的惩罚矩阵, 使得算法可以在线处理不平衡数据流的分类问题。文献[11]将模糊理论与加权ELM相结合, 构造基于多数投票机制的集成分类器, 以提高WELM对不平衡基因表达数据的分类性能。文献[12]提出一种基于指数加权的在线核序列ELM算法, 并将其应用于混沌动力学系统的动态重构研究。WELM在设计时虽然对每个样本都做了加权处理, 但在计算加权值时仅考虑类别的影响, 对同一类别样本都取同样的权值, 并未考虑每个类别内部样本不同的重要性。

惩罚因子调节方法通过对不同类别样本赋予不同的错分惩罚因子, 从而提高少数类样本的分类效果。文献[13]提出一种类依赖代价调节极限学习机(CCR-ELM), 其在求解ELM等价约束优化问题时, 通过对少数类样本施以较大错分惩罚因子和对多数类样本施以较小错分惩罚因子, 以提高少数类样本的错分代价, 最终降低该类样本的错分概率。文献[14]采用可变长度的粒子群优化算法自适应调整CCR-ELM的超参数, 提高了CCR-ELM算法的稳定性及其对不平衡数据的分类精度。文献[15]提出了一种基于可变长度头脑风暴优化的自适应CCR-ELM算法, 其提高了CCR-ELM算法在处理不平衡数据时的分类稳定性。CCR-ELM在类别层面做了错分区别惩罚, 但在惩罚因子的取值确定方面, 对2种类别错分惩罚因子采取独立赋值的方法, 并未考虑各类别样本的分布情况对错分惩罚因子取值的影响, 且同样未考虑每个类别内部样本不同的重要性。

本文提出一种针对二分类不平衡数据集的类别与样本双依赖极限学习机(CSD-ELM)分类算法。按照两类别样本数量比例设计错分惩罚因子, 根据类内样本分布情况给出基于Mini-batch k-means聚类的类内样本权值确定方法, 并进一步按照聚类所得簇内样本分布情况提出基于类簇中心点距离测度的簇内样本权值确定方法, 每个样本的最终加权值由以上2个权值相乘而得。在此基础上, 基于约束优化理论, 提出区分正、负类别的隐含层输出矩阵, 并根据训练样本数与ELM隐含层节点数间的关系, 在较低的时间复杂度下分2种情况计算ELM隐含层与输出层间的连接权值。

1 算法描述 1.1 基于类别样本数量比例的错分惩罚因子设置

设计不平衡数据分类算法的主要目的是提高少数类样本的分类精度, 同时尽可能保持多数类样本的分类精度。由于在ELM等价约束优化问题的目标函数中, 惩罚因子越大, 对该类样本分类错误的惩罚就越大, 考虑到不同类别样本的分布情况, 在CCR-ELM算法的基础上, 本文提出一种按样本比例对两类别错分惩罚因子进行设置的方法, 具体如下:

$ \left\{ {\begin{array}{*{20}{l}} {{C_ + } = \frac{N}{{{N_ + }}}C}\\ {{C_ - } = \frac{N}{{{N_ - }}}C} \end{array}} \right. $

(1)

其中, N₊、N_-分别表示训练集的少数类、多数类样本数量, N为训练集样本总量, C₊、C_-分别表示少数类、多数类错分惩罚因子, C为一致惩罚因子。与CCR-ELM算法相比, 本文算法的惩罚因子数量从2个减少为1个, 这在很大程度上降低了算法在进行参数寻优时的计算复杂度。同时, 有:

$ \frac{{{C_ + }}}{{{C_ - }}} = \frac{{{N_ - }}}{{{N_ + }}} = IR $

(2)

其中, IR为训练数据集的类别不平衡比率。在设置一致惩罚因子C的基础上进行加权, C₊>C_-, 且C₊为C_-的IR倍, 这就使得对少数类样本的错分惩罚大于对多数类样本的错分惩罚, 且惩罚放大倍数与训练数据集的不平衡比率直接相关。

1.2 类内样本权值确定

Mini-batch k-means算法是一种改进的k-means算法^[16], 其通过随机抽样产生多个固定规模的小批量数据子集, 并使用数据子集进行类簇划分和中心点更新计算。同时, Mini-batch k-means算法还引入基于当前簇样本数倒数的学习率以提高算法的收敛速度。实验结果表明, 上述改进大幅提高了k-means算法的运算速度, 使算法能够在大数据集上以非常低的时间消耗来产生较好的聚类效果^[16]。

WELM算法在样本加权值的设置上仅考虑类别因素, 对同一类别内部样本施以同样的权值。CCR-ELM算法在设置错分惩罚因子时仅对2个类别进行区分设置, 同样也未考虑每个类别内部样本不同的重要性。在通常情况下, 由于每个样本在训练集特征空间中所处位置的不同, 它们对于分类算法训练过程中分类面形成的影响程度往往也不同, 因此, 应根据类内样本分布的特点对每个样本进行权值设置。本文设计基于Mini-batch k-means聚类与距离测度的类内样本权值确定方法。首先使用Mini-batch k-means算法对每个类别实例进行聚类, 根据聚类所得每个类簇实例数量确定样本的簇加权值, 类簇实例数越多, 簇加权值越大。然后根据每个类簇内各实例点与簇中心点的欧式距离计算各样本的簇内加权值, 距离越近, 簇内加权值越大。每个样本的最终加权值由其簇加权值与簇内加权值相乘而得。基于Mini-batch k-means聚类与距离测度的类内样本权值确定方法具体描述如下:

算法1  基于Mini-batch k-means聚类与距离测度的类内样本权值确定方法

输入  训练样本集D={(x_i, t_i)}_i=1^N, x_i∈Rⁿ, t_i∈{+1, -1}, 少数类实例集X₊={x_i⁺|x_i⁺∈Rⁿ, t_i⁺=+1, i=1, 2, …, N₊}, 多数类实例集X_-={x_i^-|x_i^-∈Rⁿ, t_i^-=-1, i=1, 2, …, N_-}

输出  少数类、多数类样本加权矩阵W₊、W_-

步骤1  使用Mini-batch k-means算法对X₊、X_-进行聚类, 分别获得k₊个类簇{X₊¹, X₊², …, X₊^k₊}及k_-个类簇X_-¹, X_-², …, X_-^k_-, 对应的类簇中心点分别为{μ₊¹, μ₊², …, μ₊^k₊}及{μ_-¹, μ_-², …, μ_-^k_-}, 簇实例数量分别为{N₊¹, N₊², …, N₊^k₊}及{N_-¹, N_-², …, N_-^k_-}。

步骤2  根据实例x_i⁺所属类簇X₊^p(p=1, 2, …, k₊)的实例数量占类别总实例数量的比例, 计算样本(x_i⁺, t_i⁺)的簇加权值:$ \left(W_{i i}^{+}\right)^{c}=\frac{N_{+}^{p}}{N_{+}}$。

步骤3  根据实例x_i⁺∈X₊^p与所属类簇中心点的欧式距离计算样本(x_i⁺, t_i⁺)的簇内加权值:(W_ii⁺)^S=exp(-‖x_i⁺-μ₊^p‖)。

步骤4  计算样本x_i⁺∈X₊^p的最终加权值:W_ii⁺=(W_ii⁺)^C·(W_ii⁺)^S。

步骤5  令i=i+1, 重复步骤2~步骤4, 直至i=N₊。

步骤6  返回少数类样本加权矩阵:W₊=diag(W_ii⁺)。

步骤7  按步骤2~步骤6计算并返回多数类样本加权矩阵:W_-=diag(W_ii^-)。

1.3 CSD-ELM分类算法

本文基于约束优化理论, 通过设计区分正、负类别的隐含层输出矩阵, 并根据训练样本数与ELM隐含层节点数间的关系, 分2种情况计算ELM隐含层与输出层间的连接权值。具体过程如下:

给定一个类别不平衡的二分类问题训练数据集D={(x_i, t_i)}_i=1^N, x_i∈Rⁿ, t_i∈{+1, -1}, CSD-ELM算法的等价约束优化问题可以表示为:

$ \begin{array}{l} {\rm{Minimize:}}\frac{1}{2}{\left\| \mathit{\boldsymbol{\beta }} \right\|^2} + {C_ + }\frac{1}{2}\sum\limits_{i = 1}^{{N_ + }} {W_{ii}^ + } {\left( {\xi _i^ + } \right)^2} + \\ \;\;\;\;\;\;\;C - \frac{1}{2}\sum\limits_{i = 1}^{{N_ - }} {W_{ii}^ - } {\left( {\xi _i^ - } \right)^2} \end{array} $

$ \begin{array}{l} {\rm{Subject}}\;{\rm{to}}:\\ \mathit{\boldsymbol{h}}\left( {\mathit{\boldsymbol{x}}_i^ + } \right)\mathit{\boldsymbol{\beta }} = t_i^ + - \xi _i^ + ,i = 1,2, \cdots ,{N_ + }\\ \mathit{\boldsymbol{h}}\left( {\mathit{\boldsymbol{x}}_i^ - } \right)\mathit{\boldsymbol{\beta }} = t_i^ - - \xi _i^ - ,i = 1,2, \cdots ,{N_ - } \end{array} $

(3)

其中, (x_i⁺, t_i⁺)、(x_i^-, t_i^-)分别表示少数类、多数类样本, 其数量分别为N₊、N_-, ξ⁺、ξ^-分别表示少数类、多数类样本的训练误差, β表示ELM隐含层与输出层间的连接权值, h(x)表示ELM的隐含层输出函数, h_j(x)表示ELM第h(x_i⁺)=[h₁(x_i⁺), h₂(x_i⁺), …, h_L(x_i⁺)]个隐含层节点的输出函数, h(x_i⁺)=[h₁(x_i⁺), h₂(x_i⁺), …, h_L(x_i⁺)], h(x_i^-)=[h₁(x_i^-), h₂(x_i^-), …, h_L(x_i^-)]。少数类和多数类样本错分惩罚因子C₊和C_-的取值按式(1)设置, 少数类、多数类样本加权因子W_ii⁺、W_ii^-按算法1计算而得。

分别记:

$ {\mathit{\boldsymbol{t}}_ + } = {\left[ {t_1^ + ,t_2^ + , \cdots ,t_N^ + } \right]^{\rm{T}}} $

(4)

$ {\mathit{\boldsymbol{t}}_ - } = {\left[ {t_1^ - ,t_2^ - , \cdots ,t_N^ - } \right]^{\rm{T}}} $

(5)

$ {\mathit{\boldsymbol{\xi }}_ + } = {\left[ {\xi _1^ + ,\xi _2^ + , \cdots ,\xi _{{N_ + }}^ + } \right]^{\rm{T}}} $

(6)

$ {\mathit{\boldsymbol{\xi }}_ - } = {\left[ {\xi _1^ - ,\xi _2^ - , \cdots ,\xi _{{N_ - }}^ - } \right]^{\rm{T}}} $

(7)

$ {\mathit{\boldsymbol{H}}_ + } = {\left[ {\mathit{\boldsymbol{h}}{{\left( {\mathit{\boldsymbol{x}}_1^ + } \right)}^{\rm{T}}},\mathit{\boldsymbol{h}}{{\left( {\mathit{\boldsymbol{x}}_2^ + } \right)}^{\rm{T}}}, \cdots ,\mathit{\boldsymbol{h}}{{\left( {\mathit{\boldsymbol{x}}_{{N_ + }}^ + } \right)}^{\rm{T}}}} \right]^{\rm{T}}} $

(8)

$ {\mathit{\boldsymbol{H}}_ - } = {\left[ {\mathit{\boldsymbol{h}}{{\left( {\mathit{\boldsymbol{x}}_1^ - } \right)}^{\rm{T}}},\mathit{\boldsymbol{h}}{{\left( {\mathit{\boldsymbol{x}}_2^ - } \right)}^{\rm{T}}}, \cdots ,\mathit{\boldsymbol{h}}{{\left( {\mathit{\boldsymbol{x}}_{{N_ - }}^ - } \right)}^{\rm{T}}}} \right]^{\rm{T}}} $

(9)

将式(3)写为矩阵形式:

$ \begin{array}{*{20}{c}} {{\rm{Minimize:}}\frac{1}{2}{\mathit{\boldsymbol{\beta }}^{\rm{T}}}\mathit{\boldsymbol{\beta }} + {C_ + }\frac{1}{2}\mathit{\boldsymbol{\xi }}_ + ^{\rm{T}}{\mathit{\boldsymbol{W}}_ + }{\mathit{\boldsymbol{\xi }}_ + } + }\\ {{C_ - }\frac{1}{2}\mathit{\boldsymbol{\xi }}_ - ^{\rm{T}} - {\mathit{\boldsymbol{W}}_ - }{\mathit{\boldsymbol{\xi }}_ - }} \end{array} $

$ \begin{array}{l} {\rm{Subject}}\;{\rm{to}}:\\ {\mathit{\boldsymbol{H}}_ + }\mathit{\boldsymbol{\beta }} = {\mathit{\boldsymbol{t}}_ + } - {\mathit{\boldsymbol{\xi }}_ + },{\mathit{\boldsymbol{H}}_ - }\mathit{\boldsymbol{\beta }} = {\mathit{\boldsymbol{t}}_ - } - {\mathit{\boldsymbol{\xi }}_ - } \end{array} $

(10)

其中, W₊与W_-根据算法1计算而得。

构造式(10)所述约束优化问题的拉格朗日辅助函数:

$ \begin{array}{l} L\left( {\mathit{\boldsymbol{\beta }},{\mathit{\boldsymbol{\xi }}_ + },{\mathit{\boldsymbol{\xi }}_ - },{\mathit{\boldsymbol{\alpha }}_ + },{\mathit{\boldsymbol{\alpha }}_ - }} \right) = \frac{1}{2}{\mathit{\boldsymbol{\beta }}^{\rm{T}}}\mathit{\boldsymbol{\beta }} + {C_ + }\frac{1}{2}\mathit{\boldsymbol{\xi }}_ + ^{\rm{T}} + {\mathit{\boldsymbol{W}}_ + }{\mathit{\boldsymbol{\xi }}_ + } + \\ \;\;\;{C_ - }\frac{1}{2}{\mathit{\boldsymbol{\xi }}^{\rm{T}}}{\mathit{\boldsymbol{W}}_ - }{\mathit{\boldsymbol{\xi }}_ - } - \mathit{\boldsymbol{\alpha }}_ + ^{\rm{T}}\left( {{\mathit{\boldsymbol{H}}_ + }\mathit{\boldsymbol{\beta }} - {\mathit{\boldsymbol{t}}_ + } + {\mathit{\boldsymbol{\xi }}_ + }} \right) - \\ \;\;\;\mathit{\boldsymbol{\alpha }}_ - ^{\rm{T}}\left( {{\mathit{\boldsymbol{H}}_ - }\mathit{\boldsymbol{\beta }} - {\mathit{\boldsymbol{t}}_ - } + {\mathit{\boldsymbol{\xi }}_ - }} \right) \end{array} $

(11)

其中, α₊、α_-为拉格朗日乘子, α₊=[α₊¹, α₊², …, α₊^N₊]^T∈R₊^N₊, α_-=[α_-¹, α_-², …, α_-^N_-]^T∈R₊^N_-。

求解式(11)的KKT条件^[17]为:

$ \frac{{\partial L}}{{\partial \mathit{\boldsymbol{\beta }}}} = 0 \to \mathit{\boldsymbol{\beta }} = \mathit{\boldsymbol{H}}_ + ^{\rm{T}}{\mathit{\boldsymbol{\alpha }}_ + } + \mathit{\boldsymbol{H}}_ - ^{\rm{T}}\mathit{\boldsymbol{\alpha }}\_ $

(12)

$ \frac{{\partial L}}{{\partial {\mathit{\boldsymbol{\xi }}_ + }}} = 0 \to {\mathit{\boldsymbol{\alpha }}_ + } = {C_ + }{\mathit{\boldsymbol{W}}_ + }{\mathit{\boldsymbol{\xi }}_ + } $

(13)

$ \frac{{\partial L}}{{\partial {\mathit{\boldsymbol{\xi }}_ - }}} = 0 \to {\mathit{\boldsymbol{\alpha }}_ - } = {C_ - }{\mathit{\boldsymbol{W}}_ - }{\mathit{\boldsymbol{\xi }}_ - } $

(14)

$ \frac{{\partial L}}{{\partial {\mathit{\boldsymbol{\alpha }}_ + }}} = 0 \to {\mathit{\boldsymbol{H}}_ + }\mathit{\boldsymbol{\beta }} = {\mathit{\boldsymbol{t}}_ + } - {\mathit{\boldsymbol{\xi }}_ + } $

(15)

$ \frac{{\partial L}}{{\partial {\mathit{\boldsymbol{\alpha }}_ - }}} = 0 \to {\mathit{\boldsymbol{H}}_ - }\mathit{\boldsymbol{\beta }} = {\mathit{\boldsymbol{t}}_ - } - {\mathit{\boldsymbol{\xi }}_ - } $

(16)

将式(12)~式(16)写为分块矩阵形式:

$ \mathit{\boldsymbol{\beta }} = {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] $

(17)

$ \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\xi }}_ + }}\\ {{\mathit{\boldsymbol{\xi }}_ - }} \end{array}} \right] $

(18)

$ \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]\mathit{\boldsymbol{\beta }} = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\xi }}_ + }}\\ {{\mathit{\boldsymbol{\xi }}_ - }} \end{array}} \right] $

(19)

分以下2种情况进行讨论:

1) 当训练样本数少于或等于隐含层节点数, 即N≤L时, 由式(18)可得:

$ \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\xi }}_ + }}\\ {{\mathit{\boldsymbol{\xi }}_ - }} \end{array}} \right] = {\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]^{ - 1}}\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] $

(20)

将式(17)、式(20)代入式(19)中, 可得:

$ \begin{array}{l} \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] - \\ {\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]^{ - 1}}\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] \end{array} $

(21)

将式(21)两端左乘$ \left[\begin{array}{cc}{C_{+} \boldsymbol{W}_{+}} & {\boldsymbol{O}} \\ {\boldsymbol{O}} & {C_{-} \boldsymbol{W}_{-}}\end{array}\right]$, 可得:

$ \begin{array}{l} \left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] = \\ \left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] - \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] \end{array} $

(22)

从而, 有:

$ \begin{array}{l} \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\alpha }}_ + }}\\ {{\mathit{\boldsymbol{\alpha }}_ - }} \end{array}} \right] = {\left( {\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}} + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\ \left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] \end{array} $

(23)

将式(23)代入式(17)中, 可得:

$ \begin{array}{l} \mathit{\boldsymbol{\beta }} = {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}{\left( {\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}} + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\ \left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] \end{array} $

(24)

2) 当训练样本数多于隐含层节点数, 即N>L时, 由式(17)、式(18)可得:

$ \mathit{\boldsymbol{\beta }} = {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\xi }}_ + }}\\ {{\mathit{\boldsymbol{\xi }}_ - }} \end{array}} \right] $

(25)

于是, 有:

$ \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{\xi }}_ + }}\\ {{\mathit{\boldsymbol{\xi }}_ - }} \end{array}} \right] = {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]} \right)^\dagger }\mathit{\boldsymbol{\beta }} $

(26)

其中, (·)^†表示矩阵的Moore-Penrose广义逆^[18]。

将式(26)代入式(19)中, 整理可得:

$ \left( {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right] + {{\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]} \right)}^\dagger }} \right)\mathit{\boldsymbol{\beta }} = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] $

(27)

由于$ \left(\left[\begin{array}{c}{\boldsymbol{H}_{+}} \\ {\boldsymbol{H}_{-}}\end{array}\right]^{\mathrm{T}}\left[\begin{array}{cc}{C_{+} \boldsymbol{W}_{+}} & {\boldsymbol{O}} \\ {\boldsymbol{O}} & {C_{-} \boldsymbol{W}_{-}}\end{array}\right]\right)_{L \times N}(L<N)$矩阵满行秩, 根据Moore-Penrose广义逆矩阵的性质^[18], 可得:

$ \begin{array}{l} \left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]} \right) \cdot \\ {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]} \right)^\dagger } = {\mathit{\boldsymbol{I}}_{L \times L}} \end{array} $

(28)

然后将式(27)的两端同时左乘表达式$ \left(\left[\begin{array}{c}{\boldsymbol{H}_{+}} \\ {\boldsymbol{H}_{-}}\end{array}\right]^{\mathrm{T}}\left[\begin{array}{cc}{C_{+} \boldsymbol{W}_{+}} & {\boldsymbol{O}} \\ {\boldsymbol{O}} & {C_{-} \boldsymbol{W}_{-}}\end{array}\right]\right)$, 可得:

$ \begin{array}{l} \left( {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]} \right)\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right] + \mathit{\boldsymbol{I}}} \right)\mathit{\boldsymbol{\beta }} = \\ {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] \end{array} $

(29)

从而, 有:

$ \begin{array}{l} \mathit{\boldsymbol{\beta }} = {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right] + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\ {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right] \end{array} $

(30)

综合以上2种情况, 可以得到式(31)。根据式(31)进一步得到二分类CSD-ELM的输出函数为式(32)。

$ \mathit{\boldsymbol{\beta }} = \left\{ \begin{array}{l} {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}} \cdot {\left( {\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}} + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right],N \le L\\ {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right] + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right],N > L \end{array} \right. $

(31)

$ f\left( \mathit{\boldsymbol{x}} \right) = {\rm{sign}}\;\mathit{\boldsymbol{h}}\left( \mathit{\boldsymbol{x}} \right)\mathit{\boldsymbol{\beta }} = \left\{ \begin{array}{l} {\rm{sign}}\;\mathit{\boldsymbol{h}}\left( \mathit{\boldsymbol{x}} \right){\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}{\left( {\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}} + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right],N \le L\\ {\rm{sign}}\;\mathit{\boldsymbol{h}}\left( \mathit{\boldsymbol{x}} \right){\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right] + \mathit{\boldsymbol{I}}} \right)^{ - 1}} \cdot \\{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]^{\rm{T}}}\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right],N > L \end{array} \right. $

(32)

CSD-ELM算法描述如下:

算法2  CSD-ELM算法

输入  训练样本集D={(x_i, t_i)}_i=1^N, 其中, x_i∈Rⁿ, t_i∈{+1, -1}, 少数类、多数类样本集D₊={(x_i⁺, t_i⁺)}_i=1^N₊、D_-={(x_i^-, t_i^-)}_i=1^N_-, 其中, x_i⁺、x_i^-∈Rⁿ, t_i⁺=+1, t_i^-=-1, ELM的隐含层节点数L, 隐含层激活函数G(x)

输出  二分类CSD-ELM的输出函数f(x)

步骤1  根据任意随机概率分布函数产生ELM输入层与隐含层间的连接权值{a_j}_j=1^L及隐含层偏置值{b_j}_j=1^L, 从而得到隐含层输出函数h(x)=[G(a₁, b₁, x), G(a₂, b₂, x), …, G(a_L, b_L, x)]。

步骤2  根据式(4)、式(5)、式(8)及式(9)分别计算t₊、t_-、H₊及H_-。

步骤3  根据式(1)计算少数类错分惩罚因子C⁺及多数类错分惩罚因子C^-。

步骤4  根据算法1计算少数类加权矩阵W⁺及多数类加权矩阵W^-。

步骤5  根据式(31)计算ELM隐含层与输出层间的连接权值β。

步骤6  根据式(32)返回二分类CSD-ELM的输出函数f(x)。

1.4 算法时间复杂度分析

由式(24)可得N≤L时β的计算公式为:

$ \begin{array}{l} \mathit{\boldsymbol{\beta }} = {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}} \right)_{L \times N}}\left( {{{\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]}_{N \times N}} \cdot } \right.\\ \;\;\;\;\;\;\left. {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}_{N \times L}} \cdot {{\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}} \right)}_{L \times N}} + {\mathit{\boldsymbol{I}}_{N \times N}}} \right)_{N \times N}^{ - 1} \cdot \\ \;\;\;\;\;\;{\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]_{N \times N}}{\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right]_{N \times 1}} \end{array} $

(33)

可得此时计算β的时间复杂度为:

$ \begin{array}{l} {O_{N \le L}} = O\left( {{N^3} + L{N^2} + L{N^2} + \Delta N + L{N^2} + L{N^2}} \right) = \\ \;\;\;\;\;\;\;\;\;\;O\left( {{N^3} + 4L{N^2} + LN} \right) \end{array} $

(34)

由式(30)可得N>L时β的计算公式为:

$ \begin{array}{l} \mathit{\boldsymbol{\beta }} = \left( {{{\left( {\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]} \right)}_{L \times N}}{{\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]}_{N \times N}} \cdot } \right.\\ \;\;\;\;\;\;\left. {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}_{N \times L}} + {\mathit{\boldsymbol{I}}_{L \times L}}} \right)_{L \times L}^{ - 1} \cdot {\left( {{{\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{H}}_ + }}\\ {{\mathit{\boldsymbol{H}}_ - }} \end{array}} \right]}^{\rm{T}}}} \right)_{L \times N}} \cdot \\ \;\;\;\;\;\;{\left[ {\begin{array}{*{20}{c}} {{C_ + }{\mathit{\boldsymbol{W}}_ + }}&\mathit{\boldsymbol{O}}\\ \mathit{\boldsymbol{O}}&{{C_ - }{\mathit{\boldsymbol{W}}_ - }} \end{array}} \right]_{N \times N}}{\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{t}}_ + }}\\ {{\mathit{\boldsymbol{t}}_ - }} \end{array}} \right]_{N \times 1}} \end{array} $

(35)

可得此时计算β的时间复杂度为:

$ \begin{array}{l} {O_{N > L}} = O\left( {{L^3} + {L^2}N + L{N^2} + LN + L{N^2} + {L^2}N} \right) = \\ \;\;\;\;\;\;\;\;\;\;O\left( {{L^3} + 2L{N^2} + 2{L^2}N + LN} \right) \end{array} $

(36)

由于:

$ \begin{array}{l} \left( {{N^3}/4L{N^2} + LN} \right) - \left( {{L^3} + 2L{N^2} + 2{L^2}N + LN} \right) = \\ \;\;\;\;\;\;\;{N^3} - {L^3} + 2L{N^2} - 2{L^2}N = \\ \;\;\;\;\;\;\;\left( {N - L} \right)\left( {{N^2} + {L^2} + 3NL} \right)\left\{ {\begin{array}{*{20}{l}} { \le 0,N \le L}\\ { > 0,N > L} \end{array}} \right. \end{array} $

(37)

故有:

$ \left\{ {\begin{array}{*{20}{l}} {{O_{N \le L}} \le {O_{N > L}},N \le L}\\ {{O_{N > L}} < {O_{N \le L}},N > L} \end{array}} \right. $

(38)

由式(38)可知, CSD-ELM算法总能在较低的时间复杂度下求解β。

2 实验结果与分析 2.1 评价指标

二分类问题的分类性能评价通常建立在表 1所示的分类结果混淆矩阵基础上^[19], 其中, 将少数类规定为正类, 多数类规定为负类。

在表 1中, TP和FP分别表示被分类器预测为正类、真实类别为正类和负类的样本数量, TN和FN分别表示被分类器预测为负类、真实类别为负类和正类的样本数量。由上述4个量可以定义如下常用的分类性能评价指标:

$ ACC = \frac{{TP + TN}}{{TP + TN + FP + FN}} $

(39)

$ \mathit{Precision} = \frac{{TP}}{{TP + FP}} $

(40)

$ \mathit{Recall} = \frac{{TP}}{{TP + FN}} $

(41)

$ F1 = \frac{{2 \times \mathit{Precision} \times \mathit{Recall}}}{{\mathit{Precision} + \mathit{Recall}}} $

(42)

$ G - mean = \sqrt {\frac{{TP}}{{TP + FN}} \times \frac{{TN}}{{TN + FP}}} $

(43)

其中, ACC表示被预测类别正确的样本占总样本的比例, 其被称为整体分类精度(简称为分类精度), Precision称为查准率, 表示所有被预测为正类的样本中真实类别为正类的样本所占的比例, Recall称为查全率, 表示所有真实类别为正类的样本中被正确预测为正类的样本所占的比例, F1为查准率和查全率的调和平均, 当查准率和查全率大小相当时F1较大, G-mean为正类分类正确率和负类分类正确率的几何平均, G-mean较高, 说明分类器对正类和负类的分类性能都较好。

针对不平衡数据分类的特点, 为更全面地评价分类器对多数类与少数类样本的综合分类性能, 本文选取G-mean作为分类器性能的主要评价指标, 并将F1、ACC作为分类器性能评价的辅助指标。

2.2 实验设置

本文实验的硬件环境为Intel i5-6200U 4核CPU, 主频2.30 GHz, 内存8 GB, 操作系统为Win10 64位, 编译环境为Python 3.6。

本文从KEEL数据仓库^[20]中选取8个二分类不平衡数据集进行算法对比与性能测试。实验数据集在选取时尽可能地考虑样本数量与不平衡比率的多样性, 数据集具体信息如表 2所示。为综合评价CSD-ELM算法的分类性能与计算效率, 本文将其与ELM、WELM、CCR-ELM等多种算法进行对比。在算法涉及的参数设置上, 参照文献[2, 10]的方法设置统一的取值范围, 并通过网格搜索方法针对具体的分类性能指标寻求最优参数组合, 各算法参数设置范围如表 3所示, 其中, 隐含层节点激活函数统一使用Sigmoid函数。同时, 为体现实验的公正性, 本文采用10折交叉检验的方法, 取10次结果的平均值及标准差作为最终实验结果。

2.3 结果分析

从表 4可以看出, 与原始ELM算法相比, WELM、CCR-ELM、CSD-ELM算法在G-mean、F1两项分类性能指标上多数都有所提升, 但ACC指标提升幅度普遍较低, 甚至在某些数据集上还有所下降。造成该现象的原因在于:在未采取任何不平衡数据处理技术的情况下, 因为样本数量的悬殊差距, 传统的ELM算法必然会产生倾向于多数类样本的分类结果, 最终使其总体分类精度ACC较高; 而改进ELM算法由于使用了样本加权或者类别区分惩罚技术, 因此其少数类样本的分类精度得到了有效提升, 这些算法的G-mean及F1值也较高。在WELM、CCR-ELM、CSD-ELM 3种算法的对比中, WELM及CSD-ELM都表现出了较强的稳定性, 而CCR-ELM算法则在一些数据集(尤其是不平衡度较高的glass5、yeast6数据集)上出现了一定程度的性能波动。本文CSD-ELM算法不仅同时使用了样本加权和类别区分惩罚技术, 并且针对不同数据集的类别分布特点设计了与其不平衡比率相关联的正负类别惩罚因子, 使用Mini-batch k-means聚类算法并基于聚类后各簇中心点的距离测度对同一类别内部样本进行区分加权, 上述设计都有助于其更精准地进行分类。从实验结果也可以看出, CSD-ELM算法在多数数据集上都取得了最高的G-mean及F1值。

由表 5可以看出, 各算法的训练时间基本上都随训练数据集样本数量的增多而增加。在同一训练数据集中, ELM算法的平均训练时间最短, 其他3种算法的训练时间都要高于原始ELM算法。而在WELM、CCR-ELM、CSD-ELM 3种算法的对比中, CCR-ELM算法的训练时间普遍较低, CSD-ELM算法的训练时间最高。造成该现象的原因在于, WELM增加了加权矩阵的计算, 而CSD-ELM则要额外基于聚类与距离测度来计算每个样本的类内加权值等。

3 结束语

本文提出一种不平衡数据分类算法CSD-ELM。分别设计错分惩罚因子与类内样本权值的确定方法, 在此基础上, 利用约束优化理论, 根据训练样本数与ELM隐含层节点数间的关系, 分2种情况求解ELM隐含层与输出层间的连接权值。实验结果表明, 相比于ELM、WELM、CCR-ELM 3种算法, CSD-ELM算法的G-mean、F1指标值较高, 分类性能较好, 但其平均训练时间高于3种对比算法。因此, 下一步将通过增量式训练方法, 在提高CSD-ELM算法分类性能的同时缩短其训练时间。