k2貝葉斯演算法

『壹』 如何利用貪心法構建貝葉斯網路代碼

基於matlab的貝葉斯網路工具箱BNT是kevin p.murphy基於matlab語言開發的關於貝葉斯網路學習的開源軟體包，提供了許多貝葉斯網路學習的底層基礎函數庫，支持多種類型的節點（概率分布）、精確推理和近似推理、參數學習及結構學習、靜態模型和動態模型。
貝葉斯網路表示：BNT中使用矩陣方式表示貝葉斯網路，即若節點i到j有一條弧，則對應矩陣中（i，j）值為1，否則為0。
結構學習演算法函數：BNT中提供了較為豐富的結構學習函數，都有：
1. 學習樹擴展貝葉斯網路結構的TANC演算法learn_struct_tan().
2. 數據完整條件下學習一般貝葉斯網路結構的K2演算法learn_struct_k2()、貪婪搜索GS（greedy search）演算法learn_struct_gs()和爬山HC（hill climbing）演算法learn_struct_hc()等。
3. 缺失數據條件下學習一般貝葉斯網路結構的最大期望EM（expectation maximization）演算法learn_struct_EM（）和馬爾科夫鏈蒙特卡羅MCMC（Markov Chain Monte Carlo）learn_struct_mcmc()演算法等。
參數學習演算法函數：BNT中也提供了豐富的參數學習函數，都有：
1． 完整數據時，學習參數的方法主要有兩種：最大似然估計learn_params()和貝葉斯方法bayes_update_params();
2． 數據缺失時，如果已知網路拓撲結構，用EM演算法來計算參數，倘若未知網路拓撲結構，使用結構最大期望SEM（structure EM）演算法learn_struct_SEM()。
推理機制及推理引擎：為了提高運算速度，使各種推理演算法能夠有效應用，BNT工具箱採用了引擎機制，不同的引擎根據不同的演算法來完成模型轉換、細化和求解。這個推理過程如下：

BNT中提供了多種推理引擎，都有：
1． 聯合樹推理引擎jtree_inf_engine();
2． 全局聯合樹推理引擎global_joint_inf_engine();
3． 信念傳播推理引擎 belprop_inf_engine();
4． 變數消元推理引擎 var_elim_inf_engine().

『貳』 樸素貝葉斯（Naive Bayes）演算法

樸素貝葉斯演算法屬於分類演算法。發源於古典數學理論，對缺失數據不太敏感，有穩定的分類效率，模型所需估計的參數很少，演算法比較簡單。

樸素貝葉斯演算法 ， 貝葉斯 是說明這個演算法和貝葉斯定理有聯系，而 樸素 是因為處理實際的需要，做了一個簡化—— 假設每個特徵之間是獨立的 （如果研究的對象互相之間的影響很強，計算概率時考慮的問題非常復雜，做了獨立假設，就可以分解後進行研究），這是這個演算法模型與貝葉斯定理的區別。

將 x 作為特徵，y 作為類別，那公式左邊的 P（yi|x）就是說在知道特徵 x 的情況下，計算這個特徵屬於 yi 類的可能性大小。通過比較找出這個可能性的值最大的屬於哪一類，就將特徵 x 歸為這一類。

第3步的計算就是整個關鍵所在，計算依據是上面的貝葉斯公式。

對於每一個類的概率計算，公式右邊的分母的 P(x)都是相同的，所以可以不計算（我們只是對最終結果進行比較，不影響）。

P（yi）也稱為先驗概率，是 x 屬於 yi 類的一個概率，這個是通過歷史信息得到的（在程序實現的時候，歷史信息或者說先驗信息就是我們的訓練數據集），我們通過對訓練樣本數據進行統計，分別算出 x 屬於 y1,y2,...,yn 類的概率是多少,這個是比較容易得到的。

所以，主要是求 P（x|yi）= P(a1,a2,...,am|yi)

這個時候對於貝葉斯模型的 樸素 的獨立性假設就發揮作用了(綜合的計算變成了獨立計算後的綜合，簡化模型，極大地減少了計算的復雜程度)：

P(a1,a2,...,am|yi) = P(a1|yi)P(a2|yi)...P(am|yi)

所以計算想要得到的東西如下：

一個程序簡例

『叄』 貝葉斯規則

全概率公式 ：設試驗E的樣本空間為S，A為E的事件，B1,B2,...,Bn為S的一個劃分，並且P(Bi)>0(i=1,2,..,n) 那麼：
P(A)=P(A|B1)P(B1)+P(A|B2)PB2)+...+P(A|Bn)P(Bn)

全概率公式證明依據：P(A)=P(AS)=P(AB1)+P(AB2)...+P(ABn)=P(A|B1)P(B1)+P(A|B2)P(B2)+....P(A|Bn)P(Bn)
S是樣本空間，B1,B2,...,Bn是S的劃分

貝葉斯公式 ：設試驗E的樣本空間為S，A為E的事件，B1,B2,..,Bn為S的一個劃分，且P(A)>0,P(Bi)>0(i=1,2,3,...,n)那麼：

貝葉斯公式分子證明依據（條件概率公式）：P(Bi|A)=P(BiA)/P(A) P(BiA)=P(A|Bi)P(Bi)
貝葉斯公式分母證明依據（全概率公式）

貝葉斯規則以Thomas Bayes主教命名。
用來估計統計量的某種性質。
貝葉斯是用概率反映知識狀態的確定性程度，數據集可以直接觀測到，所以他不是隨機的。

貝葉斯推斷與其他統計學推斷方法截然不同。它建立在主觀判斷的基礎上，也就是說，你可以不需要客觀證據，先估計一個值，然後根據實際結果不斷修正。貝葉斯推斷需要大量逗虧的計算。

http://www.ruanyifeng.com/blog/2011/08/bayesian_inference_part_one.html

他是一種條件概率條件概率。 比如：在B發生時，A發生的可能性。
公式為：

公式中，事件Bi的概率為P(Bi)，事件Bi已發生條件下事件A的概率為P(A│Bi)，事件A發生條件下事件Bi的概率為P(Bi│A)。
用來計算簡單條件下發生的復雜事件。

正如以上所說：在B發生時，A發生的可能性。 P(A|B)
通過韋恩圖可以看到：

B發生時，A發生的概率：P(A|B)=P(A∩B)/P(B)
可以得到條件概率的推導過程如下：

等式合並：

最終得到：

P(類山察神別|特徵) = P(特徵|類別)P(類別)/P(特徵)

根據以往經驗和分析得到的概率。 往往作為 由因求果 問題中的 因 出現的概率。 又稱： 古典概率

（在觀測數據之前，我們將已知的知識表示成 先驗概率分布 但是一般而言我們會選擇一個相當寬泛的先驗（高熵），反映在觀測到的任何數據前，參數的高度不確定性）
（通常，先驗概率開始是相對均勻的分布或高熵的高斯分布，觀測數據通常會使後驗的熵下降）

在上述貝葉斯公式中，我們把P(A)稱為 先驗概率 。沒祥 （B事件發生之前，對A事件概率的一個判斷）
把P（A|B)稱為 後驗概率 。(事件B發生之後，對事件A概率的重新評估）
P(B|A)/P(B)稱為：可能性函數。 這是一個調整因子，使得預估概率更接近真實概率。

在一個通信系統中，在收到某個消息之後，接收端所了解到的該消息發送的概率稱為後驗概率。
他是在給出相關證據或者數據後得到的條件概率。
他指的是在得到結果的信息重新修正的概率。計算後驗概率必須以先驗概率為基礎。

後驗概率 = 先驗概率 * 調整因子

上述調整因子又叫 似然函數
他是關於統計模型參數的函數。
假定一個關於參數y，具有離散型概率分布P的隨機變數X，則在給定X的輸出x時，關於參數y的似然函數是：L(y|x)等於給定參數y後變數X的概率：
L(y|x) = P(X=x|y) = Py(x)

概率：用於已知一些參數的情況下，預測接下來的觀測所得到的結果。
似然：用於在已知某些觀測所得到的結果時，對有關食物的性質的參數進行估計。
似然函數可以理解為條件概率的逆反。

材料：
1：先驗概率：利用現有材料計算的。
2：後驗概率：利用先驗概率+補充材料計算的。
計算：
1：先驗概率：古典概率。
2：後驗概率：使用貝葉斯公式，使用樣本資料計算邏輯概率，還要使用概率分布，數理統計。

將復雜事件概率求解 轉化為： 不同情況下發生的簡單事件概率的和。
用來計算復雜事件的概率。

定義：假設{Bn:n=1,2,3,...}是一個概率空間的有限或者無限的分割（既Bn為一完備事件組），且每個集合Bn是一個可測集合，則對任意時間A有全概率公式：

通過條件概率的推導可以看到:P(A∩B) = P(A|B)P(B) = P(B|A)P(A)
帶入上述公式。

全概率公式，將對一復雜事件A的概率求解問題轉換為在不同情況下或者不同原因Bn下發生的簡單概率的求和問題。

現在我們有樣本空間S，事件A，A『和B。
韋恩圖：

從上圖給出：
P(B) = P(B∩A) + P(B∩A')
將條件概率推導中的公式有：
P(B∩A) = P(B|A)P(A)
將上述公式合並：
P(B) = P(B|A)P(A) + P(B|A')P(A')

解釋：如果A和A'構成樣本空間，那麼事件B的概率就是A和A』的概率分別乘以B對這兩個事件的條件概率之和。
公式另一寫法：

樸素貝葉斯演算法是假設各個特徵之間相互獨立。

假設一種特定的癌症，發病率為人口的1%。
如果得了這種癌症，檢查結果90%可能是呈陽性。
但是你並沒有患癌症，檢查結果還是呈陽性。所以，假設 如果你沒有患上這種特定癌症，有90%可能性是呈陰性的。 這通常叫做 特異性 。

問題：沒有任何症狀的情況下，你進行了檢查，檢查結果呈陽性， 那麼你認為患上這種特定癌症的可能性是多少？
之前的癌症概率是 1%，敏感型和特殊性是 90%，癌症測試結果呈陽性的人患病的概率有多大？
是： 百分之八又1/3

假定A事件表示得病，P(A)=0.001,這是 先驗概率 。（沒有做實驗之前，我們預計的發病率）
假定B事件表示陽性，那麼計算P=(A|B)，這是 後驗概率 。（做了試驗後，對發病率的估計）
P(A|B)=P(A)P(B|A)/P(B)
用全概率公式，改寫分母：
P(A|B)=P(A)P(B|A)/(P(B|A)P(A)+P(B|A反)P(A反))

假設：現在我們有兩個人A和B，兩人寫郵件都會用到love，deal，life這三個單詞。
A使用三個單詞的頻率為：love=0.1,deal=0.8,life=0.1。
B使用三個單詞的頻率為：love=0.5，deal=0.2,life=0.3。
現在我們有很多封email，假設這封email作者是A或者B是等概率的，
現在有一封email，只包括life和deal兩個詞，那麼這封郵件的作者是A或者B的概率。

計算先驗概率
P(emailA) = P(lifeA)P(dealA)P(A) = 0.1* 0.8 * 0.5 = 0.04
P(emailB) = P(lifeB)P(dealB)P(B) = 0.3 * 0.2 * 0.5 = 0.03

當觀察到life和deal兩個詞的條件下，作者是A或者B的概率
計算後驗概率
P(emailA|"life,deal") = P(emailA) * f(x)(似然函數) = 0.04 * (1/(0.04+ 0.03)) = 0.57
P(emailB|"life,deal") = P(emialB) * f(x) = 0.03 * (1/(0.04+ 0.03)) = 0.43

全概率：
P(emailA|"life,deal") + P(emailB|"life,deal") = 1

『肆』 貝葉斯的學習演算法

DATA MINING? 如果是和k-means那個配套用的話，可以使用Bayesian 演算法先進行分類，初始所有樣本屬於一個大類，然後隨機的把這個大類切割成2個小類並且計算差派鬧錯誤率，切N次，選錯誤虛罩率最低的一次切割。然後把2個裡面較大的錯誤率的那個類繼續切割，如此反復，直到，切成羨念N個clusters。其中錯誤率應該有個threshold。

『伍』 貝葉斯網路演算法Java實現

public static void main(String[] args){
int n=10;//定義n
int[] π={};//定義存放π的數組
for(int i=0;i++;i<n){
π[i]=Ф;
int Pold=g(i,π[i]);//調用g方法
boolean OkToProceed=true;//定義布爾值
while(OkToProceed &&Math.abs(π[i])<u){
//寫不下去了。。。好多都不知道是什麼方法
}

}
}

『陸』 貝葉斯分類器的基本思想是什麼

樸素貝葉斯分類器是一種應用基於獨立假設的貝葉斯定理的簡單概率分類器，之所以成為樸素，應該是Naive的直譯，意思為簡單，樸素，天真。

1、貝葉斯方法

貝葉斯方法是以貝葉斯原理為基礎，使用概率統計的知識對樣本數據集進行分類。由於其有著堅實的數學基礎，貝葉斯分類演算法的誤判率是很低的。

貝葉斯方法的特點是結合先驗概率和後驗概率，即避免了只使用先驗概率的主觀偏見，也避免了單獨使用樣本信息的過擬合現象。貝葉斯分類演算法在數據集較大的情況下表現出較高的准確率，同時演算法本身也比較簡單。

2、樸素貝葉斯算和羨禪法

樸素貝葉斯喚塵演算法（Naive Bayesian algorithm) 是應用最為廣泛的分類演算法之一。

樸素貝葉斯派做方法是在貝葉斯演算法的基礎上進行了相應的簡化，即假定給定目標值時屬性之間相互條件獨立。也就是說沒有哪個屬性變數對於決策結果來說佔有著較大的比重，也沒有哪個屬性變數對於決策結果佔有著較小的比重。

雖然這個簡化方式在一定程度上降低了貝葉斯分類演算法的分類效果，但是在實際的應用場景中，極大地簡化了貝葉斯方法的復雜性。

(6)k2貝葉斯演算法擴展閱讀

研究意義

人們根據不確定性信息作出推理和決策需要對各種結論的概率作出估計，這類推理稱為概率推理。概率推理既是概率學和邏輯學的研究對象，也是心理學的研究對象，但研究的角度是不同的。概率學和邏輯學研究的是客觀概率推算的公式或規則。

而心理學研究人們主觀概率估計的認知加工過程規律。貝葉斯推理的問題是條件概率推理問題，這一領域的探討對揭示人們對概率信息的認知加工過程與規律、指導人們進行有效的學習和判斷決策都具有十分重要的理論意義和實踐意義。

『柒』 貝葉斯分類演算法和樸素貝葉斯演算法的區別

為了測試評估貝葉斯分類器的性能,用不同數據集進行對比實驗是必不可少的. 現有的貝葉斯網路實驗軟體包都是針對特定目的設計的,不能滿足不同研究的需要. 介紹了用Matlab在BNT軟體包基礎上建構的貝葉斯分類器實驗平台MBNC,闡述了MBNC的系統結構和主要功能,以及在MBNC上建立的樸素貝葉斯分類器NBC,基於互信息和條件互信息測度的樹擴展的貝葉斯分類器TANC,基於K2演算法和GS演算法的貝葉斯網路分類器BNC. 用來自UCI的標准數據集對MBNC進行測試,實驗結果表明基於MBNC所建構的貝葉斯分類器的性能優於國外同類工作的結果,編程量大大小於使用同類的實驗軟體包,所建立的MBNC實驗平台工作正確、有效、穩定. 在MBNC上已經進行貝葉斯分類器的優化和改進實驗,以及處理缺失數據等研究工作.

『捌』 貝葉斯演算法是什麼

貝葉斯演算法是統計學的一種分類方法，它是一類利用概率統計知識進行分類的演算法。在許多場合，樸素貝葉斯（Naïve Bayes，NB)分類演算法可以與決策樹和神經網路分類演算法相媲美，該演算法能運用到大型資料庫中，而且方法簡單、分類准確率高、速度快。

由於貝葉斯定理假設一個屬性值對給定類的影響獨立於其它屬性的值，而此假設在實際情況中經常是不成立的，因此其分類准確率可能會下降。為此，就衍生出許多降低獨立性假設的貝葉斯分類演算法，如TAN(tree augmented Bayes network)演算法。

貝葉斯演算法的主要步驟：

1、收集大量的垃圾郵件和非垃圾郵件，建立垃圾郵件集和非垃圾郵件集。

2、提取郵件主題和郵件體中的獨立字元串，例如ABC32，￥234等作為TOKEN串並統計提取出的TOKEN串出現的次數即字頻。按照上述的方法分別處理垃圾郵件集和非垃圾郵件集中的所有郵件。

3、每一個郵件集對應一個哈希表，hashtable_good對應非垃圾郵件集而hashtable_bad對應垃圾郵件集。表中存儲TOKEN串到字頻的映射關系。

『玖』 貝葉斯分類演算法的基本步驟

主要有以下7個步驟：
1. 收集大量的垃圾郵件和非垃圾郵件，建立垃圾郵件集和非垃圾郵件集。
2. 提取郵件主題和郵件體中的獨立字元串，例如 ABC32，￥234等作為TOKEN串並統計提取出的TOKEN串出現的次數即字頻。按照上述的方法分別處理垃圾郵件集和非垃圾郵件集中的所有郵件。
3. 每一個郵件集對應一個哈希表，hashtable_good對應非垃圾郵件集而hashtable_bad對應垃圾郵件集。表中存儲TOKEN串到字頻的映射關系。
4. 計算每個哈希表中TOKEN串出現的概率P=（某TOKEN串的字頻）/（對應哈希表的長度）。
5. 綜合考慮hashtable_good和hashtable_bad，推斷出當新來的郵件中出現某個TOKEN串時，該新郵件為垃圾郵件的概率。數學表達式為：
A 事件 ---- 郵件為垃圾郵件；
t1,t2 …….tn 代表 TOKEN 串
則 P （ A|ti ）表示在郵件中出現 TOKEN 串 ti 時，該郵件為垃圾郵件的概率。
設
P1 （ ti ） = （ ti 在 hashtable_good 中的值）
P2 （ ti ） = （ ti 在 hashtable_ bad 中的值）
則 P （ A|ti ） =P2 （ ti ） /[ （ P1 （ ti ） +P2 （ ti ） ] ；
6. 建立新的哈希表hashtable_probability存儲TOKEN串ti到P（A|ti）的映射
7. 至此，垃圾郵件集和非垃圾郵件集的學習過程結束。根據建立的哈希表 hashtable_probability可以估計一封新到的郵件為垃圾郵件的可能性。
當新到一封郵件時，按照步驟2，生成TOKEN串。查詢hashtable_probability得到該TOKEN 串的鍵值。
假設由該郵件共得到N個TOKEN 串，t1,t2…….tn,hashtable_probability中對應的值為 P1 ， P2 ， ……PN ， P(A|t1 ,t2, t3……tn) 表示在郵件中同時出現多個TOKEN串t1,t2……tn時，該郵件為垃圾郵件的概率。
由復合概率公式可得
P(A|t1 ,t2, t3……tn)=（P1*P2*……PN）/[P1*P2*……PN+（1-P1）*（1-P2）*……（1-PN）]
當 P(A|t1 ,t2, t3……tn) 超過預定閾值時，就可以判斷郵件為垃圾郵件。