精华内容
下载资源
问答
  • 斜决策树是传统决策树的变体,它允许以功能组合的形式在其内部节点中进行多元测试。 我们的研究SLSDT是一种使用称为后验收爬山(LAHC)的随机局部搜索方法来感应倾斜决策树的方法,以尝试在每个内部节点中找到特征...
  • 斜决策树 MATLAB实验

    2019-06-27 21:32:48
    一、说明 ...3、斜决策树的节点不再是单一属性,而是属性的线性组合。 二、算法 确定节点算法流程: 确定节点算法描述: 1、找到轴平行划分的最优划分平面,I为不纯度指标。 2、重复R次: 随机算...

    一、说明
    1、根据Sreerama K. Murthy论文A System for Induction of Oblique Decision Trees中的算法进行的实验。
    2、实验数据来自周志华著的机器学习书中。
    3、斜决策树的节点不再是单一属性,而是属性的线性组合。
    二、算法
    确定节点算法流程:
    在这里插入图片描述
    确定节点算法描述:
    1、找到轴平行划分的最优划分平面,I为不纯度指标。
    2、重复R次:
    随机算则超平面,初始化时以轴平行的划分平面作为初始平面
    步骤1:
    随机扰动超平面H的参数,知道不纯度指标不再提高。
    步骤2:
    选择随机扰动方向,改变H参数。
    如果不纯度指标提高,重复步骤1
    3、让I1 = 改变参数后H的不纯度指标,如果I1 < I, 设置I = I1.
    4、输出对应于I的划分平面。

    三、实验
    首先寻找轴平行时的最优初始化平面,用到的不纯度衡量指标是
    在这里插入图片描述TwoingValue表示划分的优良性,因此优化目标为最大化TwoingValue,若选择不纯度作为指标,则可使优化目标位最小化TwoingValue的倒数。

    寻找轴平行的最优化分平面的MATLAB代码:

    %寻找最优轴平行划分超平面
    melondata = [0.697	0.46	1
    0.774	0.376	1
    0.634	0.264	1
    0.608	0.318	1
    0.556	0.215	1
    0.403	0.237	1
    0.481	0.149	1
    0.437	0.211	1
    0.666	0.091	0
    0.23	0.267	0
    0.245	0.057	0
    0.343	0.099	0
    0.639	0.161	0
    0.657	0.198	0
    0.36	0.37	0
    0.593	0.042	0
    0.719	0.103	0];
    
    %划分属性和标签
    x_axis = melondata(:,1);
    y_axis = melondata(:,2);
    label_axis = melondata(:,3);
    %样本数量
    count = length(label_axis);
    
    %属性排序
    x_sort = sort(x_axis);
    y_sort = sort(y_axis);
    
    %划分点
    x_divide = (x_sort(2:count) + x_sort(1:count-1)) / 2;
    y_divide = (y_sort(2:count) + y_sort(1:count-1)) / 2;
    
    %计算TwoingValue
    tv = zeros(count-1, 2);
    tvmax = 0;
    for i = 1 : 2
        for j = 1 : count-1
            a_coe = [0,0,0];
            if i == 1
                a_coe(1) = 1;
                a_coe(3) = -x_divide(j);
            else
                a_coe(2) = 1;
                a_coe(3) = -y_divide(j);
            end
            %统计计算TwoingValue值所需要的参数
            tl = 0; tr = 0; lk = zeros(2,1); rk = zeros(2,1);
            for k = 1 : count
                p_coe = [x_axis(k), y_axis(k), 1]';
                v_i = a_coe * p_coe;
                if v_i < 0
                    tl = tl + 1;
                    if label_axis(k) == 0
                        lk(1) = lk(1) + 1;
                    else
                        lk(2) = lk(2) + 1;
                    end
                else
                    tr = tr + 1;
                    if label_axis(k) == 0
                        rk(1) = rk(1) + 1;
                    else
                        rk(2) = rk(2) + 1;
                    end
                end
            end
            tv(j,i) = tl / count * tr / count * (abs(lk(1) / tl - rk(1) / tr) + abs(lk(2) / tl - rk(2) / tr))^2;
            if tv(j,i) > tvmax
                tvmax = tv(j,i);
                a_coemax = a_coe;
            end
        end
    end
    

    画图显示:

    %寻找最优轴平行划分超平面
    %画出原始样本集
    xi = x_axis(label_axis == 1, 1);
    yi = y_axis(label_axis == 1, 1);
    plot(xi, yi, 'b+');
    xi = x_axis(label_axis == 0, 1);
    yi = y_axis(label_axis == 0, 1);
    hold on;
    plot(xi, yi, 'go');
    
    x = 0:0.1:0.9;
    y = ones(1,10) * 0.204500000000000;
    hold on;
    plot(x, y, 'r--');
    

    最终结果如下:
    在这里插入图片描述
    1、蓝色加号表示正例。
    2、绿色圆圈表示反例。
    3、红色虚线表示找出的划分平面,二维空间中是一条直线。

    四、结论
    找到轴平行的划分平面后,可以进行算法后续的步骤,未完待续。。。

    展开全文
  • :deciduous_tree: Python中的斜决策树 倾斜决策树实现的python接口: OC1 CART-线性组合(Breiman等,1984,第5章) 安装(Python 3) 首先使用以下命令安装numpy : pip install numpy 然后运行: pip install...
  • 斜决策树是归纳一颗以线性分类器作为划分平面的决策树,是多个属性的线性组合,不再是对单一属性的划分。划分平面的选择是一个NP难问题,很难精确找到问题的最优解,可以通过OC1算法,CART-LC算法寻找,也可以通过...

    一、结点划分平面的设计
    oc1算法是一种贪婪算法,先贪心的选择每个属性的最优权值,在加入随机扰动试图找到更好的边界。
    寻找属性最优权值的算法如下:
    在这里插入图片描述
    加入随机扰动,产生随机边界进行搜索算法:
    在这里插入图片描述
    二、matlab实验

    %寻找最优轴平行划分超平面
    melondata = [0.697	0.46	1
    0.774	0.376	1
    0.634	0.264	1
    0.608	0.318	1
    0.556	0.215	1
    0.403	0.237	1
    0.481	0.149	1
    0.437	0.211	1
    0.666	0.091	0
    0.23	0.267	0
    0.245	0.057	0
    0.343	0.099	0
    0.639	0.161	0
    0.657	0.198	0
    0.36	0.37	0
    0.593	0.042	0
    0.719	0.103	0];
    
    %划分属性和标签
    x_axis = melondata(:,1);
    y_axis = melondata(:,2);
    label_axis = melondata(:,3);
    %样本数量
    count = length(label_axis);
    
    a_coemax = [0, 1, -0.2045];
    %扰动a1
    %计算Vj
    d_data = [melondata(:,1:2), ones(count, 1)]';
    
    for m = 1 : 500
    for i = 1 : 3
        v_j = (a_coemax * d_data);
        u_j = (a_coemax(i) * d_data(i,:) - v_j) ./ d_data(i,:);
    
        u_sort = sort(u_j);
        u_divide = (u_sort(2:count) + u_sort(1:count-1)) / 2;
    
        a_coe = a_coemax;
    
        %计算TwoingValue
         tv = zeros(count-1, 2);
         tvmax = 0;
        for j = 1 : count-1
            a_coe(i) = u_divide(j);
            %统计计算TwoingValue值所需要的参数
            tl = 0; tr = 0; lk = zeros(2,1); rk = zeros(2,1);
            for k = 1 : count
                p_coe = [x_axis(k), y_axis(k), 1]';
                v_i = a_coe * p_coe;
                if v_i < 0
                    tl = tl + 1;
                    if label_axis(k) == 0
                        lk(1) = lk(1) + 1;
                    else
                        lk(2) = lk(2) + 1;
                    end
                else
                    tr = tr + 1;
                    if label_axis(k) == 0
                        rk(1) = rk(1) + 1;
                    else
                        rk(2) = rk(2) + 1;
                    end
                end
            end
            tv(j,i) = tl / count * tr / count * (abs(lk(1) / tl - rk(1) / tr) + abs(lk(2) / tl - rk(2) / tr))^2;
            if tv(j,i) > tvmax
                tvmax = tv(j,i);
                a_coemax = a_coe;
            end
        end
    end
    end
    

    斜划分边界如下:
    在这里插入图片描述
    对结点划分平面划分出的两个子集,若子集中全为同一属性样本,则作为叶子;若子集中不为同一属性样本,则作为叶结点,对此叶结点做下一步的划分。
    三、总结
    斜决策树是归纳一颗以线性分类器作为划分平面的决策树,是多个属性的线性组合,不再是对单一属性的划分。划分平面的选择是一个NP难问题,很难精确找到问题的最优解,可以通过OC1算法,CART-LC算法寻找,也可以通过遗传算法等启发式算法寻找。OC1算法是以爬山算法为基础,加入随机扰动试图跳出局部最优的一种算法,在构造分类边界上有很好的效果。作者证明算法最差的时间复杂度为O(N2logN)。

    展开全文
  • 决策树学习笔记

    2019-08-22 16:22:08
    生成的边界 横平竖直,所以数据如果有一点偏决策树得到的决策边界可能就不能很好的反馈数据的分布情况。 作为非参数学习算法,对个别数据样本点是非常敏感的。 改建 在机器学习领域,决策树更重要的一个应用是...

    决策树简介:
    非参数学习算法
    可以解决分类问题和回归问题
    天然可以解决多分类问题
    具有非常好的可解释性

    决策树的局限性:

    1. 生成的边界 横平竖直,所以数据如果有一点偏斜,决策树得到的决策边界可能就不能很好的反馈数据的分布情况。
    2. 作为非参数学习算法,对个别数据样本点是非常敏感的。
      改建
      在机器学习领域,决策树更重要的一个应用是使用集成学习的方式,创建随机森林的算法。 随机森林的算法可以得到非常好的学习结果。

    决策树对于回归问题的解决方式为:
    用最终落在叶子结点的所有样本数据的平均值当作回归问题的预测值

    决策树的关键:
    每个节点在哪个维度做划分
    某个维度在哪个值做划分
    才能使得划分后,信息熵降低?

    信息熵:
    熵越大,在热力系统中,粒子的无规则运动越剧烈,也就是不确定性越高;
    熵越小,越倾向于静止的状态,也就是不确定越低。

    一个系统的信息熵总和的计算
    H=i=1kpilog(pi)H = \sum\limits_{i=1}^k p_i log(p_i)
    当系统中,每一个类别都是等概率的时候,是他最不确定的时候。此时的信息熵是最高的。如果系统偏向于某一类,就相当于一定程度上有了确定性,信息熵会逐渐降低,直到我们的系统百分百的都在某一类中,此时信息熵达到最低值,也就是0。

    基尼系数
    G=1i=1kpi2G = 1- \sum\limits_{i=1}^k p_i^2

    对比信息熵与基尼系数:
    信息熵的计算比基尼系数慢
    scikit_learn中默认为基尼系数
    大多数二者没有特别的效果优劣
    信息熵在0-1区间内分布,Gini系数在0-0.5内分布

    使用信息熵进行CART决策树(Classification And Regression Tree)的构建:
    根结点具有全部的数据,在根结点的基础上,要找到一个维度,一个阈值,对根节点进行划分,划分后希望数据的整体信息熵是减少的。
    进而对于划分出来的这两个节点,我们可以再用同样的方式去寻找特定的维度和阈值进行划分,使得整体的信息熵进一步减小。这样的过程递归下去,就形成了决策树。
    预测时的复杂度:O(logm)
    训练时的复杂度:O(nmlogm)

    CART剪枝参数:
    min_samples_split
    min_samples_leaf
    min_weight_fraction_leaf
    max_depth
    max_leaf_nodes
    max_features

    ID3 (Iterative Dichotomiser 3)构建的树是多分类的样子,按照某一列进行切分。

    局限性:

    • 分支度越高(分类水平越多)的离散变量往往子节点的总信息熵会更小,ID3是按照某一列进行切分,有一些列的分类可能不会对我们需要的结果有足够好的指示。极端情况下取ID作为切分字段,每个分类的纯度都是100%,但这样的分类方式是没有效益的
    • 不能直接处理连续型变量,若要使用,则需要对连续性变量进行离散化
    • 对缺失值较为敏感,使用ID3之前要提前对缺失值进行处理
    • 没有剪枝的设置,容易导致过拟合。

    C4.5 (ID3算法的改进)

    1. 使用信息增益率(Gain Ratio)作为选取切分字段的参考指标
      GainRatio=InformationGainInformationValueGain Ratio = \frac{Information Gain}{Information Value}
      其中InformationValues=i=1kP(vi)log2P(vi)Information Values = -\sum\limits_{i=1}^k P(v_i)log_2P(v_i)
      viv_i为子节点中样本量占父节点样本量的比例

    我们选择 信息增益率最大的那一列,本质是信息增益最大,分支度又较小的列(也就是纯度提升很快,但又不是靠着把类别分 特别细 来提升 那些特征)

    1. 添加连续变量处理手段
      如果输入特征字段是连续性变量,则有下列步骤:
      1. 算法首先对这一列数从小到大排序
      2. 选取相邻的两个数的中间数作为切分数据集的备选点,此时针对连续变量的处理并非将其转化为一个拥有N-1个分类水平的分类变量,而是将其转化为N-1个二分方案。

    当连续变量的某中间点参与到 决策树的二分过程中,往往代表该点对最终分类结果有较大影响,也为我们对连续变量的分箱压缩提供了指导性意见。也这是决策树的最常见用途之一,指导模型分箱。

    CART(C4.5进一步改进)
    现在被大量使用的是C4.5改进的CART树,CART树本质上和C4.5区别不大,只不过CART树的所有层都是二叉树,也就是每层只有两个分支。

    决策树对比KNN算法:
    对于KNN,我们假设,每一个特征对于我们的推断的重要性是一样的,这也是KNN最大的缺陷。而决策树天生就认为每个特征对于推断的重要性是不一样的,而CART则进一步认为,每个特征下的每个分类对于推断的重要性也是不一样的。

    展开全文
  • 多变量决策树

    千次阅读 2018-10-20 09:09:45
      但在学习任务的真实分类边界比较复杂时,必须使用很多段划分才能获得较好的...多变量决策树使用的划分边界,在此类决策树中,非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试。    ...

     

     

    但在学习任务的真实分类边界比较复杂时,必须使用很多段划分才能获得较好的近似。多变量决策树使用斜的划分边界,在此类决策树中,非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试。

     

     

    展开全文
  • 2.3决策树之基尼系数

    万次阅读 2016-02-08 11:09:36
    在CART里面划分决策树的条件是采用Gini Index,定义如下: gini(T)=1−sumnj=1p2j 其中,( p_j )是类j在T中的相对频率,当类在T中是倾斜的时,gini(T)会最小。 将T划分为T1(实例数为N1)和T2(实例数为N2)两...
  • 人工智能与信息社会 基于决策树和搜索的智能系统实例2 井字棋 陈斌北京大学gischen@ 井字棋 井字棋(Tic-Tac-Toe)是由两个玩家轮 流在3乘3的格上打自己的符号 圈或 者叉最先以横直连成一线 则为胜 北京大学地球与...
  • 从二分类问题来看,可以看到,信息熵越是小的,说明分类越是偏(明确),可以理解为信息熵就是为了消除分类不确定性的,决策树本就是根据一个个问题的答案去尽可能明确的找出规律去告诉别人这条数据的类别,如果说...
  • 通过交互基函数在决策树中诱导非正交和非线性决策边界 Paez,A.,López,F.,Ruiz,M.,Camacho,M.,2019年。通过交互基础函数在决策树中诱导非正交和非线性决策边界。 具有应用程序的专家系统122,183-206。 抽象...
  • 倾斜决策树的合奏 作者:Torsha Majumder 电子邮件: 背景 该存储库包含几种与Scikit-Learn的Bagging分类器兼容的决策树算法。 有关完整的实验设置和结果,请检查。 如果您认为此代码有用,请引用我的工作。 引文 ...
  • 数据分类分析

    2021-03-18 15:18:37
    一、决策树算法 首先,顾名思义,决策树是基于树结构来进行决策的。树可以表达类和属性的关系。 1.决策树的基本组成部分:决策结点、分支和叶子。 2.如何选择叶子结点——选择最佳划分(属性)的度量 选择最佳划分的...
  • 递归题的解法:首先把题目的决策树画出来,树的层就是for循环,树的深度就是要递归的参数i。画出决策树后,找规律,进行剪枝。 皇后横竖方向的棋子都会被吃掉,棋盘每行只能放一个皇后。 E.g. 输入 n = 4 树的层...
  • 针对以往使用单一因素预测底板破坏深度误差较大的问题,基于开源数据挖掘工具Weka平台,以底板破坏因素为样本应用贝叶斯分类器、支持向量机、神经网络、决策树和随机森林模型实现对底板破坏深度数据的整理挖掘分析,从...
  • 数据结构与算法 搜索算法 快排 弦乐 单模式匹配算法 BF(Brute Force)算法 RF(Rabin-Karp)算法 BM(Boyer-Moore)算法 KMP算法 多模式匹配算法(未完成) ...一个问题经历多个决策,每个决策对应一个决策状态。
  • 分类:基本概念、决策树与模型评估 分类的定义:分类任务就是通过学习得到一个目标函数f,把每个属性集x映射到一个预先定义的类标号y。 目标函数也称为分类模型,有两个主要目的:1、描述性建模 2、预测性建模 分类...
  • 该算法通过提取运动时的超重强度、持续失重时间、倾斜角度、静止时间为特征值,在 Android智能手机上使用决策树进行实时处理. 该算法对传感器的放置方位无要求,选取日常动作和与跌倒加速度特征相似的动作进行测试...
  • Udacity_机器学习

    2016-07-09 15:31:00
    决策树(ID3算法、信息熵[父节点的信息熵=1]、信息增益) 计算信息熵 分类和回归 准确率的缺陷: 对于偏类(有很多样本点,但属于该类别的数目特别少) 绝不错杀一个 宁可天下人负我(试图找出...
  • 滴滴数据分析实习面经 自我介绍 指标异动分析 机器学习算法对于数据分析的应用理解 sql题,就是说了说,但是自己答的太差了 个人项目的问题,基本就是... 随机森林算法原理、是否可以替换决策树算法 ID3、C4.5、
  • 回归模型的功能一般是预测,分为线性回归,决策树(回归树),支持向量机(SVR) 1.线性回归 线性回归一般使用的公式如下: y’ = w[0]*x[0] +w[1]*x[1] +w[2]*x[2] +… +w[p]*x[p] +bias x[0]到x[p] 表示单个数据点的...
  • 评估指标 由要解决的问题选择性能指标,然后测试模型表现。 准确度:某特定类别中我们正确标记并正确识别为此类别的项目或数据点的数量,除以该类别中全部项目或数据点的数量。...决策树混淆矩阵召回率(Recall)
  • 极小化极大算法是基于决策树和搜索的智能系统中的典型算法,可用于指导井字棋、黑白棋、五子棋等经典完全信息零和博弈。虽在学生时代学习过极小化极大算法,但时过境迁,思量该算法的来龙去脉已然如雾里探花水中望月...
  • 问题描述: 如何将 n 个皇后放置在 n×n 的棋盘上,...解决该回溯问题,实际上就是一个决策树的遍历过程 算法思路: 第一个皇后理论上可以选择棋盘上任何一个落点,依次尝试第一个皇后的可能落点,对于第一个皇后...
  • 最近想构建一个机器学习模型,用于识别图像形状问题(如:三角形[(0,0),(1,1),(2,0)] 正方形[(0,0),(2,0),(2,2),(0,2)] 正方形[(0,0),(1,1),(2,0)],(1,-1) ),最初采用决策树进行,数据分类。但在构建数据训练集时...
  • 虚拟体验卡介苗 该存储库包含我在BCG GAMMA上的虚拟体验方面的工作。 感谢Ken Jee提供了在GitHub上记录项目的通用... 运行基线模型后,我使用了健壮的模型:随机森林,决策树,梯度提升,AdaBoosting和XGBoost。 Xgbo
  • 7.9.1 决策树 7.10 桶式排序 7.11 外部排序 7.11.1 为什么需要新的算法 7.11.2 外部排序模型 7.11.3 简单算法 7.11.4 多路合并 7.11.5 多相合并 7.11.6 替换选择 总结 练习 参考文献 第...
  • 7.9.1 决策树 7.10 桶式排序 7.11 外部排序 7.11.1 为什么需要新的算法 7.11.2 外部排序模型 7.11.3 简单算法 7.11.4 多路合并 7.11.5 多相合并 7.11.6 替换选择 总结 练习 参考文献 第8章 不相交集ADT ...
  • C++实现九宫格游戏人机对战

    千次阅读 2015-08-23 11:37:25
    九宫格游戏是大家熟悉的“草稿...期间主要运用九宫格的对称性以及等价位置来画博弈来实现决策。 大致四个决策顺序: 1.看自己是否连成两个。2.看对方是否连成两个。3.特殊情况讨论。4.已是绝对平局情况,找到第一个

空空如也

空空如也

1 2 3
收藏数 42
精华内容 16
关键字:

斜决策树