算法雜貨鋪系列

• 算法雜貨鋪——分類算法之樸素貝葉斯分類(Naive Bayesian classification)
• 算法雜貨鋪——分類算法之貝葉斯網(wǎng)絡(Bayesian networks)
• 算法雜貨鋪——分類算法之決策樹(Decision tree)
• 算法雜貨鋪——k均值聚類(K-means)

　　0、寫在前面的話

　　我個人一直很喜歡算法一類的東西，在我看來算法是人類智慧的精華，其中蘊含著無與倫比的美感。而每次將學過的算法應用到實際中，并解決了實際問題后，那種快感更是我在其它地方體會不到的。

      一直想寫關(guān)于算法的博文，也曾寫過零散的兩篇，但也許是相比于工程性文章來說太小眾，并沒有引起大家的興趣。最近面臨畢業(yè)找工作，為了能給自己增加籌碼，決定再次復習算法方面的知識，我決定趁這個機會，寫一系列關(guān)于算法的文章。這樣做，主要是為了加強自己復習的效果，我想，如果能將復習的東西用自己的理解寫成文章，勢必比單純的讀書做題掌握的更牢固，也更能觸發(fā)自己的思考。如果能有感興趣的朋友從中有所收獲，那自然更好。

      這個系列我將其命名為“算法雜貨鋪”，其原因就是這些文章一大特征就是“雜”，我不會專門討論堆棧、鏈表、二叉樹、查找、排序等任何一本數(shù)據(jù)結(jié)構(gòu)教科書都會講的基礎(chǔ)內(nèi)容，我會從一個“專題”出發(fā)，如概率算法、分類算法、NP問題、遺傳算法等，然后做一個引申，可能會涉及到算法與數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學、概率論、統(tǒng)計學、運籌學、數(shù)據(jù)挖掘、形式語言與自動機等諸多方面，因此其內(nèi)容結(jié)構(gòu)就像一個雜貨鋪。當然，我會竭盡所能，盡量使內(nèi)容“雜而不亂”。

　　1.1、摘要

      貝葉斯分類是一類分類算法的總稱，這類算法均以貝葉斯定理為基礎(chǔ)，故統(tǒng)稱為貝葉斯分類。本文作為分類算法的第一篇，將首先介紹分類問題，對分類問題進行一個正式的定義。然后，介紹貝葉斯分類算法的基礎(chǔ)——貝葉斯定理。最后，通過實例討論貝葉斯分類中最簡單的一種：樸素貝葉斯分類。

　　1.2、分類問題綜述

      對于分類問題，其實誰都不會陌生，說我們每個人每天都在執(zhí)行分類操作一點都不夸張，只是我們沒有意識到罷了。例如，當你看到一個陌生人，你的腦子下意識判斷TA是男是女；你可能經(jīng)常會走在路上對身旁的朋友說“這個人一看就很有錢、那邊有個非主流”之類的話，其實這就是一種分類操作。

      從數(shù)學角度來說，分類問題可做如下定義：

      已知集合：和，確定映射規(guī)則，使得任意有且僅有一個使得成立。（不考慮模糊數(shù)學里的模糊集情況）

      其中C叫做類別集合，其中每一個元素是一個類別，而I叫做項集合，其中每一個元素是一個待分類項，f叫做分類器。分類算法的任務就是構(gòu)造分類器f。

      這里要著重強調(diào)，分類問題往往采用經(jīng)驗性方法構(gòu)造映射規(guī)則，即一般情況下的分類問題缺少足夠的信息來構(gòu)造100%正確的映射規(guī)則，而是通過對經(jīng)驗數(shù)據(jù)的學習從而實現(xiàn)一定概率意義上正確的分類，因此所訓練出的分類器并不是一定能將每個待分類項準確映射到其分類，分類器的質(zhì)量與分類器構(gòu)造方法、待分類數(shù)據(jù)的特性以及訓練樣本數(shù)量等諸多因素有關(guān)。

      例如，醫(yī)生對病人進行診斷就是一個典型的分類過程，任何一個醫(yī)生都無法直接看到病人的病情，只能觀察病人表現(xiàn)出的癥狀和各種化驗檢測數(shù)據(jù)來推斷病情，這時醫(yī)生就好比一個分類器，而這個醫(yī)生診斷的準確率，與他當初受到的教育方式（構(gòu)造方法）、病人的癥狀是否突出（待分類數(shù)據(jù)的特性）以及醫(yī)生的經(jīng)驗多少（訓練樣本數(shù)量）都有密切關(guān)系。

　　1.3、貝葉斯分類的基礎(chǔ)——貝葉斯定理

      每次提到貝葉斯定理，我心中的崇敬之情都油然而生，倒不是因為這個定理多高深，而是因為它特別有用。這個定理解決了現(xiàn)實生活里經(jīng)常遇到的問題：已知某條件概率，如何得到兩個事件交換后的概率，也就是在已知P(A|B)的情況下如何求得P(B|A)。這里先解釋什么是條件概率：

      表示事件B已經(jīng)發(fā)生的前提下，事件A發(fā)生的概率，叫做事件B發(fā)生下事件A的條件概率。其基本求解公式為：。

      貝葉斯定理之所以有用，是因為我們在生活中經(jīng)常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們更關(guān)心P(B|A)，貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。

      下面不加證明地直接給出貝葉斯定理：

　　1.4、樸素貝葉斯分類

      1.4.1、樸素貝葉斯分類的原理與流程

      樸素貝葉斯分類是一種十分簡單的分類算法，叫它樸素貝葉斯分類是因為這種方法的思想真的很樸素，樸素貝葉斯的思想基礎(chǔ)是這樣的：對于給出的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，哪個最大，就認為此待分類項屬于哪個類別。通俗來說，就好比這么個道理，你在街上看到一個黑人，我問你你猜這哥們哪里來的，你十有八九猜非洲。為什么呢？因為黑人中非洲人的比率最高，當然人家也可能是美洲人或亞洲人，但在沒有其它可用信息下，我們會選擇條件概率最大的類別，這就是樸素貝葉斯的思想基礎(chǔ)。

      樸素貝葉斯分類的正式定義如下：

      1、設(shè)為一個待分類項，而每個a為x的一個特征屬性。

      2、有類別集合。

      3、計算。

      4、如果，則。

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

      1、找到一個已知分類的待分類項集合，這個集合叫做訓練樣本集。

      2、統(tǒng)計得到在各類別下各個特征屬性的條件概率估計。即。

      3、如果各個特征屬性是條件獨立的，則根據(jù)貝葉斯定理有如下推導：

      因為分母對于所有類別為常數(shù)，因為我們只要將分子最大化皆可。又因為各特征屬性是條件獨立的，所以有：

      根據(jù)上述分析，樸素貝葉斯分類的流程可以由下圖表示（暫時不考慮驗證）：

      可以看到，整個樸素貝葉斯分類分為三個階段：

      第一階段——準備工作階段，這個階段的任務是為樸素貝葉斯分類做必要的準備，主要工作是根據(jù)具體情況確定特征屬性，并對每個特征屬性進行適當劃分，然后由人工對一部分待分類項進行分類，形成訓練樣本集合。這一階段的輸入是所有待分類數(shù)據(jù)，輸出是特征屬性和訓練樣本。這一階段是整個樸素貝葉斯分類中唯一需要人工完成的階段，其質(zhì)量對整個過程將有重要影響，分類器的質(zhì)量很大程度上由特征屬性、特征屬性劃分及訓練樣本質(zhì)量決定。

      第二階段——分類器訓練階段，這個階段的任務就是生成分類器，主要工作是計算每個類別在訓練樣本中的出現(xiàn)頻率及每個特征屬性劃分對每個類別的條件概率估計，并將結(jié)果記錄。其輸入是特征屬性和訓練樣本，輸出是分類器。這一階段是機械性階段，根據(jù)前面討論的公式可以由程序自動計算完成。

      第三階段——應用階段。這個階段的任務是使用分類器對待分類項進行分類，其輸入是分類器和待分類項，輸出是待分類項與類別的映射關(guān)系。這一階段也是機械性階段，由程序完成。

      1.4.2、估計類別下特征屬性劃分的條件概率及Laplace校準

      這一節(jié)討論P(a|y)的估計。

      由上文看出，計算各個劃分的條件概率P(a|y)是樸素貝葉斯分類的關(guān)鍵性步驟，當特征屬性為離散值時，只要很方便的統(tǒng)計訓練樣本中各個劃分在每個類別中出現(xiàn)的頻率即可用來估計P(a|y)，下面重點討論特征屬性是連續(xù)值的情況。

      當特征屬性為連續(xù)值時，通常假定其值服從高斯分布（也稱正態(tài)分布）。即：

      而

      因此只要計算出訓練樣本中各個類別中此特征項劃分的各均值和標準差，代入上述公式即可得到需要的估計值。均值與標準差的計算在此不再贅述。

      另一個需要討論的問題就是當P(a|y)=0怎么辦，當某個類別下某個特征項劃分沒有出現(xiàn)時，就是產(chǎn)生這種現(xiàn)象，這會令分類器質(zhì)量大大降低。為了解決這個問題，我們引入Laplace校準，它的思想非常簡單，就是對沒類別下所有劃分的計數(shù)加1，這樣如果訓練樣本集數(shù)量充分大時，并不會對結(jié)果產(chǎn)生影響，并且解決了上述頻率為0的尷尬局面。

      1.4.3、樸素貝葉斯分類實例：檢測SNS社區(qū)中不真實賬號

      下面討論一個使用樸素貝葉斯分類解決實際問題的例子，為了簡單起見，對例子中的數(shù)據(jù)做了適當?shù)暮喕?/p>

      這個問題是這樣的，對于SNS社區(qū)來說，不真實賬號（使用虛假身份或用戶的小號）是一個普遍存在的問題，作為SNS社區(qū)的運營商，希望可以檢測出這些不真實賬號，從而在一些運營分析報告中避免這些賬號的干擾，亦可以加強對SNS社區(qū)的了解與監(jiān)管。

      如果通過純?nèi)斯z測，需要耗費大量的人力，效率也十分低下，如能引入自動檢測機制，必將大大提升工作效率。這個問題說白了，就是要將社區(qū)中所有賬號在真實賬號和不真實賬號兩個類別上進行分類，下面我們一步一步實現(xiàn)這個過程。

      首先設(shè)C=0表示真實賬號，C=1表示不真實賬號。

      1、確定特征屬性及劃分

      這一步要找出可以幫助我們區(qū)分真實賬號與不真實賬號的特征屬性，在實際應用中，特征屬性的數(shù)量是很多的，劃分也會比較細致，但這里為了簡單起見，我們用少量的特征屬性以及較粗的劃分，并對數(shù)據(jù)做了修改。

      我們選擇三個特征屬性：a1：日志數(shù)量/注冊天數(shù)，a2：好友數(shù)量/注冊天數(shù)，a3：是否使用真實頭像。在SNS社區(qū)中這三項都是可以直接從數(shù)據(jù)庫里得到或計算出來的。

      下面給出劃分：a1：{a<=0.05, 0.05<a<0.2, a>=0.2}，a1：{a<=0.1, 0.1<a<0.8, a>=0.8}，a3：{a=0（不是）,a=1（是）}。

      2、獲取訓練樣本

      這里使用運維人員曾經(jīng)人工檢測過的1萬個賬號作為訓練樣本。

      3、計算訓練樣本中每個類別的頻率

      用訓練樣本中真實賬號和不真實賬號數(shù)量分別除以一萬，得到：

      4、計算每個類別條件下各個特征屬性劃分的頻率

      5、使用分類器進行鑒別

      下面我們使用上面訓練得到的分類器鑒別一個賬號，這個賬號使用非真實頭像，日志數(shù)量與注冊天數(shù)的比率為0.1，好友數(shù)與注冊天數(shù)的比率為0.2。

      可以看到，雖然這個用戶沒有使用真實頭像，但是通過分類器的鑒別，更傾向于將此賬號歸入真實賬號類別。這個例子也展示了當特征屬性充分多時，樸素貝葉斯分類對個別屬性的抗干擾性。

　　1.5、分類器的評價

      雖然后續(xù)還會提到其它分類算法，不過這里我想先提一下如何評價分類器的質(zhì)量。

      首先要定義，分類器的正確率指分類器正確分類的項目占所有被分類項目的比率。

      通常使用回歸測試來評估分類器的準確率，最簡單的方法是用構(gòu)造完成的分類器對訓練數(shù)據(jù)進行分類，然后根據(jù)結(jié)果給出正確率評估。但這不是一個好方法，因為使用訓練數(shù)據(jù)作為檢測數(shù)據(jù)有可能因為過分擬合而導致結(jié)果過于樂觀，所以一種更好的方法是在構(gòu)造初期將訓練數(shù)據(jù)一分為二，用一部分構(gòu)造分類器，然后用另一部分檢測分類器的準確率。