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演算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標准，重復這個過程，直至生成一個能完美分類訓練樣例的決策樹。
決策樹是對數據進行分類，以此達到預測的目的。該決策樹方法先根據訓練集數據形成決策樹，如果該樹不能對所有對象給出正確的分類，那麼選擇一些例外加入到訓練集數據中，重復該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結構。
決策樹由決策結點、分支和葉子組成。決策樹中最上面的結點為根結點，每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或決策，通常對應於待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。沿決策樹從上到下遍歷的過程中，在每個結點都會遇到一個測試，對每個結點上問題的不同的測試輸出導致不同的分支，最後會到達一個葉子結點，這個過程就是利用決策樹進行分類的過程，利用若干個變數來判斷所屬的類別。