数值数据离散化

数据离散化方法综述摘要:数据离散化是一个训练集预处理的方法，用于将连续的数值属性转化为离散的数值属性。离散数值属性在数据挖掘的过程中具有重要的作用。本文首先介绍了离散化方法的分类，同时还按照分类介绍几种具有代表性的离散化方法。然后比较各种离散化方法在特定应用环境下的优势和不足，提出需根据具体应用特征选取离散化方法。关键字：连续属性；离散属性；数据离散化1.概述数据的特征按照其取值可以分为连续型和离散型。连续型数据也叫定量特征，通常用间隔的尺度和比例尺度来衡量，其值取自于某个连续的区间，通常具有较多或者无穷多个可能的取值，例如气温、身高、价格等等。离散型数据也叫定性特征，一般以名义尺度或者有序尺度定义，其值取自于某个有限的集合当中，如人的性别只能在{男、女}中取值。此类特征的值域只限定于较少的取值。数据离散化作为训练集的预处理过程，其输出直接被用作随后进行的数据挖掘算法，如分类和预测算法的输入。这些算法大多数是针对离散型数据的，对于连续型数据不适用；有些算法即使能够处理连续型数据，效果也不如处理离散型数据好。在数据库系统中连续型受占多数，要更好地分析处理这些数据就有必要对这些数据进行离散化。离散化的方法有很多，本文第2节介绍离散化方法的分类以及离散化的一般过程第3节按类别具体介绍几种代表性的离散化方法。第4节提出要根据具体应用环境选择合适的离散化方法。2.离散化过程及分类2.1数值离散化的一般过程对连续特征进行离散化处理，一般经过以下步骤：（1）对此特征进行排序。特别是对于大数据集，排序算法的选择要有助于节省时间，提高效率，减少离散化的整个过程的时间开支及复杂度。（2）选择某个点作为候选点，用所选取的具体的离散化方法的尺度来衡量候选选点是否满足要求。（3）若候选点满足离散化的衡量尺度，则对数据集进行分裂或合并，再选择下一个候选点，重复步骤（2）（3）。（4）当离散算法存在停止准则时，如果满足停止准则，则不再进行离散化过程，从而得到最终的离散结果。其中“候选点”指的是一个数值属性取值范围内的值，这个值将属性的取值范围分为两个部分，其中一个范围中的值小于等于“候选点”的值，另一个范围中的值大于“分割点”的值。例如，一个连续的区间[a,b]被分割成[a,c]和(c,b],其中c是分割点。不同的算法根据不同的标准来衡量候选点的优劣，其中一种衡量候选点优劣程度的标准是根据一个分割或合并与类别标号的关联，如基于熵的衡量标准和基于统计的衡量标准。“停止准则”指出何时停止离散化过程，它实质上是一个精确性与易理解性的折中。离散化程度越高，数据的精确性越差，丢失信息量越大，但是使得离散分类跟容易归纳和理解。离散化程度越低，数据保有的信息量越大，但是不容归纳出数据与分类的关系和对数据的理解。此外，停止准则还需要考虑数据不一致性的问题，即两个数据对象所有属性的值都相同，但是所属类别不同。离散化过程导致的数据不一致性不应该比离散化之前原有数据的不一致性高。2.2离散化方法的分类及特点离散化方法依据不同的需求沿着不同的主线发展至今，目前已存在很多不同离散化方法的分类体系。不同的分类体系强调离散化方法间的区别的不同方面。主要的分类体系有有监督的和无监督的、动态的和静态的、全局的和局部的、分裂式的（从上至下）和合并式的（从下至上）、单变量的和多变量的以及直接的和增量式的。根据离散化方法是否在离散化过程当中使用数据集的类别标注信息，离散化方法可以分为有监督的离散化方法和无监督的离散化方法。其中无监督的离散化方法在离散化过程当中无需使用类别信息，这类方法的典型代表是分箱方法，包括等宽度分箱和等频率分箱。分箱方法使用箱均值或箱中位数替换箱中的每一个值来将数据离散化。实际应用中，分箱方法效果不佳，特别是当数值数据分布不均匀的时候。有监督的离散化方法在离散化过程当中需要使用类别信息。以前的研究表明，有监督的方法比无监督的方法效果要好。离散化方法也常以动态或静态的分类方法来区分。动态的离散化方法就是在建立分类模型的同时对连续特征进行离散化，如分类算法C4.5。静态的离散化方法就是在进行分类之前完成离散化处理。根据离散化过程是否是针对整个训练数据空间的，离散化方法又可分为全局的和局部的。全局的离散化方法使用所有的实例，而局部的离散化方法只是用一部分的实例。离散化方法还可分为从上至下的和从下至上的，也可称为分裂式的和合并式的。分裂的离散化方法起始的分裂点列表是空的，通过离散化过程逐渐往列表中加入分裂点，而合并的离散化方法则是将所有的连续值都看作可能的分裂点，再逐渐合并相邻区域的值形成区间。单变量的离散化方法是指一次只对数据集的一个特征进行离散化，而多变量的离散化是同时考虑数据集的多个特征及其相互关联关系进行离散化，需要考虑更多的因素，算法更加复杂。另外一种离散化方法的分类是直接式的和增量式的。直接式的离散化方法就是根据额外给定的参数（离散化所需得到的区间数等）一次性形成所有的分裂点，而增量式的离散化方法是根据某个准则逐渐的将离散化结果进行改进，直到满足准则的停止条件为止。2.3离散化结果的评价不同的离散化方法会产生不同的离散化结果。优良的离散化，应使划分尽可能简约，又尽可能多的保留由样本数据代表的对象的固有特性。离散化结果的好坏可以从以下几方面来考虑：(1)区间的个数。这也是对模型简洁性的要求。理论上来说，离散得到的区间数越少越好，便于理解，但区间数的减少另一方面也会导致数据的可理解性变差;(2)离散化所导致的不一致性。离散化之后数据的不一致性不能比离散化之前更高。这一点是对模型一致性的要求。（3）预测准确性。即对模型准确性的要求。这一点通常通过交叉检验模式建立分类树来衡量。3.常用的离散化方法3.1基于熵的离散化方法3.1.1基于熵的一般化方法熵(Entropy)是最常用的离散化度量之一。基于熵的离散化是一种监督的、自顶向下的分裂技术。它在计算和确定分裂点时利用分布信息。例如，为了离散化属性A，该方法选择A的具有最小熵的值作为分裂点，并递归地划分结果区间，得到分层离散化。这种离散化形成A的概念分层。设D由属性集和类标号属性定义的数据元组组成。类标号属性提供每个元组的类信息。该集合中属性A的基于熵的离散化基本方法如下：A的每个值都可以看作一个划分A的值域的潜在的区间边界或分裂点（记作split_point）。也就是说，A的分裂点可以将D中的元组划分成分别满足条件A≦split_point和A≥split_point的两个子集，这样就创建了一个二元离散化。选择分裂点对数据集进行划分的目的是为了将数据更清晰地分类。理想的状态下，我们希望每一个分类中的元组所属类别尽可能地少，即分类后各类中的元组的类别尽可能地一致，也就是说在属性A上按照split_point划分D后为了得到完全的分类所需要的信息越少。为了度量某一划分之后得到完全的分类还需要信息，引入期望信息需求的概念，期望信息需求由下式给出:()||||()||||()其中，和分别对应于D中满足条件A≤split_point和A≥split_point的元组，||是D中的元组的个数，如此等等。集合中的熵函数根据下式来计算，假设集合中的元素分别属于m个类，它们分别为，，…,,的熵是()∑其中，是中元组属于的概率，由中的类元组数除以中的元组总数||确定。这样在选择属性A的分裂点时，我们希望产生使得期望信息需求最小的属性值split_point作为分裂点，使得用A≤split_point和Asplit_point划分之后，对元组完全分类还需要的信息量最小.确定分裂点的过程递归地作用于所得到的每个划分，直到满足某个终止标准，如当所有候选点上的最小信息需求小于一个阈值，或者当区间的个数大于阈值max_interval时终止。3.1.2CAIM方法CAIM（class-attributeinterdependencemaximization）方法是一种基于熵、自顶向下的数值属性离散化方法，大致过程和基于熵的一般化方法类似。也是选择一个分裂点split_point，将属性的取值区间划分为A≤split_point和A﹥split_point两个子区间。不同的是度量按分裂点分裂以后，度量分裂优劣的方法。CAIM方法采用类-属性相互依赖来度量一个分裂结果的优劣。CAIM标准的计算需要如下一张二维表：表1类别及区间内元组分布信息表ClassIntervalCTotal[]…[]…[]…………………………………………………InTotal……M其中：表示属于第i类，第j个区域中的数据元组的个数，表示数据集中属于第i类的元组的总数，表示第r个区间中的元组的个数。CAIM度量标准的公式如下：(|)∑其中n是区间个数，是上表一中第r列中的最大值。CAIM值越大，类和离散区间之间的相互依赖越大。CAIM算法用一个贪心算法通过寻找局部最大化CAIM值的方法来得到近似的全局最大化的值。CAIM算法的伪代码如下：Given:DataconsistingofMexamples,Sclasses,andcontinuousattributesFiForeveryFido:Step1.1.1Findmaximum(),andminimumvaluesof1.2Formasetofalldistinctvaluesofinascendingorder,andinitializeallpossibleintervalboundariesBwithminimum,maximumandallthemidpointsofalltheadjacentpairsintheset.1.3SettheinitialdiscretizationschemeasD:{[，]}.setGlobalCAIM=0.Step2.2.1Initializek=1.2.2Tentativelyaddaninnerboundary,whichisnotalreadyinD,fromB,andcalculatecorrespondingCAIMvalue.2.3AfterallthetentativeadditionshavebeentriedaccepttheonewiththehighestvalueofCAIM.2.4If(CAIMGlobalCAIMorkS)thenupdateDwiththeacceptedinStep2.3boundaryandsetGlobalCAIM=CAIM,elseterminate.2.5Setk=k+1andgoto2.2.Output:DiscretizationschemeD3.2基于Chi-square的方法3.2.1ChiMerge方法ChiMerge是一种基于的离散化方法[2]，它采用自底向上的策略，递归地找出最佳临近区间，然后合并它们，形成较大的区间。这种方法是监督的，它使用类信息。其基本思想是，对于精确的离散化，相对类频率在一个区间内应当相当一致。因此，如果两个临近的区间具有相似的类分布，则这两个区间可以合并。否则，它们应当保持分开。ChiMerge过程如下。初始，将数值属性A的每个不同的值看作一个区间。对每个相邻区间进行检验。具有最小值得相邻区间合并在一起，因为低值表明它们具有相似的雷分布。合并过程递归地进行，直到满足预先定义的终止标准。其中，计算值得公式如下：χ∑∑()其中：k为类别数，为在第i个区间、j个类别中的属性值数目；为落在第i个区间中数值个数，∑；为第j类中的数值数目，∑；N为所有数值数据的个数，即∑；为的期望频率，。如果或者中其中一个为0，被设置成0.1。统计量的自由度为k-1。终止判定标准通常由三个条件决定。首先，当所有的相邻对的值都低于指定的显著水品确定的某个阈值时合并停止。检验的置信水平值太高可能导致过分离散化，而太低的值可能导致离散化不足。通常，置信水平设在0.10~0.01之间。其次区间数可能少于预先指定的max-interval。最后ChiMerge的前提是区间内的相对类频率应当相当一致。实践中，某些不一