不平衡数据集的神经网络阈值优化方法

不平衡数据集的神经网络阈值优化方法 李明方，张化祥，张 雯，计 华 LI Ming-fang，ZHANG Hua-xiang，ZHANG Wen，JI Hua 山东师范大学 信息科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院，济南 250014 School of Information Science and Engineering，Shandong Normal University，Jinan 250014，China E-mail:lmgc21713@yahoo.com.cn LI Ming-fang，ZHANG Hua-xiang，ZHANG Wen，et al.Approach to optimize threshold of ANN on imbalance datasets. Computer Engineering and Applications，2010，46(20):168-171. Abstract:The classification of imbalance datasets is a hot research area in the field of machine learning，and recently，many researchers have proposed several theories and algorithms to improve the performance of classical classification algorithms on imbalance datasets.One of the most important methods is adopting threshold selection criteria to determine the output threshold of an Artificial Neural Network(ANN).The commonly used threshold selection criteria have some drawbacks，such as failing to get optimal classification performances both on data in minority class and in majority class，only focusing on the classification accuracy of the majority class data.This paper proposes a new threshold selection criterion based on which， both the data in the minority class and majority class can reach optimal classification accuracies without the impact of the sample proportion.When the new threshold selection criterion is applied as a classifier evaluation criterion to classifiers trained using Artificial Neural Networks and Genetic approaches，good results can be obtained. Key words:imbalance datasets;threshold selection criterion;Artificial Neural Network(ANN);genetic method 摘 要:不平衡数据集分类为机器学习热点研究问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 之一，近年来研究人员提出很多理论和算法以改进传统分类技术在不平衡数据集上的性能，其中用阈值判定标准确定神经网络中的阈值是重要的方法之一。常用的阈值判定标准存在一定缺点，如不能 使少数类及多数类分类精度同时取得最好、过于偏好多数类的精度等。为此提出一种新的阈值判定标准，依据该标准能够使少 数类及多数类分类精度同时取得最好而不受样例类别比例的影响。以神经网络与遗传算法相结合训练分类器，作为阈值选择条 件和分类器的评价标准，新标准能够得到较好的结果。 关键词:不平衡数据集;阈值判定标准;神经网络;遗传算法 DOI:10.3778/j.issn.1002-8331.2010.20.047 文章编号:1002-8331(2010)20-0168-04 文献标识码:,中图分类号:TP18 [2] 。其中数据加工究方法主要是数据加工和算法改进两方面1 引言 技术通过重采样技术改变数据间的分布。如过采样、欠采样、 在机器学习和数据挖掘研究中，通常假定数据集是平衡 特征提取等。过采样通过复制少数类样例并添至原样例中提 的。然而这一假设在很多实际问题中不成立，很多情况下，数 高少数类的比重，欠采样通过删除部分多数类样例，缓解多数 [1]据类别严重不平衡，且少数类被错分的代价很大。对于不平 类和少数类的不平衡差距。文献[3]基于过采样技术提出了 衡数据集分类问题，理想情况是使多数类与少数类的准确率 SMOTE 方法。文献[4]认为在一定的条件下，针对类别重叠问 题，过采样技术优于欠采样技术。文献[5]提出在数据集存在 同时达到一个较大值，但此目标很难达到，算法通常以整体准 噪声的前提下，优先使用随机欠采样技术。文献[6]的特征提 确率作为评价标准，由于少数类样例所占比例较少，算法会忽 取方法是对少数类样例和多数类样例进行特征选择，然后再 略少数类而着重提高对多数类的分类性能。有时即使把少数 用相应的方法进行合并，从而达到提高分类器性能的目的。 类样例全部错分仍能保证较高的整体准确率，而人们通常更 通过数据加工技术改变原有数据分布存在着一定缺陷，过采 关注少数类的分类精度，因此提高算法对不平衡数据集的分 类性能成为机器学习和数据挖掘的一个重要研究方向，其研 基金项目:山东省科技研究 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 项目(the Science and Technologies Research Plan of Shandong Province，China under Grant No.2007ZZ17， 假设，而这一假设在不平衡数据集上并不成立，因此算法改进data[i]:当o[k] < ch[ j]时，data[i]为负类，反之为正类; ?重复?，判定data中每个样例的类别; 技术成为重要研究方向。许多学者在这方面做了大量工作， ?根据data中所有样例的类别计算每个样例的fitnes s值;文献[7]提出一种代价敏感算法在类别间设定不同的误分代价 ?重复?,?，直至每个ch都得到 fitness值; 并通过最小化所提出的误差代价公式来确定样例类别。文献 ?按照判定标准选择ch最优值，存入opch[k]; [7][8]在 MetaCost的基础上提出一种代价敏感决策方法，代价敏 ?进行交叉变异选择操作，形成新的pop; 感学习可以避免采样技术对数据分布造成的干扰。文献[9]将 ?迭代?,?1 000 次; 反向传播算法、Naïve Bayesian、决策树进行集成并应用于欺 ?得到opch[k]为最优值;[11] 诈检测研究。文献[10]在 AdaBoost的基础上提出三种代价 ?重复?,?直至每个输出单元得到计算。 敏感学习算法，并在现实医疗数据上取得较好效果。上述研 (4)根据所得到的每个输出单元的阈值opch[k]，在测试样 例上进行测试，输出单元采用多数投票的方式决定样例类别。 究结果表明，集成方法对不平衡数据具有较高的适应能力。 阈值方法也是当前主流算法之一，在 Bayes 网络、神经网络、 SVM 中广泛使用。它根据阈值把样例分到特定类别中去，其 中如何通过阈值判定函数确定阈值成为关键，阈值判定函数 3 阈值判定标准 是否合适直接影响到分类器的性能。 上面所述算法中，遗传算法的适应度函数对染色体(阈 目前针对不平衡数据集的分类仍存在很多问题有待解 值)的选择影响很大，进而影响整个分类算法的性能，因此适 决，主要问题有以下方面:(1)数据提取困难，各种取样方法存 应度函数的选择非常重要。能进行阈值判定的标准多种多 在缺陷;(2)评估标准选择困难，不同的评估标准从不同的角 样，文献[13]提出了若干阈值判定标准作为适应度函数。对于 度影响分类器性能;(3)分类算法选择困难，大多数算法偏好 给定变量TP(正例正确分类的个数)、FN(正例错误分类的个 于多数类精度，忽略少数类精度。在神经网络中，阈值方法通 数)、TN(负例正确分类的个数)及FP(负例错误分类的个数)， 常以分类性能的评价标准作为阈值判定函数，但很多评价标 TP 定义Sn = (正例正确分类占所有正例的样本的比例)TP + FN 准倾向于多数类的分类精度，并不适合不平衡数据集。因此 TN [13]对(2)、(3)方面问题在神经网络的基础上，借助遗传算法搜寻 (负例正确分类占所有负例的样本的比例)。及Sp = TN + FP 全局最优值的能力，针对阈值判定方法进行改进，提出新的阈 很明显，Sn Sp 0 - 1。Î[] 值选择标准公式，并通过理论证明及实验验证新标准的有效 [13] 定义 1 RI 标准性。本文仅考虑两类不平衡问题，并设定少数类样本为正类， |Sp Sn| - (1) RI = 类别值为 1，多数类样本为负类，类别值为0。 Sp + Sn RI 作为适应度函数使遗传算法优先选择使之趋向于 0 的 2 算法描述 阈值，但当Sn = Sp时，RI 取最小值 0，说明，当RI 达到最小值时， 反向传播算法是一种启发式学习算法，它采用梯度下降 并不能保证 Sn、Sp 同时达到最大值 1，也就不能保证少数类的 [12]方法试图最小化网络输出值和目标值之间的误差平方。在 分类正确率。[13]定义 2 P标准 二分类问题中，反向传播算法计算结果不一定是类别值，其对 负类的计算结果是接近 0 的一个正值，正类的计算结果是小于 = SpNn + SnNp P (2) 1 的一个值。因此需要确定一个阈值对计算结果进行类别判 其中，Nn为数据集中负例所占比例，Np为数据集中正例所占比 [13]例。 P 作为适应度函数使遗传算法优先选择使之趋向于 断。文献[14]提出的 MVGen 系统是在神经网络和遗传算法 (Nn + Np)的阈值，但当数据类别比例相差很大时，由P确定的 的基础上根据阈值判定标准确定阈值，这里对 MVGen 系统改 阈值倾向于提高负类的分类精度，忽略正类的准确率。 造以适应所使用的 UCI 数据集。算法如下: [13]定义 3 OP标准 初始设置，定义如下 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 :n为样本属性个数(不包含类 别);data为样例集合;o[k]为所有样例在第k个输出单元的输出 |Sp - Sn| OP = P - RI = SpNn + SnNp - (3) Sp + Sn 值数组;ch为阈值(染色体);pop为阈值种群集合;fitness为适 应度函数;opch为最优阈值(最优染色体)数组。神经网络以及 为克服RI 和P作为适应度函数时的缺陷，文献[13]将标准 遗传算法中的参数设置如下:隐藏层层数为 1，隐藏单元个数 RI 和标准P结合起来提出标准OP。以OP作为适应度函数使遗 为(n + 2)/2，输出层单元个数为n，隐藏层和输出层单元均为 传算法优先选择使之趋向于(Nn + Np)的阈值，这样既能避免 sigmoid单元;遗传算法种群数量为100 个，遗传代数为 1 000 Sn、Sp 在任意值取得相等值时RI 取得最小值的缺点，又可缓解 次，变异、交叉、选择操作采用二进制编码。 标准P对多数类的偏好。OP虽然在 MVGen 系统上取得了较 算法基本步骤如下: 好的结果，但是其参数Nn对公式性能存在较大影响，对于不平 (1)训练神经网络。 衡数据集来说，Nn值一般会远大于Np值。当OP作为适应度函 (2)根据阈值判定标准确定 fitness。 数求其最大值(Nn + Np)时，由于Nn较大，OP仍然会使分类器有 ORI = 1 - Sp1 - Sn+ (4) ()() Sp + Sn TP ×TN G - mean = (5) ORI 作为适应度函数使遗传算法优先选择使之趋向于 0 TP + FN FP + TN ()( ) 的阈值。- mean反映了算法对于两个类别的分类能力的平衡程度。 G 定理 1 在Sn Sp 0 1时，公式(4)存在唯一的最小值， - Î[] G mean的值越大说明分类器对两个类别的分类能力越好。- 且当公式(4)取得最小值时，Sn、Sp 分别取得最大值。 定义 6 F-measure ×Recall × Precision 2 证明 设Sn = x Sp = y ORI = f x y 则x [0 1] y [0 1]。 - - ÎÎ( ) = F - measure= Recall+ Precision 2y - ì 2 + y - 1 (x ? y)ï(6) 2 1/Recall+ 1/Precision ?f ( x y ) ( x + y) ï= fx y=( ) í x TP TP 2y ?x 其中，Recall = ，Precision= 。F - measure反映 + y - 1 (x > y)TP + FN TP + FP ï2 ïx + y( ) [10]î的是Recall和Precision的调和平均值。F - measure的值越大 2x ì + x - 1 (x ? y) 表明Recall和Precision的值越接近于 1。 为从实验上验证算2ïx + y ( )?f (x y) ï 法性能，采用 UCI 中的二类不平衡数 f(x y) == íy ?y -2x ï+ x - 1 (x > y)据集，使用F - measure、G - mean作为评价标准，采用十折交叉 2 ï x + y( ) î的方式进行验证，使用ORI 及OP分别作为遗传算法中的适应 当 x ? y 时，fx y< 0 ;故 f x y在 x ? y 区间内无极值,( ) ( ) x 度函数来确定阈值并利用神经网络进行分类。实验数据集描述 f ( x y) = 2 ，当 x=y 在端点处取得最值。当 x，y?0 时， lim 见表 1，实验结果见表 2，阈值分布见表 3，表 4 为 breast-cancer x 0 y ? 0 ? 2数据集的结果。 时，(f x，y)=(1-x)>0; 表 1 数据集描述 当 x>y 时，f(x，y)<0;故(f x，y)在 x>y 区间内无极值，在端y 2 点处取得最值。当 x?y 时，lim f ( x y) = (1 - y)> 0 ，当 x=1，y= 正例数量负例数量正负比属性个数(不含类别) x ? y 85 201 0.422 885 572 9 breast-cancer 1 时，(f x，y)=0; breast-w 241 458 0.526 200 873 9 故当 x=1，y=1 时，(f x，y)取得最小值 0。diabetes 268 500 0.536 000 000 8 由定理 1 可得出结论:ORI 标准中的多项式(1 Sp)(1 Sn)- - haberman 81 255 0.317 647 059 3 能避免 Sn、Sp 在任意值取得相等值时ORI 取得最小值;ORI 公 hepatitis 32 123 0.260 162 602 19 式关于 Sn、Sp 对称，不包含其他参数，避免了OP存在的受到类 tic-tac-toe 332 626 0.530 351 438 9 别比例影响的问题，不会对多数类产生偏好;当Sn Sp Î0 - 1[] measure、G mean作为衡量标 表 2 的实验结果表明，以F - - 时，ORI 有唯一最小值，当Sn = Sp = 1时，ORI 取得最小值 0。定 理 1 从理论上说明ORI 同OP 一样消除了RI 和P 的缺点，确保 准，ORI 在 4 个数据集 breast-cancer、diabetes、haberman、hepati- Sn、Sp 能够取得最优值1。 tis 上的性能优于OP，在 tic-tac-toe 数据集上的结果与OP相等， 在 breast-w 数据集的性能不如OP 。除 breast-w、tic-tac-toe之 外，ORI 将正例正确分类的数量(TP)高于OP，但是将负例错分 4 实验结果分析 为正例的数量(FP)高于或等于OP，表明ORI 更倾向于正例的 无论是衡量分类器性能还是指导构建分类器，分类器性 正确率，倾向于将位于分界面上的实例分为正例。在将负例 能评价标准都发挥着重要作用。通常最为常用的评价标准是 错分为正例的代价较小的情况下ORI， 的性能优于OP。但在 整体准确率，然而并不适用于不平衡数据，正如第 1 章所述，由 两类错分代价大致相等的情况下ORI 不如OP。 于少数类样例所占比例较少，算法会忽略少数类而着重提高 表 3 给出在 4 个数据集上神经网络输出单元的阈值分 对多数类的分类性能。有时即使把少数类样例全部错分仍能布。在设定少数类样本为正类且类别值为 1，多数类样本为负 表 2 实验结果 适应度函数TP TN FP FN F-measure G-mean Sn Sp OP 值 ORI 值 OP 33 151 50 52 0.392 0.540 0.388 0.751 0.324 0.470 breast-cancer ORI 37 136 65 48 0.396 0.543 0.435 0.677 0.387 0.400 OP 221 445 13 20 0.930 0.943 0.917 0.971 0.923 0.031 breast-w ORI 219 446 12 22 0.928 0.941 0.909 0.974 0.916 0.037 OP 188 374 126 80 0.646 0.724 0.701 0.748 0.699 0.107 diabetes ORI 191 372 128 77 0.651 0.728 0.713 0.744 0.711 0.095 OP 36 153 72 45 0.380 0.549 0.444 0.680 0.413 0.387 haberman ORI 37 153 72 44 0.389 0.557 0.457 0.680 0.429 0.370 OP 15 108 15 17 0.483 0.641 0.468 0.878 0.489 0.368 hepatitis ORI 23 101 22 9 0.597 0.768 0.719 0.821 0.733 0.117 0.390 687 0.353 820 0.332 771 0.317 480 0.337 710 0.328 020 0.746 546 0.827 839 0.375 186 0.343 700 0.332 363 0.317 370 0.337 570 0.327 300 0.788 581 0.794 208 0.383 570 0.354 540 0.331 720 0.317 248 0.337 810 0.326 750 0.784 725 0.817 651 0.381 070 0.359 240 0.331 510 0.317 010 0.810 858 0.853 820 0.386 978 0.321 320 0.331 900 0.316 839 0.745 063 0.811 340 0.392 134 0.358 000 0.332 649 0.317 310 0.703 428 0.782 980 0.386 117 0.335 066 0.331 742 0.317 172 0.719 415 0.848 940 0.385 531 0.344 840 0.804 364 0.786 648 0.331 750 0.316 764 0.388 719 0.348 120 0.706 591 0.837 730 16:321-357. 类且类别值为 0 的情况下，结果表明除 breast-w 外，ORI 所确定 [4] Batista G E A，Prati R C，Monard M C.A study of the behav- 的阈值要小于OP所确定的阈值，当根据阈值进行分类时，ORI ior of several methods for balancing machine learning training 将更多的样例分为正例，此时TP，、FP 值都会高于根据OP所得 data[J].SIGKDD Explorations，2004，6(1):20-29. 到的值。造成上述结果的原因很多，其中之一是两种标准的 [5] Hulse J V，Khoshgoftaar T.Knowledge discovery from imbalanced 偏好不同。除 breast-w、tic-tac-toe外 ，表 2 的Sn列和Sp列中， and noisy data[J].Data Knowledge Engineering，2009，68:1513-1542. [6] Zheng Z，Wu X，Srihari R.Feature selection for text categoriza- ORI 行的|Sn - Sp|值小于OP行的|Sn - Sp|值。ORI 更倾向于在缩 tion on imbalanced data[J].SIGKDD Explorations，2004，6(1): 小Sn与Sp之间差距的前提下，共同提高两者的值，在其中一个 80-89. 无法得到进一步提高时，它会降低另外一个值以满足要求。 因为Sp在OP公式中有一个较大的系数Nn，OP相对于ORI 更倾 [7] Domingos P.MetaCost:A general method for making classifiers 向于提高Sp的值。cost-sensitive[C]//Proceedings of the Fifth International Confer- ence on Knowledge Discovery and Data Mining.[S.l.]:ACM Press， 表 2 最后两列是在分类完成后，分别用 OP、ORI 作为衡量 1999:155-164. 标准的情况。ORI 值越小说明算法性能越好，OP则相反。从 [8] Zadrozny B，Elkan C.Learning and making decisions when costs 结 果 可 以 看 出 ，根 据ORI 、OP 选 择 出 的 最 优 算 法 同 依 据 and probabilities are both unknown[C]//Proceedings of the Sev- F - measure及G - mean选择出来的算法相同。 enth International Conference Knowledge Discovery and Data 通过以上实验可以看出，作为适应度函数时，ORI适用于负 Mining，2001:204-213. 类错分代价小的情况，OP适用于两类错分代价相近的情况，作为 [9] Phua C，Alahakoon D，Lee V.Minority report in fraud detection: 一种评价标准，ORI和OP，F measure、G mean取得效果一致。 - - Classification of skewed data[J].SIGKDD Explorations，2004，6 (1):50-59. [10] Sun Y，Kamel M S，Wong A K C，et al.Cost-sensitive boosting 5 结论 for classification of imbalanced data[J].Pattern Recognition， 在阈值方法中，阈值判定函数是否合适直接影响到分类 2007，40:3358-3378. 器的性能。许多阈值判定标准都存在着缺陷，RI 在的基础上 [11] Freund Y，Schapire R E.A decision-theoretic generalization of 提出标准ORI ，理论上能够在少数类及多数类分类精度同时取 on-line learning and an application to boosting[J].Journal of Computer Science and Technology，1997，55(1):119-139. 得最好，实验数据表明，虽然在少数类及多数类分类精度同时 [12] Mitchell T M.Machine learning[M].北 京 :机 械 工 业 出 版 社 ， 取得最好的目的很难达到，但是标准ORI 提高了少数类分类精 2003:70-72. 度，并且不受样例类别比例的影响。与OP相比，ORI 适用于负 [13] Ranawana R，Palade V.Optimized precision-a new measure for 类错分代价小的情况。ORI 在 breast-w 数据集上的性能不如 classifier performance evaluation[C]//2006 IEEE Congress on OP，在 tic-tac-toe 数据集上的性能同OP一致，这两个数据集的 Evolutionary Computation Sheraton Vancouver Wall Centre Ho- tel，共同特点是容易被分类，下一步工作是找出ORI 不如OP的原 Vancouver，BC，Canada，July 16-21，2006:2254-2261. 因。另外ORI 性能提高幅度较小，继续完善ORI 标准，使之性能 [14] Ranawana R，Palade V.A neuro-genetic framework for multi- 提高幅度增大且能在理论与实验结果上相统一也是下一步工 classifier design:An application to promoter recognition in DNA 作目标。 sequences[C]//Advances in Evolutionary Computing for System Design，2007:71-94. 参考文献: [1] 刘胥影，吴建鑫，周志华.一种基于级联模型的类别不平衡数据分 [15] Kubat M，Holte R，Matwin S.Machine learning for the detec- 类方法[J].南京大学学报:自然科学版，2006，42(2). tion of oil spills in satellite radar images[J].Machine Learning， [2] Kotsiantis S，Kanellopoulos D，Pintelas P.Handling imbalanced da- 1998，30:195-215. tasets:A review[J].GESTS International Transactions on Comput- er Science and Engineering，2006，30. [16] Lewis D，Gale W.Training text classifiers by uncertainty sam- [3] Chawla N V，Bowyer K W.SMOTE:Synthetic minority over-sam- pling[C]//Proceedings of the Seventeenth Annual International ACM SIGIR Conference on Research and Development in In- file:///D|/我的资料/Desktop/新建文本文 档.txt Appliance Error (configuration_error) Your request could not be processed because of a configuration error: "Could not connect to LDAP server." For assistance, contact your network support team. file:///D|/我的资料/Desktop/新建文本文档.txt2012-07-12 20:42:52