二元決策系統
概述
知識獲取是構造專家系統的“瓶頸”問題, 而專家知識的好壞將直接影響整個系統的性能。歸納學習能從大量分散的事實和蘊含規律的數據中歸納出一般規則, 是解決知識獲取問題的有效手段。但是許多專家系統要求計算機人員和領域專家的緊密合作, 並要求人工對專家知識進行編碼建立, 不僅效率低下, 而且要在不同的套用領域進行相同的工作。因此, 迫切需要建立一種歸納學習方法, 以便從一個精心選取的專家決策樣本集中自動歸納和提煉決策規則, 而與領域無關。
粗集理論是研究不完整數據及不精確知識的表達、學習、歸納的一套方法, 是以對觀察和測量數據進行分類為基礎, 通過對數據進行分析、近似分類、推理數據間的關係, 從中發現隱含的知識, 揭示其潛在的規律。首先將事例集表示為二元決策系統, 並將二元決策系統分解為多個單一二元決策子系統; 然後針對每一子系統提取出最能反映其特性的條件屬性簡約集, 得到簡化的子系統; 最後利用核與簡化的概念對子系統中的決策規則進行簡化,得到簡潔明了的決策規則集。
基於二元決策系統的粗集知識獲取方法
任何事例集都可表示為二元決策表形式,二元決策表便是旋轉機械故障診斷事例集的決策表表示。說明該事例含有此症狀(或屬於此類) ; 為0 則說明不含症狀( 或不屬於此類)。從決策表中提出決策規則主要有以下兩步:決策表中條件屬性的簡化, 即求取C 的D 簡約, 得到簡化的決策表。將事例集表示為二元決策系統, 然後將決策系統分解為多個單一二元決策子系統, 依據機率最佳簡約準則為每個子系統選出最能反映其特性的簡約屬性集, 為最終得到簡潔明了的決策規則提供了可能。 每個正例代表一條規則,。由於每條規則具有多種簡化形式,而且多條規則可能擁有相同的規則簡化形式, 求取所有簡化規則和最小簡化規則是相當複雜的, 在屬性較多時也是不可能的。為此提出一種機率最小規則準則, 在計算出每條決策規則的核屬性的基礎上,依照它選擇相應規則簡化形式, 能夠得出機率意義上的最小規則集。
決策表中的每個正例都代表一條規則, 如果將各屬性在所有正例中屬於核屬性的頻度P i( i = 1, 2, , n) 作為該屬性的規則重要度, 以任一條規則的核屬性為起點, 依次添加出現規則重要度較大的其它屬性, 便可能得到覆蓋更多正例的規則簡化形式, 從而使最終得到的規則數目較小。這種最小數目的決策規則是機率意義上得到的, 稱為機率最小規則準則。
二元決策圖分析方法
概述
動態故障樹定性分析的目的是為了識別故障樹頂部事件失效的主要模式，找出導致故障發生的原因和規律，為潛在故障的診斷提供指導。對於動態故障樹，其頂部事件的發生不僅與基本事件有關，而且還依賴於基本事件的發生順序，因此動態故障樹的故障模式識別不能僅僅依靠割集的確定，更應找出基本事件的順序失效關係，即割序。割序是導致動態故障樹頂部事件發生的基本事件序列，當順序表達式中任意去掉一個基本事件時，這些順序表達式不能形成割序，則稱這類割序為最小割動態故障樹定性分析的目的是為了識別故障樹頂部事件失效的主要模式，找出導致故障發生的當前用於動態故障樹定性分析的方法主要有原因和規律，為潛在故障的診斷提供指導。對於動 馬爾科夫法、代數法和有序二元決策圖法（Se－態故障樹，其頂部事件的發生不僅與基本事件有 ），而且還依賴於基本事件的發生順序，因此動態 三種方法都存在一定的不足。馬爾科夫法在對大故障樹的故障模式識別不能僅僅依靠割集的確定， 規模故障樹進行定性分析時，會出現狀態組合爆炸更應找出基本事件的順序失效關係，即割序。割序 的問題，限制了其在複雜故障樹中的運用。基於代是導致動態故障樹頂部事件發生的基本事件序列， 數框架的動態故障樹分析方法計算過程複雜，不適用與大規模的故障樹分析。有序二元決策圖方法適用於大規模複雜動態故障樹的定性分析，但是受動態故障樹向有序二元決策圖轉換方法的影響，使得轉換後的有序二元決策圖存在冗餘節點和規模過大等問題，降低了動態故障樹定性分析的效果。為了提高大型、複雜動態故障樹定性分析的效率和效果，本次研究將對基於有序二元決策圖的動態故障樹定性分析方法進行研究，重點對動態故障樹向有序二元決策圖轉換的方法進行最佳化，提出一種基於成分組合法的逆向轉換法。
相關概念、知識
1.時序邏輯的關係符號
為了分析動態門中基本事件的順序失效關係，引入時序邏輯符號，主要包括優先關係符號和同時關係符號。
1）優先關係
時序邏輯的優先關係用“”表示，表示左面的事件先於右面事件發生，如 AB表示 A事件先於B事件發生。
2）同時關係
同時關係用“”表示，表示是左面的事件和右面的事件同時發生，如A～B表示事件A、B同時發生。
2.有序二元決策圖的結構
二元決策圖本質是布爾邏輯函式的圖形表示，即用有向的二叉樹圖來表示布爾邏輯函式。主要由根節點、非終結點、終結點組成。非終結點的狀態分為兩種，0表示基本事件工作正常，1表示基本事件工作異常。同樣，終結點狀態也分為兩類：系統工作正常和系統工作非正常，分別用0、1表示。有序二元決策圖是對二元決策圖的拓展，在二元決策圖的基礎上引入了有序性的條件限制，其核心思想將時間動態關係用時序邏輯表達式替換，並將其看作布爾邏輯變數。
3.基於有序二元決策圖的動態故障樹定性分析的步驟
1）對動態故障樹進行預處理，包括故障樹結構的規範化、化簡和模組化；
2）將動態故障樹中的動態門用時序邏輯表達式進行描述替換；
3）將動態故障樹轉換為有序二元決策圖，然後對有序二元決策圖進行遊歷，找到動態故障樹的割集和割序集，從而確定最小割集和割序集。
動態門的時序邏輯描述
1.優先與門的時序邏輯描述
優先與門的符號如圖2所示，只有當基本事件A、B都發生，並且事件A先於事件B發生時，輸出事件才會發生。根據其功能，採用優先關係符號對優先與門基本事件的時序關係進行描述，當輸出事件發生時，有：AB。
2.順序門的時序邏輯描述
順序門的符號如圖3所示，當順序門所有的基本事件按照從左到右的順序發生時，輸出事件才會發生。順序門與優先與門不同之處在於，優先與門允許基本事件按照任意的時序發生，而順序門的基本事件發生必須遵循預定的時序發生。根據順序門的功能和定義，採用優先關係符號對其時序邏輯關係進行描述，對於圖3，當輸出事件發生時，有A→A2→→An
3.功能門的時序邏輯描述
其輸入事件由一個觸發事件T和多個相關的基本事件A、B、C組成。功能門的基本事件既可以發生獨立失效，也可以由觸發事件強制基失效，根據其功能關係，採用同時關係對功能門的時序關係進行描述，當基本事件A發生時，有A+AT。同理，當事件B、C失效時，有B+BT；C+C～T
4.不含公用備件的備件門時序邏輯描述
1）冷備件門
冷備件門的輸入事件由一個主事件和多個儲備事件構成，如圖5所示，其中事件A為主事件，事
件B、C為冷儲備事件。儲備事件不能先於主事件而失效，並且儲備事件必選按照先後順序依次失效，因此選擇優先關係對其時間邏輯關係進行分析，其代數描述為：ABC。
2）溫備件門
溫備件門結構如圖6所示，其儲備事件在儲備期間也能失效，但是儲備期間失效的機率與工作狀態下失效機率不同（通常為正常工作失效機率的倍，01）。對於儲備事件B，用B表示事件在激活狀態失效，用B表示事件在儲備期間失效。根據溫備件門輸出事件發生的原因，採用優先關係運用以下方法對圖6的溫備件門時序邏輯關係進行代數描述：
運用排列組合方法，產生3！=6種事件A、B、C的排列，分別為A→B→CA→C→BB→A→CB→C→AC→B→AC→A→B
判斷儲備事件（設為B）失效處於的時間範圍，若在儲備期失效則用B代替B，否則則用B代替B，因此得到溫備件門的代數描述為
A→Ba→CaA→Cd→BaBd→A→CaBd→Cd→ACd→Bd→ACd→A→Ba
熱備件門
熱備件門的結構如圖7所示，其儲備事件在儲備期間和激活狀態下的失效機率相同，即=1。對於儲備事件B，有B=B=B，因此將溫備件門中的B、B用B替換，即得到熱備件門的時序邏輯表達式：
A→B→C+A→C→B+B→A→C+B→C→A+C→B→A+C→A→B
5.含公用備件的備件門時序邏輯描述
1）含公用備件的溫備件門討論2個溫備件門公用一個儲備事件的情況，如圖8所示，儲備事件C只能被其中一個溫備件門使用，到底被哪個備件門使用取決與事件ABC發生的時間。當第一個溫備件門的輸出事件發生時，有A→Ca+Cd→A+B→A同理，當第二個備件門的輸出事件發生時，滿足B→Ca+Cd→B+A→B的時序邏輯關係當nn>2個備件門公用一個儲備事件時，用X表示每個溫備件門的主事件（i=1，2，3…n），公用備件用T表示，則當第i個溫備件門的輸出事件發生時。
2）含公用備件的冷備件門
冷備件門的儲備事件不能在儲備期失效，對於含公用備件的冷備件門，只需考慮備件在激活期失效，因此將含公用備件溫備件門的儲備期失效邏輯刪除即可得到含公用備件冷備件門的時序邏輯表達式。對於n個冷備件門公用一個儲備事件時，用X表示每個冷備件門的主事件（i=1，2，3，…，n），公用備件用T表示。
3）含公用備件的熱備件門
對於含公用備件的熱備件門，其時序邏輯與含公用備件的溫備件門相似，因此將儲備事件（假設為C事件）的失效狀態統一替換為C。對於當nn>2個熱備件門共同使用一個儲備事件時。
動態故障樹向有序二元決策圖轉換方法的研究
當前動態故障樹向有序二元決策圖轉換的方法主要有方法和成分組合法。採用基於方法對動態故障樹進行轉換時，首先要對故障樹中底部事件排序，排序結果將直接影響轉換後的有序二元決策圖的規模與計算效率，而底事件的排序過程是一個NP問題，儘管國內外有很多學者對底部事件排序的問題進行了探討，並提出一系列的排序規則和方法，但是這些方法不具有通用性，不能夠勝任任何故障樹的底事件排序問題。相對於ite方法，成分組合法避免了底部事件排序的問題，但是由於成分組合法在處理具有重複底部事件的故障樹時可能會產生冗餘邏輯，並且在融合兩個二元決策圖分支時，需要確定主二元決策圖。針對這些不足，在成分組合法的基礎上提出一種將動態故障樹轉換為有序二元決策圖的逆向轉換法。
1.逆向轉換法的理論基礎
將動態故障樹轉換為有序二元決策圖的依據是兩者在結構和邏輯關係上具有一一對應的關係。逆向轉換法採取自上而下層層分解的方法，避免了選擇主二元決策圖的問題，其構建有序二元決策圖的過程可以看作成分組合法的逆向過程，該方法的實現是基於與門、或門的轉換規則：
2.逆向轉換法的步驟、規則逆向轉換法的步驟：
將動態故障樹頂部事件轉換為有序二元決策圖的根節點，相應的輸入事件轉換為非終結點，按照與門、或門的轉換規則進行連線，構建第一層邏輯門的有序二元決策圖結構。子節點的置換。根據動態故障樹的結構，將轉換後的有序二元決策圖的節點用其子節點行替代。將動態故障樹層層分解，直到所有的底部事件都包含在有序二元決策圖中，最終構造出完整的有序二元決策圖。為了保證故障樹和有序二元決策圖的邏輯一致性，在子結點置換的過程中，遵循以下的原則：
1）若替換的節點為與門結構，則子節點間以“1”分支連線，被替換節點的上一個節點按照原結構與替換結構的第一個節點連線，被替換節點的下一個節點則按照原結構與替換結構的所有子節點連線。
2）若替換的節點為或門結構，則子節點間以“0”分支連線，被替換節點的上一個節點按照原結構與替換結構的第一個節點連線，被替換節點的下一個節點則按照原結構與替換結構的所有子節點連線。
3）在將每一層故障樹結構進行轉換時，當存在靜態基本事件和動態時序邏輯表達式時，優先將靜態基本事件的節點排在靠上的層次；當只存在靜態的基本事件時，優先將子事件個數少的節點排在靠上的層次。
3.逆向轉換法的化簡規則
動態故障樹中重複事件的存在有以下三種情況：
1）靜態門間的基本事件中存在重複事件；
2）動態門間共用同一個基本事件；
3）靜態門和動態門間存在重複的基本事件。當重複事件存在時，利用逆向轉換法對動態故障樹進行轉換後可能出現冗餘的邏輯結構，不利於動態故障樹割集/割序的計算，因此為了減少轉換後的有序二元決策圖中的冗餘結構，在每次邏輯門轉換的過程中，對有序二元決策圖的邏輯結構進行化簡，其化簡規則如下：
如果一個節點的0、1分支指向的結構完全相同，那么該節點的信息對有序二元決策圖的結構無影響，應刪除。在有序二元決策圖的一條路徑上，一個節點首次的狀態規定了該路徑上所有相同節點的狀態，如果出現的相同節點的狀態與首節點的狀態相同，則刪除重複節點；如果出現的相同節點的狀態與首節點狀態不同，則該節點以後的所有節點均可以刪除替換過程中，若替換的子節點與其下層的非終結點構成封閉的圖形，且封閉圖形的最高層頂點能通過“”分支到達最底層的節點，則刪除頂點到最底層節點間的由“”、“”支線組成的路徑的最後兩個節點間的連線。當封閉圖形被打破時，其節點狀態的確定會影響有序二元決策圖分析結果的正確性，根據SBDD的邏輯結構，當由非終結點構成的封閉圖形被打破時，關於節點狀態的確定有以下規則：
當封閉圖形最上層端點在下一層節點的子路徑出現時，重複節點的狀態不受替換節點狀態的影響。若X節點後再次出現節點X時，節點X的狀態不受第一個X的影響，可以將其看作首次出現。
當封閉圖形最上層端點也是動態門的基本事件時，遊歷有序二元決策圖時，在得到該動態門割序的基礎上，加上該節點。），注意到動態門的輸入事件 為重複事件，並且為原封閉結構圖形的頂點。
二元決策套用實例
對捷運施工安全風險分析
由於我國的捷運建造的起步較晚，相關技術方面還不夠成熟，所以近十幾年來，捷運建造事故頻發，造成嚴重的經濟財產損失。引起事故發生的因素是多方面的，包括人員、環境、材料和設備等因素。故障樹分析是一種較為傳統的方法，當風險因素較多時，無法高效地得出定量分析結果，而 BDD 結構的出現，能有效解決組和爆炸問題。
故障樹分析方法的套用
故障樹分析（Fault Tree Analysis-FTA），就是對可能引發事故安全風險的因素進行分析，繪出邏輯框圖，從而確定各因素的組合方式以及發生機率。故障樹的繪製是關鍵，會直接影響分析結果。（T：捷運隧道豎井基坑圍護結構失穩；A1：勘察問題；A2：設計失誤；A3：施工問題；A4：降水問題；B1：施工不當；B2：降水失效；x1：勘察數據有誤；x2：勘察資料不詳；x3：設計荷載取值不當；x4：土體強度指標失真；x5：未嚴格依照規範設計；x6：計算失誤；x7：施工管理不嚴；x8：未及時支護；x9：棄土位置不當；x10：支護結構底端插入深度不足；x11：卸載速度過快；x12：降水速度過快；x13：地下管道滲漏水；x14：設備故障；x15：無備用設備）樹根代表頂事件（T），表示基坑圍護結構失穩；樹葉是底事件（X），亦稱基本事件,用圓形框表示；樹幹是中間事件（A、B），用矩形框表示。“or”、“and”分別代表邏輯“或”、“與”，算法分別對應“加”“、乘”。將各分式代入T 的表達式，為T=X+X+X+X+X+X+X·X+X·X+X·X+X·X+X+X·X+X；定性分析的目的就是找出故障樹的全部最小割集，上式共 13 項，即共有 13 種引發危險的事件組合。以V 表示底事件（基本事件）的重要程度，；也就是說，底事件（基本事件）X 、X、X、X、X、X、X、X引發頂事件發生的可能性較大，需要多加注意。
基於二元決策圖的安全風險評估
為提高故障樹分析效率、降低計算複雜度，BDD（Binary Decision Diagram）被引入了安全體系中的故障樹分析。BDD 是一種描述布爾函式的有向無環圖，由 Lee 在 1959 年發明；1978 年，Aker 明確提出了 BDD 的概念；1993 年 Rauzy 首先提出把故障樹轉換成二元決策圖，並用於系統可靠性分析。此後，Andrews 對這種方法做了進一步論述, 針對大型故障樹分析所面臨的組合爆炸問題，通過遍歷 BDD 獲得割集進行故障樹分析。
建築施工安全風險事故率和基本事件重要度兩項指標是評估施工安全風險的重要參數，而這兩項數據的計算是建立在故障樹及其 BDD 結構的基礎之上。下面我就計算過程作出解釋。
