精华内容
下载资源
问答
  • 树形结构数据库表设计

    千次阅读 2019-07-13 18:04:34
    文章目录1 基础数据2 继承关系驱动架构设计2.1 表结构2.2 方案优点及缺点3 基于左右值编码架构设计3.1 表结构3.2 方案优缺点4 基于继承关系及左右值编码架构设计4.1 表结构4.2 CURD操作4.2.1 create node...

    1 基础数据

    我们以以下数据为例进行说明

    A
    AA
    AB
    AC
    ABA
    ABB
    ABC
    ACA
    ACAA
    ACAB

    2 继承关系驱动的架构设计

    2.1 表结构

    id parent_id name
    1 A
    2 1 AA
    3 1 AB
    4 3 ABA
    5 3 ABB
    6 3 ABC
    7 1 AC
    8 7 ACA
    9 8 ACAA
    10 8 ACAB

    2.2 方案的优点及缺点

    1. 优点: 设计和实现简单, 直观
    2. 缺点: CURD操作是低效的, 主要归根于频繁的“递归”操作导致的IO开销
    3. 解决方案: 在数据规模较小的情况下可以通过缓存机制来优化

    3 基于左右值编码的架构设计

      关于此方案的设计可以查看另一篇博客, 本人也是通过查看此篇博客学习的, 一些说明也是直接粘过来的, 所以部分细节我这里不再说明, 本篇博客与其的区别主要在于第四节
      在基于数据库的一般应用中,查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程,基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案,来保存该树的数据。

    3.1 表结构

    id left right name
    1 1 20 A
    2 2 3 AA
    3 4 11 AB
    4 5 6 ABA
    5 7 8 ABB
    6 9 10 ABC
    7 12 19 AC
    8 13 18 ACA
    9 14 15 ACAA
    10 16 17 ACAB

      第一次看见这种表结构,相信大部分人都不清楚左值(left)和右值(right)是如何计算出来的,而且这种表设计似乎并没有保存父子节点的继承关系。但当你用手指指着表中的数字从1数到20,你应该会发现点什么吧。对,你手指移动的顺序就是对这棵树进行前序遍历的顺序,如下图所示。当我们从根节点A左侧开始,标记为1,并沿前序遍历的方向,依次在遍历的路径上标注数字,最后我们回到了根节点A,并在右边写上了20。

    (1) A (20)
    (2) AA (3)
    (4) AB (11)
    (5) ABA (6)
    (7) ABB (8)
    (9) ABC (10)
    (12) AC (19)
    (13) AC (18)
    (14) AC (15)
    (16) AC (17)

    3.2 方案优缺点

    1. 优点:
      • 可以方便的查询出某个节点的所有子孙节点
      • 可以方便的获取某个节点的族谱路径(即所有的上级节点)
      • 可已通过自身的left, right值计算出共有多少个子孙节点
    2. 缺点:
      • 增删及移动节点操作比较复杂
      • 无法简单的获取某个节点的子节点

    4 基于继承关系及左右值编码的架构设计

      其实就是在第三节的基础上又加了一列parent_id, 目的是在保留上述优点的同时可以简单的获取某个节点的直属子节点

    4.1 表结构

    id parent_id left right name
    1 1 20 A
    2 1 2 3 AA
    3 1 4 11 AB
    4 3 5 6 ABA
    5 3 7 8 ABB
    6 3 9 10 ABC
    7 1 12 19 AC
    8 7 13 18 ACA
    9 8 14 15 ACAA
    10 8 16 17 ACAB

    4.2 CURD操作

    4.2.1 create node

    # 为id为 id_ 的节点创建名为 name_ 的子节点
    CREATE PROCEDURE `tree_create_node`(IN `id_` INT, IN `name_` VARCHAR(50))
    	LANGUAGE SQL
    	NOT DETERMINISTIC
    	CONTAINS SQL
    	SQL SECURITY DEFINER
    	COMMENT '创建节点'
    BEGIN
    	declare right1 int;
    	# 当 id_ 为 0 时表示创建根节点
    	if id_ = 0 then
    		# 此处我限制了仅允许存在一个根节点, 当然这并不是必须的
    		if exists(select `id` from tree_table where `left` = 1) then
    			SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '根节点已存在';
    		end if;
    		
    		insert into tree_table(`parent_id`, `name`, `left`, `right`)
    		values(0, name_, 1, 2);
    		commit;
    	elseif exists(select `id` from tree_table where `parent_id` = id_ and `name` = name_) then
    		# 禁止在同一级创建同名节点
    		SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '已存在同名兄弟节点';
    	elseif exists(select `id` from tree_table where `id` = id_ and `is_delete` = 0) then
    		start transaction;
    		set right1=(select `right` from tree_table where `id` = id_);
    		
    		update tree_table set `right` = `right` + 2 where `right` >= right1;
    		update tree_table set `left` = `left` + 2 where `left` >= right1;
    
    		insert into tree_table(`parent_id`, `name`, `left`, `right`) 
    		values(id_, name_, right1, right1 + 1);
    
    		commit;
    		# 下面一行仅为了展示以下新插入记录的id, 并不是必须的
    		select LAST_INSERT_ID();
    	else
    		SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '父节点不存在(未创建或被删除)';
    	end if;
    END
    
    # 创建根节点
    call tree_create_node(0, 'A')
    # 为节点1创建名为AB的子节点
    call tree_create_node(1, 'AB')
    

    4.2.2 delete node

    CREATE PROCEDURE `tree_delete_node`(IN `id_` INT)
    	LANGUAGE SQL
    	NOT DETERMINISTIC
    	CONTAINS SQL
    	SQL SECURITY DEFINER
    	COMMENT ''
    BEGIN
    	declare left1 int;
    	declare right1 int;
    	if exists(select id from tree_table where id = id_) then
    		start transaction;
    		select `left`, `right` into left1, right1 from tree_table where id = id_;
    		delete from tree_table where `left` >= left1 and `right` <= right1;
    		update tree_table set `left` = `left` - (right1-left1+1) where `left` > left1;
    		update tree_table set `right` = `right` - (right1-left1+1) where `right` > right1;      
    		commit;
    	end if;
    END
    
    # 删除节点2, 节点2的子孙节点也会被删除
    call tree_delete_node(2)
    

    4.2.3 move node

       move的原理是先删除再添加, 但涉及被移动的节点的left, right值不能乱所以需要使用临时表(由于在存储过程中无法创建临时表, 此处我使用了一张正常的表进行缓存, 欢迎提出更合理的方案)

    # 此存储过程中涉及到is_delete字段, 表示数据是否被删除, 因为正式环境中删除操作一般都不会真的删除而是进行软删(即标记删除), 如果不需要此字段请自行对程序进行调整
    CREATE PROCEDURE `tree_move_node`(IN `self_id` INT, IN `parent_id` INT
    , IN `sibling_id` INT)
    	LANGUAGE SQL
    	NOT DETERMINISTIC
    	CONTAINS SQL
    	SQL SECURITY DEFINER
    	COMMENT ''
    BEGIN
    	declare self_left int;
    	declare self_right int;
    	declare parent_left int;
    	declare parent_right int;
    	declare sibling_left int; 
    	declare sibling_right int;
    	declare sibling_parent_id int;
    	if exists(select id from tree_table where id = parent_id and is_delete = 0) then
    		# 创建中间表
    		CREATE TABLE If Not Exists tree_table_self_ids (`id` int(10) unsigned NOT NULL);
    		truncate tree_table_self_ids;
    		
    		start transaction;  # 事务
    		# 获取移动对象的 left, right 值
    		select `left`, `right` into self_left, self_right from tree_table where id = self_id;
    		# 将需要移动的记录的 id 存入临时表, 以保证操作 left, right 值变化时这些记录不受影响
    		insert into tree_table_self_ids(id) select id from tree_table where `left` >= self_left and `right` <= self_right;
    		
    		# 将被移动记录后面的记录往前移, 填充空缺位置
    		update tree_table set `left` = `left` - (self_right-self_left+1) where `left` > self_left and id not in (select id from tree_table_self_ids);
    		update tree_table set `right` = `right` - (self_right-self_left+1) where `right` > self_right and id not in (select id from tree_table_self_ids);
    		
    		select `left`, `right` into parent_left, parent_right from tree_table where id = parent_id;
    		if sibling_id = -1 then
    			# 在末尾插入子节点
    			update tree_table set `right` = `right` + (self_right-self_left+1) where `right` >= parent_right and id not in (select id from tree_table_self_ids);
    			update tree_table set `left` = `left` + (self_right-self_left+1) where `left` >= parent_right and id not in (select id from tree_table_self_ids);
    			update tree_table set `right`=`right` + (parent_right-self_left), `left`=`left` + (parent_right-self_left) where id in (select id from tree_table_self_ids);
    		elseif sibling_id = 0 then
    			# 在开头插入子节点
    			update tree_table set `right` = `right` + (self_right-self_left+1) where `right` > parent_left and id not in (select id from tree_table_self_ids);
    			update tree_table set `left` = `left` + (self_right-self_left+1) where `left` > parent_left and id not in (select id from tree_table_self_ids);
    			update tree_table set `right`=`right` - (self_left-parent_left-1), `left`=`left` - (self_left-parent_left-1) where id in (select id from tree_table_self_ids);
    		else
    			# 插入指定节点之后
    			select `left`, `right`, `parent_id` into sibling_left, sibling_right, sibling_parent_id from tree_table where id = sibling_id;
    			if parent_id != sibling_parent_id then
    				SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '指定的兄弟节点不在指定的父节点中';
    			end if;
    			update tree_table set `right` = `right` + (self_right-self_left+1) where `right` > sibling_right and id not in (select id from ctree_table_self_ids);
    			update tree_table set `left` = `left` + (self_right-self_left+1) where `left` > sibling_right and id not in (select id from tree_table_self_ids);
    			update tree_table set `right`=`right` - (self_left-sibling_right-1), `left`=`left` - (self_left-sibling_right-1) where id in (select id from tree_table_self_ids);
    		end if;
    		update tree_table set `parent_id`=parent_id where `id` = self_id;
    		commit;
    	else
    		SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = '父节点不存在(未创建或被删除)';
    	end if;
    END
    
    # 将节点2移动到节点1下面开头的位置
    call tree_move_node(2, 1, 0)
    # 将节点2移动到节点1下面末尾的位置
    call tree_move_node(2, 1, -1)
    # 将节点2移动到节点1下面且跟在节点3后面的位置
    call tree_move_node(2, 1, 3)
    

    4.2.4 select

    # 以下sql中需要传的值全用???表示
    # 根据节点id获取此节点所有子孙节点
    select * from tree_table where 
    	left > (select left from tree_table where id=???) and 
    	right < (select right from tree_table where id=???)
    # 根据节点id获取此节点的所有子孙节点(包含自己)
    select * from tree_table where 
    	left >= (select left from tree_table where id=???) and 
    	right <= (select right from tree_table where id=???)
    # 根据节点id获取此节点的所有上级节点
    select * from tree_table where 
    	left < (select left from tree_table where id=???) and 
    	right > (select right from tree_table where id=???)
    # 根据节点id获取此节点的所有上级节点(包括自己)
    select * from tree_table where 
    	left <= (select left from tree_table where id=???) and 
    	right >= (select right from tree_table where id=???)
    

    5 存储完整父级路径的架构设计

    5.1 表结构

    id parent_id parents_id name
    1 0 A
    2 1 1 AA
    3 1 1 AB
    4 3 1,3 ABA
    5 3 1,3 ABB
    6 3 1,3 ABC
    7 1 1 AC
    8 7 1,7 ACA
    9 8 1,7,8 ACAA
    10 8 1,7,8 ACAB

    给parents_id字段加上全文索引就可以方便的查出某个节点的所有下级数据了
    须注意的mysql全文索引默认是无法识别出短数字的, 需要先修改配置
    配置参数参考另一篇文章
    将上述参数改为1即可正常使用全文索引搜索数据(如果索引已经建好, 改完数据库配置需要重建索引才能生效)
    当然不想使用全文索引的话, 正常的索引使用前缀查询也可以相对方便的查出数据

    5.2 方案优缺点

    1. 创建节点时需先查出父节点的信息
    2. 当移动节点时更新数据较多

    6 总结

       此篇文章对左右值编码结构的原理介绍的不多, 需要详细了解的可以查阅末尾引用的博客

    树形结构的数据库表设计

    展开全文
  • 目录 1. 定义 2. 结构 3. 代码实现 4. 透明组合模式与安全组合模式 4.1 透明组合模式 4.1 安全组合模式 5. 优缺点 6. 适用场景 7. 个人理解 参考 ...

    树形结构在软件中随处可见,例如操作系统中的目录结构、应用软件中的菜单、办公系统中的公司组织结构等。

    组合模式通过一种巧妙的设计方案使得用户可以一致性地处理整个树形结构或者树形结构的一部分,也可以一致性地处理树形结构中的叶子节点(不包含子节点的节点)和容器节点(包含子节点的节点)。

    1. 定义

    组合模式(Composite Pattern):组合多个对象形成树形结构以表示具有“整体—部分”关系的层次结构。组合模式对单个对象(即叶子对象)和组合对象(即容器对象)的使用具有一致性,组合模式又可以称为“整体—部分”(Part-Whole)模式,它是一种对象结构型模式。

    2. 结构

    在组合模式中引入了抽象构件类Component,它是所有容器类和叶子类的公共父类,客户端针对Component进行编程。组合模式结构如图所示:

    组合模式

    • Component(抽象构件):它可以是接口或抽象类,为叶子构件和容器构件对象声明接口,在该角色中可以包含所有子类共有行为的声明和实现。在抽象构件中定义了访问及管理它的子构件的方法,如增加子构件、删除子构件、获取子构件等。
    • Leaf(叶子构件):它在组合结构中表示叶子节点对象,叶子节点没有子节点,它实现了在抽象构件中定义的行为。对于那些访问及管理子构件的方法,可以通过异常等方式进行处理。
    • Composite(容器构件):它在组合结构中表示容器节点对象,容器节点包含子节点,其子节点可以是叶子节点,也可以是容器节点,它提供一个集合用于存储子节点,实现了在抽象构件中定义的行为,包括那些访问及管理子构件的方法,在其业务方法中可以递归调用其子节点的业务方法。

    3. 代码实现

    代码实现了一个公司的组织架构,包括各级公司,各级公司包括各部门,AbstractOrganization充当抽象构建类,Company充当容器构建类(可以定义其他容器构建类),Department充当叶子构建类(可以定义其他叶子构建类)。

    AbstractOrganization

    public abstract class AbstractOrganization {
    
        public abstract void add(AbstractOrganization organization);
    
        public abstract void remove(AbstractOrganization organization);
    
        public abstract  AbstractOrganization getChild(int i);
    
        public abstract void notifyMessage();
    
    }

    Company

    public class Company extends AbstractOrganization {
    
        private List<AbstractOrganization> organizationList=new ArrayList<>();
        private String name;
    
        public Company(String name) {
            this.name = name;
        }
    
        @Override
        public void add(AbstractOrganization organization) {
            organizationList.add(organization);
        }
    
        @Override
        public void remove(AbstractOrganization organization) {
            organization.remove(organization);
        }
    
        @Override
        public AbstractOrganization getChild(int i) {
            return organizationList.get(i);
        }
    
        @Override
        public void notifyMessage() {
            System.out.println("对公司:"+name+" 进行通知");
            for (AbstractOrganization organization:organizationList){
                organization.notifyMessage();
            }
        }
    }

    Department

    public class Department extends AbstractOrganization {
    
        private String name;
    
        public Department(String name) {
            this.name = name;
        }
    
        @Override
        public void add(AbstractOrganization organization) {
            System.out.println("对不起,不支持该方法!");
        }
    
        @Override
        public void remove(AbstractOrganization organization) {
            System.out.println("对不起,不支持该方法!");
        }
    
        @Override
        public AbstractOrganization getChild(int i) {
            System.out.println("对不起,不支持该方法!");
            return null;
        }
    
        @Override
        public void notifyMessage() {
            System.out.println("对"+name+" 进行通知");
        }
    }

    Client

    public class Client {
    
        public static void main(String[] args) {
            AbstractOrganization c1,c2,d1,d2,d3;
            c1=new Company("总公司");
            c2=new Company("分公司1");
            d1=new Department("总公司部门1");
            d2=new Department("分公司部门1");
            d3=new Department("分公司部门2");
            c1.add(c2);
            c1.add(d1);
            c2.add(d2);
            c2.add(d3);
            //客户端无序关心节点的层次结构,对节点可以进行统一处理
            c1.notifyMessage();
            System.out.println("-------------");
            c2.notifyMessage();
        }
    }
    
    //对公司:总公司 进行通知
    //对公司:分公司1 进行通知
    //对分公司部门1 进行通知
    //对分公司部门2 进行通知
    //对总公司部门1 进行通知
    //-------------
    //对公司:分公司1 进行通知
    //对分公司部门1 进行通知
    //对分公司部门2 进行通知

    4. 透明组合模式与安全组合模式

    4.1 透明组合模式

    透明组合模式中,抽象构件Component中声明了所有用于管理成员对象的方法,包括add()、remove()以及getChild()等方法,这样做的好处是确保所有的构件类都有相同的接口。在客户端看来,叶子对象与容器对象所提供的方法是一致的,客户端可以相同地对待所有的对象。

    透明组合模式的缺点是不够安全,因为叶子对象和容器对象在本质上是有区别的。叶子对象不可能有下一个层次的对象,即不可能包含成员对象,因此为其提供add()、remove()以及getChild()等方法是没有意义的,这在编译阶段不会出错,但在运行阶段如果调用这些方法可能会出错(如果没有提供相应的错误处理代码)。

    4.1 安全组合模式

    Java AWT中使用的组合模式就是安全组合模式。

    安全组合模式中,在抽象构件Component中没有声明任何用于管理成员对象的方法,而是在Composite类中声明并实现这些方法。这种做法是安全的,因为根本不向叶子对象提供这些管理成员对象的方法,对于叶子对象,客户端不可能调用到这些方法。

    安全组合模式的缺点是不够透明,因为叶子构件和容器构件具有不同的方法,且容器构件中那些用于管理成员对象的方法没有在抽象构件类中定义,因此客户端不能完全针对抽象编程,必须有区别地对待叶子构件和容器构件。

    客户端需要指定具体的容器类型,才能调用管理成员对象的方法。

    Comapany c1,c2;
    AbstractOrganization d1,d2,d3;
    ...
    c1.notifyMessage();

    5. 优缺点

    • 优点
    1. 组合模式可以清楚地定义分层次的复杂对象,表示对象的全部或部分层次,它让客户端忽略了层次的差异,方便对整个层次结构进行控制。
    2. 客户端可以一致地使用一个组合结构或其中单个对象,简化客户端代码。
    3. 在组合模式中增加新的容器构件和叶子构件都很方便,无须对现有类库进行任何修改,符合“开闭原则”。
    4. 组合模式为树形结构的面向对象实现提供了一种灵活的解决方案,通过叶子对象和容器对象的递归组合,可以形成复杂的树形结构,但对树形结构的控制却非常简单。
    • 缺点
    1. 在增加新构件时很难对容器中的构件类型进行限制。因为它们都来自于相同的抽象层,在这种情况下,必须通过在运行时进行类型检查来实现,这个实现过程较为复杂。

    6. 适用场景

    1. 在具有整体和部分的层次结构中,希望通过一种方式忽略整体与部分的差异,客户端可以一致地对待它们。
    2. 在一个使用面向对象语言开发的系统中需要处理一个树形结构
    3. 在一个系统中能够分离出叶子对象和容器对象,而且它们的类型不固定,需要增加一些新的类型。

    7. 个人理解

    组合模式用户处理类似树形结构的包含容器对象和叶子对象的层次结构,通过该模式可忽略整体与部分的差异,让客户端统一对待它们,同时符合“开闭原则”利于扩展。

    参考

    1. Java设计模式-刘伟

    转载于:https://www.cnblogs.com/ading-blog/p/9678293.html

    展开全文
  • 文章目录概述随机森林优缺点GBDT原理, 如何做分类和回归GBDT分类拟合是什么GBDT+ LR 是怎么做CART分类回归和ID3以及C4.5有什么区别决策树的优点和缺点RF, GBDT, XGBOOST, XGB区别改变随机森林训练...

    概述

    基本推导和理论还是以看李航老师的《统计学习方法》为主。
    各种算法的原理,推荐理解到可以手撕的程度。
    以下为通过网络资源搜集整理的一些问题及答案,准备的有些仓促,没能记录所有资料的来源(侵删)

    决策树笔记

    https://download.csdn.net/download/yolohohohoho/10973332

    随机森林优缺点

    随机森林优点
    1、在当前的很多数据集上,相对其他算法有着很大的优势,表现良好
    2、它能够处理很高维度(feature很多)的数据,并且不用做特征选择
    3、在训练完后,它能够给出哪些feature比较重要
    4、 在创建随机森林的时候,对generlization error使用的是无偏估计,模型泛化能力强
    5、训练速度快,容易做成并行化方法,训练时树与树之间是相互独立的
    6、 在训练过程中,能够检测到feature间的互相影响
    7、 实现比较简单
    8、 对于不平衡的数据集来说,它可以平衡误差。
    1)每棵树都选择部分样本及部分特征,一定程度避免过拟合;
    2)每棵树随机选择样本并随机选择特征,使得具有很好的抗噪能力,性能稳定;
    对缺失值不敏感,如果有很大一部分的特征遗失,仍可以维持准确度
    随机森林有out of bag,不需要单独换分交叉验证集

    随机森林缺点:
    1) 参数较复杂;
    2) 模型训练和预测都比较慢。
    3) 不适合小样本,只适合大样本。

    GBDT的原理, 如何做分类和回归

    首先明确一点,gbdt 无论用于分类还是回归一直都是使用的CART 回归树。不会因为我们所选择的任务是分类任务就选用分类树,这里面的核心是因为gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候,弱分类器的输出的结果相减是有意义的。残差相减是有意义的。
    如果选用的弱分类器是分类树,类别相减是没有意义的。上一轮输出的是样本 x 属于 A类,本一轮训练输出的是样本 x 属于 B类。 A 和 B 很多时候甚至都没有比较的意义,A 类- B类是没有意义的。
    我们仿照多分类的逻辑回归 ,使用softmax 来产生概率

    GBDT分类树拟合的是什么

    利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值,拟合一个回归树。GBDT 每轮迭代的时候,都去拟合损失函数在当前模型下的负梯度。

    GBDT+ LR 是怎么做的

    主要思想:GBDT 每棵树的路径直接作为 LR 输入特征使用。
    https://blog.csdn.net/lilyth_lilyth/article/details/48032119
    https://www.deeplearn.me/1797.html

    CART分类回归树和ID3以及C4.5有什么区别

    ID3最大信息熵增益”选取当前最佳的特征来分割数据. 采用的信息增益度量存在一个缺点,它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大).

    C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature。除此之外,C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是,对连续属性值需要扫描排序,会使C4.5性能下降

    CART回归树用平方误差最小化准则,分类树用基尼指数最小化准则

    决策树的优点和缺点
    • 优点:
    1. 决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解,
    2. 决策树模型可以可视化,非常直观
    3. 应用范围广,可用于分类和回归,而且非常容易做多类别的分类
    4. 能够处理数值型和连续的样本特征
    • 缺点:
    1. 很容易在训练数据中生成复杂的树结构,造成过拟合(overfitting)。剪枝可以缓解过拟合的负作用,常用方法是限制树的高度、叶子节点中的最少样本数量。
    2. 学习一棵最优的决策树被认为是NP-Complete问题。实际中的决策树是基于启发式的贪心算法建立的,这种算法不能保证建立全局最优的决策树。Random Forest 引入随机能缓解这个问题
    RF, GBDT, XGBOOST, XGB的区别

    GBDT和随机森林的相同点:
    1、都是由多棵树组成
    2、最终的结果都是由多棵树一起决定
    GBDT和随机森林的不同点:
    1、组成随机森林的树可以是分类树,也可以是回归树;而GBDT只由回归树组成
    2、组成随机森林的树可以并行生成;而GBDT只能是串行生成
    3、对于最终的输出结果而言,随机森林采用多数投票等;而GBDT则是将所有结果累加起来,或者加权累加起来
    4、随机森林对异常值不敏感,GBDT对异常值非常敏感
    5、随机森林对训练集一视同仁,GBDT是基于权值的弱分类器的集成
    6、随机森林是通过减少模型方差提高性能,GBDT是通过减少模型偏差提高性能

    Xgboost是GB算法的高效实现,xgboost中的基学习器除了可以是CART(gbtree)也可以是线性分类器(gblinear)。
      (1). xgboost在目标函数中显示的加上了正则化项,基学习为CART时,正则化项与树的叶子节点的数量T和叶子节点的值有关。
      (2). GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x),xgboost不仅使用到了一阶导数,还使用二阶导数。
      (3). 上面提到CART回归树中寻找最佳分割点的衡量标准是最小化均方差,xgboost寻找分割点的标准是最大化,lambda,gamma与正则化项相关。
    参见https://blog.csdn.net/timcompp/article/details/61919851

    改变随机森林的训练样本数据量,是否会影响到随机森林学习到的模型的复杂度

    https://zhuanlan.zhihu.com/p/29114739
    默认参数下模型复杂度是:O(MNlog(N)) , 其中 M 是树的数目, N 是样本数。
    其中 M 是树的数目, N 是样本数。可以通过设置以下参数来降低模型复杂度: min_samples_split , min_samples_leaf , max_leaf_nodes 和 max_depth 。

    Time complexity for building a complete unpruned decision tree is O( v * n log(n) ), where n is the number of records and v is the number of variables/attributes.
    Since we would only use mtry variables at each node the complexity to build one tree would be O( mtry * n log(n) )
    Now for building a random forest with ntree number of trees, the complexity would be O( ntree * mtry * nlog(n) ) say you restrict the maximum depth of your tree to be “d” then the complexity calculations can be simplified to: O( ntree * mtry * d * n)
    Note. The above calculations are ignoring the complexity involved for random selection of variables that needs to be done at each node. I believe this would add an additional O( v * d * ntree)

    树集成模型有哪几种形式?

    bagging和boosting

    随机森林的随机体现在哪方面
    • 在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。随机森林的随机性体现在每颗树的训练样本是随机的,树中每个节点的分裂属性集合也是随机选择确定的。有了这2个随机的保证,随机森林就不会产生过拟合的现象了。

    • random forest 确实是一个不会overfitting的模型。主要依靠了其中三个随机过程,即产生决策树的样本是随机生成,构建决策树的特征值是随机选取,树产生过程中裂变的时候是选择N个最佳方向中的随机一个裂变的。当随机森林产生的树的数目趋近无穷的时候,理论上根据大数定理可以证明训练误差与测试误差是收敛到一起的。

      https://www.applysquare.com/topic-cn/TKfPL4L4y/

    决策树处理连续值的方法。

    二分法切分点

    决策树如何防止过拟合,过拟合的标志有哪些?

    Early Stopping
    • 限制树的深度:当达到设置好的最大深度的时候结束;
    • 分类误差法:当继续展开无法得到可观的分类误差减小,结束;
    • 叶子节点最小数据量限制:一个结点的数据量过小,结束
    early stopping的缺点:以异或为例,说明只有分到最后才能达到理想效果,但是early stopping过早结束。

    Pruning剪枝;

    训练集误差越来越小,true error却先变小后变大,我们就说发生了过拟合(overfitting)
    测试机误差大

    展开全文
  • 一什么是Trie树二Trie树的优缺点 优点缺点 三Trie树的应用 字符串检索词频统计字符串排序前缀匹配作为其他数据结构和算法的辅助结构 四Trie树的实现 本文用尽量简洁的语言介绍一种树形数据结构 ...
    
    

    本文用尽量简洁的语言介绍一种树形数据结构 —— Trie树。

    一、什么是Trie树

    Trie树,又叫字典树前缀树(Prefix Tree)单词查找树 或 键树,是一种多叉树结构。如下图:


     

    上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:

    1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
    2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
    3. 每个节点的所有子节点包含的字符互不相同。

    通常在实现的时候,会在节点结构中设置一个标志,用来标记该结点处是否构成一个单词(关键字)。

    可以看出,Trie树的关键字一般都是字符串,而且Trie树把每个关键字保存在一条路径上,而不是一个结点中。另外,两个有公共前缀的关键字,在Trie树中前缀部分的路径相同,所以Trie树又叫做前缀树(Prefix Tree)


    二、Trie树的优缺点

    Trie树的核心思想是空间换时间,利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

    优点

    1. 插入和查询的效率很高,都为O(m),其中 m 是待插入/查询的字符串的长度。

      • 关于查询,会有人说 hash 表时间复杂度是O(1)不是更快?但是,哈希搜索的效率通常取决于 hash 函数的好坏,若一个坏的 hash 函数导致很多的冲突,效率并不一定比Trie树高。
    2. Trie树中不同的关键字不会产生冲突。

    3. Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。

    4. Trie树不用求 hash 值,对短字符串有更快的速度。通常,求hash值也是需要遍历字符串的。

    5. Trie树可以对关键字按字典序排序。

    缺点

    1. 当 hash 函数很好时,Trie树的查找效率会低于哈希搜索。

    2. 空间消耗比较大。


    三、Trie树的应用

    1、字符串检索

    检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较:

    • 如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在。
    • 如果所有的字符全部比较完并且全部相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)。
    struct trie_node
    {
        bool isKey;   // 标记该节点是否代表一个关键字
        trie_node *children[26]; // 各个子节点 
    };
    • 1
    • 2
    • 3
    • 4
    • 5

    2、词频统计

    Trie树常被搜索引擎系统用于文本词频统计 。

    struct trie_node
    {
        int count;   // 记录该节点代表的单词的个数
        trie_node *children[26]; // 各个子节点 
    };
    • 1
    • 2
    • 3
    • 4
    • 5

    思路:为了实现词频统计,我们修改了节点结构,用一个整型变量count来计数。对每一个关键字执行插入操作,若已存在,计数加1,若不存在,插入后count置1。

    注意:第一、第二种应用也都可以用 hash table 来做。

    3、字符串排序

    Trie树可以对大量字符串按字典序进行排序,思路也很简单:遍历一次所有关键字,将它们全部插入trie树,树的每个结点的所有儿子很显然地按照字母表排序,然后先序遍历输出Trie树中所有关键字即可。

    4、前缀匹配

    例如:找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树,然后输出以a->b->开头的路径上的关键字即可。

    trie树前缀匹配常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

    5、作为其他数据结构和算法的辅助结构

    如后缀树,AC自动机等。


    四、Trie树的实现

    这里为了方便,我们假设所有的关键字都由 a-z 的字母组成。下面是 trie 树的一种典型实现:

    #include <iostream>
    #include <string>
    using namespace std;
    
    #define ALPHABET_SIZE 26
    
    typedef struct trie_node
    {
        int count;   // 记录该节点代表的单词的个数
        trie_node *children[ALPHABET_SIZE]; // 各个子节点 
    }*trie;
    
    trie_node* create_trie_node()
    {
        trie_node* pNode = new trie_node();
        pNode->count = 0;
        for(int i=0; i<ALPHABET_SIZE; ++i)
            pNode->children[i] = NULL;
        return pNode;
    }
    
    void trie_insert(trie root, char* key)
    {
        trie_node* node = root;
        char* p = key;
        while(*p)
        {
            if(node->children[*p-'a'] == NULL)
            {
                node->children[*p-'a'] = create_trie_node();
            }
            node = node->children[*p-'a'];
            ++p;
        }
        node->count += 1;
    }
    
    /**
     * 查询:不存在返回0,存在返回出现的次数
     */ 
    int trie_search(trie root, char* key)
    {
        trie_node* node = root;
        char* p = key;
        while(*p && node!=NULL)
        {
            node = node->children[*p-'a'];
            ++p;
        }
    
        if(node == NULL)
            return 0;
        else
            return node->count;
    }
    
    int main()
    {
        // 关键字集合
        char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
        trie root = create_trie_node();
    
        // 创建trie树
        for(int i = 0; i < 8; i++)
            trie_insert(root, keys[i]);
    
        // 检索字符串
        char s[][32] = {"Present in trie", "Not present in trie"};
        printf("%s --- %s\n", "the", trie_search(root, "the")>0?s[0]:s[1]);
        printf("%s --- %s\n", "these", trie_search(root, "these")>0?s[0]:s[1]);
        printf("%s --- %s\n", "their", trie_search(root, "their")>0?s[0]:s[1]);
        printf("%s --- %s\n", "thaw", trie_search(root, "thaw")>0?s[0]:s[1]);
    
        return 0;
    }
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75

    对于Trie树,我们一般只实现插入和搜索操作。这段代码可以用来检索单词和统计词频。

    展开全文
  • 目录-按照顺序阅读即可决策树之基础一句话概括决策树分类决策树分类决策树的构建节点划分标准ID3ID3的缺点C4.5C4.5的优缺点CART 决策树之基础 一句话概括决策树 决策树就是按照一定的规则构建出的树形结构,实现分类...
  • 文章目录分类算法之决策特征选择信息度量和作用信息增益信息增益计算method决策本地保存决策树优缺点分析集成方法(分类)之随机森林学习算法属性方法波士顿房屋租赁价格预测完整代码 分类算法之决策 决策...
  • 机器学习算法系列 目录 机器学习算法系列 前言 二、决策树生成原则 ...八、决策树优缺点 ...决策树是一种树形结构,树内部每个节点表示一个属性上测试,每个分支代表一个测试输出,每个叶子节点代表.
  • 文章目录1. 简单介绍决策树算法2. 决策树和条件概率分布的关系?3. 信息增益比相对信息增益有什么好处?4. ID3算法—>C4.5算法—> CART算法5....10.决策树的优缺点?11. 树形结构为什么不需要...
  • 决策算法优缺点 知识巩固 Python实战:决策判断员工是否适合相关工作 拓展学习 现实问题:“求职简历太多,给不给面试机会?” 简历上有什么:个人技能、工作经验、学校学历、期望薪资等 任务:根据求职...
  • (2)还有就是处理树形结构时候,比如菜单,菜单下面有子菜单,子菜单下面还有菜单,以及目录目录下有子目录 优缺点 优点: 可以清除地定义分层次复杂对象,表示对象全部或部分层次 让客户端忽...
  • JAVA设计模式--组合模式

    万次阅读 2017-02-10 22:14:23
    五、组合模式的优缺点 六、总结 一、什么是组合模式 组合(Composite)模式是一种对象的行为模式。将对象组合成树形结构以表示“部分-整体”的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。 ...
  • 文章目录定义优缺点优点:缺点:实现代码测试 定义 组合模式依据树形结构来组合对象,用来表示部分以及整体层次。 优缺点 优点: 层次清晰。 节点自由增加。 方便创建出复杂层次机构,客户端不用理会组合里面...
  • 文章目录各个数据结构的优缺点数组结构链表结构树形结构二叉树简介二叉树遍历前序遍历中序遍历后序遍历二叉树查找二叉树节点的删除 各个数据结构的优缺点 数组结构 查找快,删除插入慢。 链表结构 删除插入块,查找...
  • 文章目录组合模式(1)概念(2)适用场景(3)代码示例(4)该模式在源码中的体现(5)组合模式的优缺点 (1)概念 组合模式(Composite Pattern),又叫部分整体模式,是用于把一组相似的对象当作一个单一的对象。...
  • 文章目录实战,借助组合模式,实现dom树节点创建优缺点适用场景 组合模式,又叫整体-部分模式,它允许你将对象组合成树形结构来表现 整体-部分层次结构,让使用者可以以一致方式处理组合对象以及部分对象。 ...
  • vue项目,所在项目有一个文档树形数据,前端请求到文档数据后需要动态渲染,此时当文档过长时就需要通过目录进行锚点定位,以方便用户查看。 2.需求分析 锚点定位方法常用有两种,这两种各有优缺点。第一种是a...
  • 文章目录KNN原理优缺点逻辑斯蒂函数原理优缺点决策原理优缺点朴素贝叶斯支持向量机自适应提升算法 KNN K-近邻算法(k-Nearest Neighbor,KNN)采用测量不同特征值之间距离方法进行分类。 原理 已知数据...
  • 计算机操作系统面经(一) 计算机操作系统面经(二) 1.有哪几种文件目录结构,目前广泛采用文件目录结构是哪种?它有什么优点? (1)目录结构有:单级目录结构,两级目录结构、多级...分别有什么优缺点? ...
  • 第七章 文件管理

    2020-05-18 09:20:55
    文章目录树形目录结构7.1 文件和文件系统7.1.1 文件、记录和数据项文件、记录和数据项之间关系文件属性7.1.2 文件名和类型1. 文件名和扩展名2. 文件类型7.1.3 文件系统层次结构7.1.4 文件操作文件“打开”和...
  • 文章目录介绍类图说明代码示例应用场景优缺点优点缺点 介绍 组合模式(Composite Pattern),又叫部分整体模式,是用于把一组相似对象当作一个单一对象。组合模式依据树形结构来组合对象,用来表示部分以及整体...
  • 树形目录结构中,利用链接方式共享文件有何好处?使用文件系统时,通常要显式地进行open、close操作 第七章:文件管理 文件系统需要做什么事情? 文件需要共享,需要保护,创建文件目录开管理文件,有了目录就需要...
  • 五、组合模式的优缺点 六、组合模式的实际应用场景例子 一、组合模式应用在哪些场景中 需求中是整体与部分的层次结构时,而且需求是树形结构,整体与部分用户希望忽略组合对象和单个对象的不同,统一使用组合...
  • 文章目录C++设计模式——组合模式目录定义定义结构代码示例总结使用场景及注意事项优缺点参考资料 定义 定义 Compose objects into tree structures to represent part-whole hierarchies.Composite lets clients ...
  • 组合模式读书笔记

    2019-11-19 20:32:11
    文章目录模式定义模式结构通用源代码实现应用场景和具体实现组合模式的优缺点:1.组合模式的优点2.组合模式的缺点适用场景2.组合模式的缺点适用场景 模式定义 组合模式组合多个对象形成树形结构以表示“整体-部分”...
  • 设计模式-组合模式-Java 目录 文章目录1、示例案例- 设计杀毒...  树形结构在软件中随处可见,例如操作系统中的目录结构、应用软件中菜单、办公系统中公司组织结构等等,如何运用面向对象方式来处理这种树形
  • 13、组合模式

    2020-12-19 14:40:54
    文章目录组合模式概述结构结构实现练习源代码透明组合模式与安全组合模式透明组合模式安全组合模式组合模式/缺点与适用环境优点缺点适用环境 概述 组合模式:组合多个对象形成树形结构以表示具有部分-整体关系...
  • 对于树形结构,客户端中必须区别对待容器(这里容器指树形结构中不是端点节点)和叶子对象,而实际上大多数情况下客户端希望一致处理他们。 二 . 模式定义 组合模式(Composite Pattern):组合多个对象形...
  • 数据结构 + 算法 = 程序 ...顺序存储结构和链式存储结构的优缺点 数据逻辑结构 集合结构 线性结构 树形结构 图形结构 数据结构 一些概念 数据结构就是研究数据的逻辑结构和物理结构以...

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

树形目录的优缺点