【机器学习】基于异构距离的集成分类算法研究

第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201807023 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190409.0946.012.html 基于异构距离的集成分类算法研究 张燕，杜红乐 (商洛学院数学与计算机应用学院，陕西商洛726000) 摘要：针对异构数据集下的不均衡分类问题，从数据集重采样、集成学习算法和构建弱分类器3个角度出发， 提出一种针对异构不均衡数据集的分类方法一一HVDM-Adaboost-KNN算法(heterogeneous value difference metric-Adaboost-KNN),该算法首先通过聚类算法对数据集进行均衡处理，获得多个均衡的数据子集，并构建多 个子分类器，采用异构距离计算异构数据集中2个样本之间的距离，提高KNN算法的分类准性能，然后用Ada boost算法进行迭代获得最终分类器。用8组UCI数据集来评估算法在不均衡数据集下的分类性能，Ada- boost实验结果表明，相比Adaboost等算法，F,值、AUC、G-mean等指标在异构不均衡数据集上的分类性能都有 相应的提高。 关键词：异构数据：不均衡数据：异构距离：集成学习：过取样；欠取样 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2019)04-0733-10 中文引用格式：张燕，杜红乐.基于异构距离的集成分类算法研究.智能系统学报，2019,14(4)：733-742 英文引用格式：ZHANG Yan,DU Hongle..Imbalanced heterogeneous data ensemble classification based on HVDM-KNNJ.CAAI transactions on intelligent systems,2019,14(4):733-742 Imbalanced heterogeneous data ensemble classification based on HVDM-KNN ZHANG Yan,DU Hongle (School of Math and Computer Application,Shangluo University,Shangluo 726000,China) Abstract:A novel classification method,the heterogeneous value difference metric-Adaboost-KNN(HVDM-Adaboost- KNN),is proposed to achieve data resampling,to obtain an ensemble learning algorithm,and to construct a weak classi- fier for addressing the imbalanced classification of a heterogeneous dataset.This algorithm initially equalizes the data- set using a clustering algorithm to obtain several equalized data subsets and constructs several sub-classifiers.Further, the heterogeneous distance is used to calculate the distance between two samples in the heterogeneous dataset to im- prove the classification accuracy of the KNN algorithm.Subsequently,the Adaboost algorithm is used to iteratively ob- tain the final classifier.Eight groups of UCI datasets are used to evaluate the classification performance of the algorithm in imbalanced datasets.The Adaboost experimental results denote that the classification performance of indices,such as the FI value,AUC,and G-means,using the heterogeneous imbalanced datasets was better when compared with that ex- hibited by other algorithms. Keywords:heterogeneous data;imbalanced data;heterogeneous value difference metric;ensemble learning;over sampling;undersampling 传统的算法多是面向均衡数据集，有较好的 分类性能，而实际应用中的数据集多是不均衡、 收稿日期：2018-07-22.网络出版日期：2019-04-10. 异构的。面向不均衡数据分类的研究是数据挖 基金项目：陕西省自然科学基础研究计划项目(2015JM6347): 掘、机器学习等领域当前的研究热点之一16，主 陕西省教育厅科技计划项目(15JK1218):商洛学院 科学与技术项目(18sky014):商洛学院科技创新团队 要集中在数据层面和算法层面。 建设项目(18SCX002):商洛学院重点学科建设项 目，学科名：数学”. 数据层面的方法，又称为重采样法，多采 通信作者：杜红乐.E-mail:dhl5597@163.com. 用减少多数类样本或增加少数类样本，使得数据

DOI: 10.11992/tis.201807023 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190409.0946.012.html 基于异构距离的集成分类算法研究 张燕，杜红乐 （商洛学院 数学与计算机应用学院，陕西 商洛 726000） 摘 要：针对异构数据集下的不均衡分类问题，从数据集重采样、集成学习算法和构建弱分类器 3 个角度出发， 提出一种针对异构不均衡数据集的分类方法——HVDM-Adaboost-KNN 算法 (heterogeneous value difference metric-Adaboost-KNN)，该算法首先通过聚类算法对数据集进行均衡处理，获得多个均衡的数据子集，并构建多 个子分类器，采用异构距离计算异构数据集中 2 个样本之间的距离，提高 KNN 算法的分类准性能，然后用 Ada￾boost 算法进行迭代获得最终分类器。用 8 组 UCI 数据集来评估算法在不均衡数据集下的分类性能，Ada￾boost 实验结果表明，相比 Adaboost 等算法，F1 值、AUC、G-mean 等指标在异构不均衡数据集上的分类性能都有 相应的提高。 关键词：异构数据；不均衡数据；异构距离；集成学习；过取样；欠取样 中图分类号：TP391.4 文献标志码：A 文章编号：1673−4785(2019)04−0733−10 中文引用格式：张燕, 杜红乐. 基于异构距离的集成分类算法研究 [J]. 智能系统学报, 2019, 14(4): 733–742. 英文引用格式：ZHANG Yan, DU Hongle. Imbalanced heterogeneous data ensemble classification based on HVDM-KNN[J]. CAAI transactions on intelligent systems, 2019, 14(4): 733–742. Imbalanced heterogeneous data ensemble classification based on HVDM-KNN ZHANG Yan，DU Hongle (School of Math and Computer Application, Shangluo University, Shangluo 726000, China) Abstract: A novel classification method, the heterogeneous value difference metric-Adaboost-KNN (HVDM-Adaboost￾KNN), is proposed to achieve data resampling, to obtain an ensemble learning algorithm, and to construct a weak classi￾fier for addressing the imbalanced classification of a heterogeneous dataset. This algorithm initially equalizes the data￾set using a clustering algorithm to obtain several equalized data subsets and constructs several sub-classifiers. Further, the heterogeneous distance is used to calculate the distance between two samples in the heterogeneous dataset to im￾prove the classification accuracy of the KNN algorithm. Subsequently, the Adaboost algorithm is used to iteratively ob￾tain the final classifier. Eight groups of UCI datasets are used to evaluate the classification performance of the algorithm in imbalanced datasets. The Adaboost experimental results denote that the classification performance of indices, such as the F1 value, AUC, and G-means, using the heterogeneous imbalanced datasets was better when compared with that ex￾hibited by other algorithms. Keywords: heterogeneous data; imbalanced data; heterogeneous value difference metric; ensemble learning; over sampling; undersampling 传统的算法多是面向均衡数据集，有较好的 分类性能，而实际应用中的数据集多是不均衡、 异构的。面向不均衡数据分类的研究是数据挖 掘、机器学习等领域当前的研究热点之一[1-16] ，主 要集中在数据层面[1-8] 和算法层面[9-16]。 数据层面的方法[1-5] ，又称为重采样法，多采 用减少多数类样本或增加少数类样本，使得数据 收稿日期：2018−07−22. 网络出版日期：2019−04−10. 基金项目：陕西省自然科学基础研究计划项目 (2015JM6347)； 陕西省教育厅科技计划项目 (15JK1218)；商洛学院 科学与技术项目 (18sky014)；商洛学院科技创新团队 建设项目 (18SCX002)；商洛学院重点学科建设项 目，学科名：数学”. 通信作者：杜红乐. E-mail：dhl5597@163.com. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019

·734· 智能系统学报 第14卷 集均衡化，过采样是依据少数类样本的空间特 data ensemble classification based on HVDM-KNN, 征，通过一定的方法增加少数类样本数量，该方 HK-Adaboost算法)，提高异构不均衡数据下的分 法容易导致过拟合，为此许多研究者提出了解决 类性能。该算法首先用聚类算法把数据集划分为 方法，例如合成少数类样本过采样技术(synthetic 多个均衡的数据子集，对于每个子集采用基于异 minority oversampling technique,.SMOTE)及对 构距离的KNN算法，然后用Adaboost算法对弱 SMOTE的改进算法；欠采样-则是通过一定的 分类器进行训练，然后依据一定的评价指标进行 方法删除多数类样本中信息重复或者包含信息量 调整，获得最终的强分类器。 较少的样本，但由于计算方法的不同，会删除包 1相关概念 含丰富信息的样本，导致欠学习，为此研究者结 合集成学习和重采样思想，不删除样本，而是对 1.1异构距离 多数类样本按照一定策略进行抽取，然后与少数 定义1异构不均衡数据(heterogeneous data): 类样本一起构成训练子集切。 设数据集X上的每条记录共有m个属性，k(0< 算法层面的方法则是提出新方法或者改进已 k<m)个属性取值为连续值，其余m-k个属性取值 有算法，减少数据不均衡对分类性能的影响，主 为离散值，则称该数据集为异构数据集，若该数 要包括代价敏感学习、单类学习、集成学习oW 据集中类样本数量有较大差异，则称数据集为异 等。其中集成学习方法是通过迭代逐步把弱分类 构不均衡数据集。 器提升为强分类器，能够较好的提高分类器的性 根据样本到类中心的距离判断样本的类别， 能，也是解决不均衡分类问题的常用方法，在一 其实质就是计算样本与类的相似度，然而欧氏距 些领域得到应用5。文献1首先将数据集划 离以及其它距离都不能准确度量异构数据集中记 分为多个均衡的子集，训练各个子集获得多个分 录的相似度。为了有效度量异构数据之间的相似 类器，然后把多个分类器按照一定的规则（文中 度，实现数据分类，Wilson等I提出HVDM(het-. 给出5种集成规则)进行集成，从而提高分类性 erogeneous value difference metric)距离函数，能够 能，该方法中对数据集的划分方法对最终的分类 反映出不同属性对相似度的影响，有效度量数据 器性能有较大的影响，为此，文献[5]中通过聚类 之间的差异，其定义如下： 对多数类样本进行欠取样，获得与少数类样本数 定义2异构距离：设xy∈X,则x,y之间的异 量相同的样本，然后采用Adaboost算法获得最终 构距离Hxy)定义为 分类器，该方法保证所选样本的空间分布，但不 能对分类错误样本和正确样本进行区别对待，而 H(x,y) d(xj.y) (1) 文献[6]利用抽样概率进行抽样，通过迭代不断 式中： 修正抽样概率，对于分类错误的样本加大抽样概 1,xjoryj 率，而分类正确的样本减小抽样概率，目的是争 d,(xy）= dvdm(xj,yi), xy为离散属性 (2) 取下轮迭代中能选中进行学习。因此，本文方法 dan(xj.yj). y为连续属性 既要充分考虑样本的空间分布，又要考虑到正确 dain(xjyj)= - 分类和错误分类样本之间的区别，采用聚类和抽 40j (3) 样概率的方式进行数据集的划分，获得多个均衡 Naxi Nayi (4) 的数据子集。 i=1 KNN算法是一种简单而有效的分类算法，通 式中：σ，为数据集上第j个属性的方差；N.是数 过计算与样本最近的K个样本的类别来判断样 据集X上第a个属性取值为x的记录数；N为数 本的类别，计算样本的K近邻经常采用欧氏距 据集X上第a个属性取值为x且类别为i的记录 离、相关距离等，而对于异构数据集下，这些距离 数。可以看到，异构距离依据数据集上每个属性 不能准确的表达样本的相似程度，针对此问题， 的统计信息，而不是简单的2个属性的差值，在异 Wilson等u提出了异构距离，可以更准确的度量 构数据集上能够更加准确的描述2个样本之间的 异构数据下2个样本之间的相似度，因此，本文采 差异。 用基于异构距离的KNN算法作为弱分类器。 1.2KNN算法 基于以上分析，本文提出一种面向不均衡异 K-近邻算法通过取测试样本的K个近邻，然 构数据的集成学习算法(imbalanced heterogeneous 后依据K个近邻的类别进行投票，确定测试样本

集均衡化，过采样[1-3] 是依据少数类样本的空间特 征，通过一定的方法增加少数类样本数量，该方 法容易导致过拟合，为此许多研究者提出了解决 方法，例如合成少数类样本过采样技术 (synthetic minority oversampling technique,SMOTE) 及对 SMOTE 的改进算法；欠采样[5-6] 则是通过一定的 方法删除多数类样本中信息重复或者包含信息量 较少的样本，但由于计算方法的不同，会删除包 含丰富信息的样本，导致欠学习，为此研究者结 合集成学习和重采样思想，不删除样本，而是对 多数类样本按照一定策略进行抽取，然后与少数 类样本一起构成训练子集[7]。 算法层面的方法则是提出新方法或者改进已 有算法，减少数据不均衡对分类性能的影响，主 要包括代价敏感学习[8-9] 、单类学习、集成学习[10-14] 等。其中集成学习方法是通过迭代逐步把弱分类 器提升为强分类器，能够较好的提高分类器的性 能，也是解决不均衡分类问题的常用方法，在一 些领域得到应用[15-16]。文献 [11] 首先将数据集划 分为多个均衡的子集，训练各个子集获得多个分 类器，然后把多个分类器按照一定的规则 (文中 给出 5 种集成规则) 进行集成，从而提高分类性 能，该方法中对数据集的划分方法对最终的分类 器性能有较大的影响，为此，文献 [5] 中通过聚类 对多数类样本进行欠取样，获得与少数类样本数 量相同的样本，然后采用 Adaboost 算法获得最终 分类器，该方法保证所选样本的空间分布，但不 能对分类错误样本和正确样本进行区别对待，而 文献 [6] 利用抽样概率进行抽样，通过迭代不断 修正抽样概率，对于分类错误的样本加大抽样概 率，而分类正确的样本减小抽样概率，目的是争 取下轮迭代中能选中进行学习。因此，本文方法 既要充分考虑样本的空间分布，又要考虑到正确 分类和错误分类样本之间的区别，采用聚类和抽 样概率的方式进行数据集的划分，获得多个均衡 的数据子集。 KNN 算法是一种简单而有效的分类算法，通 过计算与样本最近的 K 个样本的类别来判断样 本的类别，计算样本的 K 近邻经常采用欧氏距 离、相关距离等，而对于异构数据集下，这些距离 不能准确的表达样本的相似程度，针对此问题， Wilson 等 [18] 提出了异构距离，可以更准确的度量 异构数据下 2 个样本之间的相似度，因此，本文采 用基于异构距离的 KNN 算法作为弱分类器。 基于以上分析，本文提出一种面向不均衡异 构数据的集成学习算法 (imbalanced heterogeneous data ensemble classification based on HVDM-KNN, HK-Adaboost 算法)，提高异构不均衡数据下的分 类性能。该算法首先用聚类算法把数据集划分为 多个均衡的数据子集，对于每个子集采用基于异 构距离的 KNN 算法，然后用 Adaboost 算法对弱 分类器进行训练，然后依据一定的评价指标进行 调整，获得最终的强分类器。 1 相关概念 1.1 异构距离 定义 1 异构不均衡数据 (heterogeneous data)： 设数据集 X 上的每条记录共有 m 个属性，k(0< k<m) 个属性取值为连续值，其余 m-k 个属性取值 为离散值，则称该数据集为异构数据集，若该数 据集中类样本数量有较大差异，则称数据集为异 构不均衡数据集。 根据样本到类中心的距离判断样本的类别， 其实质就是计算样本与类的相似度，然而欧氏距 离以及其它距离都不能准确度量异构数据集中记 录的相似度。为了有效度量异构数据之间的相似 度，实现数据分类，Wilson 等 [18] 提出 HVDM(het￾erogeneous value difference metric) 距离函数，能够 反映出不同属性对相似度的影响，有效度量数据 之间的差异，其定义如下： 定义 2 异构距离：设x, y ∈ X，则 x，y 之间的异 构距离 H(x,y) 定义为 H(x, y) = vt∑m i=1 d 2 j (xj , yj) (1) 式中： dj(xj , yj) =    1, xj or yj dvdm(xj , yj), xj , yj为离散属性 ddiff(xj , yj), xj , yj为连续属性 (2) ddiff(xj , yj) = |xj −yj | 4σj (3) dvdm(xj , yj) = ∑k i=1 | Na,x,i Na,x − Na,y,i Na,y | (4) σj Na,x xa Na,x,i xa 式中： 为数据集上第 j 个属性的方差； 是数 据集 X 上第 a 个属性取值为 的记录数； 为数 据集 X 上第 a 个属性取值为 且类别为 i 的记录 数。可以看到，异构距离依据数据集上每个属性 的统计信息，而不是简单的 2 个属性的差值，在异 构数据集上能够更加准确的描述 2 个样本之间的 差异。 1.2 KNN 算法 K-近邻算法通过取测试样本的 K 个近邻，然 后依据 K 个近邻的类别进行投票，确定测试样本 ·734· 智 能 系 统 学 报 第 14 卷

第4期 张燕，等：基于异构距离的集成分类算法研究 ·735· 的类别，由于算法简单、易于实现等特点，被广泛 train_data=((xiy)),xE R",yiEY=(-1,1) 应用。KNN是依据K个近邻的类别决定测试样 l)把数据集分为min data和maj data,并计算 本的类别，因此K个近邻的选取将影响算法的性 2类样本数量min num和maj_num; 能，与测试样本越相近实质就是与测试样本越相 2)若maj_num<min_num,终止，train data为最 似，而计算相似度可以采用距离、夹角余弦等方 终数据集；否则调用Cluster(maj_data,min_num),获 法，基于距离相似度中常采用欧氏距离，尤其是 得min num个簇； 对连续属性的向量之间，能较好的度量2个向量 3)分别从min num个簇中放回抽取一个样 间的相似程度。而对于既有数值属性又有字符属 本，与少数类样本一起构成数据子集Bm。 性的异构数据，采用欧氏距离不能准确描述2个 输出获得m个均衡的子集Bm={(1y), 向量间的相似程度，而实际应用中的数据有相当 (x2,y2),…,(x1,}。 部分属于这样的异构数据集，进行训练、分类时 2HK-Adaboost算法 多是采用简单的数字替换，把数据集转换为数值 型的向量，例如red、blue、yellow3种颜色，若用 算法需要依据每个子分类器的分类性能计算 l、2、3进行代替，原来red与blue之间的差别与 每个子分类器的权重，这里采用子分类器的分类 red与yellow之间的差别是相同的，但是用数字替 错误率描述子分类器的权重，子分类器的权重表 换后的距离计算中，(1-2)与(1-3)2间的差别是不 示为 相同的，因此本文的KNN算法中采用文献[18] (5) 给出的异构距离作为度量选择K个近邻样本。 w=na-600 1.3数据均衡化 式中：G=∑，DD≠（表示子分类器的分类错 在集成学习中，对多个训练集进行训练获得 误率。 分类器，然后把分类器进行集成，Adaboost算法是 在第1轮迭代中需要更新样本的权重，改变 通过修改每个样本的权重，改变原有的数据分布 子分类器的分类性能，新样本的权重依据式 从而得到新的训练集，但是该方法无法改变2类 (6)进行更新： 样本数量不成比例的问题，为此，文献[11]提出 D((j)=D.exp(-wyjh(xj))/zn (6) 一种新的面向不均衡数据的集成方法，把多数类 每轮迭代结束，对分类器进行集成时，要考虑 样本划分为多个与少数类样本规模相当的子集， 上轮所获得的分类器和本轮分类器进行集成，集 然后与少数类样本一起构成多个均衡的子集，该 成方法如下： 方法的关键是如何对多数类样本进行划分；文献[⑤] 6=A(+∑ (7) 采用K均值聚类，产生与少数类样本数量相同的 =1 簇数，用簇代表原来的多数类样本，从而对数据 计算每轮迭代结束所获得分类器的分类性能 进行均衡化，该方法会导致丢掉较多的样本，进 提升情况，并获得该轮迭代后的分类器： 而导致出现欠学习现象；文献[6]中依据抽样概 H,(x)=H(x),t arg max() (8) 率从多数类样本中随机抽取与少数类样本数量相 对H,(x)的分类性能表示为 等的样本，与少数类一起构成训练集，这样同样 a=1- 2- (9) 会导致丢掉较多的样本，为此，文中采用迭代的 方式多次抽取，每次抽取都会修改样本的抽样概 迭代结束后获得最终分类器为 率，一方面该方法仍然会有部分样本不被选中， 另一方面，抽取的样本无法保持原有数据的空间 na-on (10) 分布，为此本文采用先聚类再抽取的方式对多数 算法2的详细过程如下： 类样本进行划分，划分方法如算法1。 算法2HK-Adaboost算法 该方法抽取的样本包含有对应簇的空间信 输入数据集train data={(x,yh,∈R,:∈Y= 息，使得针对每个子集获得的分类器有较好的分 (-1,1,迭代次数T,基础分类器C。 类性能，另外选取合理的m值，几乎不会有样本 不被抽取，并且抽取的样本与多数类样本有相似 输出最终分类器为国=g吃∑a 的空间分布。 1)用K均值聚类算法对数据集进得划分，获 算法1数据划分 得m个均衡的子集Bm={(x1y),(2y2),…,(x7): 输入数据集 2)初始化样本权重：D1m=(d1m,d2m,…,dm)=1/l

的类别，由于算法简单、易于实现等特点，被广泛 应用。KNN 是依据 K 个近邻的类别决定测试样 本的类别，因此 K 个近邻的选取将影响算法的性 能，与测试样本越相近实质就是与测试样本越相 似，而计算相似度可以采用距离、夹角余弦等方 法，基于距离相似度中常采用欧氏距离，尤其是 对连续属性的向量之间，能较好的度量 2 个向量 间的相似程度。而对于既有数值属性又有字符属 性的异构数据，采用欧氏距离不能准确描述 2 个 向量间的相似程度，而实际应用中的数据有相当 部分属于这样的异构数据集，进行训练、分类时 多是采用简单的数字替换，把数据集转换为数值 型的向量，例如 red、blue、yellow 3 种颜色，若用 1、2、3 进行代替，原来 red 与 blue 之间的差别与 red 与 yellow 之间的差别是相同的，但是用数字替 换后的距离计算中，(1−2)2 与 (1−3)2 间的差别是不 相同的，因此本文的 KNN 算法中采用文献 [18] 给出的异构距离作为度量选择 K 个近邻样本。 1.3 数据均衡化 在集成学习中，对多个训练集进行训练获得 分类器，然后把分类器进行集成，Adaboost 算法是 通过修改每个样本的权重，改变原有的数据分布 从而得到新的训练集，但是该方法无法改变 2 类 样本数量不成比例的问题，为此，文献 [11] 提出 一种新的面向不均衡数据的集成方法，把多数类 样本划分为多个与少数类样本规模相当的子集， 然后与少数类样本一起构成多个均衡的子集，该 方法的关键是如何对多数类样本进行划分；文献 [5] 采用 K 均值聚类，产生与少数类样本数量相同的 簇数，用簇代表原来的多数类样本，从而对数据 进行均衡化，该方法会导致丢掉较多的样本，进 而导致出现欠学习现象；文献 [6] 中依据抽样概 率从多数类样本中随机抽取与少数类样本数量相 等的样本，与少数类一起构成训练集，这样同样 会导致丢掉较多的样本，为此，文中采用迭代的 方式多次抽取，每次抽取都会修改样本的抽样概 率，一方面该方法仍然会有部分样本不被选中， 另一方面，抽取的样本无法保持原有数据的空间 分布，为此本文采用先聚类再抽取的方式对多数 类样本进行划分，划分方法如算法 1。 该方法抽取的样本包含有对应簇的空间信 息，使得针对每个子集获得的分类器有较好的分 类性能，另外选取合理的 m 值，几乎不会有样本 不被抽取，并且抽取的样本与多数类样本有相似 的空间分布。 算法 1 数据划分 输入 数据集 train_data = {(xi , yi)}, xi ∈ R n , yi ∈ Y = {−1,1} min_data maj_data min_num maj_num 1) 把数据集分为 和 ，并计算 2 类样本数量 和 ； maj_num < min_num train_data maj_data min_num min_num 2) 若 ，终止， 为最 终数据集；否则调用 Cluster( , )，获 得 个簇； min_num Bm 3) 分别从 个簇中放回抽取一个样 本，与少数类样本一起构成数据子集 。 Bm = {(x1, y1), (x2, y2),··· ,(xl , yl)} 输 出 获 得 m 个均衡的子集 。 2 HK-Adaboost 算法 算法需要依据每个子分类器的分类性能计算 每个子分类器的权重，这里采用子分类器的分类 错误率描述子分类器的权重，子分类器的权重表 示为 w t i = 1 2 ln((1−e t i )/e t i ) (5) e t i = ∑l i=1 Dti[y , h t i 式中： (x)] 表示子分类器的分类错 误率。 在第 t 轮迭代中需要更新样本的权重，改变 子分类器的分类性能，新样本的权重依据 式 (6) 进行更新： D(t+1)i(j) = Dti exp(−w t i yjh t i (xj))/zti (6) 每轮迭代结束，对分类器进行集成时，要考虑 上轮所获得的分类器和本轮分类器进行集成，集 成方法如下： H t i (x) = Ht−1(x)+ ∑T t=1 w t ih t i (x) (7) 计算每轮迭代结束所获得分类器的分类性能 提升情况，并获得该轮迭代后的分类器： Ht(x) = H t i (x),t = argmax(σti) (8) 对 Ht(x) 的分类性能表示为 at = 1− 1 2l ∑l i=1 |Ht(xi)−yi | (9) 迭代结束后获得最终分类器为 H(x) = 1 Z ∑t i=1 aiHi(x) (10) 算法 2 的详细过程如下： 算法 2 HK-Adaboost 算法 train_data = {(xi , yi)}, xi ∈ R n , yi ∈ Y = {−1,1} 输入 数据集 ，迭代次数 T，基础分类器 C。 H(x) = sign( 1 Z ∑t i=1 输出 最终分类器为 aiHi(x))。 Bm = {(x1, y1),(x2, y2),··· ,(xl , yl)} 1) 用 K 均值聚类算法对数据集进行划分，获 得 m 个均衡的子集 ； 2) 初始化样本权重： D1m = (d1m,d2m,··· ,dlm) = 1/l， 第 4 期 张燕，等：基于异构距离的集成分类算法研究 ·735·

·736· 智能系统学报 第14卷 m表示第m个子集； mean、AUC等，本文算法中采用与Adaboost一致 for =1:T 的评价方式-分类错误率。 3)for i=1:M 式（⑤）是依据分类器对样本的分类错误样本 调用分类器C(B,D)训练并获得第i个子 的权重之和计算分类器的权重，然后依据Ada- 集上的子分类器： boost算法中更新样本权重的思想，应用式(6)更 利用式（⑤）计算每个分类器权重： 新每个样本的权重，第1轮迭代结束。 利用式(6)对各子集中样本进行权重更新； 4)是计算第1次迭代结束后获得的分类器， 利用式(7获得本轮结束时分类器H(x: 如果分类效果比上次迭代好，则进行后面步骤， end for i 否则丢弃该次迭代产生分类器。这里从m个子 4)计算所得各子分类器(x)与上轮所得分类 分类器中选择提升效果最好的分类器作为第1次 器的提升效果：oi=H(x)-H-(x): 迭代后的分类器，提升效果的评价仍然可以采用 若分类效果没有提升，则结束该子集上的迭 F1值、G-mean、AUC等评价指标进行评价，本文 代，若有提升，则依据公式(8)选择提升效果最好 为简化算法，仍采用准确率作为评价指标，获得 的分类器作为第1次迭代后的分类器； 本轮迭代的分类器。然后计算本轮所得分类器的 利用公式(9)计算分类器的分类性能a: 分类性能，并计算本轮迭代所得分类器在最终分 类器中的权重。 end for t 5)获得最终分类器，是每轮迭代所得分类器 5)利用式(10)获得最终分类器H(x)。 1)中，利用K均值聚类算法对多数类样本进 的加权和，其中2为归一化因子，这里取Z=4。 行聚类，K值为少数类样本数，得到K个簇，然后 采用有放回抽样，从每个簇中随机取出一个样 3实验分析 本，与少数量样本一起构成一个均衡的训练子 本文选择8组不同的数据集进行实验，8组 集，然后重复该步骤，产生m个均衡的训练子集。 数据集来自UCI数据库，Car Evaluation、TIC- 2)是对每个训练子集中的每个样本赋予权 TAC-Toe Endgame、Liver Disorders、Breast Cancer、 值，初始权值都相等。 Haberman's Survival,Blood transfusion,Contra- 3)是第1次迭代时，每个训练子集上的训练 ceptive Method Choice Teaching Assistant Evalu- 过程，依据Adaboost算法思想，对每个子集上的 ation,所选实验数据集的详细信息如表1所示，可 每个样本的权重进行更新，当第1次迭代结束后 以看到数据集在一定程度上都是不均衡的，并且 获得的分类器为第1-1次迭代获得分类器与第 数据集的各个属性是不连续的，另外本文算法是 i个子集上前-1次迭代获得的分类器的加权和。 针对2类分类的，因此把数据集都转化为2类的 每个分类器的分类性能评价指标可以是F,值、G- 数据集1,1 表1实验数据集 Table 1 dataset 序号 数据集 属性 属性类别 多数类 少数类 比例 1 Car 6 6离散 1210 384 3.15 2 Tic-Tac-To 9 9离散 626 332 1.89 3 Liver 7 7整数 200 145 1.38 Breast 9 8离散，1整数 201 85 2.36 Haberman 3 3整数 225 81 2.78 6 Blood 4 4整数 570 178 3.20 Contraceptive 9 2整数，7离散 844 300 2.81 8 Teaching 5 5整数 102 49 2.08 3.1实验评价指标 类样本的分类情况，这种基于相同错分代价的评 针对均衡数据的分类多采用分类精度作为评 价指标不能很好描述分类性能。针对不均衡数据 价指标，而对于不均衡数据，更多关注的是少数 分类的评价指标多采用Recall、Precision、F-mean

m 表示第 m 个子集； for t=1:T 3) for i=1:M C(Bi , Dti) h t i 调用分类器 训练并获得第 i 个子 集上的子分类器 ； 利用式 (5) 计算每个分类器权重； 利用式 (6) 对各子集中样本进行权重更新； Ht i 利用式 (7) 获得本轮结束时分类器 (x) ； end for i Ht i (x) σti = Ht i (x)− Ht−1(x) 4) 计算所得各子分类器 与上轮所得分类 器的提升效果： ； 若分类效果没有提升，则结束该子集上的迭 代，若有提升，则依据公式 (8) 选择提升效果最好 的分类器作为第 t 次迭代后的分类器； 利用公式 (9) 计算分类器的分类性能at； end for t 5) 利用式 (10) 获得最终分类器 H(x)。 1) 中，利用 K 均值聚类算法对多数类样本进 行聚类，K 值为少数类样本数，得到 K 个簇，然后 采用有放回抽样，从每个簇中随机取出一个样 本，与少数量样本一起构成一个均衡的训练子 集，然后重复该步骤，产生 m 个均衡的训练子集。 2) 是对每个训练子集中的每个样本赋予权 值，初始权值都相等。 3) 是第 t 次迭代时，每个训练子集上的训练 过程，依据 Adaboost 算法思想，对每个子集上的 每个样本的权重进行更新，当第 t 次迭代结束后 获得的分类器为第 t-1 次迭代获得分类器与第 i 个子集上前 t-1 次迭代获得的分类器的加权和。 每个分类器的分类性能评价指标可以是 F1 值、G￾mean、AUC 等，本文算法中采用与 Adaboost 一致 的评价方式-分类错误率。 式 (5) 是依据分类器对样本的分类错误样本 的权重之和计算分类器的权重，然后依据 Ada￾boost 算法中更新样本权重的思想，应用式 (6) 更 新每个样本的权重，第 t 轮迭代结束。 4) 是计算第 t 次迭代结束后获得的分类器， 如果分类效果比上次迭代好，则进行后面步骤， 否则丢弃该次迭代产生分类器。这里从 m 个子 分类器中选择提升效果最好的分类器作为第 t 次 迭代后的分类器，提升效果的评价仍然可以采用 F1 值、G-mean、AUC 等评价指标进行评价，本文 为简化算法，仍采用准确率作为评价指标，获得 本轮迭代的分类器。然后计算本轮所得分类器的 分类性能，并计算本轮迭代所得分类器在最终分 类器中的权重。 Z Z = ∑t i=1 at 5) 获得最终分类器，是每轮迭代所得分类器 的加权和，其中 为归一化因子，这里取 。 3 实验分析 本文选择 8 组不同的数据集进行实验，8 组 数据集来自 UCI 数据库，Car Evaluation、TIC￾TAC-Toe Endgame、Liver Disorders、Breast Cancer、 Haberman’s Survival、Blood transfusion、Contra￾ceptive Method Choice 和 Teaching Assistant Evalu￾ation，所选实验数据集的详细信息如表 1 所示，可 以看到数据集在一定程度上都是不均衡的，并且 数据集的各个属性是不连续的，另外本文算法是 针对 2 类分类的，因此把数据集都转化为 2 类的 数据集[17,19]。 表 1 实验数据集 Table 1 dataset 序号 数据集 属性 属性类别 多数类 少数类 比例 1 Car 6 6离散 1 210 384 3.15 2 Tic-Tac-To 9 9离散 626 332 1.89 3 Liver 7 7整数 200 145 1.38 4 Breast 9 8离散，1整数 201 85 2.36 5 Haberman 3 3整数 225 81 2.78 6 Blood 4 4整数 570 178 3.20 7 Contraceptive 9 2整数，7离散 844 300 2.81 8 Teaching 5 5整数 102 49 2.08 3.1 实验评价指标 针对均衡数据的分类多采用分类精度作为评 价指标，而对于不均衡数据，更多关注的是少数 类样本的分类情况，这种基于相同错分代价的评 价指标不能很好描述分类性能。针对不均衡数据 分类的评价指标多采用 Recall、Precision、F-mean、 ·736· 智 能 系 统 学 报 第 14 卷

第4期 张燕，等：基于异构距离的集成分类算法研究 ·737· G-mean、ROC曲线和AUC等，这些性能指标是基 mean的值都会较小，因此能够较好评价不均衡数 于混淆矩阵来计算的，对于二分类问题的混淆矩 据集下的分类性能。 阵如表2所示。 ROC曲线则是以正负类的召回率为坐标轴， 表2混淆矩阵 通过调整分类器的阈值而获得一系列值对应的曲 Table 2 Obfuscation matrix 线，由于ROC曲线不能定量评价分类器的分类性 类别 预测正类 预测负类 能，因此常采用ROC曲线下的面积AUC来评价 正类 TP FN 分类器的分类性能，AUC值越大代表分类器的分 负类 FP TN 类性能越好，本文实验主要从上面所列评价指标 来对比算法的性能。 依据混淆矩阵可以计算上面评价指标的计算 3.2异构距离有效性验证 公式： 表3中HDVM KNN是指采用HDVM距离 TP Recall= TP+FN (11) 的K近邻算法，KNN指采用欧氏距离的K近邻算 TP 法，其中K取值为5的实验结果，SVM是依据动 Precision (12) TP+FP 态错分代价的支持向量机算法，SVM和KNN是 F= 2xPrecisionx Recall 对数据进行归一化操作后采用matlab中自带的支 (13) Precision+Recall 持向量机算法进行实验的结果，Car数据集的实 TN TP G-mean 验是从数据集中隔一条记录取一条的方式选取训 √TN+币×TP+ (14) 练集，用全部样本作为测试集的结果，其他数据 Recall表示正类的查全率；Precision表示正类 集均是全部数据既是训练集又是测试集的结果。 的查准率；F-mean同时考虑查全率和查准率，只 实验结果主要依据常见的性能指标样本准确率 有当两个都大时F-mean的值才较大，可以较好的 ACC、Recall、Precision、F-mean、G-mean和AUC 描述不均衡数据集下的分类性能；G-mean综合考 验证算法的性能，实验更加关注少数类样本的分 虑2类的准确率，任何一类准确率较低时，G- 类性能。 表3实验结果 Table 3 Experimental result 性能指标 数据集 算法 ACC Recall Precision AUC F mean G mean HDVM KNN 0.8959 0.7466 0.9074 0.8828 0.7990 0.8436 Car KNN 0.8864 0.7067 0.8810 0.8752 0.7931 0.8264 SVM 0.6236 0.3778 0.5455 0.6774 0.5268 0.5926 HDVM KNN 0.9553 0.9054 0.9040 0.9059 0.8535 0.9044 Tic-Tac-Toe KNN 0.9329 0.7879 0.7724 0.7812 0.5887 0.7781 SVM 0.5972 0.4295 0.5877 0.5971 0.4929 0.5584 HDVM KNN 0.9188 0.9034 0.9300 0.9311 0.9034 0.9166 Liver KNN 0.7855 0.8034 0.8850 0.7898 0.7176 0.7898 SVM 0.6841 0.6098 0.6800 0.6751 0.6472 0.6769 HDVM_KNN 0.7797 0.7273 0.9303 0.6990 0.5714 0.7652 Breast KNN 0.7902 0.7200 0.9254 0.6553 0.5333 0.7553 SVM 0.7168 0.5208 0.7711 0.5009 0.5525 0.6518 HDVM KNN 0.8431 0.7797 0.9422 0.7913 0.6571 0.8180 Haberman KNN 0.7974 0.7111 0.9422 0.7676 0.5079 0.7600 SVM 0.7386 0.5079 0.8622 0.6791 0.4444 0.6368 HDVM_KNN 0.8476 0.7759 0.9544 0.8712 0.6122 0.8172 Blood KNN 0.8195 0.6937 0.9404 0.8496 0.5329 0.7640 SVM 0.4933 0.3093 0.3614 0.8067 0.4624 0.5369 HDVM KNN 0.8637 0.7797 0.7712 0.6610 0.7072 0.7731 Contraceptive KNN 0.7536 0.6986 0.7590 0.7563 0.7309 0.7533 SVM 0.7583 0.6311 0.6714 0.7743 0.5905 0.6626 HDVM KNN 0.8922 0.7963 0.8874 0.8868 0.8350 0.8643 Teaching KNN 0.8039 0.5652 0.7152 0.6667 0.5474 0.6644 SVM 0.1078 0.3406 0.3841 0.6093 0.5027 0.5368

G-mean、ROC 曲线和 AUC 等，这些性能指标是基 于混淆矩阵来计算的，对于二分类问题的混淆矩 阵如表 2 所示。 表 2 混淆矩阵 Table 2 Obfuscation matrix 类别 预测正类 预测负类 正类 TP FN 负类 FP TN 依据混淆矩阵可以计算上面评价指标的计算 公式： Recall = TP TP+FN (11) Pr ecision = TP TP+FP (12) F1 = 2×Pr ecision×Recall Pr ecision+Recall (13) G−mean = √ TN TN+FP × TP TP+FN (14) Recall 表示正类的查全率；Precision 表示正类 的查准率；F-mean 同时考虑查全率和查准率，只 有当两个都大时 F-mean 的值才较大，可以较好的 描述不均衡数据集下的分类性能；G-mean 综合考 虑 2 类的准确率，任何一类准确率较低时， G￾mean 的值都会较小，因此能够较好评价不均衡数 据集下的分类性能。 ROC 曲线则是以正负类的召回率为坐标轴， 通过调整分类器的阈值而获得一系列值对应的曲 线，由于 ROC 曲线不能定量评价分类器的分类性 能，因此常采用 ROC 曲线下的面积 AUC 来评价 分类器的分类性能，AUC 值越大代表分类器的分 类性能越好，本文实验主要从上面所列评价指标 来对比算法的性能。 3.2 异构距离有效性验证 表 3 中 HDVM_KNN 是指采用 HDVM 距离 的 K 近邻算法，KNN 指采用欧氏距离的 K 近邻算 法，其中 K 取值为 5 的实验结果，SVM 是依据动 态错分代价的支持向量机算法，SVM 和 KNN 是 对数据进行归一化操作后采用 matlab 中自带的支 持向量机算法进行实验的结果，Car 数据集的实 验是从数据集中隔一条记录取一条的方式选取训 练集，用全部样本作为测试集的结果，其他数据 集均是全部数据既是训练集又是测试集的结果。 实验结果主要依据常见的性能指标样本准确率 ACC、Recall、Precision、F-mean、G-mean 和 AUC 验证算法的性能，实验更加关注少数类样本的分 类性能。 表 3 实验结果 Table 3 Experimental result 数据集 算法 性能指标 ACC Recall Precision AUC F_mean G_mean Car HDVM_KNN 0.895 9 0.746 6 0.907 4 0.882 8 0.799 0 0.843 6 KNN 0.886 4 0.706 7 0.881 0 0.875 2 0.793 1 0.826 4 SVM 0.623 6 0.377 8 0.545 5 0.677 4 0.526 8 0.592 6 Tic-Tac-Toe HDVM_KNN 0.955 3 0.905 4 0.904 0 0.905 9 0.853 5 0.904 4 KNN 0.932 9 0.787 9 0.772 4 0.781 2 0.588 7 0.778 1 SVM 0.597 2 0.429 5 0.587 7 0.597 1 0.492 9 0.558 4 Liver HDVM_KNN 0.918 8 0.903 4 0.930 0 0.931 1 0.903 4 0.916 6 KNN 0.785 5 0.803 4 0.885 0 0.789 8 0.717 6 0.789 8 SVM 0.684 1 0.609 8 0.680 0 0.675 1 0.647 2 0.676 9 Breast HDVM_KNN 0.779 7 0.727 3 0.930 3 0.699 0 0.571 4 0.765 2 KNN 0.790 2 0.720 0 0.925 4 0.655 3 0.533 3 0.755 3 SVM 0.716 8 0.520 8 0.771 1 0.500 9 0.552 5 0.651 8 Haberman HDVM_KNN 0.843 1 0.779 7 0.942 2 0.791 3 0.657 1 0.818 0 KNN 0.797 4 0.711 1 0.942 2 0.767 6 0.507 9 0.760 0 SVM 0.738 6 0.507 9 0.862 2 0.679 1 0.444 4 0.636 8 Blood HDVM_KNN 0.847 6 0.775 9 0.954 4 0.871 2 0.612 2 0.817 2 KNN 0.819 5 0.693 7 0.940 4 0.849 6 0.532 9 0.764 0 SVM 0.493 3 0.309 3 0.361 4 0.806 7 0.462 4 0.536 9 Contraceptive HDVM_KNN 0.863 7 0.779 7 0.771 2 0.661 0 0.707 2 0.773 1 KNN 0.753 6 0.698 6 0.759 0 0.756 3 0.730 9 0.753 3 SVM 0.758 3 0.631 1 0.671 4 0.774 3 0.590 5 0.662 6 Teaching HDVM_KNN 0.892 2 0.796 3 0.887 4 0.886 8 0.835 0 0.864 3 KNN 0.803 9 0.565 2 0.715 2 0.666 7 0.547 4 0.664 4 SVM 0.107 8 0.340 6 0.384 1 0.609 3 0.502 7 0.536 8 第 4 期 张燕，等：基于异构距离的集成分类算法研究 ·737·