作用于大数据处理的级联分类器泛化设计

李庭燎 刘馨雨 杜宁 符垚晗

摘  要： 针对级联分类器的设计主要集中于分类器组合优化等方面，有关自动化设计研究相对较少。为了简化设计流程，设计一种方法以自动设计具有理想性能的级联分类器。这种方法不需要分别考虑每个可能的级联长度并通过最终数值优化来进一步确定每个级联长度的次优参数，而是向能够设置级联的泛化边界方向来研究，探讨如何简化级联分类器的设计流程，实现自动化设计。

关键词： 级联分类器； AdaBoost算法； 大数据； 机器视觉； ROC曲线

中图分类号：TP391.41          文献标识码：A     文章编号：1006-8228（2023）05-36-04

Cascade classifier generalization design for big data processing

Li Tingliao， Liu Xinyu， Du Ning， Fu Yaohan

（Nanjing Audit University， Nanjing， Jiangsu 211815， China）

Abstract： The design of the cascade classifier mainly focuses on the classifier combination optimization， and there are relatively few studies on the automation design. In order to simplify the design process， a method is designed to automatically design a cascade classifier with ideal performance. Instead of considering each possible cascade length separately and further determining the suboptimal parameters for each cascade length by final numerical optimization， this method is investigated in the direction of being able to set generalization bounds for the cascade， and explores how to simplify the design process of cascade classifiers and achieve automated design.

Key words： cascade classifier; AdaBoost algorithm; big data; machine vision; ROC curve

0 引言

大数据技术的战略意义不在于掌握庞大的数据信息，而在于对海量快速流转的低价值密度数据进行专业化处理。伴随着云计算的兴起和社交网络软件的整合推进，网络数据呈现出愈来愈庞大、愈来愈复杂的特点，然而用于构建社交数据以从中对大数据进行理解、分析和推断的工具很少。近年来，级联分类算法在数据处理方面吸引了越来越多的关注，其可用于解决几乎所有需要在某些条件下过滤数据然后再使用另一种条件过滤的问题。由于实时的大型数据集分析需要有效处理大量的容忍经过时间内的数据，级联分类算法成为了大数据技术应用到实践领域的一块基石。

在分类的工作中，研究人员一般会融合多种机器学习算法，进而提升分类的准确性。经过运用不同方法能够设计实现差异化的分类器，例如对相同分类器使用不同训练集、对相同分类器调节不同参数等[1]。对于训练中存在的数据不均衡等情况，傅红普提出了可以应用等同复杂水平的AdaBoost分类器的级联来测定行人，其设计实现的朋辈级联不限制分类器的复杂水平，从而能够运用更多负训练样本[2]。Maale和Nandyal提出了一种基于Haar级联分类器的3阶段人脸检测系统架构，可以运用Haar级联分类器对像素人脸开展检测[3]。Faisal等人对Haar级联分类器获取的人脸进行特征化处理，运用LBPH算法提取直方图特征，进而完成了实时的人脸检测[4]。李昆仑等设计实现了基于级联SVM和分类器融合的人脸图像性别识别方法，把识别难易水平不同的样本划分成若干层次来开展训练[5]。Wu等人提出了一种漏斗结构级联（FuSt）检测框架，一方面，其结构使用多个计算有效的分布式分类器，来提出少量的候选窗口，其具有高召回率的多视图人脸；另一方面，通过使用统一的MLP级联，以集中的方式检查所有视图的建议，为高精度和低时间成本的多视图人脸检测提供了有利的解决方案[6]。兰胜坤认为，AdaBoost算法属于非常完善的人脸检测算法，AdaBoost算法内人脸的特征选取的是矩形特征，在大量的样本集内，提取样本的矩形特征进行训练，生成多个弱分类器，然后合并多个弱分类器组合为强分类器，最后级联强分类器形成最终的分类器，进而当作人脸识别的依据[7]。

通过文献总结和归纳可以发现，目前国内外学者针对级联分类器的设计主要集中于分类器组合优化，且在设计层面注重算法的优化，主要关注对级联分类器进行改进，已具备一定的研究深度。不过目前级联分类器设计的研究广度较为狭窄，关于级联分类器的自动化、智能化设计的研究相对较少。因此，本文主要研究如何简化级联分类器的设计流程，实现自动化设计。

1 级联算法

1.1 级联算法分析

级联（cascade）是计算机科学领域里的一个专有名词，一般是指多个目标之间存在的一种映射关系。计算程序通过搭建各个数据之间的级联关系，训練出多个不同的分类器并且将这些所有的分类器联合起来，最终形成一个高正确率的级联分类器，从而使得计算效率可以大大提高，并降低了失误率。因此，级联算法成为计算机领域非常常见的一个概念。通俗来讲就是把多个目标对象按照一定的规则，有等级地或者是有梯度地联结在一起，类似于树形结构一样，有层次地把这些对象组织在一起形成一个完全独立的算法结构。在这个算法结构里，当你对某个数据进行操作的时候，会影响这个数据关联的所有数据，即会对这些数据进行相应的操作从而达到所求目的的效果。传统分类算法的局限性之一在于他们难以处理不平衡的数据，因为传统的机器学习方法通常将类平衡作为先决条件[8]。而级联提供了通过对不良学习者决策进行加权平均来训练极其精确的分类的机会[9]。

通过大量的试验数据分析，可以得出级联算法和单个大提升算法之间的主要区别在于这两种算法对于各自分类器数量和错误率的架构要求不同，级联算法可以做到及时地拒绝真负类，随时终止程序的运行，从而减少整个计算过程中程序本身所加的负载[10]。考虑到这一特殊情况，本文结合级联算法的这些优点，从单个大增强分类器作为基点构建出一个级联算法，以便于筛选计算出大增强分类器中弱分类器的子集，从而可以测试出我们输入的到底是正还是负。通常来讲，如果子集输出结果显示为正的，则继续计算另一个弱分类器子集，并再次测试，以此类推，不断重复上述计算过程，直到输入被拒绝或者计算出完整的增强分类器结束程序。

1.2 增强算法架构

假设通过增强一组弱分类器，在给定的数据集上实现期望的真正率和真负率，直到分类器的ROC曲线超过所需的真正负比。以此方式获得由弱分类器h1（X），…，hT （X） 和权重α1，…，αT定义的增强分类器HB（X）：

[HB（X）=1          t=1Tαtht（X）≥0-1       t=1Tαtht（X）<0] ⑴

引入一個数据集X1，…，XN，已知类别y1，…，yN（yN∈{?1，1}）。定义I +为使HB （Xn）=1的角标n的集合，定义I?为使HB （Xn）=-1的角标n的集合。

在实践中，通常将θ t设置为n∈I+的Gt（Xn）>θ t与大于前式且n∈I?的最小Gt（Xn）之间的中点。考虑到改进级联分类算法所示的算法结构的特征是测试时间序列T1，…，TL和阈值θ1，…，θL，于是可以定义中间实值分类器：

[Gt（X）=s=1tαshs（X）] ⑵

又定义阈值θ t，使得其对于任意正例n∈I+，恒有Gt（Xn）>θ t，故可得：

[θl=θ'Tl] ⑶

容易得到通过该选择且独立于T1，…，TL时，改进算法中定义的级联在训练数据上的输出与原始增强算法完全相同。

我们通过对分类器的复杂度计算来建构一个模型，并从给定的增强分类器上派生出的所有级联中，确定一个近乎于最佳的级联[11]。虽然在这之前已经有不少研究者考虑了评估分类器的成本，但是相比传统方法，如假设一个增强分类器的计算成本的近似模型是其假正率的函数，很明显，本文中采用的动态规划方法只需要采用很少的假设和很少的计算步骤，就能获得近乎最优的序列，在减少程序计算时间的同时也带来了更多的便利，大大提高了计算效率。

1.3 级联分类改进

给定一组弱分类器[h1（）， h2（），…， hT（）]和由增强分类器HB（X）提供的权重，设置级联调度1=T0

当l ≤ L时，令：

[Fn+1（X）=Fn（X）+αTl-1hTl-1（X）] ⑷

若[Fn（X）<θl]，将X归类为负，即[H（X）=-1]；若[Fn（X）≥θl]，将X归类为正，即记[H（X）=1]，本轮计算结束，输出结果。定义[l=l+1]，继续重复以上步骤直至[l>L]。从而得到最终的强分类器：[H（X）=sign（Fn（X））]。

从上述改进级联分类算法中可以看出，所提供的分类器[H（X）]的正输入集合包含在了其增强分类器[HB（X）]的正输入集合中。[H（X）]的真正率比[HB（X）]低，而它的真负率比[HB（X）]要高得多。因此，由ROC（Receiver Operating Characteristic，接收者操作特征曲线）可以得知与[H（X）]对应的点的分布位于[HB（X）]对应点的分布的下方和左侧区域。

这种算法的特点在于权重选择和上面引用的级联分类器方面与AdaBoost有明显的相似之处。对比当下讨论的三种不同的体系架构，在传统AdaBoost算法中，所有弱分类器被一次性计算出来并分类；而在上述所提出的计算方法和传统级联算法中，在每次测试之间只计算弱分类器中的单独一个子集，后者中只需进行几次弱分类器评估即可实现负分类。从单个大增强分类器作为基点构建出的级联算法，与传统级联算法的主要区别在于：假设权值和弱分类器相同，前者将上一个分类器的输出结果保留成为了下一个分类器的输入。结果显示，所提方法中最后一个分类器的输出就达到了与传统AdaBoost增强算法的输出完全相同的效果[12]。而改进版本的级联算法与传统级联方法之间的区别在于，该方法在每个决策中都考虑了先前决策阶段的输出，这样在保证算法准确性的同时有效提高了算法效率。

2 计算优化级联设计

2.1 动态规划

再次回到改进级联分类算法中去，H （X）的输出由弱分类器[h1（X），…，hT（X）]和权重α1，…，αT ，这些定义了增强分类器中的HB （X），但同时这些数据也由测试的时间点[T1，…，TL]和它的阈值[θ1，…，θL]来定义。Tl和θl的选择是能够获得计算效率高的分类器的决定性因素。表面上，设置这些参数似乎和设置常规级联分类器的参数一样都比较困难。然而，使用动态规划可以保留提升分类器在任何给定数据集上的输出，在验证其的所有级联中，就分类器的计算成本而言，几乎是最优的。上述方法除了参数设置更加简便的优点，还可以更容易地选择检测器的真正率和真负率。实际上，在增强的分类器中，只有一个惟一的阈值，这个阈值决定了ROC曲线上分类器所处的位置点的集合。在构建级联之前只需要设置好这个阈值就足够了，从而能够保证级联可以达到ROC曲线上这个分类器的位置（对于给定的数据集）。由于构建级联的计算成本相对于增强的计算成本完全可以忽略不计，因此对于原始增强算法所能达到的ROC曲线上的任何点位，都很容易构建出来一个分类器。相比之下，以前的级联方法，要么需要为每个期望的ROC点训练一个新的级联，要么使用一种特别的方法来调整增强分类器的阈值，就要复杂很多。

使用改进级联分类算法的体系结构构建出一个计算最优级联，该级联在训练数据上具有与增强分类器完全相同的输出，也同时描述了构建分类器级联的重要步骤。此外，所提出的级联方法并不局限于某些特定的增强方法，可以使用针对给定成本指标的增强分类器，或旨在提高计算的效率。

2.2 级联成本

与以往成效较低的推销策略相比，当前缺乏能精准推荐，减少资源浪费的大数据分析工具。当前应用较多的能够在众多数据中找到有效信息的技术是策略树，它可以按照客户的偏好为其推荐更贴合他们需求的产品，同时能够对他们的需求进行有效预测。但在数据过于宏大，客户资料过于庞杂的情况下，决策树也暴露其缺点：想要及时准确的对客户的偏好和需求等情况进行正确的预测，就必然以高昂的计算成本作为代价。如何平衡精准度和计算成本之间的关系成为当前种子集合所面临的重大难题之一。

设置试验序列[T1，…，TL]，从级别t ∈{1，…，T }开始的最优级联的成本Ct可以从成本Cs >t递归定义，由此使用动态规划可以有效地获得最优计算成本，节约计算时间。可以预测从t开始的最优级联必然存在以下情况之一：

⑴ 由计算所有剩余分类器和测试结果组成的普通级联；

⑵ 由计算分类器t，…，T-1组成的级联，在T-1处进行测试，并遵循从T-1到T的最佳顺序，直至在（T-t+1）处计算第t个弱分类器，测试并遵循从t+1到T的最优顺序。

考虑改进级联分类算法类型的任何级联，At是第t个弱分类器的计算成本，B是在目标计算机上执行测试的成本，满足条件：

[Al=Tl-1≤t≤TlAt] ⑸

可得期望实际输入的计算成本C：

[C=l=1L（ATl-1+B）qTl-1]  ⑹

设置t时刻最小级联计算成本[Ct=minCt，st

[Ct，s=qt s=tTAs               s=Tqts=tTAs +Cs+1      t ≤s≤T-1] ⑺

尽管这是增强分类器的预期行为，但是有的时候对于给定的数据集却不一定是这种预期的情况。在实践中通过大量的試验可以发现，这些序列往往并不存在单调性，故可以使用平滑法对其进行处理。由于发现非平稳序列的一般线性趋势是单调的，所以可以认为结果序列的成本接近真正的最小值。

3 结束语

本文提出一种方法来自动设计具有理想性能的级联分类器，特别针对于某些给定类型的输入和给定的计算机架构来进行计算。这种方法适用于任何底层的增强方法，包括以自适应增强为特征的AdaBoost算法以及针对ROC空间给定区域的增强方法。由于产生的级联与其底层的增强分类器密切相关，故可以预期这种级联的理论属性将比临时级联更容易进行研究。相较于它在给定数据集上的性能，这种方法更倾向于探究级联的泛化边界问题，在大数据实用领域作为其他特化级联增强算法的基础。在未来的研究中仍然需要找到设置级联水平阈值更加合适的方法，以便更好地去附和原始分类器的ROC，从而能达到比实验部分显示的更好的一个水准。

参考文献（References）：

[1] 冯昊，李树青.基于多种支持向量机的多层级联式分类器研究及其在信用评分中的应用[J].数据分析与知识发现，2021，5（10）：28-36

[2] 傅红普，邹北骥，朱承璋，等.基于朋辈AdaBoost分类器级联的行人检测（英文）[J].Journal of Central South University，2020，27（8）：2269-2279

[3] Bhavana R. Maale，Dr. Suvarna Nandyal. Face RecognitionBased on Haar Cascade Classifier[J].Journal of Research in Science and Engineering，2021，3（5）

[4] Izhar Faisal，Ali Sajid，Ponum Mahvish，MahmoodMuhammad Tahir，Ilyas Hamida，Iqbal Amna. Detection & recognition of veiled and unveiled human face on the basis of eyes using transfer learning.[J]. Multimedia tools and applications，2022

[5] 李昆仑，张炘.级联SVM和分类器融合的人脸性别识别方法[J].计算机工程与应用，2017，53（8）：154-158

[6] Shuzhe Wu， Meina Kan， Zhenliang He，et al. Funnel-structured cascade for multi-view face detection with alignment-awareness[J]. Neurocomputing，2017，221

[7] 兰胜坤.基于AdaBoost算法的人脸检测实现[J]. 电脑与信息技术，2021，29（2）：16-19

[8] Fu Y G， Huang H Y， Guan Y， et al. EBRB cascade classifierfor imbalanced data via rule weight updating[J]. Knowledge-Based Systems，2021，223：107010

[9] Hassen O A， Abu N A， Abidin Z Z， et al. A new descriptorfor smile classification based on cascade classifier in unconstrained scenarios[J]. Symmetry，2021，13（5）：805

[10] Mohamed Soha Abd ElMoamen，Mohamed MarghanyHassan，Farghally Mohammed F.. A New Cascade-Correlation Growing Deep Learning Neural Network Algorithm[J]. Algorithms，2021，14（5）

[11] Chia-Chi Wu，Yen-Liang Chen，Kwei Tang. Cost-sensitive decision tree with multiple resource constraints[J]. Applied Intelligence，2019，49（10）

[12] 金相宏，李琳，钟珞.基于主题模型和情感分析的垃圾评论识别方法研究[J].计算机科学，2017，44（10）：254-258