這一章主要打算用大白話說(shuō)一下決策樹(shù)是什么，然后介紹一個(gè)算法中的核心輔助結(jié)構(gòu)——Cluster 的實(shí)現(xiàn)（我也不知道中文叫什么我也不知道為什么當(dāng)初腦子里第一個(gè)蹦出來(lái)的就是這個(gè)名字）（逃）
決策樹(shù)，顧名思義，就是用來(lái)決策的樹(shù)（廢話）。可以這樣去想一個(gè)決策樹(shù)的決策過(guò)程：
-
輸入一個(gè)數(shù)據(jù)
-
根據(jù)數(shù)據(jù)的某個(gè)特征來(lái)把數(shù)據(jù)分成好幾份
-
如果分完數(shù)據(jù)后發(fā)現(xiàn)
-
某堆數(shù)據(jù)里面某一個(gè)類別的數(shù)據(jù)占相當(dāng)大多數(shù)，就不再分隔這堆數(shù)據(jù)、直接輸出類別
-
某堆數(shù)據(jù)還很“混亂無(wú)序”，那么就這堆數(shù)據(jù)就要繼續(xù)分下去（轉(zhuǎn)第 2. 步）
-
大概就這三步。可以發(fā)現(xiàn)，大部分時(shí)間都是根據(jù)某個(gè)“準(zhǔn)則”來(lái)進(jìn)行操作的，所以怎樣選擇這個(gè)準(zhǔn)則就成了至關(guān)重要的問(wèn)題
我們同時(shí)還可以發(fā)現(xiàn)，這個(gè)過(guò)程是個(gè)遞歸過(guò)程。通俗點(diǎn)來(lái)說(shuō)，就是整個(gè)過(guò)程都是對(duì)同一類物體做的同一系列操作
以上兩個(gè)發(fā)現(xiàn)對(duì)應(yīng)著兩個(gè)核心。這一章我們就先講第一個(gè)核心——準(zhǔn)則
常見(jiàn)的準(zhǔn)則有兩種，分別是熵和 Gini 系數(shù)。這里就主講實(shí)現(xiàn)（Again，我會(huì)先講一個(gè)相對(duì)樸素的實(shí)現(xiàn)，而把支持樣本權(quán)重的版本放在后面）：
-
預(yù)處理數(shù)據(jù)，準(zhǔn)備好接下來(lái)可能要用到的變量
-
-
輸入的 data 是 n x d 維的；n 代表有 n 個(gè)數(shù)據(jù)，d 代表有 d 個(gè)維度
-
輸入的 labels 是標(biāo)簽向量
-
Counter 是內(nèi)置庫(kù)的功能，用于數(shù) labels 中各個(gè)類別的出現(xiàn)次數(shù)
-
base 是計(jì)算熵的時(shí)候?qū)?shù)的底，基本可以不管
-
-
熵與條件熵
-
利用 labels 和 counters 計(jì)算
這里支持用戶自己輸入各類別的出現(xiàn)次數(shù)；如果沒(méi)有輸入，就用內(nèi)置的類別次數(shù)代替
eps 則是為了數(shù)值穩(wěn)定-
利用上述 ent 函數(shù)計(jì)算相對(duì)熵（建議先知道定義是什么再看……）
看上去很復(fù)雜，其實(shí)就四點(diǎn)：
-
獲取指定維度數(shù)據(jù)的所有特征
-
根據(jù)這些特征將原數(shù)據(jù)切分成若干份
-
將這幾份數(shù)據(jù)分別喂給一個(gè) Cluster 并利用上面第 1. 步定義的 ent 函數(shù)算出熵
-
把這些熵按定義弄出一個(gè)條件熵
-
-
-
Gini 系數(shù)，這個(gè)實(shí)現(xiàn)起來(lái)比較方便、因?yàn)樾问奖容^簡(jiǎn)單
同樣支持用戶自己輸入各類別的出現(xiàn)次數(shù)
-
信息增益。這是決策樹(shù)生長(zhǎng)的重點(diǎn)，但有了上面兩個(gè)函數(shù)之后，根據(jù)定義的話、直接條件熵減去熵就行（或者更寬泛地說(shuō)、是混亂程度減去條件混亂程度），最多再做一些小的改動(dòng)。相信聰明的觀眾老爺們可以輕松地完成最樸素的實(shí)現(xiàn)，所以在這里我就不細(xì)講怎么定義 info_gain 了，等到講比較復(fù)雜的模型時(shí)再補(bǔ)吧~
順便也可以當(dāng)做作業(yè)和練習(xí)呢~
其實(shí)主要是因?yàn)閼心貇（被 pia 飛）
========== 更新 ==========
這里提供一個(gè)根據(jù) ID3 算法的信息增益實(shí)現(xiàn)，C4.5 和 CART 的話會(huì)在后面講~
感谢您访问我们的网站，您可能还对以下资源感兴趣：
掃一掃獲取最新精彩內(nèi)容與學(xué)習(xí)資料