论文部分内容阅读
摘要：本文针对现有的决策树分类算法中，存在若干影响运行效率的因素对避免这种重复等问题进行了探讨，提出了一种基于数据集决策树分类算法，算法使用了扫描一遍数据构建属性统计表组的方法，减小了由于连续属性值过多而使AVC过大导致无法放于内存的问题。实验验证测试了本文提出的改进后算法的有效性，从而降低了算法的时间复杂性
关键词：数据挖掘；分类器；决策树
中图分类号：TP391 文献标识码：A文章编号：1007-9599 （2011） 04-0000-02
Research Based on Data Sets and Decision Tree Classifier
Yang Peng
(Guangzhou Panyu Polytechnic,School of Information Engineering,Guangzhou511483,China)
Abstract:This paper first discussed the data-browsing-repetition problem during getting the data statistical information in the stage of building Decision Tree Classifier.Based on some new published classifier algorithms,we gave out an ameliorated solution,and realized a Decision Tree Classifier which could be applied to large scale dataset.Then some actual simulation testing validated the solution’s efficiency
Keywords:Data mining;Classifier;Decision tree
分类分析在数据挖掘研究中占有重要的位置。所谓分类，是通过分析训练数据样本，学会一个分类函数或分类模型，该函数或模型把给定数据集的数据项映射到类别集合中的某一个类别。常见的分类分析方法有以下几种：决策树方法、贝叶斯方法、人工神经网络方法、粗集方法和遗传算法。不同的算法适用于不同特点的数据集。其中，决策树以其易于理解、分类器易于生成以及预测准确度较高等特点，是应用最为广泛的方法之一[1]。本文将主要围绕决策树分类器对大规模数据集的适用进行探讨。
一、决策树建树算法
决策树的构建是在建树阶段完成的。在建树阶段，训练集被递归分割。分割终止的判定条件为：被测试分割的子集中的所有记录都属于同一个类，或节点对应的数据集的数据量太少，进一步分割已无实际意义。对应于每一次数据集的分割，都会在决策树上产生一个新的节点。初始时，决策树只有一个根节点对应于整个数据集；在对节点对应的数据集D进行分割时，首先根据分割选择策略CL找到最好的分割标准t，之后用t将D分割成D1，D2，与D对应的节点填入分割信息，与D1，D2对应的新节点就成为D节点的子节点。然后递归地对各个节点进行分割，直至分割终止。
实现决策树算法的主要过程有两个：一是所需统计信息的计算，二是按照设定的分割规则对数据集进行分割。即代之于数据的重新组合，另外设置标识信息对数据的划分加以标记。以SLIQ[2]、SPRINT[3]为代表，许多算法的改进都是基于这两个过程进行的。
二、决策树构建算法分析
SLIQ和SPRINT的改进是引入了属性表、类别分布表。其基本思路如下：
（一）初始设置时，为每个属性建立一个属性表
属性表的一条记录对应数据集中的一条记录。属性表由三部分构成：数据记录号，相应的属性值和记录类别。对于连续属性，属性表预先按属性值的给定顺序进行排序。
（二）节点分割标准的求解
将决策树中除叶节点外的任意节点称作内部节点。建树阶段包含三个主要步骤：首先，对每一个内部节点，读取每个属性所对应的属性表，求解相应的最小gini值；其次，从所有求得的属性gini值中选取最小的为该节点的分割标准；最后，按照确定的分割标准将属性表分解为两个子集，分别对应该节点的左右子节点。
（三）树的修剪
运用最小描述长度原理对生成的决策树进行修剪。引入属性表的优点：保证了数据的一致性，可分布并行处理，适应大规模数据分类；连续属性的预排序使得求解分割点更加简单等等。但改进后的算法仍存在以下的问题：
首先，采用属性表、类表虽然减小了单个表的规模，却增加了附加的数据记录，需额外耗费存储空间来保存属性表等表数据，算法所需空间大小至少是原来的两倍。
第二，求取各节点分割的统计信息必须对各属性表依次扫描一遍。极端的情况下，若属性表很大，需全部放在外存。而在某节点为获得必要的分割判断信息，必须对每个属性表进行扫描。这时，若有m条记录，n个属性，那么每次生成统计表需扫描属性表中的m*n个记录。显然，采用属性表、类表增加了需访问的数据记录数。
第三，求解连续属性的分割点时，需预先对数据集按连续属性的顺序进行排序，并对每个可能的分割点进行求解。若该连续属性有n个不同的值，潜在的分割点就有n-1个。
针对数据冗余问题，由于求解分割标准只需知道当前节点上数据集的相应统计信息即可，据此提出了AVC二维表。如图1所示。该思路的关键在于，对节点的每一属性分别建立相应的AVC表——即为AVC-group后，求解该节点的分割标准时只需访问其对应的AVC-group，而不必再访问数据集。
RainForest存在两个影响算法性能的因素：
1.为建立每个属性的AVC二维表，需要多次扫描节点对应的数据集；
2.数据的连续属性往往使AVC二维表实际上非常庞大，全部进入内存几乎不可能。
在CLOUDS中，Alsabti等人[5]区别于将连续属性简单地离散化的方法，引入了分段确定连续属性gini值下界的思路，即将连续属性值分成若干段，求解各段的gini下界；之后从gini下界最小的段中求出全局最小gini值。相应的连续属性值即为该属性的分割点。
三、决策树分类器算法的实现
基于标识表的主要操作为：
1.初始化：将数据集记录的标识号读入标识表；
2.根据f_id的起、止号f_ids、f_ide（即节点处的数据集的第一条和最后一条记录的f_id），将其标识号f_id´满足f_ids f_id´ f_ide的相应的d_rid的记录组成集合。对于由此得到的数据集合，利用Get_info统计数据的分布信息进而得到该节点的统计表组；当节点处数据集合分割后，传递给子孙节点的只是相应数据记录在标识表中的起、止位置；
3.按分割标准对标识表进行调整：同一节点的数据标号放在相邻的区域。
四、算法性能与测试
在具体实现时，选择RAD开发工具C++ Builder、Microsoft SQL Server 2000、Microsoft Windows 2000的单机开发环境。CPU为Pentium（Ⅱ）400Mhz型，内存196MB。为KDD CUP 1999 Data数据，共有42个属性：3个离散属性（protocol_type，service，flag），39个连续属性（浮点类型或整型）；一个类别（class）；以及一个记录标号（Recid）。
在建树阶段，某一节点的计算量主要为数据集上统计信息的获取、分割标准的确定以及对分割后数据的标示。其中，数据集上属性-类别表阵列的构建是算法运行的基础，也是影响算法运行效率的主要部分。
测试结果说明，一次扫描与多次扫描的运行时间相比，前者效果明显优于后者。其次，由于改进算法可以实现如文献[1]中介绍的在节点分割时生成子节点的属性-类别表组，所以有效地减少了对外存的访问。
五、结束语
本文针对现有的决策树分类算法中存在的为生成统计数据而重复扫描，从而增加了时间复杂度的问题，提出了改进方法，并在此基础上实现了适用于大数据集的决策数分类器。通过实例测试，验证了该方法在减少决策树建树时间方面是有效的。
参考文献：
[1]邹瑞芝等.基于粗糙集理论的决策树分类方法[J].计算机工程与科学，2009，31（10）
[2]刘鹏.一众健壮有效的决策树改进模型[J]计算机工程与应用，2005，41（33）
[3]朱绍文，陆玉昌.决策树采掘技术及发展趋势[J]. 计算机工程， 2000，26（10）.
[4]唐华松，姚辉文.数据挖掘中决策树算法的探讨[J]. 计算机应用研究， 2001，18（8）
[5]闫建辉等. 基于最大熵选取实例的增量决策树归纳[J]，计算机工程与应用，2006，42（35）
[作者简介]
杨鹏（1978-），女（汉族），湖南株洲人，硕士研究生，讲师，主要研究方向数据库技术、图形图像处理、软件测试。
关键词：数据挖掘；分类器；决策树
中图分类号：TP391 文献标识码：A文章编号：1007-9599 （2011） 04-0000-02
Research Based on Data Sets and Decision Tree Classifier
Yang Peng
(Guangzhou Panyu Polytechnic,School of Information Engineering,Guangzhou511483,China)
Abstract:This paper first discussed the data-browsing-repetition problem during getting the data statistical information in the stage of building Decision Tree Classifier.Based on some new published classifier algorithms,we gave out an ameliorated solution,and realized a Decision Tree Classifier which could be applied to large scale dataset.Then some actual simulation testing validated the solution’s efficiency
Keywords:Data mining;Classifier;Decision tree
分类分析在数据挖掘研究中占有重要的位置。所谓分类，是通过分析训练数据样本，学会一个分类函数或分类模型，该函数或模型把给定数据集的数据项映射到类别集合中的某一个类别。常见的分类分析方法有以下几种：决策树方法、贝叶斯方法、人工神经网络方法、粗集方法和遗传算法。不同的算法适用于不同特点的数据集。其中，决策树以其易于理解、分类器易于生成以及预测准确度较高等特点，是应用最为广泛的方法之一[1]。本文将主要围绕决策树分类器对大规模数据集的适用进行探讨。
一、决策树建树算法
决策树的构建是在建树阶段完成的。在建树阶段，训练集被递归分割。分割终止的判定条件为：被测试分割的子集中的所有记录都属于同一个类，或节点对应的数据集的数据量太少，进一步分割已无实际意义。对应于每一次数据集的分割，都会在决策树上产生一个新的节点。初始时，决策树只有一个根节点对应于整个数据集；在对节点对应的数据集D进行分割时，首先根据分割选择策略CL找到最好的分割标准t，之后用t将D分割成D1，D2，与D对应的节点填入分割信息，与D1，D2对应的新节点就成为D节点的子节点。然后递归地对各个节点进行分割，直至分割终止。
实现决策树算法的主要过程有两个：一是所需统计信息的计算，二是按照设定的分割规则对数据集进行分割。即代之于数据的重新组合，另外设置标识信息对数据的划分加以标记。以SLIQ[2]、SPRINT[3]为代表，许多算法的改进都是基于这两个过程进行的。
二、决策树构建算法分析
SLIQ和SPRINT的改进是引入了属性表、类别分布表。其基本思路如下：
（一）初始设置时，为每个属性建立一个属性表
属性表的一条记录对应数据集中的一条记录。属性表由三部分构成：数据记录号，相应的属性值和记录类别。对于连续属性，属性表预先按属性值的给定顺序进行排序。
（二）节点分割标准的求解
将决策树中除叶节点外的任意节点称作内部节点。建树阶段包含三个主要步骤：首先，对每一个内部节点，读取每个属性所对应的属性表，求解相应的最小gini值；其次，从所有求得的属性gini值中选取最小的为该节点的分割标准；最后，按照确定的分割标准将属性表分解为两个子集，分别对应该节点的左右子节点。
（三）树的修剪
运用最小描述长度原理对生成的决策树进行修剪。引入属性表的优点：保证了数据的一致性，可分布并行处理，适应大规模数据分类；连续属性的预排序使得求解分割点更加简单等等。但改进后的算法仍存在以下的问题：
首先，采用属性表、类表虽然减小了单个表的规模，却增加了附加的数据记录，需额外耗费存储空间来保存属性表等表数据，算法所需空间大小至少是原来的两倍。
第二，求取各节点分割的统计信息必须对各属性表依次扫描一遍。极端的情况下，若属性表很大，需全部放在外存。而在某节点为获得必要的分割判断信息，必须对每个属性表进行扫描。这时，若有m条记录，n个属性，那么每次生成统计表需扫描属性表中的m*n个记录。显然，采用属性表、类表增加了需访问的数据记录数。
第三，求解连续属性的分割点时，需预先对数据集按连续属性的顺序进行排序，并对每个可能的分割点进行求解。若该连续属性有n个不同的值，潜在的分割点就有n-1个。
针对数据冗余问题，由于求解分割标准只需知道当前节点上数据集的相应统计信息即可，据此提出了AVC二维表。如图1所示。该思路的关键在于，对节点的每一属性分别建立相应的AVC表——即为AVC-group后，求解该节点的分割标准时只需访问其对应的AVC-group，而不必再访问数据集。
RainForest存在两个影响算法性能的因素：
1.为建立每个属性的AVC二维表，需要多次扫描节点对应的数据集；
2.数据的连续属性往往使AVC二维表实际上非常庞大，全部进入内存几乎不可能。
在CLOUDS中，Alsabti等人[5]区别于将连续属性简单地离散化的方法，引入了分段确定连续属性gini值下界的思路，即将连续属性值分成若干段，求解各段的gini下界；之后从gini下界最小的段中求出全局最小gini值。相应的连续属性值即为该属性的分割点。
三、决策树分类器算法的实现
基于标识表的主要操作为：
1.初始化：将数据集记录的标识号读入标识表；
2.根据f_id的起、止号f_ids、f_ide（即节点处的数据集的第一条和最后一条记录的f_id），将其标识号f_id´满足f_ids f_id´ f_ide的相应的d_rid的记录组成集合。对于由此得到的数据集合，利用Get_info统计数据的分布信息进而得到该节点的统计表组；当节点处数据集合分割后，传递给子孙节点的只是相应数据记录在标识表中的起、止位置；
3.按分割标准对标识表进行调整：同一节点的数据标号放在相邻的区域。
四、算法性能与测试
在具体实现时，选择RAD开发工具C++ Builder、Microsoft SQL Server 2000、Microsoft Windows 2000的单机开发环境。CPU为Pentium（Ⅱ）400Mhz型，内存196MB。为KDD CUP 1999 Data数据，共有42个属性：3个离散属性（protocol_type，service，flag），39个连续属性（浮点类型或整型）；一个类别（class）；以及一个记录标号（Recid）。
在建树阶段，某一节点的计算量主要为数据集上统计信息的获取、分割标准的确定以及对分割后数据的标示。其中，数据集上属性-类别表阵列的构建是算法运行的基础，也是影响算法运行效率的主要部分。
测试结果说明，一次扫描与多次扫描的运行时间相比，前者效果明显优于后者。其次，由于改进算法可以实现如文献[1]中介绍的在节点分割时生成子节点的属性-类别表组，所以有效地减少了对外存的访问。
五、结束语
本文针对现有的决策树分类算法中存在的为生成统计数据而重复扫描，从而增加了时间复杂度的问题，提出了改进方法，并在此基础上实现了适用于大数据集的决策数分类器。通过实例测试，验证了该方法在减少决策树建树时间方面是有效的。
参考文献：
[1]邹瑞芝等.基于粗糙集理论的决策树分类方法[J].计算机工程与科学，2009，31（10）
[2]刘鹏.一众健壮有效的决策树改进模型[J]计算机工程与应用，2005，41（33）
[3]朱绍文，陆玉昌.决策树采掘技术及发展趋势[J]. 计算机工程， 2000，26（10）.
[4]唐华松，姚辉文.数据挖掘中决策树算法的探讨[J]. 计算机应用研究， 2001，18（8）
[5]闫建辉等. 基于最大熵选取实例的增量决策树归纳[J]，计算机工程与应用，2006，42（35）
[作者简介]
杨鹏（1978-），女（汉族），湖南株洲人，硕士研究生，讲师，主要研究方向数据库技术、图形图像处理、软件测试。