首页(175) 数据挖掘研究(27) 数据挖掘实践(53) 数据挖掘介绍(25) 杂谈(59) 管理页面   写新日志   退出   关于IDMer

 Blog信息
 
blog名称:IDMer (数据挖掘者)
日志总数:175
评论数量:848
留言数量:119
访问次数:2310877
建立时间:2005年6月24日

 日志更新
 

 我的相册
 

It's me!


 最新评论
 

 留言板
 

 链接
 

 联系方式

 日志搜索





 公告
“数据挖掘者”博客已经搬家,欢迎光临新博客网址:http://idmer.blog.sohu.com
我的新浪微博:
@张磊IDMer
 网络日志
决策树学习
数据挖掘者 发表于 2005-6-29 15:42:13
决策树学习附件:500)this.width=500'>2 机器学习-决策树学习.zip编写:Sunstone Zhang (Aug, 2001)来源:www.cs.utexas.edu/users/mooney/cs391L 决策树决策树是实例(表示为特征向量)的分类器。结点测试特征,边表示特征的每个值,叶结点对应分类。可表示任意析取和合取范式,从而表示任意离散函数和离散特征可将实例分到多个分类(≥2)可以重写为规则,用析取范式(DNF)形式red ^ circle -> positivered ^ circle -> Ablue -> B; red ^ square -> Bgreen -> C; red ^ triangle -> C 决策树学习实例用(属性-值)对表示。离散值处理简单,连续值可以划分区间。输出可以是离散的分类,也可以是实数(回归树)。能有效处理大量数据可处理噪声数据(分类噪声,属性噪声)属性值缺失,亦可处理 基本决策树算法训练数据批处理,自顶向下递归构造决策树DTree(examples, attributes)If 所有样本属于同一分类,返回标号为该分类的叶结点Else if 属性值为空,返回标号为最普遍分类的叶结点Else 选取一个属性,A,作为根结点 For A的每一个可能的值vi   令examplesi为具有A=vi的样本子集   从根结点出发增加分支(A=vi)   如果examplesi为空     则创建标号为最普遍分类的叶结点     否则递归创建子树——调用DTree(examplesi,attributes-{A}) 根属性的选取决策树要尽可能小寻找一组数据对应的最小决策树是NP-hard的简单递归算法是贪婪启发式搜索,无法保证最优子集应尽可能“纯”,从而易于成为叶结点最常用的启发规则是基于信息增益(Information Gain) 熵(Entropy)一组样本S对于二元分类的熵(混淆度)为:其中p+和 p-为S中的正例、反例所占比例若所有样本属于同一分类,则熵为0(定义0log0=0)若样本平均分布(p+=p-=0.5),则熵最大(=1)可把熵视为对样本集分类进行编码所需的平均二进制位数,采用哈夫曼编码压缩,越普遍的分类编码越短对于多分类问题(假设有c个分类),则熵的推广定义:其中pi为属于分类i的样本在S中所占比例 信息增益属性的信息增益是按该属性分割后熵的消减期望值:其中Sv是S中属性A值为v的子集例子:big, red, circle : +small, red, circle : +small, red, square : -big, blue, circle : - 决策树归纳中的假设空间决策树可以表示任何离散函数,归纳就是在此空间内的搜索创建与数据一致的单一离散假设,所以无法提供置信度或构造有用的查询爬山式搜索存在局部最优问题。它可以保证找到符合任何无噪声数据集的树,但未必是最小的批量学习。每项决策需要一次数据集扫描,可提前结束学习以减少噪声影响 决策树学习中的误区树的深度应尽量小。但贪婪搜索可能无法找到最小树,顶层结点可能不是高区分度的 计算复杂度最坏情况是构造出一棵完全树,每条路径都测试了所有特征各层i要对剩下的|A|-i个属性计算最佳分割一般来说,性能与属性个数成线性关系 决策树研究的历史1960’s:Hunt的完全搜索决策树方法(CLS)对概念学习建模1970后期:Quinlan发明用信息增益作为启发策略的ID3方法,从样本中学习构造专家系统同时,Breiman和Friedman开发的CART(分类与回归树)方法类似于ID31980’s:对噪声、连续属性、数据缺失、改善分割条件等进行研究1993:Quinlan的改进决策树归纳包(C4.5),目前被普遍采用 过度拟合和修剪通过学习训练数据来构造分类树,可能无法达到最好的一般化性能,因为 - 噪声数据的影响 - 某些决策仅基于少量数据,与客观事实不符合一个假设H被称为对于训练数据是过度拟合的,指的是如果存在另一个假设H’,在训练集上H的误差比H‘小,但在测试集上H’的误差比H小 过度拟合与噪声分类或属性噪声都会导致过度拟合增加噪声实例<<medium, green, circle>, +>(实际为-)噪声也会直接导致样本的冲突(相同描述,不同分类)。应将叶结点标号为主要的分类<<big, red, circle>, -> (实际上为+)若属性不完备且不足以判别分类时,也可能导致样本的冲突 避免过度拟合的方法需要修剪时的两个基本方法预修剪:支持度不够则停止树的增长后修剪:置信度不够则修剪掉该分支子树是否需要修剪的判别方法:交叉检验:保留部分训练数据用于验证统计测试:通过训练集的统计来判别最小描述长度(MDL):判别该假设的复杂度是否比记忆例外情况的复杂度更高 减小误差的修剪一种后修剪,交叉验证的方法将训练数据分割为两个集合:“生长”和“验证”用“生长”数据构建一棵完全树Until 验证数据集合上的精度降低do:  For each 树中非叶结点n   临时修剪掉n下子树,用标号为主要分类的叶子代替   在验证集上计算该树的精度  修剪掉那些对精度影响最大的分支当训练集很小时,可能会严重损害分类精度最好能给定合适的结点数,达到最佳折中 连续属性用分区方法,将连续值映射为离散值结点分裂,以获得最大信息增益达到最大信息增益的单阈值分裂算法For each 连续特征 Ai 根据Ai的值对样本排序 For each 序列中的每对Xi,Xi+1   If Xi和Xi+1的分类不同     将Xi和Xi+1的中点作为可能的阈值进行检验,即例如:长度(L): 10  15  21  28  32  40  50  (已排序)     分类:    -   +   +   -   +   +   -检查阈值:L<12.5, L<24.5, L<30, L<45 替代属性选取启发策略(增益比率)信息增益缺点:偏爱那些有大量值的属性,产生很多小而纯的子集,如病人ID、姓名、日期等要降低这些情况下的增益首先计算与分类无关属性的信息量,即该属性的熵其中Si为S中具有属性A第i个值的子集。某属性按值分割样本越平均,则SplitInfo越大增益比率利用SplitInfo来避免选择这些属性 增益比率细述 然而,当|Si|=|S|时SplitInfo可能很小甚至为0,从而导致信息比率过大甚至溢出C4.5对此进行了改进,它计算每个特征的信息增益,对于超过平均增益的特征,再进一步根据增益比率来选取特征 缺失的属性值属性值可能未完全给出一种解决方法是根据已有样本属性值的先验概率来对样本计算属性值分布百分比在训练时,缺失的属性会按照其分布百分比逐个计算。例如,给定一个缺失了颜色属性值的正例,它将被视为0.6个red正例、0.2个blue正例和0.2个green正例。 测试时的值缺失若属性值未给出,则设定为??(通配符),然后多路径到达叶结点,最后计算分类结果的各分类权重例如,<big,??,circle>将得到0.6个正例,0.2+0.2=0.4个反例<big,red,??>将得到0.2个正例,0.5+0.3=0.8个反例<big,??,??>将得到0.6x0.2=0.12个正例,0.2+0.2+0.3+0.18=0.88个反例 属性开销有些领域中,某些属性比其它属性更容易获取其值(例如病人的体温比其胆固醇水平更容易得到)尽可能采用那些低开销的属性来分类在信息增益中增加属性开销是有效的:在不降低精度的同时降低了平均开销 递增式的决策树归纳ID4和ID5可以递增更新已有的树ID4有时会丢弃某些实例,不保证和历史训练样本一致ID5则保证和ID3的决策相同ID4速度快,但精度降低ID5速度较快且精度不变 决策树中的重复部分决策树比DNF更复杂,因为它常常存在重复部分范式必须分解为析取范式,导致了重复子树的出现解决:使用复杂特征或决策图构造性归纳:原子特征的逻辑组合或算术组合 边缘算法决策树构造性归纳的叠代算法边缘算法(总是沿着树的边缘走)Until 没有新的特征被创建或到达限定值do  使用当前的所有特征从训练集构造决策树 从边缘末端(正例)两个特征的联合来创建新特征 将这些新特征加入现有特征集中,同时扩展每个样本的描述以包含所有新特征 边缘示例多重模型学习概念的多重候选定义最终决策是基于多个学习模型的(加权)投票 装袋(Bagging)用训练集的不同样本来训练同一个学习者,来创建多重模型(Breiman,1996)给定训练集大小为n,通过从原始数据取样(用替换方法),创建m个不同的训练集(大小为n)用简单的投票方法来合并这m个模型可用于任何学习方法减少了不稳定学习算法的一般化错误,即当训练数据轻微改动时会导致决策结果剧烈变动的那些学习方法 引导(Boosting)另一个生成多重模型的方法——重复更改同一个学习算法的数据对弱学习算法(假设的精度只要超过1/2即可)能保证性能的改进对样本加权,每次叠代产生一个新的假设,对那些导致最终假设精度变差的样本重新加权基本算法给所有样本赋予一个初始权重For i from 1 to T do 从加权的样本中学习一个假设hi 减小那些与hi一致的样本的权重在测试时,每个假设会得到一个加权的投票(与训练数据上的精度成比例) 引导算法For D中的每个样本,令其权重wi=1/|D|For t from 1 to T do 从加权样本中学习一个假设ht 计算ht的误差εt,作为被错误分类样本的总权重 If εt >0.5 then 终止,else 继续 令βt= εt/(1- εt) 将ht正确分类出的样本的权重乘以βt 权重归一化以保证总和为1在测试时,每个假设ht获得投票的权重为log(1/ βt),票数最多的假设作为最终决策 多重模型的实验结果多决策树模型应用范围更广也更准确引导算法性能比装袋算法好引导算法偶尔也会降低性能

阅读全文(23355) | 回复(11) | 编辑 | 精华
回复:决策树学习
yizhibi(游客)发表评论于2012-4-13 11:12:31
请问您一下,weka中的logistic回归模型该如何使用啊?能不能举个例子。

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
回复:决策树学习
海潮(游客)发表评论于2008-8-20 18:51:46
您好,我是一名初学者,请问ID3算法在解决多类分类问题时,求熵的公式为?为什么大多数材料举例均为两类?
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
回复:决策树学习
ADILIYA(游客)发表评论于2007-11-1 20:07:43
您好,请问信息增益的值会是负的吗?能否给出证明呢。谢谢!
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
回复:决策树学习
月亮忘记了(游客)发表评论于2007-6-17 17:51:11
您好! 我想请教个问题:ID3、C4.5的时间复杂度是多少?如何计算?
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
回复:决策树学习
nini(游客)发表评论于2007-6-10 18:51:23
数据挖掘概念与技术一书中,7.3.6关于集成数据仓库技术和判定树归纳。这种集成具体是怎么操作的呢,导出了判定树以后,数据立方体的概念分层是怎样在属性上上卷或下钻的?是否需要导出不同概念层上的判定树呢?还是在原来导出的判定树上就可以实现上卷或下钻?
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
回复:决策树学习
ks(游客)发表评论于2007-4-9 22:19:15
能不能教我怎么用C编写CART算法?哪里可以找到相关的一些资料?
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
回复:决策树学习
sherman(游客)发表评论于2006-4-2 15:56:38
请教c4.5是怎样出理当类的类型为数值型数据的情况的呢?谢谢 以下为blog主人的回复:   关于C4.5算法,我原来只了解大体的思路,具体的细节没有深入研究。   关于它对数值型变量的处理,在我们以往的项目实施中,一般事先会对这些变量进行离散化处理,再提交给决策树算法来建立模型。按照挖掘专题的不同,进行相应的数据探索(比如查看数据分布、进行直方图分析等),并根据探索的结果对数值型变量进行切分。   在本帖给出的附件中,其实也对这种处理进行了说明,参见“连续属性”一节。   在《数据挖掘:概念与技术》一书中有简单介绍,在第7.3.4节中:======================================================= 7.3.4 基本判定树归纳的加强“对基本判定树归纳的加强有哪些?”业已提出了许多对7.3.1小节判定树归纳基本算法的加强。本小节,我们将讨论若干主要加强,其中一些结合到ID3的后继算法C4.5中。7.3.1小节的判定树归纳基本算法要求所有的属性是分类的或离散化的。可以修改该算法,允许属性具有整个离散区间或连续值。在这种属性A上的测试导致两个分枝,对应于条件A  V和A > V,其中V是A 的某个数值值。给定A的值v,确定V时考虑v-1个可能的分割。通常,考虑每对相邻值的中间值。如果这些值已预先排序,则只需要扫描一次这些值。信息增益度量有倾斜,它倾向于适合具有许多值的属性。已经提出了一些替代的方法,如增益率,它考虑每个属性值的概率。还有一些其它选择度量,包括Gini索引,2相依表统计和G-统计。已经提出了许多方法来处理遗漏的属性值。例如,属性A的遗漏值或未知值可以用A的最常见值替代。替换地,属性A的外观上的信息增益也可以根据A的值未知的样本百分比减少。这样,具有缺少值的样本“片段”可以在测试结点被划分到多个分枝。其它方法可能寻找A的最可能值,或使用A和其它属性的已知联系。 
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
决策树
侧俩(游客)发表评论于2006-2-21 20:38:10
决策树的结果是分布还是分布的变化率? 以下为blog主人的回复: 不太明白你的问题,决策树的结构就是树型结构,从根节点到每个叶节点都是一条决策路径,满足了路径上的所有条件后,就可以到达叶节点(决策的结果),同时也得到了这种决策的先验概率。 
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
» 1 2 »

发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)


站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.031 second(s), page refreshed 144298312 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号