機(jī)器學(xué)習(xí)：談?wù)?a href='/map/jueceshu/' style='color:#000;font-size:inherit;'>決策樹

今天，我們繼續(xù)開啟分類算法之旅，它是一種高效簡介的分類算法，后面有一個(gè)集成算法正是基于它之上，它是一個(gè)可視化效果很好的算法，這個(gè)算法就是決策樹。

1 一個(gè)例子

有一堆水果，其中有香蕉，蘋果，杏這三類，現(xiàn)在要對(duì)它們分類，可以選擇的特征有兩個(gè)：形狀和大小，其中形狀的取值有個(gè)：圓形和不規(guī)則形，大小的取值有：相對(duì)大和相對(duì)小。現(xiàn)在要對(duì)其做分類，我們可以這樣做：

首先根據(jù)特征：形狀，如果不是圓形，那么一定是香蕉，這個(gè)就是葉子節(jié)點(diǎn);

如果是圓形，

再進(jìn)一步根據(jù)大小這個(gè)特征判斷，如果是相對(duì)大的，則是蘋果，如果否，則是杏子，至此我們又得到兩個(gè)葉子節(jié)點(diǎn)，并且到此分類位置，都得到了正確劃分三種水果的方法。

大家可以體會(huì)剛才這個(gè)過程，這就是一個(gè)決策分類，構(gòu)建樹的一個(gè)過程，說成是樹，顯得有點(diǎn)高大上，再仔細(xì)想想就是一些列 if 和 else 的嵌套，說是樹只不過是邏輯上的一種神似罷了。

剛才舉的這個(gè)例子，有兩個(gè)特征：形狀和大小，并且選擇了第一個(gè)特征：形狀作為第一個(gè)分裂點(diǎn)，大小作為第二個(gè)分裂點(diǎn)，那么不能選擇第二個(gè)特征作為第一分裂點(diǎn)嗎? 這樣選擇有沒有公式依據(jù)呢?

2 分裂點(diǎn)選擇依據(jù)

在上個(gè)例子中，有三類水果，現(xiàn)在假設(shè)杏都被我們家的寶寶吃完了，現(xiàn)在手里只有香蕉和蘋果這兩類水果了，并且這個(gè)時(shí)候要對(duì)它們做分類，此時(shí)機(jī)靈的你，一定會(huì)根據(jù)特征：形狀對(duì)它們分類了，因?yàn)檫@樣一下就會(huì)把它們分開了，此時(shí)我們說這類集合的純度更高，與之前的那三類水果在形狀這個(gè)特征上。

純度這個(gè)概念是很好的理解的，種類越少純度越高，自然兩類純度更高。 此時(shí)有人提出了一個(gè)和它相反的但是不那么容易理解的概念：熵。它們是敵對(duì)雙方：熵越大，純度越低;熵越小，純度越高。

這是一種概念，那么如何用公式量化熵呢：

其中 i 等于蘋果，香蕉，杏，P(i)是集合中取得某一個(gè)水果的概率。

試想一下，如果我們想更好地對(duì)某個(gè)集合完成分類，會(huì)怎么做呢?我們一定會(huì)優(yōu)先選擇一個(gè)特征，使得以這個(gè)特征做分類時(shí)，它們能最大程度的降低熵，提高分類的純度，極限的情況是集合中100個(gè)元素(集合中只有兩類水果)，根據(jù)某個(gè)最優(yōu)特征，直接將分為兩類，一類都是蘋果，一類都是杏，這樣熵直接等于0。

這個(gè)特點(diǎn)就是所謂的信息增益，熵降低的越多，信息增益的就越多。很多時(shí)候都不會(huì)發(fā)生上述說的這個(gè)極限情況，就像文章一開始舉的例子，根據(jù)形狀劃分后，熵變小了，但是未等于0，比如剛開始三類水果的熵等于0.69，現(xiàn)在根據(jù)形狀分裂后，熵等于了0.4，所以信息增益為0.69 – 0.4 = 0.29 。如果根據(jù)大小劃分，信息增益為0.1，那么我們回考慮第一個(gè)分裂特征：形狀。

這種方法有問題嗎?

3 信息增益越大，分類效果越好?

這是只根據(jù)信息增益選擇分裂特征點(diǎn)的bug，請(qǐng)看下面舉例。

如果某個(gè)特征是水果的唯一標(biāo)示屬性：編號(hào)，那么此時(shí)如果選擇這個(gè)特征，共得到100個(gè)葉子節(jié)點(diǎn)(假設(shè)這堆水果一共有100個(gè))，每個(gè)葉子節(jié)點(diǎn)只含有1個(gè)樣本，并且此時(shí)的信息增益最大為 0.69 – 0 = 0.69 。

但是，這是好的分類嗎? 每一個(gè)樣本作為單獨(dú)的葉子節(jié)點(diǎn)，當(dāng)來了101號(hào)水果，都不知道劃分到哪一個(gè)葉子節(jié)點(diǎn)，也就不知道它屬于哪一類了!

因此，這個(gè)問題感覺需要除以某個(gè)變量，來消除這種情況的存在。

它就是信息增益率，它不光考慮選擇了某個(gè)分裂點(diǎn)后能獲得的信息增益，同時(shí)還要除以分裂出來的這些節(jié)點(diǎn)的熵值，什么意思呢? 剛才不是分裂出來100個(gè)節(jié)點(diǎn)嗎，那么這些節(jié)點(diǎn)自身熵一共等于多少呢：

再除以上面這個(gè)數(shù)后，往往信息增益率就不會(huì)那么大了。這就是傳說中的從ID3 到 C4.5 的改進(jìn)。

4 與熵的概念類似的基尼系數(shù)

只需要知道基尼系數(shù)和熵差不多的概念就行了，只不過量化的公式不同而已，這就說明理解了，至于公式長什么樣子，用的時(shí)候去查就行了。

讓我們看一下遠(yuǎn)邊的大海，和海邊優(yōu)美的風(fēng)景，放松一下吧!

5 展望

以上介紹了決策樹的一些概念和分裂點(diǎn)選取的基本方法。