一种基于聚类的非平衡分类算法
2014-09-04武永成
武永成，刘 钊
(1.荆楚理工学院 计算机工程学院，湖北 荆门 448000；2.武汉科技大学 计算机科学与技术学院，湖北 武汉 430081)
一种基于聚类的非平衡分类算法
武永成1，刘 钊2
(1.荆楚理工学院 计算机工程学院，湖北 荆门 448000；2.武汉科技大学 计算机科学与技术学院，湖北 武汉 430081)
传统的分类算法大多假定用来学习的数据集是平衡的，但实际应用中真正面临的数据集往往是非平衡数据。针对非平衡数据, 利用传统的分类方法往往不能获得良好的性能。文章提出了一种新的基于聚类的非平衡分类算法，通过聚类生成多个聚类体，在每个聚类体中选取一定数量的数据作为训练样本，有效地处理了样例数据的不平衡问题，在相关数据集上的实验验证了本方法的有效性。
机器学习；非平衡分类；减重取样；聚类
0 引言
分类(classification)是机器学习和数据挖掘中最典型的任务之一[1]。分类算法在对有标记样本集合(或称为有分类类型的样本集合)进行分析和学习后，生成一个分类器。利用得到的分类器，可以对那些没有分类类型的数据进行预测，判断其分类类型。如医务人员可以将病人的相关数据输入分类系统，分类系统就能根据以往学习得到的分类器，自动判断某个病人是否会药物过敏。
传统的分类算法很多都基于一种假定：用来学习的样本数据都是平衡的，即各类样本数据的数量差别不大，不是一类样本数据的数量远远大于另一类数据。然而，现实世界中，很多情况下，样例数据是不均衡的。例如：在1 000个体检数据集中，最终分类类型为健康的可能占90%，分类类型为不健康的可能为10%，这样的数据集就是非平衡的。本文中，为便于叙述，将一个数据集中大多数的样例都属于的分类类型称为MA，而剩余的样例的分类类型称为MI。
对于非平衡数据的分类(imbalanced classification)，最大的问题是：最终得到的分类器可能只对MA数据敏感，而忽略MI数据。在对测试数据进行分类预测时，容易将其分类为MA而忽略MI。例如：银行想利用分类算法构造一个分类器，对顾客未来是否进行信用贷款进行预测。银行的历史数据(有标记样本集合)中，只有2%的顾客信用贷款，其余98%顾客不贷款。传统的分类算法在这样的样本数据上进行学习得到的分类器，会将所有被预测的顾客判定为不贷款，因为这样可以得到98%的分类准确率。显然这不是银行的真正目的。能对少数的可能贷款的用户进行准确预测，才是银行所需分类器的真正目的。
针对非平衡数据的分类，在监督学习中，主要采用的是重取样(re-sampling)[2]和代价敏感(cost-sensitive learning)[3]的方法。
本文在重取样技术的基础上，提出了一种新的基于聚类(clustering)[1]的非平衡分类算法，通过聚类生成多个聚类体，在每个聚类体中选取一定数量有代表性的数据作为训练样本，有效地提高了对MI类数据预测的准确性。在相关数据集上的实验验证了本方法的有效性。
1 相关工作
机器学习的分类问题中，给定一个样例集合D={
非平衡分类问题，作为一个具有挑战性的机器学习问题，近些年在机器学习、数据挖掘等领域被广泛研究。其中使用的最重要的技术是：重取样技术和代价敏感学习技术。重取样技术又分为增重取样(over-sampling)[2]和减重取样(under-sampling)[4]两种方法，增重取样技术通过复制MI样本来使得它和MA的样本数达到平衡，减重取样技术则通过减少一定的MA样本使它与MI的样本数达到平衡。
减重取样技术中最简单的一种方法称为随机减重取样技术(random under-sampling approach，简称为RUSA)，它随机地在MA数据集中选取一定数量的MA样本，与MI一起组成一个平衡的训练集。
2 基于聚类的非平衡分类算法
随机减重取样技术最大的问题是随机选取的样本代表性可能不强。为此，本文提出了一种基于聚类的非平衡分类算法。首先对整个训练集D(由MA样本和MI样本组成的非平衡数据集)进行聚类，生成若干个聚类体。对于这些聚类体，每个可能具有不同的特点。某个聚类体可能包含较多的MA样本和较少的MI样本，则这个聚类体的整体特性与MA样本更接近；同样，某个聚类体可能包含较多的MI样本和较少的MA样本，则这个聚类体的整体特性与MI样本更接近。因此，根据每个聚类体中MA样本与MI样本的比值，我们的算法从每个聚类体中选取不同数量的MA样本，与D中所有的MI一起，组成最终的训练样本D’(平衡的数据集)，这样就有效地克服了随机减重取样技术的盲目性问题。
2.1 基于聚类的平衡数据集产生办法
(1)
例如：有一个非平衡数据集D，它的样本数量为1 100，其中SizeMA=1 000，SizeMI=100。聚类算法将D聚类为3个聚类体，3个聚类体的相关数据如表1所示。
设平衡化处理后的数据集D’中MA与MI样本之比1∶1，则可知从D中选取的MA样本数为100。这100个MA样本，是分别从聚类体1、2、3中选取82、10、8个MA样本组成的。具体计算方法如表2所示。
表1 3个聚类体的相关数据表
表2 3个聚类体中分别选取的MA样本数
2.2 基于聚类的非平衡分类算法的完整描述
本文提出的基于聚类的非平衡分类算法，其完整描述如算法1所示。
算法1 基于聚类的非平衡分类算法
3 实验结果与分析
实验中用到两个真实的数据集。一个是美国人口统计局1994年和1995年的人口-收入统计数据库，该数据集中包含公民的年龄、性别、受教育程度、工作等信息，该数据集的任务是能对每个公民的收入进行预测。总样本数为30 162，其中MA(收入低于5万美元)样本数为22 654，MI(收入高于5万美元)样本数为7 508；另一个数据库是银行贷款拖欠检测数据集，该数据集中包含客户基本信息、客户支付能力和客户账单资金总量等信息，该数据集的任务是能对容易拖欠的客户进行预测。该数据集的样本总数为62 309，其中MA(不容易拖欠的客户)样本数为47 707，MI(容易拖欠的客户)样本数为14 602。我们使用80%的样本作为学习样本，其余20%的样本用来对学习得到的分类器进行评价。
算法1的第一步提到的聚类算法采用k-medoids算法[6]，算法1的第四步提到的分类算法采用神经网络算法[7]。
为验证本算法的有效性，与随机减重取样算法(RUSA)进行了对比，实验结果如表3所示。从表3可看出，在两个数据集上，我们的算法都优于RUSA算法。
表3 两种算法的实验结果
4 结束语
本文针对随机减重取样技术的局限性，提出了一种基于聚类的非平衡分类算法。首先采用聚类算法对整个原始非平衡样本集合进行聚类，得到多个聚类体；然后在每个聚类体中，选取一定数量的MA样本，与原始样本中的所有MI样本一起，组成一个新的平衡的样本集合。在该样本集合上，利用传统的分类算法进行学习，得到最终的分类器。在两个非平衡数据集上，验证了本算法的有效性。
[1] 韩家炜.数据挖掘:概念与技术[M].北京:机械工业出版社,2004.
[2] N Chawla,K Bowyer,L Hall,et al.SMOTE:Synthetic Minority Over-Sampling Technique[J].Journal of Artificial Intelligence Research,2002,16:321-357.
[3] Z Zhou,X Liu.Training Cost-Sensitive Neural Networks with Methods Addressing the Class Imbalance Problem[C]// IEEE Transaction on Knowledge and Data Engineering,2006:63-77.
[4] R Barandela,J Sánchez,V García,et al.Strategies for Learning in Class Imbalance Problems[J].Pattern Recognition, 2003,36:849-851.
[5] M Kubat,S Matwin.Addressing the Curse of Imbalanced Training Sets:One-Sided Selection[C]//In Proceedings of ICML-97,1997:179-186.
[6] Struyf A,Hubert M,Rousseeuw P.Integrating Robust Clustering Techniques in S-plus[J].Computational Statistics and Data Analysis,1997(26):17-37.
[7] Sondak N E,Sondak V K.Neural Networks and Artificial Intelligence[C]//In Proceedings of the 20th SIGCSE Technical Symposium on Computer Science Education,1989.
2013-11-05
武永成(1971-)，男，湖北仙桃人，荆楚理工学院讲师，硕士。研究方向：机器学习和数据挖掘； 刘钊(1967-)，男，湖北襄阳人，武汉科技大学教授，博士。研究方向：人工智能和演化计算。
TP301.6
A
1008-4657(2014)02-0045-04
寸晓非]
