动态特征空间的超球体分类算法

杜 淼，余 勤，雒瑞森

四川大学 电气工程学院，成都610065

1 引言

在模式识别中，通常使用提取特征的方法对目标进行分类[1]，在分类过程中为了识别各个类别，需要找到更好的分隔面，而不同的方法在求解中有不同的分类效果。随着机器学习的发展，大量优秀的分类器被逐渐提出，通过特征进行分类与识别的应用越来越广泛，如支持向量机（Support Vector Machine，SVM）、人工神经网络（Artificial Neural Network，ANN）等。但是，在这些分类过程中，提取的特征对分隔面产生了很大的影响，并且由特征形成的特征空间不具有动态变化的过程，在很大程度上限制了识别效果。正如支持向量机被广泛应用于各种行业中，并取得了不错的效果，其通过使训练集的分类错误更小进而优化出最大分隔面。为了克服SVM形成的平行分隔面和提高SVM的效率，许多学者做出了改进[2-3]。

C-SVM 是在SVM 基础上进行了改进：（1）加入松弛变量并使用惩罚项C 约束；（2）使用核函数将原本的特征空间映射到高维[4]。C-SVM 的改进大大提高了SVM 的效率。但是之前的SVM 存在着将所有数据同时训练的问题，这个问题使得在同一个特征空间中不同类的数据同时求解一个优化问题。孪生支持向量机（Twin SVM，TWSVM）提出了分别优化两个超平面，这种方法将原本训练所有数据集的学习问题转化为两个更小的二次规划问题。通过分别求解这两个二次规划问题，得到适用于每一类分隔超平面[5]，从实验结果可以看出TWSVM表现很好。在SVM中特征空间被映射至高维，但是在不同的场景使用核函数的方法并不固定。

作为在各个领域表现非常好的神经网络，它在训练过程中使用梯度下降方法使训练的错误率不断降低来获得一个有效的模型[6]。神经动态分类器（Neural Dynamic Classification，NDC）提出另一种思想：寻找更容易分隔的特征空间来获得更好的识别率[7]。NDC 将每一个类使用感知器来构造新的特征空间，在一个特征空间中所有数据被分为+1类和－1类，通过将每一个相同的类聚集得到多个具有两个超平面的特征空间。但是算法本身具有以下缺点：（1）运算量极大，使得该算法对手写体分类时需要使用超级计算机；（2）实验效果受到迭代次数的影响，其原因在于损失函数构造不合理。

为了将SVM分隔超平面优势与神经网络的非线性优势结合，孪生神经网络（Twin Neural Networks，TNN）被提出[8]。TNN结合了TWSVM的优势，能够对每一类的训练数据分别训练出不同的分隔超平面，尤其是对于不平衡数据表现更好，并且TNN 也结合了神经网络非线性的特征变换，使得最后的分类效果得到提高。

通过TWSVM和TNN可以看出，特征变换后，针对不同类别的数据进行处理可以得到不错的效果。因此本文提出了一种动态超球体算法（Dynamic Hypersphere Algorithm，DHA），通过使用一层感知器构造动态特征空间，再利用NDC 将相同类聚集在一个超球面的思想重新构造合理的损失函数，最终将特征变换与针对每个类别进行优化的优点结合起来。本文提出的动态超球体算法克服了NDC 的两个问题：（1）计算量极大，由于NDC会生成与类别相同的特征空间，使得计算量增加；（2）收敛问题，NDC算法在构造损失函数时的思想将相同类别的特征聚集到中心点，使得随着迭代次数增加，特征点收拢至一个点，超球体半径迅速减少，最后迭代次数过多，影响最后的效果。本文提出的动态超球体算法，利用动态特征空间获得超球体分隔面，具有更好的识别效果。

2 动态超球体算法

2.1 构造动态超球体模型

图1 展示了DHA 算法的整体结构。图中从左往右依次为原始特征空间S,使用感知器进行空间变换，形成新的特征空间U,最后根据本文定义的条件得到超球体模型。在模型中，本文构造了新的损失函数，通过计算模型的分类结果与真实类别的误差，使用梯度下降[9]的方法更新参数，实现超球体的动态变化。与神经动态分类器（NDC）不同，NDC 的目标函数主要是将每一类特征点聚集到球心，而本文提出的动态超球体算法（DHA）的目标函数主要将每一类特征点约束到球内，最后导致的不同在于NDC 训练过程中超球体快速变小，过度收敛，而DHA 会呈现先快速收敛，最后缓慢变小趋于稳定。同时，DHA 也继承了TWSVM 和TNN 分别求解各个类别与特征变换的优势。

图1 DHA的整体框架

构造动态超球体的目标是特征变换后在特征空间中将相同类别的数据变换到对应的超球体中。假设数据集为S，其中有m 类共N 个样本，因此第i 个数据表示为Si,S={S1,S2,…,SN|Si∈ℝn,∀i=1,2,…,N} 。第i个样本属于第j 类表示为Sj,i，第j类的样本数量表示为Nj，特征空间的表示为：

其中，W 是n×I 的矩阵，B 是1×I 的向量，Ui是在新的特征空间U 中的第i 个点，U={U1,U2,…,UN|Ui∈ℝn,∀i=1,2,…,N}。特征变换后，开始定义构造超球体条件。超球体中心Ci与各个点到中心的距离di表示为：

其中，Ci是第i 类超球体的中心，di是第i 类的所有点到球心的总距离。为了让属于同一类的数据聚集在对应超球体中，定义了第一个条件：

为了得到第i 类数据到第i 类超球体的总距离的关系，本文做了以下定义：

为了使不属于第i 类超球体数据点在第i 类超球体外，定义了第二个条件：

其中，-i 指不属于第i 类。同理得到不属于第i 类数据到第i 类超球体的总距离的关系：

为了让每个超球体相互尽量分开，定义了第三个条件：

最后一个条件满足超球体半径大于0：

通过这些限制条件，本文构造了一种损失函数L(θ)，θ={W,B,R}：

其中，P 是惩罚系数。在计算最小化L 过程中，本文使用了梯度下降法求解θ，这些参数更新方法表示为[9]：

其中，η 是学习率。

2.2 分类方法

本文使用了一种适用于DHA 的分类方法，测试数据通过式（1）的特征变换后，被分为距离其最近的超球体对应的类，公式表示为：

3 实验结果

下面通过实验分析了DHA算法的分类效果。实验使用了深度学习框架tensorflow，编程语言为python。本文在UCI、MNIST、不平衡MNIST 数据集[10-11]进行实验。标准数据集来自UCI，每个数据集的信息展示在表1 中。为了增加统计意义，减少偶然性，最终结果选择使用连续10次实验的平均值，实验过程如图2所示。

表1 数据集信息

3.1 UCI

图2 实验过程

本节使用UCI 数据集进行实验，其中DHA 的惩罚系数P ∈[0.001,1]。在本次实验中随机抽取一定比例的数据作为测试集，剩下的作为训练集。抽取的比例包括10%，20%，30%，40%，50%，用RTT 表示。在实验中对标准数据集进行了归一化的预处理，将特征值量化到[0，1]区间。表2 展示了比较的算法在所有比例的分类效果，表3展示了比较的算法在10%抽取比例时的识别率。从表2中可以看到，DHA在大部分的数据集上具有良好的识别率，其中在RTT=10%时，DHA具有更好的表现，如表3所示。

表2 不同抽样比例下各个算法的识别率 %

表3 数据测试集为10%时各个算法的识别率 %

3.2 MNIST

本文将DHA 算法与NDC、SVM 在MNIST 上进行比较。MINST 有70 000 张图片，本次实验使用的计算机配置为i5-7400。由于本次实验计算资源有限，使用了1vs1 的策略对手写体进行分类[12]。本文在实验中一共使用了4 000 张图进行训练，意味着每个训练类别只有400张图。本次实验中，将28×28的图片转换为1×784的向量，训练集表示为（4 000，784），模型中使用参数P=0.1,W 矩阵为784×10，DHA最后的识别率为90.18%。

3.3 不平衡MNIST

本文认为DHA 能获得更好的特征空间，因此在不平衡手写体上进行了分类实验。从文献[8]中可以看到，TNN 适合于大型不平衡数据集分类，并且效果明显。本文将与TNN进行对比实验。实验中本文通过随机抽取的方法得到的数据集包括：30 张手写体“1”与3 000 张手写体“0”，30 张手写体“1”与3 000 张手写体“7”。两种手写体比例为100∶1。保持不平衡比例，本文随机抽取了3张手写体“1”与300张手写体“0”，3张手写体“1”与300张手写体“7”进行实验。最后得到4个实验结果，与MNIST 实验相同，将手写体的像素作为784 个特征点进行训练，实验中参数设置为P=0.01,W 矩阵为784×10，得到混淆矩阵[12]。如图3 所示，为了方便本文的表达，精度评价指标如下[13]：

其中，TP 是预测标签与真实标签为“True”的数量，TN是预测标签与真实标签为“False”的数量。图3 展示了不平衡手写体在TNN与DHA的实验结果。在图3所示的混淆矩阵中，颜色越深，对应区域的数值越大，在每一个混淆矩阵下给出了对应使用的算法与计算得到的识别率，以及对少数的样本的召回率、F-measure、MCC 等评价指标。

图3 TNN与DHA在不平衡手写体的实验结果

4 讨论

本文提出一种动态超球体算法（DHA），利用特征数据集，通过求解构造分隔球面，获得了更有效的特征空间。下面对第3 章实验内容与结果进行深入讨论与解释，并进一步讨论构造算法与优化特征空间，最后从MNIST扩展分析DHA应用场景。

4.1 DHA特色与优势

TWSVM、TNN 分类时主要基于SVM 分隔超平面的方法，而在形成特征空间时TNN 采用了神经网络进行了特征变换，如式（1）所示，TWSVM、TNN 的提出主要解决了数据不平衡的分类问题，其中TNN 主要在大型数据中表现良好。这两种算法的优势在于，求解分隔超平面时，各个类的数据分别用于求解优化问题，降低了不平衡数据的影响。NDC算法同样采用神经网络的方法进行特征变换，不同在于，NDC提出了一种新颖的想法，将数据分类看成两分类问题，分别求解形成的多个特征空间，最后采用高斯概率密度函数获得测试数据属于某类空间的概率。本文算法主要的不同在于：（1）结合以上优势构造新的目标函数，在一个空间形成多个超球体，在构造超球体时为了克服超球体随迭代次数迅速缩小，构造了以生成超球体为目标的函数，分隔面之间的距离作为约束项；（2）对结果采用了简单的距离进行分类。本文提出的DHA 结合了这些算法的优势：（1）采用式（1）进行特征变换；（2）分隔平面使用不同类别分别求解。通过表2 与图3 的实验结果可以发现，在标准数据集与不平衡手写体识别率表现较好。

4.2 特征空间的形成

本文算法结合了4.1节提到的优点，因此与TNN相比，在不平衡数据集上展现了一定的优势，如图3所示，“0”和“1”识别率的比较上，DHA 为98.67%，略高于TNN的97.33%。在“1”和“7”的比较上，DHA为96.83%，高于TNN 的90.34%。通过图3 实验能够证明，对于不平衡的数据形成的特征空间，DHA具有一定的优势。

为了证明形成更有效的特征空间进行了分隔平面的展示，图4（c）、（d）展示了C-SVM与DHA形成的特征空间与分隔平面。从图4（c）中可以明显观察到有些点混合到了其他类别的点中，与图4（d）比较，DHA算法通过改变特征空间获得的分隔超球面将能更好地分离各个数据点。在DHA 形成特征空间的过程中，损失函数的值逐渐降低收敛，优化半径逐渐趋于稳定，从图4（a）、（b）可以观察到这样的结果。其中从图4（b）中可以观察到随着迭代次数的增加，半径在第50 次迭代时逐渐稳定，但是随着迭代次数的增加，半径有细微的下降。结合式（12）可以看到di为一类特征点到球心的总距离，在最小化过程中，总距离减少速度与参数P 设置有关，但是可以知道在最小化过程中超球体会逐渐变小，也就是从图中的细微差别可以看到半径也会逐渐减小。

4.3 分析DHA应用场景

本文算法在UCI实验中可以发现，在大部分数据集中具有良好的识别效果，且这些数据集表示为在某种应用中的数据特征。从算法中可以知道，DHA 主要在于形成特征空间与分隔面，因此DHA 将适用于使用提取的特征来表示数据的场景，如电力系统中通过提取某些特征来分析异常情况[14-15]等。

图4 可视化变化过程，C-SVM和DHA的特征空间和分隔面

从3.2节在MNIST手写体上实验的表现来看，对于特征数据较多的情况，计算速度受到了影响，但是从另一方面来看DHA 也能形成一个有效的特征空间，在训练集数量与识别率上具有一定的优势与优化潜力。为了进一步验证DHA在形成有效空间与分隔面上具有一定的优势，3.3节展示了在不平衡比例1∶300情况下的实验。从实验结果上分析，训练数据的数量对DHA 的影响更小，且在不平衡数据集中DHA 也具有更好的实验效果。

5 结束语

本文提出了利用动态特征空间构造超球体的分类方法——动态超球体算法（DHA）。DHA利用了孪生支持向量机（TWSVM）对不同类别的数据分别求超平面思想，结合了孪生神经网络（TNN），利用感知器优化特征空间，其中在构造超球体时利用神经动态分类器（NDC）的想法，最后构造属于DHA的损失函数优化特征空间，在特征空间中形成属于每个类的超球体。

在标准数据集实验部分，本文提出的DHA 在识别率上与其他算法相比有较好的效果。如图4 所示，在Wine 标准数据集上C-SVM 形成的特征空间的分隔与DHA 特征空间的球面相比，DHA 具有通过特征空间变换能更好地将数据分隔开的效果。在手写体识别中，本文采用了构造多个分类器进行识别，通过减少训练样本也能获得较好的实验结果。不平衡手写体实验证明，DHA算法在不平衡的情况下也能找到一个有效的特征空间，充分证明了DHA利用了TNN、TWSVM在不平衡数据上的优势。综上所述，本文提出的动态超球体算法（DHA）通过线性空间变换与构造超球体空间能够寻找到更好的特征空间，在提高数据集的分类效果，结合特征空间变化与按照各类别进行目标函数的优化方面具有一定的参考价值。值得一提的是，DHA 算法在训练样本较少、不平衡较高的情况下具有着较好的表现。