决策树算法及应用

决策树算法及应用（共8篇）

决策树算法及应用 篇1

摘要：决策树算法是一种直观的、易于理解和实现的科学算法, 将决策树算法积极运用于学生选课系统中能够获得诸多良好的效果。本文在分析决策树以及决策树分类算法中最常使用的C4.5算法的基础上, 重点研究了决策树算法在学生选课系统中的应用。

关键词：决策树算法,学生选课系统,C4.5算法,应用

如何提高学校网络选课系统的使用效率和质量, 有效发挥选课系统的功能与作用, 是各大教育机构最为关切的重点课题。决策树算法是一种直观的、易于理解和实现的科学算法, 将决策树算法积极运用于学生选课系统中能够获益良多, 对于提高学生选课系统利用率具有极大帮助。

1 决策树

决策树是一种直观的图解法、预测模型, 其建立在概率分析基础之上, 人们在把握研究对象各种已知情况发生概率前提下运用决策分支画来分析各种情况的映射关系, 最终构成一个类似于二叉树结构的空间架构图, 因图形很像一棵散开的树而用术语称为决策树。决策树主要由3个层次构成: (1) 最顶层为根节点, 由根节点向下分支不同的小节点; (2) 中间层为叶子节点, 相当于属性的展示, 利用每个分支的测试属性功能可以测试出节点的属性; (3) 最终层为叶节点, 该层主要负责规划类别, 当开始由树根向下逐层测试时, 根据节点属性系统会自动规划节点类别。通过构造决策树模型, 我们可以利用模型的数据生成、预测2大功能来得出某些规律或进行预测, 模型中树的根节点相当于一个空间的集合, 叶子节点与叶节点是空间集合的分裂子集, 通过属性测试可可生成多个数据集合, 最终形成叶节点的集合数据, 可获得规律集合便于分析和研究。

2 决策树分类算法--C4.5算法

在决策树分类算法当中, C4.5是一种最常使用的算法, 其是基于ID3算法而延伸的一种更具效率性、准确性的算法。C4.5算法被广泛应用于多个研究领域, 主要由3大步骤组成: (1) 算法:由决策树提供给定的训练数据, Generate Decision Tre; (2) 输入:samples (训练样本) 、Attribute list (备选属性集合) ; (3) 随后输出:一棵决策树。具体如下:

(1) 生成根节点N; (2) IF T都属于D的同类, 返回叶节点N后可标记为D; (3) IF attribuetlist为空或T中所剩余的样本数, 若样本数低于给定值则可返回叶节点N, 其中标记N为T类中出现最多次数的类; (4) For each attribuetlist代表中属性, 其计算信息的增幅率为inf ormation gain ratio; (5) N的测试属性为test attribute=attribuetlist, 因而attribuetlist具有最高级增幅率属性; (6) IF的属性测试具有连续性, 找到IF属性即为该属性的分割阀值; (7) For each的节点N为一种始发的叶节点 (IF的叶节点和样本子集T相对应, 为空时改分裂节点可生成始发节点, 从而标记为T中出现最多的类。)

3 决策树算法在学生选课系统中的应用

学生选课系统的规划和设计复杂而繁琐, 需要涉及许多计算机方面的知识, 同时选课系统是否合理、科学直接关系到教育者对相关信息的收集、整理和分析, 进而最终影响整个选课教学质量以及学生对选修课的积极性。其中, 目标数据挖掘、课程设计决策树分类法结果是决策树算法与技术在学生选课系统中的应用。

3.1 目标数据挖掘

笔者从学校官网中随机抽取了一些不同类学生的基本信息, 运用决策树算法和技术对这些学生信息进行统一分类, 综合分析学生的爱好及需求, 以实现目标数据挖掘, 如表1是对学生信息进行处理的方法。最后, 以所得的目标属性、目标数据来设置选修课程, 以确保选修课程能够得到学生的认可与接受, 数据挖掘后最终生成决策树, 如图1所示。

(其中1、0分别代表女生、男生;0、1、2分别代表一、二、三年级;0、1分别代表文科、理科;0、1、2分别代表文学课、艺术课和专业课)

3.2 课程设计决策树分类法结果

根据学生的爱好、需求以及期望值, 运用决策树算法得出的结果显示:对专业选修课有兴趣爱好的多为二、三年级学生, 男女比例相当, 这是由于二、三年级学生开始为其今后毕业做准备, 以提高自身的专业知识与技能为根本学习目标。而对文学选修课有兴趣爱好的多为一、二年级学生, 男女比例相当, 这是由于一年级学生需要学习较多的专业课程, 自身学习任务与压力较大, 因而在选修课程上偏向于简单、轻松的课程, 主要以开拓眼界与知识面为目标。对于艺术选修课有兴趣爱好的学生很少, 一般是一年级女生偏向选择该课程。由此数据分类结果得看得出一个结论:决定不同年级学生选课类型与方向的主要因素是兴趣爱好、就业两大因素, 其中低年级选择选修课程大多由自身爱好决定, 而高年级学生在选择选修课程时更多考虑的是求职就业。

参考文献

[1]朱娟, 杨丰华.改进的决策树算法在教务管理数据挖掘系统中的应用[J].教育技术导刊, 2010 (4) .

基于属性约简的决策树算法研究 篇2

关键词：决策树 ；ID3算法；属性相似度

中图法分类号：TP301文献标识码：A 文章编号：1009-3044(2007)15-30830-02

Research about Decision Tree Algorithm Based on Attribute Reduction Technology

CHU You-bin, TANG Rui-chun, Wang Jie-qiang

(Ocean University of China, Qingdao 266000,China)

Abstract: The irrelevant or distracting attributes in datasets would have negative effect on decision making and lead to lower performance of classifier. In order to solve this problem, a new decision tree algorithm is proposed in this paper. It has an attribute selection on the sample data, and all the other attributes are eliminated except the most relevant attributes .Then the similar degrees of attributes between the test and the decision are computed and used as the inspiring rule to produce the decision tree. The new algorithm also uses the threshold quantity of classification to simplify the process of building the decision tree. The experiments show that the operation efficiency and the accuracy of the new algorithm are higher than the classic ID3 on some datasets.

Key words: Decision tree; ID3; Similar degree of attribute

1 引言

决策树方法是一种典型的分类方法，它采用自顶向下的分治策略进行分类，具有速度快、精度高、生成的模式简单等优点。构造一个决策树分类模型通常分为两部分：树的构建与树的剪枝。其中树的构建基本思路为：如果训练例子集中的所有例子都是同类的，则将之作为叶子结点，结点内容就是该类别标记。否则，根据某种策略选择一个最优属性，按此属性把训练例子集合分成各个子集，使得每个子集中的所有例子在此属性上都具有相同的属性值，然后再依次递归处理各个子集。树的构建过程中的主要环节是找出最优属性和根据最优属性对训练集进行分割。到目前为止，已经出现了很多典型的决策树算法，例如ID3、C4.5、SLIQ SPRINT等。

构造好的决策树的关键在于如何选择好的逻辑判断或属性。决策树算法要在每个节点选出能对样本进行最好划分的属性。从理论上讲，无关或是无用的属性是不应该被选中的。如果样本的属性越多，就需要算法有更强的属性识别能力，更好的启发规则来挑选属性。然而实践中，决策树算法却很容易受到这些无关或无用的属性的干扰。因而本文在决策树生成之前，对数据集的属性进行了约简选择。通过去除不相关的属性，降低了数据的维数，使其后的决策树生成更加高效和简洁。

2 属性的约简

决策树是在每个节点挑选最有希望成功的属性进行分裂的，从理论上讲决不选择无关的或是无用的属性。属性越多，从理论上看，就需要越强的识别能力。实验显示，无用的属性会影响决策树的分类性能，导致性能变差（在实验的情形中下降了5%至10%）[1]。变差的原因是由于在决策树的某些节点处，无关的属性不可避免地被选择为决定分支的属性，导致使用测试数据测试时产生随机误差。正因为无用属性对决策树生成性能的干扰，所以在使用决策树进行分类之前进行属性的选择是十分必要的。只保留一些最为相关的属性，而将其他属性去除。通过去除不适当的属性，可以改善决策树算法的性能，提高生成效率，更重要的是可以形成更为紧凑、更容易理解的目标概念表达方式，使用户的注意力集中在最为相关的变量上。

2.1 粗糙集理论在属性约简上的应用

粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家Z.Pawlak在1982年首先提出的。粗糙集一经提出就立刻引起数据挖掘研究人员的注意，并被广泛讨论[3]。

基于信息系统S{U ,A=C∪D，V ,f} ,其中, U 为有限对象集合,即论域；C 是条件属性集合, D是决策属性集合,且满足C∩D为空集,则称S 为决策系统；V 是C 和D 的值域；函数f(x,q)∈Vq, ?坌q ∈A , x∈U。这样，U 中的每个对象x 都可以用一个基于属性值A 的矢量表示，而属性值A 表明对象x 可以获得的知识信息。在一个决策系统中，各个条件属性之间往往存在着某种程度上的依赖和分类，约简可理解为在不丢失关键信息的前提下，以最简单的决策属性对条件属性集合进行分类。

设P和Q为U 中的等价关系(IND(P))，Q的P正域记为POSp (Q)，即POSp (Q) =∪Px,x∈U/ Q，Q的正域是U中所有根据分类U/P的信息，可以准确地划分到关系Q的等价类中去的对象集合。C1称为C相对于决策属性集D的约简,即C的D约简,如果满足：C1?哿C，C1≠?椎；POSIND(C1) (IND (D) ) = POSIND(C)(IND(D))

不存在C2?奂C1 ，使POSIND(C2)(IND(D))= POSIND(C1)(IND (D) )

则C的所有D约简的集合记为REDD(C)，C的所有D约简的交集称为核，即CORED(C) =∩REDD(C)。可以利用C相对于D的任一约简来代替C，而不会对决策有任何影响，这就是粗糙集属性约简的原理。

2.2 基于属性相似度的决策树生成

ID3与C4.5算法使用计算熵的方法来确定条件属性的选择。但是计算信息熵的时间复杂度较高，有时会带来不当的划分，如决策属性的选择偏向于出现频率较高的属性和只具有单一值的属性。为解决以上问题，引入了相关性分析方法，即在选择划分条件的属性时，计算每个属性与目的属性之间的相关性，从中选择相关性最大的一个属性作为划分决策树的属性。

属性相似度是指由测试属性不同取值代替决策属性进行正确决策的支持度。在决策树算法中，选择测试属性的依据是当前属性能最大程度的直接做出正确的决策。而在测试属性中只有根据不同的测试属性取值作为判断依据。测试属性不同取值的个数同决策属性类别数相近，说明测试属性的取值类与决策属性的分类数相似。如果测试属性A的取值Ai的n条记录中决策为Dj的取值数为m，则Ai与Dj相似度为m/n。如果测试属性取值分类数与决策属性类别数相差较大，则相对测试属性的每个取值与决策类的相似度就较小。因此属性相似度不仅体现了测试属性的分类能力，而且避免了信息熵分类中趋向于测试属性取值较多优先的情况。

设A为测试属性，A1,A2,…An为A的n个不同取值，D决策属性，D1,D2,…Dm为D的不同决策在训练集中的记录数，PDj为Dj类决策在训练集中的比例。并记Aij为A的取值为Ai时决策为第Dj类的记录数，PAij为Ai取值中第Dj类决策的比例。于是A的不同取值下各种决策情况可用矩阵表示如图1所示：

图1 矩阵表示

仔细分析该矩阵，每一行的和代表训练集中取值为Ai的记录数目，每一列的和代表训练集中取值为Dj的记录数目。属性相似度的计算步骤如下：(1)首先对矩阵的列按列的和的大小，从大到小顺序排列，这样第一列对应的是决策属性取值最多的那个类别；(2)查找第一列中数目最大的那个元素，取出其数值。如果最大值元素不止一个，则比较测试属性取值的条数，以条数少的测试属性取值代替决策属性取值；(3)删除最大元素对应的行和列，即删除对应的决策属性取值列和测试属性取值行；(4)如果矩阵行数或列数大于1，则跳到第(2)步；否则转到第(5)步；(5)将所有从矩阵中取出的值相加，然后除以训练集的记录总数，就得到最后的该测试属性相对于决策属性的属性相关度。

3 新的决策树生成算法

3.1 算法描述

本文在属性相似度的研究基础上，提出了一种新的有别于ID3算法基于信息熵的属性选择方法。新算法在选择划分属性时，通过计算属性相似度，选取相似度最大的那个属性作为当前节点的测试属性。同时使用基于专业经验的分类阈值，即当数据集中超过指定阈值的记录都是属于同一类别的，则认为此数据集不必再继续划分，即可生成决策树的叶子节点，标记为超过阈值的那个决策类别。算法描述如下：

算法：makeTree 由给定的训练数据产生一棵决策树

输入：训练样本data，由离散属性表示

输出：一棵决策树

方法：

if data中没有数据记录 then 返回一个空节点；

if data都在同一个类C中或属于C类的记录概率超过指定阈值then，生成一个叶子节点，并以类C标记；

if data中只剩下决策属性 then 生成一个叶子节点，以data中最普通的类标记；//多数表决

针对data中所有测试属性，计算它们同决策属性的属性相似度；

选择属性相似度最大的那个测试属性test_attribute；

生成一个属性节点，标记为test_attribute；

for each test_attribute中的所有已知值ai ；//划分data

设di是data中test_attribute= ai的样本集合，从di中去除属性test_attribute；

调用makeTree(di)；

结束for循环；

3.2 新算法的性能测试

为了验证新算法的性能，本文在Weka数据挖掘平台下实现了该算法并对其进行了实验分析和评估。

3.2.1 实验数据特征

本文所用的实验数据均来自UCI实验数据库，实验过程中选择了其中的四个数据集作为实验数据，实验数据的基本特征如表1所示,因为新算法不能处理连续值的属性，因而选取的数据集所有属性均为离散值属性。另外breast-cancer和mushroom有缺失值的情况，本文进行了缺失值的补全处理。

表1 实验数据特征描述

3.2.2 实验结果

新算法首先要对属性进行约简选择，此步骤本文是采用工具软件Weka来执行的。在对数据集分别使用新算法和ID3算法来进行决策规则的挖掘，采用10-折交叉验证后得到的实验结果如表2所示：

表2 实验结果

实验结果表明，新算法的执行效率明显优于ID3算法，并且通过根据不同的数据集来调整采用的分类阈值，新算法在这些数据集中的准确率也要高于ID3算法。

3.2.3 实验分析和算法评估

实验结果也显示出由于在决策树生成之前加入了属性的约简选择，并且使用了比信息熵更加简单的属性相似度的计算，使得新算法在执行效率上明显优于ID3算法。新算法针对不同的数据集，通过相应的调整分类阈值，在四个数据集上的预测准确率都优于ID3算法。

由实验结果可以看到，不同的数据集上的分类阈值并不相同，本文是通过很多次的实验才确定了最佳的阈值。在实际的数据挖掘实践中，如何正确把握此阈值在不同情况下的最佳取值还有待进一步的研究。

假设数据集约简选择后剩余属性个数为m,决策类别个数为n，则计算属性相似度算法的时间复杂度为O(m*n)。当m和n数目都很大时，新算法的执行效率会受到很大影响。因而算法适用于决策类别数目较少的数据集。

4 结束语

本文研究了一种基于属性相似度的决策树分类器。首先通过属性选择，只保留最为相关的属性，而将其他属性都去除。然后通过计算测试属性与决策属性的相似度作为启发规则来构造决策树。算法还使用了分类阈值设定简化了决策树的生成过程。最后通过在不同数据集上的实验对新算法进行了评估。虽然新算法是针对ID3算法的改进，但是仍然存在有很多ID3固有的不足之处：(1)不能处理连续值的属性；(2)没有对缺失值和噪声的处理功能；(3)有可能会产生过度拟合的情况。算法以上的不足还有待下一步更深入的研究和改进。

参考文献：

[1]Ian H. Written, Eibe Frank. 数据挖掘：实用机器学习技术(第2版)[M]. 北京：机械工业出版社，2006.2.41-55.

[2]Jiawei Han, Micheline Kamber.数据挖掘概念与技术[M].北京：机械工业出版社，2005.8.185-194.

[3]毛国君,段丽娟,王实等.数据挖掘原理与算法[M].北京:清华大学出版社 .2005.7.26-29.

[4]陈文伟，黄金才.数据仓库与数据挖掘[M].北京:人民邮电出版社，2004,4-5.

决策树算法及应用 篇3

客户关系管理体系的核心理念是对客户的价值进行发现和管理, 通过对既有客户的价值进行分类, 制定针对性的营销策略, 从而使价值不同的客户的实际需求得到满足, 以发展新客户, 降低运营成本。随着企业的发展壮大, 如何对海量的客户数据信息进行处理和利用, 提取对企业经营有用的信息, 以辅助营销决策, 是一个亟待解决的问题。目前的CRM数据库难以对数据信息中特有的关系与规则进行发现, 数据挖掘技术由于能够抽取出客户数据中的有价值信息, 从而为企业决策提供支持, 成为目前研究的一个热点。

2. 客户关系管理中的数据挖掘技术

在客户关系管理系统中, 数据挖掘技术可以通过对客户行为的描述和预测, 来使客户关系管理流程得到优化, 从而提升企业客户关系管理的效率。将数据挖掘技术结合数据仓库, 能够使挖掘的过程实现自动化, 利用面向对象的开发方法, 最终开发出高效易用的CRM系统。

由于看待问题角度不同, 数据挖掘技术在客户关系管理系统中可以分为两类过程, 一是以技术为中心的过程, 二是以商业为中心的过程。前者所关注的是数据的科学处理和运转, 使用智能方法, 从技术角度进行数据的处理, 向用户提供挖掘的知识;后者则更注重商业投资回报率和对数据的理解等, 从业务问题出发, 进行数据挖掘的应用, 并预测投资回报率。

3. 企业客户关系管理系统的设计

3.1 系统需求分析

结合企业不断发展的业务要求, 企业客户关系管理系统应满足以下几个方面的要求: (1) 能够进行客户信息的快速收集与共享:即分析CRM大量客户和潜在客户的信息, 进行有针对性的服务; (2) 优化客户交互渠道:将客户来自不同媒介的的请求和反馈进行集成, 并在数据库中进行准确地、完整地记录; (3) 客户数据库的集中管理:即统一控制客户信息, 实现信息的实时处理, 与系统各功能模块实现联动; (4) 良好的网络的支持能力; (5) 与面向客户的工作流集成的能力; (6) 管理决策支持的能力。

3.2 系统具体设计

(1) 具体模块的设计

在系统需求的基础上, 将系统所要实现的几个主要功能分别划分为相关的模块, 具体包括:系统管理模块、客户管理、营销管理模块、服务与支持模块、数据统计模块。

系统管理模块主要对用户角色与权限进行维护;客户管理模块管理客户和联系人信息;营销管理模块对产品营销的全过程进行流程管理;服务与支持模块对客户反馈和交流BBS论坛进行维护;数据统计模块可以根据用户的需求, 进行营销信息和客户情况的统计与分析。

(2) 系统数据库的设计

篇幅所限, 本文仅阐述产品销售数据库的设计。在销售关系中, 所包含的表文件的结构以及表之间的关系如图1所示:

(3) 系统整体结构设计

本系统的架构选择了三层B/S模式, 包括客户层, 网络应用层以及数据库服务器层。如图2所示:

图中, 应用服务器作为一个独立的进程, 负责处理来自Web服务器的应用请求。应用服务器还进行事务管理, 向数据处理层的数据库服务器发送具体的数据操作。客户端不需要安装任何软件, 只需具备普通的浏览器即可。Web客户端作为最终的用户界面, 负责向应用服务器提交用户的请求, 同时将来自应用服务器的反馈信息显示给用户。数据库服务器则存储客户的资料和产品销售情况等, 以备查询。

4. 数据挖掘决策树算法的具体应用

4.1 客户分类流程

结合数据挖掘决策树算法能够对企业客户进行筛选与分类, 从而使潜在客户群体与该群体所期望的商品建立联系, 并结合客户需求与市场情况进行促销方案的制订, 以提升营销反馈。只有用分类法对客户的反应行为进行分析, 才有可能把企业的潜在客户逐渐发展为新的客户群体。本文基于数据挖掘技术, 用分类方法去处理客户反映行为模式, 具体的过程如下:

(1) 确定客户的行为模式以及分析操作的精细度。举例来讲, 在企业进行一对一营销时, 就应将分析粒度细化到每一位客户的反应模式。

(2) 结合上一步所确定的分类目标, 从系统的数据库中提取数据源, 为进一步的分析做好准备。

(3) 以分类目标为基准, 进行变量的选择和转化。

(4) 选取适合的分类方法, 处理样本数据, 确定具体的分类器模型。

(5) 结合上一步所构建的分类器模型来预测企业的潜在用户, 从中挑选对企业商品和服务最感兴趣的用户, 进行排序操作。

4.2 数据准备

对客户的反应行为模式进行分析, 是有效获取潜在客户的关键。这一操作的前提是分析企业运营时的历史数据, 所以, 数据准备工作是必要的前提。

本文所设计的数据库是操作性的数据库, 主要目的是用于事务处理, 并对在日常商业行为中所产生的大量数据信息进行存储。考虑到系统的业务数据库是实时记录信息数据的, 难以对数据库的复杂查询和海量信息处理作出快速的响应, 而数据仓库则可克服这一局限, 以主题为依据, 有效集成多个异构的数据源, 从而满足数据挖掘以及面向分析型的处理, 因此首先建立数据仓库, 作为数据准备。

建立数据仓库的前提是结合数据挖掘的主题来确定其结构。本文选用星型模型建立数据仓库, 并注重数据仓库的规范化以及仓库中的元素间的关系。首先对一个主题之下的数据源进行精确定义, 之后确定数据信息的查询方案, 此外还需对常用的主题领域进行界定。针对本文所设计的系统实际需求, 由于需要对企业产品的销售情况进行分析, 所以将客户情况、销售数量、合同文本作为主题领域。在数据库中设定事实表, 在系统的每一个维度均设定维度表。在此基础上, 将事实表里的一些字段设置为外部关键字, 而每一个外部关键字则与一个相应的维度表相对应, 并将维度表所对应的属性字段作为主关键字, 以此来形成数据库之内的多维关系。在每一个维度表内, 不但定义了每个维度的主关键字, 同时还包括了其他描述该维数据的字段元素, 因此, 维度表可以清晰地记录维的层次。由于篇幅所限, 下面仅列出销售情况的数据仓库。

为了能结合企业销售的历史数据进行数据挖掘, 首先定义数据挖掘模型的事例集。具体到本文所设计的系统而言, 客户的消费信息体现在数据库中的客户信息表、销售信息表中。而任意一个客户的消费记录数目是不定的, 本文将“事例”定义为任意一个客户的消费信息, 而“事例集”的含义则为一组客户的消费信息。然后按照数据挖掘的要求, 将事例集存储在数据库中。通过训练数据挖掘模型, 确定模型里每一个特性的重要程度。将数据挖掘列依次添加到模型中的步骤为:

(1) 结合实际需求进行事例选取, 并确定其数据挖掘的维度与级别;

(2) 构建能够预测的数据挖掘列;

(3) 确定参与训练的数据, 构建用于输入的数据挖掘列。

4.3 模型的建立

为了建立具体的数据挖掘模型, 将数据分为两大类, 分别用于模型的训练与模型的测试。本文引入基于决策树的组合分类方法, 分析客户获取策略中二元反应行为模式, 结合分析结果, 确定具体的分类规则, 并给予Java生成数据挖掘模块。其简要类图如图所示:

4.4 对潜在客户进行排序

通过数据挖掘模型的操作, 就能获取企业的潜在客户分类规则。在此基础上以这些规则去处理企业用户的信息数据, 从而得出企业潜在客户序列。然后, 针对此序列中的潜在客户进行排序操作, 从而将这些客户的优先级别确定下来。本文所采用的排序策略是:为潜在用户进行属性的确定, 并为每一个属性分配一个合适的权值, 对某一客户的不同属性的各个权值进行求和操作, 按照权值的和的大小进行客户排序。

4.5 系统的具体实现

在本文所设计系统的实际运行中, 通过应用服务器中的会话Bean来对执行客户分析的数据挖掘模块进行调用。简要流程为:系统用户从浏览器界面发出分析潜在客户的请求, 此请求被传输至会话Bean, 会话Bean产生响应操作, 调用数据挖掘模块, 来进行数据挖掘。

5. 结束语

随着经济全球化的发展趋势, 企业之间的竞争变得更加激烈, 为了提升自身的综合实力, 越来越多的企业已经将发展理念由“产品中心”转向了“客户中心”。本文从数据准备和模型建立两个方面阐述了数据挖掘技术在客户关系管理系统中的应用, 并对潜在客户排序的策略进行了说明。基于数据挖掘技术的客户关系管理系统能够采用分类方法, 解决客户关系管理中的客户获取问题, 满足客户的个性化需求, 从而提升企业本身的竞争力。

摘要：客户关系管理系统通过对既有客户的价值进行分类来发展新客户, 降低运营成本。数据挖掘技术克服了目前的CRM系统在对数据信息中特有的关系与规则进行发现的困难, 为企业决策提供了新的解决方案。本文从数据准备和模型建立等方面阐述了数据挖掘技术在客户关系管理系统中的应用, 并对潜在客户排序的策略进行了说明。

关键词：数据挖掘,客户关系管理,潜在客户排序

参考文献

[1]George S.D., Katrina J.H., Customer Relationship Go Digital, http://www.crm2day.com/library/EpVpulykVuKbzZiCVD.PhP, Feb, 2010.

[2]B.Azvine, D.D.Nauck, et al.Intelligent Process Analytics for CRM.BT Technology Journal.2006, 24 (1) :60-61.

[3]张云涛, 龚玲著.《数据挖掘原理与技术》, 北京, 电子工业出版社, 2009.

决策树算法及应用 篇4

近些年来国内外发生了不少重大特大的突发事件,面对这些事件,世界各国政府采取了积极有效的应急措施,相应的各类应急预案的编制工作也在不断的进行着,建立健全了应对突发公共事件的应急预案机制。

然而,应急预案能否成功的运用于突发事件将直接影响应急救援效率。这就需要对预案的有效性进行预先评估,目前这方面的研究非常缺乏。文献[3]提出了基于改进的多属性群决策方法的突发事件应急预案评估,文献[4]进行了基于模糊综合评判的突发公共事件应急预案评估的研究分析,采用模糊评估理论的多级评估方法对应急预案的评估进行了大量的研究,第六届中国管理科学学术年会中提出的基于模糊综合评价方法的突发事件应急预案评估。这些的评估方法大都需要相关评估指标或属性的权重,而权重是由专家设定的,不同的专家由于主观性给出的权值会不同,最终得到的评估结果也可能会有很大的出入。决策树算法是一种基于大样本的算法,它能对所有样本数据的高度概括,即决策树能准确地识别所有样本的类别,也能有效地识别新样本的类别,可以减少人为因素的影响。

1 评价指标的建立

应急预案的实施可以看作是一个项目的实施,因此可以借鉴项目管理中后评估的方法。项目后评估可以分为:项目跟踪评估、实施效果评估和项目影响评估。应急预案的实施是为了减少突发事件造成的影响和损失,因此对应急预案实施的后评估主要从应急预案的实施过程和效果2个方面进行评估。

对应急预案的后评估是在应急预案实施后对其实施效果进行的评估,比如在应急预案实施过程中出现资源未能满足需求的情况,是由于地区资源布局不足,还是资源调度过程事件耽误,或者是应急指挥者的判断失误等等。对应急预案的一个评估主要是针对应急预案的操作步骤以及由此带来的结果的,由于不同类别不同级别的响应流程所对应的操作步骤的要求不一样,所以对应的评估指标也是不一样的。

根据应急预案的执行流程,能够知道应急响应的接警出警时间,各个部门的救援人员到位情况以及到位时间,应急预案实施过程中所需要的设备资源,凡是能够影响突发事件的一切资源,还有应急响应流程执行结束后的伤亡人数、经济损失,以及所带来的社会影响,这里将它们筛选后作为评估指标。由于主要研究的是应用决策树算法对应急预案进行评估,暂时使用分析得到的如下一些指标作为评估指标来进行试验:① 接警时间;② 各个部门的应急人员情况;③ 应急资源数量及配备情况;④ 经济损失;⑤ 伤亡人数;⑥ 救援时间。

对应急预案进行评估,其中所涉及的指标不止这些,为了简单起见,这里只拿这些指标做实验,更多的评估指标该算法同样适用。

2 决策树算法

决策树是用样本的属性作为结点,用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本中信息量最大的属性,树的中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性,决策树的叶节点代表一个类或类分布。从根节点到叶子节点的一条路径形成一条分类规则。

决策树用于对新样本的分类,即通过决策树对新样本属性值的测试,从树的根结点开始,按照样本属性的取值,逐渐沿着决策树向下,直到树的叶节点。决策树方法是数据挖掘中非常有效的分类方法。

2.1 信息论相关计算

信息熵:

${\rm H}(U)=-{\displaystyle \sum _i{\rm P}}(u{}_i)\log {}_2{\rm P}(u{}_i)$。 (1)

式中类别ui出现概率为:

${\rm P}(u{}_i)=\frac{\left|u{}_i\right|}{\left|S\right|}$。 (2)

$\left|S\right|$表示例子集S的总数;$\left|u{}_i\right|$表示类别ui的例子数。

条件熵:

${\rm H}(U/V)=-{\displaystyle \sum _J{\rm P}}(v{}_j){\displaystyle \sum _i{\rm P}}(u{}_i/v{}_j)\log {\rm P}(u{}_i/v{}_j)$。 (3)

其中属性Ai取值vi时,类别ui的条件概率为:

${\rm P}(u{}_i|v{}_j)=\frac{\left|u{}_i\right|}{\left|v{}_j\right|}$。 (4)

互信息:

I=H(U)-H(U|V)。 (5)

互信息的大小即是判定样本中哪个属性作为决策树根节点的依据,该运算中互信息大的属性就是这颗树的根结点。树的中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性。

2.2 ID3算法

决策树ID3主算法的主要步骤如下:

① 从训练集中随机选择一个含有正例集和反例集的子集(称为“窗口”);

② 用“建树算法”对当前窗口形成一棵决策树;

③ 对训练集(窗口除外)中例子用所得决策树进行类别判定,找出判错的例子;

④ 若存在判错的例子,把它们插入窗口,重复步骤②,否则结束。

主算法流程如图1所示。其中PE、NE分别表示正例集和反例集,它们共同组成训练集。PE1,PE2和NE1,NE2分别表示正例集和反例集的子集。

建树算法的具体步骤如下:

① 对当前例子集合,计算各特征的互信息;

② 选择互信息最大的特征AK;

③ 把在AK处取值相同的例子归为同一子集,AK取几个值就是几个子集;

④ 对既含正例又含反例的子集,递归调用建树算法;

⑤ 若子集仅含正例和反例的,对应分枝标上P或N,返回调用处。

测试中,预案的最终评价结果暂定为优、良、中、差4类,用它们代表上面所说的正例和反例的分类。

2.3 评估指标离散化处理

决策树是用在预案评价中,所以针对评价指标数据的特点(数据的连续性),需要实现连续数据的离散化处理,这里使用K-Means(K均值)聚类算法来实现。K-Means 算法接受输入量k;然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。

K-means算法的工作过程说明如下:首先从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下其他对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。K-Means算法流程如图2所示。

具体算法过程如下:

① 从N个数值中随机选取k个数据作为质心;

② 对剩余的每个数据测量其到每个质心的距离,并把它归到最近的质心的类;

③ 重新计算已经得到的各个类的质心(该类中所有对象的均值);

④ 迭代第②、第③步直至新的质心与原质心相等或小于指定阀值,算法结束。

对要进行连续数据离散化的属性(评估指标),首先从所选对象数据中随机的选取k(分类数)个对象作为初始聚类的中心,然后就依据算法流程开始计算分类,最终将连续数据对象成功的离散化为需要的k个类别。

3 应急预案评估的实现

以预案都涉及的共性的评估指标为例介绍决策树算法在应急预案评估中的应用并进行分析。

首先,进行评估指标的筛选。评估指标的数值分2种类型:枚举类型和数值类型。对于枚举类型要求类别不能太多,4～6个最为合适,取太多容易使生成的树过于胖,形成的规则过于“精确”,无法实现对新样本的合理分析;取太少,形成的规则又过于粗略,不能正确的分类,因此枚举类型的类别太多太少都不合适。而数值类型的属性,需要对这些数据做处理才能应用到决策树算法中,这里就选择聚类算法中的K-Means算法来实现对数据的分类,同样分类也要适中。

其次,获取样本数据。表1为地震评估指标的一些模拟样本数据,用于生成决策树。

每次突发事件最后都要进行总结,统计人员伤亡、经济损失和资源消耗等,并且针对本次突发事件进行评估,最终给出一个总的评估结果。这里的样本数据就是每次突发事件的评估指标项数据及最后的评估结果。由于全国各个地方的地质结构不一样,所以在获取这些样本的时候要按地区进行,这样有利于最终生成决策树并且用于对新样本的评估,这是因为地质结构较为接近的地区样本评估指标项也可以认为是一样的,并且这样的样本越多越有利于决策树的生成。

再次,生成决策树。每个项目的内容不一样,评估指标也不一样,因此对决策树的要求也就不一样。例如应急预案的评估,评估项中的大部分都是数值类型的,需要对这些数据离散化处理才能满足决策树分类的需要。这里采用的就是K-Means算法实现的。按照上述的建树流程构造决策树,程序通过循环方式,先计算各属性的熵,然后比较各属性熵的大小,选择值最大的属性进行分类,递归直到生成一颗完整的决策树。

某次演练的评估结果及建议如表2所示。

最后,实现对新样本的评估。新样本的数据结构必须与生成决策树的这些样本结构一致。表2是对一次演练数据的评估,并且针对预案要求,该算法能够实现给出一些评估指标参考取值。

4 结束语

在项目中的应用与测试结果表明:K-Means算法将连续数据型指标离散化处理分为2类。通过递归遍历生成的决策树,能够实现对当前数据进行分析,得到评估建议。该预案评估算法准确性很高,同时能够大大减少了专家评估中人为因素的影响,并且针对预案中出现的问题能够给出参考性的建议,使评估更加的客观,预案实施更加科学有效。

评估指标之间有很大的关联,并且关联程度不一样。单个指标的重要性在评估中不能很好地体现出来,因此需要对算法和评估指标做进一步的研究,使这种算法在应急预案评估中得到更好的应用。

参考文献

[1]NAKANISHIY.Assessing Emergency Preparedness of TransitAgencies:Afouctm on Performance Indicators[C].The 82ndAnnual Meeting of the Transportation Research Board,2003(4):24-32.

[2]刘功智,刘铁民.重大事故应急预案编制指南[J].劳动保护,2004,2(4):11-18.

[3]孙颖,池宏等.基于改进的多属性群决策方法的突发事件应急预案评估[J].中国管理科学,2005,13(10):153-156.

决策树算法及应用 篇5

决策树既可以用作分类模型, 也可以当成预测模型。决策树是一个类似树结构的表示方法, 每个中间节点表示一个属性的分裂, 分支表示一个划分的输出, 而叶节点表示分类的分布情况。决策树从根节点 (总数据集) 开始, 按照某种规则, 选择属性进行分裂, 再按照某种规则生成子节点;子节点再重复先前步骤, 直至达到某种停机准则, 从而一棵决策树便生长完毕。不同的决策树方法采用不同的树分裂方法和不同的树生成方法, 常用的决策树方法有:C4.5 (基于信息增益而产生的决策树) , CART (分类回归树) , CHAID (基于卡方检验而产生的决策树) 等。

CART (分类回归树) 又分为分类树和回归树, 其中回归树是一个有根的二叉树, 与其它决策树方法不同的是, 回归树的目标属性变量是连续型, 叶结点的属性平均值作为目标属性的预测值。回归树的构造思想是每次选择某种测试使对应的结点数据根据此测试分裂为两个子类, 分别放入左右子结点中, 而将生成的新结点加入到回归树后。

2 决策树的构造过程

决策树的构造通常包括两个步骤:利用训练数据集生成决策树;再对决策树进行剪枝f20]。另外还有一个过程, 是利用验证数据集对生成的模型进行检验, 以评估模型的优良与否。决策树从总数据集开始, 根据某种规则, 选取最优的输入属性变量, 再根据某种规则, 分裂成为'树枝', 它是一个从上到下的递归过程。决策树的剪枝是对树结构进行修剪, 删除多余分支的过程。使用决策树对数据集进行分类时, 从根结点开始对该数据集的属性进行测试, 根据测试的结果确定下一个结点, 直至到达叶结点为止, 叶结点标识的类别就是新样本的预测类别。

决策树的构造包括分裂变量的选择、树枝的生长和剪枝等几个步骤, 每个步骤都有不同的方法, 相应地就有各种不同的决策树方法。

在建立树模型之前, 需要完成工作:第一, 明确建模的终极目标, 这一步是要确定目标变量;第二, 数据清洗和输入变量的初步选取, 这一步是最重要的, 因为这将直接决定决策树的建模效率和效果;第三, 需要对目标变量执行正确的探索分析, 需要注意响应变量的分布形状, 如果响应变量的分布是偏倚的, 那么做出来的决策树一般上是不好的, 这时就需要按目标变量取值的一定比例, 重新组织数据集。

3 CHAID决策树算法

CHAID决策树的英文名称为Chi-squared Automatic Interaction Detection也就是说CHAID决策树与卡方检验有很大的关系。CHAID决策树的最大特点是:一, 可以产生多分支, 也就是说CHAID决策树是一个多叉树;二, 输入变量和目标变量即可以是定距, 也可以是定类的。在这一点上, CART决策树和C4.5决策树无法与之比拟, CART决策树的输入变量必须是连续型的, 而C4.5决策树的输入变量必须是离散的分类型的。所以, 在许多实际问题中, CART决策树和C4.5决策树是无法应用的。

于是, 为了处理连续型变量, 可以首先把连续型变量离散化, 再对它们运用决策树算法。二元决策树便是这类算法, 它的每个分支只代表对一个属性变量取值的真假的判断, 同时二元决策树会有效减少数据集的分解。人工手动地对连续性输入变量进行离散化, 这是不切实际的, 比如后面的实证分析中就有60多个连续型输入变量, 即使是逐个地完成对它们的离散化操作, 作出的决策树结果很可能会丢失很大的信息量。

CHAID决策树能够对输入变量作出预处理, 预处理的目标是对输入变量的取值进行分组。这个过程分两种情况进行:

(1) 对于定类的输入属性变量, 在它的多个分类中, 把那些对目标变量取值影响不显著的分类, 并合并它们。

(2) 对定距的连续型输入属性变量, 先按分位点分类, 然后再合并具有相同质性的组。这两种过程都应用到了统计检验方面的原理和方法:从统计显著性角度, 判定有哪些输入变量的分组取值, 对目标变量的分类预测影响不显著, 然后合并它们。

4 决策树的一个新想法

传统的决策树都有一些不足之处, 例如, CART决策树只是个二叉树, 建模结果很可能不准确, 并且输入变量只能是连续性的变量E;C4.5决策树的愉入变量只能是离散的分类型变量;CHAID决策树是对输入变量应用卡方检验或F检验进行分组或合并而生成的多叉树, 它在生长过程中, 只考虑到分裂变量与目标变量之间的联系, 而在这个步骤中没有考虑到其它变量, 可能会损失部分信息, 造成模型的部分偏差。

我们的一个新的想法是, 在构建决策树之前, 对数据集的输入变量做出初步的有针对性的选取, 剔除掉一些没有多少价值的输入变量。主要的过程是, 首先剔除以下这些变量:一, 对于某个输入变量, 它的记录取值几乎是不一样的;二, 对于某个输入变量, 它的记录取值几乎都是一样的。因为这两种输入变量几乎不提供多少有价值的信息, 所以首先需要剔除的。例如:对某个人群数据集进行分类预测, 其中一个输入变量是衣服穿着, 如果90%的人的穿着衣服是不一样的, 那么根据这个变量的分类预测的结果是每个人成为一类, 这是没有实际意义分类;或者是90%的人的穿着衣服是一样的, 那么根据这个变量的分类结果是这90%的人成为一类, 其它的10%的人再分成不同的小类, 显然这种分类结果是非常偏倚的, 也是没有实际意义的分类。所以首先需要剔除掉这样的输入变量。这个过程也可以作为后面讲述的神经网络模型的基础。

第二步骤是, 在整理好的数据集和剔除掉部分输入变量的基础上, 对数据集应用聚类分析。这个聚类分析的作用是, 初步性地探索连续型输入变量和取值较多的离散型输入变量被被分成多少个组, 为下一步的决策树的生长过程作准备。本文所采用的聚类分析的方法为动态聚类法:首先对样本进行初步分类, 然后根据某种分类原则, 对分类进行调整, 直到分类合理为止。

在聚类分析中选取马式距离是比较恰当的。动态聚类法的具体步骤为:首先将样本粗略分为几类, 然后按照某种原则聚合直到分裂满意为止。其步骤为:首先选取某些样本为凝聚点, 计算其它样本与各个凝聚点的距离, 距离近的样本归为一类;然后根据先前的分类, 重新计算各类的重心, 以及各样本与各重心的距离, 进行第二次分类;重复以上步骤。该过程的要点是新聚类的重心代替旧聚类的重心, 反复迭代, 直到不能减少各自重心的“离差和”, 为止。

第三步骤是, 在第二步聚类分析的基础之上, 对连续型输入变量和离散型输入变量取值进行分组或者合并。在第二步聚类分析之后, 连续型输入变量和离散型输入变量取值都会划分为不同的分组。

第四步骤是:这一步是选择决策树的分裂变量, 这个过程和C4.5的选择分裂变量的原理是相同的, 即根据信息增益最大原理来选择分裂变量。选择完毕分裂变量之后, 就是决策树的生长过程的讨论。

对于生长过程, 就是根据分裂变量的不同取值产生多少个分支, 如何分支, 以及怎样完成分支过程, 是决策树生长过程的核心内容。在第三步骤中, 输入变量己经被分组了, 这个过程可以看成是对输入变量的离散化处理。决策树生长过程是, 当分裂变量的分组比较少时, 若该属性仅含有有限的几个分组, 例如分裂属性变量Y只有两个分组A和B, 则子节点就直接划分为A子节点, B子节点。

当分裂的分组相对较多时, 需要对这些分组作出进一步的处理:

(1) 如果分组有很多个, 那么就要对该变量的分组作出合并处理。

(2) 如果合并结果不理想, 那么在合并同时还可以考虑取值的拆分, 根据检验结果判断是否需要把组再拆分成两组。

经过该步骤之后, 分裂变量取值的分组过程就得到了优化, 于是决策树完成生长过程。总的来说, 这种算法是对CHAID决策树算法的一种改进, 即是把聚类分析过程融合到决策树的分裂和生长过程。与CHAID决策树相比较, 在树的分裂过程中, 这种算法考虑了其它输入变量对目标变量的影响作用 (从聚类分析中体现出来) , 所以这种算法对信息的提取得到了较大的提升, 但是在执行决策树的过程中, 它的速度是比较慢的。

5 决策树数据解释和模型介绍

数据来源于某市4月份到6月份电信的部分移动用户信息, 共有一记录数120万条。

原始数据的基本组成:2009年4月份到2009年6月份的客户记录信息, 每月均记录条数为40万条, 总的数据集有120万条数据记录。原始属性变量包含有:用户的属性信息变量、行为特征信息变量、消费特征信息变量, 原始属性变量字段总共有102个, 当然这些属性变量之间有些是相互冗余。

取三个月份的数据是为了消除数据的波动, 体现出数据的一般性。波动的含义是:某个客户在第一个月份有消费一记录, 于是在数据库中就有他的一记录情况;而第二个月份该客户没有消费, 那么这个月中, 数据库中没有他的记录;但第三个月该客户又有消费, 于是数据库中有他的记录情况。

在数据的预处理中, 我们是根据月份了汇总每个客户的行为特征信息、消费行为信息。比如:客户甲三个月都有手机上网费用支出;而客户乙四月份和六月份有手机上网费用支出, 但他五月份没有手机上网费用支出。那么我们对甲的手机上网费用的汇总是按3个月计算的, 而对乙的手机上网费用的汇总是按2个月计算的。与此类似, 对客户的其它的消费行为信息变量、行为特征信息变量的统计汇总情况是相同的。那么经过初步的统计汇总之后, 中间数据集的记录条数有40万左右。

我们建模的想法和目标是, 根据这些历史数据, 分别用CHAID决策树模型和神经网络模型构建出预测分类模型, 这个模型是从这些电信移动用户数据集中寻找出电信移动上网用户的预测分类模型, 然后对它们进行评估, 选择出一个比较好的模型, 来指导市场发展战略的部署。

经过初步的ETL工作后产生的数据组成结构是:电信移动非上网用户记录数为16万条, 而电信移动上网用户数是1600条, 它们的比例为100∶1, 这个数据集在目标属性变量'移动上网'这一个维度上的分布是非常偏倚的。经过逐步查找原因, 发现这是由数据源的偏倚所造成的。说明一点:在做预测分类模型时, 首先要对数据源做数据的分布分析, 如果数据的分布是偏倚较大的, 那么该数据源是不好的, 它就不能很好的提供信息, 因此建议对该数据源做预处理, 以消除数据的偏倚分布。

建模的计算结果显示:CHAID决策树的分类预测准确率为89.47%, 神经网络的预测分类准确率为88.84%;并且它们预测一致的比率为93.9%, 也就是说, CHAID决策树的分类预测准确率略高于神经网络的分类预测准确率。从分类预测准确率这个角度分析, CHAID决策树的模型结果, 有高达89.47%是与实际情况一致的。另外, 神经网络模型和CHAID决策树模型有93.9%的预测结果是一致的。与决策树相比较, 神经网络的一个最大的缺点是它的解释性比较差, 无法像决策树那样产生最终的规则集。

参考文献

[1]何箭.决策树优化算法研究[J].合肥工业大学, 2006.

决策树算法及应用 篇6

决策树是被研究最多的数据挖掘方法之一,目前已有很多种形式的决策树分类算法。1986年,Quinlan在机器学习杂志上发文介绍了ID3算法。增益率的使用是多年前用于ID3的许多进展之一,尽管有实际的结果,但它牺牲了一些精度。C4.5算法是机器学习中一个有影响的、广泛使用的算法。在归纳学习中,代表着基于决策树的方法的里程碑。决策树学习算法的一个最大的优点就是它在学习过程中不需要使用者了解很多背景知识。这样只要训练事例能够用“属性-值”的方式表达出来,就能使用该算法来进行学习。且可以有效的处理缺省属性或是带有噪声的数据,进而高度自动化地建立起易于为用户所理解的模型。决策树方法已经在各个行业都有应用成果,其实用效果比较好,影响也较大[1,2]。

通过对决策树的深入研究,以及模糊理论和粗糙集理论知识的日益深入和完善,各种形式的决策树优化算法相继提出。模糊理论的加入,使得决策树的优化算法可以用于处理语言和测量的不确定性,能有效地解决经典数学难以解决的大系统的复杂性问题,以及在自然界和日常生活中普遍存在而无法解决的模糊性问题。粗糙集(Rough sets)理论是由波兰数学家Pawlak Z于1982年提出的一种研究不精确、不确定与不完全知识和数据的数学理论。属性重要性原理是其中比较重要的一个组成部分,最初是Z.Pawlak在考查知识约减时所提出来的,它被用于抽取等式关系最小独立部分,常用来对属性表进行简约,提取特征属性。在用于构建决策树的训练样本集,含有许多特征属性,这些属性用来尽可能的描述各个示例,每个示例也会因为属性值之间的差异呈现出不同的特征。每个属性值的变化都会有一定的规律,都能很好的反应分类效果,致使具有相同特征的属性值的示例可以被划分为同一类,但是并不是所有的属性对于分类都起关键作用,也就是说,每一个特征对于分类都有不同的重要程度[3,4]。

本文就是依据属性重要性原理,在生成决策树之前,求得每个属性对于分类的重要性,删掉不重要的属性,以对样本集进行属性约减,以减少属性间的冗余,提高决策树的分类效率。最后通过热轧工艺数据来对算法的有效性进行验证和说明。

1 热轧工艺数据预处理

数据预处理过程主要包括两方面的工作,即数据补齐和连续属性离散化[3]。对于数据补齐采用的策略是赋给它训练样例中该属性的最常见值;而对于连续属性离散化的处理,采用基于信息熵的离散化方法。这种方法是先按照对某一个连续属性对训练样例进行排序,然后确定目标分类不同的相邻实例,将不同分类的中间值产生一组候选阈值,产生最大信息增益的值必定在这组候选阈值中。最大的一个信息增益值只能将连续的属性分成两个离散的区间,为了能够离散化为多个区间,可以从这组候选阈值中多选择几个阈值。

整个热轧工艺数据分为四个数据表,通过对每个数据表的属性进行组合后形成表1所示的训练样本集。有460个样本,选择前400个样本作为训练样本,后60个样本作为测试样本。根据热轧过程中对于目标温度的影响情况可以分为3个状态,用0表示好,1表示欠佳,-1表示不好。表1中显示了在每个段钢号下的各属性值的大小及分类,其中HARDNESS为离散属性,RM_THICK,TEMP_FM,FM_WIDTH为连续属性。

2 决策树分类原理

决策树分类方法属于从特例推导到一般规则的归纳学习方法,其基本原理是使用决策树表示分类的规则,决策树由信息增益最大的字段(属性)作为根节点,各个取值为分支,各个分枝所划分的数据元组为子集,采用递归方法重复建树过程,扩展决策树,最后得到相同类别的子集,再以该类别作为叶节点,从而得到一棵完整的决策树。而在决策树生成过程中会出现树不平衡或过度拟合等现象,需对树再进行剪枝操作来简化树,使最后生成树为最优树,最后将对修剪前后的树进行评估[1,2,5]。

基于信息论的决策树分类学习算法,是通过计算数据集合对于决策属性的信息量的大小对信息进行分类和归纳,适合于实时分析和处理数据量大的样本,且具有分类精度高、对噪声数据有很好的健壮性等优点,决策树还是推理规则的一种图形表示,在生成决策树的基础之上产生推理规则。

图1为决策树分类算法过程处理的主要流程。

决策树方法与神经网络或贝叶斯分类等分类模型相比,其分类原理简单易懂,很容易被使用人员理解和接受。在决策树分类过程中,一般不需要人为设定参数,更适合于知识发现的要求,且算法建立速度快,计算量相对来说不是很大、可以处理连续值和离散值属性的优点。但热轧数据具有一定的连续性和时序性特征,对于这类数据,决策树算法就需要更多的预处理工作;热轧数据中属性的个数也是相当的多,这样可能错误会增加的比较快。要分析和尽可能减少这种情况,就需要选择合适的方法来对属性进行约减。

3 基于属性重要性的决策树优化

在决策树学习之前,训练样例集都是由“属性-值”对表示,且每一个属性都是由有限的离散值组成。离散化方法选择的不同,会有不同的离散结果。对于热轧工艺数据来说,相邻样本之间的差异比较小,在进行离散化处理后,可能由于离散化区间个数比较少,而使相邻的不同样本离散化成为相同的样本。这样样本集之间或者说属性之间就存在冗余现象。本文提出的方法就是对离散化后的样本进行处理,然后根据属性重要性大小对属性进行筛选,删掉对分类没有太大影响的属性,最后再使用决策树分类算法来形成规则。

3.1 基于信息熵的属性重要性原理基本概念

设S=(U,A,V,F)为一个信息系统,其中,U={x1,x2,…,xn}是论域;A是属性集合;V是属性取值集合;F是U×A→V的映射。若A=C∪D,C∩D=ϕ,C称为条件属性集,D称为决策属性集,则该信息系统称为决策表。

在信息系统S=(U,A,V,F)中,运用概率和熵的概念,

对于属性X的概率有:$p{}_U(X)=\frac{\text{c}\text{a}\text{r}\text{d}(X)}{\text{c}\text{a}\text{r}\text{d}(Y)}$;

属性Y相对于X的条件概率为:$p{}_U(Y|X)=\frac{\text{c}\text{a}\text{r}\text{d}(Y{\displaystyle \cap X})}{\text{c}\text{a}\text{r}\text{d}(X)}$,

其中,card()表示集合的基数。

因此,可以定义条件属性C的信息熵为:${\rm H}(C)=-{\displaystyle \sum _{i=1}^n}p(X{}_i)\ln p(X{}_i)$,其中U/C={X1,X2,…,Xn};

定义决策属性D相对于条件属性C的信息熵为:

${\rm H}(D|C)=-{\displaystyle \sum _{i=1}^{n}p}(X{}_i){\displaystyle \sum _{j=1}^{m}p}(Y{}_j|X{}_i)\ln p(Y{}_j|X{}_i)$,其中,U/D={Y1,Y2,…,Yn};

对于任意的c∈C,可定义属性重要性:sgf(c,C,D)=H(D|C)-H(D|C-{c})。

3.2 算法优化过程

对于表1中的热轧工艺数据,首先是需要对数据进行初始化处理,将缺省数据进行填补,以保证数据的完整性。再运用下述算法来进行分类处理。

输入:初始样本集。

输出:决策树分类结果输出以及分类准确率。

Step1:运用基于信息熵的离散化方法对连续属性离散化。

Step2:扫描整个样本集,将相同的样本进行处理。

Step3:分别求得每个属性的重要性大小,选择对分类有影响的若干属性,并作为新的决策树处理样本集。

Step4:使用决策树C4.5算法来对样本集进行分类,将决策树的每个节点信息输出,并评估分类的准确率。

3.3 结果分析

整个热轧工艺属性大约有198个,示例样本集的个数为461条。我们通过算法设计后,选择其中对属性非常重要的前48个,分别进行决策树分类后的结果如表2所示。

通过对结果的分析可得,在没有对原始数据表进行处理之前,通过剪枝操作,删掉的冗余部分比较多;而通过优化算法后,其删掉的冗余部分相对比较少,且提高了其评估率,在一定程度上提高了分类正确率。对最后生成的决策树每层节点的分析,以及结合温度预报精度要求并结合精轧工艺特点等,可以看出RM_THICK(粗轧厚度)和RM_TEMP(粗轧温度)这两个决策属性的属性重要性比较大的,确实是对终轧温度影响最大,这与精轧工艺机理是非常一致的。

4 结束语

本文主要是提出一种在决策树分类之前,对样本集进行去冗余,筛选掉对分类结果影响不大的属性,以缩小样本集条件属性的个数,从而提高决策树分类效率。试验结果表明,这种改进的方法在处理热轧工艺数据上,能够有效的提高分类效率。

摘要：决策树分类方法是一种非常有效的机器学习方法,具有分类精度高、对噪声数据有很好的健壮性以及形成树状模式等优点,对决策树算法的优化也主要是从分支属性的选择标准,对决策树的修剪,以及引入模糊理论、粗糙集理论、遗传算法和神经网络算法等几个方面进行优化。引入粗糙集理论中的属性重要性原理来对决策树进行优化,首先计算出每个条件属性对分类的重要度,然后根据重要度大小来对样本集进行一个筛选,在不损害分类准确率的同时减小决策树的规模。整个算法在Visual C++6.0环境下编程实现,并应用于热轧工艺模型中,通过对热轧数据的处理,验证了算法的有效性。

关键词：决策树分类,粗糙集,属性重要性,热轧工艺模型

参考文献

[1]Tom Mitchell.机器学习[M].曾华军,张银奎,等译.北京:机械工业出版社,2003.

[2]Quinlan J R.Induction of decision trees[J].Machine Learning,1986.

[3]王国胤.Rough集理论与知识获取[M].西安:西安交通大学出版社,2001:1-226.

[4]John Y Ching,Andrew K C Wong.Class-Dependent Discretizationfor Inductive Learning from Continuous and Mixed-Mode Data[J].IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINEINThLLIGENCE,VOL.17,NO.7,JULY 199.

决策树算法及应用 篇7

决策树是一种用于分类、聚类和预测的预测型建模方法,采用“分而治之”的方法将问题搜索空间分为若干子集,即采用自顶向下的递归方式从无次序、无规则的样本数据集中推理出决策树表示形式, 在内部节点进行属性值比较并根据不同的属性值判断从该节点向下的分支,在决策树的叶节点得到结论。决策树作为数据挖掘中的核心技术之一,已在很多领域中得到广泛的应用[1]。

目前气象部门对于农业气象灾情只是简单的分为:一般性气象灾害、重大气象灾害和特大气象灾害。倘若在对灾害分类的同时对灾情用数据挖掘中的决策树算法进行分类统计可以发现灾情与经济损失、人口受灾、农作物受灾都有着紧密的联系,其中有规可循。农业气象灾害数据库中积累了大量的数据,这些数据的背后隐藏着许多重要的模式和知识。面对海量数据,传统的查询或分析工具无法有效地识别出其中有价值的信息,从而形成了“数据丰富而知识贫乏”的现象。基于决策树的分类挖掘技术可以很好地解决这一问题。为此,提出了一种有效的决策树分类挖掘系统,能较直观地反映所描述问题的本质特征,提出最佳分类属性,从而优化农业气象灾害统计。

1 决策树分类挖掘系统

1.1 农业气象灾害数据分类思想

一般农业气象灾害统计主要是对农业气象灾害造成的损失进行合计。直接经济损失的评估指标一般可分为无经济损失、较大经济损失、很大经济损失。据此可将直接经济损失分为A,B,C 3个等级。通过分类挖掘思想,把农业气象灾害数据库中的数据进行分类挖掘和分析,找出经济损失严重的地区和发生的时段,可以采取积极措施将危害减至最低程度。

1.2 ID3算法

ID3是基于信息熵的决策树分类算法,该算法是根据属性集的取值选择实例的类别,其核心是在决策树中各级结点上选择属性。同时,用信息增益作为属性选择的标准,使得在每个非叶子结点测试时,能获得关于被测试例子最大的类别信息。使用该属性将训练样本集分成子集后,系统的熵值最小,期望该非叶结点到各个后代叶结点的平均路径最短, 使生成的决策树的平均深度较小,从而提高了分类的速度和准确率[5]。

ID3算法的目标是通过一系列的划分,将训练集迭代地划分为多个子集,使得每个子集中的对象尽量属于同一个类。算法的核心是构建决策树的过程。其中,树的非终端节点对应着单个属性的测试,终端节点即叶节点对应的是数据集最终被分类后所得的子集。该算法的效率就体现在对测试属性的选择上。

给定概率p1,p2,…,ps,其中∑pi=1,那么熵的定义为

H(p1,p2,…,ps)=∑[pilog(1/pi)] (1)

信息增益为

Gain(D,S)=H(D)-∑P(Di)H(Di) (2)

其中,D为样本集合,增益是指在分类进行正确分类所需要的信息与分类后进行正确分类所需要的信息的差。

1.3 C4.5算法

C4.5算法是ID3算法的后继。ID3算法采用信息增益作为分裂属性的度量标准,选择分裂属性时倾向具有较多不同值的属性,因而可能导致决策树过分拟合。在极端情况下,如果某个属性对于训练集中的每个元组都有唯一的一个数值,ID3算法则认为该属性是最好的分裂属性,因为根据该属性划分之后的每个子集都只有一个样本,因此每个子集里面只有一个类别。C4.5采用增益比率代替信息增益,样本集合D,属性A的增益比率GainRatio被定义为

GainRatio(A)=Gain(A)/Splitlnfo(A) (3)

其中,Gain(A)为属性A的信息增益,Sp1itInfo(A)为属性A的分裂信息,如果属性A由v个不同的取值,把D分为v个子集,Dj为样本在属性A上取值为Aj的子集,|Dj|为子集Dj中的样本个数。属性A的分裂信息定义为

由此可见,通过增益比率克服了信息增益偏袒取值较多的属性的缺陷。

2 决策树算法在农业气象灾害统计中的应用

2.1 训练样本数据的处理

为了验证ID3算法和C4.5算法在农业气象灾害统计中的应用,以下给出一个训练样本,其中记录了2006年6-8月江苏省部分城市暴雨洪涝数据。训练样本如表1所示。

对于训练样本,属于A类的样本有13个,属于B类的样本有10个,属于C类的样本有3个。所以分区前的熵是

根据设定的3个样本可以对它们分别进行分区,划分后的样本如表2所示。

计算相应的熵值如下

同理得

相应的信息增益是

对于训练样本采用C4.5的增益比率,则计算结果如下

同理得

Splitlnfo2=1.502 9(比特)

GainRatio2=0.399 6

Splitlnfo3=1.727 9(比特)

GainRatio3=0.275 9

2.2 规则剪枝

规则剪枝是数据挖掘领域的通用技术,其主要目标是去除无关元素,这样可以避免训练数据的溢出,另外也能简化规则,因为较为简洁的规则更易于用户理解。其基本思想是:依次除去规则中的元素,并重新评估新规则,如果新规则的有效性比旧规则高,则进行规则更新,并给新规则赋予一个新的类标号节点,但是修剪规则到什么程度将决定规则的长短和分类能力。如果允许剪枝到所有属性或者只剩下一个属性,那么规则的分类能力会提高,但这种过于简洁的规则并不珍贵,因为通过一般的统计方法就可以得出。因此,在本实验中设计了多种修剪标准,一种是剪到只剩下一个属性为止;另一种剪枝则是根据规则的长短来确定修剪程度,可以选择修剪1/3或者1/2,在实验中根据情况选定参数,这样可以得到比较满意的结果。

2.3 生成决策树

比较训练样本数据处理中的信息增益和信息增益比率可见,属性2具有最高值,属性3次之,属性1最小。无论是用ID3算法还是C4.5算法,均得出此结论,所以可由属性2对决策树的结构进行首次划分,随后再用属性3和属性1进行层层划分,再进行规则剪枝,最终生成一棵决策树如图1所示。

2.4 算法描述

下面是关于实验中决策树算法的描述:

Procedure BuildTree(S)

用训练样本集S初始化根节点R

用根节点R初始化队列Q

While Q is not Empty do {

取出队列Q中的第一个节点N

if N 不纯(Pure){

for 每一个属性A

估计该节点在A上的信息增益

选出最佳的属性,将N分裂为N1,N2

} }构建决策树的程序代码为:

Function induce-tree(example-set,properties)

Beign

If all properties in example-set are in the same class

Then return a leaf node labeled with that class

Else if properties is empty

Then return leaf node labeled with disjunction of all classes in example-set

Else beign

Select a property p and make it the root of the current tree

Delete p from properties

For each value v of p

Beign

Create a branch of the tree labeled with v

Let partition be elements of example-set with values v for property p

Call induce-tree(partition,properties) attach result to branch v

End

End

End

剪枝后计算最小子树代价的伪代码如下:

Procedure ComputerCost&Prune(Node N)

If N是仍待扩展的节点

return N节点的代价下界

If N是纯节点或不可扩展的叶节点

return (C(S)+1)

两个子节点N1,N2

minCost1=Compute & Prune (Node N1)

minCost2= Compute & Prune (Node N2)

minCostN=min{C(S)+1,Csplit(N)+1+

minCost1+minCost2}

if minCostN=C(S)+1 Prune Childnodes N1 and N2

return minCostN

其中,C(S)=∑Ni * log(Ni/N)+[(K-1)/2]log(N/2)+log[∏(K/2)/Γ(K/2)] (5)

式中 N—记录数;

K—类数目;

Ni—属于类i的记录数;

minCost—最小子树代价。

3 结论

基于决策树的分类挖掘系统的有效性和准确性与农业气象灾害数据库中的数据量密切相关。实验证明,通过计算得到的判断树能够较直观地反映所描述问题的本质特征,但要指出的是,基于决策树的分类挖掘系统只能作为灾害统计的决策依据,还要结合样本的数据数量、质量和分布才能达到较为准确的效果。而后者来自于各地气象局上报的数据,并从中提取有用信息,这也是笔者下一步要研究的问题。

评估系统以VB作为开发平台,SQL Server作为后台数据库,在对江苏省近几年的农业气象灾害分类评估中达到了理想的效果。为了验证系统评估效果的可靠性和认可度,笔者随机抽取了2004年和2006年的数据进行评估。针对给出的分类评估结果,通过气象部门专业工作人员的认可度调查结果报告,从反馈情况来看,该评估可以达到90%以上的灾害分类评估正确率。

4 展望

不同的大气现象给我们留下了不同的感受,特别是那些令人生畏的大气现象所带来的形形色色的灾难,给我们留下了极为深刻的影响:“麦莎”台风、“卡特里娜”台风, 1998年长江流域特大洪水、2006年川渝地区的特大干旱,带给世界的都是极大的震撼。将决策树算法应用于农业气象灾害统计相信可以更为便捷地分析统计出各地损失程度以分清轻重缓急,采取积极有效的抢救措施,也可以针对各地不同情况做好来年的防范工作,由此可见将决策树算法应用于农业气象灾害统计可以显著提高灾害分类统计效率。

摘要：分析了决策树分类算法中的ID3算法和C4.5算法,在论述分类挖掘的基础上分析了决策树分类挖掘系统的建立思想、步骤及算法,并把这两种算法应用到优化农业气象灾害统计的实验中,研究了决策树算法在气象灾害导致的直接经济损失评估中的应用,实验结果证明了该方法的可行性。

关键词：农业气象,决策树,ID3算法,C4.5算法,分类挖掘

参考文献

[1]Herb Edelstein.浅说数据挖掘[J].计算机系统应用,1998(4):56-57.

[2]刘红岩,陆宏钧,陈剑.利用数据库技术实现的可扩展的分类算法[J].软件学报,2002,13(6):1075-1081

[3]谢榕.数据挖掘与决策支持系统[J].计算机系统应用,1999(8):9-11.

[4]陈文伟,黄金才.数据仓库与数据挖掘(1版)[M]北京:人民邮电出版社,2004.

决策树算法及应用 篇8

Forrest[2] 把人工免疫系统(Artificial Immune System,AIS)运用到入侵检测系统(Intrusion Detection Systems,IDSs)中提出了著名的否定选择算法(Negative Selection Algorithm,NSA)并利用r领域匹配函数(R-contiguous Matching Function, RCMF)来判定模式间的匹配程度。但是,Kim通过实验证明,只有在被检测对象是网络通信数据的一个小子集时NSA才是有效的。NSA的随机搜索特性导致其仅仅只能应用于有限网认为RCMF作为一种连续位匹配函数,在对具有多个分离特征区间的网络通信数据进行匹配程度判定时,其作用不明显。络入侵的识别。同时,Kim[3]Kim和Bentley[4,5]又年提出了动态克隆选择算法(DynamiCS),主要用于网络入侵检测。

针对传统的NSA算法中生成大量无效抗体,并且抗体之间缺乏多样性,不能保证识别器在一定数量内尽可能覆盖最大的nonself空间的问题,提出了基于决策树及遗传算法的人工免疫入侵检测算法。利用决策树对噪声数据有很好的健壮性,对随机生成的候选免疫细胞进行分类,并选取亲和力低的免疫细胞进行变异,再经过否定选择淘汰部分免疫细胞,最后淘汰种群中高浓度的免疫细胞,生成成熟的免疫细胞。

1 理论基础

1.1 基因型表示网络数据

国际上,K.De.Jong等人在1993年概念学习中提出的基因表达方法。国内吴泽俊,钱立进,梁意文等人提出了新的基因型和表现型的表达方式[6]。采用基因型表示网络数据。首先每个网络数据都是由多个属性组成,每个属性都有多个不同的属性值。每个属性就是一个基因,每个属性的不同属性值就是特征簇(Phototypes)。例如:协议类型,目的地址,发送数据等。不同的基因的特征簇也不相同,用“1”“0”的代码表示特征簇。例如协议类型有TCP、UDP和ICMP就可以用0001表示TCP,用0010表示UDP,用0100表示ICMP。每个基因都包含了若干个特征的特征区间,为1表示包含这个特征值,为0表示不包含。如果特征区间的第一位为1,则表示这个区间以后的值无效,该特征区间包含了任意值。一条网络数据就可以用多个基因来表示,如果网络数据有连续值,则将连续值离散化。因此随机生成的识别器以及self和nonself都可以用基因型来表示,有利于计算抗体和抗原之间的亲和力以及浓度计算。

2.2 决策树

决策树是一种逼近离散值目标函数的方法,这种方法中学习到的函数被表示为一棵决策树[7]。每种决策树都有自己不同的选择属性的标准。Id3用信息增益,C4.5用信息增益率。按属性选择标准选出当前属性,并按当前属性的n个属性值,把集合分裂成n个不同的子集。若分裂的子集中所有记录的目标属性值一致,则生成叶子节点停止分裂。否则继续选择属性再分裂直到选择的目标属性的属性值一致。决策树的分类实际是对训练样子的预测分类结果。

一棵完全决策树能非常准确地反映训练集中数据的特征,但是由于完全决策树对训练样本的特征描述得“过于精确”,有时候反而因失去了一般代表性而无法实现对新样本的合理分析,所以完全决策树不一定是一棵能对新数据进行合理预测的最佳决策树。这种现象一般称为“过度拟合(overfitting)” [7]。解决过度拟合的主要方法是对决策树进行剪枝,即剪去影响预测精度的分枝[9]。悲观错误剪枝(Pessimistic Error Pruning, PEP) 常用于Id3算法, 基于错误的剪枝(Error Based Pruning, EBP)常用于C4.5算法。

目前生成决策树方法的算法主要有3种:CART算法、CHAID算法、C4.5算法[8]。其中C4.5算法是发展的比较完善也是比较简单易懂的一种决策树算法,因此以C4.5算法为基础对决策树进行讨论。C4.5算法自顶向下选择不同的属性,对属性的每一个值产生一个分支,分支属性值的相应样本子集被移到新生成的子节点上,这个算法递归地应用于每个子节点上,直到节点的所有样本都分区到某个类中,到达决策树的叶节点的每条路径表示一个分类规则。C4.5算法的属性选择的基础是基于使生成的决策树中节点所含的信息熵最小。

Info(S)=undefined

式中:freq(Ci,S) 代表集合S中属于类Ci (k个可能类中的一个)的样本数量。 |S|表示集合中的样本数量。上面的公式仅仅给出了一个子集的熵的计算,如果按照某个属性进行分区后就涉及到若干个子集,需要对这些子集进行熵的加权和的计算,公式如下所示:

Infox(T)=-∑((|Ti|/|T|)×Info(Ti))

其中:T-按照属性x进行分区的集合。为了更加明显的比较不同集合的熵的大小,计算分区前的集合的熵和分区后的熵的差(我们把这个差叫做增益),增益大的就是我们要选取的节点。公式如下:

Gain(X)= Info(T)- Infox(T)

2 算法设计

2.1 算法的模型

假设一个抗体的指令集合包含N个分子(N个抗体),而每个分子又存在K个基因,每个基因都由长度不等的n位组成,其中每个分子都是从长度为L的“1”和“0”数字构成的属性串。

算法的步骤如下:

①随机生成长度为L的候选抗体(识别器)R。

②将self集和nonself集用遗传算法表示并生成决策树,决策树的目标属性为no和yes,满足self集的抗体的目标属性为yes,满足nonself集的目标属性为no。利用生成的决策树将候选抗体R进行分类,将分类得到目标属性为yes的抗体淘汰,并跳转到第①步,如果分类得到目标属性为no的抗体就继续到第③步。

③ 计算候选抗体适应度fitness,这里提出了fitness函数的计算公式

定义1 候选抗体与单位抗体的匹配度P

P=undefined (1)

其中,L为抗体的长度,i是抗体的第i位。P的取值范围Pϵ[0,1]。

定义2候选抗体与抗体集合的平均匹配度AP

AP=undefined (2)

其中Pj用公式1中的Pj代替,N位抗体集合的个数,j是抗体集合的第j位。

定义3候选抗体适应度fitness的公式如下:

fitness(R)=Ap (3)

④ 计算当前抗体集合的平均适应度,如果fitness小于平均适应度则当前候选抗体被淘汰并且转到第①步,否则就继续进行。平均适应度的计算公式如下:

afitness=undefined (4)

其中 N位抗体集合的个数,fitness(Pj)是第j个抗体的适应度。

⑤ 通过对抗前抗体进行杂交和变异:在当前抗体中的k个基因中的30%个基因进行变异,并生成一定数量的种群。

⑥ 生成的种群经过否定选择算法淘汰部分种群

⑦ 计算种群中抗体的浓度

依据Mori的算法给出计算抗体浓度的以下公式:

计算抗体中位置为j的信息熵的函数Hj(N)为

Hi(N)=-undefined (5)

其中,k为某个基因的长度,pi,j表示基因位j是字符串i的概率。所以一个抗体的平均信息熵就为

H(N)=undefined (6)

计算抗体v和ω间的亲和度

ayundefined (7)

其中,H(2)根据公式4计算。

计算每个抗体的浓度cv,如果cv大于一个给定的阀值δ1,则这个个体就会被抑制(从计算机中删除),否则他将成为记忆抗体。

⑧ 计算种群单位个体的浓度是否低于识别器集合的平均浓度,如果高于平均浓度则淘汰,否则就替换识别器集合中高浓度的抗体。

⑨ 当抗体集合的平均浓度低于一定的阈值的时候停止生成识别器,否则跳转到第①步。

2.2 算法的流程图

2.3 算法的伪代码

Procedure基于决策树及遗传算法的人工免疫入侵检测算法

利用公式3计算识别器总适应度;

While 识别器的适应度低于抗体集合的平均适应度

将识别器进行遗传变异产生识别器种群;利用公式8计算种群浓度;用低浓度种群替换识别器高浓度种群中

End

End

3 算法分析

决策树是一种逼近离散值函数的方法,对噪声数据有很好的健壮性。由于在计算机免疫学中目前还存在着"不完全self集问题"导致存在着大量nonself集的缩放,造成了在self集和nonself集中存在着一定数量的噪声数据,由self集和nonself集组成的训练样本集生成决策树再通过剪枝能够很好的对随机生成的候选识别器进行分类,并且得到较高的测试数据的精度,这样就减少了后续不必要的计算,提高了整个算法的效率。

随机生成的候选识别器通过与抗体集也就是self集的每个基因的每一位的匹配计算,统计最后的匹配结果生成适应度fitness函数。由于人为的制定self集空间总是有限,根据适应的函数,候选识别器与self集中每个抗体的差异程度来评判候选识别器,差异程度越大的候选识别器,越有利于覆盖更广的nonself集空间,提高了识别器集合的的多样性,降低了错误否定率,有利于提高识别器集合的检测效率。

在算法中,采用两种遗传算子进行繁殖即杂交和变异。杂交变异包括三种:第一种一个候选识别器中的某个基因中的两个基因值互相交换位置。第二种一个候选识别器中两个具有相同位数的基因进行交换。第三种候选识别器和self集中的某个抗体的相同的基因位进行交换。变异包括:第一种将某一基因的某一基因位取反。第二种将基因集体左移或右移。第三种对某基因全部取“1”表示这个基因可以取任意值。增加遗传算子的种类,就有利于繁殖后代的多样性,提高了识别器的识别能力。

由候选识别器通过遗传算子繁殖的候选识别器种群,可能产生大量错误的抗体或者无效的看体,有的抗体可能本身就是self集中的元素。这些错误的抗体可能造成错误肯定率,直接影响到识别器的识别效率。因此引入否定选择算法再次将错误的无效的候选识别器淘汰掉。减少错误肯定率,提高识别器的效率。

最后通过计算候选识别器种群的浓度,淘汰识别器集合中浓度较高的识别器。由于较高的浓度的识别器,降低了识别器集合的多样性,缩小了识别器集合对nonself空间覆盖程度。因此对较高浓度的抗体进行抑制。

4 结束语

基于Forrest将AIS应用到IDSs中的研究,提出了一种基于决策树及遗传算法的人工免疫入侵检测算发该算法与传统的克隆选择算法做了的改进:①利用决策树学习对噪声数据有很好的健壮性,提出了一种新的用于计算抗原和抗体之间的亲和力的方法。②提出了一种新的遗传算法中的适应度函数fitness的计算公式。③将否定选择算法与遗传算法相结合,并利用识别器之间的浓度高低,引入淘汰机制,使识别器具有动态性。

摘要：针对传统的否定选择算法中生成大量无效抗体,并且抗体之间缺乏多样性的问题,设计了基于决策树及遗传算法的人工免疫入侵检测算法。将决策树和遗传算法引入传统的否定选择算法中,利用决策树计算抗原和抗体之间的亲和力,提出了新fitness的计算公式,并利用抗体浓度衡量抗体集的多样性,将低浓度抗体代替高浓度抗体,实现了抗体的多样性,确保了当抗体集的数量一定时尽可能覆盖最大的非自体集空间,以提高抗体集的性能。

关键词：人工免疫,入侵检测,决策树,遗传算法,否定选择算法

参考文献

[1]李涛·计算机免疫学·北京:电子工业出版社,2004.

[2]Forrest S,Perleson A,Allen L,et al·Self-Nonself discrimination in a computer·Oakland,USA:Proceedings of IEEE Symposium on Research in Security and Privacy,2002·202～212

[3]Kim J,Bentley P·An Evaluation of Negative Selection in an Artificial Immune System for Network Intrusion Detection·In Genetic and Evolutionary Computation Conference2001(GECCO-2001),San Francisco USA,CA,2001,1330～1337

[4]J Kim,P J Bentley·Towards an Artificial Immune System for Network Intrusion Detection:An investigation of Dynamic Clonal Se-lection with negative Selection Operator·In:Proceedings of the Congress on Evolutionary Computation,(CEC-2002),Honolulu USA,2002-05-12-17:1015～1020

[5]J Kim,P J Bentley·AModel of Gene Library Evolution in the Dynamic Clonal Selection Algorithm·Proceedings of the First Interna-tional Conference on Artificial Immune Systems(ICARIS),Canterbury UK,2002-09-9-11:57～65

[6]吴泽俊,钱立进,梁意文·入侵检测系统中基于免疫的克隆选择算法·计算机工程,2004,30(6):50～52

[7]Tom M·Mitchell·机器学习·北京:机械工业出版社,2006·38～60