精华内容
下载资源
问答
  • 主要介绍了Python 3 使用Pillow生成漂亮的分形树图片,本文通过实例代码介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
  • ,二叉搜索,B,红黑树树

    摘要

    数据结构是什么?在计算机科学中的定义为:是计算机存储,组织数据的方式。数据结构就意味着接口和封装,数据结构要能够透过程序语言所提供的数据类型,引用以及其他操作实现,一个设计良好的数据结构可以在低的时间和空间复杂度下,解决场景的问题.在这篇文章中我们要着重介绍的是数这种数据结构,它是非常常见的一种数据结构,所以了解它是计算机学生的必修内功。顾名思义这个数据结构叫做树那么它和显示中的树存在着某种联系。我们现实中的树是自底向上逐渐分叉的,一个条主干可以有很多的分支。在计算机科学中的树也是这样的一个节点可以有很多的子节点。这里有点区别的是,为了方便人的阅读,就把根节点放到最上面。

    二叉搜索树

    二叉树

    在给二叉搜索树之前,先来给二叉一个定义:

    • 由一系列的节点,这些节点包含链接,这些节点可以为null,或者指向其他节点
    • 除了根节点以外,每个节点只能又一个父节点
    • 每个节点都只有左右连个链接分别指向自己的左节点,和右节点。

    其实在第三点,我们把,左节点,和右节点看作一个新的二叉树,这样的话一些搜素和插入操作就可以很好地使用迭代的算法来使用了,下图为一棵普通的二叉树:

    搜索树

    二叉搜索树(Binary Search Tree)它是一棵二叉树而且具有以下4个特点:

    • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
    • 任意节点的左、右子树也分别为二叉查找树;
    • 没有键值相等的节点。

    下面为python代码的实现

    class Node:
        def __init__(self,key,left=None,right=None):
            self.key = key
            self.left = left
            self.right = right
                
    class Tree:
        def __init__(self):
            self.root = None
            
        def add(self, x,listCompare2):
            node = Node(x)
            if self.root is None:
                self.root = node
                #print (self.root.key)
                return listCompare2
            else:
                y = self.root
                #print (y)
                while True:
                    #print(y.key)
                    if  y.key > node.key:
                       # print(y)
                        #listCompare2.append({node.key,y.key})
                        if y.left == None:
                            y.left = node
                            return listCompare2
                        else:
                            y = y.left
                    else:
                        if y.right == None:
                            listCompare2.append({y.key,node.key})
                            y.right = node
                            return listCompare2
                        else:
                            y = y.right
    

    从上面的程序我们可以看出,二叉树的实现(add)操作,它是和数据的排列顺序有关系的,在最好的情况下即二叉树为平衡二叉树的时候:这棵树的高度为:H = log(N);N为这个树的所有节点数。但是在最差的时候即插入时数据是有序的那么在这种情况下树的高度就是:N了
    这样二叉树的建立就影响到二叉树的基本操作:查询。它取决于书的结构了。

    B树

    从上面的二叉搜索树的例子可以看出,它的add和serach操作都是不稳定的,它在最坏的情况下的性能还是很糟糕的。于是人们就想建造出一个即稳定又高效率的数据结构,B树就呼之欲出了。我们都知道,到一棵二叉搜索树为平衡时,它的add和serach都是对数时间的,但是我们在构建树的时候保证树的完美平衡的代价很高,所有为了保证稳定和高效率,我们需要一些灵活性,因此在这里我们允许树中的一个节点保存多个键
    在维基百科中是这样定义B树的:是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树(binary search tree),可以拥有多于2个子节点。

    2-3树

    在这里就挑选最简单的B树来讲解,对于它的定义如下:
    2-3查找树或为一棵空树,或由以下的节点组成:

    • 2-节点,含有一个键(及其对应的值)和两个链接左链接指向的是2-3树中的键都小于该节点,右链接指向的是2-3树中的键都大于该节点
    • 3-节点,含有两个键(及其对于的值)和三个链接,左链接指向的是2-3树中的键都小于该节点,中链接指向的2-3树中键都位于该节点的俩个键之间,右链接指向的2-3树中的键都大于该节点
      从这里我们知道2节点就相当于二叉搜索树中的节点,但是它就比二叉搜索树多一个3-节点。下图就是一个简单的2-3树
      简单的2-3树

    理解2-3树主要的就是它是怎么自平衡的,自平衡的操作主要就是旋转操作。2-3树的插入大体可以分为两种,

    1. 向2-节点插入数据
    2. 向3-节点插入数据

    当我们先2-节点上插入数据的时候,这个操作是不会破坏2-3树的特性,因为向2-节点增加字段,相当于把这个2-节点变成3-节点。主要的操作就是向3-节点插入数据时,这个3-节点就变成了4-节点。就破坏了2-3树的特性。这个时候就需要一些操作来保证树的特性。这就是为什么它叫做自平衡树的原因。
    上面的第二种情况又可以细分为三种情况:

    1. case1:插入节点为根节点
    2. case2:插入节点的父节点为2-节点
      • 插入的节点是2-节点的左侧
      • 插入的节点在2-节点的右侧
    3. case3:插入节点的父节点为3-节点
      • 插入的节点在3-节点的左侧
      • 插入的节点在3-节点的中间
      • 插入的节点在3-节点的右侧

    下面这个图就是在这三种情况下树在做怎样的一种旋转,其实我们可以验证下,这三种情况下做出来的旋转,之后的状态还是符合红黑树的性质。这个图要好好理解它是红黑树的关键所在(引自《算法》第四版)。
    在这里插入图片描述

    上面的3种case可以包含所有的2-3树的插入操作。从上面的旋转操作都没有使2-3树变称不平衡(存在两个叶子节点s1,s2:他们的深度H(s1) != H(s2)),这个就是2-3树为自平衡树的原因。
    下面的这段代码就是上面6个操作的具体python实现

    class Node:
        def __init__(self, key1,key2 = None, key3 = None,left=None, right=None, right2 = None,middle = None, p=None):
            self.left = left
            ## 当节点为3-节点时,right为节点的右子树
            self.right = right
            ## 当节点为2-节点时middle为节点的右子树
            self.middle = middle
            ## 这个为临时4-节点的最右子树
            self.right2 = right2
            self.key1 = key1
            self.key2 = key2
            ## 这个节点是作为一个临时节点它用来存储从3-节点增加的那个节点
            self.key3 = key3 
            self.p = p
            ## 如果这个键为空的话那么它的父节点为它自己
            if key1 == "NIL":
                self.p = self
        def getChild(self,key):
            if key<self.key1:
                return self.left
            elif self.key2 is None:
                return self.middle
            elif key < self.key2:
                return self.middle
            else :
                
                return self.right
    class Tree:
        def __init__(self):
            nil = Node("NIL")
            self.root = nil
            self.nil = nil
        def get(self, key):
            if self.root is None:
                return None
            else:
                return self._get(self.root, key)
        def _get(self, node, key):
            if node is None:
                return None
            elif node.hasKey(key):
                return node
            else:
                child = node.getChild(key)
                return self._get(child, key)
        
        ## 直接插入不管fixup
        def insert(self , T ,x):
            if T.root.key1 == "NIL":
                T.root = Node(x)
            else:
                y = T.root
                while y.isLeaf() == False:
                    print ("y",y.key1)
                    y = y.getChild(x)
                    print ("x",y)
                if y.key2 is not None:
                    if x < y.key1:
                        y.key3 = y.key2
                        y.key2 = y.key1
                        y.key1 = x
                    elif (x>y.key1 and x<y.key2):
                        y.key3 = y.key2
                        y.key2 = x
                    else:
                        y.key3 = x
                    print ("y.p",y.p)
                    self.insertFixUp(T,y)
                else:
                    if x < y.key1:
                        y.key2 = y.key1
                        y.key1 = x
                    else :
                        y.key2 = x
        
        ## 插入的时候把4-节点变成符合2-3树的2/3节点
        def insertFixUp(self,T,x):
            ## case 1
            if x.p == None:
                print ("x == T.root")
                T.root = Node(x.key2)
                T.root.left = Node(x.key1)
                T.root.left.p = T.root
                T.root.middle = Node(x.key3)
                T.root.middle.p = T.root
        
                if T.root.left is not None:
                    T.root.left.left = x.left
                    if T.root.left.left is not None:
                        T.root.left.left.p = T.root.left
                    T.root.left.middle = x.middle
                    if T.root.left.middle is not None:
                        T.root.left.middle.p = T.root.left
                if T.root.middle is not None:
                    T.root.middle.left = x.right
                    if  T.root.middle.left is not None :
                         T.root.middle.left.p = T.root.middle
                    T.root.middle.middle = x.right2
                    if  T.root.middle.middle is not None :
                        T.root.middle.middle.p = T.root.middle
                return
            ## case 2
            if x.p.key2 is None:
                ## 在 左侧插入
                print ("case2执行")
                z = x.p
                print(x.key1)
                if x is x.p.left:
                    print ("case2 从左侧插入")
                    z.key2 = z.key1
                    z.key1 = x.key2
                    z.left = Node(x.key1)
                    z.right = z.middle
                    z.middle = Node(x.key3)
                    z.left.p = z
                    z.middle.p = z
                    if x.left is not None:
                        z.left.left = x.left
                        z.left.left.p = z.left
                    if x.middle is not None :
                        z.left.middle = x.middle
                        z.left.middle.p = z.left
                    if x.right is not None:
                        z.middle.left = x.right
                        z.middle.left.p = z.middle
                    if x.right2 is not None:
                        z.middle.middle = x.right2
                        z.middle.middle.p = z.middle
                ## 在右侧插入
                else:
                    print("右侧插入执行")
                    z.key2 = x.key2
                    z.middle = Node(x.key1)
                    z.right = Node(x.key3)
                    z.middle.p = z
                    z.right.p = z
                    if x.left is not None:
                        z.middle.left = x.left
                        z.middle.left.p = z.middle
                    if x.middle is not None:
                        z.middle.middle = x.middle
                        z.middle.middle.p = z.middle
                    if x.right is not None :
                        z.right.left = x.right
                        z.right.left.p = z.middle
                    if x.right2 is not None:
                        z.right.middle = x.right2
                        z.right.middle.p = z.right
                return
            if x.p.key2 is not None:
                z = x.p
                #在左侧插入
                if x is z.left:
                    z.key3 = z.key2
                    z.key2 = z.key1
                    z.key1 = x.key2
                    z.right2 = z.right
                    z.right2.p = z
                    z.right = z.middle
                    z.middle = Node(x.key3)
                    z.left = Node(x.key2)
                    z.left.p = z
                    z.middle.p = z
                    z.left.left = x.left
                    z.left.left.p = z.left
                    z.left.right = x.middle
                    z.left.right.p = z.left
                    z.middle.left = x.right
                    z.middle.left.p = z.middle
                    z.middle.right = x.right2
                    z.middle.right.p = z.middle
                # 在中间插入
                if x is z.middle:
                    z.key3 = z.key2
                    z.key2 = x.key2
                    z.right2 = z.right
                    z.right2.p = z
                    z.right = Node(x.key3)
                    z.right.p = z
                    z.right.left = x.right
                    z.right.left.p = z.right
                    z.right.right = x.right2
                    z.right.right.p = z.right
                    z.middle = Node(x.key1)
                    z.middle.p = z
                    z.middle.left = x.left
                    z.middle.left.p = z.middle
                    z.middle.right = x.middle
                    z.middle.right.p = z.middle
                # 从右侧插入
                if x is z.right:
                    z.key3 = x.key2
                    z.right2 = Node(x.key3)
                    z.right2.p = z
                    z.right2.left = x.right
                    z.right2.right = x.right2
                    if z.right2.left is not None:
                        z.right2.left.p = z.right2 
                    if z.right2.right is not None:
                        z.right2.right.p = z.right2
                    z.right = Node(x.key1)
                    z.right.left = x.left
                    z.right.right = x.middle
                    if z.right.left is not None:
                        z.right.left.p = z.right
                    if z.right.left is not None:
                        z.right.right.p = z.right
            self.insertFixUp(T,z)
    

    2-3树的一些性质

    它的所有叶子结点的高度是一样的:

    这点不难得到,我们在上一些中知道,2-3树的所有插入操作都不会使这种情况发生:存在两个节点s1和s2 使得他们的高度:H(s1) !=H(s2)

    search和add的操作时间复杂度为O(log(N))

    要搜素一个键是否存在,我们先将它和根结点中的节点比较,如果相等,查找命中;否则我们就根据查找的结果找到相应的区间的链接,并递归地继续查找。如果查找到叶子结点还没有查找到就表示这个值在2-3树中不存在,所以查找的时间复杂度和树的高度成线性关系,而树的高度在为 l o g 3 ( n ) &lt; = H ( n ) &lt; = l o g 3 ( n ) log_3(n) &lt;= H(n) &lt;= log_3(n) log3(n)<=H(n)<=log3(n) 所以2-3树的查找的时间复杂度是对数级别的。同理add操作也是指数级别的;

    相近的数大体在同一个或者相近的叶子节点中(这个是B+树,非叶子结点不存储数据的特性了)

    这个特性提供B+树作为数据库常用的索引的原因了,这里就不细讲了,大体的逻辑就是,数据库是外部存储器,它不像内存一样,读取一个树的时间复杂度为1,它需要操作磁头,而操作磁头是一个物理过程,很耗费时间。所以希望从外部磁盘中读取数据都是顺序读取的,这样的话就减少了移动磁盘的操作了,加上局部性原理(当一个值被用到的时候,那么它边上的数很大概率都会使用到,所以,磁盘的读写都会使用预读),而且在数据库的应用场景来说,一般执行SQL都是查询相近位置的数据:比如在where条件后面加上大于或者小于号,这也是为什么在Innodb中不使用hash索引的原因,因为hash索引虽然查找单个数据的时间复杂度是O(1)的但是它们之间数据是无序的。在外部存储的索引中B+树是很常见的一种

    红黑树

    从B树到红黑树

    我们上一节学了B树,也讲解了一个B树的例子:2-3树,现在我们把这个放开一点,允许每个节点存放三个数值,那么这个这个时候就会变成2-3-4树了,但是从上面的2-3树我们可以看到,这个B树实现起来很复杂,而且它也没有一般二叉树的简单,从本质上讲:一个红黑树都有对应的2-3-4树。
    RED-BLACK TREE 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的,他称之为"对称二叉B树",它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的:它可以在O( log n) 时间内做查找,插入和删除,这里的n是树中元素的数目1

    用途和好处

    红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用(real time application)中有价值,而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值;例如,在计算几何中使用的很多数据结构都可以基于红黑树。

    红黑树的定义

    为什么一个二叉树,会与B树等价呢?其中比较特别的就是红黑是的定义来约束的:

    • 节点是红色或黑色。
    • 根结点是黑色的
    • 所有叶子节点都是黑色的(叶子结点是NIL节点)
    • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
    • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

    这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树
    这个特性是怎么维持的呢?原因就在于第四个和第五个约束条件。当根结点到一个叶子结点的路径为红黑搭配着前行,那么他的高度最大为2倍的黑色节点的数量;当根节点到某个叶子节点的路径全为黑色节点的时候那么高度最小为1倍的黑色节点树。所以这颗树的最大高度与最小高度相差不会超过两倍。

    红黑树的构建

    红黑树的构建也是数据插入其中的过程。我们约定插入的数据都是红色的,插入红色的就不会破坏红黑树的第五个特性,下面是插入数据的一些情况:
    这里要使用到红黑树的一个特性 当一叶子节点为红色的时候,那么它的兄弟节点只能为红色,或者为空;当一个节点为红色时,那么它的父节点为黑色

    以下流程图是以插入的父节点为祖父节点的左节点做例子的,当为右节点,只需把左旋和右旋改变即可

    Created with Raphaël 2.2.0 Start 插入节点为红色 父节点为红色 叔节点为红色 把父节点,叔节点,祖父节点颜色改变 (把root节点变成黑色)End 祖父节点,父节点和 插入节点在同一直线上 右旋 左旋 直接插入 yes no yes no yes no

    这样一直循环,直到插入的节点为root节点:

    from graphviz import Digraph
    import time
    
    dot = Digraph(comment='Red Black Tree')
    
    class Node:
        def __init__(self, key, left=None, right=None, color=None, p=None):
            self.left = left
            self.right = right
            self.color = color
            self.key = key
            self.p = p
            if key == "NIL":
                self.p = self
    
        def LeftRotate(self, T, x):
            y = x.right
            x.right = y.left
            if y.left != T.nil:
                y.left.p = x
            y.p = x.p
            if x.p == T.nil:
                T.root = y
            elif x == x.p.left:
                x.p.left = y
            else:
                x.p.right = y
            y.left = x
            x.p = y
    
        def RightRotate(self, T, x):
            y = x.left
            x.left = y.right
            if y.right != T.nil:
                y.right.p = x
            y.p = x.p
            if x.p == T.nil:
                T.root = y
            elif x == x.p.left:
                x.p.left = y
            else:
                x.p.right = y
            y.right = x
            x.p = y
    
        def RBInsert(self, T, z):
            y = T.nil
            x = T.root
            while x != T.nil:
                y = x
                if z.key < x.key:
                    x = x.left
                else:
                    x = x.right
            z.p = y
            if y == T.nil:
                T.root = z
            elif z.key < y.key:
                y.left = z
            else:
                y.right = z
            z.left = T.nil
            z.right = T.nil
            z.color = "RED"
            self.RBInsertFixUp(T, z)
    
        def TreeHeight(self, T, z):
            if z == T.nil:
                return 0
            lh = self.TreeHeight(T, z.left)
            rh = self.TreeHeight(T, z.right)
            if lh > rh:
                return lh + 1
            return rh + 1
    
        def RBInsertFixUp(self, T, z):
            while z.p.color == "RED":
                if z.p == z.p.p.left:
                    y = z.p.p.right
                    if y.color == "RED":
                        z.p.color = "BLACK"
                        y.color = "BLACK"
                        z.p.p.color = "RED"
                        z = z.p.p
                    elif z == z.p.right:
                        z = z.p
                        self.LeftRotate(T, z)
                    z.p.color = "BLACK"
                    if z.p.p != T.nil:
                        z.p.p.color = "RED"
                        self.RightRotate(T, z.p.p)
                else:
                    y = z.p.p.left
                    if y.color == "RED":
                        z.p.color = "BLACK"
                        y.color = "BLACK"
                        z.p.p.color = "RED"
                        z = z.p.p
                    elif z == z.p.left:
                        z = z.p
                        self.RightRotate(T, z)
                    z.p.color = "BLACK"
                    if z.p.p != T.nil:
                        z.p.p.color = "RED"
                        self.LeftRotate(T, z.p.p)
            T.root.color = "BLACK"
    
        def RBTransplant(self, T, u, v):
            if u.p == T.nil:
                T.root = v
            elif u == u.p.left:
                u.p.left = v
            else:
                u.p.right = v
            v.p = u.p
    
        def TreeMinimum(self, T, z):
            if z.left != T.nil:
                return self.TreeMinimum(T, z.left)
            else:
                return z
    
        def RBDeleteFixUp(self, T, x):
            while x != T.root and x.color == "BLACK":
                if x == x.p.left:
                    w = x.p.right
                    if w.color == "RED":
                        w.color = "BLACK"
                        x.p.color = "RED"
                        self.LeftRotate(T, x.p)
                        w = x.p.right
                    if w !=T.nil :
                        if w.left.color == "BLACK" and w.right.color == "BLACK":
                            w.color = "RED"
                            x = x.p
                        elif w.right.color == "BLACK":
                            w.left.color = "BLACK"
                            w.color = "RED"
                            self.RightRotate(T, w)
                            w = x.p.right
                        w.color = x.p.color
                        x.p.color = "BLACK"
                        w.right.color = "BLACK"
                        self.LeftRotate(T, x.p)
                    x = T.root
                else:
                    w = x.p.left
                    if w.color == "RED":
                        w.color = "BLACK"
                        x.p.color = "RED"
                        self.RightRotate(T, x.p)
                        w = x.p.left
                    if w.right.color == "BLACK" and w.left.color == "BLACK":
                        w.color = "RED"
                        x = x.p
                    elif w.left.color == "BLACK":
                        w.right.color = "BLACK"
                        w.color = "RED"
                        self.LeftRotate(T, w)
                        w = x.p.left
                    w.color = x.p.color
                    x.p.color = "BLACK"
                    w.left.color = "BLACK"
                    self.RightRotate(T, x.p)
                    x = T.root
            x.color = "BLACK"
    
        def RBDelete(self, T, z):
            y = z
            yOriginalColor = y.color
            if z.left == T.nil:
                x = z.right
                self.RBTransplant(T, z, z.right)
            elif z.right == T.nil:
                x = z.left
                self.RBTransplant(T, z, z.left)
            else:
                y = self.TreeMinimum(T, z.right)
                yOriginalColor = y.color
                x = y.right
                if y.p == z:
                    x.p = y
                else:
                    self.RBTransplant(T, y, y.right)
                    y.right = z.right
                    y.right.p = y
                self.RBTransplant(T, z, y)
                y.left = z.left
                y.left.p = y
                y.color = z.color
            if yOriginalColor == "BLACK":
                self.RBDeleteFixUp(T, x)
    
        def InOrderTraversal(self, T, s, A):
            if s == T.nil :
                return
            if s.left != T.nil:
                self.InOrderTraversal(T, s.left, A)
            A.append(s)
            if s.right != T.nil:
                self.InOrderTraversal(T, s.right, A)
        
        def printTree(self, T, y, dot):
            if(y != T.nil):
                dot.node(str(y.key), str(y.key), color=y.color)
                if (y.left != T.nil):
                    dot.node(str(y.left.key), str(y.left.key), color=y.left.color)
                    dot.edge(str(y.key), str(y.left.key))
                    dot = self.printTree(T, y.left, dot)
                if (y.right != T.nil):
                    dot.node(str(y.right.key), str(y.right.key), color=y.right.color)
                    dot.edge(str(y.key), str(y.right.key))
                    dot = self.printTree(T, y.right, dot)
            return dot
        
    class Tree:
        def __init__(self):
            nil = Node("NIL", color="BLACK")
            self.root = nil
            self.nil = nil
    
    ##os.chdir("/Users/wujiahui/")
    T = Tree()
    B = [11, 2, 14, 1, 7, 15, 5, 8, 4]
    BB = [26]
    i = 0
    for j in B:
        dot = Digraph(comment='Red Black Tree')
        T.root.RBInsert(T, Node(j))
        dot = T.root.printTree(T, T.root,dot)
        dot.render('test-output/'+str(i), view=False)
        i = i+ 1
    ## 把生成的pdf文件转成jpg的文件
    from wand.image import Image
    def convert_pdf_to_jpg(filename):
        pdf_list = []
        os.chdir(filename)
        for i in os.listdir():
            if ".pdf" in i:
                pdf_list.append(i)
        sorted(pdf_list)
        t = 0
        print(pdf_list)
        for i in pdf_list:
            with Image(filename=i) as img :
                with img.convert('jpeg') as converted:
                    converted.save(filename=i.split(".")[0]+'.jpg')
                    t = t+1
    convert_pdf_to_jpg(os.getcwd())
    
    ## 把生成的jpg文件生成gif的动图
    import matplotlib.pyplot as plt
    import imageio,os
    images = []
    images.append(imageio.imread('8.jpg'))
    filenames=sorted((fn for fn in os.listdir('.') if fn.endswith('.jpg')))
    for filename in filenames:
        images.append(imageio.imread(filename))
    imageio.mimsave('gif.gif', images,duration=1,loop=1)
    

    下图就是插入序列[11,2,14,1,7,15,5,8,4]生成的gif图片:
    在这里插入图片描述

    ps:当在高并发的情况下,建议使用skiplist。


    1. 维基百科:红黑树 ↩︎

    展开全文
  • 决策算法原理以及决策规则生成方法 决策是一种可解释性较强的策略分析工具。creditmodel提供了分类回归和条件推断两种决策生成和提取规则的方法。 每一个风险管理人员都应该掌握使用决策发现规则和对...

    决策树算法原理以及决策树规则生成方法

    决策树是一种可解释性较强的策略分析工具。creditmodel提供了分类回归树和条件推断树两种决策树生成和提取规则的方法。

    每一个风险管理人员都应该掌握使用决策树发现规则和对进行客户分群的方法。

    决策树实质上是IF-THEN规则的集合,这种规则与人类进行决策的行为习惯不谋而合,这使得决策树具有很强的可解释性。另外,我们可以将决策树模型进行可视化,更能有效地帮助我们分析和解决问题。
    强可解释性和易于可视化使得决策树模型在金融领域、健康医疗领域、工业生产和制造、天文学和分子生物学得到了广泛应用等。

    决策树的基本原理

    决策树是什么?

    决策树是数据科学领域最为经典的模型之一,也是一种应用非常广泛的分类方法。

    在日常生活中,我们经常会通过对一系列问题的判断来进行决策。例如,风险投资、相亲择偶、医生问诊,其实都是一个决策的过程。

    医生会通过观察、询问、体检来获得患者的基本症状,然后选择不同的维度,依据自己的经验规则,对患者的病情进行诊断。

    在银行贷款时,银行的信贷审批员也需要根据借贷人的基本信息如收入、教育程度、婚姻状态等信息对是否放贷进行决策。

    男女相亲时,双方可能会根据对方的外貌、教育程度、收入、性格等信息,决策是否进一步交往。

    如果女方比较看重男方的收入和学历,则女方判断是否约会依据的规则可能有:

    规则1:若男方收入高,则约。

    规则2:若男方收入中等且为本科或研究生学历,则约

    规则3:若男方收入中等且为高中及以下学历,则不约

    规则4:若男方收入低,则不约。

    这样四条规则就可以把是否交往这个问题从收入和教育程度两个维度进行了划分,这些几条决策规则可以用一个树形结构表示可以表示,如下图所示。
    在这里插入图片描述
    医生、天使投资人、信贷审批员、找对象的女生头脑里都有一些专家规则,这些规则往往是通过非常多的案例归纳或者其他人的言传身教逐渐形成的。但是,很多很多时候,我们并没有这样的专家决策系统,而只有数据。如果你是一个女生,注册了某个婚恋网站的会员,婚介一次性给你推荐了10个备胎,如下表所示,你选择与其中5个人约会,另外5个你选择不约。

    对象编号收入水平教育程度颜值年龄身高是否约会
    1研究生28178不约
    2本科中等35185
    3高中及以下中等30170不约
    4中等高中及以下28175不约
    5本科40165不约
    6中等本科27180
    7中等高中及以下25182不约
    8中等研究生中等50168
    9中等研究生38177
    10高中及以下24172

    于是,我们从收入水平、教育程度、颜值外貌、年龄、身高以及你的决策结果几个维度收集到了这些人的数据,我们能否从这些数据中能否学习到一些规则,构建一个交往决策系统,决定你会与哪些人约会,然后更精准地给你推荐相亲对象呢?这就是决策树所要解决的问题。那么如何根据已有数据生成决策树呢?这就是下一节所要讲的内容。

    决策树的生成

    决策树中的每一个非叶子节点(如收入,教育程度)代表在某个特征上的一次判断。每一次判断都包含两个层次的问题:

    • 一是对哪个特征进行判断,例如对收入进行判断。
    • 二是在该特征上进行怎样的判断,收入“高”?收入“低”?收入“中等”?。

    树中的叶子节点(如约,不约)代表决策的结果,决策结果是根据树的根节点到该叶子节点的路径上的一系列判断来决定的。

    决策树的生成一般是从根节点开始,选择对应特征,然后选择节点对应特征的分割点,再根据分割点分裂节点。

    对于离散型特征,根据取值进行分裂,如相亲对象这一数据集中的“颜值”是一个离散型的特征,其有三个取值——“高、中、低”,那么根节点就分裂成三个子节点。

    对于连续型特征,则需要根据取值的分割点,来分裂子节点,例如“身高”这一特征,可以选择 170 170 170作为分割点。
    在这里插入图片描述

    总而言之,决策树通过选择特征和对应分裂点生成多个子节点,当某一个节点中的取值只属于某类别(或方差较小)时,那么就不再进一步分裂子节点。

    核心问题:如何选择节点的特征以及特征分割点?

    要回答上述问题,我们首先介绍不纯度的概念(所谓的纯与不纯,就是你理解的那个“纯”)。

    不纯度(impurity): 表示落在当前节点的样本类别分布的均衡程度,如果类别一致,那么不纯度为0。

    在这里插入图片描述
    如上图所示,叶子节点 t 1 t_1 t1 t 3 t_3 t3是比较纯的,叶子节点 t 2 t_2 t2就不那么纯了。

    我们根据不纯度的下降程度来选择特征和对应的分裂点。

    假设在节点分裂前的相亲对象的数据集为 D 0 = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } D_0=\{1,2,3,4,5,6,7,8,9,10\} D0={1,2,3,4,5,6,7,8,9,10},编号代表的是每一个相亲对象。 接下来,我们根据“收入水平”和“教育程度”这两个特征为例,来说明如何选择特征。

    根据收入水平的取值“高”、“中”、“低”,将数据集分裂为三部分,分别为 D 1 D_1 D1 D 2 D_2 D2 D 3 D_3 D3,记为 D 123 D_{123} D123,教育程度分裂后的子节点数据集分别为 D 4 D_4 D4 D 5 D_5 D5 D 6 D_6 D6,记为 D 456 D_{456} D456

    假设 Imp ( ⋅ ) \text{Imp}(\cdot) Imp()为节点的不纯度。收入水平分裂节点前后的不纯度的下降值为 Imp ( D 0 ) − Imp ( D 123 ) \text{Imp}(D_0) - \text{Imp}(D_{123}) Imp(D0)Imp(D123)。 教育程度分裂节点前后,不纯度的下降值为 Imp ( D 0 ) − Imp ( D 456 ) \text{Imp}(D_0) - \text{Imp}(D_{456}) Imp(D0)Imp(D456)。 然后,比较收入水平和教育程度分裂前后不纯度下降值的大小,选择下降值更大的特征作为最优的分裂方式。

    从上图可以直观看出,选择收入水平的不纯度下降是最大的。

    如何度量不纯度呢?

    那么,究竟如何度量节点的不纯度呢?不同决策树算法有不同的衡量指标。下面介绍三种常见的节点不纯度度量方法:

    • 基尼指数(Gini index)
    • 信息熵(Entropy)
    • 误分率(Misclassification error)

    基尼指数(分割前)

    基尼指数是衡量一个国家或地区居民之间的贫富差距的指标,常用来判断社会财富分配的公平程度,这一指标实质上是反映社会中各个收入水平的人群数量分布的均衡程度。

    同理,我们可以借用Gini指数来反映决策树子节点中不同类别样本分布的均衡程度,即不纯度。

    假设数据集一共有 C C C类, p ( C ∣ t ) p(C|t) p(Ct)是节点 t t t中第 c c c类样本的相对频率,则节点 t t t的Gini指数为
    Gini ( t ) = 1 − ∑ c = 1 c [ p ( C ∣ t ) ] 2 \text {Gini}(t) = 1- \sum_{c=1}^c [p(C|t)]^2 Gini(t)=1c=1c[p(Ct)]2
    根据基尼指数的计算公式,我们可以知道,当节点中各个类别的样本比例一致时,即均匀分布,Gini指数取得最大值 ( 1 − 1 C ) (1 - \frac{1}{C}) (1C1),节点不纯度最大;当节点中的样本全部属于一个类别时,Gini指数等于0,节点不纯度也最小。

    相亲对象数据集的结果变量是否约会,有两个类别——约与不约,故$ C = 2 。 我 们 可 以 根 据 一 个 节 点 。我们可以根据一个节点 t$中不同类别样本的数量来计算Gini指数。

    节点编号约样本数不约样本数
    t 0 t_0 t055
    t 1 t_1 t120
    t 2 t_2 t232
    t 3 t_3 t303
    t 4 t_4 t413
    t 5 t_5 t521
    t 6 t_6 t621

    我们将 t 0 t_0 t0作为根节点,我们可以根据基尼指数的计算公式,计算出分裂前的根节点的基尼指数,总样本为10个,约与不约各占5个,则 Gini ( t 0 ) = 1 − ( ( 5 10 ) 2 + ( 5 10 ) 2 ) = 0.500 \text{Gini}(t_0)=1 - \left( \left(\frac{5}{10}\right)^2 + \left(\frac{5}{10}\right)^2 \right) = 0.500 Gini(t0)=1((105)2+(105)2)=0.500

    若按照“收入水平”分裂根节点,则3个叶子节点的基尼指数计算如下:

    $\text{Gini}(t_1) = 1 - \left( \left(\frac{2}{2}\right)^2 + \left(\frac{0}{2}\right)^2 \right) = 0 $

    $\text{Gini}(t_2) = 1- \left( \left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2 \right) = 0.480 $

    $\text{Gini}(t_3) = 1- \left( \left(\frac{0}{3}\right)^2 + \left(\frac{3}{3}\right)^2 \right) = 0 $

    若按照“教育程度”分裂根节点,则3个叶子节点的基尼指数计算如下:

    Gini ( t 4 ) = 1 − ( ( 1 4 ) 2 + ( 3 4 ) 2 ) = 0.375 \text{Gini}(t_4) = 1- \left( \left(\frac{1}{4}\right)^2 + \left(\frac{3}{4}\right)^2 \right) = 0.375 Gini(t4)=1((41)2+(43)2)=0.375

    $\text{Gini}(t_5) = 1- \left( \left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 \right) = 0.444 $

    $\text{Gini}(t_6) = 1- \left( \left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 \right) = 0.444 $

    我们假设n为父节点 t t t中样本数量,节点 t t t经过某种方式分裂后生成了 K K K个子节点, n k n_k nk为第 k k k个子节点 t k t_k tk的样本数量。以每个子节点包含的样本数量占比作为权重,对子节点的Gini指数加权求和,就可以得到特征分裂后的Gini指数:
    Gini split = ∑ k = 1 K n k n Gini ( t k ) \text{Gini}_{\text{split}} = \sum_{k=1}^{K} \frac{n_k}{n} \text{Gini}(t_k) Ginisplit=k=1KnnkGini(tk)
    则“收入水平”分裂后的Gini指数为:
    $\text{Gini}_{\text{split}}=\frac{2}{10}\times 0+\frac{5}{10}\times 0.480+\frac{3}{10}\times 0=0.240 $

    对于不同的分裂方式,我们总是选择使得Gini指数下降值( Gini ( t 0 ) − Gini split \text{Gini}(t_0) - \text{Gini}_{\text{split}} Gini(t0)Ginisplit)最大的分裂方案,则按“收入水平”分裂的Gini指数下降值为 Gini ( t 0 ) − Gini split = 0.500 − 0.240 = 0.260 \text{Gini}(t_0) - \text{Gini}_{\text{split}} = 0.500 - 0.240 = 0.260 Gini(t0)Ginisplit=0.5000.240=0.260

    则“教育程度”分裂后的Gini指数为:
    Gini split = 4 10 × 0.375 + 3 10 × 0.444 + 3 10 × 0.444 = 0.417 \text{Gini}_{\text{split}}=\frac{4}{10}\times 0.375+\frac{3}{10}\times 0.444+\frac{3}{10}\times 0.444 = 0.417 Ginisplit=104×0.375+103×0.444+103×0.444=0.417

    则按“教育程度”分裂的Gini指数下降值为 Gini ( t 0 ) − Gini split = 0.500 − 0.417 = 0.083 \text{Gini}(t_0) - \text{Gini}_{\text{split}} = 0.500 - 0.417 = 0.083 Gini(t0)Ginisplit=0.5000.417=0.083

    特征“收入水平”的Gini指数下降值最大,所以我们最终选择“收入水平”进行第一次分裂。

    我们使用收入水平对根节点进行第一次分裂之后,发现收入水平为“中”的节点还是不够“纯”,我们需要对这个叶子节点进行分裂,这时选择特征和分割点与分裂根节点的方法是一样的,这样最终叶子节点只包含同一类样本,最终节点的不纯度都为0,则停止分裂,由此得到最终的完整决策树。如下图所示:

    在这里插入图片描述
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xQzQdpkM-1593945767410)(dt_cheat_1537000750954_5d14.jpg)]

    信息熵

    信息熵这个词是Shannon(香农)从热力学中借用过来的一个概念,用以度量信息的不确定度。我们可以使用信息熵来度量一个节点样本分布的不纯度。
    假设数据集一共有 C C C类, p ( C ∣ t ) p(C|t) p(Ct)是节点 t t t中第 c c c类样本的相对频率,则节点 t t t的信息熵为:

    Entropy ( t ) = − ∑ c = 1 c p ( C ∣ t ) log ⁡ 2 p ( C ∣ t ) \text{Entropy}(t) = - \sum_{c=1}^{c} p(C|t) \log_2 p(C|t) Entropy(t)=c=1cp(Ct)log2p(Ct)
    Entropy ( t ) = − ∑ c = 1 c p ( C ∣ t ) log ⁡ 2 p ( C ∣ t ) \text{Entropy}(t) = - \sum_{c=1}^{c} p(C|t) \log_2 p(C|t) Entropy(t)=c=1cp(Ct)log2p(Ct)
    当节点中的样本均匀分布在每一个类别时,信息熵取得最大值 log ⁡ 2 C \log_2 C log2C,表示节点的不纯度最大。 当一个节点的所有的样本都属于某一个类别时,信息熵为 0 0 0,这时该节点的不纯度最小。根节点的信息熵为 $\text{Entropy}(t_0) = \frac{5}{10}\log_2 \frac{5}{10} - \frac{5}{10} \log_2\frac{5}{10} = 1 $
    对于收入水平的三个节点的信息熵的计算如下:
    $\text{Entropy}(t_1) = -\frac{2}{2}\log_2 \frac{2}{2} - \frac{0}{2} \log_2\frac{0}{2} = 0 $

    $\text{Entropy}(t_2) = - \frac{3}{5} \log_2 \frac{3}{5}- \frac{2}{5} \log_2 \frac{2}{5} = 0.971 $

    $\text{Entropy}(t_3) = - \frac{0}{3} \log_2 \frac{0}{3} - \frac{3}{3}\log_2 \frac{3}{3} = 0 $

    $\text{Entropy}(t_4) = -\frac{1}{4}\log_2 \frac{1}{4} - \frac{3}{4} \log_2\frac{3}{4} = 0.811 $

    $\text{Entropy}(t_5) = - \frac{1}{3} \log_2 \frac{1}{3}- \frac{2}{3} \log_2 \frac{2}{3} = 0.918 $

    Entropy ( t 6 ) = − 1 3 log ⁡ 2 1 3 − 2 3 log ⁡ 2 2 3 = 0.918 \text{Entropy}(t_6) = - \frac{1}{3} \log_2 \frac{1}{3} - \frac{2}{3}\log_2 \frac{2}{3} = 0.918 Entropy(t6)=31log23132log232=0.918

    上述计算中我们定义 0 log ⁡ 2 0 = 0 0\log_2 0 = 0 0log20=0。 基于节点信息熵的定义,我们可以计算节点分裂前后的信息熵的下降值,称为**信息增益**(Information Gain):
    InfoGain = Entropy ( t 0 ) − ∑ k = 1 K n k n Entropy ( t k ) \text{InfoGain}= \text{Entropy}(t_0) - \sum_{k=1}^{K} \frac{n_k}{n}\text{Entropy}(t_k) InfoGain=Entropy(t0)k=1KnnkEntropy(tk)
    收入水平分裂方案的
    InfoGain = 1 − ( 2 10 × 0 + 5 10 × 0.971 + 3 10 × 0 ) = 0.5145 \text{InfoGain}=1 - (\frac{2}{10}\times 0+\frac{5}{10}\times 0.971+\frac{3}{10}\times 0 )=0.5145 InfoGain=1(102×0+105×0.971+103×0)=0.5145

    教育程度分裂方案的
    InfoGain = 1 − ( 4 10 × 0.811 + 3 10 × 0.918 + 3 10 × 0.918 ) = 0.1248 \text{InfoGain}=1 - (\frac{4}{10}\times 0.811+\frac{3}{10}\times 0.918+\frac{3}{10}\times 0.918 )= 0.1248 InfoGain=1(104×0.811+103×0.918+103×0.918)=0.1248

    我们挑选使得信息增益最大的特征进行分裂,所以挑选收入水平对根节点进行分裂。

    信息增益有一个很大的缺点就是倾向于分裂很多样本数量很少的叶子节点,这样特别容易造成过拟合(模型在训练集上表现很好,在验证集上效果差)。为了解决这个问题,我们可以使用子节点的样本数量作为分裂信息对信息增益进行修正。

    n n n 为节点 t 0 t_0 t0的样本数, n k n_k nk t 0 t_0 t0分裂生成的子节点 t k t_k tk的样本数。则分裂信息为
    SplitInfo = − ∑ k = 1 K n k n log ⁡ 2 ( n k n ) \text{SplitInfo}= - \sum_{k=1}^{K} \frac{n_k}{n} \log_2 \left( \frac{n_k}{n} \right) SplitInfo=k=1Knnklog2(nnk)

    我们用信息增益除以分裂信息就得到信息增益率(Information Gain Ratio):
    InfoGainRatio = InfoGain SplitInfo = Entropy ( t 0 ) − ∑ k = 1 K n k n Entropy ( t k ) − ∑ k = 1 K n k n log ⁡ 2 ( n k n ) \text{InfoGainRatio} = \frac{\text{InfoGain}}{\text{SplitInfo}} = \frac{\text{Entropy}(t_0) - \sum\limits_{k=1}^{K} \displaystyle\frac{n_k}{n} \text{Entropy}(t_k)}{ - \sum\limits_{k=1}^{K} \displaystyle \frac{n_k}{n} \log_2 \left( \displaystyle\frac{n_k}{n} \right)} InfoGainRatio=SplitInfoInfoGain=k=1Knnklog2(nnk)Entropy(t0)k=1KnnkEntropy(tk)

    使用信息增益率代替信息增益来平均分裂的好坏,能够避免分裂很多样本很少的子节点。

    误分率

    误分率是另外一种度量节点不纯度的方法。 假设数据集一共有 C C C类,在节点 t t t中第 c c c类数据的相对频率为 p ( c ∣ t ) p(c|t) p(ct),则节点 t t t的误分率为
    Error ( t ) = 1 − max ⁡ ( p ( 1 ∣ t ) , p ( 2 ∣ t ) , … , p ( C ∣ t ) ) \text{Error}(t) = 1 - \max \left(p(1|t),p(2|t),\ldots, p(C|t)\right) Error(t)=1max(p(1t),p(2t),,p(Ct))
    误分率所代表的含义为,当按照多数类来预测当前节点样本的类别时,被错误分类的数据的比例。 当样本均匀地分布在每一个类别时,误差率取得最大值 ( 1 − 1 C ) (1 - \frac{1}{C}) (1C1),说明不纯度最大。 当样本都属于某一个类别时,误分率取得最小值 0 0 0,说明不纯度最小。
    对于表2中的3个示例节点,其误分率的计算如下:
    Error ( t 1 ) = 1 − max ⁡ ( 2 2 , 0 2 ) = 0 \text{Error}(t_1) = 1 - \max\left(\frac{2}{2}, \frac{0}{2}\right) = 0 Error(t1)=1max(22,20)=0
    Error ( t 2 ) = 1 − max ⁡ ( 3 5 , 2 5 ) = 0.400 \text{Error}(t_2) = 1 - \max\left(\frac{3}{5}, \frac{2}{5}\right) = 0.400 Error(t2)=1max(53,52)=0.400
    Error ( t 3 ) = 1 − max ⁡ ( 0 3 , 3 3 ) = 0. \text{Error}(t_3) = 1 - \max\left(\frac{0}{3}, \frac{3}{3}\right) = 0 . Error(t3)=1max(30,33)=0.
    对于二分类问题,假设正类样本的相对频率为 p p p,则负类样本的相对频率为 1 − p 1-p 1p
    此时,上述三种不纯度度量指标分别为
    Gini ( p ) = 2 p ( 1 − p ) \text{Gini}(p) = 2p(1-p) Gini(p)=2p(1p)
    Entropy ( p ) = − p log ⁡ 2 p − ( 1 − p ) log ⁡ 2 ( 1 − p ) \text{Entropy}(p) = -p \log_2 p - (1-p)\log_2 (1 - p) Entropy(p)=plog2p(1p)log2(1p)
    Error ( p ) = 1 − max ⁡ ( p , 1 − p ) \text{Error}(p) = 1 - \max(p, 1-p) \\\\ Error(p)=1max(p,1p)

    不纯度度量小结

    Gini、信息熵、误分率是最为经典的不纯度度量方法。当子节点的样本相对频率为0或者1的时候,表示该节点样本类别一致,则不纯度都为0。而子节点的样本相对频率在0.5附近时,表示该节点样本类别均匀分布,此时,三种度量方法都达到最大值。

    常见的决策树算法

    从特征类型、不纯度度量或变量以及分割的选取方法和子节点分裂数量等维度研究者提出了很多决策树生成算法。本节我们对ID3、C4.5、CART和条件推断树这四种经典的决策树算法进行介绍。

    ID3 和 C4.5

    ID3(Iterative Dichotomiser 3)算法开创了决策树的先河。该算法使用信息熵度量节点不纯度,使用信息增益评价节点分裂好坏。然而,ID3算法只能处理离散型特征,对于连续型特征则通过枚举所有取值来分裂节点。由于ID3使用信息增益作为节点分裂的评价标准,该算法倾向于选取值比较多的特征并倾向于分裂很多样本数量很少的叶子节点,容易造成过拟合。

    C4.5算法改进了ID3的上述缺点:

    • 把每个分裂节点的样本量考虑进来,使用信息增益率来代替信息增益作为节点分裂评价标准,避免分裂较多的样本量少的子节点以及选择那些取值较多的特征。
    • 通过分裂阈值来处理连续型特征,如身高,如果选取分裂阈值为170,则会分为两个子节点>170,<=170。

    然而不论是ID3还是C4.5只能解决分类问题,而无法解决回归问题。

    分类回归树(CART)

    CART算法(Classification And Regression Tree,CART)既能解决分类问题又能解决回归问题。

    • 解决分类问题时,节点不纯度采用Gini指数来度量,节点分裂评价采用Gini指数下降值。
    • 解决回归问题实,节点不纯度采用目标特征的方差来度量,节点分裂评价标准采用方差下降值。

    CART算法每次只分裂成两个子节点。

    • 对于连续型特征,通过分裂阈值分裂成两个子节点,如身高,>170,<=170。

    • 对于离散型特征,CART不再根据特征的所有取值分裂子节点,而是每次选择一个取值,根据是否为该取值来分裂节点。 例如,对于“收入水平”其取值范围为 { 高 , 中 , 低 } \{\text{高},\text{中},\text{低}\} {,,}。 选取 { 高 } \{\text{高}\} {}这一取值进行分裂,则会根据“收入水平高”和“收入水平不高”将节点分裂成两个子节点。

    条件推断树(Conditional Inference Trees)

    条件推断树(Conditional Inference Trees)与经典的决策树类似,但根据统计检验确定自变量和分割点的选择,而不是度量不纯度。 显著性检验是置换检验

    即先假设所有自变量与因变量相互独立,在对因变量和每个自变量进行卡房检验,计算出所有自变量的卡方值。选择p值小于阈值的自变量作为分裂特征,并将与因变量相关性最强的自变量作为根节点的分裂变量。自变量选择好后,用置换检验来选择分割点:选取一个划分点将一个自变量划分为两个部分,如果这两个部分有显著差异,则根据该分割点划分数据集。

    与CART树类似,条件推断树每次也只分裂成两个子节点,但条件推断树不需要剪枝,因为阀值就决定了模型的复杂程度。所以如何决定阀值参数是非常重要的。

    决策树算法总结

    从特征类型、不纯度度量或变量以及分割的选取方法和子节点分裂数量等维度对上述三种常见的决策树算法进行了归纳总结。

    算法特征类型目标类型变量和分割的选取子节点数量
    ID3离散型离散型不纯度度量:信息增益K>=2
    C4.5离散型、连续型离散型不纯度度量:信息增益率K >=2
    CART离散型,连续型离散型、连续型不纯度独立:GINI指数、方差K = 2
    条件推断树离散型,连续型离散型基于显著性检验K =2

    决策树的剪枝

    决策树如果不剪枝,就会生成非常复杂的树,这容易导致过拟合,即在训练集的预测准确率高,但是在验证集准确率低。因此在实际应用中,过于复杂的决策树性能往往很差。
    在这里插入图片描述
    我们需要使用剪枝(pruning)的方法来控制决策树生长过于复杂。根据剪枝策略是在决策树生成前还是生成后,可以分为两种:预剪枝(prepruning)和后剪枝(postpruning)。

    • 预剪枝是我们事先设置一个不纯度下降的阈值,如果子节点的不纯度下降小于该阈值,则停止分裂。
    • 后剪枝是指建立完整的决策树之后,再根据实际情况对决策树进行剪枝。
    • 预剪枝非常简单,但是后剪枝效果更好。我们往往要根据不同的数据集,综合使用两种剪枝策略。

    那么如何对决策树进行剪枝呢?

    具体剪枝操作之前,我们需要定义判断整棵决策树优劣的指标,用以判断是否要进行具体剪枝操作。我们将其称为整体损失函数。

    假设数据有 C C C种类别,某一棵决策树 T T T包含 ∣ T ∣ |T| T个节点,其中节点 t t t中的样本量为 n t n_t nt。设 Imp ( t ) \text{Imp}(t) Imp(t)为节点 t t t的不纯度度量方法(例如基尼、信息熵和误分率),那么损失函数可表示为:
    Cost α ( T ) = ∑ t = 1 ∣ T ∣ n t Imp ( t ) + α ∣ T ∣ \text{Cost}_\alpha(T) = \sum_{t=1}^{|T|} n_t \text{Imp}(t) + \alpha |T| Costα(T)=t=1TntImp(t)+αT
    这一损失函数包含两项:第一项表示模型对训练集的拟合度,第二项是模型复杂度。两者是此消彼长的关系。

    我们最小化这个总体的损失函数,可以对拟合度和复杂度做一个权衡(即偏差和方差的tradeoff)。复杂度的控制参数 α \alpha α,代表了我们对生成复杂决策树的惩罚力度。

    决策树分析

    决策树实质上是IF-THEN规则的集合,这种规则与人类进行决策的行为习惯不谋而合,这使得决策树具有很强的可解释性。另外,我们可以将决策树模型进行可视化,更能有效地帮助我们分析和解决问题。
    强可解释性和易于可视化使得决策树模型在金融领域、健康医疗领域、工业生产和制造、天文学和分子生物学得到了广泛应用等。

    剩余内容:
    决策树分析
    决策树生成和提取风险策略规则实操——基于creditmodel

    请扫码关注阅读:
    在这里插入图片描述
    关注hansenmode,给你更多的分享。

    展开全文
  • 红黑已经有很长的历史,在许多现代编程语言的符号表中都有使用,但是其缺点也很明显,其代码实现过于繁杂。因此出现的红黑的修改版——左倾红黑 左倾红黑的代码实现相比于典型的红黑来说非常简介,但是...

    红黑树已经有很长的历史,在许多现代编程语言的符号表中都有使用,但是其缺点也很明显,其代码实现过于繁杂。因此出现的红黑树的修改版——左倾红黑树

    左倾红黑树的代码实现相比于典型的红黑树来说要简单不少,但是国内论坛好像并没有一个对于左倾红黑树相对系统的介绍,因此我找到了左倾红黑树的论文并将其整理翻译,以供学习

    由于过于繁杂,因此翻译的时候未对性能分析部分进行翻译,在这里提供原文地址

    在阅读本文前读者需要详细的了解二叉搜索树(BST)、红黑树、2-3树及2-3-4树

    由于能力有限,因此翻译的时候难免有不准确的地方,这个翻译仅供学习参考

    论文地址:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282

    左倾红黑树
    罗伯特塞奇威克
    计算机科学系
    普林斯顿大学
    普林斯顿,新泽西州08544

    简介

    在用于实现平衡搜索的红黑树模型现在遍布我们的计算基础设施,在许多标准教科书中都有对红黑树的描述,是C++,Java,Python,BSD Unix等许多现代系统中符号表实现的基础数据结构。但是,其中许多实现牺牲了一些原始设计目标,因此设计一种新的模式是有价值的。

    在这篇论文中,描述了一种新的红黑树变体,它满足了许多原始设计目标,并且导致插入/删除的代码简单的多,仅需要常用实现代码的四分之一。

    所有红黑树都是基于2-3树或2-3-4树的变种,使用红色链接绑定到三节点或四节点。新代码基于三个概念的组合:

    1:使用递归实现

    2:要求所有三节点向左倾斜

    3:在树的上面执行旋转(在执行递归之后)

    这些想法不仅能生成简单的代码,而且还能统一算法:例如在2-3树的左倾版本和2-3-4树中的自顶向下的版本在一行代码的位置不同

    具体来说,在由一个N个键构成的左倾红黑2-3树种,一个搜索操作需要检查lgN - 0.5个节点,树的平均高度约为2ln n

    在LLBR(左倾红黑树)中由许多吸引人的特性:

    1:实验研究未能将这些算法与最优算法区分开

    2:它可以通过向标准BST(二叉搜索树)算法添加几行代码来实现。

    3:与散列表不同,他们支持有序操作,如:SELECT,RANK,RANGE搜索

    因此LLRB树对于各种符号表应用程序都很有用,并且是未来软件库中作为符号表基础的主要候选对象

    介绍

    我们在本文中关注的是包含通用键和关联值得符号表中提供以下操作的有效实现的目标:

    1:搜索/获取与给定键关联的值

    2:将键值对插入符号表中

    3:使用符号表中给定的键删除键值对

    4:当插入操作涉及表中已有的键时,我们将该键与指定的新值关联,因此表中没有重复的键

    我们进一步假设键是可比较的:我们有一个比较操作可以确定一个给定的键是否小于,等于,或大于另一个给定的键,这样我们就可以保留实现有序关联数组的能力,我们可以支持搜索、范围搜索和类似的操作。

    红黑树最重要的特征之一是他们不会增加搜索的开销,这是最常用的操作。因此,红黑树是C++,Java,Python,BSD Unix和许多其他系统中符号表实现的基础数据结构,为什么要重新审视这样一个成功的数据结构?在实现红黑树的时候,实际的代码很难维护并在新系统中重用,因为它很长,在典型的实现代码有100 - 200行代码,教科书中很少有完整实现。在本文中,我们提出了一种可以大大减少所需代码量的方法。为了证明这一点,我们提出一个完整的Java实现,包括三个简短使用的方法,为标准BST代码添加3行代码以进行插入,使用5行代码删除最大值,以及额外30行删除代码

    旋转和颜色翻转

    观察红黑树算法的一种方法是在插入和删除操作下维护以下不变的属性:

    1:从跟到低的路径不包含两个连续的红色链接

    2:每个路径上黑色链接的数量是相同的

    这些不变量限制了有N个节点的红黑树每条路径长度不会2lgn,这种最糟糕的情况发生在一个节点都是黑色的树中

    平衡树算法用于在插入和删除下保持平衡的基本操作称为旋转。

    在红黑树的前提下,这些操作很容易理解为将红色链接向左倾斜的3节点转换为向右倾斜和反向倾斜的3节点所需的转换

    旋转操作显然保留了上述两个不变量,在红黑树中,我们还使用一种称为颜色翻转(color flip)的简单操作。就2-3-4树而言,颜色翻转是必不可少的操作:它对应于分割4节点并将中间节点传递给父节点,颜色翻转显然不会改变从跟到底的任何路径上黑色链接的数量,但是它可能在树中引入两

    个连续的红色链接,必须进行更正

    红黑树算法在是否以及何时进行旋转和颜色翻转方面存在差异,以便维护上面的不变量

    左旋(Left rotate)

    在这里插入图片描述

    右旋(Right rotate)

    在这里插入图片描述

    颜色翻转

    在这里插入图片描述

    该串代码将节点h及h的两个孩子颜色翻转,变为与之前相反的颜色。具体的Node类型会在后面阐述

    左倾红黑树

    代码的起点是标准BST的Java实现,如下面的代码所示。在下面的代码中使用泛型以一种类型安全的方式实现,如果不使用泛型则代码是标准的,可以轻松的翻译成其他语言或应用于不需要泛型类型的特定应用程序。

    在目前的上下文中,实现的一个重要特性是insert()的实现是递归的:每个递归都以一个链接(link)作为参数并返回一个链接,该链接用于重置从该链接获取的字段(这么说很抽象,原文大概原意就是每次递归获得一个新的节点,用这个新的节点再次进行递归)。对于标准的BST,除了树的底部,参数和返回值是相同的。这里的代码(insert())用于插入新节点。对于红黑树,这个递归有助于简化代码

    除此之外,对于search()操作也可以使用递归实现。但是这里并不会使用递归实现,因为这个操作属于典型的程序内部循环,实现红黑树算法的基础实在这段代码中添加旋转和颜色翻转操作。以便维护树中的平衡不变量

    在本文的代码中,我们展示了可以通过以下方式来大大减少需要考虑的情况:

    1:要求3节点总是向左倾斜(并且4节点是平衡的)

    2:在递归调用之后,在树的路径上进行旋转

    向左倾斜的要求给出了红黑树和2-3-4树之间的1-1对应关系,并减少了需要考虑的情况数量。

    循环向上旋转策略通过一种自然方式组合各种情况简化了代码(以及我们对它的理解),这两种方法并不是什么新方法,但是二者结合在一起在减少代码数量方面却出奇的有效。

    自顶向下的2-3-4树插入一个新节点,我们翻转颜色以分割在树下的路径上遇到的任何4节点并并进行旋转以平衡4节点(消除在树上出现的连续的红色链接)。这种方法是很自然的,因为分裂4节点以确保搜索不会在4节点上终止,意味着可以通过附加红色链接添加新节点,并平衡4节点数量,平衡4节点的三种方式如下面的图片所示。如果传递的红色连接恰好在3节点中向右倾斜,我们在遇到它时会纠正这种情况

    2-3树值得注意的时,在上面描述的自上而下的2-3-4树实现中,将颜色翻转移动到最后,产生了2-3树的实现,我们将通过颜色翻转,向树传递红色连接,以及在树中移动时以完全相同的方式处理这样做的效果

    在左倾红黑树中传递一个红色节点

    在这里插入图片描述

    public class LLRB<Key extends Comparable<Key>, Value> {   
    
    	private static final boolean RED   = true;  
    	private static final boolean BLACK = false;
    	private Node root;
    	private class Node{     
    		private Key key;     
    		private Value val;     
    		private Node left, right;      
    		private boolean color;      //用一位字段表示颜色
    		Node(Key key, Value val){         
    			this.key = key;  
    			this.val = val;        
    			this.color = RED;     //新节点总是红色
    
    		}   
    	}
    
    	public Value search(Key key){      
    
    		Node x = root;     
    		while (x != null){        
    			int cmp = key.compareTo(x.key);         
    			if (cmp == 0) return x.val;         
    			else if (cmp < 0) x = x.left;         
    			else if (cmp > 0) x = x.right;      
    		}      
    		return null;   
    	}
    	
    	public void insert(Key key, Value value){       
    		root = insert(root, key, value);       
    		root.color = BLACK;  
    	}   
    
    	private Node insert(Node h, Key key, Value value){       
    		if (h == null) return new Node(key, value);
    		if (isRed(h.left) && isRed(h.right)) colorFlip(h);  //这一行开始	
    		int cmp = key.compareTo(h.key);  
    		if (cmp == 0) h.val = value;       
    		else if (cmp < 0) h.left =  insert(h.left, key, value);      
    		else h.right = insert(h.right, key, value);
    		if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);       
    		if (isRed(h.left) && isRed(h.left.left)) h =rotateRight(h);  //到这里运行结束时,得到2-3树
    		return h;   
    	} 
    } 
    
    

    删除

    在许多符号表实现中,删除操作的高效实现是一个挑战,红黑树也不例外,工业级的实现可以运行超过100行代码。教科书一般以详细的案例研究的方式描述操作,避免完整的实现

    下面的代码是LLRB 2-3树的delete()完整实现,它是基于反向自顶向下的方法用于插入2-3-4树:

    我们进行旋转和颜色翻转向下搜索路径,以确保搜索不会在2节点上结束,这样我们就可以删除底部节点,我们使用fixUp()方法共享insert()代码中递归调用后的颜色翻转和旋转代码,通过fixUp(),我们可以在搜索路径上留下右倾斜的红色链接和不平衡的四个节点,确保这些问题在沿树上升的时候会被修复(这种方法也适用于2-3-4树,但如果搜索路径上的右节点是4节点,则需要额外的旋转。)

    作为热身,考虑删除最小操作,目标是删除左边脊柱(left spine)的底部节点,同时保持平衡。为此,我们维护当前节点或者其左孩子的红色不变式,我们可以通过向左移动(move to the left)来实现,除非当前节点是红色的,其左孩子和左孙子(left grandchild,还是叫左孩子的左孩子合适一些?)都是黑的。在这种情况下我们可以做一个颜色翻转,它可以恢复不变量,但可能会在右边引入连续的红色节点,在这种情况下,我们可以通过两个旋转和一个颜色翻转来修正条件,这些操作是在下面的moveRedLeft()方法中实现的。

    使用moveRedLeft()使得deleteMin()的递归实现非常简单,对于一般的删除,我们还需要moveRedRight(),它与moveRedLeft()类似,但是更简单,并且我们需要在搜索路径上将左边的红色链接旋转到右侧以保持不变量。如果要删除的节点是内部节点,我们将其键和值字段替换为其右子树中的最小节点字段,然后删除右子树中最小值字段(或者我们可以重新安排指针来使用节点而不是复制字段)。

    在下面给出了本文所讨论的delete()的完整实现,它使用的代码量仅仅是红黑树典型实现的三分之一到四分之一,使用LLRB树,我们可以设计出简洁的代码,而且具有对数级别的性能保证,还不会使用额外的空间

    删除左倾红黑 2-3树的最小值代码(Delete-the-minimum code for LLRB 2-3 trees)

    
    public void deleteMin() {   
    	root = deleteMin(root);  
    	root.color = BLACK;
     }
    
    private Node deleteMin(Node h) {   
    	if (h.left == null) return null;
    	if (!isRed(h.left) && !isRed(h.left.left))h = moveRedLeft(h);
    	h.left = deleteMin(h.left);
    	return fixUp(h); 
    } 
    
    

    从左倾红黑 2-3树中删除节点(Delete code for LLRB 2-3 trees)

     private Node moveRedLeft(Node h){
    	colorFlip(h);      
        if(isRed(h.right.left)){ 
       	 h.right =rotateRight(h.right);  
       	 h =rotateLeft(h);        
       	 colorFlip(h);     
        }     
    return h;  
    }
    
    private Node moveRedRight(Node h){  
       colorFlip(h);       
       if (isRed(h.left.left)){   
       	h = rotateRight(h);   
       	colorFlip(h);     
       }      	
        return h;  
    }
    
     
    public void delete(Key key){ 
       root = delete(root, key); 
       root.color = BLACK;   
     }
    
    private Node delete(Node h, Key key){ 
       if (key.compareTo(h.key) < 0){             
       	if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h);              
       	h.left =  delete(h.left, key);         
       } else {     
       	if (isRed(h.left)) h = rotateRight(h); 
       	if (key.compareTo(h.key) == 0 && (h.right == null)) return null;              
       	if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);           
    
       if (key.compareTo(h.key) == 0){      
       	h.val = get(h.right, min(h.right).key);            
       	h.key = min(h.right).key;                   
       	h.right = deleteMin(h.right);             
       }else h.right = delete(h.right, key);  
    }
    return fixUp(h); 
    }
    

    图示:

    在这里插入图片描述

    展开全文
  • 多叉形背包常见建模方法

    千次阅读 2017-09-03 20:04:58
    一.多叉变二叉树。 这个技巧其实也有两种具体的方法:的孩子兄弟表示...可以结合下面的图片理解这句话。 总结成口诀就是:第一个儿子是左子树,其他儿子是左子树的右子(似乎并不押韵,手动滑稽) 2.dfs序法

    一.多叉树变二叉树。


    这个技巧其实也有两种具体的方法:树的孩子兄弟表示法与dfs序法。

    1.树的孩子兄弟表示法。

       大家在学习树形结构时一定接触了一个多叉树变二叉树的方法,就是把每个点与它的第一个儿子连边,然后将它的儿子依次连接起来。可以结合下面的图片理解这句话。


    总结成口诀就是:第一个儿子是左子树,其他儿子是左子树的右子树(似乎并不押韵,手动滑稽)

    2.dfs序法

    dfs序就是对一个树进行一个dfs,然后对于每个点记录一个时间戳dfn数组,这个时间戳就是这个节点的dfs序,然后我们再记录一个size数组,表示以每个节点为根的子树中节点的数量。

    假设根节点是u,那么可以容易的推出

    第一个儿子的dfs序dfn[first_son]就是dfn[u]+1

    第二个儿子的dfs序dfn[second_son]就是dfn[u]+size[first_son]+1

    其余同理。

    那么u的下一个兄弟的dfs序dfn[next_brother]就是dfn[u]+size[u]+1


    这两个方法大多用于树形依赖形背包(即使用一个节点必须要使用它所有的祖先),

    主要解决点权问题。


    主要作用就是可以使决策转移的过程变成O(1)的了。


    最常见的模型就是:有n个物品,有一个m大小的包,每个物品有wi物重与vi物品价值,物品之间存在只有装了物品a,才能装物品b的n-1条关系(就是一个树)。问能取得的最大价值。


    简要分析:显然是一个多叉树,考虑转换。

    1.孩子兄弟表示法:对于一个节点i,设dp[i][j]表示在以i为根的子树中,用大小为j的包能取得的最大价值,那么dp[i][j]=max(dp[left[i]][j-w[i]]+v[i],dp[right[i]][j])

    注意,这里的left[i]是i在原树中的第一个儿子,right[i]是i在原树中的下一个兄弟

    这个方程是非常好理解的。效率就是O(nm)的。

    2.dfs序法:对于一个dfs序为i的节点u,同样设dp[i][j]表示在以u为根的子树中,用大小为j的包能取得的最大价值,那么dp[i][j]+v[i]->dp[i+1][j-w[i]]

    dp[i][j]->dp[i+size[i]+1][j]

    注意,这里的转移并不是常见的dp[i][j]=max()....(用dp[i][j]的前驱状态去计算dp[i][j]),而是用dp[i][j]去更新它的后继状态。这种方法被称为刷表法。

    两种方法都是非常巧妙的。但作用也是有限的,只能解决依赖性背包中的点权问题。


    二.分组的树形背包。


    这类问题也是有一个常见模型的,具体可参考洛谷P1272重建道路

    下面针对这道题来分析,能够解决多叉树的,分组的树形背包。

    此时,我们的儿子与父亲之间并不存在依赖型关系,那么我们设dp[k][i][j]表示以i为根的子树,在前k个儿子中,分离出一个大小为j的子树(必须包含i),所需要最少的操作次数。

    那么我们每计算到第k+1个新的儿子v时(full_son[v]表示v的儿子个数),

    dp[k+1][i][j]=min(dp[k][i][j-t]+dp[full_son[v]][v][t]);

    由于一个树形关系,我们需要在一个dfs上进行dp,即先dfs(v),然后更新dp[k+1][i][j]。

    这个k的一维显然可以用滚动数组优化掉。

    那么就是

    j=m->1

    t=1->j

    dp[i][j]=min(dp[i][j-t]+dp[v][t]);

    同时,dp一律要注意初始化,即刚开始时所有的dp[i][1]=du[i](du[i]表示与i连边的节点数,又称i的入度(树是无向边哟!))

    给出参考代码,方便理解:

    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int N=201;
    struct Edge{
    	int to,next;
    }e[N*2];
    int du[N],a[N],dp[N][N];
    int n,k,res=INF,EdgeCnt=0;
    void addedge(int u,int v){
    	int p=++EdgeCnt;
    	e[p].to=v;e[p].next=a[u];
    	a[u]=p;
    }
    void dfs(int u,int fa){
    	dp[u][1]=du[u];
    	for (int p=a[u];p;p=e[p].next){
    		int v=e[p].to;
    		if (v!=fa){
    			dfs(v,u);
    			for (int j=k;j>=1;j--)
    				for (int k=1;k<=j;k++)
    					dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2);
    		}
    	}
    	res=min(res,dp[u][k]);
    }
    int main(){
    	scanf("%d%d",&n,&k);
    	memset(dp,0x3f,sizeof(dp));
    	for (int i=1;i<n;i++){
    		int u,v;
    		scanf("%d%d",&u,&v);
    		addedge(u,v);
    		addedge(v,u);
    		du[u]++;du[v]++;
    	}
    	dfs(1,0);
    	printf("%d",res);
    	return 0;
    }


    同样,这个方法也是有缺陷的,就是无法解决点权问题。大多数运用于边权问题。点权当然也可以,但是效率较低。


    最后总结一句:树形背包都与dfs离不开关系,所以我们可以在dfs上dp可以写的更简单,也可以在dfs预处理后再总刷表法dp。


    这三种方法都各有长处,各有短处,实际运用时还是要注意题目本身的。

    展开全文
  • 今天就来给大家提供一个原创的简历封面,这个个人简历封面-秋天的如下面的图片所示!该文档为个人简历封面-秋天的,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
  • 主要介绍了vue形结构样式和功能,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
  • 主要介绍了vue+element组件 实现树懒加载的过程,本文通过图文实例代码相结合给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
  • ApacheCN 人工智能知识 v1.0

    万次阅读 2019-05-18 11:19:44
    Special Sponsors 贡献者:飞龙 版本:v1.0 ...为了方便大家,我就把每本书的章节拆开,再按照知识点合并,手动整理了这个知识。大家可以按照知识点依次学习,如果理解了一个知识点,...
  • 主要介绍了ElementUI Tree 形控件的使用并给节点添加图标,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
  • gcForest论文的价值

    千次阅读 2017-03-03 14:20:10
    【转载】讨论|周志华教授gcForest论文的价值与技术讨论(微信群) 2017-03-03 全球人工智能 一、gcForest的理论:用决策集成方法解决DNN不足   (模型的框架结构) ...
  • DecisionTree决策算法及参数详解+实例+graphviz生成决策 sklearn随机森林 sklearn集合算法库 sklearn-Bagging自助聚合算法 sklearn-Boosting正向激励算法 sklearn-ExtraTrees算法
  • 数据库索引的数据结构——B-/B+

    千次阅读 2018-08-14 20:28:39
    [这里写图片描述](https://img-blog.csdn.net/20180807190351686?/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTc2Nzk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70) 红黑(自平衡二叉查找) ...
  • 如何观察一棵 - 笔记

    千次阅读 2017-04-24 05:35:00
     对于该书的内容和价值,我压根就没有任何有意义的分析和评价!在使用指读法快速阅读全书内容,我脑海里面留下的内容微乎其微。每每我摩挲着每一张栩栩如生的图片的时候,我感觉它们是那么地真实,我非常喜欢这些...
  • 机器学习实战之决策

    千次阅读 2014-03-31 10:47:46
    决策学习是应用最广泛的归纳推理算法之一,是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策。决策可以使用不熟悉的数据集合,并从中提取出一系列规则,机器学习算法最终将使用这些...
  • 预测模型-完整-教程

    千次阅读 2018-05-30 18:23:05
    基于的学习算法被认为是最好的方法之一,主要用于监测学习方法。基于的方法支持具有高精度、高稳定性和易用性解释的预测模型。不同于线性模型,它们映射非线性关系相当不错。他们善于解决手头的任何问题(分类或...
  • 二、我为什么要种一棵技能? 三、如何养一棵技能? 1、树干 2、树枝 3、树叶 4、果实 一、什么是种树? 我一直觉得,我们想要做一件事情的时候其实就是在心里埋下了一颗种子。 任何植物的成长都会...
  • 最后,我用scikit-learn的决策树拟合了Iris数据集,并生成了最后的决策树图片信息增益(information gain (IG))在介绍信息增益之前,我想先介绍3种不纯度的度量手段,它们分别是Gini index(IG)、entropy(IH)、...
  • 上一课简单介绍了博弈,从编程实现算法的角度看,博弈是三种树中最简单的一种,无论是原理还是实现都不复杂。这一课,我们就以简单的井字棋(Tic-Tac-Toe)游戏为例,介绍一下如何用博弈实现一个简单的井字棋 ...
  • MCTS蒙特卡洛搜索实现井字棋游戏

    千次阅读 2018-05-14 12:55:19
    利用蒙特卡洛搜索实现简单的井字棋游戏,重点不是井字棋,是熟悉蒙特卡洛搜索的应用,而且我们知道,MCTS可以应用到非常复杂的博弈游戏中,比如象棋,围棋,在搜索空间非常大的时候,普通的极大极小搜索无法...
  • Python语语言言描描述述KNN算算法法与与Kd树树 这篇文章主要介绍了Python语言描述KNN算法与Kd具有一定借鉴价值需要的朋友可以参考下 最最 邻法法和和k- 邻法法 下面图片中只有三种豆有三个豆是未知的种类如何判定...
  • Hdu5696 区间的价值(花式水)

    千次阅读 2016-05-22 18:09:34
    欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit...图片链接和图片上传 LaTex数学公式 UML序列图和流程图 离线写博客 导入导出Markdown文件 丰富的快捷键 快捷键 加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
  • 网页图片加载优化方案

    千次阅读 2019-08-16 17:12:46
    饿了么 App 中新零售项目主要是以图片展示为主,引导用户点击轮播广告栏或者店铺列表进入指定的商品页面,因此页面中包含了大量图片,如搜索框下面的轮播广告栏、中部的促销栏以及底部的店铺列表,这些区域中都有...
  • 发散型文本(Diverging Texts)与发散型条形图(Diverging Bars)相似,如果你想以一种漂亮和可呈现的方式显示图表中每个项目的价值,就可以使用这种方法。 12. 发散型包点图(Diverging Dot Plot) 发散型包点图...
  • 而本人的红黑系列四篇文章(详见文末的参考文献),虽然从头至尾,讲的有根有据,层次清晰,然距离读者真正做到红黑了然于胸,则还缺点什么。  而我们知道,即便在经典的算法导论一书上,也没有把所有的插入、...
  • 图片服务器搭建方案

    千次阅读 2019-11-22 17:38:34
    读取图片时不占用应用服务器资源。 缺点: 需要编写的代码较多。  前端显示图片会暴露FTP服务器的地址。  FTP服务器需要做端口映射。  传输速度一般。  同步上传思路需要修改的方法较多。 使用技术: ...
  • SPSS分类分析:决策

    千次阅读 2017-11-03 09:46:00
    SPSS分类分析:决策 一、决策(分析-分类-决策) “决策”过程创建基于的分类模型。它将个案分为若干组,或根据自变量(预测变量)的值预测因变量(目标变量)的值。此过程为探索性和证实性分类分析提供...
  • 大数据最核心的价值是什么?

    万次阅读 2018-07-23 14:33:58
     我把大数据的核心价值理解为核心商业价值。   “很多人还没搞清楚什么是PC互联网,移动互联网来了,我们还没搞清楚移动互联的时候,大数据时代又来了。”——马云卸任演讲   本文尝试从三大产业的角度将...
  • 红黑之收藏

    千次阅读 2012-08-17 13:16:34
    教你透彻了解红黑   作者:July、saturnman 2010年12月29日 本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。 本人声明:个人原创,转载请注明出处。 推荐阅读:Left-Leaning Red...
  • price,这些数值型feature之间通过算数的手段建立了联系,从而挖掘出了feature内部的一些价值,分数也就相应地上去了。 高势集类别(High Categorical)进行经验贝叶斯转换成数值feature   什么是High ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,756
精华内容 7,902
关键字:

价值树图片