在此推出一個(gè)算法系列的科普文章。我們大家在平時(shí)埋頭工程類(lèi)工作之余，也可以抽身對(duì)一些常見(jiàn)算法進(jìn)行了解，這不僅可以幫助我們拓寬思路业簿，從另一個(gè)維度加深對(duì)計(jì)算機(jī)技術(shù)領(lǐng)域的理解，做到觸類(lèi)旁通聂喇，同時(shí)也可以讓我們搞清楚一些既熟悉又陌生的領(lǐng)域——比如數(shù)據(jù)挖掘辖源、大數(shù)據(jù)蔚携、機(jī)器學(xué)習(xí)——的基本原理希太，揭開(kāi)它們的神秘面紗，了解到其實(shí)很多看似高深的領(lǐng)域酝蜒，其實(shí)背后依據(jù)的基礎(chǔ)和原理也并不復(fù)雜誊辉。而且，掌握各類(lèi)算法的特點(diǎn)亡脑、優(yōu)劣和適用場(chǎng)景堕澄，是真正從事數(shù)據(jù)挖掘工作的重中之重。只有熟悉算法霉咨，才可能對(duì)紛繁復(fù)雜的現(xiàn)實(shí)問(wèn)題合理建模蛙紫，達(dá)到最佳預(yù)期效果。
本系列文章的目的是力求用最干練而生動(dòng)的講述方式途戒，為大家講解由國(guó)際權(quán)威的學(xué)術(shù)組織the IEEE International Conference on Data Mining (ICDM) 于2006年12月評(píng)選出的數(shù)據(jù)挖掘領(lǐng)域的十大經(jīng)典算法坑傅。它們包括：
1. C4.5（c4.5決策樹(shù)算法）
2. k-Means（k均值算法）
3. SVM（支持向量機(jī)）
4. Apriori（先驗(yàn)算法）
5. EM（期望最大算法）
6. PageRank（google的網(wǎng)頁(yè)排序算法）
7. AdaBoost（Adaptive Boosting自適應(yīng)增強(qiáng)算法）
8. kNN（k近鄰算法）
9. Naive Bayes（樸素貝葉斯）
10. CART（分類(lèi)與回歸樹(shù)）
一點(diǎn)鋪墊
本文作為本系列的第一篇，在介紹具體算法之前喷斋，先簡(jiǎn)單為大家鋪墊幾個(gè)數(shù)據(jù)挖掘領(lǐng)域的常見(jiàn)概念：
在數(shù)據(jù)挖掘領(lǐng)域唁毒，按照算法本身的行為模式和使用目的，主要可以分為分類(lèi)(classification)星爪，聚類(lèi)(clustering)和回歸(regression)幾種浆西，其中：
分類(lèi) 通常是在已經(jīng)給定了幾種類(lèi)別和一部分屬于這些類(lèi)別的數(shù)據(jù)的前提下，尋找分類(lèi)規(guī)律顽腾，從而對(duì)沒(méi)有標(biāo)注類(lèi)別的數(shù)據(jù)進(jìn)行類(lèi)別劃分的行為近零。而這些事先給出的已經(jīng)分好類(lèi)的示例數(shù)據(jù)通常被稱(chēng)之為訓(xùn)練集，而這種通過(guò)已經(jīng)標(biāo)注了輸入與輸出關(guān)系訓(xùn)練集尋找規(guī)律的學(xué)習(xí)行為抄肖，在機(jī)器學(xué)習(xí)領(lǐng)域稱(chēng)之為監(jiān)督式學(xué)習(xí)（Supervised learning）秒赤。
聚類(lèi) 與分類(lèi)十分類(lèi)似，都是以找到數(shù)據(jù)和類(lèi)別之間的關(guān)系作為最終目的憎瘸。不同的是入篮，聚類(lèi)一開(kāi)始并沒(méi)有給定的類(lèi)別和訓(xùn)練集，而直接由算法找出其中潛在規(guī)律幌甘。聚類(lèi)的目的在于把相似的東西聚在一起潮售，而有時(shí)我們甚至并不關(guān)心這一類(lèi)是什么痊项。這種沒(méi)有訓(xùn)練集作為參照而直接對(duì)輸入數(shù)據(jù)進(jìn)行建模的學(xué)習(xí)方式被稱(chēng)為無(wú)監(jiān)督的學(xué)習(xí)（Unsupervised learning）。
回歸 則是通過(guò)有限的輸入數(shù)據(jù)酥诽，找出一個(gè)能描述數(shù)據(jù)潛在規(guī)律的函數(shù)鞍泉，從而對(duì)未來(lái)的走勢(shì)進(jìn)行預(yù)測(cè)。
打幾個(gè)不恰當(dāng)?shù)谋确?/strong>：
- 分類(lèi)就好似垃圾歸類(lèi)肮帐，一共就三種垃圾桶咖驮，并告訴你哪幾種垃圾扔進(jìn)哪個(gè)桶，通過(guò)分析得知將來(lái)要扔的所有垃圾該往哪兒扔训枢；
- 聚類(lèi)就像生物劃分界門(mén)綱目科屬種托修，一開(kāi)始根本不知道全世界的生物有多少種類(lèi)，通過(guò)不斷摸索找出這些類(lèi)別恒界；
- 而回歸就像是在探索一個(gè)能描述一切的萬(wàn)物理論睦刃，不僅要能完美解釋當(dāng)前觀察到的所有現(xiàn)象，還能對(duì)未來(lái)做出精確預(yù)測(cè)十酣。
另外涩拙，還有一個(gè)經(jīng)常有人問(wèn)起的問(wèn)題，就是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)這兩個(gè)概念的區(qū)別耸采，這里一句話闡明我自己的認(rèn)識(shí)：機(jī)器學(xué)習(xí)是基礎(chǔ)兴泥，數(shù)據(jù)挖掘是應(yīng)用。機(jī)器學(xué)習(xí)研制出各種各樣的算法虾宇，數(shù)據(jù)挖掘根據(jù)應(yīng)用場(chǎng)景把這些算法合理運(yùn)用起來(lái)搓彻，目的是達(dá)到最好的挖掘效果。
當(dāng)然文留，以上的簡(jiǎn)單總結(jié)一定不夠準(zhǔn)確和嚴(yán)謹(jǐn)好唯，更多的是為了方便大家理解打的比方。如果大家有更精當(dāng)?shù)睦斫庠锍幔瑲g迎補(bǔ)充和交流骑篙。
進(jìn)入正題
好了，鋪墊了這么多森书，現(xiàn)在終于進(jìn)入正題靶端！
作為本系列入門(mén)的第一篇，先為大家介紹一個(gè)容易理解又很有趣的算法——樸素貝葉斯凛膏。
先站好隊(duì)杨名，樸素貝葉斯是一個(gè)典型的有監(jiān)督的分類(lèi)算法。
貝葉斯定理
光從名字也可以想到猖毫，要想了解樸素貝葉斯台谍，先要從貝葉斯定理說(shuō)起。
貝葉斯定理是我們高中時(shí)代學(xué)過(guò)的一條概率學(xué)基礎(chǔ)定理吁断，它描述了條件概率的計(jì)算方式趁蕊。不要怕已經(jīng)把這些知識(shí)還給了體育老師坞生，相信你一看公式就能想起來(lái)。
P(A|B)表示事件B已經(jīng)發(fā)生的前提下掷伙，事件A發(fā)生的概率是己，叫做事件B發(fā)生下事件A的條件概率。其基本求解公式為：
其中任柜，P(AB)表示A和B同時(shí)發(fā)生的概率卒废，P(B)標(biāo)識(shí)B事件本身的概率。
貝葉斯定理之所以有用宙地，是因?yàn)槲覀冊(cè)谏钪薪?jīng)常遇到這種情況：我們可以很容易直接得出P(A|B)摔认，P(B|A)則很難直接得出，但我們更關(guān)心P(B|A)绸栅。
舉個(gè)栗子级野，通過(guò)歷次美國(guó)大選页屠，我們可以得知粹胯，投票給共和黨的選票有多大概率來(lái)自加州，但我們更關(guān)心的是辰企，一張來(lái)自加州的選票风纠，有多大概率會(huì)投給共和黨
（當(dāng)然，美國(guó)大選真正的投票機(jī)制并不是一人一票的簡(jiǎn)單投票制牢贸，這里只是為了示意）竹观。
而貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。
下面不加證明地直接給出貝葉斯定理：
樸素貝葉斯的基本思路
有了貝葉斯定理這個(gè)基礎(chǔ)潜索，下面來(lái)看看樸素貝葉斯算法的基本思路臭增。
樸素貝葉斯的核心思想就是，你不是要給我分類(lèi)嗎竹习？我算出自己屬于各個(gè)分類(lèi)的條件概率誊抛，屬于誰(shuí)的概率最大，就歸入哪一類(lèi)整陌。
你看拗窃，其思想就是這么的樸素。那么泌辫，屬于每個(gè)分類(lèi)的概率該怎么計(jì)算呢随夸？下面我們先祭出形式化語(yǔ)言！
設(shè)
x = {a1, a2, ..., am}為一個(gè)待分類(lèi)項(xiàng)震放，而每個(gè)a為x的一個(gè)特征屬性宾毒。有類(lèi)別集合
C = {y1, y2, ..., yn}我們的目的是要計(jì)算以下值
P(y1|x), P(y2|x), ... ,P(yn|x)如果
P(yk|x) = max{P(y1|x), P(y2|x), ... ,P(yn|x)}
則x屬于yk
那么現(xiàn)在的關(guān)鍵就是如何計(jì)算第3步中的各個(gè)條件概率。我們可以這么做：
找到一個(gè)已知分類(lèi)的待分類(lèi)項(xiàng)集合殿遂，這個(gè)集合叫做訓(xùn)練樣本集诈铛。
統(tǒng)計(jì)得到在各類(lèi)別下各個(gè)特征屬性的條件概率估計(jì)邪锌。即
P(a1|y1), P(a2|y1),...,P(am|y1); P(a1|y2), P(a2|y2),...,P(am|y2); ...; P(a1|yn), P(a2|yn),...,P(am|yn);-
如果各個(gè)特征屬性是條件獨(dú)立的，則根據(jù)貝葉斯定理有如下推導(dǎo)：
因?yàn)榉帜笇?duì)于所有類(lèi)別為常數(shù)癌瘾，因?yàn)槲覀冎灰獙⒎肿幼畲蠡钥擅俜帷Ｓ忠驗(yàn)楦魈卣鲗傩允菞l件獨(dú)立的，所以有：
別被形式化嚇倒妨退，我們來(lái)舉個(gè)栗子
如果你也跟我一樣妇萄，對(duì)形式化語(yǔ)言有嚴(yán)重生理反應(yīng)，不要怕咬荷，直接跳過(guò)前面這一坨冠句，我們通過(guò)一個(gè)鮮活的例子，用人類(lèi)的語(yǔ)言再解釋一遍這個(gè)過(guò)程幸乒。
以下這個(gè)例子轉(zhuǎn)自博客http://www.ruanyifeng.com/blog/2013/12/naive_bayes_classifier.html
某個(gè)醫(yī)院早上收了六個(gè)門(mén)診病人懦底，如下表。
| 癥狀 | 職業(yè) | 疾病 |
|---|---|---|
| 打噴嚏 | 護(hù)士 | 感冒 |
| 打噴嚏 | 農(nóng)夫 | 過(guò)敏 |
| 頭痛 | 建筑工人 | 腦震蕩 |
| 頭痛 | 建筑工人 | 感冒 |
| 打噴嚏 | 教師 | 感冒 |
| 頭痛 | 教師 | 腦震蕩 |
現(xiàn)在又來(lái)了第七個(gè)病人罕扎，是一個(gè)打噴嚏的建筑工人聚唐。請(qǐng)問(wèn)他最有可能患有何種疾病腔召？
本質(zhì)上杆查，這就是一個(gè)典型的分類(lèi)問(wèn)題，癥狀和職業(yè)是特征屬性臀蛛，疾病種類(lèi)是目標(biāo)類(lèi)別
根據(jù)貝葉斯定理
P(A|B) = P(B|A) P(A) / P(B)
可得
P(感冒|打噴嚏x建筑工人)
= P(打噴嚏x建筑工人|感冒) x P(感冒)
/ P(打噴嚏x建筑工人)
假定"打噴嚏"和"建筑工人"這兩個(gè)特征是獨(dú)立的亲桦，因此，上面的等式就變成了
P(感冒|打噴嚏x建筑工人)
= P(打噴嚏|感冒) x P(建筑工人|感冒) x P(感冒)
/ P(打噴嚏) x P(建筑工人)
這是可以計(jì)算的浊仆。
P(感冒|打噴嚏x建筑工人)
= 0.66 x 0.33 x 0.5 / 0.5 x 0.33
= 0.66
因此客峭，這個(gè)打噴嚏的建筑工人，有66%的概率是得了感冒抡柿。同理舔琅，可以計(jì)算這個(gè)病人患上過(guò)敏或腦震蕩的概率。比較這幾個(gè)概率沙绝，就可以知道他最可能得什么病搏明。
再舉個(gè)栗子
接下來(lái)，我們?cè)倥e一個(gè)樸素貝葉斯算法在實(shí)際中經(jīng)常被使用的場(chǎng)景的例子——文本分類(lèi)器闪檬，通常會(huì)用來(lái)識(shí)別垃圾郵件星著。
首先，我們可以把一封郵件的內(nèi)容抽象為由若干關(guān)鍵詞組成的集合粗悯，這樣是否包含每種關(guān)鍵詞就成了一封郵件的特征值虚循，而目標(biāo)類(lèi)別就是屬于垃圾郵件或不屬于垃圾郵件
假設(shè)每個(gè)關(guān)鍵詞在一封郵件里出現(xiàn)與否的概率相互之間是獨(dú)立的，那么只要我們有若干已經(jīng)標(biāo)記為垃圾郵件和非垃圾郵件的樣本作為訓(xùn)練集，那么就可以得出横缔，在全部垃圾郵件（記為T(mén)rash）出現(xiàn)某個(gè)關(guān)鍵詞Wi的概率铺遂，即P(Wi|Trash)
而我們最重要回答的問(wèn)題是，給定一封郵件內(nèi)容M茎刚，它屬于垃圾郵件的概率是多大襟锐，即P(Trash|M)
根據(jù)貝葉斯定理，有
P(Trash|M) = P(M|Trash) * P(Trash) / P(M)
我們先來(lái)看分子：
P(M|Trash)可以理解為在垃圾郵件這個(gè)范疇中遇見(jiàn)郵件M的概率膛锭，而一封郵件M是由若干單詞Wi獨(dú)立匯聚組成的粮坞，只要我們所掌握的單詞樣本足夠多，因此就可以得到
P(M|Trash) = P(W1|Trash) * P(W2|Trash) * ... P(Wn|Trash)
這些值我們之前已經(jīng)可以得到了初狰。
再來(lái)看分子里的另一部分P(Trash)莫杈，這個(gè)值也就是垃圾郵件的總體概率，這個(gè)值顯然很容易得到奢入，用訓(xùn)練集中垃圾郵件數(shù)除以總數(shù)即可筝闹。
而對(duì)于分母來(lái)說(shuō)，我們雖然也可以去計(jì)算它腥光，但實(shí)際上已經(jīng)沒(méi)有必要了关顷，因?yàn)槲覀円容^的P(Trash|M)和P(non-Trash|M)的分母都是一樣的，因此只需要比較分子大小即可柴我。
這樣一來(lái)解寝，我們就可以通過(guò)簡(jiǎn)單的計(jì)算扩然，比較郵件M屬于垃圾還是非垃圾二者誰(shuí)的概率更大了艘儒。
樸素貝葉斯樸素在哪？
樸素貝葉斯的英文叫做Naive Bayes夫偶，直譯過(guò)來(lái)其實(shí)是天真的貝葉斯界睁，那么他到底天真在哪了呢？
這主要是因?yàn)闃闼刎惾~斯的基本假設(shè)是所有特征值之間都是相互獨(dú)立的兵拢，這才使得概率直接相乘這種簡(jiǎn)單計(jì)算方式得以實(shí)現(xiàn)翻斟。然而在現(xiàn)實(shí)生活中，各個(gè)特征值之間往往存在一些關(guān)聯(lián)说铃，比如上面的例子访惜，一篇文章中不同單詞之間一定是有關(guān)聯(lián)的，比如有些詞總是容易同時(shí)出現(xiàn)腻扇。
因此债热，在經(jīng)典樸素貝葉斯的基礎(chǔ)上，還有更為靈活的建模方式——貝葉斯網(wǎng)絡(luò)（Bayesian Belief Networks, BBN）幼苛，可以單獨(dú)指定特征值之間的是否獨(dú)立窒篱。這里就不展開(kāi)了，有興趣的同學(xué)們可以做進(jìn)一步了解。
優(yōu)缺點(diǎn)
最后我們來(lái)對(duì)這個(gè)經(jīng)典算法做個(gè)點(diǎn)評(píng)：
優(yōu)點(diǎn)：
- 計(jì)算效率高
- 容易實(shí)現(xiàn)
- 計(jì)算復(fù)雜度不隨特征值維度增加而增加墙杯，可以處理高維度問(wèn)題
缺點(diǎn)：
- 對(duì)于特征值之間關(guān)系的假設(shè)過(guò)于單純配并，并不適用于關(guān)聯(lián)度較為復(fù)雜的模型
好了，對(duì)于樸素貝葉斯的介紹就到這里高镐，不知道各位看完之后是否會(huì)對(duì)數(shù)據(jù)挖掘這個(gè)領(lǐng)域產(chǎn)生了一點(diǎn)興趣了呢溉旋？
