在此推出一個算法系列的科普文章。我們大家在平時埋頭工程類工作之余，也可以抽身對一些常見算法進(jìn)行了解，這不僅可以幫助我們拓寬思路，從另一個維度加深對計算機(jī)技術(shù)領(lǐng)域的理解，做到觸類旁通，同時也可以讓我們搞清楚一些既熟悉又陌生的領(lǐng)域——比如數(shù)據(jù)挖掘、大數(shù)據(jù)、機(jī)器學(xué)習(xí)——的基本原理，揭開它們的神秘面紗，了解到其實很多看似高深的領(lǐng)域，其實背后依據(jù)的基礎(chǔ)和原理也并不復(fù)雜。而且，掌握各類算法的特點(diǎn)、優(yōu)劣和適用場景，是真正從事數(shù)據(jù)挖掘工作的重中之重。只有熟悉算法，才可能對紛繁復(fù)雜的現(xiàn)實問題合理建模，達(dá)到最佳預(yù)期效果。
本系列文章的目的是力求用最干練而生動的講述方式，為大家講解由國際權(quán)威的學(xué)術(shù)組織the IEEE International Conference on Data Mining (ICDM) 于2006年12月評選出的數(shù)據(jù)挖掘領(lǐng)域的十大經(jīng)典算法。它們包括：
1. C4.5（c4.5決策樹算法）
2. k-Means（k均值算法）
3. SVM（支持向量機(jī)）
4. Apriori（先驗算法）
5. EM（期望最大算法）
6. PageRank（google的網(wǎng)頁排序算法）
7. AdaBoost（Adaptive Boosting自適應(yīng)增強(qiáng)算法）
8. kNN（k近鄰算法）
9. Naive Bayes（樸素貝葉斯）
10. CART（分類與回歸樹）
一點(diǎn)鋪墊
本文作為本系列的第一篇，在介紹具體算法之前，先簡單為大家鋪墊幾個數(shù)據(jù)挖掘領(lǐng)域的常見概念：
在數(shù)據(jù)挖掘領(lǐng)域，按照算法本身的行為模式和使用目的，主要可以分為分類(classification)，聚類(clustering)和回歸(regression)幾種，其中：
分類 通常是在已經(jīng)給定了幾種類別和一部分屬于這些類別的數(shù)據(jù)的前提下，尋找分類規(guī)律，從而對沒有標(biāo)注類別的數(shù)據(jù)進(jìn)行類別劃分的行為。而這些事先給出的已經(jīng)分好類的示例數(shù)據(jù)通常被稱之為訓(xùn)練集，而這種通過已經(jīng)標(biāo)注了輸入與輸出關(guān)系訓(xùn)練集尋找規(guī)律的學(xué)習(xí)行為，在機(jī)器學(xué)習(xí)領(lǐng)域稱之為監(jiān)督式學(xué)習(xí)（Supervised learning）。
聚類 與分類十分類似，都是以找到數(shù)據(jù)和類別之間的關(guān)系作為最終目的。不同的是，聚類一開始并沒有給定的類別和訓(xùn)練集，而直接由算法找出其中潛在規(guī)律。聚類的目的在于把相似的東西聚在一起，而有時我們甚至并不關(guān)心這一類是什么。這種沒有訓(xùn)練集作為參照而直接對輸入數(shù)據(jù)進(jìn)行建模的學(xué)習(xí)方式被稱為無監(jiān)督的學(xué)習(xí)（Unsupervised learning）。
回歸 則是通過有限的輸入數(shù)據(jù)，找出一個能描述數(shù)據(jù)潛在規(guī)律的函數(shù)，從而對未來的走勢進(jìn)行預(yù)測。
打幾個不恰當(dāng)?shù)谋确?/strong>：
- 分類就好似垃圾歸類，一共就三種垃圾桶，并告訴你哪幾種垃圾扔進(jìn)哪個桶，通過分析得知將來要扔的所有垃圾該往哪兒扔；
- 聚類就像生物劃分界門綱目科屬種，一開始根本不知道全世界的生物有多少種類，通過不斷摸索找出這些類別；
- 而回歸就像是在探索一個能描述一切的萬物理論，不僅要能完美解釋當(dāng)前觀察到的所有現(xiàn)象，還能對未來做出精確預(yù)測。
另外，還有一個經(jīng)常有人問起的問題，就是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)這兩個概念的區(qū)別，這里一句話闡明我自己的認(rèn)識：機(jī)器學(xué)習(xí)是基礎(chǔ)，數(shù)據(jù)挖掘是應(yīng)用。機(jī)器學(xué)習(xí)研制出各種各樣的算法，數(shù)據(jù)挖掘根據(jù)應(yīng)用場景把這些算法合理運(yùn)用起來，目的是達(dá)到最好的挖掘效果。
當(dāng)然，以上的簡單總結(jié)一定不夠準(zhǔn)確和嚴(yán)謹(jǐn)，更多的是為了方便大家理解打的比方。如果大家有更精當(dāng)?shù)睦斫?，歡迎補(bǔ)充和交流。
進(jìn)入正題
好了，鋪墊了這么多，現(xiàn)在終于進(jìn)入正題！
作為本系列入門的第一篇，先為大家介紹一個容易理解又很有趣的算法——樸素貝葉斯。
先站好隊，樸素貝葉斯是一個典型的有監(jiān)督的分類算法。
貝葉斯定理
光從名字也可以想到，要想了解樸素貝葉斯，先要從貝葉斯定理說起。
貝葉斯定理是我們高中時代學(xué)過的一條概率學(xué)基礎(chǔ)定理，它描述了條件概率的計算方式。不要怕已經(jīng)把這些知識還給了體育老師，相信你一看公式就能想起來。
P(A|B)表示事件B已經(jīng)發(fā)生的前提下，事件A發(fā)生的概率，叫做事件B發(fā)生下事件A的條件概率。其基本求解公式為：
其中，P(AB)表示A和B同時發(fā)生的概率，P(B)標(biāo)識B事件本身的概率。
貝葉斯定理之所以有用，是因為我們在生活中經(jīng)常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們更關(guān)心P(B|A)。
舉個栗子，通過歷次美國大選，我們可以得知，投票給共和黨的選票有多大概率來自加州，但我們更關(guān)心的是，一張來自加州的選票，有多大概率會投給共和黨
（當(dāng)然，美國大選真正的投票機(jī)制并不是一人一票的簡單投票制，這里只是為了示意）。
而貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。
下面不加證明地直接給出貝葉斯定理：
樸素貝葉斯的基本思路
有了貝葉斯定理這個基礎(chǔ)，下面來看看樸素貝葉斯算法的基本思路。
樸素貝葉斯的核心思想就是，你不是要給我分類嗎？我算出自己屬于各個分類的條件概率，屬于誰的概率最大，就歸入哪一類。
你看，其思想就是這么的樸素。那么，屬于每個分類的概率該怎么計算呢？下面我們先祭出形式化語言！
設(shè)
x = {a1, a2, ..., am}為一個待分類項，而每個a為x的一個特征屬性。有類別集合
C = {y1, y2, ..., yn}我們的目的是要計算以下值
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)鍵就是如何計算第3步中的各個條件概率。我們可以這么做：
找到一個已知分類的待分類項集合，這個集合叫做訓(xùn)練樣本集。
統(tǒng)計得到在各類別下各個特征屬性的條件概率估計。即
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);-
如果各個特征屬性是條件獨(dú)立的，則根據(jù)貝葉斯定理有如下推導(dǎo)：
因為分母對于所有類別為常數(shù)，因為我們只要將分子最大化皆可。又因為各特征屬性是條件獨(dú)立的，所以有：
別被形式化嚇倒，我們來舉個栗子
如果你也跟我一樣，對形式化語言有嚴(yán)重生理反應(yīng)，不要怕，直接跳過前面這一坨，我們通過一個鮮活的例子，用人類的語言再解釋一遍這個過程。
以下這個例子轉(zhuǎn)自博客http://www.ruanyifeng.com/blog/2013/12/naive_bayes_classifier.html
某個醫(yī)院早上收了六個門診病人，如下表。
| 癥狀 | 職業(yè) | 疾病 |
|---|---|---|
| 打噴嚏 | 護(hù)士 | 感冒 |
| 打噴嚏 | 農(nóng)夫 | 過敏 |
| 頭痛 | 建筑工人 | 腦震蕩 |
| 頭痛 | 建筑工人 | 感冒 |
| 打噴嚏 | 教師 | 感冒 |
| 頭痛 | 教師 | 腦震蕩 |
現(xiàn)在又來了第七個病人，是一個打噴嚏的建筑工人。請問他最有可能患有何種疾??？
本質(zhì)上，這就是一個典型的分類問題，癥狀和職業(yè)是特征屬性，疾病種類是目標(biāo)類別
根據(jù)貝葉斯定理
P(A|B) = P(B|A) P(A) / P(B)
可得
P(感冒|打噴嚏x建筑工人)
= P(打噴嚏x建筑工人|感冒) x P(感冒)
/ P(打噴嚏x建筑工人)
假定"打噴嚏"和"建筑工人"這兩個特征是獨(dú)立的，因此，上面的等式就變成了
P(感冒|打噴嚏x建筑工人)
= P(打噴嚏|感冒) x P(建筑工人|感冒) x P(感冒)
/ P(打噴嚏) x P(建筑工人)
這是可以計算的。
P(感冒|打噴嚏x建筑工人)
= 0.66 x 0.33 x 0.5 / 0.5 x 0.33
= 0.66
因此，這個打噴嚏的建筑工人，有66%的概率是得了感冒。同理，可以計算這個病人患上過敏或腦震蕩的概率。比較這幾個概率，就可以知道他最可能得什么病。
再舉個栗子
接下來，我們再舉一個樸素貝葉斯算法在實際中經(jīng)常被使用的場景的例子——文本分類器，通常會用來識別垃圾郵件。
首先，我們可以把一封郵件的內(nèi)容抽象為由若干關(guān)鍵詞組成的集合，這樣是否包含每種關(guān)鍵詞就成了一封郵件的特征值，而目標(biāo)類別就是屬于垃圾郵件或不屬于垃圾郵件
假設(shè)每個關(guān)鍵詞在一封郵件里出現(xiàn)與否的概率相互之間是獨(dú)立的，那么只要我們有若干已經(jīng)標(biāo)記為垃圾郵件和非垃圾郵件的樣本作為訓(xùn)練集，那么就可以得出，在全部垃圾郵件（記為Trash）出現(xiàn)某個關(guān)鍵詞Wi的概率，即P(Wi|Trash)
而我們最重要回答的問題是，給定一封郵件內(nèi)容M，它屬于垃圾郵件的概率是多大，即P(Trash|M)
根據(jù)貝葉斯定理，有
P(Trash|M) = P(M|Trash) * P(Trash) / P(M)
我們先來看分子：
P(M|Trash)可以理解為在垃圾郵件這個范疇中遇見郵件M的概率，而一封郵件M是由若干單詞Wi獨(dú)立匯聚組成的，只要我們所掌握的單詞樣本足夠多，因此就可以得到
P(M|Trash) = P(W1|Trash) * P(W2|Trash) * ... P(Wn|Trash)
這些值我們之前已經(jīng)可以得到了。
再來看分子里的另一部分P(Trash)，這個值也就是垃圾郵件的總體概率，這個值顯然很容易得到，用訓(xùn)練集中垃圾郵件數(shù)除以總數(shù)即可。
而對于分母來說，我們雖然也可以去計算它，但實際上已經(jīng)沒有必要了，因為我們要比較的P(Trash|M)和P(non-Trash|M)的分母都是一樣的，因此只需要比較分子大小即可。
這樣一來，我們就可以通過簡單的計算，比較郵件M屬于垃圾還是非垃圾二者誰的概率更大了。
樸素貝葉斯樸素在哪？
樸素貝葉斯的英文叫做Naive Bayes，直譯過來其實是天真的貝葉斯，那么他到底天真在哪了呢？
這主要是因為樸素貝葉斯的基本假設(shè)是所有特征值之間都是相互獨(dú)立的，這才使得概率直接相乘這種簡單計算方式得以實現(xiàn)。然而在現(xiàn)實生活中，各個特征值之間往往存在一些關(guān)聯(lián)，比如上面的例子，一篇文章中不同單詞之間一定是有關(guān)聯(lián)的，比如有些詞總是容易同時出現(xiàn)。
因此，在經(jīng)典樸素貝葉斯的基礎(chǔ)上，還有更為靈活的建模方式——貝葉斯網(wǎng)絡(luò)（Bayesian Belief Networks, BBN），可以單獨(dú)指定特征值之間的是否獨(dú)立。這里就不展開了，有興趣的同學(xué)們可以做進(jìn)一步了解。
優(yōu)缺點(diǎn)
最后我們來對這個經(jīng)典算法做個點(diǎn)評：
優(yōu)點(diǎn)：
- 計算效率高
- 容易實現(xiàn)
- 計算復(fù)雜度不隨特征值維度增加而增加，可以處理高維度問題
缺點(diǎn)：
- 對于特征值之間關(guān)系的假設(shè)過于單純，并不適用于關(guān)聯(lián)度較為復(fù)雜的模型
好了，對于樸素貝葉斯的介紹就到這里，不知道各位看完之后是否會對數(shù)據(jù)挖掘這個領(lǐng)域產(chǎn)生了一點(diǎn)興趣了呢？
