本文關(guān)鍵詞：決策樹分類，由筆耕文化傳播整理發(fā)布。

算法總結(jié)2—決策樹分類器

數(shù)學(xué)基礎(chǔ)：

樹：樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個結(jié)點有零個或多個子結(jié)點；

每一個子結(jié)點只有一個父結(jié)點；

沒有前驅(qū)的結(jié)點為根結(jié)點；

除了根結(jié)點外，每個子結(jié)點可以分為m個不相交的子樹；

沒有子節(jié)點的節(jié)點稱為葉節(jié)點。

決策樹分類器原理：

決策樹是一顆樹，要分類的樣本從樹根進入，在樹的每個節(jié)點通過對樣本的某種屬性的判斷選擇不同的路徑逐步下降到底,得出其所屬類別。

例圖:

為了建立一棵決策樹,我們首先應(yīng)向程序輸入大量訓(xùn)練數(shù)據(jù)(包含所屬類別的數(shù)據(jù))，程序?qū)⒏鶕?jù)訓(xùn)練數(shù)據(jù)按某一算法自動生成決策樹。

決策樹生成算法:

   為了構(gòu)造決策樹，算法首先創(chuàng)建一個根節(jié)點，然后通過分析訓(xùn)練數(shù)據(jù)，逐步選出適合的變量對數(shù)據(jù)進行拆分(即逐步構(gòu)造上圖中的非葉子節(jié)點。)

   為了選擇適合的變量對數(shù)據(jù)進行拆分，我們需要一個方法來評估一種拆分方案的好壞，其評估方法包括：

1)      基尼不純度：

定義：基尼不存度是指來自集合的某種結(jié)果隨機應(yīng)用于集合中某一數(shù)據(jù)的預(yù)期誤差。（如果集合中所有結(jié)果屬于同一類，則誤差為0）

使用：利用這一思想，我們可以將集合中每種類別的數(shù)據(jù)出現(xiàn)的次數(shù)除以數(shù)據(jù)總數(shù)計算相應(yīng)概率，再將這些概率的乘積相加（所有概率兩兩相乘后在相加），，這樣就會得到某一數(shù)據(jù)被隨機分配到錯誤結(jié)果的總概率。

偽代碼：

imp=0

for  k1 in kinds

p1=count(k1) / total

for k2 in counts

   if (k1==k2)continue

   p2=count(k2) / total

   imp+=p1*p2

    ans=imp

   (p1*p2是一個p1類別的數(shù)據(jù)被當(dāng)作p2的概率)

2)      熵：在信息論中，熵代表的是集合的無序程度-----基本上就相當(dāng)于我們在此處所說的集合的混雜程度。

熵的值是遍歷所有結(jié)果后得到的pi*log2(pi)的和的絕對值

偽代碼：

ent=0.0

for k in kinds

p=count(k) / total

ent=ent – p*log2(p)     // 因為0

  本文關(guān)鍵詞：決策樹分類，由筆耕文化傳播整理發(fā)布。