决策树算法及应用.doc

决策树算法及应用决策树算法及应用数一决策树算法简介168决策树算法是一种归纳分类算法,它通过对训练集的学习，挖掘出有用的规则，用于对新集进行预测.决策树算法可设计成具有良好可伸缩性的算法,能够很好地与超大型数据库结合,处理相关的多种数据类型，并且,其运算结果容易被人理解,其分类模式容易转化成分类规则。因此，在过去的几十年中，决策树算法在机器学习（machine learning）和数据挖掘( data mining） 领域一直受到广泛地重视. 决策树算法以树状结构表示数据分类的结果。树的非叶结点表示对数据属性（at tribute） 的测试.每个分枝代表一个测试输出,而每个叶结点代表一个分类。由根结点到各个叶结点的路径描述可得到各种分类规则。目前有多种形式的决策树算法。其中最值得注意的是CART 和ID3/ C4. 5 。许多其它的算法都是由它们演变而来。下面介绍决策树算法ID3 （Quinlan ,1979) 在实际中的一例应用.决策树算法ID3 使用信息增益( Information Gain）作为选择属性对节点进行划分的指标。信息增益表示系统由于分类获得的信息量,该量由系统熵的减少值定量描述。熵（Entropy) 是一个反映信息量大小的概念。最终信息增益最高的划分将被作为分裂方案。决策树和决策规则是实际应用中分类问题的数据挖掘方法。决策树表示法是应用最广泛的逻辑方法，它通过一组输入-输出样本构建决策树的有指导的学习方法。对于分类决策树来说，需要先对原始资料来进行分类训练，经由不断的属性分类后，得到预期的分类结果.判定树归纳的基本算法是贪心算法，它采用自上而下、分而治之的递归方式来构造一个决策树。ID3 算法是一种著名的判定树归纳算法，伪代码如下：Function Generate_decision_tree（训练样本samples，候选属性attributelist）创建节点N:if samples 都在同一个类C then返回N 作为叶节点，以类C 标记；if attribute_list 为空then返回N 为叶节点，标记为samples 中最普通类： /多数表决定选择attribute_list 中有最高信息增益的属性test_attribute：标记节点N 为test_attribute；for each test_attribute 中的已知位ai /划分samples由节点N 长出一个条件为test_attribute=ai 的分枝；设Si 是samples 中test attribute=ai 样本的集合； /一个划分If Si 为空then加上一个树叶，标记为samples 中最普通的类；Else 加上一个由Generate_desdecision_tree（Si，attribute_list_test_attribute）返回的节点：在树的每个节点上使用具有最高信息增益的属性作为当前节点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并确保找到一棵简单的树。二 数据挖掘技术的基本概念710 数据挖掘是从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则。它所挖掘出的规则蕴涵了数据库中一组对象之间的特定关系,揭示出了许多有用的信息，为经营决策、市场策划、金融预测等提供依据。通过数据挖掘,有价值的知识、规则或高层次的信息能从数据库的相关数据集合中抽取出来,并从不同的角度显示，从而使大型数据库成为一个丰富可靠的资源,为知识归纳服务。数据挖掘发现的知识通常是以概念（Concepts）、规则(Rules）、规律（Regularities）、模式（Patterns）、约束（Constraints）、可视化（Visualizations）等形式表现。这些知识可以直接提供给决策者，用以辅助决策过程，或者提供给领域专家，修正专家已有的知识体系，也可以作为新知识转存到相应系统的知识存储机构中，比如专家系统（Expert System）、规则库等（Rule Base）.数据挖掘应用领域的不断扩展，为数据挖掘的发展带来了蓬勃的生机。三 决策树在许多领域的应用基于决策树C4.5算法的我国商业银行信用风险评估模型实证分析251。实证分析的样本来源本文从某银行的信息系统中随机抽取了某行业( 2004 年) 100 个贷款企业的资料作为建模样本,其中有81 个企业的财务数据资料完整， 可以作为分析研究的对象。在这81 个企业中有64 个企业贷款履约, 17 个企业贷款违约, 不良贷款率为20。1, 与该行业的整体贷款不良率非常接近, 因此, 随机抽取的81 个企业财务资料具有代表性, 可以用此样本对总体进行统计推断.2.指标体系的建立适当地选择财务指标建立反映企业信用风险的指标体系， 是信用风险评估的基础。依据全面性、有效性和可操作性的原则, 选择了5 个方面的9 项指标构建了信用风险评估指标体系。( 1） 负债水平资产负债率X1。适度的资产负债率表明企业投资人、债权人的投资风险较小， 企业经营安全稳健, 具有较强的筹资能力。（ 2） 流动能力和偿债能力流动比率X2、总债务/ebitdaX3.流动比率越高, 表明企业流动资产周转越快, 偿还流动负债能力越强。但需要说明的是， 该指标过高， 表明企业的资金利用效率比较低下, 对企业经营发展不利。总债务/ebitda 是指总债务相对于当年的息、税、折摊前收益的大小。总债务与ebitda的比率反映以企业所创造的税前利润和留在企业内部的固定资产折旧费用、摊销费用在支付利息前对总债务的保障能力。该指标越小, 企业还债能力越强， 反之, 企业还债的能力就比较弱.（ 3） 赢利能力净资产收益率X4、销售（ 营业)利润率X5。企业获利能力是企业信用的基础, 企业只有盈利, 才有可能按时偿还债务.（ 4） 经营效益和资金利用效率总资产周转率X6、流动资产周转率X7。企业的资产管理状况对于企业的信用风险水平有直接的影响。( 5） 发展能力销售（ 营业） 增长率X8、资本积累率X9。销售( 营业) 增长率越大， 表明销售( 营业)收入增长速度越快, 企业发展形势较好， 企业的信用风险较小。资本积累率展示了企业的发展潜力。该指标值越高, 说明企业的资本积累越多， 投资者投入企业资本的保全性和增长性越强, 企业应付风险的能力越强， 企业的信用风险相对较小。决策树预测评价模型的构建3411将决策树预测应用于农村信用合作社农户贷款信用评价问题中，基本思路是：根据已知的样本与原始信用评价状态，运用决策树发现贷款人信用状态与其某些特征属性之间的关系,使得能够通过对农户这些属性的具体观察值,对贷款人的信用情况进行预测。信息增益的计算及属性评估分值的获得在树的每个节点上使用信息增益度量选择测试属性，这种度量称为属性选择度量或分裂的优良性度量。选择具有最高信息增益的属性作为当前节点的测试属性.该属性是给定集合中具有最高区分度的属性。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小，并确保找到一棵简单的树.设S 是s 个数据样本的集合，假定类标号属性具有m 个不同类Ci ( i=1，,m）。设si 是类Ci 中的样本数。对一个给定的样本分类所需的期望信息由下式给出: （1）其中pi 是任意样本属于Ci 的概率，并用si/s 估计.设属性A 具有v 个不同值a1，a2，av.可以用属性A 将S 划分为v 个子集S1，S2，,SV;其中，Sj 包含S 中这样一些样本，它们在A 上具有值aj。设sij 是Sj 中类Ci 的样本数.根据由A 划分子集的熵由下式给出： （2）项充当第j 个子集的权，并且等于子集（即A 值为aj）中的样本个数除以S 中样本总数。熵值越小，子集划分的纯度就高。对于给定的子集Sj: （3)其中,Pij=Sij/Sj 是Sj 中的样本属于类Ci 的概率。面向账户的决策树分类预测算法912第一步：计算面向账户的反洗钱决策树分类预测算法训练集S 划分前的熵。数据集S 中的分类属性C = 是否涉嫌洗钱有2 个不同的离散属性值“ Y ”和“N ”, 将数据集S中的所有记录分成2 个类别。假设该训练集S 中全部的记录数为s ， 分类属性值为“ Y "和“N "的记录数分别为S Y 和S N .数据集S 的总熵值在划分之前是属于不同类别的记录的信息量的加权平均， 权重以训练集中的发生概率衡量。那么划分之前，数据集S 的总熵值为：第二步:计算数据集S 按照A 6 属性进行划分后的熵。非类别属性A 6 具有3 个不同的离散型属性值“高”、“中”、“低”，可以把整个数据集S 划分成3 个子集 S 高 、 S 中 、 S 低 。设这3 个子集中全部的记录数为S 高， S 中, S 低， 其中分类属性值为“ Y ”和“N "的记录数分别为S Y高, S N 高， S N 中， S Y中, S Y低，S N 低。则有子集S 高的熵值为：同理可得子集S 中和S 低的熵值.属性A 6 把数据集S 划分成3 个子集 S 高 、 S 中 、 S 低 后,数据集S 的总熵值为3 个子集的熵的加权平均.则有数据集S 划分后的总熵值为:第三步：计算数据集S 按照属性 进行划分前与划分后的熵差按照公式可得数据集S 按照属性进行划分前与划分后的熵差为:Gain （A6） = E（SY,SN) E（A6）最终得到了在面向账户的反洗钱决策树分类预测算法训练集中按照非类别属性 进行划分的信息增益值Gain （) .决策树算法会按照同样的步骤计算、 这5 个非类别属性的信息增益值Gain （） 、Gain （） 、Gain （） 、Gain （） 、Gain () ，然后比较它们的大小,取其中值最大的非类别属性作为根节点划分的最佳选择。四 结论决策树算法是基于信息熵理论的有效的算法。它运用了交叉确认的模型验证方法。本文通过对数据的分析，利用决策树理论以及相关性分析，对初选的数据进行筛选,得到比较科学合理的数据挖掘结构，然后再对决策树进行构建和修剪，得到分类规则，进而得出综合评价。决策树算法对数据分布无任何要求, 应用于银行和金融的效果也比较好, 因此具有良好的发展前景， 值得我们深入研究.据挖掘掘 参考文献1杨胜刚,王 鹏，贺学会. 决策树算法在反洗钱领域中的应用研究J。湖南大学学报.2006，20（1）：6571。2徐晓霞，李金林.基于决策树法的我国商业银行信用风险评估模型研究J。北京理工大学学报.2006，8(3)：71-74。3 武魏巍，王如燕，丁日佳。基于数据挖掘的银行客户管理信息系统的应用J。金融理论与实践，2006（10）：3537。4 巩帅.交通流量数据的分类规则挖掘J。计算机工程与应用,2006，42（6）：219-2205 张渝，周宗放。商业银行信用风险评价指标的熵权选择方法J.电子科技大学学报,2006（5）：857-860。6张立.决策树分类算法在CRM中的应用J。统计和咨询,2006，(2):2829。7赵红宇.CRM中的数据挖掘技术J。商场现代化，2006,(6）:1538 郭超峰, 李梅莲。基于ID3算法的决策树研究与应用J，许昌学院学报,2007年第5期.9 刘惟一, 李维华等. 智能数据分析， 北京科学出版社，2007年. 10 CHEN Liang-wei.Study and development of decisiontree algorithm on farmer credit evaluation.Computer Engineeringand Applications，2008，44（31）：242244。11 Yu D R, Hu Q H， Wu C。 Uncertainty measures for fuzzy relations and their applications. Appl Soft Comput， 2007， 7:1135114312 Kamishima T, Akaho S。 Dimension reduction for supervised ordering. In: Proceedings of the Sixth InternationalConference on Data Mining (ICDM06). Hong Kong， China, 2006。 1822