(完整版)生物数据挖掘-决策树实验报告

实验四 决策树

一、 实验目的

了解典型决策树算法

熟悉决策树算法的思路与步骤

掌握运用 Matlab 对数据集做决策树分析的方法

二、 实验内容

1.运用 Matlab 对数据集做决策树分析

三、 实验步骤

1.写出对决策树算法的理解 决策树方法是数据挖掘的重要方法之一， 它是利用树形结构的特性来对数据进行分类的 一种方法。

　决策树学习从一组无规则、 无次序的事例中推理出有用的分类规则， 是一种实例 为基础的归纳学习算法。

　决策树首先利用训练数据集合生成一个测试函数， 根据不同的权值 建立树的分支， 即叶子结点， 在每个叶子节点下又建立层次结点和分支， 如此重利生成决策 树，然后对决策树进行剪树处理，最后把决策树转换成规则。

　决策树的最大优点是直观，以 树状图的形式表现预测结果， 而且这个结果可以进行解释。

　决策树主要用于聚类和分类方面 的应用。

决策树是一树状结构， 它的每一个叶子节点对应着一个分类， 非叶子节点对应着在某个 属性上的划分， 根据样本在该属性上的不同取值将其划分成若干个子集。

　构造决策树的核心 问题是在每一步如何选择适当的属性对样本进行拆分。

　对一个分类问题， 从已知类标记的训 练样本中学习并构造出决策树是一个自上而下分而治之的过程。

2.启动 Matlab ，运用 Matlab 对数据集进行决策树分析，写出算法名称、数据集名称、关键 代码，记录实验过程，实验结果，并分析实验结果

（1） 算法名称 : ID3 算法

ID3 算法是最经典的决策树分类算法。

　ID3 算法基于信息熵来选择最佳的测试属性，它 选择当前样本集中具有最大信息增益值的属性作为测试属性； 样本集的划分则依据测试属性 的取值进行， 测试属性有多少个不同的取值就将样本集划分为多少个子样本集， 同时决策树 上相应于该样本集的节点长出新的叶子节点。

　ID3 算法根据信息论的理论，采用划分后样本 集的不确定性作为衡量划分好坏的标准， 用信息增益值度量不确定性： 信息增益值越大， 不 确定性越小。因此， ID3 算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样 可以得到当前情况下最纯的划分，从而得到较小的决策树。

ID3 算法的具体流程如下：

1）对当前样本集合，计算所有属性的信息增益；

2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本 集；

3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应 的符号，然后返回调用处；否则对子样本集递归调用本算法。

（2） 数据集名称：鸢尾花卉 Iris 数据集

选择了部分数据集来区分 Iris Setosa （山鸢尾）及Iris Versicolour （杂色鸢尾）两个种类。

实验代码：

%%使用ID3决策树算法预测鸢尾花卉 Iris种类

clear ;

%% 数据预处理

disp('正在进行数据预处理...')；

[matrix,attributes_label,attributes] = id3_preprocess();

%%构造ID3决策树，其中id3()为自定义函数

disp('数据预处理完成，正在进行构造树 ...');

tree = id3(matrix,attributes_label,attributes)；

%% 打印并画决策树

[nodeids,nodevalues] = print_tree(tree); tree_plot(nodeids,nodevalues);

disp('ID3 算法构建决策树完成！ ');

%% 构造函数 id3_preprocess

function [ matrix,attributes,activeAttributes ] = id3_preprocess( )

%% ID3算法数据预处理，把字符串转换为 0,1编码

%% 读取数据

txt={ ' 序号 '

' 花萼大小 '

'花瓣长度 '

'花瓣宽度 '

'类型 '

II

'小'

'长'

'长'

'versicolor'

II

'小'

'长'

'长'

'versicolor'

II

'小'

'长'

'长'

'versicolor'

II

'小'

'短'

'长'

'versicolor'

II

'小'

'长'

'长'

'versicolor'

II

'小'

'短'

'长'

'versicolor'

II

'小'

'长'

'短'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'大'

'长'

'短'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'小'

'长'

'长'

'setosa'

II

'大'

'短'

'长'

'versicolor'

II

'大'

'短'

'长'

'versicolor'

II

'大'

'短'

'长'

'versicolor'

II

'大'

'短'

'长'

'versicolor'

II

'大'

'短'

'短'

'versicolor'

II

'小'

'短'

'短'

'setosa'

II

'小'

'短'

'长'

'setosa'

II

'小'

'短'

'长'

'setosa'

II

'小'

'短'

'长'

'setosa'

II

'小'

'短'

'短'

'setosa'

II

'小'

'长'

'短'

'setosa'

II

'大'

'短'

'长'

'setosa'

II

'大'

'短'

'长'

'setosa'

II

'小'

'短'

'短'

'setosa'

II

'小'

'短'

'短'

'setosa'

II

'大'

'短'

'短'

'setosa'

II

'小'

'长'

'短'

'setosa'

II

'大'

'短'

'长'

'setosa'

II

'大'

'短'

'短'

'setosa'

II

'大'

'短'

'短'

'setosa'

} attributes=txt(1,2:end); % attributes: 属性和 Label； activeAttributes = ones(1,length(attributes) -1);% activeAttributes : 属性向量，全 1； data = txt(2:end,2:end);

%% 针对每列数据进行转换 [rows,cols] = size(data); matrix = zeros(rows,cols); % matrix ： 转换后的 0,1 矩阵； for j=1:cols

matrix(:,j) = cellfun(@trans2onezero,data(:,j)); end end %%构造函数 trans2onezero function flag = trans2onezero(data)

if strcmp(data,' 小 ')||strcmp(data,' 短 ')... ||strcmp(data,'setosa') flag =0; return ;

end

flag =1;

end %%构造函数 id3

function [ tree ] = id3( examples, attributes, activeAttributes ) %% ID3 算法 ，构建 ID3 决策树

%% 提供的数据为空，则报异常

if (isempty(examples));

error(' 必须提供数据！ ');

end numberAttributes = length(activeAttributes);

% activeAttributes: 活跃的属性值； -1,1 向量， 1 表示活跃； numberExamples = length(examples(:,1)); % example: 输入 0、 1 矩阵； % 创建树节点

tree = struct('value', 'null', 'left', 'null', 'right', 'null'); % 如果最后一列全部为 1，则返回“ versicolor ” lastColumnSum = sum(examples(:, numberAttributes + 1)); if (lastColumnSum == numberExamples);

tree.value = 'versicolor';

return

end

% 如果最后一列全部为 0 ，则返回“ setosa”

if (lastColumnSum == 0);

tree.value = 'setosa';

return

end

% 如果活跃的属性为空，则返回 label 最多的属性值

if (sum(activeAttributes) == 0);

if (lastColumnSum >= numberExamples / 2);

tree.value = 'versicolor';

else

tree.value = 'setosa';

end

return

end

%% 计算当前属性的熵

p1 = lastColumnSum / numberExamples;

if (p1 == 0);

p1_eq = 0;

else

p1_eq = -1*p1*log2(p1);

end

p0 = (numberExamples - lastColumnSum) / numberExamples; if (p0 == 0);

p0_eq = 0;

else

p0_eq = -1*p0*log2(p0);

end

currentEntropy = p1_eq + p0_eq;

%% 寻找最大增益

gains = -1*ones(1,numberAttributes); % 初始化增益

for i=1:numberAttributes;

if (activeAttributes(i)) % 该属性仍处于活跃状态，对其更新 s0 = 0; s0_and_true = 0; s1 = 0; s1_and_true = 0;

for j=1:numberExamples;

if (examples(j,i));

s1 = s1 + 1;

if (examples(j, numberAttributes + 1));

s1_and_true = s1_and_true + 1;

end else

s0 = s0 + 1;

if (examples(j, numberAttributes + 1)); s0_and_true = s0_and_true + 1;

end

end

end

if (~s1); % 熵 S(v=1) p1 = 0;

else

p1 = (s1_and_true / s1); end if (p1 == 0);

p1_eq = 0;

else

p1_eq = -1*(p1)*log2(p1);

end

if (~s1); p0 = 0;

else

p0 = ((s1 - s1_and_true) / s1); end if (p0 == 0);

p0_eq = 0;

else

p0_eq = -1*(p0)*log2(p0); end entropy_s1 = p1_eq + p0_eq; if (~s0); % 熵 S(v=0) p1 = 0;

else

p1 = (s0_and_true / s0); end if (p1 == 0); p1_eq = 0;

else

p1_eq = -1*(p1)*log2(p1);

end

if (~s0); p0 = 0;

else

p0 = ((s0 - s0_and_true) / s0); end if (p0 == 0);

p0_eq = 0;

else

p0_eq = -1*(p0)*log2(p0);

end

entropy_s0 = p1_eq + p0_eq;

gains(i)=currentEntropy -((s1/numberExamples)*entropy_s1) -((s0/numberExamples)*entropy_s0); end

end

% 选出最大增益

[~, bestAttribute] = max(gains);

% 设置相应值

tree.value = attributes{bestAttribute};

% 去活跃状态 activeAttributes(bestAttribute) = 0;

% 根据 bestAttribute 把数据进行分组 examples_0= examples(examples(:,bestAttribute)==0,:); examples_1= examples(examples(:,bestAttribute)==1,:);

% 当 value = false or 0, 左分支 if (isempty(examples_0));

leaf = struct('value', 'null', 'left', 'null', 'right', 'null');

if (lastColumnSum >= numberExamples / 2); % for matrix examples

leaf.value =

'true';

else

leaf.value =

'false';

end

tree.left = leaf;

else

% 递归

tree.left = id3(examples_0, attributes, activeAttributes); end

% 当 value = true or 1, 右分支

if (isempty(examples_1));

leaf = struct('value', 'null', 'left', 'null', 'right', 'null'); if (lastColumnSum >= numberExamples / 2);

leaf.value = 'true'; else

leaf.value = 'false';

end tree.right = leaf;

else

% 递归

tree.right = id3(examples_1, attributes, activeAttributes);

end

% 返回

return

end

%%构造函数 print_tree

function [nodeids_,nodevalue_] = print_tree(tree)

%% 打印树，返回树的关系向量 global nodeid nodeids nodevalue;

nodeids(1)=0; % 根节点的值为 0

nodeid=0;

nodevalue={};

if isempty(tree)

disp(' 空树！ ');

return ;

end

queue = queue_push([],tree);

while ~isempty(queue) % 队列不为空

[node,queue] = queue_pop(queue); % 出队列 visit(node,queue_curr_size(queue));

if ~strcmp(node.left,'null') % 左子树不为空

queue = queue_push(queue,node.left); % 进队 end

if ~strcmp(node.right,'null') % 左子树不为空

queue = queue_push(queue,node.right); % 进队 end

end

%% 返回 节点关系，用于 treeplot 画图 nodeids_=nodeids;

nodevalue_=nodevalue;

end

%%构造函数 visit

function visit(node,length_)

%% 访问 node 节点，并把其设置值为 nodeid 的节点 global nodeid nodeids nodevalue;

if isleaf(node) nodeid=nodeid+1;

fprintf(' 叶子节点， node: %d\t ，属性值 : %s\n', ... nodeid, node.value);

nodevalue{1,nodeid}=node.value;

else % 要么是叶子节点，要么不是

%if isleaf(node.left) && ~isleaf(node.right) % 左边为叶子节点 ,右边不是 nodeid=nodeid+1;

nodeids(nodeid+length_+1)=nodeid;

nodeids(nodeid+length_+2)=nodeid;

fprintf('node: %d\t 属性值 : %s\t ，左子树为节点： node%d ，右子树为节点： node%d\n', ...

nodeid, node.value,nodeid+length_+1,nodeid+length_+2); nodevalue{1,nodeid}=node.value;

end

end

%%构造函数 isleaf

function flag = isleaf(node)

%% 是否是叶子节点

if strcmp(node.left,'null') && strcmp(node.right,'null') % 左右都为空

flag =1;

else

flag=0;

end

end

%%构造函数 tree_plot

function tree_plot( p ,nodevalues)

%% 参考 treeplot 函数

[x,y,h]=treelayout(p);

f = find(p~=0);

pp = p(f);

X = [x(f); x(pp); NaN(size(f))];

Y = [y(f); y(pp); NaN(size(f))];

X = X(:);

Y = Y(:);

n = length(p);

if n < 500,

hold on ;

plot (x, y, 'ro', X, Y, 'r-');

nodesize = length(x);

for i=1:nodesize

%text(x(i)+0.01,y(i),['node' num2str(i)]); text(x(i)+0.01,y(i),nodevalues{1,i});

end

hold off;

else

plot (X, Y, 'b-');

end;

xlabel(['height = ' int2str(h)]);

axis([0 1 0 1]);

end %%构造函数 queue_curr_size function [ length_ ] = queue_curr_size( queue ) %% 当前队列长度 length_= length(queue);

end %%构造函数 queue_pop

function [ item,newqueue ] = queue_pop( queue ) %% 访问队列

if isempty(queue)

disp(' 队列为空，不能访问！ '); return;

end

item = queue(1); % 第一个元素弹出 newqueue=queue(2:end); % 往后移动一个元素位置 end %%构造函数 queue_push

function [ newqueue ] = queue_push( queue,item ) %% 进队

% cols = size(queue);

% newqueue =structs(1,cols+1); newqueue=[queue,item];

end

（4）实验步骤：

>> Untitled 正在进行数据预处理 txt =

35 x 5 cell 数组

'序号'

'花萼大小 '

'花瓣长度 '

' 花瓣宽度 '

' 类型 '

II

'小'

'长'

'长'

'versicolor'

II

'小'

'长'

'长'

'versicolor'

II

'小'

'长'

'长'

'versicolor'

II

'小'

'短'

'长'

'versicolor'

II

'小'

'长'

'长'

'versicolor'

II

'小'

'短'

'长'

'versicolor'

II

'小'

'长'

'短'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'大'

'长'

'短'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

II

'大'

'长'

'长'

'versicolor'

'' '大 '

'长'

'长'

'versicolor'

'' '大 '

'长'

'长'

'versicolor'

'' '小 '

'长'

'长'

'setosa'

'' '大 '

'短'

'长'

'versicolor'

'' '大 '

'短'

'长'

'versicolor'

'' '大 '

'短'

'长'

'versicolor'

'' '大 '

'短'

'长'

'versicolor'

'' '大 '

'短'

'短'

'versicolor'

'' '小 '

'短'

'短'

'setosa'

'' '小 '

'短'

'长'

'setosa'

'' '小 '

'短'

'长'

'setosa'

'' '小 '

'短'

'长'

'setosa'

'' '小 '

'短'

'短'

'setosa'

'' '小 '

'长'

'短'

'setosa'

'' '大 '

'短'

'长'

'setosa'

'' '大 '

'短'

'长'

'setosa'

'' '小 '

'短'

'短'

'setosa'

'' '小 '

'短'

'短'

'setosa'

'' '大 '

'短'

'短'

'setosa'

'' '小 '

'长'

'短'

'setosa'

'' '大 '

'短'

'长'

'setosa'

'' '大 '

'短'

'短'

'setosa'

'' '大 '

'短'

'短'

'setosa'

数据预处理完成，

正在进行构造树

node: 1 node: 2 node: 3 node: 4 node: 5 node: 6

属性值 属性值 属性值 属性值 属性值 属性值

叶子节点， 叶子节点， 叶子节点， 叶子节点， 叶子节点， 叶子节点， 叶子节点，

花瓣长度 ，左子树为节点 花瓣宽度 ，左子树为节点 花萼大小 ，左子树为节点 花萼大小 ，左子树为节点 花萼大小 ，左子树为节点 花瓣宽度 ，左子树为节点

node: 7

node: 8

node

node: 10

node: 11

node: 12

node: 13

，属性值 : versicolor

，属性值 : setosa

，属性值 : setosa

，属性值 : setosa ，属性值 : versicolor

，属性值 : setosa ，属性值 : versicolor

node2 ，右子树为节点： node4 ，右子树为节点： node6 ，右子树为节点： node8 ，右子树为节点： node10 ，右子树为节点： node12 ，右子树为节点：

node3

node5

node7

node9

node11

node13

ID3 算法构建决策树完成！

4）实验结果

0.9 -

0.8 ?

0.7 -

0.6 -

0.5 -

0 4

0.3?

0.2 -

0.1 ?

Q 1 ■ 1 I

0 0.1 02 0.3 0.4 0.5 0.6 07 0.8 0.9 1

height = 3