貝葉斯信念網絡樸素貝葉斯分類〔NaiveBayesianClassification〕貝葉斯信念網絡〔BayesianBliefNetworks〕樸素貝葉斯分類一.摘要貝葉斯分類是一類分類算法的總稱，這類算法均以貝葉斯定理為根底，故統稱為貝葉斯分類。這里首先介紹分類問題，對分類問題進行一個正式的定義。然后，介紹貝葉斯分類算法的根底——貝葉斯定理。最后，通過實例討論貝葉斯分類中最簡單的一種：樸素貝葉斯分類。二.分類問題綜述對于分類問題，其實誰都不會陌生，說我們每個人每天都在執行分類操作一點都不夸張，只是我們沒有意識到罷了。例如，當你看到一個陌生人，你的腦子下意識判斷TA是男是女；你可能經常會走在路上對身旁的朋友說“這個人一看就很有錢、那邊有個非主流〞之類的話，其實這就是一種分類操作。從數學角度來說，分類問題可做如下定義：其中C叫做類別集合，其中每一個元素是一個類別，而I叫做項集合，其中每一個元素是一個待分類項，f叫做分類器。分類算法的任務就是構造分類器f。例如，醫生對病人進行診斷就是一個典型的分類過程，任何一個醫生都無法直接看到病人的病情，只能觀察病人表現出的病癥和各種化驗檢測數據來推斷病情，這時醫生就好比一個分類器，而這個醫生診斷的準確率，與他當初受到的教育方式〔構造方法〕、病人的病癥是否突出〔待分類數據的特性〕以及醫生的經驗多少〔訓練樣本數量〕都有密切關系。三.貝葉斯定理貝葉斯定理解決了現實生活里經常遇到的問題：某條件概率，如何得到兩個事件交換后的概率，也就是在P(A|B)的情況下如何求得P(B|A)。這里先解釋什么是條件概率：P(A|B)表示事件B已經發生的前提下，事件A發生的概率，P(B|A)叫做事件B發生下事件A的條件概率。其根本求解公式為：貝葉斯定理之所以有用，是因為我們在生活中經常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)那么很難直接得出，但我們更關心P(B|A)，貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。下面不加證明地直接給出貝葉斯定理：四.樸素貝葉斯分類1：樸素貝葉斯分類的原理與流程樸素貝葉斯分類是一種十分簡單的分類算法，叫它樸素貝葉斯分類是因為這種方法的思想真的很樸素，樸素貝葉斯的思想根底是這樣的：對于給出的待分類項〔x〕，求解在此項出現的條件下各個類別〔y〕出現的概率，哪個最大，就認為此待分類項屬于哪個類別。通俗來說，就好比這么個道理，你在街上看到一個黑人，我問你你猜這哥們哪里來的，你十有八九猜非洲。為什么呢？因為黑人中非洲人的比率最高，當然人家也可能是美洲人或歐洲人，但在沒有其它可用信息下，我們會選擇條件概率最大的類別，這就是樸素貝葉斯的思想根底。樸素貝葉斯分類的正式定義如下：那么現在的關鍵就是如何計算第3步中的各個條件概率。我們可以這么做：1〕、找到一個分類的待分類項集合，這個集合叫做訓練樣本集。2〕、統計得到在各類別下各個特征屬性的條件概率估計，即：、如果各個特征屬性是條件獨立的，那么根據貝葉斯定理有如下推導：因為分母對于所有類別為常數，因為我們只要將分子最大化皆可。又因為各特征屬性是條件獨立的，所以有:根據上述分析，樸素貝葉斯分類的流程可以由下列圖表示:可以看到，整個樸素貝葉斯分類分為三個階段：第一階段——準備工作階段，這個階段的任務是為樸素貝葉斯分類做必要的準備，主要工作是根據具體情況確定特征屬性，并對每個特征屬性進行適當劃分，然后由人工對一局部待分類項進行分類，形成訓練樣本集合。這一階段的輸入是所有待分類數據，輸出是特征屬性和訓練樣本。這一階段是整個樸素貝葉斯分類中唯一需要人工完成的階段，其質量對整個過程將有重要影響，分類器的質量很大程度上由特征屬性、特征屬性劃分及訓練樣本質量決定。第二階段——分類器訓練階段，這個階段的任務就是生成分類器，主要工作是計算每個類別在訓練樣本中的出現頻率及每個特征屬性劃分對每個類別的條件概率估計，并將結果記錄。其輸入是特征屬性和訓練樣本，輸出是分類器。這一階段是機械性階段，根據前面討論的公式可以由程序自動計算完成。第三階段——應用階段。這個階段的任務是使用分類器對待分類項進行分類，其輸入是分類器和待分類項，輸出是待分類項與類別的映射關系。這一階段也是機械性階段，由程序完成。五.樸素貝葉斯分類實例：檢測SNS社區中不真實賬號這個問題是這樣的，對于SNS社區來說，不真實賬號〔使用虛假身份或用戶的小號〕是一個普遍存在的問題，作為SNS社區的運營商，希望可以檢測出這些不真實賬號，從而在一些運營分析報告中防止這些賬號的干擾，亦可以加強對SNS社區的了解與監管。如果通過純人工檢測，需要消耗大量的人力，效率也十分低下，如能引入自動檢測機制，必將大大提升工作效率。這個問題說白了，就是要將社區中所有賬號在真實賬號和不真實賬號兩個類別上進行分類，下面我們一步一步實現這個過程。1、確定特征屬性及劃分首先設C=0表示真實賬號，C=1表示不真實賬號這一步要找出可以幫助我們區分真實賬號與不真實賬號的特征屬性，在實際應用中，特征屬性的數量是很多的，劃分也會比擬細致，但這里為了簡單起見，我們用少量的特征屬性以及較粗的劃分。我們選擇三個特征屬性：a1：日志數量/注冊天數〔日記密度〕{a<=0.05,0.05<a<0.2,a>=0.2}a2：好友數量/注冊天數〔好友密度〕{a<=0.1,0.1<a<0.8,a>=0.8}a3：是否使用真實頭像a3：{a=0〔不是〕,a=1〔是〕}2、獲取訓練樣本這里使用運維人員曾經人工檢測過的1萬個賬號作為訓練樣本。訓練樣本中每個類別的頻率〔數據〕用訓練樣本中真實賬號和不真實賬號數量分別除以1萬，得到：4、每個類別條件下各個特征屬性劃分的頻率〔數據〕5、使用分類器進行鑒別下面我們使用上面訓練得到的分類器鑒別一個賬號，這個賬號日志數量與注冊天數的比率a1為0.1，好友數與注冊天數的比率a2為0.2，使用非真實頭像a3=0。可以看到，雖然這個用戶沒有使用真實頭像，但是通過分類器的鑒別，更傾向于將此賬號歸入真實賬號類別。這個例子也展示了當特征屬性充分多時，樸素貝葉斯分類對個別屬性的抗干擾性。6.如何評價分類器的質量首先要定義，分類器的正確率指分類器正確分類的工程占所有被分類工程的比率。通常使用回歸測試來評估分類器的準確率，最簡單的方法是用構造完成的分類器對訓練數據進行分類，然后根據結果給出正確率評估。但這不是一個好方法，因為使用訓練數據作為檢測數據有可能因為過分擬合而導致結果過于樂觀，所以一種更好的方法是在構造初期將訓練數據一分為二，用一局部構造分類器，然后用另一局部檢測分類器的準確率。貝葉斯信念網絡在我們討論樸素貝葉斯分類時，樸素貝葉斯分類有一個限制條件，就是特征屬性必須有條件獨立或根本獨立〔實際上在現實應用中幾乎不可能做到完全獨立〕。當這個條件成立時，樸素貝葉斯分類法的準確率是最高的，但不幸的是，現實中各個特征屬性間往往并不條件獨立，而是具有較強的相關性，這樣就限制了樸素貝葉斯分類的能力。接下來討論貝葉斯分類中更高級、應用范圍更廣的一種算法——貝葉斯網絡〔又稱貝葉斯信念網絡或信念網絡〕。一：貝葉斯信念網絡概述貝葉斯網絡是一種圖形模型(概率理論和圖論相結合的產物)，又被稱為貝葉斯信念網絡、因果網絡，是描述隨機變量(事件)之間依賴關系的一種圖形模式。是一種將因果知識和概率知識相結合的信息表示框架，使得不確定性推理在邏輯上變得更為清晰．理解性更強。已經成為數據庫中的知識發現和決策支持系統的有效方法。從大量數據中構造貝葉斯網絡模型，進行不確定性知識的發現。貝葉斯網絡由網絡結構和條件概率表兩局部組成。貝葉斯網的網絡結構是一個有向無環圖〔DCG〕．由結點和有向弧段組成。每個結點代表一個事件或者隨機變量，變量值可以是離散的或連續的，結點的取值是完備互斥的。表示起因的假設和表示結果的數據均用結點表示。有向圖：頂點間的邊都是有向的,可以從頂點A指向B一條邊,但該邊不能從B指向A.有向無環圖：在一個有向圖中,如果從某頂點出發沒有一條回到該頂點的路徑,