FROM：?http://www.cnblogs.com/leoo2sk/archive/2010/09/17/1829190.html

0、寫在前面的話

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

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

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

1.1、摘要

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

1.2、分類問題綜述

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

????? 從數學角度來說，分類問題可做如下定義：

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

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

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

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

1.3、貝葉斯分類的基礎——貝葉斯定理

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

????? 表示事件B已經發生的前提下，事件A發生的概率，叫做事件B發生下事件A的條件概率。其基本求解公式為：。

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

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

?????

1.4、樸素貝葉斯分類

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

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

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

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

????? 2、有類別集合。

????? 3、計算。

????? 4、如果，則。

????? 那么現在的關鍵就是如何計算第3步中的各個條件概率。我們可以這么做：

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

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

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

?????

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

?????

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

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

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

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

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

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

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

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

????? 當特征屬性為連續值時，通常假定其值服從高斯分布（也稱正態分布）。即：

?????

????? 而

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

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

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

????? 下面討論一個使用樸素貝葉斯分類解決實際問題的例子，為了簡單起見，對例子中的數據做了適當的簡化。

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

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

????? 首先設C=0表示真實賬號，C=1表示不真實賬號。

????? 1、確定特征屬性及劃分

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

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

????? 下面給出劃分：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、獲取訓練樣本

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

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

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

?????

?????

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

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

?????

????? 5、使用分類器進行鑒別

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

?????

?????

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

1.5、分類器的評價

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

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

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

總結

以上是生活随笔為你收集整理的算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。