基于改进χ2统计的数据离散化算法

桑 雨， 李 克 秋＊， 闫 德 勤

(1.大连理工大学 计算机科学与技术学院，辽宁 大连 116024；2.辽宁师范大学 计算机与信息技术学院，辽宁 大连 116029)

0 引 言

随着数据库中信息量的增加以及信息管理水平的不断提高，涌现了各种类型的数据来描述客观世界.在应用机器学习从数据中提取知识时，涉及的数据通常包括离散值(如男、女)和连续值(如身高、温度等).然而，大多数的数据挖掘、归纳学习等算法仅仅适用于使用离散化方法描述的样本，如 C4.5[1]和 AQ 算法[2]等.因此，连续属性必须进行离散化，其实质是分割连续属性的值域，转化成若干个有意义的区间，简化数据，提高分类器的学习精度.

离散化算法的类型有[3]考虑类信息的有监督类型和不考虑类信息的无监督类型；考虑整体样本的全局型和考虑部分样本的局部型；相邻区间合并的自底向上型(bottom－up)和区间分割的自顶向下型(top－down).EQW 和 EQF[3]是实现简单且计算消耗低的自顶向下无监督离散化算法.著名的自顶向下有监督离散化算法包括基于信息熵理论的算法，如Ent－MDLP[4]；基于类属性相互依赖的算法，如 CACC[5].Ent－MDLP通过定义信息熵标准来最小化模型总的信息量，同时利用MDLP来决定合适的离散区间数.CACC是目前最新的基于类－属性相互依赖的离散化算法，它提出了一个启发式断点选择标准，考虑了所有样本的分布信息，并且避免了过拟合现象，产生了理想的离散化方案.著名的自底向上有监督离散化算法包括基于统计学理论的Chi2－based相关算法[6～9]，如 ChiMerge[6]和 Extended Chi2[9]等.它们首先初始化区间，采用χ2统计来判断当前相邻区间是否被合并，并且通过不一致衡量标准来判断离散化进程是否结束.

基于χ2统计的方法是目前最有效的离散化算法之一.自由度与期望频数的选取直接影响χ2计算的准确性，从而影响离散化的性能.本文提出一种基于改进χ2统计的数据离散化算法，该算法考虑相邻区间数对自由度的影响.此外，对于没有在相邻区间中出现的类，期望频数均取一个预先给定的常数，忽视了自身的内在信息对期望频数的影响，导致计算χ2不准确，区间合并顺序不合理，从而降低了学习精度.因此，本文给出自由度与期望频数的合理改进方案.

1 基础知识

1.1 粗糙集[10]

设S＝ (U，A，V，F)是一个信息系统，其中U＝｛x1，x2，…，xn｝是论域，A是属性集合，V是属性取值集合，F是U×A→V的映射.A由条件属性集合C与一个决策类属性d来决定，即A＝C∪d，C∩d＝，则此信息系统被定义为决策表.

对于x，y∈U，PA是U上的一个子集(等价关系)，如果满足xPy(p∈P)(fp(x)＝fp(y))，则x和y是在等价关系P下所构成等价类集合中的元素.

定义1 假设论域U的一个子集为X，条件属性集合C的一个子集为P，则X关于P的下近似被定义为

P－X＝ ｛x∈U｜[x]PX｝

其中[x]P是P所产生等价类的元素构成的集合.

定义2 等价关系P关于决策类属性所划分的等价类｛Y1，Y2，…，Yk｝的一致性水平为其中card(·)是集合的基数.

1.2 χ2统计

离散化任务要求训练集包含N个样本，每个样本属于k个类中的其中一类，且包含m个连续属性(条件属性).基于χ2统计的自底向上离散化算法的实质是在所有相邻区间对中决定哪一对相邻区间首先被选择合并.

χ2统计可评价被离散区间与类属性之间的独立性.在离散化过程中，需要计算所有相邻区间的χ2来判断当前哪对区间先被合并，计算方法如下:

式中:k为数据集总的决策类别数；Aij为i区间j类样本数；Eij＝Ri×Cj／M，为Aij的期望频数，其中为i区间样本数为相邻两区间中j类样本数为相邻两区间的样本总数.如果Cj＝0，则Eij＝0.1.

2 改进χ2统计的离散化算法

有效的离散化标准(区间合并标准)可以产生好的离散化结果.在基于χ2统计的离散化算法中，χ2统计的合理性直接影响离散化的性能.然而，χ2统计中在自由度的选取上仅仅考虑了相邻区间的类别数，忽视了相邻区间数的作用；另外，对于没有在相邻区间中出现的类，其期望频数取一个预先给定的常数，忽视了数据类分布对期望频数取值的影响.这些缺陷导致计算χ2不准确，区间合并顺序不合理，从而降低学习精度.基于上面两点不足，本文提出一种基于改进χ2统计的数据离散化算法，该算法考虑了相邻区间数对自由度的影响，并依据数据类分布给出了合理的期望频数，能够合理准确地进行离散化.下面，具体分析这两点不足并且提出有效的改进方案.

2.1 χ2分布中自由度选取的不足及改进

在Chi2算法[7]中，χ2分布的自由度选取为v＝k－1，k为数据总的决策类别数.改进的Chi2算法[8]认为自由度的选择应该根据划分断点两边区间的类别数来确定，即v＝k′－1，k′为相邻区间对中的类别数，2≤k′≤k.

一般来说，χ2分布的随机变量为W＝＋，其中Zi服从标准正态分布，i＝1，2，…，n.也就是说，W服从自由度为n－1的χ2分布，即分布.这样，式(2)中的χ2相当于χ2分布的随机变量，由2k′项的加和获得，即服从自由度为2k′－1的χ2分布.在自由度的选取上，χ2统计仅仅考虑了相邻区间的类别数，忽视了相邻区间数的作用；换句话说，自由度选取不仅仅与相邻区间的类别数有关，还与相邻区间数有关.因此，应该选取v＝2k′－1作为χ2统计显著性检验的自由度.

2.2 χ2分布中期望频数Eij取值的不足及改进

在式(2)中，如果Cj＝0，则Eij＝0.1.也就是说，如果相邻区间的类别数小于总的类别数(k′＜k)，则对于没有在相邻区间中出现的类，其期望频数Eij均取一个预先给定的值0.1.然而，这忽视了数据类分布对Eij取值的影响，导致计算χ2不准确以及不合理的区间合并顺序.

假设存在两对相邻区间，其中一个区间对的类别数大于另一对的，且与数据集总类数不等.然而，如果类别较多的区间对的类分布较均匀，而类别较少的区间对的类分布不均匀，考虑公平性，如果区间对类别较多，则适当降低Eij取值；如果区间对类别较少，则适当增加Eij取值.基于上面分析，针对数据本身的特点，本文启发式地选取(2k－v)／2k作为Eij取值的重要部分.然而，当数据集总的类别数为3时，(2k－v)／2k中的v是常量，因此，不能区分出各对相邻区间χ2函数中Eij的差异.本文考虑了相邻区间对的自由度与区间大小的相关关系，即自由度越大，区间样本数越多；自由度越小，区间样本数越少，所以，选取(NM)／N作为Eij取值的另一部分.总之，如果相邻两区间的自由度较大，则使Eij按较小比例增加；如果相邻两区间的自由度较小，则使Eij按较大比例增加.基于上面的分析，有以下改进方案:

如果k′＜k，并且Cj＝0，则有

其中N为数据集总的样本数，v＝2k′－1(以改进的自由度为标准)，2≤k′≤k，i∈｛1，2｝，1＜j≤k.

注 意:式 (3)中 [(2k－v)／2k]· [(N－M)／N]前面乘以2有以下原因.

从上面的分析中可以看到，式(3)可以完整地反映出Eij取值在χ2统计中的合理性，并很好地解决了χ2统计应用在Chi2－based算法中的缺陷.

2.3 算法描述

本文所提出的基于改进χ2统计的数据离散化算法基于的是Chi2－based算法的框架，分为两个阶段进行离散化:第一阶段考虑整体属性进行区间合并，算法通过不一致衡量标准自动地进行离散化，当被离散数据的不一致率超过原始数据不一致率时，算法停止；第二阶段对每个属性进行离散化，使得离散化更加精确.注意:新算法的区间合并标准为差异与Extended Chi2算法[9]相似，不同的是，本文提出的和χ2采用的是第2章中改进的算法.

基于改进χ2统计的离散化算法描述如下.

第一阶段:

步骤1 设置显著水平α＝0.5，根据式(1)计算数据的一致性水平γc.

步骤2 升序排序每个连续属性的值，计算所有相邻区间改进后的χ2以及差异D.

步骤3 考虑整体连续属性，选择合适的相邻区间进行合并

下面，对新算法的时间复杂度做具体分析.每个连续属性值排序的时间复杂度为O(NlogN)；对于本文提出的算法，对χ2统计量做了两处改进:一是自由度的改进；原始自由度v＝k′－1与改进自由度v＝2k′－1都是通过相邻两区间中的类别数k′决定的，然而，求得相邻区间类别数的时间复杂度是不发生变化的，因此，自由度的改进没有影响求得差异D所需时间的变化.二是χ2中Eij取值的改进；对于Extended Chi2算法，计算χ2的时间复杂度为O(2kN)，改进Eij取值后，计算χ2的时间复杂度为O(2kN)＋O(M)＝O(2kN)，这里M＜N.综上，在对χ2统计量改进后，不会影响求得差异D所需时间的变化.由于所提出算法的框架相似于Extended Chi2的框架，新算法的时间复杂度仍为O(KmNlogN)，其中m为连续属性个数，K为算法的增量步数.

3 性能评价

在实验中，采用了UCI机器学习数据库[11]中的9个数据集(见表1)来评价本文所提算法的性能.数据集均是数据挖掘等实验所常用的.将所提出的基于改进χ2统计的离散化算法与下列4种算法进行了比较.

(1)EQF:经典的无监督离散化算法[3]；

(2)Ent－MDLP:基于熵的离散化算法[4]；

(3)Ext－Chi2:最先进的自底向上离散化算法[9]；

(4)CACC:最先进的自顶向下离散化算法[5].

表1 数据集描述Tab.1 Description of datasets

9个数据集全部通过上述离散化算法进行离散化，在VC＋＋6.0环境下实现.将离散后的数据应用C4.5方法构造决策树，并采用Naive贝叶斯分类器进行分类预测，使用Weka数据挖掘工具[12]进行分类预测，采用10折交叉验证的方法[13]对平均学习精度统计进行对比(见表2和3).

表2 C4.5分类预测结果Tab.2 Classification and prediction results by C4.5%

表3 Naive贝叶斯分类预测结果Tab.3 Classification and prediction results by Naive Bayes %

由表2可以看出，在9个数据集上，本文算法的平均分类精度有所提高.由于EQF、Ent－MDLP和CACC均没有考虑离散化过程中的数据信息丢失情况，与本文算法和Ext－Chi2算法相比，这3种算法有较低的分类精度.

由表3可以看出，在正确识别率方面，本文算法的平均学习精度是最高的，可见，当χ2统计量改善后数据的平均学习精度显著提高，充分显示了本文所提算法的有效性.

4 结 语

基于概率统计理论的Chi2系列算法为连续属性离散化算法的研究提供了新的思路.本文分析了Chi2系列算法中χ2统计量的不足，并提出了合理的改进方案，获得了期望的离散化结果，提高了分类器的学习精度.

[1]QUINLAN J R.C4.5:Programs for Machine Learning [M].San Mateo:Morgan Kaufmann，1993

[2]MICHALSKI R S，MOZETIC I，HONG Ja－rong，etal.The multi－purpose incremental learning system AQ15and its testing application to three medical domains [C]／／ Proceedings of Fifth National Conference on Artificial Intelligence.Pennsylvania:AAAI Press，1986:1041－1045

[3]DOUGHERTY J， KOHAVI R，SAHAMI M.Supervised and unsupervised discretization of continuous feature [C]／／ Proceedings of 12th International Conference of Machine Learning.San Mateo:Morgan Kaufmann，1995:194－202

[4]FAYYAD U，IRANI K.Multi－interval discretization of continuous－valued attributes for classification learning [C]／／ Proceedings of Thirteenth International Joint Conference on Artificial Intelligence.San Mateo:Morgan Kaufmann，1993:1022－1027

[5]TSAI C J，LEE C I，YANG W P.A discretization algorithm based on class－attributes contingency coefficient[J].Information Sciences，2008，178(17):714－731

[6]KERBER R.ChiMerge:discretization of numeric attributes [C]／／ Proceedings of Ninth National Conference on Artificial Intelligence.San Jose:AAAI Press，1992:123－128

[7]LIU H， SETIONO R. Feature selection via discretization [J].IEEE Transactions on Knowledge and Data Engineering，1997，9(4):642－645

[8]TAY E H，SHEN L.A modified Chi2algorithm for discretization [J].IEEE Transactions on Knowledge and Data Engineering，2002，14(3):666－670

[9]SU C T，HSU J H.An extended Chi2algorithm for discretization of real value attributes [J].IEEE Transactions on Knowledge and Data Engineering，2005，17(3):437－441

[10]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11(5):341－356

[11]HETTICH S，BAY S D.The UCI KDD archive[DB／OL]. [2010－08－25].http:／／kdd.ics.uci.edu／，1999

[12]PENTAHO.Weka 3:data mining software in Java[EB／OL]. [2010－08－25]. http:／／www.cs.waikato.ac.nz／ml／weka，2007

[13]WEISS S M，KULIKOWSKI C A.Computer systems that learn:classification and prediction methods from statistics，neural nets [M]／／Machine Learning and Expert Systems.San Mateo:Morgan Kaufmann，1990