【学术论文】不平衡分类问题研究综述

第4卷第2期 智能系统学报 Vol 4 Ng 2 2009年4月 CAA I Transactions on Intelligent Systems Apr 2009 不平衡分类问题研究综述 叶志飞，文益民2，吕宝粮 (1上海交通大学计算机科学与工程系，上海200240,2湖南工业职业技术学院信息工程系，湖南长沙410208： 3上海交通大学智能计算与智能系统教育部微软重点实验室，上海200240) 摘要：实际的分类问题往往都是不平衡分类问题，采用传统的分类方法，难以得到满意的分类效果.为此，十多年 来，人们相继提出了各种解决方案.对国内外不平衡分类问题的研究做了比较详细地综述，讨论了数据不平衡性引 发的问题，介绍了目前几种主要的解决方案.通过仿真实验，比较了具有代表性的重采样法、代价敏感学习、训练集 划分以及分类器集成在3个实际的不平衡数据集上的分类性能，发现训练集划分和分类器集成方法能较好地处理 不平衡数据集，给出了针对不平衡分类问题的分类器评测指标和将来的工作】 关键词：机器学习；不平衡模式分类；重采样；代价敏感学习；训练集划分，分类器集成；分类器性能评测 中图分类号：TP181文献标识码：A文章编号：16734785(2009)02014809 A survey of i ba lanced pa ttern classifica tion problem s YE Zhi-fei,WEN Yim in2,LU Bao-liang 3 (1.Deparment of Computer Science and Engineering,Shanghai Jiao Tong University,Shanghai 200240,China 2 Deparment of In- omation Engineering.Hunan Industry Polytechnic,Changsha 410208,China;3 MOEMicrosoft Key Lab or Intelligent Computing and Intelligent Systems,Shanghai Jiao Tong University,Shanghai 200240,China) Abstract:mbalanced data sets have akays been regarded as presenting significant difficulties when app lying ma- chine leaming methods to real-world pattem classification problems A lthough various approaches have been pro- posed during the past decade,lim itations are mposed by many realworld ibalanced data sets,and as a result,a bot of further research is currently being done In this paper,we provide an up-to-date survey of research on mbal- anced pattem classification problems We first took a deep look into the problems that mbalanced data sets bring, and then we introduced different kinds of solutons in detail,with their representative approaches Finally,using three real ibalanced data sets,we compared the perfomance of some typ icalmethods including re-sampling,cost sensitive leaming,training set partitions,and the perfommance of classifier ensembles In addition,top ics such as evaluation indexes and future areas of research were also discussed Keywords:machine leaming mbalanced pattem classificaton;re-sampling cost sensitive leaming task decom- position;classifier ensemble;evaluation matrices 所谓不平衡分类问题，是指训练样本数量在类 稀有的类，它们虽然很重要，但是用传统的分类方 间分布不平衡的模式分类问题.具体地说就是某些法，却难以被正确分类.当传统的机器学习方法用于 类的样本数量远远少于其他类.本文称具有少量样解决这些不平衡分类问题时，往往出现分类器性能 本的那些类为稀有类，而具有大量样本的那些类为的大幅度下降，得到的分类器具有很大的偏向性.最 大类.物以稀为贵，稀有的信息，往往能获得人们更 常见的表现是稀有类的识别率远远低于大类.因此， 多的关注.在许多实际的模式分类问题中，同样存在 本属于稀有类的样本往往被错分到大类 在实际应用中，不平衡问题很常见.有些问题其 收稿日期：200804-23 原始数据的分布就存在不平衡，如通过卫星雷达图 基金项目：国家自然科学基金资助项目(60375022,60473040) 通信作者：吕宝粮.Email blu(@cs sjtu edu cn 片检测海面石油油污山、监测信用卡非法交易) 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 第 4卷第 2期 智 能 系 统 学 报 Vol. 4 №. 2 2009年 4月 CAA I Transactions on Intelligent System s Ap r. 2009 不平衡分类问题研究综述 叶志飞 1 , 文益民 2 ,吕宝粮 1, 3 (1. 上海交通大学 计算机科学与工程系 ,上海 200240; 2. 湖南工业职业技术学院 信息工程系 ,湖南 长沙 410208; 3. 上海交通大学 智能计算与智能系统教育部微软重点实验室 ,上海 200240) 摘 要 :实际的分类问题往往都是不平衡分类问题 ,采用传统的分类方法 ,难以得到满意的分类效果. 为此 ,十多年 来 ,人们相继提出了各种解决方案. 对国内外不平衡分类问题的研究做了比较详细地综述 ,讨论了数据不平衡性引 发的问题 ,介绍了目前几种主要的解决方案. 通过仿真实验 ,比较了具有代表性的重采样法、代价敏感学习、训练集 划分以及分类器集成在 3个实际的不平衡数据集上的分类性能 ,发现训练集划分和分类器集成方法能较好地处理 不平衡数据集 ,给出了针对不平衡分类问题的分类器评测指标和将来的工作. 关键词 :机器学习 ;不平衡模式分类 ;重采样 ;代价敏感学习 ;训练集划分 ;分类器集成 ;分类器性能评测 中图分类号 : TP181 文献标识码 : A 文章编号 : 167324785 (2009) 0220148209 A survey of imbalanced pattern classification problem s YE Zhi2fei 1 ,W EN Yi2m in 2 ,LU Bao2liang 1, 3 (1. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; 2. Department of In2 formation Engineering, Hunan Industry Polytechnic, Changsha 410208, China; 3. MOE2M icrosoft Key Lab. for Intelligent Computing and Intelligent Systems, Shanghai Jiao Tong University, Shanghai 200240, China) Abstract: Imbalanced data sets have always been regarded as p resenting significant difficulties when app lying ma2 chine learning methods to real2world pattern classification p roblem s. A lthough various app roaches have been p ro2 posed during the past decade, lim itations are imposed by many real2world imbalanced data sets, and as a result, a lot of further research is currently being done. In this paper, we p rovide an up2to2date survey of research on imbal2 anced pattern classification p roblem s. W e first took a deep look into the p roblem s that imbalanced data sets bring, and then we introduced different kinds of solutions in detail, with their rep resentative app roaches. Finally, using three real imbalanced data sets, we compared the performance of some typ icalmethods including re2samp ling, cost sensitive learning, training set partitions, and the performance of classifier ensembles. In addition, top ics such as evaluation indexes and future areas of research were also discussed. Keywords:machine learning; imbalanced pattern classification; re2samp ling; cost sensitive learning; task decom2 position; classifier ensemble; evaluation matrices 收稿日期 : 2008204223. 基金项目 :国家自然科学基金资助项目 (60375022, 60473040). 通信作者 :吕宝粮. E2mail: blu@cs. sjtu. edu. cn. 所谓不平衡分类问题 ,是指训练样本数量在类 间分布不平衡的模式分类问题. 具体地说就是某些 类的样本数量远远少于其他类. 本文称具有少量样 本的那些类为稀有类 ,而具有大量样本的那些类为 大类. 物以稀为贵 ,稀有的信息 ,往往能获得人们更 多的关注. 在许多实际的模式分类问题中 ,同样存在 稀有的类 ,它们虽然很重要 ,但是用传统的分类方 法 ,却难以被正确分类. 当传统的机器学习方法用于 解决这些不平衡分类问题时 ,往往出现分类器性能 的大幅度下降 ,得到的分类器具有很大的偏向性. 最 常见的表现是稀有类的识别率远远低于大类. 因此 , 本属于稀有类的样本往往被错分到大类. 在实际应用中 ,不平衡问题很常见. 有些问题其 原始数据的分布就存在不平衡 ,如通过卫星雷达图 片检测海面石油油污 [ 1 ]、监测信用卡非法交易 [ 2 ]

第2期 叶志飞，等：不平衡分类问题研究综述 ·149· 发掘基因序列中编码信息以及医学数据分类3) 的原因在于它和噪声数据块难以区分.许多分类器 等.这些问题都以稀有类的信息为关注的重点，如在 为了防止过学习的产生，需要进行统计显著性(sa 信用卡非法交易记录的监测问题中，非法交易记录 tistical significance)检测，如决策树分类器的剪枝， 是监测的目标.但训练数据中包含大量正常的信用 关联规则分类器的规则筛选等，只有覆盖足够多样 卡交易记录，只有很少的一部分是非法交易记录，使 本的决策规则和关联规则才能被保留下来.小区块 用一般的模式分类方法，非法交易记录的检测率很 的数据经常无法顺利通过这类显著性检测，但如果 低.有些不平衡分类问题源自数据收集过程中人为 为了使它们通过检测而降低检测的阈值，又将无法 地造成的不平衡，比如由于个人隐私或者高昂的数 有效地去除噪声 据采集代价等因素导致某些类的样本数量过少.还 相对稀缺是指稀有类样本本身数量并不过少 有些不平衡问题来自多类(multi-class)问题和多标 但相对大类，占有的比例过小.在这种情况下，稀有 号(multi-label)问题的分解.有些分类器如支持向量 类样本的识别好比大海捞针，使得基于启发式的贪 机(SM),无法直接解决多类多标号问题，必须将 心搜索方法效果变差II.Japkowicz和Stephen's1通 原始问题分解成一系列两类问题解决，这样很容易 过改变训练集的概念复杂度、样本不平衡度和训练 导致原来平衡的问题变得不平衡，原来不平衡的问 集规模发现，当总样本数量足够多时，相对稀缺并不 题变得更加不平衡 一定引起分类器性能下降.相反，绝对稀缺导致的稀 不平衡分类问题到底有什么样的特征？它们为 有样本分布不集中且数量过少才容易引起分类器性 何会导致分类器性能下降？有什么有效的方法可以能下降 解决不平衡分类问题？通过分析各种不平衡分类问12噪声问题 题和己有的解决方案，希望对上述问题做出回答.内 噪声数据的存在不可避免，并在一定程度上影 容安排如下：第1节讨论不平衡问题的特征及问题 响到分类器性能.但是，对不平衡分类问题，噪声数 点；第2节介绍目前己有的解决不平衡问题的主要 据对稀有类将产生更大的影响).只要在稀有类的 方法；第3节讨论针对不平衡问题的分类器评价指 决策域存在少数的噪声样本，就会影响该稀有类决 标；第4节通过仿真实验比较主要的几种分类方法 策面的学习.也就是说，稀有类的抗噪能力较弱，并 在一些不平衡数据上的分类性能；第5节总结并讨 且分类器难以区分稀有类样本和噪声数据).如果 论未来的研究方向。 分类器采用一些防止过学习的技术去除噪声，则会 将一些稀有类样本信息一并去除.如果不去除噪声， 1不平衡分类问题 分类性能也难以提高 不平衡分类问题具有一系列传统模式分类方法 13决策面偏移问题 所没有考虑到的特点，从而引发了一系列传统模式 传统的模式分类方法，大都建立在训练样本数 分类方法难以解决的问题， 量均衡的前提下.当用于解决不平衡分类问题时，它 1.1数据稀缺问题 们的分类性能往往有不同程度的下降， 样本分布的不平衡容易导致稀有类样本的稀 基于特征空间决策面进行类别划分的分类器 缺，具体地说，稀缺包括绝对稀缺和相对稀缺 如支持向量机，目标在于寻找一个最优的决策面.为 绝对稀缺是指稀有类训练样本数量绝对过少 了降低噪声数据的影响和防止过学习的产生，最优 导致该类信息无法通过训练样本充分表示.Weis) 决策面必须兼顾训练分类准确率(accuracy)和决策 通过生成人工数据的实验指出，绝对数据稀缺类的 面的复杂度，即采用结构风险最小化原则.然而，如 分类错误率要比一般类高出许多.此外，当某类数据 果训练集不平衡，则支持向量的个数也不平衡.在结 过于稀缺时，容易在特征空间中形成小的数据区域， 构风险最小化原则下，支持向量机会忽略稀有类少 从而引发小区块(sall disjuncts)问题.Weiss和 量支持向量对结构风险的影响，而扩大决策边界，最 Hish6通过30个实际数据集的测试结果表明，分 终导致训练的实际超平面与最优超平面不一致， 类错误大部分集中在小区块上 基于概率估计的分类器，如贝叶斯分类器，分类 小区块之所以有很高的分类错误率，其中很大 准确率依赖于概率分布的准确估计，当稀有类样本 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 发掘基因序列中编码信息以及医学数据分类 [ 324 ] 等. 这些问题都以稀有类的信息为关注的重点 ,如在 信用卡非法交易记录的监测问题中 ,非法交易记录 是监测的目标. 但训练数据中包含大量正常的信用 卡交易记录 ,只有很少的一部分是非法交易记录 ,使 用一般的模式分类方法 ,非法交易记录的检测率很 低. 有些不平衡分类问题源自数据收集过程中人为 地造成的不平衡 ,比如由于个人隐私或者高昂的数 据采集代价等因素导致某些类的样本数量过少. 还 有些不平衡问题来自多类 (multi2class)问题和多标 号 (multi2label)问题的分解. 有些分类器如支持向量 机 (SVM ) ,无法直接解决多类多标号问题 ,必须将 原始问题分解成一系列两类问题解决 ,这样很容易 导致原来平衡的问题变得不平衡 ,原来不平衡的问 题变得更加不平衡. 不平衡分类问题到底有什么样的特征 ? 它们为 何会导致分类器性能下降 ? 有什么有效的方法可以 解决不平衡分类问题 ? 通过分析各种不平衡分类问 题和已有的解决方案 ,希望对上述问题做出回答. 内 容安排如下 :第 1节讨论不平衡问题的特征及问题 点 ;第 2节介绍目前已有的解决不平衡问题的主要 方法 ;第 3节讨论针对不平衡问题的分类器评价指 标 ;第 4节通过仿真实验比较主要的几种分类方法 在一些不平衡数据上的分类性能 ;第 5节总结并讨 论未来的研究方向. 1 不平衡分类问题 不平衡分类问题具有一系列传统模式分类方法 所没有考虑到的特点 ,从而引发了一系列传统模式 分类方法难以解决的问题. 1. 1 数据稀缺问题 样本分布的不平衡容易导致稀有类样本的稀 缺 ,具体地说 ,稀缺包括绝对稀缺和相对稀缺. 绝对稀缺是指稀有类训练样本数量绝对过少 , 导致该类信息无法通过训练样本充分表示. W eiss [ 5 ] 通过生成人工数据的实验指出 ,绝对数据稀缺类的 分类错误率要比一般类高出许多. 此外 ,当某类数据 过于稀缺时 ,容易在特征空间中形成小的数据区域 , 从而引发小区块 ( small disjuncts) 问题. W eiss和 H irsh [ 6 ]通过 30个实际数据集的测试结果表明 ,分 类错误大部分集中在小区块上. 小区块之所以有很高的分类错误率 ,其中很大 的原因在于它和噪声数据块难以区分. 许多分类器 为了防止过学习的产生 ,需要进行统计显著性 ( sta2 tistical significance) 检测 ,如决策树分类器的剪枝 , 关联规则分类器的规则筛选等 ,只有覆盖足够多样 本的决策规则和关联规则才能被保留下来. 小区块 的数据经常无法顺利通过这类显著性检测 ,但如果 为了使它们通过检测而降低检测的阈值 ,又将无法 有效地去除噪声. 相对稀缺是指稀有类样本本身数量并不过少 , 但相对大类 ,占有的比例过小. 在这种情况下 ,稀有 类样本的识别好比大海捞针 ,使得基于启发式的贪 心搜索方法效果变差 [ 7 ] . Japkowicz和 Stephen [ 8 ]通 过改变训练集的概念复杂度、样本不平衡度和训练 集规模发现 ,当总样本数量足够多时 ,相对稀缺并不 一定引起分类器性能下降. 相反 ,绝对稀缺导致的稀 有样本分布不集中且数量过少才容易引起分类器性 能下降. 1. 2 噪声问题 噪声数据的存在不可避免 ,并在一定程度上影 响到分类器性能. 但是 ,对不平衡分类问题 ,噪声数 据对稀有类将产生更大的影响 [ 7 ] . 只要在稀有类的 决策域存在少数的噪声样本 ,就会影响该稀有类决 策面的学习. 也就是说 ,稀有类的抗噪能力较弱 ,并 且分类器难以区分稀有类样本和噪声数据 [ 5 ] . 如果 分类器采用一些防止过学习的技术去除噪声 ,则会 将一些稀有类样本信息一并去除. 如果不去除噪声 , 分类性能也难以提高. 1. 3 决策面偏移问题 传统的模式分类方法 ,大都建立在训练样本数 量均衡的前提下. 当用于解决不平衡分类问题时 ,它 们的分类性能往往有不同程度的下降. 基于特征空间决策面进行类别划分的分类器 , 如支持向量机 ,目标在于寻找一个最优的决策面. 为 了降低噪声数据的影响和防止过学习的产生 ,最优 决策面必须兼顾训练分类准确率 ( accuracy)和决策 面的复杂度 ,即采用结构风险最小化原则. 然而 ,如 果训练集不平衡 ,则支持向量的个数也不平衡. 在结 构风险最小化原则下 ,支持向量机会忽略稀有类少 量支持向量对结构风险的影响 ,而扩大决策边界 ,最 终导致训练的实际超平面与最优超平面不一致. 基于概率估计的分类器 ,如贝叶斯分类器 ,分类 准确率依赖于概率分布的准确估计. 当稀有类样本 第 2期 叶志飞 ,等 :不平衡分类问题研究综述 ·149·

·150· 智能系统学报 第4卷 过少时，概率估计的准确率将远小于大类，稀有类的 的样本重新标定成稀有类样本，以降低不平衡度 识别率也因此下降.基于规则的分类器，如决策树和 另一方面，下采样通过舍弃部分大类样本的方 关联规则分类器，需要对规则进行筛选.其中，支持 法，降低不平衡程度.Kubat和Mawin采用单边 度(support))和可信度(confidence)是规则筛选的重 采样方式，去除大类中的噪音样本边界样本和冗余 要指标.但是，当训练集不平衡时，基于上述指标的 样本.Chen等人u则通过修剪大类的支持向量，达 筛选变得困难且不合理) 到平衡支持向量个数的目的，从而提高稀有类的识 1.4评测指标问题 别率.Raskutti和Kowalczyk同时考虑上采样和下 分类器评测指标的科学性直接影响着分类器的 采样，并且扩展到一类学习，即只采用一类的样本作 性能，因为分类器训练的目标是实现最高的评测指 为训练集，因此不存在不平衡分类问题.Estabrooks 标.传统的模式分类方法一般以准确率作为分类器 和J即kowic2同时采用上采样和下采样以及不同 评测指标.但是以准确率为评测指标的分类器倾向 的采样率，获得大量的子分类器，并使用混合专家 于降低稀有类的分类效果0).而且准确率不重视 (m ixtureof-experts)学习框架将这些子分类器集成. 稀有类对分类性能评测的影响.例如，假设有一个训 他们的结果显示，这种方法比普通的AdaBoost有更 练样本数量为1：99的两类问题，即使分类器将所 好的分类效果，但并不清楚到底是上采样还是下采 有样本分到大类，它仍可以得到99%的训练准确 样更有效，也不清楚哪种采样率最合适 率 虽然重采样在一些数据集上取得了不错的效 果，但是这类方法也存在一些缺陷.上采样方法并不 2不平衡分类问题的解决策略 增加任何新的数据，只是重复一些样本或增加一些 迄今为止，解决不平衡分类问题的策略可以分 人工生成的稀有类样本，增加了训练时间.更危险的 为两大类.一类是从训练集入手，通过改变训练集样 是，上采样复制某些稀有类样本，或者在它周围生成 本分布，降低不平衡程度.另一类是从学习算法入 新的稀有类样本，使得分类器过分注重这些样本，导 手，根据算法在解决不平衡问题时的缺陷，适当地修 致过学习2,4).上采样不能从本质上解决稀有类样 改算法使之适应不平衡分类问题.平衡训练集的方 本的稀缺性和数据表示的不充分性，因此有人指出 法主要有训练集重采样(re-sampling)方法和训练集 它的性能不如下采样I2).但是Japkowic2对人工 划分方法.学习算法层面的策略包括分类器集成、代 数据的一项系统研究得到了相反的结论.下采样在 价敏感学习和特征选择方法等 去除大类样本的时候，容易去除重要的样本信息.虽 21重采样方法 然有些启发式的下采样方法，只是去除元余样本和 重采样方法是通过增加稀有类训练样本数的上 噪声样本，但是多数情况下这类样本只是小部分，因 采样(p~sampling)和减少大类样本数的下采样 此这种方法能够调整的不平衡度相当有限 (down~mp ling)使不平衡的样本分布变得比较平22训练集划分方法 衡，从而提高分类器对稀有类的识别率」 对训练数据集进行划分，是另一种有效的训练 最原始的上采样方法是复制稀有类的样本，但 集平衡方法.Chan和Sol621首先根据代价敏感学 是这样做容易导致过学习2】，并且对提高稀有类识 习的需要，学习一个合理的类别样本分布比例.然后 别率没有太大帮助1.较高级的上采样方法则采用 将大类样本随机划分成一系列不相交子集.这些子 一些启发式技巧，有选择地复制稀有类样本，或者生 集的大小由稀有类样本集的数量和预先学习的样本 成新的稀有类样本.Chawla等人提出的SMOTE 分布比例决定.接下来分别将这些不相交子集跟稀 算法是一种简单有效的上采样方法，该方法首先为 有类样本结合，组成一系列平衡的分类子问题，单独 每个稀有类样本随机选出几个邻近样本，并且在该 训练成子分类器.最后通过元学习(meta leaming) 样本与这些邻近的样本的连线上随机取点，生成无 将这些子分类器的输出进一步学习成组合分类器」 重复的新的稀有类样本.Lee1s则通过为训练集中 这种方法在信用卡非法使用检测问题上大大降低了 的稀有类样本加上随机噪声的方式获取新的正类样 总代价.Yan等人2)采用类似的问题分解方式，并 本.Kubat等人16将稀有类和大类交叉分布区域内 将每个子问题用SM独立训练后采用分类器集成， 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 过少时 ,概率估计的准确率将远小于大类 ,稀有类的 识别率也因此下降. 基于规则的分类器 ,如决策树和 关联规则分类器 ,需要对规则进行筛选. 其中 ,支持 度 ( support) 和可信度 ( confidence)是规则筛选的重 要指标. 但是 ,当训练集不平衡时 ,基于上述指标的 筛选变得困难且不合理 [ 9 ] . 1. 4 评测指标问题 分类器评测指标的科学性直接影响着分类器的 性能 ,因为分类器训练的目标是实现最高的评测指 标. 传统的模式分类方法一般以准确率作为分类器 评测指标. 但是以准确率为评测指标的分类器倾向 于降低稀有类的分类效果 [ 10211 ] . 而且准确率不重视 稀有类对分类性能评测的影响. 例如 ,假设有一个训 练样本数量为 1∶99的两类问题 ,即使分类器将所 有样本分到大类 ,它仍可以得到 99%的训练准确 率. 2 不平衡分类问题的解决策略 迄今为止 ,解决不平衡分类问题的策略可以分 为两大类. 一类是从训练集入手 ,通过改变训练集样 本分布 ,降低不平衡程度. 另一类是从学习算法入 手 ,根据算法在解决不平衡问题时的缺陷 ,适当地修 改算法使之适应不平衡分类问题. 平衡训练集的方 法主要有训练集重采样 ( re2samp ling)方法和训练集 划分方法. 学习算法层面的策略包括分类器集成、代 价敏感学习和特征选择方法等. 2. 1 重采样方法 重采样方法是通过增加稀有类训练样本数的上 采样 ( up2samp ling) 和减少大类样本数的下采样 ( down2samp ling)使不平衡的样本分布变得比较平 衡 ,从而提高分类器对稀有类的识别率. 最原始的上采样方法是复制稀有类的样本 ,但 是这样做容易导致过学习 [ 12 ] ,并且对提高稀有类识 别率没有太大帮助 [ 13 ] . 较高级的上采样方法则采用 一些启发式技巧 ,有选择地复制稀有类样本 ,或者生 成新的稀有类样本. Chawla等人 [ 14 ]提出的 SMOTE 算法是一种简单有效的上采样方法 ,该方法首先为 每个稀有类样本随机选出几个邻近样本 ,并且在该 样本与这些邻近的样本的连线上随机取点 ,生成无 重复的新的稀有类样本. Lee [ 15 ]则通过为训练集中 的稀有类样本加上随机噪声的方式获取新的正类样 本. Kubat等人 [ 16 ]将稀有类和大类交叉分布区域内 的样本重新标定成稀有类样本 ,以降低不平衡度. 另一方面 ,下采样通过舍弃部分大类样本的方 法 ,降低不平衡程度. Kubat和 Matwin [ 17 ]采用单边 采样方式 ,去除大类中的噪音样本、边界样本和冗余 样本. Chen等人 [ 18 ]则通过修剪大类的支持向量 ,达 到平衡支持向量个数的目的 ,从而提高稀有类的识 别率. Raskutti和 Kowalczyk [ 19 ]同时考虑上采样和下 采样 ,并且扩展到一类学习 ,即只采用一类的样本作 为训练集 ,因此不存在不平衡分类问题. Estabrooks 和 Japkowic [ 20 ]同时采用上采样和下采样以及不同 的采样率 ,获得大量的子分类器 ,并使用混合专家 (m ixture2of2experts)学习框架将这些子分类器集成. 他们的结果显示 ,这种方法比普通的 AdaBoost有更 好的分类效果 ,但并不清楚到底是上采样还是下采 样更有效 ,也不清楚哪种采样率最合适. 虽然重采样在一些数据集上取得了不错的效 果 ,但是这类方法也存在一些缺陷. 上采样方法并不 增加任何新的数据 ,只是重复一些样本或增加一些 人工生成的稀有类样本 ,增加了训练时间. 更危险的 是 ,上采样复制某些稀有类样本 ,或者在它周围生成 新的稀有类样本 ,使得分类器过分注重这些样本 ,导 致过学习 [ 12, 14 ] . 上采样不能从本质上解决稀有类样 本的稀缺性和数据表示的不充分性 ,因此有人指出 它的性能不如下采样 [ 12 ] . 但是 Japkowicz [ 8 ]对人工 数据的一项系统研究得到了相反的结论. 下采样在 去除大类样本的时候 ,容易去除重要的样本信息. 虽 然有些启发式的下采样方法 ,只是去除冗余样本和 噪声样本 ,但是多数情况下这类样本只是小部分 ,因 此这种方法能够调整的不平衡度相当有限. 2. 2 训练集划分方法 对训练数据集进行划分 ,是另一种有效的训练 集平衡方法. Chan和 Stolfo [ 2 ]首先根据代价敏感学 习的需要 ,学习一个合理的类别样本分布比例. 然后 将大类样本随机划分成一系列不相交子集. 这些子 集的大小由稀有类样本集的数量和预先学习的样本 分布比例决定. 接下来分别将这些不相交子集跟稀 有类样本结合 ,组成一系列平衡的分类子问题 ,单独 训练成子分类器. 最后通过元学习 (meta learning) 将这些子分类器的输出进一步学习成组合分类器. 这种方法在信用卡非法使用检测问题上大大降低了 总代价. Yan等人 [ 21 ]采用类似的问题分解方式 ,并 将每个子问题用 SVM独立训练后采用分类器集成 , ·150· 智 能 系 统 学 报 第 4卷

第2期 叶志飞，等：不平衡分类问题研究综述 ·151 得到的组合分类器的性能超过了上采样和下采样方 24代价敏感学习方法 法.上述训练集划分方法仅考虑了划分后子训练集 在大部分不平衡分类问题中，稀有类是分类的 的规模和分布，没有对划分规则作进一步考虑.Lu 重点.在这种情况下，正确识别出稀有类的样本比识 和Io2提出了最小最大模块化(m inmax modular) 别大类的样本更有价值.反过来说，错分稀有类的样 神经网络模型，该模型利用最小最大化集成规则能 本需要付出更大的代价.代价敏感学习赋予各个 有效地将子分类器组合，使组合分类器容易地实现 类别不同的错分代价，它能很好地解决不平衡分类 并列学习和增量学习.之后Lu等人2将上述模型 问题.以两类问题为例，假设正类是稀有类，并具有 推广到支持向量机并提出了部分对部分”(part vs 更高的错分代价，则分类器在训练时，会对错分正类 par)任务分解策略.部分对部分任务分解策略可 样本做更大的惩罚，迫使最终分类器对正类样本有 对不平衡两类子问题作进一步分解.这种分解策略 更高的识别率 可以自由地控制每个子问题的规模和平衡度，并且 Dom ingos2提出了一种Metacost方法，该方法 可以根据先验知识和训练集样本的分布特征，制定 通过估计训练样本的后验概率密度，结合代价矩阵 有效的分解规则.实验表明，该方法比代价敏感学习 (cost matriⅸ)计算每个训练样本的理想类别，然后根 和重采样方法能更好地解决不平衡问题[24) 据理想类别修改原训练样本的类别，得到新的训练 23分类器集成方法 集，最后使用基于错误率的分类器学习这个新的训 上述通过训练集划分得到的子分类器，利用分 练集.仿真实验表明，Metacost比下采样和上采样方 类器集成的方法获得了良好的效果.Kotsiantis和 法能获得更低的错误代价.Metacost的重要意义在 Peas5将训练集重采样后用3种学习方法分别于它能将普通的基于准确率的学习方法容易地改造 训练，然后将得到的分类器采用多数投票方法给出 成对错分代价敏感的学习方法.Chen2在平衡随机 预测类别.实验表明，他们的方法能提高对稀有类样 森林的基础上提出了带权随机森林算法，该方法赋 本的识别率.Estabrook等人261通过计算发现，根据 予每个类一个权值，训练样本最少的类赋予的权值 训练集的自然分布得到的分类器不一定具有最好的 最大.在构造决策树的过程中引入权值，每一棵决策 一般化能力.他们提出通过对原不平衡问题进行重 树的决策采用带权多数投票.最后所有的决策树采 采样，从而构建多个平衡度不同的训练集，训练后采 用带权投票集成.Che等人I33通过训练集先验信息 用分类器挑选和偏向正类的原则将各个分类器综 的分析，利用支持向量机为不同类的样本设置惩罚 合，仿真实验表明，该方法比单独应用上采样和下采 系数」 样方法获得了更好的准确率和ROC(receiver oper 给不同的训练样本赋予不同的权值也能起到代 ating characteristic)曲线.Chen等人I2提出了平衡 价敏感学习的作用.Fan等人提出了一种AdaCost 随机森林的方法，该方法对正类和反类分别进行重 算法，该算法通过在Boosting算法的权值更新规则中 采样，重采样多次后采用多数投票的方法进行集成 引入每个训练样本的错分代价，提高了Boosting算法 学习.Chawla等人I2将boosting算法与MOTE算 对稀有类的查全率和查准率.该算法的权值更新原则 法结合成MOTEBoost算法，该算法每次迭代使用 是：如果错分代价较大的样本被弱分类器错分则它 SMOTE生成新的样本，取代原有Adaboost算法中队 对应的权值被较大地增加.如果它被正确分类，则 样本权值的调整，使得Boosting算法专注于正类中 它对应的权值被较小程度地减少.Josh等人5通 的难分样本.Lu等人2基于人脸识别的级联模型 过研究发现，如果AdaCost算法中的基分类器能获得 提出了一种基于级联模型的不平衡数据分类方法， 较平衡的查全率和查准率，则AdaCost能获得对稀有 该方法通过逐步筛掉反类样本，使得级联结构中后 类较平衡的查全率和查准率 面的结点得到更为平衡的训练集.Zhou和Lo1提 代价敏感学习能有效地提高稀有类的识别率」 出了代价敏感神经网络与分类器集成相结合的方 但问题是，一方面，在多数情况下，真实的错分代价 法，他们通过21个UC标准数据集的实验发现，分 很难被准确地估计[1.另一方面，虽然许多分类器 类器集成不仅对处理2类不平衡问题有效，而且对 可以直接引入代价敏感学习机制，如支持向量机和 多类不平衡问题同样有效， 决策树，但是也有一些分类器不能直接使用代价敏 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 得到的组合分类器的性能超过了上采样和下采样方 法. 上述训练集划分方法仅考虑了划分后子训练集 的规模和分布 ,没有对划分规则作进一步考虑. Lu 和 Ito [ 22 ]提出了最小最大模块化 (m in2max modular) 神经网络模型 ,该模型利用最小最大化集成规则 ,能 有效地将子分类器组合 ,使组合分类器容易地实现 并列学习和增量学习. 之后 Lu等人 [ 23 ]将上述模型 推广到支持向量机并提出了“部分对部分 ”(part vs. part)任务分解策略.“部分对部分 ”任务分解策略可 对不平衡两类子问题作进一步分解. 这种分解策略 可以自由地控制每个子问题的规模和平衡度 ,并且 可以根据先验知识和训练集样本的分布特征 ,制定 有效的分解规则. 实验表明 ,该方法比代价敏感学习 和重采样方法能更好地解决不平衡问题 [ 24 ] . 2. 3 分类器集成方法 上述通过训练集划分得到的子分类器 ,利用分 类器集成的方法获得了良好的效果. Kotsiantis和 Pintelas [ 25 ]将训练集重采样后用 3种学习方法分别 训练 ,然后将得到的分类器采用多数投票方法给出 预测类别. 实验表明 ,他们的方法能提高对稀有类样 本的识别率. Estabrook等人 [ 26 ]通过计算发现 ,根据 训练集的自然分布得到的分类器不一定具有最好的 一般化能力. 他们提出通过对原不平衡问题进行重 采样 ,从而构建多个平衡度不同的训练集 ,训练后采 用分类器挑选和偏向正类的原则将各个分类器综 合. 仿真实验表明 ,该方法比单独应用上采样和下采 样方法获得了更好的准确率和 ROC ( receiver oper2 ating characteristic)曲线. Chen等人 [ 27 ]提出了平衡 随机森林的方法 ,该方法对正类和反类分别进行重 采样 ,重采样多次后采用多数投票的方法进行集成 学习. Chawla等人 [ 28 ]将 boosting算法与 SMOTE算 法结合成 SMOTEBoost算法 ,该算法每次迭代使用 SMOTE生成新的样本 ,取代原有 AdaBoost算法中队 样本权值的调整 ,使得 Boosting算法专注于正类中 的难分样本. L iu等人 [ 29 ]基于人脸识别的级联模型 提出了一种基于级联模型的不平衡数据分类方法 , 该方法通过逐步筛掉反类样本 ,使得级联结构中后 面的结点得到更为平衡的训练集. Zhou和 L iu [ 30 ]提 出了代价敏感神经网络与分类器集成相结合的方 法 ,他们通过 21个 UCI标准数据集的实验发现 ,分 类器集成不仅对处理 2类不平衡问题有效 ,而且对 多类不平衡问题同样有效. 2. 4 代价敏感学习方法 在大部分不平衡分类问题中 ,稀有类是分类的 重点. 在这种情况下 ,正确识别出稀有类的样本比识 别大类的样本更有价值. 反过来说 ,错分稀有类的样 本需要付出更大的代价. 代价敏感学习 [ 31 ]赋予各个 类别不同的错分代价 ,它能很好地解决不平衡分类 问题. 以两类问题为例 ,假设正类是稀有类 ,并具有 更高的错分代价 ,则分类器在训练时 ,会对错分正类 样本做更大的惩罚 ,迫使最终分类器对正类样本有 更高的识别率. Dom ingos [ 32 ]提出了一种 Metacost方法 ,该方法 通过估计训练样本的后验概率密度 ,结合代价矩阵 ( cost matrix)计算每个训练样本的理想类别 ,然后根 据理想类别修改原训练样本的类别 ,得到新的训练 集 ,最后使用基于错误率的分类器学习这个新的训 练集. 仿真实验表明 ,Metacost比下采样和上采样方 法能获得更低的错误代价. Metacost的重要意义在 于它能将普通的基于准确率的学习方法容易地改造 成对错分代价敏感的学习方法. Chen [ 27 ]在平衡随机 森林的基础上提出了带权随机森林算法 ,该方法赋 予每个类一个权值 ,训练样本最少的类赋予的权值 最大. 在构造决策树的过程中引入权值 ,每一棵决策 树的决策采用带权多数投票. 最后所有的决策树采 用带权投票集成. Che等人 [ 33 ]通过训练集先验信息 的分析 ,利用支持向量机为不同类的样本设置惩罚 系数. 给不同的训练样本赋予不同的权值也能起到代 价敏感学习的作用. Fan等人 [ 34 ]提出了一种 AdaCost 算法 ,该算法通过在 Boosting算法的权值更新规则中 引入每个训练样本的错分代价 ,提高了 Boosting算法 对稀有类的查全率和查准率.该算法的权值更新原则 是:如果错分代价较大的样本被弱分类器错分 ,则它 对应的权值被“较大 ”地增加. 如果它被正确分类 ,则 它对应的权值被“较小 ”程度地减少. Joshi等人 [ 35 ]通 过研究发现 ,如果 AdaCost算法中的基分类器能获得 较平衡的查全率和查准率 ,则 AdaCost能获得对稀有 类较平衡的查全率和查准率. 代价敏感学习能有效地提高稀有类的识别率. 但问题是 ,一方面 ,在多数情况下 ,真实的错分代价 很难被准确地估计 [ 36 ] . 另一方面 ,虽然许多分类器 可以直接引入代价敏感学习机制 ,如支持向量机和 决策树 ,但是也有一些分类器不能直接使用代价敏 第 2期 叶志飞 ,等 :不平衡分类问题研究综述 ·151·

152· 智能系统学报 第4卷 感学习，只能通过调整正负样本比例或者决策阈值 器对稀有类有更高的识别率 间接地实现代价敏感学习)，这样不能保证代价敏 Hong等人I在ROC曲线下面积AUC(area 感学习的效果 under curve)指标的基础上，定义了LOO-AUC 25特征选择方法 (leaveone-out area under curve).LOO-AUC借鉴交 特征选择方法对于不平衡分类问题同样具有重 叉验证的方法，每次移除一个样本，利用剩余样本训 要意义.样本数量分布很不平衡时，特征的分布同样 练的分类器预测该样本.在核分类器模型采用正交 会不平衡.尤其在文本分类问题中，在大类中经常出 形式表示的基础上，Hong等人利用前向回归的更新 现的特征，也许在稀有类中根本不出现.因此，根据 规则，实现了LOO-AUC的快速计算.他们提出了一 不平衡分类问题的特点，选取最具有区分能力的特 种新的分类器最佳参数估计方法：正规正交带权最 征，有利于提高稀有类的识别率 小方差估计，并以最大化LOO-AUC作为模型选择 通过采用特征选择来解决不平衡分类问题主要 标准，实现了正交前向模型选择.实验表明，该方法 集中于自然语言处理领域.Cardie和Howe8以基 在生成数据和实际数据集上都能很好地处理不平衡 于事例学习(case based leaming)的框架为基础，提 问题 出了一种与测试样本相关的动态特征加权方法.该 一类学习(one-class leaming)1也被用于处理 方法首先利用训练集得到一棵决策树，然后计算每 不平衡问题.当样本数量不平衡时，并且当特征空间 个测试样本在测试路径上的信息收益，并以此计算 中混杂有大量噪音特征时，基于学习单一稀有类样 每个特征的权值，最后，从训练集中挑选k个与测 本的产生式模型，相比于学习两类问题的判别式模 试样本最接近的样本，并对他们测试类别进行投票： 型具有更好的性能叫 该方法在提高正类样本准确率的同时确保了总的准 3分类器评价指标 确率不下降.Zheng和Srihari91针对文本分类中存 在的不平衡分类问题，按照一个经验性的样本比例， 鉴于大类对准确率标准的影响大于稀有类，导 挑选正负2个样本集，分别从中选择最能表示该类 致稀有类的识别率难以提高，新的分类器评价指标 样本的特征集，然后将这些特征集合并作为最后挑 更注重稀有类对性能指标的影响。 选的特征.对不同规模的特征集进行特征挑选的仿 最常见的分类器评价指标是OC曲线，以及 真实验表明，该特征挑选方法能有效提高文本分类 ROC曲线下覆盖的面积AUC].ROC曲线和AUC 的F1测度 能够公平地对待稀有类和大类，与查准率和查全率 26其他方法 类似，ROC曲线可以在稀有类识别率和大类识别率 Wu和Chang 40提出了一种修改支持向量机核 之间做权衡。 函数矩阵(kemel matrix)方法，该方法通过将核函数 为了定义ROC曲线，需要用到机器学习方法的 矩阵进行保角变换(confomal transfomation),扩大 基础评价指标混淆矩阵（如表1所示）. 稀有类特征向量处的边界，从而增加正负类样本的 表1两类混淆矩阵 Table 1 A two-chass confusion matrix 分离度，减少大类的支持向量数目起到降低不平衡 度的效果.理论分析和仿真试验结果表明，该方法在 预测正类 预测反类 一些不平衡数据集上有比较好的效果 预测正类 TP N A runasalam和Chawla提出了一种自上而下 预测反类 FP N 的基于联合规则的分类器.他们指出，在处理不平衡 在一个两类混淆矩阵中，实际为正类，预测也为 分类问题时，传统的支持度和可信度在筛选关联规 正类的样本数量称为正确正类TP(true positive); 则时存在缺陷，并提出了补集类支持度(comp le- 实际为正类，预测为反类的称为错误反类N(false ment class support)作为挑选关联规则的重要指标. negative);实际为反类，预测为正类的称为错误正类 通过自上而下地将筛选出的最佳关联规则逐一添加 FP(false positive);实际为反类，预测为反类的称为 到决策树中，形成最终的分类器.实验结果表明，该 正确反类N(true negative) 方法在不平衡数据上比传统的基于联合规则的分类 利用混淆矩阵可以定义常用的分类器评价指 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. htp://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 感学习 ,只能通过调整正负样本比例或者决策阈值 间接地实现代价敏感学习 [ 37 ] ,这样不能保证代价敏 感学习的效果. 2. 5 特征选择方法 特征选择方法对于不平衡分类问题同样具有重 要意义. 样本数量分布很不平衡时 ,特征的分布同样 会不平衡. 尤其在文本分类问题中 ,在大类中经常出 现的特征 ,也许在稀有类中根本不出现. 因此 ,根据 不平衡分类问题的特点 ,选取最具有区分能力的特 征 ,有利于提高稀有类的识别率. 通过采用特征选择来解决不平衡分类问题主要 集中于自然语言处理领域. Cardie和 Howe [ 38 ]以基 于事例学习 ( case based learning) 的框架为基础 ,提 出了一种与测试样本相关的动态特征加权方法. 该 方法首先利用训练集得到一棵决策树 ,然后计算每 个测试样本在测试路径上的信息收益 ,并以此计算 每个特征的权值 ,最后 , 从训练集中挑选 k个与测 试样本最接近的样本 ,并对他们测试类别进行投票. 该方法在提高正类样本准确率的同时确保了总的准 确率不下降. Zheng和 Srihari [ 39 ]针对文本分类中存 在的不平衡分类问题 ,按照一个经验性的样本比例 , 挑选正负 2个样本集 ,分别从中选择最能表示该类 样本的特征集 ,然后将这些特征集合并作为最后挑 选的特征. 对不同规模的特征集进行特征挑选的仿 真实验表明 ,该特征挑选方法能有效提高文本分类 的 F1测度. 2. 6 其他方法 W u和 Chang [ 40 ]提出了一种修改支持向量机核 函数矩阵 ( kernel matrix)方法 ,该方法通过将核函数 矩阵进行保角变换 ( conformal transformation) , 扩大 稀有类特征向量处的边界 ,从而增加正负类样本的 分离度 ,减少大类的支持向量数目 ,起到降低不平衡 度的效果. 理论分析和仿真试验结果表明 ,该方法在 一些不平衡数据集上有比较好的效果. A runasalam和 Chawla [ 9 ]提出了一种自上而下 的基于联合规则的分类器. 他们指出 ,在处理不平衡 分类问题时 ,传统的支持度和可信度在筛选关联规 则时存在缺陷 ,并提出了补集类支持度 ( comp le2 ment class support)作为挑选关联规则的重要指标. 通过自上而下地将筛选出的最佳关联规则逐一添加 到决策树中 ,形成最终的分类器. 实验结果表明 ,该 方法在不平衡数据上比传统的基于联合规则的分类 器对稀有类有更高的识别率. Hong等人 [ 41 ]在 ROC曲线下面积 AUC ( area under curve ) 指 标 的 基 础 上 , 定 义 了 LOO2AUC ( leave2one2out area under curve). LOO2AUC借鉴交 叉验证的方法 ,每次移除一个样本 ,利用剩余样本训 练的分类器预测该样本. 在核分类器模型采用正交 形式表示的基础上 , Hong等人利用前向回归的更新 规则 ,实现了 LOO2AUC的快速计算. 他们提出了一 种新的分类器最佳参数估计方法 :正规正交带权最 小方差估计 , 并以最大化 LOO2AUC作为模型选择 标准 ,实现了正交前向模型选择. 实验表明 ,该方法 在生成数据和实际数据集上都能很好地处理不平衡 问题. 一类学习 (one2class learning) [ 42 ]也被用于处理 不平衡问题. 当样本数量不平衡时 ,并且当特征空间 中混杂有大量噪音特征时 ,基于学习单一稀有类样 本的产生式模型 ,相比于学习两类问题的判别式模 型具有更好的性能 [ 19 ] . 3 分类器评价指标 鉴于大类对准确率标准的影响大于稀有类 ,导 致稀有类的识别率难以提高 ,新的分类器评价指标 更注重稀有类对性能指标的影响. 最常见的分类器评价指标是 ROC曲线 ,以及 ROC曲线下覆盖的面积 AUC [ 43 ] . ROC曲线和 AUC 能够公平地对待稀有类和大类 ,与查准率和查全率 类似 , ROC曲线可以在稀有类识别率和大类识别率 之间做权衡. 为了定义 ROC曲线 ,需要用到机器学习方法的 基础评价指标 ———混淆矩阵 (如表 1所示 ). 表 1 两类混淆矩阵 Table 1 A two2cla ss confusion ma tr ix 预测正类 预测反类 预测正类 TP FN 预测反类 FP TN 在一个两类混淆矩阵中 ,实际为正类 ,预测也为 正类的样本数量称为正确正类 TP ( true positive) ; 实际为正类 ,预测为反类的称为错误反类 FN ( false negative) ;实际为反类 ,预测为正类的称为错误正类 FP (false positive) ; 实际为反类 ,预测为反类的称为 正确反类 TN ( true negative). 利用混淆矩阵可以定义常用的分类器评价指 ·152· 智 能 系 统 学 报 第 4卷

第2期 叶志飞等：不平衡分类问题研究综述 ·153· 标，如表2所示 本.采用一对其他分解策略把其中第11类的487个 表2常用评价指标 样本作为正例，其余作为负例，构成一个不平衡的两 Table 2 Common evaluation metrics 类问题」 名称 计算方法 Pak蛋白质亚细胞定位数据，是一个典型的 平衡准确率BA (TP/(TP+FN)+IN/(IN +FP))/2 生物信息学模式分类问题.它总共有7579条蛋白 查全率TPR TP/(TP+FN) 质序列，分布在12个不同的亚细胞位置上，有些位 查准率 TP/(TP+FP) 置上的蛋白质数量很不平衡.最多的位置上有1932 误警率FPR FP/(FP+IN) 条序列，而最少的位置只有40条.同样采用一对其 2 XR XP/(R +P) 他分解策略，把其中细胞外的861条作为正例，其余 F1测度 的作为负例，构成一个不平衡的两类分类问题 几何平均 R XP Roofiop!6数据是一个不平衡的场景识别问题 ROC曲线的X轴表示FPR,轴表示TPR.ROC 它总共包括1782张图片，其中只有781张图片被 曲线上的一组点是通过调整分类器决策阈值得到 标注成正例（屋顶照片），其余的17048张图片都是 的，OC曲线越凸越靠近左上方，表示对应的分类 负例 器一般化能力越强.AUC(area under curve)是指 上述3个数据集的概况如表3所示，其中训练 ROC曲线下面包括的面积，即ROC曲线的积分， 集和测试集是按照6：4的比例随机划分得到的 AUC能以定量的方式表示该ROC曲线对应的分类 分类器性能的评价指标采用ROC曲线、AUC 器的一般化能力.然而需要指出的是，ROC和AUC 以及ROC曲线与对角线交点处的TPR、NR(即1- 仅适合于两类问题，对多类问题，无法直接应用 FPR)和平衡准确率BA 查准率(Precision)和查全率(Recall)是信息检 图I给出了Pak数据上几种方法的ROC曲 索与数据挖掘中常用的评价指标.许多系统将两者 线.从图中可以看出，M3-SM具有最好的分类性 同时考虑，如Fl测度和几何平均(Gmeans),它们 能，CM的方法仅次于M3-SM,而C5.0方法效 都同等看待Precision和Recall对分类器评测的贡 果最差.使用9MOTE采样方法前后，CSM和C5.0 献.Josh比较系统地研究了包括F1和Gmeans 对应的ROC曲线非常接近，说明9MOTE采样在 在内的多种标准，通过分析Precision,.Recall和训练 Park数据上没有明显的效果 样本不平衡度的关系得出结论，在不平衡度不是很 1.0 大的情况下，F1和Gmeanst可以作为较好的评测指 标.但当训练样本很不平衡时，F1比Gmean要好. 0.8 J0sh指出，当测试集和训练集不是同分布或不同类 年0.6 的错分代价不同时，使用ROC曲线比较不同分类器 0.4 的性能更合适 C5.0 -C5.0+SMOTE 0.2 CSVM 4几种主要学习方法的性能比较 CSVM+SMOTE M3-SVM 0 在实验中，选取了4种比较具有代表性的学习 0.2 0.40.6 0.81.0 报警率 方法，它们分别是，代价敏感学习的决策树算法 (C50)、代价敏感的支持向量机(CSM)、 图1Park数据的ROC曲线 Fig 1 ROC curves for Park data 9MOTE采样法、以及结合训练集划分与分类器集 表33种数据集的概况 成的最小最大模块化支持向量机M3-SM)2] Table 3 Three i balnced da ta sets 实验使用了来自3个不同领域的不平衡数据 集.Abalone是UCI标准数据集中比较难分的一个 名称正类样本数负类样本数正负样本数比 Roofop 781 17048 1:218 数据集，类间重叠程度较大，各种分类器在它上面的 Park 861 6718 1:78 效果都不是很理想.它总共有29个类，4177个样 Ababne 487 3690 1:76 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. htip://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 标 ,如表 2所示. 表 2 常用评价指标 Table 2 Comm on eva lua tion m etr ics 名 称 计算方法 平衡准确率 BA ( TP / ( TP + FN) + TN / ( TN + FP) ) /2 查全率 TPR TP / (TP + FN) 查准率 TP / (TP + FP) 误警率 FPR FP / ( FP + TN) F1测度 2 ×R ×P / (R + P) 几何平均 R ×P ROC曲线的 X轴表示 FPR, Y轴表示 TPR. ROC 曲线上的一组点是通过调整分类器决策阈值得到 的 , ROC曲线越凸越靠近左上方 ,表示对应的分类 器一般化能力越强. AUC ( area under curve )是指 ROC曲线下面包括的面积 ,即 ROC曲线的积分 , AUC能以定量的方式表示该 ROC曲线对应的分类 器的一般化能力. 然而需要指出的是 , ROC和 AUC 仅适合于两类问题 ,对多类问题 ,无法直接应用. 查准率 (Precision)和查全率 (Recall)是信息检 索与数据挖掘中常用的评价指标. 许多系统将两者 同时考虑 ,如 F1测度和几何平均 ( G2means) ,它们 都同等看待 Precision和 Recall对分类器评测的贡 献. Joshi [ 44 ]比较系统地研究了包括 F1和 G2means 在内的多种标准 ,通过分析 Precision, Recall和训练 样本不平衡度的关系得出结论 ,在不平衡度不是很 大的情况下 , F1和 G2means可以作为较好的评测指 标. 但当训练样本很不平衡时 , F1比 G2mean要好. Joshi指出 ,当测试集和训练集不是同分布或不同类 的错分代价不同时 ,使用 ROC曲线比较不同分类器 的性能更合适. 4 几种主要学习方法的性能比较 在实验中 ,选取了 4种比较具有代表性的学习 方法 ,它们分别是 ,代价敏感学习的决策树算法 (C5. 0 )、代 价 敏 感 的 支 持 向 量 机 ( CSVM )、 SMOTE [ 14 ]采样法、以及结合训练集划分与分类器集 成的最小最大模块化支持向量机 (M32SVM) [ 23 ] . 实验使用了来自 3个不同领域的不平衡数据 集. Abalone是 UCI标准数据集中比较难分的一个 数据集 ,类间重叠程度较大 ,各种分类器在它上面的 效果都不是很理想. 它总共有 29个类 , 4 177个样 本. 采用一对其他分解策略把其中第 11类的 487个 样本作为正例 ,其余作为负例 ,构成一个不平衡的两 类问题. Park [ 45 ]蛋白质亚细胞定位数据 ,是一个典型的 生物信息学模式分类问题. 它总共有 7 579条蛋白 质序列 ,分布在 12个不同的亚细胞位置上 ,有些位 置上的蛋白质数量很不平衡. 最多的位置上有 1 932 条序列 ,而最少的位置只有 40条. 同样采用一对其 他分解策略 ,把其中细胞外的 861条作为正例 ,其余 的作为负例 ,构成一个不平衡的两类分类问题. Rooftop [ 46 ]数据是一个不平衡的场景识别问题 , 它总共包括 17 829张图片 ,其中只有 781张图片被 标注成正例 (屋顶照片 ) ,其余的 17 048张图片都是 负例. 上述 3个数据集的概况如表 3所示 ,其中训练 集和测试集是按照 6: 4的比例随机划分得到的. 分类器性能的评价指标采用 ROC曲线、AUC 以及 ROC曲线与对角线交点处的 TPR、TNR (即 12 FPR)和平衡准确率 BA. 图 1给出了 Park数据上几种方法的 ROC曲 线. 从图中可以看出 , M32SVM 具有最好的分类性 能 , CSVM的方法仅次于 M32SVM,而 C5. 0方法效 果最差. 使用 SMOTE采样方法前后 , CSVM和 C5. 0 对应的 ROC 曲线非常接近 ,说明 SMOTE 采样在 Park数据上没有明显的效果. 图 1 Park数据的 ROC曲线 Fig. 1 ROC curves for Park data 表 3 3种数据集的概况 Table 3 Three im ba lanced da ta sets 名 称 正类样本数 负类样本数 正负样本数比 Rooftop 781 17 048 1∶21. 8 Park 861 6 718 1∶7. 8 Abalone 487 3 690 1∶7. 6 第 2期 叶志飞 ,等 :不平衡分类问题研究综述 ·153·

·154· 智能系统学报 第4卷 表4各种方法的性能比较 Table 4 Performance com parison of different methods % 数据集 方法 TPR INR BA AUC C5.0 785 802 799 8743 CSVM 80.3 818 81.1 87.98 Rooftop C5 0+MMOTE 79.9 801 800 8822 CSVM SMOTE 81.3 804 809 8787 M3-SVM 816 81.4 815 8928 C5.0 826 858 842 9039 CSVM 849 85.5 85.2 9393 Park C5 0 SMOTE 843 83.8 842 9096 CSVM SMOTE 85.4 85.1 853 9410 M3-SVM 87.2 87.7 87.5 9454 C50 615 59.6 606 6684 CSVM 59.0 588 589 6425 Ababne C5 0 SMOTE 645 624 635 6953 CSVM SMOTE 627 63.3 630 6800 M3 SVM 675 664 6707267 表4给出了在3个数据集上其他的分类器性能 2类问题的方法解决.另外目前没有针对多类不平 指标.从该表可以得到下面一些观察结果 衡分类问题的公认评价指标，ROC和AUC不能直 1)仅用代价敏感的SVM和决策树算法在解决 接运用于多类问题，因此迫切需要提出针对多类不 不平衡问题时效果较差，两者的性能差异不大，因数 平衡分类问题的评价指标和相应的学习算法.迄今 据集的不同而变化.在Roofop数据上两者性能相 为止，不平衡模式分类问题的理论研究成果很少，以 近，在Pak数据上CSM略好于决策树C5.0,而在 上的研究多是依据实验的方法，所得到的结果也多 Abalone数据上.C5.0优于CSM 是经验性的.因此进一步的理论分析非常重要。 2)在多数情况下SMOTE采样的方法对分类精 参考文献： 度有所提高.但有时却没有什么效果甚至导致性能 下降，如在Roofiop数据上，MOTE采样后的数据经 [1]KUBATM,HOLTE B C,MATW N S Machine leaming for CSM分类比采样前分类效果反而下降 the detection ofoil spills in satellite radar mages[J].Ma- chine Leaming,1998,30(2):195-215 3)结合数据集划分和分类器集成思想的M3- [2 CHAN P K,STOLFO S J.Toward scalable leaming with SM表现出了最好最稳定的分类性能， non-unifom class and cost distributions a case study in 5结束语 credit card fraud detection[C]//Proceedings of the 4th In- temational Conference on Knowledge Discovery and Data 本文综述了不平衡分类问题的特征、问题点以 Mining New York:AAA I Press,1998:164-168 [3 ]CHOE W,ERSOYO K,B NA M.Neural netork schemes 及已有的几种主要解决方案和新的分类器评测指 for detecting rare events in human genom ic DNA [J]Bioin- 标.通过在3个不同领域的不平衡数据集上的实验， 6 matics,.2000,16(12):1062-1072 比较了决策树、支持向量机、代价敏感学习、采样方 [4]PLANT C,BOHM C,BERNHARD T,et al Enhancing in- 法以及训练集划分结合分类器集成等方法的性能， stance-based classification with local density:a new algo- 实验结果表明，训练集划分结合分类器集成的方法 rithm or classifying unbalanced biomedical data[J]Biin- 6 matics,2006,22(8):981-988 在处理不平衡问题时具有最好的效果.目前研究不 [5]WEISS G M.Leaming with rare cases and sall disjuncts 平衡模式分类问题都是基于不平衡的两类问题，即 [C]//Proceedings of the 12th Intemational Conference on 使是不平衡的多类问题，也是通过将原问题分解成 Machine Leaming San Francisco:Morgan Kaufnann, 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 表 4 各种方法的性能比较 Table 4 Performance com par ison of d ifferen t m ethods % 数据集 方法 TPR TNR BA AUC Rooftop C5. 0 CSVM C5. 0 + SMOTE CSVM + SMOTE M3 2 SVM 78. 5 80. 3 79. 9 81. 3 81. 6 80. 2 81. 8 80. 1 80. 4 81. 4 79. 9 81. 1 80. 0 80. 9 81. 5 87. 43 87. 98 88. 22 87. 87 89. 28 Park C5. 0 CSVM C5. 0 + SMOTE CSVM + SMOTE M3 2 SVM 82. 6 84. 9 84. 3 85. 4 87. 2 85. 8 85. 5 83. 8 85. 1 87. 7 84. 2 85. 2 84. 2 85. 3 87. 5 90. 39 93. 93 90. 96 94. 10 94. 54 Abalone C5. 0 CSVM C5. 0 + SMOTE CSVM + SMOTE M3 2 SVM 61. 5 59. 0 64. 5 62. 7 67. 5 59. 6 58. 8 62. 4 63. 3 66. 4 60. 6 58. 9 63. 5 63. 0 67. 0 66. 84 64. 25 69. 53 68. 00 72. 67 表 4给出了在 3个数据集上其他的分类器性能 指标. 从该表可以得到下面一些观察结果 : 1)仅用代价敏感的 SVM和决策树算法在解决 不平衡问题时效果较差 ,两者的性能差异不大 ,因数 据集的不同而变化. 在 Rooftop 数据上两者性能相 近 ,在 Park数据上 CSVM略好于决策树 C5. 0,而在 Abalone数据上 C5. 0优于 CSVM. 2)在多数情况下 SMOTE采样的方法对分类精 度有所提高. 但有时却没有什么效果甚至导致性能 下降 ,如在 Rooftop数据上 , SMOTE采样后的数据经 CSVM分类比采样前分类效果反而下降. 3)结合数据集划分和分类器集成思想的 M32 SVM表现出了最好最稳定的分类性能. 5 结束语 本文综述了不平衡分类问题的特征、问题点以 及已有的几种主要解决方案和新的分类器评测指 标. 通过在 3个不同领域的不平衡数据集上的实验 , 比较了决策树、支持向量机、代价敏感学习、采样方 法以及训练集划分结合分类器集成等方法的性能. 实验结果表明 ,训练集划分结合分类器集成的方法 在处理不平衡问题时具有最好的效果. 目前研究不 平衡模式分类问题都是基于不平衡的两类问题 ,即 使是不平衡的多类问题 ,也是通过将原问题分解成 2类问题的方法解决. 另外目前没有针对多类不平 衡分类问题的公认评价指标 , ROC和 AUC不能直 接运用于多类问题 ,因此迫切需要提出针对多类不 平衡分类问题的评价指标和相应的学习算法. 迄今 为止 ,不平衡模式分类问题的理论研究成果很少 ,以 上的研究多是依据实验的方法 ,所得到的结果也多 是经验性的. 因此进一步的理论分析非常重要. 参考文献 : [ 1 ] KUBATM, HOLTE B C,MATW IN S. Machine learning for the detection of oil sp ills in satellite radar images[J ]. Ma2 chine Learning, 1998, 30 (2) : 1952215. [ 2 ] CHAN P K, STOLFO S J. Toward scalable learning with non2uniform class and cost distributions: a case study in credit card fraud detection[ C ] / /Proceedings of the 4 th In2 ternational Conference on Knowledge D iscovery and Data M ining. New York: AAA I Press, 1998: 1642168. [ 3 ]CHOE W , ERSOY O K,B INA M. Neural network schemes for detecting rare events in human genomic DNA [J ]. Bioin2 formatics, 2000, 16 (12) : 106221072. [ 4 ] PLANT C, BO¨HM C, BERNHARD T, et al. Enhancing in2 stance2based classification with local density: a new algo2 rithm for classifying unbalanced biomedical data[J ]. Bioin2 formatics, 2006, 22 (8) : 9812988. [ 5 ]W EISS G M. Learning with rare cases and small disjuncts [C ] / / Proceedings of the 12 th International Conference on Machine Learning. San Francisco: Morgan Kaufmann, ·154· 智 能 系 统 学 报 第 4卷

第2期 叶志飞，等：不平衡分类问题研究综述 ·155· 1995:558-565 SVM's a case study [C]//Intemational Conference on [6 WEISS GM,H RSH H.A quantitative study of sall dis- Machine Leaming Washington DC,2003:65-71. juncts[C]//Proceedings of the 17th National Conference on [20]ESTABROOKS A,JAPKOW CZ N.A m ixture-of-experts A rtific ial Intelligence Texas:AAA I Press,2000:665- framework for leaming from unbalanced data sets[C]// 670 Proceedings of the 4th Intelligent Data Analysis Confer [7 WEISS GM.Mining with rarity:a unifying framework[J]. ence L isbon,Portugal,2001:34-43 Sigkdd Expbrations,2004,6(1):7-19 [21]AN R,LU Y,JN R,et al On predicting rare classes [8 ]JAPKOW CCZ N,STEPHEN S The class ibalance prob- with SVM ensembles in scene classification [C]//IEEE In- lem:a systematic study[J].Intelligent Data Analysis Jour temational Conference on Acoustics,Speech and Signal nal2002,6(5):429-450 Processing Hong Kong,2003:21-24. [9]ARUNASALAM B,CHAWLA S CCCS:a top down associ- [22 ]LU BL,IIO M.Task decomposition and module combina- ative classifier for m balanced class distribution [C]//Inter tion based on class relations a modular neural netork for national Conference on Knowledge Discovery and Data M in- pattem classification[J].IEEE Transaction on NeuralNet- ing New York:ACM Press,2006:517-522 w0ks,1999,10(5):1244-1256 10]DRUMMOND C,HOLTE R Explicitly representing ex- [23 ]LU BL,WANG KA,UTIYAMA M,et al A part-versus- pected cost an altemative o ROC representation [C]// part method ormassively parallel training of support vecor Proceedings of the 6th ACM SIGKDD Intemational Confer machines C ]//Proceedings of 17th Intemational Joint ence on Knowledge Discovery and Data Mining New Conference on NeuralNetorks Budapest Hungary,2004: York:ACM Press,2000:187-207. 735-740 [11]PROVOST F,FAWCETT T Robust classification for m- [24]YE Z F,LU B L Leaming mbalanced data sets with a precise envirorments[J]Machine Leaming.2001,42 m inmax modular support vector machine [C ]//Proceed- (3):203-231 ings of the 20th Intemational Joint Conference on Neural [12 ]DRUMMOND C.HOLTE R C C4 5,class ibalance, Netorks Orlando,USA,2007:1673-1678 and oost sensitivity:why under-sampling beats over-sam- [25 KOTSANTIS S B,PNTELAS P E Mixture of expert a- pling[C]//Intemational Conference on Machine Leaming gents for handling ibalanced data sets[J ]Annals of Washington DC,2003:152-154. Mathematics,Computing Teleinomatics,2003,1(1): [13 ]L NG C,LIC Data mining or direct marketing problems 46-55 and solutions C ]//Proceedings of the 4th Intemational [26]ESTABROOK A,TAEHO J,JAPKOW ICZ N.A multip le Conference on Knowledge Discovery and Data M ing New resampling method or leaming from mbalanced data sets York:AAA I Press,1998:73-79. [J].Computatonal Intelligence,2004,20(1):18-36 [14]CHAWLA N V.BOW YER K W.HALL L O,et al [27]CHEN C,L AW A,BREMAN L.Using random forest SMOTE:synthetic m inority over-sampling technique [J]. leam mbalanced data [R No 666,Statistics Depart- Joumal ofA rtificial Intelligence Research,2002,16:321- ment,University of Calimia at Berkeley,2004 357 [28]CHAWLA N V,LAZAREV C A,HALL L O,et al [15 ]LEE SS Noisy replication in skewed binary classification SMOTEBoost:mp oving prediction of the m inority class in [J].Computational Statistics and Data Analysis,2000, boosting[C]//Proceedings of 7th European Conference on 34(2):165-191 Princples and Practice of Knowledge Discovery in Data- [16 ]KUBATM,HOTLE R,MA TW N S Leaming when nega- bases CavtatDubrovnik,Croatia,2003:107-119 tive examp les abound [C]//Proceedings of the 9th Europe- [29]L U X Y,WU J X,ZHOU Z H A cascade-based classifi- an Conference on Machine Leaming London:Springer- cation method for class-mbalanced data [J ]Joumal of Verlag.1997:146-153 NanJ ing University:Natural Science,2006,42 (2):148- [17]KUBAT M,MATW N S Addressing the curse of mbal- 155 anced training sets one-sided selection[C]//Poceedings [30 ]ZHOU Z H,LU X Y Training cost-sensitive neural net of the 14th Intemational Conference on Machine Leaming works with methods addressing the class mbalance poblem San Francisco:Morgan Kaufann,1997:179-186. [J].EEE Transaction on Knowledge and Data Engineer [18 ]CHEN X W,GERLACH B,CASASENT D.Pruning sup- mg2006,18(1):63-77 port vectors for mbalanced data classification [C ]//Pro- [31]PAZZAN IM,MERZ C,MURPHY P,et al Reducing ceedings of 18th Intemational Joint Conference on Neural m isc lassificaton costs[C]//Proceedings of the 11 th Inter Netorks Montreal,Quebec,Canada,2005:1883-1887. national Conference on Machine Leaming San Francisco, [19]RASKUTTIB,KOW ALCZYK A Extreme re-balancing for CA,US4,1994:217-225 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 1995: 5582565. [ 6 ]W EISS GM, H IRSH H. A quantitative study of small dis2 juncts[C ] / /Proceedings of the 17 th National Conference on A rtificial Intelligence. Texas: AAA I Press, 2000: 6652 670. [ 7 ]W EISS GM. M ining with rarity: a unifying framework[J ]. Sigkdd Exp lorations, 2004, 6 (1) : 7219. [ 8 ]JAPKOW ICZ N, STEPHEN S. The class imbalance p rob2 lem: a systematic study[J ]. IntelligentData Analysis Jour2 nal, 2002, 6 (5) : 4292450. [ 9 ]ARUNASALAM B, CHAWLA S. CCCS: a top down associ2 ative classifier for imbalanced class distribution [C ] / / Inter2 national Conference on Knowledge D iscovery and Data M in2 ing. New York: ACM Press, 2006: 5172522. [ 10 ]DRUMMOND C, HOLTE R. Exp licitly rep resenting ex2 pected cost: an alternative to ROC rep resentation [ C ] / / Proceedings of the 6 th ACM SIGKDD International Confer2 ence on Knowledge D iscovery and Data M ining. New York: ACM Press, 2000: 1872207. [ 11 ] PROVOST F, FAWCETT T. Robust classification for im2 p recise environments [ J ]. Machine Learning, 2001, 42 (3) : 2032231. [ 12 ]DRUMMOND C, HOLTE R C. C4. 5, class imbalance, and cost sensitivity: why under2samp ling beats over2sam2 p ling[C ] / / International Conference onMachine Learning. W ashington DC, 2003: 1522154. [ 13 ]L ING C,L I C. Data m ining for direct marketing p roblem s and solutions [ C ] / /Proceedings of the 4 th International Conference on Knowledge D iscovery and Data M ing. New York: AAA I Press, 1998: 73279. [ 14 ] CHAWLA N V, BOW YER K W , HALL L O, et al. SMOTE: synthetic m inority over2samp ling technique [J ]. Journal ofA rtificial Intelligence Research, 2002, 16: 3212 357. [ 15 ]LEE S S. Noisy rep lication in skewed binary classification [J ]. Computational Statistics and Data Analysis, 2000, 34 (2) : 1652191. [ 16 ]KUBATM, HOTLE R,MATW IN S. Learning when nega2 tive examp les abound[C ] / /Proceedings of the 9 th Europe2 an Conference on Machine Learning. London: Sp ringer2 Verlag, 1997: 1462153. [ 17 ] KUBAT M, MATW IN S. Addressing the curse of imbal2 anced training sets: one2sided selection [ C ] / /Proceedings of the 14 th International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 1997: 1792186. [ 18 ]CHEN X W , GERLACH B, CASASENT D. Pruning sup2 port vectors for imbalanced data classification [ C ] / /Pro2 ceedings of 18 th International Joint Conference on Neural Networks. Montreal,Quebec, Canada, 2005: 188321887. [ 19 ]RASKUTTIB, KOWALCZYK A. Extreme re2balancing for SVM’s: a case study [ C ] / / International Conference on Machine Learning. W ashington DC, 2003: 65271. [ 20 ] ESTABROOKS A, JAPKOW ICZ N. A mixture2of2experts framework for learning from unbalanced data sets[ C ] / / Proceedings of the 4 th Intelligent Data Analysis Confer2 ence. L isbon, Portugal, 2001: 34243. [ 21 ]AN R, L IU Y, J IN R, et al. On p redicting rare classes with SVM ensembles in scene classification[C ] / / IEEE In2 ternational Conference on Acoustics, Speech and Signal Processing. Hong Kong, 2003: 21224. [ 22 ]LU B L, ITO M. Task decomposition and module combina2 tion based on class relations: a modular neural network for pattern classification[J ]. IEEE Transaction on NeuralNet2 works, 1999, 10 (5) : 124421256. [ 23 ]LU B L, WANG KA, UTIYAMA M, et al. A part2versus2 part method formassively parallel training of support vector machines [ C ] / /Proceedings of 17 th International Joint Conference on NeuralNetworks. Budapest, Hungary, 2004: 7352740. [ 24 ] YE Z F , LU B L. Learning imbalanced data sets with a min2max modular support vector machine [ C ] / /Proceed2 ings of the 20 th International Joint Conference on Neural Networks. O rlando, USA, 2007: 167321678. [ 25 ] KOTSIANTIS S B, P INTELAS P E. M ixture of expert a2 gents for handling imbalanced data sets [ J ]. Annals of Mathematics, Computing & Teleinformatics, 2003, 1 (1) : 46255. [ 26 ] ESTABROOK A, TAEHO J, JAPKOW ICZ N. A multip le resamp ling method for learning from imbalanced data sets [J ]. Computational Intelligence, 2004, 20 (1) : 18236. [ 27 ]CHEN C, L IAW A, BREIMAN L. U sing random forest to learn imbalanced data [ R ]. No. 666, Statistics Depart2 ment, University of California atBerkeley, 2004. [ 28 ] CHAWLA N V, LAZAREV IC A, HALL L O, et al. SMOTEBoost: imp roving p rediction of the m inority class in boosting[C ] / /Proceedings of 7 th European Conference on Princip les and Practice of Knowledge D iscovery in Data2 bases. Cavtat2Dubrovnik, Croatia, 2003: 1072119. [ 29 ]L IU X Y, WU J X, ZHOU Z H. A cascade2based classifi2 cation method for class2imbalanced data [ J ]. Journal of NanJing University: Natural Science, 2006 , 42 ( 2) : 1482 155. [ 30 ] ZHOU Z H, L IU X Y. Training cost2sensitive neural net2 works with methods addressing the class imbalance p roblem [J ]. IEEE Transaction on Knowledge and Data Engineer2 ing, 2006, 18 (1) : 63277. [ 31 ] PAZZAN I M, MERZ C, MURPHY P, et al. Reducing m isclassification costs[C ] / /Proceedings of the 11 th Inter2 national Conference on Machine Learning. San Francisco, CA, USA, 1994: 2172225. 第 2期 叶志飞 ,等 :不平衡分类问题研究综述 ·155·

·156· 智能系统学报 第4卷 [32 ]DOM NGOS P METACOST:a generalmethod for making [42 ]SCHOLKOPF B,PLATT J C,TA YLOR J S,et al Esti- classifiers cost sensitive[C]//Proceedings of the 5th Inter mating the support of a high-dmensonal distribution [J] national Conference on Knowledge Discovery and Data Neural Computation,2001,13(7):1443-1472 Mining San Dieg,CA:ACM Press,1999:155-164 [43 ]BRADLEY A.The use of the area under the ROC curve in [33]CHE H G,BONGER R E,LM CC Dual-nu-support the evaluation ofmachine leaming algorithms[J].Pattem vector machine with eror rate and training size biasing Recognition,1997,30(7):1145-1159 [C]//Proceedings of the 25th IEEE Intemational Confer- [44 ]JOSHIM V.On evaluating perfomance of classifiers r ence on Acoustics,Speech and Signal Processing Salt rare classes [C]//Proceedings of the 2nd IEEE Intema- Lake City,USA:IEEE Press,2001:1269-1272 tional Conference on Data Mining Japan,2002:641-644 [34]FAN W,STOLFO J S,ZHANG J X.et al AdaCost mis- [45 ]PARK KJ,KANEH SA M Prediction of potein subcellu- classification cost-sensitive boosting [C]//Proceedings of lar locations by support vecpormachines using compositions the 16th Itemational Conference on Machine Leaming of am ino acids and am ino acid pairs[J ]Bioinfomatics, San Mateo,USA,1999:97-105. 2003,19(13):1656-1663 (35 ]JOSHIM V,AGARWAL R C,KUMAR V.Predicting [46 ]MALOOF M A.Leaming when data sets are mbalanced rare classes can boosting make any weak leamer strong and when costs are unequal and unknown C]//Intema- [C]//Proceedings of the 8th ACM SIGKDD Intemational tonal Conference on Machine Leaming Washington DC. Conference on Knowledge Discovery and DataM ining Ed- 2003:154-160 monton,Canada:ACM Press,2002:297-306 作者简介： [36 ]CHAWLA N V.C4.5 and mbalanced data sets:investiga- 叶志飞，男，1983年生，硕士，主要 ting the effect of sampling method,probabilistic estmate, 研究方向为统计机器学习和模式分类. and decision tree structure C]//Intemational Conference on Machine Leaming Washingbn DC,2003:125-130. [37 ]ELKAN C The foundation of cost-sensitive leaming[C]// Proceedings of the 17th Intemational Joint Conference on Artificial Intelligence Seattle,Washington,2001:239- 246 文益民，男，1969年生，博士后，副 [38 ]CARD IE C,HOW EN.mprovingm inority class predicting 教授，CCF高级会员，主要研究方向为 using case-specific feature weights[C]//Proceed ings of the 统计学习理论、生物信息学和图像处 14 th Intemational Conference on Machine Leaming San 理.发表学术论文20余篇」 Francisco:Morgan Kaufnann,1997:57-65. [39 ]ZHENG Z H,SR HAR I R Optmally combining positive and negative features for text categorization[C]//Itema- tional Conference on Machine Leaming Washington DC, 吕宝粮，男，1960年生，教授、博士 2003:241-245. 生导师、博士、EEE高级会员，主要研 [40 ]WU G,CHANG E Y.KBA:kemel boundary aligrment 究方向为仿脑计算理论与模型、神经网 considering mbalanced data distribution [J].IEEE Trans 络理论与应用、机器学习、模式识别 on Knowledge and Data Engineering,2005,17(6):786- 脑计算机接口、生物信息学与计算生 795 物学.己在EEE Trans Neural Net [41]HONG X,CHEN S,HARR IS C J.A kemel-based to- works,IEEE Trans Bmedical Engineering,Neural Netorks class classifier for ibalanced data sets[J].IEEE Trans- CCV等国际期刊和会议上发表学术论文80余篇. action on Neural Netorks,2007,18(1):28-41. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.hutp://ww.cnki.net

© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net [ 32 ]DOM INGOS P. METACOST: a generalmethod for making classifiers cost sensitive[C ] / /Proceedings of the 5 th Inter2 national Conference on Knowledge D iscovery and Data M ining. San D iego, CA: ACM Press, 1999: 1552164. [ 33 ] CHE H G, BONGER R E, L IM C C. Dual2nu2support vector machine with error rate and training size biasing [C ] / /Proceedings of the 25 th IEEE International Confer2 ence on Acoustics, Speech and Signal Processing. Salt Lake City, USA: IEEE Press, 2001: 126921272. [ 34 ] FAN W , STOLFO J S, ZHANG J X, et al. AdaCost: m is2 classification cost2sensitive boosting [ C ] / /Proceedings of the 16 th International Conference on Machine Learning. San Mateo, USA, 1999: 972105. [ 35 ] JOSH I M V, AGARWAL R C, KUMAR V. Predicting rare classes: can boosting make any weak learner strong [C ] / /Proceedings of the 8 th ACM SIGKDD International Conference on Knowledge D iscovery and DataM ining. Ed2 monton, Canada: ACM Press, 2002: 2972306. [ 36 ]CHAWLA N V. C4. 5 and imbalanced data sets: investiga2 ting the effect of samp ling method, p robabilistic estimate, and decision tree structure [ C ] / / International Conference on Machine Learning. W ashington DC, 2003: 1252130. [ 37 ]ELKAN C. The foundation of cost2sensitive learning[C ] / / Proceedings of the 17 th International Joint Conference on A rtificial Intelligence. Seattle, W ashington, 2001: 2392 246. [ 38 ]CARD IE C, HOW E N. Imp rovingminority class p redicting using case2specific feature weights[C ] / /Proceedings of the 14 th International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 1997: 57265. [ 39 ] ZHENG Z H, SR IHAR I R. Op timally combining positive and negative features for text categorization [ C ] / / Interna2 tional Conference on Machine Learning. W ashington DC, 2003: 2412245. [ 40 ]WU G, CHANG E Y. KBA: kernel boundary alignment considering imbalanced data distribution [J ]. IEEE Trans on Knowledge and Data Engineering, 2005, 17 ( 6) : 7862 795. [ 41 ]HONG X, CHEN S, HARR IS C J. A kernel2based two2 class classifier for imbalanced data sets[J ]. IEEE Trans2 action on Neural Networks, 2007, 18 (1) : 28241. [ 42 ] SCHO¨LKOPF B, PLATT J C, TAYLOR J S, et al. Esti2 mating the support of a high2dimensional distribution [J ]. Neural Computation, 2001, 13 (7) : 144321472. [ 43 ]BRADLEY A. The use of the area under the ROC curve in the evaluation of machine learning algorithm s[J ]. Pattern Recognition, 1997, 30 (7) : 114521159. [ 44 ]JOSH IM V. On evaluating performance of classifiers for rare classes[ C ] / /Proceedings of the 2nd IEEE Interna2 tional Conference on Data M ining. Japan, 2002: 6412644. [ 45 ] PARK K J, KANEH ISA M. Prediction of p rotein subcellu2 lar locations by support vectormachines using compositions of amino acids and amino acid pairs[J ]. Bioinformatics, 2003, 19 (13) : 165621663. [ 46 ]MALOOF M A. Learning when data sets are imbalanced and when costs are unequal and unknown [ C ] / / Interna2 tional Conference on Machine Learning. W ashington DC, 2003: 1542160. 作者简介 : 叶志飞 ,男 , 1983年生 ,硕士 ,主要 研究方向为统计机器学习和模式分类. 文益民 ,男 , 1969年生 ,博士后 ,副 教授 , CCF高级会员 ,主要研究方向为 统计学习理论、生物信息学和图像处 理. 发表学术论文 20余篇. 吕宝粮 ,男 , 1960年生 ,教授、博士 生导师、博士、IEEE高级会员 ,主要研 究方向为仿脑计算理论与模型、神经网 络理论与应用、机器学习、模式识别、 脑 —计算机接口、生物信息学与计算生 物 学. 已 在 IEEE Trans. Neural Net2 works, IEEE Trans. Bimedical Engineering,Neural Networks和 ICCV等国际期刊和会议上发表学术论文 80余篇. ·156· 智 能 系 统 学 报 第 4卷