离散化技术：近期的一项调查外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

离散化技术：近期的一项调查

Sotiris Kotsiantis, Dimitris Kanellopoulos

Educational Software Development Laboratory

Department of Mathematics, University of Patras, Greece

sotos@math.upatras.gr, dkanellop@teipat.gr

摘要：为了使用决策树（DT），贝叶斯网络（BN）和规则学习者（RL）处理实值属性的问题，需要离散化算法，将得到的区间视为名义值。 这些系统的性能与这些间隔的正确选择有关。 良好的离散化算法必须平衡这种过程固有的信息损失并产生合理数量的切割点，即合理的搜索空间。 本文介绍了众所周知的离散化技术。 当然，单篇文章不能完全回顾所有离散化算法。 尽管如此，我们希望引用的参考文献涵盖主要的理论问题，并指导研究人员研究有趣的研究方向，并提出可能需要探索的组合。

1简介

众所周知，许多机器学习（ML）算法通过离散连续属性来产生更好的模型[14]。朴素贝叶斯（NB）分类器需要估计概率，并且连续的解释性属性不容易处理，因为它们通常采用太多不同的值来直接估计频率。为了避免这种情况，可以是连续值的正态分布假设，但这个假设并不总是现实的。同样的现象导致规则提取技术构建较差的规则集。 DT算法执行标称属性的选择过程，不能直接处理连续的属性。

因此，大量的ML和统计技术只能应用于完全由名义变量组成的数据集。然而，很大比例的实际数据集包括连续变量：即以间隔或比率水平测量的变量。该问题的一个解决方案是将数值变量划分为多个子范围，并将每个这样的子范围视为一个类别。将连续变量划分为类别的过程通常称为离散化。不幸的是，离散连续属性的方法的数量是无限的。离散化是一个潜在的耗时瓶颈，因为可能的离散化数量是域内区间阈值候选者数量的指数[14]。

离散化的目标是找到一组切割点以将范围划分为具有良好类相干性的少量间隔，其通常通过评估函数来测量。除了相互依存最大化beGEST国际计算机科学与工程交易，Vol.32（1），2006，pp.47-58类标签和属性值之外，理想的离散化方法应该有一个次要目标，以尽量减少数量间隔没有明显损失的类别相互依赖。离散化通常在学习过程之前执行，并且可以分为两个任务。第一项任务是找到离散间隔的数量。只有少数离散化算法执行此操作;通常，用户必须指定间隔数或提供启发式规则。第二个任务是在给定连续属性的值范围的情况下找到间隔的宽度或边界。

通常，在离散化过程中，在相对于要离散化的变量按升序或降序对数据进行排序之后，必须在整个数据集中选择标记。通常，用于选择地标的算法可以是自上而下，其以空标记列表和分割间隔开始，或自下而上，其以所有值的完整列表作为地标并且合并间隔开始。

在这两种情况下都有一个停止标准，它指定何时停止离散化过程。 ML社区的研究人员已经引入了许多离散化算法。这些算法中的大多数在候选离散化的空间中执行迭代贪婪启发式搜索，使用不同类型的评分函数来评估离散化。最近对各种类型的离散化算法的概述可以在[28]中找到。因此，除了对离散化过程的简要描述之外，在这项工作中，我们参考了一些刘的文章更新的作品以及一些没有被刘介绍的文章。

下一节将介绍离散化过程的广泛问题。离散化方法的类别在第3节中进行了分析，而离散化方法与DT，RL和BN的组合在第4节中给出。最后，最后一节总结了这项工作。

2离散化过程

术语“切点”是指在连续值范围内的实际值，其将范围分成两个间​​隔，一个间隔小于或等于切割点，另一个间隔大于切割点。例如，连续间隔[a，b]分为[a，c]和（c，b），其中值c是一个切点。切点也称为分裂点。离散化背景下的术语“arity”表示间隔或分区的数量。在连续特征的离散化之前，arity可以设置为k-连续特征中的分区数。切割点的数量是k-1。离散化过程减少了arity，但是arity之间存在相关性以及它对精度的影响。

典型的离散化过程大致包括四个步骤：（1）对要离散的特征的连续值进行排序，（2）评估合并的分割或相邻间隔的切割点，（3）根据某些标准，分割或合并连续值的间隔，以及（4）最终在某一点停止。

在排序之后，离散化过程的下一步是找到最佳的“切割点”以分割一系列连续值或最佳的一对相邻间隔以进行合并。一种典型的评估函数是确定分割或合并与类标签的相关性。在文献中发现了许多评估函数，例如熵测量和统计测量（更多细节在以下部分中）。停止标准指定何时停止离散化过程。它通常由较低的arity之间的权衡来理解，但是更好的理解但是更低的准确性和更高的理解，更差的理解但更高的准确性。由离散化引起的不一致的数量（后面定义的不一致性） - 它不应该远高于离散化之前原始数据的不一致性的数量。如果两个实例的属性值相同，则除了类标签外，它们被认为是不一致的。

通常，离散化方法可以分类为：（1）监督或无监督，（2）直接或增量，（3）全球或本地，（4）静态或动态，（5）自上而下或自下而上。我们在以下部分中区分这些类别。

3 离散化方法的种类

可以根据该方法是否考虑类信息以找到适当的间隔来进行区分。在离散化过程期间，诸如等宽间隔合并或相等频率合并的若干离散化方法不利用类成员资格信息。这些方法称为无监督方法。相反，使用类标签进行离散化的离散化方法被称为监督方法。先前的研究表明，监督比无监督方法更好[12]。

无监督（或类盲）算法的两种代表性算法是等宽和等频离散化。等宽离散化算法确定离散化属性的最小值和最大值，然后将范围划分为用户定义的等宽离散间隔数。

等频算法确定离散化属性的最小值和最大值，按升序对所有值进行排序，并将范围划分为用户定义的间隔数，以便每个间隔包含相同数量的排序值。这种等宽方法的明显弱点在于，在结果观察不均匀分布的情况下，在离散化过程之后可能丢失大量重要信息。对于等频，连续值的多次出现可能导致将出现分配到不同的区间。一个改进可以是在将连续值分配到箱中之后，调整每对相邻箱的边界，使得重复值仅应属于一个箱。

离散化方法的另一个方面是直接与增量过程[14]。直接方法同时划分k个间隔的范围（即，等宽度），需要来自用户的附加输入以确定间隔的数量。增量方法从简单的离散化开始，并通过改进过程，需要一个额外的标准来知道何时停止离散化[7]。

全局和局部离散化方法之间的区别取决于何时执行离散化[28]。全局离散化处理每个数字属性的离散化作为预处理步骤，即在引入分类器之前像C4.5这样的本地方法即时进行离散化（在感应期间）。实证结果表明，与局部方法相比，全局离散化方法通常产生超级结果，因为前者使用数值属性的整个值域进行离散化，而局部方法产生的间隔是应用于实例空间的子分区。

静态和动态方法之间的区别取决于该方法是否考虑了特征交互[32]。静态方法，例如分箱，基于熵的分区和1R算法[21]，确定每个属性的分区数量，与其他特征无关。相反，动态方法同时针对所有特征在可能的k个分区的空间中进行搜索，从而捕获特征离散化中的相互依赖性。

最后，可以区分自上而下和自下而上的离散化方法。自上而下的方法考虑一个包含所有已知特征值的大间隔，然后将此间隔划分为越来越小的子间隔，直到实现某些停止标准，例如最小描述长度（MDL）或最佳间隔数。相反，自下而上方法最初考虑由边界点集确定的多个间隔，以在执行期间组合这些间隔，直到达到某个停止标准，例如x2阈值或最佳间隔数[24]。

在离散化问题中，必须在信息质量（关于预测属性的均匀间隔）和统计质量（每个间隔中足够的样本大小以确保概括）之间找到折衷方案。基于chisquare的标准侧重于统计观点，而基于熵的标准侧重于信息观点。其他标准（如基尼或Fusinter标准）试图在信息和统计属性之间找到折衷方案。还有其他方法，类似于特征选择领域中涉及的包装方法以及基于进化的方法。我们分析所有这些接下来的小节。

3.1基于卡方的方法

卡方（x2）是一种统计测量，对特征值和类之间的关系进行显着性检验。 Kerber [24]认为，在准确的离散化中，相对类频率应该在一个区间内相当一致（否则区间应该被分割以表示这种差异），但是两个相邻区间不应该具有相似的相对类频率（在这种情况下，相邻的区间应合并为一个）。 x2统计量基于某个显着性水平确定相邻区间的相似性。它测试了一个假设，即一个特征的两个相邻区间独立于该类。如果他们是独立的，他们应该合并;否则他们应该保持分开。

基于卡方的自上而下方法是ChiSplit。它通过最大化应用于与分裂点相邻的两个子区间的卡方标准来搜索区间的最佳分割：如果两个子区间在统计上基本上不同，则分割间隔。 ChiSplit停止规则基于用户定义的卡方阈值，如果两个子区间太相似，则拒绝分割。

基于卡方的自下而上方法是ChiMerge [24]。它通过最小化局部应用于两个相邻区间的卡方准则来搜索相邻区间的最佳合并：如果它们在统计上相似，则它们被合并。如果两个相邻的间隔不够相似，则停止规则基于用户定义的卡方阈值以拒绝合并。没有明确的规则来选择这个门槛。 Chi2 [30]是ChiMerge的自动化版本。在Chi2中，只要满足不一致性标准[29]，统计显着性水平就会不断变化以合并越来越多的相邻区间。与Chi2非常相似的方法是ConMerge [33]，它也使用x2统计量和不一致性度量。 ConMerge不是一次考虑一个属性，而是在所有连续特征的区间中选择最低的x2值。

Boulle [5]基于卡方统计量提出了离散化方法Khiops。与相关方法ChiMerge和ChiSplit相比，该方法在整个离散化域上以全局方式优化卡方准则，并且不需要任何停止准则。 Khiops方法从基本单值间隔开始离散化。它评估相邻区间之间的所有合并，并根据应用于整个区间集的卡方准则选择最佳合并。停止规则基于使用卡方统计量计算的置信水平。该方法自动停止合并间隔为很快，与离散属性和类属性之间的独立性卡方检验相关的置信水平不再降低。

3.2基于熵的方法

其他离散化方法使用熵测量来评估候选切割点。这意味着基于熵的方法将使用候选分区的类信息熵来选择用于离散化的边界。类信息熵是纯度的度量，它测量信息量需要指定实例所属的类。它考虑包含特征的所有已知值的一个大间隔，然后递归地将该间隔划分为较小的子间隔，直到一些停止标准，例如最小描述长度（MDL）原则或最佳间隔数量。其他评估措施包括基尼，不相似和海林格的衡量标准。

MDL原则指出最佳假设是具有最小描述长度的假设。由于分区总是减小熵函数的值，考虑到假设的描述长度允许平衡熵增益并最终接受零假设。使用该标准执行递归二分区导致手头的连续解释属性的离散化。

FID [15]评估每个连续的排序值对之间的中点作为候选切割点。对于候选切割点的每个评估，将数据离散化为两个间隔，并计算得到的类信息熵。通过在所有候选切割点中选择熵最小的切割点来确定二元离散化。这种二进制离散化是递归应用的，总是选择最佳切割点。应用最小描述长度标准（MDL）来决定何时停止离散化。

目前已经表明熵最小化的最佳切割点必须位于不同类别的例子之间[15]。Zeta最大化可以证明类似的结果：当独立变量的每个值必须预测因变量的不同值时，基于误差率最小化的度量[20]。

试图通过离散间隔和类标签之间的相互依赖性冗余来测量最大化相互依赖性[9]的方法，并且可以自动确定归纳学习应用的最优选间隔数。由于其能够自动选择最小间隔数而不会显着减少有用的互信息，因此该方法可以加快大多数归纳学习者的学习时间，而分类准确度损失很小。

USD [19]将连续属性划分为有限数量的区间，具有最大优度，因此最终区间集的平均优度将是最高的。主要过程分为两个不同的部分：首先，它通过投影计算初始间隔，具体取决于之后获得的好处执行两个可能的动作：加入或不加入相邻的间隔。该算法的主要特点是：它是确定性的，不需要任何用户参数，其复杂性是次二次的。

CAIM算法[26]的目标是最大化类属性相互依赖性并生成（可能）最小数量的离散区间。 CAIM算法最大化了相互类属性的相互依赖性，并且可能为给定的连续属性生成最小数量的间隔。它经过测试几个众所周知的数据集，并与其他六个最先进的离散化算法进行比较。这组作者说，比较表明，CAIM算法产生的离散化方案平均来说，最小的区间数和类标签与离散区间之间的依赖性最高，因此优于其他离散化算法。

3.3基于包装器的方法

虽然大多数离散化方法被用作归纳算法的预处理步骤，但是仍然存在其他方法，类似于特征选择字段中涉及的包装方法。例如，[4]和[6]的作者提出了允许通过从归纳算法获取反馈来改进连续解释属性的离散化的方法。基于错误的方法，如[31]，针对误差函数评估候选切割点并探索边界点的搜索空间，以最小化训练集上的假阳性（FP）和假阴性（FN）误差的总和。换句话说，给定固定数量的间隔，基于错误的离散化旨在找到最佳离散化，其最小化通过将特定连续值分组到一个区间中而产生的错误总数（FP和FN）。

另一个使用精度进行离散化的例子是Adaptive Quantizer [8]。它考虑了一个属性一次预测该类的程度。对于每个属性，其连续范围通过等频或等宽分成两个分区。通过运行分类器来检查拆分，以查看拆分是否有助于提高准确性。它继续二值化子范围和切割点，给出了选择最低费率。因为它涉及训练分类器，所以通常比不使用分类器的人更耗时。

Elomaa和Rousu [13]表明，为了找到训练集误差（区间标记与数据点的差异最小的最佳离散化），只需要检查少数所有切割点，称为交替点。另一方面，作者证明未能检查交替点可能导致次优离散化。一旦订购了数据，就可以有效地识别交替点。

Elomaa和Rousu [14]提出了加速发现最优的技

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19993]，资料为PDF文档或Word文档，PDF文档可免费转换为Word