不平衡分类问题的一阶逻辑决策树集合

M.Manjula¹, T.Seeniselvi²

印度哥印拜陀艺术与科学学院计算机科学系PG&Research研究学者
PG&Research助理教授。印度哥印拜陀艺术与科学学院计算机科学系

摘要

不平衡类分布是现实分类问题中经常遇到的问题。基于决策树分类学习的集合分类在商业和医疗领域得到了广泛的应用。基于一阶逻辑决策树的高维集成分类方法可以提高竞争性能，解决这一问题。提出的工作是用不同类别的KEEL数据集进行测试的。数据预处理方法(采样过程)的目的是通过随机消除大多数类的例子来平衡类的分布，然后分裂决策树算法生成树状的分类规则，这些规则以特征值的合取和离取的形式来编写。基于Bagging的集成方法通过少数类实例的复制来增加它们的数量，最终方法是一阶逻辑决策树(FOLD)方法，用于查找随着连接0到1的变化。本文提供了许多类别不平衡数据集的实验结果，包括来自医学界的BRFSS和MIMIC数据集，以及来自UCI和KEEL的几个数据集，以突出所提出的集成在广泛的数据分布和类别不平衡方面的有效性。

关键字

数据挖掘，逻辑决策树，不平衡数据集，集成分类

介绍

在现实世界的分类问题中经常遇到不平衡的类别分布，这些问题产生于欺诈检测、风险管理、文本分类、医疗诊断和许多其他领域。这种不平衡的阶级数据集与平衡的阶级数据集的区别不仅在于阶级分布的偏倚性，而且在于少数阶级的重要性的增加。尽管不平衡问题在日常应用中经常出现并产生巨大影响，但许多标准的机器学习算法并没有适当地解决不平衡问题，因为它们假设平衡的类分布或相等的错误分类成本为[1]。

为了解决这些问题，人们提出了各种方法来处理不平衡类，包括过采样/过采样[2]，[3]，合成少数过采样技术(SMOTE)，代价敏感[4]，基于改进内核的主动学习方法[5]，[6]。尽管这些方法确实在一定程度上缓解了问题，但它们通常是基于启发式的，而不是基于明确的指导。例如，在过采样技术中，最佳过采样比在数据集之间有很大差异，通常通过多次交叉验证或其他启发式来确定。

最近的研究结果表明，应该从多个角度来解决阶级失衡问题，并使用不同的评价指标[7]。这些发现表明，不平衡的程度并不是阻碍学习过程的唯一因素。相反，困难在于各种其他因素，如重叠的类、缺乏代表性数据和小的分离。更糟糕的是，当职业分布高度不平衡时，这些因素的影响会被放大。

决策树学习方法是用于分类或诊断的方法之一。与许多其他机器学习方法一样，决策树中的学习是通过使用已经分类的实例的数据集来构建决策树，该决策树稍后将用作分类器。用于“训练”决策树的实例集称为训练集。

相关工作

在[1]作者中，在许多大规模、复杂和网络化系统(如监视、安全、互联网和金融)中数据可用性的不断扩展，从原始数据中推进对知识发现和分析的基本理解以支持决策过程变得至关重要。尽管现有的知识发现和数据工程技术已经在许多实际应用中取得了巨大成功，但从不平衡数据中学习的问题(不平衡学习问题)是一个相对较新的挑战，已经引起了学术界和工业界越来越多的关注。在[2]中，作者使用了所有的约简方法提高了小类的识别(20-30%)，但差异不显著。然而，用3-最近邻法和减少后数据的C4.5得到的正确率、真阳性率和真阴性率有显著差异，更倾向于邻域清洁规则(NCL)。结果表明，NCL是一种有效的方法，可以改进困难小类的建模，并从实际数据中构建分类器来识别这些类。在[3]中讨论了该研究比较了从不平衡数据集生成的分类器的性能与从相同数据集的平衡版本生成的分类器的性能。这种比较使我们能够分离和量化训练集的类分布对学习的影响，并对比分类器在少数类和多数类上的表现。第二项研究评估了哪种分布对训练来说是“最佳”的，这涉及到两个性能指标:分类精度和ROC曲线下面积(AUC)。在[4]中，作者讨论了支持向量机(SVM)已经得到了广泛的研究，并在许多应用中取得了显著的成功。然而，支持向量机的成功是非常有限的，当它应用于从不平衡的数据集中学习的问题，其中消极实例远远超过积极实例(例如在基因分析和检测信用卡欺诈)。 This paper discusses the factors behind this failure and explains why the common strategy of under-sampling the training data may not be the best choice for SVM. In [5] authors discussed the problem occurs when there are significantly less number of observations of the target concept. Various real-world classification tasks, such as medical diagnosis, text categorization and fraud detection suffer from this phenomenon. The standard machine learning algorithms yield better prediction performance with balanced datasets. In this paper, we demonstrate that active learning is capable of solving the class imbalance problem by providing the learner more balanced classes. In [6] authors considered the large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data.

算法

A.拆分决策树

决策树学习是数据挖掘中常用的方法。大多数商业软件包都提供复杂的Tree分类算法，但是它们非常昂贵。决策树算法生成树结构的分类规则，这些规则以特征值(或属性值)的连接和分离形式编写。这些分类规则是通过

？根据一定的准则选择最佳的分裂特征，

？根据最佳分割特征值对输入数据进行分区，

？递归地重复此过程，直到满足某些停止条件。

所选的最佳分割特征不仅会影响输入数据的当前分区，还会影响后续的最佳分割特征，因为它会改变结果分区的样本分布。因此，最佳的分裂特征选择可以说是决策树构建中最重要的一步，使用不同分裂标准的决策树有不同的名称，例如，C4.5和ID3用于基于Shannon熵的分裂标准，而信息增益比和CART用于基尼杂质度量。

B.基于装袋的套装

装袋包括用原始训练数据集的引导副本训练不同的分类器。也就是说，形成一个新的数据集，通过从原始数据集中随机抽取(替换)实例(通常保持原始数据集的大小)来训练每个分类器。

袋装算法不需要重新计算任何类型的权重;因此，既不需要调整权重更新公式，也不需要改变算法中的计算。在这些方法中，关键因素是如何收集每个bootstrap副本(算法1)，即如何处理类不平衡问题，在不忘记多样性重要性的情况下，在每次迭代中获得一个有用的分类器。

C.一阶逻辑决策树

一阶逻辑决策树l是龙骨数据库;一个节点中的测试对应于检查一个查询←C在l ^ LEAT(以Lift-Boosting Ensemble of α-Trees (LEAT)为背景知识)中是否成功。注意，对于C，仅在节点本身中使用连接符conj是不够的。由于conj可能与树中更高位置的节点共享变量，因此C由几个出现在从根到当前节点的路径上的连接符组成。因此，当一个例子向左排序时，C将通过添加conj来更新。当一个例子向右排序时，C不需要更新:失败的测试永远不会引入新的变量。

一阶逻辑决策树(FOLDT)是一种二叉决策树，其中树的节点包含一个字面量的连接，不同的节点可以共享变量，但有以下限制:在节点中引入的变量(这意味着它不会出现在更高的节点中)必须不能出现在该节点的右分支中。逻辑决策树的一个例子如图1所示。它对例1的目标假设进行编码。

伪代码

逻辑分类(s: sample)返回类:

步骤1:C:= true

步骤2:N:= root。

第三步:当N≠叶(c)时

步骤4:let N = inode(conj, left, right)

步骤5:如果C ^ conj在Tree ^ s中成功，那么

C:= C ^ conj

N:=左

N:= right

步骤8:返回c

仿真结果

本文所使用的20个数据集均来自1)KEEL非平衡数据集。许多KEEL数据集都是从UCI机器学习库中派生出来的，它们要么选择不平衡的数据集，要么折叠/删除一些类，使它们成为不平衡的二进制数据集。paw02a、03subcl5和04clover是人工数据集，它们不是来自UCI存储库。它们被设计用来模拟[43]中的噪声、边缘和不平衡示例。除了上述修改外，KEEL存储库中的每个数据集都是“按原样”使用的。

表1显示了逻辑决策树分类，α-多样化分类器使用EAT框架:EAT (α -多样化单树)，BEAT (α -多样化袋装树)，UBEAT (α -多样化袋装下树)当K = 3时。请注意，EAT框架可以插入到任何基于装袋的集成算法中，例如过度装袋。将这六种算法与两种基线算法和一个C4.5算法一起应用于数据集，并记录了5 × 2交叉验证的auroc。

结果表明，α -多元集成比相应的基线方法具有更好的AUROC性能

结论及未来工作

仿真结果表明，该算法比现有的半监督聚类算法性能更好。一阶逻辑关系的新集成框架(称为FOLR)的建议工作，始终导致比类不平衡数据集更高的AUROC值。所提出的工作修改了决策树算法中的传统修剪规则，以直接反映基于条件的评估指标。对于未观察到的实例，一阶逻辑关系树是一个很好的泛化方法，前提是实例是用与目标概念相关的特征来描述的。该决定提供了一个明确的指示，哪些领域是最重要的预测或分类。

作为未来的工作，该系统需要大量的数据集进行测试，并需要进一步的训练和分类，以解决不同领域表达的比较句问题。