基于FP-growth的大壩安全監測數據挖掘方法

毛寧寧,蘇懷智,高建新

(1. 河海大學水文水資源與水利工程科學國家重點實驗室,江蘇 南京 210098; 2. 河海大學水利水電學院,江蘇 南京 210098)

數據挖掘方法常應用于大壩安全監測數據的分析和處理。工程中常對變形、滲流、應力和裂縫開口等大壩安全監測資料進行整編和分析,挖掘數據之間的相關關系,以此評估大壩運行狀態,防止災害發生[1-2]。基于監測資料和壩工原理的統計模型也可分析其相關關系,但實際監測資料存在不連續、精確度低的情況,復相關系數低,且無法對比相似的影響因子或分析多因子耦合作用的影響[3]。

近年來,學者們對大壩安全監測數據挖掘方法展開了研究。蘇振華等[4]采用關聯分析方法對溫度數據進行深度挖掘,確定了溪洛渡大壩施工過程中冷卻通水的最高溫度。張海燕[5]基于關聯規則決策樹法進行了大壩安全監測數據挖掘,并利用上下游水位、降雨量、溫度等數據對壩頂沉降進行預測。王偉等[6]將大壩安全監控統計模型的求解轉換為多目標函數的優化,利用混合蛙跳算法同步確定調整系數和回歸系數,建立基于混合蛙跳算法的混凝土壩加權變形預模型。FP-growth算法是Apriori算法的延伸,阮志毅[7]將FP-Growth算法和空間多尺度剖分進行結合,提出一種頻繁項集的精確挖掘算法。顧軍華等[8]提出一種新的基于Spark的并行FP-Growth算法—BFPG,以提高算法的執行效率。劉沖等[9]提出的占用內存少、能滿足大型數據庫挖掘需求的改進的FP-growth算法,使挖掘速度大大提高,適合于大型數據庫的關聯規則挖掘算法。

在大壩安全監測數據中,變形量關乎大壩狀態是否穩定。大壩變形量受到包括水位因素、溫度因素、時效因素等影響,具有很強的非線性、隨機性[10-11]。本文基于關聯規則原理,應用改進的FP-growth算法,依據大壩安全監測數據,挖掘變形量與其影響因子之間的相關關系,分析大壩運行性態。實例結合梅山水庫的變形和環境量監測資料,利用此方法對數據進行橫向和縱向的比對,實現對各個影響因子進行綜合評價。

1 改進的FP-growth算法

1.1 關聯規則

關聯規則是數據挖掘方法之一,涉及2個基本概念:支持度、置信度。

a. 支持度(support):包含M且包含N的元組數占總元組數的比例,即項集A和項集B在數據庫中同時出現的概率:

(1)

式中:WM∪N為包含M且包含N的元組數;W為總元組數。

b. 置信度(confidence):包含M且包含N的元組數占包含M的元組數的比例,即含有項集M的事件中項集N同時出現的概率:

(2)

式中:WM為包含M的元組數。

關聯規則即根據給定的最小支持度Smin和最小置信度Cmin在事務數據庫W中找出的事物相關關系[12]。

1.2 改進的FP-growth算法

探索不同影響因子在數據庫中的重要程度,即是發現頻繁項集的過程,亦是對關聯規則中“支持度”的應用。FP-Growth算法建立在Apriori算法思想的基礎上,在挖掘頻繁模式的算法中應用最廣。算法采用一種緊湊的數據結構組織構成頻繁模式樹(Priority樹),通過壓縮方式存儲數據庫中的數據,并直接從Priority樹中提取頻繁項集[12]。

當數據庫總量大、事務集數目多或頻繁項集的數目大時,重復掃描降低了運行速度,同時在進行數據挖掘時難以抓住主次,找到有用的關聯規則。改進的FP-growth算法在計算過程中對數據庫進行剪枝,以提高計算效率。算法具體過程如下:

輸入:事務數據庫W;最小支持度;最小置信度。

步驟1:掃描數據庫W,以不小于Smin為條件找出頻繁項集,并得到其出現的次數計數m(或支持度),注意區別于FP-Growth算法,這一步無須產生候選項集。按照支持度遞減排列頻繁項集各項,得到頻繁項集集合L。設L={Im,Im-1,…,I1}(其中Im的支持度最高,I1的支持度最小)。

步驟2:將支持度小于Smin的項從各事務中刪除,再次掃描數據庫W,按照頻繁項集支持度遞減的次序重新排列各事務中的項,得到數據庫W′。

步驟3:根據L中的各項的支持度大小,按照以下規則由小到大依次構造各項數據庫子集,并利用FP-growth算法分別對其Priority樹分支進行約束頻繁項挖掘:掃描數據庫W′,從中提取所有包含項Ii(i=m,m-1,…,1)的頻繁項集,然后刪除這些事務中支持度小于該項的支持度的項集,所得事務集合便為項Ii的數據庫子集Wi;其次利用FP-growth算法對數據庫子集W′進行頻繁項集挖掘;最后構造該項的條件模式基,然后構造其條件Priority樹,在該條件Priority樹上挖掘出包含該項的頻繁項集CL,即完成在數據庫子集Wi上的約束頻繁項集的挖掘。

步驟4:當L中所有的項的約束頻繁項集CL被依次挖掘出來后,合并這些約束頻繁項集,即取這些約束頻繁項集CL的并集,便可得到數據庫W的所有頻繁項集,結束挖掘過程[9,12]。

2 基于改進FP-growth算法的大壩運行性態分析方法

2.1 數據預處理

大壩監測數據是不連續且無序的,計算前需對數據進行預處理。影響大壩變形的因素眾多,假定因變量Q為某大壩運行時期的某處變形量,基于以下自變量建立數據模型:水壓因子A、氣溫因子B、水溫因子C、時效因子D[13-15]。

2.1.1異常值處理

實際所得的大壩監測數據中,有些是連續的自動化監測值,有些是不連續的人工監測值,同時也存在數據缺失或數據異常的情況,如由于儀器損壞導致某一時間段內的測值缺失,或者測水溫或氣溫時,由于某種原因測值在某一時段出現異常等。本算法中采取忽略元組法,舍去自變量缺失或異常時間段內的所有數據。

2.1.2數據集成變換

數據集成變換能夠消除不同屬性的數值因大小不一而造成的計算偏差,將不同量級的數據縮放至同一數值區間,以便比較和處理。以自變量A為例,假定某特定時間段內數值的最大值Amax和最小值Amin為規范值,通過公式:

(3)

將自變量測值A(或者B、C、D)以及因變量Q的測值映射到區間[0, 1]區間。

2.1.3數據規約

數據規約可將復雜的數據庫簡化,分析和挖掘也能接近和保持原數據的完整性,并產生相同的分析結果[12]。

a. 采用離散化對數據進行規約:將給定的連續屬性值分區,采用式(4)將4個自變量A、B、C、D變換后的值再映射到區間[0, 10]區間:

A″=10A′-Q′

(4)

式中:A″的大小反映了自變量與因變量的離散程度。

b. 通過將屬性值域劃分為區間,用區間的標記替代實際的數據集:由“等距分箱”思想在某一時段對A″、B″、C″、D″取整數,數值相同的分為一類,則A可得到A0～A9不同項,B、C、D同理。選取某時段的數據,按照上述步驟進行數據預處理,每個時段即可得到集合{Ax、Bx、Cx、Dx},其中x為1～10的整數,由此生成數據庫K。

2.2 基于改進FP-growth算法的大壩安全監測數據挖掘步驟

具體挖掘流程見圖1,步驟如下。

圖1 改進的FP-growth算法流程

步驟1:參考大壩安全監測的資料,輸入合適的最小支持度、最小置信度,將已預處理的大壩監測數據庫K生成txt文件,導入改進FP-growth算法Python程序。

步驟2:利用Python程序對數據庫K進行掃描,根據不同監測數據與支持度的對比結果進行剪枝,得到新的數據庫K′,這一過程剪去出現幾率小于置信度的項集以及相關分支,即部分異常的數據。例如在實例中,由于讀數誤差造成的與平均值偏差較遠的水壓項A9、A8等在此步驟中被剪去。

步驟3:利用Python程序對數據庫K′進行掃描,構造Priority樹。

步驟4:對Priority樹進行關聯規則分析運算,挖掘大壩監測數據庫K′中頻繁項集以及強關聯規則。

從3個角度對運算結果進行分析論證:分析{Ax}、{Bx}、{Cx}、{Dx}的支持度,得出監測數據與單個環境量之間的關系;分析含{Ax,Bx}、{Ax,Cx}、{Ax,Dx}、{Bx,Cx}、{Bx,Dx}、{Cx,Dx}、{Ax,Bx,Cx}、{Ax,Bx,Dx}、{Ax,Cx,Dx}、{Ax,Bx,Cx,Dx}的支持度,得出監測數據與2個環境量耦合作用下的關系;分析含{Ax,Bx,Cx}、{Ax,Bx,Dx}、{Ax,Cx,Dx}、{Ax,Bx,Cx,Dx}的支持度,得出監測數據與3個環境量耦合作用下的關系。

3 工程實例

梅山水庫位于淮河支流史河上游的安徽省金寨縣境內,流域面積1 970 km2,于1954年3月動工,1956年4月竣工,是一座以防洪為主、結合灌溉、發電、航運、水產養殖等效益的多年運行的老壩。選取梅山水庫2012—2014年間3組環境量監測資料(上游水位、平均氣溫、平均水溫)以及位于壩頂的PL2測點(如圖2)在大壩橫截面方向(即上下游方向,簡稱X方向)的測值為基本資料進行分析。梅山大壩壩體水平位移監測采用垂線法,其測點的具體布置見圖2。

3.1 數據預處理

現有資料中測點PL2在X方向上的位移測讀頻率為一周一測,其余環境量測值為一天一測。其中上游水位缺少2012年3月22日—2012年4月4日2周的測值,PL2測點的位移監測數據缺少2013年9月26日和2014年3月27日2次測值。將相關時間段內的所有數據剔除,取余下時段中上游水位、平均氣溫、平均水溫一周測值的平均值與當周的位移測值,過程線見圖3和圖4。

3.2 數據集成變換與規約

按照前述步驟對數據進行數據預處理,得到數據集K,部分結果見表1(全部數據共153組)。表1中下標0～9表示各個自變量與因變量的離散程度。數字越小,表示此自變量與因變量有關的可能性較大;數字越大,表示自變量與因變量有關的可能性較小。

3.3 數據集掃描與剪枝

將數據集K生成txt文件,導入Python中,經過查閱相關資料和多次試驗,選取Smin=0.9,Cmin=0.1,對數據集K進行剪枝,生成新的書庫的K′。此時數據集K中的項目,如A5～A9、B3～B9、C3～C9被剪去,得到最終的事務集K′,部分結果見表2(全部數據共153組)。

3.4 構建Priority樹

由事務集K′帶入Python中運行算法,把A、B、C、D作為項,生成Priority樹,根據計算結果繪制的Priority樹見圖5。

圖2 梅山水庫水平位移正倒垂線(自動化和人工)測點布置

圖3 梅山水庫PL2測點位移與溫度過程線

圖4 梅山水庫PL2測點位移與上游水位過程線

Priority樹將上游水位、平均氣溫、平均水溫、時效4組復雜的數據與位移之間的關系梳理的簡明清晰。由Priority樹可知,B為Priority樹的主枝干,且B的計數比C多,說明與大壩變形量關系最密切的是B平均氣溫因子,其次是C平均水溫因子。再次,Priority樹中A上游水位因子與D時效因子計數相當,說明與B和C相比,其與位移之間的關系較不密切。

表2 梅山水庫數據集K′(部分)

圖5 梅山水庫運算結果Priority樹

3.5 頻繁項集及其支持度

得到Priority樹之后,利用python程序計算各個項集的支持度,得到的所有項集及其支持度見表3。

由表3可知,在含有2個因子的項集中,頻繁項集{B，C}支持度為82%,其次是頻繁項集{A，B}支持度為78%,再次之是頻繁項集{C，D}支持度為70%,說明當2項因子耦合作用的情況下,氣溫因子和水溫因子的耦合作用,是導致大壩變形的主要原因,而氣溫因子和上游水位交互作用,以及水溫因子與時效因子交互作用對大壩變形也有很大的影響。同樣,不經過頻率分析,通過對Priority樹枝干進行分析(即圖5中數字比)也可得到上述結論。在含有3個因子的項集中,頻繁項集{A，B，D}的支持度為84%,比率最高;其次,頻繁項集{A，B，C}的支持度為71%;再次,頻繁項集{B，C，D}的支持度為69%。說明3項因子耦合作用的情況下,上游水位因子、氣溫因子和時效因子的耦合作用,對大壩變形的影響最大,而上游水位因子、氣溫因子和水溫因子交互作用,以及氣溫因子、水溫因子與時效因子交互作用對大壩變形也有影響。

表3 挖掘數據庫W′所得到的項集

4 結 語

a. 關聯規則挖掘大壩安全監測數據時,對監測資料的完整性要求較低,并且可以比較同類的影響因子重要程度,如比較“氣溫因子”與“水溫因子”的重要程度,也可將不同因子耦合作用的情況進行對比。以上通過統計模型則很難實現。

b. 改進的FP-growth算法新穎、思路清晰、結果簡約、實用性高,可通過多種編程軟件來實現。利用改進的FP-growth算法挖掘大壩變形監測數據庫,能夠很好地建立大壩變形量和影響因子之間的相關關系,得出簡明結論。實例表明,改進后的FP-growth算法為大壩安全監測數據挖掘提供了一條良好的思路。