计算机数学-(5).pptx

第5章 树,引言,树是图论中应用最广泛、最重要的子类之一。1847年，Gustav Kirchhoff（1824-1887）在有关电网的著作中首次使用了树，后来Arthur Cayley（1821-1895）重新发展并命名了树。现在，计算机科学广泛采用了树的概念。比如，在数据库系统中用树来组织信息，在编绎程序中用树表示源程序的语法结构，在最优化问题的求解中树也起着重要作用。本章主要介绍树的基本术语，树的子类（如根数和二叉树），以及树的应用。,例：2011年法网四强结果图，我国选手李娜获得最终法网冠军,5.1 树的概念,树是没有简单回路的连通无向图例：判断下图中的图哪些是树？为什么？,森林是每个连通分支都是树的无向图,5.1 树的概念性质,1、一个无向图是树当且仅当在它的每对顶点之间存在唯一简单路径2、带有n个顶点的树含有n-1条边3、树是边数最多的无回路图，树是边数最少的连通图4、n（n2）阶树T至少有2个叶子。,5.1 树的概念,根树是指定一个顶点作为根并且每条边的方向都离开根的树。,结点v的层数是从根结点到结点v的简单路径的长度。根树的深度是树的最大层数。,5.1 树的概念,例5.1.4如果把e指定为图5.1.5中树T的根结点，我们就得到如图5.1.5所示的根树T1。结点a，d，e，h，j的层数分别为2，1，0，2，3。树T1的深度为3。很显然，选择不同的根会产生不同的根树。,5.1 树的概念树模型,例5.1.5一个虚拟大学的行政结构图。,10.3.5 根树的应用,计算机的文件结构,练习：完成习题5.1的1-3题,5.1 树的概念霍夫曼（Huffman）编码,计算机中信息的表示和传输是通过编码来实现的。在计算机内部进行编码或表示字符的最常用方法是使用由符号0和1组成的定长二进制符号串。例如ASCII（美国标准信息交换码）采用7位二进制串来表示一个字符，,5.1 树的概念-最优树与哈夫曼算法,在计算机及通讯事业中，常用二进制编码来表示符号，称之为码字(codeword)。例如，可用00、01、10、11分别表示字母A、B、C、D。如果字母A、B、C、D出现的频率是一样的，传输100个字母用200个二进制位。但实际上字母出现的频率很不一样，如A出现的频率为50，B出现的频率为25，C出现的频率为20，D出现的频率为5。能否用不等长的二进制序列表示字母A、B、C、D，使传输的信息的二进制位尽可能少呢？事实上，可用000表示字母D，用001表示字母C，01表示B，1表示A。这样表示，传输100个字母所用的二进制位为35+320+225+150 = 175。这种表示比用等长的二进制序列表示法好，节省了二进制位。但当我们用1表示A，用00表示B，用001表示C，用000表示D时，如果接收到的信息为001000，则无法辨别它是CD还是BAD。因而，不能用这种二进制序列表示A、B、C、D，要寻找另外的表示法。,定义,设a1a2an-1an为长度为n的符号串，称其子串a1，a1a2，, a1a2an-1分别为a1a2an-1an的长度为1，2，n-1的前缀(Prefix)。 设A = b1, b2, , bm是一个符号串集合，若对任意bi, bjA，bibj，bi不是bj的前缀，bj也不是bi的前缀，则称A为前缀码(Prefixed Code)。若符号串bi(i = 1, 2, m)中，只出现0和1两个符号，则称A为二元前缀码(Binary Prefixed Code)。,1, 01, 001, 000是前缀码1, 11, 001, 0011不是前缀码。,用二元树产生二元前缀码,给定一棵二元树T，假设它有t片树叶。 设v是T任意一个分支点，则v至少有一个儿子至多有两个儿子。若v有两个儿子，则在由v引出的两条边上，左边的标上0，右边的标上1；若v只有一个儿子，在v引出的边上可标0也可标1。设vi为T的任意一片树叶，从树根到vi的通路上各边的标号组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码。,vi中的符号串的前缀均在vi所在的通路上，因而所得集合为二元(0和1组成)前缀码。,若T存在带一个儿子的分支点，则由T产生的前缀码不唯一，但T若为完全二元树，则T产生的前缀码就是唯一的了。,例,图中所示的二元树产生的前缀码为：1，00，010，011。因此用1表示A，用00表示B，用010表示 C，用011表示 即可满足要求。,当知道了传输的符号出现的频率时，如何选择前缀码，使传输的二进制位尽可能地少呢？先产生最优二元树T，然后用T产生二元前缀码。,最优树,定义 设有一棵二元树，若对其所有的t片叶赋以权值w1、w2、wt，则称之为赋权二元树(Power Binary Tree)；若权为wi的叶的层数为L(wi)，则称 为该赋权二元树的权；而在所有赋权w1、w2、wt的二元树中，W(T)最小的二元树称为最优树(Optimal Tree)。 1952年哈夫曼(Huffman)给出了求最优树的方法。该方法的关键是：从带权为W1+W2、W3、Wt(这里假设W1W2Wt)的最优树T中得到带权为W1、W2、Wt的最优树。,算法5.1.8 哈夫曼算法：,初始：令S = W1, W2, , Wt；从S中取出两个最小的权Wi和Wj，画结点vi，带权Wi，画结点vj，带权Wj。画vi和vj的父亲v，连接vi和v，vj和v，令v带权Wi+Wj；令S = (S -Wi, Wj)Wi+Wj；判断S是否只含一个元素？若是，则停止，否则转2。,例10.3.9,求带权7、8、9、12、16的最优树。,15,7,8,9,16,12,21,31,52,例,用机器分辨一些币值为1分、2分、5分的硬币，假设各种硬币出现的概率分别为0.5、0.4、0.1。问如何设计一个分辨硬币的算法，使所需的时间最少(假设每作一次判别所用的时间相同，以此为一个时间单位)？,所需时间：20.1+20.4+10.5 = 1.5(时间单位)。,例,已知字母A、B、C、D、E、F出现的频率如下：A30，B25，C20D10，E10，F 5构造一个表示A、B、C、D、E、F前缀码，使得传输的二进制位最少。解（1）求带权30,25,20,10,10,5的最优二元树T。（2）在T上求一个前缀码。,（3）设树叶vi带权为w100 = w，则vi处的符号串表示出现频率为w的字母。01，10，11，001，0001，0000为一前缀码，其中0000表示F，0001表示E，001表示D，01表示C，10表示B，11表示A。传输100个这样的字母所用的二进制位为：4(5+10)+310+2(20+25+30) = 240。,例：我们利用上面的霍夫曼码树对二进制位串01010111进行解码。,练习：完成课本习题5.1的4-9题,5.2 树的特征,我们可以把一个家谱树看成一个根树。如古希腊神话中诸神的家谱树的一部分,5.2 树的特征术语,阅读课本定义5.2.1理解父亲，祖先，孩子，子孙，兄弟，外部结点(叶子)，内部结点，子树的概念,例5.2.6设T是一个树，且有3个3度结点，1个2度结点，其余均为1度结点。那么该无向树共有多少个结点？对此，画出两棵不同的树。,练习：完成课本习题5.2,5.3 最小生成树生成树的概念,定义5.3.1如果树T是包含图G的所有结点的一个子图，那么就称树T是图G的一个生成树。,5.3 最小生成树生成树,判断下图中的图(b)、(c)、(d)、(e)是否是图(a)的生成树。,定理5.3.3图G有一个生成树T当且仅当G是连通的。,破圈法与避圈法,算法5.3.1 求连通图G = 的生成树的破圈法：每次删除回路中的一条边，其删除的边的总数为m-n+1。算法5.3.2 求连通图G = 的生成树的避圈法：每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。由于删除回路上的边和选择不构成任何回路的边有多种选法，所以产生的生成树不是惟一的。,例1,分别用破圈法和避圈法求下图的生成树。,1,2,3,4,5,6,分析 分别用破圈法和避圈法依次进行即可。用破圈法时，由于n = 6，m = 9，所以m-n+1 = 4，故要删除的边数为4，因此只需4步即可。用避圈法时，由于n = 6，所以n-1 = 5，故要选取5条边，因此需5步即可。,破圈法,避圈法,由于生成树的形式不惟一，故上述两棵生成树都是所求的。 破圈法和避圈法的计算量较大，主要是需要找出回路或验证不存在回路。,1,2,3,4,5,6,最小生成树,定义5.3.4 设G = 是连通的赋权图，T是G的一棵生成树，T的每个树枝所赋权值之和称为T的权(Weight)，记为w(T)。G中具有最小权的生成树称为G的最小生成树(Minimal Spanning Tree)。,一个无向图的生成树不是惟一的，同样地，一个赋权图的最小生成树也不一定是惟一的。,算法5.3.5 Kruskal算法,（1）在G中选取最小权边e1，置i = 1。（2）当i = n-1时，结束，否则转(3)。（3）设已选取的边为e1, e2, , ei，在G中选取不同于e1, e2, , ei的边ei+1，使e1, e2, , ei, ei+1中无回路且ei+1是满足此条件的最小权边。（4）置i = i+1，转(2)。,要点：在与已选取的边不构成回路的边中选取最小者。,在Kruskal算法的步骤1和3中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。,例2,用Kruskal算法求图中赋权图的最小生成树。,解 n=12，按算法要执行n-1=11次，,w(T) = 36。,算法5.3.5 Prim算法,（1）在G中任意选取一个结点v1，置VT = v1, ET = ，k = 1；（2）在V-VT中选取与某个viVT邻接的结点vj，使得边(vi, vj)的权最小，置VT = VTvj, ET = ET(vi, vj)，k = k+1；（3）重复步骤2，直到k = |V|。,要点：从任意结点开始，每次增加一条最小权边构成一棵新树。,在Prim算法的步骤2中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。,例3,用Prim算法求图中赋权图的最小生成树。,解 n = 7，按算法要执行n-1 = 6次，,w(T) = 25。,由Prim算法可以看出，每一步得到的图一定是树，故不需要验证是否有回路，因此它的计算工作量较Kruskal算法要小。,5.3 小结,树是不含回路的连通图。注意把握树的性质，特别是树中叶结点的数目及边数与结点数的关系：m = n-1；生成树是无向连通图是树的生成子图。注意把握所有连通图都有生成树，会使用避圈法、破圈法算法求生成树；最小生成树是赋权连通图的权值之和最小的生成树。会使用Kruskal算法和Prim算法求最小生成树。,5.3 最小生成树应用,例5 假设有5个信息中心A、B、C、D、E，它们之间的距离(以百公里为单位)如图所示。要交换数据，我们可以在任意两个信息中心之间通过光纤连接，但是费用的限制要求铺设尽可能少的光纤线路。重要的是每个信息中心能和其它中心通信，但并不需要在任意两个中心之间都铺设线路，可以通过其它中心转发。,分析 这实际上就是求赋权连通图的最小生成树问题，可用Prim算法或Kruskal算法求解。,解 求得图的最小生成树如图所示，w(T) = 15百公里。即按图的图铺设，使得铺设的线路最短。,练习：完成习题5.3,5.4 二叉树,定义5.4.1 二叉树是一棵根树，该树的每个结点可以没有孩子，可以有1个孩子，也可以有2个孩子。如果它仅有1个孩子，则该孩子必须被指定为左孩子或右孩子。若它有2个孩子，则一个被指定为左孩子，另一个被指定为右孩子。(即两个孩子是有序的),根结点,左子树,右子树,5.4 二叉树,基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点(以出度作为树结点的度)） 左子树和右子树次序不能颠倒。下面是两棵不同的树:,5.4 二叉树,练习：具有3个结点的二叉树共有几棵，试分别画出。,5.4 二叉树的性质,性质1：在二叉树的第i层上至多有(2i)个结点( i1)性质2：深度为 k 的二叉树至多有(2k+1-1)个结点（k1)。(例5.4.6)深度为 k 的二叉树的最大结点数目为二叉树中每层上的最大结点数之和，第1层到第k层的最大结点数之和为： 20+ 21 + 22+ + 2k = (1-2k+1)/(1-2) = 2k+1-1,性质3：对任何一棵二叉树 T，如果其外部结点数为 n0，内部结点即度为2的结点数为 n2，则 (n0=n2+1)。(即定理5.4.4),5.4 二叉树完全二叉树,完全二叉树是一棵二叉树，其每个结点要么有2个孩子，要么没有孩子。(也有很多教材完全二叉树定义不是这样的),5.4 二叉树,例5.4.5单循环淘汰赛是失败一场就被淘汰出局的比赛。其示意图是一棵完全二叉树（如图5.4.2）。比赛者的名字列于左侧，胜者的名字列于右侧，最后在树根上仅有一个胜者。若参赛者的数目不是2的幂次方，则会有一些参赛者直接进入下一轮比赛。在图5.4.2中参赛者7就直接进入下一轮。,容易证明，如果有n个参赛者参加单循环淘汰赛，则一共要进行n1场比赛，才能决出最后的胜者。因为每比赛一场淘汰一名选手，要淘汰n1名选手，就需要进行n1场比赛。,2022/7/8,5.4 二叉树应用,规定用树叶表示参加运算的元素，分支结点表示相应的运算。,(a+(bc)d-e)(f+g)+(hi)j,5.4 二叉树二叉查找树,定义5.4.7二叉查找树是一种二叉树，其中结点所存放的数据用下列方式进行组织：对树中某个结点v而言，其左子树中每个结点的数据都小于v中的数据；其右子树中每个结点的数据都大于v中的数据。,例5.4.8在下图5.4.4所示的4棵二叉树中，规定顺序是通常的数的大小顺序，问哪些树是二叉查找树？,例5.4.10按以下单词顺序构造二叉查找树 old，programmers，never，die，they， just，lose，their，memories,练习：完成习题5.4,5.5 决策树,定义 设有一棵根树，如果其每个分支点都会提出一个问题，从根开始，每回答一个问题，走相应的边，最后到达一个叶结点，即获得一个决策，则称之为决策树(Decision Tree)。 下面我们用决策树表示算法，并使得在最坏情形下花费时间最少。,例1 硬币问题,例10.3.13 现有5枚外观一样的硬币，只有1枚硬币与其它的重量不同。问如何使用一架天平来判别哪枚硬币是坏的，重还是轻？分析 用天平来称A和B两枚硬币，只有AB、A = B、AB三种可能的情形，因此可构造3元决策树来解决。,从根到叶就是一种求解过程，由于该树有10片叶子，因此最多有10种可能的解。又由于该树高为3，因此最坏情形下需要3次判别就能得到结论。,例2 用决策树给出对不同元素a1，a2，a3进行排序的算法。分析：因为a1，a2，a3排序共有3！=6种可能性，即6个树叶结点。 22623。即至少需要比较3次。,5.5 决策树数据挖掘中的应用(补充),这个世界上每天产生的新数据速度惊人Data Mining就是要从数据中挖出知识超出人的脑力所及的知识麻省理工学院科技评论: Data Ming 是改变这个世界的十大高新技术之一 决策树是数据挖掘的有力工具之一,60,数据挖掘简介,性别 年龄种族家庭人口家庭收入申请该校原因家庭住址 ,学校录取部门的困扰：新生录取以后会不会来报到？,61,数据挖掘简介,产品名称产品型号产品价格生产厂家生产国家出售地点出售日期,Wal-Mart的销售与供应商,62,数据挖掘简介,你能判定他/她买计算机的可能性大不大吗？,63,数据挖掘简介,1我们拥有什么: Huge amount of data (GTE:1TB/day)2.我们需要什么: Information and knowledge3. 我们应该怎么办: Data Mining,64,数据挖掘技术Neural Networks 计算机神经网络Decision trees决策树Regression methods Predicate logic,数据挖掘简介,各八显仙神过通海,65,决策树的用途,决策树是数据挖掘的有力工具之一,66,决策树的用途,假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？又：你需要多少有关这位客人的信息才能回答这个问题？,决策树可以帮助你解决好这个问题,67,决策树的用途,谁在买计算机？,他/她会买计算机吗？,68,决策树的用途,一棵很糟糕的决策树,69,决策树的建立- 决策树建立的关键,建立一个好的决策树的关键是决定树根和子树根的属性,ID3 信息量大小的度量,决策树算法,Shannon1948年提出的信息论理论。事件ai的信息量I（ ai ）可如下度量：,其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,.,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：,ID3 信息量大小的度量,决策树算法,上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时 =0,公式1,在决策树分类中，假设S是训练样本集合，|S|是训练样本数，样本划分为n个不同的类C1,C2,.Cn，这些类的大小分别标记为|C1|，|C2|，.,|Cn|。则任意样本S属于类Ci的概率为：,ID3 信息量大小的度量,决策树算法,Entropy（S，A）=（|Sv|/|S|）* Entropy（Sv）公式2,是属性A的所有可能的值v,Sv是属性A有v值的S子集|Sv|是Sv 中元素的个数；|S|是S中元素的个数。,ID3 信息量大小的度量,决策树算法,Gain（S，A）是属性A在集合S上的信息增益Gain（S，A）= Entropy（S） -Entropy（S，A） 公式3Gain（S，A）越大，说明选择测试属性对分类提供的信息越多,决策树算法,第1步计算决策属性的熵,决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641 S2（不买）= 383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537,决策树算法,第2步计算条件属性的熵,条件属性共有4个。分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。,决策树算法,第2-1步计算年龄的熵,年龄共分三个组： 青年、中年、老年青年买与不买比例为128/256S1(买)=128 S2（不买）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,决策树算法,第2-2步计算年龄的熵,年龄共分三个组： 青年、中年、老年中年买与不买比例为256/0S1(买)=256 S2（不买）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0,决策树算法,第2-3步计算年龄的熵,年龄共分三个组： 青年、中年、老年老年买与不买比例为125/127S1(买)=125 S2（不买）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157,决策树算法,第2-4步计算年龄的熵,年龄共分三个组： 青年、中年、老年所占比例青年组 384/1024=0.375中年组 256/1024=0.25老年组 384/1024=0.375计算年龄的平均信息期望E（年龄）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877G（年龄信息增益） =0.9537-0.6877 =0.2660 （1）,决策树算法,第3步计算收入的熵,收入共分三个组： 高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 (2),决策树算法,第4步计算学生的熵,学生共分二个组： 学生、非学生E（学生）=0.7811年龄信息增益=0.9537-0.7811 =0.1726 （3）,决策树算法,第5步计算信誉的熵,信誉分二个组： 良好，优秀E（信誉）= 0.9048信誉信息增益=0.9537-0.9048 =0.0453 （4）,决策树算法,第6步计算选择节点,年龄信息增益=0.9537-0.6877 =0.2660 （1）收入信息增益=0.9537-0.9361 =0.0176 （2）学生信息增益=0.9537-0.7811 =0.1726 （3）信誉信息增益=0.9537-0.9048 =0.0453 （4）,决策树算法,年龄,青年,中年,老年,买/不买,买,买/不买,叶子,决策树算法,青年买与不买比例为128/256S1(买)=128 S2（不买）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183,决策树算法,如果选择收入作为节点分高、中、低,平均信息期望（加权总和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591,I(0,128)=0 比例: 128/384=0.3333I(64,128)=0.9183 比例: 192/384=0.5I(64,0)=0比例: 64/384=0.1667,注意,决策树算法,年龄,青年,中年,老年,学生,买,信誉,叶子,否,是,优,良,买,不买,买/不买,买,叶子,叶子,叶子,决策树算法,ID3 决策树建立算法1 决定分类属性；2 对目前的数据表，建立一个节点N3 如果数据库中的数据都属于同一个类，N就是树叶，在树叶上 标出所属的类4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少 数服从多数的原则在树叶上标出所属类别5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作 为节点N的测试属性6 节点属性选定后，对于该属性中的每个值： 从N生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏 如果分支数据表非空，则运用以上算法从该节点建立子树。,决策树算法,Thank You！,