西南大学学报 (自然科学版)  2018, Vol. 40 Issue (12): 163-172.  DOI: 10.13718/j.cnki.xdzk.2018.12.025
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    周国华
    申燕萍
    殷新春
    欢迎关注西南大学期刊社
     

  • 基于凸壳的在线单类学习机    [PDF全文]
    周国华1,2, 申燕萍1, 殷新春2     
    1. 常州轻工职业技术学院 信息工程系, 江苏 常州 213164;
    2. 扬州大学 信息工程学院, 江苏 扬州 225127
    摘要:传统的基于支持向量机的单类分类器因计算复杂度高而无法满足大规模数据实时处理的需求,在线学习方法为解决该问题提供了一种有效途径.本文在挖掘样本数据在特征空间分布性状的基础上,提出了一种基于凸壳的在线单类学习机(One-class Online Classifier based on Convex Hull,OOCCH).该方法首先使用凸壳的定义选择能代表特征空间中数据分布的凸壳向量对应的原始样本作为训练样本来缩减训练集的规模;其次在分类器在线更新阶段利用凸壳向量动态地调整分类器的训练样本.理论分析证明了OOCCH的有效性,与现有的在线单类分类器的实验比较,OOCCH在训练时间和分类性能方面有显著优势.
    关键词在线学习    单类    分类    凸壳    

    机器学习是人工智能中最具智能特性和最前沿的研究分支之一,它利用经验产生学习模型以提高系统的性能.机器学习在机器故障诊断、网络流量监测和垃圾邮件分类等领域应用广泛,但这些应用领域的数据常存在类别样本数严重不平衡的情况,如机器故障诊断中正常样本占绝大多数,而故障样本往往稀缺,类型多样且获取代价极高.机器学习中的单类分类器可以很好地适应这种分类场景,单类分类器通过对一个类别的样本进行学习形成对该类别的数据描述,从而根据设计的相似性度量和阈值来判别新样本的归属[1].根据分类原理,单类分类器可以分成4类:基于密度估计的算法[2-3]、基于聚类的算法[4-5]、基于神经网络的算法[6-7]和基于支持向量机(SVM)的算法[8-9].但这4类单类分类器皆存在一定的缺陷:基于密度估计的单类分类器不适用于高维数据场景;基于聚类的单类分类器对聚类的相似性度量不易定义且对噪声敏感;而基于神经网络和SVM的算法因其复杂度较高不适用于大规模数据的场景.

    随着云计算、传感器等新兴技术的快速发展,产生越来越多的大规模数据,这些大规模数据还同时具有实时性、动态性和突发性等特征[10-11].传统单类分类器训练时将数据作为整体进行批量学习,不适应海量数据和流式数据.在线学习是面对该挑战的有效解决方法之一.在线学习首先使用部分数据建立一个初始模型,然后按时序一次处理一个或者一小批数据来更新模型,从而有效降低训练模型的复杂度,同时也可以保留数据的最新信息[12].根据模型是线性还是非线性,在线学习方法可分为2类:第一类是线性在线学习方法,如基于感知器的在线学习算法[13]和稀疏在线学习算法[14]等;第二类是以使用核技术为代表的非线性学习方法,如基于SVM的在线学习算法[15]等. SVM借助统计学习理论和最优化方法解决机器学习的问题,并凭借其优秀的泛化性能成为模式识别领域一个非常重要的分支.在处理非线性不可分的数据分类时,SVM通常采用核化的方法将原始数据映射到高维核空间中,且核化后的最优化问题常描述成二次规划问题.例如Wang T.等人[9]提出了稀疏化的在线最小二乘SVM算法;Krell M.M.等人[15]结合特征选择提出了在线学习的单类学习算法,用于解决不平衡数据的分类问题.

    针对上述问题,本文提出了一种适用于大规模数据环境下的基于凸壳的在线单类学习机(OOCCH). OOCCH做了以下4个方面的尝试:

    1) OOCCH基于凸壳技术得到特征空间中能代表数据分布信息的凸壳向量,并使用凸壳向量对应的原始样本作为训练数据,在分类精度相当的条件下,比传统的基于SVM在线学习方法训练速度快且高效;

    2) OOCCH基于凸壳的定义动态地调整分类器的训练样本,以对后续样本进行在线学习,保证数据的完整性;

    3) 从理论上证明凸壳向量对应的原始样本作为训练数据的分类器在精度上是有保证的;

    4) 对比4种不同的单类分类在线学习算法,验证OOCCH在保证分类精度的同时能显著提升大规模数据在线分类的实时性,是一种处理大规模数据在线学习的有效工具.

    1 单类SVM

    单类SVM主要分为基于超球法和基于超平面法这2类.前者确定一个能够包含所有训练样本的体积最小化的超球,后者构建一个超平面来描述数据集中正常的样本.这里介绍基于超平面法的单类SVM,假设有N个样本的数据集X={xi|xiRdi=1,2,…,N},特征映射φ将样本x映射到特征空间F中,超平面法的单类SVM可以表示为如下的优化问题:

    $ \begin{array}{*{20}{c}} {\mathop {\min }\limits_{\mathit{\boldsymbol{w}},\xi ,\rho } \frac{1}{2}{\mathit{\boldsymbol{w}}^{\rm{T}}}\mathit{\boldsymbol{w}} - \rho + \frac{1}{{\nu N}}\sum\limits_{i = 1}^N {{\xi _i}} }\\ {\begin{array}{*{20}{c}} {{\rm{s}}.\;{\rm{t}}.\;\rho - {\mathit{\boldsymbol{w}}^{\rm{T}}}\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right) - {\mathit{\boldsymbol{\xi }}_i} \le 0,{\mathit{\boldsymbol{\xi }}_i} \ge 0}&{i = 1,2, \cdots ,N} \end{array}} \end{array} $ (1)

    其中,wRd是超平面的法向量,ρR是超平面的偏置量,ν为一常数.其对偶形式可表示为

    $ \begin{array}{*{20}{c}} {\sum\limits_{i,j = 1}^N {{\alpha _i}{\alpha _j}K\left( {{\mathit{\boldsymbol{x}}_i},{\mathit{\boldsymbol{x}}_j}} \right)} }\\ {\begin{array}{*{20}{c}} {{\rm{s}}.\;{\rm{t}}.\;\sum\limits_{i = 1}^N {{\alpha _i}} = 1,0 \le {\alpha _i} \le \frac{1}{{\nu l}}}&{i = 1,2, \cdots ,N} \end{array}} \end{array} $ (2)

    单类SVM的决策函数为

    $ f\left( \mathit{\boldsymbol{x}} \right) = {\rm{sign}}\left( {{\mathit{\boldsymbol{w}}^{\rm{T}}}\mathit{\boldsymbol{x}} - \rho } \right) $ (3)

    对于测试样本,如果f(x)=1,则判定该样本为正常类;如果f(x)=-1,则判定该样本为例外点.由式(2)可以看出单类SVM的计算复杂度为O(N3).

    2 基于凸壳的在线单类分类器 2.1 基本思想

    单类SVM的分类本质可以表现为寻找一个能最大化与原点之间距离的超平面,并根据训练数据的几何分布,累积求出支持向量.因为只有在目标类的训练数据中,单类SVM将原点虚设为非目标类唯一的样本.受这一思想启发,本文认为构建单类SVM分类器仅需使用能代表训练数据轮廓范围的样本而无需使用全部的训练样本,并且删除轮廓内部样本对构建分类器没有影响.凸壳是计算几何中的概念,对于给定的集合X,凸壳是包含所有样本的最小凸集,它由凸壳顶点构成,样本集X内所有的样本都可用凸壳向量的线性组合来表示[16],即

    $ {\mathit{\boldsymbol{x}}_i} = \sum\limits_{{\mathit{\boldsymbol{x}}_t} \in {\mathit{\boldsymbol{X}}^ * }} {{\mu _{i,t}}{\mathit{\boldsymbol{x}}_t}} $ (4)

    其中X*X的凸壳向量集,$\sum\limits_{{{\mathit{\boldsymbol{x}}}_{t}}\in {{\mathit{\boldsymbol{X}}}^{*}}}{{{\mu }_{i,t}}}=1$μit≥0.

    本文所提的在线单类分类器首先计算得到训练集在特征空间的凸壳向量,在构建初始分类器时将这些凸壳向量对应的原始样本作为训练数据.在线学习阶段,在接受到新样本后对样本进行分类,同时辨别该样本是否是特征空间的凸壳向量,如果是则将其对应的原始样本加入到训练数据集中,并更新分类器;如果不是则不更新分类器.

    2.2 OOCCH算法描述

    OOCCH在线分类器的构建可以分为3个阶段:1)选择初始训练集在特征空间的凸壳向量;2)训练初始分类器;3)在线分类器的更新.下面详细介绍OOCCH在线分类器的3个阶段.

    第1阶段,选择初始训练集在特征空间的凸壳向量. OOCCH这一阶段的工作可分为4个步骤:1)使用支持向量数据描述(Support Vector Data Description,SVDD)[17]得到特征空间下能够包含初始训练集样本的体积最小化的超球,并设超球球面上的向量是特征空间下的凸壳集的初始集M*;2)对得到的特征向量按照其到超球球心的距离进行降序排序,形成特征数据集φ(X*);3)计算当前凸壳集的向量权重λ的值,即:

    $ \begin{array}{*{20}{c}} {\mathop {\min }\limits_\lambda {{\left\| {\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right) - \sum\limits_{t = 1}^{\left| {{\mathit{\boldsymbol{M}}^ * }} \right|} {{\lambda _{i,t}}\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right)} } \right\|}^2}}\\ {{\rm{s}}.\;{\rm{t}}.\;\sum\limits_{t = 1}^{\left| {{\mathit{\boldsymbol{M}}^ * }} \right|} {{\lambda _{i,t}}} = 1,0 \le {\lambda _{i,t}} \le 1} \end{array} $ (5)

    其中,|M*|表示M*中样本的个数.将式(5)的常数项舍弃后,式(5)的求解可以转化为以下的二次规划形式:

    $ \begin{array}{*{20}{c}} {\mathop {\min }\limits_\lambda 2\varphi {{\left( {{\mathit{\boldsymbol{x}}_i}} \right)}^{\rm{T}}}{\mathit{\boldsymbol{M}}^ * }\lambda + {\lambda ^{\rm{T}}}{\mathit{\boldsymbol{M}}^ * }^{\rm{T}}{\mathit{\boldsymbol{M}}^ * }^\lambda }\\ {{\rm{s}}.\;{\rm{t}}.\;\sum\limits_{t = 1}^{\left| {{\mathit{\boldsymbol{M}}^ * }} \right|} {{\lambda _{i,t}}} = 1,0 \le {\lambda _{i,t}} \le 1} \end{array} $ (6)

    4) 根据排序结果依次判断非初始集M*中的每个向量φ(xi)是否是凸壳向量,其中xiX*φ(xi)∉M*,即

    $ {\left\| {\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right) - \sum\limits_{t = 1}^{\left| {{\mathit{\boldsymbol{M}}^ * }} \right|} {{\lambda _{i,t}}\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right)} } \right\|^2} \le \mu $ (7)

    若式(7)的计算结果小于阈值μ,则表示φ(xi)能用当前的凸壳向量线性表示,说明φ(xi)不是凸壳向量;反之,若式(7)的计算结果大于阈值μ,说明φ(xi)是凸壳向量,将其并入当前的凸壳向量集M*中,即M*=M*φ(xi).同时,通过上式也可以得到:

    $ \varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right) = \sum\limits_{\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right) \in {\mathit{\boldsymbol{M}}^ * }} {{\lambda _{i,t}}\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right)} + {\tau _i} $ (8)

    其中,‖τi2μi=|M*|+1,|M*|+2,…,N.

    第2阶段,训练初始分类器.将第1阶段得到的凸壳向量集M*中对应的原始数据作为训练样本Xtrain代入式(2),完成OOCCH初始分类器的训练.

    第3阶段,在线分类器的更新.传统的在线学习算法中,常采用两类方法更新分类器,一是将新样本直接加入到训练集中重新训练分类器;二是将新样本与上一阶段构成分类器的支持向量合并组成新的训练集,重新训练分类器.但第一类方法会随着训练集容量的增长而使分类器的训练效率急剧下降,不适用于大数据环境的实时分类要求.第二类方法保留在线分类器的支持向量作为训练数据,但支持向量仅与分类器构建的分类面相关,不能很好地代表数据在特征空间的轮廓分布.当新到达的训练数据与历史训练数据的分布存在变化时,这一类方法的分类效果不佳.

    OOCCH在这一阶段使用式(3)判断新到达的一个(一批)样本xnew的类别,如果是目标类样本,则将Xtrain代入以下函数判断其是否是候选凸壳向量:

    $ f'\left( {{\mathit{\boldsymbol{x}}_{{\rm{new}}}}} \right) = {\mathit{\boldsymbol{w}}^{\rm{T}}}\varphi \left( {{\mathit{\boldsymbol{x}}_{{\rm{new}}}}} \right) - \rho $ (9)

    如果|f(xnew)|≤1+β(β是设定的很小的常数),则将新样本加入到训练集Xtrain中,即

    $ {\mathit{\boldsymbol{X}}_{{\rm{train}}}} = {\mathit{\boldsymbol{X}}_{{\rm{train}}}} \cup \left\{ {{\mathit{\boldsymbol{x}}_{{\rm{new}}}}} \right\} $

    如果|f(xnew)|>1+β,则不更新训练集Xtrain.

    为了减少在线分类器更新阶段的运算量,OOCCH将分布在分类面边界周围的样本纳入到训练集中.但随着在线分类器的不断更新,训练集Xtrain的容量也在不断增长.当Xtrain的容量超过设定的阈值K时,OOCCH重新计算训练集的凸壳向量,将新得到的凸壳向量对应的原始样本作为当前的训练数据.

    2.3 OOCCH精度和时间复杂度分析

    本节首先从理论上证明使用凸壳向量对应的原始样本作为单类分类器的训练样本在精度上是有保证的.这里将式(2)改写成无约束目标函数,命名为F(wρ),则

    $ \mathop {\min }\limits_{\mathit{\boldsymbol{w}},\rho } \frac{1}{2}{\left\| \mathit{\boldsymbol{w}} \right\|^2} + \frac{1}{{\nu N}}\sum\limits_{i = 1}^N {l\left( {\mathit{\boldsymbol{w}},\rho ,\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} - \rho $ (10)

    其中,l(wρφ(xi))=max{0,ρ-wTφ(xi)},i=1,2,…,N.

    定理1    假设(w1*ρ1*)是使用全部训练集代入式(2)得到的单类在线分类器的最优解,(w2*ρ2*)是使用凸壳向量对应的原始样本代入式(2)得到的单类在线分类器的最优解,则

    $ {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) \le \frac{{N - \left| {{\mathit{\boldsymbol{M}}^ * }} \right|}}{{N \cdot \nu }}\sqrt {\frac{\mu }{\nu }} $

    $ {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) = \frac{1}{2}{\left\| {\mathit{\boldsymbol{w}}_2^ * } \right\|^2} + \frac{1}{{\nu N}}\sum\limits_{i = 1}^N {l\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * ,\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} - \rho _2^ * $
    $ {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) = \frac{1}{2}{\left\| {\mathit{\boldsymbol{w}}_2^ * } \right\|^2} + \frac{1}{{\nu N}}\sum\limits_{i = 1}^{\left| {{\mathit{\boldsymbol{M}}^ * }} \right|} {l\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * ,\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} - \rho _2^ * $

    可得

    $ {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) = \frac{1}{{N \cdot \nu }}\sum\limits_{i = \left| {{\mathit{\boldsymbol{M}}^ * }} \right| + 1}^N {l\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * ,\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} $

    因为

    $ \begin{array}{*{20}{c}} {\rho _2^ * - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right) \le 0}&{i = 1,2, \cdots ,\left| {{\mathit{\boldsymbol{M}}^ * }} \right|} \end{array} $

    根据式(8)可得

    $ \begin{array}{l} \rho _2^ * - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right) = \rho _2^ * - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}\left( {\sum\limits_{\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right) \in {\mathit{\boldsymbol{M}}^ * }} {{\lambda _{i,t}}\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right)} + {\tau _i}} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\rho _2^ * - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}\sum\limits_{\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right) \in {\mathit{\boldsymbol{M}}^ * }} {{\lambda _{i,t}}\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right)} - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}{\tau _i} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right) \in {\mathit{\boldsymbol{M}}^ * }} {{\lambda _{i,t}}\left[ {\rho _2^ * - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}\varphi \left( {{\mathit{\boldsymbol{x}}_t}} \right)} \right]} - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}{\tau _i} \le - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}{\tau _i} \le \left\| {\mathit{\boldsymbol{w}}_2^ * } \right\|\left\| {{\tau _i}} \right\| \end{array} $

    参照文献[18],可得

    $ \left\| {\mathit{\boldsymbol{w}}_2^ * } \right\| \le \sqrt {\left| {{\mathit{\boldsymbol{M}}^ * }} \right|/\left( {\nu ,N} \right)} \le \sqrt {1/\nu } $

    所以可得

    $ \begin{array}{l} \frac{1}{{N \cdot \nu }}\sum\limits_{i = \left| {{\mathit{\boldsymbol{M}}^ * }} \right| + 1}^N {l\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * ,\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} = \frac{1}{{N \cdot \nu }}\sum\limits_{i = \left| {{\mathit{\boldsymbol{M}}^ * }} \right| + 1}^N {\left( {\rho _2^ * - \mathit{\boldsymbol{w}}_2^{ * {\rm{T}}}\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} \le \\ \frac{1}{{N \cdot \nu }}\sum\limits_{i = \left| {{\mathit{\boldsymbol{M}}^ * }} \right| + 1}^N {\left\| {\mathit{\boldsymbol{w}}_2^ * } \right\|\left\| {{\tau _i}} \right\|} \le \frac{1}{{N \cdot \nu }}\sum\limits_{i = \left| {{\mathit{\boldsymbol{M}}^ * }} \right| + 1}^N {\sqrt {\frac{\mu }{\nu }} } = \frac{{N - \left| {{\mathit{\boldsymbol{M}}^ * }} \right|}}{{N \cdot \nu }}\sqrt {\frac{\mu }{\nu }} \end{array} $

    因此得证.

    定理2    假设

    $ {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) = \frac{1}{2}{\left\| {\mathit{\boldsymbol{w}}_2^ * } \right\|^2} + \frac{1}{{\nu N}}\sum\limits_{i = 1}^N {l\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * ,\varphi \left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right)} - \rho _2^ * $

    $ {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_1^ * ,\rho _1^ * } \right) \le \frac{{N - \left| {{\mathit{\boldsymbol{M}}^ * }} \right|}}{{N \cdot \nu }}\sqrt {\frac{\mu }{\nu }} $

    $ {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_1^ * ,\rho _1^ * } \right) \le {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_1^ * ,\rho _1^ * } \right) - {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_1^ * ,\rho _1^ * } \right) \le 0 $

    由定理1可得

    $ \begin{array}{l} {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_1^ * ,\rho _1^ * } \right) = \\ {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) + {\mathit{\boldsymbol{F}}_2}\left( {\mathit{\boldsymbol{w}}_2^ * ,\rho _2^ * } \right) - {\mathit{\boldsymbol{F}}_1}\left( {\mathit{\boldsymbol{w}}_1^ * ,\rho _1^ * } \right) \le \\ \frac{{N - \left| {{\mathit{\boldsymbol{M}}^ * }} \right|}}{{N \cdot \nu }}\sqrt {\frac{\mu }{\nu }} \end{array} $

    因此得证.

    下面讨论OOCCH算法的时间复杂度.在OOCCH第1阶段,使用序贯最小优化法(SMO)求解式(6)~(7),并以渐进的方式得到凸壳集,其计算复杂度为$O(\sum\limits_{i=1}^{\mathit{\boldsymbol{M}}}{n_{i}^{2}})$,其中Mni分别是SVDD边界向量和当前凸壳向量集的容量.在OOCCH第2阶段,仍使用SMO方法训练初始分类器,计算复杂度为O(|M*|2),其中|M*|是第1阶段最终获得的凸壳向量集的容量.第3阶段是分类器的在线更新阶段,OOCCH使用式(9)判断新到达的样本xnew是否是候选凸壳向量,其时间复杂度为线性.因此OOCCH总的计算复杂度为$O(\sum\limits_{i=1}^{\mathit{\boldsymbol{M}}}{n_{i}^{2}+{{\left| {{\mathit{\boldsymbol{M}}}^{*}} \right|}^{2}}})$,而|M*|值远小于训练样本容量N,因此该方法能适用于大规模样本的在线分类场景中.

    3 实验与分析 3.1 实验设置

    本节通过真实数据[19](数据详细信息如表 1所示)对OOCCH分类器进行分析与验证,并与4种基于SVM的单类分类在线学习算法进行比较:IOCSVM[8]、LS-OC-SVM[9]、WOCSVM [20]和SO-LS-SVM[21].所有的SVM分类器均采用高斯核,核参数σ范围为{10-2,10-1,…,102},正则化参数范围为{10-3,10-2,…,103}(为保持参数的一致性,OOCCH的正则化参数设为1/νN). OOCCH分类器的误差阈值μ范围为{10-4,10-3,10-2},K=103β=10-3.另外,各对比算法的参数设置均参照文献中的默认设置.实验在2.53-GHz quad-core CPU,8-GB RAM,Windows 7系统下执行,所有算法均在Matlab 2016b环境下实现.

    表 1 数据集的基本信息

    参照文献[16]的实验设置,本文实验分为4个步骤:第1步,产生实验数据.首先随机选取90%正类样本和部分负类样本,使得产生的数据集中95%的训练样本属于正常类,而5%的训练样本属于异常类;然后将数据集随机分成10份,训练集、扩展集和测试集所占比为3:4:3,其中训练集用于初始分类器的训练,扩展集用于分类器的更新,测试集用于分类器的分类测试.实验中这一操作重复10次,产生10组不同的训练集、扩展集和测试集.第2步,初始分类器的训练.各算法完成给定训练数据集的初始分类器的训练,各调节参数的设置通过5重交叉验证法来选取最优值.在这一步骤中,OOCCH基于凸壳的定义选择能代表样本在特征空间轮廓分布的凸壳向量,使用凸壳向量对应的原始样本作为训练数据来完成初始分类器的训练.第3步,分类器的在线更新,各算法使用扩展集对分类器进行在线更新.实验中扩展集分成10份,每次使用1份扩展集更新分类器.第4步:测试评估.当所有在线分类器完成更新后,我们使用测试集评估分类器的性能.

    为了更好地评价单类分类器的性能,实验采用G-mean[22]F-measure[23]评价准则,

    $ G - mean = \sqrt {Positive\;Accuracy \times Negative\;Accuracy} $ (11)
    $ F - measure = \frac{{2 \times \mathit{Recall} \times \mathit{Precision}}}{{\mathit{Recall} + \mathit{Precision}}} $ (12)

    其中,G-mean能有效评价数据整体的分类性能,F-measure侧重评价异常类样本的分类准确率. Positive Accuracy是异常类样本的分类正确率,Negative Accuracy是正常类样本的分类正确率,Precision=TP/(TP+FP)为查准率,其中TP是被正确分类的异常类样本数,FP是被错误分类的正常类样本数,Recall=Positive Accuracy.

    3.2 OOCCH参数选择

    OOCCH分类器中有3个参数需要从给定的范围内选取最优值,这3个参数分别是:误差阈值μ、正则化参数和高斯核参数σ.根据文献[24]分析,正则化参数和高斯核参数σ宜在一定范围内采用交叉验证法得到,而OOCCH中误差阈值μ与特征空间中凸壳的选择和算法运行时间密切相关.因此,本小节从凸壳向量数量和凸壳选择运行时间2方面讨论误差阈值μ的选择.考虑到σ与特征空间的选择有关,表 2表 3分别列出了在COV、KDD和SEI数据集上不同μσ时OOCCH得到的凸壳向量数量(标准差)和运行时间(标准差). 表 4列出了在COV、KDD和SEI数据集上不同μσ时OOCCH在测试集上的G-meanF-measure值.

    表 2 OOCCH在COV、KDD和SEI数据集上凸壳向量的数量(标准差)
    表 3 OOCCH在COV、KDD和SEI数据集上计算凸壳向量的运行时间(标准差)
    表 4 OOCCH在COV、KDD和SEI数据集上的G-mean(标准差)和F-measure(标准差)

    通过表 2~4的结果可以发现:

    1) 随着高斯核参数σ的增加,凸壳向量的数目也随着增加.这是因为:σ值与特征空间的选择有关,σ值较小时,数据在特征空间内的间距较小而分布较集中,因此获得较少的凸壳向量;反之,σ值较大时,数据在特征空间内的间距较大而分布较分散,因此获得较多的凸壳向量.

    2) 当误差阈值μ较小时,满足${{\left\| \varphi ({{\mathit{\boldsymbol{x}}}_{i}})-\sum\limits_{t=1}^{\left| {{M}^{*}} \right|}{{{\lambda }_{i,t}}\varphi ({{\mathit{\boldsymbol{x}}}_{t}})} \right\|}^{2}}\le \mu $的样本较少,因此获得的凸壳向量较多,同时运行时间较长;反之,当误差阈值μ较大时,获得的凸壳向量较少,同时运行时间较小.

    3) μ值与凸壳向量数量、凸壳选择运行时间和测试集上的G-meanF-measure密切相关,凸壳向量数量较多则凸壳选择运行时间较长,但获得的G-meanF-measure值较大,这是因为凸壳向量数量越多时,越能较好地表示数据在特征空间的轮廓分布.因此在实际应用中需要从运行时间和凸壳向量数量2个方面权衡选择μ值,在下面的实验中μ值固定为μ=10-3.

    3.3 性能比较

    本小节我们在6个真实数据集上进行OOCCH与4种单类分类在线学习算法IOCSVM、LS-OC-SVM、WOCSVM和SO-LS-SVM的性能比较. 图 1图 2分别显示了OOCCH和另外4种在线学习算法训练初始分类器的运行时间和在线更新分类器的运行时间(单位:s). 表 5显示了OOCCH和对比算法在测试集上的G-mean(标准差)和F-measure(标准差)比较.根据图 12表 5的结果可以看出:

    图 1 OOCCH和对比算法训练初始分类器的时间比较(单位:s)
    图 2 OOCCH和对比算法在线更新分类器的时间比较(单位:s)
    表 5 OOCCH和对比算法在测试集上的G-mean(标准差)和F-measure(标准差)比较

    1) OOCCH在训练初始分类器和在线更新分类器上花费时间最少,因为OOCCH能够根据数据在特征空间的分布得到代表其轮廓分布的凸壳向量,并以凸壳向量对应的原始样本作为训练数据,这样在保证分类精度的情况下能有效缩减训练集的容量;

    2) OOCCH在线学习中基于凸壳的定义调整分类器的训练数据,既可以动态调整分类器,使之适应新的数据分布,同时又不增加分类器的训练负担;

    3) 前文证明使用凸壳向量对应的原始样本作为训练数据不会降低分类的性能,表 5的结果显示从G-meanF-measure 2个性能指标上OOCCH取得了令人满意的分类效果.在6个真实数据集上,除了在WWW数据集上的性能略逊于LS-OC-SVM算法外,在其他5个数据集上均取得了最优的G-meanF-measure结果.

    4 总结

    本文基于凸壳的定义提出了一种新的在线单类学习机OOCCH. OOCCH在分类器初始训练阶段使用凸壳技术对训练集进行选择,使所选样本能够在最大程度上表示数据集在特征空间的轮廓分布.在线更新阶段OOCCH再次使用凸壳技术对新到达的样本进行筛选,仅保留能改变数据集分布形状的凸壳样本作为训练集的补充.理论分析和真实数据集的仿真实验证明了本文算法具有优良的分类性能和较少的运行时间.

    参考文献
    [1] 潘志松, 陈斌, 缪志敏, 等. One-Class分类器研究[J]. 电子学报, 2009, 37(11): 2498-2503.
    [2] LIU J C, MIAO Q G, SUN Y N, et al. Modular Ensembles for One-Class Classification Based on Density Analysis[J]. Neurocomputing, 2016, 171(C): 262-276.
    [3] LIU B, XIAO Y, YU P S, et al. Uncertain One-Class Learning and Concept Summarization Learning on Uncertain Data Streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 26(2): 468-484.
    [4] KRAWCZYK B, WOZNIAK M, CYGANEK B. Clustering-Based Ensembles for One-Class Classification[J]. Information Sciences, 2014, 264(6): 182-195.
    [5] 张辉荣, 唐雁, 何荧, 等. 面向分类数据的重叠子空间聚类算法SCCAT[J]. 西南大学学报(自然科学版), 2016, 38(3): 171-176.
    [6] MANEVITZ L, YOUSEF M. One-Class Document Classification via Neural Networks[J]. Neurocomputing, 2007, 70(7/9): 1466-1481.
    [7] ZHANG M, WU J, LIN H, et al. The Application of One-Class Classifier Based on CNN in Image Defect Detection[J]. Procedia Computer Science, 2017, 114: 341-348. DOI:10.1016/j.procs.2017.09.040
    [8] 梁修荣, 杨正益. 基于聚类和SVM的数据分类方法与实验研究[J]. 西南师范大学学报(自然科学版), 2018, 43(3): 91-96.
    [9] WANG T, CHEN J, ZHOU Y, et al. Online Least Squares One-Class Support Vector Machines-Based Abnormal Visual Event Detection[J]. Sensors, 2013, 13(12): 17130-17155. DOI:10.3390/s131217130
    [10] KIVINEN J, SMOLA A J, WILLIAMSON R C. Online Learning with Kernels[J]. IEEE Transactions on Signal Processing, 2004, 52(8): 2165-2176. DOI:10.1109/TSP.2004.830991
    [11] YANG H Q, LYU M R, KING I. Efficient Online Learning for Multitask Feature Selection[J]. ACM Transactions on Knowledge Discovery from Data, 2013, 7(2): 1-27.
    [12] ZHENG J, SHEN F, FAN H, et al. An Online Incremental Learning Support Vector Machine for Large-Scale Data[J]. Neural Computing and Applications, 2013, 22(5): 1023-1035. DOI:10.1007/s00521-011-0793-1
    [13] SAITOH D, HARA K. Mutual Learning Using Nonlinear Perceptron[J]. Journal of Artificial Intelligence and Soft Computing Research, 2015, 5(1): 71-77. DOI:10.1515/jaiscr-2015-0020
    [14] LANGFORD J, LI L H, ZHANG T. Sparse Online Learning via Truncated Gradient[J]. Journal of Machine Learning Research, 2009, 10(2): 777-801.
    [15] KRELL M M, WILSHUSEN N, SEELAND A, et al. Classifier Transfer with Data Selection Strategies for Online Support Vector Machine Classification with Class Imbalance[J]. Journal of Neural Engineering, 2017, 14(2): 025003. DOI:10.1088/1741-2552/aa5166
    [16] WANG D, QIAO H, ZHANG B. Online Support Vector Machine Based on Convex Hull Vertices Selection[J]. IEEE Transaction on Neural Networks and Learning Systems, 2013, 24(4): 593-609. DOI:10.1109/TNNLS.2013.2238556
    [17] TAX D M J, DUIN R P W. Support Vector Data Description[J]. Machine Learning, 2004, 54(1): 45-66.
    [18] SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos: Primal Estimated Sub-Gradient Solver for SVM[C]//The 24th International Conference on Machine Learning. Corvalis, USA: ACM, 2007: 807-814.
    [19] UC Irvine Machine Learning Repository. UCI database[EB/OL].[2013-1-12]. https://archive.ics.uci.edu/ml/datasets.html.
    [20] KRAWCZYK B, WOZNIAK M. One-Class Classifiers with Incremental Learning and Forgetting for Data Streams with Concept Drift[J]. Soft Computing, 2015, 19(12): 3387-3400. DOI:10.1007/s00500-014-1492-5
    [21] UDDIN M S, KUH A. Online Least-squares One-Class Support Vector Machine for Outlier Detection in Power Grid Data[C]//2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Shanghai, China: IEEE, 2016: 2628-2632.
    [22] BATUWITA R, PALADE V. FSVM-CIL:Fuzzy Support Vector Machines for Class Imbalance Learning[J]. IEEE Transactions on Fuzzy Systems, 2010, 18(3): 558-571. DOI:10.1109/TFUZZ.2010.2042721
    [23] GU X Q, CHUNG F L, ISHIBUCHI H S, et al. Imbalanced TSK Fuzzy Classifier by Cross-Class Bayesian Fuzzy Clustering and Imbalance Learning[J]. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2017, 47(8): 2005-2020. DOI:10.1109/TSMC.2016.2598270
    [24] CHANG C C, LIN C J. LIBSVM:A Library for Support Vector Machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27.
    A One-Class Online Classifier Based on Convex Hull
    ZHOU Guo-hua1,2, SHEN Yan-ping1, YIN Xin-chun2     
    1. Department of Information Engineering, Changzhou Institute of Light Industry Technology, Changzhou Jiangsu 213164, China;
    2. College of Information Engineering, Yangzhou University, Yangzhou Jiangsu 225127, China
    Abstract: Facing the challenge of large-scale data processing, the traditional SVM(support vector machine) based one-class classifier suffers from its high computational complexity. The online learning technique is an effective way to solve this problem. In this paper, a one-class online classifier based on convex hull (OOCCH) is proposed by considering the distribution characteristics of the data in the feature space. In order to reduce the number of training sets, OOCCH selects the samples corresponding to the convex hull vectors in the feature space as training samples. In the online update stage of the classifier, OOCCH dynamically adjusts the training samples based on the definition of convex hull. Theoretical analysis proves the effectiveness of OOCCH. Compared with the existing online one-class classifiers in experiments, OOCCH has significant advantages in training time and classification performance.
    Key words: online learning    one-class    classification    convex hull    
    X