3.4 优化采样技术
通过3.3节的介绍，我们了解到：人工采样技术充分利用了训练集中样本的局部先验分布信息，能或多或少地克服随机采样技术的缺点，提升分类的性能。是不是只要采用这些算法，便足以保证采样的质量了呢？答案显然是否定的。实际上，上述各种算法均存在各自的缺点，每种算法对样本分布都有一定的选择性，远未达到普适的目的。为此，近几年，一些更为高级的采样算法被陆续开发出来，它们往往具有更强的自适应性、普适性与泛化能力。这些算法利用了样本的全局概率密度信息[14],[15]、集成学习技术[16-21]或随机优化技术[22-24]。有关结合样本采样的集成学习技术将在本书第6章做详细介绍，而关于利用全局概率密度信息的样本采样技术，鉴于本书篇幅有限，在此不做讨论，有兴趣的读者可参考相关文献。下面将着重介绍一种基于随机优化技术的采样算法，即基于蚁群优化的降采样算法（ACOSampling）算法。
众所周知，蚁群算法是Colorni等人[25]所提出的一种重要的群集智能算法，其主要模拟蚁群的觅食行为。近年来，蚁群算法已被广泛用于解决各类优化问题，包括旅行商（travelling saleman problem, TSP）问题[26]、参数优化问题[27]、蛋白质折叠预测问题[28]等。2013年，Yu等人[24]借鉴蚁群优化算法的思想提出了一种自适应的降采样算法，并将之命名为ACOSampling算法。
图3-9给出了在ACOSampling算法中，利用蚁群优化搜索算法进行样本选择过程的图示。如图3-9所示，在ACOSampling算法中，样本选择的过程可被看作是蚂蚁觅食的过程。在巢穴（nest）与食物（food）之间，按顺序排列着一个个的中转站点，每个站点对应于一个多数类样本。在蚂蚁从巢穴出发并移向食物源的过程中，蚂蚁要逐一通过每个站点，任一相邻站点间有两条路径相连，分别为路径0与路径1，其中前者表示对应样本需被移除，而后者则代表对应样本将被保留。最终，当蚂蚁到达食物源时，那些被保留的多数类样本将与所有少数类样本一起构成对应训练集。例如，一个二进制字符串{1,0,1,0,0,1}代表第1、第3与第6个多数类样本被保留。接下来，则以新生成的训练集在验证集上的适应度对其质量进行评价。蚂蚁彼此之间互相协作，并利用每条路径上残存的信息素浓度来搜索最优路径。
图3-9 基于蚁群优化搜索算法的多数类样本选择过程示意图
在上述蚁群算法中，蚂蚁们可同步搜索从巢穴到食物源间的路径。对于路径的选择则依据各路径上的信息素浓度而定。某条路径被选择的概率可通过下式进行计算：
其中，i代表第i个中转站点，即原始训练集中的第i个多数类样本；j 代表路径，其可赋值为0或1，指代对应样本是否已被保留；τij则代表第i个站点在第j条路径上的信息素浓度；而pij和k分别代表在第i个站点上选择第j 条路径的概率及路径j 的可能取值（0或1）。当一只蚂蚁到达食物源，可使用适应度函数对对应的样本子集进行评价。此外，适应度函数同步考虑了三种性能评价测度，其具体可由下式计算得到：
显然，适应度函数fitness由以下三种性能评价测度加权构成：F-measure, G-mean和AUC。三个权重因子的比例可以任意设置，用以指代对应性能测度的重要性，通常可将上述三个权重因子均设为1/3。蚁群算法每迭代一次，所有路径上的信息素浓度也将做相应更新，更新公式为
其中，t表示迭代轮次；ρ为蒸发因子，指代每条路径上信息素减少的比例；Δτij表示在一定比例较优路径上信息素的增加量。在ACOSampling算法中，每轮迭代后只增加最好的10%路径上的信息素，并将这些路径存储于一个集合E中。Δτij可由下式计算得到：
其中，ant_n表示蚁群的规模，即蚂蚁的数量。当一轮搜索完成后，某些路径上信息素浓度加强，而另一些路径的信息素浓度则会减弱，从而保证那些较优的路径在下一轮迭代时将有更高的概率被选择。当蚁群算法收敛时，所有蚂蚁将会倾向于选择相同的路径，并最终返回最优解。
为防止蚁群出现早熟的现象，ACOSampling算法也设定了各条路径上信息素浓度的上下界phmax及phmin，即当信息素浓度在更新后，超出了所设界限，则以对应界限浓度值来取代。基于蚁群优化思想的降采样算法的具体流程如下：
算法3-9：基于蚁群优化思想的降采样算法
输入：训练集S中多数类样本数N-, S中少数类样本数N+，验证集V，分类算法C，蚁群规模ant_n，蚁群迭代轮数ITA，蒸发因子dispose，每条路径初始信息素浓度ph_initial，信息素浓度的上下界phmax及phmin。
输出：降采样后的训练集S′。
算法步骤：
1.For i=1:N-
For j=0:1
为第i个多数类样本的第j 条路径设置初始信息素浓度ph_initial；
End
End
2．设置全局最优解OPS=0；
3.For i=1:ITA
For j=1:ant_n
3.1采用式（3-4）计算得出训练子集SSij；
3.2在训练子集SSij上利用分类算法C训练得到分类器C ij；
3.3在验证集V 上，采用式（3-5）计算得出分类器Cij所对应的适应度；
End
3.4找到第i轮迭代中的最优解OPSi；
3.5 if（OPS＜OPSi）
OPS=OPSi；
End
3.6采用式（3-6）及式（3-7）更新各条路径上的信息素浓度；
End
4．得到降采样后的训练集S′, S′对应于全局最优解OPS的样本子集。
利用上述算法，可在原始训练集中抽取一个较优的子集并作为最终的训练样本集使用，以训练分类器并对未来测试样本的类属进行识别。但该算法是有缺陷的，即在优化过程中，需将原始训练集划分为互不相交的两部分：训练集和验证集，这就会导致如下两个严重的问题：信息缺失以及过适应，从而影响分类器的最终性能。当原始训练集为小样本时，上述问题将体现得尤为突出。为解决该问题，ACOSampling算法采用了一种迭代划分原始训练集的策略，其流程详见图3-10。
图3-10 ACOSampling算法图示
如图3-10所示，ACOSampling算法采用3折交叉验证来评价分类的性能，即每次抽取原始训练集中的2/3样本做训练，而以另外1/3的样本做测试。在实际应用中，也可采用5折或10折交叉验证的方法来进行替换。同时，为了公正地评价每个多数类样本所含信息量的大小，并有效避免最终训练结果过适应，可对原始训练集随机并重复地划分100次。很明显，在这100次划分中，每个样本有均等的机会被选入训练集。接下来，在每一次划分中运行基于蚁群优化思想的降采样算法并获取最优的降采样集，从而给出多数类样本的频率排序表（以图3-11为例，样本出现的频次越高，则可认为其所含有的分类信息越多）。然后，通过排序的方法选出那些高频的多数类样本，并与全部少数类样本混合以构成一个平衡的训练样本集。最后，可利用该样本集来训练分类器并通过测试样本对其性能进行评价。
图3-11 多数类样本的频率排序表
ACOSampling算法的具体流程如下。
算法3-10:ACOSampling算法
输入：原始训练集S中多数类样本数N-, S中少数类样本数N+，分类算法C，蚁群规模ant_n，蚁群迭代轮数ITA，蒸发因子dispose，每条路径初始信息素浓度ph_initial，信息素浓度的上下界phmax及phmin，训练集划分次数ITP，采样率SR。
输出：降采样后的训练集S′。
算法步骤：
1.For i=1:ITP
1.1将原始训练集S随机划分为均等的两份，一份作为训练子集SS，一份为验证子集V；
1.2调用算法3～算法9以获取第i个降采样集Si；
1.3记录Si中多数类样本的索引号，并将其记录入索引表RECi中；
End
2．统计索引表REC中各多数类样本的出现频率，并根据频率对其进行降序排列；
3．选取排序前N+×SR个多数类样本，与全部少数类样本一起共同组成降采样后的训练集S′。
显然，ACOSampling算法最为突出的优点即是无须探查训练样本的真实分布，而是仅通过分类的反馈结果来确定各多数类样本的信息含量，从而可有效避免在传统降采样算法中所出现的重要分类信息缺失问题。严格来讲，ACOSampling算法是一种具有自适应能力的采样算法。但由于该算法采用了迭代寻优的模式，故具有较高的时间复杂度。