第1期 张本才，等：一种多样性和精度加权的数据流集成分类算法 ·181· MSE,=∑p0I-p (2) 器所构成集合的多样性值可以通过式（⑧）计算： div,=∑Q/IEl (8) 精度可以使用MSE和MSE,来表示，本文使 C∈E,#j 用式(3)来表示集成分类器中已有的基分类器的 2.2基于多样性和精度加权的集成算法 精度，即 1)基于多样性和精度加权的分类器权重计算 本文提出了一种新的分类器权重计算方式 Accij=MSE+6 (3) 以往的集成方法在计算基分类器或者新建立分类 式中6的存在是为了防止式(3)的分母为0。另 器的权重时通常只根据精度或者多样性一个标准 外，新建立的分类器的精度Accc根据式(4)来计算： 来计算，这难免具有片面性，所以为了同时考虑 1 Accc MSE,+6 (4) 一个分类器的精度和多样性，本文采用了一种线 2)集成分类器中的多样性度量 性加权方式来计算分类器权重，将在最新数据块 目前已有的理论和实验研究可以证明，由多 上分类器的精度以及该分类器与集成分类器之间 个分类器组合而成的集成分类器相对于单个分类 的多样性这两种度量分类器价值的标准以一种线 器来说泛化能力更强，并且由相互独立、互为补 性加权的方式融合成一个标准，以此作为衡量一 充且相对精确的分类器集成得到的集成分类器在 个分类器对于当前集成分类器价值大小的依据， 泛化性能上要优于性能最好的基分类器例。当发 并通过1个位于0~1的可调整的参数来控制精度 生概念漂移时，所有基分类器可能全都无法处理 和多样性各自在计算权重过程中的重要性。计算 这类新问题；而如果集成分类器中的基分类器是 权重有两个目的：1)使用权重来表示一个分类器 多样性的，那么总能找到一个最擅长处理这个新 在整个集成分类器的价值，用于集成分类器更 问题的基分类器，从而使集成分类器具有良好的 新；2)在预测阶段将每个基分类器的预测结果融 泛化性能。 合，权重高的分类器在预测时将起到更重要的作 本文采用的多样性度量方法为Q统计量，计 用。下面是具体的权重计算方式。 算两个分类器之间的Q统计量值的公式如式 当一个新的数据块到来时，使用此数据块构 (5)所示： 建一个新的分类器C',并根据式(4)计算C的精 N11N00 -NOi N10 度Accc,根据式(T)计算C的多样性divc'。C的 =NI N+NOI NIO (5) 权重根据式(9)来计算，即 式中：W表示分类器i分类结果为a、分类器j分 Wc aAccc+(1-a)divc. (9) 类结果为b的实例数量；1代表正确分类；0代表 式中a∈[0,1。 错误分类。比如，W表示分类器i和分类器j同 已有基分类器的权重也需要根据新来的数据 时分类正确的实例数量。 块调整，使用式(10)计算基分类器新的权重值 为了方便加权后的度量，所以需要将多样性 P即 转化为越大代表多样性越强，如式(6)所示： Wij=aAcci+(1-a)div (10) Q=0.5(1-Q) (6) 式中w,表示基分类器C,在数据块B,上的权重。 式中Q表示分类器C,与C,的Q统计量，用这个 2)基于价值度量的集成分类器更新策略 值表示二者的差异程度，由于Q的值域为[-1， 本文假定集成分类器的大小是固定的，即基 1],因此1-Q的值域为[0,2]，然后进行了归一 分类器的个数是固定的，因此在新数据块建立一 化，归一化这一步不是必需的，是否归一化对结 个新的分类器C'后，如果基分类器的数量已经达 果影响不大。 到了规定的数目，则需要将集成分类器中的其中 一个分类器C与一个集成分类器E的多样性 一个基分类器替换出，那么如何选择被替换的基 值为C与E中的每一个基分类器根据式(6)计算 分类器将至关重要。 得到的Q,的平均值。因此，新建立的分类器 本文采用的是一种基于价值度量的集成分类 C与集成分类器E之间的多样性值divc可以通过 器更新策略，将式(10)计算得到的权重，作为分 式(7计算： 类器C,当前的价值，当有新的分类器到来时，价 divc=∑g/l回 (7 值最低的基分类器将会被新建立的分类器替换掉。 i=C.CJEE 另外，之所以每次建立新分类器C后都将其 集成分类器中一个基分类器C,与其余分类 加入到集成分类器中，而不是先比较其是否比最MSEr = ∑ y p(y)(1− p(y))2 (2) 精度可以使用 MSEij 和 MSEr 来表示，本文使 用式 (3) 来表示集成分类器中已有的基分类器的 精度，即 Acci j = 1 MSEi j +δ (3) 式中 δ 的存在是为了防止式 (3) 的分母为 0。另 外，新建立的分类器的精度 AccC’根据式 (4) 来计算： AccC′ = 1 MSEr +δ (4) 2) 集成分类器中的多样性度量 目前已有的理论和实验研究可以证明，由多 个分类器组合而成的集成分类器相对于单个分类 器来说泛化能力更强，并且由相互独立、互为补 充且相对精确的分类器集成得到的集成分类器在 泛化性能上要优于性能最好的基分类器[9]。当发 生概念漂移时，所有基分类器可能全都无法处理 这类新问题；而如果集成分类器中的基分类器是 多样性的，那么总能找到一个最擅长处理这个新 问题的基分类器，从而使集成分类器具有良好的 泛化性能。 本文采用的多样性度量方法为 Q 统计量，计 算两个分类器之间的 Q 统计量值的公式如式 (5) 所示： Qi j = N 11N 00 −N 01N 10 N11N00 +N01N10 (5) 式中：N ab 表示分类器 i 分类结果为 a、分类器 j 分 类结果为 b 的实例数量；1 代表正确分类；0 代表 错误分类。比如，N 11 表示分类器 i 和分类器 j 同 时分类正确的实例数量。 为了方便加权后的度量，所以需要将多样性 转化为越大代表多样性越强，如式 (6) 所示： Q ∗ i j = 0.5(1− Qi j) (6) 式中 Qij 表示分类器 Ci 与 Cj 的 Q 统计量，用这个 值表示二者的差异程度，由于 Qij 的值域为[−1, 1]，因此 1 − Qij 的值域为[0, 2]，然后进行了归一 化，归一化这一步不是必需的，是否归一化对结 果影响不大。 一个分类器 C 与一个集成分类器 E 的多样性 值为 C 与 E 中的每一个基分类器根据式 (6) 计算 得到的 Qi j *的平均值。因此，新建立的分类器 C′与集成分类器 E 之间的多样性值 divC′可以通过 式 (7) 计算： divC′ = ∑ i=C′ , Cj∈E Q ∗ i j/ |E| (7) 集成分类器中一个基分类器 Ci 与其余分类 器所构成集合的多样性值可以通过式 (8) 计算： divi = ∑ Cj∈E,i,j Q ∗ i j/ |E| (8) 2.2 基于多样性和精度加权的集成算法 1) 基于多样性和精度加权的分类器权重计算 本文提出了一种新的分类器权重计算方式， 以往的集成方法在计算基分类器或者新建立分类 器的权重时通常只根据精度或者多样性一个标准 来计算，这难免具有片面性，所以为了同时考虑 一个分类器的精度和多样性，本文采用了一种线 性加权方式来计算分类器权重，将在最新数据块 上分类器的精度以及该分类器与集成分类器之间 的多样性这两种度量分类器价值的标准以一种线 性加权的方式融合成一个标准，以此作为衡量一 个分类器对于当前集成分类器价值大小的依据， 并通过 1 个位于 0~1 的可调整的参数来控制精度 和多样性各自在计算权重过程中的重要性。计算 权重有两个目的：1) 使用权重来表示一个分类器 在整个集成分类器的价值，用于集成分类器更 新；2) 在预测阶段将每个基分类器的预测结果融 合，权重高的分类器在预测时将起到更重要的作 用。下面是具体的权重计算方式。 当一个新的数据块到来时，使用此数据块构 建一个新的分类器 C′，并根据式 (4) 计算 C′的精 度 AccC′，根据式 (7) 计算 C′的多样性 divC′。C′的 权重 wC′根据式 (9) 来计算，即 wC′ = αAccC′ +(1−α)divC′ (9) 式中α ∈ [0,1]。 已有基分类器的权重也需要根据新来的数据 块调整，使用式 (10) 计算基分类器新的权重值 wij，即 wi j = αAcci j +(1−α)divi (10) 式中 wij 表示基分类器 Ci 在数据块 Bj 上的权重。 2) 基于价值度量的集成分类器更新策略 本文假定集成分类器的大小是固定的，即基 分类器的个数是固定的，因此在新数据块建立一 个新的分类器 C′后，如果基分类器的数量已经达 到了规定的数目，则需要将集成分类器中的其中 一个基分类器替换出，那么如何选择被替换的基 分类器将至关重要。 本文采用的是一种基于价值度量的集成分类 器更新策略，将式 (10) 计算得到的权重 wij 作为分 类器 Ci 当前的价值，当有新的分类器到来时，价 值最低的基分类器将会被新建立的分类器替换掉。 另外，之所以每次建立新分类器 C′后都将其 加入到集成分类器中，而不是先比较其是否比最 第 1 期 张本才，等：一种多样性和精度加权的数据流集成分类算法 ·181·