·1246· 工程科学学报，第39卷，第8期 D'=D'UD' 0.210 输出：均衡数据集D' 上述过程为基于聚类的欠采样过程，输入不均衡 数据集，得到均衡数据集.其中Cluster(k,D)算法选 用k-means算法.聚类过程中使用的距离公式为欧氏 距离。 在欠采样过程中，首先将数据集分为少数类数据 和多数类数据.少数类数据直接放入新的数据集中， 多数类数据需要经过聚类后，将各类的中心点放入新 0.05 10.38 21.088 31.795 的数据集.聚类方法选择k-means算法，因为要保证欠 属性一 采样后多数类数据与少数类数据的个数达到平衡，因 图2聚类后的数据分布 此设置多数类聚类的数目为少数类数据的个数.先随 Fig.2 Data distribution after clustering 机选择k个数据作为聚类中心，然后计算数据集中每 个点和各个聚类中心的欧氏距离，将数据样本分到距 器五，(x) 离最近的聚类中心代表的簇中.在将所有数据点归为 用h,(x)对样本x进行分类，计算h,(x)分类错 k个类后，重新计算各个类的中心，然后再计算各个点 误率8，= ∑g×lr-h,(x)1 和新的各个类中心距离，重新划分数据类，直到各个类 1 中心不再变化为止 if e>or8=0 经过聚类后的数据集虽然数量变少，但数据的空 break 间特征保留了下来.如图1与图2所示，图1是聚类前 更新样本的权重： 的数据分布图，图2是聚类后的数据分布图，从图中可 以看出，聚类后数据量变少，但数据集的空间分布仍然 g=g,hx）=r otherwise 未变，数据集的分布特征被保留了下来 0.210 B=色6R<1:2=言是-个归一化 常量 输出：集成强分类器.（国)=册二g司 0.130 在集成分类中，最常用的弱分类器是Decision-- Stump.DecisionStump算法是一种简单的单层决策树， 有时也成为决策桩.单层决策树只选择一个具有最大 信息嫡的属性来进行分类).另外，因为Adaboost算 0.055l 法是一个迭代的过程，因此弱分类器应选择时间复杂 10.38 24.83 39.28 属性一 度较低的算法[s].在经典算法中，KNN是一种时间复 图1聚类前的数据分布 杂度较低的算法，其算法的思想是：如果与某个数据样 Fig.1 Data distribution before clustering 本距离最近的k个数据样本中大多数都属于某一类， 基于聚类的欠采样过程利用聚类方法在保留多数 则该数据样本也属于该类.基于上述原因，本文选择 类数据特征的基础上使得两类数据变均衡，集成分类 KNN和DecisionStump两种分类器作为弱分类器.这 过程则基于集成学习的方法在已经均衡的数据集上进 两种算法都简单快速，适合用在迭代过程中 行分类规则的学习，最终输出分类器 1.2.2集成算法的训练过程 2ECUA实验准备 在得到均衡的数据集后，用AdaBoost集成算法对 2.1数据集说明 新的数据集进行分类训练.具体步骤如下 为了检验ECUA算法的分类性能，选取UCI数据 输入：均衡数据集D',迭代次数T 集(htp:/archive.ics.uci.ed/ml/datasets.html)中六 初始化：样本权重a=1/W,i=1,2,…,N,N= 组不均衡数据集进行实验，分别是：ecoli、Pima Indians card(D') diabetes(以下简称pima)、blood transfusion(以下简称 forl=1,2,…,T blood)、Haberman's survival(以下简称haberman)、Wis- 用样本x∈D'训练弱分类器h,(x),得到弱分类 consin prognostic breast cancer(以下简称wpbe)以及工程科学学报,第 39 卷,第 8 期 D忆 = D忆胰D忆1 输出:均衡数据集 D忆 上述过程为基于聚类的欠采样过程,输入不均衡 数据集,得到均衡数据集. 其中 Cluster( k,D) 算法选 用 k鄄means 算法. 聚类过程中使用的距离公式为欧氏 距离. 在欠采样过程中,首先将数据集分为少数类数据 和多数类数据. 少数类数据直接放入新的数据集中, 多数类数据需要经过聚类后,将各类的中心点放入新 的数据集. 聚类方法选择 k鄄means 算法,因为要保证欠 采样后多数类数据与少数类数据的个数达到平衡,因 此设置多数类聚类的数目为少数类数据的个数. 先随 机选择 k 个数据作为聚类中心,然后计算数据集中每 个点和各个聚类中心的欧氏距离,将数据样本分到距 离最近的聚类中心代表的簇中. 在将所有数据点归为 k 个类后,重新计算各个类的中心,然后再计算各个点 和新的各个类中心距离,重新划分数据类,直到各个类 中心不再变化为止. 经过聚类后的数据集虽然数量变少,但数据的空 间特征保留了下来. 如图1 与图2 所示,图1 是聚类前 的数据分布图,图 2 是聚类后的数据分布图,从图中可 以看出,聚类后数据量变少,但数据集的空间分布仍然 未变,数据集的分布特征被保留了下来. 图 1 聚类前的数据分布 Fig. 1 Data distribution before clustering 基于聚类的欠采样过程利用聚类方法在保留多数 类数据特征的基础上使得两类数据变均衡,集成分类 过程则基于集成学习的方法在已经均衡的数据集上进 行分类规则的学习,最终输出分类器. 1郾 2郾 2 集成算法的训练过程 在得到均衡的数据集后,用 AdaBoost 集成算法对 新的数据集进行分类训练. 具体步骤如下. 输入:均衡数据集 D忆,迭代次数 T 初始化:样本权重 琢 1 i = 1 / N, i = 1,2,…,N,N = card(D忆) for t = 1,2,…,T 用样本 x i沂D忆训练弱分类器 ht(x),得到弱分类 图 2 聚类后的数据分布 Fig. 2 Data distribution after clustering 器 ht(x) 用 ht(x)对样本 x i 进行分类,计算 ht(x)分类错 误率 着t = 移 N i = 1 琢 t i 伊 | r i - ht(xi) | if 着t > 1 2 or 着t = 0 break 更新样本的权重: 琢 t + 1 i = 琢 t i Zt 茁t, ht(xi) = r i 1, { otherwise 茁t = 着t 1 - 着t ,茁t < 1;Zt = 移 N i = 1 琢 t + 1 i 是一个归一化 常量. 输出:集成强分类器 hfin (x) = arg max r沂{0,1} 移t:ht(xi) = r i log 1 茁t 在集成分类中,最常用的弱分类器是 Decision鄄 Stump. DecisionStump 算法是一种简单的单层决策树, 有时也成为决策桩. 单层决策树只选择一个具有最大 信息熵的属性来进行分类[14] . 另外,因为 Adaboost 算 法是一个迭代的过程,因此弱分类器应选择时间复杂 度较低的算法[15] . 在经典算法中,KNN 是一种时间复 杂度较低的算法,其算法的思想是:如果与某个数据样 本距离最近的 k 个数据样本中大多数都属于某一类, 则该数据样本也属于该类. 基于上述原因,本文选择 KNN 和 DecisionStump 两种分类器作为弱分类器. 这 两种算法都简单快速,适合用在迭代过程中. 2 ECUA 实验准备 2郾 1 数据集说明 为了检验 ECUA 算法的分类性能,选取 UCI 数据 集( http: / / archive. ics. uci. edu / ml / datasets. html) 中六 组不均衡数据集进行实验,分别是:ecoli、Pima Indians diabetes(以下简称 pima)、blood transfusion(以下简称 blood)、Haberman蒺s survival(以下简称 haberman)、Wis鄄 consin prognostic breast cancer ( 以下简称 wpbc) 以及 ·1246·