標(biāo)題:
決策樹算法詳解
[打印本頁]
作者:
jialinx
時間:
2015-9-15 14:56
標(biāo)題:
決策樹算法詳解
決策樹算法是一種逼近離散函數(shù)值的方法，是一種典型的分類方法。
決策樹算法構(gòu)造決策樹來發(fā)現(xiàn)數(shù)據(jù)中蘊(yùn)涵的分類規(guī)則。如何
構(gòu)造精度高，規(guī)模小的決策樹
是決策樹算法的
核心
內(nèi)容。一般情況下分兩步進(jìn)行，
1.決策樹的生成。
2.決策樹的剪枝。（對上一個階段生成的決策樹進(jìn)行檢驗，校正和修下的過程，方法：使用測試數(shù)據(jù)集校驗1中生成的決策樹，將那些影響準(zhǔn)確性的分枝剪除）
典型算法
ID3算法，此算法目的在于減少樹的深度。但是忽略了葉子數(shù)目的研究。
C4.5算法，在ID3算法的基礎(chǔ)上進(jìn)行了改進(jìn)，對于預(yù)測變量的缺值處理，剪枝技術(shù)，派生規(guī)則等方面做了較大的改進(jìn)，既適合于
分類
問題，又適合于
回歸
問題。
總結(jié)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。不過在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，在實際應(yīng)用中會導(dǎo)致算法低效。
決策樹算法的優(yōu)點如下：
1.分類精度高；
2.生成的模式簡單；
3.對噪聲數(shù)據(jù)有很好的健壯性。
以上為概念總結(jié)。
——————————————————————————————————————————————————————————
-信息增益
在劃分?jǐn)?shù)據(jù)集之前后信息發(fā)生的變化稱之為信息增益，計算每個特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。
計算方法（香農(nóng)熵）
熵定義為信息的期望值。計算公式如下：
符號xi的信息定義為l(xi)=-log2p(xi)，其中p(xi)是選擇該分類的概率。（各分類在總實例中得比例）
所有類別所有可能值包含的信息期望值H=-∑ni=1p(xi)log2p(xi),其中n分類的數(shù)目。
-劃分?jǐn)?shù)據(jù)集
對每個特征劃分?jǐn)?shù)據(jù)集的結(jié)果計算一次信息熵，然后判斷按照哪個特征劃分?jǐn)?shù)據(jù)集是最好的劃分方式。
增益=元數(shù)據(jù)的熵-按特征量劃分的熵 -->增益越大 劃分越優(yōu)
-遞歸構(gòu)建決策樹
工作原理如下：
1.得到原始數(shù)據(jù)集
2.基于好的屬性劃分?jǐn)?shù)據(jù)集
3.特征值多于兩個的情況下�？赡艽嬖诖笥趦蓚€分支的數(shù)據(jù)集劃分。第一次劃分后，數(shù)據(jù)被向下傳遞到樹分支的下一個節(jié)點，在這個節(jié)點上再次劃分?jǐn)?shù)據(jù)。
遞歸的結(jié)束條件：1.遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性 2 每個分支下得所有實例都具有相同的分類。
后續(xù)：改進(jìn)算法的總結(jié)和代碼整理
歡迎光臨 (http://www.torrancerestoration.com/bbs/)
Powered by Discuz! X3.1