决策树方法

决策树方法（精选十篇）

决策树方法 篇1

关键词：决策树,分类,算法

分类就是学会一个分类函数或构造一个分类模型 (也指分类器) 。构造一个分类器可以用规则或决策树模式表示, 其过程一般分为建立模型和使用模型分类两个步骤.在构造模型通常把数据集分成训练集和测试集。在训练阶段就要为对每个类别相应数据集进行一个准确的描述或产生一个模型;在测试阶段, 利用类别的描述或模型进行对测试数据集测试。

目前常用的分类算法:决策树方法、KNN方法、贝叶斯方法、人工神经网络方法、粗糙集方法和关联规则分类法等。这些算法是主要的算法, 他们都有其优缺点, 都有其适用的数据。本文将对分类算法中的决策树进行一个简单介绍。

一、概念

决策树是由一系列判断 (包括条件和结论) 组成的一种树状结构, 是实例属性值约束的合取式。在其树型结构中, 每个结点表示对一个属性值的测试, 分支表示测试的结果, 而树的叶结点表示类别, 从决策树的根结点到叶结点的一条路径对应着一条合取规则, 整个决策树的产生是一个自顶向下的方式, 其大致过程是:首先, 利用一组训练数据集训练, 生成决策树, 再次, 利用生成的决策树, 对一组未知数据集属性的取值进行分类。

决策树分类算法由Quinlan提出了著名的ID3算法和C4.5算法, 随后为了满足大规模数据的处理, 又对算法进行多次改进算法, 其中SLIQ和SPRINT算法是两个最具代表性的算法。

二、算法介绍

1. ID3算法

ID3算法的核心是:用信息增益 (information gain) 作为属性的选择标准来确定决策树的各级结点属性, 因而对于每一个非叶子结点进行测试时, 都能获得被测试记录最大的类别信息。其具体方法是:测试所有的属性, 选取信息增益最大的属性字段, 建立决策树的一个结点, 由该属性字段的不同取值建立决策树的分支;然后采用递归方法对各分支的子集建立决策树结点的各分支, 直至所有子集只属于同一类别的数据为止。所构建成一棵决策树, 可以利用它对新的样本进行分类。

定义1:若存在n个相同概率的消息, 则每个消息的概率p是1/n, 一个消息传递的信息量为log2n!"

定义2:若有n个消息, 其给定概率分布为p= (p1, p2, …pn) , 则由该分布传递的信息量称为P的熵, 记为

定义3:若一个记录集合T根据类别属性的值被分成互相独立的类C1, C2…Ck, 则识别T的一个元素所属哪个类所需要的信息量为Info (T) =I (p) , 其中P为C1, C2…Ck的概率分布, 即P= (|C1|/|T|, …..|Ck|/|T|)

定义4:若我们先根据非类别属性X的值将T分成集合T1, T2…Tn, 则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到, 即Info (Ti) 的加权平均值为:

定义5:信息增益度是两个信息量之间的差值, 其中一个信息量是需确定T的一个元素的信息量, 另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量, 信息增益度公式为:

2. C4.5算法

C4.5算法在继承ID3算法的优点的基础上对其进行了改进, 用信息增益率代替信息增益来选择属性, 同时在树的构造过程中对树进行剪枝避免了过拟合问题, 还能够处理属性值缺少的样本, 提高了抗噪能力。C4.5算法所采用的分类规则也容易理解, 而且准确率要来得高, 但在构造树的过程中也存在不足, 主要是因为对多次对数据集进行顺序扫描和排序, 降低算法的效率, 不适合大训练集数据。

3.%SLIQ算法

SLIQ算法是在C4.5决策树分类算法的基础上进行了改进, 其主要思想是在构造决策树的过程中使用“预排序”和“广度优先策略”两种技术。

1) 预排序。SLIQ算法为了解决在决策树结点构造过程中对数据集排序所产生的耗时而采用了预排序技术。

2) 广度优先策略。SLIQ采用广度优先策略是为了消除在C4.5算法中树的构造按照深度优先策略完成时对每个属性列表在每个结点处都进行一遍扫描所产生费时。此方法构造决策树时, 在同一层只需对每个属性列表扫描一次, 就能寻找到最优分裂标准的叶子结点。

4.

SPRINT算法为了减少驻留于内存的数据量, SPRINT算法为了解决减少内存中的数据存量, 而对决策树算法的数据结构进行进一步的改进。其方法是将SLIQ中需要驻留于内存的类别列表去掉, 将其类别列归到每个属性列表中。因此, 在每个属性列表的遍历过程中寻找当前结点的最优分裂标准时, 无须对其他信息进行参照, 表现在对属性列表的分裂, 也就是对每个属性列表分成两个, 存放各自结点的记录。

三、实例分析

有一个信息系统, 是关于公司雇佣员工几种因素来决定是否雇佣这个员工。根据这些信息, 有如下一个决策表, 本文将对决策树ID3和C4.5两种常用方法进行介绍。

1.%ID3算法

(1) %计算决策树属性的熵

信息熵的定义:

(2) %计算决策树条件的熵

(2.1) %条件属性共有3个, 分别是本地人、经验、参考意见。分别计算不同属性的信息增益:

本地人共分为二个组是和否:%

本地人的平均信息期望:

本地人变量的信息增益计算为:

(2.2) %经验共分为3个组高、中等、低:

经验的平均信息期望:

经验变量的信息增益计算为:

(2.3) %参考意见共分为3个优秀、好、一般:

参考意见的平均信息期望:

参考意见的信息增益计算为:

通过上述计算可以知道经验的信息增益最大, 其次是本地人, 最后是参考意见, 所以选择经验作为根节点, 接下来要考虑剩下的两个属性的增益,

2.%C4.5算法

从上选取各属性增益最大的属性作为根结点, 此后的方法与ID3的相同, 不同之处就是判定的准则由信息增益变成信息增益率。

四、总结

由上述实例通过该例子, 我们了解到用ID3算法简单, 易理解, 最终都能构造出一个决策树, 但构造决策树难以得到最优的, 而且是一种单变量决策树的方法, 忽略了属性之间的联系。C4.5算法是在ID3算法的基础进行改进, 因此它继承ID3算法优点, 又与ID3算法有所不同:用信息增益率来选择属性, 弥补了用信息增益选择属性时偏向选择取值多的属性的不足;可以处理连续数值型属性, 即对连续型属性值离散化;可以对不确定的属性进行处理。由于在构造树的过程中, 多次的对数据集进行顺序扫描和排序, 因而导致算法的效率降低。此外, C4.5的数据集将驻留在内存中, 所以当训练集大得在内存中无法容纳时程序就无法运行。所以, 每个算法都有各自的利弊, 根据实际情况选择一个适合算法。

参考文献

[1]杨明, 张载鸿决策树学习算法ID3的研究[J].微机发展.2002 (5) :6-9

[2]王光宏, 蒋平数据挖掘综述[J]同济大学学报, 2004, 32 (2) :246-252

[3]江效尧, 江伟决策树在数据挖掘中的应用研究[J]安庆师范学院学报 (自然科学版) , 2003 (1) :83-85

[4]王清毅, 张波, 蔡庆生目前数据挖掘算法的评价[J]小型微型计算机系统, 2000 (1) :75-77

[5]肖攸安, 李腊元数据挖掘与知识发现的理论方法及技术分析[J]交通与计算机, 2002 (1) :57-61

[6]罗可, 林睦纲, 郗东妹数据挖掘中分类算法综述[J]计算机工程, 2005 (1) 3-5

[7]http://blog.csdn.net/aladdina/article/details/4141127

[8]http://www.cnblogs.com/zhaoqian/archive/2011/01/25/1944717.html

[9]http://wenku.baidu.com/view/64919e3043323968011c926d.html

风险评估技术-决策树分析 篇2

决策树分析

1 概述

考虑到不确定性结果，决策树(Decision tree)以序列方式表示决策选择和结果。类似于事件树，决策树开始于初因事项或是最初决策，同时由于可能Www.发生的事项及可能做出的决策，它需要对不同路径和结果进行建模。

2 用途

决策树用于项目风险管理和其他环境中，以便在不确定的情况下选择最佳的行动步骤。图形显示也有助于沟通决策原因。

3 输入

带有决策点的项目计划。有关决策可能结果和有可能影响决策的偶然事件的`信息。

4 过程

决策树开始于最初决策，例如继续项目A，而不是项目B。随着两种假定项目的继续，不同的事项会发生，同时需要做出不同的可预见性决定。这用树形格式进行表示，类似于事件树。事项发生的可能性能够与路径最终结果的成本或用途一起进行估算。

有关最佳决策路径的信息是富有逻辑性的，考虑各条路径上的条件概率和结果值可以产生最高的期望值。

5 输出

输出包括：

● 显示可以采取不同选择的风险逻辑分析；

● 每一个可能路径的预期值计算结果。

6 优势及局限

优势包括：

● 对于决策问题的细节提供了一种清楚的图解说明；

● 能够计算到达一种情形的最优路径。

限制包括：

别把决策树画 歪 了 篇3

在某种意义上，任何一项决策都像是一次赌博，对决策好坏的评估不能光看结果，而且要看决策者的判断，及其审慎评估相关风险的努力。企业和个人都可以通过多种方式改善决策过程，从而减少做出糟糕决策的可能性。

在本文中你将看到，诸如“决策树”等工具在决策过程中所起的重要作用。这些工具能帮助经理人对问题条分缕析，仔细考量各种选择，并计算相关风险。

不过，决策图也不能保证万无一失，它无法确保任何时候都决策正确。不管决策图有多美妙，在很大程度上，它还要依赖人类的判断，特别是依赖决策者正确评估相关风险的能力。这一过程与理性无关，因为人类行为中充满了各种偏见，这会给决策制造诸多障碍。

我的观点是，只有理解了这些偏见会对我们产生怎样的影响，我们才能设计出某种方案消除或者尽量弱化这种影响，让公司能够更有效地评估它所面临的选择。

栽下一棵决策树

简单的情况下或许不需要什么特别的决策工具。不过，在情况复杂时，如果不借助战略性管理工具，直观地显示问题的结构可能相当困难。

所谓“决策树”，就是以树形图的方式表明，一旦你做出了某种选择，后面可能发生的一系列情形。它能帮助你厘清问题的本质，评估风险对最终结果可能造成的影响。

让我们以欧洲一家制药公司为例来讲解如何利用决策树工具做决策。该公司CEO马克（Marc）正准备决定是否继续某种疟疾药的研发工作，这项工作需要投资1，000万欧元。

该项目一旦完成，公司就必须申请一项专利。根据以往经验，获得专利的概率为40%。如果申请成功，公司就有两种选择：以3，500万欧元的预计价格转让专利许可，或自己直接销售产品。

自己直接销售将需要追加投资1，500万欧元，用于设计并实施生产、营销等活动。此外，该公司还面临着生产要素价格波动的问题——现金流的净现值在某个范围内波动：若要素价格较低，净现值估计为6，500万欧元；若要素价格适中，净现值估计为3，000万欧元；若要素价格较高，净现值估计为2，000万欧元。出现上述各种情形的可能性分别为30%、50%和20%。

因为举棋不定，马克绘制了一棵决策树（参见副栏“马克的决策树”）。第一个决策是，要投资1，000万欧元还是完全取消该研发项目。该选择用一个正方形表示——正方形代表“决策节点”，意思就是，需要决策者在这里选择一种行动方案。

如果马克决定继续这一项目，现金流就取决于能否获得专利。这种不确定性用一个圆形来表示。这种决策者无法控制结果的节点称为“事件节点”。

事件节点的每一分支都代表一种可能情形。一个事件节点应该包含所有可能的情形，这些情形必须相互排斥，这样才能保证如果其中一种情形出现，其他所有情形都不会出现。

获得专利后就遇到了另一个决策节点，因为这时候马克必须决定是转让专利许可，还是自己直接销售这种药物。不过，如果马克决定自己直接销售，就会出现另一个事件节点，因为不受公司控制的要素价格会影响利润。

既然决策树考虑到了决策和事件的时间序列，这个树状图就应该从左往右推进，各个节点按照时间先后发生，表明决策者必须做出一项选择，然后才能解决不确定性的问题。

一旦问题以这种图形的方式呈现出来，决策者就能够计算出树状图每一分支的最终值。在本例中，净利润可以通过下述路径得出：

如果马克取消这一项目，公司将铁定获得0欧元。

如果马克继续该项目，并且未获得专利，公司将损失1，000万欧元。

如果获得专利并转让，公司将赚2，500万欧元（预计转让收入3，500万欧元减去投资1，000万欧元）。

如果获得专利且自己直接销售产品，而且要素价格较高，净利润将为-500万欧元（预计收入2，000万欧元减去追加投资1，500万欧元，再减去最初投资1，000万欧元）。

如果获得专利且自己直接销售产品，而且要素价格适中，净利润将为500万欧元（预计收入3，000万欧元减去追加投资1，500万欧元，再减去最初投资1，000万欧元）。

如果获得专利且自己直接销售产品，而且要素价格较低，净利润将为4，000万欧元（预计收入6，500万欧元减去追加投资1，500万欧元，再减去最初投资1，000万欧元）。

虽说决策树有助于厘清所有可能的结果，但马克在做出最终决定之前还需要再干一件事：计算每一行动方案的期望值。

计算期望值

期望值就是所有可能结果的加权平均值，权重就是事件节点上每一分支的概率。决策者必须对所有可能情形进行权衡，并选择期望值最高的那种情形。

为了说明问题，我们再举一个例子。假设你被一家公司雇用，人力资源总监告诉你，你必须在以下两种薪酬方案中选择一种：

每月5，000欧元。

每月的第一天去找你的老板，用抛硬币的方式决定你的月薪。如果正面朝上，你当月就可以拿到11，000欧元；如果背面朝上，你当月就只能拿到1，000欧元。

你会选择哪种薪酬方案？如果你知道自己会在这家公司干上几年，那么可以选择期望值较高的方案——也就是抛硬币的方案，因为在这段时间内，你的实际薪酬的期望值可以达到平均每月6，000欧元。

若要期望值能够兑现，就必须有“重复”因素在内，即事件在一段时间内重复发生。比如有一位房地产经纪人，过去的经验告诉他，每月卖出一栋房子的概率是50%，卖出两栋的概率是35%，三栋是15%。那么，在12个月的时间里，这名经纪人预期每月可以卖出1.65栋房子。有些月份卖出三栋，有些月份卖出两栋，有些月份卖出一栋（显而易见，没有任何一个月份会卖出1.65栋）。

nlc202309021920

在各种商业活动中都可能出现重复的现象，比如出版业。出版书籍中有98%会亏钱，比如说每种亏5万欧元，另外的2%会成为畅销书，每种畅销书的平均回报是1，000万欧元。那么每种书的平均利润就是151，000欧元，因为畅销书的利润能够弥补其他书亏的钱。

以期望值为基础做决策的另一个前提条件是，如果出现不利后果，你不至于破产。

再来考虑一下每月抛硬币决定薪酬的情况。如果正面朝上，你那个月就会拿到11，000欧元；如果背面朝上，你那个月就只能拿到1，000欧元。接下来，假设你每月要支付2，000欧元的住房按揭贷款。在这种情形下，尽管长期而言抛硬币的方案能让你每月的薪酬达到6，000欧元，你也不能选择这种方案，因为如果前三个月抛硬币的结果都是背面朝上，你的房子可能就没了。

在实践中运用期望值

以制药公司为例，它定期投资一系列研发项目，但其中很多项目不会最终进入市场。正因如此，它需要不断对假设提出质疑，重新评估决策的可能结果。

为方便起见，我们假定上述例子中的制药公司是一家大型企业，如果没有获得专利，1，000万欧元的损失对它来说不算什么。在这样的情形下，就可以用期望值来评估不同方案，并依此做出最终决定。

为了确定哪个方案的期望值较高，马克采取了从后往前推的方式，先看树状图终端的各个节点。在每一个事件节点，他都计算出相关分支的期望值；在每一个决策节点，他都选择期望值最高的分支。这种方式叫作“决策图简化法”，可以指明在每一个点哪种策略是最优的。

副栏“马克的决策图简化”更新了之前的决策树，添加了每个决策的期望值。通过计算生产并直接销售这种药品的期望值（-0.2×500万）+（0.5×500万）+（0.3×4，000万），马克意识到，平均而言，这个节点的价值是1，350万欧元。这意味着，如果马克决定继续这一项目，并且获得专利，那么他就会决定转让专利许可，因为这样做的期望回报（2，500万欧元）比生产并直接销售这种药品的期望值更高。

接下来，马克计算了继续这一项目的期望值。这次，他用获得专利的概率（0.4）乘以转让专利许可的可能回报（2，500万欧元），然后减去专利申请被驳回的概率（0.6）乘以由此造成的损失（1，000万欧元），得出期望值是400万欧元。因此，马克的决定应该是继续该研发项目。

了解你自己的弱点

通过利用决策树和期望值，马克得以改进自己的决策过程。不过，这种方法也有其局限性，最重要的局限来自人们的一些偏见。偏见使人们失去了理性，也正因为如此，人类的判断远远说不上是无懈可击。

就像马克一样，所有的经理人都在一个相对不明朗的世界里做决策。在我们所做的大多数决策中都充斥着人类的偏见。只有理解了这些偏见造成的风险，然后设计出某种系统抑制此类风险的影响，经理人才能安心地确定，自己所做的决策已经毫无瑕疵——至少在人力所及的范围内是如此了。

为了让读者对这一问题的普遍性有所认识，我特别列出了三种常见的人类偏见，并且在个人和组织层面上提出了一系列策略来抑制此类偏见对决策的影响。

锚定效应

所谓“锚定”（anchoring），指的是人们在估测的时候过于受到初始值的影响。在一项著名的研究中，研究人员让参与者给出他们愿意为数件产品支付的最高金额。在他们说出这个数字之前，参与者被要求写下他们社会保障号码的最后两位数字。研究人员发现，这些人写下的两位数与他们给出的价格存在显著的相关性。社保号最后两位数字最大（80～99）的参与者给出的价格最高，而社保号最后两位数字最小（01～20）的参与者给出的价格最低。这表明人们有一种非理性倾向：围绕着一个暗示值（即“锚点”）做出自己的判断，而不是先去批判性地评估这一暗示值有什么价值。

虽说大多数人可能都善于做出相对判断，但要做绝对判断就难多了。经理人不要轻信自己的直觉，应当尽可能用更多的量化参照标准来支持自己的决策。下面再举两个例子。

有一个很有名的实验，我在课堂上也经常做这个实验。我让学生们在两个方案中做出选择：免费领取一张价值10美元的礼品券，或者支付7美元换取一张20美元的礼品券。尽管第二个方案的回报事实上更高，但仍有超过70%的学生选择了第一个方案。

不过，如果在这两个方案中，礼品券的成本都增加1美元，情况就完全不一样了，人们就会变得更理性。当学生们被要求从支付1美元换取一张10美元的礼品券和支付8美元换取一张20美元的礼品券之间做出选择时，超过60%的人选择了后一种方案。这是因为，在第一种情形下，“免费”这个词成了一个锚点，学生们围绕这个锚点做出了决策。

当亚马逊公司（Amazon）对超过25美元的订单提供免费配送服务时，类似的情况发生了。全球各地的销售都得到了提振，除了法国——在法国，销售状况几乎丝毫未变。对这种异常状况的调查发现，亚马逊法国公司收取了1法郎的配送费。尽管这区区1法郎的配送费和免费相差无几，顾客却并不这么想。后来，亚马逊在法国也提供免费配送服务，销售随即上升。

框架效应

所谓“框架效应”（framing），指的是你呈现信息的方式（不管是向公司董事会，还是向与你一同工作的团队）可能会对最终决策或最终结果产生重大影响。

器官捐赠项目很好地证明了这一点。一项针对欧洲国家的研究发现，各国的参与率显著不同。为什么100%的法国驾车人选择死后捐赠器官，而只有4%的丹麦驾车人做出同样的选择？

就如行为经济学家丹·艾瑞里（Dan Ariely）指出的那样，其中原因完全在于“是否参与器官捐赠项目”这一选择的呈现方式。在参与率低的国家里，受访者如果想参加这个项目就在一个方框里打勾；而在参与率高的国家里，受访者如果不想参加这个项目才在相应的方框里打勾。考虑到在两种情形下，大多数受访者都不愿意在方框里打勾，那么问题的呈现方式就是造成这种差异的全部原因。

nlc202309021920

在一篇题为《为什么优秀的经理人会选择拙劣的战略》（Why Do Good Managers Choose Poor Strategies）的文章中，伊丽莎白·奥姆斯特德·泰斯伯格（Elizabeth Olmsted Teisberg）详细阐述了以正面措施或负面措辞设计战略选择的重要性。她写道：“之所以要实施战略变革，一种说法是为了避免丧失竞争优势，另一种说法是为了改进优势来源，增强竞争地位。同样，之所以要开发新技术，可以是为了避免落后于竞争对手，也可以是为了吸引新客户，扩大市场份额。”

这可不是“你五十他半百”这么简单。研究发现，个体面对得益的不确定性和损失的不确定性时，态度迥异。因此，分析时是以损失还是得益来表述，会导致人们做出不同决策。通常来说，人们在得益方面是风险厌恶型的，而在损失方面是风险偏好型的。

赌博是一个经典的例子。大多数人都会在输钱之后很难收手，然后以输掉的钱的两倍下注。但并不是只有在赌徒身上才会出现这种行为。为了挽回颜面，公司员工和经理人也一样有可能做出类似的举动，比如他们积极参与的某一商业活动出现了亏损，他们也可能会再双倍下注。

投入升级效应

人们不愿意接受或承认一项必然的损失。相反，他们会冒险止损，但同时也面临着损失加重的可能性。这就是所谓的“投入升级效应”（escalation of commitment）。很多公司之所以倒掉，原因就在于此。（参见副栏“驶入漩涡”）

企业如何确保自己的高管和员工不会做出这种危及企业利润的行为？以下措施可以帮助企业降低因框架效应和投入升级效应带来的风险。

保持风险偏好的稳健平衡 这个社会是由风险厌恶型、风险中立型和风险偏好型的人构成的。正因如此，企业需确保其决策团队中，这几类人都得到广泛代表。同样，在分析策略时，各种不同的视角也要得到代表。

预备一个退出策略 在动态的环境中，要做出优秀的决策，需要在时移境迁之际不断再评估。有时候，对一家公司来说，最好的决策就是修正或放弃以往曾大力主张的行动方案。管理界首屈一指的思想家彼得·德鲁克（Peter Drucker）就曾建议过，组织要每月举行会议，考虑“缩减投资”的机会，也就是停止无效的项目。

避免当场做出重要决策 大多数组织都把决策看成一个事件，而不是一个流程。因此，他们认为关键决策会议非常重要，出了问题就赶快开会解决。这里的关键在于，建立一个系统，监督项目以及项目背后决策的演变，同时鼓励人们把所有有风险的决策摆到桌面上。

学会应对糟糕的结果 一些决策，甚至是良好的决策也会产生不好的结果，这是不可避免的。重要的是，分析这些不好的结果是在哪种情形下发生的：是在获得充分信息、对风险进行了缜密计算后发生的，还是因不良的决策习惯而导致的。

以区间的方式描述未来的可能 利用区间预测，而不是点预测，这样可以避免“假精确”，增强可信度。尽管这样可能会更难确定未来收入，但也让经理人变得更加现实，更理性地看待他们力主的项目未来能获得多大的成功。

过度自信：你到底有多大把握？

大多数人都会对不确定性感到不舒服，在这种心理状态下，自然就会产生过度自信的倾向，让人们感觉良好，以为自己知道很多，其实不然。

我在IESE商学院高管培训项目中教授决策课程，在课堂上，我让学员回答五个常识性问题，并让他们告诉我，他们对自己答案的正确性抱有多大的自信。几乎每次的结果都差不多：在那些表示对自己的答案抱有80%信心的人中，只有50%左右的人答对了问题。这种过度自信的倾向对企业的决策有着至关重要的影响，特别是在评估产生某种结果的概率的时候。

回到前面制药公司的例子。获得专利的概率（40%）和对生产要素价格的估计都来自马克手下的运营副总裁。那么，仅仅依靠一个人提供的信息就制定了全部决策，马克的这种做法是明智的吗？那位副总裁的判断力到底有多可靠？他是否过度自信？或许马克和那位副总裁都有既得利益，希望看到疟疾药品进入市场，而且不管他们自己有没有意识到，他们都过高地估计了一切按计划进行的可能性。

为了避免出现过度自信，第一步就是要保持警惕：总是保持对过度自信迹象的警觉。尽可能依靠确凿的事实，确保信息源可靠。所有评估都须经过各部门有经验的经理人的复核。一些银行要求再融资审批必须由前审批人之外的人来做。本文前面提出的建议——在预测未来时给出一个上下波动范围，而不是精准数字——在这里也适用。

最重要的一件事是，有意识地质疑自己的估测。在评估一项决策时，大多数人都会寻找那些能支持自己意见的证据，而不去考虑反面信息。为了避免落入这一陷阱，你需要在分析阶段引入几个不同的视角。这可能包括组织的外部人，比如买家、供应商，甚至是竞争对手。

就如伊丽莎白·奥姆斯特德·泰斯伯格教授所指出的那样，通过不同角度观察，不仅能帮助经理人发现瑕疵，为可能出现的意外事件做准备，还能帮助他们跳出常规的思维模式，增强创造力。积极唱反调的“魔鬼代言人”还会质疑是否有运气的成分在内，同时注意寻找以前没有考虑到的机会，以及在现有逻辑中存在认知偏见的证据。

从错误中学习

要想做好决策，最后的关键是：从错误中学习。正如德鲁克所言：“将决策结果与预期进行对比，高管们就知道自己的长处在哪里，哪里需要改进，缺少哪方面的知识或信息。这会让他们了解到自己的偏见。”

归根结底，了解你自己的偏见，了解你们团队的偏见，并设法限制偏见对决策过程的不利影响，这样才能为自己的企业做出正确的决策——至少大部分情况下能做出正确决策。

观点概要

我们时常需要在不确定的环境下做决策，这时借助一些决策工具，可以让我们理清复杂的问题，仔细考量各种选择，计算相关风险。

nlc202309021920

“决策树”就是这样的一种工具，它以树形图的方式表明，一旦你做出了某种选择，后面可能发生的一系列情形。你可以判断每种情形的发生概率和预期价值，权衡之后选择期望值最高的那种情形。

然而，不要被这看似完美的“科学”流程所误导，决策图并不能保证万无一失。无论决策图有多美妙，在很大程度上，它还要依赖人类的判断，而人类的判断会受到各种偏见的影响。以下是三种最常见的人类偏见：

锚定效应

框架效应

投入升级效应

意识到这些偏见的存在，我们才能设计出某种方案消除或者尽量弱化它们的影响，让公司能够更有效地评估它所面临的选择。

驶入漩涡

不愿接受已经造成的损失有时会造成致命的错误。近几十年来，金融行业有过无数这样触目惊心的重大灾难性事件，究其根本，可归结为投入升级效应。

巴林银行（Barings Bank）事件或许是最臭名昭著的一个例子。这家有着两百多年历史的老牌银行，一直小心谨慎地为腰缠万贯的客户提供金融服务，其中包括英国王室。然而1995年，仅在几个星期内，一名驻新加坡的交易员尼克·利森（Nick Leeson）的无良行为就让这家银行轰然倒塌。他干的事情就是：试图在会计上做手脚，掩盖自己规模越来越大的损失，不让上级知道。

类似的事情在2008年也发生过。当时，热罗姆·凯尔维尔（Jerome Kerviel）让法国银行业巨头法兴银行（Société Générale）损失了49亿欧元。检方对此的解释是：“凯尔维尔的本意不是想搞垮这家银行，他只是想成为明星交易员。交易就好比毒品，能让人上瘾。他对这种赌市场的复杂‘游戏’产生了依赖，而且这像是一个漩涡，很难从中脱身出来。”

后来的丑闻——比如2012年摩根大通（JP Morgan）的“伦敦鲸”交易巨亏事件——表明，不仅仅是无良的个人，甚至整个管理层都可能拒绝承认损失，自掘坟墓，越陷越深。

当然，事情不一定大到搞垮整个银行或整个行业，在有关企业日常经营的小决策中，也能看到投入升级现象，比如：

？为劣质项目再融资

？守住价格不断下跌的股票不放

？在需要帮助的时候不愿开口求人

？犯了错误之后不愿立即承认

？事情不对头的时候不立即承认

？不愿取消一项已计划好的事情

？在交货期或到达时间方面不切实际：“我五分钟后就到……”

？不愿在维护和安全保障方面投资

在你的个人生活或工作当中，是否有哪些方面需要克服这种不愿承认坏事的心理？你最好放下姿态，而不是硬撑下去，否则麻烦可能越来越大。

决策树方法的研究进展 篇4

随着数据库技术的不断发展及数据库管理系统的推广应用, 存储在数据库中的数据量急剧增大, 大量数据背后必定蕴藏着许多信息, 如何从数据库中抽取出有用信息逐渐成为商业界普遍关心的问题。数据挖掘的概念为解决这一问题而提出并在近年来引起学术界的广泛关注, 成为学术研究的热点。

数据挖掘, 又称数据库中的知识发现, 是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的知识或模式, 它是数据库研究中的一个很有应用价值的新领域, 融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。

数据挖掘的任务是从大量的数据中发现模式或知识。模式按其作用可分为两类:一类称为描述型模式, 它是对数据中存在的规律做出描述。如泛化模式、聚类模式、关联模式及时间序列模式。另一类是预测型模式, 它依据从己有数据获得的知识对未知数据的某些性质进行预测。包括分类模式和回归模式。其中, 分类模式是一种重要的预测型模式。

用于挖掘分类模式的方法有很多, 如决策树方法, 贝叶斯网络, 遗传算法, 基于关联的分类方法, 粗糙集, k-最临近方法, 等等。其中决策树方法以其易被人理解、需要信息觅少、效率及准确率较高等优点占据着重要地位。决策树方法自产生至今, 先后涌现出多种算法, 包括ID3、C4.5、CART, SLIQ、SPRINTPUBLIC, 基于人机交互的方法等。他们的共同特点是对训练样本集进行挖掘后都会生成一棵形如二叉树或多叉树的决策树。树的叶子节点代表某一类别, 非叶节点, 包括根节点及内节点代表某个一般属性 (非类别属性) 的一个测试, 测试的一个结果形成非叶节点的一个分枝。从根节点到叶子节点的一条路径形成一条分类规则。一棵决策树能够很方便的转化为若干条分类规则。人们可以依据分类规则直观地对未知类别的样本进行预测。

2 数据挖掘工具

根据挖掘方法, 数据挖掘可分为:机器学习方法、统计方法、神经网络方法和数据库方法。根据所采用的方法, 数据挖掘工具可以大致分为以下六类:

(1) 基于规则和决策树的工具:大部分数据挖掘工具采用规则发现和决策树分类技术来发现数据模式和规则, 其核心是某种归纳算法, 如ID3和C4.5算法。它通常是对数据库中的数据进行挖掘生成规则和决策树, 然后对新数据进行分析和预测。

(2) 基于神经元网络的工具:基于神经元网络的工具由于具有对非线性数据的快速建模能力, 因此越来越流行。挖掘过程基本上是将数据簇聚, 然后分类计算权伯。

(3) 数据可视化方法:这类工具大大扩展了传统商业图形的能力, 支持多维数据的可视化, 同时提供了进行数据分析的图形方法。

(4) 模糊发现方法:应用模糊逻辑进行数据查询排序。

(5) 统计方法:这此工具没有使用人下智能技术, 因此更适于分析现有信息, 而不是从原始数据中发现数据模式和规则。

(6) 综合方法:许多工具采用了多种挖掘方法, 一般规模较大。

3 决策树方法的优缺点

决策树, 又称判定树, 是一种类似二叉树或多叉树的树结构。树中的每个非叶节点 (包括根节点) 对应于训练样本集中一个非类别属性的测试, 非叶节点的每一个分枝对应属性的一个测试结果, 每个叶子节点则代表一个类或类分布。从根节点到叶子节点的一条路径形成一条分类规则。决策树可以很方便地转化为分类规则, 是一种非常直观的分类模式表示形式。

相对于其它分类方法, 决策树算法应用最为广泛, 其独特的优点包括: (1) 可以生成可以理解的规则; (2) 计算量相对来说不是很大; (3) 可以处理连续和种类字段; (4) 决策树可以清晰地显示哪些字段比较重要。

当然, 决策树也存在着很多的缺点: (1) 对连续性的字段比较难预测; (2) 对有时间顺序的数据, 需要很多预处理工作; (3) 当类别太多时, 错误可能会增加比较快; (4) 一般算法分类的时候, 只是根据一个字段来分类。

4 决策树方法的主要研究进展

4.1 决策树的精度

决策树的预测精度一直是研究的重点, 判断各种决策树的生成算法和剪枝算法的优劣, 精度是最重要的衡量指标。构造多变量决策树是为了减小树的规模, 其最终目的是为了提高决策树的精度。如何提高决策树的预测精度是决策树方法的研究方向之一。

4.2 决策树技术与其他技术的结合

在知识发现中, 不可能用一种方法处理所有的数据集, 完成各种数据采掘任务, 需要研究同其它方法相结合的问题。并且, 决策树方法本身也可以和其它方法结合, 现在已有人把决策树方法同神经网络技术、模糊集理论、遗传算法等相结合来进行研究, 结果不同程度地提高了处理效率和精度。多种方法的交叉结合也是决策树方法研究的方向之一。

4.3 寻找更好的简化决策树方法

简化决策树的研究工作主要有两个方面, 一是对比各种不同的简化决策树方法, 分析它们各自的特性、优点和缺点。另外一个就是寻找更好的与传统方法不同的简化决策树的方法, 这一直是决策树技术研究的一个热点。

4.4 不确定环境下决策树研究

实际的数据集中存在着一些缺值数据, 最简单的方案是删除带有未属性值的例子或是将未知属性值用最常用的值代替, Quinlan J R提出的一种解决方案是依据对象的其它属性值和类信息来预测未知属性的属性值。对缺值数据的处理一直是决策树研究的热点。

4.5 决策树技术的软件实现

将决策树技术软件化一直是决策树技术的方向之一。如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术, 一直是大家努力的方向。

5 小结

决策树算法已经有了广泛的应用, 并且已经有了许多成熟的系统, 这此系统广泛应用于各个领域, 如语音识别, 模式识别, 专家系统等。但是, 解决一个复杂的数据挖掘问题的任何算法都要面临以下问题:从错误的数据中学习、从分布的数据中学习、从有偏的数据中学习、学习有弹性的概念、学习那些抽象程度不同的概念、整合定性与定量的发现等, 归纳学习当中还有很多未开发的课题等待我们去研究。

摘要：随着计算机硬件和软件的飞速发展, 尤其是数据库技术与应用的日益普及, 人们面临着快速扩张的数据海洋, 如何有效利用这一丰富数据海洋的宝藏为人类服务, 业已成为广大信息科技工作者所重点关注的焦点之一。为有效解决这一问题, 自20世纪80年代开始, 数据挖掘技术逐步发展起来。而分类作为数据挖掘中的一个重要的方法, 目前的研究在商业上应用最多。决策树算法是分类的一种重要方法, 同时也是一种典型的数据挖掘技术。本文分析了决策树方法的优缺点, 同时也阐述了决策树方法在各个领域的研究进展。

关键词：数据挖掘,决策树,进展研究

参考文献

[1]李卿.决策树优化算法研究[D].西南交通大学, 2009.

[2]万永锋.决策树学习算法在金融自助设备监控系统中的应用[D].郑州大学, 2007.

[3]戴南.基于决策树的分类方法研究[D].南京师范大学, 2003

[4]李明仑.基于动态模糊格的决策树理论及应用研究[D].苏州大学, 2006.

基于决策树的红色籽用西瓜数据挖掘 篇5

利用Clementine软件提供的决策树C5.0算法,探索红色耔用西瓜自交系多个数量性状之间的相互制约关系.初步建立了单瓜种子重决策树模型,预测精度达到68%.可据此模型对红籽瓜自交系的各经济性状进行定量分析,为育种生产者进行优良自交系和亲本选配提供决策.

作 者：樊建峰 马学良 张广斌 李绍稳 汪伟伟 程磊 FAN Jian-feng MA Xue-liang ZHANG Guang-bin LI Shao-wen WANG Wei-wei CHENG Lei 作者单位：樊建峰,FAN Jian-feng(鄂尔多斯市统计局,内蒙古,017000)

马学良,MA Xue-liang(内蒙古鄂托克前旗农牧业局,内蒙古,016200)

张广斌,李绍稳,ZHANG Guang-bin,LI Shao-wen(内蒙古鄂托克前旗兽医站,内蒙古,016200)

汪伟伟,程磊,WANG Wei-wei,CHENG Lei(安徽农业大学信息与计算机学院,合肥,230036)

基于决策树的心理危机预警模型研究 篇6

关键词： 心理危机； 关键因素； C4.5； 危机预警

中图分类号：TP301 文献标志码：A 文献标志码：1006-8228（2013）01-03-03

Research on psychological crisis alert model based on decision tree

Zhang Limin， Jin Xinmin

（Zhanjiang Normal University， Zhanjiang， Guangdong 524048， China）

Abstract： With the rapid development of network culture and the strong influence of social transformation， the psychological crisis of college students has become a serious challenge to the universities and society. Through the investigation and study， various factors of the psychological problems from several aspects， such as character， learning， economy and so on， are analyzed. Psychological crisis information is examined by means of decision trees （C4.5 algorithm）. The critical factor is searched in order to establish a psychological crisis alert model of college students， to perfect the mechanism of crisis alert and crisis intervention and to prevent the psychological crisis.

Key words： psychological crisis； critical factor； C4.5； crisis alert

0 引言

危机系指因内、外环境因素所引起的一种对组织生存具有立即且严重威胁性的情境或事件[1]，心理危机则可以定义为当个体面临突然或重大生活逆境时出现的心理失衡状态[2]。大学生心理危机有深刻的社会文化根源，其核心是异质文化的冲突所导致的价值观念的冲突，突出地体现为文化整合中社会主体文化的内在分裂导致大学生亚文化的贫困、文化转型中家庭功能的失调、文化冲突中传统教育的偏颇等[3]。大学生心理危机已成为当前校园危机产生的重要原因，正在威胁着高校的正常教学和管理工作。英国危机管理专家迈克尔·里杰斯特曾经说过：“预防是解决危机的最好办法”。分析大学生心理危机产生的各种因素有利于构建心理危机预警机制和教育干预体系。

计算机技术的飞速发展，信息系统的大量应用，海量数据背后大量的隐藏信息，迫切需要人们对现实数据进行统计分析以发现其中存在的关系和规则，从中获取有用的知识并对未来的发展趋势作出预测。决策树（Decision Tree）是数据挖掘分类方法中最常用的方法之一，能够以图形化的形式表现挖掘的结果，从而方便于使用者快速作出决定或预测。决策树在各行业有广泛的应用，本文将决策树C4.5算法应用于心理危机相关信息的数据挖掘中，旨在分析影响当前高校大学生心理危机的关键因素，为高校有针对性地开展心理健康教育工作提供支持，同时也为建立信息化的校园心理危机预警系统提供理论支撑。

1 高校大学生心理危机产生的关键因素

当代大学生心理危机的产生可以用社会环境、家庭影响、个人性格等多种因素，以及与之关联的各种关系的集合来描述，特别是在当前的社会转型期，社会变革对大学生造成强烈的冲击，价值观念的多元化、人际交往的复杂化、各种压力的并存化极大地增加了大学生的心理负荷，集中表现在客观环境的外在挤压力和个体心理的内在驱动力[4]。

性格缺陷是导致心理健康失衡的重要因素，性格缺陷产生的原因很多，我们采用来源于中国心理卫生协会大学生心理咨询专业委员会组织修订的UPI（University Personality Inventory）调查问卷对入学新生进行调查。根据UPI测试结果，我们对19.11%心理健康状态严重的学生进行邀约面谈并进行甄别，通过与学生的邀约面谈发现，大部分学生通过谈心可以舒缓压力并表现正常，仅有极少数性格偏执，观察发现这部分性格偏执的学生在日后的学习生活中产生了诸多问题。家庭环境是造成各类性格问题的最大原因，尤其是离异家庭和单亲家庭对子女的伤害极大，此类家庭的教育会出现相应的缺失或问题。

学习压力的上升正成为影响大学生心理健康的重要因素，招生规模的不断扩大，学生之间学习能力和成绩水平存在的差异也进一步拉大，还有竞争对手的突然增多，学习环境的相对自由等，让一部分学生陷入了学习困境，导致了学习成绩直线下滑，心理压力也随之增大。此外，学生对专业的满意度也值得关注，兴趣是最好的老师，然而很多就读于一般本科院校的学生却无法选择自己喜欢的专业进行学习。我们在对师范院校的工科学生调查时发现，只有42.66%的学生对自己所学的专业满意，近五成的学生不喜欢自己的专业，心理压力的加剧导致学习和心理双重压力恶性循环，成绩的下滑和补考的增多进一步加深了学生的学习压力。

网络文化的冲击正急速地影响着当代大学生的心理健康状况。在相对封闭的校园环境下，网络在以其自身特有的形式和手段推动着文化的丰富与创新的同时又承载并传播大量文化垃圾。形形色色的网络游戏对自制力尚不健全的大学生构成了严重的影响，充斥着色情和暴力的网络游戏，会对大学生的心理健康产生负面影响。人类的心理病态主要是由于人际关系的失调而来，沉湎于网络虚拟世界容易造成对现实世界缺乏正常的认知，自我封闭会导致缺乏自我认同，不能正确地评价自己与他人，从而造成人际关系紧张，缺乏应对冲突和危机的能力，色情与暴力元素的存在则会进一步加深心理缺陷。

经济因素在心理健康中的影响力正逐步上升。当前部分高校已有超过30%的学生家庭经济困难，昂贵的学费和生活费对于这部分学生来说是沉重的负担。贫富差距的持续拉大，来自不同家庭的学生在消费观念和消费方式上存在着巨大反差，许多原本相对平衡的心态出现失衡。在调查中我们发现，有29.36%的学生选择“过于担心将来的事情”，这是对未来工作的担忧，也是对未来经济状态的担忧，高额学费的投入已不能产生高额的经济回报，过重的家庭经济压力带来严重的心理压力，最终可能导致危机事件的发生。

2 C4.5算法描述

数据挖掘是一个从大规模数据库的数据中抽取有效的、隐含的、未知的、有潜在使用价值的知识的过程，数据挖掘的结果往往只有统计学上的意义，用户需要寻找的是有意义的、相对部分数据有效的知识，而非一定要考虑所有的数据。目前，数据挖掘的方法和技术主要包括统计分析方法、关联规则方法、决策树方法、粗糙集理论方法、神经网络法、遗传算法、可视化技术等。

分类作为数据挖掘的方法之一，它根据带类标号的历史数据建立模型，进而使用该模型来预测类标号未知的数据所属的类。最知名的分类算法是决策树方法，决策树是用于分类的一种树结构，决策树方法的起源是概念学习系统，发展到ID3方法为高潮，最后又演化为能处理连续属性的C4.5。本文设计并实现用C4.5分类算法来挖掘学生心理危机相关信息数据，通过分类方法较全面地分析学生心理危机与各种因素之间隐藏的内在联系，从大量数据中发现潜在规律，找出隐含的模式，准确掌握学生的心理动态，为心理危机预警提供更多有价值的信息。

J.R Quinlan在1993年提出了C4.5算法[5]，他针对基于ID3算法利用信息增益作为分类评价函数来选取最优属性而导致容易倾向于选择取值较多的属性的缺陷，适当地修改了分类评价函数，挑选具有最高信息增益率的属性作为测试属性。对样本集T，假设变量a有n个属性，属性取值a1，a2，…，an，对应a取值ai出现的样本个数分别为ni，若n是样本的总数，则应有n1+n2+…+nk=n。Quinlan利用属性a的熵值H（X，a）来定义为了获取样本关于属性a的信息所需要付出的代价，即

I（X，a）定义为平均互信息，选择属性a作为分类属性之后信息熵的下降程度，即不确定性下降程度，在ID3算法中选择使得I（X，a）最大的属性作为分类属性。

C4.5则选择信息增益率来作为评价指标，信息增益率定义为平均互信息与获取a信息所付出代价的比值，即

信息增益率是单位代价所取的信息量，是一种相对的信息量不确定性度量，以信息增益率作为测试属性的选择标准，即选择E（X，a）最大的属性a作为测试属性[6]。

3 基于C4.5的心理危机预警模型

在高校中，可供我们挖掘的与学生心理健康相关的数据非常多，依据前面的分析我们选择相关性较大的性格指数、游戏指数、贫困指数、志愿指数和补考指数作为建立心理危机预警分类决策树的依据，测试数据表的各字段属性如表1所示。

表1 测试表字段属性

[字段名称＼&数据类型＼&取值范围＼&备注＼&ID＼&自动编号＼&＼&记录ID号＼&upi＼&文本＼&ultra/normal＼&性格指数＼&game＼&文本＼&indulgence/normal＼&游戏指数＼&poverty＼&文本＼&poor/rich＼&贫困指数＼&volunteer＼&文本＼&like/dislike＼&志愿指数＼&test＼&文本＼&much/few＼&补考指数＼&alert＼&文本＼&high/low＼&预警级别＼&]

关于性格指数，依据UPI测试的分类结果分别约谈可能存在心理健康问题的学生来确定其性格指数，ultra代表存在相对严重心理问题，normal代表心理健康状况相对良好。游戏指数依据学生日常生活中沉湎于游戏的情况分类，indulgence代表沉湎于游戏，并由此产生逃课、成绩下降等现象，normal代表相对正常。贫困指数则主要依据学校的贫困生认定情况分类，通过贫困生认定的即认为是poor，没有通过的为rich。关于志愿指数，依据入学时所选志愿分类，凡学校和专业为第一志愿选择的为like，否则为dislike。关于补考指数，依据自入学起的累积补考课数分类，补考课数大于3的为much，否则为few。预警级别则依据对学生的综合评价分类，评价依据主要来自负责管理该班级的辅导员和班主任的评价，需要指出的是，预警级别高并不代表一定会产生心理危机突发事件，只代表产生各类心理危机的可能性更高。

我们选取了具有典型意义的17条记录作为样本数据进行C4.5的算法实现，表2是经过预处理的数据，也是决策树算法的输入数据，采用由SPSS生产商推出的数据挖掘软件Clementine进行模拟实现。在Clementine中支持两个决策树模型调用，其中C5.0是对算法C4.5的实现，通过实验得出的决策树如图1所示。

图1中，补考指数成为各种属性中信息增益率最大的属性，这说明当前在评价学生时往往把成绩作为第一要素，成绩的好坏决定了学生在老师眼中的优劣标准。与此同时，少数性格偏执的学生成为关注的重点，这类学生往往会提出各种非常规问题，给学校管理带来一定的困难。另外，沉湎于游戏已成为学生产生心理危机的决定性因素之一，沉湎于游戏带来的直接后果是成绩下滑，性格内向，网络游戏正严重地影响着当代大学生的身心健康。我们还发现专业喜好程度和家庭贫困程度并不是产生心理危机的直接影响因素，但仍值得我们关注。

4 结束语

在网络文化飞速发展的今天，大学校园正承受着物质文明和精神文明的巨大冲击，大学生正面临着日益严峻的各种挑战，产生各种各样的困惑，如果不能得到及时的帮助或引导将可能产生非常严重的心理危机，进而影响正常的教学和管理活动。

本文通过调查研究，分析了大学生心理危机产生的种种因素，重点分析了关键因素的产生原因和可能影响，通过引入决策树C4.5算法建立了大学生心理危机预警模型，实验结果验证了心理危机产生的各种因素的可能作用，为建立健全心理危机预警和干预机制，有效预防心理危机的发生提供了理论支持。我们下一步研究的重点是如何从海量的心理危机相关数据中高效地挖掘出学生可能产生心理危机的数据，从而更有效地预防大学生心理危机的产生。

参考文献：

[1] Lichtenstein R， ec al. School Crisis Response： Expecting the Unexpected[J].Educational Leadership，1994.52（3）：79-83

[2] Caplan G. （1964） The Principles of Psychiatry.New York： Basic.

[3] 黄建榕，陈建新.论我国大学生的心理危机及其干预系统的建构[J].华南理工大学学报，2004.6：73-77

[4] 吕杰.跨世纪新生代的社会心理承受能力及培养机制[J].当代青年研究，1995.6：11-14

[5] Quinlan J R. C4.5：Programs for Machine Learning[M]. San Mateo：Morgan Kaufmann Publicshers，Inc，1993：17-42

基于全同态加密的决策树构造方法 篇7

分类[1]是一类重要的数据挖掘问题,目的在于从海量数据中发现潜在的、未知、隐含而有价值的规律和知识。目前海量的数据都是存储在物理隔离的各个站点,即处于分布式环境中。常用的数据挖掘技术大多数是基于未加密过的原始数据来进行的,由于数据存储在不同的站点,每个站点都不愿公开自身的数据。为了在保护站点隐私的前提下进行安全地数据挖掘,基于隐私保护的分类提供了有效的解决方案。

目前,隐私保护决策树构造的研究已经取得了较好的发展,其技术主要可以分为两大类,即基于数据扰动的方法以及基于安全多方计算的方法。文献[2]提出了基于Paillier的同态加密算法,在水平分布类型的数据上进行关联规则的挖掘,Paillier算法在密文操作上所消耗的时间相对较少,但是Paillier公钥密码体制自身加密效率过低。文献[3]结合安全多方计算技术和数据干扰技术,设计了一种数据垂直分布下具有隐私保护能力的聚类挖掘算法,该算法以用户和数据挖掘人员都是诚实的为基础,如果存在不诚实的参与方,方案就不能实现隐私保护。结合RSA公钥加密和全同态加密,文献[4]提出了一种隐私保护的聚类挖掘算法,同样是保证在半诚信的环境中,参与挖掘的各站点数据隐私不被泄露。文献[5]提出的是引入同态加密来改进xlnx协议,使之适应多个节点的水平分布式数据库,并使用改进协议来进行信息增益的计算。为此,针对.密钥加密效率不高、进行数据挖掘时候需要可信第三方等问题,本文提出一种基于全同态加密的决策树构造方法,该方法通过ID3算法确定根节点,再对各站点数据离散化,进而对加密的数据做同态运算,得到各属性的信息增益,比较各属性信息增益的大小确定子节点,最终生成完整的决策树。

数据在网络中的分布有三种情况[6]:①水平分布类型,即每个站点仅包含一部分元组,但每个元组都是完整的,包含所有属性;②垂直分布类型,即各个站点包含所有元组,但每个元组都不是完整的,仅包含一部分属性;③混合分布类型,即数据的分布既有水平分布又有垂直分布类型。本文仅限讨论第2种情况。

1 相关知识介绍

1.1 全同态加密

2009年IBM研究员Craig Gentry发表了一篇论文[7],从数学上提出了“全同态加密”的可行办法。全同态加密是一种特殊的加密方式,即可以在不知道密钥的条件下对密文进行运算。对于任意有效的运算F和明文m,有性质(1)。

简单来说就是可以对加密的数据进行任意多次加和乘的运算,运算的结果经过解密过后是相对应于明文做同样运算的结果。全同态一般分为加法同态和何乘法同态[8]。

加法同态:如果存在有效算法,E(X+Y)=E(X)E(Y)或者X+Y=D(E(X)E(Y))成立,并且不泄露X和Y。

乘法同态:如果存在有效算法,E(X*Y)=E(X)E(Y)或者X*Y=D(E(X)E(Y))成立,并且不泄露X和Y。

1.2 决策树

决策树是用于分类和预测的主要技术,在数据挖掘、机器学习领域得到了巨大发展。它着眼于从一组无次序、无规则的事例中推理出决策树表示形成的分类规则。对一个分类问题或规则学习问题,决策树的生成时一个从上至下、分而治之的过程。决策树从根节点开始,对数据样本进行测试,根据不同的结果将数据样本分成不同的样本子集,每个样本子集构成一个子节点,对每个子节点再进行划分,生成新的子节点,不断反复,直至达到特定的终止准则。

1.3 决策树构造中的隐私保护

假设分别有如表1-2所示的两个站点A和B,站点A存放数据集Sa,站点B存放数据集Sb。两个站点想合作在数据集Sa∪Sb上建立决策树[9],使用ID3算法构建决策树需要两个站点交互数据,但是由于数据的隐私性,任意一方都不可以把自身站点未经加密的数据透露给对方。

2 基于全同态加密的决策树构造方法

本文的算法思想是根据ID3算法计算出每个站点各属性的信息增益,从而确定决策树的根节点,在选取子节点时,属性的信息增益需要两个站点互相公开自身的数据才能得到。首先将两个站点的数据分别离散化,即用0-1来表示站点数据,根据设计的安全两方点积协议[10],先对数据进行加密,然后对密文做各种同态运算,达到隐私保护的目的,从而算出各属性的信息增益,确定子节点,构造生成决策树。

2.1 算法基本思路

在Sa∩Sb上构建决策树的算法过程如下:

①两个站点分别计算数据集里每个属性的信息增益。选取信息增益最大的属性作为根节点。

②初始化一个包含根节点的队列Q。

③While Q!=null do{

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

评估每一个属性Attr[i]的分类标识能力,找到最佳分割点。

④分割成节点N1,N2,…,Nk。

⑤如果节点Ni不能被准确分类则将Ni加入到队列Q。

其中,Attr表示包含站点A和B的所有属性集合,Attr[i]表示属性集合里第i个属性。垂直两方构建决策树的关键问题就是计算每个属性的信息增益,即Information Gain(S),从而找到最佳子节点。首先需要计算数据集S的信息熵,即:

其中,P(ui)表示类别为ui的样本所占样本的数据集比例,即P(ui)=|ui|/|S|,|ui|表示类别为ui的样本数,|S|表示训练集样本的总数。属性的信息增益公式为:

其中,v表示属性Attr[i]的取值为v,|Sv|表示属性Attr[i]取值为v的样本个数,|S|为训练集样本的总数。为了计算属性的信息增益,我们需要知道Attr[i]去指定值时的样本个数,所以可以将站点A和B的数据离散化,写成0-1的形式,从而将问题规约到向量内积上。用N维的向量Va表示站点A,Va(i)=1表示第i个记录满足站点A,反之Va(i)=0则表示不满足;同样的用N维的向量Vb表示站点B。若存在一个非零项V=Va(i)·Vb(i)(i=1,…,N),则表示该非零项同时满足站点A和B,通过计算Va(i)·Vb(i)可以得到同时满足站点A和站点B的样本数。

在计算Va和Vb内积时站点A不能直接将数据发送给B,本文对Va和Vb进行加密,在Va、Vb的密文上做同态加和同态乘运算得到Va和Vb的内积。由于站点的数据均是二进制数据,本文选取DGHV方案作为加密方案,假设站点A拥有DGHV方案的某个私钥,并公布其公钥,DGHV方案为:

输入:站点A明文Va;站点B明文Vb。

①B生成一个N维的随机向量R1,并生成密文C1=E(Vb+R1);并将C1发送给站点A。

②A对Va加密得到C2=E(Va)。计算E(Va)·E(Vb+R1)=C3,并将C2和C3发送给B。

③B计算C4=E(Va)·E(-R1)+C3;站点B生成一个N维的随机向量R2,并计算C5=C4+E(R2),再将C5发送给站点A。

④A对C5解密得到D(C5)=Va·Vb+R2;站点B计算(-R2);将两个数据相加即可得到Va·Vb的值。

2.2 正确性和安全性分析

根据全同态加密的原理,C4=E(Va)·E(-R1)+E(Va)·E(Vb+R1),D(C5)=D[C4+E(R2)]=D[E(Va)·E(Vb)+E(R2)]=Va·Vb+R2。将站点A对C5解密得到的值和站点B计算的(-R2)相加即可得到Va·Vb。

首先,由于站点B没有掌握到私钥,其知道的所有的数据都是经过加密的,故其不可能掌握到站点A的的内容。对于站点A,虽然其拥有私钥,有解密的权限。但是在第一步中,其解密出来C1的信息,由于不知道随即向量R,故无法得知Vb的信息。即站点A猜到Vb的概率只有1/2,针对于DGHV方案来说,其本身就是对以比特为基础加密的,所以猜是毫无意义的。

举例说明:

本案例根据ID3算法,由上面的公式(2)-(3)计算得到三个属性Outlook、Humidity、Wind的信息增益,选取信息增益最大的值作为根节点。根据根节点的属性取值得到相应的分支,递归调用ID3算法确定子节点。先将两个站点的数据离散化,在Linux操作系统下使用sage Math数学工具进行DGHV方案,主要是编写DGHV加密算法的密钥生成Key Gen()、加密Encrypt(pk,m)、解密Decrypt(sk,c)三个阶段,最后确定子节点。具体计算过程如下:

2.2.1 站点A计算Gain(S,Outlook)

其中,u1=“No”,u2=“Yes”,|u1|=3,|u2|=2,|S|=5。

2.2.2 站点B计算Gain(S,Humidity)和Gain(S,Wind)

2.2.3 根节点的确定

根据公式计算得出表1 Outlook和表2 Wind的信息增益一样大,Humidity信息增益最小,故A和B协商选取Outlook属性作为根节点。

2.2.4 子节点的选取

由于Outlook属性有Sunny和Rain两个属性值,所以根节点有两个分支(Sunny,Rain),分别计算Sunny和Rain两个分支上的节点情况。Gain(SRain,Wind)的计算过程如下:

①站点A、B上数据的离散化

用向量Va(Rain)表示属性Outlook取值情况,1表示属性Outlook取值为Rain,0则表示取值为其它属性;用向量Va(Rain_No)和Va(Rain_Yes)表示属性Outlook取值为Rain的时候所属类别情况。此时站点A的数据可以用向量表示为:Va(Rain)=(0,0,1,1,1)T、Va(Rain_No)=(0,0,0,0,1)T、Va(Rain_Yes)=(0,0,1,1,0)T。

同样的站点B的数据可以用向量表示为:Vb(False)=(1,0,1,1,0)T、Vb(True)=(0,1,0,0,1)T。

②确定类别为ui所占总样本的比例

为了求得Entropy(SRain,False),A、B双方需要合作才能计算,因为A拥有属性为Rain的样本数据,却不知道这些样本数据的Wind的属性是False还是True;站点B知道Wind属性,却不知道哪些数据是属性为Rain的样本数据。站点A拥有属性Outlook取值为Rain的数据,但无法确定这些数据的Wind属性取值,同样地,站点B知道Wind属性取值为False的数据,但不确定数据是否属于SRain,所以用Va(Rain)和Vb(False)做点积运算表示同时这条数据在站点A属于Outlook取值为Rain,站点B属性Wind取值为False。|uNo|表示类别为No且同时满足在站点A属于Outlook取值为Rain,在站点B属性Wind取值为False的样本数,|uYes|表示类别为yes且同时满足在站点A属于Outlook取值为Rain,在站点B属性Wind取值为False的样本数。

同样地,A和B合作计算Entropy(SRain,True)。

最终,可以得到:Gain(SRain,Wind)=0.918,同样的方法可以计算出:Gain(SRain,Humidity)=0.252

选取Wind属性作为分支根节点,Wind取”False”时全为适合运动,该分支的节点为叶子节点标记为合适;取”True”时为不合适运动,该分支的节点为叶子节点标记为不合适。完整的决策树如图1所示,其结果与Weka[11]工具下使用相同参数和数据集的结果一样的。

3 结束语

近年来,对分布式数据进行挖掘研究已成为当前数据挖掘重要的方向之一。对于垂直两方分布的数据,提出一个基于全同态加密的协议,该协议允许两个站点之间进行安全的通信,达到了隐私保护的目的。该协议不需要第三方的存在,减少了数据通信量,从而有效降低网络传输时间。下一步将研究在水平分布的情况下如何使用全同态加密的方法构造决策树。

参考文献

[1]Han J,Kamber M.数据挖掘:概念与技术[M].范明,孟小锋,等译.北京:机械工业出版社,2001.

[2]Shubhra Rana P,Santhi Thilagam.Hierarchical Homomorphic Encryption based Privacy Preserving Distributed Association Rule Mining[J].IEEE computer society,2014,14:379-385.

[3]乔冉冉.数据垂直分布隐私保护数据挖掘算法研究[D].南京:南京邮电大学,2012:37-40.

[4]袁武,仁勋益.水平分割数据的保护隐私聚类挖掘方法研究[J].计算机技术与发展,2015(2).

[5]Xiao M J,Huang L S,Shen H,et al.Privacy Preserving ID3 Algorithm Over Horizontally Partitioned Data[C].Proceeding of the Sixth International Conferences on Parrel and Distributed Computing,Applications and Technoloies.Washington,DC,USA:IEEE Computer Society,2005:239-243.

[6]Skillicorn D B,Mcconnell S M.Distributed prediction from vertically partitioned data[J].Journal of Paraller and Distributed Computing,2008,68(1):16-36.

[7]Gentry C.Fully homomorphic encryption using ideal lattices[C].Proceeding of the 41stAnnual ACM Symp on Theory of Computing(STOC 2009).New York:ACM,2009:169-178.

[8]刘明洁,王安.全同态加密研究动态及其应用概述[J].计算机研究与发展,2014,51(12):2593-2606.

[9]Du Wen-liang,Zhan Zhi-jun.Building decision tree classifer on private data[C].Proceeding of the IEEE ICDM Workshop on Private,Security and Data Mining,2002.

[10]夏超,仲红,石润华.基于同态加密技术的安全多方乘积协议[J].计算机工程与应用,2015,51(1):76-80.

决策树方法 篇8

然矿物原料,这些原料因成因不同、地质条件不同,其组成与性能往往会有较大的波动,影响正常的生产,配方调试是陶瓷生产的重要环节,其成果的好坏决定着陶瓷企业的命运。开发新产品,更替现有配方中的某些原料,维持正常的生产,都要对配方进行研究和调试。在这些工作过程中,陶瓷原料的遴选是关键性的工作。由于陶瓷原料种类繁多,既有天然矿物原料也有合成原料,而且结构复杂,成分多变,现又缺乏稳定的标准化原料供应,给配方中选择原料和替代原料带来了很大困难,因而对陶瓷原料进行科学分类和识别就显得尤为重要。如何科学、合理地对陶瓷原料进行分类,进而选择适合自己工艺流程的陶瓷原料,已成为众多陶瓷企业关心的且迫切需要解决的问题。我们认为对陶瓷原料的分类是一种多指标多层次的综合评价的过程。由于评价指标的作用和重要性程度难以准确确定,需要适宜的识别模型和方法。

一、决策树模型简介

所谓决策树就是一个类似流程图的树型结构,其中树的每个内部结点代表对一个属(取值)的测试,其分支代表测试的结果;而树的每个叶结点就代表一个类别,树的最高层结点就是根结点。在各种决策树分类算法中,最有影响的是R.Quilan于1986年提出的ID3算法,其基本原理是:首先在数据集中用信息增益(Information gain)作为属性选择的标准找出最有影响力的属性,将数据集分成多个子集,每个子集又选择最有影响力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止,最后得到一棵决策树。目前,决策树分类算法已被广泛应用到许多进行分类识别的应用领域,是一种知识获取的有用工具。

1、C5.0算法简介

C5.0算法可以建立决策树(Decision Tree)或者规则集(Ruleset)。根据能够提供最大信息增益的字段划分样本,对第一次划分出来的子样本递归的划分,直到不能再分为止,最后重新检查最底层的划分,去掉那些贡献不大的分支,得到最终的模型。C5.0可以产生两种模型:决策树和规则集,决策树由算法划分样本直接产生,每个叶子节点表示一个特定的训练数据子集,训练数据集中的每个样本只属于一个叶子节点。也就是说,任何一个给定的样本通过决策树只能得到一个预测结果。规则集是一个用于预测样本的规则集合,实际上是从决策树发现的信息中提取出来的,保留了决策树的大部分重要信息,但结构更加简单。C5.0模型对大量的输入数据非常有效,训练时间短并且较其它模型更容易理解。

2、陶瓷原料特征参数的选择

特征参数的抽取实质就是要按一定的规律整理有关陶瓷原料的性能指标,为后续的数据分析做准备。陶瓷原料常用的性能指标有化学成分、矿物成分及一些相应的工艺参数。此外,依据不同的工作目的、产地、运输条件以及成本等经济学参数也常可作为原料的“性能指标”。在陶瓷配方研究与陶瓷生产控制过程中,化学成分是最直接、容易精确测量和控制的,矿物成分和工艺性参数虽可测量,却因影响因素多而难以定量。以粘土原料为例,粘土类原料又是陶瓷坯体配方中最复杂的,它会影响到坯体的可塑性、结合强度、收缩尺寸和烧成温度,甚至影响到产品的质量。本文以粘土原料的化学成分作为特征参数,这些参数包括9种化学成分,如Si O2,Al2O3,Fe2O3,Ca O,Mg O,K2O,Na2O,Ti O和烧失I.L,将陶瓷原料分为4类:1类,2类,3类和4类利用C5.0决策树探讨陶瓷原料的分类,从而为配方中选择陶瓷原料提供科学的依据。

二、模型的计算与结果分析

根据有关工厂收集的数据,抽取31种粘土原料以其中2/3种作为决策树的训练样本集(表1),另外1/3种作为待判别的未知样本(表2)根据表1,将21种原料的9个特征参数作为输入节点的特征值按照C5.0决策树原理不断调整网络参数,直到训练结果符合决策树模型的要求训练样本集的输出结果较大,它们大多数是由片状和杆状2种结构的高岭石混合组成。其典型的代表有上店土(主要是结晶较差的高岭石类矿物),并含有一定的高铝矿物;第3类粘土Si O2含量高,主要矿物为蒙脱石(也称微晶高岭石)。蒙脱石层间结合力极弱,易理解,可塑性好,干燥强度高。陶瓷工业中常用之以提高制品成型时的可塑性,增加坯体强度,减少搬运损耗,但用量过多会引起干燥收缩过大。这类粘土大多数为风化良好的瓷土和膨润土,典型的代表有黑山膨润土和四班瓷土;第4类粘土中最突出的特点是Fe2O3含量较高,该类粘土属于软质粘土,其组织疏松,质点分散度大,典型的代表是宜兴红泥。宜兴红泥容易粉碎,因含Fe2O3量较高而显红色。

三、模型的应用

从以上表3中可以清楚看到,对未知样品的判别输出结果与实际结果相互印证,与采用聚类分析法及因子分析法的结果一致。可见,决策树模型也是一种对陶瓷原料进行分类的有效实用方法。

我们利用陶瓷原材料互相替代原理,可以将分类的结果直接应用到生产的过程中去,利用这一原理我们可以合理地利用本地的资源,减少实验的盲目性,节约运输的费用从而间接地为企业节省了成本费用。

参考文献

[1]轻工业陶瓷研究所.日用陶瓷工业手册[M].北京:轻工业出版社,1984.

[2]李玉平,刘付胜聪,胡鹏飞.陶瓷原料分类的人工神经网络模型[J].硅酸盐通报.2003(22)06.

[3]周永正,单盈真瓷石和高岭土的分类研究数理统计与管理.1994(05).

决策树方法 篇9

关键词：决策树分类方法,学生成绩挖掘,应用

1 决策树分类方法概述

在数据挖掘研究中,分类方法属于不可或缺的组成部分,且在众多领域获得了理想应用,因而发展成为数据发掘中的一个主流研究方向。所谓数据分类指的是,以训练数据集以及类标号为基础,对相关数据做分类处理,构建对应模型,对预定的数据类集进行描述。对于分类而言,其目的在于构造一个分类模型,然后在该模型的帮助下,以数据库中的数据项为目标对象,将其映射到某个已给定类别。

2 决策树分类算法选择

对于决策树技术而言,ID3算法与C4.5算法属于最常用的两种算法。ID3算法一般借助信息增益这种辅助途径来确定基于哪个属性来形成分支。该选择标准更适合于选择取值相对较多的属性。除此之外,ID3算法只能用来分析离散型数据及其内在属性,不能有效地解决训练集中的缺值问题。C4.5算法是一种基于信息熵理论的先进算法,以目标样本最大信息增益率为分析对象,将其属性当作测试属性,与此同时,还涉及对连续型属性以及属性值空缺等问题的处理。C4.5算法在诸多算法中较为突出,有鉴于此,本文选用C4.5算法以完成对决策树的建立,同时结合实例数据进行相关分析。

3 决策树分类方法在学生成绩挖掘中的应用

3.1问题的提出

现阶段,在高校管理工作中,尤其是学生成绩管理这项工作中,面临最大的问题便是,学生成绩数据极其庞大,然而关于此类数据的处理尚不成熟,仅仅涉及数据备份、查询、统计等,无法发掘学生成绩进步或者退步的内在原因。如此一来,该类数据的真正作用便无法得到有效发挥。所以,借助该类数据对教学工作成效予以有效分析,找出并确定影响学生成绩的相关因素,便成了各大高校普遍关心的问题。本文针对决策树分类方法在学生成绩数据中的具体应用进行相关探讨,在决策树分类算法的帮助下,对相关数据展开深入研究,确定哪些因素将会对学生成绩产生影响,影响程度的大小,以及各因素之间的内在关系,总结了一些有用的知识,并参考这些知识制定更为科学、高效的教学计划,从而推动教学工作更加高效的开展。

3.2解决问题的方案

首先,以当前教务网络管理系统数据库为基础,运用数据库技术建立一个所谓的“学生成绩数据挖掘库”;其次,借助决策树C4.5算法对上述新建数据库中的一系列数据展开相应的分析;最后,构建一个“学生成绩决策树”模型,并制定一个完善的分类规则。主要包括以下工作:1)确定数据分类的对象以及目标;2)数据采集;3)数据预处理;4)数据分类挖掘;5)生成分类规则;6)知识应用[2]。

3.3具体应用研究

3.3.1确定挖掘对象和目标

本研究选取学生考试成绩作为挖掘的目标对象。选取我校2012~2013学年度第一学期《计算机应用基础》课程为例,研究对象为2012级全体学生,共计1667人。挖掘目标是结合学生自身以及教师基本情况来找出哪些因素将会对学生成绩产生影响,同时确定影响的程度。

3.3.2数据分类挖掘

本研究基于学生成绩属性,一共选择了与之存在较大关联的三个属性,一是学生性别,二是教师职称,三是平时成绩,并以上述三大属性为依据完成了成绩分类决策树模型的构建和完善。

以C4.5算法为基础建立学生成绩决策树模型的主要步骤如下:

3.3.2.1 计算分类属性的信息量

对研究样 本归结为4大类,即C1=“优秀”,C2=“中等”,C3=“一般”,C4=“不及格,”如此一来,可得s1=67,s2=153,s3=316,s4=235, 总计s=771。以给定样本为目标对象,对其分类所涉及的信息熵进行计算,得到:I(s1,s2,s3,s4)=1.81914。

3.3.2.2 依次计算出四大测试属性的信息熵

1)以性别属性为目标对象,对“性别”=“男”这一子集的信息熵进行计算:I(30,83,232,186)=1.70479,然后,对“性别”=“女”这一子集的信息熵进行计算 :I(37,70,84,49)=1.93241 ;2) 以教师职称属性为目标对象,对“教师职称”=“高级”这一子集的信息熵进行计算:I(70,76,129,62)=1.8734,然后,对“教师职称”=“中级”这一子集的信息熵进行计算:I(9,15,32,29)=1.84452,最后,对“教师职称”=“初级”这一子集的信息熵进行计算:I(18,62,155,144)=1.84452 ;3)以平时成绩为目标对象,对“平时成绩”=“优秀”这一子集的信息熵进行计算:I(46,98,143,66)=1.87679,然后,对“平时成绩”=“中等”这一子集的信息熵进行计算:I(18,40,132,109)=1.68377,接下来,对“平时成绩”=“一般”这一子集的信息熵进行计算:I(3,14,37,59)=1.52917,最后,对“平时成绩”=“不及格”这一子集的信息熵进行计算 :I(0,1,4,1)=1.25163。

3.3.2.3 依次计算出四大测试属性的期望信息

根据“学生性别”划分赋予样本期望信息为:E( 学生性别 )=1.7756 ;根据“教师职称”划分赋予样本期望值为:E( 教师职称 )=1.78206;根据“平时成绩”划分赋予样本期望值为:E( 平时成绩)=1.74612。

3.3.2.4 依次计算出四大测试属性的信息增益量

Gain( 学生性别 )=0.04350 ;Gain( 教师职称 )=0.03708;Gain( 平时成绩)=0.07302。

3.3.2.5 依次计算出四大测试属性的信息增益率

GainRatio( 学生性别 )=0.0245 ;GainRatio( 教师职称 )=0.0208 ;

GainRatio( 平时成绩)=0.0418

3.3.2.6 比较四大测试属性的信息增益率

对四大测试属性的信息增益率进行比较,确定信息增益率最大的属性,并将其当作根节点。根据计算结果得到,“平时成绩”这一属性表现出最高信息增益率,所以,将其当作测试属性。创建一个节点,然后使用“平时成绩”予以标记,并结合其本身的四大属性值,构建四个分枝,以此为基础对样本进行划分。接下来,对各个分枝节点的划分进行相应计算[3]。

对“平时成绩”是“优秀”的全部可能性进行划分,通过计算求得学生性别属性所对应的信息增益率:GainRatio( 学生性别 )=0.01984 ;同理,通过计算求得教师职称属性所对应的信息增益率:GainRatio( 教师职称)=0.00482。

由计算结果可知,在信息增益率方面,“学生性别”超过“教师职称”。其被选择为“平时成绩”是“优秀”的测试属性,因此,在“平时成绩”所包含的“优秀”这一分支之下创建一个节点,同时使用“学生性别”予以标记,并结合其两个不同属性值,构建两个分支,接下来再计算每一个分支节点的具体划分。所以,只余下“教师职称”这一竖向,可用来对“学生性别”所引出的两个分支基于“教师职称”展开相应划分。

重复3.3.2.1~3.3.2.6步骤,实现对所有分支的有效划分,从而建立一个完整的学生成绩决策树模型,详见图1。

4 结束语

决策树方法 篇10

二维码(Two-dimensional barcode)是在条码技术基础上,在二维平面上按一定规律构造黑白相间的图形用以记录信息,通过输入设备读取几何形体,并识别处理其所表示的信息。

恶意网站是指将木马、病毒等恶意程序种植在网页内,通常没有任何表露恶意性质的外部标志,通过伪装的网址服务内容诱导用户访问该网站,攻击者经常使用网站执行网络钓鱼攻击或分发恶意软件。

手机与二维码的结合拓展了二维码的应用,随着互联网应用的发展,手机拍照二维码获取网址使手机用户浏览网页信息更加方便。同时,二维码逐渐成为恶意软件新的传播途径,针对手机等移动用户的恶意钓鱼网站越来越多。当用户扫描输入存有恶意网址的二维码时, 用户的手机可能被引导访问钓鱼网页、甚至被安装恶意插件,结果会造成用户资料泄露、用户账户密码被盗等安全问题。这些恶意网页对用户手机构成巨大威胁。然 而,二维码表面仅是图片,单凭图片用户不能得知当前二维码所存的网址所对应的网站是否具有恶意行为。

本文主要针对手机用户上网、面向二维码URL,结合机器学习、引入决策树算法,提出恶意网址智能检测系统。针对二维码所存的网址进行识别测试和过滤,以保证用户访问安全的网页。

2恶意网站的现有研究和分析

目前检测、防范恶意网站的方法有恶意网页分析技术、SSL证书分析技术、黑白名单技术等。网页分析技术是研究最深入、研究领域最广、准确率最高的方法,主要包括静态特征检测、动态特征检测、以及基于统计与特征分析的启发式检测技术等。静态特征检测是指从文本 角度分析网页的HTML语句、网页内嵌的JavaScript脚本、Active插件实例化等, 主要通过特征码匹配的方法实现检测。该方法简单有效,但主要缺陷在于只能用于识别已经经过样本采集的已知恶意网页、对未知的恶意攻击则无能为力,而且即使是已知的恶意代码、通过简单的加壳或加密即可逃过该类策略的检测。同时,由于新型木马以及变形木马的产生速度越来越快,及时快速地采集木马特征也是一项具有挑战性的任务。

动态特征检测是指实时监控网页从预载入到整个运行过程中的所有行为,从而判断其是否为恶意代码网页。动态分析把恶意网页当作一个黑匣子,不再分析它的语句和执行流程,而仅测试分析其行为。由于行为分析必须让恶意脚本或者实际的恶意网页完全把行为展示出来,系统会遭受到不同的攻击,因此行为分析系统一般运行在VMware虚拟机上,以使得系统受到损害时能够迅速恢复。

基于统计与特征分析的启发式检测技术是指在已有特征值识别的基础上, 根据总结的恶意代码样本经验, 在没有符合的特征值比对时, 根据代码所调用的API的函数情况 ,如频率、组合等 ,来判断网页是否可疑。这种方法构造的系统分为学习和检测两个阶段,在学习阶段中需要有正规网页和恶意网页训练集,学习得到一个阀值,在检测阶段根据这个阀值判断某个网页是否为恶意网页。

合法的商业网站通常会对安全敏感的网页启用SSL安全连接机制, 以防止信息在传输过程中被窃听、篡改。安全敏感网页的SSL相关信息,包括是否启用了SSL安全连接、颁发SSL证书的CA是否权威可信、SSL证书是否过期、证书中的识别名是否与网址的身份相符等,也可作为识别网址真伪的依据。但是,这种方法在于只有提交用户账号密码的网页才能使用这种技术,而且容易产生误判。

黑名单技术是将所有已经发现的恶意网址记录到一个地址列表、即所谓的黑名单中,据此判断用户所访问的网址是否为恶意网址。黑名单技术实现简单,但其问题在于及时更新黑名单十分困难,现在的浏览器厂商大多是采用这种做法,在用户端建立黑名单库,每隔几天更新一次。这种方式作为浏览器识别恶意网址是相对最优的方法,其缺点在于对于未知网页缺乏识别能力。

目前, 手机等移动端的计算能力相对于PC机尚有差别,专门针对手机的恶意网址检测方法不多,基本采用专家系统规则匹配方法。如果将现有的恶意网站检测技术应用到二维码恶意网站检测中来, 检测恶意网站的主要方法多数需要进入网页,目前手机上不支持沙箱技术, 在检测过程中很可能使用户信息遭受各种安全风险。

3基于决策树的恶意网址检测方法

3.1 恶意网址智能检测方法概述

本文提出通过对二维码存有的网址URL进行智能检测,避开检测过程中用户信息遭受威胁带来的安全风险问题,达到检测恶意网址的目的。考虑到客户端跨平台应 用以及手 机计算资 源等实际 问题 , 利用Web Service技术将恶意网址智能检测算法配置成服务的方式、部署到Web服务器上,提供服务器和客户端之间的信息交换, 使系统对恶意网址识别的响应更加快捷、适用范围更加广泛。

决策树算法在机器学习和数据挖掘领域一直受到广泛重视,算法通过对训练集的学习,挖掘出实用规则, 经测试集对性能测试并调整后、用于对实际数据进行预测。本研究通过收集大量正规网址和恶意网址数据、建立类库,抽取恶意网址URL特征、建立数据集,经过反复训练,构建决策树,经过修枝剪枝对特征进行优化,最终形成用于判别二维码恶意网址的决策树算法。

系统由服务器和客户端两部分组成,服务器端主要功能包括检测二维码恶意网址的决策树算法、在数据库中存取收集积累的数据及算法所利用的相关数据、网址数据接收、检测结果信息回传,主要使用Web Service技术和决策树算法; 客户端分为手机等移动端客户和PC客户,主要功能包括二维码识别、URL传输、以及识别结果提示,主要使用Web Service接口、二维码识别组件等技术。

3.2 数据集的构成

依据统计学思想进行分析, 把网址URL解析成12个属性,包括网址的后缀(Name)、长度(Length)、前缀 (Prefix)、IP地址 (ip1,ip2,ip3,ip4)、点的个数 (Dot)、是否有大写字母(Captial)、是否有数字(Number)、是否有特殊符号(Symbol)、是否为恶意网址(Outcome),并将其表示为向量形式。

3.3 决策树算法训练流程

决策树的总体训练过程如图1所示。

1)设S是s个数据样本的集合。假定类标号属性具有m个不同值,定义m个不同类Ci(i=1,2,...,m)。设si是类Ci中的样本数。对一个给定的样本分类、所需要的期望信息如下:

其中pi是任意样本属于Ci的概率,并用s2/s估计

2)设属性A具有v个不同值{a1,a2,...,av}。用属性A将S划分为v个子集{S1,S2,...,Sv},设Sij是子集Sj中类Ci的样本数。由A划分成子集的熵表示如下:

3)在A分枝将获得的信息增益表示为 :

Gain(S,A)=i(S1,S2,...,Sm)-E(A)

4) 用信息增益率进行属性选择 , 信息增益率定义为:

分裂信息Split Info(S,A)代表了按照属性A分裂样本集S的广度和均匀性。分裂信息定义如下:

其中,S1到Sc是c个不同值的属性A分割S而形成的c个样本子集。

3.4 决策树算法的种类选择

目前决策 树的典型 算法有ID3、C4.5、CART、J48等,不同的决策树会影响系统判别的准确度。

首先对建立好的训练集进行预处理,即对非数值型的属性进行离散化,并优化属性。之后对训练集进行分类回归, 采取十折交叉验证的方法, 将数据集分成10份,轮流将其中9份做为训练数据、1份做为测试数据进行实验。每次实验都会得出相应的正确率,将10次结果正确率的平均值做为对算法精度的估计。运用不同的决策树算法进行训练,根据设置的实例情况,共选择了10种决策树进行对比分析,实验结果如图2所示。结果表明,J48决策树算法的正确率最高,所用的属性集为最优的属性组合,其正确分类比例为94.96%。

3.5 不同属性组合的选择

不同的属性组合同样对预测结果产生很大影响。为提高算法的速度和精度,避免对一些作用小的属性进行分析而增大系统负荷, 选择不同属性组合进行测试,得到最优的属性组合。参考测试决策树算法时每个决策树最后形成的决策树中的属性, 对12个属性进行不同的组合,测试不同组合利用J48决策树算法的正确率。表1所示的测试结果说明, 第8行属性组合、即(name、length、dot、Ip1、Ip2、Ip3、Ip4、prefix)的正确率最高 ,且形成决策树的时间最短。

4实验结果与分析

4.1 实验环境

系统的应用环境分为服务器、PC客户端、智能手机客户端,网络环境包括联通或移动3G网络、WiFi、校园无线局域网、校园LAN等。

利用weka工具实现智能算法, 算法中的重要参数设置如下: 为正规网址和恶意网址, 划分为12, 设为126,不同的属性值v的取值不同,训练集与测试集交叉表1不同属性组合对预测结果产生的影响验证重叠数为10。

4.2 结果与分析

实际检测中,二维码恶意网址数据取自近一个月的瑞星安全日报共计66个,正规网址数据取自hao123网址大全共计60个。126个实验数据有7个返回错误的结果,测试准确率为94.5%。60个正规网址实验数据,有5个返回错误的结果,误报率为8.4%。66个二维码恶意网址测试数据,有2个返回错误的结果,有17个URL失效,49个URL有效,漏报率为4.0%。

相同的测试内容使用“快拍二维码”进行测试,126个测试数据测试准确性为71.5%,66个二维码恶意网址实验数据有36个返回错误结果,漏报率为54.5%。60个正规网址实验数据,没有返回错误结果,误报率为0%。

本系统产生误报的原因在于选取的正规网址大部分是小网站、游戏网站,其某些URL特征跟恶意网站网址的特征类似。本系统漏报率只有4.0%,说明本系统对于未知的恶意网址的判别率很高。由于“快拍二维码”使用的是黑名单技术, 对于未知的恶意网址判别率非常低。实验数据表明,本系统对二维码恶意网址检测具有良好的效果。

5结束语