Hello Kitty 的種族問(wèn)題

Hello Kitty蝶怔，一只以無(wú)嘴造型40年來(lái)風(fēng)靡全球的萌萌貓奶浦，在其40歲生日時(shí)，居然被其形象擁有者宣稱(chēng)：Hello Kitty 不是貓踢星！

2014年8月澳叉，研究 Hello Kitty 多年的人類(lèi)學(xué)家 Christine R. Yano 在寫(xiě)展品解說(shuō)時(shí)，卻被 Hello Kitty 持有商三麗鷗糾正：Hello Kitty 是一個(gè)卡通人物，她是一個(gè)小女孩成洗，是一位朋友五督，但她“絕不”是一只貓。

enter image description here

粉了快半個(gè)世紀(jì)的世界萌貓瓶殃，你說(shuō)是人就是人啦充包？！就算是形象持有者遥椿，也沒(méi)權(quán)利下這個(gè)定論啊!

誰(shuí)有權(quán)認(rèn)定 Hello Kitty 是人是貓呢基矮？我們把裁決權(quán)交給世界上最公正無(wú)私的裁判—— 計(jì)算機(jī)。讓機(jī)器來(lái)決定冠场。

機(jī)器如何具備區(qū)分一個(gè)形象屬于哪個(gè)物種的知識(shí)呢愈捅？讓它學(xué)習(xí)呀！機(jī)器是可以學(xué)習(xí)的慈鸠。我們用計(jì)算機(jī)編個(gè)程序蓝谨，再輸入一堆數(shù)據(jù)，等著這個(gè)程序運(yùn)行一個(gè)算法來(lái)處理這些數(shù)據(jù)青团。最后譬巫，我們需要的結(jié)論就顯示在屏幕上啦。就是這么簡(jiǎn)單督笆！

那么來(lái)看看我們需要的數(shù)據(jù)和算法吧芦昔。

訓(xùn)練數(shù)據(jù)

如下圖所示，左邊一堆是一群小女孩娃肿，右邊一堆是一群貓咕缎。

enter image description here

特征選取

我們提取七個(gè)特征，用來(lái)判斷一個(gè)形象料扰，是人是貓凭豪。這七個(gè)特征包括：有否蝴蝶結(jié)；是否穿衣服晒杈；是否高過(guò)5個(gè)蘋(píng)果嫂伞；是否有胡子；是否圓臉拯钻；是否有貓耳朵帖努；是否兩腳走路。

用一個(gè)表格來(lái)表現(xiàn)這七個(gè)特征則粪般，如下圖所示（第一列為 Label拼余，第2至8列為7個(gè)特征，每個(gè)特征只有兩個(gè)取值亩歹，Yes 或者 No）：

enter image description here

<center style="font-size: 16px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; box-sizing: border-box; caret-color: rgb(63, 63, 63); color: rgb(63, 63, 63); font-family: "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei"; outline: 0px !important;">Table-1</center>

用 ID3 算法構(gòu)造分類(lèi)樹(shù)

本例中匙监，我們選用最簡(jiǎn)單的 ID3 算法寡润，代入數(shù)據(jù)進(jìn)行計(jì)算。

(1)根據(jù)信息熵的概念舅柜，我們先來(lái)計(jì)算 Entropy(S)。因?yàn)榭偣仓挥袃蓚€(gè)類(lèi)別：人和貓躲惰，因此 n==2致份。

Entropy(S)=?∑ni=1pilog(pi)=?pGirllog(pGirl)?pCatlog(pCat)=?9/17?log(9/17)?8/17?log(8/17)=0.69

(2)然后我們?cè)俜謩e計(jì)算各個(gè)特征的：

Entropy(S|T)=∑value(T)|Sv||S|Entropy(Sv)

因?yàn)闊o(wú)論哪個(gè)特征，都只有兩個(gè)特征值：Yes 或者 No础拨，因此 value(T) 總共只有兩個(gè)取值氮块。

下面以“Has a bow”為例來(lái)示意其計(jì)算過(guò)程。

Entropy(S|HasABow)=pYes(?p(Girl|Yes)log(p(Girl|Yes))–p(Cat|Yes)log(p(Cat|Yes)))+pNo(?p(Girl|No)log(p(Girl|No))–p(Cat|No)log(p(Cat|No)))=8/17?(?4/8?log(4/8)–4/8?log(4/8))+9/17?(?5/9?log(5/9)–4/9?log(4/9))=0.69

InformationGain(T)=Entropy(S)?∑value(T)|Sv||S|Entropy(Sv)

依次計(jì)算其他幾項(xiàng)诡宗，得出如下結(jié)果：

(3)進(jìn)一步計(jì)算滔蝉，得出 InfoGain(Has cat ears) 最大，因此“Has cat ears”是第一個(gè)分裂節(jié)點(diǎn)塔沃。

而從這一特征對(duì)應(yīng)的類(lèi)別也可以看出蝠引，所有特征值為 No 的都一定是 Girl；特征值為 Yes蛀柴，可能是 Girl 也可能是 Cat螃概，那么第一次分裂，我們得出如下結(jié)果：

enter image description here

現(xiàn)在“Has cat ears”已經(jīng)成為了分裂點(diǎn)鸽疾，則下一步將其排除吊洼，用剩下的6個(gè) Feature 繼續(xù)分裂成樹(shù)：

enter image description here

<center style="font-size: 16px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; box-sizing: border-box; caret-color: rgb(63, 63, 63); color: rgb(63, 63, 63); font-family: "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei"; outline: 0px !important;">Table-2</center>

Table-2 為第二次分裂所使用的訓(xùn)練數(shù)據(jù)，相對(duì)于 Table-1制肮，“Has cat ears”列冒窍，和前7行對(duì)應(yīng)“Has cat ears”為 No 的數(shù)據(jù)都已經(jīng)被移除，剩下部分用于第二次分裂豺鼻。

如此反復(fù)迭代综液，最后使得7個(gè)特征都成為分裂點(diǎn)。

需要注意的是儒飒，如果某個(gè)特征被選為當(dāng)前輪的分裂點(diǎn)意乓，但是它在現(xiàn)存數(shù)據(jù)中只有一個(gè)值，另一個(gè)值對(duì)應(yīng)的記錄為空约素，則這個(gè)時(shí)候針對(duì)不存在的特征值届良，將它標(biāo)記為該特征在所有訓(xùn)練數(shù)據(jù)中所占比例最大的類(lèi)型。

對(duì)本例而言圣猎，當(dāng)我們將“Wear Clothes”作為分裂點(diǎn)時(shí)士葫，會(huì)發(fā)現(xiàn)該特征只剩下了一個(gè)選項(xiàng)——Yes（如下 Table-3 所示）。此時(shí)怎么給“Wear Clothes”為 No 的分支做標(biāo)記呢送悔？

enter image description here

<center style="font-size: 16px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; box-sizing: border-box; caret-color: rgb(63, 63, 63); color: rgb(63, 63, 63); font-family: "PingFang SC", "Hiragino Sans GB", "Microsoft YaHei"; outline: 0px !important;">Table-3</center>

這時(shí)就要看在 Table-1 中慢显，“Wear Clothes”為 No 的記錄中是 Girl 多還是 Cat 多爪模。一目了然，在 Table-1 中這兩種記錄數(shù)量為 0:6，因此“Wear Clothes”為 No 的分支直接標(biāo)志成 Cat。

根據(jù)上述方法制恍，最終我們構(gòu)建出了如下決策樹(shù)：

enter image description here

決策樹(shù)構(gòu)建過(guò)程记焊，如下代碼所示：

后剪枝優(yōu)化決策樹(shù)

決策樹(shù)剪枝

剪枝是優(yōu)化決策樹(shù)的常用手段。剪枝方法大致可以分為兩類(lèi)：

1. 先剪枝（局部剪枝）：在構(gòu)造過(guò)程中，當(dāng)某個(gè)節(jié)點(diǎn)滿(mǎn)足剪枝條件，則直接停止此分支的構(gòu)造；
2. 后剪枝（全局剪枝）：先構(gòu)造完成完整的決策樹(shù)除嘹，再通過(guò)某些條件遍歷樹(shù)進(jìn)行剪枝。

后剪枝優(yōu)化 Hello Kitty 樹(shù)

現(xiàn)在岸蜗，決策樹(shù)已經(jīng)構(gòu)造完成尉咕，所以我們采用后剪枝法，對(duì)上面決策樹(shù)進(jìn)行修剪璃岳。

如圖中顯示年缎，最后兩個(gè)分裂點(diǎn)“Has round face”和“Has a bow”存在并無(wú)意義——想想也是啊，無(wú)論人貓铃慷，都有可能是圓臉晦款，也都可以戴蝴蝶結(jié)啊。

所以我們遍歷所有節(jié)點(diǎn)枚冗，將沒(méi)有區(qū)分作用的節(jié)點(diǎn)刪除缓溅。完成后，我們的決策樹(shù)變成了下面這樣：

enter image description here

用決策樹(shù)對(duì) Hello Kitty 進(jìn)行分類(lèi)

我們將 Hello Kitty 的特征帶入 Cat-Girl 決策樹(shù)赁温，發(fā)現(xiàn) Hello Kitty：Has cat ears: Yes -> Walk on 2 feet: Yes -> Wear Clothes: Yes -> Has whiskers: Yes -> Less than 5 apples: Yes -> Cat坛怪。

Bingo! Hello Kitty 是只貓！這是我們的 ID3 決策樹(shù)告訴我們的股囊！

代碼實(shí)現(xiàn)

下面的代碼就是用 numpy 和 sklearn 來(lái)實(shí)現(xiàn)例子中的訓(xùn)練分類(lèi)樹(shù)來(lái)判斷 Hello Kitty 種族所對(duì)應(yīng)的程序袜匿。

最后輸出為：

[1 1 0 0]

0.75

[0]