精华内容
下载资源
问答
  • 这是一篇关于决策树算法的MATLAB实现的文章,也是我的课堂实验,学习的书籍为西瓜书。此文章包含树的建立(使用信息增益,基尼指数),绘图,预测以及剪枝(后剪枝),部分代码为老师提供。文章中所有的代码以及老师...

    [机器学习]决策树算法的MATLAB实现
    这是一篇关于决策树算法的MATLAB实现的文章,也是我的课堂实验,学习的书籍为西瓜书。此文章包含树的建立(使用信息增益,基尼指数),绘图,预测以及剪枝(后剪枝),部分代码为老师提供。文章中所有的代码以及老师提供的代码以及实验的要求都在以下连接,需要可以自取。应该说,最好就是跟着实验要求去做,然后不懂或者看不明白再来看这里面的代码,应该会对决策树有更加深刻的了解。假如大家对决策树有什么不了解,可以问我,我会尽量解答(当然我属实能力有限,毕竟才开始学,一起努力吧,冲冲冲)当然代码略微杂乱。而且matlab现在似乎提供了决策树等算法的生成包,大家可以自行查略,本文并不涉及。以下为正文

    链接:https://pan.baidu.com/s/1ioCVZTNyCZiD0GM9Vy3L4w 
    提取码:v432 
    当然我的csdn资源中应该也有这个资源(写完这个应该就会去上传吧)
    大家如果觉得还不错可以支持一下
    

    一 .内容

    1. 基于 西瓜数据集2.0 的ID3决策树算法实现
      数据集watermelon.mat,来自教材中的西瓜数据集2.0,共有18个样本数据。实验中,选取其中的16个样本构成训练集,其余2个样本构成测试集。基于ID3算法采用训练样本构造决策树,并简单绘出生成的决策树。最后,测试该决策树对测试样本的类别划分情况。

    2. 基于 Breast Cancer癌症数据集 分析ID3决策树的分类精度
      数据集breastcancer.mat中,有277个样本数据,每个数据有9个属性特征以及一个类别标签。基于前述构造ID3决策树的算法程序,试采用10次10折交叉验证法评估ID3决策树模型在此数据集上的分类精度(注:分类精度的度量方法参见教材P29公式2.5)。
      (这一部分我的最后结果是90的正确率还是挺开心的嘿嘿。
      (不剪枝的话应该66左右。剪枝nb!

    二.具体实现
    ##基于西瓜数据集2.0的ID3决策树算法实现
    (一)要求.
    数据集watermelon.mat,来自教材中的西瓜数据集2.0,共有18个样本数据。实验中,选取其中的16个样本构成训练集,其余2个样本构成测试集。基于ID3算法采用训练样本构造决策树,并简单绘出生成的决策树。最后,测试该决策树对测试样本的类别划分情况。

    (二)过程

    1. 主函数:导入数据集,划分训练集与测试集,构造决策树 Main_DecisionTree.m
    2. 子函数ID3():基于ID3算法构造决策树 ID3.m
    3. 子函数chooseFeature():选择信息增益最大的属性特征 chooseFeature.m
    function bestFeature=chooseFeature(dataset,~)
    % 选择信息增益最大的属性特征
     %数据预处理
    [N,M]=size(dataset);                %样本数量N
    M=M-1;                              %特征个数M
    y=strcmp(dataset(:,M+1),dataset(1,M+1)); %标签y(以第一个标签为1)
    x=dataset(:,1:M);                   %数据x
    gain = (1:M);                       %创建一个数组,用于储存每个特征的信息增益
    %bestFeature;                       %最大信息增益的特征
    Ent_D=calShannonEnt(y);             %当前信息熵
    %计算信息增益
    for i=1:M
        % 计算第i种属性的增益
        temp=tabulate(x(:,i));
        value=temp(:,1);            %属性值
        count=cell2mat(temp(:,2));  %不同属性值的各自数量
        Kind_Num=length(value);     %取值数目
        Ent=zeros(Kind_Num,1);
        % i属性下 j取值的信息熵
        for j=1:Kind_Num
            % 在第j种取值下正例的数目
            Ent(j)= calShannonEnt( y(strcmp(x(:,i),value(j))) );
        end
        gain(i)=Ent_D-count'/N*Ent;
    end
    %随机挑选一个最大值
    max_gain=find(gain==max(gain));
    choose=randi(length(max_gain));
    bestFeature=max_gain(choose);
    %%%%============================================
    end
    

    (1)对数据进行预处理
    这里对数据的标签进行了特殊处理
    y=strcmp(dataset(:,M+1),dataset(1,M+1)); %标签y(以第一个标签为1)
    因为是二分类问题,所以将标签调整的为logical数组,与第一个相同的为1.不相同的为0,方便后续的计算信息熵的处理。
    (2)计算信息熵
    先利用tabulate来获取每个属性下的不同取值以及其数量

       temp=tabulate(x(:,i));
       value=temp(:,1);            %属性值
       count=cell2mat(temp(:,2));  %不同属性值的各自数量
    

    这里以此对每一个属性取值调用calShannonEnt函数来计算信息熵

    Ent(j)= calShannonEnt( y(strcmp(x(:,i),value(j))) );
    

    这里y(strcmp(x(:,i),value(j)))是选取了和x(:,i)和value(j)相同的取值对应的y传递给calShannonEnt去计算信息熵
    (3)随机选取最大的信息熵

    max_gain=find(gain==max(gain));
    choose=randi(length(max_gain));
    bestFeature=max_gain(choose);
    

    这是为了应对当有多个最大的属性特征时的情况,这里我解决的方法是随机从中随机挑选出一个作为最大值,所以也因此,虽然输入数据相同,但训练输出的树也会因此而可能发生不同。

    4.子函数calShannonEnt():计算信息熵 calShannonEnt.m

    function shannonEnt = calShannonEnt(y)
    % 计算信息熵
    % y对应的标签,为1或0,对应正例与反例
        N=length(y);            %标签长度
        P_T=sum(y)/N;           %正例概率
        P_F=(N-sum(y))/N;         %反例概率
        if(P_T==0||P_F==0)
            %使得p*log2p为0
            shannonEnt = 0; 
            return
        end
        shannonEnt=-(P_T*log2(P_T)+P_F*log2(P_F));  %信息熵
    end
    

    因为传入的为[1,0]的逻辑数组,所以正例可以直接使用sum/N来计算。后面根据信息熵的约定当p=0信息熵p*log2p为0,所以加入了中间的一句判断,来返回该情况

    5.子函数splitDataset():划分数据集 splitDataset.m
    6.子函数print_tree():遍历决策树 print_tree.m
    7.子函数tree_plot():绘出决策树tree_plot.m
    8.利用子函数predict()对测试样本进行分类predict.m文件

    对训练样本进行类别划分的代码如下:
    %----------------------------------------------
    y_test=predict(x_test,mytree,labels);
    fprintf('测试样本的分类标签为:');
    disp(y_test);
    %-----------------------------------------------
    

    (三)实验结果
    决策树图像:
    生成的决策树
    输出:

    测试样本的分类标签为:    '否'    '否'
    

    即对
    ‘浅白’ ‘蜷缩’ ‘浊响’ ‘模糊’ ‘平坦’ ‘硬滑’ ‘否’
    ‘青绿’ ‘蜷缩’ ‘沉闷’ ‘稍糊’ ‘稍凹’ ‘硬滑’ ‘否’
    这两个样本的预测为都为否,预测结果与原标签相同

    ##基于Breast Cancer数据集分析ID3决策树的分类精度
    (一)要求

    数据集breastcancer.mat中,有277个样本数据,每个数据有9个属性特征以及一个类别标签。基于前述构造ID3决策树的算法程序,试采用10次10折交叉验证法评估ID3决策树模型在此数据集上的分类精度(注:分类精度的度量方法参见教材P29公式2.5)。

    (二)实验过程
    1.predict函数的修改
    在predict中,因为数据集的标签不能包含所有标签,所以当测试集中出现了数据集中没有的标签时,将无法进行预判而返回空数组,比如年龄这一个属性在训练集中没有20-39这个属性但出现在测试级中,将会无法返回预测标签。所以对其进行更改为:

    hasKeys=0;
    keys = node.keys();
    for i = 1:length(keys)
         key = keys{i};
         c = char(feature);
         if strcmp(key,c)
             queue=[queue,{node(key)}]; %队列变成该节点下面的节点
             hasKeys=1;
         end
    end
    if(~hasKeys)
        key = keys{randi(length(keys))};
    queue=[queue,{node(key)}];                  
    end
    

    即随机选取一个属性值进行预判,接下去进行预测

    2.主函数
    主函数包含3部分:数据读取,10次10折交叉验证,结果输出。因为是2分类,所以数据读取部分中将与第一个标签相同的分为一层,另一个分为另一层。最后将随机采样的得到结果存储在D_index中,其维度为(每个数据组)*10,10个列向量中每一个维度都存这一组原数的索引。在这之中为了数据维度保持一致,放置同一个数组中所以将部分数据舍弃了,保持数据维度一致

    % breastcancer数据集
    %-----------------数据读取----------------------
    clear
    clc
    load('breastcancer.mat')
    size_data = size(breastcancer); %breastcancer 为导入工作台的数据
     
    %-------------10次10折交叉验证-------------------
    k_time=10;
    crossValidation_time=10;
    y_lable=breastcancer(2:size_data(1),size_data(2));
    T_P=zeros(k_time,crossValidation_time);
    for i=1:crossValidation_time
        %分为训练集和测试集(10折),
        y_1=find(strcmp(y_lable(:),y_lable(1)));%与第一个标签相同的为一层次
        y_2=find(~strcmp(y_lable(:),y_lable(1)));%其余为另一个层次
        y_1_length=length(y_1);
        y_2_length=length(y_2);
        y_1_perNum=floor(y_1_length/k_time);
        y_2_perNum=floor(y_2_length/k_time);
        y_1_randIndex=randperm(y_1_length);
        y_2_randIndex=randperm(y_2_length);
        D_index=zeros(y_1_perNum+y_2_perNum,k_time); %D中存放了10组数据索引
        for j=1:k_time                          %有数据被丢弃
            D_index(:,j)=[...
                y_1(y_1_randIndex(y_1_perNum*(j-1)+1:y_1_perNum*j));...
                y_2(y_2_randIndex(y_2_perNum*(j-1)+1:y_2_perNum*j))];
        end
        D_index=D_index+1;
        perNum_D=y_1_perNum+y_2_perNum;
        %训练10折交叉验证
        for k=1:k_time
            %获取此时的数据集以及测试集
            x_train = breastcancer(...
                [1; reshape(D_index(:,1:k-1),[],1);...
                 reshape(D_index(:,k+1:k_time),[],1)],:) ;     %这里加上了属性标签行
            x_test = breastcancer(D_index(:,k),:);  %选择最后两个当测试集
            %训练
            size_data = size(x_train);
            dataset = x_train(2:size_data(1),:); %纯数据集
            labels = x_train(1,1:size_data(2)-1); %属性标签
            %生成决策树
            mytree = ID3_2(dataset,labels);
            %预测测试集标签并计算精度
            y_test=predict_2(x_test(:,1:end-1),mytree,labels);
            T_P(i,k)=sum(strcmp(y_test',x_test(:,end)))/perNum_D;
        end
    end
    %----------------结果输出-------------------------
    fprintf('10次10折交叉验证的精度结果为:\n');
    for i=1:10
        fprintf('第%d次:%f\n',i,mean(T_P(i,:)));
        fprintf('\t%f\t%f\t%f\t%f\t%f\n',T_P(i,1:5));
        fprintf('\t%f\t%f\t%f\t%f\t%f\n',T_P(i,6:10));
    end 
    fprintf('平均精度为:%d\n',mean(mean(T_P)));
    

    (三)实验结果

    10次10折交叉验证的精度结果为:
    第1次:0.618519
    	0.592593	0.629630	0.518519	0.666667	0.555556
    	0.444444	0.666667	0.592593	0.777778	0.740741
    第2次:0.637037
    	0.740741	0.666667	0.592593	0.370370	0.592593
    	0.703704	0.629630	0.666667	0.666667	0.740741
    第3次:0.674074
    	0.703704	0.629630	0.777778	0.703704	0.666667
    	0.555556	0.703704	0.703704	0.629630	0.666667
    第4次:0.655556
    	0.629630	0.518519	0.629630	0.629630	0.666667
    	0.703704	0.666667	0.740741	0.666667	0.703704
    第5次:0.681481
    	0.703704	0.777778	0.814815	0.666667	0.740741
    	0.555556	0.703704	0.814815	0.518519	0.518519
    第6次:0.670370
    	0.629630	0.740741	0.629630	0.740741	0.629630
    	0.703704	0.703704	0.592593	0.629630	0.703704
    第7次:0.677778
    	0.592593	0.777778	0.666667	0.629630	0.703704
    	0.740741	0.666667	0.740741	0.555556	0.703704
    第8次:0.659259
    	0.629630	0.629630	0.814815	0.666667	0.851852
    	0.629630	0.555556	0.666667	0.592593	0.555556
    第9次:0.685185
    	0.703704	0.740741	0.555556	0.703704	0.703704
    	0.629630	0.666667	0.666667	0.666667	0.814815
    第10次:0.670370
    	0.777778	0.666667	0.740741	0.518519	0.666667
    	0.740741	0.629630	0.481481	0.740741	0.740741
    

    平均精度为:0.662963
    即最后得到的精度为0.662963,多次运行的结果在0.659,0.665的范围左右不会相差太远

    (四)改进
    1.使用基尼指数来作为选择指标
    这里与之前的计算信息增益基本相同,最后选择的指标改为了最小的而非最大

    function bestFeature=chooseFeatureGini(dataset,~)
    % 选择基尼指数最小的属性特征
     
     %数据预处理
    [N,M]=size(dataset);                %样本数量N
    M=M-1;                              %特征个数M
    y=strcmp(dataset(:,M+1),dataset(1,M+1)); %标签y(以第一个标签为1)
    x=dataset(:,1:M);                   %数据x
    Gini_index = zeros(1,M);            %创建一个数组,用于储存每个特征的信息增益
    %bestFeature;                       %最大基尼系数的特征
     
    %计算基尼指数
    for i=1:M
        % 计算第i种属性的基尼指数
        temp=tabulate(x(:,i));
        value=temp(:,1);            %属性值
        count=cell2mat(temp(:,2));  %不同属性值的各自数量
        Kind_Num=length(value);     %取值数目
        Gini=zeros(Kind_Num,1);
        % i属性下 j取值的基尼指数
        for j=1:Kind_Num
            % 在第j种取值下正例的数目
            Gini(j)= getGini( y(strcmp(x(:,i),value(j))) );
        end
        Gini_index(i)=count'/N*Gini;
    end
    %随机挑选一个最小值
    min_GiniIndex=find(Gini_index==min(Gini_index));
    choose=randi(length(min_GiniIndex));
    bestFeature=min_GiniIndex(choose);
    end
    

    用于计算基尼指数的代码:

    function Gini = getGini(y)
    % 计算基尼系数
    % y对应的标签,为1或0,对应正例与反例
    %%%%%%========================================
        N=length(y);            %标签长度
        P_T=sum(y)/N;           %正例概率
        P_F=1-P_T;              %正例概率
        Gini=1-P_T*P_T-P_F*P_F;  %基尼系数
    %%%%%%=====================================
    end
    

    在做这部分改动之后,10次10折交叉验证精度影响较小,基本与之前相同。

    2.当叶子节点时,找最多的标签值,而非选取第一个
    这一步将ID3的部分代码修改如下

    size_data = size(dataset);
    classList = dataset(:,size_data(2));
    %%属性集为空,找最多数
    temp=tabulate(classList);
    value=temp(:,1);            %属性值
    count=cell2mat(temp(:,2));  %不同属性值的各自数量
    index=find(max(count)==count);
    choose=index(randi(length(index)));
    nodeLable =  char(value(choose));
    if size_data(2) == 1
        myTree =  nodeLable;
        return
    end
    

    3.在没有对应属性值的情况下,输出当前节点在训练时的最多标签值
    这一部分是为了应对训练集中没有测试集的对应属性值,或者后续将该模型用于预测时没有对应属性值的情况。不使用之前的随机选择节点继续,因为这样可能会带来新的误差。比如没有年龄10-19的标签,却随机到了60-69的标签,这样带来更大的误差。而且会出现模型对相同的数据输出不一样标签的情况。所以在leaf中,加入一个标签,用于记录当前节点的数据的最多标签。

    leaf('nodeLabel')= nodeLable;
    

    nodeLable为当前节点的数据的最多标签。当然标签不会作为属性值进入预测节点。
    所以对预测脚本predict_2.m进行修改:

    在 string(class(node))=="containers.Map" %的情况时加入
    %除去nodelable标签(不影响检测)
    keys = node.keys();
    index=find(strcmp(keys,'nodeLabel'));
    if(~isempty(index))
         keys=[keys(1:(index-1)),keys((index+1):end)];
    end
    

    这修改后,10次10折交叉验证精度比之前的65%-66%有小幅度提升,在68%-69%左右

    4.去除没有划分能力的节点
    当属性只有一种值时,会产生没有划分能力的节点,比如在训练时出现年龄属性中只有10-19的一种属性,那么该属性将剔除而不会被加入训练中。这样可以使树的模型更加简单而且在判断是否为节点时更加容易,边必然有多个keys,而节点只有一个。
    对ID3的%全为同一类,熵为0以及%属性集为空这2个部分中间加入

    %去除完全相同的属性,避免产生没有分类结果的节点
    choose=ones(1,size_data(2));
    for i=1:(size_data(2)-1)
        featValues = dataset(:,i);
        uniqueVals = unique(featValues);
        if(length(uniqueVals)<=1)
            choose(i)=0;
        end
    end
    labels=labels((choose(1:size_data(2)-1))==1);
    dataset=dataset(:,choose==1);
    

    5.后剪枝
    这依赖到之前3,加入了leaf(‘nodeLabel’)= nodeLable,即在leaf中加入了原本在训练是当前数据集在这个节点的最多标签值

    function [correct,tree_pruning] = pruning(x_V,tree,feature_list)
    %-----------------剪枝-------------------------
    %correct:返回的数据集的预测值正确程度数组,1为预测正确
    %tree_pruning:剪枝后的数组
    %x_V:训练集
    %tree:剪枝前的树
    %feature_list:训练集的标签
    if(string(class(tree))~="containers.Map")
        %达到叶节点,计算标签与当前数据的真实标签的异同
        %将结果保存在correct数组中
        correct=strcmp(x_V(:,end),tree)';
        tree_pruning=tree;%返回原本的节点
        return;
    else
        size_data = size(x_V);
        labels=feature_list;            %数据的属性
        Feature=char(tree.keys);        %当前节点的属性
        FeatureIndex=strcmp(labels,Feature);%节点属性在所有属性中的索引
        FeatureValue=x_V(:,FeatureIndex);   %所有属性
        x_V=x_V(:,logical([~FeatureIndex,1])); %删除该特征
        feature_list=feature_list(~FeatureIndex);
        theTree = containers.Map;%新的节点以及边
        theLeaf = containers.Map;
        leaf=tree(Feature);%原本的叶子节点
        keys=leaf.keys;    %获取属性的取值
        %除去nodelable标签(不影响检测)
        index=find(strcmp(keys,'nodeLabel'));
        if(~isempty(index))
            keys=[keys(1:(index-1)),keys((index+1):end)];
        end
     
        correct=[];  %数据将包含目前数据预测的正确与否,为0-1数组
        for i=1:length(keys)
            value=keys{i};
            x_V_value=x_V(strcmp(FeatureValue,value),:); %删除拥有特征的数量
            if(~isempty(x_V_value))
                %数据集里有该取值,计算预测结果正确与否
                [correct_per,theLeaf(value)] = pruning(x_V_value,leaf(value),feature_list);
                correct=[correct,correct_per];
            else
                %数据集里没有该取值,保留原本的节点
                theLeaf(value)=leaf(value);
            end
        end
        theLeaf('nodeLabel')= char(leaf('nodeLabel'));%获取之前的节点
        theTree(Feature) = theLeaf;                     
        
        acc = sum(correct)/length(correct);%原本的精度 
        acc_pruning = strcmp(x_V(:,end),leaf('nodeLabel'))/size_data(1);%不划分的精度 
        if(acc<=acc_pruning)
            %假如不划分的精度更高,那么选取原本训练时最多的标签
            tree_pruning= char(leaf('nodeLabel'));
        else
            %保留树
            tree_pruning=theTree;
        end
    end
     
    end
    

    此时需要丢数据进行一些改动:
    (1)得到验证集用于剪枝
    这里选用了,8个数据集用于训练,1个用于验证,1个用于测试

    if k~=k_time
          x_train = breastcancer(...
              [1; reshape(D_index(:,1:k-1),[],1);...
              reshape(D_index(:,k+2:k_time),[],1)],:) ;     %这里加上了属性标签行
    else
          x_train = breastcancer([1; reshape(D_index(:,2:k-1),[],1)],:) ;     %这里加上了属性标签行
    end
    x_valid = breastcancer(D_index(:,k),:);                 %选择验证集
    x_test = breastcancer(D_index(:,mod(k+1,k_time)+1),:);  %选择测试集
    

    (2)用剪枝后的数据集去验证

    %剪枝
    [correct,tree_pruning] = pruning(x_valid,mytree,labels);      
    %----------------------------------------------
    y_test=predict_2(x_test(:,1:end-1),tree_pruning,labels);
    T_P(i,k)=sum(strcmp(y_test',x_test(:,end)))/perNum_D;
    %-----------------------------------------------
    

    (五)改进结果
    上述所有的改进之后,决策树的精度得到了很大的提升,在89% 90%左右

    10次10折交叉验证的精度结果为:
    第1次:0.885185
    	0.925926	0.888889	0.888889	0.888889	0.851852
    	0.925926	0.925926	0.925926	0.777778	0.851852
    第2次:0.914815
    	0.962963	0.888889	0.962963	0.925926	0.851852
    	0.851852	0.888889	0.888889	1.000000	0.925926
    第3次:0.888889
    	0.925926	0.888889	0.888889	0.888889	0.851852
    	0.851852	0.888889	0.851852	0.925926	0.925926
    第4次:0.918519
    	0.888889	0.888889	0.962963	0.962963	0.888889
    	0.888889	0.851852	0.925926	0.925926	1.000000
    第5次:0.896296
    	0.740741	0.925926	0.962963	0.925926	0.925926
    	0.851852	0.925926	0.925926	0.888889	0.888889
    第6次:0.903704
    	0.851852	0.888889	0.888889	0.925926	1.000000
    	0.925926	0.925926	0.814815	0.851852	0.962963
    第7次:0.907407
    	0.962963	0.851852	0.740741	0.925926	0.962963
    	0.925926	0.925926	0.851852	0.962963	0.962963
    第8次:0.918519
    	0.962963	0.888889	0.888889	0.851852	1.000000
    	1.000000	0.888889	0.888889	0.962963	0.851852
    第9次:0.896296
    	0.925926	0.925926	0.851852	0.851852	0.925926
    	0.814815	0.888889	0.962963	0.925926	0.888889
    第10次:0.918519
    	0.925926	0.851852	0.888889	0.925926	0.888889
    	0.925926	0.962963	0.851852	1.000000	0.962963
    平均精度为:0.904815
    

    END
    到此结束啦,谢谢你能看到这,感谢。你有自己试着去实现吗?你的精度又是多少呢?886

    展开全文
  • 机器学习之决策树

    2021-01-11 16:15:17
    这里仅做核心介绍,关于决策树的详细介绍请看其他机器学习书籍。 决策树的构建根据其分支依据(ID3算法, C4.5算法, CART算法)大致有三种方法: 一、ID3算法: ID3算法是说在树分裂时选取能获得最高信息增益的特征...

    这里仅做核心介绍,关于决策树的详细介绍请看其他机器学习书籍。
    决策树的构建根据其分支依据(ID3算法, C4.5算法, CART算法)大致有三种方法:

    一、ID3算法:

    ID3算法是说在树分裂时选取能获得最高信息增益的特征进行分裂。什么意思呢?就是说我们要建立决策树嘛,首先得找一个特征做为树根,对于众多的特征,到底选哪个呢?当选择某个特征feature_1做为树根时,分裂的分支数就是feature_1特征的取值种类,那么到第二层选择分裂节点时又面临当初选择树根时的抉择。聪明的科学家们发现如果我们用一个叫做信息增益的东西来选取根节点,决策树构建即快又矮。那什么是信息增益呢?
    首先从熵谈起:

    1.熵

    在决策树的构建中我们可以理解熵就是用来衡量样本纯度的指标:
    Entropy(S)=i=1Npilog2(pi);pi=Cin Entropy(S) = - \sum_{i=1}^N p_i log_2(p_i);\quad p_i = \frac{\vert C_i \vert}{n}
    其中:Ci 表示i类的样本数,n表示样本总数。假设我们有m类,每一类样本所占的比列就是pi。

    2.信息增益

    信息增益就是计算分支属性对于样本集分类好坏程度的度量:
    Gain(S,feature1)=Entropy(S)i=1nSiSEntropy(Si) Gain(S, feature_1) = Entropy(S) - \sum_{i=1}^n \frac{\lvert S_i \lvert}{\lvert S \lvert} Entropy(S_i)
    其中:
    i=1nSiSEntropy(Si)\sum_{i=1}^n \frac{\lvert S_i \lvert}{\lvert S \lvert} Entropy(S_i) 表示依据feature_1划分后的总信息熵。
    Entropy(S)Entropy(S) 表示划分前的总信息熵。
    使得Gain(S, feature_1)最大的那个特征即为本次选择的分裂特征。

    二、C4.5算法

    ID3存在两个缺点:
    1.无法处理连续型特征。
    2.使用信息增益作为分裂的依据,会导致模型在选择分裂特征时,倾向于选择分叉比较多的特征。
    C4.5解决了ID3存在的不足。在C4.5中提出了“分裂信息”的概念。
    SplitInfoA(S)=j=1mSiSlog2SiS SplitInfo_A(S) = - \sum_{j=1}^m \frac{\lvert S_i \lvert}{\vert S \vert}log_2 \frac{\lvert S_i \lvert}{\vert S \vert}
    其中,训练数据集S通过特征A的m种取值将数据集划分为m个子数据集,|Sj|表示第j个子数据集中的样本个数,|S|表示划分之前数据集中样本总数量。
    而通过特征A分裂之后样本集的信息增益为:
    InfoGain(S,A)=E(S)EA(S)InfoGain(S, A) = E(S) - E_A(S)
    则通过特征A分裂后样本集的信息增益率为:
    InfoGainRation(S,A)=InfoGain(S,A)SplitInfoA(S)InfoGainRation(S, A) = \frac{InfoGain(S, A)}{SplitInfo_A(S)}
    C4.5就是根据InfoGainRation来作为选取分离特征的依据的。通过C4.5算法构造决策树时,信息增益率最大的特征即为当前节点的分裂特征,随着递归计算,到后期则选择相对比较大的信息增益率的特征作为分裂特征。

    三、CART算法

    CART算法在分支处理中分支特征的度量指标是Gini指标:
    Gini(S)=1i=1mpi2;pi=CiS Gini(S) = 1 - \sum_{i=1}^m p_i^2; \quad p_i = \frac{\lvert C_i \lvert}{\vert S \vert}
    列如:feature有两种取值,则该特征作为分支特征,其Gini指标为:
    Gini(feature)=S1SGini(S1)+S2SGini(S2)Gini(feature) = \frac{\lvert S_1 \lvert}{\lvert S \lvert} Gini(S_1) + \frac{\lvert S_2 \lvert}{\lvert S \lvert}Gini(S_2)

    上述内容只是讲述了决策树中常见的分裂算法;此外,决策树含有很多其它特性值得我们去探索。

    展开全文
  • 决策树在商品购买能力预测案例中算法实现 作者:白宁超 2016年12月24日22:05:42 摘要:随着机器学习和深度学习热潮,各种图书层出不穷。然而多数是基础理论知识介绍,缺乏实现深入理解。本系列文章是作者结合...

     

    决策树在商品购买能力预测案例中的算法实现

    作者:白宁超

    2016年12月24日22:05:42

    摘要:随着机器学习和深度学习的热潮,各种图书层出不穷。然而多数是基础理论知识介绍,缺乏实现的深入理解。本系列文章是作者结合视频学习和书籍基础的笔记所得。本系列文章将采用理论结合实践方式编写。首先介绍机器学习和深度学习的范畴,然后介绍关于训练集、测试集等介绍。接着分别介绍机器学习常用算法,分别是监督学习之分类(决策树、临近取样、支持向量机、神经网络算法)监督学习之回归(线性回归、非线性回归)非监督学习(K-means聚类、Hierarchical聚类)。本文采用各个算法理论知识介绍,然后结合python具体实现源码和案例分析的方式本文原创编著,转载注明出处:决策树在商品购买力能力预测案例中的算法实现(3)

    目录


    1. 【Machine Learning】Python开发工具:Anaconda+Sublime(1)
    2. 【Machine Learning】机器学习及其基础概念简介(2)
    3. 【Machine Learning】决策树在商品购买力能力预测案例中的算法实现(3)
    4. 【Machine Learning】KNN算法虹膜图片识别实战(4)

    1 决策树/判定树(decision tree)


    1 决策树(Dicision Tree)是机器学习有监督算法中分类算法的一种,有关机器学习中分类和预测算法的评估主要体现在:

    1. 准确率:预测的准确与否是本算法的核心问题,其在征信系统,商品购买预测等都有应用。
    2. 速度:一个好的算法不仅要求具备准确性,其运行速度也是衡量重要标准之一。
    3. 强壮行:具备容错等功能和扩展性等。
    4. 可规模性:能够应对现实生活中的实际案例
    5. 可解释性:运行结果能够说明其含义。
    2 判定树是一个类似于流程图的树结构:其中,每个内部结点表示在一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或类分布。树的最顶层是根结点。

     

    如上案例判断是否去打球?根节点显示14天中9天适合打球,其中5天不适合打球。这里面没有全部一致的情况,说明还需要细分:
    1 晴天:晴天中有2天适合打球,3天不适合打球,还需细分①湿度小于等于70时候有2天都适合打球,停止划分;②湿度大于70有3天都不适合打球,停止划分。
    2 阴天:共4天都适合打球,停止划分。
    3 雨天:3天适合打球,2天不适合打球,继续划分。①没有风的有3天且都适合打球,停止划分;②有风的2天且都不适合打球,停止划分。
    注意:有的时候不易太细的划分,特征过多过细的话反而会影响预测的准确率。把大多数归为一类,极少数的可以归到大多数之中。
    案例:如上决策树,如果某天是:晴天,湿度90 判定是否适合打球,可以由图知是不适合打球的。
    3 官方文档: http://scikit-learn.org/stable/modules/tree.html

    2 构造决策树的基本算法:判定顾客对商品购买能力


    2.1 算法结果图:

    根据决策树分析如下客户数据,判定新客户购买力。其中

    客户年龄age:青年、中年、老年

    客户收入income:低、中、高

    客户身份student:是学生,不是学生

    客户信用credit_rating:信用一般,信用好

    是否购买电脑buy_computer:购买、不购买

    2.2 在介绍决策树算法之前,我们引入熵的概念。熵的(entropy)概念:信息和抽象,如何度量?
    1948年,香农提出了 ”信息熵(entropy)“的概念,一条信息的信息量大小和它的不确定性有直接的关系,要搞清楚一件非常非常不确定的事情,或者是我们一无所知的事情,需要了解大量信息==>信息量的度量就等于不确定性的多少。
    例子:猜世界杯冠军,假如一无所知,猜多少次?每个队夺冠的几率不是相等的,比特(bit)来衡量信息的多少。
    采用如下方式求信息熵:
    1 当每个球队夺冠概率相等时候,32支参加世界杯夺冠球队的信息熵是5,计算是2^5=32,也就是你5次可以猜对那支球队夺冠。
    2 当球队夺冠概率不相等,比如巴西、德国、荷兰是强队概率较大,信息熵就小于5,也就是你用不到5次就可以猜出哪个球队夺冠。
    注:变量的不确定性越大,熵也就越大
    2.3 决策树归纳算法 (ID3)
    1970-1980, J.Ross. Quinlan首先提出ID3算法,第一步是选择属性判断结点,我们采用信息熵的比较。第二步是信息获取量(Information Gain):Gain(A) = Info(D) - Infor_A(D)通过A来作为节点分类获取了多少信息
    详解
    信息获取量/信息增益(Information Gain):Gain(A) = Info(D) - Infor_A(D),例如age的信息增益,Gain(age) = Info(buys_computer) - Infor_age(buys_computer)。
    Info(buys_computer)是这14个记录中,购买的概率9/14,不购买的5/14,带入到信息熵公式。
    Infor_age(buys_computer)是age属性中,青年5/14购买概率是2/5,不购买3/5;中年4/14购买概率是1,不购买概率是0,老年5/14购买概率3/5,不购买概率是2/5.分别代入信息熵公式
    Info(buys_computer)与Infor_age(buys_computer)做差,即是age的信息增益,具体如下:

    类似,Gain(income) = 0.029, Gain(student) = 0.151, Gain(credit_rating)=0.048

    所以,选择信息增益最大的作为根节点即age作为第一个根节点

     

    重复计算即可
    2.4 决策树算法
    决策树算法的形式化描述如下:
    • 树以代表训练样本的单个结点开始(步骤1)。
    • 如果样本都在同一个类,则该结点成为树叶,并用该类标号(步骤2 和3)。
    • 否则,算法使用称为信息增益的基于熵的度量作为启发信息,选择能够最好地将样本分类的属性(步骤6)。该属性成为该结点的“测试”或“判定”属性(步骤7)。在算法的该版本中,
    • 所有的属性都是分类的,即离散值。连续属性必须离散化。
    • 对测试属性的每个已知的值,创建一个分枝,并据此划分样本(步骤8-10)。
    • 算法使用同样的过程,递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上,就不必该结点的任何后代上考虑它(步骤13)。
    • 递归划分步骤仅当下列条件之一成立停止:
    • (a) 给定结点的所有样本属于同一类(步骤2 和3)。
    • (b) 没有剩余属性可以用来进一步划分样本(步骤4)。在此情况下,使用多数表决(步骤5)。
    • 这涉及将给定的结点转换成树叶,并用样本中的多数所在的类标记它。替换地,可以存放结
    • 点样本的类分布。
    • (c) 分枝
    • test_attribute = a i 没有样本(步骤11)。在这种情况下,以 samples 中的多数类
    • 创建一个树叶(步骤12)

    在决策树ID3基础上,又进行了算法改进,衍生出 其他算法如:C4.5: (Quinlan) 和Classification and Regression Trees (CART): (L. Breiman, J. Friedman, R. Olshen, C. Stone)。这些算法

    共同点:都是贪心算法,自上而下(Top-down approach)

     

    区别:属性选择度量方法不同: C4.5 (gain ratio,增益比), CART(gini index,基尼指数), ID3 (Information Gain,信息增益)
     
    2.5 如何处理连续性变量的属性? 
     
    有些数据是连续性的,其不像如上实验数据可以离散化表示。诸如根据天气情况预测打球案例中,其湿度是一个连续值,我们的做法是将湿度70作为一个分界点,这里就是连续变量离散化的体现。
    2.6 补充知识
    树剪枝叶 (避免overfitting):为了避免拟合问题,我们可以对归于繁琐的树进行剪枝(就是降低树的高度),可以分为先剪枝和后剪枝。
    决策树的优点:直观,便于理解,小规模数据集有效     
    决策树的缺点:处理连续变量不好、类别较多时,错误增加的比较快、可规模性一般
     

    3 基于python代码的决策树算法实现:预测顾客购买商品的能力


    3.1 机器学习的库:scikit-learnPython

    scikit-learnPython,其特性简单高效的数据挖掘和机器学习分析,简单高效的数据挖掘和机器学习分析,对所有用户开放,根据不同需求高度可重用性,基于Numpy, SciPy和matplotlib,开源,商用级别:获得 BSD许可。scikit-learn覆盖分类(classification), 回归(regression), 聚类(clustering), 降维(dimensionality reduction),模型选择(model selection), 预处理(preprocessing)等领域。

    3.2 scikit-learn的使用:Anaconda集成了如下包,不需要安装即可使用
    • 安装scikit-learn: pip, easy_install, windows installer,安装必要package:numpy, SciPy和matplotlib, 可使用Anaconda (包含numpy, scipy等科学计算常用package)
    • 安装注意问题:Python解释器版本(2.7 or 3.4?), 32-bit or 64-bit系统

    商品购买例子:

    转化为csv文件如下:

    3.3 运行效果如下:

    其中,datafile存放模型训练数据集和测试数据集,TarFile是算法生成文本形式的dot文件和转化后的pdf图像文件,两个py文件,一个是训练算法一个是测试训练结果。右侧预测值【0 1 1】代表三条测试数据,其中后两条具备购买能力。具体算法和细节下节详解。

    3.4 具体算法和细节

    python中导入决策树相关包文件,然后通过对csv格式转化为sklearn工具包中可以识别的数据格式,再调用决策树算法,最后将模型训练的结果以图形形式展示。

    包的导入:
    from sklearn.feature_extraction import DictVectorizer
    import csv
    from sklearn import tree
    from sklearn import preprocessing
    from sklearn.externals.six import StringIO
    读取csv文件,将其特征值存储在列表featureList中,将预测的目标值存储在labelList中
    '''
    Description:python调用机器学习库scikit-learn的决策树算法,实现商品购买力的预测,并转化为pdf图像显示
    Author:Bai Ningchao
    DateTime:2016年12月24日14:08:11
    Blog URL:http://www.cnblogs.com/baiboy/
    '''
    def trainDicisionTree(csvfileurl):
        '读取csv文件,将其特征值存储在列表featureList中,将预测的目标值存储在labelList中'
    
        featureList = []
        labelList = []
    
        #读取商品信息
        allElectronicsData=open(csvfileurl)
        reader = csv.reader(allElectronicsData)                  #逐行读取信息
        headers=str(allElectronicsData.readline()).split(',')    #读取信息头文件
        print(headers)
    

      运行结果:

    存储特征数列和目标数列

        '存储特征数列和目标数列'
        for row in reader:
            labelList.append(row[len(row)-1])  #读取最后一列的目标数据
            rowDict = {}                       #存放特征值的字典
            for i in range(1, len(row)-1):
                rowDict[headers[i]] = row[i]
                # print("rowDict:",rowDict)
            featureList.append(rowDict)
        print(featureList)
        print(labelList)
    

      运行结果:

    将特征值数值化
    'Vetorize features:将特征值数值化'
        vec = DictVectorizer()    #整形数字转化
        dummyX = vec.fit_transform(featureList) .toarray()   #特征值转化是整形数据
    
        print("dummyX: " + str(dummyX))
        print(vec.get_feature_names())
    
        print("labelList: " + str(labelList))
    
        # vectorize class labels
        lb = preprocessing.LabelBinarizer()
        dummyY = lb.fit_transform(labelList)
        print("dummyY: \n" + str(dummyY))
    

      运行结果:

    如上算法就是将商品信息转化为机器学习决策树库文件可以识别的形式,即如下形式:
    使用决策树进行分类预测处理
        '使用决策树进行分类预测处理'
        # clf = tree.DecisionTreeClassifier()
        #自定义采用信息熵的方式确定根节点
        clf = tree.DecisionTreeClassifier(criterion='entropy')
        clf = clf.fit(dummyX, dummyY)
        print("clf: " + str(clf))
    
        # Visualize model
        with open("../Tarfile/allElectronicInformationGainOri.dot", 'w') as f:
            f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)
    

      运行结果:

    将其转化为图像形式展示,需要下载插件:安装 下载Graphviz:

     

    一路安装下来,然后打开cmd进入dos环境下,并进入../Tarfile/Tname.dot路径下;#2 输入dot -Tname.dot -o name.pdf命令,将dos转化为pdf格式

     

    打开文件可见:

    4 完整项目下载


    完整项目共享

    扩展:银行信用自动评估系统

     

     

     

     

    http://www.cnblogs.com/baiboy
    展开全文
  • 关于本文说明,本人原博客地址位于http://blog.csdn.net/qq_37608890,本文来自笔者于2017年12月06日 18... 本文根据最近学习机器学习书籍 网络文章情况,特将一些学习思路做了归纳整理,详情如下.如有不当之处,请各...

    关于本文说明,本人原博客地址位于http://blog.csdn.net/qq_37608890,本文来自笔者于2017年12月06日 18:06:30所撰写内容(http://blog.csdn.net/qq_37608890/article/details/78731169)。

     

      本文根据最近学习机器学习书籍 网络文章的情况,特将一些学习思路做了归纳整理,详情如下.如有不当之处,请各位大拿多多指点,在此谢过.

    一、决策树(decision tree)概述

    1、决策树概念

           决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

    2 工作原理

          在构造决策树时,需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起到来决定性的作用。为了找到决定性的特征,我们需要对每个特征都要进行评估.完成测试后,原始数据就被划分为几个数据子集.这些数据子集会分布在第一个决策点的所有分支上.若某一分支下的数据属于同一类型,则当前无需阅读的垃圾邮件已经被正确地划分数据分类,没必要再对数据集进行分类.否则,则需要重复划分数据子集的过程.这里划分子集的算法和划分原始数据集的方法相同,直至所有具有相同类型的数据都进入一个数据子集内.构造决策树伪代码函数createBranch()如下:

     

        检测数据集中的每个子项是否属于同一分类:  
              IF so return 类标签  
          
              Else  
                      寻找划分数据集的最好特征  
                      划分数据集  
                       创建分支节点  
                                 for 每个划分的子集  
                                         调用函数createBranch()并增加返回结果到分支节点中  
                        return 分支节点  
                        
    

            一旦我们构造了一个决策树模型,以它为基础来进行分类将是非常容易的。具体做法是,从根节点开始,对实例的某一特征进行测试,根据测试结构将实例分配到其子节点(也就是选择适当的分支);沿着该分支可能达到叶子节点或者到达另一个内部节点时,那么就使用新的测试条件递归执行下去,直到抵达一个叶子节点。当到达叶子节点时,我们便得到了最终的分类结果。下面介绍一个小例子。

        通俗来说,决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话:

    女儿:多大年纪了?
    母亲:26。
    女儿:长的帅不帅?
    母亲:挺帅的。
    女儿:收入高不?
    母亲:不算很高,中等情况。
    女儿:是公务员不?
    母亲:是,在税务局上班呢。
    女儿:那好,我去见见。


          这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别:见和不见。假设这个女孩对男人的要求是:30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员,那么这个可以用下图表示女孩的决策逻辑:

     

            上图完整表达了这个女孩决定是否见一个约会对象的策略,其中绿色节点表示判断条件,橙色节点表示决策结果,箭头表示在一个判断条件在不同情况下的决策路径,图中红色箭头表示了上面例子中女孩的决策过程。
    这幅图基本可以算是一颗决策树,说它“基本可以算”是因为图中的判定条件没有量化,如收入高中低等等,还不能算是严格意义上的决策树,如果将所有条件量化,则就变成真正的决策树了。

    3、决策树的相关特性

    •    优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。

    •    缺点:可能会产生过度匹配问题。

    •    使用数据类型: 数值型和标称型。

    4、 一般流程

        (1) 收集数据: 可以使用任何方法.

        (2) 准备数据: 构造算法只适用于标称型数据,因此数值型数据必须离散化.

        (3) 分析数据: 可以使用任何方法,构造树完成之后,应该检查图形是否符合预期.

        (4) 训练算法: 构造树的数据结构.

        (5) 测试算法: 使用经验树计算错误率.

        (6) 使用算法: 此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义.

     

    二 决策树场景

           假设,现在有一个叫做 "十五个问题" 的游戏,游戏的规则很简单:参与游戏的一方在脑海中想某个事物,其他参与者向他提问,只允许提 15个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围,最后得到游戏的答案。决策树的工作原理与15个问题类似,用户输入一系列数据后给出游戏答案。

          下图给出了一个假想的邮件分类系统,它首先检测发送邮件域名.如果地址为myEmployer.com,则将其放在"无聊时需要阅读的邮件"中。否则,则需要检查邮件内容中是否包含单词 曲棍球 ,若包含则将邮件归入"需要及时处理的朋友邮件",否则则归类到"无需阅读的垃圾邮件"。

     

       

     

       决策树一个很重要的任务就是为了理解数据中所蕴含的知识信息(这与K-近邻算法无法给出数据的内在含义有着显著不同),因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,这些机器根据数据集创建规则的过程,就是机器学习的过程。

    三 决策树项目案例一  对海洋生物进行鱼和非鱼判断

    1 项目情况

          下表中的数据包含5个海洋生物,特征: 不浮出水面是否可以生存和是否有脚蹼.现将动物划分为两类: 鱼和非鱼.如果想依据给出的特征选出一个来划分数据,就涉及到要将划分数据的依据进行量化后才可以判断出来.

        

      我们先构造进行数据输入的createDataSet()函数和计算给定数据集的香农熵函数calcShannonEnt()

       

        def createDataSet():  
            dataSet = [[1,1,'yes'],  
                      [1,1,'yes'],  
                      [1,0,'no'],  
                      [0,1,'no'],  
                      [0,1,'no']]  
            labels=['no surfacing','flippers']  
            # change to discrete values  
            return dataSet,labels  
        #信息增益  
        #计算给定数据的香农熵  
          
        def calcShannonEnt(dataSet): #the the number of unique elements and their occurance  
            numEntries = len(dataSet)  
            labelCounts = {}  
            for featVec in dataSet:  
                currentLabel=featVec[-1]  
                if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0  
                labelCounts[currentLabel] +=1  
            shannonEnt = 0.00000  
            for key in labelCounts:  
                prob = float(labelCounts[key]) /numEntries  
                shannonEnt -= prob * log(prob,2)   #log base 2  
                  
            return shannonEnt  
    

     

     执行

        myDat,labels=createDataSet()  
        myDat  
    

     得到 

    [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
    

     执行

    calcShannonEnt(myDat)  
    

    得到

    0.9709505944546686

    熵越高,则混合的数据越多,我们可用在数据集中添加更多的分类,观察熵是如何变化的.

    按照给定特征划分数据集,将指定特征的特征值等于 value 的行剩下列作为子数据集。

     

        def splitDataSet(dataSet, index, value):  
            """splitDataSet(通过遍历dataSet数据集,求出index对应的colnum列的值为value的行) 
                就是依据index列进行分类,如果index列的数据等于 value的时候,就要将 index 划分到我们创建的新的数据集中 
            Args: 
                dataSet 数据集                 待划分的数据集 
                index 表示每一行的index列        划分数据集的特征 
                value 表示index列对应的value值   需要返回的特征的值。 
            Returns: 
                index列为value的数据集【该数据集需要排除index列】 
            """  
            retDataSet = []  
            for featVec in dataSet:   
            
                if featVec[index] == value:  
                 
                    reducedFeatVec = featVec[:index]  
                     
                    reducedFeatVec.extend(featVec[index+1:])  
                
                    retDataSet.append(reducedFeatVec)  
            return retDataSet  
    

     选择最好的数据集划分方式:

     

        def chooseBestFeatureToSplit(dataSet):  
            """chooseBestFeatureToSplit(选择最好的特征) 
         
            Args: 
                dataSet 数据集 
            Returns: 
                bestFeature 最优的特征列 
            """  
            # 求第一行有多少列的 Feature, 最后一列是label列嘛  
            numFeatures = len(dataSet[0]) - 1  
    
            baseEntropy = calcShannonEnt(dataSet)  
          
            bestInfoGain, bestFeature = 0.0, -1  
            # iterate over all the features  
            for i in range(numFeatures):  
                     
                featList = [example[i] for example in dataSet]  
                uniqueVals = set(featList)  
           
                newEntropy = 0.0  
           
                for value in uniqueVals:  
                    subDataSet = splitDataSet(dataSet, i, value)  
                    # 计算概率  
                    prob = len(subDataSet)/float(len(dataSet))  
                    # 计算信息熵  
                    newEntropy += prob * calcShannonEnt(subDataSet)  
                # gain[信息增益]: 划分数据集前后的信息变化, 获取信息熵最大的值  
             
                infoGain = baseEntropy - newEntropy  
                print 'infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy  
                if (infoGain > bestInfoGain):  
                    bestInfoGain = infoGain  
                    bestFeature = i  
            return bestFeature  
    

     

    训练算法:构造树的数据结构

      创建树的函数

        def createTree(dataSet, labels):  
            classList = [example[-1] for example in dataSet]  
          
            if classList.count(classList[0]) == len(classList):  
                return classList[0]  
    
            if len(dataSet[0]) == 1:  
                return majorityCnt(classList)  
          
       
            bestFeat = chooseBestFeatureToSplit(dataSet)  
      
            bestFeatLabel = labels[bestFeat]  
            # 初始化myTree  
            myTree = {bestFeatLabel: {}}  
          
            del(labels[bestFeat])  
            # 取出最优列,然后它的branch做分类  
            featValues = [example[bestFeat] for example in dataSet]  
            uniqueVals = set(featValues)  
            for value in uniqueVals:  
            
                subLabels = labels[:]  
                
                myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)  
                # print 'myTree', value, myTree  
            return myTree  
    

       测试算法:使用决策树执行分类

     

        def classify(inputTree, featLabels, testVec):  
            """classify(给输入的节点,进行分类) 
         
            Args: 
                inputTree  决策树模型 
                featLabels Feature标签对应的名称 
                testVec    测试输入的数据 
            Returns: 
                classLabel 分类的结果值,需要映射label才能知道名称 
            """  
    
            firstStr = inputTree.keys()[0]  
    
            secondDict = inputTree[firstStr]  
     
            featIndex = featLabels.index(firstStr)  
    
            key = testVec[featIndex]  
            valueOfFeat = secondDict[key]  
            print '+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat  
         
            if isinstance(valueOfFeat, dict):  
                classLabel = classify(valueOfFeat, featLabels, testVec)  
            else:  
                classLabel = valueOfFeat  
            return classLabel  
    

     

     

    三  项目案例2: 使用决策树预测隐形眼镜类型

    项目概述

    隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。我们需要使用决策树预测患者需要佩戴的隐形眼镜类型。
    开发流程

    (1)收集数据: 提供的文本文件。
    (2)解析数据: 解析 tab 键分隔的数据行
    (3)分析数据: 快速检查数据,确保正确地解析数据内容,使用 createPlot() 函数绘制最终的树形图。
    (4)训练算法: 使用 createTree() 函数。
    (5)测试算法: 编写测试函数验证决策树可以正确分类给定的数据实例。
    (6)使用算法: 存储树的数据结构,以便下次使用时无需重新构造树。

    收集数据:提供的文本文件

    文本文件数据格式如下:

      

    young   myope   no  reduced no lenses  
    pre myope   no  reduced no lenses  
    presbyopic  myope   no  reduced no lenses 
    

     

      解析数据:解析 tab 键分隔的数据行

        lecses = [inst.strip().split('\t') for inst in fr.readlines()]  
        lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']  
    

     

    分析数据:快速检查数据,确保正确地解析数据内容,使用 createPlot() 函数绘制最终的树形图。

    treePlotter.createPlot(lensesTree)  
    

     
    训练算法:使用 createTree() 函数

     

        >>> lensesTree = trees.createTree(lenses, lensesLabels)  
        >>> lensesTree  
    

     

     
    得到

     

        {'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic':{'yes':  
        {'prescript':{'hyper':{'age':{'pre':'no lenses', 'presbyopic':  
        'no lenses', 'young':'hard'}}, 'myope':'hard'}}, 'no':{'age':{'pre':  
        'soft', 'presbyopic':{'prescript': {'hyper':'soft', 'myope':  
        'no lenses'}}, 'young':'soft'}}}}}  
    

     

     

    五 小结

    其实决策树跟带终止块的流程图类似,所以这里的终止块就是分类结果.当我们进行数据处理时,首先要对集合中数据的不一致性进行测量评估,也就是计算香农熵,下一步才可以寻找最有方案划分数据,最终实现所有具有相同类型的数据都划分到同一个数据子集里面.在构建数据树时,我们一般采用递归方把数据集转化为决策树.多数情况下,我们不构造新的数据结构,而是采用Python语言内嵌的数据结构字典存储树节点信息.每一步选择信息增益最大的特征作为决策块,最终来完成决策树的生成.


    Matplotlib的注解功能,可以让将存储的树结构转化为容易理解的图形.隐形眼镜的例子说明决策树可能会产生过多的数据集划分,结果导致过度匹配数据集的问题.当然可以通过裁剪决策树,合并相邻的不能产生信息增益的叶节点,来解决这个问题(过度匹配).


    关于决策树的构造算法,这里本文只是用了ID3算法,当然还有C4.5和CART算法.对于决策树的完整工作过程而言,包括三部分:


    1 特征选择;


    2 生成决策树;


    3 剪枝部分


    而除去ID3算法,其他两个算法都有剪枝部分过程.所以这也迎合来隐形眼镜过拟合的问题.

      关于决策树部分,笔者先整理到这里,后续有机会会针对C4.5和CART算法做些归纳整理.有不足之处,请各位同仁多多指导.

    转载于:https://www.cnblogs.com/georgeli/p/8087660.html

    展开全文
  • 1.在京东网站上爬取3000条关于机器学习类书籍的数据。 爬虫代码可以看这里 爬完结果如下 2. 数据预处理 去掉特殊字符 一些看起来没有用列删掉 一些由空值字段删掉。 通过title这列,衍生出两个全新列 ...
  • 1、机器学习是研究学习算法,包括神经网络、决策树、SVM等。 2、学习算法结果是获得模型,应用于预测等。如果预测离散值,称为分类;如果预测是连续值,称为回归。 3、当学习过程中,存在假设空间时,即有...
  • 在生信分析中经常会和贝叶斯打交道,比如贝叶斯分类器、贝叶斯网络、贝叶斯构建进化... 事实上,介绍贝叶斯定理、贝叶斯方法、贝叶斯推断资料、书籍不少,比如《数理统计学简史》,以及《统计决策论及贝叶斯分析 J...
  • 在生信分析中经常会和贝叶斯打交道,比如贝叶斯分类器、贝叶斯网络、贝叶斯... 事实上,介绍贝叶斯定理、贝叶斯方法、贝叶斯推断资料、书籍不少,比如《数理统计学简史》,以及《统计决策论及贝叶斯分析 James ...
  • C&RT(CART)详解

    2018-07-29 13:27:51
    关于决策树的一些基本概念在这篇博客《Decision Tree简介(决策树算法族的开篇)》中有相关介绍。 决策树的基本生成过程  一般的,一棵决策树包含一个根结点、若干个内部结点和若干个叶结点,叶结点对应...
  • 这篇notebook是关于机器学习监督学习中的决策树算法,内容包括决策树算法构造过程,使用matplotlib库绘制树形图以及使用决策树预测隐形眼睛类型. 操作系统:ubuntu14.04(win也ok) 运行环境:anaconda-python2.7-...
  • 关于决策树的一些基本概念在这篇博客《Decision Tree简介(决策树算法族的开篇)》中有相关介绍。 预备知识: 这一部分主要是谈一谈集中基于信息论的结点划分方法,包括信息熵(Informatica&amp;amp;...
  • 摘要:随着机器学习和深度学习热潮,各种图书层出不穷。...接着分别介绍机器学习常用算法,分别是监督学习之分类(决策树、临近取样、支持向量机、神经网络算法)监督学习之回归(线性回归、非线性回归)非监督学
  • CruiseYoung提供带有详细书签电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 数据库系统基础:初级篇(第5版)(讲述数据库系统原理经典教材) 基本信息 原书名: Fundamentals of Database ...
  • 本书共有43章,内容涵盖常见神经网络(BP、RBF、SOM、Hopfield、Elman、LVQ、Kohonen、GRNN、NARX等)以及相关智能算法(SVM、决策树、随机森林、极限学习机等)。同时,部分章节也涉及了常见优化算法(遗传算法...
  • asp.net知识库

    2015-06-18 08:45:45
    关于能自定义格式、支持多语言、支持多数据库代码生成器想法 发布Oracle存储过程包c#代码生成工具(CodeRobot) New Folder XCodeFactory3.0完全攻略--序 XCodeFactory3.0完全攻略--基本思想 XCodeFactory...
  • 10.11 决策树 251 10.12 小结 253 第 11章 Python生态系统外部环境和云计算 255 11.1 与MATLAB/Octave交换信息 256 11.2 Installing rpy2安装rpy2 257 11.3 连接R 257 11.4 为Java传递NumPy数组 260 11.5 ...
  • K 近邻算法、线性回归、梯度下降法、逻辑回归、支持向量机、决策树、集成学习 十、工具 Git 学习指引,将用最极简语言带你进入 Git 版本控制世界 Git 工作流 集中式工作流,功能分支工作流, GitFlow ...
  • CruiseYoung提供带有详细书签电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 Cassandra 权威指南(Apache Cassandra 项目主席作序推荐) 基本信息 原书名: Cassandra: The Definitive Guide...
  • CruiseYoung提供带有详细书签电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 Oracle 9i & 10g编程艺术:深入数据库体系结构(09年度畅销榜TOP50)(08年度畅销榜TOP50) 基本信息 原书名: ...
  • CruiseYoung提供带有详细书签电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 Oracle Database 9i/10g/11g编程艺术:深入数据库体系结构:第2版(世界顶级专家Thomas Kyte力作) 基本信息 原...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

关于决策树的书籍