2020 2 22 數據倉庫與數據挖掘 1 第7章貝葉斯網絡 2 貝葉斯網絡是20世紀80年代發展起來的 最早由JudeaPearl于1986年提出 多用于專家系統 成為表示不確定性知識和推理問題的流行方法 貝葉斯網絡最早起源于貝葉斯統計分析 它是概率理論和圖論相結合的產物 本章通過引例討論貝葉斯網絡需要解決的問題 介紹貝葉斯概率基礎 對貝葉斯網絡進行概述 講解貝葉斯網絡的預測 診斷和訓練算法 講述SQLServer2005中貝葉斯網絡的應用方法 3 7 l引例先看一個關于概率推理的例子 圖7 1中有6個結點 參加晚會 party PT 宿醉 hangover HO 患腦瘤 braintumor BT 頭疼 headache HA 有酒精味 smellalcohol SA 和X射線檢查呈陽性 posxray PX 可以把圖7 1想象成為這樣一個場景 一個中學生回家后 其父母猜測她參加了晚會 并且喝了酒 第二天這個學生感到頭疼 她的父母帶她到醫院做頭部的X光檢查 圖7 1基于結點間概率關系的推理 4 通過長期的觀察 或者從別人那里了解 這個中學生的父母知道他們的女兒參加晚會的概率 通過長時間的數據積累 他們也知道他們的女兒參加晚會后宿醉的概率 因此 結點party和結點hangover之間有一條連線 同樣 有明顯的因果關系或相關關系的結點之間都有一條連線 并且連線從原因結點出發 指向結果結點 針對圖7 1所示的網絡 有許多問題需要解決 例如 1 如果父母已知他們的女兒參加了晚會 那么第二天一早 她呼出的氣體中有酒精味的概率有多大 也就是說 當party發生時 smellalcohol發生的概率有多大 2 如果他們的女兒頭疼 那么她患腦瘤的概率有多大 這時 如果他們又知道昨晚她參加了晚會 那么綜合這些情況 她患腦瘤的可能性有多大 這兩個例子都是從原因推理結果的 還有許多從結果反推原因的例子 例如 如果父母早晨聞到他們的女兒呼出的氣體中有酒精味 那么她昨晚參加晚會的概率有多大 等等 為了系統地解決上面的各類問題 需要先掌握一定的概率基礎知識 5 7 2貝葉斯概率基礎貝葉斯概率是貝葉斯網絡運行的理論基礎 就貝葉斯概率而言 其原理和應用都比較簡單 但貝葉斯概率理論經歷了長時間的波折才被逐漸認可 直到20世紀60年代 貝葉斯概率理論才被廣泛接受并大量應用 下面將從基本的條件概率公式和全概率公式入手介紹貝葉斯概率 7 2 1先驗概率 后驗概率和條件概率下面介紹貝葉斯概率中用到的有關概率論的基本概念 1 先驗概率 先驗概率是指根據歷史的資料或主觀判斷所確定的各種事件發生的概率 該概率沒有經過實驗證實 屬于檢驗前的概率 2 后驗概率 后驗概率一般是指通過貝葉斯公式 結合調查等方式獲取了新的附加信息 對先驗概率修正后得到的更符合實際的概率 3 條件概率 當條件確定時 某事件發生的條件概率就是該事件的條件概率 6 例如 1號箱中有2個白球和4個紅球 2號箱中有5個白球和3個紅球 現隨機地從1號箱中取出一球放人2號箱 然后從2號箱隨機取出一球 問從2號箱取出紅球的概率是多少 解 令A表示事件 最后從2號箱中取出的是紅球 令B表示從1號箱中取出的是紅球 則 由式 7 5 7 2 3全概率公式 設A B是兩個事件 那么A可以表示為 顯然 如果P B P B 0 則 7 上例采用的方法是概率論中常用的方法 為了求復雜事件的概率 往往可以把它分解成若干個互不相容的簡單事件 然后利用條件概率和乘法公式 求出這些簡單事件的概率 最后利用概率可加性 得到最終結果 這一方法的一般化就是所謂的全概率公式 設 為試驗E的樣本空間 A為E的事件 B1 B2 Bn為E的一組事件 若滿足以下兩個條件 則稱B1 B2 Bn為樣本空間 的一個分割 若B1 B2 Bn為樣本空間的一個分割 那么 對每一次試驗 事件B1 B2 Bn必有一個且僅有一個發生 8 例如 設實驗E為 擲一顆骰子觀察其點數 它的樣本空間 1 2 3 4 5 6 的一組事件B1 l 2 B2 3 4 B3 5 6 是樣本空間 的一個分割 而事件組B1 1 2 3 B2 3 4 B3 5 6 不是樣本空間 的一個分割 因為B1B2 3 設實驗E為樣本空間 A為E的事件 B1 B2 Bn為 的一個分割 且P Bi 0 i 1 2 n 則 式 7 6 被稱為全概率公式 9 例 甲 乙 丙三人向同一飛機射擊 設甲 乙 丙射中的概率分別為0 4 0 5和0 7 又設若只有一人射中 飛機墜落的概率為0 2 若有兩人射中 飛機墜落的概率為0 6 若有三人射中 飛機必墜落 求飛機墜落的概率 解 記A 飛機墜落 Bi 共i個人射中飛機 i 1 2 3 Bi分別為 B1 甲射中 乙丙未射中 乙射中 甲丙未射中 丙射中 甲乙未射中 B2 甲未射中 乙丙射中 乙未射中 甲丙射中 丙未射中 甲乙射中 B3 甲乙丙均射中 可以計算i個人射中飛機的概率P B1 0 4 0 5 0 3 0 6 0 5 0 3 0 6 0 5 0 7 0 36P B2 0 6 0 5 0 7 0 4 0 5 0 7 0 4 0 5 0 3 0 41P B3 0 4 0 5 0 7 0 14再由題設 P A B1 0 2 P A B2 O 6 P A B3 1 利用全概率公式 10 設實驗E為樣本空間 A為E的事件 B1 B2 Bn為 的一個分割 且P Bi 0 i 1 2 n 則 式 7 7 被稱為貝葉斯公式 例如 某電子設備廠所用的元件是由三家元件廠提供的 根據以往的記錄 這三個廠家的次品率分別為0 02 0 01 0 03 提供元件的份額分別為0 15 0 8 0 05 設這三個廠家的產品在倉庫是均勻混合的 且無區別的標志 問題1 在倉庫中隨機地取一個元件 求它是次品的概率 問題2 在倉庫中隨機地取一個元件 若已知它是次品 為分析此次品出自何廠 需求出此元件由三個廠家分別生產的概率是多少 7 2 4貝葉斯公式 11 0 15 0 02 0 80 0 01 0 05 0 03 0 0125對于問題2 由貝葉斯公式 解 設A取到的元件是次品 Bi標識取到的元件是由第i個廠家生產的 則P B1 0 15 P B2 0 8 P B3 0 05對于問題1 由全概率公式 以上結果表明 這個次品來自第2家工廠的可能性最大 來自第1家工廠的概率次之 來自第3家工廠的概率最小 12 7 3貝葉斯網絡概述貝葉斯網絡是一種圖形模型 概率理論和圖論相結合的產物 又被稱為貝葉斯信念網絡 因果網絡 是描述隨機變量 事件 之間依賴關系的一種圖形模式 是一種將因果知識和概率知識相結合的信息表示框架 使得不確定性推理在邏輯上變得更為清晰 理解性更強 已經成為數據庫中的知識發現和決策支持系統的有效方法 從大量數據中構造貝葉斯網絡模型 進行不確定性知識的發現 7 3 1貝葉斯網絡的組成和結構貝葉斯網絡由網絡結構和條件概率表兩部分組成 貝葉斯網的網絡結構是一個有向無環圖 由結點和有向弧段組成 每個結點代表一個事件或者隨機變量 變量值可以是離散的或連續的 結點的取值是完備互斥的 表示起因的假設和表示結果的數據均用結點表示 例如 圖7 1描述的網絡符合貝葉斯網絡的條件 是一個典型的貝葉斯網絡 13 7 3 2貝葉斯網絡的優越性貝葉斯網絡的優勢主要體現在以下方面 1 貝葉斯網絡推理是利用其表達的條件獨立性 根據已有信息快速計算待求概率值的過程 應用貝葉斯網絡的概率推理算法 對已有的信息要求低 可以進行信息不完全 不確定情況下的推理 2 具有良好的可理解性和邏輯性 這是神經元網絡無法比擬的 神經元網絡從輸入層輸入影響因素信息 經隱含層處理后傳人輸出層 是黑匣子似的預測和評估 而貝葉斯網絡是白匣子 3 專家知識和試驗數據的有效結合相輔相成 忽略次要聯系而突出主要矛盾 可以有效避免過學習 4 貝葉斯網絡以概率推理為基礎 推理結果說服力強 而且相對貝葉斯方法來說 貝葉斯網絡對先驗概率的要求大大降低 貝葉斯網絡通過實踐積累可以隨時進行學習來改進網絡結構和參數 提高預測診斷能力 并且基于網絡的概率推理算法 貝葉斯網絡接受了新信息后立即更新網絡中的概率信息 14 7 3 3貝葉斯網絡的三個主要議題貝葉斯網絡的主要功能是進行預測和診斷 在貝葉斯網絡工作之前 需要對歷史數據進行訓練 所以 預測 診斷和訓練構成了貝葉斯網絡的三個主要議題 1 貝葉斯網絡預測貝葉斯網絡是一種概率推理技術 使用概率理論來處理在描述不同知識成分之間的條件而產生的不確定性 貝葉斯網絡的預測是指從起因推測一個結果的推理 也稱為由頂向下的推理 目的是由原因推導出結果 已知一定的原因 證據 利用貝葉斯網絡的推理計算 求出由原因導致的結果發生的概率 2 貝葉斯網絡診斷貝葉斯網絡的診斷是指從結果推測一個起因的推理 也稱為由底至上的推理 目的是在已知結果時 找出產生該結果的原因 已知發生了某些結果 根據貝葉斯網絡推理計算造成該結果發生的原因和發生的概率 該診斷作用多用于病理診斷 故障診斷中 目的是找到疾病發生 故障發生的原因 15 3 貝葉斯網絡學習貝葉斯網絡學習是指由先驗的貝葉斯網絡得到后驗的貝葉斯網絡的過程 先驗貝葉斯網絡是根據用戶的先驗知識構造的貝葉斯網絡 后驗貝葉斯網絡是把先驗貝葉斯網絡和數據相結合而得到的貝葉斯網絡 貝葉斯網絡學習的實質是用現有數據對先驗知識的修正 貝葉斯網絡能夠持續學習 上次學習得到的后驗貝葉斯網絡變成下一次學習的先驗貝葉斯網絡 每一次學習前用戶都可以對先驗貝葉斯網絡進行調整 使得新的貝葉斯網絡更能體現數據中蘊涵的知識 貝葉斯網絡的學習關系如圖7 2所示 圖7 2貝葉斯網絡持續學習 16 貝葉斯網絡模型是由網絡結構和條件概率分布表 ConditionalProbabilityTable CPT 組成的 因此 必須通過給出貝葉斯網絡的網絡結構及每個結點上的CPT表來描述一個貝葉斯網絡 相應地 基于貝葉斯網絡的學習包括結構學習和參數學習兩個內容 結構學習 即利用訓練樣本集 盡可能結合先驗知識 確定最合適的貝葉斯網絡模型結構 參數學習是在給定結構下 確定貝葉斯網絡模型的參數 即每個結點上的CPT表 按照學習的目的以及訓練樣本集是否完整 可以把學習方法歸為以下幾類 如表7 1所示 表7 1貝葉斯網絡學習算法分類表 17 7 4貝葉斯網絡的預測 診斷和訓練算法本節將從圖7 1所示的簡單貝葉斯網絡的例子人手 分別介紹貝葉斯網絡的預測 診斷和訓練算法 假定網絡中的概率和條件概率都已經知道 也就是說網絡已經訓練完畢 這些數據給出如下 7 4 1概率和條件概率數據圖7 1中的Party和BrainTumor兩個結點是原因結點 沒有連線以它們作為終點 首先給出這兩個結點的無條件概率 如表7 2所示 表7 2中的第二列是關于Party 參加晚會 的概率 參加晚會的概率是0 2 不參加晚會的概率是0 8 第三列是關于患腦瘤的概率 患腦瘤的概率是0 001 不患腦瘤的概率是0 999 下面還將給出幾組條件概率 分別是PT已知的情況下HO的條件概率 如表7 3所示 HO已知的情況下SA的條件概率 如表7 4所示 BT已知的情況下PX的概率 如表7 5所示 表7 2結點PT BT的無條件概率分布 18 上面三個表的結構相似 給出的都是條件概率 表7 3中第2列的意思是 當參加晚會后 宿醉的概率是0 7 不宿醉的概率是0 3 第3列的意思是 當不參加晚會后 不會發生宿醉的情況 對表7 4和表7 5的解釋類似 表7 3已知結點PT時HO的條件概率 19 最后給出的是一個聯合條件概率 已知HO和BT時HA的概率 如表7 6所示 表7 6已知HO和BT時HA的概率 當沒有宿醉但患有腦瘤的情況下 頭疼的概率是0 9 不頭疼的概率是0 01 B 當宿醉發生和有腦瘤的情況下 頭疼的概率是0 99 不頭疼的概率是0 01 當宿醉發生但沒有腦瘤的情況下 頭疼的概率是0 7 不頭疼的概率是0 3 表7 6中數據的意義是 20 貝葉斯網絡的功能之一就是在已知某些條件結點的情況下 預測結果結點的概率 當然 貝葉斯網絡也可以在不知任何結點信息的情況下計算某個結果結點的發生概率 例如 在圖7 1中 如果不知道任何結點發生與否的信息 仍然可以估算結點HA的概率 為了方便 約定 對于一個結點Point P Point 表示Point發生的概率 P Point 表示不發生的概率 例7 1 下面計算結點HA的概率 根據全概率公式 有P HA P BT P H0 0 99 P BT P H0 0 9 P BT P H0 0 7 P BT P H0 0 02 0 116P HA 1 P HA O 884也就是說 在沒有任何結點信息 稱為證據 的情況下 頭疼的概率是0 116 不頭疼的概率是0 884 用同樣的方式 可以計算所有結點的概率 這樣可以使得圖7 1所示的網絡進一步完善 事實上 完善結點概率也是預測貝葉斯網絡預測的一種情況 即在不知結點明確信息 證據 情況下的預測 下面進行一個原因結點明確情況下的預測 7 4 2貝葉斯網絡的預測算法 21 例7 2 計算已知參加晚會的情況下 第二天早晨呼吸有酒精味的概率 首先 由表7 3可以看出 當PT發生時 HO發生的概率是0 7 也就是說 當參加晚會后 宿醉發生的概率是0 7 不發生的概率是O 3 由全概率公式P SA P H0 P SA H0 P H0 P SA H0 O 7 O 8 0 3 0 1 O 59 22 例7 3 計算已知參加晚會的情況下 頭疼發生的概率 由表7 3可知 當PT發生時 HO發生的概率是0 7 不發生的概率是0 3 由表7 2可以看出 BT發生的概率是0 001 不發生的概率是0 999 已知HO和BT后 根據全概率公式 得到P HA P H0 P BT P HA H0 BT P H0 P BT 0 7 P HO P BT 0 9 P HO P BT 0 02 0 7 0 001 0 99 0 7 0 999 0 7 0 3 0 001 0 9 0 3 0 999 0 02 0 496467P HA l P HA 0 503533也就是說 如果知道已經參加了晚會 而沒有其他方面的任何證據 則這個人頭疼的概率是0 496 不頭疼的概率是0 504 B 23 讀者可以比較分析例7 1和例7 3的結果 由于參加晚會 頭疼發生的概率大大增加了 結合上面給出的三個例子 下面給出貝葉斯網絡預測算法的步驟描述 如下所示 輸入 給定貝葉斯網絡B 包括網絡結構m個結點以及某些結點間的連線 原因結點到中間結點的條件概率或聯合條件概率 給定若干個原因結點發生與否的事實向量F 或者稱為證據向量 給定待預測的某個結點t 輸出 結點t發生的概率 1 把證據向量輸入到貝葉斯網絡B中 2 對于B中的每一個沒處理過的結點n 如果它具有發生的事實 證據 則標記它為已經處理過 否則繼續下面的步驟 3 如果它的所有父結點中有一個沒有處理過 則不處理這個結點 否則 繼續下面的步驟 4 根據結點n的所有父結點的概率以及條件概率或聯合條件概率計算結點n的概率分布 并把結點n標記為已處理 5 重復步驟 2 4 共m次 此時 結點f的概率分布就是它的發生 不發生的概率 算法結束 需要注意的是 第 5 步的作用是使得每個結點都有被計算概率分布的機會 24 根據條件概率公式P BT PX P PX BT P BT P PX 0 98 0 001 0 011 0 08909P BT PX l P BT PX 0 91l也就是說 當X光檢查呈陽性的情況下 患腦瘤的概率是0 089 不患腦瘤的概率是0 911 7 4 3貝葉斯網絡的診斷算法 本部分將做相反方向的工作 在已知結果結點發生與否的情況下推斷條件結點發生的概率 例7 4 計算已知X光檢查呈陽性的情況下 患腦瘤的概率 由 P AB P A B p B 得到 P A B P AB P B 而 P AB P B A P A 所以 P A B P AB P B P B A P A P B 上面的例子比較簡單 可以直接用條件概率公式計算獲得 下面再看一個比較復雜的例子 先驗概率 25 例7 5 計算已知頭疼的情況下 患腦瘤的概率 首先 根據表7 6給出的聯合條件分布計算已知BT情況下HA的邊緣條件概率 為此 要首先計算結點HO的概率分布 根據表7 3和全概率公式P HO P HO PT P PT P HO PT P PT 0 7 0 2 0 0 14 上面的計算表明 沒有任何證據的情況下 宿醉發生的概率是0 14 不發生的概率是0 86 通過宿醉的發生概率 可以計算已知BT情況下HA的邊緣條件概率 26 最后 根據表7 7提供的條件概率 利用條件概率公式 可得P BT HA P HA BT P BT P HA 0 9126 0 001 0 116 0 007867 P HA BT P HO P HA BT HO P HO P HA BT HO 0 14 0 99 0 86 0 9 0 9126P HA BT 1 P HA BT 0 087上面的計算得到了已知患腦瘤的情況下頭疼的概率是0 913 不頭疼的概率是0 087 這個條件概率是一個邊緣分布 它是從聯合條件概率分布 H0 BT HA 去掉一個條件HO得到的 我們把這個邊緣分布的內容整理在表7 7中 B 表7 6 表7 7已知BT情況下HA的 邊緣 條件概率 全概率公式 27 例7 4和例7 5分別從簡單和復雜兩種情況進行了貝葉斯網絡的診斷示例 下面的部分將介紹同時具有預測功能和診斷功能的算法 根據上面的兩個例子 可以總結出貝葉斯網絡診斷算法的一般步驟 如下所示 輸入 給定貝葉斯網絡B 給定若干個結果結點發生與否的事實向量F 或者稱為證據向量 給定待診斷的某個結點t 輸出 結點t發生的概率 1 把證據向量輸入到貝葉斯網絡B中 2 對于B中的每一個沒處理過的結點n 如果它具有發生的事實 證據 則標記它為已經處理過 否則繼續下面的步驟 3 如果它的所有子結點中有一個沒有處理過 則不處理這個結點 否則 繼續下面的步驟 4 根據結點n的所有子結點的概率以及條件概率或聯合條件概率計算結點n的概率分布 并把結點n標記為已處理 5 重復步驟 2 4 共m次 此時 原因結點t的概率分布就是它的發生 不發生的概率 算法結束 需要注意的是 第 5 步的作用是使得每個結點都有被計算概率分布的機會 28 例7 6 計算已知參加晚會并且第二天早上呼吸有酒精味的情況下 宿醉的發生概率 由于已知參加了晚會 PT 那么根據表7 3 宿醉發生的概率是0 7 不發生的概率是0 3 根據全概率公式P SA P SA HO P HO P SA HO P 一HO 0 8 0 7 0 1 0 3 0 59這個結果就是已知參加晚會的情況下 有酒精味的發生概率 再利用條件概率公式 可得P H0 SA P SA HO P HO P SA 0 8 0 7 0 59 0 94915這是最終的結果 也就是說 當參加晚會并且第二天早晨有酒精味的情況下 宿醉發生的概率是0 949 從上面的計算過程可以總結出解決這類綜合問題的一般思路 首先 要把原因結點的證據 此例中是 PT 進行擴散 得到中間結點 HO 或結果結點 SA 的概率分布 最后根據條件概率公式計算中間結點的概率分布 7 4 4貝葉斯網絡預測和診斷的綜合算法 利用貝葉斯網絡進行單純的預測或進行單純的診斷的情況是比較少的 一般情況下 需要綜合使用預測和診斷的功能 29 這是解決預測和診斷綜合問題的一般思路 下面將給出一個更復雜的綜合問題的例子 例7 7 計算在已知有酒精味 頭疼的情況下 患腦瘤的概率 首先 由條件概率公式可以計算在有酒精味的情況下宿醉的發生概率P H0 SA P SA HO P HO P SA 0 5656然后 由全概率公式可以計算患腦瘤的情況下頭疼的發生概率 當然 這時宿醉的概率已經是0 5656 它參與了下面的運算 P HA BT P HA BT HO P HO P HA BT 一HO P 一HO 0 99 P HO 0 9 P 一HO 0 9509最后 再由條件概率公式可以計算患腦瘤的概率P BT HA P HA BT P BT P HA 0 9509 0 001 0 4052 0 002347可以比較例7 7和例7 5的計算結果 例7 7中計算得到的患腦瘤的概率要相對小一些 同樣患有頭疼 兩個例子中患腦瘤的概率是不一樣的 這是因為 例7 7中的結果結點 有酒精味 發生 這意味著頭疼的原因有更大的可能是因為宿醉 而不是患腦瘤 除了上面的7個例子外 讀者可以試著解決圖7 1所示貝葉斯網絡中更復雜的例子 或者解決本章后面的習題 30 7 4 5貝葉斯網絡的建立和訓練算法本章前面各節所進行工作的前提是假設貝葉斯網絡已經建立 有了結點和連線 原因結點的概率分布已經確定 并且有連線結點間的條件概率也已經確定 那么 如何建立一個貝葉斯網絡呢 要建立貝葉斯網絡 首先要把實際問題的事件抽象為結點 這些結點必須有明確的意義 至少有是 非兩個狀態 或者有多個狀態 并且這些狀態在概率意義上是