泉州自助建站系统,域名注册的流程是什么,深圳网站建设及推广服务公司,郓城做网站哪家好2012年8月26日决策树#xff08;Decision tree#xff09;决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式#xff0c;在决策树的内部结点进行属性值的比较#xff0c;并根据不同的属性值从…2012年8月26日 决策树Decision tree 决策树是以实例为基础的归纳学习算法。 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式在决策树的内部结点进行属性值的比较并根据不同的属性值从该结点向下分支叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则整个决策树就对应着一组析取表达式规则。1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要后来又提出了若干改进的算法其中SLIQ(super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法。 ID3算法是由Quinlan首先提出的。该算法是以信息论为基础以信息熵和信息增益度为衡量标准从而实现对数据的归纳分类。以下是一些信息论的基本概念 定义1若存在n个相同概率的消息则每个消息的概率p是1/n一个消息传递的信息量为Log2(n) 定义2若有n个消息其给定概率分布为P(p1,p2…pn)则由该分布传递的信息量称为P的熵记为 I(p)-(i1 to n求和)piLog2(pi)。 定义3若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck则识别T的一个元素所属哪个类所需要的信息量为Info(T)I(p)其中P为C1C2…Ck的概率分布即P(|C1|/|T|,…..|Ck|/|T|) 定义4若我们先根据非类别属性X的值将T分成集合T1,T2…Tn则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到即Info(Ti)的加权平均值为 Info(X, T)(i1 to n 求和)((|Ti|/|T|)Info(Ti)) 定义5信息增益度是两个信息量之间的差值其中一个信息量是需确定T的一个元素的信息量另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量信息增益度公式为 Gain(X, T)Info(T)-Info(X, T) ID3算法计算每个属性的信息增益并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点并以该节点的属性标记对该属性的每个值创建一个分支据此划分样本. 决策树的构造 这个数据集来自Mitchell的机器学习叫做是否去打网球play-tennis,以下数据仍然是从带逗号分割的文本文件复制到纪事本把后缀直接改为.csv就可以拿Excel打开 *play-tennis data其中6个变量依次为编号、天气{Sunny、Overcast、Rain}、温度{热、冷、适中}、湿度{高、正常}、风力{强、弱}以及最后是否去玩的决策{是、否}。一个建议是把这些数据导入Excel后另复制一份去掉变量的数据到另外一个工作簿即只保留14个观测值。这样可以方便地使用Excel的排序功能随时查看每个变量的取值到底有多少。*/ NO. , Outlook , Temperature , Humidity , Wind , Play 1 , Sunny , Hot , High , Weak , No 2 , Sunny , Hot , High , Strong , No 3 , Overcast , Hot , High , Weak , Yes 4 , Rain , Mild , High , Weak , Yes 5 , Rain , Cool , Normal , Weak , Yes 6 , Rain , Cool , Normal , Strong , No 7 , Overcast , Cool , Normal , Strong , Yes 8 , Sunny , Mild , High , Weak , No 9 , Sunny , Cool , Normal , Weak , Yes 10 , Rain , Mild , Normal , Weak , Yes 11 , Sunny , Mild , Normal , Strong , Yes 12 , Overcast , Mild , High , Strong , Yes 13 , Overcast , Hot , Normal , Weak , Yes 14 , Rain , Mild , High , Strong , No 这里我们先不讨论算法这里用的是ID3/C4.5把一棵决策树建立起来再说。我们要建立的决策树的形式类似于“如果天气怎么样去玩否则怎么着怎么着”的树形分叉。那么问题是用哪个属性即变量如天气、温度、湿度和风力最适合充当这颗树的根节点在它上面没有其他节点其他的属性都是它的后续节点。借用信息论的概念我们用一个统计量“信息增益”Information Gain来衡量一个属性区分以上数据样本的能力。信息增益量越大这个属性作为一棵树的根节点就能使这棵树更简洁比如说一棵树可以这么读成如果风力弱就去玩风力强再按天气、温度等分情况讨论此时用风力作为这棵树的根节点就很有价值。如果说风力弱再又天气晴朗就去玩如果风力强再又怎么怎么分情况讨论这棵树相比就不够简洁了。计算信息增益的公式需要用到“熵”Entropy。名词越来越多让我们通过手工计算记住它们的计算方法把Excel打开 1 计算熵 我们检查的属性是是否出去玩。用Excel对上面数据的play变量的各个取值排个序这个工作簿里把“play”这个词去掉一共是14条记录你能数出取值为yes的记录有9个取值为no的有5个我们说这个样本里有9个正例5 个负例记为S(9,5-)S是样本的意思(Sample)。这里熵记为Entropy(S),计算公式为 Entropy(S) -(9/14)*log(9/14)-(5/14)*log(5/14) 解释一下9/14是正例的个数与总记录之比同样5/14是负例占总记录的比例。log(.)是以2为底的对数我们知道以e为底的对数称为自然对数记为ln(.),lg(.)表示以10为底的对数。在Excel里我们可以随便找一个空白的单元格键入以下公式即得0.940 -(9/14)*LOG(9/14,2)-(5/14)*LOG(5/14,2) 这里LOG(9/14,2)中的“2”表示以2为底。类似地如果你习惯用Matlab做数学运算本公式为 -(9/14)*log2(9/14)-(5/14)*log2(5/14) 其中“2”的含义与上同。 总结在这个例子中我们的输出属性我们要检查的属性“play”只有两个取值同样地如果输出属性的取值大于2公式是对成的一样的形式连加就是找到各个取值的个数求出各自的比例。如果样本具有二元输出属性其熵的公式为 Entropy(S) -(p)*log(p)-(p-)*log(p-) 其中p、p-分别为正例和负例占总记录的比例。输出属性取值大于2的情况公式是对称的。 2 分别以Wind、Humidity、Outlook和Temperature作为根节点计算其信息增益 可以数得属性Wind中取值为Weak的记录有Normal的记录有8条其中正例6个负例2个同样取值为Strong的记录6个正例负例个3个。我们可以计算相应的熵为 Entropy(Weak)-(6/8)*log(6/8)-(2/8)*log(2/8)0.811 Entropy(Strong)-(3/6)*log(3/6)-(3/6)*log(3/6)1.0 现在就可以计算出相应的信息增益了 Gain(Wind)Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)0.940-(8/14)*0.811-(6/14)*1.00.048 这个公式的奥秘在于8/14是属性Wind取值为Weak的个数占总记录的比例同样6/14是其取值为Strong的记录个数与总记录数之比。 同理如果以Humidity作为根节点 Entropy(High)0.985 ; Entropy(Normal)0.592 Gain(Humidity)0.940-(7/14)*Entropy(High)-(7/14)*Entropy(Normal)0.151 以Outlook作为根节点 Entropy(Sunny)0.971 ; Entropy(Overcast)0.0 ; Entropy(Rain)0.971 Gain(Outlook)0.940-(5/14)*Entropy(Sunny)-(4/14)*Entropy(Overcast)-(5/14)*Entropy(Rain)0.247 以Temperature作为根节点 Entropy(Cool)0.811 ; Entropy(Hot)1.0 ; Entropy(Mild)0.918 Gain(Temperature)0.940-(4/14)*Entropy(Cool)-(4/14)*Entropy(Hot)-(6/14)*Entropy(Mild)0.029 这样我们就得到了以上四个属性相应的信息增益值 Gain(Wind)0.048 Gain(Humidity)0.151 Gain(Outlook)0.247 Gain(Temperature)0.029 最后按照信息增益最大的原则选Outlook为根节点。子节点重复上面的步骤。这颗树可以是这样的它读起来就跟你认为的那样 参考资料 1.王厚峰“机器学习‘课程讲义2007年春季学期北京大学软件与微电子学院 2.Mitchell,《机器学习》曾华军等译北京机械工业出版社2003 (2) C4.5算法 C4.5算法继承了ID3算法的优点并在以下几方面对ID3算法进行了改进 1) 用信息增益率来选择属性克服了用信息增益选择属性时偏向选择取值多的属性的不足 2) 在树构造过程中进行剪枝 3) 能够完成对连续属性的离散化处理 4) 能够对不完整数据进行处理。 C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点产生的分类规则易于理解准确率较高。其缺点是在构造树的过程中需要对数据集进行多次的顺序扫描和排序因而导致算法的低效。此外C4.5只适合于能够驻留于内存的数据集当训练集大得无法在内存容纳时程序无法运行。 (3) SLIQ算法 SLIQ算法对C4.5决策树分类算法的实现方法进行了改进在决策树的构造过程中采用了“预排序”和“广度优先策略”两种技术。 1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时都需要对训练集按照该属性的取值进行排序而排序是很浪费时间的操作。为此SLIQ算法采用了预排序技术。所谓预排序就是针对每个属性的取值把所有的记录按照从小到大的顺序进行排序以消除在决策树的每个结点对数据集进行的排序。具体实现时需要为训练数据集的每个属性创建一个属性列表为类别属性创建一个类别列表。 2)广度优先策略。在C4.5算法中树的构造是按照深度优先策略完成的需要对每个属性列表在每个结点处都进行一遍扫描费时很多为此SLIQ采用广度优先策略构造决策树即在决策树的每一层只需对每个属性列表扫描一次就可以为当前决策树中每个叶子结点找到最优分裂标准。 SLIQ算法由于采用了上述两种技术使得该算法能够处理比C4.5大得多的训练集在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。 然而它仍然存在如下缺点 1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。 2)由于采用了预排序技术而排序算法的复杂度本身并不是与记录个数成线性关系因此使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。 (4)SPRINT算法 为了减少驻留于内存的数据量SPRINT算法进一步改进了决策树算法的数据结构去掉了在SLIQ中需要驻留于内存的类别列表将它的类别列合并到每个属性列表中。这样在遍历每个属性列表寻找当前结点的最优分裂标准时不必参照其他信息将对结点的分裂表现在对属性列表的分裂即将每个属性列表分成两个分别存放属于各个结点的记录。 SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点若内存能够容纳下整个哈希表其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比当训练集很大时哈希表可能无法在内存容纳此时分裂只能分批执行这使得SPRINT算法的可伸缩性仍然不是很好。 其他资料 本文是《Mitchell机器学习》《JiaweiHan数据挖掘概念与技术》的学习笔记 概览一 1 决策树就是实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取树本身对应这些合取的析取。 2 决策树建立时使用统计测试来确定每一个实例属性单独分类训练样例的能力在每个结点选取能最好地分类样例的属性且从不回溯重新考虑以前的选择。因此决策树学习是一个自顶向下的贪婪搜索算法。 3 每一步都使用统计测试使决策树学习对错误有很好的健壮性。 4 决策树学习的假设空间包含所有的决策树它是关于现有属性的有限离散值函数的一个完整空间。每个有限离散值函数都可被表示为某个决策树。因此决策树学习(ID3)的归纳偏置来自它的搜索策略即较短的树比较长的树优先信息增益高的属性更靠近根结点的树优先。这种类型的偏置称为优选偏置或搜索偏置。而候选消除算法的归纳偏置来自它对搜索空间的定义被称为限定偏置或语言偏置。 5 奥坎姆剃刀优先选择拟合数据的最简单假设。 一个解释 找到一个短的但同时与训练数据拟合的假设的可能性较小不太可能是统计巧合。 两个难题 I 根据什么相信短描述的决策树组成的小假设集合比其它众多可定义的小假设集合更适当 II 假设的大小由学习器内部使用的特定表示决定。不同的内部表示方式据奥坎姆剃刀产生两个不同的假设。 6 处理不同代价属性 使属性代价参与属性选择度量如将信息增益除以属性代价。这在考虑获取属性的不同代价的现实条件时是很有用处的。 概览二 1 在决策树归纳分类之前假设数据是预处理过的。不可忽略地这其中包括数据清理相关分析数据变换与归约。具体实现及方法另述。 2 (离散)分类和数值预测是预测问题的两种主要类型决策树一般用于分类。 3 归纳决策树时对于树的每一层都需要扫描一遍D中的元组因此算法的计算复杂度为O(n*|D|*log|D|)。 4 决策树归纳的scalability 1SLIQ使用若干驻留磁盘的属性列表和单个驻留内存的类列表 2SPRINT使用另一种属性列表易于并行消除了所有内存限制但需要正比于训练集的散列树。 3RainForest对每个属性维护一个AVC属性-值-类集可以选择任何属性度量。 4BOAT使用称作bootstrap的统计学技术从子集构造多棵树后合并构造接近于真实树的新树。可使用二元分裂的属性选择度量如Gini指标。只需扫描训练集两次可以增量更新。 综述 1 属性选择度量信息增益ID3使用 I 熵(entropy)刻画了任意样例集的纯度熵值越大表示越不纯识别其中元组分类所需要的平均信息量就越大。公式如下 熵的最大可能为logc。信息论中熵的一种解释是确定要编码集合S中任意成员的分类所需要的最少二进制位数。所以底数都是2。 II 信息增益Gain(S,A)有几种解释 由于知道属性A的值而导致的期望熵减少 原来的信息需求与新的需求的差即信息需求的期望减少。 公式如下第二项描述的是每个子集的熵的加权和 2 属性选择度量增益率C4.5使用 I 信息增益度量存在一个内在偏置它偏袒具有较多值的属性。 II 分裂信息S关于属性A的各值的熵用来衡量属性分裂数据的广度和均匀性惩罚可取较多值的属性。公式如下 III 增益率 IV 增益率存在的问题当Si约等于S时分裂信息趋向于0GainRatio变得不稳定。可以先计算每个属性的增益仅对增益高过平均值的属性应用增益比率测试。 3 属性选择度量Gini指标CART使用 I Gini指标度量数据划分或训练元组集D的不纯度如下其中pi|C(i,D)|/|D| II 只考虑属性的二元划分。因此对于有v个值的属性A存在2^v-2中划分。从中选择该属性产生最小Gini指标的子集作为分裂子集。 III 对连续值属性考虑每对排序的相邻值之间的中点取作可能的分裂点。可以证明产生最大信息增益的分裂点必定位于这样的边界中。 4 树剪枝 (1) 当数据中有噪声或训练样例的数量太少时决策树归纳算法会出现过度拟合。另外决策树可能很大很复杂难以理解。因此需要修剪决策树。 (2) 两种常用的剪枝方法先剪枝(即提前停止树增长)后剪枝。对于前者精确地估计何时停止树增长非常困难一般进行统计测试来估计扩展一个特定的节点是否可能改善质量如用卡方测试统计显著性另外可以使用信息增益Gini指标及预定义的阈值。后剪枝更常用。 (3) 代价复杂度后剪枝(CART使用)。代价复杂度是树叶结点个数与错误率的函数使用与训练和测试集合完全不同的修剪验证集合来评估。 (4) 悲观剪枝C4.5使用。不需要剪枝集使用训练集评估错误率但是假定此估计精度为二项分布计算标准差对于一个给定的置信区间采用下界来估计错误率。虽然这种启发式方法不是统计有效的但是它在实践中是有效的。 (5) 规则后修剪。将决策树转化为等价的IF-THEN规则如何提取另述并尝试修剪每个规则的每个前件(preconditions)。这样的好处是使对于决策树上不同的路径关于一个属性测试的修剪决策可以不同。另外避免了修剪根结点后如何组织其子节点的问题。 (6) 以明确的标准来衡量训练样例和决策树的复杂度如最小描述长度准则MDL而不是根据估计的错误率。 问题 1 关于奥坎姆剃刀的第II个难题进化产生的内部表示使得学习算法的归纳偏置成为seft-fulfilling prophecy。只因为它改变内部表示比改变学习算法更容易。推理中尽是假设进化何以成立 2 证明决策树学习的时间复杂度为On*|D|*log|D| 3 信息论中的熵 4 为什么Gini指标只能用作二元划分 5 证明产生最大信息增益的分裂点必定位于相邻值之间的中点中 6 MDL准则如何用于树剪枝 http://www.cnblogs.com/zhaoqian/archive/2011/01/25/1944717.html http://www.docin.com/p-113903819.html 决策树构造法ID 如果学习的任务是对一个大的例子集作分类概念的归纳定义而这些例子又都是用一些无结构的属性值对来表示则可以采用示例学习方法的一个变种──决策树学习其代表性的算法是昆兰J.R.Quinlan1986提出的ID3。 ID3的输入是描述各种已知类别实例的列表。例子由预先定义的属性值对来表示。归纳推理产生的结果不是以往讨论的那种合取表达式而是一棵决策树也称判别树并可转而表示为决策规则的一个集合用它可正确地区分所有给定例子的类属。 树中的每一非叶节点对应一个需测试的属性每个分叉就是该属性可能的取值树的叶节点则指示一个例子事物的类别。ID3的显著优点是归纳学习花费的时间和所给任务的困难度取决于例子个数用来描述对象的属性数所学习概念的复杂度即决策树的节点数等仅成线性增长关系。当然ID3只能处理用属性-值对表示的例子。 在ID3中, 每一个例子用相同的一组属性来表示每一个属性又有自身的属性值集如颜色属性可取值是{红、绿、兰}等。构造决策树的目的是为了对事物作出正确的分类。决策树形式的分类规则适用于任何的对象集。如是空的那么它无需分类对应的决策树也为空如中的对象是同一类的那么决策树就一个叶节点即该类名如果集中的对象属于二个不同的类别那未我们可以选取一个对象的属性随后按其可能值把划分成一些不相交的子集C1C2…Cn其中Ci是含有所选属性的第个值的那些对象集。对每一个这样的子集又可以用同样的策略处理最后的结果是一棵树。 下面给出一个关于人分类的例子对象集并预先定义了指定的一组属性及其可取值高度{高矮}发色{黑色, 红色金色}和眼睛{兰色棕色}。这里将人分为两类分别以、来指示。 高度 发色 眼睛 类别 ─────────────────────────── 矮 黑色 兰色 高 黑色 兰色 矮 金色 兰色 高 金色 棕色 高 黑色 棕色 矮 金色 棕色 高 金色 兰色 高 红色 兰色 如我们首先选取发色为树的根节点即可获得图6.11所示的决策树。 相应于黑色红色和金色三值都有一个对象子集。随后我们再测试金色这一分支又按属性眼睛把其所含的对象集划分成兰色和棕色二类。至此所有叶结点相应的对象子集只含同一类的对象我们就可以用相应的类别名本例中的 和 -来取代各子集得到一决策树如图6.12所示。 一个对象所属类的判别从决策树的根开始首先依据根节点指示的属性发色选择与该对象属性值相应的分支然后以同样的方式进行下去, 一直到达叶节点。有时判别一个对象的类别由于从根到叶节点的路径较短只要测试少量的属性。如上例中若发色的值是黑色或红色则对象就可以直接归属相应的类别而不必再去判定其它属性的取值若为金色则再测试一次眼睛的值而不必考虑高度就可以进行判别。 若不存在这样的二个对象:它们在每个属性上都具有相同的值却属于不同的类别那么这种生成决策树的过程是可行的。产生这种归纳学习方法的关键在于如何选择一系列有用的属性来测试一个对象集以使生成的决策树是最小的。ID3采用了香农Shannon信息论中的方法以使分类时期望平均的测试次数最小。 一个决策树可看成一个信息源即给定一个对象可从决策树产生一个该对象所属类别的消息(比如类别或-)。决策树的复杂程度与借助这个消息所传递的信息量密切相关。若决策树传递的不同类别消息的概率用P (对应于类)和P-表示(对应于-类)那么这个消息的期望信息量为: - Plog2P - P-log2P- 对给定的物体集C我们可以把这概率近似地表示为相对频率, 此时P和P-分别等于C中类别为和-的对象所占的比例。 从C集对应的决策树中得到消息的期望信息量记为M(C)并定义M({})0。 对于上述例子C集有八个例子三个为五为-则 M(C) -3/8log23/8-5/8log25/8 0.954 bits 图6.13是一个局部决策树A为构造决策树时下一个可能选取的属性Ai为属性A的值且是互斥的。属性A将集合C划分为若干个子集合{C1C2...Cn}。设M(Ci)是值为Ai的子集Ci所对应决策树的期望信息量则确定以属性A作为树根的决策树的期望信息量B(C, A)可通过权值平均而得到: B(C, A)∑(A值为Ai的概率) * M(Ci) 同样我们把Ai的概率用相对比例来代替即在所有对象中具有Ai值所占的相对比例。 我们希望待选的测试属性能使决策树获得最大的信息增益即M(C)-B(C, A)为最大值。因为M(C)为判别一个对象的类属所要求的总的期望信息量B(C,A)为按属性A构造局部决策树后还需要的期望信息量。二者的差越大说明测试这个属性所能传递的信息量越大,则判别的速度也就越快。 例如图6.14中我们选取的属性为高度对高度值为高的分支的所需期望信息量为 -2/5log22/5-3/5log23/5 0.971 bits 同样对值为矮的分支为: -1/3log21/3-2/3log22/3 0.918 bits 则以属性高度作划分后进一步判别所需的期望信息量为 B(C,高度) 5/8 * 0.971 3/8 * 0.918 0.951 则测试这属性传递的信息为: M(C)-B(C,高度) 0.954 - 0.951 0.003 bits。 如果我们不是选择高度而选用属性头发如图6.12所示, 则有: B(C,头发) 3/8 * 0 1/8 * 0 4/8 * 1 0.5 bits 则测试属性头发获取的信息为M(C)-B(C,头发) 0.945 - 0.5 0.45 bits。 同样对属性眼睛测试获得信息为0.347bits。根据最大信息量原理,ID3就选取头发为决策树的根节点属性。 ID3通过不断的循环处理逐步求精决策树直到形成一棵完整的决策树即树的叶节点所对应的对象例子均属于同一类。 这篇文章也不错 http://blog.csdn.net/v_july_v/article/details/7577684 转载于:https://www.cnblogs.com/zhangleisanshi/p/5168991.html
