机器学习：基于加权聚类质心的SVM不平衡分类方法

第8卷第3期 智能系统学报 Vol.8 No.3 2013年6月 CAAI Transactions on Intelligent Systems Jun.2013 D0I:10.3969/j.issn.1673-4785.201209062 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20130515.0930.006.html 基于加权聚类质心的SVM不平衡分类方法 胡小生，钟勇 (佛山科学技术学院电子与信息工程学院，广东佛山528000) 摘要：不平衡数据分类是机器学习研究的热点问题，传统分类算法假定不同类别具有平衡分布或误分代价相同， 难以得到理想的分类结果.提出一种基于加权聚类质心的SVM分类方法，在正负类样本上分别进行聚类，对每个聚 类，用聚类质心和权重因子代表聚类内样本分布和数量，相等类别数量的质心和权重因子参与SVM模型训练.实验 结果表明，该方法使模型的训练样本具有较高的代表性，分类性能与其他采样方法相比得到了提升 关键词：机器学习：不平衡数据分类：聚类质心：支持向量机 中图分类号：TP181文献标志码：A文章编号：1673-4785(2013)03-0261-05 中文引用格式：胡小生，钟勇.基于加权聚类质心的SVM不平衡分类方法[J].智能系统学报，2013,8(3)：261-265. 英文引用格式：HU Xiaosheng,ZHONG Yong.Support vector machine imbalanced data classification based on weighted clustering centroid[J].CAAI Transactions on Intelligent Systems,2013,8(3):261-265. Support vector machine imbalanced data classification based on weighted clustering centroid HU Xiaosheng,ZHONG Yong (College of Electronic and Information Engineering,Foshan University,Foshan 528000,China) Abstract:Classification of imbalanced data has become a research hot topic in machine learning.Traditional classi- fication algorithms assume that different classes have balanced distribution or equal misclassification cost,thus, making it hard to get ideal result of classifications.A support vector machine (SVM)classification method based on weighted clustering centroid was proposed in this paper.First,unsupervised clustering was applied to the positive and negative samples respectively to extract the clustering centroid of each clustering,which was represented the most in compactness of the clustering sample.Next,all clustering centroids formed a new set of balance training.In order to minimize the information loss during clustering,each clustering centroid was associated with a weight factor that was defined proportional to the number of samples of the class.Finally,all clustering centroids and weight fac- tors participated in the training of the improved SVM model.Experimental results show that the proposed method can make the sample selected from model train sets more typical and improve the classification performance better than other sampling techniques for dealing with imbalanced data. Keywords:machine learning;imbalanced data classification;clustering centroid;support vector machine 不平衡分类是目前机器学习和数据挖掘领域的 而导致少数类的分类性能低下然而在诸如欺诈检 研究热点问题之一，在现实中存在许多实际应用不测、医疗诊断等实际应用中，少数类是人们关注的类 平衡数据集是指其中一类（多数类、负类）样本远多 别，往往具有很高的误分代价」 于另一类（少数类、正类），由于传统学习算法假定 常用的处理不平衡分类问题方法有基于数据层 或者期望数据集具有平衡类分布或相等的类误分代 面的方法和基于算法层面的方法口.基于数据层面 价，因此这些算法不能有效表现数据的分布特征，从 利用重采样技术，包括欠采样[)和过采样[)，使数 据集达到平衡基于算法层面的方法针对的是分类 收稿日期：2012-09-27.网络出版日期：2013-05-15. 基金项目：佛山市科技发展专项资金资助项目(2011AA100061):佛 算法，代价敏感学习(cost-sensitive learning)、主动学 山市产学研专项资金资助项目(2012HC100272):佛山市 教育局智能评价指标体系研究项目(DX20120220) 习、集成学习以及单类别学习等方法，是处理不平衡 通信作者：胡小生.E-mail:happyhxs@tom.com 数据集的常见算法[46].这2种层面方法各有优缺

第 ８ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．８ №．３ ２０１３ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１３ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１２０９０６２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１３０５１５．０９３０．００６．ｈｔｍｌ 基于加权聚类质心的 ＳＶＭ 不平衡分类方法 胡小生，钟勇 （佛山科学技术学院 电子与信息工程学院，广东 佛山 ５２８０００） 摘 要：不平衡数据分类是机器学习研究的热点问题，传统分类算法假定不同类别具有平衡分布或误分代价相同， 难以得到理想的分类结果．提出一种基于加权聚类质心的 ＳＶＭ 分类方法，在正负类样本上分别进行聚类，对每个聚 类，用聚类质心和权重因子代表聚类内样本分布和数量，相等类别数量的质心和权重因子参与 ＳＶＭ 模型训练．实验 结果表明，该方法使模型的训练样本具有较高的代表性，分类性能与其他采样方法相比得到了提升． 关键词：机器学习；不平衡数据分类；聚类质心；支持向量机 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１３）０３⁃０２６１⁃０５ 中文引用格式：胡小生，钟勇．基于加权聚类质心的 ＳＶＭ 不平衡分类方法［Ｊ］．智能系统学报， ２０１３， ８（３）： ２６１⁃２６５． 英文引用格式：ＨＵ Ｘｉａｏｓｈｅｎｇ， ＺＨＯＮＧ Ｙｏｎｇ． Ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｂａｓｅｄ ｏｎ ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１３， ８（３）： ２６１⁃２６５． Ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｂａｓｅｄ ｏｎ ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ ＨＵ Ｘｉａｏｓｈｅｎｇ， ＺＨＯＮＧ Ｙｏｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｆｏｓｈａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｆｏｓｈａｎ ５２８０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｈａｓ ｂｅｃｏｍｅ ａ ｒｅｓｅａｒｃｈ ｈｏｔ ｔｏｐｉｃ ｉｎ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ． Ｔｒａｄｉｔｉｏｎａｌ ｃｌａｓｓｉ⁃ ｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ａｓｓｕｍｅ ｔｈａｔ ｄｉｆｆｅｒｅｎｔ ｃｌａｓｓｅｓ ｈａｖｅ ｂａｌａｎｃｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｒ ｅｑｕａｌ ｍｉｓｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃｏｓｔ， ｔｈｕｓ， ｍａｋｉｎｇ ｉｔ ｈａｒｄ ｔｏ ｇｅｔ ｉｄｅａｌ ｒｅｓｕｌｔ ｏｆ ｃｌａｓｓｉｆｉｃａｔｉｏｎｓ． Ａ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ （ＳＶＭ） ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ ｗａｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ． Ｆｉｒｓｔ， ｕｎｓｕｐｅｒｖｉｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ｗａｓ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｐｏｓｉｔｉｖｅ ａｎｄ ｎｅｇａｔｉｖｅ ｓａｍｐｌｅｓ ｒｅｓｐｅｃｔｉｖｅｌｙ ｔｏ ｅｘｔｒａｃｔ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ ｏｆ ｅａｃｈ ｃｌｕｓｔｅｒｉｎｇ， ｗｈｉｃｈ ｗａｓ ｒｅｐｒｅｓｅｎｔｅｄ ｔｈｅ ｍｏｓｔ ｉｎ ｃｏｍｐａｃｔｎｅｓｓ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｓａｍｐｌｅ． Ｎｅｘｔ， ａｌｌ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄｓ ｆｏｒｍｅｄ ａ ｎｅｗ ｓｅｔ ｏｆ ｂａｌａｎｃｅ ｔｒａｉｎｉｎｇ． Ｉｎ ｏｒｄｅｒ ｔｏ ｍｉｎｉｍｉｚｅ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｌｏｓｓ ｄｕｒｉｎｇ ｃｌｕｓｔｅｒｉｎｇ， ｅａｃｈ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ ｗａｓ ａｓｓｏｃｉａｔｅｄ ｗｉｔｈ ａ ｗｅｉｇｈｔ ｆａｃｔｏｒ ｔｈａｔ ｗａｓ ｄｅｆｉｎｅｄ ｐｒｏｐｏｒｔｉｏｎａｌ ｔｏ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｓａｍｐｌｅｓ ｏｆ ｔｈｅ ｃｌａｓｓ． Ｆｉｎａｌｌｙ， ａｌｌ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄｓ ａｎｄ ｗｅｉｇｈｔ ｆａｃ⁃ ｔｏｒｓ ｐａｒｔｉｃｉｐａｔｅｄ ｉｎ ｔｈｅ ｔｒａｉｎｉｎｇ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ＳＶＭ ｍｏｄｅｌ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｃａｎ ｍａｋｅ ｔｈｅ ｓａｍｐｌｅ ｓｅｌｅｃｔｅｄ ｆｒｏｍ ｍｏｄｅｌ ｔｒａｉｎ ｓｅｔｓ ｍｏｒｅ ｔｙｐｉｃａｌ ａｎｄ ｉｍｐｒｏｖｅ ｔｈｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｅｒｆｏｒｍａｎｃｅ ｂｅｔｔｅｒ ｔｈａｎ ｏｔｈｅｒ ｓａｍｐｌｉｎｇ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｄｅａｌｉｎｇ ｗｉｔｈ ｉｍｂａｌａｎｃｅｄ ｄａｔａ． Ｋｅｙｗｏｒｄｓ：ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ； ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ； ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ； ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ 收稿日期：２０１２⁃０９⁃２７． 网络出版日期：２０１３⁃０５⁃１５． 基金项目：佛山市科技发展专项资金资助项目（２０１１ＡＡ１０００６１）；佛 山市产学研专项资金资助项目（ ２０１２ＨＣ１００２７２）；佛山市 教育局智能评价指标体系研究项目（ＤＸ２０１２０２２０）． 通信作者：胡小生．Ｅ⁃ｍａｉｌ： ｈａｐｐｙｈｘｓ＠ ｔｏｍ．ｃｏｍ． 不平衡分类是目前机器学习和数据挖掘领域的 研究热点问题之一，在现实中存在许多实际应用．不 平衡数据集是指其中一类（多数类、负类）样本远多 于另一类（少数类、正类），由于传统学习算法假定 或者期望数据集具有平衡类分布或相等的类误分代 价，因此这些算法不能有效表现数据的分布特征，从 而导致少数类的分类性能低下．然而在诸如欺诈检 测、医疗诊断等实际应用中，少数类是人们关注的类 别，往往具有很高的误分代价． 常用的处理不平衡分类问题方法有基于数据层 面的方法和基于算法层面的方法［１］ ．基于数据层面 利用重采样技术，包括欠采样［２］ 和过采样［３］ ，使数 据集达到平衡．基于算法层面的方法针对的是分类 算法，代价敏感学习（ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ｌｅａｒｎｉｎｇ）、主动学 习、集成学习以及单类别学习等方法，是处理不平衡 数据集的常见算法［４⁃６］ ．这 ２ 种层面方法各有优缺

·262· 智能系统学报 第8卷 点，基于数据层面的方法使用范围广泛，而基于算法 信息丢失.为此，还需提供聚类质心的统计概要信 层面的方法更适合某些特殊领域.支持向量机(sup 息，用权重因子p表示，如果类样本数量为N,某个 port vector machine,SVM)是基于统计学习理论和 聚类子集内样本数量为n,则 结构风险最小化原则的机器学习方法，已经成为当 前数据挖掘领域最好的方法之一.当样本类别分布 n=0∑m=1 均衡时，支持向量机方法能够取得较高的分类精度， 由于K均值聚类以及SVM分类都只能处理数 然而应用于不平衡数据集时，其分类性能会大大降 值型的属性，但实际应用中的数据集具有数值型、分 低.近年来，有许多文献提出了改进的SVM算法来 类型等属性，因此需要进行数据预处理对于数值型 处理不平衡分类问题.文献[7]提出在SVM中使用 的属性，为了消除大的数值在SVM目标函数中大的 不同的惩罚因子处理不平衡分类问题，即加权SVM 影响，需要进行[0,1]标准化，按照式(1)进行转换： (SVM-weight),在实际应用中有明显效果；文献[8] 将veropoulous的不同惩罚因子方法同SMOTE相结 ay didain (1) dmas-dmin 合处理不平衡问题；文献[9]提出核边界校准(ker 对于分类型的属性，采样二进制编码方式进行 nel boundary alignment,.KBA)方法，通过调整核函 转换，将分类型的属性转换为若干个取值0和1的 数边界使得SVM更适合处理不平衡数据集；文献 属性例如，对于有姓名、性别2个属性的某样本数 [10]提出一种基于SVM的主动学习方法，该方法 据“张三，男”，经过二进制编码转换，变为有姓名、 选择离当前分类超平面最近的最富信息样例，重新 性别_男、性别_女3个属性，相应的样本数据信息 训练SVM,能够避免搜索全部数据，但是搜索最富 为“张三，1,0”.获取聚类质心及其权重因子的具体 信息样例的过程计算量很大 流程如下. 本文借鉴加权SVM思想，提出一种基于加权聚 输入：训练数据集D 类质心的SVM不平衡分类方法(weighted clustering 1)S=pre-process[D];/数据预处理 centroid support vector machine,WCC-SVM).该方法 2)train[S]=选取数据集S中的80%样本， 首先分别在正负类样本上进行K均值聚类，2类样 test[S]=S中剩余的20%样本； 本聚类数量相同，之后对于每个聚类，得到聚类质心 3)确定聚类的K值，计算train[S]中正类样本 及其关于质心的统计概要信息，此概要信息用权重 数量N,如果N<1000,令K=N:否则取K的值接近 因子表示，所有的聚类质心组成新训练集，并且聚类 N,例如K=0.9N或者K=0.95N: 质心的权重因子通过与样本惩罚项相结合的方式修 4)在正负类样本中分别进行K均值聚类算法， 改SVM目标函数，得到最终的分类学习模型. 分别得到K个不相交子集； 1K均值聚类及数据预处理 5)对正负类样本分别计算K个聚类质心C:及 权重因子P:; 对于不平衡数据集，对多数类样本进行欠采样 6)输出：K个正类聚类质心C:和权重因子p,K 和对少数类进行过采样均能改变数据分布，使数据 个负类聚类质心C:和权重因子P 达到平衡，但是这2种方法都有缺点，过采样容易使 在步骤3)中，根据数据集train[S]中正类样本 分类器学习到的决策域变小，从而可能导致过度拟 数量N来决定聚类的K值，当N值较小时，为了不 合问题：欠采样由于删除部分训练样例，会引起信息 至于使接下来参与支持向量机训练的正类样本空间 丢失.为了减少训练样本集中的类样本数量，对类样 变小，取K=N,即对正类样本不进行聚类压缩，此时 本进行划分是一个很好的思路.本文选取K均值聚 每一个正类样本即为聚类质心，其权重因子p=1/K 类方法，将训练集中的正负类样本分别聚类为K个 而如果当正类样本数量较多时，样本空间有足够的 不相交的子集，对于类别分布极端不平衡的数据集， 代表性，适当地对正类样本进行聚类压缩，在分类性 可仅仅在多数类样本上进行K均值聚类，其中K值 能差异不明显的情况下，能够减少正、负类样本聚类 与少数类样本数量相等.样本聚类后，与欠采样方法 时间以及支持向量机模型的训练时间， 不同，不是在每个聚类子集内选择一部分样本，而是 2加权聚类质心的SVM分类 仅仅用聚类质心来代表某个子集，虽然聚类质心最 能够表征一个聚类样本的特征，但是由一个聚类质 经过K均值聚类得到类别数量相等的聚类质 心代表一个聚类内所有样本，同样也不可避免造成 心及其权重因子，这2K个聚类质心及其对应的权

点，基于数据层面的方法使用范围广泛，而基于算法 层面的方法更适合某些特殊领域．支持向量机（ ｓｕｐ⁃ ｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ， ＳＶＭ） 是基于统计学习理论和 结构风险最小化原则的机器学习方法，已经成为当 前数据挖掘领域最好的方法之一．当样本类别分布 均衡时，支持向量机方法能够取得较高的分类精度， 然而应用于不平衡数据集时，其分类性能会大大降 低．近年来，有许多文献提出了改进的 ＳＶＭ 算法来 处理不平衡分类问题．文献［７］提出在 ＳＶＭ 中使用 不同的惩罚因子处理不平衡分类问题，即加权 ＳＶＭ （ＳＶＭ⁃ｗｅｉｇｈｔ），在实际应用中有明显效果；文献［８］ 将 ｖｅｒｏｐｏｕｌｏｕｓ 的不同惩罚因子方法同 ＳＭＯＴＥ 相结 合处理不平衡问题；文献［９］提出核边界校准（ ｋｅｒ⁃ ｎｅｌ ｂｏｕｎｄａｒｙ ａｌｉｇｎｍｅｎｔ， ＫＢＡ） 方法，通过调整核函 数边界使得 ＳＶＭ 更适合处理不平衡数据集；文献 ［１０］ 提出一种基于 ＳＶＭ 的主动学习方法，该方法 选择离当前分类超平面最近的最富信息样例，重新 训练 ＳＶＭ，能够避免搜索全部数据，但是搜索最富 信息样例的过程计算量很大． 本文借鉴加权 ＳＶＭ 思想，提出一种基于加权聚 类质心的 ＳＶＭ 不平衡分类方法（ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｒｏｉｄ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ， ＷＣＣ⁃ＳＶＭ）．该方法 首先分别在正负类样本上进行 Ｋ 均值聚类，２ 类样 本聚类数量相同，之后对于每个聚类，得到聚类质心 及其关于质心的统计概要信息，此概要信息用权重 因子表示，所有的聚类质心组成新训练集，并且聚类 质心的权重因子通过与样本惩罚项相结合的方式修 改 ＳＶＭ 目标函数，得到最终的分类学习模型． １ Ｋ 均值聚类及数据预处理 对于不平衡数据集，对多数类样本进行欠采样 和对少数类进行过采样均能改变数据分布，使数据 达到平衡，但是这 ２ 种方法都有缺点，过采样容易使 分类器学习到的决策域变小，从而可能导致过度拟 合问题；欠采样由于删除部分训练样例，会引起信息 丢失．为了减少训练样本集中的类样本数量，对类样 本进行划分是一个很好的思路．本文选取 Ｋ 均值聚 类方法，将训练集中的正负类样本分别聚类为 Ｋ 个 不相交的子集，对于类别分布极端不平衡的数据集， 可仅仅在多数类样本上进行 Ｋ 均值聚类，其中 Ｋ 值 与少数类样本数量相等．样本聚类后，与欠采样方法 不同，不是在每个聚类子集内选择一部分样本，而是 仅仅用聚类质心来代表某个子集，虽然聚类质心最 能够表征一个聚类样本的特征，但是由一个聚类质 心代表一个聚类内所有样本，同样也不可避免造成 信息丢失．为此，还需提供聚类质心的统计概要信 息，用权重因子 ｐ 表示，如果类样本数量为 Ｎ，某个 聚类子集内样本数量为 ｎｉ，则 ｐｉ ＝ ｎｉ Ｎ ，∑ｐｉ ＝ １． 由于 Ｋ 均值聚类以及 ＳＶＭ 分类都只能处理数 值型的属性，但实际应用中的数据集具有数值型、分 类型等属性，因此需要进行数据预处理．对于数值型 的属性，为了消除大的数值在 ＳＶＭ 目标函数中大的 影响，需要进行［０，１］标准化，按照式（１）进行转换： ａｊ ＝ ａｊ － ａｍｉｎ ａｍａｘ － ａｍｉｎ ． （１） 对于分类型的属性，采样二进制编码方式进行 转换，将分类型的属性转换为若干个取值 ０ 和 １ 的 属性．例如，对于有姓名、性别 ２ 个属性的某样本数 据“张三，男”，经过二进制编码转换，变为有姓名、 性别＿男、性别＿女 ３ 个属性，相应的样本数据信息 为“张三，１， ０”．获取聚类质心及其权重因子的具体 流程如下． 输入：训练数据集 Ｄ １）Ｓ ＝ ｐｒｅ＿ｐｒｏｃｅｓｓ［Ｄ］； ／ ／ 数据预处理 ２） ｔｒａｉｎ［ Ｓ］ ＝ 选取数据集 Ｓ 中的 ８０％ 样本， ｔｅｓｔ［Ｓ］ ＝ Ｓ 中剩余的 ２０％样本； ３）确定聚类的 Ｋ 值，计算 ｔｒａｉｎ［ Ｓ］中正类样本 数量 Ｎ，如果 Ｎ＜１ ０００，令 Ｋ ＝Ｎ；否则取 Ｋ 的值接近 Ｎ，例如 Ｋ ＝ ０．９Ｎ 或者 Ｋ ＝ ０．９５Ｎ； ４）在正负类样本中分别进行 Ｋ 均值聚类算法， 分别得到 Ｋ 个不相交子集； ５）对正负类样本分别计算 Ｋ 个聚类质心 Ｃｉ 及 权重因子 ｐｉ； ６）输出：Ｋ 个正类聚类质心 Ｃｉ 和权重因子 ｐｉ，Ｋ 个负类聚类质心 Ｃｉ 和权重因子 ｐｉ ． 在步骤 ３）中，根据数据集 ｔｒａｉｎ［Ｓ］中正类样本 数量 Ｎ 来决定聚类的 Ｋ 值，当 Ｎ 值较小时，为了不 至于使接下来参与支持向量机训练的正类样本空间 变小，取 Ｋ ＝Ｎ，即对正类样本不进行聚类压缩，此时 每一个正类样本即为聚类质心，其权重因子 ｐ ＝ １ ／ Ｋ． 而如果当正类样本数量较多时，样本空间有足够的 代表性，适当地对正类样本进行聚类压缩，在分类性 能差异不明显的情况下，能够减少正、负类样本聚类 时间以及支持向量机模型的训练时间． ２ 加权聚类质心的 ＳＶＭ 分类 经过 Ｋ 均值聚类得到类别数量相等的聚类质 心及其权重因子，这 ２Ｋ 个聚类质心及其对应的权 ·２６２· 智 能 系 统 学 报 第 ８ 卷

第3期 胡小生，等：基于加权聚类质心的SVM不平衡分类方法 ·263- 重因子一起组成新的训练集，参与加权SVM模型训 由式(3)得到 练，现简要介绍其原理. w·= 考虑二分类问题，给定训练样本集D: 立ay()=dx i=1 D={(x,y:)Ix:∈R,y:e{1,-1}}, 式中：S为拉格朗日乘子a,>0所对应的样本（支持 i=1,2,…,K 向量)总数量.根据式(4)，能够求解出阈值b·, 支持向量机学习器的目标是求解最优分类超平面， (w·,b·)数值确定后，SVM分类决策函数可由式 也即最大化2类样本之间的距离.不失一般性，考虑 (5)确定 训练样本为非线性，通过引入非线性变换中：R→H f(x)=sign(w··中(x)+b*)= 将输入空间R映射到高维特征空间H,从而将非 sign(∑ay,K(x,x)+b) (5) 线性问题转变为线性问题.当线性可分时，求解最优 =1 分类超平面可归纳为式(2)所示的二次规划问题： 式中：K(x,x:)为高维Hilbert空间中的内积 min )=w 3实验与分析 s.t.y:(w·(x,)+b)-1>0,i=1,2,…,K 3.1数据集 为了评估基于加权聚类质心的SVM分类方法 (2) 的性能，选择6组具有不同实际应用背景的UCI数 式中：w为权重向量，b为阈值.当线性不可分时，引 据集进行测试对于含有多个类别的数据，采用与其 人惩罚因子C,对错分样本进行惩罚，此时式(2)重 他文献相似的方法，即将其中的一类作为少数类，合 写为： 并其他的类别为一个整体作为多数类.例如，将 mim0(w.6,6)-7Iw2+c26 page-blocks的类别5作为少数类，合并其他的类作 为多数类.实验数据集如表1所示. s.ty:(w·p(x:)+b)>1-, 表1UCI数据集 5>0,i=1,2,,K Table 1 UCI Datasets 式中：专为松弛变量，用来度量样本分类错误代价 数据集 样例数目 少数类多数类不平衡度 文中将聚类质心对应的权重因子p引入目标函 vehicle 846 199 647 3.25 数中，则P:专：表示给样本分类错误代价设置一个权 重.因此，分类超平面目标函数可修改为： artificial 5109 708 4401 6.21 min Q(w.b). vowel 990 90 900 10.00 i=1 letter 20000 734 19266 26.25 s.t.y:(w·(x;)+b)>1-5, abalone 4177 115 4062 35.32 5>0,i=1,2,,K page-blocks 5473 1155358 46.59 利用拉格朗日乘子法求解具有约束的二次规划 3.2评价标准 问题，即： 在传统的分类学习中，一般采用分类精度（分 mo,6apB)=号II+c套p 类正确的样本个数占总样本个数的百分比)作为评 价指标，然而对于不平衡数据集，这一指标的实际意 y(w(x)+b)-1+ 义不大，因为它反映的是多数类样本的分类测试结 s.t.a≥0，B≥0 果.针对不平衡数据，很多学者提出了建立在混淆矩 根据约束问题的KKT条件，有 阵基础上的F-measure、G-mean等评价指标ui2]. 0w6aB2-w-ax(x)=0,(3) 在某些应用中，人们更加关注少数类样本的分 ow 类性能，F-measure就是用于衡量少数类分类性能的 i=1 aQ(w,b,a,β) 2=-∑4y:=0. 指标.F-measure是查全率(recall)和查准率(preci-- ab sio)的调和均值，其取值接近两者的较小者，因此， aQ(w,b,a,B) 较大F-measure值表示recall和precision都较大，其 aξ =P:C-a-B=0, 计算公式为 aQw,ba,B）=wx)+b)-1+5:=0.(4) F2x recall x precision da recall precision

重因子一起组成新的训练集，参与加权 ＳＶＭ 模型训 练，现简要介绍其原理． 考虑二分类问题，给定训练样本集 Ｄ： Ｄ ＝ ｛（ｘｉ，ｙｉ） ｜ ｘｉ ∈ Ｒ Ｎ ，ｙｉ ∈ ｛１， － １｝｝， ｉ ＝ １，２，．．．，Ｋ． 支持向量机学习器的目标是求解最优分类超平面， 也即最大化 ２ 类样本之间的距离．不失一般性，考虑 训练样本为非线性，通过引入非线性变换 ϕ：Ｒ Ｎ→Ｈ 将输入空间 Ｒ Ｎ 映射到高维特征空间 Ｈ，从而将非 线性问题转变为线性问题．当线性可分时，求解最优 分类超平面可归纳为式（２）所示的二次规划问题： ｍｉｎ Ｑ（ｗ，ｂ） ＝ １ ２ ‖ｗ‖２ ， ｓ．ｔ． ｙｉ（ｗ·ϕ（ｘｉ） ＋ ｂ） － １ ＞ ０， ｉ ＝ １，２，．．．，Ｋ． （２） 式中：ｗ 为权重向量，ｂ 为阈值．当线性不可分时，引 入惩罚因子 Ｃ，对错分样本进行惩罚，此时式（２）重 写为： ｍｉｎ Ｑ（ｗ，ｂ，ξ） ＝ １ ２ ‖ｗ‖２ ＋ Ｃ∑ Ｋ ｉ ＝ １ ξｉ， ｓ．ｔ． ｙｉ（ｗ·ϕ（ｘｉ） ＋ ｂ） ＞ １ － ξｉ， ξｉ ＞ ０，ｉ ＝ １，２，．．．，Ｋ． 式中：ξｉ 为松弛变量，用来度量样本分类错误代价． 文中将聚类质心对应的权重因子 ｐ 引入目标函 数中，则 ｐｉ ξｉ 表示给样本分类错误代价设置一个权 重．因此，分类超平面目标函数可修改为： ｍｉｎ Ｑ（ｗ，ｂ，ξ） ＝ １ ２ ‖ｗ‖２ ＋ Ｃ∑ Ｋ ｉ ＝ １ ｐｉ ξｉ， ｓ．ｔ． ｙｉ（ｗ·ϕ（ｘｉ） ＋ ｂ） ＞ １ － ξｉ， ξｉ ＞ ０，ｉ ＝ １，２，．．．，Ｋ． 利用拉格朗日乘子法求解具有约束的二次规划 问题，即： ｍｉｎ Ｑ（ｗ，ｂ，ａ，β） ＝ １ ２ ‖ｗ‖２ ＋ Ｃ∑ Ｋ ｉ ＝ １ ｐｉ ξｉ － ∑ Ｋ ｉ ＝ １ ａｉ（ｙｉ（ｗ·ϕ（ｘｉ） ＋ ｂ） － １ ＋ ξｉ） － ∑ Ｋ ｉ ＝ １ βｉ ξｉ， ｓ．ｔ． ａｉ ≥ ０，βｉ ≥ ０． 根据约束问题的 ＫＫＴ 条件，有 ∂Ｑ（ｗ，ｂ，ａ，β） ∂ｗ ＝ ｗ － ∑ Ｋ ｉ ＝ １ ａｉ ｙｉϕ（ｘｉ） ＝ ０， （３） ∂Ｑ（ｗ，ｂ，ａ，β） ∂ｂ ＝ － ∑ Ｋ ｉ ＝ １ ａｉ ｙｉ ＝ ０， ∂Ｑ（ｗ，ｂ，ａ，β） ∂ξ ＝ ｐｉＣ － ａｉ － βｉ ＝ ０， ∂ Ｑ（ｗ，ｂ，ａ， β） ∂ ａ ＝ ｙｉ（ｗ·ϕ（ｘｉ） ＋ ｂ） － １ ＋ ξｉ ＝ ０ ． （４） 由式（３）得到 ｗ ∗ ＝ ∑ Ｋ ｉ ＝ １ ａｉ ｙｉϕ（ｘｉ） ＝ ∑ Ｓ ｉ ＝ １ ａｉ ｙｉϕ（ｘｉ）． 式中：Ｓ 为拉格朗日乘子 ａｉ ＞０ 所对应的样本（支持 向量） 总数量． 根据式（ ４），能够求解出阈值 ｂ ∗ ， （ｗ ∗ ，ｂ ∗ ） 数值确定后，ＳＶＭ 分类决策函数可由式 （５）确定． ｆ（ｘ） ＝ ｓｉｇｎ（ｗ ∗·ϕ（ｘ） ＋ ｂ ∗ ） ＝ ｓｉｇｎ（∑ Ｓ ｉ ＝ １ ａｉ ｙｉＫ（ｘ，ｘｉ） ＋ ｂ ∗ ）． （５） 式中：Ｋ（ｘ，ｘｉ）为高维 Ｈｉｌｂｅｒｔ 空间中的内积． ３ 实验与分析 ３．１ 数据集 为了评估基于加权聚类质心的 ＳＶＭ 分类方法 的性能，选择 ６ 组具有不同实际应用背景的 ＵＣＩ 数 据集进行测试．对于含有多个类别的数据，采用与其 他文献相似的方法，即将其中的一类作为少数类，合 并其他的类别为一个整体作为多数类． 例如， 将 ｐａｇｅ⁃ｂｌｏｃｋｓ 的类别 ５ 作为少数类，合并其他的类作 为多数类．实验数据集如表 １ 所示． 表 １ ＵＣＩ 数据集 Ｔａｂｌｅ １ ＵＣＩ Ｄａｔａｓｅｔｓ 数据集 样例数目 少数类 多数类 不平衡度 ｖｅｈｉｃｌｅ ８４６ １９９ ６４７ ３．２５ ａｒｔｉｆｉｃｉａｌ ５ １０９ ７０８ ４ ４０１ ６．２１ ｖｏｗｅｌ ９９０ ９０ ９００ １０．００ ｌｅｔｔｅｒ ２０ ０００ ７３４ １９ ２６６ ２６．２５ ａｂａｌｏｎｅ ４ １７７ １１５ ４ ０６２ ３５．３２ ｐａｇｅ⁃ｂｌｏｃｋｓ ５ ４７３ １１５ ５ ３５８ ４６．５９ ３．２ 评价标准 在传统的分类学习中，一般采用分类精度（分 类正确的样本个数占总样本个数的百分比）作为评 价指标，然而对于不平衡数据集，这一指标的实际意 义不大，因为它反映的是多数类样本的分类测试结 果．针对不平衡数据，很多学者提出了建立在混淆矩 阵基础上的 Ｆ⁃ｍｅａｓｕｒｅ、Ｇ⁃ｍｅａｎ 等评价指标［１１⁃１２］ ． 在某些应用中，人们更加关注少数类样本的分 类性能，Ｆ⁃ｍｅａｓｕｒｅ 就是用于衡量少数类分类性能的 指标．Ｆ⁃ｍｅａｓｕｒｅ 是查全率（ ｒｅｃａｌｌ） 和查准率（ ｐｒｅｃｉ⁃ ｓｉｏｎ）的调和均值，其取值接近两者的较小者，因此， 较大 Ｆ⁃ｍｅａｓｕｒｅ 值表示 ｒｅｃａｌｌ 和 ｐｒｅｃｉｓｉｏｎ 都较大，其 计算公式为 Ｆｍｅａｓｕｒｅ ＝ ２ × ｒｅｃａｌｌ × ｐｒｅｃｉｓｉｏｎ ｒｅｃａｌｌ ＋ ｐｒｅｃｉｓｉｏｎ ． 第 ３ 期 胡小生，等：基于加权聚类质心的 ＳＶＭ 不平衡分类方法 ·２６３·

·264· 智能系统学报 第8卷 TP TP 表4各种方法G-mean值比较 式中：recall= TP+FN,precision= TP+FP.TP .FN.FP Table 4 The comparison of G-mean in different methods TN的含义如表2所示. C5.0+ Undersample+ 数据集 M3-SVM 本文算法 表22类混淆矩阵 SMOTE CSVM Table 2 A two-class confusion matrix vehicle 0.810 0.612 0.815 0.925 预测 artificial 0.713 0.654 0.753 0.795 实际 正类 反类 vowel 0.787 0.769 0.953 0.939 正类 TP FN letter 0.940 0.860 0.894 0.992 反类 FP TN abalone 0.720 0.780 0.820 0.940 G-mean是一种衡量数据集整体分类性能的评 0.786 0.896 0.748 0.775 价指标，其值定义为 page-blocks 平均值 0.793 0.762 0.831 0.894 TP 根据F-measure的定义，如果算法能够获得较 式中：正类分类准确率A.=recall= P+Fm,负类 大的值，则说明算法的少数类查全率和查准率都较 TN 高，有较好的少数类识别性能.从表3中可以看出， 分类准确率ATN+FP 从定义中可以看出，G 在所测试的6个数据集中，所提算法在其中4个数 mean兼顾了少数类和多数类精度的平均，更能够反 据集上的F-measure值都高于其他方法，特别是在 映出分类器的整体性能， page-blocks数据集上，与所比较3种算法中的最佳 本文采用F-measure和G-mean作为分类方法 结果有将近11%的提升.此外，通过计算6组UCI数 的评价标准。 据在不同方法下的F-measure平均值，也可以看出 3.3实验结果 本文所提算法明显优于其他方法，在平均值性能上 为方便比较，实验中对数据采用五折交叉验证 比次优算法M3-SVM有将近5%的性能提升 方式，为保证数据在进行分组过程中不平衡度保持 G-mean的定义说明，其值越大，说明正类分类 一致，采用分层采样，将数据集中少数类和多数类样 准确率和负类分类准确率都越大，也即算法在整体 本分别随机分为5等份，两两随机组合得到5个与 上的分类性能越好.从整体分类角度比较，本文算法 初始数据集不平衡度一致的子集，将其中4个子集 在6组数据集上的G-mean度量指标值比次优算法 作为训练集，1个子集作为测试集，重复5次，以平 有8%的性能提升. 均值作为最终的评价结果 从F-measure和G-mean的实验结果中同时可 实验中，所提算法与其他3种具有代表性的方 以看出，在处理不平衡分类问题时，随机欠采样与代 法进行比较：过采样SMOTE与决策树C5.0结合的 价敏感支持向量机相结合方法undersample+CSVM C5.0+SMOTE、随机欠采样与代价敏感支持向量机 分类效果不佳.这是由于为了组成新的平衡训练集！ (CSVM)相结合的undersample-+CSVM、基于训练集 随机欠采样方法丢弃了许多有用的负类样本信息， 划分与分类器集成的最小最大模块化支持向量机 得到的分类超平面明显偏离实际位置，当不平衡度 (M3-SVM)I).实验结果如表3和4所示 越高时，其劣势更加明显此结果也间接表明本文所 表3各种方法F-measure值比较 提出的通过以K均值聚类质心及其权重因子来代 Table 3 The comparison of F-measure in different methods 表众多负类样本的有效性，在组成新平衡训练数据 集的同时，又不致于因改变数据集的数据分布而损 C5.0+ Undersample+ 数据集 M3-SVM 本文算法 SMOTE CSVM 失了负类样本所包含的有用的分类信息 vehicle 0.850 0.613 0.869 0.894 4结束语 artificial 0.643 0.516 0.682 0.730 本文提出一种K均值聚类与支持向量机相结 vowel 0.698 0.493 0.828 0.766 letter 0.890 0.590 0.760 0.907 合的不平衡数据分类方法一WCC-SVM,该方法在 进行数据预处理后，对训练集上的正负类样本各自 abalone 0.320 0.280 0.392 0.340 page-blocks 0.569 0.383 0.613 0.680 进行无监督的K均值聚类，对每个聚类，以聚类质 平均值 0.662 0.479 0.691 0.720 心和权重因子代表聚类样本分布和数量，然后进行 基于加权SVM模型训练.实验结果表明，该方法在

式中：ｒｅｃａｌｌ ＝ ＴＰ ＴＰ＋ＦＮ ，ｐｒｅｃｉｓｉｏｎ ＝ ＴＰ ＴＰ＋ＦＰ ，ＴＰ、ＦＮ、ＦＰ、 ＴＮ 的含义如表 ２ 所示． 表 ２ ２ 类混淆矩阵 Ｔａｂｌｅ ２ Ａ ｔｗｏ⁃ｃｌａｓｓ ｃｏｎｆｕｓｉｏｎ ｍａｔｒｉｘ 实际 预测 正类 反类 正类 ＴＰ ＦＮ 反类 ＦＰ ＴＮ Ｇ⁃ｍｅａｎ 是一种衡量数据集整体分类性能的评 价指标，其值定义为 Ｇｍｅａｎ ＝ Ａｐｏｓｉｔｉｖｅ × Ａｎｅｇａｔｉｖｅ ． 式中：正类分类准确率 Ａｐｏｓｉｔｉｖｅ ＝ ｒｅｃａｌｌ ＝ ＴＰ ＴＰ＋ＦＮ ，负类 分类准确率 Ａｎｅｇａｔｉｖｅ ＝ ＴＮ ＴＮ＋ＦＰ ．从定义中可以看出，Ｇ⁃ ｍｅａｎ 兼顾了少数类和多数类精度的平均，更能够反 映出分类器的整体性能． 本文采用 Ｆ⁃ｍｅａｓｕｒｅ 和 Ｇ⁃ｍｅａｎ 作为分类方法 的评价标准． ３．３ 实验结果 为方便比较，实验中对数据采用五折交叉验证 方式，为保证数据在进行分组过程中不平衡度保持 一致，采用分层采样，将数据集中少数类和多数类样 本分别随机分为 ５ 等份，两两随机组合得到 ５ 个与 初始数据集不平衡度一致的子集，将其中 ４ 个子集 作为训练集，１ 个子集作为测试集，重复 ５ 次，以平 均值作为最终的评价结果． 实验中，所提算法与其他 ３ 种具有代表性的方 法进行比较：过采样 ＳＭＯＴＥ 与决策树 Ｃ５．０ 结合的 Ｃ５．０＋ＳＭＯＴＥ、随机欠采样与代价敏感支持向量机 （ＣＳＶＭ）相结合的 ｕｎｄｅｒｓａｍｐｌｅ＋ＣＳＶＭ、基于训练集 划分与分类器集成的最小最大模块化支持向量机 （Ｍ３⁃ＳＶＭ） ［１３］ ．实验结果如表 ３ 和 ４ 所示． 表 ３ 各种方法 Ｆ⁃ｍｅａｓｕｒｅ 值比较 Ｔａｂｌｅ ３ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｆ⁃ｍｅａｓｕｒｅ ｉｎ ｄｉｆｆｅｒｅｎｔ ｍｅｔｈｏｄｓ 数据集 Ｃ５．０＋ ＳＭＯＴＥ Ｕｎｄｅｒｓａｍｐｌｅ＋ ＣＳＶＭ Ｍ３⁃ＳＶＭ 本文算法 ｖｅｈｉｃｌｅ ０．８５０ ０．６１３ ０．８６９ ０．８９４ ａｒｔｉｆｉｃｉａｌ ０．６４３ ０．５１６ ０．６８２ ０．７３０ ｖｏｗｅｌ ０．６９８ ０．４９３ ０．８２８ ０．７６６ ｌｅｔｔｅｒ ０．８９０ ０．５９０ ０．７６０ ０．９０７ ａｂａｌｏｎｅ ０．３２０ ０．２８０ ０．３９２ ０．３４０ ｐａｇｅ⁃ｂｌｏｃｋｓ ０．５６９ ０．３８３ ０．６１３ ０．６８０ 平均值 ０．６６２ ０．４７９ ０．６９１ ０．７２０ 表 ４ 各种方法 Ｇ⁃ｍｅａｎ 值比较 Ｔａｂｌｅ ４ Ｔｈｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｇ⁃ｍｅａｎ ｉｎ ｄｉｆｆｅｒｅｎｔ ｍｅｔｈｏｄｓ 数据集 Ｃ５．０＋ ＳＭＯＴＥ Ｕｎｄｅｒｓａｍｐｌｅ＋ ＣＳＶＭ Ｍ３⁃ＳＶＭ 本文算法 ｖｅｈｉｃｌｅ ０．８１０ ０．６１２ ０．８１５ ０．９２５ ａｒｔｉｆｉｃｉａｌ ０．７１３ ０．６５４ ０．７５３ ０．７９５ ｖｏｗｅｌ ０．７８７ ０．７６９ ０．９５３ ０．９３９ ｌｅｔｔｅｒ ０．９４０ ０．８６０ ０．８９４ ０．９９２ ａｂａｌｏｎｅ ０．７２０ ０．７８０ ０．８２０ ０．９４０ ｐａｇｅ⁃ｂｌｏｃｋｓ ０．７８６ ０．８９６ ０．７４８ ０．７７５ 平均值 ０．７９３ ０．７６２ ０．８３１ ０．８９４ 根据 Ｆ⁃ｍｅａｓｕｒｅ 的定义，如果算法能够获得较 大的值，则说明算法的少数类查全率和查准率都较 高，有较好的少数类识别性能．从表 ３ 中可以看出， 在所测试的 ６ 个数据集中，所提算法在其中 ４ 个数 据集上的 Ｆ⁃ｍｅａｓｕｒｅ 值都高于其他方法，特别是在 ｐａｇｅ⁃ｂｌｏｃｋｓ 数据集上，与所比较 ３ 种算法中的最佳 结果有将近 １１％的提升．此外，通过计算 ６ 组 ＵＣＩ 数 据在不同方法下的 Ｆ⁃ｍｅａｓｕｒｅ 平均值，也可以看出 本文所提算法明显优于其他方法，在平均值性能上 比次优算法 Ｍ３⁃ＳＶＭ 有将近 ５％的性能提升． Ｇ⁃ｍｅａｎ 的定义说明，其值越大，说明正类分类 准确率和负类分类准确率都越大，也即算法在整体 上的分类性能越好．从整体分类角度比较，本文算法 在 ６ 组数据集上的 Ｇ⁃ｍｅａｎ 度量指标值比次优算法 有 ８％的性能提升． 从 Ｆ⁃ｍｅａｓｕｒｅ 和 Ｇ⁃ｍｅａｎ 的实验结果中同时可 以看出，在处理不平衡分类问题时，随机欠采样与代 价敏感支持向量机相结合方法 ｕｎｄｅｒｓａｍｐｌｅ＋ＣＳＶＭ 分类效果不佳．这是由于为了组成新的平衡训练集， 随机欠采样方法丢弃了许多有用的负类样本信息， 得到的分类超平面明显偏离实际位置，当不平衡度 越高时，其劣势更加明显．此结果也间接表明本文所 提出的通过以 Ｋ 均值聚类质心及其权重因子来代 表众多负类样本的有效性，在组成新平衡训练数据 集的同时，又不致于因改变数据集的数据分布而损 失了负类样本所包含的有用的分类信息． ４ 结束语 本文提出一种 Ｋ 均值聚类与支持向量机相结 合的不平衡数据分类方法———ＷＣＣ⁃ＳＶＭ，该方法在 进行数据预处理后，对训练集上的正负类样本各自 进行无监督的 Ｋ 均值聚类，对每个聚类，以聚类质 心和权重因子代表聚类样本分布和数量，然后进行 基于加权 ＳＶＭ 模型训练．实验结果表明，该方法在 ·２６４· 智 能 系 统 学 报 第 ８ 卷

第3期 胡小生，等：基于加权聚类质心的SVM不平衡分类方法 ·265. 显著降低实际参与模型训练样本数量的同时，能够 [8]AKBANI R,KWEK S,JAPKOWICZ N.Applying support 取得不低于其他采样方法的分类性能，为大规模不 vetor machines to imbalanced datasets[Cl//Proceedings of 平衡数据集分类问题提供了一种新的方法 15th European Conference on Machine Learning.Pisa,Ita- 由于数据集本身的多样性和复杂性，样本的分 1y,2004:39.50. [9]WU G.CHANG E Y.KBA:kernel boundary alignment 布也呈现多样性，如果能估计正负类样本潜在的分 considering imbalanced data distribution[].IEEE Transac- 布，根据不同的潜在分布设置不同的聚类方式，对算 tions on Knowledge and Data Engineering,2005,17(6): 法的分类性能将会提高更多 786-795. 参考文献： [10]ERTEKIN S,HUAN J,BOTTON L,et al.Learning on the border:active learning in imbalanced data classification [1]叶志飞，文益民，吕宝粮不平衡分类问题研究综述[J]. [C]//Proceedings of the ACM Conference on Information 智能系统学报，2009,4(2)：148-156. and Knowledge Management.Lisbon,Portugal,2007: YE Zhifei,WEN Yimin,LO Baoliang.A survey of imbal- 127-136. anced pattern classification problems [J].CAAI Transac- [11]HAN Hui,WANG Wenyuan,MAO Binghuan.Borderline- tions on Intelligent Systems,2009,4(2):148-156. SMOTE:a new over-sampling method in imbalanced data [2]RONALDO C P,GUSTAVO E A,MARIA C M.A study sets leaming[C]//Proceedings of the International Confer- with class imbalance and random sampling for a decision ence on Intelligence Computing.Hefei,China,2005:878- tree learning system[C]//International Conference for In- 887. formation Processing.Milano,Italy,2008:131-140. [12]DASKALAKI S,KOPANAS L.Evaluation of classifiers for [3]WU Junjie,XIONG Hui,WU Peng,et al.Local decompo- an uneven class distribution problem[J].Applied Artificial sition for rare class analysis[C]//Proceedings of the 13th ntelligence,2006,20(5):381-417. ACM SIGKDD International Conference on Knowledge Dis- [13]LO Biaoliang.WANG Kaian,UTIYAMA M,et al.A part- covery and Data Mining.New York,USA:ACM,2007: versus-part method for massively parallel training of support 814-823. vector machines [C]//Proceedings of 17th International [4]HE Haibo,GARCIA E A.Learning from imbalanced data Joint Conference on Neural Networks.Budapest,Hungary, [J].IEEE Transactions on Knowledge and Data Engineer- 2004,1:735-740. ing,2009,21(9):1263-1284. 作者简介： [5]李雄飞，李军，董元方，等.一种新的不平衡数据学习算法 胡小生，男，1978年生，讲师，主要 PCBoot[J].计算机学报，2012,35(2)：203-209. 研究方向为机器学习、数据挖掘、信息 LI Xiongfei,LI Jun,DONG Yuanfang,et al.A new learn- 检索 ing algorithm for imbalanced data-PCBoost [J].Chinese Journal of Computers,2012,35(2):203-209. [6]付忠良.不平衡多分类问题的连续AdaBoost算法研究 [J].计算机研究与发展，2011,48(2)：2326-2333. FU Zhongliang.Real AdaBoost algorithm for multi-class and 钟勇.男，1970年生，教授，博士，主 imbalanced classification problems[J].Journal of Computer 要研究方向为信息检索、云计算 Research and Development,2011,48(2):2326-2333. 7]VEROPOULOS K,CAMPBELL C,CRISTIANINI N.Con- trolling the sensitivity of support vector machines[C]//Pro- ceedings of the International Joint Conference on Artificial Intelligence.San Francisco,USA,1999:55-60

显著降低实际参与模型训练样本数量的同时，能够 取得不低于其他采样方法的分类性能，为大规模不 平衡数据集分类问题提供了一种新的方法． 由于数据集本身的多样性和复杂性，样本的分 布也呈现多样性，如果能估计正负类样本潜在的分 布，根据不同的潜在分布设置不同的聚类方式，对算 法的分类性能将会提高更多． 参考文献： ［１］叶志飞，文益民，吕宝粮．不平衡分类问题研究综述［ Ｊ］． 智能系统学报， ２００９， ４（２）： １４８⁃１５６． ＹＥ Ｚｈｉｆｅｉ， ＷＥＮ Ｙｉｍｉｎ， ＬÜ Ｂａｏｌｉａｎｇ． Ａ ｓｕｒｖｅｙ ｏｆ ｉｍｂａｌ⁃ ａｎｃｅｄ ｐａｔｔｅｒｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２００９， ４（２）：１４８⁃１５６． ［２］ ＲＯＮＡＬＤＯ Ｃ Ｐ， ＧＵＳＴＡＶＯ Ｅ Ａ， ＭＡＲＩＡ Ｃ Ｍ． Ａ ｓｔｕｄｙ ｗｉｔｈ ｃｌａｓｓ ｉｍｂａｌａｎｃｅ ａｎｄ ｒａｎｄｏｍ ｓａｍｐｌｉｎｇ ｆｏｒ ａ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｌｅａｒｎｉｎｇ ｓｙｓｔｅｍ［ Ｃ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｆｏｒ Ｉｎ⁃ ｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ． Ｍｉｌａｎｏ， Ｉｔａｌｙ， ２００８： １３１⁃１４０． ［３］ＷＵ Ｊｕｎｊｉｅ， ＸＩＯＮＧ Ｈｕｉ， ＷＵ Ｐｅｎｇ， ｅｔ ａｌ． Ｌｏｃａｌ ｄｅｃｏｍｐｏ⁃ ｓｉｔｉｏｎ ｆｏｒ ｒａｒｅ ｃｌａｓｓ ａｎａｌｙｓｉｓ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １３ｔｈ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓ⁃ ｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ： ＡＣＭ， ２００７： ８１４⁃８２３． ［４］ＨＥ Ｈａｉｂｏ， ＧＡＲＣＩＡ Ｅ Ａ． Ｌｅａｒｎｉｎｇ ｆｒｏｍ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒ⁃ ｉｎｇ， ２００９， ２１（９）： １２６３⁃１２８４． ［５］李雄飞，李军，董元方，等．一种新的不平衡数据学习算法 ＰＣＢｏｏｔ［Ｊ］．计算机学报， ２０１２， ３５（２）： ２０３⁃２０９． ＬＩ Ｘｉｏｎｇｆｅｉ， ＬＩ Ｊｕｎ， ＤＯＮＧ Ｙｕａｎｆａｎｇ， ｅｔ ａｌ． Ａ ｎｅｗ ｌｅａｒｎ⁃ ｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｍｂａｌａｎｃｅｄ ｄａｔａ—ＰＣＢｏｏｓｔ ［ Ｊ］． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２０１２， ３５（２）： ２０３⁃２０９． ［６］付忠良．不平衡多分类问题的连续 ＡｄａＢｏｏｓｔ 算法研究 ［Ｊ］．计算机研究与发展， ２０１１， ４８（２）： ２３２６⁃２３３３． ＦＵ Ｚｈｏｎｇｌｉａｎｇ． Ｒｅａｌ ＡｄａＢｏｏｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉ⁃ｃｌａｓｓ ａｎｄ ｉｍｂａｌａｎｃｅｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２０１１， ４８（２）： ２３２６⁃２３３３． ［７］ＶＥＲＯＰＯＵＬＯＳ Ｋ， ＣＡＭＰＢＥＬＬ Ｃ， ＣＲＩＳＴＩＡＮＩＮＩ Ｎ． Ｃｏｎ⁃ ｔｒｏｌｌｉｎｇ ｔｈｅ ｓｅｎｓｉｔｉｖｉｔｙ ｏｆ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＵＳＡ， １９９９： ５５⁃６０． ［８］ＡＫＢＡＮＩ Ｒ， ＫＷＥＫ Ｓ， ＪＡＰＫＯＷＩＣＺ Ｎ． Ａｐｐｌｙｉｎｇ ｓｕｐｐｏｒｔ ｖｅｔｏｒ ｍａｃｈｉｎｅｓ ｔｏ ｉｍｂａｌａｎｃｅｄ ｄａｔａｓｅｔｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ １５ｔｈ Ｅｕｒｏｐｅａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｐｉｓａ， Ｉｔａ⁃ ｌｙ， ２００４： ３９⁃５０． ［９］ ＷＵ Ｇ， ＣＨＡＮＧ Ｅ Ｙ． ＫＢＡ： ｋｅｒｎｅｌ ｂｏｕｎｄａｒｙ ａｌｉｇｎｍｅｎｔ ｃｏｎｓｉｄｅｒｉｎｇ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｄｉｓｔｒｉｂｕｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００５， １７（ ６）： ７８６⁃７９５． ［１０］ＥＲＴＥＫＩＮ Ｓ， ＨＵＡＮ Ｊ， ＢＯＴＴＯＮ Ｌ， ｅｔ ａｌ． Ｌｅａｒｎｉｎｇ ｏｎ ｔｈｅ ｂｏｒｄｅｒ： ａｃｔｉｖｅ ｌｅａｒｎｉｎｇ ｉｎ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ． Ｌｉｓｂｏｎ， Ｐｏｒｔｕｇａｌ， ２００７： １２７⁃１３６． ［１１］ＨＡＮ Ｈｕｉ， ＷＡＮＧ Ｗｅｎｙｕａｎ， ＭＡＯ Ｂｉｎｇｈｕａｎ． Ｂｏｒｄｅｒｌｉｎｅ⁃ ＳＭＯＴＥ： ａ ｎｅｗ ｏｖｅｒ⁃ｓａｍｐｌｉｎｇ ｍｅｔｈｏｄ ｉｎ ｉｍｂａｌａｎｃｅｄ ｄａｔａ ｓｅｔｓ ｌｅａｒｎｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｃｏｍｐｕｔｉｎｇ． Ｈｅｆｅｉ， Ｃｈｉｎａ， ２００５： ８７８⁃ ８８７． ［１２］ＤＡＳＫＡＬＡＫＩ Ｓ， ＫＯＰＡＮＡＳ Ｌ． Ｅｖａｌｕａｔｉｏｎ ｏｆ ｃｌａｓｓｉｆｉｅｒｓ ｆｏｒ ａｎ ｕｎｅｖｅｎ ｃｌａｓｓ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｏｂｌｅｍ［Ｊ］． Ａｐｐｌｉｅｄ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００６， ２０（５）： ３８１⁃４１７． ［１３］ＬÜ Ｂｉａｏｌｉａｎｇ， ＷＡＮＧ Ｋａｉａｎ， ＵＴＩＹＡＭＡ Ｍ， ｅｔ ａｌ． Ａ ｐａｒｔ⁃ ｖｅｒｓｕｓ⁃ｐａｒｔ ｍｅｔｈｏｄ ｆｏｒ ｍａｓｓｉｖｅｌｙ ｐａｒａｌｌｅｌ ｔｒａｉｎｉｎｇ ｏｆ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ １７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ． Ｂｕｄａｐｅｓｔ， Ｈｕｎｇａｒｙ， ２００４， １： ７３５⁃７４０． 作者简介： 胡小生，男，１９７８ 年生，讲师，主要 研究方向为机器学习、数据挖掘、信息 检索． 钟勇，男，１９７０ 年生，教授，博士，主 要研究方向为信息检索、云计算． 第 ３ 期 胡小生，等：基于加权聚类质心的 ＳＶＭ 不平衡分类方法 ·２６５·