数据挖掘技术探讨：基于错误率的全局离散化方法

　　【eNet硅谷动力专稿】计算机技术的迅速发展使处理数据成为可能，这就推动了数据库技术的巨大发展，但是面对不断增加如潮水般的数据，人们不再满足于数据库的查询功能，提出了更深层次的问题：能不能从数据中提取信息或者知识为决策服务。就数据库技术而言已经显得无能为力了，同样，传统的统计技术也面临着巨大的挑战，这就急需新的方法来处理这些海量般的数据。于是，数据挖掘技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。数据挖掘发现的知识可以被用于信息管理、查询、优化、决策支持、过程控制、还可用于数据自身的维护。

　　然而，现实世界中的几乎所有数据挖掘工作都包含连续属性，而很多数据挖掘领域使用的算法只适用于名称型属性空间，因此除非对这些连续属性进行离散化，否则，数据挖掘工作将无法进行。这就要求对数据离散化进行研究。

　　一、离散化的研究现状

　　连续属性的离散化问题被广泛研究，并取得了大量成果，研究人员从不同领域提出了多种离散化方法，可以从以下三个方面进行分类：

　　局部离散化和全局离散化

　　局部离散化在实例空间的子集上进行离散化，典型算法有C4.5(Quinlan 1993,1996)以及Entropy Minimization(Fayyad & Irani 1993)；而全局离散化在整个实例空间上进行离散化，典型算法有binning，D-2(Catlett 1991)，ChiMerge(Kerber 1992)，1R(Holte 1993)，StatDisc(Richeldi & Rissitto 1995)。一般来说，局部离散化的精确度要高于全局离散化，但全局离散化的执行速度要高于局部离散化。

　　监督离散化和非监督离散化

　　监督离散化在离散化过程中使用实例的类标信息，通过某种标准衡量被离散属性和类标之间的内部相关性来进行离散化，典型的算法有：C4.5(Quinlan 1993,1996)，Entropy Minimization(Fayyad & Irani 1993)，D-2(Catlett 1991)，ChiMerge(Kerber 1992)，StatDisc(Richeldi & Rissitto 1995)；而非监督离散化算法在离散化过程中不考虑实例的类标信息，典型的算法有Equal Interval Width ，Equal Frequency Intervals。因为非监督的离散化方法在设定分割区间的时候没有利用实例的类标信息，这就有可能造成分类信息的丢失，因而非监督离散化方法的精确度要低于监督离散化算法，但它的执行时间小于监督离散化。

　　静态离散化和动态离散化

　　静态离散化对每一个属性单独进行离散化，即对一个连续属性进行离散化的时候不考虑其它连续属性，典型的算法有binning，Ent-MDLPC，1R(Holte 1993)，C4.5(Quinlan 1993,1996)；而动态离散化对所有连续属性同时进行离散化，在离散化过程中考虑各连续属性之间的相互依赖性，因而动态离散化的结果可能要好于静态离散化。

　　二、预测错误率

　　当用一个属性预测一个与之关联的属性的值时，预测错误率定义了该预测发生错误的百分比。

　　为了理解预测错误率的含义，我们首先考虑下面的简单例子：用一个三元属性A来预测另一个二元属性B的值。假定使用的数据集合包含N个实例，它的取值分布情况如下表所示：

　　
表1 预测结果取值分布表

　　属性A的每一个值被用来预测属性B的值，但A的相邻值不能预测同一个B值。所以存在两种可能的预测，或者是 ，或者是 。假如使用前者进行预测，则错误预测的个数为 ；假如使用后者，则错误预测的个数为 。每种预测的错误率定义为该预测的错误个数百分比，即错误预测的个数在总的实例数中所占的比例。最小预测错误率的定义如下：

　　

　　一般情况下，用含有k个值的属性A来预测另一属性B，属性A的k个值中的任意一个必须与属性B的一个值配对，并且要满足下面两个条件：a) 至少要预测属性B的两个值；b) A的相邻的值不能预测B的同一个值。假如属性A具有k个不同的值，属性B具有j个不同的值。则可能的预测的个数将接近但是要小于 个。其中的一个预测必然能够达到最小的预测错误率，我们称该预测为最优预测。

　　三、使用预测错误率进行离散化

　　利用预测错误率进行离散化首先把整个连续属性的取值空间看成是一个分割区间，然后选择能达到最优预测的分割点将整个取值空间一分为二，在所得的两个分割区间上重复上述过程直到最小预测错误率不再改善为止，最后，我们就得到了所求的分割区间。