不平衡数据集的代价敏感学习方法 外文翻译

不平衡数据集的代价敏感学习方法 Nguyen Thai-Nghe, Zeno Gantner, and Lars Schmidt-Thieme, Member, IEEE 摘要：类不平衡对于机器学习算法是一个挑战性的问题。当从高度不平衡的数据中学 习，大多数分类将被多数类的例子所压倒，所以漏报率总是很高。尽管研究人员已经介绍 了很多的方法来处理这个问题，包括重采样技术和成本敏感的学习（CSL） ，其中大多数是 集中在这些技术的一种。这项研究提出了两种实证方法处理 同时使用重采样和 CSL 的类 不平衡。第一种方法将几种采样技术与使用支持向量机（SVM）的 CSL 进行结合、比较。 第二种方法建议通过本地优化的成本比率（成本矩阵）使用 CSL。我们的实验结果关于来 自于 UCI 资料库的 18 不平衡数据集表明，第一种方法可以减少误分类成本，而第二种方 法可以提高分类器的性能。 一、绪论 二元分类问题中，类不平衡可描述为多数类通过一个重要因素在数量上超过了少数类。 这种现象出现在许多机器学习和数据挖掘应用，如信用卡欺诈检测，入侵检测，溢油检测， 疾病诊断和许多其他领域。多数分类器在监督机器学习中被设计以最大限度地提高他们的 模型的准确性。因此，当从不平衡数据中学习，它们通常被多数类的例子所压倒。降低这 样的分类(1, 2)的性能是最主要的问题。它也被认为是数据挖掘研究3 中的 10 个具有挑 战性的问题之一。 研究人员已经推出了许多技术来处理类不平衡，如总结1和2 。他们大多集中在数据 层面对操纵 （重采样的方法） ，数据层如4，5，6 ，7 ，8，9，10 中和分类层（内 部改变分类器） ，例如在11，12，13 ，14，15，16 ，17 ，18中。 一个相关的问题是成本敏感型的学习（CSL） 。过去，有不少出版物已将 CSL 应用于 决策树 （19， 20，21 ， 22）或朴素贝叶斯（23，24 ） 。此外，为了理解类失衡如 何影响 CSL，一些作者 CSL（ 21，25）申请时，分析分类器的行为（例如 C4.5 算法） 。 以前的作品还将在数据层的操作与分类层的修改（26， 27，28）结合起来。 虽然许多论文已经写了类不平衡问题，他们大多集中于两种重采样技术或 CSL。我们 的贡献包括同时利用重采样技术和 CSL 两种方法。 第一种方法中将几种采样技术与使用 SVM 作为基础分类 CSL 进行了结合与比较。具 体而言，在组合的第一步骤中，我们通过使用一些重采样技术，如 TLINK， RUS，ROS，SMOTE （我们将在下一节中解释这些方法）重新平衡数据集，下一 步，我们训练有素的 SVM 模型对这些数据集重新平衡。一步，我们训练 SVM 模型在数据 集重新平衡。SVM 的产出由 S 型函数进行拟合，依赖于由普拉特29得到的概率的方法。 最后，使用贝叶斯风险（有条件的风险）标准得到最低预期成本的最终的模型。 CSL 的第二种方法不是假设，我们知道在第一方法中学习前的成本比（或成本矩阵） 和以往其他工作（30，21，25 ）或设置的成本比通过对以往类分类的反转，我们把这 个数字视为一个超参数，优化本地，然后训练的最终模型。我们的实验关于来自 UCI 的 18 不平衡数据集表明这些方法是有用的。第一种方法有助于减少误分类成本而第二个方法有 助于 改善分类器的性能（例如 GMean 度量） 。 剩下的纸张安排如下：第二部分介绍了一些相关的工作;在第三部分中，我们总结了一 些通常是用来处理类失衡问题常见的技术;第四部分介绍了所提出的方法; 第五部分介绍了 数据集;第六节显示了实验结果 ;最后，第七节是结论。 2、相关工作 已被引入许多采样技术包括启发式或非启发式过采样（4，5 ） ， 欠采样（6，7 ） ， 和数据清洗规则，如消除“噪音”和“边缘”的例子（8910） 。这些工作重点在于数 据层技术。 其他研究人员集中于改变内部的分类，例如支持向量机，来处理类的不平衡，例如11， 12，13；14 采用集成学习来处理类的不平衡，而15 欠采样与集成方法结合起来；16 着重于将不同的再平衡启发式算法合并进 SVM 来解决不平衡类问题，而17和18 ，将 SVM 纳入增升的方法。 在 CSL，20介绍一个实例-用加权的方法诱发成本敏感的树；另外两种方法调查带有 决定树的 CSL (22, 23)，而24介绍了朴素贝叶斯的 CSL。这些研究引入了确定未知属 性如何选择进行测试的测试方案，为了尽量减少误分类成本和测试成本的总和。 此外，第一26应用少数合成过采样技术（SMOTE4 ）以平衡数据集，然后使用不同 成本的 SVM 建立的模型被提出13；2728应用一些常见的分类器（例如 C4.5，logistic 回归，贝氏机率）与采样技术，如随机欠采样，随机过采样， 简明最近邻规则8，威尔逊 的编辑最近邻规则10，特梅克的链接9，和 SMOTE。 不同与文献，不是只专注于数据采样或 CSL， 我们建议使用这两种技术。此外，我们 不承担固定成本比，既没有通过反转先验分布的少数和多数类之间比例设置成本比，相反， 我们在本地优化成本比。 3、处理类失衡 为了处理不平衡数据集，研究人员常常集中于数据层和分类层（1，2 ） 。在数据层， 共同的任务是类别分配的修改。在分类级别许多技术被引入，如内部操纵分类器，一个类 的学习，集成学习，和 CSL。 A.修改类的分类 随机过采样（ROS）是一个 用于平衡类分配非启发式的方法1，通过随机复制少数类 的例子，而随机欠采样（RUS ）随机地省去了多数类的例子。 简明最近邻规则（CNN）8是用来寻找一致的例子的子集。如果使用 1 近邻分类一个 子集 与 是一致的， 在 E 中正确分类的例子。E 978-1-4244-8126-2/10/$26.00 2010 IEEE 威尔逊的编辑最近邻规则（ENN）10 删除任何一类标签实例不同于三个最近邻中的 至少两个类。 特梅克链接（TLINK）9是一种用于清洗数据的方法。给出两个属于不同类的两个例 子 ， 是 和 的距离。若没有例子 如iej）（ jie,dij le 一对 被称作 TLINK。如果),(ji 有一个 2 个例子之间的 TLINK，然后其中之一是噪声或它们两者都是边界线的例子。我们 要使用 TLINK 作为欠采样方法，那么仅有的大部分例子都被删除。 单面选择（OSS）33 是一个首先套用 CNN 找到一个相一致的子集的欠采样的方法， 然后 TLINK 去除噪声和边缘的例子。 人造少数过采样技术（SMOTE）是一个通过 4产生一个新的人造少数例子来介绍过 采样的方法，通过在少数例子之间插值。此方法首先在近邻各少数民族的例子中查找 k； 接下来，它会随机选择一个最近的邻居。然后创建一个新的少数类样本沿着线段加入少数 类样本和其最近的邻居。 B、成本敏感性学习 (CSL) 大多数分类器假定的误分类成本（假阴性和假阳性的成本）是相同的。在大多数现实 世界的应用中，这种假设是不正确的。例如， 在客户关系管理， 邮寄给买家的费用低于成 本不邮寄给购房者19; 或误判非恐怖恐怖的成本远远低于实际恐怖分子携带炸弹飞行误判 的成本。另一个例子是癌症诊断：比误判误报严重得多，因为由于晚的诊断和治疗34癌 症患者可能会失去他们的生命。成本不一定是金钱，例如它可以是一个时间的浪费或严重 程度的病症30 。 本研究着重于二元分类问题;我们将表示阳性类（+或+1）作为少数， 和阴性类（或 1）作为大多数。设 是成本预测的例子属于 i 类的时候，其实它属于 j 类；成本矩),(jic 阵被定义于表。 给定的成本矩阵，如示例 x 可以被分类为类别 i 的预期成本最小，通过使用贝叶斯风 险准则：（有条件的风险）： 其中，P（j|x）是 x 作为 j 类分类例子的后验概率。假设我们没有正确分类的成本， 所以说成本矩阵可由成本比描述： CSL 的目的是建立一个模型，具有最小的误分类成本（总成本）： FN 和 FP数量分别为假阴性和假阳性的例子。 4、推荐的方法 建议的方法在 4 小节中描述：我们使用支持向量机（SVM）作为基础分类。使用网格 搜索，以确定最佳的超 SVM 和的 esampling 技术。方法 1： 采样技术与 CSL 的组合，称 为 S-CSL。 方法 2：通过优化本地成本比 使用 CSL，称作 CSL-OCRL。 A、支持向量机（SVM） 由 n 个例子(xi; yi )给定的数据集 ，其中 是输入功能和、 是目标类、Xxiiy 。SVM 预测一个新的例子 x 通过1,iy 其中 是一个核心函数，b 是偏置，i 被确定用来解决拉格朗日优化问题，),(ixk 这里 是一个差额变数， 是拉格朗日乘数， 是用户指定的超参数来表示误分类训iiC 练例子的惩罚。 对于非线形问题，核 k 用来最大限度地提高利润率分类超平面。两种常用的核函数有 多项式核 978-1-4244-8126-2/10/$26.00 2010 IEEE 和径向基函数的内核 B.超参数搜索 我们已搜索的最佳超参数 C，指数 p，在方程（5） ， （6） ， （7） 。首先， “原始搜索”两 个权力是用来识别一个很好的区域，然后“顺利搜索”围绕该地区进行35。图 1 描述了 该方法的细节。 此外，每个数据集有其自身的结构，所以欠采样和过采样的百分比也不同。这些百分 比也被视为超参数。对于过采样，我们搜索的百分比从 50,100，150两个类之间的均衡 分布。 同样，对于欠采样，我们还可以搜索的百分比从 10，20，30均衡分布。 图 1 超参数搜索优化度量 E 的一步是 C 值和一步是 RBF 内核价值 C.方法 1：结合采样与 CSL（ S-CSL） 我们将 4 种重采样技术与使用标准的 的 CSL 结合起来。这些技术包括非启发1sSVM 式（RUS ，ROS）和启发式欠 -过采样（TLINK，SMOTE） 。在第一步骤中， 我们把原始数 据集分为两个独立的训练集和测试集；然后，不同的采样百分比 的 4 种采样技术 被应用在训练上产生新的分布；接下来，我们进行新的培训 集超参数搜索（见图 1） ，就总成本（TC ）而言，以确定最佳的参数；在下一步，支持向量 机是基于最佳超参数发现的。支持向量机的输出均设有了 S 型函数 以得到后验概率；最2 后，我们在测试集使用贝叶斯风险标准来预测新的例子。详细描述在图 2 中，平均 5 倍交 叉验证结果。 大多数数据集不具有的成本比， 所以我们假设成本比率来自于集合 ，报告 的最终结果的平均值为这些比率的误分类成本。这也可以在其他许多研究（30，21 ， 25） 。 1、我们已经使用 Weka 中的 SMO，http:/www.cs.waikato.ac.nz/ml/weka/ 2、S 型函数有 2 个参数： 和 这些值可以是通过使用最大似然法29，但对于直接的确定，我们 将它们设置为 1 图 2、抽样与 CSL（CSL ）的组合 D.方法 2：CSL 通过优化本地成本比 在 S-CSL 方法中，我们假设未知的成本比率。我们尝试了不同的成本比率和平均的结 果。在本节中，我们将介绍一种方法，为分类提供最佳的成本比。在以前的作品中，成本 978-1-4244-8126-2/10/$26.00 2010 IEEE 比率由先验分布（7，31 ）反相，例如，成本比= 大多数例子 =少数例子。这种选择 导致柯尔莫哥洛夫 - 斯米尔诺夫统计性能指标 36。手部说，这几乎可以肯定是不合适的， 正是因为不考虑它是由在提出的问题的相对严重程度的错误分类的基础上的，但简单方便 的理由（36，32 ） 。在我们的方法中，我们把这个成本比作为一个超参数， 局部优化参 数（见图 3、我们使用这种搜索，因为在这项研究中的数据集并不是非常不平衡，我们的 初步实验表明，结果并不显着改进（在的 GMean 度量）当使用高的成本比。图 4 给出了 CSL-OCRL 方法。此方法几乎与 S-CSL 是相同的，我们刚刚学会的原始数据，并优化成本 比例的 GMean 度量 3。 3 在这项研究中，我们使用 GMean 作为一个评价指标，因为以前的作品中表现出 GMean 不平衡数据的情况下，是比较合适的（33，15 ，17 ，37） 。 ， TPR 和 TNR 是真正的阳性率和真阴性率。 图 3 局部优化的步长为 成本比 5、资料简介 我们已经从 UCI 库试验 18 不平衡数据集 ，如表 2 描述的。有些多类数据集使用一4 类静态方案被转换成二进制数据集。比例失调范围从 1.77（最低）至 64.03（最高）之间的 多数和少数的例子。由于每个数据集是由 4 种不同的采样技术，我们实际上已经尝试 90“数据集” ， 包括原有的。 表 2 资料简介 图 4 CSL 通过本地优化成本比 6、实验结果 A.方法 1（S-CSL）的结果 抽样方案是。例如，SM100 和 ROS200 分别表示 SMOTE 和 随机的 100和 200的过采样。我们已实施了 4 种组合，和他们相比，与其他三个 CSL 方法， 这是元成本（30） ，CSL 上的原始数据（19，由 CSL 表示）和 CSL 通过实例比 重（20，38，表示 CSW） 。图 5 显示了这些方法的成本比率和总费用的 5 个典型的结果 之间的关系。人们可以清楚地看到，当成本比例增大，我们的方法显着降低总成本。这巩 固了我们的初步研究39的结果 CSL 作为元学习方法和内部分类器（SVM 在这种情况下） 被类不平衡问题仍然影响。CSL 可以更好，如果它是由重新平衡数据集。 978-1-4244-8126-2/10/$26.00 2010 IEEE 表 III 中在长期的平均成本将 S-CSL 的结果与其他方法进行比较。对于每个数据集， 最后四列与其他（S-CSL）进行比较时。我们可以看到，在大多数情况下，经过重新采样 的平均误分类成本都减少。对于表中的每一行， 其中的粗体数字表示最好的结果，斜体数 字说明我们的组合优于元成本。我们报告的百分比抽样方法， 重新取样后，每个数据集和 比例失调。 图 5、成本率和总成本的 5 个典型的结果关系 CSL 与 RUS（RUS-CSL）的结合比其余的组合效果更好。另外，RUS-CSL 总是优于 元成本，CSL，和 CSW（DIS 数据集除外） 。表中的最后一行总结了每一种组合与其他 3 方法的比较结果。 此外， 当之前和之后的采样观察不平衡比率，结果表明，不仅是类的失衡，但也噪音， 边缘的例子，类重叠降低分类器的性能。这些问题，也有报道9，33 ，40。 表三 实验结果 - 平均成本的方法 1：S-CSL B.结果方法 2 - CSL-OCRL 表四，比较结果与其他 CSL 和元学习方法，这是 CSL 实例加权（CSW） （CSL- OCRL20，38 ） ， 元成本（ 30） ，阈值选择（38） ， 和 AdaBoost 的 CSL（41，42 ） 。 我们使用配对 t 检验显着性水平 0.05。我们使用 CSLOCRL 的方法作为基准，比较其他方 法反对。粗体的数字呈现在这些方法中最好的结果。人们可以清楚地看到，CSL-OCRL 几 乎总是等于， 或优于其他方法。 7、结论 当从不平衡数据学习，由多数类的分类通常是不堪重负，所以少数类的例子往往被错 误分类。连同采样技术和修改内部分类，CSL 也是一个重要的方法，因为它需要考虑到不 同的假阴性和假阳性误分类成本。 在这项研究中，我们提出了两种简单的方法来处理类不平衡。我们的方法的一个重要 特点是，我们不需要改变内部的分类，所以他们很容易实现。第一种方法将 CSL 与采样技 术结合，以减少总的误分类成本模型。实验结果表明，在大多数情况下，通过使用这样的 组合，误分类成本都降低。第二种方法（CSL-OCRL）优化本地成本的比例，这个比例应 用于训练模型。GMean 结果显示， CSL-OCRL 通常表现的像其他方法一样好，是显着优于 在某些情况下，一些方法。在未来，我们将研究如何结合 CSL 特征选择方法，调查类的大 978-1-4244-8126-2/10/$26.00 2010 IEEE 型数据集上的不平衡的影响。 感谢 第一作者是由“教学和科研创新资助”项目，越南芹苴大学 表四 实验结果-GMEAN 对于方法 2-CSL-OCRL 参考 1 N. V. Chawla, N. Japkowicz, and A. Kotcz, “Editorial: special issue on learning from imbalanced data sets,” SIGKDD Explorations, vol. 6, no. 1, pp. 16, 2004. 2 H. He and E. A. Garcia, “Learning from imbalanced data,” IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 9, pp. 12631284, September 2009. 3 Q. Yang and X. Wu, “10 challenging problems in data mining research,” International Journal of Information Technology and Decision Making, vol. 5, no. 4, pp. 597604, 2006. 4 N. V. Chawla, K. Bowyer, L. Hall, and W. P. Kegelmeyer, “SMOTE: synthetic minority over-sampling technique,” Journal of AI Research, vol. 16, pp. 321357, 2002. 5 A. Nickerson, N. Japkowicz, and E. Millos, “Using unsupervised learning to guide resampling in imbalanced data sets,” in Proceedings of the Eighth International Workshop on AI and Statitsics, 2001, pp. 261265. 6 P. Li, P.-L. Qiao, and Y.-C. Liu, “A hybrid re-sampling method for SVM learning from imbalanced data sets,” in Proceedings of the 2008 Fifth IC on Fuzzy Systems and Knowledge Discovery. Washington, DC, USA: IEEE Computer Society, 2008, pp. 6569. 7 B. Raskutti and A. Kowalczyk, “Extreme re-balancing for SVMs: a case study,” SIGKDD Explorations, vol. 6, no. 1, pp. 6069, 2004. 8 P. E. Hart, “The condensed nearest neighbor rule,” IEEE Trans. Inf. Theory, no. 16, pp. 515516, 1968. 9 I. Tomek, “Two modifications of CNN,” IEEE Transactions on Systems Man and Communications SMC-6, pp. 769772, 1976. 10 D. L. Wilson, “Asymptotic properties of nearest neighbor rules using edited data,” IEEE Transactions on Systems, Man and Cybernetics, no. 3, 1972. 11 X. wen Chen, B. Gerlach, and D. Casasent, “Pruning support vectors for imbalanced data classification,” proceeding of IEEE International Joint Conference on Neural Networks, vol. 3, pp. 18831888, 2005. 12 S. Lessmann, “Solving imbalanced classification problems with support vector machines,” in International Conference on Artificial Intelligence, 2004, pp. 214220. 13 K. Veropoulos, C. Campbell, and N. Cristianini, “Controlling the sensitivity of support vector machines,” in Proceedings of the IJCAI, 1999, pp. 5560. 14 R. Yan, Y. Liu, R. Jin, and A. Hauptmann, “On predicting rare classes with SVM ensembles in scene classification,” in ICASSP, 2003, pp. 2124. 15 X.-Y. Liu, J. Wu, and Z.-H. Zhou, “Exploratory under-sampling for class-imbalance learning,” IEEE Trans. on Syst, Man, and Cyber. Part B, pp. 539550, 2009. 16 Y. Tang, Y. Zhang, N. Chawla, and S. Krasser, “SVMs modeling for highly imbalanced classification.” IEEE Trans Syst Man Cybern B Cybern, vol. 39, no. 1, pp. 2818, 2009. 17 B. Wang and N. Japkowicz, “Boosting support vector machines for imbalanced data sets,” Knowledge and Information Systems, 2009. 978-1-4244-8126-2/10/$26.00 2010 IEEE 18 X. Li, L. Wang, and E. Sung, “AdaBoost with SVM-based component classifiers,” Eng. Appl. Artif. Intell., vol. 21, no. 5, pp. 785795, 2008. 19 C. Elkan, “The foundations of cost-senstive learning,” 17th International Joint Conference on Artificial Intelligence, pp. 973978, 2001. 20 K. M. Ting, “Inducing cost-sensitive trees via instance weighting,” in PKDD, 1998, pp. 139147. 21 X.-Y. Liu and Z.-H. Zhou, “The influence of class imbalance on costsensitive learning: An empirical study,” in Proceedings of the Sixth ICDM. Washington, DC, USA: IEEE Computer Society, 2006, pp. 970974. 22 S. Sheng, C. X. Ling, A. Ni, and S. Zhang, “Cost-sensitive test strategies,” in The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, 2006. 23 S. Sheng, C. X. Ling, and Q. Yang, “Simple test strategies for costsensitive decision trees,” in ECML, 2005, pp. 365376. 24 X. Chai, L. Deng, Q. Yang, and C. X. Ling, “Test-cost sensitive naive bayes classification,” in International Conference on Data Mining, 2004, pp. 5158. 25 K. M. Ting, “A study on the effect of class distribution using costsensitive learning,” in Discovery Science, 2002, pp. 98112. 26 R. Akbani, S. Kwek, and N. Japkowicz, “Applying support vector machines to imbalanced datasets,” in Proceedings of the 15th ECML, 2004, pp. 3950. 27 G. E. A. P. A. Batista, R. C. Prati, and M. C. Monard, “A study of the behavior of several methods for balancing machine learning training data,” SIGKDD Explorations, vol. 6, no. 1, pp. 2026, 2004. 28 J. Van Hulse, T. M. Khoshgoftaar, and A. Napolitano, “Experimental perspectives on learning from imbalanced data,” in Proceedings of 24th ICML. ACM, 2007, pp. 935942. 29 J. C. Platt, “Probabilistic outputs for SVM and comparisons to regularized likelihood methods,” in Advances in Large Margin Classifiers. MIT Press, 1999, pp. 6174. 30 P. Domingos, “Metacost: A general method for making classifiers costsensitive,” 5th ACM SIGKDD International conference on Knowledge Discovery and Data mining KDD1999, pp. 155164, 1999. 31 D. D. Margineantu, “When does imbalanced data require more than cost-sensitive learning?” in Workshop on Learning from Imbalanced Data, Artificial Intelligence (AAAI-2000), 2000. 32 D. J. Hand, “Classifier technology and the illusion of progress,” Statistical Science, vol. 21, no. 1, pp. 114, Jun 2006. 33 M. Kubat and S. Matwin, “Addressing the curse of imbalanced training sets: One-sided selection,” in Proceedings of the 14th ICML. Morgan Kaufmann, 1997, pp. 179186. 34 V. S. Sheng and C. X. Ling, “Thresholding for making classifiers costsensitive,” in AAAI, 2006. 35 C. W. Hsu, C. C. Chang, and C. J. Lin, A practical guide to support vector classification, Department of Computer Science and Information Engineering, National Taiwan Univ