决策树学习及SEE5的使用.ppt

《决策树学习及SEE5的使用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、决策树学习及SEE5的使用决策树学习一、什么是决策树学习？决策树学习是一种逼近离散值目标函数的方法，这种方法将从一组训练数据中学习到的函数表示为一棵决策树。决策树学习是应用最广泛的归纳推理算法之一，已经被成功地应用到从学习医疗诊断到学习评估贷款申请的信用风险的广阔领域。二、决策树的表示OutlookWindHumidityOvercastRainSunnyHighStrongNormalWeakYesYesNoYesNo上图绘出了一棵典型的学习到的决策树。这棵决策树根据天气情况分类“星期六上午是否适合打网球”。为了提高决策树的可读性，可以将学习到的决策树表示为多个IF－THE

2、N规则。如上面的决策树可以表示成以下的规则集：Rule1:IFOutlook=SunnyANDHumidity=HighTHENNoRule2：IFOutlook=SunnyANDHumidity=NormalTHENYesRule3：IFOutlook=OvercastTHENYesRule4：IFOutlook=RainANDWind=StrongTHENNoRule5：IFOutlook=RainANDWind=StrongTHENYes三、决策树学习的适用问题通常决策树学习最适合具有以下特征的问题：.事例是由一系列固定的属性（如Temperature）和它们的值（例如

3、Hot）来描述的。例事例：最简单决策数学习要求每个属性取少数的离散的值（例如Hot，Mild，Cold）；扩展的算法允许处理值域为实数的属性。.目标函数具有离散的输出值。.训练数据可以包含错误。决策树学习方法对噪声数据具有很好的健壮性，无论是训练样例所属的分类错误还是描述这些样例的属性值错误。.训练数据可以包含缺少属性值的实例。这些问题的核心任务都是要把样例分类到各可能的离散值对应的类别中，称之为分类问题（classificationproblem）。四、基本的决

4、策树学习算法TheTDIDTfamilytreeCLS(1963)ACLS(1981)ID3(1979)ASSISTANT(1984)ID3(Quinlan,1979,1985)是一种自顶向下增长树的贪婪算法，在每个节点选取能最好的分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都已被使用过。Hunt’sConceptLearningSystemframework,CLSconstructsadecisiontreethatattemptstominimizethecostofclassifyinganobject.ACLS(PatersonandNib

5、lett)是ID3的推广。允许用于描述事例的每个属性取任意多个整数值。而ID3和CLS只允许每个属性取有限个离散值。使得算法可以处理图像识别等更复杂问题。ASSISTANT(Kononenko,BratkoandRoskar)允许事例的属性取连续的实数值；某些分类值可以属于另一个分类；还可以从所提供的数据中选择一个“较好”的训练集。用于医学诊断问题。ID3算法基本的ID3算法通过自顶向下构造决策树来进行学习。构造过程是从“那一个属性将在树的根节点进行测试？”这个问题开始的。为了回答这个问题，使用(信息增益)来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性将被选作

6、树的根节点的测试。然后为根节点属性的每个可能值产生一个分枝，并把训练样例排列到该属性值对应的分枝之下。然后重复整个过程，用每个分支节点关联的训练样例来选取在该点被测试的最佳属性。直到终止条件得到满足。用熵来度量训练样例的均一性即纯度.S表示训练集合.分类属性有c个不同的分类值.则S相对于c个状态的分类的熵定义为：熵度量的是集合S的纯度，我们以分类值只有＋，－两类的分类问题为例分析如图：用信息增益来度量期望的熵降低属性A训练集合SValues(A)属性A的所有可能值的集合Sv是S中属性A的值为v的子集则属性A相对样例集合S的信息增益定义为：Gain(S,A)是由于知道属性A的值

7、而导致的期望熵减少。换句话来说，Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。WhethergotoplaytennisDayOutlookTempHumidityWindPlayD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNorma