武森等：基于聚类欠采样的集成不均衡数据分类算法 ·1245· 重采样方法从数据层面入手，将少数类数据变多 样本数据的错误率对总体错误率贡献不同. 或将多数类数据变少，从而使原有的数据集达到均衡 1ECUA概念定义及算法过程 状态.重采样方法主要分为过采样方法和欠采样方 法.最简单的过采样方法是随机过采样.但是这种方 基于聚类欠采样的集成不均衡数据分类算法 法容易使分类器对同一个数据的训练太过强化，从而 (ECUA)涉及的相关概念定义及具体的算法过程说明 使规则对这些数据产生过拟合现象.为了解决这个问 如下. 题，很多研究者都提出了其他的过采样方法，比如基于 1.1概念定义 人工合成少数类过采样技术(synthetic minority over- 概念1（分类数据样本）：约定由一组属性值和一 sampling technique,SMOTE)[)、基于主动学习的 个类标号共同描述的数据对象为分类数据样本，表示 SMOTE过采样算法[o)、引入遗传算子的改进算法[]和 为x=(x1,d2,…,xm,r).其中(x1,x2,…,xm)为数据样 基于分形自相似性理论的SMOTE改进算法[s].与过 本的属性值，下标最大值m表示属性值的个数.在二 采样方法类似，最简单的欠采样方法是随机欠采样. 0,如果样本为正样本，本文讨论的 随机欠采样首先随机的选择一部分多数类样本并将其 分类问题中，一，如果样本为负样本 删除，从而形成新的训练集，使训练集中的数据达到均 分类问题均为二分类问题，即只有两种取值，且约定 衡状态.但是这种方法容易删除一些有代表性的多数 少数类数据样本均为正类样本 类样本数据，从而使分类器不能学习到完整的分类规 概念2（分类数据集）：约定当一组数据集中每个 则.为了克服这一缺点，许多研究者都提出了其他的 数据样本均为分类数据样本，这种数据集为分类数据 欠采样方法.比如说EasyEnsemble算法和BalanceCas- 集，表示为D={x,}1,其中i=1,2,…,N,标记分 cade算法I)、基于KNN算法的KNN欠采样方法： 类数据集中N个数据样本 Near Miss--l、NearMiss-2、NearMiss--3和“最远距离” 概念3（均衡数据集、不均衡数据集）：给定一个数 法[]、单边选择方法[等.其中，有学者提出利用聚 据集D={x,}其中D,={x,0}为类标号均为 类的方法进行欠采样].由于聚类方法可以利用数 0的分类数据子集，D2={x,1,为类标号均为1的 据样本的空间结构信息寻找数据样本的最优划分，因 分类数据子集，其中，N和N2分别是数据集D,和D2 此本文也采用基于聚类的欠采样方法来对训练数据集 分类数据子集的总数，且N,+N2=N.当且仅当数据 中多数类样本进行选择， 集D满足N/N≈N,/N时，该数据集为均衡数据集；否 从算法角度对不均衡数据分类问题进行改进主要 则为不均衡数据集 有五种方法，分别是改变概率密度、单类学习分类、代 概念4（弱分类器）：分类正确率仅比随机猜测略 价敏感学习、核方法和集成学习.其中集成学习模型 好的分类器，其分类正确率略高于50%. 始于80年代提出的弱可学习和强可学习概念，集成学 1.2算法过程 习与其他技术相结合，能够提高分类器的性能.目前， ECUA算法的主要过程有两个：使用基于聚类的 最常用的集成学习算法是AdaBoost算法.国际机器学 欠采样算法，得到均衡数据集；在得到均衡的数据集 习界的权威Dietterich将集成学习列为机器学习四大 后，用AdaBoost集成算法对新的数据集进行分类 研究方向之首]，其能够有效地提高分类器的泛化能 训练 力和预测精度 1.2.1基于聚类的欠采样过程 基于上述情况，本文在原有的基于聚类的欠采样 相比于随机欠采样等算法，基于聚类的欠采样能 方法和集成学习方法的基础上，将两种针对不均衡数 够减少欠采样过程中的盲目性，从而在减少多数类数 据分类的改进方法融合，提出基于聚类的欠采样集成 据数量的同时也能够尽可能保留多数类数据样本的信 不均衡数据分类算法(imbalanced data ensemble classi- 息.下面是具体的欠采样过程 fication based on cluster-based under-sampling algorithm, 输入：不均衡数据集D ECUA),提高不均衡数据的分类性能.该算法针对不 初始化D'=☑，D1=0,k=0 均衡数据集，用聚类方法对数据集进行欠采样处理，从 foreach x'∈D 而使多数类数据和少数类数据的数量达到均衡.然后 if r=0 以聚类后的类中心代表原多数类样本数据同少数类数 D'=D'Ux 据一起构成新的数据集，再利用AdaBoost算法分别基 else 于单层决策树算法和KNN算法进行集成的分类器训 D=DUx 练.然后在上述算法中的集成学习过程引入权重，对 k=card(D') 错误率的计算进行调整，使少数类样本数据和多数类 D'=Cluster(k,D)武 森等: 基于聚类欠采样的集成不均衡数据分类算法 重采样方法从数据层面入手,将少数类数据变多 或将多数类数据变少,从而使原有的数据集达到均衡 状态. 重采样方法主要分为过采样方法和欠采样方 法. 最简单的过采样方法是随机过采样. 但是这种方 法容易使分类器对同一个数据的训练太过强化,从而 使规则对这些数据产生过拟合现象. 为了解决这个问 题,很多研究者都提出了其他的过采样方法,比如基于 人工合成少数类过采样技术( synthetic minority over鄄 sampling technique, SMOTE ) [5] 、 基 于 主 动 学 习 的 SMOTE 过采样算法[6] 、引入遗传算子的改进算法[7] 和 基于分形自相似性理论的 SMOTE 改进算法[8] . 与过 采样方法类似,最简单的欠采样方法是随机欠采样. 随机欠采样首先随机的选择一部分多数类样本并将其 删除,从而形成新的训练集,使训练集中的数据达到均 衡状态. 但是这种方法容易删除一些有代表性的多数 类样本数据,从而使分类器不能学习到完整的分类规 则. 为了克服这一缺点,许多研究者都提出了其他的 欠采样方法. 比如说 EasyEnsemble 算法和 BalanceCas鄄 cade 算 法[9] 、 基 于 KNN 算 法 的 KNN 欠 采 样 方 法: NearMiss鄄鄄1、NearMiss鄄鄄 2、NearMiss鄄鄄 3 和 “ 最 远 距 离冶 法[10] 、单边选择方法[11] 等. 其中,有学者提出利用聚 类的方法进行欠采样[12] . 由于聚类方法可以利用数 据样本的空间结构信息寻找数据样本的最优划分,因 此本文也采用基于聚类的欠采样方法来对训练数据集 中多数类样本进行选择. 从算法角度对不均衡数据分类问题进行改进主要 有五种方法,分别是改变概率密度、单类学习分类、代 价敏感学习、核方法和集成学习. 其中集成学习模型 始于 80 年代提出的弱可学习和强可学习概念,集成学 习与其他技术相结合,能够提高分类器的性能. 目前, 最常用的集成学习算法是 AdaBoost 算法. 国际机器学 习界的权威 Dietterich 将集成学习列为机器学习四大 研究方向之首[13] ,其能够有效地提高分类器的泛化能 力和预测精度. 基于上述情况,本文在原有的基于聚类的欠采样 方法和集成学习方法的基础上,将两种针对不均衡数 据分类的改进方法融合,提出基于聚类的欠采样集成 不均衡数据分类算法( imbalanced data ensemble classi鄄 fication based on cluster鄄based under鄄sampling algorithm, ECUA),提高不均衡数据的分类性能. 该算法针对不 均衡数据集,用聚类方法对数据集进行欠采样处理,从 而使多数类数据和少数类数据的数量达到均衡. 然后 以聚类后的类中心代表原多数类样本数据同少数类数 据一起构成新的数据集,再利用 AdaBoost 算法分别基 于单层决策树算法和 KNN 算法进行集成的分类器训 练. 然后在上述算法中的集成学习过程引入权重,对 错误率的计算进行调整,使少数类样本数据和多数类 样本数据的错误率对总体错误率贡献不同. 1 ECUA 概念定义及算法过程 基于聚类欠采样的集成不均衡数据分类算法 (ECUA)涉及的相关概念定义及具体的算法过程说明 如下. 1郾 1 概念定义 概念 1(分类数据样本):约定由一组属性值和一 个类标号共同描述的数据对象为分类数据样本,表示 为 x = (x1 ,x2 ,…,xm ,r). 其中(x1 ,x2 ,…,xm )为数据样 本的属性值,下标最大值 m 表示属性值的个数. 在二 分类问题中,r = 0, 如果样本为正样本, {1, 如果样本为负样本. 本文讨论的 分类问题均为二分类问题,即 r 只有两种取值,且约定 少数类数据样本均为正类样本. 概念 2(分类数据集):约定当一组数据集中每个 数据样本均为分类数据样本,这种数据集为分类数据 集,表示为 D = { x i ,r i } N i = 1 ,其中 i = 1,2,…,N,标记分 类数据集中 N 个数据样本. 概念 3(均衡数据集、不均衡数据集):给定一个数 据集 D = {x i ,r i } N i = 1 . 其中 D1 = {x i ,0} N1 i = 1为类标号均为 0 的分类数据子集,D2 = { x i ,1} N2 i = 1为类标号均为 1 的 分类数据子集,其中,N1 和 N2 分别是数据集 D1 和 D2 分类数据子集的总数,且 N1 + N2 = N. 当且仅当数据 集 D 满足 N1 / N抑N2 / N 时,该数据集为均衡数据集;否 则为不均衡数据集. 概念 4(弱分类器):分类正确率仅比随机猜测略 好的分类器,其分类正确率略高于 50% . 1郾 2 算法过程 ECUA 算法的主要过程有两个:使用基于聚类的 欠采样算法,得到均衡数据集;在得到均衡的数据集 后,用 AdaBoost 集 成 算 法 对 新 的 数 据 集 进 行 分 类 训练. 1郾 2郾 1 基于聚类的欠采样过程 相比于随机欠采样等算法,基于聚类的欠采样能 够减少欠采样过程中的盲目性,从而在减少多数类数 据数量的同时也能够尽可能保留多数类数据样本的信 息. 下面是具体的欠采样过程. 输入:不均衡数据集 D 初始化 D忆 = 芰,D1 = 芰,k = 0 foreach x i沂D if r i = 0 D忆 = D忆胰{x i } else D1 = D1胰{x i } k = card(D忆) D忆1 = Cluster(k,D1 ) ·1245·