生物數(shù)據(jù)挖掘-決策樹實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)四 決策樹一、 實(shí)驗(yàn)?zāi)康?. 了解典型決策樹算法2. 熟悉決策樹算法的思路與步驟3. 掌握運(yùn)用Matlab對(duì)數(shù)據(jù)集做決策樹分析的方法二、 實(shí)驗(yàn)內(nèi)容1.運(yùn)用Matlab對(duì)數(shù)據(jù)集做決策樹分析三、 實(shí)驗(yàn)步驟1.寫出對(duì)決策樹算法的理解決策樹方法是數(shù)據(jù)挖掘的重要方法之一，它是利用樹形結(jié)構(gòu)的特性來(lái)對(duì)數(shù)據(jù)進(jìn)行分類的一種方法。決策樹學(xué)習(xí)從一組無(wú)規(guī)則、無(wú)次序的事例中推理出有用的分類規(guī)則，是一種實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。決策樹首先利用訓(xùn)練數(shù)據(jù)集合生成一個(gè)測(cè)試函數(shù)，根據(jù)不同的權(quán)值建立樹的分支，即葉子結(jié)點(diǎn)，在每個(gè)葉子節(jié)點(diǎn)下又建立層次結(jié)點(diǎn)和分支，如此重利生成決策樹，然后對(duì)決策樹進(jìn)行剪樹處理

2、，最后把決策樹轉(zhuǎn)換成規(guī)則。決策樹的最大優(yōu)點(diǎn)是直觀，以樹狀圖的形式表現(xiàn)預(yù)測(cè)結(jié)果，而且這個(gè)結(jié)果可以進(jìn)行解釋。決策樹主要用于聚類和分類方面的應(yīng)用。決策樹是一樹狀結(jié)構(gòu)，它的每一個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)分類，非葉子節(jié)點(diǎn)對(duì)應(yīng)著在某個(gè)屬性上的劃分，根據(jù)樣本在該屬性上的不同取值將其劃分成若干個(gè)子集。構(gòu)造決策樹的核心問題是在每一步如何選擇適當(dāng)?shù)膶傩詫?duì)樣本進(jìn)行拆分。對(duì)一個(gè)分類問題，從已知類標(biāo)記的訓(xùn)練樣本中學(xué)習(xí)并構(gòu)造出決策樹是一個(gè)自上而下分而治之的過(guò)程。2.啟動(dòng)Matlab，運(yùn)用Matlab對(duì)數(shù)據(jù)集進(jìn)行決策樹分析，寫出算法名稱、數(shù)據(jù)集名稱、關(guān)鍵代碼，記錄實(shí)驗(yàn)過(guò)程，實(shí)驗(yàn)結(jié)果，并分析實(shí)驗(yàn)結(jié)果(1) 算法名稱: ID3算法I

3、D3算法是最經(jīng)典的決策樹分類算法。ID3算法基于信息熵來(lái)選擇最佳的測(cè)試屬性，它選擇當(dāng)前樣本集中具有最大信息增益值的屬性作為測(cè)試屬性；樣本集的劃分則依據(jù)測(cè)試屬性的取值進(jìn)行，測(cè)試屬性有多少個(gè)不同的取值就將樣本集劃分為多少個(gè)子樣本集，同時(shí)決策樹上相應(yīng)于該樣本集的節(jié)點(diǎn)長(zhǎng)出新的葉子節(jié)點(diǎn)。ID3算法根據(jù)信息論的理論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標(biāo)準(zhǔn)，用信息增益值度量不確定性：信息增益值越大，不確定性越小。因此，ID3算法在每個(gè)非葉節(jié)點(diǎn)選擇信息增益最大的屬性作為測(cè)試屬性，這樣可以得到當(dāng)前情況下最純的劃分，從而得到較小的決策樹。ID3算法的具體流程如下： 1）對(duì)當(dāng)前樣本集合，計(jì)算所有屬性的信息

4、增益； 2）選擇信息增益最大的屬性作為測(cè)試屬性，把測(cè)試屬性取值相同的樣本劃為同一個(gè)子樣本集； 3）若子樣本集的類別屬性只含有單個(gè)屬性，則分支為葉子節(jié)點(diǎn)，判斷其屬性值并標(biāo)上相應(yīng)的符號(hào)，然后返回調(diào)用處；否則對(duì)子樣本集遞歸調(diào)用本算法。(2) 數(shù)據(jù)集名稱：鳶尾花卉Iris數(shù)據(jù)集選擇了部分?jǐn)?shù)據(jù)集來(lái)區(qū)分Iris Setosa（山鳶尾）及Iris Versicolour（雜色鳶尾）兩個(gè)種類。（3）實(shí)驗(yàn)代碼：% 使用ID3決策樹算法預(yù)測(cè)鳶尾花卉Iris種類clear ;% 數(shù)據(jù)預(yù)處理disp('正在進(jìn)行數(shù)據(jù)預(yù)處理.');matrix,attributes_label,attributes =

5、id3_preprocess();% 構(gòu)造ID3決策樹，其中id3()為自定義函數(shù)disp('數(shù)據(jù)預(yù)處理完成，正在進(jìn)行構(gòu)造樹.');tree = id3(matrix,attributes_label,attributes);% 打印并畫決策樹nodeids,nodevalues = print_tree(tree);tree_plot(nodeids,nodevalues);disp('ID3算法構(gòu)建決策樹完成！');% 構(gòu)造函數(shù)id3_preprocessfunction matrix,attributes,activeAttributes = id3_pr

6、eprocess( )% ID3算法數(shù)據(jù)預(yù)處理，把字符串轉(zhuǎn)換為0,1編碼% 讀取數(shù)據(jù)txt= '序號(hào)' '花萼大小' '花瓣長(zhǎng)度' '花瓣寬度' '類型' '' '小' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)'

7、 'versicolor' '' '小' '短' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '短' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '短' 'versicolor' '&

8、#39; '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)' '短' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)'

9、 '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)' 'setosa' '' '大' '短' '長(zhǎng)' 'versicolor' '' '大' '短' '長(zhǎng)' 'versicolor'

10、; '' '大' '短' '長(zhǎng)' 'versicolor' '' '大' '短' '長(zhǎng)' 'versicolor' '' '大' '短' '短' 'versicolor' '' '小' '短' '短' 'setosa' '' '小' '短&

11、#39; '長(zhǎng)' 'setosa' '' '小' '短' '長(zhǎng)' 'setosa' '' '小' '短' '長(zhǎng)' 'setosa' '' '小' '短' '短' 'setosa' '' '小' '長(zhǎng)' '短' 'setosa' ''

12、 '大' '短' '長(zhǎng)' 'setosa' '' '大' '短' '長(zhǎng)' 'setosa' '' '小' '短' '短' 'setosa' '' '小' '短' '短' 'setosa' '' '大' '短' '短' 'se

13、tosa' '' '小' '長(zhǎng)' '短' 'setosa' '' '大' '短' '長(zhǎng)' '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);% 針對(duì)每列數(shù)據(jù)進(jìn)行轉(zhuǎn)換rows,cols = size(data);matrix = zeros(rows,cols);% matrix： 轉(zhuǎn)換后的0,1矩陣；for j=1:cols matrix(:,j) = cellfun(trans2onezero,data(:,j);endend%構(gòu)造函數(shù)trans2onezerofunction flag = trans2

15、onezero(data) if strcmp(data,'小')|strcmp(data,'短'). |strcmp(data,'setosa') flag =0; return ; end flag =1;end%構(gòu)造函數(shù)id3function tree = id3( examples, attributes, activeAttributes )% ID3 算法 ，構(gòu)建ID3決策樹% 提供的數(shù)據(jù)為空，則報(bào)異常if (isempty(examples); error('必須提供數(shù)據(jù)！');endnumberAttributes

16、 = length(activeAttributes);% activeAttributes: 活躍的屬性值；-1,1向量，1表示活躍；numberExamples = length(examples(:,1);% example: 輸入0、1矩陣；% 創(chuàng)建樹節(jié)點(diǎn)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% 計(jì)算當(dāng)前屬性的熵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) % 該屬性仍處于活躍狀態(tài)，對(duì)其更新 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);% 設(shè)置相應(yīng)值tree.value = attributesbestAttribute;% 去活躍狀態(tài)activeAttributes(bestAttribute) = 0;% 根據(jù)bestAttribute把數(shù)據(jù)進(jìn)行分組examples_

23、0= examples(examples(:,bestAttribute)=0,:);examples_1= examples(examples(:,bestAttribute)=1,:);% 當(dāng) 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% 當(dāng) 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%構(gòu)造函數(shù)print_treefunction nodeids_,nodevalu

26、e_ = print_tree(tree)% 打印樹，返回樹的關(guān)系向量global nodeid nodeids nodevalue;nodeids(1)=0; % 根節(jié)點(diǎn)的值為0nodeid=0;nodevalue=;if isempty(tree) disp('空樹！'); return ;endqueue = queue_push(,tree);while isempty(queue) % 隊(duì)列不為空 node,queue = queue_pop(queue); % 出隊(duì)列 visit(node,queue_curr_size(queue); if strcmp(node

27、.left,'null') % 左子樹不為空 queue = queue_push(queue,node.left); % 進(jìn)隊(duì) end if strcmp(node.right,'null') % 左子樹不為空 queue = queue_push(queue,node.right); % 進(jìn)隊(duì) endend% 返回 節(jié)點(diǎn)關(guān)系，用于treeplot畫圖nodeids_=nodeids;nodevalue_=nodevalue;end%構(gòu)造函數(shù)visitfunction visit(node,length_)% 訪問node 節(jié)點(diǎn)，并把其設(shè)置值為nodeid的節(jié)

28、點(diǎn) global nodeid nodeids nodevalue; if isleaf(node) nodeid=nodeid+1; fprintf('葉子節(jié)點(diǎn)，node: %dt，屬性值: %sn', . nodeid, node.value); nodevalue1,nodeid=node.value; else % 要么是葉子節(jié)點(diǎn)，要么不是 %if isleaf(node.left) && isleaf(node.right) % 左邊為葉子節(jié)點(diǎn),右邊不是 nodeid=nodeid+1; nodeids(nodeid+length_+1)=nodeid

29、; nodeids(nodeid+length_+2)=nodeid; fprintf('node: %dt屬性值: %st，左子樹為節(jié)點(diǎn)：node%d，右子樹為節(jié)點(diǎn)：node%dn', . nodeid, node.value,nodeid+length_+1,nodeid+length_+2); nodevalue1,nodeid=node.value; endend%構(gòu)造函數(shù)isleaffunction flag = isleaf(node)% 是否是葉子節(jié)點(diǎn) if strcmp(node.left,'null') && strcmp(no

30、de.right,'null') % 左右都為空 flag =1; else flag=0; endend%構(gòu)造函數(shù)tree_plotfunction tree_plot( p ,nodevalues)% 參考treeplot函數(shù)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%構(gòu)造函數(shù)queue_curr_sizefunction length_ = qu

32、eue_curr_size( queue )% 當(dāng)前隊(duì)列長(zhǎng)度length_= length(queue);end%構(gòu)造函數(shù)queue_popfunction item,newqueue = queue_pop( queue )% 訪問隊(duì)列if isempty(queue) disp('隊(duì)列為空，不能訪問！'); return;enditem = queue(1); % 第一個(gè)元素彈出newqueue=queue(2:end); % 往后移動(dòng)一個(gè)元素位置end%構(gòu)造函數(shù)queue_pushfunction newqueue = queue_push( queue,item )%

33、進(jìn)隊(duì)% cols = size(queue);% newqueue =structs(1,cols+1);newqueue=queue,item;end（4）實(shí)驗(yàn)步驟：>> Untitled正在進(jìn)行數(shù)據(jù)預(yù)處理.txt = 35×5 cell 數(shù)組 '序號(hào)' '花萼大小' '花瓣長(zhǎng)度' '花瓣寬度' '類型' '' '小' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' 

34、9;長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '短' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '短' '長(zhǎng)' 've

35、rsicolor' '' '小' '長(zhǎng)' '短' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)' '短' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' 

36、9;大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '大' '長(zhǎng)' '長(zhǎng)' 'versicolor' '' '小' '長(zhǎng)' '長(zhǎng)' 'setosa' '' '大' '短' '長(zhǎng)'

37、 'versicolor' '' '大' '短' '長(zhǎng)' 'versicolor' '' '大' '短' '長(zhǎng)' 'versicolor' '' '大' '短' '長(zhǎng)' 'versicolor' '' '大' '短' '短' 'versicolor' '' '小' '短' '短' 'setosa' '' '小' '短' '長(zhǎng)' 'setosa' '' '小' '短' '長(zhǎng)' 'setosa'