數(shù)據(jù)挖掘十大經(jīng)典算法(1)——樸素貝葉斯(Naive Bayes)

在此推出一個(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)。

Thomas Bayes和他的貝葉斯公式

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ǔ)言!

  1. 設(shè)x = {a1, a2, ..., am}為一個(gè)待分類(lèi)項(xiàng)震放,而每個(gè)a為x的一個(gè)特征屬性宾毒。

  2. 有類(lèi)別集合C = {y1, y2, ..., yn}

  3. 我們的目的是要計(jì)算以下值P(y1|x), P(y2|x), ... ,P(yn|x)

  4. 如果P(yk|x) = max{P(y1|x), P(y2|x), ... ,P(yn|x)}
    x屬于yk

那么現(xiàn)在的關(guān)鍵就是如何計(jì)算第3步中的各個(gè)條件概率。我們可以這么做:

  1. 找到一個(gè)已知分類(lèi)的待分類(lèi)項(xiàng)集合殿遂,這個(gè)集合叫做訓(xùn)練樣本集诈铛。

  2. 統(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);

  3. 如果各個(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)興趣了呢溉旋?

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市嫉髓,隨后出現(xiàn)的幾起案子低滩,更是在濱河造成了極大的恐慌,老刑警劉巖岩喷,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件恕沫,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡纱意,警方通過(guò)查閱死者的電腦和手機(jī)婶溯,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)偷霉,“玉大人迄委,你說(shuō)我怎么就攤上這事±嗌伲” “怎么了叙身?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)硫狞。 經(jīng)常有香客問(wèn)我信轿,道長(zhǎng),這世上最難降的妖魔是什么残吩? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任财忽,我火速辦了婚禮,結(jié)果婚禮上泣侮,老公的妹妹穿的比我還像新娘即彪。我一直安慰自己,他們只是感情好活尊,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布隶校。 她就那樣靜靜地躺著,像睡著了一般蛹锰。 火紅的嫁衣襯著肌膚如雪深胳。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,785評(píng)論 1 314
  • 那天宁仔,我揣著相機(jī)與錄音稠屠,去河邊找鬼峦睡。 笑死,一個(gè)胖子當(dāng)著我的面吹牛权埠,可吹牛的內(nèi)容都是我干的榨了。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼攘蔽,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼龙屉!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起满俗,我...
    開(kāi)封第一講書(shū)人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤转捕,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后唆垃,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體五芝,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年辕万,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了枢步。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡渐尿,死狀恐怖醉途,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情砖茸,我是刑警寧澤隘擎,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站凉夯,受9級(jí)特大地震影響货葬,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜恍涂,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一宝惰、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧再沧,春花似錦、人聲如沸尊残。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)寝衫。三九已至顷扩,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間慰毅,已是汗流浹背隘截。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人婶芭。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓东臀,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親犀农。 傳聞我的和親對(duì)象是個(gè)殘疾皇子惰赋,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容