第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·