上一篇: 數(shù)據(jù)挖掘:理論與算法筆記2-數(shù)據(jù)預(yù)處理
下一篇: 數(shù)據(jù)挖掘:理論與算法筆記4-神經(jīng)網(wǎng)絡(luò)

3 從貝葉斯到?jīng)Q策樹: 意料之外，情理之中

3.1 貝葉斯奇幻之旅

分類

魚的種類就是一種分類問題，比如我以前經(jīng)常抓到的flathead是catfish家族的，他們家的魚都是有胡子的，在catfish家族中根據(jù)顏色，體型，條紋和魚鰭等特征還可以進(jìn)一步細(xì)分，flathead就是頭部特別扁平，身體顏色帶點(diǎn)棕黃，手感滑膩。

分類是所有的動(dòng)物和人類能夠生存下來的一種本能，原始人看見兔子和鹿就會(huì)識(shí)別出來這是可以捕獵的對(duì)象，而看到獅子或者老虎就知道要趕緊逃命了。分類屬于監(jiān)督學(xué)習(xí)，必須對(duì)樣本數(shù)據(jù)打標(biāo)簽進(jìn)行訓(xùn)練，學(xué)習(xí)過程中有input和output，input是特征向量，output可以是boolean value(binary classification), 也可以是integer(multiclass)，手寫數(shù)字圖像的識(shí)別就是一個(gè)典型的多分類問題，可參考前文手工打造神經(jīng)網(wǎng)絡(luò): 透視分析。以后我們?cè)儆懻摲潜O(jiān)督學(xué)習(xí)，即對(duì)沒有標(biāo)簽的樣本數(shù)據(jù)進(jìn)行處理，如聚類。

貝葉斯定理

$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

P(A): A發(fā)生的先驗(yàn)概率
P(B): B發(fā)生的先驗(yàn)概率
P(B|A): 當(dāng)A發(fā)生時(shí)B發(fā)生的概率
P(A|B): 當(dāng)B發(fā)生時(shí)A發(fā)生的概率

Case 1

患癌癥 $\omega_1$ 的概率是0.8%, 健康 $\omega_2$ 的概率是99.2%，體檢報(bào)告的結(jié)果有陽性和陰性。
患癌癥后體檢結(jié)果為陽性的概率為98%，為陰性的概率為2%
健康的體檢結(jié)果為陽性的概率為3%，為陰性的概率為97%

那么如果一個(gè)人體的癌癥體檢結(jié)果為陽性，他實(shí)際患上癌癥的概率有多少呢? 下面可以套用貝葉斯公式來計(jì)算一下:

$P(\omega_1|+) \propto P(+|\omega_1)P(\omega_1)=0.98*0.08=0.0078$
$P(\omega_2|+) \propto P(+|\omega_2)P(\omega_2)=0.03*0.992=0.0298$
$P(\omega_1|+) = \frac{0.0078}{0.0078+0.0298}=0.21$

所以檢查結(jié)果為陽性時(shí)患癌癥概率正比于0.0078，而健康概率正比于0.0298，健康的概率遠(yuǎn)高于患癌癥概率。當(dāng)檢查結(jié)果為陽性時(shí)實(shí)際患癌癥的概率是21%，大部分情況都是假陽性結(jié)果。雖然患癌癥后檢驗(yàn)結(jié)果為陽性的概率高達(dá)98%但也不必過于恐慌，因?yàn)榻】档南闰?yàn)概率比患癌癥的先驗(yàn)概率高的多。

Case 2

頭疼的概率是1/10, 患流感的概率是1/40，患流感后頭疼的概率是1/2, 那么如果出現(xiàn)頭疼患流感的概率是多少呢?

套用貝葉斯公式計(jì)算:

$P(F|H)=\frac{P(H|F)P(F)}{P(H)}=\frac{1/2*1/40}{1/10}=\frac{1}{8}$

下圖紅色與藍(lán)色重疊部分的面積占紅色的二分之一，但只占藍(lán)色部分的八分之一。

3.2 樸素是一種美德

接下來看看如何用貝葉斯真正的去做分類。
貝葉斯分類器強(qiáng)調(diào)的是后驗(yàn)概率，當(dāng)觀察到對(duì)象的一組特征 $[\alpha_1, \alpha_1,...\alpha_n]$ 之后，要判斷對(duì)象屬于哪個(gè)分類， $\omega_{MAP}$ 是分類的集合, 集合中哪一個(gè)分類的后驗(yàn)概率大則對(duì)象歸屬于哪個(gè)分類。

假設(shè)所有的特征都是條件獨(dú)立的，我們可以把聯(lián)合概率轉(zhuǎn)化為概率的乘積，其實(shí)Naive Bayes這個(gè)名稱中Naive指的就是這個(gè)條件獨(dú)立的假設(shè)前提。

MAP：Maximum A Posterior

獨(dú)立事件

如果事件A的發(fā)生對(duì)事件B的發(fā)生不產(chǎn)生任何影響，反之亦然，則這兩個(gè)事件是獨(dú)立的。比如扔硬幣的結(jié)果和周幾扔硬幣是獨(dú)立的事件，但不是所有的場(chǎng)景都這么明顯，人的性別和是否左撇子看似獨(dú)立事件，實(shí)際上不區(qū)分性別的話只有10%的人是左利手，但12%的男性是左利手。所以這兩個(gè)事件不是獨(dú)立的，性別為男會(huì)增加左撇子的概率。

兩個(gè)事件A和B, 如果 $P(A|B)=P(A)$ 且 $P(B|A)=P(B)$ 則事件A和B是獨(dú)立的，此時(shí) $P(A \cap B) = P(A)P(B)$

$P(A \cap B|C)=P(A|C)P(B|C)$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=P(A%7CB)%3D%20%5Cfrac%7BP(A%20%5Ccap%20B)%7D%7BP(B)%7D" alt="P(A|B)= \frac{P(A \cap B)}{P(B)}" mathimg="1">
所以 $P(A|B,C)= \frac{P(A \cap B|C)}{P(B|C)} = \frac{P(A|C)P(B|C)}{P(B|C)}=P(A|C)$

條件獨(dú)立

對(duì)于條件獨(dú)立來說，多了一個(gè)條件事件G, 事件A發(fā)生的概率僅依賴于G發(fā)生的概率，與B無關(guān)。

下面結(jié)合一個(gè)例子來說明什么是條件獨(dú)立，假設(shè)我們有藍(lán)色和紅色兩個(gè)箱子，藍(lán)色箱子里有一個(gè)黑球和一個(gè)白球，紅色箱子里有兩個(gè)黑球，我要隨機(jī)選擇一個(gè)箱子隨機(jī)挑出一個(gè)球，然后再從另一個(gè)箱子里隨機(jī)挑出一個(gè)球，有以下幾個(gè)事件:
A - 從第一個(gè)隨機(jī)選擇的箱子里隨機(jī)挑出的球是黑球
B - 從第二個(gè)箱子里挑出的球是黑球
C - 第一個(gè)隨機(jī)選擇的箱子是藍(lán)色的

A事件和B事件的概率同為0.75

如果A成立，則C發(fā)生的概率是三分之一，因?yàn)楫?dāng)A發(fā)生的時(shí)候其實(shí)已經(jīng)改變了C的概率
$P(C|A)= \frac{P(A|C)P(C)}{P(A)}= \frac{0.5*0.5}{0.75}= \frac{1}{3}$

看似B的發(fā)生概率依賴于A的發(fā)生概率
$P(B|A)= \frac{1}{3}*0.5 + \frac{2}{3}*1.0= \frac{5}{6} \neq P(B)$

其實(shí)不是A影響B(tài), 而是B的發(fā)生概率依賴于條件概率C
$P(B|A, C)=P(B|C)=0.5$

看到這里也許很多人已經(jīng)會(huì)聯(lián)想起那個(gè)反直覺的著名案例 - Monty Hall Problem

Monty Hall 是美國一個(gè)電視游戲節(jié)目的主持人，你是參賽者。你面對(duì)三扇門(A,B,C)，其中一扇門的后面是汽車，另外兩扇門后面是山羊，你的目標(biāo)是贏得汽車。你隨機(jī)選擇一扇門(假設(shè)你選擇了A)，這時(shí)主持人打開了C，C后面是一只山羊，并給你一次重新選擇的機(jī)會(huì)。現(xiàn)在汽車只可能在A和B中，你該不該換門，汽車在A和B后面的概率各是多少？

正確的做法是換門以增加中獎(jiǎng)概率，可是很多人理解不了為什么，下面就用貝葉斯公式來驗(yàn)證下:
通過貝葉斯公式推導(dǎo)主持人選擇打開C門時(shí)汽車在A門后的概率
$P(CarA|C) = \frac{P(C|CarA)*P(CarA)}{P(C)}$

現(xiàn)在需要找出當(dāng)我們挑選A門后主持人選擇C門的概率
$P(C) = P(C|CarA)*P(CarA)+P(C|CarB)*P(CarB)+P(C|CarC)*P(CarC)$

下面來拆解分析一下
P(C|CarA): 如果汽車在A門后面，主持人只能在B和C門中選擇，所以選擇C門的概率是0.5
P(C|CarB): 如果汽車在B門后面，那么主持人只能選擇打開C門，這個(gè)唯一的選擇概率是1
P(C|CarC): 最后，如果汽車在C門后面，主持人不可能直接打開C門給出答案，這個(gè)概率是0

代入上面的公式得出
$P(C) = 0.5*P(CarA)+P(CarB)$

因?yàn)镃arA, CarB, CarC的概率都是三分之一，所以P(C)等于0.5

所以 $P(CarA|C) = \frac{P(C|CarA)*P(CarA)}{P(C)}=\frac{0.5*\frac{1}{3}}{0.5}=\frac{1}{3}$

此時(shí)再看主持人打開C門時(shí)汽車在B門后的概率
$P(CarB|C) = \frac{P(C|CarB)*P(CarB)}{P(C)}=\frac{1*\frac{1}{3}}{0.5}=\frac{2}{3}$

所以當(dāng)你選擇了A門，而主持人打開C門里面有一只山羊的時(shí)候，應(yīng)該毫不猶豫的選擇換到B門，這樣中獎(jiǎng)的概率會(huì)高一倍呢。

分類示例

下面結(jié)合實(shí)例看看如何用樸素貝葉斯來做分類

下表中的input是各種天氣情況，output是是否打網(wǎng)球的標(biāo)識(shí)

有了這些訓(xùn)練集之后來判斷一個(gè)新的天氣組合場(chǎng)景下是否會(huì)打網(wǎng)球的概率
Given：
<Outlook=sunny, Temperature=cool, Humidity=high, Wind=Strong>
Predict:
PlayTennis(Yes or no)

Bayes Solution:
P(PlayTennis=yes)=9/14
P(PlayTennis=no)=5/14
P(Wind=strong|PlayTennis=yes)=3/9
P(Wind=strong|PlayTennis=no)=3/5
...

在這種天氣情況下打網(wǎng)球的概率是0.0053/(0.0053+0.0206)=0.205

拉普拉斯平滑

樸素貝葉斯分類器也可以應(yīng)用在推薦系統(tǒng)如文本分類上，公式為
$P(V_k|\omega=\omega_i)=\frac{n_k+1}{n+| Vocabulary |}$
這個(gè)公式用到了拉普拉斯平滑(Lplace smoothing)，分子加了一個(gè)1，分母加了一個(gè)種類的個(gè)數(shù)。因?yàn)闃闼刎惾~斯分類是概率的乘積，如果某個(gè)特征項(xiàng)沒有出現(xiàn)過，比如有個(gè)新的單詞不在訓(xùn)練集里，這個(gè)特征項(xiàng)的概率為0會(huì)導(dǎo)致整體的乘積也為0，為了解決這個(gè)零概率的問題，法國數(shù)學(xué)家拉普拉斯最早提出用加1的方法估計(jì)沒有出現(xiàn)過的現(xiàn)象的概率。

3.3 數(shù)據(jù), 規(guī)則與樹

決策樹是一個(gè)自上而下的樹狀結(jié)構(gòu)，模仿人類思考模式一層層做出決策。

比如銷售要給潛在客戶打電話，記錄下來客戶的一系列特征已經(jīng)打電話營(yíng)銷是否成功的標(biāo)識(shí)。特征屬性包括居住地區(qū)，住房類型，收入高低，以前是否曾經(jīng)購買過。

上表只是一個(gè)很小的數(shù)據(jù)集，如果記錄有上百萬條一定看得人蒙圈，但是我們可以通過決策樹模型清晰的揭示其中的規(guī)律。下面的決策樹首先按照區(qū)域劃分，第一層告訴我們住在農(nóng)村的人一定會(huì)買，住在城市和郊區(qū)的人不太確定購買可能性，所以往下再次劃分，層層遞推，最后得到非常理想的純結(jié)果的葉節(jié)點(diǎn)，可以提取出明確的規(guī)則，但實(shí)際上通常到最后也不可能劃分的這么純粹。

這棵樹能提取出來的規(guī)則如:
(District=Rural) -> (Outcome = Responded)
(District=Urban) and (Previous Customer=Yes) -> (Outcome=Nothing)

對(duì)于同樣的數(shù)據(jù)集來說決策樹并非唯一，有很多組合的可能，下面這棵樹的層級(jí)更少，但是也能很好的區(qū)分出用戶是否會(huì)購買。

如果特征屬性很多，那么決策樹的組合數(shù)量也會(huì)非常龐大，選擇的基本原則是遵循奧卡姆剃刀原理，用盡可能簡(jiǎn)單的模型來描述規(guī)律。

3.4 植樹造林學(xué)問大

所有的決策樹算法中，Iterative Dischotomizer 3算的上是鼻祖了，雖然特殊屬性很多，但是其中有些區(qū)分效果特別好的關(guān)鍵因子，基本思路是把這些強(qiáng)大的屬性放在前面。

熵(Entropy)

熵是用來衡量系統(tǒng)的不確定性，或者說一個(gè)變量取值的不確定性。
假如變量可以取C種值，每個(gè)取值有一個(gè)概率p, 從而我們有一個(gè)預(yù)期結(jié)果的熵函數(shù):
$Entropy(S)=-\sum^C_{i=1} p_ilog(p_i)$

前面電話營(yíng)銷案例的樣本空間S=[9/14(responses), 5/14(no responses)], 這個(gè)結(jié)果有多不確定呢，可以用上面的公式來算一下:
$Entropy(S)=-\frac{9}{14}log_2\frac{9}{14} - \frac{5}{14}log_2\frac{5}{14}=0.940$

這里熵值最大為1，表示不確定性最高，比如扔硬幣，上面的0.940也是相當(dāng)?shù)牟淮_定了。

當(dāng)我們放一個(gè)屬性進(jìn)來的時(shí)候，原始數(shù)據(jù)集就被切分了，可以針對(duì)每個(gè)子集再取計(jì)算它的熵。
假設(shè) $S_v$ 是屬A取值為v時(shí)集合S的子集，加入屬性后的信息增益公式為:
$Gain(S,A)=Entropy(S)-\sum_{v \in A}\frac{|S_v|}{|S|}Entropy(S_v)$
這里計(jì)算的當(dāng)知道某個(gè)屬性A的取值后能把原始的不確定性降低多少，取值當(dāng)然是越大越好。

現(xiàn)在看看用District來劃分?jǐn)?shù)據(jù)集效果如何：
$Gain(S, District)=Entropy(S)-\frac{5}{14}Entropy(S_{District=Suburban})$
$-\frac{5}{14} Entropy(S_{District=Urban})- \frac{4}{14}Entropy(S_{District=Rural})$
$=0.940- \frac{5}{14} * 0.971- \frac{5}{14} * 0.971- \frac{4}{14} * 0=0.247$

同理可以計(jì)算出Gain(S, Income)=0.152
顯然District比Income的區(qū)分效果更好，我們應(yīng)該先選擇District.

如果屬性太多，必須在準(zhǔn)確率和過擬合之間找到一個(gè)平衡，需要控制好樹的規(guī)模，否則容易訓(xùn)練效果很好但是因?yàn)槭チ朔夯芰?dǎo)致測(cè)試效果反而變差。

上一篇: 數(shù)據(jù)挖掘:理論與算法筆記2-數(shù)據(jù)預(yù)處理
下一篇: 數(shù)據(jù)挖掘:理論與算法筆記4-神經(jīng)網(wǎng)絡(luò)

references:
Supervised machine learning classification
Bayes’ Rule and the Monty Hall Problem
Iterative Dichotomiser 3 (ID3) Algorithm From Scratch

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)挖掘:理論與算法筆記3-從貝葉斯到?jīng)Q策樹

數(shù)據(jù)挖掘:理論與算法筆記3-從貝葉斯到?jīng)Q策樹

3 從貝葉斯到?jīng)Q策樹: 意料之外，情理之中

3.1 貝葉斯奇幻之旅

分類