id3算法matlab

A. 通过ID3算法得出的决策树怎么去测试别的实例啊还有ID3算法是只能分析数值型的数据吗

如果通过训练集已经得出决策树的话， 那使用测试集测试就很简单了。 可以人工测试，也可以用数据分析软件。

数据可以有很多种类型，关键是看你怎么提取出数据的属性进行分析。

请采纳最佳答案~

B. 请问matlab中的treefit函数使用的是ID3算法吗matlab有没有其他的决策树算法或者第三方开发的源程序包

是ID3，可以参考文章： Breiman, L., J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Boca Raton, FL: CRC Press, 1984. 里面有参数可以设置算法：classification regression

C. id3算法是什么

ID3算法是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

ID3算法的背景

ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

D. id3算法matable实现 并解释一下怎么输入数据和参数

是mutable吗？
mutalbe的中文意思是“可变的，易变的”，跟constant（既C++中的const）是反义词。

在C++中，mutable也是为了突破const的限制而设置的。被mutable修饰的变量，将永远处于可变的状态，即使在一个const函数中。

我们知道，如果类的成员函数不会改变对象的状态，那么这个成员函数一般会声明成const的。但是，有些时候，我们需要在const的函数里面修改一些跟类状态无关的数据成员，那么这个数据成员就应该被mutalbe来修饰。

ID3的 解释
ID3算法是由Quinlan首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。以下是一些信息论的基本概念： 定义1：若存在n个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为Log2(n) 定义2：若有n个消息，其给定概率分布为P=(p1,p2…pn)，则由该分布传递的信息量称为P的熵，记为 I(p)=-(i=1 to n求和)piLog2(pi)。 定义3：若一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck，则识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|) 定义4：若我们先根据非类别属性X的值将T分成集合T1,T2…Tn，则确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到，即Info(Ti)的加权平均值为： Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti)) 定义5：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为： Gain(X, T)=Info(T)-Info(X, T) ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本. 一个nonincremental ID3算法,推导其阶级意义从一组固定的训练资料中。一个增量算法修改当前的概念界定,如果有必要,与一种新的样品。这个班由ID3是感应,那是,给定一小组训练资料中,特定的课程由ID3预计未来所有的情况下工作。未知的分布必须相同的测试用例。感应类无法证明工作在每种情况下,因为他们可以无限的情况下进行分类。注意,ID3(或任何可能misclassify归纳算法)数据。

可以 再联系

E. 决策树ID3，C4.5，CART算法中某一属性分类后，是否能运用该属性继续分类

决策树主要有ID3，C4.5，CART等形式。ID3选取信息增益的属性递归进行分类，C4.5改进为使用信息增益率来选取分类属性。CART是Classfication and Regression Tree的缩写。表明CART不仅可以进行分类，也可以进行回归。其中使用基尼系数选取分类属性。以下主要介绍ID3和CART算法。
ID3算法：
信息熵： H(X)=-sigma（对每一个x）（plogp） H(Y|X)=sigma(对每一个x)（pH(Y|X=xi)）
信息增益：H（D）-H(D|X) H(D)是整个数据集的熵
信息增益率：（H(D)-H(D|X)）/H(X)
算法流程：（1）对每一个属性计算信息增益，若信息增益小于阈值，则将该支置为叶节点，选择其中个数最多的类标签作为该类的类标签。否则，选择其中最大的作为分类属 性。
（2）若各个分支中都只含有同一类数据，则将这支置为叶子节点。
否则 继续进行（1）。
CART算法：
基尼系数：Gini（p）=sigma（每一个类）p(1-p)
回归树：属性值为连续实数。将整个输入空间划分为m块，每一块以其平均值作为输出。f(x)=sigma(每一块)Cm*I(x属于Rm)
回归树生成：（1）选取切分变量和切分点，将输入空间分为两份。
（2）每一份分别进行第一步，直到满足停止条件。
切分变量和切分点选取：对于每一个变量进行遍历，从中选择切分点。选择一个切分点满足分类均方误差最小。然后在选出所有变量中最小分类误差最小的变量作为切分 变量。
分类树：属性值为离散值。
分类树生成：（1）根据每一个属性的每一个取值，是否取该值将样本分成两类，计算基尼系数。选择基尼系数最小的特征和属性值，将样本分成两份。
（2）递归调用（1）直到无法分割。完成CART树生成。

决策树剪枝策略：
预剪枝（树提前停止生长）和后剪枝（完全生成以后减去一些子树提高预测准确率）
降低错误率剪枝：自下而上对每一个内部节点比较减去以其为叶节点和子树的准确率。如果减去准确率提高，则减去，依次类推知道准确率不在提高。
代价复杂度剪枝：从原始决策树T0开始生成一个子树序列{T0、T1、T2、...、Tn},其中Ti+1是从Ti总产生，Tn为根节点。每次均从Ti中 减去具有最小误差增长率的子树。然后通过 交叉验证比较序列中各子树的效果选择最优决策树。

F. 简述ID3算法基本原理和步骤

1.基本原理：
以信息增益/信息熵为度量，用于决策树结点的属性选择的标准，每次优先选取信息量最多（信息增益最大）的属性，即信息熵值最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0。（信息熵 无条件熵 条件熵 信息增益 请查找其他资料理解）
决策树将停止生长条件及叶子结点的类别取值：
①数据子集的每一条数据均已经归类到每一类，此时，叶子结点取当前样本类别值。
②数据子集类别仍有混乱，但已经找不到新的属性进行结点分解，此时，叶子结点按当前样本中少数服从多数的原则进行类别取值。
③数据子集为空，则按整个样本中少数服从多数的原则进行类别取值。

步骤：
理解了上述停止增长条件以及信息熵，步骤就很简单

G. 哪位朋友有id3算法的Matlab代码 麻烦给我发一下 [email protected]

function D = ID3(train_features, train_targets, params, region)

% Classify using Quinlan´s ID3 algorithm

% Inputs:

% features - Train features

% targets - Train targets

% params - [Number of bins for the data, Percentage of incorrectly assigned samples at a node]

% region - Decision region vector: [-x x -y y number_of_points]

%

% Outputs

% D - Decision sufrace

[Ni, M] = size(train_features);

%Get parameters

[Nbins, inc_node] = process_params(params);

inc_node = inc_node*M/100;

%For the decision region

N = region(5);

mx = ones(N,1) * linspace (region(1),region(2),N);

my = linspace (region(3),region(4),N)´ * ones(1,N);

flatxy = [mx(, my(]´;

%Preprocessing

[f, t, UW, m] = PCA(train_features, train_targets, Ni, region);

train_features = UW * (train_features - m*ones(1,M));;

flatxy = UW * (flatxy - m*ones(1,N^2));;

%First, bin the data and the decision region data

[H, binned_features]= high_histogram(train_features, Nbins, region);

[H, binned_xy] = high_histogram(flatxy, Nbins, region);

%Build the tree recursively

disp(´Building tree´

tree = make_tree(binned_features, train_targets, inc_node, Nbins);

%Make the decision region according to the tree

disp(´Building decision surface using the tree´

targets = use_tree(binned_xy, 1:N^2, tree, Nbins, unique(train_targets));

D = reshape(targets,N,N);

%END

function targets = use_tree(features, indices, tree, Nbins, Uc)

%Classify recursively using a tree

targets = zeros(1, size(features,2));

if (size(features,1) == 1),

%Only one dimension left, so work on it

for i = 1:Nbins,

in = indices(find(features(indices) == i));

if ~isempty(in),

if isfinite(tree.child(i)),

targets(in) = tree.child(i);

else

%No data was found in the training set for this bin, so choose it randomally

n = 1 + floor(rand(1)*length(Uc));

targets(in) = Uc(n);

end

end

end

break

end

%This is not the last level of the tree, so:

%First, find the dimension we are to work on

dim = tree.split_dim;

dims= find(~ismember(1:size(features,1), dim));

%And classify according to it

for i = 1:Nbins,

in = indices(find(features(dim, indices) == i));

targets = targets + use_tree(features(dims, , in, tree.child(i), Nbins, Uc);

end

%END use_tree

function tree = make_tree(features, targets, inc_node, Nbins)

%Build a tree recursively

[Ni, L] = size(features);

Uc = unique(targets);

%When to stop: If the dimension is one or the number of examples is small

if ((Ni == 1) | (inc_node > L)),

%Compute the children non-recursively

for i = 1:Nbins,

tree.split_dim = 0;

indices = find(features == i);

if ~isempty(indices),

if (length(unique(targets(indices))) == 1),

tree.child(i) = targets(indices(1));

else

H = hist(targets(indices), Uc);

[m, T] = max(H);

tree.child(i) = Uc(T);

end

else

tree.child(i) = inf;

end

end

break

end

%Compute the node´s I

for i = 1:Ni,

Pnode(i) = length(find(targets == Uc(i))) / L;

end

Inode = -sum(Pnode.*log(Pnode)/log(2));

%For each dimension, compute the gain ratio impurity

delta_Ib = zeros(1, Ni);

P = zeros(length(Uc), Nbins);

for i = 1:Ni,

for j = 1:length(Uc),

for k = 1:Nbins,

indices = find((targets == Uc(j)) & (features(i, == k));

P(j,k) = length(indices);

end

end

Pk = sum(P);

P = P/L;

Pk = Pk/sum(Pk);

info = sum(-P.*log(eps+P)/log(2));

delta_Ib(i) = (Inode-sum(Pk.*info))/-sum(Pk.*log(eps+Pk)/log(2));

end

%Find the dimension minimizing delta_Ib

[m, dim] = max(delta_Ib);

%Split along the ´dim´ dimension

tree.split_dim = dim;

dims = find(~ismember(1:Ni, dim));

for i = 1:Nbins,

indices = find(features(dim, == i);

tree.child(i) = make_tree(features(dims, indices), targets(indices), inc_node, Nbins);

H. 决策树之ID3算法及其Python实现

决策树之ID3算法及其Python实现

1. 决策树背景知识
??决策树是数据挖掘中最重要且最常用的方法之一，主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式，决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来，经过几十年发展，目前常用的算法有：ID3、C4.5、CART算法等。
2. 决策树一般构建过程
??构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程，每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始，根据选取分裂属性的属性值把训练集划分成不同的数据子集，生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程，直到满足特定的终止条件，停止对数据子集划分，生成数据子集对应的叶子节点，即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标，我们需要对决策树算法进行改善，直到达到预期的性能指标。
??注：分裂属性的选取是决策树生产过程中的关键，它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。
3. ID3算法分裂属性的选择——信息增益
??属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础，选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后，使得分裂后的样本的信息量最大，不确定性最小，即熵最小。
??信息增益的定义为变化前后熵的差值，而熵的定义为信息的期望值，因此在了解熵和信息增益之前，我们需要了解信息的定义。
??信息：分类标签xi 在样本集 S 中出现的频率记为 p(xi)，则 xi 的信息定义为：?log2p(xi) 。
??分裂之前样本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 为分类标签的个数。
??通过属性A分裂之后样本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集，|Sj| 表示第j个子样本集中样本数量，|S| 表示分裂之前数据集中样本总数量。
??通过属性A分裂之后样本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??注：分裂属性的选择标准为：分裂前后信息增益越大越好，即分裂后的熵越小越好。
4. ID3算法
??ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是：通过计算属性的信息增益来选择决策树各级节点上的分裂属性，使得在每一个非叶子节点进行测试时，获得关于被测试样本最大的类别信息。基本方法是：计算所有的属性，选择信息增益最大的属性分裂产生决策树节点，基于该属性的不同属性值建立各分支，再对各分支的子集递归调用该方法建立子节点的分支，直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树，可用来对新样本数据进行分类。
ID3算法流程：
(1) 创建一个初始节点。如果该节点中的样本都在同一类别，则算法终止，把该节点标记为叶节点，并用该类别标记。
(2) 否则，依据算法选取信息增益最大的属性，该属性作为该节点的分裂属性。
(3) 对该分裂属性中的每一个值，延伸相应的一个分支，并依据属性值划分样本。
(4) 使用同样的过程，自顶向下的递归，直到满足下面三个条件中的一个时就停止递归。
??A、待分裂节点的所有样本同属于一类。
??B、训练样本集中所有样本均完成分类。
??C、所有属性均被作为分裂属性执行一次。若此时，叶子结点中仍有属于不同类别的样本时，选取叶子结点中包含样本最多的类别，作为该叶子结点的分类。
ID3算法优缺点分析
优点：构建决策树的速度比较快，算法实现简单，生成的规则容易理解。
缺点：在属性选择时，倾向于选择那些拥有多个属性值的属性作为分裂属性，而这些属性不一定是最佳分裂属性；不能处理属性值连续的属性；无修剪过程，无法对决策树进行优化，生成的决策树可能存在过度拟合的情况。

I. 数据挖掘ID3算法有一些不懂

十经典算： 我看谭磊本书 面网站给答案： 1. C4.5 C4.5算机器习算种类决策树算,其核算ID3算. C4.5算继承ID3算优点并几面ID3算进行改进： 1) 用信息增益率选..

J. ID3算法的背景知识

ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。
决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。
决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点，每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中，在每个结点都会遇到一个测试，对每个结点上问题的不同的测试输出导致不同的分支，最后会到达一个叶子结点，这个过程就是利用决策树进行分类的过程，利用若干个变量来判断所属的类别。