ID3.rar_7LC_ID3 分类_id3_matlab id3_决策树ID3

function [ tree ] = id3( examples, attributes, activeAttributes ) %% ID3 算法 ，构建ID3决策树 ...参考：https://github.com/gwheaton/ID3-Decision-Tree % 输入参数： % example: 输入0、1矩阵； % attributes: 属性值，含有Label； % activeAttributes: 活跃的属性值；-1,1向量，1表示活跃； % 输出参数： % tree：构建的决策树； %% 提供的数据为空，则报异常 if (isempty(examples)); error('必须提供数据！'); end % 常量 numberAttributes = length(activeAttributes); numberExamples = length(examples(:,1)); % 创建树节点 tree = struct('value', 'null', 'left', 'null', 'right', 'null'); % 如果最后一列全部为1，则返回“true” lastColumnSum = sum(examples(:, numberAttributes + 1)); if (lastColumnSum == numberExamples); tree.value = 'true'; return end % 如果最后一列全部为0，则返回“false” if (lastColumnSum == 0); tree.value = 'false'; return end % 如果活跃的属性为空，则返回label最多的属性值 if (sum(activeAttributes) == 0); if (lastColumnSum >= numberExamples / 2); tree.value = 'true'; else tree.value = 'false'; 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 % 熵 S(v=1) if (~s1); 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; % 熵 S(v=0) if (~s0); 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