数值数据离散化.docx

数据离散化方法综述
摘要:数据离散化是一个训练集预处理的方法，用于将连续的数值属性转化为离散的数值属性。离散数值属性在数据挖掘的过程中具有重要的作用。本文首先介绍了离散化方法的分类，同时还按照分类介绍几种具有代表性的离散化方法。然后比较各种离散化方法在特定应用环境下的优势和不足，提出需根据具体应用特征选取离散化方法。
关键字：连续属性； 离散属性； 数据离散化
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后为了得到完全的分类所需要的信息越少。为了度量某一划分之后得到完全的分类还需要信息，引入期望信息需求的概念，期望信息需求由下式给出:
InfoAD=D1DEntropyD1+D2DEntropy(D2)
其中，D1和D2分别对应于D中满足条件A≤split_point和A≥split_point的元组，D是D中的元组的个数，如此等等。集合中的熵函数根据下式来计算，假设集合D1中的元素分别属于m个类，它们分别为C1，C2，…,Cm,D1的熵是
EntropyD1=-i=1mpilog2pi
其中，pi是D1中元组属于Ci的概率，由D1中的Ci类元组数除以D1中的元组总数D1确定。这样在选择属性A的分裂点时，我们希望产生使得期望信息需求最小的属性值split_point作为分裂点，使得用A≤split_point和A>split_point划分之后，对元组完全分类还需要的信息量最小.
确定分裂点的过程递归地作用于所得到的每个划分，直到满足某个终止标准，如当所有候选点上的最小信息需求小于一个阈值，或者当区间的个数大于阈值max_interval时终止。
3.1.2 CAIM方法
CAIM（class-attribute interdependence maximization）方法是一种基于熵、自顶向下的数值属性离散化方法，大致过程和基于熵的一般化方法类似。也是选择一个分裂点split_point，将属性的取值区间划分为A≤split_point和A﹥split_point两个子区间。不同的是度量按分裂点分裂以后，度量分裂优劣的方法。
CAIM方法采用类-属性相互依赖来度量一个分裂结果的优劣。CAIM标准的计算需要如下一张二维表：
表1类别及区间内元组分布信息表
Class
Interval
CTotal
[d0,d1]
…
[dr-1,dr]
…
[dn-1,dn]
C1
q11
…
q1r
…
q1n
M1+
…
…
…
…

…
…
Ci
qi1
…
qir
…
qin
Mi+
…
…
…
…
…
…
…
Cs
qs1
…
qsr
…
qsn
Ms+
InTotal
M+1
…
M+r
…
M+n
M
其中：qij表示属于第i类，第j个区域中的数据元组的个数，Mi+表示数据集中属于第i类的元组的总数，M+r表示第r个区间中的元组的个数。
CAIM度量标准的公式如下：
CAIMC,DF=r=1nmaxr2M+rn
其中n是区间个数，maxr是上表一中第r列中qir的最大值。CAIM值越大，类和离散区间之间的相互依赖越大。CAIM算法用一个贪心算法通过寻找局部最大化CAIM值的方法来得到近似的全局最大化的值。
CAIM算法的伪代码如下：
Given: Data consisting of M examples, S classes, and
continuous attributes Fi
For every Fi do:
Step 1.
1.1 Find maximum(dn) ,and minimum d0 values of Fi
1.2 Form a set of all distinct values of Fi in ascending order, and initialize all possible interval boundaries B with minimum, maximum and all the midpoints of all the adjacent pairs in the set.
1.3 Set the initial discretization scheme as D : d0，dn. set GlobalCAIM=0.
Step 2
2.1 Initialize k =1.
2.2 Tentatively add an inner boundary, which is not already in D, from B, and calculate corresponding CAIM value.
2.3 After all the tentative additions have been tried accept the one with the highest value of CAIM.
2.4 If (CAIM > GlobalCAIM or k < S) then update D with the accepted in Step 2.3 boundary and set GlobalCAIM=CAIM, else terminate.
2.5 Set k= k + 1 and go to 2.2.
Output: Discretization scheme D
3.2 基于Chi-square的方法
3.2.1 ChiMerge方法
ChiMerge是一种基于χ2的离散化方法[2]，它采用自底向上的策略，递归地找出最佳临近区间，然后合并它们，形成较大的区间。这种方法是监督的，它使用类信息。其基本思想是，对于精确的离散化，相对类频率在一个区间内应当相当一致。因此，如果两个临近的区间具有相似的类分布，则这两个区间可以合并。否则，它们应当保持分开。
ChiMerge过程如下。初始，将数值属性A的每个不同的值看作一个区间。对每个相邻区间进行χ2检验。具有最小χ2值得相邻区间合并在一起，因为低χ2值表明它们具有相似的雷分布。合并过程递归地进行，直到满足预先定义的终止标准。其中，计算χ2值得公式如下：
χ2=i=12j=1k(Aij-Eij)2Eij
其中：k为类别数，Aij为在第i个区间、j个类别中的属性值数目；Ri为落在第i个区间中数值个数，Ri=j=1kAij；Cj为第j类中的数值数目，Cij=i=12Aij；N为所有数值数据的个数，即N=i=12Ri；Eij为Aij的期望频率，Eij=Ri*Cj/N。如果Ri或者Cj中其中一个为0，Eij被设置成0.1。χ2统计量的自由度为k-1。
终止判定标准通常由三个条件决定。首先，当所有的相邻对的χ2值都低于指定的显著水品确定的某个阈值时合并停止。χ2检验的置信水平值太高可能导致过分离散化，而太低的值可能导致离散化不足。通常，置信水平设在0.10~0.01之间。其次区间数可能少于预先指定的max-interval。最后ChiMerge的前提是区间内的相对类频率应当相当一致。实践中，某些不一致是允许的，尽管不应当超过某个特定的阈值。
使用ChiMerge方法时需要指定一个显著性水平α，太大或太小的α会导致数值属性的过度离散化或离散化不足的现象。过度离散化会引入很多以前不存在的不一致性，因此改变了数据的性质。离散化不足时离散化算法不能很好地发挥离散化带来的作用。简而言之，不容易为ChiMerge选择一个合适的α值。因此应该让数据来决定α应该取何值，Chi2就是基于这个思想在ChiMerge的基础上改进而来的。
3.2.2 Chi2方法
Chi2算法[3]的执行过程分以下两个阶段：
阶段一中，开始时使用一个高的显著性水平，例如，0.5来离散化数值属性。对每一个数值数据根据值进行排序，然后执行以下步骤1.对于对于每对相邻的区间，使用等式（1）计算卡方值；2.将具有最低卡方值的相邻区间合并。合并的过程一直到所有的区间对的卡方值都超过了显著性水平确定的阈值为止。降低显著性水平，重复过程1和2直到离散化的数据中，数据不一致率超过了给定值δ。阶段一实质上是一个广义的ChiMerge算法，与ChiMerge给定一个卡方阈值不同的是，Chi2用一个循环将ChiMerge过程包含其中并逐渐增大卡方阈值（通过降低显著性水平）。并引进了一个数据不一致率来作为离散化过程的停止条件以保证离散化以后的数据能够精确地代表原始数据。
阶段二是阶段一的执行过程的优化，用阶段一使用的显著性水平开始，每一个属性都有一个显著性水平与之对应，这些属性轮流做合并。每次在某个属性上合并完了以后都会进行一致性检查，如果不一致率没有超过给定的阈值，就将这一属性对应的显著性水平减小用于下一轮的合并，否则，这一属性就不再参与下一轮的合并。这一过程一直进行到没有任何一个属性上还能够进行区间合并。
当阶段二结束时，如果某个属性上的值都被合并到了同一个区间，这表明这一属性与表示原始数据无关，应该被剔除。因此离散化过程结束时，属性选择也完成了。
Chi2 算法伪代码
Phase 1:
set sigLevel = 0.5;
do while (InConsistency(data) < δ) {
for each numeric attribute {
Sort(attribute, data);
chi-sq-initialization(attribute, data) ;
do {
chi-sq-calculation (attribute, data);
} while (Merge(data))
}
sigLevel0 = siglevel;
sigLeve1 = decreSigLevel(sigLeve1);
}

Phase 2:
set all sigLvlCi1 = sigLevelO for attribute
do until no-attribute-can-be-merged {
for each attribute i that can be merged {
Sort(attribute, data);
chi-sq-initialization( attribute, data) ;
do {
chi-sq-calculation(attribute,data);
} while (Merge(data1)
if (InConsistency(data) < δ)
sigLvl [ i] = decreSigLeve1 (sigLvl [il ) ;
else
attribute i cannot be merged;
}
}
3.3基于聚类分析的离散化方法
3.3.1聚类分析离散化方法的一般过程
基于聚类待分析的离散化方法[6][7][8]一般包含两个步骤，首先是将某特征的值用聚类算法（如K-means算法）通过考虑特征值的分布以及数据点的邻近性，划分成簇或者组。然后是将聚类得到的簇进行再处理，可分为自顶向下的分裂策略和自底向上的合并策略。分裂策略是将每一个初始簇进一步分裂为若干子簇，合并策略则是通过反复地对邻近簇进行合并。聚类分析的离散化方法也需要用户指定簇的个数，从而决定离散产生的区间数。
3.3.2一种基于聚类的离散化方法
算法的第一个阶段采用中值聚类方法对数据集进行聚类，聚类过程如下：（1）由于数据集中的对象属性集上的单位可能不同，所以在聚类之前必须将数据连续属性值标准化到均值为0方差为1；（2）初始化时，每个对象都被当作一个簇；（2）计算簇与簇之间的距离，选择距离最小的两个簇进行合并生成新的对象簇，例如簇a与簇b的距离最小，则合并两个簇形成簇ab。（3）计算合并后的簇与剩下的其他簇的距离，继而进行下一轮合并。当对象簇中都只有一个对象时候，两个簇之间的距离定义为对象之间欧氏距离。两个簇合并以后它们和另外的簇的距离由以下公式给定：
da(bc)=dbca=αbdab+αcdac+βdbc+γdab-dac
其中αb=αc=12，β=-14，γ=0。
在合并过程中，所有的类簇构成一个对论域U的划分，属于同一个类簇的元素被认为是不可区分的。因此我们应该继续类簇的合并直到合并后产生的数据的不一致性高于原始数据的不一致性，至此完成了聚类过程。

第二个阶段对聚类的结果进行整理与合并，令r是产生的聚类的个数，K是聚类产生的某一个类簇。这个类簇中的元素在属性Aj上的投影的集合为：
DPAjK=xje|e∈K
因此，定义根据对象在属性Aj上的取值定义类簇Kj划分间隔Ik,Aj为：
Ik,Aj=LK,Aj,RK,Aj=minDPAjK,max⁡(DPAjK)
对于一个给定的属性Aj，定义类簇K的域有可能是定义其他的类簇的域相交，此时去掉包含在其他域中的域，然后整理剩下的域使之互不相交。
后处理过程涉及合并相邻的区间来减少对象簇的个数。合并的过程包括计算所有属性上的所有相邻区间的类熵。选择类熵最小的两个相邻区间合并直到数据的不一致性超过了某个阈值。
4.根据应用环境选择离散化方法
需要注意的是，虽然已有很多离散化方法，但是没有一种离散化方法对任何数据集以及任何算法都是有效的，也没有一种离散化方法一定比其他方法产生更好的离散化结果。因为离散化本身就是一个NP-hard 问题，所以在使用时一定要根据数据集的特点和学习环境以及使用者个人的偏好理解等选择合适的离散化方法，以取得尽可能好的离散化效果。如，决策树学习容易受到碎片问题的影响，所以离散化时更偏好得到较少的离散化区间；决策规则希望离散化得到的区间中的实例的类标签是唯一的；关联规则重视特征间的相关性，所以在离散化时不能对各个特征进行单一的离散化。
以关联规则分析为例。在进行关联规则分析时，需要重视特征间的联系，而不能对数据集的各个特征进行单一的离散化。对各个特征进行孤立的离散化会破坏原始数据集的特征内在相关性，从而导致推导出不完善的关联规则，影响关联规则分析的正确性和有效性。所以关联规则分析中的连续特征离散化应考虑选择多变量的离散化方法。
并且，关联规则分析中采用的数据集在某些情况下是没有类信息的，无法使用有监督的离散化方法来进行连续特征的离散化。故在离散化时应考虑采用无监督的离散化方法，而现阶段无监督的离散化方法的发展还比较有限，主要是等宽等频离散化方法及基于聚类的离散化方法，故关联规则分析中的离散化问题将是一个很值得研究的方面，有效地解决关联分析中连续特征的离散化问题也将有效地促进关联规则分析。此外，针对其他的算法和学习环境，也应相应的分析离散化的要求，从而选择合适的离散化算法。
5.结束语
数值数据离散化在数据预处理中发挥着重要的作用。对数据进行离散化将提高后续数据处理过程的速度和效果有重要的意义。注意到没有任何离散化算法可以适用于任何环境下，在实际应用时，需要根据数据集的特点和学习环境等选择合适的离散化方法。

参考文献
[1] Kotsiantis S, Kanellopoulos D. Discretization techniques: A recent survey[J]. GESTS International Transactions on Computer Science and Engineering, 2006, 32(1): 47-58.
[2]Kerber, R., ChiMerge: Discretization of Numeric Attributes. X National Conf. on Artificial Intelligence American Association (AAAI92). USA, 1992, 123-128
[3] Liu, H. and Setiono, R. 1997. Feature selection and discretization. IEEE Transactions on Knowledge and Data Engineering, 9:1–4.
[4] Su C T, Hsu J H. An extended Chi2 algorithm for discretization of real value attributes[J]. Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(3): 437-441.
[5] Kurgan, L.A., Cios, K.J., CAIM Discretization Algorithm. IEEE Transactions on Knowledge and Data Engineering 16:2 (2004) 145-153
[6] Pfahringer B. Compression-based discretization of continuous attributes[C]//ICML. 1995: 456-463.
[7] Chmielewski M R, Grzymala-Busse J W. Global discretization of continuous attributes as preprocessing for machine learning[J]. International journal of approximate reasoning, 1996, 15(4): 319-331.
[8] 王彬． 熵与信息［M］． 西安: 西北工业大学出版社，1994．
[9] 谭旭，高妍方，陈英武． 区间型多属性决策求解新方法［J］． 系统
工程与电子技术，2007，29( 7) : 1082 － 1085．
[10] 王美义，张凤呜，刘智． 模糊信息的熵权多属性决策方案评估方
法［J］． 系统工程与电子技术，2006，28( 10) : 1523 － 1525．
[11] 陈雷，王延章． 基于熵权系数与TOPSIS 集成评价决策方法的研
究［J］． 控制与决策，2003，18( 4) : 456 － 459．
[12] 王坚强，何波． 基于证据推理的信息不完全确定的MCDM 方法
［J］． 系统工程与电子技术，2005，27( 4) : 659 － 661．
[13] 谢宏，程浩忠，牛东晓． 基于信息熵的粗糙集连续属性离散化算
法［J］． 计算机学报，2005，28( 9) : 1570 － 1574．