集成学习近年来得到广泛研究^[1-5]. 为了构建一个有效的集成分类器, 研究者提出了不同的方法来训练一组好而不同的个体分类器. 现有的集成方法大致可分为两类, 即基于单模态扰乱的方法和基于多模态扰乱的方法, 其中, 第1类方法又包括基于重采样的方法 (如Bagging、Boosting等)^{[6, 7]}、基于特征子空间的方法^[8-10]等. 与第1类方法不同, 基于多模态扰乱的方法^[5,11,12]在训练个体分类器的过程中使用了多种扰乱技术, 其动机是: 很多时候单一类型的扰乱可能不足以产生多样性大的个体分类器. 早期的集成方法通常对所有的个体分类器进行集成, 然而, 这种做法并不一定能够保证个体分类器之间的多样性. 对此, 研究者们进一步提出了不同的集成剪枝方法^[4,13,14]. 集成剪枝的主要目的是通过删除一些个体分类器来提升个体分类器之间的多样性(即只利用一部分多样性大的个体分类器来构建集成分类器). 研究表明, 集成剪枝能够有效提升集成学习的性能.

为了增加个体分类器的多样性, 多模态扰乱策略被广泛应用于集成学习, 并形成了不同的基于多模态扰乱的集成方法. 例如, Lattine等提出一种用于集成C4.5决策树的多模态扰乱策略^[15], 该策略将Bagging和随机子空间(RSM)方法结合起来. 与基于单模态扰乱的方法相比, Lattine等的方法具有更好的性能. Altinçay提出一种基于多模态扰乱的集成方法, 该方法使用遗传算法(GA)来选择特征子集和最优重采样^[16]. 实验结果表明: Altinçay的方法要优于基于单模态扰乱的RSM方法. Zhou等^[11]提出一种集成KNN分类器的多模态集成算法, 该算法对训练数据、特征空间和学习参数同时进行扰乱. 与每一种基于单模态扰乱的方法相比, Zhou等的方法都可以取得更好的性能.

本文从粗糙集^[17]中的属性约简技术出发, 提出了一种新的可同时扰乱属性空间和训练集的集成剪枝算法EPA_AO. EPA_AO的主要思路如下: (1)假设T和V分别表示训练集和验证集, 我们通过近似约简技术从T的属性集中产生M个近似约简AR₁, …, AR_M. (2)针对任意AR_i (1≤i≤M), 对T中的样本进行H次bootstrap采样, 获得H个采样集S₁, …, S_H并从中选择关于AR_i的最优采样集O_i. 具体而言, 对于任意采样集S_j, 我们利用AR_i来对S_j 进行约简, 再利用分类算法在S_j 上训练个体分类器C_j (1≤j≤H). 然后, 利用V来分别评价个体分类器C₁, …, C_H的性能, 并将性能最好的个体分类器所对应的采样集作为AR_i的最优采样集O_i. (3)利用AR_i以及AR_i所对应的最优采样集O_i来训练个体分类器IC_i (1≤i≤M). (4)基于多数投票的策略, 将个体分类器IC₁, …, IC_M集成在一起, 从而得到集成分类器.

本文的工作主要包括3个部分: 首先, 在粗糙集中引入近似约简的概念, 并提出一种计算近似约简的算法; 其次, 设计出一种基于近似约简与最优采样的多模态扰乱策略: 通过近似约简来扰乱属性空间, 并通过最优采样技术来扰乱训练集; 最后, 基于上述多模态扰乱策略, 提出一种集成剪枝算法. 该算法通过计算近似约简及其对应的最优采样集, 可以在保证个体分类器性能的前提下, 有效提升个体分类器的多样性. 证据KNN (K-近邻) 分类算法^[18]简单、有效, 并且在许多领域都得到了广泛应用. 相对于传统的KNN算法, 证据KNN算法通常具有更好的性能. 因此, 在实验中我们使用证据KNN算法来训练个体分类器. 我们利用多个UCI数据集来比较EPA_AO与现有的集成学习算法的性能. 实验结果表明, EPA_AO具有更好的分类性能.

1 预备知识

在粗糙集理论中, 信息系统是一个四元组IS = (U, A, V, f ), 其中, U是一个非空、有限的对象集; A是一个非空、有限的属性集; V=∪_a∈AV_a是所有属性论域的并集(V_a表示属性a的值域); f: U×A→V是一个信息函数, 使得对任意a∈A, u∈U, f(u, a)∈V_a ^{[17, 19]}. 如果进一步把属性集A划分为条件属性集C和决策属性集D, 则这种特殊的信息系统被称为决策表DT = (U, C, D, V, f ).

定义1. 不可分辨关系. 给定决策表DT= (U, C, D, V, f ), 对任意 $B \subseteq C \cup D$ , 我们将由B所确定的不可分辨关系 IND(B) 定义为^{[17, 19]}:

$ \begin{gathered} IND(B) = \{ (u_1, u_2) \in U \times U:\forall a \in B(f(u_1, a) = f(u_2, a))\} \end{gathered} $

(1)

不可分辨关系IND(B)实际上是U上的一个等价关系, 它将U划分为多个不相交的等价类. 令U/IND(B)表示IND(B)所对应的所有等价类的簇, 我们称U/IND(B)为由IND(B)所确定的论域U的划分. 对任意u∈U, 令[u]_B表示U/IND(B)中包含对象u的等价类^{[17, 19]}.

定义2. 正区域. 给定决策表DT= (U, C, D, V, f), 对任意 $B \subseteq C $ , 我们将D的B-正区域POS_B(D)定义为^{[17, 19]}:

$ \begin{gathered} POS_B(D) = \cup \{ Y|Y \subseteq X, X \in U/IND(D), Y \in U/IND(B)\} \end{gathered} $

(2)

定义3. 核属性. 给定决策表DT= (U, C, D, V, f ), 对任意b∈C, 如果POS_C−{b}(D)≠POS_C (D), 则我们称b是C中相对于D的一个核属性^{[17, 19]}.

给定决策表DT= (U, C, D, V, f ), C中所有核属性的集合被称为C相对于D的核.

定义4. 约简. 给出决策表DT= (U, C, D, V, f ), 对任意 $B \subseteq C $ , 如果POS_B (D) = POS_C (D)并且对任意b∈B,POS_B−{b}(D)≠POS_B (D), 则我们称B为C相对于D的一个约简^{[17, 19]}.

接下来, 我们分析证据KNN的原理. 证据KNN是由Denoeux所提出的一种分类算法^[18], 它将训练样本在输入空间不同部分的分布信息融入到传统的KNN中, 其主要思想是: 从所有训练样本中计算出测试样本t的k个最近邻, 将每个最近邻都作为支持t所属类的证据, 然后结合所有最近邻的基本概率赋值来得到t的类别^[18].

令 L = {l₁, …, l_h}表示由h个类标签所组成的标签集, T = {(u₁, C(u₁)), …, (u_g, C(u_g))}表示由g个样本所组成的训练样本集, T中每个样本都用一个二元组(u_j, C(u_j))来表示, 其中, u_j表示第j个样本, C(u_j)∈L表示u_j所属的类别标签, 1≤j ≤ g. 令N_w = {(v₁, C(v₁)), …, (v_k, C(v_k))} $\subset$ T表示T中距离当前的测试样本t_w最近的k个训练样本(即t_w的k-最近邻), N_w中每个元素也用一个二元组(v_j, C(v_j))来表示, 其中, v_j表示t_w的第j个最近邻, C(v_j)∈L表示v_j所属的类别标签, 1≤j ≤ k. 对于t_w的任意一个最近邻v_j (1≤j ≤ k), 如果C(v_j) = l_p∈L, 则我们将 (v_j, l_p) 看作是支持t_w被分类为l_p的一个独立证据.

每一个独立证据 (v_j, l_p) 的可信任度都由一个基本概率赋值函数来度量, 即该基本概率赋值函数的值越大, 则证据 (v_j, l_p) 的可信任度越高. 具体而言, (v_j, l_p)中所包含的分布信息将采用以下的基本概率赋值函数来刻画: E^{w, j}({l_p}) = β, E^{w, j}(L)= 1−β. 在上述基本概率赋值函数中, β∈[0, 1], β的具体取值由v_j与t_w的距离d(v_j, t_w)所决定(通常情况下, 距离越大, 则β越小). 很多学者通过定义相似函数来描述 β 与距离d(v_j, t_w)的关系, 例如Denoeux将相似函数定义成^[18]: $\;\beta = \beta _0 \times {{\rm{e}}^{ - \gamma s \times d{{(vj, tw)}^2}}}$ . 在上面的相似函数中, 0 < β₀ <1是一个预先指定的参数, 而 γ_s > 0则是另一个预先指定的参数. 对任意 v_i, v_j∈N_w, 如果i≠j, 则E^{w, i}与E^{w, j}是相互独立的, 这是因为这两个基本概率赋值函数是由不同的训练样本所生成的. 利用证据理论的组合规则, 将E^{w, 1}, …, E^{w, k}都组合起来, 从而获得 ${E^w} = \oplus_{vi \in Nw}{E^{w, i}}$ . 在获得E^w之后, 就可以利用其来计算t_w相对于各个类标签的置信度函数, 从而实现对测试样本t_w的分类.

2 近似约简与EPA_AO算法

在粗糙集中, 给定决策表DT= (U, C, D, V, f ), 一个约简R是条件属性集C的最小子集, 它能充分识别具有不同类别的对象. 理论上已经证明, 基于约简R所训练的分类器与基于C所训练的分类器具有相等的分类能力^[20]. 一些学者提出在C的每一个约简上训练一个个体分类器, 并利用这些个体分类器来构建集成分类器. 由于C的约简与C具有相同的区分能力, 因此, 基于这些约简所构建的个体分类器不仅可以保证个体分类器的分类能力, 还可以保证每个个体分类器之间具有较好的差异性, 降低个体分类器训练的复杂度, 从而高效率地训练出性能优异的分类器. 也就是说, 我们可以利用粗糙集的属性约简技术来扰乱属性空间. 然而, 利用属性约简技术对属性空间进行扰乱时将面临以下问题: 约简个数过少. 很多时候, 在决策表DT中, 只存在少量的C的约简. 如果没有足够多的约简, 那么我们就不能训练出足够多的个体分类器. 特别是, 如果只存在一个约简, 那么我们就只能获得一个个体分类器. 为解决上述问题, 本文提出近似约简的概念, 通过放宽对约简的严格要求(即C的约简必须与C具有完全相同的区分能力), 可以获得足够多的C的近似约简.下面, 我们首先在粗糙集中引入近似约简的概念, 利用近似约简我们可以构建足够多的个体分类器; 其次, 我们将近似约简与最优采样技术相结合, 从而设计出一种新的多模态扰乱策略; 最后, 基于上述多模态扰乱策略提出集成剪枝算法EPA_AO.

2.1 近似约简

近似约简是对粗糙集中经典的约简概念的推广. 前面提到给定决策表DT= (U, C, D, V, f ), 如果R是C的约简, 则R与C必须具有完全相同的区分能力, 即|POS_R(D)| = |POS_C(D)|. 根据上述严格的要求, 我们可以得到关于C的约简, 但是往往约简的数量不够多. 对此, 有必要对上述要求进行适当地放宽, 即要求R的区分能力不需要完全等于C, 而是在一定程度上近似等于C. 基于上述考虑, 我们可以提出近似约简的概念. 与约简不同, 近似约简的区分能力可以小于C.

定义5. 近似约简. 给定决策表DT = (U, C, D, V, f ), 对任意 $AR \subseteq C $ , 如果|POS_C (D)| ≥ |POS_AR (D)| ≥ δ×|POS_C (D)|, 则AR被称为C相对于D的 δ-近似约简, 其中, δ∈(0, 1]是一个给定的阈值.

由上述定义可以看出, 近似约简AR的区分能力不需要完全等于C(即|POS_C (D)| ≥ |POS_AR (D)|), 而是近似等于C(即 |POS_AR (D)| ≥ δ×|POS_C (D)|), 且近似的程度由阈值δ来控制. δ的值越大, 则AR的区分能力越接近于C, 特别是当 δ=1时, 近似约简AR就变成经典的约简. 接下来, 我们给出算法1, 用于计算C中所有的近似约简.

算法1. 近似约简的计算

输入: 决策表DT= (U, C, D, V, f ), 其中, U={u₁, …, u_g}, C={a₁, …, a_n}; 参数S与MI, 其中, S是预先给定的近似约简的数量, MI是最大迭代次数.

输出: 近似约简集SAR.

初始化: Core ← Ø, SAR ← Ø, 其中, Core表示所有核属性的集合.

1) 采用计数排序的方法来计算D的C-正区域POS_C (D)^[19].

2) 对任意 1≤j ≤ n, 循环执行下列语句:

3)　采用计数排序的方法来计算POS_C-aj;

4)　　如果POS_C-aj(D) ≠ POS_C (D), 则Core ← Core∪{a_j}.

5) Remain ← C – Core.

6) 如果Remain=Ø, 则SAR ← SAR∪C, 并跳转到步骤17).

7) 如果Remain≠Ø, 则对任意 1≤i ≤ MI, 循环执行下列语句:

8)　　Temp ← Core;

9)　　从Remain中随机选择一个属性a;

10)　　Temp←Temp∪{a}, Remain ← Remain – {a};

11)　　对任意属性b∈Remain, 计算b相对于Temp和D的重要性Sig (b, Temp, D), 其中, Sig (b, Temp, D) = (|POS_Temp∪{b}(D)|–|POS_Temp(D)|) / |U|;

12)　　选择Remain中重要性最大的属性b_max;

13)　　Temp ← Temp∪{b_max}, Remain ← Remain – {b_max};

14)　　重复执行步骤11)–13), 直到满足近似约简的条件, 即|POS_Temp(D) ≥ δ×|POS_C (D)|;

15)　　如果Temp $\notin $ SAR, 则SAR ← SAR∪{Temp};

16)　　如果 |SAR| = S, 则结束当前循环.

17) 输出SAR.

对任意B $ \subseteq $ C, 计算D的B正区域POS_B (D)的时间复杂度通常为O(|U|²). 在算法1中, 我们通过计数排序的方法^[21]来计算POS_B(D), 时间复杂度仅为O(|B|×|U|). 在最坏的情况下, 算法1的时间复杂度为O(MI×|C|³×|U|), 空间复杂度为O(|U|+|C|).

2.2 算法EPA_AO

由于只采用近似约简来扰乱属性空间可能还不足以保证个体分类器的多样性, 因此, 本文将近似约简与最优采样技术结合在一起来实现一种多模态的扰乱, 即不仅对属性空间进行扰乱, 而且还利用最优采样技术来扰乱训练集. 在上述多模态扰乱策略的基础上, 我们提出了集成剪枝算法EPA_AO. 在EPA_AO中, 对于每个近似约简AR_i (1≤ i ≤ M ), 我们首先对训练集进行多次bootstrap采样, 然后选择关于AR_i 的最优采样集O_i. 与其他采样集相比, 在O_i上训练的个体分类器具有最高的分类性能. 我们最终利用近似约简AR_i以及AR_i所对应的最优采样集O_i来训练个体分类器IC_i (1≤ i ≤ M ), 并对IC₁, …, IC_M进行集成.

算法2. EPA_AO算法

输入: 训练集TS = (U₁, C₁, D₁, V₁, f₁); 验证集VS = (U₂, C₂, D₂, V₂, f₂); 参数H, 其中, H表示为选择最优采样集而提前生成的bootstrap采样集的个数.

输出: 集成分类器EC.

1) 利用算法1计算出TS中的所有近似约简(令AR₁, …, AR_M 分别表示这些近似约简).

2) 对任意 1≤i ≤ M, 循环执行下列语句:

3)　　利用AR_i对TS进行约简, 并且令TS_reduced = (U₁^*, AR_i, D₁, V₁^*, f₁^*)为约简后的训练集.

4)　　利用AR_i对VS进行约简, 并且令VS_reduced = (U₂^*, AR_i, D₂, V₂^*, f₂^*)为约简后的验证集.

5)　　对任意 1≤j ≤ H, 循环执行下列语句:

6)　　　　对TS_reduced 中的U₁^*进行bootstrap采样, 生成采样集S_j;

7)　　　　利用给定的分类算法在采样集S_j上训练一个个体分类器C_j;

8)　　　　利用VS_reduced 来评价个体分类器C_j的性能.

9)　　从C₁, …, C_H中选取分类性能最好的个体分类器C_max以及C_max所对应的采样集S_max, 并且令O_i = S_max表示关于近似约简AR_i 的最优采样集, 其中, 1≤ C_max≤ H.

10)　　将C_max作为最终由近似约简AR_i 以及最优采样集O_i所训练的个体分类器IC_i.

11) 基于多数投票的策略, 将个体分类器IC₁, …, IC_M集成在一起, 从而得到集成分类器EC.

3 实验结果及分析

为了评价EPA_AO的有效性, 我们开展了相关实验. 实验采用9个来自于UCI机器学习库的数据集, 并使用证据KNN算法来生成个体分类器. 关于这9个数据集的具体信息见表1.

我们基于Java实现了EPA_AO. 在实验中, 对于表1中的任意数据集T, 我们首先使用等宽度算法对T中每一个连续型属性进行离散化处理, 其中, bins=5; 其次, 我们将T随机划分成一个训练集Train (占样本总数的50%)和一个测试集Test (剩下50%的样本); 然后, 由于我们要为EPA_AO提供一个单独的验证集VS来获得当前近似约简AR的最优采样集, 因此我们从Train中随机选择50%的样本来生成VS.

在运行证据KNN算法之前, 我们要对 β₀与 γ_s 这两个参数的取值进行设置. 在我们的实验中, β₀ 被设置为 0.95, 而 γ_s 则被设置为相应类别训练样本的平均距离的倒数^[12], 在经过多次取值实验后, 发现β₀为0.95时证据KNN算法训练出的个体分类器精度最好. 对于EPA_AO, 我们需要对S和MI这两个参数以及阈值δ的取值进行设置. 在我们的实验中, S 和MI分别被设置为10和25, 而δ则被设置为 0.9 (实验发现, S设为10时既能避免约简个数太少而影响集成分类器的分类性能, 也不会因约简太多而影响训练的效率; MI设为25时实验效果最佳; δ设为0.9时能够保证约简后的个体分类器的分类能力与约简前比较接近, 不会因为分类能力下降太多而影响集成分类器的整体性能).

下面, 我们首先比较EPA_AO与文献[12]中所采用的RSM方法的性能. 在文献[12]中, RSM也通过证据KNN算法来生成个体分类器. 证据KNN的性能依赖于k的值, 因此, 对于每个数据集, 我们为k赋予不同的取值(即k = 3、k = 5和k = 7), 从而得到不同k值下的实验结果.

表2给出了EPA_AO和RSM这两个算法在不同k值下的分类性能(为了避免偶然性, 我们将全部实验都重复执行10遍, 表2中所列出的实验结果都是这10次实验的平均值).

根据表2, 我们可以得出这样的结论: EPA_AO的分类准确率在大部分数据集上都比RSM更高. 具体而言, 如果将k设置为7, 则EPA_AO的准确率在所有数据集上均要优于RSM; 如果将k 设置为 5, 则EPA_AO的准确率在除了Vowel之外的其余8个数据集上均要优于RSM; 如果将 k 设置为 3, 则EPA_AO的准确率在其中5个数据集上要优于RSM, 而在另外4个数据集上 (即Ionosphere、Sonar、Vowel和WDBC)要低于RSM. 特别是, 如果我们统计多个k值下的平均准确率, 则可以发现EPA_AO的性能在总共7个数据集上 (除了Vowel和WDBC) 均要优于GAv1与GAv2. 由上述实验结果可知, 本文提出的EPA_AO算法其分类性能明显优于现有的集成学习算法.

接下来, 我们将比较EPA_AO与两种基于GA (遗传算法)的集成剪枝算法的性能. 这两种基于GA的集成剪枝算法是由Altinçay所提出^[12], 分别称为: GAv1(GA version 1)和GAv2 (GA version 2). 与本文所提出的EPA_AO类似, GAv1和GAv2也采用多模态扰乱策略来训练个体分类器.

表3给出了EPA_AO、GAv1与GAv2这3个算法的分类准确率(因为GAv1与GAv2能够自动选取最优的k值以得到最高的准确率^[12], 所以这里我们只给出了EPA_AO的最优结果, 即k = 7时的准确率. 此外, 我们还统计了EPA_AO在不同k值下的平均准确率).

根据表3, 我们可以得出这样的结论: EPA_AO的分类准确率在大部分数据集上都比GAv1与GAv2这两个算法更高. 具体而言, 如果将 k 设置为 7, 则EPA_AO的准确率在总共8个数据集上均要优于GAv1与GAv2, 只是在Vowel上表现差一些. 尤其是在以下4个数据集上: Credit-g、Liver、Pima与Vehicle, EPA_AO的分类准确率相对于GAv1与GAv2这两个算法有明显的提升 (提升了10%以上). 此外, 如果我们统计EPA_AO在多个k值下的平均准确率, 则可以发现EPA_AO的性能在总共 7 个数据集上(除了Vowel和WDBC) 均要优于GAv1 与GAv2. 由上述实验结果可知, 本文提出的EPA_AO算法其分类性能明显优于现有的集成学习算法.

4 总结

为了增加集成学习中个体分类器的多样性, 本文提出了近似约简的概念, 并由此设计出一种新的多模态扰乱策略. 该策略通过近似约简来扰乱属性空间, 并通过最优采样技术来扰乱训练集. 近似约简是对粗糙集中经典的约简概念的扩展, 它能够解决给定决策表中约简数量可能不足的问题. 在上述多模态扰乱策略的基础上, 本文提出了集成剪枝算法EPA_AO. 实验结果表明, EPA_AO算法的性能要优于现有的集成算法.

由于本文在Pawlak的经典粗糙集模型^[17]基础上提出了近似约简的概念, 而经典粗糙集模型更适合于处理离散型属性, 所以, EPA_AO需要通过某种离散化技术将所有的连续型属性转换为离散型属性. 然而, 属性离散化可能会导致信息的丢失问题. 因此, 在下一步工作中, 我们计划将EPA_AO扩展到邻域粗糙集^[22]或者模糊粗糙集^[23]等扩展的粗糙集模型中, 从而可以不经过离散化过程而直接处理连续型属性.