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

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

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

　　一、离散化的研究现状

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

　　局部离散化和全局离散化

　　局部离散化在实例空间的子集上进行离散化，典型算法有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个不同的值。则可能的预测的个数将接近但是要小于 个。其中的一个预测必然能够达到最小的预测错误率，我们称该预测为最优预测。

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

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

边界点的确定

　　假如数据集包含N个实例，则至多有 个候选分割点。尽管如此，我们没有必要考虑每一个分割点。《Fayyad & Irani(1992)》证明对于熵极小化来说，最优的分割点通常是这样两个相邻属性值的中点：这两个属性值不同并且所表示的实例的类是也不同的，这样的点称为边界点。不幸地是，在现实世界的问题中，连续属性的同一值可能具有很多类标。例如，“温度”表示某数据集中的一个连续属性，该数据集中可能包含很多“温度”值相同的实例，但这些实例的类标是不同的。《Elomaa &Rousu(1996)》将上述边界点的概念推广到包含属性值相同但类标不同的实例的数据集上。上述两篇文章都证明了最优分割点必然是边界点。上面的结论可以用于预测错误率值的最小化。通过下面的小例子可以很容易理解上述结论。

　　

表2 类标为a或b的连续属性的边界点

　　表2显示了一个连续属性的取值以及每个值对应的类标（a和b）。边界点确定如下：值20和30的中点并不是边界点，因为这两个值的类标是相同的。30和40的中点A是边界点，因为因为这两个值的类标是不相同的。虽然值40和50的类标是相同的，我们还不能完全肯定它们的中点不是边界点，需要继续往后看因为值50具有不同的类标。根据《Elomaa &Rousu(1996)》的理论，假如某个值（例如值50）具有不同的类标，则该值的左右边界应视为边界点,所以40和50的中点B,50和60的中点C都为边界点。我们就使用这种方法来确定连续属性的边界点。我们根据边界点得到了一个边界点表，该表显示了每个边界点以及该点及其后继边界点所对应的区间中各个类的出现次数。表3就表示根据表1得到的边界点表（最后一行的边界点一栏为空，表示最后一个分割区间）。

　　

表3 根据图1所示的边界点得到的边界点表

　　使用预测错误率进行二分化

　　每个分割区间可以按如下过程一分为二（二分化）。分割区间中出现的每个类属性值的数目被记录在一个频率表中。正常情况下，该表应该包含二个或者更多的类属性值，它们中必有一个出现的次数是最高的，我们称该类属性为这个分割区间的主类。假如我们要预测落在该区间中的实例的类别，主类无疑是最好的选择。分割区间可以根据任何一个落在它中的边界点值二分化，但二分化的前提条件是经过二分化后，两个子区间的主类的和大于二分化之前的主类值，因为只有这样，二分化后的最小预测错误率才会比二分化之前小。最小预测错误值可以用实例总数减去二分化后的两个区间的主类值和来计算出来。在一个分割区间中，我们计算每个边界点的预测错误率，然后选择测错误率最小的点将分割区间一分为二。

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

　　上面介绍的二分化过程是将一个连续属性离散成k个区间的启发式方法的基础。该方法是一种爬山式方法，依次找出每个分割点，所以，该方法找到的分割点是很好的但并不能保证是最优的。

　　假定类属性B具有j个不同的值，则将连续属性A分割成k个区间的过程如下：第一步，计算连续属性A的每个边界点的预测错误率，然后选择测错误率最小的边界点将分割区间一分为二；第二步，二分化过程分别在两个子区间上进行直到不能再分割为止。不幸地是，这有可能产生数目巨大的分割区间。为了克服这个缺点，我们增加了一个终止条件：当分割区间的数目大于类属性的数目时分割过程终止。

　　经过上述离散化过程，连续属性被划分成一系列的子区间。在有些情况下，相邻分割区间可能预测同一个类值，为了简化合并过程，这些分割区间会被合并。

　　四、计算复杂度

　　所有的连续属性的离散化过程都需要对属性值进行排序。在全局离散化方法中，连续属性值只需要一次排序并且可以重复使用，这同决策树的每个样本空间都需要重新排序的局部离散化方法相比，是一个计算上的优点。所以，全局离散化方法计算复杂度为 ，n表示数据集包含的实例数。

　　边界点表的计算复杂度为 ，n表示数据集包含的实例数。使用边界点表搜索一次分割点的时间杂度为 ，m表示类标的数目。假如整个过程需要k次这样的搜索，则当 时，找出所有的分割点的的时间复杂度为 。因而离散化一个连续变量的总的时间复杂度为 。因为在现实世界中的应用中，实例的数目通常大于类标的数目，所以当m很小时，该离散化方法的时间复杂度近似为 。

　　五、经验评价

　　我们将上述离散化方法同C4.5(Quinlan 1996)的局部离散化方法在20个数据集上进行了比较，这20个数据集中有10个数据集的类标数大于二。C4.5的离散化方法是局部离散化方法。我们用基于错误率的离散化方法对连续变量进行全局离散化，离散化后的结果别输入到C4.5分类器中来构造决策树。

　　实验中用到的数据集来源于现实生活的真实数据集，每种离散化方法在每个数据集上测试五次。

　　表4给出了分类精度的结果，结果表明基于错误率的离散化方法的精确度同C4.5分类器的局部离散化方法的精确度相当。

　　

表4 使用C4.5自带局部离散化方法、基于错误率的离散化方法的分类精度

　　表5给出了当数据集的类标数大于6时的算法的执行时间。实验结果表明基于错误率的离散化方法的计算时间要小于C4.5的局部离散化方法的执行时间。因为基于错误率的离散化方法的精确度同C4.5分类器的局部离散化方法的精确度相当，但前者的执行时间要小于C4.5的局部离散化方法，因而基于错误率的离散化方法要好于C4.5分类器的局部离散化方法。

　　

表5 二种离散化方法的执行时间（单位 分：秒）

　　结论

　　我们进行了一系列的实验来评价基于错误率的全局离散化方法。实验结果表明基于错误率的离散化方法的精确度同C4.5分类器的局部离散化方法的精确度相当，但是前者的运行速度明显快于后者。

　　关于该算法其实还有好多工作要做。比如，一，当离散化方法用于类标数很大的数据集时，它的运行时间和精度会怎样；二，对于该算法采用的终止条件还应该能细化以期望获得更好的性能；三，近来，Naive-Bayesian分类器在机器学习领域引起了广泛的注意，它已被证明是知识表示的重要工具，将该离散化方法应用于Naive-Bayesian分类器性能如何

微信扫一扫实时了解行业动态

微信扫一扫分享本文给好友