在此推出一個(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)槲覀冎灰獙⒎肿幼畲蠡钥擅俜帷S忠驗(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)興趣了呢溉旋?