基于混合蟻群關聯規則挖掘的危險源分析算法

佘雅莉，周 良

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

0 引 言

在民用航空空中交通安全管理體系中，危險源識別和風險評估是重要的組成部分。對危險源進行詳細地分析并得到其產生的原因和作用機理，是相關部門對風險進行有效準確評估的前提。在傳統的危險源分析體系中，使用事件樹分析法、蝶形分析法、危險與可操作性分析法進行危險源的分析；現在，國內外專家和學者提出了很多不同的分析方法，但大都在傳統的分析體系上建立。Katrina Groth等提出了一種混合的分析方法，將事件樹、故障樹和事件序列圖相結合對危險源中決定性因果路徑進行分析[1]，并利用貝葉斯網絡對非決定性因果關系進行分析；Leon Purton等在蝶形分析法的基礎上[2]，引入技術完整性的概念，在危險鏈中引入技術生命周期：設計、生產和維護。這些方法可以從不同的側面對危險源的原因進行分析，但是缺乏全面性。為此，需要一種能夠較全面且客觀分析危險源的方法。

危險源原因分析的過程就是在危險源數據庫中找到不安全事件X，使得X與危險源Y之間滿足X→Y的蘊涵關系。根據關聯規則的定義可知，這恰恰就是在危險源數據庫中對危險源與不安全事件進行關聯規則挖掘的過程，因此可以借助關聯規則挖掘實現對危險源的原因分析。關聯規則挖掘是數據挖掘中的一個重要領域，它能夠發現數據庫中項目之間的隱含關系。自1993年被提出后，人們提出了很多相關算法，這些算法通過發現數據庫中的頻繁項目集來發現關聯規則[3]。Apriori算法[4]、頻繁模式樹算法[5]等都是傳統的經典關聯規則挖掘算法，但它們存在頻繁掃描數據庫、產生大量候選集等不可避免的缺陷。因此，許多改進算法被提出。例如，Du等[6]提出了一種改進的Apriori算法，通過重構數據庫中的數據，增強項目集之間的聯系，使得算法能夠直接通過剪枝操作得到候選集，從而減少對候選集的驗證過程。不僅如此，具有較高搜索效率的群智能算法也被應用到關聯規則的挖掘中，Jitendra Agrawa等利用基于集的粒子群優化算法挖掘數據庫中的正關聯規則和負關聯規則[7]；Zhou等將粒子群優化算法與引力搜索算法相結合挖掘關聯規則[8]；文獻[9]提出結合遺傳算法和蟻群算法進行關聯規則挖掘，其中心思想是利用遺傳算法優化蟻群算法的參數。該方法確實取得了較好的性能，但是蟻群算法的初始信息素濃度仍然沒有確定，使螞蟻在初始時刻沒有方向，消耗較多時間。

隨著混合智能算法的興起，加上蟻群算法易于與其他算法結合的特點，文中設計了一種基于混合蟻群關聯規則挖掘的危險源分析方法。在該方法中將危險源事務數據庫進行預處理，轉換為一個二進制矩陣，利用粒子群挖掘出定量的頻繁項集，從而確定蟻群的初始信息素濃度，進而進行最大頻繁項集挖掘，并由最大頻繁項集產生強關聯規則，分析危險源原因。

1 HA-MACR算法總體思路

在國際民航組織安全管理手冊和國內民航空中交通管理安全管理體系(SMS)建設指導手冊中，危險源的原因分析都是對不安全事件的分析，在人為因素分析的基礎上，對不安全行為、不安全行為的前提條件、設備設施、監督管理和組織因素等方面進行分析。關聯規則有如下定義：設I={i1,i2,…,in}是一個項目集，事務數據庫為D，事務數據庫中的每個事務T都是項目集的一個子集T?I，關聯規則具有如下形式X→Y，其中X?I，Y?I并且X∩Y=?。由定義可以看出，關聯規則就是發現事務數據庫中項目的隱含模式，當某些項目X出現時，另一組項目Y也會同時出現。這個過程可以與危險源的原因分析相結合，因此，文中提出利用關聯規則分析危險源原因。

HA-MACR算法將該分析過程分為3部分：一是危險源狀態信息預處理過程；二是挖掘最大頻繁項集；三是產生強關聯規則從而得到導致危險源的不安全事件。關聯規則挖掘過程主要分為兩個步驟——發現頻繁項目集和產生強關聯規則[10]。其中，發現頻繁項目集是關鍵，對算法的性能有著決定性的影響，故考慮在該步驟進行優化。于是，在第二步中先由粒子群找出固定數量的頻繁項集，從而確定蟻群算法的初始信息素濃度，以期改善單純用蟻群算法進行挖掘的盲目性，再利用蟻群算法挖掘最大頻繁項集。整個算法流程如圖1所示。

圖1 HA-MACR算法流程

1.1 數據預處理

算法開始前，需要對原始數據進行預處理，將其轉換為一個二進制矩陣。在危險源原因分析中，給定事務數據庫為包含危險源和不安全事件的危險源事務數據庫，將其記作D。在預處理階段，將D中每條記錄轉換成0-1向量，這樣便于計算支持度與置信度，同時可以提高數據庫掃描速度。下面以圖2為例具體解釋轉換方法。圖2左邊是原始數據，共有4條記錄，可以看出數據庫中共有五個項目集，向量長度為5。以T1為例，它包含I1，I2和I5，因此，I1，I2和I5對應位置置1，I3和I4對應位置置0。以此類推，最終構成一個4行5列的二進制矩陣。

圖2 數據預處理

1.2 信息素初始濃度確定

蟻群算法的參數確定一直是其應用中需要解決的一個問題，尤其是初始信息素濃度的設置對算法性能有著重要影響。為了在一定程度上避免盲目性和提升搜索效率，HA-MACR算法首先借助粒子群的更新迭代，得到一定量的頻繁項集，從而更合理地設置本算法的初始信息素濃度。將項集看作粒子群中的粒子，對應于數據預處理后的二進制矩陣，把粒子位置設為0-1向量。隨機生成粒子的初始位置和速度，但需要注意的是，必須保證粒子代表的項集是頻繁的，若不是則需要重新生成。

綜合考慮頻繁項集的項目個數和支持度計數兩個因素，粒子的適應度函數設計如下：

(1)

其中，|x|為粒子向量維數，即對應項集的項目個數；count(x)表示該項集的支持度計數；參數W1、W2分別用于控制這兩個因素對于適應度函數的影響程度。

由于粒子群算法中每個粒子都有記憶功能，可以記憶自己從初始時刻到當前時刻適應度最好時的位置。個體極值就是粒子彼時的適應度函數值，而全局極值就是所有粒子個體極值中的最優值。按式1計算粒子適應度函數并更新粒子個體極值xpbest和全局極值xgbest。有了個體最優位置和全局最優位置，就可以更新t時刻粒子位置，公式為：

k2r2[xgbest(t)-xj(t)]

(2)

xj(t+1)=xj(t)+vj(t+1)

(3)

其中，vj(t)和xj(t)分別是第j個粒子迭代t次后的速度和位置；w是慣性系數，隨迭代次數增加而減?。籯1、k2是學習因子。

但是，這樣得到的位置不是0-1向量，所以還需要用式4進行轉換。

(4)

其中，r3為[0,1]之間均勻分布的隨機數；sig()為sigmoid函數。

重復上述過程，直至迭代結束或達到最大迭代次數，輸出所有xgbest(t)。由此計算危險源和不安全事件組成的項集中項集i、j同時被選擇的次數，即2-項集支持度計數，由此確定信息素初始濃度，如式5所示。

τij(0)=τmax-τmin+scij

(5)

其中，τmax和τmin分別表示信息素上限和信息素下限。

1.3 挖掘最大頻繁項目集

在上一階段，主要完成了對蟻群算法的初始信息素濃度的確定，接下來可以開始用針對危險源原因分析改進的蟻群算法挖掘關聯規則中的最大頻繁項目集。類似于用蟻群算法尋找最優路徑[11]的過程，用一個禁忌表(Tabu)存放螞蟻在后續搜索中不能選擇的數據項，用一個可選表(Allowed)存放它還可以選擇的數據項。初始時刻，將各個螞蟻隨機地置于不同數據項作為出發點，并將該數據項添加到存放已選數據項的集合fk中和禁忌表中。然后，計算出剩余所有可選數據項的概率轉移函數值，如式6所示，并據此選擇下一個項。

(6)

其中，τj(t)是t時刻的信息素濃度；ηj(t)為啟發函數。

τij(t)=(1-ε)·τij(t)+ε·Δτij(t)

(7)

(8)

(9)

若加入j后fk不是頻繁項集，則把j從fk中刪除，并根據式10決定是否繼續搜索。

(10)

其中，p是[0,1]上的隨機數；p0是[0,1]間的一定值。若stop(k)=1，則停止搜索；若stop(k)=0，將項目集j放入禁忌表并從allowed表中剔除后繼續搜索。當所有的螞蟻都完成了一次遍歷后，記錄本次遍歷所找到的最大頻繁項集。這樣就完成了一次迭代。

但是在下一輪迭代開始之前還有一項很重要的工作要做，那就是信息素的全局更新，這正是蟻群算法具有正反饋性的關鍵。螞蟻完成一次搜索后，對于本次迭代中最優頻繁項集中的點所構成的邊進行信息素更新[12-13]，方式如下：

(11)

1.4 產生規則

得到最大頻繁項集后，便可以很容易地產生其對應的強關聯規則，主要分為兩步：

(1)求出最大頻繁項集的所有非空真子集；

(2)設X、Y為步驟1中所得任意子集，若X∩Y=?且count(X∪Y)/count(X)≥min_conf，則有強關聯規則X→Y。

2 實驗結果與分析

實驗采用民航空管局安全管理系統的危險源事務數據庫，并按1.1節所述數據預處理過程進行二進制轉換。從算法運行時間和產生的規則質量兩個角度對算法進行對比實驗，實驗環境為Intel core i7 2.6 GHz Window7及MatLab 2014Ra。為了保證算法初始隨機性對結果的影響，取20次實驗的平均結果進行衡量。運行時間很好衡量，而規則質量，參考文獻[14]中對規則質量的計算方法，比值越大，質量越好。最終得到的危險源原因分析結果如表1所示。

表1 危險源原因分析結果

由于HA-MACR算法中有一些參數不確定，這些參數對算法性能有一定程度的影響，故在不同取值下分別對算法執行20次，選取平均結果較好的參數組合，實驗結果如表2所示。由結果可知，當α=2，β=1時，算法效果較好，故以下實驗將設為該值。

表2 參數組合

同時根據文獻[15-16]，算法其余參數設置如表3所示。

表3 參數取值

實驗比較了不同支持度下Apriori算法和HA-MACR算法的平均規則質量，結果如圖3所示?？梢钥闯?，HA-MACR產生的規則質量均較好。

圖3 規則質量比較

另外，實驗比較了不同支持度下Apriori算法和HA-MACR算法的平均運行時間，結果如圖4所示。可以看出，HA-MACR算法運行速度遠遠快于Apriori算法，而且Apriori算法隨支持度降低運行時間大幅上漲，變化很大，這是由于產生的候選項集增多引起的計算量增大。而HA-MACR算法由于先利用粒子群合理設置了信息素濃度，而后蟻群算法挖掘最大頻繁項集時也受到信息素的指導，所以不會出現這種情況，運行時間較穩定，即使支持度閾值設置得很小也不會出現運行時間劇增的情況。

圖4 運行時間比較

3 結束語

針對危險源原因分析中存在的分析主要依賴人的參與和傳統關聯規則挖掘算法中候選集過多影響挖掘效率的問題，提出了一種基于混合蟻群關聯規則挖掘的危險源原因分析算法HA-MACR。該算法通過引入粒子群優化蟻群初始信息素濃度，根據頻繁項集來確定，避免了蟻群算法初始時的盲目性，有效提高了危險源原因分析的效率與質量。實驗結果表明，該算法充分利用了蟻群優化算法的尋優能力和正反饋性，將其應用于對危險源原因的分析過程中，通過挖掘到的最大頻繁項集產生質量較好的關聯規則，進而得到分析結果，不僅提高了關聯規則的挖掘效率，同時也能有效提高危險源原因分析的準確性和執行效率。