代价敏感决策树讲解

2021‑01‑10计算机应用,Journal of Computer Applications 2021,41(1):48-52ISSN 1001‑9081CODEN JYIIDU http ：//基于欠采样和代价敏感的不平衡数据分类算法王俊红1，2*，闫家荣1，2（1.山西大学计算机与信息技术学院，太原030006；2.计算智能与中文信息处理教育部重点实验室（山西大学），太原030006）（∗通信作者电子邮箱wjhwjh@ ）摘要：针对不平衡数据集中的少数类在传统分类器上预测精度低的问题，提出了一种基于欠采样和代价敏感的不平衡数据分类算法——USCBoost 。

首先在AdaBoost 算法每次迭代训练基分类器之前对多数类样本按权重由大到小进行排序，根据样本权重选取与少数类样本数量相当的多数类样本；之后将采样后的多数类样本权重归一化并与少数类样本组成临时训练集训练基分类器；其次在权重更新阶段，赋予少数类更高的误分代价，使得少数类样本权重增加更快，并且多数类样本权重增加更慢。

在10组UCI 数据集上，将USCBoost 与AdaBoost 、AdaCost 、RUSBoost 进行对比实验。

实验结果表明USCBoost 在F1-measure 和G -mean 准则下分别在6组和9组数据集获得了最高的评价指标。

可见所提算法在不平衡数据上具有更好的分类性能。

关键词：不平衡数据；分类；代价敏感；AdaBoost 算法；欠采样中图分类号：TP18文献标志码：AClassification algorithm based on undersampling andcost -sensitiveness for unbalanced dataWANG Junhong 1，2*，YAN Jiarong 1，2（1.School of Computer and Information Technology ，Shanxi University ，Taiyuan Shanxi 030006，China ；2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education （Shanxi University ），Taiyuan Shanxi 030006，China ）Abstract:Focusing on the problem that the minority class in the unbalanced dataset has low prediction accuracy bytraditional classifiers ，an unbalanced data classification algorithm based on undersampling and cost -sensitiveness ，called USCBoost （UnderSamples and Cost -sensitive Boosting ），was proposed.Firstly ，the majority class samples were sorted from large weight sample to small weight sample before base classifiers being trained by the AdaBoost （Adaptive Boosting ）algorithm in each iteration ，the majority class samples with the number equal to the number of minority class samples were selected according to sample weights ，and the weights of majority class samples after sampling were normalized and a temporary training set was formed by these majority class samples and the minority class samples to train base classifiers.Secondly ，in the weight update stage ，higher misclassification cost was given to the minority class ，which made the weights of minority class samples increase faster and the weights of majority class samples increase more slowly.On ten sets of UCI datasets ，USCBoost was compared with AdaBoost ，AdaCost （Cost -sensitive AdaBoosting ），and RUSBoost （Random Under -Sampling Boosting ）.Experimental results show that USCBoost has the highest evaluation indexes on six sets and nine sets of datasets under the F1-measure and G -mean criteria respectively.The proposed algorithm has better classification performance on unbalanced data.Key words:unbalanced data;classification;cost -sensitiveness;AdaBoost algorithm;undersampling引言分类是数据挖掘领域中一个重要的分支，普通的分类模型通常假设数据集中各类别的样本数量差距很小且对于每个类别的误分代价相等，而使用不平衡数据集训练传统的分类器会导致模型对于少数类的预测精度很低，因此不平衡数据学习一直是机器学习领域的研究热点［1］。

I SSN1673—9418C O D E N JK Y T A8Jour nal of C o m p ut er S c i e nce a nd Fr ont i er s1673—941812007／01(03)-0314-11基于相对等待时间的代价敏感决策树水袁鼎荣，张师超+，朱晓峰，张晨Y U A N D i ngr ong，Z H A N G Shi chao+，Z H U X i aof eng，Z H A N G C hen E-m ai l：fcs t@pu bl i c2．bt a．net．cn —ht t p：／／w w w．ce aj．or gT e l：+86一l o-51616056广西师范大学计算机科学与信息工程学院。

广西桂林541004C o U e g e of C o m pu t er S c i e nceand Tec hnol ogy。

G uangxi N o r m al U n i ve r s i t y，G ui l i n，G uan gxi541004，C h i na+Cor r esp on di n g aut hor：E-m ai l：zha ngsc@m ai l box．gxn u．e du．caY U A N D i ngr ong，Z H A N G Shi chao，Z H U X i ao f eng，et a1．C ost-s en s i t i ve deci s i o n t re es bas ed on r e l a-t i ve w ai t i ng t i m e．Jour nal of C om p ut er Sci ence a nd Fr ont i er s，2007，1(3)：314-324．A bs t r ac t：The pape r def i nes a‘r el at i ve w ai t i ng t i m e co s t’，an d com bi nes i t w i t h‘t est cost’as‘t angi b l e c os t’．T hen a pr i nci pl e i s pr es ent ed f or se l e ct i ng spl i t t i ng a t t r i but e s，i n w hi ch t hose at t ri but e s t ha t m axi m al l y decr ease i nt angi bl e cos t(i．e．，‘m i scl a ssi fi cat i on cos t’)i n an uni t of t a ngi bl e c os t，w i l l be f i r st l y s el ect ed a sspl i t t i ng at t r i but es．Furt herm or e，cos t-sens i t i ve deci si on t r ees w i t h r el at i vew ai t i ng t i m e cos t i s pr opos ed bycom bi ni ng t he s eque nt i al t es t st r a t eg y w i t h bat ch t es t s t rat eg y．Ex per i m ent al r e sul t s dem ons t r at e t ha t t he m et hod outper for m s t he exi s t i ng m et h ods not on l y at t he decr eas e of i nt a ngi bl e cost，b ut al s o at t he quant i t y of t he t angi bl e cos t．O n t he ot her hand，t he r e sul t s sho w t h at it is nec e ss a ry t o co ns i der t he r el at i ve w ai t i ng t i m e cos t w hen bui l di ng c ost-se ns i t i ve deci si on t r ees．K ey w or d s：cos t-s ens i t i v e；deci si on bee s；s pl i t t i ng a t t ri but es；w ai t i ng t i m e；t i m e-s en s i t i v e摘要：首先引入相对等待时间代价，将它与测试代价一起称为有形代价，利用单位有形代价中无形代价(即误分类代价)降低最多的原则选择分裂属性；然后结合序列测试策略和批量测试策略建立相对等待时间代价敏感决策树。

决策树名词解释决策树（DecisionTree）是一种常见的数据挖掘技术，也称为决策树分类（Decision Tree Classification）。

决策树是一种以树状结构表示数据的模型，它可以用来描述一组数据集的概念，它可以用来作出决策。

策树是一种数据挖掘的常用算法，它可以用于分类、回归任务，以及关联规则建模，它可以帮助智能系统理解数据，从而实现更好的决策。

决策树的基本原理很简单，它是一种将每个属性值与实例的关联转换成树形结构的方法。

在这种树形结构中，每个节点存储关联属性的值，从而决定一个决策。

策树通常用于研究一组已知数据，它可以用来预测未知数据的结果，也可以用来归类数据，从而发现数据的规律性。

决策树的建立有很多步骤，但是大致可以分为以下几个步骤：（1）数据集准备：首先，需要对数据集进行预处理，将数据分成训练集和测试集。

（2）决策树划分：根据训练集中的特征属性，将数据集划分为不同的分支，并且不断划分，直到达到决策树模型所需要的精度或停止条件为止。

（3）估属性：根据训练集中的数据，选择最优的划分属性，用于对训练集进行划分。

（4）决策树剪枝：新建的决策树可能过度拟合训练数据，这会使训练出来的决策树在测试数据上的表现变差，因此，需要使用剪枝算法，来减少决策树的过拟合现象。

（5）测试：根据训练好的决策树，对测试集数据进行分类，统计测试集分类正确率，从而对决策树进行评估。

决策树在实际应用中可以用于社会决策分析、企业决策分析、关联规则挖掘等应用场景，但是决策树也有若干缺点。

其一，决策树生成过程中属性之间的关系可能非线性，而决策树假设属性之间的关系是线性的，因此可能导致决策树模型的准确性不足。

其二，决策树的剪枝操作可能会过度剪枝，也影响模型的准确性。

总之，决策树是一种常用的数据挖掘技术，它可以用于推理和预测数据，它可以用来帮助智能系统理解数据，从而改善决策效率。

但是，因为决策树的局限性，仍然需要其他的数据挖掘技术来提高决策的准确性。

代价敏感学习方法综述代价敏感学习方法是一种机器学习方法，它可以根据错误分类的代价来调整模型的权重。

通过将不同类别的错误分类赋予不同的代价值，代价敏感学习方法可以使得模型更加关注于重要的错误分类。

本文将综述代价敏感学习方法的原理、应用领域和研究进展。

代价敏感学习方法的原理是基于一个假设：不同类别的错误分类对应的代价是不同的。

例如，在医学诊断中，将正常病人错误分类为患有重大疾病的错误可能会造成严重的后果，而将患有重大疾病的病人错误分类为正常病人的错误可能相对较轻微。

因此，我们希望模型能更加关注于将患有重大疾病的病人正确分类，并降低将正常病人错误分类的概率。

代价敏感学习方法可以用于多种机器学习算法，包括决策树、支持向量机、神经网络等。

其中，决策树是最常用的方法之一、在决策树中，代价敏感学习方法可以通过调整树的划分过程来使得不同类别的错误分类具有不同的代价。

具体而言，代价敏感学习方法可以通过调整划分准则来使得错误分类代价较高的类别更容易被划分到更高层的节点，从而减少错误分类的概率。

除了决策树，代价敏感学习方法还可以与其他机器学习方法相结合。

例如，在支持向量机中，代价敏感学习方法可以通过调整不同类别样本的权重来改变模型的决策边界，从而降低错误分类的概率。

在神经网络中，代价敏感学习方法可以通过调整不同类别样本的损失函数权重来改变模型的学习规则，从而使得模型更加关注于重要的错误分类。

目前，代价敏感学习方法在研究领域有许多进展。

一方面，研究人员正在开发新的代价敏感学习算法，以提高模型的性能和效率。

例如，一些研究人员正在研究如何自动选择不同类别的错误分类代价，而不是人工设定代价值。

另一方面，研究人员还在研究如何应用代价敏感学习方法于更复杂的场景，如多类别分类和迁移学习。

此外，一些研究人员还在探索如何结合代价敏感学习方法和其他机器学习方法，以进一步提高模型的性能。

综上所述，代价敏感学习方法是一种可以根据错误分类的代价来调整模型权重的机器学习方法。

决策树算法原理（三种最优属性划分方法）决策树是一种用于分类和回归的机器学习算法，其原理是基于历史数据进行学习，并通过一系列判断条件将数据集划分为不同的类别或者预测目标值。

决策树的主要思想是通过一系列属性值来对数据进行逐层划分，直到达到终止条件为止。

在每一次划分时，决策树需要选择最优的属性来进行划分，以使得划分后的数据纯度最高或者信息增益最大。

三种最优属性划分方法包括信息增益、增益率和基尼指数。

1.信息增益：信息增益是用来衡量划分后数据集纯度提高的程度。

它基于信息论中的熵的概念，计算的是划分前后数据集的信息熵之差。

信息熵可以衡量数据集的不确定性，即数据集中的混乱程度。

在选择划分属性时，我们希望划分后的数据集的不确定性最小，即使得信息增益最大。

2.增益率：增益率是信息增益的一种改进，用于解决信息增益在选择具有较多取值的属性上的偏好问题。

增益率通过考虑属性的分裂信息来衡量属性的纯度提升程度。

分裂信息反映了数据集分裂后的数据集的不确定性。

3.基尼指数：基尼指数是通过测量在给定数据集中随机选择一些样本后，错误分类该样本的概率。

基尼指数可以用于二分类或多分类问题。

在选择划分属性时，我们希望划分后的数据集的基尼指数最小，即使得纯度提高的程度最大。

以上三种最优属性划分方法在决策树学习的过程中都有着重要的应用。

在实际应用中，决策树算法可以通过先验知识或者经验来选择最优属性划分方法。

此外，由于决策树算法在高维数据上容易过拟合的问题，可以通过剪枝等技术来避免过拟合。

决策树算法的优势在于易于理解和解释，但也存在局限性，比如对于处理缺失数据、处理连续数据和处理类别不平衡等问题仍然存在挑战。

处理类别不平衡数据的机器学习方法在机器学习中，类别不平衡数据是指训练集中各个类别的样本数量存在较大的不平衡性。

这种情况在许多现实世界的问题中都很常见，例如罕见疾病的诊断、网络异常行为检测等。

由于数据不平衡可能导致模型的预测结果存在偏见，因此需要采用一些机器学习方法来处理这类问题。

本文将介绍一些常用的处理类别不平衡数据的机器学习方法。

一、采样方法采样方法是一种常见的处理类别不平衡数据的方法，它通过增加少数类样本或减少多数类样本的方式来平衡数据集。

常见的采样方法有过采样和欠采样。

1. 过采样过采样通过增加少数类样本的数量来平衡数据集。

其中一种常见的过采样方法是SMOTE（Synthetic Minority Over-sampling Technique），它通过在少数类样本之间进行插值来产生新的合成样本。

通过SMOTE生成的合成样本可以增加训练集的多样性，使得模型更好地识别出少数类样本。

此外，还有一些改进的SMOTE算法，如Borderline-SMOTE和ADASYN，它们都是在原始SMOTE算法的基础上做了改进，进一步提高了生成合成样本的质量。

2. 欠采样欠采样通过减少多数类样本的数量来平衡数据集。

一种常见的欠采样方法是随机欠采样，它从多数类样本中随机地删除一些样本使得多数类样本和少数类样本的数量接近。

然而，随机欠采样可能会导致丢失一些重要的多数类样本信息。

为了解决这个问题，我们可以使用一些基于聚类或决策边界的欠采样方法，例如NearMiss和ENN（Edited Nearest Neighbor）。

这些方法通过选择具有代表性的多数类样本来减少多数类样本的数量，从而保留了重要的多数类样本信息。

二、集成方法集成方法是将多个学习器进行组合以提高预测性能的方法。

在处理类别不平衡数据时，集成方法可以通过将少数类样本的重要性增加来提高预测模型对少数类样本的识别能力。

常见的集成方法有Bagging、Boosting和Stacking等。

简单说明决策树原理决策树是一种基于树形结构的分类和回归模型，它通过对训练数据进行学习来建立一个树形模型，用于预测新的数据。

决策树模型具有易于理解、易于实现、可处理离散和连续数据等优点，因此在机器学习领域得到了广泛应用。

一、决策树的基本概念1. 节点：决策树中的每个圆圈都称为一个节点，分为两种类型：内部节点和叶节点。

2. 内部节点：表示对特征进行测试的节点。

每个内部节点包含一个属性测试，将输入实例分配到其子节点中。

3. 叶节点：表示分类结果或输出结果。

在叶子结点处不再进行属性测试，每个叶子结点对应着一种类别或值。

4. 分支：表示从一个内部节点指向其子节点的箭头，代表了样本在该特征上取某个值时所走的路径。

5. 根节点：表示整棵决策树的起始点，在分类问题中代表所有样本都未被分类时所走的路径。

6. 深度：从根结点到当前结点所经过分支数目。

叶子结点深度为0。

7. 路径：从根结点到叶子结点所经过的所有分支构成的序列。

8. 剪枝：对决策树进行简化的过程，目的是减少模型复杂度，提高泛化能力。

二、决策树的生成1. ID3算法ID3算法是一种基于信息熵来进行特征选择的决策树生成算法。

它通过计算每个特征对训练数据集的信息增益来选择最优特征作为当前节点的属性测试。

具体步骤如下：（1）计算数据集D的信息熵H(D)。

（2）对于每个特征A，计算其对数据集D的信息增益Gain(A)，并选择信息增益最大的特征作为当前节点的属性测试。

其中，信息增益定义为：Gain(A)=H(D)-H(D|A)，其中H(D|A)表示在已知特征A时，数据集D中所包含的各个类别所占比例对应的熵值。

（3）将数据集按照选定属性划分为多个子集，并递归地生成子树。

（4）直到所有样本都属于同一类别或者没有更多可用特征时停止递归。

2. C4.5算法C4.5算法是ID3算法的改进版，它在选择最优特征时使用了信息增益比来解决ID3算法中存在的偏向于选择取值较多的特征的问题。

决策树模型参数及其解释决策树模型是一种常用的机器学习算法，它通过构建一棵树状的决策流程来进行分类或回归任务。

决策树模型有一些重要的参数，下面我将逐个解释它们。

1. criterion（划分标准），决策树在每个节点上选择最佳划分的标准。

常见的划分标准有基尼系数（gini）和信息增益（entropy）。

基尼系数衡量了节点的不纯度，信息增益则衡量了节点的信息不确定性。

2. max_depth（最大深度），决策树的最大深度限制。

深度是指从根节点到叶节点的最长路径长度。

设置最大深度可以避免过拟合，但也可能导致欠拟合。

通常需要通过交叉验证来选择最优的最大深度。

3. min_samples_split（节点划分的最小样本数），决策树在进行节点划分时所需的最小样本数。

如果某个节点的样本数小于该值，则不再进行划分。

这个参数可以控制决策树的复杂度，避免过拟合。

4. min_samples_leaf（叶节点的最小样本数），决策树的叶节点上所需的最小样本数。

如果某个叶节点的样本数小于该值，则该节点会被剪枝。

这个参数可以控制决策树的复杂度，避免过拟合。

5. max_features（最大特征数），在进行节点划分时考虑的最大特征数。

可以是一个固定的整数值，也可以是一个比例。

这个参数可以控制决策树的复杂度，避免过拟合。

6. splitter（节点划分策略），决策树节点划分的策略，可以是"best"或"random"。

"best"表示选择最佳划分，"random"表示随机选择划分。

默认为"best"，一般情况下不需要修改。

这些参数可以根据具体问题和数据集的特点进行调整，以获得更好的模型性能。

需要注意的是，参数的选择需要综合考虑模型的准确性和复杂度，避免过拟合或欠拟合的问题。

可以使用交叉验证等技术来选择最优的参数组合。

不平衡数据分类方法综述随着大数据时代的到来，越来越多的数据被收集和存储，其中不平衡数据成为了一个普遍存在的问题。

不平衡数据指的是在分类问题中，不同类别的样本数量差别很大，例如欺诈检测、疾病诊断、文本分类等领域。

不平衡数据分类问题的存在会导致分类器的性能下降，因此如何有效地处理不平衡数据分类问题成为了研究的热点之一。

本文将综述当前常用的不平衡数据分类方法，包括基于采样的方法、基于代价敏感的方法、基于集成的方法、基于生成模型的方法和基于深度学习的方法。

一、基于采样的方法基于采样的方法是指通过对训练集进行采样来平衡不同类别的样本数量。

其中包括欠采样和过采样两种方法。

1. 欠采样欠采样是指随机删除多数类的样本，使得多数类和少数类样本数量接近。

常用的欠采样方法包括随机欠采样、聚类欠采样和Tomek链接欠采样。

随机欠采样是指从多数类中随机删除一些样本，使得多数类和少数类样本数量相等。

聚类欠采样是指将多数类样本聚类成若干个簇，然后从每个簇中随机删除一些样本。

Tomek链接欠采样是指删除多数类和少数类之间的Tomek链接样本，Tomek链接样本是指在样本空间中距离最近的一个多数类样本和一个少数类样本。

欠采样方法的优点是可以减少训练时间和存储空间，但是也有一些缺点。

首先，欠采样会导致信息丢失，可能会削弱多数类样本的代表性。

其次，欠采样可能会引入噪声，因为删除样本是随机的。

2. 过采样过采样是指对少数类样本进行复制或合成，使得多数类和少数类样本数量接近。

常用的过采样方法包括随机过采样、SMOTE和ADASYN。

随机过采样是指随机复制少数类样本，使得多数类和少数类样本数量相等。

SMOTE是指对每个少数类样本找到若干个最近邻样本，然后随机合成新的少数类样本。

ADASYN是指对每个少数类样本计算其与多数类样本的密度比，然后根据密度比生成新的少数类样本。

过采样方法的优点是可以保留所有的少数类样本和信息，但是也有一些缺点。

首先，过采样可能会引入冗余样本，因为合成样本是基于原始样本的。