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