生物数据挖掘-决策树实验报告

1、精选优质文档-倾情为你奉上实验四 决策树一、 实验目的1. 了解典型决策树算法2. 熟悉决策树算法的思路与步骤3. 掌握运用Matlab对数据集做决策树分析的方法二、 实验内容1.运用Matlab对数据集做决策树分析三、 实验步骤1.写出对决策树算法的理解决策树方法是数据挖掘的重要方法之一，它是利用树形结构的特性来对数据进行分类的一种方法。决策树学习从一组无规则、无次序的事例中推理出有用的分类规则，是一种实例为基础的归纳学习算法。决策树首先利用训练数据集合生成一个测试函数，根据不同的权值建立树的分支，即叶子结点，在每个叶子节点下又建立层次结点和分支，如此重利生成决策树，然后对决策树进行剪树处理

2、，最后把决策树转换成规则。决策树的最大优点是直观，以树状图的形式表现预测结果，而且这个结果可以进行解释。决策树主要用于聚类和分类方面的应用。决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下分而治之的过程。2.启动Matlab，运用Matlab对数据集进行决策树分析，写出算法名称、数据集名称、关键代码，记录实验过程，实验结果，并分析实验结果(1) 算法名称: ID3算法I

3、D3算法是最经典的决策树分类算法。ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的决策树。ID3算法的具体流程如下： 1）对当前样本集合，计算所有属性的信息

4、增益； 2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集； 3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。(2) 数据集名称：鸢尾花卉Iris数据集选择了部分数据集来区分Iris Setosa（山鸢尾）及Iris Versicolour（杂色鸢尾）两个种类。（3）实验代码：% 使用ID3决策树算法预测鸢尾花卉Iris种类clear ;% 数据预处理disp('正在进行数据预处理.');matrix,attributes_label,attributes =

5、id3_preprocess();% 构造ID3决策树，其中id3()为自定义函数disp('数据预处理完成，正在进行构造树.');tree = id3(matrix,attributes_label,attributes);% 打印并画决策树nodeids,nodevalues = print_tree(tree);tree_plot(nodeids,nodevalues);disp('ID3算法构建决策树完成！');% 构造函数id3_preprocessfunction matrix,attributes,activeAttributes = id3_pr

6、eprocess( )% ID3算法数据预处理，把字符串转换为0,1编码% 读取数据txt= '序号' '花萼大小' '花瓣长度' '花瓣宽度' '类型' '' '小' '长' '长' 'versicolor' '' '小' '长' '长' 'versicolor' '' '小' '长' '长'

7、 'versicolor' '' '小' '短' '长' 'versicolor' '' '小' '长' '长' 'versicolor' '' '小' '短' '长' 'versicolor' '' '小' '长' '短' 'versicolor' '&

8、#39; '大' '长' '长' 'versicolor' '' '大' '长' '短' 'versicolor' '' '大' '长' '长' 'versicolor' '' '大' '长' '长' 'versicolor' '' '大' '长'

9、 '长' 'versicolor' '' '大' '长' '长' 'versicolor' '' '小' '长' '长' 'setosa' '' '大' '短' '长' 'versicolor' '' '大' '短' '长' 'versicolor'

10、; '' '大' '短' '长' 'versicolor' '' '大' '短' '长' 'versicolor' '' '大' '短' '短' 'versicolor' '' '小' '短' '短' 'setosa' '' '小' '短&

11、#39; '长' 'setosa' '' '小' '短' '长' 'setosa' '' '小' '短' '长' 'setosa' '' '小' '短' '短' 'setosa' '' '小' '长' '短' 'setosa' ''

12、 '大' '短' '长' 'setosa' '' '大' '短' '长' 'setosa' '' '小' '短' '短' 'setosa' '' '小' '短' '短' 'setosa' '' '大' '短' '短' 'se

13、tosa' '' '小' '长' '短' 'setosa' '' '大' '短' '长' 'setosa' '' '大' '短' '短' 'setosa' '' '大' '短' '短' 'setosa' attributes=txt(1,2:end);% attribut

14、es: 属性和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);endend%构造函数trans2onezerofunction flag = trans2

15、onezero(data) if strcmp(data,'小')|strcmp(data,'短'). |strcmp(data,'setosa') flag =0; return ; end flag =1;end%构造函数id3function tree = id3( examples, attributes, activeAttributes )% ID3 算法 ，构建ID3决策树% 提供的数据为空，则报异常if (isempty(examples); error('必须提供数据！');endnumberAttributes

16、 = 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

17、(:, numberAttributes + 1);if (lastColumnSum = numberExamples); tree.value = 'versicolor' returnend% 如果最后一列全部为0，则返回“setosa”if (lastColumnSum = 0); tree.value = 'setosa' returnend% 如果活跃的属性为空，则返回label最多的属性值if (sum(activeAttributes) = 0); if (lastColumnSum >= numberExamples / 2); tree

18、.value = 'versicolor' else tree.value = 'setosa' end returnend% 计算当前属性的熵p1 = lastColumnSum / numberExamples;if (p1 = 0); p1_eq = 0;else p1_eq = -1*p1*log2(p1);endp0 = (numberExamples - lastColumnSum) / numberExamples;if (p0 = 0); p0_eq = 0;else p0_eq = -1*p0*log2(p0);endcurrentEntrop

19、y = 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_

20、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 (

21、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

22、*(p0)*log2(p0); end entropy_s0 = p1_eq + p0_eq; gains(i)=currentEntropy-(s1/numberExamples)*entropy_s1)-(s0/numberExamples)*entropy_s0); endend% 选出最大增益, bestAttribute = max(gains);% 设置相应值tree.value = attributesbestAttribute;% 去活跃状态activeAttributes(bestAttribute) = 0;% 根据bestAttribute把数据进行分组examples_

23、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 /

24、 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', '

25、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% 返回returnend%构造函数print_treefunction nodeids_,nodevalu

26、e_ = print_tree(tree)% 打印树，返回树的关系向量global nodeid nodeids nodevalue;nodeids(1)=0; % 根节点的值为0nodeid=0;nodevalue=;if isempty(tree) disp('空树！'); return ;endqueue = queue_push(,tree);while isempty(queue) % 队列不为空 node,queue = queue_pop(queue); % 出队列 visit(node,queue_curr_size(queue); if strcmp(node

27、.left,'null') % 左子树不为空 queue = queue_push(queue,node.left); % 进队 end if strcmp(node.right,'null') % 左子树不为空 queue = queue_push(queue,node.right); % 进队 endend% 返回 节点关系，用于treeplot画图nodeids_=nodeids;nodevalue_=nodevalue;end%构造函数visitfunction visit(node,length_)% 访问node 节点，并把其设置值为nodeid的节

28、点 global nodeid nodeids nodevalue; if isleaf(node) nodeid=nodeid+1; fprintf('叶子节点，node: %dt，属性值: %sn', . nodeid, node.value); nodevalue1,nodeid=node.value; else % 要么是叶子节点，要么不是 %if isleaf(node.left) && isleaf(node.right) % 左边为叶子节点,右边不是 nodeid=nodeid+1; nodeids(nodeid+length_+1)=nodeid

29、; nodeids(nodeid+length_+2)=nodeid; fprintf('node: %dt属性值: %st，左子树为节点：node%d，右子树为节点：node%dn', . nodeid, node.value,nodeid+length_+1,nodeid+length_+2); nodevalue1,nodeid=node.value; endend%构造函数isleaffunction flag = isleaf(node)% 是否是叶子节点 if strcmp(node.left,'null') && strcmp(no

30、de.right,'null') % 左右都为空 flag =1; else flag=0; endend%构造函数tree_plotfunction 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, '

31、;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),nodevalues1,i); end hold off; else plot (X, Y, 'b-'); end;xlabel('height = ' int2str(h);axis(0 1 0 1);end%构造函数queue_curr_sizefunction length_ = qu

32、eue_curr_size( queue )% 当前队列长度length_= length(queue);end%构造函数queue_popfunction item,newqueue = queue_pop( queue )% 访问队列if isempty(queue) disp('队列为空，不能访问！'); return;enditem = queue(1); % 第一个元素弹出newqueue=queue(2:end); % 往后移动一个元素位置end%构造函数queue_pushfunction newqueue = queue_push( queue,item )%

33、进队% cols = size(queue);% newqueue =structs(1,cols+1);newqueue=queue,item;end（4）实验步骤：>> Untitled正在进行数据预处理.txt = 35×5 cell 数组 '序号' '花萼大小' '花瓣长度' '花瓣宽度' '类型' '' '小' '长' '长' 'versicolor' '' '小' 

34、9;长' '长' 'versicolor' '' '小' '长' '长' 'versicolor' '' '小' '短' '长' 'versicolor' '' '小' '长' '长' 'versicolor' '' '小' '短' '长' 've

35、rsicolor' '' '小' '长' '短' 'versicolor' '' '大' '长' '长' 'versicolor' '' '大' '长' '短' 'versicolor' '' '大' '长' '长' 'versicolor' '' 

36、9;大' '长' '长' 'versicolor' '' '大' '长' '长' 'versicolor' '' '大' '长' '长' 'versicolor' '' '小' '长' '长' 'setosa' '' '大' '短' '长'

37、 'versicolor' '' '大' '短' '长' 'versicolor' '' '大' '短' '长' 'versicolor' '' '大' '短' '长' 'versicolor' '' '大' '短' '短' 'versicolor' '' '小' '短' '短' 'setosa' '' '小' '短' '长' 'setosa' '' '小' '短' '长' 'setosa'